patches to cure race in lock_set_class()

Since commit f59de89 [lockdep: Clear whole lockdep_map on initialization], lockdep_init_map() will clear all the struct. But it will break lock_set_class()/lock_set_subclass(). A typical race condition is like below:

Quoted 4 lines · Yong Zhang

Since commit f59de89 [lockdep: Clear whole lockdep_map on initialization], lockdep_init_map() will clear all the struct. But it will break lock_set_class()/lock_set_subclass(). A typical race condition is like below:

This is a horridly ugly patch, why not simply revert that memset commit?

I really can't see the point of that, and keeping the name/key pointers around (which can only be over-written with the same values, right?) would also cure the problem.

Sadly the changelog is completely devoid of useful information (which is my own damn fault, I should never have accepted the patch in that form), so I can't actually comment on what it was supposed to fix.

Arguably kmemcheck is on crack or so since both name and key pointers should be in .data so there cannot be a leak by copying the thing over.

I prefer reverting that commit, but bugzilla is down and I don't know what the real problem behind that commit.

Quoted 4 lines · Yong Zhang

Since commit f59de89 [lockdep: Clear whole lockdep_map on initialization], lockdep_init_map() will clear all the struct. But it will break lock_set_class()/lock_set_subclass(). A typical race condition is like below:

This is a horridly ugly patch, why not simply revert that memset commit? I really can't see the point of that, and keeping the name/key pointers around (which can only be over-written with the same values, right?) would also cure the problem.

Arguably kmemcheck is on crack or so since both name and key pointers should be in .data so there cannot be a leak by copying the thing over.

Quoted 2 lines · Peter Zijlstra

Arguably kmemcheck is on crack or so since both name and key pointers should be in .data so there cannot be a leak by copying the thing over.

There is no leak, it's only about uninitialised memory.

The problem is that kmemcheck cannot track "initialisedness" of stack data and we're doing a heap-to-stack copy in process_one_work(), as Tejun pointed out:

        struct lockdep_map lockdep_map = work->lockdep_map;

This is of course fine in itself. But how can we tell kmemcheck that it's fine? There are basically two options:

1. Initialise the thing completely before doing the copy, or
2. Ignore the warning.

The memset() patch (f59de8992aa6dc85e81aadc26b0f69e17809721d) attempts to do the first, i.e. to clear the whole struct in lockdep_init_map().

I think nr. 1 is the best way to go in principle, but I don't know what it takes for this to work properly. The blanket-clear memset() presumably doesn't work because it clears out something that was already initialised by the caller (right?).

Yong Zhang, can you think of a way to avoid the race you described, perhaps by memset()ing only the right/relevant parts of struct lockdep_map in lockdep_init_map()?

Peter Zijlstra, if you prefer, we can also just tell kmemcheck that this particular copy is fine, but it means that kmemcheck will not be able to detect any real bugs in this code. It can be done with something like:

We could move the key and name pointer to the start of the structure and memset everything after that, however wouldn't that leave kmemcheck with the same problem? It wouldn't know those two pointers would be initialized properly.

Quoted 5 lines

include/linux/lockdep.h +1 -0

