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 #include <linux/sched.h>
  19 #include <linux/pagemap.h>
  20 #include "hash.h"
  21 #include "crc32c.h"
  22 #include "ctree.h"
  23 #include "disk-io.h"
  24 #include "print-tree.h"
  25 #include "transaction.h"
  26 #include "volumes.h"
  27
  28 #define BLOCK_GROUP_DATA     EXTENT_WRITEBACK
  29 #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
  30 #define BLOCK_GROUP_SYSTEM   EXTENT_NEW
  31
  32 #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
  33
  34 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  35                                  btrfs_root *extent_root);
  36 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  37                                btrfs_root *extent_root);
  38
  39
  40 static int cache_block_group(struct btrfs_root *root,
  41                              struct btrfs_block_group_cache *block_group)
  42 {
  43         struct btrfs_path *path;
  44         int ret;
  45         struct btrfs_key key;
  46         struct extent_buffer *leaf;
  47         struct extent_io_tree *free_space_cache;
  48         int slot;
  49         u64 last = 0;
  50         u64 hole_size;
  51         u64 first_free;
  52         int found = 0;
  53
  54         if (!block_group)
  55                 return 0;
  56
  57         root = root->fs_info->extent_root;
  58         free_space_cache = &root->fs_info->free_space_cache;
  59
  60         if (block_group->cached)
  61                 return 0;
  62
  63         path = btrfs_alloc_path();
  64         if (!path)
  65                 return -ENOMEM;
  66
  67         path->reada = 2;
  68         first_free = block_group->key.objectid;
  69         key.objectid = block_group->key.objectid;
  70         key.offset = 0;
  71         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  72         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  73         if (ret < 0)
  74                 return ret;
  75         ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
  76         if (ret < 0)
  77                 return ret;
  78         if (ret == 0) {
  79                 leaf = path->nodes[0];
  80                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  81                 if (key.objectid + key.offset > first_free)
  82                         first_free = key.objectid + key.offset;
  83         }
  84         while(1) {
  85                 leaf = path->nodes[0];
  86                 slot = path->slots[0];
  87                 if (slot >= btrfs_header_nritems(leaf)) {
  88                         ret = btrfs_next_leaf(root, path);
  89                         if (ret < 0)
  90                                 goto err;
  91                         if (ret == 0) {
  92                                 continue;
  93                         } else {
  94                                 break;
  95                         }
  96                 }
  97                 btrfs_item_key_to_cpu(leaf, &key, slot);
  98                 if (key.objectid < block_group->key.objectid) {
  99                         goto next;
 100                 }
 101                 if (key.objectid >= block_group->key.objectid +
 102                     block_group->key.offset) {
 103                         break;
 104                 }
 105
 106                 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
 107                         if (!found) {
 108                                 last = first_free;
 109                                 found = 1;
 110                         }
 111                         if (key.objectid > last) {
 112                                 hole_size = key.objectid - last;
 113                                 set_extent_dirty(free_space_cache, last,
 114                                                  last + hole_size - 1,
 115                                                  GFP_NOFS);
 116                         }
 117                         last = key.objectid + key.offset;
 118                 }
 119 next:
 120                 path->slots[0]++;
 121         }
 122
 123         if (!found)
 124                 last = first_free;
 125         if (block_group->key.objectid +
 126             block_group->key.offset > last) {
 127                 hole_size = block_group->key.objectid +
 128                         block_group->key.offset - last;
 129                 set_extent_dirty(free_space_cache, last,
 130                                  last + hole_size - 1, GFP_NOFS);
 131         }
 132         block_group->cached = 1;
 133 err:
 134         btrfs_free_path(path);
 135         return 0;
 136 }
 137
 138 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 139                                                          btrfs_fs_info *info,
 140                                                          u64 bytenr)
 141 {
 142         struct extent_io_tree *block_group_cache;
 143         struct btrfs_block_group_cache *block_group = NULL;
 144         u64 ptr;
 145         u64 start;
 146         u64 end;
 147         int ret;
 148
 149         block_group_cache = &info->block_group_cache;
 150         ret = find_first_extent_bit(block_group_cache,
 151                                     bytenr, &start, &end,
 152                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
 153                                     BLOCK_GROUP_SYSTEM);
 154         if (ret) {
 155                 return NULL;
 156         }
 157         ret = get_state_private(block_group_cache, start, &ptr);
 158         if (ret)
 159                 return NULL;
 160
 161         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 162         if (block_group->key.objectid <= bytenr && bytenr <
 163             block_group->key.objectid + block_group->key.offset)
 164                 return block_group;
 165         return NULL;
 166 }
 167
 168 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
 169 {
 170         return (cache->flags & bits) == bits;
 171 }
 172
 173 static int noinline find_search_start(struct btrfs_root *root,
 174                               struct btrfs_block_group_cache **cache_ret,
 175                               u64 *start_ret, int num, int data)
 176 {
 177         int ret;
 178         struct btrfs_block_group_cache *cache = *cache_ret;
 179         struct extent_io_tree *free_space_cache;
 180         struct extent_state *state;
 181         u64 last;
 182         u64 start = 0;
 183         u64 cache_miss = 0;
 184         u64 total_fs_bytes;
 185         u64 search_start = *start_ret;
 186         int wrapped = 0;
 187
 188         if (!cache)
 189                 goto out;
 190
 191         total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
 192         free_space_cache = &root->fs_info->free_space_cache;
 193
 194 again:
 195         ret = cache_block_group(root, cache);
 196         if (ret)
 197                 goto out;
 198
 199         last = max(search_start, cache->key.objectid);
 200         if (!block_group_bits(cache, data) || cache->ro) {
 201                 goto new_group;
 202         }
 203
 204         spin_lock_irq(&free_space_cache->lock);
 205         state = find_first_extent_bit_state(free_space_cache, last, EXTENT_DIRTY);
 206         while(1) {
 207                 if (!state) {
 208                         if (!cache_miss)
 209                                 cache_miss = last;
 210                         spin_unlock_irq(&free_space_cache->lock);
 211                         goto new_group;
 212                 }
 213
 214                 start = max(last, state->start);
 215                 last = state->end + 1;
 216                 if (last - start < num) {
 217                         if (last == cache->key.objectid + cache->key.offset)
 218                                 cache_miss = start;
 219                         do {
 220                                 state = extent_state_next(state);
 221                         } while(state && !(state->state & EXTENT_DIRTY));
 222                         continue;
 223                 }
 224                 spin_unlock_irq(&free_space_cache->lock);
 225                 if (cache->ro)
 226                         goto new_group;
 227                 if (start + num > cache->key.objectid + cache->key.offset)
 228                         goto new_group;
 229                 if (start + num  > total_fs_bytes)
 230                         goto new_group;
 231                 if (!block_group_bits(cache, data)) {
 232                         printk("block group bits don't match %Lu %d\n", cache->flags, data);
 233                 }
 234                 *start_ret = start;
 235                 return 0;
 236         }
 237 out:
 238         cache = btrfs_lookup_block_group(root->fs_info, search_start);
 239         if (!cache) {
 240                 printk("Unable to find block group for %Lu\n", search_start);
 241                 WARN_ON(1);
 242         }
 243         return -ENOSPC;
 244
 245 new_group:
 246         last = cache->key.objectid + cache->key.offset;
 247 wrapped:
 248         cache = btrfs_lookup_block_group(root->fs_info, last);
 249         if (!cache || cache->key.objectid >= total_fs_bytes) {
 250 no_cache:
 251                 if (!wrapped) {
 252                         wrapped = 1;
 253                         last = search_start;
 254                         goto wrapped;
 255                 }
 256                 goto out;
 257         }
 258         if (cache_miss && !cache->cached) {
 259                 cache_block_group(root, cache);
 260                 last = cache_miss;
 261                 cache = btrfs_lookup_block_group(root->fs_info, last);
 262         }
 263         cache = btrfs_find_block_group(root, cache, last, data, 0);
 264         if (!cache)
 265                 goto no_cache;
 266         *cache_ret = cache;
 267         cache_miss = 0;
 268         goto again;
 269 }
 270
 271 static u64 div_factor(u64 num, int factor)
 272 {
 273         if (factor == 10)
 274                 return num;
 275         num *= factor;
 276         do_div(num, 10);
 277         return num;
 278 }
 279
 280 static int block_group_state_bits(u64 flags)
 281 {
 282         int bits = 0;
 283         if (flags & BTRFS_BLOCK_GROUP_DATA)
 284                 bits |= BLOCK_GROUP_DATA;
 285         if (flags & BTRFS_BLOCK_GROUP_METADATA)
 286                 bits |= BLOCK_GROUP_METADATA;
 287         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
 288                 bits |= BLOCK_GROUP_SYSTEM;
 289         return bits;
 290 }
 291
 292 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 293                                                  struct btrfs_block_group_cache
 294                                                  *hint, u64 search_start,
 295                                                  int data, int owner)
 296 {
 297         struct btrfs_block_group_cache *cache;
 298         struct extent_io_tree *block_group_cache;
 299         struct btrfs_block_group_cache *found_group = NULL;
 300         struct btrfs_fs_info *info = root->fs_info;
 301         u64 used;
 302         u64 last = 0;
 303         u64 hint_last;
 304         u64 start;
 305         u64 end;
 306         u64 free_check;
 307         u64 ptr;
 308         u64 total_fs_bytes;
 309         int bit;
 310         int ret;
 311         int full_search = 0;
 312         int factor = 10;
 313
 314         block_group_cache = &info->block_group_cache;
 315         total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
 316
 317         if (!owner)
 318                 factor = 10;
 319
 320         bit = block_group_state_bits(data);
 321
 322         if (search_start && search_start < total_fs_bytes) {
 323                 struct btrfs_block_group_cache *shint;
 324                 shint = btrfs_lookup_block_group(info, search_start);
 325                 if (shint && block_group_bits(shint, data) && !shint->ro) {
 326                         used = btrfs_block_group_used(&shint->item);
 327                         if (used + shint->pinned <
 328                             div_factor(shint->key.offset, factor)) {
 329                                 return shint;
 330                         }
 331                 }
 332         }
 333         if (hint && !hint->ro && block_group_bits(hint, data) &&
 334             hint->key.objectid < total_fs_bytes) {
 335                 used = btrfs_block_group_used(&hint->item);
 336                 if (used + hint->pinned <
 337                     div_factor(hint->key.offset, factor)) {
 338                         return hint;
 339                 }
 340                 last = hint->key.objectid + hint->key.offset;
 341                 hint_last = last;
 342         } else {
 343                 if (hint)
 344                         hint_last = max(hint->key.objectid, search_start);
 345                 else
 346                         hint_last = search_start;
 347
 348                 if (hint_last >= total_fs_bytes)
 349                         hint_last = search_start;
 350                 last = hint_last;
 351         }
 352 again:
 353         while(1) {
 354                 ret = find_first_extent_bit(block_group_cache, last,
 355                                             &start, &end, bit);
 356                 if (ret)
 357                         break;
 358
 359                 ret = get_state_private(block_group_cache, start, &ptr);
 360                 if (ret)
 361                         break;
 362
 363                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 364                 last = cache->key.objectid + cache->key.offset;
 365                 used = btrfs_block_group_used(&cache->item);
 366
 367                 if (cache->key.objectid > total_fs_bytes)
 368                         break;
 369
 370                 if (!cache->ro && block_group_bits(cache, data)) {
 371                         if (full_search)
 372                                 free_check = cache->key.offset;
 373                         else
 374                                 free_check = div_factor(cache->key.offset,
 375                                                         factor);
 376
 377                         if (used + cache->pinned < free_check) {
 378                                 found_group = cache;
 379                                 goto found;
 380                         }
 381                 }
 382                 cond_resched();
 383         }
 384         if (!full_search) {
 385                 last = search_start;
 386                 full_search = 1;
 387                 goto again;
 388         }
 389 found:
 390         return found_group;
 391 }
 392
 393 static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
 394                            u64 owner, u64 owner_offset)
 395 {
 396         u32 high_crc = ~(u32)0;
 397         u32 low_crc = ~(u32)0;
 398         __le64 lenum;
 399         lenum = cpu_to_le64(root_objectid);
 400         high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
 401         lenum = cpu_to_le64(ref_generation);
 402         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 403         if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
 404                 lenum = cpu_to_le64(owner);
 405                 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 406                 lenum = cpu_to_le64(owner_offset);
 407                 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 408         }
 409         return ((u64)high_crc << 32) | (u64)low_crc;
 410 }
 411
 412 static int match_extent_ref(struct extent_buffer *leaf,
 413                             struct btrfs_extent_ref *disk_ref,
 414                             struct btrfs_extent_ref *cpu_ref)
 415 {
 416         int ret;
 417         int len;
 418
 419         if (cpu_ref->objectid)
 420                 len = sizeof(*cpu_ref);
 421         else
 422                 len = 2 * sizeof(u64);
 423         ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
 424                                    len);
 425         return ret == 0;
 426 }
 427
 428 static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
 429                                           struct btrfs_root *root,
 430                                           struct btrfs_path *path, u64 bytenr,
 431                                           u64 root_objectid,
 432                                           u64 ref_generation, u64 owner,
 433                                           u64 owner_offset, int del)
 434 {
 435         u64 hash;
 436         struct btrfs_key key;
 437         struct btrfs_key found_key;
 438         struct btrfs_extent_ref ref;
 439         struct extent_buffer *leaf;
 440         struct btrfs_extent_ref *disk_ref;
 441         int ret;
 442         int ret2;
 443
 444         btrfs_set_stack_ref_root(&ref, root_objectid);
 445         btrfs_set_stack_ref_generation(&ref, ref_generation);
 446         btrfs_set_stack_ref_objectid(&ref, owner);
 447         btrfs_set_stack_ref_offset(&ref, owner_offset);
 448
 449         hash = hash_extent_ref(root_objectid, ref_generation, owner,
 450                                owner_offset);
 451         key.offset = hash;
 452         key.objectid = bytenr;
 453         key.type = BTRFS_EXTENT_REF_KEY;
 454
 455         while (1) {
 456                 ret = btrfs_search_slot(trans, root, &key, path,
 457                                         del ? -1 : 0, del);
 458                 if (ret < 0)
 459                         goto out;
 460                 leaf = path->nodes[0];
 461                 if (ret != 0) {
 462                         u32 nritems = btrfs_header_nritems(leaf);
 463                         if (path->slots[0] >= nritems) {
 464                                 ret2 = btrfs_next_leaf(root, path);
 465                                 if (ret2)
 466                                         goto out;
 467                                 leaf = path->nodes[0];
 468                         }
 469                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 470                         if (found_key.objectid != bytenr ||
 471                             found_key.type != BTRFS_EXTENT_REF_KEY)
 472                                 goto out;
 473                         key.offset = found_key.offset;
 474                         if (del) {
 475                                 btrfs_release_path(root, path);
 476                                 continue;
 477                         }
 478                 }
 479                 disk_ref = btrfs_item_ptr(path->nodes[0],
 480                                           path->slots[0],
 481                                           struct btrfs_extent_ref);
 482                 if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
 483                         ret = 0;
 484                         goto out;
 485                 }
 486                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 487                 key.offset = found_key.offset + 1;
 488                 btrfs_release_path(root, path);
 489         }
 490 out:
 491         return ret;
 492 }
 493
 494 /*
 495  * Back reference rules.  Back refs have three main goals:
 496  *
 497  * 1) differentiate between all holders of references to an extent so that
 498  *    when a reference is dropped we can make sure it was a valid reference
 499  *    before freeing the extent.
 500  *
 501  * 2) Provide enough information to quickly find the holders of an extent
 502  *    if we notice a given block is corrupted or bad.
 503  *
 504  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 505  *    maintenance.  This is actually the same as #2, but with a slightly
 506  *    different use case.
 507  *
 508  * File extents can be referenced by:
 509  *
 510  * - multiple snapshots, subvolumes, or different generations in one subvol
 511  * - different files inside a single subvolume (in theory, not implemented yet)
 512  * - different offsets inside a file (bookend extents in file.c)
 513  *
 514  * The extent ref structure has fields for:
 515  *
 516  * - Objectid of the subvolume root
 517  * - Generation number of the tree holding the reference
 518  * - objectid of the file holding the reference
 519  * - offset in the file corresponding to the key holding the reference
 520  *
 521  * When a file extent is allocated the fields are filled in:
 522  *     (root_key.objectid, trans->transid, inode objectid, offset in file)
 523  *
 524  * When a leaf is cow'd new references are added for every file extent found
 525  * in the leaf.  It looks the same as the create case, but trans->transid
 526  * will be different when the block is cow'd.
 527  *
 528  *     (root_key.objectid, trans->transid, inode objectid, offset in file)
 529  *
 530  * When a file extent is removed either during snapshot deletion or file
 531  * truncation, the corresponding back reference is found
 532  * by searching for:
 533  *
 534  *     (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
 535  *      inode objectid, offset in file)
 536  *
 537  * Btree extents can be referenced by:
 538  *
 539  * - Different subvolumes
 540  * - Different generations of the same subvolume
 541  *
 542  * Storing sufficient information for a full reverse mapping of a btree
 543  * block would require storing the lowest key of the block in the backref,
 544  * and it would require updating that lowest key either before write out or
 545  * every time it changed.  Instead, the objectid of the lowest key is stored
 546  * along with the level of the tree block.  This provides a hint
 547  * about where in the btree the block can be found.  Searches through the
 548  * btree only need to look for a pointer to that block, so they stop one
 549  * level higher than the level recorded in the backref.
 550  *
 551  * Some btrees do not do reference counting on their extents.  These
 552  * include the extent tree and the tree of tree roots.  Backrefs for these
 553  * trees always have a generation of zero.
 554  *
 555  * When a tree block is created, back references are inserted:
 556  *
 557  * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
 558  *
 559  * When a tree block is cow'd in a reference counted root,
 560  * new back references are added for all the blocks it points to.
 561  * These are of the form (trans->transid will have increased since creation):
 562  *
 563  * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
 564  *
 565  * Because the lowest_key_objectid and the level are just hints
 566  * they are not used when backrefs are deleted.  When a backref is deleted:
 567  *
 568  * if backref was for a tree root:
 569  *     root_objectid = root->root_key.objectid
 570  * else
 571  *     root_objectid = btrfs_header_owner(parent)
 572  *
 573  * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
 574  *
 575  * Back Reference Key hashing:
 576  *
 577  * Back references have four fields, each 64 bits long.  Unfortunately,
 578  * This is hashed into a single 64 bit number and placed into the key offset.
 579  * The key objectid corresponds to the first byte in the extent, and the
 580  * key type is set to BTRFS_EXTENT_REF_KEY
 581  */
 582 int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
 583                                  struct btrfs_root *root,
 584                                  struct btrfs_path *path, u64 bytenr,
 585                                  u64 root_objectid, u64 ref_generation,
 586                                  u64 owner, u64 owner_offset)
 587 {
 588         u64 hash;
 589         struct btrfs_key key;
 590         struct btrfs_extent_ref ref;
 591         struct btrfs_extent_ref *disk_ref;
 592         int ret;
 593
 594         btrfs_set_stack_ref_root(&ref, root_objectid);
 595         btrfs_set_stack_ref_generation(&ref, ref_generation);
 596         btrfs_set_stack_ref_objectid(&ref, owner);
 597         btrfs_set_stack_ref_offset(&ref, owner_offset);
 598
 599         hash = hash_extent_ref(root_objectid, ref_generation, owner,
 600                                owner_offset);
 601         key.offset = hash;
 602         key.objectid = bytenr;
 603         key.type = BTRFS_EXTENT_REF_KEY;
 604
 605         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
 606         while (ret == -EEXIST) {
 607                 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 608                                           struct btrfs_extent_ref);
 609                 if (match_extent_ref(path->nodes[0], disk_ref, &ref))
 610                         goto out;
 611                 key.offset++;
 612                 btrfs_release_path(root, path);
 613                 ret = btrfs_insert_empty_item(trans, root, path, &key,
 614                                               sizeof(ref));
 615         }
 616         if (ret)
 617                 goto out;
 618         disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 619                                   struct btrfs_extent_ref);
 620         write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
 621                             sizeof(ref));
 622         btrfs_mark_buffer_dirty(path->nodes[0]);
 623 out:
 624         btrfs_release_path(root, path);
 625         return ret;
 626 }
 627
 628 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 629                                 struct btrfs_root *root,
 630                                 u64 bytenr, u64 num_bytes,
 631                                 u64 root_objectid, u64 ref_generation,
 632                                 u64 owner, u64 owner_offset)
 633 {
 634         struct btrfs_path *path;
 635         int ret;
 636         struct btrfs_key key;
 637         struct extent_buffer *l;
 638         struct btrfs_extent_item *item;
 639         u32 refs;
 640
 641         WARN_ON(num_bytes < root->sectorsize);
 642         path = btrfs_alloc_path();
 643         if (!path)
 644                 return -ENOMEM;
 645
 646         path->reada = 1;
 647         key.objectid = bytenr;
 648         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 649         key.offset = num_bytes;
 650         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 651                                 0, 1);
 652         if (ret < 0)
 653                 return ret;
 654         if (ret != 0) {
 655                 BUG();
 656         }
 657         BUG_ON(ret != 0);
 658         l = path->nodes[0];
 659         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 660         refs = btrfs_extent_refs(l, item);
 661         btrfs_set_extent_refs(l, item, refs + 1);
 662         btrfs_mark_buffer_dirty(path->nodes[0]);
 663
 664         btrfs_release_path(root->fs_info->extent_root, path);
 665
 666         path->reada = 1;
 667         ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
 668                                           path, bytenr, root_objectid,
 669                                           ref_generation, owner, owner_offset);
 670         BUG_ON(ret);
 671         finish_current_insert(trans, root->fs_info->extent_root);
 672         del_pending_extents(trans, root->fs_info->extent_root);
 673
 674         btrfs_free_path(path);
 675         return 0;
 676 }
 677
 678 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
 679                          struct btrfs_root *root)
 680 {
 681         finish_current_insert(trans, root->fs_info->extent_root);
 682         del_pending_extents(trans, root->fs_info->extent_root);
 683         return 0;
 684 }
 685
 686 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
 687                              struct btrfs_root *root, u64 bytenr,
 688                              u64 num_bytes, u32 *refs)
 689 {
 690         struct btrfs_path *path;
 691         int ret;
 692         struct btrfs_key key;
 693         struct extent_buffer *l;
 694         struct btrfs_extent_item *item;
 695
 696         WARN_ON(num_bytes < root->sectorsize);
 697         path = btrfs_alloc_path();
 698         path->reada = 1;
 699         key.objectid = bytenr;
 700         key.offset = num_bytes;
 701         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 702         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 703                                 0, 0);
 704         if (ret < 0)
 705                 goto out;
 706         if (ret != 0) {
 707                 btrfs_print_leaf(root, path->nodes[0]);
 708                 printk("failed to find block number %Lu\n", bytenr);
 709                 BUG();
 710         }
 711         l = path->nodes[0];
 712         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 713         *refs = btrfs_extent_refs(l, item);
 714 out:
 715         btrfs_free_path(path);
 716         return 0;
 717 }
 718
 719 u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
 720                                   struct btrfs_path *count_path,
 721                                   u64 first_extent)
 722 {
 723         struct btrfs_root *extent_root = root->fs_info->extent_root;
 724         struct btrfs_path *path;
 725         u64 bytenr;
 726         u64 found_objectid;
 727         u64 root_objectid = root->root_key.objectid;
 728         u32 total_count = 0;
 729         u32 cur_count;
 730         u32 nritems;
 731         int ret;
 732         struct btrfs_key key;
 733         struct btrfs_key found_key;
 734         struct extent_buffer *l;
 735         struct btrfs_extent_item *item;
 736         struct btrfs_extent_ref *ref_item;
 737         int level = -1;
 738
 739         path = btrfs_alloc_path();
 740 again:
 741         if (level == -1)
 742                 bytenr = first_extent;
 743         else
 744                 bytenr = count_path->nodes[level]->start;
 745
 746         cur_count = 0;
 747         key.objectid = bytenr;
 748         key.offset = 0;
 749
 750         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 751         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 752         if (ret < 0)
 753                 goto out;
 754         BUG_ON(ret == 0);
 755
 756         l = path->nodes[0];
 757         btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
 758
 759         if (found_key.objectid != bytenr ||
 760             found_key.type != BTRFS_EXTENT_ITEM_KEY) {
 761                 goto out;
 762         }
 763
 764         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 765         while (1) {
 766                 l = path->nodes[0];
 767                 nritems = btrfs_header_nritems(l);
 768                 if (path->slots[0] >= nritems) {
 769                         ret = btrfs_next_leaf(extent_root, path);
 770                         if (ret == 0)
 771                                 continue;
 772                         break;
 773                 }
 774                 btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
 775                 if (found_key.objectid != bytenr)
 776                         break;
 777
 778                 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
 779                         path->slots[0]++;
 780                         continue;
 781                 }
 782
 783                 cur_count++;
 784                 ref_item = btrfs_item_ptr(l, path->slots[0],
 785                                           struct btrfs_extent_ref);
 786                 found_objectid = btrfs_ref_root(l, ref_item);
 787
 788                 if (found_objectid != root_objectid) {
 789                         total_count = 2;
 790                         goto out;
 791                 }
 792                 total_count = 1;
 793                 path->slots[0]++;
 794         }
 795         if (cur_count == 0) {
 796                 total_count = 0;
 797                 goto out;
 798         }
 799         if (level >= 0 && root->node == count_path->nodes[level])
 800                 goto out;
 801         level++;
 802         btrfs_release_path(root, path);
 803         goto again;
 804
 805 out:
 806         btrfs_free_path(path);
 807         return total_count;
 808 }
 809 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
 810                        struct btrfs_root *root, u64 owner_objectid)
 811 {
 812         u64 generation;
 813         u64 key_objectid;
 814         u64 level;
 815         u32 nritems;
 816         struct btrfs_disk_key disk_key;
 817
 818         level = btrfs_header_level(root->node);
 819         generation = trans->transid;
 820         nritems = btrfs_header_nritems(root->node);
 821         if (nritems > 0) {
 822                 if (level == 0)
 823                         btrfs_item_key(root->node, &disk_key, 0);
 824                 else
 825                         btrfs_node_key(root->node, &disk_key, 0);
 826                 key_objectid = btrfs_disk_key_objectid(&disk_key);
 827         } else {
 828                 key_objectid = 0;
 829         }
 830         return btrfs_inc_extent_ref(trans, root, root->node->start,
 831                                     root->node->len, owner_objectid,
 832                                     generation, level, key_objectid);
 833 }
 834
 835 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 836                   struct extent_buffer *buf)
 837 {
 838         u64 bytenr;
 839         u32 nritems;
 840         struct btrfs_key key;
 841         struct btrfs_file_extent_item *fi;
 842         int i;
 843         int level;
 844         int ret;
 845         int faili;
 846
 847         if (!root->ref_cows)
 848                 return 0;
 849
 850         level = btrfs_header_level(buf);
 851         nritems = btrfs_header_nritems(buf);
 852         for (i = 0; i < nritems; i++) {
 853                 if (level == 0) {
 854                         u64 disk_bytenr;
 855                         btrfs_item_key_to_cpu(buf, &key, i);
 856                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
 857                                 continue;
 858                         fi = btrfs_item_ptr(buf, i,
 859                                             struct btrfs_file_extent_item);
 860                         if (btrfs_file_extent_type(buf, fi) ==
 861                             BTRFS_FILE_EXTENT_INLINE)
 862                                 continue;
 863                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
 864                         if (disk_bytenr == 0)
 865                                 continue;
 866                         ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
 867                                     btrfs_file_extent_disk_num_bytes(buf, fi),
 868                                     root->root_key.objectid, trans->transid,
 869                                     key.objectid, key.offset);
 870                         if (ret) {
 871                                 faili = i;
 872                                 goto fail;
 873                         }
 874                 } else {
 875                         bytenr = btrfs_node_blockptr(buf, i);
 876                         btrfs_node_key_to_cpu(buf, &key, i);
 877                         ret = btrfs_inc_extent_ref(trans, root, bytenr,
 878                                            btrfs_level_size(root, level - 1),
 879                                            root->root_key.objectid,
 880                                            trans->transid,
 881                                            level - 1, key.objectid);
 882                         if (ret) {
 883                                 faili = i;
 884                                 goto fail;
 885                         }
 886                 }
 887         }
 888         return 0;
 889 fail:
 890         WARN_ON(1);
 891 #if 0
 892         for (i =0; i < faili; i++) {
 893                 if (level == 0) {
 894                         u64 disk_bytenr;
 895                         btrfs_item_key_to_cpu(buf, &key, i);
 896                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
 897                                 continue;
 898                         fi = btrfs_item_ptr(buf, i,
 899                                             struct btrfs_file_extent_item);
 900                         if (btrfs_file_extent_type(buf, fi) ==
 901                             BTRFS_FILE_EXTENT_INLINE)
 902                                 continue;
 903                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
 904                         if (disk_bytenr == 0)
 905                                 continue;
 906                         err = btrfs_free_extent(trans, root, disk_bytenr,
 907                                     btrfs_file_extent_disk_num_bytes(buf,
 908                                                                       fi), 0);
 909                         BUG_ON(err);
 910                 } else {
 911                         bytenr = btrfs_node_blockptr(buf, i);
 912                         err = btrfs_free_extent(trans, root, bytenr,
 913                                         btrfs_level_size(root, level - 1), 0);
 914                         BUG_ON(err);
 915                 }
 916         }
 917 #endif
 918         return ret;
 919 }
 920
 921 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 922                                  struct btrfs_root *root,
 923                                  struct btrfs_path *path,
 924                                  struct btrfs_block_group_cache *cache)
 925 {
 926         int ret;
 927         int pending_ret;
 928         struct btrfs_root *extent_root = root->fs_info->extent_root;
 929         unsigned long bi;
 930         struct extent_buffer *leaf;
 931
 932         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 933         if (ret < 0)
 934                 goto fail;
 935         BUG_ON(ret);
 936
 937         leaf = path->nodes[0];
 938         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
 939         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
 940         btrfs_mark_buffer_dirty(leaf);
 941         btrfs_release_path(extent_root, path);
 942 fail:
 943         finish_current_insert(trans, extent_root);
 944         pending_ret = del_pending_extents(trans, extent_root);
 945         if (ret)
 946                 return ret;
 947         if (pending_ret)
 948                 return pending_ret;
 949         return 0;
 950
 951 }
 952
 953 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 954                                    struct btrfs_root *root)
 955 {
 956         struct extent_io_tree *block_group_cache;
 957         struct btrfs_block_group_cache *cache;
 958         int ret;
 959         int err = 0;
 960         int werr = 0;
 961         struct btrfs_path *path;
 962         u64 last = 0;
 963         u64 start;
 964         u64 end;
 965         u64 ptr;
 966
 967         block_group_cache = &root->fs_info->block_group_cache;
 968         path = btrfs_alloc_path();
 969         if (!path)
 970                 return -ENOMEM;
 971
 972         while(1) {
 973                 ret = find_first_extent_bit(block_group_cache, last,
 974                                             &start, &end, BLOCK_GROUP_DIRTY);
 975                 if (ret)
 976                         break;
 977
 978                 last = end + 1;
 979                 ret = get_state_private(block_group_cache, start, &ptr);
 980                 if (ret)
 981                         break;
 982                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 983                 err = write_one_cache_group(trans, root,
 984                                             path, cache);
 985                 /*
 986                  * if we fail to write the cache group, we want
 987                  * to keep it marked dirty in hopes that a later
 988                  * write will work
 989                  */
 990                 if (err) {
 991                         werr = err;
 992                         continue;
 993                 }
 994                 clear_extent_bits(block_group_cache, start, end,
 995                                   BLOCK_GROUP_DIRTY, GFP_NOFS);
 996         }
 997         btrfs_free_path(path);
 998         return werr;
 999 }
