Skip to contentSkip to conversation

ext4: Optimize case-insensitive lookups

PATCH In review Gabriel Krisman Bertazi 2 participants 3 messages May 29, 2019 – May 31, 2019

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 ext4: Optimize case-insensitive lookups

Temporarily cache a casefolded version of the file name under lookup in ext4_filename, to avoid repeatedly casefolding it.

This gives me some performance gains on the lookup patch, when performing cold dcache case-insensitive lookups on directories with a high number of entries.

Below is a measure of average speedup of several runs with the patch applied; where the baseline is the currently ext4 code, and the rows are for different number of directory entries/number of lookup performed. The speedup is not linear with the number of dentries, which I believe is because of the changing format of the htree.

| entries | avg speedup |
| 1000    |  1.15	|
| 10000   |  1.19	|
| 50000   |  1.25	|
| 70000   |  1.20	|
| 100000  |  1.13	|
---
 fs/ext4/dir.c           |  2 +-
 fs/ext4/ext4.h          | 32 +++++++++++++++++++++++++++++---
 fs/ext4/namei.c         | 41 +++++++++++++++++++++++++++++++++++------
 fs/unicode/utf8-core.c  | 25 +++++++++++++++++++++++++
 include/linux/unicode.h |  3 +++
 5 files changed, 93 insertions(+), 10 deletions(-)
fs/ext4/dir.c +1 -1
index c7843b149a1e..0a427e18584a 100644
@@ -674,7 +674,7 @@ static int ext4_d_compare(const struct dentry *dentry, unsigned int len,
 		return memcmp(str, name->name, len);
 	}
 
-	return ext4_ci_compare(dentry->d_parent->d_inode, name, &qstr);
+	return ext4_ci_compare(dentry->d_parent->d_inode, name, &qstr, false);
 }
 
 static int ext4_d_hash(const struct dentry *dentry, struct qstr *str)
fs/ext4/ext4.h +29 -3
index c18ab748d20d..e3809cfda9f4 100644
@@ -2078,6 +2078,10 @@ struct ext4_filename {
 #ifdef CONFIG_FS_ENCRYPTION
 	struct fscrypt_str crypto_buf;
 #endif
+#ifdef CONFIG_UNICODE
+	int cf_len;
+	unsigned char cf_name[EXT4_NAME_LEN];
+#endif
 };
 
 #define fname_name(p) ((p)->disk_name.name)
@@ -2303,6 +2307,12 @@ extern unsigned ext4_free_clusters_after_init(struct super_block *sb,
 					      struct ext4_group_desc *gdp);
 ext4_fsblk_t ext4_inode_to_goal_block(struct inode *);
 
