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

cynthiazhang cynthia_zhang123 at 163.com
Wed Jul 5 01:36:17 UTC 2017

From my point of view, the emc_cache in OVS is microflow cache, and it is not implemented  by cuckoo hash. And the second level cache -- megaflow cache uses cuckoo hash.

At 2017-07-04 17:01:52, "Bodireddy, Bhanuprakash" <bhanuprakash.bodireddy at intel.com> wrote:
>>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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-discuss/attachments/20170705/01916014/attachment-0001.html>

More information about the discuss mailing list