Skip to contentSkip to conversation

Per-superblock unused dentry LRU lists.

PATCH In review David Chinner 4 participants 12 messages May 24, 2006 VFS

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Per-superblock unused 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.

My initial attempt to solve the problem using per-node LRUs
(http://marc.theaimsgroup.com/?l=linux-kernel&m=114537118504917&w=2)
fell apart under the complexity of locking required. This approach can probably be made to work in the long term, but we need a robust fix for now....

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

This approach does not change any of the locking required, so avoids the locking problems of the per-node lru implementation.

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

---
The patch has been stress tested on single and multiple filesystems, using dbench, postmark and parallel create/unlink load tests. It has also been running on the problem server since last Saturday which currently has ~11 million cached dentries, and a dentry_cache slab size of ~27 million objects.

% diffstat patches/dcache-per-sb-lru

 fs/dcache.c        |  214 +++++++++++++++++++++++++++++------------------------
 fs/super.c         |    1
 include/linux/fs.h |    1
 3 files changed, 121 insertions(+), 95 deletions(-)
fs/dcache.c +119 -95
Index: 2.6.x-xfs-new/fs/dcache.c
===================================================================
@@ -62,7 +62,6 @@ static kmem_cache_t *dentry_cache; 
 static unsigned int d_hash_mask;
 static unsigned int d_hash_shift;
 static struct hlist_head *dentry_hashtable;
-static LIST_HEAD(dentry_unused);
 
 /* Statistics gathering. */
 struct dentry_stat_t dentry_stat = {
@@ -114,6 +113,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_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_stat.nr_unused++;
+}
+
+static void
+dentry_lru_del(struct dentry *dentry)
+{
+	if (!list_empty(&dentry->d_lru)) {
+		list_del(&dentry->d_lru);
+		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_stat.nr_unused--;
+	}
+}
+
 /* 
  * This is dput
  *
@@ -173,8 +204,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);
@@ -186,13 +216,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 */
@@ -268,10 +293,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;
 }
 
@@ -377,6 +399,48 @@ static inline void prune_one_dentry(stru
 	spin_lock(&dcache_lock);
 }
 
+/*
+ * Shrink the dentry LRU on æ given superblock.
+ */
+static void
+__shrink_dcache_sb(struct super_block *sb, int *count, int flags)
+{
+	struct dentry *dentry;
+	int cnt = (count == NULL) ? -1 : *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 the dentry matches the flags passed in, don't free it.
+		 * clear the flags and put it back on the LRU */
+		if (flags && (dentry->d_flags & flags)) {
+			dentry->d_flags &= ~flags;
+			dentry_lru_add(dentry);
+			spin_unlock(&dentry->d_lock);
+			continue;
+		}
+		prune_one_dentry(dentry);
+	}
+	spin_unlock(&dcache_lock);
+	if (count)
+		*count = cnt;
+}
+
 /**
  * prune_dcache - shrink the dcache
  * @count: number of entries to try and free
@@ -392,42 +456,44 @@ static inline void prune_one_dentry(stru
  
 static void prune_dcache(int count)
 {
-	spin_lock(&dcache_lock);
-	for (; count ; count--) {
-		struct dentry *dentry;
-		struct list_head *tmp;
-
-		cond_resched_lock(&dcache_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;
+		/* Found the next superblock to work on.
+		 * Move the hand forwards so that parallel
+		 * pruners will work on a different sb */
+		work_done++;
+		sb_hand = sb_entry(sb->s_list.next);
+		sb->s_count++;
+		spin_unlock(&sb_lock);
+
+		/* we don't take the s_umount lock here because
+		 * because we can be called already holding a
+		 * write lock on a superblock */
+		if (!list_empty(&sb->s_dentry_lru))
+			__shrink_dcache_sb(sb, &count, DCACHE_REFERENCED);
 
-		tmp = dentry_unused.prev;
-		if (tmp == &dentry_unused)
+		spin_lock(&sb_lock);
+		if (__put_super_and_need_restart(sb) && count)
+			goto restart;
+		if (count <= 0)
 			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);
