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