[PATCH 1/2] lockdep: check the depth of subclass

[PATCH 1/2] lockdep: check the depth of subclass

[Hitoshi Mitake]

Current look_up_lock_class() doesn't check the parameter "subclass".
This rarely rises problems because the main caller of this function,
register_lock_class(), checks it.
But register_lock_class() is not the only function which calls
look_up_lock_class(). lock_set_class() and its callees also call it.
And lock_set_class() doesn't check this parameter.

This will rise problems when the the value of subclass is larger
MAX_LOCKDEP_SUBCLASSES. Because the address (used as the key of class)
caliculated with too large subclass has a possibility to point
another key in different lock_class_key.
Of course this problem depends on the memory layout and
occurs with really low possibility.

And mousedev_create() calles lockdep_set_subclass() and
sets class of mousedev->mutex as MOUSEDEV_MIX(== 31).
And if my understanding is correct,
this subclass doesn't have to be MOUSEDEV_MIX,
so I modified this value to SINGLE_DEPTH_NESTING.

Signed-off-by: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
Cc: Dmitry Torokhov <dtor@mail.ru>
Cc: Vojtech Pavlik <vojtech@ucw.cz>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
---
 drivers/input/mousedev.c |    2 +-
 kernel/lockdep.c         |   15 +++++++++++++++
 2 files changed, 16 insertions(+), 1 deletions(-)

diff --git a/drivers/input/mousedev.c b/drivers/input/mousedev.c
index d528a2d..9897334 100644
--- a/drivers/input/mousedev.c
+++ b/drivers/input/mousedev.c
@@ -866,7 +866,7 @@ static struct mousedev *mousedev_create(struct input_dev *dev,
 	spin_lock_init(&mousedev->client_lock);
 	mutex_init(&mousedev->mutex);
 	lockdep_set_subclass(&mousedev->mutex,
-			     minor == MOUSEDEV_MIX ? MOUSEDEV_MIX : 0);
+			     minor == MOUSEDEV_MIX ? SINGLE_DEPTH_NESTING : 0);
 	init_waitqueue_head(&mousedev->wait);
 
 	if (minor == MOUSEDEV_MIX)
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 84baa71..c4c13ae 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -639,6 +639,21 @@ look_up_lock_class(struct lockdep_map *lock, unsigned int subclass)
 	}
 #endif
 
+	if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
+		/*
+		 * This check should be done not only in __lock_acquire()
+		 * but also here. Because register_lock_class() is also called
+		 * by lock_set_class(). Callers of lock_set_class() can
+		 * pass invalid value as subclass.
+		 */
+
+		debug_locks_off();
+		printk(KERN_ERR "BUG: looking up invalid subclass: %u\n", subclass);
+		printk(KERN_ERR "turning off the locking correctness validator.\n");
+		dump_stack();
+		return NULL;
+	}
+
 	/*
 	 * Static locks do not have their class-keys yet - for them the key
 	 * is the lock object itself:
-- 
1.6.5.2

[RFC PATCH 2/2] lockdep: caching subclasses

[Hitoshi Mitake]

Current lockdep_map only caches one class with subclass == 0,
and looks up hash table of classes when subclass != 0.

It seems that this has no problem because the case of
subclass != 0 is rare. But locks of struct rq are
acquired with subclass == 1 when task migration is executed.
Task migration is high frequent event, so I modified lockdep
to cache subclasses.

I measured the score of perf bench sched messaging.
This patch has slightly but certain (order of milli seconds
or 10 milli seconds) effect when lots of tasks are running.
I'll show the result in the tail of this description.

NR_LOCKDEP_CACHING_CLASSES specifies how many classes can be
cached in the instances of lockdep_map.
I discussed with Peter Zijlstra in LinuxCon Japan about
this approach and he taught me that caching every subclasses(8)
is cleary waste of memory. So number of cached classes
should be configurable.

I think that this patch has a little effect for making lockdep
as a production feature, I'd like to hear your comments.

Thanks,

=== Score comparison of benchmarks ===
# "min" means best score, and "max" means worst score

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

before: min: 0.565000, max: 0.583000, avg: 0.572500
after:  min: 0.559000, max: 0.568000, avg: 0.563300

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

before: min: 2.274000, max: 2.298000, avg: 2.286300
after:  min: 2.242000, max: 2.270000, avg: 2.259700

Signed-off-by: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
---
 include/linux/lockdep.h |   13 ++++++++++++-
 kernel/lockdep.c        |   25 ++++++++++++++++++-------
 2 files changed, 30 insertions(+), 8 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 06aed83..2186a64 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -32,6 +32,17 @@ extern int lock_stat;
 #define MAX_LOCKDEP_SUBCLASSES		8UL
 
 /*
+ * NR_LOCKDEP_CACHING_CLASSES ... Number of classes
+ * cached in the instance of lockdep_map
+ *
+ * Currently main class (subclass == 0) and signle depth subclass
+ * are cached in lockdep_map. This optimization is mainly targeting
+ * on rq->lock. double_rq_lock() acquires this highly competitive with
+ * single depth.
+ */
+#define NR_LOCKDEP_CACHING_CLASSES	2
+
+/*
  * Lock-classes are keyed via unique addresses, by embedding the
  * lockclass-key into the kernel (or module) .data section. (For
  * static locks we use the lock address itself as the key.)
@@ -138,7 +149,7 @@ void clear_lock_stats(struct lock_class *class);
  */
 struct lockdep_map {
 	struct lock_class_key		*key;
-	struct lock_class		*class_cache;
+	struct lock_class		*class_cache[NR_LOCKDEP_CACHING_CLASSES];
 	const char			*name;
 #ifdef CONFIG_LOCK_STAT
 	int				cpu;
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index c4c13ae..a41b38f 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -789,7 +789,9 @@ out_unlock_set:
 	raw_local_irq_restore(flags);
 
 	if (!subclass || force)
-		lock->class_cache = class;
+		lock->class_cache[0] = class;
+	else if (subclass < NR_LOCKDEP_CACHING_CLASSES)
+		lock->class_cache[subclass] = class;
 
 	if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass))
 		return NULL;
