Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

Hi Heikki,

On 2016-11-22 10:56:07 -0800, Peter Geoghegan wrote:
> I attach V4 of amcheck.

Is there any chance you could look at the concurrency related parts of
amcheck?  I'd like to push this to be mergeable, but that area is a bit
outside of my area of expertise...

Andres

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

Hi,

On 2016-11-22 10:56:07 -0800, Peter Geoghegan wrote:
> Andres said: "Theoretically we should recheck that the oids still
> match, theoretically the locking here allows the index->table mapping
> to change". I don't know how to act on this feedback, since comparable
> index + heap locking code should have the same problem, but doesn't
> consider it. How is this any different to reindex_index()?

reindex_index isn't necessarily comparable, because
RangeVarCallbackForReindexIndex() is, on first blush at least, careful
enough about the locking, and reindex_relation only gets the index list
after building the index:/* * Find and lock index, and check permissions on table; use callback to * obtain lock on table first, to avoid deadlock hazard.  The lock level * used here must match the index lock obtained in reindex_index(). */

I think you ought to do something similar.


I'd really like to have something like relation_check(), index_check()
which calls the correct functions for the relevan index types (and
possibly warns about !nbtree indexes not being checked?).


> @@ -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).

I'd appreciate some rephrasing of this paragraph. "includes the
invariant that" isn't that easy to understand for an ESL person.


> + *
> + * Copyright (c) 2016, PostgreSQL Global Development Group

... ;)


> +#define CHECK_SUPERUSER() { \
> +		if (!superuser()) \
> +			ereport(ERROR, \
> +					(errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), \
> +					 (errmsg("must be superuser to use verification functions")))); }

Please make this either a function or just copy - the macro doesn't buy
us anything except weirder looking syntax.


> +/*
> + * 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

Please remove this block and use the normal elevels.



> +/*
> + * 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;

Can you move the field comments to the individual fields? Separating
them makes it more likely to get out of date (obviously keep the
header).  I'd also rename 'exclusivelock' to 'exclusivelylocked' or
such.


> +	/*
> +	 * Mutable state, for verification of particular page:
> +	 *
> +	 * target:              Main target page
> +	 * targetblock:         Main target page's block number
> +	 * targetlsn:           Main target page's LSN

Same here.


> +PG_FUNCTION_INFO_V1(bt_index_check);
> +PG_FUNCTION_INFO_V1(bt_index_parent_check);

I think it'd be good to avoid adding a lot of functions for each
additional type of check we can think of.  I think adding a named 'bool
check_parents = false' argument or such would be better.  Then we can
simply add more and more checks subsequently, and we can have
'bool all_checks = false' so people can trivially check everything,
instead of having to add new checks in each new function.


> +/*
> + * 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);

I'm *VERY* strongly against releasing locks on user relations early.


> +/*
> + * 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);

So yea, this is what I was complaining about re locking / index & table
relation IIRC.  Note you're also deadlock prone by violating the rule
about always locking the relation first.


> +	index_close(indrel, ExclusiveLock);
> +	if (heaprel)
> +		heap_close(heaprel, ShareLock);

Same thing about releasing locks early.



> +/*
> + * 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))));

I think this message could stand some rephrasing.  There's a significant
overlap between msg and detail, and they use different phrasing for
btree.


> +	if (!IndexIsValid(rel->rd_index))
> +		ereport(ERROR,
> +				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
> +				 errmsg("cannot check index \"%s\"",
> +						RelationGetRelationName(rel)),
> +				 errdetail("Index is not valid")));

I'm perfectly fine with not changing that, but IIUC it'd be fine to
weaken this to IndexIsLive() - right?


> + * 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.

It might make sense to be a bit more explicit about the structure bit
(which I assume refers to the fact that modifications to individual
pages are possible (re killitems)?).


> + */
> +static void
> +bt_check_every_level(Relation rel, bool exclusivelock)

Hm, is every level accurate - this is more like checking every
"reachable" page, right?


> +	/*
> +	 * 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)));

I'd weaken the message to something that sounds less like an actual
problem... - which this is not, right?


> +/*
> + * 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.

Wouldn't "'sets state for the next call..." be more accurate than
returning?

> +static BtreeLevel
> +bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
> +{

> +		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))));

I think this could stand a bit more formal language.


> +			else
> +				ereport(CONCERN,
> +						(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
> +						 errmsg("block %u of index \"%s\" ignored",
> +								current, RelationGetRelationName(state->rel))));

missing verb. Also, is this actually worth logging (even at such a low level)?


> +			/*
> +			 * 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.

"state to be passed by caller for next call here" is hard to
understand.  "Prepare state for next bt_check_level_from_leftmost
invocation for the next level"?


> +			 * There should be at least one non-ignorable page per level.
> +			 */

I might have missed something, but you're not checking that, are you?

> +		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)));

"mutual" doesn't seem to add much here.


> +		/* 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))));

That's not really reliable though, is it?  I've seen corrupted link
chains (leading to endless vacuums and such) a number of times, so maybe
explicitly keeping track of already visited pages within a level would
be worthwhile?


> +/*
> + * 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).

Hm. I think it'd be useful if we also made sure (or in the caller) that
the page actually is at the correct level.  I seem to recall seing a
case where downlinks were "circular" due to corruption, leading to stuck
scans.

> + * 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.

I'd shorten this to "Memory allocated in this routine is expected to be
released by the caller resetting the ->xxx/current context".

> +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);

I think it's fine if you don't, but this could theoretically integrate
with the progress stuff added in 9.6 (as in
pgstat_progress_start_command()).  That'd allow for a lot more
convenient display of this than thousands of debug messages or nothing.


> +	/*
> +	 * Loop over page items, but don't start from P_HIKEY (don't have iteration
> +	 * directly considering high key item, if any).

I don't understand the parenthetical comment as phrased.


> +		/*
> +		 *   ********************
> +		 *   * 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.

"which there must be for" sounds weird.


> +		 * 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).

s/prefer to//


> +		/*
> +		 *   ********************
> +		 *   * 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).
> +		 */

Does that kind of comment look reasonable after pgindent? Actually,
could you just pindent this patch (including typedefs.list additions)
and repair the bad looking damage?


> +		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));

Do all these separate psprintfs have much of a point?  It seems just as
easy to includ ethem in the actual ereport?


> +		 * 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).
> +		 */

Is the comma after e.g. correct?  


> +				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)));

I'm am *wondering* (as in not sure), if we could get rid of all the "for
index ..." bits and use an errcontext for that instead, which'd be
included in all messages.


> +	/*
> +	 * 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.

raison d'etre comment seems more like something belonging to
nbtree/README than this, but I don't care much.


> +	/*
> +	 * 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.

Maybe s/Ensuring/The reasons why they don't happen in ...'?


> +	 * 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

"on to this right sibling page"?


> +	 * 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

missing trailing 'the'?  I'm really not a native speaker (and thus might
be off the mark), but making these sentences a bit clearer really
wouldn't hurt.


> +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,

s/N.B./NB/ by precedence ;)


> +	 * We prefer to check all items, rather than checking just the first and
> +	 * trusting that the operator class obeys the transitive law.
> +	 */

s/We prefer//


> +	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;

FWIW, I'd even convert this to an inline function rather than a macro.
Macros are useful when you have to do stuff you can't do otherwise, but
shouldn't be used much otherwise.


