1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * BTRFS filesystem implementation for U-Boot
4 *
5 * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
6 */
7
8 #include "btrfs.h"
9 #include <malloc.h>
10
btrfs_comp_keys(struct btrfs_key * a,struct btrfs_key * b)11 int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b)
12 {
13 if (a->objectid > b->objectid)
14 return 1;
15 if (a->objectid < b->objectid)
16 return -1;
17 if (a->type > b->type)
18 return 1;
19 if (a->type < b->type)
20 return -1;
21 if (a->offset > b->offset)
22 return 1;
23 if (a->offset < b->offset)
24 return -1;
25 return 0;
26 }
27
btrfs_comp_keys_type(struct btrfs_key * a,struct btrfs_key * b)28 int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
29 {
30 if (a->objectid > b->objectid)
31 return 1;
32 if (a->objectid < b->objectid)
33 return -1;
34 if (a->type > b->type)
35 return 1;
36 if (a->type < b->type)
37 return -1;
38 return 0;
39 }
40
generic_bin_search(void * addr,int item_size,struct btrfs_key * key,int max,int * slot)41 static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
42 int max, int *slot)
43 {
44 int low = 0, high = max, mid, ret;
45 struct btrfs_key *tmp;
46
47 while (low < high) {
48 mid = (low + high) / 2;
49
50 tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
51 ret = btrfs_comp_keys(tmp, key);
52
53 if (ret < 0) {
54 low = mid + 1;
55 } else if (ret > 0) {
56 high = mid;
57 } else {
58 *slot = mid;
59 return 0;
60 }
61 }
62
63 *slot = low;
64 return 1;
65 }
66
btrfs_bin_search(union btrfs_tree_node * p,struct btrfs_key * key,int * slot)67 int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
68 int *slot)
69 {
70 void *addr;
71 unsigned long size;
72
73 if (p->header.level) {
74 addr = p->node.ptrs;
75 size = sizeof(struct btrfs_key_ptr);
76 } else {
77 addr = p->leaf.items;
78 size = sizeof(struct btrfs_item);
79 }
80
81 return generic_bin_search(addr, size, key, p->header.nritems, slot);
82 }
83
clear_path(struct btrfs_path * p)84 static void clear_path(struct btrfs_path *p)
85 {
86 int i;
87
88 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
89 p->nodes[i] = NULL;
90 p->slots[i] = 0;
91 }
92 }
93
btrfs_free_path(struct btrfs_path * p)94 void btrfs_free_path(struct btrfs_path *p)
95 {
96 int i;
97
98 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
99 if (p->nodes[i])
100 free(p->nodes[i]);
101 }
102
103 clear_path(p);
104 }
105
read_tree_node(u64 physical,union btrfs_tree_node ** buf)106 static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
107 {
108 struct btrfs_header hdr;
109 unsigned long size, offset = sizeof(hdr);
110 union btrfs_tree_node *res;
111 u32 i;
112
113 if (!btrfs_devread(physical, sizeof(hdr), &hdr))
114 return -1;
115
116 btrfs_header_to_cpu(&hdr);
117
118 if (hdr.level)
119 size = sizeof(struct btrfs_node)
120 + hdr.nritems * sizeof(struct btrfs_key_ptr);
121 else
122 size = btrfs_info.sb.nodesize;
123
124 res = malloc(size);
125 if (!res) {
126 debug("%s: malloc failed\n", __func__);
127 return -1;
128 }
129
130 if (!btrfs_devread(physical + offset, size - offset,
131 ((u8 *) res) + offset)) {
132 free(res);
133 return -1;
134 }
135
136 res->header = hdr;
137 if (hdr.level)
138 for (i = 0; i < hdr.nritems; ++i)
139 btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
140 else
141 for (i = 0; i < hdr.nritems; ++i)
142 btrfs_item_to_cpu(&res->leaf.items[i]);
143
144 *buf = res;
145
146 return 0;
147 }
148
btrfs_search_tree(const struct btrfs_root * root,struct btrfs_key * key,struct btrfs_path * p)149 int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
150 struct btrfs_path *p)
151 {
152 u8 lvl, prev_lvl;
153 int i, slot, ret;
154 u64 logical, physical;
155 union btrfs_tree_node *buf;
156
157 clear_path(p);
158
159 logical = root->bytenr;
160
161 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
162 physical = btrfs_map_logical_to_physical(logical);
163 if (physical == -1ULL)
164 goto err;
165
166 if (read_tree_node(physical, &buf))
167 goto err;
168
169 lvl = buf->header.level;
170 if (i && prev_lvl != lvl + 1) {
171 printf("%s: invalid level in header at %llu\n",
172 __func__, logical);
173 goto err;
174 }
175 prev_lvl = lvl;
176
177 ret = btrfs_bin_search(buf, key, &slot);
178 if (ret < 0)
179 goto err;
180 if (ret && slot > 0 && lvl)
181 slot -= 1;
182
183 p->slots[lvl] = slot;
184 p->nodes[lvl] = buf;
185
186 if (lvl)
187 logical = buf->node.ptrs[slot].blockptr;
188 else
189 break;
190 }
191
192 return 0;
193 err:
194 btrfs_free_path(p);
195 return -1;
196 }
197
jump_leaf(struct btrfs_path * path,int dir)198 static int jump_leaf(struct btrfs_path *path, int dir)
199 {
200 struct btrfs_path p;
201 u32 slot;
202 int level = 1, from_level, i;
203
204 dir = dir >= 0 ? 1 : -1;
205
206 p = *path;
207
208 while (level < BTRFS_MAX_LEVEL) {
209 if (!p.nodes[level])
210 return 1;
211
212 slot = p.slots[level];
213 if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
214 || (dir < 0 && !slot))
215 level++;
216 else
217 break;
218 }
219
220 if (level == BTRFS_MAX_LEVEL)
221 return 1;
222
223 p.slots[level] = slot + dir;
224 level--;
225 from_level = level;
226
227 while (level >= 0) {
228 u64 logical, physical;
229
230 slot = p.slots[level + 1];
231 logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
232 physical = btrfs_map_logical_to_physical(logical);
233 if (physical == -1ULL)
234 goto err;
235
236 if (read_tree_node(physical, &p.nodes[level]))
237 goto err;
238
239 if (dir > 0)
240 p.slots[level] = 0;
241 else
242 p.slots[level] = p.nodes[level]->header.nritems - 1;
243 level--;
244 }
245
246 /* Free rewritten nodes in path */
247 for (i = 0; i <= from_level; ++i)
248 free(path->nodes[i]);
249
250 *path = p;
251 return 0;
252
253 err:
254 /* Free rewritten nodes in p */
255 for (i = level + 1; i <= from_level; ++i)
256 free(p.nodes[i]);
257 return -1;
258 }
259
btrfs_prev_slot(struct btrfs_path * p)260 int btrfs_prev_slot(struct btrfs_path *p)
261 {
262 if (!p->slots[0])
263 return jump_leaf(p, -1);
264
265 p->slots[0]--;
266 return 0;
267 }
268
btrfs_next_slot(struct btrfs_path * p)269 int btrfs_next_slot(struct btrfs_path *p)
270 {
271 struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
272
273 if (p->slots[0] >= leaf->header.nritems)
274 return jump_leaf(p, 1);
275
276 p->slots[0]++;
277 return 0;
278 }
279