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