[ovs-dev] [PATCH] dpcls_lookup: added comments.

Jarno Rajahalme jarno at ovn.org
Fri Aug 5 20:58:01 UTC 2016


Acked-by: Jarno Rajahalme <jarno at ovn.org>

Pushed to master with a rebase and minor edits.

  Jarno


> On Aug 5, 2016, at 6:40 AM, antonio.fischetti at intel.com wrote:
> 
> This patch adds some comments to the dpcls_lookup() funtion,
> which is one of the most important places where the Userspace
> wildcard matching happens.
> The purpose is to give some more explanations on its design
> and also on how it works.
> 
> Signed-off-by: Antonio Fischetti <antonio.fischetti at intel.com>
> ---
> lib/dpif-netdev.c | 40 ++++++++++++++++++++++++++++++++++------
> 1 file changed, 34 insertions(+), 6 deletions(-)
> 
> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
> index e0107b7..a390758 100644
> --- a/lib/dpif-netdev.c
> +++ b/lib/dpif-netdev.c
> @@ -4492,8 +4492,8 @@ dpcls_rule_matches_key(const struct dpcls_rule *rule,
>     return true;
> }
> 
> -/* For each miniflow in 'flows' performs a classifier lookup writing the result
> - * into the corresponding slot in 'rules'.  If a particular entry in 'flows' is
> +/* For each miniflow in 'keys' performs a classifier lookup writing the result
> + * into the corresponding slot in 'rules'.  If a particular entry in 'keys' is
>  * NULL it is skipped.
>  *
>  * This function is optimized for use in the userspace datapath and therefore
> @@ -4501,12 +4501,15 @@ dpcls_rule_matches_key(const struct dpcls_rule *rule,
>  * classifier_lookup() function.  Specifically, it does not implement
>  * priorities, instead returning any rule which matches the flow.
>  *
> - * Returns true if all flows found a corresponding rule. */
> + * Returns true if all miniflows found a corresponding rule. */
> static bool
> dpcls_lookup(const struct dpcls *cls, const struct netdev_flow_key keys[],
>              struct dpcls_rule **rules, const size_t cnt)
> {
> -    /* The batch size 16 was experimentally found faster than 8 or 32. */
> +    /* The received 'cnt' miniflows are the search-keys that will be processed
> +     * in batches of 16 elements.  N_MAPS will contain the number of these
> +     * 16-elements batches.  i.e. for 'cnt'=32, N_MAPS shall be 2.
> +     * The batch size 16 was experimentally found faster than 8 or 32. */
>     typedef uint16_t map_type;
> #define MAP_BITS (sizeof(map_type) * CHAR_BIT)
> 
> @@ -4524,6 +4527,16 @@ dpcls_lookup(const struct dpcls *cls, const struct netdev_flow_key keys[],
>     }
>     memset(rules, 0, cnt * sizeof *rules);
> 
> +    /* The Datapath classifier - aka dpcls - is composed of subtables.
> +     * They are dynamically created depending on the new rules we need to
> +     * cache.
> +     * Each subtable collects rules with a certain subset of packet fields and
> +     * with a given unique mask.
> +     * We need to process every search-key against each subtable.
> +     * When an entry is found the search can stop because rules are
> +     * non-overlapping by nature.
> +     * The next macro loops on the current subtables listed into the
> +     * 'cls->subtables' pvector. */
>     PVECTOR_FOR_EACH (subtable, &cls->subtables) {
>         const struct netdev_flow_key *mkeys = keys;
>         struct dpcls_rule **mrules = rules;
> @@ -4532,6 +4545,7 @@ dpcls_lookup(const struct dpcls *cls, const struct netdev_flow_key keys[],
> 
>         BUILD_ASSERT_DECL(sizeof remains == sizeof *maps);
> 
> +        /* Loops on each batch of 16 search-keys. */
>         for (m = 0; m < N_MAPS; m++, mkeys += MAP_BITS, mrules += MAP_BITS) {
>             uint32_t hashes[MAP_BITS];
>             const struct cmap_node *nodes[MAP_BITS];
> @@ -4542,14 +4556,25 @@ dpcls_lookup(const struct dpcls *cls, const struct netdev_flow_key keys[],
>                 continue; /* Skip empty maps. */
>             }
> 
> -            /* Compute hashes for the remaining keys. */
> +            /* Compute hashes for the remaining keys.
> +             * Beside the search-key we need to pass also the specific mask
> +             * of the current subtable, because we are using Hash tables for
> +             * a wildcard match.
> +             * The mask will be applied to the search-key before computing the
> +             * Hash value. */
>             ULLONG_FOR_EACH_1(i, map) {
>                 hashes[i] = netdev_flow_key_hash_in_mask(&mkeys[i],
>                                                          &subtable->mask);
>             }
>             /* Lookup. */
>             map = cmap_find_batch(&subtable->rules, map, hashes, nodes);
> -            /* Check results. */
> +            /* Check results.
> +             * When the i-th bit of map is set, it means that a Hash entry
> +             * was found for the i-th search-key.  Considering how Hash
> +             * mechanism works, we still need to check that the found entry
> +             * really matches our masked search-key.  Otherwise we will loop on
> +             * the linked nodes - which will be present if any collision
> +             * occurred - to repeat the check for a match. */
>             ULLONG_FOR_EACH_1(i, map) {
>                 struct dpcls_rule *rule;
> 
> @@ -4559,6 +4584,9 @@ dpcls_lookup(const struct dpcls *cls, const struct netdev_flow_key keys[],
>                         goto next;
>                     }
>                 }
> +                /* The search did find an entry but none of the linked nodes
> +                 * could match our masked search-key.  By resetting the i-th
> +                 * bit we will trigger a new search on the next subtable. */
>                 ULLONG_SET0(map, i);  /* Did not match. */
>             next:
>                 ;                     /* Keep Sparse happy. */
> -- 
> 2.4.11
> 




More information about the dev mailing list