@@ -2694,7 +2696,11 @@ 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)
 {
-	lock->class_cache = NULL;
+	int i;
+
+	for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
+		lock->class_cache[i] = NULL;
+
 #ifdef CONFIG_LOCK_STAT
 	lock->cpu = raw_smp_processor_id();
 #endif
@@ -2765,10 +2771,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (lock->key == &__lockdep_no_validate__)
 		check = 1;
 
-	if (!subclass)
-		class = lock->class_cache;
+	if (subclass < NR_LOCKDEP_CACHING_CLASSES)
+		class = lock->class_cache[subclass];
 	/*
-	 * Not cached yet or subclass?
+	 * Not cached?
 	 */
 	if (unlikely(!class)) {
 		class = register_lock_class(lock, subclass, 0);
@@ -2933,7 +2939,7 @@ static int match_held_lock(struct held_lock *hlock, struct lockdep_map *lock)
 		return 1;
 
 	if (hlock->references) {
-		struct lock_class *class = lock->class_cache;
+		struct lock_class *class = lock->class_cache[0];
 
 		if (!class)
 			class = look_up_lock_class(lock, 0);
@@ -3574,7 +3580,12 @@ void lockdep_reset_lock(struct lockdep_map *lock)
 		if (list_empty(head))
 			continue;
 		list_for_each_entry_safe(class, next, head, hash_entry) {
-			if (unlikely(class == lock->class_cache)) {
+			int match = 0;
+
+			for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++)
+				match |= class == lock->class_cache[j];
+
+			if (unlikely(match)) {
 				if (debug_locks_off_graph_unlock())
 					WARN_ON(1);
 				goto out_restore;
-- 
1.6.5.2

Re: [PATCH 1/2] lockdep: check the depth of subclass

[Peter Zijlstra]

On Tue, 2010-10-05 at 18:01 +0900, Hitoshi Mitake wrote:
> Current look_up_lock_class() doesn't check the parameter "subclass".
> This rarely rises problems because the main caller of this function,
> register_lock_class(), checks it.
> But register_lock_class() is not the only function which calls
> look_up_lock_class(). lock_set_class() and its callees also call it.
> And lock_set_class() doesn't check this parameter.
> 
> This will rise problems when the the value of subclass is larger
> MAX_LOCKDEP_SUBCLASSES. Because the address (used as the key of class)
> caliculated with too large subclass has a possibility to point
> another key in different lock_class_key.
> Of course this problem depends on the memory layout and
> occurs with really low possibility.
> 
> And mousedev_create() calles lockdep_set_subclass() and
> sets class of mousedev->mutex as MOUSEDEV_MIX(== 31).
> And if my understanding is correct,
> this subclass doesn't have to be MOUSEDEV_MIX,
> so I modified this value to SINGLE_DEPTH_NESTING.
> 
> Signed-off-by: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
> Cc: Dmitry Torokhov <dtor@mail.ru>
> Cc: Vojtech Pavlik <vojtech@ucw.cz>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Frederic Weisbecker <fweisbec@gmail.com>
> ---
>  drivers/input/mousedev.c |    2 +-
>  kernel/lockdep.c         |   15 +++++++++++++++
>  2 files changed, 16 insertions(+), 1 deletions(-)
> 
> diff --git a/drivers/input/mousedev.c b/drivers/input/mousedev.c
> index d528a2d..9897334 100644
> --- a/drivers/input/mousedev.c
> +++ b/drivers/input/mousedev.c
> @@ -866,7 +866,7 @@ static struct mousedev *mousedev_create(struct input_dev *dev,
>  	spin_lock_init(&mousedev->client_lock);
>  	mutex_init(&mousedev->mutex);
>  	lockdep_set_subclass(&mousedev->mutex,
> -			     minor == MOUSEDEV_MIX ? MOUSEDEV_MIX : 0);
> +			     minor == MOUSEDEV_MIX ? SINGLE_DEPTH_NESTING : 0);

Ah good find.

>  	init_waitqueue_head(&mousedev->wait);
>  
>  	if (minor == MOUSEDEV_MIX)
> diff --git a/kernel/lockdep.c b/kernel/lockdep.c
> index 84baa71..c4c13ae 100644
> --- a/kernel/lockdep.c
> +++ b/kernel/lockdep.c
> @@ -639,6 +639,21 @@ look_up_lock_class(struct lockdep_map *lock, unsigned int subclass)
>  	}
>  #endif
>  
> +	if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
> +		/*
> +		 * This check should be done not only in __lock_acquire()
> +		 * but also here. Because register_lock_class() is also called
> +		 * by lock_set_class(). Callers of lock_set_class() can
> +		 * pass invalid value as subclass.
> +		 */
> +
> +		debug_locks_off();
> +		printk(KERN_ERR "BUG: looking up invalid subclass: %u\n", subclass);
> +		printk(KERN_ERR "turning off the locking correctness validator.\n");
> +		dump_stack();
> +		return NULL;
> +	}

Would we catch all cases if we moved this check from __lock_acquire()
into register_lock_class()? It would result in only a single instance of
this logic.


>  	/*
>  	 * Static locks do not have their class-keys yet - for them the key
>  	 * is the lock object itself:

Re: [RFC PATCH 2/2] lockdep: caching subclasses

[Peter Zijlstra]

On Tue, 2010-10-05 at 18:01 +0900, Hitoshi Mitake wrote:
> Current lockdep_map only caches one class with subclass == 0,
> and looks up hash table of classes when subclass != 0.
> 
> It seems that this has no problem because the case of
> subclass != 0 is rare. But locks of struct rq are
> acquired with subclass == 1 when task migration is executed.
> Task migration is high frequent event, so I modified lockdep
> to cache subclasses.
> 
> I measured the score of perf bench sched messaging.
> This patch has slightly but certain (order of milli seconds
> or 10 milli seconds) effect when lots of tasks are running.
> I'll show the result in the tail of this description.
> 
> NR_LOCKDEP_CACHING_CLASSES specifies how many classes can be
> cached in the instances of lockdep_map.
> I discussed with Peter Zijlstra in LinuxCon Japan about
> this approach and he taught me that caching every subclasses(8)
> is cleary waste of memory. So number of cached classes
> should be configurable.
> 
> I think that this patch has a little effect for making lockdep
> as a production feature, I'd like to hear your comments.
> 
> Thanks,
> 
> === Score comparison of benchmarks ===
> # "min" means best score, and "max" means worst score
> 
> for i in `seq 1 10`; do ./perf bench -f simple sched messaging; done
> 
> before: min: 0.565000, max: 0.583000, avg: 0.572500
> after:  min: 0.559000, max: 0.568000, avg: 0.563300
> 
> # with more processes
> for i in `seq 1 10`; do ./perf bench -f simple sched messaging -g 40; done
> 
> before: min: 2.274000, max: 2.298000, avg: 2.286300
> after:  min: 2.242000, max: 2.270000, avg: 2.259700

Very nice numbers, I'll queue this patch.

Thanks!

Re: [PATCH 1/2] lockdep: check the depth of subclass

[Dmitry Torokhov]

On Tue, Oct 12, 2010 at 12:27:01PM +0200, Peter Zijlstra wrote:
> On Tue, 2010-10-05 at 18:01 +0900, Hitoshi Mitake wrote:
> > ---
> >  drivers/input/mousedev.c |    2 +-
> >  kernel/lockdep.c         |   15 +++++++++++++++
> >  2 files changed, 16 insertions(+), 1 deletions(-)
> > 
> > diff --git a/drivers/input/mousedev.c b/drivers/input/mousedev.c
> > index d528a2d..9897334 100644
> > --- a/drivers/input/mousedev.c
> > +++ b/drivers/input/mousedev.c
> > @@ -866,7 +866,7 @@ static struct mousedev *mousedev_create(struct input_dev *dev,
> >  	spin_lock_init(&mousedev->client_lock);
> >  	mutex_init(&mousedev->mutex);
> >  	lockdep_set_subclass(&mousedev->mutex,
> > -			     minor == MOUSEDEV_MIX ? MOUSEDEV_MIX : 0);
> > +			     minor == MOUSEDEV_MIX ? SINGLE_DEPTH_NESTING : 0);
> 
> Ah good find.
> 

I'll pick up mousedev change for .37.

Thanks.

-- 
Dmitry

Re: [PATCH 1/2] lockdep: check the depth of subclass

[Hitoshi Mitake]

On 10/12/10 19:27, Peter Zijlstra wrote:
 > On Tue, 2010-10-05 at 18:01 +0900, Hitoshi Mitake wrote:
 >> Current look_up_lock_class() doesn't check the parameter "subclass".
 >> This rarely rises problems because the main caller of this function,
 >> register_lock_class(), checks it.
 >> But register_lock_class() is not the only function which calls
 >> look_up_lock_class(). lock_set_class() and its callees also call it.
 >> And lock_set_class() doesn't check this parameter.
 >>
 >> This will rise problems when the the value of subclass is larger
 >> MAX_LOCKDEP_SUBCLASSES. Because the address (used as the key of class)
 >> caliculated with too large subclass has a possibility to point
 >> another key in different lock_class_key.
 >> Of course this problem depends on the memory layout and
 >> occurs with really low possibility.
 >>
 >> And mousedev_create() calles lockdep_set_subclass() and
 >> sets class of mousedev->mutex as MOUSEDEV_MIX(== 31).
 >> And if my understanding is correct,
 >> this subclass doesn't have to be MOUSEDEV_MIX,
 >> so I modified this value to SINGLE_DEPTH_NESTING.
 >>
 >> Signed-off-by: Hitoshi Mitake<mitake@dcl.info.waseda.ac.jp>
 >> Cc: Dmitry Torokhov<dtor@mail.ru>
 >> Cc: Vojtech Pavlik<vojtech@ucw.cz>
 >> Cc: Peter Zijlstra<peterz@infradead.org>
 >> Cc: Frederic Weisbecker<fweisbec@gmail.com>
 >> ---
 >>   drivers/input/mousedev.c |    2 +-
 >>   kernel/lockdep.c         |   15 +++++++++++++++
 >>   2 files changed, 16 insertions(+), 1 deletions(-)
 >>
 >> diff --git a/drivers/input/mousedev.c b/drivers/input/mousedev.c
 >> index d528a2d..9897334 100644
 >> --- a/drivers/input/mousedev.c
 >> +++ b/drivers/input/mousedev.c
 >> @@ -866,7 +866,7 @@ static struct mousedev *mousedev_create(struct 
input_dev *dev,
 >>   	spin_lock_init(&mousedev->client_lock);
 >>   	mutex_init(&mousedev->mutex);
 >>   	lockdep_set_subclass(&mousedev->mutex,
 >> -			     minor == MOUSEDEV_MIX ? MOUSEDEV_MIX : 0);
 >> +			     minor == MOUSEDEV_MIX ? SINGLE_DEPTH_NESTING : 0);
 >
 > Ah good find.
 >
 >>   	init_waitqueue_head(&mousedev->wait);
 >>
 >>   	if (minor == MOUSEDEV_MIX)
 >> diff --git a/kernel/lockdep.c b/kernel/lockdep.c
 >> index 84baa71..c4c13ae 100644
 >> --- a/kernel/lockdep.c
 >> +++ b/kernel/lockdep.c
 >> @@ -639,6 +639,21 @@ look_up_lock_class(struct lockdep_map *lock, 
unsigned int subclass)
 >>   	}
 >>   #endif
 >>
 >> +	if (unlikely(subclass>= MAX_LOCKDEP_SUBCLASSES)) {
 >> +		/*
 >> +		 * This check should be done not only in __lock_acquire()
 >> +		 * but also here. Because register_lock_class() is also called
 >> +		 * by lock_set_class(). Callers of lock_set_class() can
 >> +		 * pass invalid value as subclass.
 >> +		 */
 >> +
 >> +		debug_locks_off();
 >> +		printk(KERN_ERR "BUG: looking up invalid subclass: %u\n", subclass);
 >> +		printk(KERN_ERR "turning off the locking correctness validator.\n");
 >> +		dump_stack();
 >> +		return NULL;
 >> +	}
 >
 > Would we catch all cases if we moved this check from __lock_acquire()
 > into register_lock_class()? It would result in only a single instance of
 > this logic.
 >

I think that __lock_acquire() should also check the value of subclass.
Because it access to the lock->class_cache as array
before calling look_up_lock_class() after applying this patch.

So if the check isn't done in __lock_acquire(),
the invalid addresses might be interpreted as the addresses of
struct lock_class.

Re: [PATCH 1/2] lockdep: check the depth of subclass

[Hitoshi Mitake]

On 10/13/10 01:03, Dmitry Torokhov wrote:
 > On Tue, Oct 12, 2010 at 12:27:01PM +0200, Peter Zijlstra wrote:
 >> On Tue, 2010-10-05 at 18:01 +0900, Hitoshi Mitake wrote:
 >>> ---
 >>>   drivers/input/mousedev.c |    2 +-
 >>>   kernel/lockdep.c         |   15 +++++++++++++++
 >>>   2 files changed, 16 insertions(+), 1 deletions(-)
 >>>
 >>> diff --git a/drivers/input/mousedev.c b/drivers/input/mousedev.c
 >>> index d528a2d..9897334 100644
 >>> --- a/drivers/input/mousedev.c
 >>> +++ b/drivers/input/mousedev.c
 >>> @@ -866,7 +866,7 @@ static struct mousedev *mousedev_create(struct 
input_dev *dev,
 >>>   	spin_lock_init(&mousedev->client_lock);
 >>>   	mutex_init(&mousedev->mutex);
 >>>   	lockdep_set_subclass(&mousedev->mutex,
 >>> -			     minor == MOUSEDEV_MIX ? MOUSEDEV_MIX : 0);
 >>> +			     minor == MOUSEDEV_MIX ? SINGLE_DEPTH_NESTING : 0);
 >>
 >> Ah good find.
 >>
 >
 > I'll pick up mousedev change for .37.

Thanks a lot, Dmitry.

Should I divide this patch into two for
drivers/input/mousedev.c and kernel/lockdep.c?
If you need, I'll resend second version.

Re: [PATCH 1/2] lockdep: check the depth of subclass

[Peter Zijlstra]

On Wed, 2010-10-13 at 11:26 +0900, Hitoshi Mitake wrote:
>  >> @@ -639,6 +639,21 @@ look_up_lock_class(struct lockdep_map *lock, unsigned int subclass)
>  >>     }
>  >>   #endif
>  >>
>  >> +   if (unlikely(subclass>= MAX_LOCKDEP_SUBCLASSES)) {
>  >> +           /*
>  >> +            * This check should be done not only in __lock_acquire()
>  >> +            * but also here. Because register_lock_class() is also called
>  >> +            * by lock_set_class(). Callers of lock_set_class() can
>  >> +            * pass invalid value as subclass.
>  >> +            */
>  >> +
>  >> +           debug_locks_off();
>  >> +           printk(KERN_ERR "BUG: looking up invalid subclass: %u\n", subclass);
>  >> +           printk(KERN_ERR "turning off the locking correctness validator.\n");
>  >> +           dump_stack();
>  >> +           return NULL;
>  >> +   }
>  >
>  > Would we catch all cases if we moved this check from __lock_acquire()
>  > into register_lock_class()? It would result in only a single instance of
>  > this logic.
>  >
> 
> I think that __lock_acquire() should also check the value of subclass.
> Because it access to the lock->class_cache as array
> before calling look_up_lock_class() after applying this patch.
> 
> So if the check isn't done in __lock_acquire(),
> the invalid addresses might be interpreted as the addresses of
> struct lock_class. 


But __lock_acquire() does:

  if (subclass < NR_LOCKDEP_CACHING_CLASSES)
    class = lock->class_cache[subclass];

  if (!class)
    class = register_lock_class();

So by moving the: subclass >= MAX_LOCKDEP_SUBCLASSES, check into
register_lock_class() it would still trigger for __lock_acquire().
Because NR_LOCKDEP_CACHING_CLASSES <= MAX_LOCKDEP_SUBCLASSES, and thus
for subclass >= MAX_LOCKDEP_SUBCLASSES we'll always call into
register_lock_class() and trigger the failure there, no?

Re: [PATCH 1/2] lockdep: check the depth of subclass

[Hitoshi Mitake]

On 10/13/10 16:33, Peter Zijlstra wrote:
 > On Wed, 2010-10-13 at 11:26 +0900, Hitoshi Mitake wrote:
 >>   >>  @@ -639,6 +639,21 @@ look_up_lock_class(struct lockdep_map 
*lock, unsigned int subclass)
 >>   >>      }
 >>   >>    #endif
 >>   >>
 >>   >>  +   if (unlikely(subclass>= MAX_LOCKDEP_SUBCLASSES)) {
 >>   >>  +           /*
 >>   >>  +            * This check should be done not only in 
__lock_acquire()
 >>   >>  +            * but also here. Because register_lock_class() is 
also called
 >>   >>  +            * by lock_set_class(). Callers of 
lock_set_class() can
 >>   >>  +            * pass invalid value as subclass.
 >>   >>  +            */
 >>   >>  +
 >>   >>  +           debug_locks_off();
 >>   >>  +           printk(KERN_ERR "BUG: looking up invalid subclass: 
%u\n", subclass);
 >>   >>  +           printk(KERN_ERR "turning off the locking 
correctness validator.\n");
 >>   >>  +           dump_stack();
 >>   >>  +           return NULL;
 >>   >>  +   }
 >>   >
 >>   >  Would we catch all cases if we moved this check from 
__lock_acquire()
 >>   >  into register_lock_class()? It would result in only a single 
instance of
 >>   >  this logic.
 >>   >
 >>
 >> I think that __lock_acquire() should also check the value of subclass.
 >> Because it access to the lock->class_cache as array
 >> before calling look_up_lock_class() after applying this patch.
 >>
 >> So if the check isn't done in __lock_acquire(),
 >> the invalid addresses might be interpreted as the addresses of
 >> struct lock_class.
 >
 >
 > But __lock_acquire() does:
 >
 >    if (subclass<  NR_LOCKDEP_CACHING_CLASSES)
 >      class = lock->class_cache[subclass];
 >
 >    if (!class)
 >      class = register_lock_class();
 >
 > So by moving the: subclass>= MAX_LOCKDEP_SUBCLASSES, check into
 > register_lock_class() it would still trigger for __lock_acquire().
 > Because NR_LOCKDEP_CACHING_CLASSES<= MAX_LOCKDEP_SUBCLASSES, and thus
 > for subclass>= MAX_LOCKDEP_SUBCLASSES we'll always call into
 > register_lock_class() and trigger the failure there, no?
 >
 >
 >

Ahh, sorry, you are right.
So current checking subclass >= MAX_LOCKDEP_SUBCLASSES is redundant,
I'll remove this checking and resend second version later.

Thanks for your advice!

[PATCH v2] lockdep: check the depth of subclass

[Hitoshi Mitake]

Current look_up_lock_class() doesn't check the parameter "subclass".
This rarely rises problems because the main caller of this function,
register_lock_class(), checks it.
But register_lock_class() is not the only function which calls
look_up_lock_class(). lock_set_class() and its callees also call it.
And lock_set_class() doesn't check this parameter.

This will rise problems when the the value of subclass is larger than
MAX_LOCKDEP_SUBCLASSES. Because the address (used as the key of class)
caliculated with too large subclass has a possibility to point
another key in different lock_class_key.
Of course this problem depends on the memory layout and
occurs with really low possibility.

And mousedev_create() calles lockdep_set_subclass() and
sets class of mousedev->mutex as MOUSEDEV_MIX(== 31).
And if my understanding is correct,
this subclass doesn't have to be MOUSEDEV_MIX,
so I modified this value to SINGLE_DEPTH_NESTING.

v2: Based on Peter Zijlstra's advice, I removed the
checking of the subclass value from __lock_acquire().
Because this is already a redundant thing.

# If you need devided version for mousedev.c and lockdep.c,
# feel free to tell me.

Signed-off-by: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
Cc: Dmitry Torokhov <dtor@mail.ru>
Cc: Vojtech Pavlik <vojtech@ucw.cz>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
---
 drivers/input/mousedev.c |    2 +-
 kernel/lockdep.c         |   18 ++++++++++--------
 2 files changed, 11 insertions(+), 9 deletions(-)

diff --git a/drivers/input/mousedev.c b/drivers/input/mousedev.c
index d528a2d..9897334 100644
--- a/drivers/input/mousedev.c
+++ b/drivers/input/mousedev.c
@@ -866,7 +866,7 @@ static struct mousedev *mousedev_create(struct input_dev *dev,
 	spin_lock_init(&mousedev->client_lock);
 	mutex_init(&mousedev->mutex);
 	lockdep_set_subclass(&mousedev->mutex,
-			     minor == MOUSEDEV_MIX ? MOUSEDEV_MIX : 0);
+			     minor == MOUSEDEV_MIX ? SINGLE_DEPTH_NESTING : 0);
 	init_waitqueue_head(&mousedev->wait);
 
 	if (minor == MOUSEDEV_MIX)
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 84baa71..553d410 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -639,6 +639,16 @@ look_up_lock_class(struct lockdep_map *lock, unsigned int subclass)
 	}
 #endif
 
+	if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
+		debug_locks_off();
+		printk(KERN_ERR
+			"BUG: looking up invalid subclass: %u\n", subclass);
+		printk(KERN_ERR
+			"turning off the locking correctness validator.\n");
+		dump_stack();
+		return NULL;
+	}
+
 	/*
 	 * Static locks do not have their class-keys yet - for them the key
 	 * is the lock object itself:
@@ -2739,14 +2749,6 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
 		return 0;
 
-	if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
-		debug_locks_off();
-		printk("BUG: MAX_LOCKDEP_SUBCLASSES too low!\n");
-		printk("turning off the locking correctness validator.\n");
-		dump_stack();
-		return 0;
-	}
-
 	if (lock->key == &__lockdep_no_validate__)
 		check = 1;
 
-- 
1.6.5.2

Re: [PATCH v2] lockdep: check the depth of subclass

[Peter Zijlstra]

On Wed, 2010-10-13 at 17:30 +0900, Hitoshi Mitake wrote:
> Current look_up_lock_class() doesn't check the parameter "subclass".
> This rarely rises problems because the main caller of this function,
> register_lock_class(), checks it.
> But register_lock_class() is not the only function which calls
> look_up_lock_class(). lock_set_class() and its callees also call it.
> And lock_set_class() doesn't check this parameter.
> 
> This will rise problems when the the value of subclass is larger than
> MAX_LOCKDEP_SUBCLASSES. Because the address (used as the key of class)
> caliculated with too large subclass has a possibility to point
> another key in different lock_class_key.
> Of course this problem depends on the memory layout and
> occurs with really low possibility.
> 
> And mousedev_create() calles lockdep_set_subclass() and
> sets class of mousedev->mutex as MOUSEDEV_MIX(== 31).
> And if my understanding is correct,
> this subclass doesn't have to be MOUSEDEV_MIX,
> so I modified this value to SINGLE_DEPTH_NESTING.
> 
> v2: Based on Peter Zijlstra's advice, I removed the
> checking of the subclass value from __lock_acquire().
> Because this is already a redundant thing.
> 
> # If you need devided version for mousedev.c and lockdep.c,
> # feel free to tell me.

I've taken the patch without the mousedev hunk, as Dmitry said he'd take
that.

Thanks!

Re: [PATCH 1/2] lockdep: check the depth of subclass

[Dmitry Torokhov]

On Wed, Oct 13, 2010 at 11:27:46AM +0900, Hitoshi Mitake wrote:
> On 10/13/10 01:03, Dmitry Torokhov wrote:
> > On Tue, Oct 12, 2010 at 12:27:01PM +0200, Peter Zijlstra wrote:
> >> On Tue, 2010-10-05 at 18:01 +0900, Hitoshi Mitake wrote:
> >>> ---
> >>>   drivers/input/mousedev.c |    2 +-
> >>>   kernel/lockdep.c         |   15 +++++++++++++++
> >>>   2 files changed, 16 insertions(+), 1 deletions(-)
> >>>
> >>> diff --git a/drivers/input/mousedev.c b/drivers/input/mousedev.c
> >>> index d528a2d..9897334 100644
> >>> --- a/drivers/input/mousedev.c
> >>> +++ b/drivers/input/mousedev.c
> >>> @@ -866,7 +866,7 @@ static struct mousedev
> *mousedev_create(struct input_dev *dev,
> >>>   	spin_lock_init(&mousedev->client_lock);
> >>>   	mutex_init(&mousedev->mutex);
> >>>   	lockdep_set_subclass(&mousedev->mutex,
> >>> -			     minor == MOUSEDEV_MIX ? MOUSEDEV_MIX : 0);
> >>> +			     minor == MOUSEDEV_MIX ? SINGLE_DEPTH_NESTING : 0);
> >>
> >> Ah good find.
> >>
> >
> > I'll pick up mousedev change for .37.
> 
> Thanks a lot, Dmitry.
> 
> Should I divide this patch into two for
> drivers/input/mousedev.c and kernel/lockdep.c?
> If you need, I'll resend second version.

No, thanks, I'll extract it on my end.

-- 
Dmitry

[tip:core/locking] lockdep: Add improved subclass caching

[tip-bot for Hitoshi Mitake]

Commit-ID:  620162505e5d46bc4494b1761743e4b0b3bf8e16
Gitweb:     http://git.kernel.org/tip/620162505e5d46bc4494b1761743e4b0b3bf8e16
Author:     Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
AuthorDate: Tue, 5 Oct 2010 18:01:51 +0900
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Mon, 18 Oct 2010 18:44:25 +0200

lockdep: Add improved subclass caching

Current lockdep_map only caches one class with subclass == 0,
and looks up hash table of classes when subclass != 0.

It seems that this has no problem because the case of
subclass != 0 is rare. But locks of struct rq are
acquired with subclass == 1 when task migration is executed.
Task migration is high frequent event, so I modified lockdep
to cache subclasses.

I measured the score of perf bench sched messaging.
This patch has slightly but certain (order of milli seconds
or 10 milli seconds) effect when lots of tasks are running.
I'll show the result in the tail of this description.

NR_LOCKDEP_CACHING_CLASSES specifies how many classes can be
cached in the instances of lockdep_map.
I discussed with Peter Zijlstra in LinuxCon Japan about
this approach and he taught me that caching every subclasses(8)
is cleary waste of memory. So number of cached classes
should be configurable.

=== Score comparison of benchmarks ===
# "min" means best score, and "max" means worst score

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

before: min: 0.565000, max: 0.583000, avg: 0.572500
after:  min: 0.559000, max: 0.568000, avg: 0.563300

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

before: min: 2.274000, max: 2.298000, avg: 2.286300
after:  min: 2.242000, max: 2.270000, avg: 2.259700

Signed-off-by: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <1286269311-28336-2-git-send-email-mitake@dcl.info.waseda.ac.jp>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 include/linux/lockdep.h |   13 ++++++++++++-
 kernel/lockdep.c        |   25 ++++++++++++++++++-------
 2 files changed, 30 insertions(+), 8 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 06aed83..2186a64 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -32,6 +32,17 @@ extern int lock_stat;
 #define MAX_LOCKDEP_SUBCLASSES		8UL
 
 /*
+ * NR_LOCKDEP_CACHING_CLASSES ... Number of classes
+ * cached in the instance of lockdep_map
+ *
+ * Currently main class (subclass == 0) and signle depth subclass
+ * are cached in lockdep_map. This optimization is mainly targeting
+ * on rq->lock. double_rq_lock() acquires this highly competitive with
+ * single depth.
+ */
+#define NR_LOCKDEP_CACHING_CLASSES	2
+
+/*
  * Lock-classes are keyed via unique addresses, by embedding the
  * lockclass-key into the kernel (or module) .data section. (For
  * static locks we use the lock address itself as the key.)
@@ -138,7 +149,7 @@ void clear_lock_stats(struct lock_class *class);
  */
 struct lockdep_map {
 	struct lock_class_key		*key;
-	struct lock_class		*class_cache;
+	struct lock_class		*class_cache[NR_LOCKDEP_CACHING_CLASSES];
 	const char			*name;
 #ifdef CONFIG_LOCK_STAT
 	int				cpu;
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index 84baa71..bc4d328 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -774,7 +774,9 @@ out_unlock_set:
 	raw_local_irq_restore(flags);
 
 	if (!subclass || force)
-		lock->class_cache = class;
+		lock->class_cache[0] = class;
+	else if (subclass < NR_LOCKDEP_CACHING_CLASSES)
+		lock->class_cache[subclass] = class;
 
 	if (DEBUG_LOCKS_WARN_ON(class->subclass != subclass))
 		return NULL;
@@ -2679,7 +2681,11 @@ 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)
 {
-	lock->class_cache = NULL;
+	int i;
+
+	for (i = 0; i < NR_LOCKDEP_CACHING_CLASSES; i++)
+		lock->class_cache[i] = NULL;
+
 #ifdef CONFIG_LOCK_STAT
 	lock->cpu = raw_smp_processor_id();
 #endif
@@ -2750,10 +2756,10 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (lock->key == &__lockdep_no_validate__)
 		check = 1;
 
-	if (!subclass)
-		class = lock->class_cache;
+	if (subclass < NR_LOCKDEP_CACHING_CLASSES)
+		class = lock->class_cache[subclass];
 	/*
-	 * Not cached yet or subclass?
+	 * Not cached?
 	 */
 	if (unlikely(!class)) {
 		class = register_lock_class(lock, subclass, 0);
@@ -2918,7 +2924,7 @@ static int match_held_lock(struct held_lock *hlock, struct lockdep_map *lock)
 		return 1;
 
 	if (hlock->references) {
-		struct lock_class *class = lock->class_cache;
+		struct lock_class *class = lock->class_cache[0];
 
 		if (!class)
 			class = look_up_lock_class(lock, 0);
@@ -3559,7 +3565,12 @@ void lockdep_reset_lock(struct lockdep_map *lock)
 		if (list_empty(head))
 			continue;
 		list_for_each_entry_safe(class, next, head, hash_entry) {
-			if (unlikely(class == lock->class_cache)) {
+			int match = 0;
+
+			for (j = 0; j < NR_LOCKDEP_CACHING_CLASSES; j++)
+				match |= class == lock->class_cache[j];
+
+			if (unlikely(match)) {
 				if (debug_locks_off_graph_unlock())
 					WARN_ON(1);
 				goto out_restore;

[tip:core/locking] lockdep: Check the depth of subclass

[tip-bot for Hitoshi Mitake]

Commit-ID:  4ba053c04aece1f4734056f21b751eee47ea3fb1
Gitweb:     http://git.kernel.org/tip/4ba053c04aece1f4734056f21b751eee47ea3fb1
Author:     Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
AuthorDate: Wed, 13 Oct 2010 17:30:26 +0900
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Mon, 18 Oct 2010 18:44:26 +0200

lockdep: Check the depth of subclass

Current look_up_lock_class() doesn't check the parameter "subclass".
This rarely rises problems because the main caller of this function,
register_lock_class(), checks it.

But register_lock_class() is not the only function which calls
look_up_lock_class(). lock_set_class() and its callees also call it.
And lock_set_class() doesn't check this parameter.

This will rise problems when the the value of subclass is larger than
MAX_LOCKDEP_SUBCLASSES. Because the address (used as the key of class)
caliculated with too large subclass has a probability to point
another key in different lock_class_key.

Of course this problem depends on the memory layout and
occurs with really low probability.

Signed-off-by: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
Cc: Dmitry Torokhov <dtor@mail.ru>
Cc: Vojtech Pavlik <vojtech@ucw.cz>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <1286958626-986-1-git-send-email-mitake@dcl.info.waseda.ac.jp>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/lockdep.c |   18 ++++++++++--------
 1 files changed, 10 insertions(+), 8 deletions(-)

diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index bc4d328..42ba65d 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -639,6 +639,16 @@ look_up_lock_class(struct lockdep_map *lock, unsigned int subclass)
 	}
 #endif
 
+	if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
+		debug_locks_off();
+		printk(KERN_ERR
+			"BUG: looking up invalid subclass: %u\n", subclass);
+		printk(KERN_ERR
+			"turning off the locking correctness validator.\n");
+		dump_stack();
+		return NULL;
+	}
+
 	/*
 	 * Static locks do not have their class-keys yet - for them the key
 	 * is the lock object itself:
@@ -2745,14 +2755,6 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
 	if (DEBUG_LOCKS_WARN_ON(!irqs_disabled()))
 		return 0;
 
-	if (unlikely(subclass >= MAX_LOCKDEP_SUBCLASSES)) {
-		debug_locks_off();
-		printk("BUG: MAX_LOCKDEP_SUBCLASSES too low!\n");
-		printk("turning off the locking correctness validator.\n");
-		dump_stack();
-		return 0;
-	}
-
 	if (lock->key == &__lockdep_no_validate__)
 		check = 1;