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

[Ben Pfaff]

On Mon, Jun 09, 2014 at 11:53:51AM -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 on optimization

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 it's purpose in bug

"its" purpose

> hunting.  Checks on the new pvector are now incorporated into
> tests/test-classifier.c.
> 
> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>

I would start the top-level comment in pvector.h with a sentence or
short paragraph that briefly describes what a concurrent priority
vector is.  As is, it jumps in with what readers and writers can do,
without saying what the overall data structure is for.

I think that the size calculation in pvector_impl_dup() is wrong,
because it does not include sizeof(struct pvector_impl).

It looks like PVECTOR_EXTRA_ALLOC only affects the allocation when a
pvector_element is removed, but it seems to me that it could be
equally useful to have extra space in other cases.

"Poisoning" in pvector_destroy() seems like a good idea that we could
apply elsewhere.

pvector.c defines PVECTOR_IMPL_FOR_EACH_REVERSE but does not use it.

I spent some time studying the code that rearranges the priority
vectors upon insertion, deletion, and priority change.  I did not see
any bugs.

classifier_lookup() could be a little more straightforward if it did
not open-code the cursor iteration.  Did you consider adding a pvector
iteration macro that embeds lookahead?  Then it could easily be used
in find_match_miniflow() also (is there reason to believe that this
function wouldn't benefit from lookahead too?).

Thanks,

Ben.