LXR linux/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 */
   6#include "xattr.h"
   7
   8#include <trace/events/erofs.h>
   9
  10struct 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' */
  16static 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
  45static 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
  89static struct page *find_target_block_classic(struct inode *dir,
  90                                              struct erofs_qstr *name,
  91                                              int *_ndirents)
  92{
  93        unsigned int startprfx, endprfx;
  94        int head, back;
  95        struct address_space *const mapping = dir->i_mapping;
  96        struct page *candidate = ERR_PTR(-ENOENT);
  97
  98        startprfx = endprfx = 0;
  99        head = 0;
 100        back = erofs_inode_datablocks(dir) - 1;
 101
 102        while (head <= back) {
 103                const int mid = head + (back - head) / 2;
 104                struct page *page = read_mapping_page(mapping, mid, NULL);
 105
 106                if (!IS_ERR(page)) {
 107                        struct erofs_dirent *de = kmap_atomic(page);
 108                        const int nameoff = nameoff_from_disk(de->nameoff,
 109                                                              EROFS_BLKSIZ);
 110                        const int ndirents = nameoff / sizeof(*de);
 111                        int diff;
 112                        unsigned int matched;
 113                        struct erofs_qstr dname;
 114
 115                        if (!ndirents) {
 116                                kunmap_atomic(de);
 117                                put_page(page);
 118                                erofs_err(dir->i_sb,
 119                                          "corrupted dir block %d @ nid %llu",
 120                                          mid, EROFS_I(dir)->nid);
 121                                DBG_BUGON(1);
 122                                page = ERR_PTR(-EFSCORRUPTED);
 123                                goto out;
 124                        }
 125
 126                        matched = min(startprfx, endprfx);
 127
 128                        dname.name = (u8 *)de + nameoff;
 129                        if (ndirents == 1)
 130                                dname.end = (u8 *)de + EROFS_BLKSIZ;
 131                        else
 132                                dname.end = (u8 *)de +
 133                                        nameoff_from_disk(de[1].nameoff,
 134                                                          EROFS_BLKSIZ);
 135
 136                        /* string comparison without already matched prefix */
 137                        diff = erofs_dirnamecmp(name, &dname, &matched);
 138                        kunmap_atomic(de);
 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                                        put_page(candidate);
 149                                candidate = page;
 150                                *_ndirents = ndirents;
 151                        } else {
 152                                put_page(page);
 153
 154                                back = mid - 1;
 155                                endprfx = matched;
 156                        }
 157                        continue;
 158                }
 159out:            /* free if the candidate is valid */
 160                if (!IS_ERR(candidate))
 161                        put_page(candidate);
 162                return page;
 163        }
 164        return candidate;
 165}
 166
 167int erofs_namei(struct inode *dir,
 168                struct qstr *name,
 169                erofs_nid_t *nid, unsigned int *d_type)
 170{
 171        int ndirents;
 172        struct page *page;
 173        void *data;
 174        struct erofs_dirent *de;
 175        struct erofs_qstr qn;
 176
 177        if (!dir->i_size)
 178                return -ENOENT;
 179
 180        qn.name = name->name;
 181        qn.end = name->name + name->len;
 182
 183        ndirents = 0;
 184        page = find_target_block_classic(dir, &qn, &ndirents);
 185
 186        if (IS_ERR(page))
 187                return PTR_ERR(page);
 188
 189        data = kmap_atomic(page);
 190        /* the target page has been mapped */
 191        if (ndirents)
 192                de = find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents);
 193        else
 194                de = (struct erofs_dirent *)data;
 195
 196        if (!IS_ERR(de)) {
 197                *nid = le64_to_cpu(de->nid);
 198                *d_type = de->file_type;
 199        }
 200
 201        kunmap_atomic(data);
 202        put_page(page);
 203
 204        return PTR_ERR_OR_ZERO(de);
 205}
 206
 207/* NOTE: i_mutex is already held by vfs */
 208static struct dentry *erofs_lookup(struct inode *dir,
 209                                   struct dentry *dentry,
 210                                   unsigned int flags)
 211{
 212        int err;
 213        erofs_nid_t nid;
 214        unsigned int d_type;
 215        struct inode *inode;
 216
 217        DBG_BUGON(!d_really_is_negative(dentry));
 218        /* dentry must be unhashed in lookup, no need to worry about */
 219        DBG_BUGON(!d_unhashed(dentry));
 220
 221        trace_erofs_lookup(dir, dentry, flags);
 222
 223        /* file name exceeds fs limit */
 224        if (dentry->d_name.len > EROFS_NAME_LEN)
 225                return ERR_PTR(-ENAMETOOLONG);
 226
 227        /* false uninitialized warnings on gcc 4.8.x */
 228        err = erofs_namei(dir, &dentry->d_name, &nid, &d_type);
 229
 230        if (err == -ENOENT) {
 231                /* negative dentry */
 232                inode = NULL;
 233        } else if (err) {
 234                inode = ERR_PTR(err);
 235        } else {
 236                erofs_dbg("%s, %pd (nid %llu) found, d_type %u", __func__,
 237                          dentry, nid, d_type);
 238                inode = erofs_iget(dir->i_sb, nid, d_type == FT_DIR);
 239        }
 240        return d_splice_alias(inode, dentry);
 241}
 242
 243const struct inode_operations erofs_dir_iops = {
 244        .lookup = erofs_lookup,
 245        .getattr = erofs_getattr,
 246        .listxattr = erofs_listxattr,
 247        .get_acl = erofs_get_acl,
 248        .fiemap = erofs_fiemap,
 249};
 250