-			continue;
-		}
-		prune_one_dentry(dentry);
 	}
-	spin_unlock(&dcache_lock);
+	if (!work_done) {
+		/* sb_hand is stale. Start and the beginning of the
+		 * list again. */
+		sb_hand = sb_entry(super_blocks.next);
+		goto restart;
+	}
+	spin_unlock(&sb_lock);
 }
 
 /*
@@ -454,41 +520,7 @@ static void prune_dcache(int count)
 
 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_del(tmp);
-		list_add(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);
-		goto repeat;
-	}
-	spin_unlock(&dcache_lock);
+	__shrink_dcache_sb(sb, NULL, 0);
 }
 
 /*
@@ -572,17 +604,13 @@ 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(&dentry->d_lru, dentry_unused.prev);
-			dentry_stat.nr_unused++;
+			dentry_lru_add_tail(dentry);
 			found++;
 		}
 
@@ -657,18 +685,14 @@ void shrink_dcache_anon(struct hlist_hea
 		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++;
 			}
 		}
@@ -1019,7 +1043,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 +1 -0
Index: 2.6.x-xfs-new/include/linux/fs.h
===================================================================
@@ -831,6 +831,7 @@ 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 */
 
 	struct block_device	*s_bdev;
 	struct list_head	s_instances;
fs/super.c +1 -0
Index: 2.6.x-xfs-new/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);

-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#1 lore raw
Quoted 33 lines · On Wed, 24 May 2006 11:24:12 +1000 David Chinner wrote:

Index: 2.6.x-xfs-new/fs/dcache.c
===================================================================

fs/dcache.c +25 -0
@@ -114,6 +113,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_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_stat.nr_unused++;
+}
+
+static void
+dentry_lru_del(struct dentry *dentry)
+{
+	if (!list_empty(&dentry->d_lru)) {
+		list_del(&dentry->d_lru);
+		dentry_stat.nr_unused--;
+	}
+}
+
+static void
+dentry_lru_del_init(struct dentry *dentry)

