Fix false positive by LOCKDEP_CROSSRELEASE

Fix false positive by LOCKDEP_CROSSRELEASE

[Byungchul Park]

Several false positives were reported, so I tried to fix them.

It would be appreciated if you tell me if it works as expected, or let
me know your opinion.

Thank you,
Byungchul

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

[RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Byungchul Park]

Sometimes, we want to initialize completions with sparate lockdep maps
to assign lock classes under control. For example, the workqueue code
manages lockdep maps, as it can classify lockdep maps properly.
Provided a function for that purpose.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/completion.h | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/include/linux/completion.h b/include/linux/completion.h
index cae5400..182d56e 100644
--- a/include/linux/completion.h
+++ b/include/linux/completion.h
@@ -49,6 +49,13 @@ static inline void complete_release_commit(struct completion *x)
 	lock_commit_crosslock((struct lockdep_map *)&x->map);
 }
 
+#define init_completion_with_map(x, m)					\
+do {									\
+	lockdep_init_map_crosslock((struct lockdep_map *)&(x)->map,	\
+			(m)->name, (m)->key, 0);				\
+	__init_completion(x);						\
+} while (0)
+
 #define init_completion(x)						\
 do {									\
 	static struct lock_class_key __key;				\
@@ -58,6 +65,7 @@ static inline void complete_release_commit(struct completion *x)
 	__init_completion(x);						\
 } while (0)
 #else
+#define init_completion_with_map(x, m) __init_completion(x)
 #define init_completion(x) __init_completion(x)
 static inline void complete_acquire(struct completion *x) {}
 static inline void complete_release(struct completion *x) {}
-- 
1.9.1

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

[RESEND PATCH 2/3] lockdep: Remove unnecessary acquisitions wrt workqueue flush

[Byungchul Park]

The workqueue added manual acquisitions to catch deadlock cases.
Now crossrelease was introduced, some of those are redundant, since
wait_for_completion() already includes the acquisition for itself.
Removed it.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/workqueue.h |  4 ++--
 kernel/workqueue.c        | 20 ++++----------------
 2 files changed, 6 insertions(+), 18 deletions(-)

diff --git a/include/linux/workqueue.h b/include/linux/workqueue.h
index db6dc9d..1bef13e 100644
--- a/include/linux/workqueue.h
+++ b/include/linux/workqueue.h
@@ -218,7 +218,7 @@ static inline void destroy_delayed_work_on_stack(struct delayed_work *work) { }
 									\
 		__init_work((_work), _onstack);				\
 		(_work)->data = (atomic_long_t) WORK_DATA_INIT();	\
