Lockdep complains about commit 1331e7a1bb ("rcu: Remove _rcu_barrier() dependency on __stop_machine()")

Hi,

this commit:

==
1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

Quoted 22 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

Quoted 4 lines

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

Hmmm... Does the following patch help? It swaps the order in which rcu_barrier() acquires the hotplug and rcu_barrier locks.

Quoted 22 lines

Quoted 22 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

Quoted 7 lines

Quoted 4 lines

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

Hmmm... Does the following patch help? It swaps the order in which rcu_barrier() acquires the hotplug and rcu_barrier locks.

It changed the report slightly (see for example the change in possible unsafe locking scenario, rcu_sched_state.barrier_mutex vanished and it's now directly about cpu_hotplug.lock). With the patch applied I get

======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-03888-g3f99f3b #145 Not tainted

Quoted 36 lines

Quoted 22 lines

Quoted 22 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

Quoted 7 lines

Quoted 4 lines

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

Hmmm... Does the following patch help? It swaps the order in which rcu_barrier() acquires the hotplug and rcu_barrier locks.

It changed the report slightly (see for example the change in possible unsafe locking scenario, rcu_sched_state.barrier_mutex vanished and it's now directly about cpu_hotplug.lock). With the patch applied I get

Quoted 3 lines

======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-03888-g3f99f3b #145 Not tainted

And it really seems valid.

kmem_cache_destroy() calls rcu_barrier() with slab_mutex locked, which introduces slab_mutex -> cpu_hotplug.lock dependency (through rcu_barrier() -> _rcu_barrier() -> get_online_cpus()).

On the other hand, _cpu_up() acquires cpu_hotplug.lock through cpu_hotplug_begin(), and with this lock held cpuup_callback() notifier gets called, which acquires slab_mutex. This gives the reverse dependency, i.e. deadlock scenario is valid one.

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is triggering this, because before that, there was no slab_mutex -> cpu_hotplug.lock dependency.

Simply put, the commit causes get_online_cpus() to be called with slab_mutex held, which is invalid.

Quoted 36 lines · Jiri Kosina

Quoted 36 lines

Quoted 22 lines

Quoted 22 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

Quoted 7 lines

Quoted 4 lines

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

Hmmm... Does the following patch help? It swaps the order in which rcu_barrier() acquires the hotplug and rcu_barrier locks.

It changed the report slightly (see for example the change in possible unsafe locking scenario, rcu_sched_state.barrier_mutex vanished and it's now directly about cpu_hotplug.lock). With the patch applied I get

Quoted 5 lines

Quoted 3 lines

======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-03888-g3f99f3b #145 Not tainted

And it really seems valid.

Quoted 9 lines

kmem_cache_destroy() calls rcu_barrier() with slab_mutex locked, which introduces slab_mutex -> cpu_hotplug.lock dependency (through rcu_barrier() -> _rcu_barrier() -> get_online_cpus()).

On the other hand, _cpu_up() acquires cpu_hotplug.lock through cpu_hotplug_begin(), and with this lock held cpuup_callback() notifier gets called, which acquires slab_mutex. This gives the reverse dependency, i.e. deadlock scenario is valid one.

Quoted 5 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is triggering this, because before that, there was no slab_mutex -> cpu_hotplug.lock dependency.

Simply put, the commit causes get_online_cpus() to be called with slab_mutex held, which is invalid.

Oh, and it seems to be actually triggering in real.

With HEAD being 974a847e00c, machine suspends nicely. With 974a847e00c + your patch, changing the order in which rcu_barrier() acquires hotplug and rcu_barrier locks, the machine hangs 100% reliably during suspend, which very likely actually is the deadlock described above.

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events. I could go back to the old approach, but it is significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

Quoted 7 lines · Paul E. McKenney

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events. I could go back to the old approach, but it is significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

Quoted 6 lines

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

Sorry, I don't think I understand what you are proposing just yet.

If I understand it correctly, you are proposing to introduce some magic into _rcu_barrier() such as (pseudocode of course):

if (!being_called_from_hotplug_notifier_callback)
get_online_cpus()

How does that protect from the scenario I've outlined before though?

	CPU 0                           CPU 1
	kmem_cache_destroy()
	mutex_lock(slab_mutex)
					_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)	

CPU 0 grabs both locks anyway (it's not running from notifier callback). CPU 1 grabs both locks as well, as there is no _rcu_barrier() being called from notifier callback either.

What did I miss?

Quoted 40 lines · Jiri Kosina

Quoted 7 lines · Paul E. McKenney

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events. I could go back to the old approach, but it is significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

Quoted 6 lines

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

Sorry, I don't think I understand what you are proposing just yet.

If I understand it correctly, you are proposing to introduce some magic into _rcu_barrier() such as (pseudocode of course):

if (!being_called_from_hotplug_notifier_callback)
get_online_cpus()

How does that protect from the scenario I've outlined before though?

	CPU 0                           CPU 1
	kmem_cache_destroy()
	mutex_lock(slab_mutex)
					_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)	

Quoted 5 lines

CPU 0 grabs both locks anyway (it's not running from notifier callback). CPU 1 grabs both locks as well, as there is no _rcu_barrier() being called from notifier callback either.

What did I miss?

You didn't miss anything, I was suffering a failure to read carefully.

So my next stupid question is "Why can't kmem_cache_destroy drop slab_mutex early?" like the following:

	void kmem_cache_destroy(struct kmem_cache *cachep)
	{
		BUG_ON(!cachep || in_interrupt());

		/* Find the cache in the chain of caches. */
		get_online_cpus();
		mutex_lock(&slab_mutex);
		/*
		 * the chain is never empty, cache_cache is never destroyed
		 */
		list_del(&cachep->list);
		if (__cache_shrink(cachep)) {
			slab_error(cachep, "Can't free all objects");
			list_add(&cachep->list, &slab_caches);
			mutex_unlock(&slab_mutex);
			put_online_cpus();
			return;
		}
		mutex_unlock(&slab_mutex);

		if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
			rcu_barrier();

		__kmem_cache_destroy(cachep);
		put_online_cpus();
	}

Or did I miss some reason why __kmem_cache_destroy() needs that lock? Looks to me like it is just freeing now-disconnected memory.

Quoted 79 lines · Paul E. McKenney

Quoted 40 lines · Jiri Kosina

Quoted 7 lines · Paul E. McKenney

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events. I could go back to the old approach, but it is significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

Quoted 6 lines

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

Sorry, I don't think I understand what you are proposing just yet.

If I understand it correctly, you are proposing to introduce some magic into _rcu_barrier() such as (pseudocode of course):

if (!being_called_from_hotplug_notifier_callback)
get_online_cpus()

How does that protect from the scenario I've outlined before though?

	CPU 0                           CPU 1
	kmem_cache_destroy()
	mutex_lock(slab_mutex)
					_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)	

Quoted 5 lines

CPU 0 grabs both locks anyway (it's not running from notifier callback). CPU 1 grabs both locks as well, as there is no _rcu_barrier() being called from notifier callback either.

What did I miss?

You didn't miss anything, I was suffering a failure to read carefully.

So my next stupid question is "Why can't kmem_cache_destroy drop slab_mutex early?" like the following:

	void kmem_cache_destroy(struct kmem_cache *cachep)
	{
		BUG_ON(!cachep || in_interrupt());

		/* Find the cache in the chain of caches. */
		get_online_cpus();
		mutex_lock(&slab_mutex);
		/*
		 * the chain is never empty, cache_cache is never destroyed
		 */
		list_del(&cachep->list);
		if (__cache_shrink(cachep)) {
			slab_error(cachep, "Can't free all objects");
			list_add(&cachep->list, &slab_caches);
			mutex_unlock(&slab_mutex);
			put_online_cpus();
			return;
		}
		mutex_unlock(&slab_mutex);

		if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
			rcu_barrier();

		__kmem_cache_destroy(cachep);
		put_online_cpus();
	}

Quoted 2 lines

Or did I miss some reason why __kmem_cache_destroy() needs that lock? Looks to me like it is just freeing now-disconnected memory.

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

It makes the lockdep happy again, and obviously removes the deadlock (I tested it).

From: Jiri Kosina <[email protected]>
Subject: mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

This opens a possibilty for deadlock:

        CPU 0                           CPU 1
	        kmem_cache_destroy()
	        mutex_lock(slab_mutex)
	                                        _cpu_up()
	                                        cpu_hotplug_begin()
	                                        mutex_lock(cpu_hotplug.lock)
	        rcu_barrier()
	        _rcu_barrier()
	        get_online_cpus()
	        mutex_lock(cpu_hotplug.lock)
	         (blocks, CPU 1 has the mutex)
	                                        __cpu_notify()
	                                        mutex_lock(slab_mutex)

It turns out that slab's kmem_cache_destroy() might release slab_mutex earlier before calling out to rcu_barrier(), as cachep has already been unlinked.

This patch removes the AB-BA dependency by calling rcu_barrier() with slab_mutex already unlocked.

Signed-off-by Jiri Kosina <[email protected]>

---
 mm/slab.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

mm/slab.c +1 -1

index 1133911..693c7cb 100644
@@ -2801,12 +2801,12 @@ void kmem_cache_destroy(struct kmem_cache *cachep)
 		put_online_cpus();
 		return;
 	}
+	mutex_unlock(&slab_mutex);
 
 	if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
 		rcu_barrier();
 
 	__kmem_cache_destroy(cachep);
-	mutex_unlock(&slab_mutex);
 	put_online_cpus();
 }
 EXPORT_SYMBOL(kmem_cache_destroy);

Signature · 3 lines

-- 
Jiri Kosina
SUSE Labs

Quoted 79 lines · Paul E. McKenney

Quoted 40 lines · Jiri Kosina

Quoted 7 lines · Paul E. McKenney

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events. I could go back to the old approach, but it is significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

Quoted 6 lines

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

Sorry, I don't think I understand what you are proposing just yet.

If I understand it correctly, you are proposing to introduce some magic into _rcu_barrier() such as (pseudocode of course):

if (!being_called_from_hotplug_notifier_callback)
get_online_cpus()

How does that protect from the scenario I've outlined before though?

	CPU 0                           CPU 1
	kmem_cache_destroy()
	mutex_lock(slab_mutex)
					_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)	

Quoted 5 lines

CPU 0 grabs both locks anyway (it's not running from notifier callback). CPU 1 grabs both locks as well, as there is no _rcu_barrier() being called from notifier callback either.

What did I miss?

You didn't miss anything, I was suffering a failure to read carefully.

So my next stupid question is "Why can't kmem_cache_destroy drop slab_mutex early?" like the following:

	void kmem_cache_destroy(struct kmem_cache *cachep)
	{
		BUG_ON(!cachep || in_interrupt());

		/* Find the cache in the chain of caches. */
		get_online_cpus();
		mutex_lock(&slab_mutex);
		/*
		 * the chain is never empty, cache_cache is never destroyed
		 */
		list_del(&cachep->list);
		if (__cache_shrink(cachep)) {
			slab_error(cachep, "Can't free all objects");
			list_add(&cachep->list, &slab_caches);
			mutex_unlock(&slab_mutex);
			put_online_cpus();
			return;
		}
		mutex_unlock(&slab_mutex);

		if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
			rcu_barrier();

		__kmem_cache_destroy(cachep);
		put_online_cpus();
	}

Quoted 2 lines

Or did I miss some reason why __kmem_cache_destroy() needs that lock? Looks to me like it is just freeing now-disconnected memory.

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

It makes the lockdep happy again, and obviously removes the deadlock (I tested it).

From: Jiri Kosina <[email protected]>
Subject: mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

This opens a possibilty for deadlock:

        CPU 0                           CPU 1
	        kmem_cache_destroy()
	        mutex_lock(slab_mutex)
	                                        _cpu_up()
	                                        cpu_hotplug_begin()
	                                        mutex_lock(cpu_hotplug.lock)
	        rcu_barrier()
	        _rcu_barrier()
	        get_online_cpus()
	        mutex_lock(cpu_hotplug.lock)
	         (blocks, CPU 1 has the mutex)
	                                        __cpu_notify()
	                                        mutex_lock(slab_mutex)

It turns out that slab's kmem_cache_destroy() might release slab_mutex earlier before calling out to rcu_barrier(), as cachep has already been unlinked.

This patch removes the AB-BA dependency by calling rcu_barrier() with slab_mutex already unlocked.

Signed-off-by Jiri Kosina <[email protected]>

---
 mm/slab.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

mm/slab.c +1 -1

index 1133911..693c7cb 100644
@@ -2801,12 +2801,12 @@ void kmem_cache_destroy(struct kmem_cache *cachep)
 		put_online_cpus();
 		return;
 	}
+	mutex_unlock(&slab_mutex);
 
 	if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
 		rcu_barrier();
 
 	__kmem_cache_destroy(cachep);
-	mutex_unlock(&slab_mutex);
 	put_online_cpus();
 }
 EXPORT_SYMBOL(kmem_cache_destroy);

