[ovs-dev] [cmap 1/2] cmap: New module for cuckoo hash table.

Ben Pfaff blp at nicira.com
Fri May 2 00:14:55 UTC 2014


This implements an "optimistic concurrent cuckoo hash", a single-writer,
multiple-reader hash table data structure.  The point of this data
structure is performance, so this commit message focuses on performance.

I tested the performance of cmap with the test-cmap utility included in
this commit.  It takes three parameters for benchmarking:

    - n, the number of elements to insert.

    - n_threads, the number of threads to use for searching and
      mutating the hash table.

    - mutations, the percentage of operations that should modify the
      hash table, from 0% to 100%.

e.g. "test-cmap 1000000 16 1" inserts one million elements, uses 16
threads, and 1% of the operations modify the hash table.

Any given run does the following for both hmap and cmap
implementations:

    - Inserts n elements into a hash table.

    - Iterates over all of the elements.

    - Spawns n_threads threads, each of which searches for each of the
      elements in the hash table, once, and removes the specified
      percentage of them.

    - Removes each of the (remaining) elements and destroys the hash
      table.

and reports the time taken by each step,

The tables below report results for various parameters.  n_threads=16
was used each time, on a 16-core x86-64 machine.  The compiler used was
Clang 3.5.  (GCC yields different numbers but similar relative results.)

The results show:

    - Insertion is generally 3x to 5x faster in an hmap.

    - Iteration is generally about 3x faster in a cmap.

    - Search and mutation is 4x faster with .1% mutations and the
      advantage grows as the fraction of mutations grows.  This is
      because a cmap does not require locking for read operations,
      even in the presence of a writer.

      With no mutations, however, no locking is required in the hmap
      case, and the hmap is somewhat faster.  This is because raw hmap
      search is somewhat simpler and faster than raw cmap search.

    - Destruction is faster, usually by less than 2x, in an hmap.

n=10,000,000:

        .1% mutations    1% mutations    10% mutations     no mutations
          cmap  hmap     cmap   hmap      cmap   hmap       cmap  hmap
insert:   6132  2182     6136   2178      6111   2174       6124  2180
iterate:   370  1203      378   1201       370   1200        371  1202
search:   1375  8692     2393  28197     18402  80379       1281  1097
destroy:  1382  1187     1197   1034       324    241       1405  1205

n=1,000,000:

        .1% mutations    1% mutations    10% mutations     no mutations
          cmap  hmap     cmap   hmap      cmap   hmap       cmap  hmap
insert:    311    25      310     60       311     59        310    60
iterate:    25    62       25     64        25     57         25    60
search:    115   637      197   2266      1803   7284        101    67
destroy:   103    64       90     59        25     13        104    66

n=100,000:

        .1% mutations    1% mutations    10% mutations     no mutations
          cmap  hmap     cmap   hmap      cmap   hmap       cmap  hmap
insert:     25     6       26      5        25      5         25     5
iterate:     1     3        1      3         1      3          2     3
search:     12    57       27    219       164    735         10     5
destroy:     5     3        6      3         2      1          6     4

Signed-off-by: Ben Pfaff <blp at nicira.com>
---
 lib/automake.mk   |    2 +
 lib/cmap.c        |  765 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/cmap.h        |  155 +++++++++++
 lib/ovs-thread.h  |    2 +-
 lib/util.h        |    5 +
 tests/automake.mk |    2 +
 tests/test-cmap.c |  453 +++++++++++++++++++++++++++++++
 7 files changed, 1383 insertions(+), 1 deletion(-)
 create mode 100644 lib/cmap.c
 create mode 100644 lib/cmap.h
 create mode 100644 tests/test-cmap.c

diff --git a/lib/automake.mk b/lib/automake.mk
index de3f068..2f5cc02 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -34,6 +34,8 @@ lib_libopenvswitch_la_SOURCES = \
 	lib/cfm.h \
 	lib/classifier.c \
 	lib/classifier.h \
+	lib/cmap.c \
+	lib/cmap.h \
 	lib/command-line.c \
 	lib/command-line.h \
 	lib/compiler.h \
