Home | History | Annotate | Download | only in btrfs 
      1 // SPDX-License-Identifier: GPL-2.0+
      2 /*
      3  * BTRFS filesystem implementation for U-Boot
      4  *
      5  * 2017 Marek Behun, CZ.NIC, marek.behun (at) 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