fs/btrfs/ctree.c

   1 /*
   2  * Copyright (C) 2007,2008 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include <linux/sched.h>
  20 #include <linux/slab.h>
  21 #include <linux/rbtree.h>
  22 #include "ctree.h"
  23 #include "disk-io.h"
  24 #include "transaction.h"
  25 #include "print-tree.h"
  26 #include "locking.h"
  27
  28 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  29                       *root, struct btrfs_path *path, int level);
  30 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
  31                       *root, struct btrfs_key *ins_key,
  32                       struct btrfs_path *path, int data_size, int extend);
  33 static int push_node_left(struct btrfs_trans_handle *trans,
  34                           struct btrfs_root *root, struct extent_buffer *dst,
  35                           struct extent_buffer *src, int empty);
  36 static int balance_node_right(struct btrfs_trans_handle *trans,
  37                               struct btrfs_root *root,
  38                               struct extent_buffer *dst_buf,
  39                               struct extent_buffer *src_buf);
  40 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
  41                     int level, int slot);
  42 static int tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
  43                                  struct extent_buffer *eb);
  44
  45 struct btrfs_path *btrfs_alloc_path(void)
  46 {
  47         struct btrfs_path *path;
  48         path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
  49         return path;
  50 }
  51
  52 /*
  53  * set all locked nodes in the path to blocking locks.  This should
  54  * be done before scheduling
  55  */
  56 noinline void btrfs_set_path_blocking(struct btrfs_path *p)
  57 {
  58         int i;
  59         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  60                 if (!p->nodes[i] || !p->locks[i])
  61                         continue;
  62                 btrfs_set_lock_blocking_rw(p->nodes[i], p->locks[i]);
  63                 if (p->locks[i] == BTRFS_READ_LOCK)
  64                         p->locks[i] = BTRFS_READ_LOCK_BLOCKING;
  65                 else if (p->locks[i] == BTRFS_WRITE_LOCK)
  66                         p->locks[i] = BTRFS_WRITE_LOCK_BLOCKING;
  67         }
  68 }
  69
  70 /*
  71  * reset all the locked nodes in the patch to spinning locks.
  72  *
  73  * held is used to keep lockdep happy, when lockdep is enabled
  74  * we set held to a blocking lock before we go around and
  75  * retake all the spinlocks in the path.  You can safely use NULL
  76  * for held
  77  */
  78 noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
  79                                         struct extent_buffer *held, int held_rw)
  80 {
  81         int i;
  82
  83         if (held) {
  84                 btrfs_set_lock_blocking_rw(held, held_rw);
  85                 if (held_rw == BTRFS_WRITE_LOCK)
  86                         held_rw = BTRFS_WRITE_LOCK_BLOCKING;
  87                 else if (held_rw == BTRFS_READ_LOCK)
  88                         held_rw = BTRFS_READ_LOCK_BLOCKING;
  89         }
  90         btrfs_set_path_blocking(p);
  91
  92         for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
  93                 if (p->nodes[i] && p->locks[i]) {
  94                         btrfs_clear_lock_blocking_rw(p->nodes[i], p->locks[i]);
  95                         if (p->locks[i] == BTRFS_WRITE_LOCK_BLOCKING)
  96                                 p->locks[i] = BTRFS_WRITE_LOCK;
  97                         else if (p->locks[i] == BTRFS_READ_LOCK_BLOCKING)
  98                                 p->locks[i] = BTRFS_READ_LOCK;
  99                 }
 100         }
 101
 102         if (held)
 103                 btrfs_clear_lock_blocking_rw(held, held_rw);
 104 }
 105
 106 /* this also releases the path */
 107 void btrfs_free_path(struct btrfs_path *p)
 108 {
 109         if (!p)
 110                 return;
 111         btrfs_release_path(p);
 112         kmem_cache_free(btrfs_path_cachep, p);
 113 }
 114
 115 /*
 116  * path release drops references on the extent buffers in the path
 117  * and it drops any locks held by this path
 118  *
 119  * It is safe to call this on paths that no locks or extent buffers held.
 120  */
 121 noinline void btrfs_release_path(struct btrfs_path *p)
 122 {
 123         int i;
 124
 125         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
 126                 p->slots[i] = 0;
 127                 if (!p->nodes[i])
 128                         continue;
 129                 if (p->locks[i]) {
 130                         btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]);
 131                         p->locks[i] = 0;
 132                 }
 133                 free_extent_buffer(p->nodes[i]);
 134                 p->nodes[i] = NULL;
 135         }
 136 }
 137
 138 /*
 139  * safely gets a reference on the root node of a tree.  A lock
 140  * is not taken, so a concurrent writer may put a different node
 141  * at the root of the tree.  See btrfs_lock_root_node for the
 142  * looping required.
 143  *
 144  * The extent buffer returned by this has a reference taken, so
 145  * it won't disappear.  It may stop being the root of the tree
 146  * at any time because there are no locks held.
 147  */
 148 struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
 149 {
 150         struct extent_buffer *eb;
 151
 152         while (1) {
 153                 rcu_read_lock();
 154                 eb = rcu_dereference(root->node);
 155
 156                 /*
 157                  * RCU really hurts here, we could free up the root node because
 158                  * it was cow'ed but we may not get the new root node yet so do
 159                  * the inc_not_zero dance and if it doesn't work then
 160                  * synchronize_rcu and try again.
 161                  */
 162                 if (atomic_inc_not_zero(&eb->refs)) {
 163                         rcu_read_unlock();
 164                         break;
 165                 }
 166                 rcu_read_unlock();
 167                 synchronize_rcu();
 168         }
 169         return eb;
 170 }
 171
 172 /* loop around taking references on and locking the root node of the
 173  * tree until you end up with a lock on the root.  A locked buffer
 174  * is returned, with a reference held.
 175  */
 176 struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
 177 {
 178         struct extent_buffer *eb;
 179
 180         while (1) {
 181                 eb = btrfs_root_node(root);
 182                 btrfs_tree_lock(eb);
 183                 if (eb == root->node)
 184                         break;
 185                 btrfs_tree_unlock(eb);
 186                 free_extent_buffer(eb);
 187         }
 188         return eb;
 189 }
 190
 191 /* loop around taking references on and locking the root node of the
 192  * tree until you end up with a lock on the root.  A locked buffer
 193  * is returned, with a reference held.
 194  */
 195 static struct extent_buffer *btrfs_read_lock_root_node(struct btrfs_root *root)
 196 {
 197         struct extent_buffer *eb;
 198
 199         while (1) {
 200                 eb = btrfs_root_node(root);
 201                 btrfs_tree_read_lock(eb);
 202                 if (eb == root->node)
 203                         break;
 204                 btrfs_tree_read_unlock(eb);
 205                 free_extent_buffer(eb);
 206         }
 207         return eb;
 208 }
 209
 210 /* cowonly root (everything not a reference counted cow subvolume), just get
 211  * put onto a simple dirty list.  transaction.c walks this to make sure they
 212  * get properly updated on disk.
 213  */
 214 static void add_root_to_dirty_list(struct btrfs_root *root)
 215 {
 216         if (test_bit(BTRFS_ROOT_DIRTY, &root->state) ||
 217             !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state))
 218                 return;
 219
 220         spin_lock(&root->fs_info->trans_lock);
 221         if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) {
 222                 /* Want the extent tree to be the last on the list */
 223                 if (root->objectid == BTRFS_EXTENT_TREE_OBJECTID)
 224                         list_move_tail(&root->dirty_list,
 225                                        &root->fs_info->dirty_cowonly_roots);
 226                 else
 227                         list_move(&root->dirty_list,
 228                                   &root->fs_info->dirty_cowonly_roots);
 229         }
 230         spin_unlock(&root->fs_info->trans_lock);
 231 }
 232
 233 /*
 234  * used by snapshot creation to make a copy of a root for a tree with
 235  * a given objectid.  The buffer with the new root node is returned in
 236  * cow_ret, and this func returns zero on success or a negative error code.
 237  */
 238 int btrfs_copy_root(struct btrfs_trans_handle *trans,
 239                       struct btrfs_root *root,
 240                       struct extent_buffer *buf,
 241                       struct extent_buffer **cow_ret, u64 new_root_objectid)
 242 {
 243         struct extent_buffer *cow;
 244         int ret = 0;
 245         int level;
 246         struct btrfs_disk_key disk_key;
 247
 248         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 249                 trans->transid != root->fs_info->running_transaction->transid);
 250         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 251                 trans->transid != root->last_trans);
 252
 253         level = btrfs_header_level(buf);
 254         if (level == 0)
 255                 btrfs_item_key(buf, &disk_key, 0);
 256         else
 257                 btrfs_node_key(buf, &disk_key, 0);
 258
 259         cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid,
 260                         &disk_key, level, buf->start, 0);
 261         if (IS_ERR(cow))
 262                 return PTR_ERR(cow);
 263
 264         copy_extent_buffer(cow, buf, 0, 0, cow->len);
 265         btrfs_set_header_bytenr(cow, cow->start);
 266         btrfs_set_header_generation(cow, trans->transid);
 267         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
 268         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
 269                                      BTRFS_HEADER_FLAG_RELOC);
 270         if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
 271                 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
 272         else
 273                 btrfs_set_header_owner(cow, new_root_objectid);
 274
 275         write_extent_buffer(cow, root->fs_info->fsid, btrfs_header_fsid(),
 276                             BTRFS_FSID_SIZE);
 277
 278         WARN_ON(btrfs_header_generation(buf) > trans->transid);
 279         if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
 280                 ret = btrfs_inc_ref(trans, root, cow, 1);
 281         else
 282                 ret = btrfs_inc_ref(trans, root, cow, 0);
 283
 284         if (ret)
 285                 return ret;
 286
 287         btrfs_mark_buffer_dirty(cow);
 288         *cow_ret = cow;
 289         return 0;
 290 }
 291
 292 enum mod_log_op {
 293         MOD_LOG_KEY_REPLACE,
 294         MOD_LOG_KEY_ADD,
 295         MOD_LOG_KEY_REMOVE,
 296         MOD_LOG_KEY_REMOVE_WHILE_FREEING,
 297         MOD_LOG_KEY_REMOVE_WHILE_MOVING,
 298         MOD_LOG_MOVE_KEYS,
 299         MOD_LOG_ROOT_REPLACE,
 300 };
 301
 302 struct tree_mod_move {
 303         int dst_slot;
 304         int nr_items;
 305 };
 306
 307 struct tree_mod_root {
 308         u64 logical;
 309         u8 level;
 310 };
 311
 312 struct tree_mod_elem {
 313         struct rb_node node;
 314         u64 index;              /* shifted logical */
 315         u64 seq;
 316         enum mod_log_op op;
 317
 318         /* this is used for MOD_LOG_KEY_* and MOD_LOG_MOVE_KEYS operations */
 319         int slot;
 320
 321         /* this is used for MOD_LOG_KEY* and MOD_LOG_ROOT_REPLACE */
 322         u64 generation;
 323
 324         /* those are used for op == MOD_LOG_KEY_{REPLACE,REMOVE} */
 325         struct btrfs_disk_key key;
 326         u64 blockptr;
 327
 328         /* this is used for op == MOD_LOG_MOVE_KEYS */
 329         struct tree_mod_move move;
 330
 331         /* this is used for op == MOD_LOG_ROOT_REPLACE */
 332         struct tree_mod_root old_root;
 333 };
 334
 335 /*
 336  * Pull a new tree mod seq number for our operation.
 337  */
 338 static inline u64 btrfs_inc_tree_mod_seq(struct btrfs_fs_info *fs_info)
 339 {
 340         return atomic64_inc_return(&fs_info->tree_mod_seq);
 341 }
 342
 343 /*
 344  * This adds a new blocker to the tree mod log's blocker list if the @elem
 345  * passed does not already have a sequence number set. So when a caller expects
 346  * to record tree modifications, it should ensure to set elem->seq to zero
 347  * before calling btrfs_get_tree_mod_seq.
 348  * Returns a fresh, unused tree log modification sequence number, even if no new
 349  * blocker was added.
 350  */
 351 u64 btrfs_get_tree_mod_seq(struct btrfs_fs_info *fs_info,
 352                            struct seq_list *elem)
 353 {
 354         write_lock(&fs_info->tree_mod_log_lock);
 355         if (!elem->seq) {
 356                 elem->seq = btrfs_inc_tree_mod_seq(fs_info);
 357                 list_add_tail(&elem->list, &fs_info->tree_mod_seq_list);
 358         }
 359         write_unlock(&fs_info->tree_mod_log_lock);
 360
 361         return elem->seq;
 362 }
 363
 364 void btrfs_put_tree_mod_seq(struct btrfs_fs_info *fs_info,
 365                             struct seq_list *elem)
 366 {
 367         struct rb_root *tm_root;
 368         struct rb_node *node;
 369         struct rb_node *next;
 370         struct seq_list *cur_elem;
 371         struct tree_mod_elem *tm;
 372         u64 min_seq = (u64)-1;
 373         u64 seq_putting = elem->seq;
 374
 375         if (!seq_putting)
 376                 return;
 377
 378         write_lock(&fs_info->tree_mod_log_lock);
 379         list_del(&elem->list);
 380         elem->seq = 0;
 381
 382         list_for_each_entry(cur_elem, &fs_info->tree_mod_seq_list, list) {
 383                 if (cur_elem->seq < min_seq) {
 384                         if (seq_putting > cur_elem->seq) {
 385                                 /*
 386                                  * blocker with lower sequence number exists, we
 387                                  * cannot remove anything from the log
 388                                  */
 389                                 write_unlock(&fs_info->tree_mod_log_lock);
 390                                 return;
 391                         }
 392                         min_seq = cur_elem->seq;
 393                 }
 394         }
 395
 396         /*
 397          * anything that's lower than the lowest existing (read: blocked)
 398          * sequence number can be removed from the tree.
 399          */
 400         tm_root = &fs_info->tree_mod_log;
 401         for (node = rb_first(tm_root); node; node = next) {
 402                 next = rb_next(node);
 403                 tm = container_of(node, struct tree_mod_elem, node);
 404                 if (tm->seq >= min_seq)
 405                         continue;
 406                 rb_erase(node, tm_root);
 407                 kfree(tm);
 408         }
 409         write_unlock(&fs_info->tree_mod_log_lock);
 410 }
 411
 412 /*
 413  * key order of the log:
 414  *       index -> sequence
 415  *
 416  * the index is the shifted logical of the *new* root node for root replace
 417  * operations, or the shifted logical of the affected block for all other
 418  * operations.
 419  *
 420  * Note: must be called with write lock for fs_info::tree_mod_log_lock.
 421  */
 422 static noinline int
 423 __tree_mod_log_insert(struct btrfs_fs_info *fs_info, struct tree_mod_elem *tm)
 424 {
 425         struct rb_root *tm_root;
 426         struct rb_node **new;
 427         struct rb_node *parent = NULL;
 428         struct tree_mod_elem *cur;
 429
 430         BUG_ON(!tm);
 431
 432         tm->seq = btrfs_inc_tree_mod_seq(fs_info);
 433
 434         tm_root = &fs_info->tree_mod_log;
 435         new = &tm_root->rb_node;
 436         while (*new) {
 437                 cur = container_of(*new, struct tree_mod_elem, node);
 438                 parent = *new;
 439                 if (cur->index < tm->index)
 440                         new = &((*new)->rb_left);
 441                 else if (cur->index > tm->index)
 442                         new = &((*new)->rb_right);
 443                 else if (cur->seq < tm->seq)
 444                         new = &((*new)->rb_left);
 445                 else if (cur->seq > tm->seq)
 446                         new = &((*new)->rb_right);
 447                 else
 448                         return -EEXIST;
 449         }
 450
 451         rb_link_node(&tm->node, parent, new);
 452         rb_insert_color(&tm->node, tm_root);
 453         return 0;
 454 }
 455
 456 /*
 457  * Determines if logging can be omitted. Returns 1 if it can. Otherwise, it
 458  * returns zero with the tree_mod_log_lock acquired. The caller must hold
 459  * this until all tree mod log insertions are recorded in the rb tree and then
 460  * write unlock fs_info::tree_mod_log_lock.
 461  */
 462 static inline int tree_mod_dont_log(struct btrfs_fs_info *fs_info,
 463                                     struct extent_buffer *eb) {
 464         smp_mb();
 465         if (list_empty(&(fs_info)->tree_mod_seq_list))
 466                 return 1;
 467         if (eb && btrfs_header_level(eb) == 0)
 468                 return 1;
 469
 470         write_lock(&fs_info->tree_mod_log_lock);
 471         if (list_empty(&(fs_info)->tree_mod_seq_list)) {
 472                 write_unlock(&fs_info->tree_mod_log_lock);
 473                 return 1;
 474         }
 475
 476         return 0;
 477 }
 478
 479 /* Similar to tree_mod_dont_log, but doesn't acquire any locks. */
 480 static inline int tree_mod_need_log(const struct btrfs_fs_info *fs_info,
 481                                     struct extent_buffer *eb)
 482 {
 483         smp_mb();
 484         if (list_empty(&(fs_info)->tree_mod_seq_list))
 485                 return 0;
 486         if (eb && btrfs_header_level(eb) == 0)
 487                 return 0;
 488
 489         return 1;
 490 }
 491
 492 static struct tree_mod_elem *
 493 alloc_tree_mod_elem(struct extent_buffer *eb, int slot,
 494                     enum mod_log_op op, gfp_t flags)
 495 {
 496         struct tree_mod_elem *tm;
 497
 498         tm = kzalloc(sizeof(*tm), flags);
 499         if (!tm)
 500                 return NULL;
 501
 502         tm->index = eb->start >> PAGE_CACHE_SHIFT;
 503         if (op != MOD_LOG_KEY_ADD) {
 504                 btrfs_node_key(eb, &tm->key, slot);
 505                 tm->blockptr = btrfs_node_blockptr(eb, slot);
 506         }
 507         tm->op = op;
 508         tm->slot = slot;
 509         tm->generation = btrfs_node_ptr_generation(eb, slot);
 510         RB_CLEAR_NODE(&tm->node);
 511
 512         return tm;
 513 }
 514
 515 static noinline int
 516 tree_mod_log_insert_key(struct btrfs_fs_info *fs_info,
 517                         struct extent_buffer *eb, int slot,
 518                         enum mod_log_op op, gfp_t flags)
 519 {
 520         struct tree_mod_elem *tm;
 521         int ret;
 522
 523         if (!tree_mod_need_log(fs_info, eb))
 524                 return 0;
 525
 526         tm = alloc_tree_mod_elem(eb, slot, op, flags);
 527         if (!tm)
 528                 return -ENOMEM;
 529
 530         if (tree_mod_dont_log(fs_info, eb)) {
 531                 kfree(tm);
 532                 return 0;
 533         }
 534
 535         ret = __tree_mod_log_insert(fs_info, tm);
 536         write_unlock(&eb->fs_info->tree_mod_log_lock);
 537         if (ret)
 538                 kfree(tm);
 539
 540         return ret;
 541 }
 542
 543 static noinline int
 544 tree_mod_log_insert_move(struct btrfs_fs_info *fs_info,
 545                          struct extent_buffer *eb, int dst_slot, int src_slot,
 546                          int nr_items, gfp_t flags)
 547 {
 548         struct tree_mod_elem *tm = NULL;
 549         struct tree_mod_elem **tm_list = NULL;
 550         int ret = 0;
 551         int i;
 552         int locked = 0;
 553
 554         if (!tree_mod_need_log(fs_info, eb))
 555                 return 0;
 556
 557         tm_list = kcalloc(nr_items, sizeof(struct tree_mod_elem *), flags);
 558         if (!tm_list)
 559                 return -ENOMEM;
 560
 561         tm = kzalloc(sizeof(*tm), flags);
 562         if (!tm) {
 563                 ret = -ENOMEM;
 564                 goto free_tms;
 565         }
 566
 567         tm->index = eb->start >> PAGE_CACHE_SHIFT;
 568         tm->slot = src_slot;
 569         tm->move.dst_slot = dst_slot;
 570         tm->move.nr_items = nr_items;
 571         tm->op = MOD_LOG_MOVE_KEYS;
 572
 573         for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
 574                 tm_list[i] = alloc_tree_mod_elem(eb, i + dst_slot,
 575                     MOD_LOG_KEY_REMOVE_WHILE_MOVING, flags);
 576                 if (!tm_list[i]) {
 577                         ret = -ENOMEM;
 578                         goto free_tms;
 579                 }
 580         }
 581
 582         if (tree_mod_dont_log(fs_info, eb))
 583                 goto free_tms;
 584         locked = 1;
 585
 586         /*
 587          * When we override something during the move, we log these removals.
 588          * This can only happen when we move towards the beginning of the
 589          * buffer, i.e. dst_slot < src_slot.
 590          */
 591         for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
 592                 ret = __tree_mod_log_insert(fs_info, tm_list[i]);
 593                 if (ret)
 594                         goto free_tms;
 595         }
 596
 597         ret = __tree_mod_log_insert(fs_info, tm);
 598         if (ret)
 599                 goto free_tms;
 600         write_unlock(&eb->fs_info->tree_mod_log_lock);
 601         kfree(tm_list);
 602
 603         return 0;
 604 free_tms:
 605         for (i = 0; i < nr_items; i++) {
 606                 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
 607                         rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
 608                 kfree(tm_list[i]);
 609         }
 610         if (locked)
 611                 write_unlock(&eb->fs_info->tree_mod_log_lock);
 612         kfree(tm_list);
 613         kfree(tm);
 614
 615         return ret;
 616 }
 617
 618 static inline int
 619 __tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
 620                        struct tree_mod_elem **tm_list,
 621                        int nritems)
 622 {
 623         int i, j;
 624         int ret;
 625
 626         for (i = nritems - 1; i >= 0; i--) {
 627                 ret = __tree_mod_log_insert(fs_info, tm_list[i]);
 628                 if (ret) {
 629                         for (j = nritems - 1; j > i; j--)
 630                                 rb_erase(&tm_list[j]->node,
 631                                          &fs_info->tree_mod_log);
 632                         return ret;
 633                 }
 634         }
 635
 636         return 0;
 637 }
 638
 639 static noinline int
 640 tree_mod_log_insert_root(struct btrfs_fs_info *fs_info,
 641                          struct extent_buffer *old_root,
 642                          struct extent_buffer *new_root, gfp_t flags,
 643                          int log_removal)
 644 {
 645         struct tree_mod_elem *tm = NULL;
 646         struct tree_mod_elem **tm_list = NULL;
 647         int nritems = 0;
 648         int ret = 0;
 649         int i;
 650
 651         if (!tree_mod_need_log(fs_info, NULL))
 652                 return 0;
 653
 654         if (log_removal && btrfs_header_level(old_root) > 0) {
 655                 nritems = btrfs_header_nritems(old_root);
 656                 tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *),
 657                                   flags);
 658                 if (!tm_list) {
 659                         ret = -ENOMEM;
 660                         goto free_tms;
 661                 }
 662                 for (i = 0; i < nritems; i++) {
 663                         tm_list[i] = alloc_tree_mod_elem(old_root, i,
 664                             MOD_LOG_KEY_REMOVE_WHILE_FREEING, flags);
 665                         if (!tm_list[i]) {
 666                                 ret = -ENOMEM;
 667                                 goto free_tms;
 668                         }
 669                 }
 670         }
 671
 672         tm = kzalloc(sizeof(*tm), flags);
 673         if (!tm) {
 674                 ret = -ENOMEM;
 675                 goto free_tms;
 676         }
 677
 678         tm->index = new_root->start >> PAGE_CACHE_SHIFT;
 679         tm->old_root.logical = old_root->start;
 680         tm->old_root.level = btrfs_header_level(old_root);
 681         tm->generation = btrfs_header_generation(old_root);
 682         tm->op = MOD_LOG_ROOT_REPLACE;
 683
 684         if (tree_mod_dont_log(fs_info, NULL))
 685                 goto free_tms;
 686
 687         if (tm_list)
 688                 ret = __tree_mod_log_free_eb(fs_info, tm_list, nritems);
 689         if (!ret)
 690                 ret = __tree_mod_log_insert(fs_info, tm);
 691
 692         write_unlock(&fs_info->tree_mod_log_lock);
 693         if (ret)
 694                 goto free_tms;
 695         kfree(tm_list);
 696
 697         return ret;
 698
 699 free_tms:
 700         if (tm_list) {
 701                 for (i = 0; i < nritems; i++)
 702                         kfree(tm_list[i]);
 703                 kfree(tm_list);
 704         }
 705         kfree(tm);
 706
 707         return ret;
 708 }
 709
 710 static struct tree_mod_elem *
 711 __tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq,
 712                       int smallest)
 713 {
 714         struct rb_root *tm_root;
 715         struct rb_node *node;
 716         struct tree_mod_elem *cur = NULL;
 717         struct tree_mod_elem *found = NULL;
 718         u64 index = start >> PAGE_CACHE_SHIFT;
 719
 720         read_lock(&fs_info->tree_mod_log_lock);
 721         tm_root = &fs_info->tree_mod_log;
 722         node = tm_root->rb_node;
 723         while (node) {
 724                 cur = container_of(node, struct tree_mod_elem, node);
 725                 if (cur->index < index) {
 726                         node = node->rb_left;
 727                 } else if (cur->index > index) {
 728                         node = node->rb_right;
 729                 } else if (cur->seq < min_seq) {
 730                         node = node->rb_left;
 731                 } else if (!smallest) {
 732                         /* we want the node with the highest seq */
 733                         if (found)
 734                                 BUG_ON(found->seq > cur->seq);
 735                         found = cur;
 736                         node = node->rb_left;
 737                 } else if (cur->seq > min_seq) {
 738                         /* we want the node with the smallest seq */
 739                         if (found)
 740                                 BUG_ON(found->seq < cur->seq);
 741                         found = cur;
 742                         node = node->rb_right;
 743                 } else {
 744                         found = cur;
 745                         break;
 746                 }
 747         }
 748         read_unlock(&fs_info->tree_mod_log_lock);
 749
 750         return found;
 751 }
 752
 753 /*
 754  * this returns the element from the log with the smallest time sequence
 755  * value that's in the log (the oldest log item). any element with a time
 756  * sequence lower than min_seq will be ignored.
 757  */
 758 static struct tree_mod_elem *
 759 tree_mod_log_search_oldest(struct btrfs_fs_info *fs_info, u64 start,
 760                            u64 min_seq)
 761 {
 762         return __tree_mod_log_search(fs_info, start, min_seq, 1);
 763 }
 764
 765 /*
 766  * this returns the element from the log with the largest time sequence
 767  * value that's in the log (the most recent log item). any element with
 768  * a time sequence lower than min_seq will be ignored.
 769  */
 770 static struct tree_mod_elem *
 771 tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq)
 772 {
 773         return __tree_mod_log_search(fs_info, start, min_seq, 0);
 774 }
 775
 776 static noinline int
 777 tree_mod_log_eb_copy(struct btrfs_fs_info *fs_info, struct extent_buffer *dst,
 778                      struct extent_buffer *src, unsigned long dst_offset,
 779                      unsigned long src_offset, int nr_items)
 780 {
 781         int ret = 0;
 782         struct tree_mod_elem **tm_list = NULL;
 783         struct tree_mod_elem **tm_list_add, **tm_list_rem;
 784         int i;
 785         int locked = 0;
 786
 787         if (!tree_mod_need_log(fs_info, NULL))
 788                 return 0;
 789
 790         if (btrfs_header_level(dst) == 0 && btrfs_header_level(src) == 0)
 791                 return 0;
 792
 793         tm_list = kcalloc(nr_items * 2, sizeof(struct tree_mod_elem *),
 794                           GFP_NOFS);
 795         if (!tm_list)
 796                 return -ENOMEM;
 797
 798         tm_list_add = tm_list;
 799         tm_list_rem = tm_list + nr_items;
 800         for (i = 0; i < nr_items; i++) {
 801                 tm_list_rem[i] = alloc_tree_mod_elem(src, i + src_offset,
 802                     MOD_LOG_KEY_REMOVE, GFP_NOFS);
 803                 if (!tm_list_rem[i]) {
 804                         ret = -ENOMEM;
 805                         goto free_tms;
 806                 }
 807
 808                 tm_list_add[i] = alloc_tree_mod_elem(dst, i + dst_offset,
 809                     MOD_LOG_KEY_ADD, GFP_NOFS);
 810                 if (!tm_list_add[i]) {
 811                         ret = -ENOMEM;
 812                         goto free_tms;
 813                 }
 814         }
 815
 816         if (tree_mod_dont_log(fs_info, NULL))
 817                 goto free_tms;
 818         locked = 1;
 819
 820         for (i = 0; i < nr_items; i++) {
 821                 ret = __tree_mod_log_insert(fs_info, tm_list_rem[i]);
 822                 if (ret)
 823                         goto free_tms;
 824                 ret = __tree_mod_log_insert(fs_info, tm_list_add[i]);
 825                 if (ret)
 826                         goto free_tms;
 827         }
 828
 829         write_unlock(&fs_info->tree_mod_log_lock);
 830         kfree(tm_list);
 831
 832         return 0;
 833
 834 free_tms:
 835         for (i = 0; i < nr_items * 2; i++) {
 836                 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
 837                         rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
 838                 kfree(tm_list[i]);
 839         }
 840         if (locked)
 841                 write_unlock(&fs_info->tree_mod_log_lock);
 842         kfree(tm_list);
 843
 844         return ret;
 845 }
 846
 847 static inline void
 848 tree_mod_log_eb_move(struct btrfs_fs_info *fs_info, struct extent_buffer *dst,
 849                      int dst_offset, int src_offset, int nr_items)
 850 {
 851         int ret;
 852         ret = tree_mod_log_insert_move(fs_info, dst, dst_offset, src_offset,
 853                                        nr_items, GFP_NOFS);
 854         BUG_ON(ret < 0);
 855 }
 856
 857 static noinline void
 858 tree_mod_log_set_node_key(struct btrfs_fs_info *fs_info,
 859                           struct extent_buffer *eb, int slot, int atomic)
 860 {
 861         int ret;
 862
 863         ret = tree_mod_log_insert_key(fs_info, eb, slot,
 864                                         MOD_LOG_KEY_REPLACE,
 865                                         atomic ? GFP_ATOMIC : GFP_NOFS);
 866         BUG_ON(ret < 0);
 867 }
 868
 869 static noinline int
 870 tree_mod_log_free_eb(struct btrfs_fs_info *fs_info, struct extent_buffer *eb)
 871 {
 872         struct tree_mod_elem **tm_list = NULL;
 873         int nritems = 0;
 874         int i;
 875         int ret = 0;
 876
 877         if (btrfs_header_level(eb) == 0)
 878                 return 0;
 879
 880         if (!tree_mod_need_log(fs_info, NULL))
 881                 return 0;
 882
 883         nritems = btrfs_header_nritems(eb);
 884         tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *), GFP_NOFS);
 885         if (!tm_list)
 886                 return -ENOMEM;
 887
 888         for (i = 0; i < nritems; i++) {
 889                 tm_list[i] = alloc_tree_mod_elem(eb, i,
 890                     MOD_LOG_KEY_REMOVE_WHILE_FREEING, GFP_NOFS);
 891                 if (!tm_list[i]) {
 892                         ret = -ENOMEM;
 893                         goto free_tms;
 894                 }
 895         }
 896
 897         if (tree_mod_dont_log(fs_info, eb))
 898                 goto free_tms;
 899
 900         ret = __tree_mod_log_free_eb(fs_info, tm_list, nritems);
 901         write_unlock(&eb->fs_info->tree_mod_log_lock);
 902         if (ret)
 903                 goto free_tms;
 904         kfree(tm_list);
 905
 906         return 0;
 907
 908 free_tms:
 909         for (i = 0; i < nritems; i++)
 910                 kfree(tm_list[i]);
 911         kfree(tm_list);
 912
 913         return ret;
 914 }
 915
 916 static noinline void
 917 tree_mod_log_set_root_pointer(struct btrfs_root *root,
 918                               struct extent_buffer *new_root_node,
 919                               int log_removal)
 920 {
 921         int ret;
 922         ret = tree_mod_log_insert_root(root->fs_info, root->node,
 923                                        new_root_node, GFP_NOFS, log_removal);
 924         BUG_ON(ret < 0);
 925 }
 926
 927 /*
 928  * check if the tree block can be shared by multiple trees
 929  */
 930 int btrfs_block_can_be_shared(struct btrfs_root *root,
 931                               struct extent_buffer *buf)
 932 {
 933         /*
 934          * Tree blocks not in refernece counted trees and tree roots
 935          * are never shared. If a block was allocated after the last
 936          * snapshot and the block was not allocated by tree relocation,
 937          * we know the block is not shared.
 938          */
 939         if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 940             buf != root->node && buf != root->commit_root &&
 941             (btrfs_header_generation(buf) <=
 942              btrfs_root_last_snapshot(&root->root_item) ||
 943              btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
 944                 return 1;
 945 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 946         if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 947             btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
 948                 return 1;
 949 #endif
 950         return 0;
 951 }
 952
 953 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
 954                                        struct btrfs_root *root,
 955                                        struct extent_buffer *buf,
 956                                        struct extent_buffer *cow,
 957                                        int *last_ref)
 958 {
 959         u64 refs;
 960         u64 owner;
 961         u64 flags;
 962         u64 new_flags = 0;
 963         int ret;
 964
 965         /*
 966          * Backrefs update rules:
 967          *
 968          * Always use full backrefs for extent pointers in tree block
 969          * allocated by tree relocation.
 970          *
 971          * If a shared tree block is no longer referenced by its owner
 972          * tree (btrfs_header_owner(buf) == root->root_key.objectid),
 973          * use full backrefs for extent pointers in tree block.
 974          *
 975          * If a tree block is been relocating
 976          * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
 977          * use full backrefs for extent pointers in tree block.
 978          * The reason for this is some operations (such as drop tree)
 979          * are only allowed for blocks use full backrefs.
 980          */
 981
 982         if (btrfs_block_can_be_shared(root, buf)) {
 983                 ret = btrfs_lookup_extent_info(trans, root, buf->start,
 984                                                btrfs_header_level(buf), 1,
 985                                                &refs, &flags);
 986                 if (ret)
 987                         return ret;
 988                 if (refs == 0) {
 989                         ret = -EROFS;
 990                         btrfs_std_error(root->fs_info, ret, NULL);
 991                         return ret;
 992                 }
 993         } else {
 994                 refs = 1;
 995                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
 996                     btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
 997                         flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
 998                 else
 999                         flags = 0;
1000         }
1001
1002         owner = btrfs_header_owner(buf);
1003         BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
1004                !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
1005
1006         if (refs > 1) {
1007                 if ((owner == root->root_key.objectid ||
1008                      root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
1009                     !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
1010                         ret = btrfs_inc_ref(trans, root, buf, 1);
1011                         BUG_ON(ret); /* -ENOMEM */
1012
1013                         if (root->root_key.objectid ==
1014                             BTRFS_TREE_RELOC_OBJECTID) {
1015                                 ret = btrfs_dec_ref(trans, root, buf, 0);
1016                                 BUG_ON(ret); /* -ENOMEM */
1017                                 ret = btrfs_inc_ref(trans, root, cow, 1);
1018                                 BUG_ON(ret); /* -ENOMEM */
1019                         }
1020                         new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
1021                 } else {
1022
1023                         if (root->root_key.objectid ==
1024                             BTRFS_TREE_RELOC_OBJECTID)
1025                                 ret = btrfs_inc_ref(trans, root, cow, 1);
1026                         else
1027                                 ret = btrfs_inc_ref(trans, root, cow, 0);
1028                         BUG_ON(ret); /* -ENOMEM */
1029                 }
1030                 if (new_flags != 0) {
1031                         int level = btrfs_header_level(buf);
1032
1033                         ret = btrfs_set_disk_extent_flags(trans, root,
1034                                                           buf->start,
1035                                                           buf->len,
1036                                                           new_flags, level, 0);
1037                         if (ret)
1038                                 return ret;
1039                 }
1040         } else {
1041                 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
1042                         if (root->root_key.objectid ==
1043                             BTRFS_TREE_RELOC_OBJECTID)
1044                                 ret = btrfs_inc_ref(trans, root, cow, 1);
1045                         else
1046                                 ret = btrfs_inc_ref(trans, root, cow, 0);
1047                         BUG_ON(ret); /* -ENOMEM */
1048                         ret = btrfs_dec_ref(trans, root, buf, 1);
1049                         BUG_ON(ret); /* -ENOMEM */
1050                 }
1051                 clean_tree_block(trans, root->fs_info, buf);
1052                 *last_ref = 1;
1053         }
1054         return 0;
1055 }
1056
1057 /*
1058  * does the dirty work in cow of a single block.  The parent block (if
1059  * supplied) is updated to point to the new cow copy.  The new buffer is marked
1060  * dirty and returned locked.  If you modify the block it needs to be marked
1061  * dirty again.
1062  *
1063  * search_start -- an allocation hint for the new block
1064  *
1065  * empty_size -- a hint that you plan on doing more cow.  This is the size in
1066  * bytes the allocator should try to find free next to the block it returns.
1067  * This is just a hint and may be ignored by the allocator.
1068  */
1069 static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
1070                              struct btrfs_root *root,
1071                              struct extent_buffer *buf,
1072                              struct extent_buffer *parent, int parent_slot,
1073                              struct extent_buffer **cow_ret,
1074                              u64 search_start, u64 empty_size)
1075 {
1076         struct btrfs_disk_key disk_key;
1077         struct extent_buffer *cow;
1078         int level, ret;
1079         int last_ref = 0;
1080         int unlock_orig = 0;
1081         u64 parent_start;
1082
1083         if (*cow_ret == buf)
1084                 unlock_orig = 1;
1085
1086         btrfs_assert_tree_locked(buf);
1087
1088         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
1089                 trans->transid != root->fs_info->running_transaction->transid);
1090         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
1091                 trans->transid != root->last_trans);
1092
1093         level = btrfs_header_level(buf);
1094
1095         if (level == 0)
1096                 btrfs_item_key(buf, &disk_key, 0);
1097         else
1098                 btrfs_node_key(buf, &disk_key, 0);
1099
1100         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1101                 if (parent)
1102                         parent_start = parent->start;
1103                 else
1104                         parent_start = 0;
1105         } else
1106                 parent_start = 0;
1107
1108         cow = btrfs_alloc_tree_block(trans, root, parent_start,
1109                         root->root_key.objectid, &disk_key, level,
1110                         search_start, empty_size);
1111         if (IS_ERR(cow))
1112                 return PTR_ERR(cow);
1113
1114         /* cow is set to blocking by btrfs_init_new_buffer */
1115
1116         copy_extent_buffer(cow, buf, 0, 0, cow->len);
1117         btrfs_set_header_bytenr(cow, cow->start);
1118         btrfs_set_header_generation(cow, trans->transid);
1119         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1120         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
1121                                      BTRFS_HEADER_FLAG_RELOC);
1122         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
1123                 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
1124         else
1125                 btrfs_set_header_owner(cow, root->root_key.objectid);
1126
1127         write_extent_buffer(cow, root->fs_info->fsid, btrfs_header_fsid(),
1128                             BTRFS_FSID_SIZE);
1129
1130         ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
1131         if (ret) {
1132                 btrfs_tree_unlock(cow);
1133                 free_extent_buffer(cow);
1134                 btrfs_abort_transaction(trans, root, ret);
1135                 return ret;
1136         }
1137
1138         if (test_bit(BTRFS_ROOT_REF_COWS, &root->state)) {
1139                 ret = btrfs_reloc_cow_block(trans, root, buf, cow);
1140                 if (ret) {
1141                         btrfs_tree_unlock(cow);
1142                         free_extent_buffer(cow);
1143                         btrfs_abort_transaction(trans, root, ret);
1144                         return ret;
1145                 }
1146         }
1147
1148         if (buf == root->node) {
1149                 WARN_ON(parent && parent != buf);
1150                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
1151                     btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
1152                         parent_start = buf->start;
1153                 else
1154                         parent_start = 0;
1155
1156                 extent_buffer_get(cow);
1157                 tree_mod_log_set_root_pointer(root, cow, 1);
1158                 rcu_assign_pointer(root->node, cow);
1159
1160                 btrfs_free_tree_block(trans, root, buf, parent_start,
1161                                       last_ref);
1162                 free_extent_buffer(buf);
1163                 add_root_to_dirty_list(root);
1164         } else {
1165                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
1166                         parent_start = parent->start;
1167                 else
1168                         parent_start = 0;
1169
1170                 WARN_ON(trans->transid != btrfs_header_generation(parent));
1171                 tree_mod_log_insert_key(root->fs_info, parent, parent_slot,
1172                                         MOD_LOG_KEY_REPLACE, GFP_NOFS);
1173                 btrfs_set_node_blockptr(parent, parent_slot,
1174                                         cow->start);
1175                 btrfs_set_node_ptr_generation(parent, parent_slot,
1176                                               trans->transid);
1177                 btrfs_mark_buffer_dirty(parent);
1178                 if (last_ref) {
1179                         ret = tree_mod_log_free_eb(root->fs_info, buf);
1180                         if (ret) {
1181                                 btrfs_tree_unlock(cow);
1182                                 free_extent_buffer(cow);
1183                                 btrfs_abort_transaction(trans, root, ret);
1184                                 return ret;
1185                         }
1186                 }
1187                 btrfs_free_tree_block(trans, root, buf, parent_start,
1188                                       last_ref);
1189         }
1190         if (unlock_orig)
1191                 btrfs_tree_unlock(buf);
1192         free_extent_buffer_stale(buf);
1193         btrfs_mark_buffer_dirty(cow);
1194         *cow_ret = cow;
1195         return 0;
1196 }
1197
1198 /*
1199  * returns the logical address of the oldest predecessor of the given root.
1200  * entries older than time_seq are ignored.
1201  */
1202 static struct tree_mod_elem *
1203 __tree_mod_log_oldest_root(struct btrfs_fs_info *fs_info,
1204                            struct extent_buffer *eb_root, u64 time_seq)
1205 {
1206         struct tree_mod_elem *tm;
1207         struct tree_mod_elem *found = NULL;
1208         u64 root_logical = eb_root->start;
1209         int looped = 0;
1210
1211         if (!time_seq)
1212                 return NULL;
1213
1214         /*
1215          * the very last operation that's logged for a root is the replacement
1216          * operation (if it is replaced at all). this has the index of the *new*
1217          * root, making it the very first operation that's logged for this root.
1218          */
1219         while (1) {
1220                 tm = tree_mod_log_search_oldest(fs_info, root_logical,
1221                                                 time_seq);
1222                 if (!looped && !tm)
1223                         return NULL;
1224                 /*
1225                  * if there are no tree operation for the oldest root, we simply
1226                  * return it. this should only happen if that (old) root is at
1227                  * level 0.
1228                  */
1229                 if (!tm)
1230                         break;
1231
1232                 /*
1233                  * if there's an operation that's not a root replacement, we
1234                  * found the oldest version of our root. normally, we'll find a
1235                  * MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here.
1236                  */
1237                 if (tm->op != MOD_LOG_ROOT_REPLACE)
1238                         break;
1239
1240                 found = tm;
1241                 root_logical = tm->old_root.logical;
1242                 looped = 1;
1243         }
1244
1245         /* if there's no old root to return, return what we found instead */
1246         if (!found)
1247                 found = tm;
1248
1249         return found;
1250 }
1251
1252 /*
1253  * tm is a pointer to the first operation to rewind within eb. then, all
1254  * previous operations will be rewinded (until we reach something older than
1255  * time_seq).
1256  */
1257 static void
1258 __tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct extent_buffer *eb,
1259                       u64 time_seq, struct tree_mod_elem *first_tm)
1260 {
1261         u32 n;
1262         struct rb_node *next;
1263         struct tree_mod_elem *tm = first_tm;
1264         unsigned long o_dst;
1265         unsigned long o_src;
1266         unsigned long p_size = sizeof(struct btrfs_key_ptr);
1267
1268         n = btrfs_header_nritems(eb);
1269         read_lock(&fs_info->tree_mod_log_lock);
1270         while (tm && tm->seq >= time_seq) {
1271                 /*
1272                  * all the operations are recorded with the operator used for
1273                  * the modification. as we're going backwards, we do the
1274                  * opposite of each operation here.
1275                  */
1276                 switch (tm->op) {
1277                 case MOD_LOG_KEY_REMOVE_WHILE_FREEING:
1278                         BUG_ON(tm->slot < n);
1279                         /* Fallthrough */
1280                 case MOD_LOG_KEY_REMOVE_WHILE_MOVING:
1281                 case MOD_LOG_KEY_REMOVE:
1282                         btrfs_set_node_key(eb, &tm->key, tm->slot);
1283                         btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
1284                         btrfs_set_node_ptr_generation(eb, tm->slot,
1285                                                       tm->generation);
1286                         n++;
1287                         break;
1288                 case MOD_LOG_KEY_REPLACE:
1289                         BUG_ON(tm->slot >= n);
1290                         btrfs_set_node_key(eb, &tm->key, tm->slot);
1291                         btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
1292                         btrfs_set_node_ptr_generation(eb, tm->slot,
1293                                                       tm->generation);
1294                         break;
1295                 case MOD_LOG_KEY_ADD:
1296                         /* if a move operation is needed it's in the log */
1297                         n--;
1298                         break;
1299                 case MOD_LOG_MOVE_KEYS:
1300                         o_dst = btrfs_node_key_ptr_offset(tm->slot);
1301                         o_src = btrfs_node_key_ptr_offset(tm->move.dst_slot);
1302                         memmove_extent_buffer(eb, o_dst, o_src,
1303                                               tm->move.nr_items * p_size);
1304                         break;
1305                 case MOD_LOG_ROOT_REPLACE:
1306                         /*
1307                          * this operation is special. for roots, this must be
1308                          * handled explicitly before rewinding.
1309                          * for non-roots, this operation may exist if the node
1310                          * was a root: root A -> child B; then A gets empty and
1311                          * B is promoted to the new root. in the mod log, we'll
1312                          * have a root-replace operation for B, a tree block
1313                          * that is no root. we simply ignore that operation.
1314                          */
1315                         break;
1316                 }
1317                 next = rb_next(&tm->node);
1318                 if (!next)
1319                         break;
1320                 tm = container_of(next, struct tree_mod_elem, node);
1321                 if (tm->index != first_tm->index)
1322                         break;
1323         }
1324         read_unlock(&fs_info->tree_mod_log_lock);
1325         btrfs_set_header_nritems(eb, n);
1326 }
1327
1328 /*
1329  * Called with eb read locked. If the buffer cannot be rewinded, the same buffer
1330  * is returned. If rewind operations happen, a fresh buffer is returned. The
1331  * returned buffer is always read-locked. If the returned buffer is not the
1332  * input buffer, the lock on the input buffer is released and the input buffer
1333  * is freed (its refcount is decremented).
1334  */
1335 static struct extent_buffer *
1336 tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
1337                     struct extent_buffer *eb, u64 time_seq)
1338 {
1339         struct extent_buffer *eb_rewin;
1340         struct tree_mod_elem *tm;
1341
1342         if (!time_seq)
1343                 return eb;
1344
1345         if (btrfs_header_level(eb) == 0)
1346                 return eb;
1347
1348         tm = tree_mod_log_search(fs_info, eb->start, time_seq);
1349         if (!tm)
1350                 return eb;
1351
1352         btrfs_set_path_blocking(path);
1353         btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1354
1355         if (tm->op == MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1356                 BUG_ON(tm->slot != 0);
1357                 eb_rewin = alloc_dummy_extent_buffer(fs_info, eb->start);
1358                 if (!eb_rewin) {
1359                         btrfs_tree_read_unlock_blocking(eb);
1360                         free_extent_buffer(eb);
1361                         return NULL;
1362                 }
1363                 btrfs_set_header_bytenr(eb_rewin, eb->start);
1364                 btrfs_set_header_backref_rev(eb_rewin,
1365                                              btrfs_header_backref_rev(eb));
1366                 btrfs_set_header_owner(eb_rewin, btrfs_header_owner(eb));
1367                 btrfs_set_header_level(eb_rewin, btrfs_header_level(eb));
1368         } else {
1369                 eb_rewin = btrfs_clone_extent_buffer(eb);
1370                 if (!eb_rewin) {
1371                         btrfs_tree_read_unlock_blocking(eb);
1372                         free_extent_buffer(eb);
1373                         return NULL;
1374                 }
1375         }
1376
1377         btrfs_clear_path_blocking(path, NULL, BTRFS_READ_LOCK);
1378         btrfs_tree_read_unlock_blocking(eb);
1379         free_extent_buffer(eb);
1380
1381         btrfs_set_buffer_lockdep_class(btrfs_header_owner(eb_rewin),
1382                                        eb_rewin, btrfs_header_level(eb_rewin));
1383         btrfs_tree_read_lock(eb_rewin);
1384         __tree_mod_log_rewind(fs_info, eb_rewin, time_seq, tm);
1385         WARN_ON(btrfs_header_nritems(eb_rewin) >
1386                 BTRFS_NODEPTRS_PER_BLOCK(fs_info->tree_root));
1387
1388         return eb_rewin;
1389 }
1390
1391 /*
1392  * get_old_root() rewinds the state of @root's root node to the given @time_seq
1393  * value. If there are no changes, the current root->root_node is returned. If
1394  * anything changed in between, there's a fresh buffer allocated on which the
1395  * rewind operations are done. In any case, the returned buffer is read locked.
1396  * Returns NULL on error (with no locks held).
1397  */
1398 static inline struct extent_buffer *
1399 get_old_root(struct btrfs_root *root, u64 time_seq)
1400 {
1401         struct tree_mod_elem *tm;
1402         struct extent_buffer *eb = NULL;
1403         struct extent_buffer *eb_root;
1404         u64 eb_root_owner = 0;
1405         struct extent_buffer *old;
1406         struct tree_mod_root *old_root = NULL;
1407         u64 old_generation = 0;
1408         u64 logical;
1409
1410         eb_root = btrfs_read_lock_root_node(root);
1411         tm = __tree_mod_log_oldest_root(root->fs_info, eb_root, time_seq);
1412         if (!tm)
1413                 return eb_root;
1414
1415         if (tm->op == MOD_LOG_ROOT_REPLACE) {
1416                 old_root = &tm->old_root;
1417                 old_generation = tm->generation;
1418                 logical = old_root->logical;
1419         } else {
1420                 logical = eb_root->start;
1421         }
1422
1423         tm = tree_mod_log_search(root->fs_info, logical, time_seq);
1424         if (old_root && tm && tm->op != MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1425                 btrfs_tree_read_unlock(eb_root);
1426                 free_extent_buffer(eb_root);
1427                 old = read_tree_block(root, logical, 0);
1428                 if (WARN_ON(IS_ERR(old) || !extent_buffer_uptodate(old))) {
1429                         if (!IS_ERR(old))
1430                                 free_extent_buffer(old);
1431                         btrfs_warn(root->fs_info,
1432                                 "failed to read tree block %llu from get_old_root", logical);
1433                 } else {
1434                         btrfs_tree_read_lock(old);
1435                         eb = btrfs_clone_extent_buffer(old);
1436                         btrfs_tree_read_unlock(old);
1437                         free_extent_buffer(old);
1438                 }
1439         } else if (old_root) {
1440                 eb_root_owner = btrfs_header_owner(eb_root);
1441                 btrfs_tree_read_unlock(eb_root);
1442                 free_extent_buffer(eb_root);
1443                 eb = alloc_dummy_extent_buffer(root->fs_info, logical);
1444         } else {
1445                 btrfs_set_lock_blocking_rw(eb_root, BTRFS_READ_LOCK);
1446                 eb = btrfs_clone_extent_buffer(eb_root);
1447                 btrfs_tree_read_unlock_blocking(eb_root);
1448                 free_extent_buffer(eb_root);
1449         }
1450
1451         if (!eb)
1452                 return NULL;
1453         if (old_root) {
1454                 btrfs_set_header_bytenr(eb, eb->start);
1455                 btrfs_set_header_backref_rev(eb, BTRFS_MIXED_BACKREF_REV);
1456                 btrfs_set_header_owner(eb, eb_root_owner);
1457                 btrfs_set_header_level(eb, old_root->level);
1458                 btrfs_set_header_generation(eb, old_generation);
1459         }
1460         btrfs_set_buffer_lockdep_class(btrfs_header_owner(eb), eb,
1461                                        btrfs_header_level(eb));
1462         btrfs_tree_read_lock(eb);
1463         if (tm)
1464                 __tree_mod_log_rewind(root->fs_info, eb, time_seq, tm);
1465         else
1466                 WARN_ON(btrfs_header_level(eb) != 0);
1467         WARN_ON(btrfs_header_nritems(eb) > BTRFS_NODEPTRS_PER_BLOCK(root));
1468
1469         return eb;
1470 }
1471
1472 int btrfs_old_root_level(struct btrfs_root *root, u64 time_seq)
1473 {
1474         struct tree_mod_elem *tm;
1475         int level;
1476         struct extent_buffer *eb_root = btrfs_root_node(root);
1477
1478         tm = __tree_mod_log_oldest_root(root->fs_info, eb_root, time_seq);
1479         if (tm && tm->op == MOD_LOG_ROOT_REPLACE) {
1480                 level = tm->old_root.level;
1481         } else {
1482                 level = btrfs_header_level(eb_root);
1483         }
1484         free_extent_buffer(eb_root);
1485
1486         return level;
1487 }
1488
1489 static inline int should_cow_block(struct btrfs_trans_handle *trans,
1490                                    struct btrfs_root *root,
1491                                    struct extent_buffer *buf)
1492 {
1493         if (btrfs_test_is_dummy_root(root))
1494                 return 0;
1495
1496         /* ensure we can see the force_cow */
1497         smp_rmb();
1498
1499         /*
1500          * We do not need to cow a block if
1501          * 1) this block is not created or changed in this transaction;
1502          * 2) this block does not belong to TREE_RELOC tree;
1503          * 3) the root is not forced COW.
1504          *
1505          * What is forced COW:
1506          *    when we create snapshot during commiting the transaction,
1507          *    after we've finished coping src root, we must COW the shared
1508          *    block to ensure the metadata consistency.
1509          */
1510         if (btrfs_header_generation(buf) == trans->transid &&
1511             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
1512             !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
1513               btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) &&
1514             !test_bit(BTRFS_ROOT_FORCE_COW, &root->state))
1515                 return 0;
1516         return 1;
1517 }
1518
1519 /*
1520  * cows a single block, see __btrfs_cow_block for the real work.
1521  * This version of it has extra checks so that a block isn't cow'd more than
1522  * once per transaction, as long as it hasn't been written yet
1523  */
1524 noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
1525                     struct btrfs_root *root, struct extent_buffer *buf,
1526                     struct extent_buffer *parent, int parent_slot,
1527                     struct extent_buffer **cow_ret)
1528 {
1529         u64 search_start;
1530         int ret;
1531
1532         if (trans->transaction != root->fs_info->running_transaction)
1533                 WARN(1, KERN_CRIT "trans %llu running %llu\n",
1534                        trans->transid,
1535                        root->fs_info->running_transaction->transid);
1536
1537         if (trans->transid != root->fs_info->generation)
1538                 WARN(1, KERN_CRIT "trans %llu running %llu\n",
1539                        trans->transid, root->fs_info->generation);
1540
1541         if (!should_cow_block(trans, root, buf)) {
1542                 trans->dirty = true;
1543                 *cow_ret = buf;
1544                 return 0;
1545         }
1546
1547         search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
1548
1549         if (parent)
1550                 btrfs_set_lock_blocking(parent);
1551         btrfs_set_lock_blocking(buf);
1552
1553         ret = __btrfs_cow_block(trans, root, buf, parent,
1554                                  parent_slot, cow_ret, search_start, 0);
1555
1556         trace_btrfs_cow_block(root, buf, *cow_ret);
1557
1558         return ret;
1559 }
1560
1561 /*
1562  * helper function for defrag to decide if two blocks pointed to by a
1563  * node are actually close by
1564  */
1565 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
1566 {
1567         if (blocknr < other && other - (blocknr + blocksize) < 32768)
1568                 return 1;
1569         if (blocknr > other && blocknr - (other + blocksize) < 32768)
1570                 return 1;
1571         return 0;
1572 }
1573
1574 /*
1575  * compare two keys in a memcmp fashion
1576  */
1577 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
1578 {
1579         struct btrfs_key k1;
1580
1581         btrfs_disk_key_to_cpu(&k1, disk);
1582
1583         return btrfs_comp_cpu_keys(&k1, k2);
1584 }
1585
1586 /*
1587  * same as comp_keys only with two btrfs_key's
1588  */
1589 int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
1590 {
1591         if (k1->objectid > k2->objectid)
1592                 return 1;
1593         if (k1->objectid < k2->objectid)
1594                 return -1;
1595         if (k1->type > k2->type)
1596                 return 1;
1597         if (k1->type < k2->type)
1598                 return -1;
1599         if (k1->offset > k2->offset)
1600                 return 1;
1601         if (k1->offset < k2->offset)
1602                 return -1;
1603         return 0;
1604 }
1605
1606 /*
1607  * this is used by the defrag code to go through all the
1608  * leaves pointed to by a node and reallocate them so that
1609  * disk order is close to key order
1610  */
1611 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
1612                        struct btrfs_root *root, struct extent_buffer *parent,
1613                        int start_slot, u64 *last_ret,
1614                        struct btrfs_key *progress)
1615 {
1616         struct extent_buffer *cur;
1617         u64 blocknr;
1618         u64 gen;
1619         u64 search_start = *last_ret;
1620         u64 last_block = 0;
1621         u64 other;
1622         u32 parent_nritems;
1623         int end_slot;
1624         int i;
1625         int err = 0;
1626         int parent_level;
1627         int uptodate;
1628         u32 blocksize;
1629         int progress_passed = 0;
1630         struct btrfs_disk_key disk_key;
1631
1632         parent_level = btrfs_header_level(parent);
1633
1634         WARN_ON(trans->transaction != root->fs_info->running_transaction);
1635         WARN_ON(trans->transid != root->fs_info->generation);
1636
1637         parent_nritems = btrfs_header_nritems(parent);
1638         blocksize = root->nodesize;
1639         end_slot = parent_nritems - 1;
1640
1641         if (parent_nritems <= 1)
1642                 return 0;
1643
1644         btrfs_set_lock_blocking(parent);
1645
1646         for (i = start_slot; i <= end_slot; i++) {
1647                 int close = 1;
1648
1649                 btrfs_node_key(parent, &disk_key, i);
1650                 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
1651                         continue;
1652
1653                 progress_passed = 1;
1654                 blocknr = btrfs_node_blockptr(parent, i);
1655                 gen = btrfs_node_ptr_generation(parent, i);
1656                 if (last_block == 0)
1657                         last_block = blocknr;
1658
1659                 if (i > 0) {
1660                         other = btrfs_node_blockptr(parent, i - 1);
1661                         close = close_blocks(blocknr, other, blocksize);
1662                 }
1663                 if (!close && i < end_slot) {
1664                         other = btrfs_node_blockptr(parent, i + 1);
1665                         close = close_blocks(blocknr, other, blocksize);
1666                 }
1667                 if (close) {
1668                         last_block = blocknr;
1669                         continue;
1670                 }
1671
1672                 cur = btrfs_find_tree_block(root->fs_info, blocknr);
1673                 if (cur)
1674                         uptodate = btrfs_buffer_uptodate(cur, gen, 0);
1675                 else
1676                         uptodate = 0;
1677                 if (!cur || !uptodate) {
1678                         if (!cur) {
1679                                 cur = read_tree_block(root, blocknr, gen);
1680                                 if (IS_ERR(cur)) {
1681                                         return PTR_ERR(cur);
1682                                 } else if (!extent_buffer_uptodate(cur)) {
1683                                         free_extent_buffer(cur);
1684                                         return -EIO;
1685                                 }
1686                         } else if (!uptodate) {
1687                                 err = btrfs_read_buffer(cur, gen);
1688                                 if (err) {
1689                                         free_extent_buffer(cur);
1690                                         return err;
1691                                 }
1692                         }
1693                 }
1694                 if (search_start == 0)
1695                         search_start = last_block;
1696
1697                 btrfs_tree_lock(cur);
1698                 btrfs_set_lock_blocking(cur);
1699                 err = __btrfs_cow_block(trans, root, cur, parent, i,
1700                                         &cur, search_start,
1701                                         min(16 * blocksize,
1702                                             (end_slot - i) * blocksize));
1703                 if (err) {
1704                         btrfs_tree_unlock(cur);
1705                         free_extent_buffer(cur);
1706                         break;
1707                 }
1708                 search_start = cur->start;
1709                 last_block = cur->start;
1710                 *last_ret = search_start;
1711                 btrfs_tree_unlock(cur);
1712                 free_extent_buffer(cur);
1713         }
1714         return err;
1715 }
1716
1717
1718 /*
1719  * search for key in the extent_buffer.  The items start at offset p,
1720  * and they are item_size apart.  There are 'max' items in p.
1721  *
1722  * the slot in the array is returned via slot, and it points to
1723  * the place where you would insert key if it is not found in
1724  * the array.
1725  *
1726  * slot may point to max if the key is bigger than all of the keys
1727  */
1728 static noinline int generic_bin_search(struct extent_buffer *eb,
1729                                        unsigned long p,
1730                                        int item_size, struct btrfs_key *key,
1731                                        int max, int *slot)
1732 {
1733         int low = 0;
1734         int high = max;
1735         int mid;
1736         int ret;
1737         struct btrfs_disk_key *tmp = NULL;
1738         struct btrfs_disk_key unaligned;
1739         unsigned long offset;
1740         char *kaddr = NULL;
1741         unsigned long map_start = 0;
1742         unsigned long map_len = 0;
1743         int err;
1744
1745         while (low < high) {
1746                 mid = (low + high) / 2;
1747                 offset = p + mid * item_size;
1748
1749                 if (!kaddr || offset < map_start ||
1750                     (offset + sizeof(struct btrfs_disk_key)) >
1751                     map_start + map_len) {
1752
1753                         err = map_private_extent_buffer(eb, offset,
1754                                                 sizeof(struct btrfs_disk_key),
1755                                                 &kaddr, &map_start, &map_len);
1756
1757                         if (!err) {
1758                                 tmp = (struct btrfs_disk_key *)(kaddr + offset -
1759                                                         map_start);
1760                         } else {
1761                                 read_extent_buffer(eb, &unaligned,
1762                                                    offset, sizeof(unaligned));
1763                                 tmp = &unaligned;
1764                         }
1765
1766                 } else {
1767                         tmp = (struct btrfs_disk_key *)(kaddr + offset -
1768                                                         map_start);
1769                 }
1770                 ret = comp_keys(tmp, key);
1771
1772                 if (ret < 0)
1773                         low = mid + 1;
1774                 else if (ret > 0)
1775                         high = mid;
1776                 else {
1777                         *slot = mid;
1778                         return 0;
1779                 }
1780         }
1781         *slot = low;
1782         return 1;
1783 }
1784
1785 /*
1786  * simple bin_search frontend that does the right thing for
1787  * leaves vs nodes
1788  */
1789 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
1790                       int level, int *slot)
1791 {
1792         if (level == 0)
1793                 return generic_bin_search(eb,
1794                                           offsetof(struct btrfs_leaf, items),
1795                                           sizeof(struct btrfs_item),
1796                                           key, btrfs_header_nritems(eb),
1797                                           slot);
1798         else
1799                 return generic_bin_search(eb,
1800                                           offsetof(struct btrfs_node, ptrs),
1801                                           sizeof(struct btrfs_key_ptr),
1802                                           key, btrfs_header_nritems(eb),
1803                                           slot);
1804 }
1805
1806 int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
1807                      int level, int *slot)
1808 {
1809         return bin_search(eb, key, level, slot);
1810 }
1811
1812 static void root_add_used(struct btrfs_root *root, u32 size)
1813 {
1814         spin_lock(&root->accounting_lock);
1815         btrfs_set_root_used(&root->root_item,
1816                             btrfs_root_used(&root->root_item) + size);
1817         spin_unlock(&root->accounting_lock);
1818 }
1819
1820 static void root_sub_used(struct btrfs_root *root, u32 size)
1821 {
1822         spin_lock(&root->accounting_lock);
1823         btrfs_set_root_used(&root->root_item,
1824                             btrfs_root_used(&root->root_item) - size);
1825         spin_unlock(&root->accounting_lock);
1826 }
1827
1828 /* given a node and slot number, this reads the blocks it points to.  The
1829  * extent buffer is returned with a reference taken (but unlocked).
1830  * NULL is returned on error.
1831  */
1832 static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
1833                                    struct extent_buffer *parent, int slot)
1834 {
1835         int level = btrfs_header_level(parent);
1836         struct extent_buffer *eb;
1837
1838         if (slot < 0)
1839                 return NULL;
1840         if (slot >= btrfs_header_nritems(parent))
1841                 return NULL;
1842
1843         BUG_ON(level == 0);
1844
1845         eb = read_tree_block(root, btrfs_node_blockptr(parent, slot),
1846                              btrfs_node_ptr_generation(parent, slot));
1847         if (IS_ERR(eb) || !extent_buffer_uptodate(eb)) {
1848                 if (!IS_ERR(eb))
1849                         free_extent_buffer(eb);
1850                 eb = NULL;
1851         }
1852
1853         return eb;
1854 }
1855
1856 /*
1857  * node level balancing, used to make sure nodes are in proper order for
1858  * item deletion.  We balance from the top down, so we have to make sure
1859  * that a deletion won't leave an node completely empty later on.
1860  */
1861 static noinline int balance_level(struct btrfs_trans_handle *trans,
1862                          struct btrfs_root *root,
1863                          struct btrfs_path *path, int level)
1864 {
1865         struct extent_buffer *right = NULL;
1866         struct extent_buffer *mid;
1867         struct extent_buffer *left = NULL;
1868         struct extent_buffer *parent = NULL;
1869         int ret = 0;
1870         int wret;
1871         int pslot;
1872         int orig_slot = path->slots[level];
1873         u64 orig_ptr;
1874
1875         if (level == 0)
1876                 return 0;
1877
1878         mid = path->nodes[level];
1879
1880         WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK &&
1881                 path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING);
1882         WARN_ON(btrfs_header_generation(mid) != trans->transid);
1883
1884         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
1885
1886         if (level < BTRFS_MAX_LEVEL - 1) {
1887                 parent = path->nodes[level + 1];
1888                 pslot = path->slots[level + 1];
1889         }
1890
1891         /*
1892          * deal with the case where there is only one pointer in the root
1893          * by promoting the node below to a root
1894          */
1895         if (!parent) {
1896                 struct extent_buffer *child;
1897
1898                 if (btrfs_header_nritems(mid) != 1)
1899                         return 0;
1900
1901                 /* promote the child to a root */
1902                 child = read_node_slot(root, mid, 0);
1903                 if (!child) {
1904                         ret = -EROFS;
1905                         btrfs_std_error(root->fs_info, ret, NULL);
1906                         goto enospc;
1907                 }
1908
1909                 btrfs_tree_lock(child);
1910                 btrfs_set_lock_blocking(child);
1911                 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
1912                 if (ret) {
1913                         btrfs_tree_unlock(child);
1914                         free_extent_buffer(child);
1915                         goto enospc;
1916                 }
1917
1918                 tree_mod_log_set_root_pointer(root, child, 1);
1919                 rcu_assign_pointer(root->node, child);
1920
1921                 add_root_to_dirty_list(root);
1922                 btrfs_tree_unlock(child);
1923
1924                 path->locks[level] = 0;
1925                 path->nodes[level] = NULL;
1926                 clean_tree_block(trans, root->fs_info, mid);
1927                 btrfs_tree_unlock(mid);
1928                 /* once for the path */
1929                 free_extent_buffer(mid);
1930
1931                 root_sub_used(root, mid->len);
1932                 btrfs_free_tree_block(trans, root, mid, 0, 1);
1933                 /* once for the root ptr */
1934                 free_extent_buffer_stale(mid);
1935                 return 0;
1936         }
1937         if (btrfs_header_nritems(mid) >
1938             BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
1939                 return 0;
1940
1941         left = read_node_slot(root, parent, pslot - 1);
1942         if (left) {
1943                 btrfs_tree_lock(left);
1944                 btrfs_set_lock_blocking(left);
1945                 wret = btrfs_cow_block(trans, root, left,
1946                                        parent, pslot - 1, &left);
1947                 if (wret) {
1948                         ret = wret;
1949                         goto enospc;
1950                 }
1951         }
1952         right = read_node_slot(root, parent, pslot + 1);
1953         if (right) {
1954                 btrfs_tree_lock(right);
1955                 btrfs_set_lock_blocking(right);
1956                 wret = btrfs_cow_block(trans, root, right,
1957                                        parent, pslot + 1, &right);
1958                 if (wret) {
1959                         ret = wret;
1960                         goto enospc;
1961                 }
1962         }
1963
1964         /* first, try to make some room in the middle buffer */
1965         if (left) {
1966                 orig_slot += btrfs_header_nritems(left);
1967                 wret = push_node_left(trans, root, left, mid, 1);
1968                 if (wret < 0)
1969                         ret = wret;
1970         }
1971
1972         /*
1973          * then try to empty the right most buffer into the middle
1974          */
1975         if (right) {
1976                 wret = push_node_left(trans, root, mid, right, 1);
1977                 if (wret < 0 && wret != -ENOSPC)
1978                         ret = wret;
1979                 if (btrfs_header_nritems(right) == 0) {
1980                         clean_tree_block(trans, root->fs_info, right);
1981                         btrfs_tree_unlock(right);
1982                         del_ptr(root, path, level + 1, pslot + 1);
1983                         root_sub_used(root, right->len);
1984                         btrfs_free_tree_block(trans, root, right, 0, 1);
1985                         free_extent_buffer_stale(right);
1986                         right = NULL;
1987                 } else {
1988                         struct btrfs_disk_key right_key;
1989                         btrfs_node_key(right, &right_key, 0);
1990                         tree_mod_log_set_node_key(root->fs_info, parent,
1991                                                   pslot + 1, 0);
1992                         btrfs_set_node_key(parent, &right_key, pslot + 1);
1993                         btrfs_mark_buffer_dirty(parent);
1994                 }
1995         }
1996         if (btrfs_header_nritems(mid) == 1) {
1997                 /*
1998                  * we're not allowed to leave a node with one item in the
1999                  * tree during a delete.  A deletion from lower in the tree
2000                  * could try to delete the only pointer in this node.
2001                  * So, pull some keys from the left.
2002                  * There has to be a left pointer at this point because
2003                  * otherwise we would have pulled some pointers from the
2004                  * right
2005                  */
2006                 if (!left) {
2007                         ret = -EROFS;
2008                         btrfs_std_error(root->fs_info, ret, NULL);
2009                         goto enospc;
2010                 }
2011                 wret = balance_node_right(trans, root, mid, left);
2012                 if (wret < 0) {
2013                         ret = wret;
2014                         goto enospc;
2015                 }
2016                 if (wret == 1) {
2017                         wret = push_node_left(trans, root, left, mid, 1);
2018                         if (wret < 0)
2019                                 ret = wret;
2020                 }
2021                 BUG_ON(wret == 1);
2022         }
2023         if (btrfs_header_nritems(mid) == 0) {
2024                 clean_tree_block(trans, root->fs_info, mid);
2025                 btrfs_tree_unlock(mid);
2026                 del_ptr(root, path, level + 1, pslot);
2027                 root_sub_used(root, mid->len);
2028                 btrfs_free_tree_block(trans, root, mid, 0, 1);
2029                 free_extent_buffer_stale(mid);
2030                 mid = NULL;
2031         } else {
2032                 /* update the parent key to reflect our changes */
2033                 struct btrfs_disk_key mid_key;
2034                 btrfs_node_key(mid, &mid_key, 0);
2035                 tree_mod_log_set_node_key(root->fs_info, parent,
2036                                           pslot, 0);
2037                 btrfs_set_node_key(parent, &mid_key, pslot);
2038                 btrfs_mark_buffer_dirty(parent);
2039         }
2040
2041         /* update the path */
2042         if (left) {
2043                 if (btrfs_header_nritems(left) > orig_slot) {
2044                         extent_buffer_get(left);
2045                         /* left was locked after cow */
2046                         path->nodes[level] = left;
2047                         path->slots[level + 1] -= 1;
2048                         path->slots[level] = orig_slot;
2049                         if (mid) {
2050                                 btrfs_tree_unlock(mid);
2051                                 free_extent_buffer(mid);
2052                         }
2053                 } else {
2054                         orig_slot -= btrfs_header_nritems(left);
2055                         path->slots[level] = orig_slot;
2056                 }
2057         }
2058         /* double check we haven't messed things up */
2059         if (orig_ptr !=
2060             btrfs_node_blockptr(path->nodes[level], path->slots[level]))
2061                 BUG();
2062 enospc:
2063         if (right) {
2064                 btrfs_tree_unlock(right);
2065                 free_extent_buffer(right);
2066         }
2067         if (left) {
2068                 if (path->nodes[level] != left)
2069                         btrfs_tree_unlock(left);
2070                 free_extent_buffer(left);
2071         }
2072         return ret;
2073 }
2074
2075 /* Node balancing for insertion.  Here we only split or push nodes around
2076  * when they are completely full.  This is also done top down, so we
2077  * have to be pessimistic.
2078  */
2079 static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
2080                                           struct btrfs_root *root,
2081                                           struct btrfs_path *path, int level)
2082 {
2083         struct extent_buffer *right = NULL;
2084         struct extent_buffer *mid;
2085         struct extent_buffer *left = NULL;
2086         struct extent_buffer *parent = NULL;
2087         int ret = 0;
2088         int wret;
2089         int pslot;
2090         int orig_slot = path->slots[level];
2091
2092         if (level == 0)
2093                 return 1;
2094
2095         mid = path->nodes[level];
2096         WARN_ON(btrfs_header_generation(mid) != trans->transid);
2097
2098         if (level < BTRFS_MAX_LEVEL - 1) {
2099                 parent = path->nodes[level + 1];
2100                 pslot = path->slots[level + 1];
2101         }
2102
2103         if (!parent)
2104                 return 1;
2105
2106         left = read_node_slot(root, parent, pslot - 1);
2107
2108         /* first, try to make some room in the middle buffer */
2109         if (left) {
2110                 u32 left_nr;
2111
2112                 btrfs_tree_lock(left);
2113                 btrfs_set_lock_blocking(left);
2114
2115                 left_nr = btrfs_header_nritems(left);
2116                 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
2117                         wret = 1;
2118                 } else {
2119                         ret = btrfs_cow_block(trans, root, left, parent,
2120                                               pslot - 1, &left);
2121                         if (ret)
2122                                 wret = 1;
2123                         else {
2124                                 wret = push_node_left(trans, root,
2125                                                       left, mid, 0);
2126                         }
2127                 }
2128                 if (wret < 0)
2129                         ret = wret;
2130                 if (wret == 0) {
2131                         struct btrfs_disk_key disk_key;
2132                         orig_slot += left_nr;
2133                         btrfs_node_key(mid, &disk_key, 0);
2134                         tree_mod_log_set_node_key(root->fs_info, parent,
2135                                                   pslot, 0);
2136                         btrfs_set_node_key(parent, &disk_key, pslot);
2137                         btrfs_mark_buffer_dirty(parent);
2138                         if (btrfs_header_nritems(left) > orig_slot) {
2139                                 path->nodes[level] = left;
2140                                 path->slots[level + 1] -= 1;
2141                                 path->slots[level] = orig_slot;
2142                                 btrfs_tree_unlock(mid);
2143                                 free_extent_buffer(mid);
2144                         } else {
2145                                 orig_slot -=
2146                                         btrfs_header_nritems(left);
2147                                 path->slots[level] = orig_slot;
2148                                 btrfs_tree_unlock(left);
2149                                 free_extent_buffer(left);
2150                         }
2151                         return 0;
2152                 }
2153                 btrfs_tree_unlock(left);
2154                 free_extent_buffer(left);
2155         }
2156         right = read_node_slot(root, parent, pslot + 1);
2157
2158         /*
2159          * then try to empty the right most buffer into the middle
2160          */
2161         if (right) {
2162                 u32 right_nr;
2163
2164                 btrfs_tree_lock(right);
2165                 btrfs_set_lock_blocking(right);
2166
2167                 right_nr = btrfs_header_nritems(right);
2168                 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
2169                         wret = 1;
2170                 } else {
2171                         ret = btrfs_cow_block(trans, root, right,
2172                                               parent, pslot + 1,
2173                                               &right);
2174                         if (ret)
2175                                 wret = 1;
2176                         else {
2177                                 wret = balance_node_right(trans, root,
2178                                                           right, mid);
2179                         }
2180                 }
2181                 if (wret < 0)
2182                         ret = wret;
2183                 if (wret == 0) {
2184                         struct btrfs_disk_key disk_key;
2185
2186                         btrfs_node_key(right, &disk_key, 0);
2187                         tree_mod_log_set_node_key(root->fs_info, parent,
2188                                                   pslot + 1, 0);
2189                         btrfs_set_node_key(parent, &disk_key, pslot + 1);
2190                         btrfs_mark_buffer_dirty(parent);
2191
2192                         if (btrfs_header_nritems(mid) <= orig_slot) {
2193                                 path->nodes[level] = right;
2194                                 path->slots[level + 1] += 1;
2195                                 path->slots[level] = orig_slot -
2196                                         btrfs_header_nritems(mid);
2197                                 btrfs_tree_unlock(mid);
2198                                 free_extent_buffer(mid);
2199                         } else {
2200                                 btrfs_tree_unlock(right);
2201                                 free_extent_buffer(right);
2202                         }
2203                         return 0;
2204                 }
2205                 btrfs_tree_unlock(right);
2206                 free_extent_buffer(right);
2207         }
2208         return 1;
2209 }
2210
2211 /*
2212  * readahead one full node of leaves, finding things that are close
2213  * to the block in 'slot', and triggering ra on them.
2214  */
2215 static void reada_for_search(struct btrfs_root *root,
2216                              struct btrfs_path *path,
2217                              int level, int slot, u64 objectid)
2218 {
2219         struct extent_buffer *node;
2220         struct btrfs_disk_key disk_key;
2221         u32 nritems;
2222         u64 search;
2223         u64 target;
2224         u64 nread = 0;
2225         u64 gen;
2226         int direction = path->reada;
2227         struct extent_buffer *eb;
2228         u32 nr;
2229         u32 blocksize;
2230         u32 nscan = 0;
2231
2232         if (level != 1)
2233                 return;
2234
2235         if (!path->nodes[level])
2236                 return;
2237
2238         node = path->nodes[level];
2239
2240         search = btrfs_node_blockptr(node, slot);
2241         blocksize = root->nodesize;
2242         eb = btrfs_find_tree_block(root->fs_info, search);
2243         if (eb) {
2244                 free_extent_buffer(eb);
2245                 return;
2246         }
2247
2248         target = search;
2249
2250         nritems = btrfs_header_nritems(node);
2251         nr = slot;
2252
2253         while (1) {
2254                 if (direction < 0) {
2255                         if (nr == 0)
2256                                 break;
2257                         nr--;
2258                 } else if (direction > 0) {
2259                         nr++;
2260                         if (nr >= nritems)
2261                                 break;
2262                 }
2263                 if (path->reada < 0 && objectid) {
2264                         btrfs_node_key(node, &disk_key, nr);
2265                         if (btrfs_disk_key_objectid(&disk_key) != objectid)
2266                                 break;
2267                 }
2268                 search = btrfs_node_blockptr(node, nr);
2269                 if ((search <= target && target - search <= 65536) ||
2270                     (search > target && search - target <= 65536)) {
2271                         gen = btrfs_node_ptr_generation(node, nr);
2272                         readahead_tree_block(root, search);
2273                         nread += blocksize;
2274                 }
2275                 nscan++;
2276                 if ((nread > 65536 || nscan > 32))
2277                         break;
2278         }
2279 }
2280
2281 static noinline void reada_for_balance(struct btrfs_root *root,
2282                                        struct btrfs_path *path, int level)
2283 {
2284         int slot;
2285         int nritems;
2286         struct extent_buffer *parent;
2287         struct extent_buffer *eb;
2288         u64 gen;
2289         u64 block1 = 0;
2290         u64 block2 = 0;
2291
2292         parent = path->nodes[level + 1];
2293         if (!parent)
2294                 return;
2295
2296         nritems = btrfs_header_nritems(parent);
2297         slot = path->slots[level + 1];
2298
2299         if (slot > 0) {
2300                 block1 = btrfs_node_blockptr(parent, slot - 1);
2301                 gen = btrfs_node_ptr_generation(parent, slot - 1);
2302                 eb = btrfs_find_tree_block(root->fs_info, block1);
2303                 /*
2304                  * if we get -eagain from btrfs_buffer_uptodate, we
2305                  * don't want to return eagain here.  That will loop
2306                  * forever
2307                  */
2308                 if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
2309                         block1 = 0;
2310                 free_extent_buffer(eb);
2311         }
2312         if (slot + 1 < nritems) {
2313                 block2 = btrfs_node_blockptr(parent, slot + 1);
2314                 gen = btrfs_node_ptr_generation(parent, slot + 1);
2315                 eb = btrfs_find_tree_block(root->fs_info, block2);
2316                 if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
2317                         block2 = 0;
2318                 free_extent_buffer(eb);
2319         }
2320
2321         if (block1)
2322                 readahead_tree_block(root, block1);
2323         if (block2)
2324                 readahead_tree_block(root, block2);
2325 }
2326
2327
2328 /*
2329  * when we walk down the tree, it is usually safe to unlock the higher layers
2330  * in the tree.  The exceptions are when our path goes through slot 0, because
2331  * operations on the tree might require changing key pointers higher up in the
2332  * tree.
2333  *
2334  * callers might also have set path->keep_locks, which tells this code to keep
2335  * the lock if the path points to the last slot in the block.  This is part of
2336  * walking through the tree, and selecting the next slot in the higher block.
2337  *
2338  * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
2339  * if lowest_unlock is 1, level 0 won't be unlocked
2340  */
2341 static noinline void unlock_up(struct btrfs_path *path, int level,
2342                                int lowest_unlock, int min_write_lock_level,
2343                                int *write_lock_level)
2344 {
2345         int i;
2346         int skip_level = level;
2347         int no_skips = 0;
2348         struct extent_buffer *t;
2349
2350         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2351                 if (!path->nodes[i])
2352                         break;
2353                 if (!path->locks[i])
2354                         break;
2355                 if (!no_skips && path->slots[i] == 0) {
2356                         skip_level = i + 1;
2357                         continue;
2358                 }
2359                 if (!no_skips && path->keep_locks) {
2360                         u32 nritems;
2361                         t = path->nodes[i];
2362                         nritems = btrfs_header_nritems(t);
2363                         if (nritems < 1 || path->slots[i] >= nritems - 1) {
2364                                 skip_level = i + 1;
2365                                 continue;
2366                         }
2367                 }
2368                 if (skip_level < i && i >= lowest_unlock)
2369                         no_skips = 1;
2370
2371                 t = path->nodes[i];
2372                 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
2373                         btrfs_tree_unlock_rw(t, path->locks[i]);
2374                         path->locks[i] = 0;
2375                         if (write_lock_level &&
2376                             i > min_write_lock_level &&
2377                             i <= *write_lock_level) {
2378                                 *write_lock_level = i - 1;
2379                         }
2380                 }
2381         }
2382 }
2383
2384 /*
2385  * This releases any locks held in the path starting at level and
2386  * going all the way up to the root.
2387  *
2388  * btrfs_search_slot will keep the lock held on higher nodes in a few
2389  * corner cases, such as COW of the block at slot zero in the node.  This
2390  * ignores those rules, and it should only be called when there are no
2391  * more updates to be done higher up in the tree.
2392  */
2393 noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
2394 {
2395         int i;
2396
2397         if (path->keep_locks)
2398                 return;
2399
2400         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2401                 if (!path->nodes[i])
2402                         continue;
2403                 if (!path->locks[i])
2404                         continue;
2405                 btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]);
2406                 path->locks[i] = 0;
2407         }
2408 }
2409
2410 /*
2411  * helper function for btrfs_search_slot.  The goal is to find a block
2412  * in cache without setting the path to blocking.  If we find the block
2413  * we return zero and the path is unchanged.
2414  *
2415  * If we can't find the block, we set the path blocking and do some
2416  * reada.  -EAGAIN is returned and the search must be repeated.
2417  */
2418 static int
2419 read_block_for_search(struct btrfs_trans_handle *trans,
2420                        struct btrfs_root *root, struct btrfs_path *p,
2421                        struct extent_buffer **eb_ret, int level, int slot,
2422                        struct btrfs_key *key, u64 time_seq)
2423 {
2424         u64 blocknr;
2425         u64 gen;
2426         struct extent_buffer *b = *eb_ret;
2427         struct extent_buffer *tmp;
2428         int ret;
2429
2430         blocknr = btrfs_node_blockptr(b, slot);
2431         gen = btrfs_node_ptr_generation(b, slot);
2432
2433         tmp = btrfs_find_tree_block(root->fs_info, blocknr);
2434         if (tmp) {
2435                 /* first we do an atomic uptodate check */
2436                 if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) {
2437                         *eb_ret = tmp;
2438                         return 0;
2439                 }
2440
2441                 /* the pages were up to date, but we failed
2442                  * the generation number check.  Do a full
2443                  * read for the generation number that is correct.
2444                  * We must do this without dropping locks so
2445                  * we can trust our generation number
2446                  */
2447                 btrfs_set_path_blocking(p);
2448
2449                 /* now we're allowed to do a blocking uptodate check */
2450                 ret = btrfs_read_buffer(tmp, gen);
2451                 if (!ret) {
2452                         *eb_ret = tmp;
2453                         return 0;
2454                 }
2455                 free_extent_buffer(tmp);
2456                 btrfs_release_path(p);
2457                 return -EIO;
2458         }
2459
2460         /*
2461          * reduce lock contention at high levels
2462          * of the btree by dropping locks before
2463          * we read.  Don't release the lock on the current
2464          * level because we need to walk this node to figure
2465          * out which blocks to read.
2466          */
2467         btrfs_unlock_up_safe(p, level + 1);
2468         btrfs_set_path_blocking(p);
2469
2470         free_extent_buffer(tmp);
2471         if (p->reada)
2472                 reada_for_search(root, p, level, slot, key->objectid);
2473
2474         ret = -EAGAIN;
2475         tmp = read_tree_block(root, blocknr, gen);
2476         if (!IS_ERR(tmp)) {
2477                 /*
2478                  * If the read above didn't mark this buffer up to date,
2479                  * it will never end up being up to date.  Set ret to EIO now
2480                  * and give up so that our caller doesn't loop forever
2481                  * on our EAGAINs.
2482                  */
2483                 if (!btrfs_buffer_uptodate(tmp, 0, 0))
2484                         ret = -EIO;
2485                 free_extent_buffer(tmp);
2486         }
2487
2488         btrfs_release_path(p);
2489         return ret;
2490 }
2491
2492 /*
2493  * helper function for btrfs_search_slot.  This does all of the checks
2494  * for node-level blocks and does any balancing required based on
2495  * the ins_len.
2496  *
2497  * If no extra work was required, zero is returned.  If we had to
2498  * drop the path, -EAGAIN is returned and btrfs_search_slot must
2499  * start over
2500  */
2501 static int
2502 setup_nodes_for_search(struct btrfs_trans_handle *trans,
2503                        struct btrfs_root *root, struct btrfs_path *p,
2504                        struct extent_buffer *b, int level, int ins_len,
2505                        int *write_lock_level)
2506 {
2507         int ret;
2508         if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
2509             BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
2510                 int sret;
2511
2512                 if (*write_lock_level < level + 1) {
2513                         *write_lock_level = level + 1;
2514                         btrfs_release_path(p);
2515                         goto again;
2516                 }
2517
2518                 btrfs_set_path_blocking(p);
2519                 reada_for_balance(root, p, level);
2520                 sret = split_node(trans, root, p, level);
2521                 btrfs_clear_path_blocking(p, NULL, 0);
2522
2523                 BUG_ON(sret > 0);
2524                 if (sret) {
2525                         ret = sret;
2526                         goto done;
2527                 }
2528                 b = p->nodes[level];
2529         } else if (ins_len < 0 && btrfs_header_nritems(b) <
2530                    BTRFS_NODEPTRS_PER_BLOCK(root) / 2) {
2531                 int sret;
2532
2533                 if (*write_lock_level < level + 1) {
2534                         *write_lock_level = level + 1;
2535                         btrfs_release_path(p);
2536                         goto again;
2537                 }
2538
2539                 btrfs_set_path_blocking(p);
2540                 reada_for_balance(root, p, level);
2541                 sret = balance_level(trans, root, p, level);
2542                 btrfs_clear_path_blocking(p, NULL, 0);
2543
2544                 if (sret) {
2545                         ret = sret;
2546                         goto done;
2547                 }
2548                 b = p->nodes[level];
2549                 if (!b) {
2550                         btrfs_release_path(p);
2551                         goto again;
2552                 }
2553                 BUG_ON(btrfs_header_nritems(b) == 1);
2554         }
2555         return 0;
2556
2557 again:
2558         ret = -EAGAIN;
2559 done:
2560         return ret;
2561 }
2562
2563 static void key_search_validate(struct extent_buffer *b,
2564                                 struct btrfs_key *key,
2565                                 int level)
2566 {
2567 #ifdef CONFIG_BTRFS_ASSERT
2568         struct btrfs_disk_key disk_key;
2569
2570         btrfs_cpu_key_to_disk(&disk_key, key);
2571
2572         if (level == 0)
2573                 ASSERT(!memcmp_extent_buffer(b, &disk_key,
2574                     offsetof(struct btrfs_leaf, items[0].key),
2575                     sizeof(disk_key)));
2576         else
2577                 ASSERT(!memcmp_extent_buffer(b, &disk_key,
2578                     offsetof(struct btrfs_node, ptrs[0].key),
2579                     sizeof(disk_key)));
2580 #endif
2581 }
2582
2583 static int key_search(struct extent_buffer *b, struct btrfs_key *key,
2584                       int level, int *prev_cmp, int *slot)
2585 {
2586         if (*prev_cmp != 0) {
2587                 *prev_cmp = bin_search(b, key, level, slot);
2588                 return *prev_cmp;
2589         }
2590
2591         key_search_validate(b, key, level);
2592         *slot = 0;
2593
2594         return 0;
2595 }
2596
2597 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
2598                 u64 iobjectid, u64 ioff, u8 key_type,
2599                 struct btrfs_key *found_key)
2600 {
2601         int ret;
2602         struct btrfs_key key;
2603         struct extent_buffer *eb;
2604
2605         ASSERT(path);
2606         ASSERT(found_key);
2607
2608         key.type = key_type;
2609         key.objectid = iobjectid;
2610         key.offset = ioff;
2611
2612         ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
2613         if (ret < 0)
2614                 return ret;
2615
2616         eb = path->nodes[0];
2617         if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
2618                 ret = btrfs_next_leaf(fs_root, path);
2619                 if (ret)
2620                         return ret;
2621                 eb = path->nodes[0];
2622         }
2623
2624         btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
2625         if (found_key->type != key.type ||
2626                         found_key->objectid != key.objectid)
2627                 return 1;
2628
2629         return 0;
2630 }
2631
2632 /*
2633  * look for key in the tree.  path is filled in with nodes along the way
2634  * if key is found, we return zero and you can find the item in the leaf
2635  * level of the path (level 0)
2636  *
2637  * If the key isn't found, the path points to the slot where it should
2638  * be inserted, and 1 is returned.  If there are other errors during the
2639  * search a negative error number is returned.
2640  *
2641  * if ins_len > 0, nodes and leaves will be split as we walk down the
2642  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
2643  * possible)
2644  */
2645 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
2646                       *root, struct btrfs_key *key, struct btrfs_path *p, int
2647                       ins_len, int cow)
2648 {
2649         struct extent_buffer *b;
2650         int slot;
2651         int ret;
2652         int err;
2653         int level;
2654         int lowest_unlock = 1;
2655         int root_lock;
2656         /* everything at write_lock_level or lower must be write locked */
2657         int write_lock_level = 0;
2658         u8 lowest_level = 0;
2659         int min_write_lock_level;
2660         int prev_cmp;
2661
2662         lowest_level = p->lowest_level;
2663         WARN_ON(lowest_level && ins_len > 0);
2664         WARN_ON(p->nodes[0] != NULL);
2665         BUG_ON(!cow && ins_len);
2666
2667         if (ins_len < 0) {
2668                 lowest_unlock = 2;
2669
2670                 /* when we are removing items, we might have to go up to level
2671                  * two as we update tree pointers  Make sure we keep write
2672                  * for those levels as well
2673                  */
2674                 write_lock_level = 2;
2675         } else if (ins_len > 0) {
2676                 /*
2677                  * for inserting items, make sure we have a write lock on
2678                  * level 1 so we can update keys
2679                  */
2680                 write_lock_level = 1;
2681         }
2682
2683         if (!cow)
2684                 write_lock_level = -1;
2685
2686         if (cow && (p->keep_locks || p->lowest_level))
2687                 write_lock_level = BTRFS_MAX_LEVEL;
2688
2689         min_write_lock_level = write_lock_level;
2690
2691 again:
2692         prev_cmp = -1;
2693         /*
2694          * we try very hard to do read locks on the root
2695          */
2696         root_lock = BTRFS_READ_LOCK;
2697         level = 0;
2698         if (p->search_commit_root) {
2699                 /*
2700                  * the commit roots are read only
2701                  * so we always do read locks
2702                  */
2703                 if (p->need_commit_sem)
2704                         down_read(&root->fs_info->commit_root_sem);
2705                 b = root->commit_root;
2706                 extent_buffer_get(b);
2707                 level = btrfs_header_level(b);
2708                 if (p->need_commit_sem)
2709                         up_read(&root->fs_info->commit_root_sem);
2710                 if (!p->skip_locking)
2711                         btrfs_tree_read_lock(b);
2712         } else {
2713                 if (p->skip_locking) {
2714                         b = btrfs_root_node(root);
2715                         level = btrfs_header_level(b);
2716                 } else {
2717                         /* we don't know the level of the root node
2718                          * until we actually have it read locked
2719                          */
2720                         b = btrfs_read_lock_root_node(root);
2721                         level = btrfs_header_level(b);
2722                         if (level <= write_lock_level) {
2723                                 /* whoops, must trade for write lock */
2724                                 btrfs_tree_read_unlock(b);
2725                                 free_extent_buffer(b);
2726                                 b = btrfs_lock_root_node(root);
2727                                 root_lock = BTRFS_WRITE_LOCK;
2728
2729                                 /* the level might have changed, check again */
2730                                 level = btrfs_header_level(b);
2731                         }
2732                 }
2733         }
2734         p->nodes[level] = b;
2735         if (!p->skip_locking)
2736                 p->locks[level] = root_lock;
2737
2738         while (b) {
2739                 level = btrfs_header_level(b);
2740
2741                 /*
2742                  * setup the path here so we can release it under lock
2743                  * contention with the cow code
2744                  */
2745                 if (cow) {
2746                         bool last_level = (level == (BTRFS_MAX_LEVEL - 1));
2747
2748                         /*
2749                          * if we don't really need to cow this block
2750                          * then we don't want to set the path blocking,
2751                          * so we test it here
2752                          */
2753                         if (!should_cow_block(trans, root, b)) {
2754                                 trans->dirty = true;
2755                                 goto cow_done;
2756                         }
2757
2758                         /*
2759                          * must have write locks on this node and the
2760                          * parent
2761                          */
2762                         if (level > write_lock_level ||
2763                             (level + 1 > write_lock_level &&
2764                             level + 1 < BTRFS_MAX_LEVEL &&
2765                             p->nodes[level + 1])) {
2766                                 write_lock_level = level + 1;
2767                                 btrfs_release_path(p);
2768                                 goto again;
2769                         }
2770
2771                         btrfs_set_path_blocking(p);
2772                         if (last_level)
2773                                 err = btrfs_cow_block(trans, root, b, NULL, 0,
2774                                                       &b);
2775                         else
2776                                 err = btrfs_cow_block(trans, root, b,
2777                                                       p->nodes[level + 1],
2778                                                       p->slots[level + 1], &b);
2779                         if (err) {
2780                                 ret = err;
2781                                 goto done;
2782                         }
2783                 }
2784 cow_done:
2785                 p->nodes[level] = b;
2786                 btrfs_clear_path_blocking(p, NULL, 0);
2787
2788                 /*
2789                  * we have a lock on b and as long as we aren't changing
2790                  * the tree, there is no way to for the items in b to change.
2791                  * It is safe to drop the lock on our parent before we
2792                  * go through the expensive btree search on b.
2793                  *
2794                  * If we're inserting or deleting (ins_len != 0), then we might
2795                  * be changing slot zero, which may require changing the parent.
2796                  * So, we can't drop the lock until after we know which slot
2797                  * we're operating on.
2798                  */
2799                 if (!ins_len && !p->keep_locks) {
2800                         int u = level + 1;
2801
2802                         if (u < BTRFS_MAX_LEVEL && p->locks[u]) {
2803                                 btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]);
2804                                 p->locks[u] = 0;
2805                         }
2806                 }
2807
2808                 ret = key_search(b, key, level, &prev_cmp, &slot);
2809
2810                 if (level != 0) {
2811                         int dec = 0;
2812                         if (ret && slot > 0) {
2813                                 dec = 1;
2814                                 slot -= 1;
2815                         }
2816                         p->slots[level] = slot;
2817                         err = setup_nodes_for_search(trans, root, p, b, level,
2818                                              ins_len, &write_lock_level);
2819                         if (err == -EAGAIN)
2820                                 goto again;
2821                         if (err) {
2822                                 ret = err;
2823                                 goto done;
2824                         }
2825                         b = p->nodes[level];
2826                         slot = p->slots[level];
2827
2828                         /*
2829                          * slot 0 is special, if we change the key
2830                          * we have to update the parent pointer
2831                          * which means we must have a write lock
2832                          * on the parent
2833                          */
2834                         if (slot == 0 && ins_len &&
2835                             write_lock_level < level + 1) {
2836                                 write_lock_level = level + 1;
2837                                 btrfs_release_path(p);
2838                                 goto again;
2839                         }
2840
2841                         unlock_up(p, level, lowest_unlock,
2842                                   min_write_lock_level, &write_lock_level);
2843
2844                         if (level == lowest_level) {
2845                                 if (dec)
2846                                         p->slots[level]++;
2847                                 goto done;
2848                         }
2849
2850                         err = read_block_for_search(trans, root, p,
2851                                                     &b, level, slot, key, 0);
2852                         if (err == -EAGAIN)
2853                                 goto again;
2854                         if (err) {
2855                                 ret = err;
2856                                 goto done;
2857                         }
2858
2859                         if (!p->skip_locking) {
2860                                 level = btrfs_header_level(b);
2861                                 if (level <= write_lock_level) {
2862                                         err = btrfs_try_tree_write_lock(b);
2863                                         if (!err) {
2864                                                 btrfs_set_path_blocking(p);
2865                                                 btrfs_tree_lock(b);
2866                                                 btrfs_clear_path_blocking(p, b,
2867                                                                   BTRFS_WRITE_LOCK);
2868                                         }
2869                                         p->locks[level] = BTRFS_WRITE_LOCK;
2870                                 } else {
2871                                         err = btrfs_tree_read_lock_atomic(b);
2872                                         if (!err) {
2873                                                 btrfs_set_path_blocking(p);
2874                                                 btrfs_tree_read_lock(b);
2875                                                 btrfs_clear_path_blocking(p, b,
2876                                                                   BTRFS_READ_LOCK);
2877                                         }
2878                                         p->locks[level] = BTRFS_READ_LOCK;
2879                                 }
2880                                 p->nodes[level] = b;
2881                         }
2882                 } else {
2883                         p->slots[level] = slot;
2884                         if (ins_len > 0 &&
2885                             btrfs_leaf_free_space(root, b) < ins_len) {
2886                                 if (write_lock_level < 1) {
2887                                         write_lock_level = 1;
2888                                         btrfs_release_path(p);
2889                                         goto again;
2890                                 }
2891
2892                                 btrfs_set_path_blocking(p);
2893                                 err = split_leaf(trans, root, key,
2894                                                  p, ins_len, ret == 0);
2895                                 btrfs_clear_path_blocking(p, NULL, 0);
2896
2897                                 BUG_ON(err > 0);
2898                                 if (err) {
2899                                         ret = err;
2900                                         goto done;
2901                                 }
2902                         }
2903                         if (!p->search_for_split)
2904                                 unlock_up(p, level, lowest_unlock,
2905                                           min_write_lock_level, &write_lock_level);
2906                         goto done;
2907                 }
2908         }
2909         ret = 1;
2910 done:
2911         /*
2912          * we don't really know what they plan on doing with the path
2913          * from here on, so for now just mark it as blocking
2914          */
2915         if (!p->leave_spinning)
2916                 btrfs_set_path_blocking(p);
2917         if (ret < 0 && !p->skip_release_on_error)
2918                 btrfs_release_path(p);
2919         return ret;
2920 }
2921
2922 /*
2923  * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2924  * current state of the tree together with the operations recorded in the tree
2925  * modification log to search for the key in a previous version of this tree, as
2926  * denoted by the time_seq parameter.
2927  *
2928  * Naturally, there is no support for insert, delete or cow operations.
2929  *
2930  * The resulting path and return value will be set up as if we called
2931  * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
2932  */
2933 int btrfs_search_old_slot(struct btrfs_root *root, struct btrfs_key *key,
2934                           struct btrfs_path *p, u64 time_seq)
2935 {
2936         struct extent_buffer *b;
2937         int slot;
2938         int ret;
2939         int err;
2940         int level;
2941         int lowest_unlock = 1;
2942         u8 lowest_level = 0;
2943         int prev_cmp = -1;
2944
2945         lowest_level = p->lowest_level;
2946         WARN_ON(p->nodes[0] != NULL);
2947
2948         if (p->search_commit_root) {
2949                 BUG_ON(time_seq);
2950                 return btrfs_search_slot(NULL, root, key, p, 0, 0);
2951         }
2952
2953 again:
2954         b = get_old_root(root, time_seq);
2955         if (!b) {
2956                 ret = -EIO;
2957                 goto done;
2958         }
2959         level = btrfs_header_level(b);
2960         p->locks[level] = BTRFS_READ_LOCK;
2961
2962         while (b) {
2963                 level = btrfs_header_level(b);
2964                 p->nodes[level] = b;
2965                 btrfs_clear_path_blocking(p, NULL, 0);
2966
2967                 /*
2968                  * we have a lock on b and as long as we aren't changing
2969                  * the tree, there is no way to for the items in b to change.
2970                  * It is safe to drop the lock on our parent before we
2971                  * go through the expensive btree search on b.
2972                  */
2973                 btrfs_unlock_up_safe(p, level + 1);
2974
2975                 /*
2976                  * Since we can unwind eb's we want to do a real search every
2977                  * time.
2978                  */
2979                 prev_cmp = -1;
2980                 ret = key_search(b, key, level, &prev_cmp, &slot);
2981
2982                 if (level != 0) {
2983                         int dec = 0;
2984                         if (ret && slot > 0) {
2985                                 dec = 1;
2986                                 slot -= 1;
2987                         }
2988                         p->slots[level] = slot;
2989                         unlock_up(p, level, lowest_unlock, 0, NULL);
2990
2991                         if (level == lowest_level) {
2992                                 if (dec)
2993                                         p->slots[level]++;
2994                                 goto done;
2995                         }
2996
2997                         err = read_block_for_search(NULL, root, p, &b, level,
2998                                                     slot, key, time_seq);
2999                         if (err == -EAGAIN)
3000                                 goto again;
3001                         if (err) {
3002                                 ret = err;
3003                                 goto done;
3004                         }
3005
3006                         level = btrfs_header_level(b);
3007                         err = btrfs_tree_read_lock_atomic(b);
3008                         if (!err) {
3009                                 btrfs_set_path_blocking(p);
3010                                 btrfs_tree_read_lock(b);
3011                                 btrfs_clear_path_blocking(p, b,
3012                                                           BTRFS_READ_LOCK);
3013                         }
3014                         b = tree_mod_log_rewind(root->fs_info, p, b, time_seq);
3015                         if (!b) {
3016                                 ret = -ENOMEM;
3017                                 goto done;
3018                         }
3019                         p->locks[level] = BTRFS_READ_LOCK;
3020                         p->nodes[level] = b;
3021                 } else {
3022                         p->slots[level] = slot;
3023                         unlock_up(p, level, lowest_unlock, 0, NULL);
3024                         goto done;
3025                 }
3026         }
3027         ret = 1;
3028 done:
3029         if (!p->leave_spinning)
3030                 btrfs_set_path_blocking(p);
3031         if (ret < 0)
3032                 btrfs_release_path(p);
3033
3034         return ret;
3035 }
3036
3037 /*
3038  * helper to use instead of search slot if no exact match is needed but
3039  * instead the next or previous item should be returned.
3040  * When find_higher is true, the next higher item is returned, the next lower
3041  * otherwise.
3042  * When return_any and find_higher are both true, and no higher item is found,
3043  * return the next lower instead.
3044  * When return_any is true and find_higher is false, and no lower item is found,
3045  * return the next higher instead.
3046  * It returns 0 if any item is found, 1 if none is found (tree empty), and
3047  * < 0 on error
3048  */
3049 int btrfs_search_slot_for_read(struct btrfs_root *root,
3050                                struct btrfs_key *key, struct btrfs_path *p,
3051                                int find_higher, int return_any)
3052 {
3053         int ret;
3054         struct extent_buffer *leaf;
3055
3056 again:
3057         ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
3058         if (ret <= 0)
3059                 return ret;
3060         /*
3061          * a return value of 1 means the path is at the position where the
3062          * item should be inserted. Normally this is the next bigger item,
3063          * but in case the previous item is the last in a leaf, path points
3064          * to the first free slot in the previous leaf, i.e. at an invalid
3065          * item.
3066          */
3067         leaf = p->nodes[0];
3068
3069         if (find_higher) {
3070                 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
3071                         ret = btrfs_next_leaf(root, p);
3072                         if (ret <= 0)
3073                                 return ret;
3074                         if (!return_any)
3075                                 return 1;
3076                         /*
3077                          * no higher item found, return the next
3078                          * lower instead
3079                          */
3080                         return_any = 0;
3081                         find_higher = 0;
3082                         btrfs_release_path(p);
3083                         goto again;
3084                 }
3085         } else {
3086                 if (p->slots[0] == 0) {
3087                         ret = btrfs_prev_leaf(root, p);
3088                         if (ret < 0)
3089                                 return ret;
3090                         if (!ret) {
3091                                 leaf = p->nodes[0];
3092                                 if (p->slots[0] == btrfs_header_nritems(leaf))
3093                                         p->slots[0]--;
3094                                 return 0;
3095                         }
3096                         if (!return_any)
3097                                 return 1;
3098                         /*
3099                          * no lower item found, return the next
3100                          * higher instead
3101                          */
3102                         return_any = 0;
3103                         find_higher = 1;
3104                         btrfs_release_path(p);
3105                         goto again;
3106                 } else {
3107                         --p->slots[0];
3108                 }
3109         }
3110         return 0;
3111 }
3112
3113 /*
3114  * adjust the pointers going up the tree, starting at level
3115  * making sure the right key of each node is points to 'key'.
3116  * This is used after shifting pointers to the left, so it stops
3117  * fixing up pointers when a given leaf/node is not in slot 0 of the
3118  * higher levels
3119  *
3120  */
3121 static void fixup_low_keys(struct btrfs_fs_info *fs_info,
3122                            struct btrfs_path *path,
3123                            struct btrfs_disk_key *key, int level)
3124 {
3125         int i;
3126         struct extent_buffer *t;
3127
3128         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
3129                 int tslot = path->slots[i];
3130                 if (!path->nodes[i])
3131                         break;
3132                 t = path->nodes[i];
3133                 tree_mod_log_set_node_key(fs_info, t, tslot, 1);
3134                 btrfs_set_node_key(t, key, tslot);
3135                 btrfs_mark_buffer_dirty(path->nodes[i]);
3136                 if (tslot != 0)
3137                         break;
3138         }
3139 }
3140
3141 /*
3142  * update item key.
3143  *
3144  * This function isn't completely safe. It's the caller's responsibility
3145  * that the new key won't break the order
3146  */
3147 void btrfs_set_item_key_safe(struct btrfs_fs_info *fs_info,
3148                              struct btrfs_path *path,
3149                              struct btrfs_key *new_key)
3150 {
3151         struct btrfs_disk_key disk_key;
3152         struct extent_buffer *eb;
3153         int slot;
3154
3155         eb = path->nodes[0];
3156         slot = path->slots[0];
3157         if (slot > 0) {
3158                 btrfs_item_key(eb, &disk_key, slot - 1);
3159                 BUG_ON(comp_keys(&disk_key, new_key) >= 0);
3160         }
3161         if (slot < btrfs_header_nritems(eb) - 1) {
3162                 btrfs_item_key(eb, &disk_key, slot + 1);
3163                 BUG_ON(comp_keys(&disk_key, new_key) <= 0);
3164         }
3165
3166         btrfs_cpu_key_to_disk(&disk_key, new_key);
3167         btrfs_set_item_key(eb, &disk_key, slot);
3168         btrfs_mark_buffer_dirty(eb);
3169         if (slot == 0)
3170                 fixup_low_keys(fs_info, path, &disk_key, 1);
3171 }
3172
3173 /*
3174  * try to push data from one node into the next node left in the
3175  * tree.
3176  *
3177  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
3178  * error, and > 0 if there was no room in the left hand block.
3179  */
3180 static int push_node_left(struct btrfs_trans_handle *trans,
3181                           struct btrfs_root *root, struct extent_buffer *dst,
3182                           struct extent_buffer *src, int empty)
3183 {
3184         int push_items = 0;
3185         int src_nritems;
3186         int dst_nritems;
3187         int ret = 0;
3188
3189         src_nritems = btrfs_header_nritems(src);
3190         dst_nritems = btrfs_header_nritems(dst);
3191         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
3192         WARN_ON(btrfs_header_generation(src) != trans->transid);
3193         WARN_ON(btrfs_header_generation(dst) != trans->transid);
3194
3195         if (!empty && src_nritems <= 8)
3196                 return 1;
3197
3198         if (push_items <= 0)
3199                 return 1;
3200
3201         if (empty) {
3202                 push_items = min(src_nritems, push_items);
3203                 if (push_items < src_nritems) {
3204                         /* leave at least 8 pointers in the node if
3205                          * we aren't going to empty it
3206                          */
3207                         if (src_nritems - push_items < 8) {
3208                                 if (push_items <= 8)
3209                                         return 1;
3210                                 push_items -= 8;
3211                         }
3212                 }
3213         } else
3214                 push_items = min(src_nritems - 8, push_items);
3215
3216         ret = tree_mod_log_eb_copy(root->fs_info, dst, src, dst_nritems, 0,
3217                                    push_items);
3218         if (ret) {
3219                 btrfs_abort_transaction(trans, root, ret);
3220                 return ret;
3221         }
3222         copy_extent_buffer(dst, src,
3223                            btrfs_node_key_ptr_offset(dst_nritems),
3224                            btrfs_node_key_ptr_offset(0),
3225                            push_items * sizeof(struct btrfs_key_ptr));
3226
3227         if (push_items < src_nritems) {
3228                 /*
3229                  * don't call tree_mod_log_eb_move here, key removal was already
3230                  * fully logged by tree_mod_log_eb_copy above.
3231                  */
3232                 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
3233                                       btrfs_node_key_ptr_offset(push_items),
3234                                       (src_nritems - push_items) *
3235                                       sizeof(struct btrfs_key_ptr));
3236         }
3237         btrfs_set_header_nritems(src, src_nritems - push_items);
3238         btrfs_set_header_nritems(dst, dst_nritems + push_items);
3239         btrfs_mark_buffer_dirty(src);
3240         btrfs_mark_buffer_dirty(dst);
3241
3242         return ret;
3243 }
3244
3245 /*
3246  * try to push data from one node into the next node right in the
3247  * tree.
3248  *
3249  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
3250  * error, and > 0 if there was no room in the right hand block.
3251  *
3252  * this will  only push up to 1/2 the contents of the left node over
3253  */
3254 static int balance_node_right(struct btrfs_trans_handle *trans,
3255                               struct btrfs_root *root,
3256                               struct extent_buffer *dst,
3257                               struct extent_buffer *src)
3258 {
3259         int push_items = 0;
3260         int max_push;
3261         int src_nritems;
3262         int dst_nritems;
3263         int ret = 0;
3264
3265         WARN_ON(btrfs_header_generation(src) != trans->transid);
3266         WARN_ON(btrfs_header_generation(dst) != trans->transid);
3267
3268         src_nritems = btrfs_header_nritems(src);
3269         dst_nritems = btrfs_header_nritems(dst);
3270         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
3271         if (push_items <= 0)
3272                 return 1;
3273
3274         if (src_nritems < 4)
3275                 return 1;
3276
3277         max_push = src_nritems / 2 + 1;
3278         /* don't try to empty the node */
3279         if (max_push >= src_nritems)
3280                 return 1;
3281
3282         if (max_push < push_items)
3283                 push_items = max_push;
3284
3285         tree_mod_log_eb_move(root->fs_info, dst, push_items, 0, dst_nritems);
3286         memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
3287                                       btrfs_node_key_ptr_offset(0),
3288                                       (dst_nritems) *
3289                                       sizeof(struct btrfs_key_ptr));
3290
3291         ret = tree_mod_log_eb_copy(root->fs_info, dst, src, 0,
3292                                    src_nritems - push_items, push_items);
3293         if (ret) {
3294                 btrfs_abort_transaction(trans, root, ret);
3295                 return ret;
3296         }
3297         copy_extent_buffer(dst, src,
3298                            btrfs_node_key_ptr_offset(0),
3299                            btrfs_node_key_ptr_offset(src_nritems - push_items),
3300                            push_items * sizeof(struct btrfs_key_ptr));
3301
3302         btrfs_set_header_nritems(src, src_nritems - push_items);
3303         btrfs_set_header_nritems(dst, dst_nritems + push_items);
3304
3305         btrfs_mark_buffer_dirty(src);
3306         btrfs_mark_buffer_dirty(dst);
3307
3308         return ret;
3309 }
3310
3311 /*
3312  * helper function to insert a new root level in the tree.
3313  * A new node is allocated, and a single item is inserted to
3314  * point to the existing root
3315  *
3316  * returns zero on success or < 0 on failure.
3317  */
3318 static noinline int insert_new_root(struct btrfs_trans_handle *trans,
3319                            struct btrfs_root *root,
3320                            struct btrfs_path *path, int level)
3321 {
3322         u64 lower_gen;
3323         struct extent_buffer *lower;
3324         struct extent_buffer *c;
3325         struct extent_buffer *old;
3326         struct btrfs_disk_key lower_key;
3327
3328         BUG_ON(path->nodes[level]);
3329         BUG_ON(path->nodes[level-1] != root->node);
3330
3331         lower = path->nodes[level-1];
3332         if (level == 1)
3333                 btrfs_item_key(lower, &lower_key, 0);
3334         else
3335                 btrfs_node_key(lower, &lower_key, 0);
3336
3337         c = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid,
3338                                    &lower_key, level, root->node->start, 0);
3339         if (IS_ERR(c))
3340                 return PTR_ERR(c);
3341
3342         root_add_used(root, root->nodesize);
3343
3344         memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
3345         btrfs_set_header_nritems(c, 1);
3346         btrfs_set_header_level(c, level);
3347         btrfs_set_header_bytenr(c, c->start);
3348         btrfs_set_header_generation(c, trans->transid);
3349         btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
3350         btrfs_set_header_owner(c, root->root_key.objectid);
3351
3352         write_extent_buffer(c, root->fs_info->fsid, btrfs_header_fsid(),
3353                             BTRFS_FSID_SIZE);
3354
3355         write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
3356                             btrfs_header_chunk_tree_uuid(c), BTRFS_UUID_SIZE);
3357
3358         btrfs_set_node_key(c, &lower_key, 0);
3359         btrfs_set_node_blockptr(c, 0, lower->start);
3360         lower_gen = btrfs_header_generation(lower);
3361         WARN_ON(lower_gen != trans->transid);
3362
3363         btrfs_set_node_ptr_generation(c, 0, lower_gen);
3364
3365         btrfs_mark_buffer_dirty(c);
3366
3367         old = root->node;
3368         tree_mod_log_set_root_pointer(root, c, 0);
3369         rcu_assign_pointer(root->node, c);
3370
3371         /* the super has an extra ref to root->node */
3372         free_extent_buffer(old);
3373
3374         add_root_to_dirty_list(root);
3375         extent_buffer_get(c);
3376         path->nodes[level] = c;
3377         path->locks[level] = BTRFS_WRITE_LOCK_BLOCKING;
3378         path->slots[level] = 0;
3379         return 0;
3380 }
3381
3382 /*
3383  * worker function to insert a single pointer in a node.
3384  * the node should have enough room for the pointer already
3385  *
3386  * slot and level indicate where you want the key to go, and
3387  * blocknr is the block the key points to.
3388  */
3389 static void insert_ptr(struct btrfs_trans_handle *trans,
3390                        struct btrfs_root *root, struct btrfs_path *path,
3391                        struct btrfs_disk_key *key, u64 bytenr,
3392                        int slot, int level)
3393 {
3394         struct extent_buffer *lower;
3395         int nritems;
3396         int ret;
3397
3398         BUG_ON(!path->nodes[level]);
3399         btrfs_assert_tree_locked(path->nodes[level]);
3400         lower = path->nodes[level];
3401         nritems = btrfs_header_nritems(lower);
3402         BUG_ON(slot > nritems);
3403         BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(root));
3404         if (slot != nritems) {
3405                 if (level)
3406                         tree_mod_log_eb_move(root->fs_info, lower, slot + 1,
3407                                              slot, nritems - slot);
3408                 memmove_extent_buffer(lower,
3409                               btrfs_node_key_ptr_offset(slot + 1),
3410                               btrfs_node_key_ptr_offset(slot),
3411                               (nritems - slot) * sizeof(struct btrfs_key_ptr));
3412         }
3413         if (level) {
3414                 ret = tree_mod_log_insert_key(root->fs_info, lower, slot,
3415                                               MOD_LOG_KEY_ADD, GFP_NOFS);
3416                 BUG_ON(ret < 0);
3417         }
3418         btrfs_set_node_key(lower, key, slot);
3419         btrfs_set_node_blockptr(lower, slot, bytenr);
3420         WARN_ON(trans->transid == 0);
3421         btrfs_set_node_ptr_generation(lower, slot, trans->transid);
3422         btrfs_set_header_nritems(lower, nritems + 1);
3423         btrfs_mark_buffer_dirty(lower);
3424 }
3425
3426 /*
3427  * split the node at the specified level in path in two.
3428  * The path is corrected to point to the appropriate node after the split
3429  *
3430  * Before splitting this tries to make some room in the node by pushing
3431  * left and right, if either one works, it returns right away.
3432  *
3433  * returns 0 on success and < 0 on failure
3434  */
3435 static noinline int split_node(struct btrfs_trans_handle *trans,
3436                                struct btrfs_root *root,
3437                                struct btrfs_path *path, int level)
3438 {
3439         struct extent_buffer *c;
3440         struct extent_buffer *split;
3441         struct btrfs_disk_key disk_key;
3442         int mid;
3443         int ret;
3444         u32 c_nritems;
3445
3446         c = path->nodes[level];
3447         WARN_ON(btrfs_header_generation(c) != trans->transid);
3448         if (c == root->node) {
3449                 /*
3450                  * trying to split the root, lets make a new one
3451                  *
3452                  * tree mod log: We don't log_removal old root in
3453                  * insert_new_root, because that root buffer will be kept as a
3454                  * normal node. We are going to log removal of half of the
3455                  * elements below with tree_mod_log_eb_copy. We're holding a
3456                  * tree lock on the buffer, which is why we cannot race with
3457                  * other tree_mod_log users.
3458                  */
3459                 ret = insert_new_root(trans, root, path, level + 1);
3460                 if (ret)
3461                         return ret;
3462         } else {
3463                 ret = push_nodes_for_insert(trans, root, path, level);
3464                 c = path->nodes[level];
3465                 if (!ret && btrfs_header_nritems(c) <
3466                     BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
3467                         return 0;
3468                 if (ret < 0)
3469                         return ret;
3470         }
3471
3472         c_nritems = btrfs_header_nritems(c);
3473         mid = (c_nritems + 1) / 2;
3474         btrfs_node_key(c, &disk_key, mid);
3475
3476         split = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid,
3477                         &disk_key, level, c->start, 0);
3478         if (IS_ERR(split))
3479                 return PTR_ERR(split);
3480
3481         root_add_used(root, root->nodesize);
3482
3483         memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
3484         btrfs_set_header_level(split, btrfs_header_level(c));
3485         btrfs_set_header_bytenr(split, split->start);
3486         btrfs_set_header_generation(split, trans->transid);
3487         btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
3488         btrfs_set_header_owner(split, root->root_key.objectid);
3489         write_extent_buffer(split, root->fs_info->fsid,
3490                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
3491         write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
3492                             btrfs_header_chunk_tree_uuid(split),
3493                             BTRFS_UUID_SIZE);
3494
3495         ret = tree_mod_log_eb_copy(root->fs_info, split, c, 0,
3496                                    mid, c_nritems - mid);
3497         if (ret) {
3498                 btrfs_abort_transaction(trans, root, ret);
3499                 return ret;
3500         }
3501         copy_extent_buffer(split, c,
3502                            btrfs_node_key_ptr_offset(0),
3503                            btrfs_node_key_ptr_offset(mid),
3504                            (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
3505         btrfs_set_header_nritems(split, c_nritems - mid);
3506         btrfs_set_header_nritems(c, mid);
3507         ret = 0;
3508
3509         btrfs_mark_buffer_dirty(c);
3510         btrfs_mark_buffer_dirty(split);
3511
3512         insert_ptr(trans, root, path, &disk_key, split->start,
3513                    path->slots[level + 1] + 1, level + 1);
3514
3515         if (path->slots[level] >= mid) {
3516                 path->slots[level] -= mid;
3517                 btrfs_tree_unlock(c);
3518                 free_extent_buffer(c);
3519                 path->nodes[level] = split;
3520                 path->slots[level + 1] += 1;
3521         } else {
3522                 btrfs_tree_unlock(split);
3523                 free_extent_buffer(split);
3524         }
3525         return ret;
3526 }
3527
3528 /*
3529  * how many bytes are required to store the items in a leaf.  start
3530  * and nr indicate which items in the leaf to check.  This totals up the
3531  * space used both by the item structs and the item data
3532  */
3533 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
3534 {
3535         struct btrfs_item *start_item;
3536         struct btrfs_item *end_item;
3537         struct btrfs_map_token token;
3538         int data_len;
3539         int nritems = btrfs_header_nritems(l);
3540         int end = min(nritems, start + nr) - 1;
3541
3542         if (!nr)
3543                 return 0;
3544         btrfs_init_map_token(&token);
3545         start_item = btrfs_item_nr(start);
3546         end_item = btrfs_item_nr(end);
3547         data_len = btrfs_token_item_offset(l, start_item, &token) +
3548                 btrfs_token_item_size(l, start_item, &token);
3549         data_len = data_len - btrfs_token_item_offset(l, end_item, &token);
3550         data_len += sizeof(struct btrfs_item) * nr;
3551         WARN_ON(data_len < 0);
3552         return data_len;
3553 }
3554
3555 /*
3556  * The space between the end of the leaf items and
3557  * the start of the leaf data.  IOW, how much room
3558  * the leaf has left for both items and data
3559  */
3560 noinline int btrfs_leaf_free_space(struct btrfs_root *root,
3561                                    struct extent_buffer *leaf)
3562 {
3563         int nritems = btrfs_header_nritems(leaf);
3564         int ret;
3565         ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
3566         if (ret < 0) {
3567                 btrfs_crit(root->fs_info,
3568                         "leaf free space ret %d, leaf data size %lu, used %d nritems %d",
3569                        ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
3570                        leaf_space_used(leaf, 0, nritems), nritems);
3571         }
3572         return ret;
3573 }
3574
3575 /*
3576  * min slot controls the lowest index we're willing to push to the
3577  * right.  We'll push up to and including min_slot, but no lower
3578  */
3579 static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
3580                                       struct btrfs_root *root,
3581                                       struct btrfs_path *path,
3582                                       int data_size, int empty,
3583                                       struct extent_buffer *right,
3584                                       int free_space, u32 left_nritems,
3585                                       u32 min_slot)
3586 {
3587         struct extent_buffer *left = path->nodes[0];
3588         struct extent_buffer *upper = path->nodes[1];
3589         struct btrfs_map_token token;
3590         struct btrfs_disk_key disk_key;
3591         int slot;
3592         u32 i;
3593         int push_space = 0;
3594         int push_items = 0;
3595         struct btrfs_item *item;
3596         u32 nr;
3597         u32 right_nritems;
3598         u32 data_end;
3599         u32 this_item_size;
3600
3601         btrfs_init_map_token(&token);
3602
3603         if (empty)
3604                 nr = 0;
3605         else
3606                 nr = max_t(u32, 1, min_slot);
3607
3608         if (path->slots[0] >= left_nritems)
3609                 push_space += data_size;
3610
3611         slot = path->slots[1];
3612         i = left_nritems - 1;
3613         while (i >= nr) {
3614                 item = btrfs_item_nr(i);
3615
3616                 if (!empty && push_items > 0) {
3617                         if (path->slots[0] > i)
3618                                 break;
3619                         if (path->slots[0] == i) {
3620                                 int space = btrfs_leaf_free_space(root, left);
3621                                 if (space + push_space * 2 > free_space)
3622                                         break;
3623                         }
3624                 }
3625
3626                 if (path->slots[0] == i)
3627                         push_space += data_size;
3628
3629                 this_item_size = btrfs_item_size(left, item);
3630                 if (this_item_size + sizeof(*item) + push_space > free_space)
3631                         break;
3632
3633                 push_items++;
3634                 push_space += this_item_size + sizeof(*item);
3635                 if (i == 0)
3636                         break;
3637                 i--;
3638         }
3639
3640         if (push_items == 0)
3641                 goto out_unlock;
3642
3643         WARN_ON(!empty && push_items == left_nritems);
3644
3645         /* push left to right */
3646         right_nritems = btrfs_header_nritems(right);
3647
3648         push_space = btrfs_item_end_nr(left, left_nritems - push_items);
3649         push_space -= leaf_data_end(root, left);
3650
3651         /* make room in the right data area */
3652         data_end = leaf_data_end(root, right);
3653         memmove_extent_buffer(right,
3654                               btrfs_leaf_data(right) + data_end - push_space,
3655                               btrfs_leaf_data(right) + data_end,
3656                               BTRFS_LEAF_DATA_SIZE(root) - data_end);
3657
3658         /* copy from the left data area */
3659         copy_extent_buffer(right, left, btrfs_leaf_data(right) +
3660                      BTRFS_LEAF_DATA_SIZE(root) - push_space,
3661                      btrfs_leaf_data(left) + leaf_data_end(root, left),
3662                      push_space);
3663
3664         memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
3665                               btrfs_item_nr_offset(0),
3666                               right_nritems * sizeof(struct btrfs_item));
3667
3668         /* copy the items from left to right */
3669         copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
3670                    btrfs_item_nr_offset(left_nritems - push_items),
3671                    push_items * sizeof(struct btrfs_item));
3672
3673         /* update the item pointers */
3674         right_nritems += push_items;
3675         btrfs_set_header_nritems(right, right_nritems);
3676         push_space = BTRFS_LEAF_DATA_SIZE(root);
3677         for (i = 0; i < right_nritems; i++) {
3678                 item = btrfs_item_nr(i);
3679                 push_space -= btrfs_token_item_size(right, item, &token);
3680                 btrfs_set_token_item_offset(right, item, push_space, &token);
3681         }
3682
3683         left_nritems -= push_items;
3684         btrfs_set_header_nritems(left, left_nritems);
3685
3686         if (left_nritems)
3687                 btrfs_mark_buffer_dirty(left);
3688         else
3689                 clean_tree_block(trans, root->fs_info, left);
3690
3691         btrfs_mark_buffer_dirty(right);
3692
3693         btrfs_item_key(right, &disk_key, 0);
3694         btrfs_set_node_key(upper, &disk_key, slot + 1);
3695         btrfs_mark_buffer_dirty(upper);
3696
3697         /* then fixup the leaf pointer in the path */
3698         if (path->slots[0] >= left_nritems) {
3699                 path->slots[0] -= left_nritems;
3700                 if (btrfs_header_nritems(path->nodes[0]) == 0)
3701                         clean_tree_block(trans, root->fs_info, path->nodes[0]);
3702                 btrfs_tree_unlock(path->nodes[0]);
3703                 free_extent_buffer(path->nodes[0]);
3704                 path->nodes[0] = right;
3705                 path->slots[1] += 1;
3706         } else {
3707                 btrfs_tree_unlock(right);
3708                 free_extent_buffer(right);
3709         }
3710         return 0;
3711
3712 out_unlock:
3713         btrfs_tree_unlock(right);
3714         free_extent_buffer(right);
3715         return 1;
3716 }
3717
3718 /*
3719  * push some data in the path leaf to the right, trying to free up at
3720  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
3721  *
3722  * returns 1 if the push failed because the other node didn't have enough
3723  * room, 0 if everything worked out and < 0 if there were major errors.
3724  *
3725  * this will push starting from min_slot to the end of the leaf.  It won't
3726  * push any slot lower than min_slot
3727  */
3728 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
3729                            *root, struct btrfs_path *path,
3730                            int min_data_size, int data_size,
3731                            int empty, u32 min_slot)
3732 {
3733         struct extent_buffer *left = path->nodes[0];
3734         struct extent_buffer *right;
3735         struct extent_buffer *upper;
3736         int slot;
3737         int free_space;
3738         u32 left_nritems;
3739         int ret;
3740
3741         if (!path->nodes[1])
3742                 return 1;
3743
3744         slot = path->slots[1];
3745         upper = path->nodes[1];
3746         if (slot >= btrfs_header_nritems(upper) - 1)
3747                 return 1;
3748
3749         btrfs_assert_tree_locked(path->nodes[1]);
3750
3751         right = read_node_slot(root, upper, slot + 1);
3752         if (right == NULL)
3753                 return 1;
3754
3755         btrfs_tree_lock(right);
3756         btrfs_set_lock_blocking(right);
3757
3758         free_space = btrfs_leaf_free_space(root, right);
3759         if (free_space < data_size)
3760                 goto out_unlock;
3761
3762         /* cow and double check */
3763         ret = btrfs_cow_block(trans, root, right, upper,
3764                               slot + 1, &right);
3765         if (ret)
3766                 goto out_unlock;
3767
3768         free_space = btrfs_leaf_free_space(root, right);
3769         if (free_space < data_size)
3770                 goto out_unlock;
3771
3772         left_nritems = btrfs_header_nritems(left);
3773         if (left_nritems == 0)
3774                 goto out_unlock;
3775
3776         if (path->slots[0] == left_nritems && !empty) {
3777                 /* Key greater than all keys in the leaf, right neighbor has
3778                  * enough room for it and we're not emptying our leaf to delete
3779                  * it, therefore use right neighbor to insert the new item and
3780                  * no need to touch/dirty our left leaft. */
3781                 btrfs_tree_unlock(left);
3782                 free_extent_buffer(left);
3783                 path->nodes[0] = right;
3784                 path->slots[0] = 0;
3785                 path->slots[1]++;
3786                 return 0;
3787         }
3788
3789         return __push_leaf_right(trans, root, path, min_data_size, empty,
3790                                 right, free_space, left_nritems, min_slot);
3791 out_unlock:
3792         btrfs_tree_unlock(right);
3793         free_extent_buffer(right);
3794         return 1;
3795 }
3796
3797 /*
3798  * push some data in the path leaf to the left, trying to free up at
3799  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
3800  *
3801  * max_slot can put a limit on how far into the leaf we'll push items.  The
3802  * item at 'max_slot' won't be touched.  Use (u32)-1 to make us do all the
3803  * items
3804  */
3805 static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
3806                                      struct btrfs_root *root,
3807                                      struct btrfs_path *path, int data_size,
3808                                      int empty, struct extent_buffer *left,
3809                                      int free_space, u32 right_nritems,
3810                                      u32 max_slot)
3811 {
3812         struct btrfs_disk_key disk_key;
3813         struct extent_buffer *right = path->nodes[0];
3814         int i;
3815         int push_space = 0;
3816         int push_items = 0;
3817         struct btrfs_item *item;
3818         u32 old_left_nritems;
3819         u32 nr;
3820         int ret = 0;
3821         u32 this_item_size;
3822         u32 old_left_item_size;
3823         struct btrfs_map_token token;
3824
3825         btrfs_init_map_token(&token);
3826
3827         if (empty)
3828                 nr = min(right_nritems, max_slot);
3829         else
3830                 nr = min(right_nritems - 1, max_slot);
3831
3832         for (i = 0; i < nr; i++) {
3833                 item = btrfs_item_nr(i);
3834
3835                 if (!empty && push_items > 0) {
3836                         if (path->slots[0] < i)
3837                                 break;
3838                         if (path->slots[0] == i) {
3839                                 int space = btrfs_leaf_free_space(root, right);
3840                                 if (space + push_space * 2 > free_space)
3841                                         break;
3842                         }
3843                 }
3844
3845                 if (path->slots[0] == i)
3846                         push_space += data_size;
3847
3848                 this_item_size = btrfs_item_size(right, item);
3849                 if (this_item_size + sizeof(*item) + push_space > free_space)
3850                         break;
3851
3852                 push_items++;
3853                 push_space += this_item_size + sizeof(*item);
3854         }
3855
3856         if (push_items == 0) {
3857                 ret = 1;
3858                 goto out;
3859         }
3860         WARN_ON(!empty && push_items == btrfs_header_nritems(right));
3861
3862         /* push data from right to left */
3863         copy_extent_buffer(left, right,
3864                            btrfs_item_nr_offset(btrfs_header_nritems(left)),
3865                            btrfs_item_nr_offset(0),
3866                            push_items * sizeof(struct btrfs_item));
3867
3868         push_space = BTRFS_LEAF_DATA_SIZE(root) -
3869                      btrfs_item_offset_nr(right, push_items - 1);
3870
3871         copy_extent_buffer(left, right, btrfs_leaf_data(left) +
3872                      leaf_data_end(root, left) - push_space,
3873                      btrfs_leaf_data(right) +
3874                      btrfs_item_offset_nr(right, push_items - 1),
3875                      push_space);
3876         old_left_nritems = btrfs_header_nritems(left);
3877         BUG_ON(old_left_nritems <= 0);
3878
3879         old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
3880         for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
3881                 u32 ioff;
3882
3883                 item = btrfs_item_nr(i);
3884
3885                 ioff = btrfs_token_item_offset(left, item, &token);
3886                 btrfs_set_token_item_offset(left, item,
3887                       ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size),
3888                       &token);
3889         }
3890         btrfs_set_header_nritems(left, old_left_nritems + push_items);
3891
3892         /* fixup right node */
3893         if (push_items > right_nritems)
3894                 WARN(1, KERN_CRIT "push items %d nr %u\n", push_items,
3895                        right_nritems);
3896
3897         if (push_items < right_nritems) {
3898                 push_space = btrfs_item_offset_nr(right, push_items - 1) -
3899                                                   leaf_data_end(root, right);
3900                 memmove_extent_buffer(right, btrfs_leaf_data(right) +
3901                                       BTRFS_LEAF_DATA_SIZE(root) - push_space,
3902                                       btrfs_leaf_data(right) +
3903                                       leaf_data_end(root, right), push_space);
3904
3905                 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
3906                               btrfs_item_nr_offset(push_items),
3907                              (btrfs_header_nritems(right) - push_items) *
3908                              sizeof(struct btrfs_item));
3909         }
3910         right_nritems -= push_items;
3911         btrfs_set_header_nritems(right, right_nritems);
3912         push_space = BTRFS_LEAF_DATA_SIZE(root);
3913         for (i = 0; i < right_nritems; i++) {
3914                 item = btrfs_item_nr(i);
3915
3916                 push_space = push_space - btrfs_token_item_size(right,
3917                                                                 item, &token);
3918                 btrfs_set_token_item_offset(right, item, push_space, &token);
3919         }
3920
3921         btrfs_mark_buffer_dirty(left);
3922         if (right_nritems)
3923                 btrfs_mark_buffer_dirty(right);
3924         else
3925                 clean_tree_block(trans, root->fs_info, right);
3926
3927         btrfs_item_key(right, &disk_key, 0);
3928         fixup_low_keys(root->fs_info, path, &disk_key, 1);
3929
3930         /* then fixup the leaf pointer in the path */
3931         if (path->slots[0] < push_items) {
3932                 path->slots[0] += old_left_nritems;
3933                 btrfs_tree_unlock(path->nodes[0]);
3934                 free_extent_buffer(path->nodes[0]);
3935                 path->nodes[0] = left;
3936                 path->slots[1] -= 1;
3937         } else {
3938                 btrfs_tree_unlock(left);
3939                 free_extent_buffer(left);
3940                 path->slots[0] -= push_items;
3941         }
3942         BUG_ON(path->slots[0] < 0);
3943         return ret;
3944 out:
3945         btrfs_tree_unlock(left);
3946         free_extent_buffer(left);
3947         return ret;
3948 }
3949
3950 /*
3951  * push some data in the path leaf to the left, trying to free up at
3952  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
3953  *
3954  * max_slot can put a limit on how far into the leaf we'll push items.  The
3955  * item at 'max_slot' won't be touched.  Use (u32)-1 to make us push all the
3956  * items
3957  */
3958 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
3959                           *root, struct btrfs_path *path, int min_data_size,
3960                           int data_size, int empty, u32 max_slot)
3961 {
3962         struct extent_buffer *right = path->nodes[0];
3963         struct extent_buffer *left;
3964         int slot;
3965         int free_space;
3966         u32 right_nritems;
3967         int ret = 0;
3968
3969         slot = path->slots[1];
3970         if (slot == 0)
3971                 return 1;
3972         if (!path->nodes[1])
3973                 return 1;
3974
3975         right_nritems = btrfs_header_nritems(right);
3976         if (right_nritems == 0)
3977                 return 1;
3978
3979         btrfs_assert_tree_locked(path->nodes[1]);
3980
3981         left = read_node_slot(root, path->nodes[1], slot - 1);
3982         if (left == NULL)
3983                 return 1;
3984
3985         btrfs_tree_lock(left);
3986         btrfs_set_lock_blocking(left);
3987
3988         free_space = btrfs_leaf_free_space(root, left);
3989         if (free_space < data_size) {
3990                 ret = 1;
3991                 goto out;
3992         }
3993
3994         /* cow and double check */
3995         ret = btrfs_cow_block(trans, root, left,
3996                               path->nodes[1], slot - 1, &left);
3997         if (ret) {
3998                 /* we hit -ENOSPC, but it isn't fatal here */
3999                 if (ret == -ENOSPC)
4000                         ret = 1;
4001                 goto out;
4002         }
4003
4004         free_space = btrfs_leaf_free_space(root, left);
4005         if (free_space < data_size) {
4006                 ret = 1;
4007                 goto out;
4008         }
4009
4010         return __push_leaf_left(trans, root, path, min_data_size,
4011                                empty, left, free_space, right_nritems,
4012                                max_slot);
4013 out:
4014         btrfs_tree_unlock(left);
4015         free_extent_buffer(left);
4016         return ret;
4017 }
4018
4019 /*
4020  * split the path's leaf in two, making sure there is at least data_size
4021  * available for the resulting leaf level of the path.
4022  */
4023 static noinline void copy_for_split(struct btrfs_trans_handle *trans,
4024                                     struct btrfs_root *root,
4025                                     struct btrfs_path *path,
4026                                     struct extent_buffer *l,
4027                                     struct extent_buffer *right,
4028                                     int slot, int mid, int nritems)
4029 {
4030         int data_copy_size;
4031         int rt_data_off;
4032         int i;
4033         struct btrfs_disk_key disk_key;
4034         struct btrfs_map_token token;
4035
4036         btrfs_init_map_token(&token);
4037
4038         nritems = nritems - mid;
4039         btrfs_set_header_nritems(right, nritems);
4040         data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
4041
4042         copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
4043                            btrfs_item_nr_offset(mid),
4044                            nritems * sizeof(struct btrfs_item));
4045
4046         copy_extent_buffer(right, l,
4047                      btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
4048                      data_copy_size, btrfs_leaf_data(l) +
4049                      leaf_data_end(root, l), data_copy_size);
4050
4051         rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
4052                       btrfs_item_end_nr(l, mid);
4053
4054         for (i = 0; i < nritems; i++) {
4055                 struct btrfs_item *item = btrfs_item_nr(i);
4056                 u32 ioff;
4057
4058                 ioff = btrfs_token_item_offset(right, item, &token);
4059                 btrfs_set_token_item_offset(right, item,
4060                                             ioff + rt_data_off, &token);
4061         }
4062
4063         btrfs_set_header_nritems(l, mid);
4064         btrfs_item_key(right, &disk_key, 0);
4065         insert_ptr(trans, root, path, &disk_key, right->start,
4066                    path->slots[1] + 1, 1);
4067
4068         btrfs_mark_buffer_dirty(right);
4069         btrfs_mark_buffer_dirty(l);
4070         BUG_ON(path->slots[0] != slot);
4071
4072         if (mid <= slot) {
4073                 btrfs_tree_unlock(path->nodes[0]);
4074                 free_extent_buffer(path->nodes[0]);
4075                 path->nodes[0] = right;
4076                 path->slots[0] -= mid;
4077                 path->slots[1] += 1;
4078         } else {
4079                 btrfs_tree_unlock(right);
4080                 free_extent_buffer(right);
4081         }
4082
4083         BUG_ON(path->slots[0] < 0);
4084 }
4085
4086 /*
4087  * double splits happen when we need to insert a big item in the middle
4088  * of a leaf.  A double split can leave us with 3 mostly empty leaves:
4089  * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
4090  *          A                 B                 C
4091  *
4092  * We avoid this by trying to push the items on either side of our target
4093  * into the adjacent leaves.  If all goes well we can avoid the double split
4094  * completely.
4095  */
4096 static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
4097                                           struct btrfs_root *root,
4098                                           struct btrfs_path *path,
4099                                           int data_size)
4100 {
4101         int ret;
4102         int progress = 0;
4103         int slot;
4104         u32 nritems;
4105         int space_needed = data_size;
4106
4107         slot = path->slots[0];
4108         if (slot < btrfs_header_nritems(path->nodes[0]))
4109                 space_needed -= btrfs_leaf_free_space(root, path->nodes[0]);
4110
4111         /*
4112          * try to push all the items after our slot into the
4113          * right leaf
4114          */
4115         ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot);
4116         if (ret < 0)
4117                 return ret;
4118
4119         if (ret == 0)
4120                 progress++;
4121
4122         nritems = btrfs_header_nritems(path->nodes[0]);
4123         /*
4124          * our goal is to get our slot at the start or end of a leaf.  If
4125          * we've done so we're done
4126          */
4127         if (path->slots[0] == 0 || path->slots[0] == nritems)
4128                 return 0;
4129
4130         if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
4131                 return 0;
4132
4133         /* try to push all the items before our slot into the next leaf */
4134         slot = path->slots[0];
4135         ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
4136         if (ret < 0)
4137                 return ret;
4138
4139         if (ret == 0)
4140                 progress++;
4141
4142         if (progress)
4143                 return 0;
4144         return 1;
4145 }
4146
4147 /*
4148  * split the path's leaf in two, making sure there is at least data_size
4149  * available for the resulting leaf level of the path.
4150  *
4151  * returns 0 if all went well and < 0 on failure.
4152  */
4153 static noinline int split_leaf(struct btrfs_trans_handle *trans,
4154                                struct btrfs_root *root,
4155                                struct btrfs_key *ins_key,
4156                                struct btrfs_path *path, int data_size,
4157                                int extend)
4158 {
4159         struct btrfs_disk_key disk_key;
4160         struct extent_buffer *l;
4161         u32 nritems;
4162         int mid;
4163         int slot;
4164         struct extent_buffer *right;
4165         struct btrfs_fs_info *fs_info = root->fs_info;
4166         int ret = 0;
4167         int wret;
4168         int split;
4169         int num_doubles = 0;
4170         int tried_avoid_double = 0;
4171
4172         l = path->nodes[0];
4173         slot = path->slots[0];
4174         if (extend && data_size + btrfs_item_size_nr(l, slot) +
4175             sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root))
4176                 return -EOVERFLOW;
4177
4178         /* first try to make some room by pushing left and right */
4179         if (data_size && path->nodes[1]) {
4180                 int space_needed = data_size;
4181
4182                 if (slot < btrfs_header_nritems(l))
4183                         space_needed -= btrfs_leaf_free_space(root, l);
4184
4185                 wret = push_leaf_right(trans, root, path, space_needed,
4186                                        space_needed, 0, 0);
4187                 if (wret < 0)
4188                         return wret;
4189                 if (wret) {
4190                         wret = push_leaf_left(trans, root, path, space_needed,
4191                                               space_needed, 0, (u32)-1);
4192                         if (wret < 0)
4193                                 return wret;
4194                 }
4195                 l = path->nodes[0];
4196
4197                 /* did the pushes work? */
4198                 if (btrfs_leaf_free_space(root, l) >= data_size)
4199                         return 0;
4200         }
4201
4202         if (!path->nodes[1]) {
4203                 ret = insert_new_root(trans, root, path, 1);
4204                 if (ret)
4205                         return ret;
4206         }
4207 again:
4208         split = 1;
4209         l = path->nodes[0];
4210         slot = path->slots[0];
4211         nritems = btrfs_header_nritems(l);
4212         mid = (nritems + 1) / 2;
4213
4214         if (mid <= slot) {
4215                 if (nritems == 1 ||
4216                     leaf_space_used(l, mid, nritems - mid) + data_size >
4217                         BTRFS_LEAF_DATA_SIZE(root)) {
4218                         if (slot >= nritems) {
4219                                 split = 0;
4220                         } else {
4221                                 mid = slot;
4222                                 if (mid != nritems &&
4223                                     leaf_space_used(l, mid, nritems - mid) +
4224                                     data_size > BTRFS_LEAF_DATA_SIZE(root)) {
4225                                         if (data_size && !tried_avoid_double)
4226                                                 goto push_for_double;
4227                                         split = 2;
4228                                 }
4229                         }
4230                 }
4231         } else {
4232                 if (leaf_space_used(l, 0, mid) + data_size >
4233                         BTRFS_LEAF_DATA_SIZE(root)) {
4234                         if (!extend && data_size && slot == 0) {
4235                                 split = 0;
4236                         } else if ((extend || !data_size) && slot == 0) {
4237                                 mid = 1;
4238                         } else {
4239                                 mid = slot;
4240                                 if (mid != nritems &&
4241                                     leaf_space_used(l, mid, nritems - mid) +
4242                                     data_size > BTRFS_LEAF_DATA_SIZE(root)) {
4243                                         if (data_size && !tried_avoid_double)
4244                                                 goto push_for_double;
4245                                         split = 2;
4246                                 }
4247                         }
4248                 }
4249         }
4250
4251         if (split == 0)
4252                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
4253         else
4254                 btrfs_item_key(l, &disk_key, mid);
4255
4256         right = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid,
4257                         &disk_key, 0, l->start, 0);
4258         if (IS_ERR(right))
4259                 return PTR_ERR(right);
4260
4261         root_add_used(root, root->nodesize);
4262
4263         memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
4264         btrfs_set_header_bytenr(right, right->start);
4265         btrfs_set_header_generation(right, trans->transid);
4266         btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
4267         btrfs_set_header_owner(right, root->root_key.objectid);
4268         btrfs_set_header_level(right, 0);
4269         write_extent_buffer(right, fs_info->fsid,
4270                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
4271
4272         write_extent_buffer(right, fs_info->chunk_tree_uuid,
4273                             btrfs_header_chunk_tree_uuid(right),
4274                             BTRFS_UUID_SIZE);
4275
4276         if (split == 0) {
4277                 if (mid <= slot) {
4278                         btrfs_set_header_nritems(right, 0);
4279                         insert_ptr(trans, root, path, &disk_key, right->start,
4280                                    path->slots[1] + 1, 1);
4281                         btrfs_tree_unlock(path->nodes[0]);
4282                         free_extent_buffer(path->nodes[0]);
4283                         path->nodes[0] = right;
4284                         path->slots[0] = 0;
4285                         path->slots[1] += 1;
4286                 } else {
4287                         btrfs_set_header_nritems(right, 0);
4288                         insert_ptr(trans, root, path, &disk_key, right->start,
4289                                           path->slots[1], 1);
4290                         btrfs_tree_unlock(path->nodes[0]);
4291                         free_extent_buffer(path->nodes[0]);
4292                         path->nodes[0] = right;
4293                         path->slots[0] = 0;
4294                         if (path->slots[1] == 0)
4295                                 fixup_low_keys(fs_info, path, &disk_key, 1);
4296                 }
4297                 btrfs_mark_buffer_dirty(right);
4298                 return ret;
4299         }
4300
4301         copy_for_split(trans, root, path, l, right, slot, mid, nritems);
4302
4303         if (split == 2) {
4304                 BUG_ON(num_doubles != 0);
4305                 num_doubles++;
4306                 goto again;
4307         }
4308
4309         return 0;
4310
4311 push_for_double:
4312         push_for_double_split(trans, root, path, data_size);
4313         tried_avoid_double = 1;
4314         if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
4315                 return 0;
4316         goto again;
4317 }
4318
4319 static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
4320                                          struct btrfs_root *root,
4321                                          struct btrfs_path *path, int ins_len)
4322 {
4323         struct btrfs_key key;
4324         struct extent_buffer *leaf;
4325         struct btrfs_file_extent_item *fi;
4326         u64 extent_len = 0;
4327         u32 item_size;
4328         int ret;
4329
4330         leaf = path->nodes[0];
4331         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4332
4333         BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
4334                key.type != BTRFS_EXTENT_CSUM_KEY);
4335
4336         if (btrfs_leaf_free_space(root, leaf) >= ins_len)
4337                 return 0;
4338
4339         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4340         if (key.type == BTRFS_EXTENT_DATA_KEY) {
4341                 fi = btrfs_item_ptr(leaf, path->slots[0],
4342                                     struct btrfs_file_extent_item);
4343                 extent_len = btrfs_file_extent_num_bytes(leaf, fi);
4344         }
4345         btrfs_release_path(path);
4346
4347         path->keep_locks = 1;
4348         path->search_for_split = 1;
4349         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
4350         path->search_for_split = 0;
4351         if (ret > 0)
4352                 ret = -EAGAIN;
4353         if (ret < 0)
4354                 goto err;
4355
4356         ret = -EAGAIN;
4357         leaf = path->nodes[0];
4358         /* if our item isn't there, return now */
4359         if (item_size != btrfs_item_size_nr(leaf, path->slots[0]))
4360                 goto err;
4361
4362         /* the leaf has  changed, it now has room.  return now */
4363         if (btrfs_leaf_free_space(root, path->nodes[0]) >= ins_len)
4364                 goto err;
4365
4366         if (key.type == BTRFS_EXTENT_DATA_KEY) {
4367                 fi = btrfs_item_ptr(leaf, path->slots[0],
4368                                     struct btrfs_file_extent_item);
4369                 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
4370                         goto err;
4371         }
4372
4373         btrfs_set_path_blocking(path);
4374         ret = split_leaf(trans, root, &key, path, ins_len, 1);
4375         if (ret)
4376                 goto err;
4377
4378         path->keep_locks = 0;
4379         btrfs_unlock_up_safe(path, 1);
4380         return 0;
4381 err:
4382         path->keep_locks = 0;
4383         return ret;
4384 }
4385
4386 static noinline int split_item(struct btrfs_trans_handle *trans,
4387                                struct btrfs_root *root,
4388                                struct btrfs_path *path,
4389                                struct btrfs_key *new_key,
4390                                unsigned long split_offset)
4391 {
4392         struct extent_buffer *leaf;
4393         struct btrfs_item *item;
4394         struct btrfs_item *new_item;
4395         int slot;
4396         char *buf;
4397         u32 nritems;
4398         u32 item_size;
4399         u32 orig_offset;
4400         struct btrfs_disk_key disk_key;
4401
4402         leaf = path->nodes[0];
4403         BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
4404
4405         btrfs_set_path_blocking(path);
4406
4407         item = btrfs_item_nr(path->slots[0]);
4408         orig_offset = btrfs_item_offset(leaf, item);
4409         item_size = btrfs_item_size(leaf, item);
4410
4411         buf = kmalloc(item_size, GFP_NOFS);
4412         if (!buf)
4413                 return -ENOMEM;
4414
4415         read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
4416                             path->slots[0]), item_size);
4417
4418         slot = path->slots[0] + 1;
4419         nritems = btrfs_header_nritems(leaf);
4420         if (slot != nritems) {
4421                 /* shift the items */
4422                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
4423                                 btrfs_item_nr_offset(slot),
4424                                 (nritems - slot) * sizeof(struct btrfs_item));
4425         }
4426
4427         btrfs_cpu_key_to_disk(&disk_key, new_key);
4428         btrfs_set_item_key(leaf, &disk_key, slot);
4429
4430         new_item = btrfs_item_nr(slot);
4431
4432         btrfs_set_item_offset(leaf, new_item, orig_offset);
4433         btrfs_set_item_size(leaf, new_item, item_size - split_offset);
4434
4435         btrfs_set_item_offset(leaf, item,
4436                               orig_offset + item_size - split_offset);
4437         btrfs_set_item_size(leaf, item, split_offset);
4438
4439         btrfs_set_header_nritems(leaf, nritems + 1);
4440
4441         /* write the data for the start of the original item */
4442         write_extent_buffer(leaf, buf,
4443                             btrfs_item_ptr_offset(leaf, path->slots[0]),
4444                             split_offset);
4445
4446         /* write the data for the new item */
4447         write_extent_buffer(leaf, buf + split_offset,
4448                             btrfs_item_ptr_offset(leaf, slot),
4449                             item_size - split_offset);
4450         btrfs_mark_buffer_dirty(leaf);
4451
4452         BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
4453         kfree(buf);
4454         return 0;
4455 }
4456
4457 /*
4458  * This function splits a single item into two items,
4459  * giving 'new_key' to the new item and splitting the
4460  * old one at split_offset (from the start of the item).
4461  *
4462  * The path may be released by this operation.  After
4463  * the split, the path is pointing to the old item.  The
4464  * new item is going to be in the same node as the old one.
4465  *
4466  * Note, the item being split must be smaller enough to live alone on
4467  * a tree block with room for one extra struct btrfs_item
4468  *
4469  * This allows us to split the item in place, keeping a lock on the
4470  * leaf the entire time.
4471  */
4472 int btrfs_split_item(struct btrfs_trans_handle *trans,
4473                      struct btrfs_root *root,
4474                      struct btrfs_path *path,
4475                      struct btrfs_key *new_key,
4476                      unsigned long split_offset)
4477 {
4478         int ret;
4479         ret = setup_leaf_for_split(trans, root, path,
4480                                    sizeof(struct btrfs_item));
4481         if (ret)
4482                 return ret;
4483
4484         ret = split_item(trans, root, path, new_key, split_offset);
4485         return ret;
4486 }
4487
4488 /*
4489  * This function duplicate a item, giving 'new_key' to the new item.
4490  * It guarantees both items live in the same tree leaf and the new item
4491  * is contiguous with the original item.
4492  *
4493  * This allows us to split file extent in place, keeping a lock on the
4494  * leaf the entire time.
4495  */
4496 int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
4497                          struct btrfs_root *root,
4498                          struct btrfs_path *path,
4499                          struct btrfs_key *new_key)
4500 {
4501         struct extent_buffer *leaf;
4502         int ret;
4503         u32 item_size;
4504
4505         leaf = path->nodes[0];
4506         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4507         ret = setup_leaf_for_split(trans, root, path,
4508                                    item_size + sizeof(struct btrfs_item));
4509         if (ret)
4510                 return ret;
4511
4512         path->slots[0]++;
4513         setup_items_for_insert(root, path, new_key, &item_size,
4514                                item_size, item_size +
4515                                sizeof(struct btrfs_item), 1);
4516         leaf = path->nodes[0];
4517         memcpy_extent_buffer(leaf,
4518                              btrfs_item_ptr_offset(leaf, path->slots[0]),
4519                              btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4520                              item_size);
4521         return 0;
4522 }
4523
4524 /*
4525  * make the item pointed to by the path smaller.  new_size indicates
4526  * how small to make it, and from_end tells us if we just chop bytes
4527  * off the end of the item or if we shift the item to chop bytes off
4528  * the front.
4529  */
4530 void btrfs_truncate_item(struct btrfs_root *root, struct btrfs_path *path,
4531                          u32 new_size, int from_end)
4532 {
4533         int slot;
4534         struct extent_buffer *leaf;
4535         struct btrfs_item *item;
4536         u32 nritems;
4537         unsigned int data_end;
4538         unsigned int old_data_start;
4539         unsigned int old_size;
4540         unsigned int size_diff;
4541         int i;
4542         struct btrfs_map_token token;
4543
4544         btrfs_init_map_token(&token);
4545
4546         leaf = path->nodes[0];
4547         slot = path->slots[0];
4548
4549         old_size = btrfs_item_size_nr(leaf, slot);
4550         if (old_size == new_size)
4551                 return;
4552
4553         nritems = btrfs_header_nritems(leaf);
4554         data_end = leaf_data_end(root, leaf);
4555
4556         old_data_start = btrfs_item_offset_nr(leaf, slot);
4557
4558         size_diff = old_size - new_size;
4559
4560         BUG_ON(slot < 0);
4561         BUG_ON(slot >= nritems);
4562
4563         /*
4564          * item0..itemN ... dataN.offset..dataN.size .. data0.size
4565          */
4566         /* first correct the data pointers */
4567         for (i = slot; i < nritems; i++) {
4568                 u32 ioff;
4569                 item = btrfs_item_nr(i);
4570
4571                 ioff = btrfs_token_item_offset(leaf, item, &token);
4572                 btrfs_set_token_item_offset(leaf, item,
4573                                             ioff + size_diff, &token);
4574         }
4575
4576         /* shift the data */
4577         if (from_end) {
4578                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
4579                               data_end + size_diff, btrfs_leaf_data(leaf) +
4580                               data_end, old_data_start + new_size - data_end);
4581         } else {
4582                 struct btrfs_disk_key disk_key;
4583                 u64 offset;
4584
4585                 btrfs_item_key(leaf, &disk_key, slot);
4586
4587                 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
4588                         unsigned long ptr;
4589                         struct btrfs_file_extent_item *fi;
4590
4591                         fi = btrfs_item_ptr(leaf, slot,
4592                                             struct btrfs_file_extent_item);
4593                         fi = (struct btrfs_file_extent_item *)(
4594                              (unsigned long)fi - size_diff);
4595
4596                         if (btrfs_file_extent_type(leaf, fi) ==
4597                             BTRFS_FILE_EXTENT_INLINE) {
4598                                 ptr = btrfs_item_ptr_offset(leaf, slot);
4599                                 memmove_extent_buffer(leaf, ptr,
4600                                       (unsigned long)fi,
4601                                       BTRFS_FILE_EXTENT_INLINE_DATA_START);
4602                         }
4603                 }
4604
4605                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
4606                               data_end + size_diff, btrfs_leaf_data(leaf) +
4607                               data_end, old_data_start - data_end);
4608
4609                 offset = btrfs_disk_key_offset(&disk_key);
4610                 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
4611                 btrfs_set_item_key(leaf, &disk_key, slot);
4612                 if (slot == 0)
4613                         fixup_low_keys(root->fs_info, path, &disk_key, 1);
4614         }
4615
4616         item = btrfs_item_nr(slot);
4617         btrfs_set_item_size(leaf, item, new_size);
4618         btrfs_mark_buffer_dirty(leaf);
4619
4620         if (btrfs_leaf_free_space(root, leaf) < 0) {
4621                 btrfs_print_leaf(root, leaf);
4622                 BUG();
4623         }
4624 }
4625
4626 /*
4627  * make the item pointed to by the path bigger, data_size is the added size.
4628  */
4629 void btrfs_extend_item(struct btrfs_root *root, struct btrfs_path *path,
4630                        u32 data_size)
4631 {
4632         int slot;
4633         struct extent_buffer *leaf;
4634         struct btrfs_item *item;
4635         u32 nritems;
4636         unsigned int data_end;
4637         unsigned int old_data;
4638         unsigned int old_size;
4639         int i;
4640         struct btrfs_map_token token;
4641
4642         btrfs_init_map_token(&token);
4643
4644         leaf = path->nodes[0];
4645
4646         nritems = btrfs_header_nritems(leaf);
4647         data_end = leaf_data_end(root, leaf);
4648
4649         if (btrfs_leaf_free_space(root, leaf) < data_size) {
4650                 btrfs_print_leaf(root, leaf);
4651                 BUG();
4652         }
4653         slot = path->slots[0];
4654         old_data = btrfs_item_end_nr(leaf, slot);
4655
4656         BUG_ON(slot < 0);
4657         if (slot >= nritems) {
4658                 btrfs_print_leaf(root, leaf);
4659                 btrfs_crit(root->fs_info, "slot %d too large, nritems %d",
4660                        slot, nritems);
4661                 BUG_ON(1);
4662         }
4663
4664         /*
4665          * item0..itemN ... dataN.offset..dataN.size .. data0.size
4666          */
4667         /* first correct the data pointers */
4668         for (i = slot; i < nritems; i++) {
4669                 u32 ioff;
4670                 item = btrfs_item_nr(i);
4671
4672                 ioff = btrfs_token_item_offset(leaf, item, &token);
4673                 btrfs_set_token_item_offset(leaf, item,
4674                                             ioff - data_size, &token);
4675         }
4676
4677         /* shift the data */
4678         memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
4679                       data_end - data_size, btrfs_leaf_data(leaf) +
4680                       data_end, old_data - data_end);
4681
4682         data_end = old_data;
4683         old_size = btrfs_item_size_nr(leaf, slot);
4684         item = btrfs_item_nr(slot);
4685         btrfs_set_item_size(leaf, item, old_size + data_size);
4686         btrfs_mark_buffer_dirty(leaf);
4687
4688         if (btrfs_leaf_free_space(root, leaf) < 0) {
4689                 btrfs_print_leaf(root, leaf);
4690                 BUG();
4691         }
4692 }
4693
4694 /*
4695  * this is a helper for btrfs_insert_empty_items, the main goal here is
4696  * to save stack depth by doing the bulk of the work in a function
4697  * that doesn't call btrfs_search_slot
4698  */
4699 void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path,
4700                             struct btrfs_key *cpu_key, u32 *data_size,
4701                             u32 total_data, u32 total_size, int nr)
4702 {
4703         struct btrfs_item *item;
4704         int i;
4705         u32 nritems;
4706         unsigned int data_end;
4707         struct btrfs_disk_key disk_key;
4708         struct extent_buffer *leaf;
4709         int slot;
4710         struct btrfs_map_token token;
4711
4712         if (path->slots[0] == 0) {
4713                 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
4714                 fixup_low_keys(root->fs_info, path, &disk_key, 1);
4715         }
4716         btrfs_unlock_up_safe(path, 1);
4717
4718         btrfs_init_map_token(&token);
4719
4720         leaf = path->nodes[0];
4721         slot = path->slots[0];
4722
4723         nritems = btrfs_header_nritems(leaf);
4724         data_end = leaf_data_end(root, leaf);
4725
4726         if (btrfs_leaf_free_space(root, leaf) < total_size) {
4727                 btrfs_print_leaf(root, leaf);
4728                 btrfs_crit(root->fs_info, "not enough freespace need %u have %d",
4729                        total_size, btrfs_leaf_free_space(root, leaf));
4730                 BUG();
4731         }
4732
4733         if (slot != nritems) {
4734                 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
4735
4736                 if (old_data < data_end) {
4737                         btrfs_print_leaf(root, leaf);
4738                         btrfs_crit(root->fs_info, "slot %d old_data %d data_end %d",
4739                                slot, old_data, data_end);
4740                         BUG_ON(1);
4741                 }
4742                 /*
4743                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
4744                  */
4745                 /* first correct the data pointers */
4746                 for (i = slot; i < nritems; i++) {
4747                         u32 ioff;
4748
4749                         item = btrfs_item_nr( i);
4750                         ioff = btrfs_token_item_offset(leaf, item, &token);
4751                         btrfs_set_token_item_offset(leaf, item,
4752                                                     ioff - total_data, &token);
4753                 }
4754                 /* shift the items */
4755                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
4756                               btrfs_item_nr_offset(slot),
4757                               (nritems - slot) * sizeof(struct btrfs_item));
4758
4759                 /* shift the data */
4760                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
4761                               data_end - total_data, btrfs_leaf_data(leaf) +
4762                               data_end, old_data - data_end);
4763                 data_end = old_data;
4764         }
4765
4766         /* setup the item for the new data */
4767         for (i = 0; i < nr; i++) {
4768                 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
4769                 btrfs_set_item_key(leaf, &disk_key, slot + i);
4770                 item = btrfs_item_nr(slot + i);
4771                 btrfs_set_token_item_offset(leaf, item,
4772                                             data_end - data_size[i], &token);
4773                 data_end -= data_size[i];
4774                 btrfs_set_token_item_size(leaf, item, data_size[i], &token);
4775         }
4776
4777         btrfs_set_header_nritems(leaf, nritems + nr);
4778         btrfs_mark_buffer_dirty(leaf);
4779
4780         if (btrfs_leaf_free_space(root, leaf) < 0) {
4781                 btrfs_print_leaf(root, leaf);
4782                 BUG();
4783         }
4784 }
4785
4786 /*
4787  * Given a key and some data, insert items into the tree.
4788  * This does all the path init required, making room in the tree if needed.
4789  */
4790 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
4791                             struct btrfs_root *root,
4792                             struct btrfs_path *path,
4793                             struct btrfs_key *cpu_key, u32 *data_size,
4794                             int nr)
4795 {
4796         int ret = 0;
4797         int slot;
4798         int i;
4799         u32 total_size = 0;
4800         u32 total_data = 0;
4801
4802         for (i = 0; i < nr; i++)
4803                 total_data += data_size[i];
4804
4805         total_size = total_data + (nr * sizeof(struct btrfs_item));
4806         ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
4807         if (ret == 0)
4808                 return -EEXIST;
4809         if (ret < 0)
4810                 return ret;
4811
4812         slot = path->slots[0];
4813         BUG_ON(slot < 0);
4814
4815         setup_items_for_insert(root, path, cpu_key, data_size,
4816                                total_data, total_size, nr);
4817         return 0;
4818 }
4819
4820 /*
4821  * Given a key and some data, insert an item into the tree.
4822  * This does all the path init required, making room in the tree if needed.
4823  */
4824 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
4825                       *root, struct btrfs_key *cpu_key, void *data, u32
4826                       data_size)
4827 {
4828         int ret = 0;
4829         struct btrfs_path *path;
4830         struct extent_buffer *leaf;
4831         unsigned long ptr;
4832
4833         path = btrfs_alloc_path();
4834         if (!path)
4835                 return -ENOMEM;
4836         ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
4837         if (!ret) {
4838                 leaf = path->nodes[0];
4839                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4840                 write_extent_buffer(leaf, data, ptr, data_size);
4841                 btrfs_mark_buffer_dirty(leaf);
4842         }
4843         btrfs_free_path(path);
4844         return ret;
4845 }
4846
4847 /*
4848  * delete the pointer from a given node.
4849  *
4850  * the tree should have been previously balanced so the deletion does not
4851  * empty a node.
4852  */
4853 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
4854                     int level, int slot)
4855 {
4856         struct extent_buffer *parent = path->nodes[level];
4857         u32 nritems;
4858         int ret;
4859
4860         nritems = btrfs_header_nritems(parent);
4861         if (slot != nritems - 1) {
4862                 if (level)
4863                         tree_mod_log_eb_move(root->fs_info, parent, slot,
4864                                              slot + 1, nritems - slot - 1);
4865                 memmove_extent_buffer(parent,
4866                               btrfs_node_key_ptr_offset(slot),
4867                               btrfs_node_key_ptr_offset(slot + 1),
4868                               sizeof(struct btrfs_key_ptr) *
4869                               (nritems - slot - 1));
4870         } else if (level) {
4871                 ret = tree_mod_log_insert_key(root->fs_info, parent, slot,
4872                                               MOD_LOG_KEY_REMOVE, GFP_NOFS);
4873                 BUG_ON(ret < 0);
4874         }
4875
4876         nritems--;
4877         btrfs_set_header_nritems(parent, nritems);
4878         if (nritems == 0 && parent == root->node) {
4879                 BUG_ON(btrfs_header_level(root->node) != 1);
4880                 /* just turn the root into a leaf and break */
4881                 btrfs_set_header_level(root->node, 0);
4882         } else if (slot == 0) {
4883                 struct btrfs_disk_key disk_key;
4884
4885                 btrfs_node_key(parent, &disk_key, 0);
4886                 fixup_low_keys(root->fs_info, path, &disk_key, level + 1);
4887         }
4888         btrfs_mark_buffer_dirty(parent);
4889 }
4890
4891 /*
4892  * a helper function to delete the leaf pointed to by path->slots[1] and
4893  * path->nodes[1].
4894  *
4895  * This deletes the pointer in path->nodes[1] and frees the leaf
4896  * block extent.  zero is returned if it all worked out, < 0 otherwise.
4897  *
4898  * The path must have already been setup for deleting the leaf, including
4899  * all the proper balancing.  path->nodes[1] must be locked.
4900  */
4901 static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans,
4902                                     struct btrfs_root *root,
4903                                     struct btrfs_path *path,
4904                                     struct extent_buffer *leaf)
4905 {
4906         WARN_ON(btrfs_header_generation(leaf) != trans->transid);
4907         del_ptr(root, path, 1, path->slots[1]);
4908
4909         /*
4910          * btrfs_free_extent is expensive, we want to make sure we
4911          * aren't holding any locks when we call it
4912          */
4913         btrfs_unlock_up_safe(path, 0);
4914
4915         root_sub_used(root, leaf->len);
4916
4917         extent_buffer_get(leaf);
4918         btrfs_free_tree_block(trans, root, leaf, 0, 1);
4919         free_extent_buffer_stale(leaf);
4920 }
4921 /*
4922  * delete the item at the leaf level in path.  If that empties
4923  * the leaf, remove it from the tree
4924  */
4925 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4926                     struct btrfs_path *path, int slot, int nr)
4927 {
4928         struct extent_buffer *leaf;
4929         struct btrfs_item *item;
4930         u32 last_off;
4931         u32 dsize = 0;
4932         int ret = 0;
4933         int wret;
4934         int i;
4935         u32 nritems;
4936         struct btrfs_map_token token;
4937
4938         btrfs_init_map_token(&token);
4939
4940         leaf = path->nodes[0];
4941         last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
4942
4943         for (i = 0; i < nr; i++)
4944                 dsize += btrfs_item_size_nr(leaf, slot + i);
4945
4946         nritems = btrfs_header_nritems(leaf);
4947
4948         if (slot + nr != nritems) {
4949                 int data_end = leaf_data_end(root, leaf);
4950
4951                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
4952                               data_end + dsize,
4953                               btrfs_leaf_data(leaf) + data_end,
4954                               last_off - data_end);
4955
4956                 for (i = slot + nr; i < nritems; i++) {
4957                         u32 ioff;
4958
4959                         item = btrfs_item_nr(i);
4960                         ioff = btrfs_token_item_offset(leaf, item, &token);
4961                         btrfs_set_token_item_offset(leaf, item,
4962                                                     ioff + dsize, &token);
4963                 }
4964
4965                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
4966                               btrfs_item_nr_offset(slot + nr),
4967                               sizeof(struct btrfs_item) *
4968                               (nritems - slot - nr));
4969         }
4970         btrfs_set_header_nritems(leaf, nritems - nr);
4971         nritems -= nr;
4972
4973         /* delete the leaf if we've emptied it */
4974         if (nritems == 0) {
4975                 if (leaf == root->node) {
4976                         btrfs_set_header_level(leaf, 0);
4977                 } else {
4978                         btrfs_set_path_blocking(path);
4979                         clean_tree_block(trans, root->fs_info, leaf);
4980                         btrfs_del_leaf(trans, root, path, leaf);
4981                 }
4982         } else {
4983                 int used = leaf_space_used(leaf, 0, nritems);
4984                 if (slot == 0) {
4985                         struct btrfs_disk_key disk_key;
4986
4987                         btrfs_item_key(leaf, &disk_key, 0);
4988                         fixup_low_keys(root->fs_info, path, &disk_key, 1);
4989                 }
4990
4991                 /* delete the leaf if it is mostly empty */
4992                 if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
4993                         /* push_leaf_left fixes the path.
4994                          * make sure the path still points to our leaf
4995                          * for possible call to del_ptr below
4996                          */
4997                         slot = path->slots[1];
4998                         extent_buffer_get(leaf);
4999
5000                         btrfs_set_path_blocking(path);
5001                         wret = push_leaf_left(trans, root, path, 1, 1,
5002                                               1, (u32)-1);
5003                         if (wret < 0 && wret != -ENOSPC)
5004                                 ret = wret;
5005
5006                         if (path->nodes[0] == leaf &&
5007                             btrfs_header_nritems(leaf)) {
5008                                 wret = push_leaf_right(trans, root, path, 1,
5009                                                        1, 1, 0);
5010                                 if (wret < 0 && wret != -ENOSPC)
5011                                         ret = wret;
5012                         }
5013
5014                         if (btrfs_header_nritems(leaf) == 0) {
5015                                 path->slots[1] = slot;
5016                                 btrfs_del_leaf(trans, root, path, leaf);
5017                                 free_extent_buffer(leaf);
5018                                 ret = 0;
5019                         } else {
5020                                 /* if we're still in the path, make sure
5021                                  * we're dirty.  Otherwise, one of the
5022                                  * push_leaf functions must have already
5023                                  * dirtied this buffer
5024                                  */
5025                                 if (path->nodes[0] == leaf)
5026                                         btrfs_mark_buffer_dirty(leaf);
5027                                 free_extent_buffer(leaf);
5028                         }
5029                 } else {
5030                         btrfs_mark_buffer_dirty(leaf);
5031                 }
5032         }
5033         return ret;
5034 }
5035
5036 /*
5037  * search the tree again to find a leaf with lesser keys
5038  * returns 0 if it found something or 1 if there are no lesser leaves.
5039  * returns < 0 on io errors.
5040  *
5041  * This may release the path, and so you may lose any locks held at the
5042  * time you call it.
5043  */
5044 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
5045 {
5046         struct btrfs_key key;
5047         struct btrfs_disk_key found_key;
5048         int ret;
5049
5050         btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
5051
5052         if (key.offset > 0) {
5053                 key.offset--;
5054         } else if (key.type > 0) {
5055                 key.type--;
5056                 key.offset = (u64)-1;
5057         } else if (key.objectid > 0) {
5058                 key.objectid--;
5059                 key.type = (u8)-1;
5060                 key.offset = (u64)-1;
5061         } else {
5062                 return 1;
5063         }
5064
5065         btrfs_release_path(path);
5066         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5067         if (ret < 0)
5068                 return ret;
5069         btrfs_item_key(path->nodes[0], &found_key, 0);
5070         ret = comp_keys(&found_key, &key);
5071         /*
5072          * We might have had an item with the previous key in the tree right
5073          * before we released our path. And after we released our path, that
5074          * item might have been pushed to the first slot (0) of the leaf we
5075          * were holding due to a tree balance. Alternatively, an item with the
5076          * previous key can exist as the only element of a leaf (big fat item).
5077          * Therefore account for these 2 cases, so that our callers (like
5078          * btrfs_previous_item) don't miss an existing item with a key matching
5079          * the previous key we computed above.
5080          */
5081         if (ret <= 0)
5082                 return 0;
5083         return 1;
5084 }
5085
5086 /*
5087  * A helper function to walk down the tree starting at min_key, and looking
5088  * for nodes or leaves that are have a minimum transaction id.
5089  * This is used by the btree defrag code, and tree logging
5090  *
5091  * This does not cow, but it does stuff the starting key it finds back
5092  * into min_key, so you can call btrfs_search_slot with cow=1 on the
5093  * key and get a writable path.
5094  *
5095  * This does lock as it descends, and path->keep_locks should be set
5096  * to 1 by the caller.
5097  *
5098  * This honors path->lowest_level to prevent descent past a given level
5099  * of the tree.
5100  *
5101  * min_trans indicates the oldest transaction that you are interested
5102  * in walking through.  Any nodes or leaves older than min_trans are
5103  * skipped over (without reading them).
5104  *
5105  * returns zero if something useful was found, < 0 on error and 1 if there
5106  * was nothing in the tree that matched the search criteria.
5107  */
5108 int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
5109                          struct btrfs_path *path,
5110                          u64 min_trans)
5111 {
5112         struct extent_buffer *cur;
5113         struct btrfs_key found_key;
5114         int slot;
5115         int sret;
5116         u32 nritems;
5117         int level;
5118         int ret = 1;
5119         int keep_locks = path->keep_locks;
5120
5121         path->keep_locks = 1;
5122 again:
5123         cur = btrfs_read_lock_root_node(root);
5124         level = btrfs_header_level(cur);
5125         WARN_ON(path->nodes[level]);
5126         path->nodes[level] = cur;
5127         path->locks[level] = BTRFS_READ_LOCK;
5128
5129         if (btrfs_header_generation(cur) < min_trans) {
5130                 ret = 1;
5131                 goto out;
5132         }
5133         while (1) {
5134                 nritems = btrfs_header_nritems(cur);
5135                 level = btrfs_header_level(cur);
5136                 sret = bin_search(cur, min_key, level, &slot);
5137
5138                 /* at the lowest level, we're done, setup the path and exit */
5139                 if (level == path->lowest_level) {
5140                         if (slot >= nritems)
5141                                 goto find_next_key;
5142                         ret = 0;
5143                         path->slots[level] = slot;
5144                         btrfs_item_key_to_cpu(cur, &found_key, slot);
5145                         goto out;
5146                 }
5147                 if (sret && slot > 0)
5148                         slot--;
5149                 /*
5150                  * check this node pointer against the min_trans parameters.
5151                  * If it is too old, old, skip to the next one.
5152                  */
5153                 while (slot < nritems) {
5154                         u64 gen;
5155
5156                         gen = btrfs_node_ptr_generation(cur, slot);
5157                         if (gen < min_trans) {
5158                                 slot++;
5159                                 continue;
5160                         }
5161                         break;
5162                 }
5163 find_next_key:
5164                 /*
5165                  * we didn't find a candidate key in this node, walk forward
5166                  * and find another one
5167                  */
5168                 if (slot >= nritems) {
5169                         path->slots[level] = slot;
5170                         btrfs_set_path_blocking(path);
5171                         sret = btrfs_find_next_key(root, path, min_key, level,
5172                                                   min_trans);
5173                         if (sret == 0) {
5174                                 btrfs_release_path(path);
5175                                 goto again;
5176                         } else {
5177                                 goto out;
5178                         }
5179                 }
5180                 /* save our key for returning back */
5181                 btrfs_node_key_to_cpu(cur, &found_key, slot);
5182                 path->slots[level] = slot;
5183                 if (level == path->lowest_level) {
5184                         ret = 0;
5185                         goto out;
5186                 }
5187                 btrfs_set_path_blocking(path);
5188                 cur = read_node_slot(root, cur, slot);
5189                 BUG_ON(!cur); /* -ENOMEM */
5190
5191                 btrfs_tree_read_lock(cur);
5192
5193                 path->locks[level - 1] = BTRFS_READ_LOCK;
5194                 path->nodes[level - 1] = cur;
5195                 unlock_up(path, level, 1, 0, NULL);
5196                 btrfs_clear_path_blocking(path, NULL, 0);
5197         }
5198 out:
5199         path->keep_locks = keep_locks;
5200         if (ret == 0) {
5201                 btrfs_unlock_up_safe(path, path->lowest_level + 1);
5202                 btrfs_set_path_blocking(path);
5203                 memcpy(min_key, &found_key, sizeof(found_key));
5204         }
5205         return ret;
5206 }
5207
5208 static void tree_move_down(struct btrfs_root *root,
5209                            struct btrfs_path *path,
5210                            int *level, int root_level)
5211 {
5212         BUG_ON(*level == 0);
5213         path->nodes[*level - 1] = read_node_slot(root, path->nodes[*level],
5214                                         path->slots[*level]);
5215         path->slots[*level - 1] = 0;
5216         (*level)--;
5217 }
5218
5219 static int tree_move_next_or_upnext(struct btrfs_root *root,
5220                                     struct btrfs_path *path,
5221                                     int *level, int root_level)
5222 {
5223         int ret = 0;
5224         int nritems;
5225         nritems = btrfs_header_nritems(path->nodes[*level]);
5226
5227         path->slots[*level]++;
5228
5229         while (path->slots[*level] >= nritems) {
5230                 if (*level == root_level)
5231                         return -1;
5232
5233                 /* move upnext */
5234                 path->slots[*level] = 0;
5235                 free_extent_buffer(path->nodes[*level]);
5236                 path->nodes[*level] = NULL;
5237                 (*level)++;
5238                 path->slots[*level]++;
5239
5240                 nritems = btrfs_header_nritems(path->nodes[*level]);
5241                 ret = 1;
5242         }
5243         return ret;
5244 }
5245
5246 /*
5247  * Returns 1 if it had to move up and next. 0 is returned if it moved only next
5248  * or down.
5249  */
5250 static int tree_advance(struct btrfs_root *root,
5251                         struct btrfs_path *path,
5252                         int *level, int root_level,
5253                         int allow_down,
5254                         struct btrfs_key *key)
5255 {
5256         int ret;
5257
5258         if (*level == 0 || !allow_down) {
5259                 ret = tree_move_next_or_upnext(root, path, level, root_level);
5260         } else {
5261                 tree_move_down(root, path, level, root_level);
5262                 ret = 0;
5263         }
5264         if (ret >= 0) {
5265                 if (*level == 0)
5266                         btrfs_item_key_to_cpu(path->nodes[*level], key,
5267                                         path->slots[*level]);
5268                 else
5269                         btrfs_node_key_to_cpu(path->nodes[*level], key,
5270                                         path->slots[*level]);
5271         }
5272         return ret;
5273 }
5274
5275 static int tree_compare_item(struct btrfs_root *left_root,
5276                              struct btrfs_path *left_path,
5277                              struct btrfs_path *right_path,
5278                              char *tmp_buf)
5279 {
5280         int cmp;
5281         int len1, len2;
5282         unsigned long off1, off2;
5283
5284         len1 = btrfs_item_size_nr(left_path->nodes[0], left_path->slots[0]);
5285         len2 = btrfs_item_size_nr(right_path->nodes[0], right_path->slots[0]);
5286         if (len1 != len2)
5287                 return 1;
5288
5289         off1 = btrfs_item_ptr_offset(left_path->nodes[0], left_path->slots[0]);
5290         off2 = btrfs_item_ptr_offset(right_path->nodes[0],
5291                                 right_path->slots[0]);
5292
5293         read_extent_buffer(left_path->nodes[0], tmp_buf, off1, len1);
5294
5295         cmp = memcmp_extent_buffer(right_path->nodes[0], tmp_buf, off2, len1);
5296         if (cmp)
5297                 return 1;
5298         return 0;
5299 }
5300
5301 #define ADVANCE 1
5302 #define ADVANCE_ONLY_NEXT -1
5303
5304 /*
5305  * This function compares two trees and calls the provided callback for
5306  * every changed/new/deleted item it finds.
5307  * If shared tree blocks are encountered, whole subtrees are skipped, making
5308  * the compare pretty fast on snapshotted subvolumes.
5309  *
5310  * This currently works on commit roots only. As commit roots are read only,
5311  * we don't do any locking. The commit roots are protected with transactions.
5312  * Transactions are ended and rejoined when a commit is tried in between.
5313  *
5314  * This function checks for modifications done to the trees while comparing.
5315  * If it detects a change, it aborts immediately.
5316  */
5317 int btrfs_compare_trees(struct btrfs_root *left_root,
5318                         struct btrfs_root *right_root,
5319                         btrfs_changed_cb_t changed_cb, void *ctx)
5320 {
5321         int ret;
5322         int cmp;
5323         struct btrfs_path *left_path = NULL;
5324         struct btrfs_path *right_path = NULL;
5325         struct btrfs_key left_key;
5326         struct btrfs_key right_key;
5327         char *tmp_buf = NULL;
5328         int left_root_level;
5329         int right_root_level;
5330         int left_level;
5331         int right_level;
5332         int left_end_reached;
5333         int right_end_reached;
5334         int advance_left;
5335         int advance_right;
5336         u64 left_blockptr;
5337         u64 right_blockptr;
5338         u64 left_gen;
5339         u64 right_gen;
5340
5341         left_path = btrfs_alloc_path();
5342         if (!left_path) {
5343                 ret = -ENOMEM;
5344                 goto out;
5345         }
5346         right_path = btrfs_alloc_path();
5347         if (!right_path) {
5348                 ret = -ENOMEM;
5349                 goto out;
5350         }
5351
5352         tmp_buf = kmalloc(left_root->nodesize, GFP_NOFS);
5353         if (!tmp_buf) {
5354                 ret = -ENOMEM;
5355                 goto out;
5356         }
5357
5358         left_path->search_commit_root = 1;
5359         left_path->skip_locking = 1;
5360         right_path->search_commit_root = 1;
5361         right_path->skip_locking = 1;
5362
5363         /*
5364          * Strategy: Go to the first items of both trees. Then do
5365          *
5366          * If both trees are at level 0
5367          *   Compare keys of current items
5368          *     If left < right treat left item as new, advance left tree
5369          *       and repeat
5370          *     If left > right treat right item as deleted, advance right tree
5371          *       and repeat
5372          *     If left == right do deep compare of items, treat as changed if
5373          *       needed, advance both trees and repeat
5374          * If both trees are at the same level but not at level 0
5375          *   Compare keys of current nodes/leafs
5376          *     If left < right advance left tree and repeat
5377          *     If left > right advance right tree and repeat
5378          *     If left == right compare blockptrs of the next nodes/leafs
5379          *       If they match advance both trees but stay at the same level
5380          *         and repeat
5381          *       If they don't match advance both trees while allowing to go
5382          *         deeper and repeat
5383          * If tree levels are different
5384          *   Advance the tree that needs it and repeat
5385          *
5386          * Advancing a tree means:
5387          *   If we are at level 0, try to go to the next slot. If that's not
5388          *   possible, go one level up and repeat. Stop when we found a level
5389          *   where we could go to the next slot. We may at this point be on a
5390          *   node or a leaf.
5391          *
5392          *   If we are not at level 0 and not on shared tree blocks, go one
5393          *   level deeper.
5394          *
5395          *   If we are not at level 0 and on shared tree blocks, go one slot to
5396          *   the right if possible or go up and right.
5397          */
5398
5399         down_read(&left_root->fs_info->commit_root_sem);
5400         left_level = btrfs_header_level(left_root->commit_root);
5401         left_root_level = left_level;
5402         left_path->nodes[left_level] = left_root->commit_root;
5403         extent_buffer_get(left_path->nodes[left_level]);
5404
5405         right_level = btrfs_header_level(right_root->commit_root);
5406         right_root_level = right_level;
5407         right_path->nodes[right_level] = right_root->commit_root;
5408         extent_buffer_get(right_path->nodes[right_level]);
5409         up_read(&left_root->fs_info->commit_root_sem);
5410
5411         if (left_level == 0)
5412                 btrfs_item_key_to_cpu(left_path->nodes[left_level],
5413                                 &left_key, left_path->slots[left_level]);
5414         else
5415                 btrfs_node_key_to_cpu(left_path->nodes[left_level],
5416                                 &left_key, left_path->slots[left_level]);
5417         if (right_level == 0)
5418                 btrfs_item_key_to_cpu(right_path->nodes[right_level],
5419                                 &right_key, right_path->slots[right_level]);
5420         else
5421                 btrfs_node_key_to_cpu(right_path->nodes[right_level],
5422                                 &right_key, right_path->slots[right_level]);
5423
5424         left_end_reached = right_end_reached = 0;
5425         advance_left = advance_right = 0;
5426
5427         while (1) {
5428                 cond_resched();
5429                 if (advance_left && !left_end_reached) {
5430                         ret = tree_advance(left_root, left_path, &left_level,
5431                                         left_root_level,
5432                                         advance_left != ADVANCE_ONLY_NEXT,
5433                                         &left_key);
5434                         if (ret < 0)
5435                                 left_end_reached = ADVANCE;
5436                         advance_left = 0;
5437                 }
5438                 if (advance_right && !right_end_reached) {
5439                         ret = tree_advance(right_root, right_path, &right_level,
5440                                         right_root_level,
5441                                         advance_right != ADVANCE_ONLY_NEXT,
5442                                         &right_key);
5443                         if (ret < 0)
5444                                 right_end_reached = ADVANCE;
5445                         advance_right = 0;
5446                 }
5447
5448                 if (left_end_reached && right_end_reached) {
5449                         ret = 0;
5450                         goto out;
5451                 } else if (left_end_reached) {
5452                         if (right_level == 0) {
5453                                 ret = changed_cb(left_root, right_root,
5454                                                 left_path, right_path,
5455                                                 &right_key,
5456                                                 BTRFS_COMPARE_TREE_DELETED,
5457                                                 ctx);
5458                                 if (ret < 0)
5459                                         goto out;
5460                         }
5461                         advance_right = ADVANCE;
5462                         continue;
5463                 } else if (right_end_reached) {
5464                         if (left_level == 0) {
5465                                 ret = changed_cb(left_root, right_root,
5466                                                 left_path, right_path,
5467                                                 &left_key,
5468                                                 BTRFS_COMPARE_TREE_NEW,
5469                                                 ctx);
5470                                 if (ret < 0)
5471                                         goto out;
5472                         }
5473                         advance_left = ADVANCE;
5474                         continue;
5475                 }
5476
5477                 if (left_level == 0 && right_level == 0) {
5478                         cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
5479                         if (cmp < 0) {
5480                                 ret = changed_cb(left_root, right_root,
5481                                                 left_path, right_path,
5482                                                 &left_key,
5483                                                 BTRFS_COMPARE_TREE_NEW,
5484                                                 ctx);
5485                                 if (ret < 0)
5486                                         goto out;
5487                                 advance_left = ADVANCE;
5488                         } else if (cmp > 0) {
5489                                 ret = changed_cb(left_root, right_root,
5490                                                 left_path, right_path,
5491                                                 &right_key,
5492                                                 BTRFS_COMPARE_TREE_DELETED,
5493                                                 ctx);
5494                                 if (ret < 0)
5495                                         goto out;
5496                                 advance_right = ADVANCE;
5497                         } else {
5498                                 enum btrfs_compare_tree_result result;
5499
5500                                 WARN_ON(!extent_buffer_uptodate(left_path->nodes[0]));
5501                                 ret = tree_compare_item(left_root, left_path,
5502                                                 right_path, tmp_buf);
5503                                 if (ret)
5504                                         result = BTRFS_COMPARE_TREE_CHANGED;
5505                                 else
5506                                         result = BTRFS_COMPARE_TREE_SAME;
5507                                 ret = changed_cb(left_root, right_root,
5508                                                  left_path, right_path,
5509                                                  &left_key, result, ctx);
5510                                 if (ret < 0)
5511                                         goto out;
5512                                 advance_left = ADVANCE;
5513                                 advance_right = ADVANCE;
5514                         }
5515                 } else if (left_level == right_level) {
5516                         cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
5517                         if (cmp < 0) {
5518                                 advance_left = ADVANCE;
5519                         } else if (cmp > 0) {
5520                                 advance_right = ADVANCE;
5521                         } else {
5522                                 left_blockptr = btrfs_node_blockptr(
5523                                                 left_path->nodes[left_level],
5524                                                 left_path->slots[left_level]);
5525                                 right_blockptr = btrfs_node_blockptr(
5526                                                 right_path->nodes[right_level],
5527                                                 right_path->slots[right_level]);
5528                                 left_gen = btrfs_node_ptr_generation(
5529                                                 left_path->nodes[left_level],
5530                                                 left_path->slots[left_level]);
5531                                 right_gen = btrfs_node_ptr_generation(
5532                                                 right_path->nodes[right_level],
5533                                                 right_path->slots[right_level]);
5534                                 if (left_blockptr == right_blockptr &&
5535                                     left_gen == right_gen) {
5536                                         /*
5537                                          * As we're on a shared block, don't
5538                                          * allow to go deeper.
5539                                          */
5540                                         advance_left = ADVANCE_ONLY_NEXT;
5541                                         advance_right = ADVANCE_ONLY_NEXT;
5542                                 } else {
5543                                         advance_left = ADVANCE;
5544                                         advance_right = ADVANCE;
5545                                 }
5546                         }
5547                 } else if (left_level < right_level) {
5548                         advance_right = ADVANCE;
5549                 } else {
5550                         advance_left = ADVANCE;
5551                 }
5552         }
5553
5554 out:
5555         btrfs_free_path(left_path);
5556         btrfs_free_path(right_path);
5557         kfree(tmp_buf);
5558         return ret;
5559 }
5560
5561 /*
5562  * this is similar to btrfs_next_leaf, but does not try to preserve
5563  * and fixup the path.  It looks for and returns the next key in the
5564  * tree based on the current path and the min_trans parameters.
5565  *
5566  * 0 is returned if another key is found, < 0 if there are any errors
5567  * and 1 is returned if there are no higher keys in the tree
5568  *
5569  * path->keep_locks should be set to 1 on the search made before
5570  * calling this function.
5571  */
5572 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
5573                         struct btrfs_key *key, int level, u64 min_trans)
5574 {
5575         int slot;
5576         struct extent_buffer *c;
5577
5578         WARN_ON(!path->keep_locks);
5579         while (level < BTRFS_MAX_LEVEL) {
5580                 if (!path->nodes[level])
5581                         return 1;
5582
5583                 slot = path->slots[level] + 1;
5584                 c = path->nodes[level];
5585 next:
5586                 if (slot >= btrfs_header_nritems(c)) {
5587                         int ret;
5588                         int orig_lowest;
5589                         struct btrfs_key cur_key;
5590                         if (level + 1 >= BTRFS_MAX_LEVEL ||
5591                             !path->nodes[level + 1])
5592                                 return 1;
5593
5594                         if (path->locks[level + 1]) {
5595                                 level++;
5596                                 continue;
5597                         }
5598
5599                         slot = btrfs_header_nritems(c) - 1;
5600                         if (level == 0)
5601                                 btrfs_item_key_to_cpu(c, &cur_key, slot);
5602                         else
5603                                 btrfs_node_key_to_cpu(c, &cur_key, slot);
5604
5605                         orig_lowest = path->lowest_level;
5606                         btrfs_release_path(path);
5607                         path->lowest_level = level;
5608                         ret = btrfs_search_slot(NULL, root, &cur_key, path,
5609                                                 0, 0);
5610                         path->lowest_level = orig_lowest;
5611                         if (ret < 0)
5612                                 return ret;
5613
5614                         c = path->nodes[level];
5615                         slot = path->slots[level];
5616                         if (ret == 0)
5617                                 slot++;
5618                         goto next;
5619                 }
5620
5621                 if (level == 0)
5622                         btrfs_item_key_to_cpu(c, key, slot);
5623                 else {
5624                         u64 gen = btrfs_node_ptr_generation(c, slot);
5625
5626                         if (gen < min_trans) {
5627                                 slot++;
5628                                 goto next;
5629                         }
5630                         btrfs_node_key_to_cpu(c, key, slot);
5631                 }
5632                 return 0;
5633         }
5634         return 1;
5635 }
5636
5637 /*
5638  * search the tree again to find a leaf with greater keys
5639  * returns 0 if it found something or 1 if there are no greater leaves.
5640  * returns < 0 on io errors.
5641  */
5642 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
5643 {
5644         return btrfs_next_old_leaf(root, path, 0);
5645 }
5646
5647 int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
5648                         u64 time_seq)
5649 {
5650         int slot;
5651         int level;
5652         struct extent_buffer *c;
5653         struct extent_buffer *next;
5654         struct btrfs_key key;
5655         u32 nritems;
5656         int ret;
5657         int old_spinning = path->leave_spinning;
5658         int next_rw_lock = 0;
5659
5660         nritems = btrfs_header_nritems(path->nodes[0]);
5661         if (nritems == 0)
5662                 return 1;
5663
5664         btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
5665 again:
5666         level = 1;
5667         next = NULL;
5668         next_rw_lock = 0;
5669         btrfs_release_path(path);
5670
5671         path->keep_locks = 1;
5672         path->leave_spinning = 1;
5673
5674         if (time_seq)
5675                 ret = btrfs_search_old_slot(root, &key, path, time_seq);
5676         else
5677                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5678         path->keep_locks = 0;
5679
5680         if (ret < 0)
5681                 return ret;
5682
5683         nritems = btrfs_header_nritems(path->nodes[0]);
5684         /*
5685          * by releasing the path above we dropped all our locks.  A balance
5686          * could have added more items next to the key that used to be
5687          * at the very end of the block.  So, check again here and
5688          * advance the path if there are now more items available.
5689          */
5690         if (nritems > 0 && path->slots[0] < nritems - 1) {
5691                 if (ret == 0)
5692                         path->slots[0]++;
5693                 ret = 0;
5694                 goto done;
5695         }
5696         /*
5697          * So the above check misses one case:
5698          * - after releasing the path above, someone has removed the item that
5699          *   used to be at the very end of the block, and balance between leafs
5700          *   gets another one with bigger key.offset to replace it.
5701          *
5702          * This one should be returned as well, or we can get leaf corruption
5703          * later(esp. in __btrfs_drop_extents()).
5704          *
5705          * And a bit more explanation about this check,
5706          * with ret > 0, the key isn't found, the path points to the slot
5707          * where it should be inserted, so the path->slots[0] item must be the
5708          * bigger one.
5709          */
5710         if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) {
5711                 ret = 0;
5712                 goto done;
5713         }
5714
5715         while (level < BTRFS_MAX_LEVEL) {
5716                 if (!path->nodes[level]) {
5717                         ret = 1;
5718                         goto done;
5719                 }
5720
5721                 slot = path->slots[level] + 1;
5722                 c = path->nodes[level];
5723                 if (slot >= btrfs_header_nritems(c)) {
5724                         level++;
5725                         if (level == BTRFS_MAX_LEVEL) {
5726                                 ret = 1;
5727                                 goto done;
5728                         }
5729                         continue;
5730                 }
5731
5732                 if (next) {
5733                         btrfs_tree_unlock_rw(next, next_rw_lock);
5734                         free_extent_buffer(next);
5735                 }
5736
5737                 next = c;
5738                 next_rw_lock = path->locks[level];
5739                 ret = read_block_for_search(NULL, root, path, &next, level,
5740                                             slot, &key, 0);
5741                 if (ret == -EAGAIN)
5742                         goto again;
5743
5744                 if (ret < 0) {
5745                         btrfs_release_path(path);
5746                         goto done;
5747                 }
5748
5749                 if (!path->skip_locking) {
5750                         ret = btrfs_try_tree_read_lock(next);
5751                         if (!ret && time_seq) {
5752                                 /*
5753                                  * If we don't get the lock, we may be racing
5754                                  * with push_leaf_left, holding that lock while
5755                                  * itself waiting for the leaf we've currently
5756                                  * locked. To solve this situation, we give up
5757                                  * on our lock and cycle.
5758                                  */
5759                                 free_extent_buffer(next);
5760                                 btrfs_release_path(path);
5761                                 cond_resched();
5762                                 goto again;
5763                         }
5764                         if (!ret) {
5765                                 btrfs_set_path_blocking(path);
5766                                 btrfs_tree_read_lock(next);
5767                                 btrfs_clear_path_blocking(path, next,
5768                                                           BTRFS_READ_LOCK);
5769                         }
5770                         next_rw_lock = BTRFS_READ_LOCK;
5771                 }
5772                 break;
5773         }
5774         path->slots[level] = slot;
5775         while (1) {
5776                 level--;
5777                 c = path->nodes[level];
5778                 if (path->locks[level])
5779                         btrfs_tree_unlock_rw(c, path->locks[level]);
5780
5781                 free_extent_buffer(c);
5782                 path->nodes[level] = next;
5783                 path->slots[level] = 0;
5784                 if (!path->skip_locking)
5785                         path->locks[level] = next_rw_lock;
5786                 if (!level)
5787                         break;
5788
5789                 ret = read_block_for_search(NULL, root, path, &next, level,
5790                                             0, &key, 0);
5791                 if (ret == -EAGAIN)
5792                         goto again;
5793
5794                 if (ret < 0) {
5795                         btrfs_release_path(path);
5796                         goto done;
5797                 }
5798
5799                 if (!path->skip_locking) {
5800                         ret = btrfs_try_tree_read_lock(next);
5801                         if (!ret) {
5802                                 btrfs_set_path_blocking(path);
5803                                 btrfs_tree_read_lock(next);
5804                                 btrfs_clear_path_blocking(path, next,
5805                                                           BTRFS_READ_LOCK);
5806                         }
5807                         next_rw_lock = BTRFS_READ_LOCK;
5808                 }
5809         }
5810         ret = 0;
5811 done:
5812         unlock_up(path, 0, 1, 0, NULL);
5813         path->leave_spinning = old_spinning;
5814         if (!old_spinning)
5815                 btrfs_set_path_blocking(path);
5816
5817         return ret;
5818 }
5819
5820 /*
5821  * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
5822  * searching until it gets past min_objectid or finds an item of 'type'
5823  *
5824  * returns 0 if something is found, 1 if nothing was found and < 0 on error
5825  */
5826 int btrfs_previous_item(struct btrfs_root *root,
5827                         struct btrfs_path *path, u64 min_objectid,
5828                         int type)
5829 {
5830         struct btrfs_key found_key;
5831         struct extent_buffer *leaf;
5832         u32 nritems;
5833         int ret;
5834
5835         while (1) {
5836                 if (path->slots[0] == 0) {
5837                         btrfs_set_path_blocking(path);
5838                         ret = btrfs_prev_leaf(root, path);
5839                         if (ret != 0)
5840                                 return ret;
5841                 } else {
5842                         path->slots[0]--;
5843                 }
5844                 leaf = path->nodes[0];
5845                 nritems = btrfs_header_nritems(leaf);
5846                 if (nritems == 0)
5847                         return 1;
5848                 if (path->slots[0] == nritems)
5849                         path->slots[0]--;
5850
5851                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5852                 if (found_key.objectid < min_objectid)
5853                         break;
5854                 if (found_key.type == type)
5855                         return 0;
5856                 if (found_key.objectid == min_objectid &&
5857                     found_key.type < type)
5858                         break;
5859         }
5860         return 1;
5861 }
5862
5863 /*
5864  * search in extent tree to find a previous Metadata/Data extent item with
5865  * min objecitd.
5866  *
5867  * returns 0 if something is found, 1 if nothing was found and < 0 on error
5868  */
5869 int btrfs_previous_extent_item(struct btrfs_root *root,
5870                         struct btrfs_path *path, u64 min_objectid)
5871 {
5872         struct btrfs_key found_key;
5873         struct extent_buffer *leaf;
5874         u32 nritems;
5875         int ret;
5876
5877         while (1) {
5878                 if (path->slots[0] == 0) {
5879                         btrfs_set_path_blocking(path);
5880                         ret = btrfs_prev_leaf(root, path);
5881                         if (ret != 0)
5882                                 return ret;
5883                 } else {
5884                         path->slots[0]--;
5885                 }
5886                 leaf = path->nodes[0];
5887                 nritems = btrfs_header_nritems(leaf);
5888                 if (nritems == 0)
5889                         return 1;
5890                 if (path->slots[0] == nritems)
5891                         path->slots[0]--;
5892
5893                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5894                 if (found_key.objectid < min_objectid)
5895                         break;
5896                 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
5897                     found_key.type == BTRFS_METADATA_ITEM_KEY)
5898                         return 0;
5899                 if (found_key.objectid == min_objectid &&
5900                     found_key.type < BTRFS_EXTENT_ITEM_KEY)
5901                         break;
5902         }
5903         return 1;
5904 }