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