amcheck (B-Tree integrity checking tool)

From 06085b27dc36c1e05e0049d90374b9c687e5ea9a Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Tue, 10 Jun 2014 22:20:40 -0700
Subject: [PATCH] Add amcheck extension to contrib

The new extension makes available two SQL-callable functions, each of
which accept a single argument (a regclass/nbtree index relation
argument) and return void.

The SQL-callable function bt_index_check() checks invariants of the
target index by walking the tree, performing various checks of the
sanity of the page space using insertion scankeys to compare items.  The
SQL-callable function bt_index_parent_check() performs a superset of the
checks performed by bt_index_check(): the same checks, as well as
another check verifying that each downlink is actually respected as a
lower bound on its child page.

bt_index_check() requires only an AccessShareLock on the target.
bt_index_parent_check() requires an ExclusiveLock on the target,
and ShareLock on its heap relation.

To test amcheck, add regression tests that feature a variety of CREATE
INDEX statements (these are always external sort cases), and verify the
indexes afterwards in each case.  Aside from testing amcheck itself,
this approach also fills a gap in the test coverage of the standard
regression tests, since external sorts were previously completely
untested.  This also makes it possible to test OS collations without any
specific expectation about an "expected" pg_regress output, or even
specific advanced knowledge of which collations are to be tested.
---
 contrib/Makefile                                   |    1 +
 contrib/amcheck/Makefile                           |   22 +
 contrib/amcheck/amcheck--1.0.sql                   |   20 +
 contrib/amcheck/amcheck.c                          | 1265 ++++++++++++++++++++
 contrib/amcheck/amcheck.control                    |    5 +
 contrib/amcheck/expected/extern_sort_bytea.out     |   44 +
 .../amcheck/expected/extern_sort_collations.out    |   42 +
 contrib/amcheck/expected/extern_sort_numeric.out   |   44 +
 contrib/amcheck/expected/install_amcheck.out       |    1 +
 contrib/amcheck/sql/extern_sort_bytea.sql          |   23 +
 contrib/amcheck/sql/extern_sort_collations.sql     |   42 +
 contrib/amcheck/sql/extern_sort_numeric.sql        |   29 +
 contrib/amcheck/sql/install_amcheck.sql            |    1 +
 doc/src/sgml/amcheck.sgml                          |  247 ++++
 doc/src/sgml/contrib.sgml                          |    1 +
 doc/src/sgml/filelist.sgml                         |    1 +
 16 files changed, 1788 insertions(+)
 create mode 100644 contrib/amcheck/Makefile
 create mode 100644 contrib/amcheck/amcheck--1.0.sql
 create mode 100644 contrib/amcheck/amcheck.c
 create mode 100644 contrib/amcheck/amcheck.control
 create mode 100644 contrib/amcheck/expected/extern_sort_bytea.out
 create mode 100644 contrib/amcheck/expected/extern_sort_collations.out
 create mode 100644 contrib/amcheck/expected/extern_sort_numeric.out
 create mode 100644 contrib/amcheck/expected/install_amcheck.out
 create mode 100644 contrib/amcheck/sql/extern_sort_bytea.sql
 create mode 100644 contrib/amcheck/sql/extern_sort_collations.sql
 create mode 100644 contrib/amcheck/sql/extern_sort_numeric.sql
 create mode 100644 contrib/amcheck/sql/install_amcheck.sql
 create mode 100644 doc/src/sgml/amcheck.sgml

diff --git a/contrib/Makefile b/contrib/Makefile
index d12dd63..cecfb6d 100644
--- a/contrib/Makefile
+++ b/contrib/Makefile
@@ -6,6 +6,7 @@ include $(top_builddir)/src/Makefile.global
 
 SUBDIRS = \
 		adminpack	\
+		amcheck		\
 		auth_delay	\
 		auto_explain	\
 		btree_gin	\
