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