[PATCH 0/4] patches to cure race in lock_set_class()

[PATCH 0/4] patches to cure race in lock_set_class()

[Yong Zhang]

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?

patch#2~4 is an enhancement which fix a potential race in
  lock_set_class(). But the fact is the only current user
  in kernel is lock_set_subclass(), we still have no
  user which change its 'key' in flying. So I mark it
  with RFC.

More detail in each patch :)

Thanks,
Yong

[1]:http://marc.info/?l=linux-kernel&m=131919035525533

Yong Zhang (4):
  lockdep: lock_set_subclass() fix
  lockdep: Let register_lock_class() can be called with/without
    graph_lock
  lockdep: split lockdep_init_map()
  lockdep: fix race condition in __lock_set_class()

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

-- 
1.7.5.4

[PATCH 1/4] lockdep: lock_set_subclass() fix

[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:

      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;

Reported-by: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>
Reported-by: Borislav Petkov <bp@alien8.de>
Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Tejun Heo <tj@kernel.org>
Cc: David Rientjes <rientjes@google.com>
---
 include/linux/lockdep.h |    2 +-
 kernel/lockdep.c        |    9 +++++----
 2 files changed, 6 insertions(+), 5 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index b6a56e3..182fb2d 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -330,7 +330,7 @@ extern void lock_set_class(struct lockdep_map *lock, const char *name,
 static inline void lock_set_subclass(struct lockdep_map *lock,
 		unsigned int subclass, unsigned long ip)
 {
-	lock_set_class(lock, lock->name, lock->key, subclass, ip);
+	lock_set_class(lock, NULL, NULL, subclass, ip);
 }
 
 extern void lockdep_set_current_reclaim_state(gfp_t gfp_mask);
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index e69434b..4a16b0a 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -3247,7 +3247,6 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 {
 	struct task_struct *curr = current;
 	struct held_lock *hlock, *prev_hlock;
-	struct lock_class *class;
 	unsigned int depth;
 	int i;
 
@@ -3274,9 +3273,11 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 	return print_unlock_inbalance_bug(curr, lock, ip);
 
 found_it:
-	lockdep_init_map(lock, name, key, 0);
-	class = register_lock_class(lock, subclass, 0);
-	hlock->class_idx = class - lock_classes + 1;
+	/* optimizing for lock_set_subclass() */
+	if (key) {
+		lockdep_init_map(lock, name, key, 0);
+		register_lock_class(lock, subclass, 0);
+	}
 
 	curr->lockdep_depth = i;
 	curr->curr_chain_key = hlock->prev_chain_key;
-- 
1.7.5.4

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Peter Zijlstra]

On Fri, 2011-11-04 at 17:26 +0800, Yong Zhang wrote:
> 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.

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Yong Zhang]

On Mon, Nov 07, 2011 at 01:34:39PM +0100, Peter Zijlstra wrote:
> On Fri, 2011-11-04 at 17:26 +0800, Yong Zhang wrote:
> > 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 prefer reverting that commit, but bugzilla is down and I don't know
what the real problem behind that 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.

me too :(
And going through lkml history, I find nothing about it.

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

Maybe Tejun can give more detail on it.

Thanks,
Yong

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Tejun Heo]

(cc'ing the bug reporter and kmemcheck ppl)

Hello,

On Mon, Nov 07, 2011 at 09:31:31PM +0800, Yong Zhang wrote:
> I prefer reverting that commit, but bugzilla is down and I don't know
> what the real problem behind that commit.

So, this was the kmemcheck which triggers.

  PCI: Using host bridge windows from ACPI; if necessary, use "pci=nocrs" and
  report a bug
  WARNING: kmemcheck: Caught 64-bit read from uninitialized memory
  (ffff8801c6783c58)
  0000000000000000ee0caa81ffffffff00000000000000000000000000000000
   i i i i i i i i i i i i i i i i i i i i u u u u u u u u u u u u
						  ^

  Pid: 1, comm: swapper Not tainted 3.0.0-rc2 #8 Acer Aspire 7750G/JE70_HR
  RIP: 0010:[<ffffffff8108f3b3>]  [<ffffffff8108f3b3>]
  process_one_work+0x83/0x450
  RSP: 0018:ffff8801c6507d80  EFLAGS: 00010002
  RAX: 0000000000000000 RBX: ffff8801c7418300 RCX: 0000000000000000
  RDX: ffff8801c79d5800 RSI: ffff8801c6783c10 RDI: ffff8801c7418300
  RBP: ffff8801c6507e10 R08: ffff8801c64f8058 R09: 0000000000000001
  R10: 0000000000000000 R11: 0000000000000000 R12: ffff8801c6783c10
  R13: ffff8801c79d5800 R14: ffff8801c780ca00 R15: 000000000000003b
  FS:  0000000000000000(0000) GS:ffff8801c7800000(0000) knlGS:0000000000000000
  CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
  CR2: ffff8801c7430364 CR3: 0000000001c03000 CR4: 00000000000406f0
  DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
  DR3: 0000000000000000 DR6: 00000000ffff4ff0 DR7: 0000000000000400
   [<ffffffff810927cc>] worker_thread+0x15c/0x330
   [<ffffffff81097396>] kthread+0xa6/0xb0
   [<ffffffff817b3c54>] kernel_thread_helper+0x4/0x10
   [<ffffffffffffffff>] 0xffffffffffffffff
  \_SB_.PCI0:_OSC invalid UUID
  _OSC request data:1 8 1f

kmemcheck is complaining that memory area which hasn't been
initialized before is being read.  The offending code line is "struct
lockdep_map = work->lockdep_map" in process_one_work(), which caches
lockdep_map because work item can be destroyed once it starts
execution.

I don't have problem with reverting the patch but it would be much
better if it can play nice with kmemcheck.  It seems lockdep_map init
requirements are rather weird.  Maybe just avoiding clearing ->name is
better?

Thanks.

-- 
tejun

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Borislav Petkov]

On Mon, Nov 07, 2011 at 01:34:39PM +0100, Peter Zijlstra wrote:
> On Fri, 2011-11-04 at 17:26 +0800, Yong Zhang wrote:
> > 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.

FWIW,

I ran the box with the memset commit reverted for a couple of days
before applying Young's patches and it didn't show any signs of
problems.

-- 
Regards/Gruss,
Boris.

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Vegard Nossum]