fs/dcache.c static void dentry_iput(struct dentry * · line 150

Quoted 10 lines
fs/dcache.c +7 -0
+{
+	if (likely(!list_empty(&dentry->d_lru))) {
+		list_del_init(&dentry->d_lru);
+		dentry_stat.nr_unused--;
+	}
+}
+
 /* 
  * This is dput
  *

Please use regular kernel coding style for functions:
don't put qualifiers and names on separate lines.

fs/dcache.c static inline void prune_one_dentry(stru · line 403

Quoted 6 lines
fs/dcache.c +2 -0
@@ -377,6 +399,48 @@ static inline void prune_one_dentry(stru
 	spin_lock(&dcache_lock);
 }
 
+/*
+ * Shrink the dentry LRU on æ given superblock.

on ? given superblock ?

fs/dcache.c static inline void prune_one_dentry(stru · line 407

Quoted 4 lines
fs/dcache.c +4 -0
+ */
+static void
+__shrink_dcache_sb(struct super_block *sb, int *count, int flags)
+{

---
~Randy
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#2 lore raw
Quoted 16 lines · Randy.Dunlap

fs/dcache.c static void dentry_iput(struct dentry * · line 150

Quoted 12 lines · On Wed, 24 May 2006 11:24:12 +1000 David Chinner wrote:
fs/dcache.c +9 -0
+static void
+dentry_lru_del_init(struct dentry *dentry)
+{
+	if (likely(!list_empty(&dentry->d_lru))) {
+		list_del_init(&dentry->d_lru);
+		dentry_stat.nr_unused--;
+	}
+}
+
 /* 
  * This is dput
  *

Please use regular kernel coding style for functions:
don't put qualifiers and names on separate lines.

Oops - I'm too used to the XFS coding style. Fixed.

Quoted 8 lines

fs/dcache.c static inline void prune_one_dentry(stru · line 403

Quoted 6 lines
fs/dcache.c +2 -0
@@ -377,6 +399,48 @@ static inline void prune_one_dentry(stru
 	spin_lock(&dcache_lock);
 }
 
+/*
+ * Shrink the dentry LRU on æ given superblock.

on ? given superblock ?

"a". Fixed.

I'll wait for other comments before sending out an updated patch.

Cheers,

Dave.

Signature · 7 lines
Dave Chinner
R&D Software Enginner
SGI Australian Software Group
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
#3 lore raw
In reply to David Chinner
Quoted 5 lines · David Chinner

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.

how does a per SB list deal with umounts that occur frequently? I suppose it means destroying just your list...

Quoted 2 lines

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

how fair is this in the light of a non-equal sizes? say you have a 4Gb fs and a 1Tb list. Will your approach result in trying to prune 1000 from the 4Gb, then 1000 from the 1Tb, then 1000 from the 4Gb etc ? while that is fair in absolute terms, in relative terms it's highly not fair to the small filesystem....
(I'm not sure there is ONE right answer here, well maybe by scaling the count to the per fs count rather than to the total...)

this makes me wonder btw if we can do a per superblock slab for these dentries, that may decrease fragmentation of slabs in combination with your patch....

#4 lore raw
Quoted 11 lines · Arjan van de Ven
Quoted 5 lines · David Chinner

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.

how does a per SB list deal with umounts that occur frequently? I suppose it means destroying just your list...

shrink_dcache_sb no longer walks the single unsed dentry list with the dcache lock held. With many millions of dentries on the unused list, this meant that all dentry operations come to a halt while one process executes shrink_dcache_sb().

With a per-sb lru, we no longer have to walk a global list to find all the dentries that belong to the superblock we are unmounting. Hence we only hold the dcache_lock for as long as it takes to pull a dentry of the list and free it.

Quoted 4 lines
Quoted 2 lines

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

how fair is this in the light of a non-equal sizes?

It's not. If you read the thread I pointed at, you'll note that I commented at the time this method introduces "interesting" reclaim fairness issues, and this is one of the reasons I didn't implement this method straight away.

Quoted 5 lines

say you have a 4Gb
fs and a 1Tb list. Will your approach result in trying to prune 1000 from the 4Gb, then 1000 from the 1Tb, then 1000 from the 4Gb etc ? while that is fair in absolute terms, in relative terms it's highly not fair to the small filesystem....

Yup, that is what the current code I've written will do. I just wanted someting that worked over all superblocks to begin with. It's not very smart, but improving it can be done incrementally.

Quoted 2 lines

(I'm not sure there is ONE right answer here, well maybe by scaling the count to the per fs count rather than to the total...)

Agreed - scaling is probably going to result in the fairest reclaim, but I prefered to focus on getting the mechanism working properly and testing that before considering optimising the reclaim algorithm.

Also, I'd prefer to address deficiencies as they arise, rather than make optimisations based on assumptions that may be incorrect....

Quoted 3 lines

this makes me wonder btw if we can do a per superblock slab for these dentries, that may decrease fragmentation of slabs in combination with your patch....

That doesn't prevent slab fragmentation per filesystem. And most of the fragmentation problems I see are in the inode caches so at best this would be a bandaid rather than a real solution to the fundamental problems....

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
R&D Software Enginner
SGI Australian Software Group
#5 lore raw
Quoted 18 lines · David Chinner
Quoted 11 lines · Arjan van de Ven
Quoted 5 lines · David Chinner

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.

how does a per SB list deal with umounts that occur frequently? I suppose it means destroying just your list...

shrink_dcache_sb no longer walks the single unsed dentry list with the dcache lock held. With many millions of dentries on the unused list, this meant that all dentry operations come to a halt while one process executes shrink_dcache_sb().

Quoted 4 lines

With a per-sb lru, we no longer have to walk a global list to find all the dentries that belong to the superblock we are unmounting. Hence we only hold the dcache_lock for as long as it takes to pull a dentry of the list and free it.

list_splice is great for that. I can for sure see this benefit

Quoted 3 lines

Yup, that is what the current code I've written will do. I just wanted someting that worked over all superblocks to begin with. It's not very smart, but improving it can be done incrementally.

I think that if you say A you should say B, I mean, if you make the list per SB you probably just should do the step and make at least the counter per SB as well. That will also save in cacheline bounces I suppose... but more importantly you keep the counters next to the list. Which you'll also need to do any kind of scaling I suppose later on, so might as well keep the stats already.

Quoted 8 lines
Quoted 3 lines

this makes me wonder btw if we can do a per superblock slab for these dentries, that may decrease fragmentation of slabs in combination with your patch....

That doesn't prevent slab fragmentation per filesystem. And most of the fragmentation problems I see are in the inode caches so at best this would be a bandaid rather than a real solution to the fundamental problems....

well what it would do is make sure an unmount causes a lot of free pages, not just fragmented slabs.

Also it will give some more locality to group related dentries together, so pinning wise it will help some.. but yeah at this point this is just hand holding. I'm just sort of wondering how much stuff can be made per SB.. if we go this way with the list, maybe just more can follow...

#6 lore raw
Quoted 9 lines · Arjan van de Ven
Quoted 3 lines · David Chinner

Yup, that is what the current code I've written will do. I just wanted someting that worked over all superblocks to begin with. It's not very smart, but improving it can be done incrementally.

I think that if you say A you should say B, I mean, if you make the list per SB you probably just should do the step and make at least the counter per SB as well. That will also save in cacheline bounces I suppose... but more importantly you keep the counters next to the list.

But it doesn't remove the need for the global counter. The dcache_lock is far more heavily contended so the counter cacheline bouncing is lost in the noise here. No to mention the counter can only be updated while holding the dcache_lock. Hence at this point, adding per-sb counters is pure overhead unless the reclaim method is made to use them.

Quoted 2 lines

Which you'll also need to do any kind of scaling I suppose later on, so might as well keep the stats already.

The per-sb list improves scalability only by reducing the maximum length of time the dcache_lock is held. Scalabilty for further parallelism (and therefore better reclaim performance) is going to require locking changes so that's when I'd expect the counters to need changing. I don't want to over-optimise before we know what we actually need to optimise...

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
R&D Software Enginner
SGI Australian Software Group
#7 lore raw
In reply to David Chinner
Quoted 26 lines · David Chinner

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.

My initial attempt to solve the problem using per-node LRUs
(http://marc.theaimsgroup.com/?l=linux-kernel&m=114537118504917&w=2)
fell apart under the complexity of locking required. This approach can probably be made to work in the long term, but we need a robust fix for now....

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

This approach does not change any of the locking required, so avoids the locking problems of the per-node lru implementation.

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

Quoted 8 lines

---
The patch has been stress tested on single and multiple filesystems, using dbench, postmark and parallel create/unlink load tests. It has also been running on the problem server since last Saturday which currently has ~11 million cached dentries, and a dentry_cache slab size of ~27 million objects.

I like the patch already :)

<snip>

Quoted 22 lines
fs/dcache.c +22 -0
+static void
+dentry_lru_add(struct dentry *dentry)
+{
+	list_add(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
+	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_stat.nr_unused++;
+}
+
+static void
+dentry_lru_del(struct dentry *dentry)
+{
+	if (!list_empty(&dentry->d_lru)) {
+		list_del(&dentry->d_lru);
+		dentry_stat.nr_unused--;
+	}
+}

fs/dcache.c static void dentry_iput(struct dentry * · line 147

Quoted 10 lines
fs/dcache.c +10 -0
+
+static void
+dentry_lru_del_init(struct dentry *dentry)
+{
+	if (likely(!list_empty(&dentry->d_lru))) {
+		list_del_init(&dentry->d_lru);
+		dentry_stat.nr_unused--;
+	}
+}
+

I wonder if there should be per-sb count of number of used dentries. This will help us while unmounting. Instead of passing count as NULL, the number of dentries in the super block can be passed. May be we should have per-dentry stats along with global statistics.

<snip>

fs/dcache.c static inline void prune_one_dentry(stru · line 409

Quoted 9 lines
fs/dcache.c +8 -0
+/*
+ * Shrink the dentry LRU on æ given superblock.
+ */
+static void
+__shrink_dcache_sb(struct super_block *sb, int *count, int flags)
+{
+	struct dentry *dentry;
+	int cnt = (count == NULL) ? -1 : *count;

This code seems hacky. Some comments please. Negative counters are generally not good IMHO. This can be avoided by per-sb dentry stats (please see the comment above)

Quoted 11 lines
fs/dcache.c +11 -0
+
+	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);
+		/*

fs/dcache.c static inline void prune_one_dentry(stru · line 430

Quoted 10 lines
fs/dcache.c +10 -0
+		 * 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 the dentry matches the flags passed in, don't free it.
+		 * clear the flags and put it back on the LRU */

The comment does not follow coding style conventions. What do these flags typically contain - DCACHE_REFERENCED? Could you clean up this comment please.

Quoted 38 lines
fs/dcache.c +25 -6
+		if (flags && (dentry->d_flags & flags)) {
+			dentry->d_flags &= ~flags;
+			dentry_lru_add(dentry);
+			spin_unlock(&dentry->d_lock);
+			continue;
+		}
+		prune_one_dentry(dentry);
+	}
+	spin_unlock(&dcache_lock);
+	if (count)
+		*count = cnt;
+}
+
 /**
  * prune_dcache - shrink the dcache
  * @count: number of entries to try and free
@@ -392,42 +456,44 @@ static inline void prune_one_dentry(stru
 
 static void prune_dcache(int count)
 {
-	spin_lock(&dcache_lock);
-	for (; count ; count--) {
-		struct dentry *dentry;
-		struct list_head *tmp;
-
-		cond_resched_lock(&dcache_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;
+		/* Found the next superblock to work on.

fs/dcache.c static inline void prune_one_dentry(stru · line 480

Quoted 10 lines
fs/dcache.c +10 -0
+		 * Move the hand forwards so that parallel
+		 * pruners will work on a different sb */
+		work_done++;
+		sb_hand = sb_entry(sb->s_list.next);
+		sb->s_count++;
+		spin_unlock(&sb_lock);
+
+		/* we don't take the s_umount lock here because
+		 * because we can be called already holding a
+		 * write lock on a superblock */

You can use trylock. Please see the patches in -mm to fix the umount race.

fs/dcache.c static inline void prune_one_dentry(stru · line 486

Quoted 8 lines
fs/dcache.c +5 -2
+		if (!list_empty(&sb->s_dentry_lru))
+			__shrink_dcache_sb(sb, &count, DCACHE_REFERENCED);
 
-		tmp = dentry_unused.prev;
-		if (tmp == &dentry_unused)
+		spin_lock(&sb_lock);
+		if (__put_super_and_need_restart(sb) && count)
+			goto restart;

Comment please.

Quoted 21 lines
fs/dcache.c +1 -19
+		if (count <= 0)
 			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);

fs/dcache.c static inline void prune_one_dentry(stru · line 492

Quoted 10 lines
fs/dcache.c +3 -6
- 			dentry_stat.nr_unused++;
- 			spin_unlock(&dentry->d_lock);
-			continue;
-		}
-		prune_one_dentry(dentry);
 	}
