Random panics seen in 2.6.18-rc1

Quoted 4 lines · Ingo Molnar

but ... i think gcc ought to be able to figure out that the parameter is totally unused on !LOCKDEP - all functions involved are static, and we are using -funit-at-a-time already. That should make the parameter passing totally zero-cost.

hm, gcc (as of 4.1.1) doesnt seem to be able to figure that out, probably due to the 'nesting + 1' changing the variable.

Anyway, Arjan's nesting-type idea should solve the problem - in that case 'nesting + 1' becomes an identity mapping of a zero-sized variable, which will generate zero code.

Ingo

Andrew Morton

2006-07-13 09:08 UTC #9 lore raw

Re: [patch] lockdep: more annotations for mm/slab.c

In reply to Andrew Morton

Quoted 22 lines · On Thu, 13 Jul 2006 10:46:13 +0200 Ingo Molnar <[email protected]> wrote:

the SLAB code can hold multiple slab locks at once, for example at:

 [<c0105dd5>] show_trace+0xd/0x10
 [<c0105def>] dump_stack+0x17/0x1c
 [<c014182e>] __lock_acquire+0x7ab/0xa0e
 [<c0141d6e>] lock_acquire+0x5e/0x80
 [<c10b0d8e>] _spin_lock_nested+0x26/0x37
 [<c017178b>] __cache_free+0x30d/0x3d2
 [<c0171200>] slab_destroy+0xfd/0x11d
 [<c0171360>] free_block+0x140/0x17d
 [<c01717dd>] __cache_free+0x35f/0x3d2
 [<c01718cd>] kfree+0x7d/0x9a
 [<c0127889>] free_task+0xe/0x24
 [<c0127ee8>] __put_task_struct+0xc2/0xc7
 [<c012bc8f>] delayed_put_task_struct+0x1e/0x20
 [<c0139d94>] __rcu_process_callbacks+0xff/0x15d
 [<c0139e1a>] rcu_process_callbacks+0x28/0x40
 [<c012f125>] tasklet_action+0x6e/0xd1
 [<c012f2c7>] __do_softirq+0x6e/0xec
 [<c01061b7>] do_softirq+0x61/0xc7

Quoted 5 lines

so add the 'nested' parameter to the affected functions.
Signed-off-by Ingo Molnar <[email protected]>
---
 mm/slab.c |   45 +++++++++++++++++++++++++--------------------

geeze, what fuss. Can't we just tell lockdep "the locking here is correct, so buzz off"?

Ingo Molnar

2006-07-13 09:23 UTC #10 lore raw

Re: [patch] lockdep: more annotations for mm/slab.c

Quoted 5 lines · Andrew Morton

Quoted 2 lines
---
 mm/slab.c |   45 +++++++++++++++++++++++++--------------------
geeze, what fuss. Can't we just tell lockdep "the locking here is correct, so buzz off"?

well, lockdep already found a locking bug in slab.c, so by telling lockdep to buzz off we lose the proof of correctness :-)

but i agree that this is getting a bit too intrusive. This patch is really just another expression of: 'slab locking is too complex', but i digress. Not all hope is lost though: Arjan thinks he can do a much simpler annotation.

Ingo

Arjan van de Ven

2006-07-13 10:44 UTC #11 lore raw

Re: [patch] lockdep: more annotations for mm/slab.c

Quoted 8 lines · Ingo Molnar

Quoted 5 lines · Andrew Morton
Quoted 2 lines
---
 mm/slab.c |   45 +++++++++++++++++++++++++--------------------
geeze, what fuss. Can't we just tell lockdep "the locking here is correct, so buzz off"?

Quoted 7 lines

well, lockdep already found a locking bug in slab.c, so by telling lockdep to buzz off we lose the proof of correctness :-)
but i agree that this is getting a bit too intrusive. This patch is really just another expression of: 'slab locking is too complex', but i digress. Not all hope is lost though: Arjan thinks he can do a much simpler annotation.

I am hoping I can get away with just this patch; the idea is to give the cache_cache slab a special lock type since it'll be nested all the time (and has a natural ordering due to it's special position in the slab code). I'm not yet sure I found all places where this stuff is initialized (the slab code has gotten terribly complex with all the numa stuff added to it); I've started to test this now at least and so far it seems to work on my test box.

mm/slab.c +11 -0