On 7 November 2011 13:34, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> 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:

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index e69434b..08a2b1b 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -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?)

Thanks,

And sorry for the inconvenience.

I've been thinking about chucking kmemcheck and reimplementing it
using LibVEX (the dynamic translation framework used by Valgrind
itself). Whoever is interested, feel free to have a look:

https://github.com/vegard/linux-2.6/tree/kmemcheck2


Vegard

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Peter Zijlstra]

On Mon, 2011-11-07 at 16:28 +0100, Vegard Nossum wrote:
> On 7 November 2011 13:34, Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> > 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()?

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.

> 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(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index b6a56e3..7d66268 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -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;
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index e69434b..81855cf 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -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 *));
 
 #ifdef CONFIG_LOCK_STAT
 	lock->cpu = raw_smp_processor_id();

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Tejun Heo]

Hello,

On Mon, Nov 07, 2011 at 05:10:29PM +0100, Peter Zijlstra wrote:
> 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.

At that point, lockdep_map is guaranteed to have passed through
lockdep_init_map(), so I think it should be fine.

> @@ -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;

Probably fat comment explaining the ordering requirement here w/

#define LOCKDEP_MAP_INIT_OFFSET		offsetof(struct lockdep_map, class_cache)

> diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> index e69434b..81855cf 100644
> --- a/kernel/lockdep.c
> +++ b/kernel/lockdep.c
> @@ -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);

Thanks.

-- 
tejun

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Peter Zijlstra]

On Mon, 2011-11-07 at 08:21 -0800, Tejun Heo wrote:

> > @@ -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;
> 
> Probably fat comment explaining the ordering requirement here w/

yes.

> #define LOCKDEP_MAP_INIT_OFFSET		offsetof(struct lockdep_map, class_cache)
> 
> > diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> > index e69434b..81855cf 100644
> > --- a/kernel/lockdep.c
> > +++ b/kernel/lockdep.c
> > @@ -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);

Much better indeed!

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Yong Zhang]

On Mon, Nov 07, 2011 at 05:10:29PM +0100, Peter Zijlstra wrote:
> On Mon, 2011-11-07 at 16:28 +0100, Vegard Nossum wrote:
> > 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()?
> 
> 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.
> 
> > 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?

