[ovs-dev] [PATCH] dpif-netdev: emc comments

[O Mahony, Billy]

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 at vmware.com]
> Sent: Saturday, May 13, 2017 8:33 PM
> To: O Mahony, Billy <billy.o.mahony at intel.com>; dev at 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 at openvswitch.org on behalf of Billy
> O'Mahony" <ovs-dev-bounces at openvswitch.org on behalf of
> billy.o.mahony at 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 at 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 at 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=
> 
> 
>