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