[ovs-dev] [PATCH v1 3/6] dpif-netdev: improve emc lookup performance by contiguous storage of hash value.

Yanqin Wei Yanqin.Wei at arm.com
Tue Jun 2 07:10:02 UTC 2020


In the emc lookup function, hash/flow/key are checked for matching entry.
Each entry comparison loads several cachelines into CPU. So in the
multifow case, processor will wait for the data to be fetched from lower
level cacheline or main memory because of cache miss.
This patch modifies emc table layout to contiguously store the hash items.
It can reduce the number of cache miss for fetching hash value in EMC
lookup miss case. And EMC lookup hit case can also benefit because
processor can parallelly load and match hash and key in different cacheline.

Reviewed-by: Lijian Zhang <Lijian.Zhang at arm.com>
Reviewed-by: Malvika Gupta <Malvika.Gupta at arm.com>
Reviewed-by: Ruifeng Wang <Ruifeng.Wang at arm.com>
Signed-off-by: Yanqin Wei <Yanqin.Wei at arm.com>
---
 lib/dpif-netdev.c | 55 +++++++++++++++++++++++++++--------------------
 1 file changed, 32 insertions(+), 23 deletions(-)

diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index c94d5e8c7..3994f41e4 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -192,13 +192,19 @@ static struct odp_support dp_netdev_support = {
 #define DEFAULT_EM_FLOW_INSERT_INV_PROB 100
 #define DEFAULT_EM_FLOW_INSERT_MIN (UINT32_MAX /                     \
                                     DEFAULT_EM_FLOW_INSERT_INV_PROB)
+struct emc_key {
+    uint32_t len;        /* Length of the following miniflow (incl. map). */
+    struct miniflow mf;
+    uint64_t buf[FLOW_MAX_PACKET_U64S];
+};
 
 struct emc_entry {
     struct dp_netdev_flow *flow;
-    struct netdev_flow_key key;   /* key.hash used for emc hash value. */
+    struct emc_key key;
 };
 
 struct emc_cache {
+    uint32_t hash[EM_FLOW_HASH_ENTRIES];
     struct emc_entry entries[EM_FLOW_HASH_ENTRIES];
     int sweep_idx;                /* For emc_cache_slow_sweep(). */
 };
@@ -220,9 +226,9 @@ struct dfc_cache {
 
 /* Iterate in the exact match cache through every entry that might contain a
  * miniflow with hash 'HASH'. */
-#define EMC_FOR_EACH_POS_WITH_HASH(EMC, CURRENT_ENTRY, HASH)                 \
+#define EMC_FOR_EACH_POS_WITH_HASH(ID, HASH)                 \
     for (uint32_t i__ = 0, srch_hash__ = (HASH);                             \
-         (CURRENT_ENTRY) = &(EMC)->entries[srch_hash__ & EM_FLOW_HASH_MASK], \
+         (ID) = srch_hash__ & EM_FLOW_HASH_MASK, \
          i__ < EM_FLOW_HASH_SEGS;                                            \
          i__++, srch_hash__ >>= EM_FLOW_HASH_SHIFT)
 
@@ -877,8 +883,8 @@ emc_cache_init(struct emc_cache *flow_cache)
 
     flow_cache->sweep_idx = 0;
     for (i = 0; i < ARRAY_SIZE(flow_cache->entries); i++) {
+        flow_cache->hash[i] = 0;
         flow_cache->entries[i].flow = NULL;
-        flow_cache->entries[i].key.hash = 0;
         flow_cache->entries[i].key.len = sizeof(struct miniflow);
         flowmap_init(&flow_cache->entries[i].key.mf.map);
     }
@@ -2733,12 +2739,12 @@ netdev_flow_key_equal(const struct netdev_flow_key *a,
     return a->hash == b->hash && !memcmp(&a->mf, &b->mf, a->len);
 }
 
-/* Used to compare 'netdev_flow_key' in the exact match cache to a miniflow.
+/* Used to compare 'emc_key' in the exact match cache to a miniflow.
  * The maps are compared bitwise, so both 'key->mf' and 'mf' must have been
  * generated by miniflow_extract. */
 static inline bool
-netdev_flow_key_equal_mf(const struct netdev_flow_key *key,
-                         const struct miniflow *mf)
+emc_key_equal_mf(const struct emc_key *key,
+                 const struct miniflow *mf)
 {
     return !memcmp(&key->mf, mf, key->len);
 }
@@ -2840,7 +2846,8 @@ emc_change_entry(struct emc_entry *ce, struct dp_netdev_flow *flow,
         }
     }
     if (key) {
-        netdev_flow_key_clone(&ce->key, key);
+        ce->key.len = key->len;
+        memcpy(&ce->key.mf, &key->mf, key->len);
     }
 }
 
@@ -2849,12 +2856,14 @@ emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key,
            struct dp_netdev_flow *flow)
 {
     struct emc_entry *to_be_replaced = NULL;
-    struct emc_entry *current_entry;
+    uint32_t *to_be_replaced_hash = NULL;
+    uint32_t id;
 
-    EMC_FOR_EACH_POS_WITH_HASH(cache, current_entry, key->hash) {
-        if (netdev_flow_key_equal(&current_entry->key, key)) {
+    EMC_FOR_EACH_POS_WITH_HASH (id, key->hash) {
+        if (key->hash == cache->hash[id]
+            && emc_key_equal_mf(&cache->entries[id].key, &key->mf)) {
             /* We found the entry with the 'mf' miniflow */
-            emc_change_entry(current_entry, flow, NULL);
+            emc_change_entry(&cache->entries[id], flow, NULL);
             return;
         }
 
@@ -2862,14 +2871,15 @@ emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key,
          * in the first entry where it can be */
         if (!to_be_replaced
             || (emc_entry_alive(to_be_replaced)
-                && !emc_entry_alive(current_entry))
-            || current_entry->key.hash < to_be_replaced->key.hash) {
-            to_be_replaced = current_entry;
+                && !emc_entry_alive(&cache->entries[id]))
+            || cache->hash[id] < *to_be_replaced_hash) {
+            to_be_replaced = &cache->entries[id];
+            to_be_replaced_hash = &cache->hash[id];
         }
     }
     /* We didn't find the miniflow in the cache.
      * The 'to_be_replaced' entry is where the new flow will be stored */
-
+    *to_be_replaced_hash = key->hash;
     emc_change_entry(to_be_replaced, flow, key);
 }
 
@@ -2892,15 +2902,14 @@ emc_probabilistic_insert(struct dp_netdev_pmd_thread *pmd,
 static inline struct dp_netdev_flow *
 emc_lookup(struct emc_cache *cache, const struct netdev_flow_key *key)
 {
-    struct emc_entry *current_entry;
-
-    EMC_FOR_EACH_POS_WITH_HASH(cache, current_entry, key->hash) {
-        if (current_entry->key.hash == key->hash
-            && emc_entry_alive(current_entry)
-            && netdev_flow_key_equal_mf(&current_entry->key, &key->mf)) {
+    uint32_t id;
 
+    EMC_FOR_EACH_POS_WITH_HASH (id, key->hash) {
+        if (key->hash == cache->hash[id]
+            && emc_entry_alive(&cache->entries[id])
+            && emc_key_equal_mf(&cache->entries[id].key, &key->mf)) {
             /* We found the entry with the 'key->mf' miniflow */
-            return current_entry->flow;
+            return cache->entries[id].flow;
         }
     }
 
-- 
2.17.1



More information about the dev mailing list