extent-tree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "kerncompat.h"
   4 #include "radix-tree.h"
   5 #include "ctree.h"
   6 #include "disk-io.h"
   7 #include "print-tree.h"
   8
   9 static int find_free_extent(struct btrfs_root *orig_root, u64 num_blocks,
  10                             u64 search_start, u64 search_end,
  11                             struct btrfs_key *ins);
  12 static int finish_current_insert(struct btrfs_root *extent_root);
  13 static int run_pending(struct btrfs_root *extent_root);
  14
  15 /*
  16  * pending extents are blocks that we're trying to allocate in the extent
  17  * map while trying to grow the map because of other allocations.  To avoid
  18  * recursing, they are tagged in the radix tree and cleaned up after
  19  * other allocations are done.  The pending tag is also used in the same
  20  * manner for deletes.
  21  */
  22 #define CTREE_EXTENT_PENDING_DEL 0
  23
  24 static int inc_block_ref(struct btrfs_root *root, u64 blocknr)
  25 {
  26         struct btrfs_path path;
  27         int ret;
  28         struct btrfs_key key;
  29         struct btrfs_leaf *l;
  30         struct btrfs_extent_item *item;
  31         struct btrfs_key ins;
  32         u32 refs;
  33
  34         find_free_extent(root->extent_root, 0, 0, (u64)-1, &ins);
  35         btrfs_init_path(&path);
  36         key.objectid = blocknr;
  37         key.flags = 0;
  38         key.offset = 1;
  39         ret = btrfs_search_slot(root->extent_root, &key, &path, 0, 1);
  40         if (ret != 0)
  41                 BUG();
  42         BUG_ON(ret != 0);
  43         l = &path.nodes[0]->leaf;
  44         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
  45         refs = btrfs_extent_refs(item);
  46         btrfs_set_extent_refs(item, refs + 1);
  47
  48         BUG_ON(list_empty(&path.nodes[0]->dirty));
  49         btrfs_release_path(root->extent_root, &path);
  50         finish_current_insert(root->extent_root);
  51         run_pending(root->extent_root);
  52         return 0;
  53 }
  54
  55 static int lookup_block_ref(struct btrfs_root *root, u64 blocknr, u32 *refs)
  56 {
  57         struct btrfs_path path;
  58         int ret;
  59         struct btrfs_key key;
  60         struct btrfs_leaf *l;
  61         struct btrfs_extent_item *item;
  62         btrfs_init_path(&path);
  63         key.objectid = blocknr;
  64         key.flags = 0;
  65         key.offset = 1;
  66         ret = btrfs_search_slot(root->extent_root, &key, &path, 0, 0);
  67         if (ret != 0)
  68                 BUG();
  69         l = &path.nodes[0]->leaf;
  70         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
  71         *refs = btrfs_extent_refs(item);
  72         btrfs_release_path(root->extent_root, &path);
  73         return 0;
  74 }
  75
  76 int btrfs_inc_ref(struct btrfs_root *root, struct btrfs_buffer *buf)
  77 {
  78         u64 blocknr;
  79         int i;
  80
  81         if (!root->ref_cows)
  82                 return 0;
  83         if (btrfs_is_leaf(&buf->node))
  84                 return 0;
  85
  86         for (i = 0; i < btrfs_header_nritems(&buf->node.header); i++) {
  87                 blocknr = btrfs_node_blockptr(&buf->node, i);
  88                 inc_block_ref(root, blocknr);
  89         }
  90         return 0;
  91 }
  92
  93 int btrfs_finish_extent_commit(struct btrfs_root *root)
  94 {
  95         unsigned long gang[8];
  96         int ret;
  97         int i;
  98
  99         while(1) {
 100                 ret = radix_tree_gang_lookup(&root->pinned_radix,
 101                                                  (void **)gang, 0,
 102                                                  ARRAY_SIZE(gang));
 103                 if (!ret)
 104                         break;
 105                 for (i = 0; i < ret; i++) {
 106                         radix_tree_delete(&root->pinned_radix, gang[i]);
 107                 }
 108         }
 109         root->last_insert.objectid = 0;
 110         root->last_insert.offset = 0;
 111         return 0;
 112 }
 113
 114 static int finish_current_insert(struct btrfs_root *extent_root)
 115 {
 116         struct btrfs_key ins;
 117         struct btrfs_extent_item extent_item;
 118         int i;
 119         int ret;
 120
 121         btrfs_set_extent_refs(&extent_item, 1);
 122         btrfs_set_extent_owner(&extent_item,
 123                 btrfs_header_parentid(&extent_root->node->node.header));
 124         ins.offset = 1;
 125         ins.flags = 0;
 126
 127         for (i = 0; i < extent_root->current_insert.flags; i++) {
 128                 ins.objectid = extent_root->current_insert.objectid + i;
 129                 ret = btrfs_insert_item(extent_root, &ins, &extent_item,
 130                                   sizeof(extent_item));
 131                 BUG_ON(ret);
 132         }
 133         extent_root->current_insert.offset = 0;
 134         return 0;
 135 }
 136
 137 /*
 138  * remove an extent from the root, returns 0 on success
 139  */
 140 static int __free_extent(struct btrfs_root *root, u64 blocknr, u64 num_blocks)
 141 {
 142         struct btrfs_path path;
 143         struct btrfs_key key;
 144         struct btrfs_root *extent_root = root->extent_root;
 145         int ret;
 146         struct btrfs_item *item;
 147         struct btrfs_extent_item *ei;
 148         struct btrfs_key ins;
 149         u32 refs;
 150
 151         key.objectid = blocknr;
 152         key.flags = 0;
 153         key.offset = num_blocks;
 154
 155         find_free_extent(root, 0, 0, (u64)-1, &ins);
 156         btrfs_init_path(&path);
 157         ret = btrfs_search_slot(extent_root, &key, &path, -1, 1);
 158         if (ret) {
 159                 printf("failed to find %Lu\n", key.objectid);
 160                 btrfs_print_tree(extent_root, extent_root->node);
 161                 printf("failed to find %Lu\n", key.objectid);
 162                 BUG();
 163         }
 164         item = path.nodes[0]->leaf.items + path.slots[0];
 165         ei = (struct btrfs_extent_item *)(path.nodes[0]->leaf.data +
 166                                     btrfs_item_offset(item));
 167         BUG_ON(ei->refs == 0);
 168         refs = btrfs_extent_refs(ei) - 1;
 169         btrfs_set_extent_refs(ei, refs);
 170         if (refs == 0) {
 171                 if (!root->ref_cows) {
 172                         int err;
 173                         radix_tree_preload(GFP_KERNEL);
 174                         err = radix_tree_insert(&extent_root->pinned_radix,
 175                                           blocknr, (void *)blocknr);
 176                         BUG_ON(err);
 177                         radix_tree_preload_end();
 178                 }
 179                 ret = btrfs_del_item(extent_root, &path);
 180                 if (root != extent_root &&
 181                     extent_root->last_insert.objectid > blocknr)
 182                         extent_root->last_insert.objectid = blocknr;
 183                 if (ret)
 184                         BUG();
 185         }
 186         btrfs_release_path(extent_root, &path);
 187         finish_current_insert(extent_root);
 188         return ret;
 189 }
 190
 191 /*
 192  * find all the blocks marked as pending in the radix tree and remove
 193  * them from the extent map
 194  */
 195 static int del_pending_extents(struct btrfs_root *extent_root)
 196 {
 197         int ret;
 198         struct btrfs_buffer *gang[4];
 199         int i;
 200
 201         while(1) {
 202                 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
 203                                                  (void **)gang, 0,
 204                                                  ARRAY_SIZE(gang),
 205                                                  CTREE_EXTENT_PENDING_DEL);
 206                 if (!ret)
 207                         break;
 208                 for (i = 0; i < ret; i++) {
 209                         ret = __free_extent(extent_root, gang[i]->blocknr, 1);
 210                         radix_tree_tag_clear(&extent_root->cache_radix,
 211                                                 gang[i]->blocknr,
 212                                                 CTREE_EXTENT_PENDING_DEL);
 213                         btrfs_block_release(extent_root, gang[i]);
 214                 }
 215         }
 216         return 0;
 217 }
 218
 219 static int run_pending(struct btrfs_root *extent_root)
 220 {
 221         while(radix_tree_tagged(&extent_root->cache_radix,
 222                                 CTREE_EXTENT_PENDING_DEL))
 223                 del_pending_extents(extent_root);
 224         return 0;
 225 }
 226
 227
 228 /*
 229  * remove an extent from the root, returns 0 on success
 230  */
 231 int btrfs_free_extent(struct btrfs_root *root, u64 blocknr, u64 num_blocks)
 232 {
 233         struct btrfs_key key;
 234         struct btrfs_root *extent_root = root->extent_root;
 235         struct btrfs_buffer *t;
 236         int pending_ret;
 237         int ret;
 238
 239         if (root == extent_root) {
 240                 t = find_tree_block(root, blocknr);
 241                 radix_tree_tag_set(&root->cache_radix, blocknr,
 242                                    CTREE_EXTENT_PENDING_DEL);
 243                 return 0;
 244         }
 245         key.objectid = blocknr;
 246         key.flags = 0;
 247         key.offset = num_blocks;
 248         ret = __free_extent(root, blocknr, num_blocks);
 249         pending_ret = run_pending(root->extent_root);
 250         return ret ? ret : pending_ret;
 251 }
 252
 253 /*
 254  * walks the btree of allocated extents and find a hole of a given size.
 255  * The key ins is changed to record the hole:
 256  * ins->objectid == block start
 257  * ins->flags = 0
 258  * ins->offset == number of blocks
 259  * Any available blocks before search_start are skipped.
 260  */
 261 static int find_free_extent(struct btrfs_root *orig_root, u64 num_blocks,
 262                             u64 search_start, u64 search_end,
 263                             struct btrfs_key *ins)
 264 {
 265         struct btrfs_path path;
 266         struct btrfs_key key;
 267         int ret;
 268         u64 hole_size = 0;
 269         int slot = 0;
 270         u64 last_block;
 271         u64 test_block;
 272         int start_found;
 273         struct btrfs_leaf *l;
 274         struct btrfs_root * root = orig_root->extent_root;
 275         int total_needed = num_blocks;
 276
 277         total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
 278         if (root->last_insert.objectid > search_start)
 279                 search_start = root->last_insert.objectid;
 280 check_failed:
 281         btrfs_init_path(&path);
 282         ins->objectid = search_start;
 283         ins->offset = 0;
 284         ins->flags = 0;
 285         start_found = 0;
 286         ret = btrfs_search_slot(root, ins, &path, 0, 0);
 287         if (ret < 0)
 288                 goto error;
 289
 290         if (path.slots[0] > 0)
 291                 path.slots[0]--;
 292
 293         while (1) {
 294                 l = &path.nodes[0]->leaf;
 295                 slot = path.slots[0];
 296                 if (slot >= btrfs_header_nritems(&l->header)) {
 297                         ret = btrfs_next_leaf(root, &path);
 298                         if (ret == 0)
 299                                 continue;
 300                         if (ret < 0)
 301                                 goto error;
 302                         if (!start_found) {
 303                                 ins->objectid = search_start;
 304                                 ins->offset = (u64)-1;
 305                                 start_found = 1;
 306                                 goto check_pending;
 307                         }
 308                         ins->objectid = last_block > search_start ?
 309                                         last_block : search_start;
 310                         ins->offset = (u64)-1;
 311                         goto check_pending;
 312                 }
 313                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
 314                 if (key.objectid >= search_start) {
 315                         if (start_found) {
 316                                 if (last_block < search_start)
 317                                         last_block = search_start;
 318                                 hole_size = key.objectid - last_block;
 319                                 if (hole_size > total_needed) {
 320                                         ins->objectid = last_block;
 321                                         ins->offset = hole_size;
 322                                         goto check_pending;
 323                                 }
 324                         }
 325                 }
 326                 start_found = 1;
 327                 last_block = key.objectid + key.offset;
 328                 path.slots[0]++;
 329         }
 330         // FIXME -ENOSPC
 331 check_pending:
 332         /* we have to make sure we didn't find an extent that has already
 333          * been allocated by the map tree or the original allocation
 334          */
 335         btrfs_release_path(root, &path);
 336         BUG_ON(ins->objectid < search_start);
 337         for (test_block = ins->objectid;
 338              test_block < ins->objectid + total_needed; test_block++) {
 339                 if (radix_tree_lookup(&root->pinned_radix, test_block)) {
 340                         search_start = test_block + 1;
 341                         goto check_failed;
 342                 }
 343         }
 344         BUG_ON(root->current_insert.offset);
 345         root->current_insert.offset = total_needed - num_blocks;
 346         root->current_insert.objectid = ins->objectid + num_blocks;
 347         root->current_insert.flags = 0;
 348         root->last_insert.objectid = ins->objectid;
 349         ins->offset = num_blocks;
 350         return 0;
 351 error:
 352         btrfs_release_path(root, &path);
 353         return ret;
 354 }
 355
 356 /*
 357  * finds a free extent and does all the dirty work required for allocation
 358  * returns the key for the extent through ins, and a tree buffer for
 359  * the first block of the extent through buf.
 360  *
 361  * returns 0 if everything worked, non-zero otherwise.
 362  */
 363 static int alloc_extent(struct btrfs_root *root, u64 num_blocks,
 364                         u64 search_start, u64 search_end, u64 owner,
 365                         struct btrfs_key *ins)
 366 {
 367         int ret;
 368         int pending_ret;
 369         struct btrfs_root *extent_root = root->extent_root;
 370         struct btrfs_extent_item extent_item;
 371
 372         btrfs_set_extent_refs(&extent_item, 1);
 373         btrfs_set_extent_owner(&extent_item, owner);
 374
 375         if (root == extent_root) {
 376                 BUG_ON(extent_root->current_insert.offset == 0);
 377                 BUG_ON(num_blocks != 1);
 378                 BUG_ON(extent_root->current_insert.flags ==
 379                        extent_root->current_insert.offset);
 380                 ins->offset = 1;
 381                 ins->objectid = extent_root->current_insert.objectid +
 382                                 extent_root->current_insert.flags++;
 383                 return 0;
 384         }
 385         ret = find_free_extent(root, num_blocks, search_start,
 386                                search_end, ins);
 387         if (ret)
 388                 return ret;
 389
 390         ret = btrfs_insert_item(extent_root, ins, &extent_item,
 391                           sizeof(extent_item));
 392
 393         finish_current_insert(extent_root);
 394         pending_ret = run_pending(extent_root);
 395         if (ret)
 396                 return ret;
 397         if (pending_ret)
 398                 return pending_ret;
 399         return 0;
 400 }
 401
 402 /*
 403  * helper function to allocate a block for a given tree
 404  * returns the tree buffer or NULL.
 405  */
 406 struct btrfs_buffer *btrfs_alloc_free_block(struct btrfs_root *root)
 407 {
 408         struct btrfs_key ins;
 409         int ret;
 410         struct btrfs_buffer *buf;
 411
 412         ret = alloc_extent(root, 1, 0, (unsigned long)-1,
 413                            btrfs_header_parentid(&root->node->node.header),
 414                            &ins);
 415         if (ret) {
 416                 BUG();
 417                 return NULL;
 418         }
 419         buf = find_tree_block(root, ins.objectid);
 420         dirty_tree_block(root, buf);
 421         return buf;
 422 }
 423
 424 /*
 425  * helper function for drop_snapshot, this walks down the tree dropping ref
 426  * counts as it goes.
 427  */
 428 static int walk_down_tree(struct btrfs_root *root,
 429                           struct btrfs_path *path, int *level)
 430 {
 431         struct btrfs_buffer *next;
 432         struct btrfs_buffer *cur;
 433         u64 blocknr;
 434         int ret;
 435         u32 refs;
 436
 437         ret = lookup_block_ref(root, path->nodes[*level]->blocknr, &refs);
 438         BUG_ON(ret);
 439         if (refs > 1)
 440                 goto out;
 441         /*
 442          * walk down to the last node level and free all the leaves
 443          */
 444         while(*level > 0) {
 445                 cur = path->nodes[*level];
 446                 if (path->slots[*level] >=
 447                     btrfs_header_nritems(&cur->node.header))
 448                         break;
 449                 blocknr = btrfs_node_blockptr(&cur->node, path->slots[*level]);
 450                 ret = lookup_block_ref(root, blocknr, &refs);
 451                 if (refs != 1 || *level == 1) {
 452                         path->slots[*level]++;
 453                         ret = btrfs_free_extent(root, blocknr, 1);
 454                         BUG_ON(ret);
 455                         continue;
 456                 }
 457                 BUG_ON(ret);
 458                 next = read_tree_block(root, blocknr);
 459                 if (path->nodes[*level-1])
 460                         btrfs_block_release(root, path->nodes[*level-1]);
 461                 path->nodes[*level-1] = next;
 462                 *level = btrfs_header_level(&next->node.header);
 463                 path->slots[*level] = 0;
 464         }
 465 out:
 466         ret = btrfs_free_extent(root, path->nodes[*level]->blocknr, 1);
 467         btrfs_block_release(root, path->nodes[*level]);
 468         path->nodes[*level] = NULL;
 469         *level += 1;
 470         BUG_ON(ret);
 471         return 0;
 472 }
 473
 474 /*
 475  * helper for dropping snapshots.  This walks back up the tree in the path
 476  * to find the first node higher up where we haven't yet gone through
 477  * all the slots
 478  */
 479 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
 480                         int *level)
 481 {
 482         int i;
 483         int slot;
 484         int ret;
 485         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 486                 slot = path->slots[i];
 487                 if (slot <
 488                     btrfs_header_nritems(&path->nodes[i]->node.header)- 1) {
 489                         path->slots[i]++;
 490                         *level = i;
 491                         return 0;
 492                 } else {
 493                         ret = btrfs_free_extent(root,
 494                                           path->nodes[*level]->blocknr, 1);
 495                         btrfs_block_release(root, path->nodes[*level]);
 496                         path->nodes[*level] = NULL;
 497                         *level = i + 1;
 498                         BUG_ON(ret);
 499                 }
 500         }
 501         return 1;
 502 }
 503
 504 /*
 505  * drop the reference count on the tree rooted at 'snap'.  This traverses
 506  * the tree freeing any blocks that have a ref count of zero after being
 507  * decremented.
 508  */
 509 int btrfs_drop_snapshot(struct btrfs_root *root, struct btrfs_buffer *snap)
 510 {
 511         int ret = 0;
 512         int wret;
 513         int level;
 514         struct btrfs_path path;
 515         int i;
 516         int orig_level;
 517
 518         btrfs_init_path(&path);
 519
 520         level = btrfs_header_level(&snap->node.header);
 521         orig_level = level;
 522         path.nodes[level] = snap;
 523         path.slots[level] = 0;
 524         while(1) {
 525                 wret = walk_down_tree(root, &path, &level);
 526                 if (wret > 0)
 527                         break;
 528                 if (wret < 0)
 529                         ret = wret;
 530
 531                 wret = walk_up_tree(root, &path, &level);
 532                 if (wret > 0)
 533                         break;
 534                 if (wret < 0)
 535                         ret = wret;
 536         }
 537         for (i = 0; i <= orig_level; i++) {
 538                 if (path.nodes[i]) {
 539                         btrfs_block_release(root, path.nodes[i]);
 540                 }
 541         }
 542         return ret;
 543 }