Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney
<paulmck@xxxxxxxxxxxxxxxxxx> 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@xxxxxxxxxxxxxxxxxx> 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@xxxxxxxxxxx> wrote:
>> >> > On Thu, 28 May 2015 16:35:27 -0400
>> >> > Dan Streetman <ddstreet@xxxxxxxx> 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.

In my case, there's certainly no strong need.  So this patch can be ignored.

Thnx!

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