+\f
+/* Metwally "space-saving" algorithm implementation. */
+
+/* Updates 'ch' to record that a packet was received on 'port_no'. */
+static void
+update_sketch(struct dpif_channel *ch, uint32_t port_no)
+{
+ struct dpif_sketch *sk;
+
+ /* Find an existing counting element for 'port_no' or, if none, replace the
+ * counting element with the fewest hits by 'port_no'. */
+ for (sk = ch->sketches; ; sk++) {
+ if (port_no == sk->port_no) {
+ break;
+ } else if (sk == &ch->sketches[N_SKETCHES - 1]) {
+ sk->port_no = port_no;
+ sk->error = sk->hits;
+ break;
+ }
+ }
+
+ /* Increment the hit count, then re-sort the counting elements (usually
+ * nothing needs to be done). */
+ sk->hits++;
+ while (sk > ch->sketches && sk[-1].hits > sk->hits) {
+ struct dpif_sketch tmp = sk[-1];
+ sk[-1] = *sk;
+ *sk = tmp;
+ sk--;
+ }
+}
+
+/* Divide the counts of all the the counting elements in 'dpif' by 2. See the
+ * comment on SCALE_INTERVAL. */
+static void
+scale_sketches(struct dpif *dpif_)
+{
+ struct dpif_linux *dpif = dpif_linux_cast(dpif_);
+ struct dpif_channel *ch;
+
+ for (ch = dpif->channels; ch < &dpif->channels[N_CHANNELS]; ch++) {
+ struct dpif_sketch *sk;
+
+ for (sk = ch->sketches; sk < &ch->sketches[N_SKETCHES]; sk++) {
+ sk->hits /= 2;
+ sk->error /= 2;
+ }
+ }
+}
+
+/* Logs information about a packet that was recently lost in 'ch' (in
+ * 'dpif_'). */
+static void
+report_loss(struct dpif *dpif_, struct dpif_channel *ch)
+{
+ struct dpif_linux *dpif = dpif_linux_cast(dpif_);
+ static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 5);
+ struct dpif_sketch *sk;
+ struct ds s;
+
+ if (VLOG_DROP_ERR(&rl)) {
+ return;
+ }
+
+ ds_init(&s);
+ if (ch->last_poll != LLONG_MIN) {
+ ds_put_format(&s, " (last polled %lld ms ago)",
+ time_msec() - ch->last_poll);
+ }
+ ds_put_cstr(&s, ", most frequent sources are");
+ for (sk = ch->sketches; sk < &ch->sketches[N_SKETCHES]; sk++) {
+ if (sk->hits) {
+ struct dpif_port port;
+
+ ds_put_format(&s, " %"PRIu32, sk->port_no);
+ if (!dpif_port_query_by_number(dpif_, sk->port_no, &port)) {
+ ds_put_format(&s, "(%s)", port.name);
+ dpif_port_destroy(&port);
+ }
+ if (sk->error) {
+ ds_put_format(&s, ": %u to %u,",
+ sk->hits - sk->error, sk->hits);
+ } else {
+ ds_put_format(&s, ": %u,", sk->hits);
+ }
+ }
+ }
+ ds_chomp(&s, ',');
+
+ VLOG_ERR("%s: lost packet on channel %td%s",
+ dpif_name(dpif_), ch - dpif->channels, ds_cstr(&s));
+ ds_destroy(&s);
+}