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