@@ -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 \
new file mode 100644
@@ -0,0 +1,574 @@
+/*
+ * Copyright (c) 2014 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"
+#include "openvswitch/vlog.h"
+
+VLOG_DEFINE_THIS_MODULE(ccmap);
+
+COVERAGE_DEFINE(ccmap_expand);
+COVERAGE_DEFINE(ccmap_shrink);
+
+/* A count-only version of the cmap. */
+
+/* An entry is an 32-bit hash and a 32-bit count. */
+#define CCMAP_ENTRY_SIZE (4 + 4)
+
+/* Number of entries per bucket: 8 */
+#define CCMAP_K (CACHE_LINE_SIZE / CCMAP_ENTRY_SIZE)
+
+/* Pad to make a bucket a full cache line in size: 4 on 32-bit, 0 on 64-bit. */
+#define CCMAP_PADDING ((CACHE_LINE_SIZE - 4) - (CCMAP_K * CCMAP_ENTRY_SIZE))
+
+typedef ATOMIC(uint64_t) ccmap_node_t;
+
+static inline uint64_t ccmap_node(uint32_t count, uint32_t hash)
+{
+ return (uint64_t)count << 32 | hash;
+}
+
+static inline uint32_t ccmap_node_hash(uint64_t node)
+{
+ return node;
+}
+
+static inline uint32_t ccmap_node_count(uint64_t node)
+{
+ return node >> 32;
+}
+
+/* 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; /* 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 ccmap_impl exactly one cache line long. */
+ uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 5];
+
+ 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);
+
+/* Explicit inline keywords in utility functions seem to be necessary
+ * to prevent performance regression on ccmap_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 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 inline uint32_t
+rehash(const struct ccmap_impl *impl, uint32_t hash)
+{
+ return hash_finish(impl->basis, hash);
+}
+
+/* Not always inlined without the inline keyword. */
+static inline 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 = 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 elements in 'ccmap'. */
+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 inline 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;
+
+ atomic_read_relaxed(&bucket->nodes[i], &node);
+ if (ccmap_node_hash(node) == hash) {
+ return ccmap_node_count(node);
+ }
+ }
+ return 0;
+}
+
+/* Searches 'ccmap' for an element 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 inline int
+ccmap_find_slot_protected(struct ccmap_bucket *b, uint32_t hash,
+ uint32_t *count)
+{
+ int i;
+
+ for (i = 0; i < CCMAP_K; i++) {
+ uint64_t node;
+
+ atomic_read_relaxed(&b->nodes[i], &node);
+ *count = ccmap_node_count(node);
+ if (ccmap_node_hash(node) == hash && *count) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+static int
+ccmap_find_empty_slot_protected(const struct ccmap_bucket *b)
+{
+ int i;
+
+ for (i = 0; i < CCMAP_K; i++) {
+ uint64_t node;
+
+ atomic_read_relaxed(&b->nodes[i], &node);
+ if (!ccmap_node_count(node)) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+static inline void
+ccmap_set_bucket(struct ccmap_bucket *b, int i, uint32_t count, uint32_t hash)
+{
+ atomic_store_relaxed(&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)
+{
+ int i;
+ uint32_t count;
+
+ 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;
+
+ 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;
+
+ atomic_read_relaxed(&b->nodes[slot], &node);
+
+ 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;
+
+ atomic_read_relaxed(&buckets[k - 1]->nodes[slots[k - 1]],
+ &node);
+ atomic_store_relaxed(&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 'count'. */
+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];
+
+ return (OVS_LIKELY(ccmap_inc_bucket_existing(b1, hash, inc) ||
+ ccmap_inc_bucket_existing(b2, hash, inc) ||
+ ccmap_inc_bucket_new(b1, hash, inc) ||
+ ccmap_inc_bucket_new(b2, hash, inc)) ||
+ 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 >= 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);
+ }
+ if (count == 1) {
+ ++impl->n;
+ }
+ 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];
+ int slot;
+ uint32_t count;
+
+ 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 count;
+
+ count = ccmap_dec__(impl, hash, h1);
+ if (!count) {
+ count = ccmap_dec__(impl, hash, h2);
+ }
+ ovs_assert(count);
+
+ if (--count == 0) {
+ impl->n--;
+ if (OVS_UNLIKELY(impl->n < impl->min_n)) {
+ COVERAGE_INC(ccmap_shrink);
+ impl = ccmap_rehash(ccmap, impl->mask >> 1);
+ }
+ }
+ return 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++) {
+ int i;
+
+ for (i = 0; i < CCMAP_K; i++) {
+ uint64_t node;
+ uint32_t count;
+
+ atomic_read_relaxed(&b->nodes[i], &node);
+ 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;
+
+ new = ccmap_impl_create(mask);
+ ovs_assert(old->n < 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;
+ ovsrcu_set(&ccmap->impl, new);
+ ovsrcu_postpone(free_cacheline, old);
+
+ return new;
+}
new file mode 100644
@@ -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 */
@@ -17,6 +17,7 @@
#ifndef CLASSIFIER_PRIVATE_H
#define CLASSIFIER_PRIVATE_H 1
+#include "ccmap.h"
#include "cmap.h"
#include "flow.h"
#include "hash.h"
@@ -44,7 +45,7 @@ struct cls_subtable {
unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask'
* (runtime configurable). */
const int ports_mask_len;
- struct cmap indices[CLS_MAX_INDICES]; /* Staged lookup indices. */
+ struct ccmap indices[CLS_MAX_INDICES]; /* Staged lookup indices. */
rcu_trie_ptr ports_trie; /* NULL if none. */
/* These fields are accessed by all readers. */
@@ -67,8 +68,7 @@ struct cls_match {
/* Accessed by readers interested in wildcarding. */
const int priority; /* Larger numbers are higher priorities. */
- struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's
- * 'indices'. */
+
/* Accessed by all readers. */
struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
@@ -490,21 +490,6 @@ static inline ovs_be32 minimatch_get_ports(const struct minimatch *match)
& MINIFLOW_GET_BE32(&match->mask->masks, tp_src);
}
-static void
-subtable_replace_head_rule(struct classifier *cls OVS_UNUSED,
- struct cls_subtable *subtable,
- struct cls_match *head, struct cls_match *new,
- uint32_t hash, uint32_t ihash[CLS_MAX_INDICES])
-{
- /* Rule's data is already in the tries. */
-
- for (int i = 0; i < subtable->n_indices; i++) {
- cmap_replace(&subtable->indices[i], &head->index_nodes[i],
- &new->index_nodes[i], ihash[i]);
- }
- cmap_replace(&subtable->rules, &head->cmap_node, &new->cmap_node, hash);
-}
-
/* Inserts 'rule' into 'cls' in 'version'. Until 'rule' is removed from 'cls',
* the caller must not modify or free it.
*
@@ -579,15 +564,9 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule,
subtable->ports_mask_len);
}
- /* Add new node to segment indices.
- *
- * Readers may find the rule in the indices before the rule is visible
- * in the subtables 'rules' map. This may result in us losing the
- * opportunity to quit lookups earlier, resulting in sub-optimal
- * wildcarding. This will be fixed later by revalidation (always
- * scheduled after flow table changes). */
+ /* Add new node to segment indices. */
for (i = 0; i < subtable->n_indices; i++) {
- cmap_insert(&subtable->indices[i], &new->index_nodes[i], ihash[i]);
+ ccmap_inc(&subtable->indices[i], ihash[i]);
}
n_rules = cmap_insert(&subtable->rules, &new->cmap_node, hash);
} else { /* Equal rules exist in the classifier already. */
@@ -620,8 +599,8 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule,
/* Replace the existing head in data structures, if rule is the new
* head. */
if (iter == head) {
- subtable_replace_head_rule(cls, subtable, head, new, hash,
- ihash);
+ cmap_replace(&subtable->rules, &head->cmap_node,
+ &new->cmap_node, hash);
}
if (old) {
@@ -771,7 +750,8 @@ classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
* replace 'rule' in the data structures. */
next = cls_match_next_protected(rule);
if (next) {
- subtable_replace_head_rule(cls, subtable, rule, next, hash, ihash);
+ cmap_replace(&subtable->rules, &rule->cmap_node, &next->cmap_node,
+ hash);
goto check_priority;
}
@@ -792,7 +772,7 @@ classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
/* Remove rule node from indices. */
for (i = 0; i < subtable->n_indices; i++) {
- cmap_remove(&subtable->indices[i], &rule->index_nodes[i], ihash[i]);
+ ccmap_dec(&subtable->indices[i], ihash[i]);
}
n_rules = cmap_remove(&subtable->rules, &rule->cmap_node, hash);
@@ -1477,7 +1457,7 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
cls->flow_segments[i]);
/* Add an index if it adds mask bits. */
if (!flowmap_is_empty(stage_map)) {
- cmap_init(&subtable->indices[index]);
+ ccmap_init(&subtable->indices[index]);
*CONST_CAST(struct flowmap *, &subtable->index_maps[index])
= stage_map;
index++;
@@ -1493,7 +1473,7 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
/* Remove the last index, as it has the same fields as the rules
* map. */
--index;
- cmap_destroy(&subtable->indices[index]);
+ ccmap_destroy(&subtable->indices[index]);
}
}
*CONST_CAST(uint8_t *, &subtable->n_indices) = index;
@@ -1532,7 +1512,7 @@ destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
ovs_assert(rculist_is_empty(&subtable->rules_list));
for (i = 0; i < subtable->n_indices; i++) {
- cmap_destroy(&subtable->indices[i]);
+ ccmap_destroy(&subtable->indices[i]);
}
cmap_destroy(&subtable->rules);
ovsrcu_postpone(free, subtable);
@@ -1681,7 +1661,7 @@ find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
subtable->index_maps[i],
&mask_offset, &basis);
- if (!cmap_find(&subtable->indices[i], hash)) {
+ if (!ccmap_find(&subtable->indices[i], hash)) {
goto no_match;
}
}
Staged lookup indices assumed that cmap is efficient fealing with duplicates. Duplicates are implemented as linked lists, however, causing removal of rules to become (O^2) and highly cache-inefficient with large number of duplicates. This was problematic especially when many rules shared the same match in packet metadata (e.g., a port number, but nothing else). This patch fixes the problem by introducing a new 'count' 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 classifier implementation a bit more memory efficient, too. Reported-by: Alok Kumar Maurya <alok-kumar.maurya@hpe.com> Signed-off-by: Jarno Rajahalme <jarno@ovn.org> --- lib/automake.mk | 2 + lib/ccmap.c | 574 +++++++++++++++++++++++++++++++++++++++++++++++ lib/ccmap.h | 64 ++++++ lib/classifier-private.h | 6 +- lib/classifier.c | 42 +--- 5 files changed, 654 insertions(+), 34 deletions(-) create mode 100644 lib/ccmap.c create mode 100644 lib/ccmap.h