fs/btrfs/extent-tree.c

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