Skip to contentSkip to conversation

Allow lockless traversal of notifier lists

PATCH In review Andi Kleen 2 participants 8 messages Nov 28, 2005 – Nov 29, 2005

lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

PATCH 1/1 Allow lockless traversal of notifier lists

As discussed in other thread.

Just needed an additional write barrier, so that a parallel running lockup can never see inconsistent state. As long as there is no unregistration or the unregistration is done using locking or RCU in the caller they should be ok now.

This only makes a difference on non i386/x86-64 architectures. x86 was already ok because it never reorders writes.

That's the first step for fixing all the callers. Some that already don't unregister or do it safely are already ok.

Also fixed up the kerneldoc description to document the various locking restriction.

Signed-off-by Andi Kleen <[email protected]>
kernel/sys.c renamed from kernel/sys.c-o +6 -0
diff -u linux-2.6.15rc2-work/kernel/sys.c-o linux-2.6.15rc2-work/kernel/sys.c
@@ -102,6 +102,9 @@
  *	@n: New entry in notifier chain
  *
  *	Adds a notifier to a notifier chain.
+ *	As long as unregister is not used this is safe against parallel
+ *	lockless notifier lookups. If unregister is used then unregister
+ *	needs to do additional locking or use RCU.
  *
  *	Currently always returns zero.
  */

@@ -116,6 +119,7 @@
 		list= &((*list)->next);
 	}
 	n->next = *list;
+	wmb();
 	*list=n;
 	write_unlock(&notifier_lock);
 	return 0;

@@ -129,6 +133,8 @@
  *	@n: New entry in notifier chain
  *
  *	Removes a notifier from a notifier chain.
+ *	Note this needs additional locking or RCU in the caller to be safe
+ * 	against parallel traversals.
  *
  *	Returns zero on success, or %-ENOENT on failure.
  */
#1 lore raw
Quoted 15 lines · Andi Kleen

As discussed in other thread.

Just needed an additional write barrier, so that a parallel running lockup can never see inconsistent state. As long as there is no unregistration or the unregistration is done using locking or RCU in the caller they should be ok now.

This only makes a difference on non i386/x86-64 architectures. x86 was already ok because it never reorders writes.

*
* Currently always returns zero.
*/

kernel/sys.c line 124

Quoted 6 lines
kernel/sys.c renamed from kernel/sys.c-o +1 -0
@@ -116,6 +119,7 @@
 		list= &((*list)->next);
 	}
 	n->next = *list;
+	wmb();
 	*list=n;
 	write_unlock(&notifier_lock);

Shouldn't this be smp_wmb() ?

Also, not all archs have strong ordering for data dependent reads. So, you would probably need an smp_read_barrier_depends() between the load of the pointer and actual dereferencing.

Thanks
Dipankar

author
#2 lore raw
Quoted 14 lines · Dipankar Sarma

Review line 124

Quoted 11 lines · Andi Kleen

*
* Currently always returns zero.
*/

(quoted diff) +1 -0
@@ -116,6 +119,7 @@
 		list= &((*list)->next);
 	}
 	n->next = *list;
+	wmb();
 	*list=n;
 	write_unlock(&notifier_lock);

Shouldn't this be smp_wmb() ?

Yes.

Quoted 2 lines

Also, not all archs have strong ordering for data dependent reads.

Ah you mean the Alpha exception? Right Alpha would need that.

Thanks for the review.

-Andi

Revised patch with Alphaextrawurst.

----
As discussed in other thread.

Just needed an additional write barrier, so that a parallel running lockup can never see inconsistent state. As long as there is no unregistration or the unregistration is done using locking or RCU in the caller they should be ok now.

This only makes a difference on non i386/x86-64 architectures. x86 was already ok because it never reorders writes.

kernel/sys.c renamed from kernel/sys.c-o +7 -0
diff -u linux-2.6.15rc2-work/kernel/sys.c-o linux-2.6.15rc2-work/kernel/sys.c
@@ -102,6 +102,9 @@
  *	@n: New entry in notifier chain
  *
  *	Adds a notifier to a notifier chain.
+ *	As long as unregister is not used this is safe against parallel
+ *	lockless notifier lookups. If unregister is used then unregister
+ *	needs to do additional locking or use RCU.
  *
  *	Currently always returns zero.
  */

@@ -116,6 +119,7 @@
 		list= &((*list)->next);
 	}
 	n->next = *list;
+	smp_wmb();
 	*list=n;
 	write_unlock(&notifier_lock);
 	return 0;

@@ -129,6 +133,8 @@
  *	@n: New entry in notifier chain
  *
  *	Removes a notifier from a notifier chain.
+ *	Note this needs additional locking or RCU in the caller to be safe
+ * 	against parallel traversals.
  *
  *	Returns zero on success, or %-ENOENT on failure.
  */

