[ovs-dev] [RFC PATCH 6/8] dpif-netdev: Simple token-bucket meter implementation.

Jarno Rajahalme jarno.rajahalme at nsn.com
Thu Jun 20 14:26:21 UTC 2013


Signed-off-by: Jarno Rajahalme <jarno.rajahalme at nsn.com>
---
 lib/dpif-netdev.c |  273 +++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 236 insertions(+), 37 deletions(-)

diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 1f57917..32a0b7a 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -60,6 +60,9 @@ VLOG_DEFINE_THIS_MODULE(dpif_netdev);
 /* Configuration parameters. */
 enum { MAX_PORTS = 256 };       /* Maximum number of ports. */
 enum { MAX_FLOWS = 65536 };     /* Maximum number of flows in flow table. */
+enum { MAX_METERS = 65536 };    /* Maximum number of meters. */
+enum { MAX_BANDS = 8 };         /* Maximum number of bands / meter. */
+enum { MAX_DSCP_PREC_LEVEL = 0 }; /* Maximum increase in DSCP value. */
 
 /* Enough headroom to add a vlan tag, plus an extra 2 bytes to allow IP
  * headers to be aligned on a 4-byte boundary.  */
@@ -81,6 +84,34 @@ struct dp_netdev_queue {
     unsigned int head, tail;
 };
 
+/* Set of supported meter flags */
+#define DP_SUPPORTED_METER_FLAGS_MASK \
+    (OFPMF13_STATS | OFPMF13_PKTPS | OFPMF13_KBPS | OFPMF13_BURST)
+
+/* Set of supported meter band types */
+#define DP_SUPPORTED_METER_BAND_TYPES           \
+    ( 1 << OFPMBT13_DROP )
+
+struct dp_meter_band {
+    struct ofputil_meter_band up; /* type, prec_level, pad, rate, burst_size */
+    uint32_t bucket;
+    uint64_t packet_count;
+    uint64_t byte_count;
+};
+
+struct dp_meter {
+    uint16_t flags;
+    uint16_t n_bands;
+    uint64_t used;
+    uint64_t packet_count;
+    uint64_t byte_count;
+    struct dp_meter_band bands[];
+};
+
+static bool
+dp_netdev_action_meter(void *dp_, struct ofpbuf *packet, uint32_t meter_id,
+                       long long int now);
+
 /* Datapath based on the network device interface from netdev.h. */
 struct dp_netdev {
     const struct dpif_class *class;
@@ -100,6 +131,10 @@ struct dp_netdev {
     struct dp_netdev_port *ports[MAX_PORTS];
     struct list port_list;
     unsigned int serial;
+
+    /* Meters. */
+    struct dp_meter *meters[MAX_METERS]; /* meter bands */
+    uint32_t meter_free; /* Next free meter */
 };
 
 /* A port in a netdev-based datapath. */
@@ -1026,43 +1061,7 @@ dpif_netdev_recv_purge(struct dpif *dpif)
     struct dpif_netdev *dpif_netdev = dpif_netdev_cast(dpif);
     dp_netdev_purge_queues(dpif_netdev->dp);
 }
-
-/* Meters */
-static void
-dpif_netdev_meter_get_features(const struct dpif * dpif OVS_UNUSED,
-                               struct ofputil_meter_features *features)
-{
-    features->max_meters = 0;
-    features->band_types = 0;
-    features->capabilities = 0;
-    features->max_bands = 0;
-    features->max_color = 0;
-}
-
-static int
-dpif_netdev_meter_set(struct dpif *dpif OVS_UNUSED,
-                      ofproto_meter_id *meter_id OVS_UNUSED,
-                      const struct ofputil_meter_config *config OVS_UNUSED)
-{
-    return EFBIG; /* meter_id out of range */
-}
 
