RFC: patch to allow lock-free traversal of lists with insertion
Quoted 5 lines · In article <[email protected]>…
Quoted 3 lines · Rusty Russell
If noone *holds* a reference, you can remove it "sometime later", where "sometime later" is (for example) after every CPU has scheduled.
Quoted 7 lines
Ehh.. One of those readers can hold on to the thing while waiting for something else to happen.
Looking up a data structure and copying it to user space or similar is _the_ most common operation for any lookup. You MUST NOT free it just because we scheduled away. Scheduling points have zero meaning in real life.
How does locking inside the kernel help you here ? You could face the same situation even if you protect the data by locking. Perhaps, I am missing something here. So, a specific example would help.
Quoted 4 lines
So you'll need a reference count to actually keep such a data structure alive _over_ a schedule. Or all the readers need to copy the data too before they actually start using it. At which point you've made your code a _lot_ slower than the locking version.
Only relevant issue I can see here is preemption - if you hold a reference and get preempted out it is still a context switch and the logic of "when the data can be really deleted" must take into account such context switches. Alternatively, you could disable preemption while traversing such lists.
Thanks
Dipankar
Signature · 2 lines
Dipankar Sarma <[email protected]> Project: http://lse.sourceforge.net Linux Technology Center, IBM Software Lab, Bangalore, India.
Quoted 4 lines · Dipankar Sarma
How does locking inside the kernel help you here ? You could face the same situation even if you protect the data by locking. Perhaps, I am missing something here. So, a specific example would help.
Oh, absolutely.
In the kernel, the regular usage is that we
lock
lookup
increment usage count
unlock
and then the freeing is done with either
if (atomic_dec_and_lock()) {
unhash
unlock;
free
}or
lock
unhash
unlock
if (atomic_dec()) {
free
}that's the basic pattern for most data structures.
Yes, there are data structures that don't have refcounts. They aren't on any global lists either, or they are buggy.
Now, with the lockless approach, the issue is that you _cannot_ just free the thing on next schedule. You have to honor the reference count, which means that either you have different "bins" for all different kinds of users of RCU data structures (different "free" functions), or they all have the reference count in a generic place for RCU.
The latter is probably pretty doable.
Quoted 5 lines
Only relevant issue I can see here is preemption - if you hold a reference and get preempted out it is still a context switch and the logic of "when the data can be really deleted" must take into account such context switches. Alternatively, you could disable preemption while traversing such lists.
You have to disable pre-emption some way. The kernel does that by default by not pre-empting kernel space, but it's easy enough to do other ways. And you can (have to, in fact) use cpu-local data structures for it.
Locking does the same thing.
For RCU to work, it has to do all the things that locking guarantees. It can try to do more of them locally, but that reference count increment _is_ going to be a global atomic update, so it's not as if you can avoid them all.
However, it should be noted that even if you add refcounts to RCU, which makes them useful outside of atomic readers, you'll still find that most of the really core kernel data structures need locking anyway: locking not only protects the list traversal, it also is used to guarantee uniqueness which is important for a lot of the data structures - inodes, buffers, pages, etc all absolutely depend on the fact that the data structure is unique (ie there had better _not_ be two pages in the page cache with the same indexes, even if one process removes an old version at the same time as another process tries to look it up and create it if necessary).
So I'm still at a loss for what this could actually be _used_. IP routing? Certainly not sockets (which have uniqueness requirements).
Linus
Quoted 6 lines · On Wed, 10 Oct 2001 03:18:23 -0700 (PDT) Linus Torvalds…
lock
unhash
unlock
if (atomic_dec()) {
free
}And the read side is:
lock
loopup
atomic_inc
unlock
With RCU, read side is:
loopup
atomic_inc
Write is:
lock /* protect against other writes */
unhash /* be careful with wmb()s here... */ unlock
call_rcu(if (atomic_dec()) free) /* ie. does this later */
Clear?
Rusty.
Quoted 10 lines · Rusty Russell
And the read side is:
lock
loopup
atomic_inc
unlockWith RCU, read side is:
loopup
atomic_inc
Yes. With maybe
non_preempt() .. preempt()
around it for the pre-emption patches.
However, you also need to make your free _free_ be aware of the count. Which means that the current RCU patch is really unusable for this. You need to have the "count" always in a generic place (put it with the hash), and your schedule-time free needs to do
if (atomic_read(&count))
skip_this_do_it_next_time
which starts getting complicated (it means your RCU free now has to have a notion of "next time" - just leaving the RCU active will slow down scheduling for as long as any reader holds on to an entry). So your unread() path probably has to be
if (atomic_dec_and_test(&count)) free_it()
and the act of hashing should add a count and unhashing should delete a count (so that the reader doesn't free it while it is hashed).
Do that, and the RCU patches may start looking usable for the real world.
Linus
In message <[email protected]> you
write:
Quoted 7 lines
Yes. With maybe
non_preempt() .. preempt()around it for the pre-emption patches.
Sure, if they want pre-emption on SMP. Of course, then they'll want priority inheritence.
Quoted 7 lines
However, you also need to make your free _free_ be aware of the count. Which means that the current RCU patch is really unusable for this. You need to have the "count" always in a generic place (put it with the hash), and your schedule-time free needs to do
if (
atomic_read(&count))
skip_this_do_it_next_time
WTF? I'll spell it out for you again:
static inline void foo_put(struct foo *foo)
{
if (atomic_dec_and_test(foo->use))
kfree(foo);
}Write side normal:
lock
unhash(foo)
unlock
foo_put(foo)
Write side RCU:
lock unhash(foo) unlock rcu_call(foo_put, foo); /* ie. call foo_put(foo) "later". */
That's all. Really.
Quoted 1 line
Do that, and the RCU patches may start looking usable for the real world.
I know you're under strain, but think harder please.
Rusty.
--
Premature optmztion is rt of all evl. --DK
Quoted 8 lines · Linus Torvalds
Yes. With maybe
non_preempt() .. preempt()around it for the pre-emption patches.
Yes. While in the read side, preemption will have to be disabled to prevent local pointers being carried across context switches. It isn't impossible to allow preemption, but that makes the quiescent point detection logic much more complicated.
Quoted 14 lines
However, you also need to make your free _free_ be aware of the count. Which means that the current RCU patch is really unusable for this. You need to have the "count" always in a generic place (put it with the hash), and your schedule-time free needs to do
if (
atomic_read(&count))
skip_this_do_it_next_timewhich starts getting complicated (it means your RCU free now has to have a notion of "next time" - just leaving the RCU active will slow down scheduling for as long as any reader holds on to an entry). So your
unread()path probably has to be
Quoted 5 lines
if (atomic_dec_and_test(&count)) free_it()and the act of hashing should add a count and unhashing should delete a count (so that the reader doesn't free it while it is hashed).
Perhaps I am missing something here but shouldn't the refcount based schemes anyway have to do this with or without RCU ? If you do
unhash if (atomic_dec_and_test(&count)) free_it();
the isn't it that if refcount is not 0, sometime later it will have to be cleaned up by some garbage collection scheme ? Whatever that scheme is, it still needs to be made certain that the element is not back in the hash table. It seems to me that with RCU the same logic can be made use of. So instead of doing
if (atomic_dec_and_test(&count)) rcu_free_it()
you may do
if (atomic_dec_and_test(&count)) free_it();
where in free_it()
if (atomic_read(&count)) return; rcu_free_it();
Of course, there may be more complicated freeing schemes for which we may need additional logic just like you suggested.
Quoted 3 lines
Do that, and the RCU patches may start looking usable for the real world.
One RCU example for refcount + hash table is at
http://lse.sourceforge.net/locking/patches/rt_rcu-2.4.6-02.patch
(ipv4 route cache).
Thanks
Dipankar
Signature · 2 lines
Dipankar Sarma <[email protected]> Project: http://lse.sourceforge.net Linux Technology Center, IBM Software Lab, Bangalore, India.
Quoted 24 lines · Linus Torvalds
Quoted 4 lines · Dipankar Sarma
How does locking inside the kernel help you here ? You could face the same situation even if you protect the data by locking. Perhaps, I am missing something here. So, a specific example would help.
Oh, absolutely.
In the kernel, the regular usage is that we
lock
lookup
increment usage count
unlockand then the freeing is done with either
if (atomic_dec_and_lock()) { unhash unlock; free }
Quoted 4 lines
that's the basic pattern for most data structures.
Yes, there are data structures that don't have refcounts. They aren't on any global lists either, or they are buggy.
Ok, I get it now. You are talking about the situation where we may not be able to update *all* the global pointers to the data before they are "deferred deleted". I think once such example is the ipv4 route cache dst entry we have to honor the refcounts.
Quoted 8 lines
Now, with the lockless approach, the issue is that you _cannot_ just free the thing on next schedule. You have to honor the reference count, which means that either you have different "bins" for all different kinds of users of RCU data structures (different "free" functions), or they all have the reference count in a generic place for RCU.
The latter is probably pretty doable.
Agreed. One approach I took for my experimental ipv4 route cache code was to do "deferred delete" *after* refcount becomes zero. I am not sure whether this is possible in all scenerios, but the my understanding is that if you remove the global pointers (like hash table links) to data to prevent new references and do a "deferred delete" after refcount becomes zero, it would work. Of course, I am in no position to make a generalized comment on this.
Quoted 9 lines
Quoted 5 lines
Only relevant issue I can see here is preemption - if you hold a reference and get preempted out it is still a context switch and the logic of "when the data can be really deleted" must take into account such context switches. Alternatively, you could disable preemption while traversing such lists.
You have to disable pre-emption some way. The kernel does that by default by not pre-empting kernel space, but it's easy enough to do other ways. And you can (have to, in fact) use cpu-local data structures for it.
That is what the preemption patch allows (atleast when I last looked at it).
Quoted 9 lines
However, it should be noted that even if you add refcounts to RCU, which makes them useful outside of atomic readers, you'll still find that most of the really core kernel data structures need locking anyway: locking not only protects the list traversal, it also is used to guarantee uniqueness which is important for a lot of the data structures - inodes, buffers, pages, etc all absolutely depend on the fact that the data structure is unique (ie there had better _not_ be two pages in the page cache with the same indexes, even if one process removes an old version at the same time as another process tries to look it up and create it if necessary).
Uniqueness can be ensured even with RCU, albeit it is not very straitforward. One common technique we used was to mark elements deleted *before* updating global pointers. However this usually requires you to lock the element (not the list itself) while reading its contents.
Quoted 3 lines
So I'm still at a loss for what this could actually be _used_. IP routing? Certainly not sockets (which have uniqueness requirements).
Yes. We used it in IP routing in DYNIX/ptx back then at Sequent as well as for Multipath I/O routes for storage. That is all I can remember, but Paul will remember and know more about it. Paul ?
Thanks
Dipankar
Signature · 2 lines
Dipankar Sarma <[email protected]> Project: http://lse.sourceforge.net Linux Technology Center, IBM Software Lab, Bangalore, India.