[thirdparty/u-boot.git] / fs / btrfs / ctree.c

// SPDX-License-Identifier: GPL-2.0+
/*
 * BTRFS filesystem implementation for U-Boot
 *
 * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
 */

#include "btrfs.h"
#include <log.h>
#include <malloc.h>
#include <memalign.h>

static const struct btrfs_csum {
	u16 size;
	const char name[14];
} btrfs_csums[] = {
	[BTRFS_CSUM_TYPE_CRC32]		= {  4, "crc32c" },
	[BTRFS_CSUM_TYPE_XXHASH]	= {  8, "xxhash64" },
	[BTRFS_CSUM_TYPE_SHA256]	= { 32, "sha256" },
	[BTRFS_CSUM_TYPE_BLAKE2]	= { 32, "blake2" },
};

u16 btrfs_super_csum_size(const struct btrfs_super_block *sb)
{
	const u16 csum_type = btrfs_super_csum_type(sb);

	return btrfs_csums[csum_type].size;
}

const char *btrfs_super_csum_name(u16 csum_type)
{
	return btrfs_csums[csum_type].name;
}

size_t btrfs_super_num_csums(void)
{
	return ARRAY_SIZE(btrfs_csums);
}

u16 btrfs_csum_type_size(u16 csum_type)
{
	return btrfs_csums[csum_type].size;
}

int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b)
{
	if (a->objectid > b->objectid)
		return 1;
	if (a->objectid < b->objectid)
		return -1;
	if (a->type > b->type)
		return 1;
	if (a->type < b->type)
		return -1;
	if (a->offset > b->offset)
		return 1;
	if (a->offset < b->offset)
		return -1;
	return 0;
}

int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
{
	if (a->objectid > b->objectid)
		return 1;
	if (a->objectid < b->objectid)
		return -1;
	if (a->type > b->type)
		return 1;
	if (a->type < b->type)
		return -1;
	return 0;
}

static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
			      int max, int *slot)
{
	int low = 0, high = max, mid, ret;
	struct btrfs_key *tmp;

	while (low < high) {
		mid = (low + high) / 2;

		tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
		ret = btrfs_comp_keys(tmp, key);

		if (ret < 0) {
			low = mid + 1;
		} else if (ret > 0) {
			high = mid;
		} else {
			*slot = mid;
			return 0;
		}
	}

	*slot = low;
	return 1;
}

int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
		     int *slot)
{
	void *addr;
	unsigned long size;

	if (p->header.level) {
		addr = p->node.ptrs;
		size = sizeof(struct btrfs_key_ptr);
	} else {
		addr = p->leaf.items;
		size = sizeof(struct btrfs_item);
	}

	return generic_bin_search(addr, size, key, p->header.nritems, slot);
}

static void clear_path(struct btrfs_path *p)
{
	int i;

	for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
		p->nodes[i] = NULL;
		p->slots[i] = 0;
	}
}

void btrfs_free_path(struct btrfs_path *p)
{
	int i;

	for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
		if (p->nodes[i])
			free(p->nodes[i]);
	}

	clear_path(p);
}

static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
{
	ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr,
				 sizeof(struct btrfs_header));
	unsigned long size, offset = sizeof(*hdr);
	union btrfs_tree_node *res;
	u32 i;

	if (!btrfs_devread(physical, sizeof(*hdr), hdr))
		return -1;

	btrfs_header_to_cpu(hdr);

	if (hdr->level)
		size = sizeof(struct btrfs_node)
		       + hdr->nritems * sizeof(struct btrfs_key_ptr);
	else
		size = btrfs_info.sb.nodesize;

	res = malloc_cache_aligned(size);
	if (!res) {
		debug("%s: malloc failed\n", __func__);
		return -1;
	}

	if (!btrfs_devread(physical + offset, size - offset,
			   ((u8 *) res) + offset)) {
		free(res);
		return -1;
	}

	memcpy(&res->header, hdr, sizeof(*hdr));
	if (hdr->level)
		for (i = 0; i < hdr->nritems; ++i)
			btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
	else
		for (i = 0; i < hdr->nritems; ++i)
			btrfs_item_to_cpu(&res->leaf.items[i]);

	*buf = res;

	return 0;
}

int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
		      struct btrfs_path *p)
{
	u8 lvl, prev_lvl;
	int i, slot, ret;
	u64 logical, physical;
	union btrfs_tree_node *buf;

