Loading...
Searching...
No Matches
verify_nbtree.c File Reference
#include "postgres.h"#include "access/heaptoast.h"#include "access/htup_details.h"#include "access/nbtree.h"#include "access/table.h"#include "access/tableam.h"#include "access/transam.h"#include "access/xact.h"#include "verify_common.h"#include "catalog/index.h"#include "catalog/pg_am.h"#include "catalog/pg_opfamily_d.h"#include "common/pg_prng.h"#include "lib/bloomfilter.h"#include "miscadmin.h"#include "storage/smgr.h"#include "utils/guc.h"#include "utils/memutils.h"#include "utils/snapmgr.h"
Include dependency graph for verify_nbtree.c:
Go to the source code of this file.
Data Structures | |
| struct | BtreeCheckState |
| struct | BtreeLevel |
| struct | BtreeLastVisibleEntry |
| struct | BTCallbackState |
Macros | |
| #define | InvalidBtreeLevel ((uint32) InvalidBlockNumber) |
| #define | BTreeTupleGetNKeyAtts(itup, rel) Min(IndexRelationGetNumberOfKeyAttributes(rel), BTreeTupleGetNAtts(itup, rel)) |
Typedefs | |
| typedef struct BtreeCheckState | BtreeCheckState |
| typedef struct BtreeLevel | BtreeLevel |
| typedef struct BtreeLastVisibleEntry | BtreeLastVisibleEntry |
| typedef struct BTCallbackState | BTCallbackState |
Macro Definition Documentation
◆ BTreeTupleGetNKeyAtts
| #define BTreeTupleGetNKeyAtts | ( | itup, | |
| rel | |||
| ) | Min(IndexRelationGetNumberOfKeyAttributes(rel), BTreeTupleGetNAtts(itup, rel)) |
Definition at line 56 of file verify_nbtree.c.
70{
71 /*
72 * Unchanging state, established at start of verification:
73 */
74
75 /* B-Tree Index Relation and associated heap relation */
76 Relation rel;
77 Relation heaprel;
78 /* rel is heapkeyspace index? */
79 bool heapkeyspace;
80 /* ShareLock held on heap/index, rather than AccessShareLock? */
81 bool readonly;
82 /* Also verifying heap has no unindexed tuples? */
83 bool heapallindexed;
84 /* Also making sure non-pivot tuples can be found by new search? */
85 bool rootdescend;
86 /* Also check uniqueness constraint if index is unique */
87 bool checkunique;
88 /* Per-page context */
89 MemoryContext targetcontext;
90 /* Buffer access strategy */
91 BufferAccessStrategy checkstrategy;
92
93 /*
94 * Info for uniqueness checking. Fill this field and the one below once
95 * per index check.
96 */
97 IndexInfo *indexinfo;
98 /* Table scan snapshot for heapallindexed and checkunique */
99 Snapshot snapshot;
100
101 /*
102 * Mutable state, for verification of particular page:
103 */
104
105 /* Current target page */
106 Page target;
107 /* Target block number */
108 BlockNumber targetblock;
109 /* Target page's LSN */
110 XLogRecPtr targetlsn;
111
112 /*
113 * Low key: high key of left sibling of target page. Used only for child
114 * verification. So, 'lowkey' is kept only when 'readonly' is set.
115 */
116 IndexTuple lowkey;
117
118 /*
119 * The rightlink and incomplete split flag of block one level down to the
120 * target page, which was visited last time via downlink from target page.
121 * We use it to check for missing downlinks.
122 */
123 BlockNumber prevrightlink;
124 bool previncompletesplit;
125
126 /*
127 * Mutable state, for optional heapallindexed verification:
128 */
129
130 /* Bloom filter fingerprints B-Tree index */
131 bloom_filter *filter;
132 /* Debug counter */
133 int64 heaptuplespresent;
134} BtreeCheckState;
135
136/*
137 * Starting point for verifying an entire B-Tree index level
138 */
140{
141 /* Level number (0 is leaf page level). */
143
144 /* Left most block on level. Scan of level begins here. */
146
147 /* Is this level reported as "true" root level by meta page? */
149} BtreeLevel;
150
151/*
152 * Information about the last visible entry with current B-tree key. Used
153 * for validation of the unique constraint.
154 */
156{
160 * non-deduplicated tuples) */
162} BtreeLastVisibleEntry;
163
164/*
165 * arguments for the bt_index_check_callback callback
166 */
168{
173} BTCallbackState;
174
177
181 bool heapkeyspace, bool readonly, bool heapallindexed,
182 bool rootdescend, bool checkunique);
184 BtreeLevel level);
204 OffsetNumber downlinkoffnum);
215 IndexTuple itup);
219 OffsetNumber offset);
223 BTScanInsert key,
228 BTScanInsert key,
234 IndexTuple itup);
240
241/*
242 * bt_index_check(index regclass, heapallindexed boolean, checkunique boolean)
243 *
244 * Verify integrity of B-Tree index.
245 *
246 * Acquires AccessShareLock on heap & index relations. Does not consider
247 * invariants that exist between parent/child pages. Optionally verifies
248 * that heap does not contain any unindexed or incorrectly indexed tuples.
249 */
250Datum
252{
255
260
265
268 AccessShareLock, &args);
269
270 PG_RETURN_VOID();
271}
272
273/*
274 * bt_index_parent_check(index regclass, heapallindexed boolean, rootdescend boolean, checkunique boolean)
275 *
276 * Verify integrity of B-Tree index.
277 *
278 * Acquires ShareLock on heap & index relations. Verifies that downlinks in
279 * parent pages are valid lower bounds on child pages. Optionally verifies
280 * that heap does not contain any unindexed or incorrectly indexed tuples.
281 */
282Datum
284{
287
292
299
302 ShareLock, &args);
303
304 PG_RETURN_VOID();
305}
306
307/*
308 * Helper for bt_index_[parent_]check, coordinating the bulk of the work.
309 */
310static void
312{
314 bool heapkeyspace,
315 allequalimage;
316
322
323 /* Extract metadata from metapage, and sanitize it in passing */
325 if (allequalimage && !heapkeyspace)
331 {
333
336 {
342 has_interval_ops
344 : 0));
345 }
346 }
347
348 /* Check index, possibly against table it is an index on */
351}
352
353/*
354 * Main entry point for B-Tree SQL-callable functions. Walks the B-Tree in
355 * logical order, verifying invariants as it goes. Optionally, verification
356 * checks if the heap relation contains any tuples that are not represented in
357 * the index but should be.
358 *
359 * It is the caller's responsibility to acquire appropriate heavyweight lock on
360 * the index relation, and advise us if extra checks are safe when a ShareLock
361 * is held. (A lock of the same type must also have been acquired on the heap
362 * relation.)
363 *
364 * A ShareLock is generally assumed to prevent any kind of physical
365 * modification to the index structure, including modifications that VACUUM may
366 * make. This does not include setting of the LP_DEAD bit by concurrent index
367 * scans, although that is just metadata that is not able to directly affect
368 * any check performed here. Any concurrent process that might act on the
369 * LP_DEAD bit being set (recycle space) requires a heavyweight lock that
370 * cannot be held while we hold a ShareLock. (Besides, even if that could
371 * happen, the ad-hoc recycling when a page might otherwise split is performed
372 * per-page, and requires an exclusive buffer lock, which wouldn't cause us
373 * trouble. _bt_delitems_vacuum() may only delete leaf items, and so the extra
374 * parent/child check cannot be affected.)
375 */
376static void
378 bool readonly, bool heapallindexed, bool rootdescend,
379 bool checkunique)
380{
385 BtreeLevel current;
386
387 if (!readonly)
389 RelationGetRelationName(rel));
390 else
391 elog(DEBUG1, "verifying consistency of tree structure for index \"%s\" with cross-level checks",
392 RelationGetRelationName(rel));
393
394 /*
395 * This assertion matches the one in index_getnext_tid(). See page
396 * recycling/"visible to everyone" notes in nbtree README.
397 */
399
400 /*
401 * Initialize state for entire verification operation
402 */
404 state->rel = rel;
405 state->heaprel = heaprel;
406 state->heapkeyspace = heapkeyspace;
407 state->readonly = readonly;
408 state->heapallindexed = heapallindexed;
409 state->rootdescend = rootdescend;
410 state->checkunique = checkunique;
412
414 {
417 uint64 seed;
418
419 /*
420 * Size Bloom filter based on estimated number of tuples in index,
421 * while conservatively assuming that each block must contain at least
422 * MaxTIDsPerBTreePage / 3 "plain" tuples -- see
423 * bt_posting_plain_tuple() for definition, and details of how posting
424 * list tuples are handled.
425 */
429 /* Generate a random seed to avoid repetition */
431 /* Create Bloom filter to fingerprint index */
433 state->heaptuplespresent = 0;
434
435 /*
436 * Register our own snapshot for heapallindexed, rather than asking
437 * table_index_build_scan() to do this for us later. This needs to
438 * happen before index fingerprinting begins, so we can later be
439 * certain that index fingerprinting should have reached all tuples
440 * returned by table_index_build_scan().
441 */
443
444 /*
445 * GetTransactionSnapshot() always acquires a new MVCC snapshot in
446 * READ COMMITTED mode. A new snapshot is guaranteed to have all the
447 * entries it requires in the index.
448 *
449 * We must defend against the possibility that an old xact snapshot
450 * was returned at higher isolation levels when that snapshot is not
451 * safe for index scans of the target index. This is possible when
452 * the snapshot sees tuples that are before the index's indcheckxmin
453 * horizon. Throwing an error here should be very rare. It doesn't
454 * seem worth using a secondary snapshot to avoid this.
455 */
458 state->snapshot->xmin))
462 RelationGetRelationName(rel)));
463 }
464
465 /*
466 * We need a snapshot to check the uniqueness of the index. For better
467 * performance, take it once per index check. If one was already taken
468 * above, use that.
469 */
471 {
473
476 }
477
482 errmsg("cannot verify that tuples from index \"%s\" can each be found by an independent index search",
483 RelationGetRelationName(rel)),
485
486 /* Create context for page */
488 "amcheck context",
489 ALLOCSET_DEFAULT_SIZES);
491
492 /* Get true root block from meta-page */
495
496 /*
497 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
498 * the fast root and true root differ.
499 *
500 * Start from the true root, not the fast root, unlike conventional index
501 * scans. This approach is more thorough, and removes the risk of
502 * following a stale fast root from the meta page.
503 */
508 RelationGetRelationName(rel)),
512
513 /*
514 * Starting at the root, verify every level. Move left to right, top to
515 * bottom. Note that there may be no pages other than the meta page (meta
516 * page can indicate that root is P_NONE when the index is totally empty).
517 */
523 {
524 /*
525 * Verify this level, and get left most page for next level down, if
526 * not at leaf level
527 */
529
535
537 }
538
539 /*
540 * * Check whether heap contains unindexed/malformed tuples *
541 */
543 {
545 TableScanDesc scan;
546
547 /*
548 * Create our own scan for table_index_build_scan(), rather than
549 * getting it to do so for us. This is required so that we can
550 * actually use the MVCC snapshot registered earlier.
551 *
552 * Note that table_index_build_scan() calls heap_endscan() for us.
553 */
556 0, /* number of keys */
558 true, /* buffer access strategy OK */
559 true); /* syncscan OK? */
560
561 /*
562 * Scan will behave as the first scan of a CREATE INDEX CONCURRENTLY
563 * behaves.
564 *
565 * It's okay that we don't actually use the same lock strength for the
566 * heap relation as any other ii_Concurrent caller would. We have no
567 * reason to care about a concurrent VACUUM operation, since there
568 * isn't going to be a second scan of the heap that needs to be sure
569 * that there was no concurrent recycling of TIDs.
570 */
572
573 /*
574 * Don't wait for uncommitted tuple xact commit/abort when index is a
575 * unique index on a catalog (or an index used by an exclusion
576 * constraint). This could otherwise happen in the readonly case.
577 */
582
586
589
591 (errmsg_internal("finished verifying presence of " INT64_FORMAT " tuples from table \"%s\" with bitset %.2f%% set",
594
596 }
597
598 /* Be tidy: */
602}
603
604/*
605 * Given a left-most block at some level, move right, verifying each page
606 * individually (with more verification across pages for "readonly"
607 * callers). Caller should pass the true root page as the leftmost initially,
608 * working their way down by passing what is returned for the last call here
609 * until level 0 (leaf page level) was reached.
610 *
611 * Returns state for next call, if any. This includes left-most block number
612 * one level lower that should be passed on next level/call, which is set to
613 * P_NONE on last call here (when leaf level is verified). Level numbers
614 * follow the nbtree convention: higher levels have higher numbers, because new
615 * levels are added only due to a root page split. Note that prior to the
616 * first root page split, the root is also a leaf page, so there is always a
617 * level 0 (leaf level), and it's always the last level processed.
618 *
619 * Note on memory management: State's per-page context is reset here, between
620 * each call to bt_target_page_check().
621 */
624{
625 /* State to establish early, concerning entire level */
626 BTPageOpaque opaque;
627 MemoryContext oldcontext;
629
630 /* Variables for iterating across level using right links */
633
634 /* Initialize return state */
638
639 /* Use page-level context for duration of this call */
641
643 level.istruerootlevel ?
644 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
645
648
649 do
650 {
651 /* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
652 CHECK_FOR_INTERRUPTS();
653
654 /* Initialize state for this iteration */
655 state->targetblock = current;
658
660
662 {
663 /*
664 * Since there cannot be a concurrent VACUUM operation in readonly
665 * mode, and since a page has no links within other pages
666 * (siblings and parent) once it is marked fully deleted, it
667 * should be impossible to land on a fully deleted page in
668 * readonly mode. See bt_child_check() for further details.
669 *
670 * The bt_child_check() P_ISDELETED() check is repeated here so
671 * that pages that are only reachable through sibling links get
672 * checked.
673 */
681
687 else
693 }
695 {
696 /*
697 * A concurrent page split could make the caller supplied leftmost
698 * block no longer contain the leftmost page, or no longer be the
699 * true root, but where that isn't possible due to heavyweight
700 * locking, check that the first valid page meets caller's
701 * expectations.
702 */
704 {
710
716 }
717
718 /*
719 * Before beginning any non-trivial examination of level, prepare
720 * state for next bt_check_level_from_leftmost() invocation for
721 * the next level for the next level down (if any).
722 *
723 * There should be at least one non-ignorable page per level,
724 * unless this is the leaf level, which is assumed by caller to be
725 * final level.
726 */
728 {
729 IndexTuple itup;
730 ItemId itemid;
731
732 /* Internal page -- downlink gets leftmost on next level */
734 state->target,
735 P_FIRSTDATAKEY(opaque));
739 }
740 else
741 {
742 /*
743 * Leaf page -- final level caller must process.
744 *
745 * Note that this could also be the root page, if there has
746 * been no root page split yet.
747 */
750 }
751
752 /*
753 * Finished setting up state for this call/level. Control will
754 * never end up back here in any future loop iteration for this
755 * level.
756 */
757 }
758
759 /*
760 * Sibling links should be in mutual agreement. There arises
761 * leftcurrent == P_NONE && btpo_prev != P_NONE when the left sibling
762 * of the parent's low-key downlink is half-dead. (A half-dead page
763 * has no downlink from its parent.) Under heavyweight locking, the
764 * last bt_leftmost_ignoring_half_dead() validated this btpo_prev.
765 * Without heavyweight locking, validation of the P_NONE case remains
766 * unimplemented.
767 */
770
771 /* Check level */
775 errmsg("leftmost down link for level points to block in index \"%s\" whose level is not one level down",
779
780 /* Verify invariants for page */
782
783nextpage:
784
785 /* Try to detect circular links */
791
792 leftcurrent = current;
793 current = opaque->btpo_next;
794
796 {
800 }
801
802 /*
803 * Copy current target high key as the low key of right sibling.
804 * Allocate memory in upper level context, so it would be cleared
805 * after reset of target context.
806 *
807 * We only need the low key in corner cases of checking child high
808 * keys. We use high key only when incomplete split on the child level
809 * falls to the boundary of pages on the target level. See
810 * bt_child_highkey_check() for details. So, typically we won't end
811 * up doing anything with low key, but it's simpler for general case
812 * high key verification to always have it available.
813 *
814 * The correctness of managing low key in the case of concurrent
815 * splits wasn't investigated yet. Thankfully we only need low key
816 * for readonly verification and concurrent splits won't happen.
817 */
819 {
820 IndexTuple itup;
821 ItemId itemid;
822
826
829 }
830
831 /* Free page and associated memory for this iteration */
833 }
835
837 {
841 }
842
843 /* Don't change context for caller */
844 MemoryContextSwitchTo(oldcontext);
845
847}
848
849/* Check visibility of the table entry referenced by nbtree index */
850static bool
852{
854
856
858 tid, state->snapshot, slot);
860 ExecDropSingleTupleTableSlot(slot);
861
863}
864
865/*
866 * Prepare an error message for unique constrain violation in
867 * a btree index and report ERROR.
868 */
869static void
874{
876 *nhtid,
877 *itid,
881
889
892
895
898
906}
907
908/* Check if current nbtree leaf entry complies with UNIQUE constraint */
909static void
913{
914 ItemPointer tid;
916
918
919 /*
920 * Current tuple has posting list. Report duplicate if TID of any posting
921 * list entry is visible and lVis->tid is valid.
922 */
924 {
926 {
929 {
932 {
934 lVis,
935 tid, targetblock,
936 offset, i);
937 }
938
939 /*
940 * Prevent double reporting unique constraint violation
941 * between the posting list entries of the first tuple on the
942 * page after cross-page check.
943 */
945 return;
946
947 lVis->blkno = targetblock;
948 lVis->offset = offset;
950 lVis->tid = tid;
951 }
952 }
953 }
954
955 /*
956 * Current tuple has no posting list. If TID is visible save info about it
957 * for the next comparisons in the loop in bt_target_page_check(). Report
958 * duplicate if lVis->tid is already valid.
959 */
960 else
961 {
962 tid = BTreeTupleGetHeapTID(itup);
964 {
967 {
969 lVis,
970 tid, targetblock,
971 offset, -1);
972 }
973
974 lVis->blkno = targetblock;
975 lVis->offset = offset;
976 lVis->tid = tid;
977 lVis->postingIndex = -1;
978 }
979 }
980
983 lVis->blkno != targetblock)
984 {
986
992 targetblock, offset,
994 errdetail("It doesn't have visible heap tids and key is equal to the tid=(%u,%u)%s (points to heap tid=(%u,%u)).",
999 }
1000}
1001
1002/*
1003 * Like P_LEFTMOST(start_opaque), but accept an arbitrarily-long chain of
1004 * half-dead, sibling-linked pages to the left. If a half-dead page appears
1005 * under state->readonly, the database exited recovery between the first-stage
1006 * and second-stage WAL records of a deletion.
1007 */
1008static bool
1012{
1016
1017 /*
1018 * To handle the !readonly case, we'd need to accept BTP_DELETED pages and
1019 * potentially observe nbtree/README "Page deletion and backwards scans".
1020 */
1022
1024 {
1027
1028 CHECK_FOR_INTERRUPTS();
1029
1030 /*
1031 * Try to detect btpo_prev circular links. _bt_unlink_halfdead_page()
1032 * writes that side-links will continue to point to the siblings.
1033 * Check btpo_next for that property.
1034 */
1040 {
1042
1043 /* pagelsn should point to an XLOG_BTREE_MARK_PAGE_HALFDEAD */
1051
1054 }
1055
1056 pfree(page);
1057 }
1058
1060}
1061
1062/*
1063 * Raise an error when target page's left link does not point back to the
1064 * previous target page, called leftcurrent here. The leftcurrent page's
1065 * right link was followed to get to the current target page, and we expect
1066 * mutual agreement among leftcurrent and the current target page. Make sure
1067 * that this condition has definitely been violated in the !readonly case,
1068 * where concurrent page splits are something that we need to deal with.
1069 *
1070 * Cross-page inconsistencies involving pages that don't agree about being
1071 * siblings are known to be a particularly good indicator of corruption
1072 * involving partial writes/lost updates. The bt_right_page_check_scankey
1073 * check also provides a way of detecting cross-page inconsistencies for
1074 * !readonly callers, but it can only detect sibling pages that have an
1075 * out-of-order keyspace, which can't catch many of the problems that we
1076 * expect to catch here.
1077 *
1078 * The classic example of the kind of inconsistency that we can only catch
1079 * with this check (when in !readonly mode) involves three sibling pages that
1080 * were affected by a faulty page split at some point in the past. The
1081 * effects of the split are reflected in the original page and its new right
1082 * sibling page, with a lack of any accompanying changes for the _original_
1083 * right sibling page. The original right sibling page's left link fails to
1084 * point to the new right sibling page (its left link still points to the
1085 * original page), even though the first phase of a page split is supposed to
1086 * work as a single atomic action. This subtle inconsistency will probably
1087 * only break backwards scans in practice.
1088 *
1089 * Note that this is the only place where amcheck will "couple" buffer locks
1090 * (and only for !readonly callers). In general we prefer to avoid more
1091 * thorough cross-page checks in !readonly mode, but it seems worth the
1092 * complexity here. Also, the performance overhead of performing lock
1093 * coupling here is negligible in practice. Control only reaches here with a
1094 * non-corrupt index when there is a concurrent page split at the instant
1095 * caller crossed over to target page from leftcurrent page.
1096 */
1097static void
1101{
1102 /* passing metapage to BTPageGetOpaque() would give irrelevant findings */
1104
1106 {
1109 Page page;
1110 BTPageOpaque opaque;
1112
1113 /* Couple locks in the usual order for nbtree: Left to right */
1119 opaque = BTPageGetOpaque(page);
1121 {
1122 /*
1123 * Cannot reason about concurrently deleted page -- the left link
1124 * in the page to the right is expected to point to some other
1125 * page to the left (not leftcurrent page).
1126 *
1127 * Note that we deliberately don't give up with a half-dead page.
1128 */
1130 return;
1131 }
1132
1134 /* Avoid self-deadlock when newtargetblock == leftcurrent */
1136 {
1139 state->checkstrategy);
1143 opaque = BTPageGetOpaque(page);
1144 /* btpo_prev_from_target may have changed; update it */
1146 }
1147 else
1148 {
1149 /*
1150 * leftcurrent right sibling points back to leftcurrent block.
1151 * Index is corrupt. Easiest way to handle this is to pretend
1152 * that we actually read from a distinct page that has an invalid
1153 * block number in its btpo_prev.
1154 */
1157 }
1158
1159 /*
1160 * No need to check P_ISDELETED here, since new target block cannot be
1161 * marked deleted as long as we hold a lock on lbuf
1162 */
1166
1168 {
1169 /* Report split in left sibling, not target (or new target) */
1176 state->targetblock)));
1177 return;
1178 }
1179
1180 /*
1181 * Index is corrupt. Make sure that we report correct target page.
1182 *
1183 * This could have changed in cases where there was a concurrent page
1184 * split, as well as index corruption (at least in theory). Note that
1185 * btpo_prev_from_target was already updated above.
1186 */
1188 }
1189
1196 btpo_prev_from_target)));
1197}
1198
1199/*
1200 * Function performs the following checks on target page, or pages ancillary to
1201 * target page:
1202 *
1203 * - That every "real" data item is less than or equal to the high key, which
1204 * is an upper bound on the items on the page. Data items should be
1205 * strictly less than the high key when the page is an internal page.
1206 *
1207 * - That within the page, every data item is strictly less than the item
1208 * immediately to its right, if any (i.e., that the items are in order
1209 * within the page, so that the binary searches performed by index scans are
1210 * sane).
1211 *
1212 * - That the last data item stored on the page is strictly less than the
1213 * first data item on the page to the right (when such a first item is
1214 * available).
1215 *
1216 * - Various checks on the structure of tuples themselves. For example, check
1217 * that non-pivot tuples have no truncated attributes.
1218 *
1219 * - For index with unique constraint make sure that only one of table entries
1220 * for equal keys is visible.
1221 *
1222 * Furthermore, when state passed shows ShareLock held, function also checks:
1223 *
1224 * - That all child pages respect strict lower bound from parent's pivot
1225 * tuple.
1226 *
1227 * - That downlink to block was encountered in parent where that's expected.
1228 *
1229 * - That high keys of child pages matches corresponding pivot keys in parent.
1230 *
1231 * This is also where heapallindexed callers use their Bloom filter to
1232 * fingerprint IndexTuples for later table_index_build_scan() verification.
1233 *
1234 * Note: Memory allocated in this routine is expected to be released by caller
1235 * resetting state->targetcontext.
1236 */
1237static void
1239{
1240 OffsetNumber offset;
1241 OffsetNumber max;
1243
1244 /* Last visible entry info for checking indexes with unique constraint */
1246
1249
1252
1253 /*
1254 * Check the number of attributes in high key. Note, rightmost page
1255 * doesn't contain a high key, so nothing to check
1256 */
1258 {
1259 ItemId itemid;
1260 IndexTuple itup;
1261
1262 /* Verify line pointer before checking tuple */
1266 P_HIKEY))
1267 {
1274 state->targetblock,
1278 }
1279 }
1280
1281 /*
1282 * Loop over page items, starting from first non-highkey item, not high
1283 * key (if any). Most tests are not performed for the "negative infinity"
1284 * real item (if any).
1285 */
1287 offset <= max;
1288 offset = OffsetNumberNext(offset))
1289 {
1290 ItemId itemid;
1291 IndexTuple itup;
1295 ItemPointer scantid;
1296
1297 /*
1298 * True if we already called bt_entry_unique_check() for the current
1299 * item. This helps to avoid visiting the heap for keys, which are
1300 * anyway presented only once and can't comprise a unique violation.
1301 */
1303
1304 CHECK_FOR_INTERRUPTS();
1305
1307 state->target, offset);
1310
1311 /*
1312 * lp_len should match the IndexTuple reported length exactly, since
1313 * lp_len is completely redundant in indexes, and both sources of
1314 * tuple length are MAXALIGN()'d. nbtree does not use lp_len all that
1315 * frequently, and is surprisingly tolerant of corrupt lp_len fields.
1316 */
1323 state->targetblock, offset,
1327
1328 /* Check the number of index tuple attributes */
1330 offset))
1331 {
1332 ItemPointer tid;
1334 *htid;
1335
1337 tid = BTreeTupleGetPointsToTID(itup);
1339 ItemPointerGetBlockNumberNoCheck(tid),
1340 ItemPointerGetOffsetNumberNoCheck(tid));
1341
1347 itid,
1350 htid,
1352 }
1353
1354 /*
1355 * Don't try to generate scankey using "negative infinity" item on
1356 * internal pages. They are always truncated to zero attributes.
1357 */
1359 {
1360 /*
1361 * We don't call bt_child_check() for "negative infinity" items.
1362 * But if we're performing downlink connectivity check, we do it
1363 * for every item including "negative infinity" one.
1364 */
1366 {
1368 offset,
1369 NULL,
1370 topaque->btpo_level);
1371 }
1372 continue;
1373 }
1374
1375 /*
1376 * Readonly callers may optionally verify that non-pivot tuples can
1377 * each be found by an independent search that starts from the root.
1378 * Note that we deliberately don't do individual searches for each
1379 * TID, since the posting list itself is validated by other checks.
1380 */
1383 {
1386 *htid;
1387
1390 ItemPointerGetOffsetNumber(tid));
1391
1399 }
1400
1401 /*
1402 * If tuple is a posting list tuple, make sure posting list TIDs are
1403 * in order
1404 */
1406 {
1407 ItemPointerData last;
1408 ItemPointer current;
1409
1411
1413 {
1414
1416
1418 {
1420
1428 }
1429
1430 ItemPointerCopy(current, &last);
1431 }
1432 }
1433
1434 /* Build insertion scankey for current page offset */
1436
1437 /*
1438 * Make sure tuple size does not exceed the relevant BTREE_VERSION
1439 * specific limit.
1440 *
1441 * BTREE_VERSION 4 (which introduced heapkeyspace rules) requisitioned
1442 * a small amount of space from BTMaxItemSize() in order to ensure
1443 * that suffix truncation always has enough space to add an explicit
1444 * heap TID back to a tuple -- we pessimistically assume that every
1445 * newly inserted tuple will eventually need to have a heap TID
1446 * appended during a future leaf page split, when the tuple becomes
1447 * the basis of the new high key (pivot tuple) for the leaf page.
1448 *
1449 * Since the reclaimed space is reserved for that purpose, we must not
1450 * enforce the slightly lower limit when the extra space has been used
1451 * as intended. In other words, there is only a cross-version
1452 * difference in the limit on tuple size within leaf pages.
1453 *
1454 * Still, we're particular about the details within BTREE_VERSION 4
1455 * internal pages. Pivot tuples may only use the extra space for its
1456 * designated purpose. Enforce the lower limit for pivot tuples when
1457 * an explicit heap TID isn't actually present. (In all other cases
1458 * suffix truncation is guaranteed to generate a pivot tuple that's no
1459 * larger than the firstright tuple provided to it by its caller.)
1460 */
1464 {
1467 *htid;
1468
1471 ItemPointerGetBlockNumberNoCheck(tid),
1472 ItemPointerGetOffsetNumberNoCheck(tid));
1473
1479 itid,
1481 htid,
1483 }
1484
1485 /* Fingerprint leaf page tuples (those that point to the heap) */
1487 {
1489
1491 {
1492 /* Fingerprint all elements as distinct "plain" tuples */
1494 {
1496
1501 /* Be tidy */
1505 }
1506 }
1507 else
1508 {
1512 /* Be tidy */
1515 }
1516 }
1517
1518 /*
1519 * * High key check *
1520 *
1521 * If there is a high key (if this is not the rightmost page on its
1522 * entire level), check that high key actually is upper bound on all
1523 * page items. If this is a posting list tuple, we'll need to set
1524 * scantid to be highest TID in posting list.
1525 *
1526 * We prefer to check all items against high key rather than checking
1527 * just the last and trusting that the operator class obeys the
1528 * transitive law (which implies that all previous items also
1529 * respected the high key invariant if they pass the item order
1530 * check).
1531 *
1532 * Ideally, we'd compare every item in the index against every other
1533 * item in the index, and not trust opclass obedience of the
1534 * transitive law to bridge the gap between children and their
1535 * grandparents (as well as great-grandparents, and so on). We don't
1536 * go to those lengths because that would be prohibitively expensive,
1537 * and probably not markedly more effective in practice.
1538 *
1539 * On the leaf level, we check that the key is <= the highkey.
1540 * However, on non-leaf levels we check that the key is < the highkey,
1541 * because the high key is "just another separator" rather than a copy
1542 * of some existing key item; we expect it to be unique among all keys
1543 * on the same level. (Suffix truncation will sometimes produce a
1544 * leaf highkey that is an untruncated copy of the lastleft item, but
1545 * never any other item, which necessitates weakening the leaf level
1546 * check to <=.)
1547 *
1548 * Full explanation for why a highkey is never truly a copy of another
1549 * item from the same level on internal levels:
1550 *
1551 * While the new left page's high key is copied from the first offset
1552 * on the right page during an internal page split, that's not the
1553 * full story. In effect, internal pages are split in the middle of
1554 * the firstright tuple, not between the would-be lastleft and
1555 * firstright tuples: the firstright key ends up on the left side as
1556 * left's new highkey, and the firstright downlink ends up on the
1557 * right side as right's new "negative infinity" item. The negative
1558 * infinity tuple is truncated to zero attributes, so we're only left
1559 * with the downlink. In other words, the copying is just an
1560 * implementation detail of splitting in the middle of a (pivot)
1561 * tuple. (See also: "Notes About Data Representation" in the nbtree
1562 * README.)
1563 */
1564 scantid = skey->scantid;
1567
1571 {
1574 *htid;
1575
1578 ItemPointerGetBlockNumberNoCheck(tid),
1579 ItemPointerGetOffsetNumberNoCheck(tid));
1580
1586 itid,
1588 htid,
1590 }
1591 /* Reset, in case scantid was set to (itup) posting tuple's max TID */
1592 skey->scantid = scantid;
1593
1594 /*
1595 * * Item order check *
1596 *
1597 * Check that items are stored on page in logical order, by checking
1598 * current item is strictly less than next item (if any).
1599 */
1602 {
1603 ItemPointer tid;
1605 *htid,
1606 *nitid,
1607 *nhtid;
1608
1610 tid = BTreeTupleGetPointsToTID(itup);
1612 ItemPointerGetBlockNumberNoCheck(tid),
1613 ItemPointerGetOffsetNumberNoCheck(tid));
1615 OffsetNumberNext(offset));
1616
1617 /* Reuse itup to get pointed-to heap location of second item */
1619 state->target,
1620 OffsetNumberNext(offset));
1622 tid = BTreeTupleGetPointsToTID(itup);
1624 ItemPointerGetBlockNumberNoCheck(tid),
1625 ItemPointerGetOffsetNumberNoCheck(tid));
1626
1631 errdetail_internal("Lower index tid=%s (points to %s tid=%s) higher index tid=%s (points to %s tid=%s) page lsn=%X/%08X.",
1632 itid,
1634 htid,
1635 nitid,
1637 nhtid,
1639 }
1640
1641 /*
1642 * If the index is unique verify entries uniqueness by checking the
1643 * heap tuples visibility. Immediately check posting tuples and
1644 * tuples with repeated keys. Postpone check for keys, which have the
1645 * first appearance.
1646 */
1650 {
1652 &lVis);
1654 }
1655
1658 {
1659 /* Save current scankey tid */
1660 scantid = skey->scantid;
1661
1662 /*
1663 * Invalidate scankey tid to make _bt_compare compare only keys in
1664 * the item to report equality even if heap TIDs are different
1665 */
1667
1668 /*
1669 * If next key tuple is different, invalidate last visible entry
1670 * data (whole index tuple or last posting in index tuple). Key
1671 * containing null value does not violate unique constraint and
1672 * treated as different to any other key.
1673 *
1674 * If the next key is the same as the previous one, do the
1675 * bt_entry_unique_check() call if it was postponed.
1676 */
1679 {
1682 lVis.postingIndex = -1;
1684 }
1686 {
1688 &lVis);
1689 }
1691 }
1692
1693 /*
1694 * * Last item check *
1695 *
1696 * Check last item against next/right page's first data item's when
1697 * last item on page is reached. This additional check will detect
1698 * transposed pages iff the supposed right sibling page happens to
1699 * belong before target in the key space. (Otherwise, a subsequent
1700 * heap verification will probably detect the problem.)
1701 *
1702 * This check is similar to the item order check that will have
1703 * already been performed for every other "real" item on target page
1704 * when last item is checked. The difference is that the next item
1705 * (the item that is compared to target's last item) needs to come
1706 * from the next/sibling page. There may not be such an item
1707 * available from sibling for various reasons, though (e.g., target is
1708 * the rightmost page on level).
1709 */
1710 if (offset == max)
1711 {
1713
1714 /* first offset on a right index page (log only) */
1716
1717 /* Get item in next/right page */
1719
1722 {
1723 /*
1724 * As explained at length in bt_right_page_check_scankey(),
1725 * there is a known !readonly race that could account for
1726 * apparent violation of invariant, which we must check for
1727 * before actually proceeding with raising error. Our canary
1728 * condition is that target page was deleted.
1729 */
1731 {
1732 /* Get fresh copy of target page */
1734 /* Note that we deliberately do not update target LSN */
1736
1737 /*
1738 * All !readonly checks now performed; just return
1739 */
1741 return;
1742 }
1743
1749 state->targetblock, offset,
1751 }
1752
1753 /*
1754 * If index has unique constraint make sure that no more than one
1755 * found equal items is visible.
1756 */
1759 {
1761
1763
1764 /*
1765 * Make _bt_compare compare only index keys without heap TIDs.
1766 * rightkey->scantid is modified destructively but it is ok
1767 * for it is not used later.
1768 */
1770
1771 /* The first key on the next page is the same */
1773 !rightkey->anynullkeys)
1774 {
1776
1777 /*
1778 * Do the bt_entry_unique_check() call if it was
1779 * postponed.
1780 */
1783 offset, &lVis);
1784
1787 rightblock_number);
1789
1791 {
1793 break;
1794 }
1795
1802 state->targetblock,
1804
1806 rightpage,
1807 rightfirstoffset);
1809
1811
1813 }
1814 }
1815 }
1816
1817 /*
1818 * * Downlink check *
1819 *
1820 * Additional check of child items iff this is an internal page and
1821 * caller holds a ShareLock. This happens for every downlink (item)
1822 * in target excluding the negative-infinity downlink (again, this is
1823 * because it has no useful value to compare).
1824 */
1827 }
1828
1829 /*
1830 * Special case bt_child_highkey_check() call
1831 *
1832 * We don't pass a real downlink, but we've to finish the level
1833 * processing. If condition is satisfied, we've already processed all the
1834 * downlinks from the target level. But there still might be pages to the
1835 * right of the child page pointer to by our rightmost downlink. And they
1836 * might have missing downlinks. This final call checks for them.
1837 */
1839 {
1842 }
1843}
1844
1845/*
1846 * Return a scankey for an item on page to right of current target (or the
1847 * first non-ignorable page), sufficient to check ordering invariant on last
1848 * item in current target page. Returned scankey relies on local memory
1849 * allocated for the child page, which caller cannot pfree(). Caller's memory
1850 * context should be reset between calls here.
1851 *
1852 * This is the first data item, and so all adjacent items are checked against
1853 * their immediate sibling item (which may be on a sibling page, or even a
1854 * "cousin" page at parent boundaries where target's rightlink points to page
1855 * with different parent page). If no such valid item is available, return
1856 * NULL instead.
1857 *
1858 * Note that !readonly callers must reverify that target page has not
1859 * been concurrently deleted.
1860 *
1861 * Save rightfirstoffset for detailed error message.
1862 */
1865{
1866 BTPageOpaque opaque;
1872
1873 /* Determine target's next block number */
1875
1876 /* If target is already rightmost, no right sibling; nothing to do here */
1879
1880 /*
1881 * General notes on concurrent page splits and page deletion:
1882 *
1883 * Routines like _bt_search() don't require *any* page split interlock
1884 * when descending the tree, including something very light like a buffer
1885 * pin. That's why it's okay that we don't either. This avoidance of any
1886 * need to "couple" buffer locks is the raison d' etre of the Lehman & Yao
1887 * algorithm, in fact.
1888 *
1889 * That leaves deletion. A deleted page won't actually be recycled by
1890 * VACUUM early enough for us to fail to at least follow its right link
1891 * (or left link, or downlink) and find its sibling, because recycling
1892 * does not occur until no possible index scan could land on the page.
1893 * Index scans can follow links with nothing more than their snapshot as
1894 * an interlock and be sure of at least that much. (See page
1895 * recycling/"visible to everyone" notes in nbtree README.)
1896 *
1897 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
1898 * dead (ignorable) page one or more times. There will either be a
1899 * further right link to follow that leads to a live page before too long
1900 * (before passing by parent's rightmost child), or we will find the end
1901 * of the entire level instead (possible when parent page is itself the
1902 * rightmost on its level).
1903 */
1905 for (;;)
1906 {
1907 CHECK_FOR_INTERRUPTS();
1908
1911
1913 break;
1914
1915 /*
1916 * We landed on a deleted or half-dead sibling page. Step right until
1917 * we locate a live sibling page.
1918 */
1921 errmsg_internal("level %u sibling page in block %u of index \"%s\" was found deleted or half dead",
1924
1926
1927 /* Be slightly more pro-active in freeing this memory, just in case */
1929 }
1930
1931 /*
1932 * No ShareLock held case -- why it's safe to proceed.
1933 *
1934 * Problem:
1935 *
1936 * We must avoid false positive reports of corruption when caller treats
1937 * item returned here as an upper bound on target's last item. In
1938 * general, false positives are disallowed. Avoiding them here when
1939 * caller is !readonly is subtle.
1940 *
1941 * A concurrent page deletion by VACUUM of the target page can result in
1942 * the insertion of items on to this right sibling page that would
1943 * previously have been inserted on our target page. There might have
1944 * been insertions that followed the target's downlink after it was made
1945 * to point to right sibling instead of target by page deletion's first
1946 * phase. The inserters insert items that would belong on target page.
1947 * This race is very tight, but it's possible. This is our only problem.
1948 *
1949 * Non-problems:
1950 *
1951 * We are not hindered by a concurrent page split of the target; we'll
1952 * never land on the second half of the page anyway. A concurrent split
1953 * of the right page will also not matter, because the first data item
1954 * remains the same within the left half, which we'll reliably land on. If
1955 * we had to skip over ignorable/deleted pages, it cannot matter because
1956 * their key space has already been atomically merged with the first
1957 * non-ignorable page we eventually find (doesn't matter whether the page
1958 * we eventually find is a true sibling or a cousin of target, which we go
1959 * into below).
1960 *
1961 * Solution:
1962 *
1963 * Caller knows that it should reverify that target is not ignorable
1964 * (half-dead or deleted) when cross-page sibling item comparison appears
1965 * to indicate corruption (invariant fails). This detects the single race
1966 * condition that exists for caller. This is correct because the
1967 * continued existence of target block as non-ignorable (not half-dead or
1968 * deleted) implies that target page was not merged into from the right by
1969 * deletion; the key space at or after target never moved left. Target's
1970 * parent either has the same downlink to target as before, or a <
1971 * downlink due to deletion at the left of target. Target either has the
1972 * same highkey as before, or a highkey < before when there is a page
1973 * split. (The rightmost concurrently-split-from-target-page page will
1974 * still have the same highkey as target was originally found to have,
1975 * which for our purposes is equivalent to target's highkey itself never
1976 * changing, since we reliably skip over
1977 * concurrently-split-from-target-page pages.)
1978 *
1979 * In simpler terms, we allow that the key space of the target may expand
1980 * left (the key space can move left on the left side of target only), but
1981 * the target key space cannot expand right and get ahead of us without
1982 * our detecting it. The key space of the target cannot shrink, unless it
1983 * shrinks to zero due to the deletion of the original page, our canary
1984 * condition. (To be very precise, we're a bit stricter than that because
1985 * it might just have been that the target page split and only the
1986 * original target page was deleted. We can be more strict, just not more
1987 * lax.)
1988 *
1989 * Top level tree walk caller moves on to next page (makes it the new
1990 * target) following recovery from this race. (cf. The rationale for
1991 * child/downlink verification needing a ShareLock within
1992 * bt_child_check(), where page deletion is also the main source of
1993 * trouble.)
1994 *
1995 * Note that it doesn't matter if right sibling page here is actually a
1996 * cousin page, because in order for the key space to be readjusted in a
1997 * way that causes us issues in next level up (guiding problematic
1998 * concurrent insertions to the cousin from the grandparent rather than to
1999 * the sibling from the parent), there'd have to be page deletion of
2000 * target's parent page (affecting target's parent's downlink in target's
2001 * grandparent page). Internal page deletion only occurs when there are
2002 * no child pages (they were all fully deleted), and caller is checking
2003 * that the target's parent has at least one non-deleted (so
2004 * non-ignorable) child: the target page. (Note that the first phase of
2005 * deletion atomically marks the page to be deleted half-dead/ignorable at
2006 * the same time downlink in its parent is removed, so caller will
2007 * definitely not fail to detect that this happened.)
2008 *
2009 * This trick is inspired by the method backward scans use for dealing
2010 * with concurrent page splits; concurrent page deletion is a problem that
2011 * similarly receives special consideration sometimes (it's possible that
2012 * the backwards scan will re-read its "original" block after failing to
2013 * find a right-link to it, having already moved in the opposite direction
2014 * (right/"forwards") a few times to try to locate one). Just like us,
2015 * that happens only to determine if there was a concurrent page deletion
2016 * of a reference page, and just like us if there was a page deletion of
2017 * that reference page it means we can move on from caring about the
2018 * reference page. See the nbtree README for a full description of how
2019 * that works.
2020 */
2022
2023 /*
2024 * Get first data item, if any
2025 */
2027 {
2028 /* Return first data item (if any) */
2030 P_FIRSTDATAKEY(opaque));
2032 }
2035 {
2036 /*
2037 * Return first item after the internal page's "negative infinity"
2038 * item
2039 */
2042 }
2043 else
2044 {
2045 /*
2046 * No first item. Page is probably empty leaf page, but it's also
2047 * possible that it's an internal page with only a negative infinity
2048 * item.
2049 */
2056 }
2057
2058 /*
2059 * Return first real item scankey. Note that this relies on right page
2060 * memory remaining allocated.
2061 */
2064}
2065
2066/*
2067 * Check if two tuples are binary identical except the block number. So,
2068 * this function is capable to compare pivot keys on different levels.
2069 */
2070static bool
2072{
2074 return false;
2075
2076 if (heapkeyspace)
2077 {
2078 /*
2079 * Offset number will contain important information in heapkeyspace
2080 * indexes: the number of attributes left in the pivot tuple following
2081 * suffix truncation. Don't skip over it (compare it too).
2082 */
2086 return false;
2087 }
2088 else
2089 {
2090 /*
2091 * Cannot rely on offset number field having consistent value across
2092 * levels on pg_upgrade'd !heapkeyspace indexes. Compare contents of
2093 * tuple starting from just after item pointer (i.e. after block
2094 * number and offset number).
2095 */
2099 return false;
2100 }
2101
2102 return true;
2103}
2104
2105/*---
2106 * Check high keys on the child level. Traverse rightlinks from previous
2107 * downlink to the current one. Check that there are no intermediate pages
2108 * with missing downlinks.
2109 *
2110 * If 'loaded_child' is given, it's assumed to be the page pointed to by the
2111 * downlink referenced by 'downlinkoffnum' of the target page.
2112 *
2113 * Basically this function is called for each target downlink and checks two
2114 * invariants:
2115 *
2116 * 1) You can reach the next child from previous one via rightlinks;
2117 * 2) Each child high key have matching pivot key on target level.
2118 *
2119 * Consider the sample tree picture.
2120 *
2121 * 1
2122 * / \
2123 * 2 <-> 3
2124 * / \ / \
2125 * 4 <> 5 <> 6 <> 7 <> 8
2126 *
2127 * This function will be called for blocks 4, 5, 6 and 8. Consider what is
2128 * happening for each function call.
2129 *
2130 * - The function call for block 4 initializes data structure and matches high
2131 * key of block 4 to downlink's pivot key of block 2.
2132 * - The high key of block 5 is matched to the high key of block 2.
2133 * - The block 6 has an incomplete split flag set, so its high key isn't
2134 * matched to anything.
2135 * - The function call for block 8 checks that block 8 can be found while
2136 * following rightlinks from block 6. The high key of block 7 will be
2137 * matched to downlink's pivot key in block 3.
2138 *
2139 * There is also final call of this function, which checks that there is no
2140 * missing downlinks for children to the right of the child referenced by
2141 * rightmost downlink in target level.
2142 */
2143static void
2148{
2150 Page page;
2151 BTPageOpaque opaque;
2153 bool first = true;
2154 ItemId itemid;
2155 IndexTuple itup;
2156 BlockNumber downlink;
2157
2159 {
2163 downlink = BTreeTupleGetDownLink(itup);
2164 }
2165 else
2166 {
2167 downlink = P_NONE;
2168 }
2169
2170 /*
2171 * If no previous rightlink is memorized for current level just below
2172 * target page's level, we are about to start from the leftmost page. We
2173 * can't follow rightlinks from previous page, because there is no
2174 * previous page. But we still can match high key.
2175 *
2176 * So we initialize variables for the loop above like there is previous
2177 * page referencing current child. Also we imply previous page to not
2178 * have incomplete split flag, that would make us require downlink for
2179 * current child. That's correct, because leftmost page on the level
2180 * should always have parent downlink.
2181 */
2183 {
2184 blkno = downlink;
2186 }
2187
2188 /* Move to the right on the child level */
2189 while (true)
2190 {
2191 /*
2192 * Did we traverse the whole tree level and this is check for pages to
2193 * the right of rightmost downlink?
2194 */
2196 {
2199 return;
2200 }
2201
2202 /* Did we traverse the whole tree level and don't find next downlink? */
2207 state->prevrightlink, downlink,
2209
2210 /* Load page contents */
2212 page = loaded_child;
2213 else
2215
2216 opaque = BTPageGetOpaque(page);
2217
2218 /* The first page we visit at the level should be leftmost */
2226 state->targetblock, blkno,
2228
2229 /* Do level sanity check */
2238
2239 /* Try to detect circular links */
2245
2247 {
2248 /* blkno probably has missing parent downlink */
2250 }
2251
2253
2254 /*
2255 * If we visit page with high key, check that it is equal to the
2256 * target key next to corresponding downlink.
2257 */
2259 {
2263
2264 /* Get high key */
2267
2268 /*
2269 * There might be two situations when we examine high key. If
2270 * current child page is referenced by given target downlink, we
2271 * should look to the next offset number for matching key from
2272 * target page.
2273 *
2274 * Alternatively, we're following rightlinks somewhere in the
2275 * middle between page referenced by previous target's downlink
2276 * and the page referenced by current target's downlink. If
2277 * current child page hasn't incomplete split flag set, then its
2278 * high key should match to the target's key of current offset
2279 * number. This happens when a previous call here (to
2280 * bt_child_highkey_check()) found an incomplete split, and we
2281 * reach a right sibling page without a downlink -- the right
2282 * sibling page's high key still needs to be matched to a
2283 * separator key on the parent/target level.
2284 *
2285 * Don't apply OffsetNumberNext() to target_downlinkoffnum when we
2286 * already had to step right on the child level. Our traversal of
2287 * the child level must try to move in perfect lockstep behind (to
2288 * the left of) the target/parent level traversal.
2289 */
2290 if (blkno == downlink)
2292 else
2294
2296
2298 {
2299 /*
2300 * If we're looking for the next pivot tuple in target page,
2301 * but there is no more pivot tuples, then we should match to
2302 * high key instead.
2303 */
2305 {
2312 state->targetblock, blkno,
2315 }
2319 }
2320 else
2321 {
2322 /*
2323 * We cannot try to match child's high key to a negative
2324 * infinity key in target, since there is nothing to compare.
2325 * However, it's still possible to match child's high key
2326 * outside of target page. The reason why we're are is that
2327 * bt_child_highkey_check() was previously called for the
2328 * cousin page of 'loaded_child', which is incomplete split.
2329 * So, now we traverse to the right of that cousin page and
2330 * current child level page under consideration still belongs
2331 * to the subtree of target's left sibling. Thus, we need to
2332 * match child's high key to its left uncle page high key.
2333 * Thankfully we saved it, it's called a "low key" of target
2334 * page.
2335 */
2342 state->targetblock, blkno,
2344 itup = state->lowkey;
2345 }
2346
2348 {
2354 state->targetblock, blkno,
2356 }
2357 }
2358
2359 /* Exit if we already found next downlink */
2360 if (blkno == downlink)
2361 {
2364 return;
2365 }
2366
2367 /* Traverse to the next page using rightlink */
2368 blkno = opaque->btpo_next;
2369
2370 /* Free page contents if it's allocated by us */
2372 pfree(page);
2373 first = false;
2374 }
2375}
2376
2377/*
2378 * Checks one of target's downlink against its child page.
2379 *
2380 * Conceptually, the target page continues to be what is checked here. The
2381 * target block is still blamed in the event of finding an invariant violation.
2382 * The downlink insertion into the target is probably where any problem raised
2383 * here arises, and there is no such thing as a parent link, so doing the
2384 * verification this way around is much more practical.
2385 *
2386 * This function visits child page and it's sequentially called for each
2387 * downlink of target page. Assuming this we also check downlink connectivity
2388 * here in order to save child page visits.
2389 */
2390static void
2392 OffsetNumber downlinkoffnum)
2393{
2394 ItemId itemid;
2395 IndexTuple itup;
2397 OffsetNumber offset;
2399 Page child;
2402
2404 state->target, downlinkoffnum);
2407
2408 /*
2409 * Caller must have ShareLock on target relation, because of
2410 * considerations around page deletion by VACUUM.
2411 *
2412 * NB: In general, page deletion deletes the right sibling's downlink, not
2413 * the downlink of the page being deleted; the deleted page's downlink is
2414 * reused for its sibling. The key space is thereby consolidated between
2415 * the deleted page and its right sibling. (We cannot delete a parent
2416 * page's rightmost child unless it is the last child page, and we intend
2417 * to also delete the parent itself.)
2418 *
2419 * If this verification happened without a ShareLock, the following race
2420 * condition could cause false positives:
2421 *
2422 * In general, concurrent page deletion might occur, including deletion of
2423 * the left sibling of the child page that is examined here. If such a
2424 * page deletion were to occur, closely followed by an insertion into the
2425 * newly expanded key space of the child, a window for the false positive
2426 * opens up: the stale parent/target downlink originally followed to get
2427 * to the child legitimately ceases to be a lower bound on all items in
2428 * the page, since the key space was concurrently expanded "left".
2429 * (Insertion followed the "new" downlink for the child, not our now-stale
2430 * downlink, which was concurrently physically removed in target/parent as
2431 * part of deletion's first phase.)
2432 *
2433 * While we use various techniques elsewhere to perform cross-page
2434 * verification for !readonly callers, a similar trick seems difficult
2435 * here. The tricks used by bt_recheck_sibling_links and by
2436 * bt_right_page_check_scankey both involve verification of a same-level,
2437 * cross-sibling invariant. Cross-level invariants are far more squishy,
2438 * though. The nbtree REDO routines do not actually couple buffer locks
2439 * across levels during page splits, so making any cross-level check work
2440 * reliably in !readonly mode may be impossible.
2441 */
2443
2444 /*
2445 * Verify child page has the downlink key from target page (its parent) as
2446 * a lower bound; downlink must be strictly less than all keys on the
2447 * page.
2448 *
2449 * Check all items, rather than checking just the first and trusting that
2450 * the operator class obeys the transitive law.
2451 */
2456
2457 /*
2458 * Since we've already loaded the child block, combine this check with
2459 * check for downlink connectivity.
2460 */
2462 child, topaque->btpo_level);
2463
2464 /*
2465 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2466 * and since a page has no links within other pages (siblings and parent)
2467 * once it is marked fully deleted, it should be impossible to land on a
2468 * fully deleted page.
2469 *
2470 * It does not quite make sense to enforce that the page cannot even be
2471 * half-dead, despite the fact the downlink is modified at the same stage
2472 * that the child leaf page is marked half-dead. That's incorrect because
2473 * there may occasionally be multiple downlinks from a chain of pages
2474 * undergoing deletion, where multiple successive calls are made to
2475 * _bt_unlink_halfdead_page() by VACUUM before it can finally safely mark
2476 * the leaf page as fully dead. While _bt_mark_page_halfdead() usually
2477 * removes the downlink to the leaf page that is marked half-dead, that's
2478 * not guaranteed, so it's possible we'll land on a half-dead page with a
2479 * downlink due to an interrupted multi-level page deletion.
2480 *
2481 * We go ahead with our checks if the child page is half-dead. It's safe
2482 * to do so because we do not test the child's high key, so it does not
2483 * matter that the original high key will have been replaced by a dummy
2484 * truncated high key within _bt_mark_page_halfdead(). All other page
2485 * items are left intact on a half-dead page, so there is still something
2486 * to test.
2487 */
2496
2498 offset <= maxoffset;
2499 offset = OffsetNumberNext(offset))
2500 {
2501 /*
2502 * Skip comparison of target page key against "negative infinity"
2503 * item, if any. Checking it would indicate that it's not a strict
2504 * lower bound, but that's only because of the hard-coding for
2505 * negative infinity items within _bt_compare().
2506 *
2507 * If nbtree didn't truncate negative infinity tuples during internal
2508 * page splits then we'd expect child's negative infinity key to be
2509 * equal to the scankey/downlink from target/parent (it would be a
2510 * "low key" in this hypothetical scenario, and so it would still need
2511 * to be treated as a special case here).
2512 *
2513 * Negative infinity items can be thought of as a strict lower bound
2514 * that works transitively, with the last non-negative-infinity pivot
2515 * followed during a descent from the root as its "true" strict lower
2516 * bound. Only a small number of negative infinity items are truly
2517 * negative infinity; those that are the first items of leftmost
2518 * internal pages. In more general terms, a negative infinity item is
2519 * only negative infinity with respect to the subtree that the page is
2520 * at the root of.
2521 *
2522 * See also: bt_rootdescend(), which can even detect transitive
2523 * inconsistencies on cousin leaf pages.
2524 */
2526 continue;
2527
2529 offset))
2537 }
2538
2539 pfree(child);
2540}
2541
2542/*
2543 * Checks if page is missing a downlink that it should have.
2544 *
2545 * A page that lacks a downlink/parent may indicate corruption. However, we
2546 * must account for the fact that a missing downlink can occasionally be
2547 * encountered in a non-corrupt index. This can be due to an interrupted page
2548 * split, or an interrupted multi-level page deletion (i.e. there was a hard
2549 * crash or an error during a page split, or while VACUUM was deleting a
2550 * multi-level chain of pages).
2551 *
2552 * Note that this can only be called in readonly mode, so there is no need to
2553 * be concerned about concurrent page splits or page deletions.
2554 */
2555static void
2558{
2560 ItemId itemid;
2561 IndexTuple itup;
2562 Page child;
2564 uint32 level;
2567
2570
2571 /* No next level up with downlinks to fingerprint from the true root */
2573 return;
2574
2576
2577 /*
2578 * Incomplete (interrupted) page splits can account for the lack of a
2579 * downlink. Some inserting transaction should eventually complete the
2580 * page split in passing, when it notices that the left sibling page is
2581 * P_INCOMPLETE_SPLIT().
2582 *
2583 * In general, VACUUM is not prepared for there to be no downlink to a
2584 * page that it deletes. This is the main reason why the lack of a
2585 * downlink can be reported as corruption here. It's not obvious that an
2586 * invalid missing downlink can result in wrong answers to queries,
2587 * though, since index scans that land on the child may end up
2588 * consistently moving right. The handling of concurrent page splits (and
2589 * page deletions) within _bt_moveright() cannot distinguish
2590 * inconsistencies that last for a moment from inconsistencies that are
2591 * permanent and irrecoverable.
2592 *
2593 * VACUUM isn't even prepared to delete pages that have no downlink due to
2594 * an incomplete page split, but it can detect and reason about that case
2595 * by design, so it shouldn't be taken to indicate corruption. See
2596 * _bt_pagedel() for full details.
2597 */
2599 {
2605 blkno, opaque->btpo_level,
2606 opaque->btpo_prev,
2608 return;
2609 }
2610
2611 /*
2612 * Page under check is probably the "top parent" of a multi-level page
2613 * deletion. We'll need to descend the subtree to make sure that
2614 * descendant pages are consistent with that, though.
2615 *
2616 * If the page (which must be non-ignorable) is a leaf page, then clearly
2617 * it can't be the top parent. The lack of a downlink is probably a
2618 * symptom of a broad problem that could just as easily cause
2619 * inconsistencies anywhere else.
2620 */
2627 blkno,
2629
2630 /* Descend from the given page, which is an internal page */
2631 elog(DEBUG1, "checking for interrupted multi-level deletion due to missing downlink in index \"%s\"",
2633
2634 level = opaque->btpo_level;
2638 for (;;)
2639 {
2640 CHECK_FOR_INTERRUPTS();
2641
2644
2646 break;
2647
2648 /* Do an extra sanity check in passing on internal pages */
2654 errdetail_internal("Top parent/under check block=%u block pointed to=%u expected level=%u level in pointed to block=%u.",
2655 blkno, childblk,
2656 level - 1, copaque->btpo_level)));
2657
2658 level = copaque->btpo_level;
2663 /* Be slightly more pro-active in freeing this memory, just in case */
2664 pfree(child);
2665 }
2666
2667 /*
2668 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2669 * and since a page has no links within other pages (siblings and parent)
2670 * once it is marked fully deleted, it should be impossible to land on a
2671 * fully deleted page. See bt_child_check() for further details.
2672 *
2673 * The bt_child_check() P_ISDELETED() check is repeated here because
2674 * bt_child_check() does not visit pages reachable through negative
2675 * infinity items. Besides, bt_child_check() is unwilling to descend
2676 * multiple levels. (The similar bt_child_check() P_ISDELETED() check
2677 * within bt_check_level_from_leftmost() won't reach the page either,
2678 * since the leaf's live siblings should have their sibling links updated
2679 * to bypass the deletion target page when it is marked fully dead.)
2680 *
2681 * If this error is raised, it might be due to a previous multi-level page
2682 * deletion that failed to realize that it wasn't yet safe to mark the
2683 * leaf page as fully dead. A "dangling downlink" will still remain when
2684 * this happens. The fact that the dangling downlink's page (the leaf's
2685 * parent/ancestor page) lacked a downlink is incidental.
2686 */
2692 errdetail_internal("Top parent/target block=%u leaf block=%u top parent/under check lsn=%X/%08X.",
2693 blkno, childblk,
2695
2696 /*
2697 * Iff leaf page is half-dead, its high key top parent link should point
2698 * to what VACUUM considered to be the top parent page at the instant it
2699 * was interrupted. Provided the high key link actually points to the
2700 * page under check, the missing downlink we detected is consistent with
2701 * there having been an interrupted multi-level page deletion. This means
2702 * that the subtree with the page under check at its root (a page deletion
2703 * chain) is in a consistent state, enabling VACUUM to resume deleting the
2704 * entire chain the next time it encounters the half-dead leaf page.
2705 */
2707 {
2711 return;
2712 }
2713
2719 blkno, opaque->btpo_level,
2721}
2722
2723/*
2724 * Per-tuple callback from table_index_build_scan, used to determine if index has
2725 * all the entries that definitely should have been observed in leaf pages of
2726 * the target index (that is, all IndexTuples that were fingerprinted by our
2727 * Bloom filter). All heapallindexed checks occur here.
2728 *
2729 * The redundancy between an index and the table it indexes provides a good
2730 * opportunity to detect corruption, especially corruption within the table.
2731 * The high level principle behind the verification performed here is that any
2732 * IndexTuple that should be in an index following a fresh CREATE INDEX (based
2733 * on the same index definition) should also have been in the original,
2734 * existing index, which should have used exactly the same representation
2735 *
2736 * Since the overall structure of the index has already been verified, the most
2737 * likely explanation for error here is a corrupt heap page (could be logical
2738 * or physical corruption). Index corruption may still be detected here,
2739 * though. Only readonly callers will have verified that left links and right
2740 * links are in agreement, and so it's possible that a leaf page transposition
2741 * within index is actually the source of corruption detected here (for
2742 * !readonly callers). The checks performed only for readonly callers might
2743 * more accurately frame the problem as a cross-page invariant issue (this
2744 * could even be due to recovery not replaying all WAL records). The !readonly
2745 * ERROR message raised here includes a HINT about retrying with readonly
2746 * verification, just in case it's a cross-page invariant issue, though that
2747 * isn't particularly likely.
2748 *
2749 * table_index_build_scan() expects to be able to find the root tuple when a
2750 * heap-only tuple (the live tuple at the end of some HOT chain) needs to be
2751 * indexed, in order to replace the actual tuple's TID with the root tuple's
2752 * TID (which is what we're actually passed back here). The index build heap
2753 * scan code will raise an error when a tuple that claims to be the root of the
2754 * heap-only tuple's HOT chain cannot be located. This catches cases where the
2755 * original root item offset/root tuple for a HOT chain indicates (for whatever
2756 * reason) that the entire HOT chain is dead, despite the fact that the latest
2757 * heap-only tuple should be indexed. When this happens, sequential scans may
2758 * always give correct answers, and all indexes may be considered structurally
2759 * consistent (i.e. the nbtree structural checks would not detect corruption).
2760 * It may be the case that only index scans give wrong answers, and yet heap or
2761 * SLRU corruption is the real culprit. (While it's true that LP_DEAD bit
2762 * setting will probably also leave the index in a corrupt state before too
2763 * long, the problem is nonetheless that there is heap corruption.)
2764 *
2765 * Heap-only tuple handling within table_index_build_scan() works in a way that
2766 * helps us to detect index tuples that contain the wrong values (values that
2767 * don't match the latest tuple in the HOT chain). This can happen when there
2768 * is no superseding index tuple due to a faulty assessment of HOT safety,
2769 * perhaps during the original CREATE INDEX. Because the latest tuple's
2770 * contents are used with the root TID, an error will be raised when a tuple
2771 * with the same TID but non-matching attribute values is passed back to us.
2772 * Faulty assessment of HOT-safety was behind at least two distinct CREATE
2773 * INDEX CONCURRENTLY bugs that made it into stable releases, one of which was
2774 * undetected for many years. In short, the same principle that allows a
2775 * REINDEX to repair corruption when there was an (undetected) broken HOT chain
2776 * also allows us to detect the corruption in many cases.
2777 */
2778static void
2781{
2783 IndexTuple itup,
2784 norm;
2785
2787
2788 /* Generate a normalized index tuple for fingerprinting */
2790 itup->t_tid = *tid;
2792
2793 /* Probe Bloom filter -- tuple should be present */
2803 !state->readonly
2804 ? errhint("Retrying verification using the function bt_index_parent_check() might provide a more specific error.")
2805 : 0));
2806
2807 state->heaptuplespresent++;
2808 pfree(itup);
2809 /* Cannot leak memory here */
2812}
2813
2814/*
2815 * Normalize an index tuple for fingerprinting.
2816 *
2817 * In general, index tuple formation is assumed to be deterministic by
2818 * heapallindexed verification, and IndexTuples are assumed immutable. While
2819 * the LP_DEAD bit is mutable in leaf pages, that's ItemId metadata, which is
2820 * not fingerprinted. Normalization is required to compensate for corner
2821 * cases where the determinism assumption doesn't quite work.
2822 *
2823 * There is currently one such case: index_form_tuple() does not try to hide
2824 * the source TOAST state of input datums. The executor applies TOAST
2825 * compression for heap tuples based on different criteria to the compression
2826 * applied within btinsert()'s call to index_form_tuple(): it sometimes
2827 * compresses more aggressively, resulting in compressed heap tuple datums but
2828 * uncompressed corresponding index tuple datums. A subsequent heapallindexed
2829 * verification will get a logically equivalent though bitwise unequal tuple
2830 * from index_form_tuple(). False positive heapallindexed corruption reports
2831 * could occur without normalizing away the inconsistency.
2832 *
2833 * Returned tuple is often caller's own original tuple. Otherwise, it is a
2834 * new representation of caller's original index tuple, palloc()'d in caller's
2835 * memory context.
2836 *
2837 * Note: This routine is not concerned with distinctions about the
2838 * representation of tuples beyond those that might break heapallindexed
2839 * verification. In particular, it won't try to normalize opclass-equal
2840 * datums with potentially distinct representations (e.g., btree/numeric_ops
2841 * index datums will not get their display scale normalized-away here).
2842 * Caller does normalization for non-pivot tuples that have a posting list,
2843 * since dummy CREATE INDEX callback code generates new tuples with the same
2844 * normalized representation.
2845 */
2848{
2856
2857 /* Caller should only pass "logical" non-pivot tuples here */
2859
2860 /* Easy case: It's immediately clear that tuple has no varlena datums */
2862 return itup;
2863
2865 {
2867
2869
2870 /* Assume untoasted/already normalized datum initially */
2873 tupleDescriptor,
2874 &isnull[i]);
2876 continue;
2877
2878 /*
2879 * Callers always pass a tuple that could safely be inserted into the
2880 * index without further processing, so an external varlena header
2881 * should never be encountered here
2882 */
2894 {
2895 /*
2896 * This value will be compressed by index_form_tuple() with the
2897 * current storage settings. We may be here because this tuple
2898 * was formed with different storage settings. So, force forming.
2899 */
2901 }
2903 {
2907 }
2908
2909 /*
2910 * Short tuples may have 1B or 4B header. Convert 4B header of short
2911 * tuples to 1B
2912 */
2914 {
2915 /* convert to short varlena */
2918
2921
2925 }
2926 }
2927
2928 /*
2929 * Easier case: Tuple has varlena datums, none of which are compressed or
2930 * short with 4B header
2931 */
2933 return itup;
2934
2935 /*
2936 * Hard case: Tuple had compressed varlena datums that necessitate
2937 * creating normalized version of the tuple from uncompressed input datums
2938 * (normalized input datums). This is rather naive, but shouldn't be
2939 * necessary too often.
2940 *
2941 * In the heap, tuples may contain short varlena datums with both 1B
2942 * header and 4B headers. But the corresponding index tuple should always
2943 * have such varlena's with 1B headers. So, if there is a short varlena
2944 * with 4B header, we need to convert it for fingerprinting.
2945 *
2946 * Note that we rely on deterministic index_form_tuple() TOAST compression
2947 * of normalized input.
2948 */
2951
2952 /* Cannot leak memory here */
2956
2958}
2959
2960/*
2961 * Produce palloc()'d "plain" tuple for nth posting list entry/TID.
2962 *
2963 * In general, deduplication is not supposed to change the logical contents of
2964 * an index. Multiple index tuples are merged together into one equivalent
2965 * posting list index tuple when convenient.
2966 *
2967 * heapallindexed verification must normalize-away this variation in
2968 * representation by converting posting list tuples into two or more "plain"
2969 * tuples. Each tuple must be fingerprinted separately -- there must be one
2970 * tuple for each corresponding Bloom filter probe during the heap scan.
2971 *
2972 * Note: Caller still needs to call bt_normalize_tuple() with returned tuple.
2973 */
2976{
2978
2979 /* Returns non-posting-list tuple */
2981}
2982
2983/*
2984 * Search for itup in index, starting from fast root page. itup must be a
2985 * non-pivot tuple. This is only supported with heapkeyspace indexes, since
2986 * we rely on having fully unique keys to find a match with only a single
2987 * visit to a leaf page, barring an interrupted page split, where we may have
2988 * to move right. (A concurrent page split is impossible because caller must
2989 * be readonly caller.)
2990 *
2991 * This routine can detect very subtle transitive consistency issues across
2992 * more than one level of the tree. Leaf pages all have a high key (even the
2993 * rightmost page has a conceptual positive infinity high key), but not a low
2994 * key. Their downlink in parent is a lower bound, which along with the high
2995 * key is almost enough to detect every possible inconsistency. A downlink
2996 * separator key value won't always be available from parent, though, because
2997 * the first items of internal pages are negative infinity items, truncated
2998 * down to zero attributes during internal page splits. While it's true that
2999 * bt_child_check() and the high key check can detect most imaginable key
3000 * space problems, there are remaining problems it won't detect with non-pivot
3001 * tuples in cousin leaf pages. Starting a search from the root for every
3002 * existing leaf tuple detects small inconsistencies in upper levels of the
3003 * tree that cannot be detected any other way. (Besides all this, this is
3004 * probably also useful as a direct test of the code used by index scans
3005 * themselves.)
3006 */
3007static bool
3009{
3011 BTStack stack;
3014
3017
3018 /*
3019 * Search from root.
3020 *
3021 * Ideally, we would arrange to only move right within _bt_search() when
3022 * an interrupted page split is detected (i.e. when the incomplete split
3023 * bit is found to be set), but for now we accept the possibility that
3024 * that could conceal an inconsistency.
3025 */
3029
3031 {
3033 OffsetNumber offnum;
3034 Page page;
3035
3039 insertstate.postingoff = 0;
3042
3043 /* Get matching tuple on leaf page */
3045 /* Compare first >= matching item on leaf page, if any */
3047 /* Should match on first heap TID when tuple has a posting list */
3049 insertstate.postingoff <= 0 &&
3053 }
3054
3055 _bt_freestack(stack);
3056 pfree(key);
3057
3059}
3060
3061/*
3062 * Is particular offset within page (whose special state is passed by caller)
3063 * the page negative-infinity item?
3064 *
3065 * As noted in comments above _bt_compare(), there is special handling of the
3066 * first data item as a "negative infinity" item. The hard-coding within
3067 * _bt_compare() makes comparing this item for the purposes of verification
3068 * pointless at best, since the IndexTuple only contains a valid TID (a
3069 * reference TID to child page).
3070 */
3071static inline bool
3073{
3074 /*
3075 * For internal pages only, the first item after high key, if any, is
3076 * negative infinity item. Internal pages always have a negative infinity
3077 * item, whereas leaf pages never have one. This implies that negative
3078 * infinity item is either first or second line item, or there is none
3079 * within page.
3080 *
3081 * Negative infinity items are a special case among pivot tuples. They
3082 * always have zero attributes, while all other pivot tuples always have
3083 * nkeyatts attributes.
3084 *
3085 * Right-most pages don't have a high key, but could be said to
3086 * conceptually have a "positive infinity" high key. Thus, there is a
3087 * symmetry between down link items in parent pages, and high keys in
3088 * children. Together, they represent the part of the key space that
3089 * belongs to each page in the index. For example, all children of the
3090 * root page will have negative infinity as a lower bound from root
3091 * negative infinity downlink, and positive infinity as an upper bound
3092 * (implicitly, from "imaginary" positive infinity high key in root).
3093 */
3095}
3096
3097/*
3098 * Does the invariant hold that the key is strictly less than a given upper
3099 * bound offset item?
3100 *
3101 * Verifies line pointer on behalf of caller.
3102 *
3103 * If this function returns false, convention is that caller throws error due
3104 * to corruption.
3105 */
3106static inline bool
3109{
3110 ItemId itemid;
3112
3114
3115 /* Verify line pointer before checking tuple */
3117 upperbound);
3118 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3121
3123
3124 /*
3125 * _bt_compare() is capable of determining that a scankey with a
3126 * filled-out attribute is greater than pivot tuples where the comparison
3127 * is resolved at a truncated attribute (value of attribute in pivot is
3128 * minus infinity). However, it is not capable of determining that a
3129 * scankey is _less than_ a tuple on the basis of a comparison resolved at
3130 * _scankey_ minus infinity attribute. Complete an extra step to simulate
3131 * having minus infinity values for omitted scankey attribute(s).
3132 */
3134 {
3140
3144
3145 /* Get number of keys + heap TID for item to the right */
3148
3149 /* Heap TID is tiebreaker key attribute */
3152
3154 }
3155
3157}
3158
3159/*
3160 * Does the invariant hold that the key is less than or equal to a given upper
3161 * bound offset item?
3162 *
3163 * Caller should have verified that upperbound's line pointer is consistent
3164 * using PageGetItemIdCareful() call.
3165 *
3166 * If this function returns false, convention is that caller throws error due
3167 * to corruption.
3168 */
3169static inline bool
3172{
3174
3176
3178
3180}
3181
3182/*
3183 * Does the invariant hold that the key is strictly greater than a given lower
3184 * bound offset item?
3185 *
3186 * Caller should have verified that lowerbound's line pointer is consistent
3187 * using PageGetItemIdCareful() call.
3188 *
3189 * If this function returns false, convention is that caller throws error due
3190 * to corruption.
3191 */
3192static inline bool
3195{
3197
3199
3201
3202 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3205
3206 /*
3207 * No need to consider the possibility that scankey has attributes that we
3208 * need to force to be interpreted as negative infinity. _bt_compare() is
3209 * able to determine that scankey is greater than negative infinity. The
3210 * distinction between "==" and "<" isn't interesting here, since
3211 * corruption is indicated either way.
3212 */
3214}
3215
3216/*
3217 * Does the invariant hold that the key is strictly less than a given upper
3218 * bound offset item, with the offset relating to a caller-supplied page that
3219 * is not the current target page?
3220 *
3221 * Caller's non-target page is a child page of the target, checked as part of
3222 * checking a property of the target page (i.e. the key comes from the
3223 * target). Verifies line pointer on behalf of caller.
3224 *
3225 * If this function returns false, convention is that caller throws error due
3226 * to corruption.
3227 */
3228static inline bool
3232{
3233 ItemId itemid;
3235
3237
3238 /* Verify line pointer before checking tuple */
3240 upperbound);
3242
3243 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3246
3247 /* See invariant_l_offset() for an explanation of this extra step */
3249 {
3250 IndexTuple child;
3255
3259
3260 /* Get number of keys + heap TID for child/non-target item */
3263
3264 /* Heap TID is tiebreaker key attribute */
3267
3269 }
3270
3272}
3273
3274/*
3275 * Given a block number of a B-Tree page, return page in palloc()'d memory.
3276 * While at it, perform some basic checks of the page.
3277 *
3278 * There is never an attempt to get a consistent view of multiple pages using
3279 * multiple concurrent buffer locks; in general, we only acquire a single pin
3280 * and buffer lock at a time, which is often all that the nbtree code requires.
3281 * (Actually, bt_recheck_sibling_links couples buffer locks, which is the only
3282 * exception to this general rule.)
3283 *
3284 * Operating on a copy of the page is useful because it prevents control
3285 * getting stuck in an uninterruptible state when an underlying operator class
3286 * misbehaves.
3287 */
3290{
3291 Buffer buffer;
3292 Page page;
3293 BTPageOpaque opaque;
3295
3297
3298 /*
3299 * We copy the page into local storage to avoid holding pin on the buffer
3300 * longer than we must.
3301 */
3303 state->checkstrategy);
3305
3306 /*
3307 * Perform the same basic sanity checking that nbtree itself performs for
3308 * every page:
3309 */
3311
3312 /* Only use copy of page in palloc()'d memory */
3314 UnlockReleaseBuffer(buffer);
3315
3316 opaque = BTPageGetOpaque(page);
3317
3323
3324 /* Check page from block that ought to be meta page */
3326 {
3328
3335
3341 "current version %d, minimum supported version %d",
3344 BTREE_MIN_VERSION)));
3345
3346 /* Finished with metapage checks */
3347 return page;
3348 }
3349
3350 /*
3351 * Deleted pages that still use the old 32-bit XID representation have no
3352 * sane "level" field because they type pun the field, but all other pages
3353 * (including pages deleted on Postgres 14+) have a valid value.
3354 */
3356 {
3357 /* Okay, no reason not to trust btpo_level field from page */
3358
3363 opaque->btpo_level, blocknum,
3365
3370 blocknum,
3372 }
3373
3374 /*
3375 * Sanity checks for number of items on page.
3376 *
3377 * As noted at the beginning of _bt_binsrch(), an internal page must have
3378 * children, since there must always be a negative infinity downlink
3379 * (there may also be a highkey). In the case of non-rightmost leaf
3380 * pages, there must be at least a highkey. The exceptions are deleted
3381 * pages, which contain no items.
3382 *
3383 * This is correct when pages are half-dead, since internal pages are
3384 * never half-dead, and leaf pages must have a high key when half-dead
3385 * (the rightmost page can never be deleted). It's also correct with
3386 * fully deleted pages: _bt_unlink_halfdead_page() doesn't change anything
3387 * about the target page other than setting the page as fully dead, and
3388 * setting its xact field. In particular, it doesn't change the sibling
3389 * links in the deletion target itself, since they're required when index
3390 * scans land on the deletion target, and then need to move right (or need
3391 * to move left, in the case of backward index scans).
3392 */
3399 MaxIndexTuplesPerPage)));
3400
3406
3412
3413 /*
3414 * In general, internal pages are never marked half-dead, except on
3415 * versions of Postgres prior to 9.4, where it can be valid transient
3416 * state. This state is nonetheless treated as corruption by VACUUM on
3417 * from version 9.4 on, so do the same here. See _bt_pagedel() for full
3418 * details.
3419 */
3425 errhint("This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));
3426
3427 /*
3428 * Check that internal pages have no garbage items, and that no page has
3429 * an invalid combination of deletion-related page level flags
3430 */
3436
3440 errmsg_internal("full transaction id page flag appears in non-deleted block %u in index \"%s\"",
3442
3448
3449 return page;
3450}
3451
3452/*
3453 * _bt_mkscankey() wrapper that automatically prevents insertion scankey from
3454 * being considered greater than the pivot tuple that its values originated
3455 * from (or some other identical pivot tuple) in the common case where there
3456 * are truncated/minus infinity attributes. Without this extra step, there
3457 * are forms of corruption that amcheck could theoretically fail to report.
3458 *
3459 * For example, invariant_g_offset() might miss a cross-page invariant failure
3460 * on an internal level if the scankey built from the first item on the
3461 * target's right sibling page happened to be equal to (not greater than) the
3462 * last item on target page. The !backward tiebreaker in _bt_compare() might
3463 * otherwise cause amcheck to assume (rather than actually verify) that the
3464 * scankey is greater.
3465 */
3468{
3470
3473
3475}
3476
3477/*
3478 * PageGetItemId() wrapper that validates returned line pointer.
3479 *
3480 * Buffer page/page item access macros generally trust that line pointers are
3481 * not corrupt, which might cause problems for verification itself. For
3482 * example, there is no bounds checking in PageGetItem(). Passing it a
3483 * corrupt line pointer can cause it to return a tuple/pointer that is unsafe
3484 * to dereference.
3485 *
3486 * Validating line pointers before tuples avoids undefined behavior and
3487 * assertion failures with corrupt indexes, making the verification process
3488 * more robust and predictable.
3489 */
3492 OffsetNumber offset)
3493{
3495
3503 block, offset, ItemIdGetOffset(itemid),
3504 ItemIdGetLength(itemid),
3505 ItemIdGetFlags(itemid))));
3506
3507 /*
3508 * Verify that line pointer isn't LP_REDIRECT or LP_UNUSED, since nbtree
3509 * never uses either. Verify that line pointer has storage, too, since
3510 * even LP_DEAD items should within nbtree.
3511 */
3513 ItemIdGetLength(itemid) == 0)
3519 block, offset, ItemIdGetOffset(itemid),
3520 ItemIdGetLength(itemid),
3521 ItemIdGetFlags(itemid))));
3522
3523 return itemid;
3524}
3525
3526/*
3527 * BTreeTupleGetHeapTID() wrapper that enforces that a heap TID is present in
3528 * cases where that is mandatory (i.e. for non-pivot tuples)
3529 */
3533{
3535
3536 /*
3537 * Caller determines whether this is supposed to be a pivot or non-pivot
3538 * tuple using page type and item offset number. Verify that tuple
3539 * metadata agrees with this.
3540 */
3545 errmsg_internal("block %u or its right sibling block or child block in index \"%s\" has unexpected pivot tuple",
3546 state->targetblock,
3548
3552 errmsg_internal("block %u or its right sibling block or child block in index \"%s\" has unexpected non-pivot tuple",
3553 state->targetblock,
3555
3560 errmsg("block %u or its right sibling block or child block in index \"%s\" contains non-pivot tuple that lacks a heap TID",
3561 state->targetblock,
3563
3565}
3566
3567/*
3568 * Return the "pointed to" TID for itup, which is used to generate a
3569 * descriptive error message. itup must be a "data item" tuple (it wouldn't
3570 * make much sense to call here with a high key tuple, since there won't be a
3571 * valid downlink/block number to display).
3572 *
3573 * Returns either a heap TID (which will be the first heap TID in posting list
3574 * if itup is posting list tuple), or a TID that contains downlink block
3575 * number, plus some encoded metadata (e.g., the number of attributes present
3576 * in itup).
3577 */
3580{
3581 /*
3582 * Rely on the assumption that !heapkeyspace internal page data items will
3583 * correctly return TID with downlink here -- BTreeTupleGetHeapTID() won't
3584 * recognize it as a pivot tuple, but everything still works out because
3585 * the t_tid field is still returned
3586 */
3589
3590 /* Pivot tuple returns TID with downlink block (heapkeyspace variant) */
3592}
bloom_filter * bloom_create(int64 total_elems, int bloom_work_mem, uint64 seed)
Definition bloomfilter.c:87
bool bloom_lacks_element(bloom_filter *filter, unsigned char *elem, size_t len)
Definition bloomfilter.c:157
void bloom_add_element(bloom_filter *filter, unsigned char *elem, size_t len)
Definition bloomfilter.c:135
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition bufmgr.c:911
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition bufpage.h:243
static void * PageGetItem(PageData *page, const ItemIdData *itemId)
Definition bufpage.h:353
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
Definition bufpage.h:371
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition execTuples.c:1443
BufferAccessStrategy GetAccessStrategy(BufferAccessStrategyType btype)
Definition freelist.c:461
static TransactionId HeapTupleHeaderGetXmin(const HeapTupleHeaderData *tup)
Definition htup_details.h:324
IndexTuple index_form_tuple(TupleDesc tupleDescriptor, const Datum *values, const bool *isnull)
Definition indextuple.c:44
int32 ItemPointerCompare(const ItemPointerData *arg1, const ItemPointerData *arg2)
Definition itemptr.c:51
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition itemptr.h:124
static OffsetNumber ItemPointerGetOffsetNumberNoCheck(const ItemPointerData *pointer)
Definition itemptr.h:114
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition itemptr.h:103
static BlockNumber ItemPointerGetBlockNumberNoCheck(const ItemPointerData *pointer)
Definition itemptr.h:93
static void ItemPointerCopy(const ItemPointerData *fromPointer, ItemPointerData *toPointer)
Definition itemptr.h:172
static bool ItemPointerIsValid(const ItemPointerData *pointer)
Definition itemptr.h:83
static bool IndexTupleHasVarwidths(const IndexTupleData *itup)
Definition itup.h:83
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition itup.h:131
IndexTuple _bt_form_posting(IndexTuple base, const ItemPointerData *htids, int nhtids)
Definition nbtdedup.c:862
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
Definition nbtpage.c:740
static BlockNumber BTreeTupleGetTopParent(IndexTuple leafhikey)
Definition nbtree.h:621
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
Definition nbtree.h:545
static BlockNumber BTreeTupleGetDownLink(IndexTuple pivot)
Definition nbtree.h:557
static ItemPointer BTreeTupleGetMaxHeapTID(IndexTuple itup)
Definition nbtree.h:665
BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access)
Definition nbtsearch.c:98
OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
Definition nbtsearch.c:470
int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum)
Definition nbtsearch.c:684
bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
Definition nbtutils.c:964
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition palloc.h:124
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition rel.h:533
Definition verify_nbtree.c:169
Definition nbtree.h:821
Definition nbtree.h:105
Definition nbtree.h:64
Definition nbtree.h:796
Definition nbtree.h:744
Definition verify_nbtree.c:71
Definition verify_nbtree.c:157
Definition verify_nbtree.c:141
Definition freelist.c:65
Definition execnodes.h:165
Definition itup.h:36
Definition itemid.h:26
Definition itemptr.h:37
Definition memnodes.h:118
Definition rel.h:56
Definition snapshot.h:139
Definition relscan.h:33
Definition tupdesc.h:136
Definition tuptable.h:114
Definition bloomfilter.c:45
Definition regguts.h:323
TupleTableSlot * table_slot_create(Relation relation, List **reglist)
Definition tableam.c:92
static double table_index_build_scan(Relation table_rel, Relation index_rel, IndexInfo *index_info, bool allow_sync, bool progress, IndexBuildCallback callback, void *callback_state, TableScanDesc scan)
Definition tableam.h:1766
static TableScanDesc table_beginscan_strat(Relation rel, Snapshot snapshot, int nkeys, ScanKeyData *key, bool allow_strat, bool allow_sync)
Definition tableam.h:921
static bool table_tuple_fetch_row_version(Relation rel, ItemPointer tid, Snapshot snapshot, TupleTableSlot *slot)
Definition tableam.h:1275
static bool TransactionIdPrecedes(TransactionId id1, TransactionId id2)
Definition transam.h:263
static FormData_pg_attribute * TupleDescAttr(TupleDesc tupdesc, int i)
Definition tupdesc.h:160
static Size VARATT_CONVERTED_SHORT_SIZE(const void *PTR)
Definition varatt.h:425
void amcheck_lock_relation_and_check(Oid indrelid, Oid am_id, IndexDoCheckCallback check, LOCKMODE lockmode, void *state)
Definition verify_common.c:62
static bool offset_is_negative_infinity(BTPageOpaque opaque, OffsetNumber offset)
Definition verify_nbtree.c:3073
static bool bt_leftmost_ignoring_half_dead(BtreeCheckState *state, BlockNumber start, BTPageOpaque start_opaque)
Definition verify_nbtree.c:1010
static bool invariant_l_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber upperbound)
Definition verify_nbtree.c:3108
static ItemPointer BTreeTupleGetPointsToTID(IndexTuple itup)
Definition verify_nbtree.c:3580
static IndexTuple bt_posting_plain_tuple(IndexTuple itup, int n)
Definition verify_nbtree.c:2976
static void bt_target_page_check(BtreeCheckState *state)
Definition verify_nbtree.c:1239
static void bt_check_every_level(Relation rel, Relation heaprel, bool heapkeyspace, bool readonly, bool heapallindexed, bool rootdescend, bool checkunique)
Definition verify_nbtree.c:378
static void bt_report_duplicate(BtreeCheckState *state, BtreeLastVisibleEntry *lVis, ItemPointer nexttid, BlockNumber nblock, OffsetNumber noffset, int nposting)
Definition verify_nbtree.c:871
static bool bt_pivot_tuple_identical(bool heapkeyspace, IndexTuple itup1, IndexTuple itup2)
Definition verify_nbtree.c:2072
static bool invariant_leq_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber upperbound)
Definition verify_nbtree.c:3171
static void bt_child_highkey_check(BtreeCheckState *state, OffsetNumber target_downlinkoffnum, Page loaded_child, uint32 target_level)
Definition verify_nbtree.c:2145
static bool heap_entry_is_visible(BtreeCheckState *state, ItemPointer tid)
Definition verify_nbtree.c:852
static BTScanInsert bt_mkscankey_pivotsearch(Relation rel, IndexTuple itup)
Definition verify_nbtree.c:3468
static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
Definition verify_nbtree.c:624
static void bt_downlink_missing_check(BtreeCheckState *state, bool rightsplit, BlockNumber blkno, Page page)
Definition verify_nbtree.c:2557
static ItemId PageGetItemIdCareful(BtreeCheckState *state, BlockNumber block, Page page, OffsetNumber offset)
Definition verify_nbtree.c:3492
static void bt_tuple_present_callback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *checkstate)
Definition verify_nbtree.c:2780
static void bt_index_check_callback(Relation indrel, Relation heaprel, void *state, bool readonly)
Definition verify_nbtree.c:312
static bool bt_rootdescend(BtreeCheckState *state, IndexTuple itup)
Definition verify_nbtree.c:3009
static BTScanInsert bt_right_page_check_scankey(BtreeCheckState *state, OffsetNumber *rightfirstoffset)
Definition verify_nbtree.c:1865
static bool invariant_g_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber lowerbound)
Definition verify_nbtree.c:3194
static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum)
Definition verify_nbtree.c:3290
static IndexTuple bt_normalize_tuple(BtreeCheckState *state, IndexTuple itup)
Definition verify_nbtree.c:2848
static void bt_recheck_sibling_links(BtreeCheckState *state, BlockNumber btpo_prev_from_target, BlockNumber leftcurrent)
Definition verify_nbtree.c:1099
static ItemPointer BTreeTupleGetHeapTIDCareful(BtreeCheckState *state, IndexTuple itup, bool nonpivot)
Definition verify_nbtree.c:3532
static void bt_child_check(BtreeCheckState *state, BTScanInsert targetkey, OffsetNumber downlinkoffnum)
Definition verify_nbtree.c:2392
static void bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup, BlockNumber targetblock, OffsetNumber offset, BtreeLastVisibleEntry *lVis)
Definition verify_nbtree.c:911
static bool invariant_l_nontarget_offset(BtreeCheckState *state, BTScanInsert key, BlockNumber nontargetblock, Page nontarget, OffsetNumber upperbound)
Definition verify_nbtree.c:3230
◆ InvalidBtreeLevel
| #define InvalidBtreeLevel ((uint32) InvalidBlockNumber) |
Definition at line 55 of file verify_nbtree.c.
Typedef Documentation
◆ BTCallbackState
◆ BtreeCheckState
◆ BtreeLastVisibleEntry
◆ BtreeLevel
Function Documentation
◆ bt_check_every_level()
|
static |
Definition at line 378 of file verify_nbtree.c.
381{
386 BtreeLevel current;
387
388 if (!readonly)
390 RelationGetRelationName(rel));
391 else
392 elog(DEBUG1, "verifying consistency of tree structure for index \"%s\" with cross-level checks",
393 RelationGetRelationName(rel));
394
395 /*
396 * This assertion matches the one in index_getnext_tid(). See page
397 * recycling/"visible to everyone" notes in nbtree README.
398 */
400
401 /*
402 * Initialize state for entire verification operation
403 */
405 state->rel = rel;
406 state->heaprel = heaprel;
407 state->heapkeyspace = heapkeyspace;
408 state->readonly = readonly;
409 state->heapallindexed = heapallindexed;
410 state->rootdescend = rootdescend;
411 state->checkunique = checkunique;
413
415 {
418 uint64 seed;
419
420 /*
421 * Size Bloom filter based on estimated number of tuples in index,
422 * while conservatively assuming that each block must contain at least
423 * MaxTIDsPerBTreePage / 3 "plain" tuples -- see
424 * bt_posting_plain_tuple() for definition, and details of how posting
425 * list tuples are handled.
426 */
430 /* Generate a random seed to avoid repetition */
432 /* Create Bloom filter to fingerprint index */
434 state->heaptuplespresent = 0;
435
436 /*
437 * Register our own snapshot for heapallindexed, rather than asking
438 * table_index_build_scan() to do this for us later. This needs to
439 * happen before index fingerprinting begins, so we can later be
440 * certain that index fingerprinting should have reached all tuples
441 * returned by table_index_build_scan().
442 */
444
445 /*
446 * GetTransactionSnapshot() always acquires a new MVCC snapshot in
447 * READ COMMITTED mode. A new snapshot is guaranteed to have all the
448 * entries it requires in the index.
449 *
450 * We must defend against the possibility that an old xact snapshot
451 * was returned at higher isolation levels when that snapshot is not
452 * safe for index scans of the target index. This is possible when
453 * the snapshot sees tuples that are before the index's indcheckxmin
454 * horizon. Throwing an error here should be very rare. It doesn't
455 * seem worth using a secondary snapshot to avoid this.
456 */
459 state->snapshot->xmin))
463 RelationGetRelationName(rel)));
464 }
465
466 /*
467 * We need a snapshot to check the uniqueness of the index. For better
468 * performance, take it once per index check. If one was already taken
469 * above, use that.
470 */
472 {
474
477 }
478
483 errmsg("cannot verify that tuples from index \"%s\" can each be found by an independent index search",
484 RelationGetRelationName(rel)),
486
487 /* Create context for page */
489 "amcheck context",
490 ALLOCSET_DEFAULT_SIZES);
492
493 /* Get true root block from meta-page */
496
497 /*
498 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
499 * the fast root and true root differ.
500 *
501 * Start from the true root, not the fast root, unlike conventional index
502 * scans. This approach is more thorough, and removes the risk of
503 * following a stale fast root from the meta page.
504 */
509 RelationGetRelationName(rel)),
513
514 /*
515 * Starting at the root, verify every level. Move left to right, top to
516 * bottom. Note that there may be no pages other than the meta page (meta
517 * page can indicate that root is P_NONE when the index is totally empty).
518 */
524 {
525 /*
526 * Verify this level, and get left most page for next level down, if
527 * not at leaf level
528 */
530
536
538 }
539
540 /*
541 * * Check whether heap contains unindexed/malformed tuples *
542 */
544 {
546 TableScanDesc scan;
547
548 /*
549 * Create our own scan for table_index_build_scan(), rather than
550 * getting it to do so for us. This is required so that we can
551 * actually use the MVCC snapshot registered earlier.
552 *
553 * Note that table_index_build_scan() calls heap_endscan() for us.
554 */
557 0, /* number of keys */
559 true, /* buffer access strategy OK */
560 true); /* syncscan OK? */
561
562 /*
563 * Scan will behave as the first scan of a CREATE INDEX CONCURRENTLY
564 * behaves.
565 *
566 * It's okay that we don't actually use the same lock strength for the
567 * heap relation as any other ii_Concurrent caller would. We have no
568 * reason to care about a concurrent VACUUM operation, since there
569 * isn't going to be a second scan of the heap that needs to be sure
570 * that there was no concurrent recycling of TIDs.
571 */
573
574 /*
575 * Don't wait for uncommitted tuple xact commit/abort when index is a
576 * unique index on a catalog (or an index used by an exclusion
577 * constraint). This could otherwise happen in the readonly case.
578 */
583
587
590
592 (errmsg_internal("finished verifying presence of " INT64_FORMAT " tuples from table \"%s\" with bitset %.2f%% set",
595
597 }
598
599 /* Be tidy: */
603}
References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert, BAS_BULKREAD, bloom_create(), bloom_free(), bloom_prop_bits_set(), bt_check_level_from_leftmost(), bt_tuple_present_callback(), BTPageGetMeta, BTREE_METAPAGE, BuildIndexInfo(), CurrentMemoryContext, DEBUG1, elog, ereport, errcode(), ERRCODE_T_R_SERIALIZATION_FAILURE, errdetail_internal(), errhint(), errmsg(), errmsg_internal(), ERROR, fb(), GetAccessStrategy(), GetTransactionSnapshot(), HeapTupleHeaderGetXmin(), IndexInfo::ii_Concurrent, IndexInfo::ii_ExclusionOps, IndexInfo::ii_ExclusionProcs, IndexInfo::ii_ExclusionStrats, IndexInfo::ii_Unique, INT64_FORMAT, InvalidBlockNumber, InvalidBtreeLevel, InvalidSnapshot, IsolationUsesXactSnapshot, BtreeLevel::istruerootlevel, BtreeLevel::leftmost, BtreeLevel::level, maintenance_work_mem, Max, MaxTIDsPerBTreePage, MemoryContextDelete(), P_NONE, palloc0_object, palloc_btree_page(), pg_global_prng_state, pg_prng_uint64(), RelationData::rd_index, RelationData::rd_indextuple, RecentXmin, RegisterSnapshot(), RelationGetNumberOfBlocks, RelationGetRelationName, HeapTupleData::t_data, table_beginscan_strat(), table_index_build_scan(), TransactionIdIsValid, TransactionIdPrecedes(), and UnregisterSnapshot().
Referenced by bt_index_check_callback().
◆ bt_check_level_from_leftmost()
|
static |
Definition at line 624 of file verify_nbtree.c.
625{
626 /* State to establish early, concerning entire level */
627 BTPageOpaque opaque;
628 MemoryContext oldcontext;
630
631 /* Variables for iterating across level using right links */
634
635 /* Initialize return state */
639
640 /* Use page-level context for duration of this call */
642
644 level.istruerootlevel ?
645 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
646
649
650 do
651 {
652 /* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
653 CHECK_FOR_INTERRUPTS();
654
655 /* Initialize state for this iteration */
656 state->targetblock = current;
659
661
663 {
664 /*
665 * Since there cannot be a concurrent VACUUM operation in readonly
666 * mode, and since a page has no links within other pages
667 * (siblings and parent) once it is marked fully deleted, it
668 * should be impossible to land on a fully deleted page in
669 * readonly mode. See bt_child_check() for further details.
670 *
671 * The bt_child_check() P_ISDELETED() check is repeated here so
672 * that pages that are only reachable through sibling links get
673 * checked.
674 */
682
688 else
694 }
696 {
697 /*
698 * A concurrent page split could make the caller supplied leftmost
699 * block no longer contain the leftmost page, or no longer be the
700 * true root, but where that isn't possible due to heavyweight
701 * locking, check that the first valid page meets caller's
702 * expectations.
703 */
705 {
711
717 }
718
719 /*
720 * Before beginning any non-trivial examination of level, prepare
721 * state for next bt_check_level_from_leftmost() invocation for
722 * the next level for the next level down (if any).
723 *
724 * There should be at least one non-ignorable page per level,
725 * unless this is the leaf level, which is assumed by caller to be
726 * final level.
727 */
729 {
730 IndexTuple itup;
731 ItemId itemid;
732
733 /* Internal page -- downlink gets leftmost on next level */
735 state->target,
736 P_FIRSTDATAKEY(opaque));
740 }
741 else
742 {
743 /*
744 * Leaf page -- final level caller must process.
745 *
746 * Note that this could also be the root page, if there has
747 * been no root page split yet.
748 */
751 }
752
753 /*
754 * Finished setting up state for this call/level. Control will
755 * never end up back here in any future loop iteration for this
756 * level.
757 */
758 }
759
760 /*
761 * Sibling links should be in mutual agreement. There arises
762 * leftcurrent == P_NONE && btpo_prev != P_NONE when the left sibling
763 * of the parent's low-key downlink is half-dead. (A half-dead page
764 * has no downlink from its parent.) Under heavyweight locking, the
765 * last bt_leftmost_ignoring_half_dead() validated this btpo_prev.
766 * Without heavyweight locking, validation of the P_NONE case remains
767 * unimplemented.
768 */
771
772 /* Check level */
776 errmsg("leftmost down link for level points to block in index \"%s\" whose level is not one level down",
780
781 /* Verify invariants for page */
783
784nextpage:
785
786 /* Try to detect circular links */
792
793 leftcurrent = current;
794 current = opaque->btpo_next;
795
797 {
801 }
802
803 /*
804 * Copy current target high key as the low key of right sibling.
805 * Allocate memory in upper level context, so it would be cleared
806 * after reset of target context.
807 *
808 * We only need the low key in corner cases of checking child high
809 * keys. We use high key only when incomplete split on the child level
810 * falls to the boundary of pages on the target level. See
811 * bt_child_highkey_check() for details. So, typically we won't end
812 * up doing anything with low key, but it's simpler for general case
813 * high key verification to always have it available.
814 *
815 * The correctness of managing low key in the case of concurrent
816 * splits wasn't investigated yet. Thankfully we only need low key
817 * for readonly verification and concurrent splits won't happen.
818 */
820 {
821 IndexTuple itup;
822 ItemId itemid;
823
827
830 }
831
832 /* Free page and associated memory for this iteration */
834 }
836
838 {
842 }
843
844 /* Don't change context for caller */
845 MemoryContextSwitchTo(oldcontext);
846
848}
References Assert, bt_leftmost_ignoring_half_dead(), bt_recheck_sibling_links(), bt_target_page_check(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BTreeTupleGetDownLink(), CHECK_FOR_INTERRUPTS, DEBUG1, elog, ereport, errcode(), errdetail_internal(), errmsg(), errmsg_internal(), ERROR, fb(), IndexTupleSize(), InvalidBlockNumber, InvalidBtreeLevel, BtreeLevel::istruerootlevel, BtreeLevel::leftmost, BtreeLevel::level, MemoryContextAlloc(), MemoryContextReset(), MemoryContextSwitchTo(), P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_ISDELETED, P_ISLEAF, P_ISROOT, P_NONE, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetLSN(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_check_every_level().
◆ bt_child_check()
|
static |
Definition at line 2392 of file verify_nbtree.c.
2394{
2395 ItemId itemid;
2396 IndexTuple itup;
2398 OffsetNumber offset;
2400 Page child;
2403
2405 state->target, downlinkoffnum);
2408
2409 /*
2410 * Caller must have ShareLock on target relation, because of
2411 * considerations around page deletion by VACUUM.
2412 *
2413 * NB: In general, page deletion deletes the right sibling's downlink, not
2414 * the downlink of the page being deleted; the deleted page's downlink is
2415 * reused for its sibling. The key space is thereby consolidated between
2416 * the deleted page and its right sibling. (We cannot delete a parent
2417 * page's rightmost child unless it is the last child page, and we intend
2418 * to also delete the parent itself.)
2419 *
2420 * If this verification happened without a ShareLock, the following race
2421 * condition could cause false positives:
2422 *
2423 * In general, concurrent page deletion might occur, including deletion of
2424 * the left sibling of the child page that is examined here. If such a
2425 * page deletion were to occur, closely followed by an insertion into the
2426 * newly expanded key space of the child, a window for the false positive
2427 * opens up: the stale parent/target downlink originally followed to get
2428 * to the child legitimately ceases to be a lower bound on all items in
2429 * the page, since the key space was concurrently expanded "left".
2430 * (Insertion followed the "new" downlink for the child, not our now-stale
2431 * downlink, which was concurrently physically removed in target/parent as
2432 * part of deletion's first phase.)
2433 *
2434 * While we use various techniques elsewhere to perform cross-page
2435 * verification for !readonly callers, a similar trick seems difficult
2436 * here. The tricks used by bt_recheck_sibling_links and by
2437 * bt_right_page_check_scankey both involve verification of a same-level,
2438 * cross-sibling invariant. Cross-level invariants are far more squishy,
2439 * though. The nbtree REDO routines do not actually couple buffer locks
2440 * across levels during page splits, so making any cross-level check work
2441 * reliably in !readonly mode may be impossible.
2442 */
2444
2445 /*
2446 * Verify child page has the downlink key from target page (its parent) as
2447 * a lower bound; downlink must be strictly less than all keys on the
2448 * page.
2449 *
2450 * Check all items, rather than checking just the first and trusting that
2451 * the operator class obeys the transitive law.
2452 */
2457
2458 /*
2459 * Since we've already loaded the child block, combine this check with
2460 * check for downlink connectivity.
2461 */
2463 child, topaque->btpo_level);
2464
2465 /*
2466 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2467 * and since a page has no links within other pages (siblings and parent)
2468 * once it is marked fully deleted, it should be impossible to land on a
2469 * fully deleted page.
2470 *
2471 * It does not quite make sense to enforce that the page cannot even be
2472 * half-dead, despite the fact the downlink is modified at the same stage
2473 * that the child leaf page is marked half-dead. That's incorrect because
2474 * there may occasionally be multiple downlinks from a chain of pages
2475 * undergoing deletion, where multiple successive calls are made to
2476 * _bt_unlink_halfdead_page() by VACUUM before it can finally safely mark
2477 * the leaf page as fully dead. While _bt_mark_page_halfdead() usually
2478 * removes the downlink to the leaf page that is marked half-dead, that's
2479 * not guaranteed, so it's possible we'll land on a half-dead page with a
2480 * downlink due to an interrupted multi-level page deletion.
2481 *
2482 * We go ahead with our checks if the child page is half-dead. It's safe
2483 * to do so because we do not test the child's high key, so it does not
2484 * matter that the original high key will have been replaced by a dummy
2485 * truncated high key within _bt_mark_page_halfdead(). All other page
2486 * items are left intact on a half-dead page, so there is still something
2487 * to test.
2488 */
2497
2499 offset <= maxoffset;
2500 offset = OffsetNumberNext(offset))
2501 {
2502 /*
2503 * Skip comparison of target page key against "negative infinity"
2504 * item, if any. Checking it would indicate that it's not a strict
2505 * lower bound, but that's only because of the hard-coding for
2506 * negative infinity items within _bt_compare().
2507 *
2508 * If nbtree didn't truncate negative infinity tuples during internal
2509 * page splits then we'd expect child's negative infinity key to be
2510 * equal to the scankey/downlink from target/parent (it would be a
2511 * "low key" in this hypothetical scenario, and so it would still need
2512 * to be treated as a special case here).
2513 *
2514 * Negative infinity items can be thought of as a strict lower bound
2515 * that works transitively, with the last non-negative-infinity pivot
2516 * followed during a descent from the root as its "true" strict lower
2517 * bound. Only a small number of negative infinity items are truly
2518 * negative infinity; those that are the first items of leftmost
2519 * internal pages. In more general terms, a negative infinity item is
2520 * only negative infinity with respect to the subtree that the page is
2521 * at the root of.
2522 *
2523 * See also: bt_rootdescend(), which can even detect transitive
2524 * inconsistencies on cousin leaf pages.
2525 */
2527 continue;
2528
2530 offset))
2538 }
2539
2540 pfree(child);
2541}
References Assert, bt_child_highkey_check(), BTPageGetOpaque, BTreeTupleGetDownLink(), ereport, errcode(), errdetail_internal(), errmsg(), ERROR, fb(), invariant_l_nontarget_offset(), LSN_FORMAT_ARGS, offset_is_negative_infinity(), OffsetNumberNext, P_FIRSTDATAKEY, P_ISDELETED, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_target_page_check().
◆ bt_child_highkey_check()
|
static |
Definition at line 2145 of file verify_nbtree.c.
2149{
2151 Page page;
2152 BTPageOpaque opaque;
2154 bool first = true;
2155 ItemId itemid;
2156 IndexTuple itup;
2157 BlockNumber downlink;
2158
2160 {
2164 downlink = BTreeTupleGetDownLink(itup);
2165 }
2166 else
2167 {
2168 downlink = P_NONE;
2169 }
2170
2171 /*
2172 * If no previous rightlink is memorized for current level just below
2173 * target page's level, we are about to start from the leftmost page. We
2174 * can't follow rightlinks from previous page, because there is no
2175 * previous page. But we still can match high key.
2176 *
2177 * So we initialize variables for the loop above like there is previous
2178 * page referencing current child. Also we imply previous page to not
2179 * have incomplete split flag, that would make us require downlink for
2180 * current child. That's correct, because leftmost page on the level
2181 * should always have parent downlink.
2182 */
2184 {
2185 blkno = downlink;
2187 }
2188
2189 /* Move to the right on the child level */
2190 while (true)
2191 {
2192 /*
2193 * Did we traverse the whole tree level and this is check for pages to
2194 * the right of rightmost downlink?
2195 */
2197 {
2200 return;
2201 }
2202
2203 /* Did we traverse the whole tree level and don't find next downlink? */
2208 state->prevrightlink, downlink,
2210
2211 /* Load page contents */
2213 page = loaded_child;
2214 else
2216
2217 opaque = BTPageGetOpaque(page);
2218
2219 /* The first page we visit at the level should be leftmost */
2227 state->targetblock, blkno,
2229
2230 /* Do level sanity check */
2239
2240 /* Try to detect circular links */
2246
2248 {
2249 /* blkno probably has missing parent downlink */
2251 }
2252
2254
2255 /*
2256 * If we visit page with high key, check that it is equal to the
2257 * target key next to corresponding downlink.
2258 */
2260 {
2264
2265 /* Get high key */
2268
2269 /*
2270 * There might be two situations when we examine high key. If
2271 * current child page is referenced by given target downlink, we
2272 * should look to the next offset number for matching key from
2273 * target page.
2274 *
2275 * Alternatively, we're following rightlinks somewhere in the
2276 * middle between page referenced by previous target's downlink
2277 * and the page referenced by current target's downlink. If
2278 * current child page hasn't incomplete split flag set, then its
2279 * high key should match to the target's key of current offset
2280 * number. This happens when a previous call here (to
2281 * bt_child_highkey_check()) found an incomplete split, and we
2282 * reach a right sibling page without a downlink -- the right
2283 * sibling page's high key still needs to be matched to a
2284 * separator key on the parent/target level.
2285 *
2286 * Don't apply OffsetNumberNext() to target_downlinkoffnum when we
2287 * already had to step right on the child level. Our traversal of
2288 * the child level must try to move in perfect lockstep behind (to
2289 * the left of) the target/parent level traversal.
2290 */
2291 if (blkno == downlink)
2293 else
2295
2297
2299 {
2300 /*
2301 * If we're looking for the next pivot tuple in target page,
2302 * but there is no more pivot tuples, then we should match to
2303 * high key instead.
2304 */
2306 {
2313 state->targetblock, blkno,
2316 }
2320 }
2321 else
2322 {
2323 /*
2324 * We cannot try to match child's high key to a negative
2325 * infinity key in target, since there is nothing to compare.
2326 * However, it's still possible to match child's high key
2327 * outside of target page. The reason why we're are is that
2328 * bt_child_highkey_check() was previously called for the
2329 * cousin page of 'loaded_child', which is incomplete split.
2330 * So, now we traverse to the right of that cousin page and
2331 * current child level page under consideration still belongs
2332 * to the subtree of target's left sibling. Thus, we need to
2333 * match child's high key to its left uncle page high key.
2334 * Thankfully we saved it, it's called a "low key" of target
2335 * page.
2336 */
2343 state->targetblock, blkno,
2345 itup = state->lowkey;
2346 }
2347
2349 {
2355 state->targetblock, blkno,
2357 }
2358 }
2359
2360 /* Exit if we already found next downlink */
2361 if (blkno == downlink)
2362 {
2365 return;
2366 }
2367
2368 /* Traverse to the next page using rightlink */
2369 blkno = opaque->btpo_next;
2370
2371 /* Free page contents if it's allocated by us */
2373 pfree(page);
2374 first = false;
2375 }
2376}
References BlockNumberIsValid(), bt_downlink_missing_check(), bt_leftmost_ignoring_half_dead(), bt_pivot_tuple_identical(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BTreeTupleGetDownLink(), ereport, errcode(), errdetail_internal(), errmsg(), ERROR, fb(), InvalidBlockNumber, LSN_FORMAT_ARGS, offset_is_negative_infinity(), OffsetNumberIsValid, OffsetNumberNext, P_HAS_FULLXID, P_HIKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_ISDELETED, P_ISHALFDEAD, P_NONE, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_child_check(), and bt_target_page_check().
◆ bt_downlink_missing_check()
|
static |
Definition at line 2557 of file verify_nbtree.c.
2559{
2561 ItemId itemid;
2562 IndexTuple itup;
2563 Page child;
2565 uint32 level;
2568
2571
2572 /* No next level up with downlinks to fingerprint from the true root */
2574 return;
2575
2577
2578 /*
2579 * Incomplete (interrupted) page splits can account for the lack of a
2580 * downlink. Some inserting transaction should eventually complete the
2581 * page split in passing, when it notices that the left sibling page is
2582 * P_INCOMPLETE_SPLIT().
2583 *
2584 * In general, VACUUM is not prepared for there to be no downlink to a
2585 * page that it deletes. This is the main reason why the lack of a
2586 * downlink can be reported as corruption here. It's not obvious that an
2587 * invalid missing downlink can result in wrong answers to queries,
2588 * though, since index scans that land on the child may end up
2589 * consistently moving right. The handling of concurrent page splits (and
2590 * page deletions) within _bt_moveright() cannot distinguish
2591 * inconsistencies that last for a moment from inconsistencies that are
2592 * permanent and irrecoverable.
2593 *
2594 * VACUUM isn't even prepared to delete pages that have no downlink due to
2595 * an incomplete page split, but it can detect and reason about that case
2596 * by design, so it shouldn't be taken to indicate corruption. See
2597 * _bt_pagedel() for full details.
2598 */
2600 {
2606 blkno, opaque->btpo_level,
2607 opaque->btpo_prev,
2609 return;
2610 }
2611
2612 /*
2613 * Page under check is probably the "top parent" of a multi-level page
2614 * deletion. We'll need to descend the subtree to make sure that
2615 * descendant pages are consistent with that, though.
2616 *
2617 * If the page (which must be non-ignorable) is a leaf page, then clearly
2618 * it can't be the top parent. The lack of a downlink is probably a
2619 * symptom of a broad problem that could just as easily cause
2620 * inconsistencies anywhere else.
2621 */
2628 blkno,
2630
2631 /* Descend from the given page, which is an internal page */
2632 elog(DEBUG1, "checking for interrupted multi-level deletion due to missing downlink in index \"%s\"",
2634
2635 level = opaque->btpo_level;
2639 for (;;)
2640 {
2641 CHECK_FOR_INTERRUPTS();
2642
2645
2647 break;
2648
2649 /* Do an extra sanity check in passing on internal pages */
2655 errdetail_internal("Top parent/under check block=%u block pointed to=%u expected level=%u level in pointed to block=%u.",
2656 blkno, childblk,
2657 level - 1, copaque->btpo_level)));
2658
2659 level = copaque->btpo_level;
2664 /* Be slightly more pro-active in freeing this memory, just in case */
2665 pfree(child);
2666 }
2667
2668 /*
2669 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2670 * and since a page has no links within other pages (siblings and parent)
2671 * once it is marked fully deleted, it should be impossible to land on a
2672 * fully deleted page. See bt_child_check() for further details.
2673 *
2674 * The bt_child_check() P_ISDELETED() check is repeated here because
2675 * bt_child_check() does not visit pages reachable through negative
2676 * infinity items. Besides, bt_child_check() is unwilling to descend
2677 * multiple levels. (The similar bt_child_check() P_ISDELETED() check
2678 * within bt_check_level_from_leftmost() won't reach the page either,
2679 * since the leaf's live siblings should have their sibling links updated
2680 * to bypass the deletion target page when it is marked fully dead.)
2681 *
2682 * If this error is raised, it might be due to a previous multi-level page
2683 * deletion that failed to realize that it wasn't yet safe to mark the
2684 * leaf page as fully dead. A "dangling downlink" will still remain when
2685 * this happens. The fact that the dangling downlink's page (the leaf's
2686 * parent/ancestor page) lacked a downlink is incidental.
2687 */
2693 errdetail_internal("Top parent/target block=%u leaf block=%u top parent/under check lsn=%X/%08X.",
2694 blkno, childblk,
2696
2697 /*
2698 * Iff leaf page is half-dead, its high key top parent link should point
2699 * to what VACUUM considered to be the top parent page at the instant it
2700 * was interrupted. Provided the high key link actually points to the
2701 * page under check, the missing downlink we detected is consistent with
2702 * there having been an interrupted multi-level page deletion. This means
2703 * that the subtree with the page under check at its root (a page deletion
2704 * chain) is in a consistent state, enabling VACUUM to resume deleting the
2705 * entire chain the next time it encounters the half-dead leaf page.
2706 */
2708 {
2712 return;
2713 }
2714
2720 blkno, opaque->btpo_level,
2722}
References Assert, BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_prev, BTreeTupleGetDownLink(), BTreeTupleGetTopParent(), CHECK_FOR_INTERRUPTS, DEBUG1, elog, ereport, errcode(), errdetail_internal(), errmsg(), errmsg_internal(), ERROR, fb(), LSN_FORMAT_ARGS, P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_ISDELETED, P_ISHALFDEAD, P_ISLEAF, P_ISROOT, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetLSN(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_child_highkey_check().
◆ bt_entry_unique_check()
|
static |
Definition at line 911 of file verify_nbtree.c.
914{
915 ItemPointer tid;
917
919
920 /*
921 * Current tuple has posting list. Report duplicate if TID of any posting
922 * list entry is visible and lVis->tid is valid.
923 */
925 {
927 {
930 {
933 {
935 lVis,
936 tid, targetblock,
937 offset, i);
938 }
939
940 /*
941 * Prevent double reporting unique constraint violation
942 * between the posting list entries of the first tuple on the
943 * page after cross-page check.
944 */
946 return;
947
948 lVis->blkno = targetblock;
949 lVis->offset = offset;
951 lVis->tid = tid;
952 }
953 }
954 }
955
956 /*
957 * Current tuple has no posting list. If TID is visible save info about it
958 * for the next comparisons in the loop in bt_target_page_check(). Report
959 * duplicate if lVis->tid is already valid.
960 */
961 else
962 {
963 tid = BTreeTupleGetHeapTID(itup);
965 {
968 {
970 lVis,
971 tid, targetblock,
972 offset, -1);
973 }
974
975 lVis->blkno = targetblock;
976 lVis->offset = offset;
977 lVis->tid = tid;
978 lVis->postingIndex = -1;
979 }
980 }
981
984 lVis->blkno != targetblock)
985 {
987
993 targetblock, offset,
995 errdetail("It doesn't have visible heap tids and key is equal to the tid=(%u,%u)%s (points to heap tid=(%u,%u)).",
1000 }
1001}
References Assert, bt_report_duplicate(), BTreeTupleGetHeapTID(), BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), DEBUG1, ereport, errcode(), errdetail(), errhint(), errmsg(), fb(), heap_entry_is_visible(), i, InvalidBlockNumber, ItemPointerGetBlockNumberNoCheck(), ItemPointerGetOffsetNumberNoCheck(), ItemPointerIsValid(), P_NONE, psprintf(), and RelationGetRelationName.
Referenced by bt_target_page_check().
◆ bt_index_check()
| Datum bt_index_check | ( | PG_FUNCTION_ARGS | ) |
Definition at line 252 of file verify_nbtree.c.
References AccessShareLock, amcheck_lock_relation_and_check(), bt_index_check_callback(), fb(), PG_GETARG_BOOL, PG_GETARG_OID, PG_NARGS, and PG_RETURN_VOID.
◆ bt_index_check_callback()
|
static |
Definition at line 312 of file verify_nbtree.c.
313{
315 bool heapkeyspace,
316 allequalimage;
317
323
324 /* Extract metadata from metapage, and sanitize it in passing */
326 if (allequalimage && !heapkeyspace)
332 {
334
337 {
343 has_interval_ops
345 : 0));
346 }
347 }
348
349 /* Check index, possibly against table it is an index on */
352}
References _bt_allequalimage(), _bt_metaversion(), bt_check_every_level(), ereport, errcode(), errhint(), errmsg(), ERROR, fb(), i, IndexRelationGetNumberOfKeyAttributes, MAIN_FORKNUM, RelationGetRelationName, RelationGetSmgr(), and smgrexists().
Referenced by bt_index_check(), and bt_index_parent_check().
◆ bt_index_parent_check()
| Datum bt_index_parent_check | ( | PG_FUNCTION_ARGS | ) |
Definition at line 284 of file verify_nbtree.c.
References amcheck_lock_relation_and_check(), bt_index_check_callback(), fb(), PG_GETARG_BOOL, PG_GETARG_OID, PG_NARGS, PG_RETURN_VOID, and ShareLock.
◆ bt_leftmost_ignoring_half_dead()
|
static |
Definition at line 1010 of file verify_nbtree.c.
1013{
1017
1018 /*
1019 * To handle the !readonly case, we'd need to accept BTP_DELETED pages and
1020 * potentially observe nbtree/README "Page deletion and backwards scans".
1021 */
1023
1025 {
1028
1029 CHECK_FOR_INTERRUPTS();
1030
1031 /*
1032 * Try to detect btpo_prev circular links. _bt_unlink_halfdead_page()
1033 * writes that side-links will continue to point to the siblings.
1034 * Check btpo_next for that property.
1035 */
1041 {
1043
1044 /* pagelsn should point to an XLOG_BTREE_MARK_PAGE_HALFDEAD */
1052
1055 }
1056
1057 pfree(page);
1058 }
1059
1061}
References Assert, BTPageGetOpaque, CHECK_FOR_INTERRUPTS, DEBUG1, ereport, errcode(), errdetail_internal(), errmsg_internal(), fb(), LSN_FORMAT_ARGS, P_ISHALFDEAD, P_NONE, PageGetLSN(), palloc_btree_page(), pfree(), RelationGetRelationName, and start.
Referenced by bt_check_level_from_leftmost(), and bt_child_highkey_check().
◆ bt_mkscankey_pivotsearch()
|
inlinestatic |
Definition at line 3468 of file verify_nbtree.c.
3469{
3471
3474
3476}
References _bt_mkscankey(), and fb().
Referenced by bt_right_page_check_scankey(), and bt_target_page_check().
◆ bt_normalize_tuple()
|
static |
Definition at line 2848 of file verify_nbtree.c.
2849{
2857
2858 /* Caller should only pass "logical" non-pivot tuples here */
2860
2861 /* Easy case: It's immediately clear that tuple has no varlena datums */
2863 return itup;
2864
2866 {
2868
2870
2871 /* Assume untoasted/already normalized datum initially */
2874 tupleDescriptor,
2875 &isnull[i]);
2877 continue;
2878
2879 /*
2880 * Callers always pass a tuple that could safely be inserted into the
2881 * index without further processing, so an external varlena header
2882 * should never be encountered here
2883 */
2895 {
2896 /*
2897 * This value will be compressed by index_form_tuple() with the
2898 * current storage settings. We may be here because this tuple
2899 * was formed with different storage settings. So, force forming.
2900 */
2902 }
2904 {
2908 }
2909
2910 /*
2911 * Short tuples may have 1B or 4B header. Convert 4B header of short
2912 * tuples to 1B
2913 */
2915 {
2916 /* convert to short varlena */
2919
2922
2926 }
2927 }
2928
2929 /*
2930 * Easier case: Tuple has varlena datums, none of which are compressed or
2931 * short with 4B header
2932 */
2934 return itup;
2935
2936 /*
2937 * Hard case: Tuple had compressed varlena datums that necessitate
2938 * creating normalized version of the tuple from uncompressed input datums
2939 * (normalized input datums). This is rather naive, but shouldn't be
2940 * necessary too often.
2941 *
2942 * In the heap, tuples may contain short varlena datums with both 1B
2943 * header and 4B headers. But the corresponding index tuple should always
2944 * have such varlena's with 1B headers. So, if there is a short varlena
2945 * with 4B header, we need to convert it for fingerprinting.
2946 *
2947 * Note that we rely on deterministic index_form_tuple() TOAST compression
2948 * of normalized input.
2949 */
2952
2953 /* Cannot leak memory here */
2957
2959}
References Assert, BTreeTupleIsPivot(), BTreeTupleIsPosting(), data, DatumGetPointer(), ereport, errcode(), errmsg(), ERROR, fb(), i, index_form_tuple(), index_getattr(), INDEX_MAX_KEYS, IndexTupleHasVarwidths(), ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), len, palloc(), pfree(), PG_DETOAST_DATUM, PointerGetDatum(), RelationGetDescr, RelationGetRelationName, SET_VARSIZE_SHORT(), IndexTupleData::t_tid, TOAST_INDEX_TARGET, TupleDescAttr(), VARATT_CAN_MAKE_SHORT(), VARATT_CONVERTED_SHORT_SIZE(), VARATT_IS_COMPRESSED(), VARATT_IS_EXTERNAL(), VARDATA(), and VARSIZE().
Referenced by bt_target_page_check(), and bt_tuple_present_callback().
◆ bt_pivot_tuple_identical()
|
static |
Definition at line 2072 of file verify_nbtree.c.
2073{
2075 return false;
2076
2077 if (heapkeyspace)
2078 {
2079 /*
2080 * Offset number will contain important information in heapkeyspace
2081 * indexes: the number of attributes left in the pivot tuple following
2082 * suffix truncation. Don't skip over it (compare it too).
2083 */
2087 return false;
2088 }
2089 else
2090 {
2091 /*
2092 * Cannot rely on offset number field having consistent value across
2093 * levels on pg_upgrade'd !heapkeyspace indexes. Compare contents of
2094 * tuple starting from just after item pointer (i.e. after block
2095 * number and offset number).
2096 */
2100 return false;
2101 }
2102
2103 return true;
2104}
References fb(), and IndexTupleSize().
Referenced by bt_child_highkey_check().
◆ bt_posting_plain_tuple()
|
inlinestatic |
Definition at line 2976 of file verify_nbtree.c.
2977{
2979
2980 /* Returns non-posting-list tuple */
2982}
References _bt_form_posting(), Assert, BTreeTupleGetPostingN(), and BTreeTupleIsPosting().
Referenced by bt_target_page_check().
◆ bt_recheck_sibling_links()
|
static |
Definition at line 1099 of file verify_nbtree.c.
1102{
1103 /* passing metapage to BTPageGetOpaque() would give irrelevant findings */
1105
1107 {
1110 Page page;
1111 BTPageOpaque opaque;
1113
1114 /* Couple locks in the usual order for nbtree: Left to right */
1120 opaque = BTPageGetOpaque(page);
1122 {
1123 /*
1124 * Cannot reason about concurrently deleted page -- the left link
1125 * in the page to the right is expected to point to some other
1126 * page to the left (not leftcurrent page).
1127 *
1128 * Note that we deliberately don't give up with a half-dead page.
1129 */
1131 return;
1132 }
1133
1135 /* Avoid self-deadlock when newtargetblock == leftcurrent */
1137 {
1140 state->checkstrategy);
1144 opaque = BTPageGetOpaque(page);
1145 /* btpo_prev_from_target may have changed; update it */
1147 }
1148 else
1149 {
1150 /*
1151 * leftcurrent right sibling points back to leftcurrent block.
1152 * Index is corrupt. Easiest way to handle this is to pretend
1153 * that we actually read from a distinct page that has an invalid
1154 * block number in its btpo_prev.
1155 */
1158 }
1159
1160 /*
1161 * No need to check P_ISDELETED here, since new target block cannot be
1162 * marked deleted as long as we hold a lock on lbuf
1163 */
1167
1169 {
1170 /* Report split in left sibling, not target (or new target) */
1177 state->targetblock)));
1178 return;
1179 }
1180
1181 /*
1182 * Index is corrupt. Make sure that we report correct target page.
1183 *
1184 * This could have changed in cases where there was a concurrent page
1185 * split, as well as index corruption (at least in theory). Note that
1186 * btpo_prev_from_target was already updated above.
1187 */
1189 }
1190
1197 btpo_prev_from_target)));
1198}
References _bt_checkpage(), Assert, BT_READ, BTPageGetOpaque, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BufferGetPage(), BufferIsValid(), DEBUG1, ereport, errcode(), errdetail_internal(), errmsg(), errmsg_internal(), ERROR, fb(), InvalidBlockNumber, InvalidBuffer, LockBuffer(), MAIN_FORKNUM, P_ISDELETED, P_NONE, RBM_NORMAL, ReadBufferExtended(), RelationGetRelationName, and UnlockReleaseBuffer().
Referenced by bt_check_level_from_leftmost().
◆ bt_report_duplicate()
|
static |
Definition at line 871 of file verify_nbtree.c.
References ereport, errcode(), errdetail(), errmsg(), ERROR, fb(), ItemPointerGetBlockNumberNoCheck(), ItemPointerGetOffsetNumberNoCheck(), LSN_FORMAT_ARGS, psprintf(), and RelationGetRelationName.
Referenced by bt_entry_unique_check().
◆ bt_right_page_check_scankey()
|
static |
Definition at line 1865 of file verify_nbtree.c.
1866{
1867 BTPageOpaque opaque;
1873
1874 /* Determine target's next block number */
1876
1877 /* If target is already rightmost, no right sibling; nothing to do here */
1880
1881 /*
1882 * General notes on concurrent page splits and page deletion:
1883 *
1884 * Routines like _bt_search() don't require *any* page split interlock
1885 * when descending the tree, including something very light like a buffer
1886 * pin. That's why it's okay that we don't either. This avoidance of any
1887 * need to "couple" buffer locks is the raison d' etre of the Lehman & Yao
1888 * algorithm, in fact.
1889 *
1890 * That leaves deletion. A deleted page won't actually be recycled by
1891 * VACUUM early enough for us to fail to at least follow its right link
1892 * (or left link, or downlink) and find its sibling, because recycling
1893 * does not occur until no possible index scan could land on the page.
1894 * Index scans can follow links with nothing more than their snapshot as
1895 * an interlock and be sure of at least that much. (See page
1896 * recycling/"visible to everyone" notes in nbtree README.)
1897 *
1898 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
1899 * dead (ignorable) page one or more times. There will either be a
1900 * further right link to follow that leads to a live page before too long
1901 * (before passing by parent's rightmost child), or we will find the end
1902 * of the entire level instead (possible when parent page is itself the
1903 * rightmost on its level).
1904 */
1906 for (;;)
1907 {
1908 CHECK_FOR_INTERRUPTS();
1909
1912
1914 break;
1915
1916 /*
1917 * We landed on a deleted or half-dead sibling page. Step right until
1918 * we locate a live sibling page.
1919 */
1922 errmsg_internal("level %u sibling page in block %u of index \"%s\" was found deleted or half dead",
1925
1927
1928 /* Be slightly more pro-active in freeing this memory, just in case */
1930 }
1931
1932 /*
1933 * No ShareLock held case -- why it's safe to proceed.
1934 *
1935 * Problem:
1936 *
1937 * We must avoid false positive reports of corruption when caller treats
1938 * item returned here as an upper bound on target's last item. In
1939 * general, false positives are disallowed. Avoiding them here when
1940 * caller is !readonly is subtle.
1941 *
1942 * A concurrent page deletion by VACUUM of the target page can result in
1943 * the insertion of items on to this right sibling page that would
1944 * previously have been inserted on our target page. There might have
1945 * been insertions that followed the target's downlink after it was made
1946 * to point to right sibling instead of target by page deletion's first
1947 * phase. The inserters insert items that would belong on target page.
1948 * This race is very tight, but it's possible. This is our only problem.
1949 *
1950 * Non-problems:
1951 *
1952 * We are not hindered by a concurrent page split of the target; we'll
1953 * never land on the second half of the page anyway. A concurrent split
1954 * of the right page will also not matter, because the first data item
1955 * remains the same within the left half, which we'll reliably land on. If
1956 * we had to skip over ignorable/deleted pages, it cannot matter because
1957 * their key space has already been atomically merged with the first
1958 * non-ignorable page we eventually find (doesn't matter whether the page
1959 * we eventually find is a true sibling or a cousin of target, which we go
1960 * into below).
1961 *
1962 * Solution:
1963 *
1964 * Caller knows that it should reverify that target is not ignorable
1965 * (half-dead or deleted) when cross-page sibling item comparison appears
1966 * to indicate corruption (invariant fails). This detects the single race
1967 * condition that exists for caller. This is correct because the
1968 * continued existence of target block as non-ignorable (not half-dead or
1969 * deleted) implies that target page was not merged into from the right by
1970 * deletion; the key space at or after target never moved left. Target's
1971 * parent either has the same downlink to target as before, or a <
1972 * downlink due to deletion at the left of target. Target either has the
1973 * same highkey as before, or a highkey < before when there is a page
1974 * split. (The rightmost concurrently-split-from-target-page page will
1975 * still have the same highkey as target was originally found to have,
1976 * which for our purposes is equivalent to target's highkey itself never
1977 * changing, since we reliably skip over
1978 * concurrently-split-from-target-page pages.)
1979 *
1980 * In simpler terms, we allow that the key space of the target may expand
1981 * left (the key space can move left on the left side of target only), but
1982 * the target key space cannot expand right and get ahead of us without
1983 * our detecting it. The key space of the target cannot shrink, unless it
1984 * shrinks to zero due to the deletion of the original page, our canary
1985 * condition. (To be very precise, we're a bit stricter than that because
1986 * it might just have been that the target page split and only the
1987 * original target page was deleted. We can be more strict, just not more
1988 * lax.)
1989 *
1990 * Top level tree walk caller moves on to next page (makes it the new
1991 * target) following recovery from this race. (cf. The rationale for
1992 * child/downlink verification needing a ShareLock within
1993 * bt_child_check(), where page deletion is also the main source of
1994 * trouble.)
1995 *
1996 * Note that it doesn't matter if right sibling page here is actually a
1997 * cousin page, because in order for the key space to be readjusted in a
1998 * way that causes us issues in next level up (guiding problematic
1999 * concurrent insertions to the cousin from the grandparent rather than to
2000 * the sibling from the parent), there'd have to be page deletion of
2001 * target's parent page (affecting target's parent's downlink in target's
2002 * grandparent page). Internal page deletion only occurs when there are
2003 * no child pages (they were all fully deleted), and caller is checking
2004 * that the target's parent has at least one non-deleted (so
2005 * non-ignorable) child: the target page. (Note that the first phase of
2006 * deletion atomically marks the page to be deleted half-dead/ignorable at
2007 * the same time downlink in its parent is removed, so caller will
2008 * definitely not fail to detect that this happened.)
2009 *
2010 * This trick is inspired by the method backward scans use for dealing
2011 * with concurrent page splits; concurrent page deletion is a problem that
2012 * similarly receives special consideration sometimes (it's possible that
2013 * the backwards scan will re-read its "original" block after failing to
2014 * find a right-link to it, having already moved in the opposite direction
2015 * (right/"forwards") a few times to try to locate one). Just like us,
2016 * that happens only to determine if there was a concurrent page deletion
2017 * of a reference page, and just like us if there was a page deletion of
2018 * that reference page it means we can move on from caring about the
2019 * reference page. See the nbtree README for a full description of how
2020 * that works.
2021 */
2023
2024 /*
2025 * Get first data item, if any
2026 */
2028 {
2029 /* Return first data item (if any) */
2031 P_FIRSTDATAKEY(opaque));
2033 }
2036 {
2037 /*
2038 * Return first item after the internal page's "negative infinity"
2039 * item
2040 */
2043 }
2044 else
2045 {
2046 /*
2047 * No first item. Page is probably empty leaf page, but it's also
2048 * possible that it's an internal page with only a negative infinity
2049 * item.
2050 */
2057 }
2058
2059 /*
2060 * Return first real item scankey. Note that this relies on right page
2061 * memory remaining allocated.
2062 */
2065}
References bt_mkscankey_pivotsearch(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, CHECK_FOR_INTERRUPTS, DEBUG2, ereport, errcode(), errdetail_internal(), errmsg_internal(), fb(), OffsetNumberNext, P_FIRSTDATAKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_target_page_check().
◆ bt_rootdescend()
|
static |
Definition at line 3009 of file verify_nbtree.c.
3010{
3012 BTStack stack;
3015
3018
3019 /*
3020 * Search from root.
3021 *
3022 * Ideally, we would arrange to only move right within _bt_search() when
3023 * an interrupted page split is detected (i.e. when the incomplete split
3024 * bit is found to be set), but for now we accept the possibility that
3025 * that could conceal an inconsistency.
3026 */
3030
3032 {
3034 OffsetNumber offnum;
3035 Page page;
3036
3040 insertstate.postingoff = 0;
3043
3044 /* Get matching tuple on leaf page */
3046 /* Compare first >= matching item on leaf page, if any */
3048 /* Should match on first heap TID when tuple has a posting list */
3050 insertstate.postingoff <= 0 &&
3054 }
3055
3056 _bt_freestack(stack);
3057 pfree(key);
3058
3060}
References _bt_binsrch_insert(), _bt_compare(), _bt_freestack(), _bt_mkscankey(), _bt_relbuf(), _bt_search(), Assert, BT_READ, BufferGetPage(), BufferIsValid(), fb(), IndexTupleSize(), BTInsertStateData::itup, MAXALIGN, PageGetMaxOffsetNumber(), and pfree().
Referenced by bt_target_page_check().
◆ bt_target_page_check()
|
static |
Definition at line 1239 of file verify_nbtree.c.
1240{
1241 OffsetNumber offset;
1242 OffsetNumber max;
1244
1245 /* Last visible entry info for checking indexes with unique constraint */
1247
1250
1253
1254 /*
1255 * Check the number of attributes in high key. Note, rightmost page
1256 * doesn't contain a high key, so nothing to check
1257 */
1259 {
1260 ItemId itemid;
1261 IndexTuple itup;
1262
1263 /* Verify line pointer before checking tuple */
1267 P_HIKEY))
1268 {
1275 state->targetblock,
1279 }
1280 }
1281
1282 /*
1283 * Loop over page items, starting from first non-highkey item, not high
1284 * key (if any). Most tests are not performed for the "negative infinity"
1285 * real item (if any).
1286 */
1288 offset <= max;
1289 offset = OffsetNumberNext(offset))
1290 {
1291 ItemId itemid;
1292 IndexTuple itup;
1296 ItemPointer scantid;
1297
1298 /*
1299 * True if we already called bt_entry_unique_check() for the current
1300 * item. This helps to avoid visiting the heap for keys, which are
1301 * anyway presented only once and can't comprise a unique violation.
1302 */
1304
1305 CHECK_FOR_INTERRUPTS();
1306
1308 state->target, offset);
1311
1312 /*
1313 * lp_len should match the IndexTuple reported length exactly, since
1314 * lp_len is completely redundant in indexes, and both sources of
1315 * tuple length are MAXALIGN()'d. nbtree does not use lp_len all that
1316 * frequently, and is surprisingly tolerant of corrupt lp_len fields.
1317 */
1324 state->targetblock, offset,
1328
1329 /* Check the number of index tuple attributes */
1331 offset))
1332 {
1333 ItemPointer tid;
1335 *htid;
1336
1338 tid = BTreeTupleGetPointsToTID(itup);
1340 ItemPointerGetBlockNumberNoCheck(tid),
1341 ItemPointerGetOffsetNumberNoCheck(tid));
1342
1348 itid,
1351 htid,
1353 }
1354
1355 /*
1356 * Don't try to generate scankey using "negative infinity" item on
1357 * internal pages. They are always truncated to zero attributes.
1358 */
1360 {
1361 /*
1362 * We don't call bt_child_check() for "negative infinity" items.
1363 * But if we're performing downlink connectivity check, we do it
1364 * for every item including "negative infinity" one.
1365 */
1367 {
1369 offset,
1370 NULL,
1371 topaque->btpo_level);
1372 }
1373 continue;
1374 }
1375
1376 /*
1377 * Readonly callers may optionally verify that non-pivot tuples can
1378 * each be found by an independent search that starts from the root.
1379 * Note that we deliberately don't do individual searches for each
1380 * TID, since the posting list itself is validated by other checks.
1381 */
1384 {
1387 *htid;
1388
1391 ItemPointerGetOffsetNumber(tid));
1392
1400 }
1401
1402 /*
1403 * If tuple is a posting list tuple, make sure posting list TIDs are
1404 * in order
1405 */
1407 {
1408 ItemPointerData last;
1409 ItemPointer current;
1410
1412
1414 {
1415
1417
1419 {
1421
1429 }
1430
1431 ItemPointerCopy(current, &last);
1432 }
1433 }
1434
1435 /* Build insertion scankey for current page offset */
1437
1438 /*
1439 * Make sure tuple size does not exceed the relevant BTREE_VERSION
1440 * specific limit.
1441 *
1442 * BTREE_VERSION 4 (which introduced heapkeyspace rules) requisitioned
1443 * a small amount of space from BTMaxItemSize() in order to ensure
1444 * that suffix truncation always has enough space to add an explicit
1445 * heap TID back to a tuple -- we pessimistically assume that every
1446 * newly inserted tuple will eventually need to have a heap TID
1447 * appended during a future leaf page split, when the tuple becomes
1448 * the basis of the new high key (pivot tuple) for the leaf page.
1449 *
1450 * Since the reclaimed space is reserved for that purpose, we must not
1451 * enforce the slightly lower limit when the extra space has been used
1452 * as intended. In other words, there is only a cross-version
1453 * difference in the limit on tuple size within leaf pages.
1454 *
1455 * Still, we're particular about the details within BTREE_VERSION 4
1456 * internal pages. Pivot tuples may only use the extra space for its
1457 * designated purpose. Enforce the lower limit for pivot tuples when
1458 * an explicit heap TID isn't actually present. (In all other cases
1459 * suffix truncation is guaranteed to generate a pivot tuple that's no
1460 * larger than the firstright tuple provided to it by its caller.)
1461 */
1465 {
1468 *htid;
1469
1472 ItemPointerGetBlockNumberNoCheck(tid),
1473 ItemPointerGetOffsetNumberNoCheck(tid));
1474
1480 itid,
1482 htid,
1484 }
1485
1486 /* Fingerprint leaf page tuples (those that point to the heap) */
1488 {
1490
1492 {
1493 /* Fingerprint all elements as distinct "plain" tuples */
1495 {
1497
1502 /* Be tidy */
1506 }
1507 }
1508 else
1509 {
1513 /* Be tidy */
1516 }
1517 }
1518
1519 /*
1520 * * High key check *
1521 *
1522 * If there is a high key (if this is not the rightmost page on its
1523 * entire level), check that high key actually is upper bound on all
1524 * page items. If this is a posting list tuple, we'll need to set
1525 * scantid to be highest TID in posting list.
1526 *
1527 * We prefer to check all items against high key rather than checking
1528 * just the last and trusting that the operator class obeys the
1529 * transitive law (which implies that all previous items also
1530 * respected the high key invariant if they pass the item order
1531 * check).
1532 *
1533 * Ideally, we'd compare every item in the index against every other
1534 * item in the index, and not trust opclass obedience of the
1535 * transitive law to bridge the gap between children and their
1536 * grandparents (as well as great-grandparents, and so on). We don't
1537 * go to those lengths because that would be prohibitively expensive,
1538 * and probably not markedly more effective in practice.
1539 *
1540 * On the leaf level, we check that the key is <= the highkey.
1541 * However, on non-leaf levels we check that the key is < the highkey,
1542 * because the high key is "just another separator" rather than a copy
1543 * of some existing key item; we expect it to be unique among all keys
1544 * on the same level. (Suffix truncation will sometimes produce a
1545 * leaf highkey that is an untruncated copy of the lastleft item, but
1546 * never any other item, which necessitates weakening the leaf level
1547 * check to <=.)
1548 *
1549 * Full explanation for why a highkey is never truly a copy of another
1550 * item from the same level on internal levels:
1551 *
1552 * While the new left page's high key is copied from the first offset
1553 * on the right page during an internal page split, that's not the
1554 * full story. In effect, internal pages are split in the middle of
1555 * the firstright tuple, not between the would-be lastleft and
1556 * firstright tuples: the firstright key ends up on the left side as
1557 * left's new highkey, and the firstright downlink ends up on the
1558 * right side as right's new "negative infinity" item. The negative
1559 * infinity tuple is truncated to zero attributes, so we're only left
1560 * with the downlink. In other words, the copying is just an
1561 * implementation detail of splitting in the middle of a (pivot)
1562 * tuple. (See also: "Notes About Data Representation" in the nbtree
1563 * README.)
1564 */
1565 scantid = skey->scantid;
1568
1572 {
1575 *htid;
1576
1579 ItemPointerGetBlockNumberNoCheck(tid),
1580 ItemPointerGetOffsetNumberNoCheck(tid));
1581
1587 itid,
1589 htid,
1591 }
1592 /* Reset, in case scantid was set to (itup) posting tuple's max TID */
1593 skey->scantid = scantid;
1594
1595 /*
1596 * * Item order check *
1597 *
1598 * Check that items are stored on page in logical order, by checking
1599 * current item is strictly less than next item (if any).
1600 */
1603 {
1604 ItemPointer tid;
1606 *htid,
1607 *nitid,
1608 *nhtid;
1609
1611 tid = BTreeTupleGetPointsToTID(itup);
1613 ItemPointerGetBlockNumberNoCheck(tid),
1614 ItemPointerGetOffsetNumberNoCheck(tid));
1616 OffsetNumberNext(offset));
1617
1618 /* Reuse itup to get pointed-to heap location of second item */
1620 state->target,
1621 OffsetNumberNext(offset));
1623 tid = BTreeTupleGetPointsToTID(itup);
1625 ItemPointerGetBlockNumberNoCheck(tid),
1626 ItemPointerGetOffsetNumberNoCheck(tid));
1627
1632 errdetail_internal("Lower index tid=%s (points to %s tid=%s) higher index tid=%s (points to %s tid=%s) page lsn=%X/%08X.",
1633 itid,
1635 htid,
1636 nitid,
1638 nhtid,
1640 }
1641
1642 /*
1643 * If the index is unique verify entries uniqueness by checking the
1644 * heap tuples visibility. Immediately check posting tuples and
1645 * tuples with repeated keys. Postpone check for keys, which have the
1646 * first appearance.
1647 */
1651 {
1653 &lVis);
1655 }
1656
1659 {
1660 /* Save current scankey tid */
1661 scantid = skey->scantid;
1662
1663 /*
1664 * Invalidate scankey tid to make _bt_compare compare only keys in
1665 * the item to report equality even if heap TIDs are different
1666 */
1668
1669 /*
1670 * If next key tuple is different, invalidate last visible entry
1671 * data (whole index tuple or last posting in index tuple). Key
1672 * containing null value does not violate unique constraint and
1673 * treated as different to any other key.
1674 *
1675 * If the next key is the same as the previous one, do the
1676 * bt_entry_unique_check() call if it was postponed.
1677 */
1680 {
1683 lVis.postingIndex = -1;
1685 }
1687 {
1689 &lVis);
1690 }
1692 }
1693
1694 /*
1695 * * Last item check *
1696 *
1697 * Check last item against next/right page's first data item's when
1698 * last item on page is reached. This additional check will detect
1699 * transposed pages iff the supposed right sibling page happens to
1700 * belong before target in the key space. (Otherwise, a subsequent
1701 * heap verification will probably detect the problem.)
1702 *
1703 * This check is similar to the item order check that will have
1704 * already been performed for every other "real" item on target page
1705 * when last item is checked. The difference is that the next item
1706 * (the item that is compared to target's last item) needs to come
1707 * from the next/sibling page. There may not be such an item
1708 * available from sibling for various reasons, though (e.g., target is
1709 * the rightmost page on level).
1710 */
1711 if (offset == max)
1712 {
1714
1715 /* first offset on a right index page (log only) */
1717
1718 /* Get item in next/right page */
1720
1723 {
1724 /*
1725 * As explained at length in bt_right_page_check_scankey(),
1726 * there is a known !readonly race that could account for
1727 * apparent violation of invariant, which we must check for
1728 * before actually proceeding with raising error. Our canary
1729 * condition is that target page was deleted.
1730 */
1732 {
1733 /* Get fresh copy of target page */
1735 /* Note that we deliberately do not update target LSN */
1737
1738 /*
1739 * All !readonly checks now performed; just return
1740 */
1742 return;
1743 }
1744
1750 state->targetblock, offset,
1752 }
1753
1754 /*
1755 * If index has unique constraint make sure that no more than one
1756 * found equal items is visible.
1757 */
1760 {
1762
1764
1765 /*
1766 * Make _bt_compare compare only index keys without heap TIDs.
1767 * rightkey->scantid is modified destructively but it is ok
1768 * for it is not used later.
1769 */
1771
1772 /* The first key on the next page is the same */
1774 !rightkey->anynullkeys)
1775 {
1777
1778 /*
1779 * Do the bt_entry_unique_check() call if it was
1780 * postponed.
1781 */
1784 offset, &lVis);
1785
1788 rightblock_number);
1790
1792 {
1794 break;
1795 }
1796
1803 state->targetblock,
1805
1807 rightpage,
1808 rightfirstoffset);
1810
1812
1814 }
1815 }
1816 }
1817
1818 /*
1819 * * Downlink check *
1820 *
1821 * Additional check of child items iff this is an internal page and
1822 * caller holds a ShareLock. This happens for every downlink (item)
1823 * in target excluding the negative-infinity downlink (again, this is
1824 * because it has no useful value to compare).
1825 */
1828 }
1829
1830 /*
1831 * Special case bt_child_highkey_check() call
1832 *
1833 * We don't pass a real downlink, but we've to finish the level
1834 * processing. If condition is satisfied, we've already processed all the
1835 * downlinks from the target level. But there still might be pages to the
1836 * right of the child page pointer to by our rightmost downlink. And they
1837 * might have missing downlinks. This final call checks for them.
1838 */
1840 {
1843 }
1844}
References _bt_check_natts(), _bt_compare(), bloom_add_element(), bt_child_check(), bt_child_highkey_check(), bt_entry_unique_check(), bt_mkscankey_pivotsearch(), bt_normalize_tuple(), bt_posting_plain_tuple(), bt_right_page_check_scankey(), bt_rootdescend(), BTMaxItemSize, BTMaxItemSizeNoHeapTid, BTPageGetOpaque, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNAtts, BTreeTupleGetNPosting(), BTreeTupleGetPointsToTID(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), CHECK_FOR_INTERRUPTS, DEBUG2, elog, ereport, errcode(), errdetail_internal(), errhint(), errmsg(), errmsg_internal(), ERROR, fb(), i, IndexTupleSize(), InvalidBlockNumber, InvalidOffsetNumber, invariant_g_offset(), invariant_l_offset(), invariant_leq_offset(), ItemIdGetLength, ItemIdIsDead, ItemPointerCompare(), ItemPointerCopy(), ItemPointerGetBlockNumber(), ItemPointerGetBlockNumberNoCheck(), ItemPointerGetOffsetNumber(), ItemPointerGetOffsetNumberNoCheck(), ItemPointerIsValid(), LSN_FORMAT_ARGS, offset_is_negative_infinity(), OffsetNumberNext, P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), psprintf(), RelationGetRelationName, and unlikely.
Referenced by bt_check_level_from_leftmost().
◆ bt_tuple_present_callback()
|
static |
Definition at line 2780 of file verify_nbtree.c.
2782{
2784 IndexTuple itup,
2785 norm;
2786
2788
2789 /* Generate a normalized index tuple for fingerprinting */
2791 itup->t_tid = *tid;
2793
2794 /* Probe Bloom filter -- tuple should be present */
2804 !state->readonly
2805 ? errhint("Retrying verification using the function bt_index_parent_check() might provide a more specific error.")
2806 : 0));
2807
2808 state->heaptuplespresent++;
2809 pfree(itup);
2810 /* Cannot leak memory here */
2813}
References Assert, bloom_lacks_element(), bt_normalize_tuple(), ereport, errcode(), ERRCODE_DATA_CORRUPTED, errhint(), errmsg(), ERROR, fb(), index_form_tuple(), IndexTupleSize(), ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), pfree(), RelationGetDescr, RelationGetRelationName, IndexTupleData::t_tid, and values.
Referenced by bt_check_every_level().
◆ BTreeTupleGetHeapTIDCareful()
|
inlinestatic |
Definition at line 3532 of file verify_nbtree.c.
3534{
3536
3537 /*
3538 * Caller determines whether this is supposed to be a pivot or non-pivot
3539 * tuple using page type and item offset number. Verify that tuple
3540 * metadata agrees with this.
3541 */
3546 errmsg_internal("block %u or its right sibling block or child block in index \"%s\" has unexpected pivot tuple",
3547 state->targetblock,
3549
3553 errmsg_internal("block %u or its right sibling block or child block in index \"%s\" has unexpected non-pivot tuple",
3554 state->targetblock,
3556
3561 errmsg("block %u or its right sibling block or child block in index \"%s\" contains non-pivot tuple that lacks a heap TID",
3562 state->targetblock,
3564
3566}
References Assert, BTreeTupleGetHeapTID(), BTreeTupleIsPivot(), ereport, errcode(), errmsg(), errmsg_internal(), ERROR, fb(), ItemPointerIsValid(), and RelationGetRelationName.
Referenced by invariant_l_nontarget_offset(), and invariant_l_offset().
◆ BTreeTupleGetPointsToTID()
|
inlinestatic |
Definition at line 3580 of file verify_nbtree.c.
3581{
3582 /*
3583 * Rely on the assumption that !heapkeyspace internal page data items will
3584 * correctly return TID with downlink here -- BTreeTupleGetHeapTID() won't
3585 * recognize it as a pivot tuple, but everything still works out because
3586 * the t_tid field is still returned
3587 */
3590
3591 /* Pivot tuple returns TID with downlink block (heapkeyspace variant) */
3593}
References BTreeTupleGetHeapTID(), BTreeTupleIsPivot(), and IndexTupleData::t_tid.
Referenced by bt_target_page_check().
◆ heap_entry_is_visible()
|
static |
Definition at line 852 of file verify_nbtree.c.
References ExecDropSingleTupleTableSlot(), fb(), table_slot_create(), and table_tuple_fetch_row_version().
Referenced by bt_entry_unique_check().
◆ invariant_g_offset()
|
inlinestatic |
Definition at line 3194 of file verify_nbtree.c.
3196{
3198
3200
3202
3203 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3206
3207 /*
3208 * No need to consider the possibility that scankey has attributes that we
3209 * need to force to be interpreted as negative infinity. _bt_compare() is
3210 * able to determine that scankey is greater than negative infinity. The
3211 * distinction between "==" and "<" isn't interesting here, since
3212 * corruption is indicated either way.
3213 */
3215}
References _bt_compare(), Assert, cmp(), and fb().
Referenced by bt_target_page_check().
◆ invariant_l_nontarget_offset()
|
inlinestatic |
Definition at line 3230 of file verify_nbtree.c.
3233{
3234 ItemId itemid;
3236
3238
3239 /* Verify line pointer before checking tuple */
3241 upperbound);
3243
3244 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3247
3248 /* See invariant_l_offset() for an explanation of this extra step */
3250 {
3251 IndexTuple child;
3256
3260
3261 /* Get number of keys + heap TID for child/non-target item */
3264
3265 /* Heap TID is tiebreaker key attribute */
3268
3270 }
3271
3273}
References _bt_compare(), Assert, BTPageGetOpaque, BTreeTupleGetHeapTIDCareful(), BTreeTupleGetNKeyAtts, cmp(), fb(), P_FIRSTDATAKEY, P_ISLEAF, PageGetItem(), and PageGetItemIdCareful().
Referenced by bt_child_check().
◆ invariant_l_offset()
|
inlinestatic |
Definition at line 3108 of file verify_nbtree.c.
3110{
3111 ItemId itemid;
3113
3115
3116 /* Verify line pointer before checking tuple */
3118 upperbound);
3119 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3122
3124
3125 /*
3126 * _bt_compare() is capable of determining that a scankey with a
3127 * filled-out attribute is greater than pivot tuples where the comparison
3128 * is resolved at a truncated attribute (value of attribute in pivot is
3129 * minus infinity). However, it is not capable of determining that a
3130 * scankey is _less than_ a tuple on the basis of a comparison resolved at
3131 * _scankey_ minus infinity attribute. Complete an extra step to simulate
3132 * having minus infinity values for omitted scankey attribute(s).
3133 */
3135 {
3141
3145
3146 /* Get number of keys + heap TID for item to the right */
3149
3150 /* Heap TID is tiebreaker key attribute */
3153
3155 }
3156
3158}
References _bt_compare(), Assert, BTPageGetOpaque, BTreeTupleGetHeapTIDCareful(), BTreeTupleGetNKeyAtts, cmp(), fb(), invariant_leq_offset(), P_FIRSTDATAKEY, P_ISLEAF, PageGetItem(), and PageGetItemIdCareful().
Referenced by bt_target_page_check().
◆ invariant_leq_offset()
|
inlinestatic |
Definition at line 3171 of file verify_nbtree.c.
3173{
3175
3177
3179
3181}
References _bt_compare(), Assert, cmp(), and fb().
Referenced by bt_target_page_check(), and invariant_l_offset().
◆ offset_is_negative_infinity()
|
inlinestatic |
Definition at line 3073 of file verify_nbtree.c.
3074{
3075 /*
3076 * For internal pages only, the first item after high key, if any, is
3077 * negative infinity item. Internal pages always have a negative infinity
3078 * item, whereas leaf pages never have one. This implies that negative
3079 * infinity item is either first or second line item, or there is none
3080 * within page.
3081 *
3082 * Negative infinity items are a special case among pivot tuples. They
3083 * always have zero attributes, while all other pivot tuples always have
3084 * nkeyatts attributes.
3085 *
3086 * Right-most pages don't have a high key, but could be said to
3087 * conceptually have a "positive infinity" high key. Thus, there is a
3088 * symmetry between down link items in parent pages, and high keys in
3089 * children. Together, they represent the part of the key space that
3090 * belongs to each page in the index. For example, all children of the
3091 * root page will have negative infinity as a lower bound from root
3092 * negative infinity downlink, and positive infinity as an upper bound
3093 * (implicitly, from "imaginary" positive infinity high key in root).
3094 */
3096}
References P_FIRSTDATAKEY, and P_ISLEAF.
Referenced by bt_child_check(), bt_child_highkey_check(), and bt_target_page_check().
◆ PageGetItemIdCareful()
|
static |
Definition at line 3492 of file verify_nbtree.c.
3494{
3496
3504 block, offset, ItemIdGetOffset(itemid),
3505 ItemIdGetLength(itemid),
3506 ItemIdGetFlags(itemid))));
3507
3508 /*
3509 * Verify that line pointer isn't LP_REDIRECT or LP_UNUSED, since nbtree
3510 * never uses either. Verify that line pointer has storage, too, since
3511 * even LP_DEAD items should within nbtree.
3512 */
3514 ItemIdGetLength(itemid) == 0)
3520 block, offset, ItemIdGetOffset(itemid),
3521 ItemIdGetLength(itemid),
3522 ItemIdGetFlags(itemid))));
3523
3524 return itemid;
3525}
References ereport, errcode(), errdetail_internal(), errmsg(), ERROR, fb(), ItemIdGetFlags, ItemIdGetLength, ItemIdGetOffset, ItemIdIsRedirected, ItemIdIsUsed, MAXALIGN, PageGetItemId(), and RelationGetRelationName.
Referenced by bt_check_level_from_leftmost(), bt_child_check(), bt_child_highkey_check(), bt_downlink_missing_check(), bt_right_page_check_scankey(), bt_target_page_check(), invariant_l_nontarget_offset(), and invariant_l_offset().
◆ palloc_btree_page()
|
static |
Definition at line 3290 of file verify_nbtree.c.
3291{
3292 Buffer buffer;
3293 Page page;
3294 BTPageOpaque opaque;
3296
3298
3299 /*
3300 * We copy the page into local storage to avoid holding pin on the buffer
3301 * longer than we must.
3302 */
3304 state->checkstrategy);
3306
3307 /*
3308 * Perform the same basic sanity checking that nbtree itself performs for
3309 * every page:
3310 */
3312
3313 /* Only use copy of page in palloc()'d memory */
3315 UnlockReleaseBuffer(buffer);
3316
3317 opaque = BTPageGetOpaque(page);
3318
3324
3325 /* Check page from block that ought to be meta page */
3327 {
3329
3336
3342 "current version %d, minimum supported version %d",
3345 BTREE_MIN_VERSION)));
3346
3347 /* Finished with metapage checks */
3348 return page;
3349 }
3350
3351 /*
3352 * Deleted pages that still use the old 32-bit XID representation have no
3353 * sane "level" field because they type pun the field, but all other pages
3354 * (including pages deleted on Postgres 14+) have a valid value.
3355 */
3357 {
3358 /* Okay, no reason not to trust btpo_level field from page */
3359
3364 opaque->btpo_level, blocknum,
3366
3371 blocknum,
3373 }
3374
3375 /*
3376 * Sanity checks for number of items on page.
3377 *
3378 * As noted at the beginning of _bt_binsrch(), an internal page must have
3379 * children, since there must always be a negative infinity downlink
3380 * (there may also be a highkey). In the case of non-rightmost leaf
3381 * pages, there must be at least a highkey. The exceptions are deleted
3382 * pages, which contain no items.
3383 *
3384 * This is correct when pages are half-dead, since internal pages are
3385 * never half-dead, and leaf pages must have a high key when half-dead
3386 * (the rightmost page can never be deleted). It's also correct with
3387 * fully deleted pages: _bt_unlink_halfdead_page() doesn't change anything
3388 * about the target page other than setting the page as fully dead, and
3389 * setting its xact field. In particular, it doesn't change the sibling
3390 * links in the deletion target itself, since they're required when index
3391 * scans land on the deletion target, and then need to move right (or need
3392 * to move left, in the case of backward index scans).
3393 */
3400 MaxIndexTuplesPerPage)));
3401
3407
3413
3414 /*
3415 * In general, internal pages are never marked half-dead, except on
3416 * versions of Postgres prior to 9.4, where it can be valid transient
3417 * state. This state is nonetheless treated as corruption by VACUUM on
3418 * from version 9.4 on, so do the same here. See _bt_pagedel() for full
3419 * details.
3420 */
3426 errhint("This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));
3427
3428 /*
3429 * Check that internal pages have no garbage items, and that no page has
3430 * an invalid combination of deletion-related page level flags
3431 */
3437
3441 errmsg_internal("full transaction id page flag appears in non-deleted block %u in index \"%s\"",
3443
3449
3450 return page;
3451}
References _bt_checkpage(), BT_READ, BTPageGetMeta, BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTREE_MAGIC, BTREE_METAPAGE, BTREE_MIN_VERSION, BTREE_VERSION, BufferGetPage(), ereport, errcode(), errhint(), errmsg(), errmsg_internal(), ERROR, fb(), LockBuffer(), MAIN_FORKNUM, MaxIndexTuplesPerPage, P_FIRSTDATAKEY, P_HAS_FULLXID, P_HAS_GARBAGE, P_HIKEY, P_ISDELETED, P_ISHALFDEAD, P_ISLEAF, P_ISMETA, P_RIGHTMOST, PageGetMaxOffsetNumber(), palloc(), RBM_NORMAL, ReadBufferExtended(), RelationGetRelationName, and UnlockReleaseBuffer().
Referenced by bt_check_every_level(), bt_check_level_from_leftmost(), bt_child_check(), bt_child_highkey_check(), bt_downlink_missing_check(), bt_leftmost_ignoring_half_dead(), bt_right_page_check_scankey(), and bt_target_page_check().
◆ PG_FUNCTION_INFO_V1() [1/2]
| PG_FUNCTION_INFO_V1 | ( | bt_index_check | ) |
◆ PG_FUNCTION_INFO_V1() [2/2]
| PG_FUNCTION_INFO_V1 | ( | bt_index_parent_check | ) |
◆ PG_MODULE_MAGIC_EXT()
| PG_MODULE_MAGIC_EXT | ( | . | name = "amcheck", |
| . | version = PG_VERSION |
||
| ) |