-		lockdep_init_map(&(_work)->lockdep_map, #_work, &__key, 0); \
+		lockdep_init_map(&(_work)->lockdep_map, "(complete)"#_work, &__key, 0); \
 		INIT_LIST_HEAD(&(_work)->entry);			\
 		(_work)->func = (_func);				\
 	} while (0)
@@ -398,7 +398,7 @@ enum {
 	static struct lock_class_key __key;				\
 	const char *__lock_name;					\
 									\
-	__lock_name = #fmt#args;					\
+	__lock_name = "(complete)"#fmt#args;				\
 									\
 	__alloc_workqueue_key((fmt), (flags), (max_active),		\
 			      &__key, __lock_name, ##args);		\
diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index ab3c0dc..72f68b1 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -2497,15 +2497,8 @@ static void insert_wq_barrier(struct pool_workqueue *pwq,
 	INIT_WORK_ONSTACK(&barr->work, wq_barrier_func);
 	__set_bit(WORK_STRUCT_PENDING_BIT, work_data_bits(&barr->work));
 
-	/*
-	 * Explicitly init the crosslock for wq_barrier::done, make its lock
-	 * key a subkey of the corresponding work. As a result we won't
-	 * build a dependency between wq_barrier::done and unrelated work.
-	 */
-	lockdep_init_map_crosslock((struct lockdep_map *)&barr->done.map,
-				   "(complete)wq_barr::done",
-				   target->lockdep_map.key, 1);
-	__init_completion(&barr->done);
+	init_completion_with_map(&barr->done, &target->lockdep_map);
+
 	barr->task = current;
 
 	/*
@@ -2611,16 +2604,14 @@ void flush_workqueue(struct workqueue_struct *wq)
 	struct wq_flusher this_flusher = {
 		.list = LIST_HEAD_INIT(this_flusher.list),
 		.flush_color = -1,
-		.done = COMPLETION_INITIALIZER_ONSTACK(this_flusher.done),
 	};
 	int next_color;
 
+	init_completion_with_map(&this_flusher.done, &wq->lockdep_map);
+
 	if (WARN_ON(!wq_online))
 		return;
 
-	lock_map_acquire(&wq->lockdep_map);
-	lock_map_release(&wq->lockdep_map);
-
 	mutex_lock(&wq->mutex);
 
 	/*
@@ -2883,9 +2874,6 @@ bool flush_work(struct work_struct *work)
 	if (WARN_ON(!wq_online))
 		return false;
 
-	lock_map_acquire(&work->lockdep_map);
-	lock_map_release(&work->lockdep_map);
-
 	if (start_flush_work(work, &barr)) {
 		wait_for_completion(&barr.done);
 		destroy_work_on_stack(&barr.work);
-- 
1.9.1

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

[RESEND PATCH 3/3] lockdep: Assign a lock_class per gendisk used for wait_for_completion()

[Byungchul Park]

Darrick and Dave Chinner posted the following warning:

> ======================================================
> WARNING: possible circular locking dependency detected
> 4.14.0-rc1-fixes #1 Tainted: G        W
> ------------------------------------------------------
> loop0/31693 is trying to acquire lock:
>  (&(&ip->i_mmaplock)->mr_lock){++++}, at: [<ffffffffa00f1b0c>] xfs_ilock+0x23c/0x330 [xfs]
>
> but now in release context of a crosslock acquired at the following:
>  ((complete)&ret.event){+.+.}, at: [<ffffffff81326c1f>] submit_bio_wait+0x7f/0xb0
>
> which lock already depends on the new lock.
>
> the existing dependency chain (in reverse order) is:
>
> -> #2 ((complete)&ret.event){+.+.}:
>        lock_acquire+0xab/0x200
>        wait_for_completion_io+0x4e/0x1a0
>        submit_bio_wait+0x7f/0xb0
>        blkdev_issue_zeroout+0x71/0xa0
>        xfs_bmapi_convert_unwritten+0x11f/0x1d0 [xfs]
>        xfs_bmapi_write+0x374/0x11f0 [xfs]
>        xfs_iomap_write_direct+0x2ac/0x430 [xfs]
>        xfs_file_iomap_begin+0x20d/0xd50 [xfs]
>        iomap_apply+0x43/0xe0
>        dax_iomap_rw+0x89/0xf0
>        xfs_file_dax_write+0xcc/0x220 [xfs]
>        xfs_file_write_iter+0xf0/0x130 [xfs]
>        __vfs_write+0xd9/0x150
>        vfs_write+0xc8/0x1c0
>        SyS_write+0x45/0xa0
>        entry_SYSCALL_64_fastpath+0x1f/0xbe
>
> -> #1 (&xfs_nondir_ilock_class){++++}:
>        lock_acquire+0xab/0x200
>        down_write_nested+0x4a/0xb0
>        xfs_ilock+0x263/0x330 [xfs]
>        xfs_setattr_size+0x152/0x370 [xfs]
>        xfs_vn_setattr+0x6b/0x90 [xfs]
>        notify_change+0x27d/0x3f0
>        do_truncate+0x5b/0x90
>        path_openat+0x237/0xa90
>        do_filp_open+0x8a/0xf0
>        do_sys_open+0x11c/0x1f0
>        entry_SYSCALL_64_fastpath+0x1f/0xbe
>
> -> #0 (&(&ip->i_mmaplock)->mr_lock){++++}:
>        up_write+0x1c/0x40
>        xfs_iunlock+0x1d0/0x310 [xfs]
>        xfs_file_fallocate+0x8a/0x310 [xfs]
>        loop_queue_work+0xb7/0x8d0
>        kthread_worker_fn+0xb9/0x1f0
>
> Chain exists of:
>   &(&ip->i_mmaplock)->mr_lock --> &xfs_nondir_ilock_class --> (complete)&ret.event
>
>  Possible unsafe locking scenario by crosslock:
>
>        CPU0                    CPU1
>        ----                    ----
>   lock(&xfs_nondir_ilock_class);
>   lock((complete)&ret.event);
>                                lock(&(&ip->i_mmaplock)->mr_lock);
>                                unlock((complete)&ret.event);
>
>                *** DEADLOCK ***

The warning is a false positive, caused by the fact that all
wait_for_completion()s in submit_bio_wait() are waiting with the same
lock class.

However, some bios have nothing to do with others, for example, the case
might happen while using loop devices, between bios of an upper device
and a lower device(=loop device).

The safest way to assign different lock classes to different devices is
to do it for each gendisk. In other words, this patch assigns a
lockdep_map per gendisk and uses it when initializing completion in
submit_bio_wait().

Of course, it might be too conservative. But, making it safest for now
and extended by block layer experts later is good, atm.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 block/bio.c           |  4 ++--
 block/genhd.c         | 13 +++++--------
 include/linux/genhd.h | 26 ++++++++++++++++++++++----
 3 files changed, 29 insertions(+), 14 deletions(-)

diff --git a/block/bio.c b/block/bio.c
index 9a63597..0d4d6c0 100644
--- a/block/bio.c
+++ b/block/bio.c
@@ -941,7 +941,7 @@ int submit_bio_wait(struct bio *bio)
 {
 	struct submit_bio_ret ret;
 
-	init_completion(&ret.event);
+	init_completion_with_map(&ret.event, &bio->bi_disk->lockdep_map);
 	bio->bi_private = &ret;
 	bio->bi_end_io = submit_bio_wait_endio;
 	bio->bi_opf |= REQ_SYNC;
@@ -1382,7 +1382,7 @@ struct bio *bio_map_user_iov(struct request_queue *q,
 
 			if (len <= 0)
 				break;
-			
+
 			if (bytes > len)
 				bytes = len;
 
diff --git a/block/genhd.c b/block/genhd.c
index 7f520fa..676c245 100644
--- a/block/genhd.c
+++ b/block/genhd.c
@@ -1304,13 +1304,7 @@ dev_t blk_lookup_devt(const char *name, int partno)
 }
 EXPORT_SYMBOL(blk_lookup_devt);
 
-struct gendisk *alloc_disk(int minors)
-{
-	return alloc_disk_node(minors, NUMA_NO_NODE);
-}
-EXPORT_SYMBOL(alloc_disk);
-
-struct gendisk *alloc_disk_node(int minors, int node_id)
+struct gendisk *__alloc_disk_node(int minors, int node_id, struct lock_class_key *key, const char *lock_name)
 {
 	struct gendisk *disk;
 
@@ -1350,9 +1344,12 @@ struct gendisk *alloc_disk_node(int minors, int node_id)
 		disk_to_dev(disk)->type = &disk_type;
 		device_initialize(disk_to_dev(disk));
 	}
+
+	lockdep_init_map(&disk->lockdep_map, lock_name, key, 0);
+
 	return disk;
 }
-EXPORT_SYMBOL(alloc_disk_node);
+EXPORT_SYMBOL(__alloc_disk_node);
 
 struct kobject *get_disk(struct gendisk *disk)
 {
diff --git a/include/linux/genhd.h b/include/linux/genhd.h
index e619fae..5225efc 100644
--- a/include/linux/genhd.h
+++ b/include/linux/genhd.h
@@ -3,7 +3,7 @@
 
 /*
  * 	genhd.h Copyright (C) 1992 Drew Eckhardt
- *	Generic hard disk header file by  
+ *	Generic hard disk header file by
  * 		Drew Eckhardt
  *
  *		<drew@colorado.edu>
@@ -206,6 +206,9 @@ struct gendisk {
 #endif	/* CONFIG_BLK_DEV_INTEGRITY */
 	int node_id;
 	struct badblocks *bb;
+#ifdef CONFIG_LOCKDEP_COMPLETIONS
+	struct lockdep_map lockdep_map;
+#endif
 };
 
 static inline struct gendisk *part_to_disk(struct hd_struct *part)
@@ -483,7 +486,7 @@ struct bsd_disklabel {
 	__s16	d_type;			/* drive type */
 	__s16	d_subtype;		/* controller/d_type specific */
 	char	d_typename[16];		/* type name, e.g. "eagle" */
-	char	d_packname[16];			/* pack identifier */ 
+	char	d_packname[16];			/* pack identifier */
 	__u32	d_secsize;		/* # of bytes per sector */
 	__u32	d_nsectors;		/* # of data sectors per track */
 	__u32	d_ntracks;		/* # of tracks per cylinder */
@@ -602,8 +605,7 @@ extern struct hd_struct * __must_check add_partition(struct gendisk *disk,
 extern void delete_partition(struct gendisk *, int);
 extern void printk_all_partitions(void);
 
-extern struct gendisk *alloc_disk_node(int minors, int node_id);
-extern struct gendisk *alloc_disk(int minors);
+extern struct gendisk *__alloc_disk_node(int minors, int node_id, struct lock_class_key *key, const char *lock_name);
 extern struct kobject *get_disk(struct gendisk *disk);
 extern void put_disk(struct gendisk *disk);
 extern void blk_register_region(dev_t devt, unsigned long range,
@@ -627,6 +629,22 @@ extern ssize_t part_fail_store(struct device *dev,
 			       const char *buf, size_t count);
 #endif /* CONFIG_FAIL_MAKE_REQUEST */
 
+#ifdef CONFIG_LOCKDEP_COMPLETIONS
+#define alloc_disk_node(m, id) \
+({									\
+	static struct lock_class_key __key;				\
+	const char *__lock_name;					\
+									\
+	__lock_name = "(complete)"#m"("#id")";				\
+									\
+	__alloc_disk_node(m, id, &__key, __lock_name);			\
+})
+#else
+#define alloc_disk_node(m, id)	__alloc_disk_node(m, id, NULL, NULL)
+#endif
+
+#define alloc_disk(m)		alloc_disk_node(m, NUMA_NO_NODE)
+
 static inline int hd_ref_init(struct hd_struct *part)
 {
 	if (percpu_ref_init(&part->ref, __delete_partition, 0,
-- 
1.9.1

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

Re: [RESEND PATCH 3/3] lockdep: Assign a lock_class per gendisk used for wait_for_completion()

[Ingo Molnar]

* Byungchul Park <byungchul.park@lge.com> wrote:

> diff --git a/block/bio.c b/block/bio.c
> index 9a63597..0d4d6c0 100644
> --- a/block/bio.c
> +++ b/block/bio.c
> @@ -941,7 +941,7 @@ int submit_bio_wait(struct bio *bio)
>  {
>  	struct submit_bio_ret ret;
>  
> -	init_completion(&ret.event);
> +	init_completion_with_map(&ret.event, &bio->bi_disk->lockdep_map);
>  	bio->bi_private = &ret;
>  	bio->bi_end_io = submit_bio_wait_endio;
>  	bio->bi_opf |= REQ_SYNC;
> @@ -1382,7 +1382,7 @@ struct bio *bio_map_user_iov(struct request_queue *q,
>  
>  			if (len <= 0)
>  				break;
> -			
> +
>  			if (bytes > len)
>  				bytes = len;
>  

That's a spurious cleanup unrelated to this patch.

> --- a/include/linux/genhd.h
> +++ b/include/linux/genhd.h
> @@ -3,7 +3,7 @@
>  
>  /*
>   * 	genhd.h Copyright (C) 1992 Drew Eckhardt
> - *	Generic hard disk header file by  
> + *	Generic hard disk header file by
>   * 		Drew Eckhardt
>   *
>   *		<drew@colorado.edu>

Ditto.

> @@ -483,7 +486,7 @@ struct bsd_disklabel {
>  	__s16	d_type;			/* drive type */
>  	__s16	d_subtype;		/* controller/d_type specific */
>  	char	d_typename[16];		/* type name, e.g. "eagle" */
> -	char	d_packname[16];			/* pack identifier */ 
> +	char	d_packname[16];			/* pack identifier */
>  	__u32	d_secsize;		/* # of bytes per sector */
>  	__u32	d_nsectors;		/* # of data sectors per track */
>  	__u32	d_ntracks;		/* # of tracks per cylinder */

Ditto.

Thanks,

	Ingo

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

Re: Fix false positive by LOCKDEP_CROSSRELEASE

[Bart Van Assche]

On Wed, 2017-10-18 at 18:38 +0900, Byungchul Park wrote:
> Several false positives were reported, so I tried to fix them.
> 
> It would be appreciated if you tell me if it works as expected, or let
> me know your opinion.

What I have been wondering about is whether the crosslock checking makes
sense from a conceptual point of view. I tried to find documentation for the
crosslock checking in Documentation/locking/lockdep-design.txt but
couldn't find a description of the crosslock checking. Shouldn't it be
documented somewhere what the crosslock checks do and what the theory is
behind these checks?

Bart.

Re: Fix false positive by LOCKDEP_CROSSRELEASE

[Byungchul Park]

On Wed, Oct 18, 2017 at 02:29:56PM +0000, Bart Van Assche wrote:
> On Wed, 2017-10-18 at 18:38 +0900, Byungchul Park wrote:
> > Several false positives were reported, so I tried to fix them.
> > 
> > It would be appreciated if you tell me if it works as expected, or let
> > me know your opinion.
> 
> What I have been wondering about is whether the crosslock checking makes
> sense from a conceptual point of view. I tried to find documentation for the
> crosslock checking in Documentation/locking/lockdep-design.txt but
> couldn't find a description of the crosslock checking. Shouldn't it be
> documented somewhere what the crosslock checks do and what the theory is
> behind these checks?

Documentation/locking/crossrelease.txt would be helpful.

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

Re: [RESEND PATCH 3/3] lockdep: Assign a lock_class per gendisk used for wait_for_completion()

[Byungchul Park]

On Wed, Oct 18, 2017 at 11:59:16AM +0200, Ingo Molnar wrote:
> 
> * Byungchul Park <byungchul.park@lge.com> wrote:
> 
> > diff --git a/block/bio.c b/block/bio.c
> > index 9a63597..0d4d6c0 100644
> > --- a/block/bio.c
> > +++ b/block/bio.c
> > @@ -941,7 +941,7 @@ int submit_bio_wait(struct bio *bio)
> >  {
> >  	struct submit_bio_ret ret;
> >  
> > -	init_completion(&ret.event);
> > +	init_completion_with_map(&ret.event, &bio->bi_disk->lockdep_map);
> >  	bio->bi_private = &ret;
> >  	bio->bi_end_io = submit_bio_wait_endio;
> >  	bio->bi_opf |= REQ_SYNC;
> > @@ -1382,7 +1382,7 @@ struct bio *bio_map_user_iov(struct request_queue *q,
> >  
> >  			if (len <= 0)
> >  				break;
> > -			
> > +
> >  			if (bytes > len)
> >  				bytes = len;
> >  
> 
> That's a spurious cleanup unrelated to this patch.

I will separate it. Thank you.

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

Re: Fix false positive by LOCKDEP_CROSSRELEASE

[Bart Van Assche]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="utf-8", Size: 1242 bytes --]

On Thu, 2017-10-19 at 10:57 +0900, Byungchul Park wrote:
> On Wed, Oct 18, 2017 at 02:29:56PM +0000, Bart Van Assche wrote:
> > On Wed, 2017-10-18 at 18:38 +0900, Byungchul Park wrote:
> > > Several false positives were reported, so I tried to fix them.
> > > 
> > > It would be appreciated if you tell me if it works as expected, or let
> > > me know your opinion.
> > 
> > What I have been wondering about is whether the crosslock checking makes
> > sense from a conceptual point of view. I tried to find documentation for the
> > crosslock checking in Documentation/locking/lockdep-design.txt but
> > couldn't find a description of the crosslock checking. Shouldn't it be
> > documented somewhere what the crosslock checks do and what the theory is
> > behind these checks?
> 
> Documentation/locking/crossrelease.txt would be helpful.

That document is incomplete. It does not mention that although it can be
proven that the traditional lock validation code won't produce false
positives, that the cross-release checks do not have a solid theoretical
foundation and are prone to produce false positive reports.

Bart.N‹§²æìr¸›zǧu©ž²Æ {\b­†éì¹»\x1c®&Þ–)îÆi¢žØ^n‡r¶‰šŽŠÝ¢j$½§$¢¸\x05¢¹¨­è§~Š'.)îÄÃ,yèm¶ŸÿÃ\f%Š{±šj+ƒðèž×¦j)Z†·Ÿ

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Bart Van Assche]

On Wed, 2017-10-18 at 18:38 +0900, Byungchul Park wrote:
> Sometimes, we want to initialize completions with sparate lockdep maps
> to assign lock classes under control. For example, the workqueue code
> manages lockdep maps, as it can classify lockdep maps properly.
> Provided a function for that purpose.
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  include/linux/completion.h | 8 ++++++++
>  1 file changed, 8 insertions(+)
> 
> diff --git a/include/linux/completion.h b/include/linux/completion.h
> index cae5400..182d56e 100644
> --- a/include/linux/completion.h
> +++ b/include/linux/completion.h
> @@ -49,6 +49,13 @@ static inline void complete_release_commit(struct completion *x)
>  	lock_commit_crosslock((struct lockdep_map *)&x->map);
>  }
>  
> +#define init_completion_with_map(x, m)					\
> +do {									\
> +	lockdep_init_map_crosslock((struct lockdep_map *)&(x)->map,	\
> +			(m)->name, (m)->key, 0);				\
> +	__init_completion(x);						\
> +} while (0)

Are there any completion objects for which the cross-release checking is
useful? Are there any wait_for_completion() callers that hold a mutex or
other locking object?

Thanks,

Bart.

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Byungchul Park]

On Thu, Oct 19, 2017 at 11:24:00PM +0000, Bart Van Assche wrote:
> Are there any completion objects for which the cross-release checking is
> useful? Are there any wait_for_completion() callers that hold a mutex or
> other locking object?

Check /proc/lockdep, then you can find all dependencies wrt cross-lock.
I named a lock class of wait_for_completion(), a sting starting with
"(complete)".

For example, in my machine:

console_lock -> (complete)&req.done
cpu_hotplug_lock.rw_sem -> (complete)&st->done_up
cpuhp_state_mutex -> (complete)&st->done_up

and so on.

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

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Thomas Gleixner]

On Thu, 19 Oct 2017, Bart Van Assche wrote:
> On Wed, 2017-10-18 at 18:38 +0900, Byungchul Park wrote:
> > Sometimes, we want to initialize completions with sparate lockdep maps
> > to assign lock classes under control. For example, the workqueue code
> > manages lockdep maps, as it can classify lockdep maps properly.
> > Provided a function for that purpose.
> > 
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  include/linux/completion.h | 8 ++++++++
> >  1 file changed, 8 insertions(+)
> > 
> > diff --git a/include/linux/completion.h b/include/linux/completion.h
> > index cae5400..182d56e 100644
> > --- a/include/linux/completion.h
> > +++ b/include/linux/completion.h
> > @@ -49,6 +49,13 @@ static inline void complete_release_commit(struct completion *x)
> >  	lock_commit_crosslock((struct lockdep_map *)&x->map);
> >  }
> >  
> > +#define init_completion_with_map(x, m)					\
> > +do {									\
> > +	lockdep_init_map_crosslock((struct lockdep_map *)&(x)->map,	\
> > +			(m)->name, (m)->key, 0);				\
> > +	__init_completion(x);						\
> > +} while (0)
> 
> Are there any completion objects for which the cross-release checking is
> useful?

All of them by definition.

> Are there any wait_for_completion() callers that hold a mutex or
> other locking object?

Yes, there are also cross completion dependencies. There have been such
bugs and I expect more to be unearthed.

I really have to ask what your motiviation is to fight the lockdep coverage
of synchronization objects tooth and nail?

Thanks,

	tglx

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

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Bart Van Assche]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="utf-8", Size: 2022 bytes --]

On Fri, 2017-10-20 at 08:34 +0200, Thomas Gleixner wrote:
> On Thu, 19 Oct 2017, Bart Van Assche wrote:
> > Are there any completion objects for which the cross-release checking is
> > useful?
> 
> All of them by definition.

Sorry but I'm not sure that's the best possible answer. In my opinion
avoiding that completion objects have dependencies on other lock objects,
e.g. by avoiding to wait on a completion object while holding a mutex, is a
far superior strategy over adding cross-release checking to completion
objects. The former strategy namely makes it unnecessary to add
cross-release checking to completion objects because that strategy ensures
that these completion objects cannot get involved in a deadlock. The latter
strategy can lead to false positive deadlock reports by the lockdep code,
something none of us wants.

A possible alternative strategy could be to enable cross-release checking
only for those completion objects for which waiting occurs inside a critical
section.

> > Are there any wait_for_completion() callers that hold a mutex or
> > other locking object?
> 
> Yes, there are also cross completion dependencies. There have been such
> bugs and I expect more to be unearthed.
> 
> I really have to ask what your motiviation is to fight the lockdep coverage
> of synchronization objects tooth and nail?

As explained in another e-mail thread, unlike the lock inversion checking
performed by the <= v4.13 lockdep code, cross-release checking is a heuristic
that does not have a sound theoretical basis. The lock validator is an
important tool for kernel developers. It is important that it produces as few
false positives as possible. Since the cross-release checks are enabled
automatically when enabling lockdep, I think it is normal that I, as a kernel
developer, care that the cross-release checks produce as few false positives
as possible.

Bart.N‹§²æìr¸›zǧu©ž²Æ {\b­†éì¹»\x1c®&Þ–)îÆi¢žØ^n‡r¶‰šŽŠÝ¢j$½§$¢¸\x05¢¹¨­è§~Š'.)îÄÃ,yèm¶ŸÿÃ\f%Š{±šj+ƒðèž×¦j)Z†·Ÿ

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Byungchul Park]

On Sat, Oct 21, 2017 at 4:58 AM, Bart Van Assche <Bart.VanAssche@wdc.com> wrote:
> Sorry but I'm not sure that's the best possible answer. In my opinion
> avoiding that completion objects have dependencies on other lock objects,
> e.g. by avoiding to wait on a completion object while holding a mutex, is a
> far superior strategy over adding cross-release checking to completion
> objects. The former strategy namely makes it unnecessary to add
> cross-release checking to completion objects because that strategy ensures
> that these completion objects cannot get involved in a deadlock. The latter

It's true if we force it. But do you think it's possible?

> strategy can lead to false positive deadlock reports by the lockdep code,

What do you think false positives come from? It comes from assigning
lock classes falsely where we should more care, rather than lockdep code
itself. The same is applicable to cross-release.

> something none of us wants.
>
> A possible alternative strategy could be to enable cross-release checking
> only for those completion objects for which waiting occurs inside a critical
> section.

Of course, it already did. Cross-release doesn't consider any waiting
outside of critical sections at all, and it should do.

> As explained in another e-mail thread, unlike the lock inversion checking
> performed by the <= v4.13 lockdep code, cross-release checking is a heuristic
> that does not have a sound theoretical basis. The lock validator is an

It's not heuristic but based on the same theoretical basis as <=4.13
lockdep. I mean, the key basis is:

   1) What causes deadlock
   2) What is a dependency
   3) Build a dependency when identified

> important tool for kernel developers. It is important that it produces as few
> false positives as possible. Since the cross-release checks are enabled
> automatically when enabling lockdep, I think it is normal that I, as a kernel
> developer, care that the cross-release checks produce as few false positives
> as possible.

No doubt. That's why I proposed these patches.

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

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Bart Van Assche]

