]>
Commit | Line | Data |
---|---|---|
1 | // SPDX-License-Identifier: GPL-2.0+ | |
2 | /* | |
3 | * BTRFS filesystem implementation for U-Boot | |
4 | * | |
5 | * 2017 Marek BehĂșn, CZ.NIC, kabel@kernel.org | |
6 | */ | |
7 | ||
8 | #include <linux/kernel.h> | |
9 | #include <log.h> | |
10 | #include <malloc.h> | |
11 | #include <memalign.h> | |
12 | #include "btrfs.h" | |
13 | #include "disk-io.h" | |
14 | ||
15 | static const struct btrfs_csum { | |
16 | u16 size; | |
17 | const char name[14]; | |
18 | } btrfs_csums[] = { | |
19 | [BTRFS_CSUM_TYPE_CRC32] = { 4, "crc32c" }, | |
20 | [BTRFS_CSUM_TYPE_XXHASH] = { 8, "xxhash64" }, | |
21 | [BTRFS_CSUM_TYPE_SHA256] = { 32, "sha256" }, | |
22 | [BTRFS_CSUM_TYPE_BLAKE2] = { 32, "blake2" }, | |
23 | }; | |
24 | ||
25 | u16 btrfs_super_csum_size(const struct btrfs_super_block *sb) | |
26 | { | |
27 | const u16 csum_type = btrfs_super_csum_type(sb); | |
28 | ||
29 | return btrfs_csums[csum_type].size; | |
30 | } | |
31 | ||
32 | const char *btrfs_super_csum_name(u16 csum_type) | |
33 | { | |
34 | return btrfs_csums[csum_type].name; | |
35 | } | |
36 | ||
37 | size_t btrfs_super_num_csums(void) | |
38 | { | |
39 | return ARRAY_SIZE(btrfs_csums); | |
40 | } | |
41 | ||
42 | u16 btrfs_csum_type_size(u16 csum_type) | |
43 | { | |
44 | return btrfs_csums[csum_type].size; | |
45 | } | |
46 | ||
47 | struct btrfs_path *btrfs_alloc_path(void) | |
48 | { | |
49 | struct btrfs_path *path; | |
50 | path = kzalloc(sizeof(struct btrfs_path), GFP_NOFS); | |
51 | return path; | |
52 | } | |
53 | ||
54 | void btrfs_free_path(struct btrfs_path *p) | |
55 | { | |
56 | if (!p) | |
57 | return; | |
58 | btrfs_release_path(p); | |
59 | kfree(p); | |
60 | } | |
61 | ||
62 | void btrfs_release_path(struct btrfs_path *p) | |
63 | { | |
64 | int i; | |
65 | for (i = 0; i < BTRFS_MAX_LEVEL; i++) { | |
66 | if (!p->nodes[i]) | |
67 | continue; | |
68 | free_extent_buffer(p->nodes[i]); | |
69 | } | |
70 | memset(p, 0, sizeof(*p)); | |
71 | } | |
72 | ||
73 | int btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2) | |
74 | { | |
75 | if (k1->objectid > k2->objectid) | |
76 | return 1; | |
77 | if (k1->objectid < k2->objectid) | |
78 | return -1; | |
79 | if (k1->type > k2->type) | |
80 | return 1; | |
81 | if (k1->type < k2->type) | |
82 | return -1; | |
83 | if (k1->offset > k2->offset) | |
84 | return 1; | |
85 | if (k1->offset < k2->offset) | |
86 | return -1; | |
87 | return 0; | |
88 | } | |
89 | ||
90 | static int btrfs_comp_keys(struct btrfs_disk_key *disk, | |
91 | const struct btrfs_key *k2) | |
92 | { | |
93 | struct btrfs_key k1; | |
94 | ||
95 | btrfs_disk_key_to_cpu(&k1, disk); | |
96 | return btrfs_comp_cpu_keys(&k1, k2); | |
97 | } | |
98 | ||
99 | enum btrfs_tree_block_status | |
100 | btrfs_check_node(struct btrfs_fs_info *fs_info, | |
101 | struct btrfs_disk_key *parent_key, struct extent_buffer *buf) | |
102 | { | |
103 | int i; | |
104 | struct btrfs_key cpukey; | |
105 | struct btrfs_disk_key key; | |
106 | u32 nritems = btrfs_header_nritems(buf); | |
107 | enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS; | |
108 | ||
109 | if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(fs_info)) | |
110 | goto fail; | |
111 | ||
112 | ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY; | |
113 | if (parent_key && parent_key->type) { | |
114 | btrfs_node_key(buf, &key, 0); | |
115 | if (memcmp(parent_key, &key, sizeof(key))) | |
116 | goto fail; | |
117 | } | |
118 | ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER; | |
119 | for (i = 0; nritems > 1 && i < nritems - 2; i++) { | |
120 | btrfs_node_key(buf, &key, i); | |
121 | btrfs_node_key_to_cpu(buf, &cpukey, i + 1); | |
122 | if (btrfs_comp_keys(&key, &cpukey) >= 0) | |
123 | goto fail; | |
124 | } | |
125 | return BTRFS_TREE_BLOCK_CLEAN; | |
126 | fail: | |
127 | return ret; | |
128 | } | |
129 | ||
130 | enum btrfs_tree_block_status | |
131 | btrfs_check_leaf(struct btrfs_fs_info *fs_info, | |
132 | struct btrfs_disk_key *parent_key, struct extent_buffer *buf) | |
133 | { | |
134 | int i; | |
135 | struct btrfs_key cpukey; | |
136 | struct btrfs_disk_key key; | |
137 | u32 nritems = btrfs_header_nritems(buf); | |
138 | enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS; | |
139 | ||
140 | if (nritems * sizeof(struct btrfs_item) > buf->len) { | |
141 | fprintf(stderr, "invalid number of items %llu\n", | |
142 | (unsigned long long)buf->start); | |
143 | goto fail; | |
144 | } | |
145 | ||
146 | if (btrfs_header_level(buf) != 0) { | |
147 | ret = BTRFS_TREE_BLOCK_INVALID_LEVEL; | |
148 | fprintf(stderr, "leaf is not a leaf %llu\n", | |
149 | (unsigned long long)btrfs_header_bytenr(buf)); | |
150 | goto fail; | |
151 | } | |
152 | if (btrfs_leaf_free_space(buf) < 0) { | |
153 | ret = BTRFS_TREE_BLOCK_INVALID_FREE_SPACE; | |
154 | fprintf(stderr, "leaf free space incorrect %llu %d\n", | |
155 | (unsigned long long)btrfs_header_bytenr(buf), | |
156 | btrfs_leaf_free_space(buf)); | |
157 | goto fail; | |
158 | } | |
159 | ||
160 | if (nritems == 0) | |
161 | return BTRFS_TREE_BLOCK_CLEAN; | |
162 | ||
163 | btrfs_item_key(buf, &key, 0); | |
164 | if (parent_key && parent_key->type && | |
165 | memcmp(parent_key, &key, sizeof(key))) { | |
166 | ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY; | |
167 | fprintf(stderr, "leaf parent key incorrect %llu\n", | |
168 | (unsigned long long)btrfs_header_bytenr(buf)); | |
169 | goto fail; | |
170 | } | |
171 | for (i = 0; nritems > 1 && i < nritems - 1; i++) { | |
172 | btrfs_item_key(buf, &key, i); | |
173 | btrfs_item_key_to_cpu(buf, &cpukey, i + 1); | |
174 | if (btrfs_comp_keys(&key, &cpukey) >= 0) { | |
175 | ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER; | |
176 | fprintf(stderr, "bad key ordering %d %d\n", i, i+1); | |
177 | goto fail; | |
178 | } | |
179 | if (btrfs_item_offset_nr(buf, i) != | |
180 | btrfs_item_end_nr(buf, i + 1)) { | |
181 | ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS; | |
182 | fprintf(stderr, "incorrect offsets %u %u\n", | |
183 | btrfs_item_offset_nr(buf, i), | |
184 | btrfs_item_end_nr(buf, i + 1)); | |
185 | goto fail; | |
186 | } | |
187 | if (i == 0 && btrfs_item_end_nr(buf, i) != | |
188 | BTRFS_LEAF_DATA_SIZE(fs_info)) { | |
189 | ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS; | |
190 | fprintf(stderr, "bad item end %u wanted %u\n", | |
191 | btrfs_item_end_nr(buf, i), | |
192 | (unsigned)BTRFS_LEAF_DATA_SIZE(fs_info)); | |
193 | goto fail; | |
194 | } | |
195 | } | |
196 | ||
197 | for (i = 0; i < nritems; i++) { | |
198 | if (btrfs_item_end_nr(buf, i) > | |
199 | BTRFS_LEAF_DATA_SIZE(fs_info)) { | |
200 | btrfs_item_key(buf, &key, 0); | |
201 | ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS; | |
202 | fprintf(stderr, "slot end outside of leaf %llu > %llu\n", | |
203 | (unsigned long long)btrfs_item_end_nr(buf, i), | |
204 | (unsigned long long)BTRFS_LEAF_DATA_SIZE( | |
205 | fs_info)); | |
206 | goto fail; | |
207 | } | |
208 | } | |
209 | ||
210 | return BTRFS_TREE_BLOCK_CLEAN; | |
211 | fail: | |
212 | return ret; | |
213 | } | |
214 | ||
215 | static int noinline check_block(struct btrfs_fs_info *fs_info, | |
216 | struct btrfs_path *path, int level) | |
217 | { | |
218 | struct btrfs_disk_key key; | |
219 | struct btrfs_disk_key *key_ptr = NULL; | |
220 | struct extent_buffer *parent; | |
221 | enum btrfs_tree_block_status ret; | |
222 | ||
223 | if (path->nodes[level + 1]) { | |
224 | parent = path->nodes[level + 1]; | |
225 | btrfs_node_key(parent, &key, path->slots[level + 1]); | |
226 | key_ptr = &key; | |
227 | } | |
228 | if (level == 0) | |
229 | ret = btrfs_check_leaf(fs_info, key_ptr, path->nodes[0]); | |
230 | else | |
231 | ret = btrfs_check_node(fs_info, key_ptr, path->nodes[level]); | |
232 | if (ret == BTRFS_TREE_BLOCK_CLEAN) | |
233 | return 0; | |
234 | return -EIO; | |
235 | } | |
236 | ||
237 | /* | |
238 | * search for key in the extent_buffer. The items start at offset p, | |
239 | * and they are item_size apart. There are 'max' items in p. | |
240 | * | |
241 | * the slot in the array is returned via slot, and it points to | |
242 | * the place where you would insert key if it is not found in | |
243 | * the array. | |
244 | * | |
245 | * slot may point to max if the key is bigger than all of the keys | |
246 | */ | |
247 | static int generic_bin_search(struct extent_buffer *eb, unsigned long p, | |
248 | int item_size, const struct btrfs_key *key, | |
249 | int max, int *slot) | |
250 | { | |
251 | int low = 0; | |
252 | int high = max; | |
253 | int mid; | |
254 | int ret; | |
255 | unsigned long offset; | |
256 | struct btrfs_disk_key *tmp; | |
257 | ||
258 | while(low < high) { | |
259 | mid = (low + high) / 2; | |
260 | offset = p + mid * item_size; | |
261 | ||
262 | tmp = (struct btrfs_disk_key *)(eb->data + offset); | |
263 | ret = btrfs_comp_keys(tmp, key); | |
264 | ||
265 | if (ret < 0) | |
266 | low = mid + 1; | |
267 | else if (ret > 0) | |
268 | high = mid; | |
269 | else { | |
270 | *slot = mid; | |
271 | return 0; | |
272 | } | |
273 | } | |
274 | *slot = low; | |
275 | return 1; | |
276 | } | |
277 | ||
278 | /* | |
279 | * simple bin_search frontend that does the right thing for | |
280 | * leaves vs nodes | |
281 | */ | |
282 | int btrfs_bin_search(struct extent_buffer *eb, const struct btrfs_key *key, | |
283 | int *slot) | |
284 | { | |
285 | if (btrfs_header_level(eb) == 0) | |
286 | return generic_bin_search(eb, | |
287 | offsetof(struct btrfs_leaf, items), | |
288 | sizeof(struct btrfs_item), | |
289 | key, btrfs_header_nritems(eb), | |
290 | slot); | |
291 | else | |
292 | return generic_bin_search(eb, | |
293 | offsetof(struct btrfs_node, ptrs), | |
294 | sizeof(struct btrfs_key_ptr), | |
295 | key, btrfs_header_nritems(eb), | |
296 | slot); | |
297 | } | |
298 | ||
299 | struct extent_buffer *read_node_slot(struct btrfs_fs_info *fs_info, | |
300 | struct extent_buffer *parent, int slot) | |
301 | { | |
302 | struct extent_buffer *ret; | |
303 | int level = btrfs_header_level(parent); | |
304 | ||
305 | if (slot < 0) | |
306 | return NULL; | |
307 | if (slot >= btrfs_header_nritems(parent)) | |
308 | return NULL; | |
309 | ||
310 | if (level == 0) | |
311 | return NULL; | |
312 | ||
313 | ret = read_tree_block(fs_info, btrfs_node_blockptr(parent, slot), | |
314 | btrfs_node_ptr_generation(parent, slot)); | |
315 | if (!extent_buffer_uptodate(ret)) | |
316 | return ERR_PTR(-EIO); | |
317 | ||
318 | if (btrfs_header_level(ret) != level - 1) { | |
319 | error("child eb corrupted: parent bytenr=%llu item=%d parent level=%d child level=%d", | |
320 | btrfs_header_bytenr(parent), slot, | |
321 | btrfs_header_level(parent), btrfs_header_level(ret)); | |
322 | free_extent_buffer(ret); | |
323 | return ERR_PTR(-EIO); | |
324 | } | |
325 | return ret; | |
326 | } | |
327 | ||
328 | int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path, | |
329 | u64 iobjectid, u64 ioff, u8 key_type, | |
330 | struct btrfs_key *found_key) | |
331 | { | |
332 | int ret; | |
333 | struct btrfs_key key; | |
334 | struct extent_buffer *eb; | |
335 | struct btrfs_path *path; | |
336 | ||
337 | key.type = key_type; | |
338 | key.objectid = iobjectid; | |
339 | key.offset = ioff; | |
340 | ||
341 | if (found_path == NULL) { | |
342 | path = btrfs_alloc_path(); | |
343 | if (!path) | |
344 | return -ENOMEM; | |
345 | } else | |
346 | path = found_path; | |
347 | ||
348 | ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); | |
349 | if ((ret < 0) || (found_key == NULL)) | |
350 | goto out; | |
351 | ||
352 | eb = path->nodes[0]; | |
353 | if (ret && path->slots[0] >= btrfs_header_nritems(eb)) { | |
354 | ret = btrfs_next_leaf(fs_root, path); | |
355 | if (ret) | |
356 | goto out; | |
357 | eb = path->nodes[0]; | |
358 | } | |
359 | ||
360 | btrfs_item_key_to_cpu(eb, found_key, path->slots[0]); | |
361 | if (found_key->type != key.type || | |
362 | found_key->objectid != key.objectid) { | |
363 | ret = 1; | |
364 | goto out; | |
365 | } | |
366 | ||
367 | out: | |
368 | if (path != found_path) | |
369 | btrfs_free_path(path); | |
370 | return ret; | |
371 | } | |
372 | ||
373 | /* | |
374 | * look for key in the tree. path is filled in with nodes along the way | |
375 | * if key is found, we return zero and you can find the item in the leaf | |
376 | * level of the path (level 0) | |
377 | * | |
378 | * If the key isn't found, the path points to the slot where it should | |
379 | * be inserted, and 1 is returned. If there are other errors during the | |
380 | * search a negative error number is returned. | |
381 | * | |
382 | * if ins_len > 0, nodes and leaves will be split as we walk down the | |
383 | * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if | |
384 | * possible) | |
385 | * | |
386 | * NOTE: This version has no COW ability, thus we expect trans == NULL, | |
387 | * ins_len == 0 and cow == 0. | |
388 | */ | |
389 | int btrfs_search_slot(struct btrfs_trans_handle *trans, | |
390 | struct btrfs_root *root, const struct btrfs_key *key, | |
391 | struct btrfs_path *p, int ins_len, int cow) | |
392 | { | |
393 | struct extent_buffer *b; | |
394 | int slot; | |
395 | int ret; | |
396 | int level; | |
397 | struct btrfs_fs_info *fs_info = root->fs_info; | |
398 | u8 lowest_level = 0; | |
399 | ||
400 | assert(trans == NULL && ins_len == 0 && cow == 0); | |
401 | lowest_level = p->lowest_level; | |
402 | WARN_ON(lowest_level && ins_len > 0); | |
403 | WARN_ON(p->nodes[0] != NULL); | |
404 | ||
405 | b = root->node; | |
406 | extent_buffer_get(b); | |
407 | while (b) { | |
408 | level = btrfs_header_level(b); | |
409 | /* | |
410 | if (cow) { | |
411 | int wret; | |
412 | wret = btrfs_cow_block(trans, root, b, | |
413 | p->nodes[level + 1], | |
414 | p->slots[level + 1], | |
415 | &b); | |
416 | if (wret) { | |
417 | free_extent_buffer(b); | |
418 | return wret; | |
419 | } | |
420 | } | |
421 | */ | |
422 | BUG_ON(!cow && ins_len); | |
423 | if (level != btrfs_header_level(b)) | |
424 | WARN_ON(1); | |
425 | level = btrfs_header_level(b); | |
426 | p->nodes[level] = b; | |
427 | ret = check_block(fs_info, p, level); | |
428 | if (ret) | |
429 | return -1; | |
430 | ret = btrfs_bin_search(b, key, &slot); | |
431 | if (level != 0) { | |
432 | if (ret && slot > 0) | |
433 | slot -= 1; | |
434 | p->slots[level] = slot; | |
435 | /* | |
436 | if ((p->search_for_split || ins_len > 0) && | |
437 | btrfs_header_nritems(b) >= | |
438 | BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) { | |
439 | int sret = split_node(trans, root, p, level); | |
440 | BUG_ON(sret > 0); | |
441 | if (sret) | |
442 | return sret; | |
443 | b = p->nodes[level]; | |
444 | slot = p->slots[level]; | |
445 | } else if (ins_len < 0) { | |
446 | int sret = balance_level(trans, root, p, | |
447 | level); | |
448 | if (sret) | |
449 | return sret; | |
450 | b = p->nodes[level]; | |
451 | if (!b) { | |
452 | btrfs_release_path(p); | |
453 | goto again; | |
454 | } | |
455 | slot = p->slots[level]; | |
456 | BUG_ON(btrfs_header_nritems(b) == 1); | |
457 | } | |
458 | */ | |
459 | /* this is only true while dropping a snapshot */ | |
460 | if (level == lowest_level) | |
461 | break; | |
462 | ||
463 | b = read_node_slot(fs_info, b, slot); | |
464 | if (!extent_buffer_uptodate(b)) | |
465 | return -EIO; | |
466 | } else { | |
467 | p->slots[level] = slot; | |
468 | /* | |
469 | if (ins_len > 0 && | |
470 | ins_len > btrfs_leaf_free_space(b)) { | |
471 | int sret = split_leaf(trans, root, key, | |
472 | p, ins_len, ret == 0); | |
473 | BUG_ON(sret > 0); | |
474 | if (sret) | |
475 | return sret; | |
476 | } | |
477 | */ | |
478 | return ret; | |
479 | } | |
480 | } | |
481 | return 1; | |
482 | } | |
483 | ||
484 | /* | |
485 | * Helper to use instead of search slot if no exact match is needed but | |
486 | * instead the next or previous item should be returned. | |
487 | * When find_higher is true, the next higher item is returned, the next lower | |
488 | * otherwise. | |
489 | * When return_any and find_higher are both true, and no higher item is found, | |
490 | * return the next lower instead. | |
491 | * When return_any is true and find_higher is false, and no lower item is found, | |
492 | * return the next higher instead. | |
493 | * It returns 0 if any item is found, 1 if none is found (tree empty), and | |
494 | * < 0 on error | |
495 | */ | |
496 | int btrfs_search_slot_for_read(struct btrfs_root *root, | |
497 | const struct btrfs_key *key, | |
498 | struct btrfs_path *p, int find_higher, | |
499 | int return_any) | |
500 | { | |
501 | int ret; | |
502 | struct extent_buffer *leaf; | |
503 | ||
504 | again: | |
505 | ret = btrfs_search_slot(NULL, root, key, p, 0, 0); | |
506 | if (ret <= 0) | |
507 | return ret; | |
508 | /* | |
509 | * A return value of 1 means the path is at the position where the item | |
510 | * should be inserted. Normally this is the next bigger item, but in | |
511 | * case the previous item is the last in a leaf, path points to the | |
512 | * first free slot in the previous leaf, i.e. at an invalid item. | |
513 | */ | |
514 | leaf = p->nodes[0]; | |
515 | ||
516 | if (find_higher) { | |
517 | if (p->slots[0] >= btrfs_header_nritems(leaf)) { | |
518 | ret = btrfs_next_leaf(root, p); | |
519 | if (ret <= 0) | |
520 | return ret; | |
521 | if (!return_any) | |
522 | return 1; | |
523 | /* | |
524 | * No higher item found, return the next lower instead | |
525 | */ | |
526 | return_any = 0; | |
527 | find_higher = 0; | |
528 | btrfs_release_path(p); | |
529 | goto again; | |
530 | } | |
531 | } else { | |
532 | if (p->slots[0] == 0) { | |
533 | ret = btrfs_prev_leaf(root, p); | |
534 | if (ret < 0) | |
535 | return ret; | |
536 | if (!ret) { | |
537 | leaf = p->nodes[0]; | |
538 | if (p->slots[0] == btrfs_header_nritems(leaf)) | |
539 | p->slots[0]--; | |
540 | return 0; | |
541 | } | |
542 | if (!return_any) | |
543 | return 1; | |
544 | /* | |
545 | * No lower item found, return the next higher instead | |
546 | */ | |
547 | return_any = 0; | |
548 | find_higher = 1; | |
549 | btrfs_release_path(p); | |
550 | goto again; | |
551 | } else { | |
552 | --p->slots[0]; | |
553 | } | |
554 | } | |
555 | return 0; | |
556 | } | |
557 | ||
558 | /* | |
559 | * how many bytes are required to store the items in a leaf. start | |
560 | * and nr indicate which items in the leaf to check. This totals up the | |
561 | * space used both by the item structs and the item data | |
562 | */ | |
563 | static int leaf_space_used(struct extent_buffer *l, int start, int nr) | |
564 | { | |
565 | int data_len; | |
566 | int nritems = btrfs_header_nritems(l); | |
567 | int end = min(nritems, start + nr) - 1; | |
568 | ||
569 | if (!nr) | |
570 | return 0; | |
571 | data_len = btrfs_item_end_nr(l, start); | |
572 | data_len = data_len - btrfs_item_offset_nr(l, end); | |
573 | data_len += sizeof(struct btrfs_item) * nr; | |
574 | WARN_ON(data_len < 0); | |
575 | return data_len; | |
576 | } | |
577 | ||
578 | /* | |
579 | * The space between the end of the leaf items and | |
580 | * the start of the leaf data. IOW, how much room | |
581 | * the leaf has left for both items and data | |
582 | */ | |
583 | int btrfs_leaf_free_space(struct extent_buffer *leaf) | |
584 | { | |
585 | int nritems = btrfs_header_nritems(leaf); | |
586 | u32 leaf_data_size; | |
587 | int ret; | |
588 | ||
589 | BUG_ON(leaf->fs_info && leaf->fs_info->nodesize != leaf->len); | |
590 | leaf_data_size = __BTRFS_LEAF_DATA_SIZE(leaf->len); | |
591 | ret = leaf_data_size - leaf_space_used(leaf, 0 ,nritems); | |
592 | if (ret < 0) { | |
593 | printk("leaf free space ret %d, leaf data size %u, used %d nritems %d\n", | |
594 | ret, leaf_data_size, leaf_space_used(leaf, 0, nritems), | |
595 | nritems); | |
596 | } | |
597 | return ret; | |
598 | } | |
599 | ||
600 | /* | |
601 | * walk up the tree as far as required to find the previous leaf. | |
602 | * returns 0 if it found something or 1 if there are no lesser leaves. | |
603 | * returns < 0 on io errors. | |
604 | */ | |
605 | int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) | |
606 | { | |
607 | int slot; | |
608 | int level = 1; | |
609 | struct extent_buffer *c; | |
610 | struct extent_buffer *next = NULL; | |
611 | struct btrfs_fs_info *fs_info = root->fs_info; | |
612 | ||
613 | while(level < BTRFS_MAX_LEVEL) { | |
614 | if (!path->nodes[level]) | |
615 | return 1; | |
616 | ||
617 | slot = path->slots[level]; | |
618 | c = path->nodes[level]; | |
619 | if (slot == 0) { | |
620 | level++; | |
621 | if (level == BTRFS_MAX_LEVEL) | |
622 | return 1; | |
623 | continue; | |
624 | } | |
625 | slot--; | |
626 | ||
627 | next = read_node_slot(fs_info, c, slot); | |
628 | if (!extent_buffer_uptodate(next)) { | |
629 | if (IS_ERR(next)) | |
630 | return PTR_ERR(next); | |
631 | return -EIO; | |
632 | } | |
633 | break; | |
634 | } | |
635 | path->slots[level] = slot; | |
636 | while(1) { | |
637 | level--; | |
638 | c = path->nodes[level]; | |
639 | free_extent_buffer(c); | |
640 | slot = btrfs_header_nritems(next); | |
641 | if (slot != 0) | |
642 | slot--; | |
643 | path->nodes[level] = next; | |
644 | path->slots[level] = slot; | |
645 | if (!level) | |
646 | break; | |
647 | next = read_node_slot(fs_info, next, slot); | |
648 | if (!extent_buffer_uptodate(next)) { | |
649 | if (IS_ERR(next)) | |
650 | return PTR_ERR(next); | |
651 | return -EIO; | |
652 | } | |
653 | } | |
654 | return 0; | |
655 | } | |
656 | ||
657 | /* | |
658 | * Walk up the tree as far as necessary to find the next sibling tree block. | |
659 | * More generic version of btrfs_next_leaf(), as it could find sibling nodes | |
660 | * if @path->lowest_level is not 0. | |
661 | * | |
662 | * returns 0 if it found something or 1 if there are no greater leaves. | |
663 | * returns < 0 on io errors. | |
664 | */ | |
665 | int btrfs_next_sibling_tree_block(struct btrfs_fs_info *fs_info, | |
666 | struct btrfs_path *path) | |
667 | { | |
668 | int slot; | |
669 | int level = path->lowest_level + 1; | |
670 | struct extent_buffer *c; | |
671 | struct extent_buffer *next = NULL; | |
672 | ||
673 | BUG_ON(path->lowest_level + 1 >= BTRFS_MAX_LEVEL); | |
674 | do { | |
675 | if (!path->nodes[level]) | |
676 | return 1; | |
677 | ||
678 | slot = path->slots[level] + 1; | |
679 | c = path->nodes[level]; | |
680 | if (slot >= btrfs_header_nritems(c)) { | |
681 | level++; | |
682 | if (level == BTRFS_MAX_LEVEL) | |
683 | return 1; | |
684 | continue; | |
685 | } | |
686 | ||
687 | next = read_node_slot(fs_info, c, slot); | |
688 | if (!extent_buffer_uptodate(next)) | |
689 | return -EIO; | |
690 | break; | |
691 | } while (level < BTRFS_MAX_LEVEL); | |
692 | path->slots[level] = slot; | |
693 | while(1) { | |
694 | level--; | |
695 | c = path->nodes[level]; | |
696 | free_extent_buffer(c); | |
697 | path->nodes[level] = next; | |
698 | path->slots[level] = 0; | |
699 | if (level == path->lowest_level) | |
700 | break; | |
701 | next = read_node_slot(fs_info, next, 0); | |
702 | if (!extent_buffer_uptodate(next)) | |
703 | return -EIO; | |
704 | } | |
705 | return 0; | |
706 | } | |
707 | ||
708 | int btrfs_previous_item(struct btrfs_root *root, | |
709 | struct btrfs_path *path, u64 min_objectid, | |
710 | int type) | |
711 | { | |
712 | struct btrfs_key found_key; | |
713 | struct extent_buffer *leaf; | |
714 | u32 nritems; | |
715 | int ret; | |
716 | ||
717 | while(1) { | |
718 | if (path->slots[0] == 0) { | |
719 | ret = btrfs_prev_leaf(root, path); | |
720 | if (ret != 0) | |
721 | return ret; | |
722 | } else { | |
723 | path->slots[0]--; | |
724 | } | |
725 | leaf = path->nodes[0]; | |
726 | nritems = btrfs_header_nritems(leaf); | |
727 | if (nritems == 0) | |
728 | return 1; | |
729 | if (path->slots[0] == nritems) | |
730 | path->slots[0]--; | |
731 | ||
732 | btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); | |
733 | if (found_key.objectid < min_objectid) | |
734 | break; | |
735 | if (found_key.type == type) | |
736 | return 0; | |
737 | if (found_key.objectid == min_objectid && | |
738 | found_key.type < type) | |
739 | break; | |
740 | } | |
741 | return 1; | |
742 | } |