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         WARN_ON(1);
 527         for (i =0; i < faili; i++) {
 528                 if (leaf) {
 529                         u64 disk_blocknr;
 530                         key = &buf_leaf->items[i].key;
 531                         if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
 532                                 continue;
 533                         fi = btrfs_item_ptr(buf_leaf, i,
 534                                             struct btrfs_file_extent_item);
 535                         if (btrfs_file_extent_type(fi) ==
 536                             BTRFS_FILE_EXTENT_INLINE)
 537                                 continue;
 538                         disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
 539                         if (disk_blocknr == 0)
 540                                 continue;
 541                         err = btrfs_free_extent(trans, root, disk_blocknr,
 542                                     btrfs_file_extent_disk_num_blocks(fi), 0);
 543                         BUG_ON(err);
 544                 } else {
 545                         blocknr = btrfs_node_blockptr(buf_node, i);
 546                         err = btrfs_free_extent(trans, root, blocknr, 1, 0);
 547                         BUG_ON(err);
 548                 }
 549         }
 550         return ret;
 551 }
 552
 553 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 554                                  struct btrfs_root *root,
 555                                  struct btrfs_path *path,
 556                                  struct btrfs_block_group_cache *cache)
 557 {
 558         int ret;
 559         int pending_ret;
 560         struct btrfs_root *extent_root = root->fs_info->extent_root;
 561         struct btrfs_block_group_item *bi;
 562         struct btrfs_key ins;
 563
 564         ret = find_free_extent(trans, extent_root, 0, 0, (u64)-1, 0, &ins,
 565                                0, 0, 0);
 566         /* FIXME, set bit to recalc cache groups on next mount */
 567         if (ret)
 568                 return ret;
 569         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 570         if (ret < 0)
 571                 goto fail;
 572         BUG_ON(ret);
 573         bi = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
 574                             struct btrfs_block_group_item);
 575         memcpy(bi, &cache->item, sizeof(*bi));
 576         btrfs_mark_buffer_dirty(path->nodes[0]);
 577         btrfs_release_path(extent_root, path);
 578 fail:
 579         finish_current_insert(trans, extent_root);
 580         pending_ret = del_pending_extents(trans, extent_root);
 581         if (ret)
 582                 return ret;
 583         if (pending_ret)
 584                 return pending_ret;
 585         if (cache->data)
 586                 cache->last_alloc = cache->first_free;
 587         return 0;
 588
 589 }
 590
 591 static int write_dirty_block_radix(struct btrfs_trans_handle *trans,
 592                                    struct btrfs_root *root,
 593                                    struct radix_tree_root *radix)
 594 {
 595         struct btrfs_block_group_cache *cache[8];
 596         int ret;
 597         int err = 0;
 598         int werr = 0;
 599         int i;
 600         struct btrfs_path *path;
 601         unsigned long off = 0;
 602
 603         path = btrfs_alloc_path();
 604         if (!path)
 605                 return -ENOMEM;
 606
 607         while(1) {
 608                 ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
 609                                                  off, ARRAY_SIZE(cache),
 610                                                  BTRFS_BLOCK_GROUP_DIRTY);
 611                 if (!ret)
 612                         break;
 613                 for (i = 0; i < ret; i++) {
 614                         err = write_one_cache_group(trans, root,
 615                                                     path, cache[i]);
 616                         /*
 617                          * if we fail to write the cache group, we want
 618                          * to keep it marked dirty in hopes that a later
 619                          * write will work
 620                          */
 621                         if (err) {
 622                                 werr = err;
 623                                 off = cache[i]->key.objectid +
 624                                         cache[i]->key.offset;
 625                                 continue;
 626                         }
 627
 628                         radix_tree_tag_clear(radix, cache[i]->key.objectid +
 629                                              cache[i]->key.offset - 1,
 630                                              BTRFS_BLOCK_GROUP_DIRTY);
 631                 }
 632         }
 633         btrfs_free_path(path);
 634         return werr;
 635 }
 636
 637 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 638                                    struct btrfs_root *root)
 639 {
 640         int ret;
 641         int ret2;
 642         ret = write_dirty_block_radix(trans, root,
 643                                       &root->fs_info->block_group_radix);
 644         ret2 = write_dirty_block_radix(trans, root,
 645                                       &root->fs_info->block_group_data_radix);
 646         if (ret)
 647                 return ret;
 648         if (ret2)
 649                 return ret2;
 650         return 0;
 651 }
 652
 653 static int update_block_group(struct btrfs_trans_handle *trans,
 654                               struct btrfs_root *root,
 655                               u64 blocknr, u64 num, int alloc, int mark_free,
 656                               int data)
 657 {
 658         struct btrfs_block_group_cache *cache;
 659         struct btrfs_fs_info *info = root->fs_info;
 660         u64 total = num;
 661         u64 old_val;
 662         u64 block_in_group;
 663         u64 i;
 664         int ret;
 665
 666         while(total) {
 667                 cache = btrfs_lookup_block_group(info, blocknr);
 668                 if (!cache) {
 669                         return -1;
 670                 }
 671                 block_in_group = blocknr - cache->key.objectid;
 672                 WARN_ON(block_in_group > cache->key.offset);
 673                 radix_tree_tag_set(cache->radix, cache->key.objectid +
 674                                    cache->key.offset - 1,
 675                                    BTRFS_BLOCK_GROUP_DIRTY);
 676
 677                 old_val = btrfs_block_group_used(&cache->item);
 678                 num = min(total, cache->key.offset - block_in_group);
 679                 if (alloc) {
 680                         if (blocknr > cache->last_alloc)
 681                                 cache->last_alloc = blocknr;
 682                         if (!cache->data) {
 683                                 for (i = 0; i < num; i++) {
 684                                         clear_radix_bit(&info->extent_map_radix,
 685                                                         blocknr + i);
 686                                 }
 687                         }
 688                         if (cache->data != data &&
 689                             old_val < (cache->key.offset >> 1)) {
 690                                 cache->data = data;
 691                                 radix_tree_delete(cache->radix,
 692                                                   cache->key.objectid +
 693                                                   cache->key.offset - 1);
 694
 695                                 if (data) {
 696                                         cache->radix =
 697                                                 &info->block_group_data_radix;
 698                                         cache->item.flags |=
 699                                                 BTRFS_BLOCK_GROUP_DATA;
 700                                 } else {
 701                                         cache->radix = &info->block_group_radix;
 702                                         cache->item.flags &=
 703                                                 ~BTRFS_BLOCK_GROUP_DATA;
 704                                 }
 705                                 ret = radix_tree_insert(cache->radix,
 706                                                         cache->key.objectid +
 707                                                         cache->key.offset - 1,
 708                                                         (void *)cache);
 709                         }
 710                         old_val += num;
 711                 } else {
 712                         old_val -= num;
 713                         if (blocknr < cache->first_free)
 714                                 cache->first_free = blocknr;
 715                         if (!cache->data && mark_free) {
 716                                 for (i = 0; i < num; i++) {
 717                                         set_radix_bit(&info->extent_map_radix,
 718                                                       blocknr + i);
 719                                 }
 720                         }
 721                         if (old_val < (cache->key.offset >> 1) &&
 722                             old_val + num >= (cache->key.offset >> 1)) {
 723                                 radix_tree_tag_set(cache->radix,
 724                                                    cache->key.objectid +
 725                                                    cache->key.offset - 1,
 726                                                    BTRFS_BLOCK_GROUP_AVAIL);
 727                         }
 728                 }
 729                 btrfs_set_block_group_used(&cache->item, old_val);
 730                 total -= num;
 731                 blocknr += num;
 732         }
 733         return 0;
 734 }
 735
 736 static int try_remove_page(struct address_space *mapping, unsigned long index)
 737 {
 738         int ret;
 739         ret = invalidate_mapping_pages(mapping, index, index);
 740         return ret;
 741 }
 742
 743 int btrfs_copy_pinned(struct btrfs_root *root, struct radix_tree_root *copy)
 744 {
 745         unsigned long gang[8];
 746         u64 last = 0;
 747         struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
 748         int ret;
 749         int i;
 750
 751         while(1) {
 752                 ret = find_first_radix_bit(pinned_radix, gang, last,
 753                                            ARRAY_SIZE(gang));
 754                 if (!ret)
 755                         break;
 756                 for (i = 0 ; i < ret; i++) {
 757                         set_radix_bit(copy, gang[i]);
 758                         last = gang[i] + 1;
 759                 }
 760         }
 761         return 0;
 762 }
 763
 764 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
 765                                struct btrfs_root *root,
 766                                struct radix_tree_root *unpin_radix)
 767 {
 768         unsigned long gang[8];
 769         struct inode *btree_inode = root->fs_info->btree_inode;
 770         struct btrfs_block_group_cache *block_group;
 771         u64 first = 0;
 772         int ret;
 773         int i;
 774         struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
 775         struct radix_tree_root *extent_radix = &root->fs_info->extent_map_radix;
 776
 777         while(1) {
 778                 ret = find_first_radix_bit(unpin_radix, gang, 0,
 779                                            ARRAY_SIZE(gang));
 780                 if (!ret)
 781                         break;
 782                 if (!first)
 783                         first = gang[0];
 784                 for (i = 0; i < ret; i++) {
 785                         clear_radix_bit(pinned_radix, gang[i]);
 786                         clear_radix_bit(unpin_radix, gang[i]);
 787                         block_group = btrfs_lookup_block_group(root->fs_info,
 788                                                                gang[i]);
 789                         if (block_group) {
 790                                 WARN_ON(block_group->pinned == 0);
 791                                 block_group->pinned--;
 792                                 if (gang[i] < block_group->last_alloc)
 793                                         block_group->last_alloc = gang[i];
 794                                 if (gang[i] < block_group->last_prealloc)
 795                                         block_group->last_prealloc = gang[i];
 796                                 if (!block_group->data)
 797                                         set_radix_bit(extent_radix, gang[i]);
 798                         }
 799                         try_remove_page(btree_inode->i_mapping,
 800                                         gang[i] << (PAGE_CACHE_SHIFT -
 801                                                     btree_inode->i_blkbits));
 802                 }
 803         }
 804         return 0;
 805 }
 806
 807 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 808                                  btrfs_root *extent_root)
 809 {
 810         struct btrfs_key ins;
 811         struct btrfs_extent_item extent_item;
 812         int i;
 813         int ret;
 814         u64 super_blocks_used;
 815         struct btrfs_fs_info *info = extent_root->fs_info;
 816
 817         btrfs_set_extent_refs(&extent_item, 1);
 818         ins.offset = 1;
 819         ins.flags = 0;
 820         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 821         btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid);
 822
 823         for (i = 0; i < extent_root->fs_info->extent_tree_insert_nr; i++) {
 824                 ins.objectid = extent_root->fs_info->extent_tree_insert[i];
 825                 super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
 826                 btrfs_set_super_blocks_used(&info->super_copy,
 827                                             super_blocks_used + 1);
 828                 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
 829                                         sizeof(extent_item));
 830                 BUG_ON(ret);
 831         }
 832         extent_root->fs_info->extent_tree_insert_nr = 0;
 833         return 0;
 834 }
 835
 836 static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
 837 {
 838         int err;
 839         struct btrfs_header *header;
 840         struct buffer_head *bh;
 841
 842         if (!pending) {
 843                 bh = btrfs_find_tree_block(root, blocknr);
 844                 if (bh) {
 845                         if (buffer_uptodate(bh)) {
 846                                 u64 transid =
 847                                     root->fs_info->running_transaction->transid;
 848                                 header = btrfs_buffer_header(bh);
 849                                 if (btrfs_header_generation(header) ==
 850                                     transid) {
 851                                         btrfs_block_release(root, bh);
 852                                         return 0;
 853                                 }
 854                         }
 855                         btrfs_block_release(root, bh);
 856                 }
 857                 err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
 858                 if (!err) {
 859                         struct btrfs_block_group_cache *cache;
 860                         cache = btrfs_lookup_block_group(root->fs_info,
 861                                                          blocknr);
 862                         if (cache)
 863                                 cache->pinned++;
 864                 }
 865         } else {
 866                 err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
 867         }
 868         BUG_ON(err < 0);
 869         return 0;
 870 }
 871
 872 /*
 873  * remove an extent from the root, returns 0 on success
 874  */
 875 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 876                          *root, u64 blocknr, u64 num_blocks, int pin,
 877                          int mark_free)
 878 {
 879         struct btrfs_path *path;
 880         struct btrfs_key key;
 881         struct btrfs_fs_info *info = root->fs_info;
 882         struct btrfs_root *extent_root = info->extent_root;
 883         int ret;
 884         struct btrfs_extent_item *ei;
 885         struct btrfs_key ins;
 886         u32 refs;
 887
 888         key.objectid = blocknr;
 889         key.flags = 0;
 890         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 891         key.offset = num_blocks;
 892
 893         path = btrfs_alloc_path();
 894         if (!path)
 895                 return -ENOMEM;
 896
 897         ret = find_free_extent(trans, root, 0, 0, (u64)-1, 0, &ins, 0, 0, 0);
 898         if (ret) {
 899                 btrfs_free_path(path);
 900                 return ret;
 901         }
 902
 903         ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
 904         if (ret < 0)
 905                 return ret;
 906         BUG_ON(ret);
 907         ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
 908                             struct btrfs_extent_item);
 909         BUG_ON(ei->refs == 0);
 910         refs = btrfs_extent_refs(ei) - 1;
 911         btrfs_set_extent_refs(ei, refs);
 912         btrfs_mark_buffer_dirty(path->nodes[0]);
 913         if (refs == 0) {
 914                 u64 super_blocks_used;
 915
 916                 if (pin) {
 917                         ret = pin_down_block(root, blocknr, 0);
 918                         BUG_ON(ret);
 919                 }
 920
 921                 super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
 922                 btrfs_set_super_blocks_used(&info->super_copy,
 923                                             super_blocks_used - num_blocks);
 924                 ret = btrfs_del_item(trans, extent_root, path);
 925                 if (ret) {
 926                         return ret;
 927                 }
 928                 ret = update_block_group(trans, root, blocknr, num_blocks, 0,
 929                                          mark_free, 0);
 930                 BUG_ON(ret);
 931         }
 932         btrfs_free_path(path);
 933         finish_current_insert(trans, extent_root);
 934         return ret;
 935 }
 936
 937 /*
 938  * find all the blocks marked as pending in the radix tree and remove
 939  * them from the extent map
 940  */
 941 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 942                                btrfs_root *extent_root)
 943 {
 944         int ret;
 945         int wret;
 946         int err = 0;
 947         unsigned long gang[4];
 948         int i;
 949         struct radix_tree_root *pending_radix;
 950         struct radix_tree_root *pinned_radix;
 951         struct btrfs_block_group_cache *cache;
 952
 953         pending_radix = &extent_root->fs_info->pending_del_radix;
 954         pinned_radix = &extent_root->fs_info->pinned_radix;
 955
 956         while(1) {
 957                 ret = find_first_radix_bit(pending_radix, gang, 0,
 958                                            ARRAY_SIZE(gang));
 959                 if (!ret)
 960                         break;
 961                 for (i = 0; i < ret; i++) {
 962                         wret = set_radix_bit(pinned_radix, gang[i]);
 963                         if (wret == 0) {
 964                                 cache =
 965                                   btrfs_lookup_block_group(extent_root->fs_info,
 966                                                            gang[i]);
 967                                 if (cache)
 968                                         cache->pinned++;
 969                         }
 970                         if (wret < 0) {
 971                                 printk(KERN_CRIT "set_radix_bit, err %d\n",
 972                                        wret);
 973                                 BUG_ON(wret < 0);
 974                         }
 975                         wret = clear_radix_bit(pending_radix, gang[i]);
 976                         BUG_ON(wret);
 977                         wret = __free_extent(trans, extent_root,
 978                                              gang[i], 1, 0, 0);
 979                         if (wret)
 980                                 err = wret;
 981                 }
 982         }
 983         return err;
 984 }
 985
 986 /*
 987  * remove an extent from the root, returns 0 on success
 988  */
 989 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 990                       *root, u64 blocknr, u64 num_blocks, int pin)
 991 {
 992         struct btrfs_root *extent_root = root->fs_info->extent_root;
 993         int pending_ret;
 994         int ret;
 995
 996         if (root == extent_root) {
 997                 pin_down_block(root, blocknr, 1);
 998                 return 0;
 999         }
1000         ret = __free_extent(trans, root, blocknr, num_blocks, pin, pin == 0);
1001         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1002         return ret ? ret : pending_ret;
1003 }
1004
1005 /*
1006  * walks the btree of allocated extents and find a hole of a given size.
1007  * The key ins is changed to record the hole:
1008  * ins->objectid == block start
1009  * ins->flags = BTRFS_EXTENT_ITEM_KEY
1010  * ins->offset == number of blocks
1011  * Any available blocks before search_start are skipped.
1012  */
1013 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1014                             *orig_root, u64 num_blocks, u64 search_start, u64
1015                             search_end, u64 hint_block,
1016                             struct btrfs_key *ins, u64 exclude_start,
1017                             u64 exclude_nr, int data)
1018 {
1019         struct btrfs_path *path;
1020         struct btrfs_key key;
1021         int ret;
1022         u64 hole_size = 0;
1023         int slot = 0;
1024         u64 last_block = 0;
1025         u64 test_block;
1026         u64 orig_search_start = search_start;
1027         int start_found;
1028         struct btrfs_leaf *l;
1029         struct btrfs_root * root = orig_root->fs_info->extent_root;
1030         struct btrfs_fs_info *info = root->fs_info;
1031         int total_needed = num_blocks;
1032         int total_found = 0;
1033         int fill_prealloc = 0;
1034         int level;
1035         struct btrfs_block_group_cache *block_group;
1036         int full_scan = 0;
1037         int wrapped = 0;
1038         u64 limit;
1039
1040         ins->flags = 0;
1041         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1042
1043         level = btrfs_header_level(btrfs_buffer_header(root->node));
1044         if (num_blocks == 0) {
1045                 fill_prealloc = 1;
1046                 num_blocks = 1;
1047                 total_needed = (min(level + 1, BTRFS_MAX_LEVEL) + 2) * 3;
1048         }
1049         if (fill_prealloc) {
1050                 u64 first;
1051                 int nr = info->extent_tree_prealloc_nr;
1052                 first = info->extent_tree_prealloc[nr - 1];
1053                 if (info->extent_tree_prealloc_nr >= total_needed &&
1054                     first >= search_start) {
1055                         ins->objectid = info->extent_tree_prealloc[0];
1056                         ins->offset = 1;
1057                         return 0;
1058                 }
1059                 info->extent_tree_prealloc_nr = 0;
1060         }
1061         if (search_end == (u64)-1)
1062                 search_end = btrfs_super_total_blocks(&info->super_copy);
1063         if (hint_block) {
1064                 block_group = btrfs_lookup_block_group(info, hint_block);
1065                 block_group = btrfs_find_block_group(root, block_group,
1066                                                      hint_block, data, 1);
1067         } else {
1068                 block_group = btrfs_find_block_group(root,
1069                                                      trans->block_group, 0,
1070                                                      data, 1);
1071         }
1072
1073         path = btrfs_alloc_path();
1074
1075 check_failed:
1076         if (!block_group->data)
1077                 search_start = find_search_start(root, &block_group,
1078                                                  search_start, total_needed);
1079         else if (!full_scan)
1080                 search_start = max(block_group->last_alloc, search_start);
1081
1082         btrfs_init_path(path);
1083         ins->objectid = search_start;
1084         ins->offset = 0;
1085         start_found = 0;
1086
1087         ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1088         if (ret < 0)
1089                 goto error;
1090
1091         if (path->slots[0] > 0) {
1092                 path->slots[0]--;
1093         }
1094
1095         l = btrfs_buffer_leaf(path->nodes[0]);
1096         btrfs_disk_key_to_cpu(&key, &l->items[path->slots[0]].key);
1097         /*
1098          * a rare case, go back one key if we hit a block group item
1099          * instead of an extent item
1100          */
1101         if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
1102             key.objectid + key.offset >= search_start) {
1103                 ins->objectid = key.objectid;
1104                 ins->offset = key.offset - 1;
1105                 btrfs_release_path(root, path);
1106                 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1107                 if (ret < 0)
1108                         goto error;
1109
1110                 if (path->slots[0] > 0) {
1111                         path->slots[0]--;
1112                 }
1113         }
1114
1115         while (1) {
1116                 l = btrfs_buffer_leaf(path->nodes[0]);
1117                 slot = path->slots[0];
1118                 if (slot >= btrfs_header_nritems(&l->header)) {
1119                         if (fill_prealloc) {
1120                                 info->extent_tree_prealloc_nr = 0;
1121                                 total_found = 0;
1122                         }
1123                         if (start_found)
1124                                 limit = last_block +
1125                                         (block_group->key.offset >> 1);
1126                         else
1127                                 limit = search_start +
1128                                         (block_group->key.offset >> 1);
1129                         ret = btrfs_next_leaf(root, path);
1130                         if (ret == 0)
1131                                 continue;
1132                         if (ret < 0)
1133                                 goto error;
1134                         if (!start_found) {
1135                                 ins->objectid = search_start;
1136                                 ins->offset = search_end - search_start;
1137                                 start_found = 1;
1138                                 goto check_pending;
1139                         }
1140                         ins->objectid = last_block > search_start ?
1141                                         last_block : search_start;
1142                         ins->offset = search_end - ins->objectid;
1143                         goto check_pending;
1144                 }
1145
1146                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
1147                 if (key.objectid >= search_start && key.objectid > last_block &&
1148                     start_found) {
1149                         if (last_block < search_start)
1150                                 last_block = search_start;
1151                         hole_size = key.objectid - last_block;
1152                         if (hole_size >= num_blocks) {
1153                                 ins->objectid = last_block;
1154                                 ins->offset = hole_size;
1155                                 goto check_pending;
1156                         }
1157                 }
1158
1159                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
1160                         goto next;
1161
1162                 start_found = 1;
1163                 last_block = key.objectid + key.offset;
1164                 if (!full_scan && last_block >= block_group->key.objectid +
1165                     block_group->key.offset) {
1166                         btrfs_release_path(root, path);
1167                         search_start = block_group->key.objectid +
1168                                 block_group->key.offset * 2;
1169                         goto new_group;
1170                 }
1171 next:
1172                 path->slots[0]++;
1173                 cond_resched();
1174         }
1175 check_pending:
1176         /* we have to make sure we didn't find an extent that has already
1177          * been allocated by the map tree or the original allocation
1178          */
1179         btrfs_release_path(root, path);
1180         BUG_ON(ins->objectid < search_start);
1181
1182         if (ins->objectid + num_blocks >= search_end) {
1183                 if (full_scan) {
1184                         ret = -ENOSPC;
1185                         goto error;
1186                 }
1187                 search_start = orig_search_start;
1188                 if (wrapped)
1189                         full_scan = 1;
1190                 else
1191                         wrapped = 1;
1192                 goto new_group;
1193         }
1194         for (test_block = ins->objectid;
1195              test_block < ins->objectid + num_blocks; test_block++) {
1196                 if (test_radix_bit(&info->pinned_radix, test_block)) {
1197                         search_start = test_block + 1;
1198                         goto new_group;
1199                 }
1200         }
1201         if (!fill_prealloc && info->extent_tree_insert_nr) {
1202                 u64 last =
1203                   info->extent_tree_insert[info->extent_tree_insert_nr - 1];
1204                 if (ins->objectid + num_blocks >
1205                     info->extent_tree_insert[0] &&
1206                     ins->objectid <= last) {
1207                         search_start = last + 1;
1208                         WARN_ON(!full_scan);
1209                         goto new_group;
1210                 }
1211         }
1212         if (!fill_prealloc && info->extent_tree_prealloc_nr) {
1213                 u64 first =
1214                   info->extent_tree_prealloc[info->extent_tree_prealloc_nr - 1];
1215                 if (ins->objectid + num_blocks > first &&
1216                     ins->objectid <= info->extent_tree_prealloc[0]) {
1217                         search_start = info->extent_tree_prealloc[0] + 1;
1218                         goto new_group;
1219                 }
1220         }
1221         if (exclude_nr > 0 && (ins->objectid + num_blocks > exclude_start &&
1222             ins->objectid < exclude_start + exclude_nr)) {
1223                 search_start = exclude_start + exclude_nr;
1224                 goto new_group;
1225         }
1226         if (fill_prealloc) {
1227                 int nr;
1228                 test_block = ins->objectid;
1229                 if (test_block - info->extent_tree_prealloc[total_needed - 1] >=
1230                     leaf_range(root)) {
1231                         total_found = 0;
1232                         info->extent_tree_prealloc_nr = total_found;
1233                 }
1234                 while(test_block < ins->objectid + ins->offset &&
1235                       total_found < total_needed) {
1236                         nr = total_needed - total_found - 1;
1237                         BUG_ON(nr < 0);
1238                         info->extent_tree_prealloc[nr] = test_block;
1239                         total_found++;
1240                         test_block++;
1241                 }
1242                 if (total_found < total_needed) {
1243                         search_start = test_block;
1244                         goto new_group;
1245                 }
1246                 info->extent_tree_prealloc_nr = total_found;
1247         }
1248         if (!data) {
1249                 block_group = btrfs_lookup_block_group(info, ins->objectid);
1250                 if (block_group) {
1251                         if (fill_prealloc)
1252                                 block_group->last_prealloc =
1253                                      info->extent_tree_prealloc[total_needed-1];
1254                         else
1255                                 trans->block_group = block_group;
1256                 }
1257         }
1258         ins->offset = num_blocks;
1259         btrfs_free_path(path);
1260         return 0;
1261
1262 new_group:
1263         if (search_start + num_blocks >= search_end) {
1264                 search_start = orig_search_start;
1265                 if (full_scan) {
1266                         ret = -ENOSPC;
1267                         goto error;
1268                 }
1269                 if (wrapped)
1270                         full_scan = 1;
1271                 else
1272                         wrapped = 1;
1273         }
1274         block_group = btrfs_lookup_block_group(info, search_start);
1275         cond_resched();
1276         if (!full_scan)
1277                 block_group = btrfs_find_block_group(root, block_group,
1278                                                      search_start, data, 0);
1279         goto check_failed;
1280
1281 error:
1282         btrfs_release_path(root, path);
1283         btrfs_free_path(path);
1284         return ret;
1285 }
1286 /*
1287  * finds a free extent and does all the dirty work required for allocation
1288  * returns the key for the extent through ins, and a tree buffer for
1289  * the first block of the extent through buf.
1290  *
1291  * returns 0 if everything worked, non-zero otherwise.
1292  */
1293 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1294                        struct btrfs_root *root, u64 owner,
1295                        u64 num_blocks, u64 hint_block,
1296                        u64 search_end, struct btrfs_key *ins, int data)
1297 {
1298         int ret;
1299         int pending_ret;
1300         u64 super_blocks_used;
1301         u64 search_start = 0;
1302         u64 exclude_start = 0;
1303         u64 exclude_nr = 0;
1304         struct btrfs_fs_info *info = root->fs_info;
1305         struct btrfs_root *extent_root = info->extent_root;
1306         struct btrfs_extent_item extent_item;
1307         struct btrfs_key prealloc_key;
1308
1309         btrfs_set_extent_refs(&extent_item, 1);
1310         btrfs_set_extent_owner(&extent_item, owner);
1311
1312         if (root == extent_root) {
1313                 int nr;
1314                 BUG_ON(info->extent_tree_prealloc_nr == 0);
1315                 BUG_ON(num_blocks != 1);
1316                 ins->offset = 1;
1317                 info->extent_tree_prealloc_nr--;
1318                 nr = info->extent_tree_prealloc_nr;
1319                 ins->objectid = info->extent_tree_prealloc[nr];
1320                 info->extent_tree_insert[info->extent_tree_insert_nr++] =
1321                         ins->objectid;
1322                 ret = update_block_group(trans, root,
1323                                          ins->objectid, ins->offset, 1, 0, 0);
1324                 BUG_ON(ret);
1325                 return 0;
1326         }
1327
1328         /*
1329          * if we're doing a data allocation, preallocate room in the
1330          * extent tree first.  This way the extent tree blocks end up
1331          * in the correct block group.
1332          */
1333         if (data) {
1334                 ret = find_free_extent(trans, root, 0, 0,
1335                                        search_end, 0, &prealloc_key, 0, 0, 0);
1336                 BUG_ON(ret);
1337                 if (ret)
1338                         return ret;
1339                 exclude_nr = info->extent_tree_prealloc_nr;
1340                 exclude_start = info->extent_tree_prealloc[exclude_nr - 1];
1341         }
1342
1343         /* do the real allocation */
1344         ret = find_free_extent(trans, root, num_blocks, search_start,
1345                                search_end, hint_block, ins,
1346                                exclude_start, exclude_nr, data);
1347         BUG_ON(ret);
1348         if (ret)
1349                 return ret;
1350
1351         /*
1352          * if we're doing a metadata allocation, preallocate space in the
1353          * extent tree second.  This way, we don't create a tiny hole
1354          * in the allocation map between any unused preallocation blocks
1355          * and the metadata block we're actually allocating.  On disk,
1356          * it'll go:
1357          * [block we've allocated], [used prealloc 1], [ unused prealloc ]
1358          * The unused prealloc will get reused the next time around.
1359          */
1360         if (!data) {
1361                 exclude_start = ins->objectid;
1362                 exclude_nr = ins->offset;
1363                 hint_block = exclude_start + exclude_nr;
1364                 ret = find_free_extent(trans, root, 0, search_start,
1365                                        search_end, hint_block,
1366                                        &prealloc_key, exclude_start,
1367                                        exclude_nr, 0);
1368                 BUG_ON(ret);
1369                 if (ret)
1370                         return ret;
1371         }
1372
1373         super_blocks_used = btrfs_super_blocks_used(&info->super_copy);
1374         btrfs_set_super_blocks_used(&info->super_copy, super_blocks_used +
1375                                     num_blocks);
1376         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1377                                 sizeof(extent_item));
1378
1379         BUG_ON(ret);
1380         finish_current_insert(trans, extent_root);
1381         pending_ret = del_pending_extents(trans, extent_root);
1382         if (ret) {
1383                 return ret;
1384         }
1385         if (pending_ret) {
1386                 return pending_ret;
1387         }
1388         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1389                                  data);
1390         BUG_ON(ret);
1391         return 0;
1392 }
1393
1394 /*
1395  * helper function to allocate a block for a given tree
1396  * returns the tree buffer or NULL.
1397  */
1398 struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1399                                            struct btrfs_root *root, u64 hint)
1400 {
1401         struct btrfs_key ins;
1402         int ret;
1403         struct buffer_head *buf;
1404
1405         ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1406                                  1, hint, (unsigned long)-1, &ins, 0);
1407         if (ret) {
1408                 BUG_ON(ret > 0);
1409                 return ERR_PTR(ret);
1410         }
1411         buf = btrfs_find_create_tree_block(root, ins.objectid);
1412         if (!buf) {
1413                 btrfs_free_extent(trans, root, ins.objectid, 1, 0);
1414                 return ERR_PTR(-ENOMEM);
1415         }
1416         set_buffer_uptodate(buf);
1417         set_buffer_checked(buf);
1418         set_radix_bit(&trans->transaction->dirty_pages, buf->b_page->index);
1419         return buf;
1420 }
1421
1422 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
1423                          struct btrfs_root *root, struct buffer_head *cur)
1424 {
1425         struct btrfs_disk_key *key;
1426         struct btrfs_leaf *leaf;
1427         struct btrfs_file_extent_item *fi;
1428         int i;
1429         int nritems;
1430         int ret;
1431
1432         BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
1433         leaf = btrfs_buffer_leaf(cur);
1434         nritems = btrfs_header_nritems(&leaf->header);
1435         for (i = 0; i < nritems; i++) {
1436                 u64 disk_blocknr;
1437                 key = &leaf->items[i].key;
1438                 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
1439                         continue;
1440                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1441                 if (btrfs_file_extent_type(fi) == BTRFS_FILE_EXTENT_INLINE)
1442                         continue;
1443                 /*
1444                  * FIXME make sure to insert a trans record that
1445                  * repeats the snapshot del on crash
1446                  */
1447                 disk_blocknr = btrfs_file_extent_disk_blocknr(fi);
1448                 if (disk_blocknr == 0)
1449                         continue;
1450                 ret = btrfs_free_extent(trans, root, disk_blocknr,
1451                                         btrfs_file_extent_disk_num_blocks(fi),
1452                                         0);
1453                 BUG_ON(ret);
1454         }
1455         return 0;
1456 }
1457
1458 static void reada_walk_down(struct btrfs_root *root,
1459                             struct btrfs_node *node)
1460 {
1461         int i;
1462         u32 nritems;
1463         u64 blocknr;
1464         int ret;
1465         u32 refs;
1466
1467         nritems = btrfs_header_nritems(&node->header);
1468         for (i = 0; i < nritems; i++) {
1469                 blocknr = btrfs_node_blockptr(node, i);
1470                 ret = lookup_extent_ref(NULL, root, blocknr, 1, &refs);
1471                 BUG_ON(ret);
1472                 if (refs != 1)
1473                         continue;
1474                 ret = readahead_tree_block(root, blocknr);
1475                 if (ret)
1476                         break;
1477         }
1478 }
1479
1480 /*
1481  * helper function for drop_snapshot, this walks down the tree dropping ref
1482  * counts as it goes.
1483  */
1484 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1485                           *root, struct btrfs_path *path, int *level)
1486 {
1487         struct buffer_head *next;
1488         struct buffer_head *cur;
1489         u64 blocknr;
1490         int ret;
1491         u32 refs;
1492
1493         WARN_ON(*level < 0);
1494         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1495         ret = lookup_extent_ref(trans, root, bh_blocknr(path->nodes[*level]),
1496                                1, &refs);
1497         BUG_ON(ret);
1498         if (refs > 1)
1499                 goto out;
1500
1501         /*
1502          * walk down to the last node level and free all the leaves
1503          */
1504         while(*level >= 0) {
1505                 WARN_ON(*level < 0);
1506                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1507                 cur = path->nodes[*level];
1508
1509                 if (*level > 0 && path->slots[*level] == 0)
1510                         reada_walk_down(root, btrfs_buffer_node(cur));
1511
1512                 if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
1513                         WARN_ON(1);
1514
1515                 if (path->slots[*level] >=
1516                     btrfs_header_nritems(btrfs_buffer_header(cur)))
1517                         break;
1518                 if (*level == 0) {
1519                         ret = drop_leaf_ref(trans, root, cur);
1520                         BUG_ON(ret);
1521                         break;
1522                 }
1523                 blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
1524                                               path->slots[*level]);
1525                 ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
1526                 BUG_ON(ret);
1527                 if (refs != 1) {
1528                         path->slots[*level]++;
1529                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
1530                         BUG_ON(ret);
1531                         continue;
1532                 }
1533                 next = read_tree_block(root, blocknr);
1534                 WARN_ON(*level <= 0);
1535                 if (path->nodes[*level-1])
1536                         btrfs_block_release(root, path->nodes[*level-1]);
1537                 path->nodes[*level-1] = next;
1538                 *level = btrfs_header_level(btrfs_buffer_header(next));
1539                 path->slots[*level] = 0;
1540         }
1541 out:
1542         WARN_ON(*level < 0);
1543         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1544         ret = btrfs_free_extent(trans, root,
1545                                 bh_blocknr(path->nodes[*level]), 1, 1);
1546         btrfs_block_release(root, path->nodes[*level]);
1547         path->nodes[*level] = NULL;
1548         *level += 1;
1549         BUG_ON(ret);
1550         return 0;
1551 }
1552
1553 /*
1554  * helper for dropping snapshots.  This walks back up the tree in the path
1555  * to find the first node higher up where we haven't yet gone through
1556  * all the slots
1557  */
1558 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1559                         *root, struct btrfs_path *path, int *level)
1560 {
1561         int i;
1562         int slot;
1563         int ret;
1564         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1565                 slot = path->slots[i];
1566                 if (slot < btrfs_header_nritems(
1567                     btrfs_buffer_header(path->nodes[i])) - 1) {
1568                         path->slots[i]++;
1569                         *level = i;
1570                         return 0;
1571                 } else {
1572                         ret = btrfs_free_extent(trans, root,
1573                                                 bh_blocknr(path->nodes[*level]),
1574                                                 1, 1);
1575                         BUG_ON(ret);
1576                         btrfs_block_release(root, path->nodes[*level]);
1577                         path->nodes[*level] = NULL;
1578                         *level = i + 1;
1579                 }
1580         }
1581         return 1;
1582 }
1583
1584 /*
1585  * drop the reference count on the tree rooted at 'snap'.  This traverses
1586  * the tree freeing any blocks that have a ref count of zero after being
1587  * decremented.
1588  */
1589 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
1590                         *root, struct buffer_head *snap)
1591 {
1592         int ret = 0;
1593         int wret;
1594         int level;
1595         struct btrfs_path *path;
1596         int i;
1597         int orig_level;
1598
1599         path = btrfs_alloc_path();
1600         BUG_ON(!path);
1601
1602         level = btrfs_header_level(btrfs_buffer_header(snap));
1603         orig_level = level;
1604         path->nodes[level] = snap;
1605         path->slots[level] = 0;
1606         while(1) {
1607                 wret = walk_down_tree(trans, root, path, &level);
1608                 if (wret > 0)
1609                         break;
1610                 if (wret < 0)
1611                         ret = wret;
1612
1613                 wret = walk_up_tree(trans, root, path, &level);
1614                 if (wret > 0)
1615                         break;
1616                 if (wret < 0)
1617                         ret = wret;
1618         }
1619         for (i = 0; i <= orig_level; i++) {
1620                 if (path->nodes[i]) {
1621                         btrfs_block_release(root, path->nodes[i]);
1622                 }
1623         }
1624         btrfs_free_path(path);
1625         return ret;
1626 }
1627
1628 static int free_block_group_radix(struct radix_tree_root *radix)
1629 {
1630         int ret;
1631         struct btrfs_block_group_cache *cache[8];
1632         int i;
1633
1634         while(1) {
1635                 ret = radix_tree_gang_lookup(radix, (void **)cache, 0,
1636                                              ARRAY_SIZE(cache));
1637                 if (!ret)
1638                         break;
1639                 for (i = 0; i < ret; i++) {
1640                         radix_tree_delete(radix, cache[i]->key.objectid +
1641                                           cache[i]->key.offset - 1);
1642                         kfree(cache[i]);
1643                 }
1644         }
1645         return 0;
1646 }
1647
1648 int btrfs_free_block_groups(struct btrfs_fs_info *info)
1649 {
1650         int ret;
1651         int ret2;
1652         unsigned long gang[16];
1653         int i;
1654
1655         ret = free_block_group_radix(&info->block_group_radix);
1656         ret2 = free_block_group_radix(&info->block_group_data_radix);
1657         if (ret)
1658                 return ret;
1659         if (ret2)
1660                 return ret2;
1661
1662         while(1) {
1663                 ret = find_first_radix_bit(&info->extent_map_radix,
1664                                            gang, 0, ARRAY_SIZE(gang));
1665                 if (!ret)
1666                         break;
1667                 for (i = 0; i < ret; i++) {
1668                         clear_radix_bit(&info->extent_map_radix, gang[i]);
1669                 }
1670         }
1671         return 0;
1672 }
1673
1674 int btrfs_read_block_groups(struct btrfs_root *root)
1675 {
1676         struct btrfs_path *path;
1677         int ret;
1678         int err = 0;
1679         struct btrfs_block_group_item *bi;
1680         struct btrfs_block_group_cache *cache;
1681         struct btrfs_fs_info *info = root->fs_info;
1682         struct radix_tree_root *radix;
1683         struct btrfs_key key;
1684         struct btrfs_key found_key;
1685         struct btrfs_leaf *leaf;
1686         u64 group_size_blocks;
1687         u64 used;
1688
1689         group_size_blocks = BTRFS_BLOCK_GROUP_SIZE >>
1690                 root->fs_info->sb->s_blocksize_bits;
1691         root = info->extent_root;
1692         key.objectid = 0;
1693         key.offset = group_size_blocks;
1694         key.flags = 0;
1695         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
1696
1697         path = btrfs_alloc_path();
1698         if (!path)
1699                 return -ENOMEM;
1700
1701         while(1) {
1702                 ret = btrfs_search_slot(NULL, info->extent_root,
1703                                         &key, path, 0, 0);
1704                 if (ret != 0) {
1705                         err = ret;
1706                         break;
1707                 }
1708                 leaf = btrfs_buffer_leaf(path->nodes[0]);
1709                 btrfs_disk_key_to_cpu(&found_key,
1710                                       &leaf->items[path->slots[0]].key);
1711                 cache = kmalloc(sizeof(*cache), GFP_NOFS);
1712                 if (!cache) {
1713                         err = -1;
1714                         break;
1715                 }
1716
1717                 bi = btrfs_item_ptr(leaf, path->slots[0],
1718                                     struct btrfs_block_group_item);
1719                 if (bi->flags & BTRFS_BLOCK_GROUP_DATA) {
1720                         radix = &info->block_group_data_radix;
1721                         cache->data = 1;
1722                 } else {
1723                         radix = &info->block_group_radix;
1724                         cache->data = 0;
1725                 }
1726
1727                 memcpy(&cache->item, bi, sizeof(*bi));
1728                 memcpy(&cache->key, &found_key, sizeof(found_key));
1729                 cache->last_alloc = cache->key.objectid;
1730                 cache->first_free = cache->key.objectid;
1731                 cache->last_prealloc = cache->key.objectid;
1732                 cache->pinned = 0;
1733                 cache->cached = 0;
1734
1735                 cache->radix = radix;
1736
1737                 key.objectid = found_key.objectid + found_key.offset;
1738                 btrfs_release_path(root, path);
1739                 ret = radix_tree_insert(radix, found_key.objectid +
1740                                         found_key.offset - 1,
1741                                         (void *)cache);
1742                 BUG_ON(ret);
1743                 used = btrfs_block_group_used(bi);
1744                 if (used < div_factor(key.offset, 8)) {
1745                         radix_tree_tag_set(radix, found_key.objectid +
1746                                            found_key.offset - 1,
1747                                            BTRFS_BLOCK_GROUP_AVAIL);
1748                 }
1749                 if (key.objectid >=
1750                     btrfs_super_total_blocks(&info->super_copy))
1751                         break;
1752         }
1753
1754         btrfs_free_path(path);
1755         return 0;
1756 }