PostgreSQL Source Code git master
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 "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
 

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
 

Functions

 PG_FUNCTION_INFO_V1 (bt_index_check)
 
 PG_FUNCTION_INFO_V1 (bt_index_parent_check)
 
static void bt_index_check_internal (Oid indrelid, bool parentcheck, bool heapallindexed, bool rootdescend, bool checkunique)
 
static void btree_index_checkable (Relation rel)
 
static bool btree_index_mainfork_expected (Relation rel)
 
static void bt_check_every_level (Relation rel, Relation heaprel, bool heapkeyspace, bool readonly, bool heapallindexed, bool rootdescend, bool checkunique)
 
static BtreeLevel bt_check_level_from_leftmost (BtreeCheckState *state, BtreeLevel level)
 
static bool bt_leftmost_ignoring_half_dead (BtreeCheckState *state, BlockNumber start, BTPageOpaque start_opaque)
 
static void bt_recheck_sibling_links (BtreeCheckState *state, BlockNumber btpo_prev_from_target, BlockNumber leftcurrent)
 
static bool heap_entry_is_visible (BtreeCheckState *state, ItemPointer tid)
 
static void bt_report_duplicate (BtreeCheckState *state, BtreeLastVisibleEntry *lVis, ItemPointer nexttid, BlockNumber nblock, OffsetNumber noffset, int nposting)
 
static void bt_entry_unique_check (BtreeCheckState *state, IndexTuple itup, BlockNumber targetblock, OffsetNumber offset, BtreeLastVisibleEntry *lVis)
 
static void bt_target_page_check (BtreeCheckState *state)
 
static BTScanInsert bt_right_page_check_scankey (BtreeCheckState *state, OffsetNumber *rightfirstoffset)
 
static void bt_child_check (BtreeCheckState *state, BTScanInsert targetkey, OffsetNumber downlinkoffnum)
 
static void bt_child_highkey_check (BtreeCheckState *state, OffsetNumber target_downlinkoffnum, Page loaded_child, uint32 target_level)
 
static void bt_downlink_missing_check (BtreeCheckState *state, bool rightsplit, BlockNumber blkno, Page page)
 
static void bt_tuple_present_callback (Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *checkstate)
 
static IndexTuple bt_normalize_tuple (BtreeCheckState *state, IndexTuple itup)
 
static IndexTuple bt_posting_plain_tuple (IndexTuple itup, int n)
 
static bool bt_rootdescend (BtreeCheckState *state, IndexTuple itup)
 
static bool offset_is_negative_infinity (BTPageOpaque opaque, OffsetNumber offset)
 
static bool invariant_l_offset (BtreeCheckState *state, BTScanInsert key, OffsetNumber upperbound)
 
static bool invariant_leq_offset (BtreeCheckState *state, BTScanInsert key, OffsetNumber upperbound)
 
static bool invariant_g_offset (BtreeCheckState *state, BTScanInsert key, OffsetNumber lowerbound)
 
static bool invariant_l_nontarget_offset (BtreeCheckState *state, BTScanInsert key, BlockNumber nontargetblock, Page nontarget, OffsetNumber upperbound)
 
static Page palloc_btree_page (BtreeCheckState *state, BlockNumber blocknum)
 
static BTScanInsert bt_mkscankey_pivotsearch (Relation rel, IndexTuple itup)
 
static ItemId PageGetItemIdCareful (BtreeCheckState *state, BlockNumber block, Page page, OffsetNumber offset)
 
static ItemPointer BTreeTupleGetHeapTIDCareful (BtreeCheckState *state, IndexTuple itup, bool nonpivot)
 
static ItemPointer BTreeTupleGetPointsToTID (IndexTuple itup)
 
Datum bt_index_check (PG_FUNCTION_ARGS)
 
Datum bt_index_parent_check (PG_FUNCTION_ARGS)
 
static bool bt_pivot_tuple_identical (bool heapkeyspace, IndexTuple itup1, IndexTuple itup2)
 

Variables

 PG_MODULE_MAGIC
 

Macro Definition Documentation

◆ BTreeTupleGetNKeyAtts

#define BTreeTupleGetNKeyAtts (   itup,
  rel 
)     Min(IndexRelationGetNumberOfKeyAttributes(rel), BTreeTupleGetNAtts(itup, rel))

Definition at line 52 of file verify_nbtree.c.

◆ InvalidBtreeLevel

#define InvalidBtreeLevel   ((uint32) InvalidBlockNumber)

Definition at line 51 of file verify_nbtree.c.

Typedef Documentation

◆ BtreeCheckState

◆ BtreeLastVisibleEntry

◆ BtreeLevel

typedef struct BtreeLevel BtreeLevel

Function Documentation

◆ bt_check_every_level()

static void bt_check_every_level ( Relation  rel,
Relation  heaprel,
bool  heapkeyspace,
bool  readonly,
bool  heapallindexed,
bool  rootdescend,
bool  checkunique 
)
static

Definition at line 500 of file verify_nbtree.c.

503{
505 Page metapage;
506 BTMetaPageData *metad;
507 uint32 previouslevel;
508 BtreeLevel current;
509 Snapshot snapshot = SnapshotAny;
510
511 if (!readonly)
512 elog(DEBUG1, "verifying consistency of tree structure for index \"%s\"",
514 else
515 elog(DEBUG1, "verifying consistency of tree structure for index \"%s\" with cross-level checks",
517
518 /*
519 * This assertion matches the one in index_getnext_tid(). See page
520 * recycling/"visible to everyone" notes in nbtree README.
521 */
523
524 /*
525 * Initialize state for entire verification operation
526 */
527 state = palloc0(sizeof(BtreeCheckState));
528 state->rel = rel;
529 state->heaprel = heaprel;
530 state->heapkeyspace = heapkeyspace;
531 state->readonly = readonly;
532 state->heapallindexed = heapallindexed;
533 state->rootdescend = rootdescend;
534 state->checkunique = checkunique;
535 state->snapshot = InvalidSnapshot;
536
537 if (state->heapallindexed)
538 {
539 int64 total_pages;
540 int64 total_elems;
541 uint64 seed;
542
543 /*
544 * Size Bloom filter based on estimated number of tuples in index,
545 * while conservatively assuming that each block must contain at least
546 * MaxTIDsPerBTreePage / 3 "plain" tuples -- see
547 * bt_posting_plain_tuple() for definition, and details of how posting
548 * list tuples are handled.
549 */
550 total_pages = RelationGetNumberOfBlocks(rel);
551 total_elems = Max(total_pages * (MaxTIDsPerBTreePage / 3),
552 (int64) state->rel->rd_rel->reltuples);
553 /* Generate a random seed to avoid repetition */
555 /* Create Bloom filter to fingerprint index */
556 state->filter = bloom_create(total_elems, maintenance_work_mem, seed);
557 state->heaptuplespresent = 0;
558
559 /*
560 * Register our own snapshot in !readonly case, rather than asking
561 * table_index_build_scan() to do this for us later. This needs to
562 * happen before index fingerprinting begins, so we can later be
563 * certain that index fingerprinting should have reached all tuples
564 * returned by table_index_build_scan().
565 */
566 if (!state->readonly)
567 {
569
570 /*
571 * GetTransactionSnapshot() always acquires a new MVCC snapshot in
572 * READ COMMITTED mode. A new snapshot is guaranteed to have all
573 * the entries it requires in the index.
574 *
575 * We must defend against the possibility that an old xact
576 * snapshot was returned at higher isolation levels when that
577 * snapshot is not safe for index scans of the target index. This
578 * is possible when the snapshot sees tuples that are before the
579 * index's indcheckxmin horizon. Throwing an error here should be
580 * very rare. It doesn't seem worth using a secondary snapshot to
581 * avoid this.
582 */
583 if (IsolationUsesXactSnapshot() && rel->rd_index->indcheckxmin &&
585 snapshot->xmin))
588 errmsg("index \"%s\" cannot be verified using transaction snapshot",
590 }
591 }
592
593 /*
594 * We need a snapshot to check the uniqueness of the index. For better
595 * performance take it once per index check. If snapshot already taken
596 * reuse it.
597 */
598 if (state->checkunique)
599 {
600 state->indexinfo = BuildIndexInfo(state->rel);
601 if (state->indexinfo->ii_Unique)
602 {
603 if (snapshot != SnapshotAny)
604 state->snapshot = snapshot;
605 else
607 }
608 }
609
610 Assert(!state->rootdescend || state->readonly);
611 if (state->rootdescend && !state->heapkeyspace)
613 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
614 errmsg("cannot verify that tuples from index \"%s\" can each be found by an independent index search",
616 errhint("Only B-Tree version 4 indexes support rootdescend verification.")));
617
618 /* Create context for page */
620 "amcheck context",
622 state->checkstrategy = GetAccessStrategy(BAS_BULKREAD);
623
624 /* Get true root block from meta-page */
626 metad = BTPageGetMeta(metapage);
627
628 /*
629 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
630 * the fast root and true root differ.
631 *
632 * Start from the true root, not the fast root, unlike conventional index
633 * scans. This approach is more thorough, and removes the risk of
634 * following a stale fast root from the meta page.
635 */
636 if (metad->btm_fastroot != metad->btm_root)
638 (errcode(ERRCODE_NO_DATA),
639 errmsg_internal("harmless fast root mismatch in index \"%s\"",
641 errdetail_internal("Fast root block %u (level %u) differs from true root block %u (level %u).",
642 metad->btm_fastroot, metad->btm_fastlevel,
643 metad->btm_root, metad->btm_level)));
644
645 /*
646 * Starting at the root, verify every level. Move left to right, top to
647 * bottom. Note that there may be no pages other than the meta page (meta
648 * page can indicate that root is P_NONE when the index is totally empty).
649 */
650 previouslevel = InvalidBtreeLevel;
651 current.level = metad->btm_level;
652 current.leftmost = metad->btm_root;
653 current.istruerootlevel = true;
654 while (current.leftmost != P_NONE)
655 {
656 /*
657 * Verify this level, and get left most page for next level down, if
658 * not at leaf level
659 */
660 current = bt_check_level_from_leftmost(state, current);
661
662 if (current.leftmost == InvalidBlockNumber)
664 (errcode(ERRCODE_INDEX_CORRUPTED),
665 errmsg("index \"%s\" has no valid pages on level below %u or first level",
666 RelationGetRelationName(rel), previouslevel)));
667
668 previouslevel = current.level;
669 }
670
671 /*
672 * * Check whether heap contains unindexed/malformed tuples *
673 */
674 if (state->heapallindexed)
675 {
676 IndexInfo *indexinfo = BuildIndexInfo(state->rel);
677 TableScanDesc scan;
678
679 /*
680 * Create our own scan for table_index_build_scan(), rather than
681 * getting it to do so for us. This is required so that we can
682 * actually use the MVCC snapshot registered earlier in !readonly
683 * case.
684 *
685 * Note that table_index_build_scan() calls heap_endscan() for us.
686 */
687 scan = table_beginscan_strat(state->heaprel, /* relation */
688 snapshot, /* snapshot */
689 0, /* number of keys */
690 NULL, /* scan key */
691 true, /* buffer access strategy OK */
692 true); /* syncscan OK? */
693
694 /*
695 * Scan will behave as the first scan of a CREATE INDEX CONCURRENTLY
696 * behaves in !readonly case.
697 *
698 * It's okay that we don't actually use the same lock strength for the
699 * heap relation as any other ii_Concurrent caller would in !readonly
700 * case. We have no reason to care about a concurrent VACUUM
701 * operation, since there isn't going to be a second scan of the heap
702 * that needs to be sure that there was no concurrent recycling of
703 * TIDs.
704 */
705 indexinfo->ii_Concurrent = !state->readonly;
706
707 /*
708 * Don't wait for uncommitted tuple xact commit/abort when index is a
709 * unique index on a catalog (or an index used by an exclusion
710 * constraint). This could otherwise happen in the readonly case.
711 */
712 indexinfo->ii_Unique = false;
713 indexinfo->ii_ExclusionOps = NULL;
714 indexinfo->ii_ExclusionProcs = NULL;
715 indexinfo->ii_ExclusionStrats = NULL;
716
717 elog(DEBUG1, "verifying that tuples from index \"%s\" are present in \"%s\"",
720
721 table_index_build_scan(state->heaprel, state->rel, indexinfo, true, false,
723
725 (errmsg_internal("finished verifying presence of " INT64_FORMAT " tuples from table \"%s\" with bitset %.2f%% set",
726 state->heaptuplespresent, RelationGetRelationName(heaprel),
727 100.0 * bloom_prop_bits_set(state->filter))));
728
729 if (snapshot != SnapshotAny)
730 UnregisterSnapshot(snapshot);
731
732 bloom_free(state->filter);
733 }
734
735 /* Be tidy: */
736 if (snapshot == SnapshotAny && state->snapshot != InvalidSnapshot)
737 UnregisterSnapshot(state->snapshot);
738 MemoryContextDelete(state->targetcontext);
739}
#define InvalidBlockNumber
Definition: block.h:33
void bloom_free(bloom_filter *filter)
Definition: bloomfilter.c:126
bloom_filter * bloom_create(int64 total_elems, int bloom_work_mem, uint64 seed)
Definition: bloomfilter.c:87
double bloom_prop_bits_set(bloom_filter *filter)
Definition: bloomfilter.c:187
@ BAS_BULKREAD
Definition: bufmgr.h:36
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:273
PageData * Page
Definition: bufpage.h:82
#define Max(x, y)
Definition: c.h:955
#define INT64_FORMAT
Definition: c.h:506
#define Assert(condition)
Definition: c.h:815
int64_t int64
Definition: c.h:485
uint64_t uint64
Definition: c.h:489
uint32_t uint32
Definition: c.h:488
int errmsg_internal(const char *fmt,...)
Definition: elog.c:1157
int errdetail_internal(const char *fmt,...)
Definition: elog.c:1230
int errhint(const char *fmt,...)
Definition: elog.c:1317
int errcode(int sqlerrcode)
Definition: elog.c:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define DEBUG1
Definition: elog.h:30
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#define ereport(elevel,...)
Definition: elog.h:149
BufferAccessStrategy GetAccessStrategy(BufferAccessStrategyType btype)
Definition: freelist.c:541
int maintenance_work_mem
Definition: globals.c:132
static TransactionId HeapTupleHeaderGetXmin(const HeapTupleHeaderData *tup)
Definition: htup_details.h:324
IndexInfo * BuildIndexInfo(Relation index)
Definition: index.c:2427
void * palloc0(Size size)
Definition: mcxt.c:1347
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:454
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:160
#define BTPageGetMeta(p)
Definition: nbtree.h:121
#define MaxTIDsPerBTreePage
Definition: nbtree.h:185
#define P_NONE
Definition: nbtree.h:212
#define BTREE_METAPAGE
Definition: nbtree.h:148
uint64 pg_prng_uint64(pg_prng_state *state)
Definition: pg_prng.c:134
pg_prng_state pg_global_prng_state
Definition: pg_prng.c:34
#define ERRCODE_T_R_SERIALIZATION_FAILURE
Definition: pgbench.c:76
#define RelationGetRelationName(relation)
Definition: rel.h:540
TransactionId RecentXmin
Definition: snapmgr.c:100
Snapshot GetTransactionSnapshot(void)
Definition: snapmgr.c:212
void UnregisterSnapshot(Snapshot snapshot)
Definition: snapmgr.c:794
Snapshot RegisterSnapshot(Snapshot snapshot)
Definition: snapmgr.c:752
#define SnapshotAny
Definition: snapmgr.h:33
#define InvalidSnapshot
Definition: snapshot.h:119
uint32 btm_level
Definition: nbtree.h:108
BlockNumber btm_fastroot
Definition: nbtree.h:109
BlockNumber btm_root
Definition: nbtree.h:107
uint32 btm_fastlevel
Definition: nbtree.h:110
bool istruerootlevel
uint32 level
BlockNumber leftmost
HeapTupleHeader t_data
Definition: htup.h:68
bool ii_Unique
Definition: execnodes.h:208
uint16 * ii_ExclusionStrats
Definition: execnodes.h:204
Oid * ii_ExclusionOps
Definition: execnodes.h:202
bool ii_Concurrent
Definition: execnodes.h:213
Oid * ii_ExclusionProcs
Definition: execnodes.h:203
struct HeapTupleData * rd_indextuple
Definition: rel.h:194
Form_pg_index rd_index
Definition: rel.h:192
TransactionId xmin
Definition: snapshot.h:153
Definition: regguts.h:323
static TableScanDesc table_beginscan_strat(Relation rel, Snapshot snapshot, int nkeys, struct ScanKeyData *key, bool allow_strat, bool allow_sync)
Definition: tableam.h:937
static double table_index_build_scan(Relation table_rel, Relation index_rel, struct IndexInfo *index_info, bool allow_sync, bool progress, IndexBuildCallback callback, void *callback_state, TableScanDesc scan)
Definition: tableam.h:1781
bool TransactionIdPrecedes(TransactionId id1, TransactionId id2)
Definition: transam.c:280
#define TransactionIdIsValid(xid)
Definition: transam.h:41
static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
static void bt_tuple_present_callback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *checkstate)
#define InvalidBtreeLevel
Definition: verify_nbtree.c:51
static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum)
#define IsolationUsesXactSnapshot()
Definition: xact.h:51

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(), BTMetaPageData::btm_fastlevel, BTMetaPageData::btm_fastroot, BTMetaPageData::btm_level, BTMetaPageData::btm_root, BTPageGetMeta, BTREE_METAPAGE, BuildIndexInfo(), CurrentMemoryContext, DEBUG1, elog, ereport, errcode(), ERRCODE_T_R_SERIALIZATION_FAILURE, errdetail_internal(), errhint(), errmsg(), errmsg_internal(), ERROR, 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(), palloc_btree_page(), pg_global_prng_state, pg_prng_uint64(), RelationData::rd_index, RelationData::rd_indextuple, RecentXmin, RegisterSnapshot(), RelationGetNumberOfBlocks, RelationGetRelationName, SnapshotAny, HeapTupleData::t_data, table_beginscan_strat(), table_index_build_scan(), TransactionIdIsValid, TransactionIdPrecedes(), UnregisterSnapshot(), and SnapshotData::xmin.

Referenced by bt_index_check_internal().

◆ bt_check_level_from_leftmost()

static BtreeLevel bt_check_level_from_leftmost ( BtreeCheckState state,
BtreeLevel  level 
)
static

Definition at line 760 of file verify_nbtree.c.

