[ovs-dev] dpif-netdev: Simplify emc replacement policy.

Submitted by Ilya Maximets on July 28, 2017, 12:40 p.m.

Details

Message ID 1501245647-14581-1-git-send-email-i.maximets@samsung.com
State New
Headers show

Commit Message

Ilya Maximets July 28, 2017, 12:40 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.

Fix this by removing of srtange hash comparison rule from the
replacement checking. New behavior also matches the comment that
describes replacement policy. This comment wasn't correct before.

Testing shows stable work of exact match cache without misses
with up to 3072 active flows and only 0.05% of EMC misses with
4096 flows. With higher number of flows there is no significant
difference with current implementation.

For the reference, number of EMC misses in current master is
around 20% for the case with 2048 active flows.

Testing performed with 100% EMC insert probability.

Signed-off-by: Ilya Maximets <i.maximets@samsung.com>
---
 lib/dpif-netdev.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

Comments

yipeng1.wang@intel.com July 28, 2017, 6:04 p.m.
Good catch. But I think the hash comparison is to "randomly" choose one of the two entries to replace when both entries are live. Your change would always replace the first one in such case. It might cause some thrashing issue for certain traffic. Meanwhile, to my experience, the original "hash comparison" is also not a good way to choose random entry, I encountered some thrashing issue before.

I think we want some condition like below, but a way to fast choose a random entry. 

        if (!to_be_replaced || (emc_entry_alive(to_be_replaced) && !emc_entry_alive(current_entry) )
            to_be_replaced = current_entry;
        else if((emc_entry_alive(to_be_replaced) && (emc_entry_alive(current_entry))
	to_be_replaced = random_entry;
    
Thanks
Yipeng

> -----Original Message-----
> From: ovs-dev-bounces@openvswitch.org [mailto:ovs-dev-
> bounces@openvswitch.org] On Behalf Of Ilya Maximets
> Sent: Friday, July 28, 2017 5:41 AM
> To: ovs-dev@openvswitch.org
> Cc: Ilya Maximets <i.maximets@samsung.com>; Heetae Ahn
> <heetae82.ahn@samsung.com>
> Subject: [ovs-dev] [PATCH] dpif-netdev: Simplify 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.
> 
> Fix this by removing of srtange hash comparison rule from the
> replacement checking. New behavior also matches the comment that
> describes replacement policy. This comment wasn't correct before.
> 
> Testing shows stable work of exact match cache without misses
> with up to 3072 active flows and only 0.05% of EMC misses with
> 4096 flows. With higher number of flows there is no significant
> difference with current implementation.
> 
> For the reference, number of EMC misses in current master is
> around 20% for the case with 2048 active flows.
> 
> Testing performed with 100% EMC insert probability.
> 
> Signed-off-by: Ilya Maximets <i.maximets@samsung.com>
> ---
>  lib/dpif-netdev.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
> 
> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
> index 47a9fa0..4a8dd80 100644
> --- a/lib/dpif-netdev.c
> +++ b/lib/dpif-netdev.c
> @@ -2054,8 +2054,7 @@ 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) {
> +                && !emc_entry_alive(current_entry))) {
>              to_be_replaced = current_entry;
>          }
>      }
> --
> 2.7.4
> 
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev

Patch hide | download patch | download mbox

diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 47a9fa0..4a8dd80 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -2054,8 +2054,7 @@  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) {
+                && !emc_entry_alive(current_entry))) {
             to_be_replaced = current_entry;
         }
     }