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 "kerncompat.h"
24 #include "transaction.h"
25 #include "print-tree.h"
27 static int split_node(struct btrfs_trans_handle
*trans
, struct btrfs_root
28 *root
, struct btrfs_path
*path
, int level
);
29 static int split_leaf(struct btrfs_trans_handle
*trans
, struct btrfs_root
30 *root
, struct btrfs_key
*ins_key
,
31 struct btrfs_path
*path
, int data_size
, int extend
);
32 static int push_node_left(struct btrfs_trans_handle
*trans
, struct btrfs_root
33 *root
, struct btrfs_buffer
*dst
, struct btrfs_buffer
35 static int balance_node_right(struct btrfs_trans_handle
*trans
, struct
36 btrfs_root
*root
, struct btrfs_buffer
*dst_buf
,
37 struct btrfs_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 void btrfs_release_path(struct btrfs_root
*root
, struct btrfs_path
*p
)
49 for (i
= 0; i
< BTRFS_MAX_LEVEL
; i
++) {
52 btrfs_block_release(root
, p
->nodes
[i
]);
54 memset(p
, 0, sizeof(*p
));
56 int btrfs_cow_block(struct btrfs_trans_handle
*trans
, struct btrfs_root
57 *root
, struct btrfs_buffer
*buf
, struct btrfs_buffer
58 *parent
, int parent_slot
, struct btrfs_buffer
61 struct btrfs_buffer
*cow
;
64 if (!list_empty(&buf
->dirty
)) {
68 cow
= btrfs_alloc_free_block(trans
, root
, buf
->size
);
69 memcpy(&cow
->node
, &buf
->node
, buf
->size
);
70 btrfs_set_header_bytenr(&cow
->node
.header
, cow
->bytenr
);
71 btrfs_set_header_generation(&cow
->node
.header
, trans
->transid
);
72 btrfs_set_header_owner(&cow
->node
.header
, root
->root_key
.objectid
);
74 btrfs_inc_ref(trans
, root
, buf
);
75 if (buf
== root
->node
) {
76 root_gen
= btrfs_header_generation(&buf
->node
.header
);
79 if (buf
!= root
->commit_root
)
80 btrfs_free_extent(trans
, root
, buf
->bytenr
,
81 buf
->size
, root
->root_key
.objectid
,
83 btrfs_block_release(root
, buf
);
85 root_gen
= btrfs_header_generation(&parent
->node
.header
);
86 btrfs_set_node_blockptr(&parent
->node
, parent_slot
,
88 btrfs_set_node_ptr_generation(&parent
->node
, parent_slot
,
90 BUG_ON(list_empty(&parent
->dirty
));
91 btrfs_free_extent(trans
, root
, buf
->bytenr
, buf
->size
,
92 root
->root_key
.objectid
, root_gen
, 0, 0, 1);
94 btrfs_block_release(root
, buf
);
99 * The leaf data grows from end-to-front in the node.
100 * this returns the address of the start of the last item,
101 * which is the stop of the leaf data stack
103 static inline unsigned int leaf_data_end(struct btrfs_root
*root
,
104 struct btrfs_leaf
*leaf
)
106 u32 nr
= btrfs_header_nritems(&leaf
->header
);
108 return BTRFS_LEAF_DATA_SIZE(root
);
109 return btrfs_item_offset(leaf
->items
+ nr
- 1);
113 * how many bytes are required to store the items in a leaf. start
114 * and nr indicate which items in the leaf to check. This totals up the
115 * space used both by the item structs and the item data
117 static int leaf_space_used(struct btrfs_leaf
*l
, int start
, int nr
)
120 int nritems
= btrfs_header_nritems(&l
->header
);
123 if (nritems
< start
+ nr
)
126 end
= start
+ nr
- 1;
130 data_len
= btrfs_item_end(l
->items
+ start
);
131 data_len
= data_len
- btrfs_item_offset(l
->items
+ end
);
132 data_len
+= sizeof(struct btrfs_item
) * nr
;
137 * The space between the end of the leaf items and
138 * the start of the leaf data. IOW, how much room
139 * the leaf has left for both items and data
141 int btrfs_leaf_free_space(struct btrfs_root
*root
, struct btrfs_leaf
*leaf
)
143 int nritems
= btrfs_header_nritems(&leaf
->header
);
144 return BTRFS_LEAF_DATA_SIZE(root
) - leaf_space_used(leaf
, 0, nritems
);
148 * compare two keys in a memcmp fashion
150 int btrfs_comp_keys(struct btrfs_disk_key
*disk
, struct btrfs_key
*k2
)
154 btrfs_disk_key_to_cpu(&k1
, disk
);
156 if (k1
.objectid
> k2
->objectid
)
158 if (k1
.objectid
< k2
->objectid
)
160 if (k1
.type
> k2
->type
)
162 if (k1
.type
< k2
->type
)
164 if (k1
.offset
> k2
->offset
)
166 if (k1
.offset
< k2
->offset
)
171 static int check_node(struct btrfs_root
*root
, struct btrfs_path
*path
,
175 struct btrfs_node
*parent
= NULL
;
176 struct btrfs_node
*node
= &path
->nodes
[level
]->node
;
178 u32 nritems
= btrfs_header_nritems(&node
->header
);
180 if (path
->nodes
[level
+ 1])
181 parent
= &path
->nodes
[level
+ 1]->node
;
182 parent_slot
= path
->slots
[level
+ 1];
183 BUG_ON(nritems
== 0);
185 struct btrfs_disk_key
*parent_key
;
186 parent_key
= &parent
->ptrs
[parent_slot
].key
;
187 BUG_ON(memcmp(parent_key
, &node
->ptrs
[0].key
,
188 sizeof(struct btrfs_disk_key
)));
189 BUG_ON(btrfs_node_blockptr(parent
, parent_slot
) !=
190 btrfs_header_bytenr(&node
->header
));
192 BUG_ON(nritems
> BTRFS_NODEPTRS_PER_BLOCK(root
));
193 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
194 struct btrfs_key cpukey
;
195 btrfs_disk_key_to_cpu(&cpukey
, &node
->ptrs
[i
+ 1].key
);
196 BUG_ON(btrfs_comp_keys(&node
->ptrs
[i
].key
, &cpukey
) >= 0);
201 static int check_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
,
205 struct btrfs_leaf
*leaf
= &path
->nodes
[level
]->leaf
;
206 struct btrfs_node
*parent
= NULL
;
208 u32 nritems
= btrfs_header_nritems(&leaf
->header
);
210 if (path
->nodes
[level
+ 1])
211 parent
= &path
->nodes
[level
+ 1]->node
;
212 parent_slot
= path
->slots
[level
+ 1];
213 BUG_ON(btrfs_leaf_free_space(root
, leaf
) < 0);
219 struct btrfs_disk_key
*parent_key
;
220 parent_key
= &parent
->ptrs
[parent_slot
].key
;
221 BUG_ON(memcmp(parent_key
, &leaf
->items
[0].key
,
222 sizeof(struct btrfs_disk_key
)));
223 BUG_ON(btrfs_node_blockptr(parent
, parent_slot
) !=
224 btrfs_header_bytenr(&leaf
->header
));
226 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
227 struct btrfs_key cpukey
;
228 btrfs_disk_key_to_cpu(&cpukey
, &leaf
->items
[i
+ 1].key
);
229 BUG_ON(btrfs_comp_keys(&leaf
->items
[i
].key
,
231 BUG_ON(btrfs_item_offset(leaf
->items
+ i
) !=
232 btrfs_item_end(leaf
->items
+ i
+ 1));
234 BUG_ON(btrfs_item_offset(leaf
->items
+ i
) +
235 btrfs_item_size(leaf
->items
+ i
) !=
236 BTRFS_LEAF_DATA_SIZE(root
));
242 static int check_block(struct btrfs_root
*root
, struct btrfs_path
*path
,
246 return check_leaf(root
, path
, level
);
247 return check_node(root
, path
, level
);
251 * search for key in the array p. items p are item_size apart
252 * and there are 'max' items in p
253 * the slot in the array is returned via slot, and it points to
254 * the place where you would insert key if it is not found in
257 * slot may point to max if the key is bigger than all of the keys
259 static int generic_bin_search(char *p
, int item_size
, struct btrfs_key
*key
,
266 struct btrfs_disk_key
*tmp
;
269 mid
= (low
+ high
) / 2;
270 tmp
= (struct btrfs_disk_key
*)(p
+ mid
* item_size
);
271 ret
= btrfs_comp_keys(tmp
, key
);
287 * simple bin_search frontend that does the right thing for
290 static int bin_search(struct btrfs_node
*c
, struct btrfs_key
*key
, int *slot
)
292 if (btrfs_is_leaf(c
)) {
293 struct btrfs_leaf
*l
= (struct btrfs_leaf
*)c
;
294 return generic_bin_search((void *)l
->items
,
295 sizeof(struct btrfs_item
),
296 key
, btrfs_header_nritems(&c
->header
),
299 return generic_bin_search((void *)c
->ptrs
,
300 sizeof(struct btrfs_key_ptr
),
301 key
, btrfs_header_nritems(&c
->header
),
307 static struct btrfs_buffer
*read_node_slot(struct btrfs_root
*root
,
308 struct btrfs_buffer
*parent_buf
,
311 struct btrfs_node
*node
= &parent_buf
->node
;
312 int level
= btrfs_header_level(&node
->header
);
315 if (slot
>= btrfs_header_nritems(&node
->header
))
317 return read_tree_block(root
, btrfs_node_blockptr(node
, slot
),
318 btrfs_level_size(root
, level
- 1));
321 static int balance_level(struct btrfs_trans_handle
*trans
, struct btrfs_root
322 *root
, struct btrfs_path
*path
, int level
)
324 struct btrfs_buffer
*right_buf
;
325 struct btrfs_buffer
*mid_buf
;
326 struct btrfs_buffer
*left_buf
;
327 struct btrfs_buffer
*parent_buf
= NULL
;
328 struct btrfs_node
*right
= NULL
;
329 struct btrfs_node
*mid
;
330 struct btrfs_node
*left
= NULL
;
331 struct btrfs_node
*parent
= NULL
;
335 int orig_slot
= path
->slots
[level
];
341 mid_buf
= path
->nodes
[level
];
342 mid
= &mid_buf
->node
;
343 orig_ptr
= btrfs_node_blockptr(mid
, orig_slot
);
345 if (level
< BTRFS_MAX_LEVEL
- 1)
346 parent_buf
= path
->nodes
[level
+ 1];
347 pslot
= path
->slots
[level
+ 1];
350 * deal with the case where there is only one pointer in the root
351 * by promoting the node below to a root
354 struct btrfs_buffer
*child
;
355 u64 bytenr
= mid_buf
->bytenr
;
357 if (btrfs_header_nritems(&mid
->header
) != 1)
360 /* promote the child to a root */
361 child
= read_node_slot(root
, mid_buf
, 0);
364 path
->nodes
[level
] = NULL
;
365 /* once for the path */
366 btrfs_block_release(root
, mid_buf
);
367 /* once for the root ptr */
368 btrfs_block_release(root
, mid_buf
);
369 clean_tree_block(trans
, root
, mid_buf
);
370 return btrfs_free_extent(trans
, root
, bytenr
, root
->nodesize
,
371 root
->root_key
.objectid
,
372 btrfs_header_generation(&mid
->header
),
375 parent
= &parent_buf
->node
;
377 if (btrfs_header_nritems(&mid
->header
) >
378 BTRFS_NODEPTRS_PER_BLOCK(root
) / 4)
381 left_buf
= read_node_slot(root
, parent_buf
, pslot
- 1);
382 right_buf
= read_node_slot(root
, parent_buf
, pslot
+ 1);
384 /* first, try to make some room in the middle buffer */
386 btrfs_cow_block(trans
, root
, left_buf
, parent_buf
, pslot
- 1,
388 left
= &left_buf
->node
;
389 orig_slot
+= btrfs_header_nritems(&left
->header
);
390 wret
= push_node_left(trans
, root
, left_buf
, mid_buf
);
396 * then try to empty the right most buffer into the middle
399 btrfs_cow_block(trans
, root
, right_buf
, parent_buf
, pslot
+ 1,
401 right
= &right_buf
->node
;
402 wret
= push_node_left(trans
, root
, mid_buf
, right_buf
);
405 if (btrfs_header_nritems(&right
->header
) == 0) {
407 u64 bytenr
= right_buf
->bytenr
;
409 generation
= btrfs_header_generation(&parent
->header
);
410 btrfs_block_release(root
, right_buf
);
411 clean_tree_block(trans
, root
, right_buf
);
414 wret
= del_ptr(trans
, root
, path
, level
+ 1, pslot
+
418 wret
= btrfs_free_extent(trans
, root
, bytenr
,
420 root
->root_key
.objectid
,
421 generation
, 0, 0, 1);
425 memcpy(&parent
->ptrs
[pslot
+ 1].key
,
427 sizeof(struct btrfs_disk_key
));
428 BUG_ON(list_empty(&parent_buf
->dirty
));
431 if (btrfs_header_nritems(&mid
->header
) == 1) {
433 * we're not allowed to leave a node with one item in the
434 * tree during a delete. A deletion from lower in the tree
435 * could try to delete the only pointer in this node.
436 * So, pull some keys from the left.
437 * There has to be a left pointer at this point because
438 * otherwise we would have pulled some pointers from the
442 wret
= balance_node_right(trans
, root
, mid_buf
, left_buf
);
447 if (btrfs_header_nritems(&mid
->header
) == 0) {
448 /* we've managed to empty the middle node, drop it */
449 u64 bytenr
= mid_buf
->bytenr
;
452 generation
= btrfs_header_generation(&parent
->header
);
453 btrfs_block_release(root
, mid_buf
);
454 clean_tree_block(trans
, root
, mid_buf
);
457 wret
= del_ptr(trans
, root
, path
, level
+ 1, pslot
);
460 wret
= btrfs_free_extent(trans
, root
, bytenr
, root
->nodesize
,
461 root
->root_key
.objectid
,
462 generation
, 0, 0, 1);
466 /* update the parent key to reflect our changes */
467 memcpy(&parent
->ptrs
[pslot
].key
, &mid
->ptrs
[0].key
,
468 sizeof(struct btrfs_disk_key
));
469 BUG_ON(list_empty(&parent_buf
->dirty
));
472 /* update the path */
474 if (btrfs_header_nritems(&left
->header
) > orig_slot
) {
475 left_buf
->count
++; // released below
476 path
->nodes
[level
] = left_buf
;
477 path
->slots
[level
+ 1] -= 1;
478 path
->slots
[level
] = orig_slot
;
480 btrfs_block_release(root
, mid_buf
);
482 orig_slot
-= btrfs_header_nritems(&left
->header
);
483 path
->slots
[level
] = orig_slot
;
486 /* double check we haven't messed things up */
487 check_block(root
, path
, level
);
488 if (orig_ptr
!= btrfs_node_blockptr(&path
->nodes
[level
]->node
,
493 btrfs_block_release(root
, right_buf
);
495 btrfs_block_release(root
, left_buf
);
498 static int push_nodes_for_insert(struct btrfs_trans_handle
*trans
,
499 struct btrfs_root
*root
,
500 struct btrfs_path
*path
, int level
)
502 struct btrfs_node
*right
;
503 struct btrfs_node
*mid
;
504 struct btrfs_node
*left
;
505 struct btrfs_node
*parent
;
506 struct btrfs_buffer
*right_buf
;
507 struct btrfs_buffer
*mid_buf
;
508 struct btrfs_buffer
*left_buf
;
509 struct btrfs_buffer
*parent_buf
= NULL
;
513 int orig_slot
= path
->slots
[level
];
519 mid_buf
= path
->nodes
[level
];
520 mid
= &mid_buf
->node
;
521 orig_ptr
= btrfs_node_blockptr(mid
, orig_slot
);
523 if (level
< BTRFS_MAX_LEVEL
- 1)
524 parent_buf
= path
->nodes
[level
+ 1];
525 pslot
= path
->slots
[level
+ 1];
529 parent
= &parent_buf
->node
;
531 left_buf
= read_node_slot(root
, parent_buf
, pslot
- 1);
532 left
= &left_buf
->node
;
534 /* first, try to make some room in the middle buffer */
537 left_nr
= btrfs_header_nritems(&left
->header
);
538 if (left_nr
>= BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
541 ret
= btrfs_cow_block(trans
, root
, left_buf
,
542 parent_buf
, pslot
- 1,
544 left
= &left_buf
->node
;
548 wret
= push_node_left(trans
, root
,
555 orig_slot
+= left_nr
;
556 memcpy(&parent
->ptrs
[pslot
].key
, &mid
->ptrs
[0].key
,
557 sizeof(struct btrfs_disk_key
));
558 BUG_ON(list_empty(&parent_buf
->dirty
));
559 if (btrfs_header_nritems(&left
->header
) > orig_slot
) {
560 path
->nodes
[level
] = left_buf
;
561 path
->slots
[level
+ 1] -= 1;
562 path
->slots
[level
] = orig_slot
;
563 btrfs_block_release(root
, mid_buf
);
566 btrfs_header_nritems(&left
->header
);
567 path
->slots
[level
] = orig_slot
;
568 btrfs_block_release(root
, left_buf
);
572 btrfs_block_release(root
, left_buf
);
575 right_buf
= read_node_slot(root
, parent_buf
, pslot
+ 1);
576 right
= &right_buf
->node
;
579 * then try to empty the right most buffer into the middle
583 right_nr
= btrfs_header_nritems(&right
->header
);
584 if (right_nr
>= BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
587 ret
= btrfs_cow_block(trans
, root
, right_buf
,
588 parent_buf
, pslot
+ 1,
590 right
= &right_buf
->node
;
594 wret
= balance_node_right(trans
, root
,
601 memcpy(&parent
->ptrs
[pslot
+ 1].key
,
603 sizeof(struct btrfs_disk_key
));
604 BUG_ON(list_empty(&parent_buf
->dirty
));
605 if (btrfs_header_nritems(&mid
->header
) <= orig_slot
) {
606 path
->nodes
[level
] = right_buf
;
607 path
->slots
[level
+ 1] += 1;
608 path
->slots
[level
] = orig_slot
-
609 btrfs_header_nritems(&mid
->header
);
610 btrfs_block_release(root
, mid_buf
);
612 btrfs_block_release(root
, right_buf
);
616 btrfs_block_release(root
, right_buf
);
622 * look for key in the tree. path is filled in with nodes along the way
623 * if key is found, we return zero and you can find the item in the leaf
624 * level of the path (level 0)
626 * If the key isn't found, the path points to the slot where it should
627 * be inserted, and 1 is returned. If there are other errors during the
628 * search a negative error number is returned.
630 * if ins_len > 0, nodes and leaves will be split as we walk down the
631 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
634 int btrfs_search_slot(struct btrfs_trans_handle
*trans
, struct btrfs_root
635 *root
, struct btrfs_key
*key
, struct btrfs_path
*p
, int
638 struct btrfs_buffer
*b
;
639 struct btrfs_node
*c
;
648 level
= btrfs_header_level(&b
->node
.header
);
651 wret
= btrfs_cow_block(trans
, root
, b
,
656 btrfs_block_release(root
, b
);
660 BUG_ON(!cow
&& ins_len
);
663 ret
= check_block(root
, p
, level
);
666 ret
= bin_search(c
, key
, &slot
);
667 if (!btrfs_is_leaf(c
)) {
670 p
->slots
[level
] = slot
;
671 if (ins_len
> 0 && btrfs_header_nritems(&c
->header
) >=
672 BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
673 int sret
= split_node(trans
, root
, p
, level
);
679 slot
= p
->slots
[level
];
680 } else if (ins_len
< 0) {
681 int sret
= balance_level(trans
, root
, p
,
687 btrfs_release_path(NULL
, p
);
691 slot
= p
->slots
[level
];
692 BUG_ON(btrfs_header_nritems(&c
->header
) == 1);
694 b
= read_tree_block(root
,
695 btrfs_node_blockptr(c
, slot
),
696 btrfs_level_size(root
, level
- 1));
698 struct btrfs_leaf
*l
= (struct btrfs_leaf
*)c
;
699 p
->slots
[level
] = slot
;
700 if (ins_len
> 0 && btrfs_leaf_free_space(root
, l
) <
701 sizeof(struct btrfs_item
) + ins_len
) {
702 int sret
= split_leaf(trans
, root
, key
,
703 p
, ins_len
, ret
== 0);
708 BUG_ON(root
->node
->count
== 1);
712 BUG_ON(root
->node
->count
== 1);
717 * adjust the pointers going up the tree, starting at level
718 * making sure the right key of each node is points to 'key'.
719 * This is used after shifting pointers to the left, so it stops
720 * fixing up pointers when a given leaf/node is not in slot 0 of the
723 * If this fails to write a tree block, it returns -1, but continues
724 * fixing up the blocks in ram so the tree is consistent.
726 static int fixup_low_keys(struct btrfs_trans_handle
*trans
, struct btrfs_root
727 *root
, struct btrfs_path
*path
, struct btrfs_disk_key
732 for (i
= level
; i
< BTRFS_MAX_LEVEL
; i
++) {
733 struct btrfs_node
*t
;
734 int tslot
= path
->slots
[i
];
737 t
= &path
->nodes
[i
]->node
;
738 memcpy(&t
->ptrs
[tslot
].key
, key
, sizeof(*key
));
739 BUG_ON(list_empty(&path
->nodes
[i
]->dirty
));
747 * try to push data from one node into the next node left in the
750 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
751 * error, and > 0 if there was no room in the left hand block.
753 static int push_node_left(struct btrfs_trans_handle
*trans
, struct btrfs_root
754 *root
, struct btrfs_buffer
*dst_buf
, struct
755 btrfs_buffer
*src_buf
)
757 struct btrfs_node
*src
= &src_buf
->node
;
758 struct btrfs_node
*dst
= &dst_buf
->node
;
764 src_nritems
= btrfs_header_nritems(&src
->header
);
765 dst_nritems
= btrfs_header_nritems(&dst
->header
);
766 push_items
= BTRFS_NODEPTRS_PER_BLOCK(root
) - dst_nritems
;
767 if (push_items
<= 0) {
771 if (src_nritems
< push_items
)
772 push_items
= src_nritems
;
774 memcpy(dst
->ptrs
+ dst_nritems
, src
->ptrs
,
775 push_items
* sizeof(struct btrfs_key_ptr
));
776 if (push_items
< src_nritems
) {
777 memmove(src
->ptrs
, src
->ptrs
+ push_items
,
778 (src_nritems
- push_items
) *
779 sizeof(struct btrfs_key_ptr
));
781 btrfs_set_header_nritems(&src
->header
, src_nritems
- push_items
);
782 btrfs_set_header_nritems(&dst
->header
, dst_nritems
+ push_items
);
783 BUG_ON(list_empty(&src_buf
->dirty
));
784 BUG_ON(list_empty(&dst_buf
->dirty
));
789 * try to push data from one node into the next node right in the
792 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
793 * error, and > 0 if there was no room in the right hand block.
795 * this will only push up to 1/2 the contents of the left node over
797 static int balance_node_right(struct btrfs_trans_handle
*trans
, struct
798 btrfs_root
*root
, struct btrfs_buffer
*dst_buf
,
799 struct btrfs_buffer
*src_buf
)
801 struct btrfs_node
*src
= &src_buf
->node
;
802 struct btrfs_node
*dst
= &dst_buf
->node
;
809 src_nritems
= btrfs_header_nritems(&src
->header
);
810 dst_nritems
= btrfs_header_nritems(&dst
->header
);
811 push_items
= BTRFS_NODEPTRS_PER_BLOCK(root
) - dst_nritems
;
812 if (push_items
<= 0) {
815 max_push
= src_nritems
/ 2 + 1;
816 /* don't try to empty the node */
817 if (max_push
>= src_nritems
)
819 if (max_push
< push_items
)
820 push_items
= max_push
;
822 memmove(dst
->ptrs
+ push_items
, dst
->ptrs
,
823 dst_nritems
* sizeof(struct btrfs_key_ptr
));
824 memcpy(dst
->ptrs
, src
->ptrs
+ src_nritems
- push_items
,
825 push_items
* sizeof(struct btrfs_key_ptr
));
827 btrfs_set_header_nritems(&src
->header
, src_nritems
- push_items
);
828 btrfs_set_header_nritems(&dst
->header
, dst_nritems
+ push_items
);
830 BUG_ON(list_empty(&src_buf
->dirty
));
831 BUG_ON(list_empty(&dst_buf
->dirty
));
836 * helper function to insert a new root level in the tree.
837 * A new node is allocated, and a single item is inserted to
838 * point to the existing root
840 * returns zero on success or < 0 on failure.
842 static int insert_new_root(struct btrfs_trans_handle
*trans
, struct btrfs_root
843 *root
, struct btrfs_path
*path
, int level
)
845 struct btrfs_buffer
*t
;
846 struct btrfs_node
*lower
;
847 struct btrfs_node
*c
;
848 struct btrfs_disk_key
*lower_key
;
850 BUG_ON(path
->nodes
[level
]);
851 BUG_ON(path
->nodes
[level
-1] != root
->node
);
852 t
= btrfs_alloc_free_block(trans
, root
, root
->nodesize
);
854 memset(&c
->header
, 0, sizeof(c
->header
));
855 btrfs_set_header_nritems(&c
->header
, 1);
856 btrfs_set_header_level(&c
->header
, level
);
857 btrfs_set_header_bytenr(&c
->header
, t
->bytenr
);
858 btrfs_set_header_generation(&c
->header
, trans
->transid
);
859 btrfs_set_header_owner(&c
->header
, root
->root_key
.objectid
);
860 memcpy(c
->header
.fsid
, root
->fs_info
->disk_super
->fsid
,
861 sizeof(c
->header
.fsid
));
862 lower
= &path
->nodes
[level
-1]->node
;
864 if (btrfs_is_leaf(lower
))
865 lower_key
= &((struct btrfs_leaf
*)lower
)->items
[0].key
;
867 lower_key
= &lower
->ptrs
[0].key
;
868 memcpy(&c
->ptrs
[0].key
, lower_key
, sizeof(struct btrfs_disk_key
));
869 btrfs_set_node_blockptr(c
, 0, path
->nodes
[level
- 1]->bytenr
);
870 BUG_ON(list_empty(&t
->dirty
));
871 btrfs_set_node_ptr_generation(c
, 0,
872 btrfs_header_generation(&path
->nodes
[level
- 1]->node
.header
));
873 /* the super has an extra ref to root->node */
874 btrfs_block_release(root
, root
->node
);
877 path
->nodes
[level
] = t
;
878 path
->slots
[level
] = 0;
883 * worker function to insert a single pointer in a node.
884 * the node should have enough room for the pointer already
886 * slot and level indicate where you want the key to go, and
887 * bytenr is the block the key points to.
889 * returns zero on success and < 0 on any error
891 static int insert_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
892 *root
, struct btrfs_path
*path
, struct btrfs_disk_key
893 *key
, u64 bytenr
, int slot
, int level
)
895 struct btrfs_node
*lower
;
898 BUG_ON(!path
->nodes
[level
]);
899 lower
= &path
->nodes
[level
]->node
;
900 nritems
= btrfs_header_nritems(&lower
->header
);
903 if (nritems
== BTRFS_NODEPTRS_PER_BLOCK(root
))
905 if (slot
!= nritems
) {
906 memmove(lower
->ptrs
+ slot
+ 1, lower
->ptrs
+ slot
,
907 (nritems
- slot
) * sizeof(struct btrfs_key_ptr
));
909 memcpy(&lower
->ptrs
[slot
].key
, key
, sizeof(struct btrfs_disk_key
));
910 btrfs_set_node_blockptr(lower
, slot
, bytenr
);
911 btrfs_set_node_ptr_generation(lower
, slot
, trans
->transid
);
912 btrfs_set_header_nritems(&lower
->header
, nritems
+ 1);
913 BUG_ON(list_empty(&path
->nodes
[level
]->dirty
));
918 * split the node at the specified level in path in two.
919 * The path is corrected to point to the appropriate node after the split
921 * Before splitting this tries to make some room in the node by pushing
922 * left and right, if either one works, it returns right away.
924 * returns 0 on success and < 0 on failure
926 static int split_node(struct btrfs_trans_handle
*trans
, struct btrfs_root
927 *root
, struct btrfs_path
*path
, int level
)
929 struct btrfs_buffer
*t
;
930 struct btrfs_node
*c
;
931 struct btrfs_buffer
*split_buffer
;
932 struct btrfs_node
*split
;
938 t
= path
->nodes
[level
];
940 if (t
== root
->node
) {
941 /* trying to split the root, lets make a new one */
942 ret
= insert_new_root(trans
, root
, path
, level
+ 1);
946 ret
= push_nodes_for_insert(trans
, root
, path
, level
);
947 t
= path
->nodes
[level
];
949 if (!ret
&& btrfs_header_nritems(&c
->header
) <
950 BTRFS_NODEPTRS_PER_BLOCK(root
) - 1)
955 c_nritems
= btrfs_header_nritems(&c
->header
);
956 split_buffer
= btrfs_alloc_free_block(trans
, root
, root
->nodesize
);
957 split
= &split_buffer
->node
;
958 btrfs_set_header_flags(&split
->header
, btrfs_header_flags(&c
->header
));
959 btrfs_set_header_level(&split
->header
, btrfs_header_level(&c
->header
));
960 btrfs_set_header_bytenr(&split
->header
, split_buffer
->bytenr
);
961 btrfs_set_header_generation(&split
->header
, trans
->transid
);
962 btrfs_set_header_owner(&split
->header
, root
->root_key
.objectid
);
963 memcpy(split
->header
.fsid
, root
->fs_info
->disk_super
->fsid
,
964 sizeof(split
->header
.fsid
));
965 mid
= (c_nritems
+ 1) / 2;
966 memcpy(split
->ptrs
, c
->ptrs
+ mid
,
967 (c_nritems
- mid
) * sizeof(struct btrfs_key_ptr
));
968 btrfs_set_header_nritems(&split
->header
, c_nritems
- mid
);
969 btrfs_set_header_nritems(&c
->header
, mid
);
972 BUG_ON(list_empty(&t
->dirty
));
973 wret
= insert_ptr(trans
, root
, path
, &split
->ptrs
[0].key
,
974 split_buffer
->bytenr
, path
->slots
[level
+ 1] + 1,
979 if (path
->slots
[level
] >= mid
) {
980 path
->slots
[level
] -= mid
;
981 btrfs_block_release(root
, t
);
982 path
->nodes
[level
] = split_buffer
;
983 path
->slots
[level
+ 1] += 1;
985 btrfs_block_release(root
, split_buffer
);
991 * push some data in the path leaf to the right, trying to free up at
992 * least data_size bytes. returns zero if the push worked, nonzero otherwise
994 * returns 1 if the push failed because the other node didn't have enough
995 * room, 0 if everything worked out and < 0 if there were major errors.
997 static int push_leaf_right(struct btrfs_trans_handle
*trans
, struct btrfs_root
998 *root
, struct btrfs_path
*path
, int data_size
,
1001 struct btrfs_buffer
*left_buf
= path
->nodes
[0];
1002 struct btrfs_leaf
*left
= &left_buf
->leaf
;
1003 struct btrfs_leaf
*right
;
1004 struct btrfs_buffer
*right_buf
;
1005 struct btrfs_buffer
*upper
;
1011 struct btrfs_item
*item
;
1015 slot
= path
->slots
[1];
1016 if (!path
->nodes
[1]) {
1019 upper
= path
->nodes
[1];
1020 if (slot
>= btrfs_header_nritems(&upper
->node
.header
) - 1) {
1023 right_buf
= read_tree_block(root
,
1024 btrfs_node_blockptr(&upper
->node
, slot
+ 1),
1026 right
= &right_buf
->leaf
;
1027 free_space
= btrfs_leaf_free_space(root
, right
);
1028 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1029 btrfs_block_release(root
, right_buf
);
1032 /* cow and double check */
1033 btrfs_cow_block(trans
, root
, right_buf
, upper
, slot
+ 1, &right_buf
);
1034 right
= &right_buf
->leaf
;
1035 free_space
= btrfs_leaf_free_space(root
, right
);
1036 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1037 btrfs_block_release(root
, right_buf
);
1040 left_nritems
= btrfs_header_nritems(&left
->header
);
1041 if (left_nritems
== 0) {
1042 btrfs_block_release(root
, right_buf
);
1051 i
= left_nritems
- 1;
1053 item
= left
->items
+ i
;
1054 if (path
->slots
[0] == i
)
1055 push_space
+= data_size
+ sizeof(*item
);
1056 if (btrfs_item_size(item
) + sizeof(*item
) + push_space
>
1060 push_space
+= btrfs_item_size(item
) + sizeof(*item
);
1065 if (push_items
== 0) {
1066 btrfs_block_release(root
, right_buf
);
1069 right_nritems
= btrfs_header_nritems(&right
->header
);
1070 /* push left to right */
1071 push_space
= btrfs_item_end(left
->items
+ left_nritems
- push_items
);
1072 push_space
-= leaf_data_end(root
, left
);
1073 /* make room in the right data area */
1074 memmove(btrfs_leaf_data(right
) + leaf_data_end(root
, right
) -
1075 push_space
, btrfs_leaf_data(right
) + leaf_data_end(root
, right
),
1076 BTRFS_LEAF_DATA_SIZE(root
) - leaf_data_end(root
, right
));
1077 /* copy from the left data area */
1078 memcpy(btrfs_leaf_data(right
) + BTRFS_LEAF_DATA_SIZE(root
) - push_space
,
1079 btrfs_leaf_data(left
) + leaf_data_end(root
, left
), push_space
);
1080 memmove(right
->items
+ push_items
, right
->items
,
1081 right_nritems
* sizeof(struct btrfs_item
));
1082 /* copy the items from left to right */
1083 memcpy(right
->items
, left
->items
+ left_nritems
- push_items
,
1084 push_items
* sizeof(struct btrfs_item
));
1086 /* update the item pointers */
1087 right_nritems
+= push_items
;
1088 btrfs_set_header_nritems(&right
->header
, right_nritems
);
1089 push_space
= BTRFS_LEAF_DATA_SIZE(root
);
1090 for (i
= 0; i
< right_nritems
; i
++) {
1091 btrfs_set_item_offset(right
->items
+ i
, push_space
-
1092 btrfs_item_size(right
->items
+ i
));
1093 push_space
= btrfs_item_offset(right
->items
+ i
);
1095 left_nritems
-= push_items
;
1096 btrfs_set_header_nritems(&left
->header
, left_nritems
);
1098 BUG_ON(list_empty(&left_buf
->dirty
));
1099 BUG_ON(list_empty(&right_buf
->dirty
));
1100 memcpy(&upper
->node
.ptrs
[slot
+ 1].key
,
1101 &right
->items
[0].key
, sizeof(struct btrfs_disk_key
));
1102 BUG_ON(list_empty(&upper
->dirty
));
1104 /* then fixup the leaf pointer in the path */
1105 if (path
->slots
[0] >= left_nritems
) {
1106 path
->slots
[0] -= left_nritems
;
1107 btrfs_block_release(root
, path
->nodes
[0]);
1108 path
->nodes
[0] = right_buf
;
1109 path
->slots
[1] += 1;
1111 btrfs_block_release(root
, right_buf
);
1116 * push some data in the path leaf to the left, trying to free up at
1117 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1119 static int push_leaf_left(struct btrfs_trans_handle
*trans
, struct btrfs_root
1120 *root
, struct btrfs_path
*path
, int data_size
,
1123 struct btrfs_buffer
*right_buf
= path
->nodes
[0];
1124 struct btrfs_leaf
*right
= &right_buf
->leaf
;
1125 struct btrfs_buffer
*t
;
1126 struct btrfs_leaf
*left
;
1132 struct btrfs_item
*item
;
1133 u32 old_left_nritems
;
1138 slot
= path
->slots
[1];
1142 if (!path
->nodes
[1]) {
1145 right_nritems
= btrfs_header_nritems(&right
->header
);
1146 if (right_nritems
== 0) {
1150 t
= read_tree_block(root
,
1151 btrfs_node_blockptr(&path
->nodes
[1]->node
, slot
- 1),
1154 free_space
= btrfs_leaf_free_space(root
, left
);
1155 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1156 btrfs_block_release(root
, t
);
1160 /* cow and double check */
1161 btrfs_cow_block(trans
, root
, t
, path
->nodes
[1], slot
- 1, &t
);
1163 free_space
= btrfs_leaf_free_space(root
, left
);
1164 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1165 btrfs_block_release(root
, t
);
1171 nr
= right_nritems
- 1;
1173 for (i
= 0; i
< nr
; i
++) {
1174 item
= right
->items
+ i
;
1175 if (path
->slots
[0] == i
)
1176 push_space
+= data_size
+ sizeof(*item
);
1177 if (btrfs_item_size(item
) + sizeof(*item
) + push_space
>
1181 push_space
+= btrfs_item_size(item
) + sizeof(*item
);
1183 if (push_items
== 0) {
1184 btrfs_block_release(root
, t
);
1187 /* push data from right to left */
1188 memcpy(left
->items
+ btrfs_header_nritems(&left
->header
),
1189 right
->items
, push_items
* sizeof(struct btrfs_item
));
1190 push_space
= BTRFS_LEAF_DATA_SIZE(root
) -
1191 btrfs_item_offset(right
->items
+ push_items
-1);
1192 memcpy(btrfs_leaf_data(left
) + leaf_data_end(root
, left
) - push_space
,
1193 btrfs_leaf_data(right
) +
1194 btrfs_item_offset(right
->items
+ push_items
- 1),
1196 old_left_nritems
= btrfs_header_nritems(&left
->header
);
1197 BUG_ON(old_left_nritems
< 0);
1199 for (i
= old_left_nritems
; i
< old_left_nritems
+ push_items
; i
++) {
1200 u32 ioff
= btrfs_item_offset(left
->items
+ i
);
1201 btrfs_set_item_offset(left
->items
+ i
, ioff
-
1202 (BTRFS_LEAF_DATA_SIZE(root
) -
1203 btrfs_item_offset(left
->items
+
1204 old_left_nritems
- 1)));
1206 btrfs_set_header_nritems(&left
->header
, old_left_nritems
+ push_items
);
1207 /* fixup right node */
1208 if (push_items
< right_nritems
) {
1209 push_space
= btrfs_item_offset(right
->items
+ push_items
- 1) -
1210 leaf_data_end(root
, right
);
1211 memmove(btrfs_leaf_data(right
) + BTRFS_LEAF_DATA_SIZE(root
) -
1212 push_space
, btrfs_leaf_data(right
) +
1213 leaf_data_end(root
, right
), push_space
);
1214 memmove(right
->items
, right
->items
+ push_items
,
1215 (right_nritems
- push_items
) *
1216 sizeof(struct btrfs_item
));
1218 right_nritems
-= push_items
;
1219 btrfs_set_header_nritems(&right
->header
, right_nritems
);
1220 push_space
= BTRFS_LEAF_DATA_SIZE(root
);
1221 for (i
= 0; i
< right_nritems
; i
++) {
1222 btrfs_set_item_offset(right
->items
+ i
, push_space
-
1223 btrfs_item_size(right
->items
+ i
));
1224 push_space
= btrfs_item_offset(right
->items
+ i
);
1227 BUG_ON(list_empty(&t
->dirty
));
1228 BUG_ON(list_empty(&right_buf
->dirty
));
1230 wret
= fixup_low_keys(trans
, root
, path
, &right
->items
[0].key
, 1);
1234 /* then fixup the leaf pointer in the path */
1235 if (path
->slots
[0] < push_items
) {
1236 path
->slots
[0] += old_left_nritems
;
1237 btrfs_block_release(root
, path
->nodes
[0]);
1239 path
->slots
[1] -= 1;
1241 btrfs_block_release(root
, t
);
1242 path
->slots
[0] -= push_items
;
1244 BUG_ON(path
->slots
[0] < 0);
1249 * split the path's leaf in two, making sure there is at least data_size
1250 * available for the resulting leaf level of the path.
1252 * returns 0 if all went well and < 0 on failure.
1254 static int split_leaf(struct btrfs_trans_handle
*trans
, struct btrfs_root
1255 *root
, struct btrfs_key
*ins_key
,
1256 struct btrfs_path
*path
, int data_size
, int extend
)
1258 struct btrfs_buffer
*l_buf
;
1259 struct btrfs_leaf
*l
;
1263 struct btrfs_leaf
*right
;
1264 struct btrfs_buffer
*right_buffer
;
1265 int space_needed
= data_size
+ sizeof(struct btrfs_item
);
1272 int num_doubles
= 0;
1273 struct btrfs_disk_key disk_key
;
1276 space_needed
= data_size
;
1277 /* first try to make some room by pushing left and right */
1278 if (ins_key
->type
!= BTRFS_DIR_ITEM_KEY
) {
1279 wret
= push_leaf_right(trans
, root
, path
, data_size
, 0);
1284 wret
= push_leaf_left(trans
, root
, path
, data_size
, 0);
1288 l_buf
= path
->nodes
[0];
1291 /* did the pushes work? */
1292 if (btrfs_leaf_free_space(root
, l
) >= space_needed
)
1295 if (!path
->nodes
[1]) {
1296 ret
= insert_new_root(trans
, root
, path
, 1);
1302 l_buf
= path
->nodes
[0];
1304 slot
= path
->slots
[0];
1305 nritems
= btrfs_header_nritems(&l
->header
);
1306 mid
= (nritems
+ 1)/ 2;
1308 right_buffer
= btrfs_alloc_free_block(trans
, root
, root
->leafsize
);
1309 right
= &right_buffer
->leaf
;
1310 memset(&right
->header
, 0, sizeof(right
->header
));
1311 btrfs_set_header_bytenr(&right
->header
, right_buffer
->bytenr
);
1312 btrfs_set_header_level(&right
->header
, 0);
1313 btrfs_set_header_owner(&right
->header
, root
->root_key
.objectid
);
1314 btrfs_set_header_generation(&right
->header
, trans
->transid
);
1315 memcpy(right
->header
.fsid
, root
->fs_info
->disk_super
->fsid
,
1316 sizeof(right
->header
.fsid
));
1319 leaf_space_used(l
, mid
, nritems
- mid
) + space_needed
>
1320 BTRFS_LEAF_DATA_SIZE(root
)) {
1321 if (slot
>= nritems
) {
1322 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
1323 btrfs_set_header_nritems(&right
->header
, 0);
1324 wret
= insert_ptr(trans
, root
, path
,
1325 &disk_key
, right_buffer
->bytenr
,
1326 path
->slots
[1] + 1, 1);
1329 btrfs_block_release(root
, path
->nodes
[0]);
1330 path
->nodes
[0] = right_buffer
;
1332 path
->slots
[1] += 1;
1336 if (mid
!= nritems
&&
1337 leaf_space_used(l
, mid
, nritems
- mid
) +
1338 space_needed
> BTRFS_LEAF_DATA_SIZE(root
)) {
1343 if (leaf_space_used(l
, 0, mid
) + space_needed
>
1344 BTRFS_LEAF_DATA_SIZE(root
)) {
1345 if (!extend
&& slot
== 0) {
1346 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
1347 btrfs_set_header_nritems(&right
->header
, 0);
1348 wret
= insert_ptr(trans
, root
, path
,
1350 right_buffer
->bytenr
,
1354 btrfs_block_release(root
, path
->nodes
[0]);
1355 path
->nodes
[0] = right_buffer
;
1357 if (path
->slots
[1] == 0) {
1358 wret
= fixup_low_keys(trans
, root
,
1359 path
, &disk_key
, 1);
1364 } else if (extend
&& slot
== 0) {
1368 if (mid
!= nritems
&&
1369 leaf_space_used(l
, mid
, nritems
- mid
) +
1370 space_needed
> BTRFS_LEAF_DATA_SIZE(root
)) {
1376 nritems
= nritems
- mid
;
1377 btrfs_set_header_nritems(&right
->header
, nritems
);
1378 data_copy_size
= btrfs_item_end(l
->items
+ mid
) -
1379 leaf_data_end(root
, l
);
1380 memcpy(right
->items
, l
->items
+ mid
,
1381 nritems
* sizeof(struct btrfs_item
));
1382 memcpy(btrfs_leaf_data(right
) + BTRFS_LEAF_DATA_SIZE(root
) -
1383 data_copy_size
, btrfs_leaf_data(l
) +
1384 leaf_data_end(root
, l
), data_copy_size
);
1385 rt_data_off
= BTRFS_LEAF_DATA_SIZE(root
) -
1386 btrfs_item_end(l
->items
+ mid
);
1387 for (i
= 0; i
< nritems
; i
++) {
1388 u32 ioff
= btrfs_item_offset(right
->items
+ i
);
1389 btrfs_set_item_offset(right
->items
+ i
, ioff
+ rt_data_off
);
1392 btrfs_set_header_nritems(&l
->header
, mid
);
1394 wret
= insert_ptr(trans
, root
, path
, &right
->items
[0].key
,
1395 right_buffer
->bytenr
, path
->slots
[1] + 1, 1);
1399 BUG_ON(list_empty(&right_buffer
->dirty
));
1400 BUG_ON(list_empty(&l_buf
->dirty
));
1401 BUG_ON(path
->slots
[0] != slot
);
1403 btrfs_block_release(root
, path
->nodes
[0]);
1404 path
->nodes
[0] = right_buffer
;
1405 path
->slots
[0] -= mid
;
1406 path
->slots
[1] += 1;
1408 btrfs_block_release(root
, right_buffer
);
1410 BUG_ON(path
->slots
[0] < 0);
1412 BUG_ON(num_doubles
!= 0);
1419 * Given a key and some data, insert an item into the tree.
1420 * This does all the path init required, making room in the tree if needed.
1422 int btrfs_insert_empty_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
1423 *root
, struct btrfs_path
*path
, struct btrfs_key
1424 *cpu_key
, u32 data_size
)
1429 struct btrfs_leaf
*leaf
;
1430 struct btrfs_buffer
*leaf_buf
;
1432 unsigned int data_end
;
1433 struct btrfs_disk_key disk_key
;
1435 btrfs_cpu_key_to_disk(&disk_key
, cpu_key
);
1437 /* create a root if there isn't one */
1440 ret
= btrfs_search_slot(trans
, root
, cpu_key
, path
, data_size
, 1);
1447 slot_orig
= path
->slots
[0];
1448 leaf_buf
= path
->nodes
[0];
1449 leaf
= &leaf_buf
->leaf
;
1451 nritems
= btrfs_header_nritems(&leaf
->header
);
1452 data_end
= leaf_data_end(root
, leaf
);
1454 if (btrfs_leaf_free_space(root
, leaf
) <
1455 sizeof(struct btrfs_item
) + data_size
)
1458 slot
= path
->slots
[0];
1460 if (slot
!= nritems
) {
1462 unsigned int old_data
= btrfs_item_end(leaf
->items
+ slot
);
1465 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1467 /* first correct the data pointers */
1468 for (i
= slot
; i
< nritems
; i
++) {
1469 u32 ioff
= btrfs_item_offset(leaf
->items
+ i
);
1470 btrfs_set_item_offset(leaf
->items
+ i
,
1474 /* shift the items */
1475 memmove(leaf
->items
+ slot
+ 1, leaf
->items
+ slot
,
1476 (nritems
- slot
) * sizeof(struct btrfs_item
));
1478 /* shift the data */
1479 memmove(btrfs_leaf_data(leaf
) + data_end
- data_size
,
1480 btrfs_leaf_data(leaf
) +
1481 data_end
, old_data
- data_end
);
1482 data_end
= old_data
;
1484 /* setup the item for the new data */
1485 memcpy(&leaf
->items
[slot
].key
, &disk_key
,
1486 sizeof(struct btrfs_disk_key
));
1487 btrfs_set_item_offset(leaf
->items
+ slot
, data_end
- data_size
);
1488 btrfs_set_item_size(leaf
->items
+ slot
, data_size
);
1489 btrfs_set_header_nritems(&leaf
->header
, nritems
+ 1);
1493 ret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
1495 BUG_ON(list_empty(&leaf_buf
->dirty
));
1496 if (btrfs_leaf_free_space(root
, leaf
) < 0)
1498 check_leaf(root
, path
, 0);
1504 * Given a key and some data, insert an item into the tree.
1505 * This does all the path init required, making room in the tree if needed.
1507 int btrfs_insert_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
1508 *root
, struct btrfs_key
*cpu_key
, void *data
, u32
1512 struct btrfs_path path
;
1515 btrfs_init_path(&path
);
1516 ret
= btrfs_insert_empty_item(trans
, root
, &path
, cpu_key
, data_size
);
1518 ptr
= btrfs_item_ptr(&path
.nodes
[0]->leaf
, path
.slots
[0], u8
);
1519 memcpy(ptr
, data
, data_size
);
1521 btrfs_release_path(root
, &path
);
1526 * delete the pointer from a given node.
1528 * If the delete empties a node, the node is removed from the tree,
1529 * continuing all the way the root if required. The root is converted into
1530 * a leaf if all the nodes are emptied.
1532 static int del_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
1533 struct btrfs_path
*path
, int level
, int slot
)
1535 struct btrfs_node
*node
;
1536 struct btrfs_buffer
*parent
= path
->nodes
[level
];
1541 node
= &parent
->node
;
1542 nritems
= btrfs_header_nritems(&node
->header
);
1543 if (slot
!= nritems
-1) {
1544 memmove(node
->ptrs
+ slot
, node
->ptrs
+ slot
+ 1,
1545 sizeof(struct btrfs_key_ptr
) * (nritems
- slot
- 1));
1548 btrfs_set_header_nritems(&node
->header
, nritems
);
1549 if (nritems
== 0 && parent
== root
->node
) {
1550 BUG_ON(btrfs_header_level(&root
->node
->node
.header
) != 1);
1551 /* just turn the root into a leaf and break */
1552 btrfs_set_header_level(&root
->node
->node
.header
, 0);
1553 } else if (slot
== 0) {
1554 wret
= fixup_low_keys(trans
, root
, path
, &node
->ptrs
[0].key
,
1559 BUG_ON(list_empty(&parent
->dirty
));
1564 * delete the item at the leaf level in path. If that empties
1565 * the leaf, remove it from the tree
1567 int btrfs_del_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
1568 struct btrfs_path
*path
)
1571 struct btrfs_leaf
*leaf
;
1572 struct btrfs_buffer
*leaf_buf
;
1579 leaf_buf
= path
->nodes
[0];
1580 leaf
= &leaf_buf
->leaf
;
1581 slot
= path
->slots
[0];
1582 doff
= btrfs_item_offset(leaf
->items
+ slot
);
1583 dsize
= btrfs_item_size(leaf
->items
+ slot
);
1584 nritems
= btrfs_header_nritems(&leaf
->header
);
1586 if (slot
!= nritems
- 1) {
1588 int data_end
= leaf_data_end(root
, leaf
);
1589 memmove(btrfs_leaf_data(leaf
) + data_end
+ dsize
,
1590 btrfs_leaf_data(leaf
) + data_end
,
1592 for (i
= slot
+ 1; i
< nritems
; i
++) {
1593 u32 ioff
= btrfs_item_offset(leaf
->items
+ i
);
1594 btrfs_set_item_offset(leaf
->items
+ i
, ioff
+ dsize
);
1596 memmove(leaf
->items
+ slot
, leaf
->items
+ slot
+ 1,
1597 sizeof(struct btrfs_item
) *
1598 (nritems
- slot
- 1));
1600 btrfs_set_header_nritems(&leaf
->header
, nritems
- 1);
1602 /* delete the leaf if we've emptied it */
1604 if (leaf_buf
== root
->node
) {
1605 btrfs_set_header_level(&leaf
->header
, 0);
1606 BUG_ON(list_empty(&leaf_buf
->dirty
));
1609 btrfs_header_generation(&path
->nodes
[1]->node
.header
);
1611 clean_tree_block(trans
, root
, leaf_buf
);
1612 wret
= del_ptr(trans
, root
, path
, 1, path
->slots
[1]);
1615 wret
= btrfs_free_extent(trans
, root
, leaf_buf
->bytenr
,
1617 root
->root_key
.objectid
,
1618 generation
, 0, 0, 1);
1623 int used
= leaf_space_used(leaf
, 0, nritems
);
1625 wret
= fixup_low_keys(trans
, root
, path
,
1626 &leaf
->items
[0].key
, 1);
1630 BUG_ON(list_empty(&leaf_buf
->dirty
));
1632 /* delete the leaf if it is mostly empty */
1633 if (used
< BTRFS_LEAF_DATA_SIZE(root
) / 3) {
1634 /* push_leaf_left fixes the path.
1635 * make sure the path still points to our leaf
1636 * for possible call to del_ptr below
1638 slot
= path
->slots
[1];
1640 wret
= push_leaf_right(trans
, root
, path
, 1, 1);
1643 if (path
->nodes
[0] == leaf_buf
&&
1644 btrfs_header_nritems(&leaf
->header
)) {
1645 wret
= push_leaf_left(trans
, root
, path
, 1, 1);
1649 if (btrfs_header_nritems(&leaf
->header
) == 0) {
1650 u64 bytenr
= leaf_buf
->bytenr
;
1651 struct btrfs_buffer
*parent
= path
->nodes
[1];
1653 btrfs_header_generation(&parent
->node
.header
);
1655 clean_tree_block(trans
, root
, leaf_buf
);
1656 wret
= del_ptr(trans
, root
, path
, 1, slot
);
1659 wret
= btrfs_free_extent(trans
, root
, bytenr
,
1661 root
->root_key
.objectid
,
1662 generation
, 0, 0, 1);
1663 btrfs_block_release(root
, leaf_buf
);
1667 btrfs_block_release(root
, leaf_buf
);
1673 int btrfs_truncate_item(struct btrfs_trans_handle
*trans
,
1674 struct btrfs_root
*root
,
1675 struct btrfs_path
*path
,
1676 u32 new_size
, int from_end
)
1681 struct btrfs_leaf
*leaf
;
1682 struct btrfs_item
*item
;
1684 unsigned int data_end
;
1685 unsigned int old_data_start
;
1686 unsigned int old_size
;
1687 unsigned int size_diff
;
1690 slot_orig
= path
->slots
[0];
1691 leaf
= &path
->nodes
[0]->leaf
;
1692 slot
= path
->slots
[0];
1694 old_size
= btrfs_item_size(leaf
->items
+ slot
);
1695 if (old_size
== new_size
)
1698 nritems
= btrfs_header_nritems(&leaf
->header
);
1699 data_end
= leaf_data_end(root
, leaf
);
1701 old_data_start
= btrfs_item_offset(leaf
->items
+ slot
);
1703 size_diff
= old_size
- new_size
;
1706 BUG_ON(slot
>= nritems
);
1709 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1711 /* first correct the data pointers */
1712 for (i
= slot
; i
< nritems
; i
++) {
1714 item
= leaf
->items
+ i
;
1715 ioff
= btrfs_item_offset(item
);
1716 btrfs_set_item_offset(item
, ioff
+ size_diff
);
1719 /* shift the data */
1721 memmove(btrfs_leaf_data(leaf
) + data_end
+ size_diff
,
1722 btrfs_leaf_data(leaf
) + data_end
,
1723 old_data_start
+ new_size
- data_end
);
1725 struct btrfs_disk_key
*disk_key
;
1728 disk_key
= &leaf
->items
[slot
].key
;
1729 if (btrfs_disk_key_type(disk_key
) == BTRFS_EXTENT_DATA_KEY
) {
1731 struct btrfs_file_extent_item
*fi
;
1733 fi
= btrfs_item_ptr(leaf
, slot
,
1734 struct btrfs_file_extent_item
);
1735 fi
= (struct btrfs_file_extent_item
*)(
1736 (unsigned long)fi
- size_diff
);
1738 if (btrfs_file_extent_type(fi
) ==
1739 BTRFS_FILE_EXTENT_INLINE
) {
1740 ptr
= btrfs_item_ptr(leaf
, slot
, char);
1741 memmove(ptr
, (char *)fi
,
1742 offsetof(struct btrfs_file_extent_item
,
1747 memmove(btrfs_leaf_data(leaf
) + data_end
+ size_diff
,
1748 btrfs_leaf_data(leaf
) + data_end
,
1749 old_data_start
- data_end
);
1751 offset
= btrfs_disk_key_offset(disk_key
);
1752 btrfs_set_disk_key_offset(disk_key
, offset
+ size_diff
);
1754 fixup_low_keys(trans
, root
, path
, disk_key
, 1);
1757 item
= leaf
->items
+ slot
;
1758 btrfs_set_item_size(item
, new_size
);
1759 BUG_ON(list_empty(&path
->nodes
[0]->dirty
));
1762 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
1763 btrfs_print_leaf(root
, leaf
);
1769 int btrfs_extend_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
1770 *root
, struct btrfs_path
*path
, u32 data_size
)
1775 struct btrfs_leaf
*leaf
;
1776 struct btrfs_buffer
*leaf_buf
;
1778 unsigned int data_end
;
1779 unsigned int old_data
;
1780 unsigned int old_size
;
1783 slot_orig
= path
->slots
[0];
1784 leaf_buf
= path
->nodes
[0];
1785 leaf
= &leaf_buf
->leaf
;
1787 nritems
= btrfs_header_nritems(&leaf
->header
);
1788 data_end
= leaf_data_end(root
, leaf
);
1790 if (btrfs_leaf_free_space(root
, leaf
) < data_size
)
1792 slot
= path
->slots
[0];
1793 old_data
= btrfs_item_end(leaf
->items
+ slot
);
1796 BUG_ON(slot
>= nritems
);
1799 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1801 /* first correct the data pointers */
1802 for (i
= slot
; i
< nritems
; i
++) {
1803 u32 ioff
= btrfs_item_offset(leaf
->items
+ i
);
1804 btrfs_set_item_offset(leaf
->items
+ i
,
1807 /* shift the data */
1808 memmove(btrfs_leaf_data(leaf
) + data_end
- data_size
,
1809 btrfs_leaf_data(leaf
) + data_end
, old_data
- data_end
);
1810 data_end
= old_data
;
1811 old_size
= btrfs_item_size(leaf
->items
+ slot
);
1812 btrfs_set_item_size(leaf
->items
+ slot
, old_size
+ data_size
);
1815 if (btrfs_leaf_free_space(root
, leaf
) < 0)
1817 check_leaf(root
, path
, 0);
1822 * walk up the tree as far as required to find the next leaf.
1823 * returns 0 if it found something or 1 if there are no greater leaves.
1824 * returns < 0 on io errors.
1826 int btrfs_next_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
)
1831 struct btrfs_buffer
*c
;
1832 struct btrfs_buffer
*next
= NULL
;
1834 while(level
< BTRFS_MAX_LEVEL
) {
1835 if (!path
->nodes
[level
])
1837 slot
= path
->slots
[level
] + 1;
1838 c
= path
->nodes
[level
];
1839 if (slot
>= btrfs_header_nritems(&c
->node
.header
)) {
1843 bytenr
= btrfs_node_blockptr(&c
->node
, slot
);
1845 btrfs_block_release(root
, next
);
1846 next
= read_tree_block(root
, bytenr
,
1847 btrfs_level_size(root
, level
- 1));
1850 path
->slots
[level
] = slot
;
1853 c
= path
->nodes
[level
];
1854 btrfs_block_release(root
, c
);
1855 path
->nodes
[level
] = next
;
1856 path
->slots
[level
] = 0;
1859 next
= read_tree_block(root
,
1860 btrfs_node_blockptr(&next
->node
, 0),
1861 btrfs_level_size(root
, level
- 1));
1863 check_leaf(root
, path
, 0);