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