fs/btrfs/extent-tree.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18 #include <linux/sched.h>
  19 #include <linux/pagemap.h>
  20 #include <linux/writeback.h>
  21 #include <linux/blkdev.h>
  22 #include "hash.h"
  23 #include "crc32c.h"
  24 #include "ctree.h"
  25 #include "disk-io.h"
  26 #include "print-tree.h"
  27 #include "transaction.h"
  28 #include "volumes.h"
  29 #include "locking.h"
  30 #include "ref-cache.h"
  31
  32 #define BLOCK_GROUP_DATA     EXTENT_WRITEBACK
  33 #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
  34 #define BLOCK_GROUP_SYSTEM   EXTENT_NEW
  35
  36 #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
  37
  38 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  39                                  btrfs_root *extent_root);
  40 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  41                                btrfs_root *extent_root);
  42 static struct btrfs_block_group_cache *
  43 __btrfs_find_block_group(struct btrfs_root *root,
  44                          struct btrfs_block_group_cache *hint,
  45                          u64 search_start, int data, int owner);
  46
  47 void maybe_lock_mutex(struct btrfs_root *root)
  48 {
  49         if (root != root->fs_info->extent_root &&
  50             root != root->fs_info->chunk_root &&
  51             root != root->fs_info->dev_root) {
  52                 mutex_lock(&root->fs_info->alloc_mutex);
  53         }
  54 }
  55
  56 void maybe_unlock_mutex(struct btrfs_root *root)
  57 {
  58         if (root != root->fs_info->extent_root &&
  59             root != root->fs_info->chunk_root &&
  60             root != root->fs_info->dev_root) {
  61                 mutex_unlock(&root->fs_info->alloc_mutex);
  62         }
  63 }
  64
  65 static int cache_block_group(struct btrfs_root *root,
  66                              struct btrfs_block_group_cache *block_group)
  67 {
  68         struct btrfs_path *path;
  69         int ret;
  70         struct btrfs_key key;
  71         struct extent_buffer *leaf;
  72         struct extent_io_tree *free_space_cache;
  73         int slot;
  74         u64 last = 0;
  75         u64 hole_size;
  76         u64 first_free;
  77         int found = 0;
  78
  79         if (!block_group)
  80                 return 0;
  81
  82         root = root->fs_info->extent_root;
  83         free_space_cache = &root->fs_info->free_space_cache;
  84
  85         if (block_group->cached)
  86                 return 0;
  87
  88         path = btrfs_alloc_path();
  89         if (!path)
  90                 return -ENOMEM;
  91
  92         path->reada = 2;
  93         /*
  94          * we get into deadlocks with paths held by callers of this function.
  95          * since the alloc_mutex is protecting things right now, just
  96          * skip the locking here
  97          */
  98         path->skip_locking = 1;
  99         first_free = block_group->key.objectid;
 100         key.objectid = block_group->key.objectid;
 101         key.offset = 0;
 102         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 103         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 104         if (ret < 0)
 105                 return ret;
 106         ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
 107         if (ret < 0)
 108                 return ret;
 109         if (ret == 0) {
 110                 leaf = path->nodes[0];
 111                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 112                 if (key.objectid + key.offset > first_free)
 113                         first_free = key.objectid + key.offset;
 114         }
 115         while(1) {
 116                 leaf = path->nodes[0];
 117                 slot = path->slots[0];
 118                 if (slot >= btrfs_header_nritems(leaf)) {
 119                         ret = btrfs_next_leaf(root, path);
 120                         if (ret < 0)
 121                                 goto err;
 122                         if (ret == 0) {
 123                                 continue;
 124                         } else {
 125                                 break;
 126                         }
 127                 }
 128                 btrfs_item_key_to_cpu(leaf, &key, slot);
 129                 if (key.objectid < block_group->key.objectid) {
 130                         goto next;
 131                 }
 132                 if (key.objectid >= block_group->key.objectid +
 133                     block_group->key.offset) {
 134                         break;
 135                 }
 136
 137                 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
 138                         if (!found) {
 139                                 last = first_free;
 140                                 found = 1;
 141                         }
 142                         if (key.objectid > last) {
 143                                 hole_size = key.objectid - last;
 144                                 set_extent_dirty(free_space_cache, last,
 145                                                  last + hole_size - 1,
 146                                                  GFP_NOFS);
 147                         }
 148                         last = key.objectid + key.offset;
 149                 }
 150 next:
 151                 path->slots[0]++;
 152         }
 153
 154         if (!found)
 155                 last = first_free;
 156         if (block_group->key.objectid +
 157             block_group->key.offset > last) {
 158                 hole_size = block_group->key.objectid +
 159                         block_group->key.offset - last;
 160                 set_extent_dirty(free_space_cache, last,
 161                                  last + hole_size - 1, GFP_NOFS);
 162         }
 163         block_group->cached = 1;
 164 err:
 165         btrfs_free_path(path);
 166         return 0;
 167 }
 168
 169 struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
 170                                                        btrfs_fs_info *info,
 171                                                          u64 bytenr)
 172 {
 173         struct extent_io_tree *block_group_cache;
 174         struct btrfs_block_group_cache *block_group = NULL;
 175         u64 ptr;
 176         u64 start;
 177         u64 end;
 178         int ret;
 179
 180         bytenr = max_t(u64, bytenr,
 181                        BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
 182         block_group_cache = &info->block_group_cache;
 183         ret = find_first_extent_bit(block_group_cache,
 184                                     bytenr, &start, &end,
 185                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
 186                                     BLOCK_GROUP_SYSTEM);
 187         if (ret) {
 188                 return NULL;
 189         }
 190         ret = get_state_private(block_group_cache, start, &ptr);
 191         if (ret)
 192                 return NULL;
 193
 194         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 195         return block_group;
 196 }
 197
 198 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 199                                                          btrfs_fs_info *info,
 200                                                          u64 bytenr)
 201 {
 202         struct extent_io_tree *block_group_cache;
 203         struct btrfs_block_group_cache *block_group = NULL;
 204         u64 ptr;
 205         u64 start;
 206         u64 end;
 207         int ret;
 208
 209         bytenr = max_t(u64, bytenr,
 210                        BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
 211         block_group_cache = &info->block_group_cache;
 212         ret = find_first_extent_bit(block_group_cache,
 213                                     bytenr, &start, &end,
 214                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
 215                                     BLOCK_GROUP_SYSTEM);
 216         if (ret) {
 217                 return NULL;
 218         }
 219         ret = get_state_private(block_group_cache, start, &ptr);
 220         if (ret)
 221                 return NULL;
 222
 223         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 224         if (block_group->key.objectid <= bytenr && bytenr <
 225             block_group->key.objectid + block_group->key.offset)
 226                 return block_group;
 227         return NULL;
 228 }
 229
 230 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
 231 {
 232         return (cache->flags & bits) == bits;
 233 }
 234
 235 static int noinline find_search_start(struct btrfs_root *root,
 236                               struct btrfs_block_group_cache **cache_ret,
 237                               u64 *start_ret, u64 num, int data)
 238 {
 239         int ret;
 240         struct btrfs_block_group_cache *cache = *cache_ret;
 241         struct extent_io_tree *free_space_cache;
 242         struct extent_state *state;
 243         u64 last;
 244         u64 start = 0;
 245         u64 cache_miss = 0;
 246         u64 total_fs_bytes;
 247         u64 search_start = *start_ret;
 248         int wrapped = 0;
 249
 250         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
 251         total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
 252         free_space_cache = &root->fs_info->free_space_cache;
 253
 254         if (!cache)
 255                 goto out;
 256
 257 again:
 258         ret = cache_block_group(root, cache);
 259         if (ret) {
 260                 goto out;
 261         }
 262
 263         last = max(search_start, cache->key.objectid);
 264         if (!block_group_bits(cache, data) || cache->ro)
 265                 goto new_group;
 266
 267         spin_lock_irq(&free_space_cache->lock);
 268         state = find_first_extent_bit_state(free_space_cache, last, EXTENT_DIRTY);
 269         while(1) {
 270                 if (!state) {
 271                         if (!cache_miss)
 272                                 cache_miss = last;
 273                         spin_unlock_irq(&free_space_cache->lock);
 274                         goto new_group;
 275                 }
 276
 277                 start = max(last, state->start);
 278                 last = state->end + 1;
 279                 if (last - start < num) {
 280                         do {
 281                                 state = extent_state_next(state);
 282                         } while(state && !(state->state & EXTENT_DIRTY));
 283                         continue;
 284                 }
 285                 spin_unlock_irq(&free_space_cache->lock);
 286                 if (cache->ro) {
 287                         goto new_group;
 288                 }
 289                 if (start + num > cache->key.objectid + cache->key.offset)
 290                         goto new_group;
 291                 if (!block_group_bits(cache, data)) {
 292                         printk("block group bits don't match %Lu %d\n", cache->flags, data);
 293                 }
 294                 *start_ret = start;
 295                 return 0;
 296         }
 297 out:
 298         cache = btrfs_lookup_block_group(root->fs_info, search_start);
 299         if (!cache) {
 300                 printk("Unable to find block group for %Lu\n", search_start);
 301                 WARN_ON(1);
 302         }
 303         return -ENOSPC;
 304
 305 new_group:
 306         last = cache->key.objectid + cache->key.offset;
 307 wrapped:
 308         cache = btrfs_lookup_first_block_group(root->fs_info, last);
 309         if (!cache || cache->key.objectid >= total_fs_bytes) {
 310 no_cache:
 311                 if (!wrapped) {
 312                         wrapped = 1;
 313                         last = search_start;
 314                         goto wrapped;
 315                 }
 316                 goto out;
 317         }
 318         if (cache_miss && !cache->cached) {
 319                 cache_block_group(root, cache);
 320                 last = cache_miss;
 321                 cache = btrfs_lookup_first_block_group(root->fs_info, last);
 322         }
 323         cache_miss = 0;
 324         cache = btrfs_find_block_group(root, cache, last, data, 0);
 325         if (!cache)
 326                 goto no_cache;
 327         *cache_ret = cache;
 328         goto again;
 329 }
 330
 331 static u64 div_factor(u64 num, int factor)
 332 {
 333         if (factor == 10)
 334                 return num;
 335         num *= factor;
 336         do_div(num, 10);
 337         return num;
 338 }
 339
 340 static int block_group_state_bits(u64 flags)
 341 {
 342         int bits = 0;
 343         if (flags & BTRFS_BLOCK_GROUP_DATA)
 344                 bits |= BLOCK_GROUP_DATA;
 345         if (flags & BTRFS_BLOCK_GROUP_METADATA)
 346                 bits |= BLOCK_GROUP_METADATA;
 347         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
 348                 bits |= BLOCK_GROUP_SYSTEM;
 349         return bits;
 350 }
 351
 352 static struct btrfs_block_group_cache *
 353 __btrfs_find_block_group(struct btrfs_root *root,
 354                          struct btrfs_block_group_cache *hint,
 355                          u64 search_start, int data, int owner)
 356 {
 357         struct btrfs_block_group_cache *cache;
 358         struct extent_io_tree *block_group_cache;
 359         struct btrfs_block_group_cache *found_group = NULL;
 360         struct btrfs_fs_info *info = root->fs_info;
 361         u64 used;
 362         u64 last = 0;
 363         u64 start;
 364         u64 end;
 365         u64 free_check;
 366         u64 ptr;
 367         int bit;
 368         int ret;
 369         int full_search = 0;
 370         int factor = 10;
 371         int wrapped = 0;
 372
 373         block_group_cache = &info->block_group_cache;
 374
 375         if (data & BTRFS_BLOCK_GROUP_METADATA)
 376                 factor = 9;
 377
 378         bit = block_group_state_bits(data);
 379
 380         if (search_start) {
 381                 struct btrfs_block_group_cache *shint;
 382                 shint = btrfs_lookup_first_block_group(info, search_start);
 383                 if (shint && block_group_bits(shint, data) && !shint->ro) {
 384                         spin_lock(&shint->lock);
 385                         used = btrfs_block_group_used(&shint->item);
 386                         if (used + shint->pinned <
 387                             div_factor(shint->key.offset, factor)) {
 388                                 spin_unlock(&shint->lock);
 389                                 return shint;
 390                         }
 391                         spin_unlock(&shint->lock);
 392                 }
 393         }
 394         if (hint && !hint->ro && block_group_bits(hint, data)) {
 395                 spin_lock(&hint->lock);
 396                 used = btrfs_block_group_used(&hint->item);
 397                 if (used + hint->pinned <
 398                     div_factor(hint->key.offset, factor)) {
 399                         spin_unlock(&hint->lock);
 400                         return hint;
 401                 }
 402                 spin_unlock(&hint->lock);
 403                 last = hint->key.objectid + hint->key.offset;
 404         } else {
 405                 if (hint)
 406                         last = max(hint->key.objectid, search_start);
 407                 else
 408                         last = search_start;
 409         }
 410 again:
 411         while(1) {
 412                 ret = find_first_extent_bit(block_group_cache, last,
 413                                             &start, &end, bit);
 414                 if (ret)
 415                         break;
 416
 417                 ret = get_state_private(block_group_cache, start, &ptr);
 418                 if (ret) {
 419                         last = end + 1;
 420                         continue;
 421                 }
 422
 423                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 424                 spin_lock(&cache->lock);
 425                 last = cache->key.objectid + cache->key.offset;
 426                 used = btrfs_block_group_used(&cache->item);
 427
 428                 if (!cache->ro && block_group_bits(cache, data)) {
 429                         free_check = div_factor(cache->key.offset, factor);
 430                         if (used + cache->pinned < free_check) {
 431                                 found_group = cache;
 432                                 spin_unlock(&cache->lock);
 433                                 goto found;
 434                         }
 435                 }
 436                 spin_unlock(&cache->lock);
 437                 cond_resched();
 438         }
 439         if (!wrapped) {
 440                 last = search_start;
 441                 wrapped = 1;
 442                 goto again;
 443         }
 444         if (!full_search && factor < 10) {
 445                 last = search_start;
 446                 full_search = 1;
 447                 factor = 10;
 448                 goto again;
 449         }
 450 found:
 451         return found_group;
 452 }
 453
 454 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 455                                                  struct btrfs_block_group_cache
 456                                                  *hint, u64 search_start,
 457                                                  int data, int owner)
 458 {
 459
 460         struct btrfs_block_group_cache *ret;
 461         ret = __btrfs_find_block_group(root, hint, search_start, data, owner);
 462         return ret;
 463 }
 464 static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
 465                            u64 owner, u64 owner_offset)
 466 {
 467         u32 high_crc = ~(u32)0;
 468         u32 low_crc = ~(u32)0;
 469         __le64 lenum;
 470         lenum = cpu_to_le64(root_objectid);
 471         high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
 472         lenum = cpu_to_le64(ref_generation);
 473         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 474         if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
 475                 lenum = cpu_to_le64(owner);
 476                 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 477                 lenum = cpu_to_le64(owner_offset);
 478                 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 479         }
 480         return ((u64)high_crc << 32) | (u64)low_crc;
 481 }
 482
 483 static int match_extent_ref(struct extent_buffer *leaf,
 484                             struct btrfs_extent_ref *disk_ref,
 485                             struct btrfs_extent_ref *cpu_ref)
 486 {
 487         int ret;
 488         int len;
 489
 490         if (cpu_ref->objectid)
 491                 len = sizeof(*cpu_ref);
 492         else
 493                 len = 2 * sizeof(u64);
 494         ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
 495                                    len);
 496         return ret == 0;
 497 }
 498
 499 static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
 500                                           struct btrfs_root *root,
 501                                           struct btrfs_path *path, u64 bytenr,
 502                                           u64 root_objectid,
 503                                           u64 ref_generation, u64 owner,
 504                                           u64 owner_offset, int del)
 505 {
 506         u64 hash;
 507         struct btrfs_key key;
 508         struct btrfs_key found_key;
 509         struct btrfs_extent_ref ref;
 510         struct extent_buffer *leaf;
 511         struct btrfs_extent_ref *disk_ref;
 512         int ret;
 513         int ret2;
 514
 515         btrfs_set_stack_ref_root(&ref, root_objectid);
 516         btrfs_set_stack_ref_generation(&ref, ref_generation);
 517         btrfs_set_stack_ref_objectid(&ref, owner);
 518         btrfs_set_stack_ref_offset(&ref, owner_offset);
 519
 520         hash = hash_extent_ref(root_objectid, ref_generation, owner,
 521                                owner_offset);
 522         key.offset = hash;
 523         key.objectid = bytenr;
 524         key.type = BTRFS_EXTENT_REF_KEY;
 525
 526         while (1) {
 527                 ret = btrfs_search_slot(trans, root, &key, path,
 528                                         del ? -1 : 0, del);
 529                 if (ret < 0)
 530                         goto out;
 531                 leaf = path->nodes[0];
 532                 if (ret != 0) {
 533                         u32 nritems = btrfs_header_nritems(leaf);
 534                         if (path->slots[0] >= nritems) {
 535                                 ret2 = btrfs_next_leaf(root, path);
 536                                 if (ret2)
 537                                         goto out;
 538                                 leaf = path->nodes[0];
 539                         }
 540                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 541                         if (found_key.objectid != bytenr ||
 542                             found_key.type != BTRFS_EXTENT_REF_KEY)
 543                                 goto out;
 544                         key.offset = found_key.offset;
 545                         if (del) {
 546                                 btrfs_release_path(root, path);
 547                                 continue;
 548                         }
 549                 }
 550                 disk_ref = btrfs_item_ptr(path->nodes[0],
 551                                           path->slots[0],
 552                                           struct btrfs_extent_ref);
 553                 if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
 554                         ret = 0;
 555                         goto out;
 556                 }
 557                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 558                 key.offset = found_key.offset + 1;
 559                 btrfs_release_path(root, path);
 560         }
 561 out:
 562         return ret;
 563 }
 564
 565 /*
 566  * Back reference rules.  Back refs have three main goals:
 567  *
 568  * 1) differentiate between all holders of references to an extent so that
 569  *    when a reference is dropped we can make sure it was a valid reference
 570  *    before freeing the extent.
 571  *
 572  * 2) Provide enough information to quickly find the holders of an extent
 573  *    if we notice a given block is corrupted or bad.
 574  *
 575  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 576  *    maintenance.  This is actually the same as #2, but with a slightly
 577  *    different use case.
 578  *
 579  * File extents can be referenced by:
 580  *
 581  * - multiple snapshots, subvolumes, or different generations in one subvol
 582  * - different files inside a single subvolume (in theory, not implemented yet)
 583  * - different offsets inside a file (bookend extents in file.c)
 584  *
 585  * The extent ref structure has fields for:
 586  *
 587  * - Objectid of the subvolume root
 588  * - Generation number of the tree holding the reference
 589  * - objectid of the file holding the reference
 590  * - offset in the file corresponding to the key holding the reference
 591  *
 592  * When a file extent is allocated the fields are filled in:
 593  *     (root_key.objectid, trans->transid, inode objectid, offset in file)
 594  *
 595  * When a leaf is cow'd new references are added for every file extent found
 596  * in the leaf.  It looks the same as the create case, but trans->transid
 597  * will be different when the block is cow'd.
 598  *
 599  *     (root_key.objectid, trans->transid, inode objectid, offset in file)
 600  *
 601  * When a file extent is removed either during snapshot deletion or file
 602  * truncation, the corresponding back reference is found
 603  * by searching for:
 604  *
 605  *     (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
 606  *      inode objectid, offset in file)
 607  *
 608  * Btree extents can be referenced by:
 609  *
 610  * - Different subvolumes
 611  * - Different generations of the same subvolume
 612  *
 613  * Storing sufficient information for a full reverse mapping of a btree
 614  * block would require storing the lowest key of the block in the backref,
 615  * and it would require updating that lowest key either before write out or
 616  * every time it changed.  Instead, the objectid of the lowest key is stored
 617  * along with the level of the tree block.  This provides a hint
 618  * about where in the btree the block can be found.  Searches through the
 619  * btree only need to look for a pointer to that block, so they stop one
 620  * level higher than the level recorded in the backref.
 621  *
 622  * Some btrees do not do reference counting on their extents.  These
 623  * include the extent tree and the tree of tree roots.  Backrefs for these
 624  * trees always have a generation of zero.
 625  *
 626  * When a tree block is created, back references are inserted:
 627  *
 628  * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
 629  *
 630  * When a tree block is cow'd in a reference counted root,
 631  * new back references are added for all the blocks it points to.
 632  * These are of the form (trans->transid will have increased since creation):
 633  *
 634  * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
 635  *
 636  * Because the lowest_key_objectid and the level are just hints
 637  * they are not used when backrefs are deleted.  When a backref is deleted:
 638  *
 639  * if backref was for a tree root:
 640  *     root_objectid = root->root_key.objectid
 641  * else
 642  *     root_objectid = btrfs_header_owner(parent)
 643  *
 644  * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
 645  *
 646  * Back Reference Key hashing:
 647  *
 648  * Back references have four fields, each 64 bits long.  Unfortunately,
 649  * This is hashed into a single 64 bit number and placed into the key offset.
 650  * The key objectid corresponds to the first byte in the extent, and the
 651  * key type is set to BTRFS_EXTENT_REF_KEY
 652  */
 653 int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
 654                                  struct btrfs_root *root,
 655                                  struct btrfs_path *path, u64 bytenr,
 656                                  u64 root_objectid, u64 ref_generation,
 657                                  u64 owner, u64 owner_offset)
 658 {
 659         u64 hash;
 660         struct btrfs_key key;
 661         struct btrfs_extent_ref ref;
 662         struct btrfs_extent_ref *disk_ref;
 663         int ret;
 664
 665         btrfs_set_stack_ref_root(&ref, root_objectid);
 666         btrfs_set_stack_ref_generation(&ref, ref_generation);
 667         btrfs_set_stack_ref_objectid(&ref, owner);
 668         btrfs_set_stack_ref_offset(&ref, owner_offset);
 669
 670         hash = hash_extent_ref(root_objectid, ref_generation, owner,
 671                                owner_offset);
 672         key.offset = hash;
 673         key.objectid = bytenr;
 674         key.type = BTRFS_EXTENT_REF_KEY;
 675
 676         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
 677         while (ret == -EEXIST) {
 678                 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 679                                           struct btrfs_extent_ref);
 680                 if (match_extent_ref(path->nodes[0], disk_ref, &ref))
 681                         goto out;
 682                 key.offset++;
 683                 btrfs_release_path(root, path);
 684                 ret = btrfs_insert_empty_item(trans, root, path, &key,
 685                                               sizeof(ref));
 686         }
 687         if (ret)
 688                 goto out;
 689         disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 690                                   struct btrfs_extent_ref);
 691         write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
 692                             sizeof(ref));
 693         btrfs_mark_buffer_dirty(path->nodes[0]);
 694 out:
 695         btrfs_release_path(root, path);
 696         return ret;
 697 }
 698
 699 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 700                                 struct btrfs_root *root,
 701                                 u64 bytenr, u64 num_bytes,
 702                                 u64 root_objectid, u64 ref_generation,
 703                                 u64 owner, u64 owner_offset)
 704 {
 705         struct btrfs_path *path;
 706         int ret;
 707         struct btrfs_key key;
 708         struct extent_buffer *l;
 709         struct btrfs_extent_item *item;
 710         u32 refs;
 711
 712         WARN_ON(num_bytes < root->sectorsize);
 713         path = btrfs_alloc_path();
 714         if (!path)
 715                 return -ENOMEM;
 716
 717         path->reada = 1;
 718         key.objectid = bytenr;
 719         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 720         key.offset = num_bytes;
 721         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 722                                 0, 1);
 723         if (ret < 0)
 724                 return ret;
 725         if (ret != 0) {
 726                 BUG();
 727         }
 728         BUG_ON(ret != 0);
 729         l = path->nodes[0];
 730         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 731         refs = btrfs_extent_refs(l, item);
 732         btrfs_set_extent_refs(l, item, refs + 1);
 733         btrfs_mark_buffer_dirty(path->nodes[0]);
 734
 735         btrfs_release_path(root->fs_info->extent_root, path);
 736
 737         path->reada = 1;
 738         ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
 739                                           path, bytenr, root_objectid,
 740                                           ref_generation, owner, owner_offset);
 741         BUG_ON(ret);
 742         finish_current_insert(trans, root->fs_info->extent_root);
 743         del_pending_extents(trans, root->fs_info->extent_root);
 744
 745         btrfs_free_path(path);
 746         return 0;
 747 }
 748
 749 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 750                                 struct btrfs_root *root,
 751                                 u64 bytenr, u64 num_bytes,
 752                                 u64 root_objectid, u64 ref_generation,
 753                                 u64 owner, u64 owner_offset)
 754 {
 755         int ret;
 756
 757         mutex_lock(&root->fs_info->alloc_mutex);
 758         ret = __btrfs_inc_extent_ref(trans, root, bytenr, num_bytes,
 759                                      root_objectid, ref_generation,
 760                                      owner, owner_offset);
 761         mutex_unlock(&root->fs_info->alloc_mutex);
 762         return ret;
 763 }
 764
 765 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
 766                          struct btrfs_root *root)
 767 {
 768         finish_current_insert(trans, root->fs_info->extent_root);
 769         del_pending_extents(trans, root->fs_info->extent_root);
 770         return 0;
 771 }
 772
 773 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
 774                              struct btrfs_root *root, u64 bytenr,
 775                              u64 num_bytes, u32 *refs)
 776 {
 777         struct btrfs_path *path;
 778         int ret;
 779         struct btrfs_key key;
 780         struct extent_buffer *l;
 781         struct btrfs_extent_item *item;
 782
 783         WARN_ON(num_bytes < root->sectorsize);
 784         path = btrfs_alloc_path();
 785         path->reada = 1;
 786         key.objectid = bytenr;
 787         key.offset = num_bytes;
 788         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 789         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 790                                 0, 0);
 791         if (ret < 0)
 792                 goto out;
 793         if (ret != 0) {
 794                 btrfs_print_leaf(root, path->nodes[0]);
 795                 printk("failed to find block number %Lu\n", bytenr);
 796                 BUG();
 797         }
 798         l = path->nodes[0];
 799         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 800         *refs = btrfs_extent_refs(l, item);
 801 out:
 802         btrfs_free_path(path);
 803         return 0;
 804 }
 805
 806
 807 static int get_reference_status(struct btrfs_root *root, u64 bytenr,
 808                                 u64 parent_gen, u64 ref_objectid,
 809                                 u64 *min_generation, u32 *ref_count)
 810 {
 811         struct btrfs_root *extent_root = root->fs_info->extent_root;
 812         struct btrfs_path *path;
 813         struct extent_buffer *leaf;
 814         struct btrfs_extent_ref *ref_item;
 815         struct btrfs_key key;
 816         struct btrfs_key found_key;
 817         u64 root_objectid = root->root_key.objectid;
 818         u64 ref_generation;
 819         u32 nritems;
 820         int ret;
 821
 822         key.objectid = bytenr;
 823         key.offset = 0;
 824         key.type = BTRFS_EXTENT_ITEM_KEY;
 825
 826         path = btrfs_alloc_path();
 827         mutex_lock(&root->fs_info->alloc_mutex);
 828         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 829         if (ret < 0)
 830                 goto out;
 831         BUG_ON(ret == 0);
 832
 833         leaf = path->nodes[0];
 834         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 835
 836         if (found_key.objectid != bytenr ||
 837             found_key.type != BTRFS_EXTENT_ITEM_KEY) {
 838                 ret = 1;
 839                 goto out;
 840         }
 841
 842         *ref_count = 0;
 843         *min_generation = (u64)-1;
 844
 845         while (1) {
 846                 leaf = path->nodes[0];
 847                 nritems = btrfs_header_nritems(leaf);
 848                 if (path->slots[0] >= nritems) {
 849                         ret = btrfs_next_leaf(extent_root, path);
 850                         if (ret < 0)
 851                                 goto out;
 852                         if (ret == 0)
 853                                 continue;
 854                         break;
 855                 }
 856                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 857                 if (found_key.objectid != bytenr)
 858                         break;
 859
 860                 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
 861                         path->slots[0]++;
 862                         continue;
 863                 }
 864
 865                 ref_item = btrfs_item_ptr(leaf, path->slots[0],
 866                                           struct btrfs_extent_ref);
 867                 ref_generation = btrfs_ref_generation(leaf, ref_item);
 868                 /*
 869                  * For (parent_gen > 0 && parent_gen > ref_gen):
 870                  *
 871                  * we reach here through the oldest root, therefore
 872                  * all other reference from same snapshot should have
 873                  * a larger generation.
 874                  */
 875                 if ((root_objectid != btrfs_ref_root(leaf, ref_item)) ||
 876                     (parent_gen > 0 && parent_gen > ref_generation) ||
 877                     (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
 878                      ref_objectid != btrfs_ref_objectid(leaf, ref_item))) {
 879                         if (ref_count)
 880                                 *ref_count = 2;
 881                         break;
 882                 }
 883
 884                 *ref_count = 1;
 885                 if (*min_generation > ref_generation)
 886                         *min_generation = ref_generation;
 887
 888                 path->slots[0]++;
 889         }
 890         ret = 0;
 891 out:
 892         mutex_unlock(&root->fs_info->alloc_mutex);
 893         btrfs_free_path(path);
 894         return ret;
 895 }
 896
 897 int btrfs_cross_ref_exists(struct btrfs_trans_handle *trans,
 898                            struct btrfs_root *root,
 899                            struct btrfs_key *key, u64 bytenr)
 900 {
 901         struct btrfs_root *old_root;
 902         struct btrfs_path *path = NULL;
 903         struct extent_buffer *eb;
 904         struct btrfs_file_extent_item *item;
 905         u64 ref_generation;
 906         u64 min_generation;
 907         u64 extent_start;
 908         u32 ref_count;
 909         int level;
 910         int ret;
 911
 912         BUG_ON(trans == NULL);
 913         BUG_ON(key->type != BTRFS_EXTENT_DATA_KEY);
 914         ret = get_reference_status(root, bytenr, 0, key->objectid,
 915                                    &min_generation, &ref_count);
 916         if (ret)
 917                 return ret;
 918
 919         if (ref_count != 1)
 920                 return 1;
 921
 922         old_root = root->dirty_root->root;
 923         ref_generation = old_root->root_key.offset;
 924
 925         /* all references are created in running transaction */
 926         if (min_generation > ref_generation) {
 927                 ret = 0;
 928                 goto out;
 929         }
 930
 931         path = btrfs_alloc_path();
 932         if (!path) {
 933                 ret = -ENOMEM;
 934                 goto out;
 935         }
 936
 937         path->skip_locking = 1;
 938         /* if no item found, the extent is referenced by other snapshot */
 939         ret = btrfs_search_slot(NULL, old_root, key, path, 0, 0);
 940         if (ret)
 941                 goto out;
 942
 943         eb = path->nodes[0];
 944         item = btrfs_item_ptr(eb, path->slots[0],
 945                               struct btrfs_file_extent_item);
 946         if (btrfs_file_extent_type(eb, item) != BTRFS_FILE_EXTENT_REG ||
 947             btrfs_file_extent_disk_bytenr(eb, item) != bytenr) {
 948                 ret = 1;
 949                 goto out;
 950         }
 951
 952         for (level = BTRFS_MAX_LEVEL - 1; level >= -1; level--) {
 953                 if (level >= 0) {
 954                         eb = path->nodes[level];
 955                         if (!eb)
 956                                 continue;
 957                         extent_start = eb->start;
 958                 } else
 959                         extent_start = bytenr;
 960
 961                 ret = get_reference_status(root, extent_start, ref_generation,
 962                                            0, &min_generation, &ref_count);
 963                 if (ret)
 964                         goto out;
 965
 966                 if (ref_count != 1) {
 967                         ret = 1;
 968                         goto out;
 969                 }
 970                 if (level >= 0)
 971                         ref_generation = btrfs_header_generation(eb);
 972         }
 973         ret = 0;
 974 out:
 975         if (path)
 976                 btrfs_free_path(path);
 977         return ret;
 978 }
 979
 980 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 981                   struct extent_buffer *buf, int cache_ref)
 982 {
 983         u64 bytenr;
 984         u32 nritems;
 985         struct btrfs_key key;
 986         struct btrfs_file_extent_item *fi;
 987         int i;
 988         int level;
 989         int ret;
 990         int faili;
 991         int nr_file_extents = 0;
 992
 993         if (!root->ref_cows)
 994                 return 0;
 995
 996         level = btrfs_header_level(buf);
 997         nritems = btrfs_header_nritems(buf);
 998         for (i = 0; i < nritems; i++) {
 999                 cond_resched();
1000                 if (level == 0) {
1001                         u64 disk_bytenr;
1002                         btrfs_item_key_to_cpu(buf, &key, i);
1003                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1004                                 continue;
1005                         fi = btrfs_item_ptr(buf, i,
1006                                             struct btrfs_file_extent_item);
1007                         if (btrfs_file_extent_type(buf, fi) ==
1008                             BTRFS_FILE_EXTENT_INLINE)
1009                                 continue;
1010                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1011                         if (disk_bytenr == 0)
1012                                 continue;
1013
1014                         if (buf != root->commit_root)
1015                                 nr_file_extents++;
1016
1017                         mutex_lock(&root->fs_info->alloc_mutex);
1018                         ret = __btrfs_inc_extent_ref(trans, root, disk_bytenr,
1019                                     btrfs_file_extent_disk_num_bytes(buf, fi),
1020                                     root->root_key.objectid, trans->transid,
1021                                     key.objectid, key.offset);
1022                         mutex_unlock(&root->fs_info->alloc_mutex);
1023                         if (ret) {
1024                                 faili = i;
1025                                 WARN_ON(1);
1026                                 goto fail;
1027                         }
1028                 } else {
1029                         bytenr = btrfs_node_blockptr(buf, i);
1030                         btrfs_node_key_to_cpu(buf, &key, i);
1031
1032                         mutex_lock(&root->fs_info->alloc_mutex);
1033                         ret = __btrfs_inc_extent_ref(trans, root, bytenr,
1034                                            btrfs_level_size(root, level - 1),
1035                                            root->root_key.objectid,
1036                                            trans->transid,
1037                                            level - 1, key.objectid);
1038                         mutex_unlock(&root->fs_info->alloc_mutex);
1039                         if (ret) {
1040                                 faili = i;
1041                                 WARN_ON(1);
1042                                 goto fail;
1043                         }
1044                 }
1045         }
1046         /* cache orignal leaf block's references */
1047         if (level == 0 && cache_ref && buf != root->commit_root) {
1048                 struct btrfs_leaf_ref *ref;
1049                 struct btrfs_extent_info *info;
1050
1051                 ref = btrfs_alloc_leaf_ref(root, nr_file_extents);
1052                 if (!ref) {
1053                         WARN_ON(1);
1054                         goto out;
1055                 }
1056
1057                 ref->root_gen = root->root_key.offset;
1058                 ref->bytenr = buf->start;
1059                 ref->owner = btrfs_header_owner(buf);
1060                 ref->generation = btrfs_header_generation(buf);
1061                 ref->nritems = nr_file_extents;
1062                 info = ref->extents;
1063
1064                 for (i = 0; nr_file_extents > 0 && i < nritems; i++) {
1065                         u64 disk_bytenr;
1066                         btrfs_item_key_to_cpu(buf, &key, i);
1067                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1068                                 continue;
1069                         fi = btrfs_item_ptr(buf, i,
1070                                             struct btrfs_file_extent_item);
1071                         if (btrfs_file_extent_type(buf, fi) ==
1072                             BTRFS_FILE_EXTENT_INLINE)
1073                                 continue;
1074                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1075                         if (disk_bytenr == 0)
1076                                 continue;
1077
1078                         info->bytenr = disk_bytenr;
1079                         info->num_bytes =
1080                                 btrfs_file_extent_disk_num_bytes(buf, fi);
1081                         info->objectid = key.objectid;
1082                         info->offset = key.offset;
1083                         info++;
1084                 }
1085
1086                 BUG_ON(!root->ref_tree);
1087                 ret = btrfs_add_leaf_ref(root, ref);
1088                 WARN_ON(ret);
1089                 btrfs_free_leaf_ref(root, ref);
1090         }
1091 out:
1092         return 0;
1093 fail:
1094         WARN_ON(1);
1095 #if 0
1096         for (i =0; i < faili; i++) {
1097                 if (level == 0) {
1098                         u64 disk_bytenr;
1099                         btrfs_item_key_to_cpu(buf, &key, i);
1100                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1101                                 continue;
1102                         fi = btrfs_item_ptr(buf, i,
1103                                             struct btrfs_file_extent_item);
1104                         if (btrfs_file_extent_type(buf, fi) ==
1105                             BTRFS_FILE_EXTENT_INLINE)
1106                                 continue;
1107                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1108                         if (disk_bytenr == 0)
1109                                 continue;
1110                         err = btrfs_free_extent(trans, root, disk_bytenr,
1111                                     btrfs_file_extent_disk_num_bytes(buf,
1112                                                                       fi), 0);
1113                         BUG_ON(err);
1114                 } else {
1115                         bytenr = btrfs_node_blockptr(buf, i);
1116                         err = btrfs_free_extent(trans, root, bytenr,
1117                                         btrfs_level_size(root, level - 1), 0);
1118                         BUG_ON(err);
1119                 }
1120         }
1121 #endif
1122         return ret;
1123 }
1124
1125 static int write_one_cache_group(struct btrfs_trans_handle *trans,
1126                                  struct btrfs_root *root,
1127                                  struct btrfs_path *path,
1128                                  struct btrfs_block_group_cache *cache)
1129 {
1130         int ret;
1131         int pending_ret;
1132         struct btrfs_root *extent_root = root->fs_info->extent_root;
1133         unsigned long bi;
1134         struct extent_buffer *leaf;
1135
1136         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1137         if (ret < 0)
1138                 goto fail;
1139         BUG_ON(ret);
1140
1141         leaf = path->nodes[0];
1142         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
1143         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
1144         btrfs_mark_buffer_dirty(leaf);
1145         btrfs_release_path(extent_root, path);
1146 fail:
1147         finish_current_insert(trans, extent_root);
1148         pending_ret = del_pending_extents(trans, extent_root);
1149         if (ret)
1150                 return ret;
1151         if (pending_ret)
1152                 return pending_ret;
1153         return 0;
1154
1155 }
1156
1157 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
1158                                    struct btrfs_root *root)
1159 {
1160         struct extent_io_tree *block_group_cache;
1161         struct btrfs_block_group_cache *cache;
1162         int ret;
1163         int err = 0;
1164         int werr = 0;
1165         struct btrfs_path *path;
1166         u64 last = 0;
1167         u64 start;
1168         u64 end;
1169         u64 ptr;
1170
1171         block_group_cache = &root->fs_info->block_group_cache;
1172         path = btrfs_alloc_path();
1173         if (!path)
1174                 return -ENOMEM;
1175
1176         mutex_lock(&root->fs_info->alloc_mutex);
1177         while(1) {
1178                 ret = find_first_extent_bit(block_group_cache, last,
1179                                             &start, &end, BLOCK_GROUP_DIRTY);
1180                 if (ret)
1181                         break;
1182
1183                 last = end + 1;
1184                 ret = get_state_private(block_group_cache, start, &ptr);
1185                 if (ret)
1186                         break;
1187                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
1188                 err = write_one_cache_group(trans, root,
1189                                             path, cache);
1190                 /*
1191                  * if we fail to write the cache group, we want
1192                  * to keep it marked dirty in hopes that a later
1193                  * write will work
1194                  */
1195                 if (err) {
1196                         werr = err;
1197                         continue;
1198                 }
1199                 clear_extent_bits(block_group_cache, start, end,
1200                                   BLOCK_GROUP_DIRTY, GFP_NOFS);
1201         }
1202         btrfs_free_path(path);
1203         mutex_unlock(&root->fs_info->alloc_mutex);
1204         return werr;
1205 }
1206
1207 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
1208                                                   u64 flags)
1209 {
1210         struct list_head *head = &info->space_info;
1211         struct list_head *cur;
1212         struct btrfs_space_info *found;
1213         list_for_each(cur, head) {
1214                 found = list_entry(cur, struct btrfs_space_info, list);
1215                 if (found->flags == flags)
1216                         return found;
1217         }
1218         return NULL;
1219
1220 }
1221
1222 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1223                              u64 total_bytes, u64 bytes_used,
1224                              struct btrfs_space_info **space_info)
1225 {
1226         struct btrfs_space_info *found;
1227
1228         found = __find_space_info(info, flags);
1229         if (found) {
1230                 found->total_bytes += total_bytes;
1231                 found->bytes_used += bytes_used;
1232                 found->full = 0;
1233                 *space_info = found;
1234                 return 0;
1235         }
1236         found = kmalloc(sizeof(*found), GFP_NOFS);
1237         if (!found)
1238                 return -ENOMEM;
1239
1240         list_add(&found->list, &info->space_info);
1241         found->flags = flags;
1242         found->total_bytes = total_bytes;
1243         found->bytes_used = bytes_used;
1244         found->bytes_pinned = 0;
1245         found->full = 0;
1246         found->force_alloc = 0;
1247         *space_info = found;
1248         return 0;
1249 }
1250
1251 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1252 {
1253         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1254                                    BTRFS_BLOCK_GROUP_RAID1 |
1255                                    BTRFS_BLOCK_GROUP_RAID10 |
1256                                    BTRFS_BLOCK_GROUP_DUP);
1257         if (extra_flags) {
1258                 if (flags & BTRFS_BLOCK_GROUP_DATA)
1259                         fs_info->avail_data_alloc_bits |= extra_flags;
1260                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1261                         fs_info->avail_metadata_alloc_bits |= extra_flags;
1262                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1263                         fs_info->avail_system_alloc_bits |= extra_flags;
1264         }
1265 }
1266
1267 static u64 reduce_alloc_profile(struct btrfs_root *root, u64 flags)
1268 {
1269         u64 num_devices = root->fs_info->fs_devices->num_devices;
1270
1271         if (num_devices == 1)
1272                 flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
1273         if (num_devices < 4)
1274                 flags &= ~BTRFS_BLOCK_GROUP_RAID10;
1275
1276         if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
1277             (flags & (BTRFS_BLOCK_GROUP_RAID1 |
1278                       BTRFS_BLOCK_GROUP_RAID10))) {
1279                 flags &= ~BTRFS_BLOCK_GROUP_DUP;
1280         }
1281
1282         if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
1283             (flags & BTRFS_BLOCK_GROUP_RAID10)) {
1284                 flags &= ~BTRFS_BLOCK_GROUP_RAID1;
1285         }
1286
1287         if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
1288             ((flags & BTRFS_BLOCK_GROUP_RAID1) |
1289              (flags & BTRFS_BLOCK_GROUP_RAID10) |
1290              (flags & BTRFS_BLOCK_GROUP_DUP)))
1291                 flags &= ~BTRFS_BLOCK_GROUP_RAID0;
1292         return flags;
1293 }
1294
1295 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1296                           struct btrfs_root *extent_root, u64 alloc_bytes,
1297                           u64 flags, int force)
1298 {
1299         struct btrfs_space_info *space_info;
1300         u64 thresh;
1301         u64 start;
1302         u64 num_bytes;
1303         int ret;
1304
1305         flags = reduce_alloc_profile(extent_root, flags);
1306
1307         space_info = __find_space_info(extent_root->fs_info, flags);
1308         if (!space_info) {
1309                 ret = update_space_info(extent_root->fs_info, flags,
1310                                         0, 0, &space_info);
1311                 BUG_ON(ret);
1312         }
1313         BUG_ON(!space_info);
1314
1315         if (space_info->force_alloc) {
1316                 force = 1;
1317                 space_info->force_alloc = 0;
1318         }
1319         if (space_info->full)
1320                 goto out;
1321
1322         thresh = div_factor(space_info->total_bytes, 6);
1323         if (!force &&
1324            (space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
1325             thresh)
1326                 goto out;
1327
1328         mutex_lock(&extent_root->fs_info->chunk_mutex);
1329         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
1330         if (ret == -ENOSPC) {
1331 printk("space info full %Lu\n", flags);
1332                 space_info->full = 1;
1333                 goto out_unlock;
1334         }
1335         BUG_ON(ret);
1336
1337         ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1338                      BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1339         BUG_ON(ret);
1340 out_unlock:
1341         mutex_unlock(&extent_root->fs_info->chunk_mutex);
1342 out:
1343         return 0;
1344 }
1345
1346 static int update_block_group(struct btrfs_trans_handle *trans,
1347                               struct btrfs_root *root,
1348                               u64 bytenr, u64 num_bytes, int alloc,
1349                               int mark_free)
1350 {
1351         struct btrfs_block_group_cache *cache;
1352         struct btrfs_fs_info *info = root->fs_info;
1353         u64 total = num_bytes;
1354         u64 old_val;
1355         u64 byte_in_group;
1356         u64 start;
1357         u64 end;
1358
1359         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1360         while(total) {
1361                 cache = btrfs_lookup_block_group(info, bytenr);
1362                 if (!cache) {
1363                         return -1;
1364                 }
1365                 byte_in_group = bytenr - cache->key.objectid;
1366                 WARN_ON(byte_in_group > cache->key.offset);
1367                 start = cache->key.objectid;
1368                 end = start + cache->key.offset - 1;
1369                 set_extent_bits(&info->block_group_cache, start, end,
1370                                 BLOCK_GROUP_DIRTY, GFP_NOFS);
1371
1372                 spin_lock(&cache->lock);
1373                 old_val = btrfs_block_group_used(&cache->item);
1374                 num_bytes = min(total, cache->key.offset - byte_in_group);
1375                 if (alloc) {
1376                         old_val += num_bytes;
1377                         cache->space_info->bytes_used += num_bytes;
1378                         btrfs_set_block_group_used(&cache->item, old_val);
1379                         spin_unlock(&cache->lock);
1380                 } else {
1381                         old_val -= num_bytes;
1382                         cache->space_info->bytes_used -= num_bytes;
1383                         btrfs_set_block_group_used(&cache->item, old_val);
1384                         spin_unlock(&cache->lock);
1385                         if (mark_free) {
1386                                 set_extent_dirty(&info->free_space_cache,
1387                                                  bytenr, bytenr + num_bytes - 1,
1388                                                  GFP_NOFS);
1389                         }
1390                 }
1391                 total -= num_bytes;
1392                 bytenr += num_bytes;
1393         }
1394         return 0;
1395 }
1396
1397 static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
1398 {
1399         u64 start;
1400         u64 end;
1401         int ret;
1402         ret = find_first_extent_bit(&root->fs_info->block_group_cache,
1403                                     search_start, &start, &end,
1404                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
1405                                     BLOCK_GROUP_SYSTEM);
1406         if (ret)
1407                 return 0;
1408         return start;
1409 }
1410
1411
1412 static int update_pinned_extents(struct btrfs_root *root,
1413                                 u64 bytenr, u64 num, int pin)
1414 {
1415         u64 len;
1416         struct btrfs_block_group_cache *cache;
1417         struct btrfs_fs_info *fs_info = root->fs_info;
1418
1419         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1420         if (pin) {
1421                 set_extent_dirty(&fs_info->pinned_extents,
1422                                 bytenr, bytenr + num - 1, GFP_NOFS);
1423         } else {
1424                 clear_extent_dirty(&fs_info->pinned_extents,
1425                                 bytenr, bytenr + num - 1, GFP_NOFS);
1426         }
1427         while (num > 0) {
1428                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1429                 if (!cache) {
1430                         u64 first = first_logical_byte(root, bytenr);
1431                         WARN_ON(first < bytenr);
1432                         len = min(first - bytenr, num);
1433                 } else {
1434                         len = min(num, cache->key.offset -
1435                                   (bytenr - cache->key.objectid));
1436                 }
1437                 if (pin) {
1438                         if (cache) {
1439                                 spin_lock(&cache->lock);
1440                                 cache->pinned += len;
1441                                 cache->space_info->bytes_pinned += len;
1442                                 spin_unlock(&cache->lock);
1443                         }
1444                         fs_info->total_pinned += len;
1445                 } else {
1446                         if (cache) {
1447                                 spin_lock(&cache->lock);
1448                                 cache->pinned -= len;
1449                                 cache->space_info->bytes_pinned -= len;
1450                                 spin_unlock(&cache->lock);
1451                         }
1452                         fs_info->total_pinned -= len;
1453                 }
1454                 bytenr += len;
1455                 num -= len;
1456         }
1457         return 0;
1458 }
1459
1460 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
1461 {
1462         u64 last = 0;
1463         u64 start;
1464         u64 end;
1465         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
1466         int ret;
1467
1468         while(1) {
1469                 ret = find_first_extent_bit(pinned_extents, last,
1470                                             &start, &end, EXTENT_DIRTY);
1471                 if (ret)
1472                         break;
1473                 set_extent_dirty(copy, start, end, GFP_NOFS);
1474                 last = end + 1;
1475         }
1476         return 0;
1477 }
1478
1479 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1480                                struct btrfs_root *root,
1481                                struct extent_io_tree *unpin)
1482 {
1483         u64 start;
1484         u64 end;
1485         int ret;
1486         struct extent_io_tree *free_space_cache;
1487         free_space_cache = &root->fs_info->free_space_cache;
1488
1489         mutex_lock(&root->fs_info->alloc_mutex);
1490         while(1) {
1491                 ret = find_first_extent_bit(unpin, 0, &start, &end,
1492                                             EXTENT_DIRTY);
1493                 if (ret)
1494                         break;
1495                 update_pinned_extents(root, start, end + 1 - start, 0);
1496                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1497                 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1498                 if (need_resched()) {
1499                         mutex_unlock(&root->fs_info->alloc_mutex);
1500                         cond_resched();
1501                         mutex_lock(&root->fs_info->alloc_mutex);
1502                 }
1503         }
1504         mutex_unlock(&root->fs_info->alloc_mutex);
1505         return 0;
1506 }
1507
1508 static int finish_current_insert(struct btrfs_trans_handle *trans,
1509                                  struct btrfs_root *extent_root)
1510 {
1511         u64 start;
1512         u64 end;
1513         struct btrfs_fs_info *info = extent_root->fs_info;
1514         struct extent_buffer *eb;
1515         struct btrfs_path *path;
1516         struct btrfs_key ins;
1517         struct btrfs_disk_key first;
1518         struct btrfs_extent_item extent_item;
1519         int ret;
1520         int level;
1521         int err = 0;
1522
1523         WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
1524         btrfs_set_stack_extent_refs(&extent_item, 1);
1525         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1526         path = btrfs_alloc_path();
1527
1528         while(1) {
1529                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1530                                             &end, EXTENT_LOCKED);
1531                 if (ret)
1532                         break;
1533
1534                 ins.objectid = start;
1535                 ins.offset = end + 1 - start;
1536                 err = btrfs_insert_item(trans, extent_root, &ins,
1537                                         &extent_item, sizeof(extent_item));
1538                 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
1539                                   GFP_NOFS);
1540
1541                 eb = btrfs_find_tree_block(extent_root, ins.objectid,
1542                                            ins.offset);
1543
1544                 if (!btrfs_buffer_uptodate(eb, trans->transid)) {
1545                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
1546                         btrfs_read_buffer(eb, trans->transid);
1547                         mutex_lock(&extent_root->fs_info->alloc_mutex);
1548                 }
1549
1550                 btrfs_tree_lock(eb);
1551                 level = btrfs_header_level(eb);
1552                 if (level == 0) {
1553                         btrfs_item_key(eb, &first, 0);
1554                 } else {
1555                         btrfs_node_key(eb, &first, 0);
1556                 }
1557                 btrfs_tree_unlock(eb);
1558                 free_extent_buffer(eb);
1559                 /*
1560                  * the first key is just a hint, so the race we've created
1561                  * against reading it is fine
1562                  */
1563                 err = btrfs_insert_extent_backref(trans, extent_root, path,
1564                                           start, extent_root->root_key.objectid,
1565                                           0, level,
1566                                           btrfs_disk_key_objectid(&first));
1567                 BUG_ON(err);
1568                 if (need_resched()) {
1569                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
1570                         cond_resched();
1571                         mutex_lock(&extent_root->fs_info->alloc_mutex);
1572                 }
1573         }
1574         btrfs_free_path(path);
1575         return 0;
1576 }
1577
1578 static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
1579                           int pending)
1580 {
1581         int err = 0;
1582
1583         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1584         if (!pending) {
1585                 struct extent_buffer *buf;
1586                 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1587                 if (buf) {
1588                         if (btrfs_buffer_uptodate(buf, 0) &&
1589                             btrfs_try_tree_lock(buf)) {
1590                                 u64 transid =
1591                                     root->fs_info->running_transaction->transid;
1592                                 u64 header_transid =
1593                                         btrfs_header_generation(buf);
1594                                 if (header_transid == transid &&
1595                                     !btrfs_header_flag(buf,
1596                                                BTRFS_HEADER_FLAG_WRITTEN)) {
1597                                         clean_tree_block(NULL, root, buf);
1598                                         btrfs_tree_unlock(buf);
1599                                         free_extent_buffer(buf);
1600                                         return 1;
1601                                 }
1602                                 btrfs_tree_unlock(buf);
1603                         }
1604                         free_extent_buffer(buf);
1605                 }
1606                 update_pinned_extents(root, bytenr, num_bytes, 1);
1607         } else {
1608                 set_extent_bits(&root->fs_info->pending_del,
1609                                 bytenr, bytenr + num_bytes - 1,
1610                                 EXTENT_LOCKED, GFP_NOFS);
1611         }
1612         BUG_ON(err < 0);
1613         return 0;
1614 }
1615
1616 /*
1617  * remove an extent from the root, returns 0 on success
1618  */
1619 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1620                          *root, u64 bytenr, u64 num_bytes,
1621                          u64 root_objectid, u64 ref_generation,
1622                          u64 owner_objectid, u64 owner_offset, int pin,
1623                          int mark_free)
1624 {
1625         struct btrfs_path *path;
1626         struct btrfs_key key;
1627         struct btrfs_fs_info *info = root->fs_info;
1628         struct btrfs_root *extent_root = info->extent_root;
1629         struct extent_buffer *leaf;
1630         int ret;
1631         int extent_slot = 0;
1632         int found_extent = 0;
1633         int num_to_del = 1;
1634         struct btrfs_extent_item *ei;
1635         u32 refs;
1636
1637         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1638         key.objectid = bytenr;
1639         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1640         key.offset = num_bytes;
1641         path = btrfs_alloc_path();
1642         if (!path)
1643                 return -ENOMEM;
1644
1645         path->reada = 1;
1646         ret = lookup_extent_backref(trans, extent_root, path,
1647                                     bytenr, root_objectid,
1648                                     ref_generation,
1649                                     owner_objectid, owner_offset, 1);
1650         if (ret == 0) {
1651                 struct btrfs_key found_key;
1652                 extent_slot = path->slots[0];
1653                 while(extent_slot > 0) {
1654                         extent_slot--;
1655                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1656                                               extent_slot);
1657                         if (found_key.objectid != bytenr)
1658                                 break;
1659                         if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
1660                             found_key.offset == num_bytes) {
1661                                 found_extent = 1;
1662                                 break;
1663                         }
1664                         if (path->slots[0] - extent_slot > 5)
1665                                 break;
1666                 }
1667                 if (!found_extent)
1668                         ret = btrfs_del_item(trans, extent_root, path);
1669         } else {
1670                 btrfs_print_leaf(extent_root, path->nodes[0]);
1671                 WARN_ON(1);
1672                 printk("Unable to find ref byte nr %Lu root %Lu "
1673                        " gen %Lu owner %Lu offset %Lu\n", bytenr,
1674                        root_objectid, ref_generation, owner_objectid,
1675                        owner_offset);
1676         }
1677         if (!found_extent) {
1678                 btrfs_release_path(extent_root, path);
1679                 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
1680                 if (ret < 0)
1681                         return ret;
1682                 BUG_ON(ret);
1683                 extent_slot = path->slots[0];
1684         }
1685
1686         leaf = path->nodes[0];
1687         ei = btrfs_item_ptr(leaf, extent_slot,
1688                             struct btrfs_extent_item);
1689         refs = btrfs_extent_refs(leaf, ei);
1690         BUG_ON(refs == 0);
1691         refs -= 1;
1692         btrfs_set_extent_refs(leaf, ei, refs);
1693
1694         btrfs_mark_buffer_dirty(leaf);
1695
1696         if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
1697                 /* if the back ref and the extent are next to each other
1698                  * they get deleted below in one shot
1699                  */
1700                 path->slots[0] = extent_slot;
1701                 num_to_del = 2;
1702         } else if (found_extent) {
1703                 /* otherwise delete the extent back ref */
1704                 ret = btrfs_del_item(trans, extent_root, path);
1705                 BUG_ON(ret);
1706                 /* if refs are 0, we need to setup the path for deletion */
1707                 if (refs == 0) {
1708                         btrfs_release_path(extent_root, path);
1709                         ret = btrfs_search_slot(trans, extent_root, &key, path,
1710                                                 -1, 1);
1711                         if (ret < 0)
1712                                 return ret;
1713                         BUG_ON(ret);
1714                 }
1715         }
1716
1717         if (refs == 0) {
1718                 u64 super_used;
1719                 u64 root_used;
1720 #ifdef BIO_RW_DISCARD
1721                 u64 map_length = num_bytes;
1722                 struct btrfs_multi_bio *multi = NULL;
1723 #endif
1724
1725                 if (pin) {
1726                         ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1727                         if (ret > 0)
1728                                 mark_free = 1;
1729                         BUG_ON(ret < 0);
1730                 }
1731
1732                 /* block accounting for super block */
1733                 spin_lock_irq(&info->delalloc_lock);
1734                 super_used = btrfs_super_bytes_used(&info->super_copy);
1735                 btrfs_set_super_bytes_used(&info->super_copy,
1736                                            super_used - num_bytes);
1737                 spin_unlock_irq(&info->delalloc_lock);
1738
1739                 /* block accounting for root item */
1740                 root_used = btrfs_root_used(&root->root_item);
1741                 btrfs_set_root_used(&root->root_item,
1742                                            root_used - num_bytes);
1743                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
1744                                       num_to_del);
1745                 if (ret) {
1746                         return ret;
1747                 }
1748                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1749                                          mark_free);
1750                 BUG_ON(ret);
1751
1752 #ifdef BIO_RW_DISCARD
1753                 /* Tell the block device(s) that the sectors can be discarded */
1754                 ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
1755                                       bytenr, &map_length, &multi, 0);
1756                 if (!ret) {
1757                         struct btrfs_bio_stripe *stripe = multi->stripes;
1758                         int i;
1759
1760                         if (map_length > num_bytes)
1761                                 map_length = num_bytes;
1762
1763                         for (i = 0; i < multi->num_stripes; i++, stripe++) {
1764                                 blkdev_issue_discard(stripe->dev->bdev,
1765                                                      stripe->physical >> 9,
1766                                                      map_length >> 9);
1767                         }
1768                         kfree(multi);
1769                 }
1770 #endif
1771         }
1772         btrfs_free_path(path);
1773         finish_current_insert(trans, extent_root);
1774         return ret;
1775 }
1776
1777 /*
1778  * find all the blocks marked as pending in the radix tree and remove
1779  * them from the extent map
1780  */
1781 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
1782                                btrfs_root *extent_root)
1783 {
1784         int ret;
1785         int err = 0;
1786         u64 start;
1787         u64 end;
1788         struct extent_io_tree *pending_del;
1789         struct extent_io_tree *pinned_extents;
1790
1791         WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
1792         pending_del = &extent_root->fs_info->pending_del;
1793         pinned_extents = &extent_root->fs_info->pinned_extents;
1794
1795         while(1) {
1796                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
1797                                             EXTENT_LOCKED);
1798                 if (ret)
1799                         break;
1800                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
1801                                   GFP_NOFS);
1802                 if (!test_range_bit(&extent_root->fs_info->extent_ins,
1803                                     start, end, EXTENT_LOCKED, 0)) {
1804                         update_pinned_extents(extent_root, start,
1805                                               end + 1 - start, 1);
1806                         ret = __free_extent(trans, extent_root,
1807                                              start, end + 1 - start,
1808                                              extent_root->root_key.objectid,
1809                                              0, 0, 0, 0, 0);
1810                 } else {
1811                         clear_extent_bits(&extent_root->fs_info->extent_ins,
1812                                           start, end, EXTENT_LOCKED, GFP_NOFS);
1813                 }
1814                 if (ret)
1815                         err = ret;
1816
1817                 if (need_resched()) {
1818                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
1819                         cond_resched();
1820                         mutex_lock(&extent_root->fs_info->alloc_mutex);
1821                 }
1822         }
1823         return err;
1824 }
1825
1826 /*
1827  * remove an extent from the root, returns 0 on success
1828  */
1829 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
1830                                struct btrfs_root *root, u64 bytenr,
1831                                u64 num_bytes, u64 root_objectid,
1832                                u64 ref_generation, u64 owner_objectid,
1833                                u64 owner_offset, int pin)
1834 {
1835         struct btrfs_root *extent_root = root->fs_info->extent_root;
1836         int pending_ret;
1837         int ret;
1838
1839         WARN_ON(num_bytes < root->sectorsize);
1840         if (!root->ref_cows)
1841                 ref_generation = 0;
1842
1843         if (root == extent_root) {
1844                 pin_down_bytes(root, bytenr, num_bytes, 1);
1845                 return 0;
1846         }
1847         ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
1848                             ref_generation, owner_objectid, owner_offset,
1849                             pin, pin == 0);
1850
1851         finish_current_insert(trans, root->fs_info->extent_root);
1852         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1853         return ret ? ret : pending_ret;
1854 }
1855
1856 int btrfs_free_extent(struct btrfs_trans_handle *trans,
1857                       struct btrfs_root *root, u64 bytenr,
1858                       u64 num_bytes, u64 root_objectid,
1859                       u64 ref_generation, u64 owner_objectid,
1860                       u64 owner_offset, int pin)
1861 {
1862         int ret;
1863
1864         maybe_lock_mutex(root);
1865         ret = __btrfs_free_extent(trans, root, bytenr, num_bytes,
1866                                   root_objectid, ref_generation,
1867                                   owner_objectid, owner_offset, pin);
1868         maybe_unlock_mutex(root);
1869         return ret;
1870 }
1871
1872 static u64 stripe_align(struct btrfs_root *root, u64 val)
1873 {
1874         u64 mask = ((u64)root->stripesize - 1);
1875         u64 ret = (val + mask) & ~mask;
1876         return ret;
1877 }
1878
1879 /*
1880  * walks the btree of allocated extents and find a hole of a given size.
1881  * The key ins is changed to record the hole:
1882  * ins->objectid == block start
1883  * ins->flags = BTRFS_EXTENT_ITEM_KEY
1884  * ins->offset == number of blocks
1885  * Any available blocks before search_start are skipped.
1886  */
1887 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1888                                      struct btrfs_root *orig_root,
1889                                      u64 num_bytes, u64 empty_size,
1890                                      u64 search_start, u64 search_end,
1891                                      u64 hint_byte, struct btrfs_key *ins,
1892                                      u64 exclude_start, u64 exclude_nr,
1893                                      int data)
1894 {
1895         int ret;
1896         u64 orig_search_start;
1897         struct btrfs_root * root = orig_root->fs_info->extent_root;
1898         struct btrfs_fs_info *info = root->fs_info;
1899         u64 total_needed = num_bytes;
1900         u64 *last_ptr = NULL;
1901         struct btrfs_block_group_cache *block_group;
1902         int full_scan = 0;
1903         int wrapped = 0;
1904         int chunk_alloc_done = 0;
1905         int empty_cluster = 2 * 1024 * 1024;
1906         int allowed_chunk_alloc = 0;
1907
1908         WARN_ON(num_bytes < root->sectorsize);
1909         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1910
1911         if (orig_root->ref_cows || empty_size)
1912                 allowed_chunk_alloc = 1;
1913
1914         if (data & BTRFS_BLOCK_GROUP_METADATA) {
1915                 last_ptr = &root->fs_info->last_alloc;
1916                 empty_cluster = 256 * 1024;
1917         }
1918
1919         if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
1920                 last_ptr = &root->fs_info->last_data_alloc;
1921         }
1922
1923         if (last_ptr) {
1924                 if (*last_ptr)
1925                         hint_byte = *last_ptr;
1926                 else {
1927                         empty_size += empty_cluster;
1928                 }
1929         }
1930
1931         search_start = max(search_start, first_logical_byte(root, 0));
1932         orig_search_start = search_start;
1933
1934         if (search_end == (u64)-1)
1935                 search_end = btrfs_super_total_bytes(&info->super_copy);
1936
1937         if (hint_byte) {
1938                 block_group = btrfs_lookup_first_block_group(info, hint_byte);
1939                 if (!block_group)
1940                         hint_byte = search_start;
1941                 block_group = btrfs_find_block_group(root, block_group,
1942                                                      hint_byte, data, 1);
1943                 if (last_ptr && *last_ptr == 0 && block_group)
1944                         hint_byte = block_group->key.objectid;
1945         } else {
1946                 block_group = btrfs_find_block_group(root,
1947                                                      trans->block_group,
1948                                                      search_start, data, 1);
1949         }
1950         search_start = max(search_start, hint_byte);
1951
1952         total_needed += empty_size;
1953
1954 check_failed:
1955         if (!block_group) {
1956                 block_group = btrfs_lookup_first_block_group(info,
1957                                                              search_start);
1958                 if (!block_group)
1959                         block_group = btrfs_lookup_first_block_group(info,
1960                                                        orig_search_start);
1961         }
1962         if (full_scan && !chunk_alloc_done) {
1963                 if (allowed_chunk_alloc) {
1964                         do_chunk_alloc(trans, root,
1965                                      num_bytes + 2 * 1024 * 1024, data, 1);
1966                         allowed_chunk_alloc = 0;
1967                 } else if (block_group && block_group_bits(block_group, data)) {
1968                         block_group->space_info->force_alloc = 1;
1969                 }
1970                 chunk_alloc_done = 1;
1971         }
1972         ret = find_search_start(root, &block_group, &search_start,
1973                                 total_needed, data);
1974         if (ret == -ENOSPC && last_ptr && *last_ptr) {
1975                 *last_ptr = 0;
1976                 block_group = btrfs_lookup_first_block_group(info,
1977                                                              orig_search_start);
1978                 search_start = orig_search_start;
1979                 ret = find_search_start(root, &block_group, &search_start,
1980                                         total_needed, data);
1981         }
1982         if (ret == -ENOSPC)
1983                 goto enospc;
1984         if (ret)
1985                 goto error;
1986
1987         if (last_ptr && *last_ptr && search_start != *last_ptr) {
1988                 *last_ptr = 0;
1989                 if (!empty_size) {
1990                         empty_size += empty_cluster;
1991                         total_needed += empty_size;
1992                 }
1993                 block_group = btrfs_lookup_first_block_group(info,
1994                                                        orig_search_start);
1995                 search_start = orig_search_start;
1996                 ret = find_search_start(root, &block_group,
1997                                         &search_start, total_needed, data);
1998                 if (ret == -ENOSPC)
1999                         goto enospc;
2000                 if (ret)
2001                         goto error;
2002         }
2003
2004         search_start = stripe_align(root, search_start);
2005         ins->objectid = search_start;
2006         ins->offset = num_bytes;
2007
2008         if (ins->objectid + num_bytes >= search_end)
2009                 goto enospc;
2010
2011         if (ins->objectid + num_bytes >
2012             block_group->key.objectid + block_group->key.offset) {
2013                 search_start = block_group->key.objectid +
2014                         block_group->key.offset;
2015                 goto new_group;
2016         }
2017
2018         if (test_range_bit(&info->extent_ins, ins->objectid,
2019                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
2020                 search_start = ins->objectid + num_bytes;
2021                 goto new_group;
2022         }
2023
2024         if (test_range_bit(&info->pinned_extents, ins->objectid,
2025                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
2026                 search_start = ins->objectid + num_bytes;
2027                 goto new_group;
2028         }
2029
2030         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
2031             ins->objectid < exclude_start + exclude_nr)) {
2032                 search_start = exclude_start + exclude_nr;
2033                 goto new_group;
2034         }
2035
2036         if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
2037                 block_group = btrfs_lookup_block_group(info, ins->objectid);
2038                 if (block_group)
2039                         trans->block_group = block_group;
2040         }
2041         ins->offset = num_bytes;
2042         if (last_ptr) {
2043                 *last_ptr = ins->objectid + ins->offset;
2044                 if (*last_ptr ==
2045                     btrfs_super_total_bytes(&root->fs_info->super_copy)) {
2046                         *last_ptr = 0;
2047                 }
2048         }
2049         return 0;
2050
2051 new_group:
2052         if (search_start + num_bytes >= search_end) {
2053 enospc:
2054                 search_start = orig_search_start;
2055                 if (full_scan) {
2056                         ret = -ENOSPC;
2057                         goto error;
2058                 }
2059                 if (wrapped) {
2060                         if (!full_scan)
2061                                 total_needed -= empty_size;
2062                         full_scan = 1;
2063                 } else
2064                         wrapped = 1;
2065         }
2066         block_group = btrfs_lookup_first_block_group(info, search_start);
2067         cond_resched();
2068         block_group = btrfs_find_block_group(root, block_group,
2069                                              search_start, data, 0);
2070         goto check_failed;
2071
2072 error:
2073         return ret;
2074 }
2075
2076 static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2077                                   struct btrfs_root *root,
2078                                   u64 num_bytes, u64 min_alloc_size,
2079                                   u64 empty_size, u64 hint_byte,
2080                                   u64 search_end, struct btrfs_key *ins,
2081                                   u64 data)
2082 {
2083         int ret;
2084         u64 search_start = 0;
2085         u64 alloc_profile;
2086         struct btrfs_fs_info *info = root->fs_info;
2087
2088         if (data) {
2089                 alloc_profile = info->avail_data_alloc_bits &
2090                                 info->data_alloc_profile;
2091                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2092         } else if (root == root->fs_info->chunk_root) {
2093                 alloc_profile = info->avail_system_alloc_bits &
2094                                 info->system_alloc_profile;
2095                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2096         } else {
2097                 alloc_profile = info->avail_metadata_alloc_bits &
2098                                 info->metadata_alloc_profile;
2099                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2100         }
2101 again:
2102         data = reduce_alloc_profile(root, data);
2103         /*
2104          * the only place that sets empty_size is btrfs_realloc_node, which
2105          * is not called recursively on allocations
2106          */
2107         if (empty_size || root->ref_cows) {
2108                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2109                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2110                                      2 * 1024 * 1024,
2111                                      BTRFS_BLOCK_GROUP_METADATA |
2112                                      (info->metadata_alloc_profile &
2113                                       info->avail_metadata_alloc_bits), 0);
2114                         BUG_ON(ret);
2115                 }
2116                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2117                                      num_bytes + 2 * 1024 * 1024, data, 0);
2118                 BUG_ON(ret);
2119         }
2120
2121         WARN_ON(num_bytes < root->sectorsize);
2122         ret = find_free_extent(trans, root, num_bytes, empty_size,
2123                                search_start, search_end, hint_byte, ins,
2124                                trans->alloc_exclude_start,
2125                                trans->alloc_exclude_nr, data);
2126
2127         if (ret == -ENOSPC && num_bytes > min_alloc_size) {
2128                 num_bytes = num_bytes >> 1;
2129                 num_bytes = max(num_bytes, min_alloc_size);
2130                 do_chunk_alloc(trans, root->fs_info->extent_root,
2131                                num_bytes, data, 1);
2132                 goto again;
2133         }
2134         if (ret) {
2135                 printk("allocation failed flags %Lu\n", data);
2136                 BUG();
2137         }
2138         clear_extent_dirty(&root->fs_info->free_space_cache,
2139                            ins->objectid, ins->objectid + ins->offset - 1,
2140                            GFP_NOFS);
2141         return 0;
2142 }
2143
2144 int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
2145 {
2146         maybe_lock_mutex(root);
2147         set_extent_dirty(&root->fs_info->free_space_cache,
2148                          start, start + len - 1, GFP_NOFS);
2149         maybe_unlock_mutex(root);
2150         return 0;
2151 }
2152
2153 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2154                                   struct btrfs_root *root,
2155                                   u64 num_bytes, u64 min_alloc_size,
2156                                   u64 empty_size, u64 hint_byte,
2157                                   u64 search_end, struct btrfs_key *ins,
2158                                   u64 data)
2159 {
2160         int ret;
2161         maybe_lock_mutex(root);
2162         ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
2163                                      empty_size, hint_byte, search_end, ins,
2164                                      data);
2165         maybe_unlock_mutex(root);
2166         return ret;
2167 }
2168
2169 static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
2170                                          struct btrfs_root *root,
2171                                          u64 root_objectid, u64 ref_generation,
2172                                          u64 owner, u64 owner_offset,
2173                                          struct btrfs_key *ins)
2174 {
2175         int ret;
2176         int pending_ret;
2177         u64 super_used;
2178         u64 root_used;
2179         u64 num_bytes = ins->offset;
2180         u32 sizes[2];
2181         struct btrfs_fs_info *info = root->fs_info;
2182         struct btrfs_root *extent_root = info->extent_root;
2183         struct btrfs_extent_item *extent_item;
2184         struct btrfs_extent_ref *ref;
2185         struct btrfs_path *path;
2186         struct btrfs_key keys[2];
2187
2188         /* block accounting for super block */
2189         spin_lock_irq(&info->delalloc_lock);
2190         super_used = btrfs_super_bytes_used(&info->super_copy);
2191         btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
2192         spin_unlock_irq(&info->delalloc_lock);
2193
2194         /* block accounting for root item */
2195         root_used = btrfs_root_used(&root->root_item);
2196         btrfs_set_root_used(&root->root_item, root_used + num_bytes);
2197
2198         if (root == extent_root) {
2199                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
2200                                 ins->objectid + ins->offset - 1,
2201                                 EXTENT_LOCKED, GFP_NOFS);
2202                 goto update_block;
2203         }
2204
2205         memcpy(&keys[0], ins, sizeof(*ins));
2206         keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
2207                                          owner, owner_offset);
2208         keys[1].objectid = ins->objectid;
2209         keys[1].type = BTRFS_EXTENT_REF_KEY;
2210         sizes[0] = sizeof(*extent_item);
2211         sizes[1] = sizeof(*ref);
2212
2213         path = btrfs_alloc_path();
2214         BUG_ON(!path);
2215
2216         ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
2217                                        sizes, 2);
2218
2219         BUG_ON(ret);
2220         extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2221                                      struct btrfs_extent_item);
2222         btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
2223         ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
2224                              struct btrfs_extent_ref);
2225
2226         btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
2227         btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
2228         btrfs_set_ref_objectid(path->nodes[0], ref, owner);
2229         btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
2230
2231         btrfs_mark_buffer_dirty(path->nodes[0]);
2232
2233         trans->alloc_exclude_start = 0;
2234         trans->alloc_exclude_nr = 0;
2235         btrfs_free_path(path);
2236         finish_current_insert(trans, extent_root);
2237         pending_ret = del_pending_extents(trans, extent_root);
2238
2239         if (ret)
2240                 goto out;
2241         if (pending_ret) {
2242                 ret = pending_ret;
2243                 goto out;
2244         }
2245
2246 update_block:
2247         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
2248         if (ret) {
2249                 printk("update block group failed for %Lu %Lu\n",
2250                        ins->objectid, ins->offset);
2251                 BUG();
2252         }
2253 out:
2254         return ret;
2255 }
2256
2257 int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
2258                                 struct btrfs_root *root,
2259                                 u64 root_objectid, u64 ref_generation,
2260                                 u64 owner, u64 owner_offset,
2261                                 struct btrfs_key *ins)
2262 {
2263         int ret;
2264         maybe_lock_mutex(root);
2265         ret = __btrfs_alloc_reserved_extent(trans, root, root_objectid,
2266                                             ref_generation, owner,
2267                                             owner_offset, ins);
2268         maybe_unlock_mutex(root);
2269         return ret;
2270 }
2271 /*
2272  * finds a free extent and does all the dirty work required for allocation
2273  * returns the key for the extent through ins, and a tree buffer for
2274  * the first block of the extent through buf.
2275  *
2276  * returns 0 if everything worked, non-zero otherwise.
2277  */
2278 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
2279                        struct btrfs_root *root,
2280                        u64 num_bytes, u64 min_alloc_size,
2281                        u64 root_objectid, u64 ref_generation,
2282                        u64 owner, u64 owner_offset,
2283                        u64 empty_size, u64 hint_byte,
2284                        u64 search_end, struct btrfs_key *ins, u64 data)
2285 {
2286         int ret;
2287
2288         maybe_lock_mutex(root);
2289
2290         ret = __btrfs_reserve_extent(trans, root, num_bytes,
2291                                      min_alloc_size, empty_size, hint_byte,
2292                                      search_end, ins, data);
2293         BUG_ON(ret);
2294         ret = __btrfs_alloc_reserved_extent(trans, root, root_objectid,
2295                                             ref_generation, owner,
2296                                             owner_offset, ins);
2297         BUG_ON(ret);
2298
2299         maybe_unlock_mutex(root);
2300         return ret;
2301 }
2302
2303 struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
2304                                             struct btrfs_root *root,
2305                                             u64 bytenr, u32 blocksize)
2306 {
2307         struct extent_buffer *buf;
2308
2309         buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
2310         if (!buf)
2311                 return ERR_PTR(-ENOMEM);
2312         btrfs_set_header_generation(buf, trans->transid);
2313         btrfs_tree_lock(buf);
2314         clean_tree_block(trans, root, buf);
2315         btrfs_set_buffer_uptodate(buf);
2316         set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
2317                          buf->start + buf->len - 1, GFP_NOFS);
2318         trans->blocks_used++;
2319         return buf;
2320 }
2321
2322 /*
2323  * helper function to allocate a block for a given tree
2324  * returns the tree buffer or NULL.
2325  */
2326 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2327                                              struct btrfs_root *root,
2328                                              u32 blocksize,
2329                                              u64 root_objectid,
2330                                              u64 ref_generation,
2331                                              u64 first_objectid,
2332                                              int level,
2333                                              u64 hint,
2334                                              u64 empty_size)
2335 {
2336         struct btrfs_key ins;
2337         int ret;
2338         struct extent_buffer *buf;
2339
2340         ret = btrfs_alloc_extent(trans, root, blocksize, blocksize,
2341                                  root_objectid, ref_generation,
2342                                  level, first_objectid, empty_size, hint,
2343                                  (u64)-1, &ins, 0);
2344         if (ret) {
2345                 BUG_ON(ret > 0);
2346                 return ERR_PTR(ret);
2347         }
2348
2349         buf = btrfs_init_new_buffer(trans, root, ins.objectid, blocksize);
2350         return buf;
2351 }
2352
2353 static int noinline drop_leaf_ref_no_cache(struct btrfs_trans_handle *trans,
2354                                            struct btrfs_root *root,
2355                                            struct extent_buffer *leaf)
2356 {
2357         u64 leaf_owner;
2358         u64 leaf_generation;
2359         struct btrfs_key key;
2360         struct btrfs_file_extent_item *fi;
2361         int i;
2362         int nritems;
2363         int ret;
2364
2365         BUG_ON(!btrfs_is_leaf(leaf));
2366         nritems = btrfs_header_nritems(leaf);
2367         leaf_owner = btrfs_header_owner(leaf);
2368         leaf_generation = btrfs_header_generation(leaf);
2369
2370         for (i = 0; i < nritems; i++) {
2371                 u64 disk_bytenr;
2372                 cond_resched();
2373
2374                 btrfs_item_key_to_cpu(leaf, &key, i);
2375                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2376                         continue;
2377                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2378                 if (btrfs_file_extent_type(leaf, fi) ==
2379                     BTRFS_FILE_EXTENT_INLINE)
2380                         continue;
2381                 /*
2382                  * FIXME make sure to insert a trans record that
2383                  * repeats the snapshot del on crash
2384                  */
2385                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
2386                 if (disk_bytenr == 0)
2387                         continue;
2388
2389                 mutex_lock(&root->fs_info->alloc_mutex);
2390                 ret = __btrfs_free_extent(trans, root, disk_bytenr,
2391                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
2392                                 leaf_owner, leaf_generation,
2393                                 key.objectid, key.offset, 0);
2394                 mutex_unlock(&root->fs_info->alloc_mutex);
2395
2396                 atomic_inc(&root->fs_info->throttle_gen);
2397                 wake_up(&root->fs_info->transaction_throttle);
2398                 cond_resched();
2399
2400                 BUG_ON(ret);
2401         }
2402         return 0;
2403 }
2404
2405 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
2406                                          struct btrfs_root *root,
2407                                          struct btrfs_leaf_ref *ref)
2408 {
2409         int i;
2410         int ret;
2411         struct btrfs_extent_info *info = ref->extents;
2412
2413         for (i = 0; i < ref->nritems; i++) {
2414                 mutex_lock(&root->fs_info->alloc_mutex);
2415                 ret = __btrfs_free_extent(trans, root,
2416                                         info->bytenr, info->num_bytes,
2417                                         ref->owner, ref->generation,
2418                                         info->objectid, info->offset, 0);
2419                 mutex_unlock(&root->fs_info->alloc_mutex);
2420
2421                 atomic_inc(&root->fs_info->throttle_gen);
2422                 wake_up(&root->fs_info->transaction_throttle);
2423                 cond_resched();
2424
2425                 BUG_ON(ret);
2426                 info++;
2427         }
2428
2429         return 0;
2430 }
2431
2432 int drop_snap_lookup_refcount(struct btrfs_root *root, u64 start, u64 len,
2433                               u32 *refs)
2434 {
2435         int ret;
2436
2437         ret = lookup_extent_ref(NULL, root, start, len, refs);
2438         BUG_ON(ret);
2439
2440 #if 0 // some debugging code in case we see problems here
2441         /* if the refs count is one, it won't get increased again.  But
2442          * if the ref count is > 1, someone may be decreasing it at
2443          * the same time we are.
2444          */
2445         if (*refs != 1) {
2446                 struct extent_buffer *eb = NULL;
2447                 eb = btrfs_find_create_tree_block(root, start, len);
2448                 if (eb)
2449                         btrfs_tree_lock(eb);
2450
2451                 mutex_lock(&root->fs_info->alloc_mutex);
2452                 ret = lookup_extent_ref(NULL, root, start, len, refs);
2453                 BUG_ON(ret);
2454                 mutex_unlock(&root->fs_info->alloc_mutex);
2455
2456                 if (eb) {
2457                         btrfs_tree_unlock(eb);
2458                         free_extent_buffer(eb);
2459                 }
2460                 if (*refs == 1) {
2461                         printk("block %llu went down to one during drop_snap\n",
2462                                (unsigned long long)start);
2463                 }
2464
2465         }
2466 #endif
2467
2468         cond_resched();
2469         return ret;
2470 }
2471
2472 /*
2473  * helper function for drop_snapshot, this walks down the tree dropping ref
2474  * counts as it goes.
2475  */
2476 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2477                                    struct btrfs_root *root,
2478                                    struct btrfs_path *path, int *level)
2479 {
2480         u64 root_owner;
2481         u64 root_gen;
2482         u64 bytenr;
2483         u64 ptr_gen;
2484         struct extent_buffer *next;
2485         struct extent_buffer *cur;
2486         struct extent_buffer *parent;
2487         struct btrfs_leaf_ref *ref;
2488         u32 blocksize;
2489         int ret;
2490         u32 refs;
2491
2492         WARN_ON(*level < 0);
2493         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2494         ret = drop_snap_lookup_refcount(root, path->nodes[*level]->start,
2495                                 path->nodes[*level]->len, &refs);
2496         BUG_ON(ret);
2497         if (refs > 1)
2498                 goto out;
2499
2500         /*
2501          * walk down to the last node level and free all the leaves
2502          */
2503         while(*level >= 0) {
2504                 WARN_ON(*level < 0);
2505                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2506                 cur = path->nodes[*level];
2507
2508                 if (btrfs_header_level(cur) != *level)
2509                         WARN_ON(1);
2510
2511                 if (path->slots[*level] >=
2512                     btrfs_header_nritems(cur))
2513                         break;
2514                 if (*level == 0) {
2515                         ret = drop_leaf_ref_no_cache(trans, root, cur);
2516                         BUG_ON(ret);
2517                         break;
2518                 }
2519                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2520                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2521                 blocksize = btrfs_level_size(root, *level - 1);
2522
2523                 ret = drop_snap_lookup_refcount(root, bytenr, blocksize, &refs);
2524                 BUG_ON(ret);
2525                 if (refs != 1) {
2526                         parent = path->nodes[*level];
2527                         root_owner = btrfs_header_owner(parent);
2528                         root_gen = btrfs_header_generation(parent);
2529                         path->slots[*level]++;
2530
2531                         mutex_lock(&root->fs_info->alloc_mutex);
2532                         ret = __btrfs_free_extent(trans, root, bytenr,
2533                                                 blocksize, root_owner,
2534                                                 root_gen, 0, 0, 1);
2535                         BUG_ON(ret);
2536                         mutex_unlock(&root->fs_info->alloc_mutex);
2537
2538                         atomic_inc(&root->fs_info->throttle_gen);
2539                         wake_up(&root->fs_info->transaction_throttle);
2540                         cond_resched();
2541
2542                         continue;
2543                 }
2544                 /*
2545                  * at this point, we have a single ref, and since the
2546                  * only place referencing this extent is a dead root
2547                  * the reference count should never go higher.
2548                  * So, we don't need to check it again
2549                  */
2550                 if (*level == 1) {
2551                         struct btrfs_key key;
2552                         btrfs_node_key_to_cpu(cur, &key, path->slots[*level]);
2553                         ref = btrfs_lookup_leaf_ref(root, bytenr);
2554                         if (ref) {
2555                                 ret = drop_leaf_ref(trans, root, ref);
2556                                 BUG_ON(ret);
2557                                 btrfs_remove_leaf_ref(root, ref);
2558                                 btrfs_free_leaf_ref(root, ref);
2559                                 *level = 0;
2560                                 break;
2561                         }
2562                         if (printk_ratelimit())
2563                                 printk("leaf ref miss for bytenr %llu\n",
2564                                        (unsigned long long)bytenr);
2565                 }
2566                 next = btrfs_find_tree_block(root, bytenr, blocksize);
2567                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
2568                         free_extent_buffer(next);
2569
2570                         next = read_tree_block(root, bytenr, blocksize,
2571                                                ptr_gen);
2572                         cond_resched();
2573 #if 0
2574                         /*
2575                          * this is a debugging check and can go away
2576                          * the ref should never go all the way down to 1
2577                          * at this point
2578                          */
2579                         ret = lookup_extent_ref(NULL, root, bytenr, blocksize,
2580                                                 &refs);
2581                         BUG_ON(ret);
2582                         WARN_ON(refs != 1);
2583 #endif
2584                 }
2585                 WARN_ON(*level <= 0);
2586                 if (path->nodes[*level-1])
2587                         free_extent_buffer(path->nodes[*level-1]);
2588                 path->nodes[*level-1] = next;
2589                 *level = btrfs_header_level(next);
2590                 path->slots[*level] = 0;
2591                 cond_resched();
2592         }
2593 out:
2594         WARN_ON(*level < 0);
2595         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2596
2597         if (path->nodes[*level] == root->node) {
2598                 parent = path->nodes[*level];
2599                 bytenr = path->nodes[*level]->start;
2600         } else {
2601                 parent = path->nodes[*level + 1];
2602                 bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
2603         }
2604
2605         blocksize = btrfs_level_size(root, *level);
2606         root_owner = btrfs_header_owner(parent);
2607         root_gen = btrfs_header_generation(parent);
2608
2609         mutex_lock(&root->fs_info->alloc_mutex);
2610         ret = __btrfs_free_extent(trans, root, bytenr, blocksize,
2611                                   root_owner, root_gen, 0, 0, 1);
2612         free_extent_buffer(path->nodes[*level]);
2613         path->nodes[*level] = NULL;
2614         *level += 1;
2615         BUG_ON(ret);
2616         mutex_unlock(&root->fs_info->alloc_mutex);
2617
2618         cond_resched();
2619         return 0;
2620 }
2621
2622 /*
2623  * helper for dropping snapshots.  This walks back up the tree in the path
2624  * to find the first node higher up where we haven't yet gone through
2625  * all the slots
2626  */
2627 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
2628                                  struct btrfs_root *root,
2629                                  struct btrfs_path *path, int *level)
2630 {
2631         u64 root_owner;
2632         u64 root_gen;
2633         struct btrfs_root_item *root_item = &root->root_item;
2634         int i;
2635         int slot;
2636         int ret;
2637
2638         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2639                 slot = path->slots[i];
2640                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
2641                         struct extent_buffer *node;
2642                         struct btrfs_disk_key disk_key;
2643                         node = path->nodes[i];
2644                         path->slots[i]++;
2645                         *level = i;
2646                         WARN_ON(*level == 0);
2647                         btrfs_node_key(node, &disk_key, path->slots[i]);
2648                         memcpy(&root_item->drop_progress,
2649                                &disk_key, sizeof(disk_key));
2650                         root_item->drop_level = i;
2651                         return 0;
2652                 } else {
2653                         if (path->nodes[*level] == root->node) {
2654                                 root_owner = root->root_key.objectid;
2655                                 root_gen =
2656                                    btrfs_header_generation(path->nodes[*level]);
2657                         } else {
2658                                 struct extent_buffer *node;
2659                                 node = path->nodes[*level + 1];
2660                                 root_owner = btrfs_header_owner(node);
2661                                 root_gen = btrfs_header_generation(node);
2662                         }
2663                         ret = btrfs_free_extent(trans, root,
2664                                                 path->nodes[*level]->start,
2665                                                 path->nodes[*level]->len,
2666                                                 root_owner, root_gen, 0, 0, 1);
2667                         BUG_ON(ret);
2668                         free_extent_buffer(path->nodes[*level]);
2669                         path->nodes[*level] = NULL;
2670                         *level = i + 1;
2671                 }
2672         }
2673         return 1;
2674 }
2675
2676 /*
2677  * drop the reference count on the tree rooted at 'snap'.  This traverses
2678  * the tree freeing any blocks that have a ref count of zero after being
2679  * decremented.
2680  */
2681 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2682                         *root)
2683 {
2684         int ret = 0;
2685         int wret;
2686         int level;
2687         struct btrfs_path *path;
2688         int i;
2689         int orig_level;
2690         struct btrfs_root_item *root_item = &root->root_item;
2691
2692         WARN_ON(!mutex_is_locked(&root->fs_info->drop_mutex));
2693         path = btrfs_alloc_path();
2694         BUG_ON(!path);
2695
2696         level = btrfs_header_level(root->node);
2697         orig_level = level;
2698         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2699                 path->nodes[level] = root->node;
2700                 extent_buffer_get(root->node);
2701                 path->slots[level] = 0;
2702         } else {
2703                 struct btrfs_key key;
2704                 struct btrfs_disk_key found_key;
2705                 struct extent_buffer *node;
2706
2707                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2708                 level = root_item->drop_level;
2709                 path->lowest_level = level;
2710                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2711                 if (wret < 0) {
2712                         ret = wret;
2713                         goto out;
2714                 }
2715                 node = path->nodes[level];
2716                 btrfs_node_key(node, &found_key, path->slots[level]);
2717                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2718                                sizeof(found_key)));
2719                 /*
2720                  * unlock our path, this is safe because only this
2721                  * function is allowed to delete this snapshot
2722                  */
2723                 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
2724                         if (path->nodes[i] && path->locks[i]) {
2725                                 path->locks[i] = 0;
2726                                 btrfs_tree_unlock(path->nodes[i]);
2727                         }
2728                 }
2729         }
2730         while(1) {
2731                 wret = walk_down_tree(trans, root, path, &level);
2732                 if (wret > 0)
2733                         break;
2734                 if (wret < 0)
2735                         ret = wret;
2736
2737                 wret = walk_up_tree(trans, root, path, &level);
2738                 if (wret > 0)
2739                         break;
2740                 if (wret < 0)
2741                         ret = wret;
2742                 if (trans->transaction->in_commit) {
2743                         ret = -EAGAIN;
2744                         break;
2745                 }
2746                 atomic_inc(&root->fs_info->throttle_gen);
2747                 wake_up(&root->fs_info->transaction_throttle);
2748         }
2749         for (i = 0; i <= orig_level; i++) {
2750                 if (path->nodes[i]) {
2751                         free_extent_buffer(path->nodes[i]);
2752                         path->nodes[i] = NULL;
2753                 }
2754         }
2755 out:
2756         btrfs_free_path(path);
2757         return ret;
2758 }
2759
2760 int btrfs_free_block_groups(struct btrfs_fs_info *info)
2761 {
2762         u64 start;
2763         u64 end;
2764         u64 ptr;
2765         int ret;
2766
2767         mutex_lock(&info->alloc_mutex);
2768         while(1) {
2769                 ret = find_first_extent_bit(&info->block_group_cache, 0,
2770                                             &start, &end, (unsigned int)-1);
2771                 if (ret)
2772                         break;
2773                 ret = get_state_private(&info->block_group_cache, start, &ptr);
2774                 if (!ret)
2775                         kfree((void *)(unsigned long)ptr);
2776                 clear_extent_bits(&info->block_group_cache, start,
2777                                   end, (unsigned int)-1, GFP_NOFS);
2778         }
2779         while(1) {
2780                 ret = find_first_extent_bit(&info->free_space_cache, 0,
2781                                             &start, &end, EXTENT_DIRTY);
2782                 if (ret)
2783                         break;
2784                 clear_extent_dirty(&info->free_space_cache, start,
2785                                    end, GFP_NOFS);
2786         }
2787         mutex_unlock(&info->alloc_mutex);
2788         return 0;
2789 }
2790
2791 static unsigned long calc_ra(unsigned long start, unsigned long last,
2792                              unsigned long nr)
2793 {
2794         return min(last, start + nr - 1);
2795 }
2796
2797 static int noinline relocate_inode_pages(struct inode *inode, u64 start,
2798                                          u64 len)
2799 {
2800         u64 page_start;
2801         u64 page_end;
2802         unsigned long last_index;
2803         unsigned long i;
2804         struct page *page;
2805         struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
2806         struct file_ra_state *ra;
2807         unsigned long total_read = 0;
2808         unsigned long ra_pages;
2809         struct btrfs_ordered_extent *ordered;
2810         struct btrfs_trans_handle *trans;
2811
2812         ra = kzalloc(sizeof(*ra), GFP_NOFS);
2813
2814         mutex_lock(&inode->i_mutex);
2815         i = start >> PAGE_CACHE_SHIFT;
2816         last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
2817
2818         ra_pages = BTRFS_I(inode)->root->fs_info->bdi.ra_pages;
2819
2820         file_ra_state_init(ra, inode->i_mapping);
2821
2822         for (; i <= last_index; i++) {
2823                 if (total_read % ra_pages == 0) {
2824                         btrfs_force_ra(inode->i_mapping, ra, NULL, i,
2825                                        calc_ra(i, last_index, ra_pages));
2826                 }
2827                 total_read++;
2828 again:
2829                 if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
2830                         goto truncate_racing;
2831                 page = grab_cache_page(inode->i_mapping, i);
2832                 if (!page) {
2833                         goto out_unlock;
2834                 }
2835                 if (!PageUptodate(page)) {
2836                         btrfs_readpage(NULL, page);
2837                         lock_page(page);
2838                         if (!PageUptodate(page)) {
2839                                 unlock_page(page);
2840                                 page_cache_release(page);
2841                                 goto out_unlock;
2842                         }
2843                 }
2844                 wait_on_page_writeback(page);
2845
2846                 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
2847                 page_end = page_start + PAGE_CACHE_SIZE - 1;
2848                 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
2849
2850                 ordered = btrfs_lookup_ordered_extent(inode, page_start);
2851                 if (ordered) {
2852                         unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
2853                         unlock_page(page);
2854                         page_cache_release(page);
2855                         btrfs_start_ordered_extent(inode, ordered, 1);
2856                         btrfs_put_ordered_extent(ordered);
2857                         goto again;
2858                 }
2859                 set_page_extent_mapped(page);
2860
2861                 /*
2862                  * make sure page_mkwrite is called for this page if userland
2863                  * wants to change it from mmap
2864                  */
2865                 clear_page_dirty_for_io(page);
2866
2867                 btrfs_set_extent_delalloc(inode, page_start, page_end);
2868                 set_page_dirty(page);
2869
2870                 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
2871                 unlock_page(page);
2872                 page_cache_release(page);
2873         }
2874
2875 out_unlock:
2876         /* we have to start the IO in order to get the ordered extents
2877          * instantiated.  This allows the relocation to code to wait
2878          * for all the ordered extents to hit the disk.
2879          *
2880          * Otherwise, it would constantly loop over the same extents
2881          * because the old ones don't get deleted  until the IO is
2882          * started
2883          */
2884         btrfs_fdatawrite_range(inode->i_mapping, start, start + len - 1,
2885                                WB_SYNC_NONE);
2886         kfree(ra);
2887         trans = btrfs_start_transaction(BTRFS_I(inode)->root, 1);
2888         if (trans) {
2889                 btrfs_end_transaction(trans, BTRFS_I(inode)->root);
2890                 mark_inode_dirty(inode);
2891         }
2892         mutex_unlock(&inode->i_mutex);
2893         return 0;
2894
2895 truncate_racing:
2896         vmtruncate(inode, inode->i_size);
2897         balance_dirty_pages_ratelimited_nr(inode->i_mapping,
2898                                            total_read);
2899         goto out_unlock;
2900 }
2901
2902 /*
2903  * The back references tell us which tree holds a ref on a block,
2904  * but it is possible for the tree root field in the reference to
2905  * reflect the original root before a snapshot was made.  In this
2906  * case we should search through all the children of a given root
2907  * to find potential holders of references on a block.
2908  *
2909  * Instead, we do something a little less fancy and just search
2910  * all the roots for a given key/block combination.
2911  */
2912 static int find_root_for_ref(struct btrfs_root *root,
2913                              struct btrfs_path *path,
2914                              struct btrfs_key *key0,
2915                              int level,
2916                              int file_key,
2917                              struct btrfs_root **found_root,
2918                              u64 bytenr)
2919 {
2920         struct btrfs_key root_location;
2921         struct btrfs_root *cur_root = *found_root;
2922         struct btrfs_file_extent_item *file_extent;
2923         u64 root_search_start = BTRFS_FS_TREE_OBJECTID;
2924         u64 found_bytenr;
2925         int ret;
2926
2927         root_location.offset = (u64)-1;
2928         root_location.type = BTRFS_ROOT_ITEM_KEY;
2929         path->lowest_level = level;
2930         path->reada = 0;
2931         while(1) {
2932                 ret = btrfs_search_slot(NULL, cur_root, key0, path, 0, 0);
2933                 found_bytenr = 0;
2934                 if (ret == 0 && file_key) {
2935                         struct extent_buffer *leaf = path->nodes[0];
2936                         file_extent = btrfs_item_ptr(leaf, path->slots[0],
2937                                              struct btrfs_file_extent_item);
2938                         if (btrfs_file_extent_type(leaf, file_extent) ==
2939                             BTRFS_FILE_EXTENT_REG) {
2940                                 found_bytenr =
2941                                         btrfs_file_extent_disk_bytenr(leaf,
2942                                                                file_extent);
2943                        }
2944                 } else if (!file_key) {
2945                         if (path->nodes[level])
2946                                 found_bytenr = path->nodes[level]->start;
2947                 }
2948
2949                 btrfs_release_path(cur_root, path);
2950
2951                 if (found_bytenr == bytenr) {
2952                         *found_root = cur_root;
2953                         ret = 0;
2954                         goto out;
2955                 }
2956                 ret = btrfs_search_root(root->fs_info->tree_root,
2957                                         root_search_start, &root_search_start);
2958                 if (ret)
2959                         break;
2960
2961                 root_location.objectid = root_search_start;
2962                 cur_root = btrfs_read_fs_root_no_name(root->fs_info,
2963                                                       &root_location);
2964                 if (!cur_root) {
2965                         ret = 1;
2966                         break;
2967                 }
2968         }
2969 out:
2970         path->lowest_level = 0;
2971         return ret;
2972 }
2973
2974 /*
2975  * note, this releases the path
2976  */
2977 static int noinline relocate_one_reference(struct btrfs_root *extent_root,
2978                                   struct btrfs_path *path,
2979                                   struct btrfs_key *extent_key,
2980                                   u64 *last_file_objectid,
2981                                   u64 *last_file_offset,
2982                                   u64 *last_file_root,
2983                                   u64 last_extent)
2984 {
2985         struct inode *inode;
2986         struct btrfs_root *found_root;
2987         struct btrfs_key root_location;
2988         struct btrfs_key found_key;
2989         struct btrfs_extent_ref *ref;
2990         u64 ref_root;
2991         u64 ref_gen;
2992         u64 ref_objectid;
2993         u64 ref_offset;
2994         int ret;
2995         int level;
2996
2997         WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
2998
2999         ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
3000                              struct btrfs_extent_ref);
3001         ref_root = btrfs_ref_root(path->nodes[0], ref);
3002         ref_gen = btrfs_ref_generation(path->nodes[0], ref);
3003         ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
3004         ref_offset = btrfs_ref_offset(path->nodes[0], ref);
3005         btrfs_release_path(extent_root, path);
3006
3007         root_location.objectid = ref_root;
3008         if (ref_gen == 0)
3009                 root_location.offset = 0;
3010         else
3011                 root_location.offset = (u64)-1;
3012         root_location.type = BTRFS_ROOT_ITEM_KEY;
3013
3014         found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
3015                                                 &root_location);
3016         BUG_ON(!found_root);
3017         mutex_unlock(&extent_root->fs_info->alloc_mutex);
3018
3019         if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
3020                 found_key.objectid = ref_objectid;
3021                 found_key.type = BTRFS_EXTENT_DATA_KEY;
3022                 found_key.offset = ref_offset;
3023                 level = 0;
3024
3025                 if (last_extent == extent_key->objectid &&
3026                     *last_file_objectid == ref_objectid &&
3027                     *last_file_offset == ref_offset &&
3028                     *last_file_root == ref_root)
3029                         goto out;
3030
3031                 ret = find_root_for_ref(extent_root, path, &found_key,
3032                                         level, 1, &found_root,
3033                                         extent_key->objectid);
3034
3035                 if (ret)
3036                         goto out;
3037
3038                 if (last_extent == extent_key->objectid &&
3039                     *last_file_objectid == ref_objectid &&
3040                     *last_file_offset == ref_offset &&
3041                     *last_file_root == ref_root)
3042                         goto out;
3043
3044                 inode = btrfs_iget_locked(extent_root->fs_info->sb,
3045                                           ref_objectid, found_root);
3046                 if (inode->i_state & I_NEW) {
3047                         /* the inode and parent dir are two different roots */
3048                         BTRFS_I(inode)->root = found_root;
3049                         BTRFS_I(inode)->location.objectid = ref_objectid;
3050                         BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
3051                         BTRFS_I(inode)->location.offset = 0;
3052                         btrfs_read_locked_inode(inode);
3053                         unlock_new_inode(inode);
3054
3055                 }
3056                 /* this can happen if the reference is not against
3057                  * the latest version of the tree root
3058                  */
3059                 if (is_bad_inode(inode))
3060                         goto out;
3061
3062                 *last_file_objectid = inode->i_ino;
3063                 *last_file_root = found_root->root_key.objectid;
3064                 *last_file_offset = ref_offset;
3065
3066                 relocate_inode_pages(inode, ref_offset, extent_key->offset);
3067                 iput(inode);
3068         } else {
3069                 struct btrfs_trans_handle *trans;
3070                 struct extent_buffer *eb;
3071                 int needs_lock = 0;
3072
3073                 eb = read_tree_block(found_root, extent_key->objectid,
3074                                      extent_key->offset, 0);
3075                 btrfs_tree_lock(eb);
3076                 level = btrfs_header_level(eb);
3077
3078                 if (level == 0)
3079                         btrfs_item_key_to_cpu(eb, &found_key, 0);
3080                 else
3081                         btrfs_node_key_to_cpu(eb, &found_key, 0);
3082
3083                 btrfs_tree_unlock(eb);
3084                 free_extent_buffer(eb);
3085
3086                 ret = find_root_for_ref(extent_root, path, &found_key,
3087                                         level, 0, &found_root,
3088                                         extent_key->objectid);
3089
3090                 if (ret)
3091                         goto out;
3092
3093                 /*
3094                  * right here almost anything could happen to our key,
3095                  * but that's ok.  The cow below will either relocate it
3096                  * or someone else will have relocated it.  Either way,
3097                  * it is in a different spot than it was before and
3098                  * we're happy.
3099                  */
3100
3101                 trans = btrfs_start_transaction(found_root, 1);
3102
3103                 if (found_root == extent_root->fs_info->extent_root ||
3104                     found_root == extent_root->fs_info->chunk_root ||
3105                     found_root == extent_root->fs_info->dev_root) {
3106                         needs_lock = 1;
3107                         mutex_lock(&extent_root->fs_info->alloc_mutex);
3108                 }
3109
3110                 path->lowest_level = level;
3111                 path->reada = 2;
3112                 ret = btrfs_search_slot(trans, found_root, &found_key, path,
3113                                         0, 1);
3114                 path->lowest_level = 0;
3115                 btrfs_release_path(found_root, path);
3116
3117                 if (found_root == found_root->fs_info->extent_root)
3118                         btrfs_extent_post_op(trans, found_root);
3119                 if (needs_lock)
3120                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
3121
3122                 btrfs_end_transaction(trans, found_root);
3123
3124         }
3125 out:
3126         mutex_lock(&extent_root->fs_info->alloc_mutex);
3127         return 0;
3128 }
3129
3130 static int noinline del_extent_zero(struct btrfs_root *extent_root,
3131                                     struct btrfs_path *path,
3132                                     struct btrfs_key *extent_key)
3133 {
3134         int ret;
3135         struct btrfs_trans_handle *trans;
3136
3137         trans = btrfs_start_transaction(extent_root, 1);
3138         ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
3139         if (ret > 0) {
3140                 ret = -EIO;
3141                 goto out;
3142         }
3143         if (ret < 0)
3144                 goto out;
3145         ret = btrfs_del_item(trans, extent_root, path);
3146 out:
3147         btrfs_end_transaction(trans, extent_root);
3148         return ret;
3149 }
3150
3151 static int noinline relocate_one_extent(struct btrfs_root *extent_root,
3152                                         struct btrfs_path *path,
3153                                         struct btrfs_key *extent_key)
3154 {
3155         struct btrfs_key key;
3156         struct btrfs_key found_key;
3157         struct extent_buffer *leaf;
3158         u64 last_file_objectid = 0;
3159         u64 last_file_root = 0;
3160         u64 last_file_offset = (u64)-1;
3161         u64 last_extent = 0;
3162         u32 nritems;
3163         u32 item_size;
3164         int ret = 0;
3165
3166         if (extent_key->objectid == 0) {
3167                 ret = del_extent_zero(extent_root, path, extent_key);
3168                 goto out;
3169         }
3170         key.objectid = extent_key->objectid;
3171         key.type = BTRFS_EXTENT_REF_KEY;
3172         key.offset = 0;
3173
3174         while(1) {
3175                 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
3176
3177                 if (ret < 0)
3178                         goto out;
3179
3180                 ret = 0;
3181                 leaf = path->nodes[0];
3182                 nritems = btrfs_header_nritems(leaf);
3183                 if (path->slots[0] == nritems) {
3184                         ret = btrfs_next_leaf(extent_root, path);
3185                         if (ret > 0) {
3186                                 ret = 0;
3187                                 goto out;
3188                         }
3189                         if (ret < 0)
3190                                 goto out;
3191                         leaf = path->nodes[0];
3192                 }
3193
3194                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3195                 if (found_key.objectid != extent_key->objectid) {
3196                         break;
3197                 }
3198
3199                 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
3200                         break;
3201                 }
3202
3203                 key.offset = found_key.offset + 1;
3204                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3205
3206                 ret = relocate_one_reference(extent_root, path, extent_key,
3207                                              &last_file_objectid,
3208                                              &last_file_offset,
3209                                              &last_file_root, last_extent);
3210                 if (ret)
3211                         goto out;
3212                 last_extent = extent_key->objectid;
3213         }
3214         ret = 0;
3215 out:
3216         btrfs_release_path(extent_root, path);
3217         return ret;
3218 }
3219
3220 static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
3221 {
3222         u64 num_devices;
3223         u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
3224                 BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;
3225
3226         num_devices = root->fs_info->fs_devices->num_devices;
3227         if (num_devices == 1) {
3228                 stripped |= BTRFS_BLOCK_GROUP_DUP;
3229                 stripped = flags & ~stripped;
3230
3231                 /* turn raid0 into single device chunks */
3232                 if (flags & BTRFS_BLOCK_GROUP_RAID0)
3233                         return stripped;
3234
3235                 /* turn mirroring into duplication */
3236                 if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
3237                              BTRFS_BLOCK_GROUP_RAID10))
3238                         return stripped | BTRFS_BLOCK_GROUP_DUP;
3239                 return flags;
3240         } else {
3241                 /* they already had raid on here, just return */
3242                 if (flags & stripped)
3243                         return flags;
3244
3245                 stripped |= BTRFS_BLOCK_GROUP_DUP;
3246                 stripped = flags & ~stripped;
3247
3248                 /* switch duplicated blocks with raid1 */
3249                 if (flags & BTRFS_BLOCK_GROUP_DUP)
3250                         return stripped | BTRFS_BLOCK_GROUP_RAID1;
3251
3252                 /* turn single device chunks into raid0 */
3253                 return stripped | BTRFS_BLOCK_GROUP_RAID0;
3254         }
3255         return flags;
3256 }
3257
3258 int __alloc_chunk_for_shrink(struct btrfs_root *root,
3259                      struct btrfs_block_group_cache *shrink_block_group,
3260                      int force)
3261 {
3262         struct btrfs_trans_handle *trans;
3263         u64 new_alloc_flags;
3264         u64 calc;
3265
3266         spin_lock(&shrink_block_group->lock);
3267         if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
3268                 spin_unlock(&shrink_block_group->lock);
3269                 mutex_unlock(&root->fs_info->alloc_mutex);
3270
3271                 trans = btrfs_start_transaction(root, 1);
3272                 mutex_lock(&root->fs_info->alloc_mutex);
3273                 spin_lock(&shrink_block_group->lock);
3274
3275                 new_alloc_flags = update_block_group_flags(root,
3276                                                    shrink_block_group->flags);
3277                 if (new_alloc_flags != shrink_block_group->flags) {
3278                         calc =
3279                              btrfs_block_group_used(&shrink_block_group->item);
3280                 } else {
3281                         calc = shrink_block_group->key.offset;
3282                 }
3283                 spin_unlock(&shrink_block_group->lock);
3284
3285                 do_chunk_alloc(trans, root->fs_info->extent_root,
3286                                calc + 2 * 1024 * 1024, new_alloc_flags, force);
3287
3288                 mutex_unlock(&root->fs_info->alloc_mutex);
3289                 btrfs_end_transaction(trans, root);
3290                 mutex_lock(&root->fs_info->alloc_mutex);
3291         } else
3292                 spin_unlock(&shrink_block_group->lock);
3293         return 0;
3294 }
3295
3296 int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 shrink_start)
3297 {
3298         struct btrfs_trans_handle *trans;
3299         struct btrfs_root *tree_root = root->fs_info->tree_root;
3300         struct btrfs_path *path;
3301         u64 cur_byte;
3302         u64 total_found;
3303         u64 shrink_last_byte;
3304         struct btrfs_block_group_cache *shrink_block_group;
3305         struct btrfs_fs_info *info = root->fs_info;
3306         struct btrfs_key key;
3307         struct btrfs_key found_key;
3308         struct extent_buffer *leaf;
3309         u32 nritems;
3310         int ret;
3311         int progress;
3312
3313         mutex_lock(&root->fs_info->alloc_mutex);
3314         shrink_block_group = btrfs_lookup_block_group(root->fs_info,
3315                                                       shrink_start);
3316         BUG_ON(!shrink_block_group);
3317
3318         shrink_last_byte = shrink_block_group->key.objectid +
3319                 shrink_block_group->key.offset;
3320
3321         shrink_block_group->space_info->total_bytes -=
3322                 shrink_block_group->key.offset;
3323         path = btrfs_alloc_path();
3324         root = root->fs_info->extent_root;
3325         path->reada = 2;
3326
3327         printk("btrfs relocating block group %llu flags %llu\n",
3328                (unsigned long long)shrink_start,
3329                (unsigned long long)shrink_block_group->flags);
3330
3331         __alloc_chunk_for_shrink(root, shrink_block_group, 1);
3332
3333 again:
3334
3335         shrink_block_group->ro = 1;
3336
3337         total_found = 0;
3338         progress = 0;
3339         key.objectid = shrink_start;
3340         key.offset = 0;
3341         key.type = 0;
3342         cur_byte = key.objectid;
3343
3344         mutex_unlock(&root->fs_info->alloc_mutex);
3345
3346         btrfs_start_delalloc_inodes(root);
3347         btrfs_wait_ordered_extents(tree_root, 0);
3348
3349         mutex_lock(&root->fs_info->alloc_mutex);
3350
3351         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3352         if (ret < 0)
3353                 goto out;
3354
3355         ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
3356         if (ret < 0)
3357                 goto out;
3358
3359         if (ret == 0) {
3360                 leaf = path->nodes[0];
3361                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3362                 if (found_key.objectid + found_key.offset > shrink_start &&
3363                     found_key.objectid < shrink_last_byte) {
3364                         cur_byte = found_key.objectid;
3365                         key.objectid = cur_byte;
3366                 }
3367         }
3368         btrfs_release_path(root, path);
3369
3370         while(1) {
3371                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3372                 if (ret < 0)
3373                         goto out;
3374
3375 next:
3376                 leaf = path->nodes[0];
3377                 nritems = btrfs_header_nritems(leaf);
3378                 if (path->slots[0] >= nritems) {
3379                         ret = btrfs_next_leaf(root, path);
3380                         if (ret < 0)
3381                                 goto out;
3382                         if (ret == 1) {
3383                                 ret = 0;
3384                                 break;
3385                         }
3386                         leaf = path->nodes[0];
3387                         nritems = btrfs_header_nritems(leaf);
3388                 }
3389
3390                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3391
3392                 if (found_key.objectid >= shrink_last_byte)
3393                         break;
3394
3395                 if (progress && need_resched()) {
3396                         memcpy(&key, &found_key, sizeof(key));
3397                         cond_resched();
3398                         btrfs_release_path(root, path);
3399                         btrfs_search_slot(NULL, root, &key, path, 0, 0);
3400                         progress = 0;
3401                         goto next;
3402                 }
3403                 progress = 1;
3404
3405                 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
3406                     found_key.objectid + found_key.offset <= cur_byte) {
3407                         memcpy(&key, &found_key, sizeof(key));
3408                         key.offset++;
3409                         path->slots[0]++;
3410                         goto next;
3411                 }
3412
3413                 total_found++;
3414                 cur_byte = found_key.objectid + found_key.offset;
3415                 key.objectid = cur_byte;
3416                 btrfs_release_path(root, path);
3417                 ret = relocate_one_extent(root, path, &found_key);
3418                 __alloc_chunk_for_shrink(root, shrink_block_group, 0);
3419         }
3420
3421         btrfs_release_path(root, path);
3422
3423         if (total_found > 0) {
3424                 printk("btrfs relocate found %llu last extent was %llu\n",
3425                        (unsigned long long)total_found,
3426                        (unsigned long long)found_key.objectid);
3427                 mutex_unlock(&root->fs_info->alloc_mutex);
3428                 trans = btrfs_start_transaction(tree_root, 1);
3429                 btrfs_commit_transaction(trans, tree_root);
3430
3431                 btrfs_clean_old_snapshots(tree_root);
3432
3433                 btrfs_start_delalloc_inodes(root);
3434                 btrfs_wait_ordered_extents(tree_root, 0);
3435
3436                 trans = btrfs_start_transaction(tree_root, 1);
3437                 btrfs_commit_transaction(trans, tree_root);
3438                 mutex_lock(&root->fs_info->alloc_mutex);
3439                 goto again;
3440         }
3441
3442         /*
3443          * we've freed all the extents, now remove the block
3444          * group item from the tree
3445          */
3446         mutex_unlock(&root->fs_info->alloc_mutex);
3447
3448         trans = btrfs_start_transaction(root, 1);
3449
3450         mutex_lock(&root->fs_info->alloc_mutex);
3451         memcpy(&key, &shrink_block_group->key, sizeof(key));
3452
3453         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
3454         if (ret > 0)
3455                 ret = -EIO;
3456         if (ret < 0) {
3457                 btrfs_end_transaction(trans, root);
3458                 goto out;
3459         }
3460
3461         clear_extent_bits(&info->block_group_cache, key.objectid,
3462                           key.objectid + key.offset - 1,
3463                           (unsigned int)-1, GFP_NOFS);
3464
3465
3466         clear_extent_bits(&info->free_space_cache,
3467                            key.objectid, key.objectid + key.offset - 1,
3468                            (unsigned int)-1, GFP_NOFS);
3469
3470         /*
3471         memset(shrink_block_group, 0, sizeof(*shrink_block_group));
3472         kfree(shrink_block_group);
3473         */
3474
3475         btrfs_del_item(trans, root, path);
3476         btrfs_release_path(root, path);
3477         mutex_unlock(&root->fs_info->alloc_mutex);
3478         btrfs_commit_transaction(trans, root);
3479
3480         mutex_lock(&root->fs_info->alloc_mutex);
3481
3482         /* the code to unpin extents might set a few bits in the free
3483          * space cache for this range again
3484          */
3485         clear_extent_bits(&info->free_space_cache,
3486                            key.objectid, key.objectid + key.offset - 1,
3487                            (unsigned int)-1, GFP_NOFS);
3488 out:
3489         btrfs_free_path(path);
3490         mutex_unlock(&root->fs_info->alloc_mutex);
3491         return ret;
3492 }
3493
3494 int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
3495                            struct btrfs_key *key)
3496 {
3497         int ret = 0;
3498         struct btrfs_key found_key;
3499         struct extent_buffer *leaf;
3500         int slot;
3501
3502         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
3503         if (ret < 0)
3504                 goto out;
3505
3506         while(1) {
3507                 slot = path->slots[0];
3508                 leaf = path->nodes[0];
3509                 if (slot >= btrfs_header_nritems(leaf)) {
3510                         ret = btrfs_next_leaf(root, path);
3511                         if (ret == 0)
3512                                 continue;
3513                         if (ret < 0)
3514                                 goto out;
3515                         break;
3516                 }
3517                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3518
3519                 if (found_key.objectid >= key->objectid &&
3520                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
3521                         ret = 0;
3522                         goto out;
3523                 }
3524                 path->slots[0]++;
3525         }
3526         ret = -ENOENT;
3527 out:
3528         return ret;
3529 }
3530
3531 int btrfs_read_block_groups(struct btrfs_root *root)
3532 {
3533         struct btrfs_path *path;
3534         int ret;
3535         int bit;
3536         struct btrfs_block_group_cache *cache;
3537         struct btrfs_fs_info *info = root->fs_info;
3538         struct btrfs_space_info *space_info;
3539         struct extent_io_tree *block_group_cache;
3540         struct btrfs_key key;
3541         struct btrfs_key found_key;
3542         struct extent_buffer *leaf;
3543
3544         block_group_cache = &info->block_group_cache;
3545         root = info->extent_root;
3546         key.objectid = 0;
3547         key.offset = 0;
3548         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
3549         path = btrfs_alloc_path();
3550         if (!path)
3551                 return -ENOMEM;
3552
3553         mutex_lock(&root->fs_info->alloc_mutex);
3554         while(1) {
3555                 ret = find_first_block_group(root, path, &key);
3556                 if (ret > 0) {
3557                         ret = 0;
3558                         goto error;
3559                 }
3560                 if (ret != 0)
3561                         goto error;
3562
3563                 leaf = path->nodes[0];
3564                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3565                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
3566                 if (!cache) {
3567                         ret = -ENOMEM;
3568                         break;
3569                 }
3570
3571                 spin_lock_init(&cache->lock);
3572                 read_extent_buffer(leaf, &cache->item,
3573                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
3574                                    sizeof(cache->item));
3575                 memcpy(&cache->key, &found_key, sizeof(found_key));
3576
3577                 key.objectid = found_key.objectid + found_key.offset;
3578                 btrfs_release_path(root, path);
3579                 cache->flags = btrfs_block_group_flags(&cache->item);
3580                 bit = 0;
3581                 if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
3582                         bit = BLOCK_GROUP_DATA;
3583                 } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
3584                         bit = BLOCK_GROUP_SYSTEM;
3585                 } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
3586                         bit = BLOCK_GROUP_METADATA;
3587                 }
3588                 set_avail_alloc_bits(info, cache->flags);
3589
3590                 ret = update_space_info(info, cache->flags, found_key.offset,
3591                                         btrfs_block_group_used(&cache->item),
3592                                         &space_info);
3593                 BUG_ON(ret);
3594                 cache->space_info = space_info;
3595
3596                 /* use EXTENT_LOCKED to prevent merging */
3597                 set_extent_bits(block_group_cache, found_key.objectid,
3598                                 found_key.objectid + found_key.offset - 1,
3599                                 EXTENT_LOCKED, GFP_NOFS);
3600                 set_state_private(block_group_cache, found_key.objectid,
3601                                   (unsigned long)cache);
3602                 set_extent_bits(block_group_cache, found_key.objectid,
3603                                 found_key.objectid + found_key.offset - 1,
3604                                 bit | EXTENT_LOCKED, GFP_NOFS);
3605                 if (key.objectid >=
3606                     btrfs_super_total_bytes(&info->super_copy))
3607                         break;
3608         }
3609         ret = 0;
3610 error:
3611         btrfs_free_path(path);
3612         mutex_unlock(&root->fs_info->alloc_mutex);
3613         return ret;
3614 }
3615
3616 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
3617                            struct btrfs_root *root, u64 bytes_used,
3618                            u64 type, u64 chunk_objectid, u64 chunk_offset,
3619                            u64 size)
3620 {
3621         int ret;
3622         int bit = 0;
3623         struct btrfs_root *extent_root;
3624         struct btrfs_block_group_cache *cache;
3625         struct extent_io_tree *block_group_cache;
3626
3627         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
3628         extent_root = root->fs_info->extent_root;
3629         block_group_cache = &root->fs_info->block_group_cache;
3630
3631         cache = kzalloc(sizeof(*cache), GFP_NOFS);
3632         BUG_ON(!cache);
3633         cache->key.objectid = chunk_offset;
3634         cache->key.offset = size;
3635         spin_lock_init(&cache->lock);
3636         btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
3637
3638         btrfs_set_block_group_used(&cache->item, bytes_used);
3639         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
3640         cache->flags = type;
3641         btrfs_set_block_group_flags(&cache->item, type);
3642
3643         ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
3644                                 &cache->space_info);
3645         BUG_ON(ret);
3646
3647         bit = block_group_state_bits(type);
3648         set_extent_bits(block_group_cache, chunk_offset,
3649                         chunk_offset + size - 1,
3650                         EXTENT_LOCKED, GFP_NOFS);
3651         set_state_private(block_group_cache, chunk_offset,
3652                           (unsigned long)cache);
3653         set_extent_bits(block_group_cache, chunk_offset,
3654                         chunk_offset + size - 1,
3655                         bit | EXTENT_LOCKED, GFP_NOFS);
3656
3657         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
3658                                 sizeof(cache->item));
3659         BUG_ON(ret);
3660
3661         finish_current_insert(trans, extent_root);
3662         ret = del_pending_extents(trans, extent_root);
3663         BUG_ON(ret);
3664         set_avail_alloc_bits(extent_root->fs_info, type);
3665
3666         return 0;
3667 }