Re: amcheck (B-Tree integrity checking tool)

Hi,


I think the patch could use a pgindent run.

On 2016-09-07 11:44:01 -0700, Peter Geoghegan wrote:
> diff --git a/contrib/amcheck/amcheck--1.0.sql b/contrib/amcheck/amcheck--1.0.sql
> new file mode 100644
> index 0000000..ebbd6ac
> --- /dev/null
> +++ b/contrib/amcheck/amcheck--1.0.sql
> @@ -0,0 +1,20 @@
> +/* contrib/amcheck/amcheck--1.0.sql */
> +
> +-- complain if script is sourced in psql, rather than via CREATE EXTENSION
> +\echo Use "CREATE EXTENSION amcheck" to load this file. \quit
> +
> +--
> +-- bt_index_check()
> +--
> +CREATE FUNCTION bt_index_check(index regclass)
> +RETURNS VOID
> +AS 'MODULE_PATHNAME', 'bt_index_check'
> +LANGUAGE C STRICT;
> +
> +--
> +-- bt_index_parent_check()
> +--
> +CREATE FUNCTION bt_index_parent_check(index regclass)
> +RETURNS VOID
> +AS 'MODULE_PATHNAME', 'bt_index_parent_check'
> +LANGUAGE C STRICT;

I'd really want a function that runs all check on a table.


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

Why is this a macro?


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

Hm, if we want that - and it doesn't seem like a bad idea - I think we
should be make it available without recompiling.


> +/*
> + * A B-Tree cannot possibly have this many levels, since there must be one
> + * block per level, which is bound by the range of BlockNumber:
> + */
> +#define InvalidBtreeLevel    ((uint32) InvalidBlockNumber)

Hm, I think it'd be, for the long term, better if we'd move the btree
check code to amcheck_nbtree.c or such.


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

Theoretically we should recheck that the oids still match, theoretically
the locking here allows the index->table mapping to change. It's not a
huge window tho...


> +    /* Check for active uses of the index in the current transaction */
> +    CheckTableNotInUse(indrel, "bt_index_parent_check");

Why do we actually care?



> +static void
> +btree_index_checkable(Relation rel)
> +{
> +    if (rel->rd_rel->relkind != RELKIND_INDEX ||
> +        rel->rd_rel->relam != BTREE_AM_OID)
> +        ereport(ERROR,
> +                (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
> +                 errmsg("only nbtree access method indexes are supported"),
> +                 errdetail("Relation \"%s\" is not a B-Tree index.",
> +                           RelationGetRelationName(rel))));
> +
> +    if (RELATION_IS_OTHER_TEMP(rel))
> +        ereport(ERROR,
> +                (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
> +                 errmsg("cannot access temporary tables of other sessions"),
> +                 errdetail("Index \"%s\" is associated with temporary relation.",
> +                           RelationGetRelationName(rel))));
> +
> +    if (!rel->rd_index->indisready)
> +        ereport(ERROR,
> +                (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
> +                 errmsg("cannot check index \"%s\"",
> +                        RelationGetRelationName(rel)),
> +                 errdetail("Index is not yet ready for insertions")));

Why can't we check this? Seems valuable to allow checking after a
partial CONCURRENTLY index build?

Why don't you use IndexIsReady et al? Not sure if the patch compiles
against an earlier release (there weren't valid/ready/live dead fields,
but instead it was compressed into fewer)?


> +/*
> + * bt_check_every_level()
> + *
> + * Main entry point for B-Tree SQL-callable functions.  Walks the B-Tree in
> + * logical order, verifying invariants as it goes.
> + *
> + * It is the caller's responsibility to acquire appropriate heavyweight lock on
> + * the index relation, and advise us if extra checks are safe when an
> + * ExclusiveLock is held.  An ExclusiveLock is generally assumed to prevent any
> + * kind of physical modification to the index structure, including
> + * modifications that VACUUM may make.
> + */

Hm, what kind of locking does the kill_prior_tuple stuff use?


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

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

Hm, isn't that a potentially spurious report?


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

> +    do
> +    {
> +        /* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
> +        CHECK_FOR_INTERRUPTS();
> +
> +        /* Initialize state for this iteration */
> +        state->targetblock = current;
> +        state->target = palloc_btree_page(state, state->targetblock);
> +        state->targetlsn = PageGetLSN(state->target);
> +
> +        opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
> +
> +        if (P_IGNORE(opaque))
> +        {
> +            if (P_RIGHTMOST(opaque))
> +                ereport(CORRUPTION,
> +                        (errcode(ERRCODE_INDEX_CORRUPTED),
> +                         errmsg("block %u fell off the end of index \"%s\"",
> +                                current, RelationGetRelationName(state->rel))));
> +            else
> +                ereport(CONCERN,
> +                        (errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
> +                         errmsg("block %u of index \"%s\" ignored",
> +                                current, RelationGetRelationName(state->rel))));

Hm, why is this worth a WARNING? Isn't it perfectly normal to have a few
of these?


> +            /*
> +             * Before beginning any non-trivial examination of level, establish
> +             * next level down's leftmost block number, which next call here
> +             * will pass as its leftmost (iff this isn't leaf level).

"next level down's leftmost block number" - it'd be good to simplify
that a bit.


> +/*
> + * bt_target_page_check()

Why "target"?

> +static void
> +bt_target_page_check(BtreeCheckState *state)
> +{


> +        /*
> +         *   ********************
> +         *   * Page order check *
> +         *   ********************

Isn't that item order, rather than page order?


> +        }
> +        /*
> +         *   ********************
> +         *   * Last item check  *
> +         *   ********************

Newline before block wouldn't hurt.


> +         * Check last item against next/right page's first data item's when
> +         * last item on page is reached.

I think this need some polishing.



> +        /*
> +         *   ********************
> +         *   * Downlink check   *
> +         *   ********************
> +         *
> +         * Additional check of child items against target page (their parent),
> +         * iff this is internal page and caller holds ExclusiveLock on index

s/is/is an/ /holds/holds an/


> +static ScanKey
> +bt_right_page_check_scankey(BtreeCheckState *state)
> +{

> +     * A deleted page won't actually be recycled by VACUUM early enough for us
> +     * to fail to be able follow its right link (or left link, or downlink),

"for us to fail to be able" sounds odd.

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

s/item/an item/?


This paragraph is too complicated to follow in the noisy environment
where we both currently are ;)

> +/*
> + * bt_downlink_check()
> + *
> + * Checks one of target's downlink against its child page.

downlinks?

> + * Conceptually, the target page continues to be what is checked here.  The
> + * target block is still blamed in the event of finding an invariant violation.
> + * The downlink insertion into the target is probably where any problem raised
> + * here arises, and there is no such thing as a parent link, so doing the
> + * verification this way around is much more practical.
> + */
> +static void
> +bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
> +                  ScanKey targetkey)
> +{

> +     * between the deleted page and its right sibling.  (We cannot delete a
> +     * parent page's rightmost page unless it is the last child page, and we
> +     * intend to delete the parent itself.)

"parent page's rightmost page"?


I like this. Some of the more complex pieces towards the end of the
field need some attention, there's a fair amount of word-smithing
needed, and I do think we want to make the structural changes outlined
above, but besides these, imo fairly simple adaptions, I do think this
is useful and not that far from being committable.


- Andres