cmap implements duplicates as linked lists, which causes removal of
rules to become (O^2) with large number of duplicates. This patch
fixes the problem by introducing a new 'counting' 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 user implementation a bit more
memory efficient, too.
Signed-off-by: Jarno Rajahalme <ja...@ovn.org>
---
lib/automake.mk | 2 +
lib/ccmap.c | 581 +++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/ccmap.h | 64 ++++++
tests/automake.mk | 2 +
tests/library.at | 6 +
tests/test-ccmap.c | 292 +++++++++++++++++++++++++++
6 files changed, 947 insertions(+)
create mode 100644 lib/ccmap.c
create mode 100644 lib/ccmap.h
create mode 100644 tests/test-ccmap.c
diff --git a/lib/automake.mk b/lib/automake.mk
index 1ec2115..c54c8f8 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 0000000..08359b5
--- /dev/null
+++ b/lib/ccmap.c
@@ -0,0 +1,581 @@
+/*
+ * Copyright (c) 2014, 2016 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 "ccmap.h"
+#include "coverage.h"
+#include "bitmap.h"
+#include "hash.h"
+#include "ovs-rcu.h"
+#include "random.h"
+#include "util.h"
+
+COVERAGE_DEFINE(ccmap_expand);
+COVERAGE_DEFINE(ccmap_shrink);
+
+/* A count-only version of the cmap. */
+
+/* Allow protected access to the value without atomic semantics. This makes
+ * the exclusive writer somewhat faster. */
+typedef union {
+ unsigned long long protected_value;
+ ATOMIC(unsigned long long) atomic_value;
+} ccmap_node_t;
+BUILD_ASSERT_DECL(sizeof(ccmap_node_t) == sizeof(uint64_t));
+
+static uint64_t
+ccmap_node_get(const ccmap_node_t *node)
+{
+ uint64_t value;
+
+ atomic_read_relaxed(&CONST_CAST(ccmap_node_t *, node)->atomic_value,
+ &value);
+
+ return value;
+}
+
+/* It is safe to allow compiler optimize reads by the exclusive writer. */
+static uint64_t
+ccmap_node_get_protected(const ccmap_node_t *node)
+{
+ return node->protected_value;
+}
+
+static void
+ccmap_node_set_protected(ccmap_node_t *node, uint64_t value)
+{
+ atomic_store_relaxed(&node->atomic_value, value);
+}
+
+static uint64_t
+ccmap_node(uint32_t count, uint32_t hash)
+{
+ return (uint64_t)count << 32 | hash;
+}
+
+static uint32_t
+ccmap_node_hash(uint64_t node)
+{
+ return node;
+}
+
+static uint32_t
+ccmap_node_count(uint64_t node)
+{
+ return node >> 32;
+}
+
+/* Number of nodes per bucket. */
+#define CCMAP_K (CACHE_LINE_SIZE / sizeof(ccmap_node_t))
+
+/* 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_unique; /* Number of in-use nodes. */
+ unsigned int n; /* Number of hashes inserted. */
+ unsigned int max_n; /* Max nodes before enlarging. */
+ unsigned int min_n; /* Min nodes 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) * 6];
+
+ 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);
+
+/* 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 cmap.c.) */
+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 ccmap_impl *impl, uint32_t hash)
+{
+ return hash_finish(impl->basis, hash);
+}
+
+static struct ccmap_impl *
+ccmap_get_impl(const struct ccmap *ccmap)
+{
+ return ovsrcu_get(struct ccmap_impl *, &ccmap->impl);
+}
+
+static uint32_t
+calc_max_n(uint32_t mask)
+{
+ return ((uint64_t) (mask + 1) * CCMAP_K * CCMAP_MAX_LOAD) >> 32;
+}
+
+static uint32_t
+calc_min_n(uint32_t mask)
+{
+ return ((uint64_t) (mask + 1) * CCMAP_K * CCMAP_MIN_LOAD) >> 32;
+}
+
+static struct ccmap_impl *
+ccmap_impl_create(uint32_t mask)
+{
+ struct ccmap_impl *impl;
+
+ ovs_assert(is_pow2(mask + 1));
+
+ impl = xzalloc_cacheline(sizeof *impl
+ + (mask + 1) * sizeof *impl->buckets);
+ impl->n_unique = 0;
+ impl->n = 0;
+ impl->max_n = calc_max_n(mask);
+ impl->min_n = calc_min_n(mask);
+ impl->mask = mask;
+ impl->basis = random_uint32();
+
+ return impl;
+}
+
+/* Initializes 'ccmap' as an empty concurrent hash map. */
+void
+ccmap_init(struct ccmap *ccmap)
+{
+ ovsrcu_set(&ccmap->impl, ccmap_impl_create(0));
+}
+
+/* Destroys 'ccmap'.
+ *
+ * The client is responsible for destroying any data previously held in
+ * 'ccmap'. */
+void
+ccmap_destroy(struct ccmap *ccmap)
+{
+ if (ccmap) {
+ ovsrcu_postpone(free_cacheline, ccmap_get_impl(ccmap));
+ }
+}
+
+/* Returns the number of hashes inserted in 'ccmap', including duplicates. */
+size_t
+ccmap_count(const struct ccmap *ccmap)
+{
+ return ccmap_get_impl(ccmap)->n;
+}
+
+/* Returns true if 'ccmap' is empty, false otherwise. */
+bool
+ccmap_is_empty(const struct ccmap *ccmap)
+{
+ return ccmap_count(ccmap) == 0;
+}
+
+/* returns 0 if not found. Map does not contain zero counts. */
+static uint32_t
+ccmap_find_in_bucket(const struct ccmap_bucket *bucket, uint32_t hash)
+{
+ for (int i = 0; i < CCMAP_K; i++) {
+ uint64_t node = ccmap_node_get(&bucket->nodes[i]);
+
+ if (ccmap_node_hash(node) == hash) {
+ return ccmap_node_count(node);
+ }
+ }
+ return 0;
+}
+
+/* Searches 'ccmap' for a node with the specified 'hash'. If one is
+ * found, returns the count associated with it, otherwise zero.
+ */
+uint32_t
+ccmap_find(const struct ccmap *ccmap, uint32_t hash)
+{
+ const struct ccmap_impl *impl = ccmap_get_impl(ccmap);
+ uint32_t h = rehash(impl, hash);
+ uint32_t count;
+
+ count = ccmap_find_in_bucket(&impl->buckets[h & impl->mask], hash);
+ if (!count) {
+ h = other_hash(h);
+ count = ccmap_find_in_bucket(&impl->buckets[h & impl->mask], hash);
+ }
+ return count;
+}
+
+static int
+ccmap_find_slot_protected(struct ccmap_bucket *b, uint32_t hash,
+ uint32_t *count)
+{
+ for (int i = 0; i < CCMAP_K; i++) {
+ uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
+
+ *count = ccmap_node_count(node);
+ if (ccmap_node_hash(node) == hash && *count) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+static int
+ccmap_find_empty_slot_protected(struct ccmap_bucket *b)
+{
+ for (int i = 0; i < CCMAP_K; i++) {
+ uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
+
+ if (!ccmap_node_count(node)) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+static void
+ccmap_set_bucket(struct ccmap_bucket *b, int i, uint32_t count, uint32_t hash)
+{
+ ccmap_node_set_protected(&b->nodes[i], ccmap_node(count, hash));
+}
+
+/* Searches 'b' for a node with the given 'hash'. If it finds one, increments
+ * the associated count by 'inc' and returns the new value. Otherwise returns
+ * 0. */
+static uint32_t
+ccmap_inc_bucket_existing(struct ccmap_bucket *b, uint32_t hash, uint32_t inc)
+{
+ uint32_t count;
+
+ int i = ccmap_find_slot_protected(b, hash, &count);
+ if (i < 0) {
+ return 0;
+ }
+ count += inc;
+ ccmap_set_bucket(b, i, count, hash);
+ return count;
+}
+
+/* Searches 'b' for an empty slot. If successful, stores 'inc' and 'hash' in
+ * the slot and returns 'inc'. Otherwise, returns 0. */
+static uint32_t
+ccmap_inc_bucket_new(struct ccmap_bucket *b, uint32_t hash, uint32_t inc)
+{
+ int i = ccmap_find_empty_slot_protected(b);
+ if (i < 0) {
+ return 0;
+ }
+ ccmap_set_bucket(b, i, inc, hash);
+ return inc;
+}
+
+/* Returns the other bucket that b->nodes[slot] could occupy in 'impl'. (This
+ * might be the same as 'b'.) */
+static struct ccmap_bucket *
+other_bucket_protected(struct ccmap_impl *impl, struct ccmap_bucket *b, int
slot)
+{
+ uint64_t node = ccmap_node_get_protected(&b->nodes[slot]);
+
+ uint32_t h1 = rehash(impl, ccmap_node_hash(node));
+ uint32_t h2 = other_hash(h1);
+ uint32_t b_idx = b - impl->buckets;
+ uint32_t other_h = (h1 & impl->mask) == b_idx ? h2 : h1;
+
+ return &impl->buckets[other_h & impl->mask];
+}
+
+/* Count 'inc' for 'hash' is to be inserted into 'impl', but both candidate
+ * buckets 'b1' and 'b2' are full. This function attempts to rearrange buckets
+ * within 'impl' to make room for 'hash'.
+ *
+ * Returns 'inc' if the new count for the 'hash' was inserted, otherwise
+ * returns 0.
+ *
+ * The implementation is a general-purpose breadth-first search. At first
+ * glance, this is more complex than a random walk through 'impl' (suggested by
+ * some references), but random walks have a tendency to loop back through a
+ * single bucket. We have to move nodes backward along the path that we find,
+ * so that no node actually disappears from the hash table, which means a
+ * random walk would have to be careful to deal with loops. By contrast, a
+ * successful breadth-first search always finds a *shortest* path through the
+ * hash table, and a shortest path will never contain loops, so it avoids that
+ * problem entirely.
+ */
+static uint32_t
+ccmap_inc_bfs(struct ccmap_impl *impl, uint32_t hash,
+ struct ccmap_bucket *b1, struct ccmap_bucket *b2, uint32_t inc)
+{
+ enum { MAX_DEPTH = 4 };
+
+ /* A path from 'start' to 'end' via the 'n' steps in 'slots[]'.
+ *
+ * One can follow the path via:
+ *
+ * struct ccmap_bucket *b;
+ * int i;
+ *
+ * b = path->start;
+ * for (i = 0; i < path->n; i++) {
+ * b = other_bucket_protected(impl, b, path->slots[i]);
+ * }
+ * ovs_assert(b == path->end);
+ */
+ struct ccmap_path {
+ struct ccmap_bucket *start; /* First bucket along the path. */
+ struct ccmap_bucket *end; /* Last bucket on the path. */
+ uint8_t slots[MAX_DEPTH]; /* Slots used for each hop. */
+ int n; /* Number of slots[]. */
+ };
+
+ /* We need to limit the amount of work we do trying to find a path. It
+ * might actually be impossible to rearrange the ccmap, and after some time
+ * it is likely to be easier to rehash the entire ccmap.
+ *
+ * This value of MAX_QUEUE is an arbitrary limit suggested by one of the
+ * references. Empirically, it seems to work OK. */
+ enum { MAX_QUEUE = 500 };
+ struct ccmap_path queue[MAX_QUEUE];
+ int head = 0;
+ int tail = 0;
+
+ /* Add 'b1' and 'b2' as starting points for the search. */
+ queue[head].start = b1;
+ queue[head].end = b1;
+ queue[head].n = 0;
+ head++;
+ if (b1 != b2) {
+ queue[head].start = b2;
+ queue[head].end = b2;
+ queue[head].n = 0;
+ head++;
+ }
+
+ while (tail < head) {
+ const struct ccmap_path *path = &queue[tail++];
+ struct ccmap_bucket *this = path->end;
+ int i;
+
+ for (i = 0; i < CCMAP_K; i++) {
+ struct ccmap_bucket *next = other_bucket_protected(impl, this, i);
+ int j;
+
+ if (this == next) {
+ continue;
+ }
+
+ j = ccmap_find_empty_slot_protected(next);
+ if (j >= 0) {
+ /* We've found a path along which we can rearrange the hash
+ * table: Start at path->start, follow all the slots in
+ * path->slots[], then follow slot 'i', then the bucket you
+ * arrive at has slot 'j' empty. */
+ struct ccmap_bucket *buckets[MAX_DEPTH + 2];
+ int slots[MAX_DEPTH + 2];
+ int k;
+
+ /* Figure out the full sequence of slots. */
+ for (k = 0; k < path->n; k++) {
+ slots[k] = path->slots[k];
+ }
+ slots[path->n] = i;
+ slots[path->n + 1] = j;
+
+ /* Figure out the full sequence of buckets. */
+ buckets[0] = path->start;
+ for (k = 0; k <= path->n; k++) {
+ buckets[k + 1] = other_bucket_protected(impl, buckets[k],
slots[k]);
+ }
+
+ /* Now the path is fully expressed. One can start from
+ * buckets[0], go via slots[0] to buckets[1], via slots[1] to
+ * buckets[2], and so on.
+ *
+ * Move all the nodes across the path "backward". After each
+ * step some node appears in two buckets. Thus, every node is
+ * always visible to a concurrent search. */
+ for (k = path->n + 1; k > 0; k--) {
+ uint64_t node = ccmap_node_get_protected
+ (&buckets[k - 1]->nodes[slots[k - 1]]);
+ ccmap_node_set_protected(&buckets[k]->nodes[slots[k]],
+ node);
+ }
+
+ /* Finally, insert the count. */
+ ccmap_set_bucket(buckets[0], slots[0], inc, hash);
+
+ return inc;
+ }
+
+ if (path->n < MAX_DEPTH && head < MAX_QUEUE) {
+ struct ccmap_path *new_path = &queue[head++];
+
+ *new_path = *path;
+ new_path->end = next;
+ new_path->slots[new_path->n++] = i;
+ }
+ }
+ }
+
+ return 0;
+}
+
+/* Increments the count associated with 'hash', in 'impl', by 'inc'. */
+static uint32_t
+ccmap_try_inc(struct ccmap_impl *impl, uint32_t hash, uint32_t inc)
+{
+ uint32_t h1 = rehash(impl, hash);
+ uint32_t h2 = other_hash(h1);
+ struct ccmap_bucket *b1 = &impl->buckets[h1 & impl->mask];
+ struct ccmap_bucket *b2 = &impl->buckets[h2 & impl->mask];
+ uint32_t count;
+
+ return OVS_UNLIKELY(count = ccmap_inc_bucket_existing(b1, hash, inc))
+ ? count : OVS_UNLIKELY(count = ccmap_inc_bucket_existing(b2, hash,
inc))
+ ? count : OVS_LIKELY(count = ccmap_inc_bucket_new(b1, hash, inc))
+ ? count : OVS_LIKELY(count = ccmap_inc_bucket_new(b2, hash, inc))
+ ? count : ccmap_inc_bfs(impl, hash, b1, b2, inc);
+}
+
+/* Increments the count of 'hash' values in the 'ccmap'. The caller must
+ * ensure that 'ccmap' cannot change concurrently (from another thread).
+ *
+ * Returns the current count of the given hash value after the incremention. */
+uint32_t
+ccmap_inc(struct ccmap *ccmap, uint32_t hash)
+{
+ struct ccmap_impl *impl = ccmap_get_impl(ccmap);
+ uint32_t count;
+
+ if (OVS_UNLIKELY(impl->n_unique >= impl->max_n)) {
+ COVERAGE_INC(ccmap_expand);
+ impl = ccmap_rehash(ccmap, (impl->mask << 1) | 1);
+ }
+
+ while (OVS_UNLIKELY(!(count = ccmap_try_inc(impl, hash, 1)))) {
+ impl = ccmap_rehash(ccmap, impl->mask);
+ }
+ ++impl->n;
+ if (count == 1) {
+ ++impl->n_unique;
+ }
+ return count;
+}
+
+/* Decrement the count associated with 'hash' in the bucket identified by
+ * 'h'. Return the OLD count if successful, or 0. */
+static uint32_t
+ccmap_dec__(struct ccmap_impl *impl, uint32_t hash, uint32_t h)
+{
+ struct ccmap_bucket *b = &impl->buckets[h & impl->mask];
+ uint32_t count;
+
+ int slot = ccmap_find_slot_protected(b, hash, &count);
+ if (slot < 0) {
+ return 0;
+ }
+
+ ccmap_set_bucket(b, slot, count - 1, hash);
+ return count;
+}
+
+/* Decrements the count associated with 'hash'. The caller must
+ * ensure that 'ccmap' cannot change concurrently (from another thread).
+ *
+ * Returns the current count related to 'hash' in the ccmap after the
+ * decrement. */
+uint32_t
+ccmap_dec(struct ccmap *ccmap, uint32_t hash)
+{
+ struct ccmap_impl *impl = ccmap_get_impl(ccmap);
+ uint32_t h1 = rehash(impl, hash);
+ uint32_t h2 = other_hash(h1);
+
+ uint32_t old_count = ccmap_dec__(impl, hash, h1);
+ if (!old_count) {
+ old_count = ccmap_dec__(impl, hash, h2);
+ }
+ ovs_assert(old_count);
+
+ old_count--;
+
+ if (old_count == 0) {
+ impl->n_unique--;
+ if (OVS_UNLIKELY(impl->n_unique < impl->min_n)) {
+ COVERAGE_INC(ccmap_shrink);
+ impl = ccmap_rehash(ccmap, impl->mask >> 1);
+ }
+ }
+ impl->n--;
+ return old_count;
+}
+
+static bool
+ccmap_try_rehash(const struct ccmap_impl *old, struct ccmap_impl *new)
+{
+ const struct ccmap_bucket *b;
+
+ for (b = old->buckets; b <= &old->buckets[old->mask]; b++) {
+ for (int i = 0; i < CCMAP_K; i++) {
+ uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
+ uint32_t count = ccmap_node_count(node);
+
+ if (count && !ccmap_try_inc(new, ccmap_node_hash(node), count)) {
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+static struct ccmap_impl *
+ccmap_rehash(struct ccmap *ccmap, uint32_t mask)
+{
+ struct ccmap_impl *old = ccmap_get_impl(ccmap);
+ struct ccmap_impl *new = ccmap_impl_create(mask);
+
+ ovs_assert(old->n_unique < new->max_n);
+
+ while (!ccmap_try_rehash(old, new)) {
+ memset(new->buckets, 0, (mask + 1) * sizeof *new->buckets);
+ new->basis = random_uint32();
+ }
+
+ new->n = old->n;
+ new->n_unique = old->n_unique;
+ ovsrcu_set(&ccmap->impl, new);
+ ovsrcu_postpone(free_cacheline, old);
+
+ return new;
+}
diff --git a/lib/ccmap.h b/lib/ccmap.h
new file mode 100644
index 0000000..9c39448
--- /dev/null
+++ b/lib/ccmap.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright (c) 2014, 2016 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 CCMAP_H
+#define CCMAP_H 1
+
+#include <stdbool.h>
+#include <stdint.h>
+#include "ovs-rcu.h"
+#include "util.h"
+
+/* Concurrent hash map for numerical counts of given hash values.
+ * ==============================================================
+ *
+ * A single-writer, multiple-reader count hash table that efficiently supports
+ * duplicates.
+ *
+ *
+ * Thread-safety
+ * =============
+ *
+ * The general rules are:
+ *
+ * - Only a single thread may safely call into ccmap_inc(),
+ * or ccmap_dec() at any given time.
+ *
+ * - Any number of threads may use functions and macros that search
+ * a given ccmap, even in parallel with other threads
+ * calling ccmap_inc() or ccmap_dec().
+ */
+
+/* Concurrent hash map. */
+struct ccmap {
+ OVSRCU_TYPE(struct ccmap_impl *) impl;
+};
+
+/* Initialization. */
+void ccmap_init(struct ccmap *);
+void ccmap_destroy(struct ccmap *);
+
+/* Count. */
+size_t ccmap_count(const struct ccmap *);
+bool ccmap_is_empty(const struct ccmap *);
+
+/* Insertion and deletion. Return the current count after the operation. */
+uint32_t ccmap_inc(struct ccmap *, uint32_t hash);
+uint32_t ccmap_dec(struct ccmap *, uint32_t hash);
+
+uint32_t ccmap_find(const struct ccmap *, uint32_t hash);
+
+#endif /* ccmap.h */
diff --git a/tests/automake.mk b/tests/automake.mk
index aed032b..0892872 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -166,6 +166,7 @@ valgrind_wrappers = \
tests/valgrind/test-bundle \
tests/valgrind/test-byte-order \
tests/valgrind/test-classifier \
+ tests/valgrind/test-ccmap \
tests/valgrind/test-cmap \
tests/valgrind/test-csum \
tests/valgrind/test-flows \
@@ -309,6 +310,7 @@ tests_ovstest_SOURCES = \
tests/test-bundle.c \
tests/test-byte-order.c \
tests/test-classifier.c \
+ tests/test-ccmap.c \
tests/test-cmap.c \
tests/test-csum.c \
tests/test-flows.c \
diff --git a/tests/library.at b/tests/library.at
index e1bac92..22c8627 100644
--- a/tests/library.at
+++ b/tests/library.at
@@ -33,6 +33,12 @@ AT_CHECK([ovstest test-cmap check 1], [0], [...
])
AT_CLEANUP
+AT_SETUP([test counting cockoo hash])
+AT_KEYWORDS([cmap])
+AT_CHECK([ovstest test-ccmap check 1], [0], [...
+])
+AT_CLEANUP
+
AT_SETUP([test atomic operations])
AT_CHECK([ovstest test-atomic])
AT_CLEANUP
diff --git a/tests/test-ccmap.c b/tests/test-ccmap.c
new file mode 100644
index 0000000..2f2cdd6
--- /dev/null
+++ b/tests/test-ccmap.c
@@ -0,0 +1,292 @@
+/*
+ * Copyright (c) 2008, 2009, 2010, 2013, 2014, 2016 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
+ * ccmap.h. */
+
+#include <config.h>
+#undef NDEBUG
+#include "ccmap.h"
+#include <assert.h>
+#include <getopt.h>
+#include <string.h>
+#include "bitmap.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"
+
+typedef size_t hash_func(int value);
+
+static int
+compare_uint32s(const void *a_, const void *b_)
+{
+ const uint32_t *a = a_;
+ const uint32_t *b = b_;
+ return *a < *b ? -1 : *a > *b;
+}
+
+/* Verifies that 'ccmap' contains exactly the 'n' values in 'values'. */
+static void
+check_ccmap(struct ccmap *ccmap, const int values[], size_t n, hash_func *hash)
+{
+ uint32_t *hashes = xmalloc(sizeof *hashes * n);
+ int i;
+
+ for (i = 0; i < n; i++) {
+ hashes[i] = hash(values[i]);
+ }
+ qsort(hashes, n, sizeof *hashes, compare_uint32s);
+
+ /* Check that all the values are there in lookup. */
+ for (i = 0; i < n; i++) {
+ uint32_t hash = hashes[i];
+ size_t count = ccmap_find(ccmap, hash);
+
+ assert(count); /* Must have at least one. */
+ assert(i + count <= n); /* May not have too many. */
+
+ /* Skip colliding hash values and assert they were in the count. */
+ while (--count) {
+ i++;
+ assert(hashes[i] == hash);
+ }
+ /* Make sure next hash is different. */
+ if (i + 1 < n) {
+ assert(hashes[i + 1] != hash);
+ }
+ }
+
+ /* Check counters. */
+ assert(ccmap_is_empty(ccmap) == !n);
+ assert(ccmap_count(ccmap) == n);
+
+ free(hashes);
+}
+
+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;
+ }
+}
+
+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 ccmap increment and decrement. */
+static void
+test_ccmap_inc_dec(hash_func *hash)
+{
+ enum { N_ELEMS = 1000 };
+
+ int values[N_ELEMS];
+ struct ccmap ccmap;
+ size_t i;
+
+ ccmap_init(&ccmap);
+ for (i = 0; i < N_ELEMS; i++) {
+ ccmap_inc(&ccmap, hash(i));
+ values[i] = i;
+ check_ccmap(&ccmap, values, i + 1, hash);
+ }
+ shuffle(values, N_ELEMS);
+ for (i = 0; i < N_ELEMS; i++) {
+ ccmap_dec(&ccmap, hash(values[i]));
+ check_ccmap(&ccmap, values + (i + 1), N_ELEMS - (i + 1), hash);
+ }
+ ccmap_destroy(&ccmap);
+}
+
+static void
+run_test(void (*function)(hash_func *))
+{
+ hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
+
+ for (size_t i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
+ function(hash_funcs[i]);
+ printf(".");
+ fflush(stdout);
+ }
+}
+
+static void
+run_tests(struct ovs_cmdl_context *ctx)
+{
+ int n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
+ for (int i = 0; i < n; i++) {
+ run_test(test_ccmap_inc_dec);
+ }
+ 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_ccmap(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(struct ovs_cmdl_context *ctx)
+{
+ n_elems = strtol(ctx->argv[1], NULL, 10);
+ n_threads = strtol(ctx->argv[2], NULL, 10);
+ mutation_frac = strtod(ctx->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_ccmap();
+}
+
+/* ccmap benchmark. */
+
+struct ccmap_aux {
+ struct ovs_mutex mutex;
+ struct ccmap *ccmap;
+};
+
+static void *
+search_ccmap(void *aux_)
+{
+ struct ccmap_aux *aux = aux_;
+ size_t i;
+
+ if (mutation_frac) {
+ for (i = 0; i < n_elems; i++) {
+ uint32_t hash = hash_int(i, 0);
+
+ if (random_uint32() < mutation_frac) {
+ ovs_mutex_lock(&aux->mutex);
+ uint32_t count = ccmap_find(aux->ccmap, hash);
+ if (count) {
+ ccmap_dec(aux->ccmap, hash);
+ }
+ ovs_mutex_unlock(&aux->mutex);
+ } else {
+ ignore(ccmap_find(aux->ccmap, hash));
+ }
+ }
+ } else {
+ for (i = 0; i < n_elems; i++) {
+ ignore(ccmap_find(aux->ccmap, hash_int(i, 0)));
+ }
+ }
+ return NULL;
+}
+
+static void
+benchmark_ccmap(void)
+{
+ struct ccmap ccmap;
+ struct timeval start;
+ pthread_t *threads;
+ struct ccmap_aux aux;
+ size_t i;
+
+ /* Insertions. */
+ xgettimeofday(&start);
+ ccmap_init(&ccmap);
+ for (i = 0; i < n_elems; i++) {
+ ccmap_inc(&ccmap, hash_int(i, 0));
+ }
+ printf("ccmap insert: %5d ms\n", elapsed(&start));
+
+ /* Search and mutation. */
+ xgettimeofday(&start);
+ aux.ccmap = &ccmap;
+ 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_ccmap, &aux);
+ }
+ for (i = 0; i < n_threads; i++) {
+ xpthread_join(threads[i], NULL);
+ }
+ free(threads);
+ printf("ccmap search: %5d ms\n", elapsed(&start));
+
+ /* Destruction. */
+ xgettimeofday(&start);
+ for (i = 0; i < n_elems; i++) {
+ uint32_t hash = hash_int(i, 0);
+
+ if (ccmap_find(&ccmap, hash)) {
+ /* Also remove any colliding hashes. */
+ while (ccmap_dec(&ccmap, hash)) {
+ ;
+ }
+ }
+ }
+ ccmap_destroy(&ccmap);
+ printf("ccmap destroy: %5d ms\n", elapsed(&start));
+}
+
+
+static const struct ovs_cmdl_command commands[] = {
+ {"check", NULL, 0, 1, run_tests},
+ {"benchmark", NULL, 3, 3, run_benchmarks},
+ {NULL, NULL, 0, 0, NULL},
+};
+
+static void
+test_ccmap_main(int argc, char *argv[])
+{
+ struct ovs_cmdl_context ctx = {
+ .argc = argc - optind,
+ .argv = argv + optind,
+ };
+
+ set_program_name(argv[0]);
+ ovs_cmdl_run_command(&ctx, commands);
+}
+
+OVSTEST_REGISTER("test-ccmap", test_ccmap_main);
--
2.1.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
