| blob | 9cc7397a6316f155639a7422d22d2db69c19ee1b |
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 * NOTE! EDEADLK *CANNOT* be returned by this procedure.
114 */
115 int
117 {
118 hammer_node_ondisk_t node;
119 hammer_btree_elm_t elm;
120 hammer_mount_t hmp;
125 /*
126 * Skip past the current record
127 */
135 }
137 /*
138 * HAMMER can wind up being cpu-bound.
139 */
143 }
146 /*
147 * Loop until an element is found or we are done.
148 */
150 /*
151 * We iterate up the tree and then index over one element
152 * while we are at the last element in the current node.
153 *
154 * If we are at the root of the filesystem, cursor_up
155 * returns ENOENT.
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 */
173 curthread);
174 }
175 KKASSERT(cursor->parent == NULL || cursor->parent->ondisk->elms[cursor->parent_index].internal.subtree_offset == cursor->node->node_offset);
179 /* reload stale pointer */
183 /*
184 * If we are reblocking we want to return internal
185 * nodes. Note that the internal node will be
186 * returned multiple times, on each upward recursion
187 * from its children. The caller selects which
188 * revisit it cares about (usually first or last only).
189 */
193 }
196 }
198 /*
199 * Check internal or leaf element. Determine if the record
200 * at the cursor has gone beyond the end of our range.
201 *
202 * We recurse down through internal nodes.
203 */
217 r,
218 curthread
219 );
227 s
228 );
229 }
234 }
239 }
242 /*
243 * Better not be zero
244 */
247 /*
248 * If running the mirror filter see if we can skip
249 * one or more entire sub-trees. If we can we
250 * return the internal mode and the caller processes
251 * the skipped range (see mirror_read)
252 */
258 }
259 }
265 /* reload stale pointer */
281 r
282 );
283 }
287 }
289 /*
290 * We support both end-inclusive and
291 * end-exclusive searches.
292 */
297 }
305 }
311 }
314 }
315 /*
316 * node pointer invalid after loop
317 */
319 /*
320 * Return entry
321 */
331 );
332 }
334 }
336 }
338 /*
339 * We hit an internal element that we could skip as part of a mirroring
340 * scan. Calculate the entire range being skipped.
341 *
342 * It is important to include any gaps between the parent's left_bound
343 * and the node's left_bound, and same goes for the right side.
344 */
345 static void
347 {
349 hammer_node_ondisk_t ondisk;
350 hammer_btree_elm_t elm;
355 /*
356 * Calculate the skipped range
357 */
361 else
368 }
371 else
374 /*
375 * clip the returned result.
376 */
381 }
383 /*
384 * Iterate in the reverse direction. This is used by the pruning code to
385 * avoid overlapping records.
386 */
387 int
389 {
390 hammer_node_ondisk_t node;
391 hammer_btree_elm_t elm;
396 /* mirror filtering not supported for reverse iteration */
399 /*
400 * Skip past the current record. For various reasons the cursor
401 * may end up set to -1 or set to point at the end of the current
402 * node. These cases must be addressed.
403 */
410 }
414 /*
415 * Loop until an element is found or we are done.
416 */
421 /*
422 * We iterate up the tree and then index over one element
423 * while we are at the last element in the current node.
424 */
430 }
431 /* reload stale pointer */
436 }
438 /*
439 * Check internal or leaf element. Determine if the record
440 * at the cursor has gone beyond the end of our range.
441 *
442 * We recurse down through internal nodes.
443 */
457 r
458 );
466 s
467 );
468 }
473 }
476 /*
477 * Better not be zero
478 */
485 /* reload stale pointer */
488 /* this can assign -1 if the leaf was empty */
504 s
505 );
506 }
510 }
518 }
524 }
527 }
528 /*
529 * node pointer invalid after loop
530 */
532 /*
533 * Return entry
534 */
544 );
545 }
547 }
549 }
551 /*
552 * Lookup cursor->key_beg. 0 is returned on success, ENOENT if the entry
553 * could not be found, EDEADLK if inserting and a retry is needed, and a
554 * fatal error otherwise. When retrying, the caller must terminate the
555 * cursor and reinitialize it. EDEADLK cannot be returned if not inserting.
556 *
557 * The cursor is suitably positioned for a deletion on success, and suitably
558 * positioned for an insertion on ENOENT if HAMMER_CURSOR_INSERT was
559 * specified.
560 *
561 * The cursor may begin anywhere, the search will traverse the tree in
562 * either direction to locate the requested element.
563 *
564 * Most of the logic implementing historical searches is handled here. We
565 * do an initial lookup with create_tid set to the asof TID. Due to the
566 * way records are laid out, a backwards iteration may be required if
567 * ENOENT is returned to locate the historical record. Here's the
568 * problem:
569 *
570 * create_tid: 10 15 20
571 * LEAF1 LEAF2
572 * records: (11) (18)
573 *
574 * Lets say we want to do a lookup AS-OF timestamp 17. We will traverse
575 * LEAF2 but the only record in LEAF2 has a create_tid of 18, which is
576 * not visible and thus causes ENOENT to be returned. We really need
577 * to check record 11 in LEAF1. If it also fails then the search fails
578 * (e.g. it might represent the range 11-16 and thus still not match our
579 * AS-OF timestamp of 17). Note that LEAF1 could be empty, requiring
580 * further iterations.
581 *
582 * If this case occurs btree_search() will set HAMMER_CURSOR_CREATE_CHECK
583 * and the cursor->create_check TID if an iteration might be needed.
584 * In the above example create_check would be set to 14.
585 */
586 int
588 {
602 /*
603 * Stop if no error.
604 * Stop if error other then ENOENT.
605 * Stop if ENOENT and not special case.
606 */
608 }
612 }
614 /* loop */
615 }
618 }
622 }
624 /*
625 * Execute the logic required to start an iteration. The first record
626 * located within the specified range is returned and iteration control
627 * flags are adjusted for successive hammer_btree_iterate() calls.
628 *
629 * Set ATEDISK so a low-level caller can call btree_first/btree_iterate
630 * in a loop without worrying about it. Higher-level merged searches will
631 * adjust the flag appropriately.
632 */
633 int
635 {
642 }
645 }
647 /*
648 * Similarly but for an iteration in the reverse direction.
649 *
650 * Set ATEDISK when iterating backwards to skip the current entry,
651 * which after an ENOENT lookup will be pointing beyond our end point.
652 *
653 * Set ATEDISK so a low-level caller can call btree_last/btree_iterate_reverse
654 * in a loop without worrying about it. Higher-level merged searches will
655 * adjust the flag appropriately.
656 */
657 int
659 {
671 }
674 }
676 /*
677 * Extract the record and/or data associated with the cursor's current
678 * position. Any prior record or data stored in the cursor is replaced.
679 * The cursor must be positioned at a leaf node.
680 *
681 * NOTE: All extractions occur at the leaf of the B-Tree.
682 */
683 int
685 {
686 hammer_node_ondisk_t node;
687 hammer_btree_elm_t elm;
688 hammer_off_t data_off;
689 hammer_mount_t hmp;
693 /*
694 * The case where the data reference resolves to the same buffer
695 * as the record reference must be handled.
696 */
702 /*
703 * There is nothing to extract for an internal element.
704 */
708 /*
709 * Only record types have data.
710 */
723 /*
724 * Load the data
725 */
730 /*
731 * Mark the data buffer as not being meta-data if it isn't
732 * meta-data (sometimes bulk data is accessed via a volume
733 * block device).
734 */
743 }
744 }
746 /*
747 * Deal with CRC errors on the extracted data.
748 */
757 else
759 }
761 }
764 /*
765 * Insert a leaf element into the B-Tree at the current cursor position.
766 * The cursor is positioned such that the element at and beyond the cursor
767 * are shifted to make room for the new record.
768 *
769 * The caller must call hammer_btree_lookup() with the HAMMER_CURSOR_INSERT
770 * flag set and that call must return ENOENT before this function can be
771 * called.
772 *
773 * The caller may depend on the cursor's exclusive lock after return to
774 * interlock frontend visibility (see HAMMER_RECF_CONVERT_DELETE).
775 *
776 * ENOSPC is returned if there is no room to insert a new record.
777 */
778 int
781 {
782 hammer_node_ondisk_t node;
791 /*
792 * Insert the element at the leaf node and update the count in the
793 * parent. It is possible for parent to be NULL, indicating that
794 * the filesystem's ROOT B-Tree node is a leaf itself, which is
795 * possible. The root inode can never be deleted so the leaf should
796 * never be empty.
797 *
798 * Remember that the right-hand boundary is not included in the
799 * count.
800 */
810 }
815 /*
816 * Update the leaf node's aggregate mirror_tid for mirroring
817 * support.
818 */
822 }
826 }
829 /*
830 * Debugging sanity checks.
831 */
836 }
841 }
843 /*
844 * Delete a record from the B-Tree at the current cursor position.
845 * The cursor is positioned such that the current element is the one
846 * to be deleted.
847 *
848 * On return the cursor will be positioned after the deleted element and
849 * MAY point to an internal node. It will be suitable for the continuation
850 * of an iteration but not for an insertion or deletion.
851 *
852 * Deletions will attempt to partially rebalance the B-Tree in an upward
853 * direction, but will terminate rather then deadlock. Empty internal nodes
854 * are never allowed by a deletion which deadlocks may end up giving us an
855 * empty leaf. The pruner will clean up and rebalance the tree.
856 *
857 * This function can return EDEADLK, requiring the caller to retry the
858 * operation after clearing the deadlock.
859 */
860 int
862 {
863 hammer_node_ondisk_t ondisk;
864 hammer_node_t node;
865 hammer_node_t parent;
874 /*
875 * Delete the element from the leaf node.
876 *
877 * Remember that leaf nodes do not have boundaries.
878 */
889 }
894 /*
895 * Validate local parent
896 */
902 }
904 /*
905 * If the leaf becomes empty it must be detached from the parent,
906 * potentially recursing through to the filesystem root.
907 *
908 * This may reposition the cursor at one of the parent's of the
909 * current node.
910 *
911 * Ignore deadlock errors, that simply means that btree_remove
912 * was unable to recurse and had to leave us with an empty leaf.
913 */
921 }
925 }
927 /*
928 * PRIMAY B-TREE SEARCH SUPPORT PROCEDURE
929 *
930 * Search the filesystem B-Tree for cursor->key_beg, return the matching node.
931 *
932 * The search can begin ANYWHERE in the B-Tree. As a first step the search
933 * iterates up the tree as necessary to properly position itself prior to
934 * actually doing the sarch.
935 *
936 * INSERTIONS: The search will split full nodes and leaves on its way down
937 * and guarentee that the leaf it ends up on is not full. If we run out
938 * of space the search continues to the leaf (to position the cursor for
939 * the spike), but ENOSPC is returned.
940 *
941 * The search is only guarenteed to end up on a leaf if an error code of 0
942 * is returned, or if inserting and an error code of ENOENT is returned.
943 * Otherwise it can stop at an internal node. On success a search returns
944 * a leaf node.
945 *
946 * COMPLEXITY WARNING! This is the core B-Tree search code for the entire
947 * filesystem, and it is not simple code. Please note the following facts:
948 *
949 * - Internal node recursions have a boundary on the left AND right. The
950 * right boundary is non-inclusive. The create_tid is a generic part
951 * of the key for internal nodes.
952 *
953 * - Leaf nodes contain terminal elements only now.
954 *
955 * - Filesystem lookups typically set HAMMER_CURSOR_ASOF, indicating a
956 * historical search. ASOF and INSERT are mutually exclusive. When
957 * doing an as-of lookup btree_search() checks for a right-edge boundary
958 * case. If while recursing down the left-edge differs from the key
959 * by ONLY its create_tid, HAMMER_CURSOR_CREATE_CHECK is set along
960 * with cursor->create_check. This is used by btree_lookup() to iterate.
961 * The iteration backwards because as-of searches can wind up going
962 * down the wrong branch of the B-Tree.
963 */
964 static
965 int
967 {
968 hammer_node_ondisk_t node;
969 hammer_btree_elm_t elm;
988 curthread
989 );
1002 );
1003 }
1005 /*
1006 * Move our cursor up the tree until we find a node whos range covers
1007 * the key we are trying to locate.
1008 *
1009 * The left bound is inclusive, the right bound is non-inclusive.
1010 * It is ok to cursor up too far.
1011 */
1022 }
1024 /*
1025 * The delete-checks below are based on node, not parent. Set the
1026 * initial delete-check based on the parent.
1027 */
1032 }
1034 /*
1035 * We better have ended up with a node somewhere.
1036 */
1039 /*
1040 * If we are inserting we can't start at a full node if the parent
1041 * is also full (because there is no way to split the node),
1042 * continue running up the tree until the requirement is satisfied
1043 * or we hit the root of the filesystem.
1044 *
1045 * (If inserting we aren't doing an as-of search so we don't have
1046 * to worry about create_check).
1047 */
1055 }
1059 }
1062 /* node may have become stale */
1065 }
1067 /*
1068 * Push down through internal nodes to locate the requested key.
1069 */
1072 /*
1073 * Scan the node to find the subtree index to push down into.
1074 * We go one-past, then back-up.
1075 *
1076 * We must proactively remove deleted elements which may
1077 * have been left over from a deadlocked btree_remove().
1078 *
1079 * The left and right boundaries are included in the loop
1080 * in order to detect edge cases.
1081 *
1082 * If the separator only differs by create_tid (r == 1)
1083 * and we are doing an as-of search, we may end up going
1084 * down a branch to the left of the one containing the
1085 * desired key. This requires numerous special cases.
1086 */
1092 }
1094 /*
1095 * Try to shortcut the search before dropping into the
1096 * linear loop. Locate the first node where r <= 1.
1097 */
1106 }
1113 }
1115 }
1119 }
1121 /*
1122 * These cases occur when the parent's idea of the boundary
1123 * is wider then the child's idea of the boundary, and
1124 * require special handling. If not inserting we can
1125 * terminate the search early for these cases but the
1126 * child's boundaries cannot be unconditionally modified.
1127 */
1129 /*
1130 * If i == 0 the search terminated to the LEFT of the
1131 * left_boundary but to the RIGHT of the parent's left
1132 * boundary.
1133 */
1134 u_int8_t save;
1138 /*
1139 * If we aren't inserting we can stop here.
1140 */
1145 }
1147 /*
1148 * Correct a left-hand boundary mismatch.
1149 *
1150 * We can only do this if we can upgrade the lock,
1151 * and synchronized as a background cursor (i.e.
1152 * inserting or pruning).
1153 *
1154 * WARNING: We can only do this if inserting, i.e.
1155 * we are running on the backend.
1156 */
1167 /*
1168 * If i == node->count + 1 the search terminated to
1169 * the RIGHT of the right boundary but to the LEFT
1170 * of the parent's right boundary. If we aren't
1171 * inserting we can stop here.
1172 *
1173 * Note that the last element in this case is
1174 * elms[i-2] prior to adjustments to 'i'.
1175 */
1181 }
1183 /*
1184 * Correct a right-hand boundary mismatch.
1185 * (actual push-down record is i-2 prior to
1186 * adjustments to i).
1187 *
1188 * We can only do this if we can upgrade the lock,
1189 * and synchronized as a background cursor (i.e.
1190 * inserting or pruning).
1191 *
1192 * WARNING: We can only do this if inserting, i.e.
1193 * we are running on the backend.
1194 */
1205 /*
1206 * The push-down index is now i - 1. If we had
1207 * terminated on the right boundary this will point
1208 * us at the last element.
1209 */
1211 }
1219 i,
1225 );
1226 }
1228 /*
1229 * We better have a valid subtree offset.
1230 */
1233 /*
1234 * Handle insertion and deletion requirements.
1235 *
1236 * If inserting split full nodes. The split code will
1237 * adjust cursor->node and cursor->index if the current
1238 * index winds up in the new node.
1239 *
1240 * If inserting and a left or right edge case was detected,
1241 * we cannot correct the left or right boundary and must
1242 * prepend and append an empty leaf node in order to make
1243 * the boundary correction.
1244 *
1245 * If we run out of space we set enospc and continue on
1246 * to a leaf to provide the spike code with a good point
1247 * of entry.
1248 */
1256 }
1257 /*
1258 * reload stale pointers
1259 */
1262 }
1263 }
1265 /*
1266 * Push down (push into new node, existing node becomes
1267 * the parent) and continue the search.
1268 */
1270 /* node may have become stale */
1274 }
1276 /*
1277 * We are at a leaf, do a linear search of the key array.
1278 *
1279 * On success the index is set to the matching element and 0
1280 * is returned.
1281 *
1282 * On failure the index is set to the insertion point and ENOENT
1283 * is returned.
1284 *
1285 * Boundaries are not stored in leaf nodes, so the index can wind
1286 * up to the left of element 0 (index == 0) or past the end of
1287 * the array (index == node->count). It is also possible that the
1288 * leaf might be empty.
1289 */
1297 }
1299 /*
1300 * Try to shortcut the search before dropping into the
1301 * linear loop. Locate the first node where r <= 1.
1302 */
1313 /*
1314 * We are at a record element. Stop if we've flipped past
1315 * key_beg, not counting the create_tid test. Allow the
1316 * r == 1 case (key_beg > element but differs only by its
1317 * create_tid) to fall through to the AS-OF check.
1318 */
1326 }
1328 /*
1329 * Check our as-of timestamp against the element.
1330 */
1336 }
1337 /* success */
1342 }
1343 /* success */
1344 }
1350 }
1352 }
1354 /*
1355 * The search of the leaf node failed. i is the insertion point.
1356 */
1357 failed:
1361 }
1363 /*
1364 * No exact match was found, i is now at the insertion point.
1365 *
1366 * If inserting split a full leaf before returning. This
1367 * may have the side effect of adjusting cursor->node and
1368 * cursor->index.
1369 */
1378 }
1379 /*
1380 * reload stale pointers
1381 */
1382 /* NOT USED
1383 i = cursor->index;
1384 node = &cursor->node->internal;
1385 */
1386 }
1388 /*
1389 * We reached a leaf but did not find the key we were looking for.
1390 * If this is an insert we will be properly positioned for an insert
1391 * (ENOENT) or spike (ENOSPC) operation.
1392 */
1394 done:
1396 }
1398 /*
1399 * Heuristical search for the first element whos comparison is <= 1. May
1400 * return an index whos compare result is > 1 but may only return an index
1401 * whos compare result is <= 1 if it is the first element with that result.
1402 */
1403 int
1405 {
1411 /*
1412 * Don't bother if the node does not have very many elements
1413 */
1424 }
1425 }
1427 }
1430 /************************************************************************
1431 * SPLITTING AND MERGING *
1432 ************************************************************************
1433 *
1434 * These routines do all the dirty work required to split and merge nodes.
1435 */
1437 /*
1438 * Split an internal node into two nodes and move the separator at the split
1439 * point to the parent.
1440 *
1441 * (cursor->node, cursor->index) indicates the element the caller intends
1442 * to push into. We will adjust node and index if that element winds
1443 * up in the split node.
1444 *
1445 * If we are at the root of the filesystem a new root must be created with
1446 * two elements, one pointing to the original root and one pointing to the
1447 * newly allocated split node.
1448 */
1449 static
1450 int
1452 {
1453 hammer_node_ondisk_t ondisk;
1454 hammer_node_t node;
1455 hammer_node_t parent;
1456 hammer_node_t new_node;
1457 hammer_btree_elm_t elm;
1458 hammer_btree_elm_t parent_elm;
1461 hammer_off_t hint;
1477 /*
1478 * Calculate the split point. If the insertion point is at the
1479 * end of the leaf we adjust the split point significantly to the
1480 * right to try to optimize node fill and flag it. If we hit
1481 * that same leaf again our heuristic failed and we don't try
1482 * to optimize node fill (it could lead to a degenerate case).
1483 */
1492 /*
1493 * We are splitting but elms[split] will be promoted to
1494 * the parent, leaving the right hand node with one less
1495 * element. If the insertion point will be on the
1496 * left-hand side adjust the split point to give the
1497 * right hand side one additional node.
1498 */
1502 }
1504 /*
1505 * If we are at the root of the filesystem, create a new root node
1506 * with 1 element and split normally. Avoid making major
1507 * modifications until we know the whole operation will work.
1508 */
1526 /* ondisk->elms[1].base.btype - not used */
1533 }
1535 /*
1536 * Calculate a hint for the allocation of the new B-Tree node.
1537 * The most likely expansion is coming from the insertion point
1538 * at cursor->index, so try to localize the allocation of our
1539 * new node to accomodate that sub-tree.
1540 *
1541 * Use the right-most sub-tree when expandinging on the right edge.
1542 * This is a very common case when copying a directory tree.
1543 */
1546 else
1549 /*
1550 * Split node into new_node at the split point.
1551 *
1552 * B O O O P N N B <-- P = node->elms[split] (index 4)
1553 * 0 1 2 3 4 5 6 <-- subtree indices
1554 *
1555 * x x P x x
1556 * s S S s
1557 * / \
1558 * B O O O B B N N B <--- inner boundary points are 'P'
1559 * 0 1 2 3 4 5 6
1560 */
1567 }
1569 }
1572 /*
1573 * Create the new node. P becomes the left-hand boundary in the
1574 * new node. Copy the right-hand boundary as well.
1575 *
1576 * elm is the new separator.
1577 */
1591 /*
1592 * Cleanup the original node. Elm (P) becomes the new boundary,
1593 * its subtree_offset was moved to the new node. If we had created
1594 * a new root its parent pointer may have changed.
1595 */
1599 /*
1600 * Insert the separator into the parent, fixup the parent's
1601 * reference to the original node, and reference the new node.
1602 * The separator is P.
1603 *
1604 * Remember that base.count does not include the right-hand boundary.
1605 */
1620 /*
1621 * The children of new_node need their parent pointer set to new_node.
1622 * The children have already been locked by
1623 * hammer_btree_lock_children().
1624 */
1630 }
1631 }
1634 /*
1635 * The filesystem's root B-Tree pointer may have to be updated.
1636 */
1638 hammer_volume_t volume;
1644 vol0_btree_root);
1651 }
1654 }
1657 /*
1658 * Ok, now adjust the cursor depending on which element the original
1659 * index was pointing at. If we are >= the split point the push node
1660 * is now in the new node.
1661 *
1662 * NOTE: If we are at the split point itself we cannot stay with the
1663 * original node because the push index will point at the right-hand
1664 * boundary, which is illegal.
1665 *
1666 * NOTE: The cursor's parent or parent_index must be adjusted for
1667 * the case where a new parent (new root) was created, and the case
1668 * where the cursor is now pointing at the split node.
1669 */
1680 }
1682 /*
1683 * Fixup left and right bounds
1684 */
1693 done:
1697 }
1699 /*
1700 * Same as the above, but splits a full leaf node.
1701 *
1702 * This function
1703 */
1704 static
1705 int
1707 {
1708 hammer_node_ondisk_t ondisk;
1709 hammer_node_t parent;
1710 hammer_node_t leaf;
1711 hammer_mount_t hmp;
1712 hammer_node_t new_leaf;
1713 hammer_btree_elm_t elm;
1714 hammer_btree_elm_t parent_elm;
1715 hammer_base_elm_t mid_boundary;
1716 hammer_off_t hint;
1732 /*
1733 * Calculate the split point. If the insertion point is at the
1734 * end of the leaf we adjust the split point significantly to the
1735 * right to try to optimize node fill and flag it. If we hit
1736 * that same leaf again our heuristic failed and we don't try
1737 * to optimize node fill (it could lead to a degenerate case).
1738 *
1739 * Spikes are made up of two leaf elements which cannot be
1740 * safely split.
1741 */
1751 }
1753 #if 0
1754 /*
1755 * If the insertion point is at the split point shift the
1756 * split point left so we don't have to worry about
1757 */
1760 #endif
1773 /*
1774 * If we are at the root of the tree, create a new root node with
1775 * 1 element and split normally. Avoid making major modifications
1776 * until we know the whole operation will work.
1777 */
1794 /* ondisk->elms[1].base.btype = not used */
1802 }
1804 /*
1805 * Calculate a hint for the allocation of the new B-Tree leaf node.
1806 * For now just try to localize it within the same bigblock as
1807 * the current leaf.
1808 *
1809 * If the insertion point is at the end of the leaf we recognize a
1810 * likely append sequence of some sort (data, meta-data, inodes,
1811 * whatever). Set the hint to zero to allocate out of linear space
1812 * instead of trying to completely fill previously hinted space.
1813 *
1814 * This also sets the stage for recursive splits to localize using
1815 * the new space.
1816 */
1820 else
1823 /*
1824 * Split leaf into new_leaf at the split point. Select a separator
1825 * value in-between the two leafs but with a bent towards the right
1826 * leaf since comparisons use an 'elm >= separator' inequality.
1827 *
1828 * L L L L L L L L
1829 *
1830 * x x P x x
1831 * s S S s
1832 * / \
1833 * L L L L L L L L
1834 */
1841 }
1843 }
1846 /*
1847 * Create the new node and copy the leaf elements from the split
1848 * point on to the new node.
1849 */
1863 /*
1864 * Cleanup the original node. Because this is a leaf node and
1865 * leaf nodes do not have a right-hand boundary, there
1866 * aren't any special edge cases to clean up. We just fixup the
1867 * count.
1868 */
1871 /*
1872 * Insert the separator into the parent, fixup the parent's
1873 * reference to the original node, and reference the new node.
1874 * The separator is P.
1875 *
1876 * Remember that base.count does not include the right-hand boundary.
1877 * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1878 */
1896 /*
1897 * The filesystem's root B-Tree pointer may have to be updated.
1898 */
1900 hammer_volume_t volume;
1906 vol0_btree_root);
1913 }
1916 }
1919 /*
1920 * Ok, now adjust the cursor depending on which element the original
1921 * index was pointing at. If we are >= the split point the push node
1922 * is now in the new node.
1923 *
1924 * NOTE: If we are at the split point itself we need to select the
1925 * old or new node based on where key_beg's insertion point will be.
1926 * If we pick the wrong side the inserted element will wind up in
1927 * the wrong leaf node and outside that node's bounds.
1928 */
1941 }
1943 /*
1944 * Fixup left and right bounds
1945 */
1950 /*
1951 * Assert that the bounds are correct.
1952 */
1960 done:
1963 }
1965 #if 0
1967 /*
1968 * Recursively correct the right-hand boundary's create_tid to (tid) as
1969 * long as the rest of the key matches. We have to recurse upward in
1970 * the tree as well as down the left side of each parent's right node.
1971 *
1972 * Return EDEADLK if we were only partially successful, forcing the caller
1973 * to try again. The original cursor is not modified. This routine can
1974 * also fail with EDEADLK if it is forced to throw away a portion of its
1975 * record history.
1976 *
1977 * The caller must pass a downgraded cursor to us (otherwise we can't dup it).
1978 */
1981 hammer_node_t node;
1983 };
1987 int
1989 {
1992 hammer_base_elm_t elm;
1993 hammer_node_t orig_node;
2001 /*
2002 * Save our position so we can restore it on return. This also
2003 * gives us a stable 'elm'.
2004 */
2011 /*
2012 * Now build a list of parents going up, allocating a rhb
2013 * structure for each one.
2014 */
2016 /*
2017 * Stop if we no longer have any right-bounds to fix up
2018 */
2023 }
2025 /*
2026 * Stop if the right-hand bound's create_tid does not
2027 * need to be corrected.
2028 */
2040 }
2042 /*
2043 * now safely adjust the right hand bound for each rhb. This may
2044 * also require taking the right side of the tree and iterating down
2045 * ITS left side.
2046 */
2059 /*
2060 * Right-boundary for parent at internal node
2061 * is one element to the right of the element whos
2062 * right boundary needs adjusting. We must then
2063 * traverse down the left side correcting any left
2064 * bounds (which may now be too far to the left).
2065 */
2073 }
2074 }
2076 /*
2077 * Cleanup
2078 */
2084 }
2089 }
2091 /*
2092 * Similar to rhb (in fact, rhb calls lhb), but corrects the left hand
2093 * bound going downward starting at the current cursor position.
2094 *
2095 * This function does not restore the cursor after use.
2096 */
2097 int
2099 {
2101 hammer_base_elm_t elm;
2102 hammer_base_elm_t cmp;
2112 /*
2113 * Record the node and traverse down the left-hand side for all
2114 * matching records needing a boundary correction.
2115 */
2126 /*
2127 * Nothing to traverse down if we are at the right
2128 * boundary of an internal node.
2129 */
2137 }
2147 }
2151 }
2153 /*
2154 * Now we can safely adjust the left-hand boundary from the bottom-up.
2155 * The last element we remove from the list is the caller's right hand
2156 * boundary, which must also be adjusted.
2157 */
2176 }
2177 }
2179 /*
2180 * Cleanup
2181 */
2187 }
2189 }
2191 #endif
2193 /*
2194 * Attempt to remove the locked, empty or want-to-be-empty B-Tree node at
2195 * (cursor->node). Returns 0 on success, EDEADLK if we could not complete
2196 * the operation due to a deadlock, or some other error.
2197 *
2198 * This routine is initially called with an empty leaf and may be
2199 * recursively called with single-element internal nodes.
2200 *
2201 * It should also be noted that when removing empty leaves we must be sure
2202 * to test and update mirror_tid because another thread may have deadlocked
2203 * against us (or someone) trying to propagate it up and cannot retry once
2204 * the node has been deleted.
2205 *
2206 * On return the cursor may end up pointing to an internal node, suitable
2207 * for further iteration but not for an immediate insertion or deletion.
2208 */
2209 static int
2211 {
2212 hammer_node_ondisk_t ondisk;
2213 hammer_btree_elm_t elm;
2214 hammer_node_t node;
2215 hammer_node_t parent;
2221 /*
2222 * When deleting the root of the filesystem convert it to
2223 * an empty leaf node. Internal nodes cannot be empty.
2224 */
2235 }
2239 /*
2240 * Attempt to remove the parent's reference to the child. If the
2241 * parent would become empty we have to recurse. If we fail we
2242 * leave the parent pointing to an empty leaf node.
2243 *
2244 * We have to recurse successfully before we can delete the internal
2245 * node as it is illegal to have empty internal nodes. Even though
2246 * the operation may be aborted we must still fixup any unlocked
2247 * cursors as if we had deleted the element prior to recursing
2248 * (by calling hammer_cursor_deleted_element()) so those cursors
2249 * are properly forced up the chain by the recursion.
2250 */
2252 /*
2253 * This special cursor_up_locked() call leaves the original
2254 * node exclusively locked and referenced, leaves the
2255 * original parent locked (as the new node), and locks the
2256 * new parent. It can return EDEADLK.
2257 *
2258 * We cannot call hammer_cursor_removed_node() until we are
2259 * actually able to remove the node. If we did then tracked
2260 * cursors in the middle of iterations could be repointed
2261 * to a parent node. If this occurs they could end up
2262 * scanning newly inserted records into the node (that could
2263 * not be deleted) when they push down again.
2264 *
2265 * Due to the way the recursion works the final parent is left
2266 * in cursor->parent after the recursion returns. Each
2267 * layer on the way back up is thus able to call
2268 * hammer_cursor_removed_node() and 'jump' the node up to
2269 * the (same) final parent.
2270 *
2271 * NOTE! The local variable 'parent' is invalid after we
2272 * call hammer_cursor_up_locked().
2273 */
2293 /*
2294 * Defer parent removal because we could not
2295 * get the lock, just let the leaf remain
2296 * empty.
2297 */
2298 /**/
2299 }
2303 /*
2304 * Defer parent removal because we could not
2305 * get the lock, just let the leaf remain
2306 * empty.
2307 */
2308 /**/
2309 }
2321 /*
2322 * We must retain the highest mirror_tid. The deleted
2323 * range is now encompassed by the element to the left.
2324 * If we are already at the left edge the new left edge
2325 * inherits mirror_tid.
2326 *
2327 * Note that bounds of the parent to our parent may create
2328 * a gap to the left of our left-most node or to the right
2329 * of our right-most node. The gap is silently included
2330 * in the mirror_tid's area of effect from the point of view
2331 * of the scan.
2332 */
2338 }
2344 }
2345 }
2347 /*
2348 * Delete the subtree reference in the parent. Include
2349 * boundary element at end.
2350 */
2360 /*
2361 * cursor->node is invalid, cursor up to make the cursor
2362 * valid again.
2363 */
2365 }
2367 }
2369 /*
2370 * Propagate cursor->trans->tid up the B-Tree starting at the current
2371 * cursor position using pseudofs info gleaned from the passed inode.
2372 *
2373 * The passed inode has no relationship to the cursor position other
2374 * then being in the same pseudofs as the insertion or deletion we
2375 * are propagating the mirror_tid for.
2376 *
2377 * WARNING! Because we push and pop the passed cursor, it may be
2378 * modified by other B-Tree operations while it is unlocked
2379 * and things like the node & leaf pointers, and indexes might
2380 * change.
2381 */
2382 void
2384 hammer_pseudofs_inmem_t pfsm,
2385 hammer_btree_leaf_elm_t leaf)
2386 {
2387 hammer_cursor_t ncursor;
2388 hammer_tid_t mirror_tid;
2391 /*
2392 * We do not propagate a mirror_tid if the filesystem was mounted
2393 * in no-mirror mode.
2394 */
2398 /*
2399 * This is a bit of a hack because we cannot deadlock or return
2400 * EDEADLK here. The related operation has already completed and
2401 * we must propagate the mirror_tid now regardless.
2402 *
2403 * Generate a new cursor which inherits the original's locks and
2404 * unlock the original. Use the new cursor to propagate the
2405 * mirror_tid. Then clean up the new cursor and reacquire locks
2406 * on the original.
2407 *
2408 * hammer_dup_cursor() cannot dup locks. The dup inherits the
2409 * original's locks and the original is tracked and must be
2410 * re-locked.
2411 */
2418 /* WARNING: cursor's leaf pointer may change after pop */
2419 }
2422 /*
2423 * Propagate a mirror TID update upwards through the B-Tree to the root.
2424 *
2425 * A locked internal node must be passed in. The node will remain locked
2426 * on return.
2427 *
2428 * This function syncs mirror_tid at the specified internal node's element,
2429 * adjusts the node's aggregation mirror_tid, and then recurses upwards.
2430 */
2431 static int
2433 {
2434 hammer_btree_internal_elm_t elm;
2435 hammer_node_t node;
2445 }
2449 /*
2450 * If the cursor deadlocked it could end up at a leaf
2451 * after we lost the lock.
2452 */
2457 /*
2458 * Adjust the node's element
2459 */
2473 }
2476 /*
2477 * Adjust the node's mirror_tid aggregator
2478 */
2489 }
2490 }
2494 }
2496 hammer_node_t
2499 {
2500 hammer_node_t parent;
2501 hammer_btree_elm_t elm;
2504 /*
2505 * Get the node
2506 */
2511 }
2514 /*
2515 * Lock the node
2516 */
2522 }
2525 }
2527 /*
2528 * Figure out which element in the parent is pointing to the
2529 * child.
2530 */
2536 }
2542 }
2546 }
2550 }
2552 /*
2553 * The element (elm) has been moved to a new internal node (node).
2554 *
2555 * If the element represents a pointer to an internal node that node's
2556 * parent must be adjusted to the element's new location.
2557 *
2558 * XXX deadlock potential here with our exclusive locks
2559 */
2560 int
2562 hammer_btree_elm_t elm)
2563 {
2564 hammer_node_t child;
2579 }
2583 }
2585 }
2587 /*
2588 * Initialize the root of a recursive B-Tree node lock list structure.
2589 */
2590 void
2592 {
2600 }
2602 /*
2603 * Exclusively lock all the children of node. This is used by the split
2604 * code to prevent anyone from accessing the children of a cursor node
2605 * while we fix-up its parent offset.
2606 *
2607 * If we don't lock the children we can really mess up cursors which block
2608 * trying to cursor-up into our node.
2609 *
2610 * On failure EDEADLK (or some other error) is returned. If a deadlock
2611 * error is returned the cursor is adjusted to block on termination.
2612 *
2613 * The caller is responsible for managing parent->node, the root's node
2614 * is usually aliased from a cursor.
2615 */
2616 int
2618 hammer_node_lock_t parent)
2619 {
2620 hammer_node_t node;
2621 hammer_node_lock_t item;
2622 hammer_node_ondisk_t ondisk;
2623 hammer_btree_elm_t elm;
2624 hammer_node_t child;
2634 /*
2635 * We really do not want to block on I/O with exclusive locks held,
2636 * pre-get the children before trying to lock the mess. This is
2637 * only done one-level deep for now.
2638 */
2645 }
2651 }
2653 /*
2654 * Do it for real
2655 */
2671 }
2677 }
2690 /*
2691 * Recurse (used by the rebalancing code)
2692 */
2695 cursor,
2697 item);
2698 }
2699 }
2700 }
2701 }
2705 }
2707 /*
2708 * Create an in-memory copy of all B-Tree nodes listed, recursively,
2709 * including the parent.
2710 */
2711 void
2713 {
2715 hammer_node_lock_t item;
2719 M_WAITOK);
2721 }
2724 }
2725 }
2727 /*
2728 * Recursively sync modified copies to the media.
2729 */
2730 int
2732 {
2733 hammer_node_lock_t item;
2744 }
2745 }
2748 }
2750 }
2752 /*
2753 * Release previously obtained node locks. The caller is responsible for
2754 * cleaning up parent->node itself (its usually just aliased from a cursor),
2755 * but this function will take care of the copies.
2756 */
2757 void
2759 {
2760 hammer_node_lock_t item;
2765 }
2772 }
2773 }
2775 /************************************************************************
2776 * MISCELLANIOUS SUPPORT *
2777 ************************************************************************/
2779 /*
2780 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
2781 *
2782 * Note that for this particular function a return value of -1, 0, or +1
2783 * can denote a match if create_tid is otherwise discounted. A create_tid
2784 * of zero is considered to be 'infinity' in comparisons.
2785 *
2786 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
2787 */
2788 int
2790 {
2811 /*
2812 * A create_tid of zero indicates a record which is undeletable
2813 * and must be considered to have a value of positive infinity.
2814 */
2819 }
2827 }
2829 /*
2830 * Test a timestamp against an element to determine whether the
2831 * element is visible. A timestamp of 0 means 'infinity'.
2832 */
2833 int
2835 {
2840 }
2846 }
2848 /*
2849 * Create a separator half way inbetween key1 and key2. For fields just
2850 * one unit apart, the separator will match key2. key1 is on the left-hand
2851 * side and key2 is on the right-hand side.
2852 *
2853 * key2 must be >= the separator. It is ok for the separator to match key2.
2854 *
2855 * NOTE: Even if key1 does not match key2, the separator may wind up matching
2856 * key2.
2857 *
2858 * NOTE: It might be beneficial to just scrap this whole mess and just
2859 * set the separator to key2.
2860 */
2861 #define MAKE_SEPARATOR(key1, key2, dest, field) \
2862 dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
2864 static void
2866 hammer_base_elm_t dest)
2867 {
2882 /*
2883 * Don't bother creating a separator for
2884 * create_tid, which also conveniently avoids
2885 * having to handle the create_tid == 0
2886 * (infinity) case. Just leave create_tid
2887 * set to key2.
2888 *
2889 * Worst case, dest matches key2 exactly,
2890 * which is acceptable.
2891 */
2892 }
2893 }
2894 }
2895 }
2897 #undef MAKE_SEPARATOR
2899 /*
2900 * Return whether a generic internal or leaf node is full
2901 */
2902 static int
2904 {
2916 }
2918 }
2920 #if 0
2921 static int
2923 {
2929 }
2930 #endif
2932 void
2934 {
2935 hammer_btree_elm_t elm;
2942 /*
2943 * Dump both boundary elements if an internal node
2944 */
2949 }
2954 }
2955 }
2956 }
2958 void
2960 {
2984 }
2985 }