Message-ID: <CALZtONAS1KaS5hJGpLqJcOXnY9rQFT0O_j9D0-qwORNmOyNBfA@mail.gmail.com>
Date:	Fri, 29 May 2015 09:40:43 -0400
From:	Dan Streetman <ddstreet@...e.org>
To:	Paul McKenney <paulmck@...ux.vnet.ibm.com>
Cc:	Steven Rostedt <rostedt@...dmis.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Josh Triplett <josh@...htriplett.org>,
	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
	Lai Jiangshan <laijs@...fujitsu.com>,
	linux-kernel <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney
<paulmck@...ux.vnet.ibm.com> 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
>> <paulmck@...ux.vnet.ibm.com> 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 <rostedt@...dmis.org> wrote:
>> >> > On Thu, 28 May 2015 16:35:27 -0400
>> >> > Dan Streetman <ddstreet@...e.org> 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?



>
>                                                         Thanx, Paul
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists