Skip to contentSkip to conversation

Per-superblock unused dentry LRU lists V3

PATCH In review David Chinner 4 participants 6 messages May 26, 2006 – May 31, 2006 1 message not in the archive VFS

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Per-superblock unused dentry LRU lists V3

Per superblock dentry LRU lists.

As originally described in:

http://marc.theaimsgroup.com/?l=linux-kernel&m=114491661527656&w=2

shrink_dcache_sb() becomes a severe bottleneck when the unused dentry list becomes long and mounts and unmounts occur frequently on the machine.

The patch attached below is based on the suggestion made by Andrew Morton here:

http://marc.theaimsgroup.com/?l=linux-fsdevel&m=114499224412427&w=2

I've attempted to make reclaim fair by keeping track of the last superblock we pruned, and starting from the next one in the list each time.

Version 3:

o fix found count in select_parent() so that shrink_dcache_parent works again
o minor comment fixes

Version 2:

o cleaned up coding style
o added comments where required
o ported to 2.6.17-rc4-mm3
o added s_umount locking to prune_dcache()
o added counter for number of dentries on a superblock

---

 fs/dcache.c        |  291 +++++++++++++++++++++++++----------------------------
 fs/super.c         |    1 
 include/linux/fs.h |    2 
 3 files changed, 145 insertions(+), 149 deletions(-)
fs/dcache.c +144 -161
Index: linux-2.6.16/fs/dcache.c
===================================================================
@@ -61,7 +61,6 @@ static kmem_cache_t *dentry_cache __read
 static unsigned int d_hash_mask __read_mostly;
 static unsigned int d_hash_shift __read_mostly;
 static struct hlist_head *dentry_hashtable __read_mostly;
-static LIST_HEAD(dentry_unused);
 
 /* Statistics gathering. */
 struct dentry_stat_t dentry_stat = {
@@ -113,6 +112,38 @@ static void dentry_iput(struct dentry * 
 	}
 }
 
