Loading...
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
9#include <trace/events/erofs.h>
10
11struct erofs_qstr {
12 const unsigned char *name;
13 const unsigned char *end;
14};
15
16/* based on the end of qn is accurate and it must have the trailing '\0' */
17static inline int erofs_dirnamecmp(const struct erofs_qstr *qn,
18 const struct erofs_qstr *qd,
19 unsigned int *matched)
20{
21 unsigned int i = *matched;
22
23 /*
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).
27 */
28 DBG_BUGON(qd->name > qd->end);
29
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]) {
34 *matched = i;
35 return qn->name[i] > qd->name[i] ? 1 : -1;
36 }
37 ++i;
38 }
39 *matched = i;
40 /* See comments in __d_alloc on the terminating NUL character */
41 return qn->name[i] == '\0' ? 0 : 1;
42}
43
44#define nameoff_from_disk(off, sz) (le16_to_cpu(off) & ((sz) - 1))
45
46static struct erofs_dirent *find_target_dirent(struct erofs_qstr *name,
47 u8 *data,
48 unsigned int dirblksize,
49 const int ndirents)
50{
51 int head, back;
52 unsigned int startprfx, endprfx;
53 struct erofs_dirent *const de = (struct erofs_dirent *)data;
54
55 /* since the 1st dirent has been evaluated previously */
56 head = 1;
57 back = ndirents - 1;
58 startprfx = endprfx = 0;
59
60 while (head <= back) {
61 const int mid = head + (back - head) / 2;
62 const int nameoff = nameoff_from_disk(de[mid].nameoff,
63 dirblksize);
64 unsigned int matched = min(startprfx, endprfx);
65 struct erofs_qstr dname = {
66 .name = data + nameoff,
67 .end = mid >= ndirents - 1 ?
68 data + dirblksize :
69 data + nameoff_from_disk(de[mid + 1].nameoff,
70 dirblksize)
71 };
72
73 /* string comparison without already matched prefix */
74 int ret = erofs_dirnamecmp(name, &dname, &matched);
75
76 if (!ret) {
77 return de + mid;
78 } else if (ret > 0) {
79 head = mid + 1;
80 startprfx = matched;
81 } else {
82 back = mid - 1;
83 endprfx = matched;
84 }
85 }
86
87 return ERR_PTR(-ENOENT);
88}
89
90static void *find_target_block_classic(struct erofs_buf *target,
91 struct inode *dir,
92 struct erofs_qstr *name,
93 int *_ndirents)
94{
95 unsigned int startprfx, endprfx;
96 int head, back;
97 void *candidate = ERR_PTR(-ENOENT);
98
99 startprfx = endprfx = 0;
100 head = 0;
101 back = erofs_inode_datablocks(dir) - 1;
102
103 while (head <= back) {
104 const int mid = head + (back - head) / 2;
105 struct erofs_buf buf = __EROFS_BUF_INITIALIZER;
106 struct erofs_dirent *de;
107
108 de = erofs_bread(&buf, dir, mid, EROFS_KMAP);
109 if (!IS_ERR(de)) {
110 const int nameoff = nameoff_from_disk(de->nameoff,
111 EROFS_BLKSIZ);
112 const int ndirents = nameoff / sizeof(*de);
113 int diff;
114 unsigned int matched;
115 struct erofs_qstr dname;
116
117 if (!ndirents) {
118 erofs_put_metabuf(&buf);
119 erofs_err(dir->i_sb,
120 "corrupted dir block %d @ nid %llu",
121 mid, EROFS_I(dir)->nid);
122 DBG_BUGON(1);
123 de = ERR_PTR(-EFSCORRUPTED);
124 goto out;
125 }
126
127 matched = min(startprfx, endprfx);
128
129 dname.name = (u8 *)de + nameoff;
130 if (ndirents == 1)
131 dname.end = (u8 *)de + EROFS_BLKSIZ;
132 else
133 dname.end = (u8 *)de +
134 nameoff_from_disk(de[1].nameoff,
135 EROFS_BLKSIZ);
136
137 /* string comparison without already matched prefix */
138 diff = erofs_dirnamecmp(name, &dname, &matched);
139
140 if (!diff) {
141 *_ndirents = 0;
142 goto out;
143 } else if (diff > 0) {
144 head = mid + 1;
145 startprfx = matched;
146
147 if (!IS_ERR(candidate))
148 erofs_put_metabuf(target);
149 *target = buf;
150 candidate = de;
151 *_ndirents = ndirents;
152 } else {
153 erofs_put_metabuf(&buf);
154
155 back = mid - 1;
156 endprfx = matched;
157 }
158 continue;
159 }
160out: /* free if the candidate is valid */
161 if (!IS_ERR(candidate))
162 erofs_put_metabuf(target);
163 return de;
164 }
165 return candidate;
166}
167
168int erofs_namei(struct inode *dir, const struct qstr *name, erofs_nid_t *nid,
169 unsigned int *d_type)
170{
171 int ndirents;
172 struct erofs_buf buf = __EROFS_BUF_INITIALIZER;
173 struct erofs_dirent *de;
174 struct erofs_qstr qn;
175
176 if (!dir->i_size)
177 return -ENOENT;
178
179 qn.name = name->name;
180 qn.end = name->name + name->len;
181
182 ndirents = 0;
183
184 de = find_target_block_classic(&buf, dir, &qn, &ndirents);
185 if (IS_ERR(de))
186 return PTR_ERR(de);
187
188 if (ndirents)
189 de = find_target_dirent(&qn, (u8 *)de, EROFS_BLKSIZ, ndirents);
190
191 if (!IS_ERR(de)) {
192 *nid = le64_to_cpu(de->nid);
193 *d_type = de->file_type;
194 }
195 erofs_put_metabuf(&buf);
196 return PTR_ERR_OR_ZERO(de);
197}
198
199static struct dentry *erofs_lookup(struct inode *dir, struct dentry *dentry,
200 unsigned int flags)
201{
202 int err;
203 erofs_nid_t nid;
204 unsigned int d_type;
205 struct inode *inode;
206
207 trace_erofs_lookup(dir, dentry, flags);
208
209 if (dentry->d_name.len > EROFS_NAME_LEN)
210 return ERR_PTR(-ENAMETOOLONG);
211
212 err = erofs_namei(dir, &dentry->d_name, &nid, &d_type);
213
214 if (err == -ENOENT) {
215 /* negative dentry */
216 inode = NULL;
217 } else if (err) {
218 inode = ERR_PTR(err);
219 } else {
220 erofs_dbg("%s, %pd (nid %llu) found, d_type %u", __func__,
221 dentry, nid, d_type);
222 inode = erofs_iget(dir->i_sb, nid);
223 }
224 return d_splice_alias(inode, dentry);
225}
226
227const struct inode_operations erofs_dir_iops = {
228 .lookup = erofs_lookup,
229 .getattr = erofs_getattr,
230 .listxattr = erofs_listxattr,
231 .get_inode_acl = erofs_get_acl,
232 .fiemap = erofs_fiemap,
233};
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
10struct 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' */
16static 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
45static 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(name, &dname, &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(-ENOENT);
87}
88
89static 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(dir);
93 int head = 0, back = erofs_iblks(dir) - 1;
94 unsigned int startprfx = 0, endprfx = 0;
95 void *candidate = ERR_PTR(-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.mapping = dir->i_mapping;
103 de = erofs_bread(&buf, erofs_pos(dir->i_sb, mid), EROFS_KMAP);
104 if (!IS_ERR(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);
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(-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(name, &dname, &matched);
132
133 if (diff < 0) {
134 erofs_put_metabuf(&buf);
135 back = mid - 1;
136 endprfx = matched;
137 continue;
138 }
139
140 if (!IS_ERR(candidate))
141 erofs_put_metabuf(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 }
153out: /* free if the candidate is valid */
154 if (!IS_ERR(candidate))
155 erofs_put_metabuf(target);
156 return de;
157 }
158 return candidate;
159}
160
161int 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.mapping = dir->i_mapping;
175
176 ndirents = 0;
177 de = erofs_find_target_block(&buf, dir, &qn, &ndirents);
178 if (IS_ERR(de))
179 return PTR_ERR(de);
180
181 if (ndirents)
182 de = find_target_dirent(&qn, (u8 *)de, i_blocksize(dir),
183 ndirents);
184
185 if (!IS_ERR(de)) {
186 *nid = le64_to_cpu(de->nid);
187 *d_type = de->file_type;
188 }
189 erofs_put_metabuf(&buf);
190 return PTR_ERR_OR_ZERO(de);
191}
192
193static 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(-ENAMETOOLONG);
205
206 err = erofs_namei(dir, &dentry->d_name, &nid, &d_type);
207
208 if (err == -ENOENT)
209 /* negative dentry */
210 inode = NULL;
211 else if (err)
212 inode = ERR_PTR(err);
213 else
214 inode = erofs_iget(dir->i_sb, nid);
215 return d_splice_alias(inode, dentry);
216}
217
218const 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};