single-threaded wq lockdep is broken

single-threaded wq lockdep is broken

[Johannes Berg]

Hi Tejun,

I suspect this is a long-standing bug introduced by all the pool rework
you did at some point, but I don't really know nor can I figure out how
to fix it right now. I guess it could possibly also be a lockdep issue,
or an issue in how it's used, but I definitely know that this used to
work (i.e. warn) back when I introduced the lockdep checking to the WQ
code. I was actually bitten by a bug like this, and erroneously
dismissed it as not being the case because lockdep hadn't warned (and
the actual deadlock debug output is basically not existent).

In any case, the following code really should result in a warning from
lockdep, but doesn't. If you comment in the #define DEADLOCK, it will
actually cause a deadlock :)


#include <linux/kernel.h>
#include <linux/mutex.h>
#include <linux/workqueue.h>
#include <linux/module.h>
#include <linux/delay.h>

DEFINE_MUTEX(mtx);
static struct workqueue_struct *wq;
static struct work_struct w1, w2;

static void w1_wk(struct work_struct *w)
{
	mutex_lock(&mtx);
	msleep(100);
	mutex_unlock(&mtx);
}

static void w2_wk(struct work_struct *w)
{
}

/*
 * if not defined, then lockdep should warn only,
 * if defined, the system will really deadlock.
 */

//#define DEADLOCK

static int init(void)
{
	wq = create_singlethread_workqueue("test");
	if (!wq)
		return -ENOMEM;
	INIT_WORK(&w1, w1_wk);
	INIT_WORK(&w2, w2_wk);

#ifdef DEADLOCK
	queue_work(wq, &w1);
	queue_work(wq, &w2);
#endif
	mutex_lock(&mtx);
	flush_work(&w2);
	mutex_unlock(&mtx);

#ifndef DEADLOCK
	queue_work(wq, &w1);
	queue_work(wq, &w2);
#endif

	return 0;
}
module_init(init);


(to test, just copy it to some C file and add "obj-y += myfile.o" to
the Makefile in that directory, then boot the kernel - perhaps in a VM)

johannes

Re: single-threaded wq lockdep is broken

[Lai Jiangshan]

On Mon, May 29, 2017 at 3:33 AM, Johannes Berg
<johannes@sipsolutions.net> wrote:
> Hi Tejun,
>
> I suspect this is a long-standing bug introduced by all the pool rework
> you did at some point, but I don't really know nor can I figure out how
> to fix it right now. I guess it could possibly also be a lockdep issue,
> or an issue in how it's used, but I definitely know that this used to
> work (i.e. warn) back when I introduced the lockdep checking to the WQ
> code. I was actually bitten by a bug like this, and erroneously
> dismissed it as not being the case because lockdep hadn't warned (and
> the actual deadlock debug output is basically not existent).
>
> In any case, the following code really should result in a warning from
> lockdep, but doesn't. If you comment in the #define DEADLOCK, it will
> actually cause a deadlock :)
>
>
> #include <linux/kernel.h>
> #include <linux/mutex.h>
> #include <linux/workqueue.h>
> #include <linux/module.h>
> #include <linux/delay.h>
>
> DEFINE_MUTEX(mtx);
> static struct workqueue_struct *wq;
> static struct work_struct w1, w2;
>
> static void w1_wk(struct work_struct *w)
> {
>         mutex_lock(&mtx);
>         msleep(100);
>         mutex_unlock(&mtx);
> }
>
> static void w2_wk(struct work_struct *w)
> {
> }
>
> /*
>  * if not defined, then lockdep should warn only,

I guess when DEADLOCK not defined, there is no
work is queued nor executed, therefore, no lock
dependence is recorded, and there is no warn
either.

>  * if defined, the system will really deadlock.
>  */
>
> //#define DEADLOCK
>
> static int init(void)
> {
>         wq = create_singlethread_workqueue("test");
>         if (!wq)
>                 return -ENOMEM;
>         INIT_WORK(&w1, w1_wk);
>         INIT_WORK(&w2, w2_wk);
>

        /* add lock dependence, the lockdep should warn */
        queue_work(wq, &w1);
        queue_work(wq, &w2);
        flush_work(&w1);

> #ifdef DEADLOCK
>         queue_work(wq, &w1);
>         queue_work(wq, &w2);
> #endif
>         mutex_lock(&mtx);
>         flush_work(&w2);
>         mutex_unlock(&mtx);
>
> #ifndef DEADLOCK
>         queue_work(wq, &w1);
>         queue_work(wq, &w2);
> #endif
>
>         return 0;
> }
> module_init(init);
>
>
> (to test, just copy it to some C file and add "obj-y += myfile.o" to
> the Makefile in that directory, then boot the kernel - perhaps in a VM)
>
> johannes

Re: single-threaded wq lockdep is broken

[Johannes Berg]

Hi,

