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