@@ -148,9 +148,9 @@ void clear_lock_stats(struct lock_class *class);
  * This is embedded into specific lock instances:
  */
 struct lockdep_map {
+	const char			*name;

include/linux/lockdep.h void clear_lock_stats(struct lock_class *class); · line 156

Quoted 6 lines

include/linux/lockdep.h +0 -1

 	struct lock_class_key		*key;
 	struct lock_class		*class_cache[NR_LOCKDEP_CACHING_CLASSES];
-	const char			*name;
 #ifdef CONFIG_LOCK_STAT
 	int				cpu;
 	unsigned long			ip;

Probably fat comment explaining the ordering requirement here w/

#define LOCKDEP_MAP_INIT_OFFSET offsetof(struct lockdep_map, class_cache)

kernel/lockdep.c static int mark_lock(struct task_struct *curr, struct held_lock *this, · line 2952

Quoted 11 lines

kernel/lockdep.c +2 -1

index e69434b..81855cf 100644
@@ -2948,7 +2948,8 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 void lockdep_init_map(struct lockdep_map *lock, const char *name,
 		      struct lock_class_key *key, int subclass)
 {
-	memset(lock, 0, sizeof(*lock));
+	kmemcheck_mark_initialized(lock, 2*sizeof(void *));
+	memset(&lock->class_cache[0], 0, sizeof(*lock)-2*sizeof(void *));

And something like the following?

	memset((void *)lock + LOCKDEP_MAP_INIT_OFFSET, 0,
		sizeof(*lock) - LOCKDEP_MAP_INIT_OFFSET);

Quoted 11 lines · Vegard Nossum

1. Initialise the thing completely before doing the copy, or
2. Ignore the warning.

The memset() patch (f59de8992aa6dc85e81aadc26b0f69e17809721d) attempts to do the first, i.e. to clear the whole struct in lockdep_init_map().

I think nr. 1 is the best way to go in principle, but I don't know what it takes for this to work properly. The blanket-clear memset() presumably doesn't work because it clears out something that was already initialised by the caller (right?).

Quoted 3 lines

Yong Zhang, can you think of a way to avoid the race you described, perhaps by memset()ing only the right/relevant parts of struct lockdep_map in lockdep_init_map()?

We could move the key and name pointer to the start of the structure and memset everything after that, however wouldn't that leave kmemcheck with the same problem? It wouldn't know those two pointers would be initialized properly.

Quoted 4 lines

Peter Zijlstra, if you prefer, we can also just tell kmemcheck that this particular copy is fine, but it means that kmemcheck will not be able to detect any real bugs in this code. It can be done with something like:

Something like this, although it would be best to come up with a nicer way to write it..

---
 include/linux/lockdep.h |    2 +-
 kernel/lockdep.c        |    3 ++-
 2 files changed, 3 insertions(+), 2 deletions(-)

include/linux/lockdep.h +1 -1

index b6a56e3..7d66268 100644
@@ -148,9 +148,9 @@ void clear_lock_stats(struct lock_class *class);
  * This is embedded into specific lock instances:
  */
 struct lockdep_map {
+	const char			*name;
 	struct lock_class_key		*key;
 	struct lock_class		*class_cache[NR_LOCKDEP_CACHING_CLASSES];
-	const char			*name;
 #ifdef CONFIG_LOCK_STAT
 	int				cpu;
 	unsigned long			ip;

kernel/lockdep.c +0 -0

index e69434b..81855cf 100644

Quoted 12 lines · Peter Zijlstra

Quoted 11 lines · Vegard Nossum

1. Initialise the thing completely before doing the copy, or
2. Ignore the warning.

The memset() patch (f59de8992aa6dc85e81aadc26b0f69e17809721d) attempts to do the first, i.e. to clear the whole struct in lockdep_init_map().

I think nr. 1 is the best way to go in principle, but I don't know what it takes for this to work properly. The blanket-clear memset() presumably doesn't work because it clears out something that was already initialised by the caller (right?).

Quoted 13 lines

Quoted 3 lines

Yong Zhang, can you think of a way to avoid the race you described, perhaps by memset()ing only the right/relevant parts of struct lockdep_map in lockdep_init_map()?

We could move the key and name pointer to the start of the structure and memset everything after that, however wouldn't that leave kmemcheck with the same problem? It wouldn't know those two pointers would be initialized properly.

Quoted 4 lines

Peter Zijlstra, if you prefer, we can also just tell kmemcheck that this particular copy is fine, but it means that kmemcheck will not be able to detect any real bugs in this code. It can be done with something like:

We should take ->calss_cache more carefully, because if we memset() it unconditionnally we will have no chance to set it anymore. Thus the performace brought by ->class_cache will be gone.

1) for lock_set_subclass(): we can't initialize ->class_cache because it's still valid and we need it.
2) for lock_set_class(): we have to initialize ->class_cache because it's invalid anymore.

Maybe we could unconditionally set it we look_up_lock_class() find the class?

Quoted 29 lines

Something like this, although it would be best to come up with a nicer way to write it..

---
 include/linux/lockdep.h |    2 +-
 kernel/lockdep.c        |    3 ++-
 2 files changed, 3 insertions(+), 2 deletions(-)

include/linux/lockdep.h +1 -1

index b6a56e3..7d66268 100644
@@ -148,9 +148,9 @@ void clear_lock_stats(struct lock_class *class);
  * This is embedded into specific lock instances:
  */
 struct lockdep_map {
+	const char			*name;
 	struct lock_class_key		*key;
 	struct lock_class		*class_cache[NR_LOCKDEP_CACHING_CLASSES];
-	const char			*name;
 #ifdef CONFIG_LOCK_STAT
 	int				cpu;
 	unsigned long			ip;

kernel/lockdep.c +0 -0

index e69434b..81855cf 100644

kernel/lockdep.c static int mark_lock(struct task_struct *curr, struct held_lock *this, · line 2952

Quoted 6 lines

kernel/lockdep.c +2 -1

@@ -2948,7 +2948,8 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 void lockdep_init_map(struct lockdep_map *lock, const char *name,
 		      struct lock_class_key *key, int subclass)
 {
-	memset(lock, 0, sizeof(*lock));
+	kmemcheck_mark_initialized(lock, 2*sizeof(void *));
+	memset(&lock->class_cache[0], 0, sizeof(*lock)-2*sizeof(void *));

That means ->key have chance to be 0 at some time, right? Then I think it'll lead to another false positive warning like what Borislav has reported:
http://marc.info/?l=linux-kernel&m=132039877026653

The reason is some rq->lock could carry a wrong key at certain time.

	CPU A				CPU B
  lock_set_subclass(lockA)
    __lock_set_class(lockA)
      lockdep_init_map(lockA)
        memset() /* ->key = NULL */
      				__lock_acquire(lockA)
				  register_lock_class(lockA)
				    look_up_lock_class(lockA)
				      if (unlikely(!lock->key))
				              lock->key = (void *)lock;
	->key = key;
				/* lockA maybe carry wrong class in later running
				 * due to ->class_cache
				 */

Then when another lock_set_subclass() comes:
CPU A CPU B

  lock_set_subclass(lockA);
    lock_set_class(lockA);
      				__lock_acquire(lockA)
                                  /* lockA->class_cache[] is not set,
				   * different subclass */
                                  register_lock_class(lockA);
                                     look_up_lock_class(lockA); /* retrun NULL */
      lockdep_init_map(lockA);
        memset(lockA); /* ->key = NULL */
                                  if (!static_obj(lock->key))
                                  /* we get warning here */

So maybe the simplest way is just annotating ->lock like this:

	kmemcheck_mark_initialized(lock, sizeof(*lock));

Thanks,
Yong

Quoted 13 lines

struct lockdep_map {

include/linux/lockdep.h +1 -1

+     const char                      *name;
      struct lock_class_key           *key;
      struct lock_class               *class_cache[NR_LOCKDEP_CACHING_CLASSES];
-     const char                      *name;
 #ifdef CONFIG_LOCK_STAT
      int                             cpu;
      unsigned long                   ip;

kernel/lockdep.c +0 -0

index e69434b..81855cf 100644
@@ -2948,7 +2948,8 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,

kernel/lockdep.c static int mark_lock(struct task_struct *curr, struct held_lock *this, · line 2952

Quoted 6 lines

kernel/lockdep.c +2 -1

 void lockdep_init_map(struct lockdep_map *lock, const char *name,
                    struct lock_class_key *key, int subclass)
 {
-     memset(lock, 0, sizeof(*lock));
+     kmemcheck_mark_initialized(lock, 2*sizeof(void *));
+     memset(&lock->class_cache[0], 0, sizeof(*lock)-2*sizeof(void *));

That means ->key have chance to be 0 at some time, right?

Quoted 13 lines · Yong Zhang

Quoted 13 lines

struct lockdep_map {

include/linux/lockdep.h +1 -1

+     const char                      *name;
      struct lock_class_key           *key;
      struct lock_class               *class_cache[NR_LOCKDEP_CACHING_CLASSES];
-     const char                      *name;
 #ifdef CONFIG_LOCK_STAT
      int                             cpu;
      unsigned long                   ip;

kernel/lockdep.c +0 -0

index e69434b..81855cf 100644
@@ -2948,7 +2948,8 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,

Quoted 8 lines

kernel/lockdep.c static int mark_lock(struct task_struct *curr, struct held_lock *this, · line 2952

Quoted 6 lines

kernel/lockdep.c +2 -1

 void lockdep_init_map(struct lockdep_map *lock, const char *name,
                    struct lock_class_key *key, int subclass)
 {
-     memset(lock, 0, sizeof(*lock));
+     kmemcheck_mark_initialized(lock, 2*sizeof(void *));
+     memset(&lock->class_cache[0], 0, sizeof(*lock)-2*sizeof(void *));

That means ->key have chance to be 0 at some time, right?

How? We only memset from class_cache onwards, leaving name and key untouched.

But how do we deal with ->class_cache? Always set it in loop_up_lock_class()?

Quoted 3 lines · Yong Zhang

But how do we deal with ->class_cache? Always set it in loop_up_lock_class()?

Hrm.. good point, aside from that there's another problem as well, I think we can deal with the cache being NULL, but is memset() an atomic write? If not a read could observe an intermediate state and go funny.

I'm tempted to go with the pure kmemcheck_mark_initialized() thing for now.

Quoted 8 lines · Peter Zijlstra

Quoted 3 lines · Yong Zhang

But how do we deal with ->class_cache? Always set it in loop_up_lock_class()?

Hrm.. good point, aside from that there's another problem as well, I think we can deal with the cache being NULL, but is memset() an atomic write? If not a read could observe an intermediate state and go funny.

Yup.

Quoted 3 lines

I'm tempted to go with the pure kmemcheck_mark_initialized() thing for now.

me too :)

So something like below?

Thanks,
Yong
---
From: Yong Zhang <[email protected]>
Subject: [PATCH] lockdep: kmemcheck: annotate ->lock in lockdep_init_map()

Since commit f59de89 [lockdep: Clear whole lockdep_map on initialization], lockdep_init_map() will clear all the struct. But it will break lock_set_class()/lock_set_subclass(). A typical race condition is like below:

CPU A CPU B
lock_set_subclass(lockA);

 lock_set_class(lockA);
   lockdep_init_map(lockA);
     /* lockA->name is cleared */
     memset(lockA);
                                     __lock_acquire(lockA);
                                       /* lockA->class_cache[] is cleared */
                                       register_lock_class(lockA);
                                         look_up_lock_class(lockA);
                                           WARN_ON_ONCE(class->name !=
                                                     lock->name);

     lock->name = name;

So annotate ->lock with kmemcheck_mark_initialized() to cure this problem and the one reported in commit f59de89.

Reported-by Sergey Senozhatsky <[email protected]>

Reported-by Borislav Petkov <[email protected]>

Suggested-by Vegard Nossum <[email protected]>

Signed-off-by Yong Zhang <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Tejun Heo <[email protected]>

Cc David Rientjes <[email protected]>

---
 kernel/lockdep.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

kernel/lockdep.c +0 -0

index e69434b..08a2b1b 100644

kernel/lockdep.c +0 -0

 #ifdef CONFIG_LOCK_STAT
 	lock->cpu = raw_smp_processor_id();

Signature · 1 line

1.7.5.4

So something like below?

Quoted 1 line · Yong Zhang

So something like below?

that fails to clear/init the class_cache, leading to all sorts of problems.

Wiping the class_cache just reduces performance somewhat, not wiping them is disastrous since it can results in wild pointer derefs.

Now we could fix up register_lock_class() to reset the class_cache, although that's a little tricky and I'm not sure its worth it.

Commit-ID:  d3d03d4fc5b1bec3a579112de170a9676e9d97cb
Gitweb:     http://git.kernel.org/tip/d3d03d4fc5b1bec3a579112de170a9676e9d97cb
Author:     Yong Zhang <[email protected]>
AuthorDate: Wed, 9 Nov 2011 16:04:51 +0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 6 Dec 2011 08:16:51 +0100

lockdep, kmemcheck: Annotate ->lock in lockdep_init_map()

Since commit f59de89 ("lockdep: Clear whole lockdep_map on initialization"), lockdep_init_map() will clear all the struct. But it will break lock_set_class()/lock_set_subclass(). A typical race condition is like below:

CPU A CPU B
lock_set_subclass(lockA);

 lock_set_class(lockA);
   lockdep_init_map(lockA);
     /* lockA->name is cleared */
     memset(lockA);
                                     __lock_acquire(lockA);
                                       /* lockA->class_cache[] is cleared */
                                       register_lock_class(lockA);
                                         look_up_lock_class(lockA);
                                           WARN_ON_ONCE(class->name !=
                                                     lock->name);

     lock->name = name;

So restore to what we have done before commit f59de89 but annotate ->lock with kmemcheck_mark_initialized() to suppress the kmemcheck warning reported in commit f59de89.

Reported-by Sergey Senozhatsky <[email protected]>

Reported-by Borislav Petkov <[email protected]>

Suggested-by Vegard Nossum <[email protected]>

Signed-off-by Yong Zhang <[email protected]>

Cc Tejun Heo <[email protected]>

Cc David Rientjes <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

Link http://lkml.kernel.org/r/20111109080451.GB8124@zhy open here

Signed-off-by Ingo Molnar <[email protected]>

1. Initialise the thing completely before doing the copy, or
2. Ignore the warning.

The memset() patch (f59de8992aa6dc85e81aadc26b0f69e17809721d) attempts to do the first, i.e. to clear the whole struct in lockdep_init_map().

I think nr. 1 is the best way to go in principle, but I don't know what it takes for this to work properly. The blanket-clear memset() presumably doesn't work because it clears out something that was already initialised by the caller (right?).

Yong Zhang, can you think of a way to avoid the race you described, perhaps by memset()ing only the right/relevant parts of struct lockdep_map in lockdep_init_map()?

Peter Zijlstra, if you prefer, we can also just tell kmemcheck that this particular copy is fine, but it means that kmemcheck will not be able to detect any real bugs in this code. It can be done with something like:

kernel/lockdep.c +1 -1

index e69434b..08a2b1b 100644
@@ -2948,7 +2948,7 @@ static int mark_lock(struct task_struct *curr,
 struct held_lock *this,
 void lockdep_init_map(struct lockdep_map *lock, const char *name,
                      struct lock_class_key *key, int subclass)
 {
-       memset(lock, 0, sizeof(*lock));
+       kmemcheck_mark_initialized(lock, sizeof(*lock));
 
 #ifdef CONFIG_LOCK_STAT

        lock->cpu = raw_smp_processor_id();

Christian Casteyde, do you mind testing this patch as well?

(Yong Zhang, do you think this would still be vulnerable to the race you described?)

When someone call lock_set_class() with valid key, nothing protect the initializing of 'lockdep_map'; thus could lead to flase positive warning from lockdep (such as "key not in .data!"). This patch cure that potential issue.

Quoted 4 lines · Yong Zhang

When someone call lock_set_class() with valid key, nothing protect the initializing of 'lockdep_map'; thus could lead to flase positive warning from lockdep (such as "key not in .data!"). This patch cure that potential issue.

How? that warning is triggered of the lock_class_key * passed into lockdep_init_map and is unrelated to the actual content of the lockdep_map.

This a new version of my previous post[1].

patch#1 is the one which fix the reported bug.
So Sergey, Borislav, would you please give it a test?