> +		if (!invariant_key_less_than_equal_nontarget_offset(state, child,
> +															targetkey, offset))
> +			ereport(CORRUPTION,
> +					(errcode(ERRCODE_INDEX_CORRUPTED),

What's your reasoning for differing sometimes using
ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE and sometimes ERRCODE_INDEX_CORRUPTED?


> +					 errmsg("down-link lower bound invaariant violated for index \"%s\"",

s/invaariant/invariant/



> +/*
> + * invariant_key_greater_than_equal_offset()

I'd personally just remove the function name in these, but that's personal
taste and i'll leave you the decision.


- Andres

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On 2017-02-09 14:48:18 -0500, Robert Haas wrote:
> On Thu, Feb 9, 2017 at 3:05 AM, Andres Freund  wrote:
> >> +#define CHECK_SUPERUSER() { \
> >> +             if (!superuser()) \
> >> +                     ereport(ERROR, \
> >> +                                     (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), \
> >> +                                      (errmsg("must be superuser to use verification functions")))); }
> >
> > Please make this either a function or just copy - the macro doesn't buy
> > us anything except weirder looking syntax.
>
> Better yet, remove the check altogether and just revoke access from
> public.  Then the default policy is superuser-only, but the DBA can
> grant access to who they wish.

That works for me as well.

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On 2017-02-09 13:29:42 -0800, Peter Geoghegan wrote:
> > I'd really like to have something like relation_check(), index_check()
> > which calls the correct functions for the relevan index types (and
> > possibly warns about !nbtree indexes not being checked?).
> 
> I feel that that's something for an in-core facility that exposes this
> through DDL. One good reason to not do that just yet is that I'm not
> completely comfortable with what a uniform interface looks like here.
> And frankly, I really just want to get this out of the way, to prove
> the general concept of verification tooling. amcheck v1 is a good
> start, but much work remains. I think that no one will take the idea
> completely seriously until it is usable as a core extension. Let's get
> the ball rolling.

I'm not convinced at all by that argument.  If we want something in
core, having this in contrib doesn't help much.  Nor do I see much
point in explicit syntax.


> >> +#define CHECK_SUPERUSER() { \
> >> +             if (!superuser()) \
> >> +                     ereport(ERROR, \
> >> +                                     (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), \
> >> +                                      (errmsg("must be superuser to use verification functions")))); }
> >
> > Please make this either a function or just copy - the macro doesn't buy
> > us anything except weirder looking syntax.
> 
> It's actually from pageinspect, but okay.

We have a lot of dodgy stuff in places ;)


> >> +PG_FUNCTION_INFO_V1(bt_index_check);
> >> +PG_FUNCTION_INFO_V1(bt_index_parent_check);
> >
> > I think it'd be good to avoid adding a lot of functions for each
> > additional type of check we can think of.  I think adding a named 'bool
> > check_parents = false' argument or such would be better.  Then we can
> > simply add more and more checks subsequently, and we can have
> > 'bool all_checks = false' so people can trivially check everything,
> > instead of having to add new checks in each new function.
> 
> I strongly disagree. I would agree if the lock strength were the same
> in both cases, but it isn't. Varying the strength of heavyweight lock
> taken based on an argument to a function is a massive foot-gun IMV.

Meh.  I don't think that's a serious problem, nor is without precedent
(say same toplevel DDL with differing lock levels depending on
options). Nor do the function names confer that any more efficiently
than parameters.


> I do think that that's the logical way to split out functionality. I
> don't think that there is likely to be a problem with adding stuff in
> the future. It'll either be something that we can do in passing
> anyway, in which case we can just add it to the existing checks
> harmlessly. Or, it will be something like a tool that verifies the
> heap is consistent with a given index, which is vastly more expensive
> in terms of CPU and I/O costs, and yet is probably no worse than
> bt_index_check() in terms of lock strength (AccessShareLock).

But you quite possibly want to do all three in one pass - and that'll be
ugly with your API.  With your API I'll not be able to do the parent
check and the heap check at once.  Lest we add fourth function that does
all of it.


> My thinking here is that users really ought to use bt_index_check() in
> almost all cases, not bt_index_parent_check(), which is more of a tool
> for hackers that are developing new B-Tree features. The distinction
> is blurry, in fact, but the lock strength requirements of
> bt_index_parent_check() make it vastly less useful.

A quite reasonable patter is to do this verification on standbys that
you can either bring up separately and/or just temporarily pause.  Or
just backups before declaring them valid.


> >> +/*
> >> + * 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.
> >> + */
> 
> > I'm *VERY* strongly against releasing locks on user relations early.
> 
> Why? pageinspect does this.

Again, some parts of the code doing something bad isn't a good argument
for doing again. Releasing locks early is a bad pattern, because backend
code isn't generally safe against it, we have special code-paths for
catalog tables to support it for those.


> >> +     /*
> >> +      * 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);
> >
> > So yea, this is what I was complaining about re locking / index & table
> > relation IIRC.  Note you're also deadlock prone by violating the rule
> > about always locking the relation first.
> 
> This is based on brin_summarize_new_values().
> I'm not doing a recheck,
> though, because I don't actually need the heap relation for anything
> (I suppose I imagined that that was okay, possibly failing to consider
> some subtlety beyond "consistency is good").

We iirc rely on indexes not being locked without the heap also being
locked... I see no reason to be careful here.

The deadlock part of my complaint is bogus.


> The comments here are almost a direct lift -- is
> brin_summarize_new_values() wrong to itself claim to be
> deadlock-safe?.

No, that seems ok.


> (BTW, brin_summarize_new_values(), an SQL-callable function, also
> releases heavyweight locks early.)

And that's afaics actually broken and a bug.



> >> +     if (!IndexIsValid(rel->rd_index))
> >> +             ereport(ERROR,
> >> +                             (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
> >> +                              errmsg("cannot check index \"%s\"",
> >> +                                             RelationGetRelationName(rel)),
> >> +                              errdetail("Index is not valid")));
> >
> > I'm perfectly fine with not changing that, but IIUC it'd be fine to
> > weaken this to IndexIsLive() - right?
> 
> I believe so, but prefer to be more restrictive in the absence of a
> good reason not to be.

Seems useful to be able to verify an index during CONCURRENTLY, after
the initial build, but before the update pass, it's not like we didn't
have bugs in it :(


> >> +static void
> >> +bt_check_every_level(Relation rel, bool exclusivelock)
> >
> > Hm, is every level accurate - this is more like checking every
> > "reachable" page, right?
> 
> Every level should have at least one page that is reachable (not
> half-dead or fully dead), unless perhaps VACUUM marks the last leaf
> page in the entire index as half-dead and we land on that. I think
> that that's such a rare case that it shouldn't alter how we name this
> function at all, which really does do what it says almost always. Note
> that there are pretty severe restrictions on when vacuum can do
> page-level deletion of an internal page. This is what leads to index
> bloat with sparse deletion patterns (one problem I want to address by
> adding suffix truncation to internal pages at a later date).

I think my point was different - it's not that we're not checking every
level, it's that we're checking *more* than just "levels".



> > What's your reasoning for differing sometimes using
> > ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE and sometimes ERRCODE_INDEX_CORRUPTED?
> 
> The ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE ereports are not errors,
> and do not indicate corruption.

Don't think errcodes make much sense for debug stuff, nor do I think
that ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE would be a good fit for
something that's not an error.

Greetings,

Andres Freund

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On 2017-02-09 17:12:58 -0500, Robert Haas wrote:
> On Thu, Feb 9, 2017 at 4:57 PM, Andres Freund  wrote:
> > Meh.  I don't think that's a serious problem, nor is without precedent
> > (say same toplevel DDL with differing lock levels depending on
> > options). Nor do the function names confer that any more efficiently
> > than parameters.
> 
> Really?  check_btree(blah, true) vs. check_btree(blah, false) is no
> more or less clear than check_btree_for_plausible_errors(blah) vs.
> check_btree_in_unreasonable_detail(blah)?

Except that the proposed names aren't remotely like that... ;).

And I proposed documenting named parameters, and
check_btree(performing_check_requiring_exclusive_locks => true) is just
about as expressive.


> > Again, some parts of the code doing something bad isn't a good argument
> > for doing again. Releasing locks early is a bad pattern, because backend
> > code isn't generally safe against it, we have special code-paths for
> > catalog tables to support it for those.
> 
> I don't agree with that.  The reason we keep relation locks until the
> end of the transaction is to avoid surprising application code, not
> because the system can't tolerate it.  But here it's more likely that
> retaining the lock will surprise the user.

It's both.  A bunch of code paths rely on early release ony happening on
catalogs. E.g., and that's just the first thing that comes to mind,
cache invalidations which really only are guaranteed to be delivered and
visibile for other cache accesses, if the lock is only released after
the end of the transaction.  Object accesses like relation_open() accept
invalidations *after* acquiring the lock. Combined with lock releases
only happening *after* transaction commits that guarantees an up2date
view of the cache; but if others release the lock earlier and have cache
invalidations, that doesn't work anymore.  Now you can argue that it's
possibly harmless here because there's presumably no way this can ever
trigger cache invals - and you're probably right - but this isn't the
only place with such assumption and you'd definitely have to argue *why*
it's right.

There were other issues than this, but right of the top of my head I
only remember:
double
IndexBuildHeapRangeScan(Relation heapRelation,
..				/*				 * Since caller should hold ShareLock or better, normally				 * the only way to see this is if it was inserted earlier				 * in our own transaction.  However, it can happen in				 * system catalogs, since we tend to release write lock				 * before commit there.  Give a warning if neither case				 * applies.				 */				xwait = HeapTupleHeaderGetXmin(heapTuple->t_data);				if (!TransactionIdIsCurrentTransactionId(xwait))				{					if (!is_system_catalog)						elog(WARNING, "concurrent insert in progress within table \"%s\"",							 RelationGetRelationName(heapRelation));

which isn't an issue here, but reinforces my point about the (badly
documented) assumption that we don't release locks on user relations
early.

Andres

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

Hi,

On 2017-02-13 11:52:53 -0500, Robert Haas wrote:
> On Thu, Feb 9, 2017 at 5:32 PM, Andres Freund  wrote:
> >> > Again, some parts of the code doing something bad isn't a good argument
> >> > for doing again. Releasing locks early is a bad pattern, because backend
> >> > code isn't generally safe against it, we have special code-paths for
> >> > catalog tables to support it for those.
> >>
> >> I don't agree with that.  The reason we keep relation locks until the
> >> end of the transaction is to avoid surprising application code, not
> >> because the system can't tolerate it.  But here it's more likely that
> >> retaining the lock will surprise the user.
> >
> > It's both.  A bunch of code paths rely on early release ony happening on
> > catalogs. E.g., and that's just the first thing that comes to mind,
> > cache invalidations which really only are guaranteed to be delivered and
> > visibile for other cache accesses, if the lock is only released after
> > the end of the transaction.  Object accesses like relation_open() accept
> > invalidations *after* acquiring the lock. Combined with lock releases
> > only happening *after* transaction commits that guarantees an up2date
> > view of the cache; but if others release the lock earlier and have cache
> > invalidations, that doesn't work anymore.  Now you can argue that it's
> > possibly harmless here because there's presumably no way this can ever
> > trigger cache invals - and you're probably right - but this isn't the
> > only place with such assumption and you'd definitely have to argue *why*
> > it's right.
> 
> I agree that code which issues cache invalidations needs to hold a
> blocking lock until commit IF it's critical for other backends to see
> the update.

Right. And I think that needs to be the default assumption, because
otherwise you need to be careful about all the relevant code paths.  I'm
fine with adding something along the lines of
/** Release lock on relation early, this function doesn't generate any* cache invalidations, and it's convenient for callers to be able to* check multiple functions in one go.*/
(after checking that's true of course) and then skipping the lock
release.  What I'm absolutely not ok with is doing so without
consideration and documentation.


> I don't really understand your demand for "an argument why it's
> right".  My argument is simple: I can't think of a single thing that
> it would break, and I don't believe there is any such thing.

That's pretty much an argument.  I just want documentation that calls
attention that we're doing something that requires a modicum of care.  I
fail to see why that's unreasonable.  I don't think it's that unlikely
will come around adding something like "hey we can update the free page
statistic here, because we just read the whole damn thing", suddenly
invalidating the logic.  Or we add a heap check that then might trigger
pruning, which quite conceivably could trigger an invalidation. Or ...


> I think you're trying to invent a coding rule that doesn't exist, but
> I can't prove a negative.

We had bugs around this in the past, so ...


> Your argument so far is that "yeah, well, maybe inval doesn't emit
> sinval traffic (duh?) but it might do something else that breaks,
> prove to me that there is no such thing".

I have no idea what you're trying to say with this.  The rest of that
paragraph just seems like bunch of odd hyperbole ("impossible to exceed
the speed of light...").


> From my point of view, it's likely to be common to want to run amcheck
> in series on a bunch of indexes, like by writing a SELECT query
> against pg_class or pg_index and passing the OIDs to amcheck.  With
> the retain-locks design, that query accumulates locks on a large
> number of objects, possibly blowing out the lock table or blocking
> DDL.

On the other hand, retaining the locks actually increases the chance to
run a check to completion.  If you e.g. write a query checking the
indexes for a table, you suddenly can't be sure that subsequent indexes
for the same table can be checked, because the relation lock has been
released inbetween.  Which then'd lead to erroring out after doing part
of the expensive work.

I don't think that refutes your argument, but I also don't think it's
as clear cut as you make it out to be.


Greetings,

Andres Freund

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On 2017-02-13 12:05:21 -0500, Robert Haas wrote:
> On Fri, Feb 10, 2017 at 8:39 PM, Peter Geoghegan  wrote:
> > On Thu, Feb 9, 2017 at 2:32 PM, Andres Freund  wrote:
> >> Except that the proposed names aren't remotely like that... ;).
> >
> > Revision attached -- V5. We now REVOKE ALL on both functions, as
> > Robert suggested, instead of the previous approach of having a
> > hard-coded superuser check with enforcement.
> >
> >> And I proposed documenting named parameters, and
> >> check_btree(performing_check_requiring_exclusive_locks => true) is just
> >> about as expressive.
> >
> > I have not done this, nor have I renamed the functions. I still think
> > that this is something that we can fix by adding a boolean argument to
> > each function in the future, or something along those lines. I
> > *really* hate the idea of having one function with non-obvious,
> > variable requirements on locking, with locking implications that are
> > not knowable when we PREPARE an SQL statement calling the function. It
> > also removes a useful way of have superusers discriminate against the
> > stronger locking variant bt_index_parent_check() by not granting
> > execute on it (as an anti-footgun measure).
>
> I think Andres is more or less correct that
> "performing_check_requiring_exclusive_locks => true" is just about as
> expressive as calling a different function, but I think that your
> point that the superuser might want to grant access to one function
> but not the other is a good one.  On the other hand, I think Andres
> has a concern that we might have more modes in the future and we don't
> want to end up with 2^n entrypoints.  That also seems valid.  Hmm.

That's part of my concern.  The second part is that I really want to be
able to have a check_relation() (and check_database())function that I
can pass a bunch of arguments determining how expensive checks are going
to be performed.

E.g. I'd like to be able to do something like

SELECT *
FROM check_relation(  'my_table'::regclass,  test_btree => 'true',  test_btree_heap_interlock => 'true',  test_gin => 'true');

SELECT *
FROM check_current_database(  test_heap_update_chains => 'true',  test_heap_clog_interlock => 'true',  test_btree => 'true',  test_gin => 'false');

etc.

You can't really trivially replace these with a larger query and/or
function, because of the locking considerations (consider what happens
if somebody concurrently drops a table/index - your whole query errors
out, wasting hours of work).

I'm ok with not immediately doing so, but I think Peter's design isn't
in line with achieving something like this.

Regards,

Andres

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On 2017-03-06 20:40:59 -0800, Peter Geoghegan wrote:
> On Mon, Mar 6, 2017 at 3:57 PM, Andres Freund  wrote:
> > I'm ok with not immediately doing so, but I think Peter's design isn't
> > in line with achieving something like this.
>
> I would be okay with doing this if we had a grab-bag of expensive
> checks, that all pretty much require some combination of
> ExclusiveLocks and/or ShareLocks anyway, and are amenable to being
> combined. I could see that happening, but we're a long way off from
> that. When it does happen, we might have other things that are a bit
> like bt_index_parent_check(), in terms of locking requirements and
> degree of thoroughness, that might themselves require other parameters
> specific to the verification that they perform that we cannot
> anticipate. For example, maybe bt_index_parent_check() could have a
> parameter that is a probability that any given IndexTuple will be
> verified against its heap tuple. Then you could have something like a
> PRNG seed argument, so you can check different tuples every day. There
> are many possibilities, and I hope that eventually amcheck has this
> kind of very rich functionality.

> When you use the interface you describe to "stack" several checks at
> once, less important parameters, like the ones I suggest are going to
> be an awkward fit, and so will probably be excluded. I'm not opposed
> to having what amounts to a second interface to what bt_index_check()
> does, to make this kind of thing work where it makes sense. Really,
> bt_index_parent_check() is almost an alternative interface to the same
> functionality today. There can be another one in the future, if it
> serves a purpose, and the locking requirements are roughly the same
> for all the checks. I'd be fine with that. Let's just get the basic
> feature in for now, though.

I disagree quite strongly with pretty much all of that.


But I also think it's more important to get some initial verification
functionality in, than resolving this conflict. I do, also quite
strongly, think we'll be better served with having something like what
you're proposing than nothing, and I don't have time/energy to turn your
patch into what I'm envisioning, nor necessarily the buyin.  Hence I'm
planning to commit the current interface.

Attached is your original patch, and a patch editorializing things. I do
plan to merge those before pushing.

Who would you like to see added to Reviewed-By?

Regards,

Andres

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On 2017-03-09 16:29:24 -0800, Peter Geoghegan wrote:
> I am generally in favor of more inclusive Reviewed-By lists. I suggest
> that we expand it to:
> 
> "Reviewed-By: Andres Freund, Thomas Vondra, Thomas Munro, Anastasia
> Lubennikova, Robert Haas, Amit Langote"

And pushed with these.

I don't really expect buildfarm fallout, but ..

- Andres

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

Hi,

On 2017-03-09 19:04:46 -0800, Peter Geoghegan wrote:
> On Thu, Mar 9, 2017 at 4:41 PM, Andres Freund  wrote:
> > I don't really expect buildfarm fallout, but ..
> 
> Unfortunately, there is some on Windows:

Thanks for monitoring.


>   verify_nbtree.obj : error LNK2001: unresolved external symbol
> RecentGlobalXmin
> [C:\buildfarm\buildenv\HEAD\pgsql.build\amcheck.vcxproj]
> 
> Rather than marking RecentGlobalXmin as PGDLLIMPORT, I'd rather just
> remove the documenting assertion and leave that comment as-is. I'll
> work on a patch for this soon.

Hm - I think it's fair to export RecentGlobalXmin, given that we
obviously use it across modules in core code.  I see very little reason
not to export it.

Greetings,

Andres Freund

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

29.03.2016 06:13, Peter Geoghegan:
> On Tue, Mar 22, 2016 at 10:57 AM, Peter Geoghegan  wrote:
>> That's right - I have a small number of feedback items to work
>> through. I also determined myself that there could be a very low
>> probability race condition when checking the key space across sibling
>> pages, and will work to address that.
> I attach a V2 revision.
>
> Behavioral changes:
>
> * Fixes very low probability race condition when verifying ordering
> across sibling pages with bt_index_check()/AccessShareLock.
>
> Notably, the fix does not involve using the high key from the next
> page instead of the first item, despite my recent suggestion that it
> would; I changed my mind. In this revision,
> bt_right_page_check_scankey() continues to return the first item on
> the next/right page (as a scankey), just as in the first version. The
> locking considerations here are more complicated than before, and
> hopefully correct. I abandoned the high key idea when I realized that
> a concurrent page split could happen in the right sibling, making the
> high key generally no more safe in the face of concurrent target page
> deletion than continuing to use the first data item. Using the first
> data item from the right page is better than using the high key item
> from the right page verification-wise anyway, so that's good. I found
> a new way of locking down and recovering from any race conditions (the
> low probability bug in V1 for bt_index_check()/AccessShareLock calls
> to the C function bt_right_page_check_scankey()). I won't go into the
> gory details here, but I will mention that my new approach is inspired
> by how backwards scans work already.
>
> * Adds DEBUG1 traces that indicate the level and page currently being checked.
>
> Advanced users will probably find these traces useful on occasion.
> It's nice to be able to see how amcheck walks the B-Tree in practice.
>
> Non-behavioral changes:
>
> * Explains why an ExclusiveLock is needed on the target index by
> bt_index_parent_check() (and a ShareLock on its heap relation).
>
> This new explanation talks about why an ExclusiveLock *is* necessary
> when checking downlinks against child pages, per Tomas Vondra's
> request. (Note that nothing changes about child/downlink verification
> itself). Before now, I focused on why they were not necessary, but
> Tomas was right to point out that that isn't enough information.
>
> * No longer uses the word "comport" in an error message, per Amit
> Langote. Similarly, minor typos fixed, per Tomas.
>
> * Adds a variety of pg_regress-based tests for external sorting. (Via
> various CREATE INDEX statements involving a variety of datatypes. Data
> is generated pseudo-randomly.)
>
> Notably, the regression tests *never* test external sorting today.
>
> ISTM that amcheck is a convenient, reliable, and portable way of
> testing the sorting of collatable types like text, so this is the best
> way of testing external sorting. External sorting uses abbreviated
> keys for runs, but discards them as runs are written out, and so the
> merging of runs does not use abbreviated keys. Abbreviated comparisons
> and authoritative comparisons are therefore reliably used within the
> same sort. One particular goal here is that something like the recent
> strxfrm() debacle might be caught by this testing on some platforms
> (if we ever get back to trusting strxfrm() at all, that is). The style
> of these new tests is unorthodox, because a variety of collations are
> tested, which varies from system to system; we should discuss all
> this. The tests can take a minute or two to run on my laptop, but that
> could vary significantly. And so, whether or not that needs to be
> targeted by something other than "check" and "installcheck" is a
> discussion that needs to happen. I imagine a lot of buildfarm animals
> have slow storage, but on the other hand I don't think hackers run the
> contrib regression tests so often. I prefer to not follow the example
> of test_decoding if possible; test_decoding's Makefile only runs tests
> when wal_level=logical is expected (that's how the relevant Makefile
> targets are scoped), but it's a complicated special case.
>
> Review
> ------
>
> As already noted after the first bullet point, there are some tricky
> considerations on fixing the race when the user calls
> bt_index_check(). Reviewers should pay close attention to this; could
> I be wrong about that being race-safe even now? This seems to me to be
> by far the best place for reviewers to look for problems in this
> patch, as it's the only bt_index_check()/AccessShareLock case that
> compares anything *across* pages. The measures taken to prevent false
> positives described within bt_target_page_check() require expert
> review, especially because this is the one case where a faulty
> rationale may result in under-protection from false positives, and not
> just harmless over-protection.
>
> The rationale for why we can reliably recover from a race described
> within the C function bt_right_page_check_scankey() is *complicated*.
> I may have failed to make it as simple as possible despite significant
> effort. It's hard to describe these things in an accessible way. Maybe
> someone can try and understand what I've said there, and let me know
> how I might have fallen short. I have used a new term, "cousin page"
> in this explanation (cf. sibling page). This seems like useful
> terminology that makes these difficult explanations a bit more
> accessible.

I'm not an expert in btree locking races, but I tested the patch it on 
different loads and it works as promised.
I didn't find mistakes in the code logic as well.

As a reviewer, I don't have any objections to mark it "Ready for Committer".
The only notice I'd like to add is about it's compatibility with 
covering indexes.
We already discussed it in the thread 
https://commitfest.postgresql.org/9/433/
Tiny attached patch fixes this issue.

-- 
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Re: amcheck (B-Tree integrity checking tool)

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Fri, Feb 10, 2017 at 8:39 PM, Peter Geoghegan  wrote:
> On Thu, Feb 9, 2017 at 2:32 PM, Andres Freund  wrote:
>> Except that the proposed names aren't remotely like that... ;).
>
> Revision attached -- V5. We now REVOKE ALL on both functions, as
> Robert suggested, instead of the previous approach of having a
> hard-coded superuser check with enforcement.
>
>> And I proposed documenting named parameters, and
>> check_btree(performing_check_requiring_exclusive_locks => true) is just
>> about as expressive.
>
> I have not done this, nor have I renamed the functions. I still think
> that this is something that we can fix by adding a boolean argument to
> each function in the future, or something along those lines. I
> *really* hate the idea of having one function with non-obvious,
> variable requirements on locking, with locking implications that are
> not knowable when we PREPARE an SQL statement calling the function. It
> also removes a useful way of have superusers discriminate against the
> stronger locking variant bt_index_parent_check() by not granting
> execute on it (as an anti-footgun measure).

I think Andres is more or less correct that
"performing_check_requiring_exclusive_locks => true" is just about as
expressive as calling a different function, but I think that your
point that the superuser might want to grant access to one function
but not the other is a good one.  On the other hand, I think Andres
has a concern that we might have more modes in the future and we don't
want to end up with 2^n entrypoints.  That also seems valid.  Hmm.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Feb 9, 2017 at 8:15 PM, Peter Geoghegan  wrote:
> BTW, aren't there cases where a PARALLEL SAFE function that needs to
> acquire locks on some arbitrary relation not referenced in the query
> can get locks on its own, which may only last as long as the parallel
> worker's lifetime? This could happen *despite* the fact that the
> author of the function may have imagined that callers could not
> release relation level locks early (i.e., by not releasing them
> directly, and so correctly following this "badly documented
> assumption").

Yes.

> It seems like the existence of PARALLEL RESTRICTED is primarily
> motivated by making stuff that definitely needs the locks to last
> until xact end being sure that that happens -- the docs say so. This
> seems wholly inconsistent with the idea that you're not supposed to
> let that happen under any circumstances. I find all this highly
> confusing. Have I missed some further subtlety that applies with
> PARALLEL RESTRICTED?

That's by no means the only thing that could cause you to mark
something PARALLEL RESTRICTED.  I think you might have missed this bit
of the documentation, a few paragraphs up:
   Similarly, functions must be marked PARALLEL   RESTRICTED</> if they access temporary tables, client connection state,   cursors, prepared statements, or miscellaneous backend-local state which   the system cannot synchronize across workers. For example,   setseed</> and random</> are parallel restricted for   this last reason.

That stuff is the main motivation.  The early lock release stuff could
come up for user-written functions, but the things listed in the
paragraph I've quoted here come up for plenty of built-in functions.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Feb 9, 2017 at 5:32 PM, Andres Freund  wrote:
>> > Again, some parts of the code doing something bad isn't a good argument
>> > for doing again. Releasing locks early is a bad pattern, because backend
>> > code isn't generally safe against it, we have special code-paths for
>> > catalog tables to support it for those.
>>
>> I don't agree with that.  The reason we keep relation locks until the
>> end of the transaction is to avoid surprising application code, not
>> because the system can't tolerate it.  But here it's more likely that
>> retaining the lock will surprise the user.
>
> It's both.  A bunch of code paths rely on early release ony happening on
> catalogs. E.g., and that's just the first thing that comes to mind,
> cache invalidations which really only are guaranteed to be delivered and
> visibile for other cache accesses, if the lock is only released after
> the end of the transaction.  Object accesses like relation_open() accept
> invalidations *after* acquiring the lock. Combined with lock releases
> only happening *after* transaction commits that guarantees an up2date
> view of the cache; but if others release the lock earlier and have cache
> invalidations, that doesn't work anymore.  Now you can argue that it's
> possibly harmless here because there's presumably no way this can ever
> trigger cache invals - and you're probably right - but this isn't the
> only place with such assumption and you'd definitely have to argue *why*
> it's right.

I agree that code which issues cache invalidations needs to hold a
blocking lock until commit IF it's critical for other backends to see
the update.  That's not always the case; for example, if an ALTER
TABLE statement only changes the fillfactor the worst thing that
happens if some other backend fails to see the invalidations is that
some transactions continue to use the old value for a while.  That's
why we now allow fillfactor and some other things using only
ShareUpdateExclusiveLock.  That's not quite the same thing but the
effect is the same: we issue invalidations that other backends aren't
guaranteed to see in a timely fashion, and it works OK.  Yeah, some
other session might not see the change for a while, but we don't view
that as a big problem.

But I think in this case that argument is basically a straw man.  A
utility that's called amcheck is obviously not issuing any cache
invalidations.  It's probably not even changing anything at all; if it
is, maybe it should be called amrepair.  So the fact that CLUSTER has
to hold AEL until commit time really doesn't have anything to do with
whether amcheck needs to hold AES until commit time.

I don't really understand your demand for "an argument why it's
right".  My argument is simple: I can't think of a single thing that
it would break, and I don't believe there is any such thing.
Furthermore, as Peter points out, we do this kind of thing all the
time in other places and it indeed does not break things.  I think
you're trying to invent a coding rule that doesn't exist, but I can't
prove a negative.  Your argument so far is that "yeah, well, maybe
inval doesn't emit sinval traffic (duh?) but it might do something
else that breaks, prove to me that there is no such thing".  But
that's just like asking me to prove that it's impossible to exceed the
speed of light.  On information and belief, nobody currently knows how
to do that and there is good scientific evidence that it cannot be
done, but there's no way to prove that someone won't in the future
discover a refinement in the physical laws of the universe as we
understand them today which sheds a different light on the situation.

From my point of view, it's likely to be common to want to run amcheck
in series on a bunch of indexes, like by writing a SELECT query
against pg_class or pg_index and passing the OIDs to amcheck.  With
the retain-locks design, that query accumulates locks on a large
number of objects, possibly blowing out the lock table or blocking
DDL.  I think that readily-forseeable problem ought to trump concerns
about purely hypothetical issues caused by releasing locks early.  If
you can come up with an actual issue with releasing locks early that
applies to this particular case, then that's different, of course.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Feb 9, 2017 at 3:05 AM, Andres Freund  wrote:
>> +#define CHECK_SUPERUSER() { \
>> +             if (!superuser()) \
>> +                     ereport(ERROR, \
>> +                                     (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), \
>> +                                      (errmsg("must be superuser to use verification functions")))); }
>
> Please make this either a function or just copy - the macro doesn't buy
> us anything except weirder looking syntax.

Better yet, remove the check altogether and just revoke access from
public.  Then the default policy is superuser-only, but the DBA can
grant access to who they wish.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Re: amcheck (B-Tree integrity checking tool)

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Feb 9, 2017 at 4:57 PM, Andres Freund  wrote:
> On 2017-02-09 13:29:42 -0800, Peter Geoghegan wrote:
>> > I'd really like to have something like relation_check(), index_check()
>> > which calls the correct functions for the relevan index types (and
>> > possibly warns about !nbtree indexes not being checked?).
>>
>> I feel that that's something for an in-core facility that exposes this
>> through DDL. One good reason to not do that just yet is that I'm not
>> completely comfortable with what a uniform interface looks like here.
>> And frankly, I really just want to get this out of the way, to prove
>> the general concept of verification tooling. amcheck v1 is a good
>> start, but much work remains. I think that no one will take the idea
>> completely seriously until it is usable as a core extension. Let's get
>> the ball rolling.
>
> I'm not convinced at all by that argument.  If we want something in
> core, having this in contrib doesn't help much.  Nor do I see much
> point in explicit syntax.

I don't see any need for this to be in core, nor do I think we need
explicit syntax.  But given that, I also don't think that we need the
generalized infrastructure you proposed in the quoted section above.

>> I strongly disagree. I would agree if the lock strength were the same
>> in both cases, but it isn't. Varying the strength of heavyweight lock
>> taken based on an argument to a function is a massive foot-gun IMV.
>
> Meh.  I don't think that's a serious problem, nor is without precedent
> (say same toplevel DDL with differing lock levels depending on
> options). Nor do the function names confer that any more efficiently
> than parameters.

Really?  check_btree(blah, true) vs. check_btree(blah, false) is no
more or less clear than check_btree_for_plausible_errors(blah) vs.
check_btree_in_unreasonable_detail(blah)?

>> I do think that that's the logical way to split out functionality. I
>> don't think that there is likely to be a problem with adding stuff in
>> the future. It'll either be something that we can do in passing
>> anyway, in which case we can just add it to the existing checks
>> harmlessly. Or, it will be something like a tool that verifies the
>> heap is consistent with a given index, which is vastly more expensive
>> in terms of CPU and I/O costs, and yet is probably no worse than
>> bt_index_check() in terms of lock strength (AccessShareLock).
>
> But you quite possibly want to do all three in one pass - and that'll be
> ugly with your API.  With your API I'll not be able to do the parent
> check and the heap check at once.  Lest we add fourth function that does
> all of it.

This however seems like a good point.

> Again, some parts of the code doing something bad isn't a good argument
> for doing again. Releasing locks early is a bad pattern, because backend
> code isn't generally safe against it, we have special code-paths for
> catalog tables to support it for those.

I don't agree with that.  The reason we keep relation locks until the
end of the transaction is to avoid surprising application code, not
because the system can't tolerate it.  But here it's more likely that
retaining the lock will surprise the user.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Fri, Feb 10, 2017 at 6:45 AM, Peter Geoghegan  wrote:
> On Thu, Feb 9, 2017 at 2:47 PM, Peter Geoghegan  wrote:
>>> which isn't an issue here, but reinforces my point about the (badly
>>> documented) assumption that we don't release locks on user relations
>>> early.
>>

I think even if we don't need to retain locks till transaction end in
the present case, but Andres's point has a merit that it is good to
follow an undocumented rule of releasing locks at transaction end for
user relations unless there is some benefit in releasing the locks
early in some situation.  I think that can avoid unnecessary worry
that whether it safe to do in some situation.

>> You are right about the substantive issue, I assume, but I have a hard
>> time agreeing with the idea that it's even badly documented when there
>> are at least 10 counter-examples of blithely doing this. In any case,
>> I find it very confusing when you talk about things as established
>> practice/coding standards when they're very clearly not consistently
>> adhered to at all. You should at least say "let's not make a bad
>> situation any worse", or something, so that I don't need to spend 10
>> minutes pulling my hair out.
>
> BTW, aren't there cases where a PARALLEL SAFE function that needs to
> acquire locks on some arbitrary relation not referenced in the query
> can get locks on its own, which may only last as long as the parallel
> worker's lifetime? This could happen *despite* the fact that the
> author of the function may have imagined that callers could not
> release relation level locks early (i.e., by not releasing them
> directly, and so correctly following this "badly documented
> assumption").
>
> It seems like the existence of PARALLEL RESTRICTED is primarily
> motivated by making stuff that definitely needs the locks to last
> until xact end being sure that that happens -- the docs say so.
>

I don't think so.  I think one of the primary reason of releasing
locks in workers is that we don't have any way to transfer them to the
leader which can release them at transaction end.

> This
> seems wholly inconsistent with the idea that you're not supposed to
> let that happen under any circumstances. I find all this highly
> confusing. Have I missed some further subtlety that applies with
> PARALLEL RESTRICTED?
>

The basic idea of parallel restricted is that any expression will be
considered parallel restricted if that can't be executed in the
worker, for example, a reference to initplans in a query.


-- 
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Mon, Dec 5, 2016 at 2:15 PM, Haribabu Kommi  wrote:
> Moved to next CF with " needs review" status.

Same, to CF 2017-03 this time.
-- 
Michael

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

On Fri, Nov 18, 2016 at 12:17 PM, Peter Geoghegan  wrote:
> So, the Btree you show is supposed to be good? You've left it up to me
> to draw T2, the corrupt version? If so, here is a drawing of T2 for
> the sake of clarity:
>
>       Btree   =        [a|b]
>                        /   \
>                       /     \
>                      /       \
>                    [a]-------[b]
>                     |         |
>                     |         |
>                    [c]-------[d]

Actually I meant that at T2 the btree is exactly same as it was at T1,
but the order of the values has changed according to the comparator
(for example, because a collation definition changed when you updated
your operating system), so that the btree is now corrupted.  Based on
Goetz Graefe's paper I was wondering if amcheck would be unable to
detect this due to the cousin problem.

>> Now c and b have been switched around.  Won't amcheck still pass since
>> we only verify immediate downlinks and siblings?  Yet searches for b
>> will take a wrong turn at the root.  Do I have this right?  I wonder
>> if there is a way to verify that each page's high key < the 'next' key
>> for all ancestors.
>
> I don't think you have it right, because your argument is predicated
> on classic L&Y, not the Postgres variant. The high key is literally
> guaranteed to be *equal* to the initial first value of the right half
> of a split page post-split (at least initially), which is where the
> new downlink for the new right half comes from in turn, so it will be
> exactly equal as well. There is a comment which says all this within
> _bt_insert_parent(), actually.
>
> In general, I think it's pretty bad that we're so loose about
> representing the key space in downlinks compared to classic L&Y,
> because it probably makes index bloat a lot worse in internal pages,
> messing up the key space long term. As long as we're doing that,
> though, we clearly cannot usefully "verify that each page's high key <
> the 'next' key for all ancestors", because we deviate from L&Y in a
> way that makes that check always fail. It's okay that it always fails
> for us (it doesn't actually indicate corruption), because of our
> duplicate-aware index scan logic (change to invariant).
>
> In summary, I'm pretty sure that our "Ki <= v <= Ki+1" thing makes the
> cousin problem a non-issue, because we don't follow downlinks that are
> equal to our scankey -- we go to their immediate left and start
> *there*, in order to support duplicates in leaf pages. Index scans for
> 'b' work for both T1 and T2 in Postgres, because we refuse to follow
> the 'b' downlinks when doing an index scan for 'b' (relevant to T2). I
> would actually like to change things to make the invariant the classic
> L&Y "Ki < v <= Ki+1", to avoid bloat in the internal pages and to make
> suffix truncation in internal pages work.
>
> So, we don't have the cousin problem, but since I wish for us to adopt
> the stricter classic L&Y invariant at some point, you could say that I
> also wished that we had the cousin problem.

Thank you for your patient explanation!  Please see my humble attempt
to test this scenario and learn something about btrees in the process,
attached.  amcheck does detect the violation of the high key
invariant.

> Confused yet? :-)

Yes.  But it's getting better slowly :-)

-- 
Thomas Munro
http://www.enterprisedb.com

Re: amcheck (B-Tree integrity checking tool)

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Feb 9, 2017 at 2:47 PM, Peter Geoghegan  wrote:
>> which isn't an issue here, but reinforces my point about the (badly
>> documented) assumption that we don't release locks on user relations
>> early.
>
> You are right about the substantive issue, I assume, but I have a hard
> time agreeing with the idea that it's even badly documented when there
> are at least 10 counter-examples of blithely doing this. In any case,
> I find it very confusing when you talk about things as established
> practice/coding standards when they're very clearly not consistently
> adhered to at all. You should at least say "let's not make a bad
> situation any worse", or something, so that I don't need to spend 10
> minutes pulling my hair out.

BTW, aren't there cases where a PARALLEL SAFE function that needs to
acquire locks on some arbitrary relation not referenced in the query
can get locks on its own, which may only last as long as the parallel
worker's lifetime? This could happen *despite* the fact that the
author of the function may have imagined that callers could not
release relation level locks early (i.e., by not releasing them
directly, and so correctly following this "badly documented
assumption").

It seems like the existence of PARALLEL RESTRICTED is primarily
motivated by making stuff that definitely needs the locks to last
until xact end being sure that that happens -- the docs say so. This
seems wholly inconsistent with the idea that you're not supposed to
let that happen under any circumstances. I find all this highly
confusing. Have I missed some further subtlety that applies with
PARALLEL RESTRICTED?

-- 
Peter Geoghegan

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Mar 9, 2017 at 3:52 PM, Andres Freund  wrote:
>
> But I also think it's more important to get some initial verification
> functionality in, than resolving this conflict. I do, also quite
> strongly, think we'll be better served with having something like what
> you're proposing than nothing, and I don't have time/energy to turn your
> patch into what I'm envisioning, nor necessarily the buyin.  Hence I'm
> planning to commit the current interface.
>
> Attached is your original patch, and a patch editorializing things. I do
> plan to merge those before pushing.

Your revisions all seem fine. No problems with any of it.

> Who would you like to see added to Reviewed-By?

I am generally in favor of more inclusive Reviewed-By lists. I suggest
that we expand it to:

"Reviewed-By: Andres Freund, Thomas Vondra, Thomas Munro, Anastasia
Lubennikova, Robert Haas, Amit Langote"

Thanks for your help with this!

-- 
Peter Geoghegan

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Mar 9, 2017 at 4:41 PM, Andres Freund  wrote:
> And pushed with these.

Thanks.

> I don't really expect buildfarm fallout, but ..

Unfortunately, there is some on Windows:
 verify_nbtree.obj : error LNK2001: unresolved external symbol
RecentGlobalXmin
[C:\buildfarm\buildenv\HEAD\pgsql.build\amcheck.vcxproj]

Rather than marking RecentGlobalXmin as PGDLLIMPORT, I'd rather just
remove the documenting assertion and leave that comment as-is. I'll
work on a patch for this soon.

-- 
Peter Geoghegan

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Mon, Mar 6, 2017 at 3:57 PM, Andres Freund  wrote:
> I'm ok with not immediately doing so, but I think Peter's design isn't
> in line with achieving something like this.

I would be okay with doing this if we had a grab-bag of expensive
checks, that all pretty much require some combination of
ExclusiveLocks and/or ShareLocks anyway, and are amenable to being
combined. I could see that happening, but we're a long way off from
that. When it does happen, we might have other things that are a bit
like bt_index_parent_check(), in terms of locking requirements and
degree of thoroughness, that might themselves require other parameters
specific to the verification that they perform that we cannot
anticipate. For example, maybe bt_index_parent_check() could have a
parameter that is a probability that any given IndexTuple will be
verified against its heap tuple. Then you could have something like a
PRNG seed argument, so you can check different tuples every day. There
are many possibilities, and I hope that eventually amcheck has this
kind of very rich functionality.

When you use the interface you describe to "stack" several checks at
once, less important parameters, like the ones I suggest are going to
be an awkward fit, and so will probably be excluded. I'm not opposed
to having what amounts to a second interface to what bt_index_check()
does, to make this kind of thing work where it makes sense. Really,
bt_index_parent_check() is almost an alternative interface to the same
functionality today. There can be another one in the future, if it
serves a purpose, and the locking requirements are roughly the same
for all the checks. I'd be fine with that. Let's just get the basic
feature in for now, though.

-- 
Peter Geoghegan

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Mar 9, 2017 at 7:10 PM, Andres Freund  wrote:
>>   verify_nbtree.obj : error LNK2001: unresolved external symbol
>> RecentGlobalXmin
>> [C:\buildfarm\buildenv\HEAD\pgsql.build\amcheck.vcxproj]
>>
>> Rather than marking RecentGlobalXmin as PGDLLIMPORT, I'd rather just
>> remove the documenting assertion and leave that comment as-is. I'll
>> work on a patch for this soon.
>
> Hm - I think it's fair to export RecentGlobalXmin, given that we
> obviously use it across modules in core code.  I see very little reason
> not to export it.

Well, the assertion is completely useless as anything but documentation...


-- 
Peter Geoghegan

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Feb 9, 2017 at 2:32 PM, Andres Freund  wrote:
> Except that the proposed names aren't remotely like that... ;).

Revision attached -- V5. We now REVOKE ALL on both functions, as
Robert suggested, instead of the previous approach of having a
hard-coded superuser check with enforcement.

> And I proposed documenting named parameters, and
> check_btree(performing_check_requiring_exclusive_locks => true) is just
> about as expressive.

I have not done this, nor have I renamed the functions. I still think
that this is something that we can fix by adding a boolean argument to
each function in the future, or something along those lines. I
*really* hate the idea of having one function with non-obvious,
variable requirements on locking, with locking implications that are
not knowable when we PREPARE an SQL statement calling the function. It
also removes a useful way of have superusers discriminate against the
stronger locking variant bt_index_parent_check() by not granting
execute on it (as an anti-footgun measure). I don't think that it's
too much to ask for you to concede this one point to me (and to
Robert).

I have acted on every other item you raised, without exception,
including retaining the locks for the duration of the transaction. I
also made the functions PARALLEL RESTRICTED, which seemed like a good
idea.

Other notes:

* A nice thing about the additional level check that you suggested is
that it's a cross-level check that is perfectly safe to perform with
only an AccessShareLock, unlike the extra bt_index_parent_check()
check, since the number of levels only ever increases, no matter what.
There is no possible reason why we should ever find that a child page
does not agree with its self-described parent about the level it's on.
I'm glad you thought of this.

* I kept ereport() DEBUG1 calls, but now use non-error errcode for
those. I thought that preserving the various ereport() fields was
worth it, since these traces are rather information dense in a way
that is harder to deal with when using raw elog()s. If you hate this,
you can still change it.

* I have not added code to check the relation permissions, which might
matter if and when the superuser grants execute privs on amcheck
functions. Anyone want to argue that I should have added
relation-level permissions checks? I tend to think it's pointless,
since the superuser almost certainly won't think to consider that
additional factor. I cannot imagine how either function could be used
to leak information, in any case. No error message dumps the contents
of pages (only item pointers).

* pgindent was run against this revision. You were right to want to
get that out of the way now, since it needed to be fixed up by hand to
look reasonable. typedef list also updated.

-- 
Peter Geoghegan

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Feb 9, 2017 at 12:05 AM, Andres Freund  wrote:
> reindex_index isn't necessarily comparable, because
> RangeVarCallbackForReindexIndex() is, on first blush at least, careful
> enough about the locking, and reindex_relation only gets the index list
> after building the index:
>         /*
>          * Find and lock index, and check permissions on table; use callback to
>          * obtain lock on table first, to avoid deadlock hazard.  The lock level
>          * used here must match the index lock obtained in reindex_index().
>          */
>
> I think you ought to do something similar.

Okay. Looking into it, but see my response to your later remarks below.

> I'd really like to have something like relation_check(), index_check()
> which calls the correct functions for the relevan index types (and
> possibly warns about !nbtree indexes not being checked?).

I feel that that's something for an in-core facility that exposes this
through DDL. One good reason to not do that just yet is that I'm not
completely comfortable with what a uniform interface looks like here.
And frankly, I really just want to get this out of the way, to prove
the general concept of verification tooling. amcheck v1 is a good
start, but much work remains. I think that no one will take the idea
completely seriously until it is usable as a core extension. Let's get
the ball rolling.

>> +#define CHECK_SUPERUSER() { \
>> +             if (!superuser()) \
>> +                     ereport(ERROR, \
>> +                                     (errcode(ERRCODE_INSUFFICIENT_PRIVILEGE), \
>> +                                      (errmsg("must be superuser to use verification functions")))); }
>
> Please make this either a function or just copy - the macro doesn't buy
> us anything except weirder looking syntax.

It's actually from pageinspect, but okay.

>> +#define CORRUPTION           ERROR
>> +#define CONCERN                      DEBUG1
>> +#define POSITION             DEBUG2
>> +#endif
>
> Please remove this block and use the normal elevels.

Okay.

>> +/*
>> + * 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;
>
> Can you move the field comments to the individual fields? Separating
> them makes it more likely to get out of date (obviously keep the
> header).  I'd also rename 'exclusivelock' to 'exclusivelylocked' or
> such.

Okay.

>> +     /*
>> +      * Mutable state, for verification of particular page:
>> +      *
>> +      * target:              Main target page
>> +      * targetblock:         Main target page's block number
>> +      * targetlsn:           Main target page's LSN
>
> Same here.

Okay.

>> +PG_FUNCTION_INFO_V1(bt_index_check);
>> +PG_FUNCTION_INFO_V1(bt_index_parent_check);
>
> I think it'd be good to avoid adding a lot of functions for each
> additional type of check we can think of.  I think adding a named 'bool
> check_parents = false' argument or such would be better.  Then we can
> simply add more and more checks subsequently, and we can have
> 'bool all_checks = false' so people can trivially check everything,
> instead of having to add new checks in each new function.

I strongly disagree. I would agree if the lock strength were the same
in both cases, but it isn't. Varying the strength of heavyweight lock
taken based on an argument to a function is a massive foot-gun IMV. I
do think that that's the logical way to split out functionality. I
don't think that there is likely to be a problem with adding stuff in
the future. It'll either be something that we can do in passing
anyway, in which case we can just add it to the existing checks
harmlessly. Or, it will be something like a tool that verifies the
heap is consistent with a given index, which is vastly more expensive
in terms of CPU and I/O costs, and yet is probably no worse than
bt_index_check() in terms of lock strength (AccessShareLock).

My thinking here is that users really ought to use bt_index_check() in
almost all cases, not bt_index_parent_check(), which is more of a tool
for hackers that are developing new B-Tree features. The distinction
is blurry, in fact, but the lock strength requirements of
bt_index_parent_check() make it vastly less useful. Especially
considering that it seems fairly unlikely that it will ever catch a
problem that bt_index_check() would not have. bt_index_parent_check()
will become a lot more important when we implement suffix truncation
in internal pages. (I have a very rough patch that does this, actually
-- it passes the regression tests, and verification by amcheck, but
isn't anywhere near ready to post.)

>> +/*
>> + * 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.
>> + */

> I'm *VERY* strongly against releasing locks on user relations early.

Why? pageinspect does this. I think it could be really handy for users
that want to write SQL queries when using bt_index_parent_check().
It's a bit weird, in the sense that it's a special exception that has
to be explained sometimes, but I think it is worth it for something
like this.

>> +     /*
>> +      * 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);
>
> So yea, this is what I was complaining about re locking / index & table
> relation IIRC.  Note you're also deadlock prone by violating the rule
> about always locking the relation first.

This is based on brin_summarize_new_values(). I'm not doing a recheck,
though, because I don't actually need the heap relation for anything
(I suppose I imagined that that was okay, possibly failing to consider
some subtlety beyond "consistency is good"). If I added a recheck for
the heap relation in the style of brin_summarize_new_values(), would
you consider this item closed, and all heavyweight lock concerns
addressed?

The comments here are almost a direct lift -- is
brin_summarize_new_values() wrong to itself claim to be
deadlock-safe?.

(BTW, brin_summarize_new_values(), an SQL-callable function, also
releases heavyweight locks early.)

>> +/*
>> + * 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))));
>
> I think this message could stand some rephrasing.  There's a significant
> overlap between msg and detail, and they use different phrasing for
> btree.

Okay.

>> +     if (!IndexIsValid(rel->rd_index))
>> +             ereport(ERROR,
>> +                             (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
>> +                              errmsg("cannot check index \"%s\"",
>> +                                             RelationGetRelationName(rel)),
>> +                              errdetail("Index is not valid")));
>
> I'm perfectly fine with not changing that, but IIUC it'd be fine to
> weaken this to IndexIsLive() - right?

I believe so, but prefer to be more restrictive in the absence of a
good reason not to be.

>> + * 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.
>
> It might make sense to be a bit more explicit about the structure bit
> (which I assume refers to the fact that modifications to individual
> pages are possible (re killitems)?).

It's not really about killitems, which I explained won't matter here,
but I will add a bit about that.

>> + */
>> +static void
>> +bt_check_every_level(Relation rel, bool exclusivelock)
>
> Hm, is every level accurate - this is more like checking every
> "reachable" page, right?

Every level should have at least one page that is reachable (not
half-dead or fully dead), unless perhaps VACUUM marks the last leaf
page in the entire index as half-dead and we land on that. I think
that that's such a rare case that it shouldn't alter how we name this
function at all, which really does do what it says almost always. Note
that there are pretty severe restrictions on when vacuum can do
page-level deletion of an internal page. This is what leads to index
bloat with sparse deletion patterns (one problem I want to address by
adding suffix truncation to internal pages at a later date).

>> +     /*
>> +      * 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)));
>
> I'd weaken the message to something that sounds less like an actual
> problem... - which this is not, right?

No, it isn't a real problem. I'll do something about it.

>> +/*
>> + * 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.
>
> Wouldn't "'sets state for the next call..." be more accurate than
> returning?

Okay.

>> +static BtreeLevel
>> +bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
>> +{
>
>> +             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))));
>
> I think this could stand a bit more formal language.

I disagree, because it's a direct lift from nbtree itself.

>> +                     else
>> +                             ereport(CONCERN,
>> +                                             (errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
>> +                                              errmsg("block %u of index \"%s\" ignored",
>> +                                                             current, RelationGetRelationName(state->rel))));
>
> missing verb. Also, is this actually worth logging (even at such a low level)?

I'm not following -- "ignore" is a verb.

It may not be worth logging. I just don't know, and prefer to err on
the side of including it.

>> +                     /*
>> +                      * 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.
>
> "state to be passed by caller for next call here" is hard to
> understand.  "Prepare state for next bt_check_level_from_leftmost
> invocation for the next level"?

Okay.

>> +                      * There should be at least one non-ignorable page per level.
>> +                      */
>
> I might have missed something, but you're not checking that, are you?

No. As I said just now, I think it might not be true iff every single
item (every item at the leaf level) has been deleted and is being
vacuumed. If there was even one live item in one leaf page, it would
be guaranteed to have a live parent, which would itself be guaranteed
to if it wasn't the true root, and so on, until the true root. It's
really hard to "lose" a level by having the true root and fast root
differ, in general (of course, we can never truly lose a level -- the
pages can never be reclaimed entirely from a deleted level's last
page). I guess that this fast root stuff was added only for the
benefit of cases where there is continuous bulk deletion and
insertion.

> "mutual" doesn't seem to add much here.

Okay.

>> +             /* 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))));
>
> That's not really reliable though, is it?  I've seen corrupted link
> chains (leading to endless vacuums and such) a number of times, so maybe
> explicitly keeping track of already visited pages within a level would
> be worthwhile?

It's not reliable -- it's one of the "shot in the dark, but why not?"
checks, which are the majority -- no reason to not be defensive.
However, it's highly likely that cases like the one you describe would
be caught by the cross-page check, or even high-key check, because
they're probably explained by an underlying problem with transposed
pages, maybe not even 8KiB aligned pages (e.g., buggy firmware
controllers have been known to do this with their 4KiB pages, but you
wouldn't necessarily notice that easily with an int4 index or
similar).

I feel relatively confident that we don't need to do better with that
one, since it will never make a difference; the only case where that
might be wrong that I can think of is where you have an awful lot of
duplicates, which is unfortunately not that uncommon with Postgres.
Even if it could help, that sounds like something that won't pay for
itself.

> Hm. I think it'd be useful if we also made sure (or in the caller) that
> the page actually is at the correct level.  I seem to recall seing a
> case where downlinks were "circular" due to corruption, leading to stuck
> scans.

That's a good idea, because it is, if nothing else, an easy,
low-overhead additional check.

>> + * 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.
>
> I'd shorten this to "Memory allocated in this routine is expected to be
> released by the caller resetting the ->xxx/current context".

Okay.

>> +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);
>
> I think it's fine if you don't, but this could theoretically integrate
> with the progress stuff added in 9.6 (as in
> pgstat_progress_start_command()).  That'd allow for a lot more
> convenient display of this than thousands of debug messages or nothing.

Never enough time. :-)

>> +     /*
>> +      * Loop over page items, but don't start from P_HIKEY (don't have iteration
>> +      * directly considering high key item, if any).
>
> I don't understand the parenthetical comment as phrased.

It means that the high key item, which is physically the first item on
the leaf level, and the second item on internal levels. (That have an
explicit "minus infinity" downlink item), is skipped in the sense that
it doesn't get its own iteration of the loop (note that there is only
a high key on non-rightmost-at-level pages -- I like to say that the
rightmost pages have an implicit/imaginary "positive infinity" high
key, to illustrate the symmetry between high keys and downlinks.
Although, we don't say that in any code.)

> "which there must be for" sounds weird.

> s/prefer to//

Okay.

> Does that kind of comment look reasonable after pgindent? Actually,
> could you just pindent this patch (including typedefs.list additions)
> and repair the bad looking damage?

I'll check.

> Do all these separate psprintfs have much of a point?  It seems just as
> easy to includ ethem in the actual ereport?

I thought it looked very convoluted that way.

>> +              * 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).
>> +              */
>
> Is the comma after e.g. correct?  

This is a matter of style. "e.g.," is generally considered American style.

>> +                             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)));
>
> I'm am *wondering* (as in not sure), if we could get rid of all the "for
> index ..." bits and use an errcontext for that instead, which'd be
> included in all messages.