On Sat, 2017-10-21 at 11:23 +0900, Byungchul Park wrote:
> On Sat, Oct 21, 2017 at 4:58 AM, Bart Van Assche <Bart.VanAssche@wdc.com> wrote:
> > As explained in another e-mail thread, unlike the lock inversion checking
> > performed by the <= v4.13 lockdep code, cross-release checking is a heuristic
> > that does not have a sound theoretical basis. The lock validator is an
> 
> It's not heuristic but based on the same theoretical basis as <=4.13
> lockdep. I mean, the key basis is:
> 
>    1) What causes deadlock
>    2) What is a dependency
>    3) Build a dependency when identified

Sorry but I doubt that that statement is correct. The publication [1] contains
a proof that an algorithm that is closely related to the traditional lockdep
lock inversion detector is able to detect all deadlocks and does not report
false positives for programs that only use mutexes as synchronization objects.
The comment of the authors of that paper for programs that use mutexes,
condition variables and semaphores is as follows: "It is unclear how to extend
the lock-graph-based algorithm in Section 3 to efficiently consider the effects
of condition variables and semaphores. Therefore, when considering all three
synchronization mechanisms, we currently use a naive algorithm that checks each
feasible permutation of the trace for deadlock." In other words, if you have
found an approach for detecting potential deadlocks for programs that use these
three kinds of synchronization objects and that does not report false positives
then that's a breakthrough that's worth publishing in a journal or in the
proceedings of a scientific conference.

