#include <config.h>
#include "cmap.h"
+#include "coverage.h"
+#include "bitmap.h"
#include "hash.h"
#include "ovs-rcu.h"
#include "random.h"
#include "util.h"
+COVERAGE_DEFINE(cmap_expand);
+COVERAGE_DEFINE(cmap_shrink);
+
/* Optimistic Concurrent Cuckoo Hash
* =================================
*
* of about 93%. The current implementation is conservative, expanding the
* hash table when it is over 85% full.
*
+ * When the load factor is below 20%, the hash table will be shrinked by half.
+ * This is to reduce the memory utilization of the hash table and to avoid
+ * the hash table occupying the top of heap chunk which prevents the trimming
+ * of heap.
*
* Hash Functions
* ==============
* values waste memory; larger values increase the average insertion time. */
#define CMAP_MAX_LOAD ((uint32_t) (UINT32_MAX * .85))
+/* Default minimum load factor (as a fraction of UINT32_MAX + 1) before
+ * shrinking a cmap. Currently, the value is chosen to be 20%, this
+ * means cmap will have a 40% load factor after shrink. */
+#define CMAP_MIN_LOAD ((uint32_t) (UINT32_MAX * .20))
+
/* 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 min_n; /* Min elements before shrinking. */
uint32_t mask; /* Number of 'buckets', minus one. */
uint32_t basis; /* Basis for rehashing client's hash values. */
/* Padding to make cmap_impl exactly one cache line long. */
- uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 4];
+ uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 5];
struct cmap_bucket buckets[];
};
static struct cmap_impl *cmap_rehash(struct cmap *, uint32_t mask);
+/* Explicit inline keywords in utility functions seem to be necessary
+ * to prevent performance regression on cmap_find(). */
+
/* 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
+static inline 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
+static inline uint32_t
rehash(const struct cmap_impl *impl, uint32_t hash)
{
return hash_finish(impl->basis, hash);
}
-static struct cmap_impl *
+/* Not always without the inline keyword. */
+static inline struct cmap_impl *
cmap_get_impl(const struct cmap *cmap)
{
return ovsrcu_get(struct cmap_impl *, &cmap->impl);
return ((uint64_t) (mask + 1) * CMAP_K * CMAP_MAX_LOAD) >> 32;
}
+static uint32_t
+calc_min_n(uint32_t mask)
+{
+ return ((uint64_t) (mask + 1) * CMAP_K * CMAP_MIN_LOAD) >> 32;
+}
+
static struct cmap_impl *
cmap_impl_create(uint32_t mask)
{
+ (mask + 1) * sizeof *impl->buckets);
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 cmap_count(cmap) == 0;
}
-static uint32_t
-read_counter(struct cmap_bucket *bucket)
+static inline uint32_t
+read_counter(const struct cmap_bucket *bucket_)
{
+ struct cmap_bucket *bucket = CONST_CAST(struct cmap_bucket *, bucket_);
uint32_t counter;
atomic_read_explicit(&bucket->counter, &counter, memory_order_acquire);
+
return counter;
}
-static uint32_t
-read_even_counter(struct cmap_bucket *bucket)
+static inline uint32_t
+read_even_counter(const struct cmap_bucket *bucket)
{
uint32_t counter;
return counter;
}
-static bool
-counter_changed(struct cmap_bucket *b, uint32_t c)
+static inline bool
+counter_changed(const struct cmap_bucket *b_, uint32_t c)
{
+ struct cmap_bucket *b = CONST_CAST(struct cmap_bucket *, b_);
+ uint32_t counter;
+
/* Need to make sure the counter read is not moved up, before the hash and
- * cmap_node_next(). The atomic_read_explicit() with memory_order_acquire
- * in read_counter() still allows prior reads to be moved after the
- * barrier. atomic_thread_fence prevents all following memory accesses
- * from moving prior to preceding loads. */
+ * cmap_node_next(). Using atomic_read_explicit with memory_order_acquire
+ * would allow prior reads to be moved after the barrier.
+ * atomic_thread_fence prevents all following memory accesses from moving
+ * prior to preceding loads. */
atomic_thread_fence(memory_order_acquire);
+ atomic_read_relaxed(&b->counter, &counter);
+
+ return OVS_UNLIKELY(counter != c);
+}
+
+static inline const struct cmap_node *
+cmap_find_in_bucket(const struct cmap_bucket *bucket, uint32_t hash)
+{
+ for (int i = 0; i < CMAP_K; i++) {
+ if (bucket->hashes[i] == hash) {
+ return cmap_node_next(&bucket->nodes[i]);
+ }
+ }
+ return NULL;
+}
+
+static inline const struct cmap_node *
+cmap_find__(const struct cmap_bucket *b1, const struct cmap_bucket *b2,
+ uint32_t hash)
+{
+ uint32_t c1, c2;
+ const struct cmap_node *node;
+
+ do {
+ do {
+ c1 = read_even_counter(b1);
+ node = cmap_find_in_bucket(b1, hash);
+ } while (OVS_UNLIKELY(counter_changed(b1, c1)));
+ if (node) {
+ break;
+ }
+ do {
+ c2 = read_even_counter(b2);
+ node = cmap_find_in_bucket(b2, hash);
+ } while (OVS_UNLIKELY(counter_changed(b2, c2)));
+ if (node) {
+ break;
+ }
+ } while (OVS_UNLIKELY(counter_changed(b1, c1)));
- return OVS_UNLIKELY(read_counter(b) != c);
+ return node;
}
/* Searches 'cmap' for an element with the specified 'hash'. If one or more is
* not changing, then cmap_find_protected() is slightly faster.
*
* CMAP_FOR_EACH_WITH_HASH is usually more convenient. */
-struct cmap_node *
+const struct cmap_node *
cmap_find(const struct cmap *cmap, uint32_t hash)
{
- struct cmap_impl *impl = cmap_get_impl(cmap);
+ const 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;
- struct cmap_node *node;
- b1 = &impl->buckets[h1 & impl->mask];
- b2 = &impl->buckets[h2 & impl->mask];
-retry:
- node = NULL;
- c1 = read_even_counter(b1);
- for (i = 0; i < CMAP_K; i++) {
- if (b1->hashes[i] == hash) {
- node = cmap_node_next(&b1->nodes[i]);
- break;
- }
- }
- if (OVS_UNLIKELY(counter_changed(b1, c1))) {
- goto retry;
- }
- if (node) {
- return node;
- }
+ return cmap_find__(&impl->buckets[h1 & impl->mask],
+ &impl->buckets[h2 & impl->mask],
+ hash);
+}
-retry2:
- node = NULL;
- c2 = read_even_counter(b2);
- for (i = 0; i < CMAP_K; i++) {
- if (b2->hashes[i] == hash) {
- node = cmap_node_next(&b2->nodes[i]);
- break;
- }
- }
- if (OVS_UNLIKELY(counter_changed(b2, c2))) {
- goto retry2;
+/* Looks up multiple 'hashes', when the corresponding bit in 'map' is 1,
+ * and sets the corresponding pointer in 'nodes', if the hash value was
+ * found from the 'cmap'. In other cases the 'nodes' values are not changed,
+ * i.e., no NULL pointers are stored there.
+ * Returns a map where a bit is set to 1 if the corresponding 'nodes' pointer
+ * was stored, 0 otherwise.
+ * Generally, the caller wants to use CMAP_NODE_FOR_EACH to verify for
+ * hash collisions. */
+unsigned long
+cmap_find_batch(const struct cmap *cmap, unsigned long map,
+ uint32_t hashes[], const struct cmap_node *nodes[])
+{
+ const struct cmap_impl *impl = cmap_get_impl(cmap);
+ unsigned long result = map;
+ int i;
+ uint32_t h1s[sizeof map * CHAR_BIT];
+ const struct cmap_bucket *b1s[sizeof map * CHAR_BIT];
+ const struct cmap_bucket *b2s[sizeof map * CHAR_BIT];
+ uint32_t c1s[sizeof map * CHAR_BIT];
+
+ /* Compute hashes and prefetch 1st buckets. */
+ ULLONG_FOR_EACH_1(i, map) {
+ h1s[i] = rehash(impl, hashes[i]);
+ b1s[i] = &impl->buckets[h1s[i] & impl->mask];
+ OVS_PREFETCH(b1s[i]);
}
- if (node) {
- return node;
+ /* Lookups, Round 1. Only look up at the first bucket. */
+ ULLONG_FOR_EACH_1(i, map) {
+ uint32_t c1;
+ const struct cmap_bucket *b1 = b1s[i];
+ const struct cmap_node *node;
+
+ do {
+ c1 = read_even_counter(b1);
+ node = cmap_find_in_bucket(b1, hashes[i]);
+ } while (OVS_UNLIKELY(counter_changed(b1, c1)));
+
+ if (!node) {
+ /* Not found (yet); Prefetch the 2nd bucket. */
+ b2s[i] = &impl->buckets[other_hash(h1s[i]) & impl->mask];
+ OVS_PREFETCH(b2s[i]);
+ c1s[i] = c1; /* We may need to check this after Round 2. */
+ continue;
+ }
+ /* Found. */
+ ULLONG_SET0(map, i); /* Ignore this on round 2. */
+ OVS_PREFETCH(node);
+ nodes[i] = node;
}
-
- /* We just got a stable reading on 'b2', but a node could have been moved
- * to 'b1', so we need to chack the 'c1' again. */
- if (counter_changed(b1, c1)) {
- goto retry;
+ /* Round 2. Look into the 2nd bucket, if needed. */
+ ULLONG_FOR_EACH_1(i, map) {
+ uint32_t c2;
+ const struct cmap_bucket *b2 = b2s[i];
+ const struct cmap_node *node;
+
+ do {
+ c2 = read_even_counter(b2);
+ node = cmap_find_in_bucket(b2, hashes[i]);
+ } while (OVS_UNLIKELY(counter_changed(b2, c2)));
+
+ if (!node) {
+ /* Not found, but the node may have been moved from b2 to b1 right
+ * after we finished with b1 earlier. We just got a clean reading
+ * of the 2nd bucket, so we check the counter of the 1st bucket
+ * only. However, we need to check both buckets again, as the
+ * entry may be moved again to the 2nd bucket. Basically, we
+ * need to loop as long as it takes to get stable readings of
+ * both buckets. cmap_find__() does that, and now that we have
+ * fetched both buckets we can just use it. */
+ if (OVS_UNLIKELY(counter_changed(b1s[i], c1s[i]))) {
+ node = cmap_find__(b1s[i], b2s[i], hashes[i]);
+ if (node) {
+ goto found;
+ }
+ }
+ /* Not found. */
+ ULLONG_SET0(result, i); /* Fix the result. */
+ continue;
+ }
+found:
+ OVS_PREFETCH(node);
+ nodes[i] = node;
}
- return NULL;
+ return result;
}
static int
ovsrcu_set_hidden(&node->next, NULL);
if (OVS_UNLIKELY(impl->n >= impl->max_n)) {
+ COVERAGE_INC(cmap_expand);
impl = cmap_rehash(cmap, (impl->mask << 1) | 1);
}
if (!new_node) {
impl->n--;
+ if (OVS_UNLIKELY(impl->n < impl->min_n)) {
+ COVERAGE_INC(cmap_shrink);
+ impl = cmap_rehash(cmap, impl->mask >> 1);
+ }
}
return impl->n;
}
projects / cascardo / ovs.git / blobdiff