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