> 
> 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(-)
> 
> diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> index b6a56e3..7d66268 100644
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -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;
> diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> index e69434b..81855cf 100644
> --- a/kernel/lockdep.c
> +++ b/kernel/lockdep.c
> @@ -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

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Yong Zhang]

On Tue, Nov 08, 2011 at 10:58:47AM +0800, Yong Zhang wrote:
> On Mon, Nov 07, 2011 at 05:10:29PM +0100, Peter Zijlstra wrote:
> > On Mon, 2011-11-07 at 16:28 +0100, Vegard Nossum wrote:
> > > 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()?
> > 
> > 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.
> > 
> > > 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?
> 
> > 
> > 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(-)
> > 
> > diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> > index b6a56e3..7d66268 100644
> > --- a/include/linux/lockdep.h
> > +++ b/include/linux/lockdep.h
> > @@ -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;
> > diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> > index e69434b..81855cf 100644
> > --- a/kernel/lockdep.c
> > +++ b/kernel/lockdep.c
> > @@ -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
> 				 */

And lockA could also carry different key:

	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))
	->key = key;
				              lock->key = (void *)lock;
				/* lockA maybe carry wrong key in later running
				 * due to ->class_cache
				 */

Thanks,
Yong

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

-- 
Only stand for myself

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Peter Zijlstra]

On Tue, 2011-11-08 at 10:58 +0800, Yong Zhang wrote:
> >  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;
> > diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> > index e69434b..81855cf 100644
> > --- a/kernel/lockdep.c
> > +++ b/kernel/lockdep.c
> > @@ -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? 

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

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Yong Zhang]

On Tue, Nov 08, 2011 at 08:56:55AM +0100, Peter Zijlstra wrote:
> On Tue, 2011-11-08 at 10:58 +0800, Yong Zhang wrote:
> > >  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;
> > > diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> > > index e69434b..81855cf 100644
> > > --- a/kernel/lockdep.c
> > > +++ b/kernel/lockdep.c
> > > @@ -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? 
> 
> How? We only memset from class_cache onwards, leaving name and key
> untouched.

Hmm, we don't touch key in your patch. My eyes was keeping on ->name.
Sorry.

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

Thanks,
Yong

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Peter Zijlstra]

On Tue, 2011-11-08 at 16:14 +0800, Yong Zhang wrote:
> 
> 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.

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Yong Zhang]

On Tue, Nov 08, 2011 at 09:46:20AM +0100, Peter Zijlstra wrote:
> On Tue, 2011-11-08 at 16:14 +0800, Yong Zhang wrote:
> > 
> > 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.

> 
> 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 <yong.zhang0@gmail.com>
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 <sergey.senozhatsky@gmail.com>
Reported-by: Borislav Petkov <bp@alien8.de>
Suggested-by: Vegard Nossum <vegard.nossum@gmail.com>
Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Tejun Heo <tj@kernel.org>
Cc: David Rientjes <rientjes@google.com>
---
 kernel/lockdep.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index e69434b..08a2b1b 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -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();
-- 
1.7.5.4

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Yong Zhang]

On Tue, Nov 08, 2011 at 05:07:35PM +0800, Yong Zhang wrote:
> On Tue, Nov 08, 2011 at 09:46:20AM +0100, Peter Zijlstra wrote:
> > On Tue, 2011-11-08 at 16:14 +0800, Yong Zhang wrote:
> > > 
> > > 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.
> 
> > 
> > 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 <yong.zhang0@gmail.com>
> 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 <sergey.senozhatsky@gmail.com>
> Reported-by: Borislav Petkov <bp@alien8.de>
> Suggested-by: Vegard Nossum <vegard.nossum@gmail.com>
> Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Cc: Ingo Molnar <mingo@elte.hu>
> Cc: Tejun Heo <tj@kernel.org>
> Cc: David Rientjes <rientjes@google.com>
> ---
>  kernel/lockdep.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> index e69434b..08a2b1b 100644
> --- a/kernel/lockdep.c
> +++ b/kernel/lockdep.c
> @@ -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));

But for a lock in initializing stage (like spin_lock_init()), we still
need to guarantee that lock->class_cache[] doesn't contain garbage.

