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