On Tue, Nov 11, 2014 at 04:46:10PM -0800, Ben Pfaff wrote:
> On Tue, Nov 11, 2014 at 12:00:59PM -0800, Jarno Rajahalme wrote:
> > 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>
>
> I don't understand from the commit message above whether this just
> moves code around or actually changes what it does. It's usually easy
> to review a patch that moves code around, it's usually easy to review
> a patch that just changes code, but a patch that does both at once is
> harder, and I'm not sure which I'm looking at here. Let me know?
I see that it does both at once.
How about the following as a preliminary commit that just does the
integration work?
--8<--------------------------cut here-------------------------->8--
From: Ben Pfaff <b...@nicira.com>
Date: Wed, 12 Nov 2014 13:05:35 -0800
Subject: [PATCH] classifier: Integrate insert_rule() into
classifier_replace().
insert_rule() only had one caller and this makes the code easier to
understand.
Signed-off-by: Ben Pfaff <b...@nicira.com>
---
lib/classifier.c | 210 ++++++++++++++++++++++++++-----------------------------
1 file changed, 98 insertions(+), 112 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index c19d81c..8617a08 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -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 *,
@@ -478,14 +475,22 @@ static inline ovs_be32 minimatch_get_ports(const struct
minimatch *match)
* 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.
+ */
const struct cls_rule *
classifier_replace(struct classifier *cls, struct cls_rule *rule)
OVS_EXCLUDED(cls->mutex)
{
- struct cls_match *old_rule;
+ struct cls_match *new = cls_match_alloc(rule);
+ struct cls_match *old_rule = NULL;
struct cls_subtable *subtable;
const struct cls_rule *old_cls_rule = NULL;
+ uint32_t ihash[CLS_MAX_INDICES];
+ uint8_t prev_be32ofs = 0;
+ struct cls_match *head;
+ uint32_t basis;
+ uint32_t hash;
+ int i;
ovs_mutex_lock(&cls->mutex);
subtable = find_subtable(cls, &rule->match.mask);
@@ -493,10 +498,80 @@ classifier_replace(struct classifier *cls, struct
cls_rule *rule)
subtable = insert_subtable(cls, &rule->match.mask);
}
- old_rule = insert_rule(cls, subtable, rule);
+
+ /* 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). */
+ basis = 0;
+ for (i = 0; i < subtable->n_indices; i++) {
+ ihash[i] = minimatch_hash_range(&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(&rule->match, prev_be32ofs, FLOW_U32S,
+ &basis);
+ head = find_equal(subtable, &rule->match.flow, hash);
+ if (!head) {
+ cmap_insert(&subtable->rules, &new->cmap_node, hash);
+ rculist_init(&new->list);
+ } else {
+ /* Scan the list for the insertion point that will keep the list in
+ * order of decreasing priority. */
+ struct cls_match *iter;
+
+ FOR_EACH_RULE_IN_LIST_PROTECTED (iter, head) {
+ if (new->priority >= iter->priority) {
+ if (iter == head) {
+ /* 'new' is the new highest-priority flow in the list. */
+ cmap_replace(&subtable->rules, &iter->cmap_node,
+ &new->cmap_node, hash);
+ }
+
+ if (new->priority == iter->priority) {
+ rculist_replace(&new->list, &iter->list);
+ old_rule = iter;
+ } else {
+ rculist_insert(&iter->list, &new->list);
+ }
+ goto out;
+ }
+ }
+
+ /* Insert 'new' at the end of the list. */
+ rculist_push_back(&head->list, &new->list);
+ out:;
+ }
+
if (!old_rule) {
old_cls_rule = NULL;
+ subtable->n_rules++;
+
+ /* Rule was added, not replaced. Update 'subtable's 'max_priority'
+ * and 'max_count', if necessary.
+ *
+ * The rule was already inserted, so concurrent readers may not see the
+ * rule. This will have to be fixed by revalidation later. */
+ 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);
+ }
+ /* Add rule to partitions.
+ *
+ * Concurrent readers might miss seeing the rule until this update,
+ * which might require being fixed up by revalidation later. */
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);
@@ -506,13 +581,17 @@ classifier_replace(struct classifier *cls, struct
cls_rule *rule)
cls->n_rules++;
+ /* Add rule to tries.
+ *
+ * Concurrent readers might miss seeing the rule until this update,
+ * which might require being fixed up by revalidation later. */
for (int i = 0; i < cls->n_tries; i++) {
if (subtable->trie_plen[i]) {
trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]);
}
}
- /* Ports trie. */
+ /* Add rule to ports trie. */
if (subtable->ports_mask_len) {
/* We mask the value to be inserted to always have the wildcarded
* bits in known (zero) state, so we can include them in comparison
@@ -525,6 +604,17 @@ classifier_replace(struct classifier *cls, struct cls_rule
*rule)
}
} else {
old_cls_rule = old_rule->cls_rule;
+
+ /* Remove old node from indices.
+ *
+ * The effect of this late removal on concurrency is similar to that of
+ * adding the new rule to the segment indices early (at the beginning
+ * of this function.) */
+ for (i = 0; i < subtable->n_indices; i++) {
+ cmap_remove(&subtable->indices[i], &old_rule->index_nodes[i],
+ ihash[i]);
+ }
+
rule->cls_match->partition = old_rule->partition;
CONST_CAST(struct cls_rule *, old_cls_rule)->cls_match = NULL;
@@ -532,6 +622,7 @@ classifier_replace(struct classifier *cls, struct cls_rule
*rule)
* immediately. */
ovsrcu_postpone(free, old_rule);
}
+
ovs_mutex_unlock(&cls->mutex);
return old_cls_rule;
}
@@ -1360,111 +1451,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. */
--
2.1.1
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
