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