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