	clear_path(p);

	logical = root->bytenr;

	for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
		physical = btrfs_map_logical_to_physical(logical);
		if (physical == -1ULL)
			goto err;

		if (read_tree_node(physical, &buf))
			goto err;

		lvl = buf->header.level;
		if (i && prev_lvl != lvl + 1) {
			printf("%s: invalid level in header at %llu\n",
			       __func__, logical);
			goto err;
		}
		prev_lvl = lvl;

		ret = btrfs_bin_search(buf, key, &slot);
		if (ret < 0)
			goto err;
		if (ret && slot > 0 && lvl)
			slot -= 1;

		p->slots[lvl] = slot;
		p->nodes[lvl] = buf;

		if (lvl) {
			logical = buf->node.ptrs[slot].blockptr;
		} else {
			/*
			 * The path might be invalid if:
			 *   cur leaf max < searched value < next leaf min
			 *
			 * Jump to the next valid element if it exists.
			 */
			if (slot >= buf->header.nritems)
				if (btrfs_next_slot(p) < 0)
					goto err;
			break;
		}
	}

	return 0;
err:
	btrfs_free_path(p);
	return -1;
}

static int jump_leaf(struct btrfs_path *path, int dir)
{
	struct btrfs_path p;
	u32 slot;
	int level = 1, from_level, i;

	dir = dir >= 0 ? 1 : -1;

	p = *path;

	while (level < BTRFS_MAX_LEVEL) {
		if (!p.nodes[level])
			return 1;

		slot = p.slots[level];
		if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
		    || (dir < 0 && !slot))
			level++;
		else
			break;
	}

	if (level == BTRFS_MAX_LEVEL)
		return 1;

	p.slots[level] = slot + dir;
	level--;
	from_level = level;

	while (level >= 0) {
		u64 logical, physical;

		slot = p.slots[level + 1];
		logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
		physical = btrfs_map_logical_to_physical(logical);
		if (physical == -1ULL)
			goto err;

		if (read_tree_node(physical, &p.nodes[level]))
			goto err;

		if (dir > 0)
			p.slots[level] = 0;
		else
			p.slots[level] = p.nodes[level]->header.nritems - 1;
		level--;
	}

	/* Free rewritten nodes in path */
	for (i = 0; i <= from_level; ++i)
		free(path->nodes[i]);

	*path = p;
	return 0;

err:
	/* Free rewritten nodes in p */
	for (i = level + 1; i <= from_level; ++i)
		free(p.nodes[i]);
	return -1;
}

int btrfs_prev_slot(struct btrfs_path *p)
{
	if (!p->slots[0])
		return jump_leaf(p, -1);

	p->slots[0]--;
	return 0;
}

int btrfs_next_slot(struct btrfs_path *p)
{
	struct btrfs_leaf *leaf = &p->nodes[0]->leaf;

	if (p->slots[0] + 1 >= leaf->header.nritems)
		return jump_leaf(p, 1);

	p->slots[0]++;
	return 0;
}
Commit	Line	Data
83d290c5	1	// SPDX-License-Identifier: GPL-2.0+
21a14fac MB	2	/*
	3	* BTRFS filesystem implementation for U-Boot
	4	*
	5	* 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
21a14fac MB	6	*/
	7
	8	#include "btrfs.h"
f7ae49fc	9	#include <log.h>
21a14fac	10	#include <malloc.h>
c9795396	11	#include <memalign.h>
21a14fac	12
4aebb994 QW	13	static const struct btrfs_csum {
	14	u16 size;
	15	const char name[14];
	16	} btrfs_csums[] = {
	17	[BTRFS_CSUM_TYPE_CRC32] = { 4, "crc32c" },
	18	[BTRFS_CSUM_TYPE_XXHASH] = { 8, "xxhash64" },
	19	[BTRFS_CSUM_TYPE_SHA256] = { 32, "sha256" },
	20	[BTRFS_CSUM_TYPE_BLAKE2] = { 32, "blake2" },
	21	};
	22
	23	u16 btrfs_super_csum_size(const struct btrfs_super_block *sb)
	24	{
	25	const u16 csum_type = btrfs_super_csum_type(sb);
	26
	27	return btrfs_csums[csum_type].size;
	28	}
	29
	30	const char *btrfs_super_csum_name(u16 csum_type)
	31	{
	32	return btrfs_csums[csum_type].name;
	33	}
	34
	35	size_t btrfs_super_num_csums(void)
	36	{
	37	return ARRAY_SIZE(btrfs_csums);
	38	}
	39
	40	u16 btrfs_csum_type_size(u16 csum_type)
	41	{
	42	return btrfs_csums[csum_type].size;
	43	}
	44
