Re: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys

[Ola Liljedahl <Ola.Liljedahl@arm.com>]

On 03/10/2018, 20:00, "Wang, Yipeng1" <yipeng1.wang@intel.com> wrote:

    
    
    >-----Original Message-----
    >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
    >Sent: Wednesday, October 3, 2018 10:33 AM
    >To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Van Haaren, Harry <harry.van.haaren@intel.com>; Richardson, Bruce
    ><bruce.richardson@intel.com>
    >Cc: De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>; dev@dpdk.org; Gavin Hu (Arm Technology China)
    ><Gavin.Hu@arm.com>; Steve Capper <Steve.Capper@arm.com>; Ola Liljedahl <Ola.Liljedahl@arm.com>; nd <nd@arm.com>; Gobriel,
    >Sameh <sameh.gobriel@intel.com>
    >Subject: RE: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys
    >
    >> >-----Original Message-----
    >> >From: Van Haaren, Harry
    >> >> > > > > /**
    >> >> > > > >  * Add a key to an existing hash table.
    >> >> > > > >@@ -222,7 +222,7 @@ rte_hash_add_key(const struct rte_hash *h,
    >> >> > > > >const void
    >> >> > > *key);
    >> >> > > > >  *     array of user data. This value is unique for this key.
    >> >> > > > >  */
    >> >> > > > > int32_t
    >> >> > > > >-rte_hash_add_key_with_hash(const struct rte_hash *h, const
    >> >> > > > >void *key,
    >> >> > > hash_sig_t sig);
    >> >> > > > >+rte_hash_add_key_with_hash(struct rte_hash *h, const void
    >> >> > > > >+*key,
    >> >> > > hash_sig_t sig);
    >> >> > > > >
    >> >> > > > > /
    >> >> > > >
    >> >> > > > I think the above changes will break ABI by changing the
    >> >> > > > parameter
    >> >> type?
    >> >> > > Other people may know better on this.
    >> >> > >
    >> >> > > Just removing a const should not change the ABI, I believe, since
    >> >> > > the const is just advisory hint to the compiler. Actual parameter
    >> >> > > size and count remains unchanged so I don't believe there is an issue.
    >> >> > > [ABI experts, please correct me if I'm wrong on this]
    >> >> >
    >> >> >
    >> >> > [Certainly no ABI expert, but...]
    >> >> >
    >> >> > I think this is an API break, not ABI break.
    >> >> >
    >> >> > Given application code as follows, it will fail to compile - even
    >> >> > though
    >> >> running
    >> >> > the new code as a .so wouldn't cause any issues (AFAIK).
    >> >> >
    >> >> > void do_hash_stuff(const struct rte_hash *h, ...) {
    >> >> >     /* parameter passed in is const, but updated function prototype
    >> >> > is
    >> >> non-
    >> >> > const */
    >> >> >     rte_hash_add_key_with_hash(h, ...); }
    >> >> >
    >> >> > This means that we can't recompile apps against latest patch
    >> >> > without application code changes, if the app was passing a const
    >> >> > rte_hash struct
    >> >> as
    >> >> > the first parameter.
    >> >> >
    >> >> Agree. Do we need to do anything for this?
    >> >
    >> >I think we should try to avoid breaking API wherever possible.
    >> >If we must, then I suppose we could follow the ABI process of a
    >> >deprecation notice.
    >> >
    >> >From my reading of the versioning docs, it doesn't document this case:
    >> >https://doc.dpdk.org/guides/contributing/versioning.html
    >> >
    >> >I don't recall a similar situation in DPDK previously - so I suggest
    >> >you ask Tech board for input here.
    >> >
    >> >Hope that helps! -Harry
    >> [Wang, Yipeng]
    >> Honnappa, how about use a pointer to the counter in the rte_hash struct
    >> instead of the counter? Will this avoid API change?
    >I think it defeats the purpose of 'const' parameter to the API and provides incorrect information to the user.
    >IMO, DPDK should have guidelines on how to handle the API compatibility breaks. I will send an email to tech board on this.
    >We can also solve this by having counters on the bucket. I was planning to do this little bit later. I will look at the effort involved and
    >may be do it now.
    [Wang, Yipeng] 
    I think with ABI/API change, you might need to announce it one release cycle ahead.
    
    In the cuckoo switch paper: Scalable, High Performance Ethernet Forwarding with
    CUCKOOSWITCH
    it separates the version counter array and the hash table. You can strike a balance
    between granularity of the version counter and the cache/memory requirement.
    Is it a better way?
[Ola] Having only a single generation counter can easily become a scalability bottleneck due to write contention to the cache line.
Ideally you want each gen counter to be located in its own cache line (multiple gen counters in the same cache line will experience the same write contention). But that seems a bit wasteful of memory.
Ideally (in order to avoid accessing more cache lines), the gen counter should be located in the hash bucket. But as you write below, this would create problems for the layout of the hash bucket, there isn't any room for another field.
So I propose an array of gen. counters, indexed by the hash (of somekind) of primary and alternate hashes (signatures) of the element (modulo the array size). So another hash table.
    
    Another consideration is current bucket is 64-byte exactly with the partial-key-hashing.
    To add another counter, we need to think about changing certain variables to still align
    cache line.