2 * Copyright (c) 2007 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * $DragonFly: src/sys/vfs/hammer/hammer_btree.c,v 1.17 2008/01/10 07:41:03 dillon Exp $
40 * HAMMER implements a modified B+Tree. In documentation this will
41 * simply be refered to as the HAMMER B-Tree. Basically a B-Tree
42 * looks like a B+Tree (A B-Tree which stores its records only at the leafs
43 * of the tree), but adds two additional boundary elements which describe
44 * the left-most and right-most element a node is able to represent. In
45 * otherwords, we have boundary elements at the two ends of a B-Tree node
46 * instead of sub-tree pointers.
48 * A B-Tree internal node looks like this:
50 * B N N N N N N B <-- boundary and internal elements
51 * S S S S S S S <-- subtree pointers
53 * A B-Tree leaf node basically looks like this:
55 * L L L L L L L L <-- leaf elemenets
57 * The radix for an internal node is 1 less then a leaf but we get a
58 * number of significant benefits for our troubles.
60 * The big benefit to using a B-Tree containing boundary information
61 * is that it is possible to cache pointers into the middle of the tree
62 * and not have to start searches, insertions, OR deletions at the root
63 * node. In particular, searches are able to progress in a definitive
64 * direction from any point in the tree without revisting nodes. This
65 * greatly improves the efficiency of many operations, most especially
68 * B-Trees also make the stacking of trees fairly straightforward.
70 * INTER-CLUSTER ELEMENTS: An element of an internal node may reference
71 * the root of another cluster rather then a node in the current cluster.
72 * This is known as an inter-cluster references. Only B-Tree searches
73 * will cross cluster boundaries. The rebalancing and collapse code does
74 * not attempt to move children between clusters. A major effect of this
75 * is that we have to relax minimum element count requirements and allow
76 * trees to become somewhat unabalanced.
78 * INSERTIONS AND DELETIONS: When inserting we split full nodes on our
79 * way down as an optimization. I originally experimented with rebalancing
80 * nodes on the way down for deletions but it created a huge mess due to
81 * the way inter-cluster linkages work. Instead, now I simply allow
82 * the tree to become unbalanced and allow leaf nodes to become empty.
83 * The delete code will try to clean things up from the bottom-up but
84 * will stop if related elements are not in-core or if it cannot get a node
91 static int btree_search(hammer_cursor_t cursor
, int flags
);
92 static int btree_split_internal(hammer_cursor_t cursor
);
93 static int btree_split_leaf(hammer_cursor_t cursor
);
94 static int btree_remove(hammer_cursor_t cursor
);
95 static int btree_set_parent(hammer_node_t node
, hammer_btree_elm_t elm
);
97 static int btree_rebalance(hammer_cursor_t cursor
);
98 static int btree_collapse(hammer_cursor_t cursor
);
100 static int btree_node_is_full(hammer_node_ondisk_t node
);
101 static void hammer_make_separator(hammer_base_elm_t key1
,
102 hammer_base_elm_t key2
, hammer_base_elm_t dest
);
105 * Iterate records after a search. The cursor is iterated forwards past
106 * the current record until a record matching the key-range requirements
107 * is found. ENOENT is returned if the iteration goes past the ending
110 * The iteration is inclusive of key_beg and can be inclusive or exclusive
111 * of key_end depending on whether HAMMER_CURSOR_END_INCLUSIVE is set.
113 * cursor->key_beg may or may not be modified by this function during
114 * the iteration. XXX future - in case of an inverted lock we may have
115 * to reinitiate the lookup and set key_beg to properly pick up where we
119 hammer_btree_iterate(hammer_cursor_t cursor
)
121 hammer_node_ondisk_t node
;
122 hammer_btree_elm_t elm
;
128 * Skip past the current record
130 node
= cursor
->node
->ondisk
;
133 if (cursor
->index
< node
->count
&&
134 (cursor
->flags
& HAMMER_CURSOR_ATEDISK
)) {
139 * Loop until an element is found or we are done.
143 * We iterate up the tree and then index over one element
144 * while we are at the last element in the current node.
146 * NOTE: This can pop us up to another cluster.
148 * If we are at the root of the root cluster, cursor_up
151 * NOTE: hammer_cursor_up() will adjust cursor->key_beg
152 * when told to re-search for the cluster tag.
154 * XXX this could be optimized by storing the information in
155 * the parent reference.
157 * XXX we can lose the node lock temporarily, this could mess
160 if (cursor
->index
== node
->count
) {
161 error
= hammer_cursor_up(cursor
, 0);
164 node
= cursor
->node
->ondisk
;
165 KKASSERT(cursor
->index
!= node
->count
);
171 * Check internal or leaf element. Determine if the record
172 * at the cursor has gone beyond the end of our range.
174 * Generally we recurse down through internal nodes. An
175 * internal node can only be returned if INCLUSTER is set
176 * and the node represents a cluster-push record. Internal
177 * elements do not contain create_tid/delete_tid information.
179 if (node
->type
== HAMMER_BTREE_TYPE_INTERNAL
) {
180 elm
= &node
->elms
[cursor
->index
];
181 r
= hammer_btree_cmp(&cursor
->key_end
, &elm
[0].base
);
182 s
= hammer_btree_cmp(&cursor
->key_beg
, &elm
[1].base
);
183 if (hammer_debug_btree
) {
184 kprintf("BRACKETL %p:%d %016llx %02x %016llx %d\n",
185 cursor
->node
, cursor
->index
,
186 elm
[0].internal
.base
.obj_id
,
187 elm
[0].internal
.base
.rec_type
,
188 elm
[0].internal
.base
.key
,
191 kprintf("BRACKETR %p:%d %016llx %02x %016llx %d\n",
192 cursor
->node
, cursor
->index
+ 1,
193 elm
[1].internal
.base
.obj_id
,
194 elm
[1].internal
.base
.rec_type
,
195 elm
[1].internal
.base
.key
,
204 if (r
== 0 && (cursor
->flags
& HAMMER_CURSOR_END_INCLUSIVE
) == 0) {
209 if ((cursor
->flags
& HAMMER_CURSOR_INCLUSTER
) == 0 ||
210 elm
->internal
.rec_offset
== 0) {
211 error
= hammer_cursor_down(cursor
);
214 KKASSERT(cursor
->index
== 0);
215 node
= cursor
->node
->ondisk
;
219 elm
= &node
->elms
[cursor
->index
];
220 r
= hammer_btree_cmp(&cursor
->key_end
, &elm
->base
);
221 if (hammer_debug_btree
) {
222 kprintf("ELEMENT %p:%d %016llx %02x %016llx %d\n",
223 cursor
->node
, cursor
->index
,
224 elm
[0].leaf
.base
.obj_id
,
225 elm
[0].leaf
.base
.rec_type
,
226 elm
[0].leaf
.base
.key
,
234 if (r
== 0 && (cursor
->flags
& HAMMER_CURSOR_END_INCLUSIVE
) == 0) {
238 if ((cursor
->flags
& HAMMER_CURSOR_ALLHISTORY
) == 0 &&
239 hammer_btree_chkts(cursor
->key_beg
.create_tid
,
249 if (hammer_debug_btree
) {
250 int i
= cursor
->index
;
251 hammer_btree_elm_t elm
= &cursor
->node
->ondisk
->elms
[i
];
252 kprintf("ITERATE %p:%d %016llx %02x %016llx\n",
254 elm
->internal
.base
.obj_id
,
255 elm
->internal
.base
.rec_type
,
256 elm
->internal
.base
.key
265 * Lookup cursor->key_beg. 0 is returned on success, ENOENT if the entry
266 * could not be found, and a fatal error otherwise.
268 * The cursor is suitably positioned for a deletion on success, and suitably
269 * positioned for an insertion on ENOENT.
271 * The cursor may begin anywhere, the search will traverse clusters in
272 * either direction to locate the requested element.
275 hammer_btree_lookup(hammer_cursor_t cursor
)
279 error
= btree_search(cursor
, 0);
280 if (error
== 0 && cursor
->flags
)
281 error
= hammer_btree_extract(cursor
, cursor
->flags
);
286 * Execute the logic required to start an iteration. The first record
287 * located within the specified range is returned and iteration control
288 * flags are adjusted for successive hammer_btree_iterate() calls.
291 hammer_btree_first(hammer_cursor_t cursor
)
295 error
= hammer_btree_lookup(cursor
);
296 if (error
== ENOENT
) {
297 cursor
->flags
&= ~HAMMER_CURSOR_ATEDISK
;
298 error
= hammer_btree_iterate(cursor
);
300 cursor
->flags
|= HAMMER_CURSOR_ATEDISK
;
305 * Extract the record and/or data associated with the cursor's current
306 * position. Any prior record or data stored in the cursor is replaced.
307 * The cursor must be positioned at a leaf node.
309 * NOTE: Most extractions occur at the leaf of the B-Tree. The only
310 * extraction allowed at an internal element is at a cluster-push.
311 * Cluster-push elements have records but no data.
314 hammer_btree_extract(hammer_cursor_t cursor
, int flags
)
316 hammer_node_ondisk_t node
;
317 hammer_btree_elm_t elm
;
318 hammer_cluster_t cluster
;
325 * A cluster record type has no data reference, the information
326 * is stored directly in the record and B-Tree element.
328 * The case where the data reference resolves to the same buffer
329 * as the record reference must be handled.
331 node
= cursor
->node
->ondisk
;
332 elm
= &node
->elms
[cursor
->index
];
333 cluster
= cursor
->node
->cluster
;
334 cursor
->flags
&= ~HAMMER_CURSOR_DATA_EMBEDDED
;
339 * Internal elements can only be cluster pushes. A cluster push has
342 if (node
->type
== HAMMER_BTREE_TYPE_INTERNAL
) {
343 cloff
= elm
->leaf
.rec_offset
;
344 KKASSERT(cloff
!= 0);
345 cursor
->record
= hammer_bread(cluster
, cloff
,
346 HAMMER_FSBUF_RECORDS
, &error
,
347 &cursor
->record_buffer
);
354 if ((flags
& HAMMER_CURSOR_GET_RECORD
) && error
== 0) {
355 cloff
= elm
->leaf
.rec_offset
;
356 cursor
->record
= hammer_bread(cluster
, cloff
,
357 HAMMER_FSBUF_RECORDS
, &error
,
358 &cursor
->record_buffer
);
362 if ((flags
& HAMMER_CURSOR_GET_DATA
) && error
== 0) {
363 if ((cloff
^ elm
->leaf
.data_offset
) & ~HAMMER_BUFMASK
) {
365 * The data is not in the same buffer as the last
366 * record we cached, but it could still be embedded
367 * in a record. Note that we may not have loaded the
368 * record's buffer above, depending on flags.
370 if ((elm
->leaf
.rec_offset
^ elm
->leaf
.data_offset
) &
372 if (elm
->leaf
.data_len
& HAMMER_BUFMASK
)
373 buf_type
= HAMMER_FSBUF_DATA
;
375 buf_type
= 0; /* pure data buffer */
377 buf_type
= HAMMER_FSBUF_RECORDS
;
379 cursor
->data
= hammer_bread(cluster
,
380 elm
->leaf
.data_offset
,
382 &cursor
->data_buffer
);
385 * Data in same buffer as record. Note that we
386 * leave any existing data_buffer intact, even
387 * though we don't use it in this case, in case
388 * other records extracted during an iteration
391 * The data must be embedded in the record for this
394 * Just assume the buffer type is correct.
396 cursor
->data
= (void *)
397 ((char *)cursor
->record_buffer
->ondisk
+
398 (elm
->leaf
.data_offset
& HAMMER_BUFMASK
));
399 roff
= (char *)cursor
->data
- (char *)cursor
->record
;
400 KKASSERT (roff
>= 0 && roff
< HAMMER_RECORD_SIZE
);
401 cursor
->flags
|= HAMMER_CURSOR_DATA_EMBEDDED
;
409 * Insert a leaf element into the B-Tree at the current cursor position.
410 * The cursor is positioned such that the element at and beyond the cursor
411 * are shifted to make room for the new record.
413 * The caller must call hammer_btree_lookup() with the HAMMER_CURSOR_INSERT
414 * flag set and that call must return ENOENT before this function can be
417 * ENOSPC is returned if there is no room to insert a new record.
420 hammer_btree_insert(hammer_cursor_t cursor
, hammer_btree_elm_t elm
)
422 hammer_node_ondisk_t parent
;
423 hammer_node_ondisk_t node
;
427 /* HANDLED BY CALLER */
429 * Issue a search to get our cursor at the right place. The search
430 * will get us to a leaf node.
432 * The search also does some setup for our insert, so there is always
435 error
= btree_search(cursor
, HAMMER_CURSOR_INSERT
);
436 if (error
!= ENOENT
) {
444 * Insert the element at the leaf node and update the count in the
445 * parent. It is possible for parent to be NULL, indicating that
446 * the root of the B-Tree in the cluster is a leaf. It is also
447 * possible for the leaf to be empty.
449 * Remember that the right-hand boundary is not included in the
452 hammer_modify_node(cursor
->node
);
453 node
= cursor
->node
->ondisk
;
455 KKASSERT(node
->type
== HAMMER_BTREE_TYPE_LEAF
);
456 KKASSERT(node
->count
< HAMMER_BTREE_LEAF_ELMS
);
457 if (i
!= node
->count
) {
458 bcopy(&node
->elms
[i
], &node
->elms
[i
+1],
459 (node
->count
- i
) * sizeof(*elm
));
461 node
->elms
[i
] = *elm
;
464 KKASSERT(hammer_btree_cmp(cursor
->left_bound
, &elm
->leaf
.base
) <= 0);
465 KKASSERT(hammer_btree_cmp(cursor
->right_bound
, &elm
->leaf
.base
) > 0);
467 KKASSERT(hammer_btree_cmp(&node
->elms
[i
-1].leaf
.base
, &elm
->leaf
.base
) < 0);
468 if (i
!= node
->count
- 1)
469 KKASSERT(hammer_btree_cmp(&node
->elms
[i
+1].leaf
.base
, &elm
->leaf
.base
) > 0);
472 * Adjust the sub-tree count in the parent. note that the parent
473 * may be in a different cluster.
475 if (cursor
->parent
) {
476 hammer_modify_node(cursor
->parent
);
477 parent
= cursor
->parent
->ondisk
;
478 i
= cursor
->parent_index
;
479 ++parent
->elms
[i
].internal
.subtree_count
;
480 KKASSERT(parent
->elms
[i
].internal
.subtree_count
<= node
->count
);
486 * Delete a record from the B-Tree's at the current cursor position.
487 * The cursor is positioned such that the current element is the one
490 * On return the cursor will be positioned after the deleted element and
491 * MAY point to an internal node. It will be suitable for the continuation
492 * of an iteration but not for an insertion or deletion.
494 * Deletions will attempt to partially rebalance the B-Tree in an upward
495 * direction. It is possible to end up with empty leafs. An empty internal
496 * node is impossible (worst case: it has one element pointing to an empty
500 hammer_btree_delete(hammer_cursor_t cursor
)
502 hammer_node_ondisk_t ondisk
;
504 hammer_node_t parent
;
505 hammer_btree_elm_t elm
;
510 /* HANDLED BY CALLER */
512 * Locate the leaf element to delete. The search is also responsible
513 * for doing some of the rebalancing work on its way down.
515 error
= btree_search(cursor
, HAMMER_CURSOR_DELETE
);
521 * Delete the element from the leaf node.
523 * Remember that leaf nodes do not have boundaries.
526 ondisk
= node
->ondisk
;
529 KKASSERT(ondisk
->type
== HAMMER_BTREE_TYPE_LEAF
);
530 hammer_modify_node(node
);
531 if (i
+ 1 != ondisk
->count
) {
532 bcopy(&ondisk
->elms
[i
+1], &ondisk
->elms
[i
],
533 (ondisk
->count
- i
- 1) * sizeof(ondisk
->elms
[0]));
536 if (cursor
->parent
!= NULL
) {
538 * Adjust parent's notion of the leaf's count. subtree_count
539 * is only approximate, it is allowed to be too small but
540 * never allowed to be too large. Make sure we don't drop
543 parent
= cursor
->parent
;
544 hammer_modify_node(parent
);
545 elm
= &parent
->ondisk
->elms
[cursor
->parent_index
];
546 if (elm
->internal
.subtree_count
)
547 --elm
->internal
.subtree_count
;
548 KKASSERT(elm
->internal
.subtree_count
<= ondisk
->count
);
552 * It is possible, but not desireable, to stop here. If the element
553 * count drops to 0 (which is allowed for a leaf), try recursively
554 * remove the B-Tree node.
556 * XXX rebalancing calls would go here too.
558 * This may reposition the cursor at one of the parent's of the
561 KKASSERT(cursor
->index
<= ondisk
->count
);
562 if (ondisk
->count
== 0) {
563 error
= btree_remove(cursor
);
573 * PRIMAY B-TREE SEARCH SUPPORT PROCEDURE
575 * Search a cluster's B-Tree for cursor->key_beg, return the matching node.
577 * The search can begin ANYWHERE in the B-Tree. As a first step the search
578 * iterates up the tree as necessary to properly position itself prior to
579 * actually doing the sarch.
581 * INSERTIONS: The search will split full nodes and leaves on its way down
582 * and guarentee that the leaf it ends up on is not full. If we run out
583 * of space the search continues to the leaf (to position the cursor for
584 * the spike), but ENOSPC is returned.
586 * XXX this isn't optimal - we really need to just locate the end point and
587 * insert space going up, and if we get a deadlock just release and retry
588 * the operation. Or something like that. The insertion code can transit
589 * multiple clusters and run splits in unnecessary clusters.
591 * DELETIONS: The search will rebalance the tree on its way down. XXX
593 * The search is only guarenteed to end up on a leaf if an error code of 0
594 * is returned, or if inserting and an error code of ENOENT is returned.
595 * Otherwise it can stop at an internal node. On success a search returns
596 * a leaf node unless INCLUSTER is set and the search located a cluster push
597 * node (which is an internal node).
601 btree_search(hammer_cursor_t cursor
, int flags
)
603 hammer_node_ondisk_t node
;
604 hammer_cluster_t cluster
;
605 hammer_btree_elm_t elm
;
611 flags
|= cursor
->flags
;
613 if (hammer_debug_btree
) {
614 kprintf("SEARCH %p:%d %016llx %02x key=%016llx tid=%016llx\n",
615 cursor
->node
, cursor
->index
,
616 cursor
->key_beg
.obj_id
,
617 cursor
->key_beg
.rec_type
,
619 cursor
->key_beg
.create_tid
624 * Move our cursor up the tree until we find a node whos range covers
625 * the key we are trying to locate. This may move us between
628 * The left bound is inclusive, the right bound is non-inclusive.
629 * It is ok to cursor up too far so when cursoring across a cluster
632 * First see if we can skip the whole cluster. hammer_cursor_up()
633 * handles both cases but this way we don't check the cluster
634 * bounds when going up the tree within a cluster.
636 * NOTE: If INCLUSTER is set and we are at the root of the cluster,
637 * hammer_cursor_up() will return ENOENT.
639 cluster
= cursor
->node
->cluster
;
641 hammer_btree_cmp(&cursor
->key_beg
, &cluster
->clu_btree_beg
) < 0 ||
642 hammer_btree_cmp(&cursor
->key_beg
, &cluster
->clu_btree_end
) >= 0) {
643 error
= hammer_cursor_toroot(cursor
);
646 error
= hammer_cursor_up(cursor
, 0);
649 cluster
= cursor
->node
->cluster
;
653 * Deal with normal cursoring within a cluster. The right bound
654 * is non-inclusive. That is, the bounds form a separator.
656 while (hammer_btree_cmp(&cursor
->key_beg
, cursor
->left_bound
) < 0 ||
657 hammer_btree_cmp(&cursor
->key_beg
, cursor
->right_bound
) >= 0) {
658 error
= hammer_cursor_up(cursor
, 0);
664 * We better have ended up with a node somewhere, and our second
665 * while loop had better not have traversed up a cluster.
667 KKASSERT(cursor
->node
!= NULL
&& cursor
->node
->cluster
== cluster
);
670 * If we are inserting we can't start at a full node if the parent
671 * is also full (because there is no way to split the node),
672 * continue running up the tree until we hit the root of the
673 * root cluster or until the requirement is satisfied.
675 * NOTE: These cursor-up's CAN continue to cross cluster boundaries.
677 * XXX as an optimization it should be possible to unbalance the tree
678 * and stop at the root of the current cluster.
680 while ((flags
& HAMMER_CURSOR_INSERT
) && enospc
== 0) {
681 if (btree_node_is_full(cursor
->node
->ondisk
) == 0)
683 if (cursor
->parent
== NULL
)
685 if (cursor
->parent
->ondisk
->count
!= HAMMER_BTREE_INT_ELMS
)
687 error
= hammer_cursor_up(cursor
, 0);
688 /* cluster and node are now may become stale */
692 /* cluster = cursor->node->cluster; not needed until next cluster = */
696 * If we are deleting we can't start at an internal node with only
697 * one element unless it is root, because all of our code assumes
698 * that internal nodes will never be empty. Just do this generally
699 * for both leaf and internal nodes to get better balance.
701 * This handles the case where the cursor is sitting at a leaf and
702 * either the leaf or parent contain an insufficient number of
705 * NOTE: These cursor-up's CAN continue to cross cluster boundaries.
707 * XXX NOTE: Iterations may not set this flag anyway.
709 while (flags
& HAMMER_CURSOR_DELETE
) {
710 if (cursor
->node
->ondisk
->count
> 1)
712 if (cursor
->parent
== NULL
)
714 KKASSERT(cursor
->node
->ondisk
->count
!= 0);
715 error
= hammer_cursor_up(cursor
, 0);
716 /* cluster and node are now may become stale */
724 * Push down through internal nodes to locate the requested key.
726 cluster
= cursor
->node
->cluster
;
727 node
= cursor
->node
->ondisk
;
728 while (node
->type
== HAMMER_BTREE_TYPE_INTERNAL
) {
731 * If we are a the root node and deleting, try to collapse
732 * all of the root's children into the root. This is the
733 * only point where tree depth is reduced.
735 * XXX NOTE: Iterations may not set this flag anyway.
737 if ((flags
& HAMMER_CURSOR_DELETE
) && cursor
->parent
== NULL
) {
738 error
= btree_collapse(cursor
);
739 /* node becomes stale after call */
744 node
= cursor
->node
->ondisk
;
747 * Scan the node to find the subtree index to push down into.
748 * We go one-past, then back-up.
750 * We have a serious issue with the midpoints for internal
751 * nodes when the midpoint bisects two historical records
752 * (where only create_tid is different). Short of iterating
753 * through the record's entire history the only solution is
754 * to calculate a midpoint that isn't a midpoint in that
755 * case. Please see hammer_make_separator() for more
758 for (i
= 0; i
< node
->count
; ++i
) {
759 elm
= &node
->elms
[i
];
760 r
= hammer_btree_cmp(&cursor
->key_beg
, &elm
->base
);
766 * It is possible for the search to terminate at i == 0,
767 * which is to the LEFT of the LEFT boundary but the RIGHT
768 * of the parent's boundary on the left of the sub-tree
769 * element. This case can occur due to deletions (see
772 * When this case occurs an ENOENT return is guarenteed but
773 * if inserting we must still terminate at a leaf. The
774 * solution is to make the node's left boundary inherit the
775 * boundary stored in the parent.
777 * When doing this inheritance some fields in 'base' are
778 * actually related to the internal element's child
779 * specification and not to the key. These have to be
782 * If we terminate at i == count it is still possible to
783 * be to the RIGHT of the RIGHT boundary but still to the
784 * LEFT of the parent's RIGHT boundary. The solution is to
785 * adjust the RIGHT boundary to match the parent. This
786 * case can occur due to deletions (see btree_remove()).
791 if ((flags
& HAMMER_CURSOR_INSERT
) == 0) {
795 hammer_modify_node(cursor
->node
);
796 save
= node
->elms
[0].subtree_type
;
797 node
->elms
[0].base
= *cursor
->left_bound
;
798 node
->elms
[0].subtree_type
= save
;
799 } else if (i
== node
->count
) {
801 * Terminate early if not inserting and the key is
802 * beyond the uncorrected right hand boundary. The
803 * index must be PAST the last element to prevent an
804 * iteration from returning elements to the left of
807 * NOTE: For the case where the right hand boundary
808 * separates two historical records (where only
809 * create_tid differs), we rely on the boundary
810 * being exactly equal to the next record. This
811 * is handled by hammer_make_separator(). If this
812 * were not true we would have to fall through for
815 elm
= &node
->elms
[i
];
816 if ((flags
& HAMMER_CURSOR_INSERT
) == 0) {
817 r
= hammer_btree_cmp(&cursor
->key_beg
,
826 * Correct a right-hand boundary mismatch. The push
827 * index is the last element (i-1).
829 if (hammer_btree_cmp(&elm
->base
,
830 cursor
->right_bound
) != 0) {
831 hammer_modify_node(cursor
->node
);
832 elm
->base
= *cursor
->right_bound
;
837 * The push-down index is now i - 1.
843 if (hammer_debug_btree
) {
844 elm
= &node
->elms
[i
];
845 kprintf("SEARCH-I %p:%d %016llx %02x key=%016llx tid=%016llx\n",
847 elm
->internal
.base
.obj_id
,
848 elm
->internal
.base
.rec_type
,
849 elm
->internal
.base
.key
,
850 elm
->internal
.base
.create_tid
855 * Handle insertion and deletion requirements.
857 * If inserting split full nodes. The split code will
858 * adjust cursor->node and cursor->index if the current
859 * index winds up in the new node.
861 * If we run out of space we set enospc and continue on
862 * to a leaf to provide the spike code with a good point
863 * of entry. Enospc is reset if we cross a cluster boundary.
865 if ((flags
& HAMMER_CURSOR_INSERT
) && enospc
== 0) {
866 if (node
->count
== HAMMER_BTREE_INT_ELMS
) {
867 error
= btree_split_internal(cursor
);
874 * reload stale pointers
877 node
= cursor
->node
->ondisk
;
883 * If deleting rebalance - do not allow the child to have
884 * just one element or we will not be able to delete it.
886 * Neither internal or leaf nodes (except a root-leaf) are
887 * allowed to drop to 0 elements. (XXX - well, leaf nodes
888 * can at the moment).
890 * Our separators may have been reorganized after rebalancing,
891 * so we have to pop back up and rescan.
893 * XXX test for subtree_count < maxelms / 2, minus 1 or 2
896 * XXX NOTE: Iterations may not set this flag anyway.
898 if (flags
& HAMMER_CURSOR_DELETE
) {
899 if (node
->elms
[i
].internal
.subtree_count
<= 1) {
900 error
= btree_rebalance(cursor
);
903 /* cursor->index is invalid after call */
909 * A non-zero rec_offset specifies a cluster push.
910 * If this is a cluster push we reset the enospc flag,
911 * which reenables the insertion code in the new cluster.
912 * This also ensures that if a spike occurs both its node
913 * and its parent will be in the same cluster.
915 * If INCLUSTER is set we terminate at the cluster boundary.
916 * In this case we must determine whether key_beg is within
917 * the cluster's boundary or not. XXX
919 elm
= &node
->elms
[i
];
920 if (elm
->internal
.rec_offset
) {
921 KKASSERT(elm
->subtree_type
==
922 HAMMER_BTREE_TYPE_CLUSTER
);
924 if (flags
& HAMMER_CURSOR_INCLUSTER
) {
925 KKASSERT((flags
& HAMMER_CURSOR_INSERT
) == 0);
926 r
= hammer_btree_cmp(&cursor
->key_beg
,
928 error
= (r
< 0) ? 0 : ENOENT
;
934 * Push down (push into new node, existing node becomes
935 * the parent) and continue the search.
937 error
= hammer_cursor_down(cursor
);
938 /* node and cluster become stale */
941 node
= cursor
->node
->ondisk
;
942 cluster
= cursor
->node
->cluster
;
946 * We are at a leaf, do a linear search of the key array.
948 * On success the index is set to the matching element and 0
951 * On failure the index is set to the insertion point and ENOENT
954 * Boundaries are not stored in leaf nodes, so the index can wind
955 * up to the left of element 0 (index == 0) or past the end of
956 * the array (index == node->count).
958 KKASSERT(node
->count
<= HAMMER_BTREE_LEAF_ELMS
);
960 for (i
= 0; i
< node
->count
; ++i
) {
961 r
= hammer_btree_cmp(&cursor
->key_beg
, &node
->elms
[i
].base
);
964 * Stop if we've flipped past key_beg. This includes a
965 * record whos create_tid is larger then our asof id.
971 * Return an exact match. In this case we have to do special
972 * checks if the only difference in the records is the
973 * create_ts, in order to properly match against our as-of
976 if (r
>= 0 && r
<= 1) {
977 if ((cursor
->flags
& HAMMER_CURSOR_ALLHISTORY
) == 0 &&
978 hammer_btree_chkts(cursor
->key_beg
.create_tid
,
979 &node
->elms
[i
].base
) != 0) {
984 if (hammer_debug_btree
) {
985 kprintf("SEARCH-L %p:%d (SUCCESS)\n",
992 if (hammer_debug_btree
) {
993 kprintf("SEARCH-L %p:%d (FAILED)\n",
998 * No exact match was found, i is now at the insertion point.
1000 * If inserting split a full leaf before returning. This
1001 * may have the side effect of adjusting cursor->node and
1005 if ((flags
& HAMMER_CURSOR_INSERT
) &&
1006 node
->count
== HAMMER_BTREE_LEAF_ELMS
) {
1007 error
= btree_split_leaf(cursor
);
1009 if (error
!= ENOSPC
)
1012 flags
&= ~HAMMER_CURSOR_INSERT
;
1015 * reload stale pointers
1019 node = &cursor->node->internal;
1024 * We reached a leaf but did not find the key we were looking for.
1025 * If this is an insert we will be properly positioned for an insert
1026 * (ENOENT) or spike (ENOSPC) operation.
1028 error
= enospc
? ENOSPC
: ENOENT
;
1034 /************************************************************************
1035 * SPLITTING AND MERGING *
1036 ************************************************************************
1038 * These routines do all the dirty work required to split and merge nodes.
1042 * Split an internal node into two nodes and move the separator at the split
1043 * point to the parent. Note that the parent's parent's element pointing
1044 * to our parent will have an incorrect subtree_count (we don't update it).
1045 * It will be low, which is ok.
1047 * (cursor->node, cursor->index) indicates the element the caller intends
1048 * to push into. We will adjust node and index if that element winds
1049 * up in the split node.
1051 * If we are at the root of a cluster a new root must be created with two
1052 * elements, one pointing to the original root and one pointing to the
1053 * newly allocated split node.
1055 * NOTE! Being at the root of a cluster is different from being at the
1056 * root of the root cluster. cursor->parent will not be NULL and
1057 * cursor->node->ondisk.parent must be tested against 0. Theoretically
1058 * we could propogate the algorithm into the parent and deal with multiple
1059 * 'roots' in the cluster header, but it's easier not to.
1063 btree_split_internal(hammer_cursor_t cursor
)
1065 hammer_node_ondisk_t ondisk
;
1067 hammer_node_t parent
;
1068 hammer_node_t new_node
;
1069 hammer_btree_elm_t elm
;
1070 hammer_btree_elm_t parent_elm
;
1076 const int esize
= sizeof(*elm
);
1079 * We are splitting but elms[split] will be promoted to the parent,
1080 * leaving the right hand node with one less element. If the
1081 * insertion point will be on the left-hand side adjust the split
1082 * point to give the right hand side one additional node.
1084 node
= cursor
->node
;
1085 ondisk
= node
->ondisk
;
1086 split
= (ondisk
->count
+ 1) / 2;
1087 if (cursor
->index
<= split
)
1092 * If we are at the root of the cluster, create a new root node with
1093 * 1 element and split normally. Avoid making major modifications
1094 * until we know the whole operation will work.
1096 * The root of the cluster is different from the root of the root
1097 * cluster. Use the node's on-disk structure's parent offset to
1100 if (ondisk
->parent
== 0) {
1101 parent
= hammer_alloc_btree(node
->cluster
, &error
);
1104 hammer_lock_ex(&parent
->lock
);
1105 hammer_modify_node(parent
);
1106 ondisk
= parent
->ondisk
;
1109 ondisk
->type
= HAMMER_BTREE_TYPE_INTERNAL
;
1110 ondisk
->elms
[0].base
= node
->cluster
->clu_btree_beg
;
1111 ondisk
->elms
[0].internal
.subtree_type
= node
->ondisk
->type
;
1112 ondisk
->elms
[0].internal
.subtree_offset
= node
->node_offset
;
1113 ondisk
->elms
[1].base
= node
->cluster
->clu_btree_end
;
1115 parent_index
= 0; /* index of current node in parent */
1118 parent
= cursor
->parent
;
1119 parent_index
= cursor
->parent_index
;
1120 KKASSERT(parent
->cluster
== node
->cluster
);
1124 * Split node into new_node at the split point.
1126 * B O O O P N N B <-- P = node->elms[split]
1127 * 0 1 2 3 4 5 6 <-- subtree indices
1132 * B O O O B B N N B <--- inner boundary points are 'P'
1136 new_node
= hammer_alloc_btree(node
->cluster
, &error
);
1137 if (new_node
== NULL
) {
1139 hammer_unlock(&parent
->lock
);
1140 parent
->flags
|= HAMMER_NODE_DELETED
;
1141 hammer_rel_node(parent
);
1145 hammer_lock_ex(&new_node
->lock
);
1148 * Create the new node. P becomes the left-hand boundary in the
1149 * new node. Copy the right-hand boundary as well.
1151 * elm is the new separator.
1153 hammer_modify_node(new_node
);
1154 hammer_modify_node(node
);
1155 ondisk
= node
->ondisk
;
1156 elm
= &ondisk
->elms
[split
];
1157 bcopy(elm
, &new_node
->ondisk
->elms
[0],
1158 (ondisk
->count
- split
+ 1) * esize
);
1159 new_node
->ondisk
->count
= ondisk
->count
- split
;
1160 new_node
->ondisk
->parent
= parent
->node_offset
;
1161 new_node
->ondisk
->type
= HAMMER_BTREE_TYPE_INTERNAL
;
1162 KKASSERT(ondisk
->type
== new_node
->ondisk
->type
);
1165 * Cleanup the original node. P becomes the new boundary, its
1166 * subtree_offset was moved to the new node. If we had created
1167 * a new root its parent pointer may have changed.
1169 elm
->internal
.subtree_offset
= 0;
1170 elm
->internal
.rec_offset
= 0;
1171 ondisk
->count
= split
;
1174 * Insert the separator into the parent, fixup the parent's
1175 * reference to the original node, and reference the new node.
1176 * The separator is P.
1178 * Remember that base.count does not include the right-hand boundary.
1180 hammer_modify_node(parent
);
1181 ondisk
= parent
->ondisk
;
1182 KKASSERT(ondisk
->count
!= HAMMER_BTREE_INT_ELMS
);
1183 ondisk
->elms
[parent_index
].internal
.subtree_count
= split
;
1184 parent_elm
= &ondisk
->elms
[parent_index
+1];
1185 bcopy(parent_elm
, parent_elm
+ 1,
1186 (ondisk
->count
- parent_index
) * esize
);
1187 parent_elm
->internal
.base
= elm
->base
; /* separator P */
1188 parent_elm
->internal
.subtree_offset
= new_node
->node_offset
;
1189 parent_elm
->internal
.subtree_count
= new_node
->ondisk
->count
;
1190 parent_elm
->internal
.subtree_type
= new_node
->ondisk
->type
;
1191 parent_elm
->internal
.subtree_vol_no
= 0;
1192 parent_elm
->internal
.rec_offset
= 0;
1196 * The children of new_node need their parent pointer set to new_node.
1198 for (i
= 0; i
< new_node
->ondisk
->count
; ++i
) {
1199 elm
= &new_node
->ondisk
->elms
[i
];
1200 error
= btree_set_parent(new_node
, elm
);
1202 panic("btree_split_internal: btree-fixup problem");
1207 * The cluster's root pointer may have to be updated.
1210 hammer_modify_cluster(node
->cluster
);
1211 node
->cluster
->ondisk
->clu_btree_root
= parent
->node_offset
;
1212 node
->ondisk
->parent
= parent
->node_offset
;
1213 if (cursor
->parent
) {
1214 hammer_unlock(&cursor
->parent
->lock
);
1215 hammer_rel_node(cursor
->parent
);
1217 cursor
->parent
= parent
; /* lock'd and ref'd */
1222 * Ok, now adjust the cursor depending on which element the original
1223 * index was pointing at. If we are >= the split point the push node
1224 * is now in the new node.
1226 * NOTE: If we are at the split point itself we cannot stay with the
1227 * original node because the push index will point at the right-hand
1228 * boundary, which is illegal.
1230 * NOTE: The cursor's parent or parent_index must be adjusted for
1231 * the case where a new parent (new root) was created, and the case
1232 * where the cursor is now pointing at the split node.
1234 if (cursor
->index
>= split
) {
1235 cursor
->parent_index
= parent_index
+ 1;
1236 cursor
->index
-= split
;
1237 hammer_unlock(&cursor
->node
->lock
);
1238 hammer_rel_node(cursor
->node
);
1239 cursor
->node
= new_node
; /* locked and ref'd */
1241 cursor
->parent_index
= parent_index
;
1242 hammer_unlock(&new_node
->lock
);
1243 hammer_rel_node(new_node
);
1247 * Fixup left and right bounds
1249 parent_elm
= &parent
->ondisk
->elms
[cursor
->parent_index
];
1250 cursor
->left_bound
= &parent_elm
[0].internal
.base
;
1251 cursor
->right_bound
= &parent_elm
[1].internal
.base
;
1252 KKASSERT(hammer_btree_cmp(cursor
->left_bound
,
1253 &cursor
->node
->ondisk
->elms
[0].internal
.base
) <= 0);
1254 KKASSERT(hammer_btree_cmp(cursor
->right_bound
,
1255 &cursor
->node
->ondisk
->elms
[cursor
->node
->ondisk
->count
-1].internal
.base
) > 0);
1261 * Same as the above, but splits a full leaf node.
1265 btree_split_leaf(hammer_cursor_t cursor
)
1267 hammer_node_ondisk_t ondisk
;
1268 hammer_node_t parent
;
1270 hammer_node_t new_leaf
;
1271 hammer_btree_elm_t elm
;
1272 hammer_btree_elm_t parent_elm
;
1273 hammer_base_elm_t mid_boundary
;
1278 const size_t esize
= sizeof(*elm
);
1281 * Calculate the split point. If the insertion point will be on
1282 * the left-hand side adjust the split point to give the right
1283 * hand side one additional node.
1285 leaf
= cursor
->node
;
1286 ondisk
= leaf
->ondisk
;
1287 split
= (ondisk
->count
+ 1) / 2;
1288 if (cursor
->index
<= split
)
1293 * If we are at the root of the tree, create a new root node with
1294 * 1 element and split normally. Avoid making major modifications
1295 * until we know the whole operation will work.
1297 if (ondisk
->parent
== 0) {
1298 parent
= hammer_alloc_btree(leaf
->cluster
, &error
);
1301 hammer_lock_ex(&parent
->lock
);
1302 hammer_modify_node(parent
);
1303 ondisk
= parent
->ondisk
;
1306 ondisk
->type
= HAMMER_BTREE_TYPE_INTERNAL
;
1307 ondisk
->elms
[0].base
= leaf
->cluster
->clu_btree_beg
;
1308 ondisk
->elms
[0].internal
.subtree_type
= leaf
->ondisk
->type
;
1309 ondisk
->elms
[0].internal
.subtree_offset
= leaf
->node_offset
;
1310 ondisk
->elms
[1].base
= leaf
->cluster
->clu_btree_end
;
1312 parent_index
= 0; /* insertion point in parent */
1315 parent
= cursor
->parent
;
1316 parent_index
= cursor
->parent_index
;
1317 KKASSERT(parent
->cluster
== leaf
->cluster
);
1321 * Split leaf into new_leaf at the split point. Select a separator
1322 * value in-between the two leafs but with a bent towards the right
1323 * leaf since comparisons use an 'elm >= separator' inequality.
1332 new_leaf
= hammer_alloc_btree(leaf
->cluster
, &error
);
1333 if (new_leaf
== NULL
) {
1335 hammer_unlock(&parent
->lock
);
1336 parent
->flags
|= HAMMER_NODE_DELETED
;
1337 hammer_rel_node(parent
);
1341 hammer_lock_ex(&new_leaf
->lock
);
1344 * Create the new node. P become the left-hand boundary in the
1345 * new node. Copy the right-hand boundary as well.
1347 hammer_modify_node(leaf
);
1348 hammer_modify_node(new_leaf
);
1349 ondisk
= leaf
->ondisk
;
1350 elm
= &ondisk
->elms
[split
];
1351 bcopy(elm
, &new_leaf
->ondisk
->elms
[0], (ondisk
->count
- split
) * esize
);
1352 new_leaf
->ondisk
->count
= ondisk
->count
- split
;
1353 new_leaf
->ondisk
->parent
= parent
->node_offset
;
1354 new_leaf
->ondisk
->type
= HAMMER_BTREE_TYPE_LEAF
;
1355 KKASSERT(ondisk
->type
== new_leaf
->ondisk
->type
);
1358 * Cleanup the original node. Because this is a leaf node and
1359 * leaf nodes do not have a right-hand boundary, there
1360 * aren't any special edge cases to clean up. We just fixup the
1363 ondisk
->count
= split
;
1366 * Insert the separator into the parent, fixup the parent's
1367 * reference to the original node, and reference the new node.
1368 * The separator is P.
1370 * Remember that base.count does not include the right-hand boundary.
1371 * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1373 hammer_modify_node(parent
);
1374 ondisk
= parent
->ondisk
;
1375 KKASSERT(ondisk
->count
!= HAMMER_BTREE_INT_ELMS
);
1376 ondisk
->elms
[parent_index
].internal
.subtree_count
= split
;
1377 parent_elm
= &ondisk
->elms
[parent_index
+1];
1378 bcopy(parent_elm
, parent_elm
+ 1,
1379 (ondisk
->count
- parent_index
) * esize
);
1380 hammer_make_separator(&elm
[-1].base
, &elm
[0].base
, &parent_elm
->base
);
1381 parent_elm
->internal
.subtree_offset
= new_leaf
->node_offset
;
1382 parent_elm
->internal
.subtree_count
= new_leaf
->ondisk
->count
;
1383 parent_elm
->internal
.subtree_type
= new_leaf
->ondisk
->type
;
1384 parent_elm
->internal
.subtree_vol_no
= 0;
1385 parent_elm
->internal
.rec_offset
= 0;
1386 mid_boundary
= &parent_elm
->base
;
1390 * The cluster's root pointer may have to be updated.
1393 hammer_modify_cluster(leaf
->cluster
);
1394 leaf
->cluster
->ondisk
->clu_btree_root
= parent
->node_offset
;
1395 leaf
->ondisk
->parent
= parent
->node_offset
;
1396 if (cursor
->parent
) {
1397 hammer_unlock(&cursor
->parent
->lock
);
1398 hammer_rel_node(cursor
->parent
);
1400 cursor
->parent
= parent
; /* lock'd and ref'd */
1404 * Ok, now adjust the cursor depending on which element the original
1405 * index was pointing at. If we are >= the split point the push node
1406 * is now in the new node.
1408 * NOTE: If we are at the split point itself we need to select the
1409 * old or new node based on where key_beg's insertion point will be.
1410 * If we pick the wrong side the inserted element will wind up in
1411 * the wrong leaf node and outside that node's bounds.
1413 if (cursor
->index
> split
||
1414 (cursor
->index
== split
&&
1415 hammer_btree_cmp(&cursor
->key_beg
, mid_boundary
) >= 0)) {
1416 cursor
->parent_index
= parent_index
+ 1;
1417 cursor
->index
-= split
;
1418 hammer_unlock(&cursor
->node
->lock
);
1419 hammer_rel_node(cursor
->node
);
1420 cursor
->node
= new_leaf
;
1422 cursor
->parent_index
= parent_index
;
1423 hammer_unlock(&new_leaf
->lock
);
1424 hammer_rel_node(new_leaf
);
1428 * Fixup left and right bounds
1430 parent_elm
= &parent
->ondisk
->elms
[cursor
->parent_index
];
1431 cursor
->left_bound
= &parent_elm
[0].internal
.base
;
1432 cursor
->right_bound
= &parent_elm
[1].internal
.base
;
1433 KKASSERT(hammer_btree_cmp(cursor
->left_bound
,
1434 &cursor
->node
->ondisk
->elms
[0].leaf
.base
) <= 0);
1435 KKASSERT(hammer_btree_cmp(cursor
->right_bound
,
1436 &cursor
->node
->ondisk
->elms
[cursor
->node
->ondisk
->count
-1].leaf
.base
) > 0);
1442 * Attempt to remove the empty B-Tree node at (cursor->node). Returns 0
1443 * on success, EAGAIN if we could not acquire the necessary locks, or some
1446 * On return the cursor may end up pointing at an internal node, suitable
1447 * for further iteration but not for an immediate insertion or deletion.
1449 * cursor->node may be an internal node or a leaf node.
1451 * NOTE: If cursor->node has one element it is the parent trying to delete
1452 * that element, make sure cursor->index is properly adjusted on success.
1455 btree_remove(hammer_cursor_t cursor
)
1457 hammer_node_ondisk_t ondisk
;
1458 hammer_btree_elm_t elm
;
1461 hammer_node_t parent
;
1466 * If we are at the root of the root cluster there is nothing to
1467 * remove, but an internal node at the root of a cluster is not
1468 * allowed to be empty so convert it to a leaf node.
1470 if (cursor
->parent
== NULL
) {
1471 hammer_modify_node(cursor
->node
);
1472 ondisk
= cursor
->node
->ondisk
;
1473 KKASSERT(ondisk
->parent
== 0);
1474 ondisk
->type
= HAMMER_BTREE_TYPE_LEAF
;
1477 kprintf("EMPTY ROOT OF ROOT CLUSTER -> LEAF\n");
1482 * Retain a reference to cursor->node, ex-lock again (2 locks now)
1483 * so we do not lose the lock when we cursor around.
1485 save
= cursor
->node
;
1486 hammer_ref_node(save
);
1487 hammer_lock_ex(&save
->lock
);
1490 * We need to be able to lock the parent of the parent. Do this
1491 * non-blocking and return EAGAIN if the lock cannot be acquired.
1492 * non-blocking is required in order to avoid a deadlock.
1494 * After we cursor up, parent is moved to node and the new parent
1495 * is the parent of the parent.
1497 error
= hammer_cursor_up(cursor
, 1);
1499 kprintf("BTREE_REMOVE: Cannot lock parent, skipping\n");
1504 * At this point we want to remove the element at (node, index),
1505 * which is now the (original) parent pointing to the saved node.
1506 * Removing the element allows us to then free the node it was
1509 * However, an internal node is not allowed to have 0 elements, so
1510 * if the count would drop to 0 we have to recurse. It is possible
1511 * for the recursion to fail.
1513 * NOTE: The cursor is in an indeterminant position after recursing,
1514 * but will still be suitable for an iteration.
1516 node
= cursor
->node
;
1517 KKASSERT(node
->ondisk
->count
> 0);
1518 if (node
->ondisk
->count
== 1) {
1519 error
= btree_remove(cursor
);
1521 /*kprintf("BTREE_REMOVE: Successful!\n");*/
1524 kprintf("BTREE_REMOVE: Recursion failed %d\n", error
);
1530 * Remove the element at (node, index) and adjust the parent's
1533 * NOTE! If removing element 0 an internal node's left-hand boundary
1534 * will no longer match its parent. If removing a mid-element the
1535 * boundary will no longer match a child's left hand or right hand
1538 * BxBxBxB remove a (x[0]): internal node's left-hand
1539 * | | | boundary no longer matches
1542 * remove b (x[1]): a's right hand boundary no
1543 * longer matches parent.
1545 * remove c (x[2]): b's right hand boundary no
1546 * longer matches parent.
1548 * These cases are corrected in btree_search().
1551 kprintf("BTREE_REMOVE: Removing element %d\n", cursor
->index
);
1553 KKASSERT(node
->ondisk
->type
== HAMMER_BTREE_TYPE_INTERNAL
);
1554 KKASSERT(cursor
->index
< node
->ondisk
->count
);
1555 hammer_modify_node(node
);
1556 ondisk
= node
->ondisk
;
1558 bcopy(&ondisk
->elms
[i
+1], &ondisk
->elms
[i
],
1559 (ondisk
->count
- i
) * sizeof(ondisk
->elms
[0]));
1563 * Adjust the parent-parent's (now parent) reference to the parent
1566 if ((parent
= cursor
->parent
) != NULL
) {
1567 elm
= &parent
->ondisk
->elms
[cursor
->parent_index
];
1568 if (elm
->internal
.subtree_count
!= ondisk
->count
) {
1569 hammer_modify_node(parent
);
1570 elm
->internal
.subtree_count
= ondisk
->count
;
1572 if (elm
->subtree_type
!= HAMMER_BTREE_TYPE_CLUSTER
&&
1573 elm
->subtree_type
!= ondisk
->type
) {
1574 hammer_modify_node(parent
);
1575 elm
->subtree_type
= ondisk
->type
;
1581 * Free the saved node. If the saved node was the root of a
1582 * cluster, free the entire cluster.
1584 hammer_flush_node(save
);
1585 save
->flags
|= HAMMER_NODE_DELETED
;
1589 hammer_unlock(&save
->lock
);
1590 hammer_rel_node(save
);
1595 * The child represented by the element in internal node node needs
1596 * to have its parent pointer adjusted.
1600 btree_set_parent(hammer_node_t node
, hammer_btree_elm_t elm
)
1602 hammer_volume_t volume
;
1603 hammer_cluster_t cluster
;
1604 hammer_node_t child
;
1609 switch(elm
->internal
.subtree_type
) {
1610 case HAMMER_BTREE_TYPE_LEAF
:
1611 case HAMMER_BTREE_TYPE_INTERNAL
:
1612 child
= hammer_get_node(node
->cluster
,
1613 elm
->internal
.subtree_offset
, &error
);
1615 hammer_modify_node(child
);
1616 hammer_lock_ex(&child
->lock
);
1617 child
->ondisk
->parent
= node
->node_offset
;
1618 hammer_unlock(&child
->lock
);
1619 hammer_rel_node(child
);
1622 case HAMMER_BTREE_TYPE_CLUSTER
:
1623 volume
= hammer_get_volume(node
->cluster
->volume
->hmp
,
1624 elm
->internal
.subtree_vol_no
, &error
);
1627 cluster
= hammer_get_cluster(volume
,
1628 elm
->internal
.subtree_clu_no
,
1630 hammer_rel_volume(volume
, 0);
1633 hammer_modify_cluster(cluster
);
1634 hammer_lock_ex(&cluster
->io
.lock
);
1635 cluster
->ondisk
->clu_btree_parent_offset
= node
->node_offset
;
1636 hammer_unlock(&cluster
->io
.lock
);
1637 KKASSERT(cluster
->ondisk
->clu_btree_parent_clu_no
==
1638 node
->cluster
->clu_no
);
1639 KKASSERT(cluster
->ondisk
->clu_btree_parent_vol_no
==
1640 node
->cluster
->volume
->vol_no
);
1641 hammer_rel_cluster(cluster
, 0);
1644 hammer_print_btree_elm(elm
, HAMMER_BTREE_TYPE_INTERNAL
, -1);
1645 panic("btree_set_parent: bad subtree_type");
1646 break; /* NOT REACHED */
1654 * This routine is only called if the cursor is at the root node and the
1655 * root node is an internal node. We attempt to collapse the root node
1656 * by replacing it with all of its children, reducing tree depth by one.
1658 * This is the only way to reduce tree depth in a HAMMER filesystem.
1659 * Note that all leaf nodes are at the same depth.
1661 * This is a fairly expensive operation because we not only have to load
1662 * the root's children, we also have to scan each child and adjust the
1663 * parent offset for each element in each child. Nasty all around.
1667 btree_collapse(hammer_cursor_t cursor
)
1669 hammer_btree_node_ondisk_t root
, child
;
1670 hammer_btree_node_ondisk_t children
[HAMMER_BTREE_INT_ELMS
];
1671 struct hammer_buffer
*child_buffer
[HAMMER_BTREE_INT_ELMS
];
1676 int32_t root_offset
;
1677 u_int8_t subsubtype
;
1679 root
= cursor
->node
;
1680 count
= root
->base
.count
;
1681 root_offset
= hammer_bclu_offset(cursor
->node_buffer
, root
);
1684 * Sum up the number of children each element has. This value is
1685 * only approximate due to the way the insertion node works. It
1686 * may be too small but it will never be too large.
1688 * Quickly terminate the collapse if the elements have too many
1691 KKASSERT(root
->base
.parent
== 0); /* must be root node */
1692 KKASSERT(root
->base
.type
== HAMMER_BTREE_TYPE_INTERNAL
);
1693 KKASSERT(count
<= HAMMER_BTREE_INT_ELMS
);
1695 for (i
= n
= 0; i
< count
; ++i
) {
1696 n
+= root
->internal
.elms
[i
].subtree_count
;
1698 if (n
> btree_max_elements(root
->base
.subtype
))
1702 * Iterate through the elements again and correct the subtree_count.
1703 * Terminate the collapse if we wind up with too many.
1708 for (i
= n
= 0; i
< count
; ++i
) {
1709 struct hammer_btree_internal_elm
*elm
;
1711 elm
= &root
->internal
.elms
[i
];
1712 child_buffer
[i
] = NULL
;
1714 if (elm
->subtree_offset
== 0)
1716 child
= hammer_bread(cursor
->cluster
, elm
->subtree_offset
,
1717 HAMMER_FSBUF_BTREE
, &error
,
1718 &child_buffer
[i
], XXX
);
1719 children
[i
] = child
;
1722 KKASSERT(root
->base
.subtype
== child
->base
.type
);
1725 * Accumulate n for a good child, update the root's count
1728 if (root
->internal
.elms
[i
].subtree_count
!= child
->base
.count
) {
1729 root
->internal
.elms
[i
].subtree_count
= child
->base
.count
;
1732 n
+= root
->internal
.elms
[i
].subtree_count
;
1734 if (error
|| n
> btree_max_elements(root
->base
.subtype
))
1738 * Ok, we can collapse the root. If the root's children are leafs
1739 * the collapse is really simple. If they are internal nodes the
1740 * collapse is not so simple because we have to fixup the parent
1741 * pointers for the root's children's children.
1743 * When collapsing an internal node the far left and far right
1744 * element's boundaries should match the root's left and right
1747 if (root
->base
.subtype
== HAMMER_BTREE_TYPE_LEAF
) {
1748 for (i
= n
= 0; i
< count
; ++i
) {
1749 child
= children
[i
];
1750 for (j
= 0; j
< child
->base
.count
; ++j
) {
1751 root
->leaf
.elms
[n
] = child
->leaf
.elms
[j
];
1755 root
->base
.type
= root
->base
.subtype
;
1756 root
->base
.subtype
= 0;
1757 root
->base
.count
= n
;
1758 root
->leaf
.link_left
= 0;
1759 root
->leaf
.link_right
= 0;
1761 struct hammer_btree_internal_elm
*elm
;
1762 struct hammer_btree_internal_node
*subchild
;
1763 struct hammer_buffer
*subchild_buffer
= NULL
;
1766 child
= children
[0];
1767 subsubtype
= child
->base
.subtype
;
1768 KKASSERT(child
->base
.count
> 0);
1769 KKASSERT(root
->internal
.elms
[0].base
.key
==
1770 child
->internal
.elms
[0].base
.key
);
1771 child
= children
[count
-1];
1772 KKASSERT(child
->base
.count
> 0);
1773 KKASSERT(root
->internal
.elms
[count
].base
.key
==
1774 child
->internal
.elms
[child
->base
.count
].base
.key
);
1778 for (i
= n
= 0; i
< count
; ++i
) {
1779 child
= children
[i
];
1780 KKASSERT(child
->base
.subtype
== subsubtype
);
1781 for (j
= 0; j
< child
->base
.count
; ++j
) {
1782 elm
= &child
->internal
.elms
[j
];
1784 root
->internal
.elms
[n
] = *elm
;
1785 subchild
= hammer_bread(cursor
->cluster
,
1786 elm
->subtree_offset
,
1792 subchild
->base
.parent
= root_offset
;
1793 hammer_modify_buffer(subchild_buffer
);
1797 /* make sure the right boundary is correct */
1798 /* (this gets overwritten when the loop continues) */
1799 /* XXX generate a new separator? */
1800 root
->internal
.elms
[n
] = child
->internal
.elms
[j
];
1802 root
->base
.type
= HAMMER_BTREE_TYPE_INTERNAL
;
1803 root
->base
.subtype
= subsubtype
;
1804 if (subchild_buffer
)
1805 hammer_put_buffer(subchild_buffer
, 0);
1814 hammer_modify_buffer(cursor
->node_buffer
);
1815 for (i
= 0; i
< count
; ++i
) {
1816 if (child_buffer
[i
])
1817 hammer_put_buffer(child_buffer
[i
], 0);
1824 /************************************************************************
1825 * MISCELLANIOUS SUPPORT *
1826 ************************************************************************/
1829 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
1831 * Note that for this particular function a return value of -1, 0, or +1
1832 * can denote a match if create_tid is otherwise discounted.
1834 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
1837 hammer_btree_cmp(hammer_base_elm_t key1
, hammer_base_elm_t key2
)
1839 if (key1
->obj_id
< key2
->obj_id
)
1841 if (key1
->obj_id
> key2
->obj_id
)
1844 if (key1
->rec_type
< key2
->rec_type
)
1846 if (key1
->rec_type
> key2
->rec_type
)
1849 if (key1
->key
< key2
->key
)
1851 if (key1
->key
> key2
->key
)
1854 if (key1
->create_tid
< key2
->create_tid
)
1856 if (key1
->create_tid
> key2
->create_tid
)
1862 * Test a non-zero timestamp against an element to determine whether the
1863 * element is visible.
1866 hammer_btree_chkts(hammer_tid_t create_tid
, hammer_base_elm_t base
)
1868 if (create_tid
< base
->create_tid
)
1870 if (base
->delete_tid
&& create_tid
>= base
->delete_tid
)
1876 * Create a separator half way inbetween key1 and key2. For fields just
1877 * one unit apart, the separator will match key2.
1879 * At the moment require that the separator never match key2 exactly.
1881 * We have to special case the separator between two historical keys,
1882 * where all elements except create_tid match. In this case our B-Tree
1883 * searches can't figure out which branch of an internal node to go down
1884 * unless the mid point's create_tid is exactly key2.
1885 * (see btree_search()'s scan code on HAMMER_BTREE_TYPE_INTERNAL).
1887 #define MAKE_SEPARATOR(key1, key2, dest, field) \
1888 dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
1891 hammer_make_separator(hammer_base_elm_t key1
, hammer_base_elm_t key2
,
1892 hammer_base_elm_t dest
)
1894 bzero(dest
, sizeof(*dest
));
1895 MAKE_SEPARATOR(key1
, key2
, dest
, obj_id
);
1896 MAKE_SEPARATOR(key1
, key2
, dest
, rec_type
);
1897 MAKE_SEPARATOR(key1
, key2
, dest
, key
);
1898 if (key1
->obj_id
== key2
->obj_id
&&
1899 key1
->rec_type
== key2
->rec_type
&&
1900 key1
->key
== key2
->key
) {
1901 dest
->create_tid
= key2
->create_tid
;
1903 dest
->create_tid
= 0;
1907 #undef MAKE_SEPARATOR
1910 * Return whether a generic internal or leaf node is full
1913 btree_node_is_full(hammer_node_ondisk_t node
)
1915 switch(node
->type
) {
1916 case HAMMER_BTREE_TYPE_INTERNAL
:
1917 if (node
->count
== HAMMER_BTREE_INT_ELMS
)
1920 case HAMMER_BTREE_TYPE_LEAF
:
1921 if (node
->count
== HAMMER_BTREE_LEAF_ELMS
)
1925 panic("illegal btree subtype");
1932 btree_max_elements(u_int8_t type
)
1934 if (type
== HAMMER_BTREE_TYPE_LEAF
)
1935 return(HAMMER_BTREE_LEAF_ELMS
);
1936 if (type
== HAMMER_BTREE_TYPE_INTERNAL
)
1937 return(HAMMER_BTREE_INT_ELMS
);
1938 panic("btree_max_elements: bad type %d\n", type
);
1943 hammer_print_btree_node(hammer_node_ondisk_t ondisk
)
1945 hammer_btree_elm_t elm
;
1948 kprintf("node %p count=%d parent=%d type=%c\n",
1949 ondisk
, ondisk
->count
, ondisk
->parent
, ondisk
->type
);
1952 * Dump both boundary elements if an internal node
1954 if (ondisk
->type
== HAMMER_BTREE_TYPE_INTERNAL
) {
1955 for (i
= 0; i
<= ondisk
->count
; ++i
) {
1956 elm
= &ondisk
->elms
[i
];
1957 hammer_print_btree_elm(elm
, ondisk
->type
, i
);
1960 for (i
= 0; i
< ondisk
->count
; ++i
) {
1961 elm
= &ondisk
->elms
[i
];
1962 hammer_print_btree_elm(elm
, ondisk
->type
, i
);
1968 hammer_print_btree_elm(hammer_btree_elm_t elm
, u_int8_t type
, int i
)
1971 kprintf("\tobjid = %016llx\n", elm
->base
.obj_id
);
1972 kprintf("\tkey = %016llx\n", elm
->base
.key
);
1973 kprintf("\tcreate_tid = %016llx\n", elm
->base
.create_tid
);
1974 kprintf("\tdelete_tid = %016llx\n", elm
->base
.delete_tid
);
1975 kprintf("\trec_type = %04x\n", elm
->base
.rec_type
);
1976 kprintf("\tobj_type = %02x\n", elm
->base
.obj_type
);
1977 kprintf("\tsubtree_type = %02x\n", elm
->subtree_type
);
1979 if (type
== HAMMER_BTREE_TYPE_INTERNAL
) {
1980 if (elm
->internal
.rec_offset
) {
1981 kprintf("\tcluster_rec = %08x\n",
1982 elm
->internal
.rec_offset
);
1983 kprintf("\tcluster_id = %08x\n",
1984 elm
->internal
.subtree_clu_no
);
1985 kprintf("\tvolno = %08x\n",
1986 elm
->internal
.subtree_vol_no
);
1988 kprintf("\tsubtree_off = %08x\n",
1989 elm
->internal
.subtree_offset
);
1991 kprintf("\tsubtree_count= %d\n", elm
->internal
.subtree_count
);
1993 kprintf("\trec_offset = %08x\n", elm
->leaf
.rec_offset
);
1994 kprintf("\tdata_offset = %08x\n", elm
->leaf
.data_offset
);
1995 kprintf("\tdata_len = %08x\n", elm
->leaf
.data_len
);
1996 kprintf("\tdata_crc = %08x\n", elm
->leaf
.data_crc
);