[ovs-dev] [cmap v2 1/2] cmap: New module for cuckoo hash table.

[Jarno Rajahalme]

On May 20, 2014, at 1:03 PM, Ben Pfaff <blp at nicira.com> wrote:

> On Tue, May 20, 2014 at 12:40:20PM -0700, Jarno Rajahalme wrote:
>> 
>> On May 20, 2014, at 10:08 AM, Ben Pfaff <blp at nicira.com> wrote:
>> 
>>> On Tue, May 20, 2014 at 09:12:23AM -0700, Ben Pfaff wrote:
>>>> On Fri, May 16, 2014 at 04:38:02PM -0700, Jarno Rajahalme wrote:
>>>>>> +static bool
>>>>>> +cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,
>>>>>> +                struct cmap_bucket *b)
>>>>>> +{
>>>>>> +    int i;
>>>>>> +
>>>>>> +    for (i = 0; i < CMAP_K; i++) {
>>>>>> +        struct cmap_node *node = b->nodes[i];
>>>>>> +        if (b->hashes[i] == hash && node) {
>>>>>> +            for (;;) {
>>>>>> +                struct cmap_node *next = cmap_node_next_protected(node);
>>>>>> +                if (!next) {
>>>>>> +                    ovsrcu_set(&node->next, new_node);
>>>>>> +                    return true;
>>>>>> +                }
>>>>>> +                node = next;
>>>>>> +            }
>>>>> 
>>>>> It would be faster to add the dup to the beginning of the list instead:
>>>>> 
>>>>>   for (i = 0; i < CMAP_K; i++) {
>>>>>       if (b->hashes[i] == hash) {
>>>>>           ovsrcu_set(&new_node->next, b->nodes[i]);
>>>>>           b->nodes[i] = new_node;
>>>>>           return true;
>>>>>       }
>>>>>   }
>>>>> 
>>>>> Syncing via the counter should be unnecessary, as the hash value was
>>>>> already set.
>>>> 
>>>> That's a good point about the counter.  That's the reason that I
>>>> switched to this method in v2.
>>> 
>>> OK, here's an incremental I'm folding in.  What do you think?
>>> 
>>> diff --git a/lib/cmap.c b/lib/cmap.c
>>> index a1367bc..30a6e2d 100644
>>> --- a/lib/cmap.c
>>> +++ b/lib/cmap.c
>>> @@ -392,7 +392,7 @@ cmap_set_bucket(struct cmap_bucket *b, int i,
>>> 
>>> /* Searches 'b' for a node with the given 'hash'.  If it finds one, adds
>>> * 'new_node' to the node's linked list and returns true.  If it does not find
>>> - * one, returns false.  */
>>> + * one, returns false. */
>>> static bool
>>> cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,
>>>                struct cmap_bucket *b)
>>> @@ -402,14 +402,30 @@ cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,
>>>    for (i = 0; i < CMAP_K; i++) {
>>>        struct cmap_node *node = b->nodes[i];
>>>        if (b->hashes[i] == hash && node) {
>>> +            struct cmap_node *p;
>>> +
>>> +            /* The common case is that 'new_node' is a singleton, with a null
>>> +             * 'next' pointer, but rehashing can add a longer chain.  Find the
>>> +             * end of the chain starting at 'new_node', then splice 'node' to
>>> +             * the end of that chain. */
>> 
>> I think this could be done regardless of the value of the
>> ?node?. ?node? could be NULL, if a preceding remove just NULLed the
>> node pointer but left the hash intact. I.e. it seems to me that when
>> a node is removed, there is no reason to remove the hash value from
>> the bucket, meaning that syncing via the counter would not be
>> necessary when removing nodes from cmap.
> 
> I believe that the incremental that I posted does what you are describing.
> It does not call cmap_set_bucket() or set ->hashes[].

There is still this before the added code lines:

@@ -402,14 +402,30 @@ cmap_insert_dup(struct cmap_node *new_node, uint32_t hash,
    for (i = 0; i < CMAP_K; i++) {
        struct cmap_node *node = b->nodes[i];
        if (b->hashes[i] == hash && node) {

i.e., ‘node’ is checked to be non-NULL.

  Jarno

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-dev/attachments/20140520/4657aa1c/attachment-0005.html>