Quoted 106 lines · Jiri Kosina

Quoted 79 lines · Paul E. McKenney

Quoted 40 lines · Jiri Kosina

Quoted 7 lines · Paul E. McKenney

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events. I could go back to the old approach, but it is significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

Quoted 6 lines

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

Sorry, I don't think I understand what you are proposing just yet.

If I understand it correctly, you are proposing to introduce some magic into _rcu_barrier() such as (pseudocode of course):

if (!being_called_from_hotplug_notifier_callback)
get_online_cpus()

How does that protect from the scenario I've outlined before though?

	CPU 0                           CPU 1
	kmem_cache_destroy()
	mutex_lock(slab_mutex)
					_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)	

Quoted 5 lines

CPU 0 grabs both locks anyway (it's not running from notifier callback). CPU 1 grabs both locks as well, as there is no _rcu_barrier() being called from notifier callback either.

What did I miss?

You didn't miss anything, I was suffering a failure to read carefully.

So my next stupid question is "Why can't kmem_cache_destroy drop slab_mutex early?" like the following:

	void kmem_cache_destroy(struct kmem_cache *cachep)
	{
		BUG_ON(!cachep || in_interrupt());

		/* Find the cache in the chain of caches. */
		get_online_cpus();
		mutex_lock(&slab_mutex);
		/*
		 * the chain is never empty, cache_cache is never destroyed
		 */
		list_del(&cachep->list);
		if (__cache_shrink(cachep)) {
			slab_error(cachep, "Can't free all objects");
			list_add(&cachep->list, &slab_caches);
			mutex_unlock(&slab_mutex);
			put_online_cpus();
			return;
		}
		mutex_unlock(&slab_mutex);

		if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
			rcu_barrier();

		__kmem_cache_destroy(cachep);
		put_online_cpus();
	}

Quoted 2 lines

Or did I miss some reason why __kmem_cache_destroy() needs that lock? Looks to me like it is just freeing now-disconnected memory.

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

It makes the lockdep happy again, and obviously removes the deadlock (I tested it).

From: Jiri Kosina <[email protected]>
Subject: mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

This opens a possibilty for deadlock:

Quoted 13 lines

        CPU 0                           CPU 1
	        kmem_cache_destroy()
	        mutex_lock(slab_mutex)
	                                        _cpu_up()
	                                        cpu_hotplug_begin()
	                                        mutex_lock(cpu_hotplug.lock)
	        rcu_barrier()
	        _rcu_barrier()
	        get_online_cpus()
	        mutex_lock(cpu_hotplug.lock)
	         (blocks, CPU 1 has the mutex)
	                                        __cpu_notify()
	                                        mutex_lock(slab_mutex)

Hmm.. no, this should *never* happen IMHO!

If I am seeing the code right, kmem_cache_destroy() wraps its entire content inside get/put_online_cpus(), which means it cannot run concurrently with cpu_up() or cpu_down(). Are we really hitting a corner case where the refcounting logic in get/put_online_cpus() is failing and allowing a hotplug writer to run in parallel with a hotplug reader? If yes, *that* is the problem we have to fix..

Quoted 121 lines · Srivatsa S. Bhat

Quoted 106 lines · Jiri Kosina

Quoted 79 lines · Paul E. McKenney

Quoted 40 lines · Jiri Kosina

Quoted 7 lines · Paul E. McKenney

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events. I could go back to the old approach, but it is significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

Quoted 6 lines

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

Sorry, I don't think I understand what you are proposing just yet.

If I understand it correctly, you are proposing to introduce some magic into _rcu_barrier() such as (pseudocode of course):

if (!being_called_from_hotplug_notifier_callback)
get_online_cpus()

How does that protect from the scenario I've outlined before though?

	CPU 0                           CPU 1
	kmem_cache_destroy()
	mutex_lock(slab_mutex)
					_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)	

Quoted 5 lines

CPU 0 grabs both locks anyway (it's not running from notifier callback). CPU 1 grabs both locks as well, as there is no _rcu_barrier() being called from notifier callback either.

What did I miss?

You didn't miss anything, I was suffering a failure to read carefully.

So my next stupid question is "Why can't kmem_cache_destroy drop slab_mutex early?" like the following:

	void kmem_cache_destroy(struct kmem_cache *cachep)
	{
		BUG_ON(!cachep || in_interrupt());

		/* Find the cache in the chain of caches. */
		get_online_cpus();
		mutex_lock(&slab_mutex);
		/*
		 * the chain is never empty, cache_cache is never destroyed
		 */
		list_del(&cachep->list);
		if (__cache_shrink(cachep)) {
			slab_error(cachep, "Can't free all objects");
			list_add(&cachep->list, &slab_caches);
			mutex_unlock(&slab_mutex);
			put_online_cpus();
			return;
		}
		mutex_unlock(&slab_mutex);

		if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
			rcu_barrier();

		__kmem_cache_destroy(cachep);
		put_online_cpus();
	}

Quoted 2 lines

Or did I miss some reason why __kmem_cache_destroy() needs that lock? Looks to me like it is just freeing now-disconnected memory.

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

It makes the lockdep happy again, and obviously removes the deadlock (I tested it).

From: Jiri Kosina <[email protected]>
Subject: mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

This opens a possibilty for deadlock:

Quoted 13 lines

        CPU 0                           CPU 1
	        kmem_cache_destroy()
	        mutex_lock(slab_mutex)
	                                        _cpu_up()
	                                        cpu_hotplug_begin()
	                                        mutex_lock(cpu_hotplug.lock)
	        rcu_barrier()
	        _rcu_barrier()
	        get_online_cpus()
	        mutex_lock(cpu_hotplug.lock)
	         (blocks, CPU 1 has the mutex)
	                                        __cpu_notify()
	                                        mutex_lock(slab_mutex)

Quoted 8 lines

Hmm.. no, this should *never* happen IMHO!

If I am seeing the code right, kmem_cache_destroy() wraps its entire content inside get/put_online_cpus(), which means it cannot run concurrently with cpu_up() or cpu_down(). Are we really hitting a corner case where the refcounting logic in get/put_online_cpus() is failing and allowing a hotplug writer to run in parallel with a hotplug reader? If yes, *that* is the problem we have to fix..

One scenario where we can see this happen is if we had a put_online_cpus() "leak" somewhere.. that is, perhaps the task that was about to invoke kmem_cache_destroy() previously called put_online_cpus() once too many. In that case, the get_online_cpus() in kmem_cache_destroy() might prove useless in excluding it from concurrent hotplug operations.

Jiri, can you please try the debug patch below? It would be good to see if the refcount ever went negative...

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

Quoted 6 lines · Jiri Kosina

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

It turns out that lockdep is actually getting this wrong, so the changelog in the previous version wasn't accurate.

Please find patch with updated changelog below. Pekka, Christoph, could you please check whether it makes sense to you as well? Thanks.

From: Jiri Kosina <[email protected]>
Subject: [PATCH] mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

Lockdep thinks that this might actually result in ABBA deadlock, and reports it as below:

=== [ cut here ] ===
======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc5-00004-g0d8ee37 #143 Not tainted
-------------------------------------------------------
kworker/u:2/40 is trying to acquire lock:
(rcu_sched_state.barrier_mutex){+.+...}, at: [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0

but task is already holding lock:
(slab_mutex){+.+.+.}, at: [<ffffffff81176e15>] kmem_cache_destroy+0x45/0xe0

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #2 (slab_mutex){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81558cb5>] cpuup_callback+0x2f/0xbe
        [<ffffffff81564b83>] notifier_call_chain+0x93/0x140
        [<ffffffff81076f89>] __raw_notifier_call_chain+0x9/0x10
        [<ffffffff8155719d>] _cpu_up+0xba/0x14e
        [<ffffffff815572ed>] cpu_up+0xbc/0x117
        [<ffffffff81ae05e3>] smp_init+0x6b/0x9f
        [<ffffffff81ac47d6>] kernel_init+0x147/0x1dc
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

-> #1 (cpu_hotplug.lock){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81049197>] get_online_cpus+0x37/0x50
        [<ffffffff810f21bb>] _rcu_barrier+0xbb/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff8118c129>] deactivate_locked_super+0x49/0x90
        [<ffffffff8118cc01>] deactivate_super+0x61/0x70
        [<ffffffff811aaaa7>] mntput_no_expire+0x127/0x180
        [<ffffffff811ab49e>] sys_umount+0x6e/0xd0
        [<ffffffff81569979>] system_call_fastpath+0x16/0x1b

-> #0 (rcu_sched_state.barrier_mutex){+.+...}:

        [<ffffffff810adb4e>] check_prev_add+0x3de/0x440
        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff81176ea1>] kmem_cache_destroy+0xd1/0xe0
        [<ffffffffa04c3154>] nf_conntrack_cleanup_net+0xe4/0x110 [nf_conntrack]
        [<ffffffffa04c31aa>] nf_conntrack_cleanup+0x2a/0x70 [nf_conntrack]
        [<ffffffffa04c42ce>] nf_conntrack_net_exit+0x5e/0x80 [nf_conntrack]
        [<ffffffff81454b79>] ops_exit_list+0x39/0x60
        [<ffffffff814551ab>] cleanup_net+0xfb/0x1b0
        [<ffffffff8106917b>] process_one_work+0x26b/0x4c0
        [<ffffffff81069f3e>] worker_thread+0x12e/0x320
        [<ffffffff8106f73e>] kthread+0x9e/0xb0
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

other info that might help us debug this:

 Chain exists of:
   rcu_sched_state.barrier_mutex --> cpu_hotplug.lock --> slab_mutex

  Possible unsafe locking scenario:

        CPU0                    CPU1
        ----                    ----
   lock(slab_mutex);
                                lock(cpu_hotplug.lock);
                                lock(slab_mutex);

lock(rcu_sched_state.barrier_mutex);

*** DEADLOCK ***
=== [ cut here ] ===

This is actually a false positive. Lockdep has no way of knowing the fact that the ABBA can actually never happen, because of special semantics of cpu_hotplug.refcount and itss handling in cpu_hotplug_begin(); the mutual exclusion there is not achieved through mutex, but through cpu_hotplug.refcount.

The "neither cpu_up() nor cpu_down() will proceed past cpu_hotplug_begin() until everyone who called get_online_cpus() will call put_online_cpus()" semantics is totally invisible to lockdep.

This patch therefore moves the unlock of slab_mutex so that rcu_barrier() is being called with it unlocked. It has two advantages:

- it slightly reduces hold time of slab_mutex; as it's used to protect the cachep list, it's not necessary to hold it over __kmem_cache_destroy() call any more
- it silences the lockdep false positive warning, as it avoids lockdep ever learning about slab_mutex -> cpu_hotplug.lock dependency

Reviewed-by Paul E. McKenney <[email protected]>

Signed-off-by Jiri Kosina <[email protected]>

---
 mm/slab.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

mm/slab.c +0 -0

index 1133911..693c7cb 100644
@@ -2801,12 +2801,12 @@ void kmem_cache_destroy(struct kmem_cache *cachep)
 		put_online_cpus();
 		return;
 	}

Quoted 7 lines · Jiri Kosina

Quoted 5 lines · Jiri Kosina

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

But, I'm also quite surprised that the put_online_cpus() code as it stands today doesn't have any checks for the refcount going negative. I believe that such a check would be valuable to help catch cases where we might end up inadvertently causing an imbalance between get_online_cpus() and put_online_cpus(). I'll post that as a separate patch.

The synchronization between CPU hotplug readers and writers is achieved by means of refcounting, safe-guarded by the cpu_hotplug.lock.

get_online_cpus() increments the refcount, whereas put_online_cpus() decrements it. If we ever hit an imbalance between the two, we end up compromising the guarantees of the hotplug synchronization i.e, for example, an extra call to put_online_cpus() can end up allowing a hotplug reader to execute concurrently with a hotplug writer. So, add a BUG_ON() in put_online_cpus() to detect such cases where the refcount can go negative.

Signed-off-by Srivatsa S. Bhat <[email protected]>

---

 kernel/cpu.c |    1 +
 1 file changed, 1 insertion(+)

kernel/cpu.c +0 -0

index f560598..00d29bc 100644

Quoted 21 lines · On Wed, 03 Oct 2012 18:23:09 +0530 "Srivatsa S. Bhat"…

The synchronization between CPU hotplug readers and writers is achieved by means of refcounting, safe-guarded by the cpu_hotplug.lock.

get_online_cpus() increments the refcount, whereas put_online_cpus() decrements it. If we ever hit an imbalance between the two, we end up compromising the guarantees of the hotplug synchronization i.e, for example, an extra call to put_online_cpus() can end up allowing a hotplug reader to execute concurrently with a hotplug writer. So, add a BUG_ON() in put_online_cpus() to detect such cases where the refcount can go negative.

Signed-off-by Srivatsa S. Bhat <[email protected]>

---

 kernel/cpu.c |    1 +
 1 file changed, 1 insertion(+)

