[ovs-discuss] Questions about Replacement Policy in emc_insert()

Bodireddy, Bhanuprakash bhanuprakash.bodireddy at intel.com
Tue Jul 4 09:01:52 UTC 2017

>When I read the code of emc_cache in dips-netdev.c, I could not understand
>the replacement policy below in emc_insert() as follows():
>      /* Replacement policy: put the flow in an empty (not alive) entry, or
>         * 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;
>        }
>1)The EMC_FOR_EACH_POS_WITH_HASH makes us have two locations to put
>the flow in. If the first entry is dead and the
>function emc_cache_slow_sweep() has not clear this entry, and the second
>entry is also in the same condition. So does this mean that we should compare
>the hash value of each entry?If so ,why we choose the smaller hash value to
>put the new flow in? How to understand the "first place" in the Replacement
>2)So the second question is when we should compare the value of the two
>entries? And why we do this?
>3)Besides, why we define EM_FLOW_HASH_SEGS as 2?

AFAIK, cuckoo hash is used for this implementation. You should read 'Optimistic Concurrent Cuckoo Hash'  
description in https://github.com/openvswitch/ovs/blob/master/lib/cmap.c
This will give greater insights In to cuckoo hash and answers all the above questions. 

-  Bhanuprakash.

More information about the discuss mailing list