-	spin_unlock(&dcache_lock);
+	if (!work_done) {
+		/* sb_hand is stale. Start and the beginning of the
+		 * list again. */

Please fix the comment style

Quoted 59 lines
fs/dcache.c +6 -39
+		sb_hand = sb_entry(super_blocks.next);
+		goto restart;
+	}
+	spin_unlock(&sb_lock);
 }
 
 /*
@@ -454,41 +520,7 @@ static void prune_dcache(int count)
 
 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_del(tmp);
-		list_add(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);
-		goto repeat;
-	}
-	spin_unlock(&dcache_lock);
+	__shrink_dcache_sb(sb, NULL, 0);
 }
 
 /*
@@ -572,17 +604,13 @@ 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);

fs/dcache.c resume: · line 615

Quoted 10 lines
fs/dcache.c +1 -2
 		/* 
 		 * move only zero ref count dentries to the end 
 		 * of the unused list for prune_dcache
 		 */
 		if (!atomic_read(&dentry->d_count)) {
-			list_add(&dentry->d_lru, dentry_unused.prev);
-			dentry_stat.nr_unused++;
+			dentry_lru_add_tail(dentry);
 			found++;
 		}

This should not be required with per super-block dentries. The only reason, I think we moved dentries to the tail is to club all entries from the sb together (to free them all at once).