Doesn't seem worth it to me.

>> +     /*
>> +      * 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.
>
> raison d'etre comment seems more like something belonging to
> nbtree/README than this, but I don't care much.

I think it adds value. This is a learning tool for nbtree. That's a
secondary goal, at least. We're *way* too shy at pointing out simple
facts like this, that are of very significant consequence. It's only
one sentence.

> Maybe s/Ensuring/The reasons why they don't happen in ...'?

> "on to this right sibling page"?

> missing trailing 'the'?  I'm really not a native speaker (and thus might
> be off the mark), but making these sentences a bit clearer really
> wouldn't hurt.

Okay. The sentences are very complicated, but that's justified by the
complexity of the underlying issue. I rewrote that text several times.

> s/N.B./NB/ by precedence ;)

> s/We prefer//

Okay.

>> +             if (OFFSET_IS_MINUS_INFINITY(copaque, offset))
>> +                     continue;
>
> FWIW, I'd even convert this to an inline function rather than a macro.
> Macros are useful when you have to do stuff you can't do otherwise, but
> shouldn't be used much otherwise.

Okay.

>> +             if (!invariant_key_less_than_equal_nontarget_offset(state, child,
>> +                                                                                                                     targetkey, offset))
>> +                     ereport(CORRUPTION,
>> +                                     (errcode(ERRCODE_INDEX_CORRUPTED),
>
> What's your reasoning for differing sometimes using
> ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE and sometimes ERRCODE_INDEX_CORRUPTED?

The ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE ereports are not errors,
and do not indicate corruption.

-- 
Peter Geoghegan

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Feb 9, 2017 at 2:32 PM, Andres Freund  wrote:
> Except that the proposed names aren't remotely like that... ;).
>
> And I proposed documenting named parameters, and
> check_btree(performing_check_requiring_exclusive_locks => true) is just
> about as expressive.

I cannot think of an example, offhand, of where it isn't self-evident
what relation level locks will be acquired when a statement is
prepared. I guess you could say that VACUUM truncation is a bit like
that, but it's not the same IMV.

Maybe there is an easy compromise here. We can add an argument with a
default, "level". It's an "enum" of the style of pg_prewarm (i.e.,
it's actually a text argument). The default is 'medium' or something
like that. Maybe we don't add any other flags for now, or maybe we add
some generic ones that don't actually changed the behavior. Existing
names are retained.

Doesn't that address your concern about an inflexible API? I really
dislike the idea of having the lock strength be determined on the
basis of a function arguments value.

>> I don't agree with that.  The reason we keep relation locks until the
>> end of the transaction is to avoid surprising application code, not
>> because the system can't tolerate it.  But here it's more likely that
>> retaining the lock will surprise the user.

> There were other issues than this, but right of the top of my head I
> only remember:
> double
> IndexBuildHeapRangeScan(Relation heapRelation,
> ..
>                                         /*
>                                          * Since caller should hold ShareLock or better, normally
>                                          * the only way to see this is if it was inserted earlier
>                                          * in our own transaction.  However, it can happen in
>                                          * system catalogs, since we tend to release write lock
>                                          * before commit there.  Give a warning if neither case
>                                          * applies.
>                                          */
>                                         xwait = HeapTupleHeaderGetXmin(heapTuple->t_data);
>                                         if (!TransactionIdIsCurrentTransactionId(xwait))
>                                         {
>                                                 if (!is_system_catalog)
>                                                         elog(WARNING, "concurrent insert in progress within table \"%s\"",
>                                                                  RelationGetRelationName(heapRelation));
>
> which isn't an issue here, but reinforces my point about the (badly
> documented) assumption that we don't release locks on user relations
> early.

