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 unsigned int bsz = i_blocksize(dir);
93 int head = 0, back = erofs_iblks(dir) - 1;
94 unsigned int startprfx = 0, endprfx = 0;
95 void *candidate = ERR_PTR(-ENOENT);
96
97 while (head <= back) {
98 const int mid = head + (back - head) / 2;
99 struct erofs_buf buf = __EROFS_BUF_INITIALIZER;
100 struct erofs_dirent *de;
101
102 buf.mapping = dir->i_mapping;
103 de = erofs_bread(&buf, erofs_pos(dir->i_sb, mid), EROFS_KMAP);
104 if (!IS_ERR(de)) {
105 const int nameoff = nameoff_from_disk(de->nameoff, bsz);
106 const int ndirents = nameoff / sizeof(*de);
107 int diff;
108 unsigned int matched;
109 struct erofs_qstr dname;
110
111 if (!ndirents) {
112 erofs_put_metabuf(&buf);
113 erofs_err(dir->i_sb,
114 "corrupted dir block %d @ nid %llu",
115 mid, EROFS_I(dir)->nid);
116 DBG_BUGON(1);
117 de = ERR_PTR(-EFSCORRUPTED);
118 goto out;
119 }
120
121 matched = min(startprfx, endprfx);
122
123 dname.name = (u8 *)de + nameoff;
124 if (ndirents == 1)
125 dname.end = (u8 *)de + bsz;
126 else
127 dname.end = (u8 *)de +
128 nameoff_from_disk(de[1].nameoff, bsz);
129
130 /* string comparison without already matched prefix */
131 diff = erofs_dirnamecmp(name, &dname, &matched);
132
133 if (diff < 0) {
134 erofs_put_metabuf(&buf);
135 back = mid - 1;
136 endprfx = matched;
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;
146 }
147 head = mid + 1;
148 startprfx = matched;
149 candidate = de;
150 *_ndirents = ndirents;
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 buf.mapping = dir->i_mapping;
175
176 ndirents = 0;
177 de = erofs_find_target_block(&buf, dir, &qn, &ndirents);
178 if (IS_ERR(de))
179 return PTR_ERR(de);
180
181 if (ndirents)
182 de = find_target_dirent(&qn, (u8 *)de, i_blocksize(dir),
183 ndirents);
184
185 if (!IS_ERR(de)) {
186 *nid = le64_to_cpu(de->nid);
187 *d_type = de->file_type;
188 }
189 erofs_put_metabuf(&buf);
190 return PTR_ERR_OR_ZERO(de);
191 }
192
193 static struct dentry *erofs_lookup(struct inode *dir, struct dentry *dentry,
194 unsigned int flags)
195 {
196 int err;
197 erofs_nid_t nid;
198 unsigned int d_type;
199 struct inode *inode;
200
201 trace_erofs_lookup(dir, dentry, flags);
202
203 if (dentry->d_name.len > EROFS_NAME_LEN)
204 return ERR_PTR(-ENAMETOOLONG);
205
206 err = erofs_namei(dir, &dentry->d_name, &nid, &d_type);
207
208 if (err == -ENOENT)
209 /* negative dentry */
210 inode = NULL;
211 else if (err)
212 inode = ERR_PTR(err);
213 else
214 inode = erofs_iget(dir->i_sb, nid);
215 return d_splice_alias(inode, dentry);
216 }
217
218 const struct inode_operations erofs_dir_iops = {
219 .lookup = erofs_lookup,
220 .getattr = erofs_getattr,
221 .listxattr = erofs_listxattr,
222 .get_inode_acl = erofs_get_acl,
223 .fiemap = erofs_fiemap,
224 };
225
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.