Bart.

[1] Agarwal, Rahul, and Scott D. Stoller. "Run-time detection of potential
deadlocks for programs with locks, semaphores, and condition variables." In
Proceedings of the 2006 workshop on Parallel and distributed systems: testing
and debugging, pp. 51-60. ACM, 2006.
(https://pdfs.semanticscholar.org/9324/fc0b5d5cd5e05d551a3e98757122039946a2.pdf).

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Byungchul Park]

On Sun, Oct 22, 2017 at 02:34:56PM +0000, Bart Van Assche wrote:
> On Sat, 2017-10-21 at 11:23 +0900, Byungchul Park wrote:
> > On Sat, Oct 21, 2017 at 4:58 AM, Bart Van Assche <Bart.VanAssche@wdc.com> wrote:
> > > As explained in another e-mail thread, unlike the lock inversion checking
> > > performed by the <= v4.13 lockdep code, cross-release checking is a heuristic
> > > that does not have a sound theoretical basis. The lock validator is an
> > 
> > It's not heuristic but based on the same theoretical basis as <=4.13
> > lockdep. I mean, the key basis is:
> > 
> >    1) What causes deadlock
> >    2) What is a dependency
> >    3) Build a dependency when identified
> 
> Sorry but I doubt that that statement is correct. The publication [1] contains

