projects/linux·blob master · refs

343 lines · 7.5 KiB

1// SPDX-License-Identifier: GPL-2.0
2/*
3 * linux/fs/hfsplus/bfind.c
4 *
5 * Copyright (C) 2001
6 * Brad Boyer ([email protected])
7 * (C) 2003 Ardis Technologies <[email protected]>
8 *
9 * Search routines for btrees
10 */
11
12#include <linux/slab.h>
13#include "hfsplus_fs.h"
14
15int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
16{
17 void *ptr;
18
19 fd->tree = tree;
20 fd->bnode = NULL;
21 hfs_find_result_init(fd);
22 ptr = kzalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
23 if (!ptr)
24 return -ENOMEM;
25 fd->search_key = ptr;
26 fd->key = ptr + tree->max_key_len + 2;
27 hfs_dbg("cnid %d, caller %ps\n",
28 tree->cnid, __builtin_return_address(0));
29 mutex_lock_nested(&tree->tree_lock,
30 hfsplus_btree_lock_class(tree));
31 return 0;
32}
33
34void hfs_find_exit(struct hfs_find_data *fd)
35{
36 hfs_bnode_put(fd->bnode);
37 kfree(fd->search_key);
38 hfs_dbg("cnid %d, caller %ps\n",
39 fd->tree->cnid, __builtin_return_address(0));
40 mutex_unlock(&fd->tree->tree_lock);
41 fd->tree = NULL;
42}
43
44int hfs_find_1st_rec_by_cnid(struct hfs_bnode *bnode,
45 struct hfs_find_data *fd,
46 int *begin,
47 int *end,
48 int *cur_rec)
49{
50 __be32 cur_cnid;
51 __be32 search_cnid;
52
53 if (bnode->tree->cnid == HFSPLUS_EXT_CNID) {
54 cur_cnid = fd->key->ext.cnid;
55 search_cnid = fd->search_key->ext.cnid;
56 } else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) {
57 cur_cnid = fd->key->cat.parent;
58 search_cnid = fd->search_key->cat.parent;
59 } else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) {
60 cur_cnid = fd->key->attr.cnid;
61 search_cnid = fd->search_key->attr.cnid;
62 } else {
63 cur_cnid = 0; /* used-uninitialized warning */
64 search_cnid = 0;
65 BUG();
66 }
67
68 if (cur_cnid == search_cnid) {
69 (*end) = (*cur_rec);
70 if ((*begin) == (*end))
71 return 1;
72 } else {
73 if (be32_to_cpu(cur_cnid) < be32_to_cpu(search_cnid))
74 (*begin) = (*cur_rec) + 1;
75 else
76 (*end) = (*cur_rec) - 1;
77 }
78
79 return 0;
80}
81
82int hfs_find_rec_by_key(struct hfs_bnode *bnode,
83 struct hfs_find_data *fd,
84 int *begin,
85 int *end,
86 int *cur_rec)
87{
88 int cmpval;
89
90 cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
91 if (!cmpval) {
92 (*end) = (*cur_rec);
93 return 1;
94 }
95 if (cmpval < 0)
96 (*begin) = (*cur_rec) + 1;
97 else
98 *(end) = (*cur_rec) - 1;
99
100 return 0;
101}
102
103/* Find the record in bnode that best matches key (not greater than...)*/
104int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,
105 search_strategy_t rec_found)
106{
107 u16 off, len, keylen;
108 int rec;
109 int b, e;
110 int res = -ENOENT;
111
112 BUG_ON(!rec_found);
113 hfs_find_result_init(fd);
114 if (hfs_bnode_num_recs_invalid(bnode))
115 goto fail;
116
117 b = 0;
118 e = bnode->num_recs - 1;
119 do {
120 rec = (e + b) / 2;
121 len = hfs_brec_lenoff(bnode, rec, &off);
122 keylen = hfs_brec_keylen(bnode, rec);
123 if (hfs_brec_len_invalid(bnode, len) ||
124 hfs_brec_len_invalid(bnode, keylen)) {
125 res = -EINVAL;
126 goto fail;
127 }
128 hfs_bnode_read(bnode, fd->key, off, keylen);
129 if (rec_found(bnode, fd, &b, &e, &rec)) {
130 res = 0;
131 goto done;
132 }
133 } while (b <= e);
134
135 if (rec != e && e >= 0) {
136 len = hfs_brec_lenoff(bnode, e, &off);
137 keylen = hfs_brec_keylen(bnode, e);
138 if (hfs_brec_len_invalid(bnode, keylen) ||
139 hfs_brec_len_invalid(bnode, len)) {
140 res = -EINVAL;
141 goto fail;
142 }
143 hfs_bnode_read(bnode, fd->key, off, keylen);
144 }
145
146done:
147 fd->record = e;
148 fd->keyoffset = off;
149 fd->keylength = keylen;
150 fd->entryoffset = off + keylen;
151 fd->entrylength = len - keylen;
152
153fail:
154 return res;
155}
156
157/* Traverse a B*Tree from the root to a leaf finding best fit to key */
158/* Return allocated copy of node found, set recnum to best record */
159int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare)
160{
161 struct hfs_btree *tree;
162 struct hfs_bnode *bnode;
163 u32 nidx, parent;
164 __be32 data;
165 int height, res;
166
167 hfs_find_result_init(fd);
168
169 tree = fd->tree;
170 if (fd->bnode)
171 hfs_bnode_put(fd->bnode);
172 fd->bnode = NULL;
173 nidx = tree->root;
174 if (!nidx)
175 return -ENOENT;
176 height = tree->depth;
177 res = 0;
178 parent = 0;
179 for (;;) {
180 bnode = hfs_bnode_find(tree, nidx);
181 if (IS_ERR(bnode)) {
182 res = PTR_ERR(bnode);
183 bnode = NULL;
184 break;
185 }
186 if (bnode->height != height)
187 goto invalid;
188 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
189 goto invalid;
190 bnode->parent = parent;
191
192 res = __hfs_brec_find(bnode, fd, do_key_compare);
193 if (!height)
194 break;
195 if (fd->record < 0)
196 goto release;
197
198 parent = nidx;
199 hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
200 nidx = be32_to_cpu(data);
201 hfs_bnode_put(bnode);
202 }
203 fd->bnode = bnode;
204 return res;
205
206invalid:
207 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
208 height, bnode->height, bnode->type, nidx, parent);
209 res = -EIO;
210release:
211 hfs_bnode_put(bnode);
212 return res;
213}
214
215int hfs_brec_read(struct hfs_find_data *fd, void *rec, u32 rec_len)
216{
217 int res;
218
219 res = hfs_brec_find(fd, hfs_find_rec_by_key);
220 if (res)
221 return res;
222 if (fd->entrylength > rec_len)
223 return -EINVAL;
224 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
225 return 0;
226}
227
228int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
229{
230 struct hfs_btree *tree;
231 struct hfs_bnode *bnode;
232 int idx, res = 0;
233 u16 off, len, keylen;
234
235 bnode = fd->bnode;
236 tree = bnode->tree;
237
238 if (cnt < 0) {
239 cnt = -cnt;
240 while (cnt > fd->record) {
241 cnt -= fd->record + 1;
242 fd->record = bnode->num_recs - 1;
243 idx = bnode->prev;
244 if (!idx) {
245 res = -ENOENT;
246 goto out;
247 }
248 hfs_bnode_put(bnode);
249 bnode = hfs_bnode_find(tree, idx);
250 if (IS_ERR(bnode)) {
251 res = PTR_ERR(bnode);
252 bnode = NULL;
253 goto out;
254 }
255 }
256 fd->record -= cnt;
257 } else {
258 while (cnt >= bnode->num_recs - fd->record) {
259 cnt -= bnode->num_recs - fd->record;
260 fd->record = 0;
261 idx = bnode->next;
262 if (!idx) {
263 res = -ENOENT;
264 goto out;
265 }
266 hfs_bnode_put(bnode);
267 bnode = hfs_bnode_find(tree, idx);
268 if (IS_ERR(bnode)) {
269 res = PTR_ERR(bnode);
270 bnode = NULL;
271 goto out;
272 }
273 }
274 fd->record += cnt;
275 }
276
277 len = hfs_brec_lenoff(bnode, fd->record, &off);
278 keylen = hfs_brec_keylen(bnode, fd->record);
279 if (hfs_brec_len_invalid(bnode, len) ||
280 hfs_brec_len_invalid(bnode, keylen)) {
281 res = -EINVAL;
282 goto out;
283 }
284 fd->keyoffset = off;
285 fd->keylength = keylen;
286 fd->entryoffset = off + keylen;
287 fd->entrylength = len - keylen;
288 hfs_bnode_read(bnode, fd->key, off, keylen);
289out:
290 fd->bnode = bnode;
291 return res;
292}
293
294/**
295 * hfsplus_brec_read_cat - read and validate a catalog record
296 * @fd: find data structure
297 * @entry: pointer to catalog entry to read into
298 *
299 * Reads a catalog record and validates its size matches the expected
300 * size based on the record type.
301 *
302 * Returns 0 on success, or negative error code on failure.
303 */
304int hfsplus_brec_read_cat(struct hfs_find_data *fd, hfsplus_cat_entry *entry)
305{
306 int res;
307 u32 expected_size;
308
309 res = hfs_brec_read(fd, entry, sizeof(hfsplus_cat_entry));
310 if (res)
311 return res;
312
313 /* Validate catalog record size based on type */
314 switch (be16_to_cpu(entry->type)) {
315 case HFSPLUS_FOLDER:
316 expected_size = sizeof(struct hfsplus_cat_folder);
317 break;
318 case HFSPLUS_FILE:
319 expected_size = sizeof(struct hfsplus_cat_file);
320 break;
321 case HFSPLUS_FOLDER_THREAD:
322 case HFSPLUS_FILE_THREAD:
323 /* Ensure we have at least the fixed fields before reading nodeName.length */
324 if (fd->entrylength < HFSPLUS_MIN_THREAD_SZ) {
325 pr_err("thread record too short (got %u)\n", fd->entrylength);
326 return -EIO;
327 }
328 expected_size = hfsplus_cat_thread_size(&entry->thread);
329 break;
330 default:
331 pr_err("unknown catalog record type %d\n",
332 be16_to_cpu(entry->type));
333 return -EIO;
334 }
335
336 if (fd->entrylength != expected_size) {
337 pr_err("catalog record size mismatch (type %d, got %u, expected %u)\n",
338 be16_to_cpu(entry->type), fd->entrylength, expected_size);
339 return -EIO;
340 }
341
342 return 0;
343}