You are right about the substantive issue, I assume, but I have a hard
time agreeing with the idea that it's even badly documented when there
are at least 10 counter-examples of blithely doing this. In any case,
I find it very confusing when you talk about things as established
practice/coding standards when they're very clearly not consistently
adhered to at all. You should at least say "let's not make a bad
situation any worse", or something, so that I don't need to spend 10
minutes pulling my hair out.

-- 
Peter Geoghegan

Re: [HACKERS] amcheck (B-Tree integrity checking tool)

On Thu, Mar 9, 2017 at 7:12 PM, Peter Geoghegan  wrote:
>> Hm - I think it's fair to export RecentGlobalXmin, given that we
>> obviously use it across modules in core code.  I see very little reason
>> not to export it.
>
> Well, the assertion is completely useless as anything but documentation...

I came up with the attached.

-- 
Peter Geoghegan

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

On Tue, Mar 22, 2016 at 10:57 AM, Peter Geoghegan  wrote:
> That's right - I have a small number of feedback items to work
> through. I also determined myself that there could be a very low
> probability race condition when checking the key space across sibling
> pages, and will work to address that.

I attach a V2 revision.

Behavioral changes:

* Fixes very low probability race condition when verifying ordering
across sibling pages with bt_index_check()/AccessShareLock.