diff --git a/lib/cmap.c b/lib/cmap.c
new file mode 100644
index 0000000..02d6b8f
--- /dev/null
+++ b/lib/cmap.c
@@ -0,0 +1,765 @@
+/*
+ * 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 <config.h>
+#include "cmap.h"
+#include "hash.h"
+#include "ovs-rcu.h"
+#include "random.h"
+#include "util.h"
+
+/* Optimistic Concurrent Cuckoo Hash
+ * =================================
+ *
+ * A "cuckoo hash" is an open addressing hash table schema, designed such that
+ * a given element can be in one of only a small number of buckets 'd', each of
+ * which each holds up to a small number 'k' elements.  Thus, the expected and
+ * worst-case lookup times are O(1) because they require comparing no more than
+ * a fixed number of elements (k * d).  Inserting a new element can require
+ * moving around existing elements, but it is also O(1) amortized expected
+ * time.
+ *
+ * An optimistic concurrent hash table goes one step further, making it
+ * possible for a single writer to execute concurrently with any number of
+ * readers without requiring the readers to take any locks.
+ *
+ * This cuckoo hash implementation uses:
+ *
+ *    - Two hash functions (d=2).  More hash functions allow for a higher load
+ *      factor, but increasing 'k' is easier and the benefits of increasing 'd'
+ *      quickly fall off with the 'k' values used here.  Also, the method of
+ *      generating hashes used in this implementation is hard to reasonably
+ *      extend beyond d=2.  Finally, each additional hash function means that a
+ *      lookup has to look at least one extra cache line.
+ *
+ *    - 5 or 7 elements per bucket (k=5 or k=7), chosen to make buckets
+ *      exactly one cache line in size.
+ *
+ * According to Erlingsson [4], these parameters suggest a maximum load factor
+ * of about 93%.  The current implementation is conservative, expanding the
+ * hash table when it is over 85% full.
+ *
+ *
+ * Hash Functions
+ * ==============
+ *
+ * A cuckoo hash requires multiple hash functions.  When reorganizing the hash
+ * becomes too difficult, it also requires the ability to change the hash
+ * functions.  Requiring the client to provide multiple hashes and to be able
+ * to change them to new hashes upon insertion is inconvenient.
+ *
+ * This implementation takes another approach.  The client provides a single,
+ * fixed hash.  The cuckoo hash internally "rehashes" this hash against a
+ * randomly selected basis value (see rehash()).  This rehashed value is one of
+ * the two hashes.  The other hash is computed by 16-bit circular rotation of
+ * the rehashed value.  Updating the basis changes the hash functions.
+ *
+ * To work properly, the hash functions used by a cuckoo hash must be
+ * independent.  If one hash function is a function of the other (e.g. h2(x) =
+ * h1(x) + 1, or h2(x) = hash(h1(x))), then insertion will eventually fail
+ * catastrophically (loop forever) because of collisions.  With this rehashing
+ * technique, the two hashes are completely independent for masks up to 16 bits
+ * wide.  For masks wider than 16 bits, only 32-n bits are independent between
+ * the two hashes.  Thus, it becomes risky to grow a cuckoo hash table beyond
+ * about 2**24 buckets (about 71 million elements with k=5 and maximum load
+ * 85%).  Fortunately, Open vSwitch does not normally deal with hash tables
+ * this large.
+ *
+ *
+ * References
+ * ==========
+ *
+ * [1] D. Zhou, B. Fan, H. Lim, M. Kaminsky, D. G. Andersen, "Scalable, High
+ *     Performance Ethernet Forwarding with CuckooSwitch".  In Proc. 9th
+ *     CoNEXT, Dec. 2013.
+ *
+ * [2] B. Fan, D. G. Andersen, and M. Kaminsky. "MemC3: Compact and concurrent
+ *     memcache with dumber caching and smarter hashing".  In Proc. 10th USENIX
+ *     NSDI, Apr. 2013
+ *
+ * [3] R. Pagh and F. Rodler. "Cuckoo hashing". Journal of Algorithms, 51(2):
+ *     122-144, May 2004.
+ *
+ * [4] U. Erlingsson, M. Manasse, F. McSherry, "A Cool and Practical
+ *     Alternative to Traditional Hash Tables".  In Proc. 7th Workshop on
+ *     Distributed Data and Structures (WDAS'06), 2006.
+ */
+/* An entry is an int and a pointer: 8 bytes on 32-bit, 12 bytes on 64-bit. */
+#define CMAP_ENTRY_SIZE (4 + (UINTPTR_MAX == UINT32_MAX ? 4 : 8))
+
+/* Number of entries per bucket: 7 on 32-bit, 5 on 64-bit. */
+#define CMAP_K ((CACHE_LINE_SIZE - 4) / CMAP_ENTRY_SIZE)
+
+/* Pad to make a bucket a full cache line in size: 4 on 32-bit, 0 on 64-bit. */
+#define CMAP_PADDING ((CACHE_LINE_SIZE - 4) - (CMAP_K * CMAP_ENTRY_SIZE))
+
+/* A cuckoo hash bucket.  Designed to be cache-aligned and exactly one cache
+ * line long. */
+struct cmap_bucket {
+    /* Allows readers to track in-progress changes.  Initially zero, each
+     * writer increments this value just before and just after each change (see
+     * cmap_set_bucket()).  Thus, a reader can ensure that it gets a consistent
+     * snapshot by waiting for the counter to become even (see
+     * read_even_counter()), then checking that its value does not change while
+     * examining the bucket (see cmap_find()). */
+    atomic_uint32_t counter;
+
+    /* (hash, node) slots.  They are parallel arrays instead of an array of
+     * structs to reduce the amount of space lost to padding.
+     *
+     * The slots are in no particular order.  A null pointer indicates that a
+     * pair is unused.  In-use slots are not necessarily in the earliest
+     * slots. */
+    uint32_t hashes[CMAP_K];
+    struct cmap_node *nodes[CMAP_K];
+
+    /* Padding to make cmap_bucket exactly one cache line long. */
+#if CMAP_PADDING > 0
+    uint8_t pad[CMAP_PADDING];
+#endif
+};
+BUILD_ASSERT_DECL(sizeof(struct cmap_bucket) == CACHE_LINE_SIZE);
+
+/* Default maximum load factor (as a fraction of UINT32_MAX + 1) before
+ * enlarging a cmap.  Reasonable values lie between about 75% and 93%.  Smaller
+ * values waste memory; larger values increase the average insertion time. */
+#define CMAP_DEFAULT_MAX_LOAD ((uint32_t) (UINT32_MAX * .85))
+
+/* The implementation of a concurrent hash map. */
+struct cmap_impl {
+    unsigned int n;             /* Number of in-use elements. */
+    unsigned int max_n;         /* Max elements before enlarging. */
+    unsigned int max_load;      /* Max load as fraction of UINT32_MAX. */
+    uint32_t mask;              /* Number of 'buckets', minus one. */
+    uint32_t basis;             /* Basis for rehashing client's hash values. */
+
+    /* Padding to make cmap_impl exactly one cache line long. */
+    uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 5];
+
+    struct cmap_bucket buckets[];
+};
+BUILD_ASSERT_DECL(sizeof(struct cmap_impl) == CACHE_LINE_SIZE);
+
+static struct cmap_impl *cmap_rehash(struct cmap *, uint32_t mask);
+
+/* 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.) */
+static uint32_t
+other_hash(uint32_t hash)
+{
+    return (hash << 16) | (hash >> 16);
+}
+
+/* Returns the rehashed value for 'hash' within 'impl'.  (See also "Hash
+ * Functions" at the top of this file.) */
+static uint32_t
+rehash(const struct cmap_impl *impl, uint32_t hash)
+{
+    return mhash_finish(mhash_add(impl->basis, hash), 4);
+}
+
+static struct cmap_impl *
+cmap_get_impl(const struct cmap *cmap)
+{
+    return ovsrcu_get(struct cmap_impl *, &cmap->impl);
+}
+
+static uint32_t
+calc_max_n(uint32_t mask, uint32_t max_load)
+{
+    return ((uint64_t) (mask + 1) * CMAP_K * max_load) >> 32;
+}
+
+static struct cmap_impl *
+cmap_impl_create(uint32_t mask, uint32_t max_load)
+{
+    struct cmap_impl *impl;
+
+    ovs_assert(is_pow2(mask + 1));
+
+    impl = xzalloc_cacheline(sizeof *impl
+                             + (mask + 1) * sizeof *impl->buckets);
+    impl->n = 0;
+    impl->max_n = calc_max_n(mask, max_load);
+    impl->max_load = max_load;
+    impl->mask = mask;
+    impl->basis = random_uint32();
+
+    return impl;
+}
+
+/* Initializes 'cmap' as an empty concurrent hash map. */
+void
+cmap_init(struct cmap *cmap)
+{
+    ovsrcu_set(&cmap->impl, cmap_impl_create(0, CMAP_DEFAULT_MAX_LOAD));
+}
+
+/* Destroys 'cmap'.
+ *
+ * The client is responsible for destroying any data previously held in
+ * 'cmap'. */
+void
+cmap_destroy(struct cmap *cmap)
+{
+    if (cmap) {
+        free_cacheline(cmap_get_impl(cmap));
+    }
+}
+
+/* Changes the maximum load factor before enlarging 'cmap' to 'max_load', which
+ * is a fraction of UINT32_MAX + 1.  For example, a 'max_load' of UINT32_MAX/2
+ * would cause 'cmap' to be enlarged when it is half full.
+ *
+ * 'cmap' must be empty.
+ *
+ * Reasonable load factors lie between about 75% and 93%.
+ *
+ * This function is intended for testing.  Otherwise, it is best to use the
+ * default load factor (see CMAP_DEFAULT_MAX_LOAD). */
+void
+cmap_set_max_load_factor(struct cmap *cmap, uint32_t max_load)
+{
+    struct cmap_impl *impl = cmap_get_impl(cmap);
+
+    /* Not worth implementing rehashing for changing the max load factor. */
+    ovs_assert(cmap_is_empty(cmap));
+
+    /* Force the max load factor into a reasonable range:
+     *
+     *    - At least one element per bucket.
+     *
+     *    - At most 93%, based on Fig. 1 in Erlingsson [4].
+     */
+    max_load = MAX(max_load, UINT32_MAX / CMAP_K + 1);
+    max_load = MIN(max_load, (uint32_t) (UINT32_MAX * .93));
+    impl->max_load = max_load;
+    impl->max_n = calc_max_n(impl->mask, max_load);
+}
+
+/* Returns the number of elements in 'cmap'. */
+size_t
+cmap_count(const struct cmap *cmap)
+{
+    return cmap_get_impl(cmap)->n;
+}
+
+/* Returns true if 'cmap' is empty, false otherwise. */
+bool
+cmap_is_empty(const struct cmap *cmap)
+{
+    return cmap_count(cmap) == 0;
+}
+
+static uint32_t
+read_counter(struct cmap_bucket *bucket)
+{
+    uint32_t counter;
+
+    atomic_read(&bucket->counter, &counter);
+    return counter;
+}
+
+static uint32_t
+read_even_counter(struct cmap_bucket *bucket)
+{
+    uint32_t counter;
+
+    do {
+        counter = read_counter(bucket);
+    } while (OVS_UNLIKELY(counter & 1));
+
+    return counter;
+}
+
+/* Searches 'cmap' for an element with the specified 'hash'.  If one or more is
+ * found, returns a pointer to the first one, otherwise a null pointer.  All of
+ * the nodes on the returned list are guaranteed to have exactly the given
+ * 'hash'.
+ *
+ * This function works even if 'cmap' is changing concurrently.  If 'cmap' is
+ * not changing, then cmap_find_locked() is slightly faster.
+ *
+ * CMAP_FOR_EACH_WITH_HASH is usually more convenient. */
+struct cmap_node *
+cmap_find(const struct cmap *cmap, uint32_t hash)
+{
+    struct cmap_impl *impl = cmap_get_impl(cmap);
+    uint32_t h1 = rehash(impl, hash);
+    uint32_t h2 = other_hash(h1);
+    struct cmap_bucket *b1;
+    struct cmap_bucket *b2;
+    uint32_t c1, c2;
+    int i;
+
+retry:
+    b1 = &impl->buckets[h1 & impl->mask];
+    c1 = read_even_counter(b1);
+    for (i = 0; i < CMAP_K; i++) {
+        struct cmap_node *node = b1->nodes[i];
+        if (node && b1->hashes[i] == h1 && OVS_LIKELY(node->hash == hash)) {
+            if (OVS_UNLIKELY(read_counter(b1) != c1)) {
+                goto retry;
+            }
+            return node;
+        }
+    }
+
+    b2 = &impl->buckets[h2 & impl->mask];
+    c2 = read_even_counter(b2);
+    for (i = 0; i < CMAP_K; i++) {
+        struct cmap_node *node = b2->nodes[i];
+        if (node && b2->hashes[i] == h2 && OVS_LIKELY(node->hash == hash)) {
+            if (OVS_UNLIKELY(read_counter(b2) != c2)) {
+                goto retry;
+            }
+            return node;
+        }
+    }
+
+    if (OVS_UNLIKELY(read_counter(b1) != c1) ||
+        OVS_UNLIKELY(read_counter(b2) != c2)) {
+        goto retry;
+    }
+    return NULL;
+}
+
+static int
+cmap_find_slot(struct cmap_bucket *b, uint32_t hash, uint32_t h)
+{
+    int i;
+
+    for (i = 0; i < CMAP_K; i++) {
+        struct cmap_node *node = b->nodes[i];
+        if (node && b->hashes[i] == h && OVS_LIKELY(node->hash == hash)) {
+            return i;
+        }
+    }
+    return -1;
+}
+
+static struct cmap_node *
+cmap_find_bucket_locked(struct cmap_impl *impl, uint32_t hash, uint32_t h)
+{
+    struct cmap_bucket *b = &impl->buckets[h & impl->mask];
+    int i;
+
+    for (i = 0; i < CMAP_K; i++) {
+        struct cmap_node *node = b->nodes[i];
+        if (node && b->hashes[i] == h && OVS_LIKELY(node->hash == hash)) {
+            return node;
+        }
+    }
+    return NULL;
+}
+
+/* Like cmap_find(), but only for use if 'cmap' cannot change concurrently.
+ *
+ * CMAP_FOR_EACH_WITH_HASH_LOCKED is usually more convenient. */
+struct cmap_node *
+cmap_find_locked(const struct cmap *cmap, uint32_t hash)
+{
+    struct cmap_impl *impl = cmap_get_impl(cmap);
+    uint32_t h1 = rehash(impl, hash);
+    uint32_t h2 = other_hash(hash);
+    struct cmap_node *node;
+
+    node = cmap_find_bucket_locked(impl, hash, h1);
+    if (node) {
+        return node;
+    }
+    return cmap_find_bucket_locked(impl, hash, h2);
+}
+
+static int
+cmap_find_empty_slot(const struct cmap_bucket *b)
+{
+    int i;
+
+    for (i = 0; i < CMAP_K; i++) {
+        if (!b->nodes[i]) {
+            return i;
+        }
+    }
+    return -1;
+}
+
+static void
+cmap_set_bucket(struct cmap_bucket *b, int i,
+                struct cmap_node *node, uint32_t h)
+{
+    uint32_t c;
+
+    atomic_read_explicit(&b->counter, &c, memory_order_acquire);
+    atomic_store_explicit(&b->counter, c + 1, memory_order_release);
+    b->nodes[i] = node;
+    b->hashes[i] = h;
+    atomic_store_explicit(&b->counter, c + 2, memory_order_release);
+}
+
+static bool
+cmap_insert_bucket(struct cmap_impl *impl, struct cmap_node *node, uint32_t h)
+{
+    struct cmap_bucket *b = &impl->buckets[h & impl->mask];
+    int i;
+
+    i = cmap_find_empty_slot(b);
+    if (i >= 0) {
+        cmap_set_bucket(b, i, node, h);
+        return true;
+    }
+    return false;
+}
+
+static bool
+cmap_insert_dup(struct cmap_impl *impl, struct cmap_node *new_node, uint32_t h)
+{
+    struct cmap_bucket *b = &impl->buckets[h & impl->mask];
+    int i;
+
+    for (i = 0; i < CMAP_K; i++) {
+        struct cmap_node *node = b->nodes[i];
+        if (node && b->hashes[i] == h && node->hash == new_node->hash) {
+            struct cmap_node *p;
+
+            p = new_node;
+            while (p->next) {
+                p = p->next;
+            }
+            p->next = node;
+            cmap_set_bucket(b, i, new_node, h);
+
+            return true;
+        }
+    }
+    return false;
+}
+
+static void
+cmap_check_hashes(struct cmap_impl *impl)
+{
+    struct cmap_bucket *b;
+
+    return;
+    for (b = impl->buckets; b <= &impl->buckets[impl->mask]; b++) {
+        int i;
+
+        for (i = 0; i < CMAP_K; i++) {
+            struct cmap_node *node = b->nodes[i];
+            uint32_t h = b->hashes[i];
+
+            ovs_assert(!node || (h & impl->mask) == b - impl->buckets);
+        }
+    }
+}
+
+static bool
+cmap_try_insert(struct cmap_impl *impl, struct cmap_node *node, uint32_t hash)
+{
+    enum { MAX_PATH = 4 };
+    struct cmap_path {
+        struct cmap_bucket *end;
+        int start;
+        int n;
+        uint8_t slots[MAX_PATH];
+    };
+
+    uint32_t h1 = rehash(impl, hash);
+    uint32_t h2 = other_hash(h1);
+
+    enum { MAX_QUEUE = 512 };
+    BUILD_ASSERT_DECL(IS_POW2(MAX_QUEUE));
+    struct cmap_path queue[MAX_QUEUE];
+    unsigned int head = 0, tail = 0;
+
+    /* Handle the easy cases. */
+    if (cmap_insert_dup(impl, node, h1) ||
+        cmap_insert_dup(impl, node, h2) ||
+        cmap_insert_bucket(impl, node, h1) ||
+        cmap_insert_bucket(impl, node, h2)) {
+        return true;
+    }
+
+    queue[head].end = &impl->buckets[h1 & impl->mask];
+    queue[head].start = 0;
+    queue[head].n = 0;
+    head++;
+
+    if ((h1 & impl->mask) != (h2 & impl->mask)) {
+        queue[head].end = &impl->buckets[h2 & impl->mask];
+        queue[head].start = 1;
+        queue[head].n = 0;
+        head++;
+    }
+
+    while (head - tail > 0 && head - tail < MAX_QUEUE - CMAP_K) {
+        const struct cmap_path *p = &queue[tail++ & (MAX_QUEUE - 1)];
+        struct cmap_bucket *b = p->end;
+        int i;
+
+        for (i = 0; i < CMAP_K; i++) {
+            struct cmap_bucket *b2;
+            int j;
+
+            b2 = &impl->buckets[other_hash(b->hashes[i]) & impl->mask];
+            j = cmap_find_empty_slot(b2);
+            if (j >= 0) {
+                struct cmap_bucket *buckets[MAX_PATH + 2];
+                int slots[MAX_PATH + 2];
+                uint32_t h = p->start ? h2 : h1;
+                int k;
+
+                for (k = 0; k < p->n; k++) {
+                    slots[k] = p->slots[k];
+                }
+                slots[p->n] = i;
+                slots[p->n + 1] = j;
+
+                buckets[0] = &impl->buckets[h & impl->mask];
+                for (k = 0; k <= p->n; k++) {
+                    buckets[k + 1] = &impl->buckets[other_hash(buckets[k]->hashes[slots[k]]) & impl->mask];
+                }
+
+                cmap_check_hashes(impl);
+                for (k = p->n + 1; k > 0; k--) {
+                    int slot = slots[k - 1];
+
+                    cmap_set_bucket(buckets[k], slots[k],
+                                    buckets[k - 1]->nodes[slot],
+                                    other_hash(buckets[k - 1]->hashes[slot]));
+                    cmap_check_hashes(impl);
+                }
+                cmap_set_bucket(buckets[0], slots[0], node, h);
+                cmap_check_hashes(impl);
+
+                return true;
+            }
+
+            if (b2 != b && p->n < MAX_PATH) {
+                struct cmap_path *p2 = &queue[head++ & (MAX_QUEUE - 1)];
+
+                *p2 = *p;
+                p2->end = b2;
+                p2->slots[p2->n++] = i;
+            }
+        }
+    }
+
+    return false;
+}
+
+/* Inserts 'node', with the given 'hash', into 'cmap'.  The caller must ensure
+ * that 'cmap' cannot change concurrently (from another thread).  If duplicates
+ * are undesirable, the caller must have already verified that 'cmap' does not
+ * contain a duplicate of 'node'. */
+void
+cmap_insert(struct cmap *cmap, struct cmap_node *node, uint32_t hash)
+{
+    struct cmap_impl *impl = cmap_get_impl(cmap);
+
+    node->hash = hash;
+    node->next = NULL;
+
+    if (OVS_UNLIKELY(impl->n >= impl->max_n)) {
+        impl = cmap_rehash(cmap, (impl->mask << 1) | 1);
+    }
+
+    while (OVS_UNLIKELY(!cmap_try_insert(impl, node, hash))) {
+        impl = cmap_rehash(cmap, impl->mask);
+    }
+    impl->n++;
+}
+
+static bool
+cmap_remove__(struct cmap_impl *impl, struct cmap_node *node, uint32_t h)
+{
+    struct cmap_bucket *b = &impl->buckets[h & impl->mask];
+    int slot;
+
+    slot = cmap_find_slot(b, node->hash, h);
+    if (slot < 0) {
+        return false;
+    }
+
+    if (b->nodes[slot] == node) {
+        cmap_set_bucket(b, slot, node->next, h);
+    } else {
+        struct cmap_node **prev;
+
+        prev = &b->nodes[slot]->next;
+        while (*prev != node) {
+            prev = &(*prev)->next;
+        }
+        *prev = node->next;
+        atomic_thread_fence(memory_order_acq_rel);
+    }
+    return true;
+}
+
+/* Removes 'node' from 'cmap'.  The caller must ensure that 'cmap' cannot
+ * change concurrently (from another thread).
+ *
+ * 'node' must not be destroyed or modified or inserted back into 'cmap' or
+ * into any other concurrent hash map while any other thread might be accessing
+ * it.  One correct way to do this is to free it from an RCU callback with
+ * ovsrcu_postpone(). */
+void
+cmap_remove(struct cmap *cmap, struct cmap_node *node)
+{
+    struct cmap_impl *impl = cmap_get_impl(cmap);
+    uint32_t h1 = rehash(impl, node->hash);
+    uint32_t h2 = other_hash(h1);
+    bool ok;
+
+    ok = cmap_remove__(impl, node, h1) || cmap_remove__(impl, node, h2);
+    ovs_assert(ok);
+    impl->n--;
+}
+
+static bool
+cmap_try_rehash(const struct cmap_impl *old, struct cmap_impl *new)
+{
+    const struct cmap_bucket *b;
+
+    for (b = old->buckets; b <= &old->buckets[old->mask]; b++) {
+        int i;
+
+        for (i = 0; i < CMAP_K; i++) {
+            /* possible optimization here because we know the hashes are
+             * unique */
+            struct cmap_node *node = b->nodes[i];
+
+            if (node && !cmap_try_insert(new, node, node->hash)) {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
+static struct cmap_impl *
+cmap_rehash(struct cmap *cmap, uint32_t mask)
+{
+    struct cmap_impl *old = cmap_get_impl(cmap);
+    struct cmap_impl *new;
+
+    new = cmap_impl_create(mask, old->max_load);
+    ovs_assert(old->n < new->max_n);
+
+    while (!cmap_try_rehash(old, new)) {
+        memset(new->buckets, 0, (mask + 1) * sizeof *new->buckets);
+        new->basis = random_uint32();
+    }
+
+    new->n = old->n;
+    ovsrcu_set(&cmap->impl, new);
+    ovsrcu_postpone(free_cacheline, old);
+
+    return new;
+}
+
+/* Initializes 'cursor' for iterating through 'cmap'.
+ *
+ * Use via CMAP_FOR_EACH. */
+void
+cmap_cursor_init(struct cmap_cursor *cursor, const struct cmap *cmap)
+{
+    cursor->impl = cmap_get_impl(cmap);
+    cursor->bucket_idx = 0;
+    cursor->entry_idx = 0;
+}
+
+/* Returns the next node for 'cursor' to visit, following 'node', or NULL if
+ * the last node has been visited.
+ *
+ * Use via CMAP_FOR_EACH. */
+struct cmap_node *
+cmap_cursor_next(struct cmap_cursor *cursor, const struct cmap_node *node)
+{
+    const struct cmap_impl *impl = cursor->impl;
+
+    if (node && node->next) {
+        return node->next;
+    }
+
+    while (cursor->bucket_idx <= impl->mask) {
+        const struct cmap_bucket *b = &impl->buckets[cursor->bucket_idx];
+
+        while (cursor->entry_idx < CMAP_K) {
+            struct cmap_node *node = b->nodes[cursor->entry_idx++];
+            if (node) {
+                return node;
+            }
+        }
+
+        cursor->bucket_idx++;
+        cursor->entry_idx = 0;
+    }
+
+    return NULL;
+}
+
+/* Returns the next node in 'cmap' in hash order, or NULL if no nodes remain in
+ * 'cmap'.  Uses '*pos' to determine where to begin iteration, and updates
+ * '*pos' to pass on the next iteration into them before returning.
+ *
+ * It's better to use plain CMAP_FOR_EACH and related functions, since they are
+ * faster and better at dealing with cmaps that change during iteration.
+ *
+ * Before beginning iteration, set '*pos' to all zeros. */
+struct cmap_node *
+cmap_next_position(const struct cmap *cmap,
+                   struct cmap_position *pos)
+{
+    struct cmap_impl *impl = cmap_get_impl(cmap);
+    unsigned int bucket = pos->bucket;
+    unsigned int entry = pos->entry;
+    unsigned int offset = pos->offset;
+
+    while (bucket <= impl->mask) {
+        const struct cmap_bucket *b = &impl->buckets[bucket];
+
+        while (entry < CMAP_K) {
+            const struct cmap_node *node = b->nodes[entry];
+            unsigned int i;
+
+            for (i = 0; node; i++) {
+                if (i == offset) {
+                    if (node->next) {
+                        offset++;
+                    } else {
+                        entry++;
+                        offset = 0;
+                    }
+                    pos->bucket = bucket;
+                    pos->entry = entry;
+                    pos->offset = offset;
+                    return CONST_CAST(struct cmap_node *, node);
+                }
+            }
+
+            entry++;
+            offset = 0;
+        }
+
+        bucket++;
+        entry = offset = 0;
+    }
+
+    pos->bucket = pos->entry = pos->offset = 0;
+    return NULL;
+}
diff --git a/lib/cmap.h b/lib/cmap.h
new file mode 100644
index 0000000..e51f8b8
--- /dev/null
+++ b/lib/cmap.h
@@ -0,0 +1,155 @@
+/*
+ * 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.
+ */
+
+#ifndef CMAP_H
+#define CMAP_H 1
+
+#include <stdbool.h>
+#include <stdint.h>
+#include "ovs-rcu.h"
+#include "util.h"
+
+/* Concurrent hash map
+ * ===================
+ *
+ * A single-writer, multiple-reader hash table that efficiently supports
+ * duplicates.
+ *
+ *
+ * Thread-safety
+ * =============
+ *
+ * The general rules are:
+ *
+ *    - Only a single thread may safely call into cmap_insert() or
+ *      cmap_remove() at any given time.
+ *
+ *    - Any number of threads may use functions and macros that search or
+ *      iterate through a given cmap, even in parallel with other threads
+ *      calling cmap_insert() or cmap_remove().
+ *
+ *      There is one exception: cmap_find_locked() is only safe if no thread is
+ *      currently calling cmap_insert() or cmap_remove().  (Use ordinary
+ *      cmap_find() if that is not guaranteed.)
+ *
+ * Writers must use special care to ensure that any elements that they remove
+ * do not get freed or reused until readers have finished with them.  This
+ * includes inserting the element back into its original cmap or a different
+ * one.  One correct way to do this is to free them from an RCU callback with
+ * ovsrcu_postpone().
+ */
+
+/* A concurrent hash map node, to be embedded inside the data structure being
+ * mapped.
+ *
+ * All nodes linked together on a chain have exactly the same hash value. */
+struct cmap_node {
+    struct cmap_node *next;     /* Next node with same hash. */
+    uint32_t hash;              /* Hash value. */
+};
+
+/* Concurrent hash map. */
+struct cmap {
+    OVSRCU_TYPE(struct cmap_impl *) impl;
+};
+
+/* Initialization. */
+void cmap_init(struct cmap *);
+void cmap_destroy(struct cmap *);
+
+void cmap_set_max_load_factor(struct cmap *, uint32_t max_load);
+
+/* Count. */
+size_t cmap_count(const struct cmap *);
+bool cmap_is_empty(const struct cmap *);
+
+/* Insertion and deletion. */
+void cmap_insert(struct cmap *, struct cmap_node *, uint32_t hash);
+void cmap_remove(struct cmap *, struct cmap_node *);
+
+/* Search.
+ *
+ * These macros iterate NODE over all of the nodes in CMAP that have hash value
+ * equal to HASH.  MEMBER must be the name of the 'struct cmap_node' member
+ * within NODE.
+ *
+ * The _LOCKED variant is very slightly faster, but it may only be used if CMAP
+ * is guaranteed not to change during iteration.
+ *
+ * CMAP and HASH are evaluated only once.  NODE is evaluated many times.
+ */
+#define CMAP_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, CMAP)       \
+    for (ASSIGN_CONTAINER(NODE, cmap_find(CMAP, HASH), MEMBER); \
+         (NODE) != OBJECT_CONTAINING(NULL, NODE, MEMBER);       \
+         ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.next, MEMBER))
+#define CMAP_FOR_EACH_WITH_HASH_LOCKED(NODE, MEMBER, HASH, CMAP)        \
+    for (ASSIGN_CONTAINER(NODE, cmap_find_locked(CMAP, HASH), MEMBER);  \
+         (NODE) != OBJECT_CONTAINING(NULL, NODE, MEMBER);               \
+         ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.next, MEMBER))
+
+struct cmap_node *cmap_find(const struct cmap *, uint32_t hash);
+struct cmap_node *cmap_find_locked(const struct cmap *, uint32_t hash);
+
+/* Iteration.
+ *
+ * Example:
+ *
+ *     struct my_node {
+ *         struct cmap_node cmap_node;
+ *         int extra_data;
+ *     };
+ *
+ *     struct cmap_cursor cursor;
+ *     struct my_node *iter;
+ *     struct cmap my_map;
+ *
+ *     cmap_init(&cmap);
+ *     ...add data...
+ *     CMAP_FOR_EACH (my_node, cmap_node, &cursor, &cmap) {
+ *         ...operate on my_node...
+ *     }
+ *
+ * There is no CMAP_FOR_EACH_SAFE variant because it would be rarely useful:
+ * usually destruction of an element has to wait for an RCU grace period to
+ * expire. */
+#define CMAP_FOR_EACH(NODE, MEMBER, CURSOR, CMAP)                       \
+    for ((cmap_cursor_init(CURSOR, CMAP),                               \
+          ASSIGN_CONTAINER(NODE, cmap_cursor_next(CURSOR, NULL), MEMBER)); \
+         NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER);                 \
+         ASSIGN_CONTAINER(NODE, cmap_cursor_next(CURSOR, &(NODE)->MEMBER), \
+                          MEMBER))
+
+struct cmap_cursor {
+    const struct cmap_impl *impl;
+    uint32_t bucket_idx;
+    int entry_idx;
+};
+
+void cmap_cursor_init(struct cmap_cursor *, const struct cmap *);
+struct cmap_node *cmap_cursor_next(struct cmap_cursor *,
+                                   const struct cmap_node *);
+
+/* Another, less preferred, form of iteration. */
+struct cmap_position {
+    unsigned int bucket;
+    unsigned int entry;
+    unsigned int offset;
+};
+
+struct cmap_node *cmap_next_position(const struct cmap *,
+                                     struct cmap_position *);
+
+#endif /* cmap.h */
diff --git a/lib/ovs-thread.h b/lib/ovs-thread.h
index 180b66f..68db71f 100644
--- a/lib/ovs-thread.h
+++ b/lib/ovs-thread.h
@@ -40,7 +40,7 @@ struct OVS_LOCKABLE ovs_mutex {
 
 #ifdef PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP
 #define OVS_ADAPTIVE_MUTEX_INITIALIZER                  \
-    { PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP, NULL }
+    { PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP, "<unlocked>" }
 #else
 #define OVS_ADAPTIVE_MUTEX_INITIALIZER OVS_MUTEX_INITIALIZER
 #endif
diff --git a/lib/util.h b/lib/util.h
index 743b9fe..a0670f1 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -278,6 +278,11 @@ char *xasprintf(const char *format, ...) PRINTF_FORMAT(1, 2) MALLOC_LIKE;
 char *xvasprintf(const char *format, va_list) PRINTF_FORMAT(1, 0) MALLOC_LIKE;
 void *x2nrealloc(void *p, size_t *n, size_t s);
 
+/* This system's cache line size, in bytes.
+ * Being wrong hurts performance but not correctness. */
+#define CACHE_LINE_SIZE 64
+BUILD_ASSERT_DECL(IS_POW2(CACHE_LINE_SIZE));
+
 void *xmalloc_cacheline(size_t) MALLOC_LIKE;
 void *xzalloc_cacheline(size_t) MALLOC_LIKE;
 void free_cacheline(void *);
diff --git a/tests/automake.mk b/tests/automake.mk
index bf80702..ac0575e 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -105,6 +105,7 @@ valgrind_wrappers = \
 	tests/valgrind/test-bundle \
 	tests/valgrind/test-byte-order \
 	tests/valgrind/test-classifier \
+	tests/valgrind/test-cmap \
 	tests/valgrind/test-csum \
 	tests/valgrind/test-file_name \
 	tests/valgrind/test-flows \
@@ -213,6 +214,7 @@ tests_ovstest_SOURCES = \
 	tests/test-bundle.c \
 	tests/test-byte-order.c \
 	tests/test-classifier.c \
+	tests/test-cmap.c \
 	tests/test-csum.c \
 	tests/test-file_name.c \
 	tests/test-flows.c \
diff --git a/tests/test-cmap.c b/tests/test-cmap.c
new file mode 100644
index 0000000..e8611ca
--- /dev/null
+++ b/tests/test-cmap.c
@@ -0,0 +1,453 @@
+/*
+ * Copyright (c) 2008, 2009, 2010, 2013, 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.
+ */
+
+/* A non-exhaustive test for some of the functions and macros declared in
+ * cmap.h. */
+
+#include <config.h>
+#include "cmap.h"
+#include <getopt.h>
+#include <string.h>
+#include "command-line.h"
+#include "fat-rwlock.h"
+#include "hash.h"
+#include "hmap.h"
+#include "ovstest.h"
+#include "ovs-thread.h"
+#include "random.h"
+#include "timeval.h"
+#include "util.h"
+
+#undef NDEBUG
+#include <assert.h>
+
+/* Sample cmap element. */
+struct element {
+    int value;
+    struct cmap_node node;
+};
+
+typedef size_t hash_func(int value);
+
+static int
+compare_ints(const void *a_, const void *b_)
+{
+    const int *a = a_;
+    const int *b = b_;
+    return *a < *b ? -1 : *a > *b;
+}
+
+/* Verifies that 'cmap' contains exactly the 'n' values in 'values'. */
+static void
+check_cmap(struct cmap *cmap, const int values[], size_t n,
+           hash_func *hash)
+{
+    int *sort_values, *cmap_values;
+    struct cmap_cursor cursor;
+    struct element *e;
+    size_t i;
+
+    /* Check that all the values are there in iteration. */
+    sort_values = xmalloc(sizeof *sort_values * n);
+    cmap_values = xmalloc(sizeof *sort_values * n);
+
+    i = 0;
+    CMAP_FOR_EACH (e, node, &cursor, cmap) {
+        assert(i < n);
+        cmap_values[i++] = e->value;
+    }
+    assert(i == n);
+
+    memcpy(sort_values, values, sizeof *sort_values * n);
+    qsort(sort_values, n, sizeof *sort_values, compare_ints);
+    qsort(cmap_values, n, sizeof *cmap_values, compare_ints);
+
+    for (i = 0; i < n; i++) {
+        assert(sort_values[i] == cmap_values[i]);
+    }
+
+    free(cmap_values);
+    free(sort_values);
+
+    /* Check that all the values are there in lookup. */
+    for (i = 0; i < n; i++) {
+        size_t count = 0;
+
+        CMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), cmap) {
+            count += e->value == values[i];
+        }
+        assert(count == 1);
+    }
+
+    /* Check counters. */
+    assert(cmap_is_empty(cmap) == !n);
+    assert(cmap_count(cmap) == n);
+}
+
+static void
+shuffle(int *p, size_t n)
+{
+    for (; n > 1; n--, p++) {
+        int *q = &p[random_range(n)];
+        int tmp = *p;
+        *p = *q;
+        *q = tmp;
+    }
+}
+
+/* Prints the values in 'cmap', plus 'name' as a title. */
+static void OVS_UNUSED
+print_cmap(const char *name, struct cmap *cmap)
+{
+    struct cmap_cursor cursor;
+    struct element *e;
+
+    printf("%s:", name);
+    CMAP_FOR_EACH (e, node, &cursor, cmap) {
+        printf(" %d", e->value);
+    }
+    printf("\n");
+}
+
+/* Prints the 'n' values in 'values', plus 'name' as a title. */
+static void OVS_UNUSED
+print_ints(const char *name, const int *values, size_t n)
+{
+    size_t i;
+
+    printf("%s:", name);
+    for (i = 0; i < n; i++) {
+        printf(" %d", values[i]);
+    }
+    printf("\n");
+}
+
+static size_t
+identity_hash(int value)
+{
+    return value;
+}
+
+static size_t
+good_hash(int value)
+{
+    return hash_int(value, 0x1234abcd);
+}
+
+static size_t
+constant_hash(int value OVS_UNUSED)
+{
+    return 123;
+}
+
+/* Tests basic cmap insertion and deletion. */
+static void
+test_cmap_insert_delete(hash_func *hash)
+{
+    enum { N_ELEMS = 1000 };
+
+    struct element elements[N_ELEMS];
+    int values[N_ELEMS];
+    struct cmap cmap;
+    size_t i;
+
+    cmap_init(&cmap);
+    for (i = 0; i < N_ELEMS; i++) {
+        elements[i].value = i;
+        cmap_insert(&cmap, &elements[i].node, hash(i));
+        values[i] = i;
+        check_cmap(&cmap, values, i + 1, hash);
+    }
+    shuffle(values, N_ELEMS);
+    for (i = 0; i < N_ELEMS; i++) {
+        cmap_remove(&cmap, &elements[values[i]].node);
+        check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
+    }
+    cmap_destroy(&cmap);
+}
+
+static void
+run_test(void (*function)(hash_func *))
+{
+    hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
+    size_t i;
+
+    for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
+        function(hash_funcs[i]);
+        printf(".");
+        fflush(stdout);
+    }
+}
+
+static void
+run_tests(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
+{
+    int i;
+
+    for (i = 0; i < 100; i++) {
+        run_test(test_cmap_insert_delete);
+    }
+    printf("\n");
+}
+
+static int n_elems;             /* Number of elements to insert. */
+static int n_threads;           /* Number of threads to search and mutate. */
+static uint32_t mutation_frac;  /* % mutations, as fraction of UINT32_MAX. */
+
+static void benchmark_cmap(void);
+static void benchmark_hmap(void);
+
+static int
+elapsed(const struct timeval *start)
+{
+    struct timeval end;
+
+    xgettimeofday(&end);
+    return timeval_to_msec(&end) - timeval_to_msec(start);
+}
+
+static void
+run_benchmarks(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
+{
+    n_elems = strtol(argv[1], NULL, 10);
+    n_threads = strtol(argv[2], NULL, 10);
+    mutation_frac = strtod(argv[3], NULL) / 100.0 * UINT32_MAX;
+
+    printf("Benchmarking with n=%d, %d threads, %.2f%% mutations:\n",
+           n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.);
+
+    benchmark_cmap();
+    putchar('\n');
+    benchmark_hmap();
+}
+
+/* cmap benchmark. */
+
+static struct element *
+find(const struct cmap *cmap, int value)
+{
+    struct element *e;
+
+    CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
+        if (e->value == value) {
+            return e;
+        }
+    }
+    return NULL;
+}
+
+struct cmap_aux {
+    struct ovs_mutex mutex;
+    struct cmap *cmap;
+};
+
+static void *
+search_cmap(void *aux_)
+{
+    struct cmap_aux *aux = aux_;
+    size_t i;
+
+    for (i = 0; i < n_elems; i++) {
+        struct element *e;
+
+        if (random_uint32() < mutation_frac) {
+            ovs_mutex_lock(&aux->mutex);
+            e = find(aux->cmap, i);
+            if (e) {
+                cmap_remove(aux->cmap, &e->node);
+            }
+            ovs_mutex_unlock(&aux->mutex);
+        } else {
+            ignore(find(aux->cmap, i));
+        }
+    }
+    return NULL;
+}
+
+static void
+benchmark_cmap(void)
+{
+    struct element *elements;
+    struct cmap cmap;
+    struct element *e;
+    struct cmap_cursor cursor;
+    struct timeval start;
+    pthread_t *threads;
+    struct cmap_aux aux;
+    size_t i;
+
+    elements = xmalloc(n_elems * sizeof *elements);
+
+    /* Insertions. */
+    xgettimeofday(&start);
+    cmap_init(&cmap);
+    for (i = 0; i < n_elems; i++) {
+        elements[i].value = i;
+        cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
+    }
+    printf("cmap insert:  %5d ms\n", elapsed(&start));
+
+    /* Iteration. */
+    xgettimeofday(&start);
+    CMAP_FOR_EACH (e, node, &cursor, &cmap) {
+        ignore(e);
+    }
+    printf("cmap iterate: %5d ms\n", elapsed(&start));
+
+    /* Search and mutation. */
+    xgettimeofday(&start);
+    aux.cmap = &cmap;
+    ovs_mutex_init(&aux.mutex);
+    threads = xmalloc(n_threads * sizeof *threads);
+    for (i = 0; i < n_threads; i++) {
+        threads[i] = ovs_thread_create("search", search_cmap, &aux);
+    }
+    for (i = 0; i < n_threads; i++) {
+        xpthread_join(threads[i], NULL);
+    }
+    free(threads);
+    printf("cmap search:  %5d ms\n", elapsed(&start));
+
+    /* Destruction. */
+    xgettimeofday(&start);
+    CMAP_FOR_EACH (e, node, &cursor, &cmap) {
+        cmap_remove(&cmap, &e->node);
+    }
+    cmap_destroy(&cmap);
+    printf("cmap destroy: %5d ms\n", elapsed(&start));
+
+    free(elements);
+}
+
+/* hmap benchmark. */
+struct helement {
+    int value;
+    struct hmap_node node;
+};
+
+static struct helement *
+hfind(const struct hmap *hmap, int value)
+{
+    struct helement *e;
+
+    HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
+        if (e->value == value) {
+            return e;
+        }
+    }
+    return NULL;
+}
+
+struct hmap_aux {
+    struct hmap *hmap;
+    struct fat_rwlock fatlock;
+};
+
+static void *
+search_hmap(void *aux_)
+{
+    struct hmap_aux *aux = aux_;
+    size_t i;
+
+    for (i = 0; i < n_elems; i++) {
+        if (mutation_frac) {
+            if (random_uint32() < mutation_frac) {
+                struct helement *e;
+
+                fat_rwlock_wrlock(&aux->fatlock);
+                e = hfind(aux->hmap, i);
+                if (e) {
+                    hmap_remove(aux->hmap, &e->node);
+                }
+                fat_rwlock_unlock(&aux->fatlock);
+            } else {
+                fat_rwlock_rdlock(&aux->fatlock);
+                ignore(hfind(aux->hmap, i));
+                fat_rwlock_unlock(&aux->fatlock);
+            }
+        } else {
+            hfind(aux->hmap, i);
+        }
+    }
+    return NULL;
+}
+
+static void
+benchmark_hmap(void)
+{
+    struct helement *elements;
+    struct hmap hmap;
+    struct helement *e, *next;
+    struct timeval start;
+    pthread_t *threads;
+    struct hmap_aux aux;
+    size_t i;
+
+    elements = xmalloc(n_elems * sizeof *elements);
+
+    xgettimeofday(&start);
+    hmap_init(&hmap);
+    for (i = 0; i < n_elems; i++) {
+        elements[i].value = i;
+        hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
+    }
+
+    printf("hmap insert:  %5d ms\n", elapsed(&start));
+
+    xgettimeofday(&start);
+    HMAP_FOR_EACH (e, node, &hmap) {
+        ignore(e);
+    }
+    printf("hmap iterate: %5d ms\n", elapsed(&start));
+
+    xgettimeofday(&start);
+    aux.hmap = &hmap;
+    fat_rwlock_init(&aux.fatlock);
+    threads = xmalloc(n_threads * sizeof *threads);
+    for (i = 0; i < n_threads; i++) {
+        threads[i] = ovs_thread_create("search", search_hmap, &aux);
+    }
+    for (i = 0; i < n_threads; i++) {
+        xpthread_join(threads[i], NULL);
+    }
+    free(threads);
+    printf("hmap search:  %5d ms\n", elapsed(&start));
+
+    /* Destruction. */
+    xgettimeofday(&start);
+    HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
+        hmap_remove(&hmap, &e->node);
+    }
+    hmap_destroy(&hmap);
+    printf("hmap destroy: %5d ms\n", elapsed(&start));
+
+    free(elements);
+}
+
+static const struct command commands[] = {
+    {"check", 0, 0, run_tests},
+    {"benchmark", 3, 3, run_benchmarks},
+    {NULL, 0, 0, NULL},
+};
+
+static void
+test_cmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
+{
+    set_program_name(argv[0]);
+    run_command(argc - optind, argv + optind, commands);
+}
+
+OVSTEST_REGISTER("test-cmap", test_cmap_main);
-- 
1.7.10.4




More information about the dev mailing list