Quoted 12 lines
fs/dcache.c +1 -4
@@ -657,18 +685,14 @@ void shrink_dcache_anon(struct hlist_hea
 		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);
 			/* 

fs/dcache.c void shrink_dcache_anon(struct hlist_hea · line 698

Quoted 10 lines
fs/dcache.c +1 -2
 			 * 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++;
 			}
 		}

This might still be required. Do you want to split out the anonymous dcache entries as well? I am not sure what their superblock points to.

Balbir Singh,
Linux Technology Center,
IBM Software Labs
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#8 lore raw
Quoted 16 lines · Balbir Singh

fs/dcache.c static void dentry_iput(struct dentry * · line 147

Quoted 11 lines · David Chinner
fs/dcache.c +11 -0
+}
+
+static void
+dentry_lru_del_init(struct dentry *dentry)
+{
+	if (likely(!list_empty(&dentry->d_lru))) {
+		list_del_init(&dentry->d_lru);
+		dentry_stat.nr_unused--;
+	}
+}
+

I wonder if there should be per-sb count of number of used dentries. This will help us while unmounting. Instead of passing count as NULL, the number of dentries in the super block can be passed.

Possibly.

Quoted 2 lines

May be we should have
per-dentry stats along with global statistics.

per-sb, you mean? ;)

Quoted 4 lines

<snip>

Quoted 1 line
Quoted 12 lines

fs/dcache.c static inline void prune_one_dentry(stru · line 409

Quoted 8 lines
fs/dcache.c +8 -0
+/*
+ * Shrink the dentry LRU on æ given superblock.
+ */
+static void
+__shrink_dcache_sb(struct super_block *sb, int *count, int flags)
+{
+	struct dentry *dentry;
+	int cnt = (count == NULL) ? -1 : *count;

This code seems hacky. Some comments please. Negative counters are generally not good IMHO. This can be avoided by per-sb dentry stats (please see the comment above)

I'll fix that up...

Quoted 17 lines
Quoted 17 lines
fs/dcache.c +17 -0
+
+	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);
Quoted 8 lines

