fs/btrfs/extent-tree.c

   1 #include <linux/module.h>
   2 #include "ctree.h"
   3 #include "disk-io.h"
   4 #include "print-tree.h"
   5 #include "transaction.h"
   6
   7 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
   8                             *orig_root, u64 num_blocks, u64 search_start, u64
   9                             search_end, struct btrfs_key *ins);
  10 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  11                                  btrfs_root *extent_root);
  12 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  13                                btrfs_root *extent_root);
  14
  15 static int find_search_start(struct btrfs_root *root, int data)
  16 {
  17         struct btrfs_block_group_cache *cache[8];
  18         struct btrfs_fs_info *info = root->fs_info;
  19         u64 used;
  20         u64 last;
  21         int i;
  22         int ret;
  23
  24         cache[0] = info->block_group_cache;
  25         if (!cache[0])
  26                 goto find_new;
  27         used = btrfs_block_group_used(&cache[0]->item);
  28         if (used < (cache[0]->key.offset * 3 / 2))
  29                 return 0;
  30 find_new:
  31         last = 0;
  32         while(1) {
  33                 ret = radix_tree_gang_lookup_tag(&info->block_group_radix,
  34                                                  (void **)cache,
  35                                                  last, ARRAY_SIZE(cache),
  36                                                  BTRFS_BLOCK_GROUP_DIRTY);
  37                 if (!ret)
  38                         break;
  39                 for (i = 0; i < ret; i++) {
  40                         used = btrfs_block_group_used(&cache[i]->item);
  41                         if (used < (cache[i]->key.offset * 3 / 2)) {
  42                                 info->block_group_cache = cache[i];
  43                                 cache[i]->last_alloc = cache[i]->first_free;
  44                                 return 0;
  45                         }
  46                         last = cache[i]->key.objectid +
  47                                 cache[i]->key.offset - 1;
  48                 }
  49         }
  50         last = 0;
  51         while(1) {
  52                 ret = radix_tree_gang_lookup(&info->block_group_radix,
  53                                                  (void **)cache,
  54                                                  last, ARRAY_SIZE(cache));
  55                 if (!ret)
  56                         break;
  57                 for (i = 0; i < ret; i++) {
  58                         used = btrfs_block_group_used(&cache[i]->item);
  59                         if (used < (cache[i]->key.offset * 3 / 2)) {
  60                                 info->block_group_cache = cache[i];
  61                                 cache[i]->last_alloc = cache[i]->first_free;
  62                                 return 0;
  63                         }
  64                         last = cache[i]->key.objectid +
  65                                 cache[i]->key.offset - 1;
  66                 }
  67         }
  68         info->block_group_cache = NULL;
  69         return 0;
  70 }
  71
  72 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
  73                                 struct btrfs_root *root,
  74                                 u64 blocknr, u64 num_blocks)
  75 {
  76         struct btrfs_path *path;
  77         int ret;
  78         struct btrfs_key key;
  79         struct btrfs_leaf *l;
  80         struct btrfs_extent_item *item;
  81         struct btrfs_key ins;
  82         u32 refs;
  83
  84         find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
  85                          &ins);
  86         path = btrfs_alloc_path();
  87         BUG_ON(!path);
  88         btrfs_init_path(path);
  89         key.objectid = blocknr;
  90         key.flags = 0;
  91         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  92         key.offset = num_blocks;
  93         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  94                                 0, 1);
  95         if (ret != 0) {
  96 printk("can't find block %Lu %Lu\n", blocknr, num_blocks);
  97                 BUG();
  98         }
  99         BUG_ON(ret != 0);
 100         l = btrfs_buffer_leaf(path->nodes[0]);
 101         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 102         refs = btrfs_extent_refs(item);
 103         btrfs_set_extent_refs(item, refs + 1);
 104         btrfs_mark_buffer_dirty(path->nodes[0]);
 105
 106         btrfs_release_path(root->fs_info->extent_root, path);
 107         btrfs_free_path(path);
 108         finish_current_insert(trans, root->fs_info->extent_root);
 109         del_pending_extents(trans, root->fs_info->extent_root);
 110         return 0;
 111 }
 112
 113 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
 114                              struct btrfs_root *root, u64 blocknr,
 115                              u64 num_blocks, u32 *refs)
 116 {
 117         struct btrfs_path *path;
 118         int ret;
 119         struct btrfs_key key;
 120         struct btrfs_leaf *l;
 121         struct btrfs_extent_item *item;
 122
 123         path = btrfs_alloc_path();
 124         btrfs_init_path(path);
 125         key.objectid = blocknr;
 126         key.offset = num_blocks;
 127         key.flags = 0;
 128         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 129         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 130                                 0, 0);
 131         if (ret != 0)
 132                 BUG();
 133         l = btrfs_buffer_leaf(path->nodes[0]);
 134         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 135         *refs = btrfs_extent_refs(item);
 136         btrfs_release_path(root->fs_info->extent_root, path);
 137         btrfs_free_path(path);
 138         return 0;
 139 }
 140
 141 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
 142                        struct btrfs_root *root)
 143 {
 144         return btrfs_inc_extent_ref(trans, root, bh_blocknr(root->node), 1);
 145 }
 146
 147 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 148                   struct buffer_head *buf)
 149 {
 150         u64 blocknr;
 151         struct btrfs_node *buf_node;
 152         struct btrfs_leaf *buf_leaf;
 153         struct btrfs_disk_key *key;
 154         struct btrfs_file_extent_item *fi;
 155         int i;
 156         int leaf;
 157         int ret;
 158
 159         if (!root->ref_cows)
 160                 return 0;
 161         buf_node = btrfs_buffer_node(buf);
 162         leaf = btrfs_is_leaf(buf_node);
 163         buf_leaf = btrfs_buffer_leaf(buf);
 164         for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
 165                 if (leaf) {
 166                         key = &buf_leaf->items[i].key;
 167                         if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
 168                                 continue;
 169                         fi = btrfs_item_ptr(buf_leaf, i,
 170                                             struct btrfs_file_extent_item);
 171                         if (btrfs_file_extent_type(fi) ==
 172                             BTRFS_FILE_EXTENT_INLINE)
 173                                 continue;
 174                         ret = btrfs_inc_extent_ref(trans, root,
 175                                     btrfs_file_extent_disk_blocknr(fi),
 176                                     btrfs_file_extent_disk_num_blocks(fi));
 177                         BUG_ON(ret);
 178                 } else {
 179                         blocknr = btrfs_node_blockptr(buf_node, i);
 180                         ret = btrfs_inc_extent_ref(trans, root, blocknr, 1);
 181                         BUG_ON(ret);
 182                 }
 183         }
 184         return 0;
 185 }
 186
 187 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 188                                  struct btrfs_root *root,
 189                                  struct btrfs_path *path,
 190                                  struct btrfs_block_group_cache *cache)
 191 {
 192         int ret;
 193         int pending_ret;
 194         struct btrfs_root *extent_root = root->fs_info->extent_root;
 195         struct btrfs_block_group_item *bi;
 196         struct btrfs_key ins;
 197
 198         find_free_extent(trans, extent_root, 0, 0, (u64)-1, &ins);
 199         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 200         BUG_ON(ret);
 201         bi = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
 202                             struct btrfs_block_group_item);
 203         memcpy(bi, &cache->item, sizeof(*bi));
 204         mark_buffer_dirty(path->nodes[0]);
 205         btrfs_release_path(extent_root, path);
 206
 207         finish_current_insert(trans, extent_root);
 208         pending_ret = del_pending_extents(trans, extent_root);
 209         if (ret)
 210                 return ret;
 211         if (pending_ret)
 212                 return pending_ret;
 213         return 0;
 214
 215 }
 216
 217 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 218                                     struct btrfs_root *root)
 219 {
 220         struct btrfs_block_group_cache *cache[8];
 221         int ret;
 222         int err = 0;
 223         int werr = 0;
 224         struct radix_tree_root *radix = &root->fs_info->block_group_radix;
 225         int i;
 226         struct btrfs_path *path;
 227
 228         path = btrfs_alloc_path();
 229         if (!path)
 230                 return -ENOMEM;
 231
 232         while(1) {
 233                 ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
 234                                                  0, ARRAY_SIZE(cache),
 235                                                  BTRFS_BLOCK_GROUP_DIRTY);
 236                 if (!ret)
 237                         break;
 238                 for (i = 0; i < ret; i++) {
 239                         radix_tree_tag_clear(radix, cache[i]->key.objectid +
 240                                              cache[i]->key.offset - 1,
 241                                              BTRFS_BLOCK_GROUP_DIRTY);
 242                         err = write_one_cache_group(trans, root,
 243                                                     path, cache[i]);
 244                         if (err)
 245                                 werr = err;
 246                 }
 247         }
 248         btrfs_free_path(path);
 249         return werr;
 250 }
 251
 252 static int update_block_group(struct btrfs_trans_handle *trans,
 253                               struct btrfs_root *root,
 254                               u64 blocknr, u64 num, int alloc)
 255 {
 256         struct btrfs_block_group_cache *cache;
 257         struct btrfs_fs_info *info = root->fs_info;
 258         u64 total = num;
 259         u64 old_val;
 260         u64 block_in_group;
 261         int ret;
 262         while(total) {
 263                 ret = radix_tree_gang_lookup(&info->block_group_radix,
 264                                              (void **)&cache, blocknr, 1);
 265                 if (!ret) {
 266                         printk(KERN_CRIT "blocknr %Lu lookup failed\n",
 267                                blocknr);
 268                         return -1;
 269                 }
 270                 block_in_group = blocknr - cache->key.objectid;
 271                 WARN_ON(block_in_group > cache->key.offset);
 272                 radix_tree_tag_set(&info->block_group_radix,
 273                                    cache->key.objectid + cache->key.offset - 1,
 274                                    BTRFS_BLOCK_GROUP_DIRTY);
 275
 276                 old_val = btrfs_block_group_used(&cache->item);
 277                 num = min(total, cache->key.offset - block_in_group);
 278                 total -= num;
 279                 blocknr += num;
 280                 if (alloc) {
 281                         old_val += num;
 282                         if (blocknr > cache->last_alloc)
 283                                 cache->last_alloc = blocknr;
 284                 } else {
 285                         old_val -= num;
 286                         if (blocknr < cache->first_free)
 287                                 cache->first_free = blocknr;
 288                 }
 289                 btrfs_set_block_group_used(&cache->item, old_val);
 290         }
 291         return 0;
 292 }
 293
 294 static int try_remove_page(struct address_space *mapping, unsigned long index)
 295 {
 296         int ret;
 297         ret = invalidate_mapping_pages(mapping, index, index);
 298         return ret;
 299 }
 300
 301 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
 302                                btrfs_root *root)
 303 {
 304         unsigned long gang[8];
 305         struct inode *btree_inode = root->fs_info->btree_inode;
 306         u64 first = 0;
 307         int ret;
 308         int i;
 309         struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
 310
 311         while(1) {
 312                 ret = find_first_radix_bit(pinned_radix, gang,
 313                                            ARRAY_SIZE(gang));
 314                 if (!ret)
 315                         break;
 316                 if (!first)
 317                         first = gang[0];
 318                 for (i = 0; i < ret; i++) {
 319                         clear_radix_bit(pinned_radix, gang[i]);
 320                         try_remove_page(btree_inode->i_mapping,
 321                                         gang[i] << (PAGE_CACHE_SHIFT -
 322                                                     btree_inode->i_blkbits));
 323                 }
 324         }
 325         if (root->fs_info->block_group_cache) {
 326                 root->fs_info->block_group_cache->last_alloc =
 327                         root->fs_info->block_group_cache->first_free;
 328         }
 329         return 0;
 330 }
 331
 332 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 333                                  btrfs_root *extent_root)
 334 {
 335         struct btrfs_key ins;
 336         struct btrfs_extent_item extent_item;
 337         int i;
 338         int ret;
 339         u64 super_blocks_used;
 340         struct btrfs_fs_info *info = extent_root->fs_info;
 341
 342         btrfs_set_extent_refs(&extent_item, 1);
 343         ins.offset = 1;
 344         ins.flags = 0;
 345         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 346         btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid);
 347
 348         for (i = 0; i < extent_root->fs_info->extent_tree_insert_nr; i++) {
 349                 ins.objectid = extent_root->fs_info->extent_tree_insert[i];
 350                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 351                 btrfs_set_super_blocks_used(info->disk_super,
 352                                             super_blocks_used + 1);
 353                 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
 354                                         sizeof(extent_item));
 355                 BUG_ON(ret);
 356         }
 357         extent_root->fs_info->extent_tree_insert_nr = 0;
 358         extent_root->fs_info->extent_tree_prealloc_nr = 0;
 359         return 0;
 360 }
 361
 362 static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
 363 {
 364         int err;
 365         struct btrfs_header *header;
 366         struct buffer_head *bh;
 367
 368         if (!pending) {
 369                 bh = btrfs_find_tree_block(root, blocknr);
 370                 if (bh) {
 371                         if (buffer_uptodate(bh)) {
 372                                 u64 transid =
 373                                     root->fs_info->running_transaction->transid;
 374                                 header = btrfs_buffer_header(bh);
 375                                 if (btrfs_header_generation(header) ==
 376                                     transid) {
 377                                         btrfs_block_release(root, bh);
 378                                         return 0;
 379                                 }
 380                         }
 381                         btrfs_block_release(root, bh);
 382                 }
 383                 err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
 384         } else {
 385                 err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
 386         }
 387         BUG_ON(err);
 388         return 0;
 389 }
 390
 391 /*
 392  * remove an extent from the root, returns 0 on success
 393  */
 394 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 395                          *root, u64 blocknr, u64 num_blocks, int pin)
 396 {
 397         struct btrfs_path *path;
 398         struct btrfs_key key;
 399         struct btrfs_fs_info *info = root->fs_info;
 400         struct btrfs_root *extent_root = info->extent_root;
 401         int ret;
 402         struct btrfs_extent_item *ei;
 403         struct btrfs_key ins;
 404         u32 refs;
 405
 406         key.objectid = blocknr;
 407         key.flags = 0;
 408         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 409         key.offset = num_blocks;
 410
 411         find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
 412         path = btrfs_alloc_path();
 413         BUG_ON(!path);
 414         btrfs_init_path(path);
 415
 416         ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
 417         if (ret) {
 418                 printk("failed to find %Lu\n", key.objectid);
 419                 btrfs_print_tree(extent_root, extent_root->node);
 420                 printk("failed to find %Lu\n", key.objectid);
 421                 BUG();
 422         }
 423         ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
 424                             struct btrfs_extent_item);
 425         BUG_ON(ei->refs == 0);
 426         refs = btrfs_extent_refs(ei) - 1;
 427         btrfs_set_extent_refs(ei, refs);
 428         btrfs_mark_buffer_dirty(path->nodes[0]);
 429         if (refs == 0) {
 430                 u64 super_blocks_used;
 431
 432                 if (pin) {
 433                         ret = pin_down_block(root, blocknr, 0);
 434                         BUG_ON(ret);
 435                 }
 436
 437                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 438                 btrfs_set_super_blocks_used(info->disk_super,
 439                                             super_blocks_used - num_blocks);
 440                 ret = btrfs_del_item(trans, extent_root, path);
 441                 if (ret)
 442                         BUG();
 443                 ret = update_block_group(trans, root, blocknr, num_blocks, 0);
 444                 BUG_ON(ret);
 445         }
 446         btrfs_release_path(extent_root, path);
 447         btrfs_free_path(path);
 448         finish_current_insert(trans, extent_root);
 449         return ret;
 450 }
 451
 452 /*
 453  * find all the blocks marked as pending in the radix tree and remove
 454  * them from the extent map
 455  */
 456 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 457                                btrfs_root *extent_root)
 458 {
 459         int ret;
 460         int wret;
 461         int err = 0;
 462         unsigned long gang[4];
 463         int i;
 464         struct radix_tree_root *pending_radix;
 465         struct radix_tree_root *pinned_radix;
 466
 467         pending_radix = &extent_root->fs_info->pending_del_radix;
 468         pinned_radix = &extent_root->fs_info->pinned_radix;
 469
 470         while(1) {
 471                 ret = find_first_radix_bit(pending_radix, gang,
 472                                            ARRAY_SIZE(gang));
 473                 if (!ret)
 474                         break;
 475                 for (i = 0; i < ret; i++) {
 476                         wret = set_radix_bit(pinned_radix, gang[i]);
 477                         BUG_ON(wret);
 478                         wret = clear_radix_bit(pending_radix, gang[i]);
 479                         BUG_ON(wret);
 480                         wret = __free_extent(trans, extent_root,
 481                                              gang[i], 1, 0);
 482                         if (wret)
 483                                 err = wret;
 484                 }
 485         }
 486         return err;
 487 }
 488
 489 /*
 490  * remove an extent from the root, returns 0 on success
 491  */
 492 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 493                       *root, u64 blocknr, u64 num_blocks, int pin)
 494 {
 495         struct btrfs_root *extent_root = root->fs_info->extent_root;
 496         int pending_ret;
 497         int ret;
 498
 499         if (root == extent_root) {
 500                 pin_down_block(root, blocknr, 1);
 501                 return 0;
 502         }
 503         ret = __free_extent(trans, root, blocknr, num_blocks, pin);
 504         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
 505         return ret ? ret : pending_ret;
 506 }
 507
 508 /*
 509  * walks the btree of allocated extents and find a hole of a given size.
 510  * The key ins is changed to record the hole:
 511  * ins->objectid == block start
 512  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 513  * ins->offset == number of blocks
 514  * Any available blocks before search_start are skipped.
 515  */
 516 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 517                             *orig_root, u64 num_blocks, u64 search_start, u64
 518                             search_end, struct btrfs_key *ins)
 519 {
 520         struct btrfs_path *path;
 521         struct btrfs_key key;
 522         int ret;
 523         u64 hole_size = 0;
 524         int slot = 0;
 525         u64 last_block = 0;
 526         u64 test_block;
 527         int start_found;
 528         struct btrfs_leaf *l;
 529         struct btrfs_root * root = orig_root->fs_info->extent_root;
 530         struct btrfs_fs_info *info = root->fs_info;
 531         int total_needed = num_blocks;
 532         int total_found = 0;
 533         int fill_prealloc = 0;
 534         int level;
 535
 536         path = btrfs_alloc_path();
 537         ins->flags = 0;
 538         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 539
 540         level = btrfs_header_level(btrfs_buffer_header(root->node));
 541         if (num_blocks == 0) {
 542                 fill_prealloc = 1;
 543                 num_blocks = 1;
 544                 total_needed = min(level + 2, BTRFS_MAX_LEVEL) * 3;
 545         }
 546         find_search_start(root, 0);
 547         if (info->block_group_cache &&
 548             info->block_group_cache->last_alloc > search_start)
 549                 search_start = info->block_group_cache->last_alloc;
 550
 551 check_failed:
 552         btrfs_init_path(path);
 553         ins->objectid = search_start;
 554         ins->offset = 0;
 555         start_found = 0;
 556         ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
 557         if (ret < 0)
 558                 goto error;
 559
 560         if (path->slots[0] > 0)
 561                 path->slots[0]--;
 562
 563         while (1) {
 564                 l = btrfs_buffer_leaf(path->nodes[0]);
 565                 slot = path->slots[0];
 566                 if (slot >= btrfs_header_nritems(&l->header)) {
 567                         if (fill_prealloc) {
 568                                 info->extent_tree_prealloc_nr = 0;
 569                                 total_found = 0;
 570                         }
 571                         ret = btrfs_next_leaf(root, path);
 572                         if (ret == 0)
 573                                 continue;
 574                         if (ret < 0)
 575                                 goto error;
 576                         if (!start_found) {
 577                                 ins->objectid = search_start;
 578                                 ins->offset = (u64)-1 - search_start;
 579                                 start_found = 1;
 580                                 goto check_pending;
 581                         }
 582                         ins->objectid = last_block > search_start ?
 583                                         last_block : search_start;
 584                         ins->offset = (u64)-1 - ins->objectid;
 585                         goto check_pending;
 586                 }
 587                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
 588                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
 589                         goto next;
 590                 if (key.objectid >= search_start) {
 591                         if (start_found) {
 592                                 if (last_block < search_start)
 593                                         last_block = search_start;
 594                                 hole_size = key.objectid - last_block;
 595                                 if (hole_size >= num_blocks) {
 596                                         ins->objectid = last_block;
 597                                         ins->offset = hole_size;
 598                                         goto check_pending;
 599                                 }
 600                         }
 601                 }
 602                 start_found = 1;
 603                 last_block = key.objectid + key.offset;
 604 next:
 605                 path->slots[0]++;
 606         }
 607         // FIXME -ENOSPC
 608 check_pending:
 609         /* we have to make sure we didn't find an extent that has already
 610          * been allocated by the map tree or the original allocation
 611          */
 612         btrfs_release_path(root, path);
 613         BUG_ON(ins->objectid < search_start);
 614         if (ins->objectid >= btrfs_super_total_blocks(info->disk_super)) {
 615                 if (search_start == 0)
 616                         return -ENOSPC;
 617                 search_start = 0;
 618                 goto check_failed;
 619         }
 620         for (test_block = ins->objectid;
 621              test_block < ins->objectid + num_blocks; test_block++) {
 622                 if (test_radix_bit(&info->pinned_radix, test_block)) {
 623                         search_start = test_block + 1;
 624                         goto check_failed;
 625                 }
 626         }
 627         if (!fill_prealloc && info->extent_tree_insert_nr) {
 628                 u64 last =
 629                   info->extent_tree_insert[info->extent_tree_insert_nr - 1];
 630                 if (ins->objectid + num_blocks >
 631                     info->extent_tree_insert[0] &&
 632                     ins->objectid <= last) {
 633                         search_start = last + 1;
 634                         WARN_ON(1);
 635                         goto check_failed;
 636                 }
 637         }
 638         if (!fill_prealloc && info->extent_tree_prealloc_nr) {
 639                 u64 first =
 640                   info->extent_tree_prealloc[info->extent_tree_prealloc_nr - 1];
 641                 if (ins->objectid + num_blocks > first &&
 642                     ins->objectid <= info->extent_tree_prealloc[0]) {
 643                         search_start = info->extent_tree_prealloc[0] + 1;
 644                         WARN_ON(1);
 645                         goto check_failed;
 646                 }
 647         }
 648         if (fill_prealloc) {
 649                 int nr;
 650                 test_block = ins->objectid;
 651                 while(test_block < ins->objectid + ins->offset &&
 652                       total_found < total_needed) {
 653                         nr = total_needed - total_found - 1;
 654                         BUG_ON(nr < 0);
 655                         info->extent_tree_prealloc[nr] = test_block;
 656                         total_found++;
 657                         test_block++;
 658                 }
 659                 if (total_found < total_needed) {
 660                         search_start = test_block;
 661                         goto check_failed;
 662                 }
 663                 info->extent_tree_prealloc_nr = total_found;
 664         }
 665         ret = radix_tree_gang_lookup(&info->block_group_radix,
 666                                      (void **)&info->block_group_cache,
 667                                      ins->objectid, 1);
 668         if (ret) {
 669                 info->block_group_cache->last_alloc = ins->objectid;
 670         }
 671         ins->offset = num_blocks;
 672         btrfs_free_path(path);
 673         return 0;
 674 error:
 675         btrfs_release_path(root, path);
 676         btrfs_free_path(path);
 677         return ret;
 678 }
 679 /*
 680  * finds a free extent and does all the dirty work required for allocation
 681  * returns the key for the extent through ins, and a tree buffer for
 682  * the first block of the extent through buf.
 683  *
 684  * returns 0 if everything worked, non-zero otherwise.
 685  */
 686 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
 687                        struct btrfs_root *root, u64 owner,
 688                        u64 num_blocks, u64 search_start,
 689                        u64 search_end, struct btrfs_key *ins)
 690 {
 691         int ret;
 692         int pending_ret;
 693         u64 super_blocks_used;
 694         struct btrfs_fs_info *info = root->fs_info;
 695         struct btrfs_root *extent_root = info->extent_root;
 696         struct btrfs_extent_item extent_item;
 697         struct btrfs_key prealloc_key;
 698
 699         btrfs_set_extent_refs(&extent_item, 1);
 700         btrfs_set_extent_owner(&extent_item, owner);
 701
 702         if (root == extent_root) {
 703                 int nr;
 704                 BUG_ON(info->extent_tree_prealloc_nr == 0);
 705                 BUG_ON(num_blocks != 1);
 706                 ins->offset = 1;
 707                 info->extent_tree_prealloc_nr--;
 708                 nr = info->extent_tree_prealloc_nr;
 709                 ins->objectid = info->extent_tree_prealloc[nr];
 710                 info->extent_tree_insert[info->extent_tree_insert_nr++] =
 711                         ins->objectid;
 712                 ret = update_block_group(trans, root,
 713                                          ins->objectid, ins->offset, 1);
 714                 BUG_ON(ret);
 715                 return 0;
 716         }
 717         /* do the real allocation */
 718         ret = find_free_extent(trans, root, num_blocks, search_start,
 719                                search_end, ins);
 720         if (ret)
 721                 return ret;
 722
 723         /* then do prealloc for the extent tree */
 724         ret = find_free_extent(trans, root, 0, ins->objectid + ins->offset,
 725                                search_end, &prealloc_key);
 726         if (ret)
 727                 return ret;
 728
 729         super_blocks_used = btrfs_super_blocks_used(info->disk_super);
 730         btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
 731                                     num_blocks);
 732         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
 733                                 sizeof(extent_item));
 734
 735         finish_current_insert(trans, extent_root);
 736         pending_ret = del_pending_extents(trans, extent_root);
 737         if (ret)
 738                 return ret;
 739         if (pending_ret)
 740                 return pending_ret;
 741         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1);
 742         return 0;
 743 }
 744
 745 /*
 746  * helper function to allocate a block for a given tree
 747  * returns the tree buffer or NULL.
 748  */
 749 struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
 750                                            struct btrfs_root *root)
 751 {
 752         struct btrfs_key ins;
 753         int ret;
 754         struct buffer_head *buf;
 755
 756         ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
 757                                  1, 0, (unsigned long)-1, &ins);
 758         if (ret) {
 759                 BUG();
 760                 return NULL;
 761         }
 762         BUG_ON(ret);
 763         buf = btrfs_find_create_tree_block(root, ins.objectid);
 764         set_buffer_uptodate(buf);
 765         set_radix_bit(&trans->transaction->dirty_pages, buf->b_page->index);
 766         return buf;
 767 }
 768
 769 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
 770                          struct btrfs_root *root, struct buffer_head *cur)
 771 {
 772         struct btrfs_disk_key *key;
 773         struct btrfs_leaf *leaf;
 774         struct btrfs_file_extent_item *fi;
 775         int i;
 776         int nritems;
 777         int ret;
 778
 779         BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
 780         leaf = btrfs_buffer_leaf(cur);
 781         nritems = btrfs_header_nritems(&leaf->header);
 782         for (i = 0; i < nritems; i++) {
 783                 key = &leaf->items[i].key;
 784                 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
 785                         continue;
 786                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
 787                 if (btrfs_file_extent_type(fi) == BTRFS_FILE_EXTENT_INLINE)
 788                         continue;
 789                 /*
 790                  * FIXME make sure to insert a trans record that
 791                  * repeats the snapshot del on crash
 792                  */
 793                 ret = btrfs_free_extent(trans, root,
 794                                         btrfs_file_extent_disk_blocknr(fi),
 795                                         btrfs_file_extent_disk_num_blocks(fi),
 796                                         0);
 797                 BUG_ON(ret);
 798         }
 799         return 0;
 800 }
 801
 802 /*
 803  * helper function for drop_snapshot, this walks down the tree dropping ref
 804  * counts as it goes.
 805  */
 806 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 807                           *root, struct btrfs_path *path, int *level)
 808 {
 809         struct buffer_head *next;
 810         struct buffer_head *cur;
 811         u64 blocknr;
 812         int ret;
 813         u32 refs;
 814
 815         WARN_ON(*level < 0);
 816         WARN_ON(*level >= BTRFS_MAX_LEVEL);
 817         ret = lookup_extent_ref(trans, root, bh_blocknr(path->nodes[*level]),
 818                                1, &refs);
 819         BUG_ON(ret);
 820         if (refs > 1)
 821                 goto out;
 822         /*
 823          * walk down to the last node level and free all the leaves
 824          */
 825         while(*level >= 0) {
 826                 WARN_ON(*level < 0);
 827                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
 828                 cur = path->nodes[*level];
 829                 if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
 830                         WARN_ON(1);
 831                 if (path->slots[*level] >=
 832                     btrfs_header_nritems(btrfs_buffer_header(cur)))
 833                         break;
 834                 if (*level == 0) {
 835                         ret = drop_leaf_ref(trans, root, cur);
 836                         BUG_ON(ret);
 837                         break;
 838                 }
 839                 blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
 840                                               path->slots[*level]);
 841                 ret = lookup_extent_ref(trans, root, blocknr, 1, &refs);
 842                 BUG_ON(ret);
 843                 if (refs != 1) {
 844                         path->slots[*level]++;
 845                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
 846                         BUG_ON(ret);
 847                         continue;
 848                 }
 849                 next = read_tree_block(root, blocknr);
 850                 WARN_ON(*level <= 0);
 851                 if (path->nodes[*level-1])
 852                         btrfs_block_release(root, path->nodes[*level-1]);
 853                 path->nodes[*level-1] = next;
 854                 *level = btrfs_header_level(btrfs_buffer_header(next));
 855                 path->slots[*level] = 0;
 856         }
 857 out:
 858         WARN_ON(*level < 0);
 859         WARN_ON(*level >= BTRFS_MAX_LEVEL);
 860         ret = btrfs_free_extent(trans, root,
 861                                 bh_blocknr(path->nodes[*level]), 1, 1);
 862         btrfs_block_release(root, path->nodes[*level]);
 863         path->nodes[*level] = NULL;
 864         *level += 1;
 865         BUG_ON(ret);
 866         return 0;
 867 }
 868
 869 /*
 870  * helper for dropping snapshots.  This walks back up the tree in the path
 871  * to find the first node higher up where we haven't yet gone through
 872  * all the slots
 873  */
 874 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 875                         *root, struct btrfs_path *path, int *level)
 876 {
 877         int i;
 878         int slot;
 879         int ret;
 880         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 881                 slot = path->slots[i];
 882                 if (slot < btrfs_header_nritems(
 883                     btrfs_buffer_header(path->nodes[i])) - 1) {
 884                         path->slots[i]++;
 885                         *level = i;
 886                         return 0;
 887                 } else {
 888                         ret = btrfs_free_extent(trans, root,
 889                                                 bh_blocknr(path->nodes[*level]),
 890                                                 1, 1);
 891                         BUG_ON(ret);
 892                         btrfs_block_release(root, path->nodes[*level]);
 893                         path->nodes[*level] = NULL;
 894                         *level = i + 1;
 895                 }
 896         }
 897         return 1;
 898 }
 899
 900 /*
 901  * drop the reference count on the tree rooted at 'snap'.  This traverses
 902  * the tree freeing any blocks that have a ref count of zero after being
 903  * decremented.
 904  */
 905 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
 906                         *root, struct buffer_head *snap)
 907 {
 908         int ret = 0;
 909         int wret;
 910         int level;
 911         struct btrfs_path *path;
 912         int i;
 913         int orig_level;
 914
 915         path = btrfs_alloc_path();
 916         BUG_ON(!path);
 917         btrfs_init_path(path);
 918
 919         level = btrfs_header_level(btrfs_buffer_header(snap));
 920         orig_level = level;
 921         path->nodes[level] = snap;
 922         path->slots[level] = 0;
 923         while(1) {
 924                 wret = walk_down_tree(trans, root, path, &level);
 925                 if (wret > 0)
 926                         break;
 927                 if (wret < 0)
 928                         ret = wret;
 929
 930                 wret = walk_up_tree(trans, root, path, &level);
 931                 if (wret > 0)
 932                         break;
 933                 if (wret < 0)
 934                         ret = wret;
 935         }
 936         for (i = 0; i <= orig_level; i++) {
 937                 if (path->nodes[i]) {
 938                         btrfs_block_release(root, path->nodes[i]);
 939                 }
 940         }
 941         btrfs_free_path(path);
 942         return ret;
 943 }
 944
 945 int btrfs_free_block_groups(struct btrfs_fs_info *info)
 946 {
 947         int ret;
 948         struct btrfs_block_group_cache *cache[8];
 949         int i;
 950
 951         while(1) {
 952                 ret = radix_tree_gang_lookup(&info->block_group_radix,
 953                                              (void **)cache, 0,
 954                                              ARRAY_SIZE(cache));
 955                 if (!ret)
 956                         break;
 957                 for (i = 0; i < ret; i++) {
 958                         radix_tree_delete(&info->block_group_radix,
 959                                           cache[i]->key.objectid +
 960                                           cache[i]->key.offset - 1);
 961                         kfree(cache[i]);
 962                 }
 963         }
 964         return 0;
 965 }
 966
 967 int btrfs_read_block_groups(struct btrfs_root *root)
 968 {
 969         struct btrfs_path *path;
 970         int ret;
 971         int err = 0;
 972         struct btrfs_block_group_item *bi;
 973         struct btrfs_block_group_cache *cache;
 974         struct btrfs_key key;
 975         struct btrfs_key found_key;
 976         struct btrfs_leaf *leaf;
 977         u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;
 978
 979         root = root->fs_info->extent_root;
 980         key.objectid = 0;
 981         key.offset = group_size_blocks;
 982         key.flags = 0;
 983         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
 984
 985         path = btrfs_alloc_path();
 986         if (!path)
 987                 return -ENOMEM;
 988
 989         while(1) {
 990                 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
 991                                         &key, path, 0, 0);
 992                 if (ret != 0) {
 993                         err = ret;
 994                         break;
 995                 }
 996                 leaf = btrfs_buffer_leaf(path->nodes[0]);
 997                 btrfs_disk_key_to_cpu(&found_key,
 998                                       &leaf->items[path->slots[0]].key);
 999                 cache = kmalloc(sizeof(*cache), GFP_NOFS);
1000                 if (!cache) {
1001                         err = -1;
1002                         break;
1003                 }
1004                 bi = btrfs_item_ptr(leaf, path->slots[0],
1005                                     struct btrfs_block_group_item);
1006                 memcpy(&cache->item, bi, sizeof(*bi));
1007                 memcpy(&cache->key, &found_key, sizeof(found_key));
1008                 cache->last_alloc = 0;
1009                 cache->first_free = 0;
1010                 key.objectid = found_key.objectid + found_key.offset;
1011                 btrfs_release_path(root, path);
1012                 ret = radix_tree_insert(&root->fs_info->block_group_radix,
1013                                         found_key.objectid +
1014                                         found_key.offset - 1,
1015                                         (void *)cache);
1016                 BUG_ON(ret);
1017                 if (key.objectid >=
1018                     btrfs_super_total_blocks(root->fs_info->disk_super))
1019                         break;
1020         }
1021
1022         btrfs_free_path(path);
1023         return 0;
1024 }