[PATCH v3 0/2] Try exact-match comparison ahead of case-insensitive match

[PATCH v3 0/2] Try exact-match comparison ahead of case-insensitive match

[Gabriel Krisman Bertazi]

Linus, Al, Eric,

This small series implement the exact-match comparison ahead of the
case-insensitive comparison as suggested by Linus.  The first patch only
exposes dentry_string_cmp in a header file so we can use it instead of
memcmp and the second actually do the optimization in the
case-insensitive comparison code.

Gabriel Krisman Bertazi (2):
  dcache: Expose dentry_string_cmp outside of dcache
  libfs: Attempt exact-match comparison first during casefold lookup

 fs/dcache.c            | 53 ------------------------------------------
 fs/libfs.c             | 39 +++++++++++++++++--------------
 include/linux/dcache.h | 53 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 75 insertions(+), 70 deletions(-)

-- 
2.43.0

[PATCH v3 1/2] dcache: Expose dentry_string_cmp outside of dcache

[Gabriel Krisman Bertazi]

In preparation to call these from libfs, expose dentry_string_cmp in the
header file.

Signed-off-by: Gabriel Krisman Bertazi <krisman@suse.de>
---
 fs/dcache.c            | 53 ------------------------------------------
 include/linux/dcache.h | 53 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 53 insertions(+), 53 deletions(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index b813528fb147..7bb17596d0ad 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -201,59 +201,6 @@ static int __init init_fs_dcache_sysctls(void)
 fs_initcall(init_fs_dcache_sysctls);
 #endif
 
-/*
- * Compare 2 name strings, return 0 if they match, otherwise non-zero.
- * The strings are both count bytes long, and count is non-zero.
- */
-#ifdef CONFIG_DCACHE_WORD_ACCESS
-
-#include <asm/word-at-a-time.h>
-/*
- * NOTE! 'cs' and 'scount' come from a dentry, so it has a
- * aligned allocation for this particular component. We don't
- * strictly need the load_unaligned_zeropad() safety, but it
- * doesn't hurt either.
- *
- * In contrast, 'ct' and 'tcount' can be from a pathname, and do
- * need the careful unaligned handling.
- */
-static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
-{
-	unsigned long a,b,mask;
-
-	for (;;) {
-		a = read_word_at_a_time(cs);
-		b = load_unaligned_zeropad(ct);
-		if (tcount < sizeof(unsigned long))
-			break;
-		if (unlikely(a != b))
-			return 1;
-		cs += sizeof(unsigned long);
-		ct += sizeof(unsigned long);
-		tcount -= sizeof(unsigned long);
-		if (!tcount)
-			return 0;
-	}
-	mask = bytemask_from_count(tcount);
-	return unlikely(!!((a ^ b) & mask));
-}
-
-#else
-
-static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
-{
-	do {
-		if (*cs != *ct)
-			return 1;
-		cs++;
-		ct++;
-		tcount--;
-	} while (tcount);
-	return 0;
-}
-
-#endif
-
 static inline int dentry_cmp(const struct dentry *dentry, const unsigned char *ct, unsigned tcount)
 {
 	/*
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index 1666c387861f..0f210a396074 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -592,4 +592,57 @@ static inline struct dentry *d_next_sibling(const struct dentry *dentry)
 	return hlist_entry_safe(dentry->d_sib.next, struct dentry, d_sib);
 }
 
+/*
+ * Compare 2 name strings, return 0 if they match, otherwise non-zero.
+ * The strings are both count bytes long, and count is non-zero.
+ */
+#ifdef CONFIG_DCACHE_WORD_ACCESS
+
+#include <asm/word-at-a-time.h>
+/*
+ * NOTE! 'cs' and 'scount' come from a dentry, so it has a
+ * aligned allocation for this particular component. We don't
+ * strictly need the load_unaligned_zeropad() safety, but it
+ * doesn't hurt either.
+ *
+ * In contrast, 'ct' and 'tcount' can be from a pathname, and do
+ * need the careful unaligned handling.
+ */
+static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
+{
+	unsigned long a,b,mask;
+
+	for (;;) {
+		a = read_word_at_a_time(cs);
+		b = load_unaligned_zeropad(ct);
+		if (tcount < sizeof(unsigned long))
+			break;
+		if (unlikely(a != b))
+			return 1;
+		cs += sizeof(unsigned long);
+		ct += sizeof(unsigned long);
+		tcount -= sizeof(unsigned long);
+		if (!tcount)
+			return 0;
+	}
+	mask = bytemask_from_count(tcount);
+	return unlikely(!!((a ^ b) & mask));
+}
+
+#else
+
+static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char *ct, unsigned tcount)
+{
+	do {
+		if (*cs != *ct)
+			return 1;
+		cs++;
+		ct++;
+		tcount--;
+	} while (tcount);
+	return 0;
+}
+
+#endif
+
 #endif	/* __LINUX_DCACHE_H */
-- 
2.43.0

Re: [PATCH v3 1/2] dcache: Expose dentry_string_cmp outside of dcache

[Linus Torvalds]

On Fri, 19 Jan 2024 at 12:25, Gabriel Krisman Bertazi <krisman@suse.de> wrote:
>
> In preparation to call these from libfs, expose dentry_string_cmp in the
> header file.

Let's not make these header files bigger and more complex.

Particularly not for generic_ci_d_compare() to inline it, which makes
no sense: generic_ci_d_compare() is so heavy with a big stack frame
anyway, that the inlining of this would seem to be just in the noise.

And when I look closer, it turns out that __d_lookup_rcu_op_compare()
that does this all also does the proper sequence number magic to make
the name pointer and the length consistent.

So I don't think we need the careful name compare after all, because
the caller has fixed the consistency issue.

I do also wonder if we should just move the "identical always compares
equal" case into __d_lookup_rcu_op_compare(), and not have
->d_compare() have to worry about it at all?

                     Linus

Re: [PATCH v3 1/2] dcache: Expose dentry_string_cmp outside of dcache

[Gabriel Krisman Bertazi]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Fri, 19 Jan 2024 at 12:25, Gabriel Krisman Bertazi <krisman@suse.de> wrote:
>>
>> In preparation to call these from libfs, expose dentry_string_cmp in the
>> header file.
>
> Let's not make these header files bigger and more complex.
>
> Particularly not for generic_ci_d_compare() to inline it, which makes
> no sense: generic_ci_d_compare() is so heavy with a big stack frame
> anyway, that the inlining of this would seem to be just in the noise.
>
> And when I look closer, it turns out that __d_lookup_rcu_op_compare()
> that does this all also does the proper sequence number magic to make
> the name pointer and the length consistent.

Ok. I see that we retry the read before calling d_compare here:

    /* we want a consistent (name,len) pair */
    if (read_seqcount_retry(&dentry->d_seq, seq)) {
	cpu_relax();
	goto seqretry;
    }

for RCU and for d_same_name we are holding the d_lock.

So, I guess I was right for the wrong reason in the earlier
versions. which doesn't really do me any good.

> So I don't think we need the careful name compare after all, because
> the caller has fixed the consistency issue.
>
> I do also wonder if we should just move the "identical always compares
> equal" case into __d_lookup_rcu_op_compare(), and not have
> ->d_compare() have to worry about it at all?

I considered that, and I can do it as a follow up.  I'd like to audit
d_compare to ensure we can change its semantics by only calling it if
the exact-match d_compare failed.  Is there a filesystem where that
really matters?  If so, we can add a new ->d_weak_compare hook.
Considering the ones I looked already will do fine with this change,
it's likely possible.

Are you ok with the earlier v2 of this patchset as-is, and I'll send a
new series proposing this change?

Thank you,

-- 
Gabriel Krisman Bertazi

Re: [PATCH v3 1/2] dcache: Expose dentry_string_cmp outside of dcache

[Linus Torvalds]

On Sun, 21 Jan 2024 at 08:34, Gabriel Krisman Bertazi <krisman@suse.de> wrote:
>
> Are you ok with the earlier v2 of this patchset as-is, and I'll send a
> new series proposing this change?

Yeah, possibly updating just the commit log to mention how
__d_lookup_rcu_op_compare() takes care of the data race.

I do think that just doing the exact check in
__d_lookup_rcu_op_compare() would then avoid things like the indirect
call for that (presumably common) case, but it's not a big deal.

              Linus

[PATCH v4] libfs: Attempt exact-match comparison first during casefolded lookup

[Gabriel Krisman Bertazi]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> On Sun, 21 Jan 2024 at 08:34, Gabriel Krisman Bertazi <krisman@suse.de> wrote:
>>
>> Are you ok with the earlier v2 of this patchset as-is, and I'll send a
>> new series proposing this change?
>
> Yeah, possibly updating just the commit log to mention how
> __d_lookup_rcu_op_compare() takes care of the data race.

Just for completeness, below the version I intend to apply to
unicode/for-next , which is the v2, plus the comments you and Eric
requested. That is, unless something else comes up.

> I do think that just doing the exact check in
> __d_lookup_rcu_op_compare() would then avoid things like the indirect
> call for that (presumably common) case, but it's not a big deal.

I will also follow up with a new patch for this shortly.

Thanks for the reviews.

-- >8 --
Subject: [PATCH v4] libfs: Attempt exact-match comparison first during
 casefolded lookup

Casefolded comparisons are (obviously) way more costly than a simple
memcmp.  Try the case-sensitive comparison first, falling-back to the
case-insensitive lookup only when needed.  This allows any exact-match
lookup to complete without having to walk the utf8 trie.

Note that, for strict mode, generic_ci_d_compare used to reject an
invalid UTF-8 string, which would now be considered valid if it
exact-matches the disk-name.  But, if that is the case, the filesystem
is corrupt.  More than that, it really doesn't matter in practice,
because the name-under-lookup will have already been rejected by
generic_ci_d_hash and we won't even get here.

The memcmp is safe under RCU because we are operating on str/len instead
of dentry->d_name directly, and the caller guarantees their consistency
between each other in __d_lookup_rcu_op_compare.

Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Gabriel Krisman Bertazi <krisman@suse.de>
---
 fs/libfs.c | 40 +++++++++++++++++++++++-----------------
 1 file changed, 23 insertions(+), 17 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index eec6031b0155..306a0510b7dc 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -1704,16 +1704,28 @@ bool is_empty_dir_inode(struct inode *inode)
 static int generic_ci_d_compare(const struct dentry *dentry, unsigned int len,
 				const char *str, const struct qstr *name)
 {
-	const struct dentry *parent = READ_ONCE(dentry->d_parent);
-	const struct inode *dir = READ_ONCE(parent->d_inode);
-	const struct super_block *sb = dentry->d_sb;
-	const struct unicode_map *um = sb->s_encoding;
-	struct qstr qstr = QSTR_INIT(str, len);
+	const struct dentry *parent;
+	const struct inode *dir;
 	char strbuf[DNAME_INLINE_LEN];
-	int ret;
+	struct qstr qstr;
+
+	/*
+	 * Attempt a case-sensitive match first. It is cheaper and
+	 * should cover most lookups, including all the sane
+	 * applications that expect a case-sensitive filesystem.
+	 *
+	 * This comparison is safe under RCU because the caller
+	 * guarantees the consistency between str and len. See
+	 * __d_lookup_rcu_op_compare() for details.
+	 */
+	if (len == name->len && !memcmp(str, name->name, len))
+		return 0;
 
+	parent = READ_ONCE(dentry->d_parent);
+	dir = READ_ONCE(parent->d_inode);
 	if (!dir || !IS_CASEFOLDED(dir))
-		goto fallback;
+		return 1;
+
 	/*
 	 * If the dentry name is stored in-line, then it may be concurrently
 	 * modified by a rename.  If this happens, the VFS will eventually retry
@@ -1724,20 +1736,14 @@ static int generic_ci_d_compare(const struct dentry *dentry, unsigned int len,
 	if (len <= DNAME_INLINE_LEN - 1) {
 		memcpy(strbuf, str, len);
 		strbuf[len] = 0;
-		qstr.name = strbuf;
+		str = strbuf;
 		/* prevent compiler from optimizing out the temporary buffer */
 		barrier();
 	}
-	ret = utf8_strncasecmp(um, name, &qstr);
-	if (ret >= 0)
-		return ret;
+	qstr.len = len;
+	qstr.name = str;
 
-	if (sb_has_strict_encoding(sb))
-		return -EINVAL;
-fallback:
-	if (len != name->len)
-		return 1;
-	return !!memcmp(str, name->name, len);
+	return utf8_strncasecmp(dentry->d_sb->s_encoding, name, &qstr);
 }
 
 /**
-- 
2.43.0

Re: [PATCH v4] libfs: Attempt exact-match comparison first during casefolded lookup

[Linus Torvalds]

On Wed, 24 Jan 2024 at 10:13, Gabriel Krisman Bertazi <krisman@suse.de> wrote:
>
> Just for completeness, below the version I intend to apply to
> unicode/for-next , which is the v2, plus the comments you and Eric
> requested. That is, unless something else comes up.

Looks ok to me.

My one comment is actually unrelated to the new code, just because the
patch touches this code too:

>         if (len <= DNAME_INLINE_LEN - 1) {
>                 memcpy(strbuf, str, len);
>                 strbuf[len] = 0;
> -               qstr.name = strbuf;
> +               str = strbuf;
>                 /* prevent compiler from optimizing out the temporary buffer */
>                 barrier();

