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