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@xxxxxxxxx> 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
