Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com> --- lib/classifier.h | 63 +++++++++++++++++++++++++++++++++++------------------- 1 file changed, 41 insertions(+), 22 deletions(-)
diff --git a/lib/classifier.h b/lib/classifier.h index 2798752..f41fed3 100644 --- a/lib/classifier.h +++ b/lib/classifier.h @@ -227,24 +227,25 @@ * in a way to not remove the rule before all ongoing lookups are finished, the * rule should be marked as "to be deleted" by setting the rule's visibility to * the negation of the last version number in which it should be visible. - * Then, when all the lookups use that future version number, the rule can be - * actually deleted from the classifier. A rule that is marked for deletion in - * a future version will not appear in iterations, although it will still be - * found by lookups using an earlier lookup version number. + * Then, when all the lookups use a later version number, the rule can be + * actually deleted from the classifier. A rule that is marked for deletion + * after a future version will not appear in iterations, although it will still + * be found by lookups using a lookup version number up to that future version + * number. * * Classifiers can hold duplicate rules (rules with the same match criteria and - * priority) when at most one of the duplicates is visible in any given lookup - * version. The caller responsible for classifier modifications must maintain - * this invariant. + * priority) when at most one of the duplicates with the same priority is + * visible in any given lookup version. The caller responsible for classifier + * modifications must maintain this invariant. * * The classifier supports versioning for two reasons: * - * 1. Support for versioned modifications makes it possible to support - * an arbitraty series of classifier changes as one atomic transaction, + * 1. Support for versioned modifications makes it possible to perform an + * arbitraty series of classifier changes as one atomic transaction, * where intermediate versions of the classifier are not visible to any * lookups. Also, when a rule is added for a future version, or marked - * for removal in a future version, such modifications can be reverted - * without any visible effects to any of the current lookup versions. + * for removal after the current version, such modifications can be + * reverted without any visible effects to any of the current lookups. * * 2. Performance: Adding (or deleting) a large set of rules can, in * pathological cases, have a cost proportional to the number of rules @@ -253,23 +254,28 @@ * typically avoided, as long as it is OK for any new rules to be * invisible until the batch change is complete. * + * Note that the classifier_replace() function replaces a rule immediately, and + * is therefore not safe to use with versioning. It is still available for the + * users that do not use versioning. + * * * Deferred Publication * ==================== * * Removing large number of rules from classifier can be costly, as the - * supporting data structures are teared down, just to be re-instantiated right - * after. In the worst case, as when each rule has a different match pattern - * (mask), the maintenance of the match pattern can have cost O(N^2), where N - * is the number of different match patterns. To alleviate this, the - * classifier supports a "deferred mode", in which changes in internal data - * structures used for lookups may not be fully computed yet. The computation - * is finalized when the deferred mode is turned off. + * supporting data structures are teared down, in many cases just to be + * re-instantiated right after. In the worst case, as when each rule has a + * different match pattern (mask), the maintenance of the match patterns can + * have cost O(N^2), where N is the number of different match patterns. To + * alleviate this, the classifier supports a "deferred mode", in which changes + * in internal data structures needed for future version lookups may not be + * fully computed yet. The computation is finalized when the deferred mode is + * turned off. * * This feature can be used with versioning such that all changes to future - * versions are made in the deferred mode. Then, right before making the new + * versions are made in the deferred mode. Then, right before making the new * version visible to lookups, the deferred mode is turned off so that all the - * data structures are ready for lookups. + * data structures are ready for lookups with the new version number. * * To use deferred publication, first call classifier_defer(). Then, modify * the classifier via additions (classifier_insert() with a specific, future @@ -281,8 +287,21 @@ * Thread-safety * ============= * - * The classifier may safely be accessed by many reader threads concurrently or - * by a single writer. */ + * The classifier may safely be accessed by many reader threads concurrently + * and by a single writer, or by multiple writers when they guarantee mutually + * exlucive access to classifier modifications. + * + * Since the classifier rules are RCU protected, the rule destruction after + * removal from the classifier must be RCU postponed. Also, when versioning is + * used, the rule removal itself needs to be typically RCU postponed. In this + * case the rule destruction is doubly RCU postponed, i.e., the second + * ovsrcu_postpone() call to destruct the rule is called from the first RCU + * callback that removes the rule. + * + * Rules that have never been visible to lookups are an exeption to the above + * rule. Such rules can be removed immediately, but their destruction must + * still be RCU postponed, as the rule's visibility attribute may be examined + * parallel to the rule's removal. */ #include "cmap.h" #include "match.h" -- 1.7.10.4 _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
