| blob | 3eaa1b34d3100b6068d58eaf4961af1db8d8d6b3 |
1 /*
2 * Copyright (c) 2007-2008 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.76 2008/08/06 15:38:58 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 * INSERTIONS: A search performed with the intention of doing
71 * an insert will guarantee that the terminal leaf node is not full by
72 * splitting full nodes. Splits occur top-down during the dive down the
73 * B-Tree.
74 *
75 * DELETIONS: A deletion makes no attempt to proactively balance the
76 * tree and will recursively remove nodes that become empty. If a
77 * deadlock occurs a deletion may not be able to remove an empty leaf.
78 * Deletions never allow internal nodes to become empty (that would blow
79 * up the boundaries).
80 */
82 #include <sys/buf.h>
83 #include <sys/buf2.h>
91 hammer_tid_t mirror_tid);
96 /*
97 * Iterate records after a search. The cursor is iterated forwards past
98 * the current record until a record matching the key-range requirements
99 * is found. ENOENT is returned if the iteration goes past the ending
100 * key.
101 *
102 * The iteration is inclusive of key_beg and can be inclusive or exclusive
103 * of key_end depending on whether HAMMER_CURSOR_END_INCLUSIVE is set.
104 *
105 * When doing an as-of search (cursor->asof != 0), key_beg.create_tid
106 * may be modified by B-Tree functions.
107 *
108 * cursor->key_beg may or may not be modified by this function during
109 * the iteration. XXX future - in case of an inverted lock we may have
110 * to reinitiate the lookup and set key_beg to properly pick up where we
111 * left off.
112 *
113 * If HAMMER_CURSOR_ITERATE_CHECK is set it is possible that the cursor
114 * was reverse indexed due to being moved to a parent while unlocked,
115 * and something else might have inserted an element outside the iteration
116 * range. When this case occurs the iterator just keeps iterating until
117 * it gets back into the iteration range (instead of asserting).
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;
126 hammer_mount_t hmp;
131 /*
132 * Skip past the current record
133 */
141 }
143 /*
144 * HAMMER can wind up being cpu-bound.
145 */
149 }
152 /*
153 * Loop until an element is found or we are done.
154 */
156 /*
157 * We iterate up the tree and then index over one element
158 * while we are at the last element in the current node.
159 *
160 * If we are at the root of the filesystem, cursor_up
161 * returns ENOENT.
162 *
163 * XXX this could be optimized by storing the information in
164 * the parent reference.
165 *
166 * XXX we can lose the node lock temporarily, this could mess
167 * up our scan.
168 */
179 curthread);
180 }
181 KKASSERT(cursor->parent == NULL || cursor->parent->ondisk->elms[cursor->parent_index].internal.subtree_offset == cursor->node->node_offset);
185 /* reload stale pointer */
189 /*
190 * If we are reblocking we want to return internal
191 * nodes. Note that the internal node will be
192 * returned multiple times, on each upward recursion
193 * from its children. The caller selects which
194 * revisit it cares about (usually first or last only).
195 */
199 }
202 }
204 /*
205 * Check internal or leaf element. Determine if the record
206 * at the cursor has gone beyond the end of our range.
207 *
208 * We recurse down through internal nodes.
209 */
223 r,
224 curthread
225 );
233 s
234 );
235 }
240 }
245 }
247 /*
248 * Better not be zero
249 */
253 /*
254 * If running the mirror filter see if we
255 * can skip one or more entire sub-trees.
256 * If we can we return the internal node
257 * and the caller processes the skipped
258 * range (see mirror_read).
259 */
261 HAMMER_CURSOR_MIRROR_FILTERED) {
266 }
267 }
269 /*
270 * Normally it would be impossible for the
271 * cursor to have gotten back-indexed,
272 * but it can happen if a node is deleted
273 * and the cursor is moved to its parent
274 * internal node. ITERATE_CHECK will be set.
275 */
277 HAMMER_CURSOR_ITERATE_CHECK);
279 "DEBUG: Caught parent seek "
281 }
287 /* reload stale pointer */
303 r
304 );
305 }
309 }
311 /*
312 * We support both end-inclusive and
313 * end-exclusive searches.
314 */
319 }
321 /*
322 * If ITERATE_CHECK is set an unlocked cursor may
323 * have been moved to a parent and the iterate can
324 * happen upon elements that are not in the requested
325 * range.
326 */
332 "DEBUG: Caught parent seek "
336 }
337 }
340 /*
341 * Return the element
342 */
349 }
355 }
358 }
359 /*
360 * node pointer invalid after loop
361 */
363 /*
364 * Return entry
365 */
375 );
376 }
378 }
380 }
382 /*
383 * We hit an internal element that we could skip as part of a mirroring
384 * scan. Calculate the entire range being skipped.
385 *
386 * It is important to include any gaps between the parent's left_bound
387 * and the node's left_bound, and same goes for the right side.
388 */
389 static void
391 {
393 hammer_node_ondisk_t ondisk;
394 hammer_btree_elm_t elm;
399 /*
400 * Calculate the skipped range
401 */
405 else
412 }
415 else
418 /*
419 * clip the returned result.
420 */
425 }
427 /*
428 * Iterate in the reverse direction. This is used by the pruning code to
429 * avoid overlapping records.
430 */
431 int
433 {
434 hammer_node_ondisk_t node;
435 hammer_btree_elm_t elm;
440 /* mirror filtering not supported for reverse iteration */
443 /*
444 * Skip past the current record. For various reasons the cursor
445 * may end up set to -1 or set to point at the end of the current
446 * node. These cases must be addressed.
447 */
454 }
458 /*
459 * Loop until an element is found or we are done.
460 */
465 /*
466 * We iterate up the tree and then index over one element
467 * while we are at the last element in the current node.
468 */
474 }
475 /* reload stale pointer */
480 }
482 /*
483 * Check internal or leaf element. Determine if the record
484 * at the cursor has gone beyond the end of our range.
485 *
486 * We recurse down through internal nodes.
487 */
501 r
502 );
510 s
511 );
512 }
517 }
519 /*
520 * It shouldn't be possible to be seeked past key_end,
521 * even if the cursor got moved to a parent.
522 */
525 /*
526 * Better not be zero
527 */
534 /* reload stale pointer */
537 /* this can assign -1 if the leaf was empty */
553 s
554 );
555 }
559 }
561 /*
562 * It shouldn't be possible to be seeked past key_end,
563 * even if the cursor got moved to a parent.
564 */
567 /*
568 * Return the element
569 */
576 }
582 }
585 }
586 /*
587 * node pointer invalid after loop
588 */
590 /*
591 * Return entry
592 */
602 );
603 }
605 }
607 }
609 /*
610 * Lookup cursor->key_beg. 0 is returned on success, ENOENT if the entry
611 * could not be found, EDEADLK if inserting and a retry is needed, and a
612 * fatal error otherwise. When retrying, the caller must terminate the
613 * cursor and reinitialize it. EDEADLK cannot be returned if not inserting.
614 *
615 * The cursor is suitably positioned for a deletion on success, and suitably
616 * positioned for an insertion on ENOENT if HAMMER_CURSOR_INSERT was
617 * specified.
618 *
619 * The cursor may begin anywhere, the search will traverse the tree in
620 * either direction to locate the requested element.
621 *
622 * Most of the logic implementing historical searches is handled here. We
623 * do an initial lookup with create_tid set to the asof TID. Due to the
624 * way records are laid out, a backwards iteration may be required if
625 * ENOENT is returned to locate the historical record. Here's the
626 * problem:
627 *
628 * create_tid: 10 15 20
629 * LEAF1 LEAF2
630 * records: (11) (18)
631 *
632 * Lets say we want to do a lookup AS-OF timestamp 17. We will traverse
633 * LEAF2 but the only record in LEAF2 has a create_tid of 18, which is
634 * not visible and thus causes ENOENT to be returned. We really need
635 * to check record 11 in LEAF1. If it also fails then the search fails
636 * (e.g. it might represent the range 11-16 and thus still not match our
637 * AS-OF timestamp of 17). Note that LEAF1 could be empty, requiring
638 * further iterations.
639 *
640 * If this case occurs btree_search() will set HAMMER_CURSOR_CREATE_CHECK
641 * and the cursor->create_check TID if an iteration might be needed.
642 * In the above example create_check would be set to 14.
643 */
644 int
646 {
661 /*
662 * Stop if no error.
663 * Stop if error other then ENOENT.
664 * Stop if ENOENT and not special case.
665 */
667 }
671 }
673 /* loop */
674 }
677 }
681 }
683 /*
684 * Execute the logic required to start an iteration. The first record
685 * located within the specified range is returned and iteration control
686 * flags are adjusted for successive hammer_btree_iterate() calls.
687 *
688 * Set ATEDISK so a low-level caller can call btree_first/btree_iterate
689 * in a loop without worrying about it. Higher-level merged searches will
690 * adjust the flag appropriately.
691 */
692 int
694 {
701 }
704 }
706 /*
707 * Similarly but for an iteration in the reverse direction.
708 *
709 * Set ATEDISK when iterating backwards to skip the current entry,
710 * which after an ENOENT lookup will be pointing beyond our end point.
711 *
712 * Set ATEDISK so a low-level caller can call btree_last/btree_iterate_reverse
713 * in a loop without worrying about it. Higher-level merged searches will
714 * adjust the flag appropriately.
715 */
716 int
718 {
730 }
733 }
735 /*
736 * Extract the record and/or data associated with the cursor's current
737 * position. Any prior record or data stored in the cursor is replaced.
738 * The cursor must be positioned at a leaf node.
739 *
740 * NOTE: All extractions occur at the leaf of the B-Tree.
741 */
742 int
744 {
745 hammer_node_ondisk_t node;
746 hammer_btree_elm_t elm;
747 hammer_off_t data_off;
748 hammer_mount_t hmp;
752 /*
753 * The case where the data reference resolves to the same buffer
754 * as the record reference must be handled.
755 */
761 /*
762 * There is nothing to extract for an internal element.
763 */
767 /*
768 * Only record types have data.
769 */
782 /*
783 * Load the data
784 */
789 /*
790 * Mark the data buffer as not being meta-data if it isn't
791 * meta-data (sometimes bulk data is accessed via a volume
792 * block device).
793 */
802 }
803 }
805 /*
806 * Deal with CRC errors on the extracted data.
807 */
816 else
818 }
820 }
823 /*
824 * Insert a leaf element into the B-Tree at the current cursor position.
825 * The cursor is positioned such that the element at and beyond the cursor
826 * are shifted to make room for the new record.
827 *
828 * The caller must call hammer_btree_lookup() with the HAMMER_CURSOR_INSERT
829 * flag set and that call must return ENOENT before this function can be
830 * called.
831 *
832 * The caller may depend on the cursor's exclusive lock after return to
833 * interlock frontend visibility (see HAMMER_RECF_CONVERT_DELETE).
834 *
835 * ENOSPC is returned if there is no room to insert a new record.
836 */
837 int
840 {
841 hammer_node_ondisk_t node;
850 /*
851 * Insert the element at the leaf node and update the count in the
852 * parent. It is possible for parent to be NULL, indicating that
853 * the filesystem's ROOT B-Tree node is a leaf itself, which is
854 * possible. The root inode can never be deleted so the leaf should
855 * never be empty.
856 *
857 * Remember that the right-hand boundary is not included in the
858 * count.
859 */
869 }
874 /*
875 * Update the leaf node's aggregate mirror_tid for mirroring
876 * support.
877 */
881 }
885 }
888 /*
889 * Debugging sanity checks.
890 */
895 }
900 }
902 /*
903 * Delete a record from the B-Tree at the current cursor position.
904 * The cursor is positioned such that the current element is the one
905 * to be deleted.
906 *
907 * On return the cursor will be positioned after the deleted element and
908 * MAY point to an internal node. It will be suitable for the continuation
909 * of an iteration but not for an insertion or deletion.
910 *
911 * Deletions will attempt to partially rebalance the B-Tree in an upward
912 * direction, but will terminate rather then deadlock. Empty internal nodes
913 * are never allowed by a deletion which deadlocks may end up giving us an
914 * empty leaf. The pruner will clean up and rebalance the tree.
915 *
916 * This function can return EDEADLK, requiring the caller to retry the
917 * operation after clearing the deadlock.
918 */
919 int
921 {
922 hammer_node_ondisk_t ondisk;
923 hammer_node_t node;
924 hammer_node_t parent;
933 /*
934 * Delete the element from the leaf node.
935 *
936 * Remember that leaf nodes do not have boundaries.
937 */
948 }
953 /*
954 * Validate local parent
955 */
961 }
963 /*
964 * If the leaf becomes empty it must be detached from the parent,
965 * potentially recursing through to the filesystem root.
966 *
967 * This may reposition the cursor at one of the parent's of the
968 * current node.
969 *
970 * Ignore deadlock errors, that simply means that btree_remove
971 * was unable to recurse and had to leave us with an empty leaf.
972 */
980 }
984 }
986 /*
987 * PRIMAY B-TREE SEARCH SUPPORT PROCEDURE
988 *
989 * Search the filesystem B-Tree for cursor->key_beg, return the matching node.
990 *
991 * The search can begin ANYWHERE in the B-Tree. As a first step the search
992 * iterates up the tree as necessary to properly position itself prior to
993 * actually doing the sarch.
994 *
995 * INSERTIONS: The search will split full nodes and leaves on its way down
996 * and guarentee that the leaf it ends up on is not full. If we run out
997 * of space the search continues to the leaf (to position the cursor for
998 * the spike), but ENOSPC is returned.
999 *
1000 * The search is only guarenteed to end up on a leaf if an error code of 0
1001 * is returned, or if inserting and an error code of ENOENT is returned.
1002 * Otherwise it can stop at an internal node. On success a search returns
1003 * a leaf node.
1004 *
1005 * COMPLEXITY WARNING! This is the core B-Tree search code for the entire
1006 * filesystem, and it is not simple code. Please note the following facts:
1007 *
1008 * - Internal node recursions have a boundary on the left AND right. The
1009 * right boundary is non-inclusive. The create_tid is a generic part
1010 * of the key for internal nodes.
1011 *
1012 * - Leaf nodes contain terminal elements only now.
1013 *
1014 * - Filesystem lookups typically set HAMMER_CURSOR_ASOF, indicating a
1015 * historical search. ASOF and INSERT are mutually exclusive. When
1016 * doing an as-of lookup btree_search() checks for a right-edge boundary
1017 * case. If while recursing down the left-edge differs from the key
1018 * by ONLY its create_tid, HAMMER_CURSOR_CREATE_CHECK is set along
1019 * with cursor->create_check. This is used by btree_lookup() to iterate.
1020 * The iteration backwards because as-of searches can wind up going
1021 * down the wrong branch of the B-Tree.
1022 */
1023 static
1024 int
1026 {
1027 hammer_node_ondisk_t node;
1028 hammer_btree_elm_t elm;
1047 curthread
1048 );
1061 );
1062 }
1064 /*
1065 * Move our cursor up the tree until we find a node whos range covers
1066 * the key we are trying to locate.
1067 *
1068 * The left bound is inclusive, the right bound is non-inclusive.
1069 * It is ok to cursor up too far.
1070 */
1081 }
1083 /*
1084 * The delete-checks below are based on node, not parent. Set the
1085 * initial delete-check based on the parent.
1086 */
1091 }
1093 /*
1094 * We better have ended up with a node somewhere.
1095 */
1098 /*
1099 * If we are inserting we can't start at a full node if the parent
1100 * is also full (because there is no way to split the node),
1101 * continue running up the tree until the requirement is satisfied
1102 * or we hit the root of the filesystem.
1103 *
1104 * (If inserting we aren't doing an as-of search so we don't have
1105 * to worry about create_check).
1106 */
1114 }
1118 }
1121 /* node may have become stale */
1124 }
1126 /*
1127 * Push down through internal nodes to locate the requested key.
1128 */
1131 /*
1132 * Scan the node to find the subtree index to push down into.
1133 * We go one-past, then back-up.
1134 *
1135 * We must proactively remove deleted elements which may
1136 * have been left over from a deadlocked btree_remove().
1137 *
1138 * The left and right boundaries are included in the loop
1139 * in order to detect edge cases.
1140 *
1141 * If the separator only differs by create_tid (r == 1)
1142 * and we are doing an as-of search, we may end up going
1143 * down a branch to the left of the one containing the
1144 * desired key. This requires numerous special cases.
1145 */
1151 }
1153 /*
1154 * Try to shortcut the search before dropping into the
1155 * linear loop. Locate the first node where r <= 1.
1156 */
1165 }
1172 }
1174 }
1178 }
1180 /*
1181 * These cases occur when the parent's idea of the boundary
1182 * is wider then the child's idea of the boundary, and
1183 * require special handling. If not inserting we can
1184 * terminate the search early for these cases but the
1185 * child's boundaries cannot be unconditionally modified.
1186 */
1188 /*
1189 * If i == 0 the search terminated to the LEFT of the
1190 * left_boundary but to the RIGHT of the parent's left
1191 * boundary.
1192 */
1193 u_int8_t save;
1197 /*
1198 * If we aren't inserting we can stop here.
1199 */
1204 }
1206 /*
1207 * Correct a left-hand boundary mismatch.
1208 *
1209 * We can only do this if we can upgrade the lock,
1210 * and synchronized as a background cursor (i.e.
1211 * inserting or pruning).
1212 *
1213 * WARNING: We can only do this if inserting, i.e.
1214 * we are running on the backend.
1215 */
1226 /*
1227 * If i == node->count + 1 the search terminated to
1228 * the RIGHT of the right boundary but to the LEFT
1229 * of the parent's right boundary. If we aren't
1230 * inserting we can stop here.
1231 *
1232 * Note that the last element in this case is
1233 * elms[i-2] prior to adjustments to 'i'.
1234 */
1240 }
1242 /*
1243 * Correct a right-hand boundary mismatch.
1244 * (actual push-down record is i-2 prior to
1245 * adjustments to i).
1246 *
1247 * We can only do this if we can upgrade the lock,
1248 * and synchronized as a background cursor (i.e.
1249 * inserting or pruning).
1250 *
1251 * WARNING: We can only do this if inserting, i.e.
1252 * we are running on the backend.
1253 */
1264 /*
1265 * The push-down index is now i - 1. If we had
1266 * terminated on the right boundary this will point
1267 * us at the last element.
1268 */
1270 }
1278 i,
1284 );
1285 }
1287 /*
1288 * We better have a valid subtree offset.
1289 */
1292 /*
1293 * Handle insertion and deletion requirements.
1294 *
1295 * If inserting split full nodes. The split code will
1296 * adjust cursor->node and cursor->index if the current
1297 * index winds up in the new node.
1298 *
1299 * If inserting and a left or right edge case was detected,
1300 * we cannot correct the left or right boundary and must
1301 * prepend and append an empty leaf node in order to make
1302 * the boundary correction.
1303 *
1304 * If we run out of space we set enospc and continue on
1305 * to a leaf to provide the spike code with a good point
1306 * of entry.
1307 */
1315 }
1316 /*
1317 * reload stale pointers
1318 */
1321 }
1322 }
1324 /*
1325 * Push down (push into new node, existing node becomes
1326 * the parent) and continue the search.
1327 */
1329 /* node may have become stale */
1333 }
1335 /*
1336 * We are at a leaf, do a linear search of the key array.
1337 *
1338 * On success the index is set to the matching element and 0
1339 * is returned.
1340 *
1341 * On failure the index is set to the insertion point and ENOENT
1342 * is returned.
1343 *
1344 * Boundaries are not stored in leaf nodes, so the index can wind
1345 * up to the left of element 0 (index == 0) or past the end of
1346 * the array (index == node->count). It is also possible that the
1347 * leaf might be empty.
1348 */
1356 }
1358 /*
1359 * Try to shortcut the search before dropping into the
1360 * linear loop. Locate the first node where r <= 1.
1361 */
1372 /*
1373 * We are at a record element. Stop if we've flipped past
1374 * key_beg, not counting the create_tid test. Allow the
1375 * r == 1 case (key_beg > element but differs only by its
1376 * create_tid) to fall through to the AS-OF check.
1377 */
1385 }
1387 /*
1388 * Check our as-of timestamp against the element.
1389 */
1395 }
1396 /* success */
1401 }
1402 /* success */
1403 }
1409 }
1411 }
1413 /*
1414 * The search of the leaf node failed. i is the insertion point.
1415 */
1416 failed:
1420 }
1422 /*
1423 * No exact match was found, i is now at the insertion point.
1424 *
1425 * If inserting split a full leaf before returning. This
1426 * may have the side effect of adjusting cursor->node and
1427 * cursor->index.
1428 */
1437 }
1438 /*
1439 * reload stale pointers
1440 */
1441 /* NOT USED
1442 i = cursor->index;
1443 node = &cursor->node->internal;
1444 */
1445 }
1447 /*
1448 * We reached a leaf but did not find the key we were looking for.
1449 * If this is an insert we will be properly positioned for an insert
1450 * (ENOENT) or spike (ENOSPC) operation.
1451 */
1453 done:
1455 }
1457 /*
1458 * Heuristical search for the first element whos comparison is <= 1. May
1459 * return an index whos compare result is > 1 but may only return an index
1460 * whos compare result is <= 1 if it is the first element with that result.
1461 */
1462 int
1464 {
1470 /*
1471 * Don't bother if the node does not have very many elements
1472 */
1483 }
1484 }
1486 }
1489 /************************************************************************
1490 * SPLITTING AND MERGING *
1491 ************************************************************************
1492 *
1493 * These routines do all the dirty work required to split and merge nodes.
1494 */
1496 /*
1497 * Split an internal node into two nodes and move the separator at the split
1498 * point to the parent.
1499 *
1500 * (cursor->node, cursor->index) indicates the element the caller intends
1501 * to push into. We will adjust node and index if that element winds
1502 * up in the split node.
1503 *
1504 * If we are at the root of the filesystem a new root must be created with
1505 * two elements, one pointing to the original root and one pointing to the
1506 * newly allocated split node.
1507 */
1508 static
1509 int
1511 {
1512 hammer_node_ondisk_t ondisk;
1513 hammer_node_t node;
1514 hammer_node_t parent;
1515 hammer_node_t new_node;
1516 hammer_btree_elm_t elm;
1517 hammer_btree_elm_t parent_elm;
1520 hammer_off_t hint;
1536 /*
1537 * Calculate the split point. If the insertion point is at the
1538 * end of the leaf we adjust the split point significantly to the
1539 * right to try to optimize node fill and flag it. If we hit
1540 * that same leaf again our heuristic failed and we don't try
1541 * to optimize node fill (it could lead to a degenerate case).
1542 */
1551 /*
1552 * We are splitting but elms[split] will be promoted to
1553 * the parent, leaving the right hand node with one less
1554 * element. If the insertion point will be on the
1555 * left-hand side adjust the split point to give the
1556 * right hand side one additional node.
1557 */
1561 }
1563 /*
1564 * If we are at the root of the filesystem, create a new root node
1565 * with 1 element and split normally. Avoid making major
1566 * modifications until we know the whole operation will work.
1567 */
1585 /* ondisk->elms[1].base.btype - not used */
1592 }
1594 /*
1595 * Calculate a hint for the allocation of the new B-Tree node.
1596 * The most likely expansion is coming from the insertion point
1597 * at cursor->index, so try to localize the allocation of our
1598 * new node to accomodate that sub-tree.
1599 *
1600 * Use the right-most sub-tree when expandinging on the right edge.
1601 * This is a very common case when copying a directory tree.
1602 */
1605 else
1608 /*
1609 * Split node into new_node at the split point.
1610 *
1611 * B O O O P N N B <-- P = node->elms[split] (index 4)
1612 * 0 1 2 3 4 5 6 <-- subtree indices
1613 *
1614 * x x P x x
1615 * s S S s
1616 * / \
1617 * B O O O B B N N B <--- inner boundary points are 'P'
1618 * 0 1 2 3 4 5 6
1619 */
1626 }
1628 }
1631 /*
1632 * Create the new node. P becomes the left-hand boundary in the
1633 * new node. Copy the right-hand boundary as well.
1634 *
1635 * elm is the new separator.
1636 */
1650 /*
1651 * Cleanup the original node. Elm (P) becomes the new boundary,
1652 * its subtree_offset was moved to the new node. If we had created
1653 * a new root its parent pointer may have changed.
1654 */
1658 /*
1659 * Insert the separator into the parent, fixup the parent's
1660 * reference to the original node, and reference the new node.
1661 * The separator is P.
1662 *
1663 * Remember that base.count does not include the right-hand boundary.
1664 */
1679 /*
1680 * The children of new_node need their parent pointer set to new_node.
1681 * The children have already been locked by
1682 * hammer_btree_lock_children().
1683 */
1689 }
1690 }
1693 /*
1694 * The filesystem's root B-Tree pointer may have to be updated.
1695 */
1697 hammer_volume_t volume;
1703 vol0_btree_root);
1710 }
1713 }
1716 /*
1717 * Ok, now adjust the cursor depending on which element the original
1718 * index was pointing at. If we are >= the split point the push node
1719 * is now in the new node.
1720 *
1721 * NOTE: If we are at the split point itself we cannot stay with the
1722 * original node because the push index will point at the right-hand
1723 * boundary, which is illegal.
1724 *
1725 * NOTE: The cursor's parent or parent_index must be adjusted for
1726 * the case where a new parent (new root) was created, and the case
1727 * where the cursor is now pointing at the split node.
1728 */
1739 }
1741 /*
1742 * Fixup left and right bounds
1743 */
1752 done:
1756 }
1758 /*
1759 * Same as the above, but splits a full leaf node.
1760 *
1761 * This function
1762 */
1763 static
1764 int
1766 {
1767 hammer_node_ondisk_t ondisk;
1768 hammer_node_t parent;
1769 hammer_node_t leaf;
1770 hammer_mount_t hmp;
1771 hammer_node_t new_leaf;
1772 hammer_btree_elm_t elm;
1773 hammer_btree_elm_t parent_elm;
1774 hammer_base_elm_t mid_boundary;
1775 hammer_off_t hint;
1791 /*
1792 * Calculate the split point. If the insertion point is at the
1793 * end of the leaf we adjust the split point significantly to the
1794 * right to try to optimize node fill and flag it. If we hit
1795 * that same leaf again our heuristic failed and we don't try
1796 * to optimize node fill (it could lead to a degenerate case).
1797 *
1798 * Spikes are made up of two leaf elements which cannot be
1799 * safely split.
1800 */
1810 }
1812 #if 0
1813 /*
1814 * If the insertion point is at the split point shift the
1815 * split point left so we don't have to worry about
1816 */
1819 #endif
1832 /*
1833 * If we are at the root of the tree, create a new root node with
1834 * 1 element and split normally. Avoid making major modifications
1835 * until we know the whole operation will work.
1836 */
1853 /* ondisk->elms[1].base.btype = not used */
1861 }
1863 /*
1864 * Calculate a hint for the allocation of the new B-Tree leaf node.
1865 * For now just try to localize it within the same bigblock as
1866 * the current leaf.
1867 *
1868 * If the insertion point is at the end of the leaf we recognize a
1869 * likely append sequence of some sort (data, meta-data, inodes,
1870 * whatever). Set the hint to zero to allocate out of linear space
1871 * instead of trying to completely fill previously hinted space.
1872 *
1873 * This also sets the stage for recursive splits to localize using
1874 * the new space.
1875 */
1879 else
1882 /*
1883 * Split leaf into new_leaf at the split point. Select a separator
1884 * value in-between the two leafs but with a bent towards the right
1885 * leaf since comparisons use an 'elm >= separator' inequality.
1886 *
1887 * L L L L L L L L
1888 *
1889 * x x P x x
1890 * s S S s
1891 * / \
1892 * L L L L L L L L
1893 */
1900 }
1902 }
1905 /*
1906 * Create the new node and copy the leaf elements from the split
1907 * point on to the new node.
1908 */
1922 /*
1923 * Cleanup the original node. Because this is a leaf node and
1924 * leaf nodes do not have a right-hand boundary, there
1925 * aren't any special edge cases to clean up. We just fixup the
1926 * count.
1927 */
1930 /*
1931 * Insert the separator into the parent, fixup the parent's
1932 * reference to the original node, and reference the new node.
1933 * The separator is P.
1934 *
1935 * Remember that base.count does not include the right-hand boundary.
1936 * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1937 */
1955 /*
1956 * The filesystem's root B-Tree pointer may have to be updated.
1957 */
1959 hammer_volume_t volume;
1965 vol0_btree_root);
1972 }
1975 }
1978 /*
1979 * Ok, now adjust the cursor depending on which element the original
1980 * index was pointing at. If we are >= the split point the push node
1981 * is now in the new node.
1982 *
1983 * NOTE: If we are at the split point itself we need to select the
1984 * old or new node based on where key_beg's insertion point will be.
1985 * If we pick the wrong side the inserted element will wind up in
1986 * the wrong leaf node and outside that node's bounds.
1987 */
2000 }
2002 /*
2003 * Fixup left and right bounds
2004 */
2009 /*
2010 * Assert that the bounds are correct.
2011 */
2019 done:
2022 }
2024 #if 0
2026 /*
2027 * Recursively correct the right-hand boundary's create_tid to (tid) as
2028 * long as the rest of the key matches. We have to recurse upward in
2029 * the tree as well as down the left side of each parent's right node.
2030 *
2031 * Return EDEADLK if we were only partially successful, forcing the caller
2032 * to try again. The original cursor is not modified. This routine can
2033 * also fail with EDEADLK if it is forced to throw away a portion of its
2034 * record history.
2035 *
2036 * The caller must pass a downgraded cursor to us (otherwise we can't dup it).
2037 */
2040 hammer_node_t node;
2042 };
2046 int
2048 {
2051 hammer_base_elm_t elm;
2052 hammer_node_t orig_node;
2060 /*
2061 * Save our position so we can restore it on return. This also
2062 * gives us a stable 'elm'.
2063 */
2070 /*
2071 * Now build a list of parents going up, allocating a rhb
2072 * structure for each one.
2073 */
2075 /*
2076 * Stop if we no longer have any right-bounds to fix up
2077 */
2082 }
2084 /*
2085 * Stop if the right-hand bound's create_tid does not
2086 * need to be corrected.
2087 */
2099 }
2101 /*
2102 * now safely adjust the right hand bound for each rhb. This may
2103 * also require taking the right side of the tree and iterating down
2104 * ITS left side.
2105 */
2118 /*
2119 * Right-boundary for parent at internal node
2120 * is one element to the right of the element whos
2121 * right boundary needs adjusting. We must then
2122 * traverse down the left side correcting any left
2123 * bounds (which may now be too far to the left).
2124 */
2132 }
2133 }
2135 /*
2136 * Cleanup
2137 */
2143 }
2148 }
2150 /*
2151 * Similar to rhb (in fact, rhb calls lhb), but corrects the left hand
2152 * bound going downward starting at the current cursor position.
2153 *
2154 * This function does not restore the cursor after use.
2155 */
2156 int
2158 {
2160 hammer_base_elm_t elm;
2161 hammer_base_elm_t cmp;
2171 /*
2172 * Record the node and traverse down the left-hand side for all
2173 * matching records needing a boundary correction.
2174 */
2185 /*
2186 * Nothing to traverse down if we are at the right
2187 * boundary of an internal node.
2188 */
2196 }
2206 }
2210 }
2212 /*
2213 * Now we can safely adjust the left-hand boundary from the bottom-up.
2214 * The last element we remove from the list is the caller's right hand
2215 * boundary, which must also be adjusted.
2216 */
2235 }
2236 }
2238 /*
2239 * Cleanup
2240 */
2246 }
2248 }
2250 #endif
2252 /*
2253 * Attempt to remove the locked, empty or want-to-be-empty B-Tree node at
2254 * (cursor->node). Returns 0 on success, EDEADLK if we could not complete
2255 * the operation due to a deadlock, or some other error.
2256 *
2257 * This routine is initially called with an empty leaf and may be
2258 * recursively called with single-element internal nodes.
2259 *
2260 * It should also be noted that when removing empty leaves we must be sure
2261 * to test and update mirror_tid because another thread may have deadlocked
2262 * against us (or someone) trying to propagate it up and cannot retry once
2263 * the node has been deleted.
2264 *
2265 * On return the cursor may end up pointing to an internal node, suitable
2266 * for further iteration but not for an immediate insertion or deletion.
2267 */
2268 static int
2270 {
2271 hammer_node_ondisk_t ondisk;
2272 hammer_btree_elm_t elm;
2273 hammer_node_t node;
2274 hammer_node_t parent;
2280 /*
2281 * When deleting the root of the filesystem convert it to
2282 * an empty leaf node. Internal nodes cannot be empty.
2283 */
2294 }
2298 /*
2299 * Attempt to remove the parent's reference to the child. If the
2300 * parent would become empty we have to recurse. If we fail we
2301 * leave the parent pointing to an empty leaf node.
2302 *
2303 * We have to recurse successfully before we can delete the internal
2304 * node as it is illegal to have empty internal nodes. Even though
2305 * the operation may be aborted we must still fixup any unlocked
2306 * cursors as if we had deleted the element prior to recursing
2307 * (by calling hammer_cursor_deleted_element()) so those cursors
2308 * are properly forced up the chain by the recursion.
2309 */
2311 /*
2312 * This special cursor_up_locked() call leaves the original
2313 * node exclusively locked and referenced, leaves the
2314 * original parent locked (as the new node), and locks the
2315 * new parent. It can return EDEADLK.
2316 *
2317 * We cannot call hammer_cursor_removed_node() until we are
2318 * actually able to remove the node. If we did then tracked
2319 * cursors in the middle of iterations could be repointed
2320 * to a parent node. If this occurs they could end up
2321 * scanning newly inserted records into the node (that could
2322 * not be deleted) when they push down again.
2323 *
2324 * Due to the way the recursion works the final parent is left
2325 * in cursor->parent after the recursion returns. Each
2326 * layer on the way back up is thus able to call
2327 * hammer_cursor_removed_node() and 'jump' the node up to
2328 * the (same) final parent.
2329 *
2330 * NOTE! The local variable 'parent' is invalid after we
2331 * call hammer_cursor_up_locked().
2332 */
2352 /*
2353 * Defer parent removal because we could not
2354 * get the lock, just let the leaf remain
2355 * empty.
2356 */
2357 /**/
2358 }
2362 /*
2363 * Defer parent removal because we could not
2364 * get the lock, just let the leaf remain
2365 * empty.
2366 */
2367 /**/
2368 }
2380 /*
2381 * We must retain the highest mirror_tid. The deleted
2382 * range is now encompassed by the element to the left.
2383 * If we are already at the left edge the new left edge
2384 * inherits mirror_tid.
2385 *
2386 * Note that bounds of the parent to our parent may create
2387 * a gap to the left of our left-most node or to the right
2388 * of our right-most node. The gap is silently included
2389 * in the mirror_tid's area of effect from the point of view
2390 * of the scan.
2391 */
2397 }
2403 }
2404 }
2406 /*
2407 * Delete the subtree reference in the parent. Include
2408 * boundary element at end.
2409 */
2419 /*
2420 * cursor->node is invalid, cursor up to make the cursor
2421 * valid again.
2422 */
2424 }
2426 }
2428 /*
2429 * Propagate cursor->trans->tid up the B-Tree starting at the current
2430 * cursor position using pseudofs info gleaned from the passed inode.
2431 *
2432 * The passed inode has no relationship to the cursor position other
2433 * then being in the same pseudofs as the insertion or deletion we
2434 * are propagating the mirror_tid for.
2435 *
2436 * WARNING! Because we push and pop the passed cursor, it may be
2437 * modified by other B-Tree operations while it is unlocked
2438 * and things like the node & leaf pointers, and indexes might
2439 * change.
2440 */
2441 void
2443 hammer_pseudofs_inmem_t pfsm,
2444 hammer_btree_leaf_elm_t leaf)
2445 {
2446 hammer_cursor_t ncursor;
2447 hammer_tid_t mirror_tid;
2450 /*
2451 * We do not propagate a mirror_tid if the filesystem was mounted
2452 * in no-mirror mode.
2453 */
2457 /*
2458 * This is a bit of a hack because we cannot deadlock or return
2459 * EDEADLK here. The related operation has already completed and
2460 * we must propagate the mirror_tid now regardless.
2461 *
2462 * Generate a new cursor which inherits the original's locks and
2463 * unlock the original. Use the new cursor to propagate the
2464 * mirror_tid. Then clean up the new cursor and reacquire locks
2465 * on the original.
2466 *
2467 * hammer_dup_cursor() cannot dup locks. The dup inherits the
2468 * original's locks and the original is tracked and must be
2469 * re-locked.
2470 */
2477 /* WARNING: cursor's leaf pointer may change after pop */
2478 }
2481 /*
2482 * Propagate a mirror TID update upwards through the B-Tree to the root.
2483 *
2484 * A locked internal node must be passed in. The node will remain locked
2485 * on return.
2486 *
2487 * This function syncs mirror_tid at the specified internal node's element,
2488 * adjusts the node's aggregation mirror_tid, and then recurses upwards.
2489 */
2490 static int
2492 {
2493 hammer_btree_internal_elm_t elm;
2494 hammer_node_t node;
2502 /*
2503 * We can ignore HAMMER_CURSOR_ITERATE_CHECK, the
2504 * cursor will still be properly positioned for
2505 * mirror propagation, just not for iterations.
2506 */
2510 }
2514 /*
2515 * If the cursor deadlocked it could end up at a leaf
2516 * after we lost the lock.
2517 */
2522 /*
2523 * Adjust the node's element
2524 */
2538 }
2541 /*
2542 * Adjust the node's mirror_tid aggregator
2543 */
2554 }
2555 }
2559 }
2561 hammer_node_t
2564 {
2565 hammer_node_t parent;
2566 hammer_btree_elm_t elm;
2569 /*
2570 * Get the node
2571 */
2576 }
2579 /*
2580 * Lock the node
2581 */
2587 }
2590 }
2592 /*
2593 * Figure out which element in the parent is pointing to the
2594 * child.
2595 */
2601 }
2607 }
2611 }
2615 }
2617 /*
2618 * The element (elm) has been moved to a new internal node (node).
2619 *
2620 * If the element represents a pointer to an internal node that node's
2621 * parent must be adjusted to the element's new location.
2622 *
2623 * XXX deadlock potential here with our exclusive locks
2624 */
2625 int
2627 hammer_btree_elm_t elm)
2628 {
2629 hammer_node_t child;
2644 }
2648 }
2650 }
2652 /*
2653 * Initialize the root of a recursive B-Tree node lock list structure.
2654 */
2655 void
2657 {
2665 }
2667 /*
2668 * Exclusively lock all the children of node. This is used by the split
2669 * code to prevent anyone from accessing the children of a cursor node
2670 * while we fix-up its parent offset.
2671 *
2672 * If we don't lock the children we can really mess up cursors which block
2673 * trying to cursor-up into our node.
2674 *
2675 * On failure EDEADLK (or some other error) is returned. If a deadlock
2676 * error is returned the cursor is adjusted to block on termination.
2677 *
2678 * The caller is responsible for managing parent->node, the root's node
2679 * is usually aliased from a cursor.
2680 */
2681 int
2683 hammer_node_lock_t parent)
2684 {
2685 hammer_node_t node;
2686 hammer_node_lock_t item;
2687 hammer_node_ondisk_t ondisk;
2688 hammer_btree_elm_t elm;
2689 hammer_node_t child;
2699 /*
2700 * We really do not want to block on I/O with exclusive locks held,
2701 * pre-get the children before trying to lock the mess. This is
2702 * only done one-level deep for now.
2703 */
2710 }
2716 }
2718 /*
2719 * Do it for real
2720 */
2736 }
2742 }
2755 /*
2756 * Recurse (used by the rebalancing code)
2757 */
2760 cursor,
2762 item);
2763 }
2764 }
2765 }
2766 }
2770 }
2772 /*
2773 * Create an in-memory copy of all B-Tree nodes listed, recursively,
2774 * including the parent.
2775 */
2776 void
2778 {
2780 hammer_node_lock_t item;
2784 M_WAITOK);
2786 }
2789 }
2790 }
2792 /*
2793 * Recursively sync modified copies to the media.
2794 */
2795 int
2797 {
2798 hammer_node_lock_t item;
2809 }
2810 }
2813 }
2815 }
2817 /*
2818 * Release previously obtained node locks. The caller is responsible for
2819 * cleaning up parent->node itself (its usually just aliased from a cursor),
2820 * but this function will take care of the copies.
2821 */
2822 void
2824 {
2825 hammer_node_lock_t item;
2830 }
2837 }
2838 }
2840 /************************************************************************
2841 * MISCELLANIOUS SUPPORT *
2842 ************************************************************************/
2844 /*
2845 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
2846 *
2847 * Note that for this particular function a return value of -1, 0, or +1
2848 * can denote a match if create_tid is otherwise discounted. A create_tid
2849 * of zero is considered to be 'infinity' in comparisons.
2850 *
2851 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
2852 */
2853 int
2855 {
2876 /*
2877 * A create_tid of zero indicates a record which is undeletable
2878 * and must be considered to have a value of positive infinity.
2879 */
2884 }
2892 }
2894 /*
2895 * Test a timestamp against an element to determine whether the
2896 * element is visible. A timestamp of 0 means 'infinity'.
2897 */
2898 int
2900 {
2905 }
2911 }
2913 /*
2914 * Create a separator half way inbetween key1 and key2. For fields just
2915 * one unit apart, the separator will match key2. key1 is on the left-hand
2916 * side and key2 is on the right-hand side.
2917 *
2918 * key2 must be >= the separator. It is ok for the separator to match key2.
2919 *
2920 * NOTE: Even if key1 does not match key2, the separator may wind up matching
2921 * key2.
2922 *
2923 * NOTE: It might be beneficial to just scrap this whole mess and just
2924 * set the separator to key2.
2925 */
2926 #define MAKE_SEPARATOR(key1, key2, dest, field) \
2927 dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
2929 static void
2931 hammer_base_elm_t dest)
2932 {
2947 /*
2948 * Don't bother creating a separator for
2949 * create_tid, which also conveniently avoids
2950 * having to handle the create_tid == 0
2951 * (infinity) case. Just leave create_tid
2952 * set to key2.
2953 *
2954 * Worst case, dest matches key2 exactly,
2955 * which is acceptable.
2956 */
2957 }
2958 }
2959 }
2960 }
2962 #undef MAKE_SEPARATOR
2964 /*
2965 * Return whether a generic internal or leaf node is full
2966 */
2967 static int
2969 {
2981 }
2983 }
2985 #if 0
2986 static int
2988 {
2994 }
2995 #endif
2997 void
2999 {
3000 hammer_btree_elm_t elm;
3007 /*
3008 * Dump both boundary elements if an internal node
3009 */
3014 }
3019 }
3020 }
3021 }
3023 void
3025 {
3049 }
3050 }