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 } 178