fs/btrfs/chunk-map.c

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