Notably, the fix does not involve using the high key from the next
page instead of the first item, despite my recent suggestion that it
would; I changed my mind. In this revision,
bt_right_page_check_scankey() continues to return the first item on
the next/right page (as a scankey), just as in the first version. The
locking considerations here are more complicated than before, and
hopefully correct. I abandoned the high key idea when I realized that
a concurrent page split could happen in the right sibling, making the
high key generally no more safe in the face of concurrent target page
deletion than continuing to use the first data item. Using the first
data item from the right page is better than using the high key item
from the right page verification-wise anyway, so that's good. I found
a new way of locking down and recovering from any race conditions (the
low probability bug in V1 for bt_index_check()/AccessShareLock calls
to the C function bt_right_page_check_scankey()). I won't go into the
gory details here, but I will mention that my new approach is inspired
by how backwards scans work already.

* Adds DEBUG1 traces that indicate the level and page currently being checked.

Advanced users will probably find these traces useful on occasion.
It's nice to be able to see how amcheck walks the B-Tree in practice.

Non-behavioral changes:

* Explains why an ExclusiveLock is needed on the target index by
bt_index_parent_check() (and a ShareLock on its heap relation).

This new explanation talks about why an ExclusiveLock *is* necessary
when checking downlinks against child pages, per Tomas Vondra's
request. (Note that nothing changes about child/downlink verification
itself). Before now, I focused on why they were not necessary, but
Tomas was right to point out that that isn't enough information.