21a14fac MB	45	int btrfs_comp_keys(struct btrfs_key a, struct btrfs_key b)
	46	{
	47	if (a->objectid > b->objectid)
	48	return 1;
	49	if (a->objectid < b->objectid)
	50	return -1;
	51	if (a->type > b->type)
	52	return 1;
	53	if (a->type < b->type)
	54	return -1;
	55	if (a->offset > b->offset)
	56	return 1;
	57	if (a->offset < b->offset)
	58	return -1;
	59	return 0;
	60	}
	61
	62	int btrfs_comp_keys_type(struct btrfs_key a, struct btrfs_key b)
	63	{
	64	if (a->objectid > b->objectid)
	65	return 1;
	66	if (a->objectid < b->objectid)
	67	return -1;
	68	if (a->type > b->type)
	69	return 1;
	70	if (a->type < b->type)
	71	return -1;
	72	return 0;
	73	}
	74
	75	static int generic_bin_search(void addr, int item_size, struct btrfs_key key,
	76	int max, int *slot)
	77	{
	78	int low = 0, high = max, mid, ret;
	79	struct btrfs_key *tmp;
	80
21a14fac MB	81	while (low < high) {
	82	mid = (low + high) / 2;
	83
	84	tmp = (struct btrfs_key ) ((u8 ) addr + mid*item_size);
	85	ret = btrfs_comp_keys(tmp, key);
	86
	87	if (ret < 0) {
	88	low = mid + 1;
	89	} else if (ret > 0) {
	90	high = mid;
	91	} else {
	92	*slot = mid;
	93	return 0;
	94	}
	95	}
	96
	97	*slot = low;
	98	return 1;
	99	}
	100
	101	int btrfs_bin_search(union btrfs_tree_node p, struct btrfs_key key,
	102	int *slot)
	103	{
	104	void *addr;
	105	unsigned long size;
	106
	107	if (p->header.level) {
	108	addr = p->node.ptrs;
	109	size = sizeof(struct btrfs_key_ptr);
	110	} else {
	111	addr = p->leaf.items;
	112	size = sizeof(struct btrfs_item);
	113	}
	114
	115	return generic_bin_search(addr, size, key, p->header.nritems, slot);
	116	}
	117
	118	static void clear_path(struct btrfs_path *p)
	119	{
	120	int i;
	121
	122	for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
	123	p->nodes[i] = NULL;
	124	p->slots[i] = 0;
	125	}
	126	}
	127
	128	void btrfs_free_path(struct btrfs_path *p)
	129	{
	130	int i;
	131
	132	for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
	133	if (p->nodes[i])
	134	free(p->nodes[i]);
	135	}
	136
	137	clear_path(p);
	138	}
	139
	140	static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
	141	{
c9795396 MV	142	ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr,
	143	sizeof(struct btrfs_header));
	144	unsigned long size, offset = sizeof(*hdr);
21a14fac MB	145	union btrfs_tree_node *res;
	146	u32 i;
	147
c9795396	148	if (!btrfs_devread(physical, sizeof(*hdr), hdr))
21a14fac MB	149	return -1;
21a14fac MB	150
c9795396	151	btrfs_header_to_cpu(hdr);
21a14fac	152
c9795396	153	if (hdr->level)
21a14fac	154	size = sizeof(struct btrfs_node)
c9795396	155	+ hdr->nritems * sizeof(struct btrfs_key_ptr);
21a14fac MB	156	else
	157	size = btrfs_info.sb.nodesize;
	158
c9795396	159	res = malloc_cache_aligned(size);
21a14fac MB	160	if (!res) {
	161	debug("%s: malloc failed\n", __func__);
	162	return -1;
	163	}
	164
	165	if (!btrfs_devread(physical + offset, size - offset,
	166	((u8 *) res) + offset)) {
	167	free(res);
	168	return -1;
	169	}
	170
c9795396 MV	171	memcpy(&res->header, hdr, sizeof(*hdr));
	172	if (hdr->level)
	173	for (i = 0; i < hdr->nritems; ++i)
