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