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

[Ben Pfaff]

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  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 
> >> Signed-off-by: Jarno Rajahalme 
> > 
> > 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 *
> >../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 *
> >../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 *
> >../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 *
> >../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 *
> >../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 *
> >../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 *
> >../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 *
> >../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))
> > 
> >

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

[Jarno Rajahalme]

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  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 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 >> >
>>> Signed-off-by: Jarno Rajahalme 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 *
>>../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 *
>>../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 *
>>../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 *
>>../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 *
>>../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 *
>>../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 *
>>../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 *
>>../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 -

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

[Jarno Rajahalme]

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  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 
>> Signed-off-by: Jarno Rajahalme 
> 
> 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 *
>../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 *
>../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 *
>../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 *
>../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 *
>../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 *
>../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 *
>../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 *
>../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. 

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

[Ben Pfaff]

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 
> Signed-off-by: Jarno Rajahalme 

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 *
../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 *
../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 *
../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 *
../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 *
../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 *
../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 *
../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 *
../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.
__

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

[Ryan Moats]

> --- Original Message ---
> 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 
> Signed-off-by: Jarno Rajahalme 
> ---

Acked-by: Ryan Moats 
___
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev

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

[Jarno Rajahalme]

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 
Signed-off-by: Jarno Rajahalme 
---
 lib/automake.mk  |   2 +
 lib/ccmap.c  | 574 +++
 lib/ccmap.h  |  64 ++
 lib/classifier-private.h |   6 +-
 lib/classifier.c |  42 +---
 5 files changed, 654 insertions(+), 34 deletions(-)
 create mode 100644 lib/ccmap.c
 create mode 100644 lib/ccmap.h

diff --git a/lib/automake.mk b/lib/automake.mk
index 7b829d0..639a87e 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -38,6 +38,8 @@ lib_libopenvswitch_la_SOURCES = \
lib/classifier.c \
lib/classifier.h \
lib/classifier-private.h \
+   lib/ccmap.c \
+   lib/ccmap.h \
lib/cmap.c \
lib/cmap.h \
lib/colors.c \
diff --git a/lib/ccmap.c b/lib/ccmap.c
new file mode 100644
index 000..83f3bb0
--- /dev/null
+++ b/lib/ccmap.c
@@ -0,0 +1,574 @@
+/*
+ * Copyright (c) 2014 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include 
+#include "ccmap.h"
+#include "coverage.h"
+#include "bitmap.h"
+#include "hash.h"
+#include "ovs-rcu.h"
+#include "random.h"
+#include "util.h"
+#include "openvswitch/vlog.h"
+
+VLOG_DEFINE_THIS_MODULE(ccmap);
+
+COVERAGE_DEFINE(ccmap_expand);
+COVERAGE_DEFINE(ccmap_shrink);
+
+/* A count-only version of the cmap. */
+
+/* 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))
+
+typedef ATOMIC(uint64_t) ccmap_node_t;
+
+static inline uint64_t ccmap_node(uint32_t count, uint32_t hash)
+{
+return (uint64_t)count << 32 | hash;
+}
+
+static inline uint32_t ccmap_node_hash(uint64_t node)
+{
+return node;
+}
+
+static inline uint32_t ccmap_node_count(uint64_t node)
+{
+return node >> 32;
+}
+
+/* A cuckoo hash bucket.  Designed to be cache-aligned and exactly one cache
+ * line long. */
+struct ccmap_bucket {
+/* Each node incudes both the hash (low 32-bits) and the count (high
+ * 32-bits), allowing readers always getting a consistent pair. */
+ccmap_node_t nodes[CCMAP_K];
+};
+BUILD_ASSERT_DECL(sizeof(struct ccmap_bucket) == CACHE_LINE_SIZE);
+
+/* Default maximum load factor (as a fraction of UINT32_MAX + 1) before
+ * enlarging a ccmap.  Reasonable values lie between about 75% and 93%.  
Smaller
+ * values waste memory; larger values increase the average insertion time. */
+#define CCMAP_MAX_LOAD ((uint32_t) (UINT32_MAX * .85))
+
+/* Default minimum load factor (as a fraction of UINT32_MAX + 1) before
+ * shrinking a ccmap.  Currently, the value is chosen to be 20%, this
+ * means ccmap will have a 40% load factor after shrink. */
+#define CCMAP_MIN_LOAD ((uint32_t) (UINT32_MAX * .20))
+
+/* The implementation of a concurrent hash map. */
+struct ccmap_impl {
+unsigned int n; /* Number of in-use elements. */
+unsigned int max_n; /* Max elements before enlarging. */
+unsigned int min_n; /* Min elements before shrinking. */
+uint32_t mask;  /* Number of 'buckets', minus one. */
+uint32_t basis; /* Basis for rehashing client's hash values. */
+
+/* Padding to make ccmap_impl exactly one cache line long. */
+uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 5];
+
+struct ccmap_bucket buckets[];
+};
+BUILD_ASSERT_DECL(sizeof(struct ccmap_impl) == CACHE_LINE_SIZE);
+
+static struct ccmap_impl *ccmap_rehash(struct ccmap *, uint32_t mask);
+
+/* Explicit inline keywords in utility functions seem to be necessary
+ * to prevent performance reg