[PATCH RFC/RFT v2 00/18] Fix easy bits of the negative dentry problem

[PATCH RFC/RFT v2 00/18] Fix easy bits of the negative dentry problem

[NeilBrown]

Greetings all,
 following a v2 - which has grown a bit.  Thanks a log to Miklos for
 some great review - though I would still be happy for me (and maybe
 sashiko will manage to apply this time).
 I'd also be very happy to hear of testing in anyone is able to
 trigger the reported problems with excess negative dentries.

 There are no significant changes here, just a few bug fixes and
 clarification and splitting up of some patches.  The last three
 patches come from Miklos suggesting that positive_after() in
 autofs could be in common code - in fact it already was :-)

 Original comment, though without the per-patch highlights, is below.

Thanks,
NeilBrown

 I was reading about the negative dentry problem in
 https://lwn.net/Articles/1079407/ and thought I would have ago at the
 easy bits.  Given how involved some of that was I'm glad I didn't try
 the tricky bits!

 So I didn't try to reduce the number of negative dentries or handle
 them differently to positive dentries.  I just tried to address
 specific symptoms.

 This series addresses two reported symptoms.
  1/ refcounts on parents can potentially overflow if there are billions
     of (negative) children.  This was the easiest easy bit.  The first
     patch is all that is needed.

  2/ Walking the ->d_children list can take arbitrarily long and can
     trigger soft lockups.  I haven't addresses the "arbitrarily long"
     part, but the "soft lockups" only takes another 11 patches.
     With these in place I would feel more confident addressing
     the "arbitrarily long" part.

 The core idea is to use a common helper for all walking of
 ->d_children, and teach it to drop the lock and schedule when needed,
 inserting a cursor to keep its place.
 This simple idea requires:
   - nothing should be holding any other lock while walking ->d_children
   - dentries shouldn't be moved around needlessly, else things might
     get missed.
   - quite a bit of refactoring in libfs for readdir code.

 so I have probably missed some bits and would be very happy to be told
 what I have missed.
 I would also be very happy if someone who can trigger the soft lockups
 can try this code and confirm that the locks are gone, and nothing bad
 happens.
 I have done some basic testing including the "notify" parts of
 ltp, but that is all.

 I haven't addressed d_walk() in this series - I thought it was big
 enough for now.  Most of d_walk() already schedules as needed, but I
 think there is still room for improvement, but that can come later.


 [PATCH v2 01/18] VFS: don't count references through ->d_parent
 [PATCH v2 02/18] autofs: change positive_after() so it takes d_lock
 [PATCH v2 03/18] coda: don't take rcu_read_lock() in
 [PATCH v2 04/18] nfs: separate locked regions in
 [PATCH v2 05/18] Add and use d_for_each_positive_child family of
 [PATCH v2 06/18] fsnotify: don't hold a spin_lock across
 [PATCH v2 07/18] fsnotify: reduce i_lock hold time in
 [PATCH v2 08/18] libfs: simplify scan_positives()
 [PATCH v2 09/18] libfs: change scan_positives() to use
 [PATCH v2 10/18] libfs: allow scan_positives() to be called without a
 [PATCH v2 11/18] libfs: replace find_positive_dentry() with
 [PATCH v2 12/18] autofs: don't hold ->lookup_lock in
 [PATCH v2 13/18] VFS: don't move dentries in d_sib list when they
 [PATCH v2 14/18] Call cond_reshed() as needed in
 [PATCH v2 15/18] libfs: remove cond_resched() from scan_positives()
 [PATCH v2 16/18] libfs: rename and export scan_positives()
 [PATCH v2 17/18] autofs: replace positive_after() with
 [PATCH v2 18/18] autofs: change get_next_positive_dentry() to NOT

[PATCH v2 01/18] VFS: don't count references through ->d_parent

[NeilBrown]

From: NeilBrown <neil@brown.name>

The number of negative child dentries that a given dentry can have is
effectively unbounded, so counting the references through ->d_parent can
overflow ->d_lockref.count.

We only use this count so that we can know when there are no remaining
references including from children.  However most children appear on the
->d_children list and the few remaining children (inactive
DCACHE_DENTRY_CURSORs) only exist in a context were a separate reference
is held on the parent.

So if we count whether d_children is nonempty (i.e.  dget() when it
becomes non-empty, dput() when it comes empty) and require children not
on ->d_children to have a reference on the parent some other way (which
they already do), then ->d_lockref.count will not overflow and we can
still know exactly when all references, including through ->d_parent,
are gone.

__d_move() allows that dentries might not be on any d_children list as
is the case for IS_ROOT() dentries.  Rather than track when this is the
case we dget() either parent if they have an empty d_children before
children are moved around, then dput() if they turn out to be empty
afterwards.  This will increment dentry if it IS_ROOT(), and then
decrement it afterwards, and will decrement the refcount on old_parent
if its ->d_children becomes empty.

To help with this, dput_dlock() is added which warns rather than
decrementing to zero (which should never happen).

When a DCACHE_CURSOR dentry is added to d_children, it is only ever
added "before" or "behind" an existing child, so it will never be the
first and so never needs to adjust the refcount on the parent.  If it
remains on the list until dput() it could be the last child to be
removed, in which case normal handling applies in dentry_unlist() (where
it has been moved from dentry_kill().  When a cursor is deliberately
removed from the d_children list the refcount must be decremented if that
leaves the list empty.

hlist_move_behind() and hlist_move_before() are added to simplify moving
a cursor within the d_children list.  This result in some duplicate code
as they share a common prefix with d_detach_cursor() (hlist_del)
which is currently factored out.  We can expect the compiler to optimise
this away and don't need to clutter the C code with it.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/dcache.c            | 40 +++++++++++++++++++++++++++++++++-------
 fs/internal.h          | 10 ++++++++++
 fs/libfs.c             | 14 +++++++-------
 include/linux/dcache.h | 17 ++++++++++++++++-
 include/linux/list.h   | 30 ++++++++++++++++++++++++++++++
 5 files changed, 96 insertions(+), 15 deletions(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index 3e9af9de7074..ae726f3ff0cb 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -670,6 +670,8 @@ static inline void dentry_unlist(struct dentry *dentry)
 		return;
 	}
 	__hlist_del(&dentry->d_sib);
+	if (hlist_empty(&dentry->d_parent->d_children))
+		dentry->d_parent->d_lockref.count--;
 	/*
 	 * Cursors can move around the list of children.  While we'd been
 	 * a normal list member, it didn't matter - ->d_sib.next would've
@@ -843,7 +845,7 @@ static struct dentry *dentry_kill(struct dentry *dentry)
 	spin_unlock(&dentry->d_lock);
 	if (likely(can_free))
 		dentry_free(dentry);
-	if (parent && --parent->d_lockref.count) {
+	if (parent && parent->d_lockref.count) {
 		spin_unlock(&parent->d_lock);
 		return NULL;
 	}
@@ -1986,7 +1988,9 @@ struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
 	 * don't need child lock because it is not subject
 	 * to concurrency here
 	 */
-	dentry->d_parent = dget_dlock(parent);
+	dentry->d_parent = parent;
+	if (hlist_empty(&parent->d_children))
+		dget_dlock(parent);
 	hlist_add_head(&dentry->d_sib, &parent->d_children);
 	spin_unlock(&parent->d_lock);
 
@@ -2005,7 +2009,7 @@ struct dentry *d_alloc_cursor(struct dentry * parent)
 	struct dentry *dentry = d_alloc_anon(parent->d_sb);
 	if (dentry) {
 		dentry->d_flags |= DCACHE_DENTRY_CURSOR | DCACHE_NORCU;
-		dentry->d_parent = dget(parent);
+		dentry->d_parent = parent;
 	}
 	return dentry;
 }
