fs/dcache: Track # of negative dentries
Subsystems (3)
v3 cover fs/dcache: Track # of negative dentries
v2->v3:
- With confirmation that the dummy array in dentry_stat structure was never a replacement of a previously used field, patch 3 is now reverted back to use one of dummy field as the negative dentry count instead of adding a new field.
v1->v2:
- Clarify what the new nr_dentry_negative per-cpu counter is tracking and open-code the increment and decrement as suggested by Dave Chinner.
- Append the new nr_dentry_negative count as the 7th element of dentry-state instead of replacing one of the dummy entries.
- Remove patch "fs/dcache: Make negative dentries easier to be reclaimed" for now as I need more time to think about what
to do with it.
- Add 2 more patches to address issues found while reviewing the dentry code.
- Add another patch to change the conditional branch of nr_dentry_negative accounting to conditional move so as to reduce the performance impact of the accounting code.
This patchset addresses 2 issues found in the dentry code and adds a new nr_dentry_negative per-cpu counter to track the total number of negative dentries in all the LRU lists.
Patch 1 fixes a bug in the accounting of nr_dentry_unused in shrink_dcache_sb().
Patch 2 removes the ____cacheline_aligned_in_smp tag from super_block LRU lists.
Patch 3 adds the new nr_dentry_negative per-cpu counter.
Patch 4 removes conditional branches in nr_dentry_negative accounting code.
Various filesystem related tests were run and no statistically significant changes in performance was observed.
Waiman Long (4):
fs/dcache: Fix incorrect nr_dentry_unused accounting in
shrink_dcache_sb()
fs: Don't need to put list_lru into its own cacheline fs/dcache: Track & report number of negative dentries fs/dcache: Eliminate branches in nr_dentry_negative accounting
Documentation/sysctl/fs.txt | 26 +++++++++++++--------- fs/dcache.c | 54 ++++++++++++++++++++++++++++++++++++++++----- include/linux/dcache.h | 7 +++--- include/linux/fs.h | 9 ++++---- 4 files changed, 74 insertions(+), 22 deletions(-)
Signature · 1 line
1.8.3.1
PATCH v3 1/4 fs/dcache: Fix incorrect nr_dentry_unused accounting in shrink_dcache_sb()
The nr_dentry_unused per-cpu counter tracks dentries in both the LRU lists and the shrink lists where the DCACHE_LRU_LIST bit is set. The shrink_dcache_sb() function moves dentries from the LRU list to a shrink list and subtracts the dentry count from nr_dentry_unused. This is incorrect as the nr_dentry_unused count Will also be decremented in shrink_dentry_list() via d_shrink_del(). To fix this double decrement, the decrement in the shrink_dcache_sb() function is taken out.
--- fs/dcache.c | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-)
fs/dcache.c +1 -5
@@ -1202,15 +1202,11 @@ static enum lru_status dentry_lru_isolate_shrink(struct list_head *item,*/ void shrink_dcache_sb (struct super_block *sb) { -long freed; -do {LIST_HEAD (dispose); - freed =list_lru_walk (&sb->s_dentry_lru, +list_lru_walk (&sb->s_dentry_lru, dentry_lru_isolate_shrink, &dispose,1024 ); - -this_cpu_sub (nr_dentry_unused, freed);shrink_dentry_list (&dispose); }while (list_lru_count (&sb->s_dentry_lru) >0 ); }
Signature · 1 line
1.8.3.1
Re: [PATCH v3 1/4] fs/dcache: Fix incorrect nr_dentry_unused accounting in shrink_dcache_sb()
Quoted 11 lines · Waiman Long
The
nr_dentry_unusedper-cpu counter tracks dentries in both the LRU lists and the shrink lists where theDCACHE_LRU_LISTbit is set. Theshrink_dcache_sb()function moves dentries from the LRU list to a shrink list and subtracts the dentry count fromnr_dentry_unused. This is incorrect as thenr_dentry_unusedcount Will also be decremented inshrink_dentry_list()viad_shrink_del(). To fix this double decrement, the decrement in theshrink_dcache_sb()function is taken out.Fixes 4e717f5c1083 ("list_lru: remove special case function list_lru_dispose_all."Signed-off-by Waiman Long <[email protected]>
Please add a stable tag for this.
Otherwise looks fine.
Signature · 2 lines
Dave Chinner [email protected]
Re: [PATCH v3 1/4] fs/dcache: Fix incorrect nr_dentry_unused accounting in shrink_dcache_sb()
Quoted 9 lines · Dave Chinner
Quoted 8 lines · Waiman Long
The
nr_dentry_unusedper-cpu counter tracks dentries in both the LRU lists and the shrink lists where theDCACHE_LRU_LISTbit is set. Theshrink_dcache_sb()function moves dentries from the LRU list to a shrink list and subtracts the dentry count fromnr_dentry_unused. This is incorrect as thenr_dentry_unusedcount Will also be decremented inshrink_dentry_list()viad_shrink_del(). To fix this double decrement, the decrement in theshrink_dcache_sb()function is taken out.
Quoted 9 lines
Quoted 3 lines
Fixes 4e717f5c1083 ("list_lru: remove special case function list_lru_dispose_all."Signed-off-by Waiman Long <[email protected]>Please add a stable tag for this.
Otherwise looks fine.
Reviewed-by Dave Chinner <[email protected]>
I will add the cc:stable tag.
Cheers,
Longman
PATCH v3 2/4 fs: Don't need to put list_lru into its own cacheline
In reply to Waiman LongThe list_lru structure is essentially just a pointer to a table of per-node LRU lists. Even if CONFIG_MEMCG_KMEM is defined, the list field is just used for LRU list registration and shrinker_id is set at initialization. Those fields won't need to be touched that often.
So there is no point to make the list_lru structures to sit in their own cachelines.
--- include/linux/fs.h | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)
include/linux/fs.h +5 -4
@@ -1443,11 +1443,12 @@ struct super_block {struct user_namespace *s_user_ns;/* -* Keep the lru lists last in the structure so they always sit on their -* own individual cachelines. +* The list_lru structure is essentially just a pointer to a table +* of per-node lru lists, each of which has its own spinlock. +* There is no need to put them into separate cachelines. */ -struct list_lru s_dentry_lru____cacheline_aligned_in_smp ; -struct list_lru s_inode_lru____cacheline_aligned_in_smp ; +struct list_lru s_dentry_lru; +struct list_lru s_inode_lru;struct rcu_head rcu;struct work_struct destroy_work;
Signature · 1 line
1.8.3.1
Re: [PATCH v3 2/4] fs: Don't need to put list_lru into its own cacheline
Quoted 9 lines · Waiman Long
The
list_lrustructure is essentially just a pointer to a table of per-node LRU lists. Even ifCONFIG_MEMCG_KMEMis defined, the list field is just used for LRU list registration andshrinker_idis set at initialization. Those fields won't need to be touched that often.So there is no point to make the
list_lrustructures to sit in their own cachelines.Signed-off-by Waiman Long <[email protected]>
Looks fine.
Signature · 2 lines
Dave Chinner [email protected]
PATCH v3 3/4 fs/dcache: Track & report number of negative dentries
In reply to Waiman LongThe current dentry number tracking code doesn't distinguish between positive & negative dentries. It just reports the total number of dentries in the LRU lists.
As excessive number of negative dentries can have an impact on system performance, it will be wise to track the number of positive and negative dentries separately.
This patch adds tracking for the total number of negative dentries in the system LRU lists and reports it in the 7th field in the /proc/sys/fs/dentry-state file. The number, however, does not include negative dentries that are in flight but not in the LRU yet as well as those in the shrinker lists.
The number of positive dentries in the LRU lists can be roughly found by subtracting the number of negative dentries from the unused count.
Matthew Wilcox had confirmed that since the introduction of the dentry_stat structure in 2.1.60, the dummy array was there, probably for future extension. They were not replacements of pre-existing fields. So no sane applications that read the value of /proc/sys/fs/dentry-state will do dummy thing if the last 2 fields of the sysctl parameter are not zero. IOW, it will be safe to use one of the dummy array entry for negative dentry count.
--- Documentation/sysctl/fs.txt | 26 ++++++++++++++++---------- fs/dcache.c | 31 +++++++++++++++++++++++++++++++ include/linux/dcache.h | 7 ++++--- 3 files changed, 51 insertions(+), 13 deletions(-)
Documentation/sysctl/fs.txt +16 -10
@@ -56,26 +56,32 @@ of any kernel data structures. dentry-state: -From linux/fs/dentry.c: +From linux/include/linux/dcache.h: -------------------------------------------------------------- -struct { +struct dentry_stat_t dentry_stat { int nr_dentry; int nr_unused; int age_limit; /* age in seconds */ int want_pages; /* pages requested by system */ - int dummy[2]; -} dentry_stat = {0, 0, 45, 0,}; --------------------------------------------------------------- - -Dentries are dynamically allocated and deallocated, and -nr_dentry seems to be 0 all the time. Hence it's safe to -assume that only nr_unused, age_limit and want_pages are -used. Nr_unused seems to be exactly what its name says. + int nr_negative; /* # of unused negative dentries */ + int dummy; /* Reserved */ +}; +-------------------------------------------------------------- + +Dentries are dynamically allocated and deallocated. + +nr_dentry shows the total number of dentries allocated (active ++ unused). nr_unused shows the number of dentries that are not +actively used, but are saved in the LRU list for future reuse. + Age_limit is the age in seconds after which dcache entries can be reclaimed when memory is short and want_pages is nonzero when shrink_dcache_pages() has been called and the dcache isn't pruned yet. +nr_negative shows the number of unused dentries that are also +negative dentries which do not mapped to actual files. + ============================================================== dquot-max & dquot-nr:
fs/dcache.c +31 -0
@@ -119,6 +119,7 @@ struct dentry_stat_t dentry_stat = { static DEFINE_PER_CPU(long, nr_dentry); static DEFINE_PER_CPU(long, nr_dentry_unused); +static DEFINE_PER_CPU(long, nr_dentry_negative);#if defined(CONFIG_SYSCTL ) && defined(CONFIG_PROC_FS )
@@ -152,11 +153,22 @@ static long get_nr_dentry_unused(void) return sum < 0 ? 0 : sum; } +static long get_nr_dentry_negative (void ) +{ +int i; +long sum =0 ; + +for_each_possible_cpu (i) + sum +=per_cpu (nr_dentry_negative, i); +return sum <0 ?0 : sum; +} +int proc_nr_dentry (struct ctl_table *table,int write,void __user *buffer,size_t *lenp,loff_t *ppos) { dentry_stat.nr_dentry =get_nr_dentry (); dentry_stat.nr_unused =get_nr_dentry_unused (); + dentry_stat.nr_negative =get_nr_dentry_negative ();return proc_doulongvec_minmax (table, write, buffer, lenp, ppos); }#endif
@@ -331,6 +343,8 @@ static inline void __d_clear_type_and_inode(struct dentry *dentry) flags &= ~(DCACHE_ENTRY_TYPE |DCACHE_FALLTHRU );WRITE_ONCE (dentry->d_flags, flags); dentry->d_inode =NULL ; +if (dentry->d_flags &DCACHE_LRU_LIST ) +this_cpu_inc (nr_dentry_negative); }static void dentry_free (struct dentry *dentry)
@@ -385,6 +399,10 @@ static void dentry_unlink_inode(struct dentry * dentry)* The per-cpu "nr_dentry_unused" counters are updated with * the DCACHE_LRU_LIST bit. * +* The per-cpu "nr_dentry_negative" counters are only updated +* when deleted or added to the per-superblock LRU list, not +* on the shrink list. +* * These helper functions make sure we always follow the * rules. d_lock must be held by the caller. */
@@ -394,6 +412,8 @@ static void d_lru_add(struct dentry *dentry)D_FLAG_VERIFY (dentry,0 ); dentry->d_flags |=DCACHE_LRU_LIST ;this_cpu_inc (nr_dentry_unused); +if (d_is_negative (dentry)) +this_cpu_inc (nr_dentry_negative);WARN_ON_ONCE (!list_lru_add (&dentry->d_sb->s_dentry_lru, &dentry->d_lru)); }
@@ -402,6 +422,8 @@ static void d_lru_del(struct dentry *dentry)D_FLAG_VERIFY (dentry,DCACHE_LRU_LIST ); dentry->d_flags &= ~DCACHE_LRU_LIST ;this_cpu_dec (nr_dentry_unused); +if (d_is_negative (dentry)) +this_cpu_dec (nr_dentry_negative);WARN_ON_ONCE (!list_lru_del (&dentry->d_sb->s_dentry_lru, &dentry->d_lru)); }
@@ -432,6 +454,8 @@ static void d_lru_isolate(struct list_lru_one *lru, struct dentry *dentry)D_FLAG_VERIFY (dentry,DCACHE_LRU_LIST ); dentry->d_flags &= ~DCACHE_LRU_LIST ;this_cpu_dec (nr_dentry_unused); +if (d_is_negative (dentry)) +this_cpu_dec (nr_dentry_negative);list_lru_isolate (lru, &dentry->d_lru); }
@@ -440,6 +464,8 @@ static void d_lru_shrink_move(struct list_lru_one *lru, struct dentry *dentry, {D_FLAG_VERIFY (dentry,DCACHE_LRU_LIST ); dentry->d_flags |=DCACHE_SHRINK_LIST ; +if (d_is_negative (dentry)) +this_cpu_dec (nr_dentry_negative);list_lru_isolate_move (lru, &dentry->d_lru, list); }
@@ -1836,6 +1862,11 @@ static void __d_instantiate(struct dentry *dentry, struct inode *inode)WARN_ON (d_in_lookup (dentry));spin_lock (&dentry->d_lock); +/* +* Decrement negative dentry count if it was in the LRU list. +*/ +if (dentry->d_flags &DCACHE_LRU_LIST ) +this_cpu_dec (nr_dentry_negative);hlist_add_head (&dentry->d_u.d_alias, &inode->i_dentry);raw_write_seqcount_begin (&dentry->d_seq);__d_set_inode_and_type (dentry, inode, add_flags);
include/linux/dcache.h +4 -3
@@ -62,9 +62,10 @@ struct qstr {struct dentry_stat_t {long nr_dentry;long nr_unused; -long age_limit;/* age in seconds */ -long want_pages;/* pages requested by system */ -long dummy[2 ]; +long age_limit;/* age in seconds */ +long want_pages;/* pages requested by system */ +long nr_negative;/* # of unused negative dentries */ +long dummy;/* Reserved */ };extern struct dentry_stat_t dentry_stat;
Signature · 1 line
1.8.3.1
Re: [PATCH v3 3/4] fs/dcache: Track & report number of negative dentries
Quoted 10 lines · Waiman Long
The current dentry number tracking code doesn't distinguish between positive & negative dentries. It just reports the total number of dentries in the LRU lists.
As excessive number of negative dentries can have an impact on system performance, it will be wise to track the number of positive and negative dentries separately.
This patch adds tracking for the total number of negative dentries in the system LRU lists and reports it in the 7th field in the
Not the 7th field anymore.
Quoted 16 lines
/proc/sys/fs/dentry-statefile. The number, however, does not include negative dentries that are in flight but not in the LRU yet as well as those in the shrinker lists.The number of positive dentries in the LRU lists can be roughly found by subtracting the number of negative dentries from the unused count.
Matthew Wilcox had confirmed that since the introduction of the
dentry_statstructure in 2.1.60, the dummy array was there, probably for future extension. They were not replacements of pre-existing fields. So no sane applications that read the value of/proc/sys/fs/dentry-statewill do dummy thing if the last 2 fields of the sysctl parameter are not zero. IOW, it will be safe to use one of the dummy array entry for negative dentry count.Signed-off-by Waiman Long <[email protected]>
....
Quoted 23 lines
--- Documentation/sysctl/fs.txt | 26 ++++++++++++++++---------- fs/dcache.c | 31 +++++++++++++++++++++++++++++++ include/linux/dcache.h | 7 ++++--- 3 files changed, 51 insertions(+), 13 deletions(-)Documentation/sysctl/fs.txt +2
-2@@ -56,26 +56,32 @@ of any kernel data structures. dentry-state: -From linux/fs/dentry.c: +From linux/include/linux/dcache.h: -------------------------------------------------------------- -struct { +struct dentry_stat_t dentry_stat { int nr_dentry; int nr_unused; int age_limit; /* age in seconds */ int want_pages; /* pages requested by system */
Documentation/sysctl/fs.txt of any kernel data structures. · line 67
Quoted 10 lines
Documentation/sysctl/fs.txt +2
-8- int dummy[2]; -} dentry_stat = {0, 0, 45, 0,}; --------------------------------------------------------------- - -Dentries are dynamically allocated and deallocated, and -nr_dentry seems to be 0 all the time. Hence it's safe to -assume that only nr_unused, age_limit and want_pages are -used. Nr_unused seems to be exactly what its name says. + int nr_negative; /* # of unused negative dentries */ + int dummy; /* Reserved */
/* reserved for future use */
....
Quoted 10 lines
Documentation/sysctl/fs.txt +2
-0@@ -331,6 +343,8 @@ static inline void __d_clear_type_and_inode(struct dentry *dentry) flags &= ~(DCACHE_ENTRY_TYPE | DCACHE_FALLTHRU); WRITE_ONCE(dentry->d_flags, flags); dentry->d_inode = NULL; + if (dentry->d_flags & DCACHE_LRU_LIST) + this_cpu_inc(nr_dentry_negative); } static void dentry_free(struct dentry *dentry)
Documentation/sysctl/fs.txt static void dentry_unlink_inode(struct dentry * dentry) · line 404
Quoted 6 lines
Documentation/sysctl/fs.txt +3
-0@@ -385,6 +399,10 @@ static void dentry_unlink_inode(struct dentry * dentry) * The per-cpu "nr_dentry_unused" counters are updated with * the DCACHE_LRU_LIST bit. * + * The per-cpu "nr_dentry_negative" counters are only updated + * when deleted or added to the per-superblock LRU list, not + * on the shrink list.
This tells us what the code is doing, but it doesn't explain why a different accounting method to nr_dentry_unused was chosen. What constraints require the accounting to be done this way rather than just mirror the unused dentry accounting?
Quoted 17 lines
Documentation/sysctl/fs.txt +5
-0@@ -1836,6 +1862,11 @@ static void __d_instantiate(struct dentry *dentry, struct inode *inode) WARN_ON(d_in_lookup(dentry)); spin_lock(&dentry->d_lock); + /* + * Decrement negative dentry count if it was in the LRU list. + */ + if (dentry->d_flags & DCACHE_LRU_LIST) + this_cpu_dec(nr_dentry_negative); hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry); raw_write_seqcount_begin(&dentry->d_seq); __d_set_inode_and_type(dentry, inode, add_flags);include/linux/dcache.h +0
-0
include/linux/dcache.h struct qstr { · line 68
Quoted 10 lines
include/linux/dcache.h +4
-3@@ -62,9 +62,10 @@ struct qstr {struct dentry_stat_t {long nr_dentry;long nr_unused; -long age_limit;/* age in seconds */ -long want_pages;/* pages requested by system */ -long dummy[2 ]; +long age_limit;/* age in seconds */ +long want_pages;/* pages requested by system */ +long nr_negative;/* # of unused negative dentries */ +long dummy;/* Reserved */
/* reserved for future use */
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [PATCH v3 3/4] fs/dcache: Track & report number of negative dentries
Quoted 5 lines · Dave Chinner
Quoted 4 lines · Waiman Long
The current dentry number tracking code doesn't distinguish between positive & negative dentries. It just reports the total number of dentries in the LRU lists.
Quoted 8 lines
Quoted 6 lines
As excessive number of negative dentries can have an impact on system performance, it will be wise to track the number of positive and negative dentries separately.
This patch adds tracking for the total number of negative dentries in the system LRU lists and reports it in the 7th field in the
Not the 7th field anymore.
You are right. It is a left-behind from v2.
Quoted 43 lines
Quoted 16 lines
/proc/sys/fs/dentry-statefile. The number, however, does not include negative dentries that are in flight but not in the LRU yet as well as those in the shrinker lists.The number of positive dentries in the LRU lists can be roughly found by subtracting the number of negative dentries from the unused count.
Matthew Wilcox had confirmed that since the introduction of the
dentry_statstructure in 2.1.60, the dummy array was there, probably for future extension. They were not replacements of pre-existing fields. So no sane applications that read the value of/proc/sys/fs/dentry-statewill do dummy thing if the last 2 fields of the sysctl parameter are not zero. IOW, it will be safe to use one of the dummy array entry for negative dentry count.Signed-off-by Waiman Long <[email protected]>....
Quoted 26 lines
--- Documentation/sysctl/fs.txt | 26 ++++++++++++++++---------- fs/dcache.c | 31 +++++++++++++++++++++++++++++++ include/linux/dcache.h | 7 ++++--- 3 files changed, 51 insertions(+), 13 deletions(-)Documentation/sysctl/fs.txt +2
-5@@ -56,26 +56,32 @@ of any kernel data structures. dentry-state: -From linux/fs/dentry.c: +From linux/include/linux/dcache.h: -------------------------------------------------------------- -struct { +struct dentry_stat_t dentry_stat { int nr_dentry; int nr_unused; int age_limit; /* age in seconds */ int want_pages; /* pages requested by system */ - int dummy[2]; -} dentry_stat = {0, 0, 45, 0,}; ---------------------------------------------------------------
Quoted 8 lines
Documentation/sysctl/fs.txt of any kernel data structures. · line 67
Quoted 7 lines
Documentation/sysctl/fs.txt +2
-5- -Dentries are dynamically allocated and deallocated, and -nr_dentry seems to be 0 all the time. Hence it's safe to -assume that only nr_unused, age_limit and want_pages are -used. Nr_unused seems to be exactly what its name says. + int nr_negative; /* # of unused negative dentries */ + int dummy; /* Reserved *//* reserved for future use */
Will change that.
Quoted 9 lines
....
Quoted 8 lines
Documentation/sysctl/fs.txt +2
-0@@ -331,6 +343,8 @@ static inline void __d_clear_type_and_inode(struct dentry *dentry) flags &= ~(DCACHE_ENTRY_TYPE | DCACHE_FALLTHRU); WRITE_ONCE(dentry->d_flags, flags); dentry->d_inode = NULL; + if (dentry->d_flags & DCACHE_LRU_LIST) + this_cpu_inc(nr_dentry_negative); }
Quoted 12 lines
Documentation/sysctl/fs.txt static void dentry_unlink_inode(struct dentry * dentry) · line 404
Quoted 8 lines
Documentation/sysctl/fs.txt +3
-0static void dentry_free(struct dentry *dentry)@@ -385,6 +399,10 @@ static void dentry_unlink_inode(struct dentry * dentry) * The per-cpu "nr_dentry_unused" counters are updated with * the DCACHE_LRU_LIST bit. * + * The per-cpu "nr_dentry_negative" counters are only updated + * when deleted or added to the per-superblock LRU list, not + * on the shrink list.This tells us what the code is doing, but it doesn't explain why a different accounting method to
nr_dentry_unusedwas chosen. What constraints require the accounting to be done this way rather than just mirror the unused dentry accounting?
It is done to minimize the number of percpu count update as much as possible. There is one code path where the unused count is decremented when removing from the lru and then increment later on when added to the shrink list. So we are doing double inc/dec in this case.
Besides, those in the shrink list are on the way out and its number isn't really that important. I will elaborate a bit more on the rationale behind this decision in the patch.
Quoted 20 lines
Quoted 20 lines
Documentation/sysctl/fs.txt +5
-0@@ -1836,6 +1862,11 @@ static void __d_instantiate(struct dentry *dentry, struct inode *inode) WARN_ON(d_in_lookup(dentry)); spin_lock(&dentry->d_lock); + /* + * Decrement negative dentry count if it was in the LRU list. + */ + if (dentry->d_flags & DCACHE_LRU_LIST) + this_cpu_dec(nr_dentry_negative); hlist_add_head(&dentry->d_u.d_alias, &inode->i_dentry); raw_write_seqcount_begin(&dentry->d_seq); __d_set_inode_and_type(dentry, inode, add_flags);include/linux/dcache.h +0
-0@@ -62,9 +62,10 @@ struct qstr {struct dentry_stat_t {long nr_dentry;long nr_unused;
Quoted 8 lines
include/linux/dcache.h struct qstr { · line 68
Quoted 7 lines
include/linux/dcache.h +4
-3-long age_limit;/* age in seconds */ -long want_pages;/* pages requested by system */ -long dummy[2 ]; +long age_limit;/* age in seconds */ +long want_pages;/* pages requested by system */ +long nr_negative;/* # of unused negative dentries */ +long dummy;/* Reserved */ /* reserved for future use */
Will do.
Cheers,
Longman
PATCH v3 4/4 fs/dcache: Eliminate branches in nr_dentry_negative accounting
In reply to Waiman LongBecause the accounting of nr_dentry_negative depends on whether a dentry is a negative one or not, branch instructions are introduced to handle the accounting conditionally. That may potentially slow down the task by a noticeable amount if that introduces sizeable amount of additional branch mispredictions.
To avoid that, the accounting code is now modified to use conditional move instructions instead, if supported by the architecture.
--- fs/dcache.c | 41 +++++++++++++++++++++++++++++------------ 1 file changed, 29 insertions(+), 12 deletions(-)
fs/dcache.c +29 -12
@@ -171,6 +171,29 @@ int proc_nr_dentry(struct ctl_table *table, int write, void __user *buffer, dentry_stat.nr_negative =get_nr_dentry_negative (); return proc_doulongvec_minmax(table, write, buffer, lenp, ppos); } + +/* +* Increment/Decrement nr_dentry_negative if the condition is true. +* For architectures that support some kind of conditional move, compiler +* should be able generate code to inc/dec negative dentry counter +* without any branch instruction. +*/ +static inline void cond_negative_dentry_inc (bool cond) +{ +int val = !!cond; + +this_cpu_add (nr_dentry_negative, val); +} + +static inline void cond_negative_dentry_dec (bool cond) +{ +int val = !!cond; + +this_cpu_sub (nr_dentry_negative, val); +} +#else +static inline void cond_negative_dentry_inc (bool cond) { } +static inline void cond_negative_dentry_dec (bool cond) { }#endif /*
@@ -343,8 +366,7 @@ static inline void __d_clear_type_and_inode(struct dentry *dentry) flags &= ~(DCACHE_ENTRY_TYPE |DCACHE_FALLTHRU );WRITE_ONCE (dentry->d_flags, flags); dentry->d_inode =NULL ; -if (dentry->d_flags &DCACHE_LRU_LIST ) -this_cpu_inc (nr_dentry_negative); +cond_negative_dentry_inc (dentry->d_flags &DCACHE_LRU_LIST ); }static void dentry_free (struct dentry *dentry)
@@ -412,8 +434,7 @@ static void d_lru_add(struct dentry *dentry)D_FLAG_VERIFY (dentry,0 ); dentry->d_flags |=DCACHE_LRU_LIST ;this_cpu_inc (nr_dentry_unused); -if (d_is_negative (dentry)) -this_cpu_inc (nr_dentry_negative); +cond_negative_dentry_inc (d_is_negative (dentry));WARN_ON_ONCE (!list_lru_add (&dentry->d_sb->s_dentry_lru, &dentry->d_lru)); }
@@ -422,8 +443,7 @@ static void d_lru_del(struct dentry *dentry)D_FLAG_VERIFY (dentry,DCACHE_LRU_LIST ); dentry->d_flags &= ~DCACHE_LRU_LIST ;this_cpu_dec (nr_dentry_unused); -if (d_is_negative (dentry)) -this_cpu_dec (nr_dentry_negative); +cond_negative_dentry_dec (d_is_negative (dentry));WARN_ON_ONCE (!list_lru_del (&dentry->d_sb->s_dentry_lru, &dentry->d_lru)); }
@@ -454,8 +474,7 @@ static void d_lru_isolate(struct list_lru_one *lru, struct dentry *dentry)D_FLAG_VERIFY (dentry,DCACHE_LRU_LIST ); dentry->d_flags &= ~DCACHE_LRU_LIST ;this_cpu_dec (nr_dentry_unused); -if (d_is_negative (dentry)) -this_cpu_dec (nr_dentry_negative); +cond_negative_dentry_dec (d_is_negative (dentry));list_lru_isolate (lru, &dentry->d_lru); }
@@ -464,8 +483,7 @@ static void d_lru_shrink_move(struct list_lru_one *lru, struct dentry *dentry, {D_FLAG_VERIFY (dentry,DCACHE_LRU_LIST ); dentry->d_flags |=DCACHE_SHRINK_LIST ; -if (d_is_negative (dentry)) -this_cpu_dec (nr_dentry_negative); +cond_negative_dentry_dec (d_is_negative (dentry));list_lru_isolate_move (lru, &dentry->d_lru, list); }
@@ -1865,8 +1883,7 @@ static void __d_instantiate(struct dentry *dentry, struct inode *inode)/* * Decrement negative dentry count if it was in the LRU list. */ -if (dentry->d_flags &DCACHE_LRU_LIST ) -this_cpu_dec (nr_dentry_negative); +cond_negative_dentry_dec (dentry->d_flags &DCACHE_LRU_LIST );hlist_add_head (&dentry->d_u.d_alias, &inode->i_dentry);raw_write_seqcount_begin (&dentry->d_seq);__d_set_inode_and_type (dentry, inode, add_flags);
Signature · 1 line
1.8.3.1
Re: [PATCH v3 4/4] fs/dcache: Eliminate branches in nr_dentry_negative accounting
Quoted 8 lines · Waiman Long
Because the accounting of
nr_dentry_negativedepends on whether a dentry is a negative one or not, branch instructions are introduced to handle the accounting conditionally. That may potentially slow down the task by a noticeable amount if that introduces sizeable amount of additional branch mispredictions.To avoid that, the accounting code is now modified to use conditional move instructions instead, if supported by the architecture.
I think this is a case of over-optimisation. It makes the code harder to read for extremely marginal benefit, and if we ever need to add any more code for negative dentries in these paths the first thing we'll have to do is revert this change.
Unless you have numbers demonstrating that it's a clear performance improvement, then NACK for this patch.
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Re: [PATCH v3 4/4] fs/dcache: Eliminate branches in nr_dentry_negative accounting
Quoted 14 lines · Dave Chinner
Quoted 8 lines · Waiman Long
Because the accounting of
nr_dentry_negativedepends on whether a dentry is a negative one or not, branch instructions are introduced to handle the accounting conditionally. That may potentially slow down the task by a noticeable amount if that introduces sizeable amount of additional branch mispredictions.To avoid that, the accounting code is now modified to use conditional move instructions instead, if supported by the architecture.
I think this is a case of over-optimisation. It makes the code harder to read for extremely marginal benefit, and if we ever need to add any more code for negative dentries in these paths the first thing we'll have to do is revert this change.
Quoted 6 lines
Unless you have numbers demonstrating that it's a clear performance improvement, then NACK for this patch.
Cheers,
Dave.
Yes, this is an optimization.
Unfortunately I don't have any performance number as I had not seen any significant performance difference outside of the noise range with these set of changes. I am not fine with not taking this patch.
Cheers,
Longman
Re: [PATCH v3 4/4] fs/dcache: Eliminate branches in nr_dentry_negative accounting
In reply to Waiman LongQuoted 8 lines · Waiman Long
Because the accounting of
nr_dentry_negativedepends on whether a dentry is a negative one or not, branch instructions are introduced to handle the accounting conditionally. That may potentially slow down the task by a noticeable amount if that introduces sizeable amount of additional branch mispredictions.To avoid that, the accounting code is now modified to use conditional move instructions instead, if supported by the architecture.
You're substituting your judgement here for the compiler's. I don't see a reason why the compiler couldn't choose to use a cmov in order to do this:
if (dentry->d_flags & DCACHE_LRU_LIST) this_cpu_inc(nr_dentry_negative);
unless our macrology has got too clever for the compilre to see through it. In which case, the right answer is to simplify the percpu code, not to force the compiler to optimise the code in the way that makes sense for your current microarchitecture.
Re: [PATCH v3 4/4] fs/dcache: Eliminate branches in nr_dentry_negative accounting
Quoted 13 lines · Matthew Wilcox
Quoted 8 lines · Waiman Long
Because the accounting of
nr_dentry_negativedepends on whether a dentry is a negative one or not, branch instructions are introduced to handle the accounting conditionally. That may potentially slow down the task by a noticeable amount if that introduces sizeable amount of additional branch mispredictions.To avoid that, the accounting code is now modified to use conditional move instructions instead, if supported by the architecture.
You're substituting your judgement here for the compiler's. I don't see a reason why the compiler couldn't choose to use a cmov in order to do this:
Quoted 8 lines
if (dentry->d_flags & DCACHE_LRU_LIST) this_cpu_inc(nr_dentry_negative);unless our macrology has got too clever for the compilre to see through it. In which case, the right answer is to simplify the percpu code, not to force the compiler to optimise the code in the way that makes sense for your current microarchitecture.
I had actually looked at the x86 object file generated to verify that it did use cmove with the patch and use branch without. It is possible that there are other twists to make that happen with the above expression. I will need to run some experiments to figure it out. In the mean time, I am fine with dropping this patch as it is a micro-optimization that doesn't change the behavior at all.
Cheers,
Longman
Re: [PATCH v3 4/4] fs/dcache: Eliminate branches in nr_dentry_negative accounting
Quoted 11 lines · Waiman Long
Quoted 5 lines
unless our macrology has got too clever for the compilre to see through it. In which case, the right answer is to simplify the percpu code, not to force the compiler to optimise the code in the way that makes sense for your current microarchitecture.
I had actually looked at the x86 object file generated to verify that it did use cmove with the patch and use branch without. It is possible that there are other twists to make that happen with the above expression. I will need to run some experiments to figure it out. In the mean time, I am fine with dropping this patch as it is a micro-optimization that doesn't change the behavior at all.
I don't understand why you included it, to be honest. But it did get me looking at the percpu code to see if it was too clever. And that led to the resubmission of rth's patch from two years ago that I cc'd you on earlier.
With that patch applied, gcc should be able to choose to use the cmov if it feels that would be a better optimisation. It already makes one different decision in dcache.o, namely that it uses addq $0x1,%gs:0x0(%rip) instead of incq %gs:0x0(%rip). Apparently this performs better on some CPUs.
So I wouldn't spend any more time on this patch.
Re: [PATCH v3 4/4] fs/dcache: Eliminate branches in nr_dentry_negative accounting
Quoted 17 lines · Matthew Wilcox
Quoted 11 lines · Waiman Long
Quoted 5 lines
unless our macrology has got too clever for the compilre to see through it. In which case, the right answer is to simplify the percpu code, not to force the compiler to optimise the code in the way that makes sense for your current microarchitecture.
I had actually looked at the x86 object file generated to verify that it did use cmove with the patch and use branch without. It is possible that there are other twists to make that happen with the above expression. I will need to run some experiments to figure it out. In the mean time, I am fine with dropping this patch as it is a micro-optimization that doesn't change the behavior at all.
I don't understand why you included it, to be honest. But it did get me looking at the percpu code to see if it was too clever. And that led to the resubmission of rth's patch from two years ago that I cc'd you on earlier.
Quoted 7 lines
With that patch applied, gcc should be able to choose to use the cmov if it feels that would be a better optimisation. It already makes one different decision in dcache.o, namely that it uses addq $0x1,%gs:0x0(%rip) instead of incq %gs:0x0(%rip). Apparently this performs better on some CPUs.
So I wouldn't spend any more time on this patch.
Thank for looking into that. Well I am not going to look further into this unless I have no other thing to do which is unlikely.
Cheers,
Longman