183d290c5STom Rini // SPDX-License-Identifier: GPL-2.0+
221a14facSMarek Behún /*
321a14facSMarek Behún * BTRFS filesystem implementation for U-Boot
421a14facSMarek Behún *
521a14facSMarek Behún * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
621a14facSMarek Behún */
721a14facSMarek Behún
821a14facSMarek Behún #include "btrfs.h"
921a14facSMarek Behún #include <malloc.h>
10c9795396SMarek Vasut #include <memalign.h>
1121a14facSMarek Behún
btrfs_comp_keys(struct btrfs_key * a,struct btrfs_key * b)1221a14facSMarek Behún int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b)
1321a14facSMarek Behún {
1421a14facSMarek Behún if (a->objectid > b->objectid)
1521a14facSMarek Behún return 1;
1621a14facSMarek Behún if (a->objectid < b->objectid)
1721a14facSMarek Behún return -1;
1821a14facSMarek Behún if (a->type > b->type)
1921a14facSMarek Behún return 1;
2021a14facSMarek Behún if (a->type < b->type)
2121a14facSMarek Behún return -1;
2221a14facSMarek Behún if (a->offset > b->offset)
2321a14facSMarek Behún return 1;
2421a14facSMarek Behún if (a->offset < b->offset)
2521a14facSMarek Behún return -1;
2621a14facSMarek Behún return 0;
2721a14facSMarek Behún }
2821a14facSMarek Behún
btrfs_comp_keys_type(struct btrfs_key * a,struct btrfs_key * b)2921a14facSMarek Behún int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
3021a14facSMarek Behún {
3121a14facSMarek Behún if (a->objectid > b->objectid)
3221a14facSMarek Behún return 1;
3321a14facSMarek Behún if (a->objectid < b->objectid)
3421a14facSMarek Behún return -1;
3521a14facSMarek Behún if (a->type > b->type)
3621a14facSMarek Behún return 1;
3721a14facSMarek Behún if (a->type < b->type)
3821a14facSMarek Behún return -1;
3921a14facSMarek Behún return 0;
4021a14facSMarek Behún }
4121a14facSMarek Behún
generic_bin_search(void * addr,int item_size,struct btrfs_key * key,int max,int * slot)4221a14facSMarek Behún static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
4321a14facSMarek Behún int max, int *slot)
4421a14facSMarek Behún {
4521a14facSMarek Behún int low = 0, high = max, mid, ret;
4621a14facSMarek Behún struct btrfs_key *tmp;
4721a14facSMarek Behún
4821a14facSMarek Behún while (low < high) {
4921a14facSMarek Behún mid = (low + high) / 2;
5021a14facSMarek Behún
5121a14facSMarek Behún tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
5221a14facSMarek Behún ret = btrfs_comp_keys(tmp, key);
5321a14facSMarek Behún
5421a14facSMarek Behún if (ret < 0) {
5521a14facSMarek Behún low = mid + 1;
5621a14facSMarek Behún } else if (ret > 0) {
5721a14facSMarek Behún high = mid;
5821a14facSMarek Behún } else {
5921a14facSMarek Behún *slot = mid;
6021a14facSMarek Behún return 0;
6121a14facSMarek Behún }
6221a14facSMarek Behún }
6321a14facSMarek Behún
6421a14facSMarek Behún *slot = low;
6521a14facSMarek Behún return 1;
6621a14facSMarek Behún }
6721a14facSMarek Behún
btrfs_bin_search(union btrfs_tree_node * p,struct btrfs_key * key,int * slot)6821a14facSMarek Behún int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
6921a14facSMarek Behún int *slot)
7021a14facSMarek Behún {
7121a14facSMarek Behún void *addr;
7221a14facSMarek Behún unsigned long size;
7321a14facSMarek Behún
7421a14facSMarek Behún if (p->header.level) {
7521a14facSMarek Behún addr = p->node.ptrs;
7621a14facSMarek Behún size = sizeof(struct btrfs_key_ptr);
7721a14facSMarek Behún } else {
7821a14facSMarek Behún addr = p->leaf.items;
7921a14facSMarek Behún size = sizeof(struct btrfs_item);
8021a14facSMarek Behún }
8121a14facSMarek Behún
8221a14facSMarek Behún return generic_bin_search(addr, size, key, p->header.nritems, slot);
8321a14facSMarek Behún }
8421a14facSMarek Behún
clear_path(struct btrfs_path * p)8521a14facSMarek Behún static void clear_path(struct btrfs_path *p)
8621a14facSMarek Behún {
8721a14facSMarek Behún int i;
8821a14facSMarek Behún
8921a14facSMarek Behún for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
9021a14facSMarek Behún p->nodes[i] = NULL;
9121a14facSMarek Behún p->slots[i] = 0;
9221a14facSMarek Behún }
9321a14facSMarek Behún }
9421a14facSMarek Behún
btrfs_free_path(struct btrfs_path * p)9521a14facSMarek Behún void btrfs_free_path(struct btrfs_path *p)
9621a14facSMarek Behún {
9721a14facSMarek Behún int i;
9821a14facSMarek Behún
9921a14facSMarek Behún for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
10021a14facSMarek Behún if (p->nodes[i])
10121a14facSMarek Behún free(p->nodes[i]);
10221a14facSMarek Behún }
10321a14facSMarek Behún
10421a14facSMarek Behún clear_path(p);
10521a14facSMarek Behún }
10621a14facSMarek Behún
read_tree_node(u64 physical,union btrfs_tree_node ** buf)10721a14facSMarek Behún static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
10821a14facSMarek Behún {
109c9795396SMarek Vasut ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr,
110c9795396SMarek Vasut sizeof(struct btrfs_header));
111c9795396SMarek Vasut unsigned long size, offset = sizeof(*hdr);
11221a14facSMarek Behún union btrfs_tree_node *res;
11321a14facSMarek Behún u32 i;
11421a14facSMarek Behún
115c9795396SMarek Vasut if (!btrfs_devread(physical, sizeof(*hdr), hdr))
11621a14facSMarek Behún return -1;
11721a14facSMarek Behún
118c9795396SMarek Vasut btrfs_header_to_cpu(hdr);
11921a14facSMarek Behún
120c9795396SMarek Vasut if (hdr->level)
12121a14facSMarek Behún size = sizeof(struct btrfs_node)
122c9795396SMarek Vasut + hdr->nritems * sizeof(struct btrfs_key_ptr);
12321a14facSMarek Behún else
12421a14facSMarek Behún size = btrfs_info.sb.nodesize;
12521a14facSMarek Behún
126c9795396SMarek Vasut res = malloc_cache_aligned(size);
12721a14facSMarek Behún if (!res) {
12821a14facSMarek Behún debug("%s: malloc failed\n", __func__);
12921a14facSMarek Behún return -1;
13021a14facSMarek Behún }
13121a14facSMarek Behún
13221a14facSMarek Behún if (!btrfs_devread(physical + offset, size - offset,
13321a14facSMarek Behún ((u8 *) res) + offset)) {
13421a14facSMarek Behún free(res);
13521a14facSMarek Behún return -1;
13621a14facSMarek Behún }
13721a14facSMarek Behún
138c9795396SMarek Vasut memcpy(&res->header, hdr, sizeof(*hdr));
139c9795396SMarek Vasut if (hdr->level)
140c9795396SMarek Vasut for (i = 0; i < hdr->nritems; ++i)
14121a14facSMarek Behún btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
14221a14facSMarek Behún else
143c9795396SMarek Vasut for (i = 0; i < hdr->nritems; ++i)
14421a14facSMarek Behún btrfs_item_to_cpu(&res->leaf.items[i]);
14521a14facSMarek Behún
14621a14facSMarek Behún *buf = res;
14721a14facSMarek Behún
14821a14facSMarek Behún return 0;
14921a14facSMarek Behún }
15021a14facSMarek Behún
btrfs_search_tree(const struct btrfs_root * root,struct btrfs_key * key,struct btrfs_path * p)15121a14facSMarek Behún int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
15221a14facSMarek Behún struct btrfs_path *p)
15321a14facSMarek Behún {
15421a14facSMarek Behún u8 lvl, prev_lvl;
15521a14facSMarek Behún int i, slot, ret;
15621a14facSMarek Behún u64 logical, physical;
15721a14facSMarek Behún union btrfs_tree_node *buf;
15821a14facSMarek Behún
15921a14facSMarek Behún clear_path(p);
16021a14facSMarek Behún
16121a14facSMarek Behún logical = root->bytenr;
16221a14facSMarek Behún
16321a14facSMarek Behún for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
16421a14facSMarek Behún physical = btrfs_map_logical_to_physical(logical);
16521a14facSMarek Behún if (physical == -1ULL)
16621a14facSMarek Behún goto err;
16721a14facSMarek Behún
16821a14facSMarek Behún if (read_tree_node(physical, &buf))
16921a14facSMarek Behún goto err;
17021a14facSMarek Behún
17121a14facSMarek Behún lvl = buf->header.level;
17221a14facSMarek Behún if (i && prev_lvl != lvl + 1) {
17321a14facSMarek Behún printf("%s: invalid level in header at %llu\n",
17421a14facSMarek Behún __func__, logical);
17521a14facSMarek Behún goto err;
17621a14facSMarek Behún }
17721a14facSMarek Behún prev_lvl = lvl;
17821a14facSMarek Behún
17921a14facSMarek Behún ret = btrfs_bin_search(buf, key, &slot);
18021a14facSMarek Behún if (ret < 0)
18121a14facSMarek Behún goto err;
18221a14facSMarek Behún if (ret && slot > 0 && lvl)
18321a14facSMarek Behún slot -= 1;
18421a14facSMarek Behún
18521a14facSMarek Behún p->slots[lvl] = slot;
18621a14facSMarek Behún p->nodes[lvl] = buf;
18721a14facSMarek Behún
18821a14facSMarek Behún if (lvl)
18921a14facSMarek Behún logical = buf->node.ptrs[slot].blockptr;
19021a14facSMarek Behún else
19121a14facSMarek Behún break;
19221a14facSMarek Behún }
19321a14facSMarek Behún
19421a14facSMarek Behún return 0;
19521a14facSMarek Behún err:
19621a14facSMarek Behún btrfs_free_path(p);
19721a14facSMarek Behún return -1;
19821a14facSMarek Behún }
19921a14facSMarek Behún
jump_leaf(struct btrfs_path * path,int dir)20021a14facSMarek Behún static int jump_leaf(struct btrfs_path *path, int dir)
20121a14facSMarek Behún {
20221a14facSMarek Behún struct btrfs_path p;
20321a14facSMarek Behún u32 slot;
20421a14facSMarek Behún int level = 1, from_level, i;
20521a14facSMarek Behún
20621a14facSMarek Behún dir = dir >= 0 ? 1 : -1;
20721a14facSMarek Behún
20821a14facSMarek Behún p = *path;
20921a14facSMarek Behún
21021a14facSMarek Behún while (level < BTRFS_MAX_LEVEL) {
21121a14facSMarek Behún if (!p.nodes[level])
21221a14facSMarek Behún return 1;
21321a14facSMarek Behún
21421a14facSMarek Behún slot = p.slots[level];
21521a14facSMarek Behún if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
21621a14facSMarek Behún || (dir < 0 && !slot))
21721a14facSMarek Behún level++;
21821a14facSMarek Behún else
21921a14facSMarek Behún break;
22021a14facSMarek Behún }
22121a14facSMarek Behún
22221a14facSMarek Behún if (level == BTRFS_MAX_LEVEL)
22321a14facSMarek Behún return 1;
22421a14facSMarek Behún
22521a14facSMarek Behún p.slots[level] = slot + dir;
22621a14facSMarek Behún level--;
22721a14facSMarek Behún from_level = level;
22821a14facSMarek Behún
22921a14facSMarek Behún while (level >= 0) {
23021a14facSMarek Behún u64 logical, physical;
23121a14facSMarek Behún
23221a14facSMarek Behún slot = p.slots[level + 1];
23321a14facSMarek Behún logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
23421a14facSMarek Behún physical = btrfs_map_logical_to_physical(logical);
23521a14facSMarek Behún if (physical == -1ULL)
23621a14facSMarek Behún goto err;
23721a14facSMarek Behún
23821a14facSMarek Behún if (read_tree_node(physical, &p.nodes[level]))
23921a14facSMarek Behún goto err;
24021a14facSMarek Behún
24121a14facSMarek Behún if (dir > 0)
24221a14facSMarek Behún p.slots[level] = 0;
24321a14facSMarek Behún else
24421a14facSMarek Behún p.slots[level] = p.nodes[level]->header.nritems - 1;
24521a14facSMarek Behún level--;
24621a14facSMarek Behún }
24721a14facSMarek Behún
24821a14facSMarek Behún /* Free rewritten nodes in path */
24921a14facSMarek Behún for (i = 0; i <= from_level; ++i)
25021a14facSMarek Behún free(path->nodes[i]);
25121a14facSMarek Behún
25221a14facSMarek Behún *path = p;
25321a14facSMarek Behún return 0;
25421a14facSMarek Behún
25521a14facSMarek Behún err:
25621a14facSMarek Behún /* Free rewritten nodes in p */
25721a14facSMarek Behún for (i = level + 1; i <= from_level; ++i)
25821a14facSMarek Behún free(p.nodes[i]);
25921a14facSMarek Behún return -1;
26021a14facSMarek Behún }
26121a14facSMarek Behún
btrfs_prev_slot(struct btrfs_path * p)26221a14facSMarek Behún int btrfs_prev_slot(struct btrfs_path *p)
26321a14facSMarek Behún {
26421a14facSMarek Behún if (!p->slots[0])
26521a14facSMarek Behún return jump_leaf(p, -1);
26621a14facSMarek Behún
26721a14facSMarek Behún p->slots[0]--;
26821a14facSMarek Behún return 0;
26921a14facSMarek Behún }
27021a14facSMarek Behún
btrfs_next_slot(struct btrfs_path * p)27121a14facSMarek Behún int btrfs_next_slot(struct btrfs_path *p)
27221a14facSMarek Behún {
27321a14facSMarek Behún struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
27421a14facSMarek Behún
275*5b781cf0SYevgeny Popovych if (p->slots[0] + 1 >= leaf->header.nritems)
27621a14facSMarek Behún return jump_leaf(p, 1);
27721a14facSMarek Behún
27821a14facSMarek Behún p->slots[0]++;
27921a14facSMarek Behún return 0;
28021a14facSMarek Behún }
281