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(qn: name, qd: &dname, matched: &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(error: -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(node: dir); |
93 | int head = 0, back = erofs_iblks(dir) - 1; |
94 | unsigned int startprfx = 0, endprfx = 0; |
95 | void *candidate = ERR_PTR(error: -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.inode = dir; |
103 | de = erofs_bread(buf: &buf, blkaddr: mid, type: EROFS_KMAP); |
104 | if (!IS_ERR(ptr: 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: &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(error: -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(qn: name, qd: &dname, matched: &matched); |
132 | |
133 | if (diff < 0) { |
134 | erofs_put_metabuf(buf: &buf); |
135 | back = mid - 1; |
136 | endprfx = matched; |
137 | continue; |
138 | } |
139 | |
140 | if (!IS_ERR(ptr: candidate)) |
141 | erofs_put_metabuf(buf: 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(ptr: candidate)) |
155 | erofs_put_metabuf(buf: 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.inode = dir; |
175 | |
176 | ndirents = 0; |
177 | de = erofs_find_target_block(target: &buf, dir, name: &qn, ndirents: &ndirents); |
178 | if (IS_ERR(ptr: de)) |
179 | return PTR_ERR(ptr: de); |
180 | |
181 | if (ndirents) |
182 | de = find_target_dirent(name: &qn, data: (u8 *)de, dirblksize: i_blocksize(node: dir), |
183 | ndirents); |
184 | |
185 | if (!IS_ERR(ptr: de)) { |
186 | *nid = le64_to_cpu(de->nid); |
187 | *d_type = de->file_type; |
188 | } |
189 | erofs_put_metabuf(buf: &buf); |
190 | return PTR_ERR_OR_ZERO(ptr: 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(error: -ENAMETOOLONG); |
205 | |
206 | err = erofs_namei(dir, name: &dentry->d_name, nid: &nid, d_type: &d_type); |
207 | |
208 | if (err == -ENOENT) |
209 | /* negative dentry */ |
210 | inode = NULL; |
211 | else if (err) |
212 | inode = ERR_PTR(error: err); |
213 | else |
214 | inode = erofs_iget(sb: 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 | |