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:[email protected]] > Sent: Saturday, May 13, 2017 8:33 PM > To: O Mahony, Billy <[email protected]>; [email protected] > Subject: Re: [ovs-dev] [PATCH] dpif-netdev: emc comments > > Thanks for the patch Billy > > On 3/30/17, 3:20 AM, "[email protected] on behalf of Billy > O'Mahony" <[email protected] on behalf of > [email protected]> 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 <[email protected]> > --- > 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 > [email protected] > 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= > > > _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