diff --git a/contrib/amcheck/Makefile b/contrib/amcheck/Makefile
new file mode 100644
index 0000000..26b7b9b
--- /dev/null
+++ b/contrib/amcheck/Makefile
@@ -0,0 +1,22 @@
+# contrib/amcheck/Makefile
+
+MODULE_big	= amcheck
+OBJS		= amcheck.o $(WIN32RES)
+
+EXTENSION = amcheck
+DATA = amcheck--1.0.sql
+PGFILEDESC = "amcheck - functions to verify access method invariants"
+
+REGRESS = install_amcheck extern_sort_bytea \
+	extern_sort_collations extern_sort_numeric
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/amcheck
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/amcheck/amcheck--1.0.sql b/contrib/amcheck/amcheck--1.0.sql
new file mode 100644
index 0000000..ebbd6ac
--- /dev/null
+++ b/contrib/amcheck/amcheck--1.0.sql
@@ -0,0 +1,20 @@
+/* contrib/amcheck/amcheck--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION amcheck" to load this file. \quit
+
+--
+-- bt_index_check()
+--
+CREATE FUNCTION bt_index_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'bt_index_check'
+LANGUAGE C STRICT;
+
+--
+-- bt_index_parent_check()
+--
+CREATE FUNCTION bt_index_parent_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'bt_index_parent_check'
+LANGUAGE C STRICT;
diff --git a/contrib/amcheck/amcheck.c b/contrib/amcheck/amcheck.c
new file mode 100644
index 0000000..66d1f4f
--- /dev/null
+++ b/contrib/amcheck/amcheck.c
@@ -0,0 +1,1265 @@
+/*-------------------------------------------------------------------------
+ *
+ * amcheck.c
+ *		Verifies the integrity of access methods based on invariants.
+ *
+ * Provides SQL-callable functions for verifying that various logical
+ * invariants in the structure of index access methods are respected.  This
+ * includes, for example, the invariant that each page in the target B-Tree
+ * index has "real" items in logical order as reported by an insertion scankey
+ * (the insertion scankey sort-wise NULL semantics are useful for
+ * verification).
+ *
+ *
+ * Copyright (c) 2016, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  contrib/amcheck/amcheck.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/nbtree.h"
+#include "access/transam.h"
+#include "catalog/index.h"
+#include "catalog/pg_am.h"
+#include "commands/tablecmds.h"
+#include "miscadmin.h"
+#include "storage/lmgr.h"
+#include "utils/memutils.h"
+#include "utils/snapmgr.h"
+
+
+PG_MODULE_MAGIC;
+
+#define CHECK_SUPERUSER() { \
+		if (!superuser()) \
+			ereport(ERROR, \
+					(errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), \
+					 (errmsg("must be superuser to use verification functions")))); }
+
+/*
+* As noted in comments above _bt_compare(), there is special handling of the
+* first data item (that is, the first item with a valid downlink -- not the
+* high key item) on a non-leaf (internal) page.  There is clearly no point in
+* having amcheck functions make any comparison of or against these "minus
+* infinity" items, because they contain no actual information other than the
+* downlink.
+*/
+#define OFFSET_IS_MINUS_INFINITY(opaque, offset) \
+	(!P_ISLEAF(opaque) && offset == P_FIRSTDATAKEY(opaque))
+
+/*
+ * Callers to verification functions should never receive a false positive
+ * indication of corruption.  Therefore, when using amcheck functions for
+ * stress testing, it may be useful to temporally change the CORRUPTION elevel
+ * to PANIC, to immediately halt the server in the event of detecting an
+ * invariant condition violation.  This may preserve more information about the
+ * nature of the underlying problem.  Note that modifying the CORRUPTION
+ * constant to be an elevel < ERROR is not well tested.
+ */
+#ifdef NOT_USED
+#define CORRUPTION		PANIC
+#define CONCERN			WARNING
+#else
+#define CORRUPTION		ERROR
+#define CONCERN			INFO
+#endif
+
+/*
+ * A B-Tree cannot possibly have this many levels, since there must be one
+ * block per level, which is bound by the range of BlockNumber:
+ */
+#define InvalidBtreeLevel	((uint32) InvalidBlockNumber)
+
+/*
+ * State associated with verifying a B-Tree index
+ */
+typedef struct BtreeCheckState
+{
+	/*
+	 * Unchanging state, established at start of verification:
+	 *
+	 * rel:                 B-Tree Index Relation
+	 * exclusivelock:       ExclusiveLock held on rel; else AccessShareLock
+	 * checkstrategy:       Buffer access strategy
+	 * targetcontext:       Target page memory context
+	 */
+	Relation				rel;
+	bool					exclusivelock;
+	BufferAccessStrategy 	checkstrategy;
+	MemoryContext			targetcontext;
+
+	/*
+	 * Mutable state, for verification of particular page:
+	 *
+	 * target:              Main target page
+	 * targetblock:         Main target page's block number
+	 * targetlsn:           Main target page's LSN
+	 *
+	 * target is the point of reference for a verification operation.
+	 *
+	 * Note: targetlsn is always from "target".  It is stashed here out of
+	 * convenience.
+	 *
+	 * Other B-Tree pages may be allocated, but those are always auxiliary
+	 * (e.g. they are target's child pages).  Conceptually, only the target
+	 * page is checked.  Each page found by verification's left/right,
+	 * top/bottom scan becomes the target once.
+	 *
+	 * Memory is managed by resetting targetcontext after verification of some
+	 * target page finishes (possibly including target verification that
+	 * depends on non-target page state).
+	 */
+	Page					target;
+	BlockNumber				targetblock;
+	XLogRecPtr				targetlsn;
+
+} BtreeCheckState;
+
+/*
+ * Starting point for verifying an entire B-Tree index level
+ */
+typedef struct BtreeLevel
+{
+	/* Level number (0 is leaf page level). */
+	uint32			level;
+
+	/* Left most block on level.  Scan of level begins here. */
+	BlockNumber		leftmost;
+
+	/* Is this level reported as "true" root level by meta page? */
+	bool			istruerootlevel;
+} BtreeLevel;
+
+PG_FUNCTION_INFO_V1(bt_index_check);
+PG_FUNCTION_INFO_V1(bt_index_parent_check);
+
+static void btree_index_checkable(Relation rel);
+static void bt_check_every_level(Relation rel, bool exclusivelock);
+static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state,
+											   BtreeLevel level);
+static void bt_target_page_check(BtreeCheckState *state);
+static ScanKey bt_right_page_check_scankey(BtreeCheckState *state);
+static void bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
+							  ScanKey targetkey);
+static bool invariant_key_less_than_equal_offset(BtreeCheckState *state,
+												 ScanKey key,
+												 OffsetNumber upperbound);
+static bool invariant_key_greater_than_equal_offset(BtreeCheckState *state,
+													ScanKey key,
+													OffsetNumber lowerbound);
+static bool invariant_key_less_than_equal_nontarget_offset(BtreeCheckState *state,
+														   Page other,
+														   ScanKey key,
+														   OffsetNumber upperbound);
+static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum);
+
+/*
+ * bt_index_check(index regclass)
+ *
+ * Verify integrity of B-Tree index.
+ *
+ * Only acquires AccessShareLock on index relation.  Does not consider
+ * invariants that exist between parent/child pages.
+ */
+Datum
+bt_index_check(PG_FUNCTION_ARGS)
+{
+	Oid			relid = PG_GETARG_OID(0);
+	Relation	indrel;
+
+	CHECK_SUPERUSER();
+
+	indrel = relation_open(relid, AccessShareLock);
+
+	/* Relation suitable for checking as B-Tree? */
+	btree_index_checkable(indrel);
+
+	/* Check index */
+	bt_check_every_level(indrel, false);
+
+	relation_close(indrel, AccessShareLock);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * bt_index_parent_check(index regclass)
+ *
+ * Verify integrity of B-Tree index.
+ *
+ * Acquires ExclusiveLock on index relation, and ShareLock on the associated
+ * heap relation, a bit like REINDEX.  Verifies that downlinks in parent pages
+ * are valid lower bounds on child pages.
+ */
+Datum
+bt_index_parent_check(PG_FUNCTION_ARGS)
+{
+	Oid			indrelid = PG_GETARG_OID(0);
+	Oid			heapid;
+	Relation	indrel;
+	Relation	heaprel;
+
+	CHECK_SUPERUSER();
+
+	/*
+	 * We must lock table before index to avoid deadlocks.  However, if the
+	 * passed indrelid isn't an index then IndexGetRelation() will fail.
+	 * Rather than emitting a not-very-helpful error message, postpone
+	 * complaining, expecting that the is-it-an-index test below will fail.
+	 */
+	heapid = IndexGetRelation(indrelid, true);
+	if (OidIsValid(heapid))
+		heaprel = heap_open(heapid, ShareLock);
+	else
+		heaprel = NULL;
+
+	/*
+	 * Open the target index relations separately (like relation_openrv(), but
+	 * with heap relation locked first to prevent deadlocking).  In hot standby
+	 * mode this will raise an error.
+	 */
+	indrel = index_open(indrelid, ExclusiveLock);
+
+	/* Check for active uses of the index in the current transaction */
+	CheckTableNotInUse(indrel, "bt_index_parent_check");
+
+	/* Relation suitable for checking as B-Tree? */
+	btree_index_checkable(indrel);
+
+	/* Check index */
+	bt_check_every_level(indrel, true);
+
+	index_close(indrel, ExclusiveLock);
+	if (heaprel)
+		heap_close(heaprel, ShareLock);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * btree_index_checkable()
+ *
+ * Basic checks about the suitability of a relation for checking as a B-Tree
+ * index.
+ */
+static void
+btree_index_checkable(Relation rel)
+{
+	if (rel->rd_rel->relkind != RELKIND_INDEX ||
+		rel->rd_rel->relam != BTREE_AM_OID)
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("only nbtree access method indexes are supported"),
+				 errdetail("index \"%s\" does not using the nbtree access method.",
+						   RelationGetRelationName(rel))));
+
+	if (RELATION_IS_OTHER_TEMP(rel))
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot access temporary tables of other sessions"),
+				 errdetail("index \"%s\" is associated with temporary relation.",
+						   RelationGetRelationName(rel))));
+
+	if (!rel->rd_index->indisready)
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot check index \"%s\"",
+						RelationGetRelationName(rel)),
+				 errdetail("index is not yet ready for insertions")));
+
+	if (!rel->rd_index->indisvalid)
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot check index \"%s\"",
+						RelationGetRelationName(rel)),
+				 errdetail("index is not valid")));
+}
+
+/*
+ * bt_check_every_level()
+ *
+ * Main entry point for B-Tree SQL-callable functions.  Walks the B-Tree in
+ * logical order, verifying invariants as it goes.
+ *
+ * It is the caller's responsibility to acquire appropriate heavyweight lock on
+ * the index relation, and advise us if extra checks are safe when an
+ * ExclusiveLock is held.  An ExclusiveLock is generally assumed to prevent any
+ * kind of physical modification to the index structure, including
+ * modifications that VACUUM may make.
+ */
+static void
+bt_check_every_level(Relation rel, bool exclusivelock)
+{
+	BtreeCheckState	   *state;
+	Page				metapage;
+	BTMetaPageData	   *metad;
+	uint32				previouslevel;
+	BtreeLevel			current;
+
+	/*
+	 * RecentGlobalXmin assertion matches index_getnext_tid().  See note on
+	 * RecentGlobalXmin/B-Tree page deletion.
+	 */
+	Assert(TransactionIdIsValid(RecentGlobalXmin));
+
+	/*
+	 * Initialize state for entire verification operation
+	 */
+	state = palloc(sizeof(BtreeCheckState));
+	state->rel = rel;
+	state->exclusivelock = exclusivelock;
+	state->checkstrategy = GetAccessStrategy(BAS_BULKREAD);
+	/* Create context for page */
+	state->targetcontext = AllocSetContextCreate(CurrentMemoryContext,
+												 "amcheck page data",
+												 ALLOCSET_DEFAULT_MINSIZE,
+												 ALLOCSET_DEFAULT_INITSIZE,
+												 ALLOCSET_DEFAULT_MAXSIZE);
+
+	/* Get true root block from meta-page */
+	metapage = palloc_btree_page(state, BTREE_METAPAGE);
+	metad = BTPageGetMeta(metapage);
+
+	/*
+	 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
+	 * the fast root and true root differ.
+	 *
+	 * Start from the true root, not the fast root, unlike conventional index
+	 * scans.  This approach is more thorough, and removes the risk of
+	 * following a stale fast root from the meta page.
+	 */
+	if (metad->btm_fastroot != metad->btm_root)
+		ereport(CONCERN,
+				(errcode(ERRCODE_DUPLICATE_OBJECT),
+				 errmsg("fast root mismatch in index %s",
+						RelationGetRelationName(rel)),
+				 errdetail_internal("Fast block %u (level %u) "
+									"differs from true root "
+									"block %u (level %u).",
+									metad->btm_fastroot, metad->btm_fastlevel,
+									metad->btm_root, metad->btm_level)));
+
+	/*
+	 * Starting at the root, verify every level.  Move left to right, top to
+	 * bottom.  Note that there may be no pages other than the meta page (meta
+	 * page can indicate that root is P_NONE when the index is totally empty).
+	 */
+	previouslevel = InvalidBtreeLevel;
+	current.level = metad->btm_level;
+	current.leftmost = metad->btm_root;
+	current.istruerootlevel =  true;
+	while (current.leftmost != P_NONE)
+	{
+		/*
+		 * Verify this level, and get left most page for next level down, if
+		 * not at leaf level
+		 */
+		current = bt_check_level_from_leftmost(state, current);
+
+		if (current.leftmost == InvalidBlockNumber)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("index \"%s\" has no valid pages on level below %u or first level",
+							RelationGetRelationName(rel), previouslevel)));
+
+		previouslevel = current.level;
+	}
+
+	/* Be tidy: */
+	MemoryContextDelete(state->targetcontext);
+}
+
+/*
+ * bt_check_level_from_leftmost()
+ *
+ * Given a left-most block at some level, move right, verifying each page
+ * individually (with more verification across pages for "exclusivelock"
+ * callers).  Caller should pass the true root page as the leftmost initially,
+ * working their way down by passing what is returned for the last call here
+ * until level 0 (leaf page level) was reached.
+ *
+ * Returns state for next call, if any.  This includes left-most block number
+ * one level lower that should be checked on next call here, or P_NONE when
+ * leaf level is to be checked.  The nbtree level number convention is that
+ * higher levels have higher numbers, because new levels are added only due to
+ * a root page split.  Prior to the first root page split, when there are only
+ * two pages (the root page and the meta page), the root page is classified as
+ * a leaf page, not an internal page.
+ *
+ * Note on memory management:  State's per-page context is reset here, between
+ * each call to bt_target_page_check().
+ */
+static BtreeLevel
+bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
+{
+	/* State to establish early, concerning entire level */
+	BTPageOpaque	opaque;
+	MemoryContext 	oldcontext;
+	BtreeLevel		nextleveldown;
+
+	/* Variables for iterating across level using right links */
+	BlockNumber		leftcurrent = P_NONE;
+	BlockNumber		current = level.leftmost;
+
+	/* Initialize return state */
+	nextleveldown.leftmost = InvalidBlockNumber;
+	nextleveldown.level = InvalidBtreeLevel;
+	nextleveldown.istruerootlevel = false;
+
+	/* Use page-level context for duration of this call */
+	oldcontext = MemoryContextSwitchTo(state->targetcontext);
+
+	elog(DEBUG1, "verifying level %u%s", level.level,
+		 level.istruerootlevel?
+		 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
+
+	do
+	{
+		/* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
+		CHECK_FOR_INTERRUPTS();
+
+		/* Initialize state for this iteration */
+		state->targetblock = current;
+		state->target = palloc_btree_page(state, state->targetblock);
+		state->targetlsn = PageGetLSN(state->target);
+
+		opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+		if (P_IGNORE(opaque))
+		{
+			if (P_RIGHTMOST(opaque))
+				ereport(CORRUPTION,
+						(errcode(ERRCODE_INDEX_CORRUPTED),
+						 errmsg("block %u fell off the end of index \"%s\"",
+								current, RelationGetRelationName(state->rel))));
+			else
+				ereport(CONCERN,
+						(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+						 errmsg("block %u of index \"%s\" ignored",
+								current, RelationGetRelationName(state->rel))));
+			goto nextpage;
+		}
+		else if (nextleveldown.leftmost == InvalidBlockNumber)
+		{
+			/*
+			 * A concurrent page split could make the caller supplied leftmost
+			 * block no longer contain the leftmost page, or no longer be the
+			 * true root, but where that isn't possible due to heavyweight
+			 * locking, check that the first valid page meets caller's
+			 * expectations.
+			 */
+			if (state->exclusivelock)
+			{
+				if (!P_LEFTMOST(opaque))
+					ereport(CORRUPTION,
+							(errcode(ERRCODE_INDEX_CORRUPTED),
+							 errmsg("block %u is not leftmost in index \"%s\"",
+									current, RelationGetRelationName(state->rel))));
+
+				if (level.istruerootlevel && !P_ISROOT(opaque))
+					ereport(CORRUPTION,
+							(errcode(ERRCODE_INDEX_CORRUPTED),
+							 errmsg("block %u is not true root in index \"%s\"",
+									current, RelationGetRelationName(state->rel))));
+			}
+
+			/*
+			 * Before beginning any non-trivial examination of level, establish
+			 * next level down's leftmost block number, which next call here
+			 * will pass as its leftmost (iff this isn't leaf level).
+			 *
+			 * There should be at least one non-ignorable page per level.
+			 */
+			if (!P_ISLEAF(opaque))
+			{
+				IndexTuple		itup;
+				ItemId			itemid;
+
+				/* Internal page -- downlink gets leftmost on next level */
+				itemid = PageGetItemId(state->target, P_FIRSTDATAKEY(opaque));
+				itup = (IndexTuple) PageGetItem(state->target, itemid);
+				nextleveldown.leftmost = ItemPointerGetBlockNumber(&(itup->t_tid));
+				nextleveldown.level = opaque->btpo.level - 1;
+			}
+			else
+			{
+				/*
+				 * Leaf page -- final level caller must process.
+				 *
+				 * Note that this could also be the root page, if there has
+				 * been no root page split yet.
+				 */
+				nextleveldown.leftmost = P_NONE;
+				nextleveldown.level = InvalidBtreeLevel;
+			}
+
+			/*
+			 * Finished setting up state for this call/level.  Control will
+			 * never end up back here in any future loop iteration for this
+			 * level.
+			 */
+		}
+
+		if (state->exclusivelock && opaque->btpo_prev != leftcurrent)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("right link/left link pair in index \"%s\" not in mutual agreement",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Deleted block=%u left block=%u link reported block=%u.",
+										current, leftcurrent, opaque->btpo_prev)));
+
+		/* Verify invariants for page -- all important checks occur here */
+		bt_target_page_check(state);
+
+nextpage:
+
+		/* Try to detect circular links */
+		if (current == leftcurrent || current == opaque->btpo_prev)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("circular link chain found in block %u of index \"%s\"",
+							current, RelationGetRelationName(state->rel))));
+
+		leftcurrent = current;
+		current = opaque->btpo_next;
+
+		/* Free page and associated memory for this iteration */
+		MemoryContextReset(state->targetcontext);
+	}
+	while (current != P_NONE);
+
+	/* Don't change context for caller */
+	MemoryContextSwitchTo(oldcontext);
+
+	return nextleveldown;
+}
+
+/*
+ * bt_target_page_check()
+ *
+ * Function performs the following checks on target page, or pages ancillary to
+ * target page:
+ *
+ * - That every "real" data item is less than or equal to the high key, which
+ *   is an upper bound on the items on the pages (where there is a high key at
+ *   all -- pages that are rightmost lack one).
+ *
+ * - That within the page, every "real" item is less than or equal to the item
+ *   immediately to its right, if any (i.e., that the items are in order within
+ *   the page, so that the binary searches performed by index scans are sane).
+ *
+ * - That the last item stored on the page is less than or equal to the first
+ *   "real" data item on the page to the right (if such a first item is
+ *   available from next page).
+ *
+ * Furthermore, when state passed shows ExclusiveLock held, function also
+ * checks:
+ *
+ * - That all child pages respect downlinks lower bound (internal pages only).
+ *
+ * Note:  This routine is not especially proactive in freeing memory.  High
+ * watermark memory consumption is bound to some small fixed multiple of
+ * BLCKSZ, though.  Caller should reset the current context between calls here.
+ */
+static void
+bt_target_page_check(BtreeCheckState *state)
+{
+	OffsetNumber	offset;
+	OffsetNumber	max;
+	BTPageOpaque	topaque;
+
+	topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+	max = PageGetMaxOffsetNumber(state->target);
+
+	elog(DEBUG1, "verifying %u items on %s block %u", max,
+		 P_ISLEAF(topaque) ? "leaf":"internal", state->targetblock);
+
+	/*
+	 * Loop over page items, but don't start from P_HIKEY (don't have iteration
+	 * directly considering high key item, if any).  That's something that is
+	 * used as part of verifying all other items, but doesn't get its own
+	 * iteration.
+	 */
+	for (offset = P_FIRSTDATAKEY(topaque);
+		 offset <= max;
+		 offset = OffsetNumberNext(offset))
+	{
+		ItemId		itemid;
+		IndexTuple	itup;
+		ScanKey		skey;
+
+		CHECK_FOR_INTERRUPTS();
+
+		/* Don't try to generate scankey using "minus infinity" garbage data */
+		if (OFFSET_IS_MINUS_INFINITY(topaque, offset))
+			continue;
+
+		/* Build insertion scankey for current page offset */
+		itemid = PageGetItemId(state->target, offset);
+		itup = (IndexTuple) PageGetItem(state->target, itemid);
+		skey = _bt_mkscankey(state->rel, itup);
+
+		/*
+		 *   ********************
+		 *   * High key check   *
+		 *   ********************
+		 *
+		 * If there is a high key, which there must be for a non-rightmost
+		 * page, check that it actually is upper bound on all page items.
+		 *
+		 * We prefer to check all items, rather than checking just the first
+		 * and trusting that the operator class obeys the transitive law (which
+		 * implies that all subsequent items also respected the high key
+		 * invariant if they pass the page order check).
+		 *
+		 * Ideally, we'd compare every item in the index against every other
+		 * item in the index, and not trust opclass obedience of the transitive
+		 * law to bridge the gap between children and their grandparents (as
+		 * well as great-grandparents, and so on).  We don't go to those
+		 * lengths because that would be prohibitively expensive, and probably
+		 * not markedly more effective in practice.
+		 */
+		if (!P_RIGHTMOST(topaque) &&
+			!invariant_key_less_than_equal_offset(state, skey, P_HIKEY))
+		{
+			char	   *itid,  *htid;
+
+			itid = psprintf("(%u,%u)", state->targetblock, offset);
+			htid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("high key invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Index tid=%s points to %s tid=%s "
+										"page lsn=%X/%X.",
+										itid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										htid,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+		}
+
+		/*
+		 *   ********************
+		 *   * Page order check *
+		 *   ********************
+		 *
+		 * Check that items are stored on page in logical order, by checking
+		 * current item is less than or equal to next item (if any).
+		 */
+		if (OffsetNumberNext(offset) <= max &&
+			!invariant_key_less_than_equal_offset(state, skey,
+												  OffsetNumberNext(offset)))
+		{
+			char	   *itid,  *htid,
+					   *nitid, *nhtid;
+
+			itid = psprintf("(%u,%u)", state->targetblock, offset);
+			htid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+			nitid = psprintf("(%u,%u)", state->targetblock,
+							 OffsetNumberNext(offset));
+
+			/* Reuse itup to get pointed-to heap location of second item */
+			itemid = PageGetItemId(state->target, OffsetNumberNext(offset));
+			itup = (IndexTuple) PageGetItem(state->target, itemid);
+			nhtid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("page order invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Lower index tid=%s (points to %s tid=%s) "
+										"higher index tid=%s (points to %s tid=%s) "
+										"page lsn=%X/%X.",
+										itid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										htid,
+										nitid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										nhtid,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+		}
+		/*
+		 *   ********************
+		 *   * Last item check  *
+		 *   ********************
+		 *
+		 * Check last item against next/right page's first data item's when
+		 * last item on page is reached.
+		 *
+		 * The general idea here is that checking the ordering of items on the
+		 * page should still perform some check on the last item on the page,
+		 * if at all possible.  In other words, this is roughly the same
+		 * process as the page order check that has already been performed for
+		 * every other "real" item on target page by now; we just need to reach
+		 * into the next page to get a scankey to compare against lower bound
+		 * of max.
+		 */
+		else if (offset == max)
+		{
+			ScanKey		rightkey;
+
+			/* Get item in next/right page */
+			rightkey = bt_right_page_check_scankey(state);
+
+			if (rightkey &&
+				!invariant_key_greater_than_equal_offset(state, rightkey, max))
+			{
+				/*
+				 * As discussed in bt_right_page_check_scankey(),
+				 * non-ExclusiveLock case might have had target page deleted,
+				 * in which case no error is raised
+				 */
+				if (!state->exclusivelock)
+				{
+					/* Get fresh copy of target page */
+					state->target = palloc_btree_page(state, state->targetblock);
+					topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+					/*
+					 * Because of RecentGlobalXmin interlock against VACUUM's
+					 * recycling of blocks, we can safely assume that this is
+					 * substantively the same target page as before.
+					 *
+					 * Just return, because all !exclusivelock checks already
+					 * performed against target.
+					 */
+					if (P_IGNORE(topaque))
+						return;
+				}
+				ereport(CORRUPTION,
+						(errcode(ERRCODE_INDEX_CORRUPTED),
+						 errmsg("cross page order invariant violated for index \"%s\"",
+								RelationGetRelationName(state->rel)),
+						 errdetail_internal("Last item on page tid=(%u,%u) "
+											"right page block=%u "
+											"page lsn=%X/%X.",
+											state->targetblock, offset,
+											topaque->btpo_next,
+											(uint32) (state->targetlsn >> 32),
+											(uint32) state->targetlsn)));
+			}
+		}
+
+		/*
+		 *   ********************
+		 *   * Downlink check   *
+		 *   ********************
+		 *
+		 * Additional check of child items against target page (their parent),
+		 * iff this is internal page and caller holds ExclusiveLock on index
+		 * relation.  This involves a pass over each child page at the end of
+		 * each iteration (excluding the minus infinity iteration which
+		 * internal pages always have, which is immediately skipped).
+		 */
+		if (!P_ISLEAF(topaque) && state->exclusivelock)
+		{
+			BlockNumber childblock = ItemPointerGetBlockNumber(&(itup->t_tid));
+
+			bt_downlink_check(state, childblock, skey);
+		}
+	}
+}
+
+/*
+ * bt_right_page_check_scankey()
+ *
+ * Return a scankey for an item on page to right of current target (or the
+ * first non-ignorable page), sufficient to check ordering invariant on last
+ * item in current target page.  Returned scankey relies on local memory
+ * allocated for the child page, which caller cannot pfree().  Caller's memory
+ * context should be reset between calls here.
+ *
+ * This is the first data item, and so all adjacent items are checked against
+ * their immediate sibling item (which may be on the same page, or may be the
+ * cases this function helps with: comparisons of items across sibling pages,
+ * or even comparisons of items across "cousin" pages).
+ *
+ * If no first data item is available on right page, just return NULL.  Note
+ * that !exclusivelock callers must reverify that target page has not been
+ * concurrently deleted.  There is a complex explanation for why this is below.
+ */
+static ScanKey
+bt_right_page_check_scankey(BtreeCheckState *state)
+{
+	BTPageOpaque	opaque;
+	ItemId			rightitem;
+	BlockNumber		targetnext;
+	Page			rightpage;
+	OffsetNumber	nline;
+
+	/* Determine target's next block number */
+	opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+	/* If target is already rightmost, no right sibling; nothing to do here */
+	if (P_RIGHTMOST(opaque))
+		return NULL;
+
+	/*
+	 * General notes on concurrent page splits and page deletion:
+	 *
+	 * Concurrent page splits are not a problem for ordinary index scans, since
+	 * the key space always moves in a way that lets index scans not miss
+	 * things:  they might have to move right, but they never have to move left
+	 * (leaving aside index scans backwards, a special case).  A concurrent
+	 * page split could occur here, but just as with index scans we're
+	 * following the stale right link, which will reliably get us further along
+	 * in the key space, which is all we really need to get an item further
+	 * along in key space to check invariant in target page.
+	 *
+	 * A deleted page won't actually be recycled by VACUUM early enough for us
+	 * to fail to be able follow its right link (or left link, or downlink),
+	 * because it doesn't do so until it knows that no possible index scan
+	 * could land on the page with the expectation of at least being able to
+	 * move right and eventually find a non-ignorable page.  (see page
+	 * recycling/RecentGlobalXmin notes in nbtree README.)
+	 *
+	 * It's okay if we follow a rightlink and find a half-dead or dead
+	 * (ignorable) page.  Either way, there must be a sane further right link
+	 * to follow for these ignorable pages, because page deletion refuses to
+	 * merge the key space between adjacent pages that do not share a common
+	 * parent (that is, merging of the key space has to be among true sibling
+	 * pages, never cousin pages).  We should succeed in finding a page to the
+	 * right that isn't ignorable before too long.
+	 */
+	targetnext = opaque->btpo_next;
+	for (;;)
+	{
+		CHECK_FOR_INTERRUPTS();
+
+		rightpage = palloc_btree_page(state, targetnext);
+		opaque = (BTPageOpaque) PageGetSpecialPointer(rightpage);
+
+		if (!P_IGNORE(opaque) || P_RIGHTMOST(opaque))
+			break;
+
+		/* We landed on a deleted page, so step right to find a live page */
+		targetnext = opaque->btpo_next;
+		ereport(CONCERN,
+				(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+				 errmsg("level %u leftmost page of index \"%s\" was found deleted or half dead",
+						opaque->btpo.level, RelationGetRelationName(state->rel)),
+				 errdetail_internal("Deleted page found when building scankey from right sibling.")));
+
+		/* Be slightly more pro-active in freeing this memory, just in case */
+		pfree(rightpage);
+	}
+
+	/*
+	 * No ExclusiveLock held case -- why it's safe to proceed.
+	 *
+	 * Problem:
+	 *
+	 * We must avoid false positive reports of corruption when caller treats
+	 * item returned here as an upper bound on target's last item.  In general,
+	 * false positives are disallowed.  Ensuring they don't happen in
+	 * !exclusivelock case is subtle.
+	 *
+	 * A concurrent page deletion by VACUUM of the target page can result in
+	 * the insertion of items on to this right sibling page that would
+	 * previously have been inserted on our target page.  There might have been
+	 * insertions that followed target's downlink after it was made to point to
+	 * right sibling instead of target by page deletion's first phase.  The
+	 * inserters insert items that would belong on target page.  This race is
+	 * very tight, but it's possible.  This is our only problem.
+	 *
+	 * Non-problems:
+	 *
+	 * We are not hindered by a concurrent page split of the target; we'll
+	 * never land on the second half of the page anyway.  A concurrent split of
+	 * the right page will also not matter, because the first data item remains
+	 * the same within the left half, which we'll reliably land on.  If we had
+	 * to skip over ignorable/deleted pages, it cannot matter because their key
+	 * space has already been atomically merged with the first non-ignorable
+	 * page we eventually find (doesn't matter whether the page we eventually
+	 * find is a true sibling or a cousin of target, which we go into below).
+	 *
+	 * Solution:
+	 *
+	 * Caller knows that it should reverify that target is not ignorable
+	 * (half-dead or deleted) when cross-page sibling item comparison appears
+	 * to indicate corruption (invariant fails).  This detects the single race
+	 * condition that exists for caller.  This is correct because the continued
+	 * existence of target block as non-ignorable (not half-dead or deleted)
+	 * implies that target page was not merged into from the right by deletion;
+	 * the key space at or after target never moved left.  Target's parent
+	 * either has the same downlink to target as before, or a <= downlink due
+	 * to deletion at the left of target.  Target either has the same high key
+	 * as before, or a high key <= before when there is a page split. (The
+	 * rightmost concurrently-split-from-target-page page will still have the
+	 * same high key as target was originally found to have, which for our
+	 * purposes is equivalent to target's high key itself never changing, since
+	 * we reliably skip over concurrently-split-from-target-page pages.)
+	 *
+	 * In simpler terms, we allow that the key space of the target may expand
+	 * left (the key space can move left on the left side of target only), but
+	 * the target key space cannot expand right and get ahead of us without our
+	 * detecting it.  The key space of the target cannot shrink, unless it
+	 * shrinks to zero due to the deletion of the original page, our canary
+	 * condition.  (To be very precise, we're a bit stricter than that because
+	 * it might just have been that the target page split and only the original
+	 * target page was deleted.  We can be more strict, just not more lax.)
+	 *
+	 * Top level tree walk caller moves on to next page (makes it the new
+	 * target) following recovery from this race.  (cf.  The rationale for
+	 * child/downlink verification needing an ExclusiveLock within
+	 * bt_downlink_check(), where page deletion is also the main source of
+	 * trouble.)
+	 *
+	 * Note that it doesn't matter if right sibling page here is actually a
+	 * cousin page, because in order for the key space to be readjusted in a
+	 * way that causes us issues in next level up (guiding problematic
+	 * concurrent insertions to the cousin from the grandparent rather than to
+	 * the sibling from the parent), there'd have to be page deletion of
+	 * target's parent page (affecting target's parent's downlink in target's
+	 * grandparent page).  Internal page deletion only occurs when there are no
+	 * child pages (they were all fully deleted), and caller is checking that
+	 * the target's parent has at least one non-deleted (so non-ignorable)
+	 * child: the target page.  (Note that the first phase of deletion
+	 * atomically marks the page to be deleted half-dead/ignorable at the same
+	 * time downlink in its parent is removed, so we'll definitely be able to
+	 * detect that this might have happened just from the target page.)
+	 *
+	 * This trick is inspired by the method backward scans use for dealing with
+	 * concurrent page splits; concurrent page deletion is a problem that
+	 * similarly receives special consideration sometimes (it's possible that
+	 * the backwards scan will re-read its "original" block after failing to
+	 * find a right-link to it, having already moved in the opposite direction
+	 * (right/"forwards") a few times to try to locate one).  Just like us,
+	 * that happens only to determine if there was a concurrent page deletion
+	 * of a reference page, and just like us if there was a page deletion of
+	 * that reference page it means we can move on from caring about the
+	 * reference page.  See the nbtree README for a full description of how
+	 * that works.
+	 */
+	nline = PageGetMaxOffsetNumber(rightpage);
+
+	/*
+	 * Get first data item.
+	 *
+	 * Importantly, this allows the verification of page order across target
+	 * and rightmost page when rightmost page is the target's right sibling.
+	 * Moreover, the only way logical inconsistencies can really be missed
+	 * across a given level is if the transitive law is broken by an opclass,
+	 * because contiguous pairs are always compared, even across page
+	 * boundaries. (Assuming we have a "stable snapshot" of structure, as in
+	 * exclusivelock case.  Otherwise, strictly speaking, we might just miss
+	 * corruption that would have been caught in exclusivelock case.)
+	 */
+	if (P_ISLEAF(opaque) && nline >= P_FIRSTDATAKEY(opaque))
+	{
+		/*
+		 * For leaf page, return first data item (if any), which cannot be a
+		 * "minus infinity" item
+		 */
+		rightitem = PageGetItemId(rightpage, P_FIRSTDATAKEY(opaque));
+	}
+	else if (!P_ISLEAF(opaque) &&
+			 nline >= OffsetNumberNext(P_FIRSTDATAKEY(opaque)))
+	{
+		/*
+		 * Return first item after the internal page's undefined "minus
+		 * infinity" item.  Also skip the high key when page isn't rightmost on
+		 * level.
+		 */
+		rightitem = PageGetItemId(rightpage,
+								  OffsetNumberNext(P_FIRSTDATAKEY(opaque)));
+	}
+	else
+	{
+		/*
+		 * No first item.  Page is probably empty leaf page, but it's also
+		 * possible that it's an internal page with only a minus infinity item,
+		 * because caller moves left to right.
+		 */
+		ereport(CONCERN,
+				(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+				 errmsg("%s block %u of index \"%s\" has no first data item",
+						P_ISLEAF(opaque) ? "leaf":"internal", targetnext,
+						RelationGetRelationName(state->rel))));
+		return NULL;
+	}
+
+	/*
+	 * Return first real item scankey.  Note that this relies on right page
+	 * memory remaining allocated.
+	 */
+	return _bt_mkscankey(state->rel,
+						 (IndexTuple) PageGetItem(rightpage, rightitem));
+}
+
+/*
+ * bt_downlink_check()
+ *
+ * Checks one of target's downlink against its child page.
+ *
+ * Conceptually, the target page continues to be what is checked here.  The
+ * target block is still blamed in the event of finding an invariant violation.
+ * The downlink insertion into the target is probably where any problem raised
+ * here arises, and there is no such thing as a parent link, so doing the
+ * verification this way around is much more practical.
+ */
+static void
+bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
+				  ScanKey targetkey)
+{
+	OffsetNumber	offset;
+	OffsetNumber	maxoffset;
+	Page			child;
+	BTPageOpaque	copaque;
+
+	/*
+	 * Caller must have ExclusiveLock on target relation, because of
+	 * considerations around page deletion by VACUUM.
+	 *
+	 * N.B.: In general, page deletion deletes the right sibling's downlink,
+	 * not the downlink of the page being deleted; the deleted page's downlink
+	 * is reused for its sibling.  The key space is thereby consolidated
+	 * between the deleted page and its right sibling.  (We cannot delete a
+	 * parent page's rightmost page unless it is the last child page, and we
+	 * intend to delete the parent itself.)
+	 *
+	 * If this verification happened without an ExclusiveLock, the following
+	 * race condition could cause false positives (which are generally
+	 * disallowed):
+	 *
+	 * Not having an ExclusiveLock would allow concurrent page deletion,
+	 * including deletion of the left sibling of the child page that is
+	 * examined here.  If such a page deletion occurred, and was then closely
+	 * followed by an insertion into the newly expanded key space of the child,
+	 * a false positive may result: our stale parent/target downlink would
+	 * legitimately not be a lower bound on all items in the page anymore,
+	 * because the key space was concurrently expanded "left" (insertion
+	 * followed the "new" downlink for the child, not our now-stale downlink,
+	 * which was concurrently physically removed in target/parent as part of
+	 * deletion's first phase).
+	 *
+	 * Note that while the cross-page-same-level check uses a trick that allows
+	 * it to perform verification for !exclusivelock callers, an analogous
+	 * trick seems very difficult here.  The trick that that other check uses
+	 * is, in essence, to lock down race conditions to those that occur due to
+	 * concurrent page deletion of the target; that's a race that can be
+	 * reliably detected before actually reporting corruption.  On the other
+	 * hand, we'd need to lock down race conditions involving deletion of
+	 * child's left page, at least for long enough to read the child page into
+	 * memory.  Any more granular locking schemes all seem to involve multiple
+	 * concurrently held buffer locks.  That's unacceptable for amcheck on
+	 * general principle, though; amcheck functions never hold more than one
+	 * buffer lock at a time.
+	 */
+	Assert(state->exclusivelock);
+
+	/*
+	 * Verify child page has the downlink key from target page (its parent) as
+	 * a lower bound.
+	 *
+	 * We prefer to check all items, rather than checking just the first and
+	 * trusting that the operator class obeys the transitive law (which implies
+	 * that all subsequent items also respected the downlink-as-lower-bound
+	 * invariant if they pass the page order check when the child later becomes
+	 * our target for verification).
+	 */
+	child = palloc_btree_page(state, childblock);
+	copaque = (BTPageOpaque) PageGetSpecialPointer(child);
+	maxoffset = PageGetMaxOffsetNumber(child);
+
+	for (offset = P_FIRSTDATAKEY(copaque);
+		 offset <= maxoffset;
+		 offset = OffsetNumberNext(offset))
+	{
+		/*
+		 * Skip comparison of target page key against "minus infinity" item, if
+		 * any.  Checking it would indicate that its not an upper bound, but
+		 * that's only because of the hard-coding within _bt_compare().
+		 */
+		if (OFFSET_IS_MINUS_INFINITY(copaque, offset))
+			continue;
+
+		if (!invariant_key_less_than_equal_nontarget_offset(state, child,
+															targetkey, offset))
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("down-link lower bound invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Parent block=%u child index tid=(%u,%u) "
+										"parent page lsn=%X/%X.",
+										state->targetblock, childblock, offset,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+	}
+
+	pfree(child);
+}
+
+/*
+ * invariant_key_less_than_equal_offset()
+ *
+ * Does the invariant hold that the key is less than or equal to a given upper
+ * bound offset item?
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_less_than_equal_offset(BtreeCheckState *state, ScanKey key,
+									 OffsetNumber upperbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, state->target, upperbound);
+
+	return cmp <= 0;
+}
+
+/*
+ * invariant_key_less_than_equal_offset()
+ *
+ * Does the invariant hold that the key is greater than or equal to a given
+ * lower bound offset item?
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_greater_than_equal_offset(BtreeCheckState *state, ScanKey key,
+										OffsetNumber lowerbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, state->target, lowerbound);
+
+	return cmp >= 0;
+}
+
+/*
+ * invariant_key_less_than_equal_nontarget_offset()
+ *
+ * Does the invariant hold that the key is less than or equal to a given upper
+ * bound offset item, with the offset relating to a caller-supplied page that
+ * is not the current target page? Caller's non-target page is typically a
+ * child page of the target, checked as part of checking a property of the
+ * target page (i.e. the key comes from the target).
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_less_than_equal_nontarget_offset(BtreeCheckState *state,
+											   Page nontarget, ScanKey key,
+											   OffsetNumber upperbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, nontarget, upperbound);
+
+	return cmp <= 0;
+}
+
+/*
+ * palloc_btree_page()
+ *
+ * Given a block number of a B-Tree page, return page in palloc()'d memory.
+ * While at it, perform some basic checks of the page.
+ *
+ * There is never an attempt to get a consistent view of multiple pages using
+ * multiple concurrent buffer locks; in general, we prefer to have only one pin
+ * and buffer lock at a time, which is often all that the nbtree code requires.
+ *
+ * Operating on a copy of the page is useful because it prevents control
+ * getting stuck in an uninterruptible state when an underlying operator class
+ * misbehaves.
+ */
+static Page
+palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum)
+{
+	Buffer			buffer;
+	Page			page;
+	BTPageOpaque	opaque;
+
+	page = palloc(BLCKSZ);
+
+	/*
+	 * We copy the page into local storage to avoid holding pin on the buffer
+	 * longer than we must.
+	 */
+	buffer = ReadBufferExtended(state->rel, MAIN_FORKNUM, blocknum, RBM_NORMAL,
+								state->checkstrategy);
+	LockBuffer(buffer, BT_READ);
+
+	/*
+	 * Perform the same basic sanity checking that nbtree itself performs for
+	 * every page:
+	 */
+	_bt_checkpage(state-> rel, buffer);
+
+	/* Only use copy of page in palloc()'d memory */
+	memcpy(page, BufferGetPage(buffer), BLCKSZ);
+	UnlockReleaseBuffer(buffer);
+
+	opaque = (BTPageOpaque) PageGetSpecialPointer(page);
+
+	if (opaque->btpo_flags & BTP_META && blocknum != BTREE_METAPAGE)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid meta page found at block %u in index \"%s\"",
+						blocknum, RelationGetRelationName(state->rel))));
+
+	/* Check page from block that ought to be meta page */
+	if (blocknum == BTREE_METAPAGE)
+	{
+		BTMetaPageData *metad = BTPageGetMeta(page);
+
+		if (!(opaque->btpo_flags & BTP_META) ||
+			metad->btm_magic != BTREE_MAGIC)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("index \"%s\" meta page is corrupt",
+							RelationGetRelationName(state->rel))));
+
+		if (metad->btm_version != BTREE_VERSION)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("version mismatch in index \"%s\": file version %d, code version %d",
+							RelationGetRelationName(state->rel),
+							metad->btm_version, BTREE_VERSION)));
+	}
+
+	/*
+	 * Deleted pages have no sane "level" field, so can only check non-deleted
+	 * page level
+	 */
+	if (P_ISLEAF(opaque) && !P_ISDELETED(opaque) && opaque->btpo.level != 0)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid leaf page level %u for block %u in index \"%s\"",
+						opaque->btpo.level, blocknum, RelationGetRelationName(state->rel))));
+
+	if (blocknum != BTREE_METAPAGE && !P_ISLEAF(opaque) &&
+		!P_ISDELETED(opaque) && opaque->btpo.level == 0)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid internal page level 0 for block %u in index \"%s\"",
+						opaque->btpo.level, RelationGetRelationName(state->rel))));
+
+	if (!P_ISLEAF(opaque) && P_HAS_GARBAGE(opaque))
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("internal page block %u in index \"%s\" has garbage items",
+						blocknum, RelationGetRelationName(state->rel))));
+
+	return page;
+}
diff --git a/contrib/amcheck/amcheck.control b/contrib/amcheck/amcheck.control
new file mode 100644
index 0000000..180f150
--- /dev/null
+++ b/contrib/amcheck/amcheck.control
@@ -0,0 +1,5 @@
+# amcheck extension
+comment = 'verify access method invariants'
+default_version = '1.0'
+module_pathname = '$libdir/amcheck'
+relocatable = true
diff --git a/contrib/amcheck/expected/extern_sort_bytea.out b/contrib/amcheck/expected/extern_sort_bytea.out
new file mode 100644
index 0000000..54a8f3b
--- /dev/null
+++ b/contrib/amcheck/expected/extern_sort_bytea.out
@@ -0,0 +1,44 @@
+CREATE TEMP TABLE bytea_test (i bytea);
+-- Seed random number generator to make outcome deterministic.
+SELECT setseed(0.5);
+ setseed 
+---------
+ 
+(1 row)
+
+INSERT INTO bytea_test SELECT decode(repeat(md5(random()::text), (random() * 100)::int4), 'hex')
+      FROM generate_series(0, 100000);
+SET maintenance_work_mem = '1MB';
+CREATE INDEX idx_bytea ON bytea_test(i);
+SELECT bt_index_parent_check('idx_bytea');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+SET maintenance_work_mem = '3MB';
+REINDEX INDEX idx_bytea;
+SELECT bt_index_parent_check('idx_bytea');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+SET maintenance_work_mem = '5MB';
+REINDEX INDEX idx_bytea;
+SELECT bt_index_parent_check('idx_bytea');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+SET maintenance_work_mem = '20MB';
+REINDEX INDEX idx_bytea;
+SELECT bt_index_parent_check('idx_bytea');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+-- drop the temporary table
+DROP TABLE bytea_test;
diff --git a/contrib/amcheck/expected/extern_sort_collations.out b/contrib/amcheck/expected/extern_sort_collations.out
new file mode 100644
index 0000000..63ee4d0
--- /dev/null
+++ b/contrib/amcheck/expected/extern_sort_collations.out
@@ -0,0 +1,42 @@
+-- Perform tests of external sorting collated text.  Only test at most 10
+-- available collations, to make sure that the tests complete in a reasonable
+-- amount of time.
+DO $x$
+DECLARE
+  r record;
+  index_build_mem int4;
+BEGIN
+	FOR r IN SELECT oid, collname FROM pg_collation ORDER BY oid LIMIT 10 LOOP
+
+  EXECUTE format($y$CREATE TEMP TABLE text_test_collation (i text COLLATE "%s");$y$, r.collname);
+
+  -- Seed random number generator so that each collation that happens to be
+  -- available on the system consistently sorts the same strings, using the
+  -- same maintenance_work_mem setting.  In theory, varying these makes the
+  -- tests more likely to catch problems.
+  PERFORM setseed(get_byte(decode(md5(r.collname), 'hex'), 5) / 256.0);
+  -- Don't actually output collation names
+  -- RAISE NOTICE '%', r.collname;
+
+  -- Make sure MD5 strings contain some space characters, and a doublequote, so
+  -- multiple "weight levels" are represented.  Typically, OS strcoll()
+  -- implementations follow the conventions of the standard Unicode collation
+  -- algorithm, and primarily weight alphabetical ordering when comparing
+  -- strings.
+  INSERT INTO text_test_collation
+      SELECT replace(replace(md5(random()::text), '4', ' '), '9', '"')
+      FROM generate_series(0, 100000);
+
+  -- Set maintenance_work_mem  to at least mimimum value, 1MB, and at most 10MB
+  -- to test external sorting:
+  index_build_mem := (SELECT greatest((random() * 1024 * 10)::int4, 1024));
+  -- Don't actually output pseudo-random maintenance_work_mem:
+  -- RAISE NOTICE '%', index_build_mem;
+  EXECUTE 'SET maintenance_work_mem = ' || index_build_mem;
+  CREATE INDEX idx_text ON text_test_collation(i);
+  PERFORM bt_index_parent_check('idx_text');
+  -- drop the temporary table
+  DROP TABLE text_test_collation;
+	END LOOP;
+END;
+$x$;
diff --git a/contrib/amcheck/expected/extern_sort_numeric.out b/contrib/amcheck/expected/extern_sort_numeric.out
new file mode 100644
index 0000000..253f9b3
--- /dev/null
+++ b/contrib/amcheck/expected/extern_sort_numeric.out
@@ -0,0 +1,44 @@
+CREATE TEMP TABLE numeric_test (i numeric);
+-- Seed random number generator to make outcome deterministic.
+SELECT setseed(0.5);
+ setseed 
+---------
+ 
+(1 row)
+
+INSERT INTO numeric_test SELECT random() * 100000000 FROM generate_series(0, 5000000);
+-- special cases
+INSERT INTO numeric_test SELECT exp(0.0);
+INSERT INTO numeric_test SELECT exp(1.0);
+INSERT INTO numeric_test SELECT exp(1.0::numeric(71,70));
+INSERT INTO numeric_test SELECT 0.0 ^ 0.0;
+INSERT INTO numeric_test SELECT (-12.34) ^ 0.0;
+INSERT INTO numeric_test SELECT 12.34 ^ 0.0;
+INSERT INTO numeric_test SELECT 0.0 ^ 12.34;
+SET maintenance_work_mem = '1MB';
+CREATE INDEX idx_numeric ON numeric_test(i);
+SELECT bt_index_parent_check('idx_numeric');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+SET maintenance_work_mem = '5MB';
+REINDEX INDEX idx_numeric;
+SELECT bt_index_parent_check('idx_numeric');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+-- Only this final REINDEX requires just one merge pass:
+SET maintenance_work_mem = '20MB';
+REINDEX INDEX idx_numeric;
+SELECT bt_index_parent_check('idx_numeric');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+-- drop the temporary table
+DROP TABLE numeric_test;
diff --git a/contrib/amcheck/expected/install_amcheck.out b/contrib/amcheck/expected/install_amcheck.out
new file mode 100644
index 0000000..5b3e6d5
--- /dev/null
+++ b/contrib/amcheck/expected/install_amcheck.out
@@ -0,0 +1 @@
+CREATE EXTENSION amcheck;
diff --git a/contrib/amcheck/sql/extern_sort_bytea.sql b/contrib/amcheck/sql/extern_sort_bytea.sql
new file mode 100644
index 0000000..a302c55e
--- /dev/null
+++ b/contrib/amcheck/sql/extern_sort_bytea.sql
@@ -0,0 +1,23 @@
+CREATE TEMP TABLE bytea_test (i bytea);
+
+-- Seed random number generator to make outcome deterministic.
+SELECT setseed(0.5);
+
+INSERT INTO bytea_test SELECT decode(repeat(md5(random()::text), (random() * 100)::int4), 'hex')
+      FROM generate_series(0, 100000);
+
+SET maintenance_work_mem = '1MB';
+CREATE INDEX idx_bytea ON bytea_test(i);
+SELECT bt_index_parent_check('idx_bytea');
+SET maintenance_work_mem = '3MB';
+REINDEX INDEX idx_bytea;
+SELECT bt_index_parent_check('idx_bytea');
+SET maintenance_work_mem = '5MB';
+REINDEX INDEX idx_bytea;
+SELECT bt_index_parent_check('idx_bytea');
+SET maintenance_work_mem = '20MB';
+REINDEX INDEX idx_bytea;
+SELECT bt_index_parent_check('idx_bytea');
+
+-- drop the temporary table
+DROP TABLE bytea_test;
diff --git a/contrib/amcheck/sql/extern_sort_collations.sql b/contrib/amcheck/sql/extern_sort_collations.sql
new file mode 100644
index 0000000..63ee4d0
--- /dev/null
+++ b/contrib/amcheck/sql/extern_sort_collations.sql
@@ -0,0 +1,42 @@
+-- Perform tests of external sorting collated text.  Only test at most 10
+-- available collations, to make sure that the tests complete in a reasonable
+-- amount of time.
+DO $x$
+DECLARE
+  r record;
+  index_build_mem int4;
+BEGIN
+	FOR r IN SELECT oid, collname FROM pg_collation ORDER BY oid LIMIT 10 LOOP
+
+  EXECUTE format($y$CREATE TEMP TABLE text_test_collation (i text COLLATE "%s");$y$, r.collname);
+
+  -- Seed random number generator so that each collation that happens to be
+  -- available on the system consistently sorts the same strings, using the
+  -- same maintenance_work_mem setting.  In theory, varying these makes the
+  -- tests more likely to catch problems.
+  PERFORM setseed(get_byte(decode(md5(r.collname), 'hex'), 5) / 256.0);
+  -- Don't actually output collation names
+  -- RAISE NOTICE '%', r.collname;
+
+  -- Make sure MD5 strings contain some space characters, and a doublequote, so
+  -- multiple "weight levels" are represented.  Typically, OS strcoll()
+  -- implementations follow the conventions of the standard Unicode collation
+  -- algorithm, and primarily weight alphabetical ordering when comparing
+  -- strings.
+  INSERT INTO text_test_collation
+      SELECT replace(replace(md5(random()::text), '4', ' '), '9', '"')
+      FROM generate_series(0, 100000);
+
+  -- Set maintenance_work_mem  to at least mimimum value, 1MB, and at most 10MB
+  -- to test external sorting:
+  index_build_mem := (SELECT greatest((random() * 1024 * 10)::int4, 1024));
+  -- Don't actually output pseudo-random maintenance_work_mem:
+  -- RAISE NOTICE '%', index_build_mem;
+  EXECUTE 'SET maintenance_work_mem = ' || index_build_mem;
+  CREATE INDEX idx_text ON text_test_collation(i);
+  PERFORM bt_index_parent_check('idx_text');
+  -- drop the temporary table
+  DROP TABLE text_test_collation;
+	END LOOP;
+END;
+$x$;
diff --git a/contrib/amcheck/sql/extern_sort_numeric.sql b/contrib/amcheck/sql/extern_sort_numeric.sql
new file mode 100644
index 0000000..018b87a
--- /dev/null
+++ b/contrib/amcheck/sql/extern_sort_numeric.sql
@@ -0,0 +1,29 @@
+CREATE TEMP TABLE numeric_test (i numeric);
+
+-- Seed random number generator to make outcome deterministic.
+SELECT setseed(0.5);
+
+INSERT INTO numeric_test SELECT random() * 100000000 FROM generate_series(0, 5000000);
+
+-- special cases
+INSERT INTO numeric_test SELECT exp(0.0);
+INSERT INTO numeric_test SELECT exp(1.0);
+INSERT INTO numeric_test SELECT exp(1.0::numeric(71,70));
+INSERT INTO numeric_test SELECT 0.0 ^ 0.0;
+INSERT INTO numeric_test SELECT (-12.34) ^ 0.0;
+INSERT INTO numeric_test SELECT 12.34 ^ 0.0;
+INSERT INTO numeric_test SELECT 0.0 ^ 12.34;
+
+SET maintenance_work_mem = '1MB';
+CREATE INDEX idx_numeric ON numeric_test(i);
+SELECT bt_index_parent_check('idx_numeric');
+SET maintenance_work_mem = '5MB';
+REINDEX INDEX idx_numeric;
+SELECT bt_index_parent_check('idx_numeric');
+-- Only this final REINDEX requires just one merge pass:
+SET maintenance_work_mem = '20MB';
+REINDEX INDEX idx_numeric;
+SELECT bt_index_parent_check('idx_numeric');
+
+-- drop the temporary table
+DROP TABLE numeric_test;
diff --git a/contrib/amcheck/sql/install_amcheck.sql b/contrib/amcheck/sql/install_amcheck.sql
new file mode 100644
index 0000000..5b3e6d5
--- /dev/null
+++ b/contrib/amcheck/sql/install_amcheck.sql
@@ -0,0 +1 @@
+CREATE EXTENSION amcheck;
diff --git a/doc/src/sgml/amcheck.sgml b/doc/src/sgml/amcheck.sgml
new file mode 100644
index 0000000..524f88d
--- /dev/null
+++ b/doc/src/sgml/amcheck.sgml
@@ -0,0 +1,247 @@
+<!-- doc/src/sgml/amcheck.sgml -->
+
+<sect1 id="amcheck" xreflabel="amcheck">
+ <title>amcheck</title>
+
+ <indexterm zone="amcheck">
+  <primary>amcheck</primary>
+ </indexterm>
+
+ <para>
+  The <filename>amcheck</> module provides functions that allow you to
+  verify the logical consistency of the structure of indexes.  If the
+  structure appears to be valid, no error is raised.
+ </para>
+
+ <para>
+  The functions verify various <emphasis>invariants</> in the
+  structure of the representation of particular indexes.  The
+  correctness of the access method functions behind index scans and
+  other important operations is predicated on these invariants always
+  holding.  For example, certain functions verify, among other things,
+  that all B-Tree pages have items in <quote>logical</> order; if that
+  particular invariant somehow fails to hold, we can expect binary
+  searches on any affected page to produce wrong answers.  As a
+  consequence of that, index scans may subtly produce wrong answers.
+ </para>
+
+ <para>
+  Verification is performed using the same procedures as those used by
+  index scans themselves, which may be user-defined operator class
+  code.  For example, B-Tree index verification relies on comparisons
+  made with one or more B-Tree support function 1 routines, much like
+  B-Tree index scans rely on the routines to guide the scan to a point
+  in the underlying table;  see <xref linkend="xindex-support"> for
+  details of operator class support functions.
+ </para>
+
+ <para>
+  <filename>amcheck</> functions may be used only by superusers.
+ </para>
+
+ <sect2>
+  <title>Functions</title>
+
+  <variablelist>
+   <varlistentry>
+    <term>
+     <function>bt_index_check(index regclass) returns void</function>
+     <indexterm>
+      <primary>bt_index_check</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>bt_index_check</function> tests that its target, a
+      B-Tree index, respects a variety of invariants.  Example usage:
+<screen>
+test=# SELECT bt_index_check(c.oid), c.relname, c.relpages
+FROM pg_index i
+JOIN pg_opclass op ON i.indclass[0] = op.oid
+JOIN pg_am am ON op.opcmethod = am.oid
+JOIN pg_class c ON i.indexrelid = c.oid
+JOIN pg_namespace n ON c.relnamespace = n.oid
+WHERE am.amname = 'btree' AND n.nspname = 'pg_catalog'
+-- Don't check pg_class (bt_index_parent_check() requires this):
+AND c.relname NOT LIKE 'pg_class%'
+-- Function may throw an error when this is omitted:
+AND i.indisready AND i.indisvalid
+ORDER BY c.relpages DESC LIMIT 10;
+ bt_index_check |             relname             | relpages 
+----------------+---------------------------------+----------
+                | pg_depend_reference_index       |       43
+                | pg_depend_depender_index        |       40
+                | pg_proc_proname_args_nsp_index  |       31
+                | pg_description_o_c_o_index      |       21
+                | pg_attribute_relid_attnam_index |       14
+                | pg_proc_oid_index               |       10
+                | pg_attribute_relid_attnum_index |        9
+                | pg_amproc_fam_proc_index        |        5
+                | pg_amop_opr_fam_index           |        5
+                | pg_amop_fam_strat_index         |        5
+(10 rows)
+</screen>
+      This example shows a session that performs verification of every
+      catalog index in the database <quote>test</> (except those
+      associated with the <structname>pg_class</structname> catalog).
+      Details of just the 10 largest indexes verified are displayed.
+      Since no error is raised, all indexes tested appear to be
+      logically consistent.  Naturally, this query could easily be
+      changed to call <function>bt_index_check</function> for every
+      index in the database where verification is supported.
+     </para>
+     <para>
+      An <literal>AccessShareLock</> is acquired on the target index
+      by <function>bt_index_check</function>.  This lock mode is the
+      same lock mode acquired on relations by simple
+      <literal>SELECT</> statements.
+      <function>bt_index_check</function> does not verify invariants
+      that span child/parent relationships, nor does it verify that
+      the target index is consistent with its heap relation.  When a
+      routine, lightweight test for corruption is required in a live
+      production environment, using
+      <function>bt_index_check</function> often provides the best
+      trade-off between thoroughness of verification and limiting the
+      impact on application performance and availability.
+     </para>
+    </listitem>
+   </varlistentry>
+
+   <varlistentry>
+    <term>
+     <function>bt_index_parent_check(index regclass) returns void</function>
+     <indexterm>
+      <primary>bt_index_parent_check</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>bt_index_parent_check</function> tests that its
+      target, a B-Tree index, respects a variety of invariants.  The
+      checks performed by <function>bt_index_parent_check</function>
+      are a superset of the checks performed by
+      <function>bt_index_check</function>.
+      <function>bt_index_parent_check</function> can be thought of as
+      a more thorough variant of <function>bt_index_check</function>:
+      unlike <function>bt_index_check</function>,
+      <function>bt_index_parent_check</function> also checks
+      invariants that span parent/child relationships.  However, it
+      does not verify that the target index is consistent with its
+      heap relation.  <function>bt_index_parent_check</function>
+      follows the general convention of raising an error if it finds a
+      logical inconsistency or other problem.
+     </para>
+     <para>
+      An <literal>ExclusiveLock</> is required on the target index by
+      <function>bt_index_parent_check</function> (a
+      <literal>ShareLock</> is also acquired on the heap relation).
+      These locks prevent concurrent data modification from
+      <command>INSERT</>, <command>UPDATE</>, and <command>DELETE</>
+      commands.  The locks also prevent the underlying relation from
+      being concurrently processed by <command>VACUUM</> and certain
+      other utility commands.  Note that the function holds locks for
+      as short a duration as possible, so there is no advantage to
+      verifying each index individually in a series of transactions.
+     </para>
+     <para>
+      <function>bt_index_parent_check</function>'s additional
+      verification is more likely to detect various pathological
+      cases.  These cases may involve an incorrectly implemented
+      B-Tree operator class used by the index that is checked, or,
+      hypothetically, undiscovered bugs in the underlying B-Tree index
+      access method code.  Note that
+      <function>bt_index_parent_check</function> will raise an error
+      when called while Hot Standby mode is enabled, unlike
+      <function>bt_index_check</function>.
+     </para>
+    </listitem>
+   </varlistentry>
+  </variablelist>
+ </sect2>
+
+ <sect2>
+  <title>Using <filename>amcheck</> effectively</title>
+
+ <para>
+  <filename>amcheck</> can be effective at detecting various types of
+  failure modes that <link
+  linkend="app-initdb-data-checksums"><application>data page
+  checksums</></link> will always fail to catch.  These include:
+
+  <itemizedlist>
+   <listitem>
+    <para>
+     Filesystem or storage subsystem faults where checksums happen to
+     simply not be enabled.  Note that <filename>amcheck</> examines a
+     page as represented in some shared memory buffer at the time of
+     verification if there is only a shared buffer hit when accessing
+     the block.  Consequently, <filename>amcheck</> does not
+     necessarily examine data read from the filesystem at the time of
+     verification.  Note that when checksums are enabled,
+     <filename>amcheck</> may raise an error due to a checksum failure
+     when a corrupt block is read into a buffer.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Corruption caused by faulty RAM, and the broader memory subsystem
+     and operating system.  <productname>PostgreSQL</> does not
+     protect against correctable memory errors and it is assumed you
+     will operate using RAM that uses industry standard Error
+     Correcting Codes (ECC) or better protection.  However, ECC memory
+     is typically only immune to single-bit errors, and should not be
+     assumed to provide <emphasis>absolute</emphasis> protection
+     against failures that result in memory corruption.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Structural inconsistencies caused by incorrect operator class
+     implementations, including issues due to the comparison rules of
+     operating system collations changing the ordering implied by
+     comparisons of an underlying collatable type, such as
+     <type>text</>.  Though rare, updates to operating system
+     collation rules can cause these issues.  More commonly, an
+     inconsistency in the collation order between a master server and
+     a standby server is implicated, possibly because the
+     <emphasis>major</> operating system version in use is
+     inconsistent.  Such inconsistencies will generally only arise on
+     standby servers, and so can generally only be detected on standby
+     servers.  If a problem like this arises, it may not affect each
+     individual index that is ordered using an affected collation,
+     simply because <emphasis>indexed</> values might happen to have
+     the same absolute ordering regardless of the behavioral
+     inconsistency.  See <xref linkend="locale"> and <xref
+     linkend="collation"> for further details about how
+     <productname>PostgreSQL</> uses operating system locales and
+     collations.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Corruption caused by hypothetical undiscovered bugs in the
+     underlying <productname>PostgreSQL</> access method code.
+     Automatic verification of the structural integrity of indexes
+     plays a role in the general testing of new or proposed
+     <productname>PostgreSQL</> features that could plausibly allow a
+     logical inconsistency to be introduced.  One obvious testing
+     strategy is to call <filename>amcheck</> functions continuously
+     when running the standard regression tests.  See <xref
+     linkend="regress-run"> for details on running the tests.
+    </para>
+   </listitem>
+  </itemizedlist>
+
+  No error concerning corruption raised by <filename>amcheck</> should
+  ever be a false positive.  Users are strongly advised to perform a
+  <command>REINDEX</> for any index where corruption is indicated,
+  although it is also important to identify and correct the underlying
+  problem.  In general, <filename>amcheck</> can only prove the
+  presence of corruption; it cannot prove its absence.
+ </para>
+
+ </sect2>
+
+</sect1>
diff --git a/doc/src/sgml/contrib.sgml b/doc/src/sgml/contrib.sgml
index 4e3f337..9f6389c 100644
--- a/doc/src/sgml/contrib.sgml
+++ b/doc/src/sgml/contrib.sgml
@@ -103,6 +103,7 @@ CREATE EXTENSION <replaceable>module_name</> FROM unpackaged;
  </para>
 
  &adminpack;
+ &amcheck;
  &auth-delay;
  &auto-explain;
  &btree-gin;
diff --git a/doc/src/sgml/filelist.sgml b/doc/src/sgml/filelist.sgml
index 30adece..5675d6d 100644
--- a/doc/src/sgml/filelist.sgml
+++ b/doc/src/sgml/filelist.sgml
@@ -104,6 +104,7 @@
 <!-- contrib information -->
 <!ENTITY contrib         SYSTEM "contrib.sgml">
 <!ENTITY adminpack       SYSTEM "adminpack.sgml">
+<!ENTITY amcheck         SYSTEM "amcheck.sgml">
 <!ENTITY auth-delay      SYSTEM "auth-delay.sgml">
 <!ENTITY auto-explain    SYSTEM "auto-explain.sgml">
 <!ENTITY btree-gin       SYSTEM "btree-gin.sgml">
-- 
1.9.1

