Re: Question regarding hash_resize

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

On Tue, Jan 08, 2019 at 06:59:13PM -0800, Paul E. McKenney wrote:
> 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...

Seems to be stable.  I have not yet updated the text.  I am currently
looking into whether I can get rid of ->ht_resize_cur.  In theory, this
would make it trivial to make the resizing "pause", releasing the lock
from time to time.

For whatever it is worth...

							Thanx, Paul