archive mirror
 help / color / mirror / Atom feed
From: Gabriel Krisman Bertazi <>
	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	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <>

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

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)
-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)
+	if (!inode) {
+		/* hard negative dentries get set beforehand. */
+		if (d_is_hard_negative(dentry))
+		else
+			return DCACHE_MISS_TYPE;
+	}
 	if (S_ISDIR(inode->i_mode)) {
@@ -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);
@@ -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,
+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)
@@ -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)
 	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);
 		__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))
@@ -3151,6 +3153,7 @@ static int lookup_open(struct nameidata *nd, struct path *path,
 		if (error)
 			goto out_dput;
 		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);

  parent reply	other threads:[~2018-05-22 20:38 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-22 20:38 [PATCH NOMERGE 00/13] Case insensitiveness as a mountpoint Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 01/13] vfs: Add support for mounting with MS_CASEFOLD Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 02/13] vfs: Propagate LOOKUP_CASEFOLD after doing parent lookups Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 03/13] vfs: Add support for positive dentries CI lookups in the dentry cache Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 04/13] vfs: Allow bind,remount with MS_CASEFOLD Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 05/13] vfs: Handle case-exact lookup in d_add_ci Gabriel Krisman Bertazi
2018-05-22 20:38 ` Gabriel Krisman Bertazi [this message]
2018-05-22 20:38 ` [PATCH NOMERGE 07/13] vfs: Handle MNT_CASEFOLD in /proc/mounts Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 08/13] fscrypt: Introduce charset-based matching functions Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 09/13] ext4: Include encoding information on the superblock Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 10/13] ext4: Plumb LOOK_CASEFOLD up to ext4 comparison functions Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 11/13] ext4: Support charset name matching Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 12/13] ext4: Implement ext4 dcache hooks for custom charsets Gabriel Krisman Bertazi
2018-05-22 20:38 ` [PATCH NOMERGE 13/13] ext4: Notify VFS of support for casefolded mountpoints Gabriel Krisman Bertazi

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \
    --subject='Re: [PATCH NOMERGE 06/13] vfs: Add Support for hard negative dentries in the dcache' \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).