[ovs-dev] [PATCH v2 2/2] dpif-netdev: Fix emc replacement policy.

[Ilya Maximets]

Current EMC replacement policy allows to replace active EMC entry
even if there are dead (empty) entries available. This leads to
EMC trashing even on few hundreds of flows. In some cases PMD
threads starts to execute classifier lookups even in tests with
50 - 100 active flows.

Looks like the hash comparison rule was introduced to randomly
choose one of alive entries to replace. But it doesn't work as
needed and also hashes has nothing common with randomness.

Lets fix the replacement policy by removing hash checking and
using the random value passed from 'emc_probabilistic_insert()'
only while considering replace of the alive entry.
This should give us nearly fair way to choose the entry to replace.

We are avoiding calculation of the new random value by reusing
bits of already generated random for probabilistic EMC insertion.
Bits higher than 'EM_FLOW_INSERT_INV_PROB_SHIFT' are used because
lower bits are less than 'min' and not fully random.

Not replacing of alive entries while dead ones exists allows to
significantly decrease EMC trashing.

Testing shows stable work of exact match cache without misses
with up to 3072 - 6144 active flows (depends on traffic pattern).

Signed-off-by: Ilya Maximets <i.maximets at samsung.com>
---
 lib/dpif-netdev.c | 23 ++++++++++++++++-------
 1 file changed, 16 insertions(+), 7 deletions(-)

diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 123a7c9..a714329 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -155,6 +155,9 @@ struct netdev_flow_key {
 #define EM_FLOW_INSERT_INV_PROB_SHIFT 20
 #define EM_FLOW_INSERT_INV_PROB_MAX  (1 << EM_FLOW_INSERT_INV_PROB_SHIFT)
 #define EM_FLOW_INSERT_INV_PROB_MASK (EM_FLOW_INSERT_INV_PROB_MAX - 1)
+/* We will use bits higher than EM_FLOW_INSERT_INV_PROB_SHIFT of the random
+ * value for EMC replacement policy. */
+BUILD_ASSERT_DECL(32 - EM_FLOW_INSERT_INV_PROB_SHIFT >= EM_FLOW_HASH_SEGS);
 /* Default EMC insert probability is 1 / DEFAULT_EM_FLOW_INSERT_INV_PROB */
 #define DEFAULT_EM_FLOW_INSERT_INV_PROB 100
 #define DEFAULT_EM_FLOW_INSERT_MIN (EM_FLOW_INSERT_INV_PROB_MAX /        \
@@ -2041,7 +2044,7 @@ emc_change_entry(struct emc_entry *ce, struct dp_netdev_flow *flow,
 
 static inline void
 emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key,
-           struct dp_netdev_flow *flow)
+           struct dp_netdev_flow *flow, uint32_t random_value)
 {
     struct emc_entry *to_be_replaced = NULL;
     struct emc_entry *current_entry;
@@ -2054,12 +2057,12 @@ emc_insert(struct emc_cache *cache, const struct netdev_flow_key *key,
         }
 
         /* Replacement policy: put the flow in an empty (not alive) entry, or
-         * in the first entry where it can be */
+         * in the random 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) {
+                && (!emc_entry_alive(current_entry) || random_value & 1))) {
             to_be_replaced = current_entry;
+            random_value >>= 1;
         }
     }
     /* We didn't find the miniflow in the cache.
@@ -2077,11 +2080,17 @@ emc_probabilistic_insert(struct dp_netdev_pmd_thread *pmd,
      * default the value is UINT32_MAX / 100 which yields an insertion
      * probability of 1/100 ie. 1% */
 
-    uint32_t min;
+    uint32_t min, random_value;
     atomic_read_relaxed(&pmd->dp->emc_insert_min, &min);
 
-    if (min && (random_uint32() & EM_FLOW_INSERT_INV_PROB_MASK) < min) {
-        emc_insert(&pmd->flow_cache, key, flow);
+    if (!min) {
+        return;
+    }
+
+    random_value = random_uint32();
+    if ((random_value & EM_FLOW_INSERT_INV_PROB_MASK) < min) {
+        emc_insert(&pmd->flow_cache, key, flow,
+                   random_value >> EM_FLOW_INSERT_INV_PROB_SHIFT);
     }
 }
 
-- 
2.7.4