fs/btrfs/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 <linux/sched.h>
  20 #include "ctree.h"
  21 #include "disk-io.h"
  22 #include "print-tree.h"
  23 #include "transaction.h"
  24
  25 #define BLOCK_GROUP_DATA EXTENT_WRITEBACK
  26 #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
  27 #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
  28
  29 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  30                                  btrfs_root *extent_root);
  31 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  32                                btrfs_root *extent_root);
  33
  34 static int cache_block_group(struct btrfs_root *root,
  35                              struct btrfs_block_group_cache *block_group)
  36 {
  37         struct btrfs_path *path;
  38         int ret;
  39         struct btrfs_key key;
  40         struct extent_buffer *leaf;
  41         struct extent_map_tree *free_space_cache;
  42         int slot;
  43         u64 last = 0;
  44         u64 hole_size;
  45         u64 first_free;
  46         int found = 0;
  47
  48         root = root->fs_info->extent_root;
  49         free_space_cache = &root->fs_info->free_space_cache;
  50
  51         if (block_group->cached)
  52                 return 0;
  53
  54         path = btrfs_alloc_path();
  55         if (!path)
  56                 return -ENOMEM;
  57
  58         path->reada = 2;
  59         first_free = block_group->key.objectid;
  60         key.objectid = block_group->key.objectid;
  61         key.offset = 0;
  62
  63         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  64         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  65
  66         if (ret < 0)
  67                 return ret;
  68
  69         if (ret && path->slots[0] > 0)
  70                 path->slots[0]--;
  71
  72         while(1) {
  73                 leaf = path->nodes[0];
  74                 slot = path->slots[0];
  75                 if (slot >= btrfs_header_nritems(leaf)) {
  76                         ret = btrfs_next_leaf(root, path);
  77                         if (ret < 0)
  78                                 goto err;
  79                         if (ret == 0) {
  80                                 continue;
  81                         } else {
  82                                 break;
  83                         }
  84                 }
  85
  86                 btrfs_item_key_to_cpu(leaf, &key, slot);
  87                 if (key.objectid < block_group->key.objectid) {
  88                         if (key.objectid + key.offset > first_free)
  89                                 first_free = key.objectid + key.offset;
  90                         goto next;
  91                 }
  92
  93                 if (key.objectid >= block_group->key.objectid +
  94                     block_group->key.offset) {
  95                         break;
  96                 }
  97
  98                 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
  99                         if (!found) {
 100                                 last = first_free;
 101                                 found = 1;
 102                         }
 103                         if (key.objectid > last) {
 104                                 hole_size = key.objectid - last;
 105                                 set_extent_dirty(free_space_cache, last,
 106                                                  last + hole_size - 1,
 107                                                  GFP_NOFS);
 108                         }
 109                         last = key.objectid + key.offset;
 110                 }
 111 next:
 112                 path->slots[0]++;
 113         }
 114
 115         if (!found)
 116                 last = first_free;
 117         if (block_group->key.objectid +
 118             block_group->key.offset > last) {
 119                 hole_size = block_group->key.objectid +
 120                         block_group->key.offset - last;
 121                 set_extent_dirty(free_space_cache, last,
 122                                  last + hole_size - 1, GFP_NOFS);
 123         }
 124         block_group->cached = 1;
 125 err:
 126         btrfs_free_path(path);
 127         return 0;
 128 }
 129
 130 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 131                                                          btrfs_fs_info *info,
 132                                                          u64 bytenr)
 133 {
 134         struct extent_map_tree *block_group_cache;
 135         struct btrfs_block_group_cache *block_group = NULL;
 136         u64 ptr;
 137         u64 start;
 138         u64 end;
 139         int ret;
 140
 141         block_group_cache = &info->block_group_cache;
 142         ret = find_first_extent_bit(block_group_cache,
 143                                     bytenr, &start, &end,
 144                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA);
 145         if (ret) {
 146                 return NULL;
 147         }
 148         ret = get_state_private(block_group_cache, start, &ptr);
 149         if (ret)
 150                 return NULL;
 151
 152         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 153
 154
 155         if (block_group->key.objectid <= bytenr && bytenr <=
 156             block_group->key.objectid + block_group->key.offset)
 157                 return block_group;
 158
 159         return NULL;
 160 }
 161 static u64 find_search_start(struct btrfs_root *root,
 162                              struct btrfs_block_group_cache **cache_ret,
 163                              u64 search_start, int num,
 164                              int data, int full_scan)
 165 {
 166         int ret;
 167         struct btrfs_block_group_cache *cache = *cache_ret;
 168         u64 last;
 169         u64 start = 0;
 170         u64 end = 0;
 171         u64 cache_miss = 0;
 172         int wrapped = 0;
 173
 174 again:
 175         ret = cache_block_group(root, cache);
 176         if (ret)
 177                 goto out;
 178
 179         last = max(search_start, cache->key.objectid);
 180
 181         while(1) {
 182                 ret = find_first_extent_bit(&root->fs_info->free_space_cache,
 183                                             last, &start, &end, EXTENT_DIRTY);
 184                 if (ret) {
 185                         if (!cache_miss)
 186                                 cache_miss = last;
 187                         goto new_group;
 188                 }
 189
 190                 start = max(last, start);
 191                 last = end + 1;
 192                 if (last - start < num) {
 193                         if (last == cache->key.objectid + cache->key.offset)
 194                                 cache_miss = start;
 195                         continue;
 196                 }
 197                 if (data != BTRFS_BLOCK_GROUP_MIXED &&
 198                     start + num >= cache->key.objectid + cache->key.offset)
 199                         goto new_group;
 200                 return start;
 201         }
 202 out:
 203         return search_start;
 204
 205 new_group:
 206         last = cache->key.objectid + cache->key.offset;
 207 wrapped:
 208         cache = btrfs_lookup_block_group(root->fs_info, last);
 209         if (!cache) {
 210                 if (!wrapped) {
 211                         wrapped = 1;
 212                         last = search_start;
 213                         data = BTRFS_BLOCK_GROUP_MIXED;
 214                         goto wrapped;
 215                 }
 216                 return search_start;
 217         }
 218         if (cache_miss && !cache->cached) {
 219                 cache_block_group(root, cache);
 220                 last = cache_miss;
 221                 cache = btrfs_lookup_block_group(root->fs_info, last);
 222         }
 223         if (!full_scan)
 224                 cache = btrfs_find_block_group(root, cache, last, data, 0);
 225         *cache_ret = cache;
 226         cache_miss = 0;
 227         goto again;
 228 }
 229
 230 static u64 div_factor(u64 num, int factor)
 231 {
 232         if (factor == 10)
 233                 return num;
 234         num *= factor;
 235         do_div(num, 10);
 236         return num;
 237 }
 238
 239 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 240                                                  struct btrfs_block_group_cache
 241                                                  *hint, u64 search_start,
 242                                                  int data, int owner)
 243 {
 244         struct btrfs_block_group_cache *cache;
 245         struct extent_map_tree *block_group_cache;
 246         struct btrfs_block_group_cache *found_group = NULL;
 247         struct btrfs_fs_info *info = root->fs_info;
 248         u64 used;
 249         u64 last = 0;
 250         u64 hint_last;
 251         u64 start;
 252         u64 end;
 253         u64 free_check;
 254         u64 ptr;
 255         int bit;
 256         int ret;
 257         int full_search = 0;
 258         int factor = 8;
 259         int data_swap = 0;
 260
 261         block_group_cache = &info->block_group_cache;
 262
 263         if (!owner)
 264                 factor = 8;
 265
 266         if (data == BTRFS_BLOCK_GROUP_MIXED) {
 267                 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
 268                 factor = 10;
 269         } else if (data)
 270                 bit = BLOCK_GROUP_DATA;
 271         else
 272                 bit = BLOCK_GROUP_METADATA;
 273
 274         if (search_start) {
 275                 struct btrfs_block_group_cache *shint;
 276                 shint = btrfs_lookup_block_group(info, search_start);
 277                 if (shint && (shint->data == data ||
 278                               shint->data == BTRFS_BLOCK_GROUP_MIXED)) {
 279                         used = btrfs_block_group_used(&shint->item);
 280                         if (used + shint->pinned <
 281                             div_factor(shint->key.offset, factor)) {
 282                                 return shint;
 283                         }
 284                 }
 285         }
 286         if (hint && (hint->data == data ||
 287                      hint->data == BTRFS_BLOCK_GROUP_MIXED)) {
 288                 used = btrfs_block_group_used(&hint->item);
 289                 if (used + hint->pinned <
 290                     div_factor(hint->key.offset, factor)) {
 291                         return hint;
 292                 }
 293                 last = hint->key.objectid + hint->key.offset;
 294                 hint_last = last;
 295         } else {
 296                 if (hint)
 297                         hint_last = max(hint->key.objectid, search_start);
 298                 else
 299                         hint_last = search_start;
 300
 301                 last = hint_last;
 302         }
 303 again:
 304         while(1) {
 305                 ret = find_first_extent_bit(block_group_cache, last,
 306                                             &start, &end, bit);
 307                 if (ret)
 308                         break;
 309
 310                 ret = get_state_private(block_group_cache, start, &ptr);
 311                 if (ret)
 312                         break;
 313
 314                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 315                 last = cache->key.objectid + cache->key.offset;
 316                 used = btrfs_block_group_used(&cache->item);
 317
 318                 if (full_search)
 319                         free_check = cache->key.offset;
 320                 else
 321                         free_check = div_factor(cache->key.offset, factor);
 322                 if (used + cache->pinned < free_check) {
 323                         found_group = cache;
 324                         goto found;
 325                 }
 326                 cond_resched();
 327         }
 328         if (!full_search) {
 329                 last = search_start;
 330                 full_search = 1;
 331                 goto again;
 332         }
 333         if (!data_swap) {
 334                 data_swap = 1;
 335                 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
 336                 last = search_start;
 337                 goto again;
 338         }
 339 found:
 340         return found_group;
 341 }
 342
 343 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 344                                 struct btrfs_root *root,
 345                                 u64 bytenr, u64 num_bytes)
 346 {
 347         struct btrfs_path *path;
 348         int ret;
 349         struct btrfs_key key;
 350         struct extent_buffer *l;
 351         struct btrfs_extent_item *item;
 352         u32 refs;
 353
 354         WARN_ON(num_bytes < root->sectorsize);
 355         path = btrfs_alloc_path();
 356         if (!path)
 357                 return -ENOMEM;
 358
 359         key.objectid = bytenr;
 360         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 361         key.offset = num_bytes;
 362         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 363                                 0, 1);
 364         if (ret < 0)
 365                 return ret;
 366         if (ret != 0) {
 367                 BUG();
 368         }
 369         BUG_ON(ret != 0);
 370         l = path->nodes[0];
 371         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 372         refs = btrfs_extent_refs(l, item);
 373         btrfs_set_extent_refs(l, item, refs + 1);
 374         btrfs_mark_buffer_dirty(path->nodes[0]);
 375
 376         btrfs_release_path(root->fs_info->extent_root, path);
 377         btrfs_free_path(path);
 378         finish_current_insert(trans, root->fs_info->extent_root);
 379         del_pending_extents(trans, root->fs_info->extent_root);
 380         return 0;
 381 }
 382
 383 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
 384                          struct btrfs_root *root)
 385 {
 386         finish_current_insert(trans, root->fs_info->extent_root);
 387         del_pending_extents(trans, root->fs_info->extent_root);
 388         return 0;
 389 }
 390
 391 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
 392                              struct btrfs_root *root, u64 bytenr,
 393                              u64 num_bytes, u32 *refs)
 394 {
 395         struct btrfs_path *path;
 396         int ret;
 397         struct btrfs_key key;
 398         struct extent_buffer *l;
 399         struct btrfs_extent_item *item;
 400
 401         WARN_ON(num_bytes < root->sectorsize);
 402         path = btrfs_alloc_path();
 403         key.objectid = bytenr;
 404         key.offset = num_bytes;
 405         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 406         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 407                                 0, 0);
 408         if (ret < 0)
 409                 goto out;
 410         if (ret != 0) {
 411                 btrfs_print_leaf(root, path->nodes[0]);
 412                 printk("failed to find block number %Lu\n", bytenr);
 413                 BUG();
 414         }
 415         l = path->nodes[0];
 416         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 417         *refs = btrfs_extent_refs(l, item);
 418 out:
 419         btrfs_free_path(path);
 420         return 0;
 421 }
 422
 423 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
 424                        struct btrfs_root *root)
 425 {
 426         return btrfs_inc_extent_ref(trans, root, root->node->start,
 427                                     root->node->len);
 428 }
 429
 430 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 431                   struct extent_buffer *buf)
 432 {
 433         u64 bytenr;
 434         u32 nritems;
 435         struct btrfs_key key;
 436         struct btrfs_file_extent_item *fi;
 437         int i;
 438         int level;
 439         int ret;
 440         int faili;
 441         int err;
 442
 443         if (!root->ref_cows)
 444                 return 0;
 445
 446         level = btrfs_header_level(buf);
 447         nritems = btrfs_header_nritems(buf);
 448         for (i = 0; i < nritems; i++) {
 449                 if (level == 0) {
 450                         u64 disk_bytenr;
 451                         btrfs_item_key_to_cpu(buf, &key, i);
 452                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
 453                                 continue;
 454                         fi = btrfs_item_ptr(buf, i,
 455                                             struct btrfs_file_extent_item);
 456                         if (btrfs_file_extent_type(buf, fi) ==
 457                             BTRFS_FILE_EXTENT_INLINE)
 458                                 continue;
 459                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
 460                         if (disk_bytenr == 0)
 461                                 continue;
 462                         ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
 463                                     btrfs_file_extent_disk_num_bytes(buf, fi));
 464                         if (ret) {
 465                                 faili = i;
 466                                 goto fail;
 467                         }
 468                 } else {
 469                         bytenr = btrfs_node_blockptr(buf, i);
 470                         ret = btrfs_inc_extent_ref(trans, root, bytenr,
 471                                            btrfs_level_size(root, level - 1));
 472                         if (ret) {
 473                                 faili = i;
 474                                 goto fail;
 475                         }
 476                 }
 477         }
 478         return 0;
 479 fail:
 480         WARN_ON(1);
 481         for (i =0; i < faili; i++) {
 482                 if (level == 0) {
 483                         u64 disk_bytenr;
 484                         btrfs_item_key_to_cpu(buf, &key, i);
 485                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
 486                                 continue;
 487                         fi = btrfs_item_ptr(buf, i,
 488                                             struct btrfs_file_extent_item);
 489                         if (btrfs_file_extent_type(buf, fi) ==
 490                             BTRFS_FILE_EXTENT_INLINE)
 491                                 continue;
 492                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
 493                         if (disk_bytenr == 0)
 494                                 continue;
 495                         err = btrfs_free_extent(trans, root, disk_bytenr,
 496                                     btrfs_file_extent_disk_num_bytes(buf,
 497                                                                       fi), 0);
 498                         BUG_ON(err);
 499                 } else {
 500                         bytenr = btrfs_node_blockptr(buf, i);
 501                         err = btrfs_free_extent(trans, root, bytenr,
 502                                         btrfs_level_size(root, level - 1), 0);
 503                         BUG_ON(err);
 504                 }
 505         }
 506         return ret;
 507 }
 508
 509 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 510                                  struct btrfs_root *root,
 511                                  struct btrfs_path *path,
 512                                  struct btrfs_block_group_cache *cache)
 513 {
 514         int ret;
 515         int pending_ret;
 516         struct btrfs_root *extent_root = root->fs_info->extent_root;
 517         unsigned long bi;
 518         struct extent_buffer *leaf;
 519
 520         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 521         if (ret < 0)
 522                 goto fail;
 523         BUG_ON(ret);
 524
 525         leaf = path->nodes[0];
 526         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
 527         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
 528         btrfs_mark_buffer_dirty(leaf);
 529         btrfs_release_path(extent_root, path);
 530 fail:
 531         finish_current_insert(trans, extent_root);
 532         pending_ret = del_pending_extents(trans, extent_root);
 533         if (ret)
 534                 return ret;
 535         if (pending_ret)
 536                 return pending_ret;
 537         return 0;
 538
 539 }
 540
 541 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 542                                    struct btrfs_root *root)
 543 {
 544         struct extent_map_tree *block_group_cache;
 545         struct btrfs_block_group_cache *cache;
 546         int ret;
 547         int err = 0;
 548         int werr = 0;
 549         struct btrfs_path *path;
 550         u64 last = 0;
 551         u64 start;
 552         u64 end;
 553         u64 ptr;
 554
 555         block_group_cache = &root->fs_info->block_group_cache;
 556         path = btrfs_alloc_path();
 557         if (!path)
 558                 return -ENOMEM;
 559
 560         while(1) {
 561                 ret = find_first_extent_bit(block_group_cache, last,
 562                                             &start, &end, BLOCK_GROUP_DIRTY);
 563                 if (ret)
 564                         break;
 565
 566                 last = end + 1;
 567                 ret = get_state_private(block_group_cache, start, &ptr);
 568                 if (ret)
 569                         break;
 570
 571                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 572                 err = write_one_cache_group(trans, root,
 573                                             path, cache);
 574                 /*
 575                  * if we fail to write the cache group, we want
 576                  * to keep it marked dirty in hopes that a later
 577                  * write will work
 578                  */
 579                 if (err) {
 580                         werr = err;
 581                         continue;
 582                 }
 583                 clear_extent_bits(block_group_cache, start, end,
 584                                   BLOCK_GROUP_DIRTY, GFP_NOFS);
 585         }
 586         btrfs_free_path(path);
 587         return werr;
 588 }
 589
 590 static int update_block_group(struct btrfs_trans_handle *trans,
 591                               struct btrfs_root *root,
 592                               u64 bytenr, u64 num_bytes, int alloc,
 593                               int mark_free, int data)
 594 {
 595         struct btrfs_block_group_cache *cache;
 596         struct btrfs_fs_info *info = root->fs_info;
 597         u64 total = num_bytes;
 598         u64 old_val;
 599         u64 byte_in_group;
 600         u64 start;
 601         u64 end;
 602
 603         while(total) {
 604                 cache = btrfs_lookup_block_group(info, bytenr);
 605                 if (!cache) {
 606                         return -1;
 607                 }
 608                 byte_in_group = bytenr - cache->key.objectid;
 609                 WARN_ON(byte_in_group > cache->key.offset);
 610                 start = cache->key.objectid;
 611                 end = start + cache->key.offset - 1;
 612                 set_extent_bits(&info->block_group_cache, start, end,
 613                                 BLOCK_GROUP_DIRTY, GFP_NOFS);
 614
 615                 old_val = btrfs_block_group_used(&cache->item);
 616                 num_bytes = min(total, cache->key.offset - byte_in_group);
 617                 if (alloc) {
 618                         if (cache->data != data &&
 619                             old_val < (cache->key.offset >> 1)) {
 620                                 int bit_to_clear;
 621                                 int bit_to_set;
 622                                 cache->data = data;
 623                                 if (data) {
 624                                         bit_to_clear = BLOCK_GROUP_METADATA;
 625                                         bit_to_set = BLOCK_GROUP_DATA;
 626                                         cache->item.flags &=
 627                                                 ~BTRFS_BLOCK_GROUP_MIXED;
 628                                         cache->item.flags |=
 629                                                 BTRFS_BLOCK_GROUP_DATA;
 630                                 } else {
 631                                         bit_to_clear = BLOCK_GROUP_DATA;
 632                                         bit_to_set = BLOCK_GROUP_METADATA;
 633                                         cache->item.flags &=
 634                                                 ~BTRFS_BLOCK_GROUP_MIXED;
 635                                         cache->item.flags &=
 636                                                 ~BTRFS_BLOCK_GROUP_DATA;
 637                                 }
 638                                 clear_extent_bits(&info->block_group_cache,
 639                                                   start, end, bit_to_clear,
 640                                                   GFP_NOFS);
 641                                 set_extent_bits(&info->block_group_cache,
 642                                                 start, end, bit_to_set,
 643                                                 GFP_NOFS);
 644                         } else if (cache->data != data &&
 645                                    cache->data != BTRFS_BLOCK_GROUP_MIXED) {
 646                                 cache->data = BTRFS_BLOCK_GROUP_MIXED;
 647                                 set_extent_bits(&info->block_group_cache,
 648                                                 start, end,
 649                                                 BLOCK_GROUP_DATA |
 650                                                 BLOCK_GROUP_METADATA,
 651                                                 GFP_NOFS);
 652                         }
 653                         old_val += num_bytes;
 654                 } else {
 655                         old_val -= num_bytes;
 656                         if (mark_free) {
 657                                 set_extent_dirty(&info->free_space_cache,
 658                                                  bytenr, bytenr + num_bytes - 1,
 659                                                  GFP_NOFS);
 660                         }
 661                 }
 662                 btrfs_set_block_group_used(&cache->item, old_val);
 663                 total -= num_bytes;
 664                 bytenr += num_bytes;
 665         }
 666         return 0;
 667 }
 668 static int update_pinned_extents(struct btrfs_root *root,
 669                                 u64 bytenr, u64 num, int pin)
 670 {
 671         u64 len;
 672         struct btrfs_block_group_cache *cache;
 673         struct btrfs_fs_info *fs_info = root->fs_info;
 674
 675         if (pin) {
 676                 set_extent_dirty(&fs_info->pinned_extents,
 677                                 bytenr, bytenr + num - 1, GFP_NOFS);
 678         } else {
 679                 clear_extent_dirty(&fs_info->pinned_extents,
 680                                 bytenr, bytenr + num - 1, GFP_NOFS);
 681         }
 682         while (num > 0) {
 683                 cache = btrfs_lookup_block_group(fs_info, bytenr);
 684                 WARN_ON(!cache);
 685                 len = min(num, cache->key.offset -
 686                           (bytenr - cache->key.objectid));
 687                 if (pin) {
 688                         cache->pinned += len;
 689                         fs_info->total_pinned += len;
 690                 } else {
 691                         cache->pinned -= len;
 692                         fs_info->total_pinned -= len;
 693                 }
 694                 bytenr += len;
 695                 num -= len;
 696         }
 697         return 0;
 698 }
 699
 700 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_map_tree *copy)
 701 {
 702         u64 last = 0;
 703         u64 start;
 704         u64 end;
 705         struct extent_map_tree *pinned_extents = &root->fs_info->pinned_extents;
 706         int ret;
 707
 708         while(1) {
 709                 ret = find_first_extent_bit(pinned_extents, last,
 710                                             &start, &end, EXTENT_DIRTY);
 711                 if (ret)
 712                         break;
 713                 set_extent_dirty(copy, start, end, GFP_NOFS);
 714                 last = end + 1;
 715         }
 716         return 0;
 717 }
 718
 719 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
 720                                struct btrfs_root *root,
 721                                struct extent_map_tree *unpin)
 722 {
 723         u64 start;
 724         u64 end;
 725         int ret;
 726         struct extent_map_tree *free_space_cache;
 727         free_space_cache = &root->fs_info->free_space_cache;
 728
 729         while(1) {
 730                 ret = find_first_extent_bit(unpin, 0, &start, &end,
 731                                             EXTENT_DIRTY);
 732                 if (ret)
 733                         break;
 734                 update_pinned_extents(root, start, end + 1 - start, 0);
 735                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
 736                 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
 737         }
 738         return 0;
 739 }
 740
 741 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 742                                  btrfs_root *extent_root)
 743 {
 744         struct btrfs_key ins;
 745         struct btrfs_extent_item extent_item;
 746         int ret;
 747         int err = 0;
 748         u64 start;
 749         u64 end;
 750         struct btrfs_fs_info *info = extent_root->fs_info;
 751
 752         btrfs_set_stack_extent_refs(&extent_item, 1);
 753         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 754         btrfs_set_stack_extent_owner(&extent_item,
 755                                      extent_root->root_key.objectid);
 756
 757         while(1) {
 758                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
 759                                             &end, EXTENT_LOCKED);
 760                 if (ret)
 761                         break;
 762
 763                 ins.objectid = start;
 764                 ins.offset = end + 1 - start;
 765                 err = btrfs_insert_item(trans, extent_root, &ins,
 766                                         &extent_item, sizeof(extent_item));
 767                 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
 768                                   GFP_NOFS);
 769         }
 770         return 0;
 771 }
 772
 773 static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
 774                           int pending)
 775 {
 776         int err = 0;
 777         struct extent_buffer *buf;
 778
 779         if (!pending) {
 780                 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
 781                 if (buf) {
 782                         if (btrfs_buffer_uptodate(buf)) {
 783                                 u64 transid =
 784                                     root->fs_info->running_transaction->transid;
 785                                 if (btrfs_header_generation(buf) == transid) {
 786                                         free_extent_buffer(buf);
 787                                         return 1;
 788                                 }
 789                         }
 790                         free_extent_buffer(buf);
 791                 }
 792                 update_pinned_extents(root, bytenr, num_bytes, 1);
 793         } else {
 794                 set_extent_bits(&root->fs_info->pending_del,
 795                                 bytenr, bytenr + num_bytes - 1,
 796                                 EXTENT_LOCKED, GFP_NOFS);
 797         }
 798         BUG_ON(err < 0);
 799         return 0;
 800 }
 801
 802 /*
 803  * remove an extent from the root, returns 0 on success
 804  */
 805 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 806                          *root, u64 bytenr, u64 num_bytes, int pin,
 807                          int mark_free)
 808 {
 809         struct btrfs_path *path;
 810         struct btrfs_key key;
 811         struct btrfs_fs_info *info = root->fs_info;
 812         struct btrfs_root *extent_root = info->extent_root;
 813         struct extent_buffer *leaf;
 814         int ret;
 815         struct btrfs_extent_item *ei;
 816         u32 refs;
 817
 818         key.objectid = bytenr;
 819         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 820         key.offset = num_bytes;
 821
 822         path = btrfs_alloc_path();
 823         if (!path)
 824                 return -ENOMEM;
 825
 826         ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
 827         if (ret < 0)
 828                 return ret;
 829         BUG_ON(ret);
 830
 831         leaf = path->nodes[0];
 832         ei = btrfs_item_ptr(leaf, path->slots[0],
 833                             struct btrfs_extent_item);
 834         refs = btrfs_extent_refs(leaf, ei);
 835         BUG_ON(refs == 0);
 836         refs -= 1;
 837         btrfs_set_extent_refs(leaf, ei, refs);
 838         btrfs_mark_buffer_dirty(leaf);
 839
 840         if (refs == 0) {
 841                 u64 super_used;
 842                 u64 root_used;
 843
 844                 if (pin) {
 845                         ret = pin_down_bytes(root, bytenr, num_bytes, 0);
 846                         if (ret > 0)
 847                                 mark_free = 1;
 848                         BUG_ON(ret < 0);
 849                 }
 850
 851                 /* block accounting for super block */
 852                 super_used = btrfs_super_bytes_used(&info->super_copy);
 853                 btrfs_set_super_bytes_used(&info->super_copy,
 854                                            super_used - num_bytes);
 855
 856                 /* block accounting for root item */
 857                 root_used = btrfs_root_used(&root->root_item);
 858                 btrfs_set_root_used(&root->root_item,
 859                                            root_used - num_bytes);
 860
 861                 ret = btrfs_del_item(trans, extent_root, path);
 862                 if (ret) {
 863                         return ret;
 864                 }
 865                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
 866                                          mark_free, 0);
 867                 BUG_ON(ret);
 868         }
 869         btrfs_free_path(path);
 870         finish_current_insert(trans, extent_root);
 871         return ret;
 872 }
 873
 874 /*
 875  * find all the blocks marked as pending in the radix tree and remove
 876  * them from the extent map
 877  */
 878 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 879                                btrfs_root *extent_root)
 880 {
 881         int ret;
 882         int err = 0;
 883         u64 start;
 884         u64 end;
 885         struct extent_map_tree *pending_del;
 886         struct extent_map_tree *pinned_extents;
 887
 888         pending_del = &extent_root->fs_info->pending_del;
 889         pinned_extents = &extent_root->fs_info->pinned_extents;
 890
 891         while(1) {
 892                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
 893                                             EXTENT_LOCKED);
 894                 if (ret)
 895                         break;
 896                 update_pinned_extents(extent_root, start, end + 1 - start, 1);
 897                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
 898                                   GFP_NOFS);
 899                 ret = __free_extent(trans, extent_root,
 900                                      start, end + 1 - start, 0, 0);
 901                 if (ret)
 902                         err = ret;
 903         }
 904         return err;
 905 }
 906
 907 /*
 908  * remove an extent from the root, returns 0 on success
 909  */
 910 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 911                       *root, u64 bytenr, u64 num_bytes, int pin)
 912 {
 913         struct btrfs_root *extent_root = root->fs_info->extent_root;
 914         int pending_ret;
 915         int ret;
 916
 917         WARN_ON(num_bytes < root->sectorsize);
 918         if (root == extent_root) {
 919                 pin_down_bytes(root, bytenr, num_bytes, 1);
 920                 return 0;
 921         }
 922         ret = __free_extent(trans, root, bytenr, num_bytes, pin, pin == 0);
 923         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
 924         return ret ? ret : pending_ret;
 925 }
 926
 927 /*
 928  * walks the btree of allocated extents and find a hole of a given size.
 929  * The key ins is changed to record the hole:
 930  * ins->objectid == block start
 931  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 932  * ins->offset == number of blocks
 933  * Any available blocks before search_start are skipped.
 934  */
 935 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 936                             *orig_root, u64 num_bytes, u64 empty_size,
 937                             u64 search_start, u64 search_end, u64 hint_byte,
 938                             struct btrfs_key *ins, u64 exclude_start,
 939                             u64 exclude_nr, int data)
 940 {
 941         struct btrfs_path *path;
 942         struct btrfs_key key;
 943         int ret;
 944         u64 hole_size = 0;
 945         int slot = 0;
 946         u64 last_byte = 0;
 947         u64 orig_search_start = search_start;
 948         int start_found;
 949         struct extent_buffer *l;
 950         struct btrfs_root * root = orig_root->fs_info->extent_root;
 951         struct btrfs_fs_info *info = root->fs_info;
 952         u64 total_needed = num_bytes;
 953         int level;
 954         struct btrfs_block_group_cache *block_group;
 955         int full_scan = 0;
 956         int wrapped = 0;
 957         u64 cached_start;
 958
 959         WARN_ON(num_bytes < root->sectorsize);
 960         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 961
 962         level = btrfs_header_level(root->node);
 963
 964         if (num_bytes >= 96 * 1024 * 1024 && hint_byte) {
 965                 data = BTRFS_BLOCK_GROUP_MIXED;
 966         }
 967
 968         if (search_end == (u64)-1)
 969                 search_end = btrfs_super_total_bytes(&info->super_copy);
 970         if (hint_byte) {
 971                 block_group = btrfs_lookup_block_group(info, hint_byte);
 972                 block_group = btrfs_find_block_group(root, block_group,
 973                                                      hint_byte, data, 1);
 974         } else {
 975                 block_group = btrfs_find_block_group(root,
 976                                                      trans->block_group, 0,
 977                                                      data, 1);
 978         }
 979
 980         total_needed += empty_size;
 981         path = btrfs_alloc_path();
 982 check_failed:
 983         search_start = find_search_start(root, &block_group, search_start,
 984                                          total_needed, data, full_scan);
 985         cached_start = search_start;
 986         btrfs_init_path(path);
 987         ins->objectid = search_start;
 988         ins->offset = 0;
 989         start_found = 0;
 990         path->reada = 2;
 991
 992         ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
 993         if (ret < 0)
 994                 goto error;
 995
 996         if (path->slots[0] > 0) {
 997                 path->slots[0]--;
 998         }
 999
1000         l = path->nodes[0];
1001         btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1002
1003         /*
1004          * a rare case, go back one key if we hit a block group item
1005          * instead of an extent item
1006          */
1007         if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
1008             key.objectid + key.offset >= search_start) {
1009                 ins->objectid = key.objectid;
1010                 ins->offset = key.offset - 1;
1011                 btrfs_release_path(root, path);
1012                 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1013                 if (ret < 0)
1014                         goto error;
1015
1016                 if (path->slots[0] > 0) {
1017                         path->slots[0]--;
1018                 }
1019         }
1020
1021         while (1) {
1022                 l = path->nodes[0];
1023                 slot = path->slots[0];
1024                 if (slot >= btrfs_header_nritems(l)) {
1025                         ret = btrfs_next_leaf(root, path);
1026                         if (ret == 0)
1027                                 continue;
1028                         if (ret < 0)
1029                                 goto error;
1030
1031                         search_start = max(search_start,
1032                                            block_group->key.objectid);
1033                         if (!start_found) {
1034                                 ins->objectid = search_start;
1035                                 ins->offset = search_end - search_start;
1036                                 start_found = 1;
1037                                 goto check_pending;
1038                         }
1039                         ins->objectid = last_byte > search_start ?
1040                                         last_byte : search_start;
1041                         ins->offset = search_end - ins->objectid;
1042                         BUG_ON(ins->objectid >= search_end);
1043                         goto check_pending;
1044                 }
1045                 btrfs_item_key_to_cpu(l, &key, slot);
1046
1047                 if (key.objectid >= search_start && key.objectid > last_byte &&
1048                     start_found) {
1049                         if (last_byte < search_start)
1050                                 last_byte = search_start;
1051                         hole_size = key.objectid - last_byte;
1052                         if (hole_size >= num_bytes) {
1053                                 ins->objectid = last_byte;
1054                                 ins->offset = hole_size;
1055                                 goto check_pending;
1056                         }
1057                 }
1058                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
1059                         if (!start_found) {
1060                                 last_byte = key.objectid;
1061                                 start_found = 1;
1062                         }
1063                         goto next;
1064                 }
1065
1066
1067                 start_found = 1;
1068                 last_byte = key.objectid + key.offset;
1069
1070                 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1071                     last_byte >= block_group->key.objectid +
1072                     block_group->key.offset) {
1073                         btrfs_release_path(root, path);
1074                         search_start = block_group->key.objectid +
1075                                 block_group->key.offset;
1076                         goto new_group;
1077                 }
1078 next:
1079                 path->slots[0]++;
1080                 cond_resched();
1081         }
1082 check_pending:
1083         /* we have to make sure we didn't find an extent that has already
1084          * been allocated by the map tree or the original allocation
1085          */
1086         btrfs_release_path(root, path);
1087         BUG_ON(ins->objectid < search_start);
1088
1089         if (ins->objectid + num_bytes >= search_end)
1090                 goto enospc;
1091
1092         if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1093             ins->objectid + num_bytes >= block_group->
1094             key.objectid + block_group->key.offset) {
1095                 search_start = block_group->key.objectid +
1096                         block_group->key.offset;
1097                 goto new_group;
1098         }
1099         if (test_range_bit(&info->extent_ins, ins->objectid,
1100                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1101                 search_start = ins->objectid + num_bytes;
1102                 goto new_group;
1103         }
1104         if (test_range_bit(&info->pinned_extents, ins->objectid,
1105                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1106                 search_start = ins->objectid + num_bytes;
1107                 goto new_group;
1108         }
1109         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1110             ins->objectid < exclude_start + exclude_nr)) {
1111                 search_start = exclude_start + exclude_nr;
1112                 goto new_group;
1113         }
1114         if (!data) {
1115                 block_group = btrfs_lookup_block_group(info, ins->objectid);
1116                 if (block_group)
1117                         trans->block_group = block_group;
1118         }
1119         ins->offset = num_bytes;
1120         btrfs_free_path(path);
1121         return 0;
1122
1123 new_group:
1124         if (search_start + num_bytes >= search_end) {
1125 enospc:
1126                 search_start = orig_search_start;
1127                 if (full_scan) {
1128                         ret = -ENOSPC;
1129                         goto error;
1130                 }
1131                 if (wrapped) {
1132                         if (!full_scan)
1133                                 total_needed -= empty_size;
1134                         full_scan = 1;
1135                 } else
1136                         wrapped = 1;
1137         }
1138         block_group = btrfs_lookup_block_group(info, search_start);
1139         cond_resched();
1140         if (!full_scan)
1141                 block_group = btrfs_find_block_group(root, block_group,
1142                                                      search_start, data, 0);
1143         goto check_failed;
1144
1145 error:
1146         btrfs_release_path(root, path);
1147         btrfs_free_path(path);
1148         return ret;
1149 }
1150 /*
1151  * finds a free extent and does all the dirty work required for allocation
1152  * returns the key for the extent through ins, and a tree buffer for
1153  * the first block of the extent through buf.
1154  *
1155  * returns 0 if everything worked, non-zero otherwise.
1156  */
1157 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1158                        struct btrfs_root *root, u64 owner,
1159                        u64 num_bytes, u64 empty_size, u64 hint_byte,
1160                        u64 search_end, struct btrfs_key *ins, int data)
1161 {
1162         int ret;
1163         int pending_ret;
1164         u64 super_used, root_used;
1165         u64 search_start = 0;
1166         struct btrfs_fs_info *info = root->fs_info;
1167         struct btrfs_root *extent_root = info->extent_root;
1168         struct btrfs_extent_item extent_item;
1169
1170         btrfs_set_stack_extent_refs(&extent_item, 1);
1171         btrfs_set_stack_extent_owner(&extent_item, owner);
1172
1173         WARN_ON(num_bytes < root->sectorsize);
1174         ret = find_free_extent(trans, root, num_bytes, empty_size,
1175                                search_start, search_end, hint_byte, ins,
1176                                trans->alloc_exclude_start,
1177                                trans->alloc_exclude_nr, data);
1178         BUG_ON(ret);
1179         if (ret)
1180                 return ret;
1181
1182         /* block accounting for super block */
1183         super_used = btrfs_super_bytes_used(&info->super_copy);
1184         btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1185
1186         /* block accounting for root item */
1187         root_used = btrfs_root_used(&root->root_item);
1188         btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1189
1190         clear_extent_dirty(&root->fs_info->free_space_cache,
1191                            ins->objectid, ins->objectid + ins->offset - 1,
1192                            GFP_NOFS);
1193
1194         if (root == extent_root) {
1195                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1196                                 ins->objectid + ins->offset - 1,
1197                                 EXTENT_LOCKED, GFP_NOFS);
1198                 WARN_ON(data == 1);
1199                 goto update_block;
1200         }
1201
1202         WARN_ON(trans->alloc_exclude_nr);
1203         trans->alloc_exclude_start = ins->objectid;
1204         trans->alloc_exclude_nr = ins->offset;
1205         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1206                                 sizeof(extent_item));
1207
1208         trans->alloc_exclude_start = 0;
1209         trans->alloc_exclude_nr = 0;
1210
1211         BUG_ON(ret);
1212         finish_current_insert(trans, extent_root);
1213         pending_ret = del_pending_extents(trans, extent_root);
1214
1215         if (ret) {
1216                 return ret;
1217         }
1218         if (pending_ret) {
1219                 return pending_ret;
1220         }
1221
1222 update_block:
1223         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1224                                  data);
1225         BUG_ON(ret);
1226         return 0;
1227 }
1228
1229 /*
1230  * helper function to allocate a block for a given tree
1231  * returns the tree buffer or NULL.
1232  */
1233 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1234                                              struct btrfs_root *root,
1235                                              u32 blocksize, u64 hint,
1236                                              u64 empty_size)
1237 {
1238         struct btrfs_key ins;
1239         int ret;
1240         struct extent_buffer *buf;
1241
1242         ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1243                                  blocksize, empty_size, hint,
1244                                  (u64)-1, &ins, 0);
1245         if (ret) {
1246                 BUG_ON(ret > 0);
1247                 return ERR_PTR(ret);
1248         }
1249         buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1250         if (!buf) {
1251                 btrfs_free_extent(trans, root, ins.objectid, blocksize, 0);
1252                 return ERR_PTR(-ENOMEM);
1253         }
1254         btrfs_set_buffer_uptodate(buf);
1255         set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1256                          buf->start + buf->len - 1, GFP_NOFS);
1257         set_extent_bits(&BTRFS_I(root->fs_info->btree_inode)->extent_tree,
1258                         buf->start, buf->start + buf->len - 1,
1259                         EXTENT_CSUM, GFP_NOFS);
1260         buf->flags |= EXTENT_CSUM;
1261         btrfs_set_buffer_defrag(buf);
1262         trans->blocks_used++;
1263         return buf;
1264 }
1265
1266 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
1267                          struct btrfs_root *root, struct extent_buffer *leaf)
1268 {
1269         struct btrfs_key key;
1270         struct btrfs_file_extent_item *fi;
1271         int i;
1272         int nritems;
1273         int ret;
1274
1275         BUG_ON(!btrfs_is_leaf(leaf));
1276         nritems = btrfs_header_nritems(leaf);
1277         for (i = 0; i < nritems; i++) {
1278                 u64 disk_bytenr;
1279
1280                 btrfs_item_key_to_cpu(leaf, &key, i);
1281                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1282                         continue;
1283                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1284                 if (btrfs_file_extent_type(leaf, fi) ==
1285                     BTRFS_FILE_EXTENT_INLINE)
1286                         continue;
1287                 /*
1288                  * FIXME make sure to insert a trans record that
1289                  * repeats the snapshot del on crash
1290                  */
1291                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1292                 if (disk_bytenr == 0)
1293                         continue;
1294                 ret = btrfs_free_extent(trans, root, disk_bytenr,
1295                                 btrfs_file_extent_disk_num_bytes(leaf, fi), 0);
1296                 BUG_ON(ret);
1297         }
1298         return 0;
1299 }
1300
1301 static void reada_walk_down(struct btrfs_root *root,
1302                             struct extent_buffer *node)
1303 {
1304         int i;
1305         u32 nritems;
1306         u64 bytenr;
1307         int ret;
1308         u32 refs;
1309         int level;
1310         u32 blocksize;
1311
1312         nritems = btrfs_header_nritems(node);
1313         level = btrfs_header_level(node);
1314         for (i = 0; i < nritems; i++) {
1315                 bytenr = btrfs_node_blockptr(node, i);
1316                 blocksize = btrfs_level_size(root, level - 1);
1317                 ret = lookup_extent_ref(NULL, root, bytenr, blocksize, &refs);
1318                 BUG_ON(ret);
1319                 if (refs != 1)
1320                         continue;
1321                 mutex_unlock(&root->fs_info->fs_mutex);
1322                 ret = readahead_tree_block(root, bytenr, blocksize);
1323                 cond_resched();
1324                 mutex_lock(&root->fs_info->fs_mutex);
1325                 if (ret)
1326                         break;
1327         }
1328 }
1329
1330 /*
1331  * helper function for drop_snapshot, this walks down the tree dropping ref
1332  * counts as it goes.
1333  */
1334 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1335                           *root, struct btrfs_path *path, int *level)
1336 {
1337         struct extent_buffer *next;
1338         struct extent_buffer *cur;
1339         u64 bytenr;
1340         u32 blocksize;
1341         int ret;
1342         u32 refs;
1343
1344         WARN_ON(*level < 0);
1345         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1346         ret = lookup_extent_ref(trans, root,
1347                                 path->nodes[*level]->start,
1348                                 path->nodes[*level]->len, &refs);
1349         BUG_ON(ret);
1350         if (refs > 1)
1351                 goto out;
1352
1353         /*
1354          * walk down to the last node level and free all the leaves
1355          */
1356         while(*level >= 0) {
1357                 WARN_ON(*level < 0);
1358                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1359                 cur = path->nodes[*level];
1360
1361                 if (*level > 0 && path->slots[*level] == 0)
1362                         reada_walk_down(root, cur);
1363
1364                 if (btrfs_header_level(cur) != *level)
1365                         WARN_ON(1);
1366
1367                 if (path->slots[*level] >=
1368                     btrfs_header_nritems(cur))
1369                         break;
1370                 if (*level == 0) {
1371                         ret = drop_leaf_ref(trans, root, cur);
1372                         BUG_ON(ret);
1373                         break;
1374                 }
1375                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1376                 blocksize = btrfs_level_size(root, *level - 1);
1377                 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1378                 BUG_ON(ret);
1379                 if (refs != 1) {
1380                         path->slots[*level]++;
1381                         ret = btrfs_free_extent(trans, root, bytenr,
1382                                                 blocksize, 1);
1383                         BUG_ON(ret);
1384                         continue;
1385                 }
1386                 next = btrfs_find_tree_block(root, bytenr, blocksize);
1387                 if (!next || !btrfs_buffer_uptodate(next)) {
1388                         free_extent_buffer(next);
1389                         mutex_unlock(&root->fs_info->fs_mutex);
1390                         next = read_tree_block(root, bytenr, blocksize);
1391                         mutex_lock(&root->fs_info->fs_mutex);
1392
1393                         /* we dropped the lock, check one more time */
1394                         ret = lookup_extent_ref(trans, root, bytenr,
1395                                                 blocksize, &refs);
1396                         BUG_ON(ret);
1397                         if (refs != 1) {
1398                                 path->slots[*level]++;
1399                                 free_extent_buffer(next);
1400                                 ret = btrfs_free_extent(trans, root,
1401                                                         bytenr, blocksize, 1);
1402                                 BUG_ON(ret);
1403                                 continue;
1404                         }
1405                 }
1406                 WARN_ON(*level <= 0);
1407                 if (path->nodes[*level-1])
1408                         free_extent_buffer(path->nodes[*level-1]);
1409                 path->nodes[*level-1] = next;
1410                 *level = btrfs_header_level(next);
1411                 path->slots[*level] = 0;
1412         }
1413 out:
1414         WARN_ON(*level < 0);
1415         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1416         ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
1417                                 path->nodes[*level]->len, 1);
1418         free_extent_buffer(path->nodes[*level]);
1419         path->nodes[*level] = NULL;
1420         *level += 1;
1421         BUG_ON(ret);
1422         return 0;
1423 }
1424
1425 /*
1426  * helper for dropping snapshots.  This walks back up the tree in the path
1427  * to find the first node higher up where we haven't yet gone through
1428  * all the slots
1429  */
1430 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1431                         *root, struct btrfs_path *path, int *level)
1432 {
1433         int i;
1434         int slot;
1435         int ret;
1436         struct btrfs_root_item *root_item = &root->root_item;
1437
1438         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1439                 slot = path->slots[i];
1440                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
1441                         struct extent_buffer *node;
1442                         struct btrfs_disk_key disk_key;
1443                         node = path->nodes[i];
1444                         path->slots[i]++;
1445                         *level = i;
1446                         WARN_ON(*level == 0);
1447                         btrfs_node_key(node, &disk_key, path->slots[i]);
1448                         memcpy(&root_item->drop_progress,
1449                                &disk_key, sizeof(disk_key));
1450                         root_item->drop_level = i;
1451                         return 0;
1452                 } else {
1453                         ret = btrfs_free_extent(trans, root,
1454                                                 path->nodes[*level]->start,
1455                                                 path->nodes[*level]->len, 1);
1456                         BUG_ON(ret);
1457                         free_extent_buffer(path->nodes[*level]);
1458                         path->nodes[*level] = NULL;
1459                         *level = i + 1;
1460                 }
1461         }
1462         return 1;
1463 }
1464
1465 /*
1466  * drop the reference count on the tree rooted at 'snap'.  This traverses
1467  * the tree freeing any blocks that have a ref count of zero after being
1468  * decremented.
1469  */
1470 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
1471                         *root)
1472 {
1473         int ret = 0;
1474         int wret;
1475         int level;
1476         struct btrfs_path *path;
1477         int i;
1478         int orig_level;
1479         struct btrfs_root_item *root_item = &root->root_item;
1480
1481         path = btrfs_alloc_path();
1482         BUG_ON(!path);
1483
1484         level = btrfs_header_level(root->node);
1485         orig_level = level;
1486         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1487                 path->nodes[level] = root->node;
1488                 extent_buffer_get(root->node);
1489                 path->slots[level] = 0;
1490         } else {
1491                 struct btrfs_key key;
1492                 struct btrfs_disk_key found_key;
1493                 struct extent_buffer *node;
1494
1495                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1496                 level = root_item->drop_level;
1497                 path->lowest_level = level;
1498                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1499                 if (wret < 0) {
1500                         ret = wret;
1501                         goto out;
1502                 }
1503                 node = path->nodes[level];
1504                 btrfs_node_key(node, &found_key, path->slots[level]);
1505                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1506                                sizeof(found_key)));
1507         }
1508         while(1) {
1509                 wret = walk_down_tree(trans, root, path, &level);
1510                 if (wret > 0)
1511                         break;
1512                 if (wret < 0)
1513                         ret = wret;
1514
1515                 wret = walk_up_tree(trans, root, path, &level);
1516                 if (wret > 0)
1517                         break;
1518                 if (wret < 0)
1519                         ret = wret;
1520                 ret = -EAGAIN;
1521                 break;
1522         }
1523         for (i = 0; i <= orig_level; i++) {
1524                 if (path->nodes[i]) {
1525                         free_extent_buffer(path->nodes[i]);
1526                         path->nodes[i] = NULL;
1527                 }
1528         }
1529 out:
1530         btrfs_free_path(path);
1531         return ret;
1532 }
1533
1534 int btrfs_free_block_groups(struct btrfs_fs_info *info)
1535 {
1536         u64 start;
1537         u64 end;
1538         u64 ptr;
1539         int ret;
1540         while(1) {
1541                 ret = find_first_extent_bit(&info->block_group_cache, 0,
1542                                             &start, &end, (unsigned int)-1);
1543                 if (ret)
1544                         break;
1545                 ret = get_state_private(&info->block_group_cache, start, &ptr);
1546                 if (!ret)
1547                         kfree((void *)(unsigned long)ptr);
1548                 clear_extent_bits(&info->block_group_cache, start,
1549                                   end, (unsigned int)-1, GFP_NOFS);
1550         }
1551         while(1) {
1552                 ret = find_first_extent_bit(&info->free_space_cache, 0,
1553                                             &start, &end, EXTENT_DIRTY);
1554                 if (ret)
1555                         break;
1556                 clear_extent_dirty(&info->free_space_cache, start,
1557                                    end, GFP_NOFS);
1558         }
1559         return 0;
1560 }
1561
1562 int btrfs_read_block_groups(struct btrfs_root *root)
1563 {
1564         struct btrfs_path *path;
1565         int ret;
1566         int err = 0;
1567         int bit;
1568         struct btrfs_block_group_cache *cache;
1569         struct btrfs_fs_info *info = root->fs_info;
1570         struct extent_map_tree *block_group_cache;
1571         struct btrfs_key key;
1572         struct btrfs_key found_key;
1573         struct extent_buffer *leaf;
1574
1575         block_group_cache = &info->block_group_cache;
1576
1577         root = info->extent_root;
1578         key.objectid = 0;
1579         key.offset = BTRFS_BLOCK_GROUP_SIZE;
1580         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
1581
1582         path = btrfs_alloc_path();
1583         if (!path)
1584                 return -ENOMEM;
1585
1586         while(1) {
1587                 ret = btrfs_search_slot(NULL, info->extent_root,
1588                                         &key, path, 0, 0);
1589                 if (ret != 0) {
1590                         err = ret;
1591                         break;
1592                 }
1593                 leaf = path->nodes[0];
1594                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1595                 cache = kmalloc(sizeof(*cache), GFP_NOFS);
1596                 if (!cache) {
1597                         err = -1;
1598                         break;
1599                 }
1600
1601                 read_extent_buffer(leaf, &cache->item,
1602                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
1603                                    sizeof(cache->item));
1604                 memcpy(&cache->key, &found_key, sizeof(found_key));
1605                 cache->cached = 0;
1606                 cache->pinned = 0;
1607                 key.objectid = found_key.objectid + found_key.offset;
1608                 btrfs_release_path(root, path);
1609
1610                 if (cache->item.flags & BTRFS_BLOCK_GROUP_MIXED) {
1611                         bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
1612                         cache->data = BTRFS_BLOCK_GROUP_MIXED;
1613                 } else if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
1614                         bit = BLOCK_GROUP_DATA;
1615                         cache->data = BTRFS_BLOCK_GROUP_DATA;
1616                 } else {
1617                         bit = BLOCK_GROUP_METADATA;
1618                         cache->data = 0;
1619                 }
1620
1621                 /* use EXTENT_LOCKED to prevent merging */
1622                 set_extent_bits(block_group_cache, found_key.objectid,
1623                                 found_key.objectid + found_key.offset - 1,
1624                                 bit | EXTENT_LOCKED, GFP_NOFS);
1625                 set_state_private(block_group_cache, found_key.objectid,
1626                                   (unsigned long)cache);
1627
1628                 if (key.objectid >=
1629                     btrfs_super_total_bytes(&info->super_copy))
1630                         break;
1631         }
1632
1633         btrfs_free_path(path);
1634         return 0;
1635 }