diff --git a/contrib/amcheck/amcheck.c b/contrib/amcheck/amcheck.c
index 66d1f4f..91b2bc5 100644
--- a/contrib/amcheck/amcheck.c
+++ b/contrib/amcheck/amcheck.c
@@ -1118,6 +1118,9 @@ invariant_key_less_than_equal_offset(BtreeCheckState *state, ScanKey key,
 	int16		natts = state->rel->rd_rel->relnatts;
 	int32		cmp;
 
+#if (PG_VERSION_NUM >= 90600)
+		natts = state->rel->rd_index->indnkeyatts;
+#endif
 	cmp = _bt_compare(state->rel, natts, key, state->target, upperbound);
 
 	return cmp <= 0;
@@ -1139,6 +1142,9 @@ invariant_key_greater_than_equal_offset(BtreeCheckState *state, ScanKey key,
 	int16		natts = state->rel->rd_rel->relnatts;
 	int32		cmp;
 
+#if (PG_VERSION_NUM >= 90600)
+		natts = state->rel->rd_index->indnkeyatts;
+#endif
 	cmp = _bt_compare(state->rel, natts, key, state->target, lowerbound);
 
 	return cmp >= 0;
@@ -1164,6 +1170,9 @@ invariant_key_less_than_equal_nontarget_offset(BtreeCheckState *state,
 	int16		natts = state->rel->rd_rel->relnatts;
 	int32		cmp;
 
+#if (PG_VERSION_NUM >= 90600)
+		natts = state->rel->rd_index->indnkeyatts;
+#endif
 	cmp = _bt_compare(state->rel, natts, key, nontarget, upperbound);
 
 	return cmp <= 0;

From 03046b49c893c7695bbae365c33e3d7b27a1f9a3 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Tue, 10 Jun 2014 22:20:40 -0700
Subject: [PATCH] Add amcheck extension to contrib

The new extension makes available two SQL-callable functions, each of
which accept a single argument (a regclass/nbtree index relation
argument) and return void.

The SQL-callable function bt_index_check() checks invariants of the
target index by walking the tree, performing various checks of the
sanity of the page space using insertion scankeys to compare items.  The
SQL-callable function bt_index_parent_check() performs a superset of the
checks performed by bt_index_check(): the same checks, as well as
another check verifying that each downlink is actually respected as a
lower bound on its child page.

bt_index_check() requires only an AccessShareLock on the target.
bt_index_parent_check() requires an ExclusiveLock on the target,
and ShareLock on its heap relation.
---
 contrib/Makefile                 |    1 +
 contrib/amcheck/Makefile         |   19 +
 contrib/amcheck/amcheck--1.0.sql |   20 +
 contrib/amcheck/amcheck.c        | 1267 ++++++++++++++++++++++++++++++++++++++
 contrib/amcheck/amcheck.control  |    5 +
 doc/src/sgml/amcheck.sgml        |  278 +++++++++
 doc/src/sgml/contrib.sgml        |    1 +
 doc/src/sgml/filelist.sgml       |    1 +
 8 files changed, 1592 insertions(+)
 create mode 100644 contrib/amcheck/Makefile
 create mode 100644 contrib/amcheck/amcheck--1.0.sql
 create mode 100644 contrib/amcheck/amcheck.c
 create mode 100644 contrib/amcheck/amcheck.control
 create mode 100644 doc/src/sgml/amcheck.sgml

diff --git a/contrib/Makefile b/contrib/Makefile
index 25263c0..4acd50e 100644
--- a/contrib/Makefile
+++ b/contrib/Makefile
@@ -6,6 +6,7 @@ include $(top_builddir)/src/Makefile.global
 
 SUBDIRS = \
 		adminpack	\
+		amcheck		\
 		auth_delay	\
 		auto_explain	\
 		bloom		\
diff --git a/contrib/amcheck/Makefile b/contrib/amcheck/Makefile
new file mode 100644
index 0000000..7bb29aa
--- /dev/null
+++ b/contrib/amcheck/Makefile
@@ -0,0 +1,19 @@
+# contrib/amcheck/Makefile
+
+MODULE_big	= amcheck
+OBJS		= amcheck.o $(WIN32RES)
+
+EXTENSION = amcheck
+DATA = amcheck--1.0.sql
+PGFILEDESC = "amcheck - functions to verify access method invariants"
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/amcheck
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/amcheck/amcheck--1.0.sql b/contrib/amcheck/amcheck--1.0.sql
new file mode 100644
index 0000000..ebbd6ac
--- /dev/null
+++ b/contrib/amcheck/amcheck--1.0.sql
@@ -0,0 +1,20 @@
+/* contrib/amcheck/amcheck--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION amcheck" to load this file. \quit
+
+--
+-- bt_index_check()
+--
+CREATE FUNCTION bt_index_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'bt_index_check'
+LANGUAGE C STRICT;
+
+--
+-- bt_index_parent_check()
+--
+CREATE FUNCTION bt_index_parent_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'bt_index_parent_check'
+LANGUAGE C STRICT;
diff --git a/contrib/amcheck/amcheck.c b/contrib/amcheck/amcheck.c
new file mode 100644
index 0000000..5c4d02d
--- /dev/null
+++ b/contrib/amcheck/amcheck.c
@@ -0,0 +1,1267 @@
+/*-------------------------------------------------------------------------
+ *
+ * amcheck.c
+ *		Verifies the integrity of access methods based on invariants.
+ *
+ * Provides SQL-callable functions for verifying that various logical
+ * invariants in the structure of index access methods are respected.  This
+ * includes, for example, the invariant that each page in the target B-Tree
+ * index has "real" items in logical order as reported by an insertion scankey
+ * (the insertion scankey sort-wise NULL semantics are useful for
+ * verification).
+ *
+ *
+ * Copyright (c) 2016, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  contrib/amcheck/amcheck.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/nbtree.h"
+#include "access/transam.h"
+#include "catalog/index.h"
+#include "catalog/pg_am.h"
+#include "commands/tablecmds.h"
+#include "miscadmin.h"
+#include "storage/lmgr.h"
+#include "utils/memutils.h"
+#include "utils/snapmgr.h"
+
+
+PG_MODULE_MAGIC;
+
+#define CHECK_SUPERUSER() { \
+		if (!superuser()) \
+			ereport(ERROR, \
+					(errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), \
+					 (errmsg("must be superuser to use verification functions")))); }
+
+/*
+ * As noted in comments above _bt_compare(), there is special handling of the
+ * first data item (that is, the first item with a valid downlink -- not the
+ * high key item) on a non-leaf (internal) page.  There is clearly no point in
+ * having amcheck functions make any comparison of or against these "minus
+ * infinity" items, because they contain no actual information other than the
+ * downlink.
+ */
+#define OFFSET_IS_MINUS_INFINITY(opaque, offset) \
+	(!P_ISLEAF(opaque) && offset == P_FIRSTDATAKEY(opaque))
+
+/*
+ * Callers to verification functions should never receive a false positive
+ * indication of corruption.  Therefore, when using amcheck functions for
+ * stress testing, it may be useful to temporally change the CORRUPTION elevel
+ * to PANIC, to immediately halt the server in the event of detecting an
+ * invariant condition violation.  This may preserve more information about the
+ * nature of the underlying problem.  Note that modifying the CORRUPTION
+ * constant to be an elevel < ERROR is not well tested.
+ */
+#ifdef NOT_USED
+#define CORRUPTION		PANIC
+#define CONCERN			WARNING
+#define POSITION		NOTICE
+#else
+#define CORRUPTION		ERROR
+#define CONCERN			DEBUG1
+#define POSITION		DEBUG2
+#endif
+
+/*
+ * A B-Tree cannot possibly have this many levels, since there must be one
+ * block per level, which is bound by the range of BlockNumber:
+ */
+#define InvalidBtreeLevel	((uint32) InvalidBlockNumber)
+
+/*
+ * State associated with verifying a B-Tree index
+ */
+typedef struct BtreeCheckState
+{
+	/*
+	 * Unchanging state, established at start of verification:
+	 *
+	 * rel:                 B-Tree Index Relation
+	 * exclusivelock:       ExclusiveLock held on rel; else AccessShareLock
+	 * checkstrategy:       Buffer access strategy
+	 * targetcontext:       Target page memory context
+	 */
+	Relation				rel;
+	bool					exclusivelock;
+	BufferAccessStrategy 	checkstrategy;
+	MemoryContext			targetcontext;
+
+	/*
+	 * Mutable state, for verification of particular page:
+	 *
+	 * target:              Main target page
+	 * targetblock:         Main target page's block number
+	 * targetlsn:           Main target page's LSN
+	 *
+	 * target is the point of reference for a verification operation.
+	 *
+	 * Note: targetlsn is always from "target".  It is stashed here out of
+	 * convenience.
+	 *
+	 * Other B-Tree pages may be allocated, but those are always auxiliary
+	 * (e.g. they are target's child pages).  Conceptually, only the target
+	 * page is checked.  Each page found by verification's left/right,
+	 * top/bottom scan becomes the target once.
+	 *
+	 * Memory is managed by resetting targetcontext after verification of some
+	 * target page finishes (possibly including target verification that
+	 * depends on non-target page state).
+	 */
+	Page					target;
+	BlockNumber				targetblock;
+	XLogRecPtr				targetlsn;
+
+} BtreeCheckState;
+
+/*
+ * Starting point for verifying an entire B-Tree index level
+ */
+typedef struct BtreeLevel
+{
+	/* Level number (0 is leaf page level). */
+	uint32			level;
+
+	/* Left most block on level.  Scan of level begins here. */
+	BlockNumber		leftmost;
+
+	/* Is this level reported as "true" root level by meta page? */
+	bool			istruerootlevel;
+} BtreeLevel;
+
+PG_FUNCTION_INFO_V1(bt_index_check);
+PG_FUNCTION_INFO_V1(bt_index_parent_check);
+
+static void btree_index_checkable(Relation rel);
+static void bt_check_every_level(Relation rel, bool exclusivelock);
+static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state,
+											   BtreeLevel level);
+static void bt_target_page_check(BtreeCheckState *state);
+static ScanKey bt_right_page_check_scankey(BtreeCheckState *state);
+static void bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
+							  ScanKey targetkey);
+static bool invariant_key_less_than_equal_offset(BtreeCheckState *state,
+												 ScanKey key,
+												 OffsetNumber upperbound);
+static bool invariant_key_greater_than_equal_offset(BtreeCheckState *state,
+													ScanKey key,
+													OffsetNumber lowerbound);
+static bool invariant_key_less_than_equal_nontarget_offset(BtreeCheckState *state,
+														   Page other,
+														   ScanKey key,
+														   OffsetNumber upperbound);
+static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum);
+
+/*
+ * bt_index_check(index regclass)
+ *
+ * Verify integrity of B-Tree index.
+ *
+ * Only acquires AccessShareLock on index relation.  Does not consider
+ * invariants that exist between parent/child pages.
+ */
+Datum
+bt_index_check(PG_FUNCTION_ARGS)
+{
+	Oid			relid = PG_GETARG_OID(0);
+	Relation	indrel;
+
+	CHECK_SUPERUSER();
+
+	indrel = relation_open(relid, AccessShareLock);
+
+	/* Relation suitable for checking as B-Tree? */
+	btree_index_checkable(indrel);
+
+	/* Check index */
+	bt_check_every_level(indrel, false);
+
+	relation_close(indrel, AccessShareLock);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * bt_index_parent_check(index regclass)
+ *
+ * Verify integrity of B-Tree index.
+ *
+ * Acquires ExclusiveLock on index relation, and ShareLock on the associated
+ * heap relation, a bit like REINDEX.  Verifies that downlinks in parent pages
+ * are valid lower bounds on child pages.
+ */
+Datum
+bt_index_parent_check(PG_FUNCTION_ARGS)
+{
+	Oid			indrelid = PG_GETARG_OID(0);
+	Oid			heapid;
+	Relation	indrel;
+	Relation	heaprel;
+
+	CHECK_SUPERUSER();
+
+	/*
+	 * We must lock table before index to avoid deadlocks.  However, if the
+	 * passed indrelid isn't an index then IndexGetRelation() will fail.
+	 * Rather than emitting a not-very-helpful error message, postpone
+	 * complaining, expecting that the is-it-an-index test below will fail.
+	 */
+	heapid = IndexGetRelation(indrelid, true);
+	if (OidIsValid(heapid))
+		heaprel = heap_open(heapid, ShareLock);
+	else
+		heaprel = NULL;
+
+	/*
+	 * Open the target index relations separately (like relation_openrv(), but
+	 * with heap relation locked first to prevent deadlocking).  In hot standby
+	 * mode this will raise an error.
+	 */
+	indrel = index_open(indrelid, ExclusiveLock);
+
+	/* Check for active uses of the index in the current transaction */
+	CheckTableNotInUse(indrel, "bt_index_parent_check");
+
+	/* Relation suitable for checking as B-Tree? */
+	btree_index_checkable(indrel);
+
+	/* Check index */
+	bt_check_every_level(indrel, true);
+
+	index_close(indrel, ExclusiveLock);
+	if (heaprel)
+		heap_close(heaprel, ShareLock);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * btree_index_checkable()
+ *
+ * Basic checks about the suitability of a relation for checking as a B-Tree
+ * index.
+ */
+static void
+btree_index_checkable(Relation rel)
+{
+	if (rel->rd_rel->relkind != RELKIND_INDEX ||
+		rel->rd_rel->relam != BTREE_AM_OID)
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("only nbtree access method indexes are supported"),
+				 errdetail("Relation \"%s\" is not a B-Tree index.",
+						   RelationGetRelationName(rel))));
+
+	if (RELATION_IS_OTHER_TEMP(rel))
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot access temporary tables of other sessions"),
+				 errdetail("Index \"%s\" is associated with temporary relation.",
+						   RelationGetRelationName(rel))));
+
+	if (!rel->rd_index->indisready)
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot check index \"%s\"",
+						RelationGetRelationName(rel)),
+				 errdetail("Index is not yet ready for insertions")));
+
+	if (!rel->rd_index->indisvalid)
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot check index \"%s\"",
+						RelationGetRelationName(rel)),
+				 errdetail("Index is not valid")));
+}
+
+/*
+ * bt_check_every_level()
+ *
+ * Main entry point for B-Tree SQL-callable functions.  Walks the B-Tree in
+ * logical order, verifying invariants as it goes.
+ *
+ * It is the caller's responsibility to acquire appropriate heavyweight lock on
+ * the index relation, and advise us if extra checks are safe when an
+ * ExclusiveLock is held.  An ExclusiveLock is generally assumed to prevent any
+ * kind of physical modification to the index structure, including
+ * modifications that VACUUM may make.
+ */
+static void
+bt_check_every_level(Relation rel, bool exclusivelock)
+{
+	BtreeCheckState	   *state;
+	Page				metapage;
+	BTMetaPageData	   *metad;
+	uint32				previouslevel;
+	BtreeLevel			current;
+
+	/*
+	 * RecentGlobalXmin assertion matches index_getnext_tid().  See note on
+	 * RecentGlobalXmin/B-Tree page deletion.
+	 */
+	Assert(TransactionIdIsValid(RecentGlobalXmin));
+
+	/*
+	 * Initialize state for entire verification operation
+	 */
+	state = palloc(sizeof(BtreeCheckState));
+	state->rel = rel;
+	state->exclusivelock = exclusivelock;
+	state->checkstrategy = GetAccessStrategy(BAS_BULKREAD);
+	/* Create context for page */
+	state->targetcontext = AllocSetContextCreate(CurrentMemoryContext,
+												 "amcheck page data",
+												 ALLOCSET_DEFAULT_MINSIZE,
+												 ALLOCSET_DEFAULT_INITSIZE,
+												 ALLOCSET_DEFAULT_MAXSIZE);
+
+	/* Get true root block from meta-page */
+	metapage = palloc_btree_page(state, BTREE_METAPAGE);
+	metad = BTPageGetMeta(metapage);
+
+	/*
+	 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
+	 * the fast root and true root differ.
+	 *
+	 * Start from the true root, not the fast root, unlike conventional index
+	 * scans.  This approach is more thorough, and removes the risk of
+	 * following a stale fast root from the meta page.
+	 */
+	if (metad->btm_fastroot != metad->btm_root)
+		ereport(CONCERN,
+				(errcode(ERRCODE_DUPLICATE_OBJECT),
+				 errmsg("fast root mismatch in index %s",
+						RelationGetRelationName(rel)),
+				 errdetail_internal("Fast block %u (level %u) "
+									"differs from true root "
+									"block %u (level %u).",
+									metad->btm_fastroot, metad->btm_fastlevel,
+									metad->btm_root, metad->btm_level)));
+
+	/*
+	 * Starting at the root, verify every level.  Move left to right, top to
+	 * bottom.  Note that there may be no pages other than the meta page (meta
+	 * page can indicate that root is P_NONE when the index is totally empty).
+	 */
+	previouslevel = InvalidBtreeLevel;
+	current.level = metad->btm_level;
+	current.leftmost = metad->btm_root;
+	current.istruerootlevel =  true;
+	while (current.leftmost != P_NONE)
+	{
+		/*
+		 * Verify this level, and get left most page for next level down, if
+		 * not at leaf level
+		 */
+		current = bt_check_level_from_leftmost(state, current);
+
+		if (current.leftmost == InvalidBlockNumber)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("index \"%s\" has no valid pages on level below %u or first level",
+							RelationGetRelationName(rel), previouslevel)));
+
+		previouslevel = current.level;
+	}
+
+	/* Be tidy: */
+	MemoryContextDelete(state->targetcontext);
+}
+
+/*
+ * bt_check_level_from_leftmost()
+ *
+ * Given a left-most block at some level, move right, verifying each page
+ * individually (with more verification across pages for "exclusivelock"
+ * callers).  Caller should pass the true root page as the leftmost initially,
+ * working their way down by passing what is returned for the last call here
+ * until level 0 (leaf page level) was reached.
+ *
+ * Returns state for next call, if any.  This includes left-most block number
+ * one level lower that should be passed on next level/call, or P_NONE leaf
+ * level is checked.  Level numbers follow the nbtree convention: higher levels
+ * have higher numbers, because new levels are added only due to a root page
+ * split.  Note that prior to the first root page split, the root is also a
+ * leaf page.  This means that there is always a level 0 (leaf level), and it's
+ * always the last level processed.
+ *
+ * Note on memory management:  State's per-page context is reset here, between
+ * each call to bt_target_page_check().
+ */
+static BtreeLevel
+bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
+{
+	/* State to establish early, concerning entire level */
+	BTPageOpaque	opaque;
+	MemoryContext 	oldcontext;
+	BtreeLevel		nextleveldown;
+
+	/* Variables for iterating across level using right links */
+	BlockNumber		leftcurrent = P_NONE;
+	BlockNumber		current = level.leftmost;
+
+	/* Initialize return state */
+	nextleveldown.leftmost = InvalidBlockNumber;
+	nextleveldown.level = InvalidBtreeLevel;
+	nextleveldown.istruerootlevel = false;
+
+	/* Use page-level context for duration of this call */
+	oldcontext = MemoryContextSwitchTo(state->targetcontext);
+
+	elog(POSITION, "verifying level %u%s", level.level,
+		 level.istruerootlevel?
+		 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
+
+	do
+	{
+		/* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
+		CHECK_FOR_INTERRUPTS();
+
+		/* Initialize state for this iteration */
+		state->targetblock = current;
+		state->target = palloc_btree_page(state, state->targetblock);
+		state->targetlsn = PageGetLSN(state->target);
+
+		opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+		if (P_IGNORE(opaque))
+		{
+			if (P_RIGHTMOST(opaque))
+				ereport(CORRUPTION,
+						(errcode(ERRCODE_INDEX_CORRUPTED),
+						 errmsg("block %u fell off the end of index \"%s\"",
+								current, RelationGetRelationName(state->rel))));
+			else
+				ereport(CONCERN,
+						(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+						 errmsg("block %u of index \"%s\" ignored",
+								current, RelationGetRelationName(state->rel))));
+			goto nextpage;
+		}
+		else if (nextleveldown.leftmost == InvalidBlockNumber)
+		{
+			/*
+			 * A concurrent page split could make the caller supplied leftmost
+			 * block no longer contain the leftmost page, or no longer be the
+			 * true root, but where that isn't possible due to heavyweight
+			 * locking, check that the first valid page meets caller's
+			 * expectations.
+			 */
+			if (state->exclusivelock)
+			{
+				if (!P_LEFTMOST(opaque))
+					ereport(CORRUPTION,
+							(errcode(ERRCODE_INDEX_CORRUPTED),
+							 errmsg("block %u is not leftmost in index \"%s\"",
+									current, RelationGetRelationName(state->rel))));
+
+				if (level.istruerootlevel && !P_ISROOT(opaque))
+					ereport(CORRUPTION,
+							(errcode(ERRCODE_INDEX_CORRUPTED),
+							 errmsg("block %u is not true root in index \"%s\"",
+									current, RelationGetRelationName(state->rel))));
+			}
+
+			/*
+			 * Before beginning any non-trivial examination of level, establish
+			 * next level down's leftmost block number, which next call here
+			 * will pass as its leftmost (iff this isn't leaf level).
+			 *
+			 * There should be at least one non-ignorable page per level.
+			 */
+			if (!P_ISLEAF(opaque))
+			{
+				IndexTuple		itup;
+				ItemId			itemid;
+
+				/* Internal page -- downlink gets leftmost on next level */
+				itemid = PageGetItemId(state->target, P_FIRSTDATAKEY(opaque));
+				itup = (IndexTuple) PageGetItem(state->target, itemid);
+				nextleveldown.leftmost = ItemPointerGetBlockNumber(&(itup->t_tid));
+				nextleveldown.level = opaque->btpo.level - 1;
+			}
+			else
+			{
+				/*
+				 * Leaf page -- final level caller must process.
+				 *
+				 * Note that this could also be the root page, if there has
+				 * been no root page split yet.
+				 */
+				nextleveldown.leftmost = P_NONE;
+				nextleveldown.level = InvalidBtreeLevel;
+			}
+
+			/*
+			 * Finished setting up state for this call/level.  Control will
+			 * never end up back here in any future loop iteration for this
+			 * level.
+			 */
+		}
+
+		if (state->exclusivelock && opaque->btpo_prev != leftcurrent)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("right link/left link pair in index \"%s\" not in mutual agreement",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Deleted block=%u left block=%u link reported block=%u.",
+										current, leftcurrent, opaque->btpo_prev)));
+
+		/* Verify invariants for page -- all important checks occur here */
+		bt_target_page_check(state);
+
+nextpage:
+
+		/* Try to detect circular links */
+		if (current == leftcurrent || current == opaque->btpo_prev)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("circular link chain found in block %u of index \"%s\"",
+							current, RelationGetRelationName(state->rel))));
+
+		leftcurrent = current;
+		current = opaque->btpo_next;
+
+		/* Free page and associated memory for this iteration */
+		MemoryContextReset(state->targetcontext);
+	}
+	while (current != P_NONE);
+
+	/* Don't change context for caller */
+	MemoryContextSwitchTo(oldcontext);
+
+	return nextleveldown;
+}
+
+/*
+ * bt_target_page_check()
+ *
+ * Function performs the following checks on target page, or pages ancillary to
+ * target page:
+ *
+ * - That every "real" data item is less than or equal to the high key, which
+ *   is an upper bound on the items on the pages (where there is a high key at
+ *   all -- pages that are rightmost lack one).
+ *
+ * - That within the page, every "real" item is less than or equal to the item
+ *   immediately to its right, if any (i.e., that the items are in order within
+ *   the page, so that the binary searches performed by index scans are sane).
+ *
+ * - That the last item stored on the page is less than or equal to the first
+ *   "real" data item on the page to the right (if such a first item is
+ *   available).
+ *
+ * Furthermore, when state passed shows ExclusiveLock held, function also
+ * checks:
+ *
+ * - That all child pages respect downlinks lower bound (internal pages only).
+ *
+ * Note:  This routine is not especially proactive in freeing memory.  High
+ * watermark memory consumption is bound to some small fixed multiple of
+ * BLCKSZ, though.  Caller should reset the current context between calls here.
+ */
+static void
+bt_target_page_check(BtreeCheckState *state)
+{
+	OffsetNumber	offset;
+	OffsetNumber	max;
+	BTPageOpaque	topaque;
+
+	topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+	max = PageGetMaxOffsetNumber(state->target);
+
+	elog(POSITION, "verifying %u items on %s block %u", max,
+		 P_ISLEAF(topaque) ? "leaf":"internal", state->targetblock);
+
+	/*
+	 * Loop over page items, but don't start from P_HIKEY (don't have iteration
+	 * directly considering high key item, if any).  That's something that is
+	 * used as part of verifying all other items, but doesn't get its own
+	 * iteration.
+	 */
+	for (offset = P_FIRSTDATAKEY(topaque);
+		 offset <= max;
+		 offset = OffsetNumberNext(offset))
+	{
+		ItemId		itemid;
+		IndexTuple	itup;
+		ScanKey		skey;
+
+		CHECK_FOR_INTERRUPTS();
+
+		/* Don't try to generate scankey using "minus infinity" garbage data */
+		if (OFFSET_IS_MINUS_INFINITY(topaque, offset))
+			continue;
+
+		/* Build insertion scankey for current page offset */
+		itemid = PageGetItemId(state->target, offset);
+		itup = (IndexTuple) PageGetItem(state->target, itemid);
+		skey = _bt_mkscankey(state->rel, itup);
+
+		/*
+		 *   ********************
+		 *   * High key check   *
+		 *   ********************
+		 *
+		 * If there is a high key, which there must be for a non-rightmost
+		 * page, check that it actually is upper bound on all page items.
+		 *
+		 * We prefer to check all items, rather than checking just the first
+		 * and trusting that the operator class obeys the transitive law (which
+		 * implies that all subsequent items also respected the high key
+		 * invariant if they pass the page order check).
+		 *
+		 * Ideally, we'd compare every item in the index against every other
+		 * item in the index, and not trust opclass obedience of the transitive
+		 * law to bridge the gap between children and their grandparents (as
+		 * well as great-grandparents, and so on).  We don't go to those
+		 * lengths because that would be prohibitively expensive, and probably
+		 * not markedly more effective in practice.
+		 */
+		if (!P_RIGHTMOST(topaque) &&
+			!invariant_key_less_than_equal_offset(state, skey, P_HIKEY))
+		{
+			char	   *itid,  *htid;
+
+			itid = psprintf("(%u,%u)", state->targetblock, offset);
+			htid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("high key invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Index tid=%s points to %s tid=%s "
+										"page lsn=%X/%X.",
+										itid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										htid,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+		}
+
+		/*
+		 *   ********************
+		 *   * Page order check *
+		 *   ********************
+		 *
+		 * Check that items are stored on page in logical order, by checking
+		 * current item is less than or equal to next item (if any).
+		 */
+		if (OffsetNumberNext(offset) <= max &&
+			!invariant_key_less_than_equal_offset(state, skey,
+												  OffsetNumberNext(offset)))
+		{
+			char	   *itid,  *htid,
+					   *nitid, *nhtid;
+
+			itid = psprintf("(%u,%u)", state->targetblock, offset);
+			htid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+			nitid = psprintf("(%u,%u)", state->targetblock,
+							 OffsetNumberNext(offset));
+
+			/* Reuse itup to get pointed-to heap location of second item */
+			itemid = PageGetItemId(state->target, OffsetNumberNext(offset));
+			itup = (IndexTuple) PageGetItem(state->target, itemid);
+			nhtid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("page order invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Lower index tid=%s (points to %s tid=%s) "
+										"higher index tid=%s (points to %s tid=%s) "
+										"page lsn=%X/%X.",
+										itid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										htid,
+										nitid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										nhtid,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+		}
+		/*
+		 *   ********************
+		 *   * Last item check  *
+		 *   ********************
+		 *
+		 * Check last item against next/right page's first data item's when
+		 * last item on page is reached.
+		 *
+		 * The general idea here is that checking the ordering of items on the
+		 * page should still perform some check on the last item on the page,
+		 * if at all possible.  In other words, this is roughly the same
+		 * process as the page order check that has already been performed for
+		 * every other "real" item on target page by now; we just need to reach
+		 * into the next page to get a scankey to compare against lower bound
+		 * of max.
+		 */
+		else if (offset == max)
+		{
+			ScanKey		rightkey;
+
+			/* Get item in next/right page */
+			rightkey = bt_right_page_check_scankey(state);
+
+			if (rightkey &&
+				!invariant_key_greater_than_equal_offset(state, rightkey, max))
+			{
+				/*
+				 * As discussed in bt_right_page_check_scankey(),
+				 * non-ExclusiveLock case might have had target page deleted,
+				 * in which case no error is raised
+				 */
+				if (!state->exclusivelock)
+				{
+					/* Get fresh copy of target page */
+					state->target = palloc_btree_page(state, state->targetblock);
+					/* Note that we deliberately do not update target LSN */
+					topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+					/*
+					 * Because of RecentGlobalXmin interlock against VACUUM's
+					 * recycling of blocks, we can safely assume that this is
+					 * substantively the same target page as before.
+					 *
+					 * Just return, because all !exclusivelock checks already
+					 * performed against target.
+					 */
+					if (P_IGNORE(topaque))
+						return;
+				}
+				ereport(CORRUPTION,
+						(errcode(ERRCODE_INDEX_CORRUPTED),
+						 errmsg("cross page order invariant violated for index \"%s\"",
+								RelationGetRelationName(state->rel)),
+						 errdetail_internal("Last item on page tid=(%u,%u) "
+											"page lsn=%X/%X.",
+											state->targetblock, offset,
+											(uint32) (state->targetlsn >> 32),
+											(uint32) state->targetlsn)));
+			}
+		}
+
+		/*
+		 *   ********************
+		 *   * Downlink check   *
+		 *   ********************
+		 *
+		 * Additional check of child items against target page (their parent),
+		 * iff this is internal page and caller holds ExclusiveLock on index
+		 * relation.  This involves a pass over each child page at the end of
+		 * each iteration (excluding the minus infinity iteration which
+		 * internal pages always have, which is immediately skipped).
+		 */
+		if (!P_ISLEAF(topaque) && state->exclusivelock)
+		{
+			BlockNumber childblock = ItemPointerGetBlockNumber(&(itup->t_tid));
+
+			bt_downlink_check(state, childblock, skey);
+		}
+	}
+}
+
+/*
+ * bt_right_page_check_scankey()
+ *
+ * Return a scankey for an item on page to right of current target (or the
+ * first non-ignorable page), sufficient to check ordering invariant on last
+ * item in current target page.  Returned scankey relies on local memory
+ * allocated for the child page, which caller cannot pfree().  Caller's memory
+ * context should be reset between calls here.
+ *
+ * This is the first data item, and so all adjacent items are checked against
+ * their immediate sibling item (which may be on a sibling page, or even a
+ * "cousin" page at parent boundaries where target's rightlink points to page
+ * with different parent page).  If no such valid item is available, return
+ * NULL instead.
+ *
+ * Note that !exclusivelock callers must reverify that target page has not been
+ * concurrently deleted.
+ */
+static ScanKey
+bt_right_page_check_scankey(BtreeCheckState *state)
+{
+	BTPageOpaque	opaque;
+	ItemId			rightitem;
+	BlockNumber		targetnext;
+	Page			rightpage;
+	OffsetNumber	nline;
+
+	/* Determine target's next block number */
+	opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+	/* If target is already rightmost, no right sibling; nothing to do here */
+	if (P_RIGHTMOST(opaque))
+		return NULL;
+
+	/*
+	 * General notes on concurrent page splits and page deletion:
+	 *
+	 * Concurrent page splits are not a problem for ordinary index scans, since
+	 * the key space always moves in a way that lets index scans not miss
+	 * things:  they might have to move right, but they never have to move left
+	 * (leaving aside index scans backwards, a special case).  A concurrent
+	 * page split could occur here, but just as with index scans we're
+	 * following the stale right link, which will reliably get us further along
+	 * in the key space, which is all we really need to get an item further
+	 * along in key space to check invariant in target page.
+	 *
+	 * (Note that routines like _bt_search() don't require *any* page split
+	 * interlock when descending the tree, including something very light like
+	 * a buffer pin.  That's why it's okay that we don't either.)
+	 *
+	 * A deleted page won't actually be recycled by VACUUM early enough for us
+	 * to fail to be able follow its right link (or left link, or downlink),
+	 * because it doesn't do so until it knows that no possible index scan
+	 * could land on the page with the expectation of at least being able to
+	 * move right and eventually find a non-ignorable page.  (see page
+	 * recycling/RecentGlobalXmin notes in nbtree README.)
+	 *
+	 * It's okay if we follow a rightlink and find a half-dead or dead
+	 * (ignorable) page.  Either way, there must be a sane further right link
+	 * to follow for these ignorable pages, because page deletion refuses to
+	 * merge the key space between adjacent pages that do not share a common
+	 * parent (that is, merging of the key space has to be among true sibling
+	 * pages, never cousin pages).  We should succeed in finding a page to the
+	 * right that isn't ignorable before too long.
+	 */
+	targetnext = opaque->btpo_next;
+	for (;;)
+	{
+		CHECK_FOR_INTERRUPTS();
+
+		rightpage = palloc_btree_page(state, targetnext);
+		opaque = (BTPageOpaque) PageGetSpecialPointer(rightpage);
+
+		if (!P_IGNORE(opaque) || P_RIGHTMOST(opaque))
+			break;
+
+		/* We landed on a deleted page, so step right to find a live page */
+		targetnext = opaque->btpo_next;
+		ereport(CONCERN,
+				(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+				 errmsg("level %u leftmost page of index \"%s\" was found deleted or half dead",
+						opaque->btpo.level, RelationGetRelationName(state->rel)),
+				 errdetail_internal("Deleted page found when building scankey from right sibling.")));
+
+		/* Be slightly more pro-active in freeing this memory, just in case */
+		pfree(rightpage);
+	}
+
+	/*
+	 * No ExclusiveLock held case -- why it's safe to proceed.
+	 *
+	 * Problem:
+	 *
+	 * We must avoid false positive reports of corruption when caller treats
+	 * item returned here as an upper bound on target's last item.  In general,
+	 * false positives are disallowed.  Ensuring they don't happen in
+	 * !exclusivelock case is subtle.
+	 *
+	 * A concurrent page deletion by VACUUM of the target page can result in
+	 * the insertion of items on to this right sibling page that would
+	 * previously have been inserted on our target page.  There might have been
+	 * insertions that followed target's downlink after it was made to point to
+	 * right sibling instead of target by page deletion's first phase.  The
+	 * inserters insert items that would belong on target page.  This race is
+	 * very tight, but it's possible.  This is our only problem.
+	 *
+	 * Non-problems:
+	 *
+	 * We are not hindered by a concurrent page split of the target; we'll
+	 * never land on the second half of the page anyway.  A concurrent split of
+	 * the right page will also not matter, because the first data item remains
+	 * the same within the left half, which we'll reliably land on.  If we had
+	 * to skip over ignorable/deleted pages, it cannot matter because their key
+	 * space has already been atomically merged with the first non-ignorable
+	 * page we eventually find (doesn't matter whether the page we eventually
+	 * find is a true sibling or a cousin of target, which we go into below).
+	 *
+	 * Solution:
+	 *
+	 * Caller knows that it should reverify that target is not ignorable
+	 * (half-dead or deleted) when cross-page sibling item comparison appears
+	 * to indicate corruption (invariant fails).  This detects the single race
+	 * condition that exists for caller.  This is correct because the continued
+	 * existence of target block as non-ignorable (not half-dead or deleted)
+	 * implies that target page was not merged into from the right by deletion;
+	 * the key space at or after target never moved left.  Target's parent
+	 * either has the same downlink to target as before, or a <= downlink due
+	 * to deletion at the left of target.  Target either has the same highkey
+	 * as before, or a highkey <= before when there is a page split. (The
+	 * rightmost concurrently-split-from-target-page page will still have the
+	 * same highkey as target was originally found to have, which for our
+	 * purposes is equivalent to target's highkey itself never changing, since
+	 * we reliably skip over concurrently-split-from-target-page pages.)
+	 *
+	 * In simpler terms, we allow that the key space of the target may expand
+	 * left (the key space can move left on the left side of target only), but
+	 * the target key space cannot expand right and get ahead of us without our
+	 * detecting it.  The key space of the target cannot shrink, unless it
+	 * shrinks to zero due to the deletion of the original page, our canary
+	 * condition.  (To be very precise, we're a bit stricter than that because
+	 * it might just have been that the target page split and only the original
+	 * target page was deleted.  We can be more strict, just not more lax.)
+	 *
+	 * Top level tree walk caller moves on to next page (makes it the new
+	 * target) following recovery from this race.  (cf.  The rationale for
+	 * child/downlink verification needing an ExclusiveLock within
+	 * bt_downlink_check(), where page deletion is also the main source of
+	 * trouble.)
+	 *
+	 * Note that it doesn't matter if right sibling page here is actually a
+	 * cousin page, because in order for the key space to be readjusted in a
+	 * way that causes us issues in next level up (guiding problematic
+	 * concurrent insertions to the cousin from the grandparent rather than to
+	 * the sibling from the parent), there'd have to be page deletion of
+	 * target's parent page (affecting target's parent's downlink in target's
+	 * grandparent page).  Internal page deletion only occurs when there are no
+	 * child pages (they were all fully deleted), and caller is checking that
+	 * the target's parent has at least one non-deleted (so non-ignorable)
+	 * child: the target page.  (Note that the first phase of deletion
+	 * atomically marks the page to be deleted half-dead/ignorable at the same
+	 * time downlink in its parent is removed, so we'll definitely be able to
+	 * detect that this might have happened just from the target page.)
+	 *
+	 * This trick is inspired by the method backward scans use for dealing with
+	 * concurrent page splits; concurrent page deletion is a problem that
+	 * similarly receives special consideration sometimes (it's possible that
+	 * the backwards scan will re-read its "original" block after failing to
+	 * find a right-link to it, having already moved in the opposite direction
+	 * (right/"forwards") a few times to try to locate one).  Just like us,
+	 * that happens only to determine if there was a concurrent page deletion
+	 * of a reference page, and just like us if there was a page deletion of
+	 * that reference page it means we can move on from caring about the
+	 * reference page.  See the nbtree README for a full description of how
+	 * that works.
+	 */
+	nline = PageGetMaxOffsetNumber(rightpage);
+
+	/*
+	 * Get first data item.
+	 *
+	 * Importantly, this allows the verification of page order across target
+	 * and rightmost page when rightmost page is the target's right sibling.
+	 * Moreover, the only way logical inconsistencies can really be missed
+	 * across a given level is if the transitive law is broken by an opclass,
+	 * because contiguous pairs are always compared, even across page
+	 * boundaries. (Or, we don't have a stable snapshot of structure, as in
+	 * !exclusivelock case -- it can theoretically "just miss" corruption.)
+	 */
+	if (P_ISLEAF(opaque) && nline >= P_FIRSTDATAKEY(opaque))
+	{
+		/*
+		 * For leaf page, return first data item (if any), which cannot be a
+		 * "minus infinity" item
+		 */
+		rightitem = PageGetItemId(rightpage, P_FIRSTDATAKEY(opaque));
+	}
+	else if (!P_ISLEAF(opaque) &&
+			 nline >= OffsetNumberNext(P_FIRSTDATAKEY(opaque)))
+	{
+		/*
+		 * Return first item after the internal page's undefined "minus
+		 * infinity" item, if any.  Also skip the high key if that's necessary.
+		 */
+		rightitem = PageGetItemId(rightpage,
+								  OffsetNumberNext(P_FIRSTDATAKEY(opaque)));
+	}
+	else
+	{
+		/*
+		 * No first item.  Page is probably empty leaf page, but it's also
+		 * possible that it's an internal page with only a minus infinity item.
+		 */
+		ereport(CONCERN,
+				(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+				 errmsg("%s block %u of index \"%s\" has no first data item",
+						P_ISLEAF(opaque) ? "leaf":"internal", targetnext,
+						RelationGetRelationName(state->rel))));
+		return NULL;
+	}
+
+	/*
+	 * Return first real item scankey.  Note that this relies on right page
+	 * memory remaining allocated.
+	 */
+	return _bt_mkscankey(state->rel,
+						 (IndexTuple) PageGetItem(rightpage, rightitem));
+}
+
+/*
+ * bt_downlink_check()
+ *
+ * Checks one of target's downlink against its child page.
+ *
+ * Conceptually, the target page continues to be what is checked here.  The
+ * target block is still blamed in the event of finding an invariant violation.
+ * The downlink insertion into the target is probably where any problem raised
+ * here arises, and there is no such thing as a parent link, so doing the
+ * verification this way around is much more practical.
+ */
+static void
+bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
+				  ScanKey targetkey)
+{
+	OffsetNumber	offset;
+	OffsetNumber	maxoffset;
+	Page			child;
+	BTPageOpaque	copaque;
+
+	/*
+	 * Caller must have ExclusiveLock on target relation, because of
+	 * considerations around page deletion by VACUUM.
+	 *
+	 * N.B.: In general, page deletion deletes the right sibling's downlink,
+	 * not the downlink of the page being deleted; the deleted page's downlink
+	 * is reused for its sibling.  The key space is thereby consolidated
+	 * between the deleted page and its right sibling.  (We cannot delete a
+	 * parent page's rightmost page unless it is the last child page, and we
+	 * intend to delete the parent itself.)
+	 *
+	 * If this verification happened without an ExclusiveLock, the following
+	 * race condition could cause false positives (which are generally
+	 * disallowed):
+	 *
+	 * Not having an ExclusiveLock would allow concurrent page deletion,
+	 * including deletion of the left sibling of the child page that is
+	 * examined here.  If such a page deletion occurred, and was then closely
+	 * followed by an insertion into the newly expanded key space of the child,
+	 * a false positive may result: our stale parent/target downlink would
+	 * legitimately not be a lower bound on all items in the page anymore,
+	 * because the key space was concurrently expanded "left" (insertion
+	 * followed the "new" downlink for the child, not our now-stale downlink,
+	 * which was concurrently physically removed in target/parent as part of
+	 * deletion's first phase).
+	 *
+	 * Note that while the cross-page-same-level check uses a trick that allows
+	 * it to perform verification for !exclusivelock callers, an analogous
+	 * trick seems very difficult here.  The trick that that other check uses
+	 * is, in essence, to lock down race conditions to those that occur due to
+	 * concurrent page deletion of the target; that's a race that can be
+	 * reliably detected before actually reporting corruption.  On the other
+	 * hand, we'd need to lock down race conditions involving deletion of
+	 * child's left page, at least for long enough to read the child page into
+	 * memory.  Any more granular locking schemes all seem to involve multiple
+	 * concurrently held buffer locks.  That's unacceptable for amcheck on
+	 * general principle, though; amcheck functions never hold more than one
+	 * buffer lock at a time.
+	 */
+	Assert(state->exclusivelock);
+
+	/*
+	 * Verify child page has the down-link key from target page (its parent) as
+	 * a lower bound.
+	 *
+	 * We prefer to check all items, rather than checking just the first and
+	 * trusting that the operator class obeys the transitive law (which implies
+	 * that all subsequent items also respected the downlink-as-lower-bound
+	 * invariant if they pass the page order check when the child later becomes
+	 * our target for verification).
+	 */
+	child = palloc_btree_page(state, childblock);
+	copaque = (BTPageOpaque) PageGetSpecialPointer(child);
+	maxoffset = PageGetMaxOffsetNumber(child);
+
+	for (offset = P_FIRSTDATAKEY(copaque);
+		 offset <= maxoffset;
+		 offset = OffsetNumberNext(offset))
+	{
+		/*
+		 * Skip comparison of target page key against "minus infinity" item, if
+		 * any.  Checking it would indicate that its not an upper bound, but
+		 * that's only because of the hard-coding within _bt_compare().
+		 */
+		if (OFFSET_IS_MINUS_INFINITY(copaque, offset))
+			continue;
+
+		if (!invariant_key_less_than_equal_nontarget_offset(state, child,
+															targetkey, offset))
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("down-link lower bound invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Parent block=%u child index tid=(%u,%u) "
+										"parent page lsn=%X/%X.",
+										state->targetblock, childblock, offset,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+	}
+
+	pfree(child);
+}
+
+/*
+ * invariant_key_less_than_equal_offset()
+ *
+ * Does the invariant hold that the key is less than or equal to a given upper
+ * bound offset item?
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_less_than_equal_offset(BtreeCheckState *state, ScanKey key,
+									 OffsetNumber upperbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, state->target, upperbound);
+
+	return cmp <= 0;
+}
+
+/*
+ * invariant_key_greater_than_equal_offset()
+ *
+ * Does the invariant hold that the key is greater than or equal to a given
+ * lower bound offset item?
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_greater_than_equal_offset(BtreeCheckState *state, ScanKey key,
+										OffsetNumber lowerbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, state->target, lowerbound);
+
+	return cmp >= 0;
+}
+
+/*
+ * invariant_key_less_than_equal_nontarget_offset()
+ *
+ * Does the invariant hold that the key is less than or equal to a given upper
+ * bound offset item, with the offset relating to a caller-supplied page that
+ * is not the current target page? Caller's non-target page is typically a
+ * child page of the target, checked as part of checking a property of the
+ * target page (i.e. the key comes from the target).
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_less_than_equal_nontarget_offset(BtreeCheckState *state,
+											   Page nontarget, ScanKey key,
+											   OffsetNumber upperbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, nontarget, upperbound);
+
+	return cmp <= 0;
+}
+
+/*
+ * palloc_btree_page()
+ *
+ * Given a block number of a B-Tree page, return page in palloc()'d memory.
+ * While at it, perform some basic checks of the page.
+ *
+ * There is never an attempt to get a consistent view of multiple pages using
+ * multiple concurrent buffer locks; in general, we prefer to have only one pin
+ * and buffer lock at a time, which is often all that the nbtree code requires.
+ *
+ * Operating on a copy of the page is useful because it prevents control
+ * getting stuck in an uninterruptible state when an underlying operator class
+ * misbehaves.
+ */
+static Page
+palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum)
+{
+	Buffer			buffer;
+	Page			page;
+	BTPageOpaque	opaque;
+
+	page = palloc(BLCKSZ);
+
+	/*
+	 * We copy the page into local storage to avoid holding pin on the buffer
+	 * longer than we must.
+	 */
+	buffer = ReadBufferExtended(state->rel, MAIN_FORKNUM, blocknum, RBM_NORMAL,
+								state->checkstrategy);
+	LockBuffer(buffer, BT_READ);
+
+	/*
+	 * Perform the same basic sanity checking that nbtree itself performs for
+	 * every page:
+	 */
+	_bt_checkpage(state->rel, buffer);
+
+	/* Only use copy of page in palloc()'d memory */
+	memcpy(page, BufferGetPage(buffer), BLCKSZ);
+	UnlockReleaseBuffer(buffer);
+
+	opaque = (BTPageOpaque) PageGetSpecialPointer(page);
+
+	if (opaque->btpo_flags & BTP_META && blocknum != BTREE_METAPAGE)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid meta page found at block %u in index \"%s\"",
+						blocknum, RelationGetRelationName(state->rel))));
+
+	/* Check page from block that ought to be meta page */
+	if (blocknum == BTREE_METAPAGE)
+	{
+		BTMetaPageData *metad = BTPageGetMeta(page);
+
+		if (!(opaque->btpo_flags & BTP_META) ||
+			metad->btm_magic != BTREE_MAGIC)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("index \"%s\" meta page is corrupt",
+							RelationGetRelationName(state->rel))));
+
+		if (metad->btm_version != BTREE_VERSION)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("version mismatch in index \"%s\": file version %d, code version %d",
+							RelationGetRelationName(state->rel),
+							metad->btm_version, BTREE_VERSION)));
+	}
+
+	/*
+	 * Deleted pages have no sane "level" field, so can only check non-deleted
+	 * page level
+	 */
+	if (P_ISLEAF(opaque) && !P_ISDELETED(opaque) && opaque->btpo.level != 0)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid leaf page level %u for block %u in index \"%s\"",
+						opaque->btpo.level, blocknum, RelationGetRelationName(state->rel))));
+
+	if (blocknum != BTREE_METAPAGE && !P_ISLEAF(opaque) &&
+		!P_ISDELETED(opaque) && opaque->btpo.level == 0)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid internal page level 0 for block %u in index \"%s\"",
+						opaque->btpo.level, RelationGetRelationName(state->rel))));
+
+	if (!P_ISLEAF(opaque) && P_HAS_GARBAGE(opaque))
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("internal page block %u in index \"%s\" has garbage items",
+						blocknum, RelationGetRelationName(state->rel))));
+
+	return page;
+}
diff --git a/contrib/amcheck/amcheck.control b/contrib/amcheck/amcheck.control
new file mode 100644
index 0000000..180f150
--- /dev/null
+++ b/contrib/amcheck/amcheck.control
@@ -0,0 +1,5 @@
+# amcheck extension
+comment = 'verify access method invariants'
+default_version = '1.0'
+module_pathname = '$libdir/amcheck'
+relocatable = true
diff --git a/doc/src/sgml/amcheck.sgml b/doc/src/sgml/amcheck.sgml
new file mode 100644
index 0000000..d3d6a96
--- /dev/null
+++ b/doc/src/sgml/amcheck.sgml
@@ -0,0 +1,278 @@
+<!-- doc/src/sgml/amcheck.sgml -->
+
+<sect1 id="amcheck" xreflabel="amcheck">
+ <title>amcheck</title>
+
+ <indexterm zone="amcheck">
+  <primary>amcheck</primary>
+ </indexterm>
+
+ <para>
+  The <filename>amcheck</> module provides functions that allow you to
+  verify the logical consistency of the structure of indexes.  If the
+  structure appears to be valid, no error is raised.
+ </para>
+
+ <para>
+  The functions verify various <emphasis>invariants</> in the
+  structure of the representation of particular indexes.  The
+  correctness of the access method functions behind index scans and
+  other important operations relies on these invariants always
+  holding.  For example, certain functions verify, among other things,
+  that all B-Tree pages have items in <quote>logical</> order (e.g.,
+  for B-Tree indexes on <type>text</>, index tuples should be in
+  collated lexical order).  If that particular invariant somehow fails
+  to hold, we can expect binary searches on the affected page to
+  incorrectly guide index scans, resulting in wrong answers to SQL
+  queries.  Problems like this can be very subtle.
+ </para>
+ <para>
+  Verification is performed using the same procedures as those used by
+  index scans themselves, which may be user-defined operator class
+  code.  For example, B-Tree index verification relies on comparisons
+  made with one or more B-Tree support function 1 routines.  See <xref
+  linkend="xindex-support"> for details of operator class support
+  functions.
+ </para>
+ <para>
+  <filename>amcheck</> functions may be used only by superusers.
+ </para>
+
+ <sect2>
+  <title>Functions</title>
+
+  <variablelist>
+   <varlistentry>
+    <term>
+     <function>bt_index_check(index regclass) returns void</function>
+     <indexterm>
+      <primary>bt_index_check</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>bt_index_check</function> tests that its target, a
+      B-Tree index, respects a variety of invariants.  Example usage:
+<screen>
+test=# SELECT bt_index_check(c.oid), c.relname, c.relpages
+FROM pg_index i
+JOIN pg_opclass op ON i.indclass[0] = op.oid
+JOIN pg_am am ON op.opcmethod = am.oid
+JOIN pg_class c ON i.indexrelid = c.oid
+JOIN pg_namespace n ON c.relnamespace = n.oid
+WHERE am.amname = 'btree' AND n.nspname = 'pg_catalog'
+-- Don't check pg_class (bt_index_parent_check() requires this):
+AND c.relname NOT LIKE 'pg_class%'
+-- Don't check temp tables, which may be from another session:
+AND c.relpersistence != 't'
+-- Function may throw an error when this is omitted:
+AND i.indisready AND i.indisvalid
+ORDER BY c.relpages DESC LIMIT 10;
+ bt_index_check |             relname             | relpages 
+----------------+---------------------------------+----------
+                | pg_depend_reference_index       |       43
+                | pg_depend_depender_index        |       40
+                | pg_proc_proname_args_nsp_index  |       31
+                | pg_description_o_c_o_index      |       21
+                | pg_attribute_relid_attnam_index |       14
+                | pg_proc_oid_index               |       10
+                | pg_attribute_relid_attnum_index |        9
+                | pg_amproc_fam_proc_index        |        5
+                | pg_amop_opr_fam_index           |        5
+                | pg_amop_fam_strat_index         |        5
+(10 rows)
+</screen>
+      This example shows a session that performs verification of every
+      catalog index in the database <quote>test</> (except those
+      associated with the <structname>pg_class</structname> catalog).
+      Details of just the 10 largest indexes verified are displayed.
+      Since no error is raised, all indexes tested appear to be
+      logically consistent.  Naturally, this query could easily be
+      changed to call <function>bt_index_check</function> for every
+      index in the database where verification is supported.
+     </para>
+     <para>
+      An <literal>AccessShareLock</> is acquired on the target index
+      by <function>bt_index_check</function>.  This lock mode is the
+      same lock mode acquired on relations by simple
+      <literal>SELECT</> statements.
+      <function>bt_index_check</function> does not verify invariants
+      that span child/parent relationships, nor does it verify that
+      the target index is consistent with its heap relation.  When a
+      routine, lightweight test for corruption is required in a live
+      production environment, using
+      <function>bt_index_check</function> often provides the best
+      trade-off between thoroughness of verification and limiting the
+      impact on application performance and availability.
+     </para>
+    </listitem>
+   </varlistentry>
+
+   <varlistentry>
+    <term>
+     <function>bt_index_parent_check(index regclass) returns void</function>
+     <indexterm>
+      <primary>bt_index_parent_check</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>bt_index_parent_check</function> tests that its
+      target, a B-Tree index, respects a variety of invariants.  The
+      checks performed by <function>bt_index_parent_check</function>
+      are a superset of the checks performed by
+      <function>bt_index_check</function>.
+      <function>bt_index_parent_check</function> can be thought of as
+      a more thorough variant of <function>bt_index_check</function>:
+      unlike <function>bt_index_check</function>,
+      <function>bt_index_parent_check</function> also checks
+      invariants that span parent/child relationships.  However, it
+      does not verify that the target index is consistent with its
+      heap relation.  <function>bt_index_parent_check</function>
+      follows the general convention of raising an error if it finds a
+      logical inconsistency or other problem.
+     </para>
+     <para>
+      An <literal>ExclusiveLock</> is required on the target index by
+      <function>bt_index_parent_check</function> (a
+      <literal>ShareLock</> is also acquired on the heap relation).
+      These locks prevent concurrent data modification from
+      <command>INSERT</>, <command>UPDATE</>, and <command>DELETE</>
+      commands.  The locks also prevent the underlying relation from
+      being concurrently processed by <command>VACUUM</> (and certain
+      other utility commands).  Note that the function holds locks for
+      as short a duration as possible, so there is no advantage to
+      verifying each index individually in a series of transactions,
+      unless long running queries happen to be of particular concern.
+     </para>
+     <para>
+      <function>bt_index_parent_check</function>'s additional
+      verification is more likely to detect various pathological
+      cases.  These cases may involve an incorrectly implemented
+      B-Tree operator class used by the index that is checked, or,
+      hypothetically, undiscovered bugs in the underlying B-Tree index
+      access method code.  Note that
+      <function>bt_index_parent_check</function> cannot be used when
+      Hot Standby mode is enabled (i.e., on read-only physical
+      replicas), unlike <function>bt_index_check</function>.
+     </para>
+    </listitem>
+   </varlistentry>
+  </variablelist>
+ </sect2>
+
+ <sect2>
+  <title>Using <filename>amcheck</> effectively</title>
+
+ <para>
+  <filename>amcheck</> can be effective at detecting various types of
+  failure modes that <link
+  linkend="app-initdb-data-checksums"><application>data page
+  checksums</></link> will always fail to catch.  These include:
+
+  <itemizedlist>
+   <listitem>
+    <para>
+     Structural inconsistencies caused by incorrect operator class
+     implementations.
+    </para>
+    <para>
+     This includes issues caused by the comparison rules of operating
+     system collations changing. Comparisons of datums of a collatable
+     type like <type>text</> must be immutable (just as all
+     comparisons used for B-Tree index scans must be immutable), which
+     implies that operating system collation rules must never change.
+     Though rare, updates to operating system collation rules can
+     cause these issues. More commonly, an inconsistency in the
+     collation order between a master server and a standby server is
+     implicated, possibly because the <emphasis>major</> operating
+     system version in use is inconsistent.  Such inconsistencies will
+     generally only arise on standby servers, and so can generally
+     only be detected on standby servers.
+    </para>
+    <para>
+     If a problem like this arises, it may not affect each individual
+     index that is ordered using an affected collation, simply because
+     <emphasis>indexed</> values might happen to have the same
+     absolute ordering regardless of the behavioral inconsistency. See
+     <xref linkend="locale"> and <xref linkend="collation"> for
+     further details about how <productname>PostgreSQL</> uses
+     operating system locales and collations.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Corruption caused by hypothetical undiscovered bugs in the
+     underlying <productname>PostgreSQL</> access method code or sort
+     code.
+    </para>
+    <para>
+     Automatic verification of the structural integrity of indexes
+     plays a role in the general testing of new or proposed
+     <productname>PostgreSQL</> features that could plausibly allow a
+     logical inconsistency to be introduced.  One obvious testing
+     strategy is to call <filename>amcheck</> functions continuously
+     when running the standard regression tests.  See <xref
+     linkend="regress-run"> for details on running the tests.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Filesystem or storage subsystem faults where checksums happen to
+     simply not be enabled.
+    </para>
+    <para>
+     Note that <filename>amcheck</> examines a page as represented in some
+     shared memory buffer at the time of verification if there is only a
+     shared buffer hit when accessing the block. Consequently,
+     <filename>amcheck</> does not necessarily examine data read from the
+     filesystem at the time of verification. Note that when checksums are
+     enabled, <filename>amcheck</> may raise an error due to a checksum
+     failure when a corrupt block is read into a buffer.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Corruption caused by faulty RAM, and the broader memory subsystem
+     and operating system.
+    </para>
+    <para>
+     <productname>PostgreSQL</> does not protect against correctable
+     memory errors and it is assumed you will operate using RAM that
+     uses industry standard Error Correcting Codes (ECC) or better
+     protection.  However, ECC memory is typically only immune to
+     single-bit errors, and should not be assumed to provide
+     <emphasis>absolute</emphasis> protection against failures that
+     result in memory corruption.
+    </para>
+   </listitem>
+  </itemizedlist>
+  In general, <filename>amcheck</> can only prove the presence of
+  corruption; it cannot prove its absence.
+ </para>
+
+ </sect2>
+ <sect2>
+  <title>Repairing corruption</title>
+ <para>
+  No error concerning corruption raised by <filename>amcheck</> should
+  ever be a false positive.  In practice, <filename>amcheck</> is more
+  likely to find software bugs than problems with hardware.
+  <filename>amcheck</> raises errors in the event of conditions that,
+  by definition, should never happen, and so careful analysis of
+  <filename>amcheck</> errors is often required.
+ </para>
+ <para>
+  There is no general method of repairing problems that
+  <filename>amcheck</> detects.  An explanation for the root cause of
+  an invariant violation should be sought.  <xref
+  linkend="pageinspect"> may play a useful role in diagnosing
+  corruption that <filename>amcheck</> detects. A <command>REINDEX</>
+  may or may not be effective in repairing corruption.
+ </para>
+
+ </sect2>
+
+</sect1>
diff --git a/doc/src/sgml/contrib.sgml b/doc/src/sgml/contrib.sgml
index c8708ec..54102d6 100644
--- a/doc/src/sgml/contrib.sgml
+++ b/doc/src/sgml/contrib.sgml
@@ -103,6 +103,7 @@ CREATE EXTENSION <replaceable>module_name</> FROM unpackaged;
  </para>
 
  &adminpack;
