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