Index: linux-2.6.18-rc1/mm/slab.c
===================================================================
@@ -317,6 +317,16 @@ static void enable_cpucache(struct kmem_
 static void cache_reap(void *unused);
 
 /*
+ * Slab sometimes uses the kmalloc slabs to store the slab headers
+ * for other slabs "off slab".
+ * The locking for this is tricky in that it
+ * nests within the locks of all other slabs in a few
+ * places; to deal with this special locking we give
+ * this one slab a special class.
+ */
+static struct lock_class_key slab_name_lock_key;
+
+/*
  * This function must be completely optimized away if a constant is passed to
  * it.  Mostly the same as what is in linux/slab.h except it returns an index.
  */

@@ -1443,6 +1453,7 @@ void __init kmem_cache_init(void)
 		/* Replace the static kmem_list3 structures for the boot cpu */
 		init_list(&cache_cache, &initkmem_list3[CACHE_CACHE],
 			  numa_node_id());
+		lockdep_set_class(&(cache_cache.nodelists[numa_node_id()]->list_lock), &slab_name_lock_key);
 
 		for_each_online_node(node) {
 			init_list(malloc_sizes[INDEX_AC].cs_cachep,

Arjan van de Ven

2006-07-13 10:58 UTC #12 lore raw

Re: [patch] lockdep: more annotations for mm/slab.c

Quoted 18 lines · Arjan van de Ven

Quoted 8 lines · Ingo Molnar
Quoted 5 lines · Andrew Morton
Quoted 2 lines
---
 mm/slab.c |   45 +++++++++++++++++++++++++--------------------
geeze, what fuss. Can't we just tell lockdep "the locking here is correct, so buzz off"?
Quoted 7 lines
well, lockdep already found a locking bug in slab.c, so by telling lockdep to buzz off we lose the proof of correctness :-)
but i agree that this is getting a bit too intrusive. This patch is really just another expression of: 'slab locking is too complex', but i digress. Not all hope is lost though: Arjan thinks he can do a much simpler annotation.

Quoted 8 lines

I am hoping I can get away with just this patch; the idea is to give the cache_cache slab a special lock type since it'll be nested all the time (and has a natural ordering due to it's special position in the slab code). I'm not yet sure I found all places where this stuff is initialized (the slab code has gotten terribly complex with all the numa stuff added to it); I've started to test this now at least and so far it seems to work on my test box.

fwiw the slab where off-slab datastructures get stored needs this treatment as well, I've yet to decipher the slab code where this slab is though ;)

Ingo Molnar

2006-07-13 12:50 UTC #13 lore raw

PATCH 1/1 lockdep: undo mm/slab.c annotation

Subject: lockdep: undo mm/slab.c annotation
From: Ingo Molnar <[email protected]>

undo existing mm/slab.c lock-validator annotations, in preparation of a new, less intrusive annotation patch.

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

In reply to Andrew Morton

---
 mm/slab.c |   33 ++++++++++-----------------------
 1 file changed, 10 insertions(+), 23 deletions(-)

mm/slab.c +10 ~~-23~~

Index: linux/mm/slab.c
===================================================================
@@ -1021,8 +1021,7 @@ static void drain_alien_cache(struct kme
 	}
 }
 
