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 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
 400                          struct btrfs_root *root)
 401 {
 402         finish_current_insert(trans, root->fs_info->extent_root);
 403         del_pending_extents(trans, root->fs_info->extent_root);
 404         return 0;
 405 }
 406
 407 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
 408                              struct btrfs_root *root, u64 blocknr,
 409                              u64 num_blocks, u32 *refs)
 410 {
 411         struct btrfs_path *path;
 412         int ret;
 413         struct btrfs_key key;
 414         struct btrfs_leaf *l;
 415         struct btrfs_extent_item *item;
 416
 417         path = btrfs_alloc_path();
 418         key.objectid = blocknr;
 419         key.offset = num_blocks;
 420         key.flags = 0;
 421         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 422         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 423                                 0, 0);
 424         if (ret < 0)
 425                 goto out;
 426         if (ret != 0)
 427                 BUG();
 428         l = btrfs_buffer_leaf(path->nodes[0]);
 429         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 430         *refs = btrfs_extent_refs(item);
 431 out:
 432         btrfs_free_path(path);
 433         return 0;
 434 }
 435
 436 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
 437                        struct btrfs_root *root)
 438 {
 439         return btrfs_inc_extent_ref(trans, root, bh_blocknr(root->node), 1);
 440 }
 441
 442 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 443                   struct buffer_head *buf)
 444 {
 445         u64 blocknr;
 446         struct btrfs_node *buf_node;
 447         struct btrfs_leaf *buf_leaf;
 448         struct btrfs_disk_key *key;
 449         struct btrfs_file_extent_item *fi;
 450         int i;
 451         int leaf;
 452         int ret;
 453         int faili;
 454         int err;
 455
 456         if (!root->ref_cows)
 457                 return 0;
 458         buf_node = btrfs_buffer_node(buf);
 459         leaf = btrfs_is_leaf(buf_node);
 460         buf_leaf = btrfs_buffer_leaf(buf);
 461         for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
 462                 if (leaf) {
 463                         u64 disk_blocknr;
 464                         key = &buf_leaf->items[i].key;
 465                         if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
 466                                 continue;
 467                         fi = btrfs_item_ptr(buf_leaf, i,
 468                                             struct btrfs_file_extent_item);
 469                         if (btrfs_file_extent_type(fi) ==
 470                             BTRFS_FILE_EXTENT_INLINE)
 471                                 continue;
 472                         disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
 473                         if (disk_blocknr == 0)
 474                                 continue;
 475                         ret = btrfs_inc_extent_ref(trans, root, disk_blocknr,
 476                                     btrfs_file_extent_disk_num_blocks(fi));
 477                         if (ret) {
 478                                 faili = i;
 479                                 goto fail;
 480                         }
 481                 } else {
 482                         blocknr = btrfs_node_blockptr(buf_node, i);
 483                         ret = btrfs_inc_extent_ref(trans, root, blocknr, 1);
 484                         if (ret) {
 485                                 faili = i;
 486                                 goto fail;
 487                         }
 488                 }
 489         }
 490         return 0;
 491 fail:
 492         WARN_ON(1);
 493         for (i =0; i < faili; i++) {
 494                 if (leaf) {
 495                         u64 disk_blocknr;
 496                         key = &buf_leaf->items[i].key;
 497                         if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
 498                                 continue;
 499                         fi = btrfs_item_ptr(buf_leaf, i,
 500                                             struct btrfs_file_extent_item);
 501                         if (btrfs_file_extent_type(fi) ==
 502                             BTRFS_FILE_EXTENT_INLINE)
 503                                 continue;
 504                         disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
 505                         if (disk_blocknr == 0)
 506                                 continue;
 507                         err = btrfs_free_extent(trans, root, disk_blocknr,
 508                                     btrfs_file_extent_disk_num_blocks(fi), 0);
 509                         BUG_ON(err);
 510                 } else {
 511                         blocknr = btrfs_node_blockptr(buf_node, i);
 512                         err = btrfs_free_extent(trans, root, blocknr, 1, 0);
 513                         BUG_ON(err);
 514                 }
 515         }
 516         return ret;
 517 }
 518
 519 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 520                                  struct btrfs_root *root,
 521                                  struct btrfs_path *path,
 522                                  struct btrfs_block_group_cache *cache)
 523 {
 524         int ret;
 525         int pending_ret;
 526         struct btrfs_root *extent_root = root->fs_info->extent_root;
 527         struct btrfs_block_group_item *bi;
 528
 529         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 530         if (ret < 0)
 531                 goto fail;
 532         BUG_ON(ret);
 533         bi = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
 534                             struct btrfs_block_group_item);
 535         memcpy(bi, &cache->item, sizeof(*bi));
 536         btrfs_mark_buffer_dirty(path->nodes[0]);
 537         btrfs_release_path(extent_root, path);
 538 fail:
 539         finish_current_insert(trans, extent_root);
 540         pending_ret = del_pending_extents(trans, extent_root);
 541         if (ret)
 542                 return ret;
 543         if (pending_ret)
 544                 return pending_ret;
 545         if (cache->data)
 546                 cache->last_alloc = cache->first_free;
 547         return 0;
 548
 549 }
 550
 551 static int write_dirty_block_radix(struct btrfs_trans_handle *trans,
 552                                    struct btrfs_root *root,
 553                                    struct radix_tree_root *radix)
 554 {
 555         struct btrfs_block_group_cache *cache[8];
 556         int ret;
 557         int err = 0;
 558         int werr = 0;
 559         int i;
 560         struct btrfs_path *path;
 561         unsigned long off = 0;
 562
 563         path = btrfs_alloc_path();
 564         if (!path)
 565                 return -ENOMEM;
 566
 567         while(1) {
 568                 ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
 569                                                  off, ARRAY_SIZE(cache),
 570                                                  BTRFS_BLOCK_GROUP_DIRTY);
 571                 if (!ret)
 572                         break;
 573                 for (i = 0; i < ret; i++) {
 574                         err = write_one_cache_group(trans, root,
 575                                                     path, cache[i]);
 576                         /*
 577                          * if we fail to write the cache group, we want
 578                          * to keep it marked dirty in hopes that a later
 579                          * write will work
 580                          */
 581                         if (err) {
 582                                 werr = err;
 583                                 off = cache[i]->key.objectid +
 584                                         cache[i]->key.offset;
 585                                 continue;
 586                         }
 587
 588                         radix_tree_tag_clear(radix, cache[i]->key.objectid +
 589                                              cache[i]->key.offset - 1,
 590                                              BTRFS_BLOCK_GROUP_DIRTY);
 591                 }
 592         }
 593         btrfs_free_path(path);
 594         return werr;
 595 }
 596
 597 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 598                                    struct btrfs_root *root)
 599 {
 600         int ret;
 601         int ret2;
 602         ret = write_dirty_block_radix(trans, root,
 603                                       &root->fs_info->block_group_radix);
 604         ret2 = write_dirty_block_radix(trans, root,
 605                                       &root->fs_info->block_group_data_radix);
 606         if (ret)
 607                 return ret;
 608         if (ret2)
 609                 return ret2;
 610         return 0;
 611 }
 612
 613 static int update_block_group(struct btrfs_trans_handle *trans,
 614                               struct btrfs_root *root,
 615                               u64 blocknr, u64 num, int alloc, int mark_free,
 616                               int data)
 617 {
 618         struct btrfs_block_group_cache *cache;
 619         struct btrfs_fs_info *info = root->fs_info;
 620         u64 total = num;
 621         u64 old_val;
 622         u64 block_in_group;
 623         u64 i;
 624         int ret;
 625
 626         while(total) {
 627                 cache = btrfs_lookup_block_group(info, blocknr);
 628                 if (!cache) {
 629                         return -1;
 630                 }
 631                 block_in_group = blocknr - cache->key.objectid;
 632                 WARN_ON(block_in_group > cache->key.offset);
 633                 radix_tree_tag_set(cache->radix, cache->key.objectid +
 634                                    cache->key.offset - 1,
 635                                    BTRFS_BLOCK_GROUP_DIRTY);
 636
 637                 old_val = btrfs_block_group_used(&cache->item);
 638                 num = min(total, cache->key.offset - block_in_group);
 639                 if (alloc) {
 640                         if (blocknr > cache->last_alloc)
 641                                 cache->last_alloc = blocknr;
 642                         if (!cache->data) {
 643                                 for (i = 0; i < num; i++) {
 644                                         clear_radix_bit(&info->extent_map_radix,
 645                                                         blocknr + i);
 646                                 }
 647                         }
 648                         if (cache->data != data &&
 649                             old_val < (cache->key.offset >> 1)) {
 650                                 cache->data = data;
 651                                 radix_tree_delete(cache->radix,
 652                                                   cache->key.objectid +
 653                                                   cache->key.offset - 1);
 654
 655                                 if (data) {
 656                                         cache->radix =
 657                                                 &info->block_group_data_radix;
 658                                         cache->item.flags |=
 659                                                 BTRFS_BLOCK_GROUP_DATA;
 660                                 } else {
 661                                         cache->radix = &info->block_group_radix;
 662                                         cache->item.flags &=
 663                                                 ~BTRFS_BLOCK_GROUP_DATA;
 664                                 }
 665                                 ret = radix_tree_insert(cache->radix,
 666                                                         cache->key.objectid +
 667                                                         cache->key.offset - 1,
 668                                                         (void *)cache);
 669                         }
 670                         old_val += num;
 671                 } else {
 672                         old_val -= num;
 673                         if (blocknr < cache->first_free)
 674                                 cache->first_free = blocknr;
 675                         if (!cache->data && mark_free) {
 676                                 for (i = 0; i < num; i++) {
 677                                         set_radix_bit(&info->extent_map_radix,
 678                                                       blocknr + i);
 679                                 }
 680                         }
 681                         if (old_val < (cache->key.offset >> 1) &&
 682                             old_val + num >= (cache->key.offset >> 1)) {
 683                                 radix_tree_tag_set(cache->radix,
 684                                                    cache->key.objectid +
 685                                                    cache->key.offset - 1,
 686                                                    BTRFS_BLOCK_GROUP_AVAIL);
 687                         }
 688                 }
 689                 btrfs_set_block_group_used(&cache->item, old_val);
 690                 total -= num;
 691                 blocknr += num;
 692         }
 693         return 0;
 694 }
 695
 696 int btrfs_copy_pinned(struct btrfs_root *root, struct radix_tree_root *copy)
 697 {
 698         unsigned long gang[8];
 699         u64 last = 0;
 700         struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
 701         int ret;
 702         int i;
 703
 704         while(1) {
 705                 ret = find_first_radix_bit(pinned_radix, gang, last,
 706                                            ARRAY_SIZE(gang));
 707                 if (!ret)
 708                         break;
 709                 for (i = 0 ; i < ret; i++) {
 710                         set_radix_bit(copy, gang[i]);
 711                         last = gang[i] + 1;
 712                 }
 713         }
 714         ret = find_first_radix_bit(&root->fs_info->extent_ins_radix, gang, 0,
 715                                    ARRAY_SIZE(gang));
 716         WARN_ON(ret);
 717         return 0;
 718 }
 719
 720 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
 721                                struct btrfs_root *root,
 722                                struct radix_tree_root *unpin_radix)
 723 {
 724         unsigned long gang[8];
 725         struct btrfs_block_group_cache *block_group;
 726         u64 first = 0;
 727         int ret;
 728         int i;
 729         struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
 730         struct radix_tree_root *extent_radix = &root->fs_info->extent_map_radix;
 731
 732         while(1) {
 733                 ret = find_first_radix_bit(unpin_radix, gang, 0,
 734                                            ARRAY_SIZE(gang));
 735                 if (!ret)
 736                         break;
 737                 if (!first)
 738                         first = gang[0];
 739                 for (i = 0; i < ret; i++) {
 740                         clear_radix_bit(pinned_radix, gang[i]);
 741                         clear_radix_bit(unpin_radix, gang[i]);
 742                         block_group = btrfs_lookup_block_group(root->fs_info,
 743                                                                gang[i]);
 744                         if (block_group) {
 745                                 WARN_ON(block_group->pinned == 0);
 746                                 block_group->pinned--;
 747                                 if (gang[i] < block_group->last_alloc)
 748                                         block_group->last_alloc = gang[i];
 749                                 if (!block_group->data)
 750                                         set_radix_bit(extent_radix, gang[i]);
 751                         }
 752                 }
 753         }
 754         return 0;
 755 }
 756
 757 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 758                                  btrfs_root *extent_root)
 759 {
 760         struct btrfs_key ins;
 761         struct btrfs_extent_item extent_item;
 762         int i;
 763         int ret;
 764         int err;
 765         unsigned long gang[8];
 766         struct btrfs_fs_info *info = extent_root->fs_info;
 767
 768         btrfs_set_extent_refs(&extent_item, 1);
 769         ins.offset = 1;
 770         ins.flags = 0;
 771         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 772         btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid);
 773
 774         while(1) {
 775                 ret = find_first_radix_bit(&info->extent_ins_radix, gang, 0,
 776                                            ARRAY_SIZE(gang));
 777                 if (!ret)
 778                         break;
 779
 780                 for (i = 0; i < ret; i++) {
 781                         ins.objectid = gang[i];
 782                         err = btrfs_insert_item(trans, extent_root, &ins,
 783                                                 &extent_item,
 784                                                 sizeof(extent_item));
 785                         clear_radix_bit(&info->extent_ins_radix, gang[i]);
 786                         WARN_ON(err);
 787                 }
 788         }
 789         return 0;
 790 }
 791
 792 static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
 793 {
 794         int err;
 795         struct btrfs_header *header;
 796         struct buffer_head *bh;
 797
 798         if (!pending) {
 799                 bh = btrfs_find_tree_block(root, blocknr);
 800                 if (bh) {
 801                         if (buffer_uptodate(bh)) {
 802                                 u64 transid =
 803                                     root->fs_info->running_transaction->transid;
 804                                 header = btrfs_buffer_header(bh);
 805                                 if (btrfs_header_generation(header) ==
 806                                     transid) {
 807                                         btrfs_block_release(root, bh);
 808                                         return 0;
 809                                 }
 810                         }
 811                         btrfs_block_release(root, bh);
 812                 }
 813                 err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
 814                 if (!err) {
 815                         struct btrfs_block_group_cache *cache;
 816                         cache = btrfs_lookup_block_group(root->fs_info,
 817                                                          blocknr);
 818                         if (cache)
 819                                 cache->pinned++;
 820                 }
 821         } else {
 822                 err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
 823         }
 824         BUG_ON(err < 0);
 825         return 0;
 826 }
 827
 828 /*
 829  * remove an extent from the root, returns 0 on success
 830  */
 831 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 832                          *root, u64 blocknr, u64 num_blocks, int pin,
 833                          int mark_free)
 834 {
 835         struct btrfs_path *path;
 836         struct btrfs_key key;
 837         struct btrfs_fs_info *info = root->fs_info;
 838         struct btrfs_root *extent_root = info->extent_root;
 839         int ret;
 840         struct btrfs_extent_item *ei;
 841         u32 refs;
 842
 843         key.objectid = blocknr;
 844         key.flags = 0;
 845         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 846         key.offset = num_blocks;
 847
 848         path = btrfs_alloc_path();
 849         if (!path)
 850                 return -ENOMEM;
 851
 852         ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
 853         if (ret < 0)
 854                 return ret;
 855         BUG_ON(ret);
 856         ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
 857                             struct btrfs_extent_item);
 858         BUG_ON(ei->refs == 0);
 859         refs = btrfs_extent_refs(ei) - 1;
 860         btrfs_set_extent_refs(ei, refs);
 861         btrfs_mark_buffer_dirty(path->nodes[0]);
 862         if (refs == 0) {
 863                 u64 super_blocks_used;
 864
 865                 if (pin) {
 866                         ret = pin_down_block(root, blocknr, 0);
 867                         BUG_ON(ret);
 868                 }
 869
 870                 super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
 871                 btrfs_set_super_blocks_used(&info->super_copy,
 872                                             super_blocks_used - num_blocks);
 873                 ret = btrfs_del_item(trans, extent_root, path);
 874                 if (ret) {
 875                         return ret;
 876                 }
 877                 ret = update_block_group(trans, root, blocknr, num_blocks, 0,
 878                                          mark_free, 0);
 879                 BUG_ON(ret);
 880         }
 881         btrfs_free_path(path);
 882         finish_current_insert(trans, extent_root);
 883         return ret;
 884 }
 885
 886 /*
 887  * find all the blocks marked as pending in the radix tree and remove
 888  * them from the extent map
 889  */
 890 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 891                                btrfs_root *extent_root)
 892 {
 893         int ret;
 894         int wret;
 895         int err = 0;
 896         unsigned long gang[4];
 897         int i;
 898         struct radix_tree_root *pending_radix;
 899         struct radix_tree_root *pinned_radix;
 900         struct btrfs_block_group_cache *cache;
 901
 902         pending_radix = &extent_root->fs_info->pending_del_radix;
 903         pinned_radix = &extent_root->fs_info->pinned_radix;
 904
 905         while(1) {
 906                 ret = find_first_radix_bit(pending_radix, gang, 0,
 907                                            ARRAY_SIZE(gang));
 908                 if (!ret)
 909                         break;
 910                 for (i = 0; i < ret; i++) {
 911                         wret = set_radix_bit(pinned_radix, gang[i]);
 912                         if (wret == 0) {
 913                                 cache =
 914                                   btrfs_lookup_block_group(extent_root->fs_info,
 915                                                            gang[i]);
 916                                 if (cache)
 917                                         cache->pinned++;
 918                         }
 919                         if (wret < 0) {
 920                                 printk(KERN_CRIT "set_radix_bit, err %d\n",
 921                                        wret);
 922                                 BUG_ON(wret < 0);
 923                         }
 924                         wret = clear_radix_bit(pending_radix, gang[i]);
 925                         BUG_ON(wret);
 926                         wret = __free_extent(trans, extent_root,
 927                                              gang[i], 1, 0, 0);
 928                         if (wret)
 929                                 err = wret;
 930                 }
 931         }
 932         return err;
 933 }
 934
 935 /*
 936  * remove an extent from the root, returns 0 on success
 937  */
 938 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 939                       *root, u64 blocknr, u64 num_blocks, int pin)
 940 {
 941         struct btrfs_root *extent_root = root->fs_info->extent_root;
 942         int pending_ret;
 943         int ret;
 944
 945         if (root == extent_root) {
 946                 pin_down_block(root, blocknr, 1);
 947                 return 0;
 948         }
 949         ret = __free_extent(trans, root, blocknr, num_blocks, pin, pin == 0);
 950         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
 951         return ret ? ret : pending_ret;
 952 }
 953
 954 /*
 955  * walks the btree of allocated extents and find a hole of a given size.
 956  * The key ins is changed to record the hole:
 957  * ins->objectid == block start
 958  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 959  * ins->offset == number of blocks
 960  * Any available blocks before search_start are skipped.
 961  */
 962 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 963                             *orig_root, u64 num_blocks, u64 empty_size,
 964                             u64 search_start, u64 search_end, u64 hint_block,
 965                             struct btrfs_key *ins, u64 exclude_start,
 966                             u64 exclude_nr, int data)
 967 {
 968         struct btrfs_path *path;
 969         struct btrfs_key key;
 970         int ret;
 971         u64 hole_size = 0;
 972         int slot = 0;
 973         u64 last_block = 0;
 974         u64 test_block;
 975         u64 orig_search_start = search_start;
 976         int start_found;
 977         struct btrfs_leaf *l;
 978         struct btrfs_root * root = orig_root->fs_info->extent_root;
 979         struct btrfs_fs_info *info = root->fs_info;
 980         int total_needed = num_blocks;
 981         int level;
 982         struct btrfs_block_group_cache *block_group;
 983         int full_scan = 0;
 984         int wrapped = 0;
 985         u64 limit;
 986
 987         WARN_ON(num_blocks < 1);
 988         ins->flags = 0;
 989         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 990
 991         level = btrfs_header_level(btrfs_buffer_header(root->node));
 992         if (search_end == (u64)-1)
 993                 search_end = btrfs_super_total_blocks(&info->super_copy);
 994         if (hint_block) {
 995                 block_group = btrfs_lookup_block_group(info, hint_block);
 996                 block_group = btrfs_find_block_group(root, block_group,
 997                                                      hint_block, data, 1);
 998         } else {
 999                 block_group = btrfs_find_block_group(root,
1000                                                      trans->block_group, 0,
1001                                                      data, 1);
1002         }
1003
1004         total_needed += empty_size;
1005         path = btrfs_alloc_path();
1006
1007 check_failed:
1008         if (!block_group->data)
1009                 search_start = find_search_start(root, &block_group,
1010                                                  search_start, total_needed);
1011         else if (!full_scan)
1012                 search_start = max(block_group->last_alloc, search_start);
1013
1014         btrfs_init_path(path);
1015         ins->objectid = search_start;
1016         ins->offset = 0;
1017         start_found = 0;
1018         path->reada = 1;
1019
1020         ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1021         if (ret < 0)
1022                 goto error;
1023
1024         if (path->slots[0] > 0) {
1025                 path->slots[0]--;
1026         }
1027
1028         l = btrfs_buffer_leaf(path->nodes[0]);
1029         btrfs_disk_key_to_cpu(&key, &l->items[path->slots[0]].key);
1030         /*
1031          * a rare case, go back one key if we hit a block group item
1032          * instead of an extent item
1033          */
1034         if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
1035             key.objectid + key.offset >= search_start) {
1036                 ins->objectid = key.objectid;
1037                 ins->offset = key.offset - 1;
1038                 btrfs_release_path(root, path);
1039                 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1040                 if (ret < 0)
1041                         goto error;
1042
1043                 if (path->slots[0] > 0) {
1044                         path->slots[0]--;
1045                 }
1046         }
1047
1048         while (1) {
1049                 l = btrfs_buffer_leaf(path->nodes[0]);
1050                 slot = path->slots[0];
1051                 if (slot >= btrfs_header_nritems(&l->header)) {
1052                         if (start_found)
1053                                 limit = last_block +
1054                                         (block_group->key.offset >> 1);
1055                         else
1056                                 limit = search_start +
1057                                         (block_group->key.offset >> 1);
1058                         ret = btrfs_next_leaf(root, path);
1059                         if (ret == 0)
1060                                 continue;
1061                         if (ret < 0)
1062                                 goto error;
1063                         if (!start_found) {
1064                                 ins->objectid = search_start;
1065                                 ins->offset = search_end - search_start;
1066                                 start_found = 1;
1067                                 goto check_pending;
1068                         }
1069                         ins->objectid = last_block > search_start ?
1070                                         last_block : search_start;
1071                         ins->offset = search_end - ins->objectid;
1072                         goto check_pending;
1073                 }
1074
1075                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
1076                 if (key.objectid >= search_start && key.objectid > last_block &&
1077                     start_found) {
1078                         if (last_block < search_start)
1079                                 last_block = search_start;
1080                         hole_size = key.objectid - last_block;
1081                         if (hole_size >= num_blocks) {
1082                                 ins->objectid = last_block;
1083                                 ins->offset = hole_size;
1084                                 goto check_pending;
1085                         }
1086                 }
1087
1088                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
1089                         goto next;
1090
1091                 start_found = 1;
1092                 last_block = key.objectid + key.offset;
1093                 if (!full_scan && last_block >= block_group->key.objectid +
1094                     block_group->key.offset) {
1095                         btrfs_release_path(root, path);
1096                         search_start = block_group->key.objectid +
1097                                 block_group->key.offset * 2;
1098                         goto new_group;
1099                 }
1100 next:
1101                 path->slots[0]++;
1102                 cond_resched();
1103         }
1104 check_pending:
1105         /* we have to make sure we didn't find an extent that has already
1106          * been allocated by the map tree or the original allocation
1107          */
1108         btrfs_release_path(root, path);
1109         BUG_ON(ins->objectid < search_start);
1110
1111         if (ins->objectid + num_blocks >= search_end) {
1112                 if (full_scan) {
1113                         ret = -ENOSPC;
1114                         goto error;
1115                 }
1116                 search_start = orig_search_start;
1117                 if (wrapped) {
1118                         if (!full_scan)
1119                                 total_needed -= empty_size;
1120                         full_scan = 1;
1121                 } else
1122                         wrapped = 1;
1123                 goto new_group;
1124         }
1125         for (test_block = ins->objectid;
1126              test_block < ins->objectid + num_blocks; test_block++) {
1127                 if (test_radix_bit(&info->pinned_radix, test_block) ||
1128                     test_radix_bit(&info->extent_ins_radix, test_block)) {
1129                         search_start = test_block + 1;
1130                         goto new_group;
1131                 }
1132         }
1133         if (exclude_nr > 0 && (ins->objectid + num_blocks > exclude_start &&
1134             ins->objectid < exclude_start + exclude_nr)) {
1135                 search_start = exclude_start + exclude_nr;
1136                 goto new_group;
1137         }
1138         if (!data) {
1139                 block_group = btrfs_lookup_block_group(info, ins->objectid);
1140                 if (block_group)
1141                         trans->block_group = block_group;
1142         }
1143         ins->offset = num_blocks;
1144         btrfs_free_path(path);
1145         return 0;
1146
1147 new_group:
1148         if (search_start + num_blocks >= search_end) {
1149                 search_start = orig_search_start;
1150                 if (full_scan) {
1151                         ret = -ENOSPC;
1152                         goto error;
1153                 }
1154                 if (wrapped) {
1155                         if (!full_scan)
1156                                 total_needed -= empty_size;
1157                         full_scan = 1;
1158                 } else
1159                         wrapped = 1;
1160         }
1161         block_group = btrfs_lookup_block_group(info, search_start);
1162         cond_resched();
1163         if (!full_scan)
1164                 block_group = btrfs_find_block_group(root, block_group,
1165                                                      search_start, data, 0);
1166         goto check_failed;
1167
1168 error:
1169         btrfs_release_path(root, path);
1170         btrfs_free_path(path);
1171         return ret;
1172 }
1173 /*
1174  * finds a free extent and does all the dirty work required for allocation
1175  * returns the key for the extent through ins, and a tree buffer for
1176  * the first block of the extent through buf.
1177  *
1178  * returns 0 if everything worked, non-zero otherwise.
1179  */
1180 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1181                        struct btrfs_root *root, u64 owner,
1182                        u64 num_blocks, u64 empty_size, u64 hint_block,
1183                        u64 search_end, struct btrfs_key *ins, int data)
1184 {
1185         int ret;
1186         int pending_ret;
1187         u64 super_blocks_used;
1188         u64 search_start = 0;
1189         struct btrfs_fs_info *info = root->fs_info;
1190         struct btrfs_root *extent_root = info->extent_root;
1191         struct btrfs_extent_item extent_item;
1192
1193         btrfs_set_extent_refs(&extent_item, 1);
1194         btrfs_set_extent_owner(&extent_item, owner);
1195
1196         WARN_ON(num_blocks < 1);
1197         ret = find_free_extent(trans, root, num_blocks, empty_size,
1198                                search_start, search_end, hint_block, ins,
1199                                trans->alloc_exclude_start,
1200                                trans->alloc_exclude_nr, data);
1201         BUG_ON(ret);
1202         if (ret)
1203                 return ret;
1204
1205         super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
1206         btrfs_set_super_blocks_used(&info->super_copy, super_blocks_used +
1207                                     num_blocks);
1208
1209         if (root == extent_root) {
1210                 BUG_ON(num_blocks != 1);
1211                 set_radix_bit(&root->fs_info->extent_ins_radix, ins->objectid);
1212                 goto update_block;
1213         }
1214
1215         WARN_ON(trans->alloc_exclude_nr);
1216         trans->alloc_exclude_start = ins->objectid;
1217         trans->alloc_exclude_nr = ins->offset;
1218         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1219                                 sizeof(extent_item));
1220
1221         trans->alloc_exclude_start = 0;
1222         trans->alloc_exclude_nr = 0;
1223
1224         BUG_ON(ret);
1225         finish_current_insert(trans, extent_root);
1226         pending_ret = del_pending_extents(trans, extent_root);
1227         if (ret) {
1228                 return ret;
1229         }
1230         if (pending_ret) {
1231                 return pending_ret;
1232         }
1233
1234 update_block:
1235         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1236                                  data);
1237         BUG_ON(ret);
1238         return 0;
1239 }
1240
1241 /*
1242  * helper function to allocate a block for a given tree
1243  * returns the tree buffer or NULL.
1244  */
1245 struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1246                                            struct btrfs_root *root, u64 hint,
1247                                            u64 empty_size)
1248 {
1249         struct btrfs_key ins;
1250         int ret;
1251         struct buffer_head *buf;
1252
1253         ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1254                                  1, empty_size, hint,
1255                                  (unsigned long)-1, &ins, 0);
1256         if (ret) {
1257                 BUG_ON(ret > 0);
1258                 return ERR_PTR(ret);
1259         }
1260         buf = btrfs_find_create_tree_block(root, ins.objectid);
1261         if (!buf) {
1262                 btrfs_free_extent(trans, root, ins.objectid, 1, 0);
1263                 return ERR_PTR(-ENOMEM);
1264         }
1265         WARN_ON(buffer_dirty(buf));
1266         set_buffer_uptodate(buf);
1267         set_buffer_checked(buf);
1268         set_buffer_defrag(buf);
1269         set_radix_bit(&trans->transaction->dirty_pages, buf->b_page->index);
1270         return buf;
1271 }
1272
1273 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
1274                          struct btrfs_root *root, struct buffer_head *cur)
1275 {
1276         struct btrfs_disk_key *key;
1277         struct btrfs_leaf *leaf;
1278         struct btrfs_file_extent_item *fi;
1279         int i;
1280         int nritems;
1281         int ret;
1282
1283         BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
1284         leaf = btrfs_buffer_leaf(cur);
1285         nritems = btrfs_header_nritems(&leaf->header);
1286         for (i = 0; i < nritems; i++) {
1287                 u64 disk_blocknr;
1288                 key = &leaf->items[i].key;
1289                 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
1290                         continue;
1291                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1292                 if (btrfs_file_extent_type(fi) == BTRFS_FILE_EXTENT_INLINE)
1293                         continue;
1294                 /*
1295                  * FIXME make sure to insert a trans record that
1296                  * repeats the snapshot del on crash
1297                  */
1298                 disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
1299                 if (disk_blocknr == 0)
1300                         continue;
1301                 ret = btrfs_free_extent(trans, root, disk_blocknr,
1302                                         btrfs_file_extent_disk_num_blocks(fi),
1303                                         0);
1304                 BUG_ON(ret);
1305         }
1306         return 0;
1307 }
1308
1309 static void reada_walk_down(struct btrfs_root *root,
1310                             struct btrfs_node *node)
1311 {
1312         int i;
1313         u32 nritems;
1314         u64 blocknr;
1315         int ret;
1316         u32 refs;
1317
1318         nritems = btrfs_header_nritems(&node->header);
1319         for (i = 0; i < nritems; i++) {
1320                 blocknr = btrfs_node_blockptr(node, i);
1321                 ret = lookup_extent_ref(NULL, root, blocknr, 1, &refs);
1322                 BUG_ON(ret);
1323                 if (refs != 1)
1324                         continue;
1325                 mutex_unlock(&root->fs_info->fs_mutex);
1326                 ret = readahead_tree_block(root, blocknr);
1327                 cond_resched();
1328                 mutex_lock(&root->fs_info->fs_mutex);
1329                 if (ret)
1330                         break;
1331         }
1332 }
1333
1334 /*
1335  * helper function for drop_snapshot, this walks down the tree dropping ref
1336  * counts as it goes.
1337  */
1338 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1339                           *root, struct btrfs_path *path, int *level)
1340 {
1341         struct buffer_head *next;
1342         struct buffer_head *cur;
1343         u64 blocknr;
1344         int ret;
1345         u32 refs;
1346
1347         WARN_ON(*level < 0);
1348         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1349         ret = lookup_extent_ref(trans, root, bh_blocknr(path->nodes[*level]),
1350                                1, &refs);
1351         BUG_ON(ret);
1352         if (refs > 1)
1353                 goto out;
1354
1355         /*
1356          * walk down to the last node level and free all the leaves
1357          */
1358         while(*level >= 0) {
1359                 WARN_ON(*level < 0);
1360                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1361                 cur = path->nodes[*level];
1362
1363                 if (*level > 0 && path->slots[*level] == 0)
1364                         reada_walk_down(root, btrfs_buffer_node(cur));
1365
1366                 if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
1367                         WARN_ON(1);
1368
1369                 if (path->slots[*level] >=
1370                     btrfs_header_nritems(btrfs_buffer_header(cur)))
1371                         break;
1372                 if (*level == 0) {
1373                         ret = drop_leaf_ref(trans, root, cur);
1374                         BUG_ON(ret);
1375                         break;
1376                 }
1377                 blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
1378                                               path->slots[*level]);
1379                 ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1380                 BUG_ON(ret);
1381                 if (refs != 1) {
1382                         path->slots[*level]++;
1383                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
1384                         BUG_ON(ret);
1385                         continue;
1386                 }
1387                 next = btrfs_find_tree_block(root, blocknr);
1388                 if (!next || !buffer_uptodate(next)) {
1389                         brelse(next);
1390                         mutex_unlock(&root->fs_info->fs_mutex);
1391                         next = read_tree_block(root, blocknr);
1392                         mutex_lock(&root->fs_info->fs_mutex);
1393
1394                         /* we dropped the lock, check one more time */
1395                         ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1396                         BUG_ON(ret);
1397                         if (refs != 1) {
1398                                 path->slots[*level]++;
1399                                 brelse(next);
1400                                 ret = btrfs_free_extent(trans, root,
1401                                                         blocknr, 1, 1);
1402                                 BUG_ON(ret);
1403                                 continue;
1404                         }
1405                 }
1406                 WARN_ON(*level <= 0);
1407                 if (path->nodes[*level-1])
1408                         btrfs_block_release(root, path->nodes[*level-1]);
1409                 path->nodes[*level-1] = next;
1410                 *level = btrfs_header_level(btrfs_buffer_header(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,
1417                                 bh_blocknr(path->nodes[*level]), 1, 1);
1418         btrfs_block_release(root, 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(
1441                     btrfs_buffer_header(path->nodes[i])) - 1) {
1442                         struct btrfs_node *node;
1443                         node = btrfs_buffer_node(path->nodes[i]);
1444                         path->slots[i]++;
1445                         *level = i;
1446                         WARN_ON(*level == 0);
1447                         memcpy(&root_item->drop_progress,
1448                                &node->ptrs[path->slots[i]].key,
1449                                sizeof(root_item->drop_progress));
1450                         root_item->drop_level = i;
1451                         return 0;
1452                 } else {
1453                         ret = btrfs_free_extent(trans, root,
1454                                                 bh_blocknr(path->nodes[*level]),
1455                                                 1, 1);
1456                         BUG_ON(ret);
1457                         btrfs_block_release(root, 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(btrfs_buffer_header(root->node));
1485         orig_level = level;
1486         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1487                 path->nodes[level] = root->node;
1488                 path->slots[level] = 0;
1489         } else {
1490                 struct btrfs_key key;
1491                 struct btrfs_disk_key *found_key;
1492                 struct btrfs_node *node;
1493
1494                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1495                 level = root_item->drop_level;
1496                 path->lowest_level = level;
1497                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1498                 if (wret < 0) {
1499                         ret = wret;
1500                         goto out;
1501                 }
1502                 node = btrfs_buffer_node(path->nodes[level]);
1503                 found_key = &node->ptrs[path->slots[level]].key;
1504                 WARN_ON(memcmp(found_key, &root_item->drop_progress,
1505                                sizeof(*found_key)));
1506         }
1507         while(1) {
1508                 wret = walk_down_tree(trans, root, path, &level);
1509                 if (wret > 0)
1510                         break;
1511                 if (wret < 0)
1512                         ret = wret;
1513
1514                 wret = walk_up_tree(trans, root, path, &level);
1515                 if (wret > 0)
1516                         break;
1517                 if (wret < 0)
1518                         ret = wret;
1519                 ret = -EAGAIN;
1520                 get_bh(root->node);
1521                 break;
1522         }
1523         for (i = 0; i <= orig_level; i++) {
1524                 if (path->nodes[i]) {
1525                         btrfs_block_release(root, path->nodes[i]);
1526                         path->nodes[i] = 0;
1527                 }
1528         }
1529 out:
1530         btrfs_free_path(path);
1531         return ret;
1532 }
1533
1534 static int free_block_group_radix(struct radix_tree_root *radix)
1535 {
1536         int ret;
1537         struct btrfs_block_group_cache *cache[8];
1538         int i;
1539
1540         while(1) {
1541                 ret = radix_tree_gang_lookup(radix, (void **)cache, 0,
1542                                              ARRAY_SIZE(cache));
1543                 if (!ret)
1544                         break;
1545                 for (i = 0; i < ret; i++) {
1546                         radix_tree_delete(radix, cache[i]->key.objectid +
1547                                           cache[i]->key.offset - 1);
1548                         kfree(cache[i]);
1549                 }
1550         }
1551         return 0;
1552 }
1553
1554 int btrfs_free_block_groups(struct btrfs_fs_info *info)
1555 {
1556         int ret;
1557         int ret2;
1558         unsigned long gang[16];
1559         int i;
1560
1561         ret = free_block_group_radix(&info->block_group_radix);
1562         ret2 = free_block_group_radix(&info->block_group_data_radix);
1563         if (ret)
1564                 return ret;
1565         if (ret2)
1566                 return ret2;
1567
1568         while(1) {
1569                 ret = find_first_radix_bit(&info->extent_map_radix,
1570                                            gang, 0, ARRAY_SIZE(gang));
1571                 if (!ret)
1572                         break;
1573                 for (i = 0; i < ret; i++) {
1574                         clear_radix_bit(&info->extent_map_radix, gang[i]);
1575                 }
1576         }
1577         return 0;
1578 }
1579
1580 int btrfs_read_block_groups(struct btrfs_root *root)
1581 {
1582         struct btrfs_path *path;
1583         int ret;
1584         int err = 0;
1585         struct btrfs_block_group_item *bi;
1586         struct btrfs_block_group_cache *cache;
1587         struct btrfs_fs_info *info = root->fs_info;
1588         struct radix_tree_root *radix;
1589         struct btrfs_key key;
1590         struct btrfs_key found_key;
1591         struct btrfs_leaf *leaf;
1592         u64 group_size_blocks;
1593         u64 used;
1594
1595         group_size_blocks = BTRFS_BLOCK_GROUP_SIZE >>
1596                 root->fs_info->sb->s_blocksize_bits;
1597         root = info->extent_root;
1598         key.objectid = 0;
1599         key.offset = group_size_blocks;
1600         key.flags = 0;
1601         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
1602
1603         path = btrfs_alloc_path();
1604         if (!path)
1605                 return -ENOMEM;
1606
1607         while(1) {
1608                 ret = btrfs_search_slot(NULL, info->extent_root,
1609                                         &key, path, 0, 0);
1610                 if (ret != 0) {
1611                         err = ret;
1612                         break;
1613                 }
1614                 leaf = btrfs_buffer_leaf(path->nodes[0]);
1615                 btrfs_disk_key_to_cpu(&found_key,
1616                                       &leaf->items[path->slots[0]].key);
1617                 cache = kmalloc(sizeof(*cache), GFP_NOFS);
1618                 if (!cache) {
1619                         err = -1;
1620                         break;
1621                 }
1622
1623                 bi = btrfs_item_ptr(leaf, path->slots[0],
1624                                     struct btrfs_block_group_item);
1625                 if (bi->flags & BTRFS_BLOCK_GROUP_DATA) {
1626                         radix = &info->block_group_data_radix;
1627                         cache->data = 1;
1628                 } else {
1629                         radix = &info->block_group_radix;
1630                         cache->data = 0;
1631                 }
1632
1633                 memcpy(&cache->item, bi, sizeof(*bi));
1634                 memcpy(&cache->key, &found_key, sizeof(found_key));
1635                 cache->last_alloc = cache->key.objectid;
1636                 cache->first_free = cache->key.objectid;
1637                 cache->pinned = 0;
1638                 cache->cached = 0;
1639
1640                 cache->radix = radix;
1641
1642                 key.objectid = found_key.objectid + found_key.offset;
1643                 btrfs_release_path(root, path);
1644                 ret = radix_tree_insert(radix, found_key.objectid +
1645                                         found_key.offset - 1,
1646                                         (void *)cache);
1647                 BUG_ON(ret);
1648                 used = btrfs_block_group_used(bi);
1649                 if (used < div_factor(key.offset, 8)) {
1650                         radix_tree_tag_set(radix, found_key.objectid +
1651                                            found_key.offset - 1,
1652                                            BTRFS_BLOCK_GROUP_AVAIL);
1653                 }
1654                 if (key.objectid >=
1655                     btrfs_super_total_blocks(&info->super_copy))
1656                         break;
1657         }
1658
1659         btrfs_free_path(path);
1660         return 0;
1661 }