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