-static int
-dpif_netdev_meter_get(const struct dpif *dpif OVS_UNUSED,
-                      ofproto_meter_id meter_id OVS_UNUSED,
-                      struct ofputil_meter_stats *stats OVS_UNUSED)
-{
-    return EFBIG; /* meter_id out of range */
-}
-
-static int
-dpif_netdev_meter_del(struct dpif *dpif OVS_UNUSED,
-                      ofproto_meter_id meter_id OVS_UNUSED,
-                      struct ofputil_meter_stats *stats OVS_UNUSED)
-{
-    return EFBIG; /* meter_id out of range */
-}
-
 static void
 dp_netdev_flow_used(struct dp_netdev_flow *flow, const struct ofpbuf *packet)
 {
@@ -1213,7 +1212,207 @@ dp_netdev_execute_actions(struct dp_netdev *dp,
 {
     odp_execute_actions(dp, packet, key, actions, actions_len,
                         dp_netdev_output_port, dp_netdev_action_userspace,
-                        NULL);
+                        dp_netdev_action_meter);
+}
+
+/* Meters */
+static void
+dpif_netdev_meter_get_features(const struct dpif * dpif OVS_UNUSED,
+                         struct ofputil_meter_features *features)
+{
+    features->max_meters = MAX_METERS;
+    features->band_types = DP_SUPPORTED_METER_BAND_TYPES >> 1;
+    features->capabilities = DP_SUPPORTED_METER_FLAGS_MASK;
+    features->max_bands = MAX_BANDS;
+    features->max_color = MAX_DSCP_PREC_LEVEL;
+}
+
+static bool
+dp_netdev_action_meter(void *dp_, struct ofpbuf *packet, uint32_t meter_id,
+                       long long int now)
+{
+    struct dp_netdev *dp = dp_;
+    struct dp_meter *meter = dp->meters[meter_id];
+    struct dp_meter_band *band;
+    int delta_t = (now - meter->used); /* msec */
+    int divider;
+    uint32_t volume;
+    int i, band_exceeded_max = -1;
+    uint32_t band_exceeded_rate = 0;
+
+    meter->used = now;
+    meter->packet_count += 1;
+    meter->byte_count += packet->size;
+
+    if (meter->flags & OFPMF13_PKTPS) {
+        divider = 1000; /* msec * packets per second / 1000 = packets */
+        volume = 1; /* Take one packet from the bucket */
+    } else {
+        /* rate in kbps, bucket in bytes */
+        divider = 8; /* msec * kbps / 8 = bytes */
+        volume = packet->size; /* How much to take from the bucket */
+    }
+
+    /* Update all bands and find the one hit with the highest rate */
+    for (i = 0; i < meter->n_bands; ++i) {
+        band = &meter->bands[i];
+        /* Extremely large delta_t could wrap the 32-bit bucket around */
+        band->bucket += delta_t * band->up.rate / divider;
+        if (band->bucket > band->up.burst_size) {
+            band->bucket = band->up.burst_size;
+        }
+        if (band->bucket >= volume) {
+            band->bucket -= volume;
+        } else if (band->up.rate > band_exceeded_rate) {
+            band_exceeded_rate = band->up.rate;
+            band_exceeded_max = i;
+        }
+    }
+
+    if (band_exceeded_max < 0) {
+        return false; /* Do not drop */
+    }
+
+    band = &meter->bands[band_exceeded_max];
+    band->packet_count += 1;
+    band->byte_count += packet->size;
+
+    switch (band->up.type) {
+    case OFPMBT13_DROP:
+        return true; /* drop */
+    case OFPMBT13_DSCP_REMARK:
+        /* FIXME: NOT IMPLEMETED YET */
+    default:
+        NOT_REACHED();
+    }
+}
+
+static inline void
+dp_delete_meter(struct dp_netdev *dp, uint32_t meter_id)
+{
+    if (dp->meters[meter_id]) {
+        free(dp->meters[meter_id]);
+        dp->meters[meter_id] = NULL;
+    }
+}
+
+static int
+dpif_netdev_meter_set(struct dpif *dpif, ofproto_meter_id *meter_id,
+                      const struct ofputil_meter_config *config)
+{
+    struct dp_netdev *dp = get_dp_netdev(dpif);
+    uint32_t mid = meter_id->uint32;
+    struct dp_meter *meter;
+    int i;
+
+    if (mid == UINT32_MAX) {
+        mid = dp->meter_free;
+    }
+    if (mid >= MAX_METERS) {
+        return EFBIG; /* Meter_id out of range. */
+    }
+
+    if (config->flags & ~DP_SUPPORTED_METER_FLAGS_MASK) {
+        return EBADF; /* Unsupported flags set */
+    }
+
+    /* Validate bands */
+    if (config->n_bands == 0 || config->n_bands > MAX_BANDS)
+        return EINVAL; /* Too many bands */
+    for (i = 0; i < config->n_bands; ++i) {
+        switch (config->bands[i].type) {
+        case OFPMBT13_DROP:
+            break;
+        case OFPMBT13_DSCP_REMARK:
+        default:
+            return ENODEV; /* Unsupported band type */
+        }
+    }
+
+    /* Allocate meter */
+    meter = xzalloc(sizeof *meter
+                    + config->n_bands * sizeof(struct dp_meter_band));
+    if (meter) {
+        /* Free existing meter, if any */
+        dp_delete_meter(dp, mid);
+
+        meter->flags = config->flags;
+        meter->n_bands = config->n_bands;
+
+        /* set up bands */
+        for (i = 0; i < config->n_bands; ++i) {
+            meter->bands[i].up = config->bands[i];
+            meter->bands[i].bucket = config->bands[i].burst_size;
+        }
+        dp->meters[mid] = meter;
+        meter_id->uint32 = mid; /* Store on success. */
+
+        /* Find next free meter */
+        if (dp->meter_free == mid) { /* Now taken. */
+            do {
+                if (++mid >= MAX_METERS) { /* Wrap around */
+                    mid = 0;
+                }
+                if (mid == dp->meter_free) { /* Full circle */
+                    mid = MAX_METERS;
+                    break;
+                }
+            } while (dp->meters[mid]);
+            dp->meter_free = mid; /* Next free meter or MAX_METERS */
+        }
+        return 0;
+    }
+    return ENOMEM;
+}
+
+static int
+dpif_netdev_meter_get(const struct dpif *dpif,
+                      ofproto_meter_id meter_id_,
+                      struct ofputil_meter_stats *stats)
+{
+    const struct dp_netdev *dp = get_dp_netdev(dpif);
+    const struct dp_meter *meter;
+    uint32_t meter_id = meter_id_.uint32;
+
+    if (meter_id >= MAX_METERS) {
+        return EFBIG;
+    }
+    meter = dp->meters[meter_id];
+    if (!meter) {
+        return ENOENT;
+    }
+    if (stats) {
+        int i = 0;
+
+        stats->packet_in_count = meter->packet_count;
+        stats->byte_in_count = meter->byte_count;
+
+        for (i = 0; i < stats->n_bands && i < meter->n_bands; ++i) {
+            stats->bands[i].packet_count = meter->bands[i].packet_count;
+            stats->bands[i].byte_count = meter->bands[i].byte_count;
+        }
+        stats->n_bands = i;
+    }
+    return 0;
+}
+
+static int
+dpif_netdev_meter_del(struct dpif *dpif, ofproto_meter_id meter_id_,
+                      struct ofputil_meter_stats *stats)
+{
+    struct dp_netdev *dp = get_dp_netdev(dpif);
+    int error;
+
+    error = dpif_netdev_meter_get(dpif, meter_id_, stats);
+    if (!error) {
+        uint32_t meter_id = meter_id_.uint32;
+        dp_delete_meter(dp, meter_id);
+        /* Keep free meter index as low as possible */
+        if (meter_id < dp->meter_free) {
+            dp->meter_free = meter_id;
+        }
+    }
+    return error;
 }
 
 const struct dpif_class dpif_netdev_class = {
-- 
1.7.10.4




More information about the dev mailing list