[ovs-dev] [PATCH v4 04/12] classifier: Make traversing identical rules robust.

Ben Pfaff blp at nicira.com
Wed Jun 10 23:36:07 UTC 2015


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...?

> 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 <jrajahalme at 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?).

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. */

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.

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));

Acked-by: Ben Pfaff <blp at nicira.com>



More information about the dev mailing list