]> git.sur5r.net Git - u-boot/blob - fs/btrfs/chunk-map.c
Merge branch 'master' of git://git.denx.de/u-boot-usb
[u-boot] / 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 }