[ovs-dev,v3,2/2] dpif-netdev: Fix emc replacement policy.

Message ID 1501856248-28555-3-git-send-email-i.maximets@samsung.com
State New
Headers show

Commit Message

Ilya Maximets Aug. 4, 2017, 2:17 p.m.
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@samsung.com>
---

Some test results from Antonio Fischetti here:
https://mail.openvswitch.org/pipermail/ovs-dev/2017-August/336707.html

 lib/dpif-netdev.c | 23 ++++++++++++++++-------
 1 file changed, 16 insertions(+), 7 deletions(-)

Comments

Fischetti, Antonio Aug. 4, 2017, 3:08 p.m. | #1
LGTM

Acked-by: Antonio Fischetti <antonio.fischetti@intel.com>

> -----Original Message-----
> From: Ilya Maximets [mailto:i.maximets@samsung.com]
> Sent: Friday, August 4, 2017 3:17 PM
> To: ovs-dev@openvswitch.org
> Cc: Heetae Ahn <heetae82.ahn@samsung.com>; Darrell Ball <dball@vmware.com>;
> Wang, Yipeng1 <yipeng1.wang@intel.com>; Kevin Traynor <ktraynor@redhat.com>;
> Loftus, Ciara <ciara.loftus@intel.com>; Fischetti, Antonio
> <antonio.fischetti@intel.com>; Ilya Maximets <i.maximets@samsung.com>
> Subject: [PATCH v3 2/2] dpif-netdev: Fix emc replacement policy.
> 
> 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@samsung.com>
> ---

Patch

diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index e23c674..c36fd32 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -158,6 +158,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 /        \
@@ -2058,7 +2061,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;
@@ -2071,12 +2074,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.
@@ -2094,11 +2097,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);
     }
 }