kernel/cpu.c +0 -0

index f560598..00d29bc 100644

kernel/cpu.c void put_online_cpus(void) · line 86

Quoted 7 lines

kernel/cpu.c +1 -0

@@ -80,6 +80,7 @@ void put_online_cpus(void)
 	if (cpu_hotplug.active_writer == current)
 		return;
 	mutex_lock(&cpu_hotplug.lock);
+	BUG_ON(cpu_hotplug.refcount == 0);
 	if (!--cpu_hotplug.refcount && unlikely(cpu_hotplug.active_writer))
 		wake_up_process(cpu_hotplug.active_writer);
 	mutex_unlock(&cpu_hotplug.lock);

I think calling BUG() here is a bit harsh. We should only do that if there's a risk to proceeding: a risk of data loss, a reduced ability to analyse the underlying bug, etc.

But a cpu-hotplug locking imbalance is a really really really minor problem! So how about we emit a warning then try to fix things up?

This should increase the chance that the machine will keep running and so will increase the chance that a user will be able to report the bug to us.

Quoted 36 lines · Andrew Morton

Quoted 21 lines · On Wed, 03 Oct 2012 18:23:09 +0530 "Srivatsa S. Bhat"…

The synchronization between CPU hotplug readers and writers is achieved by means of refcounting, safe-guarded by the cpu_hotplug.lock.

get_online_cpus() increments the refcount, whereas put_online_cpus() decrements it. If we ever hit an imbalance between the two, we end up compromising the guarantees of the hotplug synchronization i.e, for example, an extra call to put_online_cpus() can end up allowing a hotplug reader to execute concurrently with a hotplug writer. So, add a BUG_ON() in put_online_cpus() to detect such cases where the refcount can go negative.

Signed-off-by Srivatsa S. Bhat <[email protected]>

---

  kernel/cpu.c |    1 +
  1 file changed, 1 insertion(+)

kernel/cpu.c +0 -0

index f560598..00d29bc 100644

kernel/cpu.c void put_online_cpus(void) · line 86

Quoted 7 lines

kernel/cpu.c +1 -0

@@ -80,6 +80,7 @@ void put_online_cpus(void)
  	if (cpu_hotplug.active_writer == current)
  		return;
  	mutex_lock(&cpu_hotplug.lock);
+	BUG_ON(cpu_hotplug.refcount == 0);
  	if (!--cpu_hotplug.refcount && unlikely(cpu_hotplug.active_writer))
  		wake_up_process(cpu_hotplug.active_writer);
  	mutex_unlock(&cpu_hotplug.lock);

I think calling BUG() here is a bit harsh. We should only do that if there's a risk to proceeding: a risk of data loss, a reduced ability to analyse the underlying bug, etc.

Quoted 2 lines

But a cpu-hotplug locking imbalance is a really really really minor problem! So how about we emit a warning then try to fix things up?

That would be better indeed, thanks!

Quoted 4 lines

This should increase the chance that the machine will keep running and so will increase the chance that a user will be able to report the bug to us.

Yep, sounds good.

kernel/cpu.c void put_online_cpus(void) · line 83

Quoted 11 lines

kernel/cpu.c renamed from kernel/cpu.c~cpu-hotplug-debug-detect-imbalance-between-get_online_cpus-and-put_online_cpus-fix +1 -3

@@ -80,9 +80,12 @@ void put_online_cpus(void)
  	if (cpu_hotplug.active_writer == current)
  		return;
  	mutex_lock(&cpu_hotplug.lock);
-	BUG_ON(cpu_hotplug.refcount == 0);
-	if (!--cpu_hotplug.refcount && unlikely(cpu_hotplug.active_writer))
-		wake_up_process(cpu_hotplug.active_writer);
+	if (!--cpu_hotplug.refcount) {

This won't catch it. We'll enter this 'if' condition only when cpu_hotplug.refcount was decremented to zero. We'll miss out the case when it went negative (which we intended to detect).

kernel/cpu.c void put_online_cpus(void) · line 91

Quoted 8 lines

kernel/cpu.c renamed from kernel/cpu.c~cpu-hotplug-debug-detect-imbalance-between-get_online_cpus-and-put_online_cpus-fix +5 -0

+		if (WARN_ON(cpu_hotplug.refcount == -1))
+			cpu_hotplug.refcount++;	/* try to fix things up */
+		if (unlikely(cpu_hotplug.active_writer))
+			wake_up_process(cpu_hotplug.active_writer);
+	}
  	mutex_unlock(&cpu_hotplug.lock);
 
  }

So how about something like below:

------------------------------------------------------>

From: Srivatsa S. Bhat <[email protected]>
Subject: [PATCH] CPU hotplug, debug: Detect imbalance between get_online_cpus() and put_online_cpus()

The synchronization between CPU hotplug readers and writers is achieved by means of refcounting, safe-guarded by the cpu_hotplug.lock.

get_online_cpus() increments the refcount, whereas put_online_cpus() decrements it. If we ever hit an imbalance between the two, we end up compromising the guarantees of the hotplug synchronization i.e, for example, an extra call to put_online_cpus() can end up allowing a hotplug reader to execute concurrently with a hotplug writer. So, add a WARN_ON() in put_online_cpus() to detect such cases where the refcount can go negative, and also attempt to fix it up, so that we can continue to run.

Signed-off-by Srivatsa S. Bhat <[email protected]>

---

  kernel/cpu.c |    4 ++++
  1 file changed, 4 insertions(+)

kernel/cpu.c +4 -1

index f560598..42bd331 100644
@@ -80,6 +80,10 @@ void put_online_cpus(void)
  	if (cpu_hotplug.active_writer == current)
  		return;
  	mutex_lock(&cpu_hotplug.lock);
+
+	if (WARN_ON(!cpu_hotplug.refcount))
+		cpu_hotplug.refcount++; /* try to fix things up */
+
  	if (!--cpu_hotplug.refcount && unlikely(cpu_hotplug.active_writer))
  		wake_up_process(cpu_hotplug.active_writer);
  	mutex_unlock(&cpu_hotplug.lock);
 
 
--

To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Quoted 110 lines · Srivatsa S. Bhat

Quoted 43 lines · Andrew Morton

Quoted 34 lines · On Wed, 03 Oct 2012 18:23:09 +0530 "Srivatsa S. Bhat"…

The synchronization between CPU hotplug readers and writers is achieved by
means of refcounting, safe-guarded by the cpu_hotplug.lock.

get_online_cpus() increments the refcount, whereas put_online_cpus() decrements
it. If we ever hit an imbalance between the two, we end up compromising the
guarantees of the hotplug synchronization i.e, for example, an extra call to
put_online_cpus() can end up allowing a hotplug reader to execute concurrently with
a hotplug writer. So, add a BUG_ON() in put_online_cpus() to detect such cases
where the refcount can go negative.

Signed-off-by Srivatsa S. Bhat <[email protected]>

---

  kernel/cpu.c |    1 +
  1 file changed, 1 insertion(+)

kernel/cpu.c +1 -0

index f560598..00d29bc 100644
@@ -80,6 +80,7 @@ void put_online_cpus(void)
      if (cpu_hotplug.active_writer == current)
          return;
      mutex_lock(&cpu_hotplug.lock);
+    BUG_ON(cpu_hotplug.refcount == 0);
      if (!--cpu_hotplug.refcount &&
 unlikely(cpu_hotplug.active_writer))
          wake_up_process(cpu_hotplug.active_writer);

Quoted 1 line

      mutex_unlock(&cpu_hotplug.lock);

I think calling BUG() here is a bit harsh. We should only do that if there's a risk to proceeding: a risk of data loss, a reduced ability to analyse the underlying bug, etc.

Quoted 2 lines

But a cpu-hotplug locking imbalance is a really really really minor problem! So how about we emit a warning then try to fix things up?

That would be better indeed, thanks!

Quoted 4 lines

This should increase the chance that the machine will keep running and so will increase the chance that a user will be able to report the bug to us.

Yep, sounds good.

Review void put_online_cpus(void) · line 83

Quoted 13 lines

---
a/kernel/cpu.c~cpu-hotplug-debug-detect-imbalance-between-get_online_cpus-and-put_online_cpus-fix

+++ a/kernel/cpu.c

(quoted diff) +1 -3

@@ -80,9 +80,12 @@ void put_online_cpus(void)
      if (cpu_hotplug.active_writer == current)
          return;
      mutex_lock(&cpu_hotplug.lock);
-    BUG_ON(cpu_hotplug.refcount == 0);
-    if (!--cpu_hotplug.refcount && unlikely(cpu_hotplug.active_writer))
-        wake_up_process(cpu_hotplug.active_writer);
+    if (!--cpu_hotplug.refcount) {

This won't catch it. We'll enter this 'if' condition only when cpu_hotplug.refcount was
decremented to zero. We'll miss out the case when it went negative (which we intended to detect).

Review void put_online_cpus(void) · line 91

Quoted 8 lines

(quoted diff) +5 -0

+        if (WARN_ON(cpu_hotplug.refcount == -1))
+            cpu_hotplug.refcount++;    /* try to fix things up */
+        if (unlikely(cpu_hotplug.active_writer))
+            wake_up_process(cpu_hotplug.active_writer);
+    }
      mutex_unlock(&cpu_hotplug.lock);
 
  }

So how about something like below:

------------------------------------------------------>

From: Srivatsa S. Bhat <[email protected]>
Subject: [PATCH] CPU hotplug, debug: Detect imbalance between get_online_cpus() and put_online_cpus()

The synchronization between CPU hotplug readers and writers is achieved by
means of refcounting, safe-guarded by the cpu_hotplug.lock.

get_online_cpus() increments the refcount, whereas put_online_cpus() decrements
it. If we ever hit an imbalance between the two, we end up compromising the
guarantees of the hotplug synchronization i.e, for example, an extra call to
put_online_cpus() can end up allowing a hotplug reader to execute concurrently with
a hotplug writer. So, add a WARN_ON() in put_online_cpus() to detect such cases
where the refcount can go negative, and also attempt to fix it up, so that we can
continue to run.

Quoted 2 lines

Signed-off-by Srivatsa S. Bhat <[email protected]>

---

Looks good to me.

Reviewed-by Yasuaki Ishimatsu <[email protected]>

Quoted 13 lines

  kernel/cpu.c |    4 ++++
  1 file changed, 4 insertions(+)

kernel/cpu.c +1 -0

index f560598..42bd331 100644
@@ -80,6 +80,10 @@ void put_online_cpus(void)
      if (cpu_hotplug.active_writer == current)
          return;
      mutex_lock(&cpu_hotplug.lock);
+

kernel/cpu.c void put_online_cpus(void) · line 89

Quoted 8 lines

kernel/cpu.c +3 -0

+    if (WARN_ON(!cpu_hotplug.refcount))
+        cpu_hotplug.refcount++; /* try to fix things up */
+
      if (!--cpu_hotplug.refcount && unlikely(cpu_hotplug.active_writer))
          wake_up_process(cpu_hotplug.active_writer);
      mutex_unlock(&cpu_hotplug.lock);

Quoted 126 lines · Jiri Kosina

Quoted 6 lines · Jiri Kosina

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

It turns out that lockdep is actually getting this wrong, so the changelog in the previous version wasn't accurate.

Please find patch with updated changelog below. Pekka, Christoph, could you please check whether it makes sense to you as well? Thanks.

From: Jiri Kosina <[email protected]>
Subject: [PATCH] mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

Lockdep thinks that this might actually result in ABBA deadlock, and reports it as below:

=== [ cut here ] ===
======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc5-00004-g0d8ee37 #143 Not tainted
-------------------------------------------------------
kworker/u:2/40 is trying to acquire lock:
(rcu_sched_state.barrier_mutex){+.+...}, at: [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0

but task is already holding lock:
(slab_mutex){+.+.+.}, at: [<ffffffff81176e15>] kmem_cache_destroy+0x45/0xe0

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #2 (slab_mutex){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81558cb5>] cpuup_callback+0x2f/0xbe
        [<ffffffff81564b83>] notifier_call_chain+0x93/0x140
        [<ffffffff81076f89>] __raw_notifier_call_chain+0x9/0x10
        [<ffffffff8155719d>] _cpu_up+0xba/0x14e
        [<ffffffff815572ed>] cpu_up+0xbc/0x117
        [<ffffffff81ae05e3>] smp_init+0x6b/0x9f
        [<ffffffff81ac47d6>] kernel_init+0x147/0x1dc
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

-> #1 (cpu_hotplug.lock){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81049197>] get_online_cpus+0x37/0x50
        [<ffffffff810f21bb>] _rcu_barrier+0xbb/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff8118c129>] deactivate_locked_super+0x49/0x90
        [<ffffffff8118cc01>] deactivate_super+0x61/0x70
        [<ffffffff811aaaa7>] mntput_no_expire+0x127/0x180
        [<ffffffff811ab49e>] sys_umount+0x6e/0xd0
        [<ffffffff81569979>] system_call_fastpath+0x16/0x1b

