fs/btrfs/extent-tree.c

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