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