[ovs-dev] [PATCH 4/7] lib/rculist: New RCU-iterator, single-writer doubly-linked list.

[Jarno Rajahalme]

On Oct 28, 2014, at 4:25 PM, Ben Pfaff <blp at nicira.com> wrote:

> On Fri, Oct 24, 2014 at 01:36:38PM -0700, Jarno Rajahalme wrote:
>> rculist allows concurrent lockless list iteration, while a writer may
>> be modifying the list.  Multiple writers can be supported by using a
>> mutex in addition to rculist.
>> 
>> First user will be added in a following patch.
>> 
>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> 
> I think this will be useful.  Thank you.
> 
> Hardly anything in the original list.h is inlined.  I wonder whether
> we should inline some of those functions.

I’ll look into that. In general the functions are tiny, so it might make sense to just inline most of them.

> 
> I think that the following evaluates to 0xc0000000 on 32-bit and
> 0xc000000000000000 on 64-bit.  That's identifiable, yes, but something
> like 0xcccccccc is even more obvious (and somewhat customary; it is
> both a large number that is likely to segfault and the "trap to
> debugger" instruction on x86).  So would you consider UINTPTR_MAX /
> 0xf * 0xc?
>> +#define RCULIST_POISON (struct rculist *)(((UINTPTR_MAX / 4) + 1) * 3)
> 

Right, I actually noticed that while debugging, but then forgot.

Thanks for the fix!

> In rculist_splice_hidden(), can the first ovsrcu_set() be an
> ovsrcu_set_hidden()?  I think that the stipulation in the comment
> means that the pointer being set can't be visible yet:

Yes, thanks!

>> +/* Removes elements 'first' though 'last' (exclusive) from their current list,
>> + * which may NOT be visible to any other threads (== be hidden from them),
>> + * then inserts them just before 'before'. */
>> +static inline void
>> +rculist_splice_hidden(struct rculist *before, struct rculist *first,
>> +                      struct rculist *last)
>> +    OVS_NO_THREAD_SAFETY_ANALYSIS
>> +{
>> +    struct rculist *last_next;
>> +
>> +    if (first == last) {
>> +        return;
>> +    }
>> +    last = last->prev;
>> +
>> +    /* Cleanly remove 'first'...'last' from its current list. */
>> +    last_next = rculist_next_protected(last);
>> +    last_next->prev = first->prev;
>> +    ovsrcu_set(&first->prev->next, last_next);
>> +
>> +    /* Splice 'first'...'last' into new list. */
>> +    first->prev = before->prev;
>> +    ovsrcu_set(&last->next, before);
>> +    ovsrcu_set(&before->prev->next, first);
>> +    before->prev = last;
>> +}
> 
> I think that the first ovsrcu_set() here can be ovsrcu_set_hidden()
> also:

Right.

>> +static inline void
>> +rculist_replace(struct rculist *element, struct rculist *position)
>> +    OVS_NO_THREAD_SAFETY_ANALYSIS
>> +{
>> +    struct rculist *position_next = rculist_next_protected(position);
>> +
>> +    ovsrcu_set(&element->next, position_next);
>> +    position_next->prev = element;
>> +    element->prev = position->prev;
>> +    ovsrcu_set(&element->prev->next, element);
>> +
>> +#ifndef NDEBUG
>> +    rculist_poison(position); /* XXX: Some overhead due to ovsrcu_postpone() */
>> +#endif
>> +}
> 
> In rculist_front() and rculist_back_protected(), it looks pretty odd
> to write "#ifndef NDEBUG" around an ovs_assert().  I understand the
> idea, but if it's important enough to support NDEBUG here then maybe
> we should just add NDEBUG support to ovs_assert().
> 

OK, I’ll remove NDEBUG from those functions for now.

> Acked-by: Ben Pfaff <blp at nicira.com>

Thanks for the review, pushed to master!

  Jarno