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