From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0b-001b2d01.pphosted.com ([148.163.158.5]:56402 "EHLO mx0a-001b2d01.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1728129AbfAKEI3 (ORCPT ); Thu, 10 Jan 2019 23:08:29 -0500 Received: from pps.filterd (m0098414.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id x0B44lmE119916 for ; Thu, 10 Jan 2019 23:08:27 -0500 Received: from e11.ny.us.ibm.com (e11.ny.us.ibm.com [129.33.205.201]) by mx0b-001b2d01.pphosted.com with ESMTP id 2pxgf1pcwv-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Thu, 10 Jan 2019 23:08:27 -0500 Received: from localhost by e11.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Fri, 11 Jan 2019 04:08:27 -0000 Date: Thu, 10 Jan 2019 20:08:22 -0800 From: "Paul E. McKenney" Subject: Re: Question regarding hash_resize Reply-To: paulmck@linux.ibm.com References: <20190107183317.GB1215@linux.ibm.com> <63181ff3-bcfa-0819-460a-867e438a22f7@gmail.com> <6d75361a-8a7f-1190-0c34-dccb7e2dea01@gmail.com> <20190108152846.GN1215@linux.ibm.com> <20190108183931.GR1215@linux.ibm.com> <288a7aca-75ba-d9ba-297b-5bbd98054d5f@gmail.com> <20190109001959.GS1215@linux.ibm.com> <20190109025913.GA7904@linux.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20190109025913.GA7904@linux.ibm.com> Message-Id: <20190111040822.GA23716@linux.ibm.com> Sender: perfbook-owner@vger.kernel.org List-ID: To: Akira Yokosawa Cc: Junchang Wang , perfbook@vger.kernel.org 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 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