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