| blob | 6f752c3e78c70fd401c54d8a5b38d5d003f02fb0 |
1 /*
2 * Copyright (c) 2007 The DragonFly Project. All rights reserved.
3 *
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
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
16 * distribution.
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.
20 *
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
32 * SUCH DAMAGE.
33 *
34 * $DragonFly: src/sys/vfs/hammer/hammer_btree.c,v 1.28 2008/02/05 07:58:43 dillon Exp $
35 */
37 /*
38 * HAMMER B-Tree index
39 *
40 * HAMMER implements a modified B+Tree. In documentation this will
41 * simply be refered to as the HAMMER B-Tree. Basically a HAMMER 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.
47 *
48 * A B-Tree internal node looks like this:
49 *
50 * B N N N N N N B <-- boundary and internal elements
51 * S S S S S S S <-- subtree pointers
52 *
53 * A B-Tree leaf node basically looks like this:
54 *
55 * L L L L L L L L <-- leaf elemenets
56 *
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.
59 *
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
66 * record appends.
67 *
68 * B-Trees also make the stacking of trees fairly straightforward.
69 *
70 * SPIKES: Two leaf elements denoting a sub-range of keys may represent
71 * a spike, or a recursion into another cluster. Most standard B-Tree
72 * searches traverse spikes. The ending spike element is range-inclusive
73 * and does not operate quite like a right-bound.
74 *
75 * INSERTIONS: A search performed with the intention of doing
76 * an insert will guarantee that the terminal leaf node is not full by
77 * splitting full nodes. Splits occur top-down during the dive down the
78 * B-Tree.
79 *
80 * DELETIONS: A deletion makes no attempt to proactively balance the
81 * tree and will recursively remove nodes that become empty. Empty
82 * nodes are not allowed and a deletion may recurse upwards from the leaf.
83 * Rather then allow a deadlock a deletion may terminate early by setting
84 * an internal node's element's subtree_offset to 0. The deletion will
85 * then be resumed the next time a search encounters the element.
86 */
88 #include <sys/buf.h>
89 #include <sys/buf2.h>
102 /*
103 * Iterate records after a search. The cursor is iterated forwards past
104 * the current record until a record matching the key-range requirements
105 * is found. ENOENT is returned if the iteration goes past the ending
106 * key.
107 *
108 * The iteration is inclusive of key_beg and can be inclusive or exclusive
109 * of key_end depending on whether HAMMER_CURSOR_END_INCLUSIVE is set.
110 *
111 * When doing an as-of search (cursor->asof != 0), key_beg.create_tid
112 * may be modified by B-Tree functions.
113 *
114 * cursor->key_beg may or may not be modified by this function during
115 * the iteration. XXX future - in case of an inverted lock we may have
116 * to reinitiate the lookup and set key_beg to properly pick up where we
117 * left off.
118 *
119 * NOTE! EDEADLK *CANNOT* be returned by this procedure.
120 */
121 int
123 {
124 hammer_node_ondisk_t node;
125 hammer_btree_elm_t elm;
130 /*
131 * Skip past the current record
132 */
139 }
141 /*
142 * Loop until an element is found or we are done.
143 */
145 /*
146 * We iterate up the tree and then index over one element
147 * while we are at the last element in the current node.
148 *
149 * NOTE: This can pop us up to another cluster.
150 *
151 * If we are at the root of the root cluster, cursor_up
152 * returns ENOENT.
153 *
154 * NOTE: hammer_cursor_up() will adjust cursor->key_beg
155 * when told to re-search for the cluster tag.
156 *
157 * XXX this could be optimized by storing the information in
158 * the parent reference.
159 *
160 * XXX we can lose the node lock temporarily, this could mess
161 * up our scan.
162 */
167 /* reload stale pointer */
172 }
174 /*
175 * Check internal or leaf element. Determine if the record
176 * at the cursor has gone beyond the end of our range.
177 *
178 * Generally we recurse down through internal nodes. An
179 * internal node can only be returned if INCLUSTER is set
180 * and the node represents a cluster-push record.
181 */
195 r
196 );
205 s
206 );
207 }
212 }
217 }
220 /*
221 * When iterating try to clean up any deleted
222 * internal elements left over from btree_remove()
223 * deadlocks, but it is ok if we can't.
224 */
227 /* note: elm also invalid */
233 }
234 /* reload stale pointer */
251 r
252 );
253 }
257 }
259 /*
260 * We support both end-inclusive and
261 * end-exclusive searches.
262 */
267 }
275 }
278 /*
279 * NOTE: This code assumes that the spike
280 * ending element immediately follows the
281 * spike beginning element.
282 */
283 /*
284 * We must cursor-down via the SPIKE_END
285 * element, otherwise cursor->parent will
286 * not be set correctly for deletions.
287 *
288 * fall-through to avoid an improper
289 * termination from the conditional above.
290 */
294 HAMMER_BTREE_TYPE_SPIKE_END);
296 /* fall through */
298 /*
299 * The SPIKE_END element is inclusive, NOT
300 * like a boundary, so be careful with the
301 * match check.
302 *
303 * This code assumes that a preceding SPIKE_BEG
304 * has already been checked.
305 */
312 /* reload stale pointer */
315 /*
316 * If the cluster root is empty it and its
317 * related spike can be deleted. Ignore
318 * errors. Cursor
319 */
326 /* reload stale pointer */
328 }
333 }
336 }
337 /*
338 * node pointer invalid after loop
339 */
341 /*
342 * Return entry
343 */
352 );
353 }
355 }
357 }
359 /*
360 * Iterate in the reverse direction. This is used by the pruning code to
361 * avoid overlapping records.
362 */
363 int
365 {
366 hammer_node_ondisk_t node;
367 hammer_btree_elm_t elm;
372 /*
373 * Skip past the current record. For various reasons the cursor
374 * may end up set to -1 or set to point at the end of the current
375 * node. These cases must be addressed.
376 */
383 }
387 /*
388 * Loop until an element is found or we are done.
389 */
391 /*
392 * We iterate up the tree and then index over one element
393 * while we are at the last element in the current node.
394 *
395 * NOTE: This can pop us up to another cluster.
396 *
397 * If we are at the root of the root cluster, cursor_up
398 * returns ENOENT.
399 *
400 * NOTE: hammer_cursor_up() will adjust cursor->key_beg
401 * when told to re-search for the cluster tag.
402 *
403 * XXX this could be optimized by storing the information in
404 * the parent reference.
405 *
406 * XXX we can lose the node lock temporarily, this could mess
407 * up our scan.
408 */
414 }
415 /* reload stale pointer */
420 }
422 /*
423 * Check internal or leaf element. Determine if the record
424 * at the cursor has gone beyond the end of our range.
425 *
426 * Generally we recurse down through internal nodes. An
427 * internal node can only be returned if INCLUSTER is set
428 * and the node represents a cluster-push record.
429 */
444 r
445 );
454 s
455 );
456 }
461 }
464 /*
465 * When iterating try to clean up any deleted
466 * internal elements left over from btree_remove()
467 * deadlocks, but it is ok if we can't.
468 */
471 /* note: elm also invalid */
478 }
479 /* reload stale pointer */
496 s
497 );
498 }
502 }
510 }
513 /*
514 * Skip the spike BEG record. We will hit
515 * the END record first since we are
516 * iterating backwards.
517 */
521 /*
522 * The SPIKE_END element is inclusive, NOT
523 * like a boundary, so be careful with the
524 * match check.
525 *
526 * This code assumes that a preceding SPIKE_BEG
527 * has already been checked.
528 */
535 /* reload stale pointer */
538 /*
539 * If the cluster root is empty it and its
540 * related spike can be deleted. Ignore
541 * errors. Cursor
542 */
549 /* reload stale pointer */
551 }
557 }
560 }
561 /*
562 * node pointer invalid after loop
563 */
565 /*
566 * Return entry
567 */
576 );
577 }
579 }
581 }
583 /*
584 * Lookup cursor->key_beg. 0 is returned on success, ENOENT if the entry
585 * could not be found, EDEADLK if inserting and a retry is needed, and a
586 * fatal error otherwise. When retrying, the caller must terminate the
587 * cursor and reinitialize it. EDEADLK cannot be returned if not inserting.
588 *
589 * The cursor is suitably positioned for a deletion on success, and suitably
590 * positioned for an insertion on ENOENT if HAMMER_CURSOR_INSERT was
591 * specified.
592 *
593 * The cursor may begin anywhere, the search will traverse clusters in
594 * either direction to locate the requested element.
595 *
596 * Most of the logic implementing historical searches is handled here. We
597 * do an initial lookup with create_tid set to the asof TID. Due to the
598 * way records are laid out, a backwards iteration may be required if
599 * ENOENT is returned to locate the historical record. Here's the
600 * problem:
601 *
602 * create_tid: 10 15 20
603 * LEAF1 LEAF2
604 * records: (11) (18)
605 *
606 * Lets say we want to do a lookup AS-OF timestamp 17. We will traverse
607 * LEAF2 but the only record in LEAF2 has a create_tid of 18, which is
608 * not visible and thus causes ENOENT to be returned. We really need
609 * to check record 11 in LEAF1. If it also fails then the search fails
610 * (e.g. it might represent the range 11-16 and thus still not match our
611 * AS-OF timestamp of 17).
612 *
613 * If this case occurs btree_search() will set HAMMER_CURSOR_CREATE_CHECK
614 * and the cursor->create_check TID if an iteration might be needed.
615 * In the above example create_check would be set to 14.
616 */
617 int
619 {
630 /*
631 * Stop if no error.
632 * Stop if error other then ENOENT.
633 * Stop if ENOENT and not special case.
634 */
636 }
640 }
642 /* loop */
643 }
646 }
650 }
652 /*
653 * Execute the logic required to start an iteration. The first record
654 * located within the specified range is returned and iteration control
655 * flags are adjusted for successive hammer_btree_iterate() calls.
656 */
657 int
659 {
666 }
669 }
671 /*
672 * Similarly but for an iteration in the reverse direction.
673 */
674 int
676 {
688 }
691 }
693 /*
694 * Extract the record and/or data associated with the cursor's current
695 * position. Any prior record or data stored in the cursor is replaced.
696 * The cursor must be positioned at a leaf node.
697 *
698 * NOTE: Most extractions occur at the leaf of the B-Tree. The only
699 * extraction allowed at an internal element is at a cluster-push.
700 * Cluster-push elements have records but no data.
701 */
702 int
704 {
705 hammer_node_ondisk_t node;
706 hammer_btree_elm_t elm;
707 hammer_cluster_t cluster;
708 u_int64_t buf_type;
713 /*
714 * A cluster record type has no data reference, the information
715 * is stored directly in the record and B-Tree element.
716 *
717 * The case where the data reference resolves to the same buffer
718 * as the record reference must be handled.
719 */
726 /*
727 * There is nothing to extract for an internal element.
728 */
734 /*
735 * Leaf element.
736 */
745 }
748 /*
749 * Only records have data references. Spike elements
750 * do not.
751 */
754 /*
755 * The data is not in the same buffer as the last
756 * record we cached, but it could still be embedded
757 * in a record. Note that we may not have loaded the
758 * record's buffer above, depending on flags.
759 */
764 else
768 }
774 /*
775 * Data in same buffer as record. Note that we
776 * leave any existing data_buffer intact, even
777 * though we don't use it in this case, in case
778 * other records extracted during an iteration
779 * go back to it.
780 *
781 * The data must be embedded in the record for this
782 * case to be hit.
783 *
784 * Just assume the buffer type is correct.
785 */
792 }
793 }
795 }
798 /*
799 * Insert a leaf element into the B-Tree at the current cursor position.
800 * The cursor is positioned such that the element at and beyond the cursor
801 * are shifted to make room for the new record.
802 *
803 * The caller must call hammer_btree_lookup() with the HAMMER_CURSOR_INSERT
804 * flag set and that call must return ENOENT before this function can be
805 * called.
806 *
807 * ENOSPC is returned if there is no room to insert a new record.
808 */
809 int
811 {
812 hammer_node_ondisk_t node;
819 /*
820 * Insert the element at the leaf node and update the count in the
821 * parent. It is possible for parent to be NULL, indicating that
822 * the root of the B-Tree in the cluster is a leaf. It is also
823 * possible for the leaf to be empty.
824 *
825 * Remember that the right-hand boundary is not included in the
826 * count.
827 */
837 }
841 /*
842 * Debugging sanity checks. Note that the element to the left
843 * can match the element we are inserting if it is a SPIKE_END,
844 * because spike-end's represent a non-inclusive end to a range.
845 */
850 }
855 }
857 /*
858 * Insert a cluster spike into the B-Tree at the current cursor position.
859 * The caller pre-positions the insertion cursor at ncluster's
860 * left bound in the originating cluster. Both the originating cluster
861 * and the target cluster must be serialized, EDEADLK is fatal.
862 *
863 * Basically we have to lay down the two spike elements and assert that
864 * the leaf's right bound does not bisect the ending element. The ending
865 * spike element is non-inclusive, just like a boundary. The target cluster's
866 * clu_btree_parent_offset may have to adjusted.
867 *
868 * NOTE: Serialization is usually accoplished by virtue of being the
869 * initial accessor of a cluster.
870 */
871 int
874 {
875 hammer_node_ondisk_t node;
876 hammer_btree_elm_t elm;
877 hammer_cluster_t ocluster;
894 /*
895 * Make sure the spike is legal or the B-Tree code will get really
896 * confused.
897 *
898 * XXX the right bound my bisect the two spike elements. We
899 * need code here to 'fix' the right bound going up the tree
900 * instead of an assertion.
901 */
909 }
928 /*
929 * SPIKE_END must be inclusive, not exclusive.
930 */
934 /*
935 * The target cluster's parent offset may have to be updated.
936 *
937 * NOTE: Modifying a cluster header does not mark it open, and
938 * flushing it will only clear an existing open flag if the cluster
939 * has been validated.
940 */
947 }
962 }
965 }
967 /*
968 * Delete a record from the B-Tree at the current cursor position.
969 * The cursor is positioned such that the current element is the one
970 * to be deleted.
971 *
972 * On return the cursor will be positioned after the deleted element and
973 * MAY point to an internal node. It will be suitable for the continuation
974 * of an iteration but not for an insertion or deletion.
975 *
976 * Deletions will attempt to partially rebalance the B-Tree in an upward
977 * direction, but will terminate rather then deadlock. Empty leaves are
978 * not allowed except at the root node of a cluster. An early termination
979 * will leave an internal node with an element whos subtree_offset is 0,
980 * a case detected and handled by btree_search().
981 *
982 * This function can return EDEADLK, requiring the caller to retry the
983 * operation after clearing the deadlock.
984 */
985 int
987 {
988 hammer_node_ondisk_t ondisk;
989 hammer_node_t node;
990 hammer_node_t parent;
997 /*
998 * Delete the element from the leaf node.
999 *
1000 * Remember that leaf nodes do not have boundaries.
1001 */
1012 }
1015 /*
1016 * Validate local parent
1017 */
1024 }
1026 /*
1027 * If the leaf becomes empty it must be detached from the parent,
1028 * potentially recursing through to the cluster root.
1029 *
1030 * This may reposition the cursor at one of the parent's of the
1031 * current node.
1032 *
1033 * Ignore deadlock errors, that simply means that btree_remove
1034 * was unable to recurse and had to leave the subtree_offset
1035 * in the parent set to 0.
1036 */
1046 }
1050 }
1052 /*
1053 * PRIMAY B-TREE SEARCH SUPPORT PROCEDURE
1054 *
1055 * Search a cluster's B-Tree for cursor->key_beg, return the matching node.
1056 *
1057 * The search can begin ANYWHERE in the B-Tree. As a first step the search
1058 * iterates up the tree as necessary to properly position itself prior to
1059 * actually doing the sarch.
1060 *
1061 * INSERTIONS: The search will split full nodes and leaves on its way down
1062 * and guarentee that the leaf it ends up on is not full. If we run out
1063 * of space the search continues to the leaf (to position the cursor for
1064 * the spike), but ENOSPC is returned.
1065 *
1066 * The search is only guarenteed to end up on a leaf if an error code of 0
1067 * is returned, or if inserting and an error code of ENOENT is returned.
1068 * Otherwise it can stop at an internal node. On success a search returns
1069 * a leaf node unless INCLUSTER is set and the search located a cluster push
1070 * node (which is an internal node).
1071 *
1072 * COMPLEXITY WARNING! This is the core B-Tree search code for the entire
1073 * filesystem, and it is not simple code. Please note the following facts:
1074 *
1075 * - Internal node recursions have a boundary on the left AND right. The
1076 * right boundary is non-inclusive. The create_tid is a generic part
1077 * of the key for internal nodes.
1078 *
1079 * - Leaf nodes contain terminal elements AND spikes. A spike recurses into
1080 * another cluster and contains two leaf elements.. a beginning and an
1081 * ending element. The SPIKE_END element is RANGE-EXCLUSIVE, just like a
1082 * boundary. This means that it is possible to have two elements
1083 * (a spike ending element and a record) side by side with the same key.
1084 *
1085 * - Because the SPIKE_END element is range inclusive, it cannot match the
1086 * right boundary of the parent node. SPIKE_BEG and SPIKE_END elements
1087 * always come in pairs, and always exist side by side in the same leaf.
1088 *
1089 * - Filesystem lookups typically set HAMMER_CURSOR_ASOF, indicating a
1090 * historical search. ASOF and INSERT are mutually exclusive. When
1091 * doing an as-of lookup btree_search() checks for a right-edge boundary
1092 * case. If while recursing down the left-edge differs from the key
1093 * by ONLY its create_tid, HAMMER_CURSOR_CREATE_CHECK is set along
1094 * with cursor->create_check. This is used by btree_lookup() to iterate.
1095 * The iteration backwards because as-of searches can wind up going
1096 * down the wrong branch of the B-Tree.
1097 */
1098 static
1099 int
1101 {
1102 hammer_node_ondisk_t node;
1103 hammer_cluster_t cluster;
1104 hammer_btree_elm_t elm;
1123 );
1124 }
1126 /*
1127 * Move our cursor up the tree until we find a node whos range covers
1128 * the key we are trying to locate. This may move us between
1129 * clusters.
1130 *
1131 * The left bound is inclusive, the right bound is non-inclusive.
1132 * It is ok to cursor up too far so when cursoring across a cluster
1133 * boundary.
1134 *
1135 * First see if we can skip the whole cluster. hammer_cursor_up()
1136 * handles both cases but this way we don't check the cluster
1137 * bounds when going up the tree within a cluster.
1138 *
1139 * NOTE: If INCLUSTER is set and we are at the root of the cluster,
1140 * hammer_cursor_up() will return ENOENT.
1141 */
1157 }
1167 }
1169 /*
1170 * The delete-checks below are based on node, not parent. Set the
1171 * initial delete-check based on the parent.
1172 */
1177 }
1179 /*
1180 * We better have ended up with a node somewhere, and our second
1181 * while loop had better not have traversed up a cluster.
1182 */
1185 /*
1186 * If we are inserting we can't start at a full node if the parent
1187 * is also full (because there is no way to split the node),
1188 * continue running up the tree until the requirement is satisfied
1189 * or we hit the root of the current cluster.
1190 *
1191 * (If inserting we aren't doing an as-of search so we don't have
1192 * to worry about create_check).
1193 */
1201 }
1205 }
1207 /* cluster and node are now may become stale */
1210 }
1211 /* cluster = cursor->node->cluster; not needed until next cluster = */
1213 new_cluster:
1214 /*
1215 * Push down through internal nodes to locate the requested key.
1216 */
1220 /*
1221 * Scan the node to find the subtree index to push down into.
1222 * We go one-past, then back-up.
1223 *
1224 * We must proactively remove deleted elements which may
1225 * have been left over from a deadlocked btree_remove().
1226 *
1227 * The left and right boundaries are included in the loop
1228 * in order to detect edge cases.
1229 *
1230 * If the separator only differs by create_tid (r == 1)
1231 * and we are doing an as-of search, we may end up going
1232 * down a branch to the left of the one containing the
1233 * desired key. This requires numerous special cases.
1234 */
1241 }
1248 }
1255 }
1256 }
1260 }
1262 /*
1263 * These cases occur when the parent's idea of the boundary
1264 * is wider then the child's idea of the boundary, and
1265 * require special handling. If not inserting we can
1266 * terminate the search early for these cases but the
1267 * child's boundaries cannot be unconditionally modified.
1268 */
1270 /*
1271 * If i == 0 the search terminated to the LEFT of the
1272 * left_boundary but to the RIGHT of the parent's left
1273 * boundary.
1274 */
1275 u_int8_t save;
1279 /*
1280 * If we aren't inserting we can stop here.
1281 */
1285 }
1287 /*
1288 * Correct a left-hand boundary mismatch.
1289 *
1290 * We can only do this if we can upgrade the lock.
1291 */
1299 /*
1300 * If i == node->count + 1 the search terminated to
1301 * the RIGHT of the right boundary but to the LEFT
1302 * of the parent's right boundary. If we aren't
1303 * inserting we can stop here.
1304 *
1305 * Note that the last element in this case is
1306 * elms[i-2] prior to adjustments to 'i'.
1307 */
1312 }
1314 /*
1315 * Correct a right-hand boundary mismatch.
1316 * (actual push-down record is i-2 prior to
1317 * adjustments to i).
1318 *
1319 * We can only do this if we can upgrade the lock.
1320 */
1328 /*
1329 * The push-down index is now i - 1. If we had
1330 * terminated on the right boundary this will point
1331 * us at the last element.
1332 */
1334 }
1344 i,
1349 );
1350 }
1352 /*
1353 * When searching try to clean up any deleted
1354 * internal elements left over from btree_remove()
1355 * deadlocks.
1356 *
1357 * If we fail and we are doing an insertion lookup,
1358 * we have to return EDEADLK, because an insertion lookup
1359 * must terminate at a leaf.
1360 */
1368 }
1370 }
1373 /*
1374 * Handle insertion and deletion requirements.
1375 *
1376 * If inserting split full nodes. The split code will
1377 * adjust cursor->node and cursor->index if the current
1378 * index winds up in the new node.
1379 *
1380 * If inserting and a left or right edge case was detected,
1381 * we cannot correct the left or right boundary and must
1382 * prepend and append an empty leaf node in order to make
1383 * the boundary correction.
1384 *
1385 * If we run out of space we set enospc and continue on
1386 * to a leaf to provide the spike code with a good point
1387 * of entry. Enospc is reset if we cross a cluster boundary.
1388 */
1396 }
1397 /*
1398 * reload stale pointers
1399 */
1402 }
1403 }
1405 /*
1406 * Push down (push into new node, existing node becomes
1407 * the parent) and continue the search.
1408 */
1410 /* node and cluster become stale */
1415 }
1417 /*
1418 * We are at a leaf, do a linear search of the key array.
1419 *
1420 * If we encounter a spike element type within the necessary
1421 * range we push into it. Note that SPIKE_END is non-inclusive
1422 * of the spike range.
1423 *
1424 * On success the index is set to the matching element and 0
1425 * is returned.
1426 *
1427 * On failure the index is set to the insertion point and ENOENT
1428 * is returned.
1429 *
1430 * Boundaries are not stored in leaf nodes, so the index can wind
1431 * up to the left of element 0 (index == 0) or past the end of
1432 * the array (index == node->count).
1433 */
1442 }
1453 /*
1454 * SPIKE_BEG. Stop if we are to the left of the
1455 * spike begin element.
1456 *
1457 * If we are not the last element in the leaf continue
1458 * the loop looking for the SPIKE_END. If we are
1459 * the last element, however, then push into the
1460 * spike.
1461 *
1462 * If doing an as-of search a Spike demark on a
1463 * create_tid boundary must be pushed into and an
1464 * iteration will be forced if it turned out to be
1465 * the wrong choice.
1466 *
1467 * If not doing an as-of search exact comparisons
1468 * must be used.
1469 *
1470 * enospc must be reset because we have crossed a
1471 * cluster boundary.
1472 */
1476 /*
1477 * Set the create_check if the spike element
1478 * only differs by its create_tid.
1479 */
1483 }
1488 }
1490 /*
1491 * SPIKE_END. We can only hit this case if we are
1492 * greater or equal to SPIKE_BEG.
1493 *
1494 * If we are <= SPIKE_END we must push into
1495 * it, otherwise continue the search. The SPIKE_END
1496 * element is range-inclusive.
1497 *
1498 * enospc must be reset because we have crossed a
1499 * cluster boundary.
1500 */
1502 /*
1503 * Continue the search but check for a
1504 * create_tid boundary. Because the
1505 * SPIKE_END is inclusive we do not have
1506 * to subtract 1 to force an iteration to
1507 * go down the spike.
1508 */
1513 HAMMER_CURSOR_CREATE_CHECK;
1514 }
1516 }
1525 }
1527 /*
1528 * We are at a record element. Stop if we've flipped past
1529 * key_beg, not counting the create_tid test. Allow the
1530 * r == 1 case (key_beg > element but differs only by its
1531 * create_tid) to fall through to the AS-OF check.
1532 */
1540 /*
1541 * Check our as-of timestamp against the element.
1542 */
1547 }
1548 /* success */
1552 /* success */
1553 }
1554 success:
1562 i);
1563 }
1565 }
1567 /*
1568 * The search of the leaf node failed. i is the insertion point.
1569 */
1570 failed:
1576 i);
1577 }
1579 /*
1580 * No exact match was found, i is now at the insertion point.
1581 *
1582 * If inserting split a full leaf before returning. This
1583 * may have the side effect of adjusting cursor->node and
1584 * cursor->index.
1585 *
1586 * For now the leaf must have at least 2 free elements to accomodate
1587 * the insertion of a spike during recovery. See the
1588 * hammer_btree_insert_cluster() function.
1589 */
1598 }
1599 /*
1600 * reload stale pointers
1601 */
1602 /* NOT USED
1603 i = cursor->index;
1604 node = &cursor->node->internal;
1605 */
1606 }
1608 /*
1609 * We reached a leaf but did not find the key we were looking for.
1610 * If this is an insert we will be properly positioned for an insert
1611 * (ENOENT) or spike (ENOSPC) operation.
1612 */
1614 done:
1616 }
1619 /************************************************************************
1620 * SPLITTING AND MERGING *
1621 ************************************************************************
1622 *
1623 * These routines do all the dirty work required to split and merge nodes.
1624 */
1626 /*
1627 * Split an internal node into two nodes and move the separator at the split
1628 * point to the parent.
1629 *
1630 * (cursor->node, cursor->index) indicates the element the caller intends
1631 * to push into. We will adjust node and index if that element winds
1632 * up in the split node.
1633 *
1634 * If we are at the root of a cluster a new root must be created with two
1635 * elements, one pointing to the original root and one pointing to the
1636 * newly allocated split node.
1637 *
1638 * NOTE! Being at the root of a cluster is different from being at the
1639 * root of the root cluster. cursor->parent will not be NULL and
1640 * cursor->node->ondisk.parent must be tested against 0. Theoretically
1641 * we could propogate the algorithm into the parent and deal with multiple
1642 * 'roots' in the cluster header, but it's easier not to.
1643 */
1644 static
1645 int
1647 {
1648 hammer_node_ondisk_t ondisk;
1649 hammer_node_t node;
1650 hammer_node_t parent;
1651 hammer_node_t new_node;
1652 hammer_btree_elm_t elm;
1653 hammer_btree_elm_t parent_elm;
1668 }
1670 /*
1671 * We are splitting but elms[split] will be promoted to the parent,
1672 * leaving the right hand node with one less element. If the
1673 * insertion point will be on the left-hand side adjust the split
1674 * point to give the right hand side one additional node.
1675 */
1682 /*
1683 * If we are at the root of the cluster, create a new root node with
1684 * 1 element and split normally. Avoid making major modifications
1685 * until we know the whole operation will work.
1686 *
1687 * The root of the cluster is different from the root of the root
1688 * cluster. Use the node's on-disk structure's parent offset to
1689 * detect the case.
1690 */
1705 /* ondisk->elms[1].base.btype - not used */
1713 }
1715 /*
1716 * Split node into new_node at the split point.
1717 *
1718 * B O O O P N N B <-- P = node->elms[split]
1719 * 0 1 2 3 4 5 6 <-- subtree indices
1720 *
1721 * x x P x x
1722 * s S S s
1723 * / \
1724 * B O O O B B N N B <--- inner boundary points are 'P'
1725 * 0 1 2 3 4 5 6
1726 *
1727 */
1734 }
1736 }
1739 /*
1740 * Create the new node. P becomes the left-hand boundary in the
1741 * new node. Copy the right-hand boundary as well.
1742 *
1743 * elm is the new separator.
1744 */
1756 /*
1757 * Cleanup the original node. Elm (P) becomes the new boundary,
1758 * its subtree_offset was moved to the new node. If we had created
1759 * a new root its parent pointer may have changed.
1760 */
1764 /*
1765 * Insert the separator into the parent, fixup the parent's
1766 * reference to the original node, and reference the new node.
1767 * The separator is P.
1768 *
1769 * Remember that base.count does not include the right-hand boundary.
1770 */
1782 /*
1783 * The children of new_node need their parent pointer set to new_node.
1784 * The children have already been locked by
1785 * hammer_btree_lock_children().
1786 */
1792 }
1793 }
1795 /*
1796 * The cluster's root pointer may have to be updated.
1797 */
1805 }
1807 }
1810 /*
1811 * Ok, now adjust the cursor depending on which element the original
1812 * index was pointing at. If we are >= the split point the push node
1813 * is now in the new node.
1814 *
1815 * NOTE: If we are at the split point itself we cannot stay with the
1816 * original node because the push index will point at the right-hand
1817 * boundary, which is illegal.
1818 *
1819 * NOTE: The cursor's parent or parent_index must be adjusted for
1820 * the case where a new parent (new root) was created, and the case
1821 * where the cursor is now pointing at the split node.
1822 */
1833 }
1835 /*
1836 * Fixup left and right bounds
1837 */
1846 done:
1850 }
1852 /*
1853 * Same as the above, but splits a full leaf node.
1854 *
1855 * This function
1856 */
1857 static
1858 int
1860 {
1861 hammer_node_ondisk_t ondisk;
1862 hammer_node_t parent;
1863 hammer_node_t leaf;
1864 hammer_node_t new_leaf;
1865 hammer_btree_elm_t elm;
1866 hammer_btree_elm_t parent_elm;
1867 hammer_base_elm_t mid_boundary;
1882 }
1884 /*
1885 * Calculate the split point. If the insertion point will be on
1886 * the left-hand side adjust the split point to give the right
1887 * hand side one additional node.
1888 *
1889 * Spikes are made up of two leaf elements which cannot be
1890 * safely split.
1891 */
1904 }
1906 /*
1907 * If we are at the root of the tree, create a new root node with
1908 * 1 element and split normally. Avoid making major modifications
1909 * until we know the whole operation will work.
1910 */
1925 /* ondisk->elms[1].base.btype = not used */
1933 }
1935 /*
1936 * Split leaf into new_leaf at the split point. Select a separator
1937 * value in-between the two leafs but with a bent towards the right
1938 * leaf since comparisons use an 'elm >= separator' inequality.
1939 *
1940 * L L L L L L L L
1941 *
1942 * x x P x x
1943 * s S S s
1944 * / \
1945 * L L L L L L L L
1946 */
1953 }
1955 }
1958 /*
1959 * Create the new node. P (elm) become the left-hand boundary in the
1960 * new node. Copy the right-hand boundary as well.
1961 */
1972 /*
1973 * Cleanup the original node. Because this is a leaf node and
1974 * leaf nodes do not have a right-hand boundary, there
1975 * aren't any special edge cases to clean up. We just fixup the
1976 * count.
1977 */
1980 /*
1981 * Insert the separator into the parent, fixup the parent's
1982 * reference to the original node, and reference the new node.
1983 * The separator is P.
1984 *
1985 * Remember that base.count does not include the right-hand boundary.
1986 * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1987 */
1995 /*
1996 * Create the separator. XXX At the moment use exactly the
1997 * right-hand element if this is a recovery operation in order
1998 * to guarantee that it does not bisect the spike elements in a
1999 * later call to hammer_btree_insert_cluster().
2000 */
2006 }
2012 /*
2013 * The children of new_leaf need their parent pointer set to new_leaf.
2014 * The children have already been locked by btree_lock_children().
2015 *
2016 * The leaf's elements are either TYPE_RECORD or TYPE_SPIKE_*. Only
2017 * elements of BTREE_TYPE_SPIKE_END really requires any action.
2018 */
2024 }
2025 }
2027 /*
2028 * The cluster's root pointer may have to be updated.
2029 */
2037 }
2039 }
2041 /*
2042 * Ok, now adjust the cursor depending on which element the original
2043 * index was pointing at. If we are >= the split point the push node
2044 * is now in the new node.
2045 *
2046 * NOTE: If we are at the split point itself we need to select the
2047 * old or new node based on where key_beg's insertion point will be.
2048 * If we pick the wrong side the inserted element will wind up in
2049 * the wrong leaf node and outside that node's bounds.
2050 */
2063 }
2065 /*
2066 * Fixup left and right bounds
2067 */
2072 /*
2073 * Note: The right assertion is typically > 0, but if the last element
2074 * is a SPIKE_END it can be == 0 because the spike-end is non-inclusive
2075 * of the range being spiked.
2076 *
2077 * This may seem a bit odd but it works.
2078 */
2084 done:
2088 }
2090 /*
2091 * Recursively correct the right-hand boundary's create_tid to (tid) as
2092 * long as the rest of the key matches. We have to recurse upward in
2093 * the tree as well as down the left side of each parent's right node.
2094 *
2095 * Return EDEADLK if we were only partially successful, forcing the caller
2096 * to try again. The original cursor is not modified. This routine can
2097 * also fail with EDEADLK if it is forced to throw away a portion of its
2098 * record history.
2099 *
2100 * The caller must pass a downgraded cursor to us (otherwise we can't dup it).
2101 */
2104 hammer_node_t node;
2106 };
2110 int
2112 {
2114 hammer_base_elm_t elm;
2115 hammer_node_t orig_node;
2122 /*
2123 * Save our position so we can restore it on return. This also
2124 * gives us a stable 'elm'.
2125 */
2132 /*
2133 * Now build a list of parents going up, allocating a rhb
2134 * structure for each one.
2135 */
2137 /*
2138 * Stop if we no longer have any right-bounds to fix up
2139 */
2144 }
2146 /*
2147 * Stop if the right-hand bound's create_tid does not
2148 * need to be corrected. Note that if the parent is
2149 * a cluster the bound is pointing at the actual bound
2150 * in the cluster header, not the SPIKE_END element in
2151 * the parent cluster, so we don't have to worry about
2152 * the fact that SPIKE_END is range-inclusive.
2153 */
2157 KKASSERT(cursor->parent->ondisk->elms[cursor->parent_index].base.btype != HAMMER_BTREE_TYPE_SPIKE_BEG);
2167 }
2169 /*
2170 * now safely adjust the right hand bound for each rhb. This may
2171 * also require taking the right side of the tree and iterating down
2172 * ITS left side.
2173 */
2190 /*
2191 * Right-boundary for parent at internal node
2192 * is one element to the right of the element whos
2193 * right boundary needs adjusting. We must then
2194 * traverse down the left side correcting any left
2195 * bounds (which may now be too far to the left).
2196 */
2201 /*
2202 * Right-boundary for parent at leaf node. Both
2203 * the SPIKE_END and the cluster header must be
2204 * corrected, but we don't have to traverse down
2205 * (there's nothing TO traverse down other then what
2206 * we've already recorded).
2207 *
2208 * The SPIKE_END is range-inclusive.
2209 */
2225 }
2231 }
2232 }
2234 /*
2235 * Cleanup
2236 */
2242 }
2247 }
2249 /*
2250 * Similar to rhb (in fact, rhb calls lhb), but corrects the left hand
2251 * bound going downward starting at the current cursor position.
2252 *
2253 * This function does not restore the cursor after use.
2254 */
2255 int
2257 {
2259 hammer_base_elm_t elm;
2260 hammer_base_elm_t cmp;
2268 /*
2269 * Record the node and traverse down the left-hand side for all
2270 * matching records needing a boundary correction.
2271 */
2282 /*
2283 * Nothing to traverse down if we are at the right
2284 * boundary of an internal node.
2285 */
2293 }
2303 }
2307 }
2309 /*
2310 * Now we can safely adjust the left-hand boundary from the bottom-up.
2311 * The last element we remove from the list is the caller's right hand
2312 * boundary, which must also be adjusted.
2313 */
2332 /*
2333 * SPIKE_BEG, also correct cluster header. Occurs
2334 * only while we are traversing the left-hand
2335 * boundary.
2336 */
2344 /*
2345 * We can only cursor down through SPIKE_END.
2346 */
2359 }
2362 }
2363 }
2365 /*
2366 * Cleanup
2367 */
2373 }
2375 }
2377 /*
2378 * Attempt to remove the empty B-Tree node at (cursor->node). Returns 0
2379 * on success, EAGAIN if we could not acquire the necessary locks, or some
2380 * other error. This node can be a leaf node or an internal node.
2381 *
2382 * On return the cursor may end up pointing at an internal node, suitable
2383 * for further iteration but not for an immediate insertion or deletion.
2384 *
2385 * cursor->node may be an internal node or a leaf node.
2386 *
2387 * NOTE: If cursor->node has one element it is the parent trying to delete
2388 * that element, make sure cursor->index is properly adjusted on success.
2389 */
2390 int
2392 {
2393 hammer_node_ondisk_t ondisk;
2394 hammer_btree_elm_t elm;
2395 hammer_node_t node;
2396 hammer_node_t save;
2397 hammer_node_t parent;
2401 /*
2402 * If we are at the root of the cluster we must be able to
2403 * successfully delete the HAMMER_BTREE_SPIKE_* leaf elements in
2404 * the parent in order to be able to destroy the cluster.
2405 */
2416 /*
2417 * When trying to delete a cluster we need to exclusively
2418 * lock the cluster root, its parent (leaf in parent cluster),
2419 * AND the parent of that leaf if it's going to be empty,
2420 * because we can't leave around an empty leaf.
2421 *
2422 * XXX this is messy due to potentially recursive locks.
2423 * downgrade the cursor, get a second shared lock on the
2424 * node that cannot deadlock because we only own shared locks
2425 * then, cursor-up, and re-upgrade everything. If the
2426 * upgrades EDEADLK then don't try to remove the cluster
2427 * at this time.
2428 */
2435 /*
2436 * After the cursor up save has the empty root node
2437 * of the target cluster to be deleted, cursor->node
2438 * is at the leaf containing the spikes, and
2439 * cursor->parent is the parent of that leaf.
2440 *
2441 * cursor->node and cursor->parent are both in the
2442 * parent cluster of the cluster being deleted.
2443 */
2452 /* may be EDEADLK */
2456 /*
2457 * cursor->node is now the leaf in the parent
2458 * cluster containing the spike elements.
2459 *
2460 * The cursor should be pointing at the
2461 * SPIKE_END element.
2462 *
2463 * Remove the spike elements and recurse
2464 * if the leaf becomes empty.
2465 */
2473 HAMMER_BTREE_TYPE_SPIKE_BEG);
2475 HAMMER_BTREE_TYPE_SPIKE_END);
2477 /*
2478 * Ok, remove it and the underlying record.
2479 */
2482 HAMMER_RECTYPE_CLUSTER);
2493 }
2494 }
2496 }
2498 /*
2499 * Zero-out the parent's reference to the child and flag the
2500 * child for destruction. This ensures that the child is not
2501 * reused while other references to it exist.
2502 */
2514 /*
2515 * If the parent would otherwise not become empty we can physically
2516 * remove the zero'd element. Note however that in order to
2517 * guarentee a valid cursor we still need to be able to cursor up
2518 * because we no longer have a node.
2519 *
2520 * This collapse will change the parent's boundary elements, making
2521 * them wider. The new boundaries are recursively corrected in
2522 * btree_search().
2523 *
2524 * XXX we can theoretically recalculate the midpoint but there isn't
2525 * much of a reason to do it.
2526 */
2535 }
2537 /*
2538 * Remove the internal element from the parent. The bcopy must
2539 * include the right boundary element.
2540 */
2544 /* ondisk is node's ondisk */
2545 /* elm is node's element */
2547 /*
2548 * Remove the internal element that we zero'd out. Tell the caller
2549 * to loop if it hits zero (to try to avoid eating up precious kernel
2550 * stack).
2551 */
2558 }
2560 /*
2561 * Attempt to remove the deleted internal element at the current cursor
2562 * position. If we are unable to remove the element we return EDEADLK.
2563 *
2564 * If the current internal node becomes empty we delete it in the parent
2565 * and cursor up, looping until we finish or we deadlock.
2566 *
2567 * On return, if successful, the cursor will be pointing at the next
2568 * iterative position in the B-Tree. If unsuccessful the cursor will be
2569 * pointing at the last deleted internal element that could not be
2570 * removed.
2571 */
2572 static
2573 int
2575 {
2576 hammer_node_t node;
2577 hammer_btree_elm_t elm;
2589 }
2591 }
2593 /*
2594 * The element (elm) has been moved to a new internal node (node).
2595 *
2596 * If the element represents a pointer to an internal node that node's
2597 * parent must be adjusted to the element's new location.
2598 *
2599 * If the element represents a spike the target cluster's header must
2600 * be adjusted to point to the element's new location. This only
2601 * applies to HAMMER_SPIKE_END.
2602 *
2603 * GET_CLUSTER_NORECOVER must be used to avoid a recovery recursion during
2604 * the rebuild of the recovery cluster's B-Tree, which can blow the kernel
2605 * stack.
2606 *
2607 * XXX deadlock potential here with our exclusive locks
2608 */
2609 static
2610 int
2612 {
2613 hammer_volume_t volume;
2614 hammer_cluster_t cluster;
2615 hammer_node_t child;
2629 }
2651 }
2653 }
2655 /*
2656 * Exclusively lock all the children of node. This is used by the split
2657 * code to prevent anyone from accessing the children of a cursor node
2658 * while we fix-up its parent offset.
2659 *
2660 * If we don't lock the children we can really mess up cursors which block
2661 * trying to cursor-up into our node.
2662 *
2663 * WARNING: Cannot be used when doing B-tree operations on a recovery
2664 * cluster because the target cluster may require recovery, resulting
2665 * in a deep recursion which blows the kernel stack.
2666 *
2667 * On failure EDEADLK (or some other error) is returned. If a deadlock
2668 * error is returned the cursor is adjusted to block on termination.
2669 */
2670 int
2673 {
2674 hammer_node_t node;
2675 hammer_node_locklist_t item;
2676 hammer_node_ondisk_t ondisk;
2677 hammer_btree_elm_t elm;
2678 hammer_volume_t volume;
2679 hammer_cluster_t cluster;
2680 hammer_node_t child;
2719 }
2725 }
2733 }
2734 }
2735 }
2739 }
2742 /*
2743 * Release previously obtained node locks.
2744 */
2745 void
2747 {
2748 hammer_node_locklist_t item;
2755 }
2756 }
2758 /************************************************************************
2759 * MISCELLANIOUS SUPPORT *
2760 ************************************************************************/
2762 /*
2763 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
2764 *
2765 * Note that for this particular function a return value of -1, 0, or +1
2766 * can denote a match if create_tid is otherwise discounted. A create_tid
2767 * of zero is considered to be 'infinity' in comparisons.
2768 *
2769 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
2770 */
2771 int
2773 {
2789 /*
2790 * A create_tid of zero indicates a record which is undeletable
2791 * and must be considered to have a value of positive infinity.
2792 */
2797 }
2805 }
2807 /*
2808 * Test a timestamp against an element to determine whether the
2809 * element is visible. A timestamp of 0 means 'infinity'.
2810 */
2811 int
2813 {
2818 }
2824 }
2826 /*
2827 * Create a separator half way inbetween key1 and key2. For fields just
2828 * one unit apart, the separator will match key2. key1 is on the left-hand
2829 * side and key2 is on the right-hand side.
2830 *
2831 * create_tid has to be special cased because a value of 0 represents
2832 * infinity.
2833 */
2834 #define MAKE_SEPARATOR(key1, key2, dest, field) \
2835 dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
2837 static void
2839 hammer_base_elm_t dest)
2840 {
2850 /*
2851 * Oops, a create_tid of 0 means 'infinity', so
2852 * if everything matches this just isn't legal.
2853 */
2859 }
2862 }
2863 }
2865 #undef MAKE_SEPARATOR
2867 /*
2868 * Return whether a generic internal or leaf node is full
2869 */
2870 static int
2872 {
2884 }
2886 }
2888 /*
2889 * Return whether a generic internal or leaf node is almost full. This
2890 * routine is used as a helper for search insertions to guarentee at
2891 * least 2 available slots in the internal node(s) leading up to a leaf,
2892 * so hammer_btree_insert_cluster() will function properly.
2893 */
2894 static int
2896 {
2908 }
2910 }
2912 #if 0
2913 static int
2915 {
2921 }
2922 #endif
2924 void
2926 {
2927 hammer_btree_elm_t elm;
2933 /*
2934 * Dump both boundary elements if an internal node
2935 */
2940 }
2945 }
2946 }
2947 }
2949 void
2951 {
2979 }
2980 }