> On Jun 10, 2015, at 4:36 PM, Ben Pfaff <b...@nicira.com> wrote:
>
> On Tue, Jun 09, 2015 at 05:24:11PM -0700, Jarno Rajahalme wrote:
>> The traversal of the list of identical rules from the lookup threads
>> is fragile in the list head is removed during the list traversal.
>
> fragile "if" the list head…?
Fixed.
>> This patch simplifies the implementation of that list by making the
>> list NULL terminated, singly linked RCU-protected list. By having the
>> NULL at the end there is no longer a possiblity of missing the point
>> when the list wraps around. This is significant when there can be
>> multiple elements with the same priority in the list.
>>
>> This change also decreases the size of the struct cls_match back
>> pre-'visibility' attribute size.
>>
>> Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
>
> The comment on cls_match_remove() seems somewhat inconsistent with the
> implementation. The comment says:
>
> ...If 'prev' is NULL, then the 'rule' is a list head, and the 'rule'
> is only poisoned after all threads have quiesced.
>
> which to my mind says that when (whether?) 'rule' is poisoned depends on
> whether it is a list head. But the implementation does a postponed
> poison regardless of whether it is a list head. (However, in practice,
> cls_match_remove()'s only caller never passes it a list head.)
>
> Here is a suggestion for a comment improvement. While I was writing it,
> though, it came to mind that it while it says that the list is sorted by
> priority, it doesn't say how it is sort by version (is it?).
>
The is list is first sorted by decreasing priority, and equal priority rules
are in practice sorted by cls_rule->version, even though we never actually use
the cls_rule->version when inserting in to the list:
- Lookups rely on the invariant that at most one of the duplicates is visible
in their version, so they stop at highest priority match that is visible to
them.
- Since all rules that have not been marked for removal in any version are
visible in version CLS_MAX_VERSION, at most one of the otherwise duplicate
rules may be not marked for removal.
- We always insert a new rule after rules of equal priority that have not been
marked for removal to find the potentially displaced rule.
- It follows that the rule not marked for removal (if any) is always the last
of the identical rules with the same priority.
- It further follows that since the tables version number is monotonically
increasing, the duplicate rules with the same priority in the list are in
increasing version order.
- The version number is in the cls_rule, not in cls_match, and is not
actually considered by cls_match.
The later patch adding versioned testing to test-classifier verifies this.
While looking into clarifying this I found that in some rather improbable but
still theoretically possible cases we need to consider the original version
value (cls_rule->version) in the visibility check as well. I’ll introduce a
separate patch that adds this to cls_match as well, and simplifies the details
quite a bit.
> diff --git a/lib/classifier-private.h b/lib/classifier-private.h
> index 01b31e0..9ebb52f 100644
> --- a/lib/classifier-private.h
> +++ b/lib/classifier-private.h
> @@ -65,14 +65,16 @@ struct cls_partition {
> struct tag_tracker tracker; /* Tracks the bits in 'tags'. */
> };
>
> -/* Internal representation of a rule in a "struct cls_subtable". */
> +/* Internal representation of a rule in a "struct cls_subtable".
> + *
> + * The 'next' member is an element in a singly linked, null-terminated list.
> + * This list links together identical "cls_match"es in order of decreasing
> + * priority. The classifier code maintains the invariant that at most one
> rule
> + * of a given priority is visible for any given lookup version.
> + */
> struct cls_match {
> /* Accessed by everybody. */
> - OVSRCU_TYPE(struct cls_match *) next; /* Identical "cls_match"es in the
> - * order of decreasing priority.
> At
> - * most one rule of a given
> priority
> - * may be visible to any given
> lookup
> - * version. */
> + OVSRCU_TYPE(struct cls_match *) next; /* Equal, lower-priority matches.
> */
> OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
>
> /* Accessed only by writers. */
>
Applied.
> This code reminds me of my favorite idiom for singly linked lists, which
> is to iterate using a pointer-to-pointer rather than a single pointer.
> That way you can use a single variable instead of two of them, which
> sometimes seems cleaner. Like this:
>
> struct slist {
> struct list *next;
> } *head;
>
> ...
>
> for (struct slist *iter = &head; *head != NULL; head = &(*head)->next) {
> ...work with *iter or assign to temporary variable...
> }
>
> The nice thing about this is that it's very clean to insert before the
> current position, without any conditionals, e.g.:
>
> new_item->next = (*iter)->next;
> *iter = new_item;
>
> or to remove the item at the current position:
>
> struct slist *victim = *iter;
> *iter = (*iter)->next;
> free(victim);
>
> Dunno if this idiom makes any code cleaner here; up to you.
>
I’ll leave this for a future exercise, maybe it will be useful also elsewhere
to have a generic singly linked RCU list.
> In next_visible_rule_in_list(),
> do {
> rule = cls_match_next(rule);
> if (!rule) {
> /* We have reached the head of the list, stop. */
> break;
> }
> } while (!cls_match_visible_in_version(rule, version));
> could use the "while" clause more completely:
> do {
> rule = cls_match_next(rule);
> } while (rule && !cls_match_visible_in_version(rule, version));
How did I not see this? Thanks!
I removed the postponed poisoning for the same reason we are doing it for the
rculist, so I applied this to master with the following incremental:
---
lib/classifier-private.h | 71 ++++++++++++++++++----------------------------
lib/classifier.c | 7 +++--
2 files changed, 31 insertions(+), 47 deletions(-)
diff --git a/lib/classifier-private.h b/lib/classifier-private.h
index 0f982ad..a540371 100644
--- a/lib/classifier-private.h
+++ b/lib/classifier-private.h
@@ -65,14 +65,16 @@ struct cls_partition {
struct tag_tracker tracker; /* Tracks the bits in 'tags'. */
};
-/* Internal representation of a rule in a "struct cls_subtable". */
+/* Internal representation of a rule in a "struct cls_subtable".
+ *
+ * The 'next' member is an element in a singly linked, null-terminated list.
+ * This list links together identical "cls_match"es in order of decreasing
+ * priority. The classifier code maintains the invariant that at most one rule
+ * of a given priority is visible for any given lookup version.
+ */
struct cls_match {
/* Accessed by everybody. */
- OVSRCU_TYPE(struct cls_match *) next; /* Identical "cls_match"es in the
- * order of decreasing priority. At
- * most one rule of a given priority
- * may be visible to any given lookup
- * version. */
+ OVSRCU_TYPE(struct cls_match *) next; /* Equal, lower-priority matches. */
OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
/* Accessed only by writers. */
@@ -104,6 +106,9 @@ struct cls_match {
/* 'flow' must be the last field. */
};
+/* Must be RCU postponed. */
+void cls_match_free_cb(struct cls_match *);
+
static inline void
cls_match_set_visibility(struct cls_match *rule, long long version)
{
@@ -155,56 +160,39 @@ cls_match_next_protected(const struct cls_match *rule)
return ovsrcu_get_protected(struct cls_match *, &rule->next);
}
-/* Puts 'rule' in the position between 'prev' and 'next'. If 'prev' == NULL,
+/* Puts 'rule' in the position between 'prev' and 'next'. If 'prev' == NULL,
* then the 'rule' is the new list head, and if 'next' == NULL, the rule is the
- * new list tail. */
+ * new list tail.
+ * If there are any nodes between 'prev' and 'next', they are dropped from the
+ * list. */
static inline void
cls_match_insert(struct cls_match *prev, struct cls_match *next,
struct cls_match *rule)
{
- if (!prev) {
- /* 'rule' is the new head. */
- ovsrcu_set_hidden(&rule->next, next);
- } else {
- /* 'rule' is new node after 'prev' */
- ovsrcu_set_hidden(&rule->next, cls_match_next_protected(prev));
+ ovsrcu_set_hidden(&rule->next, next);
+
+ if (prev) {
ovsrcu_set(&prev->next, rule);
}
}
-void cls_match_poison(struct cls_match *);
-
/* Puts 'new_rule' in the position of 'old_rule', which is the next node after
- * 'prev'. If 'prev' == NULL, then the 'rule' is the new list head.
+ * 'prev'. If 'prev' == NULL, then the 'new_rule' is the new list head.
*
- * Returns the replaced cls_match, which is not linked to any more, but still
- * links to the later rules, and may still be referenced by other threads until
- * all other threads quiesce. The returned rule may not be re-inserted,
- * re-initialized, or deleted until after all other threads have quiesced (use
- * ovsrcu_postpone). */
+ * The replaced cls_match still links to the later rules, and may still be
+ * referenced by other threads until all other threads quiesce. The replaced
+ * rule may not be re-inserted, re-initialized, or deleted until after all
+ * other threads have quiesced (use ovsrcu_postpone). */
static inline void
cls_match_replace(struct cls_match *prev,
struct cls_match *old_rule, struct cls_match *new_rule)
{
- if (prev == NULL) {
- /* 'new_rule' replaces the old head. */
- ovsrcu_set_hidden(&new_rule->next, cls_match_next_protected(old_rule));
- } else {
- /* 'new_rule' replaces an existing non-head node. */
- struct cls_match *next = cls_match_next_protected(old_rule);
-
- ovsrcu_set_hidden(&new_rule->next, next);
- ovsrcu_set(&prev->next, new_rule);
- }
-
-#ifndef NDEBUG
- ovsrcu_postpone(cls_match_poison, old_rule);
-#endif
+ cls_match_insert(prev, cls_match_next_protected(old_rule), new_rule);
}
/* Removes 'rule' following 'prev' from the list. If 'prev' is NULL, then the
- * 'rule' is a list head, and the 'rule' is only poisoned after all threads
- * have quiesced.
+ * 'rule' is a list head, and the caller is responsible for maintaining its
+ * list head pointer (if any).
*
* Afterward, the removed rule is not linked to any more, but still links to
* the following rules, and may still be referenced by other threads until all
@@ -216,13 +204,8 @@ static inline void
cls_match_remove(struct cls_match *prev, struct cls_match *rule)
{
if (prev) {
- struct cls_match *next = cls_match_next_protected(rule);
-
- ovsrcu_set(&prev->next, next);
+ ovsrcu_set(&prev->next, cls_match_next_protected(rule));
}
-#ifndef NDEBUG
- ovsrcu_postpone(cls_match_poison, rule);
-#endif
}
#define CLS_MATCH_FOR_EACH(ITER, HEAD) \
diff --git a/lib/classifier.c b/lib/classifier.c
index fad384c..28121bf 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -719,7 +719,7 @@ classifier_replace(struct classifier *cls, const struct
cls_rule *rule,
ovsrcu_postpone(free, conj_set);
}
- ovsrcu_postpone(free, iter);
+ ovsrcu_postpone(cls_match_free_cb, iter);
old->cls_match = NULL;
/* No change in subtable's max priority or max count. */
@@ -925,7 +925,7 @@ check_priority:
if (conj_set) {
ovsrcu_postpone(free, conj_set);
}
- ovsrcu_postpone(free, rule);
+ ovsrcu_postpone(cls_match_free_cb, rule);
cls->n_rules--;
return cls_rule;
@@ -2364,7 +2364,8 @@ trie_remove_prefix(rcu_trie_ptr *root, const ovs_be32
*prefix, int mlen)
#define CLS_MATCH_POISON (struct cls_match *)(UINTPTR_MAX / 0xf * 0xb)
void
-cls_match_poison(struct cls_match *rule)
+cls_match_free_cb(struct cls_match *rule)
{
ovsrcu_set_hidden(&rule->next, CLS_MATCH_POISON);
+ free(rule);
}
>
> Acked-by: Ben Pfaff <b...@nicira.com>
Thanks, pushed to master,
Jarno
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
