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 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 105                                  struct btrfs_root *root,
 106                                  struct btrfs_path *path,
 107                                  struct btrfs_block_group_cache *cache)
 108 {
 109         int ret;
 110         int pending_ret;
 111         struct btrfs_root *extent_root = root->fs_info->extent_root;
 112         struct btrfs_block_group_item *bi;
 113         struct btrfs_key ins;
 114
 115         ret = find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
 116         if (ret)
 117                 return ret;
 118         ret = btrfs_search_slot(trans, root->fs_info->extent_root,
 119                                 &cache->key, path, 0, 1);
 120         BUG_ON(ret);
 121         bi = btrfs_item_ptr(&path->nodes[0]->leaf, path->slots[0],
 122                             struct btrfs_block_group_item);
 123         memcpy(bi, &cache->item, sizeof(*bi));
 124         dirty_tree_block(trans, extent_root, path->nodes[0]);
 125         btrfs_release_path(extent_root, path);
 126         finish_current_insert(trans, root);
 127         pending_ret = run_pending(trans, root);
 128         if (ret)
 129                 return ret;
 130         if (pending_ret)
 131                 return pending_ret;
 132         return 0;
 133
 134 }
 135
 136 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 137                                     struct btrfs_root *root)
 138 {
 139         struct btrfs_block_group_cache *cache[8];
 140         int ret;
 141         int err = 0;
 142         int werr = 0;
 143         struct radix_tree_root *radix = &root->fs_info->block_group_radix;
 144         int i;
 145         struct btrfs_path path;
 146         btrfs_init_path(&path);
 147
 148         while(1) {
 149                 ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
 150                                                  0, ARRAY_SIZE(cache),
 151                                                  BTRFS_BLOCK_GROUP_DIRTY);
 152                 if (!ret)
 153                         break;
 154                 for (i = 0; i < ret; i++) {
 155                         radix_tree_tag_clear(radix, cache[i]->key.objectid +
 156                                              cache[i]->key.offset -1,
 157                                              BTRFS_BLOCK_GROUP_DIRTY);
 158                         err = write_one_cache_group(trans, root,
 159                                                     &path, cache[i]);
 160                         if (err)
 161                                 werr = err;
 162                 }
 163         }
 164         return werr;
 165 }
 166
 167 static int update_block_group(struct btrfs_trans_handle *trans,
 168                               struct btrfs_root *root,
 169                               u64 blocknr, u64 num, int alloc)
 170 {
 171         struct btrfs_block_group_cache *cache;
 172         struct btrfs_fs_info *info = root->fs_info;
 173         u64 total = num;
 174         u64 old_val;
 175         u64 block_in_group;
 176         int ret;
 177
 178         while(total) {
 179                 ret = radix_tree_gang_lookup(&info->block_group_radix,
 180                                              (void **)&cache, blocknr, 1);
 181                 if (!ret)
 182                         return -1;
 183                 radix_tree_tag_set(&info->block_group_radix,
 184                                    cache->key.objectid + cache->key.offset - 1,
 185                                    BTRFS_BLOCK_GROUP_DIRTY);
 186
 187                 block_in_group = blocknr - cache->key.objectid;
 188                 old_val = btrfs_block_group_used(&cache->item);
 189                 if (total > cache->key.offset - block_in_group)
 190                         num = cache->key.offset - block_in_group;
 191                 else
 192                         num = total;
 193                 total -= num;
 194                 blocknr += num;
 195                 if (alloc)
 196                         old_val += num;
 197                 else
 198                         old_val -= num;
 199                 btrfs_set_block_group_used(&cache->item, old_val);
 200         }
 201         return 0;
 202 }
 203
 204 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
 205                                btrfs_root *root)
 206 {
 207         unsigned long gang[8];
 208         u64 first = 0;
 209         int ret;
 210         int i;
 211
 212         while(1) {
 213                 ret = radix_tree_gang_lookup(&root->fs_info->pinned_radix,
 214                                              (void **)gang, 0,
 215                                              ARRAY_SIZE(gang));
 216                 if (!ret)
 217                         break;
 218                 if (!first)
 219                         first = gang[0];
 220                 for (i = 0; i < ret; i++) {
 221                         radix_tree_delete(&root->fs_info->pinned_radix,
 222                                           gang[i]);
 223                 }
 224         }
 225         root->fs_info->last_insert.objectid = first;
 226         root->fs_info->last_insert.offset = 0;
 227         return 0;
 228 }
 229
 230 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 231                                  btrfs_root *extent_root)
 232 {
 233         struct btrfs_key ins;
 234         struct btrfs_extent_item extent_item;
 235         int i;
 236         int ret;
 237         u64 super_blocks_used;
 238         struct btrfs_fs_info *info = extent_root->fs_info;
 239
 240         btrfs_set_extent_refs(&extent_item, 1);
 241         btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid);
 242         ins.offset = 1;
 243         ins.flags = 0;
 244         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 245
 246         for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) {
 247                 ins.objectid = extent_root->fs_info->current_insert.objectid +
 248                                 i;
 249                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 250                 btrfs_set_super_blocks_used(info->disk_super,
 251                                             super_blocks_used + 1);
 252                 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
 253                                         sizeof(extent_item));
 254                 if (ret) {
 255                         btrfs_print_tree(extent_root, extent_root->node);
 256                 }
 257                 BUG_ON(ret);
 258         }
 259         extent_root->fs_info->current_insert.offset = 0;
 260         return 0;
 261 }
 262
 263 /*
 264  * remove an extent from the root, returns 0 on success
 265  */
 266 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 267                          *root, u64 blocknr, u64 num_blocks, int pin)
 268 {
 269         struct btrfs_path path;
 270         struct btrfs_key key;
 271         struct btrfs_fs_info *info = root->fs_info;
 272         struct btrfs_root *extent_root = info->extent_root;
 273         int ret;
 274         struct btrfs_extent_item *ei;
 275         struct btrfs_key ins;
 276         u32 refs;
 277
 278         BUG_ON(pin && num_blocks != 1);
 279         key.objectid = blocknr;
 280         key.flags = 0;
 281         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 282         key.offset = num_blocks;
 283
 284         find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
 285         btrfs_init_path(&path);
 286         ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1);
 287         if (ret) {
 288                 printf("failed to find %Lu\n", key.objectid);
 289                 btrfs_print_tree(extent_root, extent_root->node);
 290                 printf("failed to find %Lu\n", key.objectid);
 291                 BUG();
 292         }
 293         ei = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
 294                             struct btrfs_extent_item);
 295         BUG_ON(ei->refs == 0);
 296         refs = btrfs_extent_refs(ei) - 1;
 297         btrfs_set_extent_refs(ei, refs);
 298         if (refs == 0) {
 299                 u64 super_blocks_used;
 300                 if (pin) {
 301                         int err;
 302                         radix_tree_preload(GFP_KERNEL);
 303                         err = radix_tree_insert(&info->pinned_radix,
 304                                                 blocknr, (void *)blocknr);
 305                         BUG_ON(err);
 306                         radix_tree_preload_end();
 307                 }
 308                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 309                 btrfs_set_super_blocks_used(info->disk_super,
 310                                             super_blocks_used - num_blocks);
 311                 ret = btrfs_del_item(trans, extent_root, &path);
 312                 if (!pin && extent_root->fs_info->last_insert.objectid >
 313                     blocknr)
 314                         extent_root->fs_info->last_insert.objectid = blocknr;
 315                 if (ret)
 316                         BUG();
 317                 ret = update_block_group(trans, root, blocknr, num_blocks, 0);
 318                 BUG_ON(ret);
 319         }
 320         btrfs_release_path(extent_root, &path);
 321         finish_current_insert(trans, extent_root);
 322         return ret;
 323 }
 324
 325 /*
 326  * find all the blocks marked as pending in the radix tree and remove
 327  * them from the extent map
 328  */
 329 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 330                                btrfs_root *extent_root)
 331 {
 332         int ret;
 333         struct btrfs_buffer *gang[4];
 334         int i;
 335
 336         while(1) {
 337                 ret = radix_tree_gang_lookup_tag(
 338                                         &extent_root->fs_info->cache_radix,
 339                                         (void **)gang, 0,
 340                                         ARRAY_SIZE(gang),
 341                                         CTREE_EXTENT_PENDING_DEL);
 342                 if (!ret)
 343                         break;
 344                 for (i = 0; i < ret; i++) {
 345                         ret = __free_extent(trans, extent_root,
 346                                             gang[i]->blocknr, 1, 1);
 347                         radix_tree_tag_clear(&extent_root->fs_info->cache_radix,
 348                                              gang[i]->blocknr,
 349                                              CTREE_EXTENT_PENDING_DEL);
 350                         btrfs_block_release(extent_root, gang[i]);
 351                 }
 352         }
 353         return 0;
 354 }
 355
 356 static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
 357                        *extent_root)
 358 {
 359         while(radix_tree_tagged(&extent_root->fs_info->cache_radix,
 360                                 CTREE_EXTENT_PENDING_DEL))
 361                 del_pending_extents(trans, extent_root);
 362         return 0;
 363 }
 364
 365
 366 /*
 367  * remove an extent from the root, returns 0 on success
 368  */
 369 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 370                       *root, u64 blocknr, u64 num_blocks, int pin)
 371 {
 372         struct btrfs_root *extent_root = root->fs_info->extent_root;
 373         struct btrfs_buffer *t;
 374         int pending_ret;
 375         int ret;
 376
 377         if (root == extent_root) {
 378                 t = find_tree_block(root, blocknr);
 379                 radix_tree_tag_set(&root->fs_info->cache_radix, blocknr,
 380                                    CTREE_EXTENT_PENDING_DEL);
 381                 return 0;
 382         }
 383         ret = __free_extent(trans, root, blocknr, num_blocks, pin);
 384         pending_ret = run_pending(trans, root->fs_info->extent_root);
 385         return ret ? ret : pending_ret;
 386 }
 387
 388 /*
 389  * walks the btree of allocated extents and find a hole of a given size.
 390  * The key ins is changed to record the hole:
 391  * ins->objectid == block start
 392  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 393  * ins->offset == number of blocks
 394  * Any available blocks before search_start are skipped.
 395  */
 396 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 397                             *orig_root, u64 num_blocks, u64 search_start, u64
 398                             search_end, struct btrfs_key *ins)
 399 {
 400         struct btrfs_path path;
 401         struct btrfs_key key;
 402         int ret;
 403         u64 hole_size = 0;
 404         int slot = 0;
 405         u64 last_block = 0;
 406         u64 test_block;
 407         int start_found;
 408         struct btrfs_leaf *l;
 409         struct btrfs_root * root = orig_root->fs_info->extent_root;
 410         int total_needed = num_blocks;
 411
 412         total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
 413         if (root->fs_info->last_insert.objectid > search_start)
 414                 search_start = root->fs_info->last_insert.objectid;
 415
 416         ins->flags = 0;
 417         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 418
 419 check_failed:
 420         btrfs_init_path(&path);
 421         ins->objectid = search_start;
 422         ins->offset = 0;
 423         start_found = 0;
 424         ret = btrfs_search_slot(trans, root, ins, &path, 0, 0);
 425         if (ret < 0)
 426                 goto error;
 427
 428         if (path.slots[0] > 0)
 429                 path.slots[0]--;
 430
 431         while (1) {
 432                 l = &path.nodes[0]->leaf;
 433                 slot = path.slots[0];
 434                 if (slot >= btrfs_header_nritems(&l->header)) {
 435                         ret = btrfs_next_leaf(root, &path);
 436                         if (ret == 0)
 437                                 continue;
 438                         if (ret < 0)
 439                                 goto error;
 440                         if (!start_found) {
 441                                 ins->objectid = search_start;
 442                                 ins->offset = (u64)-1 - search_start;
 443                                 start_found = 1;
 444                                 goto check_pending;
 445                         }
 446                         ins->objectid = last_block > search_start ?
 447                                         last_block : search_start;
 448                         ins->offset = (u64)-1 - ins->objectid;
 449                         goto check_pending;
 450                 }
 451                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
 452                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
 453                         goto next;
 454                 if (key.objectid >= search_start) {
 455                         if (start_found) {
 456                                 if (last_block < search_start)
 457                                         last_block = search_start;
 458                                 hole_size = key.objectid - last_block;
 459                                 if (hole_size > total_needed) {
 460                                         ins->objectid = last_block;
 461                                         ins->offset = hole_size;
 462                                         goto check_pending;
 463                                 }
 464                         }
 465                 }
 466                 start_found = 1;
 467                 last_block = key.objectid + key.offset;
 468 next:
 469                 path.slots[0]++;
 470         }
 471         // FIXME -ENOSPC
 472 check_pending:
 473         /* we have to make sure we didn't find an extent that has already
 474          * been allocated by the map tree or the original allocation
 475          */
 476         btrfs_release_path(root, &path);
 477         BUG_ON(ins->objectid < search_start);
 478         for (test_block = ins->objectid;
 479              test_block < ins->objectid + total_needed; test_block++) {
 480                 if (radix_tree_lookup(&root->fs_info->pinned_radix,
 481                                       test_block)) {
 482                         search_start = test_block + 1;
 483                         goto check_failed;
 484                 }
 485         }
 486         BUG_ON(root->fs_info->current_insert.offset);
 487         root->fs_info->current_insert.offset = total_needed - num_blocks;
 488         root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
 489         root->fs_info->current_insert.flags = 0;
 490         root->fs_info->last_insert.objectid = ins->objectid;
 491         ins->offset = num_blocks;
 492         return 0;
 493 error:
 494         btrfs_release_path(root, &path);
 495         return ret;
 496 }
 497 /*
 498  * finds a free extent and does all the dirty work required for allocation
 499  * returns the key for the extent through ins, and a tree buffer for
 500  * the first block of the extent through buf.
 501  *
 502  * returns 0 if everything worked, non-zero otherwise.
 503  */
 504 static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 505                         *root, u64 owner, u64 num_blocks,
 506                         u64 search_start, u64
 507                         search_end, struct btrfs_key *ins)
 508 {
 509         int ret;
 510         int pending_ret;
 511         u64 super_blocks_used;
 512         struct btrfs_fs_info *info = root->fs_info;
 513         struct btrfs_root *extent_root = info->extent_root;
 514         struct btrfs_extent_item extent_item;
 515
 516         btrfs_set_extent_refs(&extent_item, 1);
 517         btrfs_set_extent_owner(&extent_item, owner);
 518
 519         if (root == extent_root) {
 520                 BUG_ON(extent_root->fs_info->current_insert.offset == 0);
 521                 BUG_ON(num_blocks != 1);
 522                 BUG_ON(extent_root->fs_info->current_insert.flags ==
 523                        extent_root->fs_info->current_insert.offset);
 524                 ins->offset = 1;
 525                 ins->objectid = extent_root->fs_info->current_insert.objectid +
 526                                 extent_root->fs_info->current_insert.flags++;
 527                 return 0;
 528         }
 529         ret = find_free_extent(trans, root, num_blocks, search_start,
 530                                search_end, ins);
 531         if (ret)
 532                 return ret;
 533
 534         super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 535         btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
 536                                     num_blocks);
 537         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
 538                                 sizeof(extent_item));
 539
 540         finish_current_insert(trans, extent_root);
 541         pending_ret = run_pending(trans, extent_root);
 542         if (ret)
 543                 return ret;
 544         if (pending_ret)
 545                 return pending_ret;
 546         return 0;
 547 }
 548
 549 /*
 550  * helper function to allocate a block for a given tree
 551  * returns the tree buffer or NULL.
 552  */
 553 struct btrfs_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
 554                                             struct btrfs_root *root)
 555 {
 556         struct btrfs_key ins;
 557         int ret;
 558         struct btrfs_buffer *buf;
 559
 560         ret = alloc_extent(trans, root, root->root_key.objectid,
 561                            1, 0, (unsigned long)-1, &ins);
 562         if (ret) {
 563                 BUG();
 564                 return NULL;
 565         }
 566         ret = update_block_group(trans, root, ins.objectid, ins.offset, 1);
 567         buf = find_tree_block(root, ins.objectid);
 568         btrfs_set_header_generation(&buf->node.header,
 569                                     root->root_key.offset + 1);
 570         btrfs_set_header_blocknr(&buf->node.header, buf->blocknr);
 571         memcpy(buf->node.header.fsid, root->fs_info->disk_super->fsid,
 572                sizeof(buf->node.header.fsid));
 573         dirty_tree_block(trans, root, buf);
 574         return buf;
 575
 576 }
 577
 578 /*
 579  * helper function for drop_snapshot, this walks down the tree dropping ref
 580  * counts as it goes.
 581  */
 582 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 583                           *root, struct btrfs_path *path, int *level)
 584 {
 585         struct btrfs_buffer *next;
 586         struct btrfs_buffer *cur;
 587         u64 blocknr;
 588         int ret;
 589         u32 refs;
 590
 591         ret = lookup_block_ref(trans, root, path->nodes[*level]->blocknr,
 592                                &refs);
 593         BUG_ON(ret);
 594         if (refs > 1)
 595                 goto out;
 596         /*
 597          * walk down to the last node level and free all the leaves
 598          */
 599         while(*level > 0) {
 600                 cur = path->nodes[*level];
 601                 if (path->slots[*level] >=
 602                     btrfs_header_nritems(&cur->node.header))
 603                         break;
 604                 blocknr = btrfs_node_blockptr(&cur->node, path->slots[*level]);
 605                 ret = lookup_block_ref(trans, root, blocknr, &refs);
 606                 if (refs != 1 || *level == 1) {
 607                         path->slots[*level]++;
 608                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
 609                         BUG_ON(ret);
 610                         continue;
 611                 }
 612                 BUG_ON(ret);
 613                 next = read_tree_block(root, blocknr);
 614                 if (path->nodes[*level-1])
 615                         btrfs_block_release(root, path->nodes[*level-1]);
 616                 path->nodes[*level-1] = next;
 617                 *level = btrfs_header_level(&next->node.header);
 618                 path->slots[*level] = 0;
 619         }
 620 out:
 621         ret = btrfs_free_extent(trans, root, path->nodes[*level]->blocknr, 1,
 622                                 1);
 623         btrfs_block_release(root, path->nodes[*level]);
 624         path->nodes[*level] = NULL;
 625         *level += 1;
 626         BUG_ON(ret);
 627         return 0;
 628 }
 629
 630 /*
 631  * helper for dropping snapshots.  This walks back up the tree in the path
 632  * to find the first node higher up where we haven't yet gone through
 633  * all the slots
 634  */
 635 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 636                         *root, struct btrfs_path *path, int *level)
 637 {
 638         int i;
 639         int slot;
 640         int ret;
 641         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 642                 slot = path->slots[i];
 643                 if (slot <
 644                     btrfs_header_nritems(&path->nodes[i]->node.header)- 1) {
 645                         path->slots[i]++;
 646                         *level = i;
 647                         return 0;
 648                 } else {
 649                         ret = btrfs_free_extent(trans, root,
 650                                                 path->nodes[*level]->blocknr,
 651                                                 1, 1);
 652                         btrfs_block_release(root, path->nodes[*level]);
 653                         path->nodes[*level] = NULL;
 654                         *level = i + 1;
 655                         BUG_ON(ret);
 656                 }
 657         }
 658         return 1;
 659 }
 660
 661 /*
 662  * drop the reference count on the tree rooted at 'snap'.  This traverses
 663  * the tree freeing any blocks that have a ref count of zero after being
 664  * decremented.
 665  */
 666 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
 667                         *root, struct btrfs_buffer *snap)
 668 {
 669         int ret = 0;
 670         int wret;
 671         int level;
 672         struct btrfs_path path;
 673         int i;
 674         int orig_level;
 675
 676         btrfs_init_path(&path);
 677
 678         level = btrfs_header_level(&snap->node.header);
 679         orig_level = level;
 680         path.nodes[level] = snap;
 681         path.slots[level] = 0;
 682         while(1) {
 683                 wret = walk_down_tree(trans, root, &path, &level);
 684                 if (wret > 0)
 685                         break;
 686                 if (wret < 0)
 687                         ret = wret;
 688
 689                 wret = walk_up_tree(trans, root, &path, &level);
 690                 if (wret > 0)
 691                         break;
 692                 if (wret < 0)
 693                         ret = wret;
 694         }
 695         for (i = 0; i <= orig_level; i++) {
 696                 if (path.nodes[i]) {
 697                         btrfs_block_release(root, path.nodes[i]);
 698                 }
 699         }
 700         return ret;
 701 }
 702
 703 int btrfs_free_block_groups(struct btrfs_fs_info *info)
 704 {
 705         int ret;
 706         struct btrfs_block_group_cache *cache[8];
 707         int i;
 708
 709         while(1) {
 710                 ret = radix_tree_gang_lookup(&info->block_group_radix,
 711                                              (void **)cache, 0,
 712                                              ARRAY_SIZE(cache));
 713                 if (!ret)
 714                         break;
 715                 for (i = 0; i < ret; i++) {
 716                         radix_tree_delete(&info->block_group_radix,
 717                                           cache[i]->key.objectid +
 718                                           cache[i]->key.offset - 1);
 719                         free(cache[i]);
 720                 }
 721         }
 722         return 0;
 723 }
 724
 725 int btrfs_read_block_groups(struct btrfs_root *root)
 726 {
 727         struct btrfs_path path;
 728         int ret;
 729         int err = 0;
 730         struct btrfs_block_group_item *bi;
 731         struct btrfs_block_group_cache *cache;
 732         struct btrfs_key key;
 733         struct btrfs_key found_key;
 734         struct btrfs_leaf *leaf;
 735         u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;
 736
 737         root = root->fs_info->extent_root;
 738         key.objectid = 0;
 739         key.offset = group_size_blocks;
 740         key.flags = 0;
 741         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
 742         btrfs_init_path(&path);
 743
 744         while(1) {
 745                 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
 746                                         &key, &path, 0, 0);
 747                 if (ret != 0) {
 748                         err = ret;
 749                         break;
 750                 }
 751                 leaf = &path.nodes[0]->leaf;
 752                 btrfs_disk_key_to_cpu(&found_key,
 753                                       &leaf->items[path.slots[0]].key);
 754                 cache = malloc(sizeof(*cache));
 755                 if (!cache) {
 756                         err = -1;
 757                         break;
 758                 }
 759                 bi = btrfs_item_ptr(leaf, path.slots[0],
 760                                     struct btrfs_block_group_item);
 761                 memcpy(&cache->item, bi, sizeof(*bi));
 762                 memcpy(&cache->key, &found_key, sizeof(found_key));
 763                 key.objectid = found_key.objectid + found_key.offset;
 764                 btrfs_release_path(root, &path);
 765                 ret = radix_tree_insert(&root->fs_info->block_group_radix,
 766                                         found_key.objectid +
 767                                         found_key.offset - 1, (void *)cache);
 768                 BUG_ON(ret);
 769                 if (key.objectid >=
 770                     btrfs_super_total_blocks(root->fs_info->disk_super))
 771                         break;
 772         }
 773         btrfs_release_path(root, &path);
 774         return 0;
 775 }
 776
 777 int btrfs_insert_block_group(struct btrfs_trans_handle *trans,
 778                              struct btrfs_root *root,
 779                              struct btrfs_key *key,
 780                              struct btrfs_block_group_item *bi)
 781 {
 782         struct btrfs_key ins;
 783         int ret;
 784         int pending_ret;
 785
 786         root = root->fs_info->extent_root;
 787         ret = find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
 788         if (ret)
 789                 return ret;
 790         ret = btrfs_insert_item(trans, root, key, bi, sizeof(*bi));
 791         finish_current_insert(trans, root);
 792         pending_ret = run_pending(trans, root);
 793         if (ret)
 794                 return ret;
 795         if (pending_ret)
 796                 return pending_ret;
 797         return ret;
 798 }