> > #include <linux/kernel.h>
> > #include <linux/mutex.h>
> > #include <linux/workqueue.h>
> > #include <linux/module.h>
> > #include <linux/delay.h>
> > 
> > DEFINE_MUTEX(mtx);
> > static struct workqueue_struct *wq;
> > static struct work_struct w1, w2;
> > 
> > static void w1_wk(struct work_struct *w)
> > {
> >         mutex_lock(&mtx);
> >         msleep(100);
> >         mutex_unlock(&mtx);
> > }
> > 
> > static void w2_wk(struct work_struct *w)
> > {
> > }
> > 
> > /*
> >  * if not defined, then lockdep should warn only,
> 
> I guess when DEADLOCK not defined, there is no
> work is queued nor executed, therefore, no lock
> dependence is recorded, and there is no warn
> either.
> 
> >  * if defined, the system will really deadlock.
> >  */
> > 
> > //#define DEADLOCK
> > 
> > static int init(void)
> > {
> >         wq = create_singlethread_workqueue("test");
> >         if (!wq)
> >                 return -ENOMEM;
> >         INIT_WORK(&w1, w1_wk);
> >         INIT_WORK(&w2, w2_wk);
> > 
> 
>         /* add lock dependence, the lockdep should warn */
>         queue_work(wq, &w1);
>         queue_work(wq, &w2);
>         flush_work(&w1);
> 
> > #ifdef DEADLOCK
> >         queue_work(wq, &w1);
> >         queue_work(wq, &w2);
> > #endif
> >         mutex_lock(&mtx);
> >         flush_work(&w2);
> >         mutex_unlock(&mtx);
> > 
> > #ifndef DEADLOCK
> >         queue_work(wq, &w1);
> >         queue_work(wq, &w2);
> > #endif

This was "ifndef", so it does in fact run here, just like you
suggested. It doesn't warn though.

I don't think the order of queue/flush would matter, in fact, if you
insert it like you did, with the flush outside the mutex, no issue
exists (until the later flush)

johannes

Re: single-threaded wq lockdep is broken

[Johannes Berg]

On Wed, 2017-05-31 at 10:36 +0200, Johannes Berg wrote:
> 
> This was "ifndef", so it does in fact run here, just like you
> suggested. It doesn't warn though.

Also, even if DEADLOCK *is* defined, lockdep doesn't report anything.

johannes

Re: single-threaded wq lockdep is broken

[Tejun Heo]

Hello, Johannes.

On Sun, May 28, 2017 at 09:33:13PM +0200, Johannes Berg wrote:
> I suspect this is a long-standing bug introduced by all the pool rework
> you did at some point, but I don't really know nor can I figure out how
> to fix it right now. I guess it could possibly also be a lockdep issue,
> or an issue in how it's used, but I definitely know that this used to
> work (i.e. warn) back when I introduced the lockdep checking to the WQ

Hah, didn't know this worked.

> code. I was actually bitten by a bug like this, and erroneously
> dismissed it as not being the case because lockdep hadn't warned (and
> the actual deadlock debug output is basically not existent).
> 
> In any case, the following code really should result in a warning from
> lockdep, but doesn't. If you comment in the #define DEADLOCK, it will
> actually cause a deadlock :)
...
> static void w1_wk(struct work_struct *w)
> {
> 	mutex_lock(&mtx);
> 	msleep(100);
> 	mutex_unlock(&mtx);
> }
...
> static int init(void)
> {
> 	wq = create_singlethread_workqueue("test");
> 	if (!wq)
> 		return -ENOMEM;
> 	INIT_WORK(&w1, w1_wk);
> 	INIT_WORK(&w2, w2_wk);
> 
> #ifdef DEADLOCK
> 	queue_work(wq, &w1);
> 	queue_work(wq, &w2);
> #endif
> 	mutex_lock(&mtx);
> 	flush_work(&w2);
> 	mutex_unlock(&mtx);

So, it used to always create dependency between work items on
singlethread workqueues according to their queeing order?  It
shouldn't be difficult to fix.  I'll dig through the history and see
what happened.

Thanks.

-- 
tejun

Re: single-threaded wq lockdep is broken

[Johannes Berg]

Hi Tejun,

> On Sun, May 28, 2017 at 09:33:13PM +0200, Johannes Berg wrote:
> > I suspect this is a long-standing bug introduced by all the pool
> > rework
> > you did at some point, but I don't really know nor can I figure out
> > how
> > to fix it right now. I guess it could possibly also be a lockdep
> > issue,
> > or an issue in how it's used, but I definitely know that this used
> > to
> > work (i.e. warn) back when I introduced the lockdep checking to the
> > WQ
> 
> Hah, didn't know this worked.

Ah, it was nice when I made this work - but you won't believe the
number of times I had to answer the question "what does this mean?" :-)

> So, it used to always create dependency between work items on
> singlethread workqueues according to their queeing order?  It
> shouldn't be difficult to fix.  I'll dig through the history and see
> what happened.

