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