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