[ovs-dev] [PATCH 1/5] dpif-netdev: Basic CD feature with scalar lookup.

yipeng1.wang at intel.com yipeng1.wang at intel.com
Tue Jun 13 23:09:32 UTC 2017


From: Yipeng Wang <yipeng1.wang at intel.com>

Cuckoo distributor (CD) is a double-hash function hash table, that helps
redirect packets to their corresponding subtables to avoid the sequential
search of megaflow subtables.  This is another layer of cache to cache flows
and their corresponding subtable indexes.  Different from a hash table, CD
can have certain false positive rate (since the full key is not stored for
space efficiency).  Our CD design was partially inspired by earlier concepts
proposed in "simTable"[1] and "Cuckoo Filter"[2], and DPDK's cuckoo hash
implementation.

For the current implementation, the design does not allow displacing items
when a bucket is full, which is different from the behavior of a cuckoo hash
table.  The advantage is that we do not need to store two signatures so that
the struct is more compact.  We use 16 entries per bucket for the
convenience of vector lookup.

Each classifier has its own cuckoo distributor.

Evaluation:
We create set of rules with various src IP. We feed traffic containing 1M
flows with various src IP and dst IP. All the flows hit 10/20/30
rules creating 10/20/30 subtables.

The table below shows the preliminary continuous testing results (full line
speed test) we collected with a uni-directional phy-to-phy setup. The
machine we tested on is a Xeon E5 server running with 2.2GHz cores. OvS
runs with 1 PMD. We use Spirent as the hardware traffic generator.

Scalar CD results:
1M flows:
no.subtable: 10          20          30
cd-ovs       3658328     3028111     2863329
orig_ovs     2683455     1646227     1240501
speedup      1.36x       1.84x       2.31x

[1] H. Lee and B. Lee, Approaches for improving tuple space search-based
table lookup, ICTC '15
[2] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher,
Cuckoo Filter: Practically Better Than Bloom, CoNEXT '14

Signed-off-by: Yipeng Wang <yipeng1.wang at intel.com>
Signed-off-by: Charlie Tai <charlie.tai at intel.com>
Co-authored-by: Charlie Tai <charlie.tai at intel.com>
Signed-off-by: Sameh Gobriel <sameh.gobriel at intel.com>
Co-authored-by: Sameh Gobriel <sameh.gobriel at intel.com>
Signed-off-by: Ren Wang <ren.wang at intel.com>
Co-authored-by: Ren Wang <ren.wang at intel.com>
Signed-off-by: Antonio Fischetti <antonio.fischetti at intel.com>
Co-authored-by: Antonio Fischetti <antonio.fischetti at intel.com>
---
 lib/dpif-netdev.c | 421 +++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 419 insertions(+), 2 deletions(-)

diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 2f224db..c697e78 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -172,6 +172,66 @@ struct emc_cache {
          i__ < EM_FLOW_HASH_SEGS;                                            \
          i__++, srch_hash__ >>= EM_FLOW_HASH_SHIFT)
 
