This patch integrates insert_rule() to the sole caller
classifier_replace(). This makes classifer_replace() more symmetric
with classifier_remove(), and makes it easier to change the following:
- Rules invisible to the lookups are no longer inserted to any of the
index cmaps or tries.
- subtable's 'n_rules' member is eliminated.
Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
---
lib/classifier-private.h | 5 +-
lib/classifier.c | 365 ++++++++++++++++++++++++----------------------
lib/rculist.h | 13 +-
tests/test-classifier.c | 2 +-
4 files changed, 197 insertions(+), 188 deletions(-)
diff --git a/lib/classifier-private.h b/lib/classifier-private.h
index a00c001..441aaff 100644
--- a/lib/classifier-private.h
+++ b/lib/classifier-private.h
@@ -31,11 +31,12 @@ struct cls_subtable {
struct cmap_node cmap_node; /* Within struct classifier 'subtables_map'. */
/* The fields are only used by writers. */
- int n_rules OVS_GUARDED; /* Number of rules, including
- * duplicates. */
int max_priority OVS_GUARDED; /* Max priority of any rule in subtable. */
unsigned int max_count OVS_GUARDED; /* Count of max_priority rules. */
+ /* Identical, but lower priority rules are not inserted to any of the
+ * following data structures. */
+
/* These fields are accessed by readers who care about wildcarding. */
const tag_type tag; /* Tag generated from mask for partitioning. */
const uint8_t n_indices; /* How many indices to use. */
diff --git a/lib/classifier.c b/lib/classifier.c
index 82aaf3e..0e985c3 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -44,11 +44,11 @@ cls_match_alloc(struct cls_rule *rule)
= xmalloc(sizeof *cls_match - sizeof cls_match->flow.inline_values
+ MINIFLOW_VALUES_SIZE(count));
+ rculist_init(&cls_match->list);
*CONST_CAST(const struct cls_rule **, &cls_match->cls_rule) = rule;
*CONST_CAST(int *, &cls_match->priority) = rule->priority;
miniflow_clone_inline(CONST_CAST(struct miniflow *, &cls_match->flow),
&rule->match.flow, count);
- rule->cls_match = cls_match;
return cls_match;
}
@@ -60,9 +60,6 @@ static struct cls_subtable *insert_subtable(struct classifier
*cls,
OVS_REQUIRES(cls->mutex);
static void destroy_subtable(struct classifier *cls, struct cls_subtable *)
OVS_REQUIRES(cls->mutex);
-static struct cls_match *insert_rule(struct classifier *cls,
- struct cls_subtable *, struct cls_rule *)
- OVS_REQUIRES(cls->mutex);
static const struct cls_match *find_match_wc(const struct cls_subtable *,
const struct flow *,
@@ -388,11 +385,7 @@ trie_init(struct classifier *cls, int trie_idx, const
struct mf_field *field)
struct cls_match *head;
CMAP_FOR_EACH (head, cmap_node, &subtable->rules) {
- struct cls_match *match;
-
- FOR_EACH_RULE_IN_LIST_PROTECTED (match, head) {
- trie_insert(trie, match->cls_rule, plen);
- }
+ trie_insert(trie, head->cls_rule, plen);
}
}
/* Initialize subtable's prefix length on this field. This will
@@ -466,47 +459,85 @@ 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])
+ OVS_REQUIRES(cls->mutex)
+{
+ /* Rule's data is already in the tries. */
+
+ new->partition = head->partition; /* Steal partition, if any. */
+ head->partition = NULL;
+
+ 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'. Until 'rule' is removed from 'cls', the caller
* must not modify or free it.
*
* If 'cls' already contains an identical rule (including wildcards, values of
* fixed fields, and priority), replaces the old rule by 'rule' and returns the
* rule that was replaced. The caller takes ownership of the returned rule and
- * is thus responsible for destroying it with cls_rule_destroy(), freeing the
- * memory block in which it resides, etc., as necessary.
+ * is thus responsible for destroying it with cls_rule_destroy(), after RCU
+ * grace period has passed (see ovsrcu_postpone()).
*
* Returns NULL if 'cls' does not contain a rule with an identical key, after
* inserting the new rule. In this case, no rules are displaced by the new
* rule, even rules that cannot have any effect because the new rule matches a
- * superset of their flows and has higher priority. */
+ * superset of their flows and has higher priority.
+ *
+ * As the readers are operating concurrently with the modifications, a
+ * concurrent reader may or may not see the new rule, depending on how the
+ * concurrent events overlap with each other.
+ *
+ * The new rule is first added to the segment indices, so the 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 by forthcoming
+ * revalidation always scheduled after flow table changes.
+ *
+ * The subtable's max priority is updated only after the rule is inserted, so
+ * the concurrent readers may not see the rule, as the updated priority ordered
+ * subtable list will only be visible after the subtable's max priority is
+ * updated. */
const struct cls_rule *
classifier_replace(struct classifier *cls, struct cls_rule *rule)
OVS_EXCLUDED(cls->mutex)
{
- struct cls_match *old_rule;
struct cls_subtable *subtable;
- const struct cls_rule *old_cls_rule = NULL;
+ struct cls_match *head;
+ int i;
+ uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES];
+ uint8_t prev_be32ofs = 0;
+ size_t n_rules = 0;
+ struct cls_match *new = cls_match_alloc(rule);
ovs_mutex_lock(&cls->mutex);
+ rule->cls_match = new;
+
subtable = find_subtable(cls, &rule->match.mask);
if (!subtable) {
subtable = insert_subtable(cls, &rule->match.mask);
}
- old_rule = insert_rule(cls, subtable, rule);
- if (!old_rule) {
- old_cls_rule = NULL;
-
- rule->cls_match->partition = NULL;
- if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
- ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
- rule->cls_match->partition = create_partition(cls, subtable,
- metadata);
- }
-
- cls->n_rules++;
+ /* Compute hashes in segments. */
+ for (i = 0; i < subtable->n_indices; i++) {
+ ihash[i] = minimatch_hash_range(&rule->match, prev_be32ofs,
+ subtable->index_ofs[i], &basis);
+ prev_be32ofs = subtable->index_ofs[i];
+ }
+ hash = minimatch_hash_range(&rule->match, prev_be32ofs, FLOW_U32S, &basis);
- for (int i = 0; i < cls->n_tries; i++) {
+ head = find_equal(subtable, &rule->match.flow, hash);
+ if (!head) {
+ /* Tries. */
+ for (i = 0; i < cls->n_tries; i++) {
if (subtable->trie_plen[i]) {
trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]);
}
@@ -523,17 +554,83 @@ classifier_replace(struct classifier *cls, struct
cls_rule *rule)
trie_insert_prefix(&subtable->ports_trie, &masked_ports,
subtable->ports_mask_len);
}
- } else {
- old_cls_rule = old_rule->cls_rule;
- rule->cls_match->partition = old_rule->partition;
- CONST_CAST(struct cls_rule *, old_cls_rule)->cls_match = NULL;
- /* 'old_rule' contains a cmap_node, which may not be freed
- * immediately. */
- ovsrcu_postpone(free, old_rule);
+ new->partition = NULL;
+ if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX) {
+ ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
+
+ new->partition = create_partition(cls, subtable, metadata);
+ }
+
+ /* Make rule visible to lookups. */
+ for (i = 0; i < subtable->n_indices; i++) {
+ cmap_insert(&subtable->indices[i], &new->index_nodes[i], ihash[i]);
+ }
+ n_rules = cmap_insert(&subtable->rules, &new->cmap_node, hash);
+
+ } else { /* Equal rules exist in the classifier already. */
+ struct cls_match *iter;
+ struct cls_rule *old = NULL;
+
+ /* Scan the list for the insertion point that will keep the list in
+ * order of decreasing priority. */
+ FOR_EACH_RULE_IN_LIST_PROTECTED (iter, head) {
+ if (rule->priority >= iter->priority) {
+ if (rule->priority == iter->priority) {
+ old = CONST_CAST(struct cls_rule *, iter->cls_rule);
+ }
+ break;
+ }
+ }
+
+ /* 'iter' now at the insertion point or NULL it at end. */
+ if (old) {
+ rculist_replace(&new->list, &iter->list);
+ } else {
+ if (!iter) {
+ rculist_push_back(&head->list, &new->list);
+ } else {
+ /* Insert 'rule' right before 'iter'. */
+ rculist_insert(&iter->list, &new->list);
+ }
+ }
+
+ /* 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);
+ }
+
+ if (old) {
+ ovsrcu_postpone(free, iter);
+ old->cls_match = NULL;
+
+ /* No change in subtable's max priority or max count. */
+
+ /* Return displaced rule. Caller is responsible for keeping it
+ * around until all threads quiesce. */
+ ovs_mutex_unlock(&cls->mutex);
+ return old;
+ }
}
+
+ /* Update 'subtable's 'max_priority' and 'max_count', if necessary. */
+ if (n_rules == 1) {
+ subtable->max_priority = rule->priority;
+ subtable->max_count = 1;
+ pvector_insert(&cls->subtables, subtable, rule->priority);
+ } else if (rule->priority == subtable->max_priority) {
+ ++subtable->max_count;
+ } else if (rule->priority > subtable->max_priority) {
+ subtable->max_priority = rule->priority;
+ subtable->max_count = 1;
+ pvector_change_priority(&cls->subtables, subtable, rule->priority);
+ }
+
+ /* Nothing was replaced. */
+ cls->n_rules++;
ovs_mutex_unlock(&cls->mutex);
- return old_cls_rule;
+ return NULL;
}
/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller
@@ -563,11 +660,13 @@ classifier_remove(struct classifier *cls, const struct
cls_rule *rule)
{
struct cls_partition *partition;
struct cls_match *cls_match;
- struct cls_match *head;
struct cls_subtable *subtable;
+ struct cls_match *prev;
+ struct cls_match *next;
int i;
uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES];
uint8_t prev_be32ofs = 0;
+ size_t n_rules;
ovs_mutex_lock(&cls->mutex);
cls_match = rule->cls_match;
@@ -575,10 +674,43 @@ classifier_remove(struct classifier *cls, const struct
cls_rule *rule)
rule = NULL;
goto unlock; /* Already removed. */
}
+ /* Mark as removed. */
+ CONST_CAST(struct cls_rule *, rule)->cls_match = NULL;
+
+ INIT_CONTAINER(prev, rculist_back_protected(&cls_match->list), list);
+ INIT_CONTAINER(next, rculist_next(&cls_match->list), list);
+
+ /* Remove from the list of equal rules. */
+ rculist_remove(&cls_match->list);
+
+ /* Check if this is NOT a head rule. */
+ if (prev->priority > rule->priority) {
+ /* Not the highest priority rule, no need to check subtable's
+ * 'max_priority'. */
+ goto free;
+ }
subtable = find_subtable(cls, &rule->match.mask);
ovs_assert(subtable);
+ for (i = 0; i < subtable->n_indices; i++) {
+ ihash[i] = minimatch_hash_range(&rule->match, prev_be32ofs,
+ subtable->index_ofs[i], &basis);
+ prev_be32ofs = subtable->index_ofs[i];
+ }
+ hash = minimatch_hash_range(&rule->match, prev_be32ofs, FLOW_U32S, &basis);
+
+ /* Head rule. Check if 'next' is an identical, lower-priority rule that
+ * will replace 'rule' in the data structures. */
+ if (next->priority < rule->priority) {
+ subtable_replace_head_rule(cls, subtable, cls_match, next, hash,
+ ihash);
+ goto check_priority;
+ }
+
+ /* 'rule' is last of the kind in the classifier, must remove from all the
+ * data structures. */
+
if (subtable->ports_mask_len) {
ovs_be32 masked_ports = minimatch_get_ports(&rule->match);
@@ -593,26 +725,10 @@ classifier_remove(struct classifier *cls, const struct
cls_rule *rule)
/* Remove rule node from indices. */
for (i = 0; i < subtable->n_indices; i++) {
- ihash[i] = minimatch_hash_range(&rule->match, prev_be32ofs,
- subtable->index_ofs[i], &basis);
cmap_remove(&subtable->indices[i], &cls_match->index_nodes[i],
ihash[i]);
- prev_be32ofs = subtable->index_ofs[i];
- }
- hash = minimatch_hash_range(&rule->match, prev_be32ofs, FLOW_U32S, &basis);
-
- head = find_equal(subtable, &rule->match.flow, hash);
- if (head != cls_match) {
- rculist_remove(&cls_match->list);
- } else if (rculist_is_empty(&cls_match->list)) {
- cmap_remove(&subtable->rules, &cls_match->cmap_node, hash);
- } else {
- struct cls_match *next = next_rule_in_list_protected(cls_match);
-
- rculist_remove(&cls_match->list);
- cmap_replace(&subtable->rules, &cls_match->cmap_node,
- &next->cmap_node, hash);
}
+ n_rules = cmap_remove(&subtable->rules, &cls_match->cmap_node, hash);
partition = cls_match->partition;
if (partition) {
@@ -625,30 +741,31 @@ classifier_remove(struct classifier *cls, const struct
cls_rule *rule)
}
}
- if (--subtable->n_rules == 0) {
+ if (n_rules == 0) {
destroy_subtable(cls, subtable);
- } else if (subtable->max_priority == cls_match->priority
- && --subtable->max_count == 0) {
- /* Find the new 'max_priority' and 'max_count'. */
- struct cls_match *head;
- int max_priority = INT_MIN;
+ } else {
+check_priority:
+ if (subtable->max_priority == rule->priority
+ && --subtable->max_count == 0) {
+ /* Find the new 'max_priority' and 'max_count'. */
+ struct cls_match *head;
+ int max_priority = INT_MIN;
- CMAP_FOR_EACH (head, cmap_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;
+ CMAP_FOR_EACH (head, cmap_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;
+ }
}
+ subtable->max_priority = max_priority;
+ pvector_change_priority(&cls->subtables, subtable, max_priority);
}
- subtable->max_priority = max_priority;
- pvector_change_priority(&cls->subtables, subtable, max_priority);
}
-
- cls->n_rules--;
-
+free:
ovsrcu_postpone(free, cls_match);
- CONST_CAST(struct cls_rule *, rule)->cls_match = NULL;
+ cls->n_rules--;
unlock:
ovs_mutex_unlock(&cls->mutex);
@@ -1359,112 +1476,6 @@ find_equal(const struct cls_subtable *subtable, const
struct miniflow *flow,
}
return NULL;
}
-
-/*
- * As the readers are operating concurrently with the modifications, a
- * concurrent reader may or may not see the new rule, depending on how
- * the concurrent events overlap with each other. This is no
- * different from the former locked behavior, but there the visibility
- * of the new rule only depended on the timing of the locking
- * functions.
- *
- * The new rule is first added to the segment indices, so the 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 by forthcoming revalidation always
- * scheduled after flow table changes.
- *
- * Similar behavior may happen due to us removing the overlapping rule
- * (if any) from the indices only after the new rule has been added.
- *
- * The subtable's max priority is updated only after the rule is
- * inserted, so the concurrent readers may not see the rule, as the
- * updated priority ordered subtable list will only be visible after
- * the subtable's max priority is updated.
- *
- * Similarly, the classifier's partitions for new rules are updated by
- * the caller after this function, so the readers may keep skipping
- * the subtable until they see the updated partitions.
- */
-static struct cls_match *
-insert_rule(struct classifier *cls, struct cls_subtable *subtable,
- struct cls_rule *new_rule)
- OVS_REQUIRES(cls->mutex)
-{
- struct cls_match *old = NULL;
- struct cls_match *new = cls_match_alloc(new_rule);
- struct cls_match *head;
- int i;
- uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES];
- uint8_t prev_be32ofs = 0;
-
- /* Add new node to segment indices. */
- for (i = 0; i < subtable->n_indices; i++) {
- ihash[i] = minimatch_hash_range(&new_rule->match, prev_be32ofs,
- subtable->index_ofs[i], &basis);
- cmap_insert(&subtable->indices[i], &new->index_nodes[i], ihash[i]);
- prev_be32ofs = subtable->index_ofs[i];
- }
- hash = minimatch_hash_range(&new_rule->match, prev_be32ofs, FLOW_U32S,
- &basis);
- head = find_equal(subtable, &new_rule->match.flow, hash);
- if (!head) {
- cmap_insert(&subtable->rules, &new->cmap_node, hash);
- rculist_init(&new->list);
- goto out;
- } else {
- /* Scan the list for the insertion point that will keep the list in
- * order of decreasing priority. */
- struct cls_match *rule;
-
- FOR_EACH_RULE_IN_LIST_PROTECTED (rule, head) {
- if (new->priority >= rule->priority) {
- if (rule == head) {
- /* 'new' is the new highest-priority flow in the list. */
- cmap_replace(&subtable->rules, &rule->cmap_node,
- &new->cmap_node, hash);
- }
-
- if (new->priority == rule->priority) {
- rculist_replace(&new->list, &rule->list);
- old = rule;
- } else {
- rculist_insert(&rule->list, &new->list);
- }
- goto out;
- }
- }
-
- /* Insert 'new' at the end of the list. */
- rculist_push_back(&head->list, &new->list);
- }
-
- out:
- if (!old) {
- subtable->n_rules++;
-
- /* Rule was added, not replaced. Update 'subtable's 'max_priority'
- * and 'max_count', if necessary. */
- if (subtable->n_rules == 1) {
- subtable->max_priority = new->priority;
- subtable->max_count = 1;
- pvector_insert(&cls->subtables, subtable, new->priority);
- } else if (subtable->max_priority == new->priority) {
- ++subtable->max_count;
- } else if (new->priority > subtable->max_priority) {
- subtable->max_priority = new->priority;
- subtable->max_count = 1;
- pvector_change_priority(&cls->subtables, subtable, new->priority);
- }
- } else {
- /* Remove old node from indices. */
- for (i = 0; i < subtable->n_indices; i++) {
- cmap_remove(&subtable->indices[i], &old->index_nodes[i], ihash[i]);
- }
- }
- return old;
-}
/* A longest-prefix match tree. */
diff --git a/lib/rculist.h b/lib/rculist.h
index 2e926de..f597d84 100644
--- a/lib/rculist.h
+++ b/lib/rculist.h
@@ -250,7 +250,8 @@ rculist_move(struct rculist *dst, struct rculist *src)
}
/* Removes 'elem' from its list and returns the element that followed it.
- * Undefined behavior if 'elem' is not in a list.
+ * Has no effect when 'elem' is initialized, but not in a list.
+ * Undefined behavior if 'elem' is not initialized.
*
* Afterward, 'elem' is not linked to from the list any more, but still links
* to the nodes in the list, and may still be referenced by other threads until
@@ -318,16 +319,12 @@ rculist_front(const struct rculist *list)
}
/* Returns the back element in 'list_'.
- * Undefined behavior if 'list_' is empty. */
+ * Returns the 'list_' itself, if 'list_' is empty. */
static inline struct rculist *
-rculist_back_protected(const struct rculist *list_)
+rculist_back_protected(const struct rculist *list)
OVS_NO_THREAD_SAFETY_ANALYSIS
{
- struct rculist *list = CONST_CAST(struct rculist *, list_);
-
- ovs_assert(!rculist_is_empty(list));
-
- return list->prev;
+ return CONST_CAST(struct rculist *, list)->prev;
}
/* Returns the number of elements in 'list'.
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
index 2848d01..d42de06 100644
--- a/tests/test-classifier.c
+++ b/tests/test-classifier.c
@@ -546,7 +546,7 @@ check_tables(const struct classifier *cls, int n_tables,
int n_rules,
ovs_mutex_lock(&cls->mutex);
assert(trie_verify(&table->ports_trie, 0, table->ports_mask_len)
- == (table->ports_mask_len ? table->n_rules : 0));
+ == (table->ports_mask_len ? cmap_count(&table->rules) : 0));
ovs_mutex_unlock(&cls->mutex);
found_tables++;
--
1.7.10.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
