extent-tree.c

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