+ &amcheck;
  &auth-delay;
  &auto-explain;
  &bloom;
diff --git a/doc/src/sgml/filelist.sgml b/doc/src/sgml/filelist.sgml
index 4383711..3c7ec01 100644
--- a/doc/src/sgml/filelist.sgml
+++ b/doc/src/sgml/filelist.sgml
@@ -105,6 +105,7 @@
 <!-- contrib information -->
 <!ENTITY contrib         SYSTEM "contrib.sgml">
 <!ENTITY adminpack       SYSTEM "adminpack.sgml">
+<!ENTITY amcheck         SYSTEM "amcheck.sgml">
 <!ENTITY auth-delay      SYSTEM "auth-delay.sgml">
 <!ENTITY auto-explain    SYSTEM "auto-explain.sgml">
 <!ENTITY bloom           SYSTEM "bloom.sgml">
-- 
2.7.4

From 21c843ae0193ed17b2e5234d67f2e73f7015b3cd Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Tue, 10 Jun 2014 22:20:40 -0700
Subject: [PATCH] Add amcheck extension to contrib

The new extension makes available two SQL-callable functions, each of
which accept a single argument (a regclass/nbtree index relation
argument) and return void.

The SQL-callable function bt_index_check() checks invariants of the
target index by walking the tree, performing various checks of the
sanity of the page space using insertion scankeys to compare items.  The
SQL-callable function bt_index_parent_check() performs a superset of the
checks performed by bt_index_check(): the same checks, as well as
another check verifying that each downlink is actually respected as a
lower bound on its child page.

bt_index_check() requires only an AccessShareLock on the target.
bt_index_parent_check() requires an ExclusiveLock on the target,
and ShareLock on its heap relation.
---
 contrib/Makefile                 |    1 +
 contrib/amcheck/Makefile         |   19 +
 contrib/amcheck/amcheck--1.0.sql |   20 +
 contrib/amcheck/amcheck.control  |    5 +
 contrib/amcheck/verify_nbtree.c  | 1227 ++++++++++++++++++++++++++++++++++++++
 doc/src/sgml/amcheck.sgml        |  275 +++++++++
 doc/src/sgml/contrib.sgml        |    1 +
 doc/src/sgml/filelist.sgml       |    1 +
 8 files changed, 1549 insertions(+)
 create mode 100644 contrib/amcheck/Makefile
 create mode 100644 contrib/amcheck/amcheck--1.0.sql
 create mode 100644 contrib/amcheck/amcheck.control
 create mode 100644 contrib/amcheck/verify_nbtree.c
 create mode 100644 doc/src/sgml/amcheck.sgml

diff --git a/contrib/Makefile b/contrib/Makefile
index 25263c0..4acd50e 100644
--- a/contrib/Makefile
+++ b/contrib/Makefile
@@ -6,6 +6,7 @@ include $(top_builddir)/src/Makefile.global
 
 SUBDIRS = \
 		adminpack	\
+		amcheck		\
 		auth_delay	\
 		auto_explain	\
 		bloom		\
