1 // SPDX-License-Identifier: GPL-2.0+
3 * BTRFS filesystem implementation for U-Boot
5 * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
13 int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b)
15 if (a->objectid > b->objectid)
17 if (a->objectid < b->objectid)
19 if (a->type > b->type)
21 if (a->type < b->type)
23 if (a->offset > b->offset)
25 if (a->offset < b->offset)
30 int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
32 if (a->objectid > b->objectid)
34 if (a->objectid < b->objectid)
36 if (a->type > b->type)
38 if (a->type < b->type)
43 static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
46 int low = 0, high = max, mid, ret;
47 struct btrfs_key *tmp;
50 mid = (low + high) / 2;
52 tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
53 ret = btrfs_comp_keys(tmp, key);
69 int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
75 if (p->header.level) {
77 size = sizeof(struct btrfs_key_ptr);
80 size = sizeof(struct btrfs_item);
83 return generic_bin_search(addr, size, key, p->header.nritems, slot);
86 static void clear_path(struct btrfs_path *p)
90 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
96 void btrfs_free_path(struct btrfs_path *p)
100 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
108 static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
110 ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr,
111 sizeof(struct btrfs_header));
112 unsigned long size, offset = sizeof(*hdr);
113 union btrfs_tree_node *res;
116 if (!btrfs_devread(physical, sizeof(*hdr), hdr))
119 btrfs_header_to_cpu(hdr);
122 size = sizeof(struct btrfs_node)
123 + hdr->nritems * sizeof(struct btrfs_key_ptr);
125 size = btrfs_info.sb.nodesize;
127 res = malloc_cache_aligned(size);
129 debug("%s: malloc failed\n", __func__);
133 if (!btrfs_devread(physical + offset, size - offset,
134 ((u8 *) res) + offset)) {
139 memcpy(&res->header, hdr, sizeof(*hdr));
141 for (i = 0; i < hdr->nritems; ++i)
142 btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
144 for (i = 0; i < hdr->nritems; ++i)
145 btrfs_item_to_cpu(&res->leaf.items[i]);
152 int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
153 struct btrfs_path *p)
157 u64 logical, physical;
158 union btrfs_tree_node *buf;
162 logical = root->bytenr;
164 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
165 physical = btrfs_map_logical_to_physical(logical);
166 if (physical == -1ULL)
169 if (read_tree_node(physical, &buf))
172 lvl = buf->header.level;
173 if (i && prev_lvl != lvl + 1) {
174 printf("%s: invalid level in header at %llu\n",
180 ret = btrfs_bin_search(buf, key, &slot);
183 if (ret && slot > 0 && lvl)
186 p->slots[lvl] = slot;
190 logical = buf->node.ptrs[slot].blockptr;
193 * The path might be invalid if:
194 * cur leaf max < searched value < next leaf min
196 * Jump to the next valid element if it exists.
198 if (slot >= buf->header.nritems)
199 if (btrfs_next_slot(p) < 0)
211 static int jump_leaf(struct btrfs_path *path, int dir)
215 int level = 1, from_level, i;
217 dir = dir >= 0 ? 1 : -1;
221 while (level < BTRFS_MAX_LEVEL) {
225 slot = p.slots[level];
226 if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
227 || (dir < 0 && !slot))
233 if (level == BTRFS_MAX_LEVEL)
236 p.slots[level] = slot + dir;
241 u64 logical, physical;
243 slot = p.slots[level + 1];
244 logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
245 physical = btrfs_map_logical_to_physical(logical);
246 if (physical == -1ULL)
249 if (read_tree_node(physical, &p.nodes[level]))
255 p.slots[level] = p.nodes[level]->header.nritems - 1;
259 /* Free rewritten nodes in path */
260 for (i = 0; i <= from_level; ++i)
261 free(path->nodes[i]);
267 /* Free rewritten nodes in p */
268 for (i = level + 1; i <= from_level; ++i)
273 int btrfs_prev_slot(struct btrfs_path *p)
276 return jump_leaf(p, -1);
282 int btrfs_next_slot(struct btrfs_path *p)
284 struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
286 if (p->slots[0] + 1 >= leaf->header.nritems)
287 return jump_leaf(p, 1);