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