fs/dcache.c static inline void prune_one_dentry(stru · line 430

Quoted 4 lines
fs/dcache.c +4 -0
+			continue;
+		}
+		/* If the dentry matches the flags passed in, don't free it.
+		 * clear the flags and put it back on the LRU */

The comment does not follow coding style conventions. What do these flags typically contain - DCACHE_REFERENCED? Could you clean up this comment please.

DCACHE_REFERENCED is the only one at the moment. I'll make that more obvious.

Quoted 43 lines
Quoted 43 lines
fs/dcache.c +30 -6
+		if (flags && (dentry->d_flags & flags)) {
+			dentry->d_flags &= ~flags;
+			dentry_lru_add(dentry);
+			spin_unlock(&dentry->d_lock);
+			continue;
+		}
+		prune_one_dentry(dentry);
+	}
+	spin_unlock(&dcache_lock);
+	if (count)
+		*count = cnt;
+}
+
 /**
  * prune_dcache - shrink the dcache
  * @count: number of entries to try and free
@@ -392,42 +456,44 @@ static inline void prune_one_dentry(stru
 
 static void prune_dcache(int count)
 {
-	spin_lock(&dcache_lock);
-	for (; count ; count--) {
-		struct dentry *dentry;
-		struct list_head *tmp;
-
-		cond_resched_lock(&dcache_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;
+		/* Found the next superblock to work on.
+		 * Move the hand forwards so that parallel
+		 * pruners will work on a different sb */
+		work_done++;
+		sb_hand = sb_entry(sb->s_list.next);
+		sb->s_count++;
Quoted 8 lines

