1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * linux/fs/hfs/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 "btree.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 if (!tree)
20 return -EINVAL;
21 fd->tree = tree;
22 fd->bnode = NULL;
23 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
24 if (!ptr)
25 return -ENOMEM;
26 fd->search_key = ptr;
27 fd->key = ptr + tree->max_key_len + 2;
28 hfs_dbg(BNODE_REFS, "find_init: %d (%p)\n",
29 tree->cnid, __builtin_return_address(0));
30 switch (tree->cnid) {
31 case HFS_CAT_CNID:
32 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX);
33 break;
34 case HFS_EXT_CNID:
35 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX);
36 break;
37 case HFS_ATTR_CNID:
38 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX);
39 break;
40 default:
41 return -EINVAL;
42 }
43 return 0;
44 }
45
hfs_find_exit(struct hfs_find_data * fd)46 void hfs_find_exit(struct hfs_find_data *fd)
47 {
48 hfs_bnode_put(fd->bnode);
49 kfree(fd->search_key);
50 hfs_dbg(BNODE_REFS, "find_exit: %d (%p)\n",
51 fd->tree->cnid, __builtin_return_address(0));
52 mutex_unlock(&fd->tree->tree_lock);
53 fd->tree = NULL;
54 }
55
56 /* Find the record in bnode that best matches key (not greater than...)*/
__hfs_brec_find(struct hfs_bnode * bnode,struct hfs_find_data * fd)57 int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd)
58 {
59 int cmpval;
60 u16 off, len, keylen;
61 int rec;
62 int b, e;
63 int res;
64
65 b = 0;
66 e = bnode->num_recs - 1;
67 res = -ENOENT;
68 do {
69 rec = (e + b) / 2;
70 len = hfs_brec_lenoff(bnode, rec, &off);
71 keylen = hfs_brec_keylen(bnode, rec);
72 if (keylen == 0) {
73 res = -EINVAL;
74 goto fail;
75 }
76 hfs_bnode_read(bnode, fd->key, off, keylen);
77 cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
78 if (!cmpval) {
79 e = rec;
80 res = 0;
81 goto done;
82 }
83 if (cmpval < 0)
84 b = rec + 1;
85 else
86 e = rec - 1;
87 } while (b <= e);
88 if (rec != e && e >= 0) {
89 len = hfs_brec_lenoff(bnode, e, &off);
90 keylen = hfs_brec_keylen(bnode, e);
91 if (keylen == 0) {
92 res = -EINVAL;
93 goto fail;
94 }
95 hfs_bnode_read(bnode, fd->key, off, keylen);
96 }
97 done:
98 fd->record = e;
99 fd->keyoffset = off;
100 fd->keylength = keylen;
101 fd->entryoffset = off + keylen;
102 fd->entrylength = len - keylen;
103 fail:
104 return res;
105 }
106
107 /* Traverse a B*Tree from the root to a leaf finding best fit to key */
108 /* Return allocated copy of node found, set recnum to best record */
hfs_brec_find(struct hfs_find_data * fd)109 int hfs_brec_find(struct hfs_find_data *fd)
110 {
111 struct hfs_btree *tree;
112 struct hfs_bnode *bnode;
113 u32 nidx, parent;
114 __be32 data;
115 int height, res;
116
117 tree = fd->tree;
118 if (fd->bnode)
119 hfs_bnode_put(fd->bnode);
120 fd->bnode = NULL;
121 nidx = tree->root;
122 if (!nidx)
123 return -ENOENT;
124 height = tree->depth;
125 res = 0;
126 parent = 0;
127 for (;;) {
128 bnode = hfs_bnode_find(tree, nidx);
129 if (IS_ERR(bnode)) {
130 res = PTR_ERR(bnode);
131 bnode = NULL;
132 break;
133 }
134 if (bnode->height != height)
135 goto invalid;
136 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
137 goto invalid;
138 bnode->parent = parent;
139
140 res = __hfs_brec_find(bnode, fd);
141 if (!height)
142 break;
143 if (fd->record < 0)
144 goto release;
145
146 parent = nidx;
147 hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
148 nidx = be32_to_cpu(data);
149 hfs_bnode_put(bnode);
150 }
151 fd->bnode = bnode;
152 return res;
153
154 invalid:
155 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
156 height, bnode->height, bnode->type, nidx, parent);
157 res = -EIO;
158 release:
159 hfs_bnode_put(bnode);
160 return res;
161 }
162
hfs_brec_read(struct hfs_find_data * fd,void * rec,int rec_len)163 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
164 {
165 int res;
166
167 res = hfs_brec_find(fd);
168 if (res)
169 return res;
170 if (fd->entrylength > rec_len)
171 return -EINVAL;
172 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
173 return 0;
174 }
175
hfs_brec_goto(struct hfs_find_data * fd,int cnt)176 int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
177 {
178 struct hfs_btree *tree;
179 struct hfs_bnode *bnode;
180 int idx, res = 0;
181 u16 off, len, keylen;
182
183 bnode = fd->bnode;
184 tree = bnode->tree;
185
186 if (cnt < 0) {
187 cnt = -cnt;
188 while (cnt > fd->record) {
189 cnt -= fd->record + 1;
190 fd->record = bnode->num_recs - 1;
191 idx = bnode->prev;
192 if (!idx) {
193 res = -ENOENT;
194 goto out;
195 }
196 hfs_bnode_put(bnode);
197 bnode = hfs_bnode_find(tree, idx);
198 if (IS_ERR(bnode)) {
199 res = PTR_ERR(bnode);
200 bnode = NULL;
201 goto out;
202 }
203 }
204 fd->record -= cnt;
205 } else {
206 while (cnt >= bnode->num_recs - fd->record) {
207 cnt -= bnode->num_recs - fd->record;
208 fd->record = 0;
209 idx = bnode->next;
210 if (!idx) {
211 res = -ENOENT;
212 goto out;
213 }
214 hfs_bnode_put(bnode);
215 bnode = hfs_bnode_find(tree, idx);
216 if (IS_ERR(bnode)) {
217 res = PTR_ERR(bnode);
218 bnode = NULL;
219 goto out;
220 }
221 }
222 fd->record += cnt;
223 }
224
225 len = hfs_brec_lenoff(bnode, fd->record, &off);
226 keylen = hfs_brec_keylen(bnode, fd->record);
227 if (keylen == 0) {
228 res = -EINVAL;
229 goto out;
230 }
231 fd->keyoffset = off;
232 fd->keylength = keylen;
233 fd->entryoffset = off + keylen;
234 fd->entrylength = len - keylen;
235 hfs_bnode_read(bnode, fd->key, off, keylen);
236 out:
237 fd->bnode = bnode;
238 return res;
239 }
240