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 int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b) 13 { 14 if (a->objectid > b->objectid) 15 return 1; 16 if (a->objectid < b->objectid) 17 return -1; 18 if (a->type > b->type) 19 return 1; 20 if (a->type < b->type) 21 return -1; 22 if (a->offset > b->offset) 23 return 1; 24 if (a->offset < b->offset) 25 return -1; 26 return 0; 27 } 28 29 int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b) 30 { 31 if (a->objectid > b->objectid) 32 return 1; 33 if (a->objectid < b->objectid) 34 return -1; 35 if (a->type > b->type) 36 return 1; 37 if (a->type < b->type) 38 return -1; 39 return 0; 40 } 41 42 static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key, 43 int max, int *slot) 44 { 45 int low = 0, high = max, mid, ret; 46 struct btrfs_key *tmp; 47 48 while (low < high) { 49 mid = (low + high) / 2; 50 51 tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size); 52 ret = btrfs_comp_keys(tmp, key); 53 54 if (ret < 0) { 55 low = mid + 1; 56 } else if (ret > 0) { 57 high = mid; 58 } else { 59 *slot = mid; 60 return 0; 61 } 62 } 63 64 *slot = low; 65 return 1; 66 } 67 68 int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key, 69 int *slot) 70 { 71 void *addr; 72 unsigned long size; 73 74 if (p->header.level) { 75 addr = p->node.ptrs; 76 size = sizeof(struct btrfs_key_ptr); 77 } else { 78 addr = p->leaf.items; 79 size = sizeof(struct btrfs_item); 80 } 81 82 return generic_bin_search(addr, size, key, p->header.nritems, slot); 83 } 84 85 static void clear_path(struct btrfs_path *p) 86 { 87 int i; 88 89 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) { 90 p->nodes[i] = NULL; 91 p->slots[i] = 0; 92 } 93 } 94 95 void btrfs_free_path(struct btrfs_path *p) 96 { 97 int i; 98 99 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) { 100 if (p->nodes[i]) 101 free(p->nodes[i]); 102 } 103 104 clear_path(p); 105 } 106 107 static int read_tree_node(u64 physical, union btrfs_tree_node **buf) 108 { 109 struct btrfs_header hdr; 110 unsigned long size, offset = sizeof(hdr); 111 union btrfs_tree_node *res; 112 u32 i; 113 114 if (!btrfs_devread(physical, sizeof(hdr), &hdr)) 115 return -1; 116 117 btrfs_header_to_cpu(&hdr); 118 119 if (hdr.level) 120 size = sizeof(struct btrfs_node) 121 + hdr.nritems * sizeof(struct btrfs_key_ptr); 122 else 123 size = btrfs_info.sb.nodesize; 124 125 res = malloc(size); 126 if (!res) { 127 debug("%s: malloc failed\n", __func__); 128 return -1; 129 } 130 131 if (!btrfs_devread(physical + offset, size - offset, 132 ((u8 *) res) + offset)) { 133 free(res); 134 return -1; 135 } 136 137 res->header = hdr; 138 if (hdr.level) 139 for (i = 0; i < hdr.nritems; ++i) 140 btrfs_key_ptr_to_cpu(&res->node.ptrs[i]); 141 else 142 for (i = 0; i < hdr.nritems; ++i) 143 btrfs_item_to_cpu(&res->leaf.items[i]); 144 145 *buf = res; 146 147 return 0; 148 } 149 150 int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key, 151 struct btrfs_path *p) 152 { 153 u8 lvl, prev_lvl; 154 int i, slot, ret; 155 u64 logical, physical; 156 union btrfs_tree_node *buf; 157 158 clear_path(p); 159 160 logical = root->bytenr; 161 162 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) { 163 physical = btrfs_map_logical_to_physical(logical); 164 if (physical == -1ULL) 165 goto err; 166 167 if (read_tree_node(physical, &buf)) 168 goto err; 169 170 lvl = buf->header.level; 171 if (i && prev_lvl != lvl + 1) { 172 printf("%s: invalid level in header at %llu\n", 173 __func__, logical); 174 goto err; 175 } 176 prev_lvl = lvl; 177 178 ret = btrfs_bin_search(buf, key, &slot); 179 if (ret < 0) 180 goto err; 181 if (ret && slot > 0 && lvl) 182 slot -= 1; 183 184 p->slots[lvl] = slot; 185 p->nodes[lvl] = buf; 186 187 if (lvl) 188 logical = buf->node.ptrs[slot].blockptr; 189 else 190 break; 191 } 192 193 return 0; 194 err: 195 btrfs_free_path(p); 196 return -1; 197 } 198 199 static int jump_leaf(struct btrfs_path *path, int dir) 200 { 201 struct btrfs_path p; 202 u32 slot; 203 int level = 1, from_level, i; 204 205 dir = dir >= 0 ? 1 : -1; 206 207 p = *path; 208 209 while (level < BTRFS_MAX_LEVEL) { 210 if (!p.nodes[level]) 211 return 1; 212 213 slot = p.slots[level]; 214 if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems) 215 || (dir < 0 && !slot)) 216 level++; 217 else 218 break; 219 } 220 221 if (level == BTRFS_MAX_LEVEL) 222 return 1; 223 224 p.slots[level] = slot + dir; 225 level--; 226 from_level = level; 227 228 while (level >= 0) { 229 u64 logical, physical; 230 231 slot = p.slots[level + 1]; 232 logical = p.nodes[level + 1]->node.ptrs[slot].blockptr; 233 physical = btrfs_map_logical_to_physical(logical); 234 if (physical == -1ULL) 235 goto err; 236 237 if (read_tree_node(physical, &p.nodes[level])) 238 goto err; 239 240 if (dir > 0) 241 p.slots[level] = 0; 242 else 243 p.slots[level] = p.nodes[level]->header.nritems - 1; 244 level--; 245 } 246 247 /* Free rewritten nodes in path */ 248 for (i = 0; i <= from_level; ++i) 249 free(path->nodes[i]); 250 251 *path = p; 252 return 0; 253 254 err: 255 /* Free rewritten nodes in p */ 256 for (i = level + 1; i <= from_level; ++i) 257 free(p.nodes[i]); 258 return -1; 259 } 260 261 int btrfs_prev_slot(struct btrfs_path *p) 262 { 263 if (!p->slots[0]) 264 return jump_leaf(p, -1); 265 266 p->slots[0]--; 267 return 0; 268 } 269 270 int btrfs_next_slot(struct btrfs_path *p) 271 { 272 struct btrfs_leaf *leaf = &p->nodes[0]->leaf; 273 274 if (p->slots[0] >= leaf->header.nritems) 275 return jump_leaf(p, 1); 276 277 p->slots[0]++; 278 return 0; 279 } 280