extent-tree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "kerncompat.h"
   4 #include "radix-tree.h"
   5 #include "ctree.h"
   6 #include "disk-io.h"
   7 #include "print-tree.h"
   8 #include "transaction.h"
   9
  10 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
  11                             *orig_root, u64 num_blocks, u64 search_start, u64
  12                             search_end, struct btrfs_key *ins);
  13 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  14                                  btrfs_root *extent_root);
  15 static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
  16                        *extent_root);
  17
  18 /*
  19  * pending extents are blocks that we're trying to allocate in the extent
  20  * map while trying to grow the map because of other allocations.  To avoid
  21  * recursing, they are tagged in the radix tree and cleaned up after
  22  * other allocations are done.  The pending tag is also used in the same
  23  * manner for deletes.
  24  */
  25 #define CTREE_EXTENT_PENDING_DEL 0
  26
  27 static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
  28                          *root, u64 blocknr)
  29 {
  30         struct btrfs_path path;
  31         int ret;
  32         struct btrfs_key key;
  33         struct btrfs_leaf *l;
  34         struct btrfs_extent_item *item;
  35         struct btrfs_key ins;
  36         u32 refs;
  37
  38         find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
  39                          &ins);
  40         btrfs_init_path(&path);
  41         key.objectid = blocknr;
  42         key.flags = 0;
  43         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  44         key.offset = 1;
  45         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
  46                                 0, 1);
  47         if (ret != 0)
  48                 BUG();
  49         BUG_ON(ret != 0);
  50         l = &path.nodes[0]->leaf;
  51         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
  52         refs = btrfs_extent_refs(item);
  53         btrfs_set_extent_refs(item, refs + 1);
  54
  55         BUG_ON(list_empty(&path.nodes[0]->dirty));
  56         btrfs_release_path(root->fs_info->extent_root, &path);
  57         finish_current_insert(trans, root->fs_info->extent_root);
  58         run_pending(trans, root->fs_info->extent_root);
  59         return 0;
  60 }
  61
  62 static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
  63                             *root, u64 blocknr, u32 *refs)
  64 {
  65         struct btrfs_path path;
  66         int ret;
  67         struct btrfs_key key;
  68         struct btrfs_leaf *l;
  69         struct btrfs_extent_item *item;
  70         btrfs_init_path(&path);
  71         key.objectid = blocknr;
  72         key.offset = 1;
  73         key.flags = 0;
  74         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  75         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
  76                                 0, 0);
  77         if (ret != 0)
  78                 BUG();
  79         l = &path.nodes[0]->leaf;
  80         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
  81         *refs = btrfs_extent_refs(item);
  82         btrfs_release_path(root->fs_info->extent_root, &path);
  83         return 0;
  84 }
  85
  86 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  87                   struct btrfs_buffer *buf)
  88 {
  89         u64 blocknr;
  90         int i;
  91
  92         if (!root->ref_cows)
  93                 return 0;
  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         unsigned long gang[8];
 108         u64 first = 0;
 109         int ret;
 110         int i;
 111
 112         while(1) {
 113                 ret = radix_tree_gang_lookup(&root->fs_info->pinned_radix,
 114                                              (void **)gang, 0,
 115                                              ARRAY_SIZE(gang));
 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_type(&extent_item, BTRFS_EXTENT_TREE);
 142         btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid);
 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 /*
 162  * remove an extent from the root, returns 0 on success
 163  */
 164 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 165                          *root, u64 blocknr, u64 num_blocks, int pin)
 166 {
 167         struct btrfs_path path;
 168         struct btrfs_key key;
 169         struct btrfs_fs_info *info = root->fs_info;
 170         struct btrfs_root *extent_root = info->extent_root;
 171         int ret;
 172         struct btrfs_extent_item *ei;
 173         struct btrfs_key ins;
 174         u32 refs;
 175
 176         BUG_ON(pin && num_blocks != 1);
 177         key.objectid = blocknr;
 178         key.flags = 0;
 179         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 180         key.offset = num_blocks;
 181
 182         find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
 183         btrfs_init_path(&path);
 184         ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1);
 185         if (ret) {
 186                 printf("failed to find %Lu\n", key.objectid);
 187                 btrfs_print_tree(extent_root, extent_root->node);
 188                 printf("failed to find %Lu\n", key.objectid);
 189                 BUG();
 190         }
 191         ei = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
 192                             struct btrfs_extent_item);
 193         BUG_ON(ei->refs == 0);
 194         refs = btrfs_extent_refs(ei) - 1;
 195         btrfs_set_extent_refs(ei, refs);
 196         if (refs == 0) {
 197                 u64 super_blocks_used;
 198                 if (pin) {
 199                         int err;
 200                         radix_tree_preload(GFP_KERNEL);
 201                         err = radix_tree_insert(&info->pinned_radix,
 202                                                 blocknr, (void *)blocknr);
 203                         BUG_ON(err);
 204                         radix_tree_preload_end();
 205                 }
 206                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 207                 btrfs_set_super_blocks_used(info->disk_super,
 208                                             super_blocks_used - num_blocks);
 209                 ret = btrfs_del_item(trans, extent_root, &path);
 210                 if (!pin && extent_root->fs_info->last_insert.objectid >
 211                     blocknr)
 212                         extent_root->fs_info->last_insert.objectid = blocknr;
 213                 if (ret)
 214                         BUG();
 215         }
 216         btrfs_release_path(extent_root, &path);
 217         finish_current_insert(trans, extent_root);
 218         return ret;
 219 }
 220
 221 /*
 222  * find all the blocks marked as pending in the radix tree and remove
 223  * them from the extent map
 224  */
 225 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 226                                btrfs_root *extent_root)
 227 {
 228         int ret;
 229         struct btrfs_buffer *gang[4];
 230         int i;
 231
 232         while(1) {
 233                 ret = radix_tree_gang_lookup_tag(
 234                                         &extent_root->fs_info->cache_radix,
 235                                         (void **)gang, 0,
 236                                         ARRAY_SIZE(gang),
 237                                         CTREE_EXTENT_PENDING_DEL);
 238                 if (!ret)
 239                         break;
 240                 for (i = 0; i < ret; i++) {
 241                         ret = __free_extent(trans, extent_root,
 242                                             gang[i]->blocknr, 1, 1);
 243                         radix_tree_tag_clear(&extent_root->fs_info->cache_radix,
 244                                              gang[i]->blocknr,
 245                                              CTREE_EXTENT_PENDING_DEL);
 246                         btrfs_block_release(extent_root, gang[i]);
 247                 }
 248         }
 249         return 0;
 250 }
 251
 252 static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
 253                        *extent_root)
 254 {
 255         while(radix_tree_tagged(&extent_root->fs_info->cache_radix,
 256                                 CTREE_EXTENT_PENDING_DEL))
 257                 del_pending_extents(trans, extent_root);
 258         return 0;
 259 }
 260
 261
 262 /*
 263  * remove an extent from the root, returns 0 on success
 264  */
 265 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 266                       *root, u64 blocknr, u64 num_blocks, int pin)
 267 {
 268         struct btrfs_root *extent_root = root->fs_info->extent_root;
 269         struct btrfs_buffer *t;
 270         int pending_ret;
 271         int ret;
 272
 273         if (root == extent_root) {
 274                 t = find_tree_block(root, blocknr);
 275                 radix_tree_tag_set(&root->fs_info->cache_radix, blocknr,
 276                                    CTREE_EXTENT_PENDING_DEL);
 277                 return 0;
 278         }
 279         ret = __free_extent(trans, root, blocknr, num_blocks, pin);
 280         pending_ret = run_pending(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;
 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
 308         total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
 309         if (root->fs_info->last_insert.objectid > search_start)
 310                 search_start = root->fs_info->last_insert.objectid;
 311
 312         ins->flags = 0;
 313         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 314
 315 check_failed:
 316         btrfs_init_path(&path);
 317         ins->objectid = search_start;
 318         ins->offset = 0;
 319         start_found = 0;
 320         ret = btrfs_search_slot(trans, root, ins, &path, 0, 0);
 321         if (ret < 0)
 322                 goto error;
 323
 324         if (path.slots[0] > 0)
 325                 path.slots[0]--;
 326
 327         while (1) {
 328                 l = &path.nodes[0]->leaf;
 329                 slot = path.slots[0];
 330                 if (slot >= btrfs_header_nritems(&l->header)) {
 331                         ret = btrfs_next_leaf(root, &path);
 332                         if (ret == 0)
 333                                 continue;
 334                         if (ret < 0)
 335                                 goto error;
 336                         if (!start_found) {
 337                                 ins->objectid = search_start;
 338                                 ins->offset = (u64)-1;
 339                                 start_found = 1;
 340                                 goto check_pending;
 341                         }
 342                         ins->objectid = last_block > search_start ?
 343                                         last_block : search_start;
 344                         ins->offset = (u64)-1;
 345                         goto check_pending;
 346                 }
 347                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
 348                 if (key.objectid >= search_start) {
 349                         if (start_found) {
 350                                 if (last_block < search_start)
 351                                         last_block = search_start;
 352                                 hole_size = key.objectid - last_block;
 353                                 if (hole_size > total_needed) {
 354                                         ins->objectid = last_block;
 355                                         ins->offset = hole_size;
 356                                         goto check_pending;
 357                                 }
 358                         }
 359                 }
 360                 start_found = 1;
 361                 last_block = key.objectid + key.offset;
 362                 path.slots[0]++;
 363         }
 364         // FIXME -ENOSPC
 365 check_pending:
 366         /* we have to make sure we didn't find an extent that has already
 367          * been allocated by the map tree or the original allocation
 368          */
 369         btrfs_release_path(root, &path);
 370         BUG_ON(ins->objectid < search_start);
 371         for (test_block = ins->objectid;
 372              test_block < ins->objectid + total_needed; test_block++) {
 373                 if (radix_tree_lookup(&root->fs_info->pinned_radix,
 374                                       test_block)) {
 375                         search_start = test_block + 1;
 376                         goto check_failed;
 377                 }
 378         }
 379         BUG_ON(root->fs_info->current_insert.offset);
 380         root->fs_info->current_insert.offset = total_needed - num_blocks;
 381         root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
 382         root->fs_info->current_insert.flags = 0;
 383         root->fs_info->last_insert.objectid = ins->objectid;
 384         ins->offset = num_blocks;
 385         return 0;
 386 error:
 387         btrfs_release_path(root, &path);
 388         return ret;
 389 }
 390
 391 /*
 392  * finds a free extent and does all the dirty work required for allocation
 393  * returns the key for the extent through ins, and a tree buffer for
 394  * the first block of the extent through buf.
 395  *
 396  * returns 0 if everything worked, non-zero otherwise.
 397  */
 398 static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 399                         *root, u64 owner, u8 type, u64 num_blocks,
 400                         u64 search_start, u64
 401                         search_end, struct btrfs_key *ins)
 402 {
 403         int ret;
 404         int pending_ret;
 405         u64 super_blocks_used;
 406         struct btrfs_fs_info *info = root->fs_info;
 407         struct btrfs_root *extent_root = info->extent_root;
 408         struct btrfs_extent_item extent_item;
 409
 410         btrfs_set_extent_refs(&extent_item, 1);
 411         btrfs_set_extent_owner(&extent_item, owner);
 412         btrfs_set_extent_type(&extent_item, type);
 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 = run_pending(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 btrfs_buffer *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 btrfs_buffer *buf;
 454
 455         ret = alloc_extent(trans, root, root->root_key.objectid,
 456                            BTRFS_EXTENT_TREE, 1, 0, (unsigned long)-1, &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         btrfs_set_header_generation(&buf->node.header,
 464                                     root->root_key.offset + 1);
 465         memcpy(buf->node.header.fsid, root->fs_info->disk_super->fsid,
 466                sizeof(buf->node.header.fsid));
 467         return buf;
 468 }
 469
 470 /*
 471  * helper function for drop_snapshot, this walks down the tree dropping ref
 472  * counts as it goes.
 473  */
 474 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 475                           *root, struct btrfs_path *path, int *level)
 476 {
 477         struct btrfs_buffer *next;
 478         struct btrfs_buffer *cur;
 479         u64 blocknr;
 480         int ret;
 481         u32 refs;
 482
 483         ret = lookup_block_ref(trans, root, path->nodes[*level]->blocknr,
 484                                &refs);
 485         BUG_ON(ret);
 486         if (refs > 1)
 487                 goto out;
 488         /*
 489          * walk down to the last node level and free all the leaves
 490          */
 491         while(*level > 0) {
 492                 cur = path->nodes[*level];
 493                 if (path->slots[*level] >=
 494                     btrfs_header_nritems(&cur->node.header))
 495                         break;
 496                 blocknr = btrfs_node_blockptr(&cur->node, path->slots[*level]);
 497                 ret = lookup_block_ref(trans, root, blocknr, &refs);
 498                 if (refs != 1 || *level == 1) {
 499                         path->slots[*level]++;
 500                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
 501                         BUG_ON(ret);
 502                         continue;
 503                 }
 504                 BUG_ON(ret);
 505                 next = read_tree_block(root, blocknr);
 506                 if (path->nodes[*level-1])
 507                         btrfs_block_release(root, path->nodes[*level-1]);
 508                 path->nodes[*level-1] = next;
 509                 *level = btrfs_header_level(&next->node.header);
 510                 path->slots[*level] = 0;
 511         }
 512 out:
 513         ret = btrfs_free_extent(trans, root, path->nodes[*level]->blocknr, 1,
 514                                 1);
 515         btrfs_block_release(root, path->nodes[*level]);
 516         path->nodes[*level] = NULL;
 517         *level += 1;
 518         BUG_ON(ret);
 519         return 0;
 520 }
 521
 522 /*
 523  * helper for dropping snapshots.  This walks back up the tree in the path
 524  * to find the first node higher up where we haven't yet gone through
 525  * all the slots
 526  */
 527 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 528                         *root, struct btrfs_path *path, int *level)
 529 {
 530         int i;
 531         int slot;
 532         int ret;
 533         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 534                 slot = path->slots[i];
 535                 if (slot <
 536                     btrfs_header_nritems(&path->nodes[i]->node.header)- 1) {
 537                         path->slots[i]++;
 538                         *level = i;
 539                         return 0;
 540                 } else {
 541                         ret = btrfs_free_extent(trans, root,
 542                                                 path->nodes[*level]->blocknr,
 543                                                 1, 1);
 544                         btrfs_block_release(root, path->nodes[*level]);
 545                         path->nodes[*level] = NULL;
 546                         *level = i + 1;
 547                         BUG_ON(ret);
 548                 }
 549         }
 550         return 1;
 551 }
 552
 553 /*
 554  * drop the reference count on the tree rooted at 'snap'.  This traverses
 555  * the tree freeing any blocks that have a ref count of zero after being
 556  * decremented.
 557  */
 558 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
 559                         *root, struct btrfs_buffer *snap)
 560 {
 561         int ret = 0;
 562         int wret;
 563         int level;
 564         struct btrfs_path path;
 565         int i;
 566         int orig_level;
 567
 568         btrfs_init_path(&path);
 569
 570         level = btrfs_header_level(&snap->node.header);
 571         orig_level = level;
 572         path.nodes[level] = snap;
 573         path.slots[level] = 0;
 574         while(1) {
 575                 wret = walk_down_tree(trans, root, &path, &level);
 576                 if (wret > 0)
 577                         break;
 578                 if (wret < 0)
 579                         ret = wret;
 580
 581                 wret = walk_up_tree(trans, root, &path, &level);
 582                 if (wret > 0)
 583                         break;
 584                 if (wret < 0)
 585                         ret = wret;
 586         }
 587         for (i = 0; i <= orig_level; i++) {
 588                 if (path.nodes[i]) {
 589                         btrfs_block_release(root, path.nodes[i]);
 590                 }
 591         }
 592         return ret;
 593 }