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_DUP);
1046         if (extra_flags) {
1047                 if (flags & BTRFS_BLOCK_GROUP_DATA)
1048                         fs_info->avail_data_alloc_bits |= extra_flags;
1049                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1050                         fs_info->avail_metadata_alloc_bits |= extra_flags;
1051                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1052                         fs_info->avail_system_alloc_bits |= extra_flags;
1053         }
1054 }
1055
1056 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1057                           struct btrfs_root *extent_root, u64 alloc_bytes,
1058                           u64 flags)
1059 {
1060         struct btrfs_space_info *space_info;
1061         u64 thresh;
1062         u64 start;
1063         u64 num_bytes;
1064         int ret;
1065
1066         space_info = __find_space_info(extent_root->fs_info, flags);
1067         if (!space_info) {
1068                 ret = update_space_info(extent_root->fs_info, flags,
1069                                         0, 0, &space_info);
1070                 BUG_ON(ret);
1071         }
1072         BUG_ON(!space_info);
1073
1074         if (space_info->full)
1075                 return 0;
1076
1077         thresh = div_factor(space_info->total_bytes, 6);
1078         if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
1079             thresh)
1080                 return 0;
1081
1082         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
1083         if (ret == -ENOSPC) {
1084 printk("space info full %Lu\n", flags);
1085                 space_info->full = 1;
1086                 return 0;
1087         }
1088
1089         BUG_ON(ret);
1090
1091         ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1092                      BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1093         BUG_ON(ret);
1094
1095         return 0;
1096 }
1097
1098 static int update_block_group(struct btrfs_trans_handle *trans,
1099                               struct btrfs_root *root,
1100                               u64 bytenr, u64 num_bytes, int alloc,
1101                               int mark_free)
1102 {
1103         struct btrfs_block_group_cache *cache;
1104         struct btrfs_fs_info *info = root->fs_info;
1105         u64 total = num_bytes;
1106         u64 old_val;
1107         u64 byte_in_group;
1108         u64 start;
1109         u64 end;
1110
1111         while(total) {
1112                 cache = btrfs_lookup_block_group(info, bytenr);
1113                 if (!cache) {
1114                         return -1;
1115                 }
1116                 byte_in_group = bytenr - cache->key.objectid;
1117                 WARN_ON(byte_in_group > cache->key.offset);
1118                 start = cache->key.objectid;
1119                 end = start + cache->key.offset - 1;
1120                 set_extent_bits(&info->block_group_cache, start, end,
1121                                 BLOCK_GROUP_DIRTY, GFP_NOFS);
1122
1123                 old_val = btrfs_block_group_used(&cache->item);
1124                 num_bytes = min(total, cache->key.offset - byte_in_group);
1125                 if (alloc) {
1126                         old_val += num_bytes;
1127                         cache->space_info->bytes_used += num_bytes;
1128                 } else {
1129                         old_val -= num_bytes;
1130                         cache->space_info->bytes_used -= num_bytes;
1131                         if (mark_free) {
1132                                 set_extent_dirty(&info->free_space_cache,
1133                                                  bytenr, bytenr + num_bytes - 1,
1134                                                  GFP_NOFS);
1135                         }
1136                 }
1137                 btrfs_set_block_group_used(&cache->item, old_val);
1138                 total -= num_bytes;
1139                 bytenr += num_bytes;
1140         }
1141         return 0;
1142 }
1143
1144 static int update_pinned_extents(struct btrfs_root *root,
1145                                 u64 bytenr, u64 num, int pin)
1146 {
1147         u64 len;
1148         struct btrfs_block_group_cache *cache;
1149         struct btrfs_fs_info *fs_info = root->fs_info;
1150
1151         if (pin) {
1152                 set_extent_dirty(&fs_info->pinned_extents,
1153                                 bytenr, bytenr + num - 1, GFP_NOFS);
1154         } else {
1155                 clear_extent_dirty(&fs_info->pinned_extents,
1156                                 bytenr, bytenr + num - 1, GFP_NOFS);
1157         }
1158         while (num > 0) {
1159                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1160                 WARN_ON(!cache);
1161                 len = min(num, cache->key.offset -
1162                           (bytenr - cache->key.objectid));
1163                 if (pin) {
1164                         cache->pinned += len;
1165                         cache->space_info->bytes_pinned += len;
1166                         fs_info->total_pinned += len;
1167                 } else {
1168                         cache->pinned -= len;
1169                         cache->space_info->bytes_pinned -= len;
1170                         fs_info->total_pinned -= len;
1171                 }
1172                 bytenr += len;
1173                 num -= len;
1174         }
1175         return 0;
1176 }
1177
1178 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
1179 {
1180         u64 last = 0;
1181         u64 start;
1182         u64 end;
1183         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
1184         int ret;
1185
1186         while(1) {
1187                 ret = find_first_extent_bit(pinned_extents, last,
1188                                             &start, &end, EXTENT_DIRTY);
1189                 if (ret)
1190                         break;
1191                 set_extent_dirty(copy, start, end, GFP_NOFS);
1192                 last = end + 1;
1193         }
1194         return 0;
1195 }
1196
1197 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1198                                struct btrfs_root *root,
1199                                struct extent_io_tree *unpin)
1200 {
1201         u64 start;
1202         u64 end;
1203         int ret;
1204         struct extent_io_tree *free_space_cache;
1205         free_space_cache = &root->fs_info->free_space_cache;
1206
1207         while(1) {
1208                 ret = find_first_extent_bit(unpin, 0, &start, &end,
1209                                             EXTENT_DIRTY);
1210                 if (ret)
1211                         break;
1212                 update_pinned_extents(root, start, end + 1 - start, 0);
1213                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1214                 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1215         }
1216         return 0;
1217 }
1218
1219 static int finish_current_insert(struct btrfs_trans_handle *trans,
1220                                  struct btrfs_root *extent_root)
1221 {
1222         u64 start;
1223         u64 end;
1224         struct btrfs_fs_info *info = extent_root->fs_info;
1225         struct extent_buffer *eb;
1226         struct btrfs_path *path;
1227         struct btrfs_key ins;
1228         struct btrfs_disk_key first;
1229         struct btrfs_extent_item extent_item;
1230         int ret;
1231         int level;
1232         int err = 0;
1233
1234         btrfs_set_stack_extent_refs(&extent_item, 1);
1235         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1236         path = btrfs_alloc_path();
1237
1238         while(1) {
1239                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1240                                             &end, EXTENT_LOCKED);
1241                 if (ret)
1242                         break;
1243
1244                 ins.objectid = start;
1245                 ins.offset = end + 1 - start;
1246                 err = btrfs_insert_item(trans, extent_root, &ins,
1247                                         &extent_item, sizeof(extent_item));
1248                 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
1249                                   GFP_NOFS);
1250                 eb = read_tree_block(extent_root, ins.objectid, ins.offset);
1251                 level = btrfs_header_level(eb);
1252                 if (level == 0) {
1253                         btrfs_item_key(eb, &first, 0);
1254                 } else {
1255                         btrfs_node_key(eb, &first, 0);
1256                 }
1257                 err = btrfs_insert_extent_backref(trans, extent_root, path,
1258                                           start, extent_root->root_key.objectid,
1259                                           0, level,
1260                                           btrfs_disk_key_objectid(&first));
1261                 BUG_ON(err);
1262                 free_extent_buffer(eb);
1263         }
1264         btrfs_free_path(path);
1265         return 0;
1266 }
1267
1268 static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
1269                           int pending)
1270 {
1271         int err = 0;
1272         struct extent_buffer *buf;
1273
1274         if (!pending) {
1275                 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1276                 if (buf) {
1277                         if (btrfs_buffer_uptodate(buf)) {
1278                                 u64 transid =
1279                                     root->fs_info->running_transaction->transid;
1280                                 u64 header_transid =
1281                                         btrfs_header_generation(buf);
1282                                 if (header_transid == transid &&
1283                                     !btrfs_header_flag(buf,
1284                                                BTRFS_HEADER_FLAG_WRITTEN)) {
1285                                         clean_tree_block(NULL, root, buf);
1286                                         free_extent_buffer(buf);
1287                                         return 1;
1288                                 }
1289                         }
1290                         free_extent_buffer(buf);
1291                 }
1292                 update_pinned_extents(root, bytenr, num_bytes, 1);
1293         } else {
1294                 set_extent_bits(&root->fs_info->pending_del,
1295                                 bytenr, bytenr + num_bytes - 1,
1296                                 EXTENT_LOCKED, GFP_NOFS);
1297         }
1298         BUG_ON(err < 0);
1299         return 0;
1300 }
1301
1302 /*
1303  * remove an extent from the root, returns 0 on success
1304  */
1305 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1306                          *root, u64 bytenr, u64 num_bytes,
1307                          u64 root_objectid, u64 ref_generation,
1308                          u64 owner_objectid, u64 owner_offset, int pin,
1309                          int mark_free)
1310 {
1311         struct btrfs_path *path;
1312         struct btrfs_key key;
1313         struct btrfs_fs_info *info = root->fs_info;
1314         struct btrfs_root *extent_root = info->extent_root;
1315         struct extent_buffer *leaf;
1316         int ret;
1317         int extent_slot = 0;
1318         int found_extent = 0;
1319         int num_to_del = 1;
1320         struct btrfs_extent_item *ei;
1321         u32 refs;
1322
1323         key.objectid = bytenr;
1324         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1325         key.offset = num_bytes;
1326         path = btrfs_alloc_path();
1327         if (!path)
1328                 return -ENOMEM;
1329
1330         path->reada = 0;
1331         ret = lookup_extent_backref(trans, extent_root, path,
1332                                     bytenr, root_objectid,
1333                                     ref_generation,
1334                                     owner_objectid, owner_offset, 1);
1335         if (ret == 0) {
1336                 struct btrfs_key found_key;
1337                 extent_slot = path->slots[0];
1338                 while(extent_slot > 0) {
1339                         extent_slot--;
1340                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1341                                               extent_slot);
1342                         if (found_key.objectid != bytenr)
1343                                 break;
1344                         if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
1345                             found_key.offset == num_bytes) {
1346                                 found_extent = 1;
1347                                 break;
1348                         }
1349                         if (path->slots[0] - extent_slot > 5)
1350                                 break;
1351                 }
1352                 if (!found_extent)
1353                         ret = btrfs_del_item(trans, extent_root, path);
1354         } else {
1355                 btrfs_print_leaf(extent_root, path->nodes[0]);
1356                 WARN_ON(1);
1357                 printk("Unable to find ref byte nr %Lu root %Lu "
1358                        " gen %Lu owner %Lu offset %Lu\n", bytenr,
1359                        root_objectid, ref_generation, owner_objectid,
1360                        owner_offset);
1361         }
1362         if (!found_extent) {
1363                 btrfs_release_path(extent_root, path);
1364                 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
1365                 if (ret < 0)
1366                         return ret;
1367                 BUG_ON(ret);
1368                 extent_slot = path->slots[0];
1369         }
1370
1371         leaf = path->nodes[0];
1372         ei = btrfs_item_ptr(leaf, extent_slot,
1373                             struct btrfs_extent_item);
1374         refs = btrfs_extent_refs(leaf, ei);
1375         BUG_ON(refs == 0);
1376         refs -= 1;
1377         btrfs_set_extent_refs(leaf, ei, refs);
1378
1379         btrfs_mark_buffer_dirty(leaf);
1380
1381         if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
1382                 /* if the back ref and the extent are next to each other
1383                  * they get deleted below in one shot
1384                  */
1385                 path->slots[0] = extent_slot;
1386                 num_to_del = 2;
1387         } else if (found_extent) {
1388                 /* otherwise delete the extent back ref */
1389                 ret = btrfs_del_item(trans, extent_root, path);
1390                 BUG_ON(ret);
1391                 /* if refs are 0, we need to setup the path for deletion */
1392                 if (refs == 0) {
1393                         btrfs_release_path(extent_root, path);
1394                         ret = btrfs_search_slot(trans, extent_root, &key, path,
1395                                                 -1, 1);
1396                         if (ret < 0)
1397                                 return ret;
1398                         BUG_ON(ret);
1399                 }
1400         }
1401
1402         if (refs == 0) {
1403                 u64 super_used;
1404                 u64 root_used;
1405
1406                 if (pin) {
1407                         ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1408                         if (ret > 0)
1409                                 mark_free = 1;
1410                         BUG_ON(ret < 0);
1411                 }
1412
1413                 /* block accounting for super block */
1414                 super_used = btrfs_super_bytes_used(&info->super_copy);
1415                 btrfs_set_super_bytes_used(&info->super_copy,
1416                                            super_used - num_bytes);
1417
1418                 /* block accounting for root item */
1419                 root_used = btrfs_root_used(&root->root_item);
1420                 btrfs_set_root_used(&root->root_item,
1421                                            root_used - num_bytes);
1422                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
1423                                       num_to_del);
1424                 if (ret) {
1425                         return ret;
1426                 }
1427                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1428                                          mark_free);
1429                 BUG_ON(ret);
1430         }
1431         btrfs_free_path(path);
1432         finish_current_insert(trans, extent_root);
1433         return ret;
1434 }
1435
1436 /*
1437  * find all the blocks marked as pending in the radix tree and remove
1438  * them from the extent map
1439  */
1440 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
1441                                btrfs_root *extent_root)
1442 {
1443         int ret;
1444         int err = 0;
1445         u64 start;
1446         u64 end;
1447         struct extent_io_tree *pending_del;
1448         struct extent_io_tree *pinned_extents;
1449
1450         pending_del = &extent_root->fs_info->pending_del;
1451         pinned_extents = &extent_root->fs_info->pinned_extents;
1452
1453         while(1) {
1454                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
1455                                             EXTENT_LOCKED);
1456                 if (ret)
1457                         break;
1458                 update_pinned_extents(extent_root, start, end + 1 - start, 1);
1459                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
1460                                   GFP_NOFS);
1461                 ret = __free_extent(trans, extent_root,
1462                                      start, end + 1 - start,
1463                                      extent_root->root_key.objectid,
1464                                      0, 0, 0, 0, 0);
1465                 if (ret)
1466                         err = ret;
1467         }
1468         return err;
1469 }
1470
1471 /*
1472  * remove an extent from the root, returns 0 on success
1473  */
1474 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1475                       *root, u64 bytenr, u64 num_bytes,
1476                       u64 root_objectid, u64 ref_generation,
1477                       u64 owner_objectid, u64 owner_offset, int pin)
1478 {
1479         struct btrfs_root *extent_root = root->fs_info->extent_root;
1480         int pending_ret;
1481         int ret;
1482
1483         WARN_ON(num_bytes < root->sectorsize);
1484         if (!root->ref_cows)
1485                 ref_generation = 0;
1486
1487         if (root == extent_root) {
1488                 pin_down_bytes(root, bytenr, num_bytes, 1);
1489                 return 0;
1490         }
1491         ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
1492                             ref_generation, owner_objectid, owner_offset,
1493                             pin, pin == 0);
1494         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1495         return ret ? ret : pending_ret;
1496 }
1497
1498 static u64 stripe_align(struct btrfs_root *root, u64 val)
1499 {
1500         u64 mask = ((u64)root->stripesize - 1);
1501         u64 ret = (val + mask) & ~mask;
1502         return ret;
1503 }
1504
1505 /*
1506  * walks the btree of allocated extents and find a hole of a given size.
1507  * The key ins is changed to record the hole:
1508  * ins->objectid == block start
1509  * ins->flags = BTRFS_EXTENT_ITEM_KEY
1510  * ins->offset == number of blocks
1511  * Any available blocks before search_start are skipped.
1512  */
1513 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1514                                      struct btrfs_root *orig_root,
1515                                      u64 num_bytes, u64 empty_size,
1516                                      u64 search_start, u64 search_end,
1517                                      u64 hint_byte, struct btrfs_key *ins,
1518                                      u64 exclude_start, u64 exclude_nr,
1519                                      int data)
1520 {
1521         int ret;
1522         u64 orig_search_start = search_start;
1523         struct btrfs_root * root = orig_root->fs_info->extent_root;
1524         struct btrfs_fs_info *info = root->fs_info;
1525         u64 total_needed = num_bytes;
1526         u64 *last_ptr = NULL;
1527         struct btrfs_block_group_cache *block_group;
1528         int full_scan = 0;
1529         int wrapped = 0;
1530         int empty_cluster = 2 * 1024 * 1024;
1531
1532         WARN_ON(num_bytes < root->sectorsize);
1533         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1534
1535         if (data & BTRFS_BLOCK_GROUP_METADATA) {
1536                 last_ptr = &root->fs_info->last_alloc;
1537                 empty_cluster = 256 * 1024;
1538         }
1539
1540         if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
1541                 last_ptr = &root->fs_info->last_data_alloc;
1542         }
1543
1544         if (last_ptr) {
1545                 if (*last_ptr)
1546                         hint_byte = *last_ptr;
1547                 else {
1548                         empty_size += empty_cluster;
1549                 }
1550         }
1551
1552         if (search_end == (u64)-1)
1553                 search_end = btrfs_super_total_bytes(&info->super_copy);
1554
1555         if (hint_byte) {
1556                 block_group = btrfs_lookup_block_group(info, hint_byte);
1557                 if (!block_group)
1558                         hint_byte = search_start;
1559                 block_group = btrfs_find_block_group(root, block_group,
1560                                                      hint_byte, data, 1);
1561                 if (last_ptr && *last_ptr == 0 && block_group)
1562                         hint_byte = block_group->key.objectid;
1563         } else {
1564                 block_group = btrfs_find_block_group(root,
1565                                                      trans->block_group,
1566                                                      search_start, data, 1);
1567         }
1568         search_start = max(search_start, hint_byte);
1569
1570         total_needed += empty_size;
1571
1572 check_failed:
1573         if (!block_group) {
1574                 block_group = btrfs_lookup_block_group(info, search_start);
1575                 if (!block_group)
1576                         block_group = btrfs_lookup_block_group(info,
1577                                                        orig_search_start);
1578         }
1579         ret = find_search_start(root, &block_group, &search_start,
1580                                 total_needed, data);
1581         if (ret == -ENOSPC && last_ptr && *last_ptr) {
1582                 *last_ptr = 0;
1583                 block_group = btrfs_lookup_block_group(info,
1584                                                        orig_search_start);
1585                 search_start = orig_search_start;
1586                 ret = find_search_start(root, &block_group, &search_start,
1587                                         total_needed, data);
1588         }
1589         if (ret == -ENOSPC)
1590                 goto enospc;
1591         if (ret)
1592                 goto error;
1593
1594         if (last_ptr && *last_ptr && search_start != *last_ptr) {
1595                 *last_ptr = 0;
1596                 if (!empty_size) {
1597                         empty_size += empty_cluster;
1598                         total_needed += empty_size;
1599                 }
1600                 block_group = btrfs_lookup_block_group(info,
1601                                                        orig_search_start);
1602                 search_start = orig_search_start;
1603                 ret = find_search_start(root, &block_group,
1604                                         &search_start, total_needed, data);
1605                 if (ret == -ENOSPC)
1606                         goto enospc;
1607                 if (ret)
1608                         goto error;
1609         }
1610
1611         search_start = stripe_align(root, search_start);
1612         ins->objectid = search_start;
1613         ins->offset = num_bytes;
1614
1615         if (ins->objectid + num_bytes >= search_end)
1616                 goto enospc;
1617
1618         if (ins->objectid + num_bytes >
1619             block_group->key.objectid + block_group->key.offset) {
1620                 search_start = block_group->key.objectid +
1621                         block_group->key.offset;
1622                 goto new_group;
1623         }
1624
1625         if (test_range_bit(&info->extent_ins, ins->objectid,
1626                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1627                 search_start = ins->objectid + num_bytes;
1628                 goto new_group;
1629         }
1630
1631         if (test_range_bit(&info->pinned_extents, ins->objectid,
1632                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1633                 search_start = ins->objectid + num_bytes;
1634                 goto new_group;
1635         }
1636
1637         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1638             ins->objectid < exclude_start + exclude_nr)) {
1639                 search_start = exclude_start + exclude_nr;
1640                 goto new_group;
1641         }
1642
1643         if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
1644                 block_group = btrfs_lookup_block_group(info, ins->objectid);
1645                 if (block_group)
1646                         trans->block_group = block_group;
1647         }
1648         ins->offset = num_bytes;
1649         if (last_ptr) {
1650                 *last_ptr = ins->objectid + ins->offset;
1651                 if (*last_ptr ==
1652                     btrfs_super_total_bytes(&root->fs_info->super_copy)) {
1653                         *last_ptr = 0;
1654                 }
1655         }
1656         return 0;
1657
1658 new_group:
1659         if (search_start + num_bytes >= search_end) {
1660 enospc:
1661                 search_start = orig_search_start;
1662                 if (full_scan) {
1663                         ret = -ENOSPC;
1664                         goto error;
1665                 }
1666                 if (wrapped) {
1667                         if (!full_scan)
1668                                 total_needed -= empty_size;
1669                         full_scan = 1;
1670                 } else
1671                         wrapped = 1;
1672         }
1673         block_group = btrfs_lookup_block_group(info, search_start);
1674         cond_resched();
1675         block_group = btrfs_find_block_group(root, block_group,
1676                                              search_start, data, 0);
1677         goto check_failed;
1678
1679 error:
1680         return ret;
1681 }
1682 /*
1683  * finds a free extent and does all the dirty work required for allocation
1684  * returns the key for the extent through ins, and a tree buffer for
1685  * the first block of the extent through buf.
1686  *
1687  * returns 0 if everything worked, non-zero otherwise.
1688  */
1689 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1690                        struct btrfs_root *root,
1691                        u64 num_bytes, u64 min_alloc_size,
1692                        u64 root_objectid, u64 ref_generation,
1693                        u64 owner, u64 owner_offset,
1694                        u64 empty_size, u64 hint_byte,
1695                        u64 search_end, struct btrfs_key *ins, int data)
1696 {
1697         int ret;
1698         int pending_ret;
1699         u64 super_used;
1700         u64 root_used;
1701         u64 search_start = 0;
1702         u64 new_hint;
1703         u64 alloc_profile;
1704         u32 sizes[2];
1705         struct btrfs_fs_info *info = root->fs_info;
1706         struct btrfs_root *extent_root = info->extent_root;
1707         struct btrfs_extent_item *extent_item;
1708         struct btrfs_extent_ref *ref;
1709         struct btrfs_path *path;
1710         struct btrfs_key keys[2];
1711
1712         if (data) {
1713                 alloc_profile = info->avail_data_alloc_bits &
1714                                 info->data_alloc_profile;
1715                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
1716         } else if (root == root->fs_info->chunk_root) {
1717                 alloc_profile = info->avail_system_alloc_bits &
1718                                 info->system_alloc_profile;
1719                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
1720         } else {
1721                 alloc_profile = info->avail_metadata_alloc_bits &
1722                                 info->metadata_alloc_profile;
1723                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
1724         }
1725 again:
1726         if (root->ref_cows) {
1727                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
1728                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1729                                              2 * 1024 * 1024,
1730                                              BTRFS_BLOCK_GROUP_METADATA |
1731                                              (info->metadata_alloc_profile &
1732                                               info->avail_metadata_alloc_bits));
1733                         BUG_ON(ret);
1734                 }
1735                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1736                                      num_bytes + 2 * 1024 * 1024, data);
1737                 BUG_ON(ret);
1738         }
1739
1740         new_hint = max(hint_byte, root->fs_info->alloc_start);
1741         if (new_hint < btrfs_super_total_bytes(&info->super_copy))
1742                 hint_byte = new_hint;
1743
1744         WARN_ON(num_bytes < root->sectorsize);
1745         ret = find_free_extent(trans, root, num_bytes, empty_size,
1746                                search_start, search_end, hint_byte, ins,
1747                                trans->alloc_exclude_start,
1748                                trans->alloc_exclude_nr, data);
1749         if (ret == -ENOSPC && num_bytes > min_alloc_size) {
1750                 num_bytes = num_bytes >> 1;
1751                 num_bytes = max(num_bytes, min_alloc_size);
1752                 goto again;
1753         }
1754         BUG_ON(ret);
1755         if (ret)
1756                 return ret;
1757
1758         /* block accounting for super block */
1759         super_used = btrfs_super_bytes_used(&info->super_copy);
1760         btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1761
1762         /* block accounting for root item */
1763         root_used = btrfs_root_used(&root->root_item);
1764         btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1765
1766         clear_extent_dirty(&root->fs_info->free_space_cache,
1767                            ins->objectid, ins->objectid + ins->offset - 1,
1768                            GFP_NOFS);
1769
1770         if (root == extent_root) {
1771                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1772                                 ins->objectid + ins->offset - 1,
1773                                 EXTENT_LOCKED, GFP_NOFS);
1774                 goto update_block;
1775         }
1776
1777         WARN_ON(trans->alloc_exclude_nr);
1778         trans->alloc_exclude_start = ins->objectid;
1779         trans->alloc_exclude_nr = ins->offset;
1780
1781         memcpy(&keys[0], ins, sizeof(*ins));
1782         keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
1783                                          owner, owner_offset);
1784         keys[1].objectid = ins->objectid;
1785         keys[1].type = BTRFS_EXTENT_REF_KEY;
1786         sizes[0] = sizeof(*extent_item);
1787         sizes[1] = sizeof(*ref);
1788
1789         path = btrfs_alloc_path();
1790         BUG_ON(!path);
1791
1792         ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
1793                                        sizes, 2);
1794
1795         BUG_ON(ret);
1796         extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1797                                      struct btrfs_extent_item);
1798         btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
1799         ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
1800                              struct btrfs_extent_ref);
1801
1802         btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
1803         btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
1804         btrfs_set_ref_objectid(path->nodes[0], ref, owner);
1805         btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
1806
1807         btrfs_mark_buffer_dirty(path->nodes[0]);
1808
1809         trans->alloc_exclude_start = 0;
1810         trans->alloc_exclude_nr = 0;
1811         btrfs_free_path(path);
1812         finish_current_insert(trans, extent_root);
1813         pending_ret = del_pending_extents(trans, extent_root);
1814
1815         if (ret) {
1816                 return ret;
1817         }
1818         if (pending_ret) {
1819                 return pending_ret;
1820         }
1821
1822 update_block:
1823         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
1824         if (ret) {
1825                 printk("update block group failed for %Lu %Lu\n",
1826                        ins->objectid, ins->offset);
1827                 BUG();
1828         }
1829         return 0;
1830 }
1831
1832 /*
1833  * helper function to allocate a block for a given tree
1834  * returns the tree buffer or NULL.
1835  */
1836 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1837                                              struct btrfs_root *root,
1838                                              u32 blocksize,
1839                                              u64 root_objectid, u64 hint,
1840                                              u64 empty_size)
1841 {
1842         u64 ref_generation;
1843
1844         if (root->ref_cows)
1845                 ref_generation = trans->transid;
1846         else
1847                 ref_generation = 0;
1848
1849
1850         return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
1851                                         ref_generation, 0, 0, hint, empty_size);
1852 }
1853
1854 /*
1855  * helper function to allocate a block for a given tree
1856  * returns the tree buffer or NULL.
1857  */
1858 struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1859                                              struct btrfs_root *root,
1860                                              u32 blocksize,
1861                                              u64 root_objectid,
1862                                              u64 ref_generation,
1863                                              u64 first_objectid,
1864                                              int level,
1865                                              u64 hint,
1866                                              u64 empty_size)
1867 {
1868         struct btrfs_key ins;
1869         int ret;
1870         struct extent_buffer *buf;
1871
1872         ret = btrfs_alloc_extent(trans, root, blocksize, blocksize,
1873                                  root_objectid, ref_generation,
1874                                  level, first_objectid, empty_size, hint,
1875                                  (u64)-1, &ins, 0);
1876         if (ret) {
1877                 BUG_ON(ret > 0);
1878                 return ERR_PTR(ret);
1879         }
1880         buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1881         if (!buf) {
1882                 btrfs_free_extent(trans, root, ins.objectid, blocksize,
1883                                   root->root_key.objectid, ref_generation,
1884                                   0, 0, 0);
1885                 return ERR_PTR(-ENOMEM);
1886         }
1887         btrfs_set_header_generation(buf, trans->transid);
1888         clean_tree_block(trans, root, buf);
1889         wait_on_tree_block_writeback(root, buf);
1890         btrfs_set_buffer_uptodate(buf);
1891
1892         if (PageDirty(buf->first_page)) {
1893                 printk("page %lu dirty\n", buf->first_page->index);
1894                 WARN_ON(1);
1895         }
1896
1897         set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1898                          buf->start + buf->len - 1, GFP_NOFS);
1899         if (!btrfs_test_opt(root, SSD))
1900                 btrfs_set_buffer_defrag(buf);
1901         trans->blocks_used++;
1902         return buf;
1903 }
1904
1905 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
1906                                   struct btrfs_root *root,
1907                                   struct extent_buffer *leaf)
1908 {
1909         u64 leaf_owner;
1910         u64 leaf_generation;
1911         struct btrfs_key key;
1912         struct btrfs_file_extent_item *fi;
1913         int i;
1914         int nritems;
1915         int ret;
1916
1917         BUG_ON(!btrfs_is_leaf(leaf));
1918         nritems = btrfs_header_nritems(leaf);
1919         leaf_owner = btrfs_header_owner(leaf);
1920         leaf_generation = btrfs_header_generation(leaf);
1921
1922         for (i = 0; i < nritems; i++) {
1923                 u64 disk_bytenr;
1924
1925                 btrfs_item_key_to_cpu(leaf, &key, i);
1926                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1927                         continue;
1928                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1929                 if (btrfs_file_extent_type(leaf, fi) ==
1930                     BTRFS_FILE_EXTENT_INLINE)
1931                         continue;
1932                 /*
1933                  * FIXME make sure to insert a trans record that
1934                  * repeats the snapshot del on crash
1935                  */
1936                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1937                 if (disk_bytenr == 0)
1938                         continue;
1939                 ret = btrfs_free_extent(trans, root, disk_bytenr,
1940                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
1941                                 leaf_owner, leaf_generation,
1942                                 key.objectid, key.offset, 0);
1943                 BUG_ON(ret);
1944         }
1945         return 0;
1946 }
1947
1948 static void noinline reada_walk_down(struct btrfs_root *root,
1949                                      struct extent_buffer *node,
1950                                      int slot)
1951 {
1952         u64 bytenr;
1953         u64 last = 0;
1954         u32 nritems;
1955         u32 refs;
1956         u32 blocksize;
1957         int ret;
1958         int i;
1959         int level;
1960         int skipped = 0;
1961
1962         nritems = btrfs_header_nritems(node);
1963         level = btrfs_header_level(node);
1964         if (level)
1965                 return;
1966
1967         for (i = slot; i < nritems && skipped < 32; i++) {
1968                 bytenr = btrfs_node_blockptr(node, i);
1969                 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
1970                              (last > bytenr && last - bytenr > 32 * 1024))) {
1971                         skipped++;
1972                         continue;
1973                 }
1974                 blocksize = btrfs_level_size(root, level - 1);
1975                 if (i != slot) {
1976                         ret = lookup_extent_ref(NULL, root, bytenr,
1977                                                 blocksize, &refs);
1978                         BUG_ON(ret);
1979                         if (refs != 1) {
1980                                 skipped++;
1981                                 continue;
1982                         }
1983                 }
1984                 mutex_unlock(&root->fs_info->fs_mutex);
1985                 ret = readahead_tree_block(root, bytenr, blocksize);
1986                 last = bytenr + blocksize;
1987                 cond_resched();
1988                 mutex_lock(&root->fs_info->fs_mutex);
1989                 if (ret)
1990                         break;
1991         }
1992 }
1993
1994 /*
1995  * helper function for drop_snapshot, this walks down the tree dropping ref
1996  * counts as it goes.
1997  */
1998 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
1999                                    struct btrfs_root *root,
2000                                    struct btrfs_path *path, int *level)
2001 {
2002         u64 root_owner;
2003         u64 root_gen;
2004         u64 bytenr;
2005         struct extent_buffer *next;
2006         struct extent_buffer *cur;
2007         struct extent_buffer *parent;
2008         u32 blocksize;
2009         int ret;
2010         u32 refs;
2011
2012         WARN_ON(*level < 0);
2013         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2014         ret = lookup_extent_ref(trans, root,
2015                                 path->nodes[*level]->start,
2016                                 path->nodes[*level]->len, &refs);
2017         BUG_ON(ret);
2018         if (refs > 1)
2019                 goto out;
2020
2021         /*
2022          * walk down to the last node level and free all the leaves
2023          */
2024         while(*level >= 0) {
2025                 WARN_ON(*level < 0);
2026                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2027                 cur = path->nodes[*level];
2028
2029                 if (btrfs_header_level(cur) != *level)
2030                         WARN_ON(1);
2031
2032                 if (path->slots[*level] >=
2033                     btrfs_header_nritems(cur))
2034                         break;
2035                 if (*level == 0) {
2036                         ret = drop_leaf_ref(trans, root, cur);
2037                         BUG_ON(ret);
2038                         break;
2039                 }
2040                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2041                 blocksize = btrfs_level_size(root, *level - 1);
2042                 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
2043                 BUG_ON(ret);
2044                 if (refs != 1) {
2045                         parent = path->nodes[*level];
2046                         root_owner = btrfs_header_owner(parent);
2047                         root_gen = btrfs_header_generation(parent);
2048                         path->slots[*level]++;
2049                         ret = btrfs_free_extent(trans, root, bytenr,
2050                                                 blocksize, root_owner,
2051                                                 root_gen, 0, 0, 1);
2052                         BUG_ON(ret);
2053                         continue;
2054                 }
2055                 next = btrfs_find_tree_block(root, bytenr, blocksize);
2056                 if (!next || !btrfs_buffer_uptodate(next)) {
2057                         free_extent_buffer(next);
2058                         reada_walk_down(root, cur, path->slots[*level]);
2059
2060                         mutex_unlock(&root->fs_info->fs_mutex);
2061                         next = read_tree_block(root, bytenr, blocksize);
2062                         mutex_lock(&root->fs_info->fs_mutex);
2063
2064                         /* we've dropped the lock, double check */
2065                         ret = lookup_extent_ref(trans, root, bytenr,
2066                                                 blocksize, &refs);
2067                         BUG_ON(ret);
2068                         if (refs != 1) {
2069                                 parent = path->nodes[*level];
2070                                 root_owner = btrfs_header_owner(parent);
2071                                 root_gen = btrfs_header_generation(parent);
2072
2073                                 path->slots[*level]++;
2074                                 free_extent_buffer(next);
2075                                 ret = btrfs_free_extent(trans, root, bytenr,
2076                                                         blocksize,
2077                                                         root_owner,
2078                                                         root_gen, 0, 0, 1);
2079                                 BUG_ON(ret);
2080                                 continue;
2081                         }
2082                 } else if (next) {
2083                         btrfs_verify_block_csum(root, next);
2084                 }
2085                 WARN_ON(*level <= 0);
2086                 if (path->nodes[*level-1])
2087                         free_extent_buffer(path->nodes[*level-1]);
2088                 path->nodes[*level-1] = next;
2089                 *level = btrfs_header_level(next);
2090                 path->slots[*level] = 0;
2091         }
2092 out:
2093         WARN_ON(*level < 0);
2094         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2095
2096         if (path->nodes[*level] == root->node) {
2097                 root_owner = root->root_key.objectid;
2098                 parent = path->nodes[*level];
2099         } else {
2100                 parent = path->nodes[*level + 1];
2101                 root_owner = btrfs_header_owner(parent);
2102         }
2103
2104         root_gen = btrfs_header_generation(parent);
2105         ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
2106                                 path->nodes[*level]->len,
2107                                 root_owner, root_gen, 0, 0, 1);
2108         free_extent_buffer(path->nodes[*level]);
2109         path->nodes[*level] = NULL;
2110         *level += 1;
2111         BUG_ON(ret);
2112         return 0;
2113 }
2114
2115 /*
2116  * helper for dropping snapshots.  This walks back up the tree in the path
2117  * to find the first node higher up where we haven't yet gone through
2118  * all the slots
2119  */
2120 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
2121                                  struct btrfs_root *root,
2122                                  struct btrfs_path *path, int *level)
2123 {
2124         u64 root_owner;
2125         u64 root_gen;
2126         struct btrfs_root_item *root_item = &root->root_item;
2127         int i;
2128         int slot;
2129         int ret;
2130
2131         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2132                 slot = path->slots[i];
2133                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
2134                         struct extent_buffer *node;
2135                         struct btrfs_disk_key disk_key;
2136                         node = path->nodes[i];
2137                         path->slots[i]++;
2138                         *level = i;
2139                         WARN_ON(*level == 0);
2140                         btrfs_node_key(node, &disk_key, path->slots[i]);
2141                         memcpy(&root_item->drop_progress,
2142                                &disk_key, sizeof(disk_key));
2143                         root_item->drop_level = i;
2144                         return 0;
2145                 } else {
2146                         if (path->nodes[*level] == root->node) {
2147                                 root_owner = root->root_key.objectid;
2148                                 root_gen =
2149                                    btrfs_header_generation(path->nodes[*level]);
2150                         } else {
2151                                 struct extent_buffer *node;
2152                                 node = path->nodes[*level + 1];
2153                                 root_owner = btrfs_header_owner(node);
2154                                 root_gen = btrfs_header_generation(node);
2155                         }
2156                         ret = btrfs_free_extent(trans, root,
2157                                                 path->nodes[*level]->start,
2158                                                 path->nodes[*level]->len,
2159                                                 root_owner, root_gen, 0, 0, 1);
2160                         BUG_ON(ret);
2161                         free_extent_buffer(path->nodes[*level]);
2162                         path->nodes[*level] = NULL;
2163                         *level = i + 1;
2164                 }
2165         }
2166         return 1;
2167 }
2168
2169 /*
2170  * drop the reference count on the tree rooted at 'snap'.  This traverses
2171  * the tree freeing any blocks that have a ref count of zero after being
2172  * decremented.
2173  */
2174 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2175                         *root)
2176 {
2177         int ret = 0;
2178         int wret;
2179         int level;
2180         struct btrfs_path *path;
2181         int i;
2182         int orig_level;
2183         struct btrfs_root_item *root_item = &root->root_item;
2184
2185         path = btrfs_alloc_path();
2186         BUG_ON(!path);
2187
2188         level = btrfs_header_level(root->node);
2189         orig_level = level;
2190         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2191                 path->nodes[level] = root->node;
2192                 extent_buffer_get(root->node);
2193                 path->slots[level] = 0;
2194         } else {
2195                 struct btrfs_key key;
2196                 struct btrfs_disk_key found_key;
2197                 struct extent_buffer *node;
2198
2199                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2200                 level = root_item->drop_level;
2201                 path->lowest_level = level;
2202                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2203                 if (wret < 0) {
2204                         ret = wret;
2205                         goto out;
2206                 }
2207                 node = path->nodes[level];
2208                 btrfs_node_key(node, &found_key, path->slots[level]);
2209                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2210                                sizeof(found_key)));
2211         }
2212         while(1) {
2213                 wret = walk_down_tree(trans, root, path, &level);
2214                 if (wret > 0)
2215                         break;
2216                 if (wret < 0)
2217                         ret = wret;
2218
2219                 wret = walk_up_tree(trans, root, path, &level);
2220                 if (wret > 0)
2221                         break;
2222                 if (wret < 0)
2223                         ret = wret;
2224                 ret = -EAGAIN;
2225                 break;
2226         }
2227         for (i = 0; i <= orig_level; i++) {
2228                 if (path->nodes[i]) {
2229                         free_extent_buffer(path->nodes[i]);
2230                         path->nodes[i] = NULL;
2231                 }
2232         }
2233 out:
2234         btrfs_free_path(path);
2235         return ret;
2236 }
2237
2238 int btrfs_free_block_groups(struct btrfs_fs_info *info)
2239 {
2240         u64 start;
2241         u64 end;
2242         u64 ptr;
2243         int ret;
2244         while(1) {
2245                 ret = find_first_extent_bit(&info->block_group_cache, 0,
2246                                             &start, &end, (unsigned int)-1);
2247                 if (ret)
2248                         break;
2249                 ret = get_state_private(&info->block_group_cache, start, &ptr);
2250                 if (!ret)
2251                         kfree((void *)(unsigned long)ptr);
2252                 clear_extent_bits(&info->block_group_cache, start,
2253                                   end, (unsigned int)-1, GFP_NOFS);
2254         }
2255         while(1) {
2256                 ret = find_first_extent_bit(&info->free_space_cache, 0,
2257                                             &start, &end, EXTENT_DIRTY);
2258                 if (ret)
2259                         break;
2260                 clear_extent_dirty(&info->free_space_cache, start,
2261                                    end, GFP_NOFS);
2262         }
2263         return 0;
2264 }
2265
2266 static int noinline relocate_inode_pages(struct inode *inode, u64 start,
2267                                          u64 len)
2268 {
2269         u64 page_start;
2270         u64 page_end;
2271         u64 delalloc_start;
2272         u64 existing_delalloc;
2273         unsigned long last_index;
2274         unsigned long i;
2275         struct page *page;
2276         struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
2277         struct file_ra_state *ra;
2278
2279         ra = kzalloc(sizeof(*ra), GFP_NOFS);
2280
2281         mutex_lock(&inode->i_mutex);
2282         i = start >> PAGE_CACHE_SHIFT;
2283         last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
2284
2285         file_ra_state_init(ra, inode->i_mapping);
2286         btrfs_force_ra(inode->i_mapping, ra, NULL, i, last_index);
2287         kfree(ra);
2288
2289         for (; i <= last_index; i++) {
2290                 page = grab_cache_page(inode->i_mapping, i);
2291                 if (!page)
2292                         goto out_unlock;
2293                 if (!PageUptodate(page)) {
2294                         btrfs_readpage(NULL, page);
2295                         lock_page(page);
2296                         if (!PageUptodate(page)) {
2297                                 unlock_page(page);
2298                                 page_cache_release(page);
2299                                 goto out_unlock;
2300                         }
2301                 }
2302                 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
2303                 page_end = page_start + PAGE_CACHE_SIZE - 1;
2304
2305                 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
2306
2307                 delalloc_start = page_start;
2308                 existing_delalloc = count_range_bits(io_tree,
2309                                              &delalloc_start, page_end,
2310                                              PAGE_CACHE_SIZE, EXTENT_DELALLOC);
2311
2312                 set_extent_delalloc(io_tree, page_start,
2313                                     page_end, GFP_NOFS);
2314
2315                 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
2316                 set_page_dirty(page);
2317                 unlock_page(page);
2318                 page_cache_release(page);
2319         }
2320
2321 out_unlock:
2322         mutex_unlock(&inode->i_mutex);
2323         return 0;
2324 }
2325
2326 /*
2327  * note, this releases the path
2328  */
2329 static int noinline relocate_one_reference(struct btrfs_root *extent_root,
2330                                   struct btrfs_path *path,
2331                                   struct btrfs_key *extent_key)
2332 {
2333         struct inode *inode;
2334         struct btrfs_root *found_root;
2335         struct btrfs_key *root_location;
2336         struct btrfs_extent_ref *ref;
2337         u64 ref_root;
2338         u64 ref_gen;
2339         u64 ref_objectid;
2340         u64 ref_offset;
2341         int ret;
2342
2343         ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
2344                              struct btrfs_extent_ref);
2345         ref_root = btrfs_ref_root(path->nodes[0], ref);
2346         ref_gen = btrfs_ref_generation(path->nodes[0], ref);
2347         ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
2348         ref_offset = btrfs_ref_offset(path->nodes[0], ref);
2349         btrfs_release_path(extent_root, path);
2350
2351         root_location = kmalloc(sizeof(*root_location), GFP_NOFS);
2352         root_location->objectid = ref_root;
2353         if (ref_gen == 0)
2354                 root_location->offset = 0;
2355         else
2356                 root_location->offset = (u64)-1;
2357         root_location->type = BTRFS_ROOT_ITEM_KEY;
2358
2359         found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
2360                                                 root_location);
2361         BUG_ON(!found_root);
2362         kfree(root_location);
2363
2364         if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
2365                 mutex_unlock(&extent_root->fs_info->fs_mutex);
2366                 inode = btrfs_iget_locked(extent_root->fs_info->sb,
2367                                           ref_objectid, found_root);
2368                 if (inode->i_state & I_NEW) {
2369                         /* the inode and parent dir are two different roots */
2370                         BTRFS_I(inode)->root = found_root;
2371                         BTRFS_I(inode)->location.objectid = ref_objectid;
2372                         BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
2373                         BTRFS_I(inode)->location.offset = 0;
2374                         btrfs_read_locked_inode(inode);
2375                         unlock_new_inode(inode);
2376
2377                 }
2378                 /* this can happen if the reference is not against
2379                  * the latest version of the tree root
2380                  */
2381                 if (is_bad_inode(inode)) {
2382                         mutex_lock(&extent_root->fs_info->fs_mutex);
2383                         goto out;
2384                 }
2385                 relocate_inode_pages(inode, ref_offset, extent_key->offset);
2386                 /* FIXME, data=ordered will help get rid of this */
2387                 filemap_fdatawrite(inode->i_mapping);
2388                 iput(inode);
2389                 mutex_lock(&extent_root->fs_info->fs_mutex);
2390         } else {
2391                 struct btrfs_trans_handle *trans;
2392                 struct btrfs_key found_key;
2393                 struct extent_buffer *eb;
2394                 int level;
2395                 int i;
2396
2397                 trans = btrfs_start_transaction(found_root, 1);
2398                 eb = read_tree_block(found_root, extent_key->objectid,
2399                                      extent_key->offset);
2400                 level = btrfs_header_level(eb);
2401
2402                 if (level == 0)
2403                         btrfs_item_key_to_cpu(eb, &found_key, 0);
2404                 else
2405                         btrfs_node_key_to_cpu(eb, &found_key, 0);
2406
2407                 free_extent_buffer(eb);
2408
2409                 path->lowest_level = level;
2410                 path->reada = 2;
2411                 ret = btrfs_search_slot(trans, found_root, &found_key, path,
2412                                         0, 1);
2413                 path->lowest_level = 0;
2414                 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2415                         if (!path->nodes[i])
2416                                 break;
2417                         free_extent_buffer(path->nodes[i]);
2418                         path->nodes[i] = NULL;
2419                 }
2420                 btrfs_release_path(found_root, path);
2421                 btrfs_end_transaction(trans, found_root);
2422         }
2423
2424 out:
2425         return 0;
2426 }
2427
2428 static int noinline relocate_one_extent(struct btrfs_root *extent_root,
2429                                         struct btrfs_path *path,
2430                                         struct btrfs_key *extent_key)
2431 {
2432         struct btrfs_key key;
2433         struct btrfs_key found_key;
2434         struct extent_buffer *leaf;
2435         u32 nritems;
2436         u32 item_size;
2437         int ret = 0;
2438
2439         key.objectid = extent_key->objectid;
2440         key.type = BTRFS_EXTENT_REF_KEY;
2441         key.offset = 0;
2442
2443         while(1) {
2444                 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2445
2446                 if (ret < 0)
2447                         goto out;
2448
2449                 ret = 0;
2450                 leaf = path->nodes[0];
2451                 nritems = btrfs_header_nritems(leaf);
2452                 if (path->slots[0] == nritems)
2453                         goto out;
2454
2455                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2456                 if (found_key.objectid != extent_key->objectid)
2457                         break;
2458
2459                 if (found_key.type != BTRFS_EXTENT_REF_KEY)
2460                         break;
2461
2462                 key.offset = found_key.offset + 1;
2463                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2464
2465                 ret = relocate_one_reference(extent_root, path, extent_key);
2466                 if (ret)
2467                         goto out;
2468         }
2469         ret = 0;
2470 out:
2471         btrfs_release_path(extent_root, path);
2472         return ret;
2473 }
2474
2475 int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 new_size)
2476 {
2477         struct btrfs_trans_handle *trans;
2478         struct btrfs_root *tree_root = root->fs_info->tree_root;
2479         struct btrfs_path *path;
2480         u64 cur_byte;
2481         u64 total_found;
2482         struct btrfs_fs_info *info = root->fs_info;
2483         struct extent_io_tree *block_group_cache;
2484         struct btrfs_key key;
2485         struct btrfs_key found_key;
2486         struct extent_buffer *leaf;
2487         u32 nritems;
2488         int ret;
2489         int progress = 0;
2490
2491         btrfs_set_super_total_bytes(&info->super_copy, new_size);
2492         clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
2493                            GFP_NOFS);
2494         block_group_cache = &info->block_group_cache;
2495         path = btrfs_alloc_path();
2496         root = root->fs_info->extent_root;
2497         path->reada = 2;
2498
2499 again:
2500         total_found = 0;
2501         key.objectid = new_size;
2502         key.offset = 0;
2503         key.type = 0;
2504         cur_byte = key.objectid;
2505
2506         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2507         if (ret < 0)
2508                 goto out;
2509
2510         ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
2511         if (ret < 0)
2512                 goto out;
2513         if (ret == 0) {
2514                 leaf = path->nodes[0];
2515                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2516                 if (found_key.objectid + found_key.offset > new_size) {
2517                         cur_byte = found_key.objectid;
2518                         key.objectid = cur_byte;
2519                 }
2520         }
2521         btrfs_release_path(root, path);
2522
2523         while(1) {
2524                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2525                 if (ret < 0)
2526                         goto out;
2527
2528                 leaf = path->nodes[0];
2529                 nritems = btrfs_header_nritems(leaf);
2530 next:
2531                 if (path->slots[0] >= nritems) {
2532                         ret = btrfs_next_leaf(root, path);
2533                         if (ret < 0)
2534                                 goto out;
2535                         if (ret == 1) {
2536                                 ret = 0;
2537                                 break;
2538                         }
2539                         leaf = path->nodes[0];
2540                         nritems = btrfs_header_nritems(leaf);
2541                 }
2542
2543                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2544
2545                 if (progress && need_resched()) {
2546                         memcpy(&key, &found_key, sizeof(key));
2547                         mutex_unlock(&root->fs_info->fs_mutex);
2548                         cond_resched();
2549                         mutex_lock(&root->fs_info->fs_mutex);
2550                         btrfs_release_path(root, path);
2551                         btrfs_search_slot(NULL, root, &key, path, 0, 0);
2552                         progress = 0;
2553                         goto next;
2554                 }
2555                 progress = 1;
2556
2557                 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
2558                     found_key.objectid + found_key.offset <= cur_byte) {
2559                         path->slots[0]++;
2560                         goto next;
2561                 }
2562
2563                 total_found++;
2564                 cur_byte = found_key.objectid + found_key.offset;
2565                 key.objectid = cur_byte;
2566                 btrfs_release_path(root, path);
2567                 ret = relocate_one_extent(root, path, &found_key);
2568         }
2569
2570         btrfs_release_path(root, path);
2571
2572         if (total_found > 0) {
2573                 trans = btrfs_start_transaction(tree_root, 1);
2574                 btrfs_commit_transaction(trans, tree_root);
2575
2576                 mutex_unlock(&root->fs_info->fs_mutex);
2577                 btrfs_clean_old_snapshots(tree_root);
2578                 mutex_lock(&root->fs_info->fs_mutex);
2579
2580                 trans = btrfs_start_transaction(tree_root, 1);
2581                 btrfs_commit_transaction(trans, tree_root);
2582                 goto again;
2583         }
2584
2585         trans = btrfs_start_transaction(root, 1);
2586         key.objectid = new_size;
2587         key.offset = 0;
2588         key.type = 0;
2589         while(1) {
2590                 u64 ptr;
2591
2592                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
2593                 if (ret < 0)
2594                         goto out;
2595
2596                 leaf = path->nodes[0];
2597                 nritems = btrfs_header_nritems(leaf);
2598 bg_next:
2599                 if (path->slots[0] >= nritems) {
2600                         ret = btrfs_next_leaf(root, path);
2601                         if (ret < 0)
2602                                 break;
2603                         if (ret == 1) {
2604                                 ret = 0;
2605                                 break;
2606                         }
2607                         leaf = path->nodes[0];
2608                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2609
2610                         /*
2611                          * btrfs_next_leaf doesn't cow buffers, we have to
2612                          * do the search again
2613                          */
2614                         memcpy(&key, &found_key, sizeof(key));
2615                         btrfs_release_path(root, path);
2616                         goto resched_check;
2617                 }
2618
2619                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2620                 if (btrfs_key_type(&found_key) != BTRFS_BLOCK_GROUP_ITEM_KEY) {
2621                         printk("shrinker found key %Lu %u %Lu\n",
2622                                 found_key.objectid, found_key.type,
2623                                 found_key.offset);
2624                         path->slots[0]++;
2625                         goto bg_next;
2626                 }
2627                 ret = get_state_private(&info->block_group_cache,
2628                                         found_key.objectid, &ptr);
2629                 if (!ret)
2630                         kfree((void *)(unsigned long)ptr);
2631
2632                 clear_extent_bits(&info->block_group_cache, found_key.objectid,
2633                                   found_key.objectid + found_key.offset - 1,
2634                                   (unsigned int)-1, GFP_NOFS);
2635
2636                 key.objectid = found_key.objectid + 1;
2637                 btrfs_del_item(trans, root, path);
2638                 btrfs_release_path(root, path);
2639 resched_check:
2640                 if (need_resched()) {
2641                         mutex_unlock(&root->fs_info->fs_mutex);
2642                         cond_resched();
2643                         mutex_lock(&root->fs_info->fs_mutex);
2644                 }
2645         }
2646         clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
2647                            GFP_NOFS);
2648         btrfs_commit_transaction(trans, root);
2649 out:
2650         btrfs_free_path(path);
2651         return ret;
2652 }
2653
2654 int btrfs_grow_extent_tree(struct btrfs_trans_handle *trans,
2655                            struct btrfs_root *root, u64 new_size)
2656 {
2657         btrfs_set_super_total_bytes(&root->fs_info->super_copy, new_size);
2658         return 0;
2659 }
2660
2661 int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
2662                            struct btrfs_key *key)
2663 {
2664         int ret;
2665         struct btrfs_key found_key;
2666         struct extent_buffer *leaf;
2667         int slot;
2668
2669         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
2670         if (ret < 0)
2671                 return ret;
2672         while(1) {
2673                 slot = path->slots[0];
2674                 leaf = path->nodes[0];
2675                 if (slot >= btrfs_header_nritems(leaf)) {
2676                         ret = btrfs_next_leaf(root, path);
2677                         if (ret == 0)
2678                                 continue;
2679                         if (ret < 0)
2680                                 goto error;
2681                         break;
2682                 }
2683                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
2684
2685                 if (found_key.objectid >= key->objectid &&
2686                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
2687                         return 0;
2688                 path->slots[0]++;
2689         }
2690         ret = -ENOENT;
2691 error:
2692         return ret;
2693 }
2694
2695 int btrfs_read_block_groups(struct btrfs_root *root)
2696 {
2697         struct btrfs_path *path;
2698         int ret;
2699         int bit;
2700         struct btrfs_block_group_cache *cache;
2701         struct btrfs_fs_info *info = root->fs_info;
2702         struct btrfs_space_info *space_info;
2703         struct extent_io_tree *block_group_cache;
2704         struct btrfs_key key;
2705         struct btrfs_key found_key;
2706         struct extent_buffer *leaf;
2707
2708         block_group_cache = &info->block_group_cache;
2709         root = info->extent_root;
2710         key.objectid = 0;
2711         key.offset = 0;
2712         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2713         path = btrfs_alloc_path();
2714         if (!path)
2715                 return -ENOMEM;
2716
2717         while(1) {
2718                 ret = find_first_block_group(root, path, &key);
2719                 if (ret > 0) {
2720                         ret = 0;
2721                         goto error;
2722                 }
2723                 if (ret != 0)
2724                         goto error;
2725
2726                 leaf = path->nodes[0];
2727                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2728                 cache = kmalloc(sizeof(*cache), GFP_NOFS);
2729                 if (!cache) {
2730                         ret = -ENOMEM;
2731                         break;
2732                 }
2733
2734                 read_extent_buffer(leaf, &cache->item,
2735                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
2736                                    sizeof(cache->item));
2737                 memcpy(&cache->key, &found_key, sizeof(found_key));
2738                 cache->cached = 0;
2739                 cache->pinned = 0;
2740
2741                 key.objectid = found_key.objectid + found_key.offset;
2742                 btrfs_release_path(root, path);
2743                 cache->flags = btrfs_block_group_flags(&cache->item);
2744                 bit = 0;
2745                 if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
2746                         bit = BLOCK_GROUP_DATA;
2747                 } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
2748                         bit = BLOCK_GROUP_SYSTEM;
2749                 } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
2750                         bit = BLOCK_GROUP_METADATA;
2751                 }
2752                 set_avail_alloc_bits(info, cache->flags);
2753
2754                 ret = update_space_info(info, cache->flags, found_key.offset,
2755                                         btrfs_block_group_used(&cache->item),
2756                                         &space_info);
2757                 BUG_ON(ret);
2758                 cache->space_info = space_info;
2759
2760                 /* use EXTENT_LOCKED to prevent merging */
2761                 set_extent_bits(block_group_cache, found_key.objectid,
2762                                 found_key.objectid + found_key.offset - 1,
2763                                 bit | EXTENT_LOCKED, GFP_NOFS);
2764                 set_state_private(block_group_cache, found_key.objectid,
2765                                   (unsigned long)cache);
2766
2767                 if (key.objectid >=
2768                     btrfs_super_total_bytes(&info->super_copy))
2769                         break;
2770         }
2771         ret = 0;
2772 error:
2773         btrfs_free_path(path);
2774         return ret;
2775 }
2776
2777 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
2778                            struct btrfs_root *root, u64 bytes_used,
2779                            u64 type, u64 chunk_objectid, u64 chunk_offset,
2780                            u64 size)
2781 {
2782         int ret;
2783         int bit = 0;
2784         struct btrfs_root *extent_root;
2785         struct btrfs_block_group_cache *cache;
2786         struct extent_io_tree *block_group_cache;
2787
2788         extent_root = root->fs_info->extent_root;
2789         block_group_cache = &root->fs_info->block_group_cache;
2790
2791         cache = kmalloc(sizeof(*cache), GFP_NOFS);
2792         BUG_ON(!cache);
2793         cache->key.objectid = chunk_offset;
2794         cache->key.offset = size;
2795         cache->cached = 0;
2796         cache->pinned = 0;
2797
2798         btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2799         memset(&cache->item, 0, sizeof(cache->item));
2800         btrfs_set_block_group_used(&cache->item, bytes_used);
2801         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
2802         cache->flags = type;
2803         btrfs_set_block_group_flags(&cache->item, type);
2804
2805         ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
2806                                 &cache->space_info);
2807         BUG_ON(ret);
2808
2809         bit = block_group_state_bits(type);
2810         set_extent_bits(block_group_cache, chunk_offset,
2811                         chunk_offset + size - 1,
2812                         bit | EXTENT_LOCKED, GFP_NOFS);
2813
2814         set_state_private(block_group_cache, chunk_offset,
2815                           (unsigned long)cache);
2816         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
2817                                 sizeof(cache->item));
2818         BUG_ON(ret);
2819
2820         finish_current_insert(trans, extent_root);
2821         ret = del_pending_extents(trans, extent_root);
2822         BUG_ON(ret);
2823         set_avail_alloc_bits(extent_root->fs_info, type);
2824         return 0;
2825 }