2 * Copyright (C) 2007 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.
21 #include "transaction.h"
22 #include "print-tree.h"
24 static int split_node(struct btrfs_trans_handle
*trans
, struct btrfs_root
25 *root
, struct btrfs_path
*path
, int level
);
26 static int split_leaf(struct btrfs_trans_handle
*trans
, struct btrfs_root
27 *root
, struct btrfs_key
*ins_key
,
28 struct btrfs_path
*path
, int data_size
);
29 static int push_node_left(struct btrfs_trans_handle
*trans
,
30 struct btrfs_root
*root
, struct extent_buffer
*dst
,
31 struct extent_buffer
*src
);
32 static int balance_node_right(struct btrfs_trans_handle
*trans
,
33 struct btrfs_root
*root
,
34 struct extent_buffer
*dst_buf
,
35 struct extent_buffer
*src_buf
);
36 static int del_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
37 struct btrfs_path
*path
, int level
, int slot
);
39 inline void btrfs_init_path(struct btrfs_path
*p
)
41 memset(p
, 0, sizeof(*p
));
44 struct btrfs_path
*btrfs_alloc_path(void)
46 struct btrfs_path
*path
;
47 path
= kmem_cache_alloc(btrfs_path_cachep
, GFP_NOFS
);
49 btrfs_init_path(path
);
55 void btrfs_free_path(struct btrfs_path
*p
)
57 btrfs_release_path(NULL
, p
);
58 kmem_cache_free(btrfs_path_cachep
, p
);
61 void btrfs_release_path(struct btrfs_root
*root
, struct btrfs_path
*p
)
64 for (i
= 0; i
< BTRFS_MAX_LEVEL
; i
++) {
67 free_extent_buffer(p
->nodes
[i
]);
69 memset(p
, 0, sizeof(*p
));
72 static int __btrfs_cow_block(struct btrfs_trans_handle
*trans
,
73 struct btrfs_root
*root
,
74 struct extent_buffer
*buf
,
75 struct extent_buffer
*parent
, int parent_slot
,
76 struct extent_buffer
**cow_ret
,
77 u64 search_start
, u64 empty_size
)
79 struct extent_buffer
*cow
;
81 int different_trans
= 0;
83 WARN_ON(root
->ref_cows
&& trans
->transid
!= root
->last_trans
);
85 cow
= btrfs_alloc_free_block(trans
, root
, buf
->len
,
86 search_start
, empty_size
);
90 copy_extent_buffer(cow
, buf
, 0, 0, cow
->len
);
91 btrfs_set_header_bytenr(cow
, cow
->start
);
92 btrfs_set_header_generation(cow
, trans
->transid
);
93 btrfs_set_header_owner(cow
, root
->root_key
.objectid
);
95 WARN_ON(btrfs_header_generation(buf
) > trans
->transid
);
96 if (btrfs_header_generation(buf
) != trans
->transid
) {
98 ret
= btrfs_inc_ref(trans
, root
, buf
);
102 clean_tree_block(trans
, root
, buf
);
105 if (buf
== root
->node
) {
107 extent_buffer_get(cow
);
108 if (buf
!= root
->commit_root
) {
109 btrfs_free_extent(trans
, root
, buf
->start
,
112 free_extent_buffer(buf
);
114 btrfs_set_node_blockptr(parent
, parent_slot
,
116 btrfs_mark_buffer_dirty(parent
);
117 WARN_ON(btrfs_header_generation(parent
) != trans
->transid
);
118 btrfs_free_extent(trans
, root
, buf
->start
, buf
->len
, 1);
120 free_extent_buffer(buf
);
121 btrfs_mark_buffer_dirty(cow
);
126 int btrfs_cow_block(struct btrfs_trans_handle
*trans
,
127 struct btrfs_root
*root
, struct extent_buffer
*buf
,
128 struct extent_buffer
*parent
, int parent_slot
,
129 struct extent_buffer
**cow_ret
)
133 if (trans
->transaction
!= root
->fs_info
->running_transaction
) {
134 printk(KERN_CRIT
"trans %Lu running %Lu\n", trans
->transid
,
135 root
->fs_info
->running_transaction
->transid
);
138 if (trans
->transid
!= root
->fs_info
->generation
) {
139 printk(KERN_CRIT
"trans %Lu running %Lu\n", trans
->transid
,
140 root
->fs_info
->generation
);
143 if (btrfs_header_generation(buf
) == trans
->transid
) {
148 search_start
= buf
->start
& ~((u64
)BTRFS_BLOCK_GROUP_SIZE
- 1);
149 ret
= __btrfs_cow_block(trans
, root
, buf
, parent
,
150 parent_slot
, cow_ret
, search_start
, 0);
154 static int close_blocks(u64 blocknr
, u64 other
, u32 blocksize
)
156 if (blocknr
< other
&& other
- (blocknr
+ blocksize
) < 32768)
158 if (blocknr
> other
&& blocknr
- (other
+ blocksize
) < 32768)
163 static int should_defrag_leaf(struct extent_buffer
*leaf
)
165 struct btrfs_key key
;
168 if (btrfs_buffer_defrag(leaf
))
171 nritems
= btrfs_header_nritems(leaf
);
175 btrfs_item_key_to_cpu(leaf
, &key
, 0);
176 if (key
.type
== BTRFS_DIR_ITEM_KEY
)
180 btrfs_item_key_to_cpu(leaf
, &key
, nritems
- 1);
181 if (key
.type
== BTRFS_DIR_ITEM_KEY
)
184 btrfs_item_key_to_cpu(leaf
, &key
, nritems
/ 2);
185 if (key
.type
== BTRFS_DIR_ITEM_KEY
)
191 int btrfs_realloc_node(struct btrfs_trans_handle
*trans
,
192 struct btrfs_root
*root
, struct extent_buffer
*parent
,
193 int cache_only
, u64
*last_ret
)
195 struct extent_buffer
*cur
;
196 struct extent_buffer
*tmp
;
198 u64 search_start
= *last_ret
;
210 if (trans
->transaction
!= root
->fs_info
->running_transaction
) {
211 printk(KERN_CRIT
"trans %Lu running %Lu\n", trans
->transid
,
212 root
->fs_info
->running_transaction
->transid
);
215 if (trans
->transid
!= root
->fs_info
->generation
) {
216 printk(KERN_CRIT
"trans %Lu running %Lu\n", trans
->transid
,
217 root
->fs_info
->generation
);
220 parent_level
= btrfs_header_level(parent
);
222 parent_nritems
= btrfs_header_nritems(parent
);
223 blocksize
= btrfs_level_size(root
, parent_level
- 1);
226 end_slot
= parent_nritems
;
228 if (parent_nritems
== 1)
231 for (i
= start_slot
; i
< end_slot
; i
++) {
233 blocknr
= btrfs_node_blockptr(parent
, i
);
235 last_block
= blocknr
;
237 other
= btrfs_node_blockptr(parent
, i
- 1);
238 close
= close_blocks(blocknr
, other
, blocksize
);
240 if (close
&& i
< end_slot
- 1) {
241 other
= btrfs_node_blockptr(parent
, i
+ 1);
242 close
= close_blocks(blocknr
, other
, blocksize
);
245 last_block
= blocknr
;
249 cur
= btrfs_find_tree_block(root
, blocknr
, blocksize
);
251 uptodate
= btrfs_buffer_uptodate(cur
);
254 if (!cur
|| !uptodate
||
255 (parent_level
!= 1 && !btrfs_buffer_defrag(cur
)) ||
256 (parent_level
== 1 && !should_defrag_leaf(cur
))) {
258 free_extent_buffer(cur
);
262 cur
= read_tree_block(root
, blocknr
,
264 } else if (!uptodate
) {
265 btrfs_read_buffer(cur
);
268 if (search_start
== 0)
269 search_start
= last_block
;
271 err
= __btrfs_cow_block(trans
, root
, cur
, parent
, i
,
274 (end_slot
- i
) * blocksize
));
276 free_extent_buffer(cur
);
279 search_start
= tmp
->start
;
280 *last_ret
= search_start
;
281 if (parent_level
== 1)
282 btrfs_clear_buffer_defrag(tmp
);
283 free_extent_buffer(tmp
);
289 * The leaf data grows from end-to-front in the node.
290 * this returns the address of the start of the last item,
291 * which is the stop of the leaf data stack
293 static inline unsigned int leaf_data_end(struct btrfs_root
*root
,
294 struct extent_buffer
*leaf
)
296 u32 nr
= btrfs_header_nritems(leaf
);
298 return BTRFS_LEAF_DATA_SIZE(root
);
299 return btrfs_item_offset_nr(leaf
, nr
- 1);
303 * compare two keys in a memcmp fashion
305 static int comp_keys(struct btrfs_disk_key
*disk
, struct btrfs_key
*k2
)
309 btrfs_disk_key_to_cpu(&k1
, disk
);
311 if (k1
.objectid
> k2
->objectid
)
313 if (k1
.objectid
< k2
->objectid
)
315 if (k1
.type
> k2
->type
)
317 if (k1
.type
< k2
->type
)
319 if (k1
.offset
> k2
->offset
)
321 if (k1
.offset
< k2
->offset
)
326 static int check_node(struct btrfs_root
*root
, struct btrfs_path
*path
,
329 struct extent_buffer
*parent
= NULL
;
330 struct extent_buffer
*node
= path
->nodes
[level
];
331 struct btrfs_disk_key parent_key
;
332 struct btrfs_disk_key node_key
;
335 struct btrfs_key cpukey
;
336 u32 nritems
= btrfs_header_nritems(node
);
338 if (path
->nodes
[level
+ 1])
339 parent
= path
->nodes
[level
+ 1];
341 slot
= path
->slots
[level
];
342 BUG_ON(nritems
== 0);
344 parent_slot
= path
->slots
[level
+ 1];
345 btrfs_node_key(parent
, &parent_key
, parent_slot
);
346 btrfs_node_key(node
, &node_key
, 0);
347 BUG_ON(memcmp(&parent_key
, &node_key
,
348 sizeof(struct btrfs_disk_key
)));
349 BUG_ON(btrfs_node_blockptr(parent
, parent_slot
) !=
350 btrfs_header_bytenr(node
));
352 BUG_ON(nritems
> BTRFS_NODEPTRS_PER_BLOCK(root
));
354 btrfs_node_key_to_cpu(node
, &cpukey
, slot
- 1);
355 btrfs_node_key(node
, &node_key
, slot
);
356 BUG_ON(comp_keys(&node_key
, &cpukey
) <= 0);
358 if (slot
< nritems
- 1) {
359 btrfs_node_key_to_cpu(node
, &cpukey
, slot
+ 1);
360 btrfs_node_key(node
, &node_key
, slot
);
361 BUG_ON(comp_keys(&node_key
, &cpukey
) >= 0);
366 static int check_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
,
369 struct extent_buffer
*leaf
= path
->nodes
[level
];
370 struct extent_buffer
*parent
= NULL
;
372 struct btrfs_key cpukey
;
373 struct btrfs_disk_key parent_key
;
374 struct btrfs_disk_key leaf_key
;
375 int slot
= path
->slots
[0];
377 u32 nritems
= btrfs_header_nritems(leaf
);
379 if (path
->nodes
[level
+ 1])
380 parent
= path
->nodes
[level
+ 1];
386 parent_slot
= path
->slots
[level
+ 1];
387 btrfs_node_key(parent
, &parent_key
, parent_slot
);
388 btrfs_item_key(leaf
, &leaf_key
, 0);
390 BUG_ON(memcmp(&parent_key
, &leaf_key
,
391 sizeof(struct btrfs_disk_key
)));
392 BUG_ON(btrfs_node_blockptr(parent
, parent_slot
) !=
393 btrfs_header_bytenr(leaf
));
396 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
397 btrfs_item_key_to_cpu(leaf
, &cpukey
, i
+ 1);
398 btrfs_item_key(leaf
, &leaf_key
, i
);
399 if (comp_keys(&leaf_key
, &cpukey
) >= 0) {
400 btrfs_print_leaf(root
, leaf
);
401 printk("slot %d offset bad key\n", i
);
404 if (btrfs_item_offset_nr(leaf
, i
) !=
405 btrfs_item_end_nr(leaf
, i
+ 1)) {
406 btrfs_print_leaf(root
, leaf
);
407 printk("slot %d offset bad\n", i
);
411 if (btrfs_item_offset_nr(leaf
, i
) +
412 btrfs_item_size_nr(leaf
, i
) !=
413 BTRFS_LEAF_DATA_SIZE(root
)) {
414 btrfs_print_leaf(root
, leaf
);
415 printk("slot %d first offset bad\n", i
);
421 if (btrfs_item_size_nr(leaf
, nritems
- 1) > 4096) {
422 btrfs_print_leaf(root
, leaf
);
423 printk("slot %d bad size \n", nritems
- 1);
428 if (slot
!= 0 && slot
< nritems
- 1) {
429 btrfs_item_key(leaf
, &leaf_key
, slot
);
430 btrfs_item_key_to_cpu(leaf
, &cpukey
, slot
- 1);
431 if (comp_keys(&leaf_key
, &cpukey
) <= 0) {
432 btrfs_print_leaf(root
, leaf
);
433 printk("slot %d offset bad key\n", slot
);
436 if (btrfs_item_offset_nr(leaf
, slot
- 1) !=
437 btrfs_item_end_nr(leaf
, slot
)) {
438 btrfs_print_leaf(root
, leaf
);
439 printk("slot %d offset bad\n", slot
);
443 if (slot
< nritems
- 1) {
444 btrfs_item_key(leaf
, &leaf_key
, slot
);
445 btrfs_item_key_to_cpu(leaf
, &cpukey
, slot
+ 1);
446 BUG_ON(comp_keys(&leaf_key
, &cpukey
) >= 0);
447 if (btrfs_item_offset_nr(leaf
, slot
) !=
448 btrfs_item_end_nr(leaf
, slot
+ 1)) {
449 btrfs_print_leaf(root
, leaf
);
450 printk("slot %d offset bad\n", slot
);
454 BUG_ON(btrfs_item_offset_nr(leaf
, 0) +
455 btrfs_item_size_nr(leaf
, 0) != BTRFS_LEAF_DATA_SIZE(root
));
459 static int check_block(struct btrfs_root
*root
, struct btrfs_path
*path
,
464 struct extent_buffer
*buf
= path
->nodes
[level
];
466 if (memcmp_extent_buffer(buf
, root
->fs_info
->fsid
,
467 (unsigned long)btrfs_header_fsid(buf
),
469 printk("warning bad block %Lu\n", buf
->start
);
474 return check_leaf(root
, path
, level
);
475 return check_node(root
, path
, level
);
479 * search for key in the extent_buffer. The items start at offset p,
480 * and they are item_size apart. There are 'max' items in p.
482 * the slot in the array is returned via slot, and it points to
483 * the place where you would insert key if it is not found in
486 * slot may point to max if the key is bigger than all of the keys
488 static int generic_bin_search(struct extent_buffer
*eb
, unsigned long p
,
489 int item_size
, struct btrfs_key
*key
,
496 struct btrfs_disk_key
*tmp
= NULL
;
497 struct btrfs_disk_key unaligned
;
498 unsigned long offset
;
499 char *map_token
= NULL
;
501 unsigned long map_start
= 0;
502 unsigned long map_len
= 0;
506 mid
= (low
+ high
) / 2;
507 offset
= p
+ mid
* item_size
;
509 if (!map_token
|| offset
< map_start
||
510 (offset
+ sizeof(struct btrfs_disk_key
)) >
511 map_start
+ map_len
) {
513 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
516 err
= map_extent_buffer(eb
, offset
,
517 sizeof(struct btrfs_disk_key
),
519 &map_start
, &map_len
, KM_USER0
);
522 tmp
= (struct btrfs_disk_key
*)(kaddr
+ offset
-
525 read_extent_buffer(eb
, &unaligned
,
526 offset
, sizeof(unaligned
));
531 tmp
= (struct btrfs_disk_key
*)(kaddr
+ offset
-
534 ret
= comp_keys(tmp
, key
);
543 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
549 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
554 * simple bin_search frontend that does the right thing for
557 static int bin_search(struct extent_buffer
*eb
, struct btrfs_key
*key
,
558 int level
, int *slot
)
561 return generic_bin_search(eb
,
562 offsetof(struct btrfs_leaf
, items
),
563 sizeof(struct btrfs_item
),
564 key
, btrfs_header_nritems(eb
),
567 return generic_bin_search(eb
,
568 offsetof(struct btrfs_node
, ptrs
),
569 sizeof(struct btrfs_key_ptr
),
570 key
, btrfs_header_nritems(eb
),
576 static struct extent_buffer
*read_node_slot(struct btrfs_root
*root
,
577 struct extent_buffer
*parent
, int slot
)
581 if (slot
>= btrfs_header_nritems(parent
))
583 return read_tree_block(root
, btrfs_node_blockptr(parent
, slot
),
584 btrfs_level_size(root
, btrfs_header_level(parent
) - 1));
587 static int balance_level(struct btrfs_trans_handle
*trans
, struct btrfs_root
588 *root
, struct btrfs_path
*path
, int level
)
590 struct extent_buffer
*right
= NULL
;
591 struct extent_buffer
*mid
;
592 struct extent_buffer
*left
= NULL
;
593 struct extent_buffer
*parent
= NULL
;
597 int orig_slot
= path
->slots
[level
];
598 int err_on_enospc
= 0;
604 mid
= path
->nodes
[level
];
605 orig_ptr
= btrfs_node_blockptr(mid
, orig_slot
);
607 if (level
< BTRFS_MAX_LEVEL
- 1)
608 parent
= path
->nodes
[level
+ 1];
609 pslot
= path
->slots
[level
+ 1];
612 * deal with the case where there is only one pointer in the root
613 * by promoting the node below to a root
616 struct extent_buffer
*child
;
618 if (btrfs_header_nritems(mid
) != 1)
621 /* promote the child to a root */
622 child
= read_node_slot(root
, mid
, 0);
625 path
->nodes
[level
] = NULL
;
626 clean_tree_block(trans
, root
, mid
);
627 wait_on_tree_block_writeback(root
, mid
);
628 /* once for the path */
629 free_extent_buffer(mid
);
630 ret
= btrfs_free_extent(trans
, root
, mid
->start
, mid
->len
, 1);
631 /* once for the root ptr */
632 free_extent_buffer(mid
);
635 if (btrfs_header_nritems(mid
) >
636 BTRFS_NODEPTRS_PER_BLOCK(root
) / 4)
639 if (btrfs_header_nritems(mid
) < 2)
642 left
= read_node_slot(root
, parent
, pslot
- 1);
644 wret
= btrfs_cow_block(trans
, root
, left
,
645 parent
, pslot
- 1, &left
);
651 right
= read_node_slot(root
, parent
, pslot
+ 1);
653 wret
= btrfs_cow_block(trans
, root
, right
,
654 parent
, pslot
+ 1, &right
);
661 /* first, try to make some room in the middle buffer */
663 orig_slot
+= btrfs_header_nritems(left
);
664 wret
= push_node_left(trans
, root
, left
, mid
);
667 if (btrfs_header_nritems(mid
) < 2)
672 * then try to empty the right most buffer into the middle
675 wret
= push_node_left(trans
, root
, mid
, right
);
676 if (wret
< 0 && wret
!= -ENOSPC
)
678 if (btrfs_header_nritems(right
) == 0) {
679 u64 bytenr
= right
->start
;
680 u32 blocksize
= right
->len
;
682 clean_tree_block(trans
, root
, right
);
683 wait_on_tree_block_writeback(root
, right
);
684 free_extent_buffer(right
);
686 wret
= del_ptr(trans
, root
, path
, level
+ 1, pslot
+
690 wret
= btrfs_free_extent(trans
, root
, bytenr
,
695 struct btrfs_disk_key right_key
;
696 btrfs_node_key(right
, &right_key
, 0);
697 btrfs_set_node_key(parent
, &right_key
, pslot
+ 1);
698 btrfs_mark_buffer_dirty(parent
);
701 if (btrfs_header_nritems(mid
) == 1) {
703 * we're not allowed to leave a node with one item in the
704 * tree during a delete. A deletion from lower in the tree
705 * could try to delete the only pointer in this node.
706 * So, pull some keys from the left.
707 * There has to be a left pointer at this point because
708 * otherwise we would have pulled some pointers from the
712 wret
= balance_node_right(trans
, root
, mid
, left
);
719 if (btrfs_header_nritems(mid
) == 0) {
720 /* we've managed to empty the middle node, drop it */
721 u64 bytenr
= mid
->start
;
722 u32 blocksize
= mid
->len
;
723 clean_tree_block(trans
, root
, mid
);
724 wait_on_tree_block_writeback(root
, mid
);
725 free_extent_buffer(mid
);
727 wret
= del_ptr(trans
, root
, path
, level
+ 1, pslot
);
730 wret
= btrfs_free_extent(trans
, root
, bytenr
, blocksize
, 1);
734 /* update the parent key to reflect our changes */
735 struct btrfs_disk_key mid_key
;
736 btrfs_node_key(mid
, &mid_key
, 0);
737 btrfs_set_node_key(parent
, &mid_key
, pslot
);
738 btrfs_mark_buffer_dirty(parent
);
741 /* update the path */
743 if (btrfs_header_nritems(left
) > orig_slot
) {
744 extent_buffer_get(left
);
745 path
->nodes
[level
] = left
;
746 path
->slots
[level
+ 1] -= 1;
747 path
->slots
[level
] = orig_slot
;
749 free_extent_buffer(mid
);
751 orig_slot
-= btrfs_header_nritems(left
);
752 path
->slots
[level
] = orig_slot
;
755 /* double check we haven't messed things up */
756 check_block(root
, path
, level
);
758 btrfs_node_blockptr(path
->nodes
[level
], path
->slots
[level
]))
762 free_extent_buffer(right
);
764 free_extent_buffer(left
);
768 /* returns zero if the push worked, non-zero otherwise */
769 static int push_nodes_for_insert(struct btrfs_trans_handle
*trans
,
770 struct btrfs_root
*root
,
771 struct btrfs_path
*path
, int level
)
773 struct extent_buffer
*right
= NULL
;
774 struct extent_buffer
*mid
;
775 struct extent_buffer
*left
= NULL
;
776 struct extent_buffer
*parent
= NULL
;
780 int orig_slot
= path
->slots
[level
];
786 mid
= path
->nodes
[level
];
787 orig_ptr
= btrfs_node_blockptr(mid
, orig_slot
);
789 if (level
< BTRFS_MAX_LEVEL
- 1)
790 parent
= path
->nodes
[level
+ 1];
791 pslot
= path
->slots
[level
+ 1];
796 left
= read_node_slot(root
, parent
, pslot
- 1);
798 /* first, try to make some room in the middle buffer */
801 left_nr
= btrfs_header_nritems(left
);
802 if (left_nr
>= BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
805 ret
= btrfs_cow_block(trans
, root
, left
, parent
,
810 wret
= push_node_left(trans
, root
,
817 struct btrfs_disk_key disk_key
;
818 orig_slot
+= left_nr
;
819 btrfs_node_key(mid
, &disk_key
, 0);
820 btrfs_set_node_key(parent
, &disk_key
, pslot
);
821 btrfs_mark_buffer_dirty(parent
);
822 if (btrfs_header_nritems(left
) > orig_slot
) {
823 path
->nodes
[level
] = left
;
824 path
->slots
[level
+ 1] -= 1;
825 path
->slots
[level
] = orig_slot
;
826 free_extent_buffer(mid
);
829 btrfs_header_nritems(left
);
830 path
->slots
[level
] = orig_slot
;
831 free_extent_buffer(left
);
835 free_extent_buffer(left
);
837 right
= read_node_slot(root
, parent
, pslot
+ 1);
840 * then try to empty the right most buffer into the middle
844 right_nr
= btrfs_header_nritems(right
);
845 if (right_nr
>= BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
848 ret
= btrfs_cow_block(trans
, root
, right
,
854 wret
= balance_node_right(trans
, root
,
861 struct btrfs_disk_key disk_key
;
863 btrfs_node_key(right
, &disk_key
, 0);
864 btrfs_set_node_key(parent
, &disk_key
, pslot
+ 1);
865 btrfs_mark_buffer_dirty(parent
);
867 if (btrfs_header_nritems(mid
) <= orig_slot
) {
868 path
->nodes
[level
] = right
;
869 path
->slots
[level
+ 1] += 1;
870 path
->slots
[level
] = orig_slot
-
871 btrfs_header_nritems(mid
);
872 free_extent_buffer(mid
);
874 free_extent_buffer(right
);
878 free_extent_buffer(right
);
884 * readahead one full node of leaves
886 static void reada_for_search(struct btrfs_root
*root
, struct btrfs_path
*path
,
889 struct extent_buffer
*node
;
895 int direction
= path
->reada
;
896 struct extent_buffer
*eb
;
904 if (!path
->nodes
[level
])
907 node
= path
->nodes
[level
];
908 search
= btrfs_node_blockptr(node
, slot
);
909 blocksize
= btrfs_level_size(root
, level
- 1);
910 eb
= btrfs_find_tree_block(root
, search
, blocksize
);
912 free_extent_buffer(eb
);
916 highest_read
= search
;
917 lowest_read
= search
;
919 nritems
= btrfs_header_nritems(node
);
926 } else if (direction
> 0) {
931 search
= btrfs_node_blockptr(node
, nr
);
932 if ((search
>= lowest_read
&& search
<= highest_read
) ||
933 (search
< lowest_read
&& lowest_read
- search
<= 32768) ||
934 (search
> highest_read
&& search
- highest_read
<= 32768)) {
935 readahead_tree_block(root
, search
, blocksize
);
939 if (path
->reada
< 2 && (nread
> (256 * 1024) || nscan
> 32))
941 if(nread
> (1024 * 1024) || nscan
> 128)
944 if (search
< lowest_read
)
945 lowest_read
= search
;
946 if (search
> highest_read
)
947 highest_read
= search
;
951 * look for key in the tree. path is filled in with nodes along the way
952 * if key is found, we return zero and you can find the item in the leaf
953 * level of the path (level 0)
955 * If the key isn't found, the path points to the slot where it should
956 * be inserted, and 1 is returned. If there are other errors during the
957 * search a negative error number is returned.
959 * if ins_len > 0, nodes and leaves will be split as we walk down the
960 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
963 int btrfs_search_slot(struct btrfs_trans_handle
*trans
, struct btrfs_root
964 *root
, struct btrfs_key
*key
, struct btrfs_path
*p
, int
967 struct extent_buffer
*b
;
972 int should_reada
= p
->reada
;
975 lowest_level
= p
->lowest_level
;
976 WARN_ON(lowest_level
&& ins_len
);
977 WARN_ON(p
->nodes
[0] != NULL
);
978 WARN_ON(!mutex_is_locked(&root
->fs_info
->fs_mutex
));
981 extent_buffer_get(b
);
983 level
= btrfs_header_level(b
);
986 wret
= btrfs_cow_block(trans
, root
, b
,
991 free_extent_buffer(b
);
995 BUG_ON(!cow
&& ins_len
);
996 if (level
!= btrfs_header_level(b
))
998 level
= btrfs_header_level(b
);
1000 ret
= check_block(root
, p
, level
);
1003 ret
= bin_search(b
, key
, level
, &slot
);
1005 if (ret
&& slot
> 0)
1007 p
->slots
[level
] = slot
;
1008 if (ins_len
> 0 && btrfs_header_nritems(b
) >=
1009 BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
1010 int sret
= split_node(trans
, root
, p
, level
);
1014 b
= p
->nodes
[level
];
1015 slot
= p
->slots
[level
];
1016 } else if (ins_len
< 0) {
1017 int sret
= balance_level(trans
, root
, p
,
1021 b
= p
->nodes
[level
];
1023 btrfs_release_path(NULL
, p
);
1026 slot
= p
->slots
[level
];
1027 BUG_ON(btrfs_header_nritems(b
) == 1);
1029 /* this is only true while dropping a snapshot */
1030 if (level
== lowest_level
)
1032 bytenr
= btrfs_node_blockptr(b
, slot
);
1034 reada_for_search(root
, p
, level
, slot
);
1035 b
= read_tree_block(root
, bytenr
,
1036 btrfs_level_size(root
, level
- 1));
1038 p
->slots
[level
] = slot
;
1039 if (ins_len
> 0 && btrfs_leaf_free_space(root
, b
) <
1040 sizeof(struct btrfs_item
) + ins_len
) {
1041 int sret
= split_leaf(trans
, root
, key
,
1054 * adjust the pointers going up the tree, starting at level
1055 * making sure the right key of each node is points to 'key'.
1056 * This is used after shifting pointers to the left, so it stops
1057 * fixing up pointers when a given leaf/node is not in slot 0 of the
1060 * If this fails to write a tree block, it returns -1, but continues
1061 * fixing up the blocks in ram so the tree is consistent.
1063 static int fixup_low_keys(struct btrfs_trans_handle
*trans
,
1064 struct btrfs_root
*root
, struct btrfs_path
*path
,
1065 struct btrfs_disk_key
*key
, int level
)
1069 struct extent_buffer
*t
;
1071 for (i
= level
; i
< BTRFS_MAX_LEVEL
; i
++) {
1072 int tslot
= path
->slots
[i
];
1073 if (!path
->nodes
[i
])
1076 btrfs_set_node_key(t
, key
, tslot
);
1077 btrfs_mark_buffer_dirty(path
->nodes
[i
]);
1085 * try to push data from one node into the next node left in the
1088 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1089 * error, and > 0 if there was no room in the left hand block.
1091 static int push_node_left(struct btrfs_trans_handle
*trans
, struct btrfs_root
1092 *root
, struct extent_buffer
*dst
,
1093 struct extent_buffer
*src
)
1100 src_nritems
= btrfs_header_nritems(src
);
1101 dst_nritems
= btrfs_header_nritems(dst
);
1102 push_items
= BTRFS_NODEPTRS_PER_BLOCK(root
) - dst_nritems
;
1104 if (push_items
<= 0) {
1108 if (src_nritems
< push_items
)
1109 push_items
= src_nritems
;
1111 copy_extent_buffer(dst
, src
,
1112 btrfs_node_key_ptr_offset(dst_nritems
),
1113 btrfs_node_key_ptr_offset(0),
1114 push_items
* sizeof(struct btrfs_key_ptr
));
1116 if (push_items
< src_nritems
) {
1117 memmove_extent_buffer(src
, btrfs_node_key_ptr_offset(0),
1118 btrfs_node_key_ptr_offset(push_items
),
1119 (src_nritems
- push_items
) *
1120 sizeof(struct btrfs_key_ptr
));
1122 btrfs_set_header_nritems(src
, src_nritems
- push_items
);
1123 btrfs_set_header_nritems(dst
, dst_nritems
+ push_items
);
1124 btrfs_mark_buffer_dirty(src
);
1125 btrfs_mark_buffer_dirty(dst
);
1130 * try to push data from one node into the next node right in the
1133 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1134 * error, and > 0 if there was no room in the right hand block.
1136 * this will only push up to 1/2 the contents of the left node over
1138 static int balance_node_right(struct btrfs_trans_handle
*trans
,
1139 struct btrfs_root
*root
,
1140 struct extent_buffer
*dst
,
1141 struct extent_buffer
*src
)
1149 src_nritems
= btrfs_header_nritems(src
);
1150 dst_nritems
= btrfs_header_nritems(dst
);
1151 push_items
= BTRFS_NODEPTRS_PER_BLOCK(root
) - dst_nritems
;
1152 if (push_items
<= 0)
1155 max_push
= src_nritems
/ 2 + 1;
1156 /* don't try to empty the node */
1157 if (max_push
>= src_nritems
)
1160 if (max_push
< push_items
)
1161 push_items
= max_push
;
1163 memmove_extent_buffer(dst
, btrfs_node_key_ptr_offset(push_items
),
1164 btrfs_node_key_ptr_offset(0),
1166 sizeof(struct btrfs_key_ptr
));
1168 copy_extent_buffer(dst
, src
,
1169 btrfs_node_key_ptr_offset(0),
1170 btrfs_node_key_ptr_offset(src_nritems
- push_items
),
1171 push_items
* sizeof(struct btrfs_key_ptr
));
1173 btrfs_set_header_nritems(src
, src_nritems
- push_items
);
1174 btrfs_set_header_nritems(dst
, dst_nritems
+ push_items
);
1176 btrfs_mark_buffer_dirty(src
);
1177 btrfs_mark_buffer_dirty(dst
);
1182 * helper function to insert a new root level in the tree.
1183 * A new node is allocated, and a single item is inserted to
1184 * point to the existing root
1186 * returns zero on success or < 0 on failure.
1188 static int insert_new_root(struct btrfs_trans_handle
*trans
,
1189 struct btrfs_root
*root
,
1190 struct btrfs_path
*path
, int level
)
1192 struct extent_buffer
*lower
;
1193 struct extent_buffer
*c
;
1194 struct btrfs_disk_key lower_key
;
1196 BUG_ON(path
->nodes
[level
]);
1197 BUG_ON(path
->nodes
[level
-1] != root
->node
);
1199 c
= btrfs_alloc_free_block(trans
, root
, root
->nodesize
,
1200 root
->node
->start
, 0);
1203 memset_extent_buffer(c
, 0, 0, root
->nodesize
);
1204 btrfs_set_header_nritems(c
, 1);
1205 btrfs_set_header_level(c
, level
);
1206 btrfs_set_header_bytenr(c
, c
->start
);
1207 btrfs_set_header_generation(c
, trans
->transid
);
1208 btrfs_set_header_owner(c
, root
->root_key
.objectid
);
1209 lower
= path
->nodes
[level
-1];
1211 write_extent_buffer(c
, root
->fs_info
->fsid
,
1212 (unsigned long)btrfs_header_fsid(c
),
1215 btrfs_item_key(lower
, &lower_key
, 0);
1217 btrfs_node_key(lower
, &lower_key
, 0);
1218 btrfs_set_node_key(c
, &lower_key
, 0);
1219 btrfs_set_node_blockptr(c
, 0, lower
->start
);
1221 btrfs_mark_buffer_dirty(c
);
1223 /* the super has an extra ref to root->node */
1224 free_extent_buffer(root
->node
);
1226 extent_buffer_get(c
);
1227 path
->nodes
[level
] = c
;
1228 path
->slots
[level
] = 0;
1233 * worker function to insert a single pointer in a node.
1234 * the node should have enough room for the pointer already
1236 * slot and level indicate where you want the key to go, and
1237 * blocknr is the block the key points to.
1239 * returns zero on success and < 0 on any error
1241 static int insert_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
1242 *root
, struct btrfs_path
*path
, struct btrfs_disk_key
1243 *key
, u64 bytenr
, int slot
, int level
)
1245 struct extent_buffer
*lower
;
1248 BUG_ON(!path
->nodes
[level
]);
1249 lower
= path
->nodes
[level
];
1250 nritems
= btrfs_header_nritems(lower
);
1253 if (nritems
== BTRFS_NODEPTRS_PER_BLOCK(root
))
1255 if (slot
!= nritems
) {
1256 memmove_extent_buffer(lower
,
1257 btrfs_node_key_ptr_offset(slot
+ 1),
1258 btrfs_node_key_ptr_offset(slot
),
1259 (nritems
- slot
) * sizeof(struct btrfs_key_ptr
));
1261 btrfs_set_node_key(lower
, key
, slot
);
1262 btrfs_set_node_blockptr(lower
, slot
, bytenr
);
1263 btrfs_set_header_nritems(lower
, nritems
+ 1);
1264 btrfs_mark_buffer_dirty(lower
);
1269 * split the node at the specified level in path in two.
1270 * The path is corrected to point to the appropriate node after the split
1272 * Before splitting this tries to make some room in the node by pushing
1273 * left and right, if either one works, it returns right away.
1275 * returns 0 on success and < 0 on failure
1277 static int split_node(struct btrfs_trans_handle
*trans
, struct btrfs_root
1278 *root
, struct btrfs_path
*path
, int level
)
1280 struct extent_buffer
*c
;
1281 struct extent_buffer
*split
;
1282 struct btrfs_disk_key disk_key
;
1288 c
= path
->nodes
[level
];
1289 if (c
== root
->node
) {
1290 /* trying to split the root, lets make a new one */
1291 ret
= insert_new_root(trans
, root
, path
, level
+ 1);
1295 ret
= push_nodes_for_insert(trans
, root
, path
, level
);
1296 c
= path
->nodes
[level
];
1297 if (!ret
&& btrfs_header_nritems(c
) <
1298 BTRFS_NODEPTRS_PER_BLOCK(root
) - 1)
1304 c_nritems
= btrfs_header_nritems(c
);
1305 split
= btrfs_alloc_free_block(trans
, root
, root
->nodesize
,
1308 return PTR_ERR(split
);
1310 btrfs_set_header_flags(split
, btrfs_header_flags(c
));
1311 btrfs_set_header_level(split
, btrfs_header_level(c
));
1312 btrfs_set_header_bytenr(split
, split
->start
);
1313 btrfs_set_header_generation(split
, trans
->transid
);
1314 btrfs_set_header_owner(split
, root
->root_key
.objectid
);
1315 write_extent_buffer(split
, root
->fs_info
->fsid
,
1316 (unsigned long)btrfs_header_fsid(split
),
1319 mid
= (c_nritems
+ 1) / 2;
1321 copy_extent_buffer(split
, c
,
1322 btrfs_node_key_ptr_offset(0),
1323 btrfs_node_key_ptr_offset(mid
),
1324 (c_nritems
- mid
) * sizeof(struct btrfs_key_ptr
));
1325 btrfs_set_header_nritems(split
, c_nritems
- mid
);
1326 btrfs_set_header_nritems(c
, mid
);
1329 btrfs_mark_buffer_dirty(c
);
1330 btrfs_mark_buffer_dirty(split
);
1332 btrfs_node_key(split
, &disk_key
, 0);
1333 wret
= insert_ptr(trans
, root
, path
, &disk_key
, split
->start
,
1334 path
->slots
[level
+ 1] + 1,
1339 if (path
->slots
[level
] >= mid
) {
1340 path
->slots
[level
] -= mid
;
1341 free_extent_buffer(c
);
1342 path
->nodes
[level
] = split
;
1343 path
->slots
[level
+ 1] += 1;
1345 free_extent_buffer(split
);
1351 * how many bytes are required to store the items in a leaf. start
1352 * and nr indicate which items in the leaf to check. This totals up the
1353 * space used both by the item structs and the item data
1355 static int leaf_space_used(struct extent_buffer
*l
, int start
, int nr
)
1358 int nritems
= btrfs_header_nritems(l
);
1359 int end
= min(nritems
, start
+ nr
) - 1;
1363 data_len
= btrfs_item_end_nr(l
, start
);
1364 data_len
= data_len
- btrfs_item_offset_nr(l
, end
);
1365 data_len
+= sizeof(struct btrfs_item
) * nr
;
1366 WARN_ON(data_len
< 0);
1371 * The space between the end of the leaf items and
1372 * the start of the leaf data. IOW, how much room
1373 * the leaf has left for both items and data
1375 int btrfs_leaf_free_space(struct btrfs_root
*root
, struct extent_buffer
*leaf
)
1377 int nritems
= btrfs_header_nritems(leaf
);
1379 ret
= BTRFS_LEAF_DATA_SIZE(root
) - leaf_space_used(leaf
, 0, nritems
);
1381 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1382 ret
, BTRFS_LEAF_DATA_SIZE(root
),
1383 leaf_space_used(leaf
, 0, nritems
), nritems
);
1389 * push some data in the path leaf to the right, trying to free up at
1390 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1392 * returns 1 if the push failed because the other node didn't have enough
1393 * room, 0 if everything worked out and < 0 if there were major errors.
1395 static int push_leaf_right(struct btrfs_trans_handle
*trans
, struct btrfs_root
1396 *root
, struct btrfs_path
*path
, int data_size
)
1398 struct extent_buffer
*left
= path
->nodes
[0];
1399 struct extent_buffer
*right
;
1400 struct extent_buffer
*upper
;
1401 struct btrfs_disk_key disk_key
;
1407 struct btrfs_item
*item
;
1414 slot
= path
->slots
[1];
1415 if (!path
->nodes
[1]) {
1418 upper
= path
->nodes
[1];
1419 if (slot
>= btrfs_header_nritems(upper
) - 1)
1422 right
= read_tree_block(root
, btrfs_node_blockptr(upper
, slot
+ 1),
1424 free_space
= btrfs_leaf_free_space(root
, right
);
1425 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1426 free_extent_buffer(right
);
1430 /* cow and double check */
1431 ret
= btrfs_cow_block(trans
, root
, right
, upper
,
1434 free_extent_buffer(right
);
1437 free_space
= btrfs_leaf_free_space(root
, right
);
1438 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1439 free_extent_buffer(right
);
1443 left_nritems
= btrfs_header_nritems(left
);
1444 if (left_nritems
== 0) {
1445 free_extent_buffer(right
);
1449 for (i
= left_nritems
- 1; i
>= 1; i
--) {
1450 item
= btrfs_item_nr(left
, i
);
1452 if (path
->slots
[0] == i
)
1453 push_space
+= data_size
+ sizeof(*item
);
1455 if (!left
->map_token
) {
1456 map_extent_buffer(left
, (unsigned long)item
,
1457 sizeof(struct btrfs_item
),
1458 &left
->map_token
, &left
->kaddr
,
1459 &left
->map_start
, &left
->map_len
,
1463 this_item_size
= btrfs_item_size(left
, item
);
1464 if (this_item_size
+ sizeof(*item
) + push_space
> free_space
)
1467 push_space
+= this_item_size
+ sizeof(*item
);
1469 if (left
->map_token
) {
1470 unmap_extent_buffer(left
, left
->map_token
, KM_USER1
);
1471 left
->map_token
= NULL
;
1474 if (push_items
== 0) {
1475 free_extent_buffer(right
);
1479 if (push_items
== left_nritems
)
1482 /* push left to right */
1483 right_nritems
= btrfs_header_nritems(right
);
1484 push_space
= btrfs_item_end_nr(left
, left_nritems
- push_items
);
1485 push_space
-= leaf_data_end(root
, left
);
1487 /* make room in the right data area */
1488 data_end
= leaf_data_end(root
, right
);
1489 memmove_extent_buffer(right
,
1490 btrfs_leaf_data(right
) + data_end
- push_space
,
1491 btrfs_leaf_data(right
) + data_end
,
1492 BTRFS_LEAF_DATA_SIZE(root
) - data_end
);
1494 /* copy from the left data area */
1495 copy_extent_buffer(right
, left
, btrfs_leaf_data(right
) +
1496 BTRFS_LEAF_DATA_SIZE(root
) - push_space
,
1497 btrfs_leaf_data(left
) + leaf_data_end(root
, left
),
1500 memmove_extent_buffer(right
, btrfs_item_nr_offset(push_items
),
1501 btrfs_item_nr_offset(0),
1502 right_nritems
* sizeof(struct btrfs_item
));
1504 /* copy the items from left to right */
1505 copy_extent_buffer(right
, left
, btrfs_item_nr_offset(0),
1506 btrfs_item_nr_offset(left_nritems
- push_items
),
1507 push_items
* sizeof(struct btrfs_item
));
1509 /* update the item pointers */
1510 right_nritems
+= push_items
;
1511 btrfs_set_header_nritems(right
, right_nritems
);
1512 push_space
= BTRFS_LEAF_DATA_SIZE(root
);
1514 for (i
= 0; i
< right_nritems
; i
++) {
1515 item
= btrfs_item_nr(right
, i
);
1516 if (!right
->map_token
) {
1517 map_extent_buffer(right
, (unsigned long)item
,
1518 sizeof(struct btrfs_item
),
1519 &right
->map_token
, &right
->kaddr
,
1520 &right
->map_start
, &right
->map_len
,
1523 push_space
-= btrfs_item_size(right
, item
);
1524 btrfs_set_item_offset(right
, item
, push_space
);
1527 if (right
->map_token
) {
1528 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
1529 right
->map_token
= NULL
;
1531 left_nritems
-= push_items
;
1532 btrfs_set_header_nritems(left
, left_nritems
);
1534 btrfs_mark_buffer_dirty(left
);
1535 btrfs_mark_buffer_dirty(right
);
1537 btrfs_item_key(right
, &disk_key
, 0);
1538 btrfs_set_node_key(upper
, &disk_key
, slot
+ 1);
1539 btrfs_mark_buffer_dirty(upper
);
1541 /* then fixup the leaf pointer in the path */
1542 if (path
->slots
[0] >= left_nritems
) {
1543 path
->slots
[0] -= left_nritems
;
1544 free_extent_buffer(path
->nodes
[0]);
1545 path
->nodes
[0] = right
;
1546 path
->slots
[1] += 1;
1548 free_extent_buffer(right
);
1553 * push some data in the path leaf to the left, trying to free up at
1554 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1556 static int push_leaf_left(struct btrfs_trans_handle
*trans
, struct btrfs_root
1557 *root
, struct btrfs_path
*path
, int data_size
)
1559 struct btrfs_disk_key disk_key
;
1560 struct extent_buffer
*right
= path
->nodes
[0];
1561 struct extent_buffer
*left
;
1567 struct btrfs_item
*item
;
1568 u32 old_left_nritems
;
1573 u32 old_left_item_size
;
1575 slot
= path
->slots
[1];
1578 if (!path
->nodes
[1])
1581 left
= read_tree_block(root
, btrfs_node_blockptr(path
->nodes
[1],
1582 slot
- 1), root
->leafsize
);
1583 free_space
= btrfs_leaf_free_space(root
, left
);
1584 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1585 free_extent_buffer(left
);
1589 /* cow and double check */
1590 ret
= btrfs_cow_block(trans
, root
, left
,
1591 path
->nodes
[1], slot
- 1, &left
);
1593 /* we hit -ENOSPC, but it isn't fatal here */
1594 free_extent_buffer(left
);
1597 free_space
= btrfs_leaf_free_space(root
, left
);
1598 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1599 free_extent_buffer(left
);
1603 right_nritems
= btrfs_header_nritems(right
);
1604 if (right_nritems
== 0) {
1605 free_extent_buffer(left
);
1609 for (i
= 0; i
< right_nritems
- 1; i
++) {
1610 item
= btrfs_item_nr(right
, i
);
1611 if (!right
->map_token
) {
1612 map_extent_buffer(right
, (unsigned long)item
,
1613 sizeof(struct btrfs_item
),
1614 &right
->map_token
, &right
->kaddr
,
1615 &right
->map_start
, &right
->map_len
,
1619 if (path
->slots
[0] == i
)
1620 push_space
+= data_size
+ sizeof(*item
);
1622 this_item_size
= btrfs_item_size(right
, item
);
1623 if (this_item_size
+ sizeof(*item
) + push_space
> free_space
)
1627 push_space
+= this_item_size
+ sizeof(*item
);
1630 if (right
->map_token
) {
1631 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
1632 right
->map_token
= NULL
;
1635 if (push_items
== 0) {
1636 free_extent_buffer(left
);
1639 if (push_items
== btrfs_header_nritems(right
))
1642 /* push data from right to left */
1643 copy_extent_buffer(left
, right
,
1644 btrfs_item_nr_offset(btrfs_header_nritems(left
)),
1645 btrfs_item_nr_offset(0),
1646 push_items
* sizeof(struct btrfs_item
));
1648 push_space
= BTRFS_LEAF_DATA_SIZE(root
) -
1649 btrfs_item_offset_nr(right
, push_items
-1);
1651 copy_extent_buffer(left
, right
, btrfs_leaf_data(left
) +
1652 leaf_data_end(root
, left
) - push_space
,
1653 btrfs_leaf_data(right
) +
1654 btrfs_item_offset_nr(right
, push_items
- 1),
1656 old_left_nritems
= btrfs_header_nritems(left
);
1657 BUG_ON(old_left_nritems
< 0);
1659 old_left_item_size
= btrfs_item_offset_nr(left
, old_left_nritems
- 1);
1660 for (i
= old_left_nritems
; i
< old_left_nritems
+ push_items
; i
++) {
1663 item
= btrfs_item_nr(left
, i
);
1664 if (!left
->map_token
) {
1665 map_extent_buffer(left
, (unsigned long)item
,
1666 sizeof(struct btrfs_item
),
1667 &left
->map_token
, &left
->kaddr
,
1668 &left
->map_start
, &left
->map_len
,
1672 ioff
= btrfs_item_offset(left
, item
);
1673 btrfs_set_item_offset(left
, item
,
1674 ioff
- (BTRFS_LEAF_DATA_SIZE(root
) - old_left_item_size
));
1676 btrfs_set_header_nritems(left
, old_left_nritems
+ push_items
);
1677 if (left
->map_token
) {
1678 unmap_extent_buffer(left
, left
->map_token
, KM_USER1
);
1679 left
->map_token
= NULL
;
1682 /* fixup right node */
1683 push_space
= btrfs_item_offset_nr(right
, push_items
- 1) -
1684 leaf_data_end(root
, right
);
1685 memmove_extent_buffer(right
, btrfs_leaf_data(right
) +
1686 BTRFS_LEAF_DATA_SIZE(root
) - push_space
,
1687 btrfs_leaf_data(right
) +
1688 leaf_data_end(root
, right
), push_space
);
1690 memmove_extent_buffer(right
, btrfs_item_nr_offset(0),
1691 btrfs_item_nr_offset(push_items
),
1692 (btrfs_header_nritems(right
) - push_items
) *
1693 sizeof(struct btrfs_item
));
1695 right_nritems
= btrfs_header_nritems(right
) - push_items
;
1696 btrfs_set_header_nritems(right
, right_nritems
);
1697 push_space
= BTRFS_LEAF_DATA_SIZE(root
);
1699 for (i
= 0; i
< right_nritems
; i
++) {
1700 item
= btrfs_item_nr(right
, i
);
1702 if (!right
->map_token
) {
1703 map_extent_buffer(right
, (unsigned long)item
,
1704 sizeof(struct btrfs_item
),
1705 &right
->map_token
, &right
->kaddr
,
1706 &right
->map_start
, &right
->map_len
,
1710 push_space
= push_space
- btrfs_item_size(right
, item
);
1711 btrfs_set_item_offset(right
, item
, push_space
);
1713 if (right
->map_token
) {
1714 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
1715 right
->map_token
= NULL
;
1718 btrfs_mark_buffer_dirty(left
);
1719 btrfs_mark_buffer_dirty(right
);
1721 btrfs_item_key(right
, &disk_key
, 0);
1722 wret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
1726 /* then fixup the leaf pointer in the path */
1727 if (path
->slots
[0] < push_items
) {
1728 path
->slots
[0] += old_left_nritems
;
1729 free_extent_buffer(path
->nodes
[0]);
1730 path
->nodes
[0] = left
;
1731 path
->slots
[1] -= 1;
1733 free_extent_buffer(left
);
1734 path
->slots
[0] -= push_items
;
1736 BUG_ON(path
->slots
[0] < 0);
1741 * split the path's leaf in two, making sure there is at least data_size
1742 * available for the resulting leaf level of the path.
1744 * returns 0 if all went well and < 0 on failure.
1746 static int split_leaf(struct btrfs_trans_handle
*trans
, struct btrfs_root
1747 *root
, struct btrfs_key
*ins_key
,
1748 struct btrfs_path
*path
, int data_size
)
1750 struct extent_buffer
*l
;
1754 struct extent_buffer
*right
;
1755 int space_needed
= data_size
+ sizeof(struct btrfs_item
);
1761 int double_split
= 0;
1762 struct btrfs_disk_key disk_key
;
1764 /* first try to make some room by pushing left and right */
1765 wret
= push_leaf_left(trans
, root
, path
, data_size
);
1770 wret
= push_leaf_right(trans
, root
, path
, data_size
);
1776 /* did the pushes work? */
1777 if (btrfs_leaf_free_space(root
, l
) >=
1778 sizeof(struct btrfs_item
) + data_size
) {
1782 if (!path
->nodes
[1]) {
1783 ret
= insert_new_root(trans
, root
, path
, 1);
1787 slot
= path
->slots
[0];
1788 nritems
= btrfs_header_nritems(l
);
1789 mid
= (nritems
+ 1)/ 2;
1791 right
= btrfs_alloc_free_block(trans
, root
, root
->leafsize
,
1794 return PTR_ERR(right
);
1796 memset_extent_buffer(right
, 0, 0, sizeof(struct btrfs_header
));
1797 btrfs_set_header_bytenr(right
, right
->start
);
1798 btrfs_set_header_generation(right
, trans
->transid
);
1799 btrfs_set_header_owner(right
, root
->root_key
.objectid
);
1800 btrfs_set_header_level(right
, 0);
1801 write_extent_buffer(right
, root
->fs_info
->fsid
,
1802 (unsigned long)btrfs_header_fsid(right
),
1807 leaf_space_used(l
, mid
, nritems
- mid
) + space_needed
>
1808 BTRFS_LEAF_DATA_SIZE(root
)) {
1809 if (slot
>= nritems
) {
1810 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
1811 btrfs_set_header_nritems(right
, 0);
1812 wret
= insert_ptr(trans
, root
, path
,
1813 &disk_key
, right
->start
,
1814 path
->slots
[1] + 1, 1);
1817 free_extent_buffer(path
->nodes
[0]);
1818 path
->nodes
[0] = right
;
1820 path
->slots
[1] += 1;
1824 if (mid
!= nritems
&&
1825 leaf_space_used(l
, mid
, nritems
- mid
) +
1826 space_needed
> BTRFS_LEAF_DATA_SIZE(root
)) {
1831 if (leaf_space_used(l
, 0, mid
+ 1) + space_needed
>
1832 BTRFS_LEAF_DATA_SIZE(root
)) {
1834 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
1835 btrfs_set_header_nritems(right
, 0);
1836 wret
= insert_ptr(trans
, root
, path
,
1842 free_extent_buffer(path
->nodes
[0]);
1843 path
->nodes
[0] = right
;
1845 if (path
->slots
[1] == 0) {
1846 wret
= fixup_low_keys(trans
, root
,
1847 path
, &disk_key
, 1);
1857 nritems
= nritems
- mid
;
1858 btrfs_set_header_nritems(right
, nritems
);
1859 data_copy_size
= btrfs_item_end_nr(l
, mid
) - leaf_data_end(root
, l
);
1861 copy_extent_buffer(right
, l
, btrfs_item_nr_offset(0),
1862 btrfs_item_nr_offset(mid
),
1863 nritems
* sizeof(struct btrfs_item
));
1865 copy_extent_buffer(right
, l
,
1866 btrfs_leaf_data(right
) + BTRFS_LEAF_DATA_SIZE(root
) -
1867 data_copy_size
, btrfs_leaf_data(l
) +
1868 leaf_data_end(root
, l
), data_copy_size
);
1870 rt_data_off
= BTRFS_LEAF_DATA_SIZE(root
) -
1871 btrfs_item_end_nr(l
, mid
);
1873 for (i
= 0; i
< nritems
; i
++) {
1874 struct btrfs_item
*item
= btrfs_item_nr(right
, i
);
1877 if (!right
->map_token
) {
1878 map_extent_buffer(right
, (unsigned long)item
,
1879 sizeof(struct btrfs_item
),
1880 &right
->map_token
, &right
->kaddr
,
1881 &right
->map_start
, &right
->map_len
,
1885 ioff
= btrfs_item_offset(right
, item
);
1886 btrfs_set_item_offset(right
, item
, ioff
+ rt_data_off
);
1889 if (right
->map_token
) {
1890 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
1891 right
->map_token
= NULL
;
1894 btrfs_set_header_nritems(l
, mid
);
1896 btrfs_item_key(right
, &disk_key
, 0);
1897 wret
= insert_ptr(trans
, root
, path
, &disk_key
, right
->start
,
1898 path
->slots
[1] + 1, 1);
1902 btrfs_mark_buffer_dirty(right
);
1903 btrfs_mark_buffer_dirty(l
);
1904 BUG_ON(path
->slots
[0] != slot
);
1907 free_extent_buffer(path
->nodes
[0]);
1908 path
->nodes
[0] = right
;
1909 path
->slots
[0] -= mid
;
1910 path
->slots
[1] += 1;
1912 free_extent_buffer(right
);
1914 BUG_ON(path
->slots
[0] < 0);
1916 if (!double_split
) {
1920 right
= btrfs_alloc_free_block(trans
, root
, root
->leafsize
,
1923 return PTR_ERR(right
);
1925 memset_extent_buffer(right
, 0, 0, sizeof(struct btrfs_header
));
1926 btrfs_set_header_bytenr(right
, right
->start
);
1927 btrfs_set_header_generation(right
, trans
->transid
);
1928 btrfs_set_header_owner(right
, root
->root_key
.objectid
);
1929 btrfs_set_header_level(right
, 0);
1930 write_extent_buffer(right
, root
->fs_info
->fsid
,
1931 (unsigned long)btrfs_header_fsid(right
),
1934 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
1935 btrfs_set_header_nritems(right
, 0);
1936 wret
= insert_ptr(trans
, root
, path
,
1937 &disk_key
, right
->start
,
1941 if (path
->slots
[1] == 0) {
1942 wret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
1946 free_extent_buffer(path
->nodes
[0]);
1947 path
->nodes
[0] = right
;
1952 int btrfs_truncate_item(struct btrfs_trans_handle
*trans
,
1953 struct btrfs_root
*root
,
1954 struct btrfs_path
*path
,
1960 struct extent_buffer
*leaf
;
1961 struct btrfs_item
*item
;
1963 unsigned int data_end
;
1964 unsigned int old_data_start
;
1965 unsigned int old_size
;
1966 unsigned int size_diff
;
1969 slot_orig
= path
->slots
[0];
1970 leaf
= path
->nodes
[0];
1972 nritems
= btrfs_header_nritems(leaf
);
1973 data_end
= leaf_data_end(root
, leaf
);
1975 slot
= path
->slots
[0];
1976 old_data_start
= btrfs_item_offset_nr(leaf
, slot
);
1977 old_size
= btrfs_item_size_nr(leaf
, slot
);
1978 BUG_ON(old_size
<= new_size
);
1979 size_diff
= old_size
- new_size
;
1982 BUG_ON(slot
>= nritems
);
1985 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1987 /* first correct the data pointers */
1988 for (i
= slot
; i
< nritems
; i
++) {
1990 item
= btrfs_item_nr(leaf
, i
);
1992 if (!leaf
->map_token
) {
1993 map_extent_buffer(leaf
, (unsigned long)item
,
1994 sizeof(struct btrfs_item
),
1995 &leaf
->map_token
, &leaf
->kaddr
,
1996 &leaf
->map_start
, &leaf
->map_len
,
2000 ioff
= btrfs_item_offset(leaf
, item
);
2001 btrfs_set_item_offset(leaf
, item
, ioff
+ size_diff
);
2004 if (leaf
->map_token
) {
2005 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
2006 leaf
->map_token
= NULL
;
2009 /* shift the data */
2010 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2011 data_end
+ size_diff
, btrfs_leaf_data(leaf
) +
2012 data_end
, old_data_start
+ new_size
- data_end
);
2014 item
= btrfs_item_nr(leaf
, slot
);
2015 btrfs_set_item_size(leaf
, item
, new_size
);
2016 btrfs_mark_buffer_dirty(leaf
);
2019 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
2020 btrfs_print_leaf(root
, leaf
);
2026 int btrfs_extend_item(struct btrfs_trans_handle
*trans
,
2027 struct btrfs_root
*root
, struct btrfs_path
*path
,
2033 struct extent_buffer
*leaf
;
2034 struct btrfs_item
*item
;
2036 unsigned int data_end
;
2037 unsigned int old_data
;
2038 unsigned int old_size
;
2041 slot_orig
= path
->slots
[0];
2042 leaf
= path
->nodes
[0];
2044 nritems
= btrfs_header_nritems(leaf
);
2045 data_end
= leaf_data_end(root
, leaf
);
2047 if (btrfs_leaf_free_space(root
, leaf
) < data_size
) {
2048 btrfs_print_leaf(root
, leaf
);
2051 slot
= path
->slots
[0];
2052 old_data
= btrfs_item_end_nr(leaf
, slot
);
2055 if (slot
>= nritems
) {
2056 btrfs_print_leaf(root
, leaf
);
2057 printk("slot %d too large, nritems %d\n", slot
, nritems
);
2062 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2064 /* first correct the data pointers */
2065 for (i
= slot
; i
< nritems
; i
++) {
2067 item
= btrfs_item_nr(leaf
, i
);
2069 if (!leaf
->map_token
) {
2070 map_extent_buffer(leaf
, (unsigned long)item
,
2071 sizeof(struct btrfs_item
),
2072 &leaf
->map_token
, &leaf
->kaddr
,
2073 &leaf
->map_start
, &leaf
->map_len
,
2076 ioff
= btrfs_item_offset(leaf
, item
);
2077 btrfs_set_item_offset(leaf
, item
, ioff
- data_size
);
2080 if (leaf
->map_token
) {
2081 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
2082 leaf
->map_token
= NULL
;
2085 /* shift the data */
2086 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2087 data_end
- data_size
, btrfs_leaf_data(leaf
) +
2088 data_end
, old_data
- data_end
);
2090 data_end
= old_data
;
2091 old_size
= btrfs_item_size_nr(leaf
, slot
);
2092 item
= btrfs_item_nr(leaf
, slot
);
2093 btrfs_set_item_size(leaf
, item
, old_size
+ data_size
);
2094 btrfs_mark_buffer_dirty(leaf
);
2097 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
2098 btrfs_print_leaf(root
, leaf
);
2105 * Given a key and some data, insert an item into the tree.
2106 * This does all the path init required, making room in the tree if needed.
2108 int btrfs_insert_empty_item(struct btrfs_trans_handle
*trans
,
2109 struct btrfs_root
*root
,
2110 struct btrfs_path
*path
,
2111 struct btrfs_key
*cpu_key
, u32 data_size
)
2113 struct extent_buffer
*leaf
;
2114 struct btrfs_item
*item
;
2119 unsigned int data_end
;
2120 struct btrfs_disk_key disk_key
;
2122 btrfs_cpu_key_to_disk(&disk_key
, cpu_key
);
2124 /* create a root if there isn't one */
2128 ret
= btrfs_search_slot(trans
, root
, cpu_key
, path
, data_size
, 1);
2135 slot_orig
= path
->slots
[0];
2136 leaf
= path
->nodes
[0];
2138 nritems
= btrfs_header_nritems(leaf
);
2139 data_end
= leaf_data_end(root
, leaf
);
2141 if (btrfs_leaf_free_space(root
, leaf
) <
2142 sizeof(struct btrfs_item
) + data_size
) {
2143 btrfs_print_leaf(root
, leaf
);
2144 printk("not enough freespace need %u have %d\n",
2145 data_size
, btrfs_leaf_free_space(root
, leaf
));
2149 slot
= path
->slots
[0];
2152 if (slot
!= nritems
) {
2154 unsigned int old_data
= btrfs_item_end_nr(leaf
, slot
);
2156 if (old_data
< data_end
) {
2157 btrfs_print_leaf(root
, leaf
);
2158 printk("slot %d old_data %d data_end %d\n",
2159 slot
, old_data
, data_end
);
2163 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2165 /* first correct the data pointers */
2166 WARN_ON(leaf
->map_token
);
2167 for (i
= slot
; i
< nritems
; i
++) {
2170 item
= btrfs_item_nr(leaf
, i
);
2171 if (!leaf
->map_token
) {
2172 map_extent_buffer(leaf
, (unsigned long)item
,
2173 sizeof(struct btrfs_item
),
2174 &leaf
->map_token
, &leaf
->kaddr
,
2175 &leaf
->map_start
, &leaf
->map_len
,
2179 ioff
= btrfs_item_offset(leaf
, item
);
2180 btrfs_set_item_offset(leaf
, item
, ioff
- data_size
);
2182 if (leaf
->map_token
) {
2183 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
2184 leaf
->map_token
= NULL
;
2187 /* shift the items */
2188 memmove_extent_buffer(leaf
, btrfs_item_nr_offset(slot
+ 1),
2189 btrfs_item_nr_offset(slot
),
2190 (nritems
- slot
) * sizeof(struct btrfs_item
));
2192 /* shift the data */
2193 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2194 data_end
- data_size
, btrfs_leaf_data(leaf
) +
2195 data_end
, old_data
- data_end
);
2196 data_end
= old_data
;
2199 /* setup the item for the new data */
2200 btrfs_set_item_key(leaf
, &disk_key
, slot
);
2201 item
= btrfs_item_nr(leaf
, slot
);
2202 btrfs_set_item_offset(leaf
, item
, data_end
- data_size
);
2203 btrfs_set_item_size(leaf
, item
, data_size
);
2204 btrfs_set_header_nritems(leaf
, nritems
+ 1);
2205 btrfs_mark_buffer_dirty(leaf
);
2209 ret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
2211 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
2212 btrfs_print_leaf(root
, leaf
);
2220 * Given a key and some data, insert an item into the tree.
2221 * This does all the path init required, making room in the tree if needed.
2223 int btrfs_insert_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
2224 *root
, struct btrfs_key
*cpu_key
, void *data
, u32
2228 struct btrfs_path
*path
;
2229 struct extent_buffer
*leaf
;
2232 path
= btrfs_alloc_path();
2234 ret
= btrfs_insert_empty_item(trans
, root
, path
, cpu_key
, data_size
);
2236 leaf
= path
->nodes
[0];
2237 ptr
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
2238 write_extent_buffer(leaf
, data
, ptr
, data_size
);
2239 btrfs_mark_buffer_dirty(leaf
);
2241 btrfs_free_path(path
);
2246 * delete the pointer from a given node.
2248 * If the delete empties a node, the node is removed from the tree,
2249 * continuing all the way the root if required. The root is converted into
2250 * a leaf if all the nodes are emptied.
2252 static int del_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
2253 struct btrfs_path
*path
, int level
, int slot
)
2255 struct extent_buffer
*parent
= path
->nodes
[level
];
2260 nritems
= btrfs_header_nritems(parent
);
2261 if (slot
!= nritems
-1) {
2262 memmove_extent_buffer(parent
,
2263 btrfs_node_key_ptr_offset(slot
),
2264 btrfs_node_key_ptr_offset(slot
+ 1),
2265 sizeof(struct btrfs_key_ptr
) *
2266 (nritems
- slot
- 1));
2269 btrfs_set_header_nritems(parent
, nritems
);
2270 if (nritems
== 0 && parent
== root
->node
) {
2271 BUG_ON(btrfs_header_level(root
->node
) != 1);
2272 /* just turn the root into a leaf and break */
2273 btrfs_set_header_level(root
->node
, 0);
2274 } else if (slot
== 0) {
2275 struct btrfs_disk_key disk_key
;
2277 btrfs_node_key(parent
, &disk_key
, 0);
2278 wret
= fixup_low_keys(trans
, root
, path
, &disk_key
, level
+ 1);
2282 btrfs_mark_buffer_dirty(parent
);
2287 * delete the item at the leaf level in path. If that empties
2288 * the leaf, remove it from the tree
2290 int btrfs_del_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
2291 struct btrfs_path
*path
)
2294 struct extent_buffer
*leaf
;
2295 struct btrfs_item
*item
;
2302 leaf
= path
->nodes
[0];
2303 slot
= path
->slots
[0];
2304 doff
= btrfs_item_offset_nr(leaf
, slot
);
2305 dsize
= btrfs_item_size_nr(leaf
, slot
);
2306 nritems
= btrfs_header_nritems(leaf
);
2308 if (slot
!= nritems
- 1) {
2310 int data_end
= leaf_data_end(root
, leaf
);
2312 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2314 btrfs_leaf_data(leaf
) + data_end
,
2317 for (i
= slot
+ 1; i
< nritems
; i
++) {
2320 item
= btrfs_item_nr(leaf
, i
);
2321 if (!leaf
->map_token
) {
2322 map_extent_buffer(leaf
, (unsigned long)item
,
2323 sizeof(struct btrfs_item
),
2324 &leaf
->map_token
, &leaf
->kaddr
,
2325 &leaf
->map_start
, &leaf
->map_len
,
2328 ioff
= btrfs_item_offset(leaf
, item
);
2329 btrfs_set_item_offset(leaf
, item
, ioff
+ dsize
);
2332 if (leaf
->map_token
) {
2333 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
2334 leaf
->map_token
= NULL
;
2337 memmove_extent_buffer(leaf
, btrfs_item_nr_offset(slot
),
2338 btrfs_item_nr_offset(slot
+ 1),
2339 sizeof(struct btrfs_item
) *
2340 (nritems
- slot
- 1));
2342 btrfs_set_header_nritems(leaf
, nritems
- 1);
2345 /* delete the leaf if we've emptied it */
2347 if (leaf
== root
->node
) {
2348 btrfs_set_header_level(leaf
, 0);
2350 clean_tree_block(trans
, root
, leaf
);
2351 wait_on_tree_block_writeback(root
, leaf
);
2352 wret
= del_ptr(trans
, root
, path
, 1, path
->slots
[1]);
2355 wret
= btrfs_free_extent(trans
, root
,
2356 leaf
->start
, leaf
->len
, 1);
2361 int used
= leaf_space_used(leaf
, 0, nritems
);
2363 struct btrfs_disk_key disk_key
;
2365 btrfs_item_key(leaf
, &disk_key
, 0);
2366 wret
= fixup_low_keys(trans
, root
, path
,
2372 /* delete the leaf if it is mostly empty */
2373 if (used
< BTRFS_LEAF_DATA_SIZE(root
) / 3) {
2374 /* push_leaf_left fixes the path.
2375 * make sure the path still points to our leaf
2376 * for possible call to del_ptr below
2378 slot
= path
->slots
[1];
2379 extent_buffer_get(leaf
);
2381 wret
= push_leaf_left(trans
, root
, path
, 1);
2382 if (wret
< 0 && wret
!= -ENOSPC
)
2385 if (path
->nodes
[0] == leaf
&&
2386 btrfs_header_nritems(leaf
)) {
2387 wret
= push_leaf_right(trans
, root
, path
, 1);
2388 if (wret
< 0 && wret
!= -ENOSPC
)
2392 if (btrfs_header_nritems(leaf
) == 0) {
2393 u64 bytenr
= leaf
->start
;
2394 u32 blocksize
= leaf
->len
;
2396 clean_tree_block(trans
, root
, leaf
);
2397 wait_on_tree_block_writeback(root
, leaf
);
2399 wret
= del_ptr(trans
, root
, path
, 1, slot
);
2403 free_extent_buffer(leaf
);
2404 wret
= btrfs_free_extent(trans
, root
, bytenr
,
2409 btrfs_mark_buffer_dirty(leaf
);
2410 free_extent_buffer(leaf
);
2413 btrfs_mark_buffer_dirty(leaf
);
2420 * walk up the tree as far as required to find the next leaf.
2421 * returns 0 if it found something or 1 if there are no greater leaves.
2422 * returns < 0 on io errors.
2424 int btrfs_next_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
)
2429 struct extent_buffer
*c
;
2430 struct extent_buffer
*next
= NULL
;
2432 while(level
< BTRFS_MAX_LEVEL
) {
2433 if (!path
->nodes
[level
])
2436 slot
= path
->slots
[level
] + 1;
2437 c
= path
->nodes
[level
];
2438 if (slot
>= btrfs_header_nritems(c
)) {
2443 bytenr
= btrfs_node_blockptr(c
, slot
);
2445 free_extent_buffer(next
);
2448 reada_for_search(root
, path
, level
, slot
);
2450 next
= read_tree_block(root
, bytenr
,
2451 btrfs_level_size(root
, level
-1));
2454 path
->slots
[level
] = slot
;
2457 c
= path
->nodes
[level
];
2458 free_extent_buffer(c
);
2459 path
->nodes
[level
] = next
;
2460 path
->slots
[level
] = 0;
2464 reada_for_search(root
, path
, level
, 0);
2465 next
= read_tree_block(root
, btrfs_node_blockptr(next
, 0),
2466 btrfs_level_size(root
, level
- 1));