Per-superblock unused dentry LRU lists.
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
@@ -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(struspin_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(strustatic 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_heaspin_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
@@ -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
@@ -71,6 +71,7 @@ static struct super_block *alloc_super(vINIT_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
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(struspin_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
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(struspin_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
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....
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
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_sbno 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 executesshrink_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_lockfor 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...
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
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
Signed-off-by Dave Chinner <[email protected]>---
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 adentry_cacheslab 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(strustatic 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_heaspin_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
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(strustatic 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_heaspin_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
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 thes_umountlock 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
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 thes_umountlock 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
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 fromselect_parent(). Please correct me if I'm wrong, but I think we're agreeing that it's doing the right thing inselect_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