[PATCH 4/13] vfs: Factor out tree (of four) shrinkers code

[Pavel Emelyanov <xemul@parallels.com>]

There are 4 dcache shrinkers in dcache.c now.

* prune_dcache one, which shrinks the dentries from the LRU list;
* shrink_dcache_parent, which tries to remove unused dentries from a
subtree starting from a given point;
* shrink_dcache_sb, which wants to acheive the same result as the
previous one, but starting from the given sb root;
* shink_dcache_for_umount, which also kills the dcache for a super
block, but it believes that all the subtree is unreachable and unused
and thus uses lighter locking and more strict checks.

That said, 3 last shrinkers do the same and deserve being factored out.

The srhink_dcache_parent uses the same tree walk as I propose to
shrink the dentry subtree from leaves to the roots, so things do not
get worse after this change.

The shrink_dcache_for_umount_subtree does the same walk as I propose,
but it will take the rename_lock. This is OK, since the rename_lock
is now per-sb and is taken on a dead super block and thus isn't
contented.

The shink_dcache_sb is O(n) before and after the change and seems OK
as well.

The walker code I use was copy-n-paste-d from have_submounts routine.
Yes, it's worth merging them (and the dcache_genocide ;) ).

Signed-off-by: Pavel Emelyanov <xemul@openvz.org>

---
 fs/dcache.c |  365 +++++++++++++++++++++--------------------------------------
 1 files changed, 130 insertions(+), 235 deletions(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index 976a917..67d6590 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -262,19 +262,6 @@ static void dentry_lru_del(struct dentry *dentry)
 	}
 }
 
