xref: /openbmc/u-boot/fs/btrfs/chunk-map.c (revision e31fb4db)
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