225 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright (C) 2017-2018 HUAWEI, Inc.4 * https://www.huawei.com/5 * Copyright (C) 2022, Alibaba Cloud6 */7#include "xattr.h"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 name25 * 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 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.mapping = dir->i_mapping;103 de = erofs_bread(&buf, erofs_pos(dir->i_sb, 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 else127 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 < 0) {134 erofs_put_metabuf(&buf);135 back = mid - 1;136 endprfx = matched;137 continue;138 }139 140 if (!IS_ERR(candidate))141 erofs_put_metabuf(target);142 *target = buf;143 if (!diff) {144 *_ndirents = 0;145 return de;146 }147 head = mid + 1;148 startprfx = matched;149 candidate = de;150 *_ndirents = ndirents;151 continue;152 }153out: /* 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 161int 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.mapping = dir->i_mapping;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 193static 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 else214 inode = erofs_iget(dir->i_sb, nid);215 return d_splice_alias(inode, dentry);216}217 218const 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};225