IMHO, the paper is talking about totally different things wrt
deadlocks by wait_for_event/event, that is, lost events.

Furthermore, it doesn't rely on dependencies itself, but just lock
ordering 'case by case', which is a subset of the more general concept.

> a proof that an algorithm that is closely related to the traditional lockdep
> lock inversion detector is able to detect all deadlocks and does not report

I can admit this.

> false positives for programs that only use mutexes as synchronization objects.

I want to ask you. What makes false positives avoidable in the paper?

> The comment of the authors of that paper for programs that use mutexes,
> condition variables and semaphores is as follows: "It is unclear how to extend
> the lock-graph-based algorithm in Section 3 to efficiently consider the effects
> of condition variables and semaphores. Therefore, when considering all three
> synchronization mechanisms, we currently use a naive algorithm that checks each

Right. The paper seems to use a naive algorigm for that cases, not
replying on dependencies, which they should.

> feasible permutation of the trace for deadlock." In other words, if you have
> found an approach for detecting potential deadlocks for programs that use these
> three kinds of synchronization objects and that does not report false positives
> then that's a breakthrough that's worth publishing in a journal or in the
> proceedings of a scientific conference.

Please, point out logical problems of cross-release than saying it's
impossbile according to the paper. I think you'd better understand how
cross-release works *first*. I'll do my best to help you do.

