extent-tree.c

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