Pileus Git - ~andy/linux/blob - 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
1019         ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1020         if (ret < 0)
1021                 goto error;
1022
1023         if (path->slots[0] > 0) {
1024                 path->slots[0]--;
1025         }
1026
1027         l = btrfs_buffer_leaf(path->nodes[0]);
1028         btrfs_disk_key_to_cpu(&key, &l->items[path->slots[0]].key);
1029         /*
1030          * a rare case, go back one key if we hit a block group item
1031          * instead of an extent item
1032          */
1033         if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
1034             key.objectid + key.offset >= search_start) {
1035                 ins->objectid = key.objectid;
1036                 ins->offset = key.offset - 1;
1037                 btrfs_release_path(root, path);
1038                 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1039                 if (ret < 0)
1040                         goto error;
1041
1042                 if (path->slots[0] > 0) {
1043                         path->slots[0]--;
1044                 }
1045         }
1046
1047         while (1) {
1048                 l = btrfs_buffer_leaf(path->nodes[0]);
1049                 slot = path->slots[0];
1050                 if (slot >= btrfs_header_nritems(&l->header)) {
1051                         if (start_found)
1052                                 limit = last_block +
1053                                         (block_group->key.offset >> 1);
1054                         else
1055                                 limit = search_start +
1056                                         (block_group->key.offset >> 1);
1057                         ret = btrfs_next_leaf(root, path);
1058                         if (ret == 0)
1059                                 continue;
1060                         if (ret < 0)
1061                                 goto error;
1062                         if (!start_found) {
1063                                 ins->objectid = search_start;
1064                                 ins->offset = search_end - search_start;
1065                                 start_found = 1;
1066                                 goto check_pending;
1067                         }
1068                         ins->objectid = last_block > search_start ?
1069                                         last_block : search_start;
1070                         ins->offset = search_end - ins->objectid;
1071                         goto check_pending;
1072                 }
1073
1074                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
1075                 if (key.objectid >= search_start && key.objectid > last_block &&
1076                     start_found) {
1077                         if (last_block < search_start)
1078                                 last_block = search_start;
1079                         hole_size = key.objectid - last_block;
1080                         if (hole_size >= num_blocks) {
1081                                 ins->objectid = last_block;
1082                                 ins->offset = hole_size;
1083                                 goto check_pending;
1084                         }
1085                 }
1086
1087                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
1088                         goto next;
1089
1090                 start_found = 1;
1091                 last_block = key.objectid + key.offset;
1092                 if (!full_scan && last_block >= block_group->key.objectid +
1093                     block_group->key.offset) {
1094                         btrfs_release_path(root, path);
1095                         search_start = block_group->key.objectid +
1096                                 block_group->key.offset * 2;
1097                         goto new_group;
1098                 }
1099 next:
1100                 path->slots[0]++;
1101                 cond_resched();
1102         }
1103 check_pending:
1104         /* we have to make sure we didn't find an extent that has already
1105          * been allocated by the map tree or the original allocation
1106          */
1107         btrfs_release_path(root, path);
1108         BUG_ON(ins->objectid < search_start);
1109
1110         if (ins->objectid + num_blocks >= search_end) {
1111                 if (full_scan) {
1112                         ret = -ENOSPC;
1113                         goto error;
1114                 }
1115                 search_start = orig_search_start;
1116                 if (wrapped) {
1117                         if (!full_scan)
1118                                 total_needed -= empty_size;
1119                         full_scan = 1;
1120                 } else
1121                         wrapped = 1;
1122                 goto new_group;
1123         }
1124         for (test_block = ins->objectid;
1125              test_block < ins->objectid + num_blocks; test_block++) {
1126                 if (test_radix_bit(&info->pinned_radix, test_block) ||
1127                     test_radix_bit(&info->extent_ins_radix, test_block)) {
1128                         search_start = test_block + 1;
1129                         goto new_group;
1130                 }
1131         }
1132         if (exclude_nr > 0 && (ins->objectid + num_blocks > exclude_start &&
1133             ins->objectid < exclude_start + exclude_nr)) {
1134                 search_start = exclude_start + exclude_nr;
1135                 goto new_group;
1136         }
1137         if (!data) {
1138                 block_group = btrfs_lookup_block_group(info, ins->objectid);
1139                 if (block_group)
1140                         trans->block_group = block_group;
1141         }
1142         ins->offset = num_blocks;
1143         btrfs_free_path(path);
1144         return 0;
1145
1146 new_group:
1147         if (search_start + num_blocks >= search_end) {
1148                 search_start = orig_search_start;
1149                 if (full_scan) {
1150                         ret = -ENOSPC;
1151                         goto error;
1152                 }
1153                 if (wrapped) {
1154                         if (!full_scan)
1155                                 total_needed -= empty_size;
1156                         full_scan = 1;
1157                 } else
1158                         wrapped = 1;
1159         }
1160         block_group = btrfs_lookup_block_group(info, search_start);
1161         cond_resched();
1162         if (!full_scan)
1163                 block_group = btrfs_find_block_group(root, block_group,
1164                                                      search_start, data, 0);
1165         goto check_failed;
1166
1167 error:
1168         btrfs_release_path(root, path);
1169         btrfs_free_path(path);
1170         return ret;
1171 }
1172 /*
1173  * finds a free extent and does all the dirty work required for allocation
1174  * returns the key for the extent through ins, and a tree buffer for
1175  * the first block of the extent through buf.
1176  *
1177  * returns 0 if everything worked, non-zero otherwise.
1178  */
1179 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1180                        struct btrfs_root *root, u64 owner,
1181                        u64 num_blocks, u64 empty_size, u64 hint_block,
1182                        u64 search_end, struct btrfs_key *ins, int data)
1183 {
1184         int ret;
1185         int pending_ret;
1186         u64 super_blocks_used;
1187         u64 search_start = 0;
1188         struct btrfs_fs_info *info = root->fs_info;
1189         struct btrfs_root *extent_root = info->extent_root;
1190         struct btrfs_extent_item extent_item;
1191
1192         btrfs_set_extent_refs(&extent_item, 1);
1193         btrfs_set_extent_owner(&extent_item, owner);
1194
1195         WARN_ON(num_blocks < 1);
1196         ret = find_free_extent(trans, root, num_blocks, empty_size,
1197                                search_start, search_end, hint_block, ins,
1198                                trans->alloc_exclude_start,
1199                                trans->alloc_exclude_nr, data);
1200         BUG_ON(ret);
1201         if (ret)
1202                 return ret;
1203
1204         super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
1205         btrfs_set_super_blocks_used(&info->super_copy, super_blocks_used +
1206                                     num_blocks);
1207
1208         if (root == extent_root) {
1209                 BUG_ON(num_blocks != 1);
1210                 set_radix_bit(&root->fs_info->extent_ins_radix, ins->objectid);
1211                 goto update_block;
1212         }
1213
1214         WARN_ON(trans->alloc_exclude_nr);
1215         trans->alloc_exclude_start = ins->objectid;
1216         trans->alloc_exclude_nr = ins->offset;
1217         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1218                                 sizeof(extent_item));
1219
1220         trans->alloc_exclude_start = 0;
1221         trans->alloc_exclude_nr = 0;
1222
1223         BUG_ON(ret);
1224         finish_current_insert(trans, extent_root);
1225         pending_ret = del_pending_extents(trans, extent_root);
1226         if (ret) {
1227                 return ret;
1228         }
1229         if (pending_ret) {
1230                 return pending_ret;
1231         }
1232
1233 update_block:
1234         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1235                                  data);
1236         BUG_ON(ret);
1237         return 0;
1238 }
1239
1240 /*
1241  * helper function to allocate a block for a given tree
1242  * returns the tree buffer or NULL.
1243  */
1244 struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1245                                            struct btrfs_root *root, u64 hint,
1246                                            u64 empty_size)
1247 {
1248         struct btrfs_key ins;
1249         int ret;
1250         struct buffer_head *buf;
1251
1252         ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1253                                  1, empty_size, hint,
1254                                  (unsigned long)-1, &ins, 0);
1255         if (ret) {
1256                 BUG_ON(ret > 0);
1257                 return ERR_PTR(ret);
1258         }
1259         buf = btrfs_find_create_tree_block(root, ins.objectid);
1260         if (!buf) {
1261                 btrfs_free_extent(trans, root, ins.objectid, 1, 0);
1262                 return ERR_PTR(-ENOMEM);
1263         }
1264         WARN_ON(buffer_dirty(buf));
1265         set_buffer_uptodate(buf);
1266         set_buffer_checked(buf);
1267         set_radix_bit(&trans->transaction->dirty_pages, buf->b_page->index);
1268         return buf;
1269 }
1270
1271 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
1272                          struct btrfs_root *root, struct buffer_head *cur)
1273 {
1274         struct btrfs_disk_key *key;
1275         struct btrfs_leaf *leaf;
1276         struct btrfs_file_extent_item *fi;
1277         int i;
1278         int nritems;
1279         int ret;
1280
1281         BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
1282         leaf = btrfs_buffer_leaf(cur);
1283         nritems = btrfs_header_nritems(&leaf->header);
1284         for (i = 0; i < nritems; i++) {
1285                 u64 disk_blocknr;
1286                 key = &leaf->items[i].key;
1287                 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
1288                         continue;
1289                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1290                 if (btrfs_file_extent_type(fi) == BTRFS_FILE_EXTENT_INLINE)
1291                         continue;
1292                 /*
1293                  * FIXME make sure to insert a trans record that
1294                  * repeats the snapshot del on crash
1295                  */
1296                 disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
1297                 if (disk_blocknr == 0)
1298                         continue;
1299                 ret = btrfs_free_extent(trans, root, disk_blocknr,
1300                                         btrfs_file_extent_disk_num_blocks(fi),
1301                                         0);
1302                 BUG_ON(ret);
1303         }
1304         return 0;
1305 }
1306
1307 static void reada_walk_down(struct btrfs_root *root,
1308                             struct btrfs_node *node)
1309 {
1310         int i;
1311         u32 nritems;
1312         u64 blocknr;
1313         int ret;
1314         u32 refs;
1315
1316         nritems = btrfs_header_nritems(&node->header);
1317         for (i = 0; i < nritems; i++) {
1318                 blocknr = btrfs_node_blockptr(node, i);
1319                 ret = lookup_extent_ref(NULL, root, blocknr, 1, &refs);
1320                 BUG_ON(ret);
1321                 if (refs != 1)
1322                         continue;
1323                 mutex_unlock(&root->fs_info->fs_mutex);
1324                 ret = readahead_tree_block(root, blocknr);
1325                 cond_resched();
1326                 mutex_lock(&root->fs_info->fs_mutex);
1327                 if (ret)
1328                         break;
1329         }
1330 }
1331
1332 /*
1333  * helper function for drop_snapshot, this walks down the tree dropping ref
1334  * counts as it goes.
1335  */
1336 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1337                           *root, struct btrfs_path *path, int *level)
1338 {
1339         struct buffer_head *next;
1340         struct buffer_head *cur;
1341         u64 blocknr;
1342         int ret;
1343         u32 refs;
1344
1345         WARN_ON(*level < 0);
1346         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1347         ret = lookup_extent_ref(trans, root, bh_blocknr(path->nodes[*level]),
1348                                1, &refs);
1349         BUG_ON(ret);
1350         if (refs > 1)
1351                 goto out;
1352
1353         /*
1354          * walk down to the last node level and free all the leaves
1355          */
1356         while(*level >= 0) {
1357                 WARN_ON(*level < 0);
1358                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1359                 cur = path->nodes[*level];
1360
1361                 if (*level > 0 && path->slots[*level] == 0)
1362                         reada_walk_down(root, btrfs_buffer_node(cur));
1363
1364                 if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
1365                         WARN_ON(1);
1366
1367                 if (path->slots[*level] >=
1368                     btrfs_header_nritems(btrfs_buffer_header(cur)))
1369                         break;
1370                 if (*level == 0) {
1371                         ret = drop_leaf_ref(trans, root, cur);
1372                         BUG_ON(ret);
1373                         break;
1374                 }
1375                 blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
1376                                               path->slots[*level]);
1377                 ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1378                 BUG_ON(ret);
1379                 if (refs != 1) {
1380                         path->slots[*level]++;
1381                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
1382                         BUG_ON(ret);
1383                         continue;
1384                 }
1385                 next = btrfs_find_tree_block(root, blocknr);
1386                 if (!next || !buffer_uptodate(next)) {
1387                         brelse(next);
1388                         mutex_unlock(&root->fs_info->fs_mutex);
1389                         next = read_tree_block(root, blocknr);
1390                         mutex_lock(&root->fs_info->fs_mutex);
1391
1392                         /* we dropped the lock, check one more time */
1393                         ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1394                         BUG_ON(ret);
1395                         if (refs != 1) {
1396                                 path->slots[*level]++;
1397                                 brelse(next);
1398                                 ret = btrfs_free_extent(trans, root,
1399                                                         blocknr, 1, 1);
1400                                 BUG_ON(ret);
1401                                 continue;
1402                         }
1403                 }
1404                 WARN_ON(*level <= 0);
1405                 if (path->nodes[*level-1])
1406                         btrfs_block_release(root, path->nodes[*level-1]);
1407                 path->nodes[*level-1] = next;
1408                 *level = btrfs_header_level(btrfs_buffer_header(next));
1409                 path->slots[*level] = 0;
1410         }
1411 out:
1412         WARN_ON(*level < 0);
1413         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1414         ret = btrfs_free_extent(trans, root,
1415                                 bh_blocknr(path->nodes[*level]), 1, 1);
1416         btrfs_block_release(root, path->nodes[*level]);
1417         path->nodes[*level] = NULL;
1418         *level += 1;
1419         BUG_ON(ret);
1420         return 0;
1421 }
1422
1423 /*
1424  * helper for dropping snapshots.  This walks back up the tree in the path
1425  * to find the first node higher up where we haven't yet gone through
1426  * all the slots
1427  */
1428 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1429                         *root, struct btrfs_path *path, int *level)
1430 {
1431         int i;
1432         int slot;
1433         int ret;
1434         struct btrfs_root_item *root_item = &root->root_item;
1435
1436         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1437                 slot = path->slots[i];
1438                 if (slot < btrfs_header_nritems(
1439                     btrfs_buffer_header(path->nodes[i])) - 1) {
1440                         struct btrfs_node *node;
1441                         node = btrfs_buffer_node(path->nodes[i]);
1442                         path->slots[i]++;
1443                         *level = i;
1444                         WARN_ON(*level == 0);
1445                         memcpy(&root_item->drop_progress,
1446                                &node->ptrs[path->slots[i]].key,
1447                                sizeof(root_item->drop_progress));
1448                         root_item->drop_level = i;
1449                         return 0;
1450                 } else {
1451                         ret = btrfs_free_extent(trans, root,
1452                                                 bh_blocknr(path->nodes[*level]),
1453                                                 1, 1);
1454                         BUG_ON(ret);
1455                         btrfs_block_release(root, path->nodes[*level]);
1456                         path->nodes[*level] = NULL;
1457                         *level = i + 1;
1458                 }
1459         }
1460         return 1;
1461 }
1462
1463 /*
1464  * drop the reference count on the tree rooted at 'snap'.  This traverses
1465  * the tree freeing any blocks that have a ref count of zero after being
1466  * decremented.
1467  */
1468 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
1469                         *root)
1470 {
1471         int ret = 0;
1472         int wret;
1473         int level;
1474         struct btrfs_path *path;
1475         int i;
1476         int orig_level;
1477         struct btrfs_root_item *root_item = &root->root_item;
1478
1479         path = btrfs_alloc_path();
1480         BUG_ON(!path);
1481
1482         level = btrfs_header_level(btrfs_buffer_header(root->node));
1483         orig_level = level;
1484         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1485                 path->nodes[level] = root->node;
1486                 path->slots[level] = 0;
1487         } else {
1488                 struct btrfs_key key;
1489                 struct btrfs_disk_key *found_key;
1490                 struct btrfs_node *node;
1491
1492                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1493                 level = root_item->drop_level;
1494                 path->lowest_level = level;
1495                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1496                 if (wret < 0) {
1497                         ret = wret;
1498                         goto out;
1499                 }
1500                 node = btrfs_buffer_node(path->nodes[level]);
1501                 found_key = &node->ptrs[path->slots[level]].key;
1502                 WARN_ON(memcmp(found_key, &root_item->drop_progress,
1503                                sizeof(*found_key)));
1504         }
1505         while(1) {
1506                 wret = walk_down_tree(trans, root, path, &level);
1507                 if (wret > 0)
1508                         break;
1509                 if (wret < 0)
1510                         ret = wret;
1511
1512                 wret = walk_up_tree(trans, root, path, &level);
1513                 if (wret > 0)
1514                         break;
1515                 if (wret < 0)
1516                         ret = wret;
1517                 ret = -EAGAIN;
1518                 get_bh(root->node);
1519                 break;
1520         }
1521         for (i = 0; i <= orig_level; i++) {
1522                 if (path->nodes[i]) {
1523                         btrfs_block_release(root, path->nodes[i]);
1524                         path->nodes[i] = 0;
1525                 }
1526         }
1527 out:
1528         btrfs_free_path(path);
1529         return ret;
1530 }
1531
1532 static int free_block_group_radix(struct radix_tree_root *radix)
1533 {
1534         int ret;
1535         struct btrfs_block_group_cache *cache[8];
1536         int i;
1537
1538         while(1) {
1539                 ret = radix_tree_gang_lookup(radix, (void **)cache, 0,
1540                                              ARRAY_SIZE(cache));
1541                 if (!ret)
1542                         break;
1543                 for (i = 0; i < ret; i++) {
1544                         radix_tree_delete(radix, cache[i]->key.objectid +
1545                                           cache[i]->key.offset - 1);
1546                         kfree(cache[i]);
1547                 }
1548         }
1549         return 0;
1550 }
1551
1552 int btrfs_free_block_groups(struct btrfs_fs_info *info)
1553 {
1554         int ret;
1555         int ret2;
1556         unsigned long gang[16];
1557         int i;
1558
1559         ret = free_block_group_radix(&info->block_group_radix);
1560         ret2 = free_block_group_radix(&info->block_group_data_radix);
1561         if (ret)
1562                 return ret;
1563         if (ret2)
1564                 return ret2;
1565
1566         while(1) {
1567                 ret = find_first_radix_bit(&info->extent_map_radix,
1568                                            gang, 0, ARRAY_SIZE(gang));
1569                 if (!ret)
1570                         break;
1571                 for (i = 0; i < ret; i++) {
1572                         clear_radix_bit(&info->extent_map_radix, gang[i]);
1573                 }
1574         }
1575         return 0;
1576 }
1577
1578 int btrfs_read_block_groups(struct btrfs_root *root)
1579 {
1580         struct btrfs_path *path;
1581         int ret;
1582         int err = 0;
1583         struct btrfs_block_group_item *bi;
1584         struct btrfs_block_group_cache *cache;
1585         struct btrfs_fs_info *info = root->fs_info;
1586         struct radix_tree_root *radix;
1587         struct btrfs_key key;
1588         struct btrfs_key found_key;
1589         struct btrfs_leaf *leaf;
1590         u64 group_size_blocks;
1591         u64 used;
1592
1593         group_size_blocks = BTRFS_BLOCK_GROUP_SIZE >>
1594                 root->fs_info->sb->s_blocksize_bits;
1595         root = info->extent_root;
1596         key.objectid = 0;
1597         key.offset = group_size_blocks;
1598         key.flags = 0;
1599         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
1600
1601         path = btrfs_alloc_path();
1602         if (!path)
1603                 return -ENOMEM;
1604
1605         while(1) {
1606                 ret = btrfs_search_slot(NULL, info->extent_root,
1607                                         &key, path, 0, 0);
1608                 if (ret != 0) {
1609                         err = ret;
1610                         break;
1611                 }
1612                 leaf = btrfs_buffer_leaf(path->nodes[0]);
1613                 btrfs_disk_key_to_cpu(&found_key,
1614                                       &leaf->items[path->slots[0]].key);
1615                 cache = kmalloc(sizeof(*cache), GFP_NOFS);
1616                 if (!cache) {
1617                         err = -1;
1618                         break;
1619                 }
1620
1621                 bi = btrfs_item_ptr(leaf, path->slots[0],
1622                                     struct btrfs_block_group_item);
1623                 if (bi->flags & BTRFS_BLOCK_GROUP_DATA) {
1624                         radix = &info->block_group_data_radix;
1625                         cache->data = 1;
1626                 } else {
1627                         radix = &info->block_group_radix;
1628                         cache->data = 0;
1629                 }
1630
1631                 memcpy(&cache->item, bi, sizeof(*bi));
1632                 memcpy(&cache->key, &found_key, sizeof(found_key));
1633                 cache->last_alloc = cache->key.objectid;
1634                 cache->first_free = cache->key.objectid;
1635                 cache->pinned = 0;
1636                 cache->cached = 0;
1637
1638                 cache->radix = radix;
1639
1640                 key.objectid = found_key.objectid + found_key.offset;
1641                 btrfs_release_path(root, path);
1642                 ret = radix_tree_insert(radix, found_key.objectid +
1643                                         found_key.offset - 1,
1644                                         (void *)cache);
1645                 BUG_ON(ret);
1646                 used = btrfs_block_group_used(bi);
1647                 if (used < div_factor(key.offset, 8)) {
1648                         radix_tree_tag_set(radix, found_key.objectid +
1649                                            found_key.offset - 1,
1650                                            BTRFS_BLOCK_GROUP_AVAIL);
1651                 }
1652                 if (key.objectid >=
1653                     btrfs_super_total_blocks(&info->super_copy))
1654                         break;
1655         }
1656
1657         btrfs_free_path(path);
1658         return 0;
1659 }