Commit | Line | Data |
---|---|---|
29b24f6c | 1 | // SPDX-License-Identifier: GPL-2.0-only |
d72d1ce6 | 2 | /* |
d72d1ce6 | 3 | * Copyright (C) 2017-2018 HUAWEI, Inc. |
592e7cd0 | 4 | * https://www.huawei.com/ |
500edd09 | 5 | * Copyright (C) 2022, Alibaba Cloud |
d72d1ce6 | 6 | */ |
b17500a0 | 7 | #include "xattr.h" |
13f06f48 CY |
8 | #include <trace/events/erofs.h> |
9 | ||
419d6efc GX |
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' */ | |
99634bf3 GX |
16 | static inline int erofs_dirnamecmp(const struct erofs_qstr *qn, |
17 | const struct erofs_qstr *qd, | |
18 | unsigned int *matched) | |
d72d1ce6 | 19 | { |
419d6efc GX |
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; | |
d72d1ce6 | 35 | } |
419d6efc | 36 | ++i; |
d72d1ce6 | 37 | } |
419d6efc GX |
38 | *matched = i; |
39 | /* See comments in __d_alloc on the terminating NUL character */ | |
40 | return qn->name[i] == '\0' ? 0 : 1; | |
d72d1ce6 GX |
41 | } |
42 | ||
419d6efc GX |
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) | |
d72d1ce6 | 49 | { |
419d6efc | 50 | int head, back; |
7dd68b14 | 51 | unsigned int startprfx, endprfx; |
d72d1ce6 GX |
52 | struct erofs_dirent *const de = (struct erofs_dirent *)data; |
53 | ||
419d6efc GX |
54 | /* since the 1st dirent has been evaluated previously */ |
55 | head = 1; | |
d72d1ce6 GX |
56 | back = ndirents - 1; |
57 | startprfx = endprfx = 0; | |
58 | ||
59 | while (head <= back) { | |
419d6efc GX |
60 | const int mid = head + (back - head) / 2; |
61 | const int nameoff = nameoff_from_disk(de[mid].nameoff, | |
62 | dirblksize); | |
7dd68b14 | 63 | unsigned int matched = min(startprfx, endprfx); |
419d6efc GX |
64 | struct erofs_qstr dname = { |
65 | .name = data + nameoff, | |
8d8a09b0 | 66 | .end = mid >= ndirents - 1 ? |
419d6efc GX |
67 | data + dirblksize : |
68 | data + nameoff_from_disk(de[mid + 1].nameoff, | |
69 | dirblksize) | |
70 | }; | |
d72d1ce6 GX |
71 | |
72 | /* string comparison without already matched prefix */ | |
99634bf3 | 73 | int ret = erofs_dirnamecmp(name, &dname, &matched); |
d72d1ce6 | 74 | |
8d8a09b0 | 75 | if (!ret) { |
d72d1ce6 | 76 | return de + mid; |
419d6efc | 77 | } else if (ret > 0) { |
d72d1ce6 GX |
78 | head = mid + 1; |
79 | startprfx = matched; | |
419d6efc | 80 | } else { |
d72d1ce6 GX |
81 | back = mid - 1; |
82 | endprfx = matched; | |
83 | } | |
84 | } | |
85 | ||
86 | return ERR_PTR(-ENOENT); | |
87 | } | |
88 | ||
4efdec36 GX |
89 | static void *erofs_find_target_block(struct erofs_buf *target, |
90 | struct inode *dir, struct erofs_qstr *name, int *_ndirents) | |
d72d1ce6 | 91 | { |
3acea5fc JX |
92 | unsigned int bsz = i_blocksize(dir); |
93 | int head = 0, back = erofs_iblks(dir) - 1; | |
4efdec36 | 94 | unsigned int startprfx = 0, endprfx = 0; |
500edd09 | 95 | void *candidate = ERR_PTR(-ENOENT); |
d72d1ce6 | 96 | |
d72d1ce6 | 97 | while (head <= back) { |
419d6efc | 98 | const int mid = head + (back - head) / 2; |
500edd09 GX |
99 | struct erofs_buf buf = __EROFS_BUF_INITIALIZER; |
100 | struct erofs_dirent *de; | |
d72d1ce6 | 101 | |
958b9f85 | 102 | buf.mapping = dir->i_mapping; |
706e50e4 | 103 | de = erofs_bread(&buf, erofs_pos(dir->i_sb, mid), true); |
500edd09 | 104 | if (!IS_ERR(de)) { |
3acea5fc | 105 | const int nameoff = nameoff_from_disk(de->nameoff, bsz); |
419d6efc GX |
106 | const int ndirents = nameoff / sizeof(*de); |
107 | int diff; | |
108 | unsigned int matched; | |
109 | struct erofs_qstr dname; | |
d72d1ce6 | 110 | |
8d8a09b0 | 111 | if (!ndirents) { |
500edd09 | 112 | erofs_put_metabuf(&buf); |
4f761fa2 GX |
113 | erofs_err(dir->i_sb, |
114 | "corrupted dir block %d @ nid %llu", | |
115 | mid, EROFS_I(dir)->nid); | |
a6b9b1d5 | 116 | DBG_BUGON(1); |
500edd09 | 117 | de = ERR_PTR(-EFSCORRUPTED); |
419d6efc GX |
118 | goto out; |
119 | } | |
d72d1ce6 GX |
120 | |
121 | matched = min(startprfx, endprfx); | |
122 | ||
123 | dname.name = (u8 *)de + nameoff; | |
419d6efc | 124 | if (ndirents == 1) |
3acea5fc | 125 | dname.end = (u8 *)de + bsz; |
419d6efc GX |
126 | else |
127 | dname.end = (u8 *)de + | |
3acea5fc | 128 | nameoff_from_disk(de[1].nameoff, bsz); |
d72d1ce6 GX |
129 | |
130 | /* string comparison without already matched prefix */ | |
99634bf3 | 131 | diff = erofs_dirnamecmp(name, &dname, &matched); |
d72d1ce6 | 132 | |
56ee7db3 | 133 | if (diff < 0) { |
500edd09 | 134 | erofs_put_metabuf(&buf); |
d72d1ce6 GX |
135 | back = mid - 1; |
136 | endprfx = matched; | |
56ee7db3 SD |
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; | |
d72d1ce6 | 146 | } |
56ee7db3 SD |
147 | head = mid + 1; |
148 | startprfx = matched; | |
149 | candidate = de; | |
150 | *_ndirents = ndirents; | |
419d6efc | 151 | continue; |
d72d1ce6 | 152 | } |
419d6efc GX |
153 | out: /* free if the candidate is valid */ |
154 | if (!IS_ERR(candidate)) | |
500edd09 GX |
155 | erofs_put_metabuf(target); |
156 | return de; | |
d72d1ce6 | 157 | } |
d72d1ce6 GX |
158 | return candidate; |
159 | } | |
160 | ||
3e917cc3 HL |
161 | int erofs_namei(struct inode *dir, const struct qstr *name, erofs_nid_t *nid, |
162 | unsigned int *d_type) | |
d72d1ce6 | 163 | { |
419d6efc | 164 | int ndirents; |
500edd09 | 165 | struct erofs_buf buf = __EROFS_BUF_INITIALIZER; |
d72d1ce6 | 166 | struct erofs_dirent *de; |
419d6efc | 167 | struct erofs_qstr qn; |
d72d1ce6 | 168 | |
8d8a09b0 | 169 | if (!dir->i_size) |
d72d1ce6 GX |
170 | return -ENOENT; |
171 | ||
419d6efc GX |
172 | qn.name = name->name; |
173 | qn.end = name->name + name->len; | |
958b9f85 | 174 | buf.mapping = dir->i_mapping; |
419d6efc GX |
175 | |
176 | ndirents = 0; | |
4efdec36 | 177 | de = erofs_find_target_block(&buf, dir, &qn, &ndirents); |
500edd09 GX |
178 | if (IS_ERR(de)) |
179 | return PTR_ERR(de); | |
d72d1ce6 | 180 | |
419d6efc | 181 | if (ndirents) |
3acea5fc JX |
182 | de = find_target_dirent(&qn, (u8 *)de, i_blocksize(dir), |
183 | ndirents); | |
d72d1ce6 | 184 | |
7fadcdce | 185 | if (!IS_ERR(de)) { |
d72d1ce6 GX |
186 | *nid = le64_to_cpu(de->nid); |
187 | *d_type = de->file_type; | |
188 | } | |
500edd09 | 189 | erofs_put_metabuf(&buf); |
38c6aa21 | 190 | return PTR_ERR_OR_ZERO(de); |
d72d1ce6 GX |
191 | } |
192 | ||
53a7f996 | 193 | static struct dentry *erofs_lookup(struct inode *dir, struct dentry *dentry, |
447a3621 | 194 | unsigned int flags) |
d72d1ce6 GX |
195 | { |
196 | int err; | |
197 | erofs_nid_t nid; | |
7dd68b14 | 198 | unsigned int d_type; |
d72d1ce6 GX |
199 | struct inode *inode; |
200 | ||
13f06f48 CY |
201 | trace_erofs_lookup(dir, dentry, flags); |
202 | ||
8d8a09b0 | 203 | if (dentry->d_name.len > EROFS_NAME_LEN) |
d72d1ce6 GX |
204 | return ERR_PTR(-ENAMETOOLONG); |
205 | ||
d72d1ce6 GX |
206 | err = erofs_namei(dir, &dentry->d_name, &nid, &d_type); |
207 | ||
10656f9c | 208 | if (err == -ENOENT) |
d72d1ce6 GX |
209 | /* negative dentry */ |
210 | inode = NULL; | |
10656f9c | 211 | else if (err) |
8300807f | 212 | inode = ERR_PTR(err); |
10656f9c | 213 | else |
312fe643 | 214 | inode = erofs_iget(dir->i_sb, nid); |
d72d1ce6 GX |
215 | return d_splice_alias(inode, dentry); |
216 | } | |
217 | ||
218 | const struct inode_operations erofs_dir_iops = { | |
219 | .lookup = erofs_lookup, | |
89f27ede | 220 | .getattr = erofs_getattr, |
b17500a0 | 221 | .listxattr = erofs_listxattr, |
cac2f8b8 | 222 | .get_inode_acl = erofs_get_acl, |
eadcd6b5 | 223 | .fiemap = erofs_fiemap, |
d72d1ce6 | 224 | }; |