21a14fac MB	174	btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
21a14fac MB	175	else
c9795396	176	for (i = 0; i < hdr->nritems; ++i)
21a14fac MB	177	btrfs_item_to_cpu(&res->leaf.items[i]);
	178
	179	*buf = res;
	180
	181	return 0;
	182	}
	183
	184	int btrfs_search_tree(const struct btrfs_root root, struct btrfs_key key,
	185	struct btrfs_path *p)
	186	{
	187	u8 lvl, prev_lvl;
	188	int i, slot, ret;
	189	u64 logical, physical;
	190	union btrfs_tree_node *buf;
	191
	192	clear_path(p);
	193
	194	logical = root->bytenr;
	195
	196	for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
	197	physical = btrfs_map_logical_to_physical(logical);
	198	if (physical == -1ULL)
	199	goto err;
	200
	201	if (read_tree_node(physical, &buf))
	202	goto err;
	203
	204	lvl = buf->header.level;
	205	if (i && prev_lvl != lvl + 1) {
	206	printf("%s: invalid level in header at %llu\n",
	207	__func__, logical);
	208	goto err;
	209	}
	210	prev_lvl = lvl;
	211
	212	ret = btrfs_bin_search(buf, key, &slot);
	213	if (ret < 0)
	214	goto err;
	215	if (ret && slot > 0 && lvl)
	216	slot -= 1;
	217
	218	p->slots[lvl] = slot;
	219	p->nodes[lvl] = buf;
	220
1627e5e5	221	if (lvl) {
21a14fac	222	logical = buf->node.ptrs[slot].blockptr;
1627e5e5 PB	223	} else {
	224	/*
	225	* The path might be invalid if:
	226	* cur leaf max < searched value < next leaf min
	227	*
	228	* Jump to the next valid element if it exists.
	229	*/
	230	if (slot >= buf->header.nritems)
	231	if (btrfs_next_slot(p) < 0)
	232	goto err;
21a14fac	233	break;
1627e5e5	234	}
21a14fac MB	235	}
	236
	237	return 0;
	238	err:
	239	btrfs_free_path(p);
	240	return -1;
	241	}
	242
	243	static int jump_leaf(struct btrfs_path *path, int dir)
	244	{
	245	struct btrfs_path p;
	246	u32 slot;
	247	int level = 1, from_level, i;
	248
	249	dir = dir >= 0 ? 1 : -1;
	250
	251	p = *path;
	252
	253	while (level < BTRFS_MAX_LEVEL) {
	254	if (!p.nodes[level])
	255	return 1;
	256
	257	slot = p.slots[level];
	258	if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
	259	\|\| (dir < 0 && !slot))
	260	level++;
	261	else
	262	break;
	263	}
	264
	265	if (level == BTRFS_MAX_LEVEL)
	266	return 1;
	267
	268	p.slots[level] = slot + dir;
	269	level--;
	270	from_level = level;
	271
	272	while (level >= 0) {
	273	u64 logical, physical;
	274
	275	slot = p.slots[level + 1];
	276	logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
	277	physical = btrfs_map_logical_to_physical(logical);
	278	if (physical == -1ULL)
	279	goto err;
	280
	281	if (read_tree_node(physical, &p.nodes[level]))
	282	goto err;
	283
	284	if (dir > 0)
	285	p.slots[level] = 0;
	286	else
	287	p.slots[level] = p.nodes[level]->header.nritems - 1;
	288	level--;
	289	}
	290
	291	/* Free rewritten nodes in path */
	292	for (i = 0; i <= from_level; ++i)
	293	free(path->nodes[i]);
	294
	295	*path = p;
	296	return 0;
	297
	298	err:
299	/* Free rewritten nodes in p */
300	for (i = level + 1; i <= from_level; ++i)
301	free(p.nodes[i]);
302	return -1;
303	}
304
305	int btrfs_prev_slot(struct btrfs_path *p)
306	{
307	if (!p->slots[0])
308	return jump_leaf(p, -1);
309
310	p->slots[0]--;
311	return 0;
312	}
313
314	int btrfs_next_slot(struct btrfs_path *p)
315	{
316	struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
317
5b781cf0	318	if (p->slots[0] + 1 >= leaf->header.nritems)
21a14fac MB	319	return jump_leaf(p, 1);
	320
	321	p->slots[0]++;
	322	return 0;
	323	}