[ovs-dev] [PATCH 4/4] classifier: Avoid inserting duplicates to cmaps.

Jarno Rajahalme jarno at ovn.org
Sat Apr 23 03:01:40 UTC 2016


Scrap the v2, I sent a v3 which avoids a portability problem I introduced in v2.

  Jarno

> On Apr 22, 2016, at 7:46 PM, Jarno Rajahalme <jarno at ovn.org> wrote:
> 
> Thanks for a thorough review Ben! I just sent a v2 to the list.
> 
> I addressed all your concerns and even found a small bug when testing with the new test-ccmap.
> 
>   Jarno
> 
>> On Apr 21, 2016, at 2:42 PM, Ben Pfaff <blp at ovn.org <mailto:blp at ovn.org>> wrote:
>> 
>> On Wed, Apr 13, 2016 at 07:06:46PM -0700, Jarno Rajahalme wrote:
>>> Staged lookup indices assumed that cmap is efficient fealing with
>>> duplicates.  Duplicates are implemented as linked lists, however,
>>> causing removal of rules to become (O^2) and highly cache-inefficient
>>> with large number of duplicates.
>>> 
>>> This was problematic especially when many rules shared the same match
>>> in packet metadata (e.g., a port number, but nothing else).
>>> 
>>> This patch fixes the problem by introducing a new 'count' variant of
>>> the cmap (ccmap), which can be efficiently used to keep counts of
>>> inserted hash values provided by the caller.  This does not require a
>>> node in the user data structure, so this makes the classifier
>>> implementation a bit more memory efficient, too.
>>> 
>>> Reported-by: Alok Kumar Maurya <alok-kumar.maurya at hpe.com <mailto:alok-kumar.maurya at hpe.com>>
>>> Signed-off-by: Jarno Rajahalme <jarno at ovn.org <mailto:jarno at ovn.org>>
>> 
>> At first I was unhappy that we needed a new data structure, then I
>> discovered that I like the new data structure.  Thanks for doing this.
>> 
>> This is a lot of new code to write without adding a test!  Can you adapt
>> test-cmap.c, or write something else, to test ccmap?
>> 
>> My compilers do not like this.  Clang 3.5.0:
>> 
>>    ../lib/ccmap.c:193:9: error: address argument to atomic operation must be a pointer to non-const _Atomic type ('const ccmap_node_t *' (aka 'const _Atomic(uint64_t) *') invalid)
>>    ../lib/ovs-atomic.h:393:5: note: expanded from macro 'atomic_read_relaxed'
>>    ../lib/ovs-atomic-clang.h:53:15: note: expanded from macro 'atomic_read_explicit'
>>    ../lib/ccmap.c:245:9: error: address argument to atomic operation must be a pointer to non-const _Atomic type ('const ccmap_node_t *' (aka 'const _Atomic(uint64_t) *') invalid)
>>    ../lib/ovs-atomic.h:393:5: note: expanded from macro 'atomic_read_relaxed'
>>    ../lib/ovs-atomic-clang.h:53:15: note: expanded from macro 'atomic_read_explicit'
>>    ../lib/ccmap.c:544:13: error: address argument to atomic operation must be a pointer to non-const _Atomic type ('const ccmap_node_t *' (aka 'const _Atomic(uint64_t) *') invalid)
>>    ../lib/ovs-atomic.h:393:5: note: expanded from macro 'atomic_read_relaxed'
>>    ../lib/ovs-atomic-clang.h:53:15: note: expanded from macro 'atomic_read_explicit'
>> 
>> Sparse:
>> 
>>    ../lib/ccmap.c:193:9: warning: incorrect type in argument 1 (different modifiers)
>>    ../lib/ccmap.c:193:9:    expected void *<noident>
>>    ../lib/ccmap.c:193:9:    got unsigned long long const *
>>    ../lib/ccmap.c:193:9: warning: incorrect type in argument 1 (different modifiers)
>>    ../lib/ccmap.c:193:9:    expected void *<noident>
>>    ../lib/ccmap.c:193:9:    got unsigned long long const *
>>    ../lib/ccmap.c:193:9: warning: incorrect type in argument 1 (different modifiers)
>>    ../lib/ccmap.c:193:9:    expected void *<noident>
>>    ../lib/ccmap.c:193:9:    got unsigned long long const *
>>    ../lib/ccmap.c:193:9: warning: incorrect type in argument 1 (different modifiers)
>>    ../lib/ccmap.c:193:9:    expected void *<noident>
>>    ../lib/ccmap.c:193:9:    got unsigned long long const *
>>    ../lib/ccmap.c:245:9: warning: incorrect type in argument 1 (different modifiers)
>>    ../lib/ccmap.c:245:9:    expected void *<noident>
>>    ../lib/ccmap.c:245:9:    got unsigned long long const *
>>    ../lib/ccmap.c:245:9: warning: incorrect type in argument 1 (different modifiers)
>>    ../lib/ccmap.c:245:9:    expected void *<noident>
>>    ../lib/ccmap.c:245:9:    got unsigned long long const *
>>    ../lib/ccmap.c:544:13: warning: incorrect type in argument 1 (different modifiers)
>>    ../lib/ccmap.c:544:13:    expected void *<noident>
>>    ../lib/ccmap.c:544:13:    got unsigned long long const *
>>    ../lib/ccmap.c:544:13: warning: incorrect type in argument 1 (different modifiers)
>>    ../lib/ccmap.c:544:13:    expected void *<noident>
>>    ../lib/ccmap.c:544:13:    got unsigned long long const *
>> 
>> These comments and macros are the only mention of "entries", everything
>> else talks about "nodes", perhaps the names here should be updated.
>> Also, CCMAP_PADDING is never used and it is always 0 despite the
>> comment:
>> 
>>    /* An entry is an 32-bit hash and a 32-bit count. */
>>    #define CCMAP_ENTRY_SIZE (4 + 4)
>> 
>>    /* Number of entries per bucket: 8 */
>>    #define CCMAP_K (CACHE_LINE_SIZE / CCMAP_ENTRY_SIZE)
>> 
>>    /* Pad to make a bucket a full cache line in size: 4 on 32-bit, 0 on 64-bit. */
>>    #define CCMAP_PADDING ((CACHE_LINE_SIZE - 4) - (CCMAP_K * CCMAP_ENTRY_SIZE))
>> 
>> There's a lot of explicit "inline" in this file, presumably left over
>> from cmap.c.  You might be able to drop some of it.
>> 
>> This comment on other_hash() talks about another comment that does not
>> exist:
>> 
>> /* Given a rehashed value 'hash', returns the other hash for that rehashed
>> * value.  This is symmetric: other_hash(other_hash(x)) == x.  (See also "Hash
>> * Functions" at the top of this file.) */
>> 
>> Some of the code here retains the style that we used to use where
>> variables are declared at the top of the block rather than where
>> needed.  It's nice to modernize when one can, e.g. to declare the loop
>> index in the for statement itself.
> 




More information about the dev mailing list