fs/btrfs/extent-tree.c

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