[ovs-dev] [PATCH] lib/classifier: Fix array splicing.

Jarno Rajahalme jrajahalme at nicira.com
Mon May 12 15:43:10 UTC 2014


On May 12, 2014, at 8:36 AM, Ben Pfaff <blp at nicira.com> wrote:

> On Sun, May 11, 2014 at 11:55:01PM -0700, Jarno Rajahalme wrote:
>> Array splicing was broken when multiple elements were being moved,
>> resulting in the priority order being mixed.  This came up when the
>> highest priority rule from a subtable was removed and the subtable
>> needed to be moved down the priority list by more than one position.
>> 
>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> 
> Can you explain what this function does?  I feel like it should be
> obvious (I mean, clearly it's reordering the array), but in fact I'm
> having trouble puzzling it out.
> 

It moves elements starting from ‘start’ and ending before ‘end’ to ‘to’. This is the same as swapping the places of items [to,start) and [start,end), when to < start. I implemented shifting to one direction only, so in the buggy case the arguments are shifted like this: to = start, start = end and end = (old) to.

The loop moves elements one by one, moving the items [to, start) forward by one, and moving the (old) ‘start' element to ‘to’. I forgot to advance the ‘to’ at each round...

  Jarno

>> diff --git a/lib/classifier.c b/lib/classifier.c
>> index a9046cd..aef57bb 100644
>> --- a/lib/classifier.c
>> +++ b/lib/classifier.c
>> @@ -224,12 +224,14 @@ cls_subtable_cache_splice(struct cls_subtable_entry *to,
>>         to = start; start = end; end = temp;
>>     }
>>     if (to < start) {
>> +        /* Move elements [start, end) to (to) one by one. */
>>         while (start != end) {
>>             struct cls_subtable_entry temp = *start;
>> 
>> +            /* Shift array by one, making space for the element at 'temp'. */
>>             memmove(to + 1, to, (start - to) * sizeof *to);
>>             *to = temp;
>> -            start++;
>> +            start++; to++;
>>         }
>>     } /* Else nothing to be done. */
>> }
>> -- 
>> 1.7.10.4
>> 
>> _______________________________________________
>> dev mailing list
>> dev at openvswitch.org
>> http://openvswitch.org/mailman/listinfo/dev




More information about the dev mailing list