+
+/* Cuckoo distributor (CD) is a double-hash function hash table, that helps
+ * redirect packets to their corresponding subtables to avoid the sequential
+ * search of megaflow subtables.  This is another layer of cache to cache flows
+ * and their corresponding subtable indexes.  Different from a hash table, CD
+ * can have certain false positive rate (since the full key is not stored for
+ * space efficiency).  Our CD design was partially inspired by earlier concepts
+ * proposed in "simTable"[1] and "Cuckoo Filter"[2], and DPDK's cuckoo hash
+ * implementation.
+ *
+ * For the current implementation, the design does not allow displacing items
+ * when a bucket is full, which is different from the behavior of a cuckoo hash
+ * table.  The advantage is that we do not need to store two signatures so that
+ * the struct is more compact.  We use 16 entries per bucket for the
+ * convenience of vector lookup.
+ *
+ * Each classifier has its own cuckoo distributor.
+ *
+ * [1] H. Lee and B. Lee, Approaches for improving tuple space search-based
+ * table lookup, ICTC '15
+ * [2] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher,
+ * Cuckoo Filter: Practically Better Than Bloom, CoNEXT '14
+ */
+
+#define CD_NUM_BUCKETS (1 << 16)
+#define CD_BUCKET_MASK (CD_NUM_BUCKETS - 1)
+/* Number of entries per bucket. */
+#define CD_ENTRIES 16
+#define CD_ENTRY_MASK (CD_ENTRIES - 1)
+
+/* These two seeds are used for hashing out two bucket locations. */
+#define CD_PRIM_SEED 10
+#define CD_SEC_SEED 20
+
+/* This bit is used to choose which bucket to replace CD's entry
+ * in cd_insert. */
+#define CD_BKT_BIT (1 << CD_ENTRIES)
+
+/* Two byte signature and same length of mask. */
+typedef uint16_t cd_sig_t;
+#define CD_SIG_MASK 0xffff
+
+/* Length of Subtable pointer array for cuckoo distributor to index subtables.
+ * The size of the table is at most 2^16-1 entires because the CD's entry
+ * provides 2 bytes for indexing currently.
+ */
+#define SUB_PTR_LEN 256
+
+/* The bucket struct for cuckoo distributor*/
+struct cd_bucket {
+    cd_sig_t sig[CD_ENTRIES];           /* 2-byte long signature. */
+    uint16_t table_index[CD_ENTRIES];   /* index to subtable pointer array. */
+} __attribute__ ((packed));
+
+
+struct cd_cache {
+    struct cd_bucket buckets[CD_NUM_BUCKETS]; /* buckets array. */
+} __attribute__ ((aligned (64)));
+
+
 /* Simple non-wildcarding single-priority classifier. */
 
 /* Time in ms between successive optimizations of the dpcls subtable vector */
@@ -182,6 +242,8 @@ struct dpcls {
     odp_port_t in_port;
     struct cmap subtables_map;
     struct pvector subtables;
+    struct cd_cache *cdtable;   /* The cuckoo distributor. */
+    struct dpcls_subtable *sub_ptrs[SUB_PTR_LEN]; /* Subtable pointer array. */
 };
 
 /* A rule to be inserted to the classifier. */
@@ -202,6 +264,9 @@ static bool dpcls_lookup(struct dpcls *cls,
                          const struct netdev_flow_key keys[],
                          struct dpcls_rule **rules, size_t cnt,
                          int *num_lookups_p);
+static inline struct dpcls_subtable *
+dpcls_find_subtable(struct dpcls *cls, const struct netdev_flow_key *mask);
+
 
 /* Set of supported meter flags */
 #define DP_SUPPORTED_METER_FLAGS_MASK \
@@ -713,6 +778,27 @@ emc_cache_slow_sweep(struct emc_cache *flow_cache)
     flow_cache->sweep_idx = (flow_cache->sweep_idx + 1) & EM_FLOW_HASH_MASK;
 }
 
+/* Initialize the cuckoo distributor structure */
+static void
+cd_init(struct cd_cache *cd)
+{
+    int i, j;
+
+    for (i = 0; i < CD_NUM_BUCKETS; i++) {
+        for (j = 0; j < CD_ENTRIES; j++) {
+            cd->buckets[i].sig[j] = 0;
+            cd->buckets[i].table_index[j] = 0;
+        }
+    }
+}
+
+/* Delete the cuckoo distributor*/
+static void
+cd_delete(struct cd_cache *cd)
+{
+    free(cd);
+}
+
 /* Returns true if 'dpif' is a netdev or dummy dpif, false otherwise. */
 bool
 dpif_is_netdev(const struct dpif *dpif)
@@ -2101,6 +2187,240 @@ emc_lookup(struct emc_cache *cache, const struct netdev_flow_key *key)
     return NULL;
 }
 
