On Mon, May 18, 2015 at 04:10:14PM -0700, Jarno Rajahalme wrote:
> OpenFlow 1.4 bundles are easier to implement when it is possible to
> mark a rule as 'to_be_removed' and then insert a new, identical rule
> with the same priority.
>
> All but one out of the identical rules must be marked as
> 'to_be_removed', and the one rule that is not 'to_be_removed' must
> have been inserted last.
>
> Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
I find myself wondering whether there should be a function to set
->to_be_removed, since clients aren't otherwise supposed to mess around
with a cls_rule once it's initialized.
I hope that some tests for these new features are forthcoming. They are
tricky.
Here's an idea for better comments. It should supplant the ones from
the previous patch. I'm not entirely happy with them, because the
rationale and the use cases are complicated.
diff --git a/lib/classifier.h b/lib/classifier.h
index 50cc9f8..b9b753a 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -126,9 +126,12 @@
* cls_subtable", with the other almost-identical rules chained off a linked
* list inside that highest-priority rule.
*
+ * The following sub-sections describe various optimizations over this simple
+ * approach.
+ *
*
* Staged Lookup (Wildcard Optimization)
- * =====================================
+ * -------------------------------------
*
* Subtable lookup is performed in ranges defined for struct flow, starting
* from metadata (registers, in_port, etc.), then L2 header, L3, and finally
@@ -141,7 +144,7 @@
*
*
* Prefix Tracking (Wildcard Optimization)
- * =======================================
+ * ---------------------------------------
*
* Classifier uses prefix trees ("tries") for tracking the used
* address space, enabling skipping classifier tables containing
@@ -171,7 +174,7 @@
*
*
* Partitioning (Lookup Time and Wildcard Optimization)
- * ====================================================
+ * ----------------------------------------------------
*
* Suppose that a given classifier is being used to handle multiple stages in a
* pipeline using "resubmit", with metadata (that is, the OpenFlow 1.1+ field
@@ -207,6 +210,41 @@
* Each eliminated subtable lookup also reduces the amount of un-wildcarding.
*
*
+ * Tentative Modifications
+ * =======================
+ *
+ * When a new rule is added to a classifier, it can optionally be "invisible".
+ * That means that lookups won't find the rule, although iterations through
+ * the classifier will still see it.
+ *
+ * Similarly, deletions from a classifier can be "tentative", by setting
+ * 'to_be_removed' to true within the rule. A rule that is tentatively deleted
+ * will not appear in iterations, although it will still be found by lookups.
+ *
+ * Classifiers can hold duplicate rules (rules with the same match criteria and
+ * priority) when tentative modifications are involved: one (or more) identical
+ * tentatively deleted rules can coexist in a classifier with at most one
+ * identical invisible rule.
+ *
+ * The classifier supports tentative modifications for two reasons:
+ *
+ * 1. Performance: Adding (or deleting) a rule can, in pathological cases,
+ * have a cost proportional to the number of rules already in the
+ * classifier. When multiple rules are being added (or deleted) in one
+ * go, though, this cost can be paid just once, not once per addition
+ * (or deletion), as long as it is OK for any new rules to be invisible
+ * until the batch change is complete.
+ *
+ * 2. Staging additions and deletions: Invisibility allows a rule to be
+ * added tentatively, to possibly be modified or removed before it
+ * becomes visible. Tentatively deletion allows a rule to be scheduled
+ * for deletion before it is certain that the deletion is desirable.
+ *
+ * To use deferred publication, first call classifier_defer(). Then, modify
+ * the classifier via additions and deletions. Call cls_rule_make_visible() on
+ * each new rule at an appropriate time. Finally, call classifier_publish().
+ *
+ *
* Thread-safety
* =============
*
Acked-by: Ben Pfaff <b...@nicira.com>
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