761{
762 /* State to establish early, concerning entire level */
763 BTPageOpaque opaque;
764 MemoryContext oldcontext;
765 BtreeLevel nextleveldown;
766
767 /* Variables for iterating across level using right links */
768 BlockNumber leftcurrent = P_NONE;
769 BlockNumber current = level.leftmost;
770
771 /* Initialize return state */
772 nextleveldown.leftmost = InvalidBlockNumber;
773 nextleveldown.level = InvalidBtreeLevel;
774 nextleveldown.istruerootlevel = false;
775
776 /* Use page-level context for duration of this call */
777 oldcontext = MemoryContextSwitchTo(state->targetcontext);
778
779 elog(DEBUG1, "verifying level %u%s", level.level,
780 level.istruerootlevel ?
781 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
782
783 state->prevrightlink = InvalidBlockNumber;
784 state->previncompletesplit = false;
785
786 do
787 {
788 /* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
790
791 /* Initialize state for this iteration */
792 state->targetblock = current;
793 state->target = palloc_btree_page(state, state->targetblock);
794 state->targetlsn = PageGetLSN(state->target);
795
796 opaque = BTPageGetOpaque(state->target);
797
798 if (P_IGNORE(opaque))
799 {
800 /*
801 * Since there cannot be a concurrent VACUUM operation in readonly
802 * mode, and since a page has no links within other pages
803 * (siblings and parent) once it is marked fully deleted, it
804 * should be impossible to land on a fully deleted page in
805 * readonly mode. See bt_child_check() for further details.
806 *
807 * The bt_child_check() P_ISDELETED() check is repeated here so
808 * that pages that are only reachable through sibling links get
809 * checked.
810 */
811 if (state->readonly && P_ISDELETED(opaque))
813 (errcode(ERRCODE_INDEX_CORRUPTED),
814 errmsg("downlink or sibling link points to deleted block in index \"%s\"",
816 errdetail_internal("Block=%u left block=%u left link from block=%u.",
817 current, leftcurrent, opaque->btpo_prev)));
818
819 if (P_RIGHTMOST(opaque))
821 (errcode(ERRCODE_INDEX_CORRUPTED),
822 errmsg("block %u fell off the end of index \"%s\"",
823 current, RelationGetRelationName(state->rel))));
824 else
826 (errcode(ERRCODE_NO_DATA),
827 errmsg_internal("block %u of index \"%s\" concurrently deleted",
828 current, RelationGetRelationName(state->rel))));
829 goto nextpage;
830 }
831 else if (nextleveldown.leftmost == InvalidBlockNumber)
832 {
833 /*
834 * A concurrent page split could make the caller supplied leftmost
835 * block no longer contain the leftmost page, or no longer be the
836 * true root, but where that isn't possible due to heavyweight
837 * locking, check that the first valid page meets caller's
838 * expectations.
839 */
840 if (state->readonly)
841 {
842 if (!bt_leftmost_ignoring_half_dead(state, current, opaque))
844 (errcode(ERRCODE_INDEX_CORRUPTED),
845 errmsg("block %u is not leftmost in index \"%s\"",
846 current, RelationGetRelationName(state->rel))));
847
848 if (level.istruerootlevel && !P_ISROOT(opaque))
850 (errcode(ERRCODE_INDEX_CORRUPTED),
851 errmsg("block %u is not true root in index \"%s\"",
852 current, RelationGetRelationName(state->rel))));
853 }
854
855 /*
856 * Before beginning any non-trivial examination of level, prepare
857 * state for next bt_check_level_from_leftmost() invocation for
858 * the next level for the next level down (if any).
859 *
860 * There should be at least one non-ignorable page per level,
861 * unless this is the leaf level, which is assumed by caller to be
862 * final level.
863 */
864 if (!P_ISLEAF(opaque))
865 {
866 IndexTuple itup;
867 ItemId itemid;
868
869 /* Internal page -- downlink gets leftmost on next level */
870 itemid = PageGetItemIdCareful(state, state->targetblock,
871 state->target,
872 P_FIRSTDATAKEY(opaque));
873 itup = (IndexTuple) PageGetItem(state->target, itemid);
874 nextleveldown.leftmost = BTreeTupleGetDownLink(itup);
875 nextleveldown.level = opaque->btpo_level - 1;
876 }
877 else
878 {
879 /*
880 * Leaf page -- final level caller must process.
881 *
882 * Note that this could also be the root page, if there has
883 * been no root page split yet.
884 */
885 nextleveldown.leftmost = P_NONE;
886 nextleveldown.level = InvalidBtreeLevel;
887 }
888
889 /*
890 * Finished setting up state for this call/level. Control will
891 * never end up back here in any future loop iteration for this
892 * level.
893 */
894 }
895
896 /*
897 * Sibling links should be in mutual agreement. There arises
898 * leftcurrent == P_NONE && btpo_prev != P_NONE when the left sibling
899 * of the parent's low-key downlink is half-dead. (A half-dead page
900 * has no downlink from its parent.) Under heavyweight locking, the
901 * last bt_leftmost_ignoring_half_dead() validated this btpo_prev.
902 * Without heavyweight locking, validation of the P_NONE case remains
903 * unimplemented.
904 */
905 if (opaque->btpo_prev != leftcurrent && leftcurrent != P_NONE)
906 bt_recheck_sibling_links(state, opaque->btpo_prev, leftcurrent);
907
908 /* Check level */
909 if (level.level != opaque->btpo_level)
911 (errcode(ERRCODE_INDEX_CORRUPTED),
912 errmsg("leftmost down link for level points to block in index \"%s\" whose level is not one level down",
914 errdetail_internal("Block pointed to=%u expected level=%u level in pointed to block=%u.",
915 current, level.level, opaque->btpo_level)));
916
917 /* Verify invariants for page */
919
920nextpage:
921
922 /* Try to detect circular links */
923 if (current == leftcurrent || current == opaque->btpo_prev)
925 (errcode(ERRCODE_INDEX_CORRUPTED),
926 errmsg("circular link chain found in block %u of index \"%s\"",
927 current, RelationGetRelationName(state->rel))));
928
929 leftcurrent = current;
930 current = opaque->btpo_next;
931
932 if (state->lowkey)
933 {
934 Assert(state->readonly);
935 pfree(state->lowkey);
936 state->lowkey = NULL;
937 }
938
939 /*
940 * Copy current target high key as the low key of right sibling.
941 * Allocate memory in upper level context, so it would be cleared
942 * after reset of target context.
943 *
944 * We only need the low key in corner cases of checking child high
945 * keys. We use high key only when incomplete split on the child level
946 * falls to the boundary of pages on the target level. See
947 * bt_child_highkey_check() for details. So, typically we won't end
948 * up doing anything with low key, but it's simpler for general case
949 * high key verification to always have it available.
950 *
951 * The correctness of managing low key in the case of concurrent
952 * splits wasn't investigated yet. Thankfully we only need low key
953 * for readonly verification and concurrent splits won't happen.
954 */
955 if (state->readonly && !P_RIGHTMOST(opaque))
956 {
957 IndexTuple itup;
958 ItemId itemid;
959
960 itemid = PageGetItemIdCareful(state, state->targetblock,
961 state->target, P_HIKEY);
962 itup = (IndexTuple) PageGetItem(state->target, itemid);
963
964 state->lowkey = MemoryContextAlloc(oldcontext, IndexTupleSize(itup));
965 memcpy(state->lowkey, itup, IndexTupleSize(itup));
966 }
967
968 /* Free page and associated memory for this iteration */
969 MemoryContextReset(state->targetcontext);
970 }
971 while (current != P_NONE);
972
973 if (state->lowkey)
974 {
975 Assert(state->readonly);
976 pfree(state->lowkey);
977 state->lowkey = NULL;
978 }
979
980 /* Don't change context for caller */
981 MemoryContextSwitchTo(oldcontext);
982
983 return nextleveldown;
984}
uint32 BlockNumber
Definition: block.h:31
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
Definition: bufpage.h:354
static XLogRecPtr PageGetLSN(const PageData *page)
Definition: bufpage.h:386
IndexTupleData * IndexTuple
Definition: itup.h:53
static Size IndexTupleSize(const IndexTupleData *itup)
Definition: itup.h:71
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1181
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:383
void pfree(void *pointer)
Definition: mcxt.c:1521
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
#define P_ISLEAF(opaque)
Definition: nbtree.h:220
#define P_HIKEY
Definition: nbtree.h:367
#define BTPageGetOpaque(page)
Definition: nbtree.h:73
#define P_ISDELETED(opaque)
Definition: nbtree.h:222
#define P_FIRSTDATAKEY(opaque)
Definition: nbtree.h:369
#define P_ISROOT(opaque)
Definition: nbtree.h:221
#define P_RIGHTMOST(opaque)
Definition: nbtree.h:219
static BlockNumber BTreeTupleGetDownLink(IndexTuple pivot)
Definition: nbtree.h:556
#define P_IGNORE(opaque)
Definition: nbtree.h:225
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
BlockNumber btpo_next
Definition: nbtree.h:65
BlockNumber btpo_prev
Definition: nbtree.h:64
uint32 btpo_level
Definition: nbtree.h:66
static bool bt_leftmost_ignoring_half_dead(BtreeCheckState *state, BlockNumber start, BTPageOpaque start_opaque)
static void bt_target_page_check(BtreeCheckState *state)
static ItemId PageGetItemIdCareful(BtreeCheckState *state, BlockNumber block, Page page, OffsetNumber offset)
static void bt_recheck_sibling_links(BtreeCheckState *state, BlockNumber btpo_prev_from_target, BlockNumber leftcurrent)

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, IndexTupleSize(), InvalidBlockNumber, InvalidBtreeLevel, BtreeLevel::istruerootlevel, BtreeLevel::leftmost, BtreeLevel::level, MemoryContextAlloc(), MemoryContextReset(), MemoryContextSwitchTo(), P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, 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 void bt_child_check ( BtreeCheckState state,
BTScanInsert  targetkey,
OffsetNumber  downlinkoffnum 
)
static

Definition at line 2531 of file verify_nbtree.c.

