Re: Question regarding hash_resize

["Paul E. McKenney" <paulmck@linux.ibm.com>]

On Tue, Jan 08, 2019 at 04:19:59PM -0800, Paul E. McKenney wrote:
> On Wed, Jan 09, 2019 at 07:16:05AM +0900, Akira Yokosawa wrote:
> > On 2019/01/08 10:39:31 -0800, Paul E. McKenney wrote:
> > > On Wed, Jan 09, 2019 at 12:35:37AM +0900, Akira Yokosawa wrote:
> > >> On 2019/01/09 0:28, Paul E. McKenney wrote:
> > >>> On Tue, Jan 08, 2019 at 09:56:57AM +0800, Junchang Wang wrote:
> > >>>> On Tue, Jan 8, 2019 at 7:06 AM Akira Yokosawa <akiyks@gmail.com> wrote:
> > >>>>> On 2019/01/08 07:54:16 +0900, Akira Yokosawa wrote:
> 
> [ . . . ]
> 
> > >>>> Hi Paul and Akira,
> > >>>>
> > >>>> Thanks a lot for the comments, which I need some more time to look
> > >>>> into. For Paul's patch, I have a few concerns. Please take a look.
> > >>>>
> > >>>> My understanding is that with this path, during the time period when
> > >>>> the resizing thread is running, an updater may insert/delete an item
> > >>>> into/from the new hash table, while readers are still looking up data
> > >>>> in the old one, resulting the readers are unaware of
> > >>>> insertions/deletions happening simultaneously. For example, it seems
> > >>>> the following sequence could happen.
> > >>>>
> > >>>> 1. The resizing thread starts.
> > >>>> 2. The resizing thread successfully passes bucket *B* of the old hash table.
> > >>>> 3. An updater wants to insert a new item *I* which should be inserted
> > >>>> into bucket *B*.
> > >>>> 4. The updater will select the new hash table and insert the item *I*
> > >>>> into the new hash table.
> > >>>> 5. A read request comes in and wants to lookup item *I*. The lookup
> > >>>> request will check the old hash table and fail. Doesn't it?
> > >>>> 6. The resizing thread exits.
> > >>>> 7. Now subsequent read requests can successfully find item *I*.
> > >>>
> > >>> Yes, this can happen.
> > >>>
> > >>>> Is my understanding correct? Please let me know if I misunderstood
> > >>>> anything. Give the truth that this patch can accelerate the fast path,
> > >>>> I think it should be OK because resizing is typically happen rarely.
> > >>>> Just want to make sure I fully understand the algorithm.
> > >>>
> > >>> It is a design choice, and some users would prefer not to fail to see
> > >>> new items during a resize.  One approach would be to revert back to
> > >>> the old-style checking, and another would be to provide a separate
> > >>> lookup interface that synchronizes with adds and deletes.
> > >>>
> > >>> So, I could add a quick quiz with this information, I could revert the
> > >>> change, or I could add another lookup function that provided more timely
> > >>> information.  Left to myself, I would provide a quick quiz, but what
> > >>> do you guys think?
> > >>
> > >> Hi, I was composing a message, but now I'm replying to this one.
> > >> I think adding a quick quiz would be a good idea.
> > > 
> > > But in the meantime, it occurred to me that I was looking at the
> > > problem in the wrong way.  I believe that the following patch makes
> > > hashtab_lookup() find elements recently added by hashtab_add(), even
> > > during a resize, and without the need for memory barriers.
> > > 
> > > The scenario that convinced me to take this approach is when a thread
> > > does hashtab_add(), then immediately searches for the newly added element.
> > > Failing to find it would be quite a surprise to most people.
> > 
> > When a thread does hashtab_del() and immediately checks the deletion,
> > it still finds the deleted element while resizing is in progress.
> > This would also be a surprise. Current version looks less consistent
> > than the simpler one did.
> 
> I bet I can fix that...  Famous last words!  ;-)
> 
> But please see below and tell me what you think.

Well, that is not quite right, but close.  Working on it...

							Thanx, Paul

> ------------------------------------------------------------------------
> 
> diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> index 6dbfe020d78d..632d9e27675b 100644
> --- a/CodeSamples/datastruct/hash/hash_resize.c
> +++ b/CodeSamples/datastruct/hash/hash_resize.c
> @@ -257,9 +257,12 @@ void hashtab_add(struct ht_elem *htep,			//\lnlbl{add:b}
>  void hashtab_del(struct ht_elem *htep,			//\lnlbl{del:b}
>                   struct ht_lock_state *lsp)
>  {
> -	int i = lsp->hls_idx[!!lsp->hbp[1]];		//\lnlbl{del:i}
> +	int new = !!lsp->hbp[1];			//\lnlbl{del:new}
> +	int i = lsp->hls_idx[new];			//\lnlbl{del:i}
>  
>  	cds_list_del_rcu(&htep->hte_next[i]);		//\lnlbl{del:del}
> +	if (new)
> +		cds_list_del_rcu(&htep->hte_next[!i]);	//\lnlbl{del:del}
>  }							//\lnlbl{del:e}
>  //\end{snippet}
>