Skip to contentSkip to conversation

RFC: patch to allow lock-free traversal of lists with insertion

Lse-tech Dipankar Sarma 3 participants 7 messages Oct 10, 2001 – Oct 13, 2001

lore
Share & tools
lore
#0 lore raw
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.
#1 lore raw
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

#2 lore raw
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.

#3 lore raw
Quoted 10 lines · Rusty Russell

And the read side is:
lock
loopup
atomic_inc
unlock

With 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

#4 lore raw

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

#5 lore raw
In reply to Rusty Russell
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_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

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.
#6 lore raw
In reply to Dipankar Sarma
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
unlock

and 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.