diff --git a/contrib/amcheck/Makefile b/contrib/amcheck/Makefile
new file mode 100644
index 0000000..f14c7aa
--- /dev/null
+++ b/contrib/amcheck/Makefile
@@ -0,0 +1,19 @@
+# contrib/amcheck/Makefile
+
+MODULE_big	= amcheck
+OBJS		= verify_nbtree.o $(WIN32RES)
+
+EXTENSION = amcheck
+DATA = amcheck--1.0.sql
+PGFILEDESC = "amcheck - functions to verify access method invariants"
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/amcheck
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/amcheck/amcheck--1.0.sql b/contrib/amcheck/amcheck--1.0.sql
new file mode 100644
index 0000000..b415f0e
--- /dev/null
+++ b/contrib/amcheck/amcheck--1.0.sql
@@ -0,0 +1,20 @@
+/* contrib/amcheck/amcheck--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION amcheck" to load this file. \quit
+
+--
+-- bt_index_check()
+--
+CREATE FUNCTION bt_index_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'bt_index_check'
+LANGUAGE C STRICT PARALLEL SAFE;
+
+--
+-- bt_index_parent_check()
+--
+CREATE FUNCTION bt_index_parent_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'bt_index_parent_check'
+LANGUAGE C STRICT PARALLEL SAFE;
diff --git a/contrib/amcheck/amcheck.control b/contrib/amcheck/amcheck.control
new file mode 100644
index 0000000..180f150
--- /dev/null
+++ b/contrib/amcheck/amcheck.control
@@ -0,0 +1,5 @@
+# amcheck extension
+comment = 'verify access method invariants'
+default_version = '1.0'
+module_pathname = '$libdir/amcheck'
+relocatable = true
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
new file mode 100644
index 0000000..295ccb8
--- /dev/null
+++ b/contrib/amcheck/verify_nbtree.c
@@ -0,0 +1,1227 @@
+/*-------------------------------------------------------------------------
+ *
+ * verify_nbtree.c
+ *		Verifies the integrity of nbtree indexes based on invariants.
+ *
+ * For B-Tree indexes, verification includes the invariant that each page in
+ * the target index has items in logical order as reported by an insertion
+ * scankey (the insertion scankey sort-wise NULL semantics are needed for
+ * verification).
+ *
+ *
+ * Copyright (c) 2016, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  contrib/amcheck/verify_nbtree.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/nbtree.h"
+#include "access/transam.h"
+#include "catalog/index.h"
+#include "catalog/pg_am.h"
+#include "commands/tablecmds.h"
+#include "miscadmin.h"
+#include "storage/lmgr.h"
+#include "utils/memutils.h"
+#include "utils/snapmgr.h"
+
+
+PG_MODULE_MAGIC;
+
+#define CHECK_SUPERUSER() { \
+		if (!superuser()) \
+			ereport(ERROR, \
+					(errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), \
+					 (errmsg("must be superuser to use verification functions")))); }
+
+/*
+ * As noted in comments above _bt_compare(), there is special handling of the
+ * first data item (that is, the first item with a valid downlink -- not the
+ * high key item) on a non-leaf (internal) page.  There is clearly no point in
+ * having amcheck functions make any comparison of or against these "minus
+ * infinity" items, because they contain no actual key to compare. (Only the
+ * child block pointer is meaningful).
+ */
+#define OFFSET_IS_MINUS_INFINITY(opaque, offset) \
+	(!P_ISLEAF(opaque) && offset == P_FIRSTDATAKEY(opaque))
+
+/*
+ * Callers to verification functions should never receive a false positive
+ * indication of corruption.  Therefore, when using amcheck functions for
+ * stress testing, it may be useful to temporally change the CORRUPTION elevel
+ * to PANIC, to immediately halt the server in the event of detecting an
+ * invariant condition violation.  This may preserve more information about the
+ * nature of the underlying problem.  Note that modifying the CORRUPTION
+ * constant to be an elevel < ERROR is not well tested.
+ */
+#ifdef NOT_USED
+#define CORRUPTION		PANIC
+#define CONCERN			WARNING
+#define POSITION		NOTICE
+#else
+#define CORRUPTION		ERROR
+#define CONCERN			DEBUG1
+#define POSITION		DEBUG2
+#endif
+
+/*
+ * A B-Tree cannot possibly have this many levels, since there must be one
+ * block per level, which is bound by the range of BlockNumber:
+ */
+#define InvalidBtreeLevel	((uint32) InvalidBlockNumber)
+
+/*
+ * State associated with verifying a B-Tree index
+ */
+typedef struct BtreeCheckState
+{
+	/*
+	 * Unchanging state, established at start of verification:
+	 *
+	 * rel:                 B-Tree Index Relation
+	 * exclusivelock:       ExclusiveLock held on rel; else AccessShareLock
+	 * checkstrategy:       Buffer access strategy
+	 * targetcontext:       Target page memory context
+	 */
+	Relation				rel;
+	bool					exclusivelock;
+	BufferAccessStrategy 	checkstrategy;
+	MemoryContext			targetcontext;
+
+	/*
+	 * Mutable state, for verification of particular page:
+	 *
+	 * target:              Main target page
+	 * targetblock:         Main target page's block number
+	 * targetlsn:           Main target page's LSN
+	 *
+	 * target is the point of reference for a verification operation.
+	 *
+	 * Note: targetlsn is always from "target".  It is stashed here out of
+	 * convenience.
+	 *
+	 * Other B-Tree pages may be allocated, but those are always auxiliary
+	 * (e.g. they are target's child pages).  Conceptually, only the target
+	 * page is checked.  Each page found by verification's left/right,
+	 * top/bottom scan becomes the target exactly once.
+	 *
+	 * Memory is managed by resetting targetcontext after verification of some
+	 * target page finishes (possibly including target verification that
+	 * depends on non-target page state).
+	 */
+	Page					target;
+	BlockNumber				targetblock;
+	XLogRecPtr				targetlsn;
+
+} BtreeCheckState;
+
+/*
+ * Starting point for verifying an entire B-Tree index level
+ */
+typedef struct BtreeLevel
+{
+	/* Level number (0 is leaf page level). */
+	uint32			level;
+
+	/* Left most block on level.  Scan of level begins here. */
+	BlockNumber		leftmost;
+
+	/* Is this level reported as "true" root level by meta page? */
+	bool			istruerootlevel;
+} BtreeLevel;
+
+PG_FUNCTION_INFO_V1(bt_index_check);
+PG_FUNCTION_INFO_V1(bt_index_parent_check);
+
+static void btree_index_checkable(Relation rel);
+static void bt_check_every_level(Relation rel, bool exclusivelock);
+static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state,
+											   BtreeLevel level);
+static void bt_target_page_check(BtreeCheckState *state);
+static ScanKey bt_right_page_check_scankey(BtreeCheckState *state);
+static void bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
+							  ScanKey targetkey);
+static bool invariant_key_less_than_equal_offset(BtreeCheckState *state,
+												 ScanKey key,
+												 OffsetNumber upperbound);
+static bool invariant_key_greater_than_equal_offset(BtreeCheckState *state,
+													ScanKey key,
+													OffsetNumber lowerbound);
+static bool invariant_key_less_than_equal_nontarget_offset(BtreeCheckState *state,
+														   Page other,
+														   ScanKey key,
+														   OffsetNumber upperbound);
+static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum);
+
+/*
+ * bt_index_check(index regclass)
+ *
+ * Verify integrity of B-Tree index.
+ *
+ * Only acquires AccessShareLock on index relation.  Does not consider
+ * invariants that exist between parent/child pages.
+ */
+Datum
+bt_index_check(PG_FUNCTION_ARGS)
+{
+	Oid			relid = PG_GETARG_OID(0);
+	Relation	indrel;
+
+	CHECK_SUPERUSER();
+
+	indrel = relation_open(relid, AccessShareLock);
+
+	/* Relation suitable for checking as B-Tree? */
+	btree_index_checkable(indrel);
+
+	/* Check index */
+	bt_check_every_level(indrel, false);
+
+	relation_close(indrel, AccessShareLock);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * bt_index_parent_check(index regclass)
+ *
+ * Verify integrity of B-Tree index.
+ *
+ * Acquires ExclusiveLock on index relation, and ShareLock on the associated
+ * heap relation, a bit like REINDEX.  Verifies that downlinks in parent pages
+ * are valid lower bounds on child pages.
+ */
+Datum
+bt_index_parent_check(PG_FUNCTION_ARGS)
+{
+	Oid			indrelid = PG_GETARG_OID(0);
+	Oid			heapid;
+	Relation	indrel;
+	Relation	heaprel;
+
+	CHECK_SUPERUSER();
+
+	/*
+	 * We must lock table before index to avoid deadlocks.  However, if the
+	 * passed indrelid isn't an index then IndexGetRelation() will fail.
+	 * Rather than emitting a not-very-helpful error message, postpone
+	 * complaining, expecting that the is-it-an-index test below will fail.
+	 */
+	heapid = IndexGetRelation(indrelid, true);
+	if (OidIsValid(heapid))
+		heaprel = heap_open(heapid, ShareLock);
+	else
+		heaprel = NULL;
+
+	/*
+	 * Open the target index relations separately (like relation_openrv(), but
+	 * with heap relation locked first to prevent deadlocking).  In hot standby
+	 * mode this will raise an error.
+	 */
+	indrel = index_open(indrelid, ExclusiveLock);
+
+	/* Relation suitable for checking as B-Tree? */
+	btree_index_checkable(indrel);
+
+	/* Check index */
+	bt_check_every_level(indrel, true);
+
+	index_close(indrel, ExclusiveLock);
+	if (heaprel)
+		heap_close(heaprel, ShareLock);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * btree_index_checkable()
+ *
+ * Basic checks about the suitability of a relation for checking as a B-Tree
+ * index.
+ */
+static void
+btree_index_checkable(Relation rel)
+{
+	if (rel->rd_rel->relkind != RELKIND_INDEX ||
+		rel->rd_rel->relam != BTREE_AM_OID)
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("only nbtree access method indexes are supported"),
+				 errdetail("Relation \"%s\" is not a B-Tree index.",
+						   RelationGetRelationName(rel))));
+
+	if (RELATION_IS_OTHER_TEMP(rel))
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot access temporary tables of other sessions"),
+				 errdetail("Index \"%s\" is associated with temporary relation.",
+						   RelationGetRelationName(rel))));
+
+	if (!IndexIsValid(rel->rd_index))
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot check index \"%s\"",
+						RelationGetRelationName(rel)),
+				 errdetail("Index is not valid")));
+}
+
+/*
+ * bt_check_every_level()
+ *
+ * Main entry point for B-Tree SQL-callable functions.  Walks the B-Tree in
+ * logical order, verifying invariants as it goes.
+ *
+ * It is the caller's responsibility to acquire appropriate heavyweight lock on
+ * the index relation, and advise us if extra checks are safe when an
+ * ExclusiveLock is held.  An ExclusiveLock is generally assumed to prevent any
+ * kind of physical modification to the index structure, including
+ * modifications that VACUUM may make.
+ */
+static void
+bt_check_every_level(Relation rel, bool exclusivelock)
+{
+	BtreeCheckState	   *state;
+	Page				metapage;
+	BTMetaPageData	   *metad;
+	uint32				previouslevel;
+	BtreeLevel			current;
+
+	/*
+	 * RecentGlobalXmin assertion matches index_getnext_tid().  See note on
+	 * RecentGlobalXmin/B-Tree page deletion.
+	 */
+	Assert(TransactionIdIsValid(RecentGlobalXmin));
+
+	/*
+	 * Initialize state for entire verification operation
+	 */
+	state = palloc(sizeof(BtreeCheckState));
+	state->rel = rel;
+	state->exclusivelock = exclusivelock;
+	state->checkstrategy = GetAccessStrategy(BAS_BULKREAD);
+	/* Create context for page */
+	state->targetcontext = AllocSetContextCreate(CurrentMemoryContext,
+												 "amcheck page data",
+												 ALLOCSET_DEFAULT_MINSIZE,
+												 ALLOCSET_DEFAULT_INITSIZE,
+												 ALLOCSET_DEFAULT_MAXSIZE);
+
+	/* Get true root block from meta-page */
+	metapage = palloc_btree_page(state, BTREE_METAPAGE);
+	metad = BTPageGetMeta(metapage);
+
+	/*
+	 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
+	 * the fast root and true root differ.
+	 *
+	 * Start from the true root, not the fast root, unlike conventional index
+	 * scans.  This approach is more thorough, and removes the risk of
+	 * following a stale fast root from the meta page.
+	 */
+	if (metad->btm_fastroot != metad->btm_root)
+		ereport(CONCERN,
+				(errcode(ERRCODE_DUPLICATE_OBJECT),
+				 errmsg("fast root mismatch in index %s",
+						RelationGetRelationName(rel)),
+				 errdetail_internal("Fast block %u (level %u) "
+									"differs from true root "
+									"block %u (level %u).",
+									metad->btm_fastroot, metad->btm_fastlevel,
+									metad->btm_root, metad->btm_level)));
+
+	/*
+	 * Starting at the root, verify every level.  Move left to right, top to
+	 * bottom.  Note that there may be no pages other than the meta page (meta
+	 * page can indicate that root is P_NONE when the index is totally empty).
+	 */
+	previouslevel = InvalidBtreeLevel;
+	current.level = metad->btm_level;
+	current.leftmost = metad->btm_root;
+	current.istruerootlevel =  true;
+	while (current.leftmost != P_NONE)
+	{
+		/*
+		 * Verify this level, and get left most page for next level down, if
+		 * not at leaf level
+		 */
+		current = bt_check_level_from_leftmost(state, current);
+
+		if (current.leftmost == InvalidBlockNumber)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("index \"%s\" has no valid pages on level below %u or first level",
+							RelationGetRelationName(rel), previouslevel)));
+
+		previouslevel = current.level;
+	}
+
+	/* Be tidy: */
+	MemoryContextDelete(state->targetcontext);
+}
+
+/*
+ * bt_check_level_from_leftmost()
+ *
+ * Given a left-most block at some level, move right, verifying each page
+ * individually (with more verification across pages for "exclusivelock"
+ * callers).  Caller should pass the true root page as the leftmost initially,
+ * working their way down by passing what is returned for the last call here
+ * until level 0 (leaf page level) was reached.
+ *
+ * Returns state for next call, if any.  This includes left-most block number
+ * one level lower that should be passed on next level/call, which is set to
+ * P_NONE on last call here (when leaf level is verified).  Level numbers
+ * follow the nbtree convention: higher levels have higher numbers, because new
+ * levels are added only due to a root page split.  Note that prior to the
+ * first root page split, the root is also a leaf page, so there is always a
+ * level 0 (leaf level), and it's always the last level processed.
+ *
+ * Note on memory management:  State's per-page context is reset here, between
+ * each call to bt_target_page_check().
+ */
+static BtreeLevel
+bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
+{
+	/* State to establish early, concerning entire level */
+	BTPageOpaque	opaque;
+	MemoryContext 	oldcontext;
+	BtreeLevel		nextleveldown;
+
+	/* Variables for iterating across level using right links */
+	BlockNumber		leftcurrent = P_NONE;
+	BlockNumber		current = level.leftmost;
+
+	/* Initialize return state */
+	nextleveldown.leftmost = InvalidBlockNumber;
+	nextleveldown.level = InvalidBtreeLevel;
+	nextleveldown.istruerootlevel = false;
+
+	/* Use page-level context for duration of this call */
+	oldcontext = MemoryContextSwitchTo(state->targetcontext);
+
+	elog(POSITION, "verifying level %u%s", level.level,
+		 level.istruerootlevel?
+		 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
+
+	do
+	{
+		/* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
+		CHECK_FOR_INTERRUPTS();
+
+		/* Initialize state for this iteration */
+		state->targetblock = current;
+		state->target = palloc_btree_page(state, state->targetblock);
+		state->targetlsn = PageGetLSN(state->target);
+
+		opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+		if (P_IGNORE(opaque))
+		{
+			if (P_RIGHTMOST(opaque))
+				ereport(CORRUPTION,
+						(errcode(ERRCODE_INDEX_CORRUPTED),
+						 errmsg("block %u fell off the end of index \"%s\"",
+								current, RelationGetRelationName(state->rel))));
+			else
+				ereport(CONCERN,
+						(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+						 errmsg("block %u of index \"%s\" ignored",
+								current, RelationGetRelationName(state->rel))));
+			goto nextpage;
+		}
+		else if (nextleveldown.leftmost == InvalidBlockNumber)
+		{
+			/*
+			 * A concurrent page split could make the caller supplied leftmost
+			 * block no longer contain the leftmost page, or no longer be the
+			 * true root, but where that isn't possible due to heavyweight
+			 * locking, check that the first valid page meets caller's
+			 * expectations.
+			 */
+			if (state->exclusivelock)
+			{
+				if (!P_LEFTMOST(opaque))
+					ereport(CORRUPTION,
+							(errcode(ERRCODE_INDEX_CORRUPTED),
+							 errmsg("block %u is not leftmost in index \"%s\"",
+									current, RelationGetRelationName(state->rel))));
+
+				if (level.istruerootlevel && !P_ISROOT(opaque))
+					ereport(CORRUPTION,
+							(errcode(ERRCODE_INDEX_CORRUPTED),
+							 errmsg("block %u is not true root in index \"%s\"",
+									current, RelationGetRelationName(state->rel))));
+			}
+
+			/*
+			 * Before beginning any non-trivial examination of level, establish
+			 * state to be passed by caller for next call here, if this isn't
+			 * last call/leaf level.
+			 *
+			 * There should be at least one non-ignorable page per level.
+			 */
+			if (!P_ISLEAF(opaque))
+			{
+				IndexTuple		itup;
+				ItemId			itemid;
+
+				/* Internal page -- downlink gets leftmost on next level */
+				itemid = PageGetItemId(state->target, P_FIRSTDATAKEY(opaque));
+				itup = (IndexTuple) PageGetItem(state->target, itemid);
+				nextleveldown.leftmost = ItemPointerGetBlockNumber(&(itup->t_tid));
+				nextleveldown.level = opaque->btpo.level - 1;
+			}
+			else
+			{
+				/*
+				 * Leaf page -- final level caller must process.
+				 *
+				 * Note that this could also be the root page, if there has
+				 * been no root page split yet.
+				 */
+				nextleveldown.leftmost = P_NONE;
+				nextleveldown.level = InvalidBtreeLevel;
+			}
+
+			/*
+			 * Finished setting up state for this call/level.  Control will
+			 * never end up back here in any future loop iteration for this
+			 * level.
+			 */
+		}
+
+		if (state->exclusivelock && opaque->btpo_prev != leftcurrent)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("right link/left link pair in index \"%s\" not in mutual agreement",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Deleted block=%u left block=%u link reported block=%u.",
+										current, leftcurrent, opaque->btpo_prev)));
+
+		/* Verify invariants for page -- all important checks occur here */
+		bt_target_page_check(state);
+
+nextpage:
+
+		/* Try to detect circular links */
+		if (current == leftcurrent || current == opaque->btpo_prev)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("circular link chain found in block %u of index \"%s\"",
+							current, RelationGetRelationName(state->rel))));
+
+		leftcurrent = current;
+		current = opaque->btpo_next;
+
+		/* Free page and associated memory for this iteration */
+		MemoryContextReset(state->targetcontext);
+	}
+	while (current != P_NONE);
+
+	/* Don't change context for caller */
+	MemoryContextSwitchTo(oldcontext);
+
+	return nextleveldown;
+}
+
+/*
+ * bt_target_page_check()
+ *
+ * Function performs the following checks on target page, or pages ancillary to
+ * target page:
+ *
+ * - That every "real" data item is less than or equal to the high key, which
+ *   is an upper bound on the items on the pages (where there is a high key at
+ *   all -- pages that are rightmost lack one).
+ *
+ * - That within the page, every "real" item is less than or equal to the item
+ *   immediately to its right, if any (i.e., that the items are in order within
+ *   the page, so that the binary searches performed by index scans are sane).
+ *
+ * - That the last item stored on the page is less than or equal to the first
+ *   "real" data item on the page to the right (if such a first item is
+ *   available).
+ *
+ * Furthermore, when state passed shows ExclusiveLock held, and target page is
+ * internal page, function also checks:
+ *
+ * - That all child pages respect downlinks lower bound.
+ *
+ * Note:  This routine is not especially proactive in freeing memory.  High
+ * watermark memory consumption is bound to some small fixed multiple of
+ * BLCKSZ, though.  Caller should reset the current context between calls here.
+ */
+static void
+bt_target_page_check(BtreeCheckState *state)
+{
+	OffsetNumber	offset;
+	OffsetNumber	max;
+	BTPageOpaque	topaque;
+
+	topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+	max = PageGetMaxOffsetNumber(state->target);
+
+	elog(POSITION, "verifying %u items on %s block %u", max,
+		 P_ISLEAF(topaque) ? "leaf":"internal", state->targetblock);
+
+	/*
+	 * Loop over page items, but don't start from P_HIKEY (don't have iteration
+	 * directly considering high key item, if any).  That's something that is
+	 * used as part of verifying all other items, but doesn't get its own
+	 * iteration.
+	 */
+	for (offset = P_FIRSTDATAKEY(topaque);
+		 offset <= max;
+		 offset = OffsetNumberNext(offset))
+	{
+		ItemId		itemid;
+		IndexTuple	itup;
+		ScanKey		skey;
+
+		CHECK_FOR_INTERRUPTS();
+
+		/* Don't try to generate scankey using "minus infinity" garbage data */
+		if (OFFSET_IS_MINUS_INFINITY(topaque, offset))
+			continue;
+
+		/* Build insertion scankey for current page offset */
+		itemid = PageGetItemId(state->target, offset);
+		itup = (IndexTuple) PageGetItem(state->target, itemid);
+		skey = _bt_mkscankey(state->rel, itup);
+
+		/*
+		 *   ********************
+		 *   * High key check   *
+		 *   ********************
+		 *
+		 * If there is a high key, which there must be for a non-rightmost
+		 * page, check that it actually is upper bound on all page items.
+		 *
+		 * We prefer to check all items, rather than checking just the first
+		 * and trusting that the operator class obeys the transitive law (which
+		 * implies that all subsequent items also respected the high key
+		 * invariant if they pass the item order check).
+		 *
+		 * Ideally, we'd compare every item in the index against every other
+		 * item in the index, and not trust opclass obedience of the transitive
+		 * law to bridge the gap between children and their grandparents (as
+		 * well as great-grandparents, and so on).  We don't go to those
+		 * lengths because that would be prohibitively expensive, and probably
+		 * not markedly more effective in practice.
+		 */
+		if (!P_RIGHTMOST(topaque) &&
+			!invariant_key_less_than_equal_offset(state, skey, P_HIKEY))
+		{
+			char	   *itid,  *htid;
+
+			itid = psprintf("(%u,%u)", state->targetblock, offset);
+			htid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("high key invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Index tid=%s points to %s tid=%s "
+										"page lsn=%X/%X.",
+										itid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										htid,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+		}
+
+		/*
+		 *   ********************
+		 *   * Item order check *
+		 *   ********************
+		 *
+		 * Check that items are stored on page in logical order, by checking
+		 * current item is less than or equal to next item (if any).
+		 */
+		if (OffsetNumberNext(offset) <= max &&
+			!invariant_key_less_than_equal_offset(state, skey,
+												  OffsetNumberNext(offset)))
+		{
+			char	   *itid,  *htid,
+					   *nitid, *nhtid;
+
+			itid = psprintf("(%u,%u)", state->targetblock, offset);
+			htid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+			nitid = psprintf("(%u,%u)", state->targetblock,
+							 OffsetNumberNext(offset));
+
+			/* Reuse itup to get pointed-to heap location of second item */
+			itemid = PageGetItemId(state->target, OffsetNumberNext(offset));
+			itup = (IndexTuple) PageGetItem(state->target, itemid);
+			nhtid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("item order invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Lower index tid=%s (points to %s tid=%s) "
+										"higher index tid=%s (points to %s tid=%s) "
+										"page lsn=%X/%X.",
+										itid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										htid,
+										nitid,
+										P_ISLEAF(topaque) ? "heap":"index",
+										nhtid,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+		}
+
+		/*
+		 *   ********************
+		 *   * Last item check  *
+		 *   ********************
+		 *
+		 * Check last item against next/right page's first data item's when
+		 * last item on page is reached.  This additional check can detect
+		 * transposed pages.
+		 *
+		 * This check is similar to the item order check that will have already
+		 * been performed for every other "real" item on target page when last
+		 * item is checked.  The difference is that the next item (the item
+		 * that is compared to target's last item) needs to come from the
+		 * next/sibling page.  There may not be such an item available from
+		 * sibling for various reasons, though (e.g., target is the rightmost
+		 * page on level).
+		 */
+		else if (offset == max)
+		{
+			ScanKey		rightkey;
+
+			/* Get item in next/right page */
+			rightkey = bt_right_page_check_scankey(state);
+
+			if (rightkey &&
+				!invariant_key_greater_than_equal_offset(state, rightkey, max))
+			{
+				/*
+				 * As explained at length in bt_right_page_check_scankey(),
+				 * there is a known !exclusivelock race that could account for
+				 * apparent violation of invariant, which we must check for
+				 * before actually proceeding with raising error.  Our canary
+				 * condition is that target page was deleted.
+				 */
+				if (!state->exclusivelock)
+				{
+					/* Get fresh copy of target page */
+					state->target = palloc_btree_page(state, state->targetblock);
+					/* Note that we deliberately do not update target LSN */
+					topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+					/* All !exclusivelock checks now performed; just return */
+					if (P_IGNORE(topaque))
+						return;
+				}
+
+				ereport(CORRUPTION,
+						(errcode(ERRCODE_INDEX_CORRUPTED),
+						 errmsg("cross page item order invariant violated for index \"%s\"",
+								RelationGetRelationName(state->rel)),
+						 errdetail_internal("Last item on page tid=(%u,%u) "
+											"page lsn=%X/%X.",
+											state->targetblock, offset,
+											(uint32) (state->targetlsn >> 32),
+											(uint32) state->targetlsn)));
+			}
+		}
+
+		/*
+		 *   ********************
+		 *   * Downlink check   *
+		 *   ********************
+		 *
+		 * Additional check of child items iff this is an internal page and
+		 * caller holds an ExclusiveLock.  This happens for every downlink
+		 * (item) in target excluding the minus-infinity downlink (again, this
+		 * is because it has no useful value to compare).
+		 */
+		if (!P_ISLEAF(topaque) && state->exclusivelock)
+		{
+			BlockNumber childblock = ItemPointerGetBlockNumber(&(itup->t_tid));
+
+			bt_downlink_check(state, childblock, skey);
+		}
+	}
+}
+
+/*
+ * bt_right_page_check_scankey()
+ *
+ * Return a scankey for an item on page to right of current target (or the
+ * first non-ignorable page), sufficient to check ordering invariant on last
+ * item in current target page.  Returned scankey relies on local memory
+ * allocated for the child page, which caller cannot pfree().  Caller's memory
+ * context should be reset between calls here.
+ *
+ * This is the first data item, and so all adjacent items are checked against
+ * their immediate sibling item (which may be on a sibling page, or even a
+ * "cousin" page at parent boundaries where target's rightlink points to page
+ * with different parent page).  If no such valid item is available, return
+ * NULL instead.
+ *
+ * Note that !exclusivelock callers must reverify that target page has not been
+ * concurrently deleted.
+ */
+static ScanKey
+bt_right_page_check_scankey(BtreeCheckState *state)
+{
+	BTPageOpaque	opaque;
+	ItemId			rightitem;
+	BlockNumber		targetnext;
+	Page			rightpage;
+	OffsetNumber	nline;
+
+	/* Determine target's next block number */
+	opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+	/* If target is already rightmost, no right sibling; nothing to do here */
+	if (P_RIGHTMOST(opaque))
+		return NULL;
+
+	/*
+	 * General notes on concurrent page splits and page deletion:
+	 *
+	 * Routines like _bt_search() don't require *any* page split interlock when
+	 * descending the tree, including something very light like a buffer pin.
+	 * That's why it's okay that we don't either.  This avoidance of any need
+	 * to "couple" buffer locks is the raison d' etre of the Lehman & Yao
+	 * algorithm, in fact.
+	 *
+	 * That leaves deletion.  A deleted page won't actually be recycled by
+	 * VACUUM early enough for us to fail to at least follow its right link (or
+	 * left link, or downlink) and find its sibling, because recycling does not
+	 * occur until no possible index scan could land on the page.  Index scans
+	 * can follow links with nothing more than their snapshot as an interlock
+	 * and be sure of at least that much.  (See page recycling/RecentGlobalXmin
+	 * notes in nbtree README.)
+	 *
+	 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
+	 * dead (ignorable) page one or more times.  There will either be a further
+	 * right link to follow that leads to a live page before too long (before
+	 * passing by parent's rightmost child), or we will find the end of the
+	 * entire level instead (possible when parent page is itself the rightmost
+	 * on its level).
+	 */
+	targetnext = opaque->btpo_next;
+	for (;;)
+	{
+		CHECK_FOR_INTERRUPTS();
+
+		rightpage = palloc_btree_page(state, targetnext);
+		opaque = (BTPageOpaque) PageGetSpecialPointer(rightpage);
+
+		if (!P_IGNORE(opaque) || P_RIGHTMOST(opaque))
+			break;
+
+		/* We landed on a deleted page, so step right to find a live page */
+		targetnext = opaque->btpo_next;
+		ereport(CONCERN,
+				(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+				 errmsg("level %u leftmost page of index \"%s\" was found deleted or half dead",
+						opaque->btpo.level, RelationGetRelationName(state->rel)),
+				 errdetail_internal("Deleted page found when building scankey from right sibling.")));
+
+		/* Be slightly more pro-active in freeing this memory, just in case */
+		pfree(rightpage);
+	}
+
+	/*
+	 * No ExclusiveLock held case -- why it's safe to proceed.
+	 *
+	 * Problem:
+	 *
+	 * We must avoid false positive reports of corruption when caller treats
+	 * item returned here as an upper bound on target's last item.  In general,
+	 * false positives are disallowed.  Ensuring they don't happen in
+	 * !exclusivelock case is subtle.
+	 *
+	 * A concurrent page deletion by VACUUM of the target page can result in
+	 * the insertion of items on to this right sibling page that would
+	 * previously have been inserted on our target page.  There might have been
+	 * insertions that followed target's downlink after it was made to point to
+	 * right sibling instead of target by page deletion's first phase.  The
+	 * inserters insert items that would belong on target page.  This race is
+	 * very tight, but it's possible.  This is our only problem.
+	 *
+	 * Non-problems:
+	 *
+	 * We are not hindered by a concurrent page split of the target; we'll
+	 * never land on the second half of the page anyway.  A concurrent split of
+	 * the right page will also not matter, because the first data item remains
+	 * the same within the left half, which we'll reliably land on.  If we had
+	 * to skip over ignorable/deleted pages, it cannot matter because their key
+	 * space has already been atomically merged with the first non-ignorable
+	 * page we eventually find (doesn't matter whether the page we eventually
+	 * find is a true sibling or a cousin of target, which we go into below).
+	 *
+	 * Solution:
+	 *
+	 * Caller knows that it should reverify that target is not ignorable
+	 * (half-dead or deleted) when cross-page sibling item comparison appears
+	 * to indicate corruption (invariant fails).  This detects the single race
+	 * condition that exists for caller.  This is correct because the continued
+	 * existence of target block as non-ignorable (not half-dead or deleted)
+	 * implies that target page was not merged into from the right by deletion;
+	 * the key space at or after target never moved left.  Target's parent
+	 * either has the same downlink to target as before, or a <= downlink due
+	 * to deletion at the left of target.  Target either has the same highkey
+	 * as before, or a highkey <= before when there is a page split. (The
+	 * rightmost concurrently-split-from-target-page page will still have the
+	 * same highkey as target was originally found to have, which for our
+	 * purposes is equivalent to target's highkey itself never changing, since
+	 * we reliably skip over concurrently-split-from-target-page pages.)
+	 *
+	 * In simpler terms, we allow that the key space of the target may expand
+	 * left (the key space can move left on the left side of target only), but
+	 * the target key space cannot expand right and get ahead of us without our
+	 * detecting it.  The key space of the target cannot shrink, unless it
+	 * shrinks to zero due to the deletion of the original page, our canary
+	 * condition.  (To be very precise, we're a bit stricter than that because
+	 * it might just have been that the target page split and only the original
+	 * target page was deleted.  We can be more strict, just not more lax.)
+	 *
+	 * Top level tree walk caller moves on to next page (makes it the new
+	 * target) following recovery from this race.  (cf.  The rationale for
+	 * child/downlink verification needing an ExclusiveLock within
+	 * bt_downlink_check(), where page deletion is also the main source of
+	 * trouble.)
+	 *
+	 * Note that it doesn't matter if right sibling page here is actually a
+	 * cousin page, because in order for the key space to be readjusted in a
+	 * way that causes us issues in next level up (guiding problematic
+	 * concurrent insertions to the cousin from the grandparent rather than to
+	 * the sibling from the parent), there'd have to be page deletion of
+	 * target's parent page (affecting target's parent's downlink in target's
+	 * grandparent page).  Internal page deletion only occurs when there are no
+	 * child pages (they were all fully deleted), and caller is checking that
+	 * the target's parent has at least one non-deleted (so non-ignorable)
+	 * child: the target page.  (Note that the first phase of deletion
+	 * atomically marks the page to be deleted half-dead/ignorable at the same
+	 * time downlink in its parent is removed, so caller will definitely not
+	 * fail to detect that this happened.)
+	 *
+	 * This trick is inspired by the method backward scans use for dealing with
+	 * concurrent page splits; concurrent page deletion is a problem that
+	 * similarly receives special consideration sometimes (it's possible that
+	 * the backwards scan will re-read its "original" block after failing to
+	 * find a right-link to it, having already moved in the opposite direction
+	 * (right/"forwards") a few times to try to locate one).  Just like us,
+	 * that happens only to determine if there was a concurrent page deletion
+	 * of a reference page, and just like us if there was a page deletion of
+	 * that reference page it means we can move on from caring about the
+	 * reference page.  See the nbtree README for a full description of how
+	 * that works.
+	 */
+	nline = PageGetMaxOffsetNumber(rightpage);
+
+	/*
+	 * Get first data item, if any
+	 */
+	if (P_ISLEAF(opaque) && nline >= P_FIRSTDATAKEY(opaque))
+	{
+		/* Return first data item (if any) */
+		rightitem = PageGetItemId(rightpage, P_FIRSTDATAKEY(opaque));
+	}
+	else if (!P_ISLEAF(opaque) &&
+			 nline >= OffsetNumberNext(P_FIRSTDATAKEY(opaque)))
+	{
+		/* Return first item after the internal page's "minus infinity" item */
+		rightitem = PageGetItemId(rightpage,
+								  OffsetNumberNext(P_FIRSTDATAKEY(opaque)));
+	}
+	else
+	{
+		/*
+		 * No first item.  Page is probably empty leaf page, but it's also
+		 * possible that it's an internal page with only a minus infinity item.
+		 */
+		ereport(CONCERN,
+				(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
+				 errmsg("%s block %u of index \"%s\" has no first data item",
+						P_ISLEAF(opaque) ? "leaf":"internal", targetnext,
+						RelationGetRelationName(state->rel))));
+		return NULL;
+	}
+
+	/*
+	 * Return first real item scankey.  Note that this relies on right page
+	 * memory remaining allocated.
+	 */
+	return _bt_mkscankey(state->rel,
+						 (IndexTuple) PageGetItem(rightpage, rightitem));
+}
+
+/*
+ * bt_downlink_check()
+ *
+ * Checks one of target's downlink against its child page.
+ *
+ * Conceptually, the target page continues to be what is checked here.  The
+ * target block is still blamed in the event of finding an invariant violation.
+ * The downlink insertion into the target is probably where any problem raised
+ * here arises, and there is no such thing as a parent link, so doing the
+ * verification this way around is much more practical.
+ */
+static void
+bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
+				  ScanKey targetkey)
+{
+	OffsetNumber	offset;
+	OffsetNumber	maxoffset;
+	Page			child;
+	BTPageOpaque	copaque;
+
+	/*
+	 * Caller must have ExclusiveLock on target relation, because of
+	 * considerations around page deletion by VACUUM.
+	 *
+	 * N.B.: In general, page deletion deletes the right sibling's downlink,
+	 * not the downlink of the page being deleted; the deleted page's downlink
+	 * is reused for its sibling.  The key space is thereby consolidated
+	 * between the deleted page and its right sibling.  (We cannot delete a
+	 * parent page's rightmost child unless it is the last child page, and we
+	 * intend to also delete the parent itself.)
+	 *
+	 * If this verification happened without an ExclusiveLock, the following
+	 * race condition could cause false positives:
+	 *
+	 * In general, concurrent page deletion might occur, including deletion of
+	 * the left sibling of the child page that is examined here.  If such a
+	 * page deletion were to occur, closely followed by an insertion into the
+	 * newly expanded key space of the child, a window for the false positive
+	 * opens up: the stale parent/target downlink originally followed to get to
+	 * the child legitimately ceases to be a lower bound on all items in the
+	 * page, since the key space was concurrently expanded "left". (Insertion
+	 * followed the "new" downlink for the child, not our now-stale downlink,
+	 * which was concurrently physically removed in target/parent as part of
+	 * deletion's first phase.)
+	 *
+	 * Note that while the cross-page-same-level last item check uses a trick
+	 * that allows it to perform verification for !exclusivelock callers, a
+	 * similar trick seems difficult here.  The trick that that other check
+	 * uses is, in essence, to lock down race conditions to those that occur
+	 * due to concurrent page deletion of the target; that's a race that can be
+	 * reliably detected before actually reporting corruption.
+	 *
+	 * On the other hand, we'd need to lock down race conditions involving
+	 * deletion of child's left page, for long enough to read the child page
+	 * into memory (in other words, a scheme with concurrently held buffer
+	 * locks on both child and left-of-child pages).  That's unacceptable for
+	 * amcheck functions on general principle, though.
+	 */
+	Assert(state->exclusivelock);
+
+	/*
+	 * Verify child page has the downlink key from target page (its parent) as
+	 * a lower bound.
+	 *
+	 * We prefer to check all items, rather than checking just the first and
+	 * trusting that the operator class obeys the transitive law.
+	 */
+	child = palloc_btree_page(state, childblock);
+	copaque = (BTPageOpaque) PageGetSpecialPointer(child);
+	maxoffset = PageGetMaxOffsetNumber(child);
+
+	for (offset = P_FIRSTDATAKEY(copaque);
+		 offset <= maxoffset;
+		 offset = OffsetNumberNext(offset))
+	{
+		/*
+		 * Skip comparison of target page key against "minus infinity" item, if
+		 * any.  Checking it would indicate that it's not an upper bound, but
+		 * that's only because of the hard-coding within _bt_compare().
+		 */
+		if (OFFSET_IS_MINUS_INFINITY(copaque, offset))
+			continue;
+
+		if (!invariant_key_less_than_equal_nontarget_offset(state, child,
+															targetkey, offset))
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("down-link lower bound invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Parent block=%u child index tid=(%u,%u) "
+										"parent page lsn=%X/%X.",
+										state->targetblock, childblock, offset,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+	}
+
+	pfree(child);
+}
+
+/*
+ * invariant_key_less_than_equal_offset()
+ *
+ * Does the invariant hold that the key is less than or equal to a given upper
+ * bound offset item?
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_less_than_equal_offset(BtreeCheckState *state, ScanKey key,
+									 OffsetNumber upperbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, state->target, upperbound);
+
+	return cmp <= 0;
+}
+
+/*
+ * invariant_key_greater_than_equal_offset()
+ *
+ * Does the invariant hold that the key is greater than or equal to a given
+ * lower bound offset item?
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_greater_than_equal_offset(BtreeCheckState *state, ScanKey key,
+										OffsetNumber lowerbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, state->target, lowerbound);
+
+	return cmp >= 0;
+}
+
+/*
+ * invariant_key_less_than_equal_nontarget_offset()
+ *
+ * Does the invariant hold that the key is less than or equal to a given upper
+ * bound offset item, with the offset relating to a caller-supplied page that
+ * is not the current target page? Caller's non-target page is typically a
+ * child page of the target, checked as part of checking a property of the
+ * target page (i.e. the key comes from the target).
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static bool
+invariant_key_less_than_equal_nontarget_offset(BtreeCheckState *state,
+											   Page nontarget, ScanKey key,
+											   OffsetNumber upperbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, nontarget, upperbound);
+
+	return cmp <= 0;
+}
+
+/*
+ * palloc_btree_page()
+ *
+ * Given a block number of a B-Tree page, return page in palloc()'d memory.
+ * While at it, perform some basic checks of the page.
+ *
+ * There is never an attempt to get a consistent view of multiple pages using
+ * multiple concurrent buffer locks; in general, we prefer to have only one pin
+ * and buffer lock at a time, which is often all that the nbtree code requires.
+ *
+ * Operating on a copy of the page is useful because it prevents control
+ * getting stuck in an uninterruptible state when an underlying operator class
+ * misbehaves.
+ */
+static Page
+palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum)
+{
+	Buffer			buffer;
+	Page			page;
+	BTPageOpaque	opaque;
+
+	page = palloc(BLCKSZ);
+
+	/*
+	 * We copy the page into local storage to avoid holding pin on the buffer
+	 * longer than we must.
+	 */
+	buffer = ReadBufferExtended(state->rel, MAIN_FORKNUM, blocknum, RBM_NORMAL,
+								state->checkstrategy);
+	LockBuffer(buffer, BT_READ);
+
+	/*
+	 * Perform the same basic sanity checking that nbtree itself performs for
+	 * every page:
+	 */
+	_bt_checkpage(state->rel, buffer);
+
+	/* Only use copy of page in palloc()'d memory */
+	memcpy(page, BufferGetPage(buffer), BLCKSZ);
+	UnlockReleaseBuffer(buffer);
+
+	opaque = (BTPageOpaque) PageGetSpecialPointer(page);
+
+	if (opaque->btpo_flags & BTP_META && blocknum != BTREE_METAPAGE)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid meta page found at block %u in index \"%s\"",
+						blocknum, RelationGetRelationName(state->rel))));
+
+	/* Check page from block that ought to be meta page */
+	if (blocknum == BTREE_METAPAGE)
+	{
+		BTMetaPageData *metad = BTPageGetMeta(page);
+
+		if (!(opaque->btpo_flags & BTP_META) ||
+			metad->btm_magic != BTREE_MAGIC)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("index \"%s\" meta page is corrupt",
+							RelationGetRelationName(state->rel))));
+
+		if (metad->btm_version != BTREE_VERSION)
+			ereport(CORRUPTION,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("version mismatch in index \"%s\": file version %d, code version %d",
+							RelationGetRelationName(state->rel),
+							metad->btm_version, BTREE_VERSION)));
+	}
+
+	/*
+	 * Deleted pages have no sane "level" field, so can only check non-deleted
+	 * page level
+	 */
+	if (P_ISLEAF(opaque) && !P_ISDELETED(opaque) && opaque->btpo.level != 0)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid leaf page level %u for block %u in index \"%s\"",
+						opaque->btpo.level, blocknum, RelationGetRelationName(state->rel))));
+
+	if (blocknum != BTREE_METAPAGE && !P_ISLEAF(opaque) &&
+		!P_ISDELETED(opaque) && opaque->btpo.level == 0)
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid internal page level 0 for block %u in index \"%s\"",
+						opaque->btpo.level, RelationGetRelationName(state->rel))));
+
+	if (!P_ISLEAF(opaque) && P_HAS_GARBAGE(opaque))
+		ereport(CORRUPTION,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("internal page block %u in index \"%s\" has garbage items",
+						blocknum, RelationGetRelationName(state->rel))));
+
+	return page;
+}
diff --git a/doc/src/sgml/amcheck.sgml b/doc/src/sgml/amcheck.sgml
new file mode 100644
index 0000000..58bd0bd
--- /dev/null
+++ b/doc/src/sgml/amcheck.sgml
@@ -0,0 +1,275 @@
+<!-- doc/src/sgml/amcheck.sgml -->
+
+<sect1 id="amcheck" xreflabel="amcheck">
+ <title>amcheck</title>
+
+ <indexterm zone="amcheck">
+  <primary>amcheck</primary>
+ </indexterm>
+
+ <para>
+  The <filename>amcheck</> module provides functions that allow you to
+  verify the logical consistency of the structure of indexes.  If the
+  structure appears to be valid, no error is raised.
+ </para>
+
+ <para>
+  The functions verify various <emphasis>invariants</> in the
+  structure of the representation of particular indexes.  The
+  correctness of the access method functions behind index scans and
+  other important operations relies on these invariants always
+  holding.  For example, certain functions verify, among other things,
+  that all B-Tree pages have items in <quote>logical</> order (e.g.,
+  for B-Tree indexes on <type>text</>, index tuples should be in
+  collated lexical order).  If that particular invariant somehow fails
+  to hold, we can expect binary searches on the affected page to
+  incorrectly guide index scans, resulting in wrong answers to SQL
+  queries.  Problems like this can be very subtle.
+ </para>
+ <para>
+  Verification is performed using the same procedures as those used by
+  index scans themselves, which may be user-defined operator class
+  code.  For example, B-Tree index verification relies on comparisons
+  made with one or more B-Tree support function 1 routines.  See <xref
+  linkend="xindex-support"> for details of operator class support
+  functions.
+ </para>
+ <para>
+  <filename>amcheck</> functions may be used only by superusers.
+ </para>
+
+ <sect2>
+  <title>Functions</title>
+
+  <variablelist>
+   <varlistentry>
+    <term>
+     <function>bt_index_check(index regclass) returns void</function>
+     <indexterm>
+      <primary>bt_index_check</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>bt_index_check</function> tests that its target, a
+      B-Tree index, respects a variety of invariants.  Example usage:
+<screen>
+test=# SELECT bt_index_check(c.oid), c.relname, c.relpages
+FROM pg_index i
+JOIN pg_opclass op ON i.indclass[0] = op.oid
+JOIN pg_am am ON op.opcmethod = am.oid
+JOIN pg_class c ON i.indexrelid = c.oid
+JOIN pg_namespace n ON c.relnamespace = n.oid
+WHERE am.amname = 'btree' AND n.nspname = 'pg_catalog'
+-- Don't check temp tables, which may be from another session:
+AND c.relpersistence != 't'
+-- Function may throw an error when this is omitted:
+AND i.indisready AND i.indisvalid
+ORDER BY c.relpages DESC LIMIT 10;
+ bt_index_check |             relname             | relpages 
+----------------+---------------------------------+----------
+                | pg_depend_reference_index       |       43
+                | pg_depend_depender_index        |       40
+                | pg_proc_proname_args_nsp_index  |       31
+                | pg_description_o_c_o_index      |       21
+                | pg_attribute_relid_attnam_index |       14
+                | pg_proc_oid_index               |       10
+                | pg_attribute_relid_attnum_index |        9
+                | pg_amproc_fam_proc_index        |        5
+                | pg_amop_opr_fam_index           |        5
+                | pg_amop_fam_strat_index         |        5
+(10 rows)
+</screen>
+      This example shows a session that performs verification of every
+      catalog index in the database <quote>test</>.  Details of just
+      the 10 largest indexes verified are displayed.  Since no error
+      is raised, all indexes tested appear to be logically consistent.
+      Naturally, this query could easily be changed to call
+      <function>bt_index_check</function> for every index in the
+      database where verification is supported.
+     </para>
+     <para>
+      An <literal>AccessShareLock</> is acquired on the target index
+      by <function>bt_index_check</function>.  This lock mode is the
+      same lock mode acquired on relations by simple
+      <literal>SELECT</> statements.
+      <function>bt_index_check</function> does not verify invariants
+      that span child/parent relationships, nor does it verify that
+      the target index is consistent with its heap relation.  When a
+      routine, lightweight test for corruption is required in a live
+      production environment, using
+      <function>bt_index_check</function> often provides the best
+      trade-off between thoroughness of verification and limiting the
+      impact on application performance and availability.
+     </para>
+    </listitem>
+   </varlistentry>
+
+   <varlistentry>
+    <term>
+     <function>bt_index_parent_check(index regclass) returns void</function>
+     <indexterm>
+      <primary>bt_index_parent_check</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>bt_index_parent_check</function> tests that its
+      target, a B-Tree index, respects a variety of invariants.  The
+      checks performed by <function>bt_index_parent_check</function>
+      are a superset of the checks performed by
+      <function>bt_index_check</function>.
+      <function>bt_index_parent_check</function> can be thought of as
+      a more thorough variant of <function>bt_index_check</function>:
+      unlike <function>bt_index_check</function>,
+      <function>bt_index_parent_check</function> also checks
+      invariants that span parent/child relationships.  However, it
+      does not verify that the target index is consistent with its
+      heap relation.  <function>bt_index_parent_check</function>
+      follows the general convention of raising an error if it finds a
+      logical inconsistency or other problem.
+     </para>
+     <para>
+      An <literal>ExclusiveLock</> is required on the target index by
+      <function>bt_index_parent_check</function> (a
+      <literal>ShareLock</> is also acquired on the heap relation).
+      These locks prevent concurrent data modification from
+      <command>INSERT</>, <command>UPDATE</>, and <command>DELETE</>
+      commands.  The locks also prevent the underlying relation from
+      being concurrently processed by <command>VACUUM</> (and certain
+      other utility commands).  Note that the function holds locks for
+      as short a duration as possible, so there is no advantage to
+      verifying each index individually in a series of transactions,
+      unless long running queries happen to be of particular concern.
+     </para>
+     <para>
+      <function>bt_index_parent_check</function>'s additional
+      verification is more likely to detect various pathological
+      cases.  These cases may involve an incorrectly implemented
+      B-Tree operator class used by the index that is checked, or,
+      hypothetically, undiscovered bugs in the underlying B-Tree index
+      access method code.  Note that
+      <function>bt_index_parent_check</function> cannot be used when
+      Hot Standby mode is enabled (i.e., on read-only physical
+      replicas), unlike <function>bt_index_check</function>.
+     </para>
+    </listitem>
+   </varlistentry>
+  </variablelist>
+ </sect2>
+
+ <sect2>
+  <title>Using <filename>amcheck</> effectively</title>
+
+ <para>
+  <filename>amcheck</> can be effective at detecting various types of
+  failure modes that <link
+  linkend="app-initdb-data-checksums"><application>data page
+  checksums</></link> will always fail to catch.  These include:
+
+  <itemizedlist>
+   <listitem>
+    <para>
+     Structural inconsistencies caused by incorrect operator class
+     implementations.
+    </para>
+    <para>
+     This includes issues caused by the comparison rules of operating
+     system collations changing. Comparisons of datums of a collatable
+     type like <type>text</> must be immutable (just as all
+     comparisons used for B-Tree index scans must be immutable), which
+     implies that operating system collation rules must never change.
+     Though rare, updates to operating system collation rules can
+     cause these issues. More commonly, an inconsistency in the
+     collation order between a master server and a standby server is
+     implicated, possibly because the <emphasis>major</> operating
+     system version in use is inconsistent.  Such inconsistencies will
+     generally only arise on standby servers, and so can generally
+     only be detected on standby servers.
+    </para>
+    <para>
+     If a problem like this arises, it may not affect each individual
+     index that is ordered using an affected collation, simply because
+     <emphasis>indexed</> values might happen to have the same
+     absolute ordering regardless of the behavioral inconsistency. See
+     <xref linkend="locale"> and <xref linkend="collation"> for
+     further details about how <productname>PostgreSQL</> uses
+     operating system locales and collations.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Corruption caused by hypothetical undiscovered bugs in the
+     underlying <productname>PostgreSQL</> access method code or sort
+     code.
+    </para>
+    <para>
+     Automatic verification of the structural integrity of indexes
+     plays a role in the general testing of new or proposed
+     <productname>PostgreSQL</> features that could plausibly allow a
+     logical inconsistency to be introduced.  One obvious testing
+     strategy is to call <filename>amcheck</> functions continuously
+     when running the standard regression tests.  See <xref
+     linkend="regress-run"> for details on running the tests.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Filesystem or storage subsystem faults where checksums happen to
+     simply not be enabled.
+    </para>
+    <para>
+     Note that <filename>amcheck</> examines a page as represented in some
+     shared memory buffer at the time of verification if there is only a
+     shared buffer hit when accessing the block. Consequently,
+     <filename>amcheck</> does not necessarily examine data read from the
+     filesystem at the time of verification. Note that when checksums are
+     enabled, <filename>amcheck</> may raise an error due to a checksum
+     failure when a corrupt block is read into a buffer.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Corruption caused by faulty RAM, and the broader memory subsystem
+     and operating system.
+    </para>
+    <para>
+     <productname>PostgreSQL</> does not protect against correctable
+     memory errors and it is assumed you will operate using RAM that
+     uses industry standard Error Correcting Codes (ECC) or better
+     protection.  However, ECC memory is typically only immune to
+     single-bit errors, and should not be assumed to provide
+     <emphasis>absolute</emphasis> protection against failures that
+     result in memory corruption.
+    </para>
+   </listitem>
+  </itemizedlist>
+  In general, <filename>amcheck</> can only prove the presence of
+  corruption; it cannot prove its absence.
+ </para>
+
+ </sect2>
+ <sect2>
+  <title>Repairing corruption</title>
+ <para>
+  No error concerning corruption raised by <filename>amcheck</> should
+  ever be a false positive.  In practice, <filename>amcheck</> is more
+  likely to find software bugs than problems with hardware.
+  <filename>amcheck</> raises errors in the event of conditions that,
+  by definition, should never happen, and so careful analysis of
+  <filename>amcheck</> errors is often required.
+ </para>
+ <para>
+  There is no general method of repairing problems that
+  <filename>amcheck</> detects.  An explanation for the root cause of
+  an invariant violation should be sought.  <xref
+  linkend="pageinspect"> may play a useful role in diagnosing
+  corruption that <filename>amcheck</> detects.  A <command>REINDEX</>
+  may not be effective in repairing corruption.
+ </para>
+
+ </sect2>
+
+</sect1>
diff --git a/doc/src/sgml/contrib.sgml b/doc/src/sgml/contrib.sgml
index c8708ec..54102d6 100644
--- a/doc/src/sgml/contrib.sgml
+++ b/doc/src/sgml/contrib.sgml
@@ -103,6 +103,7 @@ CREATE EXTENSION <replaceable>module_name</> FROM unpackaged;
  </para>
 
  &adminpack;
