SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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 <linux/writeback.h>
  21 #include <linux/blkdev.h>
  22 #include "hash.h"
  23 #include "crc32c.h"
  24 #include "ctree.h"
  25 #include "disk-io.h"
  26 #include "print-tree.h"
  27 #include "transaction.h"
  28 #include "volumes.h"
  29 #include "locking.h"
  30 #include "ref-cache.h"
  31
  32 #define PENDING_EXTENT_INSERT 0
  33 #define PENDING_EXTENT_DELETE 1
  34 #define PENDING_BACKREF_UPDATE 2
  35
  36 struct pending_extent_op {
  37         int type;
  38         u64 bytenr;
  39         u64 num_bytes;
  40         u64 parent;
  41         u64 orig_parent;
  42         u64 generation;
  43         u64 orig_generation;
  44         int level;
  45 };
  46
  47 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  48                                  btrfs_root *extent_root);
  49 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  50                                btrfs_root *extent_root);
  51 static struct btrfs_block_group_cache *
  52 __btrfs_find_block_group(struct btrfs_root *root,
  53                          struct btrfs_block_group_cache *hint,
  54                          u64 search_start, int data, int owner);
  55
  56 void maybe_lock_mutex(struct btrfs_root *root)
  57 {
  58         if (root != root->fs_info->extent_root &&
  59             root != root->fs_info->chunk_root &&
  60             root != root->fs_info->dev_root) {
  61                 mutex_lock(&root->fs_info->alloc_mutex);
  62         }
  63 }
  64
  65 void maybe_unlock_mutex(struct btrfs_root *root)
  66 {
  67         if (root != root->fs_info->extent_root &&
  68             root != root->fs_info->chunk_root &&
  69             root != root->fs_info->dev_root) {
  70                 mutex_unlock(&root->fs_info->alloc_mutex);
  71         }
  72 }
  73
  74 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
  75 {
  76         return (cache->flags & bits) == bits;
  77 }
  78
  79 /*
  80  * this adds the block group to the fs_info rb tree for the block group
  81  * cache
  82  */
  83 int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
  84                                 struct btrfs_block_group_cache *block_group)
  85 {
  86         struct rb_node **p;
  87         struct rb_node *parent = NULL;
  88         struct btrfs_block_group_cache *cache;
  89
  90         spin_lock(&info->block_group_cache_lock);
  91         p = &info->block_group_cache_tree.rb_node;
  92
  93         while (*p) {
  94                 parent = *p;
  95                 cache = rb_entry(parent, struct btrfs_block_group_cache,
  96                                  cache_node);
  97                 if (block_group->key.objectid < cache->key.objectid) {
  98                         p = &(*p)->rb_left;
  99                 } else if (block_group->key.objectid > cache->key.objectid) {
 100                         p = &(*p)->rb_right;
 101                 } else {
 102                         spin_unlock(&info->block_group_cache_lock);
 103                         return -EEXIST;
 104                 }
 105         }
 106
 107         rb_link_node(&block_group->cache_node, parent, p);
 108         rb_insert_color(&block_group->cache_node,
 109                         &info->block_group_cache_tree);
 110         spin_unlock(&info->block_group_cache_lock);
 111
 112         return 0;
 113 }
 114
 115 /*
 116  * This will return the block group at or after bytenr if contains is 0, else
 117  * it will return the block group that contains the bytenr
 118  */
 119 static struct btrfs_block_group_cache *
 120 block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
 121                               int contains)
 122 {
 123         struct btrfs_block_group_cache *cache, *ret = NULL;
 124         struct rb_node *n;
 125         u64 end, start;
 126
 127         spin_lock(&info->block_group_cache_lock);
 128         n = info->block_group_cache_tree.rb_node;
 129
 130         while (n) {
 131                 cache = rb_entry(n, struct btrfs_block_group_cache,
 132                                  cache_node);
 133                 end = cache->key.objectid + cache->key.offset - 1;
 134                 start = cache->key.objectid;
 135
 136                 if (bytenr < start) {
 137                         if (!contains && (!ret || start < ret->key.objectid))
 138                                 ret = cache;
 139                         n = n->rb_left;
 140                 } else if (bytenr > start) {
 141                         if (contains && bytenr <= end) {
 142                                 ret = cache;
 143                                 break;
 144                         }
 145                         n = n->rb_right;
 146                 } else {
 147                         ret = cache;
 148                         break;
 149                 }
 150         }
 151         spin_unlock(&info->block_group_cache_lock);
 152
 153         return ret;
 154 }
 155
 156 /*
 157  * this is only called by cache_block_group, since we could have freed extents
 158  * we need to check the pinned_extents for any extents that can't be used yet
 159  * since their free space will be released as soon as the transaction commits.
 160  */
 161 static int add_new_free_space(struct btrfs_block_group_cache *block_group,
 162                               struct btrfs_fs_info *info, u64 start, u64 end)
 163 {
 164         u64 extent_start, extent_end, size;
 165         int ret;
 166
 167         while (start < end) {
 168                 ret = find_first_extent_bit(&info->pinned_extents, start,
 169                                             &extent_start, &extent_end,
 170                                             EXTENT_DIRTY);
 171                 if (ret)
 172                         break;
 173
 174                 if (extent_start == start) {
 175                         start = extent_end + 1;
 176                 } else if (extent_start > start && extent_start < end) {
 177                         size = extent_start - start;
 178                         ret = btrfs_add_free_space(block_group, start, size);
 179                         BUG_ON(ret);
 180                         start = extent_end + 1;
 181                 } else {
 182                         break;
 183                 }
 184         }
 185
 186         if (start < end) {
 187                 size = end - start;
 188                 ret = btrfs_add_free_space(block_group, start, size);
 189                 BUG_ON(ret);
 190         }
 191
 192         return 0;
 193 }
 194
 195 static int cache_block_group(struct btrfs_root *root,
 196                              struct btrfs_block_group_cache *block_group)
 197 {
 198         struct btrfs_path *path;
 199         int ret = 0;
 200         struct btrfs_key key;
 201         struct extent_buffer *leaf;
 202         int slot;
 203         u64 last = 0;
 204         u64 first_free;
 205         int found = 0;
 206
 207         if (!block_group)
 208                 return 0;
 209
 210         root = root->fs_info->extent_root;
 211
 212         if (block_group->cached)
 213                 return 0;
 214
 215         path = btrfs_alloc_path();
 216         if (!path)
 217                 return -ENOMEM;
 218
 219         path->reada = 2;
 220         /*
 221          * we get into deadlocks with paths held by callers of this function.
 222          * since the alloc_mutex is protecting things right now, just
 223          * skip the locking here
 224          */
 225         path->skip_locking = 1;
 226         first_free = max_t(u64, block_group->key.objectid,
 227                            BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
 228         key.objectid = block_group->key.objectid;
 229         key.offset = 0;
 230         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 231         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 232         if (ret < 0)
 233                 goto err;
 234         ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
 235         if (ret < 0)
 236                 goto err;
 237         if (ret == 0) {
 238                 leaf = path->nodes[0];
 239                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 240                 if (key.objectid + key.offset > first_free)
 241                         first_free = key.objectid + key.offset;
 242         }
 243         while(1) {
 244                 leaf = path->nodes[0];
 245                 slot = path->slots[0];
 246                 if (slot >= btrfs_header_nritems(leaf)) {
 247                         ret = btrfs_next_leaf(root, path);
 248                         if (ret < 0)
 249                                 goto err;
 250                         if (ret == 0)
 251                                 continue;
 252                         else
 253                                 break;
 254                 }
 255                 btrfs_item_key_to_cpu(leaf, &key, slot);
 256                 if (key.objectid < block_group->key.objectid)
 257                         goto next;
 258
 259                 if (key.objectid >= block_group->key.objectid +
 260                     block_group->key.offset)
 261                         break;
 262
 263                 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
 264                         if (!found) {
 265                                 last = first_free;
 266                                 found = 1;
 267                         }
 268
 269                         add_new_free_space(block_group, root->fs_info, last,
 270                                            key.objectid);
 271
 272                         last = key.objectid + key.offset;
 273                 }
 274 next:
 275                 path->slots[0]++;
 276         }
 277
 278         if (!found)
 279                 last = first_free;
 280
 281         add_new_free_space(block_group, root->fs_info, last,
 282                            block_group->key.objectid +
 283                            block_group->key.offset);
 284
 285         block_group->cached = 1;
 286         ret = 0;
 287 err:
 288         btrfs_free_path(path);
 289         return ret;
 290 }
 291
 292 /*
 293  * return the block group that starts at or after bytenr
 294  */
 295 struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
 296                                                        btrfs_fs_info *info,
 297                                                          u64 bytenr)
 298 {
 299         struct btrfs_block_group_cache *cache;
 300
 301         cache = block_group_cache_tree_search(info, bytenr, 0);
 302
 303         return cache;
 304 }
 305
 306 /*
 307  * return the block group that contains teh given bytenr
 308  */
 309 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 310                                                          btrfs_fs_info *info,
 311                                                          u64 bytenr)
 312 {
 313         struct btrfs_block_group_cache *cache;
 314
 315         cache = block_group_cache_tree_search(info, bytenr, 1);
 316
 317         return cache;
 318 }
 319
 320 static int noinline find_free_space(struct btrfs_root *root,
 321                                     struct btrfs_block_group_cache **cache_ret,
 322                                     u64 *start_ret, u64 num, int data)
 323 {
 324         int ret;
 325         struct btrfs_block_group_cache *cache = *cache_ret;
 326         struct btrfs_free_space *info = NULL;
 327         u64 last;
 328         u64 search_start = *start_ret;
 329
 330         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
 331         if (!cache)
 332                 goto out;
 333
 334         last = max(search_start, cache->key.objectid);
 335
 336 again:
 337         ret = cache_block_group(root, cache);
 338         if (ret)
 339                 goto out;
 340
 341         if (cache->ro || !block_group_bits(cache, data))
 342                 goto new_group;
 343
 344         info = btrfs_find_free_space(cache, last, num);
 345         if (info) {
 346                 *start_ret = info->offset;
 347                 return 0;
 348         }
 349
 350 new_group:
 351         last = cache->key.objectid + cache->key.offset;
 352
 353         cache = btrfs_lookup_first_block_group(root->fs_info, last);
 354         if (!cache)
 355                 goto out;
 356
 357         *cache_ret = cache;
 358         goto again;
 359
 360 out:
 361         return -ENOSPC;
 362 }
 363
 364 static u64 div_factor(u64 num, int factor)
 365 {
 366         if (factor == 10)
 367                 return num;
 368         num *= factor;
 369         do_div(num, 10);
 370         return num;
 371 }
 372
 373 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
 374                                                   u64 flags)
 375 {
 376         struct list_head *head = &info->space_info;
 377         struct list_head *cur;
 378         struct btrfs_space_info *found;
 379         list_for_each(cur, head) {
 380                 found = list_entry(cur, struct btrfs_space_info, list);
 381                 if (found->flags == flags)
 382                         return found;
 383         }
 384         return NULL;
 385 }
 386
 387 static struct btrfs_block_group_cache *
 388 __btrfs_find_block_group(struct btrfs_root *root,
 389                          struct btrfs_block_group_cache *hint,
 390                          u64 search_start, int data, int owner)
 391 {
 392         struct btrfs_block_group_cache *cache;
 393         struct btrfs_block_group_cache *found_group = NULL;
 394         struct btrfs_fs_info *info = root->fs_info;
 395         u64 used;
 396         u64 last = 0;
 397         u64 free_check;
 398         int full_search = 0;
 399         int factor = 10;
 400         int wrapped = 0;
 401
 402         if (data & BTRFS_BLOCK_GROUP_METADATA)
 403                 factor = 9;
 404
 405         if (search_start) {
 406                 struct btrfs_block_group_cache *shint;
 407                 shint = btrfs_lookup_first_block_group(info, search_start);
 408                 if (shint && block_group_bits(shint, data) && !shint->ro) {
 409                         spin_lock(&shint->lock);
 410                         used = btrfs_block_group_used(&shint->item);
 411                         if (used + shint->pinned + shint->reserved <
 412                             div_factor(shint->key.offset, factor)) {
 413                                 spin_unlock(&shint->lock);
 414                                 return shint;
 415                         }
 416                         spin_unlock(&shint->lock);
 417                 }
 418         }
 419         if (hint && !hint->ro && block_group_bits(hint, data)) {
 420                 spin_lock(&hint->lock);
 421                 used = btrfs_block_group_used(&hint->item);
 422                 if (used + hint->pinned + hint->reserved <
 423                     div_factor(hint->key.offset, factor)) {
 424                         spin_unlock(&hint->lock);
 425                         return hint;
 426                 }
 427                 spin_unlock(&hint->lock);
 428                 last = hint->key.objectid + hint->key.offset;
 429         } else {
 430                 if (hint)
 431                         last = max(hint->key.objectid, search_start);
 432                 else
 433                         last = search_start;
 434         }
 435 again:
 436         while (1) {
 437                 cache = btrfs_lookup_first_block_group(root->fs_info, last);
 438                 if (!cache)
 439                         break;
 440
 441                 spin_lock(&cache->lock);
 442                 last = cache->key.objectid + cache->key.offset;
 443                 used = btrfs_block_group_used(&cache->item);
 444
 445                 if (!cache->ro && block_group_bits(cache, data)) {
 446                         free_check = div_factor(cache->key.offset, factor);
 447                         if (used + cache->pinned + cache->reserved <
 448                             free_check) {
 449                                 found_group = cache;
 450                                 spin_unlock(&cache->lock);
 451                                 goto found;
 452                         }
 453                 }
 454                 spin_unlock(&cache->lock);
 455                 cond_resched();
 456         }
 457         if (!wrapped) {
 458                 last = search_start;
 459                 wrapped = 1;
 460                 goto again;
 461         }
 462         if (!full_search && factor < 10) {
 463                 last = search_start;
 464                 full_search = 1;
 465                 factor = 10;
 466                 goto again;
 467         }
 468 found:
 469         return found_group;
 470 }
 471
 472 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 473                                                  struct btrfs_block_group_cache
 474                                                  *hint, u64 search_start,
 475                                                  int data, int owner)
 476 {
 477
 478         struct btrfs_block_group_cache *ret;
 479         ret = __btrfs_find_block_group(root, hint, search_start, data, owner);
 480         return ret;
 481 }
 482
 483 /* simple helper to search for an existing extent at a given offset */
 484 int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
 485 {
 486         int ret;
 487         struct btrfs_key key;
 488         struct btrfs_path *path;
 489
 490         path = btrfs_alloc_path();
 491         BUG_ON(!path);
 492         maybe_lock_mutex(root);
 493         key.objectid = start;
 494         key.offset = len;
 495         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 496         ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
 497                                 0, 0);
 498         maybe_unlock_mutex(root);
 499         btrfs_free_path(path);
 500         return ret;
 501 }
 502
 503 /*
 504  * Back reference rules.  Back refs have three main goals:
 505  *
 506  * 1) differentiate between all holders of references to an extent so that
 507  *    when a reference is dropped we can make sure it was a valid reference
 508  *    before freeing the extent.
 509  *
 510  * 2) Provide enough information to quickly find the holders of an extent
 511  *    if we notice a given block is corrupted or bad.
 512  *
 513  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 514  *    maintenance.  This is actually the same as #2, but with a slightly
 515  *    different use case.
 516  *
 517  * File extents can be referenced by:
 518  *
 519  * - multiple snapshots, subvolumes, or different generations in one subvol
 520  * - different files inside a single subvolume
 521  * - different offsets inside a file (bookend extents in file.c)
 522  *
 523  * The extent ref structure has fields for:
 524  *
 525  * - Objectid of the subvolume root
 526  * - Generation number of the tree holding the reference
 527  * - objectid of the file holding the reference
 528  * - number of references holding by parent node (alway 1 for tree blocks)
 529  *
 530  * Btree leaf may hold multiple references to a file extent. In most cases,
 531  * these references are from same file and the corresponding offsets inside
 532  * the file are close together.
 533  *
 534  * When a file extent is allocated the fields are filled in:
 535  *     (root_key.objectid, trans->transid, inode objectid, 1)
 536  *
 537  * When a leaf is cow'd new references are added for every file extent found
 538  * in the leaf.  It looks similar to the create case, but trans->transid will
 539  * be different when the block is cow'd.
 540  *
 541  *     (root_key.objectid, trans->transid, inode objectid,
 542  *      number of references in the leaf)
 543  *
 544  * When a file extent is removed either during snapshot deletion or
 545  * file truncation, we find the corresponding back reference and check
 546  * the following fields:
 547  *
 548  *     (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
 549  *      inode objectid)
 550  *
 551  * Btree extents can be referenced by:
 552  *
 553  * - Different subvolumes
 554  * - Different generations of the same subvolume
 555  *
 556  * When a tree block is created, back references are inserted:
 557  *
 558  * (root->root_key.objectid, trans->transid, level, 1)
 559  *
 560  * When a tree block is cow'd, new back references are added for all the
 561  * blocks it points to. If the tree block isn't in reference counted root,
 562  * the old back references are removed. These new back references are of
 563  * the form (trans->transid will have increased since creation):
 564  *
 565  * (root->root_key.objectid, trans->transid, level, 1)
 566  *
 567  * When a backref is in deleting, the following fields are checked:
 568  *
 569  * if backref was for a tree root:
 570  *     (btrfs_header_owner(itself), btrfs_header_generation(itself), level)
 571  * else
 572  *     (btrfs_header_owner(parent), btrfs_header_generation(parent), level)
 573  *
 574  * Back Reference Key composing:
 575  *
 576  * The key objectid corresponds to the first byte in the extent, the key
 577  * type is set to BTRFS_EXTENT_REF_KEY, and the key offset is the first
 578  * byte of parent extent. If a extent is tree root, the key offset is set
 579  * to the key objectid.
 580  */
 581
 582 static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
 583                                           struct btrfs_root *root,
 584                                           struct btrfs_path *path,
 585                                           u64 bytenr, u64 parent,
 586                                           u64 ref_root, u64 ref_generation,
 587                                           u64 owner_objectid, int del)
 588 {
 589         struct btrfs_key key;
 590         struct btrfs_extent_ref *ref;
 591         struct extent_buffer *leaf;
 592         u64 ref_objectid;
 593         int ret;
 594
 595         key.objectid = bytenr;
 596         key.type = BTRFS_EXTENT_REF_KEY;
 597         key.offset = parent;
 598
 599         ret = btrfs_search_slot(trans, root, &key, path, del ? -1 : 0, 1);
 600         if (ret < 0)
 601                 goto out;
 602         if (ret > 0) {
 603                 ret = -ENOENT;
 604                 goto out;
 605         }
 606
 607         leaf = path->nodes[0];
 608         ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
 609         ref_objectid = btrfs_ref_objectid(leaf, ref);
 610         if (btrfs_ref_root(leaf, ref) != ref_root ||
 611             btrfs_ref_generation(leaf, ref) != ref_generation ||
 612             (ref_objectid != owner_objectid &&
 613              ref_objectid != BTRFS_MULTIPLE_OBJECTIDS)) {
 614                 ret = -EIO;
 615                 WARN_ON(1);
 616                 goto out;
 617         }
 618         ret = 0;
 619 out:
 620         return ret;
 621 }
 622
 623 static int noinline insert_extent_backref(struct btrfs_trans_handle *trans,
 624                                           struct btrfs_root *root,
 625                                           struct btrfs_path *path,
 626                                           u64 bytenr, u64 parent,
 627                                           u64 ref_root, u64 ref_generation,
 628                                           u64 owner_objectid)
 629 {
 630         struct btrfs_key key;
 631         struct extent_buffer *leaf;
 632         struct btrfs_extent_ref *ref;
 633         u32 num_refs;
 634         int ret;
 635
 636         key.objectid = bytenr;
 637         key.type = BTRFS_EXTENT_REF_KEY;
 638         key.offset = parent;
 639
 640         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*ref));
 641         if (ret == 0) {
 642                 leaf = path->nodes[0];
 643                 ref = btrfs_item_ptr(leaf, path->slots[0],
 644                                      struct btrfs_extent_ref);
 645                 btrfs_set_ref_root(leaf, ref, ref_root);
 646                 btrfs_set_ref_generation(leaf, ref, ref_generation);
 647                 btrfs_set_ref_objectid(leaf, ref, owner_objectid);
 648                 btrfs_set_ref_num_refs(leaf, ref, 1);
 649         } else if (ret == -EEXIST) {
 650                 u64 existing_owner;
 651                 BUG_ON(owner_objectid < BTRFS_FIRST_FREE_OBJECTID);
 652                 leaf = path->nodes[0];
 653                 ref = btrfs_item_ptr(leaf, path->slots[0],
 654                                      struct btrfs_extent_ref);
 655                 if (btrfs_ref_root(leaf, ref) != ref_root ||
 656                     btrfs_ref_generation(leaf, ref) != ref_generation) {
 657                         ret = -EIO;
 658                         WARN_ON(1);
 659                         goto out;
 660                 }
 661
 662                 num_refs = btrfs_ref_num_refs(leaf, ref);
 663                 BUG_ON(num_refs == 0);
 664                 btrfs_set_ref_num_refs(leaf, ref, num_refs + 1);
 665
 666                 existing_owner = btrfs_ref_objectid(leaf, ref);
 667                 if (existing_owner != owner_objectid &&
 668                     existing_owner != BTRFS_MULTIPLE_OBJECTIDS) {
 669                         btrfs_set_ref_objectid(leaf, ref,
 670                                         BTRFS_MULTIPLE_OBJECTIDS);
 671                 }
 672                 ret = 0;
 673         } else {
 674                 goto out;
 675         }
 676         btrfs_mark_buffer_dirty(path->nodes[0]);
 677 out:
 678         btrfs_release_path(root, path);
 679         return ret;
 680 }
 681
 682 static int noinline remove_extent_backref(struct btrfs_trans_handle *trans,
 683                                           struct btrfs_root *root,
 684                                           struct btrfs_path *path)
 685 {
 686         struct extent_buffer *leaf;
 687         struct btrfs_extent_ref *ref;
 688         u32 num_refs;
 689         int ret = 0;
 690
 691         leaf = path->nodes[0];
 692         ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
 693         num_refs = btrfs_ref_num_refs(leaf, ref);
 694         BUG_ON(num_refs == 0);
 695         num_refs -= 1;
 696         if (num_refs == 0) {
 697                 ret = btrfs_del_item(trans, root, path);
 698         } else {
 699                 btrfs_set_ref_num_refs(leaf, ref, num_refs);
 700                 btrfs_mark_buffer_dirty(leaf);
 701         }
 702         btrfs_release_path(root, path);
 703         return ret;
 704 }
 705
 706 static int __btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
 707                                      struct btrfs_root *root, u64 bytenr,
 708                                      u64 orig_parent, u64 parent,
 709                                      u64 orig_root, u64 ref_root,
 710                                      u64 orig_generation, u64 ref_generation,
 711                                      u64 owner_objectid)
 712 {
 713         int ret;
 714         struct btrfs_root *extent_root = root->fs_info->extent_root;
 715         struct btrfs_path *path;
 716
 717         if (root == root->fs_info->extent_root) {
 718                 struct pending_extent_op *extent_op;
 719                 u64 num_bytes;
 720
 721                 BUG_ON(owner_objectid >= BTRFS_MAX_LEVEL);
 722                 num_bytes = btrfs_level_size(root, (int)owner_objectid);
 723                 if (test_range_bit(&root->fs_info->extent_ins, bytenr,
 724                                 bytenr + num_bytes - 1, EXTENT_LOCKED, 0)) {
 725                         u64 priv;
 726                         ret = get_state_private(&root->fs_info->extent_ins,
 727                                                 bytenr, &priv);
 728                         BUG_ON(ret);
 729                         extent_op = (struct pending_extent_op *)
 730                                                         (unsigned long)priv;
 731                         BUG_ON(extent_op->parent != orig_parent);
 732                         BUG_ON(extent_op->generation != orig_generation);
 733                         extent_op->parent = parent;
 734                         extent_op->generation = ref_generation;
 735                 } else {
 736                         extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
 737                         BUG_ON(!extent_op);
 738
 739                         extent_op->type = PENDING_BACKREF_UPDATE;
 740                         extent_op->bytenr = bytenr;
 741                         extent_op->num_bytes = num_bytes;
 742                         extent_op->parent = parent;
 743                         extent_op->orig_parent = orig_parent;
 744                         extent_op->generation = ref_generation;
 745                         extent_op->orig_generation = orig_generation;
 746                         extent_op->level = (int)owner_objectid;
 747
 748                         set_extent_bits(&root->fs_info->extent_ins,
 749                                         bytenr, bytenr + num_bytes - 1,
 750                                         EXTENT_LOCKED, GFP_NOFS);
 751                         set_state_private(&root->fs_info->extent_ins,
 752                                           bytenr, (unsigned long)extent_op);
 753                 }
 754                 return 0;
 755         }
 756
 757         path = btrfs_alloc_path();
 758         if (!path)
 759                 return -ENOMEM;
 760         ret = lookup_extent_backref(trans, extent_root, path,
 761                                     bytenr, orig_parent, orig_root,
 762                                     orig_generation, owner_objectid, 1);
 763         if (ret)
 764                 goto out;
 765         ret = remove_extent_backref(trans, extent_root, path);
 766         if (ret)
 767                 goto out;
 768         ret = insert_extent_backref(trans, extent_root, path, bytenr,
 769                                     parent, ref_root, ref_generation,
 770                                     owner_objectid);
 771         BUG_ON(ret);
 772         finish_current_insert(trans, extent_root);
 773         del_pending_extents(trans, extent_root);
 774 out:
 775         btrfs_free_path(path);
 776         return ret;
 777 }
 778
 779 int btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
 780                             struct btrfs_root *root, u64 bytenr,
 781                             u64 orig_parent, u64 parent,
 782                             u64 ref_root, u64 ref_generation,
 783                             u64 owner_objectid)
 784 {
 785         int ret;
 786         if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
 787             owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
 788                 return 0;
 789         maybe_lock_mutex(root);
 790         ret = __btrfs_update_extent_ref(trans, root, bytenr, orig_parent,
 791                                         parent, ref_root, ref_root,
 792                                         ref_generation, ref_generation,
 793                                         owner_objectid);
 794         maybe_unlock_mutex(root);
 795         return ret;
 796 }
 797
 798 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 799                                   struct btrfs_root *root, u64 bytenr,
 800                                   u64 orig_parent, u64 parent,
 801                                   u64 orig_root, u64 ref_root,
 802                                   u64 orig_generation, u64 ref_generation,
 803                                   u64 owner_objectid)
 804 {
 805         struct btrfs_path *path;
 806         int ret;
 807         struct btrfs_key key;
 808         struct extent_buffer *l;
 809         struct btrfs_extent_item *item;
 810         u32 refs;
 811
 812         path = btrfs_alloc_path();
 813         if (!path)
 814                 return -ENOMEM;
 815
 816         path->reada = 1;
 817         key.objectid = bytenr;
 818         key.type = BTRFS_EXTENT_ITEM_KEY;
 819         key.offset = (u64)-1;
 820
 821         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 822                                 0, 1);
 823         if (ret < 0)
 824                 return ret;
 825         BUG_ON(ret == 0 || path->slots[0] == 0);
 826
 827         path->slots[0]--;
 828         l = path->nodes[0];
 829
 830         btrfs_item_key_to_cpu(l, &key, path->slots[0]);
 831         BUG_ON(key.objectid != bytenr);
 832         BUG_ON(key.type != BTRFS_EXTENT_ITEM_KEY);
 833
 834         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 835         refs = btrfs_extent_refs(l, item);
 836         btrfs_set_extent_refs(l, item, refs + 1);
 837         btrfs_mark_buffer_dirty(path->nodes[0]);
 838
 839         btrfs_release_path(root->fs_info->extent_root, path);
 840
 841         path->reada = 1;
 842         ret = insert_extent_backref(trans, root->fs_info->extent_root,
 843                                     path, bytenr, parent,
 844                                     ref_root, ref_generation,
 845                                     owner_objectid);
 846         BUG_ON(ret);
 847         finish_current_insert(trans, root->fs_info->extent_root);
 848         del_pending_extents(trans, root->fs_info->extent_root);
 849
 850         btrfs_free_path(path);
 851         return 0;
 852 }
 853
 854 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 855                          struct btrfs_root *root,
 856                          u64 bytenr, u64 num_bytes, u64 parent,
 857                          u64 ref_root, u64 ref_generation,
 858                          u64 owner_objectid)
 859 {
 860         int ret;
 861         if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
 862             owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
 863                 return 0;
 864         maybe_lock_mutex(root);
 865         ret = __btrfs_inc_extent_ref(trans, root, bytenr, 0, parent,
 866                                      0, ref_root, 0, ref_generation,
 867                                      owner_objectid);
 868         maybe_unlock_mutex(root);
 869         return ret;
 870 }
 871
 872 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
 873                          struct btrfs_root *root)
 874 {
 875         finish_current_insert(trans, root->fs_info->extent_root);
 876         del_pending_extents(trans, root->fs_info->extent_root);
 877         return 0;
 878 }
 879
 880 int btrfs_lookup_extent_ref(struct btrfs_trans_handle *trans,
 881                             struct btrfs_root *root, u64 bytenr,
 882                             u64 num_bytes, u32 *refs)
 883 {
 884         struct btrfs_path *path;
 885         int ret;
 886         struct btrfs_key key;
 887         struct extent_buffer *l;
 888         struct btrfs_extent_item *item;
 889
 890         WARN_ON(num_bytes < root->sectorsize);
 891         path = btrfs_alloc_path();
 892         path->reada = 1;
 893         key.objectid = bytenr;
 894         key.offset = num_bytes;
 895         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 896         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 897                                 0, 0);
 898         if (ret < 0)
 899                 goto out;
 900         if (ret != 0) {
 901                 btrfs_print_leaf(root, path->nodes[0]);
 902                 printk("failed to find block number %Lu\n", bytenr);
 903                 BUG();
 904         }
 905         l = path->nodes[0];
 906         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 907         *refs = btrfs_extent_refs(l, item);
 908 out:
 909         btrfs_free_path(path);
 910         return 0;
 911 }
 912
 913 static int get_reference_status(struct btrfs_root *root, u64 bytenr,
 914                                 u64 parent_gen, u64 ref_objectid,
 915                                 u64 *min_generation, u32 *ref_count)
 916 {
 917         struct btrfs_root *extent_root = root->fs_info->extent_root;
 918         struct btrfs_path *path;
 919         struct extent_buffer *leaf;
 920         struct btrfs_extent_ref *ref_item;
 921         struct btrfs_key key;
 922         struct btrfs_key found_key;
 923         u64 root_objectid = root->root_key.objectid;
 924         u64 ref_generation;
 925         u32 nritems;
 926         int ret;
 927
 928         key.objectid = bytenr;
 929         key.offset = (u64)-1;
 930         key.type = BTRFS_EXTENT_ITEM_KEY;
 931
 932         path = btrfs_alloc_path();
 933         mutex_lock(&root->fs_info->alloc_mutex);
 934         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 935         if (ret < 0)
 936                 goto out;
 937         BUG_ON(ret == 0);
 938         if (ret < 0 || path->slots[0] == 0)
 939                 goto out;
 940
 941         path->slots[0]--;
 942         leaf = path->nodes[0];
 943         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 944
 945         if (found_key.objectid != bytenr ||
 946             found_key.type != BTRFS_EXTENT_ITEM_KEY) {
 947                 ret = 1;
 948                 goto out;
 949         }
 950
 951         *ref_count = 0;
 952         *min_generation = (u64)-1;
 953
 954         while (1) {
 955                 leaf = path->nodes[0];
 956                 nritems = btrfs_header_nritems(leaf);
 957                 if (path->slots[0] >= nritems) {
 958                         ret = btrfs_next_leaf(extent_root, path);
 959                         if (ret < 0)
 960                                 goto out;
 961                         if (ret == 0)
 962                                 continue;
 963                         break;
 964                 }
 965                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 966                 if (found_key.objectid != bytenr)
 967                         break;
 968
 969                 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
 970                         path->slots[0]++;
 971                         continue;
 972                 }
 973
 974                 ref_item = btrfs_item_ptr(leaf, path->slots[0],
 975                                           struct btrfs_extent_ref);
 976                 ref_generation = btrfs_ref_generation(leaf, ref_item);
 977                 /*
 978                  * For (parent_gen > 0 && parent_gen > ref_generation):
 979                  *
 980                  * we reach here through the oldest root, therefore
 981                  * all other reference from same snapshot should have
 982                  * a larger generation.
 983                  */
 984                 if ((root_objectid != btrfs_ref_root(leaf, ref_item)) ||
 985                     (parent_gen > 0 && parent_gen > ref_generation) ||
 986                     (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
 987                      ref_objectid != btrfs_ref_objectid(leaf, ref_item))) {
 988                         *ref_count = 2;
 989                         break;
 990                 }
 991
 992                 *ref_count = 1;
 993                 if (*min_generation > ref_generation)
 994                         *min_generation = ref_generation;
 995
 996                 path->slots[0]++;
 997         }
 998         ret = 0;
 999 out:
