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 = kmalloc(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(BNODE_REFS, "find_init: %d (%p)\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(BNODE_REFS, "find_exit: %d (%p)\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 tree = fd->tree;
119 if (fd->bnode)
120 hfs_bnode_put(fd->bnode);
121 fd->bnode = NULL;
122 nidx = tree->root;
123 if (!nidx)
124 return -ENOENT;
125 height = tree->depth;
126 res = 0;
127 parent = 0;
128 for (;;) {
129 bnode = hfs_bnode_find(tree, nidx);
130 if (IS_ERR(bnode)) {
131 res = PTR_ERR(bnode);
132 bnode = NULL;
133 break;
134 }
135 if (bnode->height != height)
136 goto invalid;
137 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
138 goto invalid;
139 bnode->parent = parent;
140
141 res = __hfs_brec_find(bnode, fd);
142 if (!height)
143 break;
144 if (fd->record < 0)
145 goto release;
146
147 parent = nidx;
148 hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
149 nidx = be32_to_cpu(data);
150 hfs_bnode_put(bnode);
151 }
152 fd->bnode = bnode;
153 return res;
154
155 invalid:
156 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
157 height, bnode->height, bnode->type, nidx, parent);
158 res = -EIO;
159 release:
160 hfs_bnode_put(bnode);
161 return res;
162 }
163
hfs_brec_read(struct hfs_find_data * fd,void * rec,int rec_len)164 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
165 {
166 int res;
167
168 res = hfs_brec_find(fd);
169 if (res)
170 return res;
171 if (fd->entrylength > rec_len)
172 return -EINVAL;
173 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
174 return 0;
175 }
176
hfs_brec_goto(struct hfs_find_data * fd,int cnt)177 int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
178 {
179 struct hfs_btree *tree;
180 struct hfs_bnode *bnode;
181 int idx, res = 0;
182 u16 off, len, keylen;
183
184 bnode = fd->bnode;
185 tree = bnode->tree;
186
187 if (cnt < 0) {
188 cnt = -cnt;
189 while (cnt > fd->record) {
190 cnt -= fd->record + 1;
191 fd->record = bnode->num_recs - 1;
192 idx = bnode->prev;
193 if (!idx) {
194 res = -ENOENT;
195 goto out;
196 }
197 hfs_bnode_put(bnode);
198 bnode = hfs_bnode_find(tree, idx);
199 if (IS_ERR(bnode)) {
200 res = PTR_ERR(bnode);
201 bnode = NULL;
202 goto out;
203 }
204 }
205 fd->record -= cnt;
206 } else {
207 while (cnt >= bnode->num_recs - fd->record) {
208 cnt -= bnode->num_recs - fd->record;
209 fd->record = 0;
210 idx = bnode->next;
211 if (!idx) {
212 res = -ENOENT;
213 goto out;
214 }
215 hfs_bnode_put(bnode);
216 bnode = hfs_bnode_find(tree, idx);
217 if (IS_ERR(bnode)) {
218 res = PTR_ERR(bnode);
219 bnode = NULL;
220 goto out;
221 }
222 }
223 fd->record += cnt;
224 }
225
226 len = hfs_brec_lenoff(bnode, fd->record, &off);
227 keylen = hfs_brec_keylen(bnode, fd->record);
228 if (keylen == 0) {
229 res = -EINVAL;
230 goto out;
231 }
232 fd->keyoffset = off;
233 fd->keylength = keylen;
234 fd->entryoffset = off + keylen;
235 fd->entrylength = len - keylen;
236 hfs_bnode_read(bnode, fd->key, off, keylen);
237 out:
238 fd->bnode = bnode;
239 return res;
240 }
241