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