fs/dcache.c static inline void prune_one_dentry(stru · line 480

Quoted 5 lines
fs/dcache.c +5 -0
+		spin_unlock(&sb_lock);
+
+		/* we don't take the s_umount lock here because
+		 * because we can be called already holding a
+		 * write lock on a superblock */

You can use trylock. Please see the patches in -mm to fix the umount race.

I'm not sure what unmount race you are talking about.

AFAICT, there is no race here - we've got a reference on the superblock so it can't go away and the lru list is protected by the dcache_lock, so there's nothing else we can race with. However, we can deadlock by taking the s_umount lock here. So why even bother to try to take the lock when we don't actually need it?

Quoted 10 lines

fs/dcache.c static inline void prune_one_dentry(stru · line 486

Quoted 8 lines
fs/dcache.c +5 -2
+		if (!list_empty(&sb->s_dentry_lru))
+			__shrink_dcache_sb(sb, &count, DCACHE_REFERENCED);
 
-		tmp = dentry_unused.prev;
-		if (tmp == &dentry_unused)
+		spin_lock(&sb_lock);
+		if (__put_super_and_need_restart(sb) && count)
+			goto restart;

Comment please.

I'm not sure what a comment needs to explain that the code doesn't. Which bit do you think needs commenting?

Quoted 4 lines

fs/dcache.c static inline void prune_one_dentry(stru · line 492

Quoted 4 lines
fs/dcache.c +3 -1
-	spin_unlock(&dcache_lock);
+	if (!work_done) {
+		/* sb_hand is stale. Start and the beginning of the
+		 * list again. */

*nod*

Quoted 61 lines
Quoted 61 lines
fs/dcache.c +2 -40
 }
 
 /*
@@ -454,41 +520,7 @@ static void prune_dcache(int count)
 
 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_del(tmp);
-		list_add(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);
-		goto repeat;
-	}
-	spin_unlock(&dcache_lock);
+	__shrink_dcache_sb(sb, NULL, 0);
 }
 
 /*
@@ -572,17 +604,13 @@ 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(&dentry->d_lru, dentry_unused.prev);
Quoted 8 lines

fs/dcache.c resume: · line 615

Quoted 4 lines
fs/dcache.c +1 -1
-			dentry_stat.nr_unused++;
+			dentry_lru_add_tail(dentry);
 			found++;
 		}

This should not be required with per super-block dentries. The only reason, I think we moved dentries to the tail is to club all entries from the sb together (to free them all at once).

I think we still need to do that. We get called in contexts that aren't related to unmounting, so we want these dentries to be the first to be reclaimed from that superblock when we next call prune_dcache().

Quoted 9 lines
Quoted 9 lines
fs/dcache.c +0 -4
@@ -657,18 +685,14 @@ void shrink_dcache_anon(struct hlist_hea
 		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);
-			}
 
Quoted 15 lines

fs/dcache.c void shrink_dcache_anon(struct hlist_hea · line 698

Quoted 12 lines
fs/dcache.c +2 -2
+			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++;
 			}
 		}

This might still be required. Do you want to split out the anonymous dcache entries as well? I am not sure what their superblock points to.

No. Right now I just want to fix the problem that has been reported with shrink_dcache_sb().

Quoted 7 lines

Balbir Singh,
Linux Technology Center,
IBM Software Labs

Signature · 7 lines
Dave Chinner
R&D Software Enginner
SGI Australian Software Group
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
#9 lore raw
Quoted 2 lines

per-sb, you mean? ;)

Yes.

Quoted 11 lines
Quoted 3 lines

You can use trylock. Please see the patches in -mm to fix the umount race.

I'm not sure what unmount race you are talking about.

AFAICT, there is no race here - we've got a reference on the superblock so it can't go away and the lru list is protected by the dcache_lock, so there's nothing else we can race with. However, we can deadlock by taking the s_umount lock here. So why even bother to try to take the lock when we don't actually need it?

Please read the thread at http://lkml.org/lkml/2006/4/2/101.

Quoted 8 lines
Quoted 5 lines

Review

Quoted 3 lines
(quoted diff) +2 -0
+		if (__put_super_and_need_restart(sb) && count)
+			goto restart;

Comment please.

I'm not sure what a comment needs to explain that the code doesn't. Which bit do you think needs commenting?

I was referring to the __put_super_and_need_restart() part.

Quoted 7 lines
Quoted 3 lines

This should not be required with per super-block dentries. The only reason, I think we moved dentries to the tail is to club all entries from the sb together (to free them all at once).

I think we still need to do that. We get called in contexts that aren't related to unmounting, so we want these dentries to be the first to be reclaimed from that superblock when we next call prune_dcache().

Is it? I quickly checked the callers of shrink_dcache_sb() and all of them seem to be mount related. shrink_dcache_parent() is another story. Am I missing something? Code reference will be particularly useful.

Quoted 3 lines

No. Right now I just want to fix the problem that has been reported with shrink_dcache_sb().

Sure.

Balbir Singh,
Linux Technology Center,
IBM Software Labs

#10 lore raw
Quoted 5 lines · Balbir Singh
Quoted 5 lines
Quoted 2 lines

You can use trylock. Please see the patches in -mm to fix the umount race.

I'm not sure what unmount race you are talking about.

Quoted 7 lines
Quoted 5 lines

AFAICT, there is no race here - we've got a reference on the superblock so it can't go away and the lru list is protected by the dcache_lock, so there's nothing else we can race with. However, we can deadlock by taking the s_umount lock here. So why even bother to try to take the lock when we don't actually need it?

Please read the thread at http://lkml.org/lkml/2006/4/2/101.

Ok, thanks for the pointer. it's a completely differnt sort of race you're talking about ;)

I'll have to look at the -mm tree and how the locking is different there before commenting further.

Quoted 9 lines
Quoted 7 lines
Quoted 4 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+		if (__put_super_and_need_restart(sb) && count)
+			goto restart;

Comment please.

I'm not sure what a comment needs to explain that the code doesn't. Which bit do you think needs commenting?

I was referring to the __put_super_and_need_restart() part.

Ok. i didn't think it necessary given it's use in several other places and the comment at the head of __put_super_and_need_restart() explain exactly what it does and when to use it. Comment added anyway.

Quoted 11 lines
Quoted 7 lines
Quoted 3 lines

This should not be required with per super-block dentries. The only reason, I think we moved dentries to the tail is to club all entries from the sb together (to free them all at once).

I think we still need to do that. We get called in contexts that aren't related to unmounting, so we want these dentries to be the first to be reclaimed from that superblock when we next call prune_dcache().

Is it? I quickly checked the callers of shrink_dcache_sb() and all of them seem to be mount related. shrink_dcache_parent() is another story. Am I missing something? Code reference will be particularly useful.

I thought you were referring to shrink_dcache_parent(). At least, I was, and the hunk of diff that your comment followed after was from select_parent(). Please correct me if I'm wrong, but I think we're agreeing that it's doing the right thing in select_parent().

The modified shrink_dcache_sb() doesn't do do any list moving at all, it simply frees all the dentries on the superblock in a single pass.....

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
R&D Software Enginner
SGI Australian Software Group
#11 lore raw
Quoted 7 lines

I thought you were referring to shrink_dcache_parent(). At least, I was, and the hunk of diff that your comment followed after was from select_parent(). Please correct me if I'm wrong, but I think we're agreeing that it's doing the right thing in select_parent().

The modified shrink_dcache_sb() doesn't do do any list moving at all, it simply frees all the dentries on the superblock in a single pass.....

I think I misread the code, I thought I was still at an older function.

Quoted 8 lines

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
R&D Software Enginner
SGI Australian Software Group
Signature · 3 lines
	Balbir Singh,
	Linux Technology Center,
	IBM Software Labs