fs/btrfs/ctree.c

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