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