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
