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 | 591 +++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/ccmap.h | 64 ++++++ tests/automake.mk | 2 + tests/library.at | 6 + tests/test-ccmap.c | 292 ++++++++++++++++++++++++++ 6 files changed, 957 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..959e3c8 --- /dev/null +++ b/lib/ccmap.c @@ -0,0 +1,591 @@ +/* + * 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; +} + +/* The lock protecting the critical section has acquire/release semantics. The + * writes in the critical section are guaranteed to happen before the same + * location is are read within the same critical section, or latest before the + * lock is released, and since there is no tight syncronization between the + * reader and the writer, the new values need not be visible to readers before + * the lock is released. */ +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) +{ + /* We align nodes properly for them to be lock free if possible. */ + if (ATOMIC_LLONG_LOCK_FREE) { + node->protected_value = value; + } else { + 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