drivers/staging/erofs/namei.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * linux/drivers/staging/erofs/namei.c
   4  *
   5  * Copyright (C) 2017-2018 HUAWEI, Inc.
   6  *             http://www.huawei.com/
   7  * Created by Gao Xiang <gaoxiang25@huawei.com>
   8  */
   9 #include "xattr.h"
  10
  11 #include <trace/events/erofs.h>
  12
  13 struct erofs_qstr {
  14         const unsigned char *name;
  15         const unsigned char *end;
  16 };
  17
  18 /* based on the end of qn is accurate and it must have the trailing '\0' */
  19 static inline int dirnamecmp(const struct erofs_qstr *qn,
  20                              const struct erofs_qstr *qd,
  21                              unsigned int *matched)
  22 {
  23         unsigned int i = *matched;
  24
  25         /*
  26          * on-disk error, let's only BUG_ON in the debugging mode.
  27          * otherwise, it will return 1 to just skip the invalid name
  28          * and go on (in consideration of the lookup performance).
  29          */
  30         DBG_BUGON(qd->name > qd->end);
  31
  32         /* qd could not have trailing '\0' */
  33         /* However it is absolutely safe if < qd->end */
  34         while (qd->name + i < qd->end && qd->name[i] != '\0') {
  35                 if (qn->name[i] != qd->name[i]) {
  36                         *matched = i;
  37                         return qn->name[i] > qd->name[i] ? 1 : -1;
  38                 }
  39                 ++i;
  40         }
  41         *matched = i;
  42         /* See comments in __d_alloc on the terminating NUL character */
  43         return qn->name[i] == '\0' ? 0 : 1;
  44 }
  45
  46 #define nameoff_from_disk(off, sz)      (le16_to_cpu(off) & ((sz) - 1))
  47
  48 static struct erofs_dirent *find_target_dirent(struct erofs_qstr *name,
  49                                                u8 *data,
  50                                                unsigned int dirblksize,
  51                                                const int ndirents)
  52 {
  53         int head, back;
  54         unsigned int startprfx, endprfx;
  55         struct erofs_dirent *const de = (struct erofs_dirent *)data;
  56
  57         /* since the 1st dirent has been evaluated previously */
  58         head = 1;
  59         back = ndirents - 1;
  60         startprfx = endprfx = 0;
  61
  62         while (head <= back) {
  63                 const int mid = head + (back - head) / 2;
  64                 const int nameoff = nameoff_from_disk(de[mid].nameoff,
  65                                                       dirblksize);
  66                 unsigned int matched = min(startprfx, endprfx);
  67                 struct erofs_qstr dname = {
  68                         .name = data + nameoff,
  69                         .end = unlikely(mid >= ndirents - 1) ?
  70                                 data + dirblksize :
  71                                 data + nameoff_from_disk(de[mid + 1].nameoff,
  72                                                          dirblksize)
  73                 };
  74
  75                 /* string comparison without already matched prefix */
  76                 int ret = dirnamecmp(name, &dname, &matched);
  77
  78                 if (unlikely(!ret)) {
  79                         return de + mid;
  80                 } else if (ret > 0) {
  81                         head = mid + 1;
  82                         startprfx = matched;
  83                 } else {
  84                         back = mid - 1;
  85                         endprfx = matched;
  86                 }
  87         }
  88
  89         return ERR_PTR(-ENOENT);
  90 }
  91
  92 static struct page *find_target_block_classic(struct inode *dir,
  93                                               struct erofs_qstr *name,
  94                                               int *_ndirents)
  95 {
  96         unsigned int startprfx, endprfx;
  97         int head, back;
  98         struct address_space *const mapping = dir->i_mapping;
  99         struct page *candidate = ERR_PTR(-ENOENT);
 100
 101         startprfx = endprfx = 0;
 102         head = 0;
 103         back = inode_datablocks(dir) - 1;
 104
 105         while (head <= back) {
 106                 const int mid = head + (back - head) / 2;
 107                 struct page *page = read_mapping_page(mapping, mid, NULL);
 108
 109                 if (!IS_ERR(page)) {
 110                         struct erofs_dirent *de = kmap_atomic(page);
 111                         const int nameoff = nameoff_from_disk(de->nameoff,
 112                                                               EROFS_BLKSIZ);
 113                         const int ndirents = nameoff / sizeof(*de);
 114                         int diff;
 115                         unsigned int matched;
 116                         struct erofs_qstr dname;
 117
 118                         if (unlikely(!ndirents)) {
 119                                 kunmap_atomic(de);
 120                                 put_page(page);
 121                                 errln("corrupted dir block %d @ nid %llu",
 122                                       mid, EROFS_V(dir)->nid);
 123                                 DBG_BUGON(1);
 124                                 page = ERR_PTR(-EFSCORRUPTED);
 125                                 goto out;
 126                         }
 127
 128                         matched = min(startprfx, endprfx);
 129
 130                         dname.name = (u8 *)de + nameoff;
 131                         if (ndirents == 1)
 132                                 dname.end = (u8 *)de + EROFS_BLKSIZ;
 133                         else
 134                                 dname.end = (u8 *)de +
 135                                         nameoff_from_disk(de[1].nameoff,
 136                                                           EROFS_BLKSIZ);
 137
 138                         /* string comparison without already matched prefix */
 139                         diff = dirnamecmp(name, &dname, &matched);
 140                         kunmap_atomic(de);
 141
 142                         if (unlikely(!diff)) {
 143                                 *_ndirents = 0;
 144                                 goto out;
 145                         } else if (diff > 0) {
 146                                 head = mid + 1;
 147                                 startprfx = matched;
 148
 149                                 if (!IS_ERR(candidate))
 150                                         put_page(candidate);
 151                                 candidate = page;
 152                                 *_ndirents = ndirents;
 153                         } else {
 154                                 put_page(page);
 155
 156                                 back = mid - 1;
 157                                 endprfx = matched;
 158                         }
 159                         continue;
 160                 }
 161 out:            /* free if the candidate is valid */
 162                 if (!IS_ERR(candidate))
 163                         put_page(candidate);
 164                 return page;
 165         }
 166         return candidate;
 167 }
 168
 169 int erofs_namei(struct inode *dir,
 170                 struct qstr *name,
 171                 erofs_nid_t *nid, unsigned int *d_type)
 172 {
 173         int ndirents;
 174         struct page *page;
 175         void *data;
 176         struct erofs_dirent *de;
 177         struct erofs_qstr qn;
 178
 179         if (unlikely(!dir->i_size))
 180                 return -ENOENT;
 181
 182         qn.name = name->name;
 183         qn.end = name->name + name->len;
 184
 185         ndirents = 0;
 186         page = find_target_block_classic(dir, &qn, &ndirents);
 187
 188         if (IS_ERR(page))
 189                 return PTR_ERR(page);
 190
 191         data = kmap_atomic(page);
 192         /* the target page has been mapped */
 193         if (ndirents)
 194                 de = find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents);
 195         else
 196                 de = (struct erofs_dirent *)data;
 197
 198         if (!IS_ERR(de)) {
 199                 *nid = le64_to_cpu(de->nid);
 200                 *d_type = de->file_type;
 201         }
 202
 203         kunmap_atomic(data);
 204         put_page(page);
 205
 206         return PTR_ERR_OR_ZERO(de);
 207 }
 208
 209 /* NOTE: i_mutex is already held by vfs */
 210 static struct dentry *erofs_lookup(struct inode *dir,
 211                                    struct dentry *dentry,
 212                                    unsigned int flags)
 213 {
 214         int err;
 215         erofs_nid_t nid;
 216         unsigned int d_type;
 217         struct inode *inode;
 218
 219         DBG_BUGON(!d_really_is_negative(dentry));
 220         /* dentry must be unhashed in lookup, no need to worry about */
 221         DBG_BUGON(!d_unhashed(dentry));
 222
 223         trace_erofs_lookup(dir, dentry, flags);
 224
 225         /* file name exceeds fs limit */
 226         if (unlikely(dentry->d_name.len > EROFS_NAME_LEN))
 227                 return ERR_PTR(-ENAMETOOLONG);
 228
 229         /* false uninitialized warnings on gcc 4.8.x */
 230         err = erofs_namei(dir, &dentry->d_name, &nid, &d_type);
 231
 232         if (err == -ENOENT) {
 233                 /* negative dentry */
 234                 inode = NULL;
 235         } else if (unlikely(err)) {
 236                 inode = ERR_PTR(err);
 237         } else {
 238                 debugln("%s, %s (nid %llu) found, d_type %u", __func__,
 239                         dentry->d_name.name, nid, d_type);
 240                 inode = erofs_iget(dir->i_sb, nid, d_type == FT_DIR);
 241         }
 242         return d_splice_alias(inode, dentry);
 243 }
 244
 245 const struct inode_operations erofs_dir_iops = {
 246         .lookup = erofs_lookup,
 247         .getattr = erofs_getattr,
 248 #ifdef CONFIG_EROFS_FS_XATTR
 249         .listxattr = erofs_listxattr,
 250 #endif
 251         .get_acl = erofs_get_acl,
 252 };
 253