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