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