-> #0 (rcu_sched_state.barrier_mutex){+.+...}:

        [<ffffffff810adb4e>] check_prev_add+0x3de/0x440
        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff81176ea1>] kmem_cache_destroy+0xd1/0xe0
        [<ffffffffa04c3154>] nf_conntrack_cleanup_net+0xe4/0x110 [nf_conntrack]
        [<ffffffffa04c31aa>] nf_conntrack_cleanup+0x2a/0x70 [nf_conntrack]
        [<ffffffffa04c42ce>] nf_conntrack_net_exit+0x5e/0x80 [nf_conntrack]
        [<ffffffff81454b79>] ops_exit_list+0x39/0x60
        [<ffffffff814551ab>] cleanup_net+0xfb/0x1b0
        [<ffffffff8106917b>] process_one_work+0x26b/0x4c0
        [<ffffffff81069f3e>] worker_thread+0x12e/0x320
        [<ffffffff8106f73e>] kthread+0x9e/0xb0
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

other info that might help us debug this:

 Chain exists of:
   rcu_sched_state.barrier_mutex --> cpu_hotplug.lock --> slab_mutex

  Possible unsafe locking scenario:

        CPU0                    CPU1
        ----                    ----
   lock(slab_mutex);
                                lock(cpu_hotplug.lock);
                                lock(slab_mutex);

lock(rcu_sched_state.barrier_mutex);

*** DEADLOCK ***
=== [ cut here ] ===

This is actually a false positive. Lockdep has no way of knowing the fact that the ABBA can actually never happen, because of special semantics of cpu_hotplug.refcount and itss handling in cpu_hotplug_begin(); the mutual exclusion there is not achieved through mutex, but through cpu_hotplug.refcount.

The "neither cpu_up() nor cpu_down() will proceed past cpu_hotplug_begin() until everyone who called get_online_cpus() will call put_online_cpus()" semantics is totally invisible to lockdep.

This patch therefore moves the unlock of slab_mutex so that rcu_barrier() is being called with it unlocked. It has two advantages:

Quoted 8 lines

- it slightly reduces hold time of slab_mutex; as it's used to protect the cachep list, it's not necessary to hold it over __kmem_cache_destroy() call any more
- it silences the lockdep false positive warning, as it avoids lockdep ever learning about slab_mutex -> cpu_hotplug.lock dependency

Reviewed-by Paul E. McKenney <[email protected]>

Signed-off-by Jiri Kosina <[email protected]>

Reviewed-by Srivatsa S. Bhat <[email protected]>

Earlier I was under the wrong impression that all the calltraces that lockdep spewed were reflecting the same point in time. So, sorry about that noise! :-) It is indeed a false-positive and there is no real bug here, and the fix looks good, provided __kmem_cache_destroy() doesn't expect slab_mutex to be held.

But, I'm also quite surprised that the put_online_cpus() code as it stands today doesn't have any checks for the refcount going negative. I believe that such a check would be valuable to help catch cases where we might end up inadvertently causing an imbalance between get_online_cpus() and put_online_cpus(). I'll post that as a separate patch.

Regards,
Srivatsa S. Bhat

Quoted 23 lines

---
 mm/slab.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

mm/slab.c +1 -1

index 1133911..693c7cb 100644
@@ -2801,12 +2801,12 @@ void kmem_cache_destroy(struct kmem_cache *cachep)
 		put_online_cpus();
 		return;
 	}
+	mutex_unlock(&slab_mutex);
 
 	if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
 		rcu_barrier();
 
 	__kmem_cache_destroy(cachep);
-	mutex_unlock(&slab_mutex);
 	put_online_cpus();
 }
 EXPORT_SYMBOL(kmem_cache_destroy);

Quoted 136 lines · Srivatsa S. Bhat

Quoted 126 lines · Jiri Kosina

Quoted 6 lines · Jiri Kosina

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

It turns out that lockdep is actually getting this wrong, so the changelog in the previous version wasn't accurate.

Please find patch with updated changelog below. Pekka, Christoph, could you please check whether it makes sense to you as well? Thanks.

From: Jiri Kosina <[email protected]>
Subject: [PATCH] mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

Lockdep thinks that this might actually result in ABBA deadlock, and reports it as below:

=== [ cut here ] ===
======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc5-00004-g0d8ee37 #143 Not tainted
-------------------------------------------------------
kworker/u:2/40 is trying to acquire lock:
(rcu_sched_state.barrier_mutex){+.+...}, at: [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0

but task is already holding lock:
(slab_mutex){+.+.+.}, at: [<ffffffff81176e15>] kmem_cache_destroy+0x45/0xe0

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #2 (slab_mutex){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81558cb5>] cpuup_callback+0x2f/0xbe
        [<ffffffff81564b83>] notifier_call_chain+0x93/0x140
        [<ffffffff81076f89>] __raw_notifier_call_chain+0x9/0x10
        [<ffffffff8155719d>] _cpu_up+0xba/0x14e
        [<ffffffff815572ed>] cpu_up+0xbc/0x117
        [<ffffffff81ae05e3>] smp_init+0x6b/0x9f
        [<ffffffff81ac47d6>] kernel_init+0x147/0x1dc
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

-> #1 (cpu_hotplug.lock){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81049197>] get_online_cpus+0x37/0x50
        [<ffffffff810f21bb>] _rcu_barrier+0xbb/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff8118c129>] deactivate_locked_super+0x49/0x90
        [<ffffffff8118cc01>] deactivate_super+0x61/0x70
        [<ffffffff811aaaa7>] mntput_no_expire+0x127/0x180
        [<ffffffff811ab49e>] sys_umount+0x6e/0xd0
        [<ffffffff81569979>] system_call_fastpath+0x16/0x1b

-> #0 (rcu_sched_state.barrier_mutex){+.+...}:

        [<ffffffff810adb4e>] check_prev_add+0x3de/0x440
        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff81176ea1>] kmem_cache_destroy+0xd1/0xe0
        [<ffffffffa04c3154>] nf_conntrack_cleanup_net+0xe4/0x110 [nf_conntrack]
        [<ffffffffa04c31aa>] nf_conntrack_cleanup+0x2a/0x70 [nf_conntrack]
        [<ffffffffa04c42ce>] nf_conntrack_net_exit+0x5e/0x80 [nf_conntrack]
        [<ffffffff81454b79>] ops_exit_list+0x39/0x60
        [<ffffffff814551ab>] cleanup_net+0xfb/0x1b0
        [<ffffffff8106917b>] process_one_work+0x26b/0x4c0
        [<ffffffff81069f3e>] worker_thread+0x12e/0x320
        [<ffffffff8106f73e>] kthread+0x9e/0xb0
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

other info that might help us debug this:

 Chain exists of:
   rcu_sched_state.barrier_mutex --> cpu_hotplug.lock --> slab_mutex

  Possible unsafe locking scenario:

        CPU0                    CPU1
        ----                    ----
   lock(slab_mutex);
                                lock(cpu_hotplug.lock);
                                lock(slab_mutex);

lock(rcu_sched_state.barrier_mutex);

*** DEADLOCK ***
=== [ cut here ] ===

This is actually a false positive. Lockdep has no way of knowing the fact that the ABBA can actually never happen, because of special semantics of cpu_hotplug.refcount and itss handling in cpu_hotplug_begin(); the mutual exclusion there is not achieved through mutex, but through cpu_hotplug.refcount.

The "neither cpu_up() nor cpu_down() will proceed past cpu_hotplug_begin() until everyone who called get_online_cpus() will call put_online_cpus()" semantics is totally invisible to lockdep.

This patch therefore moves the unlock of slab_mutex so that rcu_barrier() is being called with it unlocked. It has two advantages:

Quoted 8 lines

- it slightly reduces hold time of slab_mutex; as it's used to protect the cachep list, it's not necessary to hold it over __kmem_cache_destroy() call any more
- it silences the lockdep false positive warning, as it avoids lockdep ever learning about slab_mutex -> cpu_hotplug.lock dependency

Reviewed-by Paul E. McKenney <[email protected]>

Signed-off-by Jiri Kosina <[email protected]>

Quoted 6 lines

Reviewed-by Srivatsa S. Bhat <[email protected]>

Earlier I was under the wrong impression that all the calltraces that lockdep spewed were reflecting the same point in time. So, sorry about that noise! :-) It is indeed a false-positive and there is no real bug here, and the fix looks good, provided __kmem_cache_destroy() doesn't expect slab_mutex to be held.

I am not so sure about it being a false positive. Consider the following sequence of events:

o Thread A starts a CPU-hotplug operation, acquiring the
hotplug mutex.

o Thread B does a kmem_cache_destroy(), acquiring the slab mutex.

o Thread A reaches the slab CPU-hotplug notifier, but cannot acquire
the slab mutex because Thread B hold it.

o Thread B enters rcu_barrier(), but cannot acquire the hotplug
mutex because Thread A holds it.

So I would argue that lockdep's output was a bit confusing, but that the deadlock it flagged is real. Or am I still missing something?

Quoted 26 lines

But, I'm also quite surprised that the put_online_cpus() code as it stands today doesn't have any checks for the refcount going negative. I believe that such a check would be valuable to help catch cases where we might end up inadvertently causing an imbalance between get_online_cpus() and put_online_cpus(). I'll post that as a separate patch.

Regards,
Srivatsa S. Bhat

Quoted 17 lines

---
 mm/slab.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

mm/slab.c +1 -0

index 1133911..693c7cb 100644
@@ -2801,12 +2801,12 @@ void kmem_cache_destroy(struct kmem_cache *cachep)
 		put_online_cpus();
 		return;
 	}
+	mutex_unlock(&slab_mutex);
 
 	if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
 		rcu_barrier();
 

Quoted 7 lines

mm/slab.c void kmem_cache_destroy(struct kmem_cache *cachep) · line 2812

Quoted 6 lines

mm/slab.c +0 -1

 	__kmem_cache_destroy(cachep);
-	mutex_unlock(&slab_mutex);
 	put_online_cpus();
 }
 EXPORT_SYMBOL(kmem_cache_destroy);

Quoted 147 lines · Paul E. McKenney

Quoted 136 lines · Srivatsa S. Bhat

Quoted 126 lines · Jiri Kosina

Quoted 6 lines · Jiri Kosina

Good question. I believe it should be safe to drop slab_mutex earlier, as cachep has already been unlinked. I am adding slab people and linux-mm to CC (the whole thread on LKML can be found at
https://lkml.org/lkml/2012/10/2/296 for reference).

How about the patch below? Pekka, Christoph, please?

It turns out that lockdep is actually getting this wrong, so the changelog in the previous version wasn't accurate.

Please find patch with updated changelog below. Pekka, Christoph, could you please check whether it makes sense to you as well? Thanks.

From: Jiri Kosina <[email protected]>
Subject: [PATCH] mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

Lockdep thinks that this might actually result in ABBA deadlock, and reports it as below:

=== [ cut here ] ===
======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc5-00004-g0d8ee37 #143 Not tainted
-------------------------------------------------------
kworker/u:2/40 is trying to acquire lock:
(rcu_sched_state.barrier_mutex){+.+...}, at: [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0

but task is already holding lock:
(slab_mutex){+.+.+.}, at: [<ffffffff81176e15>] kmem_cache_destroy+0x45/0xe0

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #2 (slab_mutex){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81558cb5>] cpuup_callback+0x2f/0xbe
        [<ffffffff81564b83>] notifier_call_chain+0x93/0x140
        [<ffffffff81076f89>] __raw_notifier_call_chain+0x9/0x10
        [<ffffffff8155719d>] _cpu_up+0xba/0x14e
        [<ffffffff815572ed>] cpu_up+0xbc/0x117
        [<ffffffff81ae05e3>] smp_init+0x6b/0x9f
        [<ffffffff81ac47d6>] kernel_init+0x147/0x1dc
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

-> #1 (cpu_hotplug.lock){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81049197>] get_online_cpus+0x37/0x50
        [<ffffffff810f21bb>] _rcu_barrier+0xbb/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff8118c129>] deactivate_locked_super+0x49/0x90
        [<ffffffff8118cc01>] deactivate_super+0x61/0x70
        [<ffffffff811aaaa7>] mntput_no_expire+0x127/0x180
        [<ffffffff811ab49e>] sys_umount+0x6e/0xd0
        [<ffffffff81569979>] system_call_fastpath+0x16/0x1b

-> #0 (rcu_sched_state.barrier_mutex){+.+...}:

        [<ffffffff810adb4e>] check_prev_add+0x3de/0x440
        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff81176ea1>] kmem_cache_destroy+0xd1/0xe0
        [<ffffffffa04c3154>] nf_conntrack_cleanup_net+0xe4/0x110 [nf_conntrack]
        [<ffffffffa04c31aa>] nf_conntrack_cleanup+0x2a/0x70 [nf_conntrack]
        [<ffffffffa04c42ce>] nf_conntrack_net_exit+0x5e/0x80 [nf_conntrack]
        [<ffffffff81454b79>] ops_exit_list+0x39/0x60
        [<ffffffff814551ab>] cleanup_net+0xfb/0x1b0
        [<ffffffff8106917b>] process_one_work+0x26b/0x4c0
        [<ffffffff81069f3e>] worker_thread+0x12e/0x320
        [<ffffffff8106f73e>] kthread+0x9e/0xb0
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

