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

Generated by: LCOV version 1.13