fs/erofs/namei.c

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