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