fs/btrfs/extent-tree.c

   1 #include <linux/module.h>
   2 #include "ctree.h"
   3 #include "disk-io.h"
   4 #include "print-tree.h"
   5 #include "transaction.h"
   6
   7 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
   8                             *orig_root, u64 num_blocks, u64 search_start, u64
   9                             search_end, struct btrfs_key *ins);
  10 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  11                                  btrfs_root *extent_root);
  12 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  13                                btrfs_root *extent_root);
  14
  15 static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
  16                          *root, u64 blocknr, u64 num_blocks)
  17 {
  18         struct btrfs_path path;
  19         int ret;
  20         struct btrfs_key key;
  21         struct btrfs_leaf *l;
  22         struct btrfs_extent_item *item;
  23         struct btrfs_key ins;
  24         u32 refs;
  25
  26         find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
  27                          &ins);
  28         btrfs_init_path(&path);
  29         key.objectid = blocknr;
  30         key.flags = 0;
  31         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  32         key.offset = num_blocks;
  33         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
  34                                 0, 1);
  35         if (ret != 0)
  36                 BUG();
  37         BUG_ON(ret != 0);
  38         l = btrfs_buffer_leaf(path.nodes[0]);
  39         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
  40         refs = btrfs_extent_refs(item);
  41         btrfs_set_extent_refs(item, refs + 1);
  42         btrfs_mark_buffer_dirty(path.nodes[0]);
  43
  44         btrfs_release_path(root->fs_info->extent_root, &path);
  45         finish_current_insert(trans, root->fs_info->extent_root);
  46         del_pending_extents(trans, root->fs_info->extent_root);
  47         return 0;
  48 }
  49
  50 static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
  51                             *root, u64 blocknr, u64 num_blocks, u32 *refs)
  52 {
  53         struct btrfs_path path;
  54         int ret;
  55         struct btrfs_key key;
  56         struct btrfs_leaf *l;
  57         struct btrfs_extent_item *item;
  58         btrfs_init_path(&path);
  59         key.objectid = blocknr;
  60         key.offset = num_blocks;
  61         key.flags = 0;
  62         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  63         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
  64                                 0, 0);
  65         if (ret != 0)
  66                 BUG();
  67         l = btrfs_buffer_leaf(path.nodes[0]);
  68         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
  69         *refs = btrfs_extent_refs(item);
  70         btrfs_release_path(root->fs_info->extent_root, &path);
  71         return 0;
  72 }
  73
  74 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  75                   struct buffer_head *buf)
  76 {
  77         u64 blocknr;
  78         struct btrfs_node *buf_node;
  79         struct btrfs_leaf *buf_leaf;
  80         struct btrfs_disk_key *key;
  81         struct btrfs_file_extent_item *fi;
  82         int i;
  83         int leaf;
  84         int ret;
  85
  86         if (!root->ref_cows)
  87                 return 0;
  88         buf_node = btrfs_buffer_node(buf);
  89         leaf = btrfs_is_leaf(buf_node);
  90         buf_leaf = btrfs_buffer_leaf(buf);
  91         for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
  92                 if (leaf) {
  93                         key = &buf_leaf->items[i].key;
  94                         if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
  95                                 continue;
  96                         fi = btrfs_item_ptr(buf_leaf, i,
  97                                             struct btrfs_file_extent_item);
  98                         ret = inc_block_ref(trans, root,
  99                                     btrfs_file_extent_disk_blocknr(fi),
 100                                     btrfs_file_extent_disk_num_blocks(fi));
 101                         BUG_ON(ret);
 102                 } else {
 103                         blocknr = btrfs_node_blockptr(buf_node, i);
 104                         ret = inc_block_ref(trans, root, blocknr, 1);
 105                         BUG_ON(ret);
 106                 }
 107         }
 108         return 0;
 109 }
 110
 111 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
 112                                btrfs_root *root)
 113 {
 114         unsigned long gang[8];
 115         u64 first = 0;
 116         int ret;
 117         int i;
 118         struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
 119
 120         while(1) {
 121                 ret = find_first_radix_bit(pinned_radix, gang,
 122                                            ARRAY_SIZE(gang));
 123                 if (!ret)
 124                         break;
 125                 if (!first)
 126                         first = gang[0];
 127                 for (i = 0; i < ret; i++) {
 128                         clear_radix_bit(pinned_radix, gang[i]);
 129                 }
 130         }
 131         if (root->fs_info->last_insert.objectid > first)
 132                 root->fs_info->last_insert.objectid = first;
 133         root->fs_info->last_insert.offset = 0;
 134         return 0;
 135 }
 136
 137 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 138                                  btrfs_root *extent_root)
 139 {
 140         struct btrfs_key ins;
 141         struct btrfs_extent_item extent_item;
 142         int i;
 143         int ret;
 144         u64 super_blocks_used;
 145         struct btrfs_fs_info *info = extent_root->fs_info;
 146
 147         btrfs_set_extent_refs(&extent_item, 1);
 148         btrfs_set_extent_owner(&extent_item,
 149                 btrfs_header_parentid(btrfs_buffer_header(extent_root->node)));
 150         ins.offset = 1;
 151         ins.flags = 0;
 152         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 153
 154         for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) {
 155                 ins.objectid = extent_root->fs_info->current_insert.objectid +
 156                                 i;
 157                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 158                 btrfs_set_super_blocks_used(info->disk_super,
 159                                             super_blocks_used + 1);
 160                 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
 161                                         sizeof(extent_item));
 162                 BUG_ON(ret);
 163         }
 164         extent_root->fs_info->current_insert.offset = 0;
 165         return 0;
 166 }
 167
 168 static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
 169 {
 170         int err;
 171         struct btrfs_header *header;
 172         struct buffer_head *bh;
 173
 174         if (!pending) {
 175                 bh = btrfs_find_tree_block(root, blocknr);
 176                 if (bh) {
 177                         if (buffer_uptodate(bh)) {
 178                                 u64 transid =
 179                                     root->fs_info->running_transaction->transid;
 180                                 header = btrfs_buffer_header(bh);
 181                                 if (btrfs_header_generation(header) ==
 182                                     transid) {
 183                                         btrfs_block_release(root, bh);
 184                                         return 0;
 185                                 }
 186                         }
 187                         btrfs_block_release(root, bh);
 188                 }
 189                 err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
 190         } else {
 191                 err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
 192         }
 193         BUG_ON(err);
 194         return 0;
 195 }
 196
 197 /*
 198  * remove an extent from the root, returns 0 on success
 199  */
 200 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 201                          *root, u64 blocknr, u64 num_blocks, int pin)
 202 {
 203         struct btrfs_path path;
 204         struct btrfs_key key;
 205         struct btrfs_fs_info *info = root->fs_info;
 206         struct btrfs_root *extent_root = info->extent_root;
 207         int ret;
 208         struct btrfs_extent_item *ei;
 209         struct btrfs_key ins;
 210         u32 refs;
 211
 212         key.objectid = blocknr;
 213         key.flags = 0;
 214         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 215         key.offset = num_blocks;
 216
 217         find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
 218         btrfs_init_path(&path);
 219         ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1);
 220         if (ret) {
 221                 printk("failed to find %Lu\n", key.objectid);
 222                 btrfs_print_tree(extent_root, extent_root->node);
 223                 printk("failed to find %Lu\n", key.objectid);
 224                 BUG();
 225         }
 226         ei = btrfs_item_ptr(btrfs_buffer_leaf(path.nodes[0]), path.slots[0],
 227                             struct btrfs_extent_item);
 228         BUG_ON(ei->refs == 0);
 229         refs = btrfs_extent_refs(ei) - 1;
 230         btrfs_set_extent_refs(ei, refs);
 231         btrfs_mark_buffer_dirty(path.nodes[0]);
 232         if (refs == 0) {
 233                 u64 super_blocks_used;
 234
 235                 if (pin) {
 236                         ret = pin_down_block(root, blocknr, 0);
 237                         BUG_ON(ret);
 238                 }
 239
 240                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 241                 btrfs_set_super_blocks_used(info->disk_super,
 242                                             super_blocks_used - num_blocks);
 243                 ret = btrfs_del_item(trans, extent_root, &path);
 244                 if (extent_root->fs_info->last_insert.objectid > blocknr)
 245                         extent_root->fs_info->last_insert.objectid = blocknr;
 246                 if (ret)
 247                         BUG();
 248         }
 249         btrfs_release_path(extent_root, &path);
 250         finish_current_insert(trans, extent_root);
 251         return ret;
 252 }
 253
 254 /*
 255  * find all the blocks marked as pending in the radix tree and remove
 256  * them from the extent map
 257  */
 258 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 259                                btrfs_root *extent_root)
 260 {
 261         int ret;
 262         int wret;
 263         int err = 0;
 264         unsigned long gang[4];
 265         int i;
 266         struct radix_tree_root *pending_radix;
 267         struct radix_tree_root *pinned_radix;
 268
 269         pending_radix = &extent_root->fs_info->pending_del_radix;
 270         pinned_radix = &extent_root->fs_info->pinned_radix;
 271
 272         while(1) {
 273                 ret = find_first_radix_bit(pending_radix, gang,
 274                                            ARRAY_SIZE(gang));
 275                 if (!ret)
 276                         break;
 277                 for (i = 0; i < ret; i++) {
 278                         wret = set_radix_bit(pinned_radix, gang[i]);
 279                         BUG_ON(wret);
 280                         wret = clear_radix_bit(pending_radix, gang[i]);
 281                         BUG_ON(wret);
 282                         wret = __free_extent(trans, extent_root,
 283                                              gang[i], 1, 0);
 284                         if (wret)
 285                                 err = wret;
 286                 }
 287         }
 288         return err;
 289 }
 290
 291 /*
 292  * remove an extent from the root, returns 0 on success
 293  */
 294 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 295                       *root, u64 blocknr, u64 num_blocks, int pin)
 296 {
 297         struct btrfs_root *extent_root = root->fs_info->extent_root;
 298         int pending_ret;
 299         int ret;
 300
 301         if (root == extent_root) {
 302                 pin_down_block(root, blocknr, 1);
 303                 return 0;
 304         }
 305         ret = __free_extent(trans, root, blocknr, num_blocks, pin);
 306         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
 307         return ret ? ret : pending_ret;
 308 }
 309
 310 /*
 311  * walks the btree of allocated extents and find a hole of a given size.
 312  * The key ins is changed to record the hole:
 313  * ins->objectid == block start
 314  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 315  * ins->offset == number of blocks
 316  * Any available blocks before search_start are skipped.
 317  */
 318 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 319                             *orig_root, u64 num_blocks, u64 search_start, u64
 320                             search_end, struct btrfs_key *ins)
 321 {
 322         struct btrfs_path path;
 323         struct btrfs_key key;
 324         int ret;
 325         u64 hole_size = 0;
 326         int slot = 0;
 327         u64 last_block = 0;
 328         u64 test_block;
 329         int start_found;
 330         struct btrfs_leaf *l;
 331         struct btrfs_root * root = orig_root->fs_info->extent_root;
 332         int total_needed = num_blocks;
 333         int level;
 334
 335         level = btrfs_header_level(btrfs_buffer_header(root->node));
 336         total_needed += (level + 1) * 3;
 337         if (root->fs_info->last_insert.objectid > search_start)
 338                 search_start = root->fs_info->last_insert.objectid;
 339
 340         ins->flags = 0;
 341         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 342
 343 check_failed:
 344         btrfs_init_path(&path);
 345         ins->objectid = search_start;
 346         ins->offset = 0;
 347         start_found = 0;
 348         ret = btrfs_search_slot(trans, root, ins, &path, 0, 0);
 349         if (ret < 0)
 350                 goto error;
 351
 352         if (path.slots[0] > 0)
 353                 path.slots[0]--;
 354
 355         while (1) {
 356                 l = btrfs_buffer_leaf(path.nodes[0]);
 357                 slot = path.slots[0];
 358                 if (slot >= btrfs_header_nritems(&l->header)) {
 359                         ret = btrfs_next_leaf(root, &path);
 360                         if (ret == 0)
 361                                 continue;
 362                         if (ret < 0)
 363                                 goto error;
 364                         if (!start_found) {
 365                                 ins->objectid = search_start;
 366                                 ins->offset = (u64)-1;
 367                                 start_found = 1;
 368                                 goto check_pending;
 369                         }
 370                         ins->objectid = last_block > search_start ?
 371                                         last_block : search_start;
 372                         ins->offset = (u64)-1;
 373                         goto check_pending;
 374                 }
 375                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
 376                 if (key.objectid >= search_start) {
 377                         if (start_found) {
 378                                 if (last_block < search_start)
 379                                         last_block = search_start;
 380                                 hole_size = key.objectid - last_block;
 381                                 if (hole_size > total_needed) {
 382                                         ins->objectid = last_block;
 383                                         ins->offset = hole_size;
 384                                         goto check_pending;
 385                                 }
 386                         }
 387                 }
 388                 start_found = 1;
 389                 last_block = key.objectid + key.offset;
 390                 path.slots[0]++;
 391         }
 392         // FIXME -ENOSPC
 393 check_pending:
 394         /* we have to make sure we didn't find an extent that has already
 395          * been allocated by the map tree or the original allocation
 396          */
 397         btrfs_release_path(root, &path);
 398         BUG_ON(ins->objectid < search_start);
 399         for (test_block = ins->objectid;
 400              test_block < ins->objectid + total_needed; test_block++) {
 401                 if (test_radix_bit(&root->fs_info->pinned_radix,
 402                                       test_block)) {
 403                         search_start = test_block + 1;
 404                         goto check_failed;
 405                 }
 406         }
 407         BUG_ON(root->fs_info->current_insert.offset);
 408         root->fs_info->current_insert.offset = total_needed - num_blocks;
 409         root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
 410         root->fs_info->current_insert.flags = 0;
 411         root->fs_info->last_insert.objectid = ins->objectid;
 412         ins->offset = num_blocks;
 413         return 0;
 414 error:
 415         btrfs_release_path(root, &path);
 416         return ret;
 417 }
 418
 419 /*
 420  * finds a free extent and does all the dirty work required for allocation
 421  * returns the key for the extent through ins, and a tree buffer for
 422  * the first block of the extent through buf.
 423  *
 424  * returns 0 if everything worked, non-zero otherwise.
 425  */
 426 int btrfs_alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 427                         *root, u64 num_blocks, u64 search_start, u64
 428                         search_end, u64 owner, struct btrfs_key *ins)
 429 {
 430         int ret;
 431         int pending_ret;
 432         u64 super_blocks_used;
 433         struct btrfs_fs_info *info = root->fs_info;
 434         struct btrfs_root *extent_root = info->extent_root;
 435         struct btrfs_extent_item extent_item;
 436
 437         btrfs_set_extent_refs(&extent_item, 1);
 438         btrfs_set_extent_owner(&extent_item, owner);
 439
 440         if (root == extent_root) {
 441                 BUG_ON(extent_root->fs_info->current_insert.offset == 0);
 442                 BUG_ON(num_blocks != 1);
 443                 BUG_ON(extent_root->fs_info->current_insert.flags ==
 444                        extent_root->fs_info->current_insert.offset);
 445                 ins->offset = 1;
 446                 ins->objectid = extent_root->fs_info->current_insert.objectid +
 447                                 extent_root->fs_info->current_insert.flags++;
 448                 return 0;
 449         }
 450         ret = find_free_extent(trans, root, num_blocks, search_start,
 451                                search_end, ins);
 452         if (ret)
 453                 return ret;
 454
 455         super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 456         btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
 457                                     num_blocks);
 458         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
 459                                 sizeof(extent_item));
 460
 461         finish_current_insert(trans, extent_root);
 462         pending_ret = del_pending_extents(trans, extent_root);
 463         if (ret)
 464                 return ret;
 465         if (pending_ret)
 466                 return pending_ret;
 467         return 0;
 468 }
 469
 470 /*
 471  * helper function to allocate a block for a given tree
 472  * returns the tree buffer or NULL.
 473  */
 474 struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
 475                                             struct btrfs_root *root)
 476 {
 477         struct btrfs_key ins;
 478         int ret;
 479         struct buffer_head *buf;
 480
 481         ret = btrfs_alloc_extent(trans, root, 1, 0, (unsigned long)-1,
 482                 btrfs_header_parentid(btrfs_buffer_header(root->node)), &ins);
 483         if (ret) {
 484                 BUG();
 485                 return NULL;
 486         }
 487         buf = btrfs_find_create_tree_block(root, ins.objectid);
 488         set_buffer_uptodate(buf);
 489         return buf;
 490 }
 491
 492 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
 493                          struct btrfs_root *root, struct buffer_head *cur)
 494 {
 495         struct btrfs_disk_key *key;
 496         struct btrfs_leaf *leaf;
 497         struct btrfs_file_extent_item *fi;
 498         int i;
 499         int nritems;
 500         int ret;
 501
 502         BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
 503         leaf = btrfs_buffer_leaf(cur);
 504         nritems = btrfs_header_nritems(&leaf->header);
 505         for (i = 0; i < nritems; i++) {
 506                 key = &leaf->items[i].key;
 507                 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
 508                         continue;
 509                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
 510                 /*
 511                  * FIXME make sure to insert a trans record that
 512                  * repeats the snapshot del on crash
 513                  */
 514                 ret = btrfs_free_extent(trans, root,
 515                                         btrfs_file_extent_disk_blocknr(fi),
 516                                         btrfs_file_extent_disk_num_blocks(fi),
 517                                         0);
 518                 BUG_ON(ret);
 519         }
 520         return 0;
 521 }
 522
 523 /*
 524  * helper function for drop_snapshot, this walks down the tree dropping ref
 525  * counts as it goes.
 526  */
 527 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 528                           *root, struct btrfs_path *path, int *level)
 529 {
 530         struct buffer_head *next;
 531         struct buffer_head *cur;
 532         u64 blocknr;
 533         int ret;
 534         u32 refs;
 535
 536         ret = lookup_block_ref(trans, root, path->nodes[*level]->b_blocknr,
 537                                1, &refs);
 538         BUG_ON(ret);
 539         if (refs > 1)
 540                 goto out;
 541         /*
 542          * walk down to the last node level and free all the leaves
 543          */
 544         while(*level >= 0) {
 545                 cur = path->nodes[*level];
 546                 if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
 547                         WARN_ON(1);
 548                 if (path->slots[*level] >=
 549                     btrfs_header_nritems(btrfs_buffer_header(cur)))
 550                         break;
 551                 if (*level == 0) {
 552                         ret = drop_leaf_ref(trans, root, cur);
 553                         BUG_ON(ret);
 554                         break;
 555                 }
 556                 blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
 557                                               path->slots[*level]);
 558                 ret = lookup_block_ref(trans, root, blocknr, 1, &refs);
 559                 BUG_ON(ret);
 560                 if (refs != 1) {
 561                         path->slots[*level]++;
 562                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
 563                         BUG_ON(ret);
 564                         continue;
 565                 }
 566                 next = read_tree_block(root, blocknr);
 567                 if (path->nodes[*level-1])
 568                         btrfs_block_release(root, path->nodes[*level-1]);
 569                 path->nodes[*level-1] = next;
 570                 *level = btrfs_header_level(btrfs_buffer_header(next));
 571                 path->slots[*level] = 0;
 572         }
 573 out:
 574         ret = btrfs_free_extent(trans, root,
 575                                 path->nodes[*level]->b_blocknr, 1, 1);
 576         btrfs_block_release(root, path->nodes[*level]);
 577         path->nodes[*level] = NULL;
 578         *level += 1;
 579         BUG_ON(ret);
 580         return 0;
 581 }
 582
 583 /*
 584  * helper for dropping snapshots.  This walks back up the tree in the path
 585  * to find the first node higher up where we haven't yet gone through
 586  * all the slots
 587  */
 588 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 589                         *root, struct btrfs_path *path, int *level)
 590 {
 591         int i;
 592         int slot;
 593         int ret;
 594         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 595                 slot = path->slots[i];
 596                 if (slot < btrfs_header_nritems(
 597                     btrfs_buffer_header(path->nodes[i])) - 1) {
 598                         path->slots[i]++;
 599                         *level = i;
 600                         return 0;
 601                 } else {
 602                         ret = btrfs_free_extent(trans, root,
 603                                                 path->nodes[*level]->b_blocknr,
 604                                                 1, 1);
 605                         BUG_ON(ret);
 606                         btrfs_block_release(root, path->nodes[*level]);
 607                         path->nodes[*level] = NULL;
 608                         *level = i + 1;
 609                 }
 610         }
 611         return 1;
 612 }
 613
 614 /*
 615  * drop the reference count on the tree rooted at 'snap'.  This traverses
 616  * the tree freeing any blocks that have a ref count of zero after being
 617  * decremented.
 618  */
 619 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
 620                         *root, struct buffer_head *snap)
 621 {
 622         int ret = 0;
 623         int wret;
 624         int level;
 625         struct btrfs_path path;
 626         int i;
 627         int orig_level;
 628
 629         btrfs_init_path(&path);
 630
 631         level = btrfs_header_level(btrfs_buffer_header(snap));
 632         orig_level = level;
 633         path.nodes[level] = snap;
 634         path.slots[level] = 0;
 635         while(1) {
 636                 wret = walk_down_tree(trans, root, &path, &level);
 637                 if (wret > 0)
 638                         break;
 639                 if (wret < 0)
 640                         ret = wret;
 641
 642                 wret = walk_up_tree(trans, root, &path, &level);
 643                 if (wret > 0)
 644                         break;
 645                 if (wret < 0)
 646                         ret = wret;
 647         }
 648         for (i = 0; i <= orig_level; i++) {
 649                 if (path.nodes[i]) {
 650                         btrfs_block_release(root, path.nodes[i]);
 651                 }
 652         }
 653         return ret;
 654 }