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