fs/btrfs/ctree.c

   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 }