2 * BTRFS filesystem implementation for U-Boot
4 * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
6 * SPDX-License-Identifier: GPL-2.0+
12 int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b)
14 if (a->objectid > b->objectid)
16 if (a->objectid < b->objectid)
18 if (a->type > b->type)
20 if (a->type < b->type)
22 if (a->offset > b->offset)
24 if (a->offset < b->offset)
29 int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
31 if (a->objectid > b->objectid)
33 if (a->objectid < b->objectid)
35 if (a->type > b->type)
37 if (a->type < b->type)
42 static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
45 int low = 0, high = max, mid, ret;
46 struct btrfs_key *tmp;
50 printf("\tsearching %llu %i\n", key->objectid, key->type);
51 for (i = 0; i < max; ++i) {
52 tmp = (struct btrfs_key *) ((u8 *) addr + i*item_size);
53 printf("\t\t%llu %i\n", tmp->objectid, tmp->type);
59 mid = (low + high) / 2;
61 tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
62 ret = btrfs_comp_keys(tmp, key);
78 int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
84 if (p->header.level) {
86 size = sizeof(struct btrfs_key_ptr);
89 size = sizeof(struct btrfs_item);
92 return generic_bin_search(addr, size, key, p->header.nritems, slot);
95 static void clear_path(struct btrfs_path *p)
99 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
105 void btrfs_free_path(struct btrfs_path *p)
109 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
117 static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
119 struct btrfs_header hdr;
120 unsigned long size, offset = sizeof(hdr);
121 union btrfs_tree_node *res;
124 if (!btrfs_devread(physical, sizeof(hdr), &hdr))
127 btrfs_header_to_cpu(&hdr);
130 size = sizeof(struct btrfs_node)
131 + hdr.nritems * sizeof(struct btrfs_key_ptr);
133 size = btrfs_info.sb.nodesize;
137 debug("%s: malloc failed\n", __func__);
141 if (!btrfs_devread(physical + offset, size - offset,
142 ((u8 *) res) + offset)) {
149 for (i = 0; i < hdr.nritems; ++i)
150 btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
152 for (i = 0; i < hdr.nritems; ++i)
153 btrfs_item_to_cpu(&res->leaf.items[i]);
160 int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
161 struct btrfs_path *p)
165 u64 logical, physical;
166 union btrfs_tree_node *buf;
170 logical = root->bytenr;
172 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
173 physical = btrfs_map_logical_to_physical(logical);
174 if (physical == -1ULL)
177 if (read_tree_node(physical, &buf))
180 lvl = buf->header.level;
181 if (i && prev_lvl != lvl + 1) {
182 printf("%s: invalid level in header at %llu\n",
188 ret = btrfs_bin_search(buf, key, &slot);
191 if (ret && slot > 0 && lvl)
194 p->slots[lvl] = slot;
198 logical = buf->node.ptrs[slot].blockptr;
209 static int jump_leaf(struct btrfs_path *path, int dir)
213 int level = 1, from_level, i;
215 dir = dir >= 0 ? 1 : -1;
219 while (level < BTRFS_MAX_LEVEL) {
223 slot = p.slots[level];
224 if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
225 || (dir < 0 && !slot))
231 if (level == BTRFS_MAX_LEVEL)
234 p.slots[level] = slot + dir;
239 u64 logical, physical;
241 slot = p.slots[level + 1];
242 logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
243 physical = btrfs_map_logical_to_physical(logical);
244 if (physical == -1ULL)
247 if (read_tree_node(physical, &p.nodes[level]))
253 p.slots[level] = p.nodes[level]->header.nritems - 1;
257 /* Free rewritten nodes in path */
258 for (i = 0; i <= from_level; ++i)
259 free(path->nodes[i]);
265 /* Free rewritten nodes in p */
266 for (i = level + 1; i <= from_level; ++i)
271 int btrfs_prev_slot(struct btrfs_path *p)
274 return jump_leaf(p, -1);
280 int btrfs_next_slot(struct btrfs_path *p)
282 struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
284 if (p->slots[0] >= leaf->header.nritems)
285 return jump_leaf(p, 1);