fs/btrfs/ctree.c

   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 }