lkml.org 
[lkml]   [2015]   [May]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [PATCH 1/2] rcu: introduce list_last_or_null_rcu
On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney
<paulmck@linux.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@linux.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@goodmis.org> wrote:
>> >> > On Thu, 28 May 2015 16:35:27 -0400
>> >> > Dan Streetman <ddstreet@ieee.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
>


\
 
 \ /
  Last update: 2015-05-29 16:01    [W:0.078 / U:12.152 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site