[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