The reason for this whole mess is that allegedly utf8_strncasecmp() is
not safe if the buffer changes under it.

At least that's what the comment says.

But honestly, I don't see it.

I think the whole "copy to a stable buffer" code can and should just
be removed as voodoo programming.

*If* the buffer is actually changing, the name lookup code will just
retry, so whether the return value is correct or not is irrelevant.

All that matters is that the code honors the str/len constraint, and
not blow up - even if the data inside that str/len buffer might not be
stable.

I don't see how the utf8 code could possibly mess up.

That code goes back to commit

  2ce3ee931a09 ("ext4: avoid utf8_strncasecmp() with unstable name")
  fc3bb095ab02 ("f2fs: avoid utf8_strncasecmp() with unstable name")

and I think it's bogus.

Eric - the string *data* may be unsafe, but the string length passed
to the utf8 routines is not changing any more (since it was loaded
long ago).

And honestly, no amount of "the data may change" should possibly ever
cause the utf8 code to then ignore the length that was passed in.

                Linus

Re: [PATCH v4] libfs: Attempt exact-match comparison first during casefolded lookup

[Eric Biggers]

Hi Linus,

On Wed, Jan 24, 2024 at 10:42:51AM -0800, Linus Torvalds wrote:
> On Wed, 24 Jan 2024 at 10:13, Gabriel Krisman Bertazi <krisman@suse.de> wrote:
> >
> > Just for completeness, below the version I intend to apply to
> > unicode/for-next , which is the v2, plus the comments you and Eric
> > requested. That is, unless something else comes up.
> 
> Looks ok to me.
> 
> My one comment is actually unrelated to the new code, just because the
> patch touches this code too:
> 
> >         if (len <= DNAME_INLINE_LEN - 1) {
> >                 memcpy(strbuf, str, len);
> >                 strbuf[len] = 0;
> > -               qstr.name = strbuf;
> > +               str = strbuf;
> >                 /* prevent compiler from optimizing out the temporary buffer */
> >                 barrier();
> 
> The reason for this whole mess is that allegedly utf8_strncasecmp() is
> not safe if the buffer changes under it.
> 
> At least that's what the comment says.
> 
> But honestly, I don't see it.
> 
> I think the whole "copy to a stable buffer" code can and should just
> be removed as voodoo programming.
> 
> *If* the buffer is actually changing, the name lookup code will just
> retry, so whether the return value is correct or not is irrelevant.
> 
> All that matters is that the code honors the str/len constraint, and
> not blow up - even if the data inside that str/len buffer might not be
> stable.
> 
> I don't see how the utf8 code could possibly mess up.
> 
> That code goes back to commit
> 
>   2ce3ee931a09 ("ext4: avoid utf8_strncasecmp() with unstable name")
>   fc3bb095ab02 ("f2fs: avoid utf8_strncasecmp() with unstable name")
> 
> and I think it's bogus.
> 
> Eric - the string *data* may be unsafe, but the string length passed
> to the utf8 routines is not changing any more (since it was loaded
> long ago).
> 
> And honestly, no amount of "the data may change" should possibly ever
> cause the utf8 code to then ignore the length that was passed in.
> 

Since utf8_strncasecmp() has to parse the UTF-8 sequences from the strings, and
UTF-8 sequences are variable-length and may be invalid, there are cases in which
it reads bytes from the strings multiple times.  This makes it especially
vulnerable to non-benign data races, when compared to simpler functions like
memcpy() or memcmp() that more straightforwardly do one pass through the data.

The onus should be on proving the code is safe, not proving that it's unsafe.
But for a specific example of how a data race in utf8_strncasecmp() might be
able to cause a memory safety violation, see the example I gave at
https://lore.kernel.org/linux-fsdevel/20200212063440.GL870@sol.localdomain/.

- Eric

[PATCH v3 2/2] libfs: Attempt exact-match comparison first during casefold lookup

[Gabriel Krisman Bertazi]

Casefolded comparisons are (obviously) way more costly than a simple
memcmp.  Try the case-sensitive comparison first, falling-back to the
case-insensitive lookup only when needed.  This allows any exact-match
lookup to complete without having to walk the utf8 trie.

Note that, for strict mode, generic_ci_d_compare used to reject an
invalid UTF-8 string, which would now be considered valid if it
exact-matches the disk-name.  But, if that is the case, the filesystem
is corrupt.  More than that, it really doesn't matter in practice,
because the name-under-lookup will have already been rejected by
generic_ci_d_hash and we won't even get here.

Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Gabriel Krisman Bertazi <krisman@suse.de>

---
changes since v2:
  - Use dentry_string_cmp instead of memcmp (Linus, Eric)
changes since v1:
  - just return utf8_strncasemp directly (Al Viro)
---
 fs/libfs.c | 39 ++++++++++++++++++++++-----------------
 1 file changed, 22 insertions(+), 17 deletions(-)

diff --git a/fs/libfs.c b/fs/libfs.c
index eec6031b0155..f64036a2eb7f 100644
--- a/fs/libfs.c
+++ b/fs/libfs.c
@@ -1704,16 +1704,27 @@ bool is_empty_dir_inode(struct inode *inode)
 static int generic_ci_d_compare(const struct dentry *dentry, unsigned int len,
 				const char *str, const struct qstr *name)
 {
-	const struct dentry *parent = READ_ONCE(dentry->d_parent);
-	const struct inode *dir = READ_ONCE(parent->d_inode);
-	const struct super_block *sb = dentry->d_sb;
-	const struct unicode_map *um = sb->s_encoding;
-	struct qstr qstr = QSTR_INIT(str, len);
+	const struct dentry *parent;
+	const struct inode *dir;
 	char strbuf[DNAME_INLINE_LEN];
-	int ret;
+	struct qstr qstr;
+
+	/*
+	 * Attempt a case-sensitive match first. It is cheaper and
+	 * should cover most lookups, including all the sane
+	 * applications that expect a case-sensitive filesystem.
+	 *
+	 * dentry->d_name might change from under us.  use str instead,
+           and make sure to not rely on len.
+	 */
+	if (!dentry_string_cmp(str, name->name, name->len))
+		return 0;
 
+	parent = READ_ONCE(dentry->d_parent);
+	dir = READ_ONCE(parent->d_inode);
 	if (!dir || !IS_CASEFOLDED(dir))
-		goto fallback;
+		return 1;
+
 	/*
 	 * If the dentry name is stored in-line, then it may be concurrently
 	 * modified by a rename.  If this happens, the VFS will eventually retry
@@ -1724,20 +1735,14 @@ static int generic_ci_d_compare(const struct dentry *dentry, unsigned int len,
 	if (len <= DNAME_INLINE_LEN - 1) {
 		memcpy(strbuf, str, len);
 		strbuf[len] = 0;
-		qstr.name = strbuf;
+		str = strbuf;
 		/* prevent compiler from optimizing out the temporary buffer */
 		barrier();
 	}
-	ret = utf8_strncasecmp(um, name, &qstr);
-	if (ret >= 0)
-		return ret;
+	qstr.len = len;
+	qstr.name = str;
 
-	if (sb_has_strict_encoding(sb))
-		return -EINVAL;
-fallback:
-	if (len != name->len)
-		return 1;
-	return !!memcmp(str, name->name, len);
+	return utf8_strncasecmp(dentry->d_sb->s_encoding, name, &qstr);
 }
 
 /**
-- 
2.43.0