[ovs-dev] [PATCH v2] lib/pvector: Non-intrusive RCU priority vector.

[Jarno Rajahalme]

Solid suggestions as always :-) Pushed to master with the changes,

  Jarno

On Jun 25, 2014, at 11:33 AM, Ben Pfaff <blp at nicira.com> wrote:

> On Wed, Jun 25, 2014 at 04:15:54AM -0700, Jarno Rajahalme wrote:
>> Factor out the priority vector code from the classifier.
>> 
>> Making the classifier use RCU instead of locking requires parallel
>> access to the priority vector, pointing to subtables in descending
>> priority order.  When a new subtable is added, a new copy of the
>> priority vector is allocated, while the current readers can keep on
>> using the old copy they started with.  Adding and removing subtables
>> is usually less frequent than adding and removing rules, so this
>> should not have a visible performance implication.  As an optimization
>> for the userspace datapath use, where all the subtables have the same
>> priority, new subtables can be added to the end of the vector without
>> reallocation and without disturbing readers.
>> 
>> cls_subtables_reset() is now removed, as it served its purpose in bug
>> hunting.  Checks on the new pvector are now incorporated into
>> tests/test-classifier.c.
>> 
>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
>> ---
>> v2: Addressed comments by Ben Pfaff, intergrating lookahead and priority
>>    handling into pvector iterator.
> 
> Thanks!
> 
> pvector_cursor has an n_lookahead member.  pvector_cursor_lookahead()
> has a pointer to a pvector_cursor but also takes an equivalent
> parameter.  It might generate better code, especially in the
> n_lookahead == 0 case, to eliminate the member and just pass
> n_lookahead directly from the PVECTOR_FOR_EACH* macros to
> pvector_cursor_next().  (I didn't check.)
> 
> I don't like the cast to void ** inside the iterator macros.  It runs
> the risk that someone might accidentally supply a non-pointer variable
> and not even get a warning.  What about using a void * return instead,
> like this?  I don't think that we allow storing null pointers inside
> pvectors, so presumably it's OK to use a null pointer as a sentinel.
> 
> diff --git a/lib/pvector.h b/lib/pvector.h
> index fd15ed2..5c22c07 100644
> --- a/lib/pvector.h
> +++ b/lib/pvector.h
> @@ -135,20 +135,20 @@ struct pvector_cursor {
> static inline struct pvector_cursor pvector_cursor_init(const struct pvector *,
>                                                         size_t n_ahead,
>                                                         size_t obj_size);
> -static inline bool pvector_cursor_next(struct pvector_cursor *, void **,
> -                                       int64_t stop_at_priority);
> +static inline void *pvector_cursor_next(struct pvector_cursor *,
> +                                        int64_t stop_at_priority);
> static inline void pvector_cursor_lookahead(const struct pvector_cursor *,
>                                             int n, size_t size);
> 
> #define PVECTOR_FOR_EACH(PTR, PVECTOR)                                  \
>     for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, 0, 0); \
> -         pvector_cursor_next(&cursor__, (void **)&(PTR), -1); )
> +         ((PTR) = pvector_cursor_next(&cursor__, -1)) != NULL; )
> 
> /* Loop while priority is higher than 'PRIORITY' and prefetch objects
>  * of size 'SZ' 'N' objects ahead from the current object. */
> #define PVECTOR_FOR_EACH_PRIORITY(PTR, PRIORITY, N, SZ, PVECTOR)        \
>     for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, N, SZ); \
> -         pvector_cursor_next(&cursor__, (void **)&(PTR), PRIORITY); )
> +         ((PTR) = pvector_cursor_next(&cursor__, PRIORITY)) != NULL; )
> 
> 
> /* Inline implementations. */
> @@ -177,8 +177,8 @@ pvector_cursor_init(const struct pvector *pvec,
>     return cursor;
> }
> 
> -static inline bool pvector_cursor_next(struct pvector_cursor *cursor,
> -                                       void **ptr, int64_t stop_at_priority)
> +static inline void *pvector_cursor_next(struct pvector_cursor *cursor,
> +                                        int64_t stop_at_priority)
> {
>     if (++cursor->entry_idx < cursor->size &&
>         cursor->vector[cursor->entry_idx].priority > stop_at_priority) {
> @@ -186,10 +186,9 @@ static inline bool pvector_cursor_next(struct pvector_cursor *cursor,
>             pvector_cursor_lookahead(cursor, cursor->n_lookahead,
>                                      cursor->obj_size);
>         }
> -        *ptr = cursor->vector[cursor->entry_idx].ptr;
> -        return true;
> +        return cursor->vector[cursor->entry_idx].ptr;
>     }
> -    return false;
> +    return NULL;
> }
> 
> static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor,
> 
> Acked-by: Ben Pfaff <blp at nicira.com>