fs/btrfs/ctree.c

   1 /*
   2  * Copyright (C) 2007,2008 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include <linux/sched.h>
  20 #include <linux/slab.h>
  21 #include <linux/rbtree.h>
  22 #include <linux/vmalloc.h>
  23 #include "ctree.h"
  24 #include "disk-io.h"
  25 #include "transaction.h"
  26 #include "print-tree.h"
  27 #include "locking.h"
  28
  29 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  30                       *root, struct btrfs_path *path, int level);
  31 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
  32                       *root, struct btrfs_key *ins_key,
  33                       struct btrfs_path *path, int data_size, int extend);
  34 static int push_node_left(struct btrfs_trans_handle *trans,
  35                           struct btrfs_root *root, struct extent_buffer *dst,
  36                           struct extent_buffer *src, int empty);
  37 static int balance_node_right(struct btrfs_trans_handle *trans,
  38                               struct btrfs_root *root,
  39                               struct extent_buffer *dst_buf,
  40                               struct extent_buffer *src_buf);
  41 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
  42                     int level, int slot);
  43 static int tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
  44                                  struct extent_buffer *eb);
  45
  46 struct btrfs_path *btrfs_alloc_path(void)
  47 {
  48         struct btrfs_path *path;
  49         path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
  50         return path;
  51 }
  52
  53 /*
  54  * set all locked nodes in the path to blocking locks.  This should
  55  * be done before scheduling
  56  */
  57 noinline void btrfs_set_path_blocking(struct btrfs_path *p)
  58 {
  59         int i;
  60         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  61                 if (!p->nodes[i] || !p->locks[i])
  62                         continue;
  63                 btrfs_set_lock_blocking_rw(p->nodes[i], p->locks[i]);
  64                 if (p->locks[i] == BTRFS_READ_LOCK)
  65                         p->locks[i] = BTRFS_READ_LOCK_BLOCKING;
  66                 else if (p->locks[i] == BTRFS_WRITE_LOCK)
  67                         p->locks[i] = BTRFS_WRITE_LOCK_BLOCKING;
  68         }
  69 }
  70
  71 /*
  72  * reset all the locked nodes in the patch to spinning locks.
  73  *
  74  * held is used to keep lockdep happy, when lockdep is enabled
  75  * we set held to a blocking lock before we go around and
  76  * retake all the spinlocks in the path.  You can safely use NULL
  77  * for held
  78  */
  79 noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
  80                                         struct extent_buffer *held, int held_rw)
  81 {
  82         int i;
  83
  84         if (held) {
  85                 btrfs_set_lock_blocking_rw(held, held_rw);
  86                 if (held_rw == BTRFS_WRITE_LOCK)
  87                         held_rw = BTRFS_WRITE_LOCK_BLOCKING;
  88                 else if (held_rw == BTRFS_READ_LOCK)
  89                         held_rw = BTRFS_READ_LOCK_BLOCKING;
  90         }
  91         btrfs_set_path_blocking(p);
  92
  93         for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
  94                 if (p->nodes[i] && p->locks[i]) {
  95                         btrfs_clear_lock_blocking_rw(p->nodes[i], p->locks[i]);
  96                         if (p->locks[i] == BTRFS_WRITE_LOCK_BLOCKING)
  97                                 p->locks[i] = BTRFS_WRITE_LOCK;
  98                         else if (p->locks[i] == BTRFS_READ_LOCK_BLOCKING)
  99                                 p->locks[i] = BTRFS_READ_LOCK;
 100                 }
 101         }
 102
 103         if (held)
 104                 btrfs_clear_lock_blocking_rw(held, held_rw);
 105 }
 106
 107 /* this also releases the path */
 108 void btrfs_free_path(struct btrfs_path *p)
 109 {
 110         if (!p)
 111                 return;
 112         btrfs_release_path(p);
 113         kmem_cache_free(btrfs_path_cachep, p);
 114 }
 115
 116 /*
 117  * path release drops references on the extent buffers in the path
 118  * and it drops any locks held by this path
 119  *
 120  * It is safe to call this on paths that no locks or extent buffers held.
 121  */
 122 noinline void btrfs_release_path(struct btrfs_path *p)
 123 {
 124         int i;
 125
 126         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
 127                 p->slots[i] = 0;
 128                 if (!p->nodes[i])
 129                         continue;
 130                 if (p->locks[i]) {
 131                         btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]);
 132                         p->locks[i] = 0;
 133                 }
 134                 free_extent_buffer(p->nodes[i]);
 135                 p->nodes[i] = NULL;
 136         }
 137 }
 138
 139 /*
 140  * safely gets a reference on the root node of a tree.  A lock
 141  * is not taken, so a concurrent writer may put a different node
 142  * at the root of the tree.  See btrfs_lock_root_node for the
 143  * looping required.
 144  *
 145  * The extent buffer returned by this has a reference taken, so
 146  * it won't disappear.  It may stop being the root of the tree
 147  * at any time because there are no locks held.
 148  */
 149 struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
 150 {
 151         struct extent_buffer *eb;
 152
 153         while (1) {
 154                 rcu_read_lock();
 155                 eb = rcu_dereference(root->node);
 156
 157                 /*
 158                  * RCU really hurts here, we could free up the root node because
 159                  * it was COWed but we may not get the new root node yet so do
 160                  * the inc_not_zero dance and if it doesn't work then
 161                  * synchronize_rcu and try again.
 162                  */
 163                 if (atomic_inc_not_zero(&eb->refs)) {
 164                         rcu_read_unlock();
 165                         break;
 166                 }
 167                 rcu_read_unlock();
 168                 synchronize_rcu();
 169         }
 170         return eb;
 171 }
 172
 173 /* loop around taking references on and locking the root node of the
 174  * tree until you end up with a lock on the root.  A locked buffer
 175  * is returned, with a reference held.
 176  */
 177 struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
 178 {
 179         struct extent_buffer *eb;
 180
 181         while (1) {
 182                 eb = btrfs_root_node(root);
 183                 btrfs_tree_lock(eb);
 184                 if (eb == root->node)
 185                         break;
 186                 btrfs_tree_unlock(eb);
 187                 free_extent_buffer(eb);
 188         }
 189         return eb;
 190 }
 191
 192 /* loop around taking references on and locking the root node of the
 193  * tree until you end up with a lock on the root.  A locked buffer
 194  * is returned, with a reference held.
 195  */
 196 static struct extent_buffer *btrfs_read_lock_root_node(struct btrfs_root *root)
 197 {
 198         struct extent_buffer *eb;
 199
 200         while (1) {
 201                 eb = btrfs_root_node(root);
 202                 btrfs_tree_read_lock(eb);
 203                 if (eb == root->node)
 204                         break;
 205                 btrfs_tree_read_unlock(eb);
 206                 free_extent_buffer(eb);
 207         }
 208         return eb;
 209 }
 210
 211 /* cowonly root (everything not a reference counted cow subvolume), just get
 212  * put onto a simple dirty list.  transaction.c walks this to make sure they
 213  * get properly updated on disk.
 214  */
 215 static void add_root_to_dirty_list(struct btrfs_root *root)
 216 {
 217         if (test_bit(BTRFS_ROOT_DIRTY, &root->state) ||
 218             !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state))
 219                 return;
 220
 221         spin_lock(&root->fs_info->trans_lock);
 222         if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) {
 223                 /* Want the extent tree to be the last on the list */
 224                 if (root->objectid == BTRFS_EXTENT_TREE_OBJECTID)
 225                         list_move_tail(&root->dirty_list,
 226                                        &root->fs_info->dirty_cowonly_roots);
 227                 else
 228                         list_move(&root->dirty_list,
 229                                   &root->fs_info->dirty_cowonly_roots);
 230         }
 231         spin_unlock(&root->fs_info->trans_lock);
 232 }
 233
 234 /*
 235  * used by snapshot creation to make a copy of a root for a tree with
 236  * a given objectid.  The buffer with the new root node is returned in
 237  * cow_ret, and this func returns zero on success or a negative error code.
 238  */
 239 int btrfs_copy_root(struct btrfs_trans_handle *trans,
 240                       struct btrfs_root *root,
 241                       struct extent_buffer *buf,
 242                       struct extent_buffer **cow_ret, u64 new_root_objectid)
 243 {
 244         struct extent_buffer *cow;
 245         int ret = 0;
 246         int level;
 247         struct btrfs_disk_key disk_key;
 248
 249         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 250                 trans->transid != root->fs_info->running_transaction->transid);
 251         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 252                 trans->transid != root->last_trans);
 253
 254         level = btrfs_header_level(buf);
 255         if (level == 0)
 256                 btrfs_item_key(buf, &disk_key, 0);
 257         else
 258                 btrfs_node_key(buf, &disk_key, 0);
 259
 260         cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid,
 261                         &disk_key, level, buf->start, 0);
 262         if (IS_ERR(cow))
 263                 return PTR_ERR(cow);
 264
 265         copy_extent_buffer(cow, buf, 0, 0, cow->len);
 266         btrfs_set_header_bytenr(cow, cow->start);
 267         btrfs_set_header_generation(cow, trans->transid);
 268         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
 269         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
 270                                      BTRFS_HEADER_FLAG_RELOC);
 271         if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
 272                 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
 273         else
 274                 btrfs_set_header_owner(cow, new_root_objectid);
 275
 276         write_extent_buffer(cow, root->fs_info->fsid, btrfs_header_fsid(),
 277                             BTRFS_FSID_SIZE);
 278
 279         WARN_ON(btrfs_header_generation(buf) > trans->transid);
 280         if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
 281                 ret = btrfs_inc_ref(trans, root, cow, 1);
 282         else
 283                 ret = btrfs_inc_ref(trans, root, cow, 0);
 284
 285         if (ret)
 286                 return ret;
 287
 288         btrfs_mark_buffer_dirty(cow);
 289         *cow_ret = cow;
 290         return 0;
 291 }
 292
 293 enum mod_log_op {
 294         MOD_LOG_KEY_REPLACE,
 295         MOD_LOG_KEY_ADD,
 296         MOD_LOG_KEY_REMOVE,
 297         MOD_LOG_KEY_REMOVE_WHILE_FREEING,
 298         MOD_LOG_KEY_REMOVE_WHILE_MOVING,
 299         MOD_LOG_MOVE_KEYS,
 300         MOD_LOG_ROOT_REPLACE,
 301 };
 302
 303 struct tree_mod_move {
 304         int dst_slot;
 305         int nr_items;
 306 };
 307
 308 struct tree_mod_root {
 309         u64 logical;
 310         u8 level;
 311 };
 312
 313 struct tree_mod_elem {
 314         struct rb_node node;
 315         u64 logical;
 316         u64 seq;
 317         enum mod_log_op op;
 318
 319         /* this is used for MOD_LOG_KEY_* and MOD_LOG_MOVE_KEYS operations */
 320         int slot;
 321
 322         /* this is used for MOD_LOG_KEY* and MOD_LOG_ROOT_REPLACE */
 323         u64 generation;
 324
 325         /* those are used for op == MOD_LOG_KEY_{REPLACE,REMOVE} */
 326         struct btrfs_disk_key key;
 327         u64 blockptr;
 328
 329         /* this is used for op == MOD_LOG_MOVE_KEYS */
 330         struct tree_mod_move move;
 331
 332         /* this is used for op == MOD_LOG_ROOT_REPLACE */
 333         struct tree_mod_root old_root;
 334 };
 335
 336 static inline void tree_mod_log_read_lock(struct btrfs_fs_info *fs_info)
 337 {
 338         read_lock(&fs_info->tree_mod_log_lock);
 339 }
 340
 341 static inline void tree_mod_log_read_unlock(struct btrfs_fs_info *fs_info)
 342 {
 343         read_unlock(&fs_info->tree_mod_log_lock);
 344 }
 345
 346 static inline void tree_mod_log_write_lock(struct btrfs_fs_info *fs_info)
 347 {
 348         write_lock(&fs_info->tree_mod_log_lock);
 349 }
 350
 351 static inline void tree_mod_log_write_unlock(struct btrfs_fs_info *fs_info)
 352 {
 353         write_unlock(&fs_info->tree_mod_log_lock);
 354 }
 355
 356 /*
 357  * Pull a new tree mod seq number for our operation.
 358  */
 359 static inline u64 btrfs_inc_tree_mod_seq(struct btrfs_fs_info *fs_info)
 360 {
 361         return atomic64_inc_return(&fs_info->tree_mod_seq);
 362 }
 363
 364 /*
 365  * This adds a new blocker to the tree mod log's blocker list if the @elem
 366  * passed does not already have a sequence number set. So when a caller expects
 367  * to record tree modifications, it should ensure to set elem->seq to zero
 368  * before calling btrfs_get_tree_mod_seq.
 369  * Returns a fresh, unused tree log modification sequence number, even if no new
 370  * blocker was added.
 371  */
 372 u64 btrfs_get_tree_mod_seq(struct btrfs_fs_info *fs_info,
 373                            struct seq_list *elem)
 374 {
 375         tree_mod_log_write_lock(fs_info);
 376         spin_lock(&fs_info->tree_mod_seq_lock);
 377         if (!elem->seq) {
 378                 elem->seq = btrfs_inc_tree_mod_seq(fs_info);
 379                 list_add_tail(&elem->list, &fs_info->tree_mod_seq_list);
 380         }
 381         spin_unlock(&fs_info->tree_mod_seq_lock);
 382         tree_mod_log_write_unlock(fs_info);
 383
 384         return elem->seq;
 385 }
 386
 387 void btrfs_put_tree_mod_seq(struct btrfs_fs_info *fs_info,
 388                             struct seq_list *elem)
 389 {
 390         struct rb_root *tm_root;
 391         struct rb_node *node;
 392         struct rb_node *next;
 393         struct seq_list *cur_elem;
 394         struct tree_mod_elem *tm;
 395         u64 min_seq = (u64)-1;
 396         u64 seq_putting = elem->seq;
 397
 398         if (!seq_putting)
 399                 return;
 400
 401         spin_lock(&fs_info->tree_mod_seq_lock);
 402         list_del(&elem->list);
 403         elem->seq = 0;
 404
 405         list_for_each_entry(cur_elem, &fs_info->tree_mod_seq_list, list) {
 406                 if (cur_elem->seq < min_seq) {
 407                         if (seq_putting > cur_elem->seq) {
 408                                 /*
 409                                  * blocker with lower sequence number exists, we
 410                                  * cannot remove anything from the log
 411                                  */
 412                                 spin_unlock(&fs_info->tree_mod_seq_lock);
 413                                 return;
 414                         }
 415                         min_seq = cur_elem->seq;
 416                 }
 417         }
 418         spin_unlock(&fs_info->tree_mod_seq_lock);
 419
 420         /*
 421          * anything that's lower than the lowest existing (read: blocked)
 422          * sequence number can be removed from the tree.
 423          */
 424         tree_mod_log_write_lock(fs_info);
 425         tm_root = &fs_info->tree_mod_log;
 426         for (node = rb_first(tm_root); node; node = next) {
 427                 next = rb_next(node);
 428                 tm = container_of(node, struct tree_mod_elem, node);
 429                 if (tm->seq > min_seq)
 430                         continue;
 431                 rb_erase(node, tm_root);
 432                 kfree(tm);
 433         }
 434         tree_mod_log_write_unlock(fs_info);
 435 }
 436
 437 /*
 438  * key order of the log:
 439  *       node/leaf start address -> sequence
 440  *
 441  * The 'start address' is the logical address of the *new* root node
 442  * for root replace operations, or the logical address of the affected
 443  * block for all other operations.
 444  *
 445  * Note: must be called with write lock (tree_mod_log_write_lock).
 446  */
 447 static noinline int
 448 __tree_mod_log_insert(struct btrfs_fs_info *fs_info, struct tree_mod_elem *tm)
 449 {
 450         struct rb_root *tm_root;
 451         struct rb_node **new;
 452         struct rb_node *parent = NULL;
 453         struct tree_mod_elem *cur;
 454
 455         BUG_ON(!tm);
 456
 457         tm->seq = btrfs_inc_tree_mod_seq(fs_info);
 458
 459         tm_root = &fs_info->tree_mod_log;
 460         new = &tm_root->rb_node;
 461         while (*new) {
 462                 cur = container_of(*new, struct tree_mod_elem, node);
 463                 parent = *new;
 464                 if (cur->logical < tm->logical)
 465                         new = &((*new)->rb_left);
 466                 else if (cur->logical > tm->logical)
 467                         new = &((*new)->rb_right);
 468                 else if (cur->seq < tm->seq)
 469                         new = &((*new)->rb_left);
 470                 else if (cur->seq > tm->seq)
 471                         new = &((*new)->rb_right);
 472                 else
 473                         return -EEXIST;
 474         }
 475
 476         rb_link_node(&tm->node, parent, new);
 477         rb_insert_color(&tm->node, tm_root);
 478         return 0;
 479 }
 480
 481 /*
 482  * Determines if logging can be omitted. Returns 1 if it can. Otherwise, it
 483  * returns zero with the tree_mod_log_lock acquired. The caller must hold
 484  * this until all tree mod log insertions are recorded in the rb tree and then
 485  * call tree_mod_log_write_unlock() to release.
 486  */
 487 static inline int tree_mod_dont_log(struct btrfs_fs_info *fs_info,
 488                                     struct extent_buffer *eb) {
 489         smp_mb();
 490         if (list_empty(&(fs_info)->tree_mod_seq_list))
 491                 return 1;
 492         if (eb && btrfs_header_level(eb) == 0)
 493                 return 1;
 494
 495         tree_mod_log_write_lock(fs_info);
 496         if (list_empty(&(fs_info)->tree_mod_seq_list)) {
 497                 tree_mod_log_write_unlock(fs_info);
 498                 return 1;
 499         }
 500
 501         return 0;
 502 }
 503
 504 /* Similar to tree_mod_dont_log, but doesn't acquire any locks. */
 505 static inline int tree_mod_need_log(const struct btrfs_fs_info *fs_info,
 506                                     struct extent_buffer *eb)
 507 {
 508         smp_mb();
 509         if (list_empty(&(fs_info)->tree_mod_seq_list))
 510                 return 0;
 511         if (eb && btrfs_header_level(eb) == 0)
 512                 return 0;
 513
 514         return 1;
 515 }
 516
 517 static struct tree_mod_elem *
 518 alloc_tree_mod_elem(struct extent_buffer *eb, int slot,
 519                     enum mod_log_op op, gfp_t flags)
 520 {
 521         struct tree_mod_elem *tm;
 522
 523         tm = kzalloc(sizeof(*tm), flags);
 524         if (!tm)
 525                 return NULL;
 526
 527         tm->logical = eb->start;
 528         if (op != MOD_LOG_KEY_ADD) {
 529                 btrfs_node_key(eb, &tm->key, slot);
 530                 tm->blockptr = btrfs_node_blockptr(eb, slot);
 531         }
 532         tm->op = op;
 533         tm->slot = slot;
 534         tm->generation = btrfs_node_ptr_generation(eb, slot);
 535         RB_CLEAR_NODE(&tm->node);
 536
 537         return tm;
 538 }
 539
 540 static noinline int
 541 tree_mod_log_insert_key(struct btrfs_fs_info *fs_info,
 542                         struct extent_buffer *eb, int slot,
 543                         enum mod_log_op op, gfp_t flags)
 544 {
 545         struct tree_mod_elem *tm;
 546         int ret;
 547
 548         if (!tree_mod_need_log(fs_info, eb))
 549                 return 0;
 550
 551         tm = alloc_tree_mod_elem(eb, slot, op, flags);
 552         if (!tm)
 553                 return -ENOMEM;
 554
 555         if (tree_mod_dont_log(fs_info, eb)) {
 556                 kfree(tm);
 557                 return 0;
 558         }
 559
 560         ret = __tree_mod_log_insert(fs_info, tm);
 561         tree_mod_log_write_unlock(fs_info);
 562         if (ret)
 563                 kfree(tm);
 564
 565         return ret;
 566 }
 567
 568 static noinline int
 569 tree_mod_log_insert_move(struct btrfs_fs_info *fs_info,
 570                          struct extent_buffer *eb, int dst_slot, int src_slot,
 571                          int nr_items, gfp_t flags)
 572 {
 573         struct tree_mod_elem *tm = NULL;
 574         struct tree_mod_elem **tm_list = NULL;
 575         int ret = 0;
 576         int i;
 577         int locked = 0;
 578
 579         if (!tree_mod_need_log(fs_info, eb))
 580                 return 0;
 581
 582         tm_list = kcalloc(nr_items, sizeof(struct tree_mod_elem *), flags);
 583         if (!tm_list)
 584                 return -ENOMEM;
 585
 586         tm = kzalloc(sizeof(*tm), flags);
 587         if (!tm) {
 588                 ret = -ENOMEM;
 589                 goto free_tms;
 590         }
 591
 592         tm->logical = eb->start;
 593         tm->slot = src_slot;
 594         tm->move.dst_slot = dst_slot;
 595         tm->move.nr_items = nr_items;
 596         tm->op = MOD_LOG_MOVE_KEYS;
 597
 598         for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
 599                 tm_list[i] = alloc_tree_mod_elem(eb, i + dst_slot,
 600                     MOD_LOG_KEY_REMOVE_WHILE_MOVING, flags);
 601                 if (!tm_list[i]) {
 602                         ret = -ENOMEM;
 603                         goto free_tms;
 604                 }
 605         }
 606
 607         if (tree_mod_dont_log(fs_info, eb))
 608                 goto free_tms;
 609         locked = 1;
 610
 611         /*
 612          * When we override something during the move, we log these removals.
 613          * This can only happen when we move towards the beginning of the
 614          * buffer, i.e. dst_slot < src_slot.
 615          */
 616         for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
 617                 ret = __tree_mod_log_insert(fs_info, tm_list[i]);
 618                 if (ret)
 619                         goto free_tms;
 620         }
 621
 622         ret = __tree_mod_log_insert(fs_info, tm);
 623         if (ret)
 624                 goto free_tms;
 625         tree_mod_log_write_unlock(fs_info);
 626         kfree(tm_list);
 627
 628         return 0;
 629 free_tms:
 630         for (i = 0; i < nr_items; i++) {
 631                 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
 632                         rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
 633                 kfree(tm_list[i]);
 634         }
 635         if (locked)
 636                 tree_mod_log_write_unlock(fs_info);
 637         kfree(tm_list);
 638         kfree(tm);
 639
 640         return ret;
 641 }
 642
 643 static inline int
 644 __tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
 645                        struct tree_mod_elem **tm_list,
 646                        int nritems)
 647 {
 648         int i, j;
 649         int ret;
 650
 651         for (i = nritems - 1; i >= 0; i--) {
 652                 ret = __tree_mod_log_insert(fs_info, tm_list[i]);
 653                 if (ret) {
 654                         for (j = nritems - 1; j > i; j--)
 655                                 rb_erase(&tm_list[j]->node,
 656                                          &fs_info->tree_mod_log);
 657                         return ret;
 658                 }
 659         }
 660
 661         return 0;
 662 }
 663
 664 static noinline int
 665 tree_mod_log_insert_root(struct btrfs_fs_info *fs_info,
 666                          struct extent_buffer *old_root,
 667                          struct extent_buffer *new_root, gfp_t flags,
 668                          int log_removal)
 669 {
 670         struct tree_mod_elem *tm = NULL;
 671         struct tree_mod_elem **tm_list = NULL;
 672         int nritems = 0;
 673         int ret = 0;
 674         int i;
 675
 676         if (!tree_mod_need_log(fs_info, NULL))
 677                 return 0;
 678
 679         if (log_removal && btrfs_header_level(old_root) > 0) {
 680                 nritems = btrfs_header_nritems(old_root);
 681                 tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *),
 682                                   flags);
 683                 if (!tm_list) {
 684                         ret = -ENOMEM;
 685                         goto free_tms;
 686                 }
 687                 for (i = 0; i < nritems; i++) {
 688                         tm_list[i] = alloc_tree_mod_elem(old_root, i,
 689                             MOD_LOG_KEY_REMOVE_WHILE_FREEING, flags);
 690                         if (!tm_list[i]) {
 691                                 ret = -ENOMEM;
 692                                 goto free_tms;
 693                         }
 694                 }
 695         }
 696
 697         tm = kzalloc(sizeof(*tm), flags);
 698         if (!tm) {
 699                 ret = -ENOMEM;
 700                 goto free_tms;
 701         }
 702
 703         tm->logical = new_root->start;
 704         tm->old_root.logical = old_root->start;
 705         tm->old_root.level = btrfs_header_level(old_root);
 706         tm->generation = btrfs_header_generation(old_root);
 707         tm->op = MOD_LOG_ROOT_REPLACE;
 708
 709         if (tree_mod_dont_log(fs_info, NULL))
 710                 goto free_tms;
 711
 712         if (tm_list)
 713                 ret = __tree_mod_log_free_eb(fs_info, tm_list, nritems);
 714         if (!ret)
 715                 ret = __tree_mod_log_insert(fs_info, tm);
 716
 717         tree_mod_log_write_unlock(fs_info);
 718         if (ret)
 719                 goto free_tms;
 720         kfree(tm_list);
 721
 722         return ret;
 723
 724 free_tms:
 725         if (tm_list) {
 726                 for (i = 0; i < nritems; i++)
 727                         kfree(tm_list[i]);
 728                 kfree(tm_list);
 729         }
 730         kfree(tm);
 731
 732         return ret;
 733 }
 734
 735 static struct tree_mod_elem *
 736 __tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq,
 737                       int smallest)
 738 {
 739         struct rb_root *tm_root;
 740         struct rb_node *node;
 741         struct tree_mod_elem *cur = NULL;
 742         struct tree_mod_elem *found = NULL;
 743
 744         tree_mod_log_read_lock(fs_info);
 745         tm_root = &fs_info->tree_mod_log;
 746         node = tm_root->rb_node;
 747         while (node) {
 748                 cur = container_of(node, struct tree_mod_elem, node);
 749                 if (cur->logical < start) {
 750                         node = node->rb_left;
 751                 } else if (cur->logical > start) {
 752                         node = node->rb_right;
 753                 } else if (cur->seq < min_seq) {
 754                         node = node->rb_left;
 755                 } else if (!smallest) {
 756                         /* we want the node with the highest seq */
 757                         if (found)
 758                                 BUG_ON(found->seq > cur->seq);
 759                         found = cur;
 760                         node = node->rb_left;
 761                 } else if (cur->seq > min_seq) {
 762                         /* we want the node with the smallest seq */
 763                         if (found)
 764                                 BUG_ON(found->seq < cur->seq);
 765                         found = cur;
 766                         node = node->rb_right;
 767                 } else {
 768                         found = cur;
 769                         break;
 770                 }
 771         }
 772         tree_mod_log_read_unlock(fs_info);
 773
 774         return found;
 775 }
 776
 777 /*
 778  * this returns the element from the log with the smallest time sequence
 779  * value that's in the log (the oldest log item). any element with a time
 780  * sequence lower than min_seq will be ignored.
 781  */
 782 static struct tree_mod_elem *
 783 tree_mod_log_search_oldest(struct btrfs_fs_info *fs_info, u64 start,
 784                            u64 min_seq)
 785 {
 786         return __tree_mod_log_search(fs_info, start, min_seq, 1);
 787 }
 788
 789 /*
 790  * this returns the element from the log with the largest time sequence
 791  * value that's in the log (the most recent log item). any element with
 792  * a time sequence lower than min_seq will be ignored.
 793  */
 794 static struct tree_mod_elem *
 795 tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq)
 796 {
 797         return __tree_mod_log_search(fs_info, start, min_seq, 0);
 798 }
 799
 800 static noinline int
 801 tree_mod_log_eb_copy(struct btrfs_fs_info *fs_info, struct extent_buffer *dst,
 802                      struct extent_buffer *src, unsigned long dst_offset,
 803                      unsigned long src_offset, int nr_items)
 804 {
 805         int ret = 0;
 806         struct tree_mod_elem **tm_list = NULL;
 807         struct tree_mod_elem **tm_list_add, **tm_list_rem;
 808         int i;
 809         int locked = 0;
 810
 811         if (!tree_mod_need_log(fs_info, NULL))
 812                 return 0;
 813
 814         if (btrfs_header_level(dst) == 0 && btrfs_header_level(src) == 0)
 815                 return 0;
 816
 817         tm_list = kcalloc(nr_items * 2, sizeof(struct tree_mod_elem *),
 818                           GFP_NOFS);
 819         if (!tm_list)
 820                 return -ENOMEM;
 821
 822         tm_list_add = tm_list;
 823         tm_list_rem = tm_list + nr_items;
 824         for (i = 0; i < nr_items; i++) {
 825                 tm_list_rem[i] = alloc_tree_mod_elem(src, i + src_offset,
 826                     MOD_LOG_KEY_REMOVE, GFP_NOFS);
 827                 if (!tm_list_rem[i]) {
 828                         ret = -ENOMEM;
 829                         goto free_tms;
 830                 }
 831
 832                 tm_list_add[i] = alloc_tree_mod_elem(dst, i + dst_offset,
 833                     MOD_LOG_KEY_ADD, GFP_NOFS);
 834                 if (!tm_list_add[i]) {
 835                         ret = -ENOMEM;
 836                         goto free_tms;
 837                 }
 838         }
 839
 840         if (tree_mod_dont_log(fs_info, NULL))
 841                 goto free_tms;
 842         locked = 1;
 843
 844         for (i = 0; i < nr_items; i++) {
 845                 ret = __tree_mod_log_insert(fs_info, tm_list_rem[i]);
 846                 if (ret)
 847                         goto free_tms;
 848                 ret = __tree_mod_log_insert(fs_info, tm_list_add[i]);
 849                 if (ret)
 850                         goto free_tms;
 851         }
 852
 853         tree_mod_log_write_unlock(fs_info);
 854         kfree(tm_list);
 855
 856         return 0;
 857
 858 free_tms:
 859         for (i = 0; i < nr_items * 2; i++) {
 860                 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
 861                         rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
 862                 kfree(tm_list[i]);
 863         }
 864         if (locked)
 865                 tree_mod_log_write_unlock(fs_info);
 866         kfree(tm_list);
 867
 868         return ret;
 869 }
 870
 871 static inline void
 872 tree_mod_log_eb_move(struct btrfs_fs_info *fs_info, struct extent_buffer *dst,
 873                      int dst_offset, int src_offset, int nr_items)
 874 {
 875         int ret;
 876         ret = tree_mod_log_insert_move(fs_info, dst, dst_offset, src_offset,
 877                                        nr_items, GFP_NOFS);
 878         BUG_ON(ret < 0);
 879 }
 880
 881 static noinline void
 882 tree_mod_log_set_node_key(struct btrfs_fs_info *fs_info,
 883                           struct extent_buffer *eb, int slot, int atomic)
 884 {
 885         int ret;
 886
 887         ret = tree_mod_log_insert_key(fs_info, eb, slot,
 888                                         MOD_LOG_KEY_REPLACE,
 889                                         atomic ? GFP_ATOMIC : GFP_NOFS);
 890         BUG_ON(ret < 0);
 891 }
 892
 893 static noinline int
 894 tree_mod_log_free_eb(struct btrfs_fs_info *fs_info, struct extent_buffer *eb)
 895 {
 896         struct tree_mod_elem **tm_list = NULL;
 897         int nritems = 0;
 898         int i;
 899         int ret = 0;
 900
 901         if (btrfs_header_level(eb) == 0)
 902                 return 0;
 903
 904         if (!tree_mod_need_log(fs_info, NULL))
 905                 return 0;
 906
 907         nritems = btrfs_header_nritems(eb);
 908         tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *), GFP_NOFS);
 909         if (!tm_list)
 910                 return -ENOMEM;
 911
 912         for (i = 0; i < nritems; i++) {
 913                 tm_list[i] = alloc_tree_mod_elem(eb, i,
 914                     MOD_LOG_KEY_REMOVE_WHILE_FREEING, GFP_NOFS);
 915                 if (!tm_list[i]) {
 916                         ret = -ENOMEM;
 917                         goto free_tms;
 918                 }
 919         }
 920
 921         if (tree_mod_dont_log(fs_info, eb))
 922                 goto free_tms;
 923
 924         ret = __tree_mod_log_free_eb(fs_info, tm_list, nritems);
 925         tree_mod_log_write_unlock(fs_info);
 926         if (ret)
 927                 goto free_tms;
 928         kfree(tm_list);
 929
 930         return 0;
 931
 932 free_tms:
 933         for (i = 0; i < nritems; i++)
 934                 kfree(tm_list[i]);
 935         kfree(tm_list);
 936
 937         return ret;
 938 }
 939
 940 static noinline void
 941 tree_mod_log_set_root_pointer(struct btrfs_root *root,
 942                               struct extent_buffer *new_root_node,
 943                               int log_removal)
 944 {
 945         int ret;
 946         ret = tree_mod_log_insert_root(root->fs_info, root->node,
 947                                        new_root_node, GFP_NOFS, log_removal);
 948         BUG_ON(ret < 0);
 949 }
 950
 951 /*
 952  * check if the tree block can be shared by multiple trees
 953  */
 954 int btrfs_block_can_be_shared(struct btrfs_root *root,
 955                               struct extent_buffer *buf)
 956 {
 957         /*
 958          * Tree blocks not in reference counted trees and tree roots
 959          * are never shared. If a block was allocated after the last
 960          * snapshot and the block was not allocated by tree relocation,
 961          * we know the block is not shared.
 962          */
 963         if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 964             buf != root->node && buf != root->commit_root &&
 965             (btrfs_header_generation(buf) <=
 966              btrfs_root_last_snapshot(&root->root_item) ||
 967              btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
 968                 return 1;
 969 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 970         if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 971             btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
 972                 return 1;
 973 #endif
 974         return 0;
 975 }
 976
 977 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
 978                                        struct btrfs_root *root,
 979                                        struct extent_buffer *buf,
 980                                        struct extent_buffer *cow,
 981                                        int *last_ref)
 982 {
 983         u64 refs;
 984         u64 owner;
 985         u64 flags;
 986         u64 new_flags = 0;
 987         int ret;
 988
 989         /*
 990          * Backrefs update rules:
 991          *
 992          * Always use full backrefs for extent pointers in tree block
 993          * allocated by tree relocation.
 994          *
 995          * If a shared tree block is no longer referenced by its owner
 996          * tree (btrfs_header_owner(buf) == root->root_key.objectid),
 997          * use full backrefs for extent pointers in tree block.
 998          *
 999          * If a tree block is been relocating
1000          * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
1001          * use full backrefs for extent pointers in tree block.
1002          * The reason for this is some operations (such as drop tree)
1003          * are only allowed for blocks use full backrefs.
1004          */
1005
1006         if (btrfs_block_can_be_shared(root, buf)) {
1007                 ret = btrfs_lookup_extent_info(trans, root, buf->start,
1008                                                btrfs_header_level(buf), 1,
1009                                                &refs, &flags);
1010                 if (ret)
1011                         return ret;
1012                 if (refs == 0) {
1013                         ret = -EROFS;
1014                         btrfs_handle_fs_error(root->fs_info, ret, NULL);
1015                         return ret;
1016                 }
1017         } else {
1018                 refs = 1;
1019                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
1020                     btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
1021                         flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
1022                 else
1023                         flags = 0;
1024         }
1025
1026         owner = btrfs_header_owner(buf);
1027         BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
1028                !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
1029
1030         if (refs > 1) {
1031                 if ((owner == root->root_key.objectid ||
1032                      root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
1033                     !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
1034                         ret = btrfs_inc_ref(trans, root, buf, 1);
1035                         BUG_ON(ret); /* -ENOMEM */
1036
1037                         if (root->root_key.objectid ==
1038                             BTRFS_TREE_RELOC_OBJECTID) {
1039                                 ret = btrfs_dec_ref(trans, root, buf, 0);
1040                                 BUG_ON(ret); /* -ENOMEM */
1041                                 ret = btrfs_inc_ref(trans, root, cow, 1);
1042                                 BUG_ON(ret); /* -ENOMEM */
1043                         }
1044                         new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
1045                 } else {
1046
1047                         if (root->root_key.objectid ==
1048                             BTRFS_TREE_RELOC_OBJECTID)
1049                                 ret = btrfs_inc_ref(trans, root, cow, 1);
1050                         else
1051                                 ret = btrfs_inc_ref(trans, root, cow, 0);
1052                         BUG_ON(ret); /* -ENOMEM */
1053                 }
1054                 if (new_flags != 0) {
1055                         int level = btrfs_header_level(buf);
1056
1057                         ret = btrfs_set_disk_extent_flags(trans, root,
1058                                                           buf->start,
1059                                                           buf->len,
1060                                                           new_flags, level, 0);
1061                         if (ret)
1062                                 return ret;
1063                 }
1064         } else {
1065                 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
1066                         if (root->root_key.objectid ==
1067                             BTRFS_TREE_RELOC_OBJECTID)
1068                                 ret = btrfs_inc_ref(trans, root, cow, 1);
1069                         else
1070                                 ret = btrfs_inc_ref(trans, root, cow, 0);
1071                         BUG_ON(ret); /* -ENOMEM */
1072                         ret = btrfs_dec_ref(trans, root, buf, 1);
1073                         BUG_ON(ret); /* -ENOMEM */
1074                 }
1075                 clean_tree_block(trans, root->fs_info, buf);
1076                 *last_ref = 1;
1077         }
1078         return 0;
1079 }
1080
1081 /*
1082  * does the dirty work in cow of a single block.  The parent block (if
1083  * supplied) is updated to point to the new cow copy.  The new buffer is marked
1084  * dirty and returned locked.  If you modify the block it needs to be marked
1085  * dirty again.
1086  *
1087  * search_start -- an allocation hint for the new block
1088  *
1089  * empty_size -- a hint that you plan on doing more cow.  This is the size in
1090  * bytes the allocator should try to find free next to the block it returns.
1091  * This is just a hint and may be ignored by the allocator.
1092  */
1093 static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
1094                              struct btrfs_root *root,
1095                              struct extent_buffer *buf,
1096                              struct extent_buffer *parent, int parent_slot,
1097                              struct extent_buffer **cow_ret,
1098                              u64 search_start, u64 empty_size)
1099 {
1100         struct btrfs_disk_key disk_key;
1101         struct extent_buffer *cow;
1102         int level, ret;
1103         int last_ref = 0;
1104         int unlock_orig = 0;
1105         u64 parent_start;
1106
1107         if (*cow_ret == buf)
1108                 unlock_orig = 1;
1109
1110         btrfs_assert_tree_locked(buf);
1111
1112         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
1113                 trans->transid != root->fs_info->running_transaction->transid);
1114         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
1115                 trans->transid != root->last_trans);
1116
1117         level = btrfs_header_level(buf);
1118
1119         if (level == 0)
1120                 btrfs_item_key(buf, &disk_key, 0);
1121         else
1122                 btrfs_node_key(buf, &disk_key, 0);
1123
1124         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1125                 if (parent)
1126                         parent_start = parent->start;
1127                 else
1128                         parent_start = 0;
1129         } else
1130                 parent_start = 0;
1131
1132         cow = btrfs_alloc_tree_block(trans, root, parent_start,
1133                         root->root_key.objectid, &disk_key, level,
1134                         search_start, empty_size);
1135         if (IS_ERR(cow))
1136                 return PTR_ERR(cow);
1137
1138         /* cow is set to blocking by btrfs_init_new_buffer */
1139
1140         copy_extent_buffer(cow, buf, 0, 0, cow->len);
1141         btrfs_set_header_bytenr(cow, cow->start);
1142         btrfs_set_header_generation(cow, trans->transid);
1143         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1144         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
1145                                      BTRFS_HEADER_FLAG_RELOC);
1146         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
1147                 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
1148         else
1149                 btrfs_set_header_owner(cow, root->root_key.objectid);
1150
1151         write_extent_buffer(cow, root->fs_info->fsid, btrfs_header_fsid(),
1152                             BTRFS_FSID_SIZE);
1153
1154         ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
1155         if (ret) {
1156                 btrfs_abort_transaction(trans, ret);
1157                 return ret;
1158         }
1159
1160         if (test_bit(BTRFS_ROOT_REF_COWS, &root->state)) {
1161                 ret = btrfs_reloc_cow_block(trans, root, buf, cow);
1162                 if (ret) {
1163                         btrfs_abort_transaction(trans, ret);
1164                         return ret;
1165                 }
1166         }
1167
1168         if (buf == root->node) {
1169                 WARN_ON(parent && parent != buf);
1170                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
1171                     btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
1172                         parent_start = buf->start;
1173                 else
1174                         parent_start = 0;
1175
1176                 extent_buffer_get(cow);
1177                 tree_mod_log_set_root_pointer(root, cow, 1);
1178                 rcu_assign_pointer(root->node, cow);
1179
1180                 btrfs_free_tree_block(trans, root, buf, parent_start,
1181                                       last_ref);
1182                 free_extent_buffer(buf);
1183                 add_root_to_dirty_list(root);
1184         } else {
1185                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
1186                         parent_start = parent->start;
1187                 else
1188                         parent_start = 0;
1189
1190                 WARN_ON(trans->transid != btrfs_header_generation(parent));
1191                 tree_mod_log_insert_key(root->fs_info, parent, parent_slot,
1192                                         MOD_LOG_KEY_REPLACE, GFP_NOFS);
1193                 btrfs_set_node_blockptr(parent, parent_slot,
1194                                         cow->start);
1195                 btrfs_set_node_ptr_generation(parent, parent_slot,
1196                                               trans->transid);
1197                 btrfs_mark_buffer_dirty(parent);
1198                 if (last_ref) {
1199                         ret = tree_mod_log_free_eb(root->fs_info, buf);
1200                         if (ret) {
1201                                 btrfs_abort_transaction(trans, ret);
1202                                 return ret;
1203                         }
1204                 }
1205                 btrfs_free_tree_block(trans, root, buf, parent_start,
1206                                       last_ref);
1207         }
1208         if (unlock_orig)
1209                 btrfs_tree_unlock(buf);
1210         free_extent_buffer_stale(buf);
1211         btrfs_mark_buffer_dirty(cow);
1212         *cow_ret = cow;
1213         return 0;
1214 }
1215
1216 /*
1217  * returns the logical address of the oldest predecessor of the given root.
1218  * entries older than time_seq are ignored.
1219  */
1220 static struct tree_mod_elem *
1221 __tree_mod_log_oldest_root(struct btrfs_fs_info *fs_info,
1222                            struct extent_buffer *eb_root, u64 time_seq)
1223 {
1224         struct tree_mod_elem *tm;
1225         struct tree_mod_elem *found = NULL;
1226         u64 root_logical = eb_root->start;
1227         int looped = 0;
1228
1229         if (!time_seq)
1230                 return NULL;
1231
1232         /*
1233          * the very last operation that's logged for a root is the
1234          * replacement operation (if it is replaced at all). this has
1235          * the logical address of the *new* root, making it the very
1236          * first operation that's logged for this root.
1237          */
1238         while (1) {
1239                 tm = tree_mod_log_search_oldest(fs_info, root_logical,
1240                                                 time_seq);
1241                 if (!looped && !tm)
1242                         return NULL;
1243                 /*
1244                  * if there are no tree operation for the oldest root, we simply
1245                  * return it. this should only happen if that (old) root is at
1246                  * level 0.
1247                  */
1248                 if (!tm)
1249                         break;
1250
1251                 /*
1252                  * if there's an operation that's not a root replacement, we
1253                  * found the oldest version of our root. normally, we'll find a
1254                  * MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here.
1255                  */
1256                 if (tm->op != MOD_LOG_ROOT_REPLACE)
1257                         break;
1258
1259                 found = tm;
1260                 root_logical = tm->old_root.logical;
1261                 looped = 1;
1262         }
1263
1264         /* if there's no old root to return, return what we found instead */
1265         if (!found)
1266                 found = tm;
1267
1268         return found;
1269 }
1270
1271 /*
1272  * tm is a pointer to the first operation to rewind within eb. then, all
1273  * previous operations will be rewound (until we reach something older than
1274  * time_seq).
1275  */
1276 static void
1277 __tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct extent_buffer *eb,
1278                       u64 time_seq, struct tree_mod_elem *first_tm)
1279 {
1280         u32 n;
1281         struct rb_node *next;
1282         struct tree_mod_elem *tm = first_tm;
1283         unsigned long o_dst;
1284         unsigned long o_src;
1285         unsigned long p_size = sizeof(struct btrfs_key_ptr);
1286
1287         n = btrfs_header_nritems(eb);
1288         tree_mod_log_read_lock(fs_info);
1289         while (tm && tm->seq >= time_seq) {
1290                 /*
1291                  * all the operations are recorded with the operator used for
1292                  * the modification. as we're going backwards, we do the
1293                  * opposite of each operation here.
1294                  */
1295                 switch (tm->op) {
1296                 case MOD_LOG_KEY_REMOVE_WHILE_FREEING:
1297                         BUG_ON(tm->slot < n);
1298                         /* Fallthrough */
1299                 case MOD_LOG_KEY_REMOVE_WHILE_MOVING:
1300                 case MOD_LOG_KEY_REMOVE:
1301                         btrfs_set_node_key(eb, &tm->key, tm->slot);
1302                         btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
1303                         btrfs_set_node_ptr_generation(eb, tm->slot,
1304                                                       tm->generation);
1305                         n++;
1306                         break;
1307                 case MOD_LOG_KEY_REPLACE:
1308                         BUG_ON(tm->slot >= n);
1309                         btrfs_set_node_key(eb, &tm->key, tm->slot);
1310                         btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
1311                         btrfs_set_node_ptr_generation(eb, tm->slot,
1312                                                       tm->generation);
1313                         break;
1314                 case MOD_LOG_KEY_ADD:
1315                         /* if a move operation is needed it's in the log */
1316                         n--;
1317                         break;
1318                 case MOD_LOG_MOVE_KEYS:
1319                         o_dst = btrfs_node_key_ptr_offset(tm->slot);
1320                         o_src = btrfs_node_key_ptr_offset(tm->move.dst_slot);
1321                         memmove_extent_buffer(eb, o_dst, o_src,
1322                                               tm->move.nr_items * p_size);
1323                         break;
1324                 case MOD_LOG_ROOT_REPLACE:
1325                         /*
1326                          * this operation is special. for roots, this must be
1327                          * handled explicitly before rewinding.
1328                          * for non-roots, this operation may exist if the node
1329                          * was a root: root A -> child B; then A gets empty and
1330                          * B is promoted to the new root. in the mod log, we'll
1331                          * have a root-replace operation for B, a tree block
1332                          * that is no root. we simply ignore that operation.
1333                          */
1334                         break;
1335                 }
1336                 next = rb_next(&tm->node);
1337                 if (!next)
1338                         break;
1339                 tm = container_of(next, struct tree_mod_elem, node);
1340                 if (tm->logical != first_tm->logical)
1341                         break;
1342         }
1343         tree_mod_log_read_unlock(fs_info);
1344         btrfs_set_header_nritems(eb, n);
1345 }
1346
1347 /*
1348  * Called with eb read locked. If the buffer cannot be rewound, the same buffer
1349  * is returned. If rewind operations happen, a fresh buffer is returned. The
1350  * returned buffer is always read-locked. If the returned buffer is not the
1351  * input buffer, the lock on the input buffer is released and the input buffer
1352  * is freed (its refcount is decremented).
1353  */
1354 static struct extent_buffer *
1355 tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
1356                     struct extent_buffer *eb, u64 time_seq)
1357 {
1358         struct extent_buffer *eb_rewin;
1359         struct tree_mod_elem *tm;
1360
1361         if (!time_seq)
1362                 return eb;
1363
1364         if (btrfs_header_level(eb) == 0)
1365                 return eb;
1366
1367         tm = tree_mod_log_search(fs_info, eb->start, time_seq);
1368         if (!tm)
1369                 return eb;
1370
1371         btrfs_set_path_blocking(path);
1372         btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1373
1374         if (tm->op == MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1375                 BUG_ON(tm->slot != 0);
1376                 eb_rewin = alloc_dummy_extent_buffer(fs_info, eb->start,
1377                                                 eb->len);
1378                 if (!eb_rewin) {
1379                         btrfs_tree_read_unlock_blocking(eb);
1380                         free_extent_buffer(eb);
1381                         return NULL;
1382                 }
1383                 btrfs_set_header_bytenr(eb_rewin, eb->start);
1384                 btrfs_set_header_backref_rev(eb_rewin,
1385                                              btrfs_header_backref_rev(eb));
1386                 btrfs_set_header_owner(eb_rewin, btrfs_header_owner(eb));
1387                 btrfs_set_header_level(eb_rewin, btrfs_header_level(eb));
1388         } else {
1389                 eb_rewin = btrfs_clone_extent_buffer(eb);
1390                 if (!eb_rewin) {
1391                         btrfs_tree_read_unlock_blocking(eb);
1392                         free_extent_buffer(eb);
1393                         return NULL;
1394                 }
1395         }
1396
1397         btrfs_clear_path_blocking(path, NULL, BTRFS_READ_LOCK);
1398         btrfs_tree_read_unlock_blocking(eb);
1399         free_extent_buffer(eb);
1400
1401         extent_buffer_get(eb_rewin);
1402         btrfs_tree_read_lock(eb_rewin);
1403         __tree_mod_log_rewind(fs_info, eb_rewin, time_seq, tm);
1404         WARN_ON(btrfs_header_nritems(eb_rewin) >
1405                 BTRFS_NODEPTRS_PER_BLOCK(fs_info->tree_root));
1406
1407         return eb_rewin;
1408 }
1409
1410 /*
1411  * get_old_root() rewinds the state of @root's root node to the given @time_seq
1412  * value. If there are no changes, the current root->root_node is returned. If
1413  * anything changed in between, there's a fresh buffer allocated on which the
1414  * rewind operations are done. In any case, the returned buffer is read locked.
1415  * Returns NULL on error (with no locks held).
1416  */
1417 static inline struct extent_buffer *
1418 get_old_root(struct btrfs_root *root, u64 time_seq)
1419 {
1420         struct tree_mod_elem *tm;
1421         struct extent_buffer *eb = NULL;
1422         struct extent_buffer *eb_root;
1423         struct extent_buffer *old;
1424         struct tree_mod_root *old_root = NULL;
1425         u64 old_generation = 0;
1426         u64 logical;
1427
1428         eb_root = btrfs_read_lock_root_node(root);
1429         tm = __tree_mod_log_oldest_root(root->fs_info, eb_root, time_seq);
1430         if (!tm)
1431                 return eb_root;
1432
1433         if (tm->op == MOD_LOG_ROOT_REPLACE) {
1434                 old_root = &tm->old_root;
1435                 old_generation = tm->generation;
1436                 logical = old_root->logical;
1437         } else {
1438                 logical = eb_root->start;
1439         }
1440
1441         tm = tree_mod_log_search(root->fs_info, logical, time_seq);
1442         if (old_root && tm && tm->op != MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1443                 btrfs_tree_read_unlock(eb_root);
1444                 free_extent_buffer(eb_root);
1445                 old = read_tree_block(root, logical, 0);
1446                 if (WARN_ON(IS_ERR(old) || !extent_buffer_uptodate(old))) {
1447                         if (!IS_ERR(old))
1448                                 free_extent_buffer(old);
1449                         btrfs_warn(root->fs_info,
1450                                 "failed to read tree block %llu from get_old_root", logical);
1451                 } else {
1452                         eb = btrfs_clone_extent_buffer(old);
1453                         free_extent_buffer(old);
1454                 }
1455         } else if (old_root) {
1456                 btrfs_tree_read_unlock(eb_root);
1457                 free_extent_buffer(eb_root);
1458                 eb = alloc_dummy_extent_buffer(root->fs_info, logical,
1459                                         root->nodesize);
1460         } else {
1461                 btrfs_set_lock_blocking_rw(eb_root, BTRFS_READ_LOCK);
1462                 eb = btrfs_clone_extent_buffer(eb_root);
1463                 btrfs_tree_read_unlock_blocking(eb_root);
1464                 free_extent_buffer(eb_root);
1465         }
1466
1467         if (!eb)
1468                 return NULL;
1469         extent_buffer_get(eb);
1470         btrfs_tree_read_lock(eb);
1471         if (old_root) {
1472                 btrfs_set_header_bytenr(eb, eb->start);
1473                 btrfs_set_header_backref_rev(eb, BTRFS_MIXED_BACKREF_REV);
1474                 btrfs_set_header_owner(eb, btrfs_header_owner(eb_root));
1475                 btrfs_set_header_level(eb, old_root->level);
1476                 btrfs_set_header_generation(eb, old_generation);
1477         }
1478         if (tm)
1479                 __tree_mod_log_rewind(root->fs_info, eb, time_seq, tm);
1480         else
1481                 WARN_ON(btrfs_header_level(eb) != 0);
1482         WARN_ON(btrfs_header_nritems(eb) > BTRFS_NODEPTRS_PER_BLOCK(root));
1483
1484         return eb;
1485 }
1486
1487 int btrfs_old_root_level(struct btrfs_root *root, u64 time_seq)
1488 {
1489         struct tree_mod_elem *tm;
1490         int level;
1491         struct extent_buffer *eb_root = btrfs_root_node(root);
1492
1493         tm = __tree_mod_log_oldest_root(root->fs_info, eb_root, time_seq);
1494         if (tm && tm->op == MOD_LOG_ROOT_REPLACE) {
1495                 level = tm->old_root.level;
1496         } else {
1497                 level = btrfs_header_level(eb_root);
1498         }
1499         free_extent_buffer(eb_root);
1500
1501         return level;
1502 }
1503
1504 static inline int should_cow_block(struct btrfs_trans_handle *trans,
1505                                    struct btrfs_root *root,
1506                                    struct extent_buffer *buf)
1507 {
1508         if (btrfs_is_testing(root->fs_info))
1509                 return 0;
1510
1511         /* ensure we can see the force_cow */
1512         smp_rmb();
1513
1514         /*
1515          * We do not need to cow a block if
1516          * 1) this block is not created or changed in this transaction;
1517          * 2) this block does not belong to TREE_RELOC tree;
1518          * 3) the root is not forced COW.
1519          *
1520          * What is forced COW:
1521          *    when we create snapshot during committing the transaction,
1522          *    after we've finished coping src root, we must COW the shared
1523          *    block to ensure the metadata consistency.
1524          */
1525         if (btrfs_header_generation(buf) == trans->transid &&
1526             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
1527             !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
1528               btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) &&
1529             !test_bit(BTRFS_ROOT_FORCE_COW, &root->state))
1530                 return 0;
1531         return 1;
1532 }
1533
1534 /*
1535  * cows a single block, see __btrfs_cow_block for the real work.
1536  * This version of it has extra checks so that a block isn't COWed more than
1537  * once per transaction, as long as it hasn't been written yet
1538  */
1539 noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
1540                     struct btrfs_root *root, struct extent_buffer *buf,
1541                     struct extent_buffer *parent, int parent_slot,
1542                     struct extent_buffer **cow_ret)
1543 {
1544         u64 search_start;
1545         int ret;
1546
1547         if (trans->transaction != root->fs_info->running_transaction)
1548                 WARN(1, KERN_CRIT "trans %llu running %llu\n",
1549                        trans->transid,
1550                        root->fs_info->running_transaction->transid);
1551
1552         if (trans->transid != root->fs_info->generation)
1553                 WARN(1, KERN_CRIT "trans %llu running %llu\n",
1554                        trans->transid, root->fs_info->generation);
1555
1556         if (!should_cow_block(trans, root, buf)) {
1557                 trans->dirty = true;
1558                 *cow_ret = buf;
1559                 return 0;
1560         }
1561
1562         search_start = buf->start & ~((u64)SZ_1G - 1);
1563
1564         if (parent)
1565                 btrfs_set_lock_blocking(parent);
1566         btrfs_set_lock_blocking(buf);
1567
1568         ret = __btrfs_cow_block(trans, root, buf, parent,
1569                                  parent_slot, cow_ret, search_start, 0);
1570
1571         trace_btrfs_cow_block(root, buf, *cow_ret);
1572
1573         return ret;
1574 }
1575
1576 /*
1577  * helper function for defrag to decide if two blocks pointed to by a
1578  * node are actually close by
1579  */
1580 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
1581 {
1582         if (blocknr < other && other - (blocknr + blocksize) < 32768)
1583                 return 1;
1584         if (blocknr > other && blocknr - (other + blocksize) < 32768)
1585                 return 1;
1586         return 0;
1587 }
1588
1589 /*
1590  * compare two keys in a memcmp fashion
1591  */
1592 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
1593 {
1594         struct btrfs_key k1;
1595
1596         btrfs_disk_key_to_cpu(&k1, disk);
1597
1598         return btrfs_comp_cpu_keys(&k1, k2);
1599 }
1600
1601 /*
1602  * same as comp_keys only with two btrfs_key's
1603  */
1604 int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
1605 {
1606         if (k1->objectid > k2->objectid)
1607                 return 1;
1608         if (k1->objectid < k2->objectid)
1609                 return -1;
1610         if (k1->type > k2->type)
1611                 return 1;
1612         if (k1->type < k2->type)
1613                 return -1;
1614         if (k1->offset > k2->offset)
1615                 return 1;
1616         if (k1->offset < k2->offset)
1617                 return -1;
1618         return 0;
1619 }
1620
1621 /*
1622  * this is used by the defrag code to go through all the
1623  * leaves pointed to by a node and reallocate them so that
1624  * disk order is close to key order
1625  */
1626 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
1627                        struct btrfs_root *root, struct extent_buffer *parent,
1628                        int start_slot, u64 *last_ret,
1629                        struct btrfs_key *progress)
1630 {
1631         struct extent_buffer *cur;
1632         u64 blocknr;
1633         u64 gen;
1634         u64 search_start = *last_ret;
1635         u64 last_block = 0;
1636         u64 other;
1637         u32 parent_nritems;
1638         int end_slot;
1639         int i;
1640         int err = 0;
1641         int parent_level;
1642         int uptodate;
1643         u32 blocksize;
1644         int progress_passed = 0;
1645         struct btrfs_disk_key disk_key;
1646
1647         parent_level = btrfs_header_level(parent);
1648
1649         WARN_ON(trans->transaction != root->fs_info->running_transaction);
1650         WARN_ON(trans->transid != root->fs_info->generation);
1651
1652         parent_nritems = btrfs_header_nritems(parent);
1653         blocksize = root->nodesize;
1654         end_slot = parent_nritems - 1;
1655
1656         if (parent_nritems <= 1)
1657                 return 0;
1658
1659         btrfs_set_lock_blocking(parent);
1660
1661         for (i = start_slot; i <= end_slot; i++) {
1662                 int close = 1;
1663
1664                 btrfs_node_key(parent, &disk_key, i);
1665                 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
1666                         continue;
1667
1668                 progress_passed = 1;
1669                 blocknr = btrfs_node_blockptr(parent, i);
1670                 gen = btrfs_node_ptr_generation(parent, i);
1671                 if (last_block == 0)
1672                         last_block = blocknr;
1673
1674                 if (i > 0) {
1675                         other = btrfs_node_blockptr(parent, i - 1);
1676                         close = close_blocks(blocknr, other, blocksize);
1677                 }
1678                 if (!close && i < end_slot) {
1679                         other = btrfs_node_blockptr(parent, i + 1);
1680                         close = close_blocks(blocknr, other, blocksize);
1681                 }
1682                 if (close) {
1683                         last_block = blocknr;
1684                         continue;
1685                 }
1686
1687                 cur = btrfs_find_tree_block(root->fs_info, blocknr);
1688                 if (cur)
1689                         uptodate = btrfs_buffer_uptodate(cur, gen, 0);
1690                 else
1691                         uptodate = 0;
1692                 if (!cur || !uptodate) {
1693                         if (!cur) {
1694                                 cur = read_tree_block(root, blocknr, gen);
1695                                 if (IS_ERR(cur)) {
1696                                         return PTR_ERR(cur);
1697                                 } else if (!extent_buffer_uptodate(cur)) {
1698                                         free_extent_buffer(cur);
1699                                         return -EIO;
1700                                 }
1701                         } else if (!uptodate) {
1702                                 err = btrfs_read_buffer(cur, gen);
1703                                 if (err) {
1704                                         free_extent_buffer(cur);
1705                                         return err;
1706                                 }
1707                         }
1708                 }
1709                 if (search_start == 0)
1710                         search_start = last_block;
1711
1712                 btrfs_tree_lock(cur);
1713                 btrfs_set_lock_blocking(cur);
1714                 err = __btrfs_cow_block(trans, root, cur, parent, i,
1715                                         &cur, search_start,
1716                                         min(16 * blocksize,
1717                                             (end_slot - i) * blocksize));
1718                 if (err) {
1719                         btrfs_tree_unlock(cur);
1720                         free_extent_buffer(cur);
1721                         break;
1722                 }
1723                 search_start = cur->start;
1724                 last_block = cur->start;
1725                 *last_ret = search_start;
1726                 btrfs_tree_unlock(cur);
1727                 free_extent_buffer(cur);
1728         }
1729         return err;
1730 }
1731
1732 /*
1733  * The leaf data grows from end-to-front in the node.
1734  * this returns the address of the start of the last item,
1735  * which is the stop of the leaf data stack
1736  */
1737 static inline unsigned int leaf_data_end(struct btrfs_root *root,
1738                                          struct extent_buffer *leaf)
1739 {
1740         u32 nr = btrfs_header_nritems(leaf);
1741         if (nr == 0)
1742                 return BTRFS_LEAF_DATA_SIZE(root);
1743         return btrfs_item_offset_nr(leaf, nr - 1);
1744 }
1745
1746
1747 /*
1748  * search for key in the extent_buffer.  The items start at offset p,
1749  * and they are item_size apart.  There are 'max' items in p.
1750  *
1751  * the slot in the array is returned via slot, and it points to
1752  * the place where you would insert key if it is not found in
1753  * the array.
1754  *
1755  * slot may point to max if the key is bigger than all of the keys
1756  */
1757 static noinline int generic_bin_search(struct extent_buffer *eb,
1758                                        unsigned long p,
1759                                        int item_size, struct btrfs_key *key,
1760                                        int max, int *slot)
1761 {
1762         int low = 0;
1763         int high = max;
1764         int mid;
1765         int ret;
1766         struct btrfs_disk_key *tmp = NULL;
1767         struct btrfs_disk_key unaligned;
1768         unsigned long offset;
1769         char *kaddr = NULL;
1770         unsigned long map_start = 0;
1771         unsigned long map_len = 0;
1772         int err;
1773
1774         if (low > high) {
1775                 btrfs_err(eb->fs_info,
1776                  "%s: low (%d) > high (%d) eb %llu owner %llu level %d",
1777                           __func__, low, high, eb->start,
1778                           btrfs_header_owner(eb), btrfs_header_level(eb));
1779                 return -EINVAL;
1780         }
1781
1782         while (low < high) {
1783                 mid = (low + high) / 2;
1784                 offset = p + mid * item_size;
1785
1786                 if (!kaddr || offset < map_start ||
1787                     (offset + sizeof(struct btrfs_disk_key)) >
1788                     map_start + map_len) {
1789
1790                         err = map_private_extent_buffer(eb, offset,
1791                                                 sizeof(struct btrfs_disk_key),
1792                                                 &kaddr, &map_start, &map_len);
1793
1794                         if (!err) {
1795                                 tmp = (struct btrfs_disk_key *)(kaddr + offset -
1796                                                         map_start);
1797                         } else if (err == 1) {
1798                                 read_extent_buffer(eb, &unaligned,
1799                                                    offset, sizeof(unaligned));
1800                                 tmp = &unaligned;
1801                         } else {
1802                                 return err;
1803                         }
1804
1805                 } else {
1806                         tmp = (struct btrfs_disk_key *)(kaddr + offset -
1807                                                         map_start);
1808                 }
1809                 ret = comp_keys(tmp, key);
1810
1811                 if (ret < 0)
1812                         low = mid + 1;
1813                 else if (ret > 0)
1814                         high = mid;
1815                 else {
1816                         *slot = mid;
1817                         return 0;
1818                 }
1819         }
1820         *slot = low;
1821         return 1;
1822 }
1823
1824 /*
1825  * simple bin_search frontend that does the right thing for
1826  * leaves vs nodes
1827  */
1828 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
1829                       int level, int *slot)
1830 {
1831         if (level == 0)
1832                 return generic_bin_search(eb,
1833                                           offsetof(struct btrfs_leaf, items),
1834                                           sizeof(struct btrfs_item),
1835                                           key, btrfs_header_nritems(eb),
1836                                           slot);
1837         else
1838                 return generic_bin_search(eb,
1839                                           offsetof(struct btrfs_node, ptrs),
1840                                           sizeof(struct btrfs_key_ptr),
1841                                           key, btrfs_header_nritems(eb),
1842                                           slot);
1843 }
1844
1845 int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
1846                      int level, int *slot)
1847 {
1848         return bin_search(eb, key, level, slot);
1849 }
1850
1851 static void root_add_used(struct btrfs_root *root, u32 size)
1852 {
1853         spin_lock(&root->accounting_lock);
1854         btrfs_set_root_used(&root->root_item,
1855                             btrfs_root_used(&root->root_item) + size);
1856         spin_unlock(&root->accounting_lock);
1857 }
1858
1859 static void root_sub_used(struct btrfs_root *root, u32 size)
1860 {
1861         spin_lock(&root->accounting_lock);
1862         btrfs_set_root_used(&root->root_item,
1863                             btrfs_root_used(&root->root_item) - size);
1864         spin_unlock(&root->accounting_lock);
1865 }
1866
1867 /* given a node and slot number, this reads the blocks it points to.  The
1868  * extent buffer is returned with a reference taken (but unlocked).
1869  */
1870 static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
1871                                    struct extent_buffer *parent, int slot)
1872 {
1873         int level = btrfs_header_level(parent);
1874         struct extent_buffer *eb;
1875
1876         if (slot < 0 || slot >= btrfs_header_nritems(parent))
1877                 return ERR_PTR(-ENOENT);
1878
1879         BUG_ON(level == 0);
1880
1881         eb = read_tree_block(root, btrfs_node_blockptr(parent, slot),
1882                              btrfs_node_ptr_generation(parent, slot));
1883         if (!IS_ERR(eb) && !extent_buffer_uptodate(eb)) {
1884                 free_extent_buffer(eb);
1885                 eb = ERR_PTR(-EIO);
1886         }
1887
1888         return eb;
1889 }
1890
1891 /*
1892  * node level balancing, used to make sure nodes are in proper order for
1893  * item deletion.  We balance from the top down, so we have to make sure
1894  * that a deletion won't leave an node completely empty later on.
1895  */
1896 static noinline int balance_level(struct btrfs_trans_handle *trans,
1897                          struct btrfs_root *root,
1898                          struct btrfs_path *path, int level)
1899 {
1900         struct extent_buffer *right = NULL;
1901         struct extent_buffer *mid;
1902         struct extent_buffer *left = NULL;
1903         struct extent_buffer *parent = NULL;
1904         int ret = 0;
1905         int wret;
1906         int pslot;
1907         int orig_slot = path->slots[level];
1908         u64 orig_ptr;
1909
1910         if (level == 0)
1911                 return 0;
1912
1913         mid = path->nodes[level];
1914
1915         WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK &&
1916                 path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING);
1917         WARN_ON(btrfs_header_generation(mid) != trans->transid);
1918
1919         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
1920
1921         if (level < BTRFS_MAX_LEVEL - 1) {
1922                 parent = path->nodes[level + 1];
1923                 pslot = path->slots[level + 1];
1924         }
1925
1926         /*
1927          * deal with the case where there is only one pointer in the root
1928          * by promoting the node below to a root
1929          */
1930         if (!parent) {
1931                 struct extent_buffer *child;
1932
1933                 if (btrfs_header_nritems(mid) != 1)
1934                         return 0;
1935
1936                 /* promote the child to a root */
1937                 child = read_node_slot(root, mid, 0);
1938                 if (IS_ERR(child)) {
1939                         ret = PTR_ERR(child);
1940                         btrfs_handle_fs_error(root->fs_info, ret, NULL);
1941                         goto enospc;
1942                 }
1943
1944                 btrfs_tree_lock(child);
1945                 btrfs_set_lock_blocking(child);
1946                 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
1947                 if (ret) {
1948                         btrfs_tree_unlock(child);
1949                         free_extent_buffer(child);
1950                         goto enospc;
1951                 }
1952
1953                 tree_mod_log_set_root_pointer(root, child, 1);
1954                 rcu_assign_pointer(root->node, child);
1955
1956                 add_root_to_dirty_list(root);
1957                 btrfs_tree_unlock(child);
1958
1959                 path->locks[level] = 0;
1960                 path->nodes[level] = NULL;
1961                 clean_tree_block(trans, root->fs_info, mid);
1962                 btrfs_tree_unlock(mid);
1963                 /* once for the path */
1964                 free_extent_buffer(mid);
1965
1966                 root_sub_used(root, mid->len);
1967                 btrfs_free_tree_block(trans, root, mid, 0, 1);
1968                 /* once for the root ptr */
1969                 free_extent_buffer_stale(mid);
1970                 return 0;
1971         }
1972         if (btrfs_header_nritems(mid) >
1973             BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
1974                 return 0;
1975
1976         left = read_node_slot(root, parent, pslot - 1);
1977         if (IS_ERR(left))
1978                 left = NULL;
1979
1980         if (left) {
1981                 btrfs_tree_lock(left);
1982                 btrfs_set_lock_blocking(left);
1983                 wret = btrfs_cow_block(trans, root, left,
1984                                        parent, pslot - 1, &left);
1985                 if (wret) {
1986                         ret = wret;
1987                         goto enospc;
1988                 }
1989         }
1990
1991         right = read_node_slot(root, parent, pslot + 1);
1992         if (IS_ERR(right))
1993                 right = NULL;
1994
1995         if (right) {
1996                 btrfs_tree_lock(right);
1997                 btrfs_set_lock_blocking(right);
1998                 wret = btrfs_cow_block(trans, root, right,
1999                                        parent, pslot + 1, &right);
2000                 if (wret) {
2001                         ret = wret;
2002                         goto enospc;
2003                 }
2004         }
2005
2006         /* first, try to make some room in the middle buffer */
2007         if (left) {
2008                 orig_slot += btrfs_header_nritems(left);
2009                 wret = push_node_left(trans, root, left, mid, 1);
2010                 if (wret < 0)
2011                         ret = wret;
2012         }
2013
2014         /*
2015          * then try to empty the right most buffer into the middle
2016          */
2017         if (right) {
2018                 wret = push_node_left(trans, root, mid, right, 1);
2019                 if (wret < 0 && wret != -ENOSPC)
2020                         ret = wret;
2021                 if (btrfs_header_nritems(right) == 0) {
2022                         clean_tree_block(trans, root->fs_info, right);
2023                         btrfs_tree_unlock(right);
2024                         del_ptr(root, path, level + 1, pslot + 1);
2025                         root_sub_used(root, right->len);
2026                         btrfs_free_tree_block(trans, root, right, 0, 1);
2027                         free_extent_buffer_stale(right);
2028                         right = NULL;
2029                 } else {
2030                         struct btrfs_disk_key right_key;
2031                         btrfs_node_key(right, &right_key, 0);
2032                         tree_mod_log_set_node_key(root->fs_info, parent,
2033                                                   pslot + 1, 0);
2034                         btrfs_set_node_key(parent, &right_key, pslot + 1);
2035                         btrfs_mark_buffer_dirty(parent);
2036                 }
2037         }
2038         if (btrfs_header_nritems(mid) == 1) {
2039                 /*
2040                  * we're not allowed to leave a node with one item in the
2041                  * tree during a delete.  A deletion from lower in the tree
2042                  * could try to delete the only pointer in this node.
2043                  * So, pull some keys from the left.
2044                  * There has to be a left pointer at this point because
2045                  * otherwise we would have pulled some pointers from the
2046                  * right
2047                  */
2048                 if (!left) {
2049                         ret = -EROFS;
2050                         btrfs_handle_fs_error(root->fs_info, ret, NULL);
2051                         goto enospc;
2052                 }
2053                 wret = balance_node_right(trans, root, mid, left);
2054                 if (wret < 0) {
2055                         ret = wret;
2056                         goto enospc;
2057                 }
2058                 if (wret == 1) {
2059                         wret = push_node_left(trans, root, left, mid, 1);
2060                         if (wret < 0)
2061                                 ret = wret;
2062                 }
2063                 BUG_ON(wret == 1);
2064         }
2065         if (btrfs_header_nritems(mid) == 0) {
2066                 clean_tree_block(trans, root->fs_info, mid);
2067                 btrfs_tree_unlock(mid);
2068                 del_ptr(root, path, level + 1, pslot);
2069                 root_sub_used(root, mid->len);
2070                 btrfs_free_tree_block(trans, root, mid, 0, 1);
2071                 free_extent_buffer_stale(mid);
2072                 mid = NULL;
2073         } else {
2074                 /* update the parent key to reflect our changes */
2075                 struct btrfs_disk_key mid_key;
2076                 btrfs_node_key(mid, &mid_key, 0);
2077                 tree_mod_log_set_node_key(root->fs_info, parent,
2078                                           pslot, 0);
2079                 btrfs_set_node_key(parent, &mid_key, pslot);
2080                 btrfs_mark_buffer_dirty(parent);
2081         }
2082
2083         /* update the path */
2084         if (left) {
2085                 if (btrfs_header_nritems(left) > orig_slot) {
2086                         extent_buffer_get(left);
2087                         /* left was locked after cow */
2088                         path->nodes[level] = left;
2089                         path->slots[level + 1] -= 1;
2090                         path->slots[level] = orig_slot;
2091                         if (mid) {
2092                                 btrfs_tree_unlock(mid);
2093                                 free_extent_buffer(mid);
2094                         }
2095                 } else {
2096                         orig_slot -= btrfs_header_nritems(left);
2097                         path->slots[level] = orig_slot;
2098                 }
2099         }
2100         /* double check we haven't messed things up */
2101         if (orig_ptr !=
2102             btrfs_node_blockptr(path->nodes[level], path->slots[level]))
2103                 BUG();
2104 enospc:
2105         if (right) {
2106                 btrfs_tree_unlock(right);
2107                 free_extent_buffer(right);
2108         }
2109         if (left) {
2110                 if (path->nodes[level] != left)
2111                         btrfs_tree_unlock(left);
2112                 free_extent_buffer(left);
2113         }
2114         return ret;
2115 }
2116
2117 /* Node balancing for insertion.  Here we only split or push nodes around
2118  * when they are completely full.  This is also done top down, so we
2119  * have to be pessimistic.
2120  */
2121 static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
2122                                           struct btrfs_root *root,
2123                                           struct btrfs_path *path, int level)
2124 {
2125         struct extent_buffer *right = NULL;
2126         struct extent_buffer *mid;
2127         struct extent_buffer *left = NULL;
2128         struct extent_buffer *parent = NULL;
2129         int ret = 0;
2130         int wret;
2131         int pslot;
2132         int orig_slot = path->slots[level];
2133
2134         if (level == 0)
2135                 return 1;
2136
2137         mid = path->nodes[level];
2138         WARN_ON(btrfs_header_generation(mid) != trans->transid);
2139
2140         if (level < BTRFS_MAX_LEVEL - 1) {
2141                 parent = path->nodes[level + 1];
2142                 pslot = path->slots[level + 1];
2143         }
2144
2145         if (!parent)
2146                 return 1;
2147
2148         left = read_node_slot(root, parent, pslot - 1);
2149         if (IS_ERR(left))
2150                 left = NULL;
2151
2152         /* first, try to make some room in the middle buffer */
2153         if (left) {
2154                 u32 left_nr;
2155
2156                 btrfs_tree_lock(left);
2157                 btrfs_set_lock_blocking(left);
2158
2159                 left_nr = btrfs_header_nritems(left);
2160                 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
2161                         wret = 1;
2162                 } else {
2163                         ret = btrfs_cow_block(trans, root, left, parent,
2164                                               pslot - 1, &left);
2165                         if (ret)
2166                                 wret = 1;
2167                         else {
2168                                 wret = push_node_left(trans, root,
2169                                                       left, mid, 0);
2170                         }
2171                 }
2172                 if (wret < 0)
2173                         ret = wret;
2174                 if (wret == 0) {
2175                         struct btrfs_disk_key disk_key;
2176                         orig_slot += left_nr;
2177                         btrfs_node_key(mid, &disk_key, 0);
2178                         tree_mod_log_set_node_key(root->fs_info, parent,
2179                                                   pslot, 0);
2180                         btrfs_set_node_key(parent, &disk_key, pslot);
2181                         btrfs_mark_buffer_dirty(parent);
2182                         if (btrfs_header_nritems(left) > orig_slot) {
2183                                 path->nodes[level] = left;
2184                                 path->slots[level + 1] -= 1;
2185                                 path->slots[level] = orig_slot;
2186                                 btrfs_tree_unlock(mid);
2187                                 free_extent_buffer(mid);
2188                         } else {
2189                                 orig_slot -=
2190                                         btrfs_header_nritems(left);
2191                                 path->slots[level] = orig_slot;
2192                                 btrfs_tree_unlock(left);
2193                                 free_extent_buffer(left);
2194                         }
2195                         return 0;
2196                 }
2197                 btrfs_tree_unlock(left);
2198                 free_extent_buffer(left);
2199         }
2200         right = read_node_slot(root, parent, pslot + 1);
2201         if (IS_ERR(right))
2202                 right = NULL;
2203
2204         /*
2205          * then try to empty the right most buffer into the middle
2206          */
2207         if (right) {
2208                 u32 right_nr;
2209
2210                 btrfs_tree_lock(right);
2211                 btrfs_set_lock_blocking(right);
2212
2213                 right_nr = btrfs_header_nritems(right);
2214                 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
2215                         wret = 1;
2216                 } else {
2217                         ret = btrfs_cow_block(trans, root, right,
2218                                               parent, pslot + 1,
2219                                               &right);
2220                         if (ret)
2221                                 wret = 1;
2222                         else {
2223                                 wret = balance_node_right(trans, root,
2224                                                           right, mid);
2225                         }
2226                 }
2227                 if (wret < 0)
2228                         ret = wret;
2229                 if (wret == 0) {
2230                         struct btrfs_disk_key disk_key;
2231
2232                         btrfs_node_key(right, &disk_key, 0);
2233                         tree_mod_log_set_node_key(root->fs_info, parent,
2234                                                   pslot + 1, 0);
2235                         btrfs_set_node_key(parent, &disk_key, pslot + 1);
2236                         btrfs_mark_buffer_dirty(parent);
2237
2238                         if (btrfs_header_nritems(mid) <= orig_slot) {
2239                                 path->nodes[level] = right;
2240                                 path->slots[level + 1] += 1;
2241                                 path->slots[level] = orig_slot -
2242                                         btrfs_header_nritems(mid);
2243                                 btrfs_tree_unlock(mid);
2244                                 free_extent_buffer(mid);
2245                         } else {
2246                                 btrfs_tree_unlock(right);
2247                                 free_extent_buffer(right);
2248                         }
2249                         return 0;
2250                 }
2251                 btrfs_tree_unlock(right);
2252                 free_extent_buffer(right);
2253         }
2254         return 1;
2255 }
2256
2257 /*
2258  * readahead one full node of leaves, finding things that are close
2259  * to the block in 'slot', and triggering ra on them.
2260  */
2261 static void reada_for_search(struct btrfs_root *root,
2262                              struct btrfs_path *path,
2263                              int level, int slot, u64 objectid)
2264 {
2265         struct extent_buffer *node;
2266         struct btrfs_disk_key disk_key;
2267         u32 nritems;
2268         u64 search;
2269         u64 target;
2270         u64 nread = 0;
2271         u64 gen;
2272         struct extent_buffer *eb;
2273         u32 nr;
2274         u32 blocksize;
2275         u32 nscan = 0;
2276
2277         if (level != 1)
2278                 return;
2279
2280         if (!path->nodes[level])
2281                 return;
2282
2283         node = path->nodes[level];
2284
2285         search = btrfs_node_blockptr(node, slot);
2286         blocksize = root->nodesize;
2287         eb = btrfs_find_tree_block(root->fs_info, search);
2288         if (eb) {
2289                 free_extent_buffer(eb);
2290                 return;
2291         }
2292
2293         target = search;
2294
2295         nritems = btrfs_header_nritems(node);
2296         nr = slot;
2297
2298         while (1) {
2299                 if (path->reada == READA_BACK) {
2300                         if (nr == 0)
2301                                 break;
2302                         nr--;
2303                 } else if (path->reada == READA_FORWARD) {
2304                         nr++;
2305                         if (nr >= nritems)
2306                                 break;
2307                 }
2308                 if (path->reada == READA_BACK && objectid) {
2309                         btrfs_node_key(node, &disk_key, nr);
2310                         if (btrfs_disk_key_objectid(&disk_key) != objectid)
2311                                 break;
2312                 }
2313                 search = btrfs_node_blockptr(node, nr);
2314                 if ((search <= target && target - search <= 65536) ||
2315                     (search > target && search - target <= 65536)) {
2316                         gen = btrfs_node_ptr_generation(node, nr);
2317                         readahead_tree_block(root, search);
2318                         nread += blocksize;
2319                 }
2320                 nscan++;
2321                 if ((nread > 65536 || nscan > 32))
2322                         break;
2323         }
2324 }
2325
2326 static noinline void reada_for_balance(struct btrfs_root *root,
2327                                        struct btrfs_path *path, int level)
2328 {
2329         int slot;
2330         int nritems;
2331         struct extent_buffer *parent;
2332         struct extent_buffer *eb;
2333         u64 gen;
2334         u64 block1 = 0;
2335         u64 block2 = 0;
2336
2337         parent = path->nodes[level + 1];
2338         if (!parent)
2339                 return;
2340
2341         nritems = btrfs_header_nritems(parent);
2342         slot = path->slots[level + 1];
2343
2344         if (slot > 0) {
2345                 block1 = btrfs_node_blockptr(parent, slot - 1);
2346                 gen = btrfs_node_ptr_generation(parent, slot - 1);
2347                 eb = btrfs_find_tree_block(root->fs_info, block1);
2348                 /*
2349                  * if we get -eagain from btrfs_buffer_uptodate, we
2350                  * don't want to return eagain here.  That will loop
2351                  * forever
2352                  */
2353                 if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
2354                         block1 = 0;
2355                 free_extent_buffer(eb);
2356         }
2357         if (slot + 1 < nritems) {
2358                 block2 = btrfs_node_blockptr(parent, slot + 1);
2359                 gen = btrfs_node_ptr_generation(parent, slot + 1);
2360                 eb = btrfs_find_tree_block(root->fs_info, block2);
2361                 if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
2362                         block2 = 0;
2363                 free_extent_buffer(eb);
2364         }
2365
2366         if (block1)
2367                 readahead_tree_block(root, block1);
2368         if (block2)
2369                 readahead_tree_block(root, block2);
2370 }
2371
2372
2373 /*
2374  * when we walk down the tree, it is usually safe to unlock the higher layers
2375  * in the tree.  The exceptions are when our path goes through slot 0, because
2376  * operations on the tree might require changing key pointers higher up in the
2377  * tree.
2378  *
2379  * callers might also have set path->keep_locks, which tells this code to keep
2380  * the lock if the path points to the last slot in the block.  This is part of
2381  * walking through the tree, and selecting the next slot in the higher block.
2382  *
2383  * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
2384  * if lowest_unlock is 1, level 0 won't be unlocked
2385  */
2386 static noinline void unlock_up(struct btrfs_path *path, int level,
2387                                int lowest_unlock, int min_write_lock_level,
2388                                int *write_lock_level)
2389 {
2390         int i;
2391         int skip_level = level;
2392         int no_skips = 0;
2393         struct extent_buffer *t;
2394
2395         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2396                 if (!path->nodes[i])
2397                         break;
2398                 if (!path->locks[i])
2399                         break;
2400                 if (!no_skips && path->slots[i] == 0) {
2401                         skip_level = i + 1;
2402                         continue;
2403                 }
2404                 if (!no_skips && path->keep_locks) {
2405                         u32 nritems;
2406                         t = path->nodes[i];
2407                         nritems = btrfs_header_nritems(t);
2408                         if (nritems < 1 || path->slots[i] >= nritems - 1) {
2409                                 skip_level = i + 1;
2410                                 continue;
2411                         }
2412                 }
2413                 if (skip_level < i && i >= lowest_unlock)
2414                         no_skips = 1;
2415
2416                 t = path->nodes[i];
2417                 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
2418                         btrfs_tree_unlock_rw(t, path->locks[i]);
2419                         path->locks[i] = 0;
2420                         if (write_lock_level &&
2421                             i > min_write_lock_level &&
2422                             i <= *write_lock_level) {
2423                                 *write_lock_level = i - 1;
2424                         }
2425                 }
2426         }
2427 }
2428
2429 /*
2430  * This releases any locks held in the path starting at level and
2431  * going all the way up to the root.
2432  *
2433  * btrfs_search_slot will keep the lock held on higher nodes in a few
2434  * corner cases, such as COW of the block at slot zero in the node.  This
2435  * ignores those rules, and it should only be called when there are no
2436  * more updates to be done higher up in the tree.
2437  */
2438 noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
2439 {
2440         int i;
2441
2442         if (path->keep_locks)
2443                 return;
2444
2445         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2446                 if (!path->nodes[i])
2447                         continue;
2448                 if (!path->locks[i])
2449                         continue;
2450                 btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]);
2451                 path->locks[i] = 0;
2452         }
2453 }
2454
2455 /*
2456  * helper function for btrfs_search_slot.  The goal is to find a block
2457  * in cache without setting the path to blocking.  If we find the block
2458  * we return zero and the path is unchanged.
2459  *
2460  * If we can't find the block, we set the path blocking and do some
2461  * reada.  -EAGAIN is returned and the search must be repeated.
2462  */
2463 static int
2464 read_block_for_search(struct btrfs_trans_handle *trans,
2465                        struct btrfs_root *root, struct btrfs_path *p,
2466                        struct extent_buffer **eb_ret, int level, int slot,
2467                        struct btrfs_key *key, u64 time_seq)
2468 {
2469         u64 blocknr;
2470         u64 gen;
2471         struct extent_buffer *b = *eb_ret;
2472         struct extent_buffer *tmp;
2473         int ret;
2474
2475         blocknr = btrfs_node_blockptr(b, slot);
2476         gen = btrfs_node_ptr_generation(b, slot);
2477
2478         tmp = btrfs_find_tree_block(root->fs_info, blocknr);
2479         if (tmp) {
2480                 /* first we do an atomic uptodate check */
2481                 if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) {
2482                         *eb_ret = tmp;
2483                         return 0;
2484                 }
2485
2486                 /* the pages were up to date, but we failed
2487                  * the generation number check.  Do a full
2488                  * read for the generation number that is correct.
2489                  * We must do this without dropping locks so
2490                  * we can trust our generation number
2491                  */
2492                 btrfs_set_path_blocking(p);
2493
2494                 /* now we're allowed to do a blocking uptodate check */
2495                 ret = btrfs_read_buffer(tmp, gen);
2496                 if (!ret) {
2497                         *eb_ret = tmp;
2498                         return 0;
2499                 }
2500                 free_extent_buffer(tmp);
2501                 btrfs_release_path(p);
2502                 return -EIO;
2503         }
2504
2505         /*
2506          * reduce lock contention at high levels
2507          * of the btree by dropping locks before
2508          * we read.  Don't release the lock on the current
2509          * level because we need to walk this node to figure
2510          * out which blocks to read.
2511          */
2512         btrfs_unlock_up_safe(p, level + 1);
2513         btrfs_set_path_blocking(p);
2514
2515         free_extent_buffer(tmp);
2516         if (p->reada != READA_NONE)
2517                 reada_for_search(root, p, level, slot, key->objectid);
2518
2519         btrfs_release_path(p);
2520
2521         ret = -EAGAIN;
2522         tmp = read_tree_block(root, blocknr, 0);
2523         if (!IS_ERR(tmp)) {
2524                 /*
2525                  * If the read above didn't mark this buffer up to date,
2526                  * it will never end up being up to date.  Set ret to EIO now
2527                  * and give up so that our caller doesn't loop forever
2528                  * on our EAGAINs.
2529                  */
2530                 if (!btrfs_buffer_uptodate(tmp, 0, 0))
2531                         ret = -EIO;
2532                 free_extent_buffer(tmp);
2533         } else {
2534                 ret = PTR_ERR(tmp);
2535         }
2536         return ret;
2537 }
2538
2539 /*
2540  * helper function for btrfs_search_slot.  This does all of the checks
2541  * for node-level blocks and does any balancing required based on
2542  * the ins_len.
2543  *
2544  * If no extra work was required, zero is returned.  If we had to
2545  * drop the path, -EAGAIN is returned and btrfs_search_slot must
2546  * start over
2547  */
2548 static int
2549 setup_nodes_for_search(struct btrfs_trans_handle *trans,
2550                        struct btrfs_root *root, struct btrfs_path *p,
2551                        struct extent_buffer *b, int level, int ins_len,
2552                        int *write_lock_level)
2553 {
2554         int ret;
2555         if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
2556             BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
2557                 int sret;
2558
2559                 if (*write_lock_level < level + 1) {
2560                         *write_lock_level = level + 1;
2561                         btrfs_release_path(p);
2562                         goto again;
2563                 }
2564
2565                 btrfs_set_path_blocking(p);
2566                 reada_for_balance(root, p, level);
2567                 sret = split_node(trans, root, p, level);
2568                 btrfs_clear_path_blocking(p, NULL, 0);
2569
2570                 BUG_ON(sret > 0);
2571                 if (sret) {
2572                         ret = sret;
2573                         goto done;
2574                 }
2575                 b = p->nodes[level];
2576         } else if (ins_len < 0 && btrfs_header_nritems(b) <
2577                    BTRFS_NODEPTRS_PER_BLOCK(root) / 2) {
2578                 int sret;
2579
2580                 if (*write_lock_level < level + 1) {
2581                         *write_lock_level = level + 1;
2582                         btrfs_release_path(p);
2583                         goto again;
2584                 }
2585
2586                 btrfs_set_path_blocking(p);
2587                 reada_for_balance(root, p, level);
2588                 sret = balance_level(trans, root, p, level);
2589                 btrfs_clear_path_blocking(p, NULL, 0);
2590
2591                 if (sret) {
2592                         ret = sret;
2593                         goto done;
2594                 }
2595                 b = p->nodes[level];
2596                 if (!b) {
2597                         btrfs_release_path(p);
2598                         goto again;
2599                 }
2600                 BUG_ON(btrfs_header_nritems(b) == 1);
2601         }
2602         return 0;
2603
2604 again:
2605         ret = -EAGAIN;
2606 done:
2607         return ret;
2608 }
2609
2610 static void key_search_validate(struct extent_buffer *b,
2611                                 struct btrfs_key *key,
2612                                 int level)
2613 {
2614 #ifdef CONFIG_BTRFS_ASSERT
2615         struct btrfs_disk_key disk_key;
2616
2617         btrfs_cpu_key_to_disk(&disk_key, key);
2618
2619         if (level == 0)
2620                 ASSERT(!memcmp_extent_buffer(b, &disk_key,
2621                     offsetof(struct btrfs_leaf, items[0].key),
2622                     sizeof(disk_key)));
2623         else
2624                 ASSERT(!memcmp_extent_buffer(b, &disk_key,
2625                     offsetof(struct btrfs_node, ptrs[0].key),
2626                     sizeof(disk_key)));
2627 #endif
2628 }
2629
2630 static int key_search(struct extent_buffer *b, struct btrfs_key *key,
2631                       int level, int *prev_cmp, int *slot)
2632 {
2633         if (*prev_cmp != 0) {
2634                 *prev_cmp = bin_search(b, key, level, slot);
2635                 return *prev_cmp;
2636         }
2637
2638         key_search_validate(b, key, level);
2639         *slot = 0;
2640
2641         return 0;
2642 }
2643
2644 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
2645                 u64 iobjectid, u64 ioff, u8 key_type,
2646                 struct btrfs_key *found_key)
2647 {
2648         int ret;
2649         struct btrfs_key key;
2650         struct extent_buffer *eb;
2651
2652         ASSERT(path);
2653         ASSERT(found_key);
2654
2655         key.type = key_type;
2656         key.objectid = iobjectid;
2657         key.offset = ioff;
2658
2659         ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
2660         if (ret < 0)
2661                 return ret;
2662
2663         eb = path->nodes[0];
2664         if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
2665                 ret = btrfs_next_leaf(fs_root, path);
2666                 if (ret)
2667                         return ret;
2668                 eb = path->nodes[0];
2669         }
2670
2671         btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
2672         if (found_key->type != key.type ||
2673                         found_key->objectid != key.objectid)
2674                 return 1;
2675
2676         return 0;
2677 }
2678
2679 /*
2680  * look for key in the tree.  path is filled in with nodes along the way
2681  * if key is found, we return zero and you can find the item in the leaf
2682  * level of the path (level 0)
2683  *
2684  * If the key isn't found, the path points to the slot where it should
2685  * be inserted, and 1 is returned.  If there are other errors during the
2686  * search a negative error number is returned.
2687  *
2688  * if ins_len > 0, nodes and leaves will be split as we walk down the
2689  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
2690  * possible)
2691  */
2692 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
2693                       *root, struct btrfs_key *key, struct btrfs_path *p, int
2694                       ins_len, int cow)
2695 {
2696         struct extent_buffer *b;
2697         int slot;
2698         int ret;
2699         int err;
2700         int level;
2701         int lowest_unlock = 1;
2702         int root_lock;
2703         /* everything at write_lock_level or lower must be write locked */
2704         int write_lock_level = 0;
2705         u8 lowest_level = 0;
2706         int min_write_lock_level;
2707         int prev_cmp;
2708
2709         lowest_level = p->lowest_level;
2710         WARN_ON(lowest_level && ins_len > 0);
2711         WARN_ON(p->nodes[0] != NULL);
2712         BUG_ON(!cow && ins_len);
2713
2714         if (ins_len < 0) {
2715                 lowest_unlock = 2;
2716
2717                 /* when we are removing items, we might have to go up to level
2718                  * two as we update tree pointers  Make sure we keep write
2719                  * for those levels as well
2720                  */
2721                 write_lock_level = 2;
2722         } else if (ins_len > 0) {
2723                 /*
2724                  * for inserting items, make sure we have a write lock on
2725                  * level 1 so we can update keys
2726                  */
2727                 write_lock_level = 1;
2728         }
2729
2730         if (!cow)
2731                 write_lock_level = -1;
2732
2733         if (cow && (p->keep_locks || p->lowest_level))
2734                 write_lock_level = BTRFS_MAX_LEVEL;
2735
2736         min_write_lock_level = write_lock_level;
2737
2738 again:
2739         prev_cmp = -1;
2740         /*
2741          * we try very hard to do read locks on the root
2742          */
2743         root_lock = BTRFS_READ_LOCK;
2744         level = 0;
2745         if (p->search_commit_root) {
2746                 /*
2747                  * the commit roots are read only
2748                  * so we always do read locks
2749                  */
2750                 if (p->need_commit_sem)
2751                         down_read(&root->fs_info->commit_root_sem);
2752                 b = root->commit_root;
2753                 extent_buffer_get(b);
2754                 level = btrfs_header_level(b);
2755                 if (p->need_commit_sem)
2756                         up_read(&root->fs_info->commit_root_sem);
2757                 if (!p->skip_locking)
2758                         btrfs_tree_read_lock(b);
2759         } else {
2760                 if (p->skip_locking) {
2761                         b = btrfs_root_node(root);
2762                         level = btrfs_header_level(b);
2763                 } else {
2764                         /* we don't know the level of the root node
2765                          * until we actually have it read locked
2766                          */
2767                         b = btrfs_read_lock_root_node(root);
2768                         level = btrfs_header_level(b);
2769                         if (level <= write_lock_level) {
2770                                 /* whoops, must trade for write lock */
2771                                 btrfs_tree_read_unlock(b);
2772                                 free_extent_buffer(b);
2773                                 b = btrfs_lock_root_node(root);
2774                                 root_lock = BTRFS_WRITE_LOCK;
2775
2776                                 /* the level might have changed, check again */
2777                                 level = btrfs_header_level(b);
2778                         }
2779                 }
2780         }
2781         p->nodes[level] = b;
2782         if (!p->skip_locking)
2783                 p->locks[level] = root_lock;
2784
2785         while (b) {
2786                 level = btrfs_header_level(b);
2787
2788                 /*
2789                  * setup the path here so we can release it under lock
2790                  * contention with the cow code
2791                  */
2792                 if (cow) {
2793                         /*
2794                          * if we don't really need to cow this block
2795                          * then we don't want to set the path blocking,
2796                          * so we test it here
2797                          */
2798                         if (!should_cow_block(trans, root, b)) {
2799                                 trans->dirty = true;
2800                                 goto cow_done;
2801                         }
2802
2803                         /*
2804                          * must have write locks on this node and the
2805                          * parent
2806                          */
2807                         if (level > write_lock_level ||
2808                             (level + 1 > write_lock_level &&
2809                             level + 1 < BTRFS_MAX_LEVEL &&
2810                             p->nodes[level + 1])) {
2811                                 write_lock_level = level + 1;
2812                                 btrfs_release_path(p);
2813                                 goto again;
2814                         }
2815
2816                         btrfs_set_path_blocking(p);
2817                         err = btrfs_cow_block(trans, root, b,
2818                                               p->nodes[level + 1],
2819                                               p->slots[level + 1], &b);
2820                         if (err) {
2821                                 ret = err;
2822                                 goto done;
2823                         }
2824                 }
2825 cow_done:
2826                 p->nodes[level] = b;
2827                 btrfs_clear_path_blocking(p, NULL, 0);
2828
2829                 /*
2830                  * we have a lock on b and as long as we aren't changing
2831                  * the tree, there is no way to for the items in b to change.
2832                  * It is safe to drop the lock on our parent before we
2833                  * go through the expensive btree search on b.
2834                  *
2835                  * If we're inserting or deleting (ins_len != 0), then we might
2836                  * be changing slot zero, which may require changing the parent.
2837                  * So, we can't drop the lock until after we know which slot
2838                  * we're operating on.
2839                  */
2840                 if (!ins_len && !p->keep_locks) {
2841                         int u = level + 1;
2842
2843                         if (u < BTRFS_MAX_LEVEL && p->locks[u]) {
2844                                 btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]);
2845                                 p->locks[u] = 0;
2846                         }
2847                 }
2848
2849                 ret = key_search(b, key, level, &prev_cmp, &slot);
2850                 if (ret < 0)
2851                         goto done;
2852
2853                 if (level != 0) {
2854                         int dec = 0;
2855                         if (ret && slot > 0) {
2856                                 dec = 1;
2857                                 slot -= 1;
2858                         }
2859                         p->slots[level] = slot;
2860                         err = setup_nodes_for_search(trans, root, p, b, level,
2861                                              ins_len, &write_lock_level);
2862                         if (err == -EAGAIN)
2863                                 goto again;
2864                         if (err) {
2865                                 ret = err;
2866                                 goto done;
2867                         }
2868                         b = p->nodes[level];
2869                         slot = p->slots[level];
2870
2871                         /*
2872                          * slot 0 is special, if we change the key
2873                          * we have to update the parent pointer
2874                          * which means we must have a write lock
2875                          * on the parent
2876                          */
2877                         if (slot == 0 && ins_len &&
2878                             write_lock_level < level + 1) {
2879                                 write_lock_level = level + 1;
2880                                 btrfs_release_path(p);
2881                                 goto again;
2882                         }
2883
2884                         unlock_up(p, level, lowest_unlock,
2885                                   min_write_lock_level, &write_lock_level);
2886
2887                         if (level == lowest_level) {
2888                                 if (dec)
2889                                         p->slots[level]++;
2890                                 goto done;
2891                         }
2892
2893                         err = read_block_for_search(trans, root, p,
2894                                                     &b, level, slot, key, 0);
2895                         if (err == -EAGAIN)
2896                                 goto again;
2897                         if (err) {
2898                                 ret = err;
2899                                 goto done;
2900                         }
2901
2902                         if (!p->skip_locking) {
2903                                 level = btrfs_header_level(b);
2904                                 if (level <= write_lock_level) {
2905                                         err = btrfs_try_tree_write_lock(b);
2906                                         if (!err) {
2907                                                 btrfs_set_path_blocking(p);
2908                                                 btrfs_tree_lock(b);
2909                                                 btrfs_clear_path_blocking(p, b,
2910                                                                   BTRFS_WRITE_LOCK);
2911                                         }
2912                                         p->locks[level] = BTRFS_WRITE_LOCK;
2913                                 } else {
2914                                         err = btrfs_tree_read_lock_atomic(b);
2915                                         if (!err) {
2916                                                 btrfs_set_path_blocking(p);
2917                                                 btrfs_tree_read_lock(b);
2918                                                 btrfs_clear_path_blocking(p, b,
2919                                                                   BTRFS_READ_LOCK);
2920                                         }
2921                                         p->locks[level] = BTRFS_READ_LOCK;
2922                                 }
2923                                 p->nodes[level] = b;
2924                         }
2925                 } else {
2926                         p->slots[level] = slot;
2927                         if (ins_len > 0 &&
2928                             btrfs_leaf_free_space(root, b) < ins_len) {
2929                                 if (write_lock_level < 1) {
2930                                         write_lock_level = 1;
2931                                         btrfs_release_path(p);
2932                                         goto again;
2933                                 }
2934
2935                                 btrfs_set_path_blocking(p);
2936                                 err = split_leaf(trans, root, key,
2937                                                  p, ins_len, ret == 0);
2938                                 btrfs_clear_path_blocking(p, NULL, 0);
2939
2940                                 BUG_ON(err > 0);
2941                                 if (err) {
2942                                         ret = err;
2943                                         goto done;
2944                                 }
2945                         }
2946                         if (!p->search_for_split)
2947                                 unlock_up(p, level, lowest_unlock,
2948                                           min_write_lock_level, &write_lock_level);
2949                         goto done;
2950                 }
2951         }
2952         ret = 1;
2953 done:
2954         /*
2955          * we don't really know what they plan on doing with the path
2956          * from here on, so for now just mark it as blocking
2957          */
2958         if (!p->leave_spinning)
2959                 btrfs_set_path_blocking(p);
2960         if (ret < 0 && !p->skip_release_on_error)
2961                 btrfs_release_path(p);
2962         return ret;
2963 }
2964
2965 /*
2966  * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2967  * current state of the tree together with the operations recorded in the tree
2968  * modification log to search for the key in a previous version of this tree, as
2969  * denoted by the time_seq parameter.
2970  *
2971  * Naturally, there is no support for insert, delete or cow operations.
2972  *
2973  * The resulting path and return value will be set up as if we called
2974  * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
2975  */
2976 int btrfs_search_old_slot(struct btrfs_root *root, struct btrfs_key *key,
2977                           struct btrfs_path *p, u64 time_seq)
2978 {
2979         struct extent_buffer *b;
2980         int slot;
2981         int ret;
2982         int err;
2983         int level;
2984         int lowest_unlock = 1;
2985         u8 lowest_level = 0;
2986         int prev_cmp = -1;
2987
2988         lowest_level = p->lowest_level;
2989         WARN_ON(p->nodes[0] != NULL);
2990
2991         if (p->search_commit_root) {
2992                 BUG_ON(time_seq);
2993                 return btrfs_search_slot(NULL, root, key, p, 0, 0);
2994         }
2995
2996 again:
2997         b = get_old_root(root, time_seq);
2998         level = btrfs_header_level(b);
2999         p->locks[level] = BTRFS_READ_LOCK;
3000
3001         while (b) {
3002                 level = btrfs_header_level(b);
3003                 p->nodes[level] = b;
3004                 btrfs_clear_path_blocking(p, NULL, 0);
3005
3006                 /*
3007                  * we have a lock on b and as long as we aren't changing
3008                  * the tree, there is no way to for the items in b to change.
3009                  * It is safe to drop the lock on our parent before we
3010                  * go through the expensive btree search on b.
3011                  */
3012                 btrfs_unlock_up_safe(p, level + 1);
3013
3014                 /*
3015                  * Since we can unwind ebs we want to do a real search every
3016                  * time.
3017                  */
3018                 prev_cmp = -1;
3019                 ret = key_search(b, key, level, &prev_cmp, &slot);
3020
3021                 if (level != 0) {
3022                         int dec = 0;
3023                         if (ret && slot > 0) {
3024                                 dec = 1;
3025                                 slot -= 1;
3026                         }
3027                         p->slots[level] = slot;
3028                         unlock_up(p, level, lowest_unlock, 0, NULL);
3029
3030                         if (level == lowest_level) {
3031                                 if (dec)
3032                                         p->slots[level]++;
3033                                 goto done;
3034                         }
3035
3036                         err = read_block_for_search(NULL, root, p, &b, level,
3037                                                     slot, key, time_seq);
3038                         if (err == -EAGAIN)
3039                                 goto again;
3040                         if (err) {
3041                                 ret = err;
3042                                 goto done;
3043                         }
3044
3045                         level = btrfs_header_level(b);
3046                         err = btrfs_tree_read_lock_atomic(b);
3047                         if (!err) {
3048                                 btrfs_set_path_blocking(p);
3049                                 btrfs_tree_read_lock(b);
3050                                 btrfs_clear_path_blocking(p, b,
3051                                                           BTRFS_READ_LOCK);
3052                         }
3053                         b = tree_mod_log_rewind(root->fs_info, p, b, time_seq);
3054                         if (!b) {
3055                                 ret = -ENOMEM;
3056                                 goto done;
3057                         }
3058                         p->locks[level] = BTRFS_READ_LOCK;
3059                         p->nodes[level] = b;
3060                 } else {
3061                         p->slots[level] = slot;
3062                         unlock_up(p, level, lowest_unlock, 0, NULL);
3063                         goto done;
3064                 }
3065         }
3066         ret = 1;
3067 done:
3068         if (!p->leave_spinning)
3069                 btrfs_set_path_blocking(p);
3070         if (ret < 0)
3071                 btrfs_release_path(p);
3072
3073         return ret;
3074 }
3075
3076 /*
3077  * helper to use instead of search slot if no exact match is needed but
3078  * instead the next or previous item should be returned.
3079  * When find_higher is true, the next higher item is returned, the next lower
3080  * otherwise.
3081  * When return_any and find_higher are both true, and no higher item is found,
3082  * return the next lower instead.
3083  * When return_any is true and find_higher is false, and no lower item is found,
3084  * return the next higher instead.
3085  * It returns 0 if any item is found, 1 if none is found (tree empty), and
3086  * < 0 on error
3087  */
3088 int btrfs_search_slot_for_read(struct btrfs_root *root,
3089                                struct btrfs_key *key, struct btrfs_path *p,
3090                                int find_higher, int return_any)
3091 {
3092         int ret;
3093         struct extent_buffer *leaf;
3094
3095 again:
3096         ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
3097         if (ret <= 0)
3098                 return ret;
3099         /*
3100          * a return value of 1 means the path is at the position where the
3101          * item should be inserted. Normally this is the next bigger item,
3102          * but in case the previous item is the last in a leaf, path points
3103          * to the first free slot in the previous leaf, i.e. at an invalid
3104          * item.
3105          */
3106         leaf = p->nodes[0];
3107
3108         if (find_higher) {
3109                 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
3110                         ret = btrfs_next_leaf(root, p);
3111                         if (ret <= 0)
3112                                 return ret;
3113                         if (!return_any)
3114                                 return 1;
3115                         /*
3116                          * no higher item found, return the next
3117                          * lower instead
3118                          */
3119                         return_any = 0;
3120                         find_higher = 0;
3121                         btrfs_release_path(p);
3122                         goto again;
3123                 }
3124         } else {
3125                 if (p->slots[0] == 0) {
3126                         ret = btrfs_prev_leaf(root, p);
3127                         if (ret < 0)
3128                                 return ret;
3129                         if (!ret) {
3130                                 leaf = p->nodes[0];
3131                                 if (p->slots[0] == btrfs_header_nritems(leaf))
3132                                         p->slots[0]--;
3133                                 return 0;
3134                         }
3135                         if (!return_any)
3136                                 return 1;
3137                         /*
3138                          * no lower item found, return the next
3139                          * higher instead
3140