> Bart.
> 
> [1] Agarwal, Rahul, and Scott D. Stoller. "Run-time detection of potential
> deadlocks for programs with locks, semaphores, and condition variables." In
> Proceedings of the 2006 workshop on Parallel and distributed systems: testing
> and debugging, pp. 51-60. ACM, 2006.
> (https://pdfs.semanticscholar.org/9324/fc0b5d5cd5e05d551a3e98757122039946a2.pdf).

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

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Bart Van Assche]

On Mon, 2017-10-23 at 11:08 +0900, Byungchul Park wrote:
> On Sun, Oct 22, 2017 at 02:34:56PM +0000, Bart Van Assche wrote:
> > On Sat, 2017-10-21 at 11:23 +0900, Byungchul Park wrote:
> > > On Sat, Oct 21, 2017 at 4:58 AM, Bart Van Assche <Bart.VanAssche@wdc.com> wrote:
> > > > As explained in another e-mail thread, unlike the lock inversion checking
> > > > performed by the <= v4.13 lockdep code, cross-release checking is a heuristic
> > > > that does not have a sound theoretical basis. The lock validator is an
> > > 
> > > It's not heuristic but based on the same theoretical basis as <=4.13
> > > lockdep. I mean, the key basis is:
> > > 
> > >    1) What causes deadlock
> > >    2) What is a dependency
> > >    3) Build a dependency when identified
> > 
> > Sorry but I doubt that that statement is correct. The publication [1] contains
> 
> IMHO, the paper is talking about totally different things wrt
> deadlocks by wait_for_event/event, that is, lost events.

