Try exact-match comparison ahead of case-insensitive match
v3 cover Try exact-match comparison ahead of case-insensitive match
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(-)
Signature · 1 line
2.43.0
PATCH v3 1/2 dcache: Expose dentry_string_cmp outside of dcache
In preparation to call these from libfs, expose dentry_string_cmp in the header file.
--- fs/dcache.c | 53 ------------------------------------------ include/linux/dcache.h | 53 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 53 insertions(+), 53 deletions(-)
fs/dcache.c +0 -53
@@ -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) {/*
include/linux/dcache.h +53 -0
57 lines not on this page · raw message
Signature · 1 line
2.43.0
Re: [PATCH v3 1/2] dcache: Expose dentry_string_cmp outside of dcache
Quoted 3 lines · Gabriel Krisman Bertazi
In preparation to call these from libfs, expose
dentry_string_cmpin 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
Quoted 7 lines · Linus Torvalds
Quoted 3 lines · Gabriel Krisman Bertazi
In preparation to call these from libfs, expose
dentry_string_cmpin the header file.Let's not make these header files bigger and more complex.
Quoted 7 lines
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.
Quoted 6 lines
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,
Signature · 1 line
Gabriel Krisman Bertazi
Re: [PATCH v3 1/2] dcache: Expose dentry_string_cmp outside of dcache
Quoted 3 lines · Gabriel Krisman Bertazi
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 1/1 libfs: Attempt exact-match comparison first during casefolded lookup
Quoted 7 lines · Linus Torvalds
Quoted 3 lines · Gabriel Krisman Bertazi
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.
Quoted 3 lines
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.
--- fs/libfs.c | 40 +++++++++++++++++++++++----------------- 1 file changed, 23 insertions(+), 17 deletions(-)
fs/libfs.c +23 -17
@@ -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); }/**
Signature · 1 line
2.43.0
Re: [PATCH v4] libfs: Attempt exact-match comparison first during casefolded lookup
Quoted 4 lines · Gabriel Krisman Bertazi
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:
fs/libfs.c static int generic_ci_d_compare(const struct dentry *dentry, unsigned int len, · line 1741
Quoted 7 lines
if (len <= DNAME_INLINE_LEN - 1) { memcpy(strbuf, str, len); strbuf[len] = 0;fs/libfs.c +1
-1- 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
Hi Linus,
Quoted 43 lines · Linus Torvalds
Quoted 4 lines · Gabriel Krisman Bertazi
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:
fs/libfs.c static int generic_ci_d_compare(const struct dentry *dentry, unsigned int len, · line 1741
Quoted 7 lines
if (len <= DNAME_INLINE_LEN - 1) { memcpy(strbuf, str, len); strbuf[len] = 0;fs/libfs.c +1
-1- 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: avoidutf8_strncasecmp()with unstable name")fc3bb095ab02("f2fs: avoidutf8_strncasecmp()with unstable name")
Quoted 9 lines
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/[email protected]/.
- Eric
PATCH v3 2/2 libfs: Attempt exact-match comparison first during casefold lookup
In reply to Gabriel Krisman BertaziCasefolded 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.
---
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(-)
fs/libfs.c +22 -17
@@ -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); }/**
Signature · 1 line
2.43.0