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