[linux.git] / fs / hfs / bfind.c

// SPDX-License-Identifier: GPL-2.0
/*
 *  linux/fs/hfs/bfind.c
 *
 * Copyright (C) 2001
 * Brad Boyer ([email protected])
 * (C) 2003 Ardis Technologies <[email protected]>
 *
 * Search routines for btrees
 */

#include <linux/slab.h>
#include "btree.h"

int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
{
	void *ptr;

	fd->tree = tree;
	fd->bnode = NULL;
	ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
	if (!ptr)
		return -ENOMEM;
	fd->search_key = ptr;
	fd->key = ptr + tree->max_key_len + 2;
	hfs_dbg(BNODE_REFS, "find_init: %d (%p)\n",
		tree->cnid, __builtin_return_address(0));
	switch (tree->cnid) {
	case HFS_CAT_CNID:
		mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX);
		break;
	case HFS_EXT_CNID:
		mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX);
		break;
	case HFS_ATTR_CNID:
		mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX);
		break;
	default:
		return -EINVAL;
	}
	return 0;
}

void hfs_find_exit(struct hfs_find_data *fd)
{
	hfs_bnode_put(fd->bnode);
	kfree(fd->search_key);
	hfs_dbg(BNODE_REFS, "find_exit: %d (%p)\n",
		fd->tree->cnid, __builtin_return_address(0));
	mutex_unlock(&fd->tree->tree_lock);
	fd->tree = NULL;
}

/* Find the record in bnode that best matches key (not greater than...)*/
int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd)
{
	int cmpval;
	u16 off, len, keylen;
	int rec;
	int b, e;
	int res;

	b = 0;
	e = bnode->num_recs - 1;
	res = -ENOENT;
	do {
		rec = (e + b) / 2;
		len = hfs_brec_lenoff(bnode, rec, &off);
		keylen = hfs_brec_keylen(bnode, rec);
		if (keylen == 0) {
			res = -EINVAL;
			goto fail;
		}
		hfs_bnode_read(bnode, fd->key, off, keylen);
		cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
		if (!cmpval) {
			e = rec;
			res = 0;
			goto done;
		}
		if (cmpval < 0)
			b = rec + 1;
		else
			e = rec - 1;
	} while (b <= e);
	if (rec != e && e >= 0) {
		len = hfs_brec_lenoff(bnode, e, &off);
		keylen = hfs_brec_keylen(bnode, e);
		if (keylen == 0) {
			res = -EINVAL;
			goto fail;
		}
		hfs_bnode_read(bnode, fd->key, off, keylen);
	}
done:
	fd->record = e;
	fd->keyoffset = off;
	fd->keylength = keylen;
	fd->entryoffset = off + keylen;
	fd->entrylength = len - keylen;
fail:
	return res;
}

/* Traverse a B*Tree from the root to a leaf finding best fit to key */
/* Return allocated copy of node found, set recnum to best record */
int hfs_brec_find(struct hfs_find_data *fd)
{
	struct hfs_btree *tree;
	struct hfs_bnode *bnode;
	u32 nidx, parent;
	__be32 data;
	int height, res;

	tree = fd->tree;
	if (fd->bnode)
		hfs_bnode_put(fd->bnode);
	fd->bnode = NULL;
	nidx = tree->root;
	if (!nidx)
		return -ENOENT;
	height = tree->depth;
	res = 0;
	parent = 0;
	for (;;) {
		bnode = hfs_bnode_find(tree, nidx);
		if (IS_ERR(bnode)) {
			res = PTR_ERR(bnode);
			bnode = NULL;
			break;
		}
		if (bnode->height != height)
			goto invalid;
		if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
			goto invalid;
		bnode->parent = parent;

		res = __hfs_brec_find(bnode, fd);
		if (!height)
			break;
		if (fd->record < 0)
			goto release;

		parent = nidx;
		hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
		nidx = be32_to_cpu(data);
		hfs_bnode_put(bnode);
	}
	fd->bnode = bnode;
	return res;

invalid:
	pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
	       height, bnode->height, bnode->type, nidx, parent);
	res = -EIO;
release:
	hfs_bnode_put(bnode);
	return res;
}

int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
{
	int res;

	res = hfs_brec_find(fd);
	if (res)
		return res;
	if (fd->entrylength > rec_len)
		return -EINVAL;
	hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
	return 0;
}

int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
{
	struct hfs_btree *tree;
	struct hfs_bnode *bnode;
	int idx, res = 0;
	u16 off, len, keylen;

	bnode = fd->bnode;
	tree = bnode->tree;

	if (cnt < 0) {
		cnt = -cnt;
		while (cnt > fd->record) {
			cnt -= fd->record + 1;
			fd->record = bnode->num_recs - 1;
			idx = bnode->prev;
			if (!idx) {
				res = -ENOENT;
				goto out;
			}
			hfs_bnode_put(bnode);
			bnode = hfs_bnode_find(tree, idx);
			if (IS_ERR(bnode)) {
				res = PTR_ERR(bnode);
				bnode = NULL;
				goto out;
			}
		}
		fd->record -= cnt;
	} else {
		while (cnt >= bnode->num_recs - fd->record) {
			cnt -= bnode->num_recs - fd->record;
			fd->record = 0;
			idx = bnode->next;
			if (!idx) {
				res = -ENOENT;
				goto out;
			}
			hfs_bnode_put(bnode);
			bnode = hfs_bnode_find(tree, idx);
			if (IS_ERR(bnode)) {
				res = PTR_ERR(bnode);
				bnode = NULL;
				goto out;
			}
		}
		fd->record += cnt;
	}

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