From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from bhuna.collabora.co.uk ([46.235.227.227]:39398 "EHLO bhuna.collabora.co.uk" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751748AbeEVUiT (ORCPT ); Tue, 22 May 2018 16:38:19 -0400 From: Gabriel Krisman Bertazi To: viro@ZenIV.linux.org.uk Cc: linux-fsdevel@vger.kernel.org, Gabriel Krisman Bertazi Subject: [PATCH NOMERGE 06/13] vfs: Add Support for hard negative dentries in the dcache Date: Tue, 22 May 2018 17:38:11 -0300 Message-Id: <20180522203818.14666-7-krisman@collabora.co.uk> In-Reply-To: <20180522203818.14666-1-krisman@collabora.co.uk> References: <20180522203818.14666-1-krisman@collabora.co.uk> Sender: linux-fsdevel-owner@vger.kernel.org List-ID: A hard negative dentry is created after an unsuccessful case-insensitive(CI) lookup operation, to indicate that there is not any file in that directory whose casefolded name matches the casefolded searched name. Hard negative dentries are the CI counterpart of the existing negative dentries for the case-isensitive lookup case. For clarity, this patch denotes the old negative dentry as "soft negative dentry" where applicable. In places where it doesn't matter whether it is a hard or soft dentry, the wrapper d_is_negative() can still be used. Despite being the counterpart of soft negative dentries, a hard dentry actually express a much stronger constraint, asserting that there is no name in the filesystem that would match the string being searched, AFTER a casefold() operation. A hard negative dentry allows the dcache to return a -ENOENT immediately during a dcache lookup , eliminating the need to go to the disk for every CI operation. The hard negative dentry definition also encloses the soft dentry constraint, such that we can also use a hard negative dentry to return ENOENT after a Case sensitive(CS) lookup. Special care must be taken to invalidate (or at least demote) Hard dentries once a matching file is created in the disk. The file being created might not have the exact name as the hard dentry (but it must have an exact casefold match), but this still means the dentry must be invalidated. This is handled by invalidating the dentry found in lookup_open, only if it is a hard negative. Unless we are doing a creation, there is no need to invalidate it elsewhere. Soft dentries could be promoted to hard dentries after a LOOKUP_CASEFOLD operation, but for simplifying the code, we don't do the promotion explicitly, instead we invalidate the soft dentry and recreate it during the following lookup as a hard dentry. Likewise, hard dentries could be demoted when a inexact-case match is created. For this case, the current code also invalidates the dentry and creates a new one. Filesystems who want to expose CI operations must make sure their revalidate() functions no longer reject any type of negative dentries, they can only reject soft negatives. If they do reject negative dentries, say in the transition phase, there is no problem, they will be basically ignoring this feature and paying the cost to hit the disk everytime. A function called d_add_ci_negative_dentry is also added in this series, as a helper for user filesystems, when they hit an inexisting file during a LOOKUP_CASEFOLD operation. An example of usage comes later in the series, with the patches that add LOOKUP_CASEFOLD support for the EXT4 filesystem. This patch reduces the time of doing an inexact-name lookup of 10k inexistant but already dcached files, down to 0.007 seconds in my test vm, which is pretty similar to issuing the same operation to a CS filesystem without this patch series. Signed-off-by: Gabriel Krisman Bertazi --- fs/dcache.c | 29 +++++++++++++++++++++-------- fs/namei.c | 7 +++++-- include/linux/dcache.h | 16 ++++++++++++++-- 3 files changed, 40 insertions(+), 12 deletions(-) diff --git a/fs/dcache.c b/fs/dcache.c index 30c5eff31e88..a68af63c8a96 100644 --- a/fs/dcache.c +++ b/fs/dcache.c @@ -1784,12 +1784,17 @@ void d_set_fallthru(struct dentry *dentry) } EXPORT_SYMBOL(d_set_fallthru); -static unsigned d_flags_for_inode(struct inode *inode) +static unsigned d_flags_for_inode(struct dentry *dentry, struct inode *inode) { unsigned add_flags = DCACHE_REGULAR_TYPE; - if (!inode) - return DCACHE_MISS_TYPE; + if (!inode) { + /* hard negative dentries get set beforehand. */ + if (d_is_hard_negative(dentry)) + return DCACHE_HARD_NEGATIVE_TYPE; + else + return DCACHE_MISS_TYPE; + } if (S_ISDIR(inode->i_mode)) { add_flags = DCACHE_DIRECTORY_TYPE; @@ -1821,7 +1826,7 @@ static unsigned d_flags_for_inode(struct inode *inode) static void __d_instantiate(struct dentry *dentry, struct inode *inode) { - unsigned add_flags = d_flags_for_inode(inode); + unsigned add_flags = d_flags_for_inode(dentry, inode); WARN_ON(d_in_lookup(dentry)); spin_lock(&dentry->d_lock); @@ -1948,7 +1953,7 @@ static struct dentry *__d_instantiate_anon(struct dentry *dentry, } /* attach a disconnected dentry */ - add_flags = d_flags_for_inode(inode); + add_flags = d_flags_for_inode(dentry, inode); if (disconnected) add_flags |= DCACHE_DISCONNECTED; @@ -2130,6 +2135,14 @@ struct dentry *d_add_ci(struct dentry *dentry, struct inode *inode, } EXPORT_SYMBOL(d_add_ci); +struct dentry *d_add_ci_negative_dentry(struct dentry *dentry) +{ + /* Mark the dentry as hard negative. */ + dentry->d_flags |= DCACHE_HARD_NEGATIVE_TYPE; + + return d_splice_alias(NULL, dentry); +} + /** * __d_lookup_rcu - search for a dentry (racy, store-free) * @parent: parent dentry @@ -2230,7 +2243,7 @@ struct dentry *__d_lookup_rcu(const struct dentry *parent, goto seqretry; } - if (ci_lookup) { + if (ci_lookup || d_is_hard_negative(dentry)) { if (parent->d_op->d_compare_ci(dentry, tlen, tname, name) != 0) continue; @@ -2335,7 +2348,7 @@ struct dentry *__d_lookup(const struct dentry *parent, const struct qstr *name, if (d_unhashed(dentry)) goto next; - if (ci_lookup) { + if (ci_lookup || d_is_hard_negative(dentry)) { if (!d_same_name_ci(dentry, parent, name)) goto next; } else { @@ -2618,7 +2631,7 @@ static inline void __d_add(struct dentry *dentry, struct inode *inode) __d_lookup_done(dentry); } if (inode) { - unsigned add_flags = d_flags_for_inode(inode); + unsigned add_flags = d_flags_for_inode(dentry, inode); 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); diff --git a/fs/namei.c b/fs/namei.c index 1ebe5e775a9a..69726d2f6f81 100644 --- a/fs/namei.c +++ b/fs/namei.c @@ -765,7 +765,7 @@ static inline int d_revalidate(struct dentry *dentry, unsigned int flags) /* Completely ignore negative dentries for LOOKUP_CASEFOLD. */ if (unlikely(flags & LOOKUP_CASEFOLD)) { - if (d_is_negative(dentry)) + if (d_is_soft_negative(dentry)) return 0; } @@ -3142,7 +3142,9 @@ static int lookup_open(struct nameidata *nd, struct path *path, dentry = d_alloc_parallel(dir, &nd->last, &wq); if (IS_ERR(dentry)) return PTR_ERR(dentry); - } + } else if (d_is_hard_negative(dentry)) + goto invalidate; + if (d_in_lookup(dentry)) break; @@ -3151,6 +3153,7 @@ static int lookup_open(struct nameidata *nd, struct path *path, break; if (error) goto out_dput; +invalidate: d_invalidate(dentry); dput(dentry); dentry = NULL; diff --git a/include/linux/dcache.h b/include/linux/dcache.h index a4ce5ea207ad..f215bcc2f60b 100644 --- a/include/linux/dcache.h +++ b/include/linux/dcache.h @@ -206,13 +206,14 @@ struct dentry_operations { #define DCACHE_LRU_LIST 0x00080000 #define DCACHE_ENTRY_TYPE 0x00700000 -#define DCACHE_MISS_TYPE 0x00000000 /* Negative dentry (maybe fallthru to nowhere) */ +#define DCACHE_MISS_TYPE 0x00000000 /* Soft negative dentry (maybe fallthru to nowhere) */ #define DCACHE_WHITEOUT_TYPE 0x00100000 /* Whiteout dentry (stop pathwalk) */ #define DCACHE_DIRECTORY_TYPE 0x00200000 /* Normal directory */ #define DCACHE_AUTODIR_TYPE 0x00300000 /* Lookupless directory (presumed automount) */ #define DCACHE_REGULAR_TYPE 0x00400000 /* Regular file type (or fallthru to such) */ #define DCACHE_SPECIAL_TYPE 0x00500000 /* Other file type (or fallthru to such) */ #define DCACHE_SYMLINK_TYPE 0x00600000 /* Symlink (or fallthru to such) */ +#define DCACHE_HARD_NEGATIVE_TYPE 0x00700000 /* Hard negative dentry */ #define DCACHE_MAY_FREE 0x00800000 #define DCACHE_FALLTHRU 0x01000000 /* Fall through to lower layer */ @@ -244,6 +245,7 @@ extern struct dentry * d_alloc_parallel(struct dentry *, const struct qstr *, wait_queue_head_t *); extern struct dentry * d_splice_alias(struct inode *, struct dentry *); extern struct dentry * d_add_ci(struct dentry *, struct inode *, struct qstr *); +extern struct dentry * d_add_ci_negative_dentry(struct dentry *); extern struct dentry * d_exact_alias(struct dentry *, struct inode *); extern struct dentry *d_find_any_alias(struct inode *inode); extern struct dentry * d_obtain_alias(struct inode *); @@ -444,12 +446,22 @@ static inline bool d_is_file(const struct dentry *dentry) return d_is_reg(dentry) || d_is_special(dentry); } -static inline bool d_is_negative(const struct dentry *dentry) +static inline bool d_is_soft_negative(const struct dentry *dentry) { // TODO: check d_is_whiteout(dentry) also. return d_is_miss(dentry); } +static inline bool d_is_hard_negative(const struct dentry *dentry) +{ + return __d_entry_type(dentry) == DCACHE_HARD_NEGATIVE_TYPE; +} + +static inline bool d_is_negative(const struct dentry *dentry) +{ + return d_is_soft_negative(dentry) || d_is_hard_negative(dentry); +} +extern const struct inode_operations ext4_dir_inode_operations; static inline bool d_is_positive(const struct dentry *dentry) { return !d_is_negative(dentry); -- 2.17.0