linux/fs/btrfs/extent-tree.c
<<
>>
Prefs
   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 <linux/kthread.h>
  25#include <linux/slab.h>
  26#include <linux/ratelimit.h>
  27#include "compat.h"
  28#include "hash.h"
  29#include "ctree.h"
  30#include "disk-io.h"
  31#include "print-tree.h"
  32#include "transaction.h"
  33#include "volumes.h"
  34#include "locking.h"
  35#include "free-space-cache.h"
  36
  37#undef SCRAMBLE_DELAYED_REFS
  38
  39/*
  40 * control flags for do_chunk_alloc's force field
  41 * CHUNK_ALLOC_NO_FORCE means to only allocate a chunk
  42 * if we really need one.
  43 *
  44 * CHUNK_ALLOC_LIMITED means to only try and allocate one
  45 * if we have very few chunks already allocated.  This is
  46 * used as part of the clustering code to help make sure
  47 * we have a good pool of storage to cluster in, without
  48 * filling the FS with empty chunks
  49 *
  50 * CHUNK_ALLOC_FORCE means it must try to allocate one
  51 *
  52 */
  53enum {
  54        CHUNK_ALLOC_NO_FORCE = 0,
  55        CHUNK_ALLOC_LIMITED = 1,
  56        CHUNK_ALLOC_FORCE = 2,
  57};
  58
  59/*
  60 * Control how reservations are dealt with.
  61 *
  62 * RESERVE_FREE - freeing a reservation.
  63 * RESERVE_ALLOC - allocating space and we need to update bytes_may_use for
  64 *   ENOSPC accounting
  65 * RESERVE_ALLOC_NO_ACCOUNT - allocating space and we should not update
  66 *   bytes_may_use as the ENOSPC accounting is done elsewhere
  67 */
  68enum {
  69        RESERVE_FREE = 0,
  70        RESERVE_ALLOC = 1,
  71        RESERVE_ALLOC_NO_ACCOUNT = 2,
  72};
  73
  74static int update_block_group(struct btrfs_trans_handle *trans,
  75                              struct btrfs_root *root,
  76                              u64 bytenr, u64 num_bytes, int alloc);
  77static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
  78                                struct btrfs_root *root,
  79                                u64 bytenr, u64 num_bytes, u64 parent,
  80                                u64 root_objectid, u64 owner_objectid,
  81                                u64 owner_offset, int refs_to_drop,
  82                                struct btrfs_delayed_extent_op *extra_op);
  83static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
  84                                    struct extent_buffer *leaf,
  85                                    struct btrfs_extent_item *ei);
  86static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
  87                                      struct btrfs_root *root,
  88                                      u64 parent, u64 root_objectid,
  89                                      u64 flags, u64 owner, u64 offset,
  90                                      struct btrfs_key *ins, int ref_mod);
  91static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
  92                                     struct btrfs_root *root,
  93                                     u64 parent, u64 root_objectid,
  94                                     u64 flags, struct btrfs_disk_key *key,
  95                                     int level, struct btrfs_key *ins);
  96static int do_chunk_alloc(struct btrfs_trans_handle *trans,
  97                          struct btrfs_root *extent_root, u64 alloc_bytes,
  98                          u64 flags, int force);
  99static int find_next_key(struct btrfs_path *path, int level,
 100                         struct btrfs_key *key);
 101static void dump_space_info(struct btrfs_space_info *info, u64 bytes,
 102                            int dump_block_groups);
 103static int btrfs_update_reserved_bytes(struct btrfs_block_group_cache *cache,
 104                                       u64 num_bytes, int reserve);
 105
 106static noinline int
 107block_group_cache_done(struct btrfs_block_group_cache *cache)
 108{
 109        smp_mb();
 110        return cache->cached == BTRFS_CACHE_FINISHED;
 111}
 112
 113static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
 114{
 115        return (cache->flags & bits) == bits;
 116}
 117
 118static void btrfs_get_block_group(struct btrfs_block_group_cache *cache)
 119{
 120        atomic_inc(&cache->count);
 121}
 122
 123void btrfs_put_block_group(struct btrfs_block_group_cache *cache)
 124{
 125        if (atomic_dec_and_test(&cache->count)) {
 126                WARN_ON(cache->pinned > 0);
 127                WARN_ON(cache->reserved > 0);
 128                kfree(cache->free_space_ctl);
 129                kfree(cache);
 130        }
 131}
 132
 133/*
 134 * this adds the block group to the fs_info rb tree for the block group
 135 * cache
 136 */
 137static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
 138                                struct btrfs_block_group_cache *block_group)
 139{
 140        struct rb_node **p;
 141        struct rb_node *parent = NULL;
 142        struct btrfs_block_group_cache *cache;
 143
 144        spin_lock(&info->block_group_cache_lock);
 145        p = &info->block_group_cache_tree.rb_node;
 146
 147        while (*p) {
 148                parent = *p;
 149                cache = rb_entry(parent, struct btrfs_block_group_cache,
 150                                 cache_node);
 151                if (block_group->key.objectid < cache->key.objectid) {
 152                        p = &(*p)->rb_left;
 153                } else if (block_group->key.objectid > cache->key.objectid) {
 154                        p = &(*p)->rb_right;
 155                } else {
 156                        spin_unlock(&info->block_group_cache_lock);
 157                        return -EEXIST;
 158                }
 159        }
 160
 161        rb_link_node(&block_group->cache_node, parent, p);
 162        rb_insert_color(&block_group->cache_node,
 163                        &info->block_group_cache_tree);
 164        spin_unlock(&info->block_group_cache_lock);
 165
 166        return 0;
 167}
 168
 169/*
 170 * This will return the block group at or after bytenr if contains is 0, else
 171 * it will return the block group that contains the bytenr
 172 */
 173static struct btrfs_block_group_cache *
 174block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
 175                              int contains)
 176{
 177        struct btrfs_block_group_cache *cache, *ret = NULL;
 178        struct rb_node *n;
 179        u64 end, start;
 180
 181        spin_lock(&info->block_group_cache_lock);
 182        n = info->block_group_cache_tree.rb_node;
 183
 184        while (n) {
 185                cache = rb_entry(n, struct btrfs_block_group_cache,
 186                                 cache_node);
 187                end = cache->key.objectid + cache->key.offset - 1;
 188                start = cache->key.objectid;
 189
 190                if (bytenr < start) {
 191                        if (!contains && (!ret || start < ret->key.objectid))
 192                                ret = cache;
 193                        n = n->rb_left;
 194                } else if (bytenr > start) {
 195                        if (contains && bytenr <= end) {
 196                                ret = cache;
 197                                break;
 198                        }
 199                        n = n->rb_right;
 200                } else {
 201                        ret = cache;
 202                        break;
 203                }
 204        }
 205        if (ret)
 206                btrfs_get_block_group(ret);
 207        spin_unlock(&info->block_group_cache_lock);
 208
 209        return ret;
 210}
 211
 212static int add_excluded_extent(struct btrfs_root *root,
 213                               u64 start, u64 num_bytes)
 214{
 215        u64 end = start + num_bytes - 1;
 216        set_extent_bits(&root->fs_info->freed_extents[0],
 217                        start, end, EXTENT_UPTODATE, GFP_NOFS);
 218        set_extent_bits(&root->fs_info->freed_extents[1],
 219                        start, end, EXTENT_UPTODATE, GFP_NOFS);
 220        return 0;
 221}
 222
 223static void free_excluded_extents(struct btrfs_root *root,
 224                                  struct btrfs_block_group_cache *cache)
 225{
 226        u64 start, end;
 227
 228        start = cache->key.objectid;
 229        end = start + cache->key.offset - 1;
 230
 231        clear_extent_bits(&root->fs_info->freed_extents[0],
 232                          start, end, EXTENT_UPTODATE, GFP_NOFS);
 233        clear_extent_bits(&root->fs_info->freed_extents[1],
 234                          start, end, EXTENT_UPTODATE, GFP_NOFS);
 235}
 236
 237static int exclude_super_stripes(struct btrfs_root *root,
 238                                 struct btrfs_block_group_cache *cache)
 239{
 240        u64 bytenr;
 241        u64 *logical;
 242        int stripe_len;
 243        int i, nr, ret;
 244
 245        if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) {
 246                stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid;
 247                cache->bytes_super += stripe_len;
 248                ret = add_excluded_extent(root, cache->key.objectid,
 249                                          stripe_len);
 250                BUG_ON(ret); /* -ENOMEM */
 251        }
 252
 253        for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
 254                bytenr = btrfs_sb_offset(i);
 255                ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
 256                                       cache->key.objectid, bytenr,
 257                                       0, &logical, &nr, &stripe_len);
 258                BUG_ON(ret); /* -ENOMEM */
 259
 260                while (nr--) {
 261                        cache->bytes_super += stripe_len;
 262                        ret = add_excluded_extent(root, logical[nr],
 263                                                  stripe_len);
 264                        BUG_ON(ret); /* -ENOMEM */
 265                }
 266
 267                kfree(logical);
 268        }
 269        return 0;
 270}
 271
 272static struct btrfs_caching_control *
 273get_caching_control(struct btrfs_block_group_cache *cache)
 274{
 275        struct btrfs_caching_control *ctl;
 276
 277        spin_lock(&cache->lock);
 278        if (cache->cached != BTRFS_CACHE_STARTED) {
 279                spin_unlock(&cache->lock);
 280                return NULL;
 281        }
 282
 283        /* We're loading it the fast way, so we don't have a caching_ctl. */
 284        if (!cache->caching_ctl) {
 285                spin_unlock(&cache->lock);
 286                return NULL;
 287        }
 288
 289        ctl = cache->caching_ctl;
 290        atomic_inc(&ctl->count);
 291        spin_unlock(&cache->lock);
 292        return ctl;
 293}
 294
 295static void put_caching_control(struct btrfs_caching_control *ctl)
 296{
 297        if (atomic_dec_and_test(&ctl->count))
 298                kfree(ctl);
 299}
 300
 301/*
 302 * this is only called by cache_block_group, since we could have freed extents
 303 * we need to check the pinned_extents for any extents that can't be used yet
 304 * since their free space will be released as soon as the transaction commits.
 305 */
 306static u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
 307                              struct btrfs_fs_info *info, u64 start, u64 end)
 308{
 309        u64 extent_start, extent_end, size, total_added = 0;
 310        int ret;
 311
 312        while (start < end) {
 313                ret = find_first_extent_bit(info->pinned_extents, start,
 314                                            &extent_start, &extent_end,
 315                                            EXTENT_DIRTY | EXTENT_UPTODATE);
 316                if (ret)
 317                        break;
 318
 319                if (extent_start <= start) {
 320                        start = extent_end + 1;
 321                } else if (extent_start > start && extent_start < end) {
 322                        size = extent_start - start;
 323                        total_added += size;
 324                        ret = btrfs_add_free_space(block_group, start,
 325                                                   size);
 326                        BUG_ON(ret); /* -ENOMEM or logic error */
 327                        start = extent_end + 1;
 328                } else {
 329                        break;
 330                }
 331        }
 332
 333        if (start < end) {
 334                size = end - start;
 335                total_added += size;
 336                ret = btrfs_add_free_space(block_group, start, size);
 337                BUG_ON(ret); /* -ENOMEM or logic error */
 338        }
 339
 340        return total_added;
 341}
 342
 343static noinline void caching_thread(struct btrfs_work *work)
 344{
 345        struct btrfs_block_group_cache *block_group;
 346        struct btrfs_fs_info *fs_info;
 347        struct btrfs_caching_control *caching_ctl;
 348        struct btrfs_root *extent_root;
 349        struct btrfs_path *path;
 350        struct extent_buffer *leaf;
 351        struct btrfs_key key;
 352        u64 total_found = 0;
 353        u64 last = 0;
 354        u32 nritems;
 355        int ret = 0;
 356
 357        caching_ctl = container_of(work, struct btrfs_caching_control, work);
 358        block_group = caching_ctl->block_group;
 359        fs_info = block_group->fs_info;
 360        extent_root = fs_info->extent_root;
 361
 362        path = btrfs_alloc_path();
 363        if (!path)
 364                goto out;
 365
 366        last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
 367
 368        /*
 369         * We don't want to deadlock with somebody trying to allocate a new
 370         * extent for the extent root while also trying to search the extent
 371         * root to add free space.  So we skip locking and search the commit
 372         * root, since its read-only
 373         */
 374        path->skip_locking = 1;
 375        path->search_commit_root = 1;
 376        path->reada = 1;
 377
 378        key.objectid = last;
 379        key.offset = 0;
 380        key.type = BTRFS_EXTENT_ITEM_KEY;
 381again:
 382        mutex_lock(&caching_ctl->mutex);
 383        /* need to make sure the commit_root doesn't disappear */
 384        down_read(&fs_info->extent_commit_sem);
 385
 386        ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 387        if (ret < 0)
 388                goto err;
 389
 390        leaf = path->nodes[0];
 391        nritems = btrfs_header_nritems(leaf);
 392
 393        while (1) {
 394                if (btrfs_fs_closing(fs_info) > 1) {
 395                        last = (u64)-1;
 396                        break;
 397                }
 398
 399                if (path->slots[0] < nritems) {
 400                        btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 401                } else {
 402                        ret = find_next_key(path, 0, &key);
 403                        if (ret)
 404                                break;
 405
 406                        if (need_resched() ||
 407                            btrfs_next_leaf(extent_root, path)) {
 408                                caching_ctl->progress = last;
 409                                btrfs_release_path(path);
 410                                up_read(&fs_info->extent_commit_sem);
 411                                mutex_unlock(&caching_ctl->mutex);
 412                                cond_resched();
 413                                goto again;
 414                        }
 415                        leaf = path->nodes[0];
 416                        nritems = btrfs_header_nritems(leaf);
 417                        continue;
 418                }
 419
 420                if (key.objectid < block_group->key.objectid) {
 421                        path->slots[0]++;
 422                        continue;
 423                }
 424
 425                if (key.objectid >= block_group->key.objectid +
 426                    block_group->key.offset)
 427                        break;
 428
 429                if (key.type == BTRFS_EXTENT_ITEM_KEY) {
 430                        total_found += add_new_free_space(block_group,
 431                                                          fs_info, last,
 432                                                          key.objectid);
 433                        last = key.objectid + key.offset;
 434
 435                        if (total_found > (1024 * 1024 * 2)) {
 436                                total_found = 0;
 437                                wake_up(&caching_ctl->wait);
 438                        }
 439                }
 440                path->slots[0]++;
 441        }
 442        ret = 0;
 443
 444        total_found += add_new_free_space(block_group, fs_info, last,
 445                                          block_group->key.objectid +
 446                                          block_group->key.offset);
 447        caching_ctl->progress = (u64)-1;
 448
 449        spin_lock(&block_group->lock);
 450        block_group->caching_ctl = NULL;
 451        block_group->cached = BTRFS_CACHE_FINISHED;
 452        spin_unlock(&block_group->lock);
 453
 454err:
 455        btrfs_free_path(path);
 456        up_read(&fs_info->extent_commit_sem);
 457
 458        free_excluded_extents(extent_root, block_group);
 459
 460        mutex_unlock(&caching_ctl->mutex);
 461out:
 462        wake_up(&caching_ctl->wait);
 463
 464        put_caching_control(caching_ctl);
 465        btrfs_put_block_group(block_group);
 466}
 467
 468static int cache_block_group(struct btrfs_block_group_cache *cache,
 469                             struct btrfs_trans_handle *trans,
 470                             struct btrfs_root *root,
 471                             int load_cache_only)
 472{
 473        DEFINE_WAIT(wait);
 474        struct btrfs_fs_info *fs_info = cache->fs_info;
 475        struct btrfs_caching_control *caching_ctl;
 476        int ret = 0;
 477
 478        caching_ctl = kzalloc(sizeof(*caching_ctl), GFP_NOFS);
 479        if (!caching_ctl)
 480                return -ENOMEM;
 481
 482        INIT_LIST_HEAD(&caching_ctl->list);
 483        mutex_init(&caching_ctl->mutex);
 484        init_waitqueue_head(&caching_ctl->wait);
 485        caching_ctl->block_group = cache;
 486        caching_ctl->progress = cache->key.objectid;
 487        atomic_set(&caching_ctl->count, 1);
 488        caching_ctl->work.func = caching_thread;
 489
 490        spin_lock(&cache->lock);
 491        /*
 492         * This should be a rare occasion, but this could happen I think in the
 493         * case where one thread starts to load the space cache info, and then
 494         * some other thread starts a transaction commit which tries to do an
 495         * allocation while the other thread is still loading the space cache
 496         * info.  The previous loop should have kept us from choosing this block
 497         * group, but if we've moved to the state where we will wait on caching
 498         * block groups we need to first check if we're doing a fast load here,
 499         * so we can wait for it to finish, otherwise we could end up allocating
 500         * from a block group who's cache gets evicted for one reason or
 501         * another.
 502         */
 503        while (cache->cached == BTRFS_CACHE_FAST) {
 504                struct btrfs_caching_control *ctl;
 505
 506                ctl = cache->caching_ctl;
 507                atomic_inc(&ctl->count);
 508                prepare_to_wait(&ctl->wait, &wait, TASK_UNINTERRUPTIBLE);
 509                spin_unlock(&cache->lock);
 510
 511                schedule();
 512
 513                finish_wait(&ctl->wait, &wait);
 514                put_caching_control(ctl);
 515                spin_lock(&cache->lock);
 516        }
 517
 518        if (cache->cached != BTRFS_CACHE_NO) {
 519                spin_unlock(&cache->lock);
 520                kfree(caching_ctl);
 521                return 0;
 522        }
 523        WARN_ON(cache->caching_ctl);
 524        cache->caching_ctl = caching_ctl;
 525        cache->cached = BTRFS_CACHE_FAST;
 526        spin_unlock(&cache->lock);
 527
 528        /*
 529         * We can't do the read from on-disk cache during a commit since we need
 530         * to have the normal tree locking.  Also if we are currently trying to
 531         * allocate blocks for the tree root we can't do the fast caching since
 532         * we likely hold important locks.
 533         */
 534        if (fs_info->mount_opt & BTRFS_MOUNT_SPACE_CACHE) {
 535                ret = load_free_space_cache(fs_info, cache);
 536
 537                spin_lock(&cache->lock);
 538                if (ret == 1) {
 539                        cache->caching_ctl = NULL;
 540                        cache->cached = BTRFS_CACHE_FINISHED;
 541                        cache->last_byte_to_unpin = (u64)-1;
 542                } else {
 543                        if (load_cache_only) {
 544                                cache->caching_ctl = NULL;
 545                                cache->cached = BTRFS_CACHE_NO;
 546                        } else {
 547                                cache->cached = BTRFS_CACHE_STARTED;
 548                        }
 549                }
 550                spin_unlock(&cache->lock);
 551                wake_up(&caching_ctl->wait);
 552                if (ret == 1) {
 553                        put_caching_control(caching_ctl);
 554                        free_excluded_extents(fs_info->extent_root, cache);
 555                        return 0;
 556                }
 557        } else {
 558                /*
 559                 * We are not going to do the fast caching, set cached to the
 560                 * appropriate value and wakeup any waiters.
 561                 */
 562                spin_lock(&cache->lock);
 563                if (load_cache_only) {
 564                        cache->caching_ctl = NULL;
 565                        cache->cached = BTRFS_CACHE_NO;
 566                } else {
 567                        cache->cached = BTRFS_CACHE_STARTED;
 568                }
 569                spin_unlock(&cache->lock);
 570                wake_up(&caching_ctl->wait);
 571        }
 572
 573        if (load_cache_only) {
 574                put_caching_control(caching_ctl);
 575                return 0;
 576        }
 577
 578        down_write(&fs_info->extent_commit_sem);
 579        atomic_inc(&caching_ctl->count);
 580        list_add_tail(&caching_ctl->list, &fs_info->caching_block_groups);
 581        up_write(&fs_info->extent_commit_sem);
 582
 583        btrfs_get_block_group(cache);
 584
 585        btrfs_queue_worker(&fs_info->caching_workers, &caching_ctl->work);
 586
 587        return ret;
 588}
 589
 590/*
 591 * return the block group that starts at or after bytenr
 592 */
 593static struct btrfs_block_group_cache *
 594btrfs_lookup_first_block_group(struct btrfs_fs_info *info, u64 bytenr)
 595{
 596        struct btrfs_block_group_cache *cache;
 597
 598        cache = block_group_cache_tree_search(info, bytenr, 0);
 599
 600        return cache;
 601}
 602
 603/*
 604 * return the block group that contains the given bytenr
 605 */
 606struct btrfs_block_group_cache *btrfs_lookup_block_group(
 607                                                 struct btrfs_fs_info *info,
 608                                                 u64 bytenr)
 609{
 610        struct btrfs_block_group_cache *cache;
 611
 612        cache = block_group_cache_tree_search(info, bytenr, 1);
 613
 614        return cache;
 615}
 616
 617static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
 618                                                  u64 flags)
 619{
 620        struct list_head *head = &info->space_info;
 621        struct btrfs_space_info *found;
 622
 623        flags &= BTRFS_BLOCK_GROUP_TYPE_MASK;
 624
 625        rcu_read_lock();
 626        list_for_each_entry_rcu(found, head, list) {
 627                if (found->flags & flags) {
 628                        rcu_read_unlock();
 629                        return found;
 630                }
 631        }
 632        rcu_read_unlock();
 633        return NULL;
 634}
 635
 636/*
 637 * after adding space to the filesystem, we need to clear the full flags
 638 * on all the space infos.
 639 */
 640void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
 641{
 642        struct list_head *head = &info->space_info;
 643        struct btrfs_space_info *found;
 644
 645        rcu_read_lock();
 646        list_for_each_entry_rcu(found, head, list)
 647                found->full = 0;
 648        rcu_read_unlock();
 649}
 650
 651static u64 div_factor(u64 num, int factor)
 652{
 653        if (factor == 10)
 654                return num;
 655        num *= factor;
 656        do_div(num, 10);
 657        return num;
 658}
 659
 660static u64 div_factor_fine(u64 num, int factor)
 661{
 662        if (factor == 100)
 663                return num;
 664        num *= factor;
 665        do_div(num, 100);
 666        return num;
 667}
 668
 669u64 btrfs_find_block_group(struct btrfs_root *root,
 670                           u64 search_start, u64 search_hint, int owner)
 671{
 672        struct btrfs_block_group_cache *cache;
 673        u64 used;
 674        u64 last = max(search_hint, search_start);
 675        u64 group_start = 0;
 676        int full_search = 0;
 677        int factor = 9;
 678        int wrapped = 0;
 679again:
 680        while (1) {
 681                cache = btrfs_lookup_first_block_group(root->fs_info, last);
 682                if (!cache)
 683                        break;
 684
 685                spin_lock(&cache->lock);
 686                last = cache->key.objectid + cache->key.offset;
 687                used = btrfs_block_group_used(&cache->item);
 688
 689                if ((full_search || !cache->ro) &&
 690                    block_group_bits(cache, BTRFS_BLOCK_GROUP_METADATA)) {
 691                        if (used + cache->pinned + cache->reserved <
 692                            div_factor(cache->key.offset, factor)) {
 693                                group_start = cache->key.objectid;
 694                                spin_unlock(&cache->lock);
 695                                btrfs_put_block_group(cache);
 696                                goto found;
 697                        }
 698                }
 699                spin_unlock(&cache->lock);
 700                btrfs_put_block_group(cache);
 701                cond_resched();
 702        }
 703        if (!wrapped) {
 704                last = search_start;
 705                wrapped = 1;
 706                goto again;
 707        }
 708        if (!full_search && factor < 10) {
 709                last = search_start;
 710                full_search = 1;
 711                factor = 10;
 712                goto again;
 713        }
 714found:
 715        return group_start;
 716}
 717
 718/* simple helper to search for an existing extent at a given offset */
 719int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
 720{
 721        int ret;
 722        struct btrfs_key key;
 723        struct btrfs_path *path;
 724
 725        path = btrfs_alloc_path();
 726        if (!path)
 727                return -ENOMEM;
 728
 729        key.objectid = start;
 730        key.offset = len;
 731        btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 732        ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
 733                                0, 0);
 734        btrfs_free_path(path);
 735        return ret;
 736}
 737
 738/*
 739 * helper function to lookup reference count and flags of extent.
 740 *
 741 * the head node for delayed ref is used to store the sum of all the
 742 * reference count modifications queued up in the rbtree. the head
 743 * node may also store the extent flags to set. This way you can check
 744 * to see what the reference count and extent flags would be if all of
 745 * the delayed refs are not processed.
 746 */
 747int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
 748                             struct btrfs_root *root, u64 bytenr,
 749                             u64 num_bytes, u64 *refs, u64 *flags)
 750{
 751        struct btrfs_delayed_ref_head *head;
 752        struct btrfs_delayed_ref_root *delayed_refs;
 753        struct btrfs_path *path;
 754        struct btrfs_extent_item *ei;
 755        struct extent_buffer *leaf;
 756        struct btrfs_key key;
 757        u32 item_size;
 758        u64 num_refs;
 759        u64 extent_flags;
 760        int ret;
 761
 762        path = btrfs_alloc_path();
 763        if (!path)
 764                return -ENOMEM;
 765
 766        key.objectid = bytenr;
 767        key.type = BTRFS_EXTENT_ITEM_KEY;
 768        key.offset = num_bytes;
 769        if (!trans) {
 770                path->skip_locking = 1;
 771                path->search_commit_root = 1;
 772        }
 773again:
 774        ret = btrfs_search_slot(trans, root->fs_info->extent_root,
 775                                &key, path, 0, 0);
 776        if (ret < 0)
 777                goto out_free;
 778
 779        if (ret == 0) {
 780                leaf = path->nodes[0];
 781                item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 782                if (item_size >= sizeof(*ei)) {
 783                        ei = btrfs_item_ptr(leaf, path->slots[0],
 784                                            struct btrfs_extent_item);
 785                        num_refs = btrfs_extent_refs(leaf, ei);
 786                        extent_flags = btrfs_extent_flags(leaf, ei);
 787                } else {
 788#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 789                        struct btrfs_extent_item_v0 *ei0;
 790                        BUG_ON(item_size != sizeof(*ei0));
 791                        ei0 = btrfs_item_ptr(leaf, path->slots[0],
 792                                             struct btrfs_extent_item_v0);
 793                        num_refs = btrfs_extent_refs_v0(leaf, ei0);
 794                        /* FIXME: this isn't correct for data */
 795                        extent_flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
 796#else
 797                        BUG();
 798#endif
 799                }
 800                BUG_ON(num_refs == 0);
 801        } else {
 802                num_refs = 0;
 803                extent_flags = 0;
 804                ret = 0;
 805        }
 806
 807        if (!trans)
 808                goto out;
 809
 810        delayed_refs = &trans->transaction->delayed_refs;
 811        spin_lock(&delayed_refs->lock);
 812        head = btrfs_find_delayed_ref_head(trans, bytenr);
 813        if (head) {
 814                if (!mutex_trylock(&head->mutex)) {
 815                        atomic_inc(&head->node.refs);
 816                        spin_unlock(&delayed_refs->lock);
 817
 818                        btrfs_release_path(path);
 819
 820                        /*
 821                         * Mutex was contended, block until it's released and try
 822                         * again
 823                         */
 824                        mutex_lock(&head->mutex);
 825                        mutex_unlock(&head->mutex);
 826                        btrfs_put_delayed_ref(&head->node);
 827                        goto again;
 828                }
 829                if (head->extent_op && head->extent_op->update_flags)
 830                        extent_flags |= head->extent_op->flags_to_set;
 831                else
 832                        BUG_ON(num_refs == 0);
 833
 834                num_refs += head->node.ref_mod;
 835                mutex_unlock(&head->mutex);
 836        }
 837        spin_unlock(&delayed_refs->lock);
 838out:
 839        WARN_ON(num_refs == 0);
 840        if (refs)
 841                *refs = num_refs;
 842        if (flags)
 843                *flags = extent_flags;
 844out_free:
 845        btrfs_free_path(path);
 846        return ret;
 847}
 848
 849/*
 850 * Back reference rules.  Back refs have three main goals:
 851 *
 852 * 1) differentiate between all holders of references to an extent so that
 853 *    when a reference is dropped we can make sure it was a valid reference
 854 *    before freeing the extent.
 855 *
 856 * 2) Provide enough information to quickly find the holders of an extent
 857 *    if we notice a given block is corrupted or bad.
 858 *
 859 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 860 *    maintenance.  This is actually the same as #2, but with a slightly
 861 *    different use case.
 862 *
 863 * There are two kinds of back refs. The implicit back refs is optimized
 864 * for pointers in non-shared tree blocks. For a given pointer in a block,
 865 * back refs of this kind provide information about the block's owner tree
 866 * and the pointer's key. These information allow us to find the block by
 867 * b-tree searching. The full back refs is for pointers in tree blocks not
 868 * referenced by their owner trees. The location of tree block is recorded
 869 * in the back refs. Actually the full back refs is generic, and can be
 870 * used in all cases the implicit back refs is used. The major shortcoming
 871 * of the full back refs is its overhead. Every time a tree block gets
 872 * COWed, we have to update back refs entry for all pointers in it.
 873 *
 874 * For a newly allocated tree block, we use implicit back refs for
 875 * pointers in it. This means most tree related operations only involve
 876 * implicit back refs. For a tree block created in old transaction, the
 877 * only way to drop a reference to it is COW it. So we can detect the
 878 * event that tree block loses its owner tree's reference and do the
 879 * back refs conversion.
 880 *
 881 * When a tree block is COW'd through a tree, there are four cases:
 882 *
 883 * The reference count of the block is one and the tree is the block's
 884 * owner tree. Nothing to do in this case.
 885 *
 886 * The reference count of the block is one and the tree is not the
 887 * block's owner tree. In this case, full back refs is used for pointers
 888 * in the block. Remove these full back refs, add implicit back refs for
 889 * every pointers in the new block.
 890 *
 891 * The reference count of the block is greater than one and the tree is
 892 * the block's owner tree. In this case, implicit back refs is used for
 893 * pointers in the block. Add full back refs for every pointers in the
 894 * block, increase lower level extents' reference counts. The original
 895 * implicit back refs are entailed to the new block.
 896 *
 897 * The reference count of the block is greater than one and the tree is
 898 * not the block's owner tree. Add implicit back refs for every pointer in
 899 * the new block, increase lower level extents' reference count.
 900 *
 901 * Back Reference Key composing:
 902 *
 903 * The key objectid corresponds to the first byte in the extent,
 904 * The key type is used to differentiate between types of back refs.
 905 * There are different meanings of the key offset for different types
 906 * of back refs.
 907 *
 908 * File extents can be referenced by:
 909 *
 910 * - multiple snapshots, subvolumes, or different generations in one subvol
 911 * - different files inside a single subvolume
 912 * - different offsets inside a file (bookend extents in file.c)
 913 *
 914 * The extent ref structure for the implicit back refs has fields for:
 915 *
 916 * - Objectid of the subvolume root
 917 * - objectid of the file holding the reference
 918 * - original offset in the file
 919 * - how many bookend extents
 920 *
 921 * The key offset for the implicit back refs is hash of the first
 922 * three fields.
 923 *
 924 * The extent ref structure for the full back refs has field for:
 925 *
 926 * - number of pointers in the tree leaf
 927 *
 928 * The key offset for the implicit back refs is the first byte of
 929 * the tree leaf
 930 *
 931 * When a file extent is allocated, The implicit back refs is used.
 932 * the fields are filled in:
 933 *
 934 *     (root_key.objectid, inode objectid, offset in file, 1)
 935 *
 936 * When a file extent is removed file truncation, we find the
 937 * corresponding implicit back refs and check the following fields:
 938 *
 939 *     (btrfs_header_owner(leaf), inode objectid, offset in file)
 940 *
 941 * Btree extents can be referenced by:
 942 *
 943 * - Different subvolumes
 944 *
 945 * Both the implicit back refs and the full back refs for tree blocks
 946 * only consist of key. The key offset for the implicit back refs is
 947 * objectid of block's owner tree. The key offset for the full back refs
 948 * is the first byte of parent block.
 949 *
 950 * When implicit back refs is used, information about the lowest key and
 951 * level of the tree block are required. These information are stored in
 952 * tree block info structure.
 953 */
 954
 955#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 956static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
 957                                  struct btrfs_root *root,
 958                                  struct btrfs_path *path,
 959                                  u64 owner, u32 extra_size)
 960{
 961        struct btrfs_extent_item *item;
 962        struct btrfs_extent_item_v0 *ei0;
 963        struct btrfs_extent_ref_v0 *ref0;
 964        struct btrfs_tree_block_info *bi;
 965        struct extent_buffer *leaf;
 966        struct btrfs_key key;
 967        struct btrfs_key found_key;
 968        u32 new_size = sizeof(*item);
 969        u64 refs;
 970        int ret;
 971
 972        leaf = path->nodes[0];
 973        BUG_ON(btrfs_item_size_nr(leaf, path->slots[0]) != sizeof(*ei0));
 974
 975        btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 976        ei0 = btrfs_item_ptr(leaf, path->slots[0],
 977                             struct btrfs_extent_item_v0);
 978        refs = btrfs_extent_refs_v0(leaf, ei0);
 979
 980        if (owner == (u64)-1) {
 981                while (1) {
 982                        if (path->slots[0] >= btrfs_header_nritems(leaf)) {
 983                                ret = btrfs_next_leaf(root, path);
 984                                if (ret < 0)
 985                                        return ret;
 986                                BUG_ON(ret > 0); /* Corruption */
 987                                leaf = path->nodes[0];
 988                        }
 989                        btrfs_item_key_to_cpu(leaf, &found_key,
 990                                              path->slots[0]);
 991                        BUG_ON(key.objectid != found_key.objectid);
 992                        if (found_key.type != BTRFS_EXTENT_REF_V0_KEY) {
 993                                path->slots[0]++;
 994                                continue;
 995                        }
 996                        ref0 = btrfs_item_ptr(leaf, path->slots[0],
 997                                              struct btrfs_extent_ref_v0);
 998                        owner = btrfs_ref_objectid_v0(leaf, ref0);
 999                        break;
1000                }
1001        }
1002        btrfs_release_path(path);
1003
1004        if (owner < BTRFS_FIRST_FREE_OBJECTID)
1005                new_size += sizeof(*bi);
1006
1007        new_size -= sizeof(*ei0);
1008        ret = btrfs_search_slot(trans, root, &key, path,
1009                                new_size + extra_size, 1);
1010        if (ret < 0)
1011                return ret;
1012        BUG_ON(ret); /* Corruption */
1013
1014        btrfs_extend_item(trans, root, path, new_size);
1015
1016        leaf = path->nodes[0];
1017        item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1018        btrfs_set_extent_refs(leaf, item, refs);
1019        /* FIXME: get real generation */
1020        btrfs_set_extent_generation(leaf, item, 0);
1021        if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1022                btrfs_set_extent_flags(leaf, item,
1023                                       BTRFS_EXTENT_FLAG_TREE_BLOCK |
1024                                       BTRFS_BLOCK_FLAG_FULL_BACKREF);
1025                bi = (struct btrfs_tree_block_info *)(item + 1);
1026                /* FIXME: get first key of the block */
1027                memset_extent_buffer(leaf, 0, (unsigned long)bi, sizeof(*bi));
1028                btrfs_set_tree_block_level(leaf, bi, (int)owner);
1029        } else {
1030                btrfs_set_extent_flags(leaf, item, BTRFS_EXTENT_FLAG_DATA);
1031        }
1032        btrfs_mark_buffer_dirty(leaf);
1033        return 0;
1034}
1035#endif
1036
1037static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
1038{
1039        u32 high_crc = ~(u32)0;
1040        u32 low_crc = ~(u32)0;
1041        __le64 lenum;
1042
1043        lenum = cpu_to_le64(root_objectid);
1044        high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
1045        lenum = cpu_to_le64(owner);
1046        low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
1047        lenum = cpu_to_le64(offset);
1048        low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
1049
1050        return ((u64)high_crc << 31) ^ (u64)low_crc;
1051}
1052
1053static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
1054                                     struct btrfs_extent_data_ref *ref)
1055{
1056        return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
1057                                    btrfs_extent_data_ref_objectid(leaf, ref),
1058                                    btrfs_extent_data_ref_offset(leaf, ref));
1059}
1060
1061static int match_extent_data_ref(struct extent_buffer *leaf,
1062                                 struct btrfs_extent_data_ref *ref,
1063                                 u64 root_objectid, u64 owner, u64 offset)
1064{
1065        if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
1066            btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
1067            btrfs_extent_data_ref_offset(leaf, ref) != offset)
1068                return 0;
1069        return 1;
1070}
1071
1072static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
1073                                           struct btrfs_root *root,
1074                                           struct btrfs_path *path,
1075                                           u64 bytenr, u64 parent,
1076                                           u64 root_objectid,
1077                                           u64 owner, u64 offset)
1078{
1079        struct btrfs_key key;
1080        struct btrfs_extent_data_ref *ref;
1081        struct extent_buffer *leaf;
1082        u32 nritems;
1083        int ret;
1084        int recow;
1085        int err = -ENOENT;
1086
1087        key.objectid = bytenr;
1088        if (parent) {
1089                key.type = BTRFS_SHARED_DATA_REF_KEY;
1090                key.offset = parent;
1091        } else {
1092                key.type = BTRFS_EXTENT_DATA_REF_KEY;
1093                key.offset = hash_extent_data_ref(root_objectid,
1094                                                  owner, offset);
1095        }
1096again:
1097        recow = 0;
1098        ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1099        if (ret < 0) {
1100                err = ret;
1101                goto fail;
1102        }
1103
1104        if (parent) {
1105                if (!ret)
1106                        return 0;
1107#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1108                key.type = BTRFS_EXTENT_REF_V0_KEY;
1109                btrfs_release_path(path);
1110                ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1111                if (ret < 0) {
1112                        err = ret;
1113                        goto fail;
1114                }
1115                if (!ret)
1116                        return 0;
1117#endif
1118                goto fail;
1119        }
1120
1121        leaf = path->nodes[0];
1122        nritems = btrfs_header_nritems(leaf);
1123        while (1) {
1124                if (path->slots[0] >= nritems) {
1125                        ret = btrfs_next_leaf(root, path);
1126                        if (ret < 0)
1127                                err = ret;
1128                        if (ret)
1129                                goto fail;
1130
1131                        leaf = path->nodes[0];
1132                        nritems = btrfs_header_nritems(leaf);
1133                        recow = 1;
1134                }
1135
1136                btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1137                if (key.objectid != bytenr ||
1138                    key.type != BTRFS_EXTENT_DATA_REF_KEY)
1139                        goto fail;
1140
1141                ref = btrfs_item_ptr(leaf, path->slots[0],
1142                                     struct btrfs_extent_data_ref);
1143
1144                if (match_extent_data_ref(leaf, ref, root_objectid,
1145                                          owner, offset)) {
1146                        if (recow) {
1147                                btrfs_release_path(path);
1148                                goto again;
1149                        }
1150                        err = 0;
1151                        break;
1152                }
1153                path->slots[0]++;
1154        }
1155fail:
1156        return err;
1157}
1158
1159static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
1160                                           struct btrfs_root *root,
1161                                           struct btrfs_path *path,
1162                                           u64 bytenr, u64 parent,
1163                                           u64 root_objectid, u64 owner,
1164                                           u64 offset, int refs_to_add)
1165{
1166        struct btrfs_key key;
1167        struct extent_buffer *leaf;
1168        u32 size;
1169        u32 num_refs;
1170        int ret;
1171
1172        key.objectid = bytenr;
1173        if (parent) {
1174                key.type = BTRFS_SHARED_DATA_REF_KEY;
1175                key.offset = parent;
1176                size = sizeof(struct btrfs_shared_data_ref);
1177        } else {
1178                key.type = BTRFS_EXTENT_DATA_REF_KEY;
1179                key.offset = hash_extent_data_ref(root_objectid,
1180                                                  owner, offset);
1181                size = sizeof(struct btrfs_extent_data_ref);
1182        }
1183
1184        ret = btrfs_insert_empty_item(trans, root, path, &key, size);
1185        if (ret && ret != -EEXIST)
1186                goto fail;
1187
1188        leaf = path->nodes[0];
1189        if (parent) {
1190                struct btrfs_shared_data_ref *ref;
1191                ref = btrfs_item_ptr(leaf, path->slots[0],
1192                                     struct btrfs_shared_data_ref);
1193                if (ret == 0) {
1194                        btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
1195                } else {
1196                        num_refs = btrfs_shared_data_ref_count(leaf, ref);
1197                        num_refs += refs_to_add;
1198                        btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
1199                }
1200        } else {
1201                struct btrfs_extent_data_ref *ref;
1202                while (ret == -EEXIST) {
1203                        ref = btrfs_item_ptr(leaf, path->slots[0],
1204                                             struct btrfs_extent_data_ref);
1205                        if (match_extent_data_ref(leaf, ref, root_objectid,
1206                                                  owner, offset))
1207                                break;
1208                        btrfs_release_path(path);
1209                        key.offset++;
1210                        ret = btrfs_insert_empty_item(trans, root, path, &key,
1211                                                      size);
1212                        if (ret && ret != -EEXIST)
1213                                goto fail;
1214
1215                        leaf = path->nodes[0];
1216                }
1217                ref = btrfs_item_ptr(leaf, path->slots[0],
1218                                     struct btrfs_extent_data_ref);
1219                if (ret == 0) {
1220                        btrfs_set_extent_data_ref_root(leaf, ref,
1221                                                       root_objectid);
1222                        btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
1223                        btrfs_set_extent_data_ref_offset(leaf, ref, offset);
1224                        btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
1225                } else {
1226                        num_refs = btrfs_extent_data_ref_count(leaf, ref);
1227                        num_refs += refs_to_add;
1228                        btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
1229                }
1230        }
1231        btrfs_mark_buffer_dirty(leaf);
1232        ret = 0;
1233fail:
1234        btrfs_release_path(path);
1235        return ret;
1236}
1237
1238static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
1239                                           struct btrfs_root *root,
1240                                           struct btrfs_path *path,
1241                                           int refs_to_drop)
1242{
1243        struct btrfs_key key;
1244        struct btrfs_extent_data_ref *ref1 = NULL;
1245        struct btrfs_shared_data_ref *ref2 = NULL;
1246        struct extent_buffer *leaf;
1247        u32 num_refs = 0;
1248        int ret = 0;
1249
1250        leaf = path->nodes[0];
1251        btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1252
1253        if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
1254                ref1 = btrfs_item_ptr(leaf, path->slots[0],
1255                                      struct btrfs_extent_data_ref);
1256                num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1257        } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
1258                ref2 = btrfs_item_ptr(leaf, path->slots[0],
1259                                      struct btrfs_shared_data_ref);
1260                num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1261#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1262        } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
1263                struct btrfs_extent_ref_v0 *ref0;
1264                ref0 = btrfs_item_ptr(leaf, path->slots[0],
1265                                      struct btrfs_extent_ref_v0);
1266                num_refs = btrfs_ref_count_v0(leaf, ref0);
1267#endif
1268        } else {
1269                BUG();
1270        }
1271
1272        BUG_ON(num_refs < refs_to_drop);
1273        num_refs -= refs_to_drop;
1274
1275        if (num_refs == 0) {
1276                ret = btrfs_del_item(trans, root, path);
1277        } else {
1278                if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
1279                        btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
1280                else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
1281                        btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
1282#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1283                else {
1284                        struct btrfs_extent_ref_v0 *ref0;
1285                        ref0 = btrfs_item_ptr(leaf, path->slots[0],
1286                                        struct btrfs_extent_ref_v0);
1287                        btrfs_set_ref_count_v0(leaf, ref0, num_refs);
1288                }
1289#endif
1290                btrfs_mark_buffer_dirty(leaf);
1291        }
1292        return ret;
1293}
1294
1295static noinline u32 extent_data_ref_count(struct btrfs_root *root,
1296                                          struct btrfs_path *path,
1297                                          struct btrfs_extent_inline_ref *iref)
1298{
1299        struct btrfs_key key;
1300        struct extent_buffer *leaf;
1301        struct btrfs_extent_data_ref *ref1;
1302        struct btrfs_shared_data_ref *ref2;
1303        u32 num_refs = 0;
1304
1305        leaf = path->nodes[0];
1306        btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1307        if (iref) {
1308                if (btrfs_extent_inline_ref_type(leaf, iref) ==
1309                    BTRFS_EXTENT_DATA_REF_KEY) {
1310                        ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
1311                        num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1312                } else {
1313                        ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
1314                        num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1315                }
1316        } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
1317                ref1 = btrfs_item_ptr(leaf, path->slots[0],
1318                                      struct btrfs_extent_data_ref);
1319                num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1320        } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
1321                ref2 = btrfs_item_ptr(leaf, path->slots[0],
1322                                      struct btrfs_shared_data_ref);
1323                num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1324#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1325        } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
1326                struct btrfs_extent_ref_v0 *ref0;
1327                ref0 = btrfs_item_ptr(leaf, path->slots[0],
1328                                      struct btrfs_extent_ref_v0);
1329                num_refs = btrfs_ref_count_v0(leaf, ref0);
1330#endif
1331        } else {
1332                WARN_ON(1);
1333        }
1334        return num_refs;
1335}
1336
1337static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
1338                                          struct btrfs_root *root,
1339                                          struct btrfs_path *path,
1340                                          u64 bytenr, u64 parent,
1341                                          u64 root_objectid)
1342{
1343        struct btrfs_key key;
1344        int ret;
1345
1346        key.objectid = bytenr;
1347        if (parent) {
1348                key.type = BTRFS_SHARED_BLOCK_REF_KEY;
1349                key.offset = parent;
1350        } else {
1351                key.type = BTRFS_TREE_BLOCK_REF_KEY;
1352                key.offset = root_objectid;
1353        }
1354
1355        ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1356        if (ret > 0)
1357                ret = -ENOENT;
1358#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1359        if (ret == -ENOENT && parent) {
1360                btrfs_release_path(path);
1361                key.type = BTRFS_EXTENT_REF_V0_KEY;
1362                ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1363                if (ret > 0)
1364                        ret = -ENOENT;
1365        }
1366#endif
1367        return ret;
1368}
1369
1370static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
1371                                          struct btrfs_root *root,
1372                                          struct btrfs_path *path,
1373                                          u64 bytenr, u64 parent,
1374                                          u64 root_objectid)
1375{
1376        struct btrfs_key key;
1377        int ret;
1378
1379        key.objectid = bytenr;
1380        if (parent) {
1381                key.type = BTRFS_SHARED_BLOCK_REF_KEY;
1382                key.offset = parent;
1383        } else {
1384                key.type = BTRFS_TREE_BLOCK_REF_KEY;
1385                key.offset = root_objectid;
1386        }
1387
1388        ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
1389        btrfs_release_path(path);
1390        return ret;
1391}
1392
1393static inline int extent_ref_type(u64 parent, u64 owner)
1394{
1395        int type;
1396        if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1397                if (parent > 0)
1398                        type = BTRFS_SHARED_BLOCK_REF_KEY;
1399                else
1400                        type = BTRFS_TREE_BLOCK_REF_KEY;
1401        } else {
1402                if (parent > 0)
1403                        type = BTRFS_SHARED_DATA_REF_KEY;
1404                else
1405                        type = BTRFS_EXTENT_DATA_REF_KEY;
1406        }
1407        return type;
1408}
1409
1410static int find_next_key(struct btrfs_path *path, int level,
1411                         struct btrfs_key *key)
1412
1413{
1414        for (; level < BTRFS_MAX_LEVEL; level++) {
1415                if (!path->nodes[level])
1416                        break;
1417                if (path->slots[level] + 1 >=
1418                    btrfs_header_nritems(path->nodes[level]))
1419                        continue;
1420                if (level == 0)
1421                        btrfs_item_key_to_cpu(path->nodes[level], key,
1422                                              path->slots[level] + 1);
1423                else
1424                        btrfs_node_key_to_cpu(path->nodes[level], key,
1425                                              path->slots[level] + 1);
1426                return 0;
1427        }
1428        return 1;
1429}
1430
1431/*
1432 * look for inline back ref. if back ref is found, *ref_ret is set
1433 * to the address of inline back ref, and 0 is returned.
1434 *
1435 * if back ref isn't found, *ref_ret is set to the address where it
1436 * should be inserted, and -ENOENT is returned.
1437 *
1438 * if insert is true and there are too many inline back refs, the path
1439 * points to the extent item, and -EAGAIN is returned.
1440 *
1441 * NOTE: inline back refs are ordered in the same way that back ref
1442 *       items in the tree are ordered.
1443 */
1444static noinline_for_stack
1445int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
1446                                 struct btrfs_root *root,
1447                                 struct btrfs_path *path,
1448                                 struct btrfs_extent_inline_ref **ref_ret,
1449                                 u64 bytenr, u64 num_bytes,
1450                                 u64 parent, u64 root_objectid,
1451                                 u64 owner, u64 offset, int insert)
1452{
1453        struct btrfs_key key;
1454        struct extent_buffer *leaf;
1455        struct btrfs_extent_item *ei;
1456        struct btrfs_extent_inline_ref *iref;
1457        u64 flags;
1458        u64 item_size;
1459        unsigned long ptr;
1460        unsigned long end;
1461        int extra_size;
1462        int type;
1463        int want;
1464        int ret;
1465        int err = 0;
1466
1467        key.objectid = bytenr;
1468        key.type = BTRFS_EXTENT_ITEM_KEY;
1469        key.offset = num_bytes;
1470
1471        want = extent_ref_type(parent, owner);
1472        if (insert) {
1473                extra_size = btrfs_extent_inline_ref_size(want);
1474                path->keep_locks = 1;
1475        } else
1476                extra_size = -1;
1477        ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1478        if (ret < 0) {
1479                err = ret;
1480                goto out;
1481        }
1482        if (ret && !insert) {
1483                err = -ENOENT;
1484                goto out;
1485        }
1486        BUG_ON(ret); /* Corruption */
1487
1488        leaf = path->nodes[0];
1489        item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1490#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1491        if (item_size < sizeof(*ei)) {
1492                if (!insert) {
1493                        err = -ENOENT;
1494                        goto out;
1495                }
1496                ret = convert_extent_item_v0(trans, root, path, owner,
1497                                             extra_size);
1498                if (ret < 0) {
1499                        err = ret;
1500                        goto out;
1501                }
1502                leaf = path->nodes[0];
1503                item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1504        }
1505#endif
1506        BUG_ON(item_size < sizeof(*ei));
1507
1508        ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1509        flags = btrfs_extent_flags(leaf, ei);
1510
1511        ptr = (unsigned long)(ei + 1);
1512        end = (unsigned long)ei + item_size;
1513
1514        if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1515                ptr += sizeof(struct btrfs_tree_block_info);
1516                BUG_ON(ptr > end);
1517        } else {
1518                BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
1519        }
1520
1521        err = -ENOENT;
1522        while (1) {
1523                if (ptr >= end) {
1524                        WARN_ON(ptr > end);
1525                        break;
1526                }
1527                iref = (struct btrfs_extent_inline_ref *)ptr;
1528                type = btrfs_extent_inline_ref_type(leaf, iref);
1529                if (want < type)
1530                        break;
1531                if (want > type) {
1532                        ptr += btrfs_extent_inline_ref_size(type);
1533                        continue;
1534                }
1535
1536                if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1537                        struct btrfs_extent_data_ref *dref;
1538                        dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1539                        if (match_extent_data_ref(leaf, dref, root_objectid,
1540                                                  owner, offset)) {
1541                                err = 0;
1542                                break;
1543                        }
1544                        if (hash_extent_data_ref_item(leaf, dref) <
1545                            hash_extent_data_ref(root_objectid, owner, offset))
1546                                break;
1547                } else {
1548                        u64 ref_offset;
1549                        ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1550                        if (parent > 0) {
1551                                if (parent == ref_offset) {
1552                                        err = 0;
1553                                        break;
1554                                }
1555                                if (ref_offset < parent)
1556                                        break;
1557                        } else {
1558                                if (root_objectid == ref_offset) {
1559                                        err = 0;
1560                                        break;
1561                                }
1562                                if (ref_offset < root_objectid)
1563                                        break;
1564                        }
1565                }
1566                ptr += btrfs_extent_inline_ref_size(type);
1567        }
1568        if (err == -ENOENT && insert) {
1569                if (item_size + extra_size >=
1570                    BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1571                        err = -EAGAIN;
1572                        goto out;
1573                }
1574                /*
1575                 * To add new inline back ref, we have to make sure
1576                 * there is no corresponding back ref item.
1577                 * For simplicity, we just do not add new inline back
1578                 * ref if there is any kind of item for this block
1579                 */
1580                if (find_next_key(path, 0, &key) == 0 &&
1581                    key.objectid == bytenr &&
1582                    key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
1583                        err = -EAGAIN;
1584                        goto out;
1585                }
1586        }
1587        *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1588out:
1589        if (insert) {
1590                path->keep_locks = 0;
1591                btrfs_unlock_up_safe(path, 1);
1592        }
1593        return err;
1594}
1595
1596/*
1597 * helper to add new inline back ref
1598 */
1599static noinline_for_stack
1600void setup_inline_extent_backref(struct btrfs_trans_handle *trans,
1601                                 struct btrfs_root *root,
1602                                 struct btrfs_path *path,
1603                                 struct btrfs_extent_inline_ref *iref,
1604                                 u64 parent, u64 root_objectid,
1605                                 u64 owner, u64 offset, int refs_to_add,
1606                                 struct btrfs_delayed_extent_op *extent_op)
1607{
1608        struct extent_buffer *leaf;
1609        struct btrfs_extent_item *ei;
1610        unsigned long ptr;
1611        unsigned long end;
1612        unsigned long item_offset;
1613        u64 refs;
1614        int size;
1615        int type;
1616
1617        leaf = path->nodes[0];
1618        ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1619        item_offset = (unsigned long)iref - (unsigned long)ei;
1620
1621        type = extent_ref_type(parent, owner);
1622        size = btrfs_extent_inline_ref_size(type);
1623
1624        btrfs_extend_item(trans, root, path, size);
1625
1626        ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1627        refs = btrfs_extent_refs(leaf, ei);
1628        refs += refs_to_add;
1629        btrfs_set_extent_refs(leaf, ei, refs);
1630        if (extent_op)
1631                __run_delayed_extent_op(extent_op, leaf, ei);
1632
1633        ptr = (unsigned long)ei + item_offset;
1634        end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1635        if (ptr < end - size)
1636                memmove_extent_buffer(leaf, ptr + size, ptr,
1637                                      end - size - ptr);
1638
1639        iref = (struct btrfs_extent_inline_ref *)ptr;
1640        btrfs_set_extent_inline_ref_type(leaf, iref, type);
1641        if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1642                struct btrfs_extent_data_ref *dref;
1643                dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1644                btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1645                btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1646                btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1647                btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1648        } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1649                struct btrfs_shared_data_ref *sref;
1650                sref = (struct btrfs_shared_data_ref *)(iref + 1);
1651                btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1652                btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1653        } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1654                btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1655        } else {
1656                btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1657        }
1658        btrfs_mark_buffer_dirty(leaf);
1659}
1660
1661static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1662                                 struct btrfs_root *root,
1663                                 struct btrfs_path *path,
1664                                 struct btrfs_extent_inline_ref **ref_ret,
1665                                 u64 bytenr, u64 num_bytes, u64 parent,
1666                                 u64 root_objectid, u64 owner, u64 offset)
1667{
1668        int ret;
1669
1670        ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
1671                                           bytenr, num_bytes, parent,
1672                                           root_objectid, owner, offset, 0);
1673        if (ret != -ENOENT)
1674                return ret;
1675
1676        btrfs_release_path(path);
1677        *ref_ret = NULL;
1678
1679        if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1680                ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
1681                                            root_objectid);
1682        } else {
1683                ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
1684                                             root_objectid, owner, offset);
1685        }
1686        return ret;
1687}
1688
1689/*
1690 * helper to update/remove inline back ref
1691 */
1692static noinline_for_stack
1693void update_inline_extent_backref(struct btrfs_trans_handle *trans,
1694                                  struct btrfs_root *root,
1695                                  struct btrfs_path *path,
1696                                  struct btrfs_extent_inline_ref *iref,
1697                                  int refs_to_mod,
1698                                  struct btrfs_delayed_extent_op *extent_op)
1699{
1700        struct extent_buffer *leaf;
1701        struct btrfs_extent_item *ei;
1702        struct btrfs_extent_data_ref *dref = NULL;
1703        struct btrfs_shared_data_ref *sref = NULL;
1704        unsigned long ptr;
1705        unsigned long end;
1706        u32 item_size;
1707        int size;
1708        int type;
1709        u64 refs;
1710
1711        leaf = path->nodes[0];
1712        ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1713        refs = btrfs_extent_refs(leaf, ei);
1714        WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1715        refs += refs_to_mod;
1716        btrfs_set_extent_refs(leaf, ei, refs);
1717        if (extent_op)
1718                __run_delayed_extent_op(extent_op, leaf, ei);
1719
1720        type = btrfs_extent_inline_ref_type(leaf, iref);
1721
1722        if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1723                dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1724                refs = btrfs_extent_data_ref_count(leaf, dref);
1725        } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1726                sref = (struct btrfs_shared_data_ref *)(iref + 1);
1727                refs = btrfs_shared_data_ref_count(leaf, sref);
1728        } else {
1729                refs = 1;
1730                BUG_ON(refs_to_mod != -1);
1731        }
1732
1733        BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1734        refs += refs_to_mod;
1735
1736        if (refs > 0) {
1737                if (type == BTRFS_EXTENT_DATA_REF_KEY)
1738                        btrfs_set_extent_data_ref_count(leaf, dref, refs);
1739                else
1740                        btrfs_set_shared_data_ref_count(leaf, sref, refs);
1741        } else {
1742                size =  btrfs_extent_inline_ref_size(type);
1743                item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1744                ptr = (unsigned long)iref;
1745                end = (unsigned long)ei + item_size;
1746                if (ptr + size < end)
1747                        memmove_extent_buffer(leaf, ptr, ptr + size,
1748                                              end - ptr - size);
1749                item_size -= size;
1750                btrfs_truncate_item(trans, root, path, item_size, 1);
1751        }
1752        btrfs_mark_buffer_dirty(leaf);
1753}
1754
1755static noinline_for_stack
1756int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1757                                 struct btrfs_root *root,
1758                                 struct btrfs_path *path,
1759                                 u64 bytenr, u64 num_bytes, u64 parent,
1760                                 u64 root_objectid, u64 owner,
1761                                 u64 offset, int refs_to_add,
1762                                 struct btrfs_delayed_extent_op *extent_op)
1763{
1764        struct btrfs_extent_inline_ref *iref;
1765        int ret;
1766
1767        ret = lookup_inline_extent_backref(trans, root, path, &iref,
1768                                           bytenr, num_bytes, parent,
1769                                           root_objectid, owner, offset, 1);
1770        if (ret == 0) {
1771                BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1772                update_inline_extent_backref(trans, root, path, iref,
1773                                             refs_to_add, extent_op);
1774        } else if (ret == -ENOENT) {
1775                setup_inline_extent_backref(trans, root, path, iref, parent,
1776                                            root_objectid, owner, offset,
1777                                            refs_to_add, extent_op);
1778                ret = 0;
1779        }
1780        return ret;
1781}
1782
1783static int insert_extent_backref(struct btrfs_trans_handle *trans,
1784                                 struct btrfs_root *root,
1785                                 struct btrfs_path *path,
1786                                 u64 bytenr, u64 parent, u64 root_objectid,
1787                                 u64 owner, u64 offset, int refs_to_add)
1788{
1789        int ret;
1790        if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1791                BUG_ON(refs_to_add != 1);
1792                ret = insert_tree_block_ref(trans, root, path, bytenr,
1793                                            parent, root_objectid);
1794        } else {
1795                ret = insert_extent_data_ref(trans, root, path, bytenr,
1796                                             parent, root_objectid,
1797                                             owner, offset, refs_to_add);
1798        }
1799        return ret;
1800}
1801
1802static int remove_extent_backref(struct btrfs_trans_handle *trans,
1803                                 struct btrfs_root *root,
1804                                 struct btrfs_path *path,
1805                                 struct btrfs_extent_inline_ref *iref,
1806                                 int refs_to_drop, int is_data)
1807{
1808        int ret = 0;
1809
1810        BUG_ON(!is_data && refs_to_drop != 1);
1811        if (iref) {
1812                update_inline_extent_backref(trans, root, path, iref,
1813                                             -refs_to_drop, NULL);
1814        } else if (is_data) {
1815                ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1816        } else {
1817                ret = btrfs_del_item(trans, root, path);
1818        }
1819        return ret;
1820}
1821
1822static int btrfs_issue_discard(struct block_device *bdev,
1823                                u64 start, u64 len)
1824{
1825        return blkdev_issue_discard(bdev, start >> 9, len >> 9, GFP_NOFS, 0);
1826}
1827
1828static int btrfs_discard_extent(struct btrfs_root *root, u64 bytenr,
1829                                u64 num_bytes, u64 *actual_bytes)
1830{
1831        int ret;
1832        u64 discarded_bytes = 0;
1833        struct btrfs_bio *bbio = NULL;
1834
1835
1836        /* Tell the block device(s) that the sectors can be discarded */
1837        ret = btrfs_map_block(&root->fs_info->mapping_tree, REQ_DISCARD,
1838                              bytenr, &num_bytes, &bbio, 0);
1839        /* Error condition is -ENOMEM */
1840        if (!ret) {
1841                struct btrfs_bio_stripe *stripe = bbio->stripes;
1842                int i;
1843
1844
1845                for (i = 0; i < bbio->num_stripes; i++, stripe++) {
1846                        if (!stripe->dev->can_discard)
1847                                continue;
1848
1849                        ret = btrfs_issue_discard(stripe->dev->bdev,
1850                                                  stripe->physical,
1851                                                  stripe->length);
1852                        if (!ret)
1853                                discarded_bytes += stripe->length;
1854                        else if (ret != -EOPNOTSUPP)
1855                                break; /* Logic errors or -ENOMEM, or -EIO but I don't know how that could happen JDM */
1856
1857                        /*
1858                         * Just in case we get back EOPNOTSUPP for some reason,
1859                         * just ignore the return value so we don't screw up
1860                         * people calling discard_extent.
1861                         */
1862                        ret = 0;
1863                }
1864                kfree(bbio);
1865        }
1866
1867        if (actual_bytes)
1868                *actual_bytes = discarded_bytes;
1869
1870
1871        return ret;
1872}
1873
1874/* Can return -ENOMEM */
1875int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1876                         struct btrfs_root *root,
1877                         u64 bytenr, u64 num_bytes, u64 parent,
1878                         u64 root_objectid, u64 owner, u64 offset, int for_cow)
1879{
1880        int ret;
1881        struct btrfs_fs_info *fs_info = root->fs_info;
1882
1883        BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID &&
1884               root_objectid == BTRFS_TREE_LOG_OBJECTID);
1885
1886        if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1887                ret = btrfs_add_delayed_tree_ref(fs_info, trans, bytenr,
1888                                        num_bytes,
1889                                        parent, root_objectid, (int)owner,
1890                                        BTRFS_ADD_DELAYED_REF, NULL, for_cow);
1891        } else {
1892                ret = btrfs_add_delayed_data_ref(fs_info, trans, bytenr,
1893                                        num_bytes,
1894                                        parent, root_objectid, owner, offset,
1895                                        BTRFS_ADD_DELAYED_REF, NULL, for_cow);
1896        }
1897        return ret;
1898}
1899
1900static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1901                                  struct btrfs_root *root,
1902                                  u64 bytenr, u64 num_bytes,
1903                                  u64 parent, u64 root_objectid,
1904                                  u64 owner, u64 offset, int refs_to_add,
1905                                  struct btrfs_delayed_extent_op *extent_op)
1906{
1907        struct btrfs_path *path;
1908        struct extent_buffer *leaf;
1909        struct btrfs_extent_item *item;
1910        u64 refs;
1911        int ret;
1912        int err = 0;
1913
1914        path = btrfs_alloc_path();
1915        if (!path)
1916                return -ENOMEM;
1917
1918        path->reada = 1;
1919        path->leave_spinning = 1;
1920        /* this will setup the path even if it fails to insert the back ref */
1921        ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
1922                                           path, bytenr, num_bytes, parent,
1923                                           root_objectid, owner, offset,
1924                                           refs_to_add, extent_op);
1925        if (ret == 0)
1926                goto out;
1927
1928        if (ret != -EAGAIN) {
1929                err = ret;
1930                goto out;
1931        }
1932
1933        leaf = path->nodes[0];
1934        item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1935        refs = btrfs_extent_refs(leaf, item);
1936        btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
1937        if (extent_op)
1938                __run_delayed_extent_op(extent_op, leaf, item);
1939
1940        btrfs_mark_buffer_dirty(leaf);
1941        btrfs_release_path(path);
1942
1943        path->reada = 1;
1944        path->leave_spinning = 1;
1945
1946        /* now insert the actual backref */
1947        ret = insert_extent_backref(trans, root->fs_info->extent_root,
1948                                    path, bytenr, parent, root_objectid,
1949                                    owner, offset, refs_to_add);
1950        if (ret)
1951                btrfs_abort_transaction(trans, root, ret);
1952out:
1953        btrfs_free_path(path);
1954        return err;
1955}
1956
1957static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
1958                                struct btrfs_root *root,
1959                                struct btrfs_delayed_ref_node *node,
1960                                struct btrfs_delayed_extent_op *extent_op,
1961                                int insert_reserved)
1962{
1963        int ret = 0;
1964        struct btrfs_delayed_data_ref *ref;
1965        struct btrfs_key ins;
1966        u64 parent = 0;
1967        u64 ref_root = 0;
1968        u64 flags = 0;
1969
1970        ins.objectid = node->bytenr;
1971        ins.offset = node->num_bytes;
1972        ins.type = BTRFS_EXTENT_ITEM_KEY;
1973
1974        ref = btrfs_delayed_node_to_data_ref(node);
1975        if (node->type == BTRFS_SHARED_DATA_REF_KEY)
1976                parent = ref->parent;
1977        else
1978                ref_root = ref->root;
1979
1980        if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1981                if (extent_op) {
1982                        BUG_ON(extent_op->update_key);
1983                        flags |= extent_op->flags_to_set;
1984                }
1985                ret = alloc_reserved_file_extent(trans, root,
1986                                                 parent, ref_root, flags,
1987                                                 ref->objectid, ref->offset,
1988                                                 &ins, node->ref_mod);
1989        } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1990                ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
1991                                             node->num_bytes, parent,
1992                                             ref_root, ref->objectid,
1993                                             ref->offset, node->ref_mod,
1994                                             extent_op);
1995        } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1996                ret = __btrfs_free_extent(trans, root, node->bytenr,
1997                                          node->num_bytes, parent,
1998                                          ref_root, ref->objectid,
1999                                          ref->offset, node->ref_mod,
2000                                          extent_op);
2001        } else {
2002                BUG();
2003        }
2004        return ret;
2005}
2006
2007static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
2008                                    struct extent_buffer *leaf,
2009                                    struct btrfs_extent_item *ei)
2010{
2011        u64 flags = btrfs_extent_flags(leaf, ei);
2012        if (extent_op->update_flags) {
2013                flags |= extent_op->flags_to_set;
2014                btrfs_set_extent_flags(leaf, ei, flags);
2015        }
2016
2017        if (extent_op->update_key) {
2018                struct btrfs_tree_block_info *bi;
2019                BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
2020                bi = (struct btrfs_tree_block_info *)(ei + 1);
2021                btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
2022        }
2023}
2024
2025static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
2026                                 struct btrfs_root *root,
2027                                 struct btrfs_delayed_ref_node *node,
2028                                 struct btrfs_delayed_extent_op *extent_op)
2029{
2030        struct btrfs_key key;
2031        struct btrfs_path *path;
2032        struct btrfs_extent_item *ei;
2033        struct extent_buffer *leaf;
2034        u32 item_size;
2035        int ret;
2036        int err = 0;
2037
2038        if (trans->aborted)
2039                return 0;
2040
2041        path = btrfs_alloc_path();
2042        if (!path)
2043                return -ENOMEM;
2044
2045        key.objectid = node->bytenr;
2046        key.type = BTRFS_EXTENT_ITEM_KEY;
2047        key.offset = node->num_bytes;
2048
2049        path->reada = 1;
2050        path->leave_spinning = 1;
2051        ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key,
2052                                path, 0, 1);
2053        if (ret < 0) {
2054                err = ret;
2055                goto out;
2056        }
2057        if (ret > 0) {
2058                err = -EIO;
2059                goto out;
2060        }
2061
2062        leaf = path->nodes[0];
2063        item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2064#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2065        if (item_size < sizeof(*ei)) {
2066                ret = convert_extent_item_v0(trans, root->fs_info->extent_root,
2067                                             path, (u64)-1, 0);
2068                if (ret < 0) {
2069                        err = ret;
2070                        goto out;
2071                }
2072                leaf = path->nodes[0];
2073                item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2074        }
2075#endif
2076        BUG_ON(item_size < sizeof(*ei));
2077        ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2078        __run_delayed_extent_op(extent_op, leaf, ei);
2079
2080        btrfs_mark_buffer_dirty(leaf);
2081out:
2082        btrfs_free_path(path);
2083        return err;
2084}
2085
2086static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
2087                                struct btrfs_root *root,
2088                                struct btrfs_delayed_ref_node *node,
2089                                struct btrfs_delayed_extent_op *extent_op,
2090                                int insert_reserved)
2091{
2092        int ret = 0;
2093        struct btrfs_delayed_tree_ref *ref;
2094        struct btrfs_key ins;
2095        u64 parent = 0;
2096        u64 ref_root = 0;
2097
2098        ins.objectid = node->bytenr;
2099        ins.offset = node->num_bytes;
2100        ins.type = BTRFS_EXTENT_ITEM_KEY;
2101
2102        ref = btrfs_delayed_node_to_tree_ref(node);
2103        if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
2104                parent = ref->parent;
2105        else
2106                ref_root = ref->root;
2107
2108        BUG_ON(node->ref_mod != 1);
2109        if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
2110                BUG_ON(!extent_op || !extent_op->update_flags ||
2111                       !extent_op->update_key);
2112                ret = alloc_reserved_tree_block(trans, root,
2113                                                parent, ref_root,
2114                                                extent_op->flags_to_set,
2115                                                &extent_op->key,
2116                                                ref->level, &ins);
2117        } else if (node->action == BTRFS_ADD_DELAYED_REF) {
2118                ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
2119                                             node->num_bytes, parent, ref_root,
2120                                             ref->level, 0, 1, extent_op);
2121        } else if (node->action == BTRFS_DROP_DELAYED_REF) {
2122                ret = __btrfs_free_extent(trans, root, node->bytenr,
2123                                          node->num_bytes, parent, ref_root,
2124                                          ref->level, 0, 1, extent_op);
2125        } else {
2126                BUG();
2127        }
2128        return ret;
2129}
2130
2131/* helper function to actually process a single delayed ref entry */
2132static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
2133                               struct btrfs_root *root,
2134                               struct btrfs_delayed_ref_node *node,
2135                               struct btrfs_delayed_extent_op *extent_op,
2136                               int insert_reserved)
2137{
2138        int ret = 0;
2139
2140        if (trans->aborted)
2141                return 0;
2142
2143        if (btrfs_delayed_ref_is_head(node)) {
2144                struct btrfs_delayed_ref_head *head;
2145                /*
2146                 * we've hit the end of the chain and we were supposed
2147                 * to insert this extent into the tree.  But, it got
2148                 * deleted before we ever needed to insert it, so all
2149                 * we have to do is clean up the accounting
2150                 */
2151                BUG_ON(extent_op);
2152                head = btrfs_delayed_node_to_head(node);
2153                if (insert_reserved) {
2154                        btrfs_pin_extent(root, node->bytenr,
2155                                         node->num_bytes, 1);
2156                        if (head->is_data) {
2157                                ret = btrfs_del_csums(trans, root,
2158                                                      node->bytenr,
2159                                                      node->num_bytes);
2160                        }
2161                }
2162                mutex_unlock(&head->mutex);
2163                return ret;
2164        }
2165
2166        if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
2167            node->type == BTRFS_SHARED_BLOCK_REF_KEY)
2168                ret = run_delayed_tree_ref(trans, root, node, extent_op,
2169                                           insert_reserved);
2170        else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
2171                 node->type == BTRFS_SHARED_DATA_REF_KEY)
2172                ret = run_delayed_data_ref(trans, root, node, extent_op,
2173                                           insert_reserved);
2174        else
2175                BUG();
2176        return ret;
2177}
2178
2179static noinline struct btrfs_delayed_ref_node *
2180select_delayed_ref(struct btrfs_delayed_ref_head *head)
2181{
2182        struct rb_node *node;
2183        struct btrfs_delayed_ref_node *ref;
2184        int action = BTRFS_ADD_DELAYED_REF;
2185again:
2186        /*
2187         * select delayed ref of type BTRFS_ADD_DELAYED_REF first.
2188         * this prevents ref count from going down to zero when
2189         * there still are pending delayed ref.
2190         */
2191        node = rb_prev(&head->node.rb_node);
2192        while (1) {
2193                if (!node)
2194                        break;
2195                ref = rb_entry(node, struct btrfs_delayed_ref_node,
2196                                rb_node);
2197                if (ref->bytenr != head->node.bytenr)
2198                        break;
2199                if (ref->action == action)
2200                        return ref;
2201                node = rb_prev(node);
2202        }
2203        if (action == BTRFS_ADD_DELAYED_REF) {
2204                action = BTRFS_DROP_DELAYED_REF;
2205                goto again;
2206        }
2207        return NULL;
2208}
2209
2210/*
2211 * Returns 0 on success or if called with an already aborted transaction.
2212 * Returns -ENOMEM or -EIO on failure and will abort the transaction.
2213 */
2214static noinline int run_clustered_refs(struct btrfs_trans_handle *trans,
2215                                       struct btrfs_root *root,
2216                                       struct list_head *cluster)
2217{
2218        struct btrfs_delayed_ref_root *delayed_refs;
2219        struct btrfs_delayed_ref_node *ref;
2220        struct btrfs_delayed_ref_head *locked_ref = NULL;
2221        struct btrfs_delayed_extent_op *extent_op;
2222        struct btrfs_fs_info *fs_info = root->fs_info;
2223        int ret;
2224        int count = 0;
2225        int must_insert_reserved = 0;
2226
2227        delayed_refs = &trans->transaction->delayed_refs;
2228        while (1) {
2229                if (!locked_ref) {
2230                        /* pick a new head ref from the cluster list */
2231                        if (list_empty(cluster))
2232                                break;
2233
2234                        locked_ref = list_entry(cluster->next,
2235                                     struct btrfs_delayed_ref_head, cluster);
2236
2237                        /* grab the lock that says we are going to process
2238                         * all the refs for this head */
2239                        ret = btrfs_delayed_ref_lock(trans, locked_ref);
2240
2241                        /*
2242                         * we may have dropped the spin lock to get the head
2243                         * mutex lock, and that might have given someone else
2244                         * time to free the head.  If that's true, it has been
2245                         * removed from our list and we can move on.
2246                         */
2247                        if (ret == -EAGAIN) {
2248                                locked_ref = NULL;
2249                                count++;
2250                                continue;
2251                        }
2252                }
2253
2254                /*
2255                 * We need to try and merge add/drops of the same ref since we
2256                 * can run into issues with relocate dropping the implicit ref
2257                 * and then it being added back again before the drop can
2258                 * finish.  If we merged anything we need to re-loop so we can
2259                 * get a good ref.
2260                 */
2261                btrfs_merge_delayed_refs(trans, fs_info, delayed_refs,
2262                                         locked_ref);
2263
2264                /*
2265                 * locked_ref is the head node, so we have to go one
2266                 * node back for any delayed ref updates
2267                 */
2268                ref = select_delayed_ref(locked_ref);
2269
2270                if (ref && ref->seq &&
2271                    btrfs_check_delayed_seq(fs_info, delayed_refs, ref->seq)) {
2272                        /*
2273                         * there are still refs with lower seq numbers in the
2274                         * process of being added. Don't run this ref yet.
2275                         */
2276                        list_del_init(&locked_ref->cluster);
2277                        mutex_unlock(&locked_ref->mutex);
2278                        locked_ref = NULL;
2279                        delayed_refs->num_heads_ready++;
2280                        spin_unlock(&delayed_refs->lock);
2281                        cond_resched();
2282                        spin_lock(&delayed_refs->lock);
2283                        continue;
2284                }
2285
2286                /*
2287                 * record the must insert reserved flag before we
2288                 * drop the spin lock.
2289                 */
2290                must_insert_reserved = locked_ref->must_insert_reserved;
2291                locked_ref->must_insert_reserved = 0;
2292
2293                extent_op = locked_ref->extent_op;
2294                locked_ref->extent_op = NULL;
2295
2296                if (!ref) {
2297                        /* All delayed refs have been processed, Go ahead
2298                         * and send the head node to run_one_delayed_ref,
2299                         * so that any accounting fixes can happen
2300                         */
2301                        ref = &locked_ref->node;
2302
2303                        if (extent_op && must_insert_reserved) {
2304                                kfree(extent_op);
2305                                extent_op = NULL;
2306                        }
2307
2308                        if (extent_op) {
2309                                spin_unlock(&delayed_refs->lock);
2310
2311                                ret = run_delayed_extent_op(trans, root,
2312                                                            ref, extent_op);
2313                                kfree(extent_op);
2314
2315                                if (ret) {
2316                                        printk(KERN_DEBUG "btrfs: run_delayed_extent_op returned %d\n", ret);
2317                                        spin_lock(&delayed_refs->lock);
2318                                        return ret;
2319                                }
2320
2321                                goto next;
2322                        }
2323
2324                        list_del_init(&locked_ref->cluster);
2325                        locked_ref = NULL;
2326                }
2327
2328                ref->in_tree = 0;
2329                rb_erase(&ref->rb_node, &delayed_refs->root);
2330                delayed_refs->num_entries--;
2331                if (locked_ref) {
2332                        /*
2333                         * when we play the delayed ref, also correct the
2334                         * ref_mod on head
2335                         */
2336                        switch (ref->action) {
2337                        case BTRFS_ADD_DELAYED_REF:
2338                        case BTRFS_ADD_DELAYED_EXTENT:
2339                                locked_ref->node.ref_mod -= ref->ref_mod;
2340                                break;
2341                        case BTRFS_DROP_DELAYED_REF:
2342                                locked_ref->node.ref_mod += ref->ref_mod;
2343                                break;
2344                        default:
2345                                WARN_ON(1);
2346                        }
2347                }
2348                spin_unlock(&delayed_refs->lock);
2349
2350                ret = run_one_delayed_ref(trans, root, ref, extent_op,
2351                                          must_insert_reserved);
2352
2353                btrfs_put_delayed_ref(ref);
2354                kfree(extent_op);
2355                count++;
2356
2357                if (ret) {
2358                        printk(KERN_DEBUG "btrfs: run_one_delayed_ref returned %d\n", ret);
2359                        spin_lock(&delayed_refs->lock);
2360                        return ret;
2361                }
2362
2363next:
2364                do_chunk_alloc(trans, fs_info->extent_root,
2365                               2 * 1024 * 1024,
2366                               btrfs_get_alloc_profile(root, 0),
2367                               CHUNK_ALLOC_NO_FORCE);
2368                cond_resched();
2369                spin_lock(&delayed_refs->lock);
2370        }
2371        return count;
2372}
2373
2374#ifdef SCRAMBLE_DELAYED_REFS
2375/*
2376 * Normally delayed refs get processed in ascending bytenr order. This
2377 * correlates in most cases to the order added. To expose dependencies on this
2378 * order, we start to process the tree in the middle instead of the beginning
2379 */
2380static u64 find_middle(struct rb_root *root)
2381{
2382        struct rb_node *n = root->rb_node;
2383        struct btrfs_delayed_ref_node *entry;
2384        int alt = 1;
2385        u64 middle;
2386        u64 first = 0, last = 0;
2387
2388        n = rb_first(root);
2389        if (n) {
2390                entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2391                first = entry->bytenr;
2392        }
2393        n = rb_last(root);
2394        if (n) {
2395                entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2396                last = entry->bytenr;
2397        }
2398        n = root->rb_node;
2399
2400        while (n) {
2401                entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2402                WARN_ON(!entry->in_tree);
2403
2404                middle = entry->bytenr;
2405
2406                if (alt)
2407                        n = n->rb_left;
2408                else
2409                        n = n->rb_right;
2410
2411                alt = 1 - alt;
2412        }
2413        return middle;
2414}
2415#endif
2416
2417int btrfs_delayed_refs_qgroup_accounting(struct btrfs_trans_handle *trans,
2418                                         struct btrfs_fs_info *fs_info)
2419{
2420        struct qgroup_update *qgroup_update;
2421        int ret = 0;
2422
2423        if (list_empty(&trans->qgroup_ref_list) !=
2424            !trans->delayed_ref_elem.seq) {
2425                /* list without seq or seq without list */
2426                printk(KERN_ERR "btrfs: qgroup accounting update error, list is%s empty, seq is %llu\n",
2427                        list_empty(&trans->qgroup_ref_list) ? "" : " not",
2428                        trans->delayed_ref_elem.seq);
2429                BUG();
2430        }
2431
2432        if (!trans->delayed_ref_elem.seq)
2433                return 0;
2434
2435        while (!list_empty(&trans->qgroup_ref_list)) {
2436                qgroup_update = list_first_entry(&trans->qgroup_ref_list,
2437                                                 struct qgroup_update, list);
2438                list_del(&qgroup_update->list);
2439                if (!ret)
2440                        ret = btrfs_qgroup_account_ref(
2441                                        trans, fs_info, qgroup_update->node,
2442                                        qgroup_update->extent_op);
2443                kfree(qgroup_update);
2444        }
2445
2446        btrfs_put_tree_mod_seq(fs_info, &trans->delayed_ref_elem);
2447
2448        return ret;
2449}
2450
2451/*
2452 * this starts processing the delayed reference count updates and
2453 * extent insertions we have queued up so far.  count can be
2454 * 0, which means to process everything in the tree at the start
2455 * of the run (but not newly added entries), or it can be some target
2456 * number you'd like to process.
2457 *
2458 * Returns 0 on success or if called with an aborted transaction
2459 * Returns <0 on error and aborts the transaction
2460 */
2461int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
2462                           struct btrfs_root *root, unsigned long count)
2463{
2464        struct rb_node *node;
2465        struct btrfs_delayed_ref_root *delayed_refs;
2466        struct btrfs_delayed_ref_node *ref;
2467        struct list_head cluster;
2468        int ret;
2469        u64 delayed_start;
2470        int run_all = count == (unsigned long)-1;
2471        int run_most = 0;
2472        int loops;
2473
2474        /* We'll clean this up in btrfs_cleanup_transaction */
2475        if (trans->aborted)
2476                return 0;
2477
2478        if (root == root->fs_info->extent_root)
2479                root = root->fs_info->tree_root;
2480
2481        do_chunk_alloc(trans, root->fs_info->extent_root,
2482                       2 * 1024 * 1024, btrfs_get_alloc_profile(root, 0),
2483                       CHUNK_ALLOC_NO_FORCE);
2484
2485        btrfs_delayed_refs_qgroup_accounting(trans, root->fs_info);
2486
2487        delayed_refs = &trans->transaction->delayed_refs;
2488        INIT_LIST_HEAD(&cluster);
2489again:
2490        loops = 0;
2491        spin_lock(&delayed_refs->lock);
2492
2493#ifdef SCRAMBLE_DELAYED_REFS
2494        delayed_refs->run_delayed_start = find_middle(&delayed_refs->root);
2495#endif
2496
2497        if (count == 0) {
2498                count = delayed_refs->num_entries * 2;
2499                run_most = 1;
2500        }
2501        while (1) {
2502                if (!(run_all || run_most) &&
2503                    delayed_refs->num_heads_ready < 64)
2504                        break;
2505
2506                /*
2507                 * go find something we can process in the rbtree.  We start at
2508                 * the beginning of the tree, and then build a cluster
2509                 * of refs to process starting at the first one we are able to
2510                 * lock
2511                 */
2512                delayed_start = delayed_refs->run_delayed_start;
2513                ret = btrfs_find_ref_cluster(trans, &cluster,
2514                                             delayed_refs->run_delayed_start);
2515                if (ret)
2516                        break;
2517
2518                ret = run_clustered_refs(trans, root, &cluster);
2519                if (ret < 0) {
2520                        spin_unlock(&delayed_refs->lock);
2521                        btrfs_abort_transaction(trans, root, ret);
2522                        return ret;
2523                }
2524
2525                count -= min_t(unsigned long, ret, count);
2526
2527                if (count == 0)
2528                        break;
2529
2530                if (delayed_start >= delayed_refs->run_delayed_start) {
2531                        if (loops == 0) {
2532                                /*
2533                                 * btrfs_find_ref_cluster looped. let's do one
2534                                 * more cycle. if we don't run any delayed ref
2535                                 * during that cycle (because we can't because
2536                                 * all of them are blocked), bail out.
2537                                 */
2538                                loops = 1;
2539                        } else {
2540                                /*
2541                                 * no runnable refs left, stop trying
2542                                 */
2543                                BUG_ON(run_all);
2544                                break;
2545                        }
2546                }
2547                if (ret) {
2548                        /* refs were run, let's reset staleness detection */
2549                        loops = 0;
2550                }
2551        }
2552
2553        if (run_all) {
2554                node = rb_first(&delayed_refs->root);
2555                if (!node)
2556                        goto out;
2557                count = (unsigned long)-1;
2558
2559                while (node) {
2560                        ref = rb_entry(node, struct btrfs_delayed_ref_node,
2561                                       rb_node);
2562                        if (btrfs_delayed_ref_is_head(ref)) {
2563                                struct btrfs_delayed_ref_head *head;
2564
2565                                head = btrfs_delayed_node_to_head(ref);
2566                                atomic_inc(&ref->refs);
2567
2568                                spin_unlock(&delayed_refs->lock);
2569                                /*
2570                                 * Mutex was contended, block until it's
2571                                 * released and try again
2572                                 */
2573                                mutex_lock(&head->mutex);
2574                                mutex_unlock(&head->mutex);
2575
2576                                btrfs_put_delayed_ref(ref);
2577                                cond_resched();
2578                                goto again;
2579                        }
2580                        node = rb_next(node);
2581                }
2582                spin_unlock(&delayed_refs->lock);
2583                schedule_timeout(1);
2584                goto again;
2585        }
2586out:
2587        spin_unlock(&delayed_refs->lock);
2588        assert_qgroups_uptodate(trans);
2589        return 0;
2590}
2591
2592int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
2593                                struct btrfs_root *root,
2594                                u64 bytenr, u64 num_bytes, u64 flags,
2595                                int is_data)
2596{
2597        struct btrfs_delayed_extent_op *extent_op;
2598        int ret;
2599
2600        extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2601        if (!extent_op)
2602                return -ENOMEM;
2603
2604        extent_op->flags_to_set = flags;
2605        extent_op->update_flags = 1;
2606        extent_op->update_key = 0;
2607        extent_op->is_data = is_data ? 1 : 0;
2608
2609        ret = btrfs_add_delayed_extent_op(root->fs_info, trans, bytenr,
2610                                          num_bytes, extent_op);
2611        if (ret)
2612                kfree(extent_op);
2613        return ret;
2614}
2615
2616static noinline int check_delayed_ref(struct btrfs_trans_handle *trans,
2617                                      struct btrfs_root *root,
2618                                      struct btrfs_path *path,
2619                                      u64 objectid, u64 offset, u64 bytenr)
2620{
2621        struct btrfs_delayed_ref_head *head;
2622        struct btrfs_delayed_ref_node *ref;
2623        struct btrfs_delayed_data_ref *data_ref;
2624        struct btrfs_delayed_ref_root *delayed_refs;
2625        struct rb_node *node;
2626        int ret = 0;
2627
2628        ret = -ENOENT;
2629        delayed_refs = &trans->transaction->delayed_refs;
2630        spin_lock(&delayed_refs->lock);
2631        head = btrfs_find_delayed_ref_head(trans, bytenr);
2632        if (!head)
2633                goto out;
2634
2635        if (!mutex_trylock(&head->mutex)) {
2636                atomic_inc(&head->node.refs);
2637                spin_unlock(&delayed_refs->lock);
2638
2639                btrfs_release_path(path);
2640
2641                /*
2642                 * Mutex was contended, block until it's released and let
2643                 * caller try again
2644                 */
2645                mutex_lock(&head->mutex);
2646                mutex_unlock(&head->mutex);
2647                btrfs_put_delayed_ref(&head->node);
2648                return -EAGAIN;
2649        }
2650
2651        node = rb_prev(&head->node.rb_node);
2652        if (!node)
2653                goto out_unlock;
2654
2655        ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2656
2657        if (ref->bytenr != bytenr)
2658                goto out_unlock;
2659
2660        ret = 1;
2661        if (ref->type != BTRFS_EXTENT_DATA_REF_KEY)
2662                goto out_unlock;
2663
2664        data_ref = btrfs_delayed_node_to_data_ref(ref);
2665
2666        node = rb_prev(node);
2667        if (node) {
2668                int seq = ref->seq;
2669
2670                ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2671                if (ref->bytenr == bytenr && ref->seq == seq)
2672                        goto out_unlock;
2673        }
2674
2675        if (data_ref->root != root->root_key.objectid ||
2676            data_ref->objectid != objectid || data_ref->offset != offset)
2677                goto out_unlock;
2678
2679        ret = 0;
2680out_unlock:
2681        mutex_unlock(&head->mutex);
2682out:
2683        spin_unlock(&delayed_refs->lock);
2684        return ret;
2685}
2686
2687static noinline int check_committed_ref(struct btrfs_trans_handle *trans,
2688                                        struct btrfs_root *root,
2689                                        struct btrfs_path *path,
2690                                        u64 objectid, u64 offset, u64 bytenr)
2691{
2692        struct btrfs_root *extent_root = root->fs_info->extent_root;
2693        struct extent_buffer *leaf;
2694        struct btrfs_extent_data_ref *ref;
2695        struct btrfs_extent_inline_ref *iref;
2696        struct btrfs_extent_item *ei;
2697        struct btrfs_key key;
2698        u32 item_size;
2699        int ret;
2700
2701        key.objectid = bytenr;
2702        key.offset = (u64)-1;
2703        key.type = BTRFS_EXTENT_ITEM_KEY;
2704
2705        ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2706        if (ret < 0)
2707                goto out;
2708        BUG_ON(ret == 0); /* Corruption */
2709
2710        ret = -ENOENT;
2711        if (path->slots[0] == 0)
2712                goto out;
2713
2714        path->slots[0]--;
2715        leaf = path->nodes[0];
2716        btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2717
2718        if (key.objectid != bytenr || key.type != BTRFS_EXTENT_ITEM_KEY)
2719                goto out;
2720
2721        ret = 1;
2722        item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2723#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2724        if (item_size < sizeof(*ei)) {
2725                WARN_ON(item_size != sizeof(struct btrfs_extent_item_v0));
2726                goto out;
2727        }
2728#endif
2729        ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2730
2731        if (item_size != sizeof(*ei) +
2732            btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY))
2733                goto out;
2734
2735        if (btrfs_extent_generation(leaf, ei) <=
2736            btrfs_root_last_snapshot(&root->root_item))
2737                goto out;
2738
2739        iref = (struct btrfs_extent_inline_ref *)(ei + 1);
2740        if (btrfs_extent_inline_ref_type(leaf, iref) !=
2741            BTRFS_EXTENT_DATA_REF_KEY)
2742                goto out;
2743
2744        ref = (struct btrfs_extent_data_ref *)(&iref->offset);
2745        if (btrfs_extent_refs(leaf, ei) !=
2746            btrfs_extent_data_ref_count(leaf, ref) ||
2747            btrfs_extent_data_ref_root(leaf, ref) !=
2748            root->root_key.objectid ||
2749            btrfs_extent_data_ref_objectid(leaf, ref) != objectid ||
2750            btrfs_extent_data_ref_offset(leaf, ref) != offset)
2751                goto out;
2752
2753        ret = 0;
2754out:
2755        return ret;
2756}
2757
2758int btrfs_cross_ref_exist(struct btrfs_trans_handle *trans,
2759                          struct btrfs_root *root,
2760                          u64 objectid, u64 offset, u64 bytenr)
2761{
2762        struct btrfs_path *path;
2763        int ret;
2764        int ret2;
2765
2766        path = btrfs_alloc_path();
2767        if (!path)
2768                return -ENOENT;
2769
2770        do {
2771                ret = check_committed_ref(trans, root, path, objectid,
2772                                          offset, bytenr);
2773                if (ret && ret != -ENOENT)
2774                        goto out;
2775
2776                ret2 = check_delayed_ref(trans, root, path, objectid,
2777                                         offset, bytenr);
2778        } while (ret2 == -EAGAIN);
2779
2780        if (ret2 && ret2 != -ENOENT) {
2781                ret = ret2;
2782                goto out;
2783        }
2784
2785        if (ret != -ENOENT || ret2 != -ENOENT)
2786                ret = 0;
2787out:
2788        btrfs_free_path(path);
2789        if (root->root_key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
2790                WARN_ON(ret > 0);
2791        return ret;
2792}
2793
2794static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
2795                           struct btrfs_root *root,
2796                           struct extent_buffer *buf,
2797                           int full_backref, int inc, int for_cow)
2798{
2799        u64 bytenr;
2800        u64 num_bytes;
2801        u64 parent;
2802        u64 ref_root;
2803        u32 nritems;
2804        struct btrfs_key key;
2805        struct btrfs_file_extent_item *fi;
2806        int i;
2807        int level;
2808        int ret = 0;
2809        int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
2810                            u64, u64, u64, u64, u64, u64, int);
2811
2812        ref_root = btrfs_header_owner(buf);
2813        nritems = btrfs_header_nritems(buf);
2814        level = btrfs_header_level(buf);
2815
2816        if (!root->ref_cows && level == 0)
2817                return 0;
2818
2819        if (inc)
2820                process_func = btrfs_inc_extent_ref;
2821        else
2822                process_func = btrfs_free_extent;
2823
2824        if (full_backref)
2825                parent = buf->start;
2826        else
2827                parent = 0;
2828
2829        for (i = 0; i < nritems; i++) {
2830                if (level == 0) {
2831                        btrfs_item_key_to_cpu(buf, &key, i);
2832                        if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2833                                continue;
2834                        fi = btrfs_item_ptr(buf, i,
2835                                            struct btrfs_file_extent_item);
2836                        if (btrfs_file_extent_type(buf, fi) ==
2837                            BTRFS_FILE_EXTENT_INLINE)
2838                                continue;
2839                        bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2840                        if (bytenr == 0)
2841                                continue;
2842
2843                        num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
2844                        key.offset -= btrfs_file_extent_offset(buf, fi);
2845                        ret = process_func(trans, root, bytenr, num_bytes,
2846                                           parent, ref_root, key.objectid,
2847                                           key.offset, for_cow);
2848                        if (ret)
2849                                goto fail;
2850                } else {
2851                        bytenr = btrfs_node_blockptr(buf, i);
2852                        num_bytes = btrfs_level_size(root, level - 1);
2853                        ret = process_func(trans, root, bytenr, num_bytes,
2854                                           parent, ref_root, level - 1, 0,
2855                                           for_cow);
2856                        if (ret)
2857                                goto fail;
2858                }
2859        }
2860        return 0;
2861fail:
2862        return ret;
2863}
2864
2865int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2866                  struct extent_buffer *buf, int full_backref, int for_cow)
2867{
2868        return __btrfs_mod_ref(trans, root, buf, full_backref, 1, for_cow);
2869}
2870
2871int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2872                  struct extent_buffer *buf, int full_backref, int for_cow)
2873{
2874        return __btrfs_mod_ref(trans, root, buf, full_backref, 0, for_cow);
2875}
2876
2877static int write_one_cache_group(struct btrfs_trans_handle *trans,
2878                                 struct btrfs_root *root,
2879                                 struct btrfs_path *path,
2880                                 struct btrfs_block_group_cache *cache)
2881{
2882        int ret;
2883        struct btrfs_root *extent_root = root->fs_info->extent_root;
2884        unsigned long bi;
2885        struct extent_buffer *leaf;
2886
2887        ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
2888        if (ret < 0)
2889                goto fail;
2890        BUG_ON(ret); /* Corruption */
2891
2892        leaf = path->nodes[0];
2893        bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
2894        write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
2895        btrfs_mark_buffer_dirty(leaf);
2896        btrfs_release_path(path);
2897fail:
2898        if (ret) {
2899                btrfs_abort_transaction(trans, root, ret);
2900                return ret;
2901        }
2902        return 0;
2903
2904}
2905
2906static struct btrfs_block_group_cache *
2907next_block_group(struct btrfs_root *root,
2908                 struct btrfs_block_group_cache *cache)
2909{
2910        struct rb_node *node;
2911        spin_lock(&root->fs_info->block_group_cache_lock);
2912        node = rb_next(&cache->cache_node);
2913        btrfs_put_block_group(cache);
2914        if (node) {
2915                cache = rb_entry(node, struct btrfs_block_group_cache,
2916                                 cache_node);
2917                btrfs_get_block_group(cache);
2918        } else
2919                cache = NULL;
2920        spin_unlock(&root->fs_info->block_group_cache_lock);
2921        return cache;
2922}
2923
2924static int cache_save_setup(struct btrfs_block_group_cache *block_group,
2925                            struct btrfs_trans_handle *trans,
2926                            struct btrfs_path *path)
2927{
2928        struct btrfs_root *root = block_group->fs_info->tree_root;
2929        struct inode *inode = NULL;
2930        u64 alloc_hint = 0;
2931        int dcs = BTRFS_DC_ERROR;
2932        int num_pages = 0;
2933        int retries = 0;
2934        int ret = 0;
2935
2936        /*
2937         * If this block group is smaller than 100 megs don't bother caching the
2938         * block group.
2939         */
2940        if (block_group->key.offset < (100 * 1024 * 1024)) {
2941                spin_lock(&block_group->lock);
2942                block_group->disk_cache_state = BTRFS_DC_WRITTEN;
2943                spin_unlock(&block_group->lock);
2944                return 0;
2945        }
2946
2947again:
2948        inode = lookup_free_space_inode(root, block_group, path);
2949        if (IS_ERR(inode) && PTR_ERR(inode) != -ENOENT) {
2950                ret = PTR_ERR(inode);
2951                btrfs_release_path(path);
2952                goto out;
2953        }
2954
2955        if (IS_ERR(inode)) {
2956                BUG_ON(retries);
2957                retries++;
2958
2959                if (block_group->ro)
2960                        goto out_free;
2961
2962                ret = create_free_space_inode(root, trans, block_group, path);
2963                if (ret)
2964                        goto out_free;
2965                goto again;
2966        }
2967
2968        /* We've already setup this transaction, go ahead and exit */
2969        if (block_group->cache_generation == trans->transid &&
2970            i_size_read(inode)) {
2971                dcs = BTRFS_DC_SETUP;
2972                goto out_put;
2973        }
2974
2975        /*
2976         * We want to set the generation to 0, that way if anything goes wrong
2977         * from here on out we know not to trust this cache when we load up next
2978         * time.
2979         */
2980        BTRFS_I(inode)->generation = 0;
2981        ret = btrfs_update_inode(trans, root, inode);
2982        WARN_ON(ret);
2983
2984        if (i_size_read(inode) > 0) {
2985                ret = btrfs_truncate_free_space_cache(root, trans, path,
2986                                                      inode);
2987                if (ret)
2988                        goto out_put;
2989        }
2990
2991        spin_lock(&block_group->lock);
2992        if (block_group->cached != BTRFS_CACHE_FINISHED ||
2993            !btrfs_test_opt(root, SPACE_CACHE)) {
2994                /*
2995                 * don't bother trying to write stuff out _if_
2996                 * a) we're not cached,
2997                 * b) we're with nospace_cache mount option.
2998                 */
2999                dcs = BTRFS_DC_WRITTEN;
3000                spin_unlock(&block_group->lock);
3001                goto out_put;
3002        }
3003        spin_unlock(&block_group->lock);
3004
3005        /*
3006         * Try to preallocate enough space based on how big the block group is.
3007         * Keep in mind this has to include any pinned space which could end up
3008         * taking up quite a bit since it's not folded into the other space
3009         * cache.
3010         */
3011        num_pages = (int)div64_u64(block_group->key.offset, 256 * 1024 * 1024);
3012        if (!num_pages)
3013                num_pages = 1;
3014
3015        num_pages *= 16;
3016        num_pages *= PAGE_CACHE_SIZE;
3017
3018        ret = btrfs_check_data_free_space(inode, num_pages);
3019        if (ret)
3020                goto out_put;
3021
3022        ret = btrfs_prealloc_file_range_trans(inode, trans, 0, 0, num_pages,
3023                                              num_pages, num_pages,
3024                                              &alloc_hint);
3025        if (!ret)
3026                dcs = BTRFS_DC_SETUP;
3027        btrfs_free_reserved_data_space(inode, num_pages);
3028
3029out_put:
3030        iput(inode);
3031out_free:
3032        btrfs_release_path(path);
3033out:
3034        spin_lock(&block_group->lock);
3035        if (!ret && dcs == BTRFS_DC_SETUP)
3036                block_group->cache_generation = trans->transid;
3037        block_group->disk_cache_state = dcs;
3038        spin_unlock(&block_group->lock);
3039
3040        return ret;
3041}
3042
3043int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
3044                                   struct btrfs_root *root)
3045{
3046        struct btrfs_block_group_cache *cache;
3047        int err = 0;
3048        struct btrfs_path *path;
3049        u64 last = 0;
3050
3051        path = btrfs_alloc_path();
3052        if (!path)
3053                return -ENOMEM;
3054
3055again:
3056        while (1) {
3057                cache = btrfs_lookup_first_block_group(root->fs_info, last);
3058                while (cache) {
3059                        if (cache->disk_cache_state == BTRFS_DC_CLEAR)
3060                                break;
3061                        cache = next_block_group(root, cache);
3062                }
3063                if (!cache) {
3064                        if (last == 0)
3065                                break;
3066                        last = 0;
3067                        continue;
3068                }
3069                err = cache_save_setup(cache, trans, path);
3070                last = cache->key.objectid + cache->key.offset;
3071                btrfs_put_block_group(cache);
3072        }
3073
3074        while (1) {
3075                if (last == 0) {
3076                        err = btrfs_run_delayed_refs(trans, root,
3077                                                     (unsigned long)-1);
3078                        if (err) /* File system offline */
3079                                goto out;
3080                }
3081
3082                cache = btrfs_lookup_first_block_group(root->fs_info, last);
3083                while (cache) {
3084                        if (cache->disk_cache_state == BTRFS_DC_CLEAR) {
3085                                btrfs_put_block_group(cache);
3086                                goto again;
3087                        }
3088
3089                        if (cache->dirty)
3090                                break;
3091                        cache = next_block_group(root, cache);
3092                }
3093                if (!cache) {
3094                        if (last == 0)
3095                                break;
3096                        last = 0;
3097                        continue;
3098                }
3099
3100                if (cache->disk_cache_state == BTRFS_DC_SETUP)
3101                        cache->disk_cache_state = BTRFS_DC_NEED_WRITE;
3102                cache->dirty = 0;
3103                last = cache->key.objectid + cache->key.offset;
3104
3105                err = write_one_cache_group(trans, root, path, cache);
3106                if (err) /* File system offline */
3107                        goto out;
3108
3109                btrfs_put_block_group(cache);
3110        }
3111
3112        while (1) {
3113                /*
3114                 * I don't think this is needed since we're just marking our
3115                 * preallocated extent as written, but just in case it can't
3116                 * hurt.
3117                 */
3118                if (last == 0) {
3119                        err = btrfs_run_delayed_refs(trans, root,
3120                                                     (unsigned long)-1);
3121                        if (err) /* File system offline */
3122                                goto out;
3123                }
3124
3125                cache = btrfs_lookup_first_block_group(root->fs_info, last);
3126                while (cache) {
3127                        /*
3128                         * Really this shouldn't happen, but it could if we
3129                         * couldn't write the entire preallocated extent and
3130                         * splitting the extent resulted in a new block.
3131                         */
3132                        if (cache->dirty) {
3133                                btrfs_put_block_group(cache);
3134                                goto again;
3135                        }
3136                        if (cache->disk_cache_state == BTRFS_DC_NEED_WRITE)
3137                                break;
3138                        cache = next_block_group(root, cache);
3139                }
3140                if (!cache) {
3141                        if (last == 0)
3142                                break;
3143                        last = 0;
3144                        continue;
3145                }
3146
3147                err = btrfs_write_out_cache(root, trans, cache, path);
3148
3149                /*
3150                 * If we didn't have an error then the cache state is still
3151                 * NEED_WRITE, so we can set it to WRITTEN.
3152                 */
3153                if (!err && cache->disk_cache_state == BTRFS_DC_NEED_WRITE)
3154                        cache->disk_cache_state = BTRFS_DC_WRITTEN;
3155                last = cache->key.objectid + cache->key.offset;
3156                btrfs_put_block_group(cache);
3157        }
3158out:
3159
3160        btrfs_free_path(path);
3161        return err;
3162}
3163
3164int btrfs_extent_readonly(struct btrfs_root *root, u64 bytenr)
3165{
3166        struct btrfs_block_group_cache *block_group;
3167        int readonly = 0;
3168
3169        block_group = btrfs_lookup_block_group(root->fs_info, bytenr);
3170        if (!block_group || block_group->ro)
3171                readonly = 1;
3172        if (block_group)
3173                btrfs_put_block_group(block_group);
3174        return readonly;
3175}
3176
3177static int update_space_info(struct btrfs_fs_info *info, u64 flags,
3178                             u64 total_bytes, u64 bytes_used,
3179                             struct btrfs_space_info **space_info)
3180{
3181        struct btrfs_space_info *found;
3182        int i;
3183        int factor;
3184
3185        if (flags & (BTRFS_BLOCK_GROUP_DUP | BTRFS_BLOCK_GROUP_RAID1 |
3186                     BTRFS_BLOCK_GROUP_RAID10))
3187                factor = 2;
3188        else
3189                factor = 1;
3190
3191        found = __find_space_info(info, flags);
3192        if (found) {
3193                spin_lock(&found->lock);
3194                found->total_bytes += total_bytes;
3195                found->disk_total += total_bytes * factor;
3196                found->bytes_used += bytes_used;
3197                found->disk_used += bytes_used * factor;
3198                found->full = 0;
3199                spin_unlock(&found->lock);
3200                *space_info = found;
3201                return 0;
3202        }
3203        found = kzalloc(sizeof(*found), GFP_NOFS);
3204        if (!found)
3205                return -ENOMEM;
3206
3207        for (i = 0; i < BTRFS_NR_RAID_TYPES; i++)
3208                INIT_LIST_HEAD(&found->block_groups[i]);
3209        init_rwsem(&found->groups_sem);
3210        spin_lock_init(&found->lock);
3211        found->flags = flags & BTRFS_BLOCK_GROUP_TYPE_MASK;
3212        found->total_bytes = total_bytes;
3213        found->disk_total = total_bytes * factor;
3214        found->bytes_used = bytes_used;
3215        found->disk_used = bytes_used * factor;
3216        found->bytes_pinned = 0;
3217        found->bytes_reserved = 0;
3218        found->bytes_readonly = 0;
3219        found->bytes_may_use = 0;
3220        found->full = 0;
3221        found->force_alloc = CHUNK_ALLOC_NO_FORCE;
3222        found->chunk_alloc = 0;
3223        found->flush = 0;
3224        init_waitqueue_head(&found->wait);
3225        *space_info = found;
3226        list_add_rcu(&found->list, &info->space_info);
3227        if (flags & BTRFS_BLOCK_GROUP_DATA)
3228                info->data_sinfo = found;
3229        return 0;
3230}
3231
3232static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
3233{
3234        u64 extra_flags = chunk_to_extended(flags) &
3235                                BTRFS_EXTENDED_PROFILE_MASK;
3236
3237        if (flags & BTRFS_BLOCK_GROUP_DATA)
3238                fs_info->avail_data_alloc_bits |= extra_flags;
3239        if (flags & BTRFS_BLOCK_GROUP_METADATA)
3240                fs_info->avail_metadata_alloc_bits |= extra_flags;
3241        if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
3242                fs_info->avail_system_alloc_bits |= extra_flags;
3243}
3244
3245/*
3246 * returns target flags in extended format or 0 if restripe for this
3247 * chunk_type is not in progress
3248 *
3249 * should be called with either volume_mutex or balance_lock held
3250 */
3251static u64 get_restripe_target(struct btrfs_fs_info *fs_info, u64 flags)
3252{
3253        struct btrfs_balance_control *bctl = fs_info->balance_ctl;
3254        u64 target = 0;
3255
3256        if (!bctl)
3257                return 0;
3258
3259        if (flags & BTRFS_BLOCK_GROUP_DATA &&
3260            bctl->data.flags & BTRFS_BALANCE_ARGS_CONVERT) {
3261                target = BTRFS_BLOCK_GROUP_DATA | bctl->data.target;
3262        } else if (flags & BTRFS_BLOCK_GROUP_SYSTEM &&
3263                   bctl->sys.flags & BTRFS_BALANCE_ARGS_CONVERT) {
3264                target = BTRFS_BLOCK_GROUP_SYSTEM | bctl->sys.target;
3265        } else if (flags & BTRFS_BLOCK_GROUP_METADATA &&
3266                   bctl->meta.flags & BTRFS_BALANCE_ARGS_CONVERT) {
3267                target = BTRFS_BLOCK_GROUP_METADATA | bctl->meta.target;
3268        }
3269
3270        return target;
3271}
3272
3273/*
3274 * @flags: available profiles in extended format (see ctree.h)
3275 *
3276 * Returns reduced profile in chunk format.  If profile changing is in
3277 * progress (either running or paused) picks the target profile (if it's
3278 * already available), otherwise falls back to plain reducing.
3279 */
3280u64 btrfs_reduce_alloc_profile(struct btrfs_root *root, u64 flags)
3281{
3282        /*
3283         * we add in the count of missing devices because we want
3284         * to make sure that any RAID levels on a degraded FS
3285         * continue to be honored.
3286         */
3287        u64 num_devices = root->fs_info->fs_devices->rw_devices +
3288                root->fs_info->fs_devices->missing_devices;
3289        u64 target;
3290
3291        /*
3292         * see if restripe for this chunk_type is in progress, if so
3293         * try to reduce to the target profile
3294         */
3295        spin_lock(&root->fs_info->balance_lock);
3296        target = get_restripe_target(root->fs_info, flags);
3297        if (target) {
3298                /* pick target profile only if it's already available */
3299                if ((flags & target) & BTRFS_EXTENDED_PROFILE_MASK) {
3300                        spin_unlock(&root->fs_info->balance_lock);
3301                        return extended_to_chunk(target);
3302                }
3303        }
3304        spin_unlock(&root->fs_info->balance_lock);
3305
3306        if (num_devices == 1)
3307                flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
3308        if (num_devices < 4)
3309                flags &= ~BTRFS_BLOCK_GROUP_RAID10;
3310
3311        if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
3312            (flags & (BTRFS_BLOCK_GROUP_RAID1 |
3313                      BTRFS_BLOCK_GROUP_RAID10))) {
3314                flags &= ~BTRFS_BLOCK_GROUP_DUP;
3315        }
3316
3317        if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
3318            (flags & BTRFS_BLOCK_GROUP_RAID10)) {
3319                flags &= ~BTRFS_BLOCK_GROUP_RAID1;
3320        }
3321
3322        if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
3323            ((flags & BTRFS_BLOCK_GROUP_RAID1) |
3324             (flags & BTRFS_BLOCK_GROUP_RAID10) |
3325             (flags & BTRFS_BLOCK_GROUP_DUP))) {
3326                flags &= ~BTRFS_BLOCK_GROUP_RAID0;
3327        }
3328
3329        return extended_to_chunk(flags);
3330}
3331
3332static u64 get_alloc_profile(struct btrfs_root *root, u64 flags)
3333{
3334        if (flags & BTRFS_BLOCK_GROUP_DATA)
3335                flags |= root->fs_info->avail_data_alloc_bits;
3336        else if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
3337                flags |= root->fs_info->avail_system_alloc_bits;
3338        else if (flags & BTRFS_BLOCK_GROUP_METADATA)
3339                flags |= root->fs_info->avail_metadata_alloc_bits;
3340
3341        return btrfs_reduce_alloc_profile(root, flags);
3342}
3343
3344u64 btrfs_get_alloc_profile(struct btrfs_root *root, int data)
3345{
3346        u64 flags;
3347
3348        if (data)
3349                flags = BTRFS_BLOCK_GROUP_DATA;
3350        else if (root == root->fs_info->chunk_root)
3351                flags = BTRFS_BLOCK_GROUP_SYSTEM;
3352        else
3353                flags = BTRFS_BLOCK_GROUP_METADATA;
3354
3355        return get_alloc_profile(root, flags);
3356}
3357
3358/*
3359 * This will check the space that the inode allocates from to make sure we have
3360 * enough space for bytes.
3361 */
3362int btrfs_check_data_free_space(struct inode *inode, u64 bytes)
3363{
3364        struct btrfs_space_info *data_sinfo;
3365        struct btrfs_root *root = BTRFS_I(inode)->root;
3366        struct btrfs_fs_info *fs_info = root->fs_info;
3367        u64 used;
3368        int ret = 0, committed = 0, alloc_chunk = 1;
3369
3370        /* make sure bytes are sectorsize aligned */
3371        bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
3372
3373        if (root == root->fs_info->tree_root ||
3374            BTRFS_I(inode)->location.objectid == BTRFS_FREE_INO_OBJECTID) {
3375                alloc_chunk = 0;
3376                committed = 1;
3377        }
3378
3379        data_sinfo = fs_info->data_sinfo;
3380        if (!data_sinfo)
3381                goto alloc;
3382
3383again:
3384        /* make sure we have enough space to handle the data first */
3385        spin_lock(&data_sinfo->lock);
3386        used = data_sinfo->bytes_used + data_sinfo->bytes_reserved +
3387                data_sinfo->bytes_pinned + data_sinfo->bytes_readonly +
3388                data_sinfo->bytes_may_use;
3389
3390        if (used + bytes > data_sinfo->total_bytes) {
3391                struct btrfs_trans_handle *trans;
3392
3393                /*
3394                 * if we don't have enough free bytes in this space then we need
3395                 * to alloc a new chunk.
3396                 */
3397                if (!data_sinfo->full && alloc_chunk) {
3398                        u64 alloc_target;
3399
3400                        data_sinfo->force_alloc = CHUNK_ALLOC_FORCE;
3401                        spin_unlock(&data_sinfo->lock);
3402alloc:
3403                        alloc_target = btrfs_get_alloc_profile(root, 1);
3404                        trans = btrfs_join_transaction(root);
3405                        if (IS_ERR(trans))
3406                                return PTR_ERR(trans);
3407
3408                        ret = do_chunk_alloc(trans, root->fs_info->extent_root,
3409                                             bytes + 2 * 1024 * 1024,
3410                                             alloc_target,
3411                                             CHUNK_ALLOC_NO_FORCE);
3412                        btrfs_end_transaction(trans, root);
3413                        if (ret < 0) {
3414                                if (ret != -ENOSPC)
3415                                        return ret;
3416                                else
3417                                        goto commit_trans;
3418                        }
3419
3420                        if (!data_sinfo)
3421                                data_sinfo = fs_info->data_sinfo;
3422
3423                        goto again;
3424                }
3425
3426                /*
3427                 * If we have less pinned bytes than we want to allocate then
3428                 * don't bother committing the transaction, it won't help us.
3429                 */
3430                if (data_sinfo->bytes_pinned < bytes)
3431                        committed = 1;
3432                spin_unlock(&data_sinfo->lock);
3433
3434                /* commit the current transaction and try again */
3435commit_trans:
3436                if (!committed &&
3437                    !atomic_read(&root->fs_info->open_ioctl_trans)) {
3438                        committed = 1;
3439                        trans = btrfs_join_transaction(root);
3440                        if (IS_ERR(trans))
3441                                return PTR_ERR(trans);
3442                        ret = btrfs_commit_transaction(trans, root);
3443                        if (ret)
3444                                return ret;
3445                        goto again;
3446                }
3447
3448                return -ENOSPC;
3449        }
3450        data_sinfo->bytes_may_use += bytes;
3451        trace_btrfs_space_reservation(root->fs_info, "space_info",
3452                                      data_sinfo->flags, bytes, 1);
3453        spin_unlock(&data_sinfo->lock);
3454
3455        return 0;
3456}
3457
3458/*
3459 * Called if we need to clear a data reservation for this inode.
3460 */
3461void btrfs_free_reserved_data_space(struct inode *inode, u64 bytes)
3462{
3463        struct btrfs_root *root = BTRFS_I(inode)->root;
3464        struct btrfs_space_info *data_sinfo;
3465
3466        /* make sure bytes are sectorsize aligned */
3467        bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
3468
3469        data_sinfo = root->fs_info->data_sinfo;
3470        spin_lock(&data_sinfo->lock);
3471        data_sinfo->bytes_may_use -= bytes;
3472        trace_btrfs_space_reservation(root->fs_info, "space_info",
3473                                      data_sinfo->flags, bytes, 0);
3474        spin_unlock(&data_sinfo->lock);
3475}
3476
3477static void force_metadata_allocation(struct btrfs_fs_info *info)
3478{
3479        struct list_head *head = &info->space_info;
3480        struct btrfs_space_info *found;
3481
3482        rcu_read_lock();
3483        list_for_each_entry_rcu(found, head, list) {
3484                if (found->flags & BTRFS_BLOCK_GROUP_METADATA)
3485                        found->force_alloc = CHUNK_ALLOC_FORCE;
3486        }
3487        rcu_read_unlock();
3488}
3489
3490static int should_alloc_chunk(struct btrfs_root *root,
3491                              struct btrfs_space_info *sinfo, u64 alloc_bytes,
3492                              int force)
3493{
3494        struct btrfs_block_rsv *global_rsv = &root->fs_info->global_block_rsv;
3495        u64 num_bytes = sinfo->total_bytes - sinfo->bytes_readonly;
3496        u64 num_allocated = sinfo->bytes_used + sinfo->bytes_reserved;
3497        u64 thresh;
3498
3499        if (force == CHUNK_ALLOC_FORCE)
3500                return 1;
3501
3502        /*
3503         * We need to take into account the global rsv because for all intents
3504         * and purposes it's used space.  Don't worry about locking the
3505         * global_rsv, it doesn't change except when the transaction commits.
3506         */
3507        num_allocated += global_rsv->size;
3508
3509        /*
3510         * in limited mode, we want to have some free space up to
3511         * about 1% of the FS size.
3512         */
3513        if (force == CHUNK_ALLOC_LIMITED) {
3514                thresh = btrfs_super_total_bytes(root->fs_info->super_copy);
3515                thresh = max_t(u64, 64 * 1024 * 1024,
3516                               div_factor_fine(thresh, 1));
3517
3518                if (num_bytes - num_allocated < thresh)
3519                        return 1;
3520        }
3521        thresh = btrfs_super_total_bytes(root->fs_info->super_copy);
3522
3523        /* 256MB or 2% of the FS */
3524        thresh = max_t(u64, 256 * 1024 * 1024, div_factor_fine(thresh, 2));
3525        /* system chunks need a much small threshold */
3526        if (sinfo->flags & BTRFS_BLOCK_GROUP_SYSTEM)
3527                thresh = 32 * 1024 * 1024;
3528
3529        if (num_bytes > thresh && sinfo->bytes_used < div_factor(num_bytes, 8))
3530                return 0;
3531        return 1;
3532}
3533
3534static u64 get_system_chunk_thresh(struct btrfs_root *root, u64 type)
3535{
3536        u64 num_dev;
3537
3538        if (type & BTRFS_BLOCK_GROUP_RAID10 ||
3539            type & BTRFS_BLOCK_GROUP_RAID0)
3540                num_dev = root->fs_info->fs_devices->rw_devices;
3541        else if (type & BTRFS_BLOCK_GROUP_RAID1)
3542                num_dev = 2;
3543        else
3544                num_dev = 1;    /* DUP or single */
3545
3546        /* metadata for updaing devices and chunk tree */
3547        return btrfs_calc_trans_metadata_size(root, num_dev + 1);
3548}
3549
3550static void check_system_chunk(struct btrfs_trans_handle *trans,
3551                               struct btrfs_root *root, u64 type)
3552{
3553        struct btrfs_space_info *info;
3554        u64 left;
3555        u64 thresh;
3556
3557        info = __find_space_info(root->fs_info, BTRFS_BLOCK_GROUP_SYSTEM);
3558        spin_lock(&info->lock);
3559        left = info->total_bytes - info->bytes_used - info->bytes_pinned -
3560                info->bytes_reserved - info->bytes_readonly;
3561        spin_unlock(&info->lock);
3562
3563        thresh = get_system_chunk_thresh(root, type);
3564        if (left < thresh && btrfs_test_opt(root, ENOSPC_DEBUG)) {
3565                printk(KERN_INFO "left=%llu, need=%llu, flags=%llu\n",
3566                       left, thresh, type);
3567                dump_space_info(info, 0, 0);
3568        }
3569
3570        if (left < thresh) {
3571                u64 flags;
3572
3573                flags = btrfs_get_alloc_profile(root->fs_info->chunk_root, 0);
3574                btrfs_alloc_chunk(trans, root, flags);
3575        }
3576}
3577
3578static int do_chunk_alloc(struct btrfs_trans_handle *trans,
3579                          struct btrfs_root *extent_root, u64 alloc_bytes,
3580                          u64 flags, int force)
3581{
3582        struct btrfs_space_info *space_info;
3583        struct btrfs_fs_info *fs_info = extent_root->fs_info;
3584        int wait_for_alloc = 0;
3585        int ret = 0;
3586
3587        space_info = __find_space_info(extent_root->fs_info, flags);
3588        if (!space_info) {
3589                ret = update_space_info(extent_root->fs_info, flags,
3590                                        0, 0, &space_info);
3591                BUG_ON(ret); /* -ENOMEM */
3592        }
3593        BUG_ON(!space_info); /* Logic error */
3594
3595again:
3596        spin_lock(&space_info->lock);
3597        if (force < space_info->force_alloc)
3598                force = space_info->force_alloc;
3599        if (space_info->full) {
3600                spin_unlock(&space_info->lock);
3601                return 0;
3602        }
3603
3604        if (!should_alloc_chunk(extent_root, space_info, alloc_bytes, force)) {
3605                spin_unlock(&space_info->lock);
3606                return 0;
3607        } else if (space_info->chunk_alloc) {
3608                wait_for_alloc = 1;
3609        } else {
3610                space_info->chunk_alloc = 1;
3611        }
3612
3613        spin_unlock(&space_info->lock);
3614
3615        mutex_lock(&fs_info->chunk_mutex);
3616
3617        /*
3618         * The chunk_mutex is held throughout the entirety of a chunk
3619         * allocation, so once we've acquired the chunk_mutex we know that the
3620         * other guy is done and we need to recheck and see if we should
3621         * allocate.
3622         */
3623        if (wait_for_alloc) {
3624                mutex_unlock(&fs_info->chunk_mutex);
3625                wait_for_alloc = 0;
3626                goto again;
3627        }
3628
3629        /*
3630         * If we have mixed data/metadata chunks we want to make sure we keep
3631         * allocating mixed chunks instead of individual chunks.
3632         */
3633        if (btrfs_mixed_space_info(space_info))
3634                flags |= (BTRFS_BLOCK_GROUP_DATA | BTRFS_BLOCK_GROUP_METADATA);
3635
3636        /*
3637         * if we're doing a data chunk, go ahead and make sure that
3638         * we keep a reasonable number of metadata chunks allocated in the
3639         * FS as well.
3640         */
3641        if (flags & BTRFS_BLOCK_GROUP_DATA && fs_info->metadata_ratio) {
3642                fs_info->data_chunk_allocations++;
3643                if (!(fs_info->data_chunk_allocations %
3644                      fs_info->metadata_ratio))
3645                        force_metadata_allocation(fs_info);
3646        }
3647
3648        /*
3649         * Check if we have enough space in SYSTEM chunk because we may need
3650         * to update devices.
3651         */
3652        check_system_chunk(trans, extent_root, flags);
3653
3654        ret = btrfs_alloc_chunk(trans, extent_root, flags);
3655        if (ret < 0 && ret != -ENOSPC)
3656                goto out;
3657
3658        spin_lock(&space_info->lock);
3659        if (ret)
3660                space_info->full = 1;
3661        else
3662                ret = 1;
3663
3664        space_info->force_alloc = CHUNK_ALLOC_NO_FORCE;
3665        space_info->chunk_alloc = 0;
3666        spin_unlock(&space_info->lock);
3667out:
3668        mutex_unlock(&fs_info->chunk_mutex);
3669        return ret;
3670}
3671
3672/*
3673 * shrink metadata reservation for delalloc
3674 */
3675static void shrink_delalloc(struct btrfs_root *root, u64 to_reclaim, u64 orig,
3676                            bool wait_ordered)
3677{
3678        struct btrfs_block_rsv *block_rsv;
3679        struct btrfs_space_info *space_info;
3680        struct btrfs_trans_handle *trans;
3681        u64 delalloc_bytes;
3682        u64 max_reclaim;
3683        long time_left;
3684        unsigned long nr_pages = (2 * 1024 * 1024) >> PAGE_CACHE_SHIFT;
3685        int loops = 0;
3686
3687        trans = (struct btrfs_trans_handle *)current->journal_info;
3688        block_rsv = &root->fs_info->delalloc_block_rsv;
3689        space_info = block_rsv->space_info;
3690
3691        smp_mb();
3692        delalloc_bytes = root->fs_info->delalloc_bytes;
3693        if (delalloc_bytes == 0) {
3694                if (trans)
3695                        return;
3696                btrfs_wait_ordered_extents(root, 0, 0);
3697                return;
3698        }
3699
3700        while (delalloc_bytes && loops < 3) {
3701                max_reclaim = min(delalloc_bytes, to_reclaim);
3702                nr_pages = max_reclaim >> PAGE_CACHE_SHIFT;
3703                writeback_inodes_sb_nr_if_idle(root->fs_info->sb, nr_pages,
3704                                               WB_REASON_FS_FREE_SPACE);
3705
3706                spin_lock(&space_info->lock);
3707                if (space_info->bytes_used + space_info->bytes_reserved +
3708                    space_info->bytes_pinned + space_info->bytes_readonly +
3709                    space_info->bytes_may_use + orig <=
3710                    space_info->total_bytes) {
3711                        spin_unlock(&space_info->lock);
3712                        break;
3713                }
3714                spin_unlock(&space_info->lock);
3715
3716                loops++;
3717                if (wait_ordered && !trans) {
3718                        btrfs_wait_ordered_extents(root, 0, 0);
3719                } else {
3720                        time_left = schedule_timeout_killable(1);
3721                        if (time_left)
3722                                break;
3723                }
3724                smp_mb();
3725                delalloc_bytes = root->fs_info->delalloc_bytes;
3726        }
3727}
3728
3729/**
3730 * maybe_commit_transaction - possibly commit the transaction if its ok to
3731 * @root - the root we're allocating for
3732 * @bytes - the number of bytes we want to reserve
3733 * @force - force the commit
3734 *
3735 * This will check to make sure that committing the transaction will actually
3736 * get us somewhere and then commit the transaction if it does.  Otherwise it
3737 * will return -ENOSPC.
3738 */
3739static int may_commit_transaction(struct btrfs_root *root,
3740                                  struct btrfs_space_info *space_info,
3741                                  u64 bytes, int force)
3742{
3743        struct btrfs_block_rsv *delayed_rsv = &root->fs_info->delayed_block_rsv;
3744        struct btrfs_trans_handle *trans;
3745
3746        trans = (struct btrfs_trans_handle *)current->journal_info;
3747        if (trans)
3748                return -EAGAIN;
3749
3750        if (force)
3751                goto commit;
3752
3753        /* See if there is enough pinned space to make this reservation */
3754        spin_lock(&space_info->lock);
3755        if (space_info->bytes_pinned >= bytes) {
3756                spin_unlock(&space_info->lock);
3757                goto commit;
3758        }
3759        spin_unlock(&space_info->lock);
3760
3761        /*
3762         * See if there is some space in the delayed insertion reservation for
3763         * this reservation.
3764         */
3765        if (space_info != delayed_rsv->space_info)
3766                return -ENOSPC;
3767
3768        spin_lock(&space_info->lock);
3769        spin_lock(&delayed_rsv->lock);
3770        if (space_info->bytes_pinned + delayed_rsv->size < bytes) {
3771                spin_unlock(&delayed_rsv->lock);
3772                spin_unlock(&space_info->lock);
3773                return -ENOSPC;
3774        }
3775        spin_unlock(&delayed_rsv->lock);
3776        spin_unlock(&space_info->lock);
3777
3778commit:
3779        trans = btrfs_join_transaction(root);
3780        if (IS_ERR(trans))
3781                return -ENOSPC;
3782
3783        return btrfs_commit_transaction(trans, root);
3784}
3785
3786enum flush_state {
3787        FLUSH_DELALLOC          =       1,
3788        FLUSH_DELALLOC_WAIT     =       2,
3789        FLUSH_DELAYED_ITEMS_NR  =       3,
3790        FLUSH_DELAYED_ITEMS     =       4,
3791        COMMIT_TRANS            =       5,
3792};
3793
3794static int flush_space(struct btrfs_root *root,
3795                       struct btrfs_space_info *space_info, u64 num_bytes,
3796                       u64 orig_bytes, int state)
3797{
3798        struct btrfs_trans_handle *trans;
3799        int nr;
3800        int ret = 0;
3801
3802        switch (state) {
3803        case FLUSH_DELALLOC:
3804        case FLUSH_DELALLOC_WAIT:
3805                shrink_delalloc(root, num_bytes, orig_bytes,
3806                                state == FLUSH_DELALLOC_WAIT);
3807                break;
3808        case FLUSH_DELAYED_ITEMS_NR:
3809        case FLUSH_DELAYED_ITEMS:
3810                if (state == FLUSH_DELAYED_ITEMS_NR) {
3811                        u64 bytes = btrfs_calc_trans_metadata_size(root, 1);
3812
3813                        nr = (int)div64_u64(num_bytes, bytes);
3814                        if (!nr)
3815                                nr = 1;
3816                        nr *= 2;
3817                } else {
3818                        nr = -1;
3819                }
3820                trans = btrfs_join_transaction(root);
3821                if (IS_ERR(trans)) {
3822                        ret = PTR_ERR(trans);
3823                        break;
3824                }
3825                ret = btrfs_run_delayed_items_nr(trans, root, nr);
3826                btrfs_end_transaction(trans, root);
3827                break;
3828        case COMMIT_TRANS:
3829                ret = may_commit_transaction(root, space_info, orig_bytes, 0);
3830                break;
3831        default:
3832                ret = -ENOSPC;
3833                break;
3834        }
3835
3836        return ret;
3837}
3838/**
3839 * reserve_metadata_bytes - try to reserve bytes from the block_rsv's space
3840 * @root - the root we're allocating for
3841 * @block_rsv - the block_rsv we're allocating for
3842 * @orig_bytes - the number of bytes we want
3843 * @flush - wether or not we can flush to make our reservation
3844 *
3845 * This will reserve orgi_bytes number of bytes from the space info associated
3846 * with the block_rsv.  If there is not enough space it will make an attempt to
3847 * flush out space to make room.  It will do this by flushing delalloc if
3848 * possible or committing the transaction.  If flush is 0 then no attempts to
3849 * regain reservations will be made and this will fail if there is not enough
3850 * space already.
3851 */
3852static int reserve_metadata_bytes(struct btrfs_root *root,
3853                                  struct btrfs_block_rsv *block_rsv,
3854                                  u64 orig_bytes, int flush)
3855{
3856        struct btrfs_space_info *space_info = block_rsv->space_info;
3857        u64 used;
3858        u64 num_bytes = orig_bytes;
3859        int flush_state = FLUSH_DELALLOC;
3860        int ret = 0;
3861        bool flushing = false;
3862        bool committed = false;
3863
3864again:
3865        ret = 0;
3866        spin_lock(&space_info->lock);
3867        /*
3868         * We only want to wait if somebody other than us is flushing and we are
3869         * actually alloed to flush.
3870         */
3871        while (flush && !flushing && space_info->flush) {
3872                spin_unlock(&space_info->lock);
3873                /*
3874                 * If we have a trans handle we can't wait because the flusher
3875                 * may have to commit the transaction, which would mean we would
3876                 * deadlock since we are waiting for the flusher to finish, but
3877                 * hold the current transaction open.
3878                 */
3879                if (current->journal_info)
3880                        return -EAGAIN;
3881                ret = wait_event_killable(space_info->wait, !space_info->flush);
3882                /* Must have been killed, return */
3883                if (ret)
3884                        return -EINTR;
3885
3886                spin_lock(&space_info->lock);
3887        }
3888
3889        ret = -ENOSPC;
3890        used = space_info->bytes_used + space_info->bytes_reserved +
3891                space_info->bytes_pinned + space_info->bytes_readonly +
3892                space_info->bytes_may_use;
3893
3894        /*
3895         * The idea here is that we've not already over-reserved the block group
3896         * then we can go ahead and save our reservation first and then start
3897         * flushing if we need to.  Otherwise if we've already overcommitted
3898         * lets start flushing stuff first and then come back and try to make
3899         * our reservation.
3900         */
3901        if (used <= space_info->total_bytes) {
3902                if (used + orig_bytes <= space_info->total_bytes) {
3903                        space_info->bytes_may_use += orig_bytes;
3904                        trace_btrfs_space_reservation(root->fs_info,
3905                                "space_info", space_info->flags, orig_bytes, 1);
3906                        ret = 0;
3907                } else {
3908                        /*
3909                         * Ok set num_bytes to orig_bytes since we aren't
3910                         * overocmmitted, this way we only try and reclaim what
3911                         * we need.
3912                         */
3913                        num_bytes = orig_bytes;
3914                }
3915        } else {
3916                /*
3917                 * Ok we're over committed, set num_bytes to the overcommitted
3918                 * amount plus the amount of bytes that we need for this
3919                 * reservation.
3920                 */
3921                num_bytes = used - space_info->total_bytes +
3922                        (orig_bytes * 2);
3923        }
3924
3925        if (ret) {
3926                u64 profile = btrfs_get_alloc_profile(root, 0);
3927                u64 avail;
3928
3929                /*
3930                 * If we have a lot of space that's pinned, don't bother doing
3931                 * the overcommit dance yet and just commit the transaction.
3932                 */
3933                avail = (space_info->total_bytes - space_info->bytes_used) * 8;
3934                do_div(avail, 10);
3935                if (space_info->bytes_pinned >= avail && flush && !committed) {
3936                        space_info->flush = 1;
3937                        flushing = true;
3938                        spin_unlock(&space_info->lock);
3939                        ret = may_commit_transaction(root, space_info,
3940                                                     orig_bytes, 1);
3941                        if (ret)
3942                                goto out;
3943                        committed = true;
3944                        goto again;
3945                }
3946
3947                spin_lock(&root->fs_info->free_chunk_lock);
3948                avail = root->fs_info->free_chunk_space;
3949
3950                /*
3951                 * If we have dup, raid1 or raid10 then only half of the free
3952                 * space is actually useable.
3953                 */
3954                if (profile & (BTRFS_BLOCK_GROUP_DUP |
3955                               BTRFS_BLOCK_GROUP_RAID1 |
3956                               BTRFS_BLOCK_GROUP_RAID10))
3957                        avail >>= 1;
3958
3959                /*
3960                 * If we aren't flushing don't let us overcommit too much, say
3961                 * 1/8th of the space.  If we can flush, let it overcommit up to
3962                 * 1/2 of the space.
3963                 */
3964                if (flush)
3965                        avail >>= 3;
3966                else
3967                        avail >>= 1;
3968                 spin_unlock(&root->fs_info->free_chunk_lock);
3969
3970                if (used + num_bytes < space_info->total_bytes + avail) {
3971                        space_info->bytes_may_use += orig_bytes;
3972                        trace_btrfs_space_reservation(root->fs_info,
3973                                "space_info", space_info->flags, orig_bytes, 1);
3974                        ret = 0;
3975                }
3976        }
3977
3978        /*
3979         * Couldn't make our reservation, save our place so while we're trying
3980         * to reclaim space we can actually use it instead of somebody else
3981         * stealing it from us.
3982         */
3983        if (ret && flush) {
3984                flushing = true;
3985                space_info->flush = 1;
3986        }
3987
3988        spin_unlock(&space_info->lock);
3989
3990        if (!ret || !flush)
3991                goto out;
3992
3993        ret = flush_space(root, space_info, num_bytes, orig_bytes,
3994                          flush_state);
3995        flush_state++;
3996        if (!ret)
3997                goto again;
3998        else if (flush_state <= COMMIT_TRANS)
3999                goto again;
4000
4001out:
4002        if (flushing) {
4003                spin_lock(&space_info->lock);
4004                space_info->flush = 0;
4005                wake_up_all(&space_info->wait);
4006                spin_unlock(&space_info->lock);
4007        }
4008        return ret;
4009}
4010
4011static struct btrfs_block_rsv *get_block_rsv(
4012                                        const struct btrfs_trans_handle *trans,
4013                                        const struct btrfs_root *root)
4014{
4015        struct btrfs_block_rsv *block_rsv = NULL;
4016
4017        if (root->ref_cows)
4018                block_rsv = trans->block_rsv;
4019
4020        if (root == root->fs_info->csum_root && trans->adding_csums)
4021                block_rsv = trans->block_rsv;
4022
4023        if (!block_rsv)
4024                block_rsv = root->block_rsv;
4025
4026        if (!block_rsv)
4027                block_rsv = &root->fs_info->empty_block_rsv;
4028
4029        return block_rsv;
4030}
4031
4032static int block_rsv_use_bytes(struct btrfs_block_rsv *block_rsv,
4033                               u64 num_bytes)
4034{
4035        int ret = -ENOSPC;
4036        spin_lock(&block_rsv->lock);
4037        if (block_rsv->reserved >= num_bytes) {
4038                block_rsv->reserved -= num_bytes;
4039                if (block_rsv->reserved < block_rsv->size)
4040                        block_rsv->full = 0;
4041                ret = 0;
4042        }
4043        spin_unlock(&block_rsv->lock);
4044        return ret;
4045}
4046
4047static void block_rsv_add_bytes(struct btrfs_block_rsv *block_rsv,
4048                                u64 num_bytes, int update_size)
4049{
4050        spin_lock(&block_rsv->lock);
4051        block_rsv->reserved += num_bytes;
4052        if (update_size)
4053                block_rsv->size += num_bytes;
4054        else if (block_rsv->reserved >= block_rsv->size)
4055                block_rsv->full = 1;
4056        spin_unlock(&block_rsv->lock);
4057}
4058
4059static void block_rsv_release_bytes(struct btrfs_fs_info *fs_info,
4060                                    struct btrfs_block_rsv *block_rsv,
4061                                    struct btrfs_block_rsv *dest, u64 num_bytes)
4062{
4063        struct btrfs_space_info *space_info = block_rsv->space_info;
4064
4065        spin_lock(&block_rsv->lock);
4066        if (num_bytes == (u64)-1)
4067                num_bytes = block_rsv->size;
4068        block_rsv->size -= num_bytes;
4069        if (block_rsv->reserved >= block_rsv->size) {
4070                num_bytes = block_rsv->reserved - block_rsv->size;
4071                block_rsv->reserved = block_rsv->size;
4072                block_rsv->full = 1;
4073        } else {
4074                num_bytes = 0;
4075        }
4076        spin_unlock(&block_rsv->lock);
4077
4078        if (num_bytes > 0) {
4079                if (dest) {
4080                        spin_lock(&dest->lock);
4081                        if (!dest->full) {
4082                                u64 bytes_to_add;
4083
4084                                bytes_to_add = dest->size - dest->reserved;
4085                                bytes_to_add = min(num_bytes, bytes_to_add);
4086                                dest->reserved += bytes_to_add;
4087                                if (dest->reserved >= dest->size)
4088                                        dest->full = 1;
4089                                num_bytes -= bytes_to_add;
4090                        }
4091                        spin_unlock(&dest->lock);
4092                }
4093                if (num_bytes) {
4094                        spin_lock(&space_info->lock);
4095                        space_info->bytes_may_use -= num_bytes;
4096                        trace_btrfs_space_reservation(fs_info, "space_info",
4097                                        space_info->flags, num_bytes, 0);
4098                        space_info->reservation_progress++;
4099                        spin_unlock(&space_info->lock);
4100                }
4101        }
4102}
4103
4104static int block_rsv_migrate_bytes(struct btrfs_block_rsv *src,
4105                                   struct btrfs_block_rsv *dst, u64 num_bytes)
4106{
4107        int ret;
4108
4109        ret = block_rsv_use_bytes(src, num_bytes);
4110        if (ret)
4111                return ret;
4112
4113        block_rsv_add_bytes(dst, num_bytes, 1);
4114        return 0;
4115}
4116
4117void btrfs_init_block_rsv(struct btrfs_block_rsv *rsv)
4118{
4119        memset(rsv, 0, sizeof(*rsv));
4120        spin_lock_init(&rsv->lock);
4121}
4122
4123struct btrfs_block_rsv *btrfs_alloc_block_rsv(struct btrfs_root *root)
4124{
4125        struct btrfs_block_rsv *block_rsv;
4126        struct btrfs_fs_info *fs_info = root->fs_info;
4127
4128        block_rsv = kmalloc(sizeof(*block_rsv), GFP_NOFS);
4129        if (!block_rsv)
4130                return NULL;
4131
4132        btrfs_init_block_rsv(block_rsv);
4133        block_rsv->space_info = __find_space_info(fs_info,
4134                                                  BTRFS_BLOCK_GROUP_METADATA);
4135        return block_rsv;
4136}
4137
4138void btrfs_free_block_rsv(struct btrfs_root *root,
4139                          struct btrfs_block_rsv *rsv)
4140{
4141        btrfs_block_rsv_release(root, rsv, (u64)-1);
4142        kfree(rsv);
4143}
4144
4145static inline int __block_rsv_add(struct btrfs_root *root,
4146                                  struct btrfs_block_rsv *block_rsv,
4147                                  u64 num_bytes, int flush)
4148{
4149        int ret;
4150
4151        if (num_bytes == 0)
4152                return 0;
4153
4154        ret = reserve_metadata_bytes(root, block_rsv, num_bytes, flush);
4155        if (!ret) {
4156                block_rsv_add_bytes(block_rsv, num_bytes, 1);
4157                return 0;
4158        }
4159
4160        return ret;
4161}
4162
4163int btrfs_block_rsv_add(struct btrfs_root *root,
4164                        struct btrfs_block_rsv *block_rsv,
4165                        u64 num_bytes)
4166{
4167        return __block_rsv_add(root, block_rsv, num_bytes, 1);
4168}
4169
4170int btrfs_block_rsv_add_noflush(struct btrfs_root *root,
4171                                struct btrfs_block_rsv *block_rsv,
4172                                u64 num_bytes)
4173{
4174        return __block_rsv_add(root, block_rsv, num_bytes, 0);
4175}
4176
4177int btrfs_block_rsv_check(struct btrfs_root *root,
4178                          struct btrfs_block_rsv *block_rsv, int min_factor)
4179{
4180        u64 num_bytes = 0;
4181        int ret = -ENOSPC;
4182
4183        if (!block_rsv)
4184                return 0;
4185
4186        spin_lock(&block_rsv->lock);
4187        num_bytes = div_factor(block_rsv->size, min_factor);
4188        if (block_rsv->reserved >= num_bytes)
4189                ret = 0;
4190        spin_unlock(&block_rsv->lock);
4191
4192        return ret;
4193}
4194
4195static inline int __btrfs_block_rsv_refill(struct btrfs_root *root,
4196                                           struct btrfs_block_rsv *block_rsv,
4197                                           u64 min_reserved, int flush)
4198{
4199        u64 num_bytes = 0;
4200        int ret = -ENOSPC;
4201
4202        if (!block_rsv)
4203                return 0;
4204
4205        spin_lock(&block_rsv->lock);
4206        num_bytes = min_reserved;
4207        if (block_rsv->reserved >= num_bytes)
4208                ret = 0;
4209        else
4210                num_bytes -= block_rsv->reserved;
4211        spin_unlock(&block_rsv->lock);
4212
4213        if (!ret)
4214                return 0;
4215
4216        ret = reserve_metadata_bytes(root, block_rsv, num_bytes, flush);
4217        if (!ret) {
4218                block_rsv_add_bytes(block_rsv, num_bytes, 0);
4219                return 0;
4220        }
4221
4222        return ret;
4223}
4224
4225int btrfs_block_rsv_refill(struct btrfs_root *root,
4226                           struct btrfs_block_rsv *block_rsv,
4227                           u64 min_reserved)
4228{
4229        return __btrfs_block_rsv_refill(root, block_rsv, min_reserved, 1);
4230}
4231
4232int btrfs_block_rsv_refill_noflush(struct btrfs_root *root,
4233                                   struct btrfs_block_rsv *block_rsv,
4234                                   u64 min_reserved)
4235{
4236        return __btrfs_block_rsv_refill(root, block_rsv, min_reserved, 0);
4237}
4238
4239int btrfs_block_rsv_migrate(struct btrfs_block_rsv *src_rsv,
4240                            struct btrfs_block_rsv *dst_rsv,
4241                            u64 num_bytes)
4242{
4243        return block_rsv_migrate_bytes(src_rsv, dst_rsv, num_bytes);
4244}
4245
4246void btrfs_block_rsv_release(struct btrfs_root *root,
4247                             struct btrfs_block_rsv *block_rsv,
4248                             u64 num_bytes)
4249{
4250        struct btrfs_block_rsv *global_rsv = &root->fs_info->global_block_rsv;
4251        if (global_rsv->full || global_rsv == block_rsv ||
4252            block_rsv->space_info != global_rsv->space_info)
4253                global_rsv = NULL;
4254        block_rsv_release_bytes(root->fs_info, block_rsv, global_rsv,
4255                                num_bytes);
4256}
4257
4258/*
4259 * helper to calculate size of global block reservation.
4260 * the desired value is sum of space used by extent tree,
4261 * checksum tree and root tree
4262 */
4263static u64 calc_global_metadata_size(struct btrfs_fs_info *fs_info)
4264{
4265        struct btrfs_space_info *sinfo;
4266        u64 num_bytes;
4267        u64 meta_used;
4268        u64 data_used;
4269        int csum_size = btrfs_super_csum_size(fs_info->super_copy);
4270
4271        sinfo = __find_space_info(fs_info, BTRFS_BLOCK_GROUP_DATA);
4272        spin_lock(&sinfo->lock);
4273        data_used = sinfo->bytes_used;
4274        spin_unlock(&sinfo->lock);
4275
4276        sinfo = __find_space_info(fs_info, BTRFS_BLOCK_GROUP_METADATA);
4277        spin_lock(&sinfo->lock);
4278        if (sinfo->flags & BTRFS_BLOCK_GROUP_DATA)
4279                data_used = 0;
4280        meta_used = sinfo->bytes_used;
4281        spin_unlock(&sinfo->lock);
4282
4283        num_bytes = (data_used >> fs_info->sb->s_blocksize_bits) *
4284                    csum_size * 2;
4285        num_bytes += div64_u64(data_used + meta_used, 50);
4286
4287        if (num_bytes * 3 > meta_used)
4288                num_bytes = div64_u64(meta_used, 3);
4289
4290        return ALIGN(num_bytes, fs_info->extent_root->leafsize << 10);
4291}
4292
4293static void update_global_block_rsv(struct btrfs_fs_info *fs_info)
4294{
4295        struct btrfs_block_rsv *block_rsv = &fs_info->global_block_rsv;
4296        struct btrfs_space_info *sinfo = block_rsv->space_info;
4297        u64 num_bytes;
4298
4299        num_bytes = calc_global_metadata_size(fs_info);
4300
4301        spin_lock(&sinfo->lock);
4302        spin_lock(&block_rsv->lock);
4303
4304        block_rsv->size = num_bytes;
4305
4306        num_bytes = sinfo->bytes_used + sinfo->bytes_pinned +
4307                    sinfo->bytes_reserved + sinfo->bytes_readonly +
4308                    sinfo->bytes_may_use;
4309
4310        if (sinfo->total_bytes > num_bytes) {
4311                num_bytes = sinfo->total_bytes - num_bytes;
4312                block_rsv->reserved += num_bytes;
4313                sinfo->bytes_may_use += num_bytes;
4314                trace_btrfs_space_reservation(fs_info, "space_info",
4315                                      sinfo->flags, num_bytes, 1);
4316        }
4317
4318        if (block_rsv->reserved >= block_rsv->size) {
4319                num_bytes = block_rsv->reserved - block_rsv->size;
4320                sinfo->bytes_may_use -= num_bytes;
4321                trace_btrfs_space_reservation(fs_info, "space_info",
4322                                      sinfo->flags, num_bytes, 0);
4323                sinfo->reservation_progress++;
4324                block_rsv->reserved = block_rsv->size;
4325                block_rsv->full = 1;
4326        }
4327
4328        spin_unlock(&block_rsv->lock);
4329        spin_unlock(&sinfo->lock);
4330}
4331
4332static void init_global_block_rsv(struct btrfs_fs_info *fs_info)
4333{
4334        struct btrfs_space_info *space_info;
4335
4336        space_info = __find_space_info(fs_info, BTRFS_BLOCK_GROUP_SYSTEM);
4337        fs_info->chunk_block_rsv.space_info = space_info;
4338
4339        space_info = __find_space_info(fs_info, BTRFS_BLOCK_GROUP_METADATA);
4340        fs_info->global_block_rsv.space_info = space_info;
4341        fs_info->delalloc_block_rsv.space_info = space_info;
4342        fs_info->trans_block_rsv.space_info = space_info;
4343        fs_info->empty_block_rsv.space_info = space_info;
4344        fs_info->delayed_block_rsv.space_info = space_info;
4345
4346        fs_info->extent_root->block_rsv = &fs_info->global_block_rsv;
4347        fs_info->csum_root->block_rsv = &fs_info->global_block_rsv;
4348        fs_info->dev_root->block_rsv = &fs_info->global_block_rsv;
4349        fs_info->tree_root->block_rsv = &fs_info->global_block_rsv;
4350        fs_info->chunk_root->block_rsv = &fs_info->chunk_block_rsv;
4351
4352        update_global_block_rsv(fs_info);
4353}
4354
4355static void release_global_block_rsv(struct btrfs_fs_info *fs_info)
4356{
4357        block_rsv_release_bytes(fs_info, &fs_info->global_block_rsv, NULL,
4358                                (u64)-1);
4359        WARN_ON(fs_info->delalloc_block_rsv.size > 0);
4360        WARN_ON(fs_info->delalloc_block_rsv.reserved > 0);
4361        WARN_ON(fs_info->trans_block_rsv.size > 0);
4362        WARN_ON(fs_info->trans_block_rsv.reserved > 0);
4363        WARN_ON(fs_info->chunk_block_rsv.size > 0);
4364        WARN_ON(fs_info->chunk_block_rsv.reserved > 0);
4365        WARN_ON(fs_info->delayed_block_rsv.size > 0);
4366        WARN_ON(fs_info->delayed_block_rsv.reserved > 0);
4367}
4368
4369void btrfs_trans_release_metadata(struct btrfs_trans_handle *trans,
4370                                  struct btrfs_root *root)
4371{
4372        if (!trans->block_rsv)
4373                return;
4374
4375        if (!trans->bytes_reserved)
4376                return;
4377
4378        trace_btrfs_space_reservation(root->fs_info, "transaction",
4379                                      trans->transid, trans->bytes_reserved, 0);
4380        btrfs_block_rsv_release(root, trans->block_rsv, trans->bytes_reserved);
4381        trans->bytes_reserved = 0;
4382}
4383
4384/* Can only return 0 or -ENOSPC */
4385int btrfs_orphan_reserve_metadata(struct btrfs_trans_handle *trans,
4386                                  struct inode *inode)
4387{
4388        struct btrfs_root *root = BTRFS_I(inode)->root;
4389        struct btrfs_block_rsv *src_rsv = get_block_rsv(trans, root);
4390        struct btrfs_block_rsv *dst_rsv = root->orphan_block_rsv;
4391
4392        /*
4393         * We need to hold space in order to delete our orphan item once we've
4394         * added it, so this takes the reservation so we can release it later
4395         * when we are truly done with the orphan item.
4396         */
4397        u64 num_bytes = btrfs_calc_trans_metadata_size(root, 1);
4398        trace_btrfs_space_reservation(root->fs_info, "orphan",
4399                                      btrfs_ino(inode), num_bytes, 1);
4400        return block_rsv_migrate_bytes(src_rsv, dst_rsv, num_bytes);
4401}
4402
4403void btrfs_orphan_release_metadata(struct inode *inode)
4404{
4405        struct btrfs_root *root = BTRFS_I(inode)->root;
4406        u64 num_bytes = btrfs_calc_trans_metadata_size(root, 1);
4407        trace_btrfs_space_reservation(root->fs_info, "orphan",
4408                                      btrfs_ino(inode), num_bytes, 0);
4409        btrfs_block_rsv_release(root, root->orphan_block_rsv, num_bytes);
4410}
4411
4412int btrfs_snap_reserve_metadata(struct btrfs_trans_handle *trans,
4413                                struct btrfs_pending_snapshot *pending)
4414{
4415        struct btrfs_root *root = pending->root;
4416        struct btrfs_block_rsv *src_rsv = get_block_rsv(trans, root);
4417        struct btrfs_block_rsv *dst_rsv = &pending->block_rsv;
4418        /*
4419         * two for root back/forward refs, two for directory entries
4420         * and one for root of the snapshot.
4421         */
4422        u64 num_bytes = btrfs_calc_trans_metadata_size(root, 5);
4423        dst_rsv->space_info = src_rsv->space_info;
4424        return block_rsv_migrate_bytes(src_rsv, dst_rsv, num_bytes);
4425}
4426
4427/**
4428 * drop_outstanding_extent - drop an outstanding extent
4429 * @inode: the inode we're dropping the extent for
4430 *
4431 * This is called when we are freeing up an outstanding extent, either called
4432 * after an error or after an extent is written.  This will return the number of
4433 * reserved extents that need to be freed.  This must be called with
4434 * BTRFS_I(inode)->lock held.
4435 */
4436static unsigned drop_outstanding_extent(struct inode *inode)
4437{
4438        unsigned drop_inode_space = 0;
4439        unsigned dropped_extents = 0;
4440
4441        BUG_ON(!BTRFS_I(inode)->outstanding_extents);
4442        BTRFS_I(inode)->outstanding_extents--;
4443
4444        if (BTRFS_I(inode)->outstanding_extents == 0 &&
4445            test_and_clear_bit(BTRFS_INODE_DELALLOC_META_RESERVED,
4446                               &BTRFS_I(inode)->runtime_flags))
4447                drop_inode_space = 1;
4448
4449        /*
4450         * If we have more or the same amount of outsanding extents than we have
4451         * reserved then we need to leave the reserved extents count alone.
4452         */
4453        if (BTRFS_I(inode)->outstanding_extents >=
4454            BTRFS_I(inode)->reserved_extents)
4455                return drop_inode_space;
4456
4457        dropped_extents = BTRFS_I(inode)->reserved_extents -
4458                BTRFS_I(inode)->outstanding_extents;
4459        BTRFS_I(inode)->reserved_extents -= dropped_extents;
4460        return dropped_extents + drop_inode_space;
4461}
4462
4463/**
4464 * calc_csum_metadata_size - return the amount of metada space that must be
4465 *      reserved/free'd for the given bytes.
4466 * @inode: the inode we're manipulating
4467 * @num_bytes: the number of bytes in question
4468 * @reserve: 1 if we are reserving space, 0 if we are freeing space
4469 *
4470 * This adjusts the number of csum_bytes in the inode and then returns the
4471 * correct amount of metadata that must either be reserved or freed.  We
4472 * calculate how many checksums we can fit into one leaf and then divide the
4473 * number of bytes that will need to be checksumed by this value to figure out
4474 * how many checksums will be required.  If we are adding bytes then the number
4475 * may go up and we will return the number of additional bytes that must be
4476 * reserved.  If it is going down we will return the number of bytes that must
4477 * be freed.
4478 *
4479 * This must be called with BTRFS_I(inode)->lock held.
4480 */
4481static u64 calc_csum_metadata_size(struct inode *inode, u64 num_bytes,
4482                                   int reserve)
4483{
4484        struct btrfs_root *root = BTRFS_I(inode)->root;
4485        u64 csum_size;
4486        int num_csums_per_leaf;
4487        int num_csums;
4488        int old_csums;
4489
4490        if (BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM &&
4491            BTRFS_I(inode)->csum_bytes == 0)
4492                return 0;
4493
4494        old_csums = (int)div64_u64(BTRFS_I(inode)->csum_bytes, root->sectorsize);
4495        if (reserve)
4496                BTRFS_I(inode)->csum_bytes += num_bytes;
4497        else
4498                BTRFS_I(inode)->csum_bytes -= num_bytes;
4499        csum_size = BTRFS_LEAF_DATA_SIZE(root) - sizeof(struct btrfs_item);
4500        num_csums_per_leaf = (int)div64_u64(csum_size,
4501                                            sizeof(struct btrfs_csum_item) +
4502                                            sizeof(struct btrfs_disk_key));
4503        num_csums = (int)div64_u64(BTRFS_I(inode)->csum_bytes, root->sectorsize);
4504        num_csums = num_csums + num_csums_per_leaf - 1;
4505        num_csums = num_csums / num_csums_per_leaf;
4506
4507        old_csums = old_csums + num_csums_per_leaf - 1;
4508        old_csums = old_csums / num_csums_per_leaf;
4509
4510        /* No change, no need to reserve more */
4511        if (old_csums == num_csums)
4512                return 0;
4513
4514        if (reserve)
4515                return btrfs_calc_trans_metadata_size(root,
4516                                                      num_csums - old_csums);
4517
4518        return btrfs_calc_trans_metadata_size(root, old_csums - num_csums);
4519}
4520
4521int btrfs_delalloc_reserve_metadata(struct inode *inode, u64 num_bytes)
4522{
4523        struct btrfs_root *root = BTRFS_I(inode)->root;
4524        struct btrfs_block_rsv *block_rsv = &root->fs_info->delalloc_block_rsv;
4525        u64 to_reserve = 0;
4526        u64 csum_bytes;
4527        unsigned nr_extents = 0;
4528        int extra_reserve = 0;
4529        int flush = 1;
4530        int ret;
4531
4532        /* Need to be holding the i_mutex here if we aren't free space cache */
4533        if (btrfs_is_free_space_inode(inode))
4534                flush = 0;
4535
4536        if (flush && btrfs_transaction_in_commit(root->fs_info))
4537                schedule_timeout(1);
4538
4539        mutex_lock(&BTRFS_I(inode)->delalloc_mutex);
4540        num_bytes = ALIGN(num_bytes, root->sectorsize);
4541
4542        spin_lock(&BTRFS_I(inode)->lock);
4543        BTRFS_I(inode)->outstanding_extents++;
4544
4545        if (BTRFS_I(inode)->outstanding_extents >
4546            BTRFS_I(inode)->reserved_extents)
4547                nr_extents = BTRFS_I(inode)->outstanding_extents -
4548                        BTRFS_I(inode)->reserved_extents;
4549
4550        /*
4551         * Add an item to reserve for updating the inode when we complete the
4552         * delalloc io.
4553         */
4554        if (!test_bit(BTRFS_INODE_DELALLOC_META_RESERVED,
4555                      &BTRFS_I(inode)->runtime_flags)) {
4556                nr_extents++;
4557                extra_reserve = 1;
4558        }
4559
4560        to_reserve = btrfs_calc_trans_metadata_size(root, nr_extents);
4561        to_reserve += calc_csum_metadata_size(inode, num_bytes, 1);
4562        csum_bytes = BTRFS_I(inode)->csum_bytes;
4563        spin_unlock(&BTRFS_I(inode)->lock);
4564
4565        if (root->fs_info->quota_enabled) {
4566                ret = btrfs_qgroup_reserve(root, num_bytes +
4567                                           nr_extents * root->leafsize);
4568                if (ret) {
4569                        mutex_unlock(&BTRFS_I(inode)->delalloc_mutex);
4570                        return ret;
4571                }
4572        }
4573
4574        ret = reserve_metadata_bytes(root, block_rsv, to_reserve, flush);
4575        if (ret) {
4576                u64 to_free = 0;
4577                unsigned dropped;
4578
4579                spin_lock(&BTRFS_I(inode)->lock);
4580                dropped = drop_outstanding_extent(inode);
4581                /*
4582                 * If the inodes csum_bytes is the same as the original
4583                 * csum_bytes then we know we haven't raced with any free()ers
4584                 * so we can just reduce our inodes csum bytes and carry on.
4585                 * Otherwise we have to do the normal free thing to account for
4586                 * the case that the free side didn't free up its reserve
4587                 * because of this outstanding reservation.
4588                 */
4589                if (BTRFS_I(inode)->csum_bytes == csum_bytes)
4590                        calc_csum_metadata_size(inode, num_bytes, 0);
4591                else
4592                        to_free = calc_csum_metadata_size(inode, num_bytes, 0);
4593                spin_unlock(&BTRFS_I(inode)->lock);
4594                if (dropped)
4595                        to_free += btrfs_calc_trans_metadata_size(root, dropped);
4596
4597                if (to_free) {
4598                        btrfs_block_rsv_release(root, block_rsv, to_free);
4599                        trace_btrfs_space_reservation(root->fs_info,
4600                                                      "delalloc",
4601                                                      btrfs_ino(inode),
4602                                                      to_free, 0);
4603                }
4604                mutex_unlock(&BTRFS_I(inode)->delalloc_mutex);
4605                return ret;
4606        }
4607
4608        spin_lock(&BTRFS_I(inode)->lock);
4609        if (extra_reserve) {
4610                set_bit(BTRFS_INODE_DELALLOC_META_RESERVED,
4611                        &BTRFS_I(inode)->runtime_flags);
4612                nr_extents--;
4613        }
4614        BTRFS_I(inode)->reserved_extents += nr_extents;
4615        spin_unlock(&BTRFS_I(inode)->lock);
4616        mutex_unlock(&BTRFS_I(inode)->delalloc_mutex);
4617
4618        if (to_reserve)
4619                trace_btrfs_space_reservation(root->fs_info,"delalloc",
4620                                              btrfs_ino(inode), to_reserve, 1);
4621        block_rsv_add_bytes(block_rsv, to_reserve, 1);
4622
4623        return 0;
4624}
4625
4626/**
4627 * btrfs_delalloc_release_metadata - release a metadata reservation for an inode
4628 * @inode: the inode to release the reservation for
4629 * @num_bytes: the number of bytes we're releasing
4630 *
4631 * This will release the metadata reservation for an inode.  This can be called
4632 * once we complete IO for a given set of bytes to release their metadata
4633 * reservations.
4634 */
4635void btrfs_delalloc_release_metadata(struct inode *inode, u64 num_bytes)
4636{
4637        struct btrfs_root *root = BTRFS_I(inode)->root;
4638        u64 to_free = 0;
4639        unsigned dropped;
4640
4641        num_bytes = ALIGN(num_bytes, root->sectorsize);
4642        spin_lock(&BTRFS_I(inode)->lock);
4643        dropped = drop_outstanding_extent(inode);
4644
4645        to_free = calc_csum_metadata_size(inode, num_bytes, 0);
4646        spin_unlock(&BTRFS_I(inode)->lock);
4647        if (dropped > 0)
4648                to_free += btrfs_calc_trans_metadata_size(root, dropped);
4649
4650        trace_btrfs_space_reservation(root->fs_info, "delalloc",
4651                                      btrfs_ino(inode), to_free, 0);
4652        if (root->fs_info->quota_enabled) {
4653                btrfs_qgroup_free(root, num_bytes +
4654                                        dropped * root->leafsize);
4655        }
4656
4657        btrfs_block_rsv_release(root, &root->fs_info->delalloc_block_rsv,
4658                                to_free);
4659}
4660
4661/**
4662 * btrfs_delalloc_reserve_space - reserve data and metadata space for delalloc
4663 * @inode: inode we're writing to
4664 * @num_bytes: the number of bytes we want to allocate
4665 *
4666 * This will do the following things
4667 *
4668 * o reserve space in the data space info for num_bytes
4669 * o reserve space in the metadata space info based on number of outstanding
4670 *   extents and how much csums will be needed
4671 * o add to the inodes ->delalloc_bytes
4672 * o add it to the fs_info's delalloc inodes list.
4673 *
4674 * This will return 0 for success and -ENOSPC if there is no space left.
4675 */
4676int btrfs_delalloc_reserve_space(struct inode *inode, u64 num_bytes)
4677{
4678        int ret;
4679
4680        ret = btrfs_check_data_free_space(inode, num_bytes);
4681        if (ret)
4682                return ret;
4683
4684        ret = btrfs_delalloc_reserve_metadata(inode, num_bytes);
4685        if (ret) {
4686                btrfs_free_reserved_data_space(inode, num_bytes);
4687                return ret;
4688        }
4689
4690        return 0;
4691}
4692
4693/**
4694 * btrfs_delalloc_release_space - release data and metadata space for delalloc
4695 * @inode: inode we're releasing space for
4696 * @num_bytes: the number of bytes we want to free up
4697 *
4698 * This must be matched with a call to btrfs_delalloc_reserve_space.  This is
4699 * called in the case that we don't need the metadata AND data reservations
4700 * anymore.  So if there is an error or we insert an inline extent.
4701 *
4702 * This function will release the metadata space that was not used and will
4703 * decrement ->delalloc_bytes and remove it from the fs_info delalloc_inodes
4704 * list if there are no delalloc bytes left.
4705 */
4706void btrfs_delalloc_release_space(struct inode *inode, u64 num_bytes)
4707{
4708        btrfs_delalloc_release_metadata(inode, num_bytes);
4709        btrfs_free_reserved_data_space(inode, num_bytes);
4710}
4711
4712static int update_block_group(struct btrfs_trans_handle *trans,
4713                              struct btrfs_root *root,
4714                              u64 bytenr, u64 num_bytes, int alloc)
4715{
4716        struct btrfs_block_group_cache *cache = NULL;
4717        struct btrfs_fs_info *info = root->fs_info;
4718        u64 total = num_bytes;
4719        u64 old_val;
4720        u64 byte_in_group;
4721        int factor;
4722
4723        /* block accounting for super block */
4724        spin_lock(&info->delalloc_lock);
4725        old_val = btrfs_super_bytes_used(info->super_copy);
4726        if (alloc)
4727                old_val += num_bytes;
4728        else
4729                old_val -= num_bytes;
4730        btrfs_set_super_bytes_used(info->super_copy, old_val);
4731        spin_unlock(&info->delalloc_lock);
4732
4733        while (total) {
4734                cache = btrfs_lookup_block_group(info, bytenr);
4735                if (!cache)
4736                        return -ENOENT;
4737                if (cache->flags & (BTRFS_BLOCK_GROUP_DUP |
4738                                    BTRFS_BLOCK_GROUP_RAID1 |
4739                                    BTRFS_BLOCK_GROUP_RAID10))
4740                        factor = 2;
4741                else
4742                        factor = 1;
4743                /*
4744                 * If this block group has free space cache written out, we
4745                 * need to make sure to load it if we are removing space.  This
4746                 * is because we need the unpinning stage to actually add the
4747                 * space back to the block group, otherwise we will leak space.
4748                 */
4749                if (!alloc && cache->cached == BTRFS_CACHE_NO)
4750                        cache_block_group(cache, trans, NULL, 1);
4751
4752                byte_in_group = bytenr - cache->key.objectid;
4753                WARN_ON(byte_in_group > cache->key.offset);
4754
4755                spin_lock(&cache->space_info->lock);
4756                spin_lock(&cache->lock);
4757
4758                if (btrfs_test_opt(root, SPACE_CACHE) &&
4759                    cache->disk_cache_state < BTRFS_DC_CLEAR)
4760                        cache->disk_cache_state = BTRFS_DC_CLEAR;
4761
4762                cache->dirty = 1;
4763                old_val = btrfs_block_group_used(&cache->item);
4764                num_bytes = min(total, cache->key.offset - byte_in_group);
4765                if (alloc) {
4766                        old_val += num_bytes;
4767                        btrfs_set_block_group_used(&cache->item, old_val);
4768                        cache->reserved -= num_bytes;
4769                        cache->space_info->bytes_reserved -= num_bytes;
4770                        cache->space_info->bytes_used += num_bytes;
4771                        cache->space_info->disk_used += num_bytes * factor;
4772                        spin_unlock(&cache->lock);
4773                        spin_unlock(&cache->space_info->lock);
4774                } else {
4775                        old_val -= num_bytes;
4776                        btrfs_set_block_group_used(&cache->item, old_val);
4777                        cache->pinned += num_bytes;
4778                        cache->space_info->bytes_pinned += num_bytes;
4779                        cache->space_info->bytes_used -= num_bytes;
4780                        cache->space_info->disk_used -= num_bytes * factor;
4781                        spin_unlock(&cache->lock);
4782                        spin_unlock(&cache->space_info->lock);
4783
4784                        set_extent_dirty(info->pinned_extents,
4785                                         bytenr, bytenr + num_bytes - 1,
4786                                         GFP_NOFS | __GFP_NOFAIL);
4787                }
4788                btrfs_put_block_group(cache);
4789                total -= num_bytes;
4790                bytenr += num_bytes;
4791        }
4792        return 0;
4793}
4794
4795static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
4796{
4797        struct btrfs_block_group_cache *cache;
4798        u64 bytenr;
4799
4800        cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
4801        if (!cache)
4802                return 0;
4803
4804        bytenr = cache->key.objectid;
4805        btrfs_put_block_group(cache);
4806
4807        return bytenr;
4808}
4809
4810static int pin_down_extent(struct btrfs_root *root,
4811                           struct btrfs_block_group_cache *cache,
4812                           u64 bytenr, u64 num_bytes, int reserved)
4813{
4814        spin_lock(&cache->space_info->lock);
4815        spin_lock(&cache->lock);
4816        cache->pinned += num_bytes;
4817        cache->space_info->bytes_pinned += num_bytes;
4818        if (reserved) {
4819                cache->reserved -= num_bytes;
4820                cache->space_info->bytes_reserved -= num_bytes;
4821        }
4822        spin_unlock(&cache->lock);
4823        spin_unlock(&cache->space_info->lock);
4824
4825        set_extent_dirty(root->fs_info->pinned_extents, bytenr,
4826                         bytenr + num_bytes - 1, GFP_NOFS | __GFP_NOFAIL);
4827        return 0;
4828}
4829
4830/*
4831 * this function must be called within transaction
4832 */
4833int btrfs_pin_extent(struct btrfs_root *root,
4834                     u64 bytenr, u64 num_bytes, int reserved)
4835{
4836        struct btrfs_block_group_cache *cache;
4837
4838        cache = btrfs_lookup_block_group(root->fs_info, bytenr);
4839        BUG_ON(!cache); /* Logic error */
4840
4841        pin_down_extent(root, cache, bytenr, num_bytes, reserved);
4842
4843        btrfs_put_block_group(cache);
4844        return 0;
4845}
4846
4847/*
4848 * this function must be called within transaction
4849 */
4850int btrfs_pin_extent_for_log_replay(struct btrfs_trans_handle *trans,
4851                                    struct btrfs_root *root,
4852                                    u64 bytenr, u64 num_bytes)
4853{
4854        struct btrfs_block_group_cache *cache;
4855
4856        cache = btrfs_lookup_block_group(root->fs_info, bytenr);
4857        BUG_ON(!cache); /* Logic error */
4858
4859        /*
4860         * pull in the free space cache (if any) so that our pin
4861         * removes the free space from the cache.  We have load_only set
4862         * to one because the slow code to read in the free extents does check
4863         * the pinned extents.
4864         */
4865        cache_block_group(cache, trans, root, 1);
4866
4867        pin_down_extent(root, cache, bytenr, num_bytes, 0);
4868
4869        /* remove us from the free space cache (if we're there at all) */
4870        btrfs_remove_free_space(cache, bytenr, num_bytes);
4871        btrfs_put_block_group(cache);
4872        return 0;
4873}
4874
4875/**
4876 * btrfs_update_reserved_bytes - update the block_group and space info counters
4877 * @cache:      The cache we are manipulating
4878 * @num_bytes:  The number of bytes in question
4879 * @reserve:    One of the reservation enums
4880 *
4881 * This is called by the allocator when it reserves space, or by somebody who is
4882 * freeing space that was never actually used on disk.  For example if you
4883 * reserve some space for a new leaf in transaction A and before transaction A
4884 * commits you free that leaf, you call this with reserve set to 0 in order to
4885 * clear the reservation.
4886 *
4887 * Metadata reservations should be called with RESERVE_ALLOC so we do the proper
4888 * ENOSPC accounting.  For data we handle the reservation through clearing the
4889 * delalloc bits in the io_tree.  We have to do this since we could end up
4890 * allocating less disk space for the amount of data we have reserved in the
4891 * case of compression.
4892 *
4893 * If this is a reservation and the block group has become read only we cannot
4894 * make the reservation and return -EAGAIN, otherwise this function always
4895 * succeeds.
4896 */
4897static int btrfs_update_reserved_bytes(struct btrfs_block_group_cache *cache,
4898                                       u64 num_bytes, int reserve)
4899{
4900        struct btrfs_space_info *space_info = cache->space_info;
4901        int ret = 0;
4902
4903        spin_lock(&space_info->lock);
4904        spin_lock(&cache->lock);
4905        if (reserve != RESERVE_FREE) {
4906                if (cache->ro) {
4907                        ret = -EAGAIN;
4908                } else {
4909                        cache->reserved += num_bytes;
4910                        space_info->bytes_reserved += num_bytes;
4911                        if (reserve == RESERVE_ALLOC) {
4912                                trace_btrfs_space_reservation(cache->fs_info,
4913                                                "space_info", space_info->flags,
4914                                                num_bytes, 0);
4915                                space_info->bytes_may_use -= num_bytes;
4916                        }
4917                }
4918        } else {
4919                if (cache->ro)
4920                        space_info->bytes_readonly += num_bytes;
4921                cache->reserved -= num_bytes;
4922                space_info->bytes_reserved -= num_bytes;
4923                space_info->reservation_progress++;
4924        }
4925        spin_unlock(&cache->lock);
4926        spin_unlock(&space_info->lock);
4927        return ret;
4928}
4929
4930void btrfs_prepare_extent_commit(struct btrfs_trans_handle *trans,
4931                                struct btrfs_root *root)
4932{
4933        struct btrfs_fs_info *fs_info = root->fs_info;
4934        struct btrfs_caching_control *next;
4935        struct btrfs_caching_control *caching_ctl;
4936        struct btrfs_block_group_cache *cache;
4937
4938        down_write(&fs_info->extent_commit_sem);
4939
4940        list_for_each_entry_safe(caching_ctl, next,
4941                                 &fs_info->caching_block_groups, list) {
4942                cache = caching_ctl->block_group;
4943                if (block_group_cache_done(cache)) {
4944                        cache->last_byte_to_unpin = (u64)-1;
4945                        list_del_init(&caching_ctl->list);
4946                        put_caching_control(caching_ctl);
4947                } else {
4948                        cache->last_byte_to_unpin = caching_ctl->progress;
4949                }
4950        }
4951
4952        if (fs_info->pinned_extents == &fs_info->freed_extents[0])
4953                fs_info->pinned_extents = &fs_info->freed_extents[1];
4954        else
4955                fs_info->pinned_extents = &fs_info->freed_extents[0];
4956
4957        up_write(&fs_info->extent_commit_sem);
4958
4959        update_global_block_rsv(fs_info);
4960}
4961
4962static int unpin_extent_range(struct btrfs_root *root, u64 start, u64 end)
4963{
4964        struct btrfs_fs_info *fs_info = root->fs_info;
4965        struct btrfs_block_group_cache *cache = NULL;
4966        u64 len;
4967
4968        while (start <= end) {
4969                if (!cache ||
4970                    start >= cache->key.objectid + cache->key.offset) {
4971                        if (cache)
4972                                btrfs_put_block_group(cache);
4973                        cache = btrfs_lookup_block_group(fs_info, start);
4974                        BUG_ON(!cache); /* Logic error */
4975                }
4976
4977                len = cache->key.objectid + cache->key.offset - start;
4978                len = min(len, end + 1 - start);
4979
4980                if (start < cache->last_byte_to_unpin) {
4981                        len = min(len, cache->last_byte_to_unpin - start);
4982                        btrfs_add_free_space(cache, start, len);
4983                }
4984
4985                start += len;
4986
4987                spin_lock(&cache->space_info->lock);
4988                spin_lock(&cache->lock);
4989                cache->pinned -= len;
4990                cache->space_info->bytes_pinned -= len;
4991                if (cache->ro)
4992                        cache->space_info->bytes_readonly += len;
4993                spin_unlock(&cache->lock);
4994                spin_unlock(&cache->space_info->lock);
4995        }
4996
4997        if (cache)
4998                btrfs_put_block_group(cache);
4999        return 0;
5000}
5001
5002int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
5003                               struct btrfs_root *root)
5004{
5005        struct btrfs_fs_info *fs_info = root->fs_info;
5006        struct extent_io_tree *unpin;
5007        u64 start;
5008        u64 end;
5009        int ret;
5010
5011        if (trans->aborted)
5012                return 0;
5013
5014        if (fs_info->pinned_extents == &fs_info->freed_extents[0])
5015                unpin = &fs_info->freed_extents[1];
5016        else
5017                unpin = &fs_info->freed_extents[0];
5018
5019        while (1) {
5020                ret = find_first_extent_bit(unpin, 0, &start, &end,
5021                                            EXTENT_DIRTY);
5022                if (ret)
5023                        break;
5024
5025                if (btrfs_test_opt(root, DISCARD))
5026                        ret = btrfs_discard_extent(root, start,
5027                                                   end + 1 - start, NULL);
5028
5029                clear_extent_dirty(unpin, start, end, GFP_NOFS);
5030                unpin_extent_range(root, start, end);
5031                cond_resched();
5032        }
5033
5034        return 0;
5035}
5036
5037static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
5038                                struct btrfs_root *root,
5039                                u64 bytenr, u64 num_bytes, u64 parent,
5040                                u64 root_objectid, u64 owner_objectid,
5041                                u64 owner_offset, int refs_to_drop,
5042                                struct btrfs_delayed_extent_op *extent_op)
5043{
5044        struct btrfs_key key;
5045        struct btrfs_path *path;
5046        struct btrfs_fs_info *info = root->fs_info;
5047        struct btrfs_root *extent_root = info->extent_root;
5048        struct extent_buffer *leaf;
5049        struct btrfs_extent_item *ei;
5050        struct btrfs_extent_inline_ref *iref;
5051        int ret;
5052        int is_data;
5053        int extent_slot = 0;
5054        int found_extent = 0;
5055        int num_to_del = 1;
5056        u32 item_size;
5057        u64 refs;
5058
5059        path = btrfs_alloc_path();
5060        if (!path)
5061                return -ENOMEM;
5062
5063        path->reada = 1;
5064        path->leave_spinning = 1;
5065
5066        is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
5067        BUG_ON(!is_data && refs_to_drop != 1);
5068
5069        ret = lookup_extent_backref(trans, extent_root, path, &iref,
5070                                    bytenr, num_bytes, parent,
5071                                    root_objectid, owner_objectid,
5072                                    owner_offset);
5073        if (ret == 0) {
5074                extent_slot = path->slots[0];
5075                while (extent_slot >= 0) {
5076                        btrfs_item_key_to_cpu(path->nodes[0], &key,
5077                                              extent_slot);
5078                        if (key.objectid != bytenr)
5079                                break;
5080                        if (key.type == BTRFS_EXTENT_ITEM_KEY &&
5081                            key.offset == num_bytes) {
5082                                found_extent = 1;
5083                                break;
5084                        }
5085                        if (path->slots[0] - extent_slot > 5)
5086                                break;
5087                        extent_slot--;
5088                }
5089#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
5090                item_size = btrfs_item_size_nr(path->nodes[0], extent_slot);
5091                if (found_extent && item_size < sizeof(*ei))
5092                        found_extent = 0;