Commit | Line | Data |
---|---|---|
d72d1ce6 GX |
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* | |
3 | * linux/drivers/staging/erofs/namei.c | |
4 | * | |
5 | * Copyright (C) 2017-2018 HUAWEI, Inc. | |
6 | * http://www.huawei.com/ | |
7 | * Created by Gao Xiang <gaoxiang25@huawei.com> | |
8 | * | |
9 | * This file is subject to the terms and conditions of the GNU General Public | |
10 | * License. See the file COPYING in the main directory of the Linux | |
11 | * distribution for more details. | |
12 | */ | |
13 | #include "internal.h" | |
b17500a0 | 14 | #include "xattr.h" |
d72d1ce6 | 15 | |
13f06f48 CY |
16 | #include <trace/events/erofs.h> |
17 | ||
d72d1ce6 GX |
18 | /* based on the value of qn->len is accurate */ |
19 | static inline int dirnamecmp(struct qstr *qn, | |
20 | struct qstr *qd, unsigned *matched) | |
21 | { | |
22 | unsigned i = *matched, len = min(qn->len, qd->len); | |
23 | loop: | |
24 | if (unlikely(i >= len)) { | |
25 | *matched = i; | |
26 | if (qn->len < qd->len) { | |
27 | /* | |
28 | * actually (qn->len == qd->len) | |
29 | * when qd->name[i] == '\0' | |
30 | */ | |
31 | return qd->name[i] == '\0' ? 0 : -1; | |
32 | } | |
33 | return (qn->len > qd->len); | |
34 | } | |
35 | ||
36 | if (qn->name[i] != qd->name[i]) { | |
37 | *matched = i; | |
38 | return qn->name[i] > qd->name[i] ? 1 : -1; | |
39 | } | |
40 | ||
41 | ++i; | |
42 | goto loop; | |
43 | } | |
44 | ||
45 | static struct erofs_dirent *find_target_dirent( | |
46 | struct qstr *name, | |
47 | u8 *data, int maxsize) | |
48 | { | |
49 | unsigned ndirents, head, back; | |
50 | unsigned startprfx, endprfx; | |
51 | struct erofs_dirent *const de = (struct erofs_dirent *)data; | |
52 | ||
53 | /* make sure that maxsize is valid */ | |
54 | BUG_ON(maxsize < sizeof(struct erofs_dirent)); | |
55 | ||
56 | ndirents = le16_to_cpu(de->nameoff) / sizeof(*de); | |
57 | ||
58 | /* corrupted dir (may be unnecessary...) */ | |
59 | BUG_ON(!ndirents); | |
60 | ||
61 | head = 0; | |
62 | back = ndirents - 1; | |
63 | startprfx = endprfx = 0; | |
64 | ||
65 | while (head <= back) { | |
66 | unsigned mid = head + (back - head) / 2; | |
67 | unsigned nameoff = le16_to_cpu(de[mid].nameoff); | |
68 | unsigned matched = min(startprfx, endprfx); | |
69 | ||
70 | struct qstr dname = QSTR_INIT(data + nameoff, | |
71 | unlikely(mid >= ndirents - 1) ? | |
72 | maxsize - nameoff : | |
73 | le16_to_cpu(de[mid + 1].nameoff) - nameoff); | |
74 | ||
75 | /* string comparison without already matched prefix */ | |
76 | int ret = dirnamecmp(name, &dname, &matched); | |
77 | ||
78 | if (unlikely(!ret)) | |
79 | return de + mid; | |
80 | else if (ret > 0) { | |
81 | head = mid + 1; | |
82 | startprfx = matched; | |
83 | } else if (unlikely(mid < 1)) /* fix "mid" overflow */ | |
84 | break; | |
85 | else { | |
86 | back = mid - 1; | |
87 | endprfx = matched; | |
88 | } | |
89 | } | |
90 | ||
91 | return ERR_PTR(-ENOENT); | |
92 | } | |
93 | ||
94 | static struct page *find_target_block_classic( | |
95 | struct inode *dir, | |
96 | struct qstr *name, int *_diff) | |
97 | { | |
98 | unsigned startprfx, endprfx; | |
99 | unsigned head, back; | |
100 | struct address_space *const mapping = dir->i_mapping; | |
101 | struct page *candidate = ERR_PTR(-ENOENT); | |
102 | ||
103 | startprfx = endprfx = 0; | |
104 | head = 0; | |
105 | back = inode_datablocks(dir) - 1; | |
106 | ||
107 | while (head <= back) { | |
108 | unsigned mid = head + (back - head) / 2; | |
109 | struct page *page = read_mapping_page(mapping, mid, NULL); | |
110 | ||
111 | if (IS_ERR(page)) { | |
112 | exact_out: | |
113 | if (!IS_ERR(candidate)) /* valid candidate */ | |
114 | put_page(candidate); | |
115 | return page; | |
116 | } else { | |
117 | int diff; | |
118 | unsigned ndirents, matched; | |
119 | struct qstr dname; | |
120 | struct erofs_dirent *de = kmap_atomic(page); | |
121 | unsigned nameoff = le16_to_cpu(de->nameoff); | |
122 | ||
123 | ndirents = nameoff / sizeof(*de); | |
124 | ||
125 | /* corrupted dir (should have one entry at least) */ | |
126 | BUG_ON(!ndirents || nameoff > PAGE_SIZE); | |
127 | ||
128 | matched = min(startprfx, endprfx); | |
129 | ||
130 | dname.name = (u8 *)de + nameoff; | |
131 | dname.len = ndirents == 1 ? | |
132 | /* since the rest of the last page is 0 */ | |
133 | EROFS_BLKSIZ - nameoff | |
134 | : le16_to_cpu(de[1].nameoff) - nameoff; | |
135 | ||
136 | /* string comparison without already matched prefix */ | |
137 | diff = dirnamecmp(name, &dname, &matched); | |
138 | kunmap_atomic(de); | |
139 | ||
140 | if (unlikely(!diff)) { | |
141 | *_diff = 0; | |
142 | goto exact_out; | |
143 | } else if (diff > 0) { | |
144 | head = mid + 1; | |
145 | startprfx = matched; | |
146 | ||
147 | if (likely(!IS_ERR(candidate))) | |
148 | put_page(candidate); | |
149 | candidate = page; | |
150 | } else { | |
151 | put_page(page); | |
152 | ||
153 | if (unlikely(mid < 1)) /* fix "mid" overflow */ | |
154 | break; | |
155 | ||
156 | back = mid - 1; | |
157 | endprfx = matched; | |
158 | } | |
159 | } | |
160 | } | |
161 | *_diff = 1; | |
162 | return candidate; | |
163 | } | |
164 | ||
165 | int erofs_namei(struct inode *dir, | |
166 | struct qstr *name, | |
167 | erofs_nid_t *nid, unsigned *d_type) | |
168 | { | |
169 | int diff; | |
170 | struct page *page; | |
171 | u8 *data; | |
172 | struct erofs_dirent *de; | |
173 | ||
174 | if (unlikely(!dir->i_size)) | |
175 | return -ENOENT; | |
176 | ||
177 | diff = 1; | |
178 | page = find_target_block_classic(dir, name, &diff); | |
179 | ||
180 | if (unlikely(IS_ERR(page))) | |
181 | return PTR_ERR(page); | |
182 | ||
183 | data = kmap_atomic(page); | |
184 | /* the target page has been mapped */ | |
185 | de = likely(diff) ? | |
186 | /* since the rest of the last page is 0 */ | |
187 | find_target_dirent(name, data, EROFS_BLKSIZ) : | |
188 | (struct erofs_dirent *)data; | |
189 | ||
190 | if (likely(!IS_ERR(de))) { | |
191 | *nid = le64_to_cpu(de->nid); | |
192 | *d_type = de->file_type; | |
193 | } | |
194 | ||
195 | kunmap_atomic(data); | |
196 | put_page(page); | |
197 | ||
198 | return IS_ERR(de) ? PTR_ERR(de) : 0; | |
199 | } | |
200 | ||
201 | /* NOTE: i_mutex is already held by vfs */ | |
202 | static struct dentry *erofs_lookup(struct inode *dir, | |
203 | struct dentry *dentry, unsigned int flags) | |
204 | { | |
205 | int err; | |
206 | erofs_nid_t nid; | |
207 | unsigned d_type; | |
208 | struct inode *inode; | |
209 | ||
210 | DBG_BUGON(!d_really_is_negative(dentry)); | |
211 | /* dentry must be unhashed in lookup, no need to worry about */ | |
212 | DBG_BUGON(!d_unhashed(dentry)); | |
213 | ||
13f06f48 CY |
214 | trace_erofs_lookup(dir, dentry, flags); |
215 | ||
d72d1ce6 GX |
216 | /* file name exceeds fs limit */ |
217 | if (unlikely(dentry->d_name.len > EROFS_NAME_LEN)) | |
218 | return ERR_PTR(-ENAMETOOLONG); | |
219 | ||
220 | /* false uninitialized warnings on gcc 4.8.x */ | |
221 | err = erofs_namei(dir, &dentry->d_name, &nid, &d_type); | |
222 | ||
223 | if (err == -ENOENT) { | |
224 | /* negative dentry */ | |
225 | inode = NULL; | |
226 | goto negative_out; | |
227 | } else if (unlikely(err)) | |
228 | return ERR_PTR(err); | |
229 | ||
230 | debugln("%s, %s (nid %llu) found, d_type %u", __func__, | |
231 | dentry->d_name.name, nid, d_type); | |
232 | ||
233 | inode = erofs_iget(dir->i_sb, nid, d_type == EROFS_FT_DIR); | |
234 | if (IS_ERR(inode)) | |
235 | return ERR_CAST(inode); | |
236 | ||
237 | negative_out: | |
238 | return d_splice_alias(inode, dentry); | |
239 | } | |
240 | ||
241 | const struct inode_operations erofs_dir_iops = { | |
242 | .lookup = erofs_lookup, | |
243 | }; | |
244 | ||
245 | const struct inode_operations erofs_dir_xattr_iops = { | |
246 | .lookup = erofs_lookup, | |
b17500a0 GX |
247 | #ifdef CONFIG_EROFS_FS_XATTR |
248 | .listxattr = erofs_listxattr, | |
249 | #endif | |
d72d1ce6 GX |
250 | }; |
251 |