2533{
2534 ItemId itemid;
2535 IndexTuple itup;
2536 BlockNumber childblock;
2537 OffsetNumber offset;
2538 OffsetNumber maxoffset;
2539 Page child;
2540 BTPageOpaque copaque;
2541 BTPageOpaque topaque;
2542
2543 itemid = PageGetItemIdCareful(state, state->targetblock,
2544 state->target, downlinkoffnum);
2545 itup = (IndexTuple) PageGetItem(state->target, itemid);
2546 childblock = BTreeTupleGetDownLink(itup);
2547
2548 /*
2549 * Caller must have ShareLock on target relation, because of
2550 * considerations around page deletion by VACUUM.
2551 *
2552 * NB: In general, page deletion deletes the right sibling's downlink, not
2553 * the downlink of the page being deleted; the deleted page's downlink is
2554 * reused for its sibling. The key space is thereby consolidated between
2555 * the deleted page and its right sibling. (We cannot delete a parent
2556 * page's rightmost child unless it is the last child page, and we intend
2557 * to also delete the parent itself.)
2558 *
2559 * If this verification happened without a ShareLock, the following race
2560 * condition could cause false positives:
2561 *
2562 * In general, concurrent page deletion might occur, including deletion of
2563 * the left sibling of the child page that is examined here. If such a
2564 * page deletion were to occur, closely followed by an insertion into the
2565 * newly expanded key space of the child, a window for the false positive
2566 * opens up: the stale parent/target downlink originally followed to get
2567 * to the child legitimately ceases to be a lower bound on all items in
2568 * the page, since the key space was concurrently expanded "left".
2569 * (Insertion followed the "new" downlink for the child, not our now-stale
2570 * downlink, which was concurrently physically removed in target/parent as
2571 * part of deletion's first phase.)
2572 *
2573 * While we use various techniques elsewhere to perform cross-page
2574 * verification for !readonly callers, a similar trick seems difficult
2575 * here. The tricks used by bt_recheck_sibling_links and by
2576 * bt_right_page_check_scankey both involve verification of a same-level,
2577 * cross-sibling invariant. Cross-level invariants are far more squishy,
2578 * though. The nbtree REDO routines do not actually couple buffer locks
2579 * across levels during page splits, so making any cross-level check work
2580 * reliably in !readonly mode may be impossible.
2581 */
2582 Assert(state->readonly);
2583
2584 /*
2585 * Verify child page has the downlink key from target page (its parent) as
2586 * a lower bound; downlink must be strictly less than all keys on the
2587 * page.
2588 *
2589 * Check all items, rather than checking just the first and trusting that
2590 * the operator class obeys the transitive law.
2591 */
2592 topaque = BTPageGetOpaque(state->target);
2593 child = palloc_btree_page(state, childblock);
2594 copaque = BTPageGetOpaque(child);
2595 maxoffset = PageGetMaxOffsetNumber(child);
2596
2597 /*
2598 * Since we've already loaded the child block, combine this check with
2599 * check for downlink connectivity.
2600 */
2601 bt_child_highkey_check(state, downlinkoffnum,
2602 child, topaque->btpo_level);
2603
2604 /*
2605 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2606 * and since a page has no links within other pages (siblings and parent)
2607 * once it is marked fully deleted, it should be impossible to land on a
2608 * fully deleted page.
2609 *
2610 * It does not quite make sense to enforce that the page cannot even be
2611 * half-dead, despite the fact the downlink is modified at the same stage
2612 * that the child leaf page is marked half-dead. That's incorrect because
2613 * there may occasionally be multiple downlinks from a chain of pages
2614 * undergoing deletion, where multiple successive calls are made to
2615 * _bt_unlink_halfdead_page() by VACUUM before it can finally safely mark
2616 * the leaf page as fully dead. While _bt_mark_page_halfdead() usually
2617 * removes the downlink to the leaf page that is marked half-dead, that's
2618 * not guaranteed, so it's possible we'll land on a half-dead page with a
2619 * downlink due to an interrupted multi-level page deletion.
2620 *
2621 * We go ahead with our checks if the child page is half-dead. It's safe
2622 * to do so because we do not test the child's high key, so it does not
2623 * matter that the original high key will have been replaced by a dummy
2624 * truncated high key within _bt_mark_page_halfdead(). All other page
2625 * items are left intact on a half-dead page, so there is still something
2626 * to test.
2627 */
2628 if (P_ISDELETED(copaque))
2629 ereport(ERROR,
2630 (errcode(ERRCODE_INDEX_CORRUPTED),
2631 errmsg("downlink to deleted page found in index \"%s\"",
2633 errdetail_internal("Parent block=%u child block=%u parent page lsn=%X/%X.",
2634 state->targetblock, childblock,
2635 LSN_FORMAT_ARGS(state->targetlsn))));
2636
2637 for (offset = P_FIRSTDATAKEY(copaque);
2638 offset <= maxoffset;
2639 offset = OffsetNumberNext(offset))
2640 {
2641 /*
2642 * Skip comparison of target page key against "negative infinity"
2643 * item, if any. Checking it would indicate that it's not a strict
2644 * lower bound, but that's only because of the hard-coding for
2645 * negative infinity items within _bt_compare().
2646 *
2647 * If nbtree didn't truncate negative infinity tuples during internal
2648 * page splits then we'd expect child's negative infinity key to be
2649 * equal to the scankey/downlink from target/parent (it would be a
2650 * "low key" in this hypothetical scenario, and so it would still need
2651 * to be treated as a special case here).
2652 *
2653 * Negative infinity items can be thought of as a strict lower bound
2654 * that works transitively, with the last non-negative-infinity pivot
2655 * followed during a descent from the root as its "true" strict lower
2656 * bound. Only a small number of negative infinity items are truly
2657 * negative infinity; those that are the first items of leftmost
2658 * internal pages. In more general terms, a negative infinity item is
2659 * only negative infinity with respect to the subtree that the page is
2660 * at the root of.
2661 *
2662 * See also: bt_rootdescend(), which can even detect transitive
2663 * inconsistencies on cousin leaf pages.
2664 */
2665 if (offset_is_negative_infinity(copaque, offset))
2666 continue;
2667
2668 if (!invariant_l_nontarget_offset(state, targetkey, childblock, child,
2669 offset))
2670 ereport(ERROR,
2671 (errcode(ERRCODE_INDEX_CORRUPTED),
2672 errmsg("down-link lower bound invariant violated for index \"%s\"",
2674 errdetail_internal("Parent block=%u child index tid=(%u,%u) parent page lsn=%X/%X.",
2675 state->targetblock, childblock, offset,
2676 LSN_FORMAT_ARGS(state->targetlsn))));
2677 }
2678
2679 pfree(child);
2680}
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
Definition: bufpage.h:372
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
uint16 OffsetNumber
Definition: off.h:24
static bool offset_is_negative_infinity(BTPageOpaque opaque, OffsetNumber offset)
static void bt_child_highkey_check(BtreeCheckState *state, OffsetNumber target_downlinkoffnum, Page loaded_child, uint32 target_level)
static bool invariant_l_nontarget_offset(BtreeCheckState *state, BTScanInsert key, BlockNumber nontargetblock, Page nontarget, OffsetNumber upperbound)
#define LSN_FORMAT_ARGS(lsn)
Definition: xlogdefs.h:43

References Assert, bt_child_highkey_check(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTreeTupleGetDownLink(), ereport, errcode(), errdetail_internal(), errmsg(), ERROR, 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 void bt_child_highkey_check ( BtreeCheckState state,
OffsetNumber  target_downlinkoffnum,
Page  loaded_child,
uint32  target_level 
)
static

Definition at line 2284 of file verify_nbtree.c.

2288{
2289 BlockNumber blkno = state->prevrightlink;
2290 Page page;
2291 BTPageOpaque opaque;
2292 bool rightsplit = state->previncompletesplit;
2293 bool first = true;
2294 ItemId itemid;
2295 IndexTuple itup;
2296 BlockNumber downlink;
2297
2298 if (OffsetNumberIsValid(target_downlinkoffnum))
2299 {
2300 itemid = PageGetItemIdCareful(state, state->targetblock,
2301 state->target, target_downlinkoffnum);
2302 itup = (IndexTuple) PageGetItem(state->target, itemid);
2303 downlink = BTreeTupleGetDownLink(itup);
2304 }
2305 else
2306 {
2307 downlink = P_NONE;
2308 }
2309
2310 /*
2311 * If no previous rightlink is memorized for current level just below
2312 * target page's level, we are about to start from the leftmost page. We
2313 * can't follow rightlinks from previous page, because there is no
2314 * previous page. But we still can match high key.
2315 *
2316 * So we initialize variables for the loop above like there is previous
2317 * page referencing current child. Also we imply previous page to not
2318 * have incomplete split flag, that would make us require downlink for
2319 * current child. That's correct, because leftmost page on the level
2320 * should always have parent downlink.
2321 */
2322 if (!BlockNumberIsValid(blkno))
2323 {
2324 blkno = downlink;
2325 rightsplit = false;
2326 }
2327
2328 /* Move to the right on the child level */
2329 while (true)
2330 {
2331 /*
2332 * Did we traverse the whole tree level and this is check for pages to
2333 * the right of rightmost downlink?
2334 */
2335 if (blkno == P_NONE && downlink == P_NONE)
2336 {
2337 state->prevrightlink = InvalidBlockNumber;
2338 state->previncompletesplit = false;
2339 return;
2340 }
2341
2342 /* Did we traverse the whole tree level and don't find next downlink? */
2343 if (blkno == P_NONE)
2344 ereport(ERROR,
2345 (errcode(ERRCODE_INDEX_CORRUPTED),
2346 errmsg("can't traverse from downlink %u to downlink %u of index \"%s\"",
2347 state->prevrightlink, downlink,
2349
2350 /* Load page contents */
2351 if (blkno == downlink && loaded_child)
2352 page = loaded_child;
2353 else
2354 page = palloc_btree_page(state, blkno);
2355
2356 opaque = BTPageGetOpaque(page);
2357
2358 /* The first page we visit at the level should be leftmost */
2359 if (first && !BlockNumberIsValid(state->prevrightlink) &&
2360 !bt_leftmost_ignoring_half_dead(state, blkno, opaque))
2361 ereport(ERROR,
2362 (errcode(ERRCODE_INDEX_CORRUPTED),
2363 errmsg("the first child of leftmost target page is not leftmost of its level in index \"%s\"",
2365 errdetail_internal("Target block=%u child block=%u target page lsn=%X/%X.",
2366 state->targetblock, blkno,
2367 LSN_FORMAT_ARGS(state->targetlsn))));
2368
2369 /* Do level sanity check */
2370 if ((!P_ISDELETED(opaque) || P_HAS_FULLXID(opaque)) &&
2371 opaque->btpo_level != target_level - 1)
2372 ereport(ERROR,
2373 (errcode(ERRCODE_INDEX_CORRUPTED),
2374 errmsg("block found while following rightlinks from child of index \"%s\" has invalid level",
2376 errdetail_internal("Block pointed to=%u expected level=%u level in pointed to block=%u.",
2377 blkno, target_level - 1, opaque->btpo_level)));
2378
2379 /* Try to detect circular links */
2380 if ((!first && blkno == state->prevrightlink) || blkno == opaque->btpo_prev)
2381 ereport(ERROR,
2382 (errcode(ERRCODE_INDEX_CORRUPTED),
2383 errmsg("circular link chain found in block %u of index \"%s\"",
2384 blkno, RelationGetRelationName(state->rel))));
2385
2386 if (blkno != downlink && !P_IGNORE(opaque))
2387 {
2388 /* blkno probably has missing parent downlink */
2389 bt_downlink_missing_check(state, rightsplit, blkno, page);
2390 }
2391
2392 rightsplit = P_INCOMPLETE_SPLIT(opaque);
2393
2394 /*
2395 * If we visit page with high key, check that it is equal to the
2396 * target key next to corresponding downlink.
2397 */
2398 if (!rightsplit && !P_RIGHTMOST(opaque))
2399 {
2400 BTPageOpaque topaque;
2401 IndexTuple highkey;
2402 OffsetNumber pivotkey_offset;
2403
2404 /* Get high key */
2405 itemid = PageGetItemIdCareful(state, blkno, page, P_HIKEY);
2406 highkey = (IndexTuple) PageGetItem(page, itemid);
2407
2408 /*
2409 * There might be two situations when we examine high key. If
2410 * current child page is referenced by given target downlink, we
2411 * should look to the next offset number for matching key from
2412 * target page.
2413 *
2414 * Alternatively, we're following rightlinks somewhere in the
2415 * middle between page referenced by previous target's downlink
2416 * and the page referenced by current target's downlink. If
2417 * current child page hasn't incomplete split flag set, then its
2418 * high key should match to the target's key of current offset
2419 * number. This happens when a previous call here (to
2420 * bt_child_highkey_check()) found an incomplete split, and we
2421 * reach a right sibling page without a downlink -- the right
2422 * sibling page's high key still needs to be matched to a
2423 * separator key on the parent/target level.
2424 *
2425 * Don't apply OffsetNumberNext() to target_downlinkoffnum when we
2426 * already had to step right on the child level. Our traversal of
2427 * the child level must try to move in perfect lockstep behind (to
2428 * the left of) the target/parent level traversal.
2429 */
2430 if (blkno == downlink)
2431 pivotkey_offset = OffsetNumberNext(target_downlinkoffnum);
2432 else
2433 pivotkey_offset = target_downlinkoffnum;
2434
2435 topaque = BTPageGetOpaque(state->target);
2436
2437 if (!offset_is_negative_infinity(topaque, pivotkey_offset))
2438 {
2439 /*
2440 * If we're looking for the next pivot tuple in target page,
2441 * but there is no more pivot tuples, then we should match to
2442 * high key instead.
2443 */
2444 if (pivotkey_offset > PageGetMaxOffsetNumber(state->target))
2445 {
2446 if (P_RIGHTMOST(topaque))
2447 ereport(ERROR,
2448 (errcode(ERRCODE_INDEX_CORRUPTED),
2449 errmsg("child high key is greater than rightmost pivot key on target level in index \"%s\"",
2451 errdetail_internal("Target block=%u child block=%u target page lsn=%X/%X.",
2452 state->targetblock, blkno,
2453 LSN_FORMAT_ARGS(state->targetlsn))));
2454 pivotkey_offset = P_HIKEY;
2455 }
2456 itemid = PageGetItemIdCareful(state, state->targetblock,
2457 state->target, pivotkey_offset);
2458 itup = (IndexTuple) PageGetItem(state->target, itemid);
2459 }
2460 else
2461 {
2462 /*
2463 * We cannot try to match child's high key to a negative
2464 * infinity key in target, since there is nothing to compare.
2465 * However, it's still possible to match child's high key
2466 * outside of target page. The reason why we're are is that
2467 * bt_child_highkey_check() was previously called for the
2468 * cousin page of 'loaded_child', which is incomplete split.
2469 * So, now we traverse to the right of that cousin page and
2470 * current child level page under consideration still belongs
2471 * to the subtree of target's left sibling. Thus, we need to
2472 * match child's high key to its left uncle page high key.
2473 * Thankfully we saved it, it's called a "low key" of target
2474 * page.
2475 */
2476 if (!state->lowkey)
2477 ereport(ERROR,
2478 (errcode(ERRCODE_INDEX_CORRUPTED),
2479 errmsg("can't find left sibling high key in index \"%s\"",
2481 errdetail_internal("Target block=%u child block=%u target page lsn=%X/%X.",
2482 state->targetblock, blkno,
2483 LSN_FORMAT_ARGS(state->targetlsn))));
2484 itup = state->lowkey;
2485 }
2486
2487 if (!bt_pivot_tuple_identical(state->heapkeyspace, highkey, itup))
2488 {
2489 ereport(ERROR,
2490 (errcode(ERRCODE_INDEX_CORRUPTED),
2491 errmsg("mismatch between parent key and child high key in index \"%s\"",
2493 errdetail_internal("Target block=%u child block=%u target page lsn=%X/%X.",
2494 state->targetblock, blkno,
2495 LSN_FORMAT_ARGS(state->targetlsn))));
2496 }
2497 }
2498
2499 /* Exit if we already found next downlink */
2500 if (blkno == downlink)
2501 {
2502 state->prevrightlink = opaque->btpo_next;
2503 state->previncompletesplit = rightsplit;
2504 return;
2505 }
2506
2507 /* Traverse to the next page using rightlink */
2508 blkno = opaque->btpo_next;
2509
2510 /* Free page contents if it's allocated by us */
2511 if (page != loaded_child)
2512 pfree(page);
2513 first = false;
2514 }
2515}
static bool BlockNumberIsValid(BlockNumber blockNumber)
Definition: block.h:71
#define P_HAS_FULLXID(opaque)
Definition: nbtree.h:228
#define P_INCOMPLETE_SPLIT(opaque)
Definition: nbtree.h:227
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:39
static bool bt_pivot_tuple_identical(bool heapkeyspace, IndexTuple itup1, IndexTuple itup2)
static void bt_downlink_missing_check(BtreeCheckState *state, bool rightsplit, BlockNumber blkno, Page page)

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, InvalidBlockNumber, LSN_FORMAT_ARGS, offset_is_negative_infinity(), OffsetNumberIsValid, OffsetNumberNext, P_HAS_FULLXID, P_HIKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_ISDELETED, 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 void bt_downlink_missing_check ( BtreeCheckState state,
bool  rightsplit,
BlockNumber  blkno,
Page  page 
)
static

Definition at line 2696 of file verify_nbtree.c.

2698{
2699 BTPageOpaque opaque = BTPageGetOpaque(page);
2700 ItemId itemid;
2701 IndexTuple itup;
2702 Page child;
2703 BTPageOpaque copaque;
2704 uint32 level;
2705 BlockNumber childblk;
2706 XLogRecPtr pagelsn;
2707
2708 Assert(state->readonly);
2709 Assert(!P_IGNORE(opaque));
2710
2711 /* No next level up with downlinks to fingerprint from the true root */
2712 if (P_ISROOT(opaque))
2713 return;
2714
2715 pagelsn = PageGetLSN(page);
2716
2717 /*
2718 * Incomplete (interrupted) page splits can account for the lack of a
2719 * downlink. Some inserting transaction should eventually complete the
2720 * page split in passing, when it notices that the left sibling page is
2721 * P_INCOMPLETE_SPLIT().
2722 *
2723 * In general, VACUUM is not prepared for there to be no downlink to a
2724 * page that it deletes. This is the main reason why the lack of a
2725 * downlink can be reported as corruption here. It's not obvious that an
2726 * invalid missing downlink can result in wrong answers to queries,
2727 * though, since index scans that land on the child may end up
2728 * consistently moving right. The handling of concurrent page splits (and
2729 * page deletions) within _bt_moveright() cannot distinguish
2730 * inconsistencies that last for a moment from inconsistencies that are
2731 * permanent and irrecoverable.
2732 *
2733 * VACUUM isn't even prepared to delete pages that have no downlink due to
2734 * an incomplete page split, but it can detect and reason about that case
2735 * by design, so it shouldn't be taken to indicate corruption. See
2736 * _bt_pagedel() for full details.
2737 */
2738 if (rightsplit)
2739 {
2741 (errcode(ERRCODE_NO_DATA),
2742 errmsg_internal("harmless interrupted page split detected in index \"%s\"",
2744 errdetail_internal("Block=%u level=%u left sibling=%u page lsn=%X/%X.",
2745 blkno, opaque->btpo_level,
2746 opaque->btpo_prev,
2747 LSN_FORMAT_ARGS(pagelsn))));
2748 return;
2749 }
2750
2751 /*
2752 * Page under check is probably the "top parent" of a multi-level page
2753 * deletion. We'll need to descend the subtree to make sure that
2754 * descendant pages are consistent with that, though.
2755 *
2756 * If the page (which must be non-ignorable) is a leaf page, then clearly
2757 * it can't be the top parent. The lack of a downlink is probably a
2758 * symptom of a broad problem that could just as easily cause
2759 * inconsistencies anywhere else.
2760 */
2761 if (P_ISLEAF(opaque))
2762 ereport(ERROR,
2763 (errcode(ERRCODE_INDEX_CORRUPTED),
2764 errmsg("leaf index block lacks downlink in index \"%s\"",
2766 errdetail_internal("Block=%u page lsn=%X/%X.",
2767 blkno,
2768 LSN_FORMAT_ARGS(pagelsn))));
2769
2770 /* Descend from the given page, which is an internal page */
2771 elog(DEBUG1, "checking for interrupted multi-level deletion due to missing downlink in index \"%s\"",
2773
2774 level = opaque->btpo_level;
2775 itemid = PageGetItemIdCareful(state, blkno, page, P_FIRSTDATAKEY(opaque));
2776 itup = (IndexTuple) PageGetItem(page, itemid);
2777 childblk = BTreeTupleGetDownLink(itup);
2778 for (;;)
2779 {
2781
2782 child = palloc_btree_page(state, childblk);
2783 copaque = BTPageGetOpaque(child);
2784
2785 if (P_ISLEAF(copaque))
2786 break;
2787
2788 /* Do an extra sanity check in passing on internal pages */
2789 if (copaque->btpo_level != level - 1)
2790 ereport(ERROR,
2791 (errcode(ERRCODE_INDEX_CORRUPTED),
2792 errmsg_internal("downlink points to block in index \"%s\" whose level is not one level down",
2794 errdetail_internal("Top parent/under check block=%u block pointed to=%u expected level=%u level in pointed to block=%u.",
2795 blkno, childblk,
2796 level - 1, copaque->btpo_level)));
2797
2798 level = copaque->btpo_level;
2799 itemid = PageGetItemIdCareful(state, childblk, child,
2800 P_FIRSTDATAKEY(copaque));
2801 itup = (IndexTuple) PageGetItem(child, itemid);
2802 childblk = BTreeTupleGetDownLink(itup);
2803 /* Be slightly more pro-active in freeing this memory, just in case */
2804 pfree(child);
2805 }
2806
2807 /*
2808 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2809 * and since a page has no links within other pages (siblings and parent)
2810 * once it is marked fully deleted, it should be impossible to land on a
2811 * fully deleted page. See bt_child_check() for further details.
2812 *
2813 * The bt_child_check() P_ISDELETED() check is repeated here because
2814 * bt_child_check() does not visit pages reachable through negative
2815 * infinity items. Besides, bt_child_check() is unwilling to descend
2816 * multiple levels. (The similar bt_child_check() P_ISDELETED() check
2817 * within bt_check_level_from_leftmost() won't reach the page either,
2818 * since the leaf's live siblings should have their sibling links updated
2819 * to bypass the deletion target page when it is marked fully dead.)
2820 *
2821 * If this error is raised, it might be due to a previous multi-level page
2822 * deletion that failed to realize that it wasn't yet safe to mark the
2823 * leaf page as fully dead. A "dangling downlink" will still remain when
2824 * this happens. The fact that the dangling downlink's page (the leaf's
2825 * parent/ancestor page) lacked a downlink is incidental.
2826 */
2827 if (P_ISDELETED(copaque))
2828 ereport(ERROR,
2829 (errcode(ERRCODE_INDEX_CORRUPTED),
2830 errmsg_internal("downlink to deleted leaf page found in index \"%s\"",
2832 errdetail_internal("Top parent/target block=%u leaf block=%u top parent/under check lsn=%X/%X.",
2833 blkno, childblk,
2834 LSN_FORMAT_ARGS(pagelsn))));
2835
2836 /*
2837 * Iff leaf page is half-dead, its high key top parent link should point
2838 * to what VACUUM considered to be the top parent page at the instant it
2839 * was interrupted. Provided the high key link actually points to the
2840 * page under check, the missing downlink we detected is consistent with
2841 * there having been an interrupted multi-level page deletion. This means
2842 * that the subtree with the page under check at its root (a page deletion
2843 * chain) is in a consistent state, enabling VACUUM to resume deleting the
2844 * entire chain the next time it encounters the half-dead leaf page.
2845 */
2846 if (P_ISHALFDEAD(copaque) && !P_RIGHTMOST(copaque))
2847 {
2848 itemid = PageGetItemIdCareful(state, childblk, child, P_HIKEY);
2849 itup = (IndexTuple) PageGetItem(child, itemid);
2850 if (BTreeTupleGetTopParent(itup) == blkno)
2851 return;
2852 }
2853
2854 ereport(ERROR,
2855 (errcode(ERRCODE_INDEX_CORRUPTED),
2856 errmsg("internal index block lacks downlink in index \"%s\"",
2858 errdetail_internal("Block=%u level=%u page lsn=%X/%X.",
2859 blkno, opaque->btpo_level,
2860 LSN_FORMAT_ARGS(pagelsn))));
2861}
#define P_ISHALFDEAD(opaque)
Definition: nbtree.h:224
static BlockNumber BTreeTupleGetTopParent(IndexTuple leafhikey)
Definition: nbtree.h:620
uint64 XLogRecPtr
Definition: xlogdefs.h:21

References Assert, BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_prev, BTreeTupleGetDownLink(), BTreeTupleGetTopParent(), CHECK_FOR_INTERRUPTS, DEBUG1, elog, ereport, errcode(), errdetail_internal(), errmsg(), errmsg_internal(), ERROR, 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 void bt_entry_unique_check ( BtreeCheckState state,
IndexTuple  itup,
BlockNumber  targetblock,
OffsetNumber  offset,
BtreeLastVisibleEntry lVis 
)
static

Definition at line 1047 of file verify_nbtree.c.

1050{
1051 ItemPointer tid;
1052 bool has_visible_entry = false;
1053
1054 Assert(targetblock != P_NONE);
1055
1056 /*
1057 * Current tuple has posting list. Report duplicate if TID of any posting
1058 * list entry is visible and lVis->tid is valid.
1059 */
1060 if (BTreeTupleIsPosting(itup))
1061 {
1062 for (int i = 0; i < BTreeTupleGetNPosting(itup); i++)
1063 {
1064 tid = BTreeTupleGetPostingN(itup, i);
1065 if (heap_entry_is_visible(state, tid))
1066 {
1067 has_visible_entry = true;
1068 if (ItemPointerIsValid(lVis->tid))
1069 {
1071 lVis,
1072 tid, targetblock,
1073 offset, i);
1074 }
1075
1076 /*
1077 * Prevent double reporting unique constraint violation
1078 * between the posting list entries of the first tuple on the
1079 * page after cross-page check.
1080 */
1081 if (lVis->blkno != targetblock && ItemPointerIsValid(lVis->tid))
1082 return;
1083
1084 lVis->blkno = targetblock;
1085 lVis->offset = offset;
1086 lVis->postingIndex = i;
1087 lVis->tid = tid;
1088 }
1089 }
1090 }
1091
1092 /*
1093 * Current tuple has no posting list. If TID is visible save info about it
1094 * for the next comparisons in the loop in bt_target_page_check(). Report
1095 * duplicate if lVis->tid is already valid.
1096 */
1097 else
1098 {
1099 tid = BTreeTupleGetHeapTID(itup);
1100 if (heap_entry_is_visible(state, tid))
1101 {
1102 has_visible_entry = true;
1103 if (ItemPointerIsValid(lVis->tid))
1104 {
1106 lVis,
1107 tid, targetblock,
1108 offset, -1);
1109 }
1110
1111 lVis->blkno = targetblock;
1112 lVis->offset = offset;
1113 lVis->tid = tid;
1114 lVis->postingIndex = -1;
1115 }
1116 }
1117
1118 if (!has_visible_entry &&
1119 lVis->blkno != InvalidBlockNumber &&
1120 lVis->blkno != targetblock)
1121 {
1122 char *posting = "";
1123
1124 if (lVis->postingIndex >= 0)
1125 posting = psprintf(" posting %u", lVis->postingIndex);
1127 (errcode(ERRCODE_NO_DATA),
1128 errmsg("index uniqueness can not be checked for index tid=(%u,%u) in index \"%s\"",
1129 targetblock, offset,
1131 errdetail("It doesn't have visible heap tids and key is equal to the tid=(%u,%u)%s (points to heap tid=(%u,%u)).",
1132 lVis->blkno, lVis->offset, posting,
1135 errhint("VACUUM the table and repeat the check.")));
1136 }
1137}
int errdetail(const char *fmt,...)
Definition: elog.c:1203
int i
Definition: isn.c:72
static OffsetNumber ItemPointerGetOffsetNumberNoCheck(const ItemPointerData *pointer)
Definition: itemptr.h:114
static BlockNumber ItemPointerGetBlockNumberNoCheck(const ItemPointerData *pointer)
Definition: itemptr.h:93
static bool ItemPointerIsValid(const ItemPointerData *pointer)
Definition: itemptr.h:83
static uint16 BTreeTupleGetNPosting(IndexTuple posting)
Definition: nbtree.h:518
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
Definition: nbtree.h:544
static bool BTreeTupleIsPosting(IndexTuple itup)
Definition: nbtree.h:492
static ItemPointer BTreeTupleGetHeapTID(IndexTuple itup)
Definition: nbtree.h:638
char * psprintf(const char *fmt,...)
Definition: psprintf.c:43
static void bt_report_duplicate(BtreeCheckState *state, BtreeLastVisibleEntry *lVis, ItemPointer nexttid, BlockNumber nblock, OffsetNumber noffset, int nposting)
static bool heap_entry_is_visible(BtreeCheckState *state, ItemPointer tid)

References Assert, BtreeLastVisibleEntry::blkno, bt_report_duplicate(), BTreeTupleGetHeapTID(), BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), DEBUG1, ereport, errcode(), errdetail(), errhint(), errmsg(), heap_entry_is_visible(), i, InvalidBlockNumber, ItemPointerGetBlockNumberNoCheck(), ItemPointerGetOffsetNumberNoCheck(), ItemPointerIsValid(), BtreeLastVisibleEntry::offset, P_NONE, BtreeLastVisibleEntry::postingIndex, psprintf(), RelationGetRelationName, and BtreeLastVisibleEntry::tid.

Referenced by bt_target_page_check().

◆ bt_index_check()

Datum bt_index_check ( PG_FUNCTION_ARGS  )

Definition at line 238 of file verify_nbtree.c.

239{
240 Oid indrelid = PG_GETARG_OID(0);
241 bool heapallindexed = false;
242 bool checkunique = false;
243
244 if (PG_NARGS() >= 2)
245 heapallindexed = PG_GETARG_BOOL(1);
246 if (PG_NARGS() == 3)
247 checkunique = PG_GETARG_BOOL(2);
248
249 bt_index_check_internal(indrelid, false, heapallindexed, false, checkunique);
250
252}
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_OID(n)
Definition: fmgr.h:275
#define PG_NARGS()
Definition: fmgr.h:203
#define PG_GETARG_BOOL(n)
Definition: fmgr.h:274
unsigned int Oid
Definition: postgres_ext.h:32
static void bt_index_check_internal(Oid indrelid, bool parentcheck, bool heapallindexed, bool rootdescend, bool checkunique)

References bt_index_check_internal(), PG_GETARG_BOOL, PG_GETARG_OID, PG_NARGS, and PG_RETURN_VOID.

◆ bt_index_check_internal()

static void bt_index_check_internal ( Oid  indrelid,
bool  parentcheck,
bool  heapallindexed,
bool  rootdescend,
bool  checkunique 
)
static

Definition at line 287 of file verify_nbtree.c.

289{
290 Oid heapid;
291 Relation indrel;
292 Relation heaprel;
293 LOCKMODE lockmode;
294 Oid save_userid;
295 int save_sec_context;
296 int save_nestlevel;
297
298 if (parentcheck)
299 lockmode = ShareLock;
300 else
301 lockmode = AccessShareLock;
302
303 /*
304 * We must lock table before index to avoid deadlocks. However, if the
305 * passed indrelid isn't an index then IndexGetRelation() will fail.
306 * Rather than emitting a not-very-helpful error message, postpone
307 * complaining, expecting that the is-it-an-index test below will fail.
308 *
309 * In hot standby mode this will raise an error when parentcheck is true.
310 */
311 heapid = IndexGetRelation(indrelid, true);
312 if (OidIsValid(heapid))
313 {
314 heaprel = table_open(heapid, lockmode);
315
316 /*
317 * Switch to the table owner's userid, so that any index functions are
318 * run as that user. Also lock down security-restricted operations
319 * and arrange to make GUC variable changes local to this command.
320 */
321 GetUserIdAndSecContext(&save_userid, &save_sec_context);
322 SetUserIdAndSecContext(heaprel->rd_rel->relowner,
323 save_sec_context | SECURITY_RESTRICTED_OPERATION);
324 save_nestlevel = NewGUCNestLevel();
326 }
327 else
328 {
329 heaprel = NULL;
330 /* Set these just to suppress "uninitialized variable" warnings */
331 save_userid = InvalidOid;
332 save_sec_context = -1;
333 save_nestlevel = -1;
334 }
335
336 /*
337 * Open the target index relations separately (like relation_openrv(), but
338 * with heap relation locked first to prevent deadlocking). In hot
339 * standby mode this will raise an error when parentcheck is true.
340 *
341 * There is no need for the usual indcheckxmin usability horizon test
342 * here, even in the heapallindexed case, because index undergoing
343 * verification only needs to have entries for a new transaction snapshot.
344 * (If this is a parentcheck verification, there is no question about
345 * committed or recently dead heap tuples lacking index entries due to
346 * concurrent activity.)
347 */
348 indrel = index_open(indrelid, lockmode);
349
350 /*
351 * Since we did the IndexGetRelation call above without any lock, it's
352 * barely possible that a race against an index drop/recreation could have
353 * netted us the wrong table.
354 */
355 if (heaprel == NULL || heapid != IndexGetRelation(indrelid, false))
358 errmsg("could not open parent table of index \"%s\"",
359 RelationGetRelationName(indrel))));
360
361 /* Relation suitable for checking as B-Tree? */
362 btree_index_checkable(indrel);
363
365 {
366 bool heapkeyspace,
367 allequalimage;
368
371 (errcode(ERRCODE_INDEX_CORRUPTED),
372 errmsg("index \"%s\" lacks a main relation fork",
373 RelationGetRelationName(indrel))));
374
375 /* Extract metadata from metapage, and sanitize it in passing */
376 _bt_metaversion(indrel, &heapkeyspace, &allequalimage);
377 if (allequalimage && !heapkeyspace)
379 (errcode(ERRCODE_INDEX_CORRUPTED),
380 errmsg("index \"%s\" metapage has equalimage field set on unsupported nbtree version",
381 RelationGetRelationName(indrel))));
382 if (allequalimage && !_bt_allequalimage(indrel, false))
383 {
384 bool has_interval_ops = false;
385
386 for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(indrel); i++)
387 if (indrel->rd_opfamily[i] == INTERVAL_BTREE_FAM_OID)
388 has_interval_ops = true;
390 (errcode(ERRCODE_INDEX_CORRUPTED),
391 errmsg("index \"%s\" metapage incorrectly indicates that deduplication is safe",
393 has_interval_ops
394 ? errhint("This is known of \"interval\" indexes last built on a version predating 2023-11.")
395 : 0));
396 }
397
398 /* Check index, possibly against table it is an index on */
399 bt_check_every_level(indrel, heaprel, heapkeyspace, parentcheck,
400 heapallindexed, rootdescend, checkunique);
401 }
402
403 /* Roll back any GUC changes executed by index functions */
404 AtEOXact_GUC(false, save_nestlevel);
405
406 /* Restore userid and security context */
407 SetUserIdAndSecContext(save_userid, save_sec_context);
408
409 /*
410 * Release locks early. That's ok here because nothing in the called
411 * routines will trigger shared cache invalidations to be sent, so we can
412 * relax the usual pattern of only releasing locks after commit.
413 */
414 index_close(indrel, lockmode);
415 if (heaprel)
416 table_close(heaprel, lockmode);
417}
#define OidIsValid(objectId)
Definition: c.h:732
int NewGUCNestLevel(void)
Definition: guc.c:2235
void RestrictSearchPath(void)
Definition: guc.c:2246
void AtEOXact_GUC(bool isCommit, int nestLevel)
Definition: guc.c:2262
Oid IndexGetRelation(Oid indexId, bool missing_ok)
Definition: index.c:3554
void index_close(Relation relation, LOCKMODE lockmode)
Definition: indexam.c:177
Relation index_open(Oid relationId, LOCKMODE lockmode)
Definition: indexam.c:133
int LOCKMODE
Definition: lockdefs.h:26
#define AccessShareLock
Definition: lockdefs.h:36
#define ShareLock
Definition: lockdefs.h:40
#define SECURITY_RESTRICTED_OPERATION
Definition: miscadmin.h:318
void GetUserIdAndSecContext(Oid *userid, int *sec_context)
Definition: miscinit.c:660
void SetUserIdAndSecContext(Oid userid, int sec_context)
Definition: miscinit.c:667
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
Definition: nbtpage.c:739
bool _bt_allequalimage(Relation rel, bool debugmessage)
Definition: nbtutils.c:3297
#define ERRCODE_UNDEFINED_TABLE
Definition: pgbench.c:78
#define InvalidOid
Definition: postgres_ext.h:37
static SMgrRelation RelationGetSmgr(Relation rel)
Definition: rel.h:568
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:525
@ MAIN_FORKNUM
Definition: relpath.h:58
bool smgrexists(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:401
Oid * rd_opfamily
Definition: rel.h:207
Form_pg_class rd_rel
Definition: rel.h:111
void table_close(Relation relation, LOCKMODE lockmode)
Definition: table.c:126
Relation table_open(Oid relationId, LOCKMODE lockmode)
Definition: table.c:40
static void bt_check_every_level(Relation rel, Relation heaprel, bool heapkeyspace, bool readonly, bool heapallindexed, bool rootdescend, bool checkunique)
static bool btree_index_mainfork_expected(Relation rel)
static void btree_index_checkable(Relation rel)

References _bt_allequalimage(), _bt_metaversion(), AccessShareLock, AtEOXact_GUC(), bt_check_every_level(), btree_index_checkable(), btree_index_mainfork_expected(), ereport, errcode(), ERRCODE_UNDEFINED_TABLE, errhint(), errmsg(), ERROR, GetUserIdAndSecContext(), i, index_close(), index_open(), IndexGetRelation(), IndexRelationGetNumberOfKeyAttributes, InvalidOid, MAIN_FORKNUM, NewGUCNestLevel(), OidIsValid, RelationData::rd_opfamily, RelationData::rd_rel, RelationGetRelationName, RelationGetSmgr(), RestrictSearchPath(), SECURITY_RESTRICTED_OPERATION, SetUserIdAndSecContext(), ShareLock, smgrexists(), table_close(), and table_open().

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 264 of file verify_nbtree.c.

265{
266 Oid indrelid = PG_GETARG_OID(0);
267 bool heapallindexed = false;
268 bool rootdescend = false;
269 bool checkunique = false;
270
271 if (PG_NARGS() >= 2)
272 heapallindexed = PG_GETARG_BOOL(1);
273 if (PG_NARGS() >= 3)
274 rootdescend = PG_GETARG_BOOL(2);
275 if (PG_NARGS() == 4)
276 checkunique = PG_GETARG_BOOL(3);
277
278 bt_index_check_internal(indrelid, true, heapallindexed, rootdescend, checkunique);
279
281}

References bt_index_check_internal(), PG_GETARG_BOOL, PG_GETARG_OID, PG_NARGS, and PG_RETURN_VOID.

◆ bt_leftmost_ignoring_half_dead()

static bool bt_leftmost_ignoring_half_dead ( BtreeCheckState state,
BlockNumber  start,
BTPageOpaque  start_opaque 
)
static

Definition at line 1146 of file verify_nbtree.c.

1149{
1150 BlockNumber reached = start_opaque->btpo_prev,
1151 reached_from = start;
1152 bool all_half_dead = true;
1153
1154 /*
1155 * To handle the !readonly case, we'd need to accept BTP_DELETED pages and
1156 * potentially observe nbtree/README "Page deletion and backwards scans".
1157 */
1158 Assert(state->readonly);
1159
1160 while (reached != P_NONE && all_half_dead)
1161 {
1162 Page page = palloc_btree_page(state, reached);
1163 BTPageOpaque reached_opaque = BTPageGetOpaque(page);
1164
1166
1167 /*
1168 * Try to detect btpo_prev circular links. _bt_unlink_halfdead_page()
1169 * writes that side-links will continue to point to the siblings.
1170 * Check btpo_next for that property.
1171 */
1172 all_half_dead = P_ISHALFDEAD(reached_opaque) &&
1173 reached != start &&
1174 reached != reached_from &&
1175 reached_opaque->btpo_next == reached_from;
1176 if (all_half_dead)
1177 {
1178 XLogRecPtr pagelsn = PageGetLSN(page);
1179
1180 /* pagelsn should point to an XLOG_BTREE_MARK_PAGE_HALFDEAD */
1182 (errcode(ERRCODE_NO_DATA),
1183 errmsg_internal("harmless interrupted page deletion detected in index \"%s\"",
1185 errdetail_internal("Block=%u right block=%u page lsn=%X/%X.",
1186 reached, reached_from,
1187 LSN_FORMAT_ARGS(pagelsn))));
1188
1189 reached_from = reached;
1190 reached = reached_opaque->btpo_prev;
1191 }
1192
1193 pfree(page);
1194 }
1195
1196 return all_half_dead;
1197}
return str start

References Assert, BTPageGetOpaque, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, CHECK_FOR_INTERRUPTS, DEBUG1, ereport, errcode(), errdetail_internal(), errmsg_internal(), 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()

static BTScanInsert bt_mkscankey_pivotsearch ( Relation  rel,
IndexTuple  itup 
)
inlinestatic

Definition at line 3607 of file verify_nbtree.c.

3608{
3609 BTScanInsert skey;
3610
3611 skey = _bt_mkscankey(rel, itup);
3612 skey->backward = true;
3613
3614 return skey;
3615}
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:80

References _bt_mkscankey(), and BTScanInsertData::backward.

Referenced by bt_right_page_check_scankey(), and bt_target_page_check().

◆ bt_normalize_tuple()

static IndexTuple bt_normalize_tuple ( BtreeCheckState state,
IndexTuple  itup 
)
static

Definition at line 2987 of file verify_nbtree.c.

2988{
2989 TupleDesc tupleDescriptor = RelationGetDescr(state->rel);
2990 Datum normalized[INDEX_MAX_KEYS];
2991 bool isnull[INDEX_MAX_KEYS];
2992 bool need_free[INDEX_MAX_KEYS];
2993 bool formnewtup = false;
2994 IndexTuple reformed;
2995 int i;
2996
2997 /* Caller should only pass "logical" non-pivot tuples here */
2999
3000 /* Easy case: It's immediately clear that tuple has no varlena datums */
3001 if (!IndexTupleHasVarwidths(itup))
3002 return itup;
3003
3004 for (i = 0; i < tupleDescriptor->natts; i++)
3005 {
3007
3008 att = TupleDescAttr(tupleDescriptor, i);
3009
3010 /* Assume untoasted/already normalized datum initially */
3011 need_free[i] = false;
3012 normalized[i] = index_getattr(itup, att->attnum,
3013 tupleDescriptor,
3014 &isnull[i]);
3015 if (att->attbyval || att->attlen != -1 || isnull[i])
3016 continue;
3017
3018 /*
3019 * Callers always pass a tuple that could safely be inserted into the
3020 * index without further processing, so an external varlena header
3021 * should never be encountered here
3022 */
3023 if (VARATT_IS_EXTERNAL(DatumGetPointer(normalized[i])))
3024 ereport(ERROR,
3025 (errcode(ERRCODE_INDEX_CORRUPTED),
3026 errmsg("external varlena datum in tuple that references heap row (%u,%u) in index \"%s\"",
3030 else if (!VARATT_IS_COMPRESSED(DatumGetPointer(normalized[i])) &&
3031 VARSIZE(DatumGetPointer(normalized[i])) > TOAST_INDEX_TARGET &&
3032 (att->attstorage == TYPSTORAGE_EXTENDED ||
3033 att->attstorage == TYPSTORAGE_MAIN))
3034 {
3035 /*
3036 * This value will be compressed by index_form_tuple() with the
3037 * current storage settings. We may be here because this tuple
3038 * was formed with different storage settings. So, force forming.
3039 */
3040 formnewtup = true;
3041 }
3042 else if (VARATT_IS_COMPRESSED(DatumGetPointer(normalized[i])))
3043 {
3044 formnewtup = true;
3045 normalized[i] = PointerGetDatum(PG_DETOAST_DATUM(normalized[i]));
3046 need_free[i] = true;
3047 }
3048
3049 /*
3050 * Short tuples may have 1B or 4B header. Convert 4B header of short
3051 * tuples to 1B
3052 */
3053 else if (VARATT_CAN_MAKE_SHORT(DatumGetPointer(normalized[i])))
3054 {
3055 /* convert to short varlena */
3057 char *data = palloc(len);
3058
3060 memcpy(data + 1, VARDATA(DatumGetPointer(normalized[i])), len - 1);
3061
3062 formnewtup = true;
3063 normalized[i] = PointerGetDatum(data);
3064 need_free[i] = true;
3065 }
3066 }
3067
3068 /*
3069 * Easier case: Tuple has varlena datums, none of which are compressed or
3070 * short with 4B header
3071 */
3072 if (!formnewtup)
3073 return itup;
3074
3075 /*
3076 * Hard case: Tuple had compressed varlena datums that necessitate
3077 * creating normalized version of the tuple from uncompressed input datums
3078 * (normalized input datums). This is rather naive, but shouldn't be
3079 * necessary too often.
3080 *
3081 * In the heap, tuples may contain short varlena datums with both 1B
3082 * header and 4B headers. But the corresponding index tuple should always
3083 * have such varlena's with 1B headers. So, if there is a short varlena
3084 * with 4B header, we need to convert it for fingerprinting.
3085 *
3086 * Note that we rely on deterministic index_form_tuple() TOAST compression
3087 * of normalized input.
3088 */
3089 reformed = index_form_tuple(tupleDescriptor, normalized, isnull);
3090 reformed->t_tid = itup->t_tid;
3091
3092 /* Cannot leak memory here */
3093 for (i = 0; i < tupleDescriptor->natts; i++)
3094 if (need_free[i])
3095 pfree(DatumGetPointer(normalized[i]));
3096
3097 return reformed;
3098}
size_t Size
Definition: c.h:562
#define PG_DETOAST_DATUM(datum)
Definition: fmgr.h:240
#define TOAST_INDEX_TARGET
Definition: heaptoast.h:68
IndexTuple index_form_tuple(TupleDesc tupleDescriptor, const Datum *values, const bool *isnull)
Definition: indextuple.c:44
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
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
void * palloc(Size size)
Definition: mcxt.c:1317
static bool BTreeTupleIsPivot(IndexTuple itup)
Definition: nbtree.h:480
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:200
#define INDEX_MAX_KEYS
const void size_t len
const void * data
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:327
uintptr_t Datum
Definition: postgres.h:69
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:317
#define RelationGetDescr(relation)
Definition: rel.h:532
ItemPointerData t_tid
Definition: itup.h:37
static FormData_pg_attribute * TupleDescAttr(TupleDesc tupdesc, int i)
Definition: tupdesc.h:153
#define SET_VARSIZE_SHORT(PTR, len)
Definition: varatt.h:306
#define VARATT_CAN_MAKE_SHORT(PTR)
Definition: varatt.h:258
#define VARDATA(PTR)
Definition: varatt.h:278
#define VARATT_IS_COMPRESSED(PTR)
Definition: varatt.h:288
#define VARSIZE(PTR)
Definition: varatt.h:279
#define VARATT_CONVERTED_SHORT_SIZE(PTR)
Definition: varatt.h:261
#define VARATT_IS_EXTERNAL(PTR)
Definition: varatt.h:289

References Assert, BTreeTupleIsPivot(), BTreeTupleIsPosting(), data, DatumGetPointer(), ereport, errcode(), errmsg(), ERROR, i, index_form_tuple(), index_getattr(), INDEX_MAX_KEYS, IndexTupleHasVarwidths(), ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), len, TupleDescData::natts, palloc(), pfree(), PG_DETOAST_DATUM, PointerGetDatum(), RelationGetDescr, RelationGetRelationName, SET_VARSIZE_SHORT, IndexTupleData::t_tid, TOAST_INDEX_TARGET, TupleDescAttr(), VARATT_CAN_MAKE_SHORT, VARATT_CONVERTED_SHORT_SIZE, VARATT_IS_COMPRESSED, VARATT_IS_EXTERNAL, VARDATA, and VARSIZE.

Referenced by bt_target_page_check(), and bt_tuple_present_callback().

◆ bt_pivot_tuple_identical()

static bool bt_pivot_tuple_identical ( bool  heapkeyspace,
IndexTuple  itup1,
IndexTuple  itup2 
)
static

Definition at line 2211 of file verify_nbtree.c.

2212{
2213 if (IndexTupleSize(itup1) != IndexTupleSize(itup2))
2214 return false;
2215
2216 if (heapkeyspace)
2217 {
2218 /*
2219 * Offset number will contain important information in heapkeyspace
2220 * indexes: the number of attributes left in the pivot tuple following
2221 * suffix truncation. Don't skip over it (compare it too).
2222 */
2223 if (memcmp(&itup1->t_tid.ip_posid, &itup2->t_tid.ip_posid,
2224 IndexTupleSize(itup1) -
2225 offsetof(ItemPointerData, ip_posid)) != 0)
2226 return false;
2227 }
2228 else
2229 {
2230 /*
2231 * Cannot rely on offset number field having consistent value across
2232 * levels on pg_upgrade'd !heapkeyspace indexes. Compare contents of
2233 * tuple starting from just after item pointer (i.e. after block
2234 * number and offset number).
2235 */
2236 if (memcmp(&itup1->t_info, &itup2->t_info,
2237 IndexTupleSize(itup1) -
2238 offsetof(IndexTupleData, t_info)) != 0)
2239 return false;
2240 }
2241
2242 return true;
2243}
unsigned short t_info
Definition: itup.h:49
OffsetNumber ip_posid
Definition: itemptr.h:39

References IndexTupleSize(), ItemPointerData::ip_posid, IndexTupleData::t_info, and IndexTupleData::t_tid.

Referenced by bt_child_highkey_check().

◆ bt_posting_plain_tuple()

static IndexTuple bt_posting_plain_tuple ( IndexTuple  itup,
int  n 
)
inlinestatic

Definition at line 3115 of file verify_nbtree.c.

3116{
3118
3119 /* Returns non-posting-list tuple */
3120 return _bt_form_posting(itup, BTreeTupleGetPostingN(itup, n), 1);
3121}
IndexTuple _bt_form_posting(IndexTuple base, ItemPointer htids, int nhtids)
Definition: nbtdedup.c:864

References _bt_form_posting(), Assert, BTreeTupleGetPostingN(), and BTreeTupleIsPosting().

Referenced by bt_target_page_check().

◆ bt_recheck_sibling_links()

static void bt_recheck_sibling_links ( BtreeCheckState state,
BlockNumber  btpo_prev_from_target,
BlockNumber  leftcurrent 
)
static

Definition at line 1235 of file verify_nbtree.c.

1238{
1239 /* passing metapage to BTPageGetOpaque() would give irrelevant findings */
1240 Assert(leftcurrent != P_NONE);
1241
1242 if (!state->readonly)
1243 {
1244 Buffer lbuf;
1245 Buffer newtargetbuf;
1246 Page page;
1247 BTPageOpaque opaque;
1248 BlockNumber newtargetblock;
1249
1250 /* Couple locks in the usual order for nbtree: Left to right */
1251 lbuf = ReadBufferExtended(state->rel, MAIN_FORKNUM, leftcurrent,
1252 RBM_NORMAL, state->checkstrategy);
1253 LockBuffer(lbuf, BT_READ);
1254 _bt_checkpage(state->rel, lbuf);
1255 page = BufferGetPage(lbuf);
1256 opaque = BTPageGetOpaque(page);
1257 if (P_ISDELETED(opaque))
1258 {
1259 /*
1260 * Cannot reason about concurrently deleted page -- the left link
1261 * in the page to the right is expected to point to some other
1262 * page to the left (not leftcurrent page).
1263 *
1264 * Note that we deliberately don't give up with a half-dead page.
1265 */
1266 UnlockReleaseBuffer(lbuf);
1267 return;
1268 }
1269
1270 newtargetblock = opaque->btpo_next;
1271 /* Avoid self-deadlock when newtargetblock == leftcurrent */
1272 if (newtargetblock != leftcurrent)
1273 {
1274 newtargetbuf = ReadBufferExtended(state->rel, MAIN_FORKNUM,
1275 newtargetblock, RBM_NORMAL,
1276 state->checkstrategy);
1277 LockBuffer(newtargetbuf, BT_READ);
1278 _bt_checkpage(state->rel, newtargetbuf);
1279 page = BufferGetPage(newtargetbuf);
1280 opaque = BTPageGetOpaque(page);
1281 /* btpo_prev_from_target may have changed; update it */
1282 btpo_prev_from_target = opaque->btpo_prev;
1283 }
1284 else
1285 {
1286 /*
1287 * leftcurrent right sibling points back to leftcurrent block.
1288 * Index is corrupt. Easiest way to handle this is to pretend
1289 * that we actually read from a distinct page that has an invalid
1290 * block number in its btpo_prev.
1291 */
1292 newtargetbuf = InvalidBuffer;
1293 btpo_prev_from_target = InvalidBlockNumber;
1294 }
1295
1296 /*
1297 * No need to check P_ISDELETED here, since new target block cannot be
1298 * marked deleted as long as we hold a lock on lbuf
1299 */
1300 if (BufferIsValid(newtargetbuf))
1301 UnlockReleaseBuffer(newtargetbuf);
1302 UnlockReleaseBuffer(lbuf);
1303
1304 if (btpo_prev_from_target == leftcurrent)
1305 {
1306 /* Report split in left sibling, not target (or new target) */
1308 (errcode(ERRCODE_INTERNAL_ERROR),
1309 errmsg_internal("harmless concurrent page split detected in index \"%s\"",
1311 errdetail_internal("Block=%u new right sibling=%u original right sibling=%u.",
1312 leftcurrent, newtargetblock,
1313 state->targetblock)));
1314 return;
1315 }
1316
1317 /*
1318 * Index is corrupt. Make sure that we report correct target page.
1319 *
1320 * This could have changed in cases where there was a concurrent page
1321 * split, as well as index corruption (at least in theory). Note that
1322 * btpo_prev_from_target was already updated above.
1323 */
1324 state->targetblock = newtargetblock;
1325 }
1326
1327 ereport(ERROR,
1328 (errcode(ERRCODE_INDEX_CORRUPTED),
1329 errmsg("left link/right link pair in index \"%s\" not in agreement",
1331 errdetail_internal("Block=%u left block=%u left link from block=%u.",
1332 state->targetblock, leftcurrent,
1333 btpo_prev_from_target)));
1334}
int Buffer
Definition: buf.h:23
#define InvalidBuffer
Definition: buf.h:25
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4883
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:5100
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:793
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:396
@ RBM_NORMAL
Definition: bufmgr.h:45
static bool BufferIsValid(Buffer bufnum)
Definition: bufmgr.h:347
void _bt_checkpage(Relation rel, Buffer buf)
Definition: nbtpage.c:797
#define BT_READ
Definition: nbtree.h:724

References _bt_checkpage(), Assert, BT_READ, BTPageGetOpaque, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BufferGetPage(), BufferIsValid(), DEBUG1, ereport, errcode(), errdetail_internal(), errmsg(), errmsg_internal(), ERROR, 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 void bt_report_duplicate ( BtreeCheckState state,
BtreeLastVisibleEntry lVis,
ItemPointer  nexttid,
BlockNumber  nblock,
OffsetNumber  noffset,
int  nposting 
)
static

Definition at line 1007 of file verify_nbtree.c.

1011{
1012 char *htid,
1013 *nhtid,
1014 *itid,
1015 *nitid = "",
1016 *pposting = "",
1017 *pnposting = "";
1018
1019 htid = psprintf("tid=(%u,%u)",
1022 nhtid = psprintf("tid=(%u,%u)",
1025 itid = psprintf("tid=(%u,%u)", lVis->blkno, lVis->offset);
1026
1027 if (nblock != lVis->blkno || noffset != lVis->offset)
1028 nitid = psprintf(" tid=(%u,%u)", nblock, noffset);
1029
1030 if (lVis->postingIndex >= 0)
1031 pposting = psprintf(" posting %u", lVis->postingIndex);
1032
1033 if (nposting >= 0)
1034 pnposting = psprintf(" posting %u", nposting);
1035
1036 ereport(ERROR,
1037 (errcode(ERRCODE_INDEX_CORRUPTED),
1038 errmsg("index uniqueness is violated for index \"%s\"",
1040 errdetail("Index %s%s and%s%s (point to heap %s and %s) page lsn=%X/%X.",
1041 itid, pposting, nitid, pnposting, htid, nhtid,
1042 LSN_FORMAT_ARGS(state->targetlsn))));
1043}

References BtreeLastVisibleEntry::blkno, ereport, errcode(), errdetail(), errmsg(), ERROR, ItemPointerGetBlockNumberNoCheck(), ItemPointerGetOffsetNumberNoCheck(), LSN_FORMAT_ARGS, BtreeLastVisibleEntry::offset, BtreeLastVisibleEntry::postingIndex, psprintf(), RelationGetRelationName, and BtreeLastVisibleEntry::tid.

Referenced by bt_entry_unique_check().

◆ bt_right_page_check_scankey()

static BTScanInsert bt_right_page_check_scankey ( BtreeCheckState state,
OffsetNumber rightfirstoffset 
)
static

Definition at line 2004 of file verify_nbtree.c.

2005{
2006 BTPageOpaque opaque;
2007 ItemId rightitem;
2008 IndexTuple firstitup;
2009 BlockNumber targetnext;
2010 Page rightpage;
2011 OffsetNumber nline;
2012
2013 /* Determine target's next block number */
2014 opaque = BTPageGetOpaque(state->target);
2015
2016 /* If target is already rightmost, no right sibling; nothing to do here */
2017 if (P_RIGHTMOST(opaque))
2018 return NULL;
2019
2020 /*
2021 * General notes on concurrent page splits and page deletion:
2022 *
2023 * Routines like _bt_search() don't require *any* page split interlock
2024 * when descending the tree, including something very light like a buffer
2025 * pin. That's why it's okay that we don't either. This avoidance of any
2026 * need to "couple" buffer locks is the raison d' etre of the Lehman & Yao
2027 * algorithm, in fact.
2028 *
2029 * That leaves deletion. A deleted page won't actually be recycled by
2030 * VACUUM early enough for us to fail to at least follow its right link
2031 * (or left link, or downlink) and find its sibling, because recycling
2032 * does not occur until no possible index scan could land on the page.
2033 * Index scans can follow links with nothing more than their snapshot as
2034 * an interlock and be sure of at least that much. (See page
2035 * recycling/"visible to everyone" notes in nbtree README.)
2036 *
2037 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
2038 * dead (ignorable) page one or more times. There will either be a
2039 * further right link to follow that leads to a live page before too long
2040 * (before passing by parent's rightmost child), or we will find the end
2041 * of the entire level instead (possible when parent page is itself the
2042 * rightmost on its level).
2043 */
2044 targetnext = opaque->btpo_next;
2045 for (;;)
2046 {
2048
2049 rightpage = palloc_btree_page(state, targetnext);
2050 opaque = BTPageGetOpaque(rightpage);
2051
2052 if (!P_IGNORE(opaque) || P_RIGHTMOST(opaque))
2053 break;
2054
2055 /*
2056 * We landed on a deleted or half-dead sibling page. Step right until
2057 * we locate a live sibling page.
2058 */
2060 (errcode(ERRCODE_NO_DATA),
2061 errmsg_internal("level %u sibling page in block %u of index \"%s\" was found deleted or half dead",
2062 opaque->btpo_level, targetnext, RelationGetRelationName(state->rel)),
2063 errdetail_internal("Deleted page found when building scankey from right sibling.")));
2064
2065 targetnext = opaque->btpo_next;
2066
2067 /* Be slightly more pro-active in freeing this memory, just in case */
2068 pfree(rightpage);
2069 }
2070
2071 /*
2072 * No ShareLock held case -- why it's safe to proceed.
2073 *
2074 * Problem:
2075 *
2076 * We must avoid false positive reports of corruption when caller treats
2077 * item returned here as an upper bound on target's last item. In
2078 * general, false positives are disallowed. Avoiding them here when
2079 * caller is !readonly is subtle.
2080 *
2081 * A concurrent page deletion by VACUUM of the target page can result in
2082 * the insertion of items on to this right sibling page that would
2083 * previously have been inserted on our target page. There might have
2084 * been insertions that followed the target's downlink after it was made
2085 * to point to right sibling instead of target by page deletion's first
2086 * phase. The inserters insert items that would belong on target page.
2087 * This race is very tight, but it's possible. This is our only problem.
2088 *
2089 * Non-problems:
2090 *
2091 * We are not hindered by a concurrent page split of the target; we'll
2092 * never land on the second half of the page anyway. A concurrent split
2093 * of the right page will also not matter, because the first data item
2094 * remains the same within the left half, which we'll reliably land on. If
2095 * we had to skip over ignorable/deleted pages, it cannot matter because
2096 * their key space has already been atomically merged with the first
2097 * non-ignorable page we eventually find (doesn't matter whether the page
2098 * we eventually find is a true sibling or a cousin of target, which we go
2099 * into below).
2100 *
2101 * Solution:
2102 *
2103 * Caller knows that it should reverify that target is not ignorable
2104 * (half-dead or deleted) when cross-page sibling item comparison appears
2105 * to indicate corruption (invariant fails). This detects the single race
2106 * condition that exists for caller. This is correct because the
2107 * continued existence of target block as non-ignorable (not half-dead or
2108 * deleted) implies that target page was not merged into from the right by
2109 * deletion; the key space at or after target never moved left. Target's
2110 * parent either has the same downlink to target as before, or a <
2111 * downlink due to deletion at the left of target. Target either has the
2112 * same highkey as before, or a highkey < before when there is a page
2113 * split. (The rightmost concurrently-split-from-target-page page will
2114 * still have the same highkey as target was originally found to have,
2115 * which for our purposes is equivalent to target's highkey itself never
2116 * changing, since we reliably skip over
2117 * concurrently-split-from-target-page pages.)
2118 *
2119 * In simpler terms, we allow that the key space of the target may expand
2120 * left (the key space can move left on the left side of target only), but
2121 * the target key space cannot expand right and get ahead of us without
2122 * our detecting it. The key space of the target cannot shrink, unless it
2123 * shrinks to zero due to the deletion of the original page, our canary
2124 * condition. (To be very precise, we're a bit stricter than that because
2125 * it might just have been that the target page split and only the
2126 * original target page was deleted. We can be more strict, just not more
2127 * lax.)
2128 *
2129 * Top level tree walk caller moves on to next page (makes it the new
2130 * target) following recovery from this race. (cf. The rationale for
2131 * child/downlink verification needing a ShareLock within
2132 * bt_child_check(), where page deletion is also the main source of
2133 * trouble.)
2134 *
2135 * Note that it doesn't matter if right sibling page here is actually a
2136 * cousin page, because in order for the key space to be readjusted in a
2137 * way that causes us issues in next level up (guiding problematic
2138 * concurrent insertions to the cousin from the grandparent rather than to
2139 * the sibling from the parent), there'd have to be page deletion of
2140 * target's parent page (affecting target's parent's downlink in target's
2141 * grandparent page). Internal page deletion only occurs when there are
2142 * no child pages (they were all fully deleted), and caller is checking
2143 * that the target's parent has at least one non-deleted (so
2144 * non-ignorable) child: the target page. (Note that the first phase of
2145 * deletion atomically marks the page to be deleted half-dead/ignorable at
2146 * the same time downlink in its parent is removed, so caller will
2147 * definitely not fail to detect that this happened.)
2148 *
2149 * This trick is inspired by the method backward scans use for dealing
2150 * with concurrent page splits; concurrent page deletion is a problem that
2151 * similarly receives special consideration sometimes (it's possible that
2152 * the backwards scan will re-read its "original" block after failing to
2153 * find a right-link to it, having already moved in the opposite direction
2154 * (right/"forwards") a few times to try to locate one). Just like us,
2155 * that happens only to determine if there was a concurrent page deletion
2156 * of a reference page, and just like us if there was a page deletion of
2157 * that reference page it means we can move on from caring about the
2158 * reference page. See the nbtree README for a full description of how
2159 * that works.
2160 */
2161 nline = PageGetMaxOffsetNumber(rightpage);
2162
2163 /*
2164 * Get first data item, if any
2165 */
2166 if (P_ISLEAF(opaque) && nline >= P_FIRSTDATAKEY(opaque))
2167 {
2168 /* Return first data item (if any) */
2169 rightitem = PageGetItemIdCareful(state, targetnext, rightpage,
2170 P_FIRSTDATAKEY(opaque));
2171 *rightfirstoffset = P_FIRSTDATAKEY(opaque);
2172 }
2173 else if (!P_ISLEAF(opaque) &&
2174 nline >= OffsetNumberNext(P_FIRSTDATAKEY(opaque)))
2175 {
2176 /*
2177 * Return first item after the internal page's "negative infinity"
2178 * item
2179 */
2180 rightitem = PageGetItemIdCareful(state, targetnext, rightpage,
2182 }
2183 else
2184 {
2185 /*
2186 * No first item. Page is probably empty leaf page, but it's also
2187 * possible that it's an internal page with only a negative infinity
2188 * item.
2189 */
2191 (errcode(ERRCODE_NO_DATA),
2192 errmsg_internal("%s block %u of index \"%s\" has no first data item",
2193 P_ISLEAF(opaque) ? "leaf" : "internal", targetnext,
2195 return NULL;
2196 }
2197
2198 /*
2199 * Return first real item scankey. Note that this relies on right page
2200 * memory remaining allocated.
2201 */
2202 firstitup = (IndexTuple) PageGetItem(rightpage, rightitem);
2203 return bt_mkscankey_pivotsearch(state->rel, firstitup);
2204}
#define DEBUG2
Definition: elog.h:29
static BTScanInsert bt_mkscankey_pivotsearch(Relation rel, IndexTuple itup)

References bt_mkscankey_pivotsearch(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, CHECK_FOR_INTERRUPTS, DEBUG2, ereport, errcode(), errdetail_internal(), errmsg_internal(), 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 bool bt_rootdescend ( BtreeCheckState state,
IndexTuple  itup 
)
static

Definition at line 3148 of file verify_nbtree.c.

3149{
3151 BTStack stack;
3152 Buffer lbuf;
3153 bool exists;
3154
3155 key = _bt_mkscankey(state->rel, itup);
3156 Assert(key->heapkeyspace && key->scantid != NULL);
3157
3158 /*
3159 * Search from root.
3160 *
3161 * Ideally, we would arrange to only move right within _bt_search() when
3162 * an interrupted page split is detected (i.e. when the incomplete split
3163 * bit is found to be set), but for now we accept the possibility that
3164 * that could conceal an inconsistency.
3165 */
3166 Assert(state->readonly && state->rootdescend);
3167 exists = false;
3168 stack = _bt_search(state->rel, NULL, key, &lbuf, BT_READ);
3169
3170 if (BufferIsValid(lbuf))
3171 {
3172 BTInsertStateData insertstate;
3173 OffsetNumber offnum;
3174 Page page;
3175
3176 insertstate.itup = itup;
3177 insertstate.itemsz = MAXALIGN(IndexTupleSize(itup));
3178 insertstate.itup_key = key;
3179 insertstate.postingoff = 0;
3180 insertstate.bounds_valid = false;
3181 insertstate.buf = lbuf;
3182
3183 /* Get matching tuple on leaf page */
3184 offnum = _bt_binsrch_insert(state->rel, &insertstate);
3185 /* Compare first >= matching item on leaf page, if any */
3186 page = BufferGetPage(lbuf);
3187 /* Should match on first heap TID when tuple has a posting list */
3188 if (offnum <= PageGetMaxOffsetNumber(page) &&
3189 insertstate.postingoff <= 0 &&
3190 _bt_compare(state->rel, key, page, offnum) == 0)
3191 exists = true;
3192 _bt_relbuf(state->rel, lbuf);
3193 }
3194
3195 _bt_freestack(stack);
3196 pfree(key);
3197
3198 return exists;
3199}
#define MAXALIGN(LEN)
Definition: c.h:768
void _bt_relbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1023
BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access)
Definition: nbtsearch.c:102
OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
Definition: nbtsearch.c:474
int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum)
Definition: nbtsearch.c:688
void _bt_freestack(BTStack stack)
Definition: nbtutils.c:172
bool bounds_valid
Definition: nbtree.h:828
IndexTuple itup
Definition: nbtree.h:816
BTScanInsert itup_key
Definition: nbtree.h:818

References _bt_binsrch_insert(), _bt_compare(), _bt_freestack(), _bt_mkscankey(), _bt_relbuf(), _bt_search(), Assert, BTInsertStateData::bounds_valid, BT_READ, BTInsertStateData::buf, BufferGetPage(), BufferIsValid(), IndexTupleSize(), BTInsertStateData::itemsz, BTInsertStateData::itup, BTInsertStateData::itup_key, sort-test::key, MAXALIGN, PageGetMaxOffsetNumber(), pfree(), and BTInsertStateData::postingoff.

Referenced by bt_target_page_check().

◆ bt_target_page_check()

static void bt_target_page_check ( BtreeCheckState state)
static

Definition at line 1375 of file verify_nbtree.c.

1376{
1377 OffsetNumber offset;
1378 OffsetNumber max;
1379 BTPageOpaque topaque;
1380
1381 /* Last visible entry info for checking indexes with unique constraint */
1383
1384 topaque = BTPageGetOpaque(state->target);
1385 max = PageGetMaxOffsetNumber(state->target);
1386
1387 elog(DEBUG2, "verifying %u items on %s block %u", max,
1388 P_ISLEAF(topaque) ? "leaf" : "internal", state->targetblock);
1389
1390 /*
1391 * Check the number of attributes in high key. Note, rightmost page
1392 * doesn't contain a high key, so nothing to check
1393 */
1394 if (!P_RIGHTMOST(topaque))
1395 {
1396 ItemId itemid;
1397 IndexTuple itup;
1398
1399 /* Verify line pointer before checking tuple */
1400 itemid = PageGetItemIdCareful(state, state->targetblock,
1401 state->target, P_HIKEY);
1402 if (!_bt_check_natts(state->rel, state->heapkeyspace, state->target,
1403 P_HIKEY))
1404 {
1405 itup = (IndexTuple) PageGetItem(state->target, itemid);
1406 ereport(ERROR,
1407 (errcode(ERRCODE_INDEX_CORRUPTED),
1408 errmsg("wrong number of high key index tuple attributes in index \"%s\"",
1410 errdetail_internal("Index block=%u natts=%u block type=%s page lsn=%X/%X.",
1411 state->targetblock,
1412 BTreeTupleGetNAtts(itup, state->rel),
1413 P_ISLEAF(topaque) ? "heap" : "index",
1414 LSN_FORMAT_ARGS(state->targetlsn))));
1415 }
1416 }
1417
1418 /*
1419 * Loop over page items, starting from first non-highkey item, not high
1420 * key (if any). Most tests are not performed for the "negative infinity"
1421 * real item (if any).
1422 */
1423 for (offset = P_FIRSTDATAKEY(topaque);
1424 offset <= max;
1425 offset = OffsetNumberNext(offset))
1426 {
1427 ItemId itemid;
1428 IndexTuple itup;
1429 size_t tupsize;
1430 BTScanInsert skey;
1431 bool lowersizelimit;
1432 ItemPointer scantid;
1433
1434 /*
1435 * True if we already called bt_entry_unique_check() for the current
1436 * item. This helps to avoid visiting the heap for keys, which are
1437 * anyway presented only once and can't comprise a unique violation.
1438 */
1439 bool unique_checked = false;
1440
1442
1443 itemid = PageGetItemIdCareful(state, state->targetblock,
1444 state->target, offset);
1445 itup = (IndexTuple) PageGetItem(state->target, itemid);
1446 tupsize = IndexTupleSize(itup);
1447
1448 /*
1449 * lp_len should match the IndexTuple reported length exactly, since
1450 * lp_len is completely redundant in indexes, and both sources of
1451 * tuple length are MAXALIGN()'d. nbtree does not use lp_len all that
1452 * frequently, and is surprisingly tolerant of corrupt lp_len fields.
1453 */
1454 if (tupsize != ItemIdGetLength(itemid))
1455 ereport(ERROR,
1456 (errcode(ERRCODE_INDEX_CORRUPTED),
1457 errmsg("index tuple size does not equal lp_len in index \"%s\"",
1459 errdetail_internal("Index tid=(%u,%u) tuple size=%zu lp_len=%u page lsn=%X/%X.",
1460 state->targetblock, offset,
1461 tupsize, ItemIdGetLength(itemid),
1462 LSN_FORMAT_ARGS(state->targetlsn)),
1463 errhint("This could be a torn page problem.")));
1464
1465 /* Check the number of index tuple attributes */
1466 if (!_bt_check_natts(state->rel, state->heapkeyspace, state->target,
1467 offset))
1468 {
1469 ItemPointer tid;
1470 char *itid,
1471 *htid;
1472
1473 itid = psprintf("(%u,%u)", state->targetblock, offset);
1474 tid = BTreeTupleGetPointsToTID(itup);
1475 htid = psprintf("(%u,%u)",
1478
1479 ereport(ERROR,
1480 (errcode(ERRCODE_INDEX_CORRUPTED),
1481 errmsg("wrong number of index tuple attributes in index \"%s\"",
1483 errdetail_internal("Index tid=%s natts=%u points to %s tid=%s page lsn=%X/%X.",
1484 itid,
1485 BTreeTupleGetNAtts(itup, state->rel),
1486 P_ISLEAF(topaque) ? "heap" : "index",
1487 htid,
1488 LSN_FORMAT_ARGS(state->targetlsn))));
1489 }
1490
1491 /*
1492 * Don't try to generate scankey using "negative infinity" item on
1493 * internal pages. They are always truncated to zero attributes.
1494 */
1495 if (offset_is_negative_infinity(topaque, offset))
1496 {
1497 /*
1498 * We don't call bt_child_check() for "negative infinity" items.
1499 * But if we're performing downlink connectivity check, we do it
1500 * for every item including "negative infinity" one.
1501 */
1502 if (!P_ISLEAF(topaque) && state->readonly)
1503 {
1505 offset,
1506 NULL,
1507 topaque->btpo_level);
1508 }
1509 continue;
1510 }
1511
1512 /*
1513 * Readonly callers may optionally verify that non-pivot tuples can
1514 * each be found by an independent search that starts from the root.
1515 * Note that we deliberately don't do individual searches for each
1516 * TID, since the posting list itself is validated by other checks.
1517 */
1518 if (state->rootdescend && P_ISLEAF(topaque) &&
1519 !bt_rootdescend(state, itup))
1520 {
1522 char *itid,
1523 *htid;
1524
1525 itid = psprintf("(%u,%u)", state->targetblock, offset);
1526 htid = psprintf("(%u,%u)", ItemPointerGetBlockNumber(tid),
1528
1529 ereport(ERROR,
1530 (errcode(ERRCODE_INDEX_CORRUPTED),
1531 errmsg("could not find tuple using search from root page in index \"%s\"",
1533 errdetail_internal("Index tid=%s points to heap tid=%s page lsn=%X/%X.",
1534 itid, htid,
1535 LSN_FORMAT_ARGS(state->targetlsn))));
1536 }
1537
1538 /*
1539 * If tuple is a posting list tuple, make sure posting list TIDs are
1540 * in order
1541 */
1542 if (BTreeTupleIsPosting(itup))
1543 {
1544 ItemPointerData last;
1545 ItemPointer current;
1546
1548
1549 for (int i = 1; i < BTreeTupleGetNPosting(itup); i++)
1550 {
1551
1552 current = BTreeTupleGetPostingN(itup, i);
1553
1554 if (ItemPointerCompare(current, &last) <= 0)
1555 {
1556 char *itid = psprintf("(%u,%u)", state->targetblock, offset);
1557
1558 ereport(ERROR,
1559 (errcode(ERRCODE_INDEX_CORRUPTED),
1560 errmsg_internal("posting list contains misplaced TID in index \"%s\"",
1562 errdetail_internal("Index tid=%s posting list offset=%d page lsn=%X/%X.",
1563 itid, i,
1564 LSN_FORMAT_ARGS(state->targetlsn))));
1565 }
1566
1567 ItemPointerCopy(current, &last);
1568 }
1569 }
1570
1571 /* Build insertion scankey for current page offset */
1572 skey = bt_mkscankey_pivotsearch(state->rel, itup);
1573
1574 /*
1575 * Make sure tuple size does not exceed the relevant BTREE_VERSION
1576 * specific limit.
1577 *
1578 * BTREE_VERSION 4 (which introduced heapkeyspace rules) requisitioned
1579 * a small amount of space from BTMaxItemSize() in order to ensure
1580 * that suffix truncation always has enough space to add an explicit
1581 * heap TID back to a tuple -- we pessimistically assume that every
1582 * newly inserted tuple will eventually need to have a heap TID
1583 * appended during a future leaf page split, when the tuple becomes
1584 * the basis of the new high key (pivot tuple) for the leaf page.
1585 *
1586 * Since the reclaimed space is reserved for that purpose, we must not
1587 * enforce the slightly lower limit when the extra space has been used
1588 * as intended. In other words, there is only a cross-version
1589 * difference in the limit on tuple size within leaf pages.
1590 *
1591 * Still, we're particular about the details within BTREE_VERSION 4
1592 * internal pages. Pivot tuples may only use the extra space for its
1593 * designated purpose. Enforce the lower limit for pivot tuples when
1594 * an explicit heap TID isn't actually present. (In all other cases
1595 * suffix truncation is guaranteed to generate a pivot tuple that's no
1596 * larger than the firstright tuple provided to it by its caller.)
1597 */
1598 lowersizelimit = skey->heapkeyspace &&
1599 (P_ISLEAF(topaque) || BTreeTupleGetHeapTID(itup) == NULL);
1600 if (tupsize > (lowersizelimit ? BTMaxItemSize(state->target) :
1601 BTMaxItemSizeNoHeapTid(state->target)))
1602 {
1604 char *itid,
1605 *htid;
1606
1607 itid = psprintf("(%u,%u)", state->targetblock, offset);
1608 htid = psprintf("(%u,%u)",
1611
1612 ereport(ERROR,
1613 (errcode(ERRCODE_INDEX_CORRUPTED),
1614 errmsg("index row size %zu exceeds maximum for index \"%s\"",
1615 tupsize, RelationGetRelationName(state->rel)),
1616 errdetail_internal("Index tid=%s points to %s tid=%s page lsn=%X/%X.",
1617 itid,
1618 P_ISLEAF(topaque) ? "heap" : "index",
1619 htid,
1620 LSN_FORMAT_ARGS(state->targetlsn))));
1621 }
1622
1623 /* Fingerprint leaf page tuples (those that point to the heap) */
1624 if (state->heapallindexed && P_ISLEAF(topaque) && !ItemIdIsDead(itemid))
1625 {
1626 IndexTuple norm;
1627
1628 if (BTreeTupleIsPosting(itup))
1629 {
1630 /* Fingerprint all elements as distinct "plain" tuples */
1631 for (int i = 0; i < BTreeTupleGetNPosting(itup); i++)
1632 {
1633 IndexTuple logtuple;
1634
1635 logtuple = bt_posting_plain_tuple(itup, i);
1636 norm = bt_normalize_tuple(state, logtuple);
1637 bloom_add_element(state->filter, (unsigned char *) norm,
1638 IndexTupleSize(norm));
1639 /* Be tidy */
1640 if (norm != logtuple)
1641 pfree(norm);
1642 pfree(logtuple);
1643 }
1644 }
1645 else
1646 {
1647 norm = bt_normalize_tuple(state, itup);
1648 bloom_add_element(state->filter, (unsigned char *) norm,
1649 IndexTupleSize(norm));
1650 /* Be tidy */
1651 if (norm != itup)
1652 pfree(norm);
1653 }
1654 }
1655
1656 /*
1657 * * High key check *
1658 *
1659 * If there is a high key (if this is not the rightmost page on its
1660 * entire level), check that high key actually is upper bound on all
1661 * page items. If this is a posting list tuple, we'll need to set
1662 * scantid to be highest TID in posting list.
1663 *
1664 * We prefer to check all items against high key rather than checking
1665 * just the last and trusting that the operator class obeys the
1666 * transitive law (which implies that all previous items also
1667 * respected the high key invariant if they pass the item order
1668 * check).
1669 *
1670 * Ideally, we'd compare every item in the index against every other
1671 * item in the index, and not trust opclass obedience of the
1672 * transitive law to bridge the gap between children and their
1673 * grandparents (as well as great-grandparents, and so on). We don't
1674 * go to those lengths because that would be prohibitively expensive,
1675 * and probably not markedly more effective in practice.
1676 *
1677 * On the leaf level, we check that the key is <= the highkey.
1678 * However, on non-leaf levels we check that the key is < the highkey,
1679 * because the high key is "just another separator" rather than a copy
1680 * of some existing key item; we expect it to be unique among all keys
1681 * on the same level. (Suffix truncation will sometimes produce a
1682 * leaf highkey that is an untruncated copy of the lastleft item, but
1683 * never any other item, which necessitates weakening the leaf level
1684 * check to <=.)
1685 *
1686 * Full explanation for why a highkey is never truly a copy of another
1687 * item from the same level on internal levels:
1688 *
1689 * While the new left page's high key is copied from the first offset
1690 * on the right page during an internal page split, that's not the
1691 * full story. In effect, internal pages are split in the middle of
1692 * the firstright tuple, not between the would-be lastleft and
1693 * firstright tuples: the firstright key ends up on the left side as
1694 * left's new highkey, and the firstright downlink ends up on the
1695 * right side as right's new "negative infinity" item. The negative
1696 * infinity tuple is truncated to zero attributes, so we're only left
1697 * with the downlink. In other words, the copying is just an
1698 * implementation detail of splitting in the middle of a (pivot)
1699 * tuple. (See also: "Notes About Data Representation" in the nbtree
1700 * README.)
1701 */
1702 scantid = skey->scantid;
1703 if (state->heapkeyspace && BTreeTupleIsPosting(itup))
1704 skey->scantid = BTreeTupleGetMaxHeapTID(itup);
1705
1706 if (!P_RIGHTMOST(topaque) &&
1707 !(P_ISLEAF(topaque) ? invariant_leq_offset(state, skey, P_HIKEY) :
1709 {
1711 char *itid,
1712 *htid;
1713
1714 itid = psprintf("(%u,%u)", state->targetblock, offset);
1715 htid = psprintf("(%u,%u)",
1718
1719 ereport(ERROR,
1720 (errcode(ERRCODE_INDEX_CORRUPTED),
1721 errmsg("high key invariant violated for index \"%s\"",
1723 errdetail_internal("Index tid=%s points to %s tid=%s page lsn=%X/%X.",
1724 itid,
1725 P_ISLEAF(topaque) ? "heap" : "index",
1726 htid,
1727 LSN_FORMAT_ARGS(state->targetlsn))));
1728 }
1729 /* Reset, in case scantid was set to (itup) posting tuple's max TID */
1730 skey->scantid = scantid;
1731
1732 /*
1733 * * Item order check *
1734 *
1735 * Check that items are stored on page in logical order, by checking
1736 * current item is strictly less than next item (if any).
1737 */
1738 if (OffsetNumberNext(offset) <= max &&
1739 !invariant_l_offset(state, skey, OffsetNumberNext(offset)))
1740 {
1741 ItemPointer tid;
1742 char *itid,
1743 *htid,
1744 *nitid,
1745 *nhtid;
1746
1747 itid = psprintf("(%u,%u)", state->targetblock, offset);
1748 tid = BTreeTupleGetPointsToTID(itup);
1749 htid = psprintf("(%u,%u)",
1752 nitid = psprintf("(%u,%u)", state->targetblock,
1753 OffsetNumberNext(offset));
1754
1755 /* Reuse itup to get pointed-to heap location of second item */
1756 itemid = PageGetItemIdCareful(state, state->targetblock,
1757 state->target,
1758 OffsetNumberNext(offset));
1759 itup = (IndexTuple) PageGetItem(state->target, itemid);
1760 tid = BTreeTupleGetPointsToTID(itup);
1761 nhtid = psprintf("(%u,%u)",
1764
1765 ereport(ERROR,
1766 (errcode(ERRCODE_INDEX_CORRUPTED),
1767 errmsg("item order invariant violated for index \"%s\"",
1769 errdetail_internal("Lower index tid=%s (points to %s tid=%s) "
1770 "higher index tid=%s (points to %s tid=%s) "
1771 "page lsn=%X/%X.",
1772 itid,
1773 P_ISLEAF(topaque) ? "heap" : "index",
1774 htid,
1775 nitid,
1776 P_ISLEAF(topaque) ? "heap" : "index",
1777 nhtid,
1778 LSN_FORMAT_ARGS(state->targetlsn))));
1779 }
1780
1781 /*
1782 * If the index is unique verify entries uniqueness by checking the
1783 * heap tuples visibility. Immediately check posting tuples and
1784 * tuples with repeated keys. Postpone check for keys, which have the
1785 * first appearance.
1786 */
1787 if (state->checkunique && state->indexinfo->ii_Unique &&
1788 P_ISLEAF(topaque) && !skey->anynullkeys &&
1790 {
1791 bt_entry_unique_check(state, itup, state->targetblock, offset,
1792 &lVis);
1793 unique_checked = true;
1794 }
1795
1796 if (state->checkunique && state->indexinfo->ii_Unique &&
1797 P_ISLEAF(topaque) && OffsetNumberNext(offset) <= max)
1798 {
1799 /* Save current scankey tid */
1800 scantid = skey->scantid;
1801
1802 /*
1803 * Invalidate scankey tid to make _bt_compare compare only keys in
1804 * the item to report equality even if heap TIDs are different
1805 */
1806 skey->scantid = NULL;
1807
1808 /*
1809 * If next key tuple is different, invalidate last visible entry
1810 * data (whole index tuple or last posting in index tuple). Key
1811 * containing null value does not violate unique constraint and
1812 * treated as different to any other key.
1813 *
1814 * If the next key is the same as the previous one, do the
1815 * bt_entry_unique_check() call if it was postponed.
1816 */
1817 if (_bt_compare(state->rel, skey, state->target,
1818 OffsetNumberNext(offset)) != 0 || skey->anynullkeys)
1819 {
1822 lVis.postingIndex = -1;
1823 lVis.tid = NULL;
1824 }
1825 else if (!unique_checked)
1826 {
1827 bt_entry_unique_check(state, itup, state->targetblock, offset,
1828 &lVis);
1829 }
1830 skey->scantid = scantid; /* Restore saved scan key state */
1831 }
1832
1833 /*
1834 * * Last item check *
1835 *
1836 * Check last item against next/right page's first data item's when
1837 * last item on page is reached. This additional check will detect
1838 * transposed pages iff the supposed right sibling page happens to
1839 * belong before target in the key space. (Otherwise, a subsequent
1840 * heap verification will probably detect the problem.)
1841 *
1842 * This check is similar to the item order check that will have
1843 * already been performed for every other "real" item on target page
1844 * when last item is checked. The difference is that the next item
1845 * (the item that is compared to target's last item) needs to come
1846 * from the next/sibling page. There may not be such an item
1847 * available from sibling for various reasons, though (e.g., target is
1848 * the rightmost page on level).
1849 */
1850 if (offset == max)
1851 {
1852 BTScanInsert rightkey;
1853
1854 /* first offset on a right index page (log only) */
1855 OffsetNumber rightfirstoffset = InvalidOffsetNumber;
1856
1857 /* Get item in next/right page */
1858 rightkey = bt_right_page_check_scankey(state, &rightfirstoffset);
1859
1860 if (rightkey &&
1861 !invariant_g_offset(state, rightkey, max))
1862 {
1863 /*
1864 * As explained at length in bt_right_page_check_scankey(),
1865 * there is a known !readonly race that could account for
1866 * apparent violation of invariant, which we must check for
1867 * before actually proceeding with raising error. Our canary
1868 * condition is that target page was deleted.
1869 */
1870 if (!state->readonly)
1871 {
1872 /* Get fresh copy of target page */
1873 state->target = palloc_btree_page(state, state->targetblock);
1874 /* Note that we deliberately do not update target LSN */
1875 topaque = BTPageGetOpaque(state->target);
1876
1877 /*
1878 * All !readonly checks now performed; just return
1879 */
1880 if (P_IGNORE(topaque))
1881 return;
1882 }
1883
1884 ereport(ERROR,
1885 (errcode(ERRCODE_INDEX_CORRUPTED),
1886 errmsg("cross page item order invariant violated for index \"%s\"",
1888 errdetail_internal("Last item on page tid=(%u,%u) page lsn=%X/%X.",
1889 state->targetblock, offset,
1890 LSN_FORMAT_ARGS(state->targetlsn))));
1891 }
1892
1893 /*
1894 * If index has unique constraint make sure that no more than one
1895 * found equal items is visible.
1896 */
1897 if (state->checkunique && state->indexinfo->ii_Unique &&
1898 rightkey && P_ISLEAF(topaque) && !P_RIGHTMOST(topaque))
1899 {
1900 BlockNumber rightblock_number = topaque->btpo_next;
1901
1902 elog(DEBUG2, "check cross page unique condition");
1903
1904 /*
1905 * Make _bt_compare compare only index keys without heap TIDs.
1906 * rightkey->scantid is modified destructively but it is ok
1907 * for it is not used later.
1908 */
1909 rightkey->scantid = NULL;
1910
1911 /* The first key on the next page is the same */
1912 if (_bt_compare(state->rel, rightkey, state->target, max) == 0 &&
1913 !rightkey->anynullkeys)
1914 {
1915 Page rightpage;
1916
1917 /*
1918 * Do the bt_entry_unique_check() call if it was
1919 * postponed.
1920 */
1921 if (!unique_checked)
1922 bt_entry_unique_check(state, itup, state->targetblock,
1923 offset, &lVis);
1924
1925 elog(DEBUG2, "cross page equal keys");
1926 rightpage = palloc_btree_page(state,
1927 rightblock_number);
1928 topaque = BTPageGetOpaque(rightpage);
1929
1930 if (P_IGNORE(topaque))
1931 {
1932 pfree(rightpage);
1933 break;
1934 }
1935
1936 if (unlikely(!P_ISLEAF(topaque)))
1937 ereport(ERROR,
1938 (errcode(ERRCODE_INDEX_CORRUPTED),
1939 errmsg("right block of leaf block is non-leaf for index \"%s\"",
1941 errdetail_internal("Block=%u page lsn=%X/%X.",
1942 state->targetblock,
1943 LSN_FORMAT_ARGS(state->targetlsn))));
1944
1945 itemid = PageGetItemIdCareful(state, rightblock_number,
1946 rightpage,
1947 rightfirstoffset);
1948 itup = (IndexTuple) PageGetItem(rightpage, itemid);
1949
1950 bt_entry_unique_check(state, itup, rightblock_number, rightfirstoffset, &lVis);
1951
1952 pfree(rightpage);
1953 }
1954 }
1955 }
1956
1957 /*
1958 * * Downlink check *
1959 *
1960 * Additional check of child items iff this is an internal page and
1961 * caller holds a ShareLock. This happens for every downlink (item)
1962 * in target excluding the negative-infinity downlink (again, this is
1963 * because it has no useful value to compare).
1964 */
1965 if (!P_ISLEAF(topaque) && state->readonly)
1966 bt_child_check(state, skey, offset);
1967 }
1968
1969 /*
1970 * Special case bt_child_highkey_check() call
1971 *
1972 * We don't pass a real downlink, but we've to finish the level
1973 * processing. If condition is satisfied, we've already processed all the
1974 * downlinks from the target level. But there still might be pages to the
1975 * right of the child page pointer to by our rightmost downlink. And they
1976 * might have missing downlinks. This final call checks for them.
1977 */
1978 if (!P_ISLEAF(topaque) && P_RIGHTMOST(topaque) && state->readonly)
1979 {
1981 NULL, topaque->btpo_level);
1982 }
1983}
void bloom_add_element(bloom_filter *filter, unsigned char *elem, size_t len)
Definition: bloomfilter.c:135
#define unlikely(x)
Definition: c.h:333
#define ItemIdGetLength(itemId)
Definition: itemid.h:59
#define ItemIdIsDead(itemId)
Definition: itemid.h:113
int32 ItemPointerCompare(ItemPointer arg1, ItemPointer arg2)
Definition: itemptr.c:51
static void ItemPointerCopy(const ItemPointerData *fromPointer, ItemPointerData *toPointer)
Definition: itemptr.h:172
#define BTMaxItemSizeNoHeapTid(page)
Definition: nbtree.h:169
#define BTMaxItemSize(page)
Definition: nbtree.h:164
static ItemPointer BTreeTupleGetMaxHeapTID(IndexTuple itup)
Definition: nbtree.h:664
#define BTreeTupleGetNAtts(itup, rel)
Definition: nbtree.h:577
bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
Definition: nbtutils.c:3079
#define InvalidOffsetNumber
Definition: off.h:26
ItemPointer scantid
Definition: nbtree.h:796
bool heapkeyspace
Definition: nbtree.h:791
bool anynullkeys
Definition: nbtree.h:793
static bool invariant_l_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber upperbound)
static ItemPointer BTreeTupleGetPointsToTID(IndexTuple itup)
static IndexTuple bt_posting_plain_tuple(IndexTuple itup, int n)
static bool invariant_leq_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber upperbound)
static bool bt_rootdescend(BtreeCheckState *state, IndexTuple itup)
static BTScanInsert bt_right_page_check_scankey(BtreeCheckState *state, OffsetNumber *rightfirstoffset)
static bool invariant_g_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber lowerbound)
static IndexTuple bt_normalize_tuple(BtreeCheckState *state, IndexTuple itup)
static void bt_child_check(BtreeCheckState *state, BTScanInsert targetkey, OffsetNumber downlinkoffnum)
static void bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup, BlockNumber targetblock, OffsetNumber offset, BtreeLastVisibleEntry *lVis)

References _bt_check_natts(), _bt_compare(), BTScanInsertData::anynullkeys, BtreeLastVisibleEntry::blkno, 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, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNAtts, BTreeTupleGetNPosting(), BTreeTupleGetPointsToTID(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), CHECK_FOR_INTERRUPTS, DEBUG2, elog, ereport, errcode(), errdetail_internal(), errhint(), errmsg(), errmsg_internal(), ERROR, BTScanInsertData::heapkeyspace, 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, BtreeLastVisibleEntry::offset, offset_is_negative_infinity(), OffsetNumberNext, P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), BtreeLastVisibleEntry::postingIndex, psprintf(), RelationGetRelationName, BTScanInsertData::scantid, BtreeLastVisibleEntry::tid, and unlikely.

Referenced by bt_check_level_from_leftmost().

◆ bt_tuple_present_callback()

static void bt_tuple_present_callback ( Relation  index,
ItemPointer  tid,
Datum values,
bool *  isnull,
bool  tupleIsAlive,
void *  checkstate 
)
static

Definition at line 2919 of file verify_nbtree.c.

2921{
2922 BtreeCheckState *state = (BtreeCheckState *) checkstate;
2923 IndexTuple itup,
2924 norm;
2925
2926 Assert(state->heapallindexed);
2927
2928 /* Generate a normalized index tuple for fingerprinting */
2930 itup->t_tid = *tid;
2931 norm = bt_normalize_tuple(state, itup);
2932
2933 /* Probe Bloom filter -- tuple should be present */
2934 if (bloom_lacks_element(state->filter, (unsigned char *) norm,
2935 IndexTupleSize(norm)))
2936 ereport(ERROR,
2938 errmsg("heap tuple (%u,%u) from table \"%s\" lacks matching index tuple within index \"%s\"",
2943 !state->readonly
2944 ? errhint("Retrying verification using the function bt_index_parent_check() might provide a more specific error.")
2945 : 0));
2946
2947 state->heaptuplespresent++;
2948 pfree(itup);
2949 /* Cannot leak memory here */
2950 if (norm != itup)
2951 pfree(norm);
2952}
bool bloom_lacks_element(bloom_filter *filter, unsigned char *elem, size_t len)
Definition: bloomfilter.c:157
static Datum values[MAXATTR]
Definition: bootstrap.c:151
#define ERRCODE_DATA_CORRUPTED
Definition: pg_basebackup.c:41
Definition: type.h:96

References Assert, bloom_lacks_element(), bt_normalize_tuple(), ereport, errcode(), ERRCODE_DATA_CORRUPTED, errhint(), errmsg(), ERROR, index_form_tuple(), IndexTupleSize(), ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), pfree(), RelationGetDescr, RelationGetRelationName, IndexTupleData::t_tid, and values.

Referenced by bt_check_every_level().

◆ btree_index_checkable()

static void btree_index_checkable ( Relation  rel)
inlinestatic

Definition at line 428 of file verify_nbtree.c.

429{
430 if (rel->rd_rel->relkind != RELKIND_INDEX ||
431 rel->rd_rel->relam != BTREE_AM_OID)
433 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
434 errmsg("only B-Tree indexes are supported as targets for verification"),
435 errdetail("Relation \"%s\" is not a B-Tree index.",
437
438 if (RELATION_IS_OTHER_TEMP(rel))
440 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
441 errmsg("cannot access temporary tables of other sessions"),
442 errdetail("Index \"%s\" is associated with temporary relation.",
444
445 if (!rel->rd_index->indisvalid)
447 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
448 errmsg("cannot check index \"%s\"",
450 errdetail("Index is not valid.")));
451}
#define RELATION_IS_OTHER_TEMP(relation)
Definition: rel.h:659

References ereport, errcode(), errdetail(), errmsg(), ERROR, RelationData::rd_index, RelationData::rd_rel, RELATION_IS_OTHER_TEMP, and RelationGetRelationName.

Referenced by bt_index_check_internal().

◆ btree_index_mainfork_expected()

static bool btree_index_mainfork_expected ( Relation  rel)
inlinestatic

Definition at line 462 of file verify_nbtree.c.

463{
464 if (rel->rd_rel->relpersistence != RELPERSISTENCE_UNLOGGED ||
466 return true;
467
469 (errcode(ERRCODE_READ_ONLY_SQL_TRANSACTION),
470 errmsg("cannot verify unlogged index \"%s\" during recovery, skipping",
472
473 return false;
474}
bool RecoveryInProgress(void)
Definition: xlog.c:6355

References DEBUG1, ereport, errcode(), errmsg(), RelationData::rd_rel, RecoveryInProgress(), and RelationGetRelationName.

Referenced by bt_index_check_internal().

◆ BTreeTupleGetHeapTIDCareful()

static ItemPointer BTreeTupleGetHeapTIDCareful ( BtreeCheckState state,
IndexTuple  itup,
bool  nonpivot 
)
inlinestatic

Definition at line 3671 of file verify_nbtree.c.

3673{
3674 ItemPointer htid;
3675
3676 /*
3677 * Caller determines whether this is supposed to be a pivot or non-pivot
3678 * tuple using page type and item offset number. Verify that tuple
3679 * metadata agrees with this.
3680 */
3681 Assert(state->heapkeyspace);
3682 if (BTreeTupleIsPivot(itup) && nonpivot)
3683 ereport(ERROR,
3684 (errcode(ERRCODE_INDEX_CORRUPTED),
3685 errmsg_internal("block %u or its right sibling block or child block in index \"%s\" has unexpected pivot tuple",
3686 state->targetblock,
3688
3689 if (!BTreeTupleIsPivot(itup) && !nonpivot)
3690 ereport(ERROR,
3691 (errcode(ERRCODE_INDEX_CORRUPTED),
3692 errmsg_internal("block %u or its right sibling block or child block in index \"%s\" has unexpected non-pivot tuple",
3693 state->targetblock,
3695
3696 htid = BTreeTupleGetHeapTID(itup);
3697 if (!ItemPointerIsValid(htid) && nonpivot)
3698 ereport(ERROR,
3699 (errcode(ERRCODE_INDEX_CORRUPTED),
3700 errmsg("block %u or its right sibling block or child block in index \"%s\" contains non-pivot tuple that lacks a heap TID",
3701 state->targetblock,
3703
3704 return htid;
3705}

References Assert, BTreeTupleGetHeapTID(), BTreeTupleIsPivot(), ereport, errcode(), errmsg(), errmsg_internal(), ERROR, ItemPointerIsValid(), and RelationGetRelationName.

Referenced by invariant_l_nontarget_offset(), and invariant_l_offset().

◆ BTreeTupleGetPointsToTID()

static ItemPointer BTreeTupleGetPointsToTID ( IndexTuple  itup)
inlinestatic

Definition at line 3719 of file verify_nbtree.c.

3720{
3721 /*
3722 * Rely on the assumption that !heapkeyspace internal page data items will
3723 * correctly return TID with downlink here -- BTreeTupleGetHeapTID() won't
3724 * recognize it as a pivot tuple, but everything still works out because
3725 * the t_tid field is still returned
3726 */
3727 if (!BTreeTupleIsPivot(itup))
3728 return BTreeTupleGetHeapTID(itup);
3729
3730 /* Pivot tuple returns TID with downlink block (heapkeyspace variant) */
3731 return &itup->t_tid;
3732}

References BTreeTupleGetHeapTID(), BTreeTupleIsPivot(), and IndexTupleData::t_tid.

Referenced by bt_target_page_check().

◆ heap_entry_is_visible()

static bool heap_entry_is_visible ( BtreeCheckState state,
ItemPointer  tid 
)
static

Definition at line 988 of file verify_nbtree.c.

989{
990 bool tid_visible;
991
992 TupleTableSlot *slot = table_slot_create(state->heaprel, NULL);
993
994 tid_visible = table_tuple_fetch_row_version(state->heaprel,
995 tid, state->snapshot, slot);
996 if (slot != NULL)
998
999 return tid_visible;
1000}
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:1441
TupleTableSlot * table_slot_create(Relation relation, List **reglist)
Definition: tableam.c:91
static bool table_tuple_fetch_row_version(Relation rel, ItemPointer tid, Snapshot snapshot, TupleTableSlot *slot)
Definition: tableam.h:1294

References ExecDropSingleTupleTableSlot(), table_slot_create(), and table_tuple_fetch_row_version().

Referenced by bt_entry_unique_check().

◆ invariant_g_offset()

static bool invariant_g_offset ( BtreeCheckState state,
BTScanInsert  key,
OffsetNumber  lowerbound 
)
inlinestatic

Definition at line 3333 of file verify_nbtree.c.

3335{
3336 int32 cmp;
3337
3338 Assert(!key->nextkey && key->backward);
3339
3340 cmp = _bt_compare(state->rel, key, state->target, lowerbound);
3341
3342 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3343 if (!key->heapkeyspace)
3344 return cmp >= 0;
3345
3346 /*
3347 * No need to consider the possibility that scankey has attributes that we
3348 * need to force to be interpreted as negative infinity. _bt_compare() is
3349 * able to determine that scankey is greater than negative infinity. The
3350 * distinction between "==" and "<" isn't interesting here, since
3351 * corruption is indicated either way.
3352 */
3353 return cmp > 0;
3354}
int32_t int32
Definition: c.h:484
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743

References _bt_compare(), Assert, cmp(), and sort-test::key.

Referenced by bt_target_page_check().

◆ invariant_l_nontarget_offset()

static bool invariant_l_nontarget_offset ( BtreeCheckState state,
BTScanInsert  key,
BlockNumber  nontargetblock,
Page  nontarget,
OffsetNumber  upperbound 
)
inlinestatic

Definition at line 3369 of file verify_nbtree.c.

3372{
3373 ItemId itemid;
3374 int32 cmp;
3375
3376 Assert(!key->nextkey && key->backward);
3377
3378 /* Verify line pointer before checking tuple */
3379 itemid = PageGetItemIdCareful(state, nontargetblock, nontarget,
3380 upperbound);
3381 cmp = _bt_compare(state->rel, key, nontarget, upperbound);
3382
3383 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3384 if (!key->heapkeyspace)
3385 return cmp <= 0;
3386
3387 /* See invariant_l_offset() for an explanation of this extra step */
3388 if (cmp == 0)
3389 {
3390 IndexTuple child;
3391 int uppnkeyatts;
3392 ItemPointer childheaptid;
3393 BTPageOpaque copaque;
3394 bool nonpivot;
3395
3396 child = (IndexTuple) PageGetItem(nontarget, itemid);
3397 copaque = BTPageGetOpaque(nontarget);
3398 nonpivot = P_ISLEAF(copaque) && upperbound >= P_FIRSTDATAKEY(copaque);
3399
3400 /* Get number of keys + heap TID for child/non-target item */
3401 uppnkeyatts = BTreeTupleGetNKeyAtts(child, state->rel);
3402 childheaptid = BTreeTupleGetHeapTIDCareful(state, child, nonpivot);
3403
3404 /* Heap TID is tiebreaker key attribute */
3405 if (key->keysz == uppnkeyatts)
3406 return key->scantid == NULL && childheaptid != NULL;
3407
3408 return key->keysz < uppnkeyatts;
3409 }
3410
3411 return cmp < 0;
3412}
static ItemPointer BTreeTupleGetHeapTIDCareful(BtreeCheckState *state, IndexTuple itup, bool nonpivot)
#define BTreeTupleGetNKeyAtts(itup, rel)
Definition: verify_nbtree.c:52

References _bt_compare(), Assert, BTPageGetOpaque, BTreeTupleGetHeapTIDCareful(), BTreeTupleGetNKeyAtts, cmp(), sort-test::key, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem(), and PageGetItemIdCareful().

Referenced by bt_child_check().

◆ invariant_l_offset()

static bool invariant_l_offset ( BtreeCheckState state,
BTScanInsert  key,
OffsetNumber  upperbound 
)
inlinestatic

Definition at line 3247 of file verify_nbtree.c.

3249{
3250 ItemId itemid;
3251 int32 cmp;
3252
3253 Assert(!key->nextkey && key->backward);
3254
3255 /* Verify line pointer before checking tuple */
3256 itemid = PageGetItemIdCareful(state, state->targetblock, state->target,
3257 upperbound);
3258 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3259 if (!key->heapkeyspace)
3260 return invariant_leq_offset(state, key, upperbound);
3261
3262 cmp = _bt_compare(state->rel, key, state->target, upperbound);
3263
3264 /*
3265 * _bt_compare() is capable of determining that a scankey with a
3266 * filled-out attribute is greater than pivot tuples where the comparison
3267 * is resolved at a truncated attribute (value of attribute in pivot is
3268 * minus infinity). However, it is not capable of determining that a
3269 * scankey is _less than_ a tuple on the basis of a comparison resolved at
3270 * _scankey_ minus infinity attribute. Complete an extra step to simulate
3271 * having minus infinity values for omitted scankey attribute(s).
3272 */
3273 if (cmp == 0)
3274 {
3275 BTPageOpaque topaque;
3276 IndexTuple ritup;
3277 int uppnkeyatts;
3278 ItemPointer rheaptid;
3279 bool nonpivot;
3280
3281 ritup = (IndexTuple) PageGetItem(state->target, itemid);
3282 topaque = BTPageGetOpaque(state->target);
3283 nonpivot = P_ISLEAF(topaque) && upperbound >= P_FIRSTDATAKEY(topaque);
3284
3285 /* Get number of keys + heap TID for item to the right */
3286 uppnkeyatts = BTreeTupleGetNKeyAtts(ritup, state->rel);
3287 rheaptid = BTreeTupleGetHeapTIDCareful(state, ritup, nonpivot);
3288
3289 /* Heap TID is tiebreaker key attribute */
3290 if (key->keysz == uppnkeyatts)
3291 return key->scantid == NULL && rheaptid != NULL;
3292
3293 return key->keysz < uppnkeyatts;
3294 }
3295
3296 return cmp < 0;
3297}

References _bt_compare(), Assert, BTPageGetOpaque, BTreeTupleGetHeapTIDCareful(), BTreeTupleGetNKeyAtts, cmp(), invariant_leq_offset(), sort-test::key, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem(), and PageGetItemIdCareful().

Referenced by bt_target_page_check().

◆ invariant_leq_offset()

static bool invariant_leq_offset ( BtreeCheckState state,
BTScanInsert  key,
OffsetNumber  upperbound 
)
inlinestatic

Definition at line 3310 of file verify_nbtree.c.

3312{
3313 int32 cmp;
3314
3315 Assert(!key->nextkey && key->backward);
3316
3317 cmp = _bt_compare(state->rel, key, state->target, upperbound);
3318
3319 return cmp <= 0;
3320}

References _bt_compare(), Assert, cmp(), and sort-test::key.

Referenced by bt_target_page_check(), and invariant_l_offset().

◆ offset_is_negative_infinity()

static bool offset_is_negative_infinity ( BTPageOpaque  opaque,
OffsetNumber  offset 
)
inlinestatic

Definition at line 3212 of file verify_nbtree.c.

3213{
3214 /*
3215 * For internal pages only, the first item after high key, if any, is
3216 * negative infinity item. Internal pages always have a negative infinity
3217 * item, whereas leaf pages never have one. This implies that negative
3218 * infinity item is either first or second line item, or there is none
3219 * within page.
3220 *
3221 * Negative infinity items are a special case among pivot tuples. They
3222 * always have zero attributes, while all other pivot tuples always have
3223 * nkeyatts attributes.
3224 *
3225 * Right-most pages don't have a high key, but could be said to
3226 * conceptually have a "positive infinity" high key. Thus, there is a
3227 * symmetry between down link items in parent pages, and high keys in
3228 * children. Together, they represent the part of the key space that
3229 * belongs to each page in the index. For example, all children of the
3230 * root page will have negative infinity as a lower bound from root
3231 * negative infinity downlink, and positive infinity as an upper bound
3232 * (implicitly, from "imaginary" positive infinity high key in root).
3233 */
3234 return !P_ISLEAF(opaque) && offset == P_FIRSTDATAKEY(opaque);
3235}

References P_FIRSTDATAKEY, and P_ISLEAF.

Referenced by bt_child_check(), bt_child_highkey_check(), and bt_target_page_check().

◆ PageGetItemIdCareful()

static ItemId PageGetItemIdCareful ( BtreeCheckState state,
BlockNumber  block,
Page  page,
OffsetNumber  offset 
)
static

Definition at line 3631 of file verify_nbtree.c.

3633{
3634 ItemId itemid = PageGetItemId(page, offset);
3635
3636 if (ItemIdGetOffset(itemid) + ItemIdGetLength(itemid) >
3637 BLCKSZ - MAXALIGN(sizeof(BTPageOpaqueData)))
3638 ereport(ERROR,
3639 (errcode(ERRCODE_INDEX_CORRUPTED),
3640 errmsg("line pointer points past end of tuple space in index \"%s\"",
3642 errdetail_internal("Index tid=(%u,%u) lp_off=%u, lp_len=%u lp_flags=%u.",
3643 block, offset, ItemIdGetOffset(itemid),
3644 ItemIdGetLength(itemid),
3645 ItemIdGetFlags(itemid))));
3646
3647 /*
3648 * Verify that line pointer isn't LP_REDIRECT or LP_UNUSED, since nbtree
3649 * never uses either. Verify that line pointer has storage, too, since
3650 * even LP_DEAD items should within nbtree.
3651 */
3652 if (ItemIdIsRedirected(itemid) || !ItemIdIsUsed(itemid) ||
3653 ItemIdGetLength(itemid) == 0)
3654 ereport(ERROR,
3655 (errcode(ERRCODE_INDEX_CORRUPTED),
3656 errmsg("invalid line pointer storage in index \"%s\"",
3658 errdetail_internal("Index tid=(%u,%u) lp_off=%u, lp_len=%u lp_flags=%u.",
3659 block, offset, ItemIdGetOffset(itemid),
3660 ItemIdGetLength(itemid),
3661 ItemIdGetFlags(itemid))));
3662
3663 return itemid;
3664}
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:244
#define ItemIdGetOffset(itemId)
Definition: itemid.h:65
#define ItemIdIsUsed(itemId)
Definition: itemid.h:92
#define ItemIdIsRedirected(itemId)
Definition: itemid.h:106
#define ItemIdGetFlags(itemId)
Definition: itemid.h:71

References ereport, errcode(), errdetail_internal(), errmsg(), ERROR, 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 Page palloc_btree_page ( BtreeCheckState state,
BlockNumber  blocknum 
)
static

Definition at line 3429 of file verify_nbtree.c.

3430{
3431 Buffer buffer;
3432 Page page;
3433 BTPageOpaque opaque;
3434 OffsetNumber maxoffset;
3435
3436 page = palloc(BLCKSZ);
3437
3438 /*
3439 * We copy the page into local storage to avoid holding pin on the buffer
3440 * longer than we must.
3441 */
3442 buffer = ReadBufferExtended(state->rel, MAIN_FORKNUM, blocknum, RBM_NORMAL,
3443 state->checkstrategy);
3444 LockBuffer(buffer, BT_READ);
3445
3446 /*
3447 * Perform the same basic sanity checking that nbtree itself performs for
3448 * every page:
3449 */
3450 _bt_checkpage(state->rel, buffer);
3451
3452 /* Only use copy of page in palloc()'d memory */
3453 memcpy(page, BufferGetPage(buffer), BLCKSZ);
3454 UnlockReleaseBuffer(buffer);
3455
3456 opaque = BTPageGetOpaque(page);
3457
3458 if (P_ISMETA(opaque) && blocknum != BTREE_METAPAGE)
3459 ereport(ERROR,
3460 (errcode(ERRCODE_INDEX_CORRUPTED),
3461 errmsg("invalid meta page found at block %u in index \"%s\"",
3462 blocknum, RelationGetRelationName(state->rel))));
3463
3464 /* Check page from block that ought to be meta page */
3465 if (blocknum == BTREE_METAPAGE)
3466 {
3467 BTMetaPageData *metad = BTPageGetMeta(page);
3468
3469 if (!P_ISMETA(opaque) ||
3470 metad->btm_magic != BTREE_MAGIC)
3471 ereport(ERROR,
3472 (errcode(ERRCODE_INDEX_CORRUPTED),
3473 errmsg("index \"%s\" meta page is corrupt",
3475
3476 if (metad->btm_version < BTREE_MIN_VERSION ||
3477 metad->btm_version > BTREE_VERSION)
3478 ereport(ERROR,
3479 (errcode(ERRCODE_INDEX_CORRUPTED),
3480 errmsg("version mismatch in index \"%s\": file version %d, "
3481 "current version %d, minimum supported version %d",
3483 metad->btm_version, BTREE_VERSION,
3485
3486 /* Finished with metapage checks */
3487 return page;
3488 }
3489
3490 /*
3491 * Deleted pages that still use the old 32-bit XID representation have no
3492 * sane "level" field because they type pun the field, but all other pages
3493 * (including pages deleted on Postgres 14+) have a valid value.
3494 */
3495 if (!P_ISDELETED(opaque) || P_HAS_FULLXID(opaque))
3496 {
3497 /* Okay, no reason not to trust btpo_level field from page */
3498
3499 if (P_ISLEAF(opaque) && opaque->btpo_level != 0)
3500 ereport(ERROR,
3501 (errcode(ERRCODE_INDEX_CORRUPTED),
3502 errmsg_internal("invalid leaf page level %u for block %u in index \"%s\"",
3503 opaque->btpo_level, blocknum,
3505
3506 if (!P_ISLEAF(opaque) && opaque->btpo_level == 0)
3507 ereport(ERROR,
3508 (errcode(ERRCODE_INDEX_CORRUPTED),
3509 errmsg_internal("invalid internal page level 0 for block %u in index \"%s\"",
3510 blocknum,
3512 }
3513
3514 /*
3515 * Sanity checks for number of items on page.
3516 *
3517 * As noted at the beginning of _bt_binsrch(), an internal page must have
3518 * children, since there must always be a negative infinity downlink
3519 * (there may also be a highkey). In the case of non-rightmost leaf
3520 * pages, there must be at least a highkey. The exceptions are deleted
3521 * pages, which contain no items.
3522 *
3523 * This is correct when pages are half-dead, since internal pages are
3524 * never half-dead, and leaf pages must have a high key when half-dead
3525 * (the rightmost page can never be deleted). It's also correct with
3526 * fully deleted pages: _bt_unlink_halfdead_page() doesn't change anything
3527 * about the target page other than setting the page as fully dead, and
3528 * setting its xact field. In particular, it doesn't change the sibling
3529 * links in the deletion target itself, since they're required when index
3530 * scans land on the deletion target, and then need to move right (or need
3531 * to move left, in the case of backward index scans).
3532 */
3533 maxoffset = PageGetMaxOffsetNumber(page);
3534 if (maxoffset > MaxIndexTuplesPerPage)
3535 ereport(ERROR,
3536 (errcode(ERRCODE_INDEX_CORRUPTED),
3537 errmsg("Number of items on block %u of index \"%s\" exceeds MaxIndexTuplesPerPage (%u)",
3538 blocknum, RelationGetRelationName(state->rel),
3540
3541 if (!P_ISLEAF(opaque) && !P_ISDELETED(opaque) && maxoffset < P_FIRSTDATAKEY(opaque))
3542 ereport(ERROR,
3543 (errcode(ERRCODE_INDEX_CORRUPTED),
3544 errmsg("internal block %u in index \"%s\" lacks high key and/or at least one downlink",
3545 blocknum, RelationGetRelationName(state->rel))));
3546
3547 if (P_ISLEAF(opaque) && !P_ISDELETED(opaque) && !P_RIGHTMOST(opaque) && maxoffset < P_HIKEY)
3548 ereport(ERROR,
3549 (errcode(ERRCODE_INDEX_CORRUPTED),
3550 errmsg("non-rightmost leaf block %u in index \"%s\" lacks high key item",
3551 blocknum, RelationGetRelationName(state->rel))));
3552
3553 /*
3554 * In general, internal pages are never marked half-dead, except on
3555 * versions of Postgres prior to 9.4, where it can be valid transient
3556 * state. This state is nonetheless treated as corruption by VACUUM on
3557 * from version 9.4 on, so do the same here. See _bt_pagedel() for full
3558 * details.
3559 */
3560 if (!P_ISLEAF(opaque) && P_ISHALFDEAD(opaque))
3561 ereport(ERROR,
3562 (errcode(ERRCODE_INDEX_CORRUPTED),
3563 errmsg("internal page block %u in index \"%s\" is half-dead",
3564 blocknum, RelationGetRelationName(state->rel)),
3565 errhint("This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));
3566
3567 /*
3568 * Check that internal pages have no garbage items, and that no page has
3569 * an invalid combination of deletion-related page level flags
3570 */
3571 if (!P_ISLEAF(opaque) && P_HAS_GARBAGE(opaque))
3572 ereport(ERROR,
3573 (errcode(ERRCODE_INDEX_CORRUPTED),
3574 errmsg_internal("internal page block %u in index \"%s\" has garbage items",
3575 blocknum, RelationGetRelationName(state->rel))));
3576
3577 if (P_HAS_FULLXID(opaque) && !P_ISDELETED(opaque))
3578 ereport(ERROR,
3579 (errcode(ERRCODE_INDEX_CORRUPTED),
3580 errmsg_internal("full transaction id page flag appears in non-deleted block %u in index \"%s\"",
3581 blocknum, RelationGetRelationName(state->rel))));
3582
3583 if (P_ISDELETED(opaque) && P_ISHALFDEAD(opaque))
3584 ereport(ERROR,
3585 (errcode(ERRCODE_INDEX_CORRUPTED),
3586 errmsg_internal("deleted page block %u in index \"%s\" is half-dead",
3587 blocknum, RelationGetRelationName(state->rel))));
3588
3589 return page;
3590}
#define MaxIndexTuplesPerPage
Definition: itup.h:181
#define BTREE_MIN_VERSION
Definition: nbtree.h:151
#define P_HAS_GARBAGE(opaque)
Definition: nbtree.h:226
#define P_ISMETA(opaque)
Definition: nbtree.h:223
#define BTREE_MAGIC
Definition: nbtree.h:149
#define BTREE_VERSION
Definition: nbtree.h:150
uint32 btm_version
Definition: nbtree.h:106
uint32 btm_magic
Definition: nbtree.h:105

References _bt_checkpage(), BT_READ, BTMetaPageData::btm_magic, BTMetaPageData::btm_version, BTPageGetMeta, BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTREE_MAGIC, BTREE_METAPAGE, BTREE_MIN_VERSION, BTREE_VERSION, BufferGetPage(), ereport, errcode(), errhint(), errmsg(), errmsg_internal(), ERROR, LockBuffer(), MAIN_FORKNUM, MaxIndexTuplesPerPage, P_FIRSTDATAKEY, P_HAS_FULLXID, P_HAS_GARBAGE, P_HIKEY, P_ISDELETED, P_ISHALFDEAD, P_ISLEAF, P_ISMETA, P_RIGHTMOST, PageGetMaxOffsetNumber(), palloc(), RBM_NORMAL, ReadBufferExtended(), RelationGetRelationName, and UnlockReleaseBuffer().

Referenced by bt_check_every_level(), bt_check_level_from_leftmost(), bt_child_check(), bt_child_highkey_check(), bt_downlink_missing_check(), bt_leftmost_ignoring_half_dead(), bt_right_page_check_scankey(), and bt_target_page_check().

◆ PG_FUNCTION_INFO_V1() [1/2]

PG_FUNCTION_INFO_V1 ( bt_index_check  )

◆ PG_FUNCTION_INFO_V1() [2/2]

PG_FUNCTION_INFO_V1 ( bt_index_parent_check  )

Variable Documentation

◆ PG_MODULE_MAGIC

PG_MODULE_MAGIC

Definition at line 45 of file verify_nbtree.c.