#include <config.h>
#include "cmap.h"
+#include "bitmap.h"
#include "hash.h"
#include "ovs-rcu.h"
#include "random.h"
* 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. */
- atomic_uint32_t hashes[CMAP_K];
+ uint32_t hashes[CMAP_K];
struct cmap_node nodes[CMAP_K];
/* Padding to make cmap_bucket exactly one cache line long. */
};
BUILD_ASSERT_DECL(sizeof(struct cmap_impl) == CACHE_LINE_SIZE);
-static uint32_t cmap_get_hash__(const atomic_uint32_t *hash,
- memory_order order)
-{
- uint32_t hash__;
-
- atomic_read_explicit(CONST_CAST(ATOMIC(uint32_t) *, hash), &hash__, order);
- return hash__;
-}
-
-#define cmap_get_hash(HASH) \
- cmap_get_hash__(HASH, memory_order_acquire)
-#define cmap_get_hash_protected(HASH) \
- cmap_get_hash__(HASH, memory_order_relaxed)
-
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 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(). 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)
{
- return OVS_UNLIKELY(read_counter(b) != c);
+ 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 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;
-retry:
- b1 = &impl->buckets[h1 & impl->mask];
- c1 = read_even_counter(b1);
- for (i = 0; i < CMAP_K; i++) {
- struct cmap_node *node = cmap_node_next(&b1->nodes[i]);
-
- if (node && cmap_get_hash(&b1->hashes[i]) == hash) {
- if (counter_changed(b1, c1)) {
- goto retry;
- }
- return node;
+ return cmap_find__(&impl->buckets[h1 & impl->mask],
+ &impl->buckets[h2 & impl->mask],
+ 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. */
+ ULONG_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. */
+ ULONG_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. */
+ ULONG_SET0(map, i); /* Ignore this on round 2. */
+ OVS_PREFETCH(node);
+ nodes[i] = node;
}
-
- b2 = &impl->buckets[h2 & impl->mask];
- c2 = read_even_counter(b2);
- for (i = 0; i < CMAP_K; i++) {
- struct cmap_node *node = cmap_node_next(&b2->nodes[i]);
-
- if (node && cmap_get_hash(&b2->hashes[i]) == hash) {
- if (counter_changed(b2, c2)) {
- goto retry;
+ /* Round 2. Look into the 2nd bucket, if needed. */
+ ULONG_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;
+ }
}
- return node;
+ /* Not found. */
+ ULONG_SET0(result, i); /* Fix the result. */
+ continue;
}
+found:
+ OVS_PREFETCH(node);
+ nodes[i] = node;
}
-
- if (counter_changed(b1, c1) || counter_changed(b2, c2)) {
- goto retry;
- }
- return NULL;
+ return result;
}
static int
int i;
for (i = 0; i < CMAP_K; i++) {
- struct cmap_node *node = cmap_node_next_protected(&b->nodes[i]);
-
- if (node && cmap_get_hash_protected(&b->hashes[i]) == hash) {
+ if (b->hashes[i] == hash && cmap_node_next_protected(&b->nodes[i])) {
return i;
}
}
int i;
for (i = 0; i < CMAP_K; i++) {
- struct cmap_node *node = cmap_node_next_protected(&b->nodes[i]);
-
- if (node && cmap_get_hash_protected(&b->hashes[i]) == hash) {
- return node;
+ if (b->hashes[i] == hash) {
+ return cmap_node_next_protected(&b->nodes[i]);
}
}
return NULL;
atomic_read_explicit(&b->counter, &c, memory_order_acquire);
atomic_store_explicit(&b->counter, c + 1, memory_order_release);
ovsrcu_set(&b->nodes[i].next, node); /* Also atomic. */
- atomic_store_explicit(&b->hashes[i], hash, memory_order_release);
+ b->hashes[i] = hash;
atomic_store_explicit(&b->counter, c + 2, memory_order_release);
}
int i;
for (i = 0; i < CMAP_K; i++) {
- struct cmap_node *node = cmap_node_next_protected(&b->nodes[i]);
+ if (b->hashes[i] == hash) {
+ struct cmap_node *node = cmap_node_next_protected(&b->nodes[i]);
- if (cmap_get_hash_protected(&b->hashes[i]) == hash) {
if (node) {
struct cmap_node *p;
static struct cmap_bucket *
other_bucket_protected(struct cmap_impl *impl, struct cmap_bucket *b, int slot)
{
- uint32_t h1 = rehash(impl, cmap_get_hash_protected(&b->hashes[slot]));
+ uint32_t h1 = rehash(impl, b->hashes[slot]);
uint32_t h2 = other_hash(h1);
uint32_t b_idx = b - impl->buckets;
uint32_t other_h = (h1 & impl->mask) == b_idx ? h2 : h1;
for (k = path->n + 1; k > 0; k--) {
int slot = slots[k - 1];
- cmap_set_bucket(buckets[k], slots[k],
- cmap_node_next_protected(&buckets[k - 1]->nodes[slot]),
- cmap_get_hash_protected(&buckets[k - 1]->hashes[slot]));
+ cmap_set_bucket(
+ buckets[k], slots[k],
+ cmap_node_next_protected(&buckets[k - 1]->nodes[slot]),
+ buckets[k - 1]->hashes[slot]);
}
/* Finally, replace the first node on the path by
* unique */
struct cmap_node *node = cmap_node_next_protected(&b->nodes[i]);
- if (node &&
- !cmap_try_insert(new, node,
- cmap_get_hash_protected(&b->hashes[i]))) {
+ if (node && !cmap_try_insert(new, node, b->hashes[i])) {
return false;
}
}