On May 20, 2014, at 1:03 PM, Ben Pfaff <[email protected]> wrote:
> On Tue, May 20, 2014 at 12:40:20PM -0700, Jarno Rajahalme wrote:
>>
>> On May 20, 2014, at 10:08 AM, Ben Pfaff <[email protected]> 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
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
