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