[PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[NeilBrown]

This took longer that I had wanted, due to various reasons - sorry.
And I'm now posting it in a merge window, which is not ideal.  I don't
expect it to be included in this merge window and I won't be at all
impatient for review, but I didn't want to delay it further.

Testing found some problems, particularly the need to use
locks_copy_lock in NFS.  And there was a small thinko in there that
effectively removed all the speed gains :-(

But this version:
 - shows excellent scalability with lots of threads on lots of CPUs
   contending on a single file
 - avoids the problems that Bruce found
 - seems to work.

Thanks,
NeilBrown


---

NeilBrown (9):
      fs/locks: rename some lists and pointers.
      fs/locks: split out __locks_wake_up_blocks().
      NFS: use locks_copy_lock() to copy locks.
      fs/locks: allow a lock request to block other requests.
      fs/locks: always delete_block after waiting.
      fs/locks: change all *_conflict() functions to return bool.
      fs/locks: create a tree of dependent requests.
      locks: merge posix_unblock_lock() and locks_delete_block()
      VFS: locks: remove unnecessary white space.


 fs/cifs/file.c                  |    4 -
 fs/lockd/svclock.c              |    2 
 fs/locks.c                      |  231 ++++++++++++++++++++++-----------------
 fs/nfs/nfs4proc.c               |    6 +
 fs/nfsd/nfs4state.c             |    6 +
 include/linux/fs.h              |   11 +-
 include/trace/events/filelock.h |   16 +--
 7 files changed, 153 insertions(+), 123 deletions(-)

--
Signature

[PATCH 1/9] fs/locks: rename some lists and pointers.

[NeilBrown]

struct file lock contains an 'fl_next' pointer which
is used to point to the lock that this request is blocked
waiting for.  So rename it to fl_blocker.

The fl_blocked list_head in an active lock is the head of a list of
blocked requests.  In a request it is a node in that list.
These are two distinct uses, so replace with two list_heads
with different names.
fl_blocked is the head of a list of blocked requests
fl_block is a node on that list.

The two different list_heads are never used at the same time, but that
will change in a future patch.

Note that a tracepoint is changed to report fl_blocker instead
of fl_next.

Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/cifs/file.c                  |    2 +-
 fs/locks.c                      |   38 ++++++++++++++++++++------------------
 include/linux/fs.h              |    7 +++++--
 include/trace/events/filelock.h |   16 ++++++++--------
 4 files changed, 34 insertions(+), 29 deletions(-)

diff --git a/fs/cifs/file.c b/fs/cifs/file.c
index 8d41ca7bfcf1..066ed2e4ba96 100644
--- a/fs/cifs/file.c
+++ b/fs/cifs/file.c
@@ -1092,7 +1092,7 @@ cifs_posix_lock_set(struct file *file, struct file_lock *flock)
 	rc = posix_lock_file(file, flock, NULL);
 	up_write(&cinode->lock_sem);
 	if (rc == FILE_LOCK_DEFERRED) {
-		rc = wait_event_interruptible(flock->fl_wait, !flock->fl_next);
+		rc = wait_event_interruptible(flock->fl_wait, !flock->fl_blocker);
 		if (!rc)
 			goto try_again;
 		posix_unblock_lock(flock);
diff --git a/fs/locks.c b/fs/locks.c
index 2ecb4db8c840..a6c6d601286c 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -189,7 +189,7 @@ static DEFINE_HASHTABLE(blocked_hash, BLOCKED_HASH_BITS);
  * This lock protects the blocked_hash. Generally, if you're accessing it, you
  * want to be holding this lock.
  *
- * In addition, it also protects the fl->fl_block list, and the fl->fl_next
+ * In addition, it also protects the fl->fl_blocked list, and the fl->fl_blocker
  * pointer for file_lock structures that are acting as lock requests (in
  * contrast to those that are acting as records of acquired locks).
  *
@@ -293,6 +293,7 @@ static void locks_init_lock_heads(struct file_lock *fl)
 {
 	INIT_HLIST_NODE(&fl->fl_link);
 	INIT_LIST_HEAD(&fl->fl_list);
+	INIT_LIST_HEAD(&fl->fl_blocked);
 	INIT_LIST_HEAD(&fl->fl_block);
 	init_waitqueue_head(&fl->fl_wait);
 }
@@ -332,6 +333,7 @@ void locks_free_lock(struct file_lock *fl)
 {
 	BUG_ON(waitqueue_active(&fl->fl_wait));
 	BUG_ON(!list_empty(&fl->fl_list));
+	BUG_ON(!list_empty(&fl->fl_blocked));
 	BUG_ON(!list_empty(&fl->fl_block));
 	BUG_ON(!hlist_unhashed(&fl->fl_link));
 
@@ -667,7 +669,7 @@ static void __locks_delete_block(struct file_lock *waiter)
 {
 	locks_delete_global_blocked(waiter);
 	list_del_init(&waiter->fl_block);
-	waiter->fl_next = NULL;
+	waiter->fl_blocker = NULL;
 }
 
 static void locks_delete_block(struct file_lock *waiter)
@@ -683,16 +685,16 @@ static void locks_delete_block(struct file_lock *waiter)
  * it seems like the reasonable thing to do.
  *
  * Must be called with both the flc_lock and blocked_lock_lock held. The
- * fl_block list itself is protected by the blocked_lock_lock, but by ensuring
+ * fl_blocked list itself is protected by the blocked_lock_lock, but by ensuring
  * that the flc_lock is also held on insertions we can avoid taking the
- * blocked_lock_lock in some cases when we see that the fl_block list is empty.
+ * blocked_lock_lock in some cases when we see that the fl_blocked list is empty.
  */
 static void __locks_insert_block(struct file_lock *blocker,
 					struct file_lock *waiter)
 {
 	BUG_ON(!list_empty(&waiter->fl_block));
-	waiter->fl_next = blocker;
-	list_add_tail(&waiter->fl_block, &blocker->fl_block);
+	waiter->fl_blocker = blocker;
+	list_add_tail(&waiter->fl_block, &blocker->fl_blocked);
 	if (IS_POSIX(blocker) && !IS_OFDLCK(blocker))
 		locks_insert_global_blocked(waiter);
 }
@@ -716,18 +718,18 @@ static void locks_wake_up_blocks(struct file_lock *blocker)
 	/*
 	 * Avoid taking global lock if list is empty. This is safe since new
 	 * blocked requests are only added to the list under the flc_lock, and
-	 * the flc_lock is always held here. Note that removal from the fl_block
+	 * the flc_lock is always held here. Note that removal from the fl_blocked
 	 * list does not require the flc_lock, so we must recheck list_empty()
 	 * after acquiring the blocked_lock_lock.
 	 */
-	if (list_empty(&blocker->fl_block))
+	if (list_empty(&blocker->fl_blocked))
 		return;
 
 	spin_lock(&blocked_lock_lock);
-	while (!list_empty(&blocker->fl_block)) {
+	while (!list_empty(&blocker->fl_blocked)) {
 		struct file_lock *waiter;
 
-		waiter = list_first_entry(&blocker->fl_block,
+		waiter = list_first_entry(&blocker->fl_blocked,
 				struct file_lock, fl_block);
 		__locks_delete_block(waiter);
 		if (waiter->fl_lmops && waiter->fl_lmops->lm_notify)
@@ -878,7 +880,7 @@ static struct file_lock *what_owner_is_waiting_for(struct file_lock *block_fl)
 
 	hash_for_each_possible(blocked_hash, fl, fl_link, posix_owner_key(block_fl)) {
 		if (posix_same_owner(fl, block_fl))
-			return fl->fl_next;
+			return fl->fl_blocker;
 	}
 	return NULL;
 }
@@ -1237,7 +1239,7 @@ static int posix_lock_inode_wait(struct inode *inode, struct file_lock *fl)
 		error = posix_lock_inode(inode, fl, NULL);
 		if (error != FILE_LOCK_DEFERRED)
 			break;
-		error = wait_event_interruptible(fl->fl_wait, !fl->fl_next);
+		error = wait_event_interruptible(fl->fl_wait, !fl->fl_blocker);
 		if (!error)
 			continue;
 
@@ -1324,7 +1326,7 @@ int locks_mandatory_area(struct inode *inode, struct file *filp, loff_t start,
 		error = posix_lock_inode(inode, &fl, NULL);
 		if (error != FILE_LOCK_DEFERRED)
 			break;
-		error = wait_event_interruptible(fl.fl_wait, !fl.fl_next);
+		error = wait_event_interruptible(fl.fl_wait, !fl.fl_blocker);
 		if (!error) {
 			/*
 			 * If we've been sleeping someone might have
@@ -1518,7 +1520,7 @@ int __break_lease(struct inode *inode, unsigned int mode, unsigned int type)
 
 	locks_dispose_list(&dispose);
 	error = wait_event_interruptible_timeout(new_fl->fl_wait,
-						!new_fl->fl_next, break_time);
+						!new_fl->fl_blocker, break_time);
 
 	percpu_down_read_preempt_disable(&file_rwsem);
 	spin_lock(&ctx->flc_lock);
@@ -1931,7 +1933,7 @@ static int flock_lock_inode_wait(struct inode *inode, struct file_lock *fl)
 		error = flock_lock_inode(inode, fl);
 		if (error != FILE_LOCK_DEFERRED)
 			break;
-		error = wait_event_interruptible(fl->fl_wait, !fl->fl_next);
+		error = wait_event_interruptible(fl->fl_wait, !fl->fl_blocker);
 		if (!error)
 			continue;
 
@@ -2210,7 +2212,7 @@ static int do_lock_file_wait(struct file *filp, unsigned int cmd,
 		error = vfs_lock_file(filp, cmd, fl, NULL);
 		if (error != FILE_LOCK_DEFERRED)
 			break;
-		error = wait_event_interruptible(fl->fl_wait, !fl->fl_next);
+		error = wait_event_interruptible(fl->fl_wait, !fl->fl_blocker);
 		if (!error)
 			continue;
 
@@ -2581,7 +2583,7 @@ posix_unblock_lock(struct file_lock *waiter)
 	int status = 0;
 
 	spin_lock(&blocked_lock_lock);
-	if (waiter->fl_next)
+	if (waiter->fl_blocker)
 		__locks_delete_block(waiter);
 	else
 		status = -ENOENT;
@@ -2707,7 +2709,7 @@ static int locks_show(struct seq_file *f, void *v)
 
 	lock_get_status(f, fl, iter->li_pos, "");
 
-	list_for_each_entry(bfl, &fl->fl_block, fl_block)
+	list_for_each_entry(bfl, &fl->fl_blocked, fl_block)
 		lock_get_status(f, bfl, iter->li_pos, " ->");
 
 	return 0;
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 897eae8faee1..90c4331a0b2c 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -1025,10 +1025,13 @@ bool opens_in_grace(struct net *);
  * Obviously, the last two criteria only matter for POSIX locks.
  */
 struct file_lock {
-	struct file_lock *fl_next;	/* singly linked list for this inode  */
+	struct file_lock *fl_blocker;	/* The lock, that is blocking us */
 	struct list_head fl_list;	/* link into file_lock_context */
 	struct hlist_node fl_link;	/* node in global lists */
-	struct list_head fl_block;	/* circular list of blocked processes */
+	struct list_head fl_blocked;	/* list of requests with
+					 * ->fl_blocker pointing here */
+	struct list_head fl_block;	/* node in
+					 * ->fl_blocker->fl_blocked */
 	fl_owner_t fl_owner;
 	unsigned int fl_flags;
 	unsigned char fl_type;
diff --git a/include/trace/events/filelock.h b/include/trace/events/filelock.h
index 68b17c116907..fad7befa612d 100644
--- a/include/trace/events/filelock.h
+++ b/include/trace/events/filelock.h
@@ -68,7 +68,7 @@ DECLARE_EVENT_CLASS(filelock_lock,
 		__field(struct file_lock *, fl)
 		__field(unsigned long, i_ino)
 		__field(dev_t, s_dev)
-		__field(struct file_lock *, fl_next)
+		__field(struct file_lock *, fl_blocker)
 		__field(fl_owner_t, fl_owner)
 		__field(unsigned int, fl_pid)
 		__field(unsigned int, fl_flags)
@@ -82,7 +82,7 @@ DECLARE_EVENT_CLASS(filelock_lock,
 		__entry->fl = fl ? fl : NULL;
 		__entry->s_dev = inode->i_sb->s_dev;
 		__entry->i_ino = inode->i_ino;
-		__entry->fl_next = fl ? fl->fl_next : NULL;
+		__entry->fl_blocker = fl ? fl->fl_blocker : NULL;
 		__entry->fl_owner = fl ? fl->fl_owner : NULL;
 		__entry->fl_pid = fl ? fl->fl_pid : 0;
 		__entry->fl_flags = fl ? fl->fl_flags : 0;
@@ -92,9 +92,9 @@ DECLARE_EVENT_CLASS(filelock_lock,
 		__entry->ret = ret;
 	),
 
-	TP_printk("fl=0x%p dev=0x%x:0x%x ino=0x%lx fl_next=0x%p fl_owner=0x%p fl_pid=%u fl_flags=%s fl_type=%s fl_start=%lld fl_end=%lld ret=%d",
+	TP_printk("fl=0x%p dev=0x%x:0x%x ino=0x%lx fl_blocker=0x%p fl_owner=0x%p fl_pid=%u fl_flags=%s fl_type=%s fl_start=%lld fl_end=%lld ret=%d",
 		__entry->fl, MAJOR(__entry->s_dev), MINOR(__entry->s_dev),
-		__entry->i_ino, __entry->fl_next, __entry->fl_owner,
+		__entry->i_ino, __entry->fl_blocker, __entry->fl_owner,
 		__entry->fl_pid, show_fl_flags(__entry->fl_flags),
 		show_fl_type(__entry->fl_type),
 		__entry->fl_start, __entry->fl_end, __entry->ret)
@@ -125,7 +125,7 @@ DECLARE_EVENT_CLASS(filelock_lease,
 		__field(struct file_lock *, fl)
 		__field(unsigned long, i_ino)
 		__field(dev_t, s_dev)
-		__field(struct file_lock *, fl_next)
+		__field(struct file_lock *, fl_blocker)
 		__field(fl_owner_t, fl_owner)
 		__field(unsigned int, fl_flags)
 		__field(unsigned char, fl_type)
@@ -137,7 +137,7 @@ DECLARE_EVENT_CLASS(filelock_lease,
 		__entry->fl = fl ? fl : NULL;
 		__entry->s_dev = inode->i_sb->s_dev;
 		__entry->i_ino = inode->i_ino;
-		__entry->fl_next = fl ? fl->fl_next : NULL;
+		__entry->fl_blocker = fl ? fl->fl_blocker : NULL;
 		__entry->fl_owner = fl ? fl->fl_owner : NULL;
 		__entry->fl_flags = fl ? fl->fl_flags : 0;
 		__entry->fl_type = fl ? fl->fl_type : 0;
@@ -145,9 +145,9 @@ DECLARE_EVENT_CLASS(filelock_lease,
 		__entry->fl_downgrade_time = fl ? fl->fl_downgrade_time : 0;
 	),
 
-	TP_printk("fl=0x%p dev=0x%x:0x%x ino=0x%lx fl_next=0x%p fl_owner=0x%p fl_flags=%s fl_type=%s fl_break_time=%lu fl_downgrade_time=%lu",
+	TP_printk("fl=0x%p dev=0x%x:0x%x ino=0x%lx fl_blocker=0x%p fl_owner=0x%p fl_flags=%s fl_type=%s fl_break_time=%lu fl_downgrade_time=%lu",
 		__entry->fl, MAJOR(__entry->s_dev), MINOR(__entry->s_dev),
-		__entry->i_ino, __entry->fl_next, __entry->fl_owner,
+		__entry->i_ino, __entry->fl_blocker, __entry->fl_owner,
 		show_fl_flags(__entry->fl_flags),
 		show_fl_type(__entry->fl_type),
 		__entry->fl_break_time, __entry->fl_downgrade_time)

[PATCH 2/9] fs/locks: split out __locks_wake_up_blocks().

[NeilBrown]

This functionality will be useful in future patches, so
split it out from locks_wake_up_blocks().

Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/locks.c |   27 ++++++++++++++++-----------
 1 file changed, 16 insertions(+), 11 deletions(-)

diff --git a/fs/locks.c b/fs/locks.c
index a6c6d601286c..b8f33792a0a6 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -672,6 +672,21 @@ static void __locks_delete_block(struct file_lock *waiter)
 	waiter->fl_blocker = NULL;
 }
 
+static void __locks_wake_up_blocks(struct file_lock *blocker)
+{
+	while (!list_empty(&blocker->fl_blocked)) {
+		struct file_lock *waiter;
+
+		waiter = list_first_entry(&blocker->fl_blocked,
+					  struct file_lock, fl_block);
+		__locks_delete_block(waiter);
+		if (waiter->fl_lmops && waiter->fl_lmops->lm_notify)
+			waiter->fl_lmops->lm_notify(waiter);
+		else
+			wake_up(&waiter->fl_wait);
+	}
+}
+
 static void locks_delete_block(struct file_lock *waiter)
 {
 	spin_lock(&blocked_lock_lock);
@@ -726,17 +741,7 @@ static void locks_wake_up_blocks(struct file_lock *blocker)
 		return;
 
 	spin_lock(&blocked_lock_lock);
-	while (!list_empty(&blocker->fl_blocked)) {
-		struct file_lock *waiter;
-
-		waiter = list_first_entry(&blocker->fl_blocked,
-				struct file_lock, fl_block);
-		__locks_delete_block(waiter);
-		if (waiter->fl_lmops && waiter->fl_lmops->lm_notify)
-			waiter->fl_lmops->lm_notify(waiter);
-		else
-			wake_up(&waiter->fl_wait);
-	}
+	__locks_wake_up_blocks(blocker);
 	spin_unlock(&blocked_lock_lock);
 }
 

[PATCH 3/9] NFS: use locks_copy_lock() to copy locks.

[NeilBrown]

Using memcpy() to copy lock requests leave the various
list_head in an inconsistent state.
As we will soon attach a list of conflicting request to
another pending request, we need these lists to be consistent.
So change NFS to use locks_init_lock/locks_copy_lock instead
of memcpy.

Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/nfs/nfs4proc.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/fs/nfs/nfs4proc.c b/fs/nfs/nfs4proc.c
index 8220a168282e..cd5a431c6583 100644
--- a/fs/nfs/nfs4proc.c
+++ b/fs/nfs/nfs4proc.c
@@ -6284,7 +6284,8 @@ static struct nfs4_unlockdata *nfs4_alloc_unlockdata(struct file_lock *fl,
 	/* Ensure we don't close file until we're done freeing locks! */
 	p->ctx = get_nfs_open_context(ctx);
 	p->l_ctx = nfs_get_lock_context(ctx);
-	memcpy(&p->fl, fl, sizeof(p->fl));
+	locks_init_lock(&p->fl);
+	locks_copy_lock(&p->fl, fl);
 	p->server = NFS_SERVER(inode);
 	return p;
 }
@@ -6506,7 +6507,8 @@ static struct nfs4_lockdata *nfs4_alloc_lockdata(struct file_lock *fl,
 	p->server = server;
 	refcount_inc(&lsp->ls_count);
 	p->ctx = get_nfs_open_context(ctx);
-	memcpy(&p->fl, fl, sizeof(p->fl));
+	locks_init_lock(&p->fl);
+	locks_copy_lock(&p->fl, fl);
 	return p;
 out_free_seqid:
 	nfs_free_seqid(p->arg.open_seqid);

[PATCH 4/9] fs/locks: allow a lock request to block other requests.

[NeilBrown]

Currently, a lock can block pending requests, but all pending
requests are equal.  If lots of pending requests are
mutually exclusive, this means they will all be woken up
and all but one will fail.  This can hurt performance.

So we will allow pending requests to block other requests.
Only the first request will be woken, and it will wake the others.

This patch doesn't implement this fully, but prepares the way.

- It acknowledges that a request might be blocking other requests,
  and when the request is converted to a lock, those blocked
  requests are moved across.
- When a request is requeued or discarded, all blocked requests are
  woken.
- When deadlock-detection looks for the lock which blocks a
  given request, we follow the chain of ->fl_blocker all
  the way to the top.

Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/locks.c |   36 ++++++++++++++++++++++++++++++------
 1 file changed, 30 insertions(+), 6 deletions(-)

diff --git a/fs/locks.c b/fs/locks.c
index b8f33792a0a6..d362e84a7176 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -402,6 +402,17 @@ void locks_copy_lock(struct file_lock *new, struct file_lock *fl)
 
 EXPORT_SYMBOL(locks_copy_lock);
 
+static void locks_move_blocks(struct file_lock *new, struct file_lock *fl)
+{
+	struct file_lock *f;
+
+	spin_lock(&blocked_lock_lock);
+	list_splice_init(&fl->fl_blocked, &new->fl_blocked);
+	list_for_each_entry(f, &fl->fl_blocked, fl_block)
+		f->fl_blocker = new;
+	spin_unlock(&blocked_lock_lock);
+}
+
 static inline int flock_translate_cmd(int cmd) {
 	if (cmd & LOCK_MAND)
 		return cmd & (LOCK_MAND | LOCK_RW);
@@ -690,6 +701,7 @@ static void __locks_wake_up_blocks(struct file_lock *blocker)
 static void locks_delete_block(struct file_lock *waiter)
 {
 	spin_lock(&blocked_lock_lock);
+	__locks_wake_up_blocks(waiter);
 	__locks_delete_block(waiter);
 	spin_unlock(&blocked_lock_lock);
 }
@@ -712,6 +724,12 @@ static void __locks_insert_block(struct file_lock *blocker,
 	list_add_tail(&waiter->fl_block, &blocker->fl_blocked);
 	if (IS_POSIX(blocker) && !IS_OFDLCK(blocker))
 		locks_insert_global_blocked(waiter);
+
+	/* The requests in waiter->fl_blocked are known to conflict with
+	 * waiter, but might not conflict with blocker, or the requests
+	 * and lock which block it.  So they all need to be woken.
+	 */
+	__locks_wake_up_blocks(waiter);
 }
 
 /* Must be called with flc_lock held. */
@@ -884,8 +902,11 @@ static struct file_lock *what_owner_is_waiting_for(struct file_lock *block_fl)
 	struct file_lock *fl;
 
 	hash_for_each_possible(blocked_hash, fl, fl_link, posix_owner_key(block_fl)) {
-		if (posix_same_owner(fl, block_fl))
-			return fl->fl_blocker;
+		if (posix_same_owner(fl, block_fl)) {
+			while (fl->fl_blocker)
+				fl = fl->fl_blocker;
+			return fl;
+		}
 	}
 	return NULL;
 }
@@ -978,6 +999,7 @@ static int flock_lock_inode(struct inode *inode, struct file_lock *request)
 	if (request->fl_flags & FL_ACCESS)
 		goto out;
 	locks_copy_lock(new_fl, request);
+	locks_move_blocks(new_fl, request);
 	locks_insert_lock_ctx(new_fl, &ctx->flc_flock);
 	new_fl = NULL;
 	error = 0;
@@ -1171,6 +1193,7 @@ static int posix_lock_inode(struct inode *inode, struct file_lock *request,
 			goto out;
 		}
 		locks_copy_lock(new_fl, request);
+		locks_move_blocks(new_fl, request);
 		locks_insert_lock_ctx(new_fl, &fl->fl_list);
 		fl = new_fl;
 		new_fl = NULL;
@@ -2585,13 +2608,14 @@ void locks_remove_file(struct file *filp)
 int
 posix_unblock_lock(struct file_lock *waiter)
 {
-	int status = 0;
+	int status = -ENOENT;
 
 	spin_lock(&blocked_lock_lock);
-	if (waiter->fl_blocker)
+	if (waiter->fl_blocker) {
+		__locks_wake_up_blocks(waiter);
 		__locks_delete_block(waiter);
-	else
-		status = -ENOENT;
+		status = 0;
+	}
 	spin_unlock(&blocked_lock_lock);
 	return status;
 }

[PATCH 5/9] fs/locks: always delete_block after waiting.

[NeilBrown]

Now that requests can block other requests, we
need to be careful to always clean up those blocked
requests.
Any time that we wait for a request, we might have
other requests attached, and when we stop waiting,
we must clean them up.
If the lock was granted, the requests might have been
moved to the new lock, though when merged with a
pre-exiting lock, this might not happen.
In all cases we don't want blocked locks to remain
attached, so we remove them to be safe.

Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/locks.c |   24 +++++++++---------------
 1 file changed, 9 insertions(+), 15 deletions(-)

diff --git a/fs/locks.c b/fs/locks.c
index d362e84a7176..e2ad0a7986c5 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -1268,12 +1268,10 @@ static int posix_lock_inode_wait(struct inode *inode, struct file_lock *fl)
 		if (error != FILE_LOCK_DEFERRED)
 			break;
 		error = wait_event_interruptible(fl->fl_wait, !fl->fl_blocker);
-		if (!error)
-			continue;
-
-		locks_delete_block(fl);
-		break;
+		if (error)
+			break;
 	}
+	locks_delete_block(fl);
 	return error;
 }
 
@@ -1962,12 +1960,10 @@ static int flock_lock_inode_wait(struct inode *inode, struct file_lock *fl)
 		if (error != FILE_LOCK_DEFERRED)
 			break;
 		error = wait_event_interruptible(fl->fl_wait, !fl->fl_blocker);
-		if (!error)
-			continue;
-
-		locks_delete_block(fl);
-		break;
+		if (error)
+			break;
 	}
+	locks_delete_block(fl);
 	return error;
 }
 
@@ -2241,12 +2237,10 @@ static int do_lock_file_wait(struct file *filp, unsigned int cmd,
 		if (error != FILE_LOCK_DEFERRED)
 			break;
 		error = wait_event_interruptible(fl->fl_wait, !fl->fl_blocker);
-		if (!error)
-			continue;
-
-		locks_delete_block(fl);
-		break;
+		if (error)
+			break;
 	}
+	locks_delete_block(fl);
 
 	return error;
 }

[PATCH 6/9] fs/locks: change all *_conflict() functions to return bool.

[NeilBrown]

posix_locks_conflict() and flock_locks_conflict() both return int.
leases_conflict() returns bool.

This inconsistency will cause problems for the next patch if not
fixed.

So change posix_locks_conflict() and flock_locks_conflict() to return
bool.
Also change the locks_conflict() helper.

And convert some
   return (foo);
to
   return foo;

Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/locks.c |   27 +++++++++++++++------------
 1 file changed, 15 insertions(+), 12 deletions(-)

diff --git a/fs/locks.c b/fs/locks.c
index e2ad0a7986c5..1e2a122c9673 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -791,47 +791,50 @@ locks_delete_lock_ctx(struct file_lock *fl, struct list_head *dispose)
 /* Determine if lock sys_fl blocks lock caller_fl. Common functionality
  * checks for shared/exclusive status of overlapping locks.
  */
-static int locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
+static bool locks_conflict(struct file_lock *caller_fl,
+			   struct file_lock *sys_fl)
 {
 	if (sys_fl->fl_type == F_WRLCK)
-		return 1;
+		return true;
 	if (caller_fl->fl_type == F_WRLCK)
-		return 1;
-	return 0;
+		return true;
+	return false;
 }
 
 /* Determine if lock sys_fl blocks lock caller_fl. POSIX specific
  * checking before calling the locks_conflict().
  */
-static int posix_locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
+static bool posix_locks_conflict(struct file_lock *caller_fl,
+				 struct file_lock *sys_fl)
 {
 	/* POSIX locks owned by the same process do not conflict with
 	 * each other.
 	 */
 	if (posix_same_owner(caller_fl, sys_fl))
-		return (0);
+		return false;
 
 	/* Check whether they overlap */
 	if (!locks_overlap(caller_fl, sys_fl))
-		return 0;
+		return false;
 
-	return (locks_conflict(caller_fl, sys_fl));
+	return locks_conflict(caller_fl, sys_fl);
 }
 
 /* Determine if lock sys_fl blocks lock caller_fl. FLOCK specific
  * checking before calling the locks_conflict().
  */
-static int flock_locks_conflict(struct file_lock *caller_fl, struct file_lock *sys_fl)
+static bool flock_locks_conflict(struct file_lock *caller_fl,
+				 struct file_lock *sys_fl)
 {
 	/* FLOCK locks referring to the same filp do not conflict with
 	 * each other.
 	 */
 	if (caller_fl->fl_file == sys_fl->fl_file)
-		return (0);
+		return false;
 	if ((caller_fl->fl_type & LOCK_MAND) || (sys_fl->fl_type & LOCK_MAND))
-		return 0;
+		return false;
 
-	return (locks_conflict(caller_fl, sys_fl));
+	return locks_conflict(caller_fl, sys_fl);
 }
 
 void

[PATCH 7/9] fs/locks: create a tree of dependent requests.

[NeilBrown]

When we find an existing lock which conflicts with a request,
and the request wants to wait, we currently add the request
to a list.  When the lock is removed, the whole list is woken.
This can cause the thundering-herd problem.
To reduce the problem, we make use of the (new) fact that
a pending request can itself have a list of blocked requests.
When we find a conflict, we look through the existing blocked requests.
If any one of them blocks the new request, the new request is attached
below that request, otherwise it is added to the list of blocked
requests, which are now known to be mutually non-conflicting.

This way, when the lock is released, only a set of non-conflicting
locks will be woken, the rest can stay asleep.
If the lock request cannot be granted and the request needs to be
requeued, all the other requests it blocks will then be woken

Reported-and-tested-by: Martin Wilck <mwilck@suse.de>
Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/locks.c |   29 +++++++++++++++++++++++------
 1 file changed, 23 insertions(+), 6 deletions(-)

diff --git a/fs/locks.c b/fs/locks.c
index 1e2a122c9673..06e9ae1cc0c4 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -715,11 +715,25 @@ static void locks_delete_block(struct file_lock *waiter)
  * fl_blocked list itself is protected by the blocked_lock_lock, but by ensuring
  * that the flc_lock is also held on insertions we can avoid taking the
  * blocked_lock_lock in some cases when we see that the fl_blocked list is empty.
+ *
+ * Rather than just adding to the list, we check for conflicts with any existing
+ * waiters, and add beneath any waiter that blocks the new waiter.
+ * Thus wakeups don't happen until needed.
  */
 static void __locks_insert_block(struct file_lock *blocker,
-					struct file_lock *waiter)
+				 struct file_lock *waiter,
+				 bool conflict(struct file_lock *,
+					       struct file_lock *))
 {
+	struct file_lock *fl;
 	BUG_ON(!list_empty(&waiter->fl_block));
+
+new_blocker:
+	list_for_each_entry(fl, &blocker->fl_blocked, fl_block)
+		if (conflict(fl, waiter)) {
+			blocker =  fl;
+			goto new_blocker;
+		}
 	waiter->fl_blocker = blocker;
 	list_add_tail(&waiter->fl_block, &blocker->fl_blocked);
 	if (IS_POSIX(blocker) && !IS_OFDLCK(blocker))
@@ -734,10 +748,12 @@ static void __locks_insert_block(struct file_lock *blocker,
 
 /* Must be called with flc_lock held. */
 static void locks_insert_block(struct file_lock *blocker,
-					struct file_lock *waiter)
+			       struct file_lock *waiter,
+			       bool conflict(struct file_lock *,
+					     struct file_lock *))
 {
 	spin_lock(&blocked_lock_lock);
-	__locks_insert_block(blocker, waiter);
+	__locks_insert_block(blocker, waiter, conflict);
 	spin_unlock(&blocked_lock_lock);
 }
 
@@ -996,7 +1012,7 @@ static int flock_lock_inode(struct inode *inode, struct file_lock *request)
 		if (!(request->fl_flags & FL_SLEEP))
 			goto out;
 		error = FILE_LOCK_DEFERRED;
-		locks_insert_block(fl, request);
+		locks_insert_block(fl, request, flock_locks_conflict);
 		goto out;
 	}
 	if (request->fl_flags & FL_ACCESS)
@@ -1071,7 +1087,8 @@ static int posix_lock_inode(struct inode *inode, struct file_lock *request,
 			spin_lock(&blocked_lock_lock);
 			if (likely(!posix_locks_deadlock(request, fl))) {
 				error = FILE_LOCK_DEFERRED;
-				__locks_insert_block(fl, request);
+				__locks_insert_block(fl, request,
+						     posix_locks_conflict);
 			}
 			spin_unlock(&blocked_lock_lock);
 			goto out;
@@ -1542,7 +1559,7 @@ int __break_lease(struct inode *inode, unsigned int mode, unsigned int type)
 		break_time -= jiffies;
 	if (break_time == 0)
 		break_time++;
-	locks_insert_block(fl, new_fl);
+	locks_insert_block(fl, new_fl, leases_conflict);
 	trace_break_lease_block(inode, new_fl);
 	spin_unlock(&ctx->flc_lock);
 	percpu_up_read_preempt_enable(&file_rwsem);

[PATCH 8/9] locks: merge posix_unblock_lock() and locks_delete_block()

[NeilBrown]

posix_unblock_lock() is not specific to posix locks, and behaves
nearly identically to locks_delete_block() - the former returning a
status while the later doesn't.

So discard posix_unblock_lock() and use locks_delete_block() instead,
after giving that function an appropriate return value.

Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/cifs/file.c      |    2 +-
 fs/lockd/svclock.c  |    2 +-
 fs/locks.c          |   35 ++++++++++++-----------------------
 fs/nfsd/nfs4state.c |    6 +++---
 include/linux/fs.h  |    4 ++--
 5 files changed, 19 insertions(+), 30 deletions(-)

diff --git a/fs/cifs/file.c b/fs/cifs/file.c
index 066ed2e4ba96..3dcee59d16bc 100644
--- a/fs/cifs/file.c
+++ b/fs/cifs/file.c
@@ -1095,7 +1095,7 @@ cifs_posix_lock_set(struct file *file, struct file_lock *flock)
 		rc = wait_event_interruptible(flock->fl_wait, !flock->fl_blocker);
 		if (!rc)
 			goto try_again;
-		posix_unblock_lock(flock);
+		locks_delete_block(flock);
 	}
 	return rc;
 }
diff --git a/fs/lockd/svclock.c b/fs/lockd/svclock.c
index 74330daeab71..ea719cdd6a36 100644
--- a/fs/lockd/svclock.c
+++ b/fs/lockd/svclock.c
@@ -276,7 +276,7 @@ static int nlmsvc_unlink_block(struct nlm_block *block)
 	dprintk("lockd: unlinking block %p...\n", block);
 
 	/* Remove block from list */
-	status = posix_unblock_lock(&block->b_call->a_args.lock.fl);
+	status = locks_delete_block(&block->b_call->a_args.lock.fl);
 	nlmsvc_remove_block(block);
 	return status;
 }
diff --git a/fs/locks.c b/fs/locks.c
index 06e9ae1cc0c4..6ecbeaaed33e 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -698,13 +698,24 @@ static void __locks_wake_up_blocks(struct file_lock *blocker)
 	}
 }
 
-static void locks_delete_block(struct file_lock *waiter)
+/**
+ *	locks_delete_lock - stop waiting for a file lock
+ *	@waiter: the lock which was waiting
+ *
+ *	lockd/nfsd need to disconnect the lock while working on it.
+ */
+int locks_delete_block(struct file_lock *waiter)
 {
+	int status = -ENOENT;
+
 	spin_lock(&blocked_lock_lock);
+	if (waiter->fl_blocker)
+		status = 0;
 	__locks_wake_up_blocks(waiter);
 	__locks_delete_block(waiter);
 	spin_unlock(&blocked_lock_lock);
 }
+EXPORT_SYMBOL(locks_delete_block);
 
 /* Insert waiter into blocker's block list.
  * We use a circular list so that processes can be easily woken up in
@@ -2613,28 +2624,6 @@ void locks_remove_file(struct file *filp)
 	spin_unlock(&ctx->flc_lock);
 }
 
-/**
- *	posix_unblock_lock - stop waiting for a file lock
- *	@waiter: the lock which was waiting
- *
- *	lockd needs to block waiting for locks.
- */
-int
-posix_unblock_lock(struct file_lock *waiter)
-{
-	int status = -ENOENT;
-
-	spin_lock(&blocked_lock_lock);
-	if (waiter->fl_blocker) {
-		__locks_wake_up_blocks(waiter);
-		__locks_delete_block(waiter);
-		status = 0;
-	}
-	spin_unlock(&blocked_lock_lock);
-	return status;
-}
-EXPORT_SYMBOL(posix_unblock_lock);
-
 /**
  * vfs_cancel_lock - file byte range unblock lock
  * @filp: The file to apply the unblock to
diff --git a/fs/nfsd/nfs4state.c b/fs/nfsd/nfs4state.c
index b0ca0efd2875..5175df0b6646 100644
--- a/fs/nfsd/nfs4state.c
+++ b/fs/nfsd/nfs4state.c
@@ -238,7 +238,7 @@ find_blocked_lock(struct nfs4_lockowner *lo, struct knfsd_fh *fh,
 	}
 	spin_unlock(&nn->blocked_locks_lock);
 	if (found)
-		posix_unblock_lock(&found->nbl_lock);
+		locks_delete_block(&found->nbl_lock);
 	return found;
 }
 
@@ -293,7 +293,7 @@ remove_blocked_locks(struct nfs4_lockowner *lo)
 		nbl = list_first_entry(&reaplist, struct nfsd4_blocked_lock,
 					nbl_lru);
 		list_del_init(&nbl->nbl_lru);
-		posix_unblock_lock(&nbl->nbl_lock);
+		locks_delete_block(&nbl->nbl_lock);
 		free_blocked_lock(nbl);
 	}
 }
@@ -4830,7 +4830,7 @@ nfs4_laundromat(struct nfsd_net *nn)
 		nbl = list_first_entry(&reaplist,
 					struct nfsd4_blocked_lock, nbl_lru);
 		list_del_init(&nbl->nbl_lru);
-		posix_unblock_lock(&nbl->nbl_lock);
+		locks_delete_block(&nbl->nbl_lock);
 		free_blocked_lock(nbl);
 	}
 out:
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 90c4331a0b2c..db02050af0e7 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -1103,7 +1103,7 @@ extern void locks_remove_file(struct file *);
 extern void locks_release_private(struct file_lock *);
 extern void posix_test_lock(struct file *, struct file_lock *);
 extern int posix_lock_file(struct file *, struct file_lock *, struct file_lock *);
-extern int posix_unblock_lock(struct file_lock *);
+extern int locks_delete_block(struct file_lock *);
 extern int vfs_test_lock(struct file *, struct file_lock *);
 extern int vfs_lock_file(struct file *, unsigned int, struct file_lock *, struct file_lock *);
 extern int vfs_cancel_lock(struct file *filp, struct file_lock *fl);
@@ -1193,7 +1193,7 @@ static inline int posix_lock_file(struct file *filp, struct file_lock *fl,
 	return -ENOLCK;
 }
 
-static inline int posix_unblock_lock(struct file_lock *waiter)
+static inline int locks_delete_block(struct file_lock *waiter)
 {
 	return -ENOENT;
 }

[PATCH 9/9] VFS: locks: remove unnecessary white space.

[NeilBrown]

 - spaces before tabs,
 - spaces at the end of lines,
 - multiple blank lines,
 - blank lines before EXPORT_SYMBOL,
can all go.

Signed-off-by: NeilBrown <neilb@suse.com>
---
 fs/locks.c |   33 ++++++++++++---------------------
 1 file changed, 12 insertions(+), 21 deletions(-)

diff --git a/fs/locks.c b/fs/locks.c
index 6ecbeaaed33e..6b9da320d9a0 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -11,11 +11,11 @@
  *
  *  Miscellaneous edits, and a total rewrite of posix_lock_file() code.
  *  Kai Petzke (wpp@marie.physik.tu-berlin.de), 1994
- *  
+ *
  *  Converted file_lock_table to a linked list from an array, which eliminates
  *  the limits on how many active file locks are open.
  *  Chad Page (pageone@netcom.com), November 27, 1994
- * 
+ *
  *  Removed dependency on file descriptors. dup()'ed file descriptors now
  *  get the same locks as the original file descriptors, and a close() on
  *  any file descriptor removes ALL the locks on the file for the current
@@ -41,7 +41,7 @@
  *  with a file pointer (filp). As a result they can be shared by a parent
  *  process and its children after a fork(). They are removed when the last
  *  file descriptor referring to the file pointer is closed (unless explicitly
- *  unlocked). 
+ *  unlocked).
  *
  *  FL_FLOCK locks never deadlock, an existing lock is always removed before
  *  upgrading from shared to exclusive (or vice versa). When this happens
@@ -50,7 +50,7 @@
  *  Andy Walker (andy@lysaker.kvaerner.no), June 09, 1995
  *
  *  Removed some race conditions in flock_lock_file(), marked other possible
- *  races. Just grep for FIXME to see them. 
+ *  races. Just grep for FIXME to see them.
  *  Dmitry Gorodchanin (pgmdsg@ibi.com), February 09, 1996.
  *
  *  Addressed Dmitry's concerns. Deadlock checking no longer recursive.
@@ -359,7 +359,6 @@ void locks_init_lock(struct file_lock *fl)
 	memset(fl, 0, sizeof(struct file_lock));
 	locks_init_lock_heads(fl);
 }
-
 EXPORT_SYMBOL(locks_init_lock);
 
 /*
@@ -399,7 +398,6 @@ void locks_copy_lock(struct file_lock *new, struct file_lock *fl)
 			fl->fl_ops->fl_copy_lock(new, fl);
 	}
 }
-
 EXPORT_SYMBOL(locks_copy_lock);
 
 static void locks_move_blocks(struct file_lock *new, struct file_lock *fl)
@@ -436,7 +434,7 @@ flock_make_lock(struct file *filp, unsigned int cmd)
 
 	if (type < 0)
 		return ERR_PTR(type);
-	
+
 	fl = locks_alloc_lock();
 	if (fl == NULL)
 		return ERR_PTR(-ENOMEM);
@@ -447,7 +445,7 @@ flock_make_lock(struct file *filp, unsigned int cmd)
 	fl->fl_flags = FL_FLOCK;
 	fl->fl_type = type;
 	fl->fl_end = OFFSET_MAX;
-	
+
 	return fl;
 }
 
@@ -1103,8 +1101,8 @@ static int posix_lock_inode(struct inode *inode, struct file_lock *request,
 			}
 			spin_unlock(&blocked_lock_lock);
 			goto out;
-  		}
-  	}
+		}
+	}
 
 	/* If we're just looking for a conflict, we're done. */
 	error = 0;
@@ -1399,7 +1397,6 @@ int locks_mandatory_area(struct inode *inode, struct file *filp, loff_t start,
 
 	return error;
 }
-
 EXPORT_SYMBOL(locks_mandatory_area);
 #endif /* CONFIG_MANDATORY_FILE_LOCKING */
 
@@ -1601,7 +1598,6 @@ int __break_lease(struct inode *inode, unsigned int mode, unsigned int type)
 	locks_free_lock(new_fl);
 	return error;
 }
-
 EXPORT_SYMBOL(__break_lease);
 
 /**
@@ -1632,7 +1628,6 @@ void lease_get_mtime(struct inode *inode, struct timespec64 *time)
 	if (has_lease)
 		*time = current_time(inode);
 }
-
 EXPORT_SYMBOL(lease_get_mtime);
 
 /**
@@ -1687,8 +1682,8 @@ int fcntl_getlease(struct file *filp)
 
 /**
  * check_conflicting_open - see if the given dentry points to a file that has
- * 			    an existing open that would conflict with the
- * 			    desired lease.
+ *			    an existing open that would conflict with the
+ *			    desired lease.
  * @dentry:	dentry to check
  * @arg:	type of lease that we're trying to acquire
  * @flags:	current lock flags
@@ -1912,7 +1907,7 @@ EXPORT_SYMBOL(generic_setlease);
  * @arg:	type of lease to obtain
  * @lease:	file_lock to use when adding a lease
  * @priv:	private info for lm_setup when adding a lease (may be
- * 		NULL if lm_setup doesn't require it)
+ *		NULL if lm_setup doesn't require it)
  *
  * Call this to establish a lease on the file. The "lease" argument is not
  * used for F_UNLCK requests and may be NULL. For commands that set or alter
@@ -2200,7 +2195,7 @@ int fcntl_getlk(struct file *filp, unsigned int cmd, struct flock *flock)
 	error = vfs_test_lock(filp, fl);
 	if (error)
 		goto out;
- 
+
 	flock->l_type = fl->fl_type;
 	if (fl->fl_type != F_UNLCK) {
 		error = posix_lock_to_flock(flock, fl);
@@ -2547,7 +2542,6 @@ void locks_remove_posix(struct file *filp, fl_owner_t owner)
 		lock.fl_ops->fl_release_private(&lock);
 	trace_locks_remove_posix(inode, &lock, error);
 }
-
 EXPORT_SYMBOL(locks_remove_posix);
 
 /* The i_flctx must be valid when calling into here */
@@ -2637,7 +2631,6 @@ int vfs_cancel_lock(struct file *filp, struct file_lock *fl)
 		return filp->f_op->lock(filp, F_CANCELLK, fl);
 	return 0;
 }
-
 EXPORT_SYMBOL_GPL(vfs_cancel_lock);
 
 #ifdef CONFIG_PROC_FS
@@ -2837,7 +2830,6 @@ static int __init filelock_init(void)
 	filelock_cache = kmem_cache_create("file_lock_cache",
 			sizeof(struct file_lock), 0, SLAB_PANIC, NULL);
 
-
 	for_each_possible_cpu(i) {
 		struct file_lock_list_struct *fll = per_cpu_ptr(&file_lock_list, i);
 
@@ -2847,5 +2839,4 @@ static int __init filelock_init(void)
 
 	return 0;
 }
-
 core_initcall(filelock_init);

Re: [PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[J. Bruce Fields]

On Wed, Oct 24, 2018 at 09:43:54AM +1100, NeilBrown wrote:
> This took longer that I had wanted, due to various reasons - sorry.
> And I'm now posting it in a merge window, which is not ideal.  I don't
> expect it to be included in this merge window and I won't be at all
> impatient for review, but I didn't want to delay it further.

Yes, apologies, I've been looking forward to finding out how this turned
out, but I'd like to track down a bug or two and also review Olga's copy
patches....  Bug me if I haven't gotten to this in a week or two.

I'd also be really interested in any details of the performance
experiments that you could share.

--b.

> 
> Testing found some problems, particularly the need to use
> locks_copy_lock in NFS.  And there was a small thinko in there that
> effectively removed all the speed gains :-(
> 
> But this version:
>  - shows excellent scalability with lots of threads on lots of CPUs
>    contending on a single file
>  - avoids the problems that Bruce found
>  - seems to work.
> 
> Thanks,
> NeilBrown
> 
> 
> ---
> 
> NeilBrown (9):
>       fs/locks: rename some lists and pointers.
>       fs/locks: split out __locks_wake_up_blocks().
>       NFS: use locks_copy_lock() to copy locks.
>       fs/locks: allow a lock request to block other requests.
>       fs/locks: always delete_block after waiting.
>       fs/locks: change all *_conflict() functions to return bool.
>       fs/locks: create a tree of dependent requests.
>       locks: merge posix_unblock_lock() and locks_delete_block()
>       VFS: locks: remove unnecessary white space.
> 
> 
>  fs/cifs/file.c                  |    4 -
>  fs/lockd/svclock.c              |    2 
>  fs/locks.c                      |  231 ++++++++++++++++++++++-----------------
>  fs/nfs/nfs4proc.c               |    6 +
>  fs/nfsd/nfs4state.c             |    6 +
>  include/linux/fs.h              |   11 +-
>  include/trace/events/filelock.h |   16 +--
>  7 files changed, 153 insertions(+), 123 deletions(-)
> 
> --
> Signature

Re: [PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[Martin Wilck]

On Thu, 2018-10-25 at 12:04 -0400, J. Bruce Fields wrote:
> On Wed, Oct 24, 2018 at 09:43:54AM +1100, NeilBrown wrote:
> > This took longer that I had wanted, due to various reasons - sorry.
> > And I'm now posting it in a merge window, which is not ideal.  I
> > don't
> > expect it to be included in this merge window and I won't be at all
> > impatient for review, but I didn't want to delay it further.
> 
> Yes, apologies, I've been looking forward to finding out how this
> turned
> out, but I'd like to track down a bug or two and also review Olga's
> copy
> patches....  Bug me if I haven't gotten to this in a week or two.
> 
> I'd also be really interested in any details of the performance
> experiments that you could share.

I pushed my test code to https://github.com/mwilck/lockscale.

Cheers,
Martin

Re: [PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[Jeff Layton]

On Wed, 2018-10-24 at 09:43 +1100, NeilBrown wrote:
> This took longer that I had wanted, due to various reasons - sorry.
> And I'm now posting it in a merge window, which is not ideal.  I don't
> expect it to be included in this merge window and I won't be at all
> impatient for review, but I didn't want to delay it further.
> 
> Testing found some problems, particularly the need to use
> locks_copy_lock in NFS.  And there was a small thinko in there that
> effectively removed all the speed gains :-(
> 
> But this version:
>  - shows excellent scalability with lots of threads on lots of CPUs
>    contending on a single file
>  - avoids the problems that Bruce found
>  - seems to work.
> 
> Thanks,
> NeilBrown
> 
> 
> ---
> 
> NeilBrown (9):
>       fs/locks: rename some lists and pointers.
>       fs/locks: split out __locks_wake_up_blocks().
>       NFS: use locks_copy_lock() to copy locks.
>       fs/locks: allow a lock request to block other requests.
>       fs/locks: always delete_block after waiting.
>       fs/locks: change all *_conflict() functions to return bool.
>       fs/locks: create a tree of dependent requests.
>       locks: merge posix_unblock_lock() and locks_delete_block()
>       VFS: locks: remove unnecessary white space.
> 
> 
>  fs/cifs/file.c                  |    4 -
>  fs/lockd/svclock.c              |    2 
>  fs/locks.c                      |  231 ++++++++++++++++++++++-----------------
>  fs/nfs/nfs4proc.c               |    6 +
>  fs/nfsd/nfs4state.c             |    6 +
>  include/linux/fs.h              |   11 +-
>  include/trace/events/filelock.h |   16 +--
>  7 files changed, 153 insertions(+), 123 deletions(-)
> 
> --
> Signature
> 


I built a kernel with these patches and ran the cthon04 lock tests and
got this on lock test 1 after a long hang (the test passed though):

[ 1694.787367] BUG: unable to handle kernel NULL pointer dereference at 000000000000002c
[ 1694.789546] PGD 118ff0067 P4D 118ff0067 PUD 135915067 PMD 0 
[ 1694.790772] Oops: 0000 [#1] SMP NOPTI
[ 1694.791749] CPU: 7 PID: 1514 Comm: tlocklfs Not tainted 4.19.0+ #56
[ 1694.792876] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20180531_142017-buildhw-08.phx2.fedoraproject.org-1.fc28 04/01/2014
[ 1694.795179] RIP: 0010:__locks_delete_block+0x14/0x90
[ 1694.796203] Code: 01 a1 e9 9f 4f d8 ff 0f 1f 44 00 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 29 9d 58 01 55 53 48 89 fb 85 c0 75 5a <48> 8b 43 20 48 85 c0 74 20 48 8b 53 18 48 89 10 48 85 d2 74 04 48
[ 1694.799277] RSP: 0018:ffff9d21c1f63cb8 EFLAGS: 00010202
[ 1694.800374] RAX: 0000000000000001 RBX: 000000000000000c RCX: aaaaaaaaaaaaaaad
[ 1694.801682] RDX: 0000000000000001 RSI: ffffffff9f7b0c38 RDI: 0000000000000246
[ 1694.802996] RBP: 000000000000000c R08: 0000000000000000 R09: 0000000000000001
[ 1694.804317] R10: 0000000000000001 R11: ffffffffa0bdc188 R12: ffff9d21c1f63dd8
[ 1694.805633] R13: ffff9d21c1f63e00 R14: ffffffff9f3241a8 R15: ffff8d0b5aef72e0
[ 1694.806941] FS:  00007efc8699c740(0000) GS:ffff8d0b7ba00000(0000) knlGS:0000000000000000
[ 1694.808380] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 1694.809550] CR2: 000000000000002c CR3: 000000011e0d8000 CR4: 00000000000006e0
[ 1694.810888] Call Trace:
[ 1694.811692]  __locks_wake_up_blocks+0x2d/0x80
[ 1694.812713]  locks_delete_block+0x1d/0x40
[ 1694.813691]  locks_lock_inode_wait+0x9c/0x1c0
[ 1694.814731]  nfs4_proc_lock+0x120/0x440 [nfsv4]
[ 1694.815786]  ? nfs_put_lock_context+0x25/0x80 [nfs]
[ 1694.816866]  ? do_unlk+0x98/0xe0 [nfs]
[ 1694.817818]  locks_remove_posix+0xba/0x1d0
[ 1694.818811]  ? _cond_resched+0x15/0x30
[ 1694.819768]  ? wait_on_commit+0x38/0xb0 [nfs]
[ 1694.820787]  ? process_echoes+0x60/0x60
[ 1694.821752]  ? __nfs_commit_inode+0xc2/0x1c0 [nfs]
[ 1694.822819]  filp_close+0x56/0x70
[ 1694.823712]  __x64_sys_close+0x1e/0x50
[ 1694.824661]  do_syscall_64+0x60/0x1f0
[ 1694.825599]  entry_SYSCALL_64_after_hwframe+0x49/0xbe
[ 1694.826731] RIP: 0033:0x7efc8616c0a4
[ 1694.827673] Code: eb 89 e8 af f6 01 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 aa e7 2c 00 48 63 ff 85 c0 75 13 b8 03 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 44 f3 c3 66 90 48 83 ec 18 48 89 7c 24 08 e8
[ 1694.830929] RSP: 002b:00007ffc70beb7b8 EFLAGS: 00000246 ORIG_RAX: 0000000000000003
[ 1694.832371] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007efc8616c0a4
[ 1694.833784] RDX: 0000000000000000 RSI: 00007efc864378a0 RDI: 0000000000000009
[ 1694.835183] RBP: 00007ffc70beb7d0 R08: 00007efc864378a0 R09: 00007efc8699c740
[ 1694.836560] R10: 00000000000006b4 R11: 0000000000000246 R12: 0000000000401000
[ 1694.837941] R13: 00007ffc70beb990 R14: 0000000000000000 R15: 0000000000000000
[ 1694.839322] Modules linked in: rpcsec_gss_krb5 nfsv4 dns_resolver nfs fscache nfsd auth_rpcgss nfs_acl lockd grace ip6t_rpfilter ip6t_REJECT nf_reject_ipv6 xt_conntrack ip_set nfnetlink ebtable_nat ebtable_broute bridge stp llc ip6table_nat nf_nat_ipv6 ip6table_mangle ip6table_raw ip6table_security iptable_nat nf_nat_ipv4 nf_nat nf_conntrack nf_defrag_ipv6 nf_defrag_ipv4 iptable_mangle iptable_raw iptable_security ebtable_filter ebtables ip6table_filter ip6_tables sunrpc joydev virtio_balloon i2c_piix4 pcspkr edac_mce_amd xfs libcrc32c serio_raw virtio_blk qxl drm_kms_helper virtio_net ttm net_failover virtio_console failover drm ata_generic pata_acpi floppy qemu_fw_cfg
[ 1694.849736] CR2: 000000000000002c
[ 1694.850813] ---[ end trace da2f469c62deb564 ]---

-- 
Jeff Layton <jlayton@kernel.org>

Re: [PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 6038 bytes --]

On Fri, Oct 26 2018, Jeff Layton wrote:

> On Wed, 2018-10-24 at 09:43 +1100, NeilBrown wrote:
>> This took longer that I had wanted, due to various reasons - sorry.
>> And I'm now posting it in a merge window, which is not ideal.  I don't
>> expect it to be included in this merge window and I won't be at all
>> impatient for review, but I didn't want to delay it further.
>> 
>> Testing found some problems, particularly the need to use
>> locks_copy_lock in NFS.  And there was a small thinko in there that
>> effectively removed all the speed gains :-(
>> 
>> But this version:
>>  - shows excellent scalability with lots of threads on lots of CPUs
>>    contending on a single file
>>  - avoids the problems that Bruce found
>>  - seems to work.
>> 
>> Thanks,
>> NeilBrown
>> 
>> 
>> ---
>> 
>> NeilBrown (9):
>>       fs/locks: rename some lists and pointers.
>>       fs/locks: split out __locks_wake_up_blocks().
>>       NFS: use locks_copy_lock() to copy locks.
>>       fs/locks: allow a lock request to block other requests.
>>       fs/locks: always delete_block after waiting.
>>       fs/locks: change all *_conflict() functions to return bool.
>>       fs/locks: create a tree of dependent requests.
>>       locks: merge posix_unblock_lock() and locks_delete_block()
>>       VFS: locks: remove unnecessary white space.
>> 
>> 
>>  fs/cifs/file.c                  |    4 -
>>  fs/lockd/svclock.c              |    2 
>>  fs/locks.c                      |  231 ++++++++++++++++++++++-----------------
>>  fs/nfs/nfs4proc.c               |    6 +
>>  fs/nfsd/nfs4state.c             |    6 +
>>  include/linux/fs.h              |   11 +-
>>  include/trace/events/filelock.h |   16 +--
>>  7 files changed, 153 insertions(+), 123 deletions(-)
>> 
>> --
>> Signature
>> 
>
>
> I built a kernel with these patches and ran the cthon04 lock tests and
> got this on lock test 1 after a long hang (the test passed though):

Thanks!

I think locks_remove_posix() needs a call to
  locks_init_lock(&lock);
just like locks_mandatory_area() has.
I cannot immediately see anywhere else it is needed but I should
probably look a bit harder.

Thanks,
NeilBrown


>
> [ 1694.787367] BUG: unable to handle kernel NULL pointer dereference at 000000000000002c
> [ 1694.789546] PGD 118ff0067 P4D 118ff0067 PUD 135915067 PMD 0 
> [ 1694.790772] Oops: 0000 [#1] SMP NOPTI
> [ 1694.791749] CPU: 7 PID: 1514 Comm: tlocklfs Not tainted 4.19.0+ #56
> [ 1694.792876] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20180531_142017-buildhw-08.phx2.fedoraproject.org-1.fc28 04/01/2014
> [ 1694.795179] RIP: 0010:__locks_delete_block+0x14/0x90
> [ 1694.796203] Code: 01 a1 e9 9f 4f d8 ff 0f 1f 44 00 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 29 9d 58 01 55 53 48 89 fb 85 c0 75 5a <48> 8b 43 20 48 85 c0 74 20 48 8b 53 18 48 89 10 48 85 d2 74 04 48
> [ 1694.799277] RSP: 0018:ffff9d21c1f63cb8 EFLAGS: 00010202
> [ 1694.800374] RAX: 0000000000000001 RBX: 000000000000000c RCX: aaaaaaaaaaaaaaad
> [ 1694.801682] RDX: 0000000000000001 RSI: ffffffff9f7b0c38 RDI: 0000000000000246
> [ 1694.802996] RBP: 000000000000000c R08: 0000000000000000 R09: 0000000000000001
> [ 1694.804317] R10: 0000000000000001 R11: ffffffffa0bdc188 R12: ffff9d21c1f63dd8
> [ 1694.805633] R13: ffff9d21c1f63e00 R14: ffffffff9f3241a8 R15: ffff8d0b5aef72e0
> [ 1694.806941] FS:  00007efc8699c740(0000) GS:ffff8d0b7ba00000(0000) knlGS:0000000000000000
> [ 1694.808380] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> [ 1694.809550] CR2: 000000000000002c CR3: 000000011e0d8000 CR4: 00000000000006e0
> [ 1694.810888] Call Trace:
> [ 1694.811692]  __locks_wake_up_blocks+0x2d/0x80
> [ 1694.812713]  locks_delete_block+0x1d/0x40
> [ 1694.813691]  locks_lock_inode_wait+0x9c/0x1c0
> [ 1694.814731]  nfs4_proc_lock+0x120/0x440 [nfsv4]
> [ 1694.815786]  ? nfs_put_lock_context+0x25/0x80 [nfs]
> [ 1694.816866]  ? do_unlk+0x98/0xe0 [nfs]
> [ 1694.817818]  locks_remove_posix+0xba/0x1d0
> [ 1694.818811]  ? _cond_resched+0x15/0x30
> [ 1694.819768]  ? wait_on_commit+0x38/0xb0 [nfs]
> [ 1694.820787]  ? process_echoes+0x60/0x60
> [ 1694.821752]  ? __nfs_commit_inode+0xc2/0x1c0 [nfs]
> [ 1694.822819]  filp_close+0x56/0x70
> [ 1694.823712]  __x64_sys_close+0x1e/0x50
> [ 1694.824661]  do_syscall_64+0x60/0x1f0
> [ 1694.825599]  entry_SYSCALL_64_after_hwframe+0x49/0xbe
> [ 1694.826731] RIP: 0033:0x7efc8616c0a4
> [ 1694.827673] Code: eb 89 e8 af f6 01 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 aa e7 2c 00 48 63 ff 85 c0 75 13 b8 03 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 44 f3 c3 66 90 48 83 ec 18 48 89 7c 24 08 e8
> [ 1694.830929] RSP: 002b:00007ffc70beb7b8 EFLAGS: 00000246 ORIG_RAX: 0000000000000003
> [ 1694.832371] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007efc8616c0a4
> [ 1694.833784] RDX: 0000000000000000 RSI: 00007efc864378a0 RDI: 0000000000000009
> [ 1694.835183] RBP: 00007ffc70beb7d0 R08: 00007efc864378a0 R09: 00007efc8699c740
> [ 1694.836560] R10: 00000000000006b4 R11: 0000000000000246 R12: 0000000000401000
> [ 1694.837941] R13: 00007ffc70beb990 R14: 0000000000000000 R15: 0000000000000000
> [ 1694.839322] Modules linked in: rpcsec_gss_krb5 nfsv4 dns_resolver nfs fscache nfsd auth_rpcgss nfs_acl lockd grace ip6t_rpfilter ip6t_REJECT nf_reject_ipv6 xt_conntrack ip_set nfnetlink ebtable_nat ebtable_broute bridge stp llc ip6table_nat nf_nat_ipv6 ip6table_mangle ip6table_raw ip6table_security iptable_nat nf_nat_ipv4 nf_nat nf_conntrack nf_defrag_ipv6 nf_defrag_ipv4 iptable_mangle iptable_raw iptable_security ebtable_filter ebtables ip6table_filter ip6_tables sunrpc joydev virtio_balloon i2c_piix4 pcspkr edac_mce_amd xfs libcrc32c serio_raw virtio_blk qxl drm_kms_helper virtio_net ttm net_failover virtio_console failover drm ata_generic pata_acpi floppy qemu_fw_cfg
> [ 1694.849736] CR2: 000000000000002c
> [ 1694.850813] ---[ end trace da2f469c62deb564 ]---
>
> -- 
> Jeff Layton <jlayton@kernel.org>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[NeilBrown]

[-- Attachment #1: Type: text/plain, Size: 6639 bytes --]

On Fri, Oct 26 2018, Jeff Layton wrote:

> On Wed, 2018-10-24 at 09:43 +1100, NeilBrown wrote:
>> This took longer that I had wanted, due to various reasons - sorry.
>> And I'm now posting it in a merge window, which is not ideal.  I don't
>> expect it to be included in this merge window and I won't be at all
>> impatient for review, but I didn't want to delay it further.
>> 
>> Testing found some problems, particularly the need to use
>> locks_copy_lock in NFS.  And there was a small thinko in there that
>> effectively removed all the speed gains :-(
>> 
>> But this version:
>>  - shows excellent scalability with lots of threads on lots of CPUs
>>    contending on a single file
>>  - avoids the problems that Bruce found
>>  - seems to work.
>> 
>> Thanks,
>> NeilBrown
>> 
>> 
>> ---
>> 
>> NeilBrown (9):
>>       fs/locks: rename some lists and pointers.
>>       fs/locks: split out __locks_wake_up_blocks().
>>       NFS: use locks_copy_lock() to copy locks.
>>       fs/locks: allow a lock request to block other requests.
>>       fs/locks: always delete_block after waiting.
>>       fs/locks: change all *_conflict() functions to return bool.
>>       fs/locks: create a tree of dependent requests.
>>       locks: merge posix_unblock_lock() and locks_delete_block()
>>       VFS: locks: remove unnecessary white space.
>> 
>> 
>>  fs/cifs/file.c                  |    4 -
>>  fs/lockd/svclock.c              |    2 
>>  fs/locks.c                      |  231 ++++++++++++++++++++++-----------------
>>  fs/nfs/nfs4proc.c               |    6 +
>>  fs/nfsd/nfs4state.c             |    6 +
>>  include/linux/fs.h              |   11 +-
>>  include/trace/events/filelock.h |   16 +--
>>  7 files changed, 153 insertions(+), 123 deletions(-)
>> 
>> --
>> Signature
>> 
>
>
> I built a kernel with these patches and ran the cthon04 lock tests and
> got this on lock test 1 after a long hang (the test passed though):

I've been looking deeper into this, and I cannot see how this can
happen.

This is an unlock request, happening when a file is closed.
locks_delete_block() will only be called from locks_lock_inode_wait()
after posix_lock_inode() (or possible flock_lock_inode()) returns
FILE_LOCK_DEFERRED.

But these only return FILE_LOCK_DEFERRED when fl_type != F_UNLCK.
(or possibly if FL_ACCESS and FL_SLEEP are both set - that would be
 weird).

So this shouldn't happen - an unlock request should never result in
locks_delete_block() being called.
But if it can, I'll need to change do_flock() in gfs2/file.c to use a
properly initialized 'struct file_lock', rather than a manifest
constant.  Maybe I should do that anyway.

Any ideas? I'll try running connectathon myself later and see if I can
reproduce it.

Thanks,
NeilBrown

>
> [ 1694.787367] BUG: unable to handle kernel NULL pointer dereference at 000000000000002c
> [ 1694.789546] PGD 118ff0067 P4D 118ff0067 PUD 135915067 PMD 0 
> [ 1694.790772] Oops: 0000 [#1] SMP NOPTI
> [ 1694.791749] CPU: 7 PID: 1514 Comm: tlocklfs Not tainted 4.19.0+ #56
> [ 1694.792876] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20180531_142017-buildhw-08.phx2.fedoraproject.org-1.fc28 04/01/2014
> [ 1694.795179] RIP: 0010:__locks_delete_block+0x14/0x90
> [ 1694.796203] Code: 01 a1 e9 9f 4f d8 ff 0f 1f 44 00 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 29 9d 58 01 55 53 48 89 fb 85 c0 75 5a <48> 8b 43 20 48 85 c0 74 20 48 8b 53 18 48 89 10 48 85 d2 74 04 48
> [ 1694.799277] RSP: 0018:ffff9d21c1f63cb8 EFLAGS: 00010202
> [ 1694.800374] RAX: 0000000000000001 RBX: 000000000000000c RCX: aaaaaaaaaaaaaaad
> [ 1694.801682] RDX: 0000000000000001 RSI: ffffffff9f7b0c38 RDI: 0000000000000246
> [ 1694.802996] RBP: 000000000000000c R08: 0000000000000000 R09: 0000000000000001
> [ 1694.804317] R10: 0000000000000001 R11: ffffffffa0bdc188 R12: ffff9d21c1f63dd8
> [ 1694.805633] R13: ffff9d21c1f63e00 R14: ffffffff9f3241a8 R15: ffff8d0b5aef72e0
> [ 1694.806941] FS:  00007efc8699c740(0000) GS:ffff8d0b7ba00000(0000) knlGS:0000000000000000
> [ 1694.808380] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> [ 1694.809550] CR2: 000000000000002c CR3: 000000011e0d8000 CR4: 00000000000006e0
> [ 1694.810888] Call Trace:
> [ 1694.811692]  __locks_wake_up_blocks+0x2d/0x80
> [ 1694.812713]  locks_delete_block+0x1d/0x40
> [ 1694.813691]  locks_lock_inode_wait+0x9c/0x1c0
> [ 1694.814731]  nfs4_proc_lock+0x120/0x440 [nfsv4]
> [ 1694.815786]  ? nfs_put_lock_context+0x25/0x80 [nfs]
> [ 1694.816866]  ? do_unlk+0x98/0xe0 [nfs]
> [ 1694.817818]  locks_remove_posix+0xba/0x1d0
> [ 1694.818811]  ? _cond_resched+0x15/0x30
> [ 1694.819768]  ? wait_on_commit+0x38/0xb0 [nfs]
> [ 1694.820787]  ? process_echoes+0x60/0x60
> [ 1694.821752]  ? __nfs_commit_inode+0xc2/0x1c0 [nfs]
> [ 1694.822819]  filp_close+0x56/0x70
> [ 1694.823712]  __x64_sys_close+0x1e/0x50
> [ 1694.824661]  do_syscall_64+0x60/0x1f0
> [ 1694.825599]  entry_SYSCALL_64_after_hwframe+0x49/0xbe
> [ 1694.826731] RIP: 0033:0x7efc8616c0a4
> [ 1694.827673] Code: eb 89 e8 af f6 01 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 aa e7 2c 00 48 63 ff 85 c0 75 13 b8 03 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 44 f3 c3 66 90 48 83 ec 18 48 89 7c 24 08 e8
> [ 1694.830929] RSP: 002b:00007ffc70beb7b8 EFLAGS: 00000246 ORIG_RAX: 0000000000000003
> [ 1694.832371] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007efc8616c0a4
> [ 1694.833784] RDX: 0000000000000000 RSI: 00007efc864378a0 RDI: 0000000000000009
> [ 1694.835183] RBP: 00007ffc70beb7d0 R08: 00007efc864378a0 R09: 00007efc8699c740
> [ 1694.836560] R10: 00000000000006b4 R11: 0000000000000246 R12: 0000000000401000
> [ 1694.837941] R13: 00007ffc70beb990 R14: 0000000000000000 R15: 0000000000000000
> [ 1694.839322] Modules linked in: rpcsec_gss_krb5 nfsv4 dns_resolver nfs fscache nfsd auth_rpcgss nfs_acl lockd grace ip6t_rpfilter ip6t_REJECT nf_reject_ipv6 xt_conntrack ip_set nfnetlink ebtable_nat ebtable_broute bridge stp llc ip6table_nat nf_nat_ipv6 ip6table_mangle ip6table_raw ip6table_security iptable_nat nf_nat_ipv4 nf_nat nf_conntrack nf_defrag_ipv6 nf_defrag_ipv4 iptable_mangle iptable_raw iptable_security ebtable_filter ebtables ip6table_filter ip6_tables sunrpc joydev virtio_balloon i2c_piix4 pcspkr edac_mce_amd xfs libcrc32c serio_raw virtio_blk qxl drm_kms_helper virtio_net ttm net_failover virtio_console failover drm ata_generic pata_acpi floppy qemu_fw_cfg
> [ 1694.849736] CR2: 000000000000002c
> [ 1694.850813] ---[ end trace da2f469c62deb564 ]---
>
> -- 
> Jeff Layton <jlayton@kernel.org>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[Jeff Layton]

On Mon, 2018-10-29 at 12:56 +1100, NeilBrown wrote:
> On Fri, Oct 26 2018, Jeff Layton wrote:
> 
> > On Wed, 2018-10-24 at 09:43 +1100, NeilBrown wrote:
> > > This took longer that I had wanted, due to various reasons - sorry.
> > > And I'm now posting it in a merge window, which is not ideal.  I don't
> > > expect it to be included in this merge window and I won't be at all
> > > impatient for review, but I didn't want to delay it further.
> > > 
> > > Testing found some problems, particularly the need to use
> > > locks_copy_lock in NFS.  And there was a small thinko in there that
> > > effectively removed all the speed gains :-(
> > > 
> > > But this version:
> > >  - shows excellent scalability with lots of threads on lots of CPUs
> > >    contending on a single file
> > >  - avoids the problems that Bruce found
> > >  - seems to work.
> > > 
> > > Thanks,
> > > NeilBrown
> > > 
> > > 
> > > ---
> > > 
> > > NeilBrown (9):
> > >       fs/locks: rename some lists and pointers.
> > >       fs/locks: split out __locks_wake_up_blocks().
> > >       NFS: use locks_copy_lock() to copy locks.
> > >       fs/locks: allow a lock request to block other requests.
> > >       fs/locks: always delete_block after waiting.
> > >       fs/locks: change all *_conflict() functions to return bool.
> > >       fs/locks: create a tree of dependent requests.
> > >       locks: merge posix_unblock_lock() and locks_delete_block()
> > >       VFS: locks: remove unnecessary white space.
> > > 
> > > 
> > >  fs/cifs/file.c                  |    4 -
> > >  fs/lockd/svclock.c              |    2 
> > >  fs/locks.c                      |  231 ++++++++++++++++++++++-----------------
> > >  fs/nfs/nfs4proc.c               |    6 +
> > >  fs/nfsd/nfs4state.c             |    6 +
> > >  include/linux/fs.h              |   11 +-
> > >  include/trace/events/filelock.h |   16 +--
> > >  7 files changed, 153 insertions(+), 123 deletions(-)
> > > 
> > > --
> > > Signature
> > > 
> > 
> > 
> > I built a kernel with these patches and ran the cthon04 lock tests and
> > got this on lock test 1 after a long hang (the test passed though):
> 
> I've been looking deeper into this, and I cannot see how this can
> happen.
> 
> This is an unlock request, happening when a file is closed.
> locks_delete_block() will only be called from locks_lock_inode_wait()
> after posix_lock_inode() (or possible flock_lock_inode()) returns
> FILE_LOCK_DEFERRED.
> 
> But these only return FILE_LOCK_DEFERRED when fl_type != F_UNLCK.
> (or possibly if FL_ACCESS and FL_SLEEP are both set - that would be
>  weird).
> 
> So this shouldn't happen - an unlock request should never result in
> locks_delete_block() being called.
> But if it can, I'll need to change do_flock() in gfs2/file.c to use a
> properly initialized 'struct file_lock', rather than a manifest
> constant.  Maybe I should do that anyway.
> 
> Any ideas? I'll try running connectathon myself later and see if I can
> reproduce it.
> 
> Thanks,
> NeilBrown
> 
> > 
> > [ 1694.787367] BUG: unable to handle kernel NULL pointer dereference at 000000000000002c
> > [ 1694.789546] PGD 118ff0067 P4D 118ff0067 PUD 135915067 PMD 0 
> > [ 1694.790772] Oops: 0000 [#1] SMP NOPTI
> > [ 1694.791749] CPU: 7 PID: 1514 Comm: tlocklfs Not tainted 4.19.0+ #56
> > [ 1694.792876] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20180531_142017-buildhw-08.phx2.fedoraproject.org-1.fc28 04/01/2014
> > [ 1694.795179] RIP: 0010:__locks_delete_block+0x14/0x90
> > [ 1694.796203] Code: 01 a1 e9 9f 4f d8 ff 0f 1f 44 00 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 29 9d 58 01 55 53 48 89 fb 85 c0 75 5a <48> 8b 43 20 48 85 c0 74 20 48 8b 53 18 48 89 10 48 85 d2 74 04 48
> > [ 1694.799277] RSP: 0018:ffff9d21c1f63cb8 EFLAGS: 00010202
> > [ 1694.800374] RAX: 0000000000000001 RBX: 000000000000000c RCX: aaaaaaaaaaaaaaad
> > [ 1694.801682] RDX: 0000000000000001 RSI: ffffffff9f7b0c38 RDI: 0000000000000246
> > [ 1694.802996] RBP: 000000000000000c R08: 0000000000000000 R09: 0000000000000001
> > [ 1694.804317] R10: 0000000000000001 R11: ffffffffa0bdc188 R12: ffff9d21c1f63dd8
> > [ 1694.805633] R13: ffff9d21c1f63e00 R14: ffffffff9f3241a8 R15: ffff8d0b5aef72e0
> > [ 1694.806941] FS:  00007efc8699c740(0000) GS:ffff8d0b7ba00000(0000) knlGS:0000000000000000
> > [ 1694.808380] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> > [ 1694.809550] CR2: 000000000000002c CR3: 000000011e0d8000 CR4: 00000000000006e0
> > [ 1694.810888] Call Trace:
> > [ 1694.811692]  __locks_wake_up_blocks+0x2d/0x80
> > [ 1694.812713]  locks_delete_block+0x1d/0x40
> > [ 1694.813691]  locks_lock_inode_wait+0x9c/0x1c0
> > [ 1694.814731]  nfs4_proc_lock+0x120/0x440 [nfsv4]
> > [ 1694.815786]  ? nfs_put_lock_context+0x25/0x80 [nfs]
> > [ 1694.816866]  ? do_unlk+0x98/0xe0 [nfs]
> > [ 1694.817818]  locks_remove_posix+0xba/0x1d0
> > [ 1694.818811]  ? _cond_resched+0x15/0x30
> > [ 1694.819768]  ? wait_on_commit+0x38/0xb0 [nfs]
> > [ 1694.820787]  ? process_echoes+0x60/0x60
> > [ 1694.821752]  ? __nfs_commit_inode+0xc2/0x1c0 [nfs]
> > [ 1694.822819]  filp_close+0x56/0x70
> > [ 1694.823712]  __x64_sys_close+0x1e/0x50
> > [ 1694.824661]  do_syscall_64+0x60/0x1f0
> > [ 1694.825599]  entry_SYSCALL_64_after_hwframe+0x49/0xbe
> > [ 1694.826731] RIP: 0033:0x7efc8616c0a4
> > [ 1694.827673] Code: eb 89 e8 af f6 01 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 aa e7 2c 00 48 63 ff 85 c0 75 13 b8 03 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 44 f3 c3 66 90 48 83 ec 18 48 89 7c 24 08 e8
> > [ 1694.830929] RSP: 002b:00007ffc70beb7b8 EFLAGS: 00000246 ORIG_RAX: 0000000000000003
> > [ 1694.832371] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007efc8616c0a4
> > [ 1694.833784] RDX: 0000000000000000 RSI: 00007efc864378a0 RDI: 0000000000000009
> > [ 1694.835183] RBP: 00007ffc70beb7d0 R08: 00007efc864378a0 R09: 00007efc8699c740
> > [ 1694.836560] R10: 00000000000006b4 R11: 0000000000000246 R12: 0000000000401000
> > [ 1694.837941] R13: 00007ffc70beb990 R14: 0000000000000000 R15: 0000000000000000
> > [ 1694.839322] Modules linked in: rpcsec_gss_krb5 nfsv4 dns_resolver nfs fscache nfsd auth_rpcgss nfs_acl lockd grace ip6t_rpfilter ip6t_REJECT nf_reject_ipv6 xt_conntrack ip_set nfnetlink ebtable_nat ebtable_broute bridge stp llc ip6table_nat nf_nat_ipv6 ip6table_mangle ip6table_raw ip6table_security iptable_nat nf_nat_ipv4 nf_nat nf_conntrack nf_defrag_ipv6 nf_defrag_ipv4 iptable_mangle iptable_raw iptable_security ebtable_filter ebtables ip6table_filter ip6_tables sunrpc joydev virtio_balloon i2c_piix4 pcspkr edac_mce_amd xfs libcrc32c serio_raw virtio_blk qxl drm_kms_helper virtio_net ttm net_failover virtio_console failover drm ata_generic pata_acpi floppy qemu_fw_cfg
> > [ 1694.849736] CR2: 000000000000002c
> > [ 1694.850813] ---[ end trace da2f469c62deb564 ]---
> > 
> > -- 
> > Jeff Layton <jlayton@kernel.org>

Yes. It crashed here:

(gdb) list *(__locks_delete_block+0x14)
0xffffffff81391374 is in __locks_delete_block
(./include/linux/list.h:693).
688		n->pprev = LIST_POISON2;
689	}
690	
691	static inline void hlist_del_init(struct hlist_node *n)
692	{
693		if (!hlist_unhashed(n)) {
694			__hlist_del(n);
695			INIT_HLIST_NODE(n);
696		}
697	}

...and that should be the address of fl->fl_link.

I think the issue is probably in locks_remove_posix. It creates a lock
request on the stack, and doesn't seem to initialize fl_link. That used
to be ok, but patch #5 in the series changes that.

The following patch seems to fix the problem in a quick test. I'll plan
to run some more tests later. It may be a day or two before I can get to
it though.

-----------------------8<---------------------------

[PATCH] locks: initialize list heads in locks_remove_posix lock request

Signed-off-by: Jeff Layton <jlayton@kernel.org>
---
 fs/locks.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/fs/locks.c b/fs/locks.c
index 6b9da320d9a0..60019e146839 100644
--- a/fs/locks.c
+++ b/fs/locks.c
@@ -2535,6 +2535,7 @@ void locks_remove_posix(struct file *filp, fl_owner_t owner)
 	lock.fl_file = filp;
 	lock.fl_ops = NULL;
 	lock.fl_lmops = NULL;
+	locks_init_lock_heads(&lock);
 
 	error = vfs_lock_file(filp, F_SETLK, &lock, NULL);
 
-- 
2.17.2

Re: [PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[Jeff Layton]

On Mon, 2018-10-29 at 08:38 -0400, Jeff Layton wrote:
> On Mon, 2018-10-29 at 12:56 +1100, NeilBrown wrote:
> > On Fri, Oct 26 2018, Jeff Layton wrote:
> > 
> > > On Wed, 2018-10-24 at 09:43 +1100, NeilBrown wrote:
> > > > This took longer that I had wanted, due to various reasons - sorry.
> > > > And I'm now posting it in a merge window, which is not ideal.  I don't
> > > > expect it to be included in this merge window and I won't be at all
> > > > impatient for review, but I didn't want to delay it further.
> > > > 
> > > > Testing found some problems, particularly the need to use
> > > > locks_copy_lock in NFS.  And there was a small thinko in there that
> > > > effectively removed all the speed gains :-(
> > > > 
> > > > But this version:
> > > >  - shows excellent scalability with lots of threads on lots of CPUs
> > > >    contending on a single file
> > > >  - avoids the problems that Bruce found
> > > >  - seems to work.
> > > > 
> > > > Thanks,
> > > > NeilBrown
> > > > 
> > > > 
> > > > ---
> > > > 
> > > > NeilBrown (9):
> > > >       fs/locks: rename some lists and pointers.
> > > >       fs/locks: split out __locks_wake_up_blocks().
> > > >       NFS: use locks_copy_lock() to copy locks.
> > > >       fs/locks: allow a lock request to block other requests.
> > > >       fs/locks: always delete_block after waiting.
> > > >       fs/locks: change all *_conflict() functions to return bool.
> > > >       fs/locks: create a tree of dependent requests.
> > > >       locks: merge posix_unblock_lock() and locks_delete_block()
> > > >       VFS: locks: remove unnecessary white space.
> > > > 
> > > > 
> > > >  fs/cifs/file.c                  |    4 -
> > > >  fs/lockd/svclock.c              |    2 
> > > >  fs/locks.c                      |  231 ++++++++++++++++++++++-----------------
> > > >  fs/nfs/nfs4proc.c               |    6 +
> > > >  fs/nfsd/nfs4state.c             |    6 +
> > > >  include/linux/fs.h              |   11 +-
> > > >  include/trace/events/filelock.h |   16 +--
> > > >  7 files changed, 153 insertions(+), 123 deletions(-)
> > > > 
> > > > --
> > > > Signature
> > > > 
> > > 
> > > 
> > > I built a kernel with these patches and ran the cthon04 lock tests and
> > > got this on lock test 1 after a long hang (the test passed though):
> > 
> > I've been looking deeper into this, and I cannot see how this can
> > happen.
> > 
> > This is an unlock request, happening when a file is closed.
> > locks_delete_block() will only be called from locks_lock_inode_wait()
> > after posix_lock_inode() (or possible flock_lock_inode()) returns
> > FILE_LOCK_DEFERRED.
> > 
> > But these only return FILE_LOCK_DEFERRED when fl_type != F_UNLCK.
> > (or possibly if FL_ACCESS and FL_SLEEP are both set - that would be
> >  weird).
> > 
> > So this shouldn't happen - an unlock request should never result in
> > locks_delete_block() being called.
> > But if it can, I'll need to change do_flock() in gfs2/file.c to use a
> > properly initialized 'struct file_lock', rather than a manifest
> > constant.  Maybe I should do that anyway.
> > 
> > Any ideas? I'll try running connectathon myself later and see if I can
> > reproduce it.
> > 
> > Thanks,
> > NeilBrown
> > 
> > > 
> > > [ 1694.787367] BUG: unable to handle kernel NULL pointer dereference at 000000000000002c
> > > [ 1694.789546] PGD 118ff0067 P4D 118ff0067 PUD 135915067 PMD 0 
> > > [ 1694.790772] Oops: 0000 [#1] SMP NOPTI
> > > [ 1694.791749] CPU: 7 PID: 1514 Comm: tlocklfs Not tainted 4.19.0+ #56
> > > [ 1694.792876] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20180531_142017-buildhw-08.phx2.fedoraproject.org-1.fc28 04/01/2014
> > > [ 1694.795179] RIP: 0010:__locks_delete_block+0x14/0x90
> > > [ 1694.796203] Code: 01 a1 e9 9f 4f d8 ff 0f 1f 44 00 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 29 9d 58 01 55 53 48 89 fb 85 c0 75 5a <48> 8b 43 20 48 85 c0 74 20 48 8b 53 18 48 89 10 48 85 d2 74 04 48
> > > [ 1694.799277] RSP: 0018:ffff9d21c1f63cb8 EFLAGS: 00010202
> > > [ 1694.800374] RAX: 0000000000000001 RBX: 000000000000000c RCX: aaaaaaaaaaaaaaad
> > > [ 1694.801682] RDX: 0000000000000001 RSI: ffffffff9f7b0c38 RDI: 0000000000000246
> > > [ 1694.802996] RBP: 000000000000000c R08: 0000000000000000 R09: 0000000000000001
> > > [ 1694.804317] R10: 0000000000000001 R11: ffffffffa0bdc188 R12: ffff9d21c1f63dd8
> > > [ 1694.805633] R13: ffff9d21c1f63e00 R14: ffffffff9f3241a8 R15: ffff8d0b5aef72e0
> > > [ 1694.806941] FS:  00007efc8699c740(0000) GS:ffff8d0b7ba00000(0000) knlGS:0000000000000000
> > > [ 1694.808380] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> > > [ 1694.809550] CR2: 000000000000002c CR3: 000000011e0d8000 CR4: 00000000000006e0
> > > [ 1694.810888] Call Trace:
> > > [ 1694.811692]  __locks_wake_up_blocks+0x2d/0x80
> > > [ 1694.812713]  locks_delete_block+0x1d/0x40
> > > [ 1694.813691]  locks_lock_inode_wait+0x9c/0x1c0
> > > [ 1694.814731]  nfs4_proc_lock+0x120/0x440 [nfsv4]
> > > [ 1694.815786]  ? nfs_put_lock_context+0x25/0x80 [nfs]
> > > [ 1694.816866]  ? do_unlk+0x98/0xe0 [nfs]
> > > [ 1694.817818]  locks_remove_posix+0xba/0x1d0
> > > [ 1694.818811]  ? _cond_resched+0x15/0x30
> > > [ 1694.819768]  ? wait_on_commit+0x38/0xb0 [nfs]
> > > [ 1694.820787]  ? process_echoes+0x60/0x60
> > > [ 1694.821752]  ? __nfs_commit_inode+0xc2/0x1c0 [nfs]
> > > [ 1694.822819]  filp_close+0x56/0x70
> > > [ 1694.823712]  __x64_sys_close+0x1e/0x50
> > > [ 1694.824661]  do_syscall_64+0x60/0x1f0
> > > [ 1694.825599]  entry_SYSCALL_64_after_hwframe+0x49/0xbe
> > > [ 1694.826731] RIP: 0033:0x7efc8616c0a4
> > > [ 1694.827673] Code: eb 89 e8 af f6 01 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 aa e7 2c 00 48 63 ff 85 c0 75 13 b8 03 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 44 f3 c3 66 90 48 83 ec 18 48 89 7c 24 08 e8
> > > [ 1694.830929] RSP: 002b:00007ffc70beb7b8 EFLAGS: 00000246 ORIG_RAX: 0000000000000003
> > > [ 1694.832371] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007efc8616c0a4
> > > [ 1694.833784] RDX: 0000000000000000 RSI: 00007efc864378a0 RDI: 0000000000000009
> > > [ 1694.835183] RBP: 00007ffc70beb7d0 R08: 00007efc864378a0 R09: 00007efc8699c740
> > > [ 1694.836560] R10: 00000000000006b4 R11: 0000000000000246 R12: 0000000000401000
> > > [ 1694.837941] R13: 00007ffc70beb990 R14: 0000000000000000 R15: 0000000000000000
> > > [ 1694.839322] Modules linked in: rpcsec_gss_krb5 nfsv4 dns_resolver nfs fscache nfsd auth_rpcgss nfs_acl lockd grace ip6t_rpfilter ip6t_REJECT nf_reject_ipv6 xt_conntrack ip_set nfnetlink ebtable_nat ebtable_broute bridge stp llc ip6table_nat nf_nat_ipv6 ip6table_mangle ip6table_raw ip6table_security iptable_nat nf_nat_ipv4 nf_nat nf_conntrack nf_defrag_ipv6 nf_defrag_ipv4 iptable_mangle iptable_raw iptable_security ebtable_filter ebtables ip6table_filter ip6_tables sunrpc joydev virtio_balloon i2c_piix4 pcspkr edac_mce_amd xfs libcrc32c serio_raw virtio_blk qxl drm_kms_helper virtio_net ttm net_failover virtio_console failover drm ata_generic pata_acpi floppy qemu_fw_cfg
> > > [ 1694.849736] CR2: 000000000000002c
> > > [ 1694.850813] ---[ end trace da2f469c62deb564 ]---
> > > 
> > > -- 
> > > Jeff Layton <jlayton@kernel.org>
> 
> Yes. It crashed here:
> 
> (gdb) list *(__locks_delete_block+0x14)
> 0xffffffff81391374 is in __locks_delete_block
> (./include/linux/list.h:693).
> 688		n->pprev = LIST_POISON2;
> 689	}
> 690	
> 691	static inline void hlist_del_init(struct hlist_node *n)
> 692	{
> 693		if (!hlist_unhashed(n)) {
> 694			__hlist_del(n);
> 695			INIT_HLIST_NODE(n);
> 696		}
> 697	}
> 
> ...and that should be the address of fl->fl_link.
> 
> I think the issue is probably in locks_remove_posix. It creates a lock
> request on the stack, and doesn't seem to initialize fl_link. That used
> to be ok, but patch #5 in the series changes that.
> 
> The following patch seems to fix the problem in a quick test. I'll plan
> to run some more tests later. It may be a day or two before I can get to
> it though.
> 
> -----------------------8<---------------------------
> 
> [PATCH] locks: initialize list heads in locks_remove_posix lock request
> 
> Signed-off-by: Jeff Layton <jlayton@kernel.org>
> ---
>  fs/locks.c | 1 +
>  1 file changed, 1 insertion(+)
> 
> diff --git a/fs/locks.c b/fs/locks.c
> index 6b9da320d9a0..60019e146839 100644
> --- a/fs/locks.c
> +++ b/fs/locks.c
> @@ -2535,6 +2535,7 @@ void locks_remove_posix(struct file *filp, fl_owner_t owner)
>  	lock.fl_file = filp;
>  	lock.fl_ops = NULL;
>  	lock.fl_lmops = NULL;
> +	locks_init_lock_heads(&lock);
>  
>  	error = vfs_lock_file(filp, F_SETLK, &lock, NULL);
>  

I ran a bunch of tests on top of your series + this patch and it seemed
to do fine. I'm guessing maybe you just got "lucky" and your kernel
happened to end up with the fl_link value set in such a way that
hlist_unhashed returned true there?

In any case, this seems to fix the issue I was seeing. The only question
I have is whether this will be more expensive than doing something more
clever like checking for FL_SLEEP in locks_remove_block.

I've gone ahead and pushed the set to my locks-next branch to start
getting more testing. If all goes well, I'll plan to send Linus a PR for
v4.21 (or v5.1).

Thanks again for doing this!
-- 
Jeff Layton <jlayton@kernel.org>

Re: [PATCH 0/9 v3] locks: avoid thundering-herd wake-ups

[Jeff Layton]

On Tue, 2018-10-30 at 08:04 -0400, Jeff Layton wrote:
> On Mon, 2018-10-29 at 08:38 -0400, Jeff Layton wrote:
> > On Mon, 2018-10-29 at 12:56 +1100, NeilBrown wrote:
> > > On Fri, Oct 26 2018, Jeff Layton wrote:
> > > 
> > > > On Wed, 2018-10-24 at 09:43 +1100, NeilBrown wrote:
> > > > > This took longer that I had wanted, due to various reasons - sorry.
> > > > > And I'm now posting it in a merge window, which is not ideal.  I don't
> > > > > expect it to be included in this merge window and I won't be at all
> > > > > impatient for review, but I didn't want to delay it further.
> > > > > 
> > > > > Testing found some problems, particularly the need to use
> > > > > locks_copy_lock in NFS.  And there was a small thinko in there that
> > > > > effectively removed all the speed gains :-(
> > > > > 
> > > > > But this version:
> > > > >  - shows excellent scalability with lots of threads on lots of CPUs
> > > > >    contending on a single file
> > > > >  - avoids the problems that Bruce found
> > > > >  - seems to work.
> > > > > 
> > > > > Thanks,
> > > > > NeilBrown
> > > > > 
> > > > > 
> > > > > ---
> > > > > 
> > > > > NeilBrown (9):
> > > > >       fs/locks: rename some lists and pointers.
> > > > >       fs/locks: split out __locks_wake_up_blocks().
> > > > >       NFS: use locks_copy_lock() to copy locks.
> > > > >       fs/locks: allow a lock request to block other requests.
> > > > >       fs/locks: always delete_block after waiting.
> > > > >       fs/locks: change all *_conflict() functions to return bool.
> > > > >       fs/locks: create a tree of dependent requests.
> > > > >       locks: merge posix_unblock_lock() and locks_delete_block()
> > > > >       VFS: locks: remove unnecessary white space.
> > > > > 
> > > > > 
> > > > >  fs/cifs/file.c                  |    4 -
> > > > >  fs/lockd/svclock.c              |    2 
> > > > >  fs/locks.c                      |  231 ++++++++++++++++++++++-----------------
> > > > >  fs/nfs/nfs4proc.c               |    6 +
> > > > >  fs/nfsd/nfs4state.c             |    6 +
> > > > >  include/linux/fs.h              |   11 +-
> > > > >  include/trace/events/filelock.h |   16 +--
> > > > >  7 files changed, 153 insertions(+), 123 deletions(-)
> > > > > 
> > > > > --
> > > > > Signature
> > > > > 
> > > > 
> > > > 
> > > > I built a kernel with these patches and ran the cthon04 lock tests and
> > > > got this on lock test 1 after a long hang (the test passed though):
> > > 
> > > I've been looking deeper into this, and I cannot see how this can
> > > happen.
> > > 
> > > This is an unlock request, happening when a file is closed.
> > > locks_delete_block() will only be called from locks_lock_inode_wait()
> > > after posix_lock_inode() (or possible flock_lock_inode()) returns
> > > FILE_LOCK_DEFERRED.
> > > 
> > > But these only return FILE_LOCK_DEFERRED when fl_type != F_UNLCK.
> > > (or possibly if FL_ACCESS and FL_SLEEP are both set - that would be
> > >  weird).
> > > 
> > > So this shouldn't happen - an unlock request should never result in
> > > locks_delete_block() being called.
> > > But if it can, I'll need to change do_flock() in gfs2/file.c to use a
> > > properly initialized 'struct file_lock', rather than a manifest
> > > constant.  Maybe I should do that anyway.
> > > 
> > > Any ideas? I'll try running connectathon myself later and see if I can
> > > reproduce it.
> > > 
> > > Thanks,
> > > NeilBrown
> > > 

Sorry, I missed your comment about gfs2.

Yes, we'll need to do something similar there. Looks like ocfs2_do_flock
likely has the same problem too. I think we can just call
locks_init_lock on those and then initialize the fields being set
afterward.

Given that that needs to be fixed, I'll hold off on merging this into
linux-next just yet. Would you mind respinning this series with those
fixed up? Feel free to squash my one-liner patch in with another too.

> > > > [ 1694.787367] BUG: unable to handle kernel NULL pointer dereference at 000000000000002c
> > > > [ 1694.789546] PGD 118ff0067 P4D 118ff0067 PUD 135915067 PMD 0 
> > > > [ 1694.790772] Oops: 0000 [#1] SMP NOPTI
> > > > [ 1694.791749] CPU: 7 PID: 1514 Comm: tlocklfs Not tainted 4.19.0+ #56
> > > > [ 1694.792876] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20180531_142017-buildhw-08.phx2.fedoraproject.org-1.fc28 04/01/2014
> > > > [ 1694.795179] RIP: 0010:__locks_delete_block+0x14/0x90
> > > > [ 1694.796203] Code: 01 a1 e9 9f 4f d8 ff 0f 1f 44 00 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 29 9d 58 01 55 53 48 89 fb 85 c0 75 5a <48> 8b 43 20 48 85 c0 74 20 48 8b 53 18 48 89 10 48 85 d2 74 04 48
> > > > [ 1694.799277] RSP: 0018:ffff9d21c1f63cb8 EFLAGS: 00010202
> > > > [ 1694.800374] RAX: 0000000000000001 RBX: 000000000000000c RCX: aaaaaaaaaaaaaaad
> > > > [ 1694.801682] RDX: 0000000000000001 RSI: ffffffff9f7b0c38 RDI: 0000000000000246
> > > > [ 1694.802996] RBP: 000000000000000c R08: 0000000000000000 R09: 0000000000000001
> > > > [ 1694.804317] R10: 0000000000000001 R11: ffffffffa0bdc188 R12: ffff9d21c1f63dd8
> > > > [ 1694.805633] R13: ffff9d21c1f63e00 R14: ffffffff9f3241a8 R15: ffff8d0b5aef72e0
> > > > [ 1694.806941] FS:  00007efc8699c740(0000) GS:ffff8d0b7ba00000(0000) knlGS:0000000000000000
> > > > [ 1694.808380] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> > > > [ 1694.809550] CR2: 000000000000002c CR3: 000000011e0d8000 CR4: 00000000000006e0
> > > > [ 1694.810888] Call Trace:
> > > > [ 1694.811692]  __locks_wake_up_blocks+0x2d/0x80
> > > > [ 1694.812713]  locks_delete_block+0x1d/0x40
> > > > [ 1694.813691]  locks_lock_inode_wait+0x9c/0x1c0
> > > > [ 1694.814731]  nfs4_proc_lock+0x120/0x440 [nfsv4]
> > > > [ 1694.815786]  ? nfs_put_lock_context+0x25/0x80 [nfs]
> > > > [ 1694.816866]  ? do_unlk+0x98/0xe0 [nfs]
> > > > [ 1694.817818]  locks_remove_posix+0xba/0x1d0
> > > > [ 1694.818811]  ? _cond_resched+0x15/0x30
> > > > [ 1694.819768]  ? wait_on_commit+0x38/0xb0 [nfs]
> > > > [ 1694.820787]  ? process_echoes+0x60/0x60
> > > > [ 1694.821752]  ? __nfs_commit_inode+0xc2/0x1c0 [nfs]
> > > > [ 1694.822819]  filp_close+0x56/0x70
> > > > [ 1694.823712]  __x64_sys_close+0x1e/0x50
> > > > [ 1694.824661]  do_syscall_64+0x60/0x1f0
> > > > [ 1694.825599]  entry_SYSCALL_64_after_hwframe+0x49/0xbe
> > > > [ 1694.826731] RIP: 0033:0x7efc8616c0a4
> > > > [ 1694.827673] Code: eb 89 e8 af f6 01 00 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 8b 05 aa e7 2c 00 48 63 ff 85 c0 75 13 b8 03 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 44 f3 c3 66 90 48 83 ec 18 48 89 7c 24 08 e8
> > > > [ 1694.830929] RSP: 002b:00007ffc70beb7b8 EFLAGS: 00000246 ORIG_RAX: 0000000000000003
> > > > [ 1694.832371] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007efc8616c0a4
> > > > [ 1694.833784] RDX: 0000000000000000 RSI: 00007efc864378a0 RDI: 0000000000000009
> > > > [ 1694.835183] RBP: 00007ffc70beb7d0 R08: 00007efc864378a0 R09: 00007efc8699c740
> > > > [ 1694.836560] R10: 00000000000006b4 R11: 0000000000000246 R12: 0000000000401000
> > > > [ 1694.837941] R13: 00007ffc70beb990 R14: 0000000000000000 R15: 0000000000000000
> > > > [ 1694.839322] Modules linked in: rpcsec_gss_krb5 nfsv4 dns_resolver nfs fscache nfsd auth_rpcgss nfs_acl lockd grace ip6t_rpfilter ip6t_REJECT nf_reject_ipv6 xt_conntrack ip_set nfnetlink ebtable_nat ebtable_broute bridge stp llc ip6table_nat nf_nat_ipv6 ip6table_mangle ip6table_raw ip6table_security iptable_nat nf_nat_ipv4 nf_nat nf_conntrack nf_defrag_ipv6 nf_defrag_ipv4 iptable_mangle iptable_raw iptable_security ebtable_filter ebtables ip6table_filter ip6_tables sunrpc joydev virtio_balloon i2c_piix4 pcspkr edac_mce_amd xfs libcrc32c serio_raw virtio_blk qxl drm_kms_helper virtio_net ttm net_failover virtio_console failover drm ata_generic pata_acpi floppy qemu_fw_cfg
> > > > [ 1694.849736] CR2: 000000000000002c
> > > > [ 1694.850813] ---[ end trace da2f469c62deb564 ]---
> > > > 
> > > > -- 
> > > > Jeff Layton <jlayton@kernel.org>
> > 
> > Yes. It crashed here:
> > 
> > (gdb) list *(__locks_delete_block+0x14)
> > 0xffffffff81391374 is in __locks_delete_block
> > (./include/linux/list.h:693).
> > 688		n->pprev = LIST_POISON2;
> > 689	}
> > 690	
> > 691	static inline void hlist_del_init(struct hlist_node *n)
> > 692	{
> > 693		if (!hlist_unhashed(n)) {
> > 694			__hlist_del(n);
> > 695			INIT_HLIST_NODE(n);
> > 696		}
> > 697	}
> > 
> > ...and that should be the address of fl->fl_link.
> > 
> > I think the issue is probably in locks_remove_posix. It creates a lock
> > request on the stack, and doesn't seem to initialize fl_link. That used
> > to be ok, but patch #5 in the series changes that.
> > 
> > The following patch seems to fix the problem in a quick test. I'll plan
> > to run some more tests later. It may be a day or two before I can get to
> > it though.
> > 
> > -----------------------8<---------------------------
> > 
> > [PATCH] locks: initialize list heads in locks_remove_posix lock request
> > 
> > Signed-off-by: Jeff Layton <jlayton@kernel.org>
> > ---
> >  fs/locks.c | 1 +
> >  1 file changed, 1 insertion(+)
> > 
> > diff --git a/fs/locks.c b/fs/locks.c
> > index 6b9da320d9a0..60019e146839 100644
> > --- a/fs/locks.c
> > +++ b/fs/locks.c
> > @@ -2535,6 +2535,7 @@ void locks_remove_posix(struct file *filp, fl_owner_t owner)
> >  	lock.fl_file = filp;
> >  	lock.fl_ops = NULL;
> >  	lock.fl_lmops = NULL;
> > +	locks_init_lock_heads(&lock);
> >  
> >  	error = vfs_lock_file(filp, F_SETLK, &lock, NULL);
> >  
> 
> I ran a bunch of tests on top of your series + this patch and it seemed
> to do fine. I'm guessing maybe you just got "lucky" and your kernel
> happened to end up with the fl_link value set in such a way that
> hlist_unhashed returned true there?
> 
> In any case, this seems to fix the issue I was seeing. The only question
> I have is whether this will be more expensive than doing something more
> clever like checking for FL_SLEEP in locks_remove_block.
> 
> I've gone ahead and pushed the set to my locks-next branch to start
> getting more testing. If all goes well, I'll plan to send Linus a PR for
> v4.21 (or v5.1).
> 
> Thanks again for doing this!

-- 
Jeff Layton <jlayton@kernel.org>