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 <krisman@xxxxxxxxxxxxxxx>
---
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
