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

[Dan Streetman]

On Mon, Jun 1, 2015 at 2:17 PM, Paul E. McKenney
<paulmck@xxxxxxxxxxxxxxxxxx> 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
>> <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.
>>
>> 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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/