[ovs-dev] [PATCH 6/7] lib/classifier: Lockless and robust classifier iteration.

Jarno Rajahalme jrajahalme at nicira.com
Fri Oct 31 20:08:37 UTC 2014


On Oct 30, 2014, at 4:43 PM, Jarno Rajahalme <jrajahalme at nicira.com> wrote:

> 
> On Oct 30, 2014, at 3:38 PM, Ben Pfaff <blp at nicira.com> wrote:
> 
>> On Tue, Oct 28, 2014 at 07:05:01PM -0700, Jarno Rajahalme wrote:
>>> 
>>>> On Oct 28, 2014, at 4:36 PM, Ben Pfaff <blp at nicira.com> wrote:
>>>> 
>>>>> On Fri, Oct 24, 2014 at 01:36:40PM -0700, Jarno Rajahalme wrote:
>>>>> Previously, accurate iteration required writers to be excluded during
>>>>> iteration.  This patch changes the structure of the classifier by
>>>>> moving the list of rules from struct cls_match to struct cls_subtable.
>>>>> The list element is also moved from the struct cls_match to struct
>>>>> cls_rule, which makes iteration more straightforward, and allows the
>>>>> iterators to remain ignorant of the internals of the cls_match.  These
>>>>> changes allow iteration of rules in the classifier by traversing the
>>>>> RCU-friendly subtables vector, and the rculist of rules in each
>>>>> subtable.  Classifier modifications may be performed concurrently, but
>>>>> whether or not the concurrent iterator sees those changes depends on
>>>>> the timing of change.  This is similar to having writers excluded by a
>>>>> mutex, where visibility of changes depends on the timing of mutex
>>>>> acquisition.
>>>>> 
>>>>> The subtable's rculist also allows to make
>>>>> classifier_find_rule_exactly() and classifier_rule_overlaps()
>>>>> lockless.
>>>>> 
>>>>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
>>>> 
>>>> I *think* I follow what's going on here, but just to be sure, let me
>>>> try to explain it.  After this patch, the subtable has a list of every
>>>> rule in the subtable, as 'rules_list'.  The rules in the list are in
>>>> no particular order, except that rules with identical match criteria
>>>> are in subsequent positions.  Is that correct?
>>> 
>>> Yes :-)
>> 
>> The conjunctive match series uses the list of lower-priority rules in
>> lookup.  I think that this patch, as-is, would make that a lot more
>> expensive, because it's no longer cheap to tell whether the next rule
>> in the list has the same match.  I guess one could still mark
>> boundaries somehow; do you have an idea?
> 
> Will have to think about this. However, I totally missed this in my review of the conjunctive match; as the lower-priority rules list is not yet RCU, it cannot be safely used on lookups. It should be sufficient to convert from struct list in struct cls_match to struct rculist, tough.
> 

My assumption with this patch was that the list entry in cls_match is not used in lookup, and hence it can be moved to cls_rule. Now, since conjunctive match is going to use the list in lookup, not only does the list be an rculist, but moving it to cls_rule will add unnecessary memory indirections.

How about simply having two rculist nodes, one in cls_match (like before) and another in cls_rule for iteration? I kind of liked the fact that this patch did not add to the memory footprint at all, but I guess more robust iteration is worth it, even if we add a new rculist node.

  Jarno




More information about the dev mailing list