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"
14 #include "xattr.h"
15
16 #include <trace/events/erofs.h>
17
18 /* based on the value of qn->len is accurate */
dirnamecmp(struct qstr * qn,struct qstr * qd,unsigned * matched)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
find_target_dirent(struct qstr * name,u8 * data,int maxsize)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
find_target_block_classic(struct inode * dir,struct qstr * name,int * _diff)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
erofs_namei(struct inode * dir,struct qstr * name,erofs_nid_t * nid,unsigned * d_type)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 PTR_ERR_OR_ZERO(de);
199 }
200
201 /* NOTE: i_mutex is already held by vfs */
erofs_lookup(struct inode * dir,struct dentry * dentry,unsigned int flags)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
214 trace_erofs_lookup(dir, dentry, flags);
215
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,
247 #ifdef CONFIG_EROFS_FS_XATTR
248 .listxattr = erofs_listxattr,
249 #endif
250 };
251
252
