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

Generated by: LCOV version 1.13