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