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 <b...@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.mau...@hpe.com>
>> Signed-off-by: Jarno Rajahalme <ja...@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.
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
