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                         unsigned long bl = blocknr;
 303                         radix_tree_preload(GFP_KERNEL);
 304                         err = radix_tree_insert(&info->pinned_radix,
 305                                                 blocknr, (void *)bl);
 306                         BUG_ON(err);
 307                         radix_tree_preload_end();
 308                 }
 309                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 310                 btrfs_set_super_blocks_used(info->disk_super,
 311                                             super_blocks_used - num_blocks);
 312                 ret = btrfs_del_item(trans, extent_root, &path);
 313                 if (!pin && extent_root->fs_info->last_insert.objectid >
 314                     blocknr)
 315                         extent_root->fs_info->last_insert.objectid = blocknr;
 316                 if (ret)
 317                         BUG();
 318                 ret = update_block_group(trans, root, blocknr, num_blocks, 0);
 319                 BUG_ON(ret);
 320         }
 321         btrfs_release_path(extent_root, &path);
 322         finish_current_insert(trans, extent_root);
 323         return ret;
 324 }
 325
 326 /*
 327  * find all the blocks marked as pending in the radix tree and remove
 328  * them from the extent map
 329  */
 330 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 331                                btrfs_root *extent_root)
 332 {
 333         int ret;
 334         struct btrfs_buffer *gang[4];
 335         int i;
 336
 337         while(1) {
 338                 ret = radix_tree_gang_lookup_tag(
 339                                         &extent_root->fs_info->cache_radix,
 340                                         (void **)gang, 0,
 341                                         ARRAY_SIZE(gang),
 342                                         CTREE_EXTENT_PENDING_DEL);
 343                 if (!ret)
 344                         break;
 345                 for (i = 0; i < ret; i++) {
 346                         ret = __free_extent(trans, extent_root,
 347                                             gang[i]->blocknr, 1, 1);
 348                         radix_tree_tag_clear(&extent_root->fs_info->cache_radix,
 349                                              gang[i]->blocknr,
 350                                              CTREE_EXTENT_PENDING_DEL);
 351                         btrfs_block_release(extent_root, gang[i]);
 352                 }
 353         }
 354         return 0;
 355 }
 356
 357 static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
 358                        *extent_root)
 359 {
 360         while(radix_tree_tagged(&extent_root->fs_info->cache_radix,
 361                                 CTREE_EXTENT_PENDING_DEL))
 362                 del_pending_extents(trans, extent_root);
 363         return 0;
 364 }
 365
 366
 367 /*
 368  * remove an extent from the root, returns 0 on success
 369  */
 370 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 371                       *root, u64 blocknr, u64 num_blocks, int pin)
 372 {
 373         struct btrfs_root *extent_root = root->fs_info->extent_root;
 374         struct btrfs_buffer *t;
 375         int pending_ret;
 376         int ret;
 377
 378         if (root == extent_root) {
 379                 t = find_tree_block(root, blocknr);
 380                 radix_tree_tag_set(&root->fs_info->cache_radix, blocknr,
 381                                    CTREE_EXTENT_PENDING_DEL);
 382                 return 0;
 383         }
 384         ret = __free_extent(trans, root, blocknr, num_blocks, pin);
 385         pending_ret = run_pending(trans, root->fs_info->extent_root);
 386         return ret ? ret : pending_ret;
 387 }
 388
 389 /*
 390  * walks the btree of allocated extents and find a hole of a given size.
 391  * The key ins is changed to record the hole:
 392  * ins->objectid == block start
 393  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 394  * ins->offset == number of blocks
 395  * Any available blocks before search_start are skipped.
 396  */
 397 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 398                             *orig_root, u64 num_blocks, u64 search_start, u64
 399                             search_end, struct btrfs_key *ins)
 400 {
 401         struct btrfs_path path;
 402         struct btrfs_key key;
 403         int ret;
 404         u64 hole_size = 0;
 405         int slot = 0;
 406         u64 last_block = 0;
 407         u64 test_block;
 408         int start_found;
 409         struct btrfs_leaf *l;
 410         struct btrfs_root * root = orig_root->fs_info->extent_root;
 411         int total_needed = num_blocks;
 412
 413         total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
 414         if (root->fs_info->last_insert.objectid > search_start)
 415                 search_start = root->fs_info->last_insert.objectid;
 416
 417         ins->flags = 0;
 418         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 419
 420 check_failed:
 421         btrfs_init_path(&path);
 422         ins->objectid = search_start;
 423         ins->offset = 0;
 424         start_found = 0;
 425         ret = btrfs_search_slot(trans, root, ins, &path, 0, 0);
 426         if (ret < 0)
 427                 goto error;
 428
 429         if (path.slots[0] > 0)
 430                 path.slots[0]--;
 431
 432         while (1) {
 433                 l = &path.nodes[0]->leaf;
 434                 slot = path.slots[0];
 435                 if (slot >= btrfs_header_nritems(&l->header)) {
 436                         ret = btrfs_next_leaf(root, &path);
 437                         if (ret == 0)
 438                                 continue;
 439                         if (ret < 0)
 440                                 goto error;
 441                         if (!start_found) {
 442                                 ins->objectid = search_start;
 443                                 ins->offset = (u64)-1 - search_start;
 444                                 start_found = 1;
 445                                 goto check_pending;
 446                         }
 447                         ins->objectid = last_block > search_start ?
 448                                         last_block : search_start;
 449                         ins->offset = (u64)-1 - ins->objectid;
 450                         goto check_pending;
 451                 }
 452                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
 453                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
 454                         goto next;
 455                 if (key.objectid >= search_start) {
 456                         if (start_found) {
 457                                 if (last_block < search_start)
 458                                         last_block = search_start;
 459                                 hole_size = key.objectid - last_block;
 460                                 if (hole_size > total_needed) {
 461                                         ins->objectid = last_block;
 462                                         ins->offset = hole_size;
 463                                         goto check_pending;
 464                                 }
 465                         }
 466                 }
 467                 start_found = 1;
 468                 last_block = key.objectid + key.offset;
 469 next:
 470                 path.slots[0]++;
 471         }
 472         // FIXME -ENOSPC
 473 check_pending:
 474         /* we have to make sure we didn't find an extent that has already
 475          * been allocated by the map tree or the original allocation
 476          */
 477         btrfs_release_path(root, &path);
 478         BUG_ON(ins->objectid < search_start);
 479         for (test_block = ins->objectid;
 480              test_block < ins->objectid + total_needed; test_block++) {
 481                 if (radix_tree_lookup(&root->fs_info->pinned_radix,
 482                                       test_block)) {
 483                         search_start = test_block + 1;
 484                         goto check_failed;
 485                 }
 486         }
 487         BUG_ON(root->fs_info->current_insert.offset);
 488         root->fs_info->current_insert.offset = total_needed - num_blocks;
 489         root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
 490         root->fs_info->current_insert.flags = 0;
 491         root->fs_info->last_insert.objectid = ins->objectid;
 492         ins->offset = num_blocks;
 493         return 0;
 494 error:
 495         btrfs_release_path(root, &path);
 496         return ret;
 497 }
 498 /*
 499  * finds a free extent and does all the dirty work required for allocation
 500  * returns the key for the extent through ins, and a tree buffer for
 501  * the first block of the extent through buf.
 502  *
 503  * returns 0 if everything worked, non-zero otherwise.
 504  */
 505 static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 506                         *root, u64 owner, u64 num_blocks,
 507                         u64 search_start, u64
 508                         search_end, struct btrfs_key *ins)
 509 {
 510         int ret;
 511         int pending_ret;
 512         u64 super_blocks_used;
 513         struct btrfs_fs_info *info = root->fs_info;
 514         struct btrfs_root *extent_root = info->extent_root;
 515         struct btrfs_extent_item extent_item;
 516
 517         btrfs_set_extent_refs(&extent_item, 1);
 518         btrfs_set_extent_owner(&extent_item, owner);
 519
 520         if (root == extent_root) {
 521                 BUG_ON(extent_root->fs_info->current_insert.offset == 0);
 522                 BUG_ON(num_blocks != 1);
 523                 BUG_ON(extent_root->fs_info->current_insert.flags ==
 524                        extent_root->fs_info->current_insert.offset);
 525                 ins->offset = 1;
 526                 ins->objectid = extent_root->fs_info->current_insert.objectid +
 527                                 extent_root->fs_info->current_insert.flags++;
 528                 return 0;
 529         }
 530         ret = find_free_extent(trans, root, num_blocks, search_start,
 531                                search_end, ins);
 532         if (ret)
 533                 return ret;
 534
 535         super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 536         btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
 537                                     num_blocks);
 538         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
 539                                 sizeof(extent_item));
 540
 541         finish_current_insert(trans, extent_root);
 542         pending_ret = run_pending(trans, extent_root);
 543         if (ret)
 544                 return ret;
 545         if (pending_ret)
 546                 return pending_ret;
 547         return 0;
 548 }
 549
 550 /*
 551  * helper function to allocate a block for a given tree
 552  * returns the tree buffer or NULL.
 553  */
 554 struct btrfs_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
 555                                             struct btrfs_root *root)
 556 {
 557         struct btrfs_key ins;
 558         int ret;
 559         struct btrfs_buffer *buf;
 560
 561         ret = alloc_extent(trans, root, root->root_key.objectid,
 562                            1, 0, (unsigned long)-1, &ins);
 563         if (ret) {
 564                 BUG();
 565                 return NULL;
 566         }
 567         ret = update_block_group(trans, root, ins.objectid, ins.offset, 1);
 568         buf = find_tree_block(root, ins.objectid);
 569         btrfs_set_header_generation(&buf->node.header,
 570                                     root->root_key.offset + 1);
 571         btrfs_set_header_blocknr(&buf->node.header, buf->blocknr);
 572         memcpy(buf->node.header.fsid, root->fs_info->disk_super->fsid,
 573                sizeof(buf->node.header.fsid));
 574         dirty_tree_block(trans, root, buf);
 575         return buf;
 576
 577 }
 578
 579 /*
 580  * helper function for drop_snapshot, this walks down the tree dropping ref
 581  * counts as it goes.
 582  */
 583 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 584                           *root, struct btrfs_path *path, int *level)
 585 {
 586         struct btrfs_buffer *next;
 587         struct btrfs_buffer *cur;
 588         u64 blocknr;
 589         int ret;
 590         u32 refs;
 591
 592         ret = lookup_block_ref(trans, root, path->nodes[*level]->blocknr,
 593                                &refs);
 594         BUG_ON(ret);
 595         if (refs > 1)
 596                 goto out;
 597         /*
 598          * walk down to the last node level and free all the leaves
 599          */
 600         while(*level > 0) {
 601                 cur = path->nodes[*level];
 602                 if (path->slots[*level] >=
 603                     btrfs_header_nritems(&cur->node.header))
 604                         break;
 605                 blocknr = btrfs_node_blockptr(&cur->node, path->slots[*level]);
 606                 ret = lookup_block_ref(trans, root, blocknr, &refs);
 607                 if (refs != 1 || *level == 1) {
 608                         path->slots[*level]++;
 609                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
 610                         BUG_ON(ret);
 611                         continue;
 612                 }
 613                 BUG_ON(ret);
 614                 next = read_tree_block(root, blocknr);
 615                 if (path->nodes[*level-1])
 616                         btrfs_block_release(root, path->nodes[*level-1]);
 617                 path->nodes[*level-1] = next;
 618                 *level = btrfs_header_level(&next->node.header);
 619                 path->slots[*level] = 0;
 620         }
 621 out:
 622         ret = btrfs_free_extent(trans, root, path->nodes[*level]->blocknr, 1,
 623                                 1);
 624         btrfs_block_release(root, path->nodes[*level]);
 625         path->nodes[*level] = NULL;
 626         *level += 1;
 627         BUG_ON(ret);
 628         return 0;
 629 }
 630
 631 /*
 632  * helper for dropping snapshots.  This walks back up the tree in the path
 633  * to find the first node higher up where we haven't yet gone through
 634  * all the slots
 635  */
 636 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 637                         *root, struct btrfs_path *path, int *level)
 638 {
 639         int i;
 640         int slot;
 641         int ret;
 642         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 643                 slot = path->slots[i];
 644                 if (slot <
 645                     btrfs_header_nritems(&path->nodes[i]->node.header)- 1) {
 646                         path->slots[i]++;
 647                         *level = i;
 648                         return 0;
 649                 } else {
 650                         ret = btrfs_free_extent(trans, root,
 651                                                 path->nodes[*level]->blocknr,
 652                                                 1, 1);
 653                         btrfs_block_release(root, path->nodes[*level]);
 654                         path->nodes[*level] = NULL;
 655                         *level = i + 1;
 656                         BUG_ON(ret);
 657                 }
 658         }
 659         return 1;
 660 }
 661
 662 /*
 663  * drop the reference count on the tree rooted at 'snap'.  This traverses
 664  * the tree freeing any blocks that have a ref count of zero after being
 665  * decremented.
 666  */
 667 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
 668                         *root, struct btrfs_buffer *snap)
 669 {
 670         int ret = 0;
 671         int wret;
 672         int level;
 673         struct btrfs_path path;
 674         int i;
 675         int orig_level;
 676
 677         btrfs_init_path(&path);
 678
 679         level = btrfs_header_level(&snap->node.header);
 680         orig_level = level;
 681         path.nodes[level] = snap;
 682         path.slots[level] = 0;
 683         while(1) {
 684                 wret = walk_down_tree(trans, root, &path, &level);
 685                 if (wret > 0)
 686                         break;
 687                 if (wret < 0)
 688                         ret = wret;
 689
 690                 wret = walk_up_tree(trans, root, &path, &level);
 691                 if (wret > 0)
 692                         break;
 693                 if (wret < 0)
 694                         ret = wret;
 695         }
 696         for (i = 0; i <= orig_level; i++) {
 697                 if (path.nodes[i]) {
 698                         btrfs_block_release(root, path.nodes[i]);
 699                 }
 700         }
 701         return ret;
 702 }
 703
 704 int btrfs_free_block_groups(struct btrfs_fs_info *info)
 705 {
 706         int ret;
 707         struct btrfs_block_group_cache *cache[8];
 708         int i;
 709
 710         while(1) {
 711                 ret = radix_tree_gang_lookup(&info->block_group_radix,
 712                                              (void **)cache, 0,
 713                                              ARRAY_SIZE(cache));
 714                 if (!ret)
 715                         break;
 716                 for (i = 0; i < ret; i++) {
 717                         radix_tree_delete(&info->block_group_radix,
 718                                           cache[i]->key.objectid +
 719                                           cache[i]->key.offset - 1);
 720                         free(cache[i]);
 721                 }
 722         }
 723         return 0;
 724 }
 725
 726 int btrfs_read_block_groups(struct btrfs_root *root)
 727 {
 728         struct btrfs_path path;
 729         int ret;
 730         int err = 0;
 731         struct btrfs_block_group_item *bi;
 732         struct btrfs_block_group_cache *cache;
 733         struct btrfs_key key;
 734         struct btrfs_key found_key;
 735         struct btrfs_leaf *leaf;
 736         u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;
 737
 738         root = root->fs_info->extent_root;
 739         key.objectid = 0;
 740         key.offset = group_size_blocks;
 741         key.flags = 0;
 742         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
 743         btrfs_init_path(&path);
 744
 745         while(1) {
 746                 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
 747                                         &key, &path, 0, 0);
 748                 if (ret != 0) {
 749                         err = ret;
 750                         break;
 751                 }
 752                 leaf = &path.nodes[0]->leaf;
 753                 btrfs_disk_key_to_cpu(&found_key,
 754                                       &leaf->items[path.slots[0]].key);
 755                 cache = malloc(sizeof(*cache));
 756                 if (!cache) {
 757                         err = -1;
 758                         break;
 759                 }
 760                 bi = btrfs_item_ptr(leaf, path.slots[0],
 761                                     struct btrfs_block_group_item);
 762                 memcpy(&cache->item, bi, sizeof(*bi));
 763                 memcpy(&cache->key, &found_key, sizeof(found_key));
 764                 key.objectid = found_key.objectid + found_key.offset;
 765                 btrfs_release_path(root, &path);
 766                 ret = radix_tree_insert(&root->fs_info->block_group_radix,
 767                                         found_key.objectid +
 768                                         found_key.offset - 1, (void *)cache);
 769                 BUG_ON(ret);
 770                 if (key.objectid >=
 771                     btrfs_super_total_blocks(root->fs_info->disk_super))
 772                         break;
 773         }
 774         btrfs_release_path(root, &path);
 775         return 0;
 776 }
 777
 778 int btrfs_insert_block_group(struct btrfs_trans_handle *trans,
 779                              struct btrfs_root *root,
 780                              struct btrfs_key *key,
 781                              struct btrfs_block_group_item *bi)
 782 {
 783         struct btrfs_key ins;
 784         int ret;
 785         int pending_ret;
 786
 787         root = root->fs_info->extent_root;
 788         ret = find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
 789         if (ret)
 790                 return ret;
 791         ret = btrfs_insert_item(trans, root, key, bi, sizeof(*bi));
 792         finish_current_insert(trans, root);
 793         pending_ret = run_pending(trans, root);
 794         if (ret)
 795                 return ret;
 796         if (pending_ret)
 797                 return pending_ret;
 798         return ret;
 799 }