blob: 8e932adc425d316966d8ece8a53502c9c84946ec [file] [log] [blame]
Tom Rini83d290c2018-05-06 17:58:06 -04001// SPDX-License-Identifier: GPL-2.0+
Marek Behún21a14fa2017-09-03 17:00:28 +02002/*
3 * BTRFS filesystem implementation for U-Boot
4 *
Marek Behún61143f72022-06-01 17:17:06 +02005 * 2017 Marek Behún, CZ.NIC, kabel@kernel.org
Marek Behún21a14fa2017-09-03 17:00:28 +02006 */
7
Qu Wenruo29c26ae2020-06-24 18:02:59 +02008#include <linux/kernel.h>
Simon Glassf7ae49f2020-05-10 11:40:05 -06009#include <log.h>
Marek Behún21a14fa2017-09-03 17:00:28 +020010#include <malloc.h>
Marek Vasutc9795392018-09-22 04:13:35 +020011#include <memalign.h>
Qu Wenruo29c26ae2020-06-24 18:02:59 +020012#include "btrfs.h"
13#include "disk-io.h"
Marek Behún21a14fa2017-09-03 17:00:28 +020014
Qu Wenruo4aebb992020-06-24 18:02:49 +020015static 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
25u16 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
32const char *btrfs_super_csum_name(u16 csum_type)
33{
34 return btrfs_csums[csum_type].name;
35}
36
37size_t btrfs_super_num_csums(void)
38{
39 return ARRAY_SIZE(btrfs_csums);
40}
41
42u16 btrfs_csum_type_size(u16 csum_type)
43{
44 return btrfs_csums[csum_type].size;
45}
46
Qu Wenruo29c26ae2020-06-24 18:02:59 +020047struct 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
54void btrfs_free_path(struct btrfs_path *p)
55{
56 if (!p)
57 return;
58 btrfs_release_path(p);
59 kfree(p);
60}
61
62void 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
Qu Wenruo75b08172020-06-24 18:02:55 +020073int 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
90static 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
99enum btrfs_tree_block_status
100btrfs_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;
126fail:
127 return ret;
128}
129
130enum btrfs_tree_block_status
131btrfs_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;
211fail:
212 return ret;
213}
214
Qu Wenruo29c26ae2020-06-24 18:02:59 +0200215static 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 */
247static 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 */
282int 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
299struct 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
328int 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
367out:
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 */
389int 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 */
496int 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
504again:
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
Qu Wenruo75b08172020-06-24 18:02:55 +0200558/*
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 */
563static 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 */
583int 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}
Qu Wenruo29c26ae2020-06-24 18:02:59 +0200599
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 */
605int 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 */
665int 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
708int 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}