Pileus Git - ~andy/linux/blob - fs/btrfs/extent-tree.c

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