optimize-case-insensitive-lookups

   1 ext4: optimize case-insensitive lookups
   2
   3 From: Gabriel Krisman Bertazi <krisman@collabora.com>
   4
   5 Temporarily cache a casefolded version of the file name under lookup in
   6 ext4_filename, to avoid repeatedly casefolding it.  I got up to 30%
   7 speedup on lookups of large directories (>100k entries), depending on
   8 the length of the string under lookup.
   9
  10 Signed-off-by: Gabriel Krisman Bertazi <krisman@collabora.com>
  11 Signed-off-by: Theodore Ts'o <tytso@mit.edu>
  12 ---
  13  fs/ext4/dir.c           |  2 +-
  14  fs/ext4/ext4.h          | 39 ++++++++++++++++++++++++++++++++++---
  15  fs/ext4/namei.c         | 43 ++++++++++++++++++++++++++++++++++++-----
  16  fs/unicode/utf8-core.c  | 28 +++++++++++++++++++++++++++
  17  include/linux/unicode.h |  3 +++
  18  5 files changed, 106 insertions(+), 9 deletions(-)
  19
  20 diff --git a/fs/ext4/dir.c b/fs/ext4/dir.c
  21 index c7843b149a1e..0a427e18584a 100644
  22 --- a/fs/ext4/dir.c
  23 +++ b/fs/ext4/dir.c
  24 @@ -674,7 +674,7 @@ static int ext4_d_compare(const struct dentry *dentry, unsigned int len,
  25                 return memcmp(str, name->name, len);
  26         }
  27
  28 -       return ext4_ci_compare(dentry->d_parent->d_inode, name, &qstr);
  29 +       return ext4_ci_compare(dentry->d_parent->d_inode, name, &qstr, false);
  30  }
  31
  32  static int ext4_d_hash(const struct dentry *dentry, struct qstr *str)
  33 diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
  34 index 1cb67859e051..c0793d9e5d12 100644
  35 --- a/fs/ext4/ext4.h
  36 +++ b/fs/ext4/ext4.h
  37 @@ -2077,6 +2077,9 @@ struct ext4_filename {
  38  #ifdef CONFIG_FS_ENCRYPTION
  39         struct fscrypt_str crypto_buf;
  40  #endif
  41 +#ifdef CONFIG_UNICODE
  42 +       struct fscrypt_str cf_name;
  43 +#endif
  44  };
  45
  46  #define fname_name(p) ((p)->disk_name.name)
  47 @@ -2302,6 +2305,12 @@ extern unsigned ext4_free_clusters_after_init(struct super_block *sb,
  48                                               struct ext4_group_desc *gdp);
  49  ext4_fsblk_t ext4_inode_to_goal_block(struct inode *);
  50
  51 +#ifdef CONFIG_UNICODE
  52 +extern void ext4_fname_setup_ci_filename(struct inode *dir,
  53 +                                        const struct qstr *iname,
  54 +                                        struct fscrypt_str *fname);
  55 +#endif
  56 +
  57  #ifdef CONFIG_FS_ENCRYPTION
  58  static inline void ext4_fname_from_fscrypt_name(struct ext4_filename *dst,
  59                                                 const struct fscrypt_name *src)
  60 @@ -2328,6 +2337,10 @@ static inline int ext4_fname_setup_filename(struct inode *dir,
  61                 return err;
  62
  63         ext4_fname_from_fscrypt_name(fname, &name);
  64 +
  65 +#ifdef CONFIG_UNICODE
  66 +       ext4_fname_setup_ci_filename(dir, iname, &fname->cf_name);
  67 +#endif
  68         return 0;
  69  }
  70
  71 @@ -2343,6 +2356,10 @@ static inline int ext4_fname_prepare_lookup(struct inode *dir,
  72                 return err;
  73
  74         ext4_fname_from_fscrypt_name(fname, &name);
  75 +
  76 +#ifdef CONFIG_UNICODE
  77 +       ext4_fname_setup_ci_filename(dir, &dentry->d_name, &fname->cf_name);
  78 +#endif
  79         return 0;
  80  }
  81
  82 @@ -2356,6 +2373,11 @@ static inline void ext4_fname_free_filename(struct ext4_filename *fname)
  83         fname->crypto_buf.name = NULL;
  84         fname->usr_fname = NULL;
  85         fname->disk_name.name = NULL;
  86 +
  87 +#ifdef CONFIG_UNICODE
  88 +       kfree(fname->cf_name.name);
  89 +       fname->cf_name.name = NULL;
  90 +#endif
  91  }
  92  #else /* !CONFIG_FS_ENCRYPTION */
  93  static inline int ext4_fname_setup_filename(struct inode *dir,
  94 @@ -2366,6 +2388,11 @@ static inline int ext4_fname_setup_filename(struct inode *dir,
  95         fname->usr_fname = iname;
  96         fname->disk_name.name = (unsigned char *) iname->name;
  97         fname->disk_name.len = iname->len;
  98 +
  99 +#ifdef CONFIG_UNICODE
 100 +       ext4_fname_setup_ci_filename(dir, iname, &fname->cf_name);
 101 +#endif
 102 +
 103         return 0;
 104  }
 105
 106 @@ -2376,7 +2403,13 @@ static inline int ext4_fname_prepare_lookup(struct inode *dir,
 107         return ext4_fname_setup_filename(dir, &dentry->d_name, 1, fname);
 108  }
 109
 110 -static inline void ext4_fname_free_filename(struct ext4_filename *fname) { }
 111 +static inline void ext4_fname_free_filename(struct ext4_filename *fname)
 112 +{
 113 +#ifdef CONFIG_UNICODE
 114 +       kfree(fname->cf_name.name);
 115 +       fname->cf_name.name = NULL;
 116 +#endif
 117 +}
 118  #endif /* !CONFIG_FS_ENCRYPTION */
 119
 120  /* dir.c */
 121 @@ -3119,8 +3152,8 @@ extern int ext4_handle_dirty_dirent_node(handle_t *handle,
 122                                          struct inode *inode,
 123                                          struct buffer_head *bh);
 124  extern int ext4_ci_compare(const struct inode *parent,
 125 -                          const struct qstr *name,
 126 -                          const struct qstr *entry);
 127 +                          const struct qstr *fname,
 128 +                          const struct qstr *entry, bool quick);
 129
 130  #define S_SHIFT 12
 131  static const unsigned char ext4_type_by_mode[(S_IFMT >> S_SHIFT) + 1] = {
 132 diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
 133 index cd01c4a67ffb..4909ced4e672 100644
 134 --- a/fs/ext4/namei.c
 135 +++ b/fs/ext4/namei.c
 136 @@ -1259,19 +1259,24 @@ static void dx_insert_block(struct dx_frame *frame, u32 hash, ext4_lblk_t block)
 137  #ifdef CONFIG_UNICODE
 138  /*
 139   * Test whether a case-insensitive directory entry matches the filename
 140 - * being searched for.
 141 + * being searched for.  If quick is set, assume the name being looked up
 142 + * is already in the casefolded form.
 143   *
 144   * Returns: 0 if the directory entry matches, more than 0 if it
 145   * doesn't match or less than zero on error.
 146   */
 147  int ext4_ci_compare(const struct inode *parent, const struct qstr *name,
 148 -                   const struct qstr *entry)
 149 +                   const struct qstr *entry, bool quick)
 150  {
 151         const struct ext4_sb_info *sbi = EXT4_SB(parent->i_sb);
 152         const struct unicode_map *um = sbi->s_encoding;
 153         int ret;
 154
 155 -       ret = utf8_strncasecmp(um, name, entry);
 156 +       if (quick)
 157 +               ret = utf8_strncasecmp_folded(um, name, entry);
 158 +       else
 159 +               ret = utf8_strncasecmp(um, name, entry);
 160 +
 161         if (ret < 0) {
 162                 /* Handle invalid character sequence as either an error
 163                  * or as an opaque byte sequence.
 164 @@ -1287,6 +1292,27 @@ int ext4_ci_compare(const struct inode *parent, const struct qstr *name,
 165
 166         return ret;
 167  }
 168 +
 169 +void ext4_fname_setup_ci_filename(struct inode *dir, const struct qstr *iname,
 170 +                                 struct fscrypt_str *cf_name)
 171 +{
 172 +       if (!IS_CASEFOLDED(dir)) {
 173 +               cf_name->name = NULL;
 174 +               return;
 175 +       }
 176 +
 177 +       cf_name->name = kmalloc(EXT4_NAME_LEN, GFP_NOFS);
 178 +       if (!cf_name->name)
 179 +               return;
 180 +
 181 +       cf_name->len = utf8_casefold(EXT4_SB(dir->i_sb)->s_encoding,
 182 +                                    iname, cf_name->name,
 183 +                                    EXT4_NAME_LEN);
 184 +       if (cf_name->len <= 0) {
 185 +               kfree(cf_name->name);
 186 +               cf_name->name = NULL;
 187 +       }
 188 +}
 189  #endif
 190
 191  /*
 192 @@ -1313,8 +1339,15 @@ static inline bool ext4_match(const struct inode *parent,
 193  #endif
 194
 195  #ifdef CONFIG_UNICODE
 196 -       if (EXT4_SB(parent->i_sb)->s_encoding && IS_CASEFOLDED(parent))
 197 -               return (ext4_ci_compare(parent, fname->usr_fname, &entry) == 0);
 198 +       if (EXT4_SB(parent->i_sb)->s_encoding && IS_CASEFOLDED(parent)) {
 199 +               if (fname->cf_name.name) {
 200 +                       struct qstr cf = {.name = fname->cf_name.name,
 201 +                                         .len = fname->cf_name.len};
 202 +                       return !ext4_ci_compare(parent, &cf, &entry, true);
 203 +               }
 204 +               return !ext4_ci_compare(parent, fname->usr_fname, &entry,
 205 +                                       false);
 206 +       }
 207  #endif
 208
 209         return fscrypt_match_name(&f, de->name, de->name_len);
 210 diff --git a/fs/unicode/utf8-core.c b/fs/unicode/utf8-core.c
 211 index 6afab4fdce90..71ca4d047d65 100644
 212 --- a/fs/unicode/utf8-core.c
 213 +++ b/fs/unicode/utf8-core.c
 214 @@ -73,6 +73,34 @@ int utf8_strncasecmp(const struct unicode_map *um,
 215  }
 216  EXPORT_SYMBOL(utf8_strncasecmp);
 217
 218 +/* String cf is expected to be a valid UTF-8 casefolded
 219 + * string.
 220 + */
 221 +int utf8_strncasecmp_folded(const struct unicode_map *um,
 222 +                           const struct qstr *cf,
 223 +                           const struct qstr *s1)
 224 +{
 225 +       const struct utf8data *data = utf8nfdicf(um->version);
 226 +       struct utf8cursor cur1;
 227 +       int c1, c2;
 228 +       int i = 0;
 229 +
 230 +       if (utf8ncursor(&cur1, data, s1->name, s1->len) < 0)
 231 +               return -EINVAL;
 232 +
 233 +       do {
 234 +               c1 = utf8byte(&cur1);
 235 +               c2 = cf->name[i++];
 236 +               if (c1 < 0)
 237 +                       return -EINVAL;
 238 +               if (c1 != c2)
 239 +                       return 1;
 240 +       } while (c1);
 241 +
 242 +       return 0;
 243 +}
 244 +EXPORT_SYMBOL(utf8_strncasecmp_folded);
 245 +
 246  int utf8_casefold(const struct unicode_map *um, const struct qstr *str,
 247                   unsigned char *dest, size_t dlen)
 248  {
 249 diff --git a/include/linux/unicode.h b/include/linux/unicode.h
 250 index aec2c6d800aa..990aa97d8049 100644
 251 --- a/include/linux/unicode.h
 252 +++ b/include/linux/unicode.h
 253 @@ -17,6 +17,9 @@ int utf8_strncmp(const struct unicode_map *um,
 254
 255  int utf8_strncasecmp(const struct unicode_map *um,
 256                  const struct qstr *s1, const struct qstr *s2);
 257 +int utf8_strncasecmp_folded(const struct unicode_map *um,
 258 +                           const struct qstr *cf,
 259 +                           const struct qstr *s1);
 260
 261  int utf8_normalize(const struct unicode_map *um, const struct qstr *str,
 262                    unsigned char *dest, size_t dlen);
 263 --
 264 2.20.1
 265
 266