ctree.c 18 KB

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