#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[];
};
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();
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(read_counter(b) != c);
+ return OVS_UNLIKELY(counter != c);
}
static inline const struct cmap_node *
hash);
}
+/* 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]);
+ }
+ /* 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;
+ }
+ /* 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 result;
+}
+
static int
cmap_find_slot_protected(struct cmap_bucket *b, uint32_t hash)
{
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