Merge tag 'pci-v6.16-fixes-3' of git://git.kernel.org/pub/scm/linux/kernel/git/pci/pci
[linux-block.git] / fs / erofs / namei.c
CommitLineData
29b24f6c 1// SPDX-License-Identifier: GPL-2.0-only
d72d1ce6 2/*
d72d1ce6 3 * Copyright (C) 2017-2018 HUAWEI, Inc.
592e7cd0 4 * https://www.huawei.com/
500edd09 5 * Copyright (C) 2022, Alibaba Cloud
d72d1ce6 6 */
b17500a0 7#include "xattr.h"
13f06f48
CY
8#include <trace/events/erofs.h>
9
419d6efc
GX
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' */
99634bf3
GX
16static inline int erofs_dirnamecmp(const struct erofs_qstr *qn,
17 const struct erofs_qstr *qd,
18 unsigned int *matched)
d72d1ce6 19{
419d6efc
GX
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;
d72d1ce6 35 }
419d6efc 36 ++i;
d72d1ce6 37 }
419d6efc
GX
38 *matched = i;
39 /* See comments in __d_alloc on the terminating NUL character */
40 return qn->name[i] == '\0' ? 0 : 1;
d72d1ce6
GX
41}
42
419d6efc
GX
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)
d72d1ce6 49{
419d6efc 50 int head, back;
7dd68b14 51 unsigned int startprfx, endprfx;
d72d1ce6
GX
52 struct erofs_dirent *const de = (struct erofs_dirent *)data;
53
419d6efc
GX
54 /* since the 1st dirent has been evaluated previously */
55 head = 1;
d72d1ce6
GX
56 back = ndirents - 1;
57 startprfx = endprfx = 0;
58
59 while (head <= back) {
419d6efc
GX
60 const int mid = head + (back - head) / 2;
61 const int nameoff = nameoff_from_disk(de[mid].nameoff,
62 dirblksize);
7dd68b14 63 unsigned int matched = min(startprfx, endprfx);
419d6efc
GX
64 struct erofs_qstr dname = {
65 .name = data + nameoff,
8d8a09b0 66 .end = mid >= ndirents - 1 ?
419d6efc
GX
67 data + dirblksize :
68 data + nameoff_from_disk(de[mid + 1].nameoff,
69 dirblksize)
70 };
d72d1ce6
GX
71
72 /* string comparison without already matched prefix */
99634bf3 73 int ret = erofs_dirnamecmp(name, &dname, &matched);
d72d1ce6 74
8d8a09b0 75 if (!ret) {
d72d1ce6 76 return de + mid;
419d6efc 77 } else if (ret > 0) {
d72d1ce6
GX
78 head = mid + 1;
79 startprfx = matched;
419d6efc 80 } else {
d72d1ce6
GX
81 back = mid - 1;
82 endprfx = matched;
83 }
84 }
85
86 return ERR_PTR(-ENOENT);
87}
88
4efdec36
GX
89static void *erofs_find_target_block(struct erofs_buf *target,
90 struct inode *dir, struct erofs_qstr *name, int *_ndirents)
d72d1ce6 91{
3acea5fc
JX
92 unsigned int bsz = i_blocksize(dir);
93 int head = 0, back = erofs_iblks(dir) - 1;
4efdec36 94 unsigned int startprfx = 0, endprfx = 0;
500edd09 95 void *candidate = ERR_PTR(-ENOENT);
d72d1ce6 96
d72d1ce6 97 while (head <= back) {
419d6efc 98 const int mid = head + (back - head) / 2;
500edd09
GX
99 struct erofs_buf buf = __EROFS_BUF_INITIALIZER;
100 struct erofs_dirent *de;
d72d1ce6 101
958b9f85 102 buf.mapping = dir->i_mapping;
706e50e4 103 de = erofs_bread(&buf, erofs_pos(dir->i_sb, mid), true);
500edd09 104 if (!IS_ERR(de)) {
3acea5fc 105 const int nameoff = nameoff_from_disk(de->nameoff, bsz);
419d6efc
GX
106 const int ndirents = nameoff / sizeof(*de);
107 int diff;
108 unsigned int matched;
109 struct erofs_qstr dname;
d72d1ce6 110
8d8a09b0 111 if (!ndirents) {
500edd09 112 erofs_put_metabuf(&buf);
4f761fa2
GX
113 erofs_err(dir->i_sb,
114 "corrupted dir block %d @ nid %llu",
115 mid, EROFS_I(dir)->nid);
a6b9b1d5 116 DBG_BUGON(1);
500edd09 117 de = ERR_PTR(-EFSCORRUPTED);
419d6efc
GX
118 goto out;
119 }
d72d1ce6
GX
120
121 matched = min(startprfx, endprfx);
122
123 dname.name = (u8 *)de + nameoff;
419d6efc 124 if (ndirents == 1)
3acea5fc 125 dname.end = (u8 *)de + bsz;
419d6efc
GX
126 else
127 dname.end = (u8 *)de +
3acea5fc 128 nameoff_from_disk(de[1].nameoff, bsz);
d72d1ce6
GX
129
130 /* string comparison without already matched prefix */
99634bf3 131 diff = erofs_dirnamecmp(name, &dname, &matched);
d72d1ce6 132
56ee7db3 133 if (diff < 0) {
500edd09 134 erofs_put_metabuf(&buf);
d72d1ce6
GX
135 back = mid - 1;
136 endprfx = matched;
56ee7db3
SD
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;
d72d1ce6 146 }
56ee7db3
SD
147 head = mid + 1;
148 startprfx = matched;
149 candidate = de;
150 *_ndirents = ndirents;
419d6efc 151 continue;
d72d1ce6 152 }
419d6efc
GX
153out: /* free if the candidate is valid */
154 if (!IS_ERR(candidate))
500edd09
GX
155 erofs_put_metabuf(target);
156 return de;
d72d1ce6 157 }
d72d1ce6
GX
158 return candidate;
159}
160
3e917cc3
HL
161int erofs_namei(struct inode *dir, const struct qstr *name, erofs_nid_t *nid,
162 unsigned int *d_type)
d72d1ce6 163{
419d6efc 164 int ndirents;
500edd09 165 struct erofs_buf buf = __EROFS_BUF_INITIALIZER;
d72d1ce6 166 struct erofs_dirent *de;
419d6efc 167 struct erofs_qstr qn;
d72d1ce6 168
8d8a09b0 169 if (!dir->i_size)
d72d1ce6
GX
170 return -ENOENT;
171
419d6efc
GX
172 qn.name = name->name;
173 qn.end = name->name + name->len;
958b9f85 174 buf.mapping = dir->i_mapping;
419d6efc
GX
175
176 ndirents = 0;
4efdec36 177 de = erofs_find_target_block(&buf, dir, &qn, &ndirents);
500edd09
GX
178 if (IS_ERR(de))
179 return PTR_ERR(de);
d72d1ce6 180
419d6efc 181 if (ndirents)
3acea5fc
JX
182 de = find_target_dirent(&qn, (u8 *)de, i_blocksize(dir),
183 ndirents);
d72d1ce6 184
7fadcdce 185 if (!IS_ERR(de)) {
d72d1ce6
GX
186 *nid = le64_to_cpu(de->nid);
187 *d_type = de->file_type;
188 }
500edd09 189 erofs_put_metabuf(&buf);
38c6aa21 190 return PTR_ERR_OR_ZERO(de);
d72d1ce6
GX
191}
192
53a7f996 193static struct dentry *erofs_lookup(struct inode *dir, struct dentry *dentry,
447a3621 194 unsigned int flags)
d72d1ce6
GX
195{
196 int err;
197 erofs_nid_t nid;
7dd68b14 198 unsigned int d_type;
d72d1ce6
GX
199 struct inode *inode;
200
13f06f48
CY
201 trace_erofs_lookup(dir, dentry, flags);
202
8d8a09b0 203 if (dentry->d_name.len > EROFS_NAME_LEN)
d72d1ce6
GX
204 return ERR_PTR(-ENAMETOOLONG);
205
d72d1ce6
GX
206 err = erofs_namei(dir, &dentry->d_name, &nid, &d_type);
207
10656f9c 208 if (err == -ENOENT)
d72d1ce6
GX
209 /* negative dentry */
210 inode = NULL;
10656f9c 211 else if (err)
8300807f 212 inode = ERR_PTR(err);
10656f9c 213 else
312fe643 214 inode = erofs_iget(dir->i_sb, nid);
d72d1ce6
GX
215 return d_splice_alias(inode, dentry);
216}
217
218const struct inode_operations erofs_dir_iops = {
219 .lookup = erofs_lookup,
89f27ede 220 .getattr = erofs_getattr,
b17500a0 221 .listxattr = erofs_listxattr,
cac2f8b8 222 .get_inode_acl = erofs_get_acl,
eadcd6b5 223 .fiemap = erofs_fiemap,
d72d1ce6 224};