+static void dentry_lru_add(struct dentry *dentry)
+{
+	list_add(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
+	dentry->d_sb->s_dentry_lru_nr++;
+	dentry_stat.nr_unused++;
+}
+
+static void dentry_lru_add_tail(struct dentry *dentry)
+{
+	list_add_tail(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
+	dentry->d_sb->s_dentry_lru_nr++;
+	dentry_stat.nr_unused++;
+}
+
+static void dentry_lru_del(struct dentry *dentry)
+{
+	if (!list_empty(&dentry->d_lru)) {
+		list_del(&dentry->d_lru);
+		dentry->d_sb->s_dentry_lru_nr--;
+		dentry_stat.nr_unused--;
+	}
+}
+
+static void dentry_lru_del_init(struct dentry *dentry)
+{
+	if (likely(!list_empty(&dentry->d_lru))) {
+		list_del_init(&dentry->d_lru);
+		dentry->d_sb->s_dentry_lru_nr--;
+		dentry_stat.nr_unused--;
+	}
+}
+
 /* 
  * This is dput
  *
@@ -172,8 +203,7 @@ repeat:
 		goto kill_it;
   	if (list_empty(&dentry->d_lru)) {
   		dentry->d_flags |= DCACHE_REFERENCED;
-  		list_add(&dentry->d_lru, &dentry_unused);
-  		dentry_stat.nr_unused++;
+		dentry_lru_add(dentry);
   	}
  	spin_unlock(&dentry->d_lock);
 	spin_unlock(&dcache_lock);
@@ -185,13 +215,8 @@ unhash_it:
 kill_it: {
 		struct dentry *parent;
 
-		/* If dentry was on d_lru list
-		 * delete it from there
-		 */
-  		if (!list_empty(&dentry->d_lru)) {
-  			list_del(&dentry->d_lru);
-  			dentry_stat.nr_unused--;
-  		}
+		/* If dentry was on d_lru list delete it from there */
+		dentry_lru_del(dentry);
   		list_del(&dentry->d_u.d_child);
 		dentry_stat.nr_dentry--;	/* For d_free, below */
 		/*drops the locks, at that point nobody can reach this dentry */
@@ -267,10 +292,7 @@ int d_invalidate(struct dentry * dentry)
 static inline struct dentry * __dget_locked(struct dentry *dentry)
 {
 	atomic_inc(&dentry->d_count);
-	if (!list_empty(&dentry->d_lru)) {
-		dentry_stat.nr_unused--;
-		list_del_init(&dentry->d_lru);
-	}
+	dentry_lru_del_init(dentry);
 	return dentry;
 }
 
@@ -380,11 +402,57 @@ static void prune_one_dentry(struct dent
 	spin_lock(&dcache_lock);
 }
 
+/*
+ * Shrink the dentry LRU on a given superblock.
+ *
+ * If flags is non-zero, we need to do special processing based on
+ * which flags are set. This means we don't need to maintain multiple
+ * similar copies of this loop.
+ */
+static void __shrink_dcache_sb(struct super_block *sb, int *count, int flags)
+{
+	struct dentry *dentry;
+	int cnt = *count;
+
+	spin_lock(&dcache_lock);
+	while (!list_empty(&sb->s_dentry_lru) && cnt--) {
+		dentry = list_entry(sb->s_dentry_lru.prev,
+					struct dentry, d_lru);
+		dentry_lru_del_init(dentry);
+		BUG_ON(dentry->d_sb != sb);
+		prefetch(sb->s_dentry_lru.prev);
+
+		spin_lock(&dentry->d_lock);
+		/*
+		 * We found an inuse dentry which was not removed from
+		 * the LRU because of laziness during lookup.  Do not free
+		 * it - just keep it off the LRU list.
+		 */
+		if (atomic_read(&dentry->d_count)) {
+			spin_unlock(&dentry->d_lock);
+			continue;
+		}
+		/*
+		 * If we are honouring the DCACHE_REFERENCED flag and the
+		 * dentry has this flag set, don't free it. Clear the flag
+		 * and put it back on the LRU
+		 */
+		if ((flags & DCACHE_REFERENCED) &&
+		    (dentry->d_flags & DCACHE_REFERENCED)) {
+			dentry->d_flags &= ~DCACHE_REFERENCED;
+			dentry_lru_add(dentry);
+			spin_unlock(&dentry->d_lock);
+			continue;
+		}
+		prune_one_dentry(dentry);
+	}
+	spin_unlock(&dcache_lock);
+	*count = cnt;
+}
+
 /**
  * prune_dcache - shrink the dcache
  * @count: number of entries to try and free
- * @sb: if given, ignore dentries for other superblocks
- *         which are being unmounted.
  *
  * Shrink the dcache. This is done when we need
  * more memory, or simply when we need to unmount
@@ -395,110 +463,64 @@ static void prune_one_dentry(struct dent
  * all the dentries are in use.
  */
  
-static void prune_dcache(int count, struct super_block *sb)
+static void prune_dcache(int count)
 {
-	spin_lock(&dcache_lock);
-	for (; count ; count--) {
-		struct dentry *dentry;
-		struct list_head *tmp;
-		struct rw_semaphore *s_umount;
-
-		cond_resched_lock(&dcache_lock);
-
-		tmp = dentry_unused.prev;
-		if (unlikely(sb)) {
-			/* Try to find a dentry for this sb, but don't try
-			 * too hard, if they aren't near the tail they will
-			 * be moved down again soon
-			 */
-			int skip = count;
-			while (skip && tmp != &dentry_unused &&
-			    list_entry(tmp, struct dentry, d_lru)->d_sb != sb) {
-				skip--;
-				tmp = tmp->prev;
-			}
-		}
-		if (tmp == &dentry_unused)
-			break;
-		list_del_init(tmp);
-		prefetch(dentry_unused.prev);
- 		dentry_stat.nr_unused--;
-		dentry = list_entry(tmp, struct dentry, d_lru);
-
- 		spin_lock(&dentry->d_lock);
-		/*
-		 * We found an inuse dentry which was not removed from
-		 * dentry_unused because of laziness during lookup.  Do not free
-		 * it - just keep it off the dentry_unused list.
-		 */
- 		if (atomic_read(&dentry->d_count)) {
- 			spin_unlock(&dentry->d_lock);
-			continue;
-		}
-		/* If the dentry was recently referenced, don't free it. */
-		if (dentry->d_flags & DCACHE_REFERENCED) {
-			dentry->d_flags &= ~DCACHE_REFERENCED;
- 			list_add(&dentry->d_lru, &dentry_unused);
- 			dentry_stat.nr_unused++;
- 			spin_unlock(&dentry->d_lock);
+	struct super_block *sb;
+	static struct super_block *sb_hand = NULL;
+	int work_done = 0;
+
+	spin_lock(&sb_lock);
+	if (sb_hand == NULL)
+		sb_hand = sb_entry(super_blocks.next);
+restart:
+	list_for_each_entry(sb, &super_blocks, s_list) {
+		if (sb != sb_hand)
 			continue;
-		}
 		/*
-		 * If the dentry is not DCACHED_REFERENCED, it is time
-		 * to remove it from the dcache, provided the super block is
-		 * NULL (which means we are trying to reclaim memory)
-		 * or this dentry belongs to the same super block that
-		 * we want to shrink.
+		 * Found the next superblock to work on.  Move the hand
+		 * forwards so that parallel pruners work on a different sb
 		 */
+		work_done++;
+		sb_hand = sb_entry(sb->s_list.next);
+		sb->s_count++;
+		spin_unlock(&sb_lock);
+
 		/*
-		 * If this dentry is for "my" filesystem, then I can prune it
-		 * without taking the s_umount lock (I already hold it).
+		 * We need to be sure this filesystem isn't being unmounted,
+		 * otherwise we could race with generic_shutdown_super(), and
+		 * end up holding a reference to an inode while the filesystem
+		 * is unmounted.  So we try to get s_umount, and make sure
+		 * s_root isn't NULL.
 		 */
-		if (sb && dentry->d_sb == sb) {
-			prune_one_dentry(dentry);
-			continue;
+		if (down_read_trylock(&sb->s_umount)) {
+			if ((sb->s_root != NULL) &&
+			    (!list_empty(&sb->s_dentry_lru))) {
+				__shrink_dcache_sb(sb, &count,
+						DCACHE_REFERENCED);
+			}
+			up_read(&sb->s_umount);
 		}
+
 		/*
-		 * ...otherwise we need to be sure this filesystem isn't being
-		 * unmounted, otherwise we could race with
-		 * generic_shutdown_super(), and end up holding a reference to
-		 * an inode while the filesystem is unmounted.
-		 * So we try to get s_umount, and make sure s_root isn't NULL.
-		 * (Take a local copy of s_umount to avoid a use-after-free of
-		 * `dentry').
+		 * restart only when sb is no longer on the list and
+		 * we have more work to do.
 		 */
-		s_umount = &dentry->d_sb->s_umount;
-		if (down_read_trylock(s_umount)) {
-			if (dentry->d_sb->s_root != NULL) {
-				prune_one_dentry(dentry);
-				up_read(s_umount);
-				continue;
-			}
-			up_read(s_umount);
-		}
-		spin_unlock(&dentry->d_lock);
-		/* Cannot remove the first dentry, and it isn't appropriate
-		 * to move it to the head of the list, so give up, and try
-		 * later
+		spin_lock(&sb_lock);
+		if (__put_super_and_need_restart(sb) && count)
+			goto restart;
+		if (count <= 0)
+			break;
+	}
+	if (!work_done) {
+		/*
+		 * sb_hand is stale. Start and the beginning of the list again.
 		 */
-		break;
+		sb_hand = sb_entry(super_blocks.next);
+		goto restart;
 	}
-	spin_unlock(&dcache_lock);
+	spin_unlock(&sb_lock);
 }
 
-/*
- * Shrink the dcache for the specified super block.
- * This allows us to unmount a device without disturbing
- * the dcache for the other devices.
- *
- * This implementation makes just two traversals of the
- * unused list.  On the first pass we move the selected
- * dentries to the most recent end, and on the second
- * pass we free them.  The second pass must restart after
- * each dput(), but since the target dentries are all at
- * the end, it's really just a single traversal.
- */
-
 /**
  * shrink_dcache_sb - shrink dcache for a superblock
  * @sb: superblock
@@ -507,44 +529,9 @@ static void prune_dcache(int count, stru
  * is used to free the dcache before unmounting a file
  * system
  */
-
 void shrink_dcache_sb(struct super_block * sb)
 {
-	struct list_head *tmp, *next;
-	struct dentry *dentry;
-
-	/*
-	 * Pass one ... move the dentries for the specified
-	 * superblock to the most recent end of the unused list.
-	 */
-	spin_lock(&dcache_lock);
-	list_for_each_safe(tmp, next, &dentry_unused) {
-		dentry = list_entry(tmp, struct dentry, d_lru);
-		if (dentry->d_sb != sb)
-			continue;
-		list_move(tmp, &dentry_unused);
-	}
-
-	/*
-	 * Pass two ... free the dentries for this superblock.
-	 */
-repeat:
-	list_for_each_safe(tmp, next, &dentry_unused) {
-		dentry = list_entry(tmp, struct dentry, d_lru);
-		if (dentry->d_sb != sb)
-			continue;
-		dentry_stat.nr_unused--;
-		list_del_init(tmp);
-		spin_lock(&dentry->d_lock);
-		if (atomic_read(&dentry->d_count)) {
-			spin_unlock(&dentry->d_lock);
-			continue;
-		}
-		prune_one_dentry(dentry);
-		cond_resched_lock(&dcache_lock);
-		goto repeat;
-	}
-	spin_unlock(&dcache_lock);
+	__shrink_dcache_sb(sb, &sb->s_dentry_lru_nr, 0);
 }
 
 /*
@@ -628,17 +615,14 @@ resume:
 		struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
 		next = tmp->next;
 
-		if (!list_empty(&dentry->d_lru)) {
-			dentry_stat.nr_unused--;
-			list_del_init(&dentry->d_lru);
-		}
+		dentry_lru_del_init(dentry);
+
 		/* 
 		 * move only zero ref count dentries to the end 
 		 * of the unused list for prune_dcache
 		 */
 		if (!atomic_read(&dentry->d_count)) {
-			list_add_tail(&dentry->d_lru, &dentry_unused);
-			dentry_stat.nr_unused++;
+			dentry_lru_add_tail(dentry);
 			found++;
 		}
 
@@ -680,10 +664,11 @@ out:
  
 void shrink_dcache_parent(struct dentry * parent)
 {
+	struct super_block *sb = parent->d_sb;
 	int found;
 
 	while ((found = select_parent(parent)) != 0)
-		prune_dcache(found, parent->d_sb);
+		__shrink_dcache_sb(sb, &found, 0);
 }
 
 /**
@@ -701,29 +686,27 @@ void shrink_dcache_anon(struct super_blo
 	struct hlist_node *lp;
 	struct hlist_head *head = &sb->s_anon;
 	int found;
-	do {
+	for (;;) {
 		found = 0;
 		spin_lock(&dcache_lock);
 		hlist_for_each(lp, head) {
 			struct dentry *this = hlist_entry(lp, struct dentry, d_hash);
-			if (!list_empty(&this->d_lru)) {
-				dentry_stat.nr_unused--;
-				list_del_init(&this->d_lru);
-			}
 
+			dentry_lru_del_init(this);
 			/* 
 			 * move only zero ref count dentries to the end 
 			 * of the unused list for prune_dcache
 			 */
 			if (!atomic_read(&this->d_count)) {
-				list_add_tail(&this->d_lru, &dentry_unused);
-				dentry_stat.nr_unused++;
+				dentry_lru_add_tail(this);
 				found++;
 			}
 		}
 		spin_unlock(&dcache_lock);
-		prune_dcache(found, sb);
-	} while(found);
+		if (!found)
+			break;
+		__shrink_dcache_sb(sb, &found, 0);
+	}
 }
 
 /*
@@ -743,7 +726,7 @@ static int shrink_dcache_memory(int nr, 
 	if (nr) {
 		if (!(gfp_mask & __GFP_FS))
 			return -1;
-		prune_dcache(nr, NULL);
+		prune_dcache(nr);
 	}
 	return (dentry_stat.nr_unused / 100) * sysctl_vfs_cache_pressure;
 }
@@ -1072,7 +1055,7 @@ struct dentry *d_splice_alias(struct ino
  * rcu_read_lock() and rcu_read_unlock() are used to disable preemption while
  * lookup is going on.
  *
- * dentry_unused list is not updated even if lookup finds the required dentry
+ * The dentry unused LRU is not updated even if lookup finds the required dentry
  * in there. It is updated in places such as prune_dcache, shrink_dcache_sb,
  * select_parent and __dget_locked. This laziness saves lookup from dcache_lock
  * acquisition.
include/linux/fs.h +2 -0
Index: linux-2.6.16/include/linux/fs.h
===================================================================
@@ -846,6 +846,8 @@ struct super_block {
 	struct list_head	s_io;		/* parked for writeback */
 	struct hlist_head	s_anon;		/* anonymous dentries for (nfs) exporting */
 	struct list_head	s_files;
