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