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