1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * linux/fs/hfsplus/bfind.c
4 *
5 * Copyright (C) 2001
6 * Brad Boyer (flar@allandria.com)
7 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 *
9 * Search routines for btrees
10 */
11
12 #include <linux/slab.h>
13 #include "hfsplus_fs.h"
14
hfs_find_init(struct hfs_btree * tree,struct hfs_find_data * fd)15 int 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 ptr = kzalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
22 if (!ptr)
23 return -ENOMEM;
24 fd->search_key = ptr;
25 fd->key = ptr + tree->max_key_len + 2;
26 hfs_dbg("cnid %d, caller %ps\n",
27 tree->cnid, __builtin_return_address(0));
28 mutex_lock_nested(&tree->tree_lock,
29 hfsplus_btree_lock_class(tree));
30 return 0;
31 }
32
hfs_find_exit(struct hfs_find_data * fd)33 void hfs_find_exit(struct hfs_find_data *fd)
34 {
35 hfs_bnode_put(fd->bnode);
36 kfree(fd->search_key);
37 hfs_dbg("cnid %d, caller %ps\n",
38 fd->tree->cnid, __builtin_return_address(0));
39 mutex_unlock(&fd->tree->tree_lock);
40 fd->tree = NULL;
41 }
42
hfs_find_1st_rec_by_cnid(struct hfs_bnode * bnode,struct hfs_find_data * fd,int * begin,int * end,int * cur_rec)43 int hfs_find_1st_rec_by_cnid(struct hfs_bnode *bnode,
44 struct hfs_find_data *fd,
45 int *begin,
46 int *end,
47 int *cur_rec)
48 {
49 __be32 cur_cnid;
50 __be32 search_cnid;
51
52 if (bnode->tree->cnid == HFSPLUS_EXT_CNID) {
53 cur_cnid = fd->key->ext.cnid;
54 search_cnid = fd->search_key->ext.cnid;
55 } else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) {
56 cur_cnid = fd->key->cat.parent;
57 search_cnid = fd->search_key->cat.parent;
58 } else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) {
59 cur_cnid = fd->key->attr.cnid;
60 search_cnid = fd->search_key->attr.cnid;
61 } else {
62 cur_cnid = 0; /* used-uninitialized warning */
63 search_cnid = 0;
64 BUG();
65 }
66
67 if (cur_cnid == search_cnid) {
68 (*end) = (*cur_rec);
69 if ((*begin) == (*end))
70 return 1;
71 } else {
72 if (be32_to_cpu(cur_cnid) < be32_to_cpu(search_cnid))
73 (*begin) = (*cur_rec) + 1;
74 else
75 (*end) = (*cur_rec) - 1;
76 }
77
78 return 0;
79 }
80
hfs_find_rec_by_key(struct hfs_bnode * bnode,struct hfs_find_data * fd,int * begin,int * end,int * cur_rec)81 int hfs_find_rec_by_key(struct hfs_bnode *bnode,
82 struct hfs_find_data *fd,
83 int *begin,
84 int *end,
85 int *cur_rec)
86 {
87 int cmpval;
88
89 cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
90 if (!cmpval) {
91 (*end) = (*cur_rec);
92 return 1;
93 }
94 if (cmpval < 0)
95 (*begin) = (*cur_rec) + 1;
96 else
97 *(end) = (*cur_rec) - 1;
98
99 return 0;
100 }
101
102 /* Find the record in bnode that best matches key (not greater than...)*/
__hfs_brec_find(struct hfs_bnode * bnode,struct hfs_find_data * fd,search_strategy_t rec_found)103 int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,
104 search_strategy_t rec_found)
105 {
106 u16 off, len, keylen;
107 int rec;
108 int b, e;
109 int res;
110
111 BUG_ON(!rec_found);
112 b = 0;
113 e = bnode->num_recs - 1;
114 res = -ENOENT;
115 do {
116 rec = (e + b) / 2;
117 len = hfs_brec_lenoff(bnode, rec, &off);
118 keylen = hfs_brec_keylen(bnode, rec);
119 if (keylen == 0) {
120 res = -EINVAL;
121 goto fail;
122 }
123 hfs_bnode_read(bnode, fd->key, off, keylen);
124 if (rec_found(bnode, fd, &b, &e, &rec)) {
125 res = 0;
126 goto done;
127 }
128 } while (b <= e);
129
130 if (rec != e && e >= 0) {
131 len = hfs_brec_lenoff(bnode, e, &off);
132 keylen = hfs_brec_keylen(bnode, e);
133 if (keylen == 0) {
134 res = -EINVAL;
135 goto fail;
136 }
137 hfs_bnode_read(bnode, fd->key, off, keylen);
138 }
139
140 done:
141 fd->record = e;
142 fd->keyoffset = off;
143 fd->keylength = keylen;
144 fd->entryoffset = off + keylen;
145 fd->entrylength = len - keylen;
146
147 fail:
148 return res;
149 }
150
151 /* Traverse a B*Tree from the root to a leaf finding best fit to key */
152 /* Return allocated copy of node found, set recnum to best record */
hfs_brec_find(struct hfs_find_data * fd,search_strategy_t do_key_compare)153 int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare)
154 {
155 struct hfs_btree *tree;
156 struct hfs_bnode *bnode;
157 u32 nidx, parent;
158 __be32 data;
159 int height, res;
160
161 fd->record = -1;
162 fd->keyoffset = -1;
163 fd->keylength = -1;
164 fd->entryoffset = -1;
165 fd->entrylength = -1;
166
167 tree = fd->tree;
168 if (fd->bnode)
169 hfs_bnode_put(fd->bnode);
170 fd->bnode = NULL;
171 nidx = tree->root;
172 if (!nidx)
173 return -ENOENT;
174 height = tree->depth;
175 res = 0;
176 parent = 0;
177 for (;;) {
178 bnode = hfs_bnode_find(tree, nidx);
179 if (IS_ERR(bnode)) {
180 res = PTR_ERR(bnode);
181 bnode = NULL;
182 break;
183 }
184 if (bnode->height != height)
185 goto invalid;
186 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
187 goto invalid;
188 bnode->parent = parent;
189
190 res = __hfs_brec_find(bnode, fd, do_key_compare);
191 if (!height)
192 break;
193 if (fd->record < 0)
194 goto release;
195
196 parent = nidx;
197 hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
198 nidx = be32_to_cpu(data);
199 hfs_bnode_put(bnode);
200 }
201 fd->bnode = bnode;
202 return res;
203
204 invalid:
205 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
206 height, bnode->height, bnode->type, nidx, parent);
207 res = -EIO;
208 release:
209 hfs_bnode_put(bnode);
210 return res;
211 }
212
hfs_brec_read(struct hfs_find_data * fd,void * rec,int rec_len)213 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
214 {
215 int res;
216
217 res = hfs_brec_find(fd, hfs_find_rec_by_key);
218 if (res)
219 return res;
220 if (fd->entrylength > rec_len)
221 return -EINVAL;
222 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
223 return 0;
224 }
225
hfs_brec_goto(struct hfs_find_data * fd,int cnt)226 int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
227 {
228 struct hfs_btree *tree;
229 struct hfs_bnode *bnode;
230 int idx, res = 0;
231 u16 off, len, keylen;
232
233 bnode = fd->bnode;
234 tree = bnode->tree;
235
236 if (cnt < 0) {
237 cnt = -cnt;
238 while (cnt > fd->record) {
239 cnt -= fd->record + 1;
240 fd->record = bnode->num_recs - 1;
241 idx = bnode->prev;
242 if (!idx) {
243 res = -ENOENT;
244 goto out;
245 }
246 hfs_bnode_put(bnode);
247 bnode = hfs_bnode_find(tree, idx);
248 if (IS_ERR(bnode)) {
249 res = PTR_ERR(bnode);
250 bnode = NULL;
251 goto out;
252 }
253 }
254 fd->record -= cnt;
255 } else {
256 while (cnt >= bnode->num_recs - fd->record) {
257 cnt -= bnode->num_recs - fd->record;
258 fd->record = 0;
259 idx = bnode->next;
260 if (!idx) {
261 res = -ENOENT;
262 goto out;
263 }
264 hfs_bnode_put(bnode);
265 bnode = hfs_bnode_find(tree, idx);
266 if (IS_ERR(bnode)) {
267 res = PTR_ERR(bnode);
268 bnode = NULL;
269 goto out;
270 }
271 }
272 fd->record += cnt;
273 }
274
275 len = hfs_brec_lenoff(bnode, fd->record, &off);
276 keylen = hfs_brec_keylen(bnode, fd->record);
277 if (keylen == 0) {
278 res = -EINVAL;
279 goto out;
280 }
281 fd->keyoffset = off;
282 fd->keylength = keylen;
283 fd->entryoffset = off + keylen;
284 fd->entrylength = len - keylen;
285 hfs_bnode_read(bnode, fd->key, off, keylen);
286 out:
287 fd->bnode = bnode;
288 return res;
289 }
290