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