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