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