fs/btrfs/extent-tree.c

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