Need more thought here.

Thanks,
Yong

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

-- 
Only stand for myself

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Peter Zijlstra]

On Tue, 2011-11-08 at 17:07 +0800, Yong Zhang wrote:
> 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.

Anyway, I see you just realized the same.. ;-)

[PATCH 1/2] lockdep: kmemcheck: annotate ->lock in lockdep_init_map()

[Yong Zhang]

On Tue, Nov 08, 2011 at 10:40:46AM +0100, Peter Zijlstra wrote:
> On Tue, 2011-11-08 at 17:07 +0800, Yong Zhang wrote:
> > 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.

Yeah, I have done some benchmark which show it's worthful, please
check patch#2.

And below is the one which cure the current problem.

Thanks,
Yong

---
From: Yong Zhang <yong.zhang0@gmail.com>
Subject: [PATCH 1/2] 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 <sergey.senozhatsky@gmail.com>
Reported-by: Borislav Petkov <bp@alien8.de>
Suggested-by: Vegard Nossum <vegard.nossum@gmail.com>
Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Tejun Heo <tj@kernel.org>
Cc: David Rientjes <rientjes@google.com>
---
 kernel/lockdep.c |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index e69434b..21ea1dc 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -2948,7 +2948,12 @@ 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));
+	int i;
+
+	kmemcheck_mark_initialized(lock, sizeof(*lock));
+
+	for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
+		lock->class_cache[i] = NULL;
 
 #ifdef CONFIG_LOCK_STAT
 	lock->cpu = raw_smp_processor_id();
-- 
1.7.5.4

[PATCH 2/2] lockdep: always try to set ->class_cache in register_lock_class() lockdep_init_map()

[Yong Zhang]

From: Yong Zhang <yong.zhang0@gmail.com>

commit [62016250 lockdep: Add improved subclass caching] try to
improve performance (expecially to reduce the cost of rq->lock)
when using lockdep, but it fails due to lockdep_init_map() in
which ->class_cache is cleared. The typical caller is
lock_set_subclass(), after that class will not be cached anymore.

This patch try to achive the goal of commit 62016250 by always
setting ->class_cache in register_lock_class().

=== Score comparison of benchmarks ===

for i in `seq 1 10`; do ./perf bench -f simple sched messaging; done

before:  min: 0.604, max: 0.660, avg: 0.622
after:   min: 0.414, max: 0.473, avg: 0.427

for i in `seq 1 10`; do ./perf bench -f simple sched messaging -g 40; done

before:  min: 2.347, max: 2.421, avg: 2.391
after:   min: 1.652, max: 1.699, avg: 1.671

Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
---
 kernel/lockdep.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 21ea1dc..e9cbb99 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -722,7 +722,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 
 	class = look_up_lock_class(lock, subclass);
 	if (likely(class))
