chunk-map.c 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
  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. struct chunk_map_item {
  10. struct rb_node node;
  11. u64 logical;
  12. u64 length;
  13. u64 physical;
  14. };
  15. static int add_chunk_mapping(struct btrfs_key *key, struct btrfs_chunk *chunk)
  16. {
  17. struct btrfs_stripe *stripe;
  18. u64 block_profile = chunk->type & BTRFS_BLOCK_GROUP_PROFILE_MASK;
  19. struct rb_node **new = &(btrfs_info.chunks_root.rb_node), *prnt = NULL;
  20. struct chunk_map_item *map_item;
  21. if (block_profile && block_profile != BTRFS_BLOCK_GROUP_DUP) {
  22. printf("%s: unsupported chunk profile %llu\n", __func__,
  23. block_profile);
  24. return -1;
  25. } else if (!chunk->length) {
  26. printf("%s: zero length chunk\n", __func__);
  27. return -1;
  28. }
  29. stripe = &chunk->stripe;
  30. btrfs_stripe_to_cpu(stripe);
  31. while (*new) {
  32. struct chunk_map_item *this;
  33. this = rb_entry(*new, struct chunk_map_item, node);
  34. prnt = *new;
  35. if (key->offset < this->logical) {
  36. new = &((*new)->rb_left);
  37. } else if (key->offset > this->logical) {
  38. new = &((*new)->rb_right);
  39. } else {
  40. debug("%s: Logical address %llu already in map!\n",
  41. __func__, key->offset);
  42. return 0;
  43. }
  44. }
  45. map_item = malloc(sizeof(struct chunk_map_item));
  46. if (!map_item)
  47. return -1;
  48. map_item->logical = key->offset;
  49. map_item->length = chunk->length;
  50. map_item->physical = le64_to_cpu(chunk->stripe.offset);
  51. rb_link_node(&map_item->node, prnt, new);
  52. rb_insert_color(&map_item->node, &btrfs_info.chunks_root);
  53. debug("%s: Mapping %llu to %llu\n", __func__, map_item->logical,
  54. map_item->physical);
  55. return 0;
  56. }
  57. u64 btrfs_map_logical_to_physical(u64 logical)
  58. {
  59. struct rb_node *node = btrfs_info.chunks_root.rb_node;
  60. while (node) {
  61. struct chunk_map_item *item;
  62. item = rb_entry(node, struct chunk_map_item, node);
  63. if (item->logical > logical)
  64. node = node->rb_left;
  65. else if (logical >= item->logical + item->length)
  66. node = node->rb_right;
  67. else
  68. return item->physical + logical - item->logical;
  69. }
  70. printf("%s: Cannot map logical address %llu to physical\n", __func__,
  71. logical);
  72. return -1ULL;
  73. }
  74. void btrfs_chunk_map_exit(void)
  75. {
  76. struct rb_node *now, *next;
  77. struct chunk_map_item *item;
  78. for (now = rb_first_postorder(&btrfs_info.chunks_root); now; now = next)
  79. {
  80. item = rb_entry(now, struct chunk_map_item, node);
  81. next = rb_next_postorder(now);
  82. free(item);
  83. }
  84. }
  85. int btrfs_chunk_map_init(void)
  86. {
  87. u8 sys_chunk_array_copy[sizeof(btrfs_info.sb.sys_chunk_array)];
  88. u8 * const start = sys_chunk_array_copy;
  89. u8 * const end = start + btrfs_info.sb.sys_chunk_array_size;
  90. u8 *cur;
  91. struct btrfs_key *key;
  92. struct btrfs_chunk *chunk;
  93. btrfs_info.chunks_root = RB_ROOT;
  94. memcpy(sys_chunk_array_copy, btrfs_info.sb.sys_chunk_array,
  95. sizeof(sys_chunk_array_copy));
  96. for (cur = start; cur < end;) {
  97. key = (struct btrfs_key *) cur;
  98. cur += sizeof(struct btrfs_key);
  99. chunk = (struct btrfs_chunk *) cur;
  100. btrfs_key_to_cpu(key);
  101. btrfs_chunk_to_cpu(chunk);
  102. if (key->type != BTRFS_CHUNK_ITEM_KEY) {
  103. printf("%s: invalid key type %u\n", __func__,
  104. key->type);
  105. return -1;
  106. }
  107. if (add_chunk_mapping(key, chunk))
  108. return -1;
  109. cur += sizeof(struct btrfs_chunk);
  110. cur += sizeof(struct btrfs_stripe) * (chunk->num_stripes - 1);
  111. }
  112. return 0;
  113. }
  114. int btrfs_read_chunk_tree(void)
  115. {
  116. struct btrfs_path path;
  117. struct btrfs_key key, *found_key;
  118. struct btrfs_chunk *chunk;
  119. int res = 0;
  120. key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
  121. key.type = BTRFS_CHUNK_ITEM_KEY;
  122. key.offset = 0;
  123. if (btrfs_search_tree(&btrfs_info.chunk_root, &key, &path))
  124. return -1;
  125. do {
  126. found_key = btrfs_path_leaf_key(&path);
  127. if (btrfs_comp_keys_type(&key, found_key))
  128. continue;
  129. chunk = btrfs_path_item_ptr(&path, struct btrfs_chunk);
  130. btrfs_chunk_to_cpu(chunk);
  131. if (add_chunk_mapping(found_key, chunk)) {
  132. res = -1;
  133. break;
  134. }
  135. } while (!(res = btrfs_next_slot(&path)));
  136. btrfs_free_path(&path);
  137. if (res < 0)
  138. return -1;
  139. return 0;
  140. }