[ovs-dev] [PATCH] classifier: Documentation clarifications.

[Jarno Rajahalme]

This applies after the bundles v3 series patch 07/12.

  Jarno

> On Jun 6, 2015, at 12:48 PM, Jarno Rajahalme <jrajahalme at nicira.com> wrote:
> 
> Signed-off-by: Jarno Rajahalme <jrajahalme at 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
>