diff options
Diffstat (limited to 'fs/btrfs/ctree.c')
| -rw-r--r-- | fs/btrfs/ctree.c | 289 |
1 files changed, 289 insertions, 0 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c new file mode 100644 index 0000000000..b13ecb9376 --- /dev/null +++ b/fs/btrfs/ctree.c @@ -0,0 +1,289 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <malloc.h> + +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; + + if (0) { + int i; + printf("\tsearching %llu %i\n", key->objectid, key->type); + for (i = 0; i < max; ++i) { + tmp = (struct btrfs_key *) ((u8 *) addr + i*item_size); + printf("\t\t%llu %i\n", tmp->objectid, tmp->type); + } + printf("\n"); + } + + 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) +{ + struct btrfs_header hdr; + 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(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; + } + + res->header = 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 + 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] >= leaf->header.nritems) + return jump_leaf(p, 1); + + p->slots[0]++; + return 0; +} |