Acked-by: Jarno Rajahalme <ja...@ovn.org> Pushed to master with a rebase and minor edits.
Jarno > On Aug 5, 2016, at 6:40 AM, antonio.fische...@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.fische...@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 > _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev