fs/dcache: avoid trylock loops

Thank you Al Viro, Linus Torvalds, Peter Zijlstra, Amir Goldstein for the detailed feedback.

Changes in v2:
. dentry_lock_inode()
- added quick out on trylock success
- added comments to rcu section
- expanded rcu coverage to all inode usage
- if inode changes during d_lock window,
restart the function (do not return)
- track the dentry refcount and return false if it changes
. dentry_kill()
- do not expect refcount=1 from caller
- if refcount changes during d_lock window, return ERR_PTR(-EINTR) and do not drop d_lock
. dentry_put_kill() [new helper function]
- dentry_kill() wrapper to implement the v1 dentry_kill() semantics needed by dput() and shrink_dentry_list()
. dput()
- use new dentry_put_kill() instead of dentry_kill()
. d_delete()
- refactor code flow using reworked dentry_lock_inode()
. shrink_dentry_list()
- use dentry_kill() for dispose list killing
- use dentry_put_kill() for ancestor pruning

This patchset removes all trylock loops from within the dcache code.

The functions d_delete(), dentry_kill(), and shrink_dentry_list() hold dentry->d_lock while needing to acquire dentry->d_inode->i_lock. The latter 2 functions also need to acquire dentry->d_parent->d_lock. This cannot be done directly with spin_lock() operations because it is the reverse of the regular lock order. To avoid ABBA deadlocks it is done using trylock loops.

Trylock loops are problematic in two scenarios:

1) PREEMPT_RT converts spinlocks to 'sleeping' spinlocks, which are preemptible. As a consequence the i_lock holder can be preempted by a higher priority task. If that task executes the trylock loop it will do so forever and live lock.

2) In virtual machines trylock loops are problematic as well. The VCPU on which the i_lock holder runs can be scheduled out and a task on a different VCPU can loop for a whole time slice. In the worst case this can lead to starvation. Commits 47be61845c77 ("fs/dcache.c: avoid soft-lockup in dput()") and 046b961b45f9 ("shrink_dentry_list(): take parent's d_lock earlier") are addressing exactly those symptoms.

The trylock loops can be avoided with functionality similar to lock_parent(); temporarily dropping dentry->d_lock while holding the rcu_read_lock so that the desired locks can be acquired in the correct order. After the locks are acquired it is necessary to verify that the relevant dentry members did not change while dentry->d_lock was dropped. If they changed, the whole operation must be repeated.

John Ogness (6):
fs/dcache: Remove stale comment from dentry_kill() fs/dcache: Move dentry_kill() below lock_parent() fs/dcache: Avoid the try_lock loop in d_delete() fs/dcache: Avoid the try_lock loops in dentry_kill() fs/dcache: Avoid a try_lock loop in shrink_dentry_list() fs/dcache: Avoid remaining try_lock loop in shrink_dentry_list()

 fs/dcache.c | 273 ++++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 183 insertions(+), 90 deletions(-)

2.11.0

Commit 0d98439ea3c6 ("vfs: use lockred "dead" flag to mark unrecoverably dead dentries") removed the `ref' parameter in dentry_kill() but its documentation remained. Remove it.

---
 fs/dcache.c | 1 -
 1 file changed, 1 deletion(-)

index 7c38f39958bc..3c7e0148b453 100644
@@ -592,7 +592,6 @@ static void __dentry_kill(struct dentry *dentry)
 /*
  * Finish off a dentry we've decided to kill.
  * dentry->d_lock must be held, returns with it unlocked.
- * If ref is non-zero, then decrement the refcount too.
  * Returns dentry requiring refcount drop, or NULL if we're done.
  */
 static struct dentry *dentry_kill(struct dentry *dentry)

2.11.0

A subsequent patch will modify dentry_kill() to call lock_parent(). Move the dentry_kill() implementation "as is" below lock_parent() first. This will help simplify the review of the subsequent patch with dentry_kill() changes.

---
 fs/dcache.c | 62 ++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 31 insertions(+), 31 deletions(-)

index 3c7e0148b453..9fed398687c9 100644
@@ -589,37 +589,6 @@ static void __dentry_kill(struct dentry *dentry)
 		dentry_free(dentry);
 }
 
-/*
- * Finish off a dentry we've decided to kill.
- * dentry->d_lock must be held, returns with it unlocked.
- * Returns dentry requiring refcount drop, or NULL if we're done.
- */
-static struct dentry *dentry_kill(struct dentry *dentry)
-	__releases(dentry->d_lock)
-{
-	struct inode *inode = dentry->d_inode;
-	struct dentry *parent = NULL;
-
-	if (inode && unlikely(!spin_trylock(&inode->i_lock)))
-		goto failed;
-
-	if (!IS_ROOT(dentry)) {
-		parent = dentry->d_parent;
-		if (unlikely(!spin_trylock(&parent->d_lock))) {
-			if (inode)
-				spin_unlock(&inode->i_lock);
-			goto failed;
-		}
-	}
-
-	__dentry_kill(dentry);
-	return parent;
-
-failed:
-	spin_unlock(&dentry->d_lock);
-	return dentry; /* try again with same dentry */
-}
-
 static inline struct dentry *lock_parent(struct dentry *dentry)
 {
 	struct dentry *parent = dentry->d_parent;

@@ -655,6 +624,37 @@ static inline struct dentry *lock_parent(struct dentry *dentry)
 }
 
 /*
+ * Finish off a dentry we've decided to kill.
+ * dentry->d_lock must be held, returns with it unlocked.
+ * Returns dentry requiring refcount drop, or NULL if we're done.
+ */
+static struct dentry *dentry_kill(struct dentry *dentry)
+	__releases(dentry->d_lock)
+{
+	struct inode *inode = dentry->d_inode;
+	struct dentry *parent = NULL;
+
+	if (inode && unlikely(!spin_trylock(&inode->i_lock)))
+		goto failed;
+
+	if (!IS_ROOT(dentry)) {
+		parent = dentry->d_parent;
+		if (unlikely(!spin_trylock(&parent->d_lock))) {
+			if (inode)
+				spin_unlock(&inode->i_lock);
+			goto failed;
+		}
+	}
+
+	__dentry_kill(dentry);
+	return parent;
+
+failed:
+	spin_unlock(&dentry->d_lock);
+	return dentry; /* try again with same dentry */
+}
+
+/*
  * Try to do a lockless dput(), and return whether that was successful.
  *
  * If unsuccessful, we return false, having already taken the dentry lock.

2.11.0

d_delete() holds dentry->d_lock and needs to acquire dentry->d_inode->i_lock. This cannot be done with a spin_lock() operation because it's the reverse of the regular lock order. To avoid the ABBA deadlock it is done with a trylock loop.

Trylock loops are problematic in two scenarios:

1) PREEMPT_RT converts spinlocks to 'sleeping' spinlocks, which are preemptible. As a consequence the i_lock holder can be preempted by a higher priority task. If that task executes the trylock loop it will do so forever and live lock.

2) In virtual machines trylock loops are problematic as well. The VCPU on which the i_lock holder runs can be scheduled out and a task on a different VCPU can loop for a whole time slice. In the worst case this can lead to starvation. Commits 47be61845c77 ("fs/dcache.c: avoid soft-lockup in dput()") and 046b961b45f9 ("shrink_dentry_list(): take parent's d_lock earlier") are addressing exactly those symptoms.

The trylock loop can be avoided with functionality similar to lock_parent(). The fast path tries the trylock first, which is likely to succeed. In the contended case it attempts locking in the correct order. This requires to drop dentry->d_lock first, which allows another task to free d_inode. This can be prevented by the following mechanism:

   inode = dentry->d_inode;
   rcu_read_lock();        <-- Protects d_inode from being freed,
                               i.e. inode is a valid pointer even
                               after dentry->d_lock is dropped
   unlock(dentry->d_lock);
   lock(inode->i_lock);
   lock(&dentry->d_lock);
   if (error)
       unlock(inode->i_lock);
   rcu_read_unlock();

After the locks are acquired it's necessary to verify whether dentry->d_inode is still pointing to inode as it might have been changed after dropping dentry->d_lock. If it matches d_delete() can proceed, if not the whole operation has to be repeated.

Implement this in a new function dentry_lock_inode() which will be used in a subsequent patch as well.

---
 fs/dcache.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 77 insertions(+), 17 deletions(-)

index 9fed398687c9..bfdf1ff237f2 100644
@@ -623,6 +623,71 @@ static inline struct dentry *lock_parent(struct dentry *dentry)
 	return parent;
 }
 
+/**
+ * dentry_lock_inode - Lock dentry->d_inode->i_lock
+ * @dentry: The dentry to operate on
+ *
+ * Tries to acquire @dentry->d_inode->i_lock with a trylock first. If
+ * that fails it retries in correct lock order, which requires dropping
+ * @dentry->d_lock under RCU protection and then reacquiring it after
+ * locking @dentry->d_inode->i_lock.
+ *
+ * If @dentry->d_lockref.count changes while trying to acquire
+ * @dentry->d_inode->i_lock, drop @dentry->d_inode->i_lock and return
+ * false. Otherwise return true.
+ *
+ * Note that all relevant struct members of @dentry must be reevaluated by
+ * the caller since @dentry->d_lock might have been temporarily dropped.
+ */
+static bool dentry_lock_inode(struct dentry *dentry)
+{
+	int saved_count = dentry->d_lockref.count;
+	struct inode *inode;
+
+	lockdep_assert_held(&dentry->d_lock);
+again:
+	inode = dentry->d_inode;
+	if (likely(spin_trylock(&inode->i_lock)))
+		return true;
+
+	/*
+	 * The inode struct pointed to by "inode" is protected by RCU,
+	 * i.e. destroy_inode() uses call_rcu() to reclaim the memory.
+	 * Using rcu_read_lock() ensures that the inode struct remains
+	 * valid after dropping @dentry->d_lock, independent of whether
+	 * or not @dentry->d_inode continues to point to that inode.
+	 */
+	rcu_read_lock();
+
+	spin_unlock(&dentry->d_lock);
+	spin_lock(&inode->i_lock);
+	spin_lock(&dentry->d_lock);
+
+	/*
+	 * @dentry->d_lockref.count might have changed after dropping
+	 * @dentry->d_lock. If so, release @inode->i_lock and tell caller.
+	 */
+	if (unlikely(dentry->d_lockref.count != saved_count)) {
+		spin_unlock(&inode->i_lock);
+		rcu_read_unlock();
+		return false;
+	}
+
+	/*
+	 * @dentry->d_inode might have changed after dropping @dentry->d_lock.
+	 * If so, release @inode->i_lock and restart.
+	 */
+	if (unlikely(inode != dentry->d_inode)) {
+		spin_unlock(&inode->i_lock);
+		rcu_read_unlock();
+		goto again;
+	}
+
+	rcu_read_unlock();
+
+	return true;
+}
+
 /*
  * Finish off a dentry we've decided to kill.
  * dentry->d_lock must be held, returns with it unlocked.

@@ -2373,32 +2438,27 @@ EXPORT_SYMBOL(d_hash_and_lookup);
  
 void d_delete(struct dentry * dentry)
 {
-	struct inode *inode;
-	int isdir = 0;
+	int isdir;
 	/*
 	 * Are we the only user?
 	 */
-again:
+
 	spin_lock(&dentry->d_lock);
-	inode = dentry->d_inode;
-	isdir = S_ISDIR(inode->i_mode);
-	if (dentry->d_lockref.count == 1) {
-		if (!spin_trylock(&inode->i_lock)) {
-			spin_unlock(&dentry->d_lock);
-			cpu_relax();
-			goto again;
-		}
-		dentry->d_flags &= ~DCACHE_CANT_MOUNT;
-		dentry_unlink_inode(dentry);
-		fsnotify_nameremove(dentry, isdir);
-		return;
-	}
 
+	if (dentry->d_lockref.count > 1 || !dentry_lock_inode(dentry))
+		goto drop;
+
+	dentry->d_flags &= ~DCACHE_CANT_MOUNT;
+	isdir = S_ISDIR(dentry->d_inode->i_mode);
+	dentry_unlink_inode(dentry);
+	fsnotify_nameremove(dentry, isdir);
+	return;
+drop:
 	if (!d_unhashed(dentry))
 		__d_drop(dentry);
 
+	isdir = S_ISDIR(dentry->d_inode->i_mode);
 	spin_unlock(&dentry->d_lock);
-
 	fsnotify_nameremove(dentry, isdir);
 }
 EXPORT_SYMBOL(d_delete);

2.11.0

Wait a minute. _What_ allows another task to free ->d_inode on a dentry we are holding a reference to? Any place like that is a serious bug - after all, what's to prevent the same place doing that to dentry of an opened file, with obvious ugly results.

That's the whole reason why d_delete() is *NOT* making dentry negative when refcount is greater than 1 (i.e. when somebody else is holding a reference).

Rules for ->d_inode:

* initially NULL.

* only changes under ->d_lock

* __dentry_kill() makes it NULL after dentry has been
+ marked dead
+ evicted from all lists except possibly shrink one.
with ->d_lock held through all of that. The only thing that can be done by anybody else with the ones stuck on shrink list is actually freeing them.

Note that once __dentry_kill() is called, that's it - dentry is ours, for all practical purposes. There'd better be no other references to that sucker and we make sure that no new ones will arise.

* prior to the call of __dentry_kill() any would-be changer of ->d_inode must be holding a reference to dentry.

* changes from non-NULL to NULL are possible only when there's nobody else holding references.

Changes from NULL to non-NULL _are_ possible (caller must be holding a reference, but that's it). However, feeding a negative dentry to your dentry_lock_inode() is an instant oops - it won't live to the point where you would recheck ->d_inode for changes.

So if you see any place where positive could be changed to negative under us, we do have a problem. Big one.

Refcount can change once we drop ->d_lock, but it can't get to zero - our reference is still with us.

Note that ->d_parent *CAN* change, no matter how many references are held. That's what rcu games in lock_parent() are about - dentry can be moved and ex-parent could've been freed if that was the last reference.

dentry_kill() holds dentry->d_lock and needs to acquire both dentry->d_inode->i_lock and dentry->d_parent->d_lock. This cannot be done with spin_lock() operations because it's the reverse of the regular lock order. To avoid ABBA deadlocks it is done with two trylock loops.

Trylock loops are problematic in two scenarios:

1) PREEMPT_RT converts spinlocks to 'sleeping' spinlocks, which are preemptible. As a consequence the i_lock holder can be preempted by a higher priority task. If that task executes the trylock loop it will do so forever and live lock.

2) In virtual machines trylock loops are problematic as well. The VCPU on which the i_lock holder runs can be scheduled out and a task on a different VCPU can loop for a whole time slice. In the worst case this can lead to starvation. Commits 47be61845c77 ("fs/dcache.c: avoid soft-lockup in dput()") and 046b961b45f9 ("shrink_dentry_list(): take parent's d_lock earlier") are addressing exactly those symptoms.

Avoid the trylock loops by using dentry_lock_inode() and lock_parent() which take the locks in the appropriate order. As both functions might drop dentry->lock briefly, this requires rechecking of the dentry content as it might have changed while the lock was dropped. dentry_lock_inode() performs the checks internally, but lock_parent() relies on the caller to perform the checks.

---
 fs/dcache.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 54 insertions(+), 16 deletions(-)

index bfdf1ff237f2..082361939b84 100644
@@ -696,27 +696,67 @@ static bool dentry_lock_inode(struct dentry *dentry)
 static struct dentry *dentry_kill(struct dentry *dentry)
 	__releases(dentry->d_lock)
 {
-	struct inode *inode = dentry->d_inode;
-	struct dentry *parent = NULL;
+	int saved_count = dentry->d_lockref.count;
+	struct dentry *parent;
+	struct inode *inode;
 
-	if (inode && unlikely(!spin_trylock(&inode->i_lock)))
-		goto failed;
+again:
+	inode = dentry->d_inode;
 
-	if (!IS_ROOT(dentry)) {
-		parent = dentry->d_parent;
-		if (unlikely(!spin_trylock(&parent->d_lock))) {
-			if (inode)
-				spin_unlock(&inode->i_lock);
-			goto failed;
-		}
+	/*
+	 * Lock the inode. It will fail if the refcount
+	 * changed while trying to lock the inode.
+	 */
+	if (inode && !dentry_lock_inode(dentry))
+		goto out_ref_changed;
+
+	parent = lock_parent(dentry);
+
+	/*
+	 * Check refcount because it might have changed
+	 * if d_lock was temporarily dropped.
+	 */
+	if (unlikely(dentry->d_lockref.count != saved_count)) {
+		if (parent)
+			spin_unlock(&parent->d_lock);
+		if (inode)
+			spin_unlock(&inode->i_lock);
+		goto out_ref_changed;
+	}
+
+	/*
+	 * d_inode might have changed if d_lock was temporarily
+	 * dropped. If it changed it is necessary to start over
+	 * because a wrong inode (or no inode) lock is held.
+	 */
+	if (unlikely(inode != dentry->d_inode)) {
+		if (parent)
+			spin_unlock(&parent->d_lock);
+		if (inode)
+			spin_unlock(&inode->i_lock);
+		goto again;
 	}
 
 	__dentry_kill(dentry);
 	return parent;
 
-failed:
+out_ref_changed:
+	/*
+	 * The refcount was incremented while dentry->d_lock was dropped.
+	 * Just decrement the refcount, unlock, and tell the caller to
+	 * stop the directory walk.
+	 *
+	 * For paranoia reasons check whether the refcount is < 1. If so,
+	 * report the detection and avoid the decrement which would just
+	 * cause a problem in some other place. The warning might be
+	 * helpful to decode the root cause of the refcounting bug.
+	 */
+	if (!WARN_ON(dentry->d_lockref.count < 1))
+		dentry->d_lockref.count--;
+
 	spin_unlock(&dentry->d_lock);
-	return dentry; /* try again with same dentry */
+
+	return NULL;
 }
 
 /*

@@ -888,10 +928,8 @@ void dput(struct dentry *dentry)
 
 kill_it:
 	dentry = dentry_kill(dentry);
-	if (dentry) {
-		cond_resched();
+	if (dentry)
 		goto repeat;
-	}
 }
 EXPORT_SYMBOL(dput);
 

2.11.0

PS: I really wonder if we should treat the failure to trylock ->i_lock and parent's ->d_lock at that point (we are already off the fast path here) as
* drop all spinlocks we'd got
* grab ->i_lock
* grab ->d_lock
* lock_parent()
* act as if fast_dput() has returned 0, only remember to drop ->i_lock
and unlock parent before dropping ->d_lock if we decide to keep it.

IOW, add

static inline bool retain_dentry(struct dentry *dentry)

{
        WARN_ON(d_in_lookup(dentry));

        /* Unreachable? Get rid of it */
        if (unlikely(d_unhashed(dentry)))
                return false;

        if (unlikely(dentry->d_flags & DCACHE_DISCONNECTED))
                return false;

        if (unlikely(dentry->d_flags & DCACHE_OP_DELETE)) {
                if (dentry->d_op->d_delete(dentry))
                        return false;
        }

	dentry_lru_add(dentry);
	dentry->d_lockref.count--;
	return true;
}

then have dput() do

{
        if (unlikely(!dentry))
                return;
repeat:
        might_sleep();

        rcu_read_lock();
        if (likely(fast_dput(dentry))) {
                rcu_read_unlock();
                return;
        }

        /* Slow case: now with the dentry lock held */
        rcu_read_unlock();
	if (likely(retain_dentry(dentry))) {
		spin_unlock(&dentry->d_lock);
		return;
	}
	dentry = dentry_kill(dentry);
	if (dentry)
		goto repeat;
}

with dentry_kill() being pretty much as it is now, except that it would be ending on

failed:

	spin_unlock(&dentry->d_lock);
	spin_lock(&inode->i_lock);
	spin_lock(&dentry->d_lock);
	parent = lock_parent(dentry);
	/* retain_dentry() needs ->count == 1 already checked)
	if (dentry->d_lockref.count == 1 && !retain_dentry(dentry)) {
		__dentry_kill(dentry);
		return parent;
	}
	/* we are keeping it, after all */
	if (inode)
		spin_unlock(&inode->i_lock);
	spin_unlock(&dentry->d_lock);
	if (parent)
		spin_unlock(&parent->d_lock);
	return NULL;
}

... obviously not even compile-tested ;-)

Hmm... Negative dentry case obviously is trickier - not to mention oopsen, it might have become positive under us. Bugger... OTOH, it's not much trickier - with negative dentry we can only fail on trying to lock the parent, in which case we should just check that it's still negative before killing it off. If it has gone positive on us, we'll just unlock the parent and we are back to the normal "positive dentry, only ->d_lock held" case. At most one retry there - once it's positive, it stays positive. So,

static struct dentry *dentry_kill(struct dentry *dentry)

        __releases(dentry->d_lock)
{
	struct inode *inode = dentry->d_inode;
	struct dentry *parent = NULL;

	if (inode && unlikely(!spin_trylock(&inode->i_lock)))
		goto no_locks;

	if (!IS_ROOT(dentry)) {
		parent = dentry->d_parent;
		if (unlikely(!spin_trylock(&parent->d_lock))) {
			if (inode) {
				spin_unlock(&inode->i_lock);
				goto no_locks;
			}
			goto need_parent;
		}
	}
kill_it:
	__dentry_kill(dentry);
	return parent;

no_locks: /* positive, only ->d_lock held */

	spin_unlock(&dentry->d_lock);
	spin_lock(&inode->i_lock);
	spin_lock(&dentry->d_lock);
need_parent:
	parent = lock_parent(dentry);
	if (unlikely(dentry->d_lockref.count != 1 || retain_dentry(dentry))) {
		/* we are keeping it, after all */
		if (inode)
			spin_unlock(&inode->i_lock);
		spin_unlock(&dentry->d_lock);
		if (parent)
			spin_unlock(&parent->d_lock);
		return NULL;
	}
	/* it should die */
	if (inode)	/* was positive, ->d_inode unchanged, locks held */
		goto kill_it;
	inode = dentry->d_inode;	// READ_ONCE?
	if (!inode)	/* still negative, locks held */
		goto kill_it;
	/* negative became positive; it can't become negative again */
	if (parent)
		spin_unlock(&parent->d_lock);
	goto no_locks;	/* once */
}

shrink_dentry_list() holds dentry->d_lock and needs to acquire dentry->d_inode->i_lock. This cannot be done with a spin_lock() operation because it's the reverse of the regular lock order. To avoid ABBA deadlocks it is done with a trylock loop.

Trylock loops are problematic in two scenarios:

1) PREEMPT_RT converts spinlocks to 'sleeping' spinlocks, which are preemptible. As a consequence the i_lock holder can be preempted by a higher priority task. If that task executes the trylock loop it will do so forever and live lock.

2) In virtual machines trylock loops are problematic as well. The VCPU on which the i_lock holder runs can be scheduled out and a task on a different VCPU can loop for a whole time slice. In the worst case this can lead to starvation. Commits 47be61845c77 ("fs/dcache.c: avoid soft-lockup in dput()") and 046b961b45f9 ("shrink_dentry_list(): take parent's d_lock earlier") are addressing exactly those symptoms.

Avoid the trylock loop by using dentry_kill(). When pruning ancestors, the same code applies that is used to kill a dentry in dput(). This also has the benefit that the locking order is now the same. First the inode is locked, then the parent.

---
 fs/dcache.c | 22 ++--------------------
 1 file changed, 2 insertions(+), 20 deletions(-)

index 082361939b84..e470d49daa54 100644
@@ -1130,26 +1130,8 @@ static void shrink_dentry_list(struct list_head *list)
 		 * fragmentation.
 		 */
 		dentry = parent;
-		while (dentry && !lockref_put_or_lock(&dentry->d_lockref)) {
-			parent = lock_parent(dentry);
-			if (dentry->d_lockref.count != 1) {
-				dentry->d_lockref.count--;
-				spin_unlock(&dentry->d_lock);
-				if (parent)
-					spin_unlock(&parent->d_lock);
-				break;
-			}
-			inode = dentry->d_inode;	/* can't be NULL */
-			if (unlikely(!spin_trylock(&inode->i_lock))) {
-				spin_unlock(&dentry->d_lock);
-				if (parent)
-					spin_unlock(&parent->d_lock);
-				cpu_relax();
-				continue;
-			}
-			__dentry_kill(dentry);
-			dentry = parent;
-		}
+		while (dentry && !lockref_put_or_lock(&dentry->d_lockref))
+			dentry = dentry_kill(dentry);
 	}
 }
 

2.11.0

shrink_dentry_list() holds dentry->d_lock and needs to acquire dentry->d_inode->i_lock. This cannot be done with a spin_lock() operation because it's the reverse of the regular lock order. To avoid ABBA deadlocks it is done with a trylock loop.

Trylock loops are problematic in two scenarios:

1) PREEMPT_RT converts spinlocks to 'sleeping' spinlocks, which are preemptible. As a consequence the i_lock holder can be preempted by a higher priority task. If that task executes the trylock loop it will do so forever and live lock.

2) In virtual machines trylock loops are problematic as well. The VCPU on which the i_lock holder runs can be scheduled out and a task on a different VCPU can loop for a whole time slice. In the worst case this can lead to starvation. Commits 47be61845c77 ("fs/dcache.c: avoid soft-lockup in dput()") and 046b961b45f9 ("shrink_dentry_list(): take parent's d_lock earlier") are addressing exactly those symptoms.

Avoid the trylock loop by using dentry_kill(). When killing dentries from the dispose list, it is very similar to killing a dentry in dput(). The difference is that dput() expects to be the last user of the dentry (refcount=1) and will deref whereas shrink_dentry_list() expects there to be no user (refcount=0). In order to handle both situations with the same code, move the deref code from dentry_kill() into a new wrapper function dentry_put_kill(), which can be used by previous dentry_kill() users. Then shrink_dentry_list() can use the dentry_kill() to cleanup the dispose list.

This also has the benefit that the locking order is now the same. First the inode is locked, then the parent.

---
 fs/dcache.c | 58 ++++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 36 insertions(+), 22 deletions(-)

index e470d49daa54..23a90a64d74f 100644
@@ -690,11 +690,17 @@ static bool dentry_lock_inode(struct dentry *dentry)
 
 /*
  * Finish off a dentry we've decided to kill.
- * dentry->d_lock must be held, returns with it unlocked.
- * Returns dentry requiring refcount drop, or NULL if we're done.
+ * dentry->d_lock must be held and returns with it unlocked if the
+ * dentry was killed.
+ *
+ * Returns parent dentry requiring refcount drop or NULL if we're done
+ * or ERR_PTR(-EINTR) if the dentry was not killed because its refcount
+ * changed while preparing to kill.
+ *
+ * Note, if the dentry was not killed, i.e. ERR_PTR(-EINTR) returned,
+ * dentry->d_lock is left locked!
  */
 static struct dentry *dentry_kill(struct dentry *dentry)
-	__releases(dentry->d_lock)
 {
 	int saved_count = dentry->d_lockref.count;
 	struct dentry *parent;

@@ -741,6 +747,27 @@ static struct dentry *dentry_kill(struct dentry *dentry)
 	return parent;
 
 out_ref_changed:
+	/* dentry->d_lock still locked! */
+	return ERR_PTR(-EINTR);
+}
+
+/*
+ * Finish off a dentry where we are the last user (refcount=1) and
+ * we've decided to kill it.
+ * dentry->d_lock must be held, returns with it unlocked.
+ * Returns dentry requiring refcount drop, or NULL if we're done.
+ */
+static struct dentry *dentry_put_kill(struct dentry *dentry)
+	__releases(dentry->d_lock)
+{
+	struct dentry *parent;
+
+	parent = dentry_kill(dentry);
+	if (likely(!IS_ERR(parent)))
+		return parent;
+
+	/* dentry->d_lock still held */
+
 	/*
 	 * The refcount was incremented while dentry->d_lock was dropped.
 	 * Just decrement the refcount, unlock, and tell the caller to

@@ -927,7 +954,7 @@ void dput(struct dentry *dentry)
 	return;
 
 kill_it:
-	dentry = dentry_kill(dentry);
+	dentry = dentry_put_kill(dentry);
 	if (dentry)
 		goto repeat;
 }

@@ -1078,10 +1105,8 @@ static void shrink_dentry_list(struct list_head *list)
 	struct dentry *dentry, *parent;
 
 	while (!list_empty(list)) {
-		struct inode *inode;
 		dentry = list_entry(list->prev, struct dentry, d_lru);
 		spin_lock(&dentry->d_lock);
-		parent = lock_parent(dentry);
 
 		/*
 		 * The dispose list is isolated and dentries are not accounted

@@ -1089,15 +1114,13 @@ static void shrink_dentry_list(struct list_head *list)
 		 * here regardless of whether it is referenced or not.
 		 */
 		d_shrink_del(dentry);
-
+again:
 		/*
 		 * We found an inuse dentry which was not removed from
 		 * the LRU because of laziness during lookup. Do not free it.
 		 */
 		if (dentry->d_lockref.count > 0) {
 			spin_unlock(&dentry->d_lock);
-			if (parent)
-				spin_unlock(&parent->d_lock);
 			continue;
 		}
 

@@ -1105,23 +1128,14 @@ static void shrink_dentry_list(struct list_head *list)
 		if (unlikely(dentry->d_flags & DCACHE_DENTRY_KILLED)) {
 			bool can_free = dentry->d_flags & DCACHE_MAY_FREE;
 			spin_unlock(&dentry->d_lock);
-			if (parent)
-				spin_unlock(&parent->d_lock);
 			if (can_free)
 				dentry_free(dentry);
 			continue;
 		}
 
-		inode = dentry->d_inode;
-		if (inode && unlikely(!spin_trylock(&inode->i_lock))) {
-			d_shrink_add(dentry, list);
-			spin_unlock(&dentry->d_lock);
-			if (parent)
-				spin_unlock(&parent->d_lock);
-			continue;
-		}
-
-		__dentry_kill(dentry);
+		parent = dentry_kill(dentry);
+		if (unlikely(IS_ERR(parent)))
+			goto again;
 
 		/*
 		 * We need to prune ancestors too. This is necessary to prevent

@@ -1131,7 +1145,7 @@ static void shrink_dentry_list(struct list_head *list)
 		 */
 		dentry = parent;
 		while (dentry && !lockref_put_or_lock(&dentry->d_lockref))
-			dentry = dentry_kill(dentry);
+			dentry = dentry_put_kill(dentry);
 	}
 }
 

2.11.0

Current code moves the sucker to the end of list in that case; I'm not at all sure that what you are doing will improve the situation at all...

You *still* have a trylock loop there - only it keeps banging at the same dentry instead of going through the rest first...

Actually, it's even worse - _here_ you are dealing with something that really can change inode under you. This is one and only case where we are kicking out a zero-refcount dentry without having already held ->i_lock. At the very least, it's bloody different from regular dentry_kill(). In this case, dentry itself is protected from freeing by being on the shrink list - that's what makes __dentry_kill() to
leave the sucker allocated. We are not holding references, it is
hashed and anybody could come, pick it, d_delete() it, etc.

Hi Al,

I am responding to these comments first because they touch on some fundemental reasons behind the motivation of the patchset.

What I am doing is a loop, but it is not a trylock loop. The trylocks in the code only exist as likely() optimization. What I am doing is spinning on each lock I need in the correct locking order until I get them all. This is quite different than looping until I chance to get the locks I need by using only trylocks and in the incorrect locking order.

Yes, and that is why the new dentry_lock_inode() and dentry_kill() functions react to any changes in refcount and check for inode changes. Obviously for d_delete() the helper functions are checking way more than they need to. But if we've missed the trylock optimization we're already in the unlikely case, so the extra checks _may_ be acceptable in order to have simplified code. As Linus already pointed out, the cost of spinning will likely overshadow the cost of a few compares.

These patches consolidate the 4 trylocking loops into 3 helper
functions: dentry_lock_inode(), dentry_kill(), dentry_put_kill(). And these helper functions base off one another. Through that consolidation, all former trylock-loops are now spinning on locks in the correct locking order. This will directly address the two problems that are mentioned in the commit messages: PREEMPT_RT sleeping spinlocks with priorities and current cpu_relax()/cond_resched() efforts to try to handle bad luck in trylock loops.

Do you recommend I avoid consolidating the 4 trylock loops into the same set of helper functions and instead handle them all separately (as is the case in mainline)?

Or maybe the problem is how my patchset is assembling the final result. If patch 3 and 4 were refined to address your concerns about them but then by the end of the 6th patch we still end up where we are now, is that something that is palatable?

IOW, do the patches only need (possibly a lot of) refinement or do you consider this approach fundamentally flawed?

John Ogness

It's not that you are checking extra things - you are checking the wrong things. "Refcount has returned to original" is useless.

No. The place where you end up with dput() is flat-out wrong.

You are conflating the "we have a reference" cases with this one, and they are very different. Note, BTW, that had we raced with somebody else grabbing a reference, we would've quietly dropped dentry from the shrink list; what if we do the following: just after checking that refcount is not positive, do

	inode = dentry->d_inode;
	if unlikely(inode && !spin_trylock...)
		rcu_read_lock
		drop ->d_lock
		grab inode->i_lock
		grab ->d_lock
		if unlikely(dentry->d_inode != inode)
			drop inode->i_lock
			rcu_read_unlock
			if !killed
				drop ->d_lock
				drop parent's ->d_lock
				continue;
		else
			rcu_read_unlock
*before* going into
                if (unlikely(dentry->d_flags & DCACHE_DENTRY_KILLED)) {
                        bool can_free = dentry->d_flags & DCACHE_MAY_FREE;
                        spin_unlock(&dentry->d_lock);
			...

part?

Owww.... It's actually even nastier than I realized - dropping ->d_lock opens us to having the sucker freed by dput() from another thread here. IOW, between d_shrink_del(dentry) and __dentry_kill(dentry) dropping ->d_lock is dangerous...

It's really very different from all other cases, and the trickiest by far.

FWIW, my impression from the series:
1) dentry_kill() should deal with trylock failures on its own, leaving
the callers only the real "we need to drop the parent" case. See upthread for one variant of doing that.
2) switching parent eviction in shrink_dentry_list() to dentry_kill()
is fine.
3) for d_delete() trylock loop is wrong; however, it does not need
anything more elaborate than

{
        struct inode *inode;
        int isdir = d_is_dir(dentry);
        /*
         * Are we the only user?
         */
        spin_lock(&dentry->d_lock);
        if (dentry->d_lockref.count != 1)
		goto Shared;

        inode = dentry->d_inode;
	if (unlikely(!spin_trylock(&inode->i_lock))) {
		spin_unlock(&dentry->d_lock);
		spin_lock(&inode->i_lock);
		spin_lock(&dentry->d_lock);
		if (dentry->d_lockref.count != 1) {
			spin_unlock(&inode->i_lock);
			goto Shared;
		}
	}
           
	dentry->d_flags &= ~DCACHE_CANT_MOUNT;
	dentry_unlink_inode(dentry);
	fsnotify_nameremove(dentry, isdir);
	return;

Shared: /* can't make it negative, must unhash */

        if (!d_unhashed(dentry))
                __d_drop(dentry);
        spin_unlock(&dentry->d_lock);

        fsnotify_nameremove(dentry, isdir);
}

If not an outright "lock inode first from the very beginning" - note that inode is stable (and non-NULL) here. IOW, that needs to be compared with

{
        struct inode *inode = dentry->d_inode;
        int isdir = d_is_dir(dentry);
        spin_lock(&inode->i_lock);
        spin_lock(&dentry->d_lock);
        /*
         * Are we the only user?
         */
        if (dentry->d_lockref.count == 1) {
		dentry->d_flags &= ~DCACHE_CANT_MOUNT;
		dentry_unlink_inode(dentry);
	} else {
		if (!d_unhashed(dentry))
			__d_drop(dentry);
		spin_unlock(&dentry->d_lock);
		spin_unlock(&inode->i_lock);
	}
	fsnotify_nameremove(dentry, isdir);
}

That costs an extra boinking the ->i_lock in case dentry is shared, but it's much shorter and simpler that way. Needs profiling; if the second variant does not give worse performance, I would definitely prefer that one.
4) the nasty one - shrink_dentry_list() evictions of zero-count dentries.
_That_ calls for careful use of RCU, etc. - none of the others need that. Need to think how to deal with that sucker; in any case, I do not believe that sharing said RCU use, etc. with any other cases would do anything other than obfuscating the rest.

Arrrgh... Actually, there's a nasty corner case where the variant in mainline is broken. Look:
dentry placed on a shrink list
we pick the fucker from the list and lock it.
we call lock_parent() on it.
dentry is not a root and it's not deleted, so we proceed. trylock fails.
we grab rcu_read_lock()
we drop dentry->d_lock
on another CPU, something does e.g. d_prune_aliases() (or finds the sucker in hash and proceeds to unhash and dput(), etc.) - anything that evicts that dentry. It is marked with DCACHE_MAY_FREE and left alone. The parent, OTOH, is dropped and freeing gets scheduled as soon as RCU allows.
we grab parent->d_lock
we verify that dentry->d_parent is still the same (it is) we do rcu_read_unlock()
we grab dentry->d_lock
we return parent
At that point we are fucked - there's nothing to prevent parent from being freed at any point. And we assume that its ->d_lock is held and needs to be dropped.

The call site in d_prune_aliases() avoids the same scenario, since there we are already holding ->i_lock and another thread won't get to __dentry_kill() until we are done with lock_parent().

Unless I'm missing something, that's a (narrow) memory corruptor. The window is narrow, but not impossibly so - if that other thread had been spinning on attempt to grab dentry->d_lock in d_prune_alias(), it has to squeeze through

                if (!dentry->d_lockref.count) {
and then in lock_parent() called there - through
        if (IS_ROOT(dentry))
                return NULL;
        if (unlikely(dentry->d_lockref.count < 0))
                return NULL;
        if (likely(spin_trylock(&parent->d_lock)))
before the first CPU gets through
        parent = READ_ONCE(dentry->d_parent);
        spin_lock(&parent->d_lock);

The first CPU can't be preempted, but there's nothing to prevent an IRQ arriving at that point, letting the second one win the race.

Comments?

I think the (untested) patch below is -stable fodder:

lock_parent() needs to recheck if dentry got __dentry_kill'ed under it

In case when dentry passed to lock_parent() is protected from freeing only by the fact that it's on a shrink list and trylock of parent fails, we could get hit by __dentry_kill() (and subsequent dentry_kill(parent)) between unlocking dentry and locking presumed parent. We need to recheck that dentry is alive once we lock both it and parent *and* postpone rcu_read_unlock() until after that point. Otherwise we could return a pointer to struct dentry that already is rcu-scheduled for freeing, with ->d_lock held on it; caller's subsequent attempt to unlock it can end up with memory corruption.

---

index 7c38f39958bc..32aaab21e648 100644
@@ -647,11 +647,16 @@ static inline struct dentry *lock_parent(struct dentry *dentry)
 		spin_unlock(&parent->d_lock);
 		goto again;
 	}
-	rcu_read_unlock();
-	if (parent != dentry)
+	if (parent != dentry) {
 		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
-	else
+		if (unlikely(dentry->d_lockref.count < 0)) {
+			spin_unlock(&parent->d_lock);
+			parent = NULL;
+		}
+	} else {
 		parent = NULL;
+	}
+	rcu_read_unlock();
 	return parent;
 }
 

[ deleted the bad things ]

Should we just instead get the ref to the dentry before dropping the lock, so that nobody else can get to dentry_kill?

This is too subtle, and your fix to check d_lockref.count < 0 sounds wrong to me. If it's really gone, maybe it has been reused and the refcount is positive again, but it's something else than a dentry entirely?

Hmm.

No, you extended the rcu read section, so I guess your patch is fine. And lock_parent already has that pattern, soiit's not new.

Ok, I agree, looks like lock_parent should just re-check that thing that it already checked earler, but that now might be true again because of we dropped d_lock.

Linus

IMO that's the right thing for backports; whether we keep it after the getting rid of trylock loops is a different question. Note that the only case where we do not have __dentry_kill() prevention guaranteed by the caller (either by holding a reference, or by holding onto ->i_lock all along) is in shrink_dentry_list(). And there we have more than enough of other subtle crap.

Moreover, there we have a good reason to treat "it had been moved" as "kick it off the shrink list and free if it's already dead", which might simplify the things. Below is a stab at that:

/*
* ONLY for shrink_dentry_list() - it returns false if it finds
* dentry grabbed, moved or killed, which is fine there but not
* anywhere else. OTOH, nobody else needs to deal with dentries
* getting killed under them.
*/
static bool shrink_lock_for_kill(struct dentry *dentry)

{
	if (dentry->d_lockref.count)
		return false;

	inode = dentry->d_inode;
	if (inode && unlikely(!spin_trylock(&inode->i_lock))) {
		rcu_read_lock();	/* to protect inode */
		spin_unlock(&dentry->d_lock);
		spin_lock(&inode->i_lock);
		spin_lock(&dentry->d_lock);
		if (unlikely(dentry->d_lockref.count))
			goto out;
		/* changed inode means that somebody had grabbed it */
		if (unlikely(inode != dentry->d_inode))
			goto out;
		rcu_read_unlock();
	}

	parent = dentry->d_parent;
	if (IS_ROOT(dentry) || likely(spin_trylock(&parent->d_lock)))
		return true;
	
	rcu_read_lock();		/* to protect parent */
	spin_unlock(&dentry->d_lock);
	parent = READ_ONCE(dentry->d_parent);
	spin_lock(&parent->d_lock);
	if (unlikely(parent != dentry->d_parent)) {
		spin_unlock(&parent->d_lock);
		spin_lock(&dentry->d_lock);
		goto out;
	}
	spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
	if (likely(!dentry->d_lockref.count)) {
		rcu_read_unlock();
		return true;
	}
	spin_unlock(&parent->d_lock);
out:
	spin_unlock(&inode->i_lock);
	rcu_read_unlock();
	return false;
}

static void shrink_dentry_list(struct list_head *list)

{
	struct dentry *dentry, *parent;

	while (!list_empty(list)) {
		struct inode *inode;
		dentry = list_entry(list->prev, struct dentry, d_lru);
		spin_lock(&dentry->d_lock);
		if (!shrink_lock_for_kill(dentry)) {
			bool can_free = false;
			d_shrink_del(dentry);
			if (dentry->d_lockref.count < 0)
				can_free = dentry->d_flags & DCACHE_MAY_FREE;
			spin_unlock(&dentry->d_lock);
			if (can_free)
				dentry_free(dentry);
			continue;
		}
		d_shrink_del(dentry);
		parent = dentry->d_parent;
		__dentry_kill(dentry);
		if (dentry == parent)
			continue;
		dentry = parent;
		.... 
		same as now
		....
	}
}

FWIW, a variant of that series is in #work.dcache; it's almost certainly not the final (I want to clean the things up and probably reorder them as well) and it needs one hell of profiling and review. It seems to work, and I don't see any obvious performance regressions (everything seems to be within normal noise), but I'd like it beaten up a lot more.

Parts are from John's series, parts are rewritten as discussed upthread. As the result, trylock loops are gone and no new retry loops had been added in their place - lock_parent() still has one, but that's it.

I'll play with cleaning up and reordering tomorrow after I get some sleep. In the meanwhile, the current state of that set is at
git://git.kernel.org/pub/scm/linux/kernel/git/viro/vfs.git #work.dcache

I have one comment on your new dentry_kill()...

Nah, better handle that in retain_dentry() itself. See updated #work.dcache.

Note: another potentially fun thing in that branch is that I've finally decided to bite the bullet and make __d_move() preserve ->d_parent of target.

Mainline:

al@sonny:/tmp$ touch d
al@sonny:/tmp$ sleep 100 >/tmp/a/b/c &
[1] 16487
al@sonny:/tmp$ ls -l /proc/16487/fd
total 0
lrwx------ 1 al al 64 Mar 12 11:33 0 -> /dev/pts/13
l-wx------ 1 al al 64 Mar 12 11:33 1 -> /tmp/a/b/c
lrwx------ 1 al al 64 Mar 12 11:33 2 -> /dev/pts/13
al@sonny:/tmp$ mv /tmp/d /tmp/a/b/c 
al@sonny:/tmp$ ls -l /proc/16487/fd
total 0
lrwx------ 1 al al 64 Mar 12 11:33 0 -> /dev/pts/13
l-wx------ 1 al al 64 Mar 12 11:33 1 -> /tmp/c (deleted)
lrwx------ 1 al al 64 Mar 12 11:33 2 -> /dev/pts/13

With that branch:

root@kvm1:/tmp# touch d
root@kvm1:/tmp# sleep 100 >/tmp/a/b/c &
[1] 2263
root@kvm1:/tmp# ls -l /proc/2263/fd
total 0
lrwx------ 1 root root 64 Mar 12 11:33 0 -> /dev/pts/0
l-wx------ 1 root root 64 Mar 12 11:33 1 -> /tmp/a/b/c
lrwx------ 1 root root 64 Mar 12 11:33 2 -> /dev/pts/0
root@kvm1:/tmp# mv /tmp/d /tmp/a/b/c
root@kvm1:/tmp# ls -l /proc/2263/fd
total 0
lrwx------ 1 root root 64 Mar 12 11:33 0 -> /dev/pts/0
l-wx------ 1 root root 64 Mar 12 11:33 1 -> '/tmp/a/b/c (deleted)'
lrwx------ 1 root root 64 Mar 12 11:33 2 -> /dev/pts/0

It doesn't come quite for free; cross-directory d_move() and d_exchange() callers are responsible for having both parents pinned (all of them do that, mostly since the usual sequence is "look parents up, lock_rename(), *then* look children up, then do renaming"; those that are not part of rename(2) are also OK) and d_splice_alias() has become potentially blocking in one case. AFAICS, none of the callers is in locking environment that would not allow that. Survives the local beating and doesn't seem to cause any performance regressions.

What we get out of that is
a) much saner semantics for d_move() et.al.
b) saner behaviour of d_path() (see above)
c) dentry can be IS_ROOT only if it has been
such all along; that simplifies the hell out of analysis.

FWIW, there's another trylock loop on dentries - one in autofs get_next_positive_dentry(). Any plans re dealing with that one?

I'd spent the last couple of weeks (when not being too sick for any work) going through dcache.c and related code; hopefully this time I will get the documentation into postable shape ;-/

There's an unpleasant area around the ->s_root vs. NFS. There's code that makes assumptions about ->s_root that are simply not true for NFS. Is path_connected() correct wrt NFS multiple imports from the same server? Ditto for mnt_already_visible() (that one might be mitigated at the moment, but probably won't last). Eric, am I missing something subtle in there?

BTW, another thing spotted while trying to document the stuff:
Neil's "VFS: don't keep disconnected dentries on d_anon" has a subtle side effect I hadn't spotted when applying. Namely, for DCACHE_DISCONNECTED non-directory IS_ROOT dentries we now have d_unhashed() true. That makes d_find_alias() logics around discon_alias dead code:

                if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
                        if (IS_ROOT(alias) &&
                            (alias->d_flags & DCACHE_DISCONNECTED)) {
                                discon_alias = alias;
                        } else {
                                __dget_dlock(alias);
                                spin_unlock(&alias->d_lock);
                                return alias;
                        }
                }

Directory case is a red herring - we'll end up picking one and only alias, whether it's IS_ROOT/disconnected or not. For non-directories, though, IS_ROOT and disconnected implies d_unhashed() now, so we might as well turn that into
if directory
return d_find_any_alias
else
return the first hashed alias

Does any of the d_find_alias() callers want those dentries? That is, non-directories from d_obtain_alias() still not attached to a parent; note that exportfs_decode_fh() is *not* one of such places - we don't use d_find_alias() there at all. If there's no such caller, we can bloody well just drop the discon_alias logics and be done with that; if there is, that commit has introduced a bug. I might have missed a part of threads related to that patch, so my apologies if it had been discussed.

Neil, what's the situation there? A lot of those callers clearly treat the "only disconnected IS_ROOT alias exist" same as "no aliases at all"; it looks like the change might have been the right thing, but it sure as hell shouldn't be an undocumented side effect...

FWIW, callers are
drivers/staging/lustre/lustre/llite/llite_lib.c:2448: dentry = d_find_alias(page->mapping->host);
definitely doesn't want them
fs/ceph/caps.c:2945: while ((dn = d_find_alias(inode))) {
fs/ceph/mds_client.c:1930: dentry = d_find_alias(inode);
ditto - it's building a pathname.
fs/ceph/mds_client.c:2910: dentry = d_find_alias(inode);
ditto.
fs/ceph/mds_client.c:3374: parent = d_find_alias(inode);
clearly at least expects a directory (feeds to d_lookup(), etc.)
fs/coda/cache.c:112: alias_de = d_find_alias(inode);
directory-only
fs/fat/namei_vfat.c:736: alias = d_find_alias(inode);
we will reject any IS_ROOT there anyway
fs/fs-writeback.c:2071: dentry = d_find_alias(inode);
wants a name, these don't have one.
fs/fuse/dir.c:966: dir = d_find_alias(parent);
directory-only
fs/hostfs/hostfs_kern.c:129: dentry = d_find_alias(ino);
wants a pathname
fs/nilfs2/super.c:931: dentry = d_find_alias(inode);
directory-only
fs/nilfs2/super.c:1025: dentry = d_find_alias(inode);
bloody better be a directory (root one, at that)
fs/xfs/xfs_filestream.c:293: dentry = d_find_alias(inode);
no parent, no love.
mm/shmem.c:3435: dentry = d_find_alias(inode);
no d_obtain_alias() on that one
security/commoncap.c:391: dentry = d_find_alias(inode);
security/lsm_audit.c:295: dentry = d_find_alias(inode);
wants a name
security/selinux/hooks.c:1536: dentry = d_find_alias(inode);
security/selinux/hooks.c:1646: dentry = d_find_alias(inode);

So all but four of them clearly do *not* want those suckers. And remaining ones are in
* ceph invalidate_aliases()
* cap_inode_getsecurity()
* selinux inode_doinit_with_dentry() (two call sites, very alike)
Do any of those want that stuff?

I agree that this code is now more complex than needed.

Yes, this looks like a good simplification.

Many of the callers really want a name, which these disconnected dentries didn't have, so the new code is more correct in those cases.

d_find_alias() is documented as returning a hashed dentry (for non-directories) and I suspect most people would be surprised to find that a disconnected dentry with no name was considered to be "hashed", so I think the patch could be seen as fixing the documentation.

Of the three users that you didn't classify as "clearly" not wanting the disconnected dentries:

This wants to ensure the dentries are discarded on final dput(). This is already the case for disconnected dentries, so it doesn't need to be told about them. Code is correct.

If this gets invoked when the nfsd server calls vfs_getxattr() on a disconnected dentry, it will return -EINVAL. This looks like a potential bug.
nfsd only calls vfs_getxattr() in nfsd4_is_junction() so this bug would not affect many use cases.
I think cap_inode_getsecurity() should really be calling d_find_any_alias().

I'm less sure about this one, but I think it probably wants d_find_any_alias() as well. Like cap_inode_getsecurity() it only wants a dentry so that it can pass something to __vfs_getxattr(), and that only wants a dentry so it can pass something to ->get.

Possibly we should rename d_find_alias() to d_find_hashed_alias() so that people need to make a conscious choice between d_find_hashed_alias() and d_find_any_alias() ??

Thanks,
NeilBrown

FWIW, it *is* a bug; this
/*
* this is can be hit on boot when a file is accessed
* before the policy is loaded. When we load policy we
* may find inodes that have no dentry on the
* sbsec->isec_head list. No reason to complain as these
* will get fixed up the next time we go through
* inode_doinit with a dentry, before these inodes could
* be used again by userspace.
*/
in selinux/hooks.c is flat-out wrong now. Sure, if you first load selinux policy after exporting something over NFS or letting attacker play with open-by-fhandle, you are past any help, but still...

I disagree about going for d_find_any_alias() from the very beginning, BTW - we need to try it in case of d_find_alias() failure, but sufficiently crappy filesystem can bloody well fail to access xattrs via disconnected dentry.

I don't have the entire context in my head. But I don't think we have problems today.

NFS before it uses paths from an unconnected root in the rest of the vfs walks those paths backwards and makes the paths connect. I don't remember where all of that code that performs those connections but I do remember the code in fs/fhandle.c shares that code with nfs, to perform the same operation in open_by_handle_at.

So I don't think the nfs peculiarities are actually relevant to anything on an ordinary code path.

Of the two code paths you are concert about:

For path path_connected looking at s_root is a heuristic to avoid calling is_subdir every time we need to do that check. If the heuristic fails we still have is_subdir which should remain accurate. If is_subdir fails the path is genuinely not connected at that moment and failing is the correct thing to do.

For mnt_too_revealing the only filesystems under consideration are
proc and sysfs. So nfs oddities are of no consequence.
mnt_too_revealing probably won't be extended to other filesystems. Certainly nfs is not a candidate for having setting SB_I_USERNS_VISIBLE.

Al is that sufficient to address your concerns?

Eric

Umm... That might be not good enough - the logics is "everything's reachable from ->s_root anyway, so we might as well not bother checking". For NFS it's simply not true.

We can mount server:/foo/bar/baz on /tmp/a, then server:/foo on /tmp/b and we'll have ->s_root pointing to a subtree of what's reachable at /tmp/b. Play with renames under /tmp/b and you just might end up with a problem. And mount on /tmp/a will be (mistakenly) considered to be safe, since it satisfies the heuristics in path_connected().

If I am parsing the code correctly path_connected is broken for nfsv2
and nfsv3 when NFS_MOUNT_UNSHARED is not set. nfsv4 appears to make
a kernel mount of the real root of the filesystem properly setting s_root and then finds the child it is mounting.

Agreed.

Which means that if you mount server:/foo/bar/baz first and then mount server:/foo with an appropriate rename you might be able to see all of server:/foo or possibly server:/

Hmm..

Given that nfs_kill_super calls generic_shutdown_super and generic_shutdown_super calls shrink_dcache_for_umount I would argue that nfsv2 and nfsv3 are buggy in the same case, as shrink_dcache_for_umount is called on something that is not the root of the filesystem's dentry tree.

Eric

Ah. I see now there is now the s_roots list that handles that bit of strangeness.

So one path is to simply remove the heuristic from path_connected.

Another path is to have nfsv2 and nfsv3 not set s_root at all. Leaving the heuristic working for the rest of the filesystems, and generally simplifying the code.

Something like the diff below I should think.

Eric

 fs/dcache.c      |  3 ++-
 fs/nfs/getroot.c | 35 +----------------------------------
 fs/nfs/super.c   |  2 --
 3 files changed, 3 insertions(+), 37 deletions(-)

index 7c38f39958bc..ebe63ca026da 100644
@@ -1501,7 +1501,8 @@ void shrink_dcache_for_umount(struct super_block *sb)
 
 	dentry = sb->s_root;
 	sb->s_root = NULL;
-	do_one_tree(dentry);
+	if (dentry)
+		do_one_tree(dentry);
 
 	while (!hlist_bl_empty(&sb->s_roots)) {
 		dentry = dget(hlist_bl_entry(hlist_bl_first(&sb->s_roots), struct dentry, d_hash));

index 391dafaf9182..f609d583fd2b 100644
@@ -36,35 +36,6 @@
 
 #define NFSDBG_FACILITY		NFSDBG_CLIENT
 
-/*
- * Set the superblock root dentry.
- * Note that this function frees the inode in case of error.
- */
-static int nfs_superblock_set_dummy_root(struct super_block *sb, struct inode *inode)
-{
-	/* The mntroot acts as the dummy root dentry for this superblock */
-	if (sb->s_root == NULL) {
-		sb->s_root = d_make_root(inode);
-		if (sb->s_root == NULL)
-			return -ENOMEM;
-		ihold(inode);
-		/*
-		 * Ensure that this dentry is invisible to d_find_alias().
-		 * Otherwise, it may be spliced into the tree by
-		 * d_splice_alias if a parent directory from the same
-		 * filesystem gets mounted at a later time.
-		 * This again causes shrink_dcache_for_umount_subtree() to
-		 * Oops, since the test for IS_ROOT() will fail.
-		 */
-		spin_lock(&d_inode(sb->s_root)->i_lock);
-		spin_lock(&sb->s_root->d_lock);
-		hlist_del_init(&sb->s_root->d_u.d_alias);
-		spin_unlock(&sb->s_root->d_lock);
-		spin_unlock(&d_inode(sb->s_root)->i_lock);
-	}
-	return 0;
-}
-
 /*
  * get an NFS2/NFS3 root dentry from the root filehandle
  */

@@ -102,11 +73,7 @@ struct dentry *nfs_get_root(struct super_block *sb, struct nfs_fh *mntfh,
 		goto out;
 	}
 
-	error = nfs_superblock_set_dummy_root(sb, inode);
-	if (error != 0) {
-		ret = ERR_PTR(error);
-		goto out;
-	}
+	/* Leave nfsv2 and nfsv3 s_root == NULL */
 
 	/* root dentries normally start off anonymous and get spliced in later
 	 * if the dentry tree reaches them; however if the dentry already

index 29bacdc56f6a..30b45ea4dfe9 100644
@@ -2625,9 +2625,7 @@ struct dentry *nfs_fs_mount_common(struct nfs_server *server,
 		}
 		s->s_bdi->ra_pages = server->rpages * NFS_MAX_READAHEAD;
 		server->super = s;
-	}
 
-	if (!s->s_root) {
 		/* initial superblock/root creation */
 		mount_info->fill_super(s, mount_info);
 		nfs_get_cache_cookie(s, mount_info->parsed, mount_info->cloned);

BTW, if rename happens on server and we step into directory we'd already seen in one subtree while doing a lookup in another, we will get it moved around. Without having the subtrees ever connected in dcache on client. So adding && IS_ROOT(sb->s_root) to the test also won't work.

Nope. We fundamentally need to call is_subdir in the nfs case to ensure we don't have crazy problems.

I believe below is the obviously correct fix (that still preserves some caching). I need to look at nilfs as it also calls d_obtain_root. I am also wondering if some of the other network filesystems might be susceptible to problems caused by renames on the server.

It is tempting to be more clever and not consider NFS_MOUNT_UNSHARED mounts or mounts without mulitple s_roots but there can be renames on the server that should trip up even those cases. At least if anything figures out how to trigger the dentries in the path to ever get revalidated.

Eric

index 921ae32dbc80..cafa365eeb70 100644
@@ -559,9 +559,10 @@ static int __nd_alloc_stack(struct nameidata *nd)
 static bool path_connected(const struct path *path)
 {
 	struct vfsmount *mnt = path->mnt;
+	struct super_block *sb = mnt->mnt_sb;
 
-	/* Only bind mounts can have disconnected paths */
-	if (mnt->mnt_root == mnt->mnt_sb->s_root)
+	/* Bind mounts and multi-root filesystems can have disconnected paths */
+	if (!(sb->s_iflags & SB_I_MULTIROOT) && (mnt->mnt_root == sb->s_root))
 		return true;
 
 	return is_subdir(path->dentry, mnt->mnt_root);

index 29bacdc56f6a..64129a72f312 100644
@@ -2631,6 +2631,7 @@ struct dentry *nfs_fs_mount_common(struct nfs_server *server,
 		/* initial superblock/root creation */
 		mount_info->fill_super(s, mount_info);
 		nfs_get_cache_cookie(s, mount_info->parsed, mount_info->cloned);
+		s->s_iflags |= SB_I_MULTIROOT;
 	}
 
 	mntroot = nfs_get_root(s, mount_info->mntfh, dev_name);

index 2a815560fda0..0430e03febaa 100644
@@ -1317,6 +1317,7 @@ extern int send_sigurg(struct fown_struct *fown);
 #define SB_I_CGROUPWB	0x00000001	/* cgroup-aware writeback enabled */
 #define SB_I_NOEXEC	0x00000002	/* Ignore executables on this fs */
 #define SB_I_NODEV	0x00000004	/* Ignore devices on this fs */
+#define SB_I_MULTIROOT	0x00000008	/* Multiple roots to the dentry tree */
 
 /* sb->s_iflags to limit user namespace mounts */
 #define SB_I_USERNS_VISIBLE		0x00000010 /* fstype already mounted */

On nfsv2 and nfsv3 the nfs server can export subsets of the same filesystem and report the same filesystem identifier, so that the nfs client can know they are the same filesystem. The subsets can be from disjoint directory trees. The nfsv2 and nfsv3 filesystems provides no way to find the common root of all directory trees exported form the server with the same filesystem identifier.

The practical result is that in struct super s_root for nfs s_root is not necessarily the root of the filesystem. The nfs mount code sets s_root to the root of the first subset of the nfs filesystem that the kernel mounts.

This effects the dcache invalidation code in generic_shutdown_super currently called shrunk_dcache_for_umount and that code for years has gone through an additional list of dentries that might be dentry trees that need to be freed to accomodate nfs.

When I wrote path_connected I did not realize nfs was so special, and it's hueristic for avoiding calling is_subdir can fail.

The practical case where this fails is when there is a move of a directory from the subtree exposed by one nfs mount to the subtree exposed by another nfs mount. This move can happen either locally or remotely. With the remote case requiring that the move directory be cached before the move and that after the move someone walks the path to where the move directory now exists and in so doing causes the already cached directory to be moved in the dcache through the magic of d_splice_alias.

If someone whose working directory is in the move directory or a subdirectory and now starts calling .. from the initial mount of nfs (where s_root == mnt_root), then path_connected as a heuristic will not bother with the is_subdir check. As s_root really is not the root of the nfs filesystem this heuristic is wrong, and the path may actually not be connected and path_connected can fail.

The is_subdir function might be cheap enough that we can call it unconditionally. Verifying that will take some benchmarking and the result may not be the same on all kernels this fix needs to be backported to. So I am avoiding that for now.

Filesystems with snapshots such as nilfs and btrfs do something similar. But as the directory tree of the snapshots are disjoint from one another and from the main directory tree rename won't move things between them and this problem will not occur.

---

Al do you want to push this one to Linus or shall I?

 fs/namei.c         | 5 +++--
 fs/nfs/super.c     | 2 ++
 include/linux/fs.h | 1 +
 3 files changed, 6 insertions(+), 2 deletions(-)

index 921ae32dbc80..cafa365eeb70 100644
@@ -559,9 +559,10 @@ static int __nd_alloc_stack(struct nameidata *nd)
 static bool path_connected(const struct path *path)
 {
 	struct vfsmount *mnt = path->mnt;
+	struct super_block *sb = mnt->mnt_sb;
 
-	/* Only bind mounts can have disconnected paths */
-	if (mnt->mnt_root == mnt->mnt_sb->s_root)
+	/* Bind mounts and multi-root filesystems can have disconnected paths */
+	if (!(sb->s_iflags & SB_I_MULTIROOT) && (mnt->mnt_root == sb->s_root))
 		return true;
 
 	return is_subdir(path->dentry, mnt->mnt_root);

index 29bacdc56f6a..5e470e233c83 100644
@@ -2631,6 +2631,8 @@ struct dentry *nfs_fs_mount_common(struct nfs_server *server,
 		/* initial superblock/root creation */
 		mount_info->fill_super(s, mount_info);
 		nfs_get_cache_cookie(s, mount_info->parsed, mount_info->cloned);
+		if (!(server->flags & NFS_MOUNT_UNSHARED))
+			s->s_iflags |= SB_I_MULTIROOT;
 	}
 
 	mntroot = nfs_get_root(s, mount_info->mntfh, dev_name);

index 2a815560fda0..0430e03febaa 100644
@@ -1317,6 +1317,7 @@ extern int send_sigurg(struct fown_struct *fown);
 #define SB_I_CGROUPWB	0x00000001	/* cgroup-aware writeback enabled */
 #define SB_I_NOEXEC	0x00000002	/* Ignore executables on this fs */
 #define SB_I_NODEV	0x00000004	/* Ignore devices on this fs */
+#define SB_I_MULTIROOT	0x00000008	/* Multiple roots to the dentry tree */
 
 /* sb->s_iflags to limit user namespace mounts */
 #define SB_I_USERNS_VISIBLE		0x00000010 /* fstype already mounted */

2.14.1

Applied; I think there might be a helper lurking in there, but for now that'll do.

That's not a problem - it will simply evict a subtree first, then go through ->s_roots and kill each piece.

Nice.

It's on our list and we wanted to wait for the final resolution of dcache before tackling it. Do you have any immediate ide about that?

Documentation is surely welcome. Paging that code back in is a mindboggling exercise.

Thanks,

tglx

	if (unlikely(dentry->d_lockref.count != 1)) {
		dentry->d_lockref.count--;
	} else if (likely(!retain_dentry(dentry))) {
		__dentry_kill(dentry);
		return parent;
	} else {
		dentry->d_lockref.count--;
		dentry_lru_add(dentry);
	}

I will need to dig into it a bit deeper (I am unfamiliar with autofs), but it looks like it is trying to do basically the same thing as the ascend loop in d_walk().

Thank you for all your help in getting these changes cleaned and correctly implemented so quickly.

I've reviewed your latest trylock loop removal patches and found only 1 minor issue. I'll post that separately.

John Ogness

Hi Al,

1 minor issue on the new shrink_lock_dentry()...

Nope. We have parent, yes, but it had been fetched outside of rcu_read_lock(). So the object it used to point to might have been already freed and we can't do this:

To get rid of that reread we'd need to do this:

	rcu_read_lock();
        parent = dentry->d_parent;
        if (IS_ROOT(dentry) || likely(spin_trylock(&parent->d_lock))) {
		rcu_read_unlock();
                return true;
	}
        spin_unlock(&dentry->d_lock);
        spin_lock(&parent->d_lock);
        if (unlikely(parent != dentry->d_parent)) {
		....

Come to think of that, it might make sense to lift rcu_read_lock() all the way out of that sucker. Objections? Below is the incremental I'd fold into that commit:

index f0e73c93182b..0d1dac750c0a 100644
@@ -1000,7 +1000,6 @@ static bool shrink_lock_dentry(struct dentry *dentry)
 
 	inode = dentry->d_inode;
 	if (inode && unlikely(!spin_trylock(&inode->i_lock))) {
-		rcu_read_lock();	/* to protect inode */
 		spin_unlock(&dentry->d_lock);
 		spin_lock(&inode->i_lock);
 		spin_lock(&dentry->d_lock);

@@ -1009,16 +1008,14 @@ static bool shrink_lock_dentry(struct dentry *dentry)
 		/* changed inode means that somebody had grabbed it */
 		if (unlikely(inode != dentry->d_inode))
 			goto out;
-		rcu_read_unlock();
 	}
 
 	parent = dentry->d_parent;
+	/* parent will stay allocated until we drop rcu_read_lock */
 	if (IS_ROOT(dentry) || likely(spin_trylock(&parent->d_lock)))
 		return true;
 
-	rcu_read_lock();		/* to protect parent */
 	spin_unlock(&dentry->d_lock);
-	parent = READ_ONCE(dentry->d_parent);
 	spin_lock(&parent->d_lock);
 	if (unlikely(parent != dentry->d_parent)) {
 		spin_unlock(&parent->d_lock);

@@ -1026,14 +1023,11 @@ static bool shrink_lock_dentry(struct dentry *dentry)
 		goto out;
 	}
 	spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
-	if (likely(!dentry->d_lockref.count)) {
-		rcu_read_unlock();
+	if (likely(!dentry->d_lockref.count))
 		return true;
-	}
 	spin_unlock(&parent->d_lock);
 out:
 	spin_unlock(&inode->i_lock);
-	rcu_read_unlock();
 	return false;
 }
 

@@ -1044,8 +1038,10 @@ static void shrink_dentry_list(struct list_head *list)
 
 		dentry = list_entry(list->prev, struct dentry, d_lru);
 		spin_lock(&dentry->d_lock);
+		rcu_read_lock();
 		if (!shrink_lock_dentry(dentry)) {
 			bool can_free = false;
+			rcu_read_unlock();
 			d_shrink_del(dentry);
 			if (dentry->d_lockref.count < 0)
 				can_free = dentry->d_flags & DCACHE_MAY_FREE;

@@ -1054,6 +1050,7 @@ static void shrink_dentry_list(struct list_head *list)
 				dentry_free(dentry);
 			continue;
 		}
+		rcu_read_unlock();
 		d_shrink_del(dentry);
 		parent = dentry->d_parent;
 		__dentry_kill(dentry);

Looks clearer to me.

When rcu_read_lock() is called, we are still holding dentry->d_lock. At that point dentry->d_parent cannot have changed and cannot have been freed. So the parent fetched outside of rcu_read_lock() is also protected from freeing inside that rcu_read_lock().

Agreed.

If you have something in mind, I could fire up something.

I've put it in -RT, let it do some upgrades and other things and nothing bad happened so far.

Sebastian

I'm not hating it.

It may be because I got used (resigned?) to this from the discussion around the previous version. But it looks ok to me.

But this is very much an area where I do want Al to ack it all, so let's see if he's any happier now.

Linus