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
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 = kmalloc(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(BNODE_REFS, "find_init: %d (%p)\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
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(BNODE_REFS, "find_exit: %d (%p)\n",
38 fd->tree->cnid, __builtin_return_address(0));
39 mutex_unlock(&fd->tree->tree_lock);
40 fd->tree = NULL;
41 }
42
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
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...)*/
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 */
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 tree = fd->tree;
162 if (fd->bnode)
163 hfs_bnode_put(fd->bnode);
164 fd->bnode = NULL;
165 nidx = tree->root;
166 if (!nidx)
167 return -ENOENT;
168 height = tree->depth;
169 res = 0;
170 parent = 0;
171 for (;;) {
172 bnode = hfs_bnode_find(tree, nidx);
173 if (IS_ERR(bnode)) {
174 res = PTR_ERR(bnode);
175 bnode = NULL;
176 break;
177 }
178 if (bnode->height != height)
179 goto invalid;
180 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
181 goto invalid;
182 bnode->parent = parent;
183
184 res = __hfs_brec_find(bnode, fd, do_key_compare);
185 if (!height)
186 break;
187 if (fd->record < 0)
188 goto release;
189
190 parent = nidx;
191 hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
192 nidx = be32_to_cpu(data);
193 hfs_bnode_put(bnode);
194 }
195 fd->bnode = bnode;
196 return res;
197
198 invalid:
199 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
200 height, bnode->height, bnode->type, nidx, parent);
201 res = -EIO;
202 release:
203 hfs_bnode_put(bnode);
204 return res;
205 }
206
207 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
208 {
209 int res;
210
211 res = hfs_brec_find(fd, hfs_find_rec_by_key);
212 if (res)
213 return res;
214 if (fd->entrylength > rec_len)
215 return -EINVAL;
216 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
217 return 0;
218 }
219
220 int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
221 {
222 struct hfs_btree *tree;
223 struct hfs_bnode *bnode;
224 int idx, res = 0;
225 u16 off, len, keylen;
226
227 bnode = fd->bnode;
228 tree = bnode->tree;
229
230 if (cnt < 0) {
231 cnt = -cnt;
232 while (cnt > fd->record) {
233 cnt -= fd->record + 1;
234 fd->record = bnode->num_recs - 1;
235 idx = bnode->prev;
236 if (!idx) {
237 res = -ENOENT;
238 goto out;
239 }
240 hfs_bnode_put(bnode);
241 bnode = hfs_bnode_find(tree, idx);
242 if (IS_ERR(bnode)) {
243 res = PTR_ERR(bnode);
244 bnode = NULL;
245 goto out;
246 }
247 }
248 fd->record -= cnt;
249 } else {
250 while (cnt >= bnode->num_recs - fd->record) {
251 cnt -= bnode->num_recs - fd->record;
252 fd->record = 0;
253 idx = bnode->next;
254 if (!idx) {
255 res = -ENOENT;
256 goto out;
257 }
258 hfs_bnode_put(bnode);
259 bnode = hfs_bnode_find(tree, idx);
260 if (IS_ERR(bnode)) {
261 res = PTR_ERR(bnode);
262 bnode = NULL;
263 goto out;
264 }
265 }
266 fd->record += cnt;
267 }
268
269 len = hfs_brec_lenoff(bnode, fd->record, &off);
270 keylen = hfs_brec_keylen(bnode, fd->record);
271 if (keylen == 0) {
272 res = -EINVAL;
273 goto out;
274 }
275 fd->keyoffset = off;
276 fd->keylength = keylen;
277 fd->entryoffset = off + keylen;
278 fd->entrylength = len - keylen;
279 hfs_bnode_read(bnode, fd->key, off, keylen);
280 out:
281 fd->bnode = bnode;
282 return res;
283 }
284
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.