Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753899AbbFAWMS (ORCPT ); Mon, 1 Jun 2015 18:12:18 -0400 Received: from mail-qg0-f53.google.com ([209.85.192.53]:35548 "EHLO mail-qg0-f53.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751889AbbFAWMM (ORCPT ); Mon, 1 Jun 2015 18:12:12 -0400 MIME-Version: 1.0 In-Reply-To: <20150601181758.GW5989@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> <20150601181758.GW5989@linux.vnet.ibm.com> From: Dan Streetman Date: Mon, 1 Jun 2015 18:11:50 -0400 X-Google-Sender-Auth: 0BGRW6KcMXlQMQTjMwHdpbCr2ZM Message-ID: Subject: Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu To: Paul McKenney Cc: Steven Rostedt , Andrew Morton , Josh Triplett , Mathieu Desnoyers , Lai Jiangshan , linux-kernel Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5951 Lines: 116 On Mon, Jun 1, 2015 at 2:17 PM, Paul E. McKenney wrote: > 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. Ok. Since in my case there will only be 1 entry (or at worst just a few) in the list in the majority of cases, I'll just stick to manually iterating to the last entry. It's easy and clear. Thanks! > > 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/