| Message ID | 1490869231-20129-1-git-send-email-billy.o.mahony@intel.com |
|---|---|
| State | Deferred |
| Delegated to: | Darrell Ball |
| Headers | show |
Thanks for the patch Billy
On 3/30/17, 3:20 AM, "ovs-dev-bounces@openvswitch.org on behalf of Billy O'Mahony" <ovs-dev-bounces@openvswitch.org on behalf of billy.o.mahony@intel.com> wrote:
Add a concrete example of how a flow's hash determines the set of
possible storage locations in the EMC.
Signed-off-by: Billy O'Mahony <billy.o.mahony@intel.com>
---
lib/dpif-netdev.c | 24 +++++++++++++++++-------
1 file changed, 17 insertions(+), 7 deletions(-)
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 7d53a8d..d99eec7 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -124,16 +124,26 @@ struct netdev_flow_key {
/* Exact match cache for frequently used flows
*
* The cache uses a 32-bit hash of the packet (which can be the RSS hash) to
- * search its entries for a miniflow that matches exactly the miniflow of the
- * packet. It stores the 'dpcls_rule' (rule) that matches the miniflow.
+ * search its entries for the miniflow that matches exactly the miniflow of the
+ * packet. The dp_netdev_flow reference in the matching emc_entry also stores
+ * the dpcls_rule that corresponds to the miniflow.
*
- * A cache entry holds a reference to its 'dp_netdev_flow'.
This part
“ + * The dp_netdev_flow reference in the matching emc_entry also stores
+ * the dpcls_rule that corresponds to the miniflow.”
is clearer.
+ * A miniflow with a given hash can be stored in any one of EM_FLOW_HASH_SEGS
+ * different entries. The 32-bit hash is split into EM_FLOW_HASH_SEGS values
+ * (each of which is EM_FLOW_HASH_SHIFT bits wide - the remainder is thrown
+ * away). Each value is the index of a cache entry where the miniflow could be
+ * stored.
*
- * A miniflow with a given hash can be in one of EM_FLOW_HASH_SEGS different
- * entries. The 32-bit hash is split into EM_FLOW_HASH_SEGS values (each of
- * them is EM_FLOW_HASH_SHIFT bits wide and the remainder is thrown away). Each
- * value is the index of a cache entry where the miniflow could be.
+ * For example, assuming that EM_FLOW_HASH_SHIFT is 13 and EM_FLOW_HASH_SEGS is
+ * 2, an entry with 32-bit hash of 0xDEADBEEF could be stored at either
+ * entries[0x156D] or entries[0x1EEF].
entries[0x1EEF] or entries[0x156D].
The indices are derived from bits 0-12
+ * and bits 13-25 of the 32-bit hash respectively. Bits 26-31 are ignored. Both
+ * entries have to be checked with netdev_flow_key_equal() to find the actual
+ * match. Note: bits 0 and 31 are the least and most significant bits
+ * respectively of the 32 bit hash value.
*
+ * It follows from the search indices being generated from n bits that the
+ * number of entries in the cache must be a power of two.
The added comments from “A miniflow with a given hash” seem obvious and also
a bit micro-detailed, such that they could easily become outdated, if not carefully maintained.
For instance, the example is based on present cache size (although, the wording uses “assuming”)
which may change and hence the example would probably need to be updated, else it might cause
confusion that would not otherwise exist.
If folks feel strongly that these added comments help them, then they can ack it and we can include
them.
*
* Thread-safety
* =============
--
2.7.4
_______________________________________________
dev mailing list
dev@openvswitch.org
https://urldefense.proofpoint.com/v2/url?u=https-3A__mail.openvswitch.org_mailman_listinfo_ovs-2Ddev&d=DwICAg&c=uilaK90D4TOVoH58JNXRgQ&r=BVhFA09CGX7JQ5Ih-uZnsw&m=8NtshUOoQuDvlKk0AzLtHL6N2FKmM4uWibENQmf8XOc&s=LrVJc9AzeZ4lJPNSehSvQUrb8J2hvZec-QQOuxB4W8o&e=
Hi Darrell, Thanks for reviewing. I considered doing a little bit of ascii art to detail what was going but they are not used in the ovs code anywhere else, so instead I settled for illustrating the general case via a specific case. I felt that the extra commentary here was useful as it makes it clearer that the cache is effectively an n-way cache and that it is quite possible to have EMC collisions between packets even if their tuple hashes are different. Cheers, /Billy. > -----Original Message----- > From: Darrell Ball [mailto:dball@vmware.com] > Sent: Saturday, May 13, 2017 8:33 PM > To: O Mahony, Billy <billy.o.mahony@intel.com>; dev@openvswitch.org > Subject: Re: [ovs-dev] [PATCH] dpif-netdev: emc comments > > Thanks for the patch Billy > > On 3/30/17, 3:20 AM, "ovs-dev-bounces@openvswitch.org on behalf of Billy > O'Mahony" <ovs-dev-bounces@openvswitch.org on behalf of > billy.o.mahony@intel.com> wrote: > > Add a concrete example of how a flow's hash determines the set of > possible storage locations in the EMC. > > Signed-off-by: Billy O'Mahony <billy.o.mahony@intel.com> > --- > lib/dpif-netdev.c | 24 +++++++++++++++++------- > 1 file changed, 17 insertions(+), 7 deletions(-) > > diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c > index 7d53a8d..d99eec7 100644 > --- a/lib/dpif-netdev.c > +++ b/lib/dpif-netdev.c > @@ -124,16 +124,26 @@ struct netdev_flow_key { > /* Exact match cache for frequently used flows > * > * The cache uses a 32-bit hash of the packet (which can be the RSS hash) > to > - * search its entries for a miniflow that matches exactly the miniflow of the > - * packet. It stores the 'dpcls_rule' (rule) that matches the miniflow. > + * search its entries for the miniflow that matches exactly the miniflow of > the > + * packet. The dp_netdev_flow reference in the matching emc_entry also > stores > + * the dpcls_rule that corresponds to the miniflow. > > * > - * A cache entry holds a reference to its 'dp_netdev_flow'. > > This part > > “ + * The dp_netdev_flow reference in the matching emc_entry also > stores > + * the dpcls_rule that corresponds to the miniflow.” > > is clearer. > > + * A miniflow with a given hash can be stored in any one of > EM_FLOW_HASH_SEGS > + * different entries. The 32-bit hash is split into EM_FLOW_HASH_SEGS > values > + * (each of which is EM_FLOW_HASH_SHIFT bits wide - the remainder is > thrown > + * away). Each value is the index of a cache entry where the miniflow > could be > + * stored. > * > - * A miniflow with a given hash can be in one of EM_FLOW_HASH_SEGS > different > - * entries. The 32-bit hash is split into EM_FLOW_HASH_SEGS values (each > of > - * them is EM_FLOW_HASH_SHIFT bits wide and the remainder is thrown > away). Each > - * value is the index of a cache entry where the miniflow could be. > + * For example, assuming that EM_FLOW_HASH_SHIFT is 13 and > EM_FLOW_HASH_SEGS is > + * 2, an entry with 32-bit hash of 0xDEADBEEF could be stored at either > + * entries[0x156D] or entries[0x1EEF]. > > entries[0x1EEF] or entries[0x156D]. > > The indices are derived from bits 0-12 > + * and bits 13-25 of the 32-bit hash respectively. Bits 26-31 are ignored. > Both > + * entries have to be checked with netdev_flow_key_equal() to find the > actual > + * match. Note: bits 0 and 31 are the least and most significant bits > + * respectively of the 32 bit hash value. > * > + * It follows from the search indices being generated from n bits that the > + * number of entries in the cache must be a power of two. > > The added comments from “A miniflow with a given hash” seem obvious and > also a bit micro-detailed, such that they could easily become outdated, if not > carefully maintained. > For instance, the example is based on present cache size (although, the > wording uses “assuming”) which may change and hence the example would > probably need to be updated, else it might cause confusion that would not > otherwise exist. > If folks feel strongly that these added comments help them, then they can > ack it and we can include them. > > > * > * Thread-safety > * ============= > -- > 2.7.4 > > _______________________________________________ > dev mailing list > dev@openvswitch.org > https://urldefense.proofpoint.com/v2/url?u=https- > 3A__mail.openvswitch.org_mailman_listinfo_ovs- > 2Ddev&d=DwICAg&c=uilaK90D4TOVoH58JNXRgQ&r=BVhFA09CGX7JQ5Ih- > uZnsw&m=8NtshUOoQuDvlKk0AzLtHL6N2FKmM4uWibENQmf8XOc&s=LrVJc > 9AzeZ4lJPNSehSvQUrb8J2hvZec-QQOuxB4W8o&e= > > >
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index 7d53a8d..d99eec7 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -124,16 +124,26 @@ struct netdev_flow_key { /* Exact match cache for frequently used flows * * The cache uses a 32-bit hash of the packet (which can be the RSS hash) to - * search its entries for a miniflow that matches exactly the miniflow of the - * packet. It stores the 'dpcls_rule' (rule) that matches the miniflow. + * search its entries for the miniflow that matches exactly the miniflow of the + * packet. The dp_netdev_flow reference in the matching emc_entry also stores + * the dpcls_rule that corresponds to the miniflow. * - * A cache entry holds a reference to its 'dp_netdev_flow'. + * A miniflow with a given hash can be stored in any one of EM_FLOW_HASH_SEGS + * different entries. The 32-bit hash is split into EM_FLOW_HASH_SEGS values + * (each of which is EM_FLOW_HASH_SHIFT bits wide - the remainder is thrown + * away). Each value is the index of a cache entry where the miniflow could be + * stored. * - * A miniflow with a given hash can be in one of EM_FLOW_HASH_SEGS different - * entries. The 32-bit hash is split into EM_FLOW_HASH_SEGS values (each of - * them is EM_FLOW_HASH_SHIFT bits wide and the remainder is thrown away). Each - * value is the index of a cache entry where the miniflow could be. + * For example, assuming that EM_FLOW_HASH_SHIFT is 13 and EM_FLOW_HASH_SEGS is + * 2, an entry with 32-bit hash of 0xDEADBEEF could be stored at either + * entries[0x156D] or entries[0x1EEF]. The indices are derived from bits 0-12 + * and bits 13-25 of the 32-bit hash respectively. Bits 26-31 are ignored. Both + * entries have to be checked with netdev_flow_key_equal() to find the actual + * match. Note: bits 0 and 31 are the least and most significant bits + * respectively of the 32 bit hash value. * + * It follows from the search indices being generated from n bits that the + * number of entries in the cache must be a power of two. * * Thread-safety * =============
Add a concrete example of how a flow's hash determines the set of possible storage locations in the EMC. Signed-off-by: Billy O'Mahony <billy.o.mahony@intel.com> --- lib/dpif-netdev.c | 24 +++++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-)