• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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