* No longer uses the word "comport" in an error message, per Amit
Langote. Similarly, minor typos fixed, per Tomas.

* Adds a variety of pg_regress-based tests for external sorting. (Via
various CREATE INDEX statements involving a variety of datatypes. Data
is generated pseudo-randomly.)

Notably, the regression tests *never* test external sorting today.

ISTM that amcheck is a convenient, reliable, and portable way of
testing the sorting of collatable types like text, so this is the best
way of testing external sorting. External sorting uses abbreviated
keys for runs, but discards them as runs are written out, and so the
merging of runs does not use abbreviated keys. Abbreviated comparisons
and authoritative comparisons are therefore reliably used within the
same sort. One particular goal here is that something like the recent
strxfrm() debacle might be caught by this testing on some platforms
(if we ever get back to trusting strxfrm() at all, that is). The style
of these new tests is unorthodox, because a variety of collations are
tested, which varies from system to system; we should discuss all
this. The tests can take a minute or two to run on my laptop, but that
could vary significantly. And so, whether or not that needs to be
targeted by something other than "check" and "installcheck" is a
discussion that needs to happen. I imagine a lot of buildfarm animals
have slow storage, but on the other hand I don't think hackers run the
contrib regression tests so often. I prefer to not follow the example
of test_decoding if possible; test_decoding's Makefile only runs tests
when wal_level=logical is expected (that's how the relevant Makefile
targets are scoped), but it's a complicated special case.