+#ifdef CONFIG_UNICODE
+extern void ext4_setup_ci_filename(struct inode *dir,
+				   const struct qstr *iname,
+				   struct ext4_filename *fname);
+#endif
+
 #ifdef CONFIG_FS_ENCRYPTION
 static inline int ext4_fname_setup_filename(struct inode *dir,
 			const struct qstr *iname,
@@ -2313,6 +2323,9 @@ static inline int ext4_fname_setup_filename(struct inode *dir,
 
 	memset(fname, 0, sizeof(struct ext4_filename));
 
+#ifdef CONFIG_UNICODE
+	ext4_setup_ci_filename(dir, iname, fname);
+#endif
 	err = fscrypt_setup_filename(dir, iname, lookup, &name);
 
 	fname->usr_fname = name.usr_fname;
@@ -2333,18 +2346,31 @@ static inline void ext4_fname_free_filename(struct ext4_filename *fname)
 	fname->crypto_buf.name = NULL;
 	fname->usr_fname = NULL;
 	fname->disk_name.name = NULL;
+#ifdef CONFIG_UNICODE
+	fname->cf_len = 0;
+#endif
 }
 #else
 static inline int ext4_fname_setup_filename(struct inode *dir,
 		const struct qstr *iname,
 		int lookup, struct ext4_filename *fname)
 {
+
+#ifdef CONFIG_UNICODE
+	ext4_setup_ci_filename(dir, iname, fname);
+#endif
 	fname->usr_fname = iname;
 	fname->disk_name.name = (unsigned char *) iname->name;
 	fname->disk_name.len = iname->len;
 	return 0;
 }
-static inline void ext4_fname_free_filename(struct ext4_filename *fname) { }
+
+static inline void ext4_fname_free_filename(struct ext4_filename *fname)
+{
+#ifdef CONFIG_UNICODE
+	fname->cf_len = 0;
+#endif
+}
 
 #endif
 
@@ -3088,8 +3114,8 @@ extern int ext4_handle_dirty_dirent_node(handle_t *handle,
 					 struct inode *inode,
 					 struct buffer_head *bh);
 extern int ext4_ci_compare(const struct inode *parent,
-			   const struct qstr *name,
-			   const struct qstr *entry);
+			   const struct qstr *fname,
+			   const struct qstr *entry, bool quick);
 
 #define S_SHIFT 12
 static const unsigned char ext4_type_by_mode[(S_IFMT >> S_SHIFT) + 1] = {
fs/ext4/namei.c +35 -6

68 lines not on this page · raw message

fs/unicode/utf8-core.c +25 -0
index 6afab4fdce90..1d74de2778e9 100644
@@ -73,6 +73,31 @@ int utf8_strncasecmp(const struct unicode_map *um,
 }
 EXPORT_SYMBOL(utf8_strncasecmp);
 
+int utf8_strncasecmp_folded(const struct unicode_map *um,
+			    const struct qstr *normalized,
+			    const struct qstr *s1)
+{
+	const struct utf8data *data = utf8nfdicf(um->version);
+	struct utf8cursor cur1;
+	int c1, c2;
+	int i = 0;
+
+	if (utf8ncursor(&cur1, data, s1->name, s1->len) < 0)
+		return -EINVAL;
+
+	do {
+		c1 = utf8byte(&cur1);
+		c2 = normalized->name[i++];
+		if (c1 < 0)
+			return -EINVAL;
+		if (c1 != c2)
+			return 1;
+	} while (c1);
+
+	return 0;
+}
+EXPORT_SYMBOL(utf8_strncasecmp_folded);
+
 int utf8_casefold(const struct unicode_map *um, const struct qstr *str,
 		  unsigned char *dest, size_t dlen)
 {
include/linux/unicode.h +3 -0
index aec2c6d800aa..e89bf3ecef21 100644
@@ -17,6 +17,9 @@ int utf8_strncmp(const struct unicode_map *um,
 
 int utf8_strncasecmp(const struct unicode_map *um,
 		 const struct qstr *s1, const struct qstr *s2);
+int utf8_strncasecmp_folded(const struct unicode_map *um,
+			    const struct qstr *normalized,
+			    const struct qstr *s1);
 
 int utf8_normalize(const struct unicode_map *um, const struct qstr *str,
 		   unsigned char *dest, size_t dlen);
Signature · 1 line
2.20.1
maintainer
#1 lore raw
Quoted 5 lines · Gabriel Krisman Bertazi
fs/ext4/ext4.h +0 -0
index c18ab748d20d..e3809cfda9f4 100644

fs/ext4/ext4.h struct ext4_filename { · line 2087

Quoted 10 lines
fs/ext4/ext4.h +4 -0
@@ -2078,6 +2078,10 @@ struct ext4_filename {
 #ifdef CONFIG_FS_ENCRYPTION
 	struct fscrypt_str crypto_buf;
 #endif
+#ifdef CONFIG_UNICODE
+	int cf_len;
+	unsigned char cf_name[EXT4_NAME_LEN];
+#endif
 };
 
 #define fname_name(p) ((p)->disk_name.name)

EXT4_NAME_LEN is 256, and struct ext4_filename is allocated on the stack. So this is going to increase the stack usage by 258 bytes. Perhaps should we just kmalloc the temporary buffer when it's needed?

The other thing that this patch reminds me is that there is great interest in supporting case folded directories and fscrypt at the same time. Today fscrypt works by encrypting the filename, and stashes it in fname->crypto_buf, and this allows for a byte-for-byte comparison of the encrypted name. To support fscrypt && casefold, what we would need to do is to change the htree hash so that the hash is caluclated on the normalized form, and then we'll have to decrypt each filename in the directory block and then compare it against the normalized form that stashed in cf_name. So that means we'll never need to allocate memory for cf_name and crypto_buf at the same time.

We can also use struct fscrypt_str for cf_name; it's defined as a combined unsighed char *name and u32 len. We already use fscrypt_str even the !CONFIG_FS_ENCRYPTION case, since it's a convenient way of handling a non-NULL terminated filename blob. And this will hopefully make it simpler to deal with integrating casefolding and fscrypt in the future.

Cheers,

- Ted

#2 lore raw
Quoted 15 lines · Theodore Ts'o
Quoted 14 lines · Gabriel Krisman Bertazi
fs/ext4/ext4.h +4 -0
index c18ab748d20d..e3809cfda9f4 100644
@@ -2078,6 +2078,10 @@ struct ext4_filename {
 #ifdef CONFIG_FS_ENCRYPTION
 	struct fscrypt_str crypto_buf;
 #endif
+#ifdef CONFIG_UNICODE
+	int cf_len;
+	unsigned char cf_name[EXT4_NAME_LEN];
+#endif
 };
 
Quoted 5 lines

fs/ext4/ext4.h struct ext4_filename { · line 2087

Quoted 1 line
fs/ext4/ext4.h +0 -0
 #define fname_name(p) ((p)->disk_name.name)

EXT4_NAME_LEN is 256, and struct ext4_filename is allocated on the stack. So this is going to increase the stack usage by 258 bytes. Perhaps should we just kmalloc the temporary buffer when it's needed?

I wanted to avoid adding an allocation to this path, but maybe that was misguided, since this is out of the dcache critical path. I also wanted to remove the allocation from d_hash, but we'd require a similar size allocation in the stack. Is that a good idea?

Quoted 10 lines

The other thing that this patch reminds me is that there is great interest in supporting case folded directories and fscrypt at the same time. Today fscrypt works by encrypting the filename, and stashes it in fname->crypto_buf, and this allows for a byte-for-byte comparison of the encrypted name. To support fscrypt && casefold, what we would need to do is to change the htree hash so that the hash is caluclated on the normalized form, and then we'll have to decrypt each filename in the directory block and then compare it against the normalized form that stashed in cf_name. So that means we'll never need to allocate memory for cf_name and crypto_buf at the same time.

fscrypt and case-insensitive is getting to the top of my to-do list, i'll something there early next week. Thanks for the explanation on it.

Quoted 7 lines

We can also use struct fscrypt_str for cf_name; it's defined as a combined unsighed char *name and u32 len. We already use fscrypt_str even the !CONFIG_FS_ENCRYPTION case, since it's a convenient way of handling a non-NULL terminated filename blob. And this will hopefully make it simpler to deal with integrating casefolding and fscrypt in the future.

I will send a v2 with this change already, to simplify fscrypt+casefolding support.

Quoted 4 lines

Cheers,

- Ted

Signature · 1 line
Gabriel Krisman Bertazi