@@ -175,6 +181,7 @@
 
 	while(nb)
 	{
+		smp_read_barrier_depends();
 		ret=nb->notifier_call(nb,val,v);
 		if(ret&NOTIFY_STOP_MASK)
 		{
#3 lore raw

Review line 181

Quoted 5 lines · Andi Kleen

*
* Returns zero on success, or %-ENOENT on failure.
*/

(quoted diff) +0 -0
@@ -175,6 +181,7 @@

There should be an smp_read_barrier_depends() here for the first dereferencing of the notifier block head, I think.

kernel/sys.c line 187

Quoted 6 lines
kernel/sys.c renamed from kernel/sys.c-o +1 -0
 	while(nb)
 	{
+		smp_read_barrier_depends();
 		ret=nb->notifier_call(nb,val,v);
 		if(ret&NOTIFY_STOP_MASK)
 		{

Thanks
Dipankar

author
#4 lore raw
Quoted 9 lines · Dipankar Sarma

Review line 181

Quoted 5 lines · Andi Kleen

*
* Returns zero on success, or %-ENOENT on failure.
*/

(quoted diff) +0 -0
@@ -175,6 +181,7 @@

There should be an smp_read_barrier_depends() here for the first dereferencing of the notifier block head, I think.

Why? The one at the top of the block should be enough, shouldn' it?

-Andi

Quoted 10 lines

kernel/sys.c line 187

Quoted 7 lines
kernel/sys.c renamed from kernel/sys.c-o +1 -0
 	while(nb)
 	{
+		smp_read_barrier_depends();
 		ret=nb->notifier_call(nb,val,v);
 		if(ret&NOTIFY_STOP_MASK)
 		{

Thanks
Dipankar

#5 lore raw
Quoted 11 lines · Andi Kleen
Quoted 9 lines · Dipankar Sarma

Review line 181

Quoted 5 lines · Andi Kleen

*
* Returns zero on success, or %-ENOENT on failure.
*/

(quoted diff) +0 -0
@@ -175,6 +181,7 @@

There should be an smp_read_barrier_depends() here for the first dereferencing of the notifier block head, I think.

Quoted 2 lines

Why? The one at the top of the block should be enough, shouldn' it?

Don't we insert at the front of the list ? Shouldn't the read-side on alpha see the contents of the new notifier block before it sees the pointer to the first notifier block in the list head ?

Thanks
Dipankar

author
#6 lore raw
Quoted 3 lines · Dipankar Sarma

Don't we insert at the front of the list ? Shouldn't the read-side on alpha see the contents of the new notifier block before it sees the pointer to the first notifier block in the list head ?

Ok third version, hopefully Dipankar proof now.

Andrew, please consider applying.

-Andi

---

As discussed in other thread.

Notifiers could be locklessly traversed if there was no removal ever, except that the update order is wrong.

Just needed an additional write barrier, so that a parallel running lockup can never see inconsistent state. As long as there is no unregistration or the unregistration is done using locking or RCU in the caller they should be ok now.

This only makes a difference on non i386/x86-64 architectures. x86 was already ok because it never reorders writes.

Signed-off-by Andi Kleen <[email protected]>
kernel/sys.c renamed from kernel/sys.c-o +10 -2
diff -u linux-2.6.15rc2-work/kernel/sys.c-o linux-2.6.15rc2-work/kernel/sys.c
@@ -102,6 +102,9 @@
  *	@n: New entry in notifier chain
  *
  *	Adds a notifier to a notifier chain.
+ *	As long as unregister is not used this is safe against parallel
+ *	lockless notifier lookups. If unregister is used then unregister
+ *	needs to do additional locking or use RCU.
  *
  *	Currently always returns zero.
  */

@@ -116,6 +119,7 @@
 		list= &((*list)->next);
 	}
 	n->next = *list;
+	smp_wmb();
 	*list=n;
 	write_unlock(&notifier_lock);
 	return 0;

@@ -129,6 +133,8 @@
  *	@n: New entry in notifier chain
  *
  *	Removes a notifier from a notifier chain.
+ *	Note this needs additional locking or RCU in the caller to be safe
+ * 	against parallel traversals.
  *
  *	Returns zero on success, or %-ENOENT on failure.
  */

@@ -171,10 +177,12 @@
 int notifier_call_chain(struct notifier_block **n, unsigned long val, void *v)
 {
 	int ret=NOTIFY_DONE;
-	struct notifier_block *nb = *n;
-
+	struct notifier_block *nb;
+	smp_read_barrier_depends();
+	nb = *n;
 	while(nb)
 	{
+		smp_read_barrier_depends();
 		ret=nb->notifier_call(nb,val,v);
 		if(ret&NOTIFY_STOP_MASK)
 		{
#7 lore raw
Quoted 4 lines · Andi Kleen

On Mon, Nov 28, 2005 at 11:12:03PM +0530, Dipankar Sarma wrote:

Ok third version, hopefully Dipankar proof now.

Not quite. I spoke without looking at the code of the whole notifier_call_chain() function.

Quoted 9 lines

+ * against parallel traversals.
*
* Returns zero on success, or %-ENOENT on failure.
*/

kernel/sys.c renamed from kernel/sys.c-o +0 -1
@@ -171,10 +177,12 @@
 int notifier_call_chain(struct notifier_block **n, unsigned long val, void *v)
 {
 	int ret=NOTIFY_DONE;
-	struct notifier_block *nb = *n;

kernel/sys.c line 188

Quoted 10 lines
kernel/sys.c renamed from kernel/sys.c-o +4 -1
-
+	struct notifier_block *nb;
+	smp_read_barrier_depends();
+	nb = *n;
 	while(nb)
 	{
+		smp_read_barrier_depends();
 		ret=nb->notifier_call(nb,val,v);
 		if(ret&NOTIFY_STOP_MASK)
 		{

Looking at the full code, it seems to me that we dereference the first notifier block only inside the while(nb) loop. That means the smp_read_barrier_depends() in the while(nb) loop should be sufficient - IOW, the previous version of the patch with one smp_read_barrier_depends() was good. Sorry about the confusion.

Thanks
Dipankar