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