+ &amcheck;
  &auth-delay;
  &auto-explain;
  &bloom;
diff --git a/doc/src/sgml/filelist.sgml b/doc/src/sgml/filelist.sgml
index 69649a7..39827be 100644
--- a/doc/src/sgml/filelist.sgml
+++ b/doc/src/sgml/filelist.sgml
@@ -106,6 +106,7 @@
 <!-- contrib information -->
 <!ENTITY contrib         SYSTEM "contrib.sgml">
 <!ENTITY adminpack       SYSTEM "adminpack.sgml">
+<!ENTITY amcheck         SYSTEM "amcheck.sgml">
 <!ENTITY auth-delay      SYSTEM "auth-delay.sgml">
 <!ENTITY auto-explain    SYSTEM "auto-explain.sgml">
 <!ENTITY bloom           SYSTEM "bloom.sgml">
-- 
2.7.4

From 60c670d251dd4244a09215e4f6c22e444d2bff7c Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Thu, 9 Mar 2017 15:50:40 -0800
Subject: [PATCH 1/2] Add amcheck extension to contrib.

This is the beginning of a collection of SQL-callable functions to
verify the integrity of data files.  For now it only contains code to
verify B-Tree indexes.

This adds two SQL-callable functions, validating B-Tree consistency to
a varying degree.  Check the, extensive, docs for details.

The goal is to later extend the coverage of the module to further
access methods, possibly including the heap.  Once checks for
additional access methods exist, we'll likely add some "dispatch"
functions that cover multiple access methods.

Author: Peter Geoghegan, editorialized by Andres Freund
Reviewed-By: Andres Freund, Thomas Vondra
Discussion: CAM3SWZQzLMhMwmBqjzK+pRKXrNUZ4w90wYMUWfkeV8mZ3Debvw@mail.gmail.com
---
 contrib/Makefile                 |    1 +
 contrib/amcheck/Makefile         |   19 +
 contrib/amcheck/amcheck--1.0.sql |   24 +
 contrib/amcheck/amcheck.control  |    5 +
 contrib/amcheck/verify_nbtree.c  | 1238 ++++++++++++++++++++++++++++++++++++++
 doc/src/sgml/amcheck.sgml        |  275 +++++++++
 doc/src/sgml/contrib.sgml        |    1 +
 doc/src/sgml/filelist.sgml       |    1 +
 src/tools/pgindent/typedefs.list |    2 +
 9 files changed, 1566 insertions(+)
 create mode 100644 contrib/amcheck/Makefile
 create mode 100644 contrib/amcheck/amcheck--1.0.sql
 create mode 100644 contrib/amcheck/amcheck.control
 create mode 100644 contrib/amcheck/verify_nbtree.c
 create mode 100644 doc/src/sgml/amcheck.sgml

diff --git a/contrib/Makefile b/contrib/Makefile
index 9a74e1b99f..e84eb67008 100644
--- a/contrib/Makefile
+++ b/contrib/Makefile
@@ -6,6 +6,7 @@ include $(top_builddir)/src/Makefile.global
 
 SUBDIRS = \
 		adminpack	\
+		amcheck		\
 		auth_delay	\
 		auto_explain	\
 		bloom		\