Review
------

As already noted after the first bullet point, there are some tricky
considerations on fixing the race when the user calls
bt_index_check(). Reviewers should pay close attention to this; could
I be wrong about that being race-safe even now? This seems to me to be
by far the best place for reviewers to look for problems in this
patch, as it's the only bt_index_check()/AccessShareLock case that
compares anything *across* pages. The measures taken to prevent false
positives described within bt_target_page_check() require expert
review, especially because this is the one case where a faulty
rationale may result in under-protection from false positives, and not
just harmless over-protection.

The rationale for why we can reliably recover from a race described
within the C function bt_right_page_check_scankey() is *complicated*.
I may have failed to make it as simple as possible despite significant
effort. It's hard to describe these things in an accessible way. Maybe
someone can try and understand what I've said there, and let me know
how I might have fallen short. I have used a new term, "cousin page"
in this explanation (cf. sibling page). This seems like useful
terminology that makes these difficult explanations a bit more
accessible.

-- 
Peter Geoghegan

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

On Fri, Sep 2, 2016 at 11:19 AM, Kevin Grittner  wrote:
> IMV the process is to post a patch to this list to certify that it
> is yours to contribute and free of IP encumbrances that would
> prevent us from using it.  I will wait for that post.

I attach my V3. There are only very minor code changes here, such as
breaking out a separate elevel constant for DEBUG2 traces that show
information of how the B-Tree is accessed (e.g. current level, block
number). Tiny tweaks to about 3 comments were also performed. These
changes are trivial.

