[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