ctree.c 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290
  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 "btrfs.h"
  8. #include <malloc.h>
  9. #include <memalign.h>
  10. int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b)
  11. {
  12. if (a->objectid > b->objectid)
  13. return 1;
  14. if (a->objectid < b->objectid)
  15. return -1;
  16. if (a->type > b->type)
  17. return 1;
  18. if (a->type < b->type)
  19. return -1;
  20. if (a->offset > b->offset)
  21. return 1;
  22. if (a->offset < b->offset)
  23. return -1;
  24. return 0;
  25. }
  26. int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
  27. {
  28. if (a->objectid > b->objectid)
  29. return 1;
  30. if (a->objectid < b->objectid)
  31. return -1;
  32. if (a->type > b->type)
  33. return 1;
  34. if (a->type < b->type)
  35. return -1;
  36. return 0;
  37. }
  38. static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
  39. int max, int *slot)
  40. {
  41. int low = 0, high = max, mid, ret;
  42. struct btrfs_key *tmp;
  43. while (low < high) {
  44. mid = (low + high) / 2;
  45. tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
  46. ret = btrfs_comp_keys(tmp, key);
  47. if (ret < 0) {
  48. low = mid + 1;
  49. } else if (ret > 0) {
  50. high = mid;
  51. } else {
  52. *slot = mid;
  53. return 0;
  54. }
  55. }
  56. *slot = low;
  57. return 1;
  58. }
  59. int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
  60. int *slot)
  61. {
  62. void *addr;
  63. unsigned long size;
  64. if (p->header.level) {
  65. addr = p->node.ptrs;
  66. size = sizeof(struct btrfs_key_ptr);
  67. } else {
  68. addr = p->leaf.items;
  69. size = sizeof(struct btrfs_item);
  70. }
  71. return generic_bin_search(addr, size, key, p->header.nritems, slot);
  72. }
  73. static void clear_path(struct btrfs_path *p)
  74. {
  75. int i;
  76. for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
  77. p->nodes[i] = NULL;
  78. p->slots[i] = 0;
  79. }
  80. }
  81. void btrfs_free_path(struct btrfs_path *p)
  82. {
  83. int i;
  84. for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
  85. if (p->nodes[i])
  86. free(p->nodes[i]);
  87. }
  88. clear_path(p);
  89. }
  90. static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
  91. {
  92. ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr,
  93. sizeof(struct btrfs_header));
  94. unsigned long size, offset = sizeof(*hdr);
  95. union btrfs_tree_node *res;
  96. u32 i;
  97. if (!btrfs_devread(physical, sizeof(*hdr), hdr))
  98. return -1;
  99. btrfs_header_to_cpu(hdr);
  100. if (hdr->level)
  101. size = sizeof(struct btrfs_node)
  102. + hdr->nritems * sizeof(struct btrfs_key_ptr);
  103. else
  104. size = btrfs_info.sb.nodesize;
  105. res = malloc_cache_aligned(size);
  106. if (!res) {
  107. debug("%s: malloc failed\n", __func__);
  108. return -1;
  109. }
  110. if (!btrfs_devread(physical + offset, size - offset,
  111. ((u8 *) res) + offset)) {
  112. free(res);
  113. return -1;
  114. }
  115. memcpy(&res->header, hdr, sizeof(*hdr));
  116. if (hdr->level)
  117. for (i = 0; i < hdr->nritems; ++i)
  118. btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
  119. else
  120. for (i = 0; i < hdr->nritems; ++i)
  121. btrfs_item_to_cpu(&res->leaf.items[i]);
  122. *buf = res;
  123. return 0;
  124. }
  125. int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
  126. struct btrfs_path *p)
  127. {
  128. u8 lvl, prev_lvl;
  129. int i, slot, ret;
  130. u64 logical, physical;
  131. union btrfs_tree_node *buf;
  132. clear_path(p);
  133. logical = root->bytenr;
  134. for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
  135. physical = btrfs_map_logical_to_physical(logical);
  136. if (physical == -1ULL)
  137. goto err;
  138. if (read_tree_node(physical, &buf))
  139. goto err;
  140. lvl = buf->header.level;
  141. if (i && prev_lvl != lvl + 1) {
  142. printf("%s: invalid level in header at %llu\n",
  143. __func__, logical);
  144. goto err;
  145. }
  146. prev_lvl = lvl;
  147. ret = btrfs_bin_search(buf, key, &slot);
  148. if (ret < 0)
  149. goto err;
  150. if (ret && slot > 0 && lvl)
  151. slot -= 1;
  152. p->slots[lvl] = slot;
  153. p->nodes[lvl] = buf;
  154. if (lvl) {
  155. logical = buf->node.ptrs[slot].blockptr;
  156. } else {
  157. /*
  158. * The path might be invalid if:
  159. * cur leaf max < searched value < next leaf min
  160. *
  161. * Jump to the next valid element if it exists.
  162. */
  163. if (slot >= buf->header.nritems)
  164. if (btrfs_next_slot(p) < 0)
  165. goto err;
  166. break;
  167. }
  168. }
  169. return 0;
  170. err:
  171. btrfs_free_path(p);
  172. return -1;
  173. }
  174. static int jump_leaf(struct btrfs_path *path, int dir)
  175. {
  176. struct btrfs_path p;
  177. u32 slot;
  178. int level = 1, from_level, i;
  179. dir = dir >= 0 ? 1 : -1;
  180. p = *path;
  181. while (level < BTRFS_MAX_LEVEL) {
  182. if (!p.nodes[level])
  183. return 1;
  184. slot = p.slots[level];
  185. if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
  186. || (dir < 0 && !slot))
  187. level++;
  188. else
  189. break;
  190. }
  191. if (level == BTRFS_MAX_LEVEL)
  192. return 1;
  193. p.slots[level] = slot + dir;
  194. level--;
  195. from_level = level;
  196. while (level >= 0) {
  197. u64 logical, physical;
  198. slot = p.slots[level + 1];
  199. logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
  200. physical = btrfs_map_logical_to_physical(logical);
  201. if (physical == -1ULL)
  202. goto err;
  203. if (read_tree_node(physical, &p.nodes[level]))
  204. goto err;
  205. if (dir > 0)
  206. p.slots[level] = 0;
  207. else
  208. p.slots[level] = p.nodes[level]->header.nritems - 1;
  209. level--;
  210. }
  211. /* Free rewritten nodes in path */
  212. for (i = 0; i <= from_level; ++i)
  213. free(path->nodes[i]);
  214. *path = p;
  215. return 0;
  216. err:
  217. /* Free rewritten nodes in p */
  218. for (i = level + 1; i <= from_level; ++i)
  219. free(p.nodes[i]);
  220. return -1;
  221. }
  222. int btrfs_prev_slot(struct btrfs_path *p)
  223. {
  224. if (!p->slots[0])
  225. return jump_leaf(p, -1);
  226. p->slots[0]--;
  227. return 0;
  228. }
  229. int btrfs_next_slot(struct btrfs_path *p)
  230. {
  231. struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
  232. if (p->slots[0] + 1 >= leaf->header.nritems)
  233. return jump_leaf(p, 1);
  234. p->slots[0]++;
  235. return 0;
  236. }