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