Please reread the paper title. The authors of the paper explain that their algorithm
can detect lost events but the most significant contribution of the paper is deadlock
detection.

> > false positives for programs that only use mutexes as synchronization objects.
> 
> I want to ask you. What makes false positives avoidable in the paper?

The algorithm used to detect deadlocks. That algorithm has been explained clearly
in the paper.

> > The comment of the authors of that paper for programs that use mutexes,
> > condition variables and semaphores is as follows: "It is unclear how to extend
> > the lock-graph-based algorithm in Section 3 to efficiently consider the effects
> > of condition variables and semaphores. Therefore, when considering all three
> > synchronization mechanisms, we currently use a naive algorithm that checks each
> > feasible permutation of the trace for deadlock." In other words, if you have
> > found an approach for detecting potential deadlocks for programs that use these
> > three kinds of synchronization objects and that does not report false positives
> > then that's a breakthrough that's worth publishing in a journal or in the
> > proceedings of a scientific conference.
> 
> Please, point out logical problems of cross-release than saying it's
> impossbile according to the paper.

Isn't that the same? If it's impossible to use lock-graphs for detecting deadlocks
in programs that use mutexes, semaphores and condition variables without triggering
false positives that means that every approach that tries to detect deadlocks and
that is based on lock graphs, including cross-release, must report false positives
for certain programs.

Bart.

Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map

[Byungchul Park]

On Wed, Oct 25, 2017 at 07:07:06AM +0000, Bart Van Assche wrote:
> > Please, point out logical problems of cross-release than saying it's
> > impossbile according to the paper.
> 
> Isn't that the same? If it's impossible to use lock-graphs for detecting deadlocks
> in programs that use mutexes, semaphores and condition variables without triggering
> false positives that means that every approach that tries to detect deadlocks and
> that is based on lock graphs, including cross-release, must report false positives
> for certain programs.

Right. That's why I'm currently trying to assign lock classes properly
where false positives were reported. You seems to say there is another
cause of false positives. If yes, please let me know what it is. If you
do with an example, it would be more helpful for me to understand you.

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