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

[antonio.fischetti at intel.com]

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