LCOV - code coverage report
Current view: top level - contrib/amcheck - verify_nbtree.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 540 749 72.1 %
Date: 2025-04-01 16:15:31 Functions: 31 33 93.9 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14