No, queuing order is (was) irrelevant, and I'm not sure it should
really matter all that much, since you often can't really predict
queueing order. It used to be that this triggered a lot on the
system_wq, which of course is no longer single-threaded so I suppose it
can make progress even in situations like this?

It basically just did a dependency of wq->work, work->mutex (according
to my code) and mutex->wq due to the flush.

I think that perhaps the last dependency of mutex->wq is lost now due
to flush_work()? Or perhaps there's something with the read/write thing
that caused this issue.

johannes

Re: single-threaded wq lockdep is broken

[Lai Jiangshan]

On Wed, May 31, 2017 at 4:36 PM, Johannes Berg
<johannes@sipsolutions.net> wrote:
> Hi,
>
>> > #include <linux/kernel.h>
>> > #include <linux/mutex.h>
>> > #include <linux/workqueue.h>
>> > #include <linux/module.h>
>> > #include <linux/delay.h>
>> >
>> > DEFINE_MUTEX(mtx);
>> > static struct workqueue_struct *wq;
>> > static struct work_struct w1, w2;
>> >
>> > static void w1_wk(struct work_struct *w)
>> > {
>> >         mutex_lock(&mtx);
>> >         msleep(100);
>> >         mutex_unlock(&mtx);
>> > }
>> >
>> > static void w2_wk(struct work_struct *w)
>> > {
>> > }
>> >
>> > /*
>> >  * if not defined, then lockdep should warn only,
>>
>> I guess when DEADLOCK not defined, there is no
>> work is queued nor executed, therefore, no lock
>> dependence is recorded, and there is no warn
>> either.
>>
>> >  * if defined, the system will really deadlock.
>> >  */
>> >
>> > //#define DEADLOCK
>> >
>> > static int init(void)
>> > {
>> >         wq = create_singlethread_workqueue("test");
>> >         if (!wq)
>> >                 return -ENOMEM;
>> >         INIT_WORK(&w1, w1_wk);
>> >         INIT_WORK(&w2, w2_wk);
>> >
>>
>>         /* add lock dependence, the lockdep should warn */
>>         queue_work(wq, &w1);
>>         queue_work(wq, &w2);
>>         flush_work(&w1);
>>
>> > #ifdef DEADLOCK
>> >         queue_work(wq, &w1);
>> >         queue_work(wq, &w2);
>> > #endif
>> >         mutex_lock(&mtx);
>> >         flush_work(&w2);
>> >         mutex_unlock(&mtx);
>> >
>> > #ifndef DEADLOCK
>> >         queue_work(wq, &w1);
>> >         queue_work(wq, &w2);
>> > #endif
>
> This was "ifndef", so it does in fact run here, just like you
> suggested. It doesn't warn though.
>
> I don't think the order of queue/flush would matter, in fact, if you
> insert it like you did, with the flush outside the mutex, no issue
> exists (until the later flush)
>

the @w2 is not queued before flush_work(&w2), it is expected
that @w2 is not associated with @wq, and the dependence
mtx -> wq will not be recorded. And it is expected no warning.

> Also, even if DEADLOCK *is* defined, lockdep doesn't report anything.

Uhhh..... I have no idea about it yet.

Re: single-threaded wq lockdep is broken

[Johannes Berg]

On Fri, 2017-06-02 at 15:03 +0800, Lai Jiangshan wrote:
> 
> the @w2 is not queued before flush_work(&w2), it is expected
> that @w2 is not associated with @wq, and the dependence
> mtx -> wq will not be recorded. And it is expected no warning.

Lockdep is symmetric. So then maybe it won't warn when executing
flush_work(), but should later when executing @w2. No real difference?

johannes

Re: single-threaded wq lockdep is broken

[Tejun Heo]

Hello,

Johannes reported that lockdep warning on single threaded workqueues
doesn't work anymore.  Nothing really changed there and all the
relevant lockdep annotaitons are being invoked correctly.  The
following is the extracted lockdep-only reproducer.

The culprit seems to be lock_map_acquire_read() being mapped to
lock_map_acquire_shared_recursive() instead of
lock_map_acquire_shared().  Is the following expected to not trigger
lockdep warning?  Should workqueue be using
rwsem_acquire[_read]/release() instead of lock_map*()?

Thanks.

#include <linux/kernel.h>
#include <linux/mutex.h>
#include <linux/slab.h>
#include <linux/module.h>

DEFINE_MUTEX(mtx);

static int init(void)
{
	static struct lock_class_key key;
	struct lockdep_map *map;

	printk("XXX lockdep test start\n");

	map = kzalloc(sizeof(*map), GFP_KERNEL);
	lockdep_init_map(map, "test_map", &key, 0);

	mutex_lock(&mtx);
	lock_map_acquire(map);
	lock_map_release(map);
	mutex_unlock(&mtx);

	lock_map_acquire_read(map);
	mutex_lock(&mtx);
	mutex_unlock(&mtx);
	lock_map_release(map);

	printk("XXX lockdep test end\n");
	return 0;
}
module_init(init);