diff --git a/contrib/amcheck/Makefile b/contrib/amcheck/Makefile
new file mode 100644
index 0000000000..f14c7aa58b
--- /dev/null
+++ b/contrib/amcheck/Makefile
@@ -0,0 +1,19 @@
+# contrib/amcheck/Makefile
+
+MODULE_big	= amcheck
+OBJS		= verify_nbtree.o $(WIN32RES)
+
+EXTENSION = amcheck
+DATA = amcheck--1.0.sql
+PGFILEDESC = "amcheck - functions to verify access method invariants"
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/amcheck
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/amcheck/amcheck--1.0.sql b/contrib/amcheck/amcheck--1.0.sql
new file mode 100644
index 0000000000..a6612d130c
--- /dev/null
+++ b/contrib/amcheck/amcheck--1.0.sql
@@ -0,0 +1,24 @@
+/* contrib/amcheck/amcheck--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION amcheck" to load this file. \quit
+
+--
+-- bt_index_check()
+--
+CREATE FUNCTION bt_index_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'bt_index_check'
+LANGUAGE C STRICT PARALLEL RESTRICTED;
+
+--
+-- bt_index_parent_check()
+--
+CREATE FUNCTION bt_index_parent_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'bt_index_parent_check'
+LANGUAGE C STRICT PARALLEL RESTRICTED;
+
+-- Don't want these to be available to public
+REVOKE ALL ON FUNCTION bt_index_check(regclass) FROM PUBLIC;
+REVOKE ALL ON FUNCTION bt_index_parent_check(regclass) FROM PUBLIC;
diff --git a/contrib/amcheck/amcheck.control b/contrib/amcheck/amcheck.control
new file mode 100644
index 0000000000..180f150e7f
--- /dev/null
+++ b/contrib/amcheck/amcheck.control
@@ -0,0 +1,5 @@
+# amcheck extension
+comment = 'verify access method invariants'
+default_version = '1.0'
+module_pathname = '$libdir/amcheck'
+relocatable = true
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
new file mode 100644
index 0000000000..4cef4c44ff
--- /dev/null
+++ b/contrib/amcheck/verify_nbtree.c
@@ -0,0 +1,1238 @@
+/*-------------------------------------------------------------------------
+ *
+ * verify_nbtree.c
+ *		Verifies the integrity of nbtree indexes based on invariants.
+ *
+ * For B-Tree indexes, verification includes checking that each page in the
+ * target index has items in logical order as reported by an insertion scankey
+ * (the insertion scankey sort-wise NULL semantics are needed for
+ * verification).
+ *
+ *
+ * Copyright (c) 2017, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  contrib/amcheck/verify_nbtree.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/nbtree.h"
+#include "access/transam.h"
+#include "catalog/index.h"
+#include "catalog/pg_am.h"
+#include "commands/tablecmds.h"
+#include "miscadmin.h"
+#include "storage/lmgr.h"
+#include "utils/memutils.h"
+#include "utils/snapmgr.h"
+
+
+PG_MODULE_MAGIC;
+
+/*
+ * A B-Tree cannot possibly have this many levels, since there must be one
+ * block per level, which is bound by the range of BlockNumber:
+ */
+#define InvalidBtreeLevel	((uint32) InvalidBlockNumber)
+
+/*
+ * State associated with verifying a B-Tree index
+ *
+ * target is the point of reference for a verification operation.
+ *
+ * Other B-Tree pages may be allocated, but those are always auxiliary (e.g.,
+ * they are current target's child pages).  Conceptually, problems are only
+ * ever found in the current target page.	Each page found by verification's
+ * left/right, top/bottom scan becomes the target exactly once.
+ */
+typedef struct BtreeCheckState
+{
+	/*
+	 * Unchanging state, established at start of verification:
+	 */
+
+	/* B-Tree Index Relation */
+	Relation	rel;
+	/* ExclusiveLock held? */
+	bool		exclusivelylocked;
+	/* Per-page context */
+	MemoryContext targetcontext;
+	/* Buffer access strategy */
+	BufferAccessStrategy checkstrategy;
+
+	/*
+	 * Mutable state, for verification of particular page:
+	 */
+
+	/* Current target page */
+	Page		target;
+	/* Target block number */
+	BlockNumber targetblock;
+	/* Target page's LSN */
+	XLogRecPtr	targetlsn;
+} BtreeCheckState;
+
+/*
+ * Starting point for verifying an entire B-Tree index level
+ */
+typedef struct BtreeLevel
+{
+	/* Level number (0 is leaf page level). */
+	uint32		level;
+
+	/* Left most block on level.  Scan of level begins here. */
+	BlockNumber leftmost;
+
+	/* Is this level reported as "true" root level by meta page? */
+	bool		istruerootlevel;
+} BtreeLevel;
+
+PG_FUNCTION_INFO_V1(bt_index_check);
+PG_FUNCTION_INFO_V1(bt_index_parent_check);
+
+static inline void btree_index_checkable(Relation rel);
+static void bt_check_every_level(Relation rel, bool exclusivelylocked);
+static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state,
+							 BtreeLevel level);
+static void bt_target_page_check(BtreeCheckState *state);
+static ScanKey bt_right_page_check_scankey(BtreeCheckState *state);
+static void bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
+				  ScanKey targetkey);
+static inline bool offset_is_negative_infinity(BTPageOpaque opaque,
+							OffsetNumber offset);
+static inline bool invariant_leq_offset(BtreeCheckState *state,
+					 ScanKey key,
+					 OffsetNumber upperbound);
+static inline bool invariant_geq_offset(BtreeCheckState *state,
+					 ScanKey key,
+					 OffsetNumber lowerbound);
+static inline bool invariant_leq_nontarget_offset(BtreeCheckState *state,
+							   Page other,
+							   ScanKey key,
+							   OffsetNumber upperbound);
+static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum);
+
+/*
+ * bt_index_check(index regclass)
+ *
+ * Verify integrity of B-Tree index.
+ *
+ * Only acquires AccessShareLock on index relation.  Does not consider
+ * invariants that exist between parent/child pages.
+ */
+Datum
+bt_index_check(PG_FUNCTION_ARGS)
+{
+	Oid			relid = PG_GETARG_OID(0);
+	Relation	indrel;
+
+	indrel = relation_open(relid, AccessShareLock);
+
+	/* Relation suitable for checking as B-Tree? */
+	btree_index_checkable(indrel);
+
+	/* Check index */
+	bt_check_every_level(indrel, false);
+
+	/* Close, but keep lock */
+	relation_close(indrel, NoLock);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * bt_index_parent_check(index regclass)
+ *
+ * Verify integrity of B-Tree index.
+ *
+ * Acquires ExclusiveLock on index relation, and ShareLock on the associated
+ * heap relation, a bit like REINDEX.  Verifies that downlinks in parent pages
+ * are valid lower bounds on child pages.
+ */
+Datum
+bt_index_parent_check(PG_FUNCTION_ARGS)
+{
+	Oid			indrelid = PG_GETARG_OID(0);
+	Oid			heapid;
+	Relation	indrel;
+	Relation	heaprel;
+
+	/*
+	 * We must lock table before index to avoid deadlocks.	However, if the
+	 * passed indrelid isn't an index then IndexGetRelation() will fail.
+	 * Rather than emitting a not-very-helpful error message, postpone
+	 * complaining, expecting that the is-it-an-index test below will fail.
+	 */
+	heapid = IndexGetRelation(indrelid, true);
+	if (OidIsValid(heapid))
+		heaprel = heap_open(heapid, ShareLock);
+	else
+		heaprel = NULL;
+
+	/*
+	 * Open the target index relations separately (like relation_openrv(), but
+	 * with heap relation locked first to prevent deadlocking).  In hot
+	 * standby mode this will raise an error.
+	 */
+	indrel = index_open(indrelid, ExclusiveLock);
+
+	/*
+	 * Since we did the IndexGetRelation call above without any lock, it's
+	 * barely possible that a race against an index drop/recreation could have
+	 * netted us the wrong table.  Although the table itself won't actually be
+	 * examined during verification currently, a recheck still seems like a
+	 * good idea.
+	 */
+	if (heaprel == NULL || heapid != IndexGetRelation(indrelid, false))
+		ereport(ERROR,
+				(errcode(ERRCODE_UNDEFINED_TABLE),
+				 errmsg("could not open parent table of index %s",
+						RelationGetRelationName(indrel))));
+
+	/* Relation suitable for checking as B-Tree? */
+	btree_index_checkable(indrel);
+
+	/* Check index */
+	bt_check_every_level(indrel, true);
+
+	/* Close, but keep locks */
+	index_close(indrel, NoLock);
+	if (heaprel)
+		heap_close(heaprel, NoLock);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * Basic checks about the suitability of a relation for checking as a B-Tree
+ * index.
+ */
+static inline void
+btree_index_checkable(Relation rel)
+{
+	if (rel->rd_rel->relkind != RELKIND_INDEX ||
+		rel->rd_rel->relam != BTREE_AM_OID)
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("only B-Tree indexes are supported as targets for verification"),
+				 errdetail("Relation \"%s\" is not a B-Tree index.",
+						   RelationGetRelationName(rel))));
+
+	if (RELATION_IS_OTHER_TEMP(rel))
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot access temporary tables of other sessions"),
+			 errdetail("Index \"%s\" is associated with temporary relation.",
+					   RelationGetRelationName(rel))));
+
+	if (!IndexIsValid(rel->rd_index))
+		ereport(ERROR,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("cannot check index \"%s\"",
+						RelationGetRelationName(rel)),
+				 errdetail("Index is not valid")));
+}
+
+/*
+ * Main entry point for B-Tree SQL-callable functions.	Walks the B-Tree in
+ * logical order, verifying invariants as it goes.
+ *
+ * It is the caller's responsibility to acquire appropriate heavyweight lock on
+ * the index relation, and advise us if extra checks are safe when an
+ * ExclusiveLock is held.
+ *
+ * An ExclusiveLock is generally assumed to prevent any kind of physical
+ * modification to the index structure, including modifications that VACUUM may
+ * make.  This does not include setting of the LP_DEAD bit by concurrent index
+ * scans, although that is just metadata that is not able to directly affect
+ * any check performed here.  Any concurrent process that might act on the
+ * LP_DEAD bit being set (recycle space) requires a heavyweight lock that
+ * cannot be held while we hold an ExclusiveLock.  (Besides, even if that could
+ * happen, the ad-hoc recycling when a page might otherwise split is performed
+ * per-page, and requires an exclusive buffer lock, which wouldn't cause us
+ * trouble.  _bt_delitems_vacuum() may only delete leaf items, and so the extra
+ * parent/child check cannot be affected.)
+ */
+static void
+bt_check_every_level(Relation rel, bool exclusivelylocked)
+{
+	BtreeCheckState *state;
+	Page		metapage;
+	BTMetaPageData *metad;
+	uint32		previouslevel;
+	BtreeLevel	current;
+
+	/*
+	 * RecentGlobalXmin assertion matches index_getnext_tid().	See note on
+	 * RecentGlobalXmin/B-Tree page deletion.
+	 */
+	Assert(TransactionIdIsValid(RecentGlobalXmin));
+
+	/*
+	 * Initialize state for entire verification operation
+	 */
+	state = palloc(sizeof(BtreeCheckState));
+	state->rel = rel;
+	state->exclusivelylocked = exclusivelylocked;
+	/* Create context for page */
+	state->targetcontext = AllocSetContextCreate(CurrentMemoryContext,
+												 "amcheck context",
+												 ALLOCSET_DEFAULT_MINSIZE,
+												 ALLOCSET_DEFAULT_INITSIZE,
+												 ALLOCSET_DEFAULT_MAXSIZE);
+	state->checkstrategy = GetAccessStrategy(BAS_BULKREAD);
+
+	/* Get true root block from meta-page */
+	metapage = palloc_btree_page(state, BTREE_METAPAGE);
+	metad = BTPageGetMeta(metapage);
+
+	/*
+	 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
+	 * the fast root and true root differ.
+	 *
+	 * Start from the true root, not the fast root, unlike conventional index
+	 * scans.  This approach is more thorough, and removes the risk of
+	 * following a stale fast root from the meta page.
+	 */
+	if (metad->btm_fastroot != metad->btm_root)
+		ereport(DEBUG1,
+				(errcode(ERRCODE_NO_DATA),
+				 errmsg("harmless fast root mismatch in index %s",
+						RelationGetRelationName(rel)),
+				 errdetail_internal("Fast block %u (level %u) "
+									"differs from true root "
+									"block %u (level %u).",
+									metad->btm_fastroot, metad->btm_fastlevel,
+									metad->btm_root, metad->btm_level)));
+
+	/*
+	 * Starting at the root, verify every level.  Move left to right, top to
+	 * bottom.	Note that there may be no pages other than the meta page (meta
+	 * page can indicate that root is P_NONE when the index is totally empty).
+	 */
+	previouslevel = InvalidBtreeLevel;
+	current.level = metad->btm_level;
+	current.leftmost = metad->btm_root;
+	current.istruerootlevel = true;
+	while (current.leftmost != P_NONE)
+	{
+		/*
+		 * Verify this level, and get left most page for next level down, if
+		 * not at leaf level
+		 */
+		current = bt_check_level_from_leftmost(state, current);
+
+		if (current.leftmost == InvalidBlockNumber)
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("index \"%s\" has no valid pages on level below %u or first level",
+							RelationGetRelationName(rel), previouslevel)));
+
+		previouslevel = current.level;
+	}
+
+	/* Be tidy: */
+	MemoryContextDelete(state->targetcontext);
+}
+
+/*
+ * Given a left-most block at some level, move right, verifying each page
+ * individually (with more verification across pages for "exclusivelylocked"
+ * callers).  Caller should pass the true root page as the leftmost initially,
+ * working their way down by passing what is returned for the last call here
+ * until level 0 (leaf page level) was reached.
+ *
+ * Returns state for next call, if any.  This includes left-most block number
+ * one level lower that should be passed on next level/call, which is set to
+ * P_NONE on last call here (when leaf level is verified).	Level numbers
+ * follow the nbtree convention: higher levels have higher numbers, because new
+ * levels are added only due to a root page split.	Note that prior to the
+ * first root page split, the root is also a leaf page, so there is always a
+ * level 0 (leaf level), and it's always the last level processed.
+ *
+ * Note on memory management:  State's per-page context is reset here, between
+ * each call to bt_target_page_check().
+ */
+static BtreeLevel
+bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
+{
+	/* State to establish early, concerning entire level */
+	BTPageOpaque opaque;
+	MemoryContext oldcontext;
+	BtreeLevel	nextleveldown;
+
+	/* Variables for iterating across level using right links */
+	BlockNumber leftcurrent = P_NONE;
+	BlockNumber current = level.leftmost;
+
+	/* Initialize return state */
+	nextleveldown.leftmost = InvalidBlockNumber;
+	nextleveldown.level = InvalidBtreeLevel;
+	nextleveldown.istruerootlevel = false;
+
+	/* Use page-level context for duration of this call */
+	oldcontext = MemoryContextSwitchTo(state->targetcontext);
+
+	elog(DEBUG2, "verifying level %u%s", level.level,
+		 level.istruerootlevel ?
+		 " (true root level)" : level.level == 0 ? " (leaf level)" : "");
+
+	do
+	{
+		/* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
+		CHECK_FOR_INTERRUPTS();
+
+		/* Initialize state for this iteration */
+		state->targetblock = current;
+		state->target = palloc_btree_page(state, state->targetblock);
+		state->targetlsn = PageGetLSN(state->target);
+
+		opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+		if (P_IGNORE(opaque))
+		{
+			if (P_RIGHTMOST(opaque))
+				ereport(ERROR,
+						(errcode(ERRCODE_INDEX_CORRUPTED),
+						 errmsg("block %u fell off the end of index \"%s\"",
+							 current, RelationGetRelationName(state->rel))));
+			else
+				ereport(DEBUG1,
+						(errcode(ERRCODE_NO_DATA),
+						 errmsg("block %u of index \"%s\" ignored",
+							 current, RelationGetRelationName(state->rel))));
+			goto nextpage;
+		}
+		else if (nextleveldown.leftmost == InvalidBlockNumber)
+		{
+			/*
+			 * A concurrent page split could make the caller supplied leftmost
+			 * block no longer contain the leftmost page, or no longer be the
+			 * true root, but where that isn't possible due to heavyweight
+			 * locking, check that the first valid page meets caller's
+			 * expectations.
+			 */
+			if (state->exclusivelylocked)
+			{
+				if (!P_LEFTMOST(opaque))
+					ereport(ERROR,
+							(errcode(ERRCODE_INDEX_CORRUPTED),
+						   errmsg("block %u is not leftmost in index \"%s\"",
+							 current, RelationGetRelationName(state->rel))));
+
+				if (level.istruerootlevel && !P_ISROOT(opaque))
+					ereport(ERROR,
+							(errcode(ERRCODE_INDEX_CORRUPTED),
+						  errmsg("block %u is not true root in index \"%s\"",
+							 current, RelationGetRelationName(state->rel))));
+			}
+
+			/*
+			 * Before beginning any non-trivial examination of level, prepare
+			 * state for next bt_check_level_from_leftmost() invocation for
+			 * the next level for the next level down (if any).
+			 *
+			 * There should be at least one non-ignorable page per level,
+			 * unless this is the leaf level, which is assumed by caller to be
+			 * final level.
+			 */
+			if (!P_ISLEAF(opaque))
+			{
+				IndexTuple	itup;
+				ItemId		itemid;
+
+				/* Internal page -- downlink gets leftmost on next level */
+				itemid = PageGetItemId(state->target, P_FIRSTDATAKEY(opaque));
+				itup = (IndexTuple) PageGetItem(state->target, itemid);
+				nextleveldown.leftmost = ItemPointerGetBlockNumber(&(itup->t_tid));
+				nextleveldown.level = opaque->btpo.level - 1;
+			}
+			else
+			{
+				/*
+				 * Leaf page -- final level caller must process.
+				 *
+				 * Note that this could also be the root page, if there has
+				 * been no root page split yet.
+				 */
+				nextleveldown.leftmost = P_NONE;
+				nextleveldown.level = InvalidBtreeLevel;
+			}
+
+			/*
+			 * Finished setting up state for this call/level.  Control will
+			 * never end up back here in any future loop iteration for this
+			 * level.
+			 */
+		}
+
+		if (state->exclusivelylocked && opaque->btpo_prev != leftcurrent)
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("left link/right link pair in index \"%s\" not in agreement",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Block=%u left block=%u left link from block=%u.",
+								  current, leftcurrent, opaque->btpo_prev)));
+
+		/* Check level, which must be valid for non-ignorable page */
+		if (level.level != opaque->btpo.level)
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("leftmost down link for level points to block in index \"%s\" whose level is not one level down",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Block pointed to=%u expected level=%u level in pointed to block=%u.",
+								 current, level.level, opaque->btpo.level)));
+
+		/* Verify invariants for page -- all important checks occur here */
+		bt_target_page_check(state);
+
+nextpage:
+
+		/* Try to detect circular links */
+		if (current == leftcurrent || current == opaque->btpo_prev)
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+			  errmsg("circular link chain found in block %u of index \"%s\"",
+					 current, RelationGetRelationName(state->rel))));
+
+		leftcurrent = current;
+		current = opaque->btpo_next;
+
+		/* Free page and associated memory for this iteration */
+		MemoryContextReset(state->targetcontext);
+	}
+	while (current != P_NONE);
+
+	/* Don't change context for caller */
+	MemoryContextSwitchTo(oldcontext);
+
+	return nextleveldown;
+}
+
+/*
+ * Function performs the following checks on target page, or pages ancillary to
+ * target page:
+ *
+ * - That every "real" data item is less than or equal to the high key, which
+ *	 is an upper bound on the items on the pages (where there is a high key at
+ *	 all -- pages that are rightmost lack one).
+ *
+ * - That within the page, every "real" item is less than or equal to the item
+ *	 immediately to its right, if any (i.e., that the items are in order within
+ *	 the page, so that the binary searches performed by index scans are sane).
+ *
+ * - That the last item stored on the page is less than or equal to the first
+ *	 "real" data item on the page to the right (if such a first item is
+ *	 available).
+ *
+ * Furthermore, when state passed shows ExclusiveLock held, and target page is
+ * internal page, function also checks:
+ *
+ * - That all child pages respect downlinks lower bound.
+ *
+ * Note:  Memory allocated in this routine is expected to be released by caller
+ * resetting state->targetcontext.
+ */
+static void
+bt_target_page_check(BtreeCheckState *state)
+{
+	OffsetNumber offset;
+	OffsetNumber max;
+	BTPageOpaque topaque;
+
+	topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+	max = PageGetMaxOffsetNumber(state->target);
+
+	elog(DEBUG2, "verifying %u items on %s block %u", max,
+		 P_ISLEAF(topaque) ? "leaf" : "internal", state->targetblock);
+
+	/*
+	 * Loop over page items, starting from first non-highkey item, not high
+	 * key (if any).  Also, immediately skip "negative infinity" real item (if
+	 * any).
+	 */
+	for (offset = P_FIRSTDATAKEY(topaque);
+		 offset <= max;
+		 offset = OffsetNumberNext(offset))
+	{
+		ItemId		itemid;
+		IndexTuple	itup;
+		ScanKey		skey;
+
+		CHECK_FOR_INTERRUPTS();
+
+		/*
+		 * Don't try to generate scankey using "negative infinity" garbage
+		 * data
+		 */
+		if (offset_is_negative_infinity(topaque, offset))
+			continue;
+
+		/* Build insertion scankey for current page offset */
+		itemid = PageGetItemId(state->target, offset);
+		itup = (IndexTuple) PageGetItem(state->target, itemid);
+		skey = _bt_mkscankey(state->rel, itup);
+
+		/*
+		 * * High key check *
+		 *
+		 * If there is a high key (if this is not the rightmost page on its
+		 * entire level), check that high key actually is upper bound on all
+		 * page items.
+		 *
+		 * We prefer to check all items against high key rather than checking
+		 * just the first and trusting that the operator class obeys the
+		 * transitive law (which implies that all subsequent items also
+		 * respected the high key invariant if they pass the item order
+		 * check).
+		 *
+		 * Ideally, we'd compare every item in the index against every other
+		 * item in the index, and not trust opclass obedience of the
+		 * transitive law to bridge the gap between children and their
+		 * grandparents (as well as great-grandparents, and so on).  We don't
+		 * go to those lengths because that would be prohibitively expensive,
+		 * and probably not markedly more effective in practice.
+		 */
+		if (!P_RIGHTMOST(topaque) &&
+			!invariant_leq_offset(state, skey, P_HIKEY))
+		{
+			char	   *itid,
+					   *htid;
+
+			itid = psprintf("(%u,%u)", state->targetblock, offset);
+			htid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("high key invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+					 errdetail_internal("Index tid=%s points to %s tid=%s "
+										"page lsn=%X/%X.",
+										itid,
+										P_ISLEAF(topaque) ? "heap" : "index",
+										htid,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
+		}
+
+		/*
+		 * * Item order check *
+		 *
+		 * Check that items are stored on page in logical order, by checking
+		 * current item is less than or equal to next item (if any).
+		 */
+		if (OffsetNumberNext(offset) <= max &&
+			!invariant_leq_offset(state, skey,
+								  OffsetNumberNext(offset)))
+		{
+			char	   *itid,
+					   *htid,
+					   *nitid,
+					   *nhtid;
+
+			itid = psprintf("(%u,%u)", state->targetblock, offset);
+			htid = psprintf("(%u,%u)",
+							ItemPointerGetBlockNumber(&(itup->t_tid)),
+							ItemPointerGetOffsetNumber(&(itup->t_tid)));
+			nitid = psprintf("(%u,%u)", state->targetblock,
+							 OffsetNumberNext(offset));
+
+			/* Reuse itup to get pointed-to heap location of second item */
+			itemid = PageGetItemId(state->target, OffsetNumberNext(offset));
+			itup = (IndexTuple) PageGetItem(state->target, itemid);
+			nhtid = psprintf("(%u,%u)",
+							 ItemPointerGetBlockNumber(&(itup->t_tid)),
+							 ItemPointerGetOffsetNumber(&(itup->t_tid)));
+
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("item order invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+			   errdetail_internal("Lower index tid=%s (points to %s tid=%s) "
+								  "higher index tid=%s (points to %s tid=%s) "
+								  "page lsn=%X/%X.",
+								  itid,
+								  P_ISLEAF(topaque) ? "heap" : "index",
+								  htid,
+								  nitid,
+								  P_ISLEAF(topaque) ? "heap" : "index",
+								  nhtid,
+								  (uint32) (state->targetlsn >> 32),
+								  (uint32) state->targetlsn)));
+		}
+
+		/*
+		 * * Last item check *
+		 *
+		 * Check last item against next/right page's first data item's when
+		 * last item on page is reached.  This additional check can detect
+		 * transposed pages.
+		 *
+		 * This check is similar to the item order check that will have
+		 * already been performed for every other "real" item on target page
+		 * when last item is checked.  The difference is that the next item
+		 * (the item that is compared to target's last item) needs to come
+		 * from the next/sibling page.	There may not be such an item
+		 * available from sibling for various reasons, though (e.g., target is
+		 * the rightmost page on level).
+		 */
+		else if (offset == max)
+		{
+			ScanKey		rightkey;
+
+			/* Get item in next/right page */
+			rightkey = bt_right_page_check_scankey(state);
+
+			if (rightkey &&
+				!invariant_geq_offset(state, rightkey, max))
+			{
+				/*
+				 * As explained at length in bt_right_page_check_scankey(),
+				 * there is a known !exclusivelylocked race that could account
+				 * for apparent violation of invariant, which we must check
+				 * for before actually proceeding with raising error.  Our
+				 * canary condition is that target page was deleted.
+				 */
+				if (!state->exclusivelylocked)
+				{
+					/* Get fresh copy of target page */
+					state->target = palloc_btree_page(state, state->targetblock);
+					/* Note that we deliberately do not update target LSN */
+					topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+					/*
+					 * All !exclusivelylocked checks now performed; just
+					 * return
+					 */
+					if (P_IGNORE(topaque))
+						return;
+				}
+
+				ereport(ERROR,
+						(errcode(ERRCODE_INDEX_CORRUPTED),
+						 errmsg("cross page item order invariant violated for index \"%s\"",
+								RelationGetRelationName(state->rel)),
+						 errdetail_internal("Last item on page tid=(%u,%u) "
+											"page lsn=%X/%X.",
+											state->targetblock, offset,
+											(uint32) (state->targetlsn >> 32),
+											(uint32) state->targetlsn)));
+			}
+		}
+
+		/*
+		 * * Downlink check *
+		 *
+		 * Additional check of child items iff this is an internal page and
+		 * caller holds an ExclusiveLock.  This happens for every downlink
+		 * (item) in target excluding the negative-infinity downlink (again,
+		 * this is because it has no useful value to compare).
+		 */
+		if (!P_ISLEAF(topaque) && state->exclusivelylocked)
+		{
+			BlockNumber childblock = ItemPointerGetBlockNumber(&(itup->t_tid));
+
+			bt_downlink_check(state, childblock, skey);
+		}
+	}
+}
+
+/*
+ * Return a scankey for an item on page to right of current target (or the
+ * first non-ignorable page), sufficient to check ordering invariant on last
+ * item in current target page.  Returned scankey relies on local memory
+ * allocated for the child page, which caller cannot pfree().  Caller's memory
+ * context should be reset between calls here.
+ *
+ * This is the first data item, and so all adjacent items are checked against
+ * their immediate sibling item (which may be on a sibling page, or even a
+ * "cousin" page at parent boundaries where target's rightlink points to page
+ * with different parent page).  If no such valid item is available, return
+ * NULL instead.
+ *
+ * Note that !exclusivelylocked callers must reverify that target page has not
+ * been concurrently deleted.
+ */
+static ScanKey
+bt_right_page_check_scankey(BtreeCheckState *state)
+{
+	BTPageOpaque opaque;
+	ItemId		rightitem;
+	BlockNumber targetnext;
+	Page		rightpage;
+	OffsetNumber nline;
+
+	/* Determine target's next block number */
+	opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
+
+	/* If target is already rightmost, no right sibling; nothing to do here */
+	if (P_RIGHTMOST(opaque))
+		return NULL;
+
+	/*
+	 * General notes on concurrent page splits and page deletion:
+	 *
+	 * Routines like _bt_search() don't require *any* page split interlock
+	 * when descending the tree, including something very light like a buffer
+	 * pin. That's why it's okay that we don't either.  This avoidance of any
+	 * need to "couple" buffer locks is the raison d' etre of the Lehman & Yao
+	 * algorithm, in fact.
+	 *
+	 * That leaves deletion.  A deleted page won't actually be recycled by
+	 * VACUUM early enough for us to fail to at least follow its right link
+	 * (or left link, or downlink) and find its sibling, because recycling
+	 * does not occur until no possible index scan could land on the page.
+	 * Index scans can follow links with nothing more than their snapshot as
+	 * an interlock and be sure of at least that much.	(See page
+	 * recycling/RecentGlobalXmin notes in nbtree README.)
+	 *
+	 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
+	 * dead (ignorable) page one or more times.  There will either be a
+	 * further right link to follow that leads to a live page before too long
+	 * (before passing by parent's rightmost child), or we will find the end
+	 * of the entire level instead (possible when parent page is itself the
+	 * rightmost on its level).
+	 */
+	targetnext = opaque->btpo_next;
+	for (;;)
+	{
+		CHECK_FOR_INTERRUPTS();
+
+		rightpage = palloc_btree_page(state, targetnext);
+		opaque = (BTPageOpaque) PageGetSpecialPointer(rightpage);
+
+		if (!P_IGNORE(opaque) || P_RIGHTMOST(opaque))
+			break;
+
+		/* We landed on a deleted page, so step right to find a live page */
+		targetnext = opaque->btpo_next;
+		ereport(DEBUG1,
+				(errcode(ERRCODE_NO_DATA),
+				 errmsg("level %u leftmost page of index \"%s\" was found deleted or half dead",
+					opaque->btpo.level, RelationGetRelationName(state->rel)),
+				 errdetail_internal("Deleted page found when building scankey from right sibling.")));
+
+		/* Be slightly more pro-active in freeing this memory, just in case */
+		pfree(rightpage);
+	}
+
+	/*
+	 * No ExclusiveLock held case -- why it's safe to proceed.
+	 *
+	 * Problem:
+	 *
+	 * We must avoid false positive reports of corruption when caller treats
+	 * item returned here as an upper bound on target's last item.  In
+	 * general, false positives are disallowed.  Avoiding them here when
+	 * caller is !exclusivelylocked is subtle.
+	 *
+	 * A concurrent page deletion by VACUUM of the target page can result in
+	 * the insertion of items on to this right sibling page that would
+	 * previously have been inserted on our target page.  There might have
+	 * been insertions that followed the target's downlink after it was made
+	 * to point to right sibling instead of target by page deletion's first
+	 * phase. The inserters insert items that would belong on target page.
+	 * This race is very tight, but it's possible.  This is our only problem.
+	 *
+	 * Non-problems:
+	 *
+	 * We are not hindered by a concurrent page split of the target; we'll
+	 * never land on the second half of the page anyway.  A concurrent split
+	 * of the right page will also not matter, because the first data item
+	 * remains the same within the left half, which we'll reliably land on. If
+	 * we had to skip over ignorable/deleted pages, it cannot matter because
+	 * their key space has already been atomically merged with the first
+	 * non-ignorable page we eventually find (doesn't matter whether the page
+	 * we eventually find is a true sibling or a cousin of target, which we go
+	 * into below).
+	 *
+	 * Solution:
+	 *
+	 * Caller knows that it should reverify that target is not ignorable
+	 * (half-dead or deleted) when cross-page sibling item comparison appears
+	 * to indicate corruption (invariant fails).  This detects the single race
+	 * condition that exists for caller.  This is correct because the
+	 * continued existence of target block as non-ignorable (not half-dead or
+	 * deleted) implies that target page was not merged into from the right by
+	 * deletion; the key space at or after target never moved left.  Target's
+	 * parent either has the same downlink to target as before, or a <=
+	 * downlink due to deletion at the left of target.	Target either has the
+	 * same highkey as before, or a highkey <= before when there is a page
+	 * split. (The rightmost concurrently-split-from-target-page page will
+	 * still have the same highkey as target was originally found to have,
+	 * which for our purposes is equivalent to target's highkey itself never
+	 * changing, since we reliably skip over
+	 * concurrently-split-from-target-page pages.)
+	 *
+	 * In simpler terms, we allow that the key space of the target may expand
+	 * left (the key space can move left on the left side of target only), but
+	 * the target key space cannot expand right and get ahead of us without
+	 * our detecting it.  The key space of the target cannot shrink, unless it
+	 * shrinks to zero due to the deletion of the original page, our canary
+	 * condition.  (To be very precise, we're a bit stricter than that because
+	 * it might just have been that the target page split and only the
+	 * original target page was deleted.  We can be more strict, just not more
+	 * lax.)
+	 *
+	 * Top level tree walk caller moves on to next page (makes it the new
+	 * target) following recovery from this race.  (cf.  The rationale for
+	 * child/downlink verification needing an ExclusiveLock within
+	 * bt_downlink_check(), where page deletion is also the main source of
+	 * trouble.)
+	 *
+	 * Note that it doesn't matter if right sibling page here is actually a
+	 * cousin page, because in order for the key space to be readjusted in a
+	 * way that causes us issues in next level up (guiding problematic
+	 * concurrent insertions to the cousin from the grandparent rather than to
+	 * the sibling from the parent), there'd have to be page deletion of
+	 * target's parent page (affecting target's parent's downlink in target's
+	 * grandparent page).  Internal page deletion only occurs when there are
+	 * no child pages (they were all fully deleted), and caller is checking
+	 * that the target's parent has at least one non-deleted (so
+	 * non-ignorable) child: the target page.  (Note that the first phase of
+	 * deletion atomically marks the page to be deleted half-dead/ignorable at
+	 * the same time downlink in its parent is removed, so caller will
+	 * definitely not fail to detect that this happened.)
+	 *
+	 * This trick is inspired by the method backward scans use for dealing
+	 * with concurrent page splits; concurrent page deletion is a problem that
+	 * similarly receives special consideration sometimes (it's possible that
+	 * the backwards scan will re-read its "original" block after failing to
+	 * find a right-link to it, having already moved in the opposite direction
+	 * (right/"forwards") a few times to try to locate one).  Just like us,
+	 * that happens only to determine if there was a concurrent page deletion
+	 * of a reference page, and just like us if there was a page deletion of
+	 * that reference page it means we can move on from caring about the
+	 * reference page.	See the nbtree README for a full description of how
+	 * that works.
+	 */
+	nline = PageGetMaxOffsetNumber(rightpage);
+
+	/*
+	 * Get first data item, if any
+	 */
+	if (P_ISLEAF(opaque) && nline >= P_FIRSTDATAKEY(opaque))
+	{
+		/* Return first data item (if any) */
+		rightitem = PageGetItemId(rightpage, P_FIRSTDATAKEY(opaque));
+	}
+	else if (!P_ISLEAF(opaque) &&
+			 nline >= OffsetNumberNext(P_FIRSTDATAKEY(opaque)))
+	{
+		/*
+		 * Return first item after the internal page's "negative infinity"
+		 * item
+		 */
+		rightitem = PageGetItemId(rightpage,
+								  OffsetNumberNext(P_FIRSTDATAKEY(opaque)));
+	}
+	else
+	{
+		/*
+		 * No first item.  Page is probably empty leaf page, but it's also
+		 * possible that it's an internal page with only a negative infinity
+		 * item.
+		 */
+		ereport(DEBUG1,
+				(errcode(ERRCODE_NO_DATA),
+				 errmsg("%s block %u of index \"%s\" has no first data item",
+						P_ISLEAF(opaque) ? "leaf" : "internal", targetnext,
+						RelationGetRelationName(state->rel))));
+		return NULL;
+	}
+
+	/*
+	 * Return first real item scankey.	Note that this relies on right page
+	 * memory remaining allocated.
+	 */
+	return _bt_mkscankey(state->rel,
+						 (IndexTuple) PageGetItem(rightpage, rightitem));
+}
+
+/*
+ * Checks one of target's downlink against its child page.
+ *
+ * Conceptually, the target page continues to be what is checked here.	The
+ * target block is still blamed in the event of finding an invariant violation.
+ * The downlink insertion into the target is probably where any problem raised
+ * here arises, and there is no such thing as a parent link, so doing the
+ * verification this way around is much more practical.
+ */
+static void
+bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
+				  ScanKey targetkey)
+{
+	OffsetNumber offset;
+	OffsetNumber maxoffset;
+	Page		child;
+	BTPageOpaque copaque;
+
+	/*
+	 * Caller must have ExclusiveLock on target relation, because of
+	 * considerations around page deletion by VACUUM.
+	 *
+	 * NB: In general, page deletion deletes the right sibling's downlink, not
+	 * the downlink of the page being deleted; the deleted page's downlink is
+	 * reused for its sibling.	The key space is thereby consolidated between
+	 * the deleted page and its right sibling.	(We cannot delete a parent
+	 * page's rightmost child unless it is the last child page, and we intend
+	 * to also delete the parent itself.)
+	 *
+	 * If this verification happened without an ExclusiveLock, the following
+	 * race condition could cause false positives:
+	 *
+	 * In general, concurrent page deletion might occur, including deletion of
+	 * the left sibling of the child page that is examined here.  If such a
+	 * page deletion were to occur, closely followed by an insertion into the
+	 * newly expanded key space of the child, a window for the false positive
+	 * opens up: the stale parent/target downlink originally followed to get
+	 * to the child legitimately ceases to be a lower bound on all items in
+	 * the page, since the key space was concurrently expanded "left".
+	 * (Insertion followed the "new" downlink for the child, not our now-stale
+	 * downlink, which was concurrently physically removed in target/parent as
+	 * part of deletion's first phase.)
+	 *
+	 * Note that while the cross-page-same-level last item check uses a trick
+	 * that allows it to perform verification for !exclusivelylocked callers,
+	 * a similar trick seems difficult here.  The trick that that other check
+	 * uses is, in essence, to lock down race conditions to those that occur
+	 * due to concurrent page deletion of the target; that's a race that can
+	 * be reliably detected before actually reporting corruption.
+	 *
+	 * On the other hand, we'd need to lock down race conditions involving
+	 * deletion of child's left page, for long enough to read the child page
+	 * into memory (in other words, a scheme with concurrently held buffer
+	 * locks on both child and left-of-child pages).  That's unacceptable for
+	 * amcheck functions on general principle, though.
+	 */
+	Assert(state->exclusivelylocked);
+
+	/*
+	 * Verify child page has the downlink key from target page (its parent) as
+	 * a lower bound.
+	 *
+	 * Check all items, rather than checking just the first and trusting that
+	 * the operator class obeys the transitive law.
+	 */
+	child = palloc_btree_page(state, childblock);
+	copaque = (BTPageOpaque) PageGetSpecialPointer(child);
+	maxoffset = PageGetMaxOffsetNumber(child);
+
+	for (offset = P_FIRSTDATAKEY(copaque);
+		 offset <= maxoffset;
+		 offset = OffsetNumberNext(offset))
+	{
+		/*
+		 * Skip comparison of target page key against "negative infinity"
+		 * item, if any.  Checking it would indicate that it's not an upper
+		 * bound, but that's only because of the hard-coding within
+		 * _bt_compare().
+		 */
+		if (offset_is_negative_infinity(copaque, offset))
+			continue;
+
+		if (!invariant_leq_nontarget_offset(state, child,
+											targetkey, offset))
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("down-link lower bound invariant violated for index \"%s\"",
+							RelationGetRelationName(state->rel)),
+				errdetail_internal("Parent block=%u child index tid=(%u,%u) "
+								   "parent page lsn=%X/%X.",
+								   state->targetblock, childblock, offset,
+								   (uint32) (state->targetlsn >> 32),
+								   (uint32) state->targetlsn)));
+	}
+
+	pfree(child);
+}
+
+/*
+ * Is particular offset within page (whose special state is passed by caller)
+ * the page negative-infinity item?
+ *
+ * As noted in comments above _bt_compare(), there is special handling of the
+ * first data item as a "negative infinity" item.  The hard-coding within
+ * _bt_compare() makes comparing this item for the purposes of verification
+ * pointless at best, since the IndexTuple only contains a valid TID (a
+ * reference TID to child page).
+ */
+static inline bool
+offset_is_negative_infinity(BTPageOpaque opaque, OffsetNumber offset)
+{
+	/*
+	 * For internal pages only, the first item after high key, if any, is
+	 * negative infinity item.	Internal pages always have a negative infinity
+	 * item, whereas leaf pages never have one.  This implies that negative
+	 * infinity item is either first or second line item, or there is none
+	 * within page.
+	 *
+	 * Right-most pages don't have a high key, but could be said to
+	 * conceptually have a "positive infinity" high key.  Thus, there is a
+	 * symmetry between down link items in parent pages, and high keys in
+	 * children.  Together, they represent the part of the key space that
+	 * belongs to each page in the index.  For example, all children of the
+	 * root page will have negative infinity as a lower bound from root
+	 * negative infinity downlink, and positive infinity as an upper bound
+	 * (implicitly, from "imaginary" positive infinity high key in root).
+	 */
+	return !P_ISLEAF(opaque) && offset == P_FIRSTDATAKEY(opaque);
+}
+
+/*
+ * Does the invariant hold that the key is less than or equal to a given upper
+ * bound offset item?
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static inline bool
+invariant_leq_offset(BtreeCheckState *state, ScanKey key,
+					 OffsetNumber upperbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, state->target, upperbound);
+
+	return cmp <= 0;
+}
+
+/*
+ * Does the invariant hold that the key is greater than or equal to a given
+ * lower bound offset item?
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static inline bool
+invariant_geq_offset(BtreeCheckState *state, ScanKey key,
+					 OffsetNumber lowerbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, state->target, lowerbound);
+
+	return cmp >= 0;
+}
+
+/*
+ * Does the invariant hold that the key is less than or equal to a given upper
+ * bound offset item, with the offset relating to a caller-supplied page that
+ * is not the current target page? Caller's non-target page is typically a
+ * child page of the target, checked as part of checking a property of the
+ * target page (i.e. the key comes from the target).
+ *
+ * If this function returns false, convention is that caller throws error due
+ * to corruption.
+ */
+static inline bool
+invariant_leq_nontarget_offset(BtreeCheckState *state,
+							   Page nontarget, ScanKey key,
+							   OffsetNumber upperbound)
+{
+	int16		natts = state->rel->rd_rel->relnatts;
+	int32		cmp;
+
+	cmp = _bt_compare(state->rel, natts, key, nontarget, upperbound);
+
+	return cmp <= 0;
+}
+
+/*
+ * Given a block number of a B-Tree page, return page in palloc()'d memory.
+ * While at it, perform some basic checks of the page.
+ *
+ * There is never an attempt to get a consistent view of multiple pages using
+ * multiple concurrent buffer locks; in general, we only acquire a single pin
+ * and buffer lock at a time, which is often all that the nbtree code requires.
+ *
+ * Operating on a copy of the page is useful because it prevents control
+ * getting stuck in an uninterruptible state when an underlying operator class
+ * misbehaves.
+ */
+static Page
+palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum)
+{
+	Buffer		buffer;
+	Page		page;
+	BTPageOpaque opaque;
+
+	page = palloc(BLCKSZ);
+
+	/*
+	 * We copy the page into local storage to avoid holding pin on the buffer
+	 * longer than we must.
+	 */
+	buffer = ReadBufferExtended(state->rel, MAIN_FORKNUM, blocknum, RBM_NORMAL,
+								state->checkstrategy);
+	LockBuffer(buffer, BT_READ);
+
+	/*
+	 * Perform the same basic sanity checking that nbtree itself performs for
+	 * every page:
+	 */
+	_bt_checkpage(state->rel, buffer);
+
+	/* Only use copy of page in palloc()'d memory */
+	memcpy(page, BufferGetPage(buffer), BLCKSZ);
+	UnlockReleaseBuffer(buffer);
+
+	opaque = (BTPageOpaque) PageGetSpecialPointer(page);
+
+	if (opaque->btpo_flags & BTP_META && blocknum != BTREE_METAPAGE)
+		ereport(ERROR,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+				 errmsg("invalid meta page found at block %u in index \"%s\"",
+						blocknum, RelationGetRelationName(state->rel))));
+
+	/* Check page from block that ought to be meta page */
+	if (blocknum == BTREE_METAPAGE)
+	{
+		BTMetaPageData *metad = BTPageGetMeta(page);
+
+		if (!(opaque->btpo_flags & BTP_META) ||
+			metad->btm_magic != BTREE_MAGIC)
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("index \"%s\" meta page is corrupt",
+							RelationGetRelationName(state->rel))));
+
+		if (metad->btm_version != BTREE_VERSION)
+			ereport(ERROR,
+					(errcode(ERRCODE_INDEX_CORRUPTED),
+					 errmsg("version mismatch in index \"%s\": file version %d, code version %d",
+							RelationGetRelationName(state->rel),
+							metad->btm_version, BTREE_VERSION)));
+	}
+
+	/*
+	 * Deleted pages have no sane "level" field, so can only check non-deleted
+	 * page level
+	 */
+	if (P_ISLEAF(opaque) && !P_ISDELETED(opaque) && opaque->btpo.level != 0)
+		ereport(ERROR,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+			errmsg("invalid leaf page level %u for block %u in index \"%s\"",
+		opaque->btpo.level, blocknum, RelationGetRelationName(state->rel))));
+
+	if (blocknum != BTREE_METAPAGE && !P_ISLEAF(opaque) &&
+		!P_ISDELETED(opaque) && opaque->btpo.level == 0)
+		ereport(ERROR,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+		 errmsg("invalid internal page level 0 for block %u in index \"%s\"",
+				opaque->btpo.level, RelationGetRelationName(state->rel))));
+
+	if (!P_ISLEAF(opaque) && P_HAS_GARBAGE(opaque))
+		ereport(ERROR,
+				(errcode(ERRCODE_INDEX_CORRUPTED),
+		   errmsg("internal page block %u in index \"%s\" has garbage items",
+				  blocknum, RelationGetRelationName(state->rel))));
+
+	return page;
+}
diff --git a/doc/src/sgml/amcheck.sgml b/doc/src/sgml/amcheck.sgml
new file mode 100644
index 0000000000..168d3f4397
--- /dev/null
+++ b/doc/src/sgml/amcheck.sgml
@@ -0,0 +1,275 @@
+<!-- doc/src/sgml/amcheck.sgml -->
+
+<sect1 id="amcheck" xreflabel="amcheck">
+ <title>amcheck</title>
+
+ <indexterm zone="amcheck">
+  <primary>amcheck</primary>
+ </indexterm>
+
+ <para>
+  The <filename>amcheck</> module provides functions that allow you to
+  verify the logical consistency of the structure of indexes.  If the
+  structure appears to be valid, no error is raised.
+ </para>
+
+ <para>
+  The functions verify various <emphasis>invariants</> in the
+  structure of the representation of particular indexes.  The
+  correctness of the access method functions behind index scans and
+  other important operations relies on these invariants always
+  holding.  For example, certain functions verify, among other things,
+  that all B-Tree pages have items in <quote>logical</> order (e.g.,
+  for B-Tree indexes on <type>text</>, index tuples should be in
+  collated lexical order).  If that particular invariant somehow fails
+  to hold, we can expect binary searches on the affected page to
+  incorrectly guide index scans, resulting in wrong answers to SQL
+  queries.  Problems like this can be very subtle.
+ </para>
+ <para>
+  Verification is performed using the same procedures as those used by
+  index scans themselves, which may be user-defined operator class
+  code.  For example, B-Tree index verification relies on comparisons
+  made with one or more B-Tree support function 1 routines.  See <xref
+  linkend="xindex-support"> for details of operator class support
+  functions.
+ </para>
+ <para>
+  <filename>amcheck</> functions may be used only by superusers.
+ </para>
+
+ <sect2>
+  <title>Functions</title>
+
+  <variablelist>
+   <varlistentry>
+    <term>
+     <function>bt_index_check(index regclass) returns void</function>
+     <indexterm>
+      <primary>bt_index_check</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>bt_index_check</function> tests that its target, a
+      B-Tree index, respects a variety of invariants.  Example usage:
+<screen>
+test=# SELECT bt_index_check(c.oid), c.relname, c.relpages
+FROM pg_index i
+JOIN pg_opclass op ON i.indclass[0] = op.oid
+JOIN pg_am am ON op.opcmethod = am.oid
+JOIN pg_class c ON i.indexrelid = c.oid
+JOIN pg_namespace n ON c.relnamespace = n.oid
+WHERE am.amname = 'btree' AND n.nspname = 'pg_catalog'
+-- Don't check temp tables, which may be from another session:
+AND c.relpersistence != 't'
+-- Function may throw an error when this is omitted:
+AND i.indisready AND i.indisvalid
+ORDER BY c.relpages DESC LIMIT 10;
+ bt_index_check |             relname             | relpages 
+----------------+---------------------------------+----------
+                | pg_depend_reference_index       |       43
+                | pg_depend_depender_index        |       40
+                | pg_proc_proname_args_nsp_index  |       31
+                | pg_description_o_c_o_index      |       21
+                | pg_attribute_relid_attnam_index |       14
+                | pg_proc_oid_index               |       10
+                | pg_attribute_relid_attnum_index |        9
+                | pg_amproc_fam_proc_index        |        5
+                | pg_amop_opr_fam_index           |        5
+                | pg_amop_fam_strat_index         |        5
+(10 rows)
+</screen>
+      This example shows a session that performs verification of every
+      catalog index in the database <quote>test</>.  Details of just
+      the 10 largest indexes verified are displayed.  Since no error
+      is raised, all indexes tested appear to be logically consistent.
+      Naturally, this query could easily be changed to call
+      <function>bt_index_check</function> for every index in the
+      database where verification is supported.
+     </para>
+     <para>
+      An <literal>AccessShareLock</> is acquired on the target index
+      by <function>bt_index_check</function>.  This lock mode is the
+      same lock mode acquired on relations by simple
+      <literal>SELECT</> statements.
+      <function>bt_index_check</function> does not verify invariants
+      that span child/parent relationships, nor does it verify that
+      the target index is consistent with its heap relation.  When a
+      routine, lightweight test for corruption is required in a live
+      production environment, using
+      <function>bt_index_check</function> often provides the best
+      trade-off between thoroughness of verification and limiting the
+      impact on application performance and availability.
+     </para>
+    </listitem>
+   </varlistentry>
+
+   <varlistentry>
+    <term>
+     <function>bt_index_parent_check(index regclass) returns void</function>
+     <indexterm>
+      <primary>bt_index_parent_check</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>bt_index_parent_check</function> tests that its
+      target, a B-Tree index, respects a variety of invariants.  The
+      checks performed by <function>bt_index_parent_check</function>
+      are a superset of the checks performed by
+      <function>bt_index_check</function>.
+      <function>bt_index_parent_check</function> can be thought of as
+      a more thorough variant of <function>bt_index_check</function>:
+      unlike <function>bt_index_check</function>,
+      <function>bt_index_parent_check</function> also checks
+      invariants that span parent/child relationships.  However, it
+      does not verify that the target index is consistent with its
+      heap relation.  <function>bt_index_parent_check</function>
+      follows the general convention of raising an error if it finds a
+      logical inconsistency or other problem.
+     </para>
+     <para>
+      An <literal>ExclusiveLock</> is required on the target index by
+      <function>bt_index_parent_check</function> (a
+      <literal>ShareLock</> is also acquired on the heap relation).
+      These locks prevent concurrent data modification from
+      <command>INSERT</>, <command>UPDATE</>, and <command>DELETE</>
+      commands.  The locks also prevent the underlying relation from
+      being concurrently processed by <command>VACUUM</>, as well as
+      all other utility commands.  Note that the function holds locks
+      for the entire duration of the transaction, so there can be a
+      significant advantage to verifying each index individually, each
+      in its own dedicated transaction.
+     </para>
+     <para>
+      <function>bt_index_parent_check</function>'s additional
+      verification is more likely to detect various pathological
+      cases.  These cases may involve an incorrectly implemented
+      B-Tree operator class used by the index that is checked, or,
+      hypothetically, undiscovered bugs in the underlying B-Tree index
+      access method code.  Note that
+      <function>bt_index_parent_check</function> cannot be used when
+      Hot Standby mode is enabled (i.e., on read-only physical
+      replicas), unlike <function>bt_index_check</function>.
+     </para>
+    </listitem>
+   </varlistentry>
+  </variablelist>
+ </sect2>
+
+ <sect2>
+  <title>Using <filename>amcheck</> effectively</title>
+
+ <para>
+  <filename>amcheck</> can be effective at detecting various types of
+  failure modes that <link
+  linkend="app-initdb-data-checksums"><application>data page
+  checksums</></link> will always fail to catch.  These include:
+
+  <itemizedlist>
+   <listitem>
+    <para>
+     Structural inconsistencies caused by incorrect operator class
+     implementations.
+    </para>
+    <para>
+     This includes issues caused by the comparison rules of operating
+     system collations changing. Comparisons of datums of a collatable
+     type like <type>text</> must be immutable (just as all
+     comparisons used for B-Tree index scans must be immutable), which
+     implies that operating system collation rules must never change.
+     Though rare, updates to operating system collation rules can
+     cause these issues. More commonly, an inconsistency in the
+     collation order between a master server and a standby server is
+     implicated, possibly because the <emphasis>major</> operating
+     system version in use is inconsistent.  Such inconsistencies will
+     generally only arise on standby servers, and so can generally
+     only be detected on standby servers.
+    </para>
+    <para>
+     If a problem like this arises, it may not affect each individual
+     index that is ordered using an affected collation, simply because
+     <emphasis>indexed</> values might happen to have the same
+     absolute ordering regardless of the behavioral inconsistency. See
+     <xref linkend="locale"> and <xref linkend="collation"> for
+     further details about how <productname>PostgreSQL</> uses
+     operating system locales and collations.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Corruption caused by hypothetical undiscovered bugs in the
+     underlying <productname>PostgreSQL</> access method code or sort
+     code.
+    </para>
+    <para>
+     Automatic verification of the structural integrity of indexes
+     plays a role in the general testing of new or proposed
+     <productname>PostgreSQL</> features that could plausibly allow a
+     logical inconsistency to be introduced.  One obvious testing
+     strategy is to call <filename>amcheck</> functions continuously
+     when running the standard regression tests.  See <xref
+     linkend="regress-run"> for details on running the tests.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Filesystem or storage subsystem faults where checksums happen to
+     simply not be enabled.
+    </para>
+    <para>
+     Note that <filename>amcheck</> examines a page as represented in some
+     shared memory buffer at the time of verification if there is only a
+     shared buffer hit when accessing the block. Consequently,
+     <filename>amcheck</> does not necessarily examine data read from the
+     filesystem at the time of verification. Note that when checksums are
+     enabled, <filename>amcheck</> may raise an error due to a checksum
+     failure when a corrupt block is read into a buffer.
+    </para>
+   </listitem>
+   <listitem>
+    <para>
+     Corruption caused by faulty RAM, and the broader memory subsystem
+     and operating system.
+    </para>
+    <para>
+     <productname>PostgreSQL</> does not protect against correctable
+     memory errors and it is assumed you will operate using RAM that
+     uses industry standard Error Correcting Codes (ECC) or better
+     protection.  However, ECC memory is typically only immune to
+     single-bit errors, and should not be assumed to provide
+     <emphasis>absolute</emphasis> protection against failures that
+     result in memory corruption.
+    </para>
+   </listitem>
+  </itemizedlist>
+  In general, <filename>amcheck</> can only prove the presence of
+  corruption; it cannot prove its absence.
+ </para>
+
+ </sect2>
+ <sect2>
+  <title>Repairing corruption</title>
+ <para>
+  No error concerning corruption raised by <filename>amcheck</> should
+  ever be a false positive.  In practice, <filename>amcheck</> is more
+  likely to find software bugs than problems with hardware.
+  <filename>amcheck</> raises errors in the event of conditions that,
+  by definition, should never happen, and so careful analysis of
+  <filename>amcheck</> errors is often required.
+ </para>
+ <para>
+  There is no general method of repairing problems that
+  <filename>amcheck</> detects.  An explanation for the root cause of
+  an invariant violation should be sought.  <xref
+  linkend="pageinspect"> may play a useful role in diagnosing
+  corruption that <filename>amcheck</> detects.  A <command>REINDEX</>
+  may not be effective in repairing corruption.
+ </para>
+
+ </sect2>
+
+</sect1>
diff --git a/doc/src/sgml/contrib.sgml b/doc/src/sgml/contrib.sgml
index 03e5889839..eaaa36cb87 100644
--- a/doc/src/sgml/contrib.sgml
+++ b/doc/src/sgml/contrib.sgml
@@ -103,6 +103,7 @@ CREATE EXTENSION <replaceable>module_name</> FROM unpackaged;
  </para>
 
  &adminpack;
+ &amcheck;
  &auth-delay;
  &auto-explain;
  &bloom;
diff --git a/doc/src/sgml/filelist.sgml b/doc/src/sgml/filelist.sgml
index e7aa92f914..6782f07aea 100644
--- a/doc/src/sgml/filelist.sgml
+++ b/doc/src/sgml/filelist.sgml
@@ -107,6 +107,7 @@
 <!-- contrib information -->
 <!ENTITY contrib         SYSTEM "contrib.sgml">
 <!ENTITY adminpack       SYSTEM "adminpack.sgml">
+<!ENTITY amcheck         SYSTEM "amcheck.sgml">
 <!ENTITY auth-delay      SYSTEM "auth-delay.sgml">
 <!ENTITY auto-explain    SYSTEM "auto-explain.sgml">
 <!ENTITY bloom           SYSTEM "bloom.sgml">
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 296552e394..3487f7becb 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -244,6 +244,8 @@ BrinRevmap
 BrinSpecialSpace
 BrinTuple
 BrinValues
+BtreeCheckState
+BtreeLevel
 Bucket
 BufFile
 Buffer
-- 
2.11.0.22.g8d7a455.dirty

From ecb145091ad8ebc48fe25d55c76a2663a9c1ef52 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Thu, 9 Mar 2017 15:50:27 -0800
Subject: [PATCH 2/2] Cleanups & tests.

