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