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