other info that might help us debug this:

 Chain exists of:
   rcu_sched_state.barrier_mutex --> cpu_hotplug.lock --> slab_mutex

  Possible unsafe locking scenario:

        CPU0                    CPU1
        ----                    ----
   lock(slab_mutex);
                                lock(cpu_hotplug.lock);
                                lock(slab_mutex);

lock(rcu_sched_state.barrier_mutex);

*** DEADLOCK ***
=== [ cut here ] ===

This is actually a false positive. Lockdep has no way of knowing the fact that the ABBA can actually never happen, because of special semantics of cpu_hotplug.refcount and itss handling in cpu_hotplug_begin(); the mutual exclusion there is not achieved through mutex, but through cpu_hotplug.refcount.

The "neither cpu_up() nor cpu_down() will proceed past cpu_hotplug_begin() until everyone who called get_online_cpus() will call put_online_cpus()" semantics is totally invisible to lockdep.

This patch therefore moves the unlock of slab_mutex so that rcu_barrier() is being called with it unlocked. It has two advantages:

Quoted 8 lines

- it slightly reduces hold time of slab_mutex; as it's used to protect the cachep list, it's not necessary to hold it over __kmem_cache_destroy() call any more
- it silences the lockdep false positive warning, as it avoids lockdep ever learning about slab_mutex -> cpu_hotplug.lock dependency

Reviewed-by Paul E. McKenney <[email protected]>

Signed-off-by Jiri Kosina <[email protected]>

Quoted 6 lines

Reviewed-by Srivatsa S. Bhat <[email protected]>

Earlier I was under the wrong impression that all the calltraces that lockdep spewed were reflecting the same point in time. So, sorry about that noise! :-) It is indeed a false-positive and there is no real bug here, and the fix looks good, provided __kmem_cache_destroy() doesn't expect slab_mutex to be held.

I am not so sure about it being a false positive. Consider the following sequence of events:

Quoted 4 lines

o Thread A starts a CPU-hotplug operation, acquiring the
hotplug mutex.

o Thread B does a kmem_cache_destroy(), acquiring the slab mutex.

This can't happen. Because kmem_cache_destroy() will call get_online_cpus() before trying to acquire slab mutex. And it sleeps waiting at get_online_cpus() because the hotplug lock has already been acquired by Thread A.

Quoted 9 lines

o Thread A reaches the slab CPU-hotplug notifier, but cannot acquire
the slab mutex because Thread B hold it.

o Thread B enters rcu_barrier(), but cannot acquire the hotplug
mutex because Thread A holds it.

So I would argue that lockdep's output was a bit confusing, but that the deadlock it flagged is real. Or am I still missing something?

So the key point is, Thread A is a hotplug writer. Thread B becomes a hotplug reader the moment it calls get_online_cpus(). So they can't co-exist/run together. They will get serialized. That is, Thread A runs to completion, releases hotplug lock. Only then thread B gets past get_online_cpus().

Regards,
Srivatsa S. Bhat

Quoted 33 lines

Quoted 33 lines

But, I'm also quite surprised that the put_online_cpus() code as it stands today doesn't have any checks for the refcount going negative. I believe that such a check would be valuable to help catch cases where we might end up inadvertently causing an imbalance between get_online_cpus() and put_online_cpus(). I'll post that as a separate patch.

Regards,
Srivatsa S. Bhat

Quoted 23 lines

---
 mm/slab.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

mm/slab.c +1 -1

index 1133911..693c7cb 100644
@@ -2801,12 +2801,12 @@ void kmem_cache_destroy(struct kmem_cache *cachep)
 		put_online_cpus();
 		return;
 	}
+	mutex_unlock(&slab_mutex);
 
 	if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
 		rcu_barrier();
 
 	__kmem_cache_destroy(cachep);
-	mutex_unlock(&slab_mutex);
 	put_online_cpus();
 }
 EXPORT_SYMBOL(kmem_cache_destroy);

How about the patch below? Pekka, Christoph, please?

Quoted 1 line

How about the patch below? Pekka, Christoph, please?

Looks fine for -stable. For upstream there is going to be a move to slab_common coming in this merge period. We would need a fix against -next or Pekka's tree too.

Quoted 5 lines · Christoph Lameter

Quoted 1 line

How about the patch below? Pekka, Christoph, please?

Looks fine for -stable. For upstream there is going to be a move to slab_common coming in this merge period. We would need a fix against -next or Pekka's tree too.

Thanks Christoph. Patch against Pekka's slab/for-linus branch below.

I have kept the Acked-by/Reviewed-by from the version of the patch against current Linus' tree, if anyone object, please shout loudly. Ideally should go in during this merge window to keep lockdep happy.

From: Jiri Kosina <[email protected]>
Subject: [PATCH] mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

Lockdep thinks that this might actually result in ABBA deadlock, and reports it as below:

Reviewed-by Srivatsa S. Bhat <[email protected]>

Reviewed-by Paul E. McKenney <[email protected]>

Acked-by Christoph Lameter <[email protected]>

Signed-off-by Jiri Kosina <[email protected]>

---
 mm/slab_common.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)

mm/slab_common.c +0 -0

index 9c21725..90c3053 100644

mm/slab_common.c void kmem_cache_destroy(struct kmem_cache *s) · line 171

Quoted 11 lines

mm/slab_common.c +1 -0

