3 #include "kerncompat.h"
4 #include "radix-tree.h"
7 #include "print-tree.h"
9 static int split_node(struct ctree_root
*root
, struct ctree_path
*path
,
11 static int split_leaf(struct ctree_root
*root
, struct ctree_path
*path
,
13 static int push_node_left(struct ctree_root
*root
, struct tree_buffer
*dst
,
14 struct tree_buffer
*src
);
15 static int balance_node_right(struct ctree_root
*root
,
16 struct tree_buffer
*dst_buf
,
17 struct tree_buffer
*src_buf
);
18 static int del_ptr(struct ctree_root
*root
, struct ctree_path
*path
, int level
,
21 inline void init_path(struct ctree_path
*p
)
23 memset(p
, 0, sizeof(*p
));
26 void release_path(struct ctree_root
*root
, struct ctree_path
*p
)
29 for (i
= 0; i
< MAX_LEVEL
; i
++) {
32 tree_block_release(root
, p
->nodes
[i
]);
34 memset(p
, 0, sizeof(*p
));
37 int btrfs_cow_block(struct ctree_root
*root
,
38 struct tree_buffer
*buf
,
39 struct tree_buffer
*parent
,
41 struct tree_buffer
**cow_ret
)
43 struct tree_buffer
*cow
;
45 if (!list_empty(&buf
->dirty
)) {
49 cow
= alloc_free_block(root
);
50 memcpy(&cow
->node
, &buf
->node
, sizeof(buf
->node
));
51 cow
->node
.header
.blocknr
= cow
->blocknr
;
53 if (buf
== root
->node
) {
56 tree_block_release(root
, buf
);
58 parent
->node
.blockptrs
[parent_slot
] = cow
->blocknr
;
59 BUG_ON(list_empty(&parent
->dirty
));
61 if (0 && root
!= root
->extent_root
&& !is_leaf(cow
->node
.header
.flags
)) {
62 btrfs_inc_ref(root
, cow
);
64 tree_block_release(root
, buf
);
69 * The leaf data grows from end-to-front in the node.
70 * this returns the address of the start of the last item,
71 * which is the stop of the leaf data stack
73 static inline unsigned int leaf_data_end(struct leaf
*leaf
)
75 unsigned int nr
= leaf
->header
.nritems
;
77 return sizeof(leaf
->data
);
78 return leaf
->items
[nr
-1].offset
;
82 * The space between the end of the leaf items and
83 * the start of the leaf data. IOW, how much room
84 * the leaf has left for both items and data
86 int leaf_free_space(struct leaf
*leaf
)
88 int data_end
= leaf_data_end(leaf
);
89 int nritems
= leaf
->header
.nritems
;
90 char *items_end
= (char *)(leaf
->items
+ nritems
+ 1);
91 return (char *)(leaf
->data
+ data_end
) - (char *)items_end
;
95 * compare two keys in a memcmp fashion
97 int comp_keys(struct key
*k1
, struct key
*k2
)
99 if (k1
->objectid
> k2
->objectid
)
101 if (k1
->objectid
< k2
->objectid
)
103 if (k1
->flags
> k2
->flags
)
105 if (k1
->flags
< k2
->flags
)
107 if (k1
->offset
> k2
->offset
)
109 if (k1
->offset
< k2
->offset
)
114 int check_node(struct ctree_path
*path
, int level
)
117 struct node
*parent
= NULL
;
118 struct node
*node
= &path
->nodes
[level
]->node
;
121 if (path
->nodes
[level
+ 1])
122 parent
= &path
->nodes
[level
+ 1]->node
;
123 parent_slot
= path
->slots
[level
+ 1];
124 if (parent
&& node
->header
.nritems
> 0) {
125 struct key
*parent_key
;
126 parent_key
= &parent
->keys
[parent_slot
];
127 BUG_ON(memcmp(parent_key
, node
->keys
, sizeof(struct key
)));
128 BUG_ON(parent
->blockptrs
[parent_slot
] != node
->header
.blocknr
);
130 BUG_ON(node
->header
.nritems
> NODEPTRS_PER_BLOCK
);
131 for (i
= 0; i
< node
->header
.nritems
- 2; i
++) {
132 BUG_ON(comp_keys(&node
->keys
[i
], &node
->keys
[i
+1]) >= 0);
137 int check_leaf(struct ctree_path
*path
, int level
)
140 struct leaf
*leaf
= &path
->nodes
[level
]->leaf
;
141 struct node
*parent
= NULL
;
144 if (path
->nodes
[level
+ 1])
145 parent
= &path
->nodes
[level
+ 1]->node
;
146 parent_slot
= path
->slots
[level
+ 1];
147 if (parent
&& leaf
->header
.nritems
> 0) {
148 struct key
*parent_key
;
149 parent_key
= &parent
->keys
[parent_slot
];
150 BUG_ON(memcmp(parent_key
, &leaf
->items
[0].key
,
151 sizeof(struct key
)));
152 BUG_ON(parent
->blockptrs
[parent_slot
] != leaf
->header
.blocknr
);
154 for (i
= 0; i
< leaf
->header
.nritems
- 2; i
++) {
155 BUG_ON(comp_keys(&leaf
->items
[i
].key
,
156 &leaf
->items
[i
+1].key
) >= 0);
157 BUG_ON(leaf
->items
[i
].offset
!= leaf
->items
[i
+ 1].offset
+
158 leaf
->items
[i
+ 1].size
);
160 BUG_ON(leaf
->items
[i
].offset
+ leaf
->items
[i
].size
!=
164 BUG_ON(leaf_free_space(leaf
) < 0);
168 int check_block(struct ctree_path
*path
, int level
)
171 return check_leaf(path
, level
);
172 return check_node(path
, level
);
176 * search for key in the array p. items p are item_size apart
177 * and there are 'max' items in p
178 * the slot in the array is returned via slot, and it points to
179 * the place where you would insert key if it is not found in
182 * slot may point to max if the key is bigger than all of the keys
184 int generic_bin_search(char *p
, int item_size
, struct key
*key
,
194 mid
= (low
+ high
) / 2;
195 tmp
= (struct key
*)(p
+ mid
* item_size
);
196 ret
= comp_keys(tmp
, key
);
212 * simple bin_search frontend that does the right thing for
215 int bin_search(struct node
*c
, struct key
*key
, int *slot
)
217 if (is_leaf(c
->header
.flags
)) {
218 struct leaf
*l
= (struct leaf
*)c
;
219 return generic_bin_search((void *)l
->items
, sizeof(struct item
),
220 key
, c
->header
.nritems
, slot
);
222 return generic_bin_search((void *)c
->keys
, sizeof(struct key
),
223 key
, c
->header
.nritems
, slot
);
228 struct tree_buffer
*read_node_slot(struct ctree_root
*root
,
229 struct tree_buffer
*parent_buf
,
232 struct node
*node
= &parent_buf
->node
;
235 if (slot
>= node
->header
.nritems
)
237 return read_tree_block(root
, node
->blockptrs
[slot
]);
240 static int balance_level(struct ctree_root
*root
, struct ctree_path
*path
,
243 struct tree_buffer
*right_buf
;
244 struct tree_buffer
*mid_buf
;
245 struct tree_buffer
*left_buf
;
246 struct tree_buffer
*parent_buf
= NULL
;
247 struct node
*right
= NULL
;
249 struct node
*left
= NULL
;
250 struct node
*parent
= NULL
;
254 int orig_slot
= path
->slots
[level
];
260 mid_buf
= path
->nodes
[level
];
261 mid
= &mid_buf
->node
;
262 orig_ptr
= mid
->blockptrs
[orig_slot
];
264 if (level
< MAX_LEVEL
- 1)
265 parent_buf
= path
->nodes
[level
+ 1];
266 pslot
= path
->slots
[level
+ 1];
269 struct tree_buffer
*child
;
270 u64 blocknr
= mid_buf
->blocknr
;
272 if (mid
->header
.nritems
!= 1)
275 /* promote the child to a root */
276 child
= read_node_slot(root
, mid_buf
, 0);
279 path
->nodes
[level
] = NULL
;
280 /* once for the path */
281 tree_block_release(root
, mid_buf
);
282 /* once for the root ptr */
283 tree_block_release(root
, mid_buf
);
284 clean_tree_block(root
, mid_buf
);
285 return free_extent(root
, blocknr
, 1);
287 parent
= &parent_buf
->node
;
289 if (mid
->header
.nritems
> NODEPTRS_PER_BLOCK
/ 4)
292 left_buf
= read_node_slot(root
, parent_buf
, pslot
- 1);
293 right_buf
= read_node_slot(root
, parent_buf
, pslot
+ 1);
295 /* first, try to make some room in the middle buffer */
297 btrfs_cow_block(root
, left_buf
, parent_buf
,
298 pslot
- 1, &left_buf
);
299 left
= &left_buf
->node
;
300 orig_slot
+= left
->header
.nritems
;
301 wret
= push_node_left(root
, left_buf
, mid_buf
);
307 * then try to empty the right most buffer into the middle
310 btrfs_cow_block(root
, right_buf
, parent_buf
,
311 pslot
+ 1, &right_buf
);
312 right
= &right_buf
->node
;
313 wret
= push_node_left(root
, mid_buf
, right_buf
);
316 if (right
->header
.nritems
== 0) {
317 u64 blocknr
= right_buf
->blocknr
;
318 tree_block_release(root
, right_buf
);
319 clean_tree_block(root
, right_buf
);
322 wret
= del_ptr(root
, path
, level
+ 1, pslot
+ 1);
325 wret
= free_extent(root
, blocknr
, 1);
329 memcpy(parent
->keys
+ pslot
+ 1, right
->keys
,
331 BUG_ON(list_empty(&parent_buf
->dirty
));
334 if (mid
->header
.nritems
== 1) {
336 * we're not allowed to leave a node with one item in the
337 * tree during a delete. A deletion from lower in the tree
338 * could try to delete the only pointer in this node.
339 * So, pull some keys from the left.
340 * There has to be a left pointer at this point because
341 * otherwise we would have pulled some pointers from the
345 wret
= balance_node_right(root
, mid_buf
, left_buf
);
350 if (mid
->header
.nritems
== 0) {
351 /* we've managed to empty the middle node, drop it */
352 u64 blocknr
= mid_buf
->blocknr
;
353 tree_block_release(root
, mid_buf
);
354 clean_tree_block(root
, mid_buf
);
357 wret
= del_ptr(root
, path
, level
+ 1, pslot
);
360 wret
= free_extent(root
, blocknr
, 1);
364 /* update the parent key to reflect our changes */
365 memcpy(parent
->keys
+ pslot
, mid
->keys
, sizeof(struct key
));
366 BUG_ON(list_empty(&parent_buf
->dirty
));
369 /* update the path */
371 if (left
->header
.nritems
> orig_slot
) {
372 left_buf
->count
++; // released below
373 path
->nodes
[level
] = left_buf
;
374 path
->slots
[level
+ 1] -= 1;
375 path
->slots
[level
] = orig_slot
;
377 tree_block_release(root
, mid_buf
);
379 orig_slot
-= left
->header
.nritems
;
380 path
->slots
[level
] = orig_slot
;
383 /* double check we haven't messed things up */
384 check_block(path
, level
);
385 if (orig_ptr
!= path
->nodes
[level
]->node
.blockptrs
[path
->slots
[level
]])
389 tree_block_release(root
, right_buf
);
391 tree_block_release(root
, left_buf
);
396 * look for key in the tree. path is filled in with nodes along the way
397 * if key is found, we return zero and you can find the item in the leaf
398 * level of the path (level 0)
400 * If the key isn't found, the path points to the slot where it should
401 * be inserted, and 1 is returned. If there are other errors during the
402 * search a negative error number is returned.
404 * if ins_len > 0, nodes and leaves will be split as we walk down the
405 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
408 int search_slot(struct ctree_root
*root
, struct key
*key
,
409 struct ctree_path
*p
, int ins_len
, int cow
)
411 struct tree_buffer
*b
;
412 struct tree_buffer
*cow_buf
;
422 level
= node_level(b
->node
.header
.flags
);
425 wret
= btrfs_cow_block(root
, b
, p
->nodes
[level
+ 1],
426 p
->slots
[level
+ 1], &cow_buf
);
429 BUG_ON(!cow
&& ins_len
);
432 ret
= check_block(p
, level
);
435 ret
= bin_search(c
, key
, &slot
);
436 if (!is_leaf(c
->header
.flags
)) {
439 p
->slots
[level
] = slot
;
441 c
->header
.nritems
== NODEPTRS_PER_BLOCK
) {
442 int sret
= split_node(root
, p
, level
);
448 slot
= p
->slots
[level
];
449 } else if (ins_len
< 0) {
450 int sret
= balance_level(root
, p
, level
);
457 slot
= p
->slots
[level
];
458 BUG_ON(c
->header
.nritems
== 1);
460 b
= read_tree_block(root
, c
->blockptrs
[slot
]);
462 struct leaf
*l
= (struct leaf
*)c
;
463 p
->slots
[level
] = slot
;
464 if (ins_len
> 0 && leaf_free_space(l
) <
465 sizeof(struct item
) + ins_len
) {
466 int sret
= split_leaf(root
, p
, ins_len
);
471 BUG_ON(root
->node
->count
== 1);
475 BUG_ON(root
->node
->count
== 1);
480 * adjust the pointers going up the tree, starting at level
481 * making sure the right key of each node is points to 'key'.
482 * This is used after shifting pointers to the left, so it stops
483 * fixing up pointers when a given leaf/node is not in slot 0 of the
486 * If this fails to write a tree block, it returns -1, but continues
487 * fixing up the blocks in ram so the tree is consistent.
489 static int fixup_low_keys(struct ctree_root
*root
,
490 struct ctree_path
*path
, struct key
*key
,
495 for (i
= level
; i
< MAX_LEVEL
; i
++) {
497 int tslot
= path
->slots
[i
];
500 t
= &path
->nodes
[i
]->node
;
501 memcpy(t
->keys
+ tslot
, key
, sizeof(*key
));
502 BUG_ON(list_empty(&path
->nodes
[i
]->dirty
));
510 * try to push data from one node into the next node left in the
513 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
514 * error, and > 0 if there was no room in the left hand block.
516 static int push_node_left(struct ctree_root
*root
, struct tree_buffer
*dst_buf
,
517 struct tree_buffer
*src_buf
)
519 struct node
*src
= &src_buf
->node
;
520 struct node
*dst
= &dst_buf
->node
;
526 src_nritems
= src
->header
.nritems
;
527 dst_nritems
= dst
->header
.nritems
;
528 push_items
= NODEPTRS_PER_BLOCK
- dst_nritems
;
529 if (push_items
<= 0) {
533 if (src_nritems
< push_items
)
534 push_items
= src_nritems
;
536 memcpy(dst
->keys
+ dst_nritems
, src
->keys
,
537 push_items
* sizeof(struct key
));
538 memcpy(dst
->blockptrs
+ dst_nritems
, src
->blockptrs
,
539 push_items
* sizeof(u64
));
540 if (push_items
< src_nritems
) {
541 memmove(src
->keys
, src
->keys
+ push_items
,
542 (src_nritems
- push_items
) * sizeof(struct key
));
543 memmove(src
->blockptrs
, src
->blockptrs
+ push_items
,
544 (src_nritems
- push_items
) * sizeof(u64
));
546 src
->header
.nritems
-= push_items
;
547 dst
->header
.nritems
+= push_items
;
549 BUG_ON(list_empty(&src_buf
->dirty
));
550 BUG_ON(list_empty(&dst_buf
->dirty
));
555 * try to push data from one node into the next node right in the
558 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
559 * error, and > 0 if there was no room in the right hand block.
561 * this will only push up to 1/2 the contents of the left node over
563 static int balance_node_right(struct ctree_root
*root
,
564 struct tree_buffer
*dst_buf
,
565 struct tree_buffer
*src_buf
)
567 struct node
*src
= &src_buf
->node
;
568 struct node
*dst
= &dst_buf
->node
;
575 src_nritems
= src
->header
.nritems
;
576 dst_nritems
= dst
->header
.nritems
;
577 push_items
= NODEPTRS_PER_BLOCK
- dst_nritems
;
578 if (push_items
<= 0) {
582 max_push
= src_nritems
/ 2 + 1;
583 /* don't try to empty the node */
584 if (max_push
> src_nritems
)
586 if (max_push
< push_items
)
587 push_items
= max_push
;
589 memmove(dst
->keys
+ push_items
, dst
->keys
,
590 dst_nritems
* sizeof(struct key
));
591 memmove(dst
->blockptrs
+ push_items
, dst
->blockptrs
,
592 dst_nritems
* sizeof(u64
));
593 memcpy(dst
->keys
, src
->keys
+ src_nritems
- push_items
,
594 push_items
* sizeof(struct key
));
595 memcpy(dst
->blockptrs
, src
->blockptrs
+ src_nritems
- push_items
,
596 push_items
* sizeof(u64
));
598 src
->header
.nritems
-= push_items
;
599 dst
->header
.nritems
+= push_items
;
601 BUG_ON(list_empty(&src_buf
->dirty
));
602 BUG_ON(list_empty(&dst_buf
->dirty
));
607 * helper function to insert a new root level in the tree.
608 * A new node is allocated, and a single item is inserted to
609 * point to the existing root
611 * returns zero on success or < 0 on failure.
613 static int insert_new_root(struct ctree_root
*root
,
614 struct ctree_path
*path
, int level
)
616 struct tree_buffer
*t
;
619 struct key
*lower_key
;
621 BUG_ON(path
->nodes
[level
]);
622 BUG_ON(path
->nodes
[level
-1] != root
->node
);
624 t
= alloc_free_block(root
);
626 memset(c
, 0, sizeof(c
));
627 c
->header
.nritems
= 1;
628 c
->header
.flags
= node_level(level
);
629 c
->header
.blocknr
= t
->blocknr
;
630 c
->header
.parentid
= root
->node
->node
.header
.parentid
;
631 lower
= &path
->nodes
[level
-1]->node
;
632 if (is_leaf(lower
->header
.flags
))
633 lower_key
= &((struct leaf
*)lower
)->items
[0].key
;
635 lower_key
= lower
->keys
;
636 memcpy(c
->keys
, lower_key
, sizeof(struct key
));
637 c
->blockptrs
[0] = path
->nodes
[level
-1]->blocknr
;
638 /* the super has an extra ref to root->node */
639 tree_block_release(root
, root
->node
);
642 path
->nodes
[level
] = t
;
643 path
->slots
[level
] = 0;
648 * worker function to insert a single pointer in a node.
649 * the node should have enough room for the pointer already
651 * slot and level indicate where you want the key to go, and
652 * blocknr is the block the key points to.
654 * returns zero on success and < 0 on any error
656 static int insert_ptr(struct ctree_root
*root
,
657 struct ctree_path
*path
, struct key
*key
,
658 u64 blocknr
, int slot
, int level
)
663 BUG_ON(!path
->nodes
[level
]);
664 lower
= &path
->nodes
[level
]->node
;
665 nritems
= lower
->header
.nritems
;
668 if (nritems
== NODEPTRS_PER_BLOCK
)
670 if (slot
!= nritems
) {
671 memmove(lower
->keys
+ slot
+ 1, lower
->keys
+ slot
,
672 (nritems
- slot
) * sizeof(struct key
));
673 memmove(lower
->blockptrs
+ slot
+ 1, lower
->blockptrs
+ slot
,
674 (nritems
- slot
) * sizeof(u64
));
676 memcpy(lower
->keys
+ slot
, key
, sizeof(struct key
));
677 lower
->blockptrs
[slot
] = blocknr
;
678 lower
->header
.nritems
++;
679 if (lower
->keys
[1].objectid
== 0)
681 BUG_ON(list_empty(&path
->nodes
[level
]->dirty
));
686 * split the node at the specified level in path in two.
687 * The path is corrected to point to the appropriate node after the split
689 * Before splitting this tries to make some room in the node by pushing
690 * left and right, if either one works, it returns right away.
692 * returns 0 on success and < 0 on failure
694 static int split_node(struct ctree_root
*root
, struct ctree_path
*path
,
697 struct tree_buffer
*t
;
699 struct tree_buffer
*split_buffer
;
705 t
= path
->nodes
[level
];
707 if (t
== root
->node
) {
708 /* trying to split the root, lets make a new one */
709 ret
= insert_new_root(root
, path
, level
+ 1);
713 split_buffer
= alloc_free_block(root
);
714 split
= &split_buffer
->node
;
715 split
->header
.flags
= c
->header
.flags
;
716 split
->header
.blocknr
= split_buffer
->blocknr
;
717 split
->header
.parentid
= root
->node
->node
.header
.parentid
;
718 mid
= (c
->header
.nritems
+ 1) / 2;
719 memcpy(split
->keys
, c
->keys
+ mid
,
720 (c
->header
.nritems
- mid
) * sizeof(struct key
));
721 memcpy(split
->blockptrs
, c
->blockptrs
+ mid
,
722 (c
->header
.nritems
- mid
) * sizeof(u64
));
723 split
->header
.nritems
= c
->header
.nritems
- mid
;
724 c
->header
.nritems
= mid
;
727 BUG_ON(list_empty(&t
->dirty
));
728 wret
= insert_ptr(root
, path
, split
->keys
, split_buffer
->blocknr
,
729 path
->slots
[level
+ 1] + 1, level
+ 1);
733 if (path
->slots
[level
] >= mid
) {
734 path
->slots
[level
] -= mid
;
735 tree_block_release(root
, t
);
736 path
->nodes
[level
] = split_buffer
;
737 path
->slots
[level
+ 1] += 1;
739 tree_block_release(root
, split_buffer
);
745 * how many bytes are required to store the items in a leaf. start
746 * and nr indicate which items in the leaf to check. This totals up the
747 * space used both by the item structs and the item data
749 static int leaf_space_used(struct leaf
*l
, int start
, int nr
)
752 int end
= start
+ nr
- 1;
756 data_len
= l
->items
[start
].offset
+ l
->items
[start
].size
;
757 data_len
= data_len
- l
->items
[end
].offset
;
758 data_len
+= sizeof(struct item
) * nr
;
763 * push some data in the path leaf to the right, trying to free up at
764 * least data_size bytes. returns zero if the push worked, nonzero otherwise
766 * returns 1 if the push failed because the other node didn't have enough
767 * room, 0 if everything worked out and < 0 if there were major errors.
769 static int push_leaf_right(struct ctree_root
*root
, struct ctree_path
*path
,
772 struct tree_buffer
*left_buf
= path
->nodes
[0];
773 struct leaf
*left
= &left_buf
->leaf
;
775 struct tree_buffer
*right_buf
;
776 struct tree_buffer
*upper
;
784 slot
= path
->slots
[1];
785 if (!path
->nodes
[1]) {
788 upper
= path
->nodes
[1];
789 if (slot
>= upper
->node
.header
.nritems
- 1) {
792 right_buf
= read_tree_block(root
, upper
->node
.blockptrs
[slot
+ 1]);
793 right
= &right_buf
->leaf
;
794 free_space
= leaf_free_space(right
);
795 if (free_space
< data_size
+ sizeof(struct item
)) {
796 tree_block_release(root
, right_buf
);
799 /* cow and double check */
800 btrfs_cow_block(root
, right_buf
, upper
, slot
+ 1, &right_buf
);
801 right
= &right_buf
->leaf
;
802 free_space
= leaf_free_space(right
);
803 if (free_space
< data_size
+ sizeof(struct item
)) {
804 tree_block_release(root
, right_buf
);
808 for (i
= left
->header
.nritems
- 1; i
>= 0; i
--) {
809 item
= left
->items
+ i
;
810 if (path
->slots
[0] == i
)
811 push_space
+= data_size
+ sizeof(*item
);
812 if (item
->size
+ sizeof(*item
) + push_space
> free_space
)
815 push_space
+= item
->size
+ sizeof(*item
);
817 if (push_items
== 0) {
818 tree_block_release(root
, right_buf
);
821 /* push left to right */
822 push_space
= left
->items
[left
->header
.nritems
- push_items
].offset
+
823 left
->items
[left
->header
.nritems
- push_items
].size
;
824 push_space
-= leaf_data_end(left
);
825 /* make room in the right data area */
826 memmove(right
->data
+ leaf_data_end(right
) - push_space
,
827 right
->data
+ leaf_data_end(right
),
828 LEAF_DATA_SIZE
- leaf_data_end(right
));
829 /* copy from the left data area */
830 memcpy(right
->data
+ LEAF_DATA_SIZE
- push_space
,
831 left
->data
+ leaf_data_end(left
),
833 memmove(right
->items
+ push_items
, right
->items
,
834 right
->header
.nritems
* sizeof(struct item
));
835 /* copy the items from left to right */
836 memcpy(right
->items
, left
->items
+ left
->header
.nritems
- push_items
,
837 push_items
* sizeof(struct item
));
839 /* update the item pointers */
840 right
->header
.nritems
+= push_items
;
841 push_space
= LEAF_DATA_SIZE
;
842 for (i
= 0; i
< right
->header
.nritems
; i
++) {
843 right
->items
[i
].offset
= push_space
- right
->items
[i
].size
;
844 push_space
= right
->items
[i
].offset
;
846 left
->header
.nritems
-= push_items
;
848 BUG_ON(list_empty(&left_buf
->dirty
));
849 BUG_ON(list_empty(&right_buf
->dirty
));
850 memcpy(upper
->node
.keys
+ slot
+ 1,
851 &right
->items
[0].key
, sizeof(struct key
));
852 BUG_ON(list_empty(&upper
->dirty
));
854 /* then fixup the leaf pointer in the path */
855 if (path
->slots
[0] >= left
->header
.nritems
) {
856 path
->slots
[0] -= left
->header
.nritems
;
857 tree_block_release(root
, path
->nodes
[0]);
858 path
->nodes
[0] = right_buf
;
861 tree_block_release(root
, right_buf
);
866 * push some data in the path leaf to the left, trying to free up at
867 * least data_size bytes. returns zero if the push worked, nonzero otherwise
869 static int push_leaf_left(struct ctree_root
*root
, struct ctree_path
*path
,
872 struct tree_buffer
*right_buf
= path
->nodes
[0];
873 struct leaf
*right
= &right_buf
->leaf
;
874 struct tree_buffer
*t
;
882 int old_left_nritems
;
886 slot
= path
->slots
[1];
890 if (!path
->nodes
[1]) {
893 t
= read_tree_block(root
, path
->nodes
[1]->node
.blockptrs
[slot
- 1]);
895 free_space
= leaf_free_space(left
);
896 if (free_space
< data_size
+ sizeof(struct item
)) {
897 tree_block_release(root
, t
);
901 /* cow and double check */
902 btrfs_cow_block(root
, t
, path
->nodes
[1], slot
- 1, &t
);
904 free_space
= leaf_free_space(left
);
905 if (free_space
< data_size
+ sizeof(struct item
)) {
906 tree_block_release(root
, t
);
910 for (i
= 0; i
< right
->header
.nritems
; i
++) {
911 item
= right
->items
+ i
;
912 if (path
->slots
[0] == i
)
913 push_space
+= data_size
+ sizeof(*item
);
914 if (item
->size
+ sizeof(*item
) + push_space
> free_space
)
917 push_space
+= item
->size
+ sizeof(*item
);
919 if (push_items
== 0) {
920 tree_block_release(root
, t
);
923 /* push data from right to left */
924 memcpy(left
->items
+ left
->header
.nritems
,
925 right
->items
, push_items
* sizeof(struct item
));
926 push_space
= LEAF_DATA_SIZE
- right
->items
[push_items
-1].offset
;
927 memcpy(left
->data
+ leaf_data_end(left
) - push_space
,
928 right
->data
+ right
->items
[push_items
- 1].offset
,
930 old_left_nritems
= left
->header
.nritems
;
931 BUG_ON(old_left_nritems
< 0);
933 for(i
= old_left_nritems
; i
< old_left_nritems
+ push_items
; i
++) {
934 left
->items
[i
].offset
-= LEAF_DATA_SIZE
-
935 left
->items
[old_left_nritems
-1].offset
;
937 left
->header
.nritems
+= push_items
;
939 /* fixup right node */
940 push_space
= right
->items
[push_items
-1].offset
- leaf_data_end(right
);
941 memmove(right
->data
+ LEAF_DATA_SIZE
- push_space
, right
->data
+
942 leaf_data_end(right
), push_space
);
943 memmove(right
->items
, right
->items
+ push_items
,
944 (right
->header
.nritems
- push_items
) * sizeof(struct item
));
945 right
->header
.nritems
-= push_items
;
946 push_space
= LEAF_DATA_SIZE
;
948 for (i
= 0; i
< right
->header
.nritems
; i
++) {
949 right
->items
[i
].offset
= push_space
- right
->items
[i
].size
;
950 push_space
= right
->items
[i
].offset
;
953 BUG_ON(list_empty(&t
->dirty
));
954 BUG_ON(list_empty(&right_buf
->dirty
));
956 wret
= fixup_low_keys(root
, path
, &right
->items
[0].key
, 1);
960 /* then fixup the leaf pointer in the path */
961 if (path
->slots
[0] < push_items
) {
962 path
->slots
[0] += old_left_nritems
;
963 tree_block_release(root
, path
->nodes
[0]);
967 tree_block_release(root
, t
);
968 path
->slots
[0] -= push_items
;
970 BUG_ON(path
->slots
[0] < 0);
975 * split the path's leaf in two, making sure there is at least data_size
976 * available for the resulting leaf level of the path.
978 * returns 0 if all went well and < 0 on failure.
980 static int split_leaf(struct ctree_root
*root
, struct ctree_path
*path
,
983 struct tree_buffer
*l_buf
;
989 struct tree_buffer
*right_buffer
;
990 int space_needed
= data_size
+ sizeof(struct item
);
997 wret
= push_leaf_left(root
, path
, data_size
);
1001 wret
= push_leaf_right(root
, path
, data_size
);
1006 l_buf
= path
->nodes
[0];
1009 /* did the pushes work? */
1010 if (leaf_free_space(l
) >= sizeof(struct item
) + data_size
)
1013 if (!path
->nodes
[1]) {
1014 ret
= insert_new_root(root
, path
, 1);
1018 slot
= path
->slots
[0];
1019 nritems
= l
->header
.nritems
;
1020 mid
= (nritems
+ 1)/ 2;
1022 right_buffer
= alloc_free_block(root
);
1023 BUG_ON(!right_buffer
);
1024 BUG_ON(mid
== nritems
);
1025 right
= &right_buffer
->leaf
;
1026 memset(right
, 0, sizeof(*right
));
1028 /* FIXME, just alloc a new leaf here */
1029 if (leaf_space_used(l
, mid
, nritems
- mid
) + space_needed
>
1033 /* FIXME, just alloc a new leaf here */
1034 if (leaf_space_used(l
, 0, mid
+ 1) + space_needed
>
1038 right
->header
.nritems
= nritems
- mid
;
1039 right
->header
.blocknr
= right_buffer
->blocknr
;
1040 right
->header
.flags
= node_level(0);
1041 right
->header
.parentid
= root
->node
->node
.header
.parentid
;
1042 data_copy_size
= l
->items
[mid
].offset
+ l
->items
[mid
].size
-
1044 memcpy(right
->items
, l
->items
+ mid
,
1045 (nritems
- mid
) * sizeof(struct item
));
1046 memcpy(right
->data
+ LEAF_DATA_SIZE
- data_copy_size
,
1047 l
->data
+ leaf_data_end(l
), data_copy_size
);
1048 rt_data_off
= LEAF_DATA_SIZE
-
1049 (l
->items
[mid
].offset
+ l
->items
[mid
].size
);
1051 for (i
= 0; i
< right
->header
.nritems
; i
++)
1052 right
->items
[i
].offset
+= rt_data_off
;
1054 l
->header
.nritems
= mid
;
1056 wret
= insert_ptr(root
, path
, &right
->items
[0].key
,
1057 right_buffer
->blocknr
, path
->slots
[1] + 1, 1);
1060 BUG_ON(list_empty(&right_buffer
->dirty
));
1061 BUG_ON(list_empty(&l_buf
->dirty
));
1062 BUG_ON(path
->slots
[0] != slot
);
1064 tree_block_release(root
, path
->nodes
[0]);
1065 path
->nodes
[0] = right_buffer
;
1066 path
->slots
[0] -= mid
;
1067 path
->slots
[1] += 1;
1069 tree_block_release(root
, right_buffer
);
1070 BUG_ON(path
->slots
[0] < 0);
1075 * Given a key and some data, insert an item into the tree.
1076 * This does all the path init required, making room in the tree if needed.
1078 int insert_item(struct ctree_root
*root
, struct key
*key
,
1079 void *data
, int data_size
)
1085 struct tree_buffer
*leaf_buf
;
1086 unsigned int nritems
;
1087 unsigned int data_end
;
1088 struct ctree_path path
;
1090 /* create a root if there isn't one */
1094 ret
= search_slot(root
, key
, &path
, data_size
, 1);
1096 release_path(root
, &path
);
1102 slot_orig
= path
.slots
[0];
1103 leaf_buf
= path
.nodes
[0];
1104 leaf
= &leaf_buf
->leaf
;
1106 nritems
= leaf
->header
.nritems
;
1107 data_end
= leaf_data_end(leaf
);
1109 if (leaf_free_space(leaf
) < sizeof(struct item
) + data_size
)
1112 slot
= path
.slots
[0];
1114 if (slot
!= nritems
) {
1116 unsigned int old_data
= leaf
->items
[slot
].offset
+
1117 leaf
->items
[slot
].size
;
1120 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1122 /* first correct the data pointers */
1123 for (i
= slot
; i
< nritems
; i
++)
1124 leaf
->items
[i
].offset
-= data_size
;
1126 /* shift the items */
1127 memmove(leaf
->items
+ slot
+ 1, leaf
->items
+ slot
,
1128 (nritems
- slot
) * sizeof(struct item
));
1130 /* shift the data */
1131 memmove(leaf
->data
+ data_end
- data_size
, leaf
->data
+
1132 data_end
, old_data
- data_end
);
1133 data_end
= old_data
;
1135 /* copy the new data in */
1136 memcpy(&leaf
->items
[slot
].key
, key
, sizeof(struct key
));
1137 leaf
->items
[slot
].offset
= data_end
- data_size
;
1138 leaf
->items
[slot
].size
= data_size
;
1139 memcpy(leaf
->data
+ data_end
- data_size
, data
, data_size
);
1140 leaf
->header
.nritems
+= 1;
1144 ret
= fixup_low_keys(root
, &path
, key
, 1);
1146 BUG_ON(list_empty(&leaf_buf
->dirty
));
1147 if (leaf_free_space(leaf
) < 0)
1149 check_leaf(&path
, 0);
1151 release_path(root
, &path
);
1156 * delete the pointer from a given node.
1158 * If the delete empties a node, the node is removed from the tree,
1159 * continuing all the way the root if required. The root is converted into
1160 * a leaf if all the nodes are emptied.
1162 static int del_ptr(struct ctree_root
*root
, struct ctree_path
*path
, int level
,
1166 struct tree_buffer
*parent
= path
->nodes
[level
];
1171 node
= &parent
->node
;
1172 nritems
= node
->header
.nritems
;
1174 if (slot
!= nritems
-1) {
1175 memmove(node
->keys
+ slot
, node
->keys
+ slot
+ 1,
1176 sizeof(struct key
) * (nritems
- slot
- 1));
1177 memmove(node
->blockptrs
+ slot
,
1178 node
->blockptrs
+ slot
+ 1,
1179 sizeof(u64
) * (nritems
- slot
- 1));
1181 node
->header
.nritems
--;
1182 if (node
->header
.nritems
== 0 && parent
== root
->node
) {
1183 BUG_ON(node_level(root
->node
->node
.header
.flags
) != 1);
1184 /* just turn the root into a leaf and break */
1185 root
->node
->node
.header
.flags
= node_level(0);
1186 } else if (slot
== 0) {
1187 wret
= fixup_low_keys(root
, path
, node
->keys
, level
+ 1);
1191 BUG_ON(list_empty(&parent
->dirty
));
1196 * delete the item at the leaf level in path. If that empties
1197 * the leaf, remove it from the tree
1199 int del_item(struct ctree_root
*root
, struct ctree_path
*path
)
1203 struct tree_buffer
*leaf_buf
;
1209 leaf_buf
= path
->nodes
[0];
1210 leaf
= &leaf_buf
->leaf
;
1211 slot
= path
->slots
[0];
1212 doff
= leaf
->items
[slot
].offset
;
1213 dsize
= leaf
->items
[slot
].size
;
1215 if (slot
!= leaf
->header
.nritems
- 1) {
1217 int data_end
= leaf_data_end(leaf
);
1218 memmove(leaf
->data
+ data_end
+ dsize
,
1219 leaf
->data
+ data_end
,
1221 for (i
= slot
+ 1; i
< leaf
->header
.nritems
; i
++)
1222 leaf
->items
[i
].offset
+= dsize
;
1223 memmove(leaf
->items
+ slot
, leaf
->items
+ slot
+ 1,
1224 sizeof(struct item
) *
1225 (leaf
->header
.nritems
- slot
- 1));
1227 leaf
->header
.nritems
-= 1;
1228 /* delete the leaf if we've emptied it */
1229 if (leaf
->header
.nritems
== 0) {
1230 if (leaf_buf
== root
->node
) {
1231 leaf
->header
.flags
= node_level(0);
1232 BUG_ON(list_empty(&leaf_buf
->dirty
));
1234 clean_tree_block(root
, leaf_buf
);
1235 wret
= del_ptr(root
, path
, 1, path
->slots
[1]);
1238 wret
= free_extent(root
, leaf_buf
->blocknr
, 1);
1243 int used
= leaf_space_used(leaf
, 0, leaf
->header
.nritems
);
1245 wret
= fixup_low_keys(root
, path
,
1246 &leaf
->items
[0].key
, 1);
1250 BUG_ON(list_empty(&leaf_buf
->dirty
));
1252 /* delete the leaf if it is mostly empty */
1253 if (used
< LEAF_DATA_SIZE
/ 3) {
1254 /* push_leaf_left fixes the path.
1255 * make sure the path still points to our leaf
1256 * for possible call to del_ptr below
1258 slot
= path
->slots
[1];
1260 wret
= push_leaf_left(root
, path
, 1);
1263 if (path
->nodes
[0] == leaf_buf
&&
1264 leaf
->header
.nritems
) {
1265 wret
= push_leaf_right(root
, path
, 1);
1269 if (leaf
->header
.nritems
== 0) {
1270 u64 blocknr
= leaf_buf
->blocknr
;
1271 clean_tree_block(root
, leaf_buf
);
1272 wret
= del_ptr(root
, path
, 1, slot
);
1275 tree_block_release(root
, leaf_buf
);
1276 wret
= free_extent(root
, blocknr
, 1);
1280 tree_block_release(root
, leaf_buf
);
1288 * walk up the tree as far as required to find the next leaf.
1289 * returns 0 if it found something or 1 if there are no greater leaves.
1290 * returns < 0 on io errors.
1292 int next_leaf(struct ctree_root
*root
, struct ctree_path
*path
)
1297 struct tree_buffer
*c
;
1298 struct tree_buffer
*next
= NULL
;
1300 while(level
< MAX_LEVEL
) {
1301 if (!path
->nodes
[level
])
1303 slot
= path
->slots
[level
] + 1;
1304 c
= path
->nodes
[level
];
1305 if (slot
>= c
->node
.header
.nritems
) {
1309 blocknr
= c
->node
.blockptrs
[slot
];
1311 tree_block_release(root
, next
);
1312 next
= read_tree_block(root
, blocknr
);
1315 path
->slots
[level
] = slot
;
1318 c
= path
->nodes
[level
];
1319 tree_block_release(root
, c
);
1320 path
->nodes
[level
] = next
;
1321 path
->slots
[level
] = 0;
1324 next
= read_tree_block(root
, next
->node
.blockptrs
[0]);
This page took 0.10394 seconds and 5 git commands to generate.