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 int head = 0, back = DIV_ROUND_UP(dir->i_size, EROFS_BLKSIZ) - 1; 93 unsigned int startprfx = 0, endprfx = 0; 94 void *candidate = ERR_PTR(-ENOENT); 95 96 while (head <= back) { 97 const int mid = head + (back - head) / 2; 98 struct erofs_buf buf = __EROFS_BUF_INITIALIZER; 99 struct erofs_dirent *de; 100 101 de = erofs_bread(&buf, dir, mid, EROFS_KMAP); 102 if (!IS_ERR(de)) { 103 const int nameoff = nameoff_from_disk(de->nameoff, 104 EROFS_BLKSIZ); 105 const int ndirents = nameoff / sizeof(*de); 106 int diff; 107 unsigned int matched; 108 struct erofs_qstr dname; 109 110 if (!ndirents) { 111 erofs_put_metabuf(&buf); 112 erofs_err(dir->i_sb, 113 "corrupted dir block %d @ nid %llu", 114 mid, EROFS_I(dir)->nid); 115 DBG_BUGON(1); 116 de = ERR_PTR(-EFSCORRUPTED); 117 goto out; 118 } 119 120 matched = min(startprfx, endprfx); 121 122 dname.name = (u8 *)de + nameoff; 123 if (ndirents == 1) 124 dname.end = (u8 *)de + EROFS_BLKSIZ; 125 else 126 dname.end = (u8 *)de + 127 nameoff_from_disk(de[1].nameoff, 128 EROFS_BLKSIZ); 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 175 ndirents = 0; 176 de = erofs_find_target_block(&buf, dir, &qn, &ndirents); 177 if (IS_ERR(de)) 178 return PTR_ERR(de); 179 180 if (ndirents) 181 de = find_target_dirent(&qn, (u8 *)de, EROFS_BLKSIZ, ndirents); 182 183 if (!IS_ERR(de)) { 184 *nid = le64_to_cpu(de->nid); 185 *d_type = de->file_type; 186 } 187 erofs_put_metabuf(&buf); 188 return PTR_ERR_OR_ZERO(de); 189 } 190 191 static struct dentry *erofs_lookup(struct inode *dir, struct dentry *dentry, 192 unsigned int flags) 193 { 194 int err; 195 erofs_nid_t nid; 196 unsigned int d_type; 197 struct inode *inode; 198 199 trace_erofs_lookup(dir, dentry, flags); 200 201 if (dentry->d_name.len > EROFS_NAME_LEN) 202 return ERR_PTR(-ENAMETOOLONG); 203 204 err = erofs_namei(dir, &dentry->d_name, &nid, &d_type); 205 206 if (err == -ENOENT) { 207 /* negative dentry */ 208 inode = NULL; 209 } else if (err) { 210 inode = ERR_PTR(err); 211 } else { 212 erofs_dbg("%s, %pd (nid %llu) found, d_type %u", __func__, 213 dentry, nid, d_type); 214 inode = erofs_iget(dir->i_sb, nid); 215 } 216 return d_splice_alias(inode, dentry); 217 } 218 219 const struct inode_operations erofs_dir_iops = { 220 .lookup = erofs_lookup, 221 .getattr = erofs_getattr, 222 .listxattr = erofs_listxattr, 223 .get_inode_acl = erofs_get_acl, 224 .fiemap = erofs_fiemap, 225 }; 226