Re: [ovs-dev] [PATCH v10 1/5] dpif-netdev: implement function pointers/subtable
On 7/10/2019 4:40 PM, Van Haaren, Harry wrote: -Original Message- From: Stokes, Ian Sent: Wednesday, July 10, 2019 4:30 PM To: Van Haaren, Harry ; d...@openvswitch.org Cc: i.maxim...@samsung.com; malvika.gu...@arm.com Subject: Re: [PATCH v10 1/5] dpif-netdev: implement function pointers/subtable On 7/9/2019 1:34 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 Tested-by: Malvika Gupta Thanks for this harry, few minor comments below. Hey, cool I'll snip away irrelevant code sections for readability. I've thought about whether an item should be added to the NEWS doc (possibly not in this patch but perhaps later in the series), it's hard to say as the changes are under the hood and not configurable by a user. Thoughts? Correct the user shouldn't identify the actual changes, except for small gains in performance if the specialized subtables are in use. I think it would be good to add a NEWS item, as people profiling OVS's functions will see different function names, and having called out the DPCLS Function Pointer changes, and why they are there would be beneficial. I will draft a separate patch for NEWS item - so we can keep it parallel to this patch set. Shout if that is not a good approach :) I would think it could be added as part of patch 5 of the series as that's when the performance increase is introduced? Anyway it's minor enough that if there is not another revision of the series it can be done upon commit. Regards Ian ___ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev
Re: [ovs-dev] [PATCH v10 1/5] dpif-netdev: implement function pointers/subtable
> -Original Message-
> From: Stokes, Ian
> Sent: Wednesday, July 10, 2019 4:30 PM
> To: Van Haaren, Harry ; d...@openvswitch.org
> Cc: i.maxim...@samsung.com; malvika.gu...@arm.com
> Subject: Re: [PATCH v10 1/5] dpif-netdev: implement function pointers/subtable
>
> On 7/9/2019 1:34 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
> > Tested-by: Malvika Gupta
> >
>
> Thanks for this harry, few minor comments below.
Hey, cool I'll snip away irrelevant code sections for readability.
> > +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;
> > +uint32_t found_map;
>
> I was thinking should this be initialized to 0, but I don't think there
> is a need. the call to cmap_find_batch() below will set it to 0 in the
> case of no math, otherwise set the i-th bit for a match so I thinks it's ok.
Correct - the value is written before being used - always.
Initializing it to zero is pointless, and only waste and instruction.
> > @@ -7849,16 +7931,12 @@ dpcls_lookup(struct dpcls *cls, const struct
> > if (cnt != MAP_BITS) {
> > keys_map >>= MAP_BITS - cnt; /* Clear extra bits. */
> > @@ -7866,6 +7944,7 @@ dpcls_lookup(struct dpcls *cls, const struct
> netdev_flow_key *keys[],
> > memset(rules, 0, cnt * sizeof *rules);
> >
> > int lookups_match = 0, subtable_pos = 1;
> > +uint32_t found_map;
>
> Same as above, should be OK as it wont be used until after the call to
> the generic look up function, which will set it to 0 in the event of no
> matches.
Correct - written before use - no use in initializing to any value.
> > -/* 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;
> > }
> >
>
> I've thought about whether an item should be added to the NEWS doc
> (possibly not in this patch but perhaps later in the series), it's hard
> to say as the changes are under the hood and not configurable by a user.
> Thoughts?
Correct the user shouldn't identify the actual changes, except for small
gains in performance if the specialized subtables are in use.
I think it would be good to add a NEWS item, as people profiling OVS's functions
will see different function names, and having called out the DPCLS Function
Pointer
changes, and why they are there would be beneficial.
I will draft a separate patch for NEWS item - so we can keep it parallel to
this patch set.
Shout if that is not a good approach :)
> Regards
> Ian
Thanks for review!
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
Re: [ovs-dev] [PATCH v10 1/5] dpif-netdev: implement function pointers/subtable
On 7/9/2019 1:34 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
Tested-by: Malvika Gupta
Thanks for this harry, few minor comments below.
---
v10:
- Fix capitalization of comments, and punctuation. (Ian)
- Variable declarations up top before use (Ian)
- Fix alignment of function parameters, had to newline after typedef (Ian)
- Some mailing-list questions relpied to on-list (Ian)
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 double * before comments (Eelco)
- Reword comments in dpcls_lookup() for clarity (Harry)
---
lib/dpif-netdev.c | 138 --
1 file changed, 96 insertions(+), 42 deletions(-)
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index f4b59e41b..f02bcd552 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -7603,6 +7603,28 @@ 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. */
@@ -7612,6 +7634,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. */
};
@@ -7671,6 +7700,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);
@@ -7831,6 +7864,55 @@ 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;
+uint32_t found_map;
I was thinking should this be initialized to 0, but I don't think there
is a need. the call to cmap_find_batch() below will set it to 0 in the
case of no math, otherwise set the i-th bit for a match so I thinks it's ok.
+
+/* 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];
+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
