| Message ID | 20190508151321.39231-2-harry.van.haaren@intel.com |
|---|---|
| State | Superseded |
| Headers | show |
| Series | dpcls func ptrs & optimizations | expand |
On 5/8/2019 4:13 PM, Harry van Haaren wrote: > This allows plugging-in of different subtable hash-lookup-verify > routines, and allows special casing of those functions based on > known context (eg: # of bits set) of the specific subtable. > > Signed-off-by: Harry van Haaren <harry.van.haaren@intel.com> > > --- > > v9: > - Use count_1bits in favour of __builtin_popcount (Ilya) > > v6: > - Implement subtable effort per packet "lookups_match" counter (Ilya) > - Remove double newline (Eelco) > - Remove doubel * before comments (Eelco) > - Reword comments in dpcls_lookup() for clarity (Harry) > --- > lib/dpif-netdev.c | 135 +++++++++++++++++++++++++++++++--------------- > 1 file changed, 93 insertions(+), 42 deletions(-) > > diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c > index 5a6f2abac..e2e2c14e7 100644 > --- a/lib/dpif-netdev.c > +++ b/lib/dpif-netdev.c > @@ -7572,6 +7572,27 @@ dpif_dummy_register(enum dummy_level level) > > /* Datapath Classifier. */ > > +/* forward declaration for lookup_func typedef */ Minor nit above, general rule of thumb for comment style, start with capital letter and finish with period. > +struct dpcls_subtable; > + > +/* Lookup function for a subtable in the dpcls. This function is called > + * by each subtable with an array of packets, and a bitmask of packets to > + * perform the lookup on. Using a function pointer gives flexibility to > + * optimize the lookup function based on subtable properties and the > + * CPU instruction set available at runtime. > + */ > +typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable *subtable, > + uint32_t keys_map, const struct netdev_flow_key *keys[], > + struct dpcls_rule **rules); Alignment for the arguments above looks odd, typically arguments are kept vertically in line with one another *similar to dpcls_subtable_lookup_generic below). > + > +/* Prototype for generic lookup func, using same code path as before */ Period at end of comment above. > +uint32_t > +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, > + uint32_t keys_map, > + const struct netdev_flow_key *keys[], > + struct dpcls_rule **rules); > + > + > /* A set of rules that all have the same fields wildcarded. */ > struct dpcls_subtable { > /* The fields are only used by writers. */ > @@ -7581,6 +7602,13 @@ struct dpcls_subtable { > struct cmap rules; /* Contains "struct dpcls_rule"s. */ > uint32_t hit_cnt; /* Number of match hits in subtable in current > optimization interval. */ > + > + /* the lookup function to use for this subtable. If there is a known > + * property of the subtable (eg: only 3 bits of miniflow metadata is > + * used for the lookup) then this can point at an optimized version of > + * the lookup function for this particular subtable. */ the -> The above. > + dpcls_subtable_lookup_func lookup_func; > + > struct netdev_flow_key mask; /* Wildcards for fields (const). */ > /* 'mask' must be the last field, additional space is allocated here. */ > }; > @@ -7640,6 +7668,10 @@ dpcls_create_subtable(struct dpcls *cls, const struct netdev_flow_key *mask) > cmap_init(&subtable->rules); > subtable->hit_cnt = 0; > netdev_flow_key_clone(&subtable->mask, mask); > + > + /* decide which hash/lookup/verify function to use */ > + subtable->lookup_func = dpcls_subtable_lookup_generic; So by default dpcls_subtable_lookup_generic is set as the look up function. Makes sense as this is the only look up available at this stage. I assume it's later in the series a mechanism to select a different lookup is introduced. Or by default does the lookup always start off as the generic option when a subtable is created even when other options are possible? > + > cmap_insert(&cls->subtables_map, &subtable->cmap_node, mask->hash); > /* Add the new subtable at the end of the pvector (with no hits yet) */ > pvector_insert(&cls->subtables, subtable, 0); > @@ -7800,6 +7832,53 @@ dpcls_rule_matches_key(const struct dpcls_rule *rule, > return true; > } > > +uint32_t > +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, > + uint32_t keys_map, > + const struct netdev_flow_key *keys[], > + struct dpcls_rule **rules) > +{ > + int i; > + /* Compute hashes for the remaining keys. Each search-key is > + * masked with the subtable's mask to avoid hashing the wildcarded > + * bits. */ > + uint32_t hashes[NETDEV_MAX_BURST]; > + ULLONG_FOR_EACH_1(i, keys_map) { > + hashes[i] = netdev_flow_key_hash_in_mask(keys[i], > + &subtable->mask); > + } > + > + /* Lookup. */ > + const struct cmap_node *nodes[NETDEV_MAX_BURST]; > + uint32_t found_map = Minor nit. Variable declaration. You may see a mix of approaches WRT where variables are declared. Personally I prefer at the beginning of the function to keep with the int variable you have already declared. looking at the original dpcls_lookup() where this code is moved from it looks like they also declared variables at the beginning. Would be good to follow that example. > + cmap_find_batch(&subtable->rules, keys_map, hashes, nodes); > + /* Check results. When the i-th bit of found_map is set, it means > + * that a set of nodes with a matching hash value was found for the > + * i-th search-key. Due to possible hash collisions we need to check > + * which of the found rules, if any, really matches our masked > + * search-key. */ > + ULLONG_FOR_EACH_1(i, found_map) { > + struct dpcls_rule *rule; > + > + CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { > + if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { > + rules[i] = rule; > + /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap > + * within one second optimization interval. */ > + subtable->hit_cnt++; > + goto next; > + } > + } > + /* None of the found rules was a match. Reset the i-th bit to > + * keep searching this key in the next subtable. */ > + ULLONG_SET0(found_map, i); /* Did not match. */ > + next: > + ; /* Keep Sparse happy. */ > + } > + > + return found_map; > +} > + > /* 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. > @@ -7818,16 +7897,12 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key *keys[], > /* The received 'cnt' miniflows are the search-keys that will be processed > * to find a matching entry into the available subtables. > * The number of bits in map_type is equal to NETDEV_MAX_BURST. */ > - typedef uint32_t map_type; > -#define MAP_BITS (sizeof(map_type) * CHAR_BIT) > +#define MAP_BITS (sizeof(uint32_t) * CHAR_BIT) > BUILD_ASSERT_DECL(MAP_BITS >= NETDEV_MAX_BURST); > > struct dpcls_subtable *subtable; > > - map_type keys_map = TYPE_MAXIMUM(map_type); /* Set all bits. */ > - map_type found_map; > - uint32_t hashes[MAP_BITS]; > - const struct cmap_node *nodes[MAP_BITS]; > + uint32_t keys_map = TYPE_MAXIMUM(uint32_t); /* Set all bits. */ > > if (cnt != MAP_BITS) { > keys_map >>= MAP_BITS - cnt; /* Clear extra bits. */ > @@ -7844,52 +7919,28 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key *keys[], > * search-key, the search for that key can stop because the rules are > * non-overlapping. */ > PVECTOR_FOR_EACH (subtable, &cls->subtables) { > - int i; > + /* call the subtable specific lookup function */ > + uint32_t found_map = subtable->lookup_func(subtable, keys_map, > + keys, rules); > > - /* Compute hashes for the remaining keys. Each search-key is > - * masked with the subtable's mask to avoid hashing the wildcarded > - * bits. */ > - ULLONG_FOR_EACH_1(i, keys_map) { > - hashes[i] = netdev_flow_key_hash_in_mask(keys[i], > - &subtable->mask); > - } > - /* Lookup. */ > - found_map = cmap_find_batch(&subtable->rules, keys_map, hashes, nodes); > - /* Check results. When the i-th bit of found_map is set, it means > - * that a set of nodes with a matching hash value was found for the > - * i-th search-key. Due to possible hash collisions we need to check > - * which of the found rules, if any, really matches our masked > - * search-key. */ > - ULLONG_FOR_EACH_1(i, found_map) { > - struct dpcls_rule *rule; > + /* Count the number of subtables searched for this packet match. This > + * estimates the "spread" of subtables looked at per matched packet */ Minor, missing period in comment above. > + uint32_t pkts_matched = count_1bits(found_map); Just to clarify, at this point found_map has been returned and it only contains matches where packets were found? i.e. it doesn't contain matches from possible hash collisions? > + lookups_match += pkts_matched * subtable_pos; > > - CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { > - if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { > - rules[i] = rule; > - /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap > - * within one second optimization interval. */ > - subtable->hit_cnt++; > - lookups_match += subtable_pos; > - goto next; > - } > - } > - /* None of the found rules was a match. Reset the i-th bit to > - * keep searching this key in the next subtable. */ > - ULLONG_SET0(found_map, i); /* Did not match. */ > - next: > - ; /* Keep Sparse happy. */ > - } > - keys_map &= ~found_map; /* Clear the found rules. */ > + /* Clear the found rules, and return early if all packets are found */ Missing period in comment above. > + keys_map &= ~found_map; > if (!keys_map) { > if (num_lookups_p) { > *num_lookups_p = lookups_match; > } > - return true; /* All found. */ > + return true; > } > subtable_pos++; > } > + > if (num_lookups_p) { > *num_lookups_p = lookups_match; > } > - return false; /* Some misses. */ > + return false; > } > I've also run some performance tests on this patch but I didn't see any notable performance degradation from the function implementation which is good. Ian
Hi Ian, Comments inline, and lots of <snips> to trim message size. Thanks for review! -H > -----Original Message----- > From: Stokes, Ian > Sent: Wednesday, May 15, 2019 6:03 PM > To: Van Haaren, Harry <harry.van.haaren@intel.com>; ovs-dev@openvswitch.org > Cc: aconole@redhat.com; echaudro@redhat.com; i.maximets@samsung.com > Subject: Re: [PATCH v9 1/5] dpif-netdev: implement function > pointers/subtable <snip> > > /* Datapath Classifier. */ > > > > +/* forward declaration for lookup_func typedef */ > > Minor nit above, general rule of thumb for comment style, start with > capital letter and finish with period. Sure, will keep in mind for the other patches too. > > +struct dpcls_subtable; > > + > > +/* Lookup function for a subtable in the dpcls. This function is called > > + * by each subtable with an array of packets, and a bitmask of packets to > > + * perform the lookup on. Using a function pointer gives flexibility to > > + * optimize the lookup function based on subtable properties and the > > + * CPU instruction set available at runtime. > > + */ > > +typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable > *subtable, > > + uint32_t keys_map, const struct netdev_flow_key *keys[], > > + struct dpcls_rule **rules); > > Alignment for the arguments above looks odd, typically arguments are > kept vertically in line with one another *similar to > dpcls_subtable_lookup_generic below). This one is a bit odd - the "const struct netdev_flow_key *keys[]" spills over the 80 char limit if aligned using vertical alignment with spaces. I've reworked to the vertical alignment but the line is now greater than 80 chars. Guidance on what is "the best bad solution" here welcome :) > > +/* Prototype for generic lookup func, using same code path as before */ > > Period at end of comment above. Done. <snip> > > @@ -7640,6 +7668,10 @@ dpcls_create_subtable(struct dpcls *cls, const > struct netdev_flow_key *mask) > > cmap_init(&subtable->rules); > > subtable->hit_cnt = 0; > > netdev_flow_key_clone(&subtable->mask, mask); > > + > > + /* decide which hash/lookup/verify function to use */ > > + subtable->lookup_func = dpcls_subtable_lookup_generic; > > So by default dpcls_subtable_lookup_generic is set as the look up > function. Makes sense as this is the only look up available at this > stage. I assume it's later in the series a mechanism to select a > different lookup is introduced. Or by default does the lookup always > start off as the generic option when a subtable is created even when > other options are possible? Yes the generic is the default, which maintains current ovs' current dpcls code. Correct that later in the series there is a dpcls_subtable_generic_probe() function added, which can optionally provide a specialized lookup function for this subtable. If the probe() function returns NULL, then the generic flavor is used. If the probe() sets a function-pointer, then we use that. <snip> > > + /* Lookup. */ > > + const struct cmap_node *nodes[NETDEV_MAX_BURST]; > > + uint32_t found_map = > > Minor nit. Variable declaration. You may see a mix of approaches WRT > where variables are declared. Personally I prefer at the beginning of > the function to keep with the int variable you have already declared. > looking at the original dpcls_lookup() where this code is moved from it > looks like they also declared variables at the beginning. Would be good > to follow that example. Sure, moved variable declaration up to above its use. <snip> > > - ULLONG_FOR_EACH_1(i, found_map) { > > - struct dpcls_rule *rule; > > + /* Count the number of subtables searched for this packet match. > This > > + * estimates the "spread" of subtables looked at per matched > packet */ > > Minor, missing period in comment above. Done. > > + uint32_t pkts_matched = count_1bits(found_map); > > Just to clarify, at this point found_map has been returned and it only > contains matches where packets were found? i.e. it doesn't contain > matches from possible hash collisions? Hash collisions are resolved inside the lookup implementation, hence any bits set in pkts_matched are hash-matches AND passed the rule-verify too. <snip> > > - keys_map &= ~found_map; /* Clear the found rules. */ > > + /* Clear the found rules, and return early if all packets are > found */ > Missing period in comment above. Fixed. > > + keys_map &= ~found_map; > > if (!keys_map) { > > if (num_lookups_p) { > > *num_lookups_p = lookups_match; > > } > > - return true; /* All found. */ > > + return true; > > } > > subtable_pos++; > > } > > + > > if (num_lookups_p) { > > *num_lookups_p = lookups_match; > > } > > - return false; /* Some misses. */ > > + return false; > > } > > > > I've also run some performance tests on this patch but I didn't see any > notable performance degradation from the function implementation which > is good. > > Ian Thanks for review, I'll address other feedback on patchset and post a v10 then.
On 5/15/2019 6:02 PM, Ian Stokes wrote: > On 5/8/2019 4:13 PM, Harry van Haaren wrote: >> This allows plugging-in of different subtable hash-lookup-verify >> routines, and allows special casing of those functions based on >> known context (eg: # of bits set) of the specific subtable. >> >> Signed-off-by: Harry van Haaren <harry.van.haaren@intel.com> >> >> --- >> >> v9: >> - Use count_1bits in favour of __builtin_popcount (Ilya) >> >> v6: >> - Implement subtable effort per packet "lookups_match" counter (Ilya) >> - Remove double newline (Eelco) >> - Remove doubel * before comments (Eelco) >> - Reword comments in dpcls_lookup() for clarity (Harry) >> --- >> lib/dpif-netdev.c | 135 +++++++++++++++++++++++++++++++--------------- >> 1 file changed, 93 insertions(+), 42 deletions(-) >> >> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c >> index 5a6f2abac..e2e2c14e7 100644 >> --- a/lib/dpif-netdev.c >> +++ b/lib/dpif-netdev.c >> @@ -7572,6 +7572,27 @@ dpif_dummy_register(enum dummy_level level) >> >> /* Datapath Classifier. */ >> +/* forward declaration for lookup_func typedef */ > > Minor nit above, general rule of thumb for comment style, start with > capital letter and finish with period. > >> +struct dpcls_subtable; >> + >> +/* Lookup function for a subtable in the dpcls. This function is called >> + * by each subtable with an array of packets, and a bitmask of >> packets to >> + * perform the lookup on. Using a function pointer gives flexibility to >> + * optimize the lookup function based on subtable properties and the >> + * CPU instruction set available at runtime. >> + */ >> +typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable >> *subtable, >> + uint32_t keys_map, const struct netdev_flow_key *keys[], >> + struct dpcls_rule **rules); > > Alignment for the arguments above looks odd, typically arguments are > kept vertically in line with one another *similar to > dpcls_subtable_lookup_generic below). > >> + >> +/* Prototype for generic lookup func, using same code path as before */ > > Period at end of comment above. > >> +uint32_t >> +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, >> + uint32_t keys_map, >> + const struct netdev_flow_key *keys[], >> + struct dpcls_rule **rules); >> + >> + One minor follow up, extra whitespace seems to have been added here, cab be reduced to 1 new line. >> /* A set of rules that all have the same fields wildcarded. */ >> struct dpcls_subtable { >> /* The fields are only used by writers. */ >> @@ -7581,6 +7602,13 @@ struct dpcls_subtable { >> struct cmap rules; /* Contains "struct dpcls_rule"s. */ >> uint32_t hit_cnt; /* Number of match hits in subtable >> in current >> optimization interval. */ >> + >> + /* the lookup function to use for this subtable. If there is a known >> + * property of the subtable (eg: only 3 bits of miniflow metadata is >> + * used for the lookup) then this can point at an optimized >> version of >> + * the lookup function for this particular subtable. */ > the -> The above. >> + dpcls_subtable_lookup_func lookup_func; >> + >> struct netdev_flow_key mask; /* Wildcards for fields (const). */ >> /* 'mask' must be the last field, additional space is allocated >> here. */ >> }; >> @@ -7640,6 +7668,10 @@ dpcls_create_subtable(struct dpcls *cls, const >> struct netdev_flow_key *mask) >> cmap_init(&subtable->rules); >> subtable->hit_cnt = 0; >> netdev_flow_key_clone(&subtable->mask, mask); >> + >> + /* decide which hash/lookup/verify function to use */ >> + subtable->lookup_func = dpcls_subtable_lookup_generic; > > So by default dpcls_subtable_lookup_generic is set as the look up > function. Makes sense as this is the only look up available at this > stage. I assume it's later in the series a mechanism to select a > different lookup is introduced. Or by default does the lookup always > start off as the generic option when a subtable is created even when > other options are possible? > >> + >> cmap_insert(&cls->subtables_map, &subtable->cmap_node, mask->hash); >> /* Add the new subtable at the end of the pvector (with no hits >> yet) */ >> pvector_insert(&cls->subtables, subtable, 0); >> @@ -7800,6 +7832,53 @@ dpcls_rule_matches_key(const struct dpcls_rule >> *rule, >> return true; >> } >> +uint32_t >> +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, >> + uint32_t keys_map, >> + const struct netdev_flow_key *keys[], >> + struct dpcls_rule **rules) >> +{ >> + int i; >> + /* Compute hashes for the remaining keys. Each search-key is >> + * masked with the subtable's mask to avoid hashing the >> wildcarded >> + * bits. */ >> + uint32_t hashes[NETDEV_MAX_BURST]; >> + ULLONG_FOR_EACH_1(i, keys_map) { >> + hashes[i] = netdev_flow_key_hash_in_mask(keys[i], >> + &subtable->mask); >> + } >> + >> + /* Lookup. */ >> + const struct cmap_node *nodes[NETDEV_MAX_BURST]; >> + uint32_t found_map = > > Minor nit. Variable declaration. You may see a mix of approaches WRT > where variables are declared. Personally I prefer at the beginning of > the function to keep with the int variable you have already declared. > looking at the original dpcls_lookup() where this code is moved from it > looks like they also declared variables at the beginning. Would be good > to follow that example. > >> + cmap_find_batch(&subtable->rules, keys_map, hashes, >> nodes); >> + /* Check results. When the i-th bit of found_map is set, it >> means >> + * that a set of nodes with a matching hash value was found >> for the >> + * i-th search-key. Due to possible hash collisions we need >> to check >> + * which of the found rules, if any, really matches our masked >> + * search-key. */ >> + ULLONG_FOR_EACH_1(i, found_map) { >> + struct dpcls_rule *rule; >> + >> + CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { >> + if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { >> + rules[i] = rule; >> + /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap >> + * within one second optimization interval. */ >> + subtable->hit_cnt++; >> + goto next; >> + } >> + } >> + /* None of the found rules was a match. Reset the i-th >> bit to >> + * keep searching this key in the next subtable. */ >> + ULLONG_SET0(found_map, i); /* Did not match. */ >> + next: >> + ; /* Keep Sparse happy. */ >> + } >> + >> + return found_map; >> +} >> + >> /* 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. >> @@ -7818,16 +7897,12 @@ dpcls_lookup(struct dpcls *cls, const struct >> netdev_flow_key *keys[], >> /* The received 'cnt' miniflows are the search-keys that will be >> processed >> * to find a matching entry into the available subtables. >> * The number of bits in map_type is equal to NETDEV_MAX_BURST. */ >> - typedef uint32_t map_type; >> -#define MAP_BITS (sizeof(map_type) * CHAR_BIT) >> +#define MAP_BITS (sizeof(uint32_t) * CHAR_BIT) >> BUILD_ASSERT_DECL(MAP_BITS >= NETDEV_MAX_BURST); >> struct dpcls_subtable *subtable; >> - map_type keys_map = TYPE_MAXIMUM(map_type); /* Set all bits. */ >> - map_type found_map; >> - uint32_t hashes[MAP_BITS]; >> - const struct cmap_node *nodes[MAP_BITS]; >> + uint32_t keys_map = TYPE_MAXIMUM(uint32_t); /* Set all bits. */ >> if (cnt != MAP_BITS) { >> keys_map >>= MAP_BITS - cnt; /* Clear extra bits. */ >> @@ -7844,52 +7919,28 @@ dpcls_lookup(struct dpcls *cls, const struct >> netdev_flow_key *keys[], >> * search-key, the search for that key can stop because the >> rules are >> * non-overlapping. */ >> PVECTOR_FOR_EACH (subtable, &cls->subtables) { >> - int i; >> + /* call the subtable specific lookup function */ >> + uint32_t found_map = subtable->lookup_func(subtable, keys_map, >> + keys, rules); >> - /* Compute hashes for the remaining keys. Each search-key is >> - * masked with the subtable's mask to avoid hashing the >> wildcarded >> - * bits. */ >> - ULLONG_FOR_EACH_1(i, keys_map) { >> - hashes[i] = netdev_flow_key_hash_in_mask(keys[i], >> - &subtable->mask); >> - } >> - /* Lookup. */ >> - found_map = cmap_find_batch(&subtable->rules, keys_map, >> hashes, nodes); >> - /* Check results. When the i-th bit of found_map is set, it >> means >> - * that a set of nodes with a matching hash value was found >> for the >> - * i-th search-key. Due to possible hash collisions we need >> to check >> - * which of the found rules, if any, really matches our masked >> - * search-key. */ >> - ULLONG_FOR_EACH_1(i, found_map) { >> - struct dpcls_rule *rule; >> + /* Count the number of subtables searched for this packet >> match. This >> + * estimates the "spread" of subtables looked at per matched >> packet */ > > Minor, missing period in comment above. > >> + uint32_t pkts_matched = count_1bits(found_map); > > Just to clarify, at this point found_map has been returned and it only > contains matches where packets were found? i.e. it doesn't contain > matches from possible hash collisions? > >> + lookups_match += pkts_matched * subtable_pos; Hi Harry, can you clarify above why '* subtable_pos' is used? Is that right? I'm just thinking that you already have the number of packets matched from the count_1bits(found_map). Ian >> - CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { >> - if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { >> - rules[i] = rule; >> - /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap >> - * within one second optimization interval. */ >> - subtable->hit_cnt++; >> - lookups_match += subtable_pos; >> - goto next; >> - } >> - } >> - /* None of the found rules was a match. Reset the i-th >> bit to >> - * keep searching this key in the next subtable. */ >> - ULLONG_SET0(found_map, i); /* Did not match. */ >> - next: >> - ; /* Keep Sparse happy. */ >> - } >> - keys_map &= ~found_map; /* Clear the found rules. */ >> + /* Clear the found rules, and return early if all packets are >> found */ > Missing period in comment above. > >> + keys_map &= ~found_map; >> if (!keys_map) { >> if (num_lookups_p) { >> *num_lookups_p = lookups_match; >> } >> - return true; /* All found. */ >> + return true; >> } >> subtable_pos++; >> } >> + >> if (num_lookups_p) { >> *num_lookups_p = lookups_match; >> } >> - return false; /* Some misses. */ >> + return false; >> } >> > > I've also run some performance tests on this patch but I didn't see any > notable performance degradation from the function implementation which > is good. > > Ian > _______________________________________________ > dev mailing list > dev@openvswitch.org > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> -----Original Message----- > From: Stokes, Ian > Sent: Tuesday, July 2, 2019 3:40 PM > To: Van Haaren, Harry <harry.van.haaren@intel.com>; ovs-dev@openvswitch.org > Cc: i.maximets@samsung.com > Subject: Re: [ovs-dev] [PATCH v9 1/5] dpif-netdev: implement function > pointers/subtable > > On 5/15/2019 6:02 PM, Ian Stokes wrote: > > On 5/8/2019 4:13 PM, Harry van Haaren wrote: > >> This allows plugging-in of different subtable hash-lookup-verify > >> routines, and allows special casing of those functions based on > >> known context (eg: # of bits set) of the specific subtable. > >> > >> Signed-off-by: Harry van Haaren <harry.van.haaren@intel.com> > >> > >> --- > >> > >> v9: > >> - Use count_1bits in favour of __builtin_popcount (Ilya) > >> > >> v6: > >> - Implement subtable effort per packet "lookups_match" counter (Ilya) > >> - Remove double newline (Eelco) > >> - Remove doubel * before comments (Eelco) > >> - Reword comments in dpcls_lookup() for clarity (Harry) > >> --- > >> lib/dpif-netdev.c | 135 +++++++++++++++++++++++++++++++--------------- > >> 1 file changed, 93 insertions(+), 42 deletions(-) > >> > >> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c > >> index 5a6f2abac..e2e2c14e7 100644 > >> --- a/lib/dpif-netdev.c > >> +++ b/lib/dpif-netdev.c > >> @@ -7572,6 +7572,27 @@ dpif_dummy_register(enum dummy_level level) > >> > >> /* Datapath Classifier. */ > >> +/* forward declaration for lookup_func typedef */ > > > > Minor nit above, general rule of thumb for comment style, start with > > capital letter and finish with period. > > > >> +struct dpcls_subtable; > >> + > >> +/* Lookup function for a subtable in the dpcls. This function is called > >> + * by each subtable with an array of packets, and a bitmask of > >> packets to > >> + * perform the lookup on. Using a function pointer gives flexibility to > >> + * optimize the lookup function based on subtable properties and the > >> + * CPU instruction set available at runtime. > >> + */ > >> +typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable > >> *subtable, > >> + uint32_t keys_map, const struct netdev_flow_key *keys[], > >> + struct dpcls_rule **rules); > > > > Alignment for the arguments above looks odd, typically arguments are > > kept vertically in line with one another *similar to > > dpcls_subtable_lookup_generic below). > > > >> + > >> +/* Prototype for generic lookup func, using same code path as before */ > > > > Period at end of comment above. > > > >> +uint32_t > >> +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, > >> + uint32_t keys_map, > >> + const struct netdev_flow_key *keys[], > >> + struct dpcls_rule **rules); > >> + > >> + > > One minor follow up, extra whitespace seems to have been added here, cab > be reduced to 1 new line. Will fix. <snip> > > > >> + uint32_t pkts_matched = count_1bits(found_map); > > > > Just to clarify, at this point found_map has been returned and it only > > contains matches where packets were found? i.e. it doesn't contain > > matches from possible hash collisions? > > > >> + lookups_match += pkts_matched * subtable_pos; > > Hi Harry, can you clarify above why '* subtable_pos' is used? Is that > right? I'm just thinking that you already have the number of packets > matched from the count_1bits(found_map). The "lookups match" counter variable name is a bit misleading, but I'd change it in this patchset as its orthogonal to the DPCLS function pointer concept. The counter counts "number of subtables searched per hit packet", so to speak. See Ilya's input and my response here: https://www.mail-archive.com/ovs-dev@openvswitch.org/msg31442.html This is a pseudo code of expected behavior: 1st subtable packet hits are += 1, 2nd subtable packet hits are += 2, 3rd subtable packet hits are += 3 etc. At the end of a burst, we have a bitmask of packets hit, and a counter for "subtable effort per packet matched". Given two experienced OVS folks asked ~ the same question, hints that its time for a cleanup & refactor, perhaps even a /* descriptive comment */ :) <snip> Thanks for review / comments! -Harry
On 7/2/2019 4:02 PM, Van Haaren, Harry wrote: >> -----Original Message----- >> From: Stokes, Ian >> Sent: Tuesday, July 2, 2019 3:40 PM >> To: Van Haaren, Harry <harry.van.haaren@intel.com>; ovs-dev@openvswitch.org >> Cc: i.maximets@samsung.com >> Subject: Re: [ovs-dev] [PATCH v9 1/5] dpif-netdev: implement function >> pointers/subtable >> >> On 5/15/2019 6:02 PM, Ian Stokes wrote: >>> On 5/8/2019 4:13 PM, Harry van Haaren wrote: >>>> This allows plugging-in of different subtable hash-lookup-verify >>>> routines, and allows special casing of those functions based on >>>> known context (eg: # of bits set) of the specific subtable. >>>> >>>> Signed-off-by: Harry van Haaren <harry.van.haaren@intel.com> >>>> >>>> --- >>>> >>>> v9: >>>> - Use count_1bits in favour of __builtin_popcount (Ilya) >>>> >>>> v6: >>>> - Implement subtable effort per packet "lookups_match" counter (Ilya) >>>> - Remove double newline (Eelco) >>>> - Remove doubel * before comments (Eelco) >>>> - Reword comments in dpcls_lookup() for clarity (Harry) >>>> --- >>>> lib/dpif-netdev.c | 135 +++++++++++++++++++++++++++++++--------------- >>>> 1 file changed, 93 insertions(+), 42 deletions(-) >>>> >>>> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c >>>> index 5a6f2abac..e2e2c14e7 100644 >>>> --- a/lib/dpif-netdev.c >>>> +++ b/lib/dpif-netdev.c >>>> @@ -7572,6 +7572,27 @@ dpif_dummy_register(enum dummy_level level) >>>> > >>>> /* Datapath Classifier. */ >>>> +/* forward declaration for lookup_func typedef */ >>> >>> Minor nit above, general rule of thumb for comment style, start with >>> capital letter and finish with period. >>> >>>> +struct dpcls_subtable; >>>> + >>>> +/* Lookup function for a subtable in the dpcls. This function is called >>>> + * by each subtable with an array of packets, and a bitmask of >>>> packets to >>>> + * perform the lookup on. Using a function pointer gives flexibility to >>>> + * optimize the lookup function based on subtable properties and the >>>> + * CPU instruction set available at runtime. >>>> + */ >>>> +typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable >>>> *subtable, >>>> + uint32_t keys_map, const struct netdev_flow_key *keys[], >>>> + struct dpcls_rule **rules); >>> >>> Alignment for the arguments above looks odd, typically arguments are >>> kept vertically in line with one another *similar to >>> dpcls_subtable_lookup_generic below). >>> >>>> + >>>> +/* Prototype for generic lookup func, using same code path as before */ >>> >>> Period at end of comment above. >>> >>>> +uint32_t >>>> +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, >>>> + uint32_t keys_map, >>>> + const struct netdev_flow_key *keys[], >>>> + struct dpcls_rule **rules); >>>> + >>>> + >> >> One minor follow up, extra whitespace seems to have been added here, cab >> be reduced to 1 new line. > > Will fix. > > <snip> > >>> >>>> + uint32_t pkts_matched = count_1bits(found_map); >>> >>> Just to clarify, at this point found_map has been returned and it only >>> contains matches where packets were found? i.e. it doesn't contain >>> matches from possible hash collisions? >>> >>>> + lookups_match += pkts_matched * subtable_pos; >> >> Hi Harry, can you clarify above why '* subtable_pos' is used? Is that >> right? I'm just thinking that you already have the number of packets >> matched from the count_1bits(found_map). > > The "lookups match" counter variable name is a bit misleading, but I'd > change it in this patchset as its orthogonal to the DPCLS function pointer > concept. > > The counter counts "number of subtables searched per hit packet", so to > speak. See Ilya's input and my response here: > https://www.mail-archive.com/ovs-dev@openvswitch.org/msg31442.html > > This is a pseudo code of expected behavior: > 1st subtable packet hits are += 1, > 2nd subtable packet hits are += 2, > 3rd subtable packet hits are += 3 etc. > > At the end of a burst, we have a bitmask of packets hit, and a counter for > "subtable effort per packet matched". > > Given two experienced OVS folks asked ~ the same question, hints that its > time for a cleanup & refactor, perhaps even a /* descriptive comment */ :) > Ya that makes more sense, confirms what i suspected :). Sure a description of the purpose would help here in the next revision. Thanks Ian
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index 5a6f2abac..e2e2c14e7 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -7572,6 +7572,27 @@ dpif_dummy_register(enum dummy_level level) /* Datapath Classifier. */ +/* forward declaration for lookup_func typedef */ +struct dpcls_subtable; + +/* Lookup function for a subtable in the dpcls. This function is called + * by each subtable with an array of packets, and a bitmask of packets to + * perform the lookup on. Using a function pointer gives flexibility to + * optimize the lookup function based on subtable properties and the + * CPU instruction set available at runtime. + */ +typedef uint32_t (*dpcls_subtable_lookup_func)(struct dpcls_subtable *subtable, + uint32_t keys_map, const struct netdev_flow_key *keys[], + struct dpcls_rule **rules); + +/* Prototype for generic lookup func, using same code path as before */ +uint32_t +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, + uint32_t keys_map, + const struct netdev_flow_key *keys[], + struct dpcls_rule **rules); + + /* A set of rules that all have the same fields wildcarded. */ struct dpcls_subtable { /* The fields are only used by writers. */ @@ -7581,6 +7602,13 @@ struct dpcls_subtable { struct cmap rules; /* Contains "struct dpcls_rule"s. */ uint32_t hit_cnt; /* Number of match hits in subtable in current optimization interval. */ + + /* the lookup function to use for this subtable. If there is a known + * property of the subtable (eg: only 3 bits of miniflow metadata is + * used for the lookup) then this can point at an optimized version of + * the lookup function for this particular subtable. */ + dpcls_subtable_lookup_func lookup_func; + struct netdev_flow_key mask; /* Wildcards for fields (const). */ /* 'mask' must be the last field, additional space is allocated here. */ }; @@ -7640,6 +7668,10 @@ dpcls_create_subtable(struct dpcls *cls, const struct netdev_flow_key *mask) cmap_init(&subtable->rules); subtable->hit_cnt = 0; netdev_flow_key_clone(&subtable->mask, mask); + + /* decide which hash/lookup/verify function to use */ + subtable->lookup_func = dpcls_subtable_lookup_generic; + cmap_insert(&cls->subtables_map, &subtable->cmap_node, mask->hash); /* Add the new subtable at the end of the pvector (with no hits yet) */ pvector_insert(&cls->subtables, subtable, 0); @@ -7800,6 +7832,53 @@ dpcls_rule_matches_key(const struct dpcls_rule *rule, return true; } +uint32_t +dpcls_subtable_lookup_generic(struct dpcls_subtable *subtable, + uint32_t keys_map, + const struct netdev_flow_key *keys[], + struct dpcls_rule **rules) +{ + int i; + /* Compute hashes for the remaining keys. Each search-key is + * masked with the subtable's mask to avoid hashing the wildcarded + * bits. */ + uint32_t hashes[NETDEV_MAX_BURST]; + ULLONG_FOR_EACH_1(i, keys_map) { + hashes[i] = netdev_flow_key_hash_in_mask(keys[i], + &subtable->mask); + } + + /* Lookup. */ + const struct cmap_node *nodes[NETDEV_MAX_BURST]; + uint32_t found_map = + cmap_find_batch(&subtable->rules, keys_map, hashes, nodes); + /* Check results. When the i-th bit of found_map is set, it means + * that a set of nodes with a matching hash value was found for the + * i-th search-key. Due to possible hash collisions we need to check + * which of the found rules, if any, really matches our masked + * search-key. */ + ULLONG_FOR_EACH_1(i, found_map) { + struct dpcls_rule *rule; + + CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { + if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { + rules[i] = rule; + /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap + * within one second optimization interval. */ + subtable->hit_cnt++; + goto next; + } + } + /* None of the found rules was a match. Reset the i-th bit to + * keep searching this key in the next subtable. */ + ULLONG_SET0(found_map, i); /* Did not match. */ + next: + ; /* Keep Sparse happy. */ + } + + return found_map; +} + /* 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. @@ -7818,16 +7897,12 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key *keys[], /* The received 'cnt' miniflows are the search-keys that will be processed * to find a matching entry into the available subtables. * The number of bits in map_type is equal to NETDEV_MAX_BURST. */ - typedef uint32_t map_type; -#define MAP_BITS (sizeof(map_type) * CHAR_BIT) +#define MAP_BITS (sizeof(uint32_t) * CHAR_BIT) BUILD_ASSERT_DECL(MAP_BITS >= NETDEV_MAX_BURST); struct dpcls_subtable *subtable; - map_type keys_map = TYPE_MAXIMUM(map_type); /* Set all bits. */ - map_type found_map; - uint32_t hashes[MAP_BITS]; - const struct cmap_node *nodes[MAP_BITS]; + uint32_t keys_map = TYPE_MAXIMUM(uint32_t); /* Set all bits. */ if (cnt != MAP_BITS) { keys_map >>= MAP_BITS - cnt; /* Clear extra bits. */ @@ -7844,52 +7919,28 @@ dpcls_lookup(struct dpcls *cls, const struct netdev_flow_key *keys[], * search-key, the search for that key can stop because the rules are * non-overlapping. */ PVECTOR_FOR_EACH (subtable, &cls->subtables) { - int i; + /* call the subtable specific lookup function */ + uint32_t found_map = subtable->lookup_func(subtable, keys_map, + keys, rules); - /* Compute hashes for the remaining keys. Each search-key is - * masked with the subtable's mask to avoid hashing the wildcarded - * bits. */ - ULLONG_FOR_EACH_1(i, keys_map) { - hashes[i] = netdev_flow_key_hash_in_mask(keys[i], - &subtable->mask); - } - /* Lookup. */ - found_map = cmap_find_batch(&subtable->rules, keys_map, hashes, nodes); - /* Check results. When the i-th bit of found_map is set, it means - * that a set of nodes with a matching hash value was found for the - * i-th search-key. Due to possible hash collisions we need to check - * which of the found rules, if any, really matches our masked - * search-key. */ - ULLONG_FOR_EACH_1(i, found_map) { - struct dpcls_rule *rule; + /* Count the number of subtables searched for this packet match. This + * estimates the "spread" of subtables looked at per matched packet */ + uint32_t pkts_matched = count_1bits(found_map); + lookups_match += pkts_matched * subtable_pos; - CMAP_NODE_FOR_EACH (rule, cmap_node, nodes[i]) { - if (OVS_LIKELY(dpcls_rule_matches_key(rule, keys[i]))) { - rules[i] = rule; - /* Even at 20 Mpps the 32-bit hit_cnt cannot wrap - * within one second optimization interval. */ - subtable->hit_cnt++; - lookups_match += subtable_pos; - goto next; - } - } - /* None of the found rules was a match. Reset the i-th bit to - * keep searching this key in the next subtable. */ - ULLONG_SET0(found_map, i); /* Did not match. */ - next: - ; /* Keep Sparse happy. */ - } - keys_map &= ~found_map; /* Clear the found rules. */ + /* Clear the found rules, and return early if all packets are found */ + keys_map &= ~found_map; if (!keys_map) { if (num_lookups_p) { *num_lookups_p = lookups_match; } - return true; /* All found. */ + return true; } subtable_pos++; } + if (num_lookups_p) { *num_lookups_p = lookups_match; } - return false; /* Some misses. */ + return false; }
This allows plugging-in of different subtable hash-lookup-verify routines, and allows special casing of those functions based on known context (eg: # of bits set) of the specific subtable. Signed-off-by: Harry van Haaren <harry.van.haaren@intel.com> --- v9: - Use count_1bits in favour of __builtin_popcount (Ilya) v6: - Implement subtable effort per packet "lookups_match" counter (Ilya) - Remove double newline (Eelco) - Remove doubel * before comments (Eelco) - Reword comments in dpcls_lookup() for clarity (Harry) --- lib/dpif-netdev.c | 135 +++++++++++++++++++++++++++++++--------------- 1 file changed, 93 insertions(+), 42 deletions(-)