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 #include <memalign.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 ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr, 110 sizeof(struct btrfs_header)); 111 unsigned long size, offset = sizeof(*hdr); 112 union btrfs_tree_node *res; 113 u32 i; 114 115 if (!btrfs_devread(physical, sizeof(*hdr), hdr)) 116 return -1; 117 118 btrfs_header_to_cpu(hdr); 119 120 if (hdr->level) 121 size = sizeof(struct btrfs_node) 122 + hdr->nritems * sizeof(struct btrfs_key_ptr); 123 else 124 size = btrfs_info.sb.nodesize; 125 126 res = malloc_cache_aligned(size); 127 if (!res) { 128 debug("%s: malloc failed\n", __func__); 129 return -1; 130 } 131 132 if (!btrfs_devread(physical + offset, size - offset, 133 ((u8 *) res) + offset)) { 134 free(res); 135 return -1; 136 } 137 138 memcpy(&res->header, hdr, sizeof(*hdr)); 139 if (hdr->level) 140 for (i = 0; i < hdr->nritems; ++i) 141 btrfs_key_ptr_to_cpu(&res->node.ptrs[i]); 142 else 143 for (i = 0; i < hdr->nritems; ++i) 144 btrfs_item_to_cpu(&res->leaf.items[i]); 145 146 *buf = res; 147 148 return 0; 149 } 150 151 int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key, 152 struct btrfs_path *p) 153 { 154 u8 lvl, prev_lvl; 155 int i, slot, ret; 156 u64 logical, physical; 157 union btrfs_tree_node *buf; 158 159 clear_path(p); 160 161 logical = root->bytenr; 162 163 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) { 164 physical = btrfs_map_logical_to_physical(logical); 165 if (physical == -1ULL) 166 goto err; 167 168 if (read_tree_node(physical, &buf)) 169 goto err; 170 171 lvl = buf->header.level; 172 if (i && prev_lvl != lvl + 1) { 173 printf("%s: invalid level in header at %llu\n", 174 __func__, logical); 175 goto err; 176 } 177 prev_lvl = lvl; 178 179 ret = btrfs_bin_search(buf, key, &slot); 180 if (ret < 0) 181 goto err; 182 if (ret && slot > 0 && lvl) 183 slot -= 1; 184 185 p->slots[lvl] = slot; 186 p->nodes[lvl] = buf; 187 188 if (lvl) 189 logical = buf->node.ptrs[slot].blockptr; 190 else 191 break; 192 } 193 194 return 0; 195 err: 196 btrfs_free_path(p); 197 return -1; 198 } 199 200 static int jump_leaf(struct btrfs_path *path, int dir) 201 { 202 struct btrfs_path p; 203 u32 slot; 204 int level = 1, from_level, i; 205 206 dir = dir >= 0 ? 1 : -1; 207 208 p = *path; 209 210 while (level < BTRFS_MAX_LEVEL) { 211 if (!p.nodes[level]) 212 return 1; 213 214 slot = p.slots[level]; 215 if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems) 216 || (dir < 0 && !slot)) 217 level++; 218 else 219 break; 220 } 221 222 if (level == BTRFS_MAX_LEVEL) 223 return 1; 224 225 p.slots[level] = slot + dir; 226 level--; 227 from_level = level; 228 229 while (level >= 0) { 230 u64 logical, physical; 231 232 slot = p.slots[level + 1]; 233 logical = p.nodes[level + 1]->node.ptrs[slot].blockptr; 234 physical = btrfs_map_logical_to_physical(logical); 235 if (physical == -1ULL) 236 goto err; 237 238 if (read_tree_node(physical, &p.nodes[level])) 239 goto err; 240 241 if (dir > 0) 242 p.slots[level] = 0; 243 else 244 p.slots[level] = p.nodes[level]->header.nritems - 1; 245 level--; 246 } 247 248 /* Free rewritten nodes in path */ 249 for (i = 0; i <= from_level; ++i) 250 free(path->nodes[i]); 251 252 *path = p; 253 return 0; 254 255 err: 256 /* Free rewritten nodes in p */ 257 for (i = level + 1; i <= from_level; ++i) 258 free(p.nodes[i]); 259 return -1; 260 } 261 262 int btrfs_prev_slot(struct btrfs_path *p) 263 { 264 if (!p->slots[0]) 265 return jump_leaf(p, -1); 266 267 p->slots[0]--; 268 return 0; 269 } 270 271 int btrfs_next_slot(struct btrfs_path *p) 272 { 273 struct btrfs_leaf *leaf = &p->nodes[0]->leaf; 274 275 if (p->slots[0] + 1 >= leaf->header.nritems) 276 return jump_leaf(p, 1); 277 278 p->slots[0]++; 279 return 0; 280 } 281