1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3 * Copyright (C) 2017-2018 HUAWEI, Inc.
4 * https://www.huawei.com/
5 * Created by Gao Xiang <gaoxiang25@huawei.com>
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' */
erofs_dirnamecmp(const struct erofs_qstr * qn,const struct erofs_qstr * qd,unsigned int * matched)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
find_target_dirent(struct erofs_qstr * name,u8 * data,unsigned int dirblksize,const int ndirents)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
find_target_block_classic(struct inode * dir,struct erofs_qstr * name,int * _ndirents)90 static struct page *find_target_block_classic(struct inode *dir,
91 struct erofs_qstr *name,
92 int *_ndirents)
93 {
94 unsigned int startprfx, endprfx;
95 int head, back;
96 struct address_space *const mapping = dir->i_mapping;
97 struct page *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 page *page = read_mapping_page(mapping, mid, NULL);
106
107 if (!IS_ERR(page)) {
108 struct erofs_dirent *de = kmap_atomic(page);
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;
115
116 if (!ndirents) {
117 kunmap_atomic(de);
118 put_page(page);
119 erofs_err(dir->i_sb,
120 "corrupted dir block %d @ nid %llu",
121 mid, EROFS_I(dir)->nid);
122 DBG_BUGON(1);
123 page = 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 kunmap_atomic(de);
140
141 if (!diff) {
142 *_ndirents = 0;
143 goto out;
144 } else if (diff > 0) {
145 head = mid + 1;
146 startprfx = matched;
147
148 if (!IS_ERR(candidate))
149 put_page(candidate);
150 candidate = page;
151 *_ndirents = ndirents;
152 } else {
153 put_page(page);
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 put_page(candidate);
163 return page;
164 }
165 return candidate;
166 }
167
erofs_namei(struct inode * dir,struct qstr * name,erofs_nid_t * nid,unsigned int * d_type)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 page *page;
174 void *data;
175 struct erofs_dirent *de;
176 struct erofs_qstr qn;
177
178 if (!dir->i_size)
179 return -ENOENT;
180
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);
186
187 if (IS_ERR(page))
188 return PTR_ERR(page);
189
190 data = kmap_atomic(page);
191 /* the target page has been mapped */
192 if (ndirents)
193 de = find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents);
194 else
195 de = (struct erofs_dirent *)data;
196
197 if (!IS_ERR(de)) {
198 *nid = le64_to_cpu(de->nid);
199 *d_type = de->file_type;
200 }
201
202 kunmap_atomic(data);
203 put_page(page);
204
205 return PTR_ERR_OR_ZERO(de);
206 }
207
208 /* NOTE: i_mutex is already held by vfs */
erofs_lookup(struct inode * dir,struct dentry * dentry,unsigned int flags)209 static struct dentry *erofs_lookup(struct inode *dir,
210 struct dentry *dentry,
211 unsigned int flags)
212 {
213 int err;
214 erofs_nid_t nid;
215 unsigned int d_type;
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
222 trace_erofs_lookup(dir, dentry, flags);
223
224 /* file name exceeds fs limit */
225 if (dentry->d_name.len > EROFS_NAME_LEN)
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;
234 } else if (err) {
235 inode = ERR_PTR(err);
236 } else {
237 erofs_dbg("%s, %pd (nid %llu) found, d_type %u", __func__,
238 dentry, nid, d_type);
239 inode = erofs_iget(dir->i_sb, nid, d_type == FT_DIR);
240 }
241 return d_splice_alias(inode, dentry);
242 }
243
244 const struct inode_operations erofs_dir_iops = {
245 .lookup = erofs_lookup,
246 .getattr = erofs_getattr,
247 .listxattr = erofs_listxattr,
248 .get_acl = erofs_get_acl,
249 };
250
251