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/ |
d72d1ce6 | 5 | * Created by Gao Xiang <gaoxiang25@huawei.com> |
d72d1ce6 | 6 | */ |
b17500a0 | 7 | #include "xattr.h" |
d72d1ce6 | 8 | |
13f06f48 CY |
9 | #include <trace/events/erofs.h> |
10 | ||
419d6efc GX |
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' */ | |
99634bf3 GX |
17 | static inline int erofs_dirnamecmp(const struct erofs_qstr *qn, |
18 | const struct erofs_qstr *qd, | |
19 | unsigned int *matched) | |
d72d1ce6 | 20 | { |
419d6efc GX |
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; | |
d72d1ce6 | 36 | } |
419d6efc | 37 | ++i; |
d72d1ce6 | 38 | } |
419d6efc GX |
39 | *matched = i; |
40 | /* See comments in __d_alloc on the terminating NUL character */ | |
41 | return qn->name[i] == '\0' ? 0 : 1; | |
d72d1ce6 GX |
42 | } |
43 | ||
419d6efc GX |
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) | |
d72d1ce6 | 50 | { |
419d6efc | 51 | int head, back; |
7dd68b14 | 52 | unsigned int startprfx, endprfx; |
d72d1ce6 GX |
53 | struct erofs_dirent *const de = (struct erofs_dirent *)data; |
54 | ||
419d6efc GX |
55 | /* since the 1st dirent has been evaluated previously */ |
56 | head = 1; | |
d72d1ce6 GX |
57 | back = ndirents - 1; |
58 | startprfx = endprfx = 0; | |
59 | ||
60 | while (head <= back) { | |
419d6efc GX |
61 | const int mid = head + (back - head) / 2; |
62 | const int nameoff = nameoff_from_disk(de[mid].nameoff, | |
63 | dirblksize); | |
7dd68b14 | 64 | unsigned int matched = min(startprfx, endprfx); |
419d6efc GX |
65 | struct erofs_qstr dname = { |
66 | .name = data + nameoff, | |
8d8a09b0 | 67 | .end = mid >= ndirents - 1 ? |
419d6efc GX |
68 | data + dirblksize : |
69 | data + nameoff_from_disk(de[mid + 1].nameoff, | |
70 | dirblksize) | |
71 | }; | |
d72d1ce6 GX |
72 | |
73 | /* string comparison without already matched prefix */ | |
99634bf3 | 74 | int ret = erofs_dirnamecmp(name, &dname, &matched); |
d72d1ce6 | 75 | |
8d8a09b0 | 76 | if (!ret) { |
d72d1ce6 | 77 | return de + mid; |
419d6efc | 78 | } else if (ret > 0) { |
d72d1ce6 GX |
79 | head = mid + 1; |
80 | startprfx = matched; | |
419d6efc | 81 | } else { |
d72d1ce6 GX |
82 | back = mid - 1; |
83 | endprfx = matched; | |
84 | } | |
85 | } | |
86 | ||
87 | return ERR_PTR(-ENOENT); | |
88 | } | |
89 | ||
419d6efc GX |
90 | static struct page *find_target_block_classic(struct inode *dir, |
91 | struct erofs_qstr *name, | |
92 | int *_ndirents) | |
d72d1ce6 | 93 | { |
7dd68b14 | 94 | unsigned int startprfx, endprfx; |
419d6efc | 95 | int head, back; |
d72d1ce6 GX |
96 | struct address_space *const mapping = dir->i_mapping; |
97 | struct page *candidate = ERR_PTR(-ENOENT); | |
98 | ||
99 | startprfx = endprfx = 0; | |
100 | head = 0; | |
99634bf3 | 101 | back = erofs_inode_datablocks(dir) - 1; |
d72d1ce6 GX |
102 | |
103 | while (head <= back) { | |
419d6efc | 104 | const int mid = head + (back - head) / 2; |
d72d1ce6 GX |
105 | struct page *page = read_mapping_page(mapping, mid, NULL); |
106 | ||
419d6efc | 107 | if (!IS_ERR(page)) { |
d72d1ce6 | 108 | struct erofs_dirent *de = kmap_atomic(page); |
419d6efc GX |
109 | const int nameoff = nameoff_from_disk(de->nameoff, |
110 | EROFS_BLKSIZ); | |
111 | const int ndirents = nameoff / sizeof(*de); | |
112 | int diff; | |
113 | unsigned int matched; | |
114 | struct erofs_qstr dname; | |
d72d1ce6 | 115 | |
8d8a09b0 | 116 | if (!ndirents) { |
419d6efc GX |
117 | kunmap_atomic(de); |
118 | put_page(page); | |
4f761fa2 GX |
119 | erofs_err(dir->i_sb, |
120 | "corrupted dir block %d @ nid %llu", | |
121 | mid, EROFS_I(dir)->nid); | |
a6b9b1d5 GX |
122 | DBG_BUGON(1); |
123 | page = ERR_PTR(-EFSCORRUPTED); | |
419d6efc GX |
124 | goto out; |
125 | } | |
d72d1ce6 GX |
126 | |
127 | matched = min(startprfx, endprfx); | |
128 | ||
129 | dname.name = (u8 *)de + nameoff; | |
419d6efc GX |
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); | |
d72d1ce6 GX |
136 | |
137 | /* string comparison without already matched prefix */ | |
99634bf3 | 138 | diff = erofs_dirnamecmp(name, &dname, &matched); |
d72d1ce6 GX |
139 | kunmap_atomic(de); |
140 | ||
8d8a09b0 | 141 | if (!diff) { |
419d6efc GX |
142 | *_ndirents = 0; |
143 | goto out; | |
d72d1ce6 GX |
144 | } else if (diff > 0) { |
145 | head = mid + 1; | |
146 | startprfx = matched; | |
147 | ||
7fadcdce | 148 | if (!IS_ERR(candidate)) |
d72d1ce6 GX |
149 | put_page(candidate); |
150 | candidate = page; | |
419d6efc | 151 | *_ndirents = ndirents; |
d72d1ce6 GX |
152 | } else { |
153 | put_page(page); | |
154 | ||
d72d1ce6 GX |
155 | back = mid - 1; |
156 | endprfx = matched; | |
157 | } | |
419d6efc | 158 | continue; |
d72d1ce6 | 159 | } |
419d6efc GX |
160 | out: /* free if the candidate is valid */ |
161 | if (!IS_ERR(candidate)) | |
162 | put_page(candidate); | |
163 | return page; | |
d72d1ce6 | 164 | } |
d72d1ce6 GX |
165 | return candidate; |
166 | } | |
167 | ||
168 | int erofs_namei(struct inode *dir, | |
419d6efc GX |
169 | struct qstr *name, |
170 | erofs_nid_t *nid, unsigned int *d_type) | |
d72d1ce6 | 171 | { |
419d6efc | 172 | int ndirents; |
d72d1ce6 | 173 | struct page *page; |
419d6efc | 174 | void *data; |
d72d1ce6 | 175 | struct erofs_dirent *de; |
419d6efc | 176 | struct erofs_qstr qn; |
d72d1ce6 | 177 | |
8d8a09b0 | 178 | if (!dir->i_size) |
d72d1ce6 GX |
179 | return -ENOENT; |
180 | ||
419d6efc GX |
181 | qn.name = name->name; |
182 | qn.end = name->name + name->len; | |
183 | ||
184 | ndirents = 0; | |
185 | page = find_target_block_classic(dir, &qn, &ndirents); | |
d72d1ce6 | 186 | |
7fadcdce | 187 | if (IS_ERR(page)) |
d72d1ce6 GX |
188 | return PTR_ERR(page); |
189 | ||
190 | data = kmap_atomic(page); | |
191 | /* the target page has been mapped */ | |
419d6efc GX |
192 | if (ndirents) |
193 | de = find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents); | |
194 | else | |
195 | de = (struct erofs_dirent *)data; | |
d72d1ce6 | 196 | |
7fadcdce | 197 | if (!IS_ERR(de)) { |
d72d1ce6 GX |
198 | *nid = le64_to_cpu(de->nid); |
199 | *d_type = de->file_type; | |
200 | } | |
201 | ||
202 | kunmap_atomic(data); | |
203 | put_page(page); | |
204 | ||
38c6aa21 | 205 | return PTR_ERR_OR_ZERO(de); |
d72d1ce6 GX |
206 | } |
207 | ||
208 | /* NOTE: i_mutex is already held by vfs */ | |
209 | static struct dentry *erofs_lookup(struct inode *dir, | |
447a3621 JM |
210 | struct dentry *dentry, |
211 | unsigned int flags) | |
d72d1ce6 GX |
212 | { |
213 | int err; | |
214 | erofs_nid_t nid; | |
7dd68b14 | 215 | unsigned int d_type; |
d72d1ce6 GX |
216 | struct inode *inode; |
217 | ||
218 | DBG_BUGON(!d_really_is_negative(dentry)); | |
219 | /* dentry must be unhashed in lookup, no need to worry about */ | |
220 | DBG_BUGON(!d_unhashed(dentry)); | |
221 | ||
13f06f48 CY |
222 | trace_erofs_lookup(dir, dentry, flags); |
223 | ||
d72d1ce6 | 224 | /* file name exceeds fs limit */ |
8d8a09b0 | 225 | if (dentry->d_name.len > EROFS_NAME_LEN) |
d72d1ce6 GX |
226 | return ERR_PTR(-ENAMETOOLONG); |
227 | ||
228 | /* false uninitialized warnings on gcc 4.8.x */ | |
229 | err = erofs_namei(dir, &dentry->d_name, &nid, &d_type); | |
230 | ||
231 | if (err == -ENOENT) { | |
232 | /* negative dentry */ | |
233 | inode = NULL; | |
8d8a09b0 | 234 | } else if (err) { |
8300807f AV |
235 | inode = ERR_PTR(err); |
236 | } else { | |
4f761fa2 GX |
237 | erofs_dbg("%s, %s (nid %llu) found, d_type %u", __func__, |
238 | dentry->d_name.name, nid, d_type); | |
1d819c54 | 239 | inode = erofs_iget(dir->i_sb, nid, d_type == FT_DIR); |
8300807f | 240 | } |
d72d1ce6 GX |
241 | return d_splice_alias(inode, dentry); |
242 | } | |
243 | ||
244 | const struct inode_operations erofs_dir_iops = { | |
245 | .lookup = erofs_lookup, | |
89f27ede | 246 | .getattr = erofs_getattr, |
b17500a0 | 247 | .listxattr = erofs_listxattr, |
516c115c | 248 | .get_acl = erofs_get_acl, |
d72d1ce6 GX |
249 | }; |
250 |