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