Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753694AbbFASSQ (ORCPT ); Mon, 1 Jun 2015 14:18:16 -0400 Received: from e38.co.us.ibm.com ([32.97.110.159]:48817 "EHLO e38.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753547AbbFASSG (ORCPT ); Mon, 1 Jun 2015 14:18:06 -0400 Date: Mon, 1 Jun 2015 11:17:58 -0700 From: "Paul E. McKenney" To: Dan Streetman Cc: Steven Rostedt , Andrew Morton , Josh Triplett , Mathieu Desnoyers , Lai Jiangshan , linux-kernel Subject: Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu Message-ID: <20150601181758.GW5989@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <1432845328-27932-1-git-send-email-ddstreet@ieee.org> <20150528170542.3b3a7b48@gandalf.local.home> <20150528211647.GO5989@linux.vnet.ibm.com> <20150528222931.GS5989@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 15060118-0029-0000-0000-00000A37BBE8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5506 Lines: 107 On Fri, May 29, 2015 at 09:40:43AM -0400, Dan Streetman wrote: > On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney > wrote: > > On Thu, May 28, 2015 at 05:24:14PM -0400, Dan Streetman wrote: > >> On Thu, May 28, 2015 at 5:16 PM, Paul E. McKenney > >> wrote: > >> > On Thu, May 28, 2015 at 05:12:00PM -0400, Dan Streetman wrote: > >> >> On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt wrote: > >> >> > On Thu, 28 May 2015 16:35:27 -0400 > >> >> > Dan Streetman wrote: > >> >> > > >> >> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a > >> >> >> rcu-protected list. The standard list_last_entry() can't be used as it > >> >> >> is not rcu-protected; the list may be modified concurrently. And the > >> >> >> ->prev pointer can't be used, as only the ->next pointers are protected > >> >> >> by rcu. > >> >> >> > >> >> >> This simply iterates forward through the entire list, to get to the last > >> >> >> entry. If the list is empty, it returns NULL. > >> >> > > >> >> > May I asked what this would be used for? It seems awfully inefficient > >> >> > in its implementation. What use cases would this be for? I hate to add > >> >> > something like this as a generic function which would encourage people > >> >> > to use it. Iterating over an entire list to find the last element is > >> >> > just nasty. > >> >> > >> >> i have a patch series that will update zswap to be able to change its > >> >> parameters at runtime, instead of only at boot time. To do that, it > >> >> creates new "pools" dynamically, and keeps them all in a list, with > >> >> only the 1st pool being actively used; any following pools still have > >> >> everything that was stored in them, but they aren't added to. When > >> >> zswap has to "shrink" - by telling one of the pools to get rid of 1 or > >> >> more items - it picks the last on the list. Once a pool is empty, > >> >> it's removed/freed. > >> >> > >> >> So zswap *could* just manually iterate the list to the last element, > >> >> instead of using this new function. But if rcu lists are ever > >> >> improved later on, e.g. if ->prev is somehow rcu-protected as well as > >> >> ->next, then this function should be faster than manually iterating. > >> >> > >> >> if there's a better rcu-way to get to the last list entry, then we > >> >> should definitely use it, although based on my understanding of the > >> >> rcu list implementation, you can only iterate forwards, safely > >> >> (without locking). > >> > > >> > The usual approach would be to maintain a tail pointer. How big are > >> > these lists likely to get? > >> > >> in the vast majority of cases, it'll only be 1 entry; the list is only > >> added to when the user decides to change the pool type or compression > >> function, which during normal operation will probably happen very > >> rarely. So in most situations, the function will just be a 1-step for > >> loop. I'm only proposing this function since it may be useful to > >> optimize last-rcu-entry access later, and maybe for other users. > > > > Fair enough. > > > >> re: keeping a rcu-safe tail pointer, how is that done? i assume since > >> head->prev isn't rcu protected (is it?), it would need to be separate > >> from the list, and thus would need to be spinlock-protected and > >> updated at each list update? > > > > Yep, each update that changed the tail would need to change the tail > > pointer, and that would need to be protected from other updates. > > > > But if the lists were long, one approach would be to provide a > > list_del_rcu_bidir() or some such that didn't poison the ->prev pointer, > > and then use rcu_dereference() to traverse the head element's ->prev > > pointer, as you suggested above. I have resisted doing that due to > > debugging issues, but if there turns out to be a strong need, let's talk. > > I was thinking; since the head element is never removed, its ->prev > pointer will never be poisoned; is something like this safe? > > /* this can only be called on the head, not on any entry; > * specifically this is not safe to call on any entry that > * may be removed with list_del_rcu() or list_replace_rcu(). > */ > #define list_last_or_null_rcu(head, type, member) \ > ({ \ > struct list_head *__last = (head)->prev; \ > __last != (head) ? list_entry_rcu(__last) : NULL; \ > }) > > I was thinking that's unsafe because the head->prev pointer can be > updated directly, such as during list_del_rcu(last_entry) which will > directly reassign head->prev to the new last entry; but maybe that is > ok since list_del_rcu(first_entry) also directly reassigns head->next > to the new first entry? In your particular case, it would be safe, but people can and do call list_del_rcu() on the header in order to remove the entire list, which would poison the header's ->prev pointer. So if you really want to do this in your own code, fine, but please: (1) include a big fat comment saying what you are doing and the resulting restrictions and (2) Name it something specific to your code. If multiple similar use cases show up, maybe we can add something to the rculist_nulls.h file. Thanx, Paul -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/