1 // SPDX-License-Identifier: GPL-2.0-only
3 * Copyright (C) 2017-2018 HUAWEI, Inc.
4 * https://www.huawei.com/
5 * Created by Gao Xiang <gaoxiang25@huawei.com>
9 #include <trace/events/erofs.h>
12 const unsigned char *name
;
13 const unsigned char *end
;
16 /* based on the end of qn is accurate and it must have the trailing '\0' */
17 static inline int erofs_dirnamecmp(const struct erofs_qstr
*qn
,
18 const struct erofs_qstr
*qd
,
19 unsigned int *matched
)
21 unsigned int i
= *matched
;
24 * on-disk error, let's only BUG_ON in the debugging mode.
25 * otherwise, it will return 1 to just skip the invalid name
26 * and go on (in consideration of the lookup performance).
28 DBG_BUGON(qd
->name
> qd
->end
);
30 /* qd could not have trailing '\0' */
31 /* However it is absolutely safe if < qd->end */
32 while (qd
->name
+ i
< qd
->end
&& qd
->name
[i
] != '\0') {
33 if (qn
->name
[i
] != qd
->name
[i
]) {
35 return qn
->name
[i
] > qd
->name
[i
] ? 1 : -1;
40 /* See comments in __d_alloc on the terminating NUL character */
41 return qn
->name
[i
] == '\0' ? 0 : 1;
44 #define nameoff_from_disk(off, sz) (le16_to_cpu(off) & ((sz) - 1))
46 static struct erofs_dirent
*find_target_dirent(struct erofs_qstr
*name
,
48 unsigned int dirblksize
,
52 unsigned int startprfx
, endprfx
;
53 struct erofs_dirent
*const de
= (struct erofs_dirent
*)data
;
55 /* since the 1st dirent has been evaluated previously */
58 startprfx
= endprfx
= 0;
60 while (head
<= back
) {
61 const int mid
= head
+ (back
- head
) / 2;
62 const int nameoff
= nameoff_from_disk(de
[mid
].nameoff
,
64 unsigned int matched
= min(startprfx
, endprfx
);
65 struct erofs_qstr dname
= {
66 .name
= data
+ nameoff
,
67 .end
= mid
>= ndirents
- 1 ?
69 data
+ nameoff_from_disk(de
[mid
+ 1].nameoff
,
73 /* string comparison without already matched prefix */
74 int ret
= erofs_dirnamecmp(name
, &dname
, &matched
);
87 return ERR_PTR(-ENOENT
);
90 static struct page
*find_target_block_classic(struct inode
*dir
,
91 struct erofs_qstr
*name
,
94 unsigned int startprfx
, endprfx
;
96 struct address_space
*const mapping
= dir
->i_mapping
;
97 struct page
*candidate
= ERR_PTR(-ENOENT
);
99 startprfx
= endprfx
= 0;
101 back
= erofs_inode_datablocks(dir
) - 1;
103 while (head
<= back
) {
104 const int mid
= head
+ (back
- head
) / 2;
105 struct page
*page
= read_mapping_page(mapping
, mid
, NULL
);
108 struct erofs_dirent
*de
= kmap_atomic(page
);
109 const int nameoff
= nameoff_from_disk(de
->nameoff
,
111 const int ndirents
= nameoff
/ sizeof(*de
);
113 unsigned int matched
;
114 struct erofs_qstr dname
;
120 "corrupted dir block %d @ nid %llu",
121 mid
, EROFS_I(dir
)->nid
);
123 page
= ERR_PTR(-EFSCORRUPTED
);
127 matched
= min(startprfx
, endprfx
);
129 dname
.name
= (u8
*)de
+ nameoff
;
131 dname
.end
= (u8
*)de
+ EROFS_BLKSIZ
;
133 dname
.end
= (u8
*)de
+
134 nameoff_from_disk(de
[1].nameoff
,
137 /* string comparison without already matched prefix */
138 diff
= erofs_dirnamecmp(name
, &dname
, &matched
);
144 } else if (diff
> 0) {
148 if (!IS_ERR(candidate
))
151 *_ndirents
= ndirents
;
160 out
: /* free if the candidate is valid */
161 if (!IS_ERR(candidate
))
168 int erofs_namei(struct inode
*dir
,
170 erofs_nid_t
*nid
, unsigned int *d_type
)
175 struct erofs_dirent
*de
;
176 struct erofs_qstr qn
;
181 qn
.name
= name
->name
;
182 qn
.end
= name
->name
+ name
->len
;
185 page
= find_target_block_classic(dir
, &qn
, &ndirents
);
188 return PTR_ERR(page
);
190 data
= kmap_atomic(page
);
191 /* the target page has been mapped */
193 de
= find_target_dirent(&qn
, data
, EROFS_BLKSIZ
, ndirents
);
195 de
= (struct erofs_dirent
*)data
;
198 *nid
= le64_to_cpu(de
->nid
);
199 *d_type
= de
->file_type
;
205 return PTR_ERR_OR_ZERO(de
);
208 /* NOTE: i_mutex is already held by vfs */
209 static struct dentry
*erofs_lookup(struct inode
*dir
,
210 struct dentry
*dentry
,
218 DBG_BUGON(!d_really_is_negative(dentry
));
219 /* dentry must be unhashed in lookup, no need to worry about */
220 DBG_BUGON(!d_unhashed(dentry
));
222 trace_erofs_lookup(dir
, dentry
, flags
);
224 /* file name exceeds fs limit */
225 if (dentry
->d_name
.len
> EROFS_NAME_LEN
)
226 return ERR_PTR(-ENAMETOOLONG
);
228 /* false uninitialized warnings on gcc 4.8.x */
229 err
= erofs_namei(dir
, &dentry
->d_name
, &nid
, &d_type
);
231 if (err
== -ENOENT
) {
232 /* negative dentry */
235 inode
= ERR_PTR(err
);
237 erofs_dbg("%s, %s (nid %llu) found, d_type %u", __func__
,
238 dentry
->d_name
.name
, nid
, d_type
);
239 inode
= erofs_iget(dir
->i_sb
, nid
, d_type
== FT_DIR
);
241 return d_splice_alias(inode
, dentry
);
244 const struct inode_operations erofs_dir_iops
= {
245 .lookup
= erofs_lookup
,
246 .getattr
= erofs_getattr
,
247 .listxattr
= erofs_listxattr
,
248 .get_acl
= erofs_get_acl
,