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;
49 mid = (low + high) / 2;
51 tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
52 ret = btrfs_comp_keys(tmp, key);
68 int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
74 if (p->header.level) {
76 size = sizeof(struct btrfs_key_ptr);
79 size = sizeof(struct btrfs_item);
82 return generic_bin_search(addr, size, key, p->header.nritems, slot);
85 static void clear_path(struct btrfs_path *p)
89 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
95 void btrfs_free_path(struct btrfs_path *p)
99 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
107 static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
109 struct btrfs_header hdr;
110 unsigned long size, offset = sizeof(hdr);
111 union btrfs_tree_node *res;
114 if (!btrfs_devread(physical, sizeof(hdr), &hdr))
117 btrfs_header_to_cpu(&hdr);
120 size = sizeof(struct btrfs_node)
121 + hdr.nritems * sizeof(struct btrfs_key_ptr);
123 size = btrfs_info.sb.nodesize;
127 debug("%s: malloc failed\n", __func__);
131 if (!btrfs_devread(physical + offset, size - offset,
132 ((u8 *) res) + offset)) {
139 for (i = 0; i < hdr.nritems; ++i)
140 btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
142 for (i = 0; i < hdr.nritems; ++i)
143 btrfs_item_to_cpu(&res->leaf.items[i]);
150 int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
151 struct btrfs_path *p)
155 u64 logical, physical;
156 union btrfs_tree_node *buf;
160 logical = root->bytenr;
162 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
163 physical = btrfs_map_logical_to_physical(logical);
164 if (physical == -1ULL)
167 if (read_tree_node(physical, &buf))
170 lvl = buf->header.level;
171 if (i && prev_lvl != lvl + 1) {
172 printf("%s: invalid level in header at %llu\n",
178 ret = btrfs_bin_search(buf, key, &slot);
181 if (ret && slot > 0 && lvl)
184 p->slots[lvl] = slot;
188 logical = buf->node.ptrs[slot].blockptr;
199 static int jump_leaf(struct btrfs_path *path, int dir)
203 int level = 1, from_level, i;
205 dir = dir >= 0 ? 1 : -1;
209 while (level < BTRFS_MAX_LEVEL) {
213 slot = p.slots[level];
214 if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
215 || (dir < 0 && !slot))
221 if (level == BTRFS_MAX_LEVEL)
224 p.slots[level] = slot + dir;
229 u64 logical, physical;
231 slot = p.slots[level + 1];
232 logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
233 physical = btrfs_map_logical_to_physical(logical);
234 if (physical == -1ULL)
237 if (read_tree_node(physical, &p.nodes[level]))
243 p.slots[level] = p.nodes[level]->header.nritems - 1;
247 /* Free rewritten nodes in path */
248 for (i = 0; i <= from_level; ++i)
249 free(path->nodes[i]);
255 /* Free rewritten nodes in p */
256 for (i = level + 1; i <= from_level; ++i)
261 int btrfs_prev_slot(struct btrfs_path *p)
264 return jump_leaf(p, -1);
270 int btrfs_next_slot(struct btrfs_path *p)
272 struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
274 if (p->slots[0] >= leaf->header.nritems)
275 return jump_leaf(p, 1);