Skip to content

Commit d72d1ce

Browse files
Gao Xianggregkh
Gao Xiang
authored and
gregkh
committed
staging: erofs: add namei functions
This commit adds functions that transfer names to inodes. Signed-off-by: Miao Xie <miaoxie@huawei.com> Signed-off-by: Chao Yu <yuchao0@huawei.com> Signed-off-by: Gao Xiang <gaoxiang25@huawei.com> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
1 parent 3aa8ec7 commit d72d1ce

File tree

1 file changed

+243
-0
lines changed

1 file changed

+243
-0
lines changed

‎drivers/staging/erofs/namei.c

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

0 commit comments

Comments
 (0)