+
+static void
+cd_insert(struct cd_cache *cd,
+            const struct netdev_flow_key *key, int index)
+{
+    int i;
+    cd_sig_t tmp_sig = (key->hash & CD_SIG_MASK);
+
+    /*
+     * First element of sub_ptrs (index == 0) means an empty element.
+     * Here we should have a valid entry for CD insertion so it is not 0.
+     */
+    ovs_assert(index != 0);
+    /*
+     * Using 2 different seeds to get 2 totally
+     * random bucket places
+     */
+    uint32_t prim_bucket = hash_int(key->hash, CD_PRIM_SEED) & CD_BUCKET_MASK;
+    uint32_t sec_bucket = hash_int(key->hash, CD_SEC_SEED) & CD_BUCKET_MASK;
+
+    /* Check if the signature is already in either of the two buckets. */
+    for (i = 0; i < CD_ENTRIES; i++) {
+        if (cd->buckets[prim_bucket].sig[i] == tmp_sig) {
+            cd->buckets[prim_bucket].table_index[i] = index;
+            return;
+        }
+        if (cd->buckets[sec_bucket].sig[i] == tmp_sig) {
+            cd->buckets[sec_bucket].table_index[i] = index;
+            return;
+        }
+    }
+
+    /* Check prim_bucket for empty slot */
+    for (i = 0; i < CD_ENTRIES; i++) {
+        if (cd->buckets[prim_bucket].table_index[i] == 0) {
+            cd->buckets[prim_bucket].sig[i] = tmp_sig;
+            cd->buckets[prim_bucket].table_index[i] = index;
+            return;
+        }
+    }
+
+    /* Check sec_bucket for empty slot */
+    if (i == CD_ENTRIES) {
+        for (i = 0; i < CD_ENTRIES; i++) {
+            if (cd->buckets[sec_bucket].table_index[i] == 0) {
+                cd->buckets[sec_bucket].sig[i] = tmp_sig;
+                cd->buckets[sec_bucket].table_index[i] = index;
+                return;
+            }
+        }
+    }
+
+    /* Then we should evict someone. */
+    uint32_t random = random_uint32();
+    uint32_t bucket_choose = prim_bucket;
+    uint32_t evict_idx = random & (CD_ENTRIES-1);
+
+    if (random & CD_BKT_BIT) {
+        bucket_choose = sec_bucket;
+    }
+
+    cd->buckets[bucket_choose].sig[evict_idx] = tmp_sig;
+    cd->buckets[bucket_choose].table_index[evict_idx] = index;
+}
+
+/* 2-stage pipelined cd lookup */
+static void
+cd_lookup_bulk_pipe(struct dpcls *cls, const struct netdev_flow_key keys[],
+                        int32_t num_keys, uint32_t *hit_mask, int data[])
+{
+    int i;
+    uint32_t prim_hitmask = 0;
+    uint32_t sec_hitmask = 0;
+    uint64_t hits = 0;
+    uint32_t loc = 0;
+    struct cd_cache *cd = cls->cdtable;
+
+    if (num_keys == 0) {
+        *hit_mask = 0;
+        return;
+    }
+    cd_sig_t temp_sig0 = (keys[0].hash) & CD_SIG_MASK;
+
+    struct cd_bucket *prim_bkt0 =
+                    &cd->buckets[hash_int(keys[0].hash, CD_PRIM_SEED)
+                    & CD_BUCKET_MASK];
+    struct cd_bucket *sec_bkt0 =
+                    &cd->buckets[hash_int(keys[0].hash, CD_SEC_SEED)
+                    & CD_BUCKET_MASK];
+    rte_prefetch0(prim_bkt0);
+    rte_prefetch0(sec_bkt0);
+
+    for (i = 1; i < num_keys; i++) {
+        cd_sig_t temp_sig1 = (keys[i].hash) & CD_SIG_MASK;
+
+        struct cd_bucket *prim_bkt1 =
+                    &cd->buckets[hash_int(keys[i].hash, CD_PRIM_SEED)
+                    & CD_BUCKET_MASK];
+        struct cd_bucket *sec_bkt1 =
+                    &cd->buckets[hash_int(keys[i].hash, CD_SEC_SEED)
+                    & CD_BUCKET_MASK];
+
+        rte_prefetch0(prim_bkt1);
+        rte_prefetch0(sec_bkt1);
+
+        unsigned int j;
+        prim_hitmask = 0;
+        sec_hitmask = 0;
+
+        for (j = 0; j < CD_ENTRIES; j++) {
+            prim_hitmask |= ((temp_sig0 == prim_bkt0->sig[j]) << j);
+            sec_hitmask |= ((temp_sig0 == sec_bkt0->sig[j]) << j);
+        }
+
+        if (prim_hitmask) {
+            loc = raw_ctz(prim_hitmask);
+            data[i-1] = prim_bkt0->table_index[loc];
+            if (data[i-1] != 0 && cls->sub_ptrs[data[i-1]] != 0) {
+                hits |= 1 << (i - 1);
+                prim_bkt0 = prim_bkt1;
+                sec_bkt0 = sec_bkt1;
+                temp_sig0 = temp_sig1;
+                continue;
+            }
+        }
+
+        if (sec_hitmask) {
+            loc = raw_ctz(sec_hitmask);
+            data[i-1] = sec_bkt0->table_index[loc];
+            if (data[i-1] != 0 && cls->sub_ptrs[data[i-1]] != 0) {
+                hits |= 1 << (i - 1);
+            }
+        }
+
+        prim_bkt0 = prim_bkt1;
+        sec_bkt0 = sec_bkt1;
+        temp_sig0 = temp_sig1;
+    }
+
+    unsigned int j;
+    prim_hitmask = 0;
+    sec_hitmask = 0;
+
+    for (j = 0; j < CD_ENTRIES; j++) {
+        prim_hitmask |= ((temp_sig0 == prim_bkt0->sig[j]) << j);
+        sec_hitmask |= ((temp_sig0 == sec_bkt0->sig[j]) << j);
+    }
+
+    if (prim_hitmask) {
+        loc = raw_ctz(prim_hitmask);
+        data[i-1] = prim_bkt0->table_index[loc];
+        if (data[i-1] != 0 && cls->sub_ptrs[data[i-1]] != 0) {
+            hits |= 1 << (i-1);
+            if (hit_mask != NULL) {
+                *hit_mask = hits;
+            }
+            return;
+        }
+    }
+
+    if (sec_hitmask) {
+        loc = raw_ctz(sec_hitmask);
+        data[i-1] = sec_bkt0->table_index[loc];
+        if (data[i-1] != 0 && cls->sub_ptrs[data[i-1]] != 0) {
+           hits |= 1 << (i - 1);
+        }
+    }
+
+    if (hit_mask != NULL) {
+        *hit_mask = hits;
+    }
+}
+
+static int
+insert_subtable_ptr(struct dpcls *cls, struct dpcls_subtable *subtable)
+{
+    int i;
+
+    ovs_assert(subtable != NULL);
+    for (i = 1; i < SUB_PTR_LEN; i++) {
+        if (cls->sub_ptrs[i] == subtable) {
+            /* When we insert, we should know that the subtable is not inserted
+             * before. */
+            VLOG_ERR("already have the subtable in sub_ptrs");
+            return -1;
+        }
+    }
+
+    for (i = 1; i < SUB_PTR_LEN; i++) {
+        if (cls->sub_ptrs[i] == 0) {
+            cls->sub_ptrs[i] = subtable;
+            return i;
+        }
+    }
+    /* When the subtable count is larger than SUB_PTR_LEN (255 now). */
+    VLOG_INFO("create subtable in sub_ptrs failed, overflow");
+    return 0;
+}
+
+static int
+remove_subtable_ptr(struct dpcls *cls, struct dpcls_subtable *subtable)
+{
+
+    int i;
+
+    ovs_assert(subtable != NULL);
+    for (i = 1; i < SUB_PTR_LEN; i++) {
+        if (cls->sub_ptrs[i] == subtable) {
+            /*reset to subtable index in sub_ptrs to NULL*/
+            cls->sub_ptrs[i] = (struct dpcls_subtable *)0;
+            return i;
+        }
+    }
+
+    /* Happens when remove while more subtable than the SUB_PTR_LEN. */
+    VLOG_INFO("cannot find the table ptr in sub_ptrs to remove");
+    return 0;
+}
+
+static int
+find_index_in_sub_ptrs(struct dpcls *cls,
+                             struct dpcls_subtable *subtable)
+{
+    int i;
+
+    ovs_assert(subtable != NULL);
+    for (i = 1; i < SUB_PTR_LEN; i++) {
+        if (cls->sub_ptrs[i] == subtable) {
+            return i;
+        }
+    }
+    return 0;
+}
+
 static struct dp_netdev_flow *
 dp_netdev_pmd_lookup_flow(struct dp_netdev_pmd_thread *pmd,
                           const struct netdev_flow_key *key,
@@ -2346,6 +2666,7 @@ out:
 
 static struct dp_netdev_flow *
 dp_netdev_flow_add(struct dp_netdev_pmd_thread *pmd,
+                   const struct netdev_flow_key *key,
                    struct match *match, const ovs_u128 *ufid,
                    const struct nlattr *actions, size_t actions_len)
     OVS_REQUIRES(pmd->flow_mutex)
@@ -2393,6 +2714,15 @@ dp_netdev_flow_add(struct dp_netdev_pmd_thread *pmd,
 
     cmap_insert(&pmd->flow_table, CONST_CAST(struct cmap_node *, &flow->node),
                 dp_netdev_flow_hash(&flow->ufid));
+    /* Insert to CD here. */
+    if (OVS_LIKELY(key != NULL)) {
+        struct dpcls_subtable *subtable = dpcls_find_subtable(cls, &mask);
+        int index = find_index_in_sub_ptrs(cls, subtable);
+
+        if (index != 0) {
+            cd_insert(cls->cdtable, key, index);
+        }
+    }
 
     if (OVS_UNLIKELY(!VLOG_DROP_DBG((&upcall_rl)))) {
         struct ds ds = DS_EMPTY_INITIALIZER;
@@ -2460,7 +2790,7 @@ flow_put_on_pmd(struct dp_netdev_pmd_thread *pmd,
     if (!netdev_flow) {
         if (put->flags & DPIF_FP_CREATE) {
             if (cmap_count(&pmd->flow_table) < MAX_FLOWS) {
-                dp_netdev_flow_add(pmd, match, ufid, put->actions,
+                dp_netdev_flow_add(pmd, NULL, match, ufid, put->actions,
                                    put->actions_len);
                 error = 0;
             } else {
@@ -4658,7 +4988,7 @@ handle_packet_upcall(struct dp_netdev_pmd_thread *pmd,
         ovs_mutex_lock(&pmd->flow_mutex);
         netdev_flow = dp_netdev_pmd_lookup_flow(pmd, key, NULL);
         if (OVS_LIKELY(!netdev_flow)) {
-            netdev_flow = dp_netdev_flow_add(pmd, &match, &ufid,
+            netdev_flow = dp_netdev_flow_add(pmd, key, &match, &ufid,
                                              add_actions->data,
                                              add_actions->size);
         }
@@ -5550,14 +5880,27 @@ struct dpcls_subtable {
 static void
 dpcls_init(struct dpcls *cls)
 {
+    int i;
+
     cmap_init(&cls->subtables_map);
     pvector_init(&cls->subtables);
+    int ret = posix_memalign((void **)&cls->cdtable, 64,
+                             sizeof(struct cd_cache));
+    if (ret != 0) {
+        VLOG_ERR("Create cuckoo distributor failed");
+    }
+    cd_init(cls->cdtable);
+    for (i = 0; i < SUB_PTR_LEN; i++) {
+        cls->sub_ptrs[i] = 0;
+    }
+    random_set_seed(100);
 }
 
 static void
 dpcls_destroy_subtable(struct dpcls *cls, struct dpcls_subtable *subtable)
 {
     VLOG_DBG("Destroying subtable %p for in_port %d", subtable, cls->in_port);
+    remove_subtable_ptr(cls, subtable);
     pvector_remove(&cls->subtables, subtable);
     cmap_remove(&cls->subtables_map, &subtable->cmap_node,
                 subtable->mask.hash);
@@ -5580,6 +5923,7 @@ dpcls_destroy(struct dpcls *cls)
         }
         cmap_destroy(&cls->subtables_map);
         pvector_destroy(&cls->subtables);
+        cd_delete(cls->cdtable);
     }
 }
 
@@ -5600,6 +5944,9 @@ dpcls_create_subtable(struct dpcls *cls, const struct netdev_flow_key *mask)
     VLOG_DBG("Creating %"PRIuSIZE". subtable %p for in_port %d",
              cmap_count(&cls->subtables_map), subtable, cls->in_port);
     pvector_publish(&cls->subtables);
+    int ret = insert_subtable_ptr(cls, subtable);
+    /* The subtable should not be in subtable-table yet */
+    ovs_assert(ret >= 0);
 
     return subtable;
 }
@@ -5738,6 +6085,59 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key keys[],
 
     int lookups_match = 0, subtable_pos = 1;
 
+    /*
+     * The cuckoo distributor lookup pass begin first before go to megaflow
+     * cache.  CD hit will return a subtable index to the subtable to lookup.
+     */
+
+    int i;
+    int data[MAP_BITS];
+
+    cd_lookup_bulk_pipe(cls, keys, cnt, &found_map, data);
+
+    ULLONG_FOR_EACH_1(i, found_map) {
+        hashes[i] = netdev_flow_key_hash_in_mask(&keys[i],
+                                &(cls->sub_ptrs[data[i]])->mask);
+        nodes[i] = cmap_find(&((cls->sub_ptrs[data[i]])->rules),
+                             hashes[i]);
+        if (nodes[i] != NULL) {
+            struct dpcls_rule *rule;
+            CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) {
+                if (OVS_LIKELY(dpcls_rule_matches_key(rule, &keys[i]))) {
+                    rules[i] = rule;
+                    lookups_match += 1;
+                    goto scnext;
+                }
+            }
+            ULLONG_SET0(found_map, i);  /* Did not match. */
+            /*
+             * Here means key same in subtable but not same rule
+             * since CD find the correct subtable,
+             * we dont need to insert to CD.
+             */
+
+        scnext:
+            ;
+        } else if (nodes[i] == NULL) {
+             ULLONG_SET0(found_map, i);
+             /* Here means in CD but not in the target subtable.
+              * meaning that it matches to a same (but wrong) key in CD.
+              * we should insert it into CD later when we know
+              * which subtable it hits.
+              */
+        }
+    }
+
+    keys_map &= ~found_map;
+
+    if (!keys_map) {
+        if (num_lookups_p) {
+            *num_lookups_p = lookups_match;
+        }
+
+        return true;              /* All found in CD. */
+    }
+
     /* The Datapath classifier - aka dpcls - is composed of subtables.
      * Subtables are dynamically created as needed when new rules are inserted.
      * Each subtable collects rules with matches on a specific subset of packet
@@ -5778,8 +6178,21 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key keys[],
             /* None of the found rules was a match.  Reset the i-th bit to
              * keep searching this key in the next subtable. */
             ULLONG_SET0(found_map, i);  /* Did not match. */
+            continue;
         next:
             ;                     /* Keep Sparse happy. */
+            /*
+             * If we find things here, it means it misses in CD.
+             * We should insert into CD.
+             */
+            int index = find_index_in_sub_ptrs(cls, subtable);
+            /*
+             * If 0, means not in sub_ptrs, then no need to insert
+             * into CD.
+             */
+            if (index != 0) {
+                cd_insert(cls->cdtable, &keys[i], index);
+            }
         }
         keys_map &= ~found_map;             /* Clear the found rules. */
         if (!keys_map) {
@@ -5793,5 +6206,9 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key keys[],
     if (num_lookups_p) {
         *num_lookups_p = lookups_match;
     }
+    /*
+     * Things that miss in both tables should also be inserted into CD.
+     * the upcall function should be able to handle it.
+     */
     return false;                     /* Some misses. */
 }
-- 
1.9.1



More information about the dev mailing list