On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney <[email protected]> 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 >> <[email protected]> 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 <[email protected]> >> >> wrote: >> >> > On Thu, 28 May 2015 16:35:27 -0400 >> >> > Dan Streetman <[email protected]> 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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
