PolarDB-for-PostgreSQL
2148 строк · 80.3 Кб
1/*-------------------------------------------------------------------------2*3* verify_nbtree.c4* Verifies the integrity of nbtree indexes based on invariants.5*6* For B-Tree indexes, verification includes checking that each page in the7* target index has items in logical order as reported by an insertion scankey8* (the insertion scankey sort-wise NULL semantics are needed for9* verification).10*11* When index-to-heap verification is requested, a Bloom filter is used to12* fingerprint all tuples in the target index, as the index is traversed to13* verify its structure. A heap scan later uses Bloom filter probes to verify14* that every visible heap tuple has a matching index tuple.15*16*17* Copyright (c) 2017-2018, PostgreSQL Global Development Group18*19* IDENTIFICATION20* contrib/amcheck/verify_nbtree.c21*22*-------------------------------------------------------------------------23*/24#include "postgres.h"25/* POLAR csn */42#include "utils/guc.h"43#include "storage/procarray.h"44/* POLAR end */45/*49* A B-Tree cannot possibly have this many levels, since there must be one50* block per level, which is bound by the range of BlockNumber:51*/52#define InvalidBtreeLevel ((uint32) InvalidBlockNumber)53/*55* State associated with verifying a B-Tree index56*57* target is the point of reference for a verification operation.58*59* Other B-Tree pages may be allocated, but those are always auxiliary (e.g.,60* they are current target's child pages). Conceptually, problems are only61* ever found in the current target page (or for a particular heap tuple during62* heapallindexed verification). Each page found by verification's left/right,63* top/bottom scan becomes the target exactly once.64*/65typedef struct BtreeCheckState66{67/*68* Unchanging state, established at start of verification:69*/70* Mutable state, for verification of particular page:85*/86* Mutable state, for optional heapallindexed verification:96*/97/*109* Starting point for verifying an entire B-Tree index level110*/111typedef struct BtreeLevel112{113/* Level number (0 is leaf page level). */114uint32 level;115/*159* bt_index_check(index regclass, heapallindexed boolean)160*161* Verify integrity of B-Tree index.162*163* Acquires AccessShareLock on heap & index relations. Does not consider164* invariants that exist between parent/child pages. Optionally verifies165* that heap does not contain any unindexed or incorrectly indexed tuples.166*/167Datum168bt_index_check(PG_FUNCTION_ARGS)169{170Oid indrelid = PG_GETARG_OID(0);171bool heapallindexed = false;172}180/*182* bt_index_parent_check(index regclass, heapallindexed boolean)183*184* Verify integrity of B-Tree index.185*186* Acquires ShareLock on heap & index relations. Verifies that downlinks in187* parent pages are valid lower bounds on child pages. Optionally verifies188* that heap does not contain any unindexed or incorrectly indexed tuples.189*/190Datum191bt_index_parent_check(PG_FUNCTION_ARGS)192{193Oid indrelid = PG_GETARG_OID(0);194bool heapallindexed = false;195}203/*205* Helper for bt_index_[parent_]check, coordinating the bulk of the work.206*/207static void208bt_index_check_internal(Oid indrelid, bool parentcheck, bool heapallindexed)209{210Oid heapid;211Relation indrel;212Relation heaprel;213LOCKMODE lockmode;214Oid save_userid;215int save_sec_context;216int save_nestlevel;217* We must lock table before index to avoid deadlocks. However, if the225* passed indrelid isn't an index then IndexGetRelation() will fail.226* Rather than emitting a not-very-helpful error message, postpone227* complaining, expecting that the is-it-an-index test below will fail.228*229* In hot standby mode this will raise an error when parentcheck is true.230*/231heapid = IndexGetRelation(indrelid, true);232if (OidIsValid(heapid))233{234heaprel = heap_open(heapid, lockmode);235* Switch to the table owner's userid, so that any index functions are238* run as that user. Also lock down security-restricted operations239* and arrange to make GUC variable changes local to this command.240*/241GetUserIdAndSecContext(&save_userid, &save_sec_context);242SetUserIdAndSecContext(heaprel->rd_rel->relowner,243save_sec_context | SECURITY_RESTRICTED_OPERATION);244save_nestlevel = NewGUCNestLevel();245}246else247{248heaprel = NULL;249/* for "gcc -Og" https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78394 */250save_userid = InvalidOid;251save_sec_context = -1;252save_nestlevel = -1;253}254* Open the target index relations separately (like relation_openrv(), but257* with heap relation locked first to prevent deadlocking). In hot258* standby mode this will raise an error when parentcheck is true.259*260* There is no need for the usual indcheckxmin usability horizon test261* here, even in the heapallindexed case, because index undergoing262* verification only needs to have entries for a new transaction snapshot.263* (If this is a parentcheck verification, there is no question about264* committed or recently dead heap tuples lacking index entries due to265* concurrent activity.)266*/267indrel = index_open(indrelid, lockmode);268* Since we did the IndexGetRelation call above without any lock, it's271* barely possible that a race against an index drop/recreation could have272* netted us the wrong table.273*/274if (heaprel == NULL || heapid != IndexGetRelation(indrelid, false))275ereport(ERROR,276(errcode(ERRCODE_UNDEFINED_TABLE),277errmsg("could not open parent table of index %s",278RelationGetRelationName(indrel))));279* Release locks early. That's ok here because nothing in the called304* routines will trigger shared cache invalidations to be sent, so we can305* relax the usual pattern of only releasing locks after commit.306*/307index_close(indrel, lockmode);308if (heaprel)309heap_close(heaprel, lockmode);310}311/*313* Basic checks about the suitability of a relation for checking as a B-Tree314* index.315*316* NB: Intentionally not checking permissions, the function is normally not317* callable by non-superusers. If granted, it's useful to be able to check a318* whole cluster.319*/320static inline void321btree_index_checkable(Relation rel)322{323if (rel->rd_rel->relkind != RELKIND_INDEX ||324rel->rd_rel->relam != BTREE_AM_OID)325ereport(ERROR,326(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),327errmsg("only B-Tree indexes are supported as targets for verification"),328errdetail("Relation \"%s\" is not a B-Tree index.",329RelationGetRelationName(rel))));330}345/*347* Check if B-Tree index relation should have a file for its main relation348* fork. Verification uses this to skip unlogged indexes when in hot standby349* mode, where there is simply nothing to verify.350*351* NB: Caller should call btree_index_checkable() before calling here.352*/353static inline bool354btree_index_mainfork_expected(Relation rel)355{356if (rel->rd_rel->relpersistence != RELPERSISTENCE_UNLOGGED ||357!RecoveryInProgress())358return true;359}367/*369* Main entry point for B-Tree SQL-callable functions. Walks the B-Tree in370* logical order, verifying invariants as it goes. Optionally, verification371* checks if the heap relation contains any tuples that are not represented in372* the index but should be.373*374* It is the caller's responsibility to acquire appropriate heavyweight lock on375* the index relation, and advise us if extra checks are safe when a ShareLock376* is held. (A lock of the same type must also have been acquired on the heap377* relation.)378*379* A ShareLock is generally assumed to prevent any kind of physical380* modification to the index structure, including modifications that VACUUM may381* make. This does not include setting of the LP_DEAD bit by concurrent index382* scans, although that is just metadata that is not able to directly affect383* any check performed here. Any concurrent process that might act on the384* LP_DEAD bit being set (recycle space) requires a heavyweight lock that385* cannot be held while we hold a ShareLock. (Besides, even if that could386* happen, the ad-hoc recycling when a page might otherwise split is performed387* per-page, and requires an exclusive buffer lock, which wouldn't cause us388* trouble. _bt_delitems_vacuum() may only delete leaf items, and so the extra389* parent/child check cannot be affected.)390*/391static void392bt_check_every_level(Relation rel, Relation heaprel, bool readonly,393bool heapallindexed)394{395BtreeCheckState *state;396Page metapage;397BTMetaPageData *metad;398uint32 previouslevel;399BtreeLevel current;400Snapshot snapshot = SnapshotAny;401* RecentGlobalXmin assertion matches index_getnext_tid(). See note on404* RecentGlobalXmin/B-Tree page deletion.405*406* POLAR csn: get newest global xmin407*/408Assert(TransactionIdIsValid(GetRecentGlobalXmin()));409* Initialize state for entire verification operation412*/413state = palloc0(sizeof(BtreeCheckState));414state->rel = rel;415state->heaprel = heaprel;416state->readonly = readonly;417state->heapallindexed = heapallindexed;418* Size Bloom filter based on estimated number of tuples in index,427* while conservatively assuming that each block must contain at least428* MaxIndexTuplesPerPage / 5 non-pivot tuples. (Non-leaf pages cannot429* contain non-pivot tuples. That's okay because they generally make430* up no more than about 1% of all pages in the index.)431*/432total_pages = RelationGetNumberOfBlocks(rel);433total_elems = Max(total_pages * (MaxIndexTuplesPerPage / 5),434(int64) state->rel->rd_rel->reltuples);435/* Random seed relies on backend srandom() call to avoid repetition */436seed = random();437/* Create Bloom filter to fingerprint index */438state->filter = bloom_create(total_elems, maintenance_work_mem, seed);439state->heaptuplespresent = 0;440* Register our own snapshot in !readonly case, rather than asking443* IndexBuildHeapScan() to do this for us later. This needs to happen444* before index fingerprinting begins, so we can later be certain that445* index fingerprinting should have reached all tuples returned by446* IndexBuildHeapScan().447*448* In readonly case, we also check for problems with missing449* downlinks. A second Bloom filter is used for this.450*/451if (!state->readonly)452{453snapshot = RegisterSnapshot(GetTransactionSnapshot());454* GetTransactionSnapshot() always acquires a new MVCC snapshot in457* READ COMMITTED mode. A new snapshot is guaranteed to have all458* the entries it requires in the index.459*460* We must defend against the possibility that an old xact461* snapshot was returned at higher isolation levels when that462* snapshot is not safe for index scans of the target index. This463* is possible when the snapshot sees tuples that are before the464* index's indcheckxmin horizon. Throwing an error here should be465* very rare. It doesn't seem worth using a secondary snapshot to466* avoid this.467*/468if (IsolationUsesXactSnapshot() && rel->rd_index->indcheckxmin &&469!TransactionIdPrecedes(HeapTupleHeaderGetXmin(rel->rd_indextuple->t_data),470snapshot->xmin))471ereport(ERROR,472(errcode(ERRCODE_T_R_SERIALIZATION_FAILURE),473errmsg("index \"%s\" cannot be verified using transaction snapshot",474RelationGetRelationName(rel))));475}476else477{478/*479* Extra readonly downlink check.480*481* In readonly case, we know that there cannot be a concurrent482* page split or a concurrent page deletion, which gives us the483* opportunity to verify that every non-ignorable page had a484* downlink one level up. We must be tolerant of interrupted page485* splits and page deletions, though. This is taken care of in486* bt_downlink_missing_check().487*/488state->downlinkfilter = bloom_create(total_pages, work_mem, seed);489}490}491* Certain deletion patterns can result in "skinny" B-Tree indexes, where504* the fast root and true root differ.505*506* Start from the true root, not the fast root, unlike conventional index507* scans. This approach is more thorough, and removes the risk of508* following a stale fast root from the meta page.509*/510if (metad->btm_fastroot != metad->btm_root)511ereport(DEBUG1,512(errcode(ERRCODE_NO_DATA),513errmsg("harmless fast root mismatch in index %s",514RelationGetRelationName(rel)),515errdetail_internal("Fast root block %u (level %u) differs from true root block %u (level %u).",516metad->btm_fastroot, metad->btm_fastlevel,517metad->btm_root, metad->btm_level)));518* Starting at the root, verify every level. Move left to right, top to521* bottom. Note that there may be no pages other than the meta page (meta522* page can indicate that root is P_NONE when the index is totally empty).523*/524previouslevel = InvalidBtreeLevel;525current.level = metad->btm_level;526current.leftmost = metad->btm_root;527current.istruerootlevel = true;528while (current.leftmost != P_NONE)529{530/*531* Leftmost page on level cannot be right half of incomplete split.532* This can go stale immediately in !readonly case.533*/534state->rightsplit = false;535* Verify this level, and get left most page for next level down, if538* not at leaf level539*/540current = bt_check_level_from_leftmost(state, current);541* * Check whether heap contains unindexed/malformed tuples *553*/554if (state->heapallindexed)555{556IndexInfo *indexinfo = BuildIndexInfo(state->rel);557HeapScanDesc scan;558* Create our own scan for IndexBuildHeapScan(), rather than getting571* it to do so for us. This is required so that we can actually use572* the MVCC snapshot registered earlier in !readonly case.573*574* Note that IndexBuildHeapScan() calls heap_endscan() for us.575*/576scan = heap_beginscan_strat(state->heaprel, /* relation */577snapshot, /* snapshot */5780, /* number of keys */579NULL, /* scan key */580true, /* buffer access strategy OK */581true); /* syncscan OK? */582* Scan will behave as the first scan of a CREATE INDEX CONCURRENTLY585* behaves in !readonly case.586*587* It's okay that we don't actually use the same lock strength for the588* heap relation as any other ii_Concurrent caller would in !readonly589* case. We have no reason to care about a concurrent VACUUM590* operation, since there isn't going to be a second scan of the heap591* that needs to be sure that there was no concurrent recycling of592* TIDs.593*/594indexinfo->ii_Concurrent = !state->readonly;595* Don't wait for uncommitted tuple xact commit/abort when index is a598* unique index on a catalog (or an index used by an exclusion599* constraint). This could otherwise happen in the readonly case.600*/601indexinfo->ii_Unique = false;602indexinfo->ii_ExclusionOps = NULL;603indexinfo->ii_ExclusionProcs = NULL;604indexinfo->ii_ExclusionStrats = NULL;605}627/*629* Given a left-most block at some level, move right, verifying each page630* individually (with more verification across pages for "readonly"631* callers). Caller should pass the true root page as the leftmost initially,632* working their way down by passing what is returned for the last call here633* until level 0 (leaf page level) was reached.634*635* Returns state for next call, if any. This includes left-most block number636* one level lower that should be passed on next level/call, which is set to637* P_NONE on last call here (when leaf level is verified). Level numbers638* follow the nbtree convention: higher levels have higher numbers, because new639* levels are added only due to a root page split. Note that prior to the640* first root page split, the root is also a leaf page, so there is always a641* level 0 (leaf level), and it's always the last level processed.642*643* Note on memory management: State's per-page context is reset here, between644* each call to bt_target_page_check().645*/646static BtreeLevel647bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)648{649/* State to establish early, concerning entire level */650BTPageOpaque opaque;651MemoryContext oldcontext;652BtreeLevel nextleveldown;653* Since there cannot be a concurrent VACUUM operation in readonly686* mode, and since a page has no links within other pages687* (siblings and parent) once it is marked fully deleted, it688* should be impossible to land on a fully deleted page in689* readonly mode. See bt_downlink_check() for further details.690*691* The bt_downlink_check() P_ISDELETED() check is repeated here so692* that pages that are only reachable through sibling links get693* checked.694*/695if (state->readonly && P_ISDELETED(opaque))696ereport(ERROR,697(errcode(ERRCODE_INDEX_CORRUPTED),698errmsg("downlink or sibling link points to deleted block in index \"%s\"",699RelationGetRelationName(state->rel)),700errdetail_internal("Block=%u left block=%u left link from block=%u.",701current, leftcurrent, opaque->btpo_prev)));702* A concurrent page split could make the caller supplied leftmost719* block no longer contain the leftmost page, or no longer be the720* true root, but where that isn't possible due to heavyweight721* locking, check that the first valid page meets caller's722* expectations.723*/724if (state->readonly)725{726if (!P_LEFTMOST(opaque))727ereport(ERROR,728(errcode(ERRCODE_INDEX_CORRUPTED),729errmsg("block %u is not leftmost in index \"%s\"",730current, RelationGetRelationName(state->rel))));731* Before beginning any non-trivial examination of level, prepare741* state for next bt_check_level_from_leftmost() invocation for742* the next level for the next level down (if any).743*744* There should be at least one non-ignorable page per level,745* unless this is the leaf level, which is assumed by caller to be746* final level.747*/748if (!P_ISLEAF(opaque))749{750IndexTuple itup;751ItemId itemid;752* Leaf page -- final level caller must process.763*764* Note that this could also be the root page, if there has765* been no root page split yet.766*/767nextleveldown.leftmost = P_NONE;768nextleveldown.level = InvalidBtreeLevel;769}770* Finished setting up state for this call/level. Control will773* never end up back here in any future loop iteration for this774* level.775*/776}777* readonly mode can only ever land on live pages and half-dead pages,780* so sibling pointers should always be in mutual agreement781*/782if (state->readonly && opaque->btpo_prev != leftcurrent)783ereport(ERROR,784(errcode(ERRCODE_INDEX_CORRUPTED),785errmsg("left link/right link pair in index \"%s\" not in agreement",786RelationGetRelationName(state->rel)),787errdetail_internal("Block=%u left block=%u left link from block=%u.",788current, leftcurrent, opaque->btpo_prev)));789* Record if page that is about to become target is the right half of813* an incomplete page split. This can go stale immediately in814* !readonly case.815*/816state->rightsplit = P_INCOMPLETE_SPLIT(opaque);817}831/*833* Function performs the following checks on target page, or pages ancillary to834* target page:835*836* - That every "real" data item is less than or equal to the high key, which837* is an upper bound on the items on the pages (where there is a high key at838* all -- pages that are rightmost lack one).839*840* - That within the page, every "real" item is less than or equal to the item841* immediately to its right, if any (i.e., that the items are in order within842* the page, so that the binary searches performed by index scans are sane).843*844* - That the last item stored on the page is less than or equal to the first845* "real" data item on the page to the right (if such a first item is846* available).847*848* - That tuples report that they have the expected number of attributes.849* INCLUDE index pivot tuples should not contain non-key attributes.850*851* Furthermore, when state passed shows ShareLock held, function also checks:852*853* - That all child pages respect downlinks lower bound.854*855* - That downlink to block was encountered in parent where that's expected.856* (Limited to heapallindexed readonly callers.)857*858* This is also where heapallindexed callers use their Bloom filter to859* fingerprint IndexTuples for later IndexBuildHeapScan() verification.860*861* Note: Memory allocated in this routine is expected to be released by caller862* resetting state->targetcontext.863*/864static void865bt_target_page_check(BtreeCheckState *state)866{867OffsetNumber offset;868OffsetNumber max;869BTPageOpaque topaque;870* Check the number of attributes in high key. Note, rightmost page879* doesn't contain a high key, so nothing to check880*/881if (!P_RIGHTMOST(topaque) &&882!_bt_check_natts(state->rel, state->target, P_HIKEY))883{884ItemId itemid;885IndexTuple itup;886* Loop over page items, starting from first non-highkey item, not high904* key (if any). Most tests are not performed for the "negative infinity"905* real item (if any).906*/907for (offset = P_FIRSTDATAKEY(topaque);908offset <= max;909offset = OffsetNumberNext(offset))910{911ItemId itemid;912IndexTuple itup;913ScanKey skey;914size_t tupsize;915* lp_len should match the IndexTuple reported length exactly, since924* lp_len is completely redundant in indexes, and both sources of925* tuple length are MAXALIGN()'d. nbtree does not use lp_len all that926* frequently, and is surprisingly tolerant of corrupt lp_len fields.927*/928if (tupsize != ItemIdGetLength(itemid))929ereport(ERROR,930(errcode(ERRCODE_INDEX_CORRUPTED),931errmsg("index tuple size does not equal lp_len in index \"%s\"",932RelationGetRelationName(state->rel)),933errdetail_internal("Index tid=(%u,%u) tuple size=%zu lp_len=%u page lsn=%X/%X.",934state->targetblock, offset,935tupsize, ItemIdGetLength(itemid),936(uint32) (state->targetlsn >> 32),937(uint32) state->targetlsn),938errhint("This could be a torn page problem.")));939* Don't try to generate scankey using "negative infinity" item on976* internal pages. They are always truncated to zero attributes.977*/978if (offset_is_negative_infinity(topaque, offset))979continue;980* * High key check *999*1000* If there is a high key (if this is not the rightmost page on its1001* entire level), check that high key actually is upper bound on all1002* page items.1003*1004* We prefer to check all items against high key rather than checking1005* just the last and trusting that the operator class obeys the1006* transitive law (which implies that all previous items also1007* respected the high key invariant if they pass the item order1008* check).1009*1010* Ideally, we'd compare every item in the index against every other1011* item in the index, and not trust opclass obedience of the1012* transitive law to bridge the gap between children and their1013* grandparents (as well as great-grandparents, and so on). We don't1014* go to those lengths because that would be prohibitively expensive,1015* and probably not markedly more effective in practice.1016*/1017if (!P_RIGHTMOST(topaque) &&1018!invariant_leq_offset(state, skey, P_HIKEY))1019{1020char *itid,1021*htid;1022* * Item order check *1042*1043* Check that items are stored on page in logical order, by checking1044* current item is less than or equal to next item (if any).1045*/1046if (OffsetNumberNext(offset) <= max &&1047!invariant_leq_offset(state, skey,1048OffsetNumberNext(offset)))1049{1050char *itid,1051*htid,1052*nitid,1053*nhtid;1054* * Last item check *1088*1089* Check last item against next/right page's first data item's when1090* last item on page is reached. This additional check will detect1091* transposed pages iff the supposed right sibling page happens to1092* belong before target in the key space. (Otherwise, a subsequent1093* heap verification will probably detect the problem.)1094*1095* This check is similar to the item order check that will have1096* already been performed for every other "real" item on target page1097* when last item is checked. The difference is that the next item1098* (the item that is compared to target's last item) needs to come1099* from the next/sibling page. There may not be such an item1100* available from sibling for various reasons, though (e.g., target is1101* the rightmost page on level).1102*/1103else if (offset == max)1104{1105ScanKey rightkey;1106* As explained at length in bt_right_page_check_scankey(),1115* there is a known !readonly race that could account for1116* apparent violation of invariant, which we must check for1117* before actually proceeding with raising error. Our canary1118* condition is that target page was deleted.1119*/1120if (!state->readonly)1121{1122/* Get fresh copy of target page */1123state->target = palloc_btree_page(state, state->targetblock);1124/* Note that we deliberately do not update target LSN */1125topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);1126* All !readonly checks now performed; just return1129*/1130if (P_IGNORE(topaque))1131return;1132}1133* * Downlink check *1147*1148* Additional check of child items iff this is an internal page and1149* caller holds a ShareLock. This happens for every downlink (item)1150* in target excluding the negative-infinity downlink (again, this is1151* because it has no useful value to compare).1152*/1153if (!P_ISLEAF(topaque) && state->readonly)1154{1155BlockNumber childblock = BTreeInnerTupleGetDownLink(itup);1156* * Check if page has a downlink in parent *1163*1164* This can only be checked in heapallindexed + readonly case.1165*/1166if (state->heapallindexed && state->readonly)1167bt_downlink_missing_check(state);1168}1169/*1171* Return a scankey for an item on page to right of current target (or the1172* first non-ignorable page), sufficient to check ordering invariant on last1173* item in current target page. Returned scankey relies on local memory1174* allocated for the child page, which caller cannot pfree(). Caller's memory1175* context should be reset between calls here.1176*1177* This is the first data item, and so all adjacent items are checked against1178* their immediate sibling item (which may be on a sibling page, or even a1179* "cousin" page at parent boundaries where target's rightlink points to page1180* with different parent page). If no such valid item is available, return1181* NULL instead.1182*1183* Note that !readonly callers must reverify that target page has not1184* been concurrently deleted.1185*/1186static ScanKey1187bt_right_page_check_scankey(BtreeCheckState *state)1188{1189BTPageOpaque opaque;1190ItemId rightitem;1191BlockNumber targetnext;1192Page rightpage;1193OffsetNumber nline;1194* General notes on concurrent page splits and page deletion:1204*1205* Routines like _bt_search() don't require *any* page split interlock1206* when descending the tree, including something very light like a buffer1207* pin. That's why it's okay that we don't either. This avoidance of any1208* need to "couple" buffer locks is the raison d' etre of the Lehman & Yao1209* algorithm, in fact.1210*1211* That leaves deletion. A deleted page won't actually be recycled by1212* VACUUM early enough for us to fail to at least follow its right link1213* (or left link, or downlink) and find its sibling, because recycling1214* does not occur until no possible index scan could land on the page.1215* Index scans can follow links with nothing more than their snapshot as1216* an interlock and be sure of at least that much. (See page1217* recycling/RecentGlobalXmin notes in nbtree README.)1218*1219* Furthermore, it's okay if we follow a rightlink and find a half-dead or1220* dead (ignorable) page one or more times. There will either be a1221* further right link to follow that leads to a live page before too long1222* (before passing by parent's rightmost child), or we will find the end1223* of the entire level instead (possible when parent page is itself the1224* rightmost on its level).1225*/1226targetnext = opaque->btpo_next;1227for (;;)1228{1229CHECK_FOR_INTERRUPTS();1230* No ShareLock held case -- why it's safe to proceed.1251*1252* Problem:1253*1254* We must avoid false positive reports of corruption when caller treats1255* item returned here as an upper bound on target's last item. In1256* general, false positives are disallowed. Avoiding them here when1257* caller is !readonly is subtle.1258*1259* A concurrent page deletion by VACUUM of the target page can result in1260* the insertion of items on to this right sibling page that would1261* previously have been inserted on our target page. There might have1262* been insertions that followed the target's downlink after it was made1263* to point to right sibling instead of target by page deletion's first1264* phase. The inserters insert items that would belong on target page.1265* This race is very tight, but it's possible. This is our only problem.1266*1267* Non-problems:1268*1269* We are not hindered by a concurrent page split of the target; we'll1270* never land on the second half of the page anyway. A concurrent split1271* of the right page will also not matter, because the first data item1272* remains the same within the left half, which we'll reliably land on. If1273* we had to skip over ignorable/deleted pages, it cannot matter because1274* their key space has already been atomically merged with the first1275* non-ignorable page we eventually find (doesn't matter whether the page1276* we eventually find is a true sibling or a cousin of target, which we go1277* into below).1278*1279* Solution:1280*1281* Caller knows that it should reverify that target is not ignorable1282* (half-dead or deleted) when cross-page sibling item comparison appears1283* to indicate corruption (invariant fails). This detects the single race1284* condition that exists for caller. This is correct because the1285* continued existence of target block as non-ignorable (not half-dead or1286* deleted) implies that target page was not merged into from the right by1287* deletion; the key space at or after target never moved left. Target's1288* parent either has the same downlink to target as before, or a <=1289* downlink due to deletion at the left of target. Target either has the1290* same highkey as before, or a highkey <= before when there is a page1291* split. (The rightmost concurrently-split-from-target-page page will1292* still have the same highkey as target was originally found to have,1293* which for our purposes is equivalent to target's highkey itself never1294* changing, since we reliably skip over1295* concurrently-split-from-target-page pages.)1296*1297* In simpler terms, we allow that the key space of the target may expand1298* left (the key space can move left on the left side of target only), but1299* the target key space cannot expand right and get ahead of us without1300* our detecting it. The key space of the target cannot shrink, unless it1301* shrinks to zero due to the deletion of the original page, our canary1302* condition. (To be very precise, we're a bit stricter than that because1303* it might just have been that the target page split and only the1304* original target page was deleted. We can be more strict, just not more1305* lax.)1306*1307* Top level tree walk caller moves on to next page (makes it the new1308* target) following recovery from this race. (cf. The rationale for1309* child/downlink verification needing a ShareLock within1310* bt_downlink_check(), where page deletion is also the main source of1311* trouble.)1312*1313* Note that it doesn't matter if right sibling page here is actually a1314* cousin page, because in order for the key space to be readjusted in a1315* way that causes us issues in next level up (guiding problematic1316* concurrent insertions to the cousin from the grandparent rather than to1317* the sibling from the parent), there'd have to be page deletion of1318* target's parent page (affecting target's parent's downlink in target's1319* grandparent page). Internal page deletion only occurs when there are1320* no child pages (they were all fully deleted), and caller is checking1321* that the target's parent has at least one non-deleted (so1322* non-ignorable) child: the target page. (Note that the first phase of1323* deletion atomically marks the page to be deleted half-dead/ignorable at1324* the same time downlink in its parent is removed, so caller will1325* definitely not fail to detect that this happened.)1326*1327* This trick is inspired by the method backward scans use for dealing1328* with concurrent page splits; concurrent page deletion is a problem that1329* similarly receives special consideration sometimes (it's possible that1330* the backwards scan will re-read its "original" block after failing to1331* find a right-link to it, having already moved in the opposite direction1332* (right/"forwards") a few times to try to locate one). Just like us,1333* that happens only to determine if there was a concurrent page deletion1334* of a reference page, and just like us if there was a page deletion of1335* that reference page it means we can move on from caring about the1336* reference page. See the nbtree README for a full description of how1337* that works.1338*/1339nline = PageGetMaxOffsetNumber(rightpage);1340* Get first data item, if any1343*/1344if (P_ISLEAF(opaque) && nline >= P_FIRSTDATAKEY(opaque))1345{1346/* Return first data item (if any) */1347rightitem = PageGetItemId(rightpage, P_FIRSTDATAKEY(opaque));1348}1349else if (!P_ISLEAF(opaque) &&1350nline >= OffsetNumberNext(P_FIRSTDATAKEY(opaque)))1351{1352/*1353* Return first item after the internal page's "negative infinity"1354* item1355*/1356rightitem = PageGetItemId(rightpage,1357OffsetNumberNext(P_FIRSTDATAKEY(opaque)));1358}1359else1360{1361/*1362* No first item. Page is probably empty leaf page, but it's also1363* possible that it's an internal page with only a negative infinity1364* item.1365*/1366ereport(DEBUG1,1367(errcode(ERRCODE_NO_DATA),1368errmsg("%s block %u of index \"%s\" has no first data item",1369P_ISLEAF(opaque) ? "leaf" : "internal", targetnext,1370RelationGetRelationName(state->rel))));1371return NULL;1372}1373* Return first real item scankey. Note that this relies on right page1376* memory remaining allocated.1377*/1378return _bt_mkscankey(state->rel,1379(IndexTuple) PageGetItem(rightpage, rightitem));1380}1381/*1383* Checks one of target's downlink against its child page.1384*1385* Conceptually, the target page continues to be what is checked here. The1386* target block is still blamed in the event of finding an invariant violation.1387* The downlink insertion into the target is probably where any problem raised1388* here arises, and there is no such thing as a parent link, so doing the1389* verification this way around is much more practical.1390*/1391static void1392bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,1393ScanKey targetkey)1394{1395OffsetNumber offset;1396OffsetNumber maxoffset;1397Page child;1398BTPageOpaque copaque;1399* Caller must have ShareLock on target relation, because of1402* considerations around page deletion by VACUUM.1403*1404* NB: In general, page deletion deletes the right sibling's downlink, not1405* the downlink of the page being deleted; the deleted page's downlink is1406* reused for its sibling. The key space is thereby consolidated between1407* the deleted page and its right sibling. (We cannot delete a parent1408* page's rightmost child unless it is the last child page, and we intend1409* to also delete the parent itself.)1410*1411* If this verification happened without a ShareLock, the following race1412* condition could cause false positives:1413*1414* In general, concurrent page deletion might occur, including deletion of1415* the left sibling of the child page that is examined here. If such a1416* page deletion were to occur, closely followed by an insertion into the1417* newly expanded key space of the child, a window for the false positive1418* opens up: the stale parent/target downlink originally followed to get1419* to the child legitimately ceases to be a lower bound on all items in1420* the page, since the key space was concurrently expanded "left".1421* (Insertion followed the "new" downlink for the child, not our now-stale1422* downlink, which was concurrently physically removed in target/parent as1423* part of deletion's first phase.)1424*1425* Note that while the cross-page-same-level last item check uses a trick1426* that allows it to perform verification for !readonly callers, a similar1427* trick seems difficult here. The trick that that other check uses is,1428* in essence, to lock down race conditions to those that occur due to1429* concurrent page deletion of the target; that's a race that can be1430* reliably detected before actually reporting corruption.1431*1432* On the other hand, we'd need to lock down race conditions involving1433* deletion of child's left page, for long enough to read the child page1434* into memory (in other words, a scheme with concurrently held buffer1435* locks on both child and left-of-child pages). That's unacceptable for1436* amcheck functions on general principle, though.1437*/1438Assert(state->readonly);1439* Verify child page has the downlink key from target page (its parent) as1442* a lower bound.1443*1444* Check all items, rather than checking just the first and trusting that1445* the operator class obeys the transitive law.1446*/1447child = palloc_btree_page(state, childblock);1448copaque = (BTPageOpaque) PageGetSpecialPointer(child);1449maxoffset = PageGetMaxOffsetNumber(child);1450* Since there cannot be a concurrent VACUUM operation in readonly mode,1453* and since a page has no links within other pages (siblings and parent)1454* once it is marked fully deleted, it should be impossible to land on a1455* fully deleted page.1456*1457* It does not quite make sense to enforce that the page cannot even be1458* half-dead, despite the fact the downlink is modified at the same stage1459* that the child leaf page is marked half-dead. That's incorrect because1460* there may occasionally be multiple downlinks from a chain of pages1461* undergoing deletion, where multiple successive calls are made to1462* _bt_unlink_halfdead_page() by VACUUM before it can finally safely mark1463* the leaf page as fully dead. While _bt_mark_page_halfdead() usually1464* removes the downlink to the leaf page that is marked half-dead, that's1465* not guaranteed, so it's possible we'll land on a half-dead page with a1466* downlink due to an interrupted multi-level page deletion.1467*1468* We go ahead with our checks if the child page is half-dead. It's safe1469* to do so because we do not test the child's high key, so it does not1470* matter that the original high key will have been replaced by a dummy1471* truncated high key within _bt_mark_page_halfdead(). All other page1472* items are left intact on a half-dead page, so there is still something1473* to test.1474*/1475if (P_ISDELETED(copaque))1476ereport(ERROR,1477(errcode(ERRCODE_INDEX_CORRUPTED),1478errmsg("downlink to deleted page found in index \"%s\"",1479RelationGetRelationName(state->rel)),1480errdetail_internal("Parent block=%u child block=%u parent page lsn=%X/%X.",1481state->targetblock, childblock,1482(uint32) (state->targetlsn >> 32),1483(uint32) state->targetlsn)));1484* Skip comparison of target page key against "negative infinity"1491* item, if any. Checking it would indicate that it's not an upper1492* bound, but that's only because of the hard-coding within1493* _bt_compare().1494*/1495if (offset_is_negative_infinity(copaque, offset))1496continue;1497}1512/*1514* Checks if page is missing a downlink that it should have.1515*1516* A page that lacks a downlink/parent may indicate corruption. However, we1517* must account for the fact that a missing downlink can occasionally be1518* encountered in a non-corrupt index. This can be due to an interrupted page1519* split, or an interrupted multi-level page deletion (i.e. there was a hard1520* crash or an error during a page split, or while VACUUM was deleting a1521* multi-level chain of pages).1522*1523* Note that this can only be called in readonly mode, so there is no need to1524* be concerned about concurrent page splits or page deletions.1525*/1526static void1527bt_downlink_missing_check(BtreeCheckState *state)1528{1529BTPageOpaque topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);1530ItemId itemid;1531IndexTuple itup;1532Page child;1533BTPageOpaque copaque;1534uint32 level;1535BlockNumber childblk;1536* Incomplete (interrupted) page splits can account for the lack of a1546* downlink. Some inserting transaction should eventually complete the1547* page split in passing, when it notices that the left sibling page is1548* P_INCOMPLETE_SPLIT().1549*1550* In general, VACUUM is not prepared for there to be no downlink to a1551* page that it deletes. This is the main reason why the lack of a1552* downlink can be reported as corruption here. It's not obvious that an1553* invalid missing downlink can result in wrong answers to queries,1554* though, since index scans that land on the child may end up1555* consistently moving right. The handling of concurrent page splits (and1556* page deletions) within _bt_moveright() cannot distinguish1557* inconsistencies that last for a moment from inconsistencies that are1558* permanent and irrecoverable.1559*1560* VACUUM isn't even prepared to delete pages that have no downlink due to1561* an incomplete page split, but it can detect and reason about that case1562* by design, so it shouldn't be taken to indicate corruption. See1563* _bt_pagedel() for full details.1564*/1565if (state->rightsplit)1566{1567ereport(DEBUG1,1568(errcode(ERRCODE_NO_DATA),1569errmsg("harmless interrupted page split detected in index %s",1570RelationGetRelationName(state->rel)),1571errdetail_internal("Block=%u level=%u left sibling=%u page lsn=%X/%X.",1572state->targetblock, topaque->btpo.level,1573topaque->btpo_prev,1574(uint32) (state->targetlsn >> 32),1575(uint32) state->targetlsn)));1576return;1577}1578* Target is probably the "top parent" of a multi-level page deletion.1587* We'll need to descend the subtree to make sure that descendant pages1588* are consistent with that, though.1589*1590* If the target page (which must be non-ignorable) is a leaf page, then1591* clearly it can't be the top parent. The lack of a downlink is probably1592* a symptom of a broad problem that could just as easily cause1593* inconsistencies anywhere else.1594*/1595if (P_ISLEAF(topaque))1596ereport(ERROR,1597(errcode(ERRCODE_INDEX_CORRUPTED),1598errmsg("leaf index block lacks downlink in index \"%s\"",1599RelationGetRelationName(state->rel)),1600errdetail_internal("Block=%u page lsn=%X/%X.",1601state->targetblock,1602(uint32) (state->targetlsn >> 32),1603(uint32) state->targetlsn)));1604* Since there cannot be a concurrent VACUUM operation in readonly mode,1643* and since a page has no links within other pages (siblings and parent)1644* once it is marked fully deleted, it should be impossible to land on a1645* fully deleted page. See bt_downlink_check() for further details.1646*1647* The bt_downlink_check() P_ISDELETED() check is repeated here because1648* bt_downlink_check() does not visit pages reachable through negative1649* infinity items. Besides, bt_downlink_check() is unwilling to descend1650* multiple levels. (The similar bt_downlink_check() P_ISDELETED() check1651* within bt_check_level_from_leftmost() won't reach the page either,1652* since the leaf's live siblings should have their sibling links updated1653* to bypass the deletion target page when it is marked fully dead.)1654*1655* If this error is raised, it might be due to a previous multi-level page1656* deletion that failed to realize that it wasn't yet safe to mark the1657* leaf page as fully dead. A "dangling downlink" will still remain when1658* this happens. The fact that the dangling downlink's page (the leaf's1659* parent/ancestor page) lacked a downlink is incidental.1660*/1661if (P_ISDELETED(copaque))1662ereport(ERROR,1663(errcode(ERRCODE_INDEX_CORRUPTED),1664errmsg_internal("downlink to deleted leaf page found in index \"%s\"",1665RelationGetRelationName(state->rel)),1666errdetail_internal("Top parent/target block=%u leaf block=%u top parent/target lsn=%X/%X.",1667state->targetblock, childblk,1668(uint32) (state->targetlsn >> 32),1669(uint32) state->targetlsn)));1670* Iff leaf page is half-dead, its high key top parent link should point1673* to what VACUUM considered to be the top parent page at the instant it1674* was interrupted. Provided the high key link actually points to the1675* target page, the missing downlink we detected is consistent with there1676* having been an interrupted multi-level page deletion. This means that1677* the subtree with the target page at its root (a page deletion chain) is1678* in a consistent state, enabling VACUUM to resume deleting the entire1679* chain the next time it encounters the half-dead leaf page.1680*/1681if (P_ISHALFDEAD(copaque) && !P_RIGHTMOST(copaque))1682{1683itemid = PageGetItemId(child, P_HIKEY);1684itup = (IndexTuple) PageGetItem(child, itemid);1685if (BTreeTupleGetTopParent(itup) == state->targetblock)1686return;1687}1688}1698/*1700* Per-tuple callback from IndexBuildHeapScan, used to determine if index has1701* all the entries that definitely should have been observed in leaf pages of1702* the target index (that is, all IndexTuples that were fingerprinted by our1703* Bloom filter). All heapallindexed checks occur here.1704*1705* The redundancy between an index and the table it indexes provides a good1706* opportunity to detect corruption, especially corruption within the table.1707* The high level principle behind the verification performed here is that any1708* IndexTuple that should be in an index following a fresh CREATE INDEX (based1709* on the same index definition) should also have been in the original,1710* existing index, which should have used exactly the same representation1711*1712* Since the overall structure of the index has already been verified, the most1713* likely explanation for error here is a corrupt heap page (could be logical1714* or physical corruption). Index corruption may still be detected here,1715* though. Only readonly callers will have verified that left links and right1716* links are in agreement, and so it's possible that a leaf page transposition1717* within index is actually the source of corruption detected here (for1718* !readonly callers). The checks performed only for readonly callers might1719* more accurately frame the problem as a cross-page invariant issue (this1720* could even be due to recovery not replaying all WAL records). The !readonly1721* ERROR message raised here includes a HINT about retrying with readonly1722* verification, just in case it's a cross-page invariant issue, though that1723* isn't particularly likely.1724*1725* IndexBuildHeapScan() expects to be able to find the root tuple when a1726* heap-only tuple (the live tuple at the end of some HOT chain) needs to be1727* indexed, in order to replace the actual tuple's TID with the root tuple's1728* TID (which is what we're actually passed back here). The index build heap1729* scan code will raise an error when a tuple that claims to be the root of the1730* heap-only tuple's HOT chain cannot be located. This catches cases where the1731* original root item offset/root tuple for a HOT chain indicates (for whatever1732* reason) that the entire HOT chain is dead, despite the fact that the latest1733* heap-only tuple should be indexed. When this happens, sequential scans may1734* always give correct answers, and all indexes may be considered structurally1735* consistent (i.e. the nbtree structural checks would not detect corruption).1736* It may be the case that only index scans give wrong answers, and yet heap or1737* SLRU corruption is the real culprit. (While it's true that LP_DEAD bit1738* setting will probably also leave the index in a corrupt state before too1739* long, the problem is nonetheless that there is heap corruption.)1740*1741* Heap-only tuple handling within IndexBuildHeapScan() works in a way that1742* helps us to detect index tuples that contain the wrong values (values that1743* don't match the latest tuple in the HOT chain). This can happen when there1744* is no superseding index tuple due to a faulty assessment of HOT safety,1745* perhaps during the original CREATE INDEX. Because the latest tuple's1746* contents are used with the root TID, an error will be raised when a tuple1747* with the same TID but non-matching attribute values is passed back to us.1748* Faulty assessment of HOT-safety was behind at least two distinct CREATE1749* INDEX CONCURRENTLY bugs that made it into stable releases, one of which was1750* undetected for many years. In short, the same principle that allows a1751* REINDEX to repair corruption when there was an (undetected) broken HOT chain1752* also allows us to detect the corruption in many cases.1753*/1754static void1755bt_tuple_present_callback(Relation index, HeapTuple htup, Datum *values,1756bool *isnull, bool tupleIsAlive, void *checkstate)1757{1758BtreeCheckState *state = (BtreeCheckState *) checkstate;1759IndexTuple itup, norm;1760}1788/*1790* Normalize an index tuple for fingerprinting.1791*1792* In general, index tuple formation is assumed to be deterministic by1793* heapallindexed verification, and IndexTuples are assumed immutable. While1794* the LP_DEAD bit is mutable in leaf pages, that's ItemId metadata, which is1795* not fingerprinted. Normalization is required to compensate for corner1796* cases where the determinism assumption doesn't quite work.1797*1798* There is currently one such case: index_form_tuple() does not try to hide1799* the source TOAST state of input datums. The executor applies TOAST1800* compression for heap tuples based on different criteria to the compression1801* applied within btinsert()'s call to index_form_tuple(): it sometimes1802* compresses more aggressively, resulting in compressed heap tuple datums but1803* uncompressed corresponding index tuple datums. A subsequent heapallindexed1804* verification will get a logically equivalent though bitwise unequal tuple1805* from index_form_tuple(). False positive heapallindexed corruption reports1806* could occur without normalizing away the inconsistency.1807*1808* Returned tuple is often caller's own original tuple. Otherwise, it is a1809* new representation of caller's original index tuple, palloc()'d in caller's1810* memory context.1811*1812* Note: This routine is not concerned with distinctions about the1813* representation of tuples beyond those that might break heapallindexed1814* verification. In particular, it won't try to normalize opclass-equal1815* datums with potentially distinct representations (e.g., btree/numeric_ops1816* index datums will not get their display scale normalized-away here).1817* Normalization may need to be expanded to handle more cases in the future,1818* though. For example, it's possible that non-pivot tuples could in the1819* future have alternative logically equivalent representations due to using1820* the INDEX_ALT_TID_MASK bit to implement intelligent deduplication.1821*/1822static IndexTuple1823bt_normalize_tuple(BtreeCheckState *state, IndexTuple itup)1824{1825TupleDesc tupleDescriptor = RelationGetDescr(state->rel);1826Datum normalized[INDEX_MAX_KEYS];1827bool isnull[INDEX_MAX_KEYS];1828bool toast_free[INDEX_MAX_KEYS];1829bool formnewtup = false;1830IndexTuple reformed;1831int i;1832* Callers always pass a tuple that could safely be inserted into the1853* index without further processing, so an external varlena header1854* should never be encountered here1855*/1856if (VARATT_IS_EXTERNAL(DatumGetPointer(normalized[i])))1857ereport(ERROR,1858(errcode(ERRCODE_INDEX_CORRUPTED),1859errmsg("external varlena datum in tuple that references heap row (%u,%u) in index \"%s\"",1860ItemPointerGetBlockNumber(&(itup->t_tid)),1861ItemPointerGetOffsetNumber(&(itup->t_tid)),1862RelationGetRelationName(state->rel))));1863else if (VARATT_IS_COMPRESSED(DatumGetPointer(normalized[i])))1864{1865formnewtup = true;1866normalized[i] = PointerGetDatum(PG_DETOAST_DATUM(normalized[i]));1867toast_free[i] = true;1868}1869}1870* Hard case: Tuple had compressed varlena datums that necessitate1877* creating normalized version of the tuple from uncompressed input datums1878* (normalized input datums). This is rather naive, but shouldn't be1879* necessary too often.1880*1881* Note that we rely on deterministic index_form_tuple() TOAST compression1882* of normalized input.1883*/1884reformed = index_form_tuple(tupleDescriptor, normalized, isnull);1885reformed->t_tid = itup->t_tid;1886}1894/*1896* Is particular offset within page (whose special state is passed by caller)1897* the page negative-infinity item?1898*1899* As noted in comments above _bt_compare(), there is special handling of the1900* first data item as a "negative infinity" item. The hard-coding within1901* _bt_compare() makes comparing this item for the purposes of verification1902* pointless at best, since the IndexTuple only contains a valid TID (a1903* reference TID to child page).1904*/1905static inline bool1906offset_is_negative_infinity(BTPageOpaque opaque, OffsetNumber offset)1907{1908/*1909* For internal pages only, the first item after high key, if any, is1910* negative infinity item. Internal pages always have a negative infinity1911* item, whereas leaf pages never have one. This implies that negative1912* infinity item is either first or second line item, or there is none1913* within page.1914*1915* Negative infinity items are a special case among pivot tuples. They1916* always have zero attributes, while all other pivot tuples always have1917* nkeyatts attributes.1918*1919* Right-most pages don't have a high key, but could be said to1920* conceptually have a "positive infinity" high key. Thus, there is a1921* symmetry between down link items in parent pages, and high keys in1922* children. Together, they represent the part of the key space that1923* belongs to each page in the index. For example, all children of the1924* root page will have negative infinity as a lower bound from root1925* negative infinity downlink, and positive infinity as an upper bound1926* (implicitly, from "imaginary" positive infinity high key in root).1927*/1928return !P_ISLEAF(opaque) && offset == P_FIRSTDATAKEY(opaque);1929}1930/*1932* Does the invariant hold that the key is less than or equal to a given upper1933* bound offset item?1934*1935* If this function returns false, convention is that caller throws error due1936* to corruption.1937*/1938static inline bool1939invariant_leq_offset(BtreeCheckState *state, ScanKey key,1940OffsetNumber upperbound)1941{1942int16 nkeyatts = IndexRelationGetNumberOfKeyAttributes(state->rel);1943int32 cmp;1944}1949/*1951* Does the invariant hold that the key is greater than or equal to a given1952* lower bound offset item?1953*1954* If this function returns false, convention is that caller throws error due1955* to corruption.1956*/1957static inline bool1958invariant_geq_offset(BtreeCheckState *state, ScanKey key,1959OffsetNumber lowerbound)1960{1961int16 nkeyatts = IndexRelationGetNumberOfKeyAttributes(state->rel);1962int32 cmp;1963}1968/*1970* Does the invariant hold that the key is less than or equal to a given upper1971* bound offset item, with the offset relating to a caller-supplied page that1972* is not the current target page? Caller's non-target page is typically a1973* child page of the target, checked as part of checking a property of the1974* target page (i.e. the key comes from the target).1975*1976* If this function returns false, convention is that caller throws error due1977* to corruption.1978*/1979static inline bool1980invariant_leq_nontarget_offset(BtreeCheckState *state,1981Page nontarget, ScanKey key,1982OffsetNumber upperbound)1983{1984int16 nkeyatts = IndexRelationGetNumberOfKeyAttributes(state->rel);1985int32 cmp;1986}1991/*1993* Given a block number of a B-Tree page, return page in palloc()'d memory.1994* While at it, perform some basic checks of the page.1995*1996* There is never an attempt to get a consistent view of multiple pages using1997* multiple concurrent buffer locks; in general, we only acquire a single pin1998* and buffer lock at a time, which is often all that the nbtree code requires.1999*2000* Operating on a copy of the page is useful because it prevents control2001* getting stuck in an uninterruptible state when an underlying operator class2002* misbehaves.2003*/2004static Page2005palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum)2006{2007Buffer buffer;2008Page page;2009BTPageOpaque opaque;2010OffsetNumber maxoffset;2011* We copy the page into local storage to avoid holding pin on the buffer2016* longer than we must.2017*/2018buffer = ReadBufferExtended(state->rel, MAIN_FORKNUM, blocknum, RBM_NORMAL,2019state->checkstrategy);2020LockBuffer(buffer, BT_READ);2021* Perform the same basic sanity checking that nbtree itself performs for2024* every page:2025*/2026_bt_checkpage(state->rel, buffer);2027* Deleted pages have no sane "level" field, so can only check non-deleted2068* page level2069*/2070if (P_ISLEAF(opaque) && !P_ISDELETED(opaque) && opaque->btpo.level != 0)2071ereport(ERROR,2072(errcode(ERRCODE_INDEX_CORRUPTED),2073errmsg("invalid leaf page level %u for block %u in index \"%s\"",2074opaque->btpo.level, blocknum, RelationGetRelationName(state->rel))));2075* Sanity checks for number of items on page.2085*2086* As noted at the beginning of _bt_binsrch(), an internal page must have2087* children, since there must always be a negative infinity downlink2088* (there may also be a highkey). In the case of non-rightmost leaf2089* pages, there must be at least a highkey. Deleted pages on replica2090* might contain no items, because page unlink re-initializes2091* page-to-be-deleted. Deleted pages with no items might be on primary2092* too due to preceding recovery, but on primary new deletions can't2093* happen concurrently to amcheck.2094*2095* This is correct when pages are half-dead, since internal pages are2096* never half-dead, and leaf pages must have a high key when half-dead2097* (the rightmost page can never be deleted). It's also correct with2098* fully deleted pages: _bt_unlink_halfdead_page() doesn't change anything2099* about the target page other than setting the page as fully dead, and2100* setting its xact field. In particular, it doesn't change the sibling2101* links in the deletion target itself, since they're required when index2102* scans land on the deletion target, and then need to move right (or need2103* to move left, in the case of backward index scans).2104*/2105maxoffset = PageGetMaxOffsetNumber(page);2106if (maxoffset > MaxIndexTuplesPerPage)2107ereport(ERROR,2108(errcode(ERRCODE_INDEX_CORRUPTED),2109errmsg("Number of items on block %u of index \"%s\" exceeds MaxIndexTuplesPerPage (%u)",2110blocknum, RelationGetRelationName(state->rel),2111MaxIndexTuplesPerPage)));2112* In general, internal pages are never marked half-dead, except on2127* versions of Postgres prior to 9.4, where it can be valid transient2128* state. This state is nonetheless treated as corruption by VACUUM on2129* from version 9.4 on, so do the same here. See _bt_pagedel() for full2130* details.2131*2132* Internal pages should never have garbage items, either.2133*/2134if (!P_ISLEAF(opaque) && P_ISHALFDEAD(opaque))2135ereport(ERROR,2136(errcode(ERRCODE_INDEX_CORRUPTED),2137errmsg("internal page block %u in index \"%s\" is half-dead",2138blocknum, RelationGetRelationName(state->rel)),2139errhint("This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));2140}2149