1000         mutex_unlock(&root->fs_info->alloc_mutex);
1001         btrfs_free_path(path);
1002         return ret;
1003 }
1004
1005 int btrfs_cross_ref_exists(struct btrfs_trans_handle *trans,
1006                            struct btrfs_root *root,
1007                            struct btrfs_key *key, u64 bytenr)
1008 {
1009         struct btrfs_root *old_root;
1010         struct btrfs_path *path = NULL;
1011         struct extent_buffer *eb;
1012         struct btrfs_file_extent_item *item;
1013         u64 ref_generation;
1014         u64 min_generation;
1015         u64 extent_start;
1016         u32 ref_count;
1017         int level;
1018         int ret;
1019
1020         BUG_ON(trans == NULL);
1021         BUG_ON(key->type != BTRFS_EXTENT_DATA_KEY);
1022         ret = get_reference_status(root, bytenr, 0, key->objectid,
1023                                    &min_generation, &ref_count);
1024         if (ret)
1025                 return ret;
1026
1027         if (ref_count != 1)
1028                 return 1;
1029
1030         old_root = root->dirty_root->root;
1031         ref_generation = old_root->root_key.offset;
1032
1033         /* all references are created in running transaction */
1034         if (min_generation > ref_generation) {
1035                 ret = 0;
1036                 goto out;
1037         }
1038
1039         path = btrfs_alloc_path();
1040         if (!path) {
1041                 ret = -ENOMEM;
1042                 goto out;
1043         }
1044
1045         path->skip_locking = 1;
1046         /* if no item found, the extent is referenced by other snapshot */
1047         ret = btrfs_search_slot(NULL, old_root, key, path, 0, 0);
1048         if (ret)
1049                 goto out;
1050
1051         eb = path->nodes[0];
1052         item = btrfs_item_ptr(eb, path->slots[0],
1053                               struct btrfs_file_extent_item);
1054         if (btrfs_file_extent_type(eb, item) != BTRFS_FILE_EXTENT_REG ||
1055             btrfs_file_extent_disk_bytenr(eb, item) != bytenr) {
1056                 ret = 1;
1057                 goto out;
1058         }
1059
1060         for (level = BTRFS_MAX_LEVEL - 1; level >= -1; level--) {
1061                 if (level >= 0) {
1062                         eb = path->nodes[level];
1063                         if (!eb)
1064                                 continue;
1065                         extent_start = eb->start;
1066                 } else
1067                         extent_start = bytenr;
1068
1069                 ret = get_reference_status(root, extent_start, ref_generation,
1070                                            0, &min_generation, &ref_count);
1071                 if (ret)
1072                         goto out;
1073
1074                 if (ref_count != 1) {
1075                         ret = 1;
1076                         goto out;
1077                 }
1078                 if (level >= 0)
1079                         ref_generation = btrfs_header_generation(eb);
1080         }
1081         ret = 0;
1082 out:
1083         if (path)
1084                 btrfs_free_path(path);
1085         return ret;
1086 }
1087
1088 int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1089                     struct extent_buffer *buf, u32 nr_extents)
1090 {
1091         struct btrfs_key key;
1092         struct btrfs_file_extent_item *fi;
1093         u64 root_gen;
1094         u32 nritems;
1095         int i;
1096         int level;
1097         int ret = 0;
1098         int shared = 0;
1099
1100         if (!root->ref_cows)
1101                 return 0;
1102
1103         if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1104                 shared = 0;
1105                 root_gen = root->root_key.offset;
1106         } else {
1107                 shared = 1;
1108                 root_gen = trans->transid - 1;
1109         }
1110
1111         level = btrfs_header_level(buf);
1112         nritems = btrfs_header_nritems(buf);
1113
1114         if (level == 0) {
1115                 struct btrfs_leaf_ref *ref;
1116                 struct btrfs_extent_info *info;
1117
1118                 ref = btrfs_alloc_leaf_ref(root, nr_extents);
1119                 if (!ref) {
1120                         ret = -ENOMEM;
1121                         goto out;
1122                 }
1123
1124                 ref->root_gen = root_gen;
1125                 ref->bytenr = buf->start;
1126                 ref->owner = btrfs_header_owner(buf);
1127                 ref->generation = btrfs_header_generation(buf);
1128                 ref->nritems = nr_extents;
1129                 info = ref->extents;
1130
1131                 for (i = 0; nr_extents > 0 && i < nritems; i++) {
1132                         u64 disk_bytenr;
1133                         btrfs_item_key_to_cpu(buf, &key, i);
1134                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1135                                 continue;
1136                         fi = btrfs_item_ptr(buf, i,
1137                                             struct btrfs_file_extent_item);
1138                         if (btrfs_file_extent_type(buf, fi) ==
1139                             BTRFS_FILE_EXTENT_INLINE)
1140                                 continue;
1141                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1142                         if (disk_bytenr == 0)
1143                                 continue;
1144
1145                         info->bytenr = disk_bytenr;
1146                         info->num_bytes =
1147                                 btrfs_file_extent_disk_num_bytes(buf, fi);
1148                         info->objectid = key.objectid;
1149                         info->offset = key.offset;
1150                         info++;
1151                 }
1152
1153                 ret = btrfs_add_leaf_ref(root, ref, shared);
1154                 if (ret == -EEXIST && shared) {
1155                         struct btrfs_leaf_ref *old;
1156                         old = btrfs_lookup_leaf_ref(root, ref->bytenr);
1157                         BUG_ON(!old);
1158                         btrfs_remove_leaf_ref(root, old);
1159                         btrfs_free_leaf_ref(root, old);
1160                         ret = btrfs_add_leaf_ref(root, ref, shared);
1161                 }
1162                 WARN_ON(ret);
1163                 btrfs_free_leaf_ref(root, ref);
1164         }
1165 out:
1166         return ret;
1167 }
1168
1169 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1170                   struct extent_buffer *orig_buf, struct extent_buffer *buf,
1171                   u32 *nr_extents)
1172 {
1173         u64 bytenr;
1174         u64 ref_root;
1175         u64 orig_root;
1176         u64 ref_generation;
1177         u64 orig_generation;
1178         u32 nritems;
1179         u32 nr_file_extents = 0;
1180         struct btrfs_key key;
1181         struct btrfs_file_extent_item *fi;
1182         int i;
1183         int level;
1184         int ret = 0;
1185         int faili = 0;
1186         int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
1187                             u64, u64, u64, u64, u64, u64, u64, u64);
1188
1189         ref_root = btrfs_header_owner(buf);
1190         ref_generation = btrfs_header_generation(buf);
1191         orig_root = btrfs_header_owner(orig_buf);
1192         orig_generation = btrfs_header_generation(orig_buf);
1193
1194         nritems = btrfs_header_nritems(buf);
1195         level = btrfs_header_level(buf);
1196
1197         if (root->ref_cows) {
1198                 process_func = __btrfs_inc_extent_ref;
1199         } else {
1200                 if (level == 0 &&
1201                     root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
1202                         goto out;
1203                 if (level != 0 &&
1204                     root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
1205                         goto out;
1206                 process_func = __btrfs_update_extent_ref;
1207         }
1208
1209         for (i = 0; i < nritems; i++) {
1210                 cond_resched();
1211                 if (level == 0) {
1212                         btrfs_item_key_to_cpu(buf, &key, i);
1213                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1214                                 continue;
1215                         fi = btrfs_item_ptr(buf, i,
1216                                             struct btrfs_file_extent_item);
1217                         if (btrfs_file_extent_type(buf, fi) ==
1218                             BTRFS_FILE_EXTENT_INLINE)
1219                                 continue;
1220                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1221                         if (bytenr == 0)
1222                                 continue;
1223
1224                         nr_file_extents++;
1225
1226                         maybe_lock_mutex(root);
1227                         ret = process_func(trans, root, bytenr,
1228                                            orig_buf->start, buf->start,
1229                                            orig_root, ref_root,
1230                                            orig_generation, ref_generation,
1231                                            key.objectid);
1232                         maybe_unlock_mutex(root);
1233
1234                         if (ret) {
1235                                 faili = i;
1236                                 WARN_ON(1);
1237                                 goto fail;
1238                         }
1239                 } else {
1240                         bytenr = btrfs_node_blockptr(buf, i);
1241                         maybe_lock_mutex(root);
1242                         ret = process_func(trans, root, bytenr,
1243                                            orig_buf->start, buf->start,
1244                                            orig_root, ref_root,
1245                                            orig_generation, ref_generation,
1246                                            level - 1);
1247                         maybe_unlock_mutex(root);
1248                         if (ret) {
1249                                 faili = i;
1250                                 WARN_ON(1);
1251                                 goto fail;
1252                         }
1253                 }
1254         }
1255 out:
1256         if (nr_extents) {
1257                 if (level == 0)
1258                         *nr_extents = nr_file_extents;
1259                 else
1260                         *nr_extents = nritems;
1261         }
1262         return 0;
1263 fail:
1264         WARN_ON(1);
1265         return ret;
1266 }
1267
1268 int btrfs_update_ref(struct btrfs_trans_handle *trans,
1269                      struct btrfs_root *root, struct extent_buffer *orig_buf,
1270                      struct extent_buffer *buf, int start_slot, int nr)
1271
1272 {
1273         u64 bytenr;
1274         u64 ref_root;
1275         u64 orig_root;
1276         u64 ref_generation;
1277         u64 orig_generation;
1278         struct btrfs_key key;
1279         struct btrfs_file_extent_item *fi;
1280         int i;
1281         int ret;
1282         int slot;
1283         int level;
1284
1285         BUG_ON(start_slot < 0);
1286         BUG_ON(start_slot + nr > btrfs_header_nritems(buf));
1287
1288         ref_root = btrfs_header_owner(buf);
1289         ref_generation = btrfs_header_generation(buf);
1290         orig_root = btrfs_header_owner(orig_buf);
1291         orig_generation = btrfs_header_generation(orig_buf);
1292         level = btrfs_header_level(buf);
1293
1294         if (!root->ref_cows) {
1295                 if (level == 0 &&
1296                     root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
1297                         return 0;
1298                 if (level != 0 &&
1299                     root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
1300                         return 0;
1301         }
1302
1303         for (i = 0, slot = start_slot; i < nr; i++, slot++) {
1304                 cond_resched();
1305                 if (level == 0) {
1306                         btrfs_item_key_to_cpu(buf, &key, slot);
1307                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1308                                 continue;
1309                         fi = btrfs_item_ptr(buf, slot,
1310                                             struct btrfs_file_extent_item);
1311                         if (btrfs_file_extent_type(buf, fi) ==
1312                             BTRFS_FILE_EXTENT_INLINE)
1313                                 continue;
1314                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1315                         if (bytenr == 0)
1316                                 continue;
1317                         maybe_lock_mutex(root);
1318                         ret = __btrfs_update_extent_ref(trans, root, bytenr,
1319                                             orig_buf->start, buf->start,
1320                                             orig_root, ref_root,
1321                                             orig_generation, ref_generation,
1322                                             key.objectid);
1323                         maybe_unlock_mutex(root);
1324                         if (ret)
1325                                 goto fail;
1326                 } else {
1327                         bytenr = btrfs_node_blockptr(buf, slot);
1328                         maybe_lock_mutex(root);
1329                         ret = __btrfs_update_extent_ref(trans, root, bytenr,
1330                                             orig_buf->start, buf->start,
1331                                             orig_root, ref_root,
1332                                             orig_generation, ref_generation,
1333                                             level - 1);
1334                         maybe_unlock_mutex(root);
1335                         if (ret)
1336                                 goto fail;
1337                 }
1338         }
1339         return 0;
1340 fail:
1341         WARN_ON(1);
1342         return -1;
1343 }
1344
1345 static int write_one_cache_group(struct btrfs_trans_handle *trans,
1346                                  struct btrfs_root *root,
1347                                  struct btrfs_path *path,
1348                                  struct btrfs_block_group_cache *cache)
1349 {
1350         int ret;
1351         int pending_ret;
1352         struct btrfs_root *extent_root = root->fs_info->extent_root;
1353         unsigned long bi;
1354         struct extent_buffer *leaf;
1355
1356         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1357         if (ret < 0)
1358                 goto fail;
1359         BUG_ON(ret);
1360
1361         leaf = path->nodes[0];
1362         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
1363         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
1364         btrfs_mark_buffer_dirty(leaf);
1365         btrfs_release_path(extent_root, path);
1366 fail:
1367         finish_current_insert(trans, extent_root);
1368         pending_ret = del_pending_extents(trans, extent_root);
1369         if (ret)
1370                 return ret;
1371         if (pending_ret)
1372                 return pending_ret;
1373         return 0;
1374
1375 }
1376
1377 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
1378                                    struct btrfs_root *root)
1379 {
1380         struct btrfs_block_group_cache *cache, *entry;
1381         struct rb_node *n;
1382         int err = 0;
1383         int werr = 0;
1384         struct btrfs_path *path;
1385         u64 last = 0;
1386
1387         path = btrfs_alloc_path();
1388         if (!path)
1389                 return -ENOMEM;
1390
1391         mutex_lock(&root->fs_info->alloc_mutex);
1392         while(1) {
1393                 cache = NULL;
1394                 spin_lock(&root->fs_info->block_group_cache_lock);
1395                 for (n = rb_first(&root->fs_info->block_group_cache_tree);
1396                      n; n = rb_next(n)) {
1397                         entry = rb_entry(n, struct btrfs_block_group_cache,
1398                                          cache_node);
1399                         if (entry->dirty) {
1400                                 cache = entry;
1401                                 break;
1402                         }
1403                 }
1404                 spin_unlock(&root->fs_info->block_group_cache_lock);
1405
1406                 if (!cache)
1407                         break;
1408
1409                 cache->dirty = 0;
1410                 last += cache->key.offset;
1411
1412                 err = write_one_cache_group(trans, root,
1413                                             path, cache);
1414                 /*
1415                  * if we fail to write the cache group, we want
1416                  * to keep it marked dirty in hopes that a later
1417                  * write will work
1418                  */
1419                 if (err) {
1420                         werr = err;
1421                         continue;
1422                 }
1423         }
1424         btrfs_free_path(path);
1425         mutex_unlock(&root->fs_info->alloc_mutex);
1426         return werr;
1427 }
1428
1429 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1430                              u64 total_bytes, u64 bytes_used,
1431                              struct btrfs_space_info **space_info)
1432 {
1433         struct btrfs_space_info *found;
1434
1435         found = __find_space_info(info, flags);
1436         if (found) {
1437                 found->total_bytes += total_bytes;
1438                 found->bytes_used += bytes_used;
1439                 found->full = 0;
1440                 *space_info = found;
1441                 return 0;
1442         }
1443         found = kmalloc(sizeof(*found), GFP_NOFS);
1444         if (!found)
1445                 return -ENOMEM;
1446
1447         list_add(&found->list, &info->space_info);
1448         INIT_LIST_HEAD(&found->block_groups);
1449         spin_lock_init(&found->lock);
1450         found->flags = flags;
1451         found->total_bytes = total_bytes;
1452         found->bytes_used = bytes_used;
1453         found->bytes_pinned = 0;
1454         found->bytes_reserved = 0;
1455         found->full = 0;
1456         found->force_alloc = 0;
1457         *space_info = found;
1458         return 0;
1459 }
1460
1461 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1462 {
1463         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1464                                    BTRFS_BLOCK_GROUP_RAID1 |
1465                                    BTRFS_BLOCK_GROUP_RAID10 |
1466                                    BTRFS_BLOCK_GROUP_DUP);
1467         if (extra_flags) {
1468                 if (flags & BTRFS_BLOCK_GROUP_DATA)
1469                         fs_info->avail_data_alloc_bits |= extra_flags;
1470                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1471                         fs_info->avail_metadata_alloc_bits |= extra_flags;
1472                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1473                         fs_info->avail_system_alloc_bits |= extra_flags;
1474         }
1475 }
1476
1477 static u64 reduce_alloc_profile(struct btrfs_root *root, u64 flags)
1478 {
1479         u64 num_devices = root->fs_info->fs_devices->num_devices;
1480
1481         if (num_devices == 1)
1482                 flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
1483         if (num_devices < 4)
1484                 flags &= ~BTRFS_BLOCK_GROUP_RAID10;
1485
1486         if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
1487             (flags & (BTRFS_BLOCK_GROUP_RAID1 |
1488                       BTRFS_BLOCK_GROUP_RAID10))) {
1489                 flags &= ~BTRFS_BLOCK_GROUP_DUP;
1490         }
1491
1492         if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
1493             (flags & BTRFS_BLOCK_GROUP_RAID10)) {
1494                 flags &= ~BTRFS_BLOCK_GROUP_RAID1;
1495         }
1496
1497         if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
1498             ((flags & BTRFS_BLOCK_GROUP_RAID1) |
1499              (flags & BTRFS_BLOCK_GROUP_RAID10) |
1500              (flags & BTRFS_BLOCK_GROUP_DUP)))
1501                 flags &= ~BTRFS_BLOCK_GROUP_RAID0;
1502         return flags;
1503 }
1504
1505 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1506                           struct btrfs_root *extent_root, u64 alloc_bytes,
1507                           u64 flags, int force)
1508 {
1509         struct btrfs_space_info *space_info;
1510         u64 thresh;
1511         u64 start;
1512         u64 num_bytes;
1513         int ret = 0, waited = 0;
1514
1515         flags = reduce_alloc_profile(extent_root, flags);
1516
1517         space_info = __find_space_info(extent_root->fs_info, flags);
1518         if (!space_info) {
1519                 ret = update_space_info(extent_root->fs_info, flags,
1520                                         0, 0, &space_info);
1521                 BUG_ON(ret);
1522         }
1523         BUG_ON(!space_info);
1524
1525         if (space_info->force_alloc) {
1526                 force = 1;
1527                 space_info->force_alloc = 0;
1528         }
1529         if (space_info->full)
1530                 goto out;
1531
1532         thresh = div_factor(space_info->total_bytes, 6);
1533         if (!force &&
1534            (space_info->bytes_used + space_info->bytes_pinned +
1535             space_info->bytes_reserved + alloc_bytes) < thresh)
1536                 goto out;
1537
1538         while (!mutex_trylock(&extent_root->fs_info->chunk_mutex)) {
1539                 if (!force)
1540                         goto out;
1541                 mutex_unlock(&extent_root->fs_info->alloc_mutex);
1542                 cond_resched();
1543                 mutex_lock(&extent_root->fs_info->alloc_mutex);
1544                 waited = 1;
1545         }
1546
1547         if (waited && space_info->full)
1548                 goto out_unlock;
1549
1550         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
1551         if (ret == -ENOSPC) {
1552 printk("space info full %Lu\n", flags);
1553                 space_info->full = 1;
1554                 goto out_unlock;
1555         }
1556         BUG_ON(ret);
1557
1558         ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1559                      BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1560         BUG_ON(ret);
1561
1562 out_unlock:
1563         mutex_unlock(&extent_root->fs_info->chunk_mutex);
1564 out:
1565         return ret;
1566 }
1567
1568 static int update_block_group(struct btrfs_trans_handle *trans,
1569                               struct btrfs_root *root,
1570                               u64 bytenr, u64 num_bytes, int alloc,
1571                               int mark_free)
1572 {
1573         struct btrfs_block_group_cache *cache;
1574         struct btrfs_fs_info *info = root->fs_info;
1575         u64 total = num_bytes;
1576         u64 old_val;
1577         u64 byte_in_group;
1578
1579         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1580         while(total) {
1581                 cache = btrfs_lookup_block_group(info, bytenr);
1582                 if (!cache) {
1583                         return -1;
1584                 }
1585                 byte_in_group = bytenr - cache->key.objectid;
1586                 WARN_ON(byte_in_group > cache->key.offset);
1587
1588                 spin_lock(&cache->lock);
1589                 cache->dirty = 1;
1590                 old_val = btrfs_block_group_used(&cache->item);
1591                 num_bytes = min(total, cache->key.offset - byte_in_group);
1592                 if (alloc) {
1593                         old_val += num_bytes;
1594                         cache->space_info->bytes_used += num_bytes;
1595                         btrfs_set_block_group_used(&cache->item, old_val);
1596                         spin_unlock(&cache->lock);
1597                 } else {
1598                         old_val -= num_bytes;
1599                         cache->space_info->bytes_used -= num_bytes;
1600                         btrfs_set_block_group_used(&cache->item, old_val);
1601                         spin_unlock(&cache->lock);
1602                         if (mark_free) {
1603                                 int ret;
1604                                 ret = btrfs_add_free_space(cache, bytenr,
1605                                                            num_bytes);
1606                                 if (ret)
1607                                         return -1;
1608                         }
1609                 }
1610                 total -= num_bytes;
1611                 bytenr += num_bytes;
1612         }
1613         return 0;
1614 }
1615
1616 static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
1617 {
1618         struct btrfs_block_group_cache *cache;
1619
1620         cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
1621         if (!cache)
1622                 return 0;
1623
1624         return cache->key.objectid;
1625 }
1626
1627 int btrfs_update_pinned_extents(struct btrfs_root *root,
1628                                 u64 bytenr, u64 num, int pin)
1629 {
1630         u64 len;
1631         struct btrfs_block_group_cache *cache;
1632         struct btrfs_fs_info *fs_info = root->fs_info;
1633
1634         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1635         if (pin) {
1636                 set_extent_dirty(&fs_info->pinned_extents,
1637                                 bytenr, bytenr + num - 1, GFP_NOFS);
1638         } else {
1639                 clear_extent_dirty(&fs_info->pinned_extents,
1640                                 bytenr, bytenr + num - 1, GFP_NOFS);
1641         }
1642         while (num > 0) {
1643                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1644                 BUG_ON(!cache);
1645                 len = min(num, cache->key.offset -
1646                           (bytenr - cache->key.objectid));
1647                 if (pin) {
1648                         spin_lock(&cache->lock);
1649                         cache->pinned += len;
1650                         cache->space_info->bytes_pinned += len;
1651                         spin_unlock(&cache->lock);
1652                         fs_info->total_pinned += len;
1653                 } else {
1654                         spin_lock(&cache->lock);
1655                         cache->pinned -= len;
1656                         cache->space_info->bytes_pinned -= len;
1657                         spin_unlock(&cache->lock);
1658                         fs_info->total_pinned -= len;
1659                 }
1660                 bytenr += len;
1661                 num -= len;
1662         }
1663         return 0;
1664 }
1665
1666 static int update_reserved_extents(struct btrfs_root *root,
1667                                    u64 bytenr, u64 num, int reserve)
1668 {
1669         u64 len;
1670         struct btrfs_block_group_cache *cache;
1671         struct btrfs_fs_info *fs_info = root->fs_info;
1672
1673         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1674         while (num > 0) {
1675                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1676                 BUG_ON(!cache);
1677                 len = min(num, cache->key.offset -
1678                           (bytenr - cache->key.objectid));
1679                 if (reserve) {
1680                         spin_lock(&cache->lock);
1681                         cache->reserved += len;
1682                         cache->space_info->bytes_reserved += len;
1683                         spin_unlock(&cache->lock);
1684                 } else {
1685                         spin_lock(&cache->lock);
1686                         cache->reserved -= len;
1687                         cache->space_info->bytes_reserved -= len;
1688                         spin_unlock(&cache->lock);
1689                 }
1690                 bytenr += len;
1691                 num -= len;
1692         }
1693         return 0;
1694 }
1695
1696 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
1697 {
1698         u64 last = 0;
1699         u64 start;
1700         u64 end;
1701         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
1702         int ret;
1703
1704         while(1) {
1705                 ret = find_first_extent_bit(pinned_extents, last,
1706                                             &start, &end, EXTENT_DIRTY);
1707                 if (ret)
1708                         break;
1709                 set_extent_dirty(copy, start, end, GFP_NOFS);
1710                 last = end + 1;
1711         }
1712         return 0;
1713 }
1714
1715 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1716                                struct btrfs_root *root,
1717                                struct extent_io_tree *unpin)
1718 {
1719         u64 start;
1720         u64 end;
1721         int ret;
1722         struct btrfs_block_group_cache *cache;
1723
1724         mutex_lock(&root->fs_info->alloc_mutex);
1725         while(1) {
1726                 ret = find_first_extent_bit(unpin, 0, &start, &end,
1727                                             EXTENT_DIRTY);
1728                 if (ret)
1729                         break;
1730                 btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
1731                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1732                 cache = btrfs_lookup_block_group(root->fs_info, start);
1733                 if (cache->cached)
1734                         btrfs_add_free_space(cache, start, end - start + 1);
1735                 if (need_resched()) {
1736                         mutex_unlock(&root->fs_info->alloc_mutex);
1737                         cond_resched();
1738                         mutex_lock(&root->fs_info->alloc_mutex);
1739                 }
1740         }
1741         mutex_unlock(&root->fs_info->alloc_mutex);
1742         return 0;
1743 }
1744
1745 static int finish_current_insert(struct btrfs_trans_handle *trans,
1746                                  struct btrfs_root *extent_root)
1747 {
1748         u64 start;
1749         u64 end;
1750         u64 priv;
1751         struct btrfs_fs_info *info = extent_root->fs_info;
1752         struct btrfs_path *path;
1753         struct btrfs_extent_ref *ref;
1754         struct pending_extent_op *extent_op;
1755         struct btrfs_key key;
1756         struct btrfs_extent_item extent_item;
1757         int ret;
1758         int err = 0;
1759
1760         WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
1761         btrfs_set_stack_extent_refs(&extent_item, 1);
1762         path = btrfs_alloc_path();
1763
1764         while(1) {
1765                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1766                                             &end, EXTENT_LOCKED);
1767                 if (ret)
1768                         break;
1769
1770                 ret = get_state_private(&info->extent_ins, start, &priv);
1771                 BUG_ON(ret);
1772                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
1773
1774                 if (extent_op->type == PENDING_EXTENT_INSERT) {
1775                         key.objectid = start;
1776                         key.offset = end + 1 - start;
1777                         key.type = BTRFS_EXTENT_ITEM_KEY;
1778                         err = btrfs_insert_item(trans, extent_root, &key,
1779                                         &extent_item, sizeof(extent_item));
1780                         BUG_ON(err);
1781
1782                         clear_extent_bits(&info->extent_ins, start, end,
1783                                           EXTENT_LOCKED, GFP_NOFS);
1784
1785                         err = insert_extent_backref(trans, extent_root, path,
1786                                                 start, extent_op->parent,
1787                                                 extent_root->root_key.objectid,
1788                                                 extent_op->generation,
1789                                                 extent_op->level);
1790                         BUG_ON(err);
1791                 } else if (extent_op->type == PENDING_BACKREF_UPDATE) {
1792                         err = lookup_extent_backref(trans, extent_root, path,
1793                                                 start, extent_op->orig_parent,
1794                                                 extent_root->root_key.objectid,
1795                                                 extent_op->orig_generation,
1796                                                 extent_op->level, 0);
1797                         BUG_ON(err);
1798
1799                         clear_extent_bits(&info->extent_ins, start, end,
1800                                           EXTENT_LOCKED, GFP_NOFS);
1801
1802                         key.objectid = start;
1803                         key.offset = extent_op->parent;
1804                         key.type = BTRFS_EXTENT_REF_KEY;
1805                         err = btrfs_set_item_key_safe(trans, extent_root, path,
1806                                                       &key);
1807                         BUG_ON(err);
1808                         ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1809                                              struct btrfs_extent_ref);
1810                         btrfs_set_ref_generation(path->nodes[0], ref,
1811                                                  extent_op->generation);
1812                         btrfs_mark_buffer_dirty(path->nodes[0]);
1813                         btrfs_release_path(extent_root, path);
1814                 } else {
1815                         BUG_ON(1);
1816                 }
1817                 kfree(extent_op);
1818
1819                 if (need_resched()) {
1820                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
1821                         cond_resched();
1822                         mutex_lock(&extent_root->fs_info->alloc_mutex);
1823                 }
1824         }
1825         btrfs_free_path(path);
1826         return 0;
1827 }
1828
1829 static int pin_down_bytes(struct btrfs_trans_handle *trans,
1830                           struct btrfs_root *root,
1831                           u64 bytenr, u64 num_bytes, int is_data)
1832 {
1833         int err = 0;
1834         struct extent_buffer *buf;
1835
1836         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1837         if (is_data)
1838                 goto pinit;
1839
1840         buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1841         if (!buf)
1842                 goto pinit;
1843
1844         /* we can reuse a block if it hasn't been written
1845          * and it is from this transaction.  We can't
1846          * reuse anything from the tree log root because
1847          * it has tiny sub-transactions.
1848          */
1849         if (btrfs_buffer_uptodate(buf, 0) &&
1850             btrfs_try_tree_lock(buf)) {
1851                 u64 header_owner = btrfs_header_owner(buf);
1852                 u64 header_transid = btrfs_header_generation(buf);
1853                 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
1854                     header_owner != BTRFS_TREE_RELOC_OBJECTID &&
1855                     header_transid == trans->transid &&
1856                     !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
1857                         clean_tree_block(NULL, root, buf);
1858                         btrfs_tree_unlock(buf);
1859                         free_extent_buffer(buf);
1860                         return 1;
1861                 }
1862                 btrfs_tree_unlock(buf);
1863         }
1864         free_extent_buffer(buf);
1865 pinit:
1866         btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
1867
1868         BUG_ON(err < 0);
1869         return 0;
1870 }
1871
1872 /*
1873  * remove an extent from the root, returns 0 on success
1874  */
1875 static int __free_extent(struct btrfs_trans_handle *trans,
1876                          struct btrfs_root *root,
1877                          u64 bytenr, u64 num_bytes, u64 parent,
1878                          u64 root_objectid, u64 ref_generation,
1879                          u64 owner_objectid, int pin, int mark_free)
1880 {
1881         struct btrfs_path *path;
1882         struct btrfs_key key;
1883         struct btrfs_fs_info *info = root->fs_info;
1884         struct btrfs_root *extent_root = info->extent_root;
1885         struct extent_buffer *leaf;
1886         int ret;
1887         int extent_slot = 0;
1888         int found_extent = 0;
1889         int num_to_del = 1;
1890         struct btrfs_extent_item *ei;
1891         u32 refs;
1892
1893         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1894         key.objectid = bytenr;
1895         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1896         key.offset = num_bytes;
1897         path = btrfs_alloc_path();
1898         if (!path)
1899                 return -ENOMEM;
1900
1901         path->reada = 1;
1902         ret = lookup_extent_backref(trans, extent_root, path,
1903                                     bytenr, parent, root_objectid,
1904                                     ref_generation, owner_objectid, 1);
1905         if (ret == 0) {
1906                 struct btrfs_key found_key;
1907                 extent_slot = path->slots[0];
1908                 while(extent_slot > 0) {
1909                         extent_slot--;
1910                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1911                                               extent_slot);
1912                         if (found_key.objectid != bytenr)
1913                                 break;
1914                         if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
1915                             found_key.offset == num_bytes) {
1916                                 found_extent = 1;
1917                                 break;
1918                         }
1919                         if (path->slots[0] - extent_slot > 5)
1920                                 break;
1921                 }
1922                 if (!found_extent) {
1923                         ret = remove_extent_backref(trans, extent_root, path);
1924                         BUG_ON(ret);
1925                         btrfs_release_path(extent_root, path);
1926                         ret = btrfs_search_slot(trans, extent_root,
1927                                                 &key, path, -1, 1);
1928                         BUG_ON(ret);
1929                         extent_slot = path->slots[0];
1930                 }
1931         } else {
1932                 btrfs_print_leaf(extent_root, path->nodes[0]);
1933                 WARN_ON(1);
1934                 printk("Unable to find ref byte nr %Lu root %Lu "
1935                        "gen %Lu owner %Lu\n", bytenr,
1936                        root_objectid, ref_generation, owner_objectid);
1937         }
1938
1939         leaf = path->nodes[0];
1940         ei = btrfs_item_ptr(leaf, extent_slot,
1941                             struct btrfs_extent_item);
1942         refs = btrfs_extent_refs(leaf, ei);
1943         BUG_ON(refs == 0);
1944         refs -= 1;
1945         btrfs_set_extent_refs(leaf, ei, refs);
1946
1947         btrfs_mark_buffer_dirty(leaf);
1948
1949         if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
1950                 struct btrfs_extent_ref *ref;
1951                 ref = btrfs_item_ptr(leaf, path->slots[0],
1952                                      struct btrfs_extent_ref);
1953                 BUG_ON(btrfs_ref_num_refs(leaf, ref) != 1);
1954                 /* if the back ref and the extent are next to each other
1955                  * they get deleted below in one shot
1956                  */
1957                 path->slots[0] = extent_slot;
1958                 num_to_del = 2;
1959         } else if (found_extent) {
1960                 /* otherwise delete the extent back ref */
1961                 ret = remove_extent_backref(trans, extent_root, path);
1962                 BUG_ON(ret);
1963                 /* if refs are 0, we need to setup the path for deletion */
1964                 if (refs == 0) {
1965                         btrfs_release_path(extent_root, path);
1966                         ret = btrfs_search_slot(trans, extent_root, &key, path,
1967                                                 -1, 1);
1968                         BUG_ON(ret);
1969                 }
1970         }
1971
1972         if (refs == 0) {
1973                 u64 super_used;
1974                 u64 root_used;
1975 #ifdef BIO_RW_DISCARD
1976                 u64 map_length = num_bytes;
1977                 struct btrfs_multi_bio *multi = NULL;
1978 #endif
1979
1980                 if (pin) {
1981                         ret = pin_down_bytes(trans, root, bytenr, num_bytes,
1982                                 owner_objectid >= BTRFS_FIRST_FREE_OBJECTID);
1983                         if (ret > 0)
1984                                 mark_free = 1;
1985                         BUG_ON(ret < 0);
1986                 }
1987
1988                 /* block accounting for super block */
1989                 spin_lock_irq(&info->delalloc_lock);
1990                 super_used = btrfs_super_bytes_used(&info->super_copy);
1991                 btrfs_set_super_bytes_used(&info->super_copy,
1992                                            super_used - num_bytes);
1993                 spin_unlock_irq(&info->delalloc_lock);
1994
1995                 /* block accounting for root item */
1996                 root_used = btrfs_root_used(&root->root_item);
1997                 btrfs_set_root_used(&root->root_item,
1998                                            root_used - num_bytes);
1999                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
2000                                       num_to_del);
2001                 BUG_ON(ret);
2002                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
2003                                          mark_free);
2004                 BUG_ON(ret);
2005
2006 #ifdef BIO_RW_DISCARD
2007                 /* Tell the block device(s) that the sectors can be discarded */
2008                 ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
2009                                       bytenr, &map_length, &multi, 0);
2010                 if (!ret) {
2011                         struct btrfs_bio_stripe *stripe = multi->stripes;
2012                         int i;
2013
2014                         if (map_length > num_bytes)
2015                                 map_length = num_bytes;
2016
2017                         for (i = 0; i < multi->num_stripes; i++, stripe++) {
2018                                 blkdev_issue_discard(stripe->dev->bdev,
2019                                                      stripe->physical >> 9,
2020                                                      map_length >> 9);
2021                         }
2022                         kfree(multi);
2023                 }
2024 #endif
2025         }
2026         btrfs_free_path(path);
2027         finish_current_insert(trans, extent_root);
2028         return ret;
2029 }
2030
2031 /*
2032  * find all the blocks marked as pending in the radix tree and remove
2033  * them from the extent map
2034  */
2035 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
2036                                btrfs_root *extent_root)
2037 {
2038         int ret;
2039         int err = 0;
2040         int mark_free = 0;
2041         u64 start;
2042         u64 end;
2043         u64 priv;
2044         struct extent_io_tree *pending_del;
2045         struct extent_io_tree *extent_ins;
2046         struct pending_extent_op *extent_op;
2047
2048         WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
2049         extent_ins = &extent_root->fs_info->extent_ins;
2050         pending_del = &extent_root->fs_info->pending_del;
2051
2052         while(1) {
2053                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
2054                                             EXTENT_LOCKED);
2055                 if (ret)
2056                         break;
2057
2058                 ret = get_state_private(pending_del, start, &priv);
2059                 BUG_ON(ret);
2060                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
2061
2062                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
2063                                   GFP_NOFS);
2064
2065                 ret = pin_down_bytes(trans, extent_root, start,
2066                                      end + 1 - start, 0);
2067                 mark_free = ret > 0;
2068                 if (!test_range_bit(extent_ins, start, end,
2069                                     EXTENT_LOCKED, 0)) {
2070 free_extent:
2071                         ret = __free_extent(trans, extent_root,
2072                                             start, end + 1 - start,
2073                                             extent_op->orig_parent,
2074                                             extent_root->root_key.objectid,
2075                                             extent_op->orig_generation,
2076                                             extent_op->level, 0, mark_free);
2077                         kfree(extent_op);
2078                 } else {
2079                         kfree(extent_op);
2080                         ret = get_state_private(extent_ins, start, &priv);
2081                         BUG_ON(ret);
2082                         extent_op = (struct pending_extent_op *)
2083                                                         (unsigned long)priv;
2084
2085                         clear_extent_bits(extent_ins, start, end,
2086                                           EXTENT_LOCKED, GFP_NOFS);
2087
2088                         if (extent_op->type == PENDING_BACKREF_UPDATE)
2089                                 goto free_extent;
2090
2091                         ret = update_block_group(trans, extent_root, start,
2092                                                 end + 1 - start, 0, mark_free);
2093                         BUG_ON(ret);
2094                         kfree(extent_op);
2095                 }
2096                 if (ret)
2097                         err = ret;
2098
2099                 if (need_resched()) {
2100                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
2101                         cond_resched();
2102                         mutex_lock(&extent_root->fs_info->alloc_mutex);
2103                 }
2104         }
2105         return err;
2106 }
2107
2108 /*
2109  * remove an extent from the root, returns 0 on success
2110  */
2111 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
2112                                struct btrfs_root *root,
2113                                u64 bytenr, u64 num_bytes, u64 parent,
2114                                u64 root_objectid, u64 ref_generation,
2115                                u64 owner_objectid, int pin)
2116 {
2117         struct btrfs_root *extent_root = root->fs_info->extent_root;
2118         int pending_ret;
2119         int ret;
2120
2121         WARN_ON(num_bytes < root->sectorsize);
2122         if (root == extent_root) {
2123                 struct pending_extent_op *extent_op;
2124
2125                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2126                 BUG_ON(!extent_op);
2127
2128                 extent_op->type = PENDING_EXTENT_DELETE;
2129                 extent_op->bytenr = bytenr;
2130                 extent_op->num_bytes = num_bytes;
2131                 extent_op->parent = parent;
2132                 extent_op->orig_parent = parent;
2133                 extent_op->generation = ref_generation;
2134                 extent_op->orig_generation = ref_generation;
2135                 extent_op->level = (int)owner_objectid;
2136
2137                 set_extent_bits(&root->fs_info->pending_del,
2138                                 bytenr, bytenr + num_bytes - 1,
2139                                 EXTENT_LOCKED, GFP_NOFS);
2140                 set_state_private(&root->fs_info->pending_del,
2141                                   bytenr, (unsigned long)extent_op);
2142                 return 0;
2143         }
2144         /* if metadata always pin */
2145         if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
2146                 if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
2147                         struct btrfs_block_group_cache *cache;
2148
2149                         /* btrfs_free_reserved_extent */
2150                         cache = btrfs_lookup_block_group(root->fs_info, bytenr);
2151                         BUG_ON(!cache);
2152                         btrfs_add_free_space(cache, bytenr, num_bytes);
2153                         update_reserved_extents(root, bytenr, num_bytes, 0);
2154                         return 0;
2155                 }
2156                 pin = 1;
2157         }
2158
2159         /* if data pin when any transaction has committed this */
2160         if (ref_generation != trans->transid)
2161                 pin = 1;
2162
2163         ret = __free_extent(trans, root, bytenr, num_bytes, parent,
2164                             root_objectid, ref_generation,
2165                             owner_objectid, pin, pin == 0);
2166
2167         finish_current_insert(trans, root->fs_info->extent_root);
2168         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
2169         return ret ? ret : pending_ret;
2170 }
2171
2172 int btrfs_free_extent(struct btrfs_trans_handle *trans,
2173                       struct btrfs_root *root,
2174                       u64 bytenr, u64 num_bytes, u64 parent,
2175                       u64 root_objectid, u64 ref_generation,
2176                       u64 owner_objectid, int pin)
2177 {
2178         int ret;
2179
2180         maybe_lock_mutex(root);
2181         ret = __btrfs_free_extent(trans, root, bytenr, num_bytes, parent,
2182                                   root_objectid, ref_generation,
2183                                   owner_objectid, pin);
2184         maybe_unlock_mutex(root);
2185         return ret;
2186 }
2187
2188 static u64 stripe_align(struct btrfs_root *root, u64 val)
2189 {
2190         u64 mask = ((u64)root->stripesize - 1);
2191         u64 ret = (val + mask) & ~mask;
2192         return ret;
2193 }
2194
2195 /*
2196  * walks the btree of allocated extents and find a hole of a given size.
2197  * The key ins is changed to record the hole:
2198  * ins->objectid == block start
2199  * ins->flags = BTRFS_EXTENT_ITEM_KEY
2200  * ins->offset == number of blocks
2201  * Any available blocks before search_start are skipped.
2202  */
2203 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
2204                                      struct btrfs_root *orig_root,
2205                                      u64 num_bytes, u64 empty_size,
2206                                      u64 search_start, u64 search_end,
2207                                      u64 hint_byte, struct btrfs_key *ins,
2208                                      u64 exclude_start, u64 exclude_nr,
2209                                      int data)
2210 {
2211         int ret;
2212         u64 orig_search_start;
2213         struct btrfs_root * root = orig_root->fs_info->extent_root;
2214         struct btrfs_fs_info *info = root->fs_info;
2215         u64 total_needed = num_bytes;
2216         u64 *last_ptr = NULL;
2217         struct btrfs_block_group_cache *block_group;
2218         int chunk_alloc_done = 0;
2219         int empty_cluster = 2 * 1024 * 1024;
2220         int allowed_chunk_alloc = 0;
2221
2222         WARN_ON(num_bytes < root->sectorsize);
2223         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
2224
2225         if (orig_root->ref_cows || empty_size)
2226                 allowed_chunk_alloc = 1;
2227
2228         if (data & BTRFS_BLOCK_GROUP_METADATA) {
2229                 last_ptr = &root->fs_info->last_alloc;
2230                 empty_cluster = 256 * 1024;
2231         }
2232
2233         if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD))
2234                 last_ptr = &root->fs_info->last_data_alloc;
2235
2236         if (last_ptr) {
2237                 if (*last_ptr)
2238                         hint_byte = *last_ptr;
2239                 else
2240                         empty_size += empty_cluster;
2241         }
2242
2243         search_start = max(search_start, first_logical_byte(root, 0));
2244         orig_search_start = search_start;
2245
2246         search_start = max(search_start, hint_byte);
2247         total_needed += empty_size;
2248
2249 new_group:
2250         block_group = btrfs_lookup_block_group(info, search_start);
2251         if (!block_group)
2252                 block_group = btrfs_lookup_first_block_group(info,
2253                                                              search_start);
2254
2255         /*
2256          * Ok this looks a little tricky, buts its really simple.  First if we
2257          * didn't find a block group obviously we want to start over.
2258          * Secondly, if the block group we found does not match the type we
2259          * need, and we have a last_ptr and its not 0, chances are the last
2260          * allocation we made was at the end of the block group, so lets go
2261          * ahead and skip the looking through the rest of the block groups and
2262          * start at the beginning.  This helps with metadata allocations,
2263          * since you are likely to have a bunch of data block groups to search
2264          * through first before you realize that you need to start over, so go
2265          * ahead and start over and save the time.
2266          */
2267         if (!block_group || (!block_group_bits(block_group, data) &&
2268                              last_ptr && *last_ptr)) {
2269                 if (search_start != orig_search_start) {
2270                         if (last_ptr && *last_ptr) {
2271                                 total_needed += empty_cluster;
2272                                 *last_ptr = 0;
2273                         }
2274                         search_start = orig_search_start;
2275                         goto new_group;
2276                 } else if (!chunk_alloc_done && allowed_chunk_alloc) {
2277                         ret = do_chunk_alloc(trans, root,
2278                                              num_bytes + 2 * 1024 * 1024,
2279                                              data, 1);
2280                         if (ret < 0)
2281                                 goto error;
2282                         BUG_ON(ret);
2283                         chunk_alloc_done = 1;
2284                         search_start = orig_search_start;
2285                         goto new_group;
2286                 } else {
2287                         ret = -ENOSPC;
2288                         goto error;
2289                 }
2290         }
2291
2292         /*
2293          * this is going to seach through all of the existing block groups it
2294          * can find, so if we don't find something we need to see if we can
2295          * allocate what we need.
2296          */
2297         ret = find_free_space(root, &block_group, &search_start,
2298                               total_needed, data);
2299         if (ret == -ENOSPC) {
2300                 /*
2301                  * instead of allocating, start at the original search start
2302                  * and see if there is something to be found, if not then we
2303                  * allocate
2304                  */
2305                 if (search_start != orig_search_start) {
2306                         if (last_ptr && *last_ptr) {
2307                                 *last_ptr = 0;
2308                                 total_needed += empty_cluster;
2309                         }
2310                         search_start = orig_search_start;
2311                         goto new_group;
2312                 }
2313
2314                 /*
2315                  * we've already allocated, we're pretty screwed
2316                  */
2317                 if (chunk_alloc_done) {
2318                         goto error;
2319                 } else if (!allowed_chunk_alloc && block_group &&
2320                            block_group_bits(block_group, data)) {
2321                         block_group->space_info->force_alloc = 1;
2322                         goto error;
2323                 } else if (!allowed_chunk_alloc) {
2324                         goto error;
2325                 }
2326
2327                 ret = do_chunk_alloc(trans, root, num_bytes + 2 * 1024 * 1024,
2328                                      data, 1);
2329                 if (ret < 0)
2330                         goto error;
2331
2332                 BUG_ON(ret);
2333                 chunk_alloc_done = 1;
2334                 if (block_group)
2335                         search_start = block_group->key.objectid +
2336                                 block_group->key.offset;
2337                 else
2338                         search_start = orig_search_start;
2339                 goto new_group;
2340         }
2341
2342         if (ret)
2343                 goto error;
2344
2345         search_start = stripe_align(root, search_start);
2346         ins->objectid = search_start;
2347         ins->offset = num_bytes;
2348
2349         if (ins->objectid + num_bytes >= search_end) {
2350                 search_start = orig_search_start;
2351                 if (chunk_alloc_done) {
2352                         ret = -ENOSPC;
2353                         goto error;
2354                 }
2355                 goto new_group;
2356         }
2357
2358         if (ins->objectid + num_bytes >
2359             block_group->key.objectid + block_group->key.offset) {
2360                 if (search_start == orig_search_start && chunk_alloc_done) {
2361                         ret = -ENOSPC;
2362                         goto error;
2363                 }
2364                 search_start = block_group->key.objectid +
2365                         block_group->key.offset;
2366                 goto new_group;
2367         }
2368
2369         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
2370             ins->objectid < exclude_start + exclude_nr)) {
2371                 search_start = exclude_start + exclude_nr;
2372                 goto new_group;
2373         }
2374
2375         if (!(data & BTRFS_BLOCK_GROUP_DATA))
2376                 trans->block_group = block_group;
2377
2378         ins->offset = num_bytes;
2379         if (last_ptr) {
2380                 *last_ptr = ins->objectid + ins->offset;
2381                 if (*last_ptr ==
2382                     btrfs_super_total_bytes(&root->fs_info->super_copy))
2383                         *last_ptr = 0;
2384         }
2385
2386         ret = 0;
2387 error:
2388         return ret;
2389 }
2390
2391 static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
2392 {
2393         struct btrfs_block_group_cache *cache;
2394         struct list_head *l;
2395
2396         printk(KERN_INFO "space_info has %Lu free, is %sfull\n",
2397                info->total_bytes - info->bytes_used - info->bytes_pinned -
2398                info->bytes_reserved, (info->full) ? "" : "not ");
2399
2400         spin_lock(&info->lock);
2401         list_for_each(l, &info->block_groups) {
2402                 cache = list_entry(l, struct btrfs_block_group_cache, list);
2403                 spin_lock(&cache->lock);
2404                 printk(KERN_INFO "block group %Lu has %Lu bytes, %Lu used "
2405                        "%Lu pinned %Lu reserved\n",
2406                        cache->key.objectid, cache->key.offset,
2407                        btrfs_block_group_used(&cache->item),
2408                        cache->pinned, cache->reserved);
2409                 btrfs_dump_free_space(cache, bytes);
2410                 spin_unlock(&cache->lock);
2411         }
2412         spin_unlock(&info->lock);
2413 }
2414
2415 static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2416                                   struct btrfs_root *root,
2417                                   u64 num_bytes, u64 min_alloc_size,
2418                                   u64 empty_size, u64 hint_byte,
2419                                   u64 search_end, struct btrfs_key *ins,
2420                                   u64 data)
2421 {
2422         int ret;
2423         u64 search_start = 0;
2424         u64 alloc_profile;
2425         struct btrfs_fs_info *info = root->fs_info;
2426         struct btrfs_block_group_cache *cache;
2427
2428         if (data) {
2429                 alloc_profile = info->avail_data_alloc_bits &
2430                                 info->data_alloc_profile;
2431                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2432         } else if (root == root->fs_info->chunk_root) {
2433                 alloc_profile = info->avail_system_alloc_bits &
2434                                 info->system_alloc_profile;
2435                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2436         } else {
2437                 alloc_profile = info->avail_metadata_alloc_bits &
2438                                 info->metadata_alloc_profile;
2439                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2440         }
2441 again:
2442         data = reduce_alloc_profile(root, data);
2443         /*
2444          * the only place that sets empty_size is btrfs_realloc_node, which
2445          * is not called recursively on allocations
2446          */
2447         if (empty_size || root->ref_cows) {
2448                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2449                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2450                                      2 * 1024 * 1024,
2451                                      BTRFS_BLOCK_GROUP_METADATA |
2452                                      (info->metadata_alloc_profile &
2453                                       info->avail_metadata_alloc_bits), 0);
2454                 }
2455                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2456                                      num_bytes + 2 * 1024 * 1024, data, 0);
2457         }
2458
2459         WARN_ON(num_bytes < root->sectorsize);
2460         ret = find_free_extent(trans, root, num_bytes, empty_size,
2461                                search_start, search_end, hint_byte, ins,
2462                                trans->alloc_exclude_start,
2463                                trans->alloc_exclude_nr, data);
2464
2465         if (ret == -ENOSPC && num_bytes > min_alloc_size) {
2466                 num_bytes = num_bytes >> 1;
2467                 num_bytes = num_bytes & ~(root->sectorsize - 1);
2468                 num_bytes = max(num_bytes, min_alloc_size);
2469                 do_chunk_alloc(trans, root->fs_info->extent_root,
2470                                num_bytes, data, 1);
2471                 goto again;
2472         }
2473         if (ret) {
2474                 struct btrfs_space_info *sinfo;
2475
2476                 sinfo = __find_space_info(root->fs_info, data);
2477                 printk("allocation failed flags %Lu, wanted %Lu\n",
2478                        data, num_bytes);
2479                 dump_space_info(sinfo, num_bytes);
2480                 BUG();
2481         }
2482         cache = btrfs_lookup_block_group(root->fs_info, ins->objectid);
2483         if (!cache) {
2484                 printk(KERN_ERR "Unable to find block group for %Lu\n", ins->objectid);
2485                 return -ENOSPC;
2486         }
2487
2488         ret = btrfs_remove_free_space(cache, ins->objectid, ins->offset);
2489
2490         return ret;
2491 }
2492
2493 int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
2494 {
2495         struct btrfs_block_group_cache *cache;
2496
2497         maybe_lock_mutex(root);
2498         cache = btrfs_lookup_block_group(root->fs_info, start);
2499         if (!cache) {
2500                 printk(KERN_ERR "Unable to find block group for %Lu\n", start);
2501                 maybe_unlock_mutex(root);
2502                 return -ENOSPC;
2503         }
2504         btrfs_add_free_space(cache, start, len);
2505         update_reserved_extents(root, start, len, 0);
2506         maybe_unlock_mutex(root);
2507         return 0;
2508 }
2509
2510 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2511                                   struct btrfs_root *root,
2512                                   u64 num_bytes, u64 min_alloc_size,
2513                                   u64 empty_size, u64 hint_byte,
2514                                   u64 search_end, struct btrfs_key *ins,
2515                                   u64 data)
2516 {
2517         int ret;
2518         maybe_lock_mutex(root);
2519         ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
2520                                      empty_size, hint_byte, search_end, ins,
2521                                      data);
2522         update_reserved_extents(root, ins->objectid, ins->offset, 1);
2523         maybe_unlock_mutex(root);
2524         return ret;
2525 }
2526
2527 static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
2528                                          struct btrfs_root *root, u64 parent,
2529                                          u64 root_objectid, u64 ref_generation,
2530                                          u64 owner, struct btrfs_key *ins)
2531 {
2532         int ret;
2533         int pending_ret;
2534         u64 super_used;
2535         u64 root_used;
2536         u64 num_bytes = ins->offset;
2537         u32 sizes[2];
2538         struct btrfs_fs_info *info = root->fs_info;
2539         struct btrfs_root *extent_root = info->extent_root;
2540         struct btrfs_extent_item *extent_item;
2541         struct btrfs_extent_ref *ref;
2542         struct btrfs_path *path;
2543         struct btrfs_key keys[2];
2544
2545         if (parent == 0)
2546                 parent = ins->objectid;
2547
2548         /* block accounting for super block */
2549         spin_lock_irq(&info->delalloc_lock);
2550         super_used = btrfs_super_bytes_used(&info->super_copy);
2551         btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
2552         spin_unlock_irq(&info->delalloc_lock);
2553
2554         /* block accounting for root item */
2555         root_used = btrfs_root_used(&root->root_item);
2556         btrfs_set_root_used(&root->root_item, root_used + num_bytes);
2557
2558         if (root == extent_root) {
2559                 struct pending_extent_op *extent_op;
2560
2561                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2562                 BUG_ON(!extent_op);
2563
2564                 extent_op->type = PENDING_EXTENT_INSERT;
2565                 extent_op->bytenr = ins->objectid;
2566                 extent_op->num_bytes = ins->offset;
2567                 extent_op->parent = parent;
2568                 extent_op->orig_parent = 0;
2569                 extent_op->generation = ref_generation;
2570                 extent_op->orig_generation = 0;
2571                 extent_op->level = (int)owner;
2572
2573                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
2574                                 ins->objectid + ins->offset - 1,
2575                                 EXTENT_LOCKED, GFP_NOFS);
2576                 set_state_private(&root->fs_info->extent_ins,
2577                                   ins->objectid, (unsigned long)extent_op);
2578                 goto update_block;
2579         }
2580
2581         memcpy(&keys[0], ins, sizeof(*ins));
2582         keys[1].objectid = ins->objectid;
2583         keys[1].type = BTRFS_EXTENT_REF_KEY;
2584         keys[1].offset = parent;
2585         sizes[0] = sizeof(*extent_item);
2586         sizes[1] = sizeof(*ref);
2587
2588         path = btrfs_alloc_path();
2589         BUG_ON(!path);
2590
2591         ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
2592                                        sizes, 2);
2593         BUG_ON(ret);
2594
2595         extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2596                                      struct btrfs_extent_item);
2597         btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
2598         ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
2599                              struct btrfs_extent_ref);
2600
2601         btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
2602         btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
2603         btrfs_set_ref_objectid(path->nodes[0], ref, owner);
2604         btrfs_set_ref_num_refs(path->nodes[0], ref, 1);
2605
2606         btrfs_mark_buffer_dirty(path->nodes[0]);
2607
2608         trans->alloc_exclude_start = 0;
2609         trans->alloc_exclude_nr = 0;
2610         btrfs_free_path(path);
2611         finish_current_insert(trans, extent_root);
2612         pending_ret = del_pending_extents(trans, extent_root);
2613
2614         if (ret)
2615                 goto out;
2616         if (pending_ret) {
2617                 ret = pending_ret;
2618                 goto out;
2619         }
2620
2621 update_block:
2622         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
2623         if (ret) {
2624                 printk("update block group failed for %Lu %Lu\n",
2625                        ins->objectid, ins->offset);
2626                 BUG();
2627         }
2628 out:
2629         return ret;
2630 }
2631
2632 int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
2633                                 struct btrfs_root *root, u64 parent,
2634                                 u64 root_objectid, u64 ref_generation,
2635                                 u64 owner, struct btrfs_key *ins)
2636 {
2637         int ret;
2638
2639         if (root_objectid == BTRFS_TREE_LOG_OBJECTID)
2640                 return 0;
2641         maybe_lock_mutex(root);
2642         ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
2643                                             ref_generation, owner, ins);
2644         update_reserved_extents(root, ins->objectid, ins->offset, 0);
2645         maybe_unlock_mutex(root);
2646         return ret;
2647 }
2648
2649 /*
2650  * this is used by the tree logging recovery code.  It records that
2651  * an extent has been allocated and makes sure to clear the free
2652  * space cache bits as well
2653  */
2654 int btrfs_alloc_logged_extent(struct btrfs_trans_handle *trans,
2655                                 struct btrfs_root *root, u64 parent,
2656                                 u64 root_objectid, u64 ref_generation,
2657                                 u64 owner, struct btrfs_key *ins)
2658 {
2659         int ret;
2660         struct btrfs_block_group_cache *block_group;
2661
2662         maybe_lock_mutex(root);
2663         block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
2664         cache_block_group(root, block_group);
2665
2666         ret = btrfs_remove_free_space(block_group, ins->objectid, ins->offset);
2667         BUG_ON(ret);
2668         ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
2669                                             ref_generation, owner, ins);
2670         maybe_unlock_mutex(root);
2671         return ret;
2672 }
2673
2674 /*
2675  * finds a free extent and does all the dirty work required for allocation
2676  * returns the key for the extent through ins, and a tree buffer for
2677  * the first block of the extent through buf.
2678  *
2679  * returns 0 if everything worked, non-zero otherwise.
2680  */
2681 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
2682                        struct btrfs_root *root,
2683                        u64 num_bytes, u64 parent, u64 min_alloc_size,
2684                        u64 root_objectid, u64 ref_generation,
2685                        u64 owner_objectid, u64 empty_size, u64 hint_byte,
2686                        u64 search_end, struct btrfs_key *ins, u64 data)
2687 {
2688         int ret;
2689
2690         maybe_lock_mutex(root);
2691
2692         ret = __btrfs_reserve_extent(trans, root, num_bytes,
2693                                      min_alloc_size, empty_size, hint_byte,
2694                                      search_end, ins, data);
2695         BUG_ON(ret);
2696         if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
2697                 ret = __btrfs_alloc_reserved_extent(trans, root, parent,
2698                                         root_objectid, ref_generation,
2699                                         owner_objectid, ins);
2700                 BUG_ON(ret);
2701
2702         } else {
2703                 update_reserved_extents(root, ins->objectid, ins->offset, 1);
2704         }
2705         maybe_unlock_mutex(root);
2706         return ret;
2707 }
2708
2709 struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
2710                                             struct btrfs_root *root,
2711                                             u64 bytenr, u32 blocksize)
2712 {
2713         struct extent_buffer *buf;
2714
2715         buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
2716         if (!buf)
2717                 return ERR_PTR(-ENOMEM);
2718         btrfs_set_header_generation(buf, trans->transid);
2719         btrfs_tree_lock(buf);
2720         clean_tree_block(trans, root, buf);
2721         btrfs_set_buffer_uptodate(buf);
2722         if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
2723                 set_extent_dirty(&root->dirty_log_pages, buf->start,
2724                          buf->start + buf->len - 1, GFP_NOFS);
2725         } else {
2726                 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
2727                          buf->start + buf->len - 1, GFP_NOFS);
2728         }
2729         trans->blocks_used++;
2730         return buf;
2731 }
2732
2733 /*
2734  * helper function to allocate a block for a given tree
2735  * returns the tree buffer or NULL.
2736  */
2737 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2738                                              struct btrfs_root *root,
2739                                              u32 blocksize, u64 parent,
2740                                              u64 root_objectid,
2741                                              u64 ref_generation,
2742                                              int level,
2743                                              u64 hint,
2744                                              u64 empty_size)
2745 {
2746         struct btrfs_key ins;
2747         int ret;
2748         struct extent_buffer *buf;
2749
2750         ret = btrfs_alloc_extent(trans, root, blocksize, parent, blocksize,
2751                                  root_objectid, ref_generation, level,
2752                                  empty_size, hint, (u64)-1, &ins, 0);
2753         if (ret) {
2754                 BUG_ON(ret > 0);
2755                 return ERR_PTR(ret);
2756         }
2757
2758         buf = btrfs_init_new_buffer(trans, root, ins.objectid, blocksize);
2759         return buf;
2760 }
2761
2762 int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
2763                         struct btrfs_root *root, struct extent_buffer *leaf)
2764 {
2765         u64 leaf_owner;
2766         u64 leaf_generation;
2767         struct btrfs_key key;
2768         struct btrfs_file_extent_item *fi;
2769         int i;
2770         int nritems;
2771         int ret;
2772
2773         BUG_ON(!btrfs_is_leaf(leaf));
2774         nritems = btrfs_header_nritems(leaf);
2775         leaf_owner = btrfs_header_owner(leaf);
2776         leaf_generation = btrfs_header_generation(leaf);
2777
2778         for (i = 0; i < nritems; i++) {
2779                 u64 disk_bytenr;
2780                 cond_resched();
2781
2782                 btrfs_item_key_to_cpu(leaf, &key, i);
2783                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2784                         continue;
2785                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2786                 if (btrfs_file_extent_type(leaf, fi) ==
2787                     BTRFS_FILE_EXTENT_INLINE)
2788                         continue;
2789                 /*
2790                  * FIXME make sure to insert a trans record that
2791                  * repeats the snapshot del on crash
2792                  */
2793                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
2794                 if (disk_bytenr == 0)
2795                         continue;
2796
2797                 mutex_lock(&root->fs_info->alloc_mutex);
2798                 ret = __btrfs_free_extent(trans, root, disk_bytenr,
2799                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
2800                                 leaf->start, leaf_owner, leaf_generation,
2801                                 key.objectid, 0);
2802                 mutex_unlock(&root->fs_info->alloc_mutex);
2803                 BUG_ON(ret);
2804
2805                 atomic_inc(&root->fs_info->throttle_gen);
2806                 wake_up(&root->fs_info->transaction_throttle);
2807                 cond_resched();
2808         }
2809         return 0;
2810 }
2811
2812 static int noinline cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
2813                                         struct btrfs_root *root,
2814                                         struct btrfs_leaf_ref *ref)
2815 {
2816         int i;
2817         int ret;
2818         struct btrfs_extent_info *info = ref->extents;
2819
2820         for (i = 0; i < ref->nritems; i++) {
2821                 mutex_lock(&root->fs_info->alloc_mutex);
2822                 ret = __btrfs_free_extent(trans, root, info->bytenr,
2823                                           info->num_bytes, ref->bytenr,
2824                                           ref->owner, ref->generation,
2825                                           info->objectid, 0);
2826                 mutex_unlock(&root->fs_info->alloc_mutex);
2827
2828                 atomic_inc(&root->fs_info->throttle_gen);
2829                 wake_up(&root->fs_info->transaction_throttle);
2830                 cond_resched();
2831
2832                 BUG_ON(ret);
2833                 info++;
2834         }
2835
2836         return 0;
2837 }
2838
2839 int drop_snap_lookup_refcount(struct btrfs_root *root, u64 start, u64 len,
2840                               u32 *refs)
2841 {
2842         int ret;
2843
2844         ret = btrfs_lookup_extent_ref(NULL, root, start, len, refs);
2845         BUG_ON(ret);
2846
2847 #if 0 // some debugging code in case we see problems here
2848         /* if the refs count is one, it won't get increased again.  But
2849          * if the ref count is > 1, someone may be decreasing it at
2850          * the same time we are.
2851          */
2852         if (*refs != 1) {
2853                 struct extent_buffer *eb = NULL;
2854                 eb = btrfs_find_create_tree_block(root, start, len);
2855                 if (eb)
2856                         btrfs_tree_lock(eb);
2857
2858                 mutex_lock(&root->fs_info->alloc_mutex);
2859                 ret = lookup_extent_ref(NULL, root, start, len, refs);
2860                 BUG_ON(ret);
2861                 mutex_unlock(&root->fs_info->alloc_mutex);
2862
2863                 if (eb) {
2864                         btrfs_tree_unlock(eb);
2865                         free_extent_buffer(eb);
2866                 }
2867                 if (*refs == 1) {
2868                         printk("block %llu went down to one during drop_snap\n",
2869                                (unsigned long long)start);
2870                 }
2871
2872         }
2873 #endif
2874
2875         cond_resched();
2876         return ret;
2877 }
2878
2879 /*
2880  * helper function for drop_snapshot, this walks down the tree dropping ref
2881  * counts as it goes.
2882  */
2883 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2884                                    struct btrfs_root *root,
2885                                    struct btrfs_path *path, int *level)
2886 {
2887         u64 root_owner;
2888         u64 root_gen;
2889         u64 bytenr;
2890         u64 ptr_gen;
2891         struct extent_buffer *next;
2892         struct extent_buffer *cur;
2893         struct extent_buffer *parent;
2894         struct btrfs_leaf_ref *ref;
2895         u32 blocksize;
2896         int ret;
2897         u32 refs;
2898
2899         WARN_ON(*level < 0);
2900         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2901         ret = drop_snap_lookup_refcount(root, path->nodes[*level]->start,
2902                                 path->nodes[*level]->len, &refs);
2903         BUG_ON(ret);
2904         if (refs > 1)
2905                 goto out;
2906
2907         /*
2908          * walk down to the last node level and free all the leaves
2909          */
2910         while(*level >= 0) {
2911                 WARN_ON(*level < 0);
2912                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2913                 cur = path->nodes[*level];
2914
2915                 if (btrfs_header_level(cur) != *level)
2916                         WARN_ON(1);
2917
2918                 if (path->slots[*level] >=
2919                     btrfs_header_nritems(cur))
2920                         break;
2921                 if (*level == 0) {
2922                         ret = btrfs_drop_leaf_ref(trans, root, cur);
2923                         BUG_ON(ret);
2924                         break;
2925                 }
2926                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2927                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2928                 blocksize = btrfs_level_size(root, *level - 1);
2929
2930                 ret = drop_snap_lookup_refcount(root, bytenr, blocksize, &refs);
2931                 BUG_ON(ret);
2932                 if (refs != 1) {
2933                         parent = path->nodes[*level];
2934                         root_owner = btrfs_header_owner(parent);
2935                         root_gen = btrfs_header_generation(parent);
2936                         path->slots[*level]++;
2937
2938                         mutex_lock(&root->fs_info->alloc_mutex);
2939                         ret = __btrfs_free_extent(trans, root, bytenr,
2940                                                 blocksize, parent->start,
2941                                                 root_owner, root_gen,
2942                                                 *level - 1, 1);
2943                         BUG_ON(ret);
2944                         mutex_unlock(&root->fs_info->alloc_mutex);
2945
2946                         atomic_inc(&root->fs_info->throttle_gen);
2947                         wake_up(&root->fs_info->transaction_throttle);
2948                         cond_resched();
2949
2950                         continue;
2951                 }
2952                 /*
2953                  * at this point, we have a single ref, and since the
2954                  * only place referencing this extent is a dead root
2955                  * the reference count should never go higher.
2956                  * So, we don't need to check it again
2957                  */
2958                 if (*level == 1) {
2959                         ref = btrfs_lookup_leaf_ref(root, bytenr);
2960                         if (ref && ref->generation != ptr_gen) {
2961                                 btrfs_free_leaf_ref(root, ref);
2962                                 ref = NULL;
2963                         }
2964                         if (ref) {
2965                                 ret = cache_drop_leaf_ref(trans, root, ref);
2966                                 BUG_ON(ret);
2967                                 btrfs_remove_leaf_ref(root, ref);
2968                                 btrfs_free_leaf_ref(root, ref);
2969                                 *level = 0;
2970                                 break;
2971                         }
2972                         if (printk_ratelimit()) {
2973                                 printk("leaf ref miss for bytenr %llu\n",
2974                                        (unsigned long long)bytenr);
2975                         }
2976                 }
2977                 next = btrfs_find_tree_block(root, bytenr, blocksize);
2978                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
2979                         free_extent_buffer(next);
2980
2981                         next = read_tree_block(root, bytenr, blocksize,
2982                                                ptr_gen);
2983                         cond_resched();
2984 #if 0
2985                         /*
2986                          * this is a debugging check and can go away
2987                          * the ref should never go all the way down to 1
2988                          * at this point
2989                          */
2990                         ret = lookup_extent_ref(NULL, root, bytenr, blocksize,
2991                                                 &refs);
2992                         BUG_ON(ret);
2993                         WARN_ON(refs != 1);
2994 #endif
2995                 }
2996                 WARN_ON(*level <= 0);
2997                 if (path->nodes[*level-1])
2998                         free_extent_buffer(path->nodes[*level-1]);
2999                 path->nodes[*level-1] = next;
3000                 *level = btrfs_header_level(next);
3001                 path->slots[*level] = 0;
3002                 cond_resched();
3003         }
3004 out:
3005         WARN_ON(*level < 0);
3006         WARN_ON(*level >= BTRFS_MAX_LEVEL);
3007
3008         if (path->nodes[*level] == root->node) {
3009                 parent = path->nodes[*level];
3010                 bytenr = path->nodes[*level]->start;
3011         } else {
3012                 parent = path->nodes[*level + 1];
3013                 bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
3014         }
3015
3016         blocksize = btrfs_level_size(root, *level);
3017         root_owner = btrfs_header_owner(parent);
3018         root_gen = btrfs_header_generation(parent);
3019
3020         mutex_lock(&root->fs_info->alloc_mutex);
3021         ret = __btrfs_free_extent(trans, root, bytenr, blocksize,
3022                                   parent->start, root_owner, root_gen,
3023                                   *level, 1);
3024         mutex_unlock(&root->fs_info->alloc_mutex);
3025         free_extent_buffer(path->nodes[*level]);
3026         path->nodes[*level] = NULL;
3027         *level += 1;
3028         BUG_ON(ret);
3029
3030         cond_resched();
3031         return 0;
3032 }
3033
3034 /*
3035  * helper for dropping snapshots.  This walks back up the tree in the path
3036  * to find the first node higher up where we haven't yet gone through
3037  * all the slots
3038  */
3039 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
3040                                  struct btrfs_root *root,
3041                                  struct btrfs_path *path, int *level)
3042 {
3043         u64 root_owner;
3044         u64 root_gen;
3045         struct btrfs_root_item *root_item = &root->root_item;
3046         int i;
3047         int slot;
3048         int ret;
3049
3050         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
3051                 slot = path->slots[i];
3052                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
3053                         struct extent_buffer *node;
3054                         struct btrfs_disk_key disk_key;
3055                         node = path->nodes[i];
3056                         path->slots[i]++;
3057                         *level = i;
3058                         WARN_ON(*level == 0);
3059                         btrfs_node_key(node, &disk_key, path->slots[i]);
3060                         memcpy(&root_item->drop_progress,
3061                                &disk_key, sizeof(disk_key));
3062                         root_item->drop_level = i;
3063                         return 0;
3064                 } else {
3065                         struct extent_buffer *parent;
3066                         if (path->nodes[*level] == root->node)
3067                                 parent = path->nodes[*level];
3068                         else
3069                                 parent = path->nodes[*level + 1];
3070
3071                         root_owner = btrfs_header_owner(parent);
3072                         root_gen = btrfs_header_generation(parent);
3073                         ret = btrfs_free_extent(trans, root,
3074                                                 path->nodes[*level]->start,
3075                                                 path->nodes[*level]->len,
3076                                                 parent->start, root_owner,
3077                                                 root_gen, *level, 1);
3078                         BUG_ON(ret);
3079                         free_extent_buffer(path->nodes[*level]);
3080                         path->nodes[*level] = NULL;
3081                         *level = i + 1;
3082                 }
3083         }
3084         return 1;
3085 }
3086
3087 /*
3088  * drop the reference count on the tree rooted at 'snap'.  This traverses
3089  * the tree freeing any blocks that have a ref count of zero after being
3090  * decremented.
3091  */
3092 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
3093                         *root)
3094 {
3095         int ret = 0;
3096         int wret;
3097         int level;
3098         struct btrfs_path *path;
3099         int i;
3100         int orig_level;
3101         struct btrfs_root_item *root_item = &root->root_item;
3102
3103         WARN_ON(!mutex_is_locked(&root->fs_info->drop_mutex));
3104         path = btrfs_alloc_path();
3105         BUG_ON(!path);
3106
3107         level = btrfs_header_level(root->node);
3108         orig_level = level;
3109         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
3110                 path->nodes[level] = root->node;
3111                 extent_buffer_get(root->node);
3112                 path->slots[level] = 0;
3113         } else {
3114                 struct btrfs_key key;
3115                 struct btrfs_disk_key found_key;
3116                 struct extent_buffer *node;
3117
3118                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
3119                 level = root_item->drop_level;
3120                 path->lowest_level = level;
3121                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3122                 if (wret < 0) {
3123                         ret = wret;
3124                         goto out;
3125                 }
3126                 node = path->nodes[level];
3127                 btrfs_node_key(node, &found_key, path->slots[level]);
3128                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
3129                                sizeof(found_key)));
3130                 /*
3131                  * unlock our path, this is safe because only this
3132                  * function is allowed to delete this snapshot
3133                  */
3134                 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
3135                         if (path->nodes[i] && path->locks[i]) {
3136                                 path->locks[i] = 0;
3137                                 btrfs_tree_unlock(path->nodes[i]);
3138                         }
3139                 }
3140         }
3141         while(1) {
3142                 wret = walk_down_tree(trans, root, path, &level);
3143                 if (wret > 0)
3144                         break;
3145                 if (wret < 0)
3146                         ret = wret;
3147
3148                 wret = walk_up_tree(trans, root, path, &level);
3149                 if (wret > 0)
3150                         break;
3151                 if (wret < 0)
3152                         ret = wret;
3153                 if (trans->transaction->in_commit) {
3154                         ret = -EAGAIN;
3155                         break;
3156                 }
3157                 atomic_inc(&root->fs_info->throttle_gen);
3158                 wake_up(&root->fs_info->transaction_throttle);
3159         }
3160         for (i = 0; i <= orig_level; i++) {
3161                 if (path->nodes[i]) {
3162                         free_extent_buffer(path->nodes[i]);
3163                         path->nodes[i] = NULL;
3164                 }
3165         }
3166 out:
3167         btrfs_free_path(path);
3168         return ret;
3169 }
3170
3171 static unsigned long calc_ra(unsigned long start, unsigned long last,
3172                              unsigned long nr)
3173 {
3174         return min(last, start + nr - 1);
3175 }
3176
3177 static int noinline relocate_inode_pages(struct inode *inode, u64 start,
3178                                          u64 len)
3179 {
3180         u64 page_start;
3181         u64 page_end;
3182         unsigned long first_index;
3183         unsigned long last_index;
3184         unsigned long i;
3185         struct page *page;
3186         struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
3187         struct file_ra_state *ra;
3188         struct btrfs_ordered_extent *ordered;
3189         unsigned int total_read = 0;
3190         unsigned int total_dirty = 0;
3191         int ret = 0;
3192
3193         ra = kzalloc(sizeof(*ra), GFP_NOFS);
3194
3195         mutex_lock(&inode->i_mutex);
3196         first_index = start >> PAGE_CACHE_SHIFT;
3197         last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
3198
3199         /* make sure the dirty trick played by the caller work */
3200         ret = invalidate_inode_pages2_range(inode->i_mapping,
3201                                             first_index, last_index);
3202         if (ret)
3203                 goto out_unlock;
3204
3205         file_ra_state_init(ra, inode->i_mapping);
3206
3207         for (i = first_index ; i <= last_index; i++) {
3208                 if (total_read % ra->ra_pages == 0) {
3209                         btrfs_force_ra(inode->i_mapping, ra, NULL, i,
3210                                        calc_ra(i, last_index, ra->ra_pages));
3211                 }
3212                 total_read++;
3213 again:
3214                 if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
3215                         BUG_ON(1);
3216                 page = grab_cache_page(inode->i_mapping, i);
3217                 if (!page) {
3218                         ret = -ENOMEM;
3219                         goto out_unlock;
3220                 }
3221                 if (!PageUptodate(page)) {
3222                         btrfs_readpage(NULL, page);
3223                         lock_page(page);
3224                         if (!PageUptodate(page)) {
3225                                 unlock_page(page);
3226                                 page_cache_release(page);
3227                                 ret = -EIO;
3228                                 goto out_unlock;
3229                         }
3230                 }
3231                 wait_on_page_writeback(page);
3232
3233                 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
3234                 page_end = page_start + PAGE_CACHE_SIZE - 1;
3235                 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
3236
3237                 ordered = btrfs_lookup_ordered_extent(inode, page_start);
3238                 if (ordered) {
3239                         unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
3240                         unlock_page(page);
3241                         page_cache_release(page);
3242                         btrfs_start_ordered_extent(inode, ordered, 1);
3243                         btrfs_put_ordered_extent(ordered);
3244                         goto again;
3245                 }
3246                 set_page_extent_mapped(page);
3247
3248                 btrfs_set_extent_delalloc(inode, page_start, page_end);
3249                 if (i == first_index)
3250                         set_extent_bits(io_tree, page_start, page_end,
3251                                         EXTENT_BOUNDARY, GFP_NOFS);
3252
3253                 set_page_dirty(page);
3254                 total_dirty++;
3255
3256                 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
3257                 unlock_page(page);
3258                 page_cache_release(page);
3259         }
3260
3261 out_unlock:
3262         kfree(ra);
3263         mutex_unlock(&inode->i_mutex);
3264         balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
3265         return ret;
3266 }
3267
3268 static int noinline relocate_data_extent(struct inode *reloc_inode,
3269                                          struct btrfs_key *extent_key,
3270                                          u64 offset)
3271 {
3272         struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
3273         struct extent_map_tree *em_tree = &BTRFS_I(reloc_inode)->extent_tree;
3274         struct extent_map *em;
3275
3276         em = alloc_extent_map(GFP_NOFS);
3277         BUG_ON(!em || IS_ERR(em));
3278
3279         em->start = extent_key->objectid - offset;
3280         em->len = extent_key->offset;
3281         em->block_start = extent_key->objectid;
3282         em->bdev = root->fs_info->fs_devices->latest_bdev;
3283         set_bit(EXTENT_FLAG_PINNED, &em->flags);
3284
3285         /* setup extent map to cheat btrfs_readpage */
3286         mutex_lock(&BTRFS_I(reloc_inode)->extent_mutex);
3287         while (1) {
3288                 int ret;
3289                 spin_lock(&em_tree->lock);
3290                 ret = add_extent_mapping(em_tree, em);
3291                 spin_unlock(&em_tree->lock);
3292                 if (ret != -EEXIST) {
3293                         free_extent_map(em);
3294                         break;
3295                 }
3296                 btrfs_drop_extent_cache(reloc_inode, em->start,
3297                                         em->start + em->len - 1, 0);
3298         }
3299         mutex_unlock(&BTRFS_I(reloc_inode)->extent_mutex);
3300
3301         return relocate_inode_pages(reloc_inode, extent_key->objectid - offset,
3302                                     extent_key->offset);
3303 }
3304
3305 struct btrfs_ref_path {
3306         u64 extent_start;
3307         u64 nodes[BTRFS_MAX_LEVEL];
3308         u64 root_objectid;
3309         u64 root_generation;
3310         u64 owner_objectid;
3311         u32 num_refs;
3312         int lowest_level;
3313         int current_level;
3314 };
3315
3316 struct disk_extent {
3317         u64 disk_bytenr;
3318         u64 disk_num_bytes;
3319         u64 offset;
3320         u64 num_bytes;
3321 };
3322
3323 static int is_cowonly_root(u64 root_objectid)
3324 {
3325         if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
3326             root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
3327             root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
3328             root_objectid == BTRFS_DEV_TREE_OBJECTID ||
3329             root_objectid == BTRFS_TREE_LOG_OBJECTID)
3330                 return 1;
3331         return 0;
3332 }
3333
3334 static int noinline __next_ref_path(struct btrfs_trans_handle *trans,
3335                                     struct btrfs_root *extent_root,
3336                                     struct btrfs_ref_path *ref_path,
3337                                     int first_time)
3338 {
3339         struct extent_buffer *leaf;
3340         struct btrfs_path *path;
3341         struct btrfs_extent_ref *ref;
3342         struct btrfs_key key;
3343         struct btrfs_key found_key;
3344         u64 bytenr;
3345         u32 nritems;
3346         int level;
3347         int ret = 1;
3348
3349         path = btrfs_alloc_path();
3350         if (!path)
3351                 return -ENOMEM;
3352
3353         mutex_lock(&extent_root->fs_info->alloc_mutex);
3354
3355         if (first_time) {
3356                 ref_path->lowest_level = -1;
3357                 ref_path->current_level = -1;
3358                 goto walk_up;
3359         }
3360 walk_down:
3361         level = ref_path->current_level - 1;
3362         while (level >= -1) {
3363                 u64 parent;
3364                 if (level < ref_path->lowest_level)
3365                         break;
3366
3367                 if (level >= 0) {
3368                         bytenr = ref_path->nodes[level];
3369                 } else {
3370                         bytenr = ref_path->extent_start;
3371                 }
3372                 BUG_ON(bytenr == 0);
3373
3374                 parent = ref_path->nodes[level + 1];
3375                 ref_path->nodes[level + 1] = 0;
3376                 ref_path->current_level = level;
3377                 BUG_ON(parent == 0);
3378
3379                 key.objectid = bytenr;
3380                 key.offset = parent + 1;
3381                 key.type = BTRFS_EXTENT_REF_KEY;
3382
3383                 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
3384                 if (ret < 0)
3385                         goto out;
3386                 BUG_ON(ret == 0);
3387
3388                 leaf = path->nodes[0];
3389                 nritems = btrfs_header_nritems(leaf);
3390                 if (path->slots[0] >= nritems) {
3391                         ret = btrfs_next_leaf(extent_root, path);
3392                         if (ret < 0)
3393                                 goto out;
3394                         if (ret > 0)
3395                                 goto next;
3396                         leaf = path->nodes[0];
3397                 }
3398
3399                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3400                 if (found_key.objectid == bytenr &&
3401                                 found_key.type == BTRFS_EXTENT_REF_KEY)
3402                         goto found;
3403 next:
3404                 level--;
3405                 btrfs_release_path(extent_root, path);
3406                 if (need_resched()) {
3407                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
3408                         cond_resched();
3409                         mutex_lock(&extent_root->fs_info->alloc_mutex);
3410                 }
3411         }
3412         /* reached lowest level */
3413         ret = 1;
3414         goto out;
3415 walk_up:
3416         level = ref_path->current_level;
3417         while (level < BTRFS_MAX_LEVEL - 1) {
3418                 u64 ref_objectid;
3419                 if (level >= 0) {
3420                         bytenr = ref_path->nodes[level];
3421                 } else {
3422                         bytenr = ref_path->extent_start;
3423                 }
3424                 BUG_ON(bytenr == 0);
3425
3426                 key.objectid = bytenr;
3427                 key.offset = 0;
3428                 key.type = BTRFS_EXTENT_REF_KEY;
3429
3430                 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
3431                 if (ret < 0)
3432                         goto out;
3433
3434                 leaf = path->nodes[0];
3435                 nritems = btrfs_header_nritems(leaf);
3436                 if (path->slots[0] >= nritems) {
3437                         ret = btrfs_next_leaf(extent_root, path);
3438                         if (ret < 0)
3439                                 goto out;
3440                         if (ret > 0) {
3441                                 /* the extent was freed by someone */
3442                                 if (ref_path->lowest_level == level)
3443                                         goto out;
3444                                 btrfs_release_path(extent_root, path);
3445                                 goto walk_down;
3446                         }
3447                         leaf = path->nodes[0];
3448                 }
3449
3450                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3451                 if (found_key.objectid != bytenr ||
3452                                 found_key.type != BTRFS_EXTENT_REF_KEY) {
3453                         /* the extent was freed by someone */
3454                         if (ref_path->lowest_level == level) {
3455                                 ret = 1;
3456                                 goto out;
3457                         }
3458                         btrfs_release_path(extent_root, path);
3459                         goto walk_down;
3460                 }
3461 found:
3462                 ref = btrfs_item_ptr(leaf, path->slots[0],
3463                                 struct btrfs_extent_ref);
3464                 ref_objectid = btrfs_ref_objectid(leaf, ref);
3465                 if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
3466                         if (first_time) {
3467                                 level = (int)ref_objectid;
3468                                 BUG_ON(level >= BTRFS_MAX_LEVEL);
3469                                 ref_path->lowest_level = level;
3470                                 ref_path->current_level = level;
3471                                 ref_path->nodes[level] = bytenr;
3472                         } else {
3473                                 WARN_ON(ref_objectid != level);
3474                         }
3475                 } else {
3476                         WARN_ON(level != -1);
3477                 }
3478                 first_time = 0;
3479
3480                 if (ref_path->lowest_level == level) {
3481                         ref_path->owner_objectid = ref_objectid;
3482                         ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
3483                 }
3484
3485                 /*
3486                  * the block is tree root or the block isn't in reference
3487                  * counted tree.
3488                  */
3489                 if (found_key.objectid == found_key.offset ||
3490                     is_cowonly_root(btrfs_ref_root(leaf, ref))) {
3491                         ref_path->root_objectid = btrfs_ref_root(leaf, ref);
3492                         ref_path->root_generation =
3493                                 btrfs_ref_generation(leaf, ref);
3494                         if (level < 0) {
3495                                 /* special reference from the tree log */
3496                                 ref_path->nodes[0] = found_key.offset;
3497                                 ref_path->current_level = 0;
3498                         }
3499                         ret = 0;
3500                         goto out;
3501                 }
3502
3503                 level++;
3504                 BUG_ON(ref_path->nodes[level] != 0);
3505                 ref_path->nodes[level] = found_key.offset;
3506                 ref_path->current_level = level;
3507
3508                 /*
3509                  * the reference was created in the running transaction,
3510                  * no need to continue walking up.
3511                  */
3512                 if (btrfs_ref_generation(leaf, ref) == trans->transid) {
3513                         ref_path->root_objectid = btrfs_ref_root(leaf, ref);
3514                         ref_path->root_generation =
3515                                 btrfs_ref_generation(leaf, ref);
3516                         ret = 0;
3517                         goto out;
3518                 }
3519
3520                 btrfs_release_path(extent_root, path);
3521                 if (need_resched()) {
3522                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
3523                         cond_resched();
3524                         mutex_lock(&extent_root->fs_info->alloc_mutex);
3525                 }
3526         }
3527         /* reached max tree level, but no tree root found. */
3528         BUG();
3529 out:
3530         mutex_unlock(&extent_root->fs_info->alloc_mutex);
3531         btrfs_free_path(path);
3532         return ret;
3533 }
3534
3535 static int btrfs_first_ref_path(struct btrfs_trans_handle *trans,
3536                                 struct btrfs_root *extent_root,
3537                                 struct btrfs_ref_path *ref_path,
3538                                 u64 extent_start)
3539 {
3540         memset(ref_path, 0, sizeof(*ref_path));
3541         ref_path->extent_start = extent_start;
3542
3543         return __next_ref_path(trans, extent_root, ref_path, 1);
3544 }
3545
3546 static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
3547                                struct btrfs_root *extent_root,
3548                                struct btrfs_ref_path *ref_path)
3549 {
3550         return __next_ref_path(trans, extent_root, ref_path, 0);
3551 }
3552
3553 static int noinline get_new_locations(struct inode *reloc_inode,
3554                                       struct btrfs_key *extent_key,
3555                                       u64 offset, int no_fragment,
3556                                       struct disk_extent **extents,
3557                                       int *nr_extents)
3558 {
3559         struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
3560         struct btrfs_path *path;
3561         struct btrfs_file_extent_item *fi;
3562         struct extent_buffer *leaf;
3563         struct disk_extent *exts = *extents;
3564         struct btrfs_key found_key;
3565         u64 cur_pos;
3566         u64 last_byte;
3567         u32 nritems;
3568         int nr = 0;
3569         int max = *nr_extents;
3570         int ret;
3571
3572         WARN_ON(!no_fragment && *extents);
3573         if (!exts) {
3574                 max = 1;
3575                 exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
3576                 if (!exts)
3577                         return -ENOMEM;
3578         }
3579
3580         path = btrfs_alloc_path();
3581         BUG_ON(!path);
3582
3583         cur_pos = extent_key->objectid - offset;
3584         last_byte = extent_key->objectid + extent_key->offset;
3585         ret = btrfs_lookup_file_extent(NULL, root, path, reloc_inode->i_ino,
3586                                        cur_pos, 0);
3587         if (ret < 0)
3588                 goto out;
3589         if (ret > 0) {
3590                 ret = -ENOENT;
3591                 goto out;
3592         }
3593
3594         while (1) {
3595                 leaf = path->nodes[0];
3596                 nritems = btrfs_header_nritems(leaf);
3597                 if (path->slots[0] >= nritems) {
3598                         ret = btrfs_next_leaf(root, path);
3599                         if (ret < 0)
3600                                 goto out;
3601                         if (ret > 0)
3602                                 break;
3603                         leaf = path->nodes[0];
3604                 }
3605
3606                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3607                 if (found_key.offset != cur_pos ||
3608                     found_key.type != BTRFS_EXTENT_DATA_KEY ||
3609                     found_key.objectid != reloc_inode->i_ino)
3610                         break;
3611
3612                 fi = btrfs_item_ptr(leaf, path->slots[0],
3613                                     struct btrfs_file_extent_item);
3614                 if (btrfs_file_extent_type(leaf, fi) !=
3615                     BTRFS_FILE_EXTENT_REG ||
3616                     btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
3617                         break;
3618
3619                 if (nr == max) {
3620                         struct disk_extent *old = exts;
3621                         max *= 2;
3622                         exts = kzalloc(sizeof(*exts) * max, GFP_NOFS);
3623                         memcpy(exts, old, sizeof(*exts) * nr);
3624                         if (old != *extents)
3625                                 kfree(old);
3626                 }
3627
3628                 exts[nr].disk_bytenr =
3629                         btrfs_file_extent_disk_bytenr(leaf, fi);
3630                 exts[nr].disk_num_bytes =
3631                         btrfs_file_extent_disk_num_bytes(leaf, fi);
3632                 exts[nr].offset = btrfs_file_extent_offset(leaf, fi);
3633                 exts[nr].num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
3634                 WARN_ON(exts[nr].offset > 0);
3635                 WARN_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
3636
3637                 cur_pos += exts[nr].num_bytes;
3638                 nr++;
3639
3640                 if (cur_pos + offset >= last_byte)
3641                         break;
3642
3643                 if (no_fragment) {
3644                         ret = 1;
3645                         goto out;
3646                 }
3647                 path->slots[0]++;
3648         }
3649
3650         WARN_ON(cur_pos + offset > last_byte);
3651         if (cur_pos + offset < last_byte) {
3652                 ret = -ENOENT;
3653                 goto out;
3654         }
3655         ret = 0;
3656 out:
3657         btrfs_free_path(path);
3658         if (ret) {
3659                 if (exts != *extents)
3660                         kfree(exts);
3661         } else {
3662                 *extents = exts;
3663                 *nr_extents = nr;
3664         }
3665         return ret;
3666 }
3667
3668 static int noinline replace_one_extent(struct btrfs_trans_handle *trans,
3669                                         struct btrfs_root *root,
3670                                         struct btrfs_path *path,
3671                                         struct btrfs_key *extent_key,
3672                                         struct btrfs_key *leaf_key,
3673                                         struct btrfs_ref_path *ref_path,
3674                                         struct disk_extent *new_extents,
3675                                         int nr_extents)
3676 {
3677         struct extent_buffer *leaf;
3678         struct btrfs_file_extent_item *fi;
3679         struct inode *inode = NULL;
3680         struct btrfs_key key;
3681         u64 lock_start = 0;
3682         u64 lock_end = 0;
3683         u64 num_bytes;
3684         u64 ext_offset;
3685         u64 first_pos;
3686         u32 nritems;
3687         int nr_scaned = 0;
3688         int extent_locked = 0;
3689         int ret;
3690
3691         memcpy(&key, leaf_key, sizeof(key));
3692         first_pos = INT_LIMIT(loff_t) - extent_key->offset;
3693         if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
3694                 if (key.objectid < ref_path->owner_objectid ||
3695                     (key.objectid == ref_path->owner_objectid &&
3696                      key.type < BTRFS_EXTENT_DATA_KEY)) {
3697                         key.objectid = ref_path->owner_objectid;
3698                         key.type = BTRFS_EXTENT_DATA_KEY;
3699                         key.offset = 0;
3700                 }
3701         }
3702
3703         while (1) {
3704                 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
3705                 if (ret < 0)
3706                         goto out;
3707
3708                 leaf = path->nodes[0];
3709                 nritems = btrfs_header_nritems(leaf);
3710 next:
3711                 if (extent_locked && ret > 0) {
3712                         /*
3713                          * the file extent item was modified by someone
3714                          * before the extent got locked.
3715                          */
3716                         mutex_unlock(&BTRFS_I(inode)->extent_mutex);
3717                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
3718                                       lock_end, GFP_NOFS);
3719                         extent_locked = 0;
3720                 }
3721
3722                 if (path->slots[0] >= nritems) {
3723                         if (++nr_scaned > 2)
3724                                 break;
3725
3726                         BUG_ON(extent_locked);
3727                         ret = btrfs_next_leaf(root, path);
3728                         if (ret < 0)
3729                                 goto out;
3730                         if (ret > 0)
3731                                 break;
3732                         leaf = path->nodes[0];
3733                         nritems = btrfs_header_nritems(leaf);
3734                 }
3735
3736                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3737
3738                 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
3739                         if ((key.objectid > ref_path->owner_objectid) ||
3740                             (key.objectid == ref_path->owner_objectid &&
3741                              key.type > BTRFS_EXTENT_DATA_KEY) ||
3742                             (key.offset >= first_pos + extent_key->offset))
3743                                 break;
3744                 }
3745
3746                 if (inode && key.objectid != inode->i_ino) {
3747                         BUG_ON(extent_locked);
3748                         btrfs_release_path(root, path);
3749                         mutex_unlock(&inode->i_mutex);
3750                         iput(inode);
3751                         inode = NULL;
3752                         continue;
3753                 }
3754
3755                 if (key.type != BTRFS_EXTENT_DATA_KEY) {
3756                         path->slots[0]++;
3757                         ret = 1;
3758                         goto next;
3759                 }
3760                 fi = btrfs_item_ptr(leaf, path->slots[0],
3761                                     struct btrfs_file_extent_item);
3762                 if ((btrfs_file_extent_type(leaf, fi) !=
3763                      BTRFS_FILE_EXTENT_REG) ||
3764                     (btrfs_file_extent_disk_bytenr(leaf, fi) !=
3765                      extent_key->objectid)) {
3766                         path->slots[0]++;
3767                         ret = 1;
3768                         goto next;
3769                 }
3770
3771                 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
3772                 ext_offset = btrfs_file_extent_offset(leaf, fi);
3773
3774                 if (first_pos > key.offset - ext_offset)
3775                         first_pos = key.offset - ext_offset;
3776
3777                 if (!extent_locked) {
3778                         lock_start = key.offset;
3779                         lock_end = lock_start + num_bytes - 1;
3780                 } else {
3781                         BUG_ON(lock_start != key.offset);
3782                         BUG_ON(lock_end - lock_start + 1 < num_bytes);
3783                 }
3784
3785                 if (!inode) {
3786                         btrfs_release_path(root, path);
3787
3788                         inode = btrfs_iget_locked(root->fs_info->sb,
3789                                                   key.objectid, root);
3790                         if (inode->i_state & I_NEW) {
3791                                 BTRFS_I(inode)->root = root;
3792                                 BTRFS_I(inode)->location.objectid =
3793                                         key.objectid;
3794                                 BTRFS_I(inode)->location.type =
3795                                         BTRFS_INODE_ITEM_KEY;
3796                                 BTRFS_I(inode)->location.offset = 0;
3797                                 btrfs_read_locked_inode(inode);
3798                                 unlock_new_inode(inode);
3799                         }
3800                         /*
3801                          * some code call btrfs_commit_transaction while
3802                          * holding the i_mutex, so we can't use mutex_lock
3803                          * here.
3804                          */
3805                         if (is_bad_inode(inode) ||
3806                             !mutex_trylock(&inode->i_mutex)) {
3807                                 iput(inode);
3808                                 inode = NULL;
3809                                 key.offset = (u64)-1;
3810                                 goto skip;
3811                         }
3812                 }
3813
3814                 if (!extent_locked) {
3815                         struct btrfs_ordered_extent *ordered;
3816
3817                         btrfs_release_path(root, path);
3818
3819                         lock_extent(&BTRFS_I(inode)->io_tree, lock_start,
3820                                     lock_end, GFP_NOFS);
3821                         ordered = btrfs_lookup_first_ordered_extent(inode,
3822                                                                     lock_end);
3823                         if (ordered &&
3824                             ordered->file_offset <= lock_end &&
3825                             ordered->file_offset + ordered->len > lock_start) {
3826                                 unlock_extent(&BTRFS_I(inode)->io_tree,
3827                                               lock_start, lock_end, GFP_NOFS);
3828                                 btrfs_start_ordered_extent(inode, ordered, 1);
3829                                 btrfs_put_ordered_extent(ordered);
3830                                 key.offset += num_bytes;
3831                                 goto skip;
3832                         }
3833                         if (ordered)
3834                                 btrfs_put_ordered_extent(ordered);
3835
3836                         mutex_lock(&BTRFS_I(inode)->extent_mutex);
3837                         extent_locked = 1;
3838                         continue;
3839                 }
3840
3841                 if (nr_extents == 1) {
3842                         /* update extent pointer in place */
3843                         btrfs_set_file_extent_generation(leaf, fi,
3844                                                 trans->transid);
3845                         btrfs_set_file_extent_disk_bytenr(leaf, fi,
3846                                                 new_extents[0].disk_bytenr);
3847                         btrfs_set_file_extent_disk_num_bytes(leaf, fi,
3848                                                 new_extents[0].disk_num_bytes);
3849                         ext_offset += new_extents[0].offset;
3850                         btrfs_set_file_extent_offset(leaf, fi, ext_offset);
3851                         btrfs_mark_buffer_dirty(leaf);
3852
3853                         btrfs_drop_extent_cache(inode, key.offset,
3854                                                 key.offset + num_bytes - 1, 0);
3855
3856                         ret = btrfs_inc_extent_ref(trans, root,
3857                                                 new_extents[0].disk_bytenr,
3858                                                 new_extents[0].disk_num_bytes,
3859                                                 leaf->start,
3860                                                 root->root_key.objectid,
3861                                                 trans->transid,
3862                                                 key.objectid);
3863                         BUG_ON(ret);
3864
3865                         ret = btrfs_free_extent(trans, root,
3866                                                 extent_key->objectid,
3867                                                 extent_key->offset,
3868                                                 leaf->start,
3869                                                 btrfs_header_owner(leaf),
3870                                                 btrfs_header_generation(leaf),
3871                                                 key.objectid, 0);
3872                         BUG_ON(ret);
3873
3874                         btrfs_release_path(root, path);
3875                         key.offset += num_bytes;
3876                 } else {
3877                         u64 alloc_hint;
3878                         u64 extent_len;
3879                         int i;
3880                         /*
3881                          * drop old extent pointer at first, then insert the
3882                          * new pointers one bye one
3883                          */
3884                         btrfs_release_path(root, path);
3885                         ret = btrfs_drop_extents(trans, root, inode, key.offset,
3886                                                  key.offset + num_bytes,
3887                                                  key.offset, &alloc_hint);
3888                         BUG_ON(ret);
3889
3890                         for (i = 0; i < nr_extents; i++) {
3891                                 if (ext_offset >= new_extents[i].num_bytes) {
3892                                         ext_offset -= new_extents[i].num_bytes;
3893                                         continue;
3894                                 }
3895                                 extent_len = min(new_extents[i].num_bytes -
3896                                                  ext_offset, num_bytes);
3897
3898                                 ret = btrfs_insert_empty_item(trans, root,
3899                                                               path, &key,
3900                                                               sizeof(*fi));
3901                                 BUG_ON(ret);
3902
3903                                 leaf = path->nodes[0];
3904                                 fi = btrfs_item_ptr(leaf, path->slots[0],
3905                                                 struct btrfs_file_extent_item);
3906                                 btrfs_set_file_extent_generation(leaf, fi,
3907                                                         trans->transid);
3908                                 btrfs_set_file_extent_type(leaf, fi,
3909                                                         BTRFS_FILE_EXTENT_REG);
3910                                 btrfs_set_file_extent_disk_bytenr(leaf, fi,
3911                                                 new_extents[i].disk_bytenr);
3912                                 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
3913                                                 new_extents[i].disk_num_bytes);
3914                                 btrfs_set_file_extent_num_bytes(leaf, fi,
3915                                                         extent_len);
3916                                 ext_offset += new_extents[i].offset;
3917                                 btrfs_set_file_extent_offset(leaf, fi,
3918                                                         ext_offset);
3919                                 btrfs_mark_buffer_dirty(leaf);
3920
3921                                 btrfs_drop_extent_cache(inode, key.offset,
3922                                                 key.offset + extent_len - 1, 0);
3923
3924                                 ret = btrfs_inc_extent_ref(trans, root,
3925                                                 new_extents[i].disk_bytenr,
3926                                                 new_extents[i].disk_num_bytes,
3927                                                 leaf->start,
3928                                                 root->root_key.objectid,
3929                                                 trans->transid, key.objectid);
3930                                 BUG_ON(ret);
3931                                 btrfs_release_path(root, path);
3932
3933                                 inode_add_bytes(inode, extent_len);
3934
3935                                 ext_offset = 0;
3936                                 num_bytes -= extent_len;
3937                                 key.offset += extent_len;
3938
3939                                 if (num_bytes == 0)
3940                                         break;
3941                         }
3942                         BUG_ON(i >= nr_extents);
3943                 }
3944
3945                 if (extent_locked) {
3946                         mutex_unlock(&BTRFS_I(inode)->extent_mutex);
3947                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
3948                                       lock_end, GFP_NOFS);
3949                         extent_locked = 0;
3950                 }
3951 skip:
3952                 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS &&
3953                     key.offset >= first_pos + extent_key->offset)
3954                         break;
3955
3956                 cond_resched();
3957         }
3958         ret = 0;
3959 out:
3960         btrfs_release_path(root, path);
3961         if (inode) {
3962                 mutex_unlock(&inode->i_mutex);
3963                 if (extent_locked) {
3964                         mutex_unlock(&BTRFS_I(inode)->extent_mutex);
3965                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
3966                                       lock_end, GFP_NOFS);
3967                 }
3968                 iput(inode);
3969         }
3970         return ret;
3971 }
3972
3973 int btrfs_add_reloc_mapping(struct btrfs_root *root, u64 orig_bytenr,
3974                             u64 num_bytes, u64 new_bytenr)
3975 {
3976         set_extent_bits(&root->fs_info->reloc_mapping_tree,
3977                         orig_bytenr, orig_bytenr + num_bytes - 1,
3978                         EXTENT_LOCKED, GFP_NOFS);
3979         set_state_private(&root->fs_info->reloc_mapping_tree,
3980                           orig_bytenr, new_bytenr);
3981         return 0;
3982 }
3983
3984 int btrfs_get_reloc_mapping(struct btrfs_root *root, u64 orig_bytenr,
3985                             u64 num_bytes, u64 *new_bytenr)
3986 {
3987         u64 bytenr;
3988         u64 cur_bytenr = orig_bytenr;
3989         u64 prev_bytenr = orig_bytenr;
3990         int ret;
3991
3992         while (1) {
3993                 ret = get_state_private(&root->fs_info->reloc_mapping_tree,
3994                                         cur_bytenr, &bytenr);
3995                 if (ret)
3996                         break;
3997                 prev_bytenr = cur_bytenr;
3998                 cur_bytenr = bytenr;
3999         }
4000
4001         if (orig_bytenr == cur_bytenr)
4002                 return -ENOENT;
4003
4004         if (prev_bytenr != orig_bytenr) {
4005                 set_state_private(&root->fs_info->reloc_mapping_tree,
4006                                   orig_bytenr, cur_bytenr);
4007         }
4008         *new_bytenr = cur_bytenr;
4009         return 0;
4010 }
4011
4012 void btrfs_free_reloc_mappings(struct btrfs_root *root)
4013 {
4014         clear_extent_bits(&root->fs_info->reloc_mapping_tree,
4015                           0, (u64)-1, -1, GFP_NOFS);
4016 }
4017
4018 int btrfs_reloc_tree_cache_ref(struct btrfs_trans_handle *trans,
4019                                struct btrfs_root *root,
4020                                struct extent_buffer *buf, u64 orig_start)
4021 {
4022         int level;
4023         int ret;
4024
4025         BUG_ON(btrfs_header_generation(buf) != trans->transid);
4026         BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
4027
4028         level = btrfs_header_level(buf);
4029         if (level == 0) {
4030                 struct btrfs_leaf_ref *ref;
4031                 struct btrfs_leaf_ref *orig_ref;
4032
4033                 orig_ref = btrfs_lookup_leaf_ref(root, orig_start);
4034                 if (!orig_ref)
4035                         return -ENOENT;
4036
4037                 ref = btrfs_alloc_leaf_ref(root, orig_ref->nritems);
4038                 if (!ref) {
4039                         btrfs_free_leaf_ref(root, orig_ref);
4040                         return -ENOMEM;
4041                 }
4042
4043                 ref->nritems = orig_ref->nritems;
4044                 memcpy(ref->extents, orig_ref->extents,
4045                         sizeof(ref->extents[0]) * ref->nritems);
4046
4047                 btrfs_free_leaf_ref(root, orig_ref);
4048
4049                 ref->root_gen = trans->transid;
4050                 ref->bytenr = buf->start;
4051                 ref->owner = btrfs_header_owner(buf);
4052                 ref->generation = btrfs_header_generation(buf);
4053                 ret = btrfs_add_leaf_ref(root, ref, 0);
4054                 WARN_ON(ret);
4055                 btrfs_free_leaf_ref(root, ref);
4056         }
4057         return 0;
4058 }
4059
4060 static int noinline invalidate_extent_cache(struct btrfs_root *root,
4061                                         struct extent_buffer *leaf,
4062                                         struct btrfs_block_group_cache *group,
4063                                         struct btrfs_root *target_root)
4064 {
4065         struct btrfs_key key;
4066         struct inode *inode = NULL;
4067         struct btrfs_file_extent_item *fi;
4068         u64 num_bytes;
4069         u64 skip_objectid = 0;
4070         u32 nritems;
4071         u32 i;
4072
4073         nritems = btrfs_header_nritems(leaf);
4074         for (i = 0; i < nritems; i++) {
4075                 btrfs_item_key_to_cpu(leaf, &key, i);
4076                 if (key.objectid == skip_objectid ||
4077                     key.type != BTRFS_EXTENT_DATA_KEY)
4078                         continue;
4079                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4080                 if (btrfs_file_extent_type(leaf, fi) ==
4081                     BTRFS_FILE_EXTENT_INLINE)
4082                         continue;
4083                 if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
4084                         continue;
4085                 if (!inode || inode->i_ino != key.objectid) {
4086                         iput(inode);
4087                         inode = btrfs_ilookup(target_root->fs_info->sb,
4088                                               key.objectid, target_root, 1);
4089                 }
4090                 if (!inode) {
4091                         skip_objectid = key.objectid;
4092                         continue;
4093                 }
4094                 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
4095
4096                 lock_extent(&BTRFS_I(inode)->io_tree, key.offset,
4097                             key.offset + num_bytes - 1, GFP_NOFS);
4098                 mutex_lock(&BTRFS_I(inode)->extent_mutex);
4099                 btrfs_drop_extent_cache(inode, key.offset,
4100                                         key.offset + num_bytes - 1, 1);
4101                 mutex_unlock(&BTRFS_I(inode)->extent_mutex);
4102                 unlock_extent(&BTRFS_I(inode)->io_tree, key.offset,
4103                               key.offset + num_bytes - 1, GFP_NOFS);
4104                 cond_resched();
4105         }
4106         iput(inode);
4107         return 0;
4108 }
4109
4110 static int noinline replace_extents_in_leaf(struct btrfs_trans_handle *trans,
4111                                         struct btrfs_root *root,
4112                                         struct extent_buffer *leaf,
4113                                         struct btrfs_block_group_cache *group,
4114                                         struct inode *reloc_inode)
4115 {
4116         struct btrfs_key key;
4117         struct btrfs_key extent_key;
4118         struct btrfs_file_extent_item *fi;
4119         struct btrfs_leaf_ref *ref;
4120         struct disk_extent *new_extent;
4121         u64 bytenr;
4122         u64 num_bytes;
4123         u32 nritems;
4124         u32 i;
4125         int ext_index;
4126         int nr_extent;
4127         int ret;
4128
4129         new_extent = kmalloc(sizeof(*new_extent), GFP_NOFS);
4130         BUG_ON(!new_extent);
4131
4132         ref = btrfs_lookup_leaf_ref(root, leaf->start);
4133         BUG_ON(!ref);
4134
4135         ext_index = -1;
4136         nritems = btrfs_header_nritems(leaf);
4137         for (i = 0; i < nritems; i++) {
4138                 btrfs_item_key_to_cpu(leaf, &key, i);
4139                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
4140                         continue;
4141                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4142                 if (btrfs_file_extent_type(leaf, fi) ==
4143                     BTRFS_FILE_EXTENT_INLINE)
4144                         continue;
4145                 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
4146                 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
4147                 if (bytenr == 0)
4148                         continue;
4149
4150                 ext_index++;
4151                 if (bytenr >= group->key.objectid + group->key.offset ||
4152                     bytenr + num_bytes <= group->key.objectid)
4153                         continue;
4154
4155                 extent_key.objectid = bytenr;
4156                 extent_key.offset = num_bytes;
4157                 extent_key.type = BTRFS_EXTENT_ITEM_KEY;
4158                 nr_extent = 1;
4159                 ret = get_new_locations(reloc_inode, &extent_key,
4160                                         group->key.objectid, 1,
4161                                         &new_extent, &nr_extent);
4162                 if (ret > 0)
4163                         continue;
4164                 BUG_ON(ret < 0);
4165
4166                 BUG_ON(ref->extents[ext_index].bytenr != bytenr);
4167                 BUG_ON(ref->extents[ext_index].num_bytes != num_bytes);
4168                 ref->extents[ext_index].bytenr = new_extent->disk_bytenr;
4169                 ref->extents[ext_index].num_bytes = new_extent->disk_num_bytes;
4170
4171                 btrfs_set_file_extent_generation(leaf, fi, trans->transid);
4172                 btrfs_set_file_extent_disk_bytenr(leaf, fi,
4173                                                 new_extent->disk_bytenr);
4174                 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
4175                                                 new_extent->disk_num_bytes);
4176                 new_extent->offset += btrfs_file_extent_offset(leaf, fi);
4177                 btrfs_set_file_extent_offset(leaf, fi, new_extent->offset);
4178                 btrfs_mark_buffer_dirty(leaf);
4179
4180                 ret = btrfs_inc_extent_ref(trans, root,
4181                                         new_extent->disk_bytenr,
4182                                         new_extent->disk_num_bytes,
4183                                         leaf->start,
4184                                         root->root_key.objectid,
4185                                         trans->transid, key.objectid);
4186                 BUG_ON(ret);
4187                 ret = btrfs_free_extent(trans, root,
4188                                         bytenr, num_bytes, leaf->start,
4189                                         btrfs_header_owner(leaf),
4190                                         btrfs_header_generation(leaf),
4191                                         key.objectid, 0);
4192                 BUG_ON(ret);
4193                 cond_resched();
4194         }
4195         kfree(new_extent);
4196         BUG_ON(ext_index + 1 != ref->nritems);
4197         btrfs_free_leaf_ref(root, ref);
4198         return 0;
4199 }
4200
4201 int btrfs_free_reloc_root(struct btrfs_root *root)
4202 {
4203         struct btrfs_root *reloc_root;
4204
4205         if (root->reloc_root) {
4206                 reloc_root = root->reloc_root;
4207                 root->reloc_root = NULL;
4208                 list_add(&reloc_root->dead_list,
4209                          &root->fs_info->dead_reloc_roots);
4210         }
4211         return 0;
4212 }
4213
4214 int btrfs_drop_dead_reloc_roots(struct btrfs_root *root)
4215 {
4216         struct btrfs_trans_handle *trans;
4217         struct btrfs_root *reloc_root;
4218         struct btrfs_root *prev_root = NULL;
4219         struct list_head dead_roots;
4220         int ret;
4221         unsigned long nr;
4222
4223         INIT_LIST_HEAD(&dead_roots);
4224         list_splice_init(&root->fs_info->dead_reloc_roots, &dead_roots);
4225
4226         while (!list_empty(&dead_roots)) {
4227                 reloc_root = list_entry(dead_roots.prev,
4228                                         struct btrfs_root, dead_list);
4229                 list_del_init(&reloc_root->dead_list);
4230
4231                 BUG_ON(reloc_root->commit_root != NULL);
4232                 while (1) {
4233                         trans = btrfs_join_transaction(root, 1);
4234                         BUG_ON(!trans);
4235
4236                         mutex_lock(&root->fs_info->drop_mutex);
4237                         ret = btrfs_drop_snapshot(trans, reloc_root);
4238                         if (ret != -EAGAIN)
4239                                 break;
4240                         mutex_unlock(&root->fs_info->drop_mutex);
4241
4242                         nr = trans->blocks_used;
4243                         ret = btrfs_end_transaction(trans, root);
4244                         BUG_ON(ret);
4245                         btrfs_btree_balance_dirty(root, nr);
4246                 }
4247
4248                 free_extent_buffer(reloc_root->node);
4249
4250                 ret = btrfs_del_root(trans, root->fs_info->tree_root,
4251                                      &reloc_root->root_key);
4252                 BUG_ON(ret);
4253                 mutex_unlock(&root->fs_info->drop_mutex);
4254
4255                 nr = trans->blocks_used;
4256                 ret = btrfs_end_transaction(trans, root);
4257                 BUG_ON(ret);
4258                 btrfs_btree_balance_dirty(root, nr);
4259
4260                 kfree(prev_root);
4261                 prev_root = reloc_root;
4262         }
4263         if (prev_root) {
4264                 btrfs_remove_leaf_refs(prev_root, (u64)-1, 0);
4265                 kfree(prev_root);
4266         }
4267         return 0;
4268 }
4269
4270 int btrfs_add_dead_reloc_root(struct btrfs_root *root)
4271 {
4272         list_add(&root->dead_list, &root->fs_info->dead_reloc_roots);
4273         return 0;
4274 }
4275
4276 int btrfs_cleanup_reloc_trees(struct btrfs_root *root)
4277 {
4278         struct btrfs_root *reloc_root;
4279         struct btrfs_trans_handle *trans;
4280         struct btrfs_key location;
4281         int found;
4282         int ret;
4283
4284         mutex_lock(&root->fs_info->tree_reloc_mutex);
4285         ret = btrfs_find_dead_roots(root, BTRFS_TREE_RELOC_OBJECTID, NULL);
4286         BUG_ON(ret);
4287         found = !list_empty(&root->fs_info->dead_reloc_roots);
4288         mutex_unlock(&root->fs_info->tree_reloc_mutex);
4289
4290         if (found) {
4291                 trans = btrfs_start_transaction(root, 1);
4292                 BUG_ON(!trans);
4293                 ret = btrfs_commit_transaction(trans, root);
4294                 BUG_ON(ret);
4295         }
4296
4297         location.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
4298         location.offset = (u64)-1;
4299         location.type = BTRFS_ROOT_ITEM_KEY;
4300
4301         reloc_root = btrfs_read_fs_root_no_name(root->fs_info, &location);
4302         BUG_ON(!reloc_root);
4303         btrfs_orphan_cleanup(reloc_root);
4304         return 0;
4305 }
4306
4307 static int noinline init_reloc_tree(struct btrfs_trans_handle *trans,
4308                                     struct btrfs_root *root)
4309 {
4310         struct btrfs_root *reloc_root;
4311         struct extent_buffer *eb;
4312         struct btrfs_root_item *root_item;
4313         struct btrfs_key root_key;
4314         int ret;
4315
4316         BUG_ON(!root->ref_cows);
4317         if (root->reloc_root)
4318                 return 0;
4319
4320         root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
4321         BUG_ON(!root_item);
4322
4323         ret = btrfs_copy_root(trans, root, root->commit_root,
4324                               &eb, BTRFS_TREE_RELOC_OBJECTID);
4325         BUG_ON(ret);
4326
4327         root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
4328         root_key.offset = root->root_key.objectid;
4329         root_key.type = BTRFS_ROOT_ITEM_KEY;
4330
4331         memcpy(root_item, &root->root_item, sizeof(root_item));
4332         btrfs_set_root_refs(root_item, 0);
4333         btrfs_set_root_bytenr(root_item, eb->start);
4334         btrfs_set_root_level(root_item, btrfs_header_level(eb));
4335         memset(&root_item->drop_progress, 0, sizeof(root_item->drop_progress));
4336         root_item->drop_level = 0;
4337
4338         btrfs_tree_unlock(eb);
4339         free_extent_buffer(eb);
4340
4341         ret = btrfs_insert_root(trans, root->fs_info->tree_root,
4342                                 &root_key, root_item);
4343         BUG_ON(ret);
4344         kfree(root_item);
4345
4346         reloc_root = btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
4347                                                  &root_key);
4348         BUG_ON(!reloc_root);
4349         reloc_root->last_trans = trans->transid;
4350         reloc_root->commit_root = NULL;
4351         reloc_root->ref_tree = &root->fs_info->reloc_ref_tree;
4352
4353         root->reloc_root = reloc_root;
4354         return 0;
4355 }
4356
4357 /*
4358  * Core function of space balance.
4359  *
4360  * The idea is using reloc trees to relocate tree blocks in reference
4361  * counted roots. There is one reloc tree for each subvol, all reloc
4362  * trees share same key objectid. Reloc trees are snapshots of the
4363  * latest committed roots (subvol root->commit_root). To relocate a tree
4364  * block referenced by a subvol, the code COW the block through the reloc
4365  * tree, then update pointer in the subvol to point to the new block.
4366  * Since all reloc trees share same key objectid, we can easily do special
4367  * handing to share tree blocks between reloc trees. Once a tree block has
4368  * been COWed in one reloc tree, we can use the result when the same block
4369  * is COWed again through other reloc trees.
4370  */
4371 static int noinline relocate_one_path(struct btrfs_trans_handle *trans,
4372                                       struct btrfs_root *root,
4373                                       struct btrfs_path *path,
4374                                       struct btrfs_key *first_key,
4375                                       struct btrfs_ref_path *ref_path,
4376                                       struct btrfs_block_group_cache *group,
4377                                       struct inode *reloc_inode)
4378 {
4379         struct btrfs_root *reloc_root;
4380         struct extent_buffer *eb = NULL;
4381         struct btrfs_key *keys;
4382         u64 *nodes;
4383         int level;
4384         int lowest_merge;
4385         int lowest_level = 0;
4386         int update_refs;
4387         int ret;
4388
4389         if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
4390                 lowest_level = ref_path->owner_objectid;
4391
4392         if (is_cowonly_root(ref_path->root_objectid)) {
4393                 path->lowest_level = lowest_level;
4394                 ret = btrfs_search_slot(trans, root, first_key, path, 0, 1);
4395                 BUG_ON(ret < 0);
4396                 path->lowest_level = 0;
4397                 btrfs_release_path(root, path);
4398                 return 0;
4399         }
4400
4401         keys = kzalloc(sizeof(*keys) * BTRFS_MAX_LEVEL, GFP_NOFS);
4402         BUG_ON(!keys);
4403         nodes = kzalloc(sizeof(*nodes) * BTRFS_MAX_LEVEL, GFP_NOFS);
4404         BUG_ON(!nodes);
4405
4406         mutex_lock(&root->fs_info->tree_reloc_mutex);
4407         ret = init_reloc_tree(trans, root);
4408         BUG_ON(ret);
4409         reloc_root = root->reloc_root;
4410
4411         path->lowest_level = lowest_level;
4412         ret = btrfs_search_slot(trans, reloc_root, first_key, path, 0, 0);
4413         BUG_ON(ret);
4414         /*
4415          * get relocation mapping for tree blocks in the path
4416          */
4417         lowest_merge = BTRFS_MAX_LEVEL;
4418         for (level = BTRFS_MAX_LEVEL - 1; level >= lowest_level; level--) {
4419                 u64 new_bytenr;
4420                 eb = path->nodes[level];
4421                 if (!eb || eb == reloc_root->node)
4422                         continue;
4423                 ret = btrfs_get_reloc_mapping(reloc_root, eb->start, eb->len,
4424                                               &new_bytenr);
4425                 if (ret)
4426                         continue;
4427                 if (level == 0)
4428                         btrfs_item_key_to_cpu(eb, &keys[level], 0);
4429                 else
4430                         btrfs_node_key_to_cpu(eb, &keys[level], 0);
4431                 nodes[level] = new_bytenr;
4432                 lowest_merge = level;
4433         }
4434
4435         update_refs = 0;
4436         if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
4437                 eb = path->nodes[0];
4438                 if (btrfs_header_generation(eb) < trans->transid)
4439                         update_refs = 1;
4440         }
4441
4442         btrfs_release_path(reloc_root, path);
4443         /*
4444          * merge tree blocks that already relocated in other reloc trees
4445          */
4446         if (lowest_merge != BTRFS_MAX_LEVEL) {
4447                 ret = btrfs_merge_path(trans, reloc_root, keys, nodes,
4448                                        lowest_merge);
4449                 BUG_ON(ret < 0);
4450         }
4451         /*
4452          * cow any tree blocks that still haven't been relocated
4453          */
4454         ret = btrfs_search_slot(trans, reloc_root, first_key, path, 0, 1);
4455         BUG_ON(ret);
4456         /*
4457          * if we are relocating data block group, update extent pointers
4458          * in the newly created tree leaf.
4459          */
4460         eb = path->nodes[0];
4461         if (update_refs && nodes[0] != eb->start) {
4462                 ret = replace_extents_in_leaf(trans, reloc_root, eb, group,
4463                                               reloc_inode);
4464                 BUG_ON(ret);
4465         }
4466
4467         memset(keys, 0, sizeof(*keys) * BTRFS_MAX_LEVEL);
4468         memset(nodes, 0, sizeof(*nodes) * BTRFS_MAX_LEVEL);
4469         for (level = BTRFS_MAX_LEVEL - 1; level >= lowest_level; level--) {
4470                 eb = path->nodes[level];
4471                 if (!eb || eb == reloc_root->node)
4472                         continue;
4473                 BUG_ON(btrfs_header_owner(eb) != BTRFS_TREE_RELOC_OBJECTID);
4474                 nodes[level] = eb->start;
4475                 if (level == 0)
4476                         btrfs_item_key_to_cpu(eb, &keys[level], 0);
4477                 else
4478                         btrfs_node_key_to_cpu(eb, &keys[level], 0);
4479         }
4480
4481         if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
4482                 eb = path->nodes[0];
4483                 extent_buffer_get(eb);
4484         }
4485         btrfs_release_path(reloc_root, path);
4486         /*
4487          * replace tree blocks in the fs tree with tree blocks in
4488          * the reloc tree.
4489          */
4490         ret = btrfs_merge_path(trans, root, keys, nodes, lowest_level);
4491         BUG_ON(ret < 0);
4492
4493         if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
4494                 ret = invalidate_extent_cache(reloc_root, eb, group, root);
4495                 BUG_ON(ret);
4496                 free_extent_buffer(eb);
4497         }
4498         mutex_unlock(&root->fs_info->tree_reloc_mutex);
4499
4500         path->lowest_level = 0;
4501         kfree(nodes);
4502         kfree(keys);
4503         return 0;
4504 }
4505
4506 static int noinline relocate_tree_block(struct btrfs_trans_handle *trans,
4507                                         struct btrfs_root *root,
4508                                         struct btrfs_path *path,
4509                                         struct btrfs_key *first_key,
4510                                         struct btrfs_ref_path *ref_path)
4511 {
4512         int ret;
4513         int needs_lock = 0;
4514
4515         if (root == root->fs_info->extent_root ||
4516             root == root->fs_info->chunk_root ||
4517             root == root->fs_info->dev_root) {
4518                 needs_lock = 1;
4519                 mutex_lock(&root->fs_info->alloc_mutex);
4520         }
4521
4522         ret = relocate_one_path(trans, root, path, first_key,
4523                                 ref_path, NULL, NULL);
4524         BUG_ON(ret);
4525
4526         if (root == root->fs_info->extent_root)
4527                 btrfs_extent_post_op(trans, root);
4528         if (needs_lock)
4529                 mutex_unlock(&root->fs_info->alloc_mutex);
4530
4531         return 0;
4532 }
4533
4534 static int noinline del_extent_zero(struct btrfs_trans_handle *trans,
4535                                     struct btrfs_root *extent_root,
4536                                     struct btrfs_path *path,
4537                                     struct btrfs_key *extent_key)
4538 {
4539         int ret;
4540
4541         mutex_lock(&extent_root->fs_info->alloc_mutex);
4542         ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
4543         if (ret)
4544                 goto out;
4545         ret = btrfs_del_item(trans, extent_root, path);
4546 out:
4547         btrfs_release_path(extent_root, path);
4548         mutex_unlock(&extent_root->fs_info->alloc_mutex);
4549         return ret;
4550 }
4551
4552 static struct btrfs_root noinline *read_ref_root(struct btrfs_fs_info *fs_info,
4553                                                 struct btrfs_ref_path *ref_path)
4554 {
4555         struct btrfs_key root_key;
4556
4557         root_key.objectid = ref_path->root_objectid;
4558         root_key.type = BTRFS_ROOT_ITEM_KEY;
4559         if (is_cowonly_root(ref_path->root_objectid))
4560                 root_key.offset = 0;
4561         else
4562                 root_key.offset = (u64)-1;
4563
4564         return btrfs_read_fs_root_no_name(fs_info, &root_key);
4565 }
4566
4567 static int noinline relocate_one_extent(struct btrfs_root *extent_root,
4568                                         struct btrfs_path *path,
4569                                         struct btrfs_key *extent_key,
4570                                         struct btrfs_block_group_cache *group,
4571                                         struct inode *reloc_inode, int pass)
4572 {
4573         struct btrfs_trans_handle *trans;
4574         struct btrfs_root *found_root;
4575         struct btrfs_ref_path *ref_path = NULL;
4576         struct disk_extent *new_extents = NULL;
4577         int nr_extents = 0;
4578         int loops;
4579         int ret;
4580         int level;
4581         struct btrfs_key first_key;
4582         u64 prev_block = 0;
4583
4584         mutex_unlock(&extent_root->fs_info->alloc_mutex);
4585
4586         trans = btrfs_start_transaction(extent_root, 1);
4587         BUG_ON(!trans);
4588
4589         if (extent_key->objectid == 0) {
4590                 ret = del_extent_zero(trans, extent_root, path, extent_key);
4591                 goto out;
4592         }
4593
4594         ref_path = kmalloc(sizeof(*ref_path), GFP_NOFS);
4595         if (!ref_path) {
4596                ret = -ENOMEM;
4597                goto out;
4598         }
4599
4600         for (loops = 0; ; loops++) {
4601                 if (loops == 0) {
4602                         ret = btrfs_first_ref_path(trans, extent_root, ref_path,
4603                                                    extent_key->objectid);
4604                 } else {
4605                         ret = btrfs_next_ref_path(trans, extent_root, ref_path);
4606                 }
4607                 if (ret < 0)
4608                         goto out;
4609                 if (ret > 0)
4610                         break;
4611
4612                 if (ref_path->root_objectid == BTRFS_TREE_LOG_OBJECTID ||
4613                     ref_path->root_objectid == BTRFS_TREE_RELOC_OBJECTID)
4614                         continue;
4615
4616                 found_root = read_ref_root(extent_root->fs_info, ref_path);
4617                 BUG_ON(!found_root);
4618                 /*
4619                  * for reference counted tree, only process reference paths
4620                  * rooted at the latest committed root.
4621                  */
4622                 if (found_root->ref_cows &&
4623                     ref_path->root_generation != found_root->root_key.offset)
4624                         continue;
4625
4626                 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
4627                         if (pass == 0) {
4628                                 /*
4629                                  * copy data extents to new locations
4630                                  */
4631                                 u64 group_start = group->key.objectid;
4632                                 ret = relocate_data_extent(reloc_inode,
4633                                                            extent_key,
4634                                                            group_start);
4635                                 if (ret < 0)
4636                                         goto out;
4637                                 break;
4638                         }
4639                         level = 0;
4640                 } else {
4641                         level = ref_path->owner_objectid;
4642                 }
4643
4644                 if (prev_block != ref_path->nodes[level]) {
4645                         struct extent_buffer *eb;
4646                         u64 block_start = ref_path->nodes[level];
4647                         u64 block_size = btrfs_level_size(found_root, level);
4648
4649                         eb = read_tree_block(found_root, block_start,
4650                                              block_size, 0);
4651                         btrfs_tree_lock(eb);
4652                         BUG_ON(level != btrfs_header_level(eb));
4653
4654                         if (level == 0)
4655                                 btrfs_item_key_to_cpu(eb, &first_key, 0);
4656                         else
4657                                 btrfs_node_key_to_cpu(eb, &first_key, 0);
4658
4659                         btrfs_tree_unlock(eb);
4660                         free_extent_buffer(eb);
4661                         prev_block = block_start;
4662                 }
4663
4664                 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
4665                     pass >= 2) {
4666                         /*
4667                          * use fallback method to process the remaining
4668                          * references.
4669                          */
4670                         if (!new_extents) {
4671                                 u64 group_start = group->key.objectid;
4672                                 ret = get_new_locations(reloc_inode,
4673                                                         extent_key,
4674                                                         group_start, 0,
4675                                                         &new_extents,
4676                                                         &nr_extents);
4677                                 if (ret < 0)
4678                                         goto out;
4679                         }
4680                         btrfs_record_root_in_trans(found_root);
4681                         ret = replace_one_extent(trans, found_root,
4682                                                 path, extent_key,
4683                                                 &first_key, ref_path,
4684                                                 new_extents, nr_extents);
4685                         if (ret < 0)
4686                                 goto out;
4687                         continue;
4688                 }
4689
4690                 btrfs_record_root_in_trans(found_root);
4691                 if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
4692                         ret = relocate_tree_block(trans, found_root, path,
4693                                                   &first_key, ref_path);
4694                 } else {
4695                         /*
4696                          * try to update data extent references while
4697                          * keeping metadata shared between snapshots.
4698                          */
4699                         ret = relocate_one_path(trans, found_root, path,
4700                                                 &first_key, ref_path,
4701                                                 group, reloc_inode);
4702                 }
4703                 if (ret < 0)
4704                         goto out;
4705         }
4706         ret = 0;
4707 out:
4708         btrfs_end_transaction(trans, extent_root);
4709         kfree(new_extents);
4710         kfree(ref_path);
4711         mutex_lock(&extent_root->fs_info->alloc_mutex);
4712         return ret;
4713 }
4714
4715 static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
4716 {
4717         u64 num_devices;
4718         u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
4719                 BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;
4720
4721         num_devices = root->fs_info->fs_devices->num_devices;
4722         if (num_devices == 1) {
4723                 stripped |= BTRFS_BLOCK_GROUP_DUP;
4724                 stripped = flags & ~stripped;
4725
4726                 /* turn raid0 into single device chunks */
4727                 if (flags & BTRFS_BLOCK_GROUP_RAID0)
4728                         return stripped;
4729
4730                 /* turn mirroring into duplication */
4731                 if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
4732                              BTRFS_BLOCK_GROUP_RAID10))
4733                         return stripped | BTRFS_BLOCK_GROUP_DUP;
4734                 return flags;
4735         } else {
4736                 /* they already had raid on here, just return */
4737                 if (flags & stripped)
4738                         return flags;
4739
4740                 stripped |= BTRFS_BLOCK_GROUP_DUP;
4741                 stripped = flags & ~stripped;
4742
4743                 /* switch duplicated blocks with raid1 */
4744                 if (flags & BTRFS_BLOCK_GROUP_DUP)
4745                         return stripped | BTRFS_BLOCK_GROUP_RAID1;
4746
4747                 /* turn single device chunks into raid0 */
4748                 return stripped | BTRFS_BLOCK_GROUP_RAID0;
4749         }
4750         return flags;
4751 }
4752
4753 int __alloc_chunk_for_shrink(struct btrfs_root *root,
4754                      struct btrfs_block_group_cache *shrink_block_group,
4755                      int force)
4756 {
4757         struct btrfs_trans_handle *trans;
4758         u64 new_alloc_flags;
4759         u64 calc;
4760
4761         spin_lock(&shrink_block_group->lock);
4762         if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
4763                 spin_unlock(&shrink_block_group->lock);
4764                 mutex_unlock(&root->fs_info->alloc_mutex);
4765
4766                 trans = btrfs_start_transaction(root, 1);
4767                 mutex_lock(&root->fs_info->alloc_mutex);
4768                 spin_lock(&shrink_block_group->lock);
4769
4770                 new_alloc_flags = update_block_group_flags(root,
4771                                                    shrink_block_group->flags);
4772                 if (new_alloc_flags != shrink_block_group->flags) {
4773                         calc =
4774                              btrfs_block_group_used(&shrink_block_group->item);
4775                 } else {
4776                         calc = shrink_block_group->key.offset;
4777                 }
4778                 spin_unlock(&shrink_block_group->lock);
4779
4780                 do_chunk_alloc(trans, root->fs_info->extent_root,
4781                                calc + 2 * 1024 * 1024, new_alloc_flags, force);
4782
4783                 mutex_unlock(&root->fs_info->alloc_mutex);
4784                 btrfs_end_transaction(trans, root);
4785                 mutex_lock(&root->fs_info->alloc_mutex);
4786         } else
4787                 spin_unlock(&shrink_block_group->lock);
4788         return 0;
4789 }
4790
4791 static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
4792                                  struct btrfs_root *root,
4793                                  u64 objectid, u64 size)
4794 {
4795         struct btrfs_path *path;
4796         struct btrfs_inode_item *item;
4797         struct extent_buffer *leaf;
4798         int ret;
4799
4800         path = btrfs_alloc_path();
4801         if (!path)
4802                 return -ENOMEM;
4803
4804         ret = btrfs_insert_empty_inode(trans, root, path, objectid);
4805         if (ret)
4806                 goto out;
4807
4808         leaf = path->nodes[0];
4809         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
4810         memset_extent_buffer(leaf, 0, (unsigned long)item, sizeof(*item));
4811         btrfs_set_inode_generation(leaf, item, 1);
4812         btrfs_set_inode_size(leaf, item, size);
4813         btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
4814         btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NODATASUM);
4815         btrfs_mark_buffer_dirty(leaf);
4816         btrfs_release_path(root, path);
4817 out:
4818         btrfs_free_path(path);
4819         return ret;
4820 }
4821
4822 static struct inode noinline *create_reloc_inode(struct btrfs_fs_info *fs_info,
4823                                         struct btrfs_block_group_cache *group)
4824 {
4825         struct inode *inode = NULL;
4826         struct btrfs_trans_handle *trans;
4827         struct btrfs_root *root;
4828         struct btrfs_key root_key;
4829         u64 objectid = BTRFS_FIRST_FREE_OBJECTID;
4830         int err = 0;
4831
4832         root_key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
4833         root_key.type = BTRFS_ROOT_ITEM_KEY;
4834         root_key.offset = (u64)-1;
4835         root = btrfs_read_fs_root_no_name(fs_info, &root_key);
4836         if (IS_ERR(root))
4837                 return ERR_CAST(root);
4838
4839         trans = btrfs_start_transaction(root, 1);
4840         BUG_ON(!trans);
4841
4842         err = btrfs_find_free_objectid(trans, root, objectid, &objectid);
4843         if (err)
4844                 goto out;
4845
4846         err = __insert_orphan_inode(trans, root, objectid, group->key.offset);
4847         BUG_ON(err);
4848
4849         err = btrfs_insert_file_extent(trans, root, objectid, 0, 0, 0,
4850                                        group->key.offset, 0);
4851         BUG_ON(err);
4852
4853         inode = btrfs_iget_locked(root->fs_info->sb, objectid, root);
4854         if (inode->i_state & I_NEW) {
4855                 BTRFS_I(inode)->root = root;
4856                 BTRFS_I(inode)->location.objectid = objectid;
4857                 BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
4858                 BTRFS_I(inode)->location.offset = 0;
4859                 btrfs_read_locked_inode(inode);
4860                 unlock_new_inode(inode);
4861                 BUG_ON(is_bad_inode(inode));
4862         } else {
4863                 BUG_ON(1);
4864         }
4865
4866         err = btrfs_orphan_add(trans, inode);
4867 out:
4868         btrfs_end_transaction(trans, root);
4869         if (err) {
4870                 if (inode)
4871                         iput(inode);
4872                 inode = ERR_PTR(err);
4873         }
4874         return inode;
4875 }
4876
4877 int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start)
4878 {
4879         struct btrfs_trans_handle *trans;
4880         struct btrfs_path *path;
4881         struct btrfs_fs_info *info = root->fs_info;
4882         struct extent_buffer *leaf;
4883         struct inode *reloc_inode;
4884         struct btrfs_block_group_cache *block_group;
4885         struct btrfs_key key;
4886         u64 cur_byte;
4887         u64 total_found;
4888         u32 nritems;
4889         int ret;
4890         int progress;
4891         int pass = 0;
4892
4893         root = root->fs_info->extent_root;
4894
4895         block_group = btrfs_lookup_block_group(info, group_start);
4896         BUG_ON(!block_group);
4897
4898         printk("btrfs relocating block group %llu flags %llu\n",
4899                (unsigned long long)block_group->key.objectid,
4900                (unsigned long long)block_group->flags);
4901
4902         path = btrfs_alloc_path();
4903         BUG_ON(!path);
4904
4905         reloc_inode = create_reloc_inode(info, block_group);
4906         BUG_ON(IS_ERR(reloc_inode));
4907
4908         mutex_lock(&root->fs_info->alloc_mutex);
4909
4910         __alloc_chunk_for_shrink(root, block_group, 1);
4911         block_group->ro = 1;
4912         block_group->space_info->total_bytes -= block_group->key.offset;
4913
4914         mutex_unlock(&root->fs_info->alloc_mutex);
4915
4916         btrfs_start_delalloc_inodes(info->tree_root);
4917         btrfs_wait_ordered_extents(info->tree_root, 0);
4918 again:
4919         total_found = 0;
4920         progress = 0;
4921         key.objectid = block_group->key.objectid;
4922         key.offset = 0;
4923         key.type = 0;
4924         cur_byte = key.objectid;
4925
4926         trans = btrfs_start_transaction(info->tree_root, 1);
4927         btrfs_commit_transaction(trans, info->tree_root);
4928
4929         mutex_lock(&root->fs_info->cleaner_mutex);
4930         btrfs_clean_old_snapshots(info->tree_root);
4931         btrfs_remove_leaf_refs(info->tree_root, (u64)-1, 1);
4932         mutex_unlock(&root->fs_info->cleaner_mutex);
4933
4934         mutex_lock(&root->fs_info->alloc_mutex);
4935
4936         while(1) {
4937                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4938                 if (ret < 0)
4939                         goto out;
4940 next:
4941                 leaf = path->nodes[0];
4942                 nritems = btrfs_header_nritems(leaf);
4943                 if (path->slots[0] >= nritems) {
4944                         ret = btrfs_next_leaf(root, path);
4945                         if (ret < 0)
4946                                 goto out;
4947                         if (ret == 1) {
4948                                 ret = 0;
4949                                 break;
4950                         }
4951                         leaf = path->nodes[0];
4952                         nritems = btrfs_header_nritems(leaf);
4953                 }
4954
4955                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4956
4957                 if (key.objectid >= block_group->key.objectid +
4958                     block_group->key.offset)
4959                         break;
4960
4961                 if (progress && need_resched()) {
4962                         btrfs_release_path(root, path);
4963                         mutex_unlock(&root->fs_info->alloc_mutex);
4964                         cond_resched();
4965                         mutex_lock(&root->fs_info->alloc_mutex);
4966                         progress = 0;
4967                         continue;
4968                 }
4969                 progress = 1;
4970
4971                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY ||
4972                     key.objectid + key.offset <= cur_byte) {
4973                         path->slots[0]++;
4974                         goto next;
4975                 }
4976
4977                 total_found++;
4978                 cur_byte = key.objectid + key.offset;
4979                 btrfs_release_path(root, path);
4980
4981                 __alloc_chunk_for_shrink(root, block_group, 0);
4982                 ret = relocate_one_extent(root, path, &key, block_group,
4983                                           reloc_inode, pass);
4984                 BUG_ON(ret < 0);
4985
4986                 key.objectid = cur_byte;
4987                 key.type = 0;
4988                 key.offset = 0;
4989         }
4990
4991         btrfs_release_path(root, path);
4992         mutex_unlock(&root->fs_info->alloc_mutex);
4993
4994         if (pass == 0) {
4995                 btrfs_wait_ordered_range(reloc_inode, 0, (u64)-1);
4996                 invalidate_mapping_pages(reloc_inode->i_mapping, 0, -1);
4997                 WARN_ON(reloc_inode->i_mapping->nrpages);
4998         }
4999
5000         if (total_found > 0) {
5001                 printk("btrfs found %llu extents in pass %d\n",
5002                        (unsigned long long)total_found, pass);
5003                 pass++;
5004                 goto again;
5005         }
5006
5007         /* delete reloc_inode */
5008         iput(reloc_inode);
5009
5010         /* unpin extents in this range */
5011         trans = btrfs_start_transaction(info->tree_root, 1);
5012         btrfs_commit_transaction(trans, info->tree_root);
5013
5014         mutex_lock(&root->fs_info->alloc_mutex);
5015
5016         spin_lock(&block_group->lock);
5017         WARN_ON(block_group->pinned > 0);
5018         WARN_ON(block_group->reserved > 0);
5019         WARN_ON(btrfs_block_group_used(&block_group->item) > 0);
5020         spin_unlock(&block_group->lock);
5021         ret = 0;
5022 out:
5023         mutex_unlock(&root->fs_info->alloc_mutex);
5024         btrfs_free_path(path);
5025         return ret;
5026 }
5027
5028 int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
5029                            struct btrfs_key *key)
5030 {
5031         int ret = 0;
5032         struct btrfs_key found_key;
5033         struct extent_buffer *leaf;
5034         int slot;
5035
5036         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
5037         if (ret < 0)
5038                 goto out;
5039
5040         while(1) {
5041                 slot = path->slots[0];
5042                 leaf = path->nodes[0];
5043                 if (slot >= btrfs_header_nritems(leaf)) {
5044                         ret = btrfs_next_leaf(root, path);
5045                         if (ret == 0)
5046                                 continue;
5047                         if (ret < 0)
5048                                 goto out;
5049                         break;
5050                 }
5051                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
5052
5053                 if (found_key.objectid >= key->objectid &&
5054                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
5055                         ret = 0;
5056                         goto out;
5057                 }
5058                 path->slots[0]++;
5059         }
5060         ret = -ENOENT;
5061 out:
5062         return ret;
5063 }
5064
5065 int btrfs_free_block_groups(struct btrfs_fs_info *info)
5066 {
5067         struct btrfs_block_group_cache *block_group;
5068         struct rb_node *n;
5069
5070         mutex_lock(&info->alloc_mutex);
5071         spin_lock(&info->block_group_cache_lock);
5072         while ((n = rb_last(&info->block_group_cache_tree)) != NULL) {
5073                 block_group = rb_entry(n, struct btrfs_block_group_cache,
5074                                        cache_node);
5075
5076                 spin_unlock(&info->block_group_cache_lock);
5077                 btrfs_remove_free_space_cache(block_group);
5078                 spin_lock(&info->block_group_cache_lock);
5079
5080                 rb_erase(&block_group->cache_node,
5081                          &info->block_group_cache_tree);
5082                 spin_lock(&block_group->space_info->lock);
5083                 list_del(&block_group->list);
5084                 spin_unlock(&block_group->space_info->lock);
5085                 kfree(block_group);
5086         }
5087         spin_unlock(&info->block_group_cache_lock);
5088         mutex_unlock(&info->alloc_mutex);
5089         return 0;
5090 }
5091
5092 int btrfs_read_block_groups(struct btrfs_root *root)
5093 {
5094         struct btrfs_path *path;
5095         int ret;
5096         struct btrfs_block_group_cache *cache;
5097         struct btrfs_fs_info *info = root->fs_info;
5098         struct btrfs_space_info *space_info;
5099         struct btrfs_key key;
5100         struct btrfs_key found_key;
5101         struct extent_buffer *leaf;
5102
5103         root = info->extent_root;
5104         key.objectid = 0;
5105         key.offset = 0;
5106         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
5107         path = btrfs_alloc_path();
5108         if (!path)
5109                 return -ENOMEM;
5110
5111         mutex_lock(&root->fs_info->alloc_mutex);
5112         while(1) {
5113                 ret = find_first_block_group(root, path, &key);
5114                 if (ret > 0) {
5115                         ret = 0;
5116                         goto error;
5117                 }
5118                 if (ret != 0)
5119                         goto error;
5120
5121                 leaf = path->nodes[0];
5122                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5123                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
5124                 if (!cache) {
5125                         ret = -ENOMEM;
5126                         break;
5127                 }
5128
5129                 spin_lock_init(&cache->lock);
5130                 INIT_LIST_HEAD(&cache->list);
5131                 read_extent_buffer(leaf, &cache->item,
5132                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
5133                                    sizeof(cache->item));
5134                 memcpy(&cache->key, &found_key, sizeof(found_key));
5135
5136                 key.objectid = found_key.objectid + found_key.offset;
5137                 btrfs_release_path(root, path);
5138                 cache->flags = btrfs_block_group_flags(&cache->item);
5139
5140                 ret = update_space_info(info, cache->flags, found_key.offset,
5141                                         btrfs_block_group_used(&cache->item),
5142                                         &space_info);
5143                 BUG_ON(ret);
5144                 cache->space_info = space_info;
5145                 spin_lock(&space_info->lock);
5146                 list_add(&cache->list, &space_info->block_groups);
5147                 spin_unlock(&space_info->lock);
5148
5149                 ret = btrfs_add_block_group_cache(root->fs_info, cache);
5150                 BUG_ON(ret);
5151
5152                 set_avail_alloc_bits(root->fs_info, cache->flags);
5153         }
5154         ret = 0;
5155 error:
5156         btrfs_free_path(path);
5157         mutex_unlock(&root->fs_info->alloc_mutex);
5158         return ret;
5159 }
5160
5161 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
5162                            struct btrfs_root *root, u64 bytes_used,
5163                            u64 type, u64 chunk_objectid, u64 chunk_offset,
5164                            u64 size)
5165 {
5166         int ret;
5167         struct btrfs_root *extent_root;
5168         struct btrfs_block_group_cache *cache;
5169
5170         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
5171         extent_root = root->fs_info->extent_root;
5172
5173         root->fs_info->last_trans_new_blockgroup = trans->transid;
5174
5175         cache = kzalloc(sizeof(*cache), GFP_NOFS);
5176         if (!cache)
5177                 return -ENOMEM;
5178
5179         cache->key.objectid = chunk_offset;
5180         cache->key.offset = size;
5181         spin_lock_init(&cache->lock);
5182         INIT_LIST_HEAD(&cache->list);
5183         btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
5184
5185         btrfs_set_block_group_used(&cache->item, bytes_used);
5186         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
5187         cache->flags = type;
5188         btrfs_set_block_group_flags(&cache->item, type);
5189
5190         ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
5191                                 &cache->space_info);
5192         BUG_ON(ret);
5193         spin_lock(&cache->space_info->lock);
5194         list_add(&cache->list, &cache->space_info->block_groups);
5195         spin_unlock(&cache->space_info->lock);
5196
5197         ret = btrfs_add_block_group_cache(root->fs_info, cache);
5198         BUG_ON(ret);
5199
5200         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
5201                                 sizeof(cache->item));
5202         BUG_ON(ret);
5203
5204         finish_current_insert(trans, extent_root);
5205         ret = del_pending_extents(trans, extent_root);
5206         BUG_ON(ret);
5207         set_avail_alloc_bits(extent_root->fs_info, type);
5208
5209         return 0;
5210 }
5211
5212 int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
5213                              struct btrfs_root *root, u64 group_start)
5214 {
5215         struct btrfs_path *path;
5216         struct btrfs_block_group_cache *block_group;
5217         struct btrfs_key key;
5218         int ret;
5219
5220         BUG_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
5221         root = root->fs_info->extent_root;
5222
5223         block_group = btrfs_lookup_block_group(root->fs_info, group_start);
5224         BUG_ON(!block_group);
5225
5226         memcpy(&key, &block_group->key, sizeof(key));
5227
5228         path = btrfs_alloc_path();
5229         BUG_ON(!path);
5230
5231         btrfs_remove_free_space_cache(block_group);
5232         rb_erase(&block_group->cache_node,
5233                  &root->fs_info->block_group_cache_tree);
5234         spin_lock(&block_group->space_info->lock);
5235         list_del(&block_group->list);
5236         spin_unlock(&block_group->space_info->lock);
5237
5238         /*
5239         memset(shrink_block_group, 0, sizeof(*shrink_block_group));
5240         kfree(shrink_block_group);
5241         */
5242
5243         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
5244         if (ret > 0)
5245                 ret = -EIO;
5246         if (ret < 0)
5247                 goto out;
5248
5249         ret = btrfs_del_item(trans, root, path);
5250 out:
5251         btrfs_free_path(path);
5252         return ret;
5253 }