2 * Copyright (C) 2007,2008 Oracle. All rights reserved.
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.
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.
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.
19 #include <linux/sched.h>
22 #include "transaction.h"
23 #include "print-tree.h"
26 static int split_node(struct btrfs_trans_handle
*trans
, struct btrfs_root
27 *root
, struct btrfs_path
*path
, int level
);
28 static int split_leaf(struct btrfs_trans_handle
*trans
, struct btrfs_root
29 *root
, struct btrfs_key
*ins_key
,
30 struct btrfs_path
*path
, int data_size
, int extend
);
31 static int push_node_left(struct btrfs_trans_handle
*trans
,
32 struct btrfs_root
*root
, struct extent_buffer
*dst
,
33 struct extent_buffer
*src
, int empty
);
34 static int balance_node_right(struct btrfs_trans_handle
*trans
,
35 struct btrfs_root
*root
,
36 struct extent_buffer
*dst_buf
,
37 struct extent_buffer
*src_buf
);
38 static int del_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
39 struct btrfs_path
*path
, int level
, int slot
);
41 inline void btrfs_init_path(struct btrfs_path
*p
)
43 memset(p
, 0, sizeof(*p
));
46 struct btrfs_path
*btrfs_alloc_path(void)
48 struct btrfs_path
*path
;
49 path
= kmem_cache_alloc(btrfs_path_cachep
, GFP_NOFS
);
51 btrfs_init_path(path
);
58 * set all locked nodes in the path to blocking locks. This should
59 * be done before scheduling
61 noinline
void btrfs_set_path_blocking(struct btrfs_path
*p
)
64 for (i
= 0; i
< BTRFS_MAX_LEVEL
; i
++) {
65 if (p
->nodes
[i
] && p
->locks
[i
])
66 btrfs_set_lock_blocking(p
->nodes
[i
]);
71 * reset all the locked nodes in the patch to spinning locks.
73 noinline
void btrfs_clear_path_blocking(struct btrfs_path
*p
)
76 for (i
= 0; i
< BTRFS_MAX_LEVEL
; i
++) {
77 if (p
->nodes
[i
] && p
->locks
[i
])
78 btrfs_clear_lock_blocking(p
->nodes
[i
]);
82 /* this also releases the path */
83 void btrfs_free_path(struct btrfs_path
*p
)
85 btrfs_release_path(NULL
, p
);
86 kmem_cache_free(btrfs_path_cachep
, p
);
90 * path release drops references on the extent buffers in the path
91 * and it drops any locks held by this path
93 * It is safe to call this on paths that no locks or extent buffers held.
95 noinline
void btrfs_release_path(struct btrfs_root
*root
, struct btrfs_path
*p
)
99 for (i
= 0; i
< BTRFS_MAX_LEVEL
; i
++) {
104 btrfs_tree_unlock(p
->nodes
[i
]);
107 free_extent_buffer(p
->nodes
[i
]);
113 * safely gets a reference on the root node of a tree. A lock
114 * is not taken, so a concurrent writer may put a different node
115 * at the root of the tree. See btrfs_lock_root_node for the
118 * The extent buffer returned by this has a reference taken, so
119 * it won't disappear. It may stop being the root of the tree
120 * at any time because there are no locks held.
122 struct extent_buffer
*btrfs_root_node(struct btrfs_root
*root
)
124 struct extent_buffer
*eb
;
125 spin_lock(&root
->node_lock
);
127 extent_buffer_get(eb
);
128 spin_unlock(&root
->node_lock
);
132 /* loop around taking references on and locking the root node of the
133 * tree until you end up with a lock on the root. A locked buffer
134 * is returned, with a reference held.
136 struct extent_buffer
*btrfs_lock_root_node(struct btrfs_root
*root
)
138 struct extent_buffer
*eb
;
141 eb
= btrfs_root_node(root
);
144 spin_lock(&root
->node_lock
);
145 if (eb
== root
->node
) {
146 spin_unlock(&root
->node_lock
);
149 spin_unlock(&root
->node_lock
);
151 btrfs_tree_unlock(eb
);
152 free_extent_buffer(eb
);
157 /* cowonly root (everything not a reference counted cow subvolume), just get
158 * put onto a simple dirty list. transaction.c walks this to make sure they
159 * get properly updated on disk.
161 static void add_root_to_dirty_list(struct btrfs_root
*root
)
163 if (root
->track_dirty
&& list_empty(&root
->dirty_list
)) {
164 list_add(&root
->dirty_list
,
165 &root
->fs_info
->dirty_cowonly_roots
);
170 * used by snapshot creation to make a copy of a root for a tree with
171 * a given objectid. The buffer with the new root node is returned in
172 * cow_ret, and this func returns zero on success or a negative error code.
174 int btrfs_copy_root(struct btrfs_trans_handle
*trans
,
175 struct btrfs_root
*root
,
176 struct extent_buffer
*buf
,
177 struct extent_buffer
**cow_ret
, u64 new_root_objectid
)
179 struct extent_buffer
*cow
;
183 struct btrfs_root
*new_root
;
185 new_root
= kmalloc(sizeof(*new_root
), GFP_NOFS
);
189 memcpy(new_root
, root
, sizeof(*new_root
));
190 new_root
->root_key
.objectid
= new_root_objectid
;
192 WARN_ON(root
->ref_cows
&& trans
->transid
!=
193 root
->fs_info
->running_transaction
->transid
);
194 WARN_ON(root
->ref_cows
&& trans
->transid
!= root
->last_trans
);
196 level
= btrfs_header_level(buf
);
197 nritems
= btrfs_header_nritems(buf
);
199 cow
= btrfs_alloc_free_block(trans
, new_root
, buf
->len
, 0,
200 new_root_objectid
, trans
->transid
,
201 level
, buf
->start
, 0);
207 copy_extent_buffer(cow
, buf
, 0, 0, cow
->len
);
208 btrfs_set_header_bytenr(cow
, cow
->start
);
209 btrfs_set_header_generation(cow
, trans
->transid
);
210 btrfs_set_header_owner(cow
, new_root_objectid
);
211 btrfs_clear_header_flag(cow
, BTRFS_HEADER_FLAG_WRITTEN
);
213 write_extent_buffer(cow
, root
->fs_info
->fsid
,
214 (unsigned long)btrfs_header_fsid(cow
),
217 WARN_ON(btrfs_header_generation(buf
) > trans
->transid
);
218 ret
= btrfs_inc_ref(trans
, new_root
, buf
, cow
, NULL
);
224 btrfs_mark_buffer_dirty(cow
);
230 * does the dirty work in cow of a single block. The parent block (if
231 * supplied) is updated to point to the new cow copy. The new buffer is marked
232 * dirty and returned locked. If you modify the block it needs to be marked
235 * search_start -- an allocation hint for the new block
237 * empty_size -- a hint that you plan on doing more cow. This is the size in
238 * bytes the allocator should try to find free next to the block it returns.
239 * This is just a hint and may be ignored by the allocator.
241 * prealloc_dest -- if you have already reserved a destination for the cow,
242 * this uses that block instead of allocating a new one.
243 * btrfs_alloc_reserved_extent is used to finish the allocation.
245 static noinline
int __btrfs_cow_block(struct btrfs_trans_handle
*trans
,
246 struct btrfs_root
*root
,
247 struct extent_buffer
*buf
,
248 struct extent_buffer
*parent
, int parent_slot
,
249 struct extent_buffer
**cow_ret
,
250 u64 search_start
, u64 empty_size
,
254 struct extent_buffer
*cow
;
263 WARN_ON(!btrfs_tree_locked(buf
));
266 parent_start
= parent
->start
;
270 WARN_ON(root
->ref_cows
&& trans
->transid
!=
271 root
->fs_info
->running_transaction
->transid
);
272 WARN_ON(root
->ref_cows
&& trans
->transid
!= root
->last_trans
);
274 level
= btrfs_header_level(buf
);
275 nritems
= btrfs_header_nritems(buf
);
278 struct btrfs_key ins
;
280 ins
.objectid
= prealloc_dest
;
281 ins
.offset
= buf
->len
;
282 ins
.type
= BTRFS_EXTENT_ITEM_KEY
;
284 ret
= btrfs_alloc_reserved_extent(trans
, root
, parent_start
,
285 root
->root_key
.objectid
,
286 trans
->transid
, level
, &ins
);
288 cow
= btrfs_init_new_buffer(trans
, root
, prealloc_dest
,
291 cow
= btrfs_alloc_free_block(trans
, root
, buf
->len
,
293 root
->root_key
.objectid
,
294 trans
->transid
, level
,
295 search_start
, empty_size
);
300 /* cow is set to blocking by btrfs_init_new_buffer */
302 copy_extent_buffer(cow
, buf
, 0, 0, cow
->len
);
303 btrfs_set_header_bytenr(cow
, cow
->start
);
304 btrfs_set_header_generation(cow
, trans
->transid
);
305 btrfs_set_header_owner(cow
, root
->root_key
.objectid
);
306 btrfs_clear_header_flag(cow
, BTRFS_HEADER_FLAG_WRITTEN
);
308 write_extent_buffer(cow
, root
->fs_info
->fsid
,
309 (unsigned long)btrfs_header_fsid(cow
),
312 WARN_ON(btrfs_header_generation(buf
) > trans
->transid
);
313 if (btrfs_header_generation(buf
) != trans
->transid
) {
315 ret
= btrfs_inc_ref(trans
, root
, buf
, cow
, &nr_extents
);
319 ret
= btrfs_cache_ref(trans
, root
, buf
, nr_extents
);
321 } else if (btrfs_header_owner(buf
) == BTRFS_TREE_RELOC_OBJECTID
) {
323 * There are only two places that can drop reference to
324 * tree blocks owned by living reloc trees, one is here,
325 * the other place is btrfs_drop_subtree. In both places,
326 * we check reference count while tree block is locked.
327 * Furthermore, if reference count is one, it won't get
328 * increased by someone else.
331 ret
= btrfs_lookup_extent_ref(trans
, root
, buf
->start
,
335 ret
= btrfs_update_ref(trans
, root
, buf
, cow
,
337 clean_tree_block(trans
, root
, buf
);
339 ret
= btrfs_inc_ref(trans
, root
, buf
, cow
, NULL
);
343 ret
= btrfs_update_ref(trans
, root
, buf
, cow
, 0, nritems
);
346 clean_tree_block(trans
, root
, buf
);
349 if (root
->root_key
.objectid
== BTRFS_TREE_RELOC_OBJECTID
) {
350 ret
= btrfs_reloc_tree_cache_ref(trans
, root
, cow
, buf
->start
);
354 if (buf
== root
->node
) {
355 WARN_ON(parent
&& parent
!= buf
);
357 spin_lock(&root
->node_lock
);
359 extent_buffer_get(cow
);
360 spin_unlock(&root
->node_lock
);
362 if (buf
!= root
->commit_root
) {
363 btrfs_free_extent(trans
, root
, buf
->start
,
364 buf
->len
, buf
->start
,
365 root
->root_key
.objectid
,
366 btrfs_header_generation(buf
),
369 free_extent_buffer(buf
);
370 add_root_to_dirty_list(root
);
372 btrfs_set_node_blockptr(parent
, parent_slot
,
374 WARN_ON(trans
->transid
== 0);
375 btrfs_set_node_ptr_generation(parent
, parent_slot
,
377 btrfs_mark_buffer_dirty(parent
);
378 WARN_ON(btrfs_header_generation(parent
) != trans
->transid
);
379 btrfs_free_extent(trans
, root
, buf
->start
, buf
->len
,
380 parent_start
, btrfs_header_owner(parent
),
381 btrfs_header_generation(parent
), level
, 1);
384 btrfs_tree_unlock(buf
);
385 free_extent_buffer(buf
);
386 btrfs_mark_buffer_dirty(cow
);
392 * cows a single block, see __btrfs_cow_block for the real work.
393 * This version of it has extra checks so that a block isn't cow'd more than
394 * once per transaction, as long as it hasn't been written yet
396 noinline
int btrfs_cow_block(struct btrfs_trans_handle
*trans
,
397 struct btrfs_root
*root
, struct extent_buffer
*buf
,
398 struct extent_buffer
*parent
, int parent_slot
,
399 struct extent_buffer
**cow_ret
, u64 prealloc_dest
)
404 if (trans
->transaction
!= root
->fs_info
->running_transaction
) {
405 printk(KERN_CRIT
"trans %llu running %llu\n",
406 (unsigned long long)trans
->transid
,
408 root
->fs_info
->running_transaction
->transid
);
411 if (trans
->transid
!= root
->fs_info
->generation
) {
412 printk(KERN_CRIT
"trans %llu running %llu\n",
413 (unsigned long long)trans
->transid
,
414 (unsigned long long)root
->fs_info
->generation
);
418 if (btrfs_header_generation(buf
) == trans
->transid
&&
419 btrfs_header_owner(buf
) == root
->root_key
.objectid
&&
420 !btrfs_header_flag(buf
, BTRFS_HEADER_FLAG_WRITTEN
)) {
422 WARN_ON(prealloc_dest
);
426 search_start
= buf
->start
& ~((u64
)(1024 * 1024 * 1024) - 1);
429 btrfs_set_lock_blocking(parent
);
430 btrfs_set_lock_blocking(buf
);
432 ret
= __btrfs_cow_block(trans
, root
, buf
, parent
,
433 parent_slot
, cow_ret
, search_start
, 0,
439 * helper function for defrag to decide if two blocks pointed to by a
440 * node are actually close by
442 static int close_blocks(u64 blocknr
, u64 other
, u32 blocksize
)
444 if (blocknr
< other
&& other
- (blocknr
+ blocksize
) < 32768)
446 if (blocknr
> other
&& blocknr
- (other
+ blocksize
) < 32768)
452 * compare two keys in a memcmp fashion
454 static int comp_keys(struct btrfs_disk_key
*disk
, struct btrfs_key
*k2
)
458 btrfs_disk_key_to_cpu(&k1
, disk
);
460 if (k1
.objectid
> k2
->objectid
)
462 if (k1
.objectid
< k2
->objectid
)
464 if (k1
.type
> k2
->type
)
466 if (k1
.type
< k2
->type
)
468 if (k1
.offset
> k2
->offset
)
470 if (k1
.offset
< k2
->offset
)
476 * same as comp_keys only with two btrfs_key's
478 static int comp_cpu_keys(struct btrfs_key
*k1
, struct btrfs_key
*k2
)
480 if (k1
->objectid
> k2
->objectid
)
482 if (k1
->objectid
< k2
->objectid
)
484 if (k1
->type
> k2
->type
)
486 if (k1
->type
< k2
->type
)
488 if (k1
->offset
> k2
->offset
)
490 if (k1
->offset
< k2
->offset
)
496 * this is used by the defrag code to go through all the
497 * leaves pointed to by a node and reallocate them so that
498 * disk order is close to key order
500 int btrfs_realloc_node(struct btrfs_trans_handle
*trans
,
501 struct btrfs_root
*root
, struct extent_buffer
*parent
,
502 int start_slot
, int cache_only
, u64
*last_ret
,
503 struct btrfs_key
*progress
)
505 struct extent_buffer
*cur
;
508 u64 search_start
= *last_ret
;
518 int progress_passed
= 0;
519 struct btrfs_disk_key disk_key
;
521 parent_level
= btrfs_header_level(parent
);
522 if (cache_only
&& parent_level
!= 1)
525 if (trans
->transaction
!= root
->fs_info
->running_transaction
)
527 if (trans
->transid
!= root
->fs_info
->generation
)
530 parent_nritems
= btrfs_header_nritems(parent
);
531 blocksize
= btrfs_level_size(root
, parent_level
- 1);
532 end_slot
= parent_nritems
;
534 if (parent_nritems
== 1)
537 btrfs_set_lock_blocking(parent
);
539 for (i
= start_slot
; i
< end_slot
; i
++) {
542 if (!parent
->map_token
) {
543 map_extent_buffer(parent
,
544 btrfs_node_key_ptr_offset(i
),
545 sizeof(struct btrfs_key_ptr
),
546 &parent
->map_token
, &parent
->kaddr
,
547 &parent
->map_start
, &parent
->map_len
,
550 btrfs_node_key(parent
, &disk_key
, i
);
551 if (!progress_passed
&& comp_keys(&disk_key
, progress
) < 0)
555 blocknr
= btrfs_node_blockptr(parent
, i
);
556 gen
= btrfs_node_ptr_generation(parent
, i
);
558 last_block
= blocknr
;
561 other
= btrfs_node_blockptr(parent
, i
- 1);
562 close
= close_blocks(blocknr
, other
, blocksize
);
564 if (!close
&& i
< end_slot
- 2) {
565 other
= btrfs_node_blockptr(parent
, i
+ 1);
566 close
= close_blocks(blocknr
, other
, blocksize
);
569 last_block
= blocknr
;
572 if (parent
->map_token
) {
573 unmap_extent_buffer(parent
, parent
->map_token
,
575 parent
->map_token
= NULL
;
578 cur
= btrfs_find_tree_block(root
, blocknr
, blocksize
);
580 uptodate
= btrfs_buffer_uptodate(cur
, gen
);
583 if (!cur
|| !uptodate
) {
585 free_extent_buffer(cur
);
589 cur
= read_tree_block(root
, blocknr
,
591 } else if (!uptodate
) {
592 btrfs_read_buffer(cur
, gen
);
595 if (search_start
== 0)
596 search_start
= last_block
;
598 btrfs_tree_lock(cur
);
599 btrfs_set_lock_blocking(cur
);
600 err
= __btrfs_cow_block(trans
, root
, cur
, parent
, i
,
603 (end_slot
- i
) * blocksize
), 0);
605 btrfs_tree_unlock(cur
);
606 free_extent_buffer(cur
);
609 search_start
= cur
->start
;
610 last_block
= cur
->start
;
611 *last_ret
= search_start
;
612 btrfs_tree_unlock(cur
);
613 free_extent_buffer(cur
);
615 if (parent
->map_token
) {
616 unmap_extent_buffer(parent
, parent
->map_token
,
618 parent
->map_token
= NULL
;
624 * The leaf data grows from end-to-front in the node.
625 * this returns the address of the start of the last item,
626 * which is the stop of the leaf data stack
628 static inline unsigned int leaf_data_end(struct btrfs_root
*root
,
629 struct extent_buffer
*leaf
)
631 u32 nr
= btrfs_header_nritems(leaf
);
633 return BTRFS_LEAF_DATA_SIZE(root
);
634 return btrfs_item_offset_nr(leaf
, nr
- 1);
638 * extra debugging checks to make sure all the items in a key are
639 * well formed and in the proper order
641 static int check_node(struct btrfs_root
*root
, struct btrfs_path
*path
,
644 struct extent_buffer
*parent
= NULL
;
645 struct extent_buffer
*node
= path
->nodes
[level
];
646 struct btrfs_disk_key parent_key
;
647 struct btrfs_disk_key node_key
;
650 struct btrfs_key cpukey
;
651 u32 nritems
= btrfs_header_nritems(node
);
653 if (path
->nodes
[level
+ 1])
654 parent
= path
->nodes
[level
+ 1];
656 slot
= path
->slots
[level
];
657 BUG_ON(nritems
== 0);
659 parent_slot
= path
->slots
[level
+ 1];
660 btrfs_node_key(parent
, &parent_key
, parent_slot
);
661 btrfs_node_key(node
, &node_key
, 0);
662 BUG_ON(memcmp(&parent_key
, &node_key
,
663 sizeof(struct btrfs_disk_key
)));
664 BUG_ON(btrfs_node_blockptr(parent
, parent_slot
) !=
665 btrfs_header_bytenr(node
));
667 BUG_ON(nritems
> BTRFS_NODEPTRS_PER_BLOCK(root
));
669 btrfs_node_key_to_cpu(node
, &cpukey
, slot
- 1);
670 btrfs_node_key(node
, &node_key
, slot
);
671 BUG_ON(comp_keys(&node_key
, &cpukey
) <= 0);
673 if (slot
< nritems
- 1) {
674 btrfs_node_key_to_cpu(node
, &cpukey
, slot
+ 1);
675 btrfs_node_key(node
, &node_key
, slot
);
676 BUG_ON(comp_keys(&node_key
, &cpukey
) >= 0);
682 * extra checking to make sure all the items in a leaf are
683 * well formed and in the proper order
685 static int check_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
,
688 struct extent_buffer
*leaf
= path
->nodes
[level
];
689 struct extent_buffer
*parent
= NULL
;
691 struct btrfs_key cpukey
;
692 struct btrfs_disk_key parent_key
;
693 struct btrfs_disk_key leaf_key
;
694 int slot
= path
->slots
[0];
696 u32 nritems
= btrfs_header_nritems(leaf
);
698 if (path
->nodes
[level
+ 1])
699 parent
= path
->nodes
[level
+ 1];
705 parent_slot
= path
->slots
[level
+ 1];
706 btrfs_node_key(parent
, &parent_key
, parent_slot
);
707 btrfs_item_key(leaf
, &leaf_key
, 0);
709 BUG_ON(memcmp(&parent_key
, &leaf_key
,
710 sizeof(struct btrfs_disk_key
)));
711 BUG_ON(btrfs_node_blockptr(parent
, parent_slot
) !=
712 btrfs_header_bytenr(leaf
));
714 if (slot
!= 0 && slot
< nritems
- 1) {
715 btrfs_item_key(leaf
, &leaf_key
, slot
);
716 btrfs_item_key_to_cpu(leaf
, &cpukey
, slot
- 1);
717 if (comp_keys(&leaf_key
, &cpukey
) <= 0) {
718 btrfs_print_leaf(root
, leaf
);
719 printk(KERN_CRIT
"slot %d offset bad key\n", slot
);
722 if (btrfs_item_offset_nr(leaf
, slot
- 1) !=
723 btrfs_item_end_nr(leaf
, slot
)) {
724 btrfs_print_leaf(root
, leaf
);
725 printk(KERN_CRIT
"slot %d offset bad\n", slot
);
729 if (slot
< nritems
- 1) {
730 btrfs_item_key(leaf
, &leaf_key
, slot
);
731 btrfs_item_key_to_cpu(leaf
, &cpukey
, slot
+ 1);
732 BUG_ON(comp_keys(&leaf_key
, &cpukey
) >= 0);
733 if (btrfs_item_offset_nr(leaf
, slot
) !=
734 btrfs_item_end_nr(leaf
, slot
+ 1)) {
735 btrfs_print_leaf(root
, leaf
);
736 printk(KERN_CRIT
"slot %d offset bad\n", slot
);
740 BUG_ON(btrfs_item_offset_nr(leaf
, 0) +
741 btrfs_item_size_nr(leaf
, 0) != BTRFS_LEAF_DATA_SIZE(root
));
745 static noinline
int check_block(struct btrfs_root
*root
,
746 struct btrfs_path
*path
, int level
)
750 return check_leaf(root
, path
, level
);
751 return check_node(root
, path
, level
);
755 * search for key in the extent_buffer. The items start at offset p,
756 * and they are item_size apart. There are 'max' items in p.
758 * the slot in the array is returned via slot, and it points to
759 * the place where you would insert key if it is not found in
762 * slot may point to max if the key is bigger than all of the keys
764 static noinline
int generic_bin_search(struct extent_buffer
*eb
,
766 int item_size
, struct btrfs_key
*key
,
773 struct btrfs_disk_key
*tmp
= NULL
;
774 struct btrfs_disk_key unaligned
;
775 unsigned long offset
;
776 char *map_token
= NULL
;
778 unsigned long map_start
= 0;
779 unsigned long map_len
= 0;
783 mid
= (low
+ high
) / 2;
784 offset
= p
+ mid
* item_size
;
786 if (!map_token
|| offset
< map_start
||
787 (offset
+ sizeof(struct btrfs_disk_key
)) >
788 map_start
+ map_len
) {
790 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
794 err
= map_private_extent_buffer(eb
, offset
,
795 sizeof(struct btrfs_disk_key
),
797 &map_start
, &map_len
, KM_USER0
);
800 tmp
= (struct btrfs_disk_key
*)(kaddr
+ offset
-
803 read_extent_buffer(eb
, &unaligned
,
804 offset
, sizeof(unaligned
));
809 tmp
= (struct btrfs_disk_key
*)(kaddr
+ offset
-
812 ret
= comp_keys(tmp
, key
);
821 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
827 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
832 * simple bin_search frontend that does the right thing for
835 static int bin_search(struct extent_buffer
*eb
, struct btrfs_key
*key
,
836 int level
, int *slot
)
839 return generic_bin_search(eb
,
840 offsetof(struct btrfs_leaf
, items
),
841 sizeof(struct btrfs_item
),
842 key
, btrfs_header_nritems(eb
),
845 return generic_bin_search(eb
,
846 offsetof(struct btrfs_node
, ptrs
),
847 sizeof(struct btrfs_key_ptr
),
848 key
, btrfs_header_nritems(eb
),
854 /* given a node and slot number, this reads the blocks it points to. The
855 * extent buffer is returned with a reference taken (but unlocked).
856 * NULL is returned on error.
858 static noinline
struct extent_buffer
*read_node_slot(struct btrfs_root
*root
,
859 struct extent_buffer
*parent
, int slot
)
861 int level
= btrfs_header_level(parent
);
864 if (slot
>= btrfs_header_nritems(parent
))
869 return read_tree_block(root
, btrfs_node_blockptr(parent
, slot
),
870 btrfs_level_size(root
, level
- 1),
871 btrfs_node_ptr_generation(parent
, slot
));
875 * node level balancing, used to make sure nodes are in proper order for
876 * item deletion. We balance from the top down, so we have to make sure
877 * that a deletion won't leave an node completely empty later on.
879 static noinline
int balance_level(struct btrfs_trans_handle
*trans
,
880 struct btrfs_root
*root
,
881 struct btrfs_path
*path
, int level
)
883 struct extent_buffer
*right
= NULL
;
884 struct extent_buffer
*mid
;
885 struct extent_buffer
*left
= NULL
;
886 struct extent_buffer
*parent
= NULL
;
890 int orig_slot
= path
->slots
[level
];
891 int err_on_enospc
= 0;
897 mid
= path
->nodes
[level
];
899 WARN_ON(!path
->locks
[level
]);
900 WARN_ON(btrfs_header_generation(mid
) != trans
->transid
);
902 orig_ptr
= btrfs_node_blockptr(mid
, orig_slot
);
904 if (level
< BTRFS_MAX_LEVEL
- 1)
905 parent
= path
->nodes
[level
+ 1];
906 pslot
= path
->slots
[level
+ 1];
909 * deal with the case where there is only one pointer in the root
910 * by promoting the node below to a root
913 struct extent_buffer
*child
;
915 if (btrfs_header_nritems(mid
) != 1)
918 /* promote the child to a root */
919 child
= read_node_slot(root
, mid
, 0);
920 btrfs_tree_lock(child
);
921 btrfs_set_lock_blocking(child
);
923 ret
= btrfs_cow_block(trans
, root
, child
, mid
, 0, &child
, 0);
926 spin_lock(&root
->node_lock
);
928 spin_unlock(&root
->node_lock
);
930 ret
= btrfs_update_extent_ref(trans
, root
, child
->start
,
931 mid
->start
, child
->start
,
932 root
->root_key
.objectid
,
933 trans
->transid
, level
- 1);
936 add_root_to_dirty_list(root
);
937 btrfs_tree_unlock(child
);
939 path
->locks
[level
] = 0;
940 path
->nodes
[level
] = NULL
;
941 clean_tree_block(trans
, root
, mid
);
942 btrfs_tree_unlock(mid
);
943 /* once for the path */
944 free_extent_buffer(mid
);
945 ret
= btrfs_free_extent(trans
, root
, mid
->start
, mid
->len
,
946 mid
->start
, root
->root_key
.objectid
,
947 btrfs_header_generation(mid
),
949 /* once for the root ptr */
950 free_extent_buffer(mid
);
953 if (btrfs_header_nritems(mid
) >
954 BTRFS_NODEPTRS_PER_BLOCK(root
) / 4)
957 if (btrfs_header_nritems(mid
) < 2)
960 left
= read_node_slot(root
, parent
, pslot
- 1);
962 btrfs_tree_lock(left
);
963 btrfs_set_lock_blocking(left
);
964 wret
= btrfs_cow_block(trans
, root
, left
,
965 parent
, pslot
- 1, &left
, 0);
971 right
= read_node_slot(root
, parent
, pslot
+ 1);
973 btrfs_tree_lock(right
);
974 btrfs_set_lock_blocking(right
);
975 wret
= btrfs_cow_block(trans
, root
, right
,
976 parent
, pslot
+ 1, &right
, 0);
983 /* first, try to make some room in the middle buffer */
985 orig_slot
+= btrfs_header_nritems(left
);
986 wret
= push_node_left(trans
, root
, left
, mid
, 1);
989 if (btrfs_header_nritems(mid
) < 2)
994 * then try to empty the right most buffer into the middle
997 wret
= push_node_left(trans
, root
, mid
, right
, 1);
998 if (wret
< 0 && wret
!= -ENOSPC
)
1000 if (btrfs_header_nritems(right
) == 0) {
1001 u64 bytenr
= right
->start
;
1002 u64 generation
= btrfs_header_generation(parent
);
1003 u32 blocksize
= right
->len
;
1005 clean_tree_block(trans
, root
, right
);
1006 btrfs_tree_unlock(right
);
1007 free_extent_buffer(right
);
1009 wret
= del_ptr(trans
, root
, path
, level
+ 1, pslot
+
1013 wret
= btrfs_free_extent(trans
, root
, bytenr
,
1014 blocksize
, parent
->start
,
1015 btrfs_header_owner(parent
),
1016 generation
, level
, 1);
1020 struct btrfs_disk_key right_key
;
1021 btrfs_node_key(right
, &right_key
, 0);
1022 btrfs_set_node_key(parent
, &right_key
, pslot
+ 1);
1023 btrfs_mark_buffer_dirty(parent
);
1026 if (btrfs_header_nritems(mid
) == 1) {
1028 * we're not allowed to leave a node with one item in the
1029 * tree during a delete. A deletion from lower in the tree
1030 * could try to delete the only pointer in this node.
1031 * So, pull some keys from the left.
1032 * There has to be a left pointer at this point because
1033 * otherwise we would have pulled some pointers from the
1037 wret
= balance_node_right(trans
, root
, mid
, left
);
1043 wret
= push_node_left(trans
, root
, left
, mid
, 1);
1049 if (btrfs_header_nritems(mid
) == 0) {
1050 /* we've managed to empty the middle node, drop it */
1051 u64 root_gen
= btrfs_header_generation(parent
);
1052 u64 bytenr
= mid
->start
;
1053 u32 blocksize
= mid
->len
;
1055 clean_tree_block(trans
, root
, mid
);
1056 btrfs_tree_unlock(mid
);
1057 free_extent_buffer(mid
);
1059 wret
= del_ptr(trans
, root
, path
, level
+ 1, pslot
);
1062 wret
= btrfs_free_extent(trans
, root
, bytenr
, blocksize
,
1064 btrfs_header_owner(parent
),
1065 root_gen
, level
, 1);
1069 /* update the parent key to reflect our changes */
1070 struct btrfs_disk_key mid_key
;
1071 btrfs_node_key(mid
, &mid_key
, 0);
1072 btrfs_set_node_key(parent
, &mid_key
, pslot
);
1073 btrfs_mark_buffer_dirty(parent
);
1076 /* update the path */
1078 if (btrfs_header_nritems(left
) > orig_slot
) {
1079 extent_buffer_get(left
);
1080 /* left was locked after cow */
1081 path
->nodes
[level
] = left
;
1082 path
->slots
[level
+ 1] -= 1;
1083 path
->slots
[level
] = orig_slot
;
1085 btrfs_tree_unlock(mid
);
1086 free_extent_buffer(mid
);
1089 orig_slot
-= btrfs_header_nritems(left
);
1090 path
->slots
[level
] = orig_slot
;
1093 /* double check we haven't messed things up */
1094 check_block(root
, path
, level
);
1096 btrfs_node_blockptr(path
->nodes
[level
], path
->slots
[level
]))
1100 btrfs_tree_unlock(right
);
1101 free_extent_buffer(right
);
1104 if (path
->nodes
[level
] != left
)
1105 btrfs_tree_unlock(left
);
1106 free_extent_buffer(left
);
1111 /* Node balancing for insertion. Here we only split or push nodes around
1112 * when they are completely full. This is also done top down, so we
1113 * have to be pessimistic.
1115 static noinline
int push_nodes_for_insert(struct btrfs_trans_handle
*trans
,
1116 struct btrfs_root
*root
,
1117 struct btrfs_path
*path
, int level
)
1119 struct extent_buffer
*right
= NULL
;
1120 struct extent_buffer
*mid
;
1121 struct extent_buffer
*left
= NULL
;
1122 struct extent_buffer
*parent
= NULL
;
1126 int orig_slot
= path
->slots
[level
];
1132 mid
= path
->nodes
[level
];
1133 WARN_ON(btrfs_header_generation(mid
) != trans
->transid
);
1134 orig_ptr
= btrfs_node_blockptr(mid
, orig_slot
);
1136 if (level
< BTRFS_MAX_LEVEL
- 1)
1137 parent
= path
->nodes
[level
+ 1];
1138 pslot
= path
->slots
[level
+ 1];
1143 left
= read_node_slot(root
, parent
, pslot
- 1);
1145 /* first, try to make some room in the middle buffer */
1149 btrfs_tree_lock(left
);
1150 btrfs_set_lock_blocking(left
);
1152 left_nr
= btrfs_header_nritems(left
);
1153 if (left_nr
>= BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
1156 ret
= btrfs_cow_block(trans
, root
, left
, parent
,
1157 pslot
- 1, &left
, 0);
1161 wret
= push_node_left(trans
, root
,
1168 struct btrfs_disk_key disk_key
;
1169 orig_slot
+= left_nr
;
1170 btrfs_node_key(mid
, &disk_key
, 0);
1171 btrfs_set_node_key(parent
, &disk_key
, pslot
);
1172 btrfs_mark_buffer_dirty(parent
);
1173 if (btrfs_header_nritems(left
) > orig_slot
) {
1174 path
->nodes
[level
] = left
;
1175 path
->slots
[level
+ 1] -= 1;
1176 path
->slots
[level
] = orig_slot
;
1177 btrfs_tree_unlock(mid
);
1178 free_extent_buffer(mid
);
1181 btrfs_header_nritems(left
);
1182 path
->slots
[level
] = orig_slot
;
1183 btrfs_tree_unlock(left
);
1184 free_extent_buffer(left
);
1188 btrfs_tree_unlock(left
);
1189 free_extent_buffer(left
);
1191 right
= read_node_slot(root
, parent
, pslot
+ 1);
1194 * then try to empty the right most buffer into the middle
1199 btrfs_tree_lock(right
);
1200 btrfs_set_lock_blocking(right
);
1202 right_nr
= btrfs_header_nritems(right
);
1203 if (right_nr
>= BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
1206 ret
= btrfs_cow_block(trans
, root
, right
,
1212 wret
= balance_node_right(trans
, root
,
1219 struct btrfs_disk_key disk_key
;
1221 btrfs_node_key(right
, &disk_key
, 0);
1222 btrfs_set_node_key(parent
, &disk_key
, pslot
+ 1);
1223 btrfs_mark_buffer_dirty(parent
);
1225 if (btrfs_header_nritems(mid
) <= orig_slot
) {
1226 path
->nodes
[level
] = right
;
1227 path
->slots
[level
+ 1] += 1;
1228 path
->slots
[level
] = orig_slot
-
1229 btrfs_header_nritems(mid
);
1230 btrfs_tree_unlock(mid
);
1231 free_extent_buffer(mid
);
1233 btrfs_tree_unlock(right
);
1234 free_extent_buffer(right
);
1238 btrfs_tree_unlock(right
);
1239 free_extent_buffer(right
);
1245 * readahead one full node of leaves, finding things that are close
1246 * to the block in 'slot', and triggering ra on them.
1248 static noinline
void reada_for_search(struct btrfs_root
*root
,
1249 struct btrfs_path
*path
,
1250 int level
, int slot
, u64 objectid
)
1252 struct extent_buffer
*node
;
1253 struct btrfs_disk_key disk_key
;
1258 int direction
= path
->reada
;
1259 struct extent_buffer
*eb
;
1267 if (!path
->nodes
[level
])
1270 node
= path
->nodes
[level
];
1272 search
= btrfs_node_blockptr(node
, slot
);
1273 blocksize
= btrfs_level_size(root
, level
- 1);
1274 eb
= btrfs_find_tree_block(root
, search
, blocksize
);
1276 free_extent_buffer(eb
);
1282 nritems
= btrfs_header_nritems(node
);
1285 if (direction
< 0) {
1289 } else if (direction
> 0) {
1294 if (path
->reada
< 0 && objectid
) {
1295 btrfs_node_key(node
, &disk_key
, nr
);
1296 if (btrfs_disk_key_objectid(&disk_key
) != objectid
)
1299 search
= btrfs_node_blockptr(node
, nr
);
1300 if ((search
<= target
&& target
- search
<= 65536) ||
1301 (search
> target
&& search
- target
<= 65536)) {
1302 readahead_tree_block(root
, search
, blocksize
,
1303 btrfs_node_ptr_generation(node
, nr
));
1307 if ((nread
> 65536 || nscan
> 32))
1313 * returns -EAGAIN if it had to drop the path, or zero if everything was in
1316 static noinline
int reada_for_balance(struct btrfs_root
*root
,
1317 struct btrfs_path
*path
, int level
)
1321 struct extent_buffer
*parent
;
1322 struct extent_buffer
*eb
;
1329 parent
= path
->nodes
[level
- 1];
1333 nritems
= btrfs_header_nritems(parent
);
1334 slot
= path
->slots
[level
];
1335 blocksize
= btrfs_level_size(root
, level
);
1338 block1
= btrfs_node_blockptr(parent
, slot
- 1);
1339 gen
= btrfs_node_ptr_generation(parent
, slot
- 1);
1340 eb
= btrfs_find_tree_block(root
, block1
, blocksize
);
1341 if (eb
&& btrfs_buffer_uptodate(eb
, gen
))
1343 free_extent_buffer(eb
);
1345 if (slot
< nritems
) {
1346 block2
= btrfs_node_blockptr(parent
, slot
+ 1);
1347 gen
= btrfs_node_ptr_generation(parent
, slot
+ 1);
1348 eb
= btrfs_find_tree_block(root
, block2
, blocksize
);
1349 if (eb
&& btrfs_buffer_uptodate(eb
, gen
))
1351 free_extent_buffer(eb
);
1353 if (block1
|| block2
) {
1355 btrfs_release_path(root
, path
);
1357 readahead_tree_block(root
, block1
, blocksize
, 0);
1359 readahead_tree_block(root
, block2
, blocksize
, 0);
1362 eb
= read_tree_block(root
, block1
, blocksize
, 0);
1363 free_extent_buffer(eb
);
1366 eb
= read_tree_block(root
, block2
, blocksize
, 0);
1367 free_extent_buffer(eb
);
1375 * when we walk down the tree, it is usually safe to unlock the higher layers
1376 * in the tree. The exceptions are when our path goes through slot 0, because
1377 * operations on the tree might require changing key pointers higher up in the
1380 * callers might also have set path->keep_locks, which tells this code to keep
1381 * the lock if the path points to the last slot in the block. This is part of
1382 * walking through the tree, and selecting the next slot in the higher block.
1384 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
1385 * if lowest_unlock is 1, level 0 won't be unlocked
1387 static noinline
void unlock_up(struct btrfs_path
*path
, int level
,
1391 int skip_level
= level
;
1393 struct extent_buffer
*t
;
1395 for (i
= level
; i
< BTRFS_MAX_LEVEL
; i
++) {
1396 if (!path
->nodes
[i
])
1398 if (!path
->locks
[i
])
1400 if (!no_skips
&& path
->slots
[i
] == 0) {
1404 if (!no_skips
&& path
->keep_locks
) {
1407 nritems
= btrfs_header_nritems(t
);
1408 if (nritems
< 1 || path
->slots
[i
] >= nritems
- 1) {
1413 if (skip_level
< i
&& i
>= lowest_unlock
)
1417 if (i
>= lowest_unlock
&& i
> skip_level
&& path
->locks
[i
]) {
1418 btrfs_tree_unlock(t
);
1425 * This releases any locks held in the path starting at level and
1426 * going all the way up to the root.
1428 * btrfs_search_slot will keep the lock held on higher nodes in a few
1429 * corner cases, such as COW of the block at slot zero in the node. This
1430 * ignores those rules, and it should only be called when there are no
1431 * more updates to be done higher up in the tree.
1433 noinline
void btrfs_unlock_up_safe(struct btrfs_path
*path
, int level
)
1437 if (path
->keep_locks
|| path
->lowest_level
)
1440 for (i
= level
; i
< BTRFS_MAX_LEVEL
; i
++) {
1441 if (!path
->nodes
[i
])
1443 if (!path
->locks
[i
])
1445 btrfs_tree_unlock(path
->nodes
[i
]);
1451 * look for key in the tree. path is filled in with nodes along the way
1452 * if key is found, we return zero and you can find the item in the leaf
1453 * level of the path (level 0)
1455 * If the key isn't found, the path points to the slot where it should
1456 * be inserted, and 1 is returned. If there are other errors during the
1457 * search a negative error number is returned.
1459 * if ins_len > 0, nodes and leaves will be split as we walk down the
1460 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1463 int btrfs_search_slot(struct btrfs_trans_handle
*trans
, struct btrfs_root
1464 *root
, struct btrfs_key
*key
, struct btrfs_path
*p
, int
1467 struct extent_buffer
*b
;
1468 struct extent_buffer
*tmp
;
1472 int should_reada
= p
->reada
;
1473 int lowest_unlock
= 1;
1475 u8 lowest_level
= 0;
1478 struct btrfs_key prealloc_block
;
1480 lowest_level
= p
->lowest_level
;
1481 WARN_ON(lowest_level
&& ins_len
> 0);
1482 WARN_ON(p
->nodes
[0] != NULL
);
1487 prealloc_block
.objectid
= 0;
1490 if (p
->skip_locking
)
1491 b
= btrfs_root_node(root
);
1493 b
= btrfs_lock_root_node(root
);
1496 level
= btrfs_header_level(b
);
1499 * setup the path here so we can release it under lock
1500 * contention with the cow code
1502 p
->nodes
[level
] = b
;
1503 if (!p
->skip_locking
)
1504 p
->locks
[level
] = 1;
1509 /* is a cow on this block not required */
1510 if (btrfs_header_generation(b
) == trans
->transid
&&
1511 btrfs_header_owner(b
) == root
->root_key
.objectid
&&
1512 !btrfs_header_flag(b
, BTRFS_HEADER_FLAG_WRITTEN
)) {
1516 /* ok, we have to cow, is our old prealloc the right
1519 if (prealloc_block
.objectid
&&
1520 prealloc_block
.offset
!= b
->len
) {
1521 btrfs_set_path_blocking(p
);
1522 btrfs_free_reserved_extent(root
,
1523 prealloc_block
.objectid
,
1524 prealloc_block
.offset
);
1525 prealloc_block
.objectid
= 0;
1529 * for higher level blocks, try not to allocate blocks
1530 * with the block and the parent locks held.
1532 if (level
> 1 && !prealloc_block
.objectid
&&
1533 btrfs_path_lock_waiting(p
, level
)) {
1535 u64 hint
= b
->start
;
1537 btrfs_release_path(root
, p
);
1538 ret
= btrfs_reserve_extent(trans
, root
,
1541 &prealloc_block
, 0);
1546 btrfs_set_path_blocking(p
);
1548 wret
= btrfs_cow_block(trans
, root
, b
,
1549 p
->nodes
[level
+ 1],
1550 p
->slots
[level
+ 1],
1551 &b
, prealloc_block
.objectid
);
1552 prealloc_block
.objectid
= 0;
1554 free_extent_buffer(b
);
1560 BUG_ON(!cow
&& ins_len
);
1561 if (level
!= btrfs_header_level(b
))
1563 level
= btrfs_header_level(b
);
1565 p
->nodes
[level
] = b
;
1566 if (!p
->skip_locking
)
1567 p
->locks
[level
] = 1;
1569 btrfs_clear_path_blocking(p
);
1572 * we have a lock on b and as long as we aren't changing
1573 * the tree, there is no way to for the items in b to change.
1574 * It is safe to drop the lock on our parent before we
1575 * go through the expensive btree search on b.
1577 * If cow is true, then we might be changing slot zero,
1578 * which may require changing the parent. So, we can't
1579 * drop the lock until after we know which slot we're
1583 btrfs_unlock_up_safe(p
, level
+ 1);
1585 ret
= check_block(root
, p
, level
);
1591 ret
= bin_search(b
, key
, level
, &slot
);
1594 if (ret
&& slot
> 0)
1596 p
->slots
[level
] = slot
;
1597 if ((p
->search_for_split
|| ins_len
> 0) &&
1598 btrfs_header_nritems(b
) >=
1599 BTRFS_NODEPTRS_PER_BLOCK(root
) - 3) {
1602 sret
= reada_for_balance(root
, p
, level
);
1606 btrfs_set_path_blocking(p
);
1607 sret
= split_node(trans
, root
, p
, level
);
1608 btrfs_clear_path_blocking(p
);
1615 b
= p
->nodes
[level
];
1616 slot
= p
->slots
[level
];
1617 } else if (ins_len
< 0) {
1620 sret
= reada_for_balance(root
, p
, level
);
1624 btrfs_set_path_blocking(p
);
1625 sret
= balance_level(trans
, root
, p
, level
);
1626 btrfs_clear_path_blocking(p
);
1632 b
= p
->nodes
[level
];
1634 btrfs_release_path(NULL
, p
);
1637 slot
= p
->slots
[level
];
1638 BUG_ON(btrfs_header_nritems(b
) == 1);
1640 unlock_up(p
, level
, lowest_unlock
);
1642 /* this is only true while dropping a snapshot */
1643 if (level
== lowest_level
) {
1648 blocknr
= btrfs_node_blockptr(b
, slot
);
1649 gen
= btrfs_node_ptr_generation(b
, slot
);
1650 blocksize
= btrfs_level_size(root
, level
- 1);
1652 tmp
= btrfs_find_tree_block(root
, blocknr
, blocksize
);
1653 if (tmp
&& btrfs_buffer_uptodate(tmp
, gen
)) {
1657 * reduce lock contention at high levels
1658 * of the btree by dropping locks before
1662 btrfs_release_path(NULL
, p
);
1664 free_extent_buffer(tmp
);
1666 reada_for_search(root
, p
,
1670 tmp
= read_tree_block(root
, blocknr
,
1673 free_extent_buffer(tmp
);
1676 btrfs_set_path_blocking(p
);
1678 free_extent_buffer(tmp
);
1680 reada_for_search(root
, p
,
1683 b
= read_node_slot(root
, b
, slot
);
1686 if (!p
->skip_locking
) {
1689 btrfs_clear_path_blocking(p
);
1690 lret
= btrfs_try_spin_lock(b
);
1693 btrfs_set_path_blocking(p
);
1695 btrfs_clear_path_blocking(p
);
1699 p
->slots
[level
] = slot
;
1701 btrfs_leaf_free_space(root
, b
) < ins_len
) {
1704 btrfs_set_path_blocking(p
);
1705 sret
= split_leaf(trans
, root
, key
,
1706 p
, ins_len
, ret
== 0);
1707 btrfs_clear_path_blocking(p
);
1715 if (!p
->search_for_split
)
1716 unlock_up(p
, level
, lowest_unlock
);
1723 * we don't really know what they plan on doing with the path
1724 * from here on, so for now just mark it as blocking
1726 btrfs_set_path_blocking(p
);
1727 if (prealloc_block
.objectid
) {
1728 btrfs_free_reserved_extent(root
,
1729 prealloc_block
.objectid
,
1730 prealloc_block
.offset
);
1735 int btrfs_merge_path(struct btrfs_trans_handle
*trans
,
1736 struct btrfs_root
*root
,
1737 struct btrfs_key
*node_keys
,
1738 u64
*nodes
, int lowest_level
)
1740 struct extent_buffer
*eb
;
1741 struct extent_buffer
*parent
;
1742 struct btrfs_key key
;
1751 eb
= btrfs_lock_root_node(root
);
1752 ret
= btrfs_cow_block(trans
, root
, eb
, NULL
, 0, &eb
, 0);
1755 btrfs_set_lock_blocking(eb
);
1759 level
= btrfs_header_level(parent
);
1760 if (level
== 0 || level
<= lowest_level
)
1763 ret
= bin_search(parent
, &node_keys
[lowest_level
], level
,
1765 if (ret
&& slot
> 0)
1768 bytenr
= btrfs_node_blockptr(parent
, slot
);
1769 if (nodes
[level
- 1] == bytenr
)
1772 blocksize
= btrfs_level_size(root
, level
- 1);
1773 generation
= btrfs_node_ptr_generation(parent
, slot
);
1774 btrfs_node_key_to_cpu(eb
, &key
, slot
);
1775 key_match
= !memcmp(&key
, &node_keys
[level
- 1], sizeof(key
));
1777 if (generation
== trans
->transid
) {
1778 eb
= read_tree_block(root
, bytenr
, blocksize
,
1780 btrfs_tree_lock(eb
);
1781 btrfs_set_lock_blocking(eb
);
1785 * if node keys match and node pointer hasn't been modified
1786 * in the running transaction, we can merge the path. for
1787 * blocks owened by reloc trees, the node pointer check is
1788 * skipped, this is because these blocks are fully controlled
1789 * by the space balance code, no one else can modify them.
1791 if (!nodes
[level
- 1] || !key_match
||
1792 (generation
== trans
->transid
&&
1793 btrfs_header_owner(eb
) != BTRFS_TREE_RELOC_OBJECTID
)) {
1794 if (level
== 1 || level
== lowest_level
+ 1) {
1795 if (generation
== trans
->transid
) {
1796 btrfs_tree_unlock(eb
);
1797 free_extent_buffer(eb
);
1802 if (generation
!= trans
->transid
) {
1803 eb
= read_tree_block(root
, bytenr
, blocksize
,
1805 btrfs_tree_lock(eb
);
1806 btrfs_set_lock_blocking(eb
);
1809 ret
= btrfs_cow_block(trans
, root
, eb
, parent
, slot
,
1813 if (root
->root_key
.objectid
==
1814 BTRFS_TREE_RELOC_OBJECTID
) {
1815 if (!nodes
[level
- 1]) {
1816 nodes
[level
- 1] = eb
->start
;
1817 memcpy(&node_keys
[level
- 1], &key
,
1818 sizeof(node_keys
[0]));
1824 btrfs_tree_unlock(parent
);
1825 free_extent_buffer(parent
);
1830 btrfs_set_node_blockptr(parent
, slot
, nodes
[level
- 1]);
1831 btrfs_set_node_ptr_generation(parent
, slot
, trans
->transid
);
1832 btrfs_mark_buffer_dirty(parent
);
1834 ret
= btrfs_inc_extent_ref(trans
, root
,
1836 blocksize
, parent
->start
,
1837 btrfs_header_owner(parent
),
1838 btrfs_header_generation(parent
),
1843 * If the block was created in the running transaction,
1844 * it's possible this is the last reference to it, so we
1845 * should drop the subtree.
1847 if (generation
== trans
->transid
) {
1848 ret
= btrfs_drop_subtree(trans
, root
, eb
, parent
);
1850 btrfs_tree_unlock(eb
);
1851 free_extent_buffer(eb
);
1853 ret
= btrfs_free_extent(trans
, root
, bytenr
,
1854 blocksize
, parent
->start
,
1855 btrfs_header_owner(parent
),
1856 btrfs_header_generation(parent
),
1862 btrfs_tree_unlock(parent
);
1863 free_extent_buffer(parent
);
1868 * adjust the pointers going up the tree, starting at level
1869 * making sure the right key of each node is points to 'key'.
1870 * This is used after shifting pointers to the left, so it stops
1871 * fixing up pointers when a given leaf/node is not in slot 0 of the
1874 * If this fails to write a tree block, it returns -1, but continues
1875 * fixing up the blocks in ram so the tree is consistent.
1877 static int fixup_low_keys(struct btrfs_trans_handle
*trans
,
1878 struct btrfs_root
*root
, struct btrfs_path
*path
,
1879 struct btrfs_disk_key
*key
, int level
)
1883 struct extent_buffer
*t
;
1885 for (i
= level
; i
< BTRFS_MAX_LEVEL
; i
++) {
1886 int tslot
= path
->slots
[i
];
1887 if (!path
->nodes
[i
])
1890 btrfs_set_node_key(t
, key
, tslot
);
1891 btrfs_mark_buffer_dirty(path
->nodes
[i
]);
1901 * This function isn't completely safe. It's the caller's responsibility
1902 * that the new key won't break the order
1904 int btrfs_set_item_key_safe(struct btrfs_trans_handle
*trans
,
1905 struct btrfs_root
*root
, struct btrfs_path
*path
,
1906 struct btrfs_key
*new_key
)
1908 struct btrfs_disk_key disk_key
;
1909 struct extent_buffer
*eb
;
1912 eb
= path
->nodes
[0];
1913 slot
= path
->slots
[0];
1915 btrfs_item_key(eb
, &disk_key
, slot
- 1);
1916 if (comp_keys(&disk_key
, new_key
) >= 0)
1919 if (slot
< btrfs_header_nritems(eb
) - 1) {
1920 btrfs_item_key(eb
, &disk_key
, slot
+ 1);
1921 if (comp_keys(&disk_key
, new_key
) <= 0)
1925 btrfs_cpu_key_to_disk(&disk_key
, new_key
);
1926 btrfs_set_item_key(eb
, &disk_key
, slot
);
1927 btrfs_mark_buffer_dirty(eb
);
1929 fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
1934 * try to push data from one node into the next node left in the
1937 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1938 * error, and > 0 if there was no room in the left hand block.
1940 static int push_node_left(struct btrfs_trans_handle
*trans
,
1941 struct btrfs_root
*root
, struct extent_buffer
*dst
,
1942 struct extent_buffer
*src
, int empty
)
1949 src_nritems
= btrfs_header_nritems(src
);
1950 dst_nritems
= btrfs_header_nritems(dst
);
1951 push_items
= BTRFS_NODEPTRS_PER_BLOCK(root
) - dst_nritems
;
1952 WARN_ON(btrfs_header_generation(src
) != trans
->transid
);
1953 WARN_ON(btrfs_header_generation(dst
) != trans
->transid
);
1955 if (!empty
&& src_nritems
<= 8)
1958 if (push_items
<= 0)
1962 push_items
= min(src_nritems
, push_items
);
1963 if (push_items
< src_nritems
) {
1964 /* leave at least 8 pointers in the node if
1965 * we aren't going to empty it
1967 if (src_nritems
- push_items
< 8) {
1968 if (push_items
<= 8)
1974 push_items
= min(src_nritems
- 8, push_items
);
1976 copy_extent_buffer(dst
, src
,
1977 btrfs_node_key_ptr_offset(dst_nritems
),
1978 btrfs_node_key_ptr_offset(0),
1979 push_items
* sizeof(struct btrfs_key_ptr
));
1981 if (push_items
< src_nritems
) {
1982 memmove_extent_buffer(src
, btrfs_node_key_ptr_offset(0),
1983 btrfs_node_key_ptr_offset(push_items
),
1984 (src_nritems
- push_items
) *
1985 sizeof(struct btrfs_key_ptr
));
1987 btrfs_set_header_nritems(src
, src_nritems
- push_items
);
1988 btrfs_set_header_nritems(dst
, dst_nritems
+ push_items
);
1989 btrfs_mark_buffer_dirty(src
);
1990 btrfs_mark_buffer_dirty(dst
);
1992 ret
= btrfs_update_ref(trans
, root
, src
, dst
, dst_nritems
, push_items
);
1999 * try to push data from one node into the next node right in the
2002 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
2003 * error, and > 0 if there was no room in the right hand block.
2005 * this will only push up to 1/2 the contents of the left node over
2007 static int balance_node_right(struct btrfs_trans_handle
*trans
,
2008 struct btrfs_root
*root
,
2009 struct extent_buffer
*dst
,
2010 struct extent_buffer
*src
)
2018 WARN_ON(btrfs_header_generation(src
) != trans
->transid
);
2019 WARN_ON(btrfs_header_generation(dst
) != trans
->transid
);
2021 src_nritems
= btrfs_header_nritems(src
);
2022 dst_nritems
= btrfs_header_nritems(dst
);
2023 push_items
= BTRFS_NODEPTRS_PER_BLOCK(root
) - dst_nritems
;
2024 if (push_items
<= 0)
2027 if (src_nritems
< 4)
2030 max_push
= src_nritems
/ 2 + 1;
2031 /* don't try to empty the node */
2032 if (max_push
>= src_nritems
)
2035 if (max_push
< push_items
)
2036 push_items
= max_push
;
2038 memmove_extent_buffer(dst
, btrfs_node_key_ptr_offset(push_items
),
2039 btrfs_node_key_ptr_offset(0),
2041 sizeof(struct btrfs_key_ptr
));
2043 copy_extent_buffer(dst
, src
,
2044 btrfs_node_key_ptr_offset(0),
2045 btrfs_node_key_ptr_offset(src_nritems
- push_items
),
2046 push_items
* sizeof(struct btrfs_key_ptr
));
2048 btrfs_set_header_nritems(src
, src_nritems
- push_items
);
2049 btrfs_set_header_nritems(dst
, dst_nritems
+ push_items
);
2051 btrfs_mark_buffer_dirty(src
);
2052 btrfs_mark_buffer_dirty(dst
);
2054 ret
= btrfs_update_ref(trans
, root
, src
, dst
, 0, push_items
);
2061 * helper function to insert a new root level in the tree.
2062 * A new node is allocated, and a single item is inserted to
2063 * point to the existing root
2065 * returns zero on success or < 0 on failure.
2067 static noinline
int insert_new_root(struct btrfs_trans_handle
*trans
,
2068 struct btrfs_root
*root
,
2069 struct btrfs_path
*path
, int level
)
2072 struct extent_buffer
*lower
;
2073 struct extent_buffer
*c
;
2074 struct extent_buffer
*old
;
2075 struct btrfs_disk_key lower_key
;
2078 BUG_ON(path
->nodes
[level
]);
2079 BUG_ON(path
->nodes
[level
-1] != root
->node
);
2081 lower
= path
->nodes
[level
-1];
2083 btrfs_item_key(lower
, &lower_key
, 0);
2085 btrfs_node_key(lower
, &lower_key
, 0);
2087 c
= btrfs_alloc_free_block(trans
, root
, root
->nodesize
, 0,
2088 root
->root_key
.objectid
, trans
->transid
,
2089 level
, root
->node
->start
, 0);
2093 memset_extent_buffer(c
, 0, 0, root
->nodesize
);
2094 btrfs_set_header_nritems(c
, 1);
2095 btrfs_set_header_level(c
, level
);
2096 btrfs_set_header_bytenr(c
, c
->start
);
2097 btrfs_set_header_generation(c
, trans
->transid
);
2098 btrfs_set_header_owner(c
, root
->root_key
.objectid
);
2100 write_extent_buffer(c
, root
->fs_info
->fsid
,
2101 (unsigned long)btrfs_header_fsid(c
),
2104 write_extent_buffer(c
, root
->fs_info
->chunk_tree_uuid
,
2105 (unsigned long)btrfs_header_chunk_tree_uuid(c
),
2108 btrfs_set_node_key(c
, &lower_key
, 0);
2109 btrfs_set_node_blockptr(c
, 0, lower
->start
);
2110 lower_gen
= btrfs_header_generation(lower
);
2111 WARN_ON(lower_gen
!= trans
->transid
);
2113 btrfs_set_node_ptr_generation(c
, 0, lower_gen
);
2115 btrfs_mark_buffer_dirty(c
);
2117 spin_lock(&root
->node_lock
);
2120 spin_unlock(&root
->node_lock
);
2122 ret
= btrfs_update_extent_ref(trans
, root
, lower
->start
,
2123 lower
->start
, c
->start
,
2124 root
->root_key
.objectid
,
2125 trans
->transid
, level
- 1);
2128 /* the super has an extra ref to root->node */
2129 free_extent_buffer(old
);
2131 add_root_to_dirty_list(root
);
2132 extent_buffer_get(c
);
2133 path
->nodes
[level
] = c
;
2134 path
->locks
[level
] = 1;
2135 path
->slots
[level
] = 0;
2140 * worker function to insert a single pointer in a node.
2141 * the node should have enough room for the pointer already
2143 * slot and level indicate where you want the key to go, and
2144 * blocknr is the block the key points to.
2146 * returns zero on success and < 0 on any error
2148 static int insert_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
2149 *root
, struct btrfs_path
*path
, struct btrfs_disk_key
2150 *key
, u64 bytenr
, int slot
, int level
)
2152 struct extent_buffer
*lower
;
2155 BUG_ON(!path
->nodes
[level
]);
2156 lower
= path
->nodes
[level
];
2157 nritems
= btrfs_header_nritems(lower
);
2160 if (nritems
== BTRFS_NODEPTRS_PER_BLOCK(root
))
2162 if (slot
!= nritems
) {
2163 memmove_extent_buffer(lower
,
2164 btrfs_node_key_ptr_offset(slot
+ 1),
2165 btrfs_node_key_ptr_offset(slot
),
2166 (nritems
- slot
) * sizeof(struct btrfs_key_ptr
));
2168 btrfs_set_node_key(lower
, key
, slot
);
2169 btrfs_set_node_blockptr(lower
, slot
, bytenr
);
2170 WARN_ON(trans
->transid
== 0);
2171 btrfs_set_node_ptr_generation(lower
, slot
, trans
->transid
);
2172 btrfs_set_header_nritems(lower
, nritems
+ 1);
2173 btrfs_mark_buffer_dirty(lower
);
2178 * split the node at the specified level in path in two.
2179 * The path is corrected to point to the appropriate node after the split
2181 * Before splitting this tries to make some room in the node by pushing
2182 * left and right, if either one works, it returns right away.
2184 * returns 0 on success and < 0 on failure
2186 static noinline
int split_node(struct btrfs_trans_handle
*trans
,
2187 struct btrfs_root
*root
,
2188 struct btrfs_path
*path
, int level
)
2190 struct extent_buffer
*c
;
2191 struct extent_buffer
*split
;
2192 struct btrfs_disk_key disk_key
;
2198 c
= path
->nodes
[level
];
2199 WARN_ON(btrfs_header_generation(c
) != trans
->transid
);
2200 if (c
== root
->node
) {
2201 /* trying to split the root, lets make a new one */
2202 ret
= insert_new_root(trans
, root
, path
, level
+ 1);
2206 ret
= push_nodes_for_insert(trans
, root
, path
, level
);
2207 c
= path
->nodes
[level
];
2208 if (!ret
&& btrfs_header_nritems(c
) <
2209 BTRFS_NODEPTRS_PER_BLOCK(root
) - 3)
2215 c_nritems
= btrfs_header_nritems(c
);
2217 split
= btrfs_alloc_free_block(trans
, root
, root
->nodesize
,
2218 path
->nodes
[level
+ 1]->start
,
2219 root
->root_key
.objectid
,
2220 trans
->transid
, level
, c
->start
, 0);
2222 return PTR_ERR(split
);
2224 btrfs_set_header_flags(split
, btrfs_header_flags(c
));
2225 btrfs_set_header_level(split
, btrfs_header_level(c
));
2226 btrfs_set_header_bytenr(split
, split
->start
);
2227 btrfs_set_header_generation(split
, trans
->transid
);
2228 btrfs_set_header_owner(split
, root
->root_key
.objectid
);
2229 btrfs_set_header_flags(split
, 0);
2230 write_extent_buffer(split
, root
->fs_info
->fsid
,
2231 (unsigned long)btrfs_header_fsid(split
),
2233 write_extent_buffer(split
, root
->fs_info
->chunk_tree_uuid
,
2234 (unsigned long)btrfs_header_chunk_tree_uuid(split
),
2237 mid
= (c_nritems
+ 1) / 2;
2239 copy_extent_buffer(split
, c
,
2240 btrfs_node_key_ptr_offset(0),
2241 btrfs_node_key_ptr_offset(mid
),
2242 (c_nritems
- mid
) * sizeof(struct btrfs_key_ptr
));
2243 btrfs_set_header_nritems(split
, c_nritems
- mid
);
2244 btrfs_set_header_nritems(c
, mid
);
2247 btrfs_mark_buffer_dirty(c
);
2248 btrfs_mark_buffer_dirty(split
);
2250 btrfs_node_key(split
, &disk_key
, 0);
2251 wret
= insert_ptr(trans
, root
, path
, &disk_key
, split
->start
,
2252 path
->slots
[level
+ 1] + 1,
2257 ret
= btrfs_update_ref(trans
, root
, c
, split
, 0, c_nritems
- mid
);
2260 if (path
->slots
[level
] >= mid
) {
2261 path
->slots
[level
] -= mid
;
2262 btrfs_tree_unlock(c
);
2263 free_extent_buffer(c
);
2264 path
->nodes
[level
] = split
;
2265 path
->slots
[level
+ 1] += 1;
2267 btrfs_tree_unlock(split
);
2268 free_extent_buffer(split
);
2274 * how many bytes are required to store the items in a leaf. start
2275 * and nr indicate which items in the leaf to check. This totals up the
2276 * space used both by the item structs and the item data
2278 static int leaf_space_used(struct extent_buffer
*l
, int start
, int nr
)
2281 int nritems
= btrfs_header_nritems(l
);
2282 int end
= min(nritems
, start
+ nr
) - 1;
2286 data_len
= btrfs_item_end_nr(l
, start
);
2287 data_len
= data_len
- btrfs_item_offset_nr(l
, end
);
2288 data_len
+= sizeof(struct btrfs_item
) * nr
;
2289 WARN_ON(data_len
< 0);
2294 * The space between the end of the leaf items and
2295 * the start of the leaf data. IOW, how much room
2296 * the leaf has left for both items and data
2298 noinline
int btrfs_leaf_free_space(struct btrfs_root
*root
,
2299 struct extent_buffer
*leaf
)
2301 int nritems
= btrfs_header_nritems(leaf
);
2303 ret
= BTRFS_LEAF_DATA_SIZE(root
) - leaf_space_used(leaf
, 0, nritems
);
2305 printk(KERN_CRIT
"leaf free space ret %d, leaf data size %lu, "
2306 "used %d nritems %d\n",
2307 ret
, (unsigned long) BTRFS_LEAF_DATA_SIZE(root
),
2308 leaf_space_used(leaf
, 0, nritems
), nritems
);
2314 * push some data in the path leaf to the right, trying to free up at
2315 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2317 * returns 1 if the push failed because the other node didn't have enough
2318 * room, 0 if everything worked out and < 0 if there were major errors.
2320 static int push_leaf_right(struct btrfs_trans_handle
*trans
, struct btrfs_root
2321 *root
, struct btrfs_path
*path
, int data_size
,
2324 struct extent_buffer
*left
= path
->nodes
[0];
2325 struct extent_buffer
*right
;
2326 struct extent_buffer
*upper
;
2327 struct btrfs_disk_key disk_key
;
2333 struct btrfs_item
*item
;
2341 slot
= path
->slots
[1];
2342 if (!path
->nodes
[1])
2345 upper
= path
->nodes
[1];
2346 if (slot
>= btrfs_header_nritems(upper
) - 1)
2349 WARN_ON(!btrfs_tree_locked(path
->nodes
[1]));
2351 right
= read_node_slot(root
, upper
, slot
+ 1);
2352 btrfs_tree_lock(right
);
2353 btrfs_set_lock_blocking(right
);
2355 free_space
= btrfs_leaf_free_space(root
, right
);
2356 if (free_space
< data_size
)
2359 /* cow and double check */
2360 ret
= btrfs_cow_block(trans
, root
, right
, upper
,
2361 slot
+ 1, &right
, 0);
2365 free_space
= btrfs_leaf_free_space(root
, right
);
2366 if (free_space
< data_size
)
2369 left_nritems
= btrfs_header_nritems(left
);
2370 if (left_nritems
== 0)
2378 if (path
->slots
[0] >= left_nritems
)
2379 push_space
+= data_size
;
2381 i
= left_nritems
- 1;
2383 item
= btrfs_item_nr(left
, i
);
2385 if (!empty
&& push_items
> 0) {
2386 if (path
->slots
[0] > i
)
2388 if (path
->slots
[0] == i
) {
2389 int space
= btrfs_leaf_free_space(root
, left
);
2390 if (space
+ push_space
* 2 > free_space
)
2395 if (path
->slots
[0] == i
)
2396 push_space
+= data_size
;
2398 if (!left
->map_token
) {
2399 map_extent_buffer(left
, (unsigned long)item
,
2400 sizeof(struct btrfs_item
),
2401 &left
->map_token
, &left
->kaddr
,
2402 &left
->map_start
, &left
->map_len
,
2406 this_item_size
= btrfs_item_size(left
, item
);
2407 if (this_item_size
+ sizeof(*item
) + push_space
> free_space
)
2411 push_space
+= this_item_size
+ sizeof(*item
);
2416 if (left
->map_token
) {
2417 unmap_extent_buffer(left
, left
->map_token
, KM_USER1
);
2418 left
->map_token
= NULL
;
2421 if (push_items
== 0)
2424 if (!empty
&& push_items
== left_nritems
)
2427 /* push left to right */
2428 right_nritems
= btrfs_header_nritems(right
);
2430 push_space
= btrfs_item_end_nr(left
, left_nritems
- push_items
);
2431 push_space
-= leaf_data_end(root
, left
);
2433 /* make room in the right data area */
2434 data_end
= leaf_data_end(root
, right
);
2435 memmove_extent_buffer(right
,
2436 btrfs_leaf_data(right
) + data_end
- push_space
,
2437 btrfs_leaf_data(right
) + data_end
,
2438 BTRFS_LEAF_DATA_SIZE(root
) - data_end
);
2440 /* copy from the left data area */
2441 copy_extent_buffer(right
, left
, btrfs_leaf_data(right
) +
2442 BTRFS_LEAF_DATA_SIZE(root
) - push_space
,
2443 btrfs_leaf_data(left
) + leaf_data_end(root
, left
),
2446 memmove_extent_buffer(right
, btrfs_item_nr_offset(push_items
),
2447 btrfs_item_nr_offset(0),
2448 right_nritems
* sizeof(struct btrfs_item
));
2450 /* copy the items from left to right */
2451 copy_extent_buffer(right
, left
, btrfs_item_nr_offset(0),
2452 btrfs_item_nr_offset(left_nritems
- push_items
),
2453 push_items
* sizeof(struct btrfs_item
));
2455 /* update the item pointers */
2456 right_nritems
+= push_items
;
2457 btrfs_set_header_nritems(right
, right_nritems
);
2458 push_space
= BTRFS_LEAF_DATA_SIZE(root
);
2459 for (i
= 0; i
< right_nritems
; i
++) {
2460 item
= btrfs_item_nr(right
, i
);
2461 if (!right
->map_token
) {
2462 map_extent_buffer(right
, (unsigned long)item
,
2463 sizeof(struct btrfs_item
),
2464 &right
->map_token
, &right
->kaddr
,
2465 &right
->map_start
, &right
->map_len
,
2468 push_space
-= btrfs_item_size(right
, item
);
2469 btrfs_set_item_offset(right
, item
, push_space
);
2472 if (right
->map_token
) {
2473 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
2474 right
->map_token
= NULL
;
2476 left_nritems
-= push_items
;
2477 btrfs_set_header_nritems(left
, left_nritems
);
2480 btrfs_mark_buffer_dirty(left
);
2481 btrfs_mark_buffer_dirty(right
);
2483 ret
= btrfs_update_ref(trans
, root
, left
, right
, 0, push_items
);
2486 btrfs_item_key(right
, &disk_key
, 0);
2487 btrfs_set_node_key(upper
, &disk_key
, slot
+ 1);
2488 btrfs_mark_buffer_dirty(upper
);
2490 /* then fixup the leaf pointer in the path */
2491 if (path
->slots
[0] >= left_nritems
) {
2492 path
->slots
[0] -= left_nritems
;
2493 if (btrfs_header_nritems(path
->nodes
[0]) == 0)
2494 clean_tree_block(trans
, root
, path
->nodes
[0]);
2495 btrfs_tree_unlock(path
->nodes
[0]);
2496 free_extent_buffer(path
->nodes
[0]);
2497 path
->nodes
[0] = right
;
2498 path
->slots
[1] += 1;
2500 btrfs_tree_unlock(right
);
2501 free_extent_buffer(right
);
2506 btrfs_tree_unlock(right
);
2507 free_extent_buffer(right
);
2512 * push some data in the path leaf to the left, trying to free up at
2513 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2515 static int push_leaf_left(struct btrfs_trans_handle
*trans
, struct btrfs_root
2516 *root
, struct btrfs_path
*path
, int data_size
,
2519 struct btrfs_disk_key disk_key
;
2520 struct extent_buffer
*right
= path
->nodes
[0];
2521 struct extent_buffer
*left
;
2527 struct btrfs_item
*item
;
2528 u32 old_left_nritems
;
2534 u32 old_left_item_size
;
2536 slot
= path
->slots
[1];
2539 if (!path
->nodes
[1])
2542 right_nritems
= btrfs_header_nritems(right
);
2543 if (right_nritems
== 0)
2546 WARN_ON(!btrfs_tree_locked(path
->nodes
[1]));
2548 left
= read_node_slot(root
, path
->nodes
[1], slot
- 1);
2549 btrfs_tree_lock(left
);
2550 btrfs_set_lock_blocking(left
);
2552 free_space
= btrfs_leaf_free_space(root
, left
);
2553 if (free_space
< data_size
) {
2558 /* cow and double check */
2559 ret
= btrfs_cow_block(trans
, root
, left
,
2560 path
->nodes
[1], slot
- 1, &left
, 0);
2562 /* we hit -ENOSPC, but it isn't fatal here */
2567 free_space
= btrfs_leaf_free_space(root
, left
);
2568 if (free_space
< data_size
) {
2576 nr
= right_nritems
- 1;
2578 for (i
= 0; i
< nr
; i
++) {
2579 item
= btrfs_item_nr(right
, i
);
2580 if (!right
->map_token
) {
2581 map_extent_buffer(right
, (unsigned long)item
,
2582 sizeof(struct btrfs_item
),
2583 &right
->map_token
, &right
->kaddr
,
2584 &right
->map_start
, &right
->map_len
,
2588 if (!empty
&& push_items
> 0) {
2589 if (path
->slots
[0] < i
)
2591 if (path
->slots
[0] == i
) {
2592 int space
= btrfs_leaf_free_space(root
, right
);
2593 if (space
+ push_space
* 2 > free_space
)
2598 if (path
->slots
[0] == i
)
2599 push_space
+= data_size
;
2601 this_item_size
= btrfs_item_size(right
, item
);
2602 if (this_item_size
+ sizeof(*item
) + push_space
> free_space
)
2606 push_space
+= this_item_size
+ sizeof(*item
);
2609 if (right
->map_token
) {
2610 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
2611 right
->map_token
= NULL
;
2614 if (push_items
== 0) {
2618 if (!empty
&& push_items
== btrfs_header_nritems(right
))
2621 /* push data from right to left */
2622 copy_extent_buffer(left
, right
,
2623 btrfs_item_nr_offset(btrfs_header_nritems(left
)),
2624 btrfs_item_nr_offset(0),
2625 push_items
* sizeof(struct btrfs_item
));
2627 push_space
= BTRFS_LEAF_DATA_SIZE(root
) -
2628 btrfs_item_offset_nr(right
, push_items
- 1);
2630 copy_extent_buffer(left
, right
, btrfs_leaf_data(left
) +
2631 leaf_data_end(root
, left
) - push_space
,
2632 btrfs_leaf_data(right
) +
2633 btrfs_item_offset_nr(right
, push_items
- 1),
2635 old_left_nritems
= btrfs_header_nritems(left
);
2636 BUG_ON(old_left_nritems
<= 0);
2638 old_left_item_size
= btrfs_item_offset_nr(left
, old_left_nritems
- 1);
2639 for (i
= old_left_nritems
; i
< old_left_nritems
+ push_items
; i
++) {
2642 item
= btrfs_item_nr(left
, i
);
2643 if (!left
->map_token
) {
2644 map_extent_buffer(left
, (unsigned long)item
,
2645 sizeof(struct btrfs_item
),
2646 &left
->map_token
, &left
->kaddr
,
2647 &left
->map_start
, &left
->map_len
,
2651 ioff
= btrfs_item_offset(left
, item
);
2652 btrfs_set_item_offset(left
, item
,
2653 ioff
- (BTRFS_LEAF_DATA_SIZE(root
) - old_left_item_size
));
2655 btrfs_set_header_nritems(left
, old_left_nritems
+ push_items
);
2656 if (left
->map_token
) {
2657 unmap_extent_buffer(left
, left
->map_token
, KM_USER1
);
2658 left
->map_token
= NULL
;
2661 /* fixup right node */
2662 if (push_items
> right_nritems
) {
2663 printk(KERN_CRIT
"push items %d nr %u\n", push_items
,
2668 if (push_items
< right_nritems
) {
2669 push_space
= btrfs_item_offset_nr(right
, push_items
- 1) -
2670 leaf_data_end(root
, right
);
2671 memmove_extent_buffer(right
, btrfs_leaf_data(right
) +
2672 BTRFS_LEAF_DATA_SIZE(root
) - push_space
,
2673 btrfs_leaf_data(right
) +
2674 leaf_data_end(root
, right
), push_space
);
2676 memmove_extent_buffer(right
, btrfs_item_nr_offset(0),
2677 btrfs_item_nr_offset(push_items
),
2678 (btrfs_header_nritems(right
) - push_items
) *
2679 sizeof(struct btrfs_item
));
2681 right_nritems
-= push_items
;
2682 btrfs_set_header_nritems(right
, right_nritems
);
2683 push_space
= BTRFS_LEAF_DATA_SIZE(root
);
2684 for (i
= 0; i
< right_nritems
; i
++) {
2685 item
= btrfs_item_nr(right
, i
);
2687 if (!right
->map_token
) {
2688 map_extent_buffer(right
, (unsigned long)item
,
2689 sizeof(struct btrfs_item
),
2690 &right
->map_token
, &right
->kaddr
,
2691 &right
->map_start
, &right
->map_len
,
2695 push_space
= push_space
- btrfs_item_size(right
, item
);
2696 btrfs_set_item_offset(right
, item
, push_space
);
2698 if (right
->map_token
) {
2699 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
2700 right
->map_token
= NULL
;
2703 btrfs_mark_buffer_dirty(left
);
2705 btrfs_mark_buffer_dirty(right
);
2707 ret
= btrfs_update_ref(trans
, root
, right
, left
,
2708 old_left_nritems
, push_items
);
2711 btrfs_item_key(right
, &disk_key
, 0);
2712 wret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
2716 /* then fixup the leaf pointer in the path */
2717 if (path
->slots
[0] < push_items
) {
2718 path
->slots
[0] += old_left_nritems
;
2719 if (btrfs_header_nritems(path
->nodes
[0]) == 0)
2720 clean_tree_block(trans
, root
, path
->nodes
[0]);
2721 btrfs_tree_unlock(path
->nodes
[0]);
2722 free_extent_buffer(path
->nodes
[0]);
2723 path
->nodes
[0] = left
;
2724 path
->slots
[1] -= 1;
2726 btrfs_tree_unlock(left
);
2727 free_extent_buffer(left
);
2728 path
->slots
[0] -= push_items
;
2730 BUG_ON(path
->slots
[0] < 0);
2733 btrfs_tree_unlock(left
);
2734 free_extent_buffer(left
);
2739 * split the path's leaf in two, making sure there is at least data_size
2740 * available for the resulting leaf level of the path.
2742 * returns 0 if all went well and < 0 on failure.
2744 static noinline
int split_leaf(struct btrfs_trans_handle
*trans
,
2745 struct btrfs_root
*root
,
2746 struct btrfs_key
*ins_key
,
2747 struct btrfs_path
*path
, int data_size
,
2750 struct extent_buffer
*l
;
2754 struct extent_buffer
*right
;
2761 int num_doubles
= 0;
2762 struct btrfs_disk_key disk_key
;
2764 /* first try to make some room by pushing left and right */
2765 if (data_size
&& ins_key
->type
!= BTRFS_DIR_ITEM_KEY
) {
2766 wret
= push_leaf_right(trans
, root
, path
, data_size
, 0);
2770 wret
= push_leaf_left(trans
, root
, path
, data_size
, 0);
2776 /* did the pushes work? */
2777 if (btrfs_leaf_free_space(root
, l
) >= data_size
)
2781 if (!path
->nodes
[1]) {
2782 ret
= insert_new_root(trans
, root
, path
, 1);
2789 slot
= path
->slots
[0];
2790 nritems
= btrfs_header_nritems(l
);
2791 mid
= (nritems
+ 1) / 2;
2793 right
= btrfs_alloc_free_block(trans
, root
, root
->leafsize
,
2794 path
->nodes
[1]->start
,
2795 root
->root_key
.objectid
,
2796 trans
->transid
, 0, l
->start
, 0);
2797 if (IS_ERR(right
)) {
2799 return PTR_ERR(right
);
2802 memset_extent_buffer(right
, 0, 0, sizeof(struct btrfs_header
));
2803 btrfs_set_header_bytenr(right
, right
->start
);
2804 btrfs_set_header_generation(right
, trans
->transid
);
2805 btrfs_set_header_owner(right
, root
->root_key
.objectid
);
2806 btrfs_set_header_level(right
, 0);
2807 write_extent_buffer(right
, root
->fs_info
->fsid
,
2808 (unsigned long)btrfs_header_fsid(right
),
2811 write_extent_buffer(right
, root
->fs_info
->chunk_tree_uuid
,
2812 (unsigned long)btrfs_header_chunk_tree_uuid(right
),
2816 leaf_space_used(l
, mid
, nritems
- mid
) + data_size
>
2817 BTRFS_LEAF_DATA_SIZE(root
)) {
2818 if (slot
>= nritems
) {
2819 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
2820 btrfs_set_header_nritems(right
, 0);
2821 wret
= insert_ptr(trans
, root
, path
,
2822 &disk_key
, right
->start
,
2823 path
->slots
[1] + 1, 1);
2827 btrfs_tree_unlock(path
->nodes
[0]);
2828 free_extent_buffer(path
->nodes
[0]);
2829 path
->nodes
[0] = right
;
2831 path
->slots
[1] += 1;
2832 btrfs_mark_buffer_dirty(right
);
2836 if (mid
!= nritems
&&
2837 leaf_space_used(l
, mid
, nritems
- mid
) +
2838 data_size
> BTRFS_LEAF_DATA_SIZE(root
)) {
2843 if (leaf_space_used(l
, 0, mid
) + data_size
>
2844 BTRFS_LEAF_DATA_SIZE(root
)) {
2845 if (!extend
&& data_size
&& slot
== 0) {
2846 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
2847 btrfs_set_header_nritems(right
, 0);
2848 wret
= insert_ptr(trans
, root
, path
,
2854 btrfs_tree_unlock(path
->nodes
[0]);
2855 free_extent_buffer(path
->nodes
[0]);
2856 path
->nodes
[0] = right
;
2858 if (path
->slots
[1] == 0) {
2859 wret
= fixup_low_keys(trans
, root
,
2860 path
, &disk_key
, 1);
2864 btrfs_mark_buffer_dirty(right
);
2866 } else if ((extend
|| !data_size
) && slot
== 0) {
2870 if (mid
!= nritems
&&
2871 leaf_space_used(l
, mid
, nritems
- mid
) +
2872 data_size
> BTRFS_LEAF_DATA_SIZE(root
)) {
2878 nritems
= nritems
- mid
;
2879 btrfs_set_header_nritems(right
, nritems
);
2880 data_copy_size
= btrfs_item_end_nr(l
, mid
) - leaf_data_end(root
, l
);
2882 copy_extent_buffer(right
, l
, btrfs_item_nr_offset(0),
2883 btrfs_item_nr_offset(mid
),
2884 nritems
* sizeof(struct btrfs_item
));
2886 copy_extent_buffer(right
, l
,
2887 btrfs_leaf_data(right
) + BTRFS_LEAF_DATA_SIZE(root
) -
2888 data_copy_size
, btrfs_leaf_data(l
) +
2889 leaf_data_end(root
, l
), data_copy_size
);
2891 rt_data_off
= BTRFS_LEAF_DATA_SIZE(root
) -
2892 btrfs_item_end_nr(l
, mid
);
2894 for (i
= 0; i
< nritems
; i
++) {
2895 struct btrfs_item
*item
= btrfs_item_nr(right
, i
);
2898 if (!right
->map_token
) {
2899 map_extent_buffer(right
, (unsigned long)item
,
2900 sizeof(struct btrfs_item
),
2901 &right
->map_token
, &right
->kaddr
,
2902 &right
->map_start
, &right
->map_len
,
2906 ioff
= btrfs_item_offset(right
, item
);
2907 btrfs_set_item_offset(right
, item
, ioff
+ rt_data_off
);
2910 if (right
->map_token
) {
2911 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
2912 right
->map_token
= NULL
;
2915 btrfs_set_header_nritems(l
, mid
);
2917 btrfs_item_key(right
, &disk_key
, 0);
2918 wret
= insert_ptr(trans
, root
, path
, &disk_key
, right
->start
,
2919 path
->slots
[1] + 1, 1);
2923 btrfs_mark_buffer_dirty(right
);
2924 btrfs_mark_buffer_dirty(l
);
2925 BUG_ON(path
->slots
[0] != slot
);
2927 ret
= btrfs_update_ref(trans
, root
, l
, right
, 0, nritems
);
2931 btrfs_tree_unlock(path
->nodes
[0]);
2932 free_extent_buffer(path
->nodes
[0]);
2933 path
->nodes
[0] = right
;
2934 path
->slots
[0] -= mid
;
2935 path
->slots
[1] += 1;
2937 btrfs_tree_unlock(right
);
2938 free_extent_buffer(right
);
2941 BUG_ON(path
->slots
[0] < 0);
2944 BUG_ON(num_doubles
!= 0);
2952 * This function splits a single item into two items,
2953 * giving 'new_key' to the new item and splitting the
2954 * old one at split_offset (from the start of the item).
2956 * The path may be released by this operation. After
2957 * the split, the path is pointing to the old item. The
2958 * new item is going to be in the same node as the old one.
2960 * Note, the item being split must be smaller enough to live alone on
2961 * a tree block with room for one extra struct btrfs_item
2963 * This allows us to split the item in place, keeping a lock on the
2964 * leaf the entire time.
2966 int btrfs_split_item(struct btrfs_trans_handle
*trans
,
2967 struct btrfs_root
*root
,
2968 struct btrfs_path
*path
,
2969 struct btrfs_key
*new_key
,
2970 unsigned long split_offset
)
2973 struct extent_buffer
*leaf
;
2974 struct btrfs_key orig_key
;
2975 struct btrfs_item
*item
;
2976 struct btrfs_item
*new_item
;
2981 struct btrfs_disk_key disk_key
;
2984 leaf
= path
->nodes
[0];
2985 btrfs_item_key_to_cpu(leaf
, &orig_key
, path
->slots
[0]);
2986 if (btrfs_leaf_free_space(root
, leaf
) >= sizeof(struct btrfs_item
))
2989 item_size
= btrfs_item_size_nr(leaf
, path
->slots
[0]);
2990 btrfs_release_path(root
, path
);
2992 path
->search_for_split
= 1;
2993 path
->keep_locks
= 1;
2995 ret
= btrfs_search_slot(trans
, root
, &orig_key
, path
, 0, 1);
2996 path
->search_for_split
= 0;
2998 /* if our item isn't there or got smaller, return now */
2999 if (ret
!= 0 || item_size
!= btrfs_item_size_nr(path
->nodes
[0],
3001 path
->keep_locks
= 0;
3005 ret
= split_leaf(trans
, root
, &orig_key
, path
,
3006 sizeof(struct btrfs_item
), 1);
3007 path
->keep_locks
= 0;
3011 * make sure any changes to the path from split_leaf leave it
3012 * in a blocking state
3014 btrfs_set_path_blocking(path
);
3016 leaf
= path
->nodes
[0];
3017 BUG_ON(btrfs_leaf_free_space(root
, leaf
) < sizeof(struct btrfs_item
));
3020 item
= btrfs_item_nr(leaf
, path
->slots
[0]);
3021 orig_offset
= btrfs_item_offset(leaf
, item
);
3022 item_size
= btrfs_item_size(leaf
, item
);
3025 buf
= kmalloc(item_size
, GFP_NOFS
);
3026 read_extent_buffer(leaf
, buf
, btrfs_item_ptr_offset(leaf
,
3027 path
->slots
[0]), item_size
);
3028 slot
= path
->slots
[0] + 1;
3029 leaf
= path
->nodes
[0];
3031 nritems
= btrfs_header_nritems(leaf
);
3033 if (slot
!= nritems
) {
3034 /* shift the items */
3035 memmove_extent_buffer(leaf
, btrfs_item_nr_offset(slot
+ 1),
3036 btrfs_item_nr_offset(slot
),
3037 (nritems
- slot
) * sizeof(struct btrfs_item
));
3041 btrfs_cpu_key_to_disk(&disk_key
, new_key
);
3042 btrfs_set_item_key(leaf
, &disk_key
, slot
);
3044 new_item
= btrfs_item_nr(leaf
, slot
);
3046 btrfs_set_item_offset(leaf
, new_item
, orig_offset
);
3047 btrfs_set_item_size(leaf
, new_item
, item_size
- split_offset
);
3049 btrfs_set_item_offset(leaf
, item
,
3050 orig_offset
+ item_size
- split_offset
);
3051 btrfs_set_item_size(leaf
, item
, split_offset
);
3053 btrfs_set_header_nritems(leaf
, nritems
+ 1);
3055 /* write the data for the start of the original item */
3056 write_extent_buffer(leaf
, buf
,
3057 btrfs_item_ptr_offset(leaf
, path
->slots
[0]),
3060 /* write the data for the new item */
3061 write_extent_buffer(leaf
, buf
+ split_offset
,
3062 btrfs_item_ptr_offset(leaf
, slot
),
3063 item_size
- split_offset
);
3064 btrfs_mark_buffer_dirty(leaf
);
3067 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
3068 btrfs_print_leaf(root
, leaf
);
3076 * make the item pointed to by the path smaller. new_size indicates
3077 * how small to make it, and from_end tells us if we just chop bytes
3078 * off the end of the item or if we shift the item to chop bytes off
3081 int btrfs_truncate_item(struct btrfs_trans_handle
*trans
,
3082 struct btrfs_root
*root
,
3083 struct btrfs_path
*path
,
3084 u32 new_size
, int from_end
)
3089 struct extent_buffer
*leaf
;
3090 struct btrfs_item
*item
;
3092 unsigned int data_end
;
3093 unsigned int old_data_start
;
3094 unsigned int old_size
;
3095 unsigned int size_diff
;
3098 slot_orig
= path
->slots
[0];
3099 leaf
= path
->nodes
[0];
3100 slot
= path
->slots
[0];
3102 old_size
= btrfs_item_size_nr(leaf
, slot
);
3103 if (old_size
== new_size
)
3106 nritems
= btrfs_header_nritems(leaf
);
3107 data_end
= leaf_data_end(root
, leaf
);
3109 old_data_start
= btrfs_item_offset_nr(leaf
, slot
);
3111 size_diff
= old_size
- new_size
;
3114 BUG_ON(slot
>= nritems
);
3117 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3119 /* first correct the data pointers */
3120 for (i
= slot
; i
< nritems
; i
++) {
3122 item
= btrfs_item_nr(leaf
, i
);
3124 if (!leaf
->map_token
) {
3125 map_extent_buffer(leaf
, (unsigned long)item
,
3126 sizeof(struct btrfs_item
),
3127 &leaf
->map_token
, &leaf
->kaddr
,
3128 &leaf
->map_start
, &leaf
->map_len
,
3132 ioff
= btrfs_item_offset(leaf
, item
);
3133 btrfs_set_item_offset(leaf
, item
, ioff
+ size_diff
);
3136 if (leaf
->map_token
) {
3137 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
3138 leaf
->map_token
= NULL
;
3141 /* shift the data */
3143 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
3144 data_end
+ size_diff
, btrfs_leaf_data(leaf
) +
3145 data_end
, old_data_start
+ new_size
- data_end
);
3147 struct btrfs_disk_key disk_key
;
3150 btrfs_item_key(leaf
, &disk_key
, slot
);
3152 if (btrfs_disk_key_type(&disk_key
) == BTRFS_EXTENT_DATA_KEY
) {
3154 struct btrfs_file_extent_item
*fi
;
3156 fi
= btrfs_item_ptr(leaf
, slot
,
3157 struct btrfs_file_extent_item
);
3158 fi
= (struct btrfs_file_extent_item
*)(
3159 (unsigned long)fi
- size_diff
);
3161 if (btrfs_file_extent_type(leaf
, fi
) ==
3162 BTRFS_FILE_EXTENT_INLINE
) {
3163 ptr
= btrfs_item_ptr_offset(leaf
, slot
);
3164 memmove_extent_buffer(leaf
, ptr
,
3166 offsetof(struct btrfs_file_extent_item
,
3171 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
3172 data_end
+ size_diff
, btrfs_leaf_data(leaf
) +
3173 data_end
, old_data_start
- data_end
);
3175 offset
= btrfs_disk_key_offset(&disk_key
);
3176 btrfs_set_disk_key_offset(&disk_key
, offset
+ size_diff
);
3177 btrfs_set_item_key(leaf
, &disk_key
, slot
);
3179 fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
3182 item
= btrfs_item_nr(leaf
, slot
);
3183 btrfs_set_item_size(leaf
, item
, new_size
);
3184 btrfs_mark_buffer_dirty(leaf
);
3187 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
3188 btrfs_print_leaf(root
, leaf
);
3195 * make the item pointed to by the path bigger, data_size is the new size.
3197 int btrfs_extend_item(struct btrfs_trans_handle
*trans
,
3198 struct btrfs_root
*root
, struct btrfs_path
*path
,
3204 struct extent_buffer
*leaf
;
3205 struct btrfs_item
*item
;
3207 unsigned int data_end
;
3208 unsigned int old_data
;
3209 unsigned int old_size
;
3212 slot_orig
= path
->slots
[0];
3213 leaf
= path
->nodes
[0];
3215 nritems
= btrfs_header_nritems(leaf
);
3216 data_end
= leaf_data_end(root
, leaf
);
3218 if (btrfs_leaf_free_space(root
, leaf
) < data_size
) {
3219 btrfs_print_leaf(root
, leaf
);
3222 slot
= path
->slots
[0];
3223 old_data
= btrfs_item_end_nr(leaf
, slot
);
3226 if (slot
>= nritems
) {
3227 btrfs_print_leaf(root
, leaf
);
3228 printk(KERN_CRIT
"slot %d too large, nritems %d\n",
3234 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3236 /* first correct the data pointers */
3237 for (i
= slot
; i
< nritems
; i
++) {
3239 item
= btrfs_item_nr(leaf
, i
);
3241 if (!leaf
->map_token
) {
3242 map_extent_buffer(leaf
, (unsigned long)item
,
3243 sizeof(struct btrfs_item
),
3244 &leaf
->map_token
, &leaf
->kaddr
,
3245 &leaf
->map_start
, &leaf
->map_len
,
3248 ioff
= btrfs_item_offset(leaf
, item
);
3249 btrfs_set_item_offset(leaf
, item
, ioff
- data_size
);
3252 if (leaf
->map_token
) {
3253 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
3254 leaf
->map_token
= NULL
;
3257 /* shift the data */
3258 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
3259 data_end
- data_size
, btrfs_leaf_data(leaf
) +
3260 data_end
, old_data
- data_end
);
3262 data_end
= old_data
;
3263 old_size
= btrfs_item_size_nr(leaf
, slot
);
3264 item
= btrfs_item_nr(leaf
, slot
);
3265 btrfs_set_item_size(leaf
, item
, old_size
+ data_size
);
3266 btrfs_mark_buffer_dirty(leaf
);
3269 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
3270 btrfs_print_leaf(root
, leaf
);
3277 * Given a key and some data, insert items into the tree.
3278 * This does all the path init required, making room in the tree if needed.
3279 * Returns the number of keys that were inserted.
3281 int btrfs_insert_some_items(struct btrfs_trans_handle
*trans
,
3282 struct btrfs_root
*root
,
3283 struct btrfs_path
*path
,
3284 struct btrfs_key
*cpu_key
, u32
*data_size
,
3287 struct extent_buffer
*leaf
;
3288 struct btrfs_item
*item
;
3295 unsigned int data_end
;
3296 struct btrfs_disk_key disk_key
;
3297 struct btrfs_key found_key
;
3299 for (i
= 0; i
< nr
; i
++) {
3300 if (total_size
+ data_size
[i
] + sizeof(struct btrfs_item
) >
3301 BTRFS_LEAF_DATA_SIZE(root
)) {
3305 total_data
+= data_size
[i
];
3306 total_size
+= data_size
[i
] + sizeof(struct btrfs_item
);
3310 ret
= btrfs_search_slot(trans
, root
, cpu_key
, path
, total_size
, 1);
3316 leaf
= path
->nodes
[0];
3318 nritems
= btrfs_header_nritems(leaf
);
3319 data_end
= leaf_data_end(root
, leaf
);
3321 if (btrfs_leaf_free_space(root
, leaf
) < total_size
) {
3322 for (i
= nr
; i
>= 0; i
--) {
3323 total_data
-= data_size
[i
];
3324 total_size
-= data_size
[i
] + sizeof(struct btrfs_item
);
3325 if (total_size
< btrfs_leaf_free_space(root
, leaf
))
3331 slot
= path
->slots
[0];
3334 if (slot
!= nritems
) {
3335 unsigned int old_data
= btrfs_item_end_nr(leaf
, slot
);
3337 item
= btrfs_item_nr(leaf
, slot
);
3338 btrfs_item_key_to_cpu(leaf
, &found_key
, slot
);
3340 /* figure out how many keys we can insert in here */
3341 total_data
= data_size
[0];
3342 for (i
= 1; i
< nr
; i
++) {
3343 if (comp_cpu_keys(&found_key
, cpu_key
+ i
) <= 0)
3345 total_data
+= data_size
[i
];
3349 if (old_data
< data_end
) {
3350 btrfs_print_leaf(root
, leaf
);
3351 printk(KERN_CRIT
"slot %d old_data %d data_end %d\n",
3352 slot
, old_data
, data_end
);
3356 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3358 /* first correct the data pointers */
3359 WARN_ON(leaf
->map_token
);
3360 for (i
= slot
; i
< nritems
; i
++) {
3363 item
= btrfs_item_nr(leaf
, i
);
3364 if (!leaf
->map_token
) {
3365 map_extent_buffer(leaf
, (unsigned long)item
,
3366 sizeof(struct btrfs_item
),
3367 &leaf
->map_token
, &leaf
->kaddr
,
3368 &leaf
->map_start
, &leaf
->map_len
,
3372 ioff
= btrfs_item_offset(leaf
, item
);
3373 btrfs_set_item_offset(leaf
, item
, ioff
- total_data
);
3375 if (leaf
->map_token
) {
3376 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
3377 leaf
->map_token
= NULL
;
3380 /* shift the items */
3381 memmove_extent_buffer(leaf
, btrfs_item_nr_offset(slot
+ nr
),
3382 btrfs_item_nr_offset(slot
),
3383 (nritems
- slot
) * sizeof(struct btrfs_item
));
3385 /* shift the data */
3386 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
3387 data_end
- total_data
, btrfs_leaf_data(leaf
) +
3388 data_end
, old_data
- data_end
);
3389 data_end
= old_data
;
3392 * this sucks but it has to be done, if we are inserting at
3393 * the end of the leaf only insert 1 of the items, since we
3394 * have no way of knowing whats on the next leaf and we'd have
3395 * to drop our current locks to figure it out
3400 /* setup the item for the new data */
3401 for (i
= 0; i
< nr
; i
++) {
3402 btrfs_cpu_key_to_disk(&disk_key
, cpu_key
+ i
);
3403 btrfs_set_item_key(leaf
, &disk_key
, slot
+ i
);
3404 item
= btrfs_item_nr(leaf
, slot
+ i
);
3405 btrfs_set_item_offset(leaf
, item
, data_end
- data_size
[i
]);
3406 data_end
-= data_size
[i
];
3407 btrfs_set_item_size(leaf
, item
, data_size
[i
]);
3409 btrfs_set_header_nritems(leaf
, nritems
+ nr
);
3410 btrfs_mark_buffer_dirty(leaf
);
3414 btrfs_cpu_key_to_disk(&disk_key
, cpu_key
);
3415 ret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
3418 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
3419 btrfs_print_leaf(root
, leaf
);
3429 * Given a key and some data, insert items into the tree.
3430 * This does all the path init required, making room in the tree if needed.
3432 int btrfs_insert_empty_items(struct btrfs_trans_handle
*trans
,
3433 struct btrfs_root
*root
,
3434 struct btrfs_path
*path
,
3435 struct btrfs_key
*cpu_key
, u32
*data_size
,
3438 struct extent_buffer
*leaf
;
3439 struct btrfs_item
*item
;
3447 unsigned int data_end
;
3448 struct btrfs_disk_key disk_key
;
3450 for (i
= 0; i
< nr
; i
++)
3451 total_data
+= data_size
[i
];
3453 total_size
= total_data
+ (nr
* sizeof(struct btrfs_item
));
3454 ret
= btrfs_search_slot(trans
, root
, cpu_key
, path
, total_size
, 1);
3460 slot_orig
= path
->slots
[0];
3461 leaf
= path
->nodes
[0];
3463 nritems
= btrfs_header_nritems(leaf
);
3464 data_end
= leaf_data_end(root
, leaf
);
3466 if (btrfs_leaf_free_space(root
, leaf
) < total_size
) {
3467 btrfs_print_leaf(root
, leaf
);
3468 printk(KERN_CRIT
"not enough freespace need %u have %d\n",
3469 total_size
, btrfs_leaf_free_space(root
, leaf
));
3473 slot
= path
->slots
[0];
3476 if (slot
!= nritems
) {
3477 unsigned int old_data
= btrfs_item_end_nr(leaf
, slot
);
3479 if (old_data
< data_end
) {
3480 btrfs_print_leaf(root
, leaf
);
3481 printk(KERN_CRIT
"slot %d old_data %d data_end %d\n",
3482 slot
, old_data
, data_end
);
3486 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3488 /* first correct the data pointers */
3489 WARN_ON(leaf
->map_token
);
3490 for (i
= slot
; i
< nritems
; i
++) {
3493 item
= btrfs_item_nr(leaf
, i
);
3494 if (!leaf
->map_token
) {
3495 map_extent_buffer(leaf
, (unsigned long)item
,
3496 sizeof(struct btrfs_item
),
3497 &leaf
->map_token
, &leaf
->kaddr
,
3498 &leaf
->map_start
, &leaf
->map_len
,
3502 ioff
= btrfs_item_offset(leaf
, item
);
3503 btrfs_set_item_offset(leaf
, item
, ioff
- total_data
);
3505 if (leaf
->map_token
) {
3506 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
3507 leaf
->map_token
= NULL
;
3510 /* shift the items */
3511 memmove_extent_buffer(leaf
, btrfs_item_nr_offset(slot
+ nr
),
3512 btrfs_item_nr_offset(slot
),
3513 (nritems
- slot
) * sizeof(struct btrfs_item
));
3515 /* shift the data */
3516 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
3517 data_end
- total_data
, btrfs_leaf_data(leaf
) +
3518 data_end
, old_data
- data_end
);
3519 data_end
= old_data
;
3522 /* setup the item for the new data */
3523 for (i
= 0; i
< nr
; i
++) {
3524 btrfs_cpu_key_to_disk(&disk_key
, cpu_key
+ i
);
3525 btrfs_set_item_key(leaf
, &disk_key
, slot
+ i
);
3526 item
= btrfs_item_nr(leaf
, slot
+ i
);
3527 btrfs_set_item_offset(leaf
, item
, data_end
- data_size
[i
]);
3528 data_end
-= data_size
[i
];
3529 btrfs_set_item_size(leaf
, item
, data_size
[i
]);
3531 btrfs_set_header_nritems(leaf
, nritems
+ nr
);
3532 btrfs_mark_buffer_dirty(leaf
);
3536 btrfs_cpu_key_to_disk(&disk_key
, cpu_key
);
3537 ret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
3540 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
3541 btrfs_print_leaf(root
, leaf
);
3545 btrfs_unlock_up_safe(path
, 1);
3550 * Given a key and some data, insert an item into the tree.
3551 * This does all the path init required, making room in the tree if needed.
3553 int btrfs_insert_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
3554 *root
, struct btrfs_key
*cpu_key
, void *data
, u32
3558 struct btrfs_path
*path
;
3559 struct extent_buffer
*leaf
;
3562 path
= btrfs_alloc_path();
3564 ret
= btrfs_insert_empty_item(trans
, root
, path
, cpu_key
, data_size
);
3566 leaf
= path
->nodes
[0];
3567 ptr
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
3568 write_extent_buffer(leaf
, data
, ptr
, data_size
);
3569 btrfs_mark_buffer_dirty(leaf
);
3571 btrfs_free_path(path
);
3576 * delete the pointer from a given node.
3578 * the tree should have been previously balanced so the deletion does not
3581 static int del_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
3582 struct btrfs_path
*path
, int level
, int slot
)
3584 struct extent_buffer
*parent
= path
->nodes
[level
];
3589 nritems
= btrfs_header_nritems(parent
);
3590 if (slot
!= nritems
- 1) {
3591 memmove_extent_buffer(parent
,
3592 btrfs_node_key_ptr_offset(slot
),
3593 btrfs_node_key_ptr_offset(slot
+ 1),
3594 sizeof(struct btrfs_key_ptr
) *
3595 (nritems
- slot
- 1));
3598 btrfs_set_header_nritems(parent
, nritems
);
3599 if (nritems
== 0 && parent
== root
->node
) {
3600 BUG_ON(btrfs_header_level(root
->node
) != 1);
3601 /* just turn the root into a leaf and break */
3602 btrfs_set_header_level(root
->node
, 0);
3603 } else if (slot
== 0) {
3604 struct btrfs_disk_key disk_key
;
3606 btrfs_node_key(parent
, &disk_key
, 0);
3607 wret
= fixup_low_keys(trans
, root
, path
, &disk_key
, level
+ 1);
3611 btrfs_mark_buffer_dirty(parent
);
3616 * a helper function to delete the leaf pointed to by path->slots[1] and
3617 * path->nodes[1]. bytenr is the node block pointer, but since the callers
3618 * already know it, it is faster to have them pass it down than to
3619 * read it out of the node again.
3621 * This deletes the pointer in path->nodes[1] and frees the leaf
3622 * block extent. zero is returned if it all worked out, < 0 otherwise.
3624 * The path must have already been setup for deleting the leaf, including
3625 * all the proper balancing. path->nodes[1] must be locked.
3627 noinline
int btrfs_del_leaf(struct btrfs_trans_handle
*trans
,
3628 struct btrfs_root
*root
,
3629 struct btrfs_path
*path
, u64 bytenr
)
3632 u64 root_gen
= btrfs_header_generation(path
->nodes
[1]);
3633 u64 parent_start
= path
->nodes
[1]->start
;
3634 u64 parent_owner
= btrfs_header_owner(path
->nodes
[1]);
3636 ret
= del_ptr(trans
, root
, path
, 1, path
->slots
[1]);
3641 * btrfs_free_extent is expensive, we want to make sure we
3642 * aren't holding any locks when we call it
3644 btrfs_unlock_up_safe(path
, 0);
3646 ret
= btrfs_free_extent(trans
, root
, bytenr
,
3647 btrfs_level_size(root
, 0),
3648 parent_start
, parent_owner
,
3653 * delete the item at the leaf level in path. If that empties
3654 * the leaf, remove it from the tree
3656 int btrfs_del_items(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
3657 struct btrfs_path
*path
, int slot
, int nr
)
3659 struct extent_buffer
*leaf
;
3660 struct btrfs_item
*item
;
3668 leaf
= path
->nodes
[0];
3669 last_off
= btrfs_item_offset_nr(leaf
, slot
+ nr
- 1);
3671 for (i
= 0; i
< nr
; i
++)
3672 dsize
+= btrfs_item_size_nr(leaf
, slot
+ i
);
3674 nritems
= btrfs_header_nritems(leaf
);
3676 if (slot
+ nr
!= nritems
) {
3677 int data_end
= leaf_data_end(root
, leaf
);
3679 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
3681 btrfs_leaf_data(leaf
) + data_end
,
3682 last_off
- data_end
);
3684 for (i
= slot
+ nr
; i
< nritems
; i
++) {
3687 item
= btrfs_item_nr(leaf
, i
);
3688 if (!leaf
->map_token
) {
3689 map_extent_buffer(leaf
, (unsigned long)item
,
3690 sizeof(struct btrfs_item
),
3691 &leaf
->map_token
, &leaf
->kaddr
,
3692 &leaf
->map_start
, &leaf
->map_len
,
3695 ioff
= btrfs_item_offset(leaf
, item
);
3696 btrfs_set_item_offset(leaf
, item
, ioff
+ dsize
);
3699 if (leaf
->map_token
) {
3700 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
3701 leaf
->map_token
= NULL
;
3704 memmove_extent_buffer(leaf
, btrfs_item_nr_offset(slot
),
3705 btrfs_item_nr_offset(slot
+ nr
),
3706 sizeof(struct btrfs_item
) *
3707 (nritems
- slot
- nr
));
3709 btrfs_set_header_nritems(leaf
, nritems
- nr
);
3712 /* delete the leaf if we've emptied it */
3714 if (leaf
== root
->node
) {
3715 btrfs_set_header_level(leaf
, 0);
3717 ret
= btrfs_del_leaf(trans
, root
, path
, leaf
->start
);
3721 int used
= leaf_space_used(leaf
, 0, nritems
);
3723 struct btrfs_disk_key disk_key
;
3725 btrfs_item_key(leaf
, &disk_key
, 0);
3726 wret
= fixup_low_keys(trans
, root
, path
,
3732 /* delete the leaf if it is mostly empty */
3733 if (used
< BTRFS_LEAF_DATA_SIZE(root
) / 4) {
3734 /* push_leaf_left fixes the path.
3735 * make sure the path still points to our leaf
3736 * for possible call to del_ptr below
3738 slot
= path
->slots
[1];
3739 extent_buffer_get(leaf
);
3741 wret
= push_leaf_left(trans
, root
, path
, 1, 1);
3742 if (wret
< 0 && wret
!= -ENOSPC
)
3745 if (path
->nodes
[0] == leaf
&&
3746 btrfs_header_nritems(leaf
)) {
3747 wret
= push_leaf_right(trans
, root
, path
, 1, 1);
3748 if (wret
< 0 && wret
!= -ENOSPC
)
3752 if (btrfs_header_nritems(leaf
) == 0) {
3753 path
->slots
[1] = slot
;
3754 ret
= btrfs_del_leaf(trans
, root
, path
,
3757 free_extent_buffer(leaf
);
3759 /* if we're still in the path, make sure
3760 * we're dirty. Otherwise, one of the
3761 * push_leaf functions must have already
3762 * dirtied this buffer
3764 if (path
->nodes
[0] == leaf
)
3765 btrfs_mark_buffer_dirty(leaf
);
3766 free_extent_buffer(leaf
);
3769 btrfs_mark_buffer_dirty(leaf
);
3776 * search the tree again to find a leaf with lesser keys
3777 * returns 0 if it found something or 1 if there are no lesser leaves.
3778 * returns < 0 on io errors.
3780 * This may release the path, and so you may lose any locks held at the
3783 int btrfs_prev_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
)
3785 struct btrfs_key key
;
3786 struct btrfs_disk_key found_key
;
3789 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, 0);
3793 else if (key
.type
> 0)
3795 else if (key
.objectid
> 0)
3800 btrfs_release_path(root
, path
);
3801 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
3804 btrfs_item_key(path
->nodes
[0], &found_key
, 0);
3805 ret
= comp_keys(&found_key
, &key
);
3812 * A helper function to walk down the tree starting at min_key, and looking
3813 * for nodes or leaves that are either in cache or have a minimum
3814 * transaction id. This is used by the btree defrag code, and tree logging
3816 * This does not cow, but it does stuff the starting key it finds back
3817 * into min_key, so you can call btrfs_search_slot with cow=1 on the
3818 * key and get a writable path.
3820 * This does lock as it descends, and path->keep_locks should be set
3821 * to 1 by the caller.
3823 * This honors path->lowest_level to prevent descent past a given level
3826 * min_trans indicates the oldest transaction that you are interested
3827 * in walking through. Any nodes or leaves older than min_trans are
3828 * skipped over (without reading them).
3830 * returns zero if something useful was found, < 0 on error and 1 if there
3831 * was nothing in the tree that matched the search criteria.
3833 int btrfs_search_forward(struct btrfs_root
*root
, struct btrfs_key
*min_key
,
3834 struct btrfs_key
*max_key
,
3835 struct btrfs_path
*path
, int cache_only
,
3838 struct extent_buffer
*cur
;
3839 struct btrfs_key found_key
;
3846 WARN_ON(!path
->keep_locks
);
3848 cur
= btrfs_lock_root_node(root
);
3849 level
= btrfs_header_level(cur
);
3850 WARN_ON(path
->nodes
[level
]);
3851 path
->nodes
[level
] = cur
;
3852 path
->locks
[level
] = 1;
3854 if (btrfs_header_generation(cur
) < min_trans
) {
3859 nritems
= btrfs_header_nritems(cur
);
3860 level
= btrfs_header_level(cur
);
3861 sret
= bin_search(cur
, min_key
, level
, &slot
);
3863 /* at the lowest level, we're done, setup the path and exit */
3864 if (level
== path
->lowest_level
) {
3865 if (slot
>= nritems
)
3868 path
->slots
[level
] = slot
;
3869 btrfs_item_key_to_cpu(cur
, &found_key
, slot
);
3872 if (sret
&& slot
> 0)
3875 * check this node pointer against the cache_only and
3876 * min_trans parameters. If it isn't in cache or is too
3877 * old, skip to the next one.
3879 while (slot
< nritems
) {
3882 struct extent_buffer
*tmp
;
3883 struct btrfs_disk_key disk_key
;
3885 blockptr
= btrfs_node_blockptr(cur
, slot
);
3886 gen
= btrfs_node_ptr_generation(cur
, slot
);
3887 if (gen
< min_trans
) {
3895 btrfs_node_key(cur
, &disk_key
, slot
);
3896 if (comp_keys(&disk_key
, max_key
) >= 0) {
3902 tmp
= btrfs_find_tree_block(root
, blockptr
,
3903 btrfs_level_size(root
, level
- 1));
3905 if (tmp
&& btrfs_buffer_uptodate(tmp
, gen
)) {
3906 free_extent_buffer(tmp
);
3910 free_extent_buffer(tmp
);
3915 * we didn't find a candidate key in this node, walk forward
3916 * and find another one
3918 if (slot
>= nritems
) {
3919 path
->slots
[level
] = slot
;
3920 btrfs_set_path_blocking(path
);
3921 sret
= btrfs_find_next_key(root
, path
, min_key
, level
,
3922 cache_only
, min_trans
);
3924 btrfs_release_path(root
, path
);
3927 btrfs_clear_path_blocking(path
);
3931 /* save our key for returning back */
3932 btrfs_node_key_to_cpu(cur
, &found_key
, slot
);
3933 path
->slots
[level
] = slot
;
3934 if (level
== path
->lowest_level
) {
3936 unlock_up(path
, level
, 1);
3939 btrfs_set_path_blocking(path
);
3940 cur
= read_node_slot(root
, cur
, slot
);
3942 btrfs_tree_lock(cur
);
3944 path
->locks
[level
- 1] = 1;
3945 path
->nodes
[level
- 1] = cur
;
3946 unlock_up(path
, level
, 1);
3947 btrfs_clear_path_blocking(path
);
3951 memcpy(min_key
, &found_key
, sizeof(found_key
));
3952 btrfs_set_path_blocking(path
);
3957 * this is similar to btrfs_next_leaf, but does not try to preserve
3958 * and fixup the path. It looks for and returns the next key in the
3959 * tree based on the current path and the cache_only and min_trans
3962 * 0 is returned if another key is found, < 0 if there are any errors
3963 * and 1 is returned if there are no higher keys in the tree
3965 * path->keep_locks should be set to 1 on the search made before
3966 * calling this function.
3968 int btrfs_find_next_key(struct btrfs_root
*root
, struct btrfs_path
*path
,
3969 struct btrfs_key
*key
, int lowest_level
,
3970 int cache_only
, u64 min_trans
)
3972 int level
= lowest_level
;
3974 struct extent_buffer
*c
;
3976 WARN_ON(!path
->keep_locks
);
3977 while (level
< BTRFS_MAX_LEVEL
) {
3978 if (!path
->nodes
[level
])
3981 slot
= path
->slots
[level
] + 1;
3982 c
= path
->nodes
[level
];
3984 if (slot
>= btrfs_header_nritems(c
)) {
3986 if (level
== BTRFS_MAX_LEVEL
)
3991 btrfs_item_key_to_cpu(c
, key
, slot
);
3993 u64 blockptr
= btrfs_node_blockptr(c
, slot
);
3994 u64 gen
= btrfs_node_ptr_generation(c
, slot
);
3997 struct extent_buffer
*cur
;
3998 cur
= btrfs_find_tree_block(root
, blockptr
,
3999 btrfs_level_size(root
, level
- 1));
4000 if (!cur
|| !btrfs_buffer_uptodate(cur
, gen
)) {
4003 free_extent_buffer(cur
);
4006 free_extent_buffer(cur
);
4008 if (gen
< min_trans
) {
4012 btrfs_node_key_to_cpu(c
, key
, slot
);
4020 * search the tree again to find a leaf with greater keys
4021 * returns 0 if it found something or 1 if there are no greater leaves.
4022 * returns < 0 on io errors.
4024 int btrfs_next_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
)
4028 struct extent_buffer
*c
;
4029 struct extent_buffer
*next
= NULL
;
4030 struct btrfs_key key
;
4034 nritems
= btrfs_header_nritems(path
->nodes
[0]);
4038 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, nritems
- 1);
4040 btrfs_release_path(root
, path
);
4041 path
->keep_locks
= 1;
4042 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
4043 path
->keep_locks
= 0;
4048 btrfs_set_path_blocking(path
);
4049 nritems
= btrfs_header_nritems(path
->nodes
[0]);
4051 * by releasing the path above we dropped all our locks. A balance
4052 * could have added more items next to the key that used to be
4053 * at the very end of the block. So, check again here and
4054 * advance the path if there are now more items available.
4056 if (nritems
> 0 && path
->slots
[0] < nritems
- 1) {
4061 while (level
< BTRFS_MAX_LEVEL
) {
4062 if (!path
->nodes
[level
])
4065 slot
= path
->slots
[level
] + 1;
4066 c
= path
->nodes
[level
];
4067 if (slot
>= btrfs_header_nritems(c
)) {
4069 if (level
== BTRFS_MAX_LEVEL
)
4075 btrfs_tree_unlock(next
);
4076 free_extent_buffer(next
);
4079 /* the path was set to blocking above */
4080 if (level
== 1 && (path
->locks
[1] || path
->skip_locking
) &&
4082 reada_for_search(root
, path
, level
, slot
, 0);
4084 next
= read_node_slot(root
, c
, slot
);
4085 if (!path
->skip_locking
) {
4086 WARN_ON(!btrfs_tree_locked(c
));
4087 btrfs_tree_lock(next
);
4088 btrfs_set_lock_blocking(next
);
4092 path
->slots
[level
] = slot
;
4095 c
= path
->nodes
[level
];
4096 if (path
->locks
[level
])
4097 btrfs_tree_unlock(c
);
4098 free_extent_buffer(c
);
4099 path
->nodes
[level
] = next
;
4100 path
->slots
[level
] = 0;
4101 if (!path
->skip_locking
)
4102 path
->locks
[level
] = 1;
4106 btrfs_set_path_blocking(path
);
4107 if (level
== 1 && path
->locks
[1] && path
->reada
)
4108 reada_for_search(root
, path
, level
, slot
, 0);
4109 next
= read_node_slot(root
, next
, 0);
4110 if (!path
->skip_locking
) {
4111 WARN_ON(!btrfs_tree_locked(path
->nodes
[level
]));
4112 btrfs_tree_lock(next
);
4113 btrfs_set_lock_blocking(next
);
4117 unlock_up(path
, 0, 1);
4122 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
4123 * searching until it gets past min_objectid or finds an item of 'type'
4125 * returns 0 if something is found, 1 if nothing was found and < 0 on error
4127 int btrfs_previous_item(struct btrfs_root
*root
,
4128 struct btrfs_path
*path
, u64 min_objectid
,
4131 struct btrfs_key found_key
;
4132 struct extent_buffer
*leaf
;
4137 if (path
->slots
[0] == 0) {
4138 btrfs_set_path_blocking(path
);
4139 ret
= btrfs_prev_leaf(root
, path
);
4145 leaf
= path
->nodes
[0];
4146 nritems
= btrfs_header_nritems(leaf
);
4149 if (path
->slots
[0] == nritems
)
4152 btrfs_item_key_to_cpu(leaf
, &found_key
, path
->slots
[0]);
4153 if (found_key
.type
== type
)
4155 if (found_key
.objectid
< min_objectid
)
4157 if (found_key
.objectid
== min_objectid
&&
4158 found_key
.type
< type
)