]> git.sur5r.net Git - u-boot/blob - fs/btrfs/ctree.c
Merge branch 'master' of git://git.denx.de/u-boot-usb
[u-boot] / fs / btrfs / ctree.c
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
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
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
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
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
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
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
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
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
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
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
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 }