+	struct list_head	s_dentry_lru;	/* unused dentry lru */
+	int			s_dentry_lru_nr;/* # of dentries on lru */
 
 	struct block_device	*s_bdev;
 	struct list_head	s_instances;
fs/super.c +1 -0
Index: linux-2.6.16/fs/super.c
===================================================================
@@ -71,6 +71,7 @@ static struct super_block *alloc_super(v
 		INIT_LIST_HEAD(&s->s_instances);
 		INIT_HLIST_HEAD(&s->s_anon);
 		INIT_LIST_HEAD(&s->s_inodes);
+		INIT_LIST_HEAD(&s->s_dentry_lru);
 		init_rwsem(&s->s_umount);
 		mutex_init(&s->s_lock);
 		down_write(&s->s_umount);
#1 lore raw
Quoted 36 lines · David Chinner

Per superblock dentry LRU lists.

...

fs/dcache.c +31 -0
+/*
+ * Shrink the dentry LRU on a given superblock.
+ *
+ * If flags is non-zero, we need to do special processing based on
+ * which flags are set. This means we don't need to maintain multiple
+ * similar copies of this loop.
+ */
+static void __shrink_dcache_sb(struct super_block *sb, int *count, int flags)
+{
+	struct dentry *dentry;
+	int cnt = *count;
+
+	spin_lock(&dcache_lock);
+	while (!list_empty(&sb->s_dentry_lru) && cnt--) {
+		dentry = list_entry(sb->s_dentry_lru.prev,
+					struct dentry, d_lru);
+		dentry_lru_del_init(dentry);
+		BUG_ON(dentry->d_sb != sb);
+		prefetch(sb->s_dentry_lru.prev);
+
+		spin_lock(&dentry->d_lock);
+		/*
+		 * We found an inuse dentry which was not removed from
+		 * the LRU because of laziness during lookup.  Do not free
+		 * it - just keep it off the LRU list.
+		 */
+		if (atomic_read(&dentry->d_count)) {
+			spin_unlock(&dentry->d_lock);
+			continue;
+		}
+		/*

fs/dcache.c static void prune_one_dentry(struct dent · line 445

Quoted 10 lines
fs/dcache.c +10 -0
+		 * If we are honouring the DCACHE_REFERENCED flag and the
+		 * dentry has this flag set, don't free it. Clear the flag
+		 * and put it back on the LRU
+		 */
+		if ((flags & DCACHE_REFERENCED) &&
+		    (dentry->d_flags & DCACHE_REFERENCED)) {
+			dentry->d_flags &= ~DCACHE_REFERENCED;
+			dentry_lru_add(dentry);
+			spin_unlock(&dentry->d_lock);
+			continue;

Here we put the dentry back onto the list which we're currently scanning. So if `cnt' exceeds the number of dentries on this superblock we end up scanning some of them more than once.

Seems odd.

Quoted 21 lines
fs/dcache.c +11 -4
-static void prune_dcache(int count, struct super_block *sb)
+static void prune_dcache(int count)
 {
 
...
 
+	struct super_block *sb;
+	static struct super_block *sb_hand = NULL;
+	int work_done = 0;
+
+	spin_lock(&sb_lock);
+	if (sb_hand == NULL)
+		sb_hand = sb_entry(super_blocks.next);
+restart:
+	list_for_each_entry(sb, &super_blocks, s_list) {
+		if (sb != sb_hand)
 			continue;
-		}
 		/*
-		 * If the dentry is not DCACHED_REFERENCED, it is time
-		 * to remove it from the dcache, provided the super block is

fs/dcache.c static void prune_one_dentry(struct dent · line 486

Quoted 10 lines
fs/dcache.c +6 -3
-		 * NULL (which means we are trying to reclaim memory)
-		 * or this dentry belongs to the same super block that
-		 * we want to shrink.
+		 * Found the next superblock to work on.  Move the hand
+		 * forwards so that parallel pruners work on a different sb
 		 */
+		work_done++;
+		sb_hand = sb_entry(sb->s_list.next);
+		sb->s_count++;
+		spin_unlock(&sb_lock);

Now sb_hand points at a superblock against which we have no reference. How can we use sb_hand safely next time we call in here? It could point at a now-freed superblock?

A better approach might be to rotate the super_blocks list as we walk through it, so the search always starts at super_blocks.next - that way, there's no need to introduce a new global to record where we're up to.

Quoted 7 lines
fs/dcache.c +4 -2
 		/*
-		 * If this dentry is for "my" filesystem, then I can prune it
-		 * without taking the s_umount lock (I already hold it).
+		 * We need to be sure this filesystem isn't being unmounted,
+		 * otherwise we could race with generic_shutdown_super(), and
+		 * end up holding a reference to an inode while the filesystem
+		 * is unmounted.  So we try to get s_umount, and make sure

fs/dcache.c static void prune_one_dentry(struct dent · line 499

Quoted 10 lines
fs/dcache.c +6 -3
+		 * s_root isn't NULL.
 		 */
-		if (sb && dentry->d_sb == sb) {
-			prune_one_dentry(dentry);
-			continue;
+		if (down_read_trylock(&sb->s_umount)) {
+			if ((sb->s_root != NULL) &&
+			    (!list_empty(&sb->s_dentry_lru))) {
+				__shrink_dcache_sb(sb, &count,
+						DCACHE_REFERENCED);

um. If `count' is 10000 and we have 100 superblocks each with 1000 dentries, we end up scanning the first five to ten (depending upon DCACHE_REFERENCED density) superblocks to exhaustion and the rest not at all. I think.

If so, I'd have thought that we'd be better off putting some balancing arithmetic in here.

number of dentries to scan on this sb =
count * (number of dentries on this sb /
number of dentries in the machine)

#2 lore raw
Quoted 15 lines · Andrew Morton
Quoted 14 lines · David Chinner

Per superblock dentry LRU lists.

...

fs/dcache.c +9 -0
+/*
+ * Shrink the dentry LRU on a given superblock.
+ *
+ * If flags is non-zero, we need to do special processing based on
+ * which flags are set. This means we don't need to maintain multiple
+ * similar copies of this loop.
+ */
+static void __shrink_dcache_sb(struct super_block *sb, int *count, int flags)
+{

....

Quoted 7 lines
Quoted 7 lines
fs/dcache.c +7 -0
+		/*
+		 * If we are honouring the DCACHE_REFERENCED flag and the
+		 * dentry has this flag set, don't free it. Clear the flag
+		 * and put it back on the LRU
+		 */
+		if ((flags & DCACHE_REFERENCED) &&
+		    (dentry->d_flags & DCACHE_REFERENCED)) {
Quoted 8 lines

fs/dcache.c static void prune_one_dentry(struct dent · line 445

Quoted 4 lines
fs/dcache.c +4 -0
+			dentry->d_flags &= ~DCACHE_REFERENCED;
+			dentry_lru_add(dentry);
+			spin_unlock(&dentry->d_lock);
+			continue;

Here we put the dentry back onto the list which we're currently scanning. So if `cnt' exceeds the number of dentries on this superblock we end up scanning some of them more than once.

Good point. Should be easy to fix because we know exactly how many dentries are on the list before we start scanning...

Quoted 29 lines

Seems odd.

Quoted 27 lines
fs/dcache.c +13 -7
-static void prune_dcache(int count, struct super_block *sb)
+static void prune_dcache(int count)
 {
 
...
 
+	struct super_block *sb;
+	static struct super_block *sb_hand = NULL;
+	int work_done = 0;
+
+	spin_lock(&sb_lock);
+	if (sb_hand == NULL)
+		sb_hand = sb_entry(super_blocks.next);
+restart:
+	list_for_each_entry(sb, &super_blocks, s_list) {
+		if (sb != sb_hand)
 			continue;
-		}
 		/*
-		 * If the dentry is not DCACHED_REFERENCED, it is time
-		 * to remove it from the dcache, provided the super block is
-		 * NULL (which means we are trying to reclaim memory)
-		 * or this dentry belongs to the same super block that
-		 * we want to shrink.
+		 * Found the next superblock to work on.  Move the hand
+		 * forwards so that parallel pruners work on a different sb
 		 */
Quoted 8 lines

fs/dcache.c static void prune_one_dentry(struct dent · line 486

Quoted 4 lines
fs/dcache.c +4 -0
+		work_done++;
+		sb_hand = sb_entry(sb->s_list.next);
+		sb->s_count++;
+		spin_unlock(&sb_lock);

Now sb_hand points at a superblock against which we have no reference. How can we use sb_hand safely next time we call in here? It could point at a now-freed superblock?

Yes, it could. but we don't use what sb_hand points at unless it matches something in the list. Therefore it only gets used when it is valid.

If sb_hand is not valid, then it won't match with any of the sb's in the list, we exist the loop, work_done is zero, and we restart after setting sb_hand back to the first entry in the list.

Quoted 3 lines

A better approach might be to rotate the super_blocks list as we walk through it, so the search always starts at super_blocks.next - that way, there's no need to introduce a new global to record where we're up to.

hmm, that'll stuff up other threads walking the superblock list. If we rotate the head while they are in the middle of walking the list, then we'll need more logic in __put_super_and_need_restart() to handle the list head changing while traversals are occuring. It also makes it difficult to give parallel shrinkers different superblocks to work on because we can't rotate the head until we've traversed the entire list or count is exhausted in prune_dcache....

Quoted 14 lines
Quoted 14 lines
fs/dcache.c +7 -5
 		/*
-		 * If this dentry is for "my" filesystem, then I can prune it
-		 * without taking the s_umount lock (I already hold it).
+		 * We need to be sure this filesystem isn't being unmounted,
+		 * otherwise we could race with generic_shutdown_super(), and
+		 * end up holding a reference to an inode while the filesystem
+		 * is unmounted.  So we try to get s_umount, and make sure
+		 * s_root isn't NULL.
 		 */
-		if (sb && dentry->d_sb == sb) {
-			prune_one_dentry(dentry);
-			continue;
+		if (down_read_trylock(&sb->s_umount)) {
+			if ((sb->s_root != NULL) &&
Quoted 8 lines

fs/dcache.c static void prune_one_dentry(struct dent · line 499

Quoted 3 lines
fs/dcache.c +3 -0
+			    (!list_empty(&sb->s_dentry_lru))) {
+				__shrink_dcache_sb(sb, &count,
+						DCACHE_REFERENCED);

um. If `count' is 10000 and we have 100 superblocks each with 1000 dentries, we end up scanning the first five to ten (depending upon DCACHE_REFERENCED density) superblocks to exhaustion and the rest not at all. I think.

Yes, given the bug you pointed out above, then yes, that is probably correct. However, given that prune_dcache() only has one caller now - the shrinker - count is only ever going to be SHRINK_BATCH (128), this is not a big problem right now because each new call into prune_dcache will start on a different superblock...

Quoted 6 lines

If so, I'd have thought that we'd be better off putting some balancing arithmetic in here.

number of dentries to scan on this sb =
count * (number of dentries on this sb /
number of dentries in the machine)

Agreed, and as I pointed out in the thread following the first version of the patch I've been concerned with fixing the bug first. now that it appears that I've fixed the bug, I'm looking at how to make this fairer. The above is basically what I was thinking of doing.

It's a bit more complex than that, though. The above will always result in zero due to the integer division. Turning it around as (count * nr_sb) / nr_unused will lead to 32bit integer overflow with more than 20 million dentries on a superblock (which we already exceed quite easily)....

So I'm thinking that the dentry stats need to be converted to longs from ints as the only platforms where 32bit overflow will be a problem are 64bit platforms...

Thoughts?

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
R&D Software Enginner
SGI Australian Software Group
#4 lore raw
In reply to a message not in the archive
Quoted 88 lines

David Chinner <[email protected]> wrote:

fs/dcache.c +8 -0
+/*
+ * Shrink the dentry LRU on a given superblock.
+ *
+ * If flags is non-zero, we need to do special processing based on
+ * which flags are set. This means we don't need to maintain multiple
+ * similar copies of this loop.
+ */
+static void __shrink_dcache_sb(struct super_block *sb, int *count, int 

flags)

fs/dcache.c +40 -0
+{
+       struct dentry *dentry;
+       int cnt = *count;
+
+       spin_lock(&dcache_lock);
+       while (!list_empty(&sb->s_dentry_lru) && cnt--) {
+               dentry = list_entry(sb->s_dentry_lru.prev,
+                                       struct dentry, d_lru);
+               dentry_lru_del_init(dentry);
+               BUG_ON(dentry->d_sb != sb);
+               prefetch(sb->s_dentry_lru.prev);
+
+               spin_lock(&dentry->d_lock);
+               /*
+                * We found an inuse dentry which was not removed from
+                * the LRU because of laziness during lookup.  Do not free
+                * it - just keep it off the LRU list.
+                */
+               if (atomic_read(&dentry->d_count)) {
+                       spin_unlock(&dentry->d_lock);
+                       continue;
+               }
+               /*
+                * If we are honouring the DCACHE_REFERENCED flag and the
+                * dentry has this flag set, don't free it. Clear the flag
+                * and put it back on the LRU
+                */
+               if ((flags & DCACHE_REFERENCED) &&
+                   (dentry->d_flags & DCACHE_REFERENCED)) {
+                       dentry->d_flags &= ~DCACHE_REFERENCED;
+                       dentry_lru_add(dentry);
+                       spin_unlock(&dentry->d_lock);
+                       continue;
+               }
+               prune_one_dentry(dentry);
+       }
+       spin_unlock(&dcache_lock);
+       *count = cnt;
+}
+

/**
* shrink_dcache_sb - shrink dcache for a superblock
* @sb: superblock

fs/dcache.c +0 -28
@@ -507,44 +529,9 @@ static void prune_dcache(int count, stru
 * is used to free the dcache before unmounting a file
 * system
 */
-
 void shrink_dcache_sb(struct super_block * sb)
 {
-       struct list_head *tmp, *next;
-       struct dentry *dentry;
-
-       /*
-        * Pass one ... move the dentries for the specified
-        * superblock to the most recent end of the unused list.
-        */
-       spin_lock(&dcache_lock);
-       list_for_each_safe(tmp, next, &dentry_unused) {
-               dentry = list_entry(tmp, struct dentry, d_lru);
-               if (dentry->d_sb != sb)
-                       continue;
-               list_move(tmp, &dentry_unused);
-       }
-
-       /*
-        * Pass two ... free the dentries for this superblock.
-        */
-repeat:
-       list_for_each_safe(tmp, next, &dentry_unused) {
-               dentry = list_entry(tmp, struct dentry, d_lru);
-               if (dentry->d_sb != sb)
-                       continue;
-               dentry_stat.nr_unused--;
-               list_del_init(tmp);
-               spin_lock(&dentry->d_lock);
-               if (atomic_read(&dentry->d_count)) {

fs/dcache.c static void prune_dcache(int count, stru · line 535

Quoted 10 lines
fs/dcache.c +1 -8
-                       spin_unlock(&dentry->d_lock);
-                       continue;
-               }
-               prune_one_dentry(dentry);
-               cond_resched_lock(&dcache_lock);
-               goto repeat;
-       }
-       spin_unlock(&dcache_lock);
+       __shrink_dcache_sb(sb, &sb->s_dentry_lru_nr, 0);
 }

This doesn't prune all the dentries on the unused list. The parents of the pruned dentries are added to the unused list. Therefore just shrinking sb->s_dentry_lru_nr dentries isn't enough.

Jan

#5 lore raw
Quoted 4 lines · Jan Blunck
Quoted 4 lines

David Chinner <[email protected]> wrote:
-
void shrink_dcache_sb(struct super_block * sb)
{

....

Quoted 6 lines
Quoted 2 lines

+ __shrink_dcache_sb(sb, &sb->s_dentry_lru_nr, 0);
}

This doesn't prune all the dentries on the unused list. The parents of the pruned dentries are added to the unused list. Therefore just shrinking sb->s_dentry_lru_nr dentries isn't enough.

Yes, you are right, Jan. I'm surprised I didn't see problems due to this. The original patch got this right by shrinking in this case until the list was empty. I'll wrap this one in a while loop...

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
R&D Software Enginner
SGI Australian Software Group
#6 lore raw
Quoted 12 lines · David Chinner
Quoted 4 lines · Jan Blunck
Quoted 4 lines

David Chinner <[email protected]> wrote:
-
void shrink_dcache_sb(struct super_block * sb)
{

....

Quoted 5 lines
Quoted 2 lines

+ __shrink_dcache_sb(sb, &sb->s_dentry_lru_nr, 0);
}

This doesn't prune all the dentries on the unused list. The parents of the pruned dentries are added to the unused list. Therefore just shrinking sb->s_dentry_lru_nr dentries isn't enough.

Quoted 7 lines

Yes, you are right, Jan. I'm surprised I didn't see problems due to this. The original patch got this right by shrinking in this case until the list was empty. I'll wrap this one in a while loop...

Cheers,

Dave.

Good catch,

I suspect the reason why the problem never showed up is because select_parent() would take care of ensuring that the parent entries move to LRU list (this is the case of regular umounts, which do not call shrink_dcache_sb() directly).

Maybe even the dentry_unused list should be per-superblock now.

Signature · 4 lines
       Regards,
	Balbir Singh,
	Linux Technology Center,
	IBM Software Labs