chunk-map.c 4.0 KB

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