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