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 {
338 break;
339 }
340
345 has_interval_ops
347 : 0));
348 }
349
350 /* Check index, possibly against table it is an index on */
353}
354
355/*
356 * Main entry point for B-Tree SQL-callable functions. Walks the B-Tree in
357 * logical order, verifying invariants as it goes. Optionally, verification
358 * checks if the heap relation contains any tuples that are not represented in
359 * the index but should be.
360 *
361 * It is the caller's responsibility to acquire appropriate heavyweight lock on
362 * the index relation, and advise us if extra checks are safe when a ShareLock
363 * is held. (A lock of the same type must also have been acquired on the heap
364 * relation.)
365 *
366 * A ShareLock is generally assumed to prevent any kind of physical
367 * modification to the index structure, including modifications that VACUUM may
368 * make. This does not include setting of the LP_DEAD bit by concurrent index
369 * scans, although that is just metadata that is not able to directly affect
370 * any check performed here. Any concurrent process that might act on the
371 * LP_DEAD bit being set (recycle space) requires a heavyweight lock that
372 * cannot be held while we hold a ShareLock. (Besides, even if that could
373 * happen, the ad-hoc recycling when a page might otherwise split is performed
374 * per-page, and requires an exclusive buffer lock, which wouldn't cause us
375 * trouble. _bt_delitems_vacuum() may only delete leaf items, and so the extra
376 * parent/child check cannot be affected.)
377 */
378static void
380 bool readonly, bool heapallindexed, bool rootdescend,
381 bool checkunique)
382{
387 BtreeLevel current;
388
389 if (!readonly)
391 RelationGetRelationName(rel));
392 else
393 elog(DEBUG1, "verifying consistency of tree structure for index \"%s\" with cross-level checks",
394 RelationGetRelationName(rel));
395
396 /*
397 * This assertion matches the one in index_getnext_tid(). See page
398 * recycling/"visible to everyone" notes in nbtree README.
399 */
401
402 /*
403 * Initialize state for entire verification operation
404 */
406 state->rel = rel;
407 state->heaprel = heaprel;
408 state->heapkeyspace = heapkeyspace;
409 state->readonly = readonly;
410 state->heapallindexed = heapallindexed;
411 state->rootdescend = rootdescend;
412 state->checkunique = checkunique;
414
416 {
419 uint64 seed;
420
421 /*
422 * Size Bloom filter based on estimated number of tuples in index,
423 * while conservatively assuming that each block must contain at least
424 * MaxTIDsPerBTreePage / 3 "plain" tuples -- see
425 * bt_posting_plain_tuple() for definition, and details of how posting
426 * list tuples are handled.
427 */
431 /* Generate a random seed to avoid repetition */
433 /* Create Bloom filter to fingerprint index */
435 state->heaptuplespresent = 0;
436
437 /*
438 * Register our own snapshot for heapallindexed, rather than asking
439 * table_index_build_scan() to do this for us later. This needs to
440 * happen before index fingerprinting begins, so we can later be
441 * certain that index fingerprinting should have reached all tuples
442 * returned by table_index_build_scan().
443 */
445
446 /*
447 * GetTransactionSnapshot() always acquires a new MVCC snapshot in
448 * READ COMMITTED mode. A new snapshot is guaranteed to have all the
449 * entries it requires in the index.
450 *
451 * We must defend against the possibility that an old xact snapshot
452 * was returned at higher isolation levels when that snapshot is not
453 * safe for index scans of the target index. This is possible when
454 * the snapshot sees tuples that are before the index's indcheckxmin
455 * horizon. Throwing an error here should be very rare. It doesn't
456 * seem worth using a secondary snapshot to avoid this.
457 */
460 state->snapshot->xmin))
464 RelationGetRelationName(rel)));
465 }
466
467 /*
468 * We need a snapshot to check the uniqueness of the index. For better
469 * performance, take it once per index check. If one was already taken
470 * above, use that.
471 */
473 {
475
478 }
479
484 errmsg("cannot verify that tuples from index \"%s\" can each be found by an independent index search",
485 RelationGetRelationName(rel)),
487
488 /* Create context for page */
490 "amcheck context",
491 ALLOCSET_DEFAULT_SIZES);
493
494 /* Get true root block from meta-page */
497
498 /*
499 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
500 * the fast root and true root differ.
501 *
502 * Start from the true root, not the fast root, unlike conventional index
503 * scans. This approach is more thorough, and removes the risk of
504 * following a stale fast root from the meta page.
505 */
510 RelationGetRelationName(rel)),
514
515 /*
516 * Starting at the root, verify every level. Move left to right, top to
517 * bottom. Note that there may be no pages other than the meta page (meta
518 * page can indicate that root is P_NONE when the index is totally empty).
519 */
525 {
526 /*
527 * Verify this level, and get left most page for next level down, if
528 * not at leaf level
529 */
531
537
539 }
540
541 /*
542 * * Check whether heap contains unindexed/malformed tuples *
543 */
545 {
547 TableScanDesc scan;
548
549 /*
550 * Create our own scan for table_index_build_scan(), rather than
551 * getting it to do so for us. This is required so that we can
552 * actually use the MVCC snapshot registered earlier.
553 *
554 * Note that table_index_build_scan() calls heap_endscan() for us.
555 */
558 0, /* number of keys */
560 true, /* buffer access strategy OK */
561 true); /* syncscan OK? */
562
563 /*
564 * Scan will behave as the first scan of a CREATE INDEX CONCURRENTLY
565 * behaves.
566 *
567 * It's okay that we don't actually use the same lock strength for the
568 * heap relation as any other ii_Concurrent caller would. We have no
569 * reason to care about a concurrent VACUUM operation, since there
570 * isn't going to be a second scan of the heap that needs to be sure
571 * that there was no concurrent recycling of TIDs.
572 */
574
575 /*
576 * Don't wait for uncommitted tuple xact commit/abort when index is a
577 * unique index on a catalog (or an index used by an exclusion
578 * constraint). This could otherwise happen in the readonly case.
579 */
584
588
591
593 (errmsg_internal("finished verifying presence of " INT64_FORMAT " tuples from table \"%s\" with bitset %.2f%% set",
596
598 }
599
600 /* Be tidy: */
604}
605
606/*
607 * Given a left-most block at some level, move right, verifying each page
608 * individually (with more verification across pages for "readonly"
609 * callers). Caller should pass the true root page as the leftmost initially,
610 * working their way down by passing what is returned for the last call here
611 * until level 0 (leaf page level) was reached.
612 *
613 * Returns state for next call, if any. This includes left-most block number
614 * one level lower that should be passed on next level/call, which is set to
615 * P_NONE on last call here (when leaf level is verified). Level numbers
616 * follow the nbtree convention: higher levels have higher numbers, because new
617 * levels are added only due to a root page split. Note that prior to the
618 * first root page split, the root is also a leaf page, so there is always a
619 * level 0 (leaf level), and it's always the last level processed.
620 *
621 * Note on memory management: State's per-page context is reset here, between
622 * each call to bt_target_page_check().
623 */
626{
627 /* State to establish early, concerning entire level */
628 BTPageOpaque opaque;
629 MemoryContext oldcontext;
631
632 /* Variables for iterating across level using right links */
635
636 /* Initialize return state */
640
641 /* Use page-level context for duration of this call */
643
645 level.istruerootlevel ?
646 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
647
650
651 do
652 {
653 /* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
654 CHECK_FOR_INTERRUPTS();
655
656 /* Initialize state for this iteration */
657 state->targetblock = current;
660
662
664 {
665 /*
666 * Since there cannot be a concurrent VACUUM operation in readonly
667 * mode, and since a page has no links within other pages
668 * (siblings and parent) once it is marked fully deleted, it
669 * should be impossible to land on a fully deleted page in
670 * readonly mode. See bt_child_check() for further details.
671 *
672 * The bt_child_check() P_ISDELETED() check is repeated here so
673 * that pages that are only reachable through sibling links get
674 * checked.
675 */
683
689 else
695 }
697 {
698 /*
699 * A concurrent page split could make the caller supplied leftmost
700 * block no longer contain the leftmost page, or no longer be the
701 * true root, but where that isn't possible due to heavyweight
702 * locking, check that the first valid page meets caller's
703 * expectations.
704 */
706 {
712
718 }
719
720 /*
721 * Before beginning any non-trivial examination of level, prepare
722 * state for next bt_check_level_from_leftmost() invocation for
723 * the next level for the next level down (if any).
724 *
725 * There should be at least one non-ignorable page per level,
726 * unless this is the leaf level, which is assumed by caller to be
727 * final level.
728 */
730 {
731 IndexTuple itup;
732 ItemId itemid;
733
734 /* Internal page -- downlink gets leftmost on next level */
736 state->target,
737 P_FIRSTDATAKEY(opaque));
741 }
742 else
743 {
744 /*
745 * Leaf page -- final level caller must process.
746 *
747 * Note that this could also be the root page, if there has
748 * been no root page split yet.
749 */
752 }
753
754 /*
755 * Finished setting up state for this call/level. Control will
756 * never end up back here in any future loop iteration for this
757 * level.
758 */
759 }
760
761 /*
762 * Sibling links should be in mutual agreement. There arises
763 * leftcurrent == P_NONE && btpo_prev != P_NONE when the left sibling
764 * of the parent's low-key downlink is half-dead. (A half-dead page
765 * has no downlink from its parent.) Under heavyweight locking, the
766 * last bt_leftmost_ignoring_half_dead() validated this btpo_prev.
767 * Without heavyweight locking, validation of the P_NONE case remains
768 * unimplemented.
769 */
772
773 /* Check level */
777 errmsg("leftmost down link for level points to block in index \"%s\" whose level is not one level down",
781
782 /* Verify invariants for page */
784
785nextpage:
786
787 /* Try to detect circular links */
793
794 leftcurrent = current;
795 current = opaque->btpo_next;
796
798 {
802 }
803
804 /*
805 * Copy current target high key as the low key of right sibling.
806 * Allocate memory in upper level context, so it would be cleared
807 * after reset of target context.
808 *
809 * We only need the low key in corner cases of checking child high
810 * keys. We use high key only when incomplete split on the child level
811 * falls to the boundary of pages on the target level. See
812 * bt_child_highkey_check() for details. So, typically we won't end
813 * up doing anything with low key, but it's simpler for general case
814 * high key verification to always have it available.
815 *
816 * The correctness of managing low key in the case of concurrent
817 * splits wasn't investigated yet. Thankfully we only need low key
818 * for readonly verification and concurrent splits won't happen.
819 */
821 {
822 IndexTuple itup;
823 ItemId itemid;
824
828
831 }
832
833 /* Free page and associated memory for this iteration */
835 }
837
839 {
843 }
844
845 /* Don't change context for caller */
846 MemoryContextSwitchTo(oldcontext);
847
849}
850
851/* Check visibility of the table entry referenced by nbtree index */
852static bool
854{
856
858
860 tid, state->snapshot, slot);
862 ExecDropSingleTupleTableSlot(slot);
863
865}
866
867/*
868 * Prepare an error message for unique constraint violation in
869 * a btree index and report ERROR.
870 */
871static void
876{
878 *nhtid,
879 *itid,
883
891
894
897
900
908}
909
910/* Check if current nbtree leaf entry complies with UNIQUE constraint */
911static void
915{
916 ItemPointer tid;
918
920
921 /*
922 * Current tuple has posting list. Report duplicate if TID of any posting
923 * list entry is visible and lVis->tid is valid.
924 */
926 {
928 {
931 {
934 {
936 lVis,
937 tid, targetblock,
938 offset, i);
939 }
940
941 /*
942 * Prevent double reporting unique constraint violation
943 * between the posting list entries of the first tuple on the
944 * page after cross-page check.
945 */
947 return;
948
949 lVis->blkno = targetblock;
950 lVis->offset = offset;
952 lVis->tid = tid;
953 }
954 }
955 }
956
957 /*
958 * Current tuple has no posting list. If TID is visible save info about it
959 * for the next comparisons in the loop in bt_target_page_check(). Report
960 * duplicate if lVis->tid is already valid.
961 */
962 else
963 {
964 tid = BTreeTupleGetHeapTID(itup);
966 {
969 {
971 lVis,
972 tid, targetblock,
973 offset, -1);
974 }
975
976 lVis->blkno = targetblock;
977 lVis->offset = offset;
978 lVis->tid = tid;
979 lVis->postingIndex = -1;
980 }
981 }
982
985 lVis->blkno != targetblock)
986 {
988
994 targetblock, offset,
996 errdetail("It doesn't have visible heap tids and key is equal to the tid=(%u,%u)%s (points to heap tid=(%u,%u)).",
1001 }
1002}
1003
1004/*
1005 * Like P_LEFTMOST(start_opaque), but accept an arbitrarily-long chain of
1006 * half-dead, sibling-linked pages to the left. If a half-dead page appears
1007 * under state->readonly, the database exited recovery between the first-stage
1008 * and second-stage WAL records of a deletion.
1009 */
1010static bool
1014{
1018
1019 /*
1020 * To handle the !readonly case, we'd need to accept BTP_DELETED pages and
1021 * potentially observe nbtree/README "Page deletion and backwards scans".
1022 */
1024
1026 {
1029
1030 CHECK_FOR_INTERRUPTS();
1031
1032 /*
1033 * Try to detect btpo_prev circular links. _bt_unlink_halfdead_page()
1034 * writes that side-links will continue to point to the siblings.
1035 * Check btpo_next for that property.
1036 */
1042 {
1044
1045 /* pagelsn should point to an XLOG_BTREE_MARK_PAGE_HALFDEAD */
1053
1056 }
1057
1058 pfree(page);
1059 }
1060
1062}
1063
1064/*
1065 * Raise an error when target page's left link does not point back to the
1066 * previous target page, called leftcurrent here. The leftcurrent page's
1067 * right link was followed to get to the current target page, and we expect
1068 * mutual agreement among leftcurrent and the current target page. Make sure
1069 * that this condition has definitely been violated in the !readonly case,
1070 * where concurrent page splits are something that we need to deal with.
1071 *
1072 * Cross-page inconsistencies involving pages that don't agree about being
1073 * siblings are known to be a particularly good indicator of corruption
1074 * involving partial writes/lost updates. The bt_right_page_check_scankey
1075 * check also provides a way of detecting cross-page inconsistencies for
1076 * !readonly callers, but it can only detect sibling pages that have an
1077 * out-of-order keyspace, which can't catch many of the problems that we
1078 * expect to catch here.
1079 *
1080 * The classic example of the kind of inconsistency that we can only catch
1081 * with this check (when in !readonly mode) involves three sibling pages that
1082 * were affected by a faulty page split at some point in the past. The
1083 * effects of the split are reflected in the original page and its new right
1084 * sibling page, with a lack of any accompanying changes for the _original_
1085 * right sibling page. The original right sibling page's left link fails to
1086 * point to the new right sibling page (its left link still points to the
1087 * original page), even though the first phase of a page split is supposed to
1088 * work as a single atomic action. This subtle inconsistency will probably
1089 * only break backwards scans in practice.
1090 *
1091 * Note that this is the only place where amcheck will "couple" buffer locks
1092 * (and only for !readonly callers). In general we prefer to avoid more
1093 * thorough cross-page checks in !readonly mode, but it seems worth the
1094 * complexity here. Also, the performance overhead of performing lock
1095 * coupling here is negligible in practice. Control only reaches here with a
1096 * non-corrupt index when there is a concurrent page split at the instant
1097 * caller crossed over to target page from leftcurrent page.
1098 */
1099static void
1103{
1104 /* passing metapage to BTPageGetOpaque() would give irrelevant findings */
1106
1108 {
1111 Page page;
1112 BTPageOpaque opaque;
1114
1115 /* Couple locks in the usual order for nbtree: Left to right */
1121 opaque = BTPageGetOpaque(page);
1123 {
1124 /*
1125 * Cannot reason about concurrently deleted page -- the left link
1126 * in the page to the right is expected to point to some other
1127 * page to the left (not leftcurrent page).
1128 *
1129 * Note that we deliberately don't give up with a half-dead page.
1130 */
1132 return;
1133 }
1134
1136 /* Avoid self-deadlock when newtargetblock == leftcurrent */
1138 {
1141 state->checkstrategy);
1145 opaque = BTPageGetOpaque(page);
1146 /* btpo_prev_from_target may have changed; update it */
1148 }
1149 else
1150 {
1151 /*
1152 * leftcurrent right sibling points back to leftcurrent block.
1153 * Index is corrupt. Easiest way to handle this is to pretend
1154 * that we actually read from a distinct page that has an invalid
1155 * block number in its btpo_prev.
1156 */
1159 }
1160
1161 /*
1162 * No need to check P_ISDELETED here, since new target block cannot be
1163 * marked deleted as long as we hold a lock on lbuf
1164 */
1168
1170 {
1171 /* Report split in left sibling, not target (or new target) */
1178 state->targetblock)));
1179 return;
1180 }
1181
1182 /*
1183 * Index is corrupt. Make sure that we report correct target page.
1184 *
1185 * This could have changed in cases where there was a concurrent page
1186 * split, as well as index corruption (at least in theory). Note that
1187 * btpo_prev_from_target was already updated above.
1188 */
1190 }
1191
1198 btpo_prev_from_target)));
1199}
1200
1201/*
1202 * Function performs the following checks on target page, or pages ancillary to
1203 * target page:
1204 *
1205 * - That every "real" data item is less than or equal to the high key, which
1206 * is an upper bound on the items on the page. Data items should be
1207 * strictly less than the high key when the page is an internal page.
1208 *
1209 * - That within the page, every data item is strictly less than the item
1210 * immediately to its right, if any (i.e., that the items are in order
1211 * within the page, so that the binary searches performed by index scans are
1212 * sane).
1213 *
1214 * - That the last data item stored on the page is strictly less than the
1215 * first data item on the page to the right (when such a first item is
1216 * available).
1217 *
1218 * - Various checks on the structure of tuples themselves. For example, check
1219 * that non-pivot tuples have no truncated attributes.
1220 *
1221 * - For index with unique constraint make sure that only one of table entries
1222 * for equal keys is visible.
1223 *
1224 * Furthermore, when state passed shows ShareLock held, function also checks:
1225 *
1226 * - That all child pages respect strict lower bound from parent's pivot
1227 * tuple.
1228 *
1229 * - That downlink to block was encountered in parent where that's expected.
1230 *
1231 * - That high keys of child pages matches corresponding pivot keys in parent.
1232 *
1233 * This is also where heapallindexed callers use their Bloom filter to
1234 * fingerprint IndexTuples for later table_index_build_scan() verification.
1235 *
1236 * Note: Memory allocated in this routine is expected to be released by caller
1237 * resetting state->targetcontext.
1238 */
1239static void
1241{
1242 OffsetNumber offset;
1243 OffsetNumber max;
1245
1246 /* Last visible entry info for checking indexes with unique constraint */
1248
1251
1254
1255 /*
1256 * Check the number of attributes in high key. Note, rightmost page
1257 * doesn't contain a high key, so nothing to check
1258 */
1260 {
1261 ItemId itemid;
1262 IndexTuple itup;
1263
1264 /* Verify line pointer before checking tuple */
1268 P_HIKEY))
1269 {
1276 state->targetblock,
1280 }
1281 }
1282
1283 /*
1284 * Loop over page items, starting from first non-highkey item, not high
1285 * key (if any). Most tests are not performed for the "negative infinity"
1286 * real item (if any).
1287 */
1289 offset <= max;
1290 offset = OffsetNumberNext(offset))
1291 {
1292 ItemId itemid;
1293 IndexTuple itup;
1297 ItemPointer scantid;
1298
1299 /*
1300 * True if we already called bt_entry_unique_check() for the current
1301 * item. This helps to avoid visiting the heap for keys, which are
1302 * anyway presented only once and can't comprise a unique violation.
1303 */
1305
1306 CHECK_FOR_INTERRUPTS();
1307
1309 state->target, offset);
1312
1313 /*
1314 * lp_len should match the IndexTuple reported length exactly, since
1315 * lp_len is completely redundant in indexes, and both sources of
1316 * tuple length are MAXALIGN()'d. nbtree does not use lp_len all that
1317 * frequently, and is surprisingly tolerant of corrupt lp_len fields.
1318 */
1325 state->targetblock, offset,
1329
1330 /* Check the number of index tuple attributes */
1332 offset))
1333 {
1334 ItemPointer tid;
1336 *htid;
1337
1339 tid = BTreeTupleGetPointsToTID(itup);
1341 ItemPointerGetBlockNumberNoCheck(tid),
1342 ItemPointerGetOffsetNumberNoCheck(tid));
1343
1349 itid,
1352 htid,
1354 }
1355
1356 /*
1357 * Don't try to generate scankey using "negative infinity" item on
1358 * internal pages. They are always truncated to zero attributes.
1359 */
1361 {
1362 /*
1363 * We don't call bt_child_check() for "negative infinity" items.
1364 * But if we're performing downlink connectivity check, we do it
1365 * for every item including "negative infinity" one.
1366 */
1368 {
1370 offset,
1371 NULL,
1372 topaque->btpo_level);
1373 }
1374 continue;
1375 }
1376
1377 /*
1378 * Readonly callers may optionally verify that non-pivot tuples can
1379 * each be found by an independent search that starts from the root.
1380 * Note that we deliberately don't do individual searches for each
1381 * TID, since the posting list itself is validated by other checks.
1382 */
1385 {
1388 *htid;
1389
1392 ItemPointerGetOffsetNumber(tid));
1393
1401 }
1402
1403 /*
1404 * If tuple is a posting list tuple, make sure posting list TIDs are
1405 * in order
1406 */
1408 {
1409 ItemPointerData last;
1410 ItemPointer current;
1411
1413
1415 {
1416
1418
1420 {
1422
1430 }
1431
1432 ItemPointerCopy(current, &last);
1433 }
1434 }
1435
1436 /* Build insertion scankey for current page offset */
1438
1439 /*
1440 * Make sure tuple size does not exceed the relevant BTREE_VERSION
1441 * specific limit.
1442 *
1443 * BTREE_VERSION 4 (which introduced heapkeyspace rules) requisitioned
1444 * a small amount of space from BTMaxItemSize() in order to ensure
1445 * that suffix truncation always has enough space to add an explicit
1446 * heap TID back to a tuple -- we pessimistically assume that every
1447 * newly inserted tuple will eventually need to have a heap TID
1448 * appended during a future leaf page split, when the tuple becomes
1449 * the basis of the new high key (pivot tuple) for the leaf page.
1450 *
1451 * Since the reclaimed space is reserved for that purpose, we must not
1452 * enforce the slightly lower limit when the extra space has been used
1453 * as intended. In other words, there is only a cross-version
1454 * difference in the limit on tuple size within leaf pages.
1455 *
1456 * Still, we're particular about the details within BTREE_VERSION 4
1457 * internal pages. Pivot tuples may only use the extra space for its
1458 * designated purpose. Enforce the lower limit for pivot tuples when
1459 * an explicit heap TID isn't actually present. (In all other cases
1460 * suffix truncation is guaranteed to generate a pivot tuple that's no
1461 * larger than the firstright tuple provided to it by its caller.)
1462 */
1466 {
1469 *htid;
1470
1473 ItemPointerGetBlockNumberNoCheck(tid),
1474 ItemPointerGetOffsetNumberNoCheck(tid));
1475
1481 itid,
1483 htid,
1485 }
1486
1487 /* Fingerprint leaf page tuples (those that point to the heap) */
1489 {
1491
1493 {
1494 /* Fingerprint all elements as distinct "plain" tuples */
1496 {
1498
1503 /* Be tidy */
1507 }
1508 }
1509 else
1510 {
1514 /* Be tidy */
1517 }
1518 }
1519
1520 /*
1521 * * High key check *
1522 *
1523 * If there is a high key (if this is not the rightmost page on its
1524 * entire level), check that high key actually is upper bound on all
1525 * page items. If this is a posting list tuple, we'll need to set
1526 * scantid to be highest TID in posting list.
1527 *
1528 * We prefer to check all items against high key rather than checking
1529 * just the last and trusting that the operator class obeys the
1530 * transitive law (which implies that all previous items also
1531 * respected the high key invariant if they pass the item order
1532 * check).
1533 *
1534 * Ideally, we'd compare every item in the index against every other
1535 * item in the index, and not trust opclass obedience of the
1536 * transitive law to bridge the gap between children and their
1537 * grandparents (as well as great-grandparents, and so on). We don't
1538 * go to those lengths because that would be prohibitively expensive,
1539 * and probably not markedly more effective in practice.
1540 *
1541 * On the leaf level, we check that the key is <= the highkey.
1542 * However, on non-leaf levels we check that the key is < the highkey,
1543 * because the high key is "just another separator" rather than a copy
1544 * of some existing key item; we expect it to be unique among all keys
1545 * on the same level. (Suffix truncation will sometimes produce a
1546 * leaf highkey that is an untruncated copy of the lastleft item, but
1547 * never any other item, which necessitates weakening the leaf level
1548 * check to <=.)
1549 *
1550 * Full explanation for why a highkey is never truly a copy of another
1551 * item from the same level on internal levels:
1552 *
1553 * While the new left page's high key is copied from the first offset
1554 * on the right page during an internal page split, that's not the
1555 * full story. In effect, internal pages are split in the middle of
1556 * the firstright tuple, not between the would-be lastleft and
1557 * firstright tuples: the firstright key ends up on the left side as
1558 * left's new highkey, and the firstright downlink ends up on the
1559 * right side as right's new "negative infinity" item. The negative
1560 * infinity tuple is truncated to zero attributes, so we're only left
1561 * with the downlink. In other words, the copying is just an
1562 * implementation detail of splitting in the middle of a (pivot)
1563 * tuple. (See also: "Notes About Data Representation" in the nbtree
1564 * README.)
1565 */
1566 scantid = skey->scantid;
1569
1573 {
1576 *htid;
1577
1580 ItemPointerGetBlockNumberNoCheck(tid),
1581 ItemPointerGetOffsetNumberNoCheck(tid));
1582
1588 itid,
1590 htid,
1592 }
1593 /* Reset, in case scantid was set to (itup) posting tuple's max TID */
1594 skey->scantid = scantid;
1595
1596 /*
1597 * * Item order check *
1598 *
1599 * Check that items are stored on page in logical order, by checking
1600 * current item is strictly less than next item (if any).
1601 */
1604 {
1605 ItemPointer tid;
1607 *htid,
1608 *nitid,
1609 *nhtid;
1610
1612 tid = BTreeTupleGetPointsToTID(itup);
1614 ItemPointerGetBlockNumberNoCheck(tid),
1615 ItemPointerGetOffsetNumberNoCheck(tid));
1617 OffsetNumberNext(offset));
1618
1619 /* Reuse itup to get pointed-to heap location of second item */
1621 state->target,
1622 OffsetNumberNext(offset));
1624 tid = BTreeTupleGetPointsToTID(itup);
1626 ItemPointerGetBlockNumberNoCheck(tid),
1627 ItemPointerGetOffsetNumberNoCheck(tid));
1628
1633 errdetail_internal("Lower index tid=%s (points to %s tid=%s) higher index tid=%s (points to %s tid=%s) page lsn=%X/%08X.",
1634 itid,
1636 htid,
1637 nitid,
1639 nhtid,
1641 }
1642
1643 /*
1644 * If the index is unique verify entries uniqueness by checking the
1645 * heap tuples visibility. Immediately check posting tuples and
1646 * tuples with repeated keys. Postpone check for keys, which have the
1647 * first appearance.
1648 */
1652 {
1654 &lVis);
1656 }
1657
1660 {
1661 /* Save current scankey tid */
1662 scantid = skey->scantid;
1663
1664 /*
1665 * Invalidate scankey tid to make _bt_compare compare only keys in
1666 * the item to report equality even if heap TIDs are different
1667 */
1669
1670 /*
1671 * If next key tuple is different, invalidate last visible entry
1672 * data (whole index tuple or last posting in index tuple). Key
1673 * containing null value does not violate unique constraint and
1674 * treated as different to any other key.
1675 *
1676 * If the next key is the same as the previous one, do the
1677 * bt_entry_unique_check() call if it was postponed.
1678 */
1681 {
1684 lVis.postingIndex = -1;
1686 }
1688 {
1690 &lVis);
1691 }
1693 }
1694
1695 /*
1696 * * Last item check *
1697 *
1698 * Check last item against next/right page's first data item's when
1699 * last item on page is reached. This additional check will detect
1700 * transposed pages iff the supposed right sibling page happens to
1701 * belong before target in the key space. (Otherwise, a subsequent
1702 * heap verification will probably detect the problem.)
1703 *
1704 * This check is similar to the item order check that will have
1705 * already been performed for every other "real" item on target page
1706 * when last item is checked. The difference is that the next item
1707 * (the item that is compared to target's last item) needs to come
1708 * from the next/sibling page. There may not be such an item
1709 * available from sibling for various reasons, though (e.g., target is
1710 * the rightmost page on level).
1711 */
1712 if (offset == max)
1713 {
1715
1716 /* first offset on a right index page (log only) */
1718
1719 /* Get item in next/right page */
1721
1724 {
1725 /*
1726 * As explained at length in bt_right_page_check_scankey(),
1727 * there is a known !readonly race that could account for
1728 * apparent violation of invariant, which we must check for
1729 * before actually proceeding with raising error. Our canary
1730 * condition is that target page was deleted.
1731 */
1733 {
1734 /* Get fresh copy of target page */
1736 /* Note that we deliberately do not update target LSN */
1738
1739 /*
1740 * All !readonly checks now performed; just return
1741 */
1743 return;
1744 }
1745
1751 state->targetblock, offset,
1753 }
1754
1755 /*
1756 * If index has unique constraint make sure that no more than one
1757 * found equal items is visible.
1758 */
1761 {
1763
1765
1766 /*
1767 * Make _bt_compare compare only index keys without heap TIDs.
1768 * rightkey->scantid is modified destructively but it is ok
1769 * for it is not used later.
1770 */
1772
1773 /* The first key on the next page is the same */
1775 !rightkey->anynullkeys)
1776 {
1778
1779 /*
1780 * Do the bt_entry_unique_check() call if it was
1781 * postponed.
1782 */
1785 offset, &lVis);
1786
1789 rightblock_number);
1791
1793 {
1795 break;
1796 }
1797
1804 state->targetblock,
1806
1808 rightpage,
1809 rightfirstoffset);
1811
1813
1815 }
1816 }
1817 }
1818
1819 /*
1820 * * Downlink check *
1821 *
1822 * Additional check of child items iff this is an internal page and
1823 * caller holds a ShareLock. This happens for every downlink (item)
1824 * in target excluding the negative-infinity downlink (again, this is
1825 * because it has no useful value to compare).
1826 */
1829 }
1830
1831 /*
1832 * Special case bt_child_highkey_check() call
1833 *
1834 * We don't pass a real downlink, but we've to finish the level
1835 * processing. If condition is satisfied, we've already processed all the
1836 * downlinks from the target level. But there still might be pages to the
1837 * right of the child page pointer to by our rightmost downlink. And they
1838 * might have missing downlinks. This final call checks for them.
1839 */
1841 {
1844 }
1845}
1846
1847/*
1848 * Return a scankey for an item on page to right of current target (or the
1849 * first non-ignorable page), sufficient to check ordering invariant on last
1850 * item in current target page. Returned scankey relies on local memory
1851 * allocated for the child page, which caller cannot pfree(). Caller's memory
1852 * context should be reset between calls here.
1853 *
1854 * This is the first data item, and so all adjacent items are checked against
1855 * their immediate sibling item (which may be on a sibling page, or even a
1856 * "cousin" page at parent boundaries where target's rightlink points to page
1857 * with different parent page). If no such valid item is available, return
1858 * NULL instead.
1859 *
1860 * Note that !readonly callers must reverify that target page has not
1861 * been concurrently deleted.
1862 *
1863 * Save rightfirstoffset for detailed error message.
1864 */
1867{
1868 BTPageOpaque opaque;
1874
1875 /* Determine target's next block number */
1877
1878 /* If target is already rightmost, no right sibling; nothing to do here */
1881
1882 /*
1883 * General notes on concurrent page splits and page deletion:
1884 *
1885 * Routines like _bt_search() don't require *any* page split interlock
1886 * when descending the tree, including something very light like a buffer
1887 * pin. That's why it's okay that we don't either. This avoidance of any
1888 * need to "couple" buffer locks is the raison d' etre of the Lehman & Yao
1889 * algorithm, in fact.
1890 *
1891 * That leaves deletion. A deleted page won't actually be recycled by
1892 * VACUUM early enough for us to fail to at least follow its right link
1893 * (or left link, or downlink) and find its sibling, because recycling
1894 * does not occur until no possible index scan could land on the page.
1895 * Index scans can follow links with nothing more than their snapshot as
1896 * an interlock and be sure of at least that much. (See page
1897 * recycling/"visible to everyone" notes in nbtree README.)
1898 *
1899 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
1900 * dead (ignorable) page one or more times. There will either be a
1901 * further right link to follow that leads to a live page before too long
1902 * (before passing by parent's rightmost child), or we will find the end
1903 * of the entire level instead (possible when parent page is itself the
1904 * rightmost on its level).
1905 */
1907 for (;;)
1908 {
1909 CHECK_FOR_INTERRUPTS();
1910
1913
1915 break;
1916
1917 /*
1918 * We landed on a deleted or half-dead sibling page. Step right until
1919 * we locate a live sibling page.
1920 */
1923 errmsg_internal("level %u sibling page in block %u of index \"%s\" was found deleted or half dead",
1926
1928
1929 /* Be slightly more pro-active in freeing this memory, just in case */
1931 }
1932
1933 /*
1934 * No ShareLock held case -- why it's safe to proceed.
1935 *
1936 * Problem:
1937 *
1938 * We must avoid false positive reports of corruption when caller treats
1939 * item returned here as an upper bound on target's last item. In
1940 * general, false positives are disallowed. Avoiding them here when
1941 * caller is !readonly is subtle.
1942 *
1943 * A concurrent page deletion by VACUUM of the target page can result in
1944 * the insertion of items on to this right sibling page that would
1945 * previously have been inserted on our target page. There might have
1946 * been insertions that followed the target's downlink after it was made
1947 * to point to right sibling instead of target by page deletion's first
1948 * phase. The inserters insert items that would belong on target page.
1949 * This race is very tight, but it's possible. This is our only problem.
1950 *
1951 * Non-problems:
1952 *
1953 * We are not hindered by a concurrent page split of the target; we'll
1954 * never land on the second half of the page anyway. A concurrent split
1955 * of the right page will also not matter, because the first data item
1956 * remains the same within the left half, which we'll reliably land on. If
1957 * we had to skip over ignorable/deleted pages, it cannot matter because
1958 * their key space has already been atomically merged with the first
1959 * non-ignorable page we eventually find (doesn't matter whether the page
1960 * we eventually find is a true sibling or a cousin of target, which we go
1961 * into below).
1962 *
1963 * Solution:
1964 *
1965 * Caller knows that it should reverify that target is not ignorable
1966 * (half-dead or deleted) when cross-page sibling item comparison appears
1967 * to indicate corruption (invariant fails). This detects the single race
1968 * condition that exists for caller. This is correct because the
1969 * continued existence of target block as non-ignorable (not half-dead or
1970 * deleted) implies that target page was not merged into from the right by
1971 * deletion; the key space at or after target never moved left. Target's
1972 * parent either has the same downlink to target as before, or a <
1973 * downlink due to deletion at the left of target. Target either has the
1974 * same highkey as before, or a highkey < before when there is a page
1975 * split. (The rightmost concurrently-split-from-target-page page will
1976 * still have the same highkey as target was originally found to have,
1977 * which for our purposes is equivalent to target's highkey itself never
1978 * changing, since we reliably skip over
1979 * concurrently-split-from-target-page pages.)
1980 *
1981 * In simpler terms, we allow that the key space of the target may expand
1982 * left (the key space can move left on the left side of target only), but
1983 * the target key space cannot expand right and get ahead of us without
1984 * our detecting it. The key space of the target cannot shrink, unless it
1985 * shrinks to zero due to the deletion of the original page, our canary
1986 * condition. (To be very precise, we're a bit stricter than that because
1987 * it might just have been that the target page split and only the
1988 * original target page was deleted. We can be more strict, just not more
1989 * lax.)
1990 *
1991 * Top level tree walk caller moves on to next page (makes it the new
1992 * target) following recovery from this race. (cf. The rationale for
1993 * child/downlink verification needing a ShareLock within
1994 * bt_child_check(), where page deletion is also the main source of
1995 * trouble.)
1996 *
1997 * Note that it doesn't matter if right sibling page here is actually a
1998 * cousin page, because in order for the key space to be readjusted in a
1999 * way that causes us issues in next level up (guiding problematic
2000 * concurrent insertions to the cousin from the grandparent rather than to
2001 * the sibling from the parent), there'd have to be page deletion of
2002 * target's parent page (affecting target's parent's downlink in target's
2003 * grandparent page). Internal page deletion only occurs when there are
2004 * no child pages (they were all fully deleted), and caller is checking
2005 * that the target's parent has at least one non-deleted (so
2006 * non-ignorable) child: the target page. (Note that the first phase of
2007 * deletion atomically marks the page to be deleted half-dead/ignorable at
2008 * the same time downlink in its parent is removed, so caller will
2009 * definitely not fail to detect that this happened.)
2010 *
2011 * This trick is inspired by the method backward scans use for dealing
2012 * with concurrent page splits; concurrent page deletion is a problem that
2013 * similarly receives special consideration sometimes (it's possible that
2014 * the backwards scan will re-read its "original" block after failing to
2015 * find a right-link to it, having already moved in the opposite direction
2016 * (right/"forwards") a few times to try to locate one). Just like us,
2017 * that happens only to determine if there was a concurrent page deletion
2018 * of a reference page, and just like us if there was a page deletion of
2019 * that reference page it means we can move on from caring about the
2020 * reference page. See the nbtree README for a full description of how
2021 * that works.
2022 */
2024
2025 /*
2026 * Get first data item, if any
2027 */
2029 {
2030 /* Return first data item (if any) */
2032 P_FIRSTDATAKEY(opaque));
2034 }
2037 {
2038 /*
2039 * Return first item after the internal page's "negative infinity"
2040 * item
2041 */
2044 }
2045 else
2046 {
2047 /*
2048 * No first item. Page is probably empty leaf page, but it's also
2049 * possible that it's an internal page with only a negative infinity
2050 * item.
2051 */
2058 }
2059
2060 /*
2061 * Return first real item scankey. Note that this relies on right page
2062 * memory remaining allocated.
2063 */
2066}
2067
2068/*
2069 * Check if two tuples are binary identical except the block number. So,
2070 * this function is capable to compare pivot keys on different levels.
2071 */
2072static bool
2074{
2076 return false;
2077
2078 if (heapkeyspace)
2079 {
2080 /*
2081 * Offset number will contain important information in heapkeyspace
2082 * indexes: the number of attributes left in the pivot tuple following
2083 * suffix truncation. Don't skip over it (compare it too).
2084 */
2088 return false;
2089 }
2090 else
2091 {
2092 /*
2093 * Cannot rely on offset number field having consistent value across
2094 * levels on pg_upgrade'd !heapkeyspace indexes. Compare contents of
2095 * tuple starting from just after item pointer (i.e. after block
2096 * number and offset number).
2097 */
2101 return false;
2102 }
2103
2104 return true;
2105}
2106
2107/*---
2108 * Check high keys on the child level. Traverse rightlinks from previous
2109 * downlink to the current one. Check that there are no intermediate pages
2110 * with missing downlinks.
2111 *
2112 * If 'loaded_child' is given, it's assumed to be the page pointed to by the
2113 * downlink referenced by 'downlinkoffnum' of the target page.
2114 *
2115 * Basically this function is called for each target downlink and checks two
2116 * invariants:
2117 *
2118 * 1) You can reach the next child from previous one via rightlinks;
2119 * 2) Each child high key have matching pivot key on target level.
2120 *
2121 * Consider the sample tree picture.
2122 *
2123 * 1
2124 * / \
2125 * 2 <-> 3
2126 * / \ / \
2127 * 4 <> 5 <> 6 <> 7 <> 8
2128 *
2129 * This function will be called for blocks 4, 5, 6 and 8. Consider what is
2130 * happening for each function call.
2131 *
2132 * - The function call for block 4 initializes data structure and matches high
2133 * key of block 4 to downlink's pivot key of block 2.
2134 * - The high key of block 5 is matched to the high key of block 2.
2135 * - The block 6 has an incomplete split flag set, so its high key isn't
2136 * matched to anything.
2137 * - The function call for block 8 checks that block 8 can be found while
2138 * following rightlinks from block 6. The high key of block 7 will be
2139 * matched to downlink's pivot key in block 3.
2140 *
2141 * There is also final call of this function, which checks that there is no
2142 * missing downlinks for children to the right of the child referenced by
2143 * rightmost downlink in target level.
2144 */
2145static void
2150{
2152 Page page;
2153 BTPageOpaque opaque;
2155 bool first = true;
2156 ItemId itemid;
2157 IndexTuple itup;
2158 BlockNumber downlink;
2159
2161 {
2165 downlink = BTreeTupleGetDownLink(itup);
2166 }
2167 else
2168 {
2169 downlink = P_NONE;
2170 }
2171
2172 /*
2173 * If no previous rightlink is memorized for current level just below
2174 * target page's level, we are about to start from the leftmost page. We
2175 * can't follow rightlinks from previous page, because there is no
2176 * previous page. But we still can match high key.
2177 *
2178 * So we initialize variables for the loop above like there is previous
2179 * page referencing current child. Also we imply previous page to not
2180 * have incomplete split flag, that would make us require downlink for
2181 * current child. That's correct, because leftmost page on the level
2182 * should always have parent downlink.
2183 */
2185 {
2186 blkno = downlink;
2188 }
2189
2190 /* Move to the right on the child level */
2191 while (true)
2192 {
2193 /*
2194 * Did we traverse the whole tree level and this is check for pages to
2195 * the right of rightmost downlink?
2196 */
2198 {
2201 return;
2202 }
2203
2204 /* Did we traverse the whole tree level and don't find next downlink? */
2209 state->prevrightlink, downlink,
2211
2212 /* Load page contents */
2214 page = loaded_child;
2215 else
2217
2218 opaque = BTPageGetOpaque(page);
2219
2220 /* The first page we visit at the level should be leftmost */
2228 state->targetblock, blkno,
2230
2231 /* Do level sanity check */
2240
2241 /* Try to detect circular links */
2247
2249 {
2250 /* blkno probably has missing parent downlink */
2252 }
2253
2255
2256 /*
2257 * If we visit page with high key, check that it is equal to the
2258 * target key next to corresponding downlink.
2259 */
2261 {
2265
2266 /* Get high key */
2269
2270 /*
2271 * There might be two situations when we examine high key. If
2272 * current child page is referenced by given target downlink, we
2273 * should look to the next offset number for matching key from
2274 * target page.
2275 *
2276 * Alternatively, we're following rightlinks somewhere in the
2277 * middle between page referenced by previous target's downlink
2278 * and the page referenced by current target's downlink. If
2279 * current child page hasn't incomplete split flag set, then its
2280 * high key should match to the target's key of current offset
2281 * number. This happens when a previous call here (to
2282 * bt_child_highkey_check()) found an incomplete split, and we
2283 * reach a right sibling page without a downlink -- the right
2284 * sibling page's high key still needs to be matched to a
2285 * separator key on the parent/target level.
2286 *
2287 * Don't apply OffsetNumberNext() to target_downlinkoffnum when we
2288 * already had to step right on the child level. Our traversal of
2289 * the child level must try to move in perfect lockstep behind (to
2290 * the left of) the target/parent level traversal.
2291 */
2292 if (blkno == downlink)
2294 else
2296
2298
2300 {
2301 /*
2302 * If we're looking for the next pivot tuple in target page,
2303 * but there is no more pivot tuples, then we should match to
2304 * high key instead.
2305 */
2307 {
2314 state->targetblock, blkno,
2317 }
2321 }
2322 else
2323 {
2324 /*
2325 * We cannot try to match child's high key to a negative
2326 * infinity key in target, since there is nothing to compare.
2327 * However, it's still possible to match child's high key
2328 * outside of target page. The reason why we're are is that
2329 * bt_child_highkey_check() was previously called for the
2330 * cousin page of 'loaded_child', which is incomplete split.
2331 * So, now we traverse to the right of that cousin page and
2332 * current child level page under consideration still belongs
2333 * to the subtree of target's left sibling. Thus, we need to
2334 * match child's high key to its left uncle page high key.
2335 * Thankfully we saved it, it's called a "low key" of target
2336 * page.
2337 */
2344 state->targetblock, blkno,
2346 itup = state->lowkey;
2347 }
2348
2350 {
2356 state->targetblock, blkno,
2358 }
2359 }
2360
2361 /* Exit if we already found next downlink */
2362 if (blkno == downlink)
2363 {
2366 return;
2367 }
2368
2369 /* Traverse to the next page using rightlink */
2370 blkno = opaque->btpo_next;
2371
2372 /* Free page contents if it's allocated by us */
2374 pfree(page);
2375 first = false;
2376 }
2377}
2378
2379/*
2380 * Checks one of target's downlink against its child page.
2381 *
2382 * Conceptually, the target page continues to be what is checked here. The
2383 * target block is still blamed in the event of finding an invariant violation.
2384 * The downlink insertion into the target is probably where any problem raised
2385 * here arises, and there is no such thing as a parent link, so doing the
2386 * verification this way around is much more practical.
2387 *
2388 * This function visits child page and it's sequentially called for each
2389 * downlink of target page. Assuming this we also check downlink connectivity
2390 * here in order to save child page visits.
2391 */
2392static void
2394 OffsetNumber downlinkoffnum)
2395{
2396 ItemId itemid;
2397 IndexTuple itup;
2399 OffsetNumber offset;
2401 Page child;
2404
2406 state->target, downlinkoffnum);
2409
2410 /*
2411 * Caller must have ShareLock on target relation, because of
2412 * considerations around page deletion by VACUUM.
2413 *
2414 * NB: In general, page deletion deletes the right sibling's downlink, not
2415 * the downlink of the page being deleted; the deleted page's downlink is
2416 * reused for its sibling. The key space is thereby consolidated between
2417 * the deleted page and its right sibling. (We cannot delete a parent
2418 * page's rightmost child unless it is the last child page, and we intend
2419 * to also delete the parent itself.)
2420 *
2421 * If this verification happened without a ShareLock, the following race
2422 * condition could cause false positives:
2423 *
2424 * In general, concurrent page deletion might occur, including deletion of
2425 * the left sibling of the child page that is examined here. If such a
2426 * page deletion were to occur, closely followed by an insertion into the
2427 * newly expanded key space of the child, a window for the false positive
2428 * opens up: the stale parent/target downlink originally followed to get
2429 * to the child legitimately ceases to be a lower bound on all items in
2430 * the page, since the key space was concurrently expanded "left".
2431 * (Insertion followed the "new" downlink for the child, not our now-stale
2432 * downlink, which was concurrently physically removed in target/parent as
2433 * part of deletion's first phase.)
2434 *
2435 * While we use various techniques elsewhere to perform cross-page
2436 * verification for !readonly callers, a similar trick seems difficult
2437 * here. The tricks used by bt_recheck_sibling_links and by
2438 * bt_right_page_check_scankey both involve verification of a same-level,
2439 * cross-sibling invariant. Cross-level invariants are far more squishy,
2440 * though. The nbtree REDO routines do not actually couple buffer locks
2441 * across levels during page splits, so making any cross-level check work
2442 * reliably in !readonly mode may be impossible.
2443 */
2445
2446 /*
2447 * Verify child page has the downlink key from target page (its parent) as
2448 * a lower bound; downlink must be strictly less than all keys on the
2449 * page.
2450 *
2451 * Check all items, rather than checking just the first and trusting that
2452 * the operator class obeys the transitive law.
2453 */
2458
2459 /*
2460 * Since we've already loaded the child block, combine this check with
2461 * check for downlink connectivity.
2462 */
2464 child, topaque->btpo_level);
2465
2466 /*
2467 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2468 * and since a page has no links within other pages (siblings and parent)
2469 * once it is marked fully deleted, it should be impossible to land on a
2470 * fully deleted page.
2471 *
2472 * It does not quite make sense to enforce that the page cannot even be
2473 * half-dead, despite the fact the downlink is modified at the same stage
2474 * that the child leaf page is marked half-dead. That's incorrect because
2475 * there may occasionally be multiple downlinks from a chain of pages
2476 * undergoing deletion, where multiple successive calls are made to
2477 * _bt_unlink_halfdead_page() by VACUUM before it can finally safely mark
2478 * the leaf page as fully dead. While _bt_mark_page_halfdead() usually
2479 * removes the downlink to the leaf page that is marked half-dead, that's
2480 * not guaranteed, so it's possible we'll land on a half-dead page with a
2481 * downlink due to an interrupted multi-level page deletion.
2482 *
2483 * We go ahead with our checks if the child page is half-dead. It's safe
2484 * to do so because we do not test the child's high key, so it does not
2485 * matter that the original high key will have been replaced by a dummy
2486 * truncated high key within _bt_mark_page_halfdead(). All other page
2487 * items are left intact on a half-dead page, so there is still something
2488 * to test.
2489 */
2498
2500 offset <= maxoffset;
2501 offset = OffsetNumberNext(offset))
2502 {
2503 /*
2504 * Skip comparison of target page key against "negative infinity"
2505 * item, if any. Checking it would indicate that it's not a strict
2506 * lower bound, but that's only because of the hard-coding for
2507 * negative infinity items within _bt_compare().
2508 *
2509 * If nbtree didn't truncate negative infinity tuples during internal
2510 * page splits then we'd expect child's negative infinity key to be
2511 * equal to the scankey/downlink from target/parent (it would be a
2512 * "low key" in this hypothetical scenario, and so it would still need
2513 * to be treated as a special case here).
2514 *
2515 * Negative infinity items can be thought of as a strict lower bound
2516 * that works transitively, with the last non-negative-infinity pivot
2517 * followed during a descent from the root as its "true" strict lower
2518 * bound. Only a small number of negative infinity items are truly
2519 * negative infinity; those that are the first items of leftmost
2520 * internal pages. In more general terms, a negative infinity item is
2521 * only negative infinity with respect to the subtree that the page is
2522 * at the root of.
2523 *
2524 * See also: bt_rootdescend(), which can even detect transitive
2525 * inconsistencies on cousin leaf pages.
2526 */
2528 continue;
2529
2531 offset))
2539 }
2540
2541 pfree(child);
2542}
2543
2544/*
2545 * Checks if page is missing a downlink that it should have.
2546 *
2547 * A page that lacks a downlink/parent may indicate corruption. However, we
2548 * must account for the fact that a missing downlink can occasionally be
2549 * encountered in a non-corrupt index. This can be due to an interrupted page
2550 * split, or an interrupted multi-level page deletion (i.e. there was a hard
2551 * crash or an error during a page split, or while VACUUM was deleting a
2552 * multi-level chain of pages).
2553 *
2554 * Note that this can only be called in readonly mode, so there is no need to
2555 * be concerned about concurrent page splits or page deletions.
2556 */
2557static void
2560{
2562 ItemId itemid;
2563 IndexTuple itup;
2564 Page child;
2566 uint32 level;
2569
2572
2573 /* No next level up with downlinks to fingerprint from the true root */
2575 return;
2576
2578
2579 /*
2580 * Incomplete (interrupted) page splits can account for the lack of a
2581 * downlink. Some inserting transaction should eventually complete the
2582 * page split in passing, when it notices that the left sibling page is
2583 * P_INCOMPLETE_SPLIT().
2584 *
2585 * In general, VACUUM is not prepared for there to be no downlink to a
2586 * page that it deletes. This is the main reason why the lack of a
2587 * downlink can be reported as corruption here. It's not obvious that an
2588 * invalid missing downlink can result in wrong answers to queries,
2589 * though, since index scans that land on the child may end up
2590 * consistently moving right. The handling of concurrent page splits (and
2591 * page deletions) within _bt_moveright() cannot distinguish
2592 * inconsistencies that last for a moment from inconsistencies that are
2593 * permanent and irrecoverable.
2594 *
2595 * VACUUM isn't even prepared to delete pages that have no downlink due to
2596 * an incomplete page split, but it can detect and reason about that case
2597 * by design, so it shouldn't be taken to indicate corruption. See
2598 * _bt_pagedel() for full details.
2599 */
2601 {
2607 blkno, opaque->btpo_level,
2608 opaque->btpo_prev,
2610 return;
2611 }
2612
2613 /*
2614 * Page under check is probably the "top parent" of a multi-level page
2615 * deletion. We'll need to descend the subtree to make sure that
2616 * descendant pages are consistent with that, though.
2617 *
2618 * If the page (which must be non-ignorable) is a leaf page, then clearly
2619 * it can't be the top parent. The lack of a downlink is probably a
2620 * symptom of a broad problem that could just as easily cause
2621 * inconsistencies anywhere else.
2622 */
2629 blkno,
2631
2632 /* Descend from the given page, which is an internal page */
2633 elog(DEBUG1, "checking for interrupted multi-level deletion due to missing downlink in index \"%s\"",
2635
2636 level = opaque->btpo_level;
2640 for (;;)
2641 {
2642 CHECK_FOR_INTERRUPTS();
2643
2646
2648 break;
2649
2650 /* Do an extra sanity check in passing on internal pages */
2656 errdetail_internal("Top parent/under check block=%u block pointed to=%u expected level=%u level in pointed to block=%u.",
2657 blkno, childblk,
2658 level - 1, copaque->btpo_level)));
2659
2660 level = copaque->btpo_level;
2665 /* Be slightly more pro-active in freeing this memory, just in case */
2666 pfree(child);
2667 }
2668
2669 /*
2670 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2671 * and since a page has no links within other pages (siblings and parent)
2672 * once it is marked fully deleted, it should be impossible to land on a
2673 * fully deleted page. See bt_child_check() for further details.
2674 *
2675 * The bt_child_check() P_ISDELETED() check is repeated here because
2676 * bt_child_check() does not visit pages reachable through negative
2677 * infinity items. Besides, bt_child_check() is unwilling to descend
2678 * multiple levels. (The similar bt_child_check() P_ISDELETED() check
2679 * within bt_check_level_from_leftmost() won't reach the page either,
2680 * since the leaf's live siblings should have their sibling links updated
2681 * to bypass the deletion target page when it is marked fully dead.)
2682 *
2683 * If this error is raised, it might be due to a previous multi-level page
2684 * deletion that failed to realize that it wasn't yet safe to mark the
2685 * leaf page as fully dead. A "dangling downlink" will still remain when
2686 * this happens. The fact that the dangling downlink's page (the leaf's
2687 * parent/ancestor page) lacked a downlink is incidental.
2688 */
2694 errdetail_internal("Top parent/target block=%u leaf block=%u top parent/under check lsn=%X/%08X.",
2695 blkno, childblk,
2697
2698 /*
2699 * Iff leaf page is half-dead, its high key top parent link should point
2700 * to what VACUUM considered to be the top parent page at the instant it
2701 * was interrupted. Provided the high key link actually points to the
2702 * page under check, the missing downlink we detected is consistent with
2703 * there having been an interrupted multi-level page deletion. This means
2704 * that the subtree with the page under check at its root (a page deletion
2705 * chain) is in a consistent state, enabling VACUUM to resume deleting the
2706 * entire chain the next time it encounters the half-dead leaf page.
2707 */
2709 {
2713 return;
2714 }
2715
2721 blkno, opaque->btpo_level,
2723}
2724
2725/*
2726 * Per-tuple callback from table_index_build_scan, used to determine if index has
2727 * all the entries that definitely should have been observed in leaf pages of
2728 * the target index (that is, all IndexTuples that were fingerprinted by our
2729 * Bloom filter). All heapallindexed checks occur here.
2730 *
2731 * The redundancy between an index and the table it indexes provides a good
2732 * opportunity to detect corruption, especially corruption within the table.
2733 * The high level principle behind the verification performed here is that any
2734 * IndexTuple that should be in an index following a fresh CREATE INDEX (based
2735 * on the same index definition) should also have been in the original,
2736 * existing index, which should have used exactly the same representation
2737 *
2738 * Since the overall structure of the index has already been verified, the most
2739 * likely explanation for error here is a corrupt heap page (could be logical
2740 * or physical corruption). Index corruption may still be detected here,
2741 * though. Only readonly callers will have verified that left links and right
2742 * links are in agreement, and so it's possible that a leaf page transposition
2743 * within index is actually the source of corruption detected here (for
2744 * !readonly callers). The checks performed only for readonly callers might
2745 * more accurately frame the problem as a cross-page invariant issue (this
2746 * could even be due to recovery not replaying all WAL records). The !readonly
2747 * ERROR message raised here includes a HINT about retrying with readonly
2748 * verification, just in case it's a cross-page invariant issue, though that
2749 * isn't particularly likely.
2750 *
2751 * table_index_build_scan() expects to be able to find the root tuple when a
2752 * heap-only tuple (the live tuple at the end of some HOT chain) needs to be
2753 * indexed, in order to replace the actual tuple's TID with the root tuple's
2754 * TID (which is what we're actually passed back here). The index build heap
2755 * scan code will raise an error when a tuple that claims to be the root of the
2756 * heap-only tuple's HOT chain cannot be located. This catches cases where the
2757 * original root item offset/root tuple for a HOT chain indicates (for whatever
2758 * reason) that the entire HOT chain is dead, despite the fact that the latest
2759 * heap-only tuple should be indexed. When this happens, sequential scans may
2760 * always give correct answers, and all indexes may be considered structurally
2761 * consistent (i.e. the nbtree structural checks would not detect corruption).
2762 * It may be the case that only index scans give wrong answers, and yet heap or
2763 * SLRU corruption is the real culprit. (While it's true that LP_DEAD bit
2764 * setting will probably also leave the index in a corrupt state before too
2765 * long, the problem is nonetheless that there is heap corruption.)
2766 *
2767 * Heap-only tuple handling within table_index_build_scan() works in a way that
2768 * helps us to detect index tuples that contain the wrong values (values that
2769 * don't match the latest tuple in the HOT chain). This can happen when there
2770 * is no superseding index tuple due to a faulty assessment of HOT safety,
2771 * perhaps during the original CREATE INDEX. Because the latest tuple's
2772 * contents are used with the root TID, an error will be raised when a tuple
2773 * with the same TID but non-matching attribute values is passed back to us.
2774 * Faulty assessment of HOT-safety was behind at least two distinct CREATE
2775 * INDEX CONCURRENTLY bugs that made it into stable releases, one of which was
2776 * undetected for many years. In short, the same principle that allows a
2777 * REINDEX to repair corruption when there was an (undetected) broken HOT chain
2778 * also allows us to detect the corruption in many cases.
2779 */
2780static void
2783{
2785 IndexTuple itup,
2786 norm;
2787
2789
2790 /* Generate a normalized index tuple for fingerprinting */
2792 itup->t_tid = *tid;
2794
2795 /* Probe Bloom filter -- tuple should be present */
2805 !state->readonly
2806 ? errhint("Retrying verification using the function bt_index_parent_check() might provide a more specific error.")
2807 : 0));
2808
2809 state->heaptuplespresent++;
2810 pfree(itup);
2811 /* Cannot leak memory here */
2814}
2815
2816/*
2817 * Normalize an index tuple for fingerprinting.
2818 *
2819 * In general, index tuple formation is assumed to be deterministic by
2820 * heapallindexed verification, and IndexTuples are assumed immutable. While
2821 * the LP_DEAD bit is mutable in leaf pages, that's ItemId metadata, which is
2822 * not fingerprinted. Normalization is required to compensate for corner
2823 * cases where the determinism assumption doesn't quite work.
2824 *
2825 * There is currently one such case: index_form_tuple() does not try to hide
2826 * the source TOAST state of input datums. The executor applies TOAST
2827 * compression for heap tuples based on different criteria to the compression
2828 * applied within btinsert()'s call to index_form_tuple(): it sometimes
2829 * compresses more aggressively, resulting in compressed heap tuple datums but
2830 * uncompressed corresponding index tuple datums. A subsequent heapallindexed
2831 * verification will get a logically equivalent though bitwise unequal tuple
2832 * from index_form_tuple(). False positive heapallindexed corruption reports
2833 * could occur without normalizing away the inconsistency.
2834 *
2835 * Returned tuple is often caller's own original tuple. Otherwise, it is a
2836 * new representation of caller's original index tuple, palloc()'d in caller's
2837 * memory context.
2838 *
2839 * Note: This routine is not concerned with distinctions about the
2840 * representation of tuples beyond those that might break heapallindexed
2841 * verification. In particular, it won't try to normalize opclass-equal
2842 * datums with potentially distinct representations (e.g., btree/numeric_ops
2843 * index datums will not get their display scale normalized-away here).
2844 * Caller does normalization for non-pivot tuples that have a posting list,
2845 * since dummy CREATE INDEX callback code generates new tuples with the same
2846 * normalized representation.
2847 */
2850{
2858
2859 /* Caller should only pass "logical" non-pivot tuples here */
2861
2862 /* Easy case: It's immediately clear that tuple has no varlena datums */
2864 return itup;
2865
2867 {
2868 Form_pg_attribute att;
2869
2871
2872 /* Assume untoasted/already normalized datum initially */
2875 tupleDescriptor,
2876 &isnull[i]);
2878 continue;
2879
2880 /*
2881 * Callers always pass a tuple that could safely be inserted into the
2882 * index without further processing, so an external varlena header
2883 * should never be encountered here
2884 */
2894 (att->attstorage == TYPSTORAGE_EXTENDED ||
2895 att->attstorage == TYPSTORAGE_MAIN))
2896 {
2897 /*
2898 * This value will be compressed by index_form_tuple() with the
2899 * current storage settings. We may be here because this tuple
2900 * was formed with different storage settings. So, force forming.
2901 */
2903 }
2905 {
2909 }
2910
2911 /*
2912 * Short tuples may have 1B or 4B header. Convert 4B header of short
2913 * tuples to 1B
2914 */
2916 {
2917 /* convert to short varlena */
2920
2923
2927 }
2928 }
2929
2930 /*
2931 * Easier case: Tuple has varlena datums, none of which are compressed or
2932 * short with 4B header
2933 */
2935 return itup;
2936
2937 /*
2938 * Hard case: Tuple had compressed varlena datums that necessitate
2939 * creating normalized version of the tuple from uncompressed input datums
2940 * (normalized input datums). This is rather naive, but shouldn't be
2941 * necessary too often.
2942 *
2943 * In the heap, tuples may contain short varlena datums with both 1B
2944 * header and 4B headers. But the corresponding index tuple should always
2945 * have such varlena's with 1B headers. So, if there is a short varlena
2946 * with 4B header, we need to convert it for fingerprinting.
2947 *
2948 * Note that we rely on deterministic index_form_tuple() TOAST compression
2949 * of normalized input.
2950 */
2953
2954 /* Cannot leak memory here */
2958
2960}
2961
2962/*
2963 * Produce palloc()'d "plain" tuple for nth posting list entry/TID.
2964 *
2965 * In general, deduplication is not supposed to change the logical contents of
2966 * an index. Multiple index tuples are merged together into one equivalent
2967 * posting list index tuple when convenient.
2968 *
2969 * heapallindexed verification must normalize-away this variation in
2970 * representation by converting posting list tuples into two or more "plain"
2971 * tuples. Each tuple must be fingerprinted separately -- there must be one
2972 * tuple for each corresponding Bloom filter probe during the heap scan.
2973 *
2974 * Note: Caller still needs to call bt_normalize_tuple() with returned tuple.
2975 */
2978{
2980
2981 /* Returns non-posting-list tuple */
2983}
2984
2985/*
2986 * Search for itup in index, starting from fast root page. itup must be a
2987 * non-pivot tuple. This is only supported with heapkeyspace indexes, since
2988 * we rely on having fully unique keys to find a match with only a single
2989 * visit to a leaf page, barring an interrupted page split, where we may have
2990 * to move right. (A concurrent page split is impossible because caller must
2991 * be readonly caller.)
2992 *
2993 * This routine can detect very subtle transitive consistency issues across
2994 * more than one level of the tree. Leaf pages all have a high key (even the
2995 * rightmost page has a conceptual positive infinity high key), but not a low
2996 * key. Their downlink in parent is a lower bound, which along with the high
2997 * key is almost enough to detect every possible inconsistency. A downlink
2998 * separator key value won't always be available from parent, though, because
2999 * the first items of internal pages are negative infinity items, truncated
3000 * down to zero attributes during internal page splits. While it's true that
3001 * bt_child_check() and the high key check can detect most imaginable key
3002 * space problems, there are remaining problems it won't detect with non-pivot
3003 * tuples in cousin leaf pages. Starting a search from the root for every
3004 * existing leaf tuple detects small inconsistencies in upper levels of the
3005 * tree that cannot be detected any other way. (Besides all this, this is
3006 * probably also useful as a direct test of the code used by index scans
3007 * themselves.)
3008 */
3009static bool
3011{
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 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:926
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition bufpage.h:268
static void * PageGetItem(PageData *page, const ItemIdData *itemId)
Definition bufpage.h:378
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
Definition bufpage.h:396
memcpy(sums, checksumBaseOffsets, sizeof(checksumBaseOffsets))
int int errdetail_internal(const char *fmt,...) pg_attribute_printf(1
int errhint(const char *fmt,...) pg_attribute_printf(1
int errdetail(const char *fmt,...) pg_attribute_printf(1
int int errmsg_internal(const char *fmt,...) pg_attribute_printf(1
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition execTuples.c:1520
BufferAccessStrategy GetAccessStrategy(BufferAccessStrategyType btype)
Definition freelist.c:426
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:864
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
Definition nbtpage.c:744
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
OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
Definition nbtsearch.c:475
int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum)
Definition nbtsearch.c:689
BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access, bool returnstack)
Definition nbtsearch.c:100
bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
Definition nbtutils.c:958
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition palloc.h:138
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition rel.h:535
Definition verify_nbtree.c:169
Definition nbtree.h:821
Definition nbtree.h:105
Definition nbtree.h:64
Definition nbtree.h:796
Definition verify_nbtree.c:71
Definition verify_nbtree.c:157
Definition verify_nbtree.c:141
Definition freelist.c:75
Definition execnodes.h:177
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:34
Definition tupdesc.h:149
Definition tuptable.h:121
Definition bloomfilter.c:45
Definition regguts.h:331
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:1845
static TableScanDesc table_beginscan_strat(Relation rel, Snapshot snapshot, int nkeys, ScanKeyData *key, bool allow_strat, bool allow_sync)
Definition tableam.h:968
static bool table_tuple_fetch_row_version(Relation rel, ItemPointer tid, Snapshot snapshot, TupleTableSlot *slot)
Definition tableam.h:1344
static bool TransactionIdPrecedes(TransactionId id1, TransactionId id2)
Definition transam.h:263
static FormData_pg_attribute * TupleDescAttr(TupleDesc tupdesc, int i)
Definition tupdesc.h:178
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:1012
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:2978
static void bt_target_page_check(BtreeCheckState *state)
Definition verify_nbtree.c:1241
static void bt_check_every_level(Relation rel, Relation heaprel, bool heapkeyspace, bool readonly, bool heapallindexed, bool rootdescend, bool checkunique)
Definition verify_nbtree.c:380
static void bt_report_duplicate(BtreeCheckState *state, BtreeLastVisibleEntry *lVis, ItemPointer nexttid, BlockNumber nblock, OffsetNumber noffset, int nposting)
Definition verify_nbtree.c:873
static bool bt_pivot_tuple_identical(bool heapkeyspace, IndexTuple itup1, IndexTuple itup2)
Definition verify_nbtree.c:2074
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:2147
static bool heap_entry_is_visible(BtreeCheckState *state, ItemPointer tid)
Definition verify_nbtree.c:854
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:626
static void bt_downlink_missing_check(BtreeCheckState *state, bool rightsplit, BlockNumber blkno, Page page)
Definition verify_nbtree.c:2559
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:2782
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:3011
static BTScanInsert bt_right_page_check_scankey(BtreeCheckState *state, OffsetNumber *rightfirstoffset)
Definition verify_nbtree.c:1867
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:2850
static void bt_recheck_sibling_links(BtreeCheckState *state, BlockNumber btpo_prev_from_target, BlockNumber leftcurrent)
Definition verify_nbtree.c:1101
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:2394
static void bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup, BlockNumber targetblock, OffsetNumber offset, BtreeLastVisibleEntry *lVis)
Definition verify_nbtree.c:913
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
| typedef struct BtreeLevel BtreeLevel |
Function Documentation
◆ bt_check_every_level()
|
static |
Definition at line 380 of file verify_nbtree.c.
383{
388 BtreeLevel current;
389
390 if (!readonly)
392 RelationGetRelationName(rel));
393 else
394 elog(DEBUG1, "verifying consistency of tree structure for index \"%s\" with cross-level checks",
395 RelationGetRelationName(rel));
396
397 /*
398 * This assertion matches the one in index_getnext_tid(). See page
399 * recycling/"visible to everyone" notes in nbtree README.
400 */
402
403 /*
404 * Initialize state for entire verification operation
405 */
407 state->rel = rel;
408 state->heaprel = heaprel;
409 state->heapkeyspace = heapkeyspace;
410 state->readonly = readonly;
411 state->heapallindexed = heapallindexed;
412 state->rootdescend = rootdescend;
413 state->checkunique = checkunique;
415
417 {
420 uint64 seed;
421
422 /*
423 * Size Bloom filter based on estimated number of tuples in index,
424 * while conservatively assuming that each block must contain at least
425 * MaxTIDsPerBTreePage / 3 "plain" tuples -- see
426 * bt_posting_plain_tuple() for definition, and details of how posting
427 * list tuples are handled.
428 */
432 /* Generate a random seed to avoid repetition */
434 /* Create Bloom filter to fingerprint index */
436 state->heaptuplespresent = 0;
437
438 /*
439 * Register our own snapshot for heapallindexed, rather than asking
440 * table_index_build_scan() to do this for us later. This needs to
441 * happen before index fingerprinting begins, so we can later be
442 * certain that index fingerprinting should have reached all tuples
443 * returned by table_index_build_scan().
444 */
446
447 /*
448 * GetTransactionSnapshot() always acquires a new MVCC snapshot in
449 * READ COMMITTED mode. A new snapshot is guaranteed to have all the
450 * entries it requires in the index.
451 *
452 * We must defend against the possibility that an old xact snapshot
453 * was returned at higher isolation levels when that snapshot is not
454 * safe for index scans of the target index. This is possible when
455 * the snapshot sees tuples that are before the index's indcheckxmin
456 * horizon. Throwing an error here should be very rare. It doesn't
457 * seem worth using a secondary snapshot to avoid this.
458 */
461 state->snapshot->xmin))
465 RelationGetRelationName(rel)));
466 }
467
468 /*
469 * We need a snapshot to check the uniqueness of the index. For better
470 * performance, take it once per index check. If one was already taken
471 * above, use that.
472 */
474 {
476
479 }
480
485 errmsg("cannot verify that tuples from index \"%s\" can each be found by an independent index search",
486 RelationGetRelationName(rel)),
488
489 /* Create context for page */
491 "amcheck context",
492 ALLOCSET_DEFAULT_SIZES);
494
495 /* Get true root block from meta-page */
498
499 /*
500 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
501 * the fast root and true root differ.
502 *
503 * Start from the true root, not the fast root, unlike conventional index
504 * scans. This approach is more thorough, and removes the risk of
505 * following a stale fast root from the meta page.
506 */
511 RelationGetRelationName(rel)),
515
516 /*
517 * Starting at the root, verify every level. Move left to right, top to
518 * bottom. Note that there may be no pages other than the meta page (meta
519 * page can indicate that root is P_NONE when the index is totally empty).
520 */
526 {
527 /*
528 * Verify this level, and get left most page for next level down, if
529 * not at leaf level
530 */
532
538
540 }
541
542 /*
543 * * Check whether heap contains unindexed/malformed tuples *
544 */
546 {
548 TableScanDesc scan;
549
550 /*
551 * Create our own scan for table_index_build_scan(), rather than
552 * getting it to do so for us. This is required so that we can
553 * actually use the MVCC snapshot registered earlier.
554 *
555 * Note that table_index_build_scan() calls heap_endscan() for us.
556 */
559 0, /* number of keys */
561 true, /* buffer access strategy OK */
562 true); /* syncscan OK? */
563
564 /*
565 * Scan will behave as the first scan of a CREATE INDEX CONCURRENTLY
566 * behaves.
567 *
568 * It's okay that we don't actually use the same lock strength for the
569 * heap relation as any other ii_Concurrent caller would. We have no
570 * reason to care about a concurrent VACUUM operation, since there
571 * isn't going to be a second scan of the heap that needs to be sure
572 * that there was no concurrent recycling of TIDs.
573 */
575
576 /*
577 * Don't wait for uncommitted tuple xact commit/abort when index is a
578 * unique index on a catalog (or an index used by an exclusion
579 * constraint). This could otherwise happen in the readonly case.
580 */
585
589
592
594 (errmsg_internal("finished verifying presence of " INT64_FORMAT " tuples from table \"%s\" with bitset %.2f%% set",
597
599 }
600
601 /* Be tidy: */
605}
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 626 of file verify_nbtree.c.
627{
628 /* State to establish early, concerning entire level */
629 BTPageOpaque opaque;
630 MemoryContext oldcontext;
632
633 /* Variables for iterating across level using right links */
636
637 /* Initialize return state */
641
642 /* Use page-level context for duration of this call */
644
646 level.istruerootlevel ?
647 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
648
651
652 do
653 {
654 /* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
655 CHECK_FOR_INTERRUPTS();
656
657 /* Initialize state for this iteration */
658 state->targetblock = current;
661
663
665 {
666 /*
667 * Since there cannot be a concurrent VACUUM operation in readonly
668 * mode, and since a page has no links within other pages
669 * (siblings and parent) once it is marked fully deleted, it
670 * should be impossible to land on a fully deleted page in
671 * readonly mode. See bt_child_check() for further details.
672 *
673 * The bt_child_check() P_ISDELETED() check is repeated here so
674 * that pages that are only reachable through sibling links get
675 * checked.
676 */
684
690 else
696 }
698 {
699 /*
700 * A concurrent page split could make the caller supplied leftmost
701 * block no longer contain the leftmost page, or no longer be the
702 * true root, but where that isn't possible due to heavyweight
703 * locking, check that the first valid page meets caller's
704 * expectations.
705 */
707 {
713
719 }
720
721 /*
722 * Before beginning any non-trivial examination of level, prepare
723 * state for next bt_check_level_from_leftmost() invocation for
724 * the next level for the next level down (if any).
725 *
726 * There should be at least one non-ignorable page per level,
727 * unless this is the leaf level, which is assumed by caller to be
728 * final level.
729 */
731 {
732 IndexTuple itup;
733 ItemId itemid;
734
735 /* Internal page -- downlink gets leftmost on next level */
737 state->target,
738 P_FIRSTDATAKEY(opaque));
742 }
743 else
744 {
745 /*
746 * Leaf page -- final level caller must process.
747 *
748 * Note that this could also be the root page, if there has
749 * been no root page split yet.
750 */
753 }
754
755 /*
756 * Finished setting up state for this call/level. Control will
757 * never end up back here in any future loop iteration for this
758 * level.
759 */
760 }
761
762 /*
763 * Sibling links should be in mutual agreement. There arises
764 * leftcurrent == P_NONE && btpo_prev != P_NONE when the left sibling
765 * of the parent's low-key downlink is half-dead. (A half-dead page
766 * has no downlink from its parent.) Under heavyweight locking, the
767 * last bt_leftmost_ignoring_half_dead() validated this btpo_prev.
768 * Without heavyweight locking, validation of the P_NONE case remains
769 * unimplemented.
770 */
773
774 /* Check level */
778 errmsg("leftmost down link for level points to block in index \"%s\" whose level is not one level down",
782
783 /* Verify invariants for page */
785
786nextpage:
787
788 /* Try to detect circular links */
794
795 leftcurrent = current;
796 current = opaque->btpo_next;
797
799 {
803 }
804
805 /*
806 * Copy current target high key as the low key of right sibling.
807 * Allocate memory in upper level context, so it would be cleared
808 * after reset of target context.
809 *
810 * We only need the low key in corner cases of checking child high
811 * keys. We use high key only when incomplete split on the child level
812 * falls to the boundary of pages on the target level. See
813 * bt_child_highkey_check() for details. So, typically we won't end
814 * up doing anything with low key, but it's simpler for general case
815 * high key verification to always have it available.
816 *
817 * The correctness of managing low key in the case of concurrent
818 * splits wasn't investigated yet. Thankfully we only need low key
819 * for readonly verification and concurrent splits won't happen.
820 */
822 {
823 IndexTuple itup;
824 ItemId itemid;
825
829
832 }
833
834 /* Free page and associated memory for this iteration */
836 }
838
840 {
844 }
845
846 /* Don't change context for caller */
847 MemoryContextSwitchTo(oldcontext);
848
850}
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, memcpy(), 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 2394 of file verify_nbtree.c.
2396{
2397 ItemId itemid;
2398 IndexTuple itup;
2400 OffsetNumber offset;
2402 Page child;
2405
2407 state->target, downlinkoffnum);
2410
2411 /*
2412 * Caller must have ShareLock on target relation, because of
2413 * considerations around page deletion by VACUUM.
2414 *
2415 * NB: In general, page deletion deletes the right sibling's downlink, not
2416 * the downlink of the page being deleted; the deleted page's downlink is
2417 * reused for its sibling. The key space is thereby consolidated between
2418 * the deleted page and its right sibling. (We cannot delete a parent
2419 * page's rightmost child unless it is the last child page, and we intend
2420 * to also delete the parent itself.)
2421 *
2422 * If this verification happened without a ShareLock, the following race
2423 * condition could cause false positives:
2424 *
2425 * In general, concurrent page deletion might occur, including deletion of
2426 * the left sibling of the child page that is examined here. If such a
2427 * page deletion were to occur, closely followed by an insertion into the
2428 * newly expanded key space of the child, a window for the false positive
2429 * opens up: the stale parent/target downlink originally followed to get
2430 * to the child legitimately ceases to be a lower bound on all items in
2431 * the page, since the key space was concurrently expanded "left".
2432 * (Insertion followed the "new" downlink for the child, not our now-stale
2433 * downlink, which was concurrently physically removed in target/parent as
2434 * part of deletion's first phase.)
2435 *
2436 * While we use various techniques elsewhere to perform cross-page
2437 * verification for !readonly callers, a similar trick seems difficult
2438 * here. The tricks used by bt_recheck_sibling_links and by
2439 * bt_right_page_check_scankey both involve verification of a same-level,
2440 * cross-sibling invariant. Cross-level invariants are far more squishy,
2441 * though. The nbtree REDO routines do not actually couple buffer locks
2442 * across levels during page splits, so making any cross-level check work
2443 * reliably in !readonly mode may be impossible.
2444 */
2446
2447 /*
2448 * Verify child page has the downlink key from target page (its parent) as
2449 * a lower bound; downlink must be strictly less than all keys on the
2450 * page.
2451 *
2452 * Check all items, rather than checking just the first and trusting that
2453 * the operator class obeys the transitive law.
2454 */
2459
2460 /*
2461 * Since we've already loaded the child block, combine this check with
2462 * check for downlink connectivity.
2463 */
2465 child, topaque->btpo_level);
2466
2467 /*
2468 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2469 * and since a page has no links within other pages (siblings and parent)
2470 * once it is marked fully deleted, it should be impossible to land on a
2471 * fully deleted page.
2472 *
2473 * It does not quite make sense to enforce that the page cannot even be
2474 * half-dead, despite the fact the downlink is modified at the same stage
2475 * that the child leaf page is marked half-dead. That's incorrect because
2476 * there may occasionally be multiple downlinks from a chain of pages
2477 * undergoing deletion, where multiple successive calls are made to
2478 * _bt_unlink_halfdead_page() by VACUUM before it can finally safely mark
2479 * the leaf page as fully dead. While _bt_mark_page_halfdead() usually
2480 * removes the downlink to the leaf page that is marked half-dead, that's
2481 * not guaranteed, so it's possible we'll land on a half-dead page with a
2482 * downlink due to an interrupted multi-level page deletion.
2483 *
2484 * We go ahead with our checks if the child page is half-dead. It's safe
2485 * to do so because we do not test the child's high key, so it does not
2486 * matter that the original high key will have been replaced by a dummy
2487 * truncated high key within _bt_mark_page_halfdead(). All other page
2488 * items are left intact on a half-dead page, so there is still something
2489 * to test.
2490 */
2499
2501 offset <= maxoffset;
2502 offset = OffsetNumberNext(offset))
2503 {
2504 /*
2505 * Skip comparison of target page key against "negative infinity"
2506 * item, if any. Checking it would indicate that it's not a strict
2507 * lower bound, but that's only because of the hard-coding for
2508 * negative infinity items within _bt_compare().
2509 *
2510 * If nbtree didn't truncate negative infinity tuples during internal
2511 * page splits then we'd expect child's negative infinity key to be
2512 * equal to the scankey/downlink from target/parent (it would be a
2513 * "low key" in this hypothetical scenario, and so it would still need
2514 * to be treated as a special case here).
2515 *
2516 * Negative infinity items can be thought of as a strict lower bound
2517 * that works transitively, with the last non-negative-infinity pivot
2518 * followed during a descent from the root as its "true" strict lower
2519 * bound. Only a small number of negative infinity items are truly
2520 * negative infinity; those that are the first items of leftmost
2521 * internal pages. In more general terms, a negative infinity item is
2522 * only negative infinity with respect to the subtree that the page is
2523 * at the root of.
2524 *
2525 * See also: bt_rootdescend(), which can even detect transitive
2526 * inconsistencies on cousin leaf pages.
2527 */
2529 continue;
2530
2532 offset))
2540 }
2541
2542 pfree(child);
2543}
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 2147 of file verify_nbtree.c.
2151{
2153 Page page;
2154 BTPageOpaque opaque;
2156 bool first = true;
2157 ItemId itemid;
2158 IndexTuple itup;
2159 BlockNumber downlink;
2160
2162 {
2166 downlink = BTreeTupleGetDownLink(itup);
2167 }
2168 else
2169 {
2170 downlink = P_NONE;
2171 }
2172
2173 /*
2174 * If no previous rightlink is memorized for current level just below
2175 * target page's level, we are about to start from the leftmost page. We
2176 * can't follow rightlinks from previous page, because there is no
2177 * previous page. But we still can match high key.
2178 *
2179 * So we initialize variables for the loop above like there is previous
2180 * page referencing current child. Also we imply previous page to not
2181 * have incomplete split flag, that would make us require downlink for
2182 * current child. That's correct, because leftmost page on the level
2183 * should always have parent downlink.
2184 */
2186 {
2187 blkno = downlink;
2189 }
2190
2191 /* Move to the right on the child level */
2192 while (true)
2193 {
2194 /*
2195 * Did we traverse the whole tree level and this is check for pages to
2196 * the right of rightmost downlink?
2197 */
2199 {
2202 return;
2203 }
2204
2205 /* Did we traverse the whole tree level and don't find next downlink? */
2210 state->prevrightlink, downlink,
2212
2213 /* Load page contents */
2215 page = loaded_child;
2216 else
2218
2219 opaque = BTPageGetOpaque(page);
2220
2221 /* The first page we visit at the level should be leftmost */
2229 state->targetblock, blkno,
2231
2232 /* Do level sanity check */
2241
2242 /* Try to detect circular links */
2248
2250 {
2251 /* blkno probably has missing parent downlink */
2253 }
2254
2256
2257 /*
2258 * If we visit page with high key, check that it is equal to the
2259 * target key next to corresponding downlink.
2260 */
2262 {
2266
2267 /* Get high key */
2270
2271 /*
2272 * There might be two situations when we examine high key. If
2273 * current child page is referenced by given target downlink, we
2274 * should look to the next offset number for matching key from
2275 * target page.
2276 *
2277 * Alternatively, we're following rightlinks somewhere in the
2278 * middle between page referenced by previous target's downlink
2279 * and the page referenced by current target's downlink. If
2280 * current child page hasn't incomplete split flag set, then its
2281 * high key should match to the target's key of current offset
2282 * number. This happens when a previous call here (to
2283 * bt_child_highkey_check()) found an incomplete split, and we
2284 * reach a right sibling page without a downlink -- the right
2285 * sibling page's high key still needs to be matched to a
2286 * separator key on the parent/target level.
2287 *
2288 * Don't apply OffsetNumberNext() to target_downlinkoffnum when we
2289 * already had to step right on the child level. Our traversal of
2290 * the child level must try to move in perfect lockstep behind (to
2291 * the left of) the target/parent level traversal.
2292 */
2293 if (blkno == downlink)
2295 else
2297
2299
2301 {
2302 /*
2303 * If we're looking for the next pivot tuple in target page,
2304 * but there is no more pivot tuples, then we should match to
2305 * high key instead.
2306 */
2308 {
2315 state->targetblock, blkno,
2318 }
2322 }
2323 else
2324 {
2325 /*
2326 * We cannot try to match child's high key to a negative
2327 * infinity key in target, since there is nothing to compare.
2328 * However, it's still possible to match child's high key
2329 * outside of target page. The reason why we're are is that
2330 * bt_child_highkey_check() was previously called for the
2331 * cousin page of 'loaded_child', which is incomplete split.
2332 * So, now we traverse to the right of that cousin page and
2333 * current child level page under consideration still belongs
2334 * to the subtree of target's left sibling. Thus, we need to
2335 * match child's high key to its left uncle page high key.
2336 * Thankfully we saved it, it's called a "low key" of target
2337 * page.
2338 */
2345 state->targetblock, blkno,
2347 itup = state->lowkey;
2348 }
2349
2351 {
2357 state->targetblock, blkno,
2359 }
2360 }
2361
2362 /* Exit if we already found next downlink */
2363 if (blkno == downlink)
2364 {
2367 return;
2368 }
2369
2370 /* Traverse to the next page using rightlink */
2371 blkno = opaque->btpo_next;
2372
2373 /* Free page contents if it's allocated by us */
2375 pfree(page);
2376 first = false;
2377 }
2378}
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 2559 of file verify_nbtree.c.
2561{
2563 ItemId itemid;
2564 IndexTuple itup;
2565 Page child;
2567 uint32 level;
2570
2573
2574 /* No next level up with downlinks to fingerprint from the true root */
2576 return;
2577
2579
2580 /*
2581 * Incomplete (interrupted) page splits can account for the lack of a
2582 * downlink. Some inserting transaction should eventually complete the
2583 * page split in passing, when it notices that the left sibling page is
2584 * P_INCOMPLETE_SPLIT().
2585 *
2586 * In general, VACUUM is not prepared for there to be no downlink to a
2587 * page that it deletes. This is the main reason why the lack of a
2588 * downlink can be reported as corruption here. It's not obvious that an
2589 * invalid missing downlink can result in wrong answers to queries,
2590 * though, since index scans that land on the child may end up
2591 * consistently moving right. The handling of concurrent page splits (and
2592 * page deletions) within _bt_moveright() cannot distinguish
2593 * inconsistencies that last for a moment from inconsistencies that are
2594 * permanent and irrecoverable.
2595 *
2596 * VACUUM isn't even prepared to delete pages that have no downlink due to
2597 * an incomplete page split, but it can detect and reason about that case
2598 * by design, so it shouldn't be taken to indicate corruption. See
2599 * _bt_pagedel() for full details.
2600 */
2602 {
2608 blkno, opaque->btpo_level,
2609 opaque->btpo_prev,
2611 return;
2612 }
2613
2614 /*
2615 * Page under check is probably the "top parent" of a multi-level page
2616 * deletion. We'll need to descend the subtree to make sure that
2617 * descendant pages are consistent with that, though.
2618 *
2619 * If the page (which must be non-ignorable) is a leaf page, then clearly
2620 * it can't be the top parent. The lack of a downlink is probably a
2621 * symptom of a broad problem that could just as easily cause
2622 * inconsistencies anywhere else.
2623 */
2630 blkno,
2632
2633 /* Descend from the given page, which is an internal page */
2634 elog(DEBUG1, "checking for interrupted multi-level deletion due to missing downlink in index \"%s\"",
2636
2637 level = opaque->btpo_level;
2641 for (;;)
2642 {
2643 CHECK_FOR_INTERRUPTS();
2644
2647
2649 break;
2650
2651 /* Do an extra sanity check in passing on internal pages */
2657 errdetail_internal("Top parent/under check block=%u block pointed to=%u expected level=%u level in pointed to block=%u.",
2658 blkno, childblk,
2659 level - 1, copaque->btpo_level)));
2660
2661 level = copaque->btpo_level;
2666 /* Be slightly more pro-active in freeing this memory, just in case */
2667 pfree(child);
2668 }
2669
2670 /*
2671 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2672 * and since a page has no links within other pages (siblings and parent)
2673 * once it is marked fully deleted, it should be impossible to land on a
2674 * fully deleted page. See bt_child_check() for further details.
2675 *
2676 * The bt_child_check() P_ISDELETED() check is repeated here because
2677 * bt_child_check() does not visit pages reachable through negative
2678 * infinity items. Besides, bt_child_check() is unwilling to descend
2679 * multiple levels. (The similar bt_child_check() P_ISDELETED() check
2680 * within bt_check_level_from_leftmost() won't reach the page either,
2681 * since the leaf's live siblings should have their sibling links updated
2682 * to bypass the deletion target page when it is marked fully dead.)
2683 *
2684 * If this error is raised, it might be due to a previous multi-level page
2685 * deletion that failed to realize that it wasn't yet safe to mark the
2686 * leaf page as fully dead. A "dangling downlink" will still remain when
2687 * this happens. The fact that the dangling downlink's page (the leaf's
2688 * parent/ancestor page) lacked a downlink is incidental.
2689 */
2695 errdetail_internal("Top parent/target block=%u leaf block=%u top parent/under check lsn=%X/%08X.",
2696 blkno, childblk,
2698
2699 /*
2700 * Iff leaf page is half-dead, its high key top parent link should point
2701 * to what VACUUM considered to be the top parent page at the instant it
2702 * was interrupted. Provided the high key link actually points to the
2703 * page under check, the missing downlink we detected is consistent with
2704 * there having been an interrupted multi-level page deletion. This means
2705 * that the subtree with the page under check at its root (a page deletion
2706 * chain) is in a consistent state, enabling VACUUM to resume deleting the
2707 * entire chain the next time it encounters the half-dead leaf page.
2708 */
2710 {
2714 return;
2715 }
2716
2722 blkno, opaque->btpo_level,
2724}
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 913 of file verify_nbtree.c.
916{
917 ItemPointer tid;
919
921
922 /*
923 * Current tuple has posting list. Report duplicate if TID of any posting
924 * list entry is visible and lVis->tid is valid.
925 */
927 {
929 {
932 {
935 {
937 lVis,
938 tid, targetblock,
939 offset, i);
940 }
941
942 /*
943 * Prevent double reporting unique constraint violation
944 * between the posting list entries of the first tuple on the
945 * page after cross-page check.
946 */
948 return;
949
950 lVis->blkno = targetblock;
951 lVis->offset = offset;
953 lVis->tid = tid;
954 }
955 }
956 }
957
958 /*
959 * Current tuple has no posting list. If TID is visible save info about it
960 * for the next comparisons in the loop in bt_target_page_check(). Report
961 * duplicate if lVis->tid is already valid.
962 */
963 else
964 {
965 tid = BTreeTupleGetHeapTID(itup);
967 {
970 {
972 lVis,
973 tid, targetblock,
974 offset, -1);
975 }
976
977 lVis->blkno = targetblock;
978 lVis->offset = offset;
979 lVis->tid = tid;
980 lVis->postingIndex = -1;
981 }
982 }
983
986 lVis->blkno != targetblock)
987 {
989
995 targetblock, offset,
997 errdetail("It doesn't have visible heap tids and key is equal to the tid=(%u,%u)%s (points to heap tid=(%u,%u)).",
1002 }
1003}
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 {
339 break;
340 }
341
346 has_interval_ops
348 : 0));
349 }
350
351 /* Check index, possibly against table it is an index on */
354}
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 1012 of file verify_nbtree.c.
1015{
1019
1020 /*
1021 * To handle the !readonly case, we'd need to accept BTP_DELETED pages and
1022 * potentially observe nbtree/README "Page deletion and backwards scans".
1023 */
1025
1027 {
1030
1031 CHECK_FOR_INTERRUPTS();
1032
1033 /*
1034 * Try to detect btpo_prev circular links. _bt_unlink_halfdead_page()
1035 * writes that side-links will continue to point to the siblings.
1036 * Check btpo_next for that property.
1037 */
1043 {
1045
1046 /* pagelsn should point to an XLOG_BTREE_MARK_PAGE_HALFDEAD */
1054
1057 }
1058
1059 pfree(page);
1060 }
1061
1063}
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 2850 of file verify_nbtree.c.
2851{
2859
2860 /* Caller should only pass "logical" non-pivot tuples here */
2862
2863 /* Easy case: It's immediately clear that tuple has no varlena datums */
2865 return itup;
2866
2868 {
2869 Form_pg_attribute att;
2870
2872
2873 /* Assume untoasted/already normalized datum initially */
2876 tupleDescriptor,
2877 &isnull[i]);
2879 continue;
2880
2881 /*
2882 * Callers always pass a tuple that could safely be inserted into the
2883 * index without further processing, so an external varlena header
2884 * should never be encountered here
2885 */
2895 (att->attstorage == TYPSTORAGE_EXTENDED ||
2896 att->attstorage == TYPSTORAGE_MAIN))
2897 {
2898 /*
2899 * This value will be compressed by index_form_tuple() with the
2900 * current storage settings. We may be here because this tuple
2901 * was formed with different storage settings. So, force forming.
2902 */
2904 }
2906 {
2910 }
2911
2912 /*
2913 * Short tuples may have 1B or 4B header. Convert 4B header of short
2914 * tuples to 1B
2915 */
2917 {
2918 /* convert to short varlena */
2921
2924
2928 }
2929 }
2930
2931 /*
2932 * Easier case: Tuple has varlena datums, none of which are compressed or
2933 * short with 4B header
2934 */
2936 return itup;
2937
2938 /*
2939 * Hard case: Tuple had compressed varlena datums that necessitate
2940 * creating normalized version of the tuple from uncompressed input datums
2941 * (normalized input datums). This is rather naive, but shouldn't be
2942 * necessary too often.
2943 *
2944 * In the heap, tuples may contain short varlena datums with both 1B
2945 * header and 4B headers. But the corresponding index tuple should always
2946 * have such varlena's with 1B headers. So, if there is a short varlena
2947 * with 4B header, we need to convert it for fingerprinting.
2948 *
2949 * Note that we rely on deterministic index_form_tuple() TOAST compression
2950 * of normalized input.
2951 */
2954
2955 /* Cannot leak memory here */
2959
2961}
References Assert, BTreeTupleIsPivot(), BTreeTupleIsPosting(), data, DatumGetPointer(), ereport, errcode(), errmsg, ERROR, fb(), i, index_form_tuple(), index_getattr(), INDEX_MAX_KEYS, IndexTupleHasVarwidths(), ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), len, memcpy(), 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_ANY().
Referenced by bt_target_page_check(), and bt_tuple_present_callback().
◆ bt_pivot_tuple_identical()
|
static |
Definition at line 2074 of file verify_nbtree.c.
2075{
2077 return false;
2078
2079 if (heapkeyspace)
2080 {
2081 /*
2082 * Offset number will contain important information in heapkeyspace
2083 * indexes: the number of attributes left in the pivot tuple following
2084 * suffix truncation. Don't skip over it (compare it too).
2085 */
2089 return false;
2090 }
2091 else
2092 {
2093 /*
2094 * Cannot rely on offset number field having consistent value across
2095 * levels on pg_upgrade'd !heapkeyspace indexes. Compare contents of
2096 * tuple starting from just after item pointer (i.e. after block
2097 * number and offset number).
2098 */
2102 return false;
2103 }
2104
2105 return true;
2106}
References fb(), and IndexTupleSize().
Referenced by bt_child_highkey_check().
◆ bt_posting_plain_tuple()
|
inlinestatic |
Definition at line 2978 of file verify_nbtree.c.
2979{
2981
2982 /* Returns non-posting-list tuple */
2984}
References _bt_form_posting(), Assert, BTreeTupleGetPostingN(), and BTreeTupleIsPosting().
Referenced by bt_target_page_check().
◆ bt_recheck_sibling_links()
|
static |
Definition at line 1101 of file verify_nbtree.c.
1104{
1105 /* passing metapage to BTPageGetOpaque() would give irrelevant findings */
1107
1109 {
1112 Page page;
1113 BTPageOpaque opaque;
1115
1116 /* Couple locks in the usual order for nbtree: Left to right */
1122 opaque = BTPageGetOpaque(page);
1124 {
1125 /*
1126 * Cannot reason about concurrently deleted page -- the left link
1127 * in the page to the right is expected to point to some other
1128 * page to the left (not leftcurrent page).
1129 *
1130 * Note that we deliberately don't give up with a half-dead page.
1131 */
1133 return;
1134 }
1135
1137 /* Avoid self-deadlock when newtargetblock == leftcurrent */
1139 {
1142 state->checkstrategy);
1146 opaque = BTPageGetOpaque(page);
1147 /* btpo_prev_from_target may have changed; update it */
1149 }
1150 else
1151 {
1152 /*
1153 * leftcurrent right sibling points back to leftcurrent block.
1154 * Index is corrupt. Easiest way to handle this is to pretend
1155 * that we actually read from a distinct page that has an invalid
1156 * block number in its btpo_prev.
1157 */
1160 }
1161
1162 /*
1163 * No need to check P_ISDELETED here, since new target block cannot be
1164 * marked deleted as long as we hold a lock on lbuf
1165 */
1169
1171 {
1172 /* Report split in left sibling, not target (or new target) */
1179 state->targetblock)));
1180 return;
1181 }
1182
1183 /*
1184 * Index is corrupt. Make sure that we report correct target page.
1185 *
1186 * This could have changed in cases where there was a concurrent page
1187 * split, as well as index corruption (at least in theory). Note that
1188 * btpo_prev_from_target was already updated above.
1189 */
1191 }
1192
1199 btpo_prev_from_target)));
1200}
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 873 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 1867 of file verify_nbtree.c.
1868{
1869 BTPageOpaque opaque;
1875
1876 /* Determine target's next block number */
1878
1879 /* If target is already rightmost, no right sibling; nothing to do here */
1882
1883 /*
1884 * General notes on concurrent page splits and page deletion:
1885 *
1886 * Routines like _bt_search() don't require *any* page split interlock
1887 * when descending the tree, including something very light like a buffer
1888 * pin. That's why it's okay that we don't either. This avoidance of any
1889 * need to "couple" buffer locks is the raison d' etre of the Lehman & Yao
1890 * algorithm, in fact.
1891 *
1892 * That leaves deletion. A deleted page won't actually be recycled by
1893 * VACUUM early enough for us to fail to at least follow its right link
1894 * (or left link, or downlink) and find its sibling, because recycling
1895 * does not occur until no possible index scan could land on the page.
1896 * Index scans can follow links with nothing more than their snapshot as
1897 * an interlock and be sure of at least that much. (See page
1898 * recycling/"visible to everyone" notes in nbtree README.)
1899 *
1900 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
1901 * dead (ignorable) page one or more times. There will either be a
1902 * further right link to follow that leads to a live page before too long
1903 * (before passing by parent's rightmost child), or we will find the end
1904 * of the entire level instead (possible when parent page is itself the
1905 * rightmost on its level).
1906 */
1908 for (;;)
1909 {
1910 CHECK_FOR_INTERRUPTS();
1911
1914
1916 break;
1917
1918 /*
1919 * We landed on a deleted or half-dead sibling page. Step right until
1920 * we locate a live sibling page.
1921 */
1924 errmsg_internal("level %u sibling page in block %u of index \"%s\" was found deleted or half dead",
1927
1929
1930 /* Be slightly more pro-active in freeing this memory, just in case */
1932 }
1933
1934 /*
1935 * No ShareLock held case -- why it's safe to proceed.
1936 *
1937 * Problem:
1938 *
1939 * We must avoid false positive reports of corruption when caller treats
1940 * item returned here as an upper bound on target's last item. In
1941 * general, false positives are disallowed. Avoiding them here when
1942 * caller is !readonly is subtle.
1943 *
1944 * A concurrent page deletion by VACUUM of the target page can result in
1945 * the insertion of items on to this right sibling page that would
1946 * previously have been inserted on our target page. There might have
1947 * been insertions that followed the target's downlink after it was made
1948 * to point to right sibling instead of target by page deletion's first
1949 * phase. The inserters insert items that would belong on target page.
1950 * This race is very tight, but it's possible. This is our only problem.
1951 *
1952 * Non-problems:
1953 *
1954 * We are not hindered by a concurrent page split of the target; we'll
1955 * never land on the second half of the page anyway. A concurrent split
1956 * of the right page will also not matter, because the first data item
1957 * remains the same within the left half, which we'll reliably land on. If
1958 * we had to skip over ignorable/deleted pages, it cannot matter because
1959 * their key space has already been atomically merged with the first
1960 * non-ignorable page we eventually find (doesn't matter whether the page
1961 * we eventually find is a true sibling or a cousin of target, which we go
1962 * into below).
1963 *
1964 * Solution:
1965 *
1966 * Caller knows that it should reverify that target is not ignorable
1967 * (half-dead or deleted) when cross-page sibling item comparison appears
1968 * to indicate corruption (invariant fails). This detects the single race
1969 * condition that exists for caller. This is correct because the
1970 * continued existence of target block as non-ignorable (not half-dead or
1971 * deleted) implies that target page was not merged into from the right by
1972 * deletion; the key space at or after target never moved left. Target's
1973 * parent either has the same downlink to target as before, or a <
1974 * downlink due to deletion at the left of target. Target either has the
1975 * same highkey as before, or a highkey < before when there is a page
1976 * split. (The rightmost concurrently-split-from-target-page page will
1977 * still have the same highkey as target was originally found to have,
1978 * which for our purposes is equivalent to target's highkey itself never
1979 * changing, since we reliably skip over
1980 * concurrently-split-from-target-page pages.)
1981 *
1982 * In simpler terms, we allow that the key space of the target may expand
1983 * left (the key space can move left on the left side of target only), but
1984 * the target key space cannot expand right and get ahead of us without
1985 * our detecting it. The key space of the target cannot shrink, unless it
1986 * shrinks to zero due to the deletion of the original page, our canary
1987 * condition. (To be very precise, we're a bit stricter than that because
1988 * it might just have been that the target page split and only the
1989 * original target page was deleted. We can be more strict, just not more
1990 * lax.)
1991 *
1992 * Top level tree walk caller moves on to next page (makes it the new
1993 * target) following recovery from this race. (cf. The rationale for
1994 * child/downlink verification needing a ShareLock within
1995 * bt_child_check(), where page deletion is also the main source of
1996 * trouble.)
1997 *
1998 * Note that it doesn't matter if right sibling page here is actually a
1999 * cousin page, because in order for the key space to be readjusted in a
2000 * way that causes us issues in next level up (guiding problematic
2001 * concurrent insertions to the cousin from the grandparent rather than to
2002 * the sibling from the parent), there'd have to be page deletion of
2003 * target's parent page (affecting target's parent's downlink in target's
2004 * grandparent page). Internal page deletion only occurs when there are
2005 * no child pages (they were all fully deleted), and caller is checking
2006 * that the target's parent has at least one non-deleted (so
2007 * non-ignorable) child: the target page. (Note that the first phase of
2008 * deletion atomically marks the page to be deleted half-dead/ignorable at
2009 * the same time downlink in its parent is removed, so caller will
2010 * definitely not fail to detect that this happened.)
2011 *
2012 * This trick is inspired by the method backward scans use for dealing
2013 * with concurrent page splits; concurrent page deletion is a problem that
2014 * similarly receives special consideration sometimes (it's possible that
2015 * the backwards scan will re-read its "original" block after failing to
2016 * find a right-link to it, having already moved in the opposite direction
2017 * (right/"forwards") a few times to try to locate one). Just like us,
2018 * that happens only to determine if there was a concurrent page deletion
2019 * of a reference page, and just like us if there was a page deletion of
2020 * that reference page it means we can move on from caring about the
2021 * reference page. See the nbtree README for a full description of how
2022 * that works.
2023 */
2025
2026 /*
2027 * Get first data item, if any
2028 */
2030 {
2031 /* Return first data item (if any) */
2033 P_FIRSTDATAKEY(opaque));
2035 }
2038 {
2039 /*
2040 * Return first item after the internal page's "negative infinity"
2041 * item
2042 */
2045 }
2046 else
2047 {
2048 /*
2049 * No first item. Page is probably empty leaf page, but it's also
2050 * possible that it's an internal page with only a negative infinity
2051 * item.
2052 */
2059 }
2060
2061 /*
2062 * Return first real item scankey. Note that this relies on right page
2063 * memory remaining allocated.
2064 */
2067}
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 3011 of file verify_nbtree.c.
3012{
3016
3019
3020 /*
3021 * Search from root.
3022 *
3023 * Ideally, we would arrange to only move right within _bt_search() when
3024 * an interrupted page split is detected (i.e. when the incomplete split
3025 * bit is found to be set), but for now we accept the possibility that
3026 * that could conceal an inconsistency.
3027 */
3031
3033 {
3035 OffsetNumber offnum;
3036 Page page;
3037
3041 insertstate.postingoff = 0;
3044
3045 /* Get matching tuple on leaf page */
3047 /* Compare first >= matching item on leaf page, if any */
3049 /* Should match on first heap TID when tuple has a posting list */
3051 insertstate.postingoff <= 0 &&
3055 }
3056
3057 pfree(key);
3058
3060}
References _bt_binsrch_insert(), _bt_compare(), _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 1241 of file verify_nbtree.c.
1242{
1243 OffsetNumber offset;
1244 OffsetNumber max;
1246
1247 /* Last visible entry info for checking indexes with unique constraint */
1249
1252
1255
1256 /*
1257 * Check the number of attributes in high key. Note, rightmost page
1258 * doesn't contain a high key, so nothing to check
1259 */
1261 {
1262 ItemId itemid;
1263 IndexTuple itup;
1264
1265 /* Verify line pointer before checking tuple */
1269 P_HIKEY))
1270 {
1277 state->targetblock,
1281 }
1282 }
1283
1284 /*
1285 * Loop over page items, starting from first non-highkey item, not high
1286 * key (if any). Most tests are not performed for the "negative infinity"
1287 * real item (if any).
1288 */
1290 offset <= max;
1291 offset = OffsetNumberNext(offset))
1292 {
1293 ItemId itemid;
1294 IndexTuple itup;
1298 ItemPointer scantid;
1299
1300 /*
1301 * True if we already called bt_entry_unique_check() for the current
1302 * item. This helps to avoid visiting the heap for keys, which are
1303 * anyway presented only once and can't comprise a unique violation.
1304 */
1306
1307 CHECK_FOR_INTERRUPTS();
1308
1310 state->target, offset);
1313
1314 /*
1315 * lp_len should match the IndexTuple reported length exactly, since
1316 * lp_len is completely redundant in indexes, and both sources of
1317 * tuple length are MAXALIGN()'d. nbtree does not use lp_len all that
1318 * frequently, and is surprisingly tolerant of corrupt lp_len fields.
1319 */
1326 state->targetblock, offset,
1330
1331 /* Check the number of index tuple attributes */
1333 offset))
1334 {
1335 ItemPointer tid;
1337 *htid;
1338
1340 tid = BTreeTupleGetPointsToTID(itup);
1342 ItemPointerGetBlockNumberNoCheck(tid),
1343 ItemPointerGetOffsetNumberNoCheck(tid));
1344
1350 itid,
1353 htid,
1355 }
1356
1357 /*
1358 * Don't try to generate scankey using "negative infinity" item on
1359 * internal pages. They are always truncated to zero attributes.
1360 */
1362 {
1363 /*
1364 * We don't call bt_child_check() for "negative infinity" items.
1365 * But if we're performing downlink connectivity check, we do it
1366 * for every item including "negative infinity" one.
1367 */
1369 {
1371 offset,
1372 NULL,
1373 topaque->btpo_level);
1374 }
1375 continue;
1376 }
1377
1378 /*
1379 * Readonly callers may optionally verify that non-pivot tuples can
1380 * each be found by an independent search that starts from the root.
1381 * Note that we deliberately don't do individual searches for each
1382 * TID, since the posting list itself is validated by other checks.
1383 */
1386 {
1389 *htid;
1390
1393 ItemPointerGetOffsetNumber(tid));
1394
1402 }
1403
1404 /*
1405 * If tuple is a posting list tuple, make sure posting list TIDs are
1406 * in order
1407 */
1409 {
1410 ItemPointerData last;
1411 ItemPointer current;
1412
1414
1416 {
1417
1419
1421 {
1423
1431 }
1432
1433 ItemPointerCopy(current, &last);
1434 }
1435 }
1436
1437 /* Build insertion scankey for current page offset */
1439
1440 /*
1441 * Make sure tuple size does not exceed the relevant BTREE_VERSION
1442 * specific limit.
1443 *
1444 * BTREE_VERSION 4 (which introduced heapkeyspace rules) requisitioned
1445 * a small amount of space from BTMaxItemSize() in order to ensure
1446 * that suffix truncation always has enough space to add an explicit
1447 * heap TID back to a tuple -- we pessimistically assume that every
1448 * newly inserted tuple will eventually need to have a heap TID
1449 * appended during a future leaf page split, when the tuple becomes
1450 * the basis of the new high key (pivot tuple) for the leaf page.
1451 *
1452 * Since the reclaimed space is reserved for that purpose, we must not
1453 * enforce the slightly lower limit when the extra space has been used
1454 * as intended. In other words, there is only a cross-version
1455 * difference in the limit on tuple size within leaf pages.
1456 *
1457 * Still, we're particular about the details within BTREE_VERSION 4
1458 * internal pages. Pivot tuples may only use the extra space for its
1459 * designated purpose. Enforce the lower limit for pivot tuples when
1460 * an explicit heap TID isn't actually present. (In all other cases
1461 * suffix truncation is guaranteed to generate a pivot tuple that's no
1462 * larger than the firstright tuple provided to it by its caller.)
1463 */
1467 {
1470 *htid;
1471
1474 ItemPointerGetBlockNumberNoCheck(tid),
1475 ItemPointerGetOffsetNumberNoCheck(tid));
1476
1482 itid,
1484 htid,
1486 }
1487
1488 /* Fingerprint leaf page tuples (those that point to the heap) */
1490 {
1492
1494 {
1495 /* Fingerprint all elements as distinct "plain" tuples */
1497 {
1499
1504 /* Be tidy */
1508 }
1509 }
1510 else
1511 {
1515 /* Be tidy */
1518 }
1519 }
1520
1521 /*
1522 * * High key check *
1523 *
1524 * If there is a high key (if this is not the rightmost page on its
1525 * entire level), check that high key actually is upper bound on all
1526 * page items. If this is a posting list tuple, we'll need to set
1527 * scantid to be highest TID in posting list.
1528 *
1529 * We prefer to check all items against high key rather than checking
1530 * just the last and trusting that the operator class obeys the
1531 * transitive law (which implies that all previous items also
1532 * respected the high key invariant if they pass the item order
1533 * check).
1534 *
1535 * Ideally, we'd compare every item in the index against every other
1536 * item in the index, and not trust opclass obedience of the
1537 * transitive law to bridge the gap between children and their
1538 * grandparents (as well as great-grandparents, and so on). We don't
1539 * go to those lengths because that would be prohibitively expensive,
1540 * and probably not markedly more effective in practice.
1541 *
1542 * On the leaf level, we check that the key is <= the highkey.
1543 * However, on non-leaf levels we check that the key is < the highkey,
1544 * because the high key is "just another separator" rather than a copy
1545 * of some existing key item; we expect it to be unique among all keys
1546 * on the same level. (Suffix truncation will sometimes produce a
1547 * leaf highkey that is an untruncated copy of the lastleft item, but
1548 * never any other item, which necessitates weakening the leaf level
1549 * check to <=.)
1550 *
1551 * Full explanation for why a highkey is never truly a copy of another
1552 * item from the same level on internal levels:
1553 *
1554 * While the new left page's high key is copied from the first offset
1555 * on the right page during an internal page split, that's not the
1556 * full story. In effect, internal pages are split in the middle of
1557 * the firstright tuple, not between the would-be lastleft and
1558 * firstright tuples: the firstright key ends up on the left side as
1559 * left's new highkey, and the firstright downlink ends up on the
1560 * right side as right's new "negative infinity" item. The negative
1561 * infinity tuple is truncated to zero attributes, so we're only left
1562 * with the downlink. In other words, the copying is just an
1563 * implementation detail of splitting in the middle of a (pivot)
1564 * tuple. (See also: "Notes About Data Representation" in the nbtree
1565 * README.)
1566 */
1567 scantid = skey->scantid;
1570
1574 {
1577 *htid;
1578
1581 ItemPointerGetBlockNumberNoCheck(tid),
1582 ItemPointerGetOffsetNumberNoCheck(tid));
1583
1589 itid,
1591 htid,
1593 }
1594 /* Reset, in case scantid was set to (itup) posting tuple's max TID */
1595 skey->scantid = scantid;
1596
1597 /*
1598 * * Item order check *
1599 *
1600 * Check that items are stored on page in logical order, by checking
1601 * current item is strictly less than next item (if any).
1602 */
1605 {
1606 ItemPointer tid;
1608 *htid,
1609 *nitid,
1610 *nhtid;
1611
1613 tid = BTreeTupleGetPointsToTID(itup);
1615 ItemPointerGetBlockNumberNoCheck(tid),
1616 ItemPointerGetOffsetNumberNoCheck(tid));
1618 OffsetNumberNext(offset));
1619
1620 /* Reuse itup to get pointed-to heap location of second item */
1622 state->target,
1623 OffsetNumberNext(offset));
1625 tid = BTreeTupleGetPointsToTID(itup);
1627 ItemPointerGetBlockNumberNoCheck(tid),
1628 ItemPointerGetOffsetNumberNoCheck(tid));
1629
1634 errdetail_internal("Lower index tid=%s (points to %s tid=%s) higher index tid=%s (points to %s tid=%s) page lsn=%X/%08X.",
1635 itid,
1637 htid,
1638 nitid,
1640 nhtid,
1642 }
1643
1644 /*
1645 * If the index is unique verify entries uniqueness by checking the
1646 * heap tuples visibility. Immediately check posting tuples and
1647 * tuples with repeated keys. Postpone check for keys, which have the
1648 * first appearance.
1649 */
1653 {
1655 &lVis);
1657 }
1658
1661 {
1662 /* Save current scankey tid */
1663 scantid = skey->scantid;
1664
1665 /*
1666 * Invalidate scankey tid to make _bt_compare compare only keys in
1667 * the item to report equality even if heap TIDs are different
1668 */
1670
1671 /*
1672 * If next key tuple is different, invalidate last visible entry
1673 * data (whole index tuple or last posting in index tuple). Key
1674 * containing null value does not violate unique constraint and
1675 * treated as different to any other key.
1676 *
1677 * If the next key is the same as the previous one, do the
1678 * bt_entry_unique_check() call if it was postponed.
1679 */
1682 {
1685 lVis.postingIndex = -1;
1687 }
1689 {
1691 &lVis);
1692 }
1694 }
1695
1696 /*
1697 * * Last item check *
1698 *
1699 * Check last item against next/right page's first data item's when
1700 * last item on page is reached. This additional check will detect
1701 * transposed pages iff the supposed right sibling page happens to
1702 * belong before target in the key space. (Otherwise, a subsequent
1703 * heap verification will probably detect the problem.)
1704 *
1705 * This check is similar to the item order check that will have
1706 * already been performed for every other "real" item on target page
1707 * when last item is checked. The difference is that the next item
1708 * (the item that is compared to target's last item) needs to come
1709 * from the next/sibling page. There may not be such an item
1710 * available from sibling for various reasons, though (e.g., target is
1711 * the rightmost page on level).
1712 */
1713 if (offset == max)
1714 {
1716
1717 /* first offset on a right index page (log only) */
1719
1720 /* Get item in next/right page */
1722
1725 {
1726 /*
1727 * As explained at length in bt_right_page_check_scankey(),
1728 * there is a known !readonly race that could account for
1729 * apparent violation of invariant, which we must check for
1730 * before actually proceeding with raising error. Our canary
1731 * condition is that target page was deleted.
1732 */
1734 {
1735 /* Get fresh copy of target page */
1737 /* Note that we deliberately do not update target LSN */
1739
1740 /*
1741 * All !readonly checks now performed; just return
1742 */
1744 return;
1745 }
1746
1752 state->targetblock, offset,
1754 }
1755
1756 /*
1757 * If index has unique constraint make sure that no more than one
1758 * found equal items is visible.
1759 */
1762 {
1764
1766
1767 /*
1768 * Make _bt_compare compare only index keys without heap TIDs.
1769 * rightkey->scantid is modified destructively but it is ok
1770 * for it is not used later.
1771 */
1773
1774 /* The first key on the next page is the same */
1776 !rightkey->anynullkeys)
1777 {
1779
1780 /*
1781 * Do the bt_entry_unique_check() call if it was
1782 * postponed.
1783 */
1786 offset, &lVis);
1787
1790 rightblock_number);
1792
1794 {
1796 break;
1797 }
1798
1805 state->targetblock,
1807
1809 rightpage,
1810 rightfirstoffset);
1812
1814
1816 }
1817 }
1818 }
1819
1820 /*
1821 * * Downlink check *
1822 *
1823 * Additional check of child items iff this is an internal page and
1824 * caller holds a ShareLock. This happens for every downlink (item)
1825 * in target excluding the negative-infinity downlink (again, this is
1826 * because it has no useful value to compare).
1827 */
1830 }
1831
1832 /*
1833 * Special case bt_child_highkey_check() call
1834 *
1835 * We don't pass a real downlink, but we've to finish the level
1836 * processing. If condition is satisfied, we've already processed all the
1837 * downlinks from the target level. But there still might be pages to the
1838 * right of the child page pointer to by our rightmost downlink. And they
1839 * might have missing downlinks. This final call checks for them.
1840 */
1842 {
1845 }
1846}
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 2782 of file verify_nbtree.c.
2784{
2786 IndexTuple itup,
2787 norm;
2788
2790
2791 /* Generate a normalized index tuple for fingerprinting */
2793 itup->t_tid = *tid;
2795
2796 /* Probe Bloom filter -- tuple should be present */
2806 !state->readonly
2807 ? errhint("Retrying verification using the function bt_index_parent_check() might provide a more specific error.")
2808 : 0));
2809
2810 state->heaptuplespresent++;
2811 pfree(itup);
2812 /* Cannot leak memory here */
2815}
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 854 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, memcpy(), 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 |
||
| ) |