-		return class;
+		goto out_set_class_cache;
 
 	/*
 	 * Debug-check: all keys must be persistent!
@@ -807,6 +807,7 @@ out_unlock_set:
 	graph_unlock();
 	raw_local_irq_restore(flags);
 
+out_set_class_cache:
 	if (!subclass || force)
 		lock->class_cache[0] = class;
 	else if (subclass < NR_LOCKDEP_CACHING_CLASSES)
-- 
1.7.5.4

[tip:core/locking] lockdep: Always try to set ->class_cache in register_lock_class() lockdep_init_map()

[tip-bot for Yong Zhang]

Commit-ID:  87cdee71166fa107c5dc8e43060eeefa533c6a3b
Gitweb:     http://git.kernel.org/tip/87cdee71166fa107c5dc8e43060eeefa533c6a3b
Author:     Yong Zhang <yong.zhang0@gmail.com>
AuthorDate: Wed, 9 Nov 2011 16:07:14 +0800
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Mon, 14 Nov 2011 13:54:11 +0100

lockdep: Always try to set ->class_cache in register_lock_class() lockdep_init_map()

Commit ["62016250 lockdep: Add improved subclass caching"] tries to
improve performance (expecially to reduce the cost of rq->lock)
when using lockdep, but it fails due to lockdep_init_map() in
which ->class_cache is cleared. The typical caller is
lock_set_subclass(), after that class will not be cached anymore.

This patch tries to achive the goal of commit 62016250 by always
setting ->class_cache in register_lock_class().

=== Score comparison of benchmarks ===

for i in `seq 1 10`; do ./perf bench -f simple sched messaging; done

before:  min: 0.604, max: 0.660, avg: 0.622
after:   min: 0.414, max: 0.473, avg: 0.427

for i in `seq 1 10`; do ./perf bench -f simple sched messaging -g 40; done

before:  min: 2.347, max: 2.421, avg: 2.391
after:   min: 1.652, max: 1.699, avg: 1.671

Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/20111109080714.GC8124@zhy
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/lockdep.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index e69434b..103bed8 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -722,7 +722,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 
 	class = look_up_lock_class(lock, subclass);
 	if (likely(class))
-		return class;
+		goto out_set_class_cache;
 
 	/*
 	 * Debug-check: all keys must be persistent!
@@ -807,6 +807,7 @@ out_unlock_set:
 	graph_unlock();
 	raw_local_irq_restore(flags);
 
+out_set_class_cache:
 	if (!subclass || force)
 		lock->class_cache[0] = class;
 	else if (subclass < NR_LOCKDEP_CACHING_CLASSES)

[tip:core/locking] lockdep, kmemcheck: Annotate ->lock in lockdep_init_map()

[tip-bot for Yong Zhang]

Commit-ID:  d3d03d4fc5b1bec3a579112de170a9676e9d97cb
Gitweb:     http://git.kernel.org/tip/d3d03d4fc5b1bec3a579112de170a9676e9d97cb
Author:     Yong Zhang <yong.zhang0@gmail.com>
AuthorDate: Wed, 9 Nov 2011 16:04:51 +0800
Committer:  Ingo Molnar <mingo@elte.hu>
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 <sergey.senozhatsky@gmail.com>
Reported-by: Borislav Petkov <bp@alien8.de>
Suggested-by: Vegard Nossum <vegard.nossum@gmail.com>
Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: David Rientjes <rientjes@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/20111109080451.GB8124@zhy
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/lockdep.c |    8 +++++++-
 1 files changed, 7 insertions(+), 1 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index a2ab30c..54cc0dc 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -44,6 +44,7 @@
 #include <linux/stringify.h>
 #include <linux/bitops.h>
 #include <linux/gfp.h>
+#include <linux/kmemcheck.h>
 
 #include <asm/sections.h>
 
@@ -2950,7 +2951,12 @@ 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));
+	int i;
+
+	kmemcheck_mark_initialized(lock, sizeof(*lock));
+
+	for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
+		lock->class_cache[i] = NULL;
 
 #ifdef CONFIG_LOCK_STAT
 	lock->cpu = raw_smp_processor_id();

Re: [tip:core/locking] lockdep, kmemcheck: Annotate ->lock in lockdep_init_map()

[David Rientjes]

On Tue, 6 Dec 2011, tip-bot for Yong Zhang wrote:

> Commit-ID:  d3d03d4fc5b1bec3a579112de170a9676e9d97cb
> Gitweb:     http://git.kernel.org/tip/d3d03d4fc5b1bec3a579112de170a9676e9d97cb
> Author:     Yong Zhang <yong.zhang0@gmail.com>
> AuthorDate: Wed, 9 Nov 2011 16:04:51 +0800
> Committer:  Ingo Molnar <mingo@elte.hu>
> 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 <sergey.senozhatsky@gmail.com>
> Reported-by: Borislav Petkov <bp@alien8.de>
> Suggested-by: Vegard Nossum <vegard.nossum@gmail.com>
> Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
> Cc: Tejun Heo <tj@kernel.org>
> Cc: David Rientjes <rientjes@google.com>

Acked-by: David Rientjes <rientjes@google.com>

> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Link: http://lkml.kernel.org/r/20111109080451.GB8124@zhy
> Signed-off-by: Ingo Molnar <mingo@elte.hu>

[tip:perf/urgent] lockdep, kmemcheck: Annotate ->lock in lockdep_init_map()

[tip-bot for Yong Zhang]

Commit-ID:  a33caeb118198286309859f014c0662f3ed54ed4
Gitweb:     http://git.kernel.org/tip/a33caeb118198286309859f014c0662f3ed54ed4
Author:     Yong Zhang <yong.zhang0@gmail.com>
AuthorDate: Wed, 9 Nov 2011 16:04:51 +0800
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Tue, 6 Dec 2011 18:18:13 +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 <sergey.senozhatsky@gmail.com>
Reported-by: Borislav Petkov <bp@alien8.de>
Suggested-by: Vegard Nossum <vegard.nossum@gmail.com>
Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: David Rientjes <rientjes@google.com>
Cc: <stable@kernel.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/20111109080451.GB8124@zhy
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/lockdep.c |    8 +++++++-
 1 files changed, 7 insertions(+), 1 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index e69434b..b2e08c9 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -44,6 +44,7 @@
 #include <linux/stringify.h>
 #include <linux/bitops.h>
 #include <linux/gfp.h>
+#include <linux/kmemcheck.h>
 
 #include <asm/sections.h>
 
@@ -2948,7 +2949,12 @@ 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));
+	int i;
+
+	kmemcheck_mark_initialized(lock, sizeof(*lock));
+
+	for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
+		lock->class_cache[i] = NULL;
 
 #ifdef CONFIG_LOCK_STAT
 	lock->cpu = raw_smp_processor_id();

Re: [PATCH 1/4] lockdep: lock_set_subclass() fix

[Yong Zhang]

On Mon, Nov 07, 2011 at 04:28:19PM +0100, Vegard Nossum wrote:
> 
> 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()?

That could work, but we should take more care on the member 'class_cache',
because under some condition (lock_set_subclass()) we don't need
to initialise it for performance issue, but under other condtion (
set a new valid key to a class) we need to initialise it since it's
invalid anymore.

Another option is always seting ->class_cache if lookup_lock_class()
find the class. Will talk about it with Peter in another thread.

> 
> 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:
> 
> diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> index e69434b..08a2b1b 100644
> --- a/kernel/lockdep.c
> +++ b/kernel/lockdep.c
> @@ -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?)

No, this will work because we just retore the previous behavior except
kmemcheck annotation, right?

Thanks,
Yong

[RFC PATCH 2/4] lockdep: Let register_lock_class() can be called with/without graph_lock

[Yong Zhang]

Will be used in later patch which fix some race condition in
lock_set_class().

Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
---
 kernel/lockdep.c |   14 +++++++++-----
 1 files changed, 9 insertions(+), 5 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 4a16b0a..e7d38fa 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -711,9 +711,13 @@ look_up_lock_class(struct lockdep_map *lock, unsigned int subclass)
  * Register a lock's class in the hash-table, if the class is not present
  * yet. Otherwise we look it up. We cache the result in the lock object
  * itself, so actual lookup of the hash should be once per lock object.
+ *
+ * NOTE: register_lock_class() can be called with/without graph_lock hold
+ *	 depending on @locked. But it will release graph_lock before return.
  */
 static inline struct lock_class *
