[ovs-dev] [PATCH 2/3] lib/classifier: Simplify subtable array.
Jarno Rajahalme
jrajahalme at nicira.com
Fri May 16 21:44:40 UTC 2014
Do not cache the 'tag' and 'max_priority' in the subtable array. This
makes later changes to classifier easier.
Also 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.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/classifier.c | 374 ++++++++++++++++++++++--------------------------------
1 file changed, 151 insertions(+), 223 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index 00d47ac..44ed2c6 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. */
size_t alloc_size; /* Number of allocated elements. */
- struct cls_subtable_entry *array;
+ struct cls_subtable **array;
};
enum {
@@ -138,13 +132,6 @@ static struct cls_subtable *insert_subtable(struct cls_classifier *,
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 struct cls_match *find_match_wc(const struct cls_subtable *,
const struct flow *, struct trie_ctx *,
unsigned int n_tries,
@@ -199,44 +186,33 @@ cls_subtables_destroy(struct cls_subtables *subtables)
memset(subtables, 0, sizeof *subtables);
}
-/* Subtables insertion. */
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);
- }
+cls_subtables_change_priority(struct cls_classifier *, struct cls_subtable *,
+ unsigned int new_priority);
- 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)
+/* Subtable insertion. 'a->max_priority' must be updated after insertion,
+ * Unless 'max_priority' remains at 0. */
+static void
+cls_subtables_insert(struct cls_classifier *cls, struct cls_subtable *a)
{
- if (to != from) {
- struct cls_subtable_entry temp = *from;
+ unsigned int priority = a->max_priority;
- 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);
}
+
+ /* Lowest priority subtables at the end. */
+ a->max_priority = 0;
+ cls->subtables.array[cls->subtables.count++] = a;
+ cls_subtables_change_priority(cls, a, priority);
}
-/* Subtables removal. */
+/* Subtable removal. */
static inline void
cls_subtables_remove(struct cls_subtables *subtables,
- struct cls_subtable_entry *elem)
+ struct cls_subtable **elem)
{
ssize_t size = (&subtables->array[subtables->count]
- (elem + 1)) * sizeof *elem;
@@ -249,35 +225,31 @@ cls_subtables_remove(struct cls_subtables *subtables,
#define CLS_SUBTABLES_FOR_EACH(SUBTABLE, ITER, SUBTABLES) \
for ((ITER) = (SUBTABLES)->array; \
(ITER) < &(SUBTABLES)->array[(SUBTABLES)->count] \
- && OVS_LIKELY((SUBTABLE) = (ITER)->subtable); \
+ && OVS_LIKELY((SUBTABLE) = *(ITER)); \
++(ITER))
#define CLS_SUBTABLES_FOR_EACH_CONTINUE(SUBTABLE, ITER, SUBTABLES) \
for (++(ITER); \
(ITER) < &(SUBTABLES)->array[(SUBTABLES)->count] \
- && OVS_LIKELY((SUBTABLE) = (ITER)->subtable); \
+ && OVS_LIKELY((SUBTABLE) = *(ITER)); \
++(ITER))
#define CLS_SUBTABLES_FOR_EACH_REVERSE(SUBTABLE, ITER, SUBTABLES) \
for ((ITER) = &(SUBTABLES)->array[(SUBTABLES)->count]; \
(ITER) > (SUBTABLES)->array \
- && OVS_LIKELY((SUBTABLE) = (--(ITER))->subtable);)
+ && OVS_LIKELY((SUBTABLE) = *(--(ITER)));)
static void
cls_subtables_verify(struct cls_subtables *subtables)
{
struct cls_subtable *table;
- struct cls_subtable_entry *iter;
+ struct cls_subtable **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) {
+ if (table->max_priority < priority) {
VLOG_WARN("Subtable cache is out of order (%u < %u)",
- iter->max_priority, priority);
+ table->max_priority, priority);
}
- priority = iter->max_priority;
+ priority = table->max_priority;
}
}
@@ -295,13 +267,27 @@ cls_subtables_reset(struct cls_classifier *cls)
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;
+ struct cls_subtable **iter;
unsigned int new_max = 0;
unsigned int max_count = 0;
bool found;
+ /* Locate the subtable from the old cache. */
+ found = false;
+ CLS_SUBTABLES_FOR_EACH (table, iter, &old) {
+ if (table == subtable) {
+ 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);
+ }
+
/* Verify max_priority. */
HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
if (head->priority > new_max) {
@@ -311,6 +297,7 @@ cls_subtables_reset(struct cls_classifier *cls)
max_count++;
}
}
+
if (new_max != subtable->max_priority ||
max_count != subtable->max_count) {
VLOG_WARN("subtable %p (%u rules) has mismatching max_priority "
@@ -321,32 +308,34 @@ cls_subtables_reset(struct cls_classifier *cls)
subtable->max_priority = new_max;
subtable->max_count = max_count;
}
+ cls_subtables_insert(cls, subtable);
+ }
- /* 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);
- }
+ /* 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);
+}
+
+/* Change subtable's 'max_priority' and keep the array ordered. */
+static void
+cls_subtables_change_priority(struct cls_classifier *cls,
+ struct cls_subtable *subtable,
+ unsigned int new_priority)
+{
+ struct cls_subtable *table;
+ struct cls_subtable **iter, **from = NULL;
+ unsigned int old_priority = subtable->max_priority;
- elem.subtable = subtable;
- elem.tag = subtable->tag;
- elem.max_priority = subtable->max_priority;
- cls_subtables_push_back(&cls->subtables, elem);
+ subtable->max_priority = new_priority;
+ if (new_priority > old_priority) {
/* 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
@@ -356,25 +345,55 @@ cls_subtables_reset(struct cls_classifier *cls)
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);
+ } else if (table->max_priority >= new_priority) {
iter++; /* After this. */
break;
}
}
+ if (from == NULL) {
+ /* Corrupted cache? */
+ cls_subtables_reset(cls);
+ VLOG_ABORT("cls_subtable_change_priority(>): Subtable priority list corrupted.");
+ OVS_NOT_REACHED();
+ }
+
/* Move subtable at 'from' to 'iter'. */
- cls_subtables_move(iter, from);
- }
+ if (iter < from) {
+ /* Shift entries [iter,from) forward to make space at 'iter'. */
+ memmove(iter + 1, iter, (from - iter) * sizeof *iter);
+ *iter = subtable;
+ }
+ } else if (new_priority < old_priority) {
+ /* 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. */
+ } else if (table->max_priority <= new_priority) {
+ break;
+ }
+ }
+ /* Now at one past the destination. */
+ iter--;
- /* 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);
- }
+ if (from == NULL) {
+ /* Corrupted cache? */
+ cls_subtables_reset(cls);
+ VLOG_ABORT("cls_subtable_change_priority(<) Subtable priority list corrupted.");
+ OVS_NOT_REACHED();
+ }
- cls_subtables_destroy(&old);
+ /* Move subtable at 'from' to 'iter'. */
+ if (iter > from) {
+ /* Shift entries (from,iter] backwards to make space at 'iter'. */
+ memmove(from, from + 1, (iter - from) * sizeof *iter);
+ *iter = subtable;
+ }
+ }
cls_subtables_verify(&cls->subtables);
}
@@ -767,7 +786,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;
+ struct cls_subtable **iter;
if (trie_idx < cls->n_tries) {
trie_destroy(trie->root);
@@ -999,8 +1018,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;
+ unsigned int max_priority = 0;
+
+ HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
+ if (head->priority > max_priority) {
+ max_priority = head->priority;
+ subtable->max_count = 1;
+ } else if (head->priority == max_priority) {
+ ++subtable->max_count;
+ }
+ }
+ cls_subtables_change_priority(cls, subtable, max_priority);
}
cls->n_rules--;
@@ -1030,9 +1062,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,13 +1082,14 @@ 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;
+
/* Prefetch the subtables array. */
ovs_prefetch_range(subtables, n_subtables * sizeof *subtables);
@@ -1091,15 +1124,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 +1141,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,7 +1209,7 @@ 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;
+ struct cls_subtable **iter;
CLS_SUBTABLES_FOR_EACH (subtable, iter, &cls->subtables) {
struct cls_match *rule;
@@ -1252,7 +1285,7 @@ classifier_rule_overlaps(const struct classifier *cls_,
{
struct cls_classifier *cls = cls_->cls;
struct cls_subtable *subtable;
- struct cls_subtable_entry *iter;
+ struct cls_subtable **iter;
/* Iterate subtables in the descending max priority order. */
CLS_SUBTABLES_FOR_EACH (subtable, iter, &cls->subtables) {
@@ -1260,7 +1293,7 @@ classifier_rule_overlaps(const struct classifier *cls_,
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 +1478,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 +1528,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;
}
@@ -1508,8 +1537,8 @@ static void
destroy_subtable(struct cls_classifier *cls, struct cls_subtable *subtable)
{
int i;
- struct cls_subtable *table = NULL;
- struct cls_subtable_entry *iter;
+ struct cls_subtable *table;
+ struct cls_subtable **iter;
CLS_SUBTABLES_FOR_EACH (table, iter, &cls->subtables) {
if (table == subtable) {
@@ -1529,114 +1558,6 @@ 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;
- }
- }
-
- /* Move subtable at 'from' to 'iter'. */
- cls_subtables_move(iter, from);
- }
-}
-
-/* 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)
-{
- 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);
- }
-}
-
struct range {
uint8_t start;
uint8_t end;
@@ -1914,7 +1835,14 @@ 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;
+ cls_subtables_change_priority(cls, subtable, cls_match->priority);
+ }
} else {
/* Remove old node from indices. */
for (i = 0; i < subtable->n_indices; i++) {
--
1.7.10.4
More information about the dev
mailing list