@@ -2767,7 +2771,9 @@ struct dentry *d_alloc_parallel(struct dentry *parent,
 
 	new->d_flags |= DCACHE_PAR_LOOKUP;
 	spin_lock(&parent->d_lock);
-	new->d_parent = dget_dlock(parent);
+	new->d_parent = parent;
+	if (hlist_empty(&parent->d_children))
+		dget_dlock(parent);
 	hlist_add_head(&new->d_sib, &parent->d_children);
 	if (parent->d_flags & DCACHE_DISCONNECTED)
 		new->d_flags |= DCACHE_DISCONNECTED;
@@ -3095,12 +3101,21 @@ static void __d_move(struct dentry *dentry, struct dentry *target,
 
 	/* ... and switch them in the tree */
 	dentry->d_parent = target->d_parent;
+
+	/*
+	 * Ensure ref count on parents reflect d_children being non-empty,
+	 * which they almost certainly are.  If either end up being empty,
+	 * this is handled below after the moves.
+	 */
+	if (hlist_empty(&old_parent->d_children))
+		dget_dlock(old_parent);
+	if (dentry->d_parent != old_parent &&
+	    hlist_empty(&dentry->d_parent->d_children))
+		dget_dlock(dentry->d_parent);
+
 	if (!exchange) {
 		copy_name(dentry, target);
 		target->d_hash.pprev = NULL;
-		dentry->d_parent->d_lockref.count++;
-		if (dentry != old_parent) /* wasn't IS_ROOT */
-			WARN_ON(!--old_parent->d_lockref.count);
 	} else {
 		target->d_parent = old_parent;
 		swap_names(dentry, target);
@@ -3113,6 +3128,17 @@ static void __d_move(struct dentry *dentry, struct dentry *target,
 	if (!hlist_unhashed(&dentry->d_sib))
 		__hlist_del(&dentry->d_sib);
 	hlist_add_head(&dentry->d_sib, &dentry->d_parent->d_children);
+
+	/*
+	 * Adjust parent refcounts if either d_children ended up empty.
+	 * This should only ever be old_parent.
+	 */
+	if (hlist_empty(&old_parent->d_children))
+		dput_dlock(old_parent);
+	if (dentry->d_parent != old_parent &&
+	    hlist_empty(&dentry->d_parent->d_children))
+		dput_dlock(dentry->d_parent);
+
 	__d_rehash(dentry);
 	fsnotify_update_flags(dentry);
 	fscrypt_handle_d_move(dentry);
diff --git a/fs/internal.h b/fs/internal.h
index 355d93f92208..8646fd6d55ef 100644
--- a/fs/internal.h
+++ b/fs/internal.h
@@ -234,6 +234,16 @@ extern struct dentry *__d_lookup(const struct dentry *, const struct qstr *);
 extern struct dentry *__d_lookup_rcu(const struct dentry *parent,
 				const struct qstr *name, unsigned *seq);
 
+static inline void d_detach_cursor(struct dentry *cursor)
+{
+	if (hlist_unhashed(&cursor->d_sib))
+		return;
+	hlist_del_init(&cursor->d_sib);
+	if (hlist_empty(&cursor->d_parent->d_children))
+		/* That was the last child, must drop implied reference */
+		dput_dlock(cursor->d_parent);
+}
+
 /*
  * pipe.c
  */
diff --git a/fs/libfs.c b/fs/libfs.c
index 5a0d276379d1..7cd816b8e2a0 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -128,9 +128,7 @@ static struct dentry *scan_positives(struct dentry *cursor,
 			count = 1;
 		}
 		if (need_resched()) {
-			if (!hlist_unhashed(&cursor->d_sib))
-				__hlist_del(&cursor->d_sib);
-			hlist_add_behind(&cursor->d_sib, &d->d_sib);
+			hlist_move_behind(&cursor->d_sib, &d->d_sib);
 			p = &cursor->d_sib.next;
 			spin_unlock(&dentry->d_lock);
 			cond_resched();
@@ -166,9 +164,10 @@ loff_t dcache_dir_lseek(struct file *file, loff_t offset, int whence)
 			to = scan_positives(cursor, &dentry->d_children.first,
 					    offset - 2, NULL);
 		spin_lock(&dentry->d_lock);
-		hlist_del_init(&cursor->d_sib);
 		if (to)
-			hlist_add_behind(&cursor->d_sib, &to->d_sib);
+			hlist_move_behind(&cursor->d_sib, &to->d_sib);
+		else
+			d_detach_cursor(cursor);
 		spin_unlock(&dentry->d_lock);
 		dput(to);
 
@@ -210,9 +209,10 @@ int dcache_readdir(struct file *file, struct dir_context *ctx)
 		p = &next->d_sib.next;
 	}
 	spin_lock(&dentry->d_lock);
-	hlist_del_init(&cursor->d_sib);
 	if (next)
-		hlist_add_before(&cursor->d_sib, &next->d_sib);
+		hlist_move_before(&cursor->d_sib, &next->d_sib);
+	else
+		d_detach_cursor(cursor);
 	spin_unlock(&dentry->d_lock);
 	dput(next);
 
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index 4b1ff99608e0..64d64bab16fe 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -324,7 +324,7 @@ extern char *dentry_path(const struct dentry *, char *, int);
 /* Allocation counts.. */
 
 /**
- * dget_dlock -	get a reference to a dentry
+ * dget_dlock -	get a reference to a dentry while locked
  * @dentry: dentry to get a reference to
  *
  * Given a live dentry, increment the reference count and return the dentry.
@@ -339,6 +339,21 @@ static inline struct dentry *dget_dlock(struct dentry *dentry)
 	return dentry;
 }
 
+/**
+ * dput_dlock -	put a reference to a dentry while locked
+ * @dentry: dentry to get a reference to
+ *
+ * Given a live dentry, decrement the reference count and return the dentry.
+ * Caller must hold @dentry->d_lock.  The dentry must still have
+ * a reference after the decrement.  This can be used when two
+ * references are held and one must be dropped.
+ */
+static inline struct dentry *dput_dlock(struct dentry *dentry)
+{
+	if (!WARN_ON(dentry->d_lockref.count == 0))
+		dentry->d_lockref.count--;
+	return dentry;
+}
 
 /**
  * dget - get a reference to a dentry
diff --git a/include/linux/list.h b/include/linux/list.h
index 09d979976b3b..8db89117e959 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -1107,6 +1107,36 @@ static inline void hlist_add_behind(struct hlist_node *n,
 		WRITE_ONCE(n->next->pprev, &n->next);
 }
 
+/**
+ * hlist_move_behind - move an hlist node to a new location in list
+ * @n: hlist node to be moved
+ * @prev: hlist node after which @n should be added.
+ *
+ * @n may be on the list or unhashed but must not be @prev.
+ * It is removed if necessary and re-added after @prev.
+ */
+static inline void hlist_move_behind(struct hlist_node *n,
+				     struct hlist_node *prev)
+{
+	hlist_del_init(n);
+	hlist_add_behind(n, prev);
+}
+
+/**
+ * hlist_move_before - move an hlist node to a new location in list
+ * @n: hlist node to be moved
+ * @next: hlist node before which @n should be added.
+ *
+ * @n may be on the list or unhashed but must not be @next.
+ * It is removed if necessary and re-added before @next.
+ */
+static inline void hlist_move_before(struct hlist_node *n,
+				     struct hlist_node *next)
+{
+	hlist_del_init(n);
+	hlist_add_before(n, next);
+}
+
 /**
  * hlist_add_fake - create a fake hlist consisting of a single headless node
  * @n: Node to make a fake list out of

base-commit: dac3e89a2c90c2feeb471e1f22a2512ad424b792
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 02/18] autofs: change positive_after() so it takes d_lock rather than the caller

[NeilBrown]

From: NeilBrown <neil@brown.name>

Moving the d_lock from caller to callee simplifies the code.

The only non-trivial code that is no longer locked is
		parent = p->d_parent;
and as autofs doesn't support rename, ->d_parent is stable
and this doesn't need to be protected.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/autofs/expire.c | 9 ++-------
 1 file changed, 2 insertions(+), 7 deletions(-)

diff --git a/fs/autofs/expire.c b/fs/autofs/expire.c
index 5c2d459e1e48..909622eeb8a0 100644
--- a/fs/autofs/expire.c
+++ b/fs/autofs/expire.c
@@ -70,9 +70,9 @@ static int autofs_mount_busy(struct vfsmount *mnt,
 	return status;
 }
 
-/* p->d_lock held */
 static struct dentry *positive_after(struct dentry *p, struct dentry *child)
 {
+	spin_lock(&p->d_lock);
 	child = child ? d_next_sibling(child) : d_first_child(p);
 
 	hlist_for_each_entry_from(child, d_sib) {
@@ -84,6 +84,7 @@ static struct dentry *positive_after(struct dentry *p, struct dentry *child)
 		}
 		spin_unlock(&child->d_lock);
 	}
+	spin_unlock(&p->d_lock);
 
 	return NULL;
 }
@@ -98,9 +99,7 @@ static struct dentry *get_next_positive_subdir(struct dentry *prev,
 	struct dentry *q;
 
 	spin_lock(&sbi->lookup_lock);
-	spin_lock(&root->d_lock);
 	q = positive_after(root, prev);
-	spin_unlock(&root->d_lock);
 	spin_unlock(&sbi->lookup_lock);
 	dput(prev);
 	return q;
@@ -119,7 +118,6 @@ static struct dentry *get_next_positive_dentry(struct dentry *prev,
 		return dget(root);
 
 	spin_lock(&sbi->lookup_lock);
-	spin_lock(&p->d_lock);
 	while (1) {
 		struct dentry *parent;
 
@@ -127,12 +125,9 @@ static struct dentry *get_next_positive_dentry(struct dentry *prev,
 		if (ret || p == root)
 			break;
 		parent = p->d_parent;
-		spin_unlock(&p->d_lock);
-		spin_lock(&parent->d_lock);
 		d = p;
 		p = parent;
 	}
-	spin_unlock(&p->d_lock);
 	spin_unlock(&sbi->lookup_lock);
 	dput(prev);
 	return ret;
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 03/18] coda: don't take rcu_read_lock() in coda_flag_children()

[NeilBrown]

From: NeilBrown <neil@brown.name>

As described in Documentation/RCU/whatisRCU.rst sections on
rcu_read_lock() and rcu_read_unlock(), spinlocks prevent the RCU grace
period from ending so there is no need to call rcu_read_lock/unlock
inside a spinlock protected section of code.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/coda/cache.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/fs/coda/cache.c b/fs/coda/cache.c
index 245131296300..970f0022ec52 100644
--- a/fs/coda/cache.c
+++ b/fs/coda/cache.c
@@ -93,14 +93,12 @@ static void coda_flag_children(struct dentry *parent, int flag)
 	struct dentry *de;
 
 	spin_lock(&parent->d_lock);
-	rcu_read_lock();
 	hlist_for_each_entry(de, &parent->d_children, d_sib) {
 		struct inode *inode = d_inode_rcu(de);
 		/* don't know what to do with negative dentries */
 		if (inode)
 			coda_flag_inode(inode, flag);
 	}
-	rcu_read_unlock();
 	spin_unlock(&parent->d_lock);
 }
 
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 04/18] nfs: separate locked regions in nfs_clear_verifier_directory()

[NeilBrown]

From: NeilBrown <neil@brown.name>

nfs_clear_verifier_directory() locks the dir to call
  nfs_unset_verifier_delegated()
and also to walk the d_children list.
These are two separate needs and they don't need to both
be in the same locked region.

Subsequent patches will use a helper for walking the d_children list and
that helper may drop the lock temporarily.  To simplify this transition,
split the locked range by dropping and retaking the lock between to make
two separate locked regions.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/nfs/dir.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/fs/nfs/dir.c b/fs/nfs/dir.c
index c7caffb31935..bba5d996413c 100644
--- a/fs/nfs/dir.c
+++ b/fs/nfs/dir.c
@@ -1492,6 +1492,9 @@ static void nfs_clear_verifier_directory(struct inode *dir)
 
 	spin_lock(&this_parent->d_lock);
 	nfs_unset_verifier_delegated(&this_parent->d_time);
+	spin_unlock(&this_parent->d_lock);
+
+	spin_lock(&this_parent->d_lock);
 	dentry = d_first_child(this_parent);
 	hlist_for_each_entry_from(dentry, d_sib) {
 		if (unlikely(dentry->d_flags & DCACHE_DENTRY_CURSOR))
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 05/18] Add and use d_for_each_positive_child family of iterators

[NeilBrown]

From: NeilBrown <neil@brown.name>

Provide iterators for the d_children/d_sib lists.  These iterators only
report dentries that are positive (though they could be negative by the
time they are used).  As DCACHE_DENTRY_CURSOR dentries are never
positive they are never reported.

d_for_each_positive_child() takes the parent lock and sets the iterator
to each positive child in turn.

d_for_each_positive_child_continue() can continue after an existing
dentry, or (when initialised to NULL) behave like
d_for_each_positive_child().  This requires that something prevent the
start dentry from being moved before
d_for_each_positive_child_continue() can take the parent lock -
typically ->i_rwsem.

The use of scoped_guard() in these macros makes it safe to "break" or
"goto" out of the loop - the lock will be dropped in that case.

These are then used everywhere outside of dcache.c and libfs.c where
d_children/d_sib iteration is needed.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/autofs/expire.c     |  7 +----
 fs/ceph/mds_client.c   | 10 +++-----
 fs/coda/cache.c        |  4 +--
 fs/libfs.c             |  4 +--
 fs/nfs/dir.c           |  7 +----
 fs/notify/fsnotify.c   |  7 +----
 include/linux/dcache.h | 58 ++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 66 insertions(+), 31 deletions(-)

diff --git a/fs/autofs/expire.c b/fs/autofs/expire.c
index 909622eeb8a0..ba1a3a2bfc9a 100644
--- a/fs/autofs/expire.c
+++ b/fs/autofs/expire.c
@@ -72,10 +72,7 @@ static int autofs_mount_busy(struct vfsmount *mnt,
 
 static struct dentry *positive_after(struct dentry *p, struct dentry *child)
 {
-	spin_lock(&p->d_lock);
-	child = child ? d_next_sibling(child) : d_first_child(p);
-
-	hlist_for_each_entry_from(child, d_sib) {
+	d_for_each_positive_child_continue(child, p) {
 		spin_lock_nested(&child->d_lock, DENTRY_D_LOCK_NESTED);
 		if (simple_positive(child)) {
 			dget_dlock(child);
@@ -84,8 +81,6 @@ static struct dentry *positive_after(struct dentry *p, struct dentry *child)
 		}
 		spin_unlock(&child->d_lock);
 	}
-	spin_unlock(&p->d_lock);
-
 	return NULL;
 }
 
diff --git a/fs/ceph/mds_client.c b/fs/ceph/mds_client.c
index 3c692ad02c85..5c4e72c3b110 100644
--- a/fs/ceph/mds_client.c
+++ b/fs/ceph/mds_client.c
@@ -2182,14 +2182,10 @@ static bool drop_negative_children(struct dentry *dentry)
 	if (!d_is_dir(dentry))
 		goto out;
 
-	spin_lock(&dentry->d_lock);
-	hlist_for_each_entry(child, &dentry->d_children, d_sib) {
-		if (d_really_is_positive(child)) {
-			all_negative = false;
-			break;
-		}
+	d_for_each_positive_child(child, dentry) {
+		all_negative = false;
+		break;
 	}
-	spin_unlock(&dentry->d_lock);
 
 	if (all_negative)
 		shrink_dcache_parent(dentry);
diff --git a/fs/coda/cache.c b/fs/coda/cache.c
index 970f0022ec52..dca88d749b86 100644
--- a/fs/coda/cache.c
+++ b/fs/coda/cache.c
@@ -92,14 +92,12 @@ static void coda_flag_children(struct dentry *parent, int flag)
 {
 	struct dentry *de;
 
-	spin_lock(&parent->d_lock);
-	hlist_for_each_entry(de, &parent->d_children, d_sib) {
+	d_for_each_positive_child(de, parent) {
 		struct inode *inode = d_inode_rcu(de);
 		/* don't know what to do with negative dentries */
 		if (inode)
 			coda_flag_inode(inode, flag);
 	}
-	spin_unlock(&parent->d_lock);
 }
 
 void coda_flag_inode_children(struct inode *inode, int flag)
diff --git a/fs/libfs.c b/fs/libfs.c
index 7cd816b8e2a0..8e99067079e8 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -768,8 +768,7 @@ int simple_empty(struct dentry *dentry)
 	struct dentry *child;
 	int ret = 0;
 
-	spin_lock(&dentry->d_lock);
-	hlist_for_each_entry(child, &dentry->d_children, d_sib) {
+	d_for_each_positive_child(child, dentry) {
 		spin_lock_nested(&child->d_lock, DENTRY_D_LOCK_NESTED);
 		if (simple_positive(child)) {
 			spin_unlock(&child->d_lock);
@@ -779,7 +778,6 @@ int simple_empty(struct dentry *dentry)
 	}
 	ret = 1;
 out:
-	spin_unlock(&dentry->d_lock);
 	return ret;
 }
 EXPORT_SYMBOL(simple_empty);
diff --git a/fs/nfs/dir.c b/fs/nfs/dir.c
index bba5d996413c..3aa874626299 100644
--- a/fs/nfs/dir.c
+++ b/fs/nfs/dir.c
@@ -1494,11 +1494,7 @@ static void nfs_clear_verifier_directory(struct inode *dir)
 	nfs_unset_verifier_delegated(&this_parent->d_time);
 	spin_unlock(&this_parent->d_lock);
 
-	spin_lock(&this_parent->d_lock);
-	dentry = d_first_child(this_parent);
-	hlist_for_each_entry_from(dentry, d_sib) {
-		if (unlikely(dentry->d_flags & DCACHE_DENTRY_CURSOR))
-			continue;
+	d_for_each_positive_child(dentry, this_parent) {
 		inode = d_inode_rcu(dentry);
 		if (inode &&
 		    NFS_PROTO(inode)->have_delegation(inode, FMODE_READ, 0))
@@ -1507,7 +1503,6 @@ static void nfs_clear_verifier_directory(struct inode *dir)
 		nfs_unset_verifier_delegated(&dentry->d_time);
 		spin_unlock(&dentry->d_lock);
 	}
-	spin_unlock(&this_parent->d_lock);
 }
 
 /**
diff --git a/fs/notify/fsnotify.c b/fs/notify/fsnotify.c
index 7e2f330fd283..90a2121fc54a 100644
--- a/fs/notify/fsnotify.c
+++ b/fs/notify/fsnotify.c
@@ -85,16 +85,11 @@ void fsnotify_set_children_dentry_flags(struct inode *inode)
 		/* run all of the children of the original inode and fix their
 		 * d_flags to indicate parental interest (their parent is the
 		 * original inode) */
-		spin_lock(&alias->d_lock);
-		hlist_for_each_entry(child, &alias->d_children, d_sib) {
-			if (!child->d_inode)
-				continue;
-
+		d_for_each_positive_child(child, alias) {
 			spin_lock_nested(&child->d_lock, DENTRY_D_LOCK_NESTED);
 			child->d_flags |= DCACHE_FSNOTIFY_PARENT_WATCHED;
 			spin_unlock(&child->d_lock);
 		}
-		spin_unlock(&alias->d_lock);
 	}
 	spin_unlock(&inode->i_lock);
 }
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index 64d64bab16fe..cabf05e74b1f 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -656,6 +656,64 @@ static inline struct dentry *d_next_sibling(const struct dentry *dentry)
 	return hlist_entry_safe(dentry->d_sib.next, struct dentry, d_sib);
 }
 
+static inline struct dentry *d_next_positive(struct dentry *child)
+{
+	do {
+		child = d_next_sibling(child);
+	} while (child && !d_really_is_positive(child));
+	return child;
+}
+
+static inline struct dentry *d_first_positive(const struct dentry *parent,
+					      struct dentry *child)
+{
+	if (!child)
+		child = d_first_child(parent);
+	else
+		child = d_next_sibling(child);
+	if (child && !d_really_is_positive(child))
+		child = d_next_positive(child);
+	return child;
+}
+
+/**
+ * d_for_each_positive_child - iterate over positive children in the dcache
+ * @child: iterator dentry
+ * @parent: dentry of parent
+ *
+ * Iteratively set @child to each positive child of @parent.
+ * @parent->d_lock should NOT be held.
+ * @child may no longer be positive when the caller examines it
+ * so care is still needed which could involve locking the child
+ * or using d_inode_rcu() to access the inode.
+ *
+ * DCACHE_DENTRY_CURSOR dentries will never be returned, only true children
+ * which have at some point in the past been positive.
+ */
+#define d_for_each_positive_child(child, parent)			\
+	scoped_guard(spinlock, &parent->d_lock)				\
+		for (child = d_first_positive(parent, NULL); child;	\
+		     child = d_next_positive(child))
+
+/**
+ * d_for_each_positive_child_continue - iterate over remaining positive children
+ * @child: iterator dentry and starting point.
+ * @parent: dentry of parent
+ *
+ * If @child is %NULL this behaves identically to d_for_each_positive_child().
+ * Otherwise @child must be an existing child of %parent and subsequent children
+ * in the d_children list of @parent are returned.
+ *
+ * Safely using this requires that something prevents @child from being
+ * renamed to a different directory before we get the lock.  Holding
+ * i_rwsem on the @parent is sufficient.
+ *
+ */
+#define d_for_each_positive_child_continue(child, parent)		\
+	scoped_guard(spinlock, &parent->d_lock)				\
+		for (child = d_first_positive(parent, child); child;	\
+		     child = d_next_positive(child))
+
 void set_default_d_op(struct super_block *, const struct dentry_operations *);
 struct dentry *d_make_persistent(struct dentry *, struct inode *);
 void d_make_discardable(struct dentry *dentry);
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 06/18] fsnotify: don't hold a spin_lock across fsnotify_recalc_mask() calls.

[NeilBrown]

From: NeilBrown <neil@brown.name>

fsnotify_recalc_mask() is normally called without any spin_lock held.
fsnotify_group_lock() (a mutex) is often held, or else
   srcu_read_lock(&fsnotify_mark_srcu)
is held.  Either of these are sufficient to keep the mark and the
connector stable.

However dnotify_recalc_inode_mask() does hold a spin_lock
when calling fsnotify_recalc_mask().  This is problematic as
fsnotify_recalc_mask() can walk the d_children list which can be long.
Holding a spin_lock prevents us from using cond_resched() in that walk.

So change dnotify_recalc_inode_mask() to NOT call fsnotify_recalc_mask()
but instead return a flag indicating if it needs to be called.  Callers
check this flag and call fsnotify_recalc_mask() after dropping the
spin_lock.

As part of this, dnotify_handle_event() now only calls
dnotify_recalc_inode_mask() once rather than possibly several times
during the loop.

After this change, the only spin_lock held across the d_children walk
other than the parent's d_lock is the inode's i_lock.  This will be
addressed in a later patch.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/notify/dnotify/dnotify.c | 32 ++++++++++++++++++++++----------
 1 file changed, 22 insertions(+), 10 deletions(-)

diff --git a/fs/notify/dnotify/dnotify.c b/fs/notify/dnotify/dnotify.c
index 9fb73bafd41d..d8aff13097c2 100644
--- a/fs/notify/dnotify/dnotify.c
+++ b/fs/notify/dnotify/dnotify.c
@@ -54,12 +54,13 @@ struct dnotify_mark {
 /*
  * When a process starts or stops watching an inode the set of events which
  * dnotify cares about for that inode may change.  This function runs the
- * list of everything receiving dnotify events about this directory and calculates
- * the set of all those events.  After it updates what dnotify is interested in
- * it calls the fsnotify function so it can update the set of all events relevant
+ * list of everything receiving dnotify events about this directory and
+ * calculates the set of all those events.  After it updates what dnotify is
+ * interested in it returns true if the fsnotify function should be called
+ * (after dropping the lock) so it can update the set of all events relevant
  * to this inode.
  */
-static void dnotify_recalc_inode_mask(struct fsnotify_mark *fsn_mark)
+static bool dnotify_recalc_inode_mask(struct fsnotify_mark *fsn_mark)
 {
 	__u32 new_mask = 0;
 	struct dnotify_struct *dn;
@@ -72,10 +73,9 @@ static void dnotify_recalc_inode_mask(struct fsnotify_mark *fsn_mark)
 	for (dn = dn_mark->dn; dn != NULL; dn = dn->dn_next)
 		new_mask |= (dn->dn_mask & ~FS_DN_MULTISHOT);
 	if (fsn_mark->mask == new_mask)
-		return;
+		return false;
 	fsn_mark->mask = new_mask;
-
-	fsnotify_recalc_mask(fsn_mark->connector);
+	return true;
 }
 
 /*
@@ -94,6 +94,7 @@ static int dnotify_handle_event(struct fsnotify_mark *inode_mark, u32 mask,
 	struct dnotify_struct *dn;
 	struct dnotify_struct **prev;
 	struct fown_struct *fown;
+	bool need_recalc = false;
 	__u32 test_mask = mask & ~FS_EVENT_ON_CHILD;
 
 	/* not a dir, dnotify doesn't care */
@@ -116,11 +117,15 @@ static int dnotify_handle_event(struct fsnotify_mark *inode_mark, u32 mask,
 		else {
 			*prev = dn->dn_next;
 			kmem_cache_free(dnotify_struct_cache, dn);
-			dnotify_recalc_inode_mask(inode_mark);
+			need_recalc = true;
 		}
 	}
 
+	if (need_recalc)
+		need_recalc = dnotify_recalc_inode_mask(inode_mark);
 	spin_unlock(&inode_mark->lock);
+	if (need_recalc)
+		fsnotify_recalc_mask(inode_mark->connector);
 
 	return 0;
 }
@@ -156,6 +161,7 @@ void dnotify_flush(struct file *filp, fl_owner_t id)
 	struct dnotify_struct **prev;
 	struct inode *inode;
 	bool free = false;
+	bool need_recalc = false;
 
 	inode = file_inode(filp);
 	if (!S_ISDIR(inode->i_mode))
@@ -174,13 +180,16 @@ void dnotify_flush(struct file *filp, fl_owner_t id)
 		if ((dn->dn_owner == id) && (dn->dn_filp == filp)) {
 			*prev = dn->dn_next;
 			kmem_cache_free(dnotify_struct_cache, dn);
-			dnotify_recalc_inode_mask(fsn_mark);
+			if (dnotify_recalc_inode_mask(fsn_mark))
+				need_recalc = true;
 			break;
 		}
 		prev = &dn->dn_next;
 	}
 
 	spin_unlock(&fsn_mark->lock);
+	if (need_recalc)
+		fsnotify_recalc_mask(fsn_mark->connector);
 
 	/* nothing else could have found us thanks to the dnotify_groups
 	   mark_mutex */
@@ -265,6 +274,7 @@ int fcntl_dirnotify(int fd, struct file *filp, unsigned int arg)
 	fl_owner_t id = current->files;
 	struct file *f = NULL;
 	int destroy = 0, error = 0;
+	bool need_recalc = false;
 	__u32 mask;
 
 	/* we use these to tell if we need to kfree */
@@ -377,9 +387,11 @@ int fcntl_dirnotify(int fd, struct file *filp, unsigned int arg)
 	else if (error == -EEXIST)
 		error = 0;
 
-	dnotify_recalc_inode_mask(fsn_mark);
+	need_recalc = dnotify_recalc_inode_mask(fsn_mark);
 out:
 	spin_unlock(&fsn_mark->lock);
+	if (need_recalc)
+		fsnotify_recalc_mask(fsn_mark->connector);
 
 	if (destroy)
 		fsnotify_detach_mark(fsn_mark);
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 07/18] fsnotify: reduce i_lock hold time in fsnotify_set_children_dentry_flags()

[NeilBrown]

From: NeilBrown <neil@brown.name>

Rather than hold i_lock across a d_children walk, dget() a reference to
the dentry and drop the i_lock before the walk.  This is easily done
with d_find_alias().

This requires that we dput() which can sleep.  Now that no locks are
held across calls to fsnotify_set_children_dentry_flags(), this is safe.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/notify/fsnotify.c | 33 +++++++++++++++++----------------
 1 file changed, 17 insertions(+), 16 deletions(-)

diff --git a/fs/notify/fsnotify.c b/fs/notify/fsnotify.c
index 90a2121fc54a..4a383d4d8a7b 100644
--- a/fs/notify/fsnotify.c
+++ b/fs/notify/fsnotify.c
@@ -71,27 +71,28 @@ void fsnotify_sb_free(struct super_block *sb)
  */
 void fsnotify_set_children_dentry_flags(struct inode *inode)
 {
-	struct dentry *alias;
+	struct dentry *alias, *child;
 
 	if (!S_ISDIR(inode->i_mode))
 		return;
 
-	spin_lock(&inode->i_lock);
-	/* run all of the dentries associated with this inode.  Since this is a
-	 * directory, there damn well better only be one item on this list */
-	for_each_alias(alias, inode) {
-		struct dentry *child;
-
-		/* run all of the children of the original inode and fix their
-		 * d_flags to indicate parental interest (their parent is the
-		 * original inode) */
-		d_for_each_positive_child(child, alias) {
-			spin_lock_nested(&child->d_lock, DENTRY_D_LOCK_NESTED);
-			child->d_flags |= DCACHE_FSNOTIFY_PARENT_WATCHED;
-			spin_unlock(&child->d_lock);
-		}
+	/* Find the dentry for inode - there can only be one */
+	alias = d_find_alias(inode);
+
+	if (!alias)
+		return;
+
+	/*
+	 * run all of the children of the original inode and fix their
+	 * d_flags to indicate parental interest (their parent is the
+	 * original inode)
+	 */
+	d_for_each_positive_child(child, alias) {
+		spin_lock_nested(&child->d_lock, DENTRY_D_LOCK_NESTED);
+		child->d_flags |= DCACHE_FSNOTIFY_PARENT_WATCHED;
+		spin_unlock(&child->d_lock);
 	}
-	spin_unlock(&inode->i_lock);
+	dput(alias);
 }
 
 /*
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 08/18] libfs: simplify scan_positives()

[NeilBrown]

From: NeilBrown <neil@brown.name>

This patch removes explicit use of hlist_node from scan_positives() and
callers, and consistently uses struct dentry instead.

Previously scan_positives() had two args which were closely related: p
and last.
If last was not NULL, p was precisely &last->d_sib.next.
If last WAS NULL, then p was
   &cursor->d_parent->d_children.first or
   &cursor->d_sib.next

If, for the final case, we pass 'cursor' as 'last', then we only need
'last' not 'p'.  For this to work we must dget(cursor) before passing
it, as scan_positives() calls dput() on last.

So now to scan from the start, pass NULL; to scan from a particular
dentry, pass that dentry.

Note that scan_positives() can be given a "last' which is unhashed.
This happens if, for example, dcache_dir_lseek is called to seek beyond
the end of the directory - thus leaving the cursor detached - and then
dcache_readdir() is called.  "next" will be the detached cursor which
will be passed in to scan_positives() as "last".  d_next_sibling()
of this will be NULL.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/libfs.c | 32 ++++++++++++++++----------------
 1 file changed, 16 insertions(+), 16 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index 8e99067079e8..c2b09e72cbd8 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -103,18 +103,23 @@ EXPORT_SYMBOL(dcache_dir_close);
  * We are looking for <count>th positive after <p>; if
  * found, dentry is grabbed and returned to caller.
  * If no such element exists, NULL is returned.
+ * If last has been removed from the d_children list
+ * (i.e. last->d_sib is unhashed) then it is treated like
+ * the last element of the list and %NULL is returned.
  */
 static struct dentry *scan_positives(struct dentry *cursor,
-					struct hlist_node **p,
-					loff_t count,
-					struct dentry *last)
+				     struct dentry *last,
+				     loff_t count)
 {
 	struct dentry *dentry = cursor->d_parent, *found = NULL;
+	struct dentry *next;
 
 	spin_lock(&dentry->d_lock);
-	while (*p) {
-		struct dentry *d = hlist_entry(*p, struct dentry, d_sib);
-		p = &d->d_sib.next;
+	next = last ? d_next_sibling(last) : d_first_child(dentry);
+	while (next) {
+		struct dentry *d = next;
+
+		next = d_next_sibling(next);
 		// we must at least skip cursors, to avoid livelocks
 		if (d->d_flags & DCACHE_DENTRY_CURSOR)
 			continue;
@@ -129,10 +134,10 @@ static struct dentry *scan_positives(struct dentry *cursor,
 		}
 		if (need_resched()) {
 			hlist_move_behind(&cursor->d_sib, &d->d_sib);
-			p = &cursor->d_sib.next;
 			spin_unlock(&dentry->d_lock);
 			cond_resched();
 			spin_lock(&dentry->d_lock);
+			next = d_next_sibling(cursor);
 		}
 	}
 	spin_unlock(&dentry->d_lock);
@@ -161,8 +166,7 @@ loff_t dcache_dir_lseek(struct file *file, loff_t offset, int whence)
 		inode_lock_shared(dentry->d_inode);
 
 		if (offset > 2)
-			to = scan_positives(cursor, &dentry->d_children.first,
-					    offset - 2, NULL);
+			to = scan_positives(cursor, NULL, offset - 2);
 		spin_lock(&dentry->d_lock);
 		if (to)
 			hlist_move_behind(&cursor->d_sib, &to->d_sib);
@@ -190,23 +194,19 @@ int dcache_readdir(struct file *file, struct dir_context *ctx)
 	struct dentry *dentry = file->f_path.dentry;
 	struct dentry *cursor = file->private_data;
 	struct dentry *next = NULL;
-	struct hlist_node **p;
 
 	if (!dir_emit_dots(file, ctx))
 		return 0;
 
-	if (ctx->pos == 2)
-		p = &dentry->d_children.first;
-	else
-		p = &cursor->d_sib.next;
+	if (ctx->pos > 2)
+		next = dget(cursor);
 
-	while ((next = scan_positives(cursor, p, 1, next)) != NULL) {
+	while ((next = scan_positives(cursor, next, 1)) != NULL) {
 		if (!dir_emit(ctx, next->d_name.name, next->d_name.len,
 			      d_inode(next)->i_ino,
 			      fs_umode_to_dtype(d_inode(next)->i_mode)))
 			break;
 		ctx->pos++;
-		p = &next->d_sib.next;
 	}
 	spin_lock(&dentry->d_lock);
 	if (next)
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 09/18] libfs: change scan_positives() to use d_for_each_positive_child_continue()

[NeilBrown]

From: NeilBrown <neil@brown.name>

Using d_for_each_positive_child_continue() simplifies this code
slightly and make is easier to read.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/libfs.c | 15 +++------------
 1 file changed, 3 insertions(+), 12 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index c2b09e72cbd8..398fae675207 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -112,17 +112,9 @@ static struct dentry *scan_positives(struct dentry *cursor,
 				     loff_t count)
 {
 	struct dentry *dentry = cursor->d_parent, *found = NULL;
-	struct dentry *next;
+	struct dentry *d = last;
 
-	spin_lock(&dentry->d_lock);
-	next = last ? d_next_sibling(last) : d_first_child(dentry);
-	while (next) {
-		struct dentry *d = next;
-
-		next = d_next_sibling(next);
-		// we must at least skip cursors, to avoid livelocks
-		if (d->d_flags & DCACHE_DENTRY_CURSOR)
-			continue;
+	d_for_each_positive_child_continue(d, dentry) {
 		if (simple_positive(d) && !--count) {
 			spin_lock_nested(&d->d_lock, DENTRY_D_LOCK_NESTED);
 			if (simple_positive(d))
@@ -134,13 +126,12 @@ static struct dentry *scan_positives(struct dentry *cursor,
 		}
 		if (need_resched()) {
 			hlist_move_behind(&cursor->d_sib, &d->d_sib);
+			d = cursor;
 			spin_unlock(&dentry->d_lock);
 			cond_resched();
 			spin_lock(&dentry->d_lock);
-			next = d_next_sibling(cursor);
 		}
 	}
-	spin_unlock(&dentry->d_lock);
 	dput(last);
 	return found;
 }
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 10/18] libfs: allow scan_positives() to be called without a cursor.

[NeilBrown]

From: NeilBrown <neil@brown.name>

Rather than taking parent from cursor, pass it in explicitly.  And only
cond_sched() if a cursor is available.  This will allow scan_positives()
to be used in place of find_positive_dentry().

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/libfs.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index 398fae675207..21abe0074c77 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -107,11 +107,12 @@ EXPORT_SYMBOL(dcache_dir_close);
  * (i.e. last->d_sib is unhashed) then it is treated like
  * the last element of the list and %NULL is returned.
  */
-static struct dentry *scan_positives(struct dentry *cursor,
+static struct dentry *scan_positives(struct dentry *dentry,
+				     struct dentry *cursor,
 				     struct dentry *last,
 				     loff_t count)
 {
-	struct dentry *dentry = cursor->d_parent, *found = NULL;
+	struct dentry *found = NULL;
 	struct dentry *d = last;
 
 	d_for_each_positive_child_continue(d, dentry) {
@@ -124,7 +125,7 @@ static struct dentry *scan_positives(struct dentry *cursor,
 				break;
 			count = 1;
 		}
-		if (need_resched()) {
+		if (cursor && need_resched()) {
 			hlist_move_behind(&cursor->d_sib, &d->d_sib);
 			d = cursor;
 			spin_unlock(&dentry->d_lock);
@@ -157,7 +158,7 @@ loff_t dcache_dir_lseek(struct file *file, loff_t offset, int whence)
 		inode_lock_shared(dentry->d_inode);
 
 		if (offset > 2)
-			to = scan_positives(cursor, NULL, offset - 2);
+			to = scan_positives(dentry, cursor, NULL, offset - 2);
 		spin_lock(&dentry->d_lock);
 		if (to)
 			hlist_move_behind(&cursor->d_sib, &to->d_sib);
@@ -192,7 +193,7 @@ int dcache_readdir(struct file *file, struct dir_context *ctx)
 	if (ctx->pos > 2)
 		next = dget(cursor);
 
-	while ((next = scan_positives(cursor, next, 1)) != NULL) {
+	while ((next = scan_positives(dentry, cursor, next, 1)) != NULL) {
 		if (!dir_emit(ctx, next->d_name.name, next->d_name.len,
 			      d_inode(next)->i_ino,
 			      fs_umode_to_dtype(d_inode(next)->i_mode)))
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 11/18] libfs: replace find_positive_dentry() with scan_positives()

[NeilBrown]

From: NeilBrown <neil@brown.name>

scan_positives() can be used in place of find_positive_dentry().

This makes offset_iterate_dir() simpler as 'next' is no longer needed.

offset_dir_lookup() needs an extra loop to find a child on which a ref
can be taken, as scan_positives() requires a dentry with a ref.  I think
this makes a cleaner separation as the RCU read lock no longer needs to
be held over the scan call.  This will be important in a future patch.

Using scan_positives() means, after the next patch, that cursors can
appear on the d_sib list, so when finding a dentry from the offset,
which might be dead by now (dentry_kill()) we need to step over any
cursors to find something we can take a reference on.  This requires
parent->d_lock as cursors are not RCU-safe.

We add lockref_get_not_dead_nested() so that we can opportunistically
get a ref on a child while holding the lock on the parent.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/libfs.c              | 58 ++++++++++++++++-------------------------
 include/linux/lockref.h | 12 ++++++++-
 lib/lockref.c           | 10 ++++---
 3 files changed, 40 insertions(+), 40 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index 21abe0074c77..44e8dec51237 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -438,47 +438,39 @@ static loff_t offset_dir_llseek(struct file *file, loff_t offset, int whence)
 	return vfs_setpos(file, offset, LONG_MAX);
 }
 
-static struct dentry *find_positive_dentry(struct dentry *parent,
-					   struct dentry *dentry,
-					   bool next)
-{
-	struct dentry *found = NULL;
-
-	spin_lock(&parent->d_lock);
-	if (next)
-		dentry = d_next_sibling(dentry);
-	else if (!dentry)
-		dentry = d_first_child(parent);
-	hlist_for_each_entry_from(dentry, d_sib) {
-		if (!simple_positive(dentry))
-			continue;
-		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
-		if (simple_positive(dentry))
-			found = dget_dlock(dentry);
-		spin_unlock(&dentry->d_lock);
-		if (likely(found))
-			break;
-	}
-	spin_unlock(&parent->d_lock);
-	return found;
-}
-
 static noinline_for_stack struct dentry *
 offset_dir_lookup(struct dentry *parent, loff_t offset)
 {
 	struct inode *inode = d_inode(parent);
 	struct offset_ctx *octx = inode->i_op->get_offset_ctx(inode);
-	struct dentry *child, *found = NULL;
+	struct dentry *found = NULL;
 
 	MA_STATE(mas, &octx->mt, offset, offset);
 
 	if (offset == DIR_OFFSET_FIRST)
-		found = find_positive_dentry(parent, NULL, false);
+		found = scan_positives(parent, NULL, NULL, 1);
 	else {
 		rcu_read_lock();
-		child = mas_find_rev(&mas, DIR_OFFSET_MIN);
-		found = find_positive_dentry(parent, child, false);
+		spin_lock(&parent->d_lock);
+		found = mas_find_rev(&mas, DIR_OFFSET_MIN);
+		if (found) {
+			/*
+			 * parent lock ensures found is still on
+			 * the d_sib list, but it could be have been marked dead.
+			 * So we need to find something we can get a ref on,
+			 * which isn't a cursor, and isn't anything NORCU.
+			 */
+			hlist_for_each_entry_from(found, d_sib) {
+				if (!(found->d_flags & DCACHE_NORCU) &&
+				    lockref_get_not_dead_nested(&found->d_lockref,
+								DENTRY_D_LOCK_NESTED))
+					break;
+			}
+		}
+		spin_unlock(&parent->d_lock);
 		rcu_read_unlock();
+		if (found && !simple_positive(found))
+			found = scan_positives(parent, NULL, found, 1);
 	}
 	return found;
 }
@@ -500,18 +492,14 @@ static void offset_iterate_dir(struct file *file, struct dir_context *ctx)
 	if (!dentry)
 		goto out_eod;
 	while (true) {
-		struct dentry *next;
-
 		ctx->pos = dentry2offset(dentry);
 		if (!offset_dir_emit(ctx, dentry))
 			break;
 
-		next = find_positive_dentry(dir, dentry, true);
-		dput(dentry);
+		dentry = scan_positives(dir, NULL, dentry, 1);
 
-		if (!next)
+		if (!dentry)
 			goto out_eod;
-		dentry = next;
 	}
 	dput(dentry);
 	return;
diff --git a/include/linux/lockref.h b/include/linux/lockref.h
index 6ded24cdb4a8..9da4fbc2cd13 100644
--- a/include/linux/lockref.h
+++ b/include/linux/lockref.h
@@ -52,7 +52,17 @@ bool lockref_get_not_zero(struct lockref *lockref);
 bool lockref_put_or_lock(struct lockref *lockref) __cond_acquires(false, &lockref->lock);
 
 void lockref_mark_dead(struct lockref *lockref);
-bool lockref_get_not_dead(struct lockref *lockref);
+bool lockref_get_not_dead_nested(struct lockref *lockref, int subclass);
+/**
+ * lockref_get_not_dead - Increments count unless the ref is dead
+ * @lockref: pointer to lockref structure
+ *
+ * Return: 1 if count updated successfully or 0 if lockref was dead
+ */
+static inline bool lockref_get_not_dead(struct lockref *lockref)
+{
+	return lockref_get_not_dead_nested(lockref, 0);
+}
 
 /* Must be called under spinlock for reliable results */
 static inline bool __lockref_is_dead(const struct lockref *l)
diff --git a/lib/lockref.c b/lib/lockref.c
index 5d8e3ef3860e..dddd26100a51 100644
--- a/lib/lockref.c
+++ b/lib/lockref.c
@@ -136,11 +136,13 @@ void lockref_mark_dead(struct lockref *lockref)
 EXPORT_SYMBOL(lockref_mark_dead);
 
 /**
- * lockref_get_not_dead - Increments count unless the ref is dead
+ * lockref_get_not_dead_nested - Increments count unless the ref is dead
  * @lockref: pointer to lockref structure
+ * @subclass: lockdep class for taking ->lock
+ *
  * Return: 1 if count updated successfully or 0 if lockref was dead
  */
-bool lockref_get_not_dead(struct lockref *lockref)
+bool lockref_get_not_dead_nested(struct lockref *lockref, int subclass)
 {
 	bool retval = false;
 
@@ -152,7 +154,7 @@ bool lockref_get_not_dead(struct lockref *lockref)
 		return true;
 	);
 
-	spin_lock(&lockref->lock);
+	spin_lock_nested(&lockref->lock, subclass);
 	if (lockref->count >= 0) {
 		lockref->count++;
 		retval = true;
@@ -160,4 +162,4 @@ bool lockref_get_not_dead(struct lockref *lockref)
 	spin_unlock(&lockref->lock);
 	return retval;
 }
-EXPORT_SYMBOL(lockref_get_not_dead);
+EXPORT_SYMBOL(lockref_get_not_dead_nested);
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 12/18] autofs: don't hold ->lookup_lock in get_next_positive_*

[NeilBrown]

From: NeilBrown <neil@brown.name>

get_next_positive_subdir() and get_next_positive_dentry() currently hold
->lookup_lock while walking the d_children list, which a subsequent
patch will add schedule points to.  So this spinlock will be a problem.

The only data structures that a protected by ->lookup_lock are the
  sbi->expiring and sbi->active_list
lists of inodes.  Neither of these are accessed in these functions,
so the lock cannot be needed.

I think the presence of these locks is a hold-over from a previous
locking scheme.

Signed-Off-By: NeilBrown <neil@brown.name>
---
 fs/autofs/expire.c | 6 ------
 1 file changed, 6 deletions(-)

diff --git a/fs/autofs/expire.c b/fs/autofs/expire.c
index ba1a3a2bfc9a..b6937c5936a5 100644
--- a/fs/autofs/expire.c
+++ b/fs/autofs/expire.c
@@ -90,12 +90,9 @@ static struct dentry *positive_after(struct dentry *p, struct dentry *child)
 static struct dentry *get_next_positive_subdir(struct dentry *prev,
 					       struct dentry *root)
 {
-	struct autofs_sb_info *sbi = autofs_sbi(root->d_sb);
 	struct dentry *q;
 
-	spin_lock(&sbi->lookup_lock);
 	q = positive_after(root, prev);
-	spin_unlock(&sbi->lookup_lock);
 	dput(prev);
 	return q;
 }
@@ -106,13 +103,11 @@ static struct dentry *get_next_positive_subdir(struct dentry *prev,
 static struct dentry *get_next_positive_dentry(struct dentry *prev,
 					       struct dentry *root)
 {
-	struct autofs_sb_info *sbi = autofs_sbi(root->d_sb);
 	struct dentry *p = prev, *ret = NULL, *d = NULL;
 
 	if (prev == NULL)
 		return dget(root);
 
-	spin_lock(&sbi->lookup_lock);
 	while (1) {
 		struct dentry *parent;
 
@@ -123,7 +118,6 @@ static struct dentry *get_next_positive_dentry(struct dentry *prev,
 		d = p;
 		p = parent;
 	}
-	spin_unlock(&sbi->lookup_lock);
 	dput(prev);
 	return ret;
 }
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 13/18] VFS: don't move dentries in d_sib list when they have the same parent

[NeilBrown]

From: NeilBrown <neil@brown.name>

When __d_move() moves or exchanges dentries it currently always moves
both dentries to the head of the ->d_children list of the respective
parents.

When they have the same parent, this simply moves them from where they
are to the start in the same list.  So it achieves nothing useful.

A future patch will allow d_for_each_positive_child() to drop and retake
the parent's d_lock during the iteration.  With the current __d_move
behaviour this would allow a dentry to be moved to the front and so
missed, even though it is still in the same directory.  This might be
unexpected.

With this change the only dentries that d_for_each_positive_child()
might miss are those moved out of the directory, or those moved in after
the iteration started.  These are unavoidable and should not be
unexpected.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/dcache.c | 20 ++++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index ae726f3ff0cb..50fbbcceca01 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -3052,6 +3052,9 @@ static void copy_name(struct dentry *dentry, struct dentry *target)
  * entries should not be moved in this way. Caller must hold rename_lock, the
  * i_rwsem of the source and target directories (exclusively), and the sb->
  * s_vfs_rename_mutex if they differ. See lock_rename().
+ *
+ * If @dentry and @target have the same parent, then neither is
+ * moved in the d_sib list.
  */
 static void __d_move(struct dentry *dentry, struct dentry *target,
 		     bool exchange)
@@ -3119,15 +3122,20 @@ static void __d_move(struct dentry *dentry, struct dentry *target,
 	} else {
 		target->d_parent = old_parent;
 		swap_names(dentry, target);
-		if (!hlist_unhashed(&target->d_sib))
-			__hlist_del(&target->d_sib);
-		hlist_add_head(&target->d_sib, &target->d_parent->d_children);
+		if (target->d_parent != dentry->d_parent) {
+			if (!hlist_unhashed(&target->d_sib))
+				__hlist_del(&target->d_sib);
+			hlist_add_head(&target->d_sib,
+				       &target->d_parent->d_children);
+		}
 		__d_rehash(target);
 		fsnotify_update_flags(target);
 	}
-	if (!hlist_unhashed(&dentry->d_sib))
-		__hlist_del(&dentry->d_sib);
-	hlist_add_head(&dentry->d_sib, &dentry->d_parent->d_children);
+	if (dentry->d_parent != old_parent) {
+		if (!hlist_unhashed(&dentry->d_sib))
+			__hlist_del(&dentry->d_sib);
+		hlist_add_head(&dentry->d_sib, &dentry->d_parent->d_children);
+	}
 
 	/*
 	 * Adjust parent refcounts if either d_children ended up empty.
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 14/18] Call cond_reshed() as needed in d_for_each_positive_child().

[NeilBrown]

From: NeilBrown <neil@brown.name>

There are reports that large numbers of negative dentries can lead to
soft lockups when walking the d_children/d_sib list, particularly in
fsnotify_set_children_dentry_flags(). (See link below)

This can be addressed by allowing a schedule during the walk in the same
way that scan_positives() (in libfs.c) already does.

As we now walk the list in common code, we can add that schedule call to
all places that walk the list using d_for_each_positive_child iterators.

Doing this involves using an on-stack dentry (about 330 bytes) which is
not standard practice but should be safe since

Commit 3df5153c5f12 ("make cursors NORCU")

made cursors NORCU, confirming that they can safely be released without
waiting.  Also importantly nothing ever takes a reference on a cursor
that it doesn't own.

To facilitate this, a new __d_init() is split out of __d_alloc() and
used in d_init_cursor() which can be called on an on-stack dentry as is
done in the new d_next_sibling_sched().

d_for_each_positive_child*() now use d_next_sibling_sched() if appropriate
and they now assert they might_sleep().

Note that d_walk() also walks this list and does not use the new helper.
Some instances of d_walk() do abort when a resched is needed, others do
not.  This patch does not help with those.

Link https://lwn.net/Articles/1079407/
Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/dcache.c            | 107 ++++++++++++++++++++++++++++++++++-------
 include/linux/dcache.h |  23 ++++++---
 2 files changed, 106 insertions(+), 24 deletions(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index 50fbbcceca01..38a726472d4a 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -1885,6 +1885,24 @@ void d_invalidate(struct dentry *dentry)
 }
 EXPORT_SYMBOL(d_invalidate);
 
+static void __d_init(struct dentry *dentry, struct super_block *sb)
+{
+	dentry->d_flags = 0;
+	lockref_init(&dentry->d_lockref);
+	seqcount_spinlock_init(&dentry->d_seq, &dentry->d_lock);
+	dentry->d_inode = NULL;
+	dentry->d_parent = dentry;
+	dentry->d_sb = sb;
+	dentry->d_op = sb->__s_d_op;
+	dentry->d_flags = sb->s_d_flags;
+	dentry->d_fsdata = NULL;
+	INIT_HLIST_BL_NODE(&dentry->d_hash);
+	INIT_LIST_HEAD(&dentry->d_lru);
+	INIT_HLIST_HEAD(&dentry->d_children);
+	dentry->waiters = NULL;
+	INIT_HLIST_NODE(&dentry->d_sib);
+}
+
 /**
  * __d_alloc - allocate a dcache entry
  * @sb: filesystem it will belong to
@@ -1894,7 +1912,6 @@ EXPORT_SYMBOL(d_invalidate);
  * available. On a success the dentry is returned. The name passed in is
  * copied and the copy passed in may be reused after this call.
  */
- 
 static struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
 {
 	struct dentry *dentry;
@@ -1922,14 +1939,14 @@ static struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
 		p = kmalloc_flex(*p, name, name->len + 1,
 				 GFP_KERNEL_ACCOUNT | __GFP_RECLAIMABLE);
 		if (!p) {
-			kmem_cache_free(dentry_cache, dentry); 
+			kmem_cache_free(dentry_cache, dentry);
 			return NULL;
 		}
 		atomic_set(&p->count, 1);
 		dname = p->name;
 	} else  {
 		dname = dentry->d_shortname.string;
-	}	
+	}
 
 	dentry->__d_name.len = name->len;
 	dentry->__d_name.hash = name->hash;
@@ -1939,20 +1956,7 @@ static struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
 	/* Make sure we always see the terminating NUL character */
 	smp_store_release(&dentry->__d_name.name, dname); /* ^^^ */
 
-	dentry->d_flags = 0;
-	lockref_init(&dentry->d_lockref);
-	seqcount_spinlock_init(&dentry->d_seq, &dentry->d_lock);
-	dentry->d_inode = NULL;
-	dentry->d_parent = dentry;
-	dentry->d_sb = sb;
-	dentry->d_op = sb->__s_d_op;
-	dentry->d_flags = sb->s_d_flags;
-	dentry->d_fsdata = NULL;
-	INIT_HLIST_BL_NODE(&dentry->d_hash);
-	INIT_LIST_HEAD(&dentry->d_lru);
-	INIT_HLIST_HEAD(&dentry->d_children);
-	dentry->waiters = NULL;
-	INIT_HLIST_NODE(&dentry->d_sib);
+	__d_init(dentry, sb);
 
 	if (dentry->d_op && dentry->d_op->d_init) {
 		err = dentry->d_op->d_init(dentry);
@@ -1969,6 +1973,75 @@ static struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
 	return dentry;
 }
 
+/**
+ * d_init_cursor - initialise an on-stack dentry cursor
+ * @dentry: the dentry to be initialised
+ * @parent: dentry of parent where cursor will be used.
+ *
+ * A DCACHE_DENTRY_CURSOR is initalised for use in marking
+ * a place in the d_children/d_sib list.  While sb-related
+ * fields are filled in, they should never be used.
+ * The filesystems d_init is not called and a final d_put()
+ * should not be called, else d_release would be called.
+ */
+static void d_init_cursor(struct dentry *dentry, struct dentry *parent)
+{
+	const struct qstr *name = &slash_name;
+	char *dname;
+
+	/*
+	 * We guarantee that the inline name is always NUL-terminated.
+	 * This way the memcpy() done by the name switching in rename
+	 * will still always have a NUL at the end, even if we might
+	 * be overwriting an internal NUL character
+	 */
+	dentry->d_shortname.string[DNAME_INLINE_LEN-1] = 0;
+	name = &slash_name;
+	dname = dentry->d_shortname.string;
+
+	dentry->__d_name.len = name->len;
+	dentry->__d_name.hash = name->hash;
+	memcpy(dname, name->name, name->len);
+	dname[name->len] = 0;
+
+	/* Make sure we always see the terminating NUL character */
+	smp_store_release(&dentry->__d_name.name, dname); /* ^^^ */
+
+	__d_init(dentry, parent->d_sb);
+	dentry->d_parent = parent;
+	dentry->d_flags |= DCACHE_DENTRY_CURSOR | DCACHE_NORCU;
+}
+
+/**
+ * d_next_sibling_sched - return next sibling, but schedule() first
+ * @child:  current child
+ *
+ * This behaves like d_next_sibling(), but drops the parent d_lock
+ * and calls cond_resched() to avoid any soft-lockup.  A cursor
+ * is inserted as place holder.
+ *
+ * Caller must hold the parents d_lock, and must hold a counted
+ * reference on the parent.
+ *
+ * Returns: the next sibling, or NULL if there is none.
+ */
+struct dentry *d_next_sibling_sched(struct dentry *child)
+__must_hold(&child->d_parent->d_lock)
+{
+	struct dentry cursor;
+
+	d_init_cursor(&cursor, child->d_parent);
+	hlist_add_behind(&cursor.d_sib, &child->d_sib);
+	spin_unlock(&cursor.d_parent->d_lock);
+	cond_resched();
+	spin_lock(&cursor.d_parent->d_lock);
+	child = d_next_sibling(&cursor);
+	d_detach_cursor(&cursor);
+	WARN_ON(d_count(&cursor) != 1);
+	return child;
+}
+EXPORT_SYMBOL(d_next_sibling_sched);
+
 /**
  * d_alloc - allocate a dcache entry
  * @parent: parent of entry to allocate
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index cabf05e74b1f..f7d5954c58da 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -656,10 +656,15 @@ static inline struct dentry *d_next_sibling(const struct dentry *dentry)
 	return hlist_entry_safe(dentry->d_sib.next, struct dentry, d_sib);
 }
 
+struct dentry *d_next_sibling_sched(struct dentry *child);
+
 static inline struct dentry *d_next_positive(struct dentry *child)
 {
 	do {
-		child = d_next_sibling(child);
+		if (need_resched())
+			child = d_next_sibling_sched(child);
+		else
+			child = d_next_sibling(child);
 	} while (child && !d_really_is_positive(child));
 	return child;
 }
@@ -691,9 +696,11 @@ static inline struct dentry *d_first_positive(const struct dentry *parent,
  * which have at some point in the past been positive.
  */
 #define d_for_each_positive_child(child, parent)			\
-	scoped_guard(spinlock, &parent->d_lock)				\
-		for (child = d_first_positive(parent, NULL); child;	\
-		     child = d_next_positive(child))
+	if (({might_sleep();0;})) ; else				\
+		scoped_guard(spinlock, &parent->d_lock)			\
+			for (child = d_first_positive(parent, NULL);	\
+			     child;					\
+			     child = d_next_positive(child))
 
 /**
  * d_for_each_positive_child_continue - iterate over remaining positive children
@@ -710,9 +717,11 @@ static inline struct dentry *d_first_positive(const struct dentry *parent,
  *
  */
 #define d_for_each_positive_child_continue(child, parent)		\
-	scoped_guard(spinlock, &parent->d_lock)				\
-		for (child = d_first_positive(parent, child); child;	\
-		     child = d_next_positive(child))
+	if (({might_sleep();0;})) ; else				\
+		scoped_guard(spinlock, &parent->d_lock)			\
+			for (child = d_first_positive(parent, child);	\
+			     child;					\
+			     child = d_next_positive(child))
 
 void set_default_d_op(struct super_block *, const struct dentry_operations *);
 struct dentry *d_make_persistent(struct dentry *, struct inode *);
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 15/18] libfs: remove cond_resched() from scan_positives()

[NeilBrown]

From: NeilBrown <neil@brown.name>

Now that d_for_each_positive_child_continue() calls cond_resced() as
needed, scan_positives() doesn't need to any more.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/libfs.c | 18 +++++-------------
 1 file changed, 5 insertions(+), 13 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index 44e8dec51237..15dd470198dd 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -108,7 +108,6 @@ EXPORT_SYMBOL(dcache_dir_close);
  * the last element of the list and %NULL is returned.
  */
 static struct dentry *scan_positives(struct dentry *dentry,
-				     struct dentry *cursor,
 				     struct dentry *last,
 				     loff_t count)
 {
@@ -125,13 +124,6 @@ static struct dentry *scan_positives(struct dentry *dentry,
 				break;
 			count = 1;
 		}
-		if (cursor && need_resched()) {
-			hlist_move_behind(&cursor->d_sib, &d->d_sib);
-			d = cursor;
-			spin_unlock(&dentry->d_lock);
-			cond_resched();
-			spin_lock(&dentry->d_lock);
-		}
 	}
 	dput(last);
 	return found;
@@ -158,7 +150,7 @@ loff_t dcache_dir_lseek(struct file *file, loff_t offset, int whence)
 		inode_lock_shared(dentry->d_inode);
 
 		if (offset > 2)
-			to = scan_positives(dentry, cursor, NULL, offset - 2);
+			to = scan_positives(dentry, NULL, offset - 2);
 		spin_lock(&dentry->d_lock);
 		if (to)
 			hlist_move_behind(&cursor->d_sib, &to->d_sib);
@@ -193,7 +185,7 @@ int dcache_readdir(struct file *file, struct dir_context *ctx)
 	if (ctx->pos > 2)
 		next = dget(cursor);
 
-	while ((next = scan_positives(dentry, cursor, next, 1)) != NULL) {
+	while ((next = scan_positives(dentry, next, 1)) != NULL) {
 		if (!dir_emit(ctx, next->d_name.name, next->d_name.len,
 			      d_inode(next)->i_ino,
 			      fs_umode_to_dtype(d_inode(next)->i_mode)))
@@ -448,7 +440,7 @@ offset_dir_lookup(struct dentry *parent, loff_t offset)
 	MA_STATE(mas, &octx->mt, offset, offset);
 
 	if (offset == DIR_OFFSET_FIRST)
-		found = scan_positives(parent, NULL, NULL, 1);
+		found = scan_positives(parent, NULL, 1);
 	else {
 		rcu_read_lock();
 		spin_lock(&parent->d_lock);
@@ -470,7 +462,7 @@ offset_dir_lookup(struct dentry *parent, loff_t offset)
 		spin_unlock(&parent->d_lock);
 		rcu_read_unlock();
 		if (found && !simple_positive(found))
-			found = scan_positives(parent, NULL, found, 1);
+			found = scan_positives(parent, found, 1);
 	}
 	return found;
 }
@@ -496,7 +488,7 @@ static void offset_iterate_dir(struct file *file, struct dir_context *ctx)
 		if (!offset_dir_emit(ctx, dentry))
 			break;
 
-		dentry = scan_positives(dir, NULL, dentry, 1);
+		dentry = scan_positives(dir, dentry, 1);
 
 		if (!dentry)
 			goto out_eod;
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 16/18] libfs: rename and export scan_positives()

[NeilBrown]

From: NeilBrown <neil@brown.name>

autofs has code nearly identical to scan_positives().  To avoid code
duplication, export scan_positives().

Rename it to "d_scan_positives()" to make it more obviously dcache
related.

Change the "count" argument to "skip" which starts from 0 rather than 1.
This makes it a little easier to document the purpose, and makes it less
likely that "0" will be passed when "1" was intended.

For aesthetic consistency, all calls of d_scan_positives() now pass as
the "prev" arg the variable that the result is being assigned to.
This was already the case except when NULL was passed, but in the two
cases where NULL was passed, the target variable already had been
initialised to NULL.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/libfs.c             | 49 ++++++++++++++++++++++++++----------------
 include/linux/dcache.h |  4 ++++
 2 files changed, 34 insertions(+), 19 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index 15dd470198dd..20cc94b41075 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -97,37 +97,48 @@ int dcache_dir_close(struct inode *inode, struct file *file)
 }
 EXPORT_SYMBOL(dcache_dir_close);
 
-/* parent is locked at least shared */
-/*
- * Returns an element of siblings' list.
- * We are looking for <count>th positive after <p>; if
- * found, dentry is grabbed and returned to caller.
- * If no such element exists, NULL is returned.
- * If last has been removed from the d_children list
- * (i.e. last->d_sib is unhashed) then it is treated like
+/**
+ * d_scan_positives - return next positive dentry after skipping some.
+ * @dentry: the parent dentry to scan
+ * @last: the place to start search, or %NULL to begin at start.
+ * @skip: number of positive dentries to skip over
+ *
+ * Returns the next, or first, positive element of siblings list after
+ * skipping over @skip positive elements.
+ * The child dentry is grabbed and returned to caller.
+ * If no such element exists, %NULL is returned.
+ *
+ * Caller must ensure returned dentry cannot be moved from
+ * the parent, possibly by holding i_rwsem.
+ *
+ * If @last has been removed from the d_children list
+ * (i.e. @last->d_sib is unhashed) then it is treated like
  * the last element of the list and %NULL is returned.
+ *
+ * Returns: a counted ref to a dentry, or %NULL
  */
-static struct dentry *scan_positives(struct dentry *dentry,
-				     struct dentry *last,
-				     loff_t count)
+struct dentry *d_scan_positives(struct dentry *dentry,
+				struct dentry *last,
+				loff_t skip)
 {
 	struct dentry *found = NULL;
 	struct dentry *d = last;
 
 	d_for_each_positive_child_continue(d, dentry) {
-		if (simple_positive(d) && !--count) {
+		if (simple_positive(d) && !skip--) {
 			spin_lock_nested(&d->d_lock, DENTRY_D_LOCK_NESTED);
 			if (simple_positive(d))
 				found = dget_dlock(d);
 			spin_unlock(&d->d_lock);
 			if (likely(found))
 				break;
-			count = 1;
+			skip = 0;
 		}
 	}
 	dput(last);
 	return found;
 }
+EXPORT_SYMBOL(d_scan_positives);
 
 loff_t dcache_dir_lseek(struct file *file, loff_t offset, int whence)
 {
@@ -149,8 +160,8 @@ loff_t dcache_dir_lseek(struct file *file, loff_t offset, int whence)
 
 		inode_lock_shared(dentry->d_inode);
 
-		if (offset > 2)
-			to = scan_positives(dentry, NULL, offset - 2);
+		if (offset >= 3)
+			to = d_scan_positives(dentry, to, offset - 3);
 		spin_lock(&dentry->d_lock);
 		if (to)
 			hlist_move_behind(&cursor->d_sib, &to->d_sib);
@@ -185,7 +196,7 @@ int dcache_readdir(struct file *file, struct dir_context *ctx)
 	if (ctx->pos > 2)
 		next = dget(cursor);
 
-	while ((next = scan_positives(dentry, next, 1)) != NULL) {
+	while ((next = d_scan_positives(dentry, next, 0)) != NULL) {
 		if (!dir_emit(ctx, next->d_name.name, next->d_name.len,
 			      d_inode(next)->i_ino,
 			      fs_umode_to_dtype(d_inode(next)->i_mode)))
@@ -440,7 +451,7 @@ offset_dir_lookup(struct dentry *parent, loff_t offset)
 	MA_STATE(mas, &octx->mt, offset, offset);
 
 	if (offset == DIR_OFFSET_FIRST)
-		found = scan_positives(parent, NULL, 1);
+		found = d_scan_positives(parent, found, 0);
 	else {
 		rcu_read_lock();
 		spin_lock(&parent->d_lock);
@@ -462,7 +473,7 @@ offset_dir_lookup(struct dentry *parent, loff_t offset)
 		spin_unlock(&parent->d_lock);
 		rcu_read_unlock();
 		if (found && !simple_positive(found))
-			found = scan_positives(parent, found, 1);
+			found = d_scan_positives(parent, found, 0);
 	}
 	return found;
 }
@@ -488,7 +499,7 @@ static void offset_iterate_dir(struct file *file, struct dir_context *ctx)
 		if (!offset_dir_emit(ctx, dentry))
 			break;
 
-		dentry = scan_positives(dir, dentry, 1);
+		dentry = d_scan_positives(dir, dentry, 0);
 
 		if (!dentry)
 			goto out_eod;
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index f7d5954c58da..a978d1c4936a 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -723,6 +723,10 @@ static inline struct dentry *d_first_positive(const struct dentry *parent,
 			     child;					\
 			     child = d_next_positive(child))
 
+struct dentry *d_scan_positives(struct dentry *dentry,
+				struct dentry *last,
+				loff_t skip);
+
 void set_default_d_op(struct super_block *, const struct dentry_operations *);
 struct dentry *d_make_persistent(struct dentry *, struct inode *);
 void d_make_discardable(struct dentry *dentry);
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 17/18] autofs: replace positive_after() with d_scan_positives()

[NeilBrown]

From: NeilBrown <neil@brown.name>

Now that d_scan_positives() is exported, autofs can use it.

An important difference from positive_after() is that d_scan_positives()
drop the ref to the "prev" dentry.  This means that
get_next_positive_dentry() must take a reference to the new parent
when stepping up, using dget_parent(), but otherwise
allows that function to be significantly simplified.

The while() loop looks a little unbalanced as there is a dget_parent
without a dput.  However when d_scan_positives() returns NULL, it will
have done a dput without a dget, which provides the required balance.

The dput(prev) at the end now doesn't (necessary) dput() the original
"prev", but instead dput()s the parent of the returned dentry.

Note that d_scan_positives() requires the caller to protect against
renames.  autofs doesn't need to take any action because it doesn't
support rename at all.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/autofs/expire.c | 51 +++++++++++-----------------------------------
 1 file changed, 12 insertions(+), 39 deletions(-)

diff --git a/fs/autofs/expire.c b/fs/autofs/expire.c
index b6937c5936a5..277d9129754e 100644
--- a/fs/autofs/expire.c
+++ b/fs/autofs/expire.c
@@ -70,53 +70,26 @@ static int autofs_mount_busy(struct vfsmount *mnt,
 	return status;
 }
 
-static struct dentry *positive_after(struct dentry *p, struct dentry *child)
-{
-	d_for_each_positive_child_continue(child, p) {
-		spin_lock_nested(&child->d_lock, DENTRY_D_LOCK_NESTED);
-		if (simple_positive(child)) {
-			dget_dlock(child);
-			spin_unlock(&child->d_lock);
-			return child;
-		}
-		spin_unlock(&child->d_lock);
-	}
-	return NULL;
-}
-
 /*
- * Calculate and dget next entry in the subdirs list under root.
- */
-static struct dentry *get_next_positive_subdir(struct dentry *prev,
-					       struct dentry *root)
-{
-	struct dentry *q;
-
-	q = positive_after(root, prev);
-	dput(prev);
-	return q;
-}
-
-/*
- * Calculate and dget next entry in top down tree traversal.
+ * Calculate and dget() next entry in top down tree traversal,
+ * and dput() the previous dentry.  If there are no positive
+ * children, we stop up to the parent and look for next
+ * sibling.
+ * As autofs does not support rename, there is no risk
+ * for the parent changing before we step up.
  */
 static struct dentry *get_next_positive_dentry(struct dentry *prev,
 					       struct dentry *root)
 {
-	struct dentry *p = prev, *ret = NULL, *d = NULL;
+	struct dentry *ret = NULL;
 
 	if (prev == NULL)
 		return dget(root);
 
-	while (1) {
-		struct dentry *parent;
-
-		ret = positive_after(p, d);
-		if (ret || p == root)
-			break;
-		parent = p->d_parent;
-		d = p;
-		p = parent;
+	while ((ret = d_scan_positives(prev, ret, 0)) == NULL &&
+	       prev != root) {
+		ret = prev;
+		prev = dget_parent(prev);
 	}
 	dput(prev);
 	return ret;
@@ -414,7 +387,7 @@ static struct dentry *autofs_expire_indirect(struct super_block *sb,
 		return NULL;
 
 	dentry = NULL;
-	while ((dentry = get_next_positive_subdir(dentry, root))) {
+	while ((dentry = d_scan_positives(root, dentry, 0))) {
 		spin_lock(&sbi->fs_lock);
 		ino = autofs_dentry_ino(dentry);
 		if (ino->flags & AUTOFS_INF_WANT_EXPIRE) {
-- 
2.50.0.107.gf914562f5916.dirty

[PATCH v2 18/18] autofs: change get_next_positive_dentry() to NOT accept NULL for start-up

[NeilBrown]

From: NeilBrown <neil@brown.name>

Rather than passing NULL to get_next_positive_dentry() to first time
round, change callers to use a for loop which does the dget() explicitly
to start the loop.

I think this makes the code clearer.  Looking at
get_next_positive_dentry() it isn't immediately obvious what that code
is doing there.

Signed-off-by: NeilBrown <neil@brown.name>
---
 fs/autofs/expire.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/fs/autofs/expire.c b/fs/autofs/expire.c
index 277d9129754e..2a1844ba48c6 100644
--- a/fs/autofs/expire.c
+++ b/fs/autofs/expire.c
@@ -83,9 +83,6 @@ static struct dentry *get_next_positive_dentry(struct dentry *prev,
 {
 	struct dentry *ret = NULL;
 
-	if (prev == NULL)
-		return dget(root);
-
 	while ((ret = d_scan_positives(prev, ret, 0)) == NULL &&
 	       prev != root) {
 		ret = prev;
@@ -148,7 +145,7 @@ static int autofs_tree_busy(struct vfsmount *mnt,
 		return 1;
 
 	p = NULL;
-	while ((p = get_next_positive_dentry(p, top))) {
+	for (p = dget(top); p; p = get_next_positive_dentry(p, top)) {
 		pr_debug("dentry %p %pd\n", p, p);
 
 		/*
@@ -201,8 +198,7 @@ static struct dentry *autofs_check_leaves(struct vfsmount *mnt,
 
 	pr_debug("parent %p %pd\n", parent, parent);
 
-	p = NULL;
-	while ((p = get_next_positive_dentry(p, parent))) {
+	for (p = dget(parent); p; p = get_next_positive_dentry(p, parent)) {
 		pr_debug("dentry %p %pd\n", p, p);
 
 		if (d_mountpoint(p)) {
-- 
2.50.0.107.gf914562f5916.dirty

Re: [PATCH RFC/RFT v2 00/18] Fix easy bits of the negative dentry problem

[Al Viro]

On Sat, Aug 15, 2026 at 02:21:17PM +1000, NeilBrown wrote:

> Most of d_walk() already schedules as needed, but I
>  think there is still room for improvement, but that can come later.

How the hell could it possibly schedule, when it might very well have
grabbed rename_lock?  Confused...

Al, getting through the piles of mail at the moment (sick for a month)...

Re: [PATCH RFC/RFT v2 00/18] Fix easy bits of the negative dentry problem

[NeilBrown]

On Sat, 15 Aug 2026, Al Viro wrote:
> On Sat, Aug 15, 2026 at 02:21:17PM +1000, NeilBrown wrote:
> 
> > Most of d_walk() already schedules as needed, but I
> >  think there is still room for improvement, but that can come later.
> 
> How the hell could it possibly schedule, when it might very well have
> grabbed rename_lock?  Confused...

I should have said:
  Most d_walk() instances abort when there is a need to schedule()
  so the caller can do that and retry.

That really only applies to shrink_dcache_tree() which it is a bit of
stretch to call "most", but apart from path_has_submounts() the others
are all called only after shrink_dcache_tree() has done its work, so
there won't be many (any?) negative dentries any more, so they won't need
to schedule().

I think path_has_submounts() could be changed to search mounts for
descendants, rather than searching descendant for mounts.
Maybe something like:

int path_has_submounts(const struct path *parent)
{
	struct mount *m;

	guard(mount_locked_reader)();
	list_for_each_entry(m, &real_mount(parent->mnt)->mnt_mounts, mnt_child)
		if (is_subdir(m->mnt_mountpoint, parent->dentry))
			return 1;

	return 0;
}

As it is only used by autofs which could have lots of mounts that might
be slower in the common case.  But it isn't clear there is problem here
that needs fixing.  autofs certainly *could* collect lots of negative
dentries, but does it?

> 
> Al, getting through the piles of mail at the moment (sick for a month)...
> 

My condolences.  Thanks for having a look at this series.

NeilBrown