-static void dentry_lru_move_tail(struct dentry *dentry)
-{
-	spin_lock(&dcache_lru_lock);
-	if (list_empty(&dentry->d_lru)) {
-		list_add_tail(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
-		dentry->d_sb->s_nr_dentry_unused++;
-		dentry_stat.nr_unused++;
-	} else {
-		list_move_tail(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
-	}
-	spin_unlock(&dcache_lru_lock);
-}
-
 /**
  * d_kill - kill dentry and return parent
  * @dentry: dentry to kill
@@ -649,6 +636,132 @@ restart:
 }
 EXPORT_SYMBOL(d_prune_aliases);
 
+static void isolate_shrinkable(struct dentry *dentry, struct list_head *list)
+{
+	if (!dentry->d_count) {
+		if (!IS_ROOT(dentry)) {
+			__d_drop(dentry);
+			list_del_init(&dentry->d_u.d_child);
+			dentry->d_parent->d_count--;
+			dentry->d_parent = dentry;
+		}
+
+		spin_lock(&dcache_lru_lock);
+		list_move_tail(&dentry->d_lru, list);
+		spin_unlock(&dcache_lru_lock);
+	} else
+		dentry_lru_del(dentry);
+}
+
+static void collect_shrinkable(struct dentry *root, struct list_head *list)
+{
+	struct dentry *this_parent;
+	struct list_head *next;
+	unsigned seq;
+	int locked = 0;
+
+	seq = read_seqbegin(&root->d_sb->s_rename_lock);
+again:
+	this_parent = root;
+	spin_lock(&this_parent->d_lock);
+repeat:
+	next = this_parent->d_subdirs.next;
+resume:
+	while (next != &this_parent->d_subdirs) {
+		struct list_head *tmp = next;
+		struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
+		next = tmp->next;
+
+		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
+		/*
+		 * Descend a level if the d_subdirs list is non-empty.
+		 */
+		if (!list_empty(&dentry->d_subdirs)) {
+			spin_unlock(&this_parent->d_lock);
+			spin_release(&dentry->d_lock.dep_map, 1, _RET_IP_);
+			this_parent = dentry;
+			spin_acquire(&this_parent->d_lock.dep_map, 0, 1, _RET_IP_);
+			goto repeat;
+		}
+
+		isolate_shrinkable(dentry, list);
+
+		spin_unlock(&dentry->d_lock);
+	}
+	/*
+	 * All done at this level ... ascend and resume the search.
+	 */
+	if (this_parent != root) {
+		struct dentry *tmp;
+		struct dentry *child;
+
+		tmp = this_parent->d_parent;
+		rcu_read_lock();
+		spin_unlock(&this_parent->d_lock);
+		child = this_parent;
+		this_parent = tmp;
+		spin_lock(&this_parent->d_lock);
+		/* might go back up the wrong parent if we have had a rename
+		 * or deletion */
+		if (this_parent != child->d_parent ||
+			(!locked && read_seqretry(&root->d_sb->s_rename_lock, seq))) {
+			spin_unlock(&this_parent->d_lock);
+			rcu_read_unlock();
+			goto rename_retry;
+		}
+		rcu_read_unlock();
+		next = child->d_u.d_child.next;
+
+		spin_lock_nested(&child->d_lock, DENTRY_D_LOCK_NESTED);
+		isolate_shrinkable(child, list);
+		spin_unlock(&child->d_lock);
+
+		goto resume;
+	}
+
+	spin_unlock(&this_parent->d_lock);
+	if (!locked && read_seqretry(&root->d_sb->s_rename_lock, seq))
+		goto rename_retry;
+	if (locked)
+		read_sequnlock(&root->d_sb->s_rename_lock);
+	return;
+
+rename_retry:
+	locked = 1;
+	read_seqlock(&root->d_sb->s_rename_lock);
+	goto again;
+}
+
+static void shrink_dcache_subtree(struct dentry *root, int with_root)
+{
+	LIST_HEAD(tmp);
+	struct dentry *de;
+
+	collect_shrinkable(root, &tmp);
+
+	if (with_root) {
+		if (root->d_count) {
+			printk("Root count is %d, kids:\n", root->d_count);
+			list_for_each_entry(de, &root->d_subdirs, d_u.d_child)
+				printk("  %s [%p, %d, %p, %s]\n",
+						de->d_name.name, de, de->d_count,
+						de->d_parent, de->d_parent->d_name.name);
+			BUG();
+		}
+
+		isolate_shrinkable(root, &tmp);
+	}
+
+	while (!list_empty(&tmp)) {
+		de = list_first_entry(&tmp, struct dentry, d_lru);
+		do {
+			spin_lock(&de->d_lock);
+			BUG_ON(de->d_count);
+			de = dentry_kill(de, 0);
+		} while (de);
+	}
+}
+
 /*
  * Try to throw away a dentry - free the inode, dput the parent.
  * Requires dentry->d_lock is held, and dentry->d_count == 0.
@@ -865,16 +978,7 @@ static void prune_dcache(int count)
  */
 void shrink_dcache_sb(struct super_block *sb)
 {
-	LIST_HEAD(tmp);
-
-	spin_lock(&dcache_lru_lock);
-	while (!list_empty(&sb->s_dentry_lru)) {
-		list_splice_init(&sb->s_dentry_lru, &tmp);
-		spin_unlock(&dcache_lru_lock);
-		shrink_dentry_list(&tmp);
-		spin_lock(&dcache_lru_lock);
-	}
-	spin_unlock(&dcache_lru_lock);
+	shrink_dcache_subtree(sb->s_root, 0);
 }
 EXPORT_SYMBOL(shrink_dcache_sb);
 
@@ -883,100 +987,6 @@ EXPORT_SYMBOL(shrink_dcache_sb);
  * - see the comments on shrink_dcache_for_umount() for a description of the
  *   locking
  */
