linux-kernel - Re: [PATCH 1/2] rcu: introduce list_last_or_null

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CALZtONC5QGcme4LuQBf7Kty7AS9vBmw8RUqKeznobir5cAgP7Q@mail.gmail.com>
Date:	Thu, 28 May 2015 19:22:59 -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.

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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/