index 9c21725..90c3053 100644
@@ -166,6 +166,7 @@ void kmem_cache_destroy(struct kmem_cache *s)
 	s->refcount--;
 	if (!s->refcount) {
 		list_del(&s->list);
+		mutex_unlock(&slab_mutex);
 
 		if (!__kmem_cache_shutdown(s)) {

__kmem_cache_shutdown() calls __cache_shrink(). And __cache_shrink() has this comment over it:
/* Called with slab_mutex held to protect against cpu hotplug */

So, I guess the question is whether to modify your patch to hold the slab_mutex while calling this function, or to update the comment on top of this function saying that we are OK to call this function (even without slab_mutex) when we are inside a get/put_online_cpus() section.

mm/slab_common.c void kmem_cache_destroy(struct kmem_cache *s) · line 181

Quoted 4 lines

mm/slab_common.c +0 -0

 			if (s->flags & SLAB_DESTROY_BY_RCU)

@@ -179,8 +180,9 @@ void kmem_cache_destroy(struct kmem_cache *s)
 				s->name);
 			dump_stack();

There is a list_add() before this dump_stack(). I assume we need to hold the slab_mutex while calling it.

Quoted 21 lines · Srivatsa S. Bhat

mm/slab_common.c void kmem_cache_destroy(struct kmem_cache *s) · line 171

Quoted 11 lines

mm/slab_common.c +1 -0

index 9c21725..90c3053 100644
@@ -166,6 +166,7 @@ void kmem_cache_destroy(struct kmem_cache *s)
 	s->refcount--;
 	if (!s->refcount) {
 		list_del(&s->list);
+		mutex_unlock(&slab_mutex);
 
 		if (!__kmem_cache_shutdown(s)) {

__kmem_cache_shutdown() calls __cache_shrink(). And __cache_shrink() has this comment over it:
/* Called with slab_mutex held to protect against cpu hotplug */

So, I guess the question is whether to modify your patch to hold the slab_mutex while calling this function, or to update the comment on top of this function saying that we are OK to call this function (even without slab_mutex) when we are inside a get/put_online_cpus() section.

Quoted 7 lines

mm/slab_common.c void kmem_cache_destroy(struct kmem_cache *s) · line 181

Quoted 4 lines

mm/slab_common.c +0 -0

 			if (s->flags & SLAB_DESTROY_BY_RCU)

@@ -179,8 +180,9 @@ void kmem_cache_destroy(struct kmem_cache *s)
 				s->name);
 			dump_stack();

There is a list_add() before this dump_stack(). I assume we need to hold the slab_mutex while calling it.

Gah, of course it is, thanks for spotting this.

From: Jiri Kosina <[email protected]>
Subject: [PATCH] mm, slab: release slab_mutex earlier in kmem_cache_destroy()

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

Lockdep thinks that this might actually result in ABBA deadlock, and reports it as below:

This patch therefore moves the unlock of slab_mutex so that rcu_barrier() is being called with it unlocked. It has two advantages:

- it slightly reduces hold time of slab_mutex; as it's used to protect the cachep list, it's not necessary to hold it over kmem_cache_free() call any more
- it silences the lockdep false positive warning, as it avoids lockdep ever learning about slab_mutex -> cpu_hotplug.lock dependency

Signed-off-by Jiri Kosina <[email protected]>

---
 mm/slab_common.c |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

mm/slab_common.c +2 -0

index 9c21725..069a24e6 100644
@@ -168,6 +168,7 @@ void kmem_cache_destroy(struct kmem_cache *s)
 		list_del(&s->list);
 
 		if (!__kmem_cache_shutdown(s)) {
+			mutex_unlock(&slab_mutex);
 			if (s->flags & SLAB_DESTROY_BY_RCU)
 				rcu_barrier();
 

@@ -175,12 +176,14 @@ void kmem_cache_destroy(struct kmem_cache *s)
 			kmem_cache_free(kmem_cache, s);
 		} else {
 			list_add(&s->list, &slab_caches);
+			mutex_unlock(&slab_mutex);
 			printk(KERN_ERR "kmem_cache_destroy %s: Slab cache still has objects\n",

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

Lockdep thinks that this might actually result in ABBA deadlock, and reports it as below:

=== [ cut here ] ===
======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc5-00004-g0d8ee37 #143 Not tainted
-------------------------------------------------------
kworker/u:2/40 is trying to acquire lock:
(rcu_sched_state.barrier_mutex){+.+...}, at: [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0

but task is already holding lock:
(slab_mutex){+.+.+.}, at: [<ffffffff81176e15>] kmem_cache_destroy+0x45/0xe0

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #2 (slab_mutex){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81558cb5>] cpuup_callback+0x2f/0xbe
        [<ffffffff81564b83>] notifier_call_chain+0x93/0x140
        [<ffffffff81076f89>] __raw_notifier_call_chain+0x9/0x10
        [<ffffffff8155719d>] _cpu_up+0xba/0x14e
        [<ffffffff815572ed>] cpu_up+0xbc/0x117
        [<ffffffff81ae05e3>] smp_init+0x6b/0x9f
        [<ffffffff81ac47d6>] kernel_init+0x147/0x1dc
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

-> #1 (cpu_hotplug.lock){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81049197>] get_online_cpus+0x37/0x50
        [<ffffffff810f21bb>] _rcu_barrier+0xbb/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff8118c129>] deactivate_locked_super+0x49/0x90
        [<ffffffff8118cc01>] deactivate_super+0x61/0x70
        [<ffffffff811aaaa7>] mntput_no_expire+0x127/0x180
        [<ffffffff811ab49e>] sys_umount+0x6e/0xd0
        [<ffffffff81569979>] system_call_fastpath+0x16/0x1b

-> #0 (rcu_sched_state.barrier_mutex){+.+...}:

        [<ffffffff810adb4e>] check_prev_add+0x3de/0x440
        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff81176ea1>] kmem_cache_destroy+0xd1/0xe0
        [<ffffffffa04c3154>] nf_conntrack_cleanup_net+0xe4/0x110 [nf_conntrack]
        [<ffffffffa04c31aa>] nf_conntrack_cleanup+0x2a/0x70 [nf_conntrack]
        [<ffffffffa04c42ce>] nf_conntrack_net_exit+0x5e/0x80 [nf_conntrack]
        [<ffffffff81454b79>] ops_exit_list+0x39/0x60
        [<ffffffff814551ab>] cleanup_net+0xfb/0x1b0
        [<ffffffff8106917b>] process_one_work+0x26b/0x4c0
        [<ffffffff81069f3e>] worker_thread+0x12e/0x320
        [<ffffffff8106f73e>] kthread+0x9e/0xb0
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

other info that might help us debug this:

 Chain exists of:
   rcu_sched_state.barrier_mutex --> cpu_hotplug.lock --> slab_mutex

  Possible unsafe locking scenario:

        CPU0                    CPU1
        ----                    ----
   lock(slab_mutex);
                                lock(cpu_hotplug.lock);
                                lock(slab_mutex);

lock(rcu_sched_state.barrier_mutex);

*** DEADLOCK ***
=== [ cut here ] ===

This is actually a false positive. Lockdep has no way of knowing the fact that the ABBA can actually never happen, because of special semantics of cpu_hotplug.refcount and itss handling in cpu_hotplug_begin(); the mutual exclusion there is not achieved through mutex, but through cpu_hotplug.refcount.

The "neither cpu_up() nor cpu_down() will proceed past cpu_hotplug_begin() until everyone who called get_online_cpus() will call put_online_cpus()" semantics is totally invisible to lockdep.

This patch therefore moves the unlock of slab_mutex so that rcu_barrier() is being called with it unlocked. It has two advantages:

- it slightly reduces hold time of slab_mutex; as it's used to protect the cachep list, it's not necessary to hold it over kmem_cache_free() call any more
- it silences the lockdep false positive warning, as it avoids lockdep ever learning about slab_mutex -> cpu_hotplug.lock dependency

Signed-off-by Jiri Kosina <[email protected]>

Commit 1331e7a1bbe1 ("rcu: Remove _rcu_barrier() dependency on __stop_machine()") introduced slab_mutex -> cpu_hotplug.lock dependency through kmem_cache_destroy() -> rcu_barrier() -> _rcu_barrier() -> get_online_cpus().

Lockdep thinks that this might actually result in ABBA deadlock, and reports it as below:

=== [ cut here ] ===
======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc5-00004-g0d8ee37 #143 Not tainted
-------------------------------------------------------
kworker/u:2/40 is trying to acquire lock:
(rcu_sched_state.barrier_mutex){+.+...}, at: [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0

but task is already holding lock:
(slab_mutex){+.+.+.}, at: [<ffffffff81176e15>] kmem_cache_destroy+0x45/0xe0

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #2 (slab_mutex){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81558cb5>] cpuup_callback+0x2f/0xbe
        [<ffffffff81564b83>] notifier_call_chain+0x93/0x140
        [<ffffffff81076f89>] __raw_notifier_call_chain+0x9/0x10
        [<ffffffff8155719d>] _cpu_up+0xba/0x14e
        [<ffffffff815572ed>] cpu_up+0xbc/0x117
        [<ffffffff81ae05e3>] smp_init+0x6b/0x9f
        [<ffffffff81ac47d6>] kernel_init+0x147/0x1dc
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

-> #1 (cpu_hotplug.lock){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81049197>] get_online_cpus+0x37/0x50
        [<ffffffff810f21bb>] _rcu_barrier+0xbb/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff8118c129>] deactivate_locked_super+0x49/0x90
        [<ffffffff8118cc01>] deactivate_super+0x61/0x70
        [<ffffffff811aaaa7>] mntput_no_expire+0x127/0x180
        [<ffffffff811ab49e>] sys_umount+0x6e/0xd0
        [<ffffffff81569979>] system_call_fastpath+0x16/0x1b

-> #0 (rcu_sched_state.barrier_mutex){+.+...}:

        [<ffffffff810adb4e>] check_prev_add+0x3de/0x440
        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff81176ea1>] kmem_cache_destroy+0xd1/0xe0
        [<ffffffffa04c3154>] nf_conntrack_cleanup_net+0xe4/0x110 [nf_conntrack]
        [<ffffffffa04c31aa>] nf_conntrack_cleanup+0x2a/0x70 [nf_conntrack]
        [<ffffffffa04c42ce>] nf_conntrack_net_exit+0x5e/0x80 [nf_conntrack]
        [<ffffffff81454b79>] ops_exit_list+0x39/0x60
        [<ffffffff814551ab>] cleanup_net+0xfb/0x1b0
        [<ffffffff8106917b>] process_one_work+0x26b/0x4c0
        [<ffffffff81069f3e>] worker_thread+0x12e/0x320
        [<ffffffff8106f73e>] kthread+0x9e/0xb0
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

other info that might help us debug this:

 Chain exists of:
   rcu_sched_state.barrier_mutex --> cpu_hotplug.lock --> slab_mutex

  Possible unsafe locking scenario:

        CPU0                    CPU1
        ----                    ----
   lock(slab_mutex);
                                lock(cpu_hotplug.lock);
                                lock(slab_mutex);

lock(rcu_sched_state.barrier_mutex);

*** DEADLOCK ***
=== [ cut here ] ===

This is actually a false positive. Lockdep has no way of knowing the fact that the ABBA can actually never happen, because of special semantics of cpu_hotplug.refcount and its handling in cpu_hotplug_begin(); the mutual exclusion there is not achieved through mutex, but through cpu_hotplug.refcount.

The "neither cpu_up() nor cpu_down() will proceed past cpu_hotplug_begin() until everyone who called get_online_cpus() will call put_online_cpus()" semantics is totally invisible to lockdep.

This patch therefore moves the unlock of slab_mutex so that rcu_barrier() is being called with it unlocked. It has two advantages:

- it slightly reduces hold time of slab_mutex; as it's used to protect the cachep list, it's not necessary to hold it over kmem_cache_free() call any more
- it silences the lockdep false positive warning, as it avoids lockdep ever learning about slab_mutex -> cpu_hotplug.lock dependency

Reviewed-by Paul E. McKenney <[email protected]>

Reviewed-by Srivatsa S. Bhat <[email protected]>

Acked-by David Rientjes <[email protected]>

Signed-off-by Jiri Kosina <[email protected]>

---
 mm/slab_common.c |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

mm/slab_common.c +2 -0

index 9c21725..069a24e6 100644
@@ -168,6 +168,7 @@ void kmem_cache_destroy(struct kmem_cache *s)
                list_del(&s->list);
 
                if (!__kmem_cache_shutdown(s)) {
+                       mutex_unlock(&slab_mutex);
                        if (s->flags & SLAB_DESTROY_BY_RCU)
                                rcu_barrier();
 

@@ -175,12 +176,14 @@ void kmem_cache_destroy(struct kmem_cache *s)
                        kmem_cache_free(kmem_cache, s);
                } else {
                        list_add(&s->list, &slab_caches);
+                       mutex_unlock(&slab_mutex);
                        printk(KERN_ERR "kmem_cache_destroy %s: Slab cache still has objects\n",

Quoted 38 lines · Jiri Kosina

Quoted 36 lines · Jiri Kosina

Quoted 36 lines

Quoted 22 lines

Quoted 22 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

Quoted 7 lines

Quoted 4 lines

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

Hmmm... Does the following patch help? It swaps the order in which rcu_barrier() acquires the hotplug and rcu_barrier locks.

It changed the report slightly (see for example the change in possible unsafe locking scenario, rcu_sched_state.barrier_mutex vanished and it's now directly about cpu_hotplug.lock). With the patch applied I get

Quoted 5 lines

Quoted 5 lines

Quoted 3 lines

======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-03888-g3f99f3b #145 Not tainted

And it really seems valid.

Yep, it sure is. I wasn't getting the full picture earlier, so please accept my apologies for the bogus patch.

Quoted 17 lines

Quoted 9 lines

kmem_cache_destroy() calls rcu_barrier() with slab_mutex locked, which introduces slab_mutex -> cpu_hotplug.lock dependency (through rcu_barrier() -> _rcu_barrier() -> get_online_cpus()).

On the other hand, _cpu_up() acquires cpu_hotplug.lock through cpu_hotplug_begin(), and with this lock held cpuup_callback() notifier gets called, which acquires slab_mutex. This gives the reverse dependency, i.e. deadlock scenario is valid one.

Quoted 5 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is triggering this, because before that, there was no slab_mutex -> cpu_hotplug.lock dependency.

Simply put, the commit causes get_online_cpus() to be called with slab_mutex held, which is invalid.

Oh, and it seems to be actually triggering in real.

Quoted 4 lines

With HEAD being 974a847e00c, machine suspends nicely. With 974a847e00c + your patch, changing the order in which rcu_barrier() acquires hotplug and rcu_barrier locks, the machine hangs 100% reliably during suspend, which very likely actually is the deadlock described above.

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events.

I could go back to the old approach, but it is
significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

Quoted 65 lines · Paul E. McKenney

Quoted 38 lines · Jiri Kosina

Quoted 36 lines · Jiri Kosina

Quoted 36 lines

Quoted 22 lines

Quoted 22 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

Quoted 7 lines

Quoted 4 lines

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

Hmmm... Does the following patch help? It swaps the order in which rcu_barrier() acquires the hotplug and rcu_barrier locks.

It changed the report slightly (see for example the change in possible unsafe locking scenario, rcu_sched_state.barrier_mutex vanished and it's now directly about cpu_hotplug.lock). With the patch applied I get

Quoted 5 lines

Quoted 5 lines

Quoted 3 lines

======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-03888-g3f99f3b #145 Not tainted

And it really seems valid.

Yep, it sure is. I wasn't getting the full picture earlier, so please accept my apologies for the bogus patch.

Quoted 17 lines

Quoted 9 lines

kmem_cache_destroy() calls rcu_barrier() with slab_mutex locked, which introduces slab_mutex -> cpu_hotplug.lock dependency (through rcu_barrier() -> _rcu_barrier() -> get_online_cpus()).

On the other hand, _cpu_up() acquires cpu_hotplug.lock through cpu_hotplug_begin(), and with this lock held cpuup_callback() notifier gets called, which acquires slab_mutex. This gives the reverse dependency, i.e. deadlock scenario is valid one.

Quoted 5 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is triggering this, because before that, there was no slab_mutex -> cpu_hotplug.lock dependency.

Simply put, the commit causes get_online_cpus() to be called with slab_mutex held, which is invalid.

Oh, and it seems to be actually triggering in real.

Quoted 8 lines

Quoted 4 lines

With HEAD being 974a847e00c, machine suspends nicely. With 974a847e00c + your patch, changing the order in which rcu_barrier() acquires hotplug and rcu_barrier locks, the machine hangs 100% reliably during suspend, which very likely actually is the deadlock described above.

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events.

Why not? IMHO it should have been perfectly fine! See below...

Quoted 5 lines

I could go back to the old approach, but it is
significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

Quoted 7 lines

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

The thing is, get_online_cpus() is smart: it *knows* when you are calling it in a hotplug-writer, IOW, when you are in a hotplug notifier.

The relevant code is:

void get_online_cpus(void)

{
        might_sleep();
        if (cpu_hotplug.active_writer == current)
                return;
	....
}

So calling rcu_barrier() (and hence get_online_cpus()) from within a hotplug notifier should pose no problem at all!

Quoted 103 lines · Srivatsa S. Bhat

Quoted 65 lines · Paul E. McKenney

Quoted 38 lines · Jiri Kosina

Quoted 36 lines · Jiri Kosina

Quoted 36 lines

Quoted 22 lines

Quoted 22 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

Quoted 7 lines

Quoted 4 lines

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

Hmmm... Does the following patch help? It swaps the order in which rcu_barrier() acquires the hotplug and rcu_barrier locks.

It changed the report slightly (see for example the change in possible unsafe locking scenario, rcu_sched_state.barrier_mutex vanished and it's now directly about cpu_hotplug.lock). With the patch applied I get

Quoted 5 lines

Quoted 5 lines

Quoted 3 lines

======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-03888-g3f99f3b #145 Not tainted

And it really seems valid.

Yep, it sure is. I wasn't getting the full picture earlier, so please accept my apologies for the bogus patch.

Quoted 17 lines

Quoted 9 lines

kmem_cache_destroy() calls rcu_barrier() with slab_mutex locked, which introduces slab_mutex -> cpu_hotplug.lock dependency (through rcu_barrier() -> _rcu_barrier() -> get_online_cpus()).

On the other hand, _cpu_up() acquires cpu_hotplug.lock through cpu_hotplug_begin(), and with this lock held cpuup_callback() notifier gets called, which acquires slab_mutex. This gives the reverse dependency, i.e. deadlock scenario is valid one.

Quoted 5 lines

1331e7a1bbe1f11b19c4327ba0853bee2a606543 is triggering this, because before that, there was no slab_mutex -> cpu_hotplug.lock dependency.

Simply put, the commit causes get_online_cpus() to be called with slab_mutex held, which is invalid.

Oh, and it seems to be actually triggering in real.

Quoted 8 lines

Quoted 4 lines

With HEAD being 974a847e00c, machine suspends nicely. With 974a847e00c + your patch, changing the order in which rcu_barrier() acquires hotplug and rcu_barrier locks, the machine hangs 100% reliably during suspend, which very likely actually is the deadlock described above.

Indeed. Slab seems to be doing an rcu_barrier() in a CPU hotplug notifier, which doesn't sit so well with rcu_barrier() trying to exclude CPU hotplug events.

Why not? IMHO it should have been perfectly fine! See below...

Quoted 5 lines

I could go back to the old approach, but it is
significantly more complex. I cannot say that I am all that happy about anyone calling rcu_barrier() from a CPU hotplug notifier because it doesn't help CPU hotplug latency, but that is a separate issue.

Quoted 7 lines

But the thing is that rcu_barrier()'s assumptions work just fine if either
(1) it excludes hotplug operations or (2) if it is called from a hotplug notifier. You see, either way, the CPU cannot go away while rcu_barrier() is executing. So the right way to resolve this seems to be to do the get_online_cpus() only if rcu_barrier() is -not- executing in the context of a hotplug notifier. Should be fixable without too much hassle...

The thing is, get_online_cpus() is smart: it *knows* when you are calling it in a hotplug-writer, IOW, when you are in a hotplug notifier.

The relevant code is:

void get_online_cpus(void)

{
        might_sleep();
        if (cpu_hotplug.active_writer == current)
                return;
	....
}

Quoted 2 lines

So calling rcu_barrier() (and hence get_online_cpus()) from within a hotplug notifier should pose no problem at all!

Indeed, that was my confusion. The deadlock can happen with the slab CPU-hotplug notifier (without calling rcu_barrier()!), which establishes hotplug->slab. The some other unrelated thread calls kmem_cache_destroy(), which acquires slab and then calls rcu_barrier(), which acquires hotplug. So the deadlock can happen independently of rcu_barrier() being called from a CPU-hotplug notifier.

Making kmem_cache_destroy() release slab before calling rcu_barrier() seems to clear things up for Jiri, but we need Pekka's or Christoph Lameter's view on whether this is really safe. (It looks safe to both Jiri and I, but...)

Thanx, Paul

Hi,

this commit:

==
1331e7a1bbe1f11b19c4327ba0853bee2a606543 is the first bad commit commit 1331e7a1bbe1f11b19c4327ba0853bee2a606543

Author: Paul E. McKenney <[email protected]>
Date:   Thu Aug 2 17:43:50 2012 -0700

rcu: Remove _rcu_barrier() dependency on __stop_machine()

Currently, _rcu_barrier() relies on preempt_disable() to prevent any CPU from going offline, which in turn depends on CPU hotplug's use of __stop_machine().

This patch therefore makes _rcu_barrier() use get_online_cpus() to block CPU-hotplug operations. This has the added benefit of removing the need for _rcu_barrier() to adopt callbacks: Because CPU-hotplug operations are excluded, there can be no callbacks to adopt. This commit simplifies the code accordingly.

Signed-off-by Paul E. McKenney <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Josh Triplett <[email protected]>

==

is causing lockdep to complain (see the full trace below). I haven't yet had time to analyze what exactly is happening, and probably will not have time to do so until tomorrow, so just sending this as a heads-up in case anyone sees the culprit immediately.

======================================================
[ INFO: possible circular locking dependency detected ] 3.6.0-rc5-00004-g0d8ee37 #143 Not tainted
-------------------------------------------------------
kworker/u:2/40 is trying to acquire lock:
(rcu_sched_state.barrier_mutex){+.+...}, at: [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0

but task is already holding lock:
(slab_mutex){+.+.+.}, at: [<ffffffff81176e15>] kmem_cache_destroy+0x45/0xe0

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #2 (slab_mutex){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81558cb5>] cpuup_callback+0x2f/0xbe
        [<ffffffff81564b83>] notifier_call_chain+0x93/0x140
        [<ffffffff81076f89>] __raw_notifier_call_chain+0x9/0x10
        [<ffffffff8155719d>] _cpu_up+0xba/0x14e
        [<ffffffff815572ed>] cpu_up+0xbc/0x117
        [<ffffffff81ae05e3>] smp_init+0x6b/0x9f
        [<ffffffff81ac47d6>] kernel_init+0x147/0x1dc
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

-> #1 (cpu_hotplug.lock){+.+.+.}:

        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff81049197>] get_online_cpus+0x37/0x50
        [<ffffffff810f21bb>] _rcu_barrier+0xbb/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff8118c129>] deactivate_locked_super+0x49/0x90
        [<ffffffff8118cc01>] deactivate_super+0x61/0x70
        [<ffffffff811aaaa7>] mntput_no_expire+0x127/0x180
        [<ffffffff811ab49e>] sys_umount+0x6e/0xd0
        [<ffffffff81569979>] system_call_fastpath+0x16/0x1b

-> #0 (rcu_sched_state.barrier_mutex){+.+...}:

        [<ffffffff810adb4e>] check_prev_add+0x3de/0x440
        [<ffffffff810ae1e2>] validate_chain+0x632/0x720
        [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
        [<ffffffff810ae921>] lock_acquire+0x121/0x190
        [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
        [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
        [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0
        [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
        [<ffffffff810f2309>] rcu_barrier+0x9/0x10
        [<ffffffff81176ea1>] kmem_cache_destroy+0xd1/0xe0
        [<ffffffffa04c3154>] nf_conntrack_cleanup_net+0xe4/0x110 [nf_conntrack]
        [<ffffffffa04c31aa>] nf_conntrack_cleanup+0x2a/0x70 [nf_conntrack]
        [<ffffffffa04c42ce>] nf_conntrack_net_exit+0x5e/0x80 [nf_conntrack]
        [<ffffffff81454b79>] ops_exit_list+0x39/0x60
        [<ffffffff814551ab>] cleanup_net+0xfb/0x1b0
        [<ffffffff8106917b>] process_one_work+0x26b/0x4c0
        [<ffffffff81069f3e>] worker_thread+0x12e/0x320
        [<ffffffff8106f73e>] kthread+0x9e/0xb0
        [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10

other info that might help us debug this:

 Chain exists of:
   rcu_sched_state.barrier_mutex --> cpu_hotplug.lock --> slab_mutex

  Possible unsafe locking scenario:

        CPU0                    CPU1
        ----                    ----
   lock(slab_mutex);
                                lock(cpu_hotplug.lock);
                                lock(slab_mutex);

lock(rcu_sched_state.barrier_mutex);

*** DEADLOCK ***

4 locks held by kworker/u:2/40:

  #0:  (netns){.+.+.+}, at: [<ffffffff810690b2>] process_one_work+0x1a2/0x4c0
  #1:  (net_cleanup_work){+.+.+.}, at: [<ffffffff810690b2>] process_one_work+0x1a2/0x4c0
  #2:  (net_mutex){+.+.+.}, at: [<ffffffff81455130>] cleanup_net+0x80/0x1b0
  #3:  (slab_mutex){+.+.+.}, at: [<ffffffff81176e15>] kmem_cache_destroy+0x45/0xe0

 stack backtrace:
 Pid: 40, comm: kworker/u:2 Not tainted 3.6.0-rc5-00004-g0d8ee37 #143
 Call Trace:
  [<ffffffff810ac85f>] print_circular_bug+0x10f/0x120
  [<ffffffff810adb4e>] check_prev_add+0x3de/0x440
  [<ffffffff810ad85a>] ? check_prev_add+0xea/0x440
  [<ffffffff8102c72f>] ? flat_send_IPI_mask+0x7f/0xc0
  [<ffffffff810ae1e2>] validate_chain+0x632/0x720
  [<ffffffff810ae5d9>] __lock_acquire+0x309/0x530
  [<ffffffff810ae921>] lock_acquire+0x121/0x190
  [<ffffffff810f2126>] ? _rcu_barrier+0x26/0x1e0
  [<ffffffff8155d4cc>] __mutex_lock_common+0x5c/0x450
  [<ffffffff810f2126>] ? _rcu_barrier+0x26/0x1e0
  [<ffffffff810b5e45>] ? on_each_cpu+0x65/0xc0
  [<ffffffff810f2126>] ? _rcu_barrier+0x26/0x1e0
  [<ffffffff8155d9ee>] mutex_lock_nested+0x3e/0x50
  [<ffffffff810f2126>] _rcu_barrier+0x26/0x1e0
  [<ffffffff810f22f0>] rcu_barrier_sched+0x10/0x20
  [<ffffffff810f2309>] rcu_barrier+0x9/0x10
  [<ffffffff81176ea1>] kmem_cache_destroy+0xd1/0xe0
  [<ffffffffa04c3154>] nf_conntrack_cleanup_net+0xe4/0x110 [nf_conntrack]
  [<ffffffffa04c31aa>] nf_conntrack_cleanup+0x2a/0x70 [nf_conntrack]
  [<ffffffffa04c42ce>] nf_conntrack_net_exit+0x5e/0x80 [nf_conntrack]
  [<ffffffff81454b79>] ops_exit_list+0x39/0x60
  [<ffffffff814551ab>] cleanup_net+0xfb/0x1b0
  [<ffffffff8106917b>] process_one_work+0x26b/0x4c0
  [<ffffffff810690b2>] ? process_one_work+0x1a2/0x4c0
  [<ffffffff81069e69>] ? worker_thread+0x59/0x320
  [<ffffffff814550b0>] ? net_drop_ns+0x40/0x40
  [<ffffffff81069f3e>] worker_thread+0x12e/0x320
  [<ffffffff81069e10>] ? manage_workers+0x110/0x110
  [<ffffffff8106f73e>] kthread+0x9e/0xb0
  [<ffffffff8156ab44>] kernel_thread_helper+0x4/0x10
  [<ffffffff81560b70>] ? retint_restore_args+0x13/0x13
  [<ffffffff8106f6a0>] ? __init_kthread_worker+0x70/0x70
  [<ffffffff8156ab40>] ? gs_change+0x13/0x13

I don't see how this circular locking dependency can occur.. If you are using SLUB, kmem_cache_destroy() releases slab_mutex before it calls rcu_barrier(). If you are using SLAB, kmem_cache_destroy() wraps its whole operation inside get/put_online_cpus(), which means, it cannot run concurrently with a hotplug operation such as cpu_up(). So, I'm rather puzzled at this lockdep splat..

Quoted 5 lines · Srivatsa S. Bhat

I don't see how this circular locking dependency can occur.. If you are using SLUB, kmem_cache_destroy() releases slab_mutex before it calls rcu_barrier(). If you are using SLAB, kmem_cache_destroy() wraps its whole operation inside get/put_online_cpus(), which means, it cannot run concurrently with a hotplug operation such as cpu_up(). So, I'm rather puzzled at this lockdep splat..

I am using SLAB here.

The scenario I think is very well possible:

	CPU 0				CPU 1
	kmem_cache_destroy()

	mutex_lock(slab_mutex)
	 				_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)

Deadlock.

Right?

Quoted 8 lines · Jiri Kosina

Quoted 5 lines · Srivatsa S. Bhat

I don't see how this circular locking dependency can occur.. If you are using SLUB, kmem_cache_destroy() releases slab_mutex before it calls rcu_barrier(). If you are using SLAB, kmem_cache_destroy() wraps its whole operation inside get/put_online_cpus(), which means, it cannot run concurrently with a hotplug operation such as cpu_up(). So, I'm rather puzzled at this lockdep splat..

Quoted 7 lines

I am using SLAB here.

The scenario I think is very well possible:

	CPU 0				CPU 1
	kmem_cache_destroy()

What about the get_online_cpus() right here at CPU0 before calling mutex_lock(slab_mutex)? How can the cpu_up() proceed on CPU1?? I still don't get it... :(

(kmem_cache_destroy() uses get/put_online_cpus() around acquiring and releasing slab_mutex).

Regards,
Srivatsa S. Bhat

Quoted 16 lines

	mutex_lock(slab_mutex)
	 				_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)

Deadlock.

Right?

Quoted 21 lines · Srivatsa S. Bhat

Quoted 8 lines · Jiri Kosina

Quoted 5 lines · Srivatsa S. Bhat

I don't see how this circular locking dependency can occur.. If you are using SLUB, kmem_cache_destroy() releases slab_mutex before it calls rcu_barrier(). If you are using SLAB, kmem_cache_destroy() wraps its whole operation inside get/put_online_cpus(), which means, it cannot run concurrently with a hotplug operation such as cpu_up(). So, I'm rather puzzled at this lockdep splat..

Quoted 7 lines

I am using SLAB here.

The scenario I think is very well possible:

	CPU 0				CPU 1
	kmem_cache_destroy()

What about the get_online_cpus() right here at CPU0 before calling mutex_lock(slab_mutex)? How can the cpu_up() proceed on CPU1?? I still don't get it... :(

Quoted 2 lines

(kmem_cache_destroy() uses get/put_online_cpus() around acquiring and releasing slab_mutex).

The problem is that there is a CPU-hotplug notifier for slab, which establishes hotplug->slab.

Then having kmem_cache_destroy() call
rcu_barrier() under the lock

establishes slab->hotplug, which results
in deadlock. Jiri really did explain this in an earlier email message, but both of us managed to miss it. ;-)

Thanx, Paul

Quoted 21 lines

Regards,
Srivatsa S. Bhat

Quoted 16 lines

	mutex_lock(slab_mutex)
	 				_cpu_up()
					cpu_hotplug_begin()
					mutex_lock(cpu_hotplug.lock)
	rcu_barrier()
	_rcu_barrier()
	get_online_cpus()
	mutex_lock(cpu_hotplug.lock)
	 (blocks, CPU 1 has the mutex)
					__cpu_notify()
					mutex_lock(slab_mutex)

Deadlock.

Right?

Quoted 7 lines

Quoted 7 lines

Quoted 2 lines

	CPU 0				CPU 1
	kmem_cache_destroy()

What about the get_online_cpus() right here at CPU0 before calling mutex_lock(slab_mutex)? How can the cpu_up() proceed on CPU1?? I still don't get it... :(

Quoted 5 lines

Quoted 2 lines

(kmem_cache_destroy() uses get/put_online_cpus() around acquiring and releasing slab_mutex).

The problem is that there is a CPU-hotplug notifier for slab, which establishes hotplug->slab.

Agreed.

Quoted 2 lines

Then having kmem_cache_destroy() call
rcu_barrier() under the lock

Ah, that's where I disagree. kmem_cache_destroy() *cannot* proceed at this point in time, because it has invoked get_online_cpus()! It simply cannot be running past that point in the presence of a running hotplug notifier! So, kmem_cache_destroy() should have been sleeping on the hotplug lock, waiting for the notifier to release it, no?

Quoted 15 lines · Srivatsa S. Bhat

Quoted 7 lines

Quoted 7 lines

Quoted 2 lines

	CPU 0				CPU 1
	kmem_cache_destroy()

What about the get_online_cpus() right here at CPU0 before calling mutex_lock(slab_mutex)? How can the cpu_up() proceed on CPU1?? I still don't get it... :(

Quoted 5 lines

Quoted 2 lines

(kmem_cache_destroy() uses get/put_online_cpus() around acquiring and releasing slab_mutex).

The problem is that there is a CPU-hotplug notifier for slab, which establishes hotplug->slab.

Agreed.

Quoted 8 lines

Quoted 2 lines

Then having kmem_cache_destroy() call
rcu_barrier() under the lock

Ah, that's where I disagree. kmem_cache_destroy() *cannot* proceed at this point in time, because it has invoked get_online_cpus()! It simply cannot be running past that point in the presence of a running hotplug notifier! So, kmem_cache_destroy() should have been sleeping on the hotplug lock, waiting for the notifier to release it, no?

Please look carefully at the scenario again. kmem_cache_destroy() calls get_online_cpus() before the hotplug notifier even starts. Hence it has no reason to block there (noone is holding hotplug lock).

*Then* hotplug notifier fires up, succeeds obtaining hotplug lock,

kmem_cache_destroy() calls rcu_barrier in the meantime, and blocks itself on the hotplug lock there.

Please note that the get_online_cpus() call in kmem_cache_destroy() doesn't play *any* role in this scenario.

Quoted 26 lines · Jiri Kosina

Quoted 15 lines · Srivatsa S. Bhat

Quoted 7 lines

Quoted 7 lines

Quoted 2 lines

	CPU 0				CPU 1
	kmem_cache_destroy()

What about the get_online_cpus() right here at CPU0 before calling mutex_lock(slab_mutex)? How can the cpu_up() proceed on CPU1?? I still don't get it... :(

Quoted 5 lines

Quoted 2 lines

(kmem_cache_destroy() uses get/put_online_cpus() around acquiring and releasing slab_mutex).

The problem is that there is a CPU-hotplug notifier for slab, which establishes hotplug->slab.

Agreed.

Quoted 8 lines

Quoted 2 lines

Then having kmem_cache_destroy() call
rcu_barrier() under the lock

Ah, that's where I disagree. kmem_cache_destroy() *cannot* proceed at this point in time, because it has invoked get_online_cpus()! It simply cannot be running past that point in the presence of a running hotplug notifier! So, kmem_cache_destroy() should have been sleeping on the hotplug lock, waiting for the notifier to release it, no?

Quoted 4 lines

Please look carefully at the scenario again. kmem_cache_destroy() calls get_online_cpus() before the hotplug notifier even starts. Hence it has no reason to block there (noone is holding hotplug lock).

Agreed.

Quoted 1 line

*Then* hotplug notifier fires up, succeeds obtaining hotplug lock,

Ah, that's the problem! The hotplug reader-writer synchronization is not just via a simple mutex. Its a refcount underneath. If kmem_cache_destroy() incremented the refcount, the hotplug-writer (cpu_up) will release the hotplug lock immediately and try again. IOW, a hotplug-reader (kmem_cache_destroy()) and a hotplug-writer (cpu_up) can *NEVER* run concurrently. If they do, we are totally screwed!

Take a look at the hotplug lock acquire function at the writer side:

static void cpu_hotplug_begin(void)

{
        cpu_hotplug.active_writer = current;

        for (;;) {
                mutex_lock(&cpu_hotplug.lock);
                if (likely(!cpu_hotplug.refcount))   <================ This one!
                        break;
                __set_current_state(TASK_UNINTERRUPTIBLE);
                mutex_unlock(&cpu_hotplug.lock);
                schedule();
        }   
}

Quoted 46 lines · Srivatsa S. Bhat

Quoted 26 lines · Jiri Kosina

Quoted 15 lines · Srivatsa S. Bhat

Quoted 7 lines

Quoted 7 lines

Quoted 2 lines

	CPU 0				CPU 1
	kmem_cache_destroy()

What about the get_online_cpus() right here at CPU0 before calling mutex_lock(slab_mutex)? How can the cpu_up() proceed on CPU1?? I still don't get it... :(

Quoted 5 lines

Quoted 2 lines

(kmem_cache_destroy() uses get/put_online_cpus() around acquiring and releasing slab_mutex).

The problem is that there is a CPU-hotplug notifier for slab, which establishes hotplug->slab.

Agreed.

Quoted 8 lines

Quoted 2 lines

Then having kmem_cache_destroy() call
rcu_barrier() under the lock

Ah, that's where I disagree. kmem_cache_destroy() *cannot* proceed at this point in time, because it has invoked get_online_cpus()! It simply cannot be running past that point in the presence of a running hotplug notifier! So, kmem_cache_destroy() should have been sleeping on the hotplug lock, waiting for the notifier to release it, no?

Quoted 4 lines

Please look carefully at the scenario again. kmem_cache_destroy() calls get_online_cpus() before the hotplug notifier even starts. Hence it has no reason to block there (noone is holding hotplug lock).

Agreed.

Quoted 1 line

*Then* hotplug notifier fires up, succeeds obtaining hotplug lock,

Ah, that's the problem! The hotplug reader-writer synchronization is not just via a simple mutex. Its a refcount underneath. If kmem_cache_destroy() incremented the refcount, the hotplug-writer (cpu_up) will release the hotplug lock immediately and try again. IOW, a hotplug-reader (kmem_cache_destroy()) and a hotplug-writer (cpu_up) can *NEVER* run concurrently. If they do, we are totally screwed!

Take a look at the hotplug lock acquire function at the writer side:

static void cpu_hotplug_begin(void)

Quoted 12 lines

{
        cpu_hotplug.active_writer = current;

        for (;;) {
                mutex_lock(&cpu_hotplug.lock);
                if (likely(!cpu_hotplug.refcount))   <================ This one!
                        break;
                __set_current_state(TASK_UNINTERRUPTIBLE);
                mutex_unlock(&cpu_hotplug.lock);
                schedule();
        }   
}

I acutally just came to the same conclusion (7 hours of sleep later, the mind indeed seems to be brighter ... what a poet I am).

Lockdep doesn't know about this semantics of cpu_hotplug_begin(), and therefore gets confused by the fact that mutual exclusion is actually achieved through the refcount instead of mutex (and the same apparently happened to me).

So right, now I agree that the deadlock scenario I have come up with is indeed bogus (*), and we just have to annotate this fact to lockdep somehow.

And I actually believe that moving the slab_mutex around in kmem_cache_destroy() is a good anotation (maybe worth a separate comment in the code), as it not only makes the lockdep false positive go away, but it also reduces the mutex hold time.

(*) I have seen machine locking hard reproducibly, but that was only with additional Paul's patch, so I guess the lock order there actually was wrong

Quoted 14 lines

Quoted 13 lines

static void cpu_hotplug_begin(void)

{
        cpu_hotplug.active_writer = current;

        for (;;) {
                mutex_lock(&cpu_hotplug.lock);
                if (likely(!cpu_hotplug.refcount))   <================ This one!
                        break;
                __set_current_state(TASK_UNINTERRUPTIBLE);
                mutex_unlock(&cpu_hotplug.lock);
                schedule();
        }   
}

Quoted 7 lines

I acutally just came to the same conclusion (7 hours of sleep later, the mind indeed seems to be brighter ... what a poet I am).

Lockdep doesn't know about this semantics of cpu_hotplug_begin(), and therefore gets confused by the fact that mutual exclusion is actually achieved through the refcount instead of mutex (and the same apparently happened to me).

No, that's not the problem. Lockdep is fine. The calltrace clearly shows that our refcounting has messed up somewhere. As a result, we really *are* running a hotplug-reader and a hotplug-writer at the same time! We really need to fix *that*! So please try the second debug patch I sent just now (with the BUG_ON() in put_online_cpus()). We need to know who is calling put_online_cpus() twice and fix that culprit!

Quoted 3 lines

So right, now I agree that the deadlock scenario I have come up with is indeed bogus (*), and we just have to annotate this fact to lockdep somehow.

Yes, the deadlock scenario is bogus, but the refcounting leak is for real and needs fixing.

I'm fine with this, but the real problem is elsewhere, like I mentioned above. This one is only a good-to-have, not a fix.

Quoted 3 lines

(*) I have seen machine locking hard reproducibly, but that was only with additional Paul's patch, so I guess the lock order there actually was wrong

If refcounting was working fine, Paul's patch wouldn't have caused *any* issues. With that patch in place, the 2 places where rcu_barrier() get invoked (ie., kmem_cache_destroy() and deactivate_locked_super()) both start waiting on get_online_cpus() until the slab cpu hotplug notifier as well as the entire cpu_up operation completes. Absolutely no problem in that! So the fact that you are seeing lock-ups here is another indication that the problem is really elsewhere!

Quoted 22 lines · Srivatsa S. Bhat

Quoted 14 lines

Quoted 13 lines

static void cpu_hotplug_begin(void)

{
        cpu_hotplug.active_writer = current;

        for (;;) {
                mutex_lock(&cpu_hotplug.lock);
                if (likely(!cpu_hotplug.refcount))   <================ This one!
                        break;
                __set_current_state(TASK_UNINTERRUPTIBLE);
                mutex_unlock(&cpu_hotplug.lock);
                schedule();
        }   
}

Quoted 7 lines

I acutally just came to the same conclusion (7 hours of sleep later, the mind indeed seems to be brighter ... what a poet I am).

Lockdep doesn't know about this semantics of cpu_hotplug_begin(), and therefore gets confused by the fact that mutual exclusion is actually achieved through the refcount instead of mutex (and the same apparently happened to me).

Quoted 6 lines

No, that's not the problem. Lockdep is fine. The calltrace clearly shows that our refcounting has messed up somewhere. As a result, we really *are* running a hotplug-reader and a hotplug-writer at the same time! We really need to fix *that*! So please try the second debug patch I sent just now (with the BUG_ON() in put_online_cpus()). We need to know who is calling put_online_cpus() twice and fix that culprit!

I don't think so.

Lockdep is complaining, because

(a) during system bootup, the smp_init() -> cpu_up() -> cpuup_callback()

    teaches him about hotplug.lock -> slab_mutex dependency

(b) many many jiffies later, nf_conntrack_cleanup_net() calls

    kmem_cache_destroy(), which introduces slab_mutex -> hotplug.lock 
    dependency

Lockdep rightfully (from his POV) sees this as potential ABBA, and reports it, it's as simple as that.
It has no way of knowing the fact that the ABBA can actually never happen, because of special semantics of cpu_hotplug.refcount and it's handling in cpu_hotplug_begin().

The "neither cpu_up() nor cpu_down() will proceed past cpu_hotplug_begin() until everyone who called get_online_cpus() will call put_online_cpus()" is totally invisible to lockdep.

Quoted 7 lines

Quoted 4 lines

So right, now I agree that the deadlock scenario I have come up with is indeed bogus (*), and we just have to annotate this fact to lockdep somehow.

Yes, the deadlock scenario is bogus, but the refcounting leak is for real and needs fixing.

With your patch applied, the BUG_ON() in put_online_cpus() didn't trigger for me at all. Which is what I expected.

Quoted 8 lines

I'm fine with this, but the real problem is elsewhere, like I mentioned above. This one is only a good-to-have, not a fix.

Quoted 3 lines

(*) I have seen machine locking hard reproducibly, but that was only with additional Paul's patch, so I guess the lock order there actually was wrong

Quoted 7 lines

If refcounting was working fine, Paul's patch wouldn't have caused *any* issues. With that patch in place, the 2 places where rcu_barrier() get invoked (ie., kmem_cache_destroy() and deactivate_locked_super()) both start waiting on get_online_cpus() until the slab cpu hotplug notifier as well as the entire cpu_up operation completes. Absolutely no problem in that! So the fact that you are seeing lock-ups here is another indication that the problem is really elsewhere!

I don't agree. The reason why Paul's patch (1331e7a1bb) started to trigger this, is that (b) above doesn't exist in pre-1331e7a1bb kernels.