drivers/staging/erofs/namei.c

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