1000
1001 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
1002                                                   u64 flags)
1003 {
1004         struct list_head *head = &info->space_info;
1005         struct list_head *cur;
1006         struct btrfs_space_info *found;
1007         list_for_each(cur, head) {
1008                 found = list_entry(cur, struct btrfs_space_info, list);
1009                 if (found->flags == flags)
1010                         return found;
1011         }
1012         return NULL;
1013
1014 }
1015
1016 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1017                              u64 total_bytes, u64 bytes_used,
1018                              struct btrfs_space_info **space_info)
1019 {
1020         struct btrfs_space_info *found;
1021
1022         found = __find_space_info(info, flags);
1023         if (found) {
1024                 found->total_bytes += total_bytes;
1025                 found->bytes_used += bytes_used;
1026                 found->full = 0;
1027                 WARN_ON(found->total_bytes < found->bytes_used);
1028                 *space_info = found;
1029                 return 0;
1030         }
1031         found = kmalloc(sizeof(*found), GFP_NOFS);
1032         if (!found)
1033                 return -ENOMEM;
1034
1035         list_add(&found->list, &info->space_info);
1036         found->flags = flags;
1037         found->total_bytes = total_bytes;
1038         found->bytes_used = bytes_used;
1039         found->bytes_pinned = 0;
1040         found->full = 0;
1041         *space_info = found;
1042         return 0;
1043 }
1044
1045 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1046 {
1047         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1048                                    BTRFS_BLOCK_GROUP_RAID1 |
1049                                    BTRFS_BLOCK_GROUP_RAID10 |
1050                                    BTRFS_BLOCK_GROUP_DUP);
1051         if (extra_flags) {
1052                 if (flags & BTRFS_BLOCK_GROUP_DATA)
1053                         fs_info->avail_data_alloc_bits |= extra_flags;
1054                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1055                         fs_info->avail_metadata_alloc_bits |= extra_flags;
1056                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1057                         fs_info->avail_system_alloc_bits |= extra_flags;
1058         }
1059 }
1060
1061 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1062                           struct btrfs_root *extent_root, u64 alloc_bytes,
1063                           u64 flags)
1064 {
1065         struct btrfs_space_info *space_info;
1066         u64 thresh;
1067         u64 start;
1068         u64 num_bytes;
1069         int ret;
1070
1071         space_info = __find_space_info(extent_root->fs_info, flags);
1072         if (!space_info) {
1073                 ret = update_space_info(extent_root->fs_info, flags,
1074                                         0, 0, &space_info);
1075                 BUG_ON(ret);
1076         }
1077         BUG_ON(!space_info);
1078
1079         if (space_info->full)
1080                 return 0;
1081
1082         thresh = div_factor(space_info->total_bytes, 6);
1083         if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
1084             thresh)
1085                 return 0;
1086
1087         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
1088         if (ret == -ENOSPC) {
1089 printk("space info full %Lu\n", flags);
1090                 space_info->full = 1;
1091                 return 0;
1092         }
1093
1094         BUG_ON(ret);
1095
1096         ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1097                      BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1098         BUG_ON(ret);
1099
1100         return 0;
1101 }
1102
1103 static int update_block_group(struct btrfs_trans_handle *trans,
1104                               struct btrfs_root *root,
1105                               u64 bytenr, u64 num_bytes, int alloc,
1106                               int mark_free)
1107 {
1108         struct btrfs_block_group_cache *cache;
1109         struct btrfs_fs_info *info = root->fs_info;
1110         u64 total = num_bytes;
1111         u64 old_val;
1112         u64 byte_in_group;
1113         u64 start;
1114         u64 end;
1115
1116         while(total) {
1117                 cache = btrfs_lookup_block_group(info, bytenr);
1118                 if (!cache) {
1119                         return -1;
1120                 }
1121                 byte_in_group = bytenr - cache->key.objectid;
1122                 WARN_ON(byte_in_group > cache->key.offset);
1123                 start = cache->key.objectid;
1124                 end = start + cache->key.offset - 1;
1125                 set_extent_bits(&info->block_group_cache, start, end,
1126                                 BLOCK_GROUP_DIRTY, GFP_NOFS);
1127
1128                 old_val = btrfs_block_group_used(&cache->item);
1129                 num_bytes = min(total, cache->key.offset - byte_in_group);
1130                 if (alloc) {
1131                         old_val += num_bytes;
1132                         cache->space_info->bytes_used += num_bytes;
1133                 } else {
1134                         old_val -= num_bytes;
1135                         cache->space_info->bytes_used -= num_bytes;
1136                         if (mark_free) {
1137                                 set_extent_dirty(&info->free_space_cache,
1138                                                  bytenr, bytenr + num_bytes - 1,
1139                                                  GFP_NOFS);
1140                         }
1141                 }
1142                 btrfs_set_block_group_used(&cache->item, old_val);
1143                 total -= num_bytes;
1144                 bytenr += num_bytes;
1145         }
1146         return 0;
1147 }
1148
1149 static int update_pinned_extents(struct btrfs_root *root,
1150                                 u64 bytenr, u64 num, int pin)
1151 {
1152         u64 len;
1153         struct btrfs_block_group_cache *cache;
1154         struct btrfs_fs_info *fs_info = root->fs_info;
1155
1156         if (pin) {
1157                 set_extent_dirty(&fs_info->pinned_extents,
1158                                 bytenr, bytenr + num - 1, GFP_NOFS);
1159         } else {
1160                 clear_extent_dirty(&fs_info->pinned_extents,
1161                                 bytenr, bytenr + num - 1, GFP_NOFS);
1162         }
1163         while (num > 0) {
1164                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1165                 WARN_ON(!cache);
1166                 len = min(num, cache->key.offset -
1167                           (bytenr - cache->key.objectid));
1168                 if (pin) {
1169                         cache->pinned += len;
1170                         cache->space_info->bytes_pinned += len;
1171                         fs_info->total_pinned += len;
1172                 } else {
1173                         cache->pinned -= len;
1174                         cache->space_info->bytes_pinned -= len;
1175                         fs_info->total_pinned -= len;
1176                 }
1177                 bytenr += len;
1178                 num -= len;
1179         }
1180         return 0;
1181 }
1182
1183 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
1184 {
1185         u64 last = 0;
1186         u64 start;
1187         u64 end;
1188         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
1189         int ret;
1190
1191         while(1) {
1192                 ret = find_first_extent_bit(pinned_extents, last,
1193                                             &start, &end, EXTENT_DIRTY);
1194                 if (ret)
1195                         break;
1196                 set_extent_dirty(copy, start, end, GFP_NOFS);
1197                 last = end + 1;
1198         }
1199         return 0;
1200 }
1201
1202 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1203                                struct btrfs_root *root,
1204                                struct extent_io_tree *unpin)
1205 {
1206         u64 start;
1207         u64 end;
1208         int ret;
1209         struct extent_io_tree *free_space_cache;
1210         free_space_cache = &root->fs_info->free_space_cache;
1211
1212         while(1) {
1213                 ret = find_first_extent_bit(unpin, 0, &start, &end,
1214                                             EXTENT_DIRTY);
1215                 if (ret)
1216                         break;
1217                 update_pinned_extents(root, start, end + 1 - start, 0);
1218                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1219                 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1220         }
1221         return 0;
1222 }
1223
1224 static int finish_current_insert(struct btrfs_trans_handle *trans,
1225                                  struct btrfs_root *extent_root)
1226 {
1227         u64 start;
1228         u64 end;
1229         struct btrfs_fs_info *info = extent_root->fs_info;
1230         struct extent_buffer *eb;
1231         struct btrfs_path *path;
1232         struct btrfs_key ins;
1233         struct btrfs_disk_key first;
1234         struct btrfs_extent_item extent_item;
1235         int ret;
1236         int level;
1237         int err = 0;
1238
1239         btrfs_set_stack_extent_refs(&extent_item, 1);
1240         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1241         path = btrfs_alloc_path();
1242
1243         while(1) {
1244                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1245                                             &end, EXTENT_LOCKED);
1246                 if (ret)
1247                         break;
1248
1249                 ins.objectid = start;
1250                 ins.offset = end + 1 - start;
1251                 err = btrfs_insert_item(trans, extent_root, &ins,
1252                                         &extent_item, sizeof(extent_item));
1253                 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
1254                                   GFP_NOFS);
1255                 eb = read_tree_block(extent_root, ins.objectid, ins.offset);
1256                 level = btrfs_header_level(eb);
1257                 if (level == 0) {
1258                         btrfs_item_key(eb, &first, 0);
1259                 } else {
1260                         btrfs_node_key(eb, &first, 0);
1261                 }
1262                 err = btrfs_insert_extent_backref(trans, extent_root, path,
1263                                           start, extent_root->root_key.objectid,
1264                                           0, level,
1265                                           btrfs_disk_key_objectid(&first));
1266                 BUG_ON(err);
1267                 free_extent_buffer(eb);
1268         }
1269         btrfs_free_path(path);
1270         return 0;
1271 }
1272
1273 static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
1274                           int pending)
1275 {
1276         int err = 0;
1277         struct extent_buffer *buf;
1278
1279         if (!pending) {
1280                 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1281                 if (buf) {
1282                         if (btrfs_buffer_uptodate(buf)) {
1283                                 u64 transid =
1284                                     root->fs_info->running_transaction->transid;
1285                                 u64 header_transid =
1286                                         btrfs_header_generation(buf);
1287                                 if (header_transid == transid &&
1288                                     !btrfs_header_flag(buf,
1289                                                BTRFS_HEADER_FLAG_WRITTEN)) {
1290                                         clean_tree_block(NULL, root, buf);
1291                                         free_extent_buffer(buf);
1292                                         return 1;
1293                                 }
1294                         }
1295                         free_extent_buffer(buf);
1296                 }
1297                 update_pinned_extents(root, bytenr, num_bytes, 1);
1298         } else {
1299                 set_extent_bits(&root->fs_info->pending_del,
1300                                 bytenr, bytenr + num_bytes - 1,
1301                                 EXTENT_LOCKED, GFP_NOFS);
1302         }
1303         BUG_ON(err < 0);
1304         return 0;
1305 }
1306
1307 /*
1308  * remove an extent from the root, returns 0 on success
1309  */
1310 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1311                          *root, u64 bytenr, u64 num_bytes,
1312                          u64 root_objectid, u64 ref_generation,
1313                          u64 owner_objectid, u64 owner_offset, int pin,
1314                          int mark_free)
1315 {
1316         struct btrfs_path *path;
1317         struct btrfs_key key;
1318         struct btrfs_fs_info *info = root->fs_info;
1319         struct btrfs_root *extent_root = info->extent_root;
1320         struct extent_buffer *leaf;
1321         int ret;
1322         int extent_slot = 0;
1323         int found_extent = 0;
1324         int num_to_del = 1;
1325         struct btrfs_extent_item *ei;
1326         u32 refs;
1327
1328         key.objectid = bytenr;
1329         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1330         key.offset = num_bytes;
1331         path = btrfs_alloc_path();
1332         if (!path)
1333                 return -ENOMEM;
1334
1335         path->reada = 1;
1336         ret = lookup_extent_backref(trans, extent_root, path,
1337                                     bytenr, root_objectid,
1338                                     ref_generation,
1339                                     owner_objectid, owner_offset, 1);
1340         if (ret == 0) {
1341                 struct btrfs_key found_key;
1342                 extent_slot = path->slots[0];
1343                 while(extent_slot > 0) {
1344                         extent_slot--;
1345                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1346                                               extent_slot);
1347                         if (found_key.objectid != bytenr)
1348                                 break;
1349                         if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
1350                             found_key.offset == num_bytes) {
1351                                 found_extent = 1;
1352                                 break;
1353                         }
1354                         if (path->slots[0] - extent_slot > 5)
1355                                 break;
1356                 }
1357                 if (!found_extent)
1358                         ret = btrfs_del_item(trans, extent_root, path);
1359         } else {
1360                 btrfs_print_leaf(extent_root, path->nodes[0]);
1361                 WARN_ON(1);
1362                 printk("Unable to find ref byte nr %Lu root %Lu "
1363                        " gen %Lu owner %Lu offset %Lu\n", bytenr,
1364                        root_objectid, ref_generation, owner_objectid,
1365                        owner_offset);
1366         }
1367         if (!found_extent) {
1368                 btrfs_release_path(extent_root, path);
1369                 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
1370                 if (ret < 0)
1371                         return ret;
1372                 BUG_ON(ret);
1373                 extent_slot = path->slots[0];
1374         }
1375
1376         leaf = path->nodes[0];
1377         ei = btrfs_item_ptr(leaf, extent_slot,
1378                             struct btrfs_extent_item);
1379         refs = btrfs_extent_refs(leaf, ei);
1380         BUG_ON(refs == 0);
1381         refs -= 1;
1382         btrfs_set_extent_refs(leaf, ei, refs);
1383
1384         btrfs_mark_buffer_dirty(leaf);
1385
1386         if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
1387                 /* if the back ref and the extent are next to each other
1388                  * they get deleted below in one shot
1389                  */
1390                 path->slots[0] = extent_slot;
1391                 num_to_del = 2;
1392         } else if (found_extent) {
1393                 /* otherwise delete the extent back ref */
1394                 ret = btrfs_del_item(trans, extent_root, path);
1395                 BUG_ON(ret);
1396                 /* if refs are 0, we need to setup the path for deletion */
1397                 if (refs == 0) {
1398                         btrfs_release_path(extent_root, path);
1399                         ret = btrfs_search_slot(trans, extent_root, &key, path,
1400                                                 -1, 1);
1401                         if (ret < 0)
1402                                 return ret;
1403                         BUG_ON(ret);
1404                 }
1405         }
1406
1407         if (refs == 0) {
1408                 u64 super_used;
1409                 u64 root_used;
1410
1411                 if (pin) {
1412                         ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1413                         if (ret > 0)
1414                                 mark_free = 1;
1415                         BUG_ON(ret < 0);
1416                 }
1417
1418                 /* block accounting for super block */
1419                 super_used = btrfs_super_bytes_used(&info->super_copy);
1420                 btrfs_set_super_bytes_used(&info->super_copy,
1421                                            super_used - num_bytes);
1422
1423                 /* block accounting for root item */
1424                 root_used = btrfs_root_used(&root->root_item);
1425                 btrfs_set_root_used(&root->root_item,
1426                                            root_used - num_bytes);
1427                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
1428                                       num_to_del);
1429                 if (ret) {
1430                         return ret;
1431                 }
1432                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1433                                          mark_free);
1434                 BUG_ON(ret);
1435         }
1436         btrfs_free_path(path);
1437         finish_current_insert(trans, extent_root);
1438         return ret;
1439 }
1440
1441 /*
1442  * find all the blocks marked as pending in the radix tree and remove
1443  * them from the extent map
1444  */
1445 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
1446                                btrfs_root *extent_root)
1447 {
1448         int ret;
1449         int err = 0;
1450         u64 start;
1451         u64 end;
1452         struct extent_io_tree *pending_del;
1453         struct extent_io_tree *pinned_extents;
1454
1455         pending_del = &extent_root->fs_info->pending_del;
1456         pinned_extents = &extent_root->fs_info->pinned_extents;
1457
1458         while(1) {
1459                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
1460                                             EXTENT_LOCKED);
1461                 if (ret)
1462                         break;
1463                 update_pinned_extents(extent_root, start, end + 1 - start, 1);
1464                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
1465                                   GFP_NOFS);
1466                 ret = __free_extent(trans, extent_root,
1467                                      start, end + 1 - start,
1468                                      extent_root->root_key.objectid,
1469                                      0, 0, 0, 0, 0);
1470                 if (ret)
1471                         err = ret;
1472         }
1473         return err;
1474 }
1475
1476 /*
1477  * remove an extent from the root, returns 0 on success
1478  */
1479 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1480                       *root, u64 bytenr, u64 num_bytes,
1481                       u64 root_objectid, u64 ref_generation,
1482                       u64 owner_objectid, u64 owner_offset, int pin)
1483 {
1484         struct btrfs_root *extent_root = root->fs_info->extent_root;
1485         int pending_ret;
1486         int ret;
1487
1488         WARN_ON(num_bytes < root->sectorsize);
1489         if (!root->ref_cows)
1490                 ref_generation = 0;
1491
1492         if (root == extent_root) {
1493                 pin_down_bytes(root, bytenr, num_bytes, 1);
1494                 return 0;
1495         }
1496         ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
1497                             ref_generation, owner_objectid, owner_offset,
1498                             pin, pin == 0);
1499         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1500         return ret ? ret : pending_ret;
1501 }
1502
1503 static u64 stripe_align(struct btrfs_root *root, u64 val)
1504 {
1505         u64 mask = ((u64)root->stripesize - 1);
1506         u64 ret = (val + mask) & ~mask;
1507         return ret;
1508 }
1509
1510 /*
1511  * walks the btree of allocated extents and find a hole of a given size.
1512  * The key ins is changed to record the hole:
1513  * ins->objectid == block start
1514  * ins->flags = BTRFS_EXTENT_ITEM_KEY
1515  * ins->offset == number of blocks
1516  * Any available blocks before search_start are skipped.
1517  */
1518 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1519                                      struct btrfs_root *orig_root,
1520                                      u64 num_bytes, u64 empty_size,
1521                                      u64 search_start, u64 search_end,
1522                                      u64 hint_byte, struct btrfs_key *ins,
1523                                      u64 exclude_start, u64 exclude_nr,
1524                                      int data)
1525 {
1526         int ret;
1527         u64 orig_search_start = search_start;
1528         struct btrfs_root * root = orig_root->fs_info->extent_root;
1529         struct btrfs_fs_info *info = root->fs_info;
1530         u64 total_needed = num_bytes;
1531         u64 *last_ptr = NULL;
1532         struct btrfs_block_group_cache *block_group;
1533         int full_scan = 0;
1534         int wrapped = 0;
1535         int empty_cluster = 2 * 1024 * 1024;
1536
1537         WARN_ON(num_bytes < root->sectorsize);
1538         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1539
1540         if (data & BTRFS_BLOCK_GROUP_METADATA) {
1541                 last_ptr = &root->fs_info->last_alloc;
1542                 empty_cluster = 256 * 1024;
1543         }
1544
1545         if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
1546                 last_ptr = &root->fs_info->last_data_alloc;
1547         }
1548
1549         if (last_ptr) {
1550                 if (*last_ptr)
1551                         hint_byte = *last_ptr;
1552                 else {
1553                         empty_size += empty_cluster;
1554                 }
1555         }
1556
1557         if (search_end == (u64)-1)
1558                 search_end = btrfs_super_total_bytes(&info->super_copy);
1559
1560         if (hint_byte) {
1561                 block_group = btrfs_lookup_block_group(info, hint_byte);
1562                 if (!block_group)
1563                         hint_byte = search_start;
1564                 block_group = btrfs_find_block_group(root, block_group,
1565                                                      hint_byte, data, 1);
1566                 if (last_ptr && *last_ptr == 0 && block_group)
1567                         hint_byte = block_group->key.objectid;
1568         } else {
1569                 block_group = btrfs_find_block_group(root,
1570                                                      trans->block_group,
1571                                                      search_start, data, 1);
1572         }
1573         search_start = max(search_start, hint_byte);
1574
1575         total_needed += empty_size;
1576
1577 check_failed:
1578         if (!block_group) {
1579                 block_group = btrfs_lookup_block_group(info, search_start);
1580                 if (!block_group)
1581                         block_group = btrfs_lookup_block_group(info,
1582                                                        orig_search_start);
1583         }
1584         ret = find_search_start(root, &block_group, &search_start,
1585                                 total_needed, data);
1586         if (ret == -ENOSPC && last_ptr && *last_ptr) {
1587                 *last_ptr = 0;
1588                 block_group = btrfs_lookup_block_group(info,
1589                                                        orig_search_start);
1590                 search_start = orig_search_start;
1591                 ret = find_search_start(root, &block_group, &search_start,
1592                                         total_needed, data);
1593         }
1594         if (ret == -ENOSPC)
1595                 goto enospc;
1596         if (ret)
1597                 goto error;
1598
1599         if (last_ptr && *last_ptr && search_start != *last_ptr) {
1600                 *last_ptr = 0;
1601                 if (!empty_size) {
1602                         empty_size += empty_cluster;
1603                         total_needed += empty_size;
1604                 }
1605                 block_group = btrfs_lookup_block_group(info,
1606                                                        orig_search_start);
1607                 search_start = orig_search_start;
1608                 ret = find_search_start(root, &block_group,
1609                                         &search_start, total_needed, data);
1610                 if (ret == -ENOSPC)
1611                         goto enospc;
1612                 if (ret)
1613                         goto error;
1614         }
1615
1616         search_start = stripe_align(root, search_start);
1617         ins->objectid = search_start;
1618         ins->offset = num_bytes;
1619
1620         if (ins->objectid + num_bytes >= search_end)
1621                 goto enospc;
1622
1623         if (ins->objectid + num_bytes >
1624             block_group->key.objectid + block_group->key.offset) {
1625                 search_start = block_group->key.objectid +
1626                         block_group->key.offset;
1627                 goto new_group;
1628         }
1629
1630         if (test_range_bit(&info->extent_ins, ins->objectid,
1631                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1632                 search_start = ins->objectid + num_bytes;
1633                 goto new_group;
1634         }
1635
1636         if (test_range_bit(&info->pinned_extents, ins->objectid,
1637                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1638                 search_start = ins->objectid + num_bytes;
1639                 goto new_group;
1640         }
1641
1642         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1643             ins->objectid < exclude_start + exclude_nr)) {
1644                 search_start = exclude_start + exclude_nr;
1645                 goto new_group;
1646         }
1647
1648         if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
1649                 block_group = btrfs_lookup_block_group(info, ins->objectid);
1650                 if (block_group)
1651                         trans->block_group = block_group;
1652         }
1653         ins->offset = num_bytes;
1654         if (last_ptr) {
1655                 *last_ptr = ins->objectid + ins->offset;
1656                 if (*last_ptr ==
1657                     btrfs_super_total_bytes(&root->fs_info->super_copy)) {
1658                         *last_ptr = 0;
1659                 }
1660         }
1661         return 0;
1662
1663 new_group:
1664         if (search_start + num_bytes >= search_end) {
1665 enospc:
1666                 search_start = orig_search_start;
1667                 if (full_scan) {
1668                         ret = -ENOSPC;
1669                         goto error;
1670                 }
1671                 if (wrapped) {
1672                         if (!full_scan)
1673                                 total_needed -= empty_size;
1674                         full_scan = 1;
1675                 } else
1676                         wrapped = 1;
1677         }
1678         block_group = btrfs_lookup_block_group(info, search_start);
1679         cond_resched();
1680         block_group = btrfs_find_block_group(root, block_group,
1681                                              search_start, data, 0);
1682         goto check_failed;
1683
1684 error:
1685         return ret;
1686 }
1687 /*
1688  * finds a free extent and does all the dirty work required for allocation
1689  * returns the key for the extent through ins, and a tree buffer for
1690  * the first block of the extent through buf.
1691  *
1692  * returns 0 if everything worked, non-zero otherwise.
1693  */
1694 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1695                        struct btrfs_root *root,
1696                        u64 num_bytes, u64 min_alloc_size,
1697                        u64 root_objectid, u64 ref_generation,
1698                        u64 owner, u64 owner_offset,
1699                        u64 empty_size, u64 hint_byte,
1700                        u64 search_end, struct btrfs_key *ins, int data)
1701 {
1702         int ret;
1703         int pending_ret;
1704         u64 super_used;
1705         u64 root_used;
1706         u64 search_start = 0;
1707         u64 alloc_profile;
1708         u32 sizes[2];
1709         struct btrfs_fs_info *info = root->fs_info;
1710         struct btrfs_root *extent_root = info->extent_root;
1711         struct btrfs_extent_item *extent_item;
1712         struct btrfs_extent_ref *ref;
1713         struct btrfs_path *path;
1714         struct btrfs_key keys[2];
1715
1716         if (data) {
1717                 alloc_profile = info->avail_data_alloc_bits &
1718                                 info->data_alloc_profile;
1719                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
1720         } else if (root == root->fs_info->chunk_root) {
1721                 alloc_profile = info->avail_system_alloc_bits &
1722                                 info->system_alloc_profile;
1723                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
1724         } else {
1725                 alloc_profile = info->avail_metadata_alloc_bits &
1726                                 info->metadata_alloc_profile;
1727                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
1728         }
1729 again:
1730         if (root->ref_cows) {
1731                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
1732                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1733                                              2 * 1024 * 1024,
1734                                              BTRFS_BLOCK_GROUP_METADATA |
1735                                              (info->metadata_alloc_profile &
1736                                               info->avail_metadata_alloc_bits));
1737                         BUG_ON(ret);
1738                 }
1739                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1740                                      num_bytes + 2 * 1024 * 1024, data);
1741                 BUG_ON(ret);
1742         }
1743
1744         WARN_ON(num_bytes < root->sectorsize);
1745         ret = find_free_extent(trans, root, num_bytes, empty_size,
1746                                search_start, search_end, hint_byte, ins,
1747                                trans->alloc_exclude_start,
1748                                trans->alloc_exclude_nr, data);
1749
1750         if (ret == -ENOSPC && num_bytes > min_alloc_size) {
1751                 num_bytes = num_bytes >> 1;
1752                 num_bytes = max(num_bytes, min_alloc_size);
1753                 goto again;
1754         }
1755         BUG_ON(ret);
1756         if (ret)
1757                 return ret;
1758
1759         /* block accounting for super block */
1760         super_used = btrfs_super_bytes_used(&info->super_copy);
1761         btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1762
1763         /* block accounting for root item */
1764         root_used = btrfs_root_used(&root->root_item);
1765         btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1766
1767         clear_extent_dirty(&root->fs_info->free_space_cache,
1768                            ins->objectid, ins->objectid + ins->offset - 1,
1769                            GFP_NOFS);
1770
1771         if (root == extent_root) {
1772                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1773                                 ins->objectid + ins->offset - 1,
1774                                 EXTENT_LOCKED, GFP_NOFS);
1775                 goto update_block;
1776         }
1777
1778         WARN_ON(trans->alloc_exclude_nr);
1779         trans->alloc_exclude_start = ins->objectid;
1780         trans->alloc_exclude_nr = ins->offset;
1781
1782         memcpy(&keys[0], ins, sizeof(*ins));
1783         keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
1784                                          owner, owner_offset);
1785         keys[1].objectid = ins->objectid;
1786         keys[1].type = BTRFS_EXTENT_REF_KEY;
1787         sizes[0] = sizeof(*extent_item);
1788         sizes[1] = sizeof(*ref);
1789
1790         path = btrfs_alloc_path();
1791         BUG_ON(!path);
1792
1793         ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
1794                                        sizes, 2);
1795
1796         BUG_ON(ret);
1797         extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1798                                      struct btrfs_extent_item);
1799         btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
1800         ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
1801                              struct btrfs_extent_ref);
1802
1803         btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
1804         btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
1805         btrfs_set_ref_objectid(path->nodes[0], ref, owner);
1806         btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
1807
1808         btrfs_mark_buffer_dirty(path->nodes[0]);
1809
1810         trans->alloc_exclude_start = 0;
1811         trans->alloc_exclude_nr = 0;
1812         btrfs_free_path(path);
1813         finish_current_insert(trans, extent_root);
1814         pending_ret = del_pending_extents(trans, extent_root);
1815
1816         if (ret) {
1817                 return ret;
1818         }
1819         if (pending_ret) {
1820                 return pending_ret;
1821         }
1822
1823 update_block:
1824         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
1825         if (ret) {
1826                 printk("update block group failed for %Lu %Lu\n",
1827                        ins->objectid, ins->offset);
1828                 BUG();
1829         }
1830         return 0;
1831 }
1832
1833 /*
1834  * helper function to allocate a block for a given tree
1835  * returns the tree buffer or NULL.
1836  */
1837 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1838                                              struct btrfs_root *root,
1839                                              u32 blocksize,
1840                                              u64 root_objectid, u64 hint,
1841                                              u64 empty_size)
1842 {
1843         u64 ref_generation;
1844
1845         if (root->ref_cows)
1846                 ref_generation = trans->transid;
1847         else
1848                 ref_generation = 0;
1849
1850
1851         return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
1852                                         ref_generation, 0, 0, hint, empty_size);
1853 }
1854
1855 /*
1856  * helper function to allocate a block for a given tree
1857  * returns the tree buffer or NULL.
1858  */
1859 struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1860                                              struct btrfs_root *root,
1861                                              u32 blocksize,
1862                                              u64 root_objectid,
1863                                              u64 ref_generation,
1864                                              u64 first_objectid,
1865                                              int level,
1866                                              u64 hint,
1867                                              u64 empty_size)
1868 {
1869         struct btrfs_key ins;
1870         int ret;
1871         struct extent_buffer *buf;
1872
1873         ret = btrfs_alloc_extent(trans, root, blocksize, blocksize,
1874                                  root_objectid, ref_generation,
1875                                  level, first_objectid, empty_size, hint,
1876                                  (u64)-1, &ins, 0);
1877         if (ret) {
1878                 BUG_ON(ret > 0);
1879                 return ERR_PTR(ret);
1880         }
1881         buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1882         if (!buf) {
1883                 btrfs_free_extent(trans, root, ins.objectid, blocksize,
1884                                   root->root_key.objectid, ref_generation,
1885                                   0, 0, 0);
1886                 return ERR_PTR(-ENOMEM);
1887         }
1888         btrfs_set_header_generation(buf, trans->transid);
1889         clean_tree_block(trans, root, buf);
1890         btrfs_set_buffer_uptodate(buf);
1891
1892         if (PageDirty(buf->first_page)) {
1893                 printk("page %lu dirty\n", buf->first_page->index);
1894                 WARN_ON(1);
1895         }
1896
1897         set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1898                          buf->start + buf->len - 1, GFP_NOFS);
1899         if (!btrfs_test_opt(root, SSD))
1900                 btrfs_set_buffer_defrag(buf);
1901         trans->blocks_used++;
1902         return buf;
1903 }
1904
1905 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
1906                                   struct btrfs_root *root,
1907                                   struct extent_buffer *leaf)
1908 {
1909         u64 leaf_owner;
1910         u64 leaf_generation;
1911         struct btrfs_key key;
1912         struct btrfs_file_extent_item *fi;
1913         int i;
1914         int nritems;
1915         int ret;
1916
1917         BUG_ON(!btrfs_is_leaf(leaf));
1918         nritems = btrfs_header_nritems(leaf);
1919         leaf_owner = btrfs_header_owner(leaf);
1920         leaf_generation = btrfs_header_generation(leaf);
1921
1922         for (i = 0; i < nritems; i++) {
1923                 u64 disk_bytenr;
1924
1925                 btrfs_item_key_to_cpu(leaf, &key, i);
1926                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1927                         continue;
1928                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1929                 if (btrfs_file_extent_type(leaf, fi) ==
1930                     BTRFS_FILE_EXTENT_INLINE)
1931                         continue;
1932                 /*
1933                  * FIXME make sure to insert a trans record that
1934                  * repeats the snapshot del on crash
1935                  */
1936                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1937                 if (disk_bytenr == 0)
1938                         continue;
1939                 ret = btrfs_free_extent(trans, root, disk_bytenr,
1940                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
1941                                 leaf_owner, leaf_generation,
1942                                 key.objectid, key.offset, 0);
1943                 BUG_ON(ret);
1944         }
1945         return 0;
1946 }
1947
1948 static void noinline reada_walk_down(struct btrfs_root *root,
1949                                      struct extent_buffer *node,
1950                                      int slot)
1951 {
1952         u64 bytenr;
1953         u64 last = 0;
1954         u32 nritems;
1955         u32 refs;
1956         u32 blocksize;
1957         int ret;
1958         int i;
1959         int level;
1960         int skipped = 0;
1961
1962         nritems = btrfs_header_nritems(node);
1963         level = btrfs_header_level(node);
1964         if (level)
1965                 return;
1966
1967         for (i = slot; i < nritems && skipped < 32; i++) {
1968                 bytenr = btrfs_node_blockptr(node, i);
1969                 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
1970                              (last > bytenr && last - bytenr > 32 * 1024))) {
1971                         skipped++;
1972                         continue;
1973                 }
1974                 blocksize = btrfs_level_size(root, level - 1);
1975                 if (i != slot) {
1976                         ret = lookup_extent_ref(NULL, root, bytenr,
1977                                                 blocksize, &refs);
1978                         BUG_ON(ret);
1979                         if (refs != 1) {
1980                                 skipped++;
1981                                 continue;
1982                         }
1983                 }
1984                 mutex_unlock(&root->fs_info->fs_mutex);
1985                 ret = readahead_tree_block(root, bytenr, blocksize);
1986                 last = bytenr + blocksize;
1987                 cond_resched();
1988                 mutex_lock(&root->fs_info->fs_mutex);
1989                 if (ret)
1990                         break;
1991         }
1992 }
1993
1994 /*
1995  * helper function for drop_snapshot, this walks down the tree dropping ref
1996  * counts as it goes.
1997  */
1998 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
1999                                    struct btrfs_root *root,
2000                                    struct btrfs_path *path, int *level)
2001 {
2002         u64 root_owner;
2003         u64 root_gen;
2004         u64 bytenr;
2005         struct extent_buffer *next;
2006         struct extent_buffer *cur;
2007         struct extent_buffer *parent;
2008         u32 blocksize;
2009         int ret;
2010         u32 refs;
2011
2012         WARN_ON(*level < 0);
2013         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2014         ret = lookup_extent_ref(trans, root,
2015                                 path->nodes[*level]->start,
2016                                 path->nodes[*level]->len, &refs);
2017         BUG_ON(ret);
2018         if (refs > 1)
2019                 goto out;
2020
2021         /*
2022          * walk down to the last node level and free all the leaves
2023          */
2024         while(*level >= 0) {
2025                 WARN_ON(*level < 0);
2026                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2027                 cur = path->nodes[*level];
2028
2029                 if (btrfs_header_level(cur) != *level)
2030                         WARN_ON(1);
2031
2032                 if (path->slots[*level] >=
2033                     btrfs_header_nritems(cur))
2034                         break;
2035                 if (*level == 0) {
2036                         ret = drop_leaf_ref(trans, root, cur);
2037                         BUG_ON(ret);
2038                         break;
2039                 }
2040                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2041                 blocksize = btrfs_level_size(root, *level - 1);
2042                 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
2043                 BUG_ON(ret);
2044                 if (refs != 1) {
2045                         parent = path->nodes[*level];
2046                         root_owner = btrfs_header_owner(parent);
2047                         root_gen = btrfs_header_generation(parent);
2048                         path->slots[*level]++;
2049                         ret = btrfs_free_extent(trans, root, bytenr,
2050                                                 blocksize, root_owner,
2051                                                 root_gen, 0, 0, 1);
2052                         BUG_ON(ret);
2053                         continue;
2054                 }
2055                 next = btrfs_find_tree_block(root, bytenr, blocksize);
2056                 if (!next || !btrfs_buffer_uptodate(next)) {
2057                         free_extent_buffer(next);
2058                         reada_walk_down(root, cur, path->slots[*level]);
2059
2060                         mutex_unlock(&root->fs_info->fs_mutex);
2061                         next = read_tree_block(root, bytenr, blocksize);
2062                         mutex_lock(&root->fs_info->fs_mutex);
2063
2064                         /* we've dropped the lock, double check */
2065                         ret = lookup_extent_ref(trans, root, bytenr,
2066                                                 blocksize, &refs);
2067                         BUG_ON(ret);
2068                         if (refs != 1) {
2069                                 parent = path->nodes[*level];
2070                                 root_owner = btrfs_header_owner(parent);
2071                                 root_gen = btrfs_header_generation(parent);
2072
2073                                 path->slots[*level]++;
2074                                 free_extent_buffer(next);
2075                                 ret = btrfs_free_extent(trans, root, bytenr,
2076                                                         blocksize,
2077                                                         root_owner,
2078                                                         root_gen, 0, 0, 1);
2079                                 BUG_ON(ret);
2080                                 continue;
2081                         }
2082                 } else if (next) {
2083                         btrfs_verify_block_csum(root, next);
2084                 }
2085                 WARN_ON(*level <= 0);
2086                 if (path->nodes[*level-1])
2087                         free_extent_buffer(path->nodes[*level-1]);
2088                 path->nodes[*level-1] = next;
2089                 *level = btrfs_header_level(next);
2090                 path->slots[*level] = 0;
2091         }
2092 out:
2093         WARN_ON(*level < 0);
2094         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2095
2096         if (path->nodes[*level] == root->node) {
2097                 root_owner = root->root_key.objectid;
2098                 parent = path->nodes[*level];
2099         } else {
2100                 parent = path->nodes[*level + 1];
2101                 root_owner = btrfs_header_owner(parent);
2102         }
2103
2104         root_gen = btrfs_header_generation(parent);
2105         ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
2106                                 path->nodes[*level]->len,
2107                                 root_owner, root_gen, 0, 0, 1);
2108         free_extent_buffer(path->nodes[*level]);
2109         path->nodes[*level] = NULL;
2110         *level += 1;
2111         BUG_ON(ret);
2112         return 0;
2113 }
2114
2115 /*
2116  * helper for dropping snapshots.  This walks back up the tree in the path
2117  * to find the first node higher up where we haven't yet gone through
2118  * all the slots
2119  */
2120 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
2121                                  struct btrfs_root *root,
2122                                  struct btrfs_path *path, int *level)
2123 {
2124         u64 root_owner;
2125         u64 root_gen;
2126         struct btrfs_root_item *root_item = &root->root_item;
2127         int i;
2128         int slot;
2129         int ret;
2130
2131         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2132                 slot = path->slots[i];
2133                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
2134                         struct extent_buffer *node;
2135                         struct btrfs_disk_key disk_key;
2136                         node = path->nodes[i];
2137                         path->slots[i]++;
2138                         *level = i;
2139                         WARN_ON(*level == 0);
2140                         btrfs_node_key(node, &disk_key, path->slots[i]);
2141                         memcpy(&root_item->drop_progress,
2142                                &disk_key, sizeof(disk_key));
2143                         root_item->drop_level = i;
2144                         return 0;
2145                 } else {
2146                         if (path->nodes[*level] == root->node) {
2147                                 root_owner = root->root_key.objectid;
2148                                 root_gen =
2149                                    btrfs_header_generation(path->nodes[*level]);
2150                         } else {
2151                                 struct extent_buffer *node;
2152                                 node = path->nodes[*level + 1];
2153                                 root_owner = btrfs_header_owner(node);
2154                                 root_gen = btrfs_header_generation(node);
2155                         }
2156                         ret = btrfs_free_extent(trans, root,
2157                                                 path->nodes[*level]->start,
2158                                                 path->nodes[*level]->len,
2159                                                 root_owner, root_gen, 0, 0, 1);
2160                         BUG_ON(ret);
2161                         free_extent_buffer(path->nodes[*level]);
2162                         path->nodes[*level] = NULL;
2163                         *level = i + 1;
2164                 }
2165         }
2166         return 1;
2167 }
2168
2169 /*
2170  * drop the reference count on the tree rooted at 'snap'.  This traverses
2171  * the tree freeing any blocks that have a ref count of zero after being
2172  * decremented.
2173  */
2174 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2175                         *root)
2176 {
2177         int ret = 0;
2178         int wret;
2179         int level;
2180         struct btrfs_path *path;
2181         int i;
2182         int orig_level;
2183         struct btrfs_root_item *root_item = &root->root_item;
2184
2185         path = btrfs_alloc_path();
2186         BUG_ON(!path);
2187
2188         level = btrfs_header_level(root->node);
2189         orig_level = level;
2190         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2191                 path->nodes[level] = root->node;
2192                 extent_buffer_get(root->node);
2193                 path->slots[level] = 0;
2194         } else {
2195                 struct btrfs_key key;
2196                 struct btrfs_disk_key found_key;
2197                 struct extent_buffer *node;
2198
2199                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2200                 level = root_item->drop_level;
2201                 path->lowest_level = level;
2202                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2203                 if (wret < 0) {
2204                         ret = wret;
2205                         goto out;
2206                 }
2207                 node = path->nodes[level];
2208                 btrfs_node_key(node, &found_key, path->slots[level]);
2209                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2210                                sizeof(found_key)));
2211         }
2212         while(1) {
2213                 wret = walk_down_tree(trans, root, path, &level);
2214                 if (wret > 0)
2215                         break;
2216                 if (wret < 0)
2217                         ret = wret;
2218
2219                 wret = walk_up_tree(trans, root, path, &level);
2220                 if (wret > 0)
2221                         break;
2222                 if (wret < 0)
2223                         ret = wret;
2224                 ret = -EAGAIN;
2225                 break;
2226         }
2227         for (i = 0; i <= orig_level; i++) {
2228                 if (path->nodes[i]) {
2229                         free_extent_buffer(path->nodes[i]);
2230                         path->nodes[i] = NULL;
2231                 }
2232         }
2233 out:
2234         btrfs_free_path(path);
2235         return ret;
2236 }
2237
2238 int btrfs_free_block_groups(struct btrfs_fs_info *info)
2239 {
2240         u64 start;
2241         u64 end;
2242         u64 ptr;
2243         int ret;
2244         while(1) {
2245                 ret = find_first_extent_bit(&info->block_group_cache, 0,
2246                                             &start, &end, (unsigned int)-1);
2247                 if (ret)
2248                         break;
2249                 ret = get_state_private(&info->block_group_cache, start, &ptr);
2250                 if (!ret)
2251                         kfree((void *)(unsigned long)ptr);
2252                 clear_extent_bits(&info->block_group_cache, start,
2253                                   end, (unsigned int)-1, GFP_NOFS);
2254         }
2255         while(1) {
2256                 ret = find_first_extent_bit(&info->free_space_cache, 0,
2257                                             &start, &end, EXTENT_DIRTY);
2258                 if (ret)
2259                         break;
2260                 clear_extent_dirty(&info->free_space_cache, start,
2261                                    end, GFP_NOFS);
2262         }
2263         return 0;
2264 }
2265
2266 static int noinline relocate_inode_pages(struct inode *inode, u64 start,
2267                                          u64 len)
2268 {
2269         u64 page_start;
2270         u64 page_end;
2271         u64 delalloc_start;
2272         u64 existing_delalloc;
2273         unsigned long last_index;
2274         unsigned long i;
2275         struct page *page;
2276         struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
2277         struct file_ra_state *ra;
2278
2279         ra = kzalloc(sizeof(*ra), GFP_NOFS);
2280
2281         mutex_lock(&inode->i_mutex);
2282         i = start >> PAGE_CACHE_SHIFT;
2283         last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
2284
2285         file_ra_state_init(ra, inode->i_mapping);
2286         btrfs_force_ra(inode->i_mapping, ra, NULL, i, last_index);
2287         kfree(ra);
2288
2289         for (; i <= last_index; i++) {
2290                 page = grab_cache_page(inode->i_mapping, i);
2291                 if (!page)
2292                         goto out_unlock;
2293                 if (!PageUptodate(page)) {
2294                         btrfs_readpage(NULL, page);
2295                         lock_page(page);
2296                         if (!PageUptodate(page)) {
2297                                 unlock_page(page);
2298                                 page_cache_release(page);
2299                                 goto out_unlock;
2300                         }
2301                 }
2302                 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
2303                 page_end = page_start + PAGE_CACHE_SIZE - 1;
2304
2305                 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
2306
2307                 delalloc_start = page_start;
2308                 existing_delalloc = count_range_bits(io_tree,
2309                                              &delalloc_start, page_end,
2310                                              PAGE_CACHE_SIZE, EXTENT_DELALLOC);
2311
2312                 set_extent_delalloc(io_tree, page_start,
2313                                     page_end, GFP_NOFS);
2314
2315                 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
2316                 set_page_dirty(page);
2317                 unlock_page(page);
2318                 page_cache_release(page);
2319         }
2320
2321 out_unlock:
2322         mutex_unlock(&inode->i_mutex);
2323         return 0;
2324 }
2325
2326 /*
2327  * note, this releases the path
2328  */
2329 static int noinline relocate_one_reference(struct btrfs_root *extent_root,
2330                                   struct btrfs_path *path,
2331                                   struct btrfs_key *extent_key)
2332 {
2333         struct inode *inode;
2334         struct btrfs_root *found_root;
2335         struct btrfs_key *root_location;
2336         struct btrfs_extent_ref *ref;
2337         u64 ref_root;
2338         u64 ref_gen;
2339         u64 ref_objectid;
2340         u64 ref_offset;
2341         int ret;
2342
2343         ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
2344                              struct btrfs_extent_ref);
2345         ref_root = btrfs_ref_root(path->nodes[0], ref);
2346         ref_gen = btrfs_ref_generation(path->nodes[0], ref);
2347         ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
2348         ref_offset = btrfs_ref_offset(path->nodes[0], ref);
2349         btrfs_release_path(extent_root, path);
2350
2351         root_location = kmalloc(sizeof(*root_location), GFP_NOFS);
2352         root_location->objectid = ref_root;
2353         if (ref_gen == 0)
2354                 root_location->offset = 0;
2355         else
2356                 root_location->offset = (u64)-1;
2357         root_location->type = BTRFS_ROOT_ITEM_KEY;
2358
2359         found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
2360                                                 root_location);
2361         BUG_ON(!found_root);
2362         kfree(root_location);
2363
2364         if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
2365                 mutex_unlock(&extent_root->fs_info->fs_mutex);
2366                 inode = btrfs_iget_locked(extent_root->fs_info->sb,
2367                                           ref_objectid, found_root);
2368                 if (inode->i_state & I_NEW) {
2369                         /* the inode and parent dir are two different roots */
2370                         BTRFS_I(inode)->root = found_root;
2371                         BTRFS_I(inode)->location.objectid = ref_objectid;
2372                         BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
2373                         BTRFS_I(inode)->location.offset = 0;
2374                         btrfs_read_locked_inode(inode);
2375                         unlock_new_inode(inode);
2376
2377                 }
2378                 /* this can happen if the reference is not against
2379                  * the latest version of the tree root
2380                  */
2381                 if (is_bad_inode(inode)) {
2382                         mutex_lock(&extent_root->fs_info->fs_mutex);
2383                         goto out;
2384                 }
2385                 relocate_inode_pages(inode, ref_offset, extent_key->offset);
2386                 /* FIXME, data=ordered will help get rid of this */
2387                 filemap_fdatawrite(inode->i_mapping);
2388                 iput(inode);
2389                 mutex_lock(&extent_root->fs_info->fs_mutex);
2390         } else {
2391                 struct btrfs_trans_handle *trans;
2392                 struct btrfs_key found_key;
2393                 struct extent_buffer *eb;
2394                 int level;
2395                 int i;
2396
2397                 trans = btrfs_start_transaction(found_root, 1);
2398                 eb = read_tree_block(found_root, extent_key->objectid,
2399                                      extent_key->offset);
2400                 level = btrfs_header_level(eb);
2401
2402                 if (level == 0)
2403                         btrfs_item_key_to_cpu(eb, &found_key, 0);
2404                 else
2405                         btrfs_node_key_to_cpu(eb, &found_key, 0);
2406
2407                 free_extent_buffer(eb);
2408
2409                 path->lowest_level = level;
2410                 path->reada = 2;
2411                 ret = btrfs_search_slot(trans, found_root, &found_key, path,
2412                                         0, 1);
2413                 path->lowest_level = 0;
2414                 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2415                         if (!path->nodes[i])
2416                                 break;
2417                         free_extent_buffer(path->nodes[i]);
2418                         path->nodes[i] = NULL;
2419                 }
2420                 btrfs_release_path(found_root, path);
2421                 btrfs_end_transaction(trans, found_root);
2422         }
2423
2424 out:
2425         return 0;
2426 }
2427
2428 static int noinline relocate_one_extent(struct btrfs_root *extent_root,
2429                                         struct btrfs_path *path,
2430                                         struct btrfs_key *extent_key)
2431 {
2432         struct btrfs_key key;
2433         struct btrfs_key found_key;
2434         struct extent_buffer *leaf;
2435         u32 nritems;
2436         u32 item_size;
2437         int ret = 0;
2438
2439         key.objectid = extent_key->objectid;
2440         key.type = BTRFS_EXTENT_REF_KEY;
2441         key.offset = 0;
2442
2443         while(1) {
2444                 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2445
2446                 if (ret < 0)
2447                         goto out;
2448
2449                 ret = 0;
2450                 leaf = path->nodes[0];
2451                 nritems = btrfs_header_nritems(leaf);
2452                 if (path->slots[0] == nritems)
2453                         goto out;
2454
2455                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2456                 if (found_key.objectid != extent_key->objectid)
2457                         break;
2458
2459                 if (found_key.type != BTRFS_EXTENT_REF_KEY)
2460                         break;
2461
2462                 key.offset = found_key.offset + 1;
2463                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2464
2465                 ret = relocate_one_reference(extent_root, path, extent_key);
2466                 if (ret)
2467                         goto out;
2468         }
2469         ret = 0;
2470 out:
2471         btrfs_release_path(extent_root, path);
2472         return ret;
2473 }
2474
2475 int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 shrink_start)
2476 {
2477         struct btrfs_trans_handle *trans;
2478         struct btrfs_root *tree_root = root->fs_info->tree_root;
2479         struct btrfs_path *path;
2480         u64 cur_byte;
2481         u64 total_found;
2482         u64 shrink_last_byte;
2483         struct btrfs_block_group_cache *shrink_block_group;
2484         struct btrfs_fs_info *info = root->fs_info;
2485         struct btrfs_key key;
2486         struct btrfs_key found_key;
2487         struct extent_buffer *leaf;
2488         u32 nritems;
2489         int ret;
2490         int progress = 0;
2491
2492         shrink_block_group = btrfs_lookup_block_group(root->fs_info,
2493                                                       shrink_start);
2494         BUG_ON(!shrink_block_group);
2495
2496         shrink_last_byte = shrink_start + shrink_block_group->key.offset;
2497
2498         shrink_block_group->space_info->total_bytes -=
2499                 shrink_block_group->key.offset;
2500 printk("shrink_extent_tree %Lu -> %Lu type %Lu\n", shrink_start, shrink_last_byte, shrink_block_group->flags);
2501         path = btrfs_alloc_path();
2502         root = root->fs_info->extent_root;
2503         path->reada = 2;
2504
2505 again:
2506         trans = btrfs_start_transaction(root, 1);
2507         do_chunk_alloc(trans, root->fs_info->extent_root,
2508                         btrfs_block_group_used(&shrink_block_group->item) +
2509                         2 * 1024 * 1024, shrink_block_group->flags);
2510         btrfs_end_transaction(trans, root);
2511         shrink_block_group->ro = 1;
2512
2513         total_found = 0;
2514         key.objectid = shrink_start;
2515         key.offset = 0;
2516         key.type = 0;
2517         cur_byte = key.objectid;
2518
2519         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2520         if (ret < 0)
2521                 goto out;
2522
2523         ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
2524         if (ret < 0)
2525                 goto out;
2526
2527         if (ret == 0) {
2528                 leaf = path->nodes[0];
2529                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2530                 if (found_key.objectid + found_key.offset > shrink_start &&
2531                     found_key.objectid < shrink_last_byte) {
2532                         cur_byte = found_key.objectid;
2533                         key.objectid = cur_byte;
2534                 }
2535         }
2536         btrfs_release_path(root, path);
2537
2538         while(1) {
2539                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2540                 if (ret < 0)
2541                         goto out;
2542
2543                 leaf = path->nodes[0];
2544                 nritems = btrfs_header_nritems(leaf);
2545 next:
2546                 if (path->slots[0] >= nritems) {
2547                         ret = btrfs_next_leaf(root, path);
2548                         if (ret < 0)
2549                                 goto out;
2550                         if (ret == 1) {
2551                                 ret = 0;
2552                                 break;
2553                         }
2554                         leaf = path->nodes[0];
2555                         nritems = btrfs_header_nritems(leaf);
2556                 }
2557
2558                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2559
2560                 if (found_key.objectid >= shrink_last_byte)
2561                         break;
2562
2563                 if (progress && need_resched()) {
2564                         memcpy(&key, &found_key, sizeof(key));
2565                         mutex_unlock(&root->fs_info->fs_mutex);
2566                         cond_resched();
2567                         mutex_lock(&root->fs_info->fs_mutex);
2568                         btrfs_release_path(root, path);
2569                         btrfs_search_slot(NULL, root, &key, path, 0, 0);
2570                         progress = 0;
2571                         goto next;
2572                 }
2573                 progress = 1;
2574
2575                 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
2576                     found_key.objectid + found_key.offset <= cur_byte) {
2577                         path->slots[0]++;
2578                         goto next;
2579                 }
2580
2581                 total_found++;
2582                 cur_byte = found_key.objectid + found_key.offset;
2583                 key.objectid = cur_byte;
2584                 btrfs_release_path(root, path);
2585                 ret = relocate_one_extent(root, path, &found_key);
2586         }
2587
2588         btrfs_release_path(root, path);
2589
2590         if (total_found > 0) {
2591                 trans = btrfs_start_transaction(tree_root, 1);
2592                 btrfs_commit_transaction(trans, tree_root);
2593
2594                 mutex_unlock(&root->fs_info->fs_mutex);
2595                 btrfs_clean_old_snapshots(tree_root);
2596                 mutex_lock(&root->fs_info->fs_mutex);
2597
2598                 trans = btrfs_start_transaction(tree_root, 1);
2599                 btrfs_commit_transaction(trans, tree_root);
2600                 goto again;
2601         }
2602
2603         /*
2604          * we've freed all the extents, now remove the block
2605          * group item from the tree
2606          */
2607         trans = btrfs_start_transaction(root, 1);
2608         memcpy(&key, &shrink_block_group->key, sizeof(key));
2609
2610         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
2611         if (ret > 0)
2612                 ret = -EIO;
2613         if (ret < 0)
2614                 goto out;
2615
2616         leaf = path->nodes[0];
2617         nritems = btrfs_header_nritems(leaf);
2618         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2619         kfree(shrink_block_group);
2620
2621         clear_extent_bits(&info->block_group_cache, found_key.objectid,
2622                           found_key.objectid + found_key.offset - 1,
2623                           (unsigned int)-1, GFP_NOFS);
2624
2625         btrfs_del_item(trans, root, path);
2626         clear_extent_dirty(&info->free_space_cache,
2627                            shrink_start, shrink_last_byte - 1,
2628                            GFP_NOFS);
2629         btrfs_commit_transaction(trans, root);
2630 out:
2631         btrfs_free_path(path);
2632         return ret;
2633 }
2634
2635 int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
2636                            struct btrfs_key *key)
2637 {
2638         int ret;
2639         struct btrfs_key found_key;
2640         struct extent_buffer *leaf;
2641         int slot;
2642
2643         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
2644         if (ret < 0)
2645                 return ret;
2646         while(1) {
2647                 slot = path->slots[0];
2648                 leaf = path->nodes[0];
2649                 if (slot >= btrfs_header_nritems(leaf)) {
2650                         ret = btrfs_next_leaf(root, path);
2651                         if (ret == 0)
2652                                 continue;
2653                         if (ret < 0)
2654                                 goto error;
2655                         break;
2656                 }
2657                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
2658
2659                 if (found_key.objectid >= key->objectid &&
2660                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
2661                         return 0;
2662                 path->slots[0]++;
2663         }
2664         ret = -ENOENT;
2665 error:
2666         return ret;
2667 }
2668
2669 int btrfs_read_block_groups(struct btrfs_root *root)
2670 {
2671         struct btrfs_path *path;
2672         int ret;
2673         int bit;
2674         struct btrfs_block_group_cache *cache;
2675         struct btrfs_fs_info *info = root->fs_info;
2676         struct btrfs_space_info *space_info;
2677         struct extent_io_tree *block_group_cache;
2678         struct btrfs_key key;
2679         struct btrfs_key found_key;
2680         struct extent_buffer *leaf;
2681
2682         block_group_cache = &info->block_group_cache;
2683         root = info->extent_root;
2684         key.objectid = 0;
2685         key.offset = 0;
2686         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2687         path = btrfs_alloc_path();
2688         if (!path)
2689                 return -ENOMEM;
2690
2691         while(1) {
2692                 ret = find_first_block_group(root, path, &key);
2693                 if (ret > 0) {
2694                         ret = 0;
2695                         goto error;
2696                 }
2697                 if (ret != 0)
2698                         goto error;
2699
2700                 leaf = path->nodes[0];
2701                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2702                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
2703                 if (!cache) {
2704                         ret = -ENOMEM;
2705                         break;
2706                 }
2707
2708                 read_extent_buffer(leaf, &cache->item,
2709                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
2710                                    sizeof(cache->item));
2711                 memcpy(&cache->key, &found_key, sizeof(found_key));
2712
2713                 key.objectid = found_key.objectid + found_key.offset;
2714                 btrfs_release_path(root, path);
2715                 cache->flags = btrfs_block_group_flags(&cache->item);
2716                 bit = 0;
2717                 if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
2718                         bit = BLOCK_GROUP_DATA;
2719                 } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
2720                         bit = BLOCK_GROUP_SYSTEM;
2721                 } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
2722                         bit = BLOCK_GROUP_METADATA;
2723                 }
2724                 set_avail_alloc_bits(info, cache->flags);
2725
2726                 ret = update_space_info(info, cache->flags, found_key.offset,
2727                                         btrfs_block_group_used(&cache->item),
2728                                         &space_info);
2729                 BUG_ON(ret);
2730                 cache->space_info = space_info;
2731
2732                 /* use EXTENT_LOCKED to prevent merging */
2733                 set_extent_bits(block_group_cache, found_key.objectid,
2734                                 found_key.objectid + found_key.offset - 1,
2735                                 bit | EXTENT_LOCKED, GFP_NOFS);
2736                 set_state_private(block_group_cache, found_key.objectid,
2737                                   (unsigned long)cache);
2738
2739                 if (key.objectid >=
2740                     btrfs_super_total_bytes(&info->super_copy))
2741                         break;
2742         }
2743         ret = 0;
2744 error:
2745         btrfs_free_path(path);
2746         return ret;
2747 }
2748
2749 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
2750                            struct btrfs_root *root, u64 bytes_used,
2751                            u64 type, u64 chunk_objectid, u64 chunk_offset,
2752                            u64 size)
2753 {
2754         int ret;
2755         int bit = 0;
2756         struct btrfs_root *extent_root;
2757         struct btrfs_block_group_cache *cache;
2758         struct extent_io_tree *block_group_cache;
2759
2760         extent_root = root->fs_info->extent_root;
2761         block_group_cache = &root->fs_info->block_group_cache;
2762
2763         cache = kzalloc(sizeof(*cache), GFP_NOFS);
2764         BUG_ON(!cache);
2765         cache->key.objectid = chunk_offset;
2766         cache->key.offset = size;
2767
2768         btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2769         memset(&cache->item, 0, sizeof(cache->item));
2770         btrfs_set_block_group_used(&cache->item, bytes_used);
2771         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
2772         cache->flags = type;
2773         btrfs_set_block_group_flags(&cache->item, type);
2774
2775         ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
2776                                 &cache->space_info);
2777         BUG_ON(ret);
2778
2779         bit = block_group_state_bits(type);
2780         set_extent_bits(block_group_cache, chunk_offset,
2781                         chunk_offset + size - 1,
2782                         bit | EXTENT_LOCKED, GFP_NOFS);
2783
2784         set_state_private(block_group_cache, chunk_offset,
2785                           (unsigned long)cache);
2786         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
2787                                 sizeof(cache->item));
2788         BUG_ON(ret);
2789
2790         finish_current_insert(trans, extent_root);
2791         ret = del_pending_extents(trans, extent_root);
2792         BUG_ON(ret);
2793         set_avail_alloc_bits(extent_root->fs_info, type);
2794         return 0;
2795 }