ext4: Optimize case-insensitive lookups
Subsystems (2)
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. I got up to 30% speedup on lookups of large directories (>100k entries), depending on the length of the string under lookup.
v2:
- Dinamically allocate space for the casefolded version.
Signed-off-by Gabriel Krisman Bertazi <[email protected]>
--- fs/ext4/dir.c | 2 +- fs/ext4/ext4.h | 39 ++++++++++++++++++++++++++++++++++--- fs/ext4/namei.c | 43 ++++++++++++++++++++++++++++++++++++----- fs/unicode/utf8-core.c | 28 +++++++++++++++++++++++++++ include/linux/unicode.h | 3 +++ 5 files changed, 106 insertions(+), 9 deletions(-)
fs/ext4/dir.c +1 -1
@@ -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 +36 -3
@@ -2077,6 +2077,9 @@ struct ext4_filename {#ifdef CONFIG_FS_ENCRYPTION struct fscrypt_str crypto_buf;#endif +#ifdef CONFIG_UNICODE +struct fscrypt_str cf_name; +#endif };#define fname_name (p) ((p)->disk_name.name)
@@ -2302,6 +2305,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_fname_setup_ci_filename (struct inode *dir, +const struct qstr *iname, +struct fscrypt_str *fname); +#endif +#ifdef CONFIG_FS_ENCRYPTION static inline void ext4_fname_from_fscrypt_name (struct ext4_filename *dst,const struct fscrypt_name *src)
@@ -2328,6 +2337,10 @@ static inline int ext4_fname_setup_filename(struct inode *dir,return err;ext4_fname_from_fscrypt_name (fname, &name); + +#ifdef CONFIG_UNICODE +ext4_fname_setup_ci_filename (dir, iname, &fname->cf_name); +#endif return 0 ; }
@@ -2343,6 +2356,10 @@ static inline int ext4_fname_prepare_lookup(struct inode *dir,return err;ext4_fname_from_fscrypt_name (fname, &name); + +#ifdef CONFIG_UNICODE +ext4_fname_setup_ci_filename (dir, &dentry->d_name, &fname->cf_name); +#endif return 0 ; }
@@ -2356,6 +2373,11 @@ 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 +kfree (fname->cf_name.name); + fname->cf_name.name =NULL ; +#endif }#else /* !CONFIG_FS_ENCRYPTION */ static inline int ext4_fname_setup_filename(struct inode *dir,
@@ -2366,6 +2388,11 @@ static inline int ext4_fname_setup_filename(struct inode *dir, fname->usr_fname = iname; fname->disk_name.name = (unsigned char *) iname->name; fname->disk_name.len = iname->len; + +#ifdef CONFIG_UNICODE +ext4_fname_setup_ci_filename (dir, iname, &fname->cf_name); +#endif +return 0 ; }
@@ -2376,7 +2403,13 @@ static inline int ext4_fname_prepare_lookup(struct inode *dir, return ext4_fname_setup_filename(dir, &dentry->d_name, 1, fname); } -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 +kfree (fname->cf_name.name); + fname->cf_name.name =NULL ; +#endif +}#endif /* !CONFIG_FS_ENCRYPTION */ /* dir.c */
@@ -3119,8 +3152,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 12static const unsigned char ext4_type_by_mode[(S_IFMT >>S_SHIFT ) +1 ] = {
fs/ext4/namei.c +38 -5
71 lines not on this page · raw message
fs/unicode/utf8-core.c +28 -0
@@ -73,6 +73,34 @@ int utf8_strncasecmp(const struct unicode_map *um, }EXPORT_SYMBOL (utf8_strncasecmp); +/* String cf is expected to be a valid UTF-8 casefolded +* string. +*/ +int utf8_strncasecmp_folded (const struct unicode_map *um, +const struct qstr *cf, +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 = cf->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
@@ -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 *cf, +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
Quoted 9 lines · Gabriel Krisman Bertazi
Temporarily cache a casefolded version of the file name under lookup in
ext4_filename, to avoid repeatedly casefolding it. I got up to 30% speedup on lookups of large directories (>100k entries), depending on the length of the string under lookup.v2:
- Dinamically allocate space for the casefolded version.Signed-off-by Gabriel Krisman Bertazi <[email protected]>
Thanks, applied.
- Ted