Thanks!
On Fri, Apr 22, 2016 at 07:46:09PM -0700, Jarno Rajahalme 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> 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