-static void shrink_dcache_for_umount_subtree(struct dentry *dentry)
-{
-	struct dentry *parent;
-	unsigned detached = 0;
-
-	BUG_ON(!IS_ROOT(dentry));
-
-	/* detach this root from the system */
-	spin_lock(&dentry->d_lock);
-	dentry_lru_del(dentry);
-	__d_drop(dentry);
-	spin_unlock(&dentry->d_lock);
-
-	for (;;) {
-		/* descend to the first leaf in the current subtree */
-		while (!list_empty(&dentry->d_subdirs)) {
-			struct dentry *loop;
-
-			/* this is a branch with children - detach all of them
-			 * from the system in one go */
-			spin_lock(&dentry->d_lock);
-			list_for_each_entry(loop, &dentry->d_subdirs,
-					    d_u.d_child) {
-				spin_lock_nested(&loop->d_lock,
-						DENTRY_D_LOCK_NESTED);
-				dentry_lru_del(loop);
-				__d_drop(loop);
-				spin_unlock(&loop->d_lock);
-			}
-			spin_unlock(&dentry->d_lock);
-
-			/* move to the first child */
-			dentry = list_entry(dentry->d_subdirs.next,
-					    struct dentry, d_u.d_child);
-		}
-
-		/* consume the dentries from this leaf up through its parents
-		 * until we find one with children or run out altogether */
-		do {
-			struct inode *inode;
-
-			if (dentry->d_count != 0) {
-				printk(KERN_ERR
-				       "BUG: Dentry %p{i=%lx,n=%s}"
-				       " still in use (%d)"
-				       " [unmount of %s %s]\n",
-				       dentry,
-				       dentry->d_inode ?
-				       dentry->d_inode->i_ino : 0UL,
-				       dentry->d_name.name,
-				       dentry->d_count,
-				       dentry->d_sb->s_type->name,
-				       dentry->d_sb->s_id);
-				BUG();
-			}
-
-			if (IS_ROOT(dentry)) {
-				parent = NULL;
-				list_del(&dentry->d_u.d_child);
-			} else {
-				parent = dentry->d_parent;
-				spin_lock(&parent->d_lock);
-				parent->d_count--;
-				list_del(&dentry->d_u.d_child);
-				spin_unlock(&parent->d_lock);
-			}
-
-			detached++;
-
-			inode = dentry->d_inode;
-			if (inode) {
-				dentry->d_inode = NULL;
-				list_del_init(&dentry->d_alias);
-				if (dentry->d_op && dentry->d_op->d_iput)
-					dentry->d_op->d_iput(dentry, inode);
-				else
-					iput(inode);
-			}
-
-			d_free(dentry);
-
-			/* finished when we fall off the top of the tree,
-			 * otherwise we ascend to the parent and move to the
-			 * next sibling if there is one */
-			if (!parent)
-				return;
-			dentry = parent;
-		} while (list_empty(&dentry->d_subdirs));
-
-		dentry = list_entry(dentry->d_subdirs.next,
-				    struct dentry, d_u.d_child);
-	}
-}
-
 /*
  * destroy the dentries attached to a superblock on unmounting
  * - we don't need to use dentry->d_lock because:
@@ -999,11 +1009,11 @@ void shrink_dcache_for_umount(struct super_block *sb)
 	spin_lock(&dentry->d_lock);
 	dentry->d_count--;
 	spin_unlock(&dentry->d_lock);
-	shrink_dcache_for_umount_subtree(dentry);
+	shrink_dcache_subtree(dentry, 1);
 
 	while (!hlist_bl_empty(&sb->s_anon)) {
 		dentry = hlist_bl_entry(hlist_bl_first(&sb->s_anon), struct dentry, d_hash);
-		shrink_dcache_for_umount_subtree(dentry);
+		shrink_dcache_subtree(dentry, 1);
 	}
 }
 
@@ -1103,117 +1113,6 @@ rename_retry:
 }
 EXPORT_SYMBOL(have_submounts);
 
-/*
- * Search the dentry child list for the specified parent,
- * and move any unused dentries to the end of the unused
- * list for prune_dcache(). We descend to the next level
- * whenever the d_subdirs list is non-empty and continue
- * searching.
- *
- * It returns zero iff there are no unused children,
- * otherwise  it returns the number of children moved to
- * the end of the unused list. This may not be the total
- * number of unused children, because select_parent can
- * drop the lock and return early due to latency
- * constraints.
- */
-static int select_parent(struct dentry * parent)
-{
-	struct dentry *this_parent;
-	struct list_head *next;
-	unsigned seq;
-	int found = 0;
-	int locked = 0;
-
-	seq = read_seqbegin(&parent->d_sb->s_rename_lock);
-again:
-	this_parent = parent;
-	spin_lock(&this_parent->d_lock);
-repeat:
-	next = this_parent->d_subdirs.next;
-resume:
-	while (next != &this_parent->d_subdirs) {
-		struct list_head *tmp = next;
-		struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
-		next = tmp->next;
-
-		spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
-
-		/* 
-		 * move only zero ref count dentries to the end 
-		 * of the unused list for prune_dcache
-		 */
-		if (!dentry->d_count) {
-			dentry_lru_move_tail(dentry);
-			found++;
-		} else {
-			dentry_lru_del(dentry);
-		}
-
-		/*
-		 * We can return to the caller if we have found some (this
-		 * ensures forward progress). We'll be coming back to find
-		 * the rest.
-		 */
-		if (found && need_resched()) {
-			spin_unlock(&dentry->d_lock);
-			goto out;
-		}
-
-		/*
-		 * Descend a level if the d_subdirs list is non-empty.
-		 */
-		if (!list_empty(&dentry->d_subdirs)) {
-			spin_unlock(&this_parent->d_lock);
-			spin_release(&dentry->d_lock.dep_map, 1, _RET_IP_);
-			this_parent = dentry;
-			spin_acquire(&this_parent->d_lock.dep_map, 0, 1, _RET_IP_);
-			goto repeat;
-		}
-
-		spin_unlock(&dentry->d_lock);
-	}
-	/*
-	 * All done at this level ... ascend and resume the search.
-	 */
-	if (this_parent != parent) {
-		struct dentry *tmp;
-		struct dentry *child;
-
-		tmp = this_parent->d_parent;
-		rcu_read_lock();
-		spin_unlock(&this_parent->d_lock);
-		child = this_parent;
-		this_parent = tmp;
-		spin_lock(&this_parent->d_lock);
-		/* might go back up the wrong parent if we have had a rename
-		 * or deletion */
-		if (this_parent != child->d_parent ||
-			(!locked && read_seqretry(&parent->d_sb->s_rename_lock, seq))) {
-			spin_unlock(&this_parent->d_lock);
-			rcu_read_unlock();
-			goto rename_retry;
-		}
-		rcu_read_unlock();
-		next = child->d_u.d_child.next;
-		goto resume;
-	}
-out:
-	spin_unlock(&this_parent->d_lock);
-	if (!locked && read_seqretry(&parent->d_sb->s_rename_lock, seq))
-		goto rename_retry;
-	if (locked)
-		read_sequnlock(&parent->d_sb->s_rename_lock);
-	return found;
-
-rename_retry:
-	if (found)
-		return found;
-	locked = 1;
-	read_seqlock(&parent->d_sb->s_rename_lock);
-	goto again;
-}
-
 /**
  * shrink_dcache_parent - prune dcache
  * @parent: parent of entries to prune
@@ -1223,11 +1122,7 @@ rename_retry:
  
 void shrink_dcache_parent(struct dentry * parent)
 {
-	struct super_block *sb = parent->d_sb;
-	int found;
-
-	while ((found = select_parent(parent)) != 0)
-		__shrink_dcache_sb(sb, &found, 0);
+	shrink_dcache_subtree(parent, 0);
 }
 EXPORT_SYMBOL(shrink_dcache_parent);
 
-- 
1.5.5.6