From: Jarno Rajahalme <jrajaha...@nicira.com>
Do not cache the 'tag' and 'max_priority' in the subtable array. This
makes later changes to classifier easier.
Change CLS_SUBTABLES_FOR_EACH to iterate with a regular array index.
Makes the 'cls_subtables*' functions to always leave the subtables
array in a consistent state. This includes the new
cls_subtables_insert() function and removal of the old
cls_subtables_push_back() function.
Finally, using qsort() instead of our hand rolled sort routines. This
simplifies the code significantly.
Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
Co-authored-by: Ethan Jackson <et...@nicira.com>
Signed-off-by: Ethan Jackson <et...@nicira.com>
---
Jarno wrote the bulk of this patch, but I folded in the switch to use the
qsort() function. I was planning to write that on top of this, but it turned
out to be much easier to fold it in. Someone other than either of us should
probably review it.
---
lib/classifier.c | 396 +++++++++++--------------------------------------------
1 file changed, 80 insertions(+), 316 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 00d47ac..1bcfba2 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -43,16 +43,10 @@ struct cls_trie {
struct trie_node *root; /* NULL if none. */
};
-struct cls_subtable_entry {
- struct cls_subtable *subtable;
- tag_type tag;
- unsigned int max_priority;
-};
-
struct cls_subtables {
- size_t count; /* One past last valid array element. */
+ int count; /* One past last valid array element. */
size_t alloc_size; /* Number of allocated elements. */
- struct cls_subtable_entry *array;
+ struct cls_subtable **array;
};
enum {
@@ -137,13 +131,7 @@ static struct cls_subtable *insert_subtable(struct
cls_classifier *,
const struct minimask *);
static void destroy_subtable(struct cls_classifier *, struct cls_subtable *);
-
-static void update_subtables_after_insertion(struct cls_classifier *,
- struct cls_subtable *,
- unsigned int new_priority);
-static void update_subtables_after_removal(struct cls_classifier *,
- struct cls_subtable *,
- unsigned int del_priority);
+static inline void sort_subtables(struct cls_subtables *);
static struct cls_match *find_match_wc(const struct cls_subtable *,
const struct flow *, struct trie_ctx *,
@@ -199,186 +187,37 @@ cls_subtables_destroy(struct cls_subtables *subtables)
memset(subtables, 0, sizeof *subtables);
}
-/* Subtables insertion. */
+/* Subtable insertion. 'a->max_priority' must be updated after insertion,
+ * Unless 'max_priority' remains at 0. */
static void
-cls_subtables_push_back(struct cls_subtables *subtables,
- struct cls_subtable_entry a)
-{
- if (subtables->count == subtables->alloc_size) {
- subtables->array = x2nrealloc(subtables->array, &subtables->alloc_size,
- sizeof a);
- }
-
- subtables->array[subtables->count++] = a;
-}
-
-/* Move subtable entry at 'from' to 'to', shifting the elements in between
- * (including the one at 'to') accordingly. */
-static inline void
-cls_subtables_move(struct cls_subtable_entry *to,
- struct cls_subtable_entry *from)
+cls_subtables_insert(struct cls_classifier *cls, struct cls_subtable *a)
{
- if (to != from) {
- struct cls_subtable_entry temp = *from;
-
- if (to > from) {
- /* Shift entries (from,to] backwards to make space at 'to'. */
- memmove(from, from + 1, (to - from) * sizeof *to);
- } else {
- /* Shift entries [to,from) forward to make space at 'to'. */
- memmove(to + 1, to, (from - to) * sizeof *to);
- }
- *to = temp;
+ if (cls->subtables.count == cls->subtables.alloc_size) {
+ cls->subtables.array = x2nrealloc(cls->subtables.array,
+ &cls->subtables.alloc_size,
+ sizeof a);
}
-}
-
-/* Subtables removal. */
-static inline void
-cls_subtables_remove(struct cls_subtables *subtables,
- struct cls_subtable_entry *elem)
-{
- ssize_t size = (&subtables->array[subtables->count]
- - (elem + 1)) * sizeof *elem;
- if (size > 0) {
- memmove(elem, elem + 1, size);
- }
- subtables->count--;
-}
-
-#define CLS_SUBTABLES_FOR_EACH(SUBTABLE, ITER, SUBTABLES) \
- for ((ITER) = (SUBTABLES)->array; \
- (ITER) < &(SUBTABLES)->array[(SUBTABLES)->count] \
- && OVS_LIKELY((SUBTABLE) = (ITER)->subtable); \
- ++(ITER))
-#define CLS_SUBTABLES_FOR_EACH_CONTINUE(SUBTABLE, ITER, SUBTABLES) \
- for (++(ITER); \
- (ITER) < &(SUBTABLES)->array[(SUBTABLES)->count] \
- && OVS_LIKELY((SUBTABLE) = (ITER)->subtable); \
- ++(ITER))
-#define CLS_SUBTABLES_FOR_EACH_REVERSE(SUBTABLE, ITER, SUBTABLES) \
- for ((ITER) = &(SUBTABLES)->array[(SUBTABLES)->count]; \
- (ITER) > (SUBTABLES)->array \
- && OVS_LIKELY((SUBTABLE) = (--(ITER))->subtable);)
-
-static void
-cls_subtables_verify(struct cls_subtables *subtables)
-{
- struct cls_subtable *table;
- struct cls_subtable_entry *iter;
- unsigned int priority = 0;
- CLS_SUBTABLES_FOR_EACH_REVERSE (table, iter, subtables) {
- if (iter->max_priority != table->max_priority) {
- VLOG_WARN("Subtable %p has mismatching priority in cache (%u !=
%u)",
- table, iter->max_priority, table->max_priority);
- }
- if (iter->max_priority < priority) {
- VLOG_WARN("Subtable cache is out of order (%u < %u)",
- iter->max_priority, priority);
- }
- priority = iter->max_priority;
- }
+ /* Lowest priority subtables at the end. */
+ cls->subtables.array[cls->subtables.count++] = a;
+ sort_subtables(&cls->subtables);
}
-static void
-cls_subtables_reset(struct cls_classifier *cls)
+/* Subtable removal. */
+static inline void
+cls_subtables_remove(struct cls_subtables *subtables, int index)
{
- struct cls_subtables old = cls->subtables;
- struct cls_subtable *subtable;
-
- VLOG_WARN("Resetting subtable cache.");
-
- cls_subtables_verify(&cls->subtables);
-
- cls_subtables_init(&cls->subtables);
-
- HMAP_FOR_EACH (subtable, hmap_node, &cls->subtables_map) {
- struct cls_match *head;
- struct cls_subtable_entry elem;
- struct cls_subtable *table;
- struct cls_subtable_entry *iter, *from = NULL;
- unsigned int new_max = 0;
- unsigned int max_count = 0;
- bool found;
-
- /* Verify max_priority. */
- HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
- if (head->priority > new_max) {
- new_max = head->priority;
- max_count = 1;
- } else if (head->priority == new_max) {
- max_count++;
- }
- }
- if (new_max != subtable->max_priority ||
- max_count != subtable->max_count) {
- VLOG_WARN("subtable %p (%u rules) has mismatching max_priority "
- "(%u) or max_count (%u). Highest priority found was %u, "
- "count: %u",
- subtable, subtable->n_rules, subtable->max_priority,
- subtable->max_count, new_max, max_count);
- subtable->max_priority = new_max;
- subtable->max_count = max_count;
- }
-
- /* Locate the subtable from the old cache. */
- found = false;
- CLS_SUBTABLES_FOR_EACH (table, iter, &old) {
- if (table == subtable) {
- if (iter->max_priority != new_max) {
- VLOG_WARN("Subtable %p has wrong max priority (%u != %u) "
- "in the old cache.",
- subtable, iter->max_priority, new_max);
- }
- if (found) {
- VLOG_WARN("Subtable %p duplicated in the old cache.",
- subtable);
- }
- found = true;
- }
- }
- if (!found) {
- VLOG_WARN("Subtable %p not found from the old cache.", subtable);
- }
-
- elem.subtable = subtable;
- elem.tag = subtable->tag;
- elem.max_priority = subtable->max_priority;
- cls_subtables_push_back(&cls->subtables, elem);
-
- /* Possibly move 'subtable' earlier in the priority array. If
- * we break out of the loop, then the subtable (at 'from')
- * should be moved to the position right after the current
- * element. If the loop terminates normally, then 'iter' will
- * be at the first array element and we'll move the subtable
- * to the front of the array. */
- CLS_SUBTABLES_FOR_EACH_REVERSE (table, iter, &cls->subtables) {
- if (table == subtable) {
- from = iter; /* Locate the subtable as we go. */
- } else if (table->max_priority >= new_max) {
- ovs_assert(from != NULL);
- iter++; /* After this. */
- break;
- }
- }
-
- /* Move subtable at 'from' to 'iter'. */
- cls_subtables_move(iter, from);
- }
-
- /* Verify that the old and the new have the same size. */
- if (old.count != cls->subtables.count) {
- VLOG_WARN("subtables cache sizes differ: old (%"PRIuSIZE
- ") != new (%"PRIuSIZE").",
- old.count, cls->subtables.count);
- }
-
- cls_subtables_destroy(&old);
-
- cls_subtables_verify(&cls->subtables);
+ ovs_assert(index >= 0 && index < subtables->count);
+ subtables->array[index] = subtables->array[--subtables->count];
+ sort_subtables(subtables);
}
+#define CLS_SUBTABLES_FOR_EACH(SUBTABLE, INDEX, SUBTABLES) \
+ for ((INDEX) = 0; \
+ (INDEX) < (SUBTABLES)->count \
+ && ((SUBTABLE) = (SUBTABLES)->array[INDEX], true); \
+ (INDEX)++)
/* flow/miniflow/minimask/minimatch utilities.
* These are only used by the classifier, so place them here to allow
@@ -767,7 +606,7 @@ trie_init(struct cls_classifier *cls, int trie_idx,
{
struct cls_trie *trie = &cls->tries[trie_idx];
struct cls_subtable *subtable;
- struct cls_subtable_entry *iter;
+ int index;
if (trie_idx < cls->n_tries) {
trie_destroy(trie->root);
@@ -776,7 +615,7 @@ trie_init(struct cls_classifier *cls, int trie_idx,
trie->field = field;
/* Add existing rules to the trie. */
- CLS_SUBTABLES_FOR_EACH (subtable, iter, &cls->subtables) {
+ CLS_SUBTABLES_FOR_EACH (subtable, index, &cls->subtables) {
unsigned int plen;
plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0;
@@ -999,8 +838,21 @@ classifier_remove(struct classifier *cls_, struct cls_rule
*rule)
if (--subtable->n_rules == 0) {
destroy_subtable(cls, subtable);
- } else {
- update_subtables_after_removal(cls, subtable, cls_match->priority);
+ } else if (subtable->max_priority == cls_match->priority
+ && --subtable->max_count == 0) {
+ /* Find the new 'max_priority' and 'max_count'. */
+ struct cls_match *head;
+
+ subtable->max_priority = 0;
+ HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
+ if (head->priority > subtable->max_priority) {
+ subtable->max_priority = head->priority;
+ subtable->max_count = 1;
+ } else if (head->priority == subtable->max_priority) {
+ subtable->max_count++;
+ }
+ }
+ sort_subtables(&cls->subtables);
}
cls->n_rules--;
@@ -1030,9 +882,9 @@ trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie
*trie)
}
static inline void
-lookahead_subtable(const struct cls_subtable_entry *subtables)
+lookahead_subtable(const struct cls_subtable *subtable)
{
- ovs_prefetch_range(subtables->subtable, sizeof *subtables->subtable);
+ ovs_prefetch_range(subtable, sizeof *subtable);
}
/* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
@@ -1050,10 +902,10 @@ classifier_lookup(const struct classifier *cls_, const
struct flow *flow,
struct cls_classifier *cls = cls_->cls;
const struct cls_partition *partition;
tag_type tags;
- struct cls_match *best;
+ const struct cls_match *best;
struct trie_ctx trie_ctx[CLS_MAX_TRIES];
int i;
- struct cls_subtable_entry *subtables = cls->subtables.array;
+ struct cls_subtable **subtables = cls->subtables.array;
int n_subtables = cls->subtables.count;
int64_t best_priority = -1;
@@ -1091,15 +943,16 @@ classifier_lookup(const struct classifier *cls_, const
struct flow *flow,
/* Prefetch the first subtables. */
if (n_subtables > 1) {
- lookahead_subtable(subtables);
- lookahead_subtable(subtables + 1);
+ lookahead_subtable(subtables[0]);
+ lookahead_subtable(subtables[1]);
}
best = NULL;
+
for (i = 0; OVS_LIKELY(i < n_subtables); i++) {
struct cls_match *rule;
- if ((int64_t)subtables[i].max_priority <= best_priority) {
+ if ((int64_t)subtables[i]->max_priority <= best_priority) {
/* Subtables are in descending priority order,
* can not find anything better. */
break;
@@ -1107,15 +960,14 @@ classifier_lookup(const struct classifier *cls_, const
struct flow *flow,
/* Prefetch a forthcoming subtable. */
if (i + 2 < n_subtables) {
- lookahead_subtable(&subtables[i + 2]);
+ lookahead_subtable(subtables[i + 2]);
}
- if (!tag_intersects(tags, subtables[i].tag)) {
+ if (!tag_intersects(tags, subtables[i]->tag)) {
continue;
}
- rule = find_match_wc(subtables[i].subtable, flow, trie_ctx,
- cls->n_tries, wc);
+ rule = find_match_wc(subtables[i], flow, trie_ctx, cls->n_tries, wc);
if (rule && (int64_t)rule->priority > best_priority) {
best_priority = (int64_t)rule->priority;
best = rule;
@@ -1176,9 +1028,9 @@ struct cls_rule *classifier_lookup_miniflow_first(const
struct classifier *cls_,
{
struct cls_classifier *cls = cls_->cls;
struct cls_subtable *subtable;
- struct cls_subtable_entry *iter;
+ int index;
- CLS_SUBTABLES_FOR_EACH (subtable, iter, &cls->subtables) {
+ CLS_SUBTABLES_FOR_EACH (subtable, index, &cls->subtables) {
struct cls_match *rule;
rule = find_match_miniflow(subtable, flow,
@@ -1252,15 +1104,15 @@ classifier_rule_overlaps(const struct classifier *cls_,
{
struct cls_classifier *cls = cls_->cls;
struct cls_subtable *subtable;
- struct cls_subtable_entry *iter;
+ int index;
/* Iterate subtables in the descending max priority order. */
- CLS_SUBTABLES_FOR_EACH (subtable, iter, &cls->subtables) {
+ CLS_SUBTABLES_FOR_EACH (subtable, index, &cls->subtables) {
uint32_t storage[FLOW_U32S];
struct minimask mask;
struct cls_match *head;
- if (target->priority > iter->max_priority) {
+ if (target->priority > subtable->max_priority) {
break; /* Can skip this and the rest of the subtables. */
}
@@ -1445,7 +1297,6 @@ insert_subtable(struct cls_classifier *cls, const struct
minimask *mask)
int i, index = 0;
struct flow_wildcards old, new;
uint8_t prev;
- struct cls_subtable_entry elem;
int count = count_1bits(mask->masks.map);
subtable = xzalloc(sizeof *subtable - sizeof mask->masks.inline_values
@@ -1496,10 +1347,7 @@ insert_subtable(struct cls_classifier *cls, const struct
minimask *mask)
= 32 - ctz32(ntohl(MINIFLOW_GET_BE32(&mask->masks, tp_src)));
hmap_insert(&cls->subtables_map, &subtable->hmap_node, hash);
- elem.subtable = subtable;
- elem.tag = subtable->tag;
- elem.max_priority = subtable->max_priority;
- cls_subtables_push_back(&cls->subtables, elem);
+ cls_subtables_insert(cls, subtable);
return subtable;
}
@@ -1507,13 +1355,12 @@ insert_subtable(struct cls_classifier *cls, const
struct minimask *mask)
static void
destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable)
{
+ struct cls_subtable *table;
int i;
- struct cls_subtable *table = NULL;
- struct cls_subtable_entry *iter;
- CLS_SUBTABLES_FOR_EACH (table, iter, &cls->subtables) {
+ CLS_SUBTABLES_FOR_EACH (table, i, &cls->subtables) {
if (table == subtable) {
- cls_subtables_remove(&cls->subtables, iter);
+ cls_subtables_remove(&cls->subtables, i);
break;
}
}
@@ -1529,112 +1376,21 @@ destroy_subtable(struct cls_classifier *cls, struct
cls_subtable *subtable)
free(subtable);
}
-/* This function performs the following updates for 'subtable' in 'cls'
- * following the addition of a new rule with priority 'new_priority' to
- * 'subtable':
- *
- * - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
- *
- * - Update 'subtable''s position in 'cls->subtables' if necessary.
- *
- * This function should only be called after adding a new rule, not after
- * replacing a rule by an identical one or modifying a rule in-place. */
-static void
-update_subtables_after_insertion(struct cls_classifier *cls,
- struct cls_subtable *subtable,
- unsigned int new_priority)
-{
- if (new_priority == subtable->max_priority) {
- ++subtable->max_count;
- } else if (new_priority > subtable->max_priority) {
- struct cls_subtable *table;
- struct cls_subtable_entry *iter, *from = NULL;
-
- subtable->max_priority = new_priority;
- subtable->max_count = 1;
-
- /* Possibly move 'subtable' earlier in the priority array. If
- * we break out of the loop, then the subtable (at 'from')
- * should be moved to the position right after the current
- * element. If the loop terminates normally, then 'iter' will
- * be at the first array element and we'll move the subtable
- * to the front of the array. */
- CLS_SUBTABLES_FOR_EACH_REVERSE (table, iter, &cls->subtables) {
- if (table == subtable) {
- from = iter; /* Locate the subtable as we go. */
- iter->max_priority = new_priority;
- } else if (table->max_priority >= new_priority) {
- if (from == NULL) {
- /* Corrupted cache? */
- cls_subtables_reset(cls);
- VLOG_ABORT("update_subtables_after_insertion(): Subtable
priority list corrupted.");
- OVS_NOT_REACHED();
- }
- iter++; /* After this. */
- break;
- }
- }
+static int
+cmp_subtable(const void *a_, const void *b_)
+{
+ unsigned int a = (*((const struct cls_subtable *const *)a_))->max_priority;
+ unsigned int b = (*((const struct cls_subtable *const *)b_))->max_priority;
- /* Move subtable at 'from' to 'iter'. */
- cls_subtables_move(iter, from);
- }
+ return a == b ? 0 : (a < b ? 1 : -1);
}
-/* This function performs the following updates for 'subtable' in 'cls'
- * following the deletion of a rule with priority 'del_priority' from
- * 'subtable':
- *
- * - Update 'subtable->max_priority' and 'subtable->max_count' if necessary.
- *
- * - Update 'subtable''s position in 'cls->subtables' if necessary.
- *
- * This function should only be called after removing a rule, not after
- * replacing a rule by an identical one or modifying a rule in-place. */
-static void
-update_subtables_after_removal(struct cls_classifier *cls,
- struct cls_subtable *subtable,
- unsigned int del_priority)
+static inline void
+sort_subtables(struct cls_subtables *subtables)
{
- if (del_priority == subtable->max_priority && --subtable->max_count == 0) {
- struct cls_match *head;
- struct cls_subtable *table;
- struct cls_subtable_entry *iter, *from = NULL;
- subtable->max_priority = 0;
- HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
- if (head->priority > subtable->max_priority) {
- subtable->max_priority = head->priority;
- subtable->max_count = 1;
- } else if (head->priority == subtable->max_priority) {
- ++subtable->max_count;
- }
- }
-
- /* Possibly move 'subtable' later in the priority array.
- * After the loop the 'iter' will point right after the position
- * at which the subtable should be moved (either at a subtable
- * with an equal or lower priority, or just past the array),
- * so it is decremented once. */
- CLS_SUBTABLES_FOR_EACH (table, iter, &cls->subtables) {
- if (table == subtable) {
- from = iter; /* Locate the subtable as we go. */
- iter->max_priority = subtable->max_priority;
- } else if (table->max_priority <= subtable->max_priority) {
- if (from == NULL) {
- /* Corrupted cache? */
- cls_subtables_reset(cls);
- VLOG_ABORT("update_subtables_after_removal(): Subtable
priority list corrupted.");
- OVS_NOT_REACHED();
- }
- break;
- }
- }
- /* Now at one past the destination. */
- iter--;
-
- /* Move subtable at 'from' to 'iter'. */
- cls_subtables_move(iter, from);
- }
+ qsort(subtables->array, subtables->count, sizeof *subtables->array,
+ cmp_subtable);
}
struct range {
@@ -1914,7 +1670,15 @@ insert_rule(struct cls_classifier *cls, struct
cls_subtable *subtable,
out:
if (!old) {
- update_subtables_after_insertion(cls, subtable, cls_match->priority);
+ /* Rule was added, not replaced. Update 'subtable's 'max_priority'
+ * and 'max_count', if necessary. */
+ if (subtable->max_priority == cls_match->priority) {
+ subtable->max_count++;
+ } else if (cls_match->priority > subtable->max_priority) {
+ subtable->max_count = 1;
+ subtable->max_priority = cls_match->priority;
+ sort_subtables(&cls->subtables);
+ }
} else {
/* Remove old node from indices. */
for (i = 0; i < subtable->n_indices; i++) {
--
1.8.1.2
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
