[ovs-dev] [PATCH 4/5] lib/cmap: split up cmap_find().
Jarno Rajahalme
jrajahalme at nicira.com
Wed Sep 24 18:31:46 UTC 2014
This makes the following patch easier and cleans up the code.
Explicit "inline" keywords seem necessary to prevent performance
regression on cmap_find() with GCC 4.7 -O2.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/classifier.c | 2 +-
lib/cmap.c | 116 +++++++++++++++++++++++++++--------------------------
lib/cmap.h | 2 +-
lib/dpif-netdev.c | 2 +-
4 files changed, 63 insertions(+), 59 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index ee737a7..3b28e14 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -1573,7 +1573,7 @@ find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
ofs.start = 0;
/* Try to finish early by checking fields in segments. */
for (i = 0; i < subtable->n_indices; i++) {
- struct cmap_node *inode;
+ const struct cmap_node *inode;
ofs.end = subtable->index_ofs[i];
diff --git a/lib/cmap.c b/lib/cmap.c
index e64d0d0..d3e49fd 100644
--- a/lib/cmap.c
+++ b/lib/cmap.c
@@ -165,10 +165,13 @@ BUILD_ASSERT_DECL(sizeof(struct cmap_impl) == CACHE_LINE_SIZE);
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);
@@ -176,13 +179,14 @@ other_hash(uint32_t hash)
/* 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);
@@ -244,17 +248,19 @@ cmap_is_empty(const struct cmap *cmap)
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;
@@ -265,9 +271,11 @@ read_even_counter(struct cmap_bucket *bucket)
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_);
+
/* 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
* still allow prior reads to be moved after the barrier.
@@ -278,6 +286,44 @@ counter_changed(struct cmap_bucket *b, uint32_t c)
return OVS_UNLIKELY(read_counter(b) != 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 node;
+}
+
/* Searches 'cmap' for an element with the specified 'hash'. If one or more is
* found, returns a pointer to the first one, otherwise a null pointer. All of
* the nodes on the returned list are guaranteed to have exactly the given
@@ -287,58 +333,16 @@ counter_changed(struct cmap_bucket *b, uint32_t c)
* 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;
- }
-
-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;
- }
- if (node) {
- return 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;
- }
- return NULL;
+ return cmap_find__(&impl->buckets[h1 & impl->mask],
+ &impl->buckets[h2 & impl->mask],
+ hash);
}
static int
diff --git a/lib/cmap.h b/lib/cmap.h
index 793202d..9e8cef9 100644
--- a/lib/cmap.h
+++ b/lib/cmap.h
@@ -123,7 +123,7 @@ void cmap_replace(struct cmap *, struct cmap_node *old_node,
ASSIGN_CONTAINER(NODE, cmap_node_next_protected(&(NODE)->MEMBER), \
MEMBER))
-struct cmap_node *cmap_find(const struct cmap *, uint32_t hash);
+const struct cmap_node *cmap_find(const struct cmap *, uint32_t hash);
struct cmap_node *cmap_find_protected(const struct cmap *, uint32_t hash);
/* Iteration.
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 6b8201b..a6f7345 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -2223,7 +2223,7 @@ static struct dp_netdev_pmd_thread *
dp_netdev_get_nonpmd(struct dp_netdev *dp)
{
struct dp_netdev_pmd_thread *pmd;
- struct cmap_node *pnode;
+ const struct cmap_node *pnode;
pnode = cmap_find(&dp->poll_threads, hash_int(NON_PMD_CORE_ID, 0));
ovs_assert(pnode);
--
1.7.10.4
More information about the dev
mailing list