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 <ja...@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 <b...@ovn.org <mailto: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 >>> <mailto:alok-kumar.mau...@hpe.com>> >>> Signed-off-by: Jarno Rajahalme <ja...@ovn.org <mailto: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