I've also removed the tests added, since external sort regression test
coverage is in a much better place now.

Finally, the documentation was updated, to make it closer to the
Github project's documentation. I expanded what was started as the
original amcheck sgml documentation based on the experience of using
amcheck on production databases at Heroku. This isn't a big change,
but it's the biggest in V3. The documentation now emphasizes the
likelihood of amcheck finding software errors, which is all we found.
Jim Gray predicted that fault tolerant systems will tend to have
almost all problems arise from operator error and software faults in
practice, so perhaps I should have predicted that that would be the
general trend.

-- 
Peter Geoghegan

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

amcheck (B-Tree integrity checking tool)

I was assigned an "action point" during the FOSDEM developer meeting:
"Post new version of btree consistency checker patch". I attach a new
WIP version of my consistency checker tool, amcheck. This patch is
proposed for 9.6, as an extension in contrib -- maybe we can still get
it in. This is the first time I've added any version of this to a
commitfest, although I've posted a couple of rough versions of this in
the past couple of years. The attached version has received a major
overhaul, and is primarily aimed at finding corruption in production
systems, although I think it will still have significant value for
debugging too. Maybe it can help with some of the B-Tree patches in
the final commitfest, for example. I also have some hope that it will
become a learning tool for people interested in how B-Tree indexes
work.

To recap, the extension adds some SQL-callable functions that verify
certain invariant conditions hold within some particular B-Tree index.
These are the conditions that index scans rely on always being true.
The tool's scope may eventually cover other AMs, including heapam, but
nbtree seems like the best place to start.

Note that no function currently checks that the index is consistent
with the heap, which would be very useful (that's probably how I'd
eventually target the heapam, actually).

Invariants
========

nbtree invariants that the tool verifies with just an AccessShareLock
on the relation are:

* That all items are in the correct, opclass order on each page.

* That the page "high key", if any, actually bounds the items on the page.

* That the last item on a page is less than or equal to the first item
on the next page (the page to its right). The idea here is that the
key space spans multiple pages, not just one page, so it make sense to
check the last item where we can.

With an ExclusiveLock + ShareLock, some addition invariants are verified:

* That child pages actually have their parent's downlink as a lower bound.

* Sane right links and left links at each level.

Obviously, this tool is all about distrusting the structure of a
B-Tree index. That being the case, it's not always totally clear where
to draw the line. I think I have the balance about right, though.

Interface
=======

There are only 2 SQL callable functions in the extension, which are
very similar:

bt_index_check(index regclass)

bt_index_parent_check(index regclass)

The latter is more thorough than the former -- it performs all checks,
including those checks that I mentioned required an ExclusiveLock. So,
bt_index_check() only requires an AccessShareLock.
bt_index_parent_check() requires an ExclusiveLock on the index
relation, and a ShareLock on its heap relation, almost like REINDEX.
bt_index_parent_check() performs verification that is a superset of
the verification performed by bt_index_check() -- mostly, the extra
verification/work is that it verifies downlinks against child pages.

Both functions raise an error in the event of observing that an
invariant in a B-Tree was violated, such as items being out of order
on a page. I've written extensive documentation, which goes into
practical aspects of using amcheck effectively. It doesn't go into
significant detail about every invariant that is checked, but gives a
good idea of roughly what checks are performed.

I could almost justify only having one function with an argument about
the downlink/child verification, but that would be a significant
footgun given the varying locking requirements that such a function
would have.

Locking
======

We never rely on something like holding on to a buffer pin as an
interlock for correctness (the vacuum interlock thing isn't generally
necessary, because we don't look at the heap at all). We simply pin +
BT_READ lock a buffer, copy it into local memory allocated by
palloc(), and then immediately release the buffer lock and drop the
pin. This is the same in all instances. There is never more than one
buffer lock or pin held at a time.

We do, on the other hand, have a detailed rationale for why it's okay
that we don't have an ExclusiveLock on the index relation for checks
that span the key space of more than one page by following right links
to compare items across sibling pages. This isn't the same thing as
having an explicit interlock like a pin -- our interlock is one
against *recycling* by vacuum, which is based on recentGlobalXmin.
This rationale requires expert review.

Performance
==========

Trying to keep the tool as simple as possible, while still making it
do verification that is as useful as possible was my priority here,
not performance. Still, verification completes fairly quickly.
Certainly, it takes far less time than having to REINDEX the index,
and doesn't need too much memory. I think that in practice most
problems that can be detected by the B-Tree checker functions will be
detected with the lighter variant.

-- 
Peter Geoghegan

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

On Sun, Nov 20, 2016 at 3:42 PM, Robert Haas  wrote:
> OK.  If it's not reasonable to continue checking after an ERROR, then
> I think ERROR is the way to go.  If somebody really doesn't like that
> lack of flexibility (in either direction), they can propose a change
> later for separate consideration.  That limitation is not, in my view,
> a sufficient reason to hold up the patch on the table.

I attach V4 of amcheck. I decided to leave things as they are, as far
as forcing a different elevel goes (you still need to modify a macro).
I didn't change the elevel macro from CONCERN in a couple of cases, as
Andres suggested, because in fact that's generally the same as DEBUG1,
not WARNING (I agreed with Andres that it was WARNING before, but it
isn't unless you #define NOT_USED).

Andres said: "Theoretically we should recheck that the oids still
match, theoretically the locking here allows the index->table mapping
to change". I don't know how to act on this feedback, since comparable
index + heap locking code should have the same problem, but doesn't
consider it. How is this any different to reindex_index()?

Other than that, all feedback items were worked through. I made the
functions PARALLEL SAFE, too, since I noticed that that wasn't the
case in passing.

-- 
Peter Geoghegan

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)

Re: amcheck (B-Tree integrity checking tool)