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
15int 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(lock: &tree->tree_lock, subclass: CATALOG_BTREE_MUTEX);
34 break;
35 case HFS_EXT_CNID:
36 mutex_lock_nested(lock: &tree->tree_lock, subclass: EXTENTS_BTREE_MUTEX);
37 break;
38 case HFS_ATTR_CNID:
39 mutex_lock_nested(lock: &tree->tree_lock, subclass: ATTR_BTREE_MUTEX);
40 break;
41 default:
42 return -EINVAL;
43 }
44 return 0;
45}
46
47void hfs_find_exit(struct hfs_find_data *fd)
48{
49 hfs_bnode_put(node: fd->bnode);
50 kfree(objp: fd->search_key);
51 hfs_dbg("cnid %d, caller %ps\n",
52 fd->tree->cnid, __builtin_return_address(0));
53 mutex_unlock(lock: &fd->tree->tree_lock);
54 fd->tree = NULL;
55}
56
57/* Find the record in bnode that best matches key (not greater than...)*/
58int __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(node: bnode, rec, off: &off);
72 keylen = hfs_brec_keylen(node: bnode, rec);
73 if (keylen == 0) {
74 res = -EINVAL;
75 goto fail;
76 }
77 hfs_bnode_read(node: bnode, buf: fd->key, off, len: 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(node: bnode, rec: e, off: &off);
91 keylen = hfs_brec_keylen(node: bnode, rec: e);
92 if (keylen == 0) {
93 res = -EINVAL;
94 goto fail;
95 }
96 hfs_bnode_read(node: bnode, buf: fd->key, off, len: keylen);
97 }
98done:
99 fd->record = e;
100 fd->keyoffset = off;
101 fd->keylength = keylen;
102 fd->entryoffset = off + keylen;
103 fd->entrylength = len - keylen;
104fail:
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 */
110int 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(node: 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, num: nidx);
136 if (IS_ERR(ptr: bnode)) {
137 res = PTR_ERR(ptr: 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(node: bnode, buf: &data, off: fd->entryoffset, len: 4);
155 nidx = be32_to_cpu(data);
156 hfs_bnode_put(node: bnode);
157 }
158 fd->bnode = bnode;
159 return res;
160
161invalid:
162 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
163 height, bnode->height, bnode->type, nidx, parent);
164 res = -EIO;
165release:
166 hfs_bnode_put(node: bnode);
167 return res;
168}
169
170int hfs_brec_read(struct hfs_find_data *fd, void *rec, u32 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(node: fd->bnode, buf: rec, off: fd->entryoffset, len: fd->entrylength);
180 return 0;
181}
182
183int 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(node: bnode);
204 bnode = hfs_bnode_find(tree, num: idx);
205 if (IS_ERR(ptr: bnode)) {
206 res = PTR_ERR(ptr: 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(node: bnode);
222 bnode = hfs_bnode_find(tree, num: idx);
223 if (IS_ERR(ptr: bnode)) {
224 res = PTR_ERR(ptr: bnode);
225 bnode = NULL;
226 goto out;
227 }
228 }
229 fd->record += cnt;
230 }
231
232 len = hfs_brec_lenoff(node: bnode, rec: fd->record, off: &off);
233 keylen = hfs_brec_keylen(node: bnode, rec: 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(node: bnode, buf: fd->key, off, len: keylen);
243out:
244 fd->bnode = bnode;
245 return res;
246}
247

source code of linux/fs/hfs/bfind.c