-static inline int cache_free_alien(struct kmem_cache *cachep, void *objp,
-				   int nesting)
+static inline int cache_free_alien(struct kmem_cache *cachep, void *objp)
 {
 	struct slab *slabp = virt_to_slab(objp);
 	int nodeid = slabp->nodeid;

@@ -1040,7 +1039,7 @@ static inline int cache_free_alien(struc
 	STATS_INC_NODEFREES(cachep);
 	if (l3->alien && l3->alien[nodeid]) {
 		alien = l3->alien[nodeid];
-		spin_lock_nested(&alien->lock, nesting);
+		spin_lock(&alien->lock);
 		if (unlikely(alien->avail == alien->limit)) {
 			STATS_INC_ACOVERFLOW(cachep);
 			__drain_alien_cache(cachep, alien, nodeid);

@@ -1069,8 +1068,7 @@ static inline void free_alien_cache(stru
 {
 }
 
-static inline int cache_free_alien(struct kmem_cache *cachep, void *objp,
-				   int nesting)
+static inline int cache_free_alien(struct kmem_cache *cachep, void *objp)
 {
 	return 0;
 }

@@ -1760,8 +1758,6 @@ static void slab_destroy_objs(struct kme
 }
 #endif
 
-static void __cache_free(struct kmem_cache *cachep, void *objp, int nesting);
-
 /**
  * slab_destroy - destroy and release all objects in a slab
  * @cachep: cache pointer being destroyed

@@ -1785,17 +1781,8 @@ static void slab_destroy(struct kmem_cac
 		call_rcu(&slab_rcu->head, kmem_rcu_free);
 	} else {
 		kmem_freepages(cachep, addr);
-		if (OFF_SLAB(cachep)) {
-			unsigned long flags;
-
-			/*
-		 	 * lockdep: we may nest inside an already held
-			 * ac->lock, so pass in a nesting flag:
-			 */
-			local_irq_save(flags);
-			__cache_free(cachep->slabp_cache, slabp, 1);
-			local_irq_restore(flags);
-		}
+		if (OFF_SLAB(cachep))
+			kmem_cache_free(cachep->slabp_cache, slabp);
 	}
 }

@@ -3126,7 +3113,7 @@ static void cache_flusharray(struct kmem
 #endif
 	check_irq_off();
 	l3 = cachep->nodelists[node];
-	spin_lock_nested(&l3->list_lock, SINGLE_DEPTH_NESTING);
+	spin_lock(&l3->list_lock);
 	if (l3->shared) {
 		struct array_cache *shared_array = l3->shared;
 		int max = shared_array->limit - shared_array->avail;

@@ -3169,14 +3156,14 @@ free_done:
  * Release an obj back to its cache. If the obj has a constructed state, it must
  * be in this state _before_ it is released.  Called with disabled ints.
  */
-static void __cache_free(struct kmem_cache *cachep, void *objp, int nesting)
+static inline void __cache_free(struct kmem_cache *cachep, void *objp)
 {
 	struct array_cache *ac = cpu_cache_get(cachep);
 
 	check_irq_off();
 	objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));
 
-	if (cache_free_alien(cachep, objp, nesting))
+	if (cache_free_alien(cachep, objp))
 		return;
 
 	if (likely(ac->avail < ac->limit)) {

@@ -3415,7 +3402,7 @@ void kmem_cache_free(struct kmem_cache *
 	BUG_ON(virt_to_cache(objp) != cachep);
 
 	local_irq_save(flags);
-	__cache_free(cachep, objp, 0);
+	__cache_free(cachep, objp);
 	local_irq_restore(flags);
 }
 EXPORT_SYMBOL(kmem_cache_free);

@@ -3440,7 +3427,7 @@ void kfree(const void *objp)
 	kfree_debugcheck(objp);
 	c = virt_to_cache(objp);
 	debug_check_no_locks_freed(objp, obj_size(c));
-	__cache_free(c, (void *)objp, 0);
+	__cache_free(c, (void *)objp);
 	local_irq_restore(flags);
 }
 EXPORT_SYMBOL(kfree);

Ingo Molnar

2006-07-13 12:51 UTC #14 lore raw

PATCH 1/1 lockdep: annotate mm/slab.c

Subject: lockdep: annotate mm/slab.c
From: Arjan van de Ven <[email protected]>

mm/slab.c uses nested locking when dealing with 'off-slab' caches, in that case it allocates the slab header from the (on-slab) kmalloc caches. Teach the lock validator about this by putting all on-slab caches into a separate class.

this patch has no effect on non-lockdep kernels.

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

---
 mm/slab.c |   32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

mm/slab.c +32 -0

Index: linux/mm/slab.c
===================================================================
@@ -674,6 +674,37 @@ static struct kmem_cache cache_cache = {
 #endif
 };
 
+#ifdef CONFIG_LOCKDEP
+
+/*
+ * Slab sometimes uses the kmalloc slabs to store the slab headers
+ * for other slabs "off slab".
+ * The locking for this is tricky in that it nests within the locks
+ * of all other slabs in a few places; to deal with this special
+ * locking we put on-slab caches into a separate lock-class.
+ */
+static struct lock_class_key on_slab_key;
+
+static inline void init_lock_keys(struct cache_sizes *s)
+{
+	int q;
+
+	for (q = 0; q < MAX_NUMNODES; q++) {
+		if (!s->cs_cachep->nodelists[q] || OFF_SLAB(s->cs_cachep))
+			continue;
+		lockdep_set_class(&s->cs_cachep->nodelists[q]->list_lock,
+				  &on_slab_key);
+	}
+}
+
+#else
+static inline void init_lock_keys(struct cache_sizes *s)
+{
+}
+#endif
+
+
+
 /* Guard access to the cache-chain. */
 static DEFINE_MUTEX(cache_chain_mutex);
 static struct list_head cache_chain;

@@ -1391,6 +1422,7 @@ void __init kmem_cache_init(void)
 					ARCH_KMALLOC_FLAGS|SLAB_PANIC,
 					NULL, NULL);
 		}
+		init_lock_keys(sizes);
 
 		sizes->cs_dmacachep = kmem_cache_create(names->name_dma,
 					sizes->cs_size,

Chandra Seetharaman

author

2006-07-13 13:51 UTC #40 lore raw

Quoted 8 lines · Ingo Molnar

Quoted 4 lines · Chandra Seetharaman
By adding one patch at a time to 2.6.17's mm/slab.c, I found that the following patch is the cause of the panic.
--------------
[PATCH] lockdep: annotate SLAB code
great debugging!

Thanks.

Quoted 7 lines

I have reviewed that patch, and there's only one chunk that could possibly have a functional effect. The patch below undoes it - does that fix the crashes you are seeing? [If you have lockdep enabled then this patch will cause a lockdep false positive - ignore that one for now, it shouldnt impact the crash scenario itself.]

started the tests with this patch now. will report back in couple of hours... earlier if it crashes again :), which i doubt.

Thanks & regards,

chandra

Quoted 37 lines

Ingo
--------------------->
Subject: revert slab.c locking change
From: Ingo Molnar <[email protected]>
Chandra Seetharaman reported SLAB crashes caused by the slab.c lock annotation patch. There is only one chunk of that patch that has a material effect on the slab logic - this patch undoes that chunk.
Signed-off-by Ingo Molnar <[email protected]>
---
 mm/slab.c |    9 ---------
 1 file changed, 9 deletions(-)
Index: linux/mm/slab.c
===================================================================
mm/slab.c +0 -9
@@ -3100,16 +3100,7 @@ static void free_block(struct kmem_cache
 		if (slabp->inuse == 0) {
 			if (l3->free_objects > l3->free_limit) {
 				l3->free_objects -= cachep->num;
-				/*
-				 * It is safe to drop the lock. The slab is
-				 * no longer linked to the cache. cachep
-				 * cannot disappear - we are using it and
-				 * all destruction of caches must be
-				 * serialized properly by the user.
-				 */
-				spin_unlock(&l3->list_lock);
 				slab_destroy(cachep, slabp);
-				spin_lock(&l3->list_lock);
 			} else {
 				list_add(&slabp->list, &l3->slabs_free);
 			}

Signature · 4 lines

----------------------------------------------------------------------
    Chandra Seetharaman               | Be careful what you choose....
              - [email protected]   |      .......you may get it.
----------------------------------------------------------------------

Pekka Enberg

2006-07-13 15:45 UTC #15 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Hi,

Quoted 4 lines · Ingo Molnar

mm/slab.c uses nested locking when dealing with 'off-slab' caches, in that case it allocates the slab header from the (on-slab) kmalloc caches. Teach the lock validator about this by putting all on-slab caches into a separate class.

Which lock is that? This affects only caches that cache_grow() use, so we are really only interested in annotating kmalloc() on-slab caches (like in the patch), not _all_, right?

Pekka Enberg

2006-07-13 15:58 UTC #17 lore raw

Re: [patch] lockdep: annotate mm/slab.c

In reply to Chandra Seetharaman

Quoted 4 lines · Ingo Molnar

mm/slab.c uses nested locking when dealing with 'off-slab' caches, in that case it allocates the slab header from the (on-slab) kmalloc caches. Teach the lock validator about this by putting all on-slab caches into a separate class.

What's "nested lock" btw? If I understood from the other patch, you're talking about ac->lock. Surely you can't take the same lock twice but it's perfectly legal to take lock as long as the ac instance is different...

Chandra Seetharaman

author

2006-07-13 16:05 UTC #41 lore raw

On Thu, 2006-07-13 at 06:51 -0700, Chandra Seetharaman wrote:

Tests are running for more than 2 hours now. So, this patch fixed the panics i was seeing.

Thanks Ingo.

chandra

Quoted 62 lines · Ingo Molnar

Quoted 8 lines · Chandra Seetharaman
Quoted 5 lines
By adding one patch at a time to 2.6.17's mm/slab.c, I found that the following patch is the cause of the panic.
--------------
[PATCH] lockdep: annotate SLAB code
great debugging!
Thanks.
Quoted 7 lines
I have reviewed that patch, and there's only one chunk that could possibly have a functional effect. The patch below undoes it - does that fix the crashes you are seeing? [If you have lockdep enabled then this patch will cause a lockdep false positive - ignore that one for now, it shouldnt impact the crash scenario itself.]
started the tests with this patch now. will report back in couple of hours... earlier if it crashes again :), which i doubt.
Thanks & regards,
chandra
Quoted 37 lines
Ingo
--------------------->
Subject: revert slab.c locking change
From: Ingo Molnar <[email protected]>
Chandra Seetharaman reported SLAB crashes caused by the slab.c lock annotation patch. There is only one chunk of that patch that has a material effect on the slab logic - this patch undoes that chunk.
Signed-off-by Ingo Molnar <[email protected]>
---
 mm/slab.c |    9 ---------
 1 file changed, 9 deletions(-)
Index: linux/mm/slab.c
===================================================================
mm/slab.c +0 -9
@@ -3100,16 +3100,7 @@ static void free_block(struct kmem_cache
 		if (slabp->inuse == 0) {
 			if (l3->free_objects > l3->free_limit) {
 				l3->free_objects -= cachep->num;
-				/*
-				 * It is safe to drop the lock. The slab is
-				 * no longer linked to the cache. cachep
-				 * cannot disappear - we are using it and
-				 * all destruction of caches must be
-				 * serialized properly by the user.
-				 */
-				spin_unlock(&l3->list_lock);
 				slab_destroy(cachep, slabp);
-				spin_lock(&l3->list_lock);
 			} else {
 				list_add(&slabp->list, &l3->slabs_free);
 			}

Signature · 4 lines

----------------------------------------------------------------------
    Chandra Seetharaman               | Be careful what you choose....
              - [email protected]   |      .......you may get it.
----------------------------------------------------------------------

Linus Torvalds

2006-07-13 18:50 UTC #33 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 19 lines · Ingo Molnar

mm/slab.c +18 -0

+#ifdef CONFIG_LOCKDEP
+
+/*
+ * Slab sometimes uses the kmalloc slabs to store the slab headers
+ * for other slabs "off slab".
+ * The locking for this is tricky in that it nests within the locks
+ * of all other slabs in a few places; to deal with this special
+ * locking we put on-slab caches into a separate lock-class.
+ */
+static struct lock_class_key on_slab_key;
+
+static inline void init_lock_keys(struct cache_sizes *s)
+{
+	int q;
+
+	for (q = 0; q < MAX_NUMNODES; q++) {
+		if (!s->cs_cachep->nodelists[q] || OFF_SLAB(s->cs_cachep))
+			continue;

mm/slab.c static struct kmem_cache cache_cache = { · line 704

Quoted 10 lines

mm/slab.c +10 -0

+		lockdep_set_class(&s->cs_cachep->nodelists[q]->list_lock,
+				  &on_slab_key);
+	}
+}
+
+#else
+static inline void init_lock_keys(struct cache_sizes *s)
+{
+}
+#endif

Why isn't the "on_slab_key" local to just the init_lock_keys() function, and the #ifdef around it all?

Ie just

	static inline void init_lock_keys(struct cache_sizes *s)
	{
	#ifdef CONFIG_LOCKDEP
		static struct lock_class_key on_slab_key;
		int q;

		for (q = 0; q < MAX_NUMNODES; q++) {
			...
	#endif CONFIG_LOCKDEP
	}

instead?

Linus

Linus Torvalds

2006-07-13 19:00 UTC #18 lore raw

Re: [patch] lockdep: annotate mm/slab.c

In reply to Pekka Enberg

Quoted 5 lines · Pekka Enberg

What's "nested lock" btw? If I understood from the other patch, you're talking about ac->lock. Surely you can't take the same lock twice but it's perfectly legal to take lock as long as the ac instance is different...

Normally, no. You can't take another lock just because the instance is different. That causes ABBA deadlocks unless you have some underlying _ordering_ of the different lock instances.

Linus

Arjan van de Ven

2006-07-13 19:06 UTC #34 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 4 lines · Linus Torvalds

Why isn't the "on_slab_key" local to just the init_lock_keys() function,
and the #ifdef around it all?

it's the same net results; the variable is 0 bytes in size for !LOCKDEP

Arjan van de Ven

2006-07-13 19:21 UTC #19 lore raw

Re: [patch] lockdep: annotate mm/slab.c

In reply to Arjan van de Ven

Quoted 11 lines · Linus Torvalds

Quoted 5 lines · Pekka Enberg
What's "nested lock" btw? If I understood from the other patch, you're talking about ac->lock. Surely you can't take the same lock twice but it's perfectly legal to take lock as long as the ac instance is different...
Normally, no. You can't take another lock just because the instance is different. That causes ABBA deadlocks unless you have some underlying _ordering_ of the different lock instances.

and that is the case here fwiw;
the OFF_SLAB metadata thing is tricky when freeing stuff:

for kfree() you take the lock for your own slab, do some management and then do effectively do a kfree() on your off-slab metadata. Which then takes the lock for the kmalloc slab of the size of your metadata. This is a natural order, you assume (and pray) that this kmalloc slab is not in itself a slab with off-slab metadata, so that there can't be a BA of the ABBA deadlock. [*]

This is what needed the lockdep annotation; lockdep by default thinks all slabs are equal (by virtue of sharing the spin_lock_init() location). And because of the slab-internal knowledge of off-slab versus not-off-slab they're not equal.

Now there are two choices for annotation: tell the spin lock aquisition that there is a natural hierarchy (eg spin_lock_depends) and this is what Ingo tried at first. Except that it got horribly complex, messy and just outright gross.

The second option is telling lockdep that kmalloc slabs without off-slab metadata are really different in terms of locking rules (eg they have a separate identity than the other slabs); and that is why my patch does (or at least tries to; it works for my machines but the slab initialization code is horribly complex wrt hotplug and numa so I may have missed a corner case initialization).

The downside of this 'separate identity' is that you basically split the lock history, meaning that the graph of past history is not built up as fast as it could have been. Slab is used so much that that isn't a big deal; for other more exotic cases that's more of a quality issue.

Greetings,
Arjan van de Ven

[*] Note Note Note
there is a corner case in the slab code that I personally don't trust at all. In the NUMA case, if the memory is not originally from your own node, the cache_free_alien() function takes, while having your own local lock, the lock of the remote node as well. (at least on my reading of the code) to free the memory to that node. I have yet to see where in the code it safeguards against that remote node doing the exact same thing in the opposite direction concurrently, and causing a basic ABBA deadlock.

Linus Torvalds

2006-07-13 19:21 UTC #35 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 7 lines · Arjan van de Ven

Quoted 4 lines · Linus Torvalds
Why isn't the "on_slab_key" local to just the init_lock_keys() function,
and the #ifdef around it all?
it's the same net results; the variable is 0 bytes in size for !LOCKDEP

That's not why I reacted. I reacted because the code is ugly, and would be much cleaner if it had everything in one place.

Btw, the variable size for !LOCKDEP is totally irrelevant: you need to have it inside the #ifdef LOCKDEP _anyway_, if only yo shut up gcc about unused static variables. Which you did do, by duplicating the function (once empty), and having an #else part to it all.

Linus

Ingo Molnar

2006-07-13 19:23 UTC #37 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 2 lines · Linus Torvalds

Why isn't the "on_slab_key" local to just the init_lock_keys() function, and the #ifdef around it all?

yeah - find updated patch below.

Ingo

------->
Subject: lockdep: annotate mm/slab.c
From: Arjan van de Ven <[email protected]>

this patch has no effect on non-lockdep kernels.

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

---
 mm/slab.c |   25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

mm/slab.c +25 -0

Index: linux/mm/slab.c
===================================================================
@@ -674,6 +674,30 @@ static struct kmem_cache cache_cache = {
 #endif
 };
 
+/*
+ * Slab sometimes uses the kmalloc slabs to store the slab headers
+ * for other slabs "off slab".
+ * The locking for this is tricky in that it nests within the locks
+ * of all other slabs in a few places; to deal with this special
+ * locking we put on-slab caches into a separate lock-class.
+ */
+static inline void init_lock_keys(struct cache_sizes *s)
+{
+#ifdef CONFIG_LOCKDEP
+	static struct lock_class_key on_slab_key;
+	int q;
+
+	for (q = 0; q < MAX_NUMNODES; q++) {
+		if (!s->cs_cachep->nodelists[q] || OFF_SLAB(s->cs_cachep))
+			continue;
+		lockdep_set_class(&s->cs_cachep->nodelists[q]->list_lock,
+				  &on_slab_key);
+	}
+#endif
+}
+
+
+
 /* Guard access to the cache-chain. */
 static DEFINE_MUTEX(cache_chain_mutex);
 static struct list_head cache_chain;

@@ -1391,6 +1415,7 @@ void __init kmem_cache_init(void)
 					ARCH_KMALLOC_FLAGS|SLAB_PANIC,
 					NULL, NULL);
 		}
+		init_lock_keys(sizes);
 
 		sizes->cs_dmacachep = kmem_cache_create(names->name_dma,
 					sizes->cs_size,

Ingo Molnar

2006-07-13 19:25 UTC #38 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 6 lines · Ingo Molnar

Quoted 2 lines · Linus Torvalds
Why isn't the "on_slab_key" local to just the init_lock_keys() function, and the #ifdef around it all?
yeah - find updated patch below.

(find yet another update below - there were too many newlines added after the function.)

------->
Subject: lockdep: annotate mm/slab.c
From: Arjan van de Ven <[email protected]>

this patch has no effect on non-lockdep kernels.

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

---
 mm/slab.c |   23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

mm/slab.c +23 -0

Index: linux/mm/slab.c
===================================================================
@@ -674,6 +674,28 @@ static struct kmem_cache cache_cache = {
 #endif
 };
 
+/*
+ * Slab sometimes uses the kmalloc slabs to store the slab headers
+ * for other slabs "off slab".
+ * The locking for this is tricky in that it nests within the locks
+ * of all other slabs in a few places; to deal with this special
+ * locking we put on-slab caches into a separate lock-class.
+ */
+static inline void init_lock_keys(struct cache_sizes *s)
+{
+#ifdef CONFIG_LOCKDEP
+	static struct lock_class_key on_slab_key;
+	int q;
+
+	for (q = 0; q < MAX_NUMNODES; q++) {
+		if (!s->cs_cachep->nodelists[q] || OFF_SLAB(s->cs_cachep))
+			continue;
+		lockdep_set_class(&s->cs_cachep->nodelists[q]->list_lock,
+				  &on_slab_key);
+	}
+#endif
+}
+
 /* Guard access to the cache-chain. */
 static DEFINE_MUTEX(cache_chain_mutex);
 static struct list_head cache_chain;

@@ -1391,6 +1413,7 @@ void __init kmem_cache_init(void)
 					ARCH_KMALLOC_FLAGS|SLAB_PANIC,
 					NULL, NULL);
 		}
+		init_lock_keys(sizes);
 
 		sizes->cs_dmacachep = kmem_cache_create(names->name_dma,
 					sizes->cs_size,

Arjan van de Ven

2006-07-13 19:26 UTC #36 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 5 lines · Linus Torvalds

Quoted 2 lines · Arjan van de Ven
Quoted 1 line · Linus Torvalds

Quoted 8 lines

Quoted 5 lines
Quoted 3 lines
Why isn't the "on_slab_key" local to just the init_lock_keys() function,
and the #ifdef around it all?
it's the same net results; the variable is 0 bytes in size for !LOCKDEP
That's not why I reacted. I reacted because the code is ugly, and would be much cleaner if it had everything in one place.

fair enough

Ingo Molnar

2006-07-13 19:38 UTC #32 lore raw

Re: [patch] lockdep: annotate mm/slab.c

In reply to Pekka Enberg

Quoted 10 lines · Pekka Enberg

Quoted 4 lines · Ingo Molnar
mm/slab.c uses nested locking when dealing with 'off-slab' caches, in that case it allocates the slab header from the (on-slab) kmalloc caches. Teach the lock validator about this by putting all on-slab caches into a separate class.
What's "nested lock" btw? If I understood from the other patch, you're talking about ac->lock. Surely you can't take the same lock twice but it's perfectly legal to take lock as long as the ac instance is different...

yeah - there's some ambiguity of the term "nested lock". For the lock validator it means "holding two instances of the same lock class". A "lock class" is something like inode->i_mutex. (standalone static locks like cache_chain_mutex form their own singleton lock class. See Documentation/lockdep-design.txt for more details.)

"trying to lock the same lock instance twice" we call "recursive locking", and that's a bug for everything except read_lock() on rwlocks. There is no "recursive locking" in slab.c, but there is "nested locking". For the case of "nested locking" the lock validator needs to be taught of the relation between instances. Most of the cases the relation is "static" and can thus be assigned build-time via the use of separate lock-keys that "split up" a class into subclasses. In rare cases the relation is dynamic (for example the VFS has such nesting rules).

initially i annotated slab.c via dynamic nesting - but as Arjan has correctly observed, most of the nested locking in slab.c is of static
type: we first take the off-slab lock, then the on-slab lock. [or we only take an on-slab lock, if the cache is on-slab]

Note: nested locking annotations arent just done to "shut up" lockdep, but rather to enable lockdep from now on to enforce this dependency
rule: if anywhere we take an off-slab lock after an on-slab lock it will print a warning. That's why we go the trouble of identifying all the nested locking cases instead of going the easy path of "shutting lockdep off" (we could trivially ignore nesting within lockdep.c) - there were a couple of locking bugs found already that were related to nested locking.

btw., there's still one nested locking construct in slab.c that could cause problems:

 Call Trace:
  [<ffffffff8020b0b9>] show_trace+0xaa/0x23d
  [<ffffffff8020b261>] dump_stack+0x15/0x17
  [<ffffffff802456c4>] __lock_acquire+0x127/0x9c4
  [<ffffffff8024648b>] lock_acquire+0x4b/0x6a
  [<ffffffff804aead3>] _spin_lock+0x25/0x31
  [<ffffffff8027301a>] __drain_alien_cache+0x34/0x78
  [<ffffffff80272b1f>] __cache_free+0xe8/0x215
  [<ffffffff80272dc4>] slab_destroy+0x9e/0xc2
  [<ffffffff80272ed3>] free_block+0xeb/0x135
  [<ffffffff80273043>] __drain_alien_cache+0x5d/0x78
  [<ffffffff80272b1f>] __cache_free+0xe8/0x215
  [<ffffffff80273203>] kfree+0x8c/0xb0

what guarantees that while we are 'draining' another node's cache, that other node does not drain our cache (and thus we'd deadlock)?

Ingo

Ingo Molnar

2006-07-13 20:01 UTC #16 lore raw

Re: [patch] lockdep: annotate mm/slab.c

In reply to Pekka Enberg

Quoted 11 lines · Pekka Enberg

Hi,
Quoted 4 lines · Ingo Molnar
mm/slab.c uses nested locking when dealing with 'off-slab' caches, in that case it allocates the slab header from the (on-slab) kmalloc caches. Teach the lock validator about this by putting all on-slab caches into a separate class.
Which lock is that? This affects only caches that cache_grow() use, so we are really only interested in annotating kmalloc() on-slab caches (like in the patch), not _all_, right?

it's ->list_lock, and a sample nesting scenario is:

 [<c013a9a8>] lock_acquire+0x78/0xa0
 [<c0313e5a>] _spin_lock_nested+0x2a/0x40
 [<c0163024>] __cache_free+0x484/0x5c0
 [<c01632ad>] slab_destroy+0x14d/0x1e0
 [<c0162ac9>] free_block+0x189/0x1e0
 [<c01630f4>] __cache_free+0x554/0x5c0
 [<c0163653>] kmem_cache_free+0x73/0xc0
 [<c016a24f>] file_free_rcu+0xf/0x20
 [<c0130755>] __rcu_process_callbacks+0x75/0x1b0
 [<c0130bc7>] rcu_process_callbacks+0x27/0x50
 [<c0123f3a>] tasklet_action+0x6a/0xf0
 [<c012413b>] __do_softirq+0x8b/0x130
 [<c0106ba3>] do_softirq+0x73/0x100

(the off-slab nesting is perfectly correct locking code AFAICS - it just needs to be taught to lockdep - which the patch does. OTOH i'm less sure about the NUMA alien-cache-draining nesting.)

Ingo

Andrew Morton

2006-07-13 21:31 UTC #39 lore raw

Re: [patch] lockdep: annotate mm/slab.c

In reply to Arjan van de Ven

Quoted 49 lines · On Thu, 13 Jul 2006 11:50:01 -0700 (PDT) Linus Torvalds <[email protected]>…

Quoted 19 lines · Ingo Molnar

mm/slab.c +18 -0

+#ifdef CONFIG_LOCKDEP
+
+/*
+ * Slab sometimes uses the kmalloc slabs to store the slab headers
+ * for other slabs "off slab".
+ * The locking for this is tricky in that it nests within the locks
+ * of all other slabs in a few places; to deal with this special
+ * locking we put on-slab caches into a separate lock-class.
+ */
+static struct lock_class_key on_slab_key;
+
+static inline void init_lock_keys(struct cache_sizes *s)
+{
+	int q;
+
+	for (q = 0; q < MAX_NUMNODES; q++) {
+		if (!s->cs_cachep->nodelists[q] || OFF_SLAB(s->cs_cachep))
+			continue;

mm/slab.c static struct kmem_cache cache_cache = { · line 704

Quoted 10 lines

mm/slab.c +10 -0

+		lockdep_set_class(&s->cs_cachep->nodelists[q]->list_lock,
+				  &on_slab_key);
+	}
+}
+
+#else
+static inline void init_lock_keys(struct cache_sizes *s)
+{
+}
+#endif

Why isn't the "on_slab_key" local to just the init_lock_keys() function, and the #ifdef around it all?

Ie just

	static inline void init_lock_keys(struct cache_sizes *s)
	{
	#ifdef CONFIG_LOCKDEP
		static struct lock_class_key on_slab_key;
		int q;

		for (q = 0; q < MAX_NUMNODES; q++) {
			...
	#endif CONFIG_LOCKDEP
	}

Quoted 2 lines

instead?

It could be wholly hidded inside a macro

#define lockdep_go_away(p) {
		static struct lock_class_key foo;
		lockdep_set_class(p, &foo);
	}

But istr suggesting that a couple of weeks ago and was given a good-sounding reason which I forget.

At least when the code laid out as Ingo proposed, we have room for a decent comment, which is rather desirable for this sort of thing.

Christoph Lameter

2006-07-13 22:27 UTC #20 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 8 lines · Arjan van de Ven

there is a corner case in the slab code that I personally don't trust at all. In the NUMA case, if the memory is not originally from your own node, the cache_free_alien() function takes, while having your own local lock, the lock of the remote node as well. (at least on my reading of the code) to free the memory to that node. I have yet to see where in the code it safeguards against that remote node doing the exact same thing in the opposite direction concurrently, and causing a basic ABBA deadlock.

Hmmm.. This case is only followed during bootup when we do not have alien caches yet. And its pretty rare to free memory on bootup. Once the alien caches are present then we do not take the listlock anymore but use the lock of the alien structure.

This could cause an ABBA deadlock if a free happens on another processor during bootup before all the slabs are established.

That then brings us to look if a slab free can happen before a slab is completely established via kmem_cache_create.

kmem_cache_create takes the cpu hotplug lock and the cache_chain_mutex.

One could argue that a subsystem must make sure that the slab cache it creates should not be used before kmem_cache_create is complete?

Alokk: Do we really need to check for alien caches not present there?

Christoph Lameter

2006-07-13 22:51 UTC #22 lore raw

Re: [patch] lockdep: annotate mm/slab.c

In reply to Arjan van de Ven

Quoted 9 lines · Arjan van de Ven

[*] Note Note Note
there is a corner case in the slab code that I personally don't trust at all. In the NUMA case, if the memory is not originally from your own node, the cache_free_alien() function takes, while having your own local lock, the lock of the remote node as well. (at least on my reading of the code) to free the memory to that node. I have yet to see where in the code it safeguards against that remote node doing the exact same thing in the opposite direction concurrently, and causing a basic ABBA deadlock.

Second look: I cannot find where we take our own local nodes list_lock. We only take the lock from the remote node. Or is this related to the OFF_SLAB kfree issue?

We either have a alien cache structure established then:

We take a lock on the alien structure for node x from our own node (without holding our local list_lock!) and then we need take the remote list_lock for node x if the alien structure overflows and we then free to the remote nodes list.

Or we do not have a alien cache structure established yet. Then:

We simply take the remote list_lock on node x and free directly to the foreign nodes list.

In an OFF_SLAB situation this may differ because then we call kmem_cache_free from slab_destroy. Ughhh... This looks extremely bad. Whew! We drop the list lock before calling slab_destroy.

Alok kataria

2006-07-13 23:08 UTC #21 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Hi,

Quoted 11 lines · Christoph Lameter

Quoted 8 lines · Arjan van de Ven
there is a corner case in the slab code that I personally don't trust at all. In the NUMA case, if the memory is not originally from your own node, the cache_free_alien() function takes, while having your own local lock, the lock of the remote node as well. (at least on my reading of the code) to free the memory to that node. I have yet to see where in the code it safeguards against that remote node doing the exact same thing in the opposite direction concurrently, and causing a basic ABBA deadlock.

Quoted 5 lines

Hmmm.. This case is only followed during bootup when we do not have alien caches yet. And its pretty rare to free memory on bootup. Once the alien caches are present then we do not take the listlock anymore but use the lock of the alien structure.

Christoph, IMO even then we wont deadlock, because in the case of a remote free when there are no alien caches, we simply take the remote node's list_lock and free the object, directly in the remote slab.

Quoted 6 lines

This could cause an ABBA deadlock if a free happens on another processor during bootup before all the slabs are established.
That then brings us to look if a slab free can happen before a slab is completely established via kmem_cache_create.

Quoted 7 lines

kmem_cache_create takes the cpu hotplug lock and the cache_chain_mutex.
One could argue that a subsystem must make sure that the slab cache it creates should not be used before kmem_cache_create is complete?
Alokk: Do we really need to check for alien caches not present there?

Yes we do need to, there can be a case when all cpu's of a node have gone down, we free the alien cache, and this alien cache might have come from this cache itself, (see cpuup_callback). In this case we will find the alien caches to be absent and then we will directly free to the remote nodes slab.

Thanks & Regards,
Alok

Quoted 7 lines

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 4 lines

A computer scientist is someone who, when told to "Go to Hell," sees
the "go to," rather than the destination, as harmful.

Alok Kataria

Andrew Morton

2006-07-13 23:17 UTC #23 lore raw

Re: [patch] lockdep: annotate mm/slab.c

http://www.kernel.org/git/gitweb.cgi?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=fc818301a8a39fedd7f0a71f878f29130c72193d

Quoted 26 lines · On Thu, 13 Jul 2006 15:51:09 -0700 (PDT) Christoph Lameter <[email protected]>…

Quoted 9 lines · Arjan van de Ven
[*] Note Note Note
there is a corner case in the slab code that I personally don't trust at all. In the NUMA case, if the memory is not originally from your own node, the cache_free_alien() function takes, while having your own local lock, the lock of the remote node as well. (at least on my reading of the code) to free the memory to that node. I have yet to see where in the code it safeguards against that remote node doing the exact same thing in the opposite direction concurrently, and causing a basic ABBA deadlock.
Second look: I cannot find where we take our own local nodes list_lock. We only take the lock from the remote node. Or is this related to the OFF_SLAB kfree issue?
We either have a alien cache structure established then:
We take a lock on the alien structure for node x from our own node (without holding our local list_lock!) and then we need take the remote list_lock for node x if the alien structure overflows and we then free to the remote nodes list.
Or we do not have a alien cache structure established yet. Then:

Quoted 7 lines

We simply take the remote list_lock on node x and free directly to the foreign nodes list.
In an OFF_SLAB situation this may differ because then we call kmem_cache_free from slab_destroy. Ughhh... This looks extremely bad.

uh-oh.

Quoted 1 line

Whew! We drop the list lock before calling slab_destroy.

Well we did, up until about ten minutes ago.

free_block()'s droppage of l3->list_lock around the slab_destroy() call was just reverted, due to Shailabh confirming that it caused corruption.

Christoph Lameter

2006-07-14 02:30 UTC #24 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 6 lines · Andrew Morton

Quoted 1 line
Whew! We drop the list lock before calling slab_destroy.
Well we did, up until about ten minutes ago.
free_block()'s droppage of l3->list_lock around the slab_destroy() call was just reverted, due to Shailabh confirming that it caused corruption.

How would this slab become corrupted if it is no longer on the lists?

Christoph Lameter

2006-07-14 02:46 UTC #25 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Could we please remove the fake revert from the git tree immediately?

2.6.17 code has also the dropping of the lock. This was no reversion. Maybe there is a problem but then I'd like to hear about it:

               /* fixup slab chains */
                if (slabp->inuse == 0) {
                        if (l3->free_objects > l3->free_limit) {
                                l3->free_objects -= cachep->num;
                                /*
                                 * It is safe to drop the lock. The slab is
                                 * no longer linked to the cache. cachep
                                 * cannot disappear - we are using it and
                                 * all destruction of caches must be
                                 * serialized properly by the user.
                                 */
                                spin_unlock(&l3->list_lock);
                                slab_destroy(cachep, slabp);
                                spin_lock(&l3->list_lock);
                        } else {
                                list_add(&slabp->list, &l3->slabs_free);
                        }

Andrew Morton

2006-07-14 02:55 UTC #30 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 10 lines · On Thu, 13 Jul 2006 19:29:52 -0700 (PDT) Christoph Lameter <[email protected]>…

Quoted 6 lines · Andrew Morton
Quoted 1 line
Whew! We drop the list lock before calling slab_destroy.
Well we did, up until about ten minutes ago.
free_block()'s droppage of l3->list_lock around the slab_destroy() call was just reverted, due to Shailabh confirming that it caused corruption.
How would this slab become corrupted if it is no longer on the lists?

It's a bad sign that this question is flowing in the you->me direction ;)

I don't see anywhere under slab_destroy() where *cachep state gets altered.

The change did cause free_block->slab_destroy->__cache_free->cache_free_alien to no longer be called under this slab's l3->list_lock. Maybe that locking is (accidentally?) protecting something?

Christoph Lameter

2006-07-14 03:00 UTC #31 lore raw

Re: [patch] lockdep: annotate mm/slab.c

Quoted 3 lines · Andrew Morton

Quoted 1 line
How would this slab become corrupted if it is no longer on the lists?
It's a bad sign that this question is flowing in the you->me direction ;)

Take it as a rhetorical question reflecting my lack of details about this issue.

Quoted 7 lines

I don't see anywhere under slab_destroy() where *cachep state gets altered.
The change did cause free_block->slab_destroy->__cache_free->cache_free_alien to no longer be called under this slab's l3->list_lock. Maybe that locking is (accidentally?) protecting something?

Yes this is also protecting the shared array. It is invalid to use free_block on elements of the shared array. It is valid to use free block on per cpu arrays since they are protected only by interrupt disable. It also valid to use free_block on alien caches because they have their own lock.

Still looking.....

Andrew Morton

2006-07-14 03:03 UTC #26 lore raw

Re: [patch] lockdep: annotate mm/slab.c