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