---
 contrib/amcheck/Makefile                 |   4 +-
 contrib/amcheck/amcheck.control          |   2 +-
 contrib/amcheck/expected/check.out       |   1 +
 contrib/amcheck/expected/check_btree.out |  87 ++++++++++++++++++++++
 contrib/amcheck/sql/check.sql            |   1 +
 contrib/amcheck/sql/check_btree.sql      |  59 +++++++++++++++
 contrib/amcheck/verify_nbtree.c          | 119 +++++++++++++++++--------------
 doc/src/sgml/amcheck.sgml                |  14 ++--
 8 files changed, 223 insertions(+), 64 deletions(-)
 create mode 100644 contrib/amcheck/expected/check.out
 create mode 100644 contrib/amcheck/expected/check_btree.out
 create mode 100644 contrib/amcheck/sql/check.sql
 create mode 100644 contrib/amcheck/sql/check_btree.sql

diff --git a/contrib/amcheck/Makefile b/contrib/amcheck/Makefile
index f14c7aa58b..43bed919ae 100644
--- a/contrib/amcheck/Makefile
+++ b/contrib/amcheck/Makefile
@@ -5,7 +5,9 @@ OBJS		= verify_nbtree.o $(WIN32RES)
 
 EXTENSION = amcheck
 DATA = amcheck--1.0.sql
-PGFILEDESC = "amcheck - functions to verify access method invariants"
+PGFILEDESC = "amcheck - function for verifying relation integrity"
+
+REGRESS = check check_btree
 
 ifdef USE_PGXS
 PG_CONFIG = pg_config
diff --git a/contrib/amcheck/amcheck.control b/contrib/amcheck/amcheck.control
index 180f150e7f..05e2861d7a 100644
--- a/contrib/amcheck/amcheck.control
+++ b/contrib/amcheck/amcheck.control
@@ -1,5 +1,5 @@
 # amcheck extension
-comment = 'verify access method invariants'
+comment = 'functions for verifying relation integrity'
 default_version = '1.0'
 module_pathname = '$libdir/amcheck'
 relocatable = true
diff --git a/contrib/amcheck/expected/check.out b/contrib/amcheck/expected/check.out
new file mode 100644
index 0000000000..5b3e6d530c
--- /dev/null
+++ b/contrib/amcheck/expected/check.out
@@ -0,0 +1 @@
+CREATE EXTENSION amcheck;
diff --git a/contrib/amcheck/expected/check_btree.out b/contrib/amcheck/expected/check_btree.out
new file mode 100644
index 0000000000..851b5cdcc1
--- /dev/null
+++ b/contrib/amcheck/expected/check_btree.out
@@ -0,0 +1,87 @@
+-- minimal test, basically just verifying that amcheck
+CREATE TABLE bttest_a(id int8);
+CREATE TABLE bttest_b(id int8);
+INSERT INTO bttest_a SELECT * FROM generate_series(1, 100000);
+INSERT INTO bttest_b SELECT * FROM generate_series(100000, 1, -1);
+CREATE INDEX bttest_a_idx ON bttest_a USING btree (id);
+CREATE INDEX bttest_b_idx ON bttest_b USING btree (id);
+CREATE ROLE bttest_role;
+-- verify permissions are checked (error due to function not callable)
+SET ROLE bttest_role;
+SELECT bt_index_check('bttest_a_idx'::regclass);
+ERROR:  permission denied for function bt_index_check
+SELECT bt_index_parent_check('bttest_a_idx'::regclass);
+ERROR:  permission denied for function bt_index_parent_check
+RESET ROLE;
+-- we, intentionally, don't check relation permissions - it's useful
+-- to run this cluster-wide with a restricted account, and as tested
+-- above explicit permission has to be granted for that.
+GRANT EXECUTE ON FUNCTION bt_index_check(regclass) TO bttest_role;
+GRANT EXECUTE ON FUNCTION bt_index_parentcheck(regclass) TO bttest_role;
+ERROR:  function bt_index_parentcheck(regclass) does not exist
+SET ROLE bttest_role;
+SELECT bt_index_check('bttest_a_idx');
+ bt_index_check 
+----------------
+ 
+(1 row)
+
+SELECT bt_index_parent_check('bttest_a_idx');
+ERROR:  permission denied for function bt_index_parent_check
+RESET ROLE;
+-- verify plain tables are rejected (error)
+SELECT bt_index_check('bttest_a');
+ERROR:  "bttest_a" is not an index
+SELECT bt_index_parent_check('bttest_a');
+ERROR:  "bttest_a" is not an index
+-- verify non-existing indexes are rejected (error)
+SELECT bt_index_check(17);
+ERROR:  could not open relation with OID 17
+SELECT bt_index_parent_check(17);
+ERROR:  could not open relation with OID 17
+-- verify wrong index types are rejected (error)
+BEGIN;
+CREATE INDEX bttest_a_brin_idx ON bttest_a USING brin(id);
+SELECT bt_index_parent_check('bttest_a_brin_idx');
+ERROR:  only B-Tree indexes are supported as targets for verification
+DETAIL:  Relation "bttest_a_brin_idx" is not a B-Tree index.
+ROLLBACK;
+-- normal check outside of xact
+SELECT bt_index_check('bttest_a_idx');
+ bt_index_check 
+----------------
+ 
+(1 row)
+
+-- more expansive test
+SELECT bt_index_parent_check('bttest_b_idx');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+BEGIN;
+SELECT bt_index_check('bttest_a_idx');
+ bt_index_check 
+----------------
+ 
+(1 row)
+
+SELECT bt_index_parent_check('bttest_b_idx');
+ bt_index_parent_check 
+-----------------------
+ 
+(1 row)
+
+-- make sure we don't have any leftover locks
+SELECT * FROM pg_locks WHERE relation IN ('bttest_a_idx'::regclass, 'bttest_b_idx'::regclass);
+ locktype | database | relation | page | tuple | virtualxid | transactionid | classid | objid | objsubid | virtualtransaction | pid | mode | granted | fastpath 
+----------+----------+----------+------+-------+------------+---------------+---------+-------+----------+--------------------+-----+------+---------+----------
+(0 rows)
+
+COMMIT;
+-- cleanup
+DROP TABLE bttest_a;
+DROP TABLE bttest_b;
+DROP OWNED BY bttest_role; -- permissions
+DROP ROLE bttest_role;
diff --git a/contrib/amcheck/sql/check.sql b/contrib/amcheck/sql/check.sql
new file mode 100644
index 0000000000..5b3e6d530c
--- /dev/null
+++ b/contrib/amcheck/sql/check.sql
@@ -0,0 +1 @@
+CREATE EXTENSION amcheck;
diff --git a/contrib/amcheck/sql/check_btree.sql b/contrib/amcheck/sql/check_btree.sql
new file mode 100644
index 0000000000..53377f6da9
--- /dev/null
+++ b/contrib/amcheck/sql/check_btree.sql
@@ -0,0 +1,59 @@
+-- minimal test, basically just verifying that amcheck
+CREATE TABLE bttest_a(id int8);
+CREATE TABLE bttest_b(id int8);
+
+INSERT INTO bttest_a SELECT * FROM generate_series(1, 100000);
+INSERT INTO bttest_b SELECT * FROM generate_series(100000, 1, -1);
+
+CREATE INDEX bttest_a_idx ON bttest_a USING btree (id);
+CREATE INDEX bttest_b_idx ON bttest_b USING btree (id);
+
+CREATE ROLE bttest_role;
+
+-- verify permissions are checked (error due to function not callable)
+SET ROLE bttest_role;
+SELECT bt_index_check('bttest_a_idx'::regclass);
+SELECT bt_index_parent_check('bttest_a_idx'::regclass);
+RESET ROLE;
+
+-- we, intentionally, don't check relation permissions - it's useful
+-- to run this cluster-wide with a restricted account, and as tested
+-- above explicit permission has to be granted for that.
+GRANT EXECUTE ON FUNCTION bt_index_check(regclass) TO bttest_role;
+GRANT EXECUTE ON FUNCTION bt_index_parentcheck(regclass) TO bttest_role;
+SET ROLE bttest_role;
+SELECT bt_index_check('bttest_a_idx');
+SELECT bt_index_parent_check('bttest_a_idx');
+RESET ROLE;
+
+-- verify plain tables are rejected (error)
+SELECT bt_index_check('bttest_a');
+SELECT bt_index_parent_check('bttest_a');
+
+-- verify non-existing indexes are rejected (error)
+SELECT bt_index_check(17);
+SELECT bt_index_parent_check(17);
+
+-- verify wrong index types are rejected (error)
+BEGIN;
+CREATE INDEX bttest_a_brin_idx ON bttest_a USING brin(id);
+SELECT bt_index_parent_check('bttest_a_brin_idx');
+ROLLBACK;
+
+-- normal check outside of xact
+SELECT bt_index_check('bttest_a_idx');
+-- more expansive test
+SELECT bt_index_parent_check('bttest_b_idx');
+
+BEGIN;
+SELECT bt_index_check('bttest_a_idx');
+SELECT bt_index_parent_check('bttest_b_idx');
+-- make sure we don't have any leftover locks
+SELECT * FROM pg_locks WHERE relation IN ('bttest_a_idx'::regclass, 'bttest_b_idx'::regclass);
+COMMIT;
+
+-- cleanup
+DROP TABLE bttest_a;
+DROP TABLE bttest_b;
+DROP OWNED BY bttest_role; -- permissions
+DROP ROLE bttest_role;
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
index 4cef4c44ff..ad8e15ea67 100644
--- a/contrib/amcheck/verify_nbtree.c
+++ b/contrib/amcheck/verify_nbtree.c
@@ -43,8 +43,8 @@ PG_MODULE_MAGIC;
  * target is the point of reference for a verification operation.
  *
  * Other B-Tree pages may be allocated, but those are always auxiliary (e.g.,
- * they are current target's child pages).  Conceptually, problems are only
- * ever found in the current target page.	Each page found by verification's
+ * they are current target's child pages). Conceptually, problems are only
+ * ever found in the current target page. Each page found by verification's
  * left/right, top/bottom scan becomes the target exactly once.
  */
 typedef struct BtreeCheckState
@@ -92,6 +92,7 @@ typedef struct BtreeLevel
 PG_FUNCTION_INFO_V1(bt_index_check);
 PG_FUNCTION_INFO_V1(bt_index_parent_check);
 
+static void bt_index_check_internal(Oid indrelid, bool parentcheck);
 static inline void btree_index_checkable(Relation rel);
 static void bt_check_every_level(Relation rel, bool exclusivelylocked);
 static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state,
@@ -119,25 +120,15 @@ static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum);
  *
  * Verify integrity of B-Tree index.
  *
- * Only acquires AccessShareLock on index relation.  Does not consider
+ * Acquires AccessShareLock on heap & index relations.  Does not consider
  * invariants that exist between parent/child pages.
  */
 Datum
 bt_index_check(PG_FUNCTION_ARGS)
 {
-	Oid			relid = PG_GETARG_OID(0);
-	Relation	indrel;
+	Oid			indrelid = PG_GETARG_OID(0);
 
-	indrel = relation_open(relid, AccessShareLock);
-
-	/* Relation suitable for checking as B-Tree? */
-	btree_index_checkable(indrel);
-
-	/* Check index */
-	bt_check_every_level(indrel, false);
-
-	/* Close, but keep lock */
-	relation_close(indrel, NoLock);
+	bt_index_check_internal(indrelid, false);
 
 	PG_RETURN_VOID();
 }
@@ -147,36 +138,55 @@ bt_index_check(PG_FUNCTION_ARGS)
  *
  * Verify integrity of B-Tree index.
  *
- * Acquires ExclusiveLock on index relation, and ShareLock on the associated
- * heap relation, a bit like REINDEX.  Verifies that downlinks in parent pages
- * are valid lower bounds on child pages.
+ * Acquires ShareLock on heap & index relations.  Verifies that downlinks in
+ * parent pages are valid lower bounds on child pages.
  */
 Datum
 bt_index_parent_check(PG_FUNCTION_ARGS)
 {
 	Oid			indrelid = PG_GETARG_OID(0);
+
+	bt_index_check_internal(indrelid, true);
+
+	PG_RETURN_VOID();
+}
+
+/*
+ * Helper for bt_index_[parent_]check, coordinating the bulk of the work.
+ */
+static void
+bt_index_check_internal(Oid indrelid, bool parentcheck)
+{
 	Oid			heapid;
 	Relation	indrel;
 	Relation	heaprel;
+	LOCKMODE	lockmode;
+
+	if (parentcheck)
+		lockmode = ShareLock;
+	else
+		lockmode = AccessShareLock;
 
 	/*
-	 * We must lock table before index to avoid deadlocks.	However, if the
+	 * We must lock table before index to avoid deadlocks.  However, if the
 	 * passed indrelid isn't an index then IndexGetRelation() will fail.
 	 * Rather than emitting a not-very-helpful error message, postpone
 	 * complaining, expecting that the is-it-an-index test below will fail.
+	 *
+	 * In hot standby mode this will raise an error when parentcheck is true.
 	 */
 	heapid = IndexGetRelation(indrelid, true);
 	if (OidIsValid(heapid))
-		heaprel = heap_open(heapid, ShareLock);
+		heaprel = heap_open(heapid, lockmode);
 	else
 		heaprel = NULL;
 
 	/*
 	 * Open the target index relations separately (like relation_openrv(), but
 	 * with heap relation locked first to prevent deadlocking).  In hot
-	 * standby mode this will raise an error.
+	 * standby mode this will raise an error when parentcheck is true.
 	 */
-	indrel = index_open(indrelid, ExclusiveLock);
+	indrel = index_open(indrelid, lockmode);
 
 	/*
 	 * Since we did the IndexGetRelation call above without any lock, it's
@@ -195,19 +205,25 @@ bt_index_parent_check(PG_FUNCTION_ARGS)
 	btree_index_checkable(indrel);
 
 	/* Check index */
-	bt_check_every_level(indrel, true);
+	bt_check_every_level(indrel, parentcheck);
 
-	/* Close, but keep locks */
-	index_close(indrel, NoLock);
+	/*
+	 * Release locks early. That's ok here because nothing in the called
+	 * routines will trigger shared cache invalidations to be sent, so we can
+	 * relax the usual pattern of only releasing locks after commit.
+	 */
+	index_close(indrel, lockmode);
 	if (heaprel)
-		heap_close(heaprel, NoLock);
-
-	PG_RETURN_VOID();
+		heap_close(heaprel, lockmode);
 }
 
 /*
  * Basic checks about the suitability of a relation for checking as a B-Tree
  * index.
+ *
+ * NB: Intentionally not checking permissions, the function is normally not
+ * callable by non-superusers. If granted, it's useful to be able to check a
+ * whole cluster.
  */
 static inline void
 btree_index_checkable(Relation rel)
@@ -236,7 +252,7 @@ btree_index_checkable(Relation rel)
 }
 
 /*
- * Main entry point for B-Tree SQL-callable functions.	Walks the B-Tree in
+ * Main entry point for B-Tree SQL-callable functions. Walks the B-Tree in
  * logical order, verifying invariants as it goes.
  *
  * It is the caller's responsibility to acquire appropriate heavyweight lock on
@@ -265,7 +281,7 @@ bt_check_every_level(Relation rel, bool exclusivelylocked)
 	BtreeLevel	current;
 
 	/*
-	 * RecentGlobalXmin assertion matches index_getnext_tid().	See note on
+	 * RecentGlobalXmin assertion matches index_getnext_tid().  See note on
 	 * RecentGlobalXmin/B-Tree page deletion.
 	 */
 	Assert(TransactionIdIsValid(RecentGlobalXmin));
@@ -301,15 +317,13 @@ bt_check_every_level(Relation rel, bool exclusivelylocked)
 				(errcode(ERRCODE_NO_DATA),
 				 errmsg("harmless fast root mismatch in index %s",
 						RelationGetRelationName(rel)),
-				 errdetail_internal("Fast block %u (level %u) "
-									"differs from true root "
-									"block %u (level %u).",
+				 errdetail_internal("Fast block %u (level %u) differs from true root block %u (level %u).",
 									metad->btm_fastroot, metad->btm_fastlevel,
 									metad->btm_root, metad->btm_level)));
 
 	/*
 	 * Starting at the root, verify every level.  Move left to right, top to
-	 * bottom.	Note that there may be no pages other than the meta page (meta
+	 * bottom.  Note that there may be no pages other than the meta page (meta
 	 * page can indicate that root is P_NONE when the index is totally empty).
 	 */
 	previouslevel = InvalidBtreeLevel;
@@ -346,9 +360,9 @@ bt_check_every_level(Relation rel, bool exclusivelylocked)
  *
  * Returns state for next call, if any.  This includes left-most block number
  * one level lower that should be passed on next level/call, which is set to
- * P_NONE on last call here (when leaf level is verified).	Level numbers
+ * P_NONE on last call here (when leaf level is verified).  Level numbers
  * follow the nbtree convention: higher levels have higher numbers, because new
- * levels are added only due to a root page split.	Note that prior to the
+ * levels are added only due to a root page split.  Note that prior to the
  * first root page split, the root is also a leaf page, so there is always a
  * level 0 (leaf level), and it's always the last level processed.
  *
@@ -610,8 +624,7 @@ bt_target_page_check(BtreeCheckState *state)
 					(errcode(ERRCODE_INDEX_CORRUPTED),
 					 errmsg("high key invariant violated for index \"%s\"",
 							RelationGetRelationName(state->rel)),
-					 errdetail_internal("Index tid=%s points to %s tid=%s "
-										"page lsn=%X/%X.",
+					 errdetail_internal("Index tid=%s points to %s tid=%s page lsn=%X/%X.",
 										itid,
 										P_ISLEAF(topaque) ? "heap" : "index",
 										htid,
@@ -676,7 +689,7 @@ bt_target_page_check(BtreeCheckState *state)
 		 * already been performed for every other "real" item on target page
 		 * when last item is checked.  The difference is that the next item
 		 * (the item that is compared to target's last item) needs to come
-		 * from the next/sibling page.	There may not be such an item
+		 * from the next/sibling page.  There may not be such an item
 		 * available from sibling for various reasons, though (e.g., target is
 		 * the rightmost page on level).
 		 */
@@ -716,8 +729,7 @@ bt_target_page_check(BtreeCheckState *state)
 						(errcode(ERRCODE_INDEX_CORRUPTED),
 						 errmsg("cross page item order invariant violated for index \"%s\"",
 								RelationGetRelationName(state->rel)),
-						 errdetail_internal("Last item on page tid=(%u,%u) "
-											"page lsn=%X/%X.",
+						 errdetail_internal("Last item on page tid=(%u,%u) page lsn=%X/%X.",
 											state->targetblock, offset,
 											(uint32) (state->targetlsn >> 32),
 											(uint32) state->targetlsn)));
@@ -787,7 +799,7 @@ bt_right_page_check_scankey(BtreeCheckState *state)
 	 * (or left link, or downlink) and find its sibling, because recycling
 	 * does not occur until no possible index scan could land on the page.
 	 * Index scans can follow links with nothing more than their snapshot as
-	 * an interlock and be sure of at least that much.	(See page
+	 * an interlock and be sure of at least that much.  (See page
 	 * recycling/RecentGlobalXmin notes in nbtree README.)
 	 *
 	 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
@@ -860,7 +872,7 @@ bt_right_page_check_scankey(BtreeCheckState *state)
 	 * deleted) implies that target page was not merged into from the right by
 	 * deletion; the key space at or after target never moved left.  Target's
 	 * parent either has the same downlink to target as before, or a <=
-	 * downlink due to deletion at the left of target.	Target either has the
+	 * downlink due to deletion at the left of target.  Target either has the
 	 * same highkey as before, or a highkey <= before when there is a page
 	 * split. (The rightmost concurrently-split-from-target-page page will
 	 * still have the same highkey as target was originally found to have,
@@ -907,7 +919,7 @@ bt_right_page_check_scankey(BtreeCheckState *state)
 	 * that happens only to determine if there was a concurrent page deletion
 	 * of a reference page, and just like us if there was a page deletion of
 	 * that reference page it means we can move on from caring about the
-	 * reference page.	See the nbtree README for a full description of how
+	 * reference page.  See the nbtree README for a full description of how
 	 * that works.
 	 */
 	nline = PageGetMaxOffsetNumber(rightpage);
@@ -946,7 +958,7 @@ bt_right_page_check_scankey(BtreeCheckState *state)
 	}
 
 	/*
-	 * Return first real item scankey.	Note that this relies on right page
+	 * Return first real item scankey.  Note that this relies on right page
 	 * memory remaining allocated.
 	 */
 	return _bt_mkscankey(state->rel,
@@ -956,7 +968,7 @@ bt_right_page_check_scankey(BtreeCheckState *state)
 /*
  * Checks one of target's downlink against its child page.
  *
- * Conceptually, the target page continues to be what is checked here.	The
+ * Conceptually, the target page continues to be what is checked here.  The
  * target block is still blamed in the event of finding an invariant violation.
  * The downlink insertion into the target is probably where any problem raised
  * here arises, and there is no such thing as a parent link, so doing the
@@ -977,8 +989,8 @@ bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
 	 *
 	 * NB: In general, page deletion deletes the right sibling's downlink, not
 	 * the downlink of the page being deleted; the deleted page's downlink is
-	 * reused for its sibling.	The key space is thereby consolidated between
-	 * the deleted page and its right sibling.	(We cannot delete a parent
+	 * reused for its sibling.  The key space is thereby consolidated between
+	 * the deleted page and its right sibling.  (We cannot delete a parent
 	 * page's rightmost child unless it is the last child page, and we intend
 	 * to also delete the parent itself.)
 	 *
@@ -1041,11 +1053,10 @@ bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
 					(errcode(ERRCODE_INDEX_CORRUPTED),
 					 errmsg("down-link lower bound invariant violated for index \"%s\"",
 							RelationGetRelationName(state->rel)),
-				errdetail_internal("Parent block=%u child index tid=(%u,%u) "
-								   "parent page lsn=%X/%X.",
-								   state->targetblock, childblock, offset,
-								   (uint32) (state->targetlsn >> 32),
-								   (uint32) state->targetlsn)));
+					 errdetail_internal("Parent block=%u child index tid=(%u,%u) parent page lsn=%X/%X.",
+									  state->targetblock, childblock, offset,
+										(uint32) (state->targetlsn >> 32),
+										(uint32) state->targetlsn)));
 	}
 
 	pfree(child);
@@ -1066,7 +1077,7 @@ offset_is_negative_infinity(BTPageOpaque opaque, OffsetNumber offset)
 {
 	/*
 	 * For internal pages only, the first item after high key, if any, is
-	 * negative infinity item.	Internal pages always have a negative infinity
+	 * negative infinity item.  Internal pages always have a negative infinity
 	 * item, whereas leaf pages never have one.  This implies that negative
 	 * infinity item is either first or second line item, or there is none
 	 * within page.
diff --git a/doc/src/sgml/amcheck.sgml b/doc/src/sgml/amcheck.sgml
index 168d3f4397..893a5b41d9 100644
--- a/doc/src/sgml/amcheck.sgml
+++ b/doc/src/sgml/amcheck.sgml
@@ -24,7 +24,7 @@
   collated lexical order).  If that particular invariant somehow fails
   to hold, we can expect binary searches on the affected page to
   incorrectly guide index scans, resulting in wrong answers to SQL
-  queries.  Problems like this can be very subtle.
+  queries.
  </para>
  <para>
   Verification is performed using the same procedures as those used by
@@ -90,9 +90,9 @@ ORDER BY c.relpages DESC LIMIT 10;
       database where verification is supported.
      </para>
      <para>
-      An <literal>AccessShareLock</> is acquired on the target index
-      by <function>bt_index_check</function>.  This lock mode is the
-      same lock mode acquired on relations by simple
+      <function>bt_index_check</function> acquires an <literal>AccessShareLock</>
+      on the target index and the heap relation it belongs to. This lock mode
+      is the same lock mode acquired on relations by simple
       <literal>SELECT</> statements.
       <function>bt_index_check</function> does not verify invariants
       that span child/parent relationships, nor does it verify that
@@ -132,7 +132,7 @@ ORDER BY c.relpages DESC LIMIT 10;
       logical inconsistency or other problem.
      </para>
      <para>
-      An <literal>ExclusiveLock</> is required on the target index by
+      A <literal>ShareLock</> is required on the target index by
       <function>bt_index_parent_check</function> (a
       <literal>ShareLock</> is also acquired on the heap relation).
       These locks prevent concurrent data modification from
@@ -140,9 +140,7 @@ ORDER BY c.relpages DESC LIMIT 10;
       commands.  The locks also prevent the underlying relation from
       being concurrently processed by <command>VACUUM</>, as well as
       all other utility commands.  Note that the function holds locks
-      for the entire duration of the transaction, so there can be a
-      significant advantage to verifying each index individually, each
-      in its own dedicated transaction.
+      only while running, not for the entire transaction.
      </para>
      <para>
       <function>bt_index_parent_check</function>'s additional
-- 
2.11.0.22.g8d7a455.dirty

From 05a8c0de7da7cd9ee4d8436abdf8368c1cf8ac19 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Thu, 9 Mar 2017 19:17:07 -0800
Subject: [PATCH] Fix amcheck build on Windows.

Remove documenting assertion around RecentGlobalXmin, rather than
marking it PGDLLIMPORT.

In passing, update some comments that did not reflect the state of
amcheck as-committed.
---
 contrib/amcheck/verify_nbtree.c | 74 +++++++++++++++++++----------------------
 1 file changed, 35 insertions(+), 39 deletions(-)

diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
index 5724aa6..d21b209 100644
--- a/contrib/amcheck/verify_nbtree.c
+++ b/contrib/amcheck/verify_nbtree.c
@@ -26,7 +26,6 @@
 #include "miscadmin.h"
 #include "storage/lmgr.h"
 #include "utils/memutils.h"
-#include "utils/snapmgr.h"
 
 
 PG_MODULE_MAGIC;
@@ -55,8 +54,8 @@ typedef struct BtreeCheckState
 
 	/* B-Tree Index Relation */
 	Relation	rel;
-	/* ExclusiveLock held? */
-	bool		exclusivelylocked;
+	/* ShareLock held on heap/index, rather than AccessShareLock? */
+	bool		strongerlock;
 	/* Per-page context */
 	MemoryContext targetcontext;
 	/* Buffer access strategy */
@@ -94,7 +93,7 @@ PG_FUNCTION_INFO_V1(bt_index_parent_check);
 
 static void bt_index_check_internal(Oid indrelid, bool parentcheck);
 static inline void btree_index_checkable(Relation rel);
-static void bt_check_every_level(Relation rel, bool exclusivelylocked);
+static void bt_check_every_level(Relation rel, bool strongerlock);
 static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state,
 							 BtreeLevel level);
 static void bt_target_page_check(BtreeCheckState *state);
@@ -256,23 +255,26 @@ btree_index_checkable(Relation rel)
  * logical order, verifying invariants as it goes.
  *
  * It is the caller's responsibility to acquire appropriate heavyweight lock on
- * the index relation, and advise us if extra checks are safe when an
- * ExclusiveLock is held.
+ * the index relation, and advise us if extra checks are safe when a ShareLock
+ * is held.
  *
- * An ExclusiveLock is generally assumed to prevent any kind of physical
+ * A ShareLock is generally assumed to prevent any kind of physical
  * modification to the index structure, including modifications that VACUUM may
  * make.  This does not include setting of the LP_DEAD bit by concurrent index
  * scans, although that is just metadata that is not able to directly affect
  * any check performed here.  Any concurrent process that might act on the
  * LP_DEAD bit being set (recycle space) requires a heavyweight lock that
- * cannot be held while we hold an ExclusiveLock.  (Besides, even if that could
+ * cannot be held while we hold a ShareLock.  (Besides, even if that could
  * happen, the ad-hoc recycling when a page might otherwise split is performed
  * per-page, and requires an exclusive buffer lock, which wouldn't cause us
  * trouble.  _bt_delitems_vacuum() may only delete leaf items, and so the extra
  * parent/child check cannot be affected.)
+ *
+ * Note that we rely on RecentGlobalXmin interlock against recycling, just like
+ * standard index scans.  See note on RecentGlobalXmin/B-Tree page deletion.
  */
 static void
-bt_check_every_level(Relation rel, bool exclusivelylocked)
+bt_check_every_level(Relation rel, bool strongerlock)
 {
 	BtreeCheckState *state;
 	Page		metapage;
@@ -281,17 +283,11 @@ bt_check_every_level(Relation rel, bool exclusivelylocked)
 	BtreeLevel	current;
 
 	/*
-	 * RecentGlobalXmin assertion matches index_getnext_tid().  See note on
-	 * RecentGlobalXmin/B-Tree page deletion.
-	 */
-	Assert(TransactionIdIsValid(RecentGlobalXmin));
-
-	/*
 	 * Initialize state for entire verification operation
 	 */
 	state = palloc(sizeof(BtreeCheckState));
 	state->rel = rel;
-	state->exclusivelylocked = exclusivelylocked;
+	state->strongerlock = strongerlock;
 	/* Create context for page */
 	state->targetcontext = AllocSetContextCreate(CurrentMemoryContext,
 												 "amcheck context",
@@ -353,7 +349,7 @@ bt_check_every_level(Relation rel, bool exclusivelylocked)
 
 /*
  * Given a left-most block at some level, move right, verifying each page
- * individually (with more verification across pages for "exclusivelylocked"
+ * individually (with more verification across pages for "strongerlock"
  * callers).  Caller should pass the true root page as the leftmost initially,
  * working their way down by passing what is returned for the last call here
  * until level 0 (leaf page level) was reached.
@@ -428,7 +424,7 @@ bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
 			 * locking, check that the first valid page meets caller's
 			 * expectations.
 			 */
-			if (state->exclusivelylocked)
+			if (state->strongerlock)
 			{
 				if (!P_LEFTMOST(opaque))
 					ereport(ERROR,
@@ -482,7 +478,7 @@ bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
 			 */
 		}
 
-		if (state->exclusivelylocked && opaque->btpo_prev != leftcurrent)
+		if (state->strongerlock && opaque->btpo_prev != leftcurrent)
 			ereport(ERROR,
 					(errcode(ERRCODE_INDEX_CORRUPTED),
 					 errmsg("left link/right link pair in index \"%s\" not in agreement",
@@ -541,7 +537,7 @@ nextpage:
  *	 "real" data item on the page to the right (if such a first item is
  *	 available).
  *
- * Furthermore, when state passed shows ExclusiveLock held, and target page is
+ * Furthermore, when state passed shows ShareLock held, and target page is
  * internal page, function also checks:
  *
  * - That all child pages respect downlinks lower bound.
@@ -597,8 +593,8 @@ bt_target_page_check(BtreeCheckState *state)
 		 * page items.
 		 *
 		 * We prefer to check all items against high key rather than checking
-		 * just the first and trusting that the operator class obeys the
-		 * transitive law (which implies that all subsequent items also
+		 * just the last and trusting that the operator class obeys the
+		 * transitive law (which implies that all previous items also
 		 * respected the high key invariant if they pass the item order
 		 * check).
 		 *
@@ -705,12 +701,12 @@ bt_target_page_check(BtreeCheckState *state)
 			{
 				/*
 				 * As explained at length in bt_right_page_check_scankey(),
-				 * there is a known !exclusivelylocked race that could account
+				 * there is a known !strongerlock race that could account
 				 * for apparent violation of invariant, which we must check
 				 * for before actually proceeding with raising error.  Our
 				 * canary condition is that target page was deleted.
 				 */
-				if (!state->exclusivelylocked)
+				if (!state->strongerlock)
 				{
 					/* Get fresh copy of target page */
 					state->target = palloc_btree_page(state, state->targetblock);
@@ -718,7 +714,7 @@ bt_target_page_check(BtreeCheckState *state)
 					topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
 
 					/*
-					 * All !exclusivelylocked checks now performed; just
+					 * All !strongerlock checks now performed; just
 					 * return
 					 */
 					if (P_IGNORE(topaque))
@@ -740,11 +736,11 @@ bt_target_page_check(BtreeCheckState *state)
 		 * * Downlink check *
 		 *
 		 * Additional check of child items iff this is an internal page and
-		 * caller holds an ExclusiveLock.  This happens for every downlink
-		 * (item) in target excluding the negative-infinity downlink (again,
-		 * this is because it has no useful value to compare).
+		 * caller holds a ShareLock.  This happens for every downlink (item) in
+		 * target excluding the negative-infinity downlink (again, this is
+		 * because it has no useful value to compare).
 		 */
-		if (!P_ISLEAF(topaque) && state->exclusivelylocked)
+		if (!P_ISLEAF(topaque) && state->strongerlock)
 		{
 			BlockNumber childblock = ItemPointerGetBlockNumber(&(itup->t_tid));
 
@@ -766,7 +762,7 @@ bt_target_page_check(BtreeCheckState *state)
  * with different parent page).  If no such valid item is available, return
  * NULL instead.
  *
- * Note that !exclusivelylocked callers must reverify that target page has not
+ * Note that !strongerlock callers must reverify that target page has not
  * been concurrently deleted.
  */
 static ScanKey
@@ -833,14 +829,14 @@ bt_right_page_check_scankey(BtreeCheckState *state)
 	}
 
 	/*
-	 * No ExclusiveLock held case -- why it's safe to proceed.
+	 * No ShareLock held case -- why it's safe to proceed.
 	 *
 	 * Problem:
 	 *
 	 * We must avoid false positive reports of corruption when caller treats
 	 * item returned here as an upper bound on target's last item.  In
 	 * general, false positives are disallowed.  Avoiding them here when
-	 * caller is !exclusivelylocked is subtle.
+	 * caller is !strongerlock is subtle.
 	 *
 	 * A concurrent page deletion by VACUUM of the target page can result in
 	 * the insertion of items on to this right sibling page that would
@@ -892,7 +888,7 @@ bt_right_page_check_scankey(BtreeCheckState *state)
 	 *
 	 * Top level tree walk caller moves on to next page (makes it the new
 	 * target) following recovery from this race.  (cf.  The rationale for
-	 * child/downlink verification needing an ExclusiveLock within
+	 * child/downlink verification needing a ShareLock within
 	 * bt_downlink_check(), where page deletion is also the main source of
 	 * trouble.)
 	 *
@@ -984,8 +980,8 @@ bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
 	BTPageOpaque copaque;
 
 	/*
-	 * Caller must have ExclusiveLock on target relation, because of
-	 * considerations around page deletion by VACUUM.
+	 * Caller must have ShareLock on target relation, because of considerations
+	 * around page deletion by VACUUM.
 	 *
 	 * NB: In general, page deletion deletes the right sibling's downlink, not
 	 * the downlink of the page being deleted; the deleted page's downlink is
@@ -994,8 +990,8 @@ bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
 	 * page's rightmost child unless it is the last child page, and we intend
 	 * to also delete the parent itself.)
 	 *
-	 * If this verification happened without an ExclusiveLock, the following
-	 * race condition could cause false positives:
+	 * If this verification happened without a ShareLock, the following race
+	 * condition could cause false positives:
 	 *
 	 * In general, concurrent page deletion might occur, including deletion of
 	 * the left sibling of the child page that is examined here.  If such a
@@ -1009,7 +1005,7 @@ bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
 	 * part of deletion's first phase.)
 	 *
 	 * Note that while the cross-page-same-level last item check uses a trick
-	 * that allows it to perform verification for !exclusivelylocked callers,
+	 * that allows it to perform verification for !strongerlock callers,
 	 * a similar trick seems difficult here.  The trick that that other check
 	 * uses is, in essence, to lock down race conditions to those that occur
 	 * due to concurrent page deletion of the target; that's a race that can
@@ -1021,7 +1017,7 @@ bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
 	 * locks on both child and left-of-child pages).  That's unacceptable for
 	 * amcheck functions on general principle, though.
 	 */
-	Assert(state->exclusivelylocked);
+	Assert(state->strongerlock);
 
 	/*
 	 * Verify child page has the downlink key from target page (its parent) as
-- 
2.7.4