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