-register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
+register_lock_class(struct lockdep_map *lock, unsigned int subclass,
+		    int force, int locked)
 {
 	struct lockdep_subclass_key *key;
 	struct list_head *hash_head;
@@ -741,7 +745,7 @@ register_lock_class(struct lockdep_map *lock, unsigned int subclass, int force)
 	hash_head = classhashentry(key);
 
 	raw_local_irq_save(flags);
-	if (!graph_lock()) {
+	if (!locked && !graph_lock()) {
 		raw_local_irq_restore(flags);
 		return NULL;
 	}
@@ -2986,7 +2990,7 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 		return;
 
 	if (subclass)
-		register_lock_class(lock, subclass, 1);
+		register_lock_class(lock, subclass, 1, 0);
 }
 EXPORT_SYMBOL_GPL(lockdep_init_map);
 
@@ -3032,7 +3036,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	 * Not cached?
 	 */
 	if (unlikely(!class)) {
-		class = register_lock_class(lock, subclass, 0);
+		class = register_lock_class(lock, subclass, 0, 0);
 		if (!class)
 			return 0;
 	}
@@ -3276,7 +3280,7 @@ found_it:
 	/* optimizing for lock_set_subclass() */
 	if (key) {
 		lockdep_init_map(lock, name, key, 0);
-		register_lock_class(lock, subclass, 0);
+		register_lock_class(lock, subclass, 0, 0);
 	}
 
 	curr->lockdep_depth = i;
-- 
1.7.5.4

[RFC PATCH 3/4] lockdep: split lockdep_init_map()

[Yong Zhang]

A new one __lockdep_init_map() is introduced which only initialize
the struct. It will be call in later patch in __lock_set_class()
to reduce recursive call to register_lock_class().

Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
---
 kernel/lockdep.c |   25 ++++++++++++++++++-------
 1 files changed, 18 insertions(+), 7 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index e7d38fa..3af87ad 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -2949,8 +2949,9 @@ static int mark_lock(struct task_struct *curr, struct held_lock *this,
 /*
  * Initialize a lock instance's lock-class mapping info:
  */
-void lockdep_init_map(struct lockdep_map *lock, const char *name,
-		      struct lock_class_key *key, int subclass)
+static inline int
+__lockdep_init_map(struct lockdep_map *lock, const char *name,
+		 struct lock_class_key *key, int subclass)
 {
 	memset(lock, 0, sizeof(*lock));
 
@@ -2963,7 +2964,7 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 	 */
 	if (DEBUG_LOCKS_WARN_ON(!name)) {
 		lock->name = "NULL";
-		return;
+		return 0;
 	}
 
 	lock->name = name;
@@ -2972,7 +2973,7 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 	 * No key, no joy, we need to hash something.
 	 */
 	if (DEBUG_LOCKS_WARN_ON(!key))
-		return;
+		return 0;
 	/*
 	 * Sanity check, the lock-class key must be persistent:
 	 */
@@ -2982,15 +2983,25 @@ void lockdep_init_map(struct lockdep_map *lock, const char *name,
 		 * What it says above ^^^^^, I suggest you read it.
 		 */
 		DEBUG_LOCKS_WARN_ON(1);
-		return;
+		return 0;
 	}
 	lock->key = key;
 
 	if (unlikely(!debug_locks))
-		return;
+		return 0;
+
+	return 1;
+}
+
+void lockdep_init_map(struct lockdep_map *lock, const char *name,
+		      struct lock_class_key *key, int subclass)
+{
+	int ret;
 
-	if (subclass)
+	ret = __lockdep_init_map(lock, name, key, subclass);
+	if (ret && subclass)
 		register_lock_class(lock, subclass, 1, 0);
+
 }
 EXPORT_SYMBOL_GPL(lockdep_init_map);
 
-- 
1.7.5.4

[RFC PATCH 4/4] lockdep: fix race condition in __lock_set_class()

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

Signed-off-by: Yong Zhang <yong.zhang0@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
---
 kernel/lockdep.c |    8 ++++++--
 1 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 3af87ad..fd4d816 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -3290,8 +3290,12 @@ __lock_set_class(struct lockdep_map *lock, const char *name,
 found_it:
 	/* optimizing for lock_set_subclass() */
 	if (key) {
-		lockdep_init_map(lock, name, key, 0);
-		register_lock_class(lock, subclass, 0, 0);
+		if (!graph_lock())
+			return 0;
+
+		__lockdep_init_map(lock, name, key, 0);
+		/* will release graph_lock() there */
+		register_lock_class(lock, subclass, 0, 1);
 	}
 
 	curr->lockdep_depth = i;
-- 
1.7.5.4

Re: [RFC PATCH 4/4] lockdep: fix race condition in __lock_set_class()

[Peter Zijlstra]

On Fri, 2011-11-04 at 17:26 +0800, Yong Zhang wrote:
> 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.

Re: [RFC PATCH 4/4] lockdep: fix race condition in __lock_set_class()

[Yong Zhang]

On Mon, Nov 07, 2011 at 01:30:54PM +0100, Peter Zijlstra wrote:
> On Fri, 2011-11-04 at 17:26 +0800, Yong Zhang wrote:
> > 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.

Oh, my fault, the false positive warning could be "non-static key".

But seems we should find the right direction for this bug :)
Some comments in replies to patch#1.

Thanks,
Yong

Re: [PATCH 0/4] patches to cure race in lock_set_class()

[Borislav Petkov]

On Fri, Nov 04, 2011 at 05:26:26PM +0800, Yong Zhang wrote:
> 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?

Yep, applied and running now, will let you know what happens.

Thanks.

-- 
Regards/Gruss,
   Boris