Re: Amcheck verification of GiST and GIN

On 5/9/25 14:43, Arseniy Mukhin wrote:
> Hello,
>
> Thanks everybody for the patch.
>
> I noticed there are no tests that GIN check fails if the index is
> corrupted, so I thought it would be great to have some.
> While writing tests I noticed some issues in the patch (all issues are
> for verify_gin.c)
>
> 1) When we add new items to the entry tree stack, ptr->parenttup is always null
> because GinPageGetOpaque(page)->rightlink is never NULL.
>
> /* last tuple in layer has no high key */
> if (i != maxoff && !GinPageGetOpaque(page)->rightlink)
> ptr->parenttup = CopyIndexTuple(idxtuple);
> else
> ptr->parenttup = NULL;
>
> Right way to check if entry doesn't have right neighbour is
>
> GinPageGetOpaque(page)->rightlink == InvalidBlockNumber
>
> But even if we fix it, the condition would not do what the comment
> says. If we want to have NULL as parenttup
> only for the last tuple of the btree layer, the right check would be:
>
> if (i == maxoff && rightlink == InvalidBlockNumber)
> ptr->parenttup = NULL;
> else
> ptr->parenttup = CopyIndexTuple(idxtuple);
>
> 2) Check don't use attnum in comparisons, but for multicolumn indexes
> attnum defines order. When we compare max entry page key
> with parent key we ignore attnum. It means we occasionally can try to
> compare keys of different columns.
> While checking order within the same page we skip checking order for
> tuples with different attnums now,
> but it can be checked. Fix is easy: using ginCompareAttEntries()
> instead of ginCompareEntries().
>
>
> 3) Here a code of the split detection
>
> if (rightlink != InvalidBlockNumber &&
> ginCompareEntries(&state, attnum, page_max_key,
> page_max_key_category, parent_key,
> parent_key_category) > 0)
> {
> /* split page detected, install right link to the stack */
>
> Condition seems not right, because the child page max item key never
> can be bigger then parent key.
> It can be equal to the parentkey, and it means that there was no split
> and the parent key that we cached in the stack is still
> relevant. Or it could be less then cached parent key and it means that
> split took place and old max item key moved to the
> right neighbour and current page max item key should be less then
> cached parent key. So I think we should replace > with <.
>
> 4) Here is the code for checking the order within the entry page.
>
> /*
> * First block is metadata, skip order check. Also, never check
> * for high key on rightmost page, as this key is not really
> * stored explicitly.
> *
> * Also make sure to not compare entries for different attnums,
> * which may be stored on the same page.
> */
> if (i != FirstOffsetNumber && attnum == prev_attnum &&
> stack->blkno != GIN_ROOT_BLKNO &&
> !(i == maxoff && rightlink == InvalidBlockNumber))
> {
> prev_key = gintuple_get_key(&state, prev_tuple,
> &prev_key_category);
> if (ginCompareEntries(&state, attnum, prev_key,
> prev_key_category, current_key,
> current_key_category) >= 0)
>
> We skip checking the order for the root page, it's not clear why.
> Probably there is some mess with the meta page, because
> comment says "First block is metadata, skip order check". So I think
> we can remove
>
> stack->blkno != GIN_ROOT_BLKNO
>
> 5) The same place as 4). We skip checking the order for the high key
> on the rightmost page, as this key is not really stored explicitly,
> but for leaf pages all keys are stored explicitly, so we can check the
> order for the last item of the leaf page too.
> So I think we can change the condition to this:
>
> !(i == maxoff && rightlink == InvalidBlockNumber &&
> !GinPageIsLeaf(page))
>
> 6) In posting tree parent key check part:
>
> /*
> * Check if this tuple is consistent with the downlink in the
> * parent.
> */
> if (stack->parentblk != InvalidBlockNumber && i == maxoff &&
> ItemPointerCompare(&stack->parentkey, &posting_item->key) < 0)
> ereport(ERROR,
> ...
> Here we don't check if stack->parentkey is valid, so sometimes we
> compare invalid parentkey (because we can have
> valid parentblk and invalid parentkey the same time). Invalid
> parentkey is always bigger, so the code never triggers
> ereport, but it doesn't look right. so probably we can rewrite it this way:
>
> if (i == maxoff && ItemPointerIsValid(&stack->parentkey) &&
> ItemPointerCompare(&stack->parentkey, &posting_item->key) < 0)
>
> 7) When producing stack entries for posting tree check, we set parent
> key like this:
>
> /*
> * Set rightmost parent key to invalid item pointer. Its value
> * is 'Infinity' and not explicitly stored.
> */
> if (rightlink == InvalidBlockNumber)
> ItemPointerSetInvalid(&ptr->parentkey);
> else
> ptr->parentkey = posting_item->key;
>
> We set invalid parent key for all items of the rightmost page. But
> it's the only rightmost item that doesn't have an explicit
> parentkey (actually the comment says exactly this, but the code does a
> different thing). All others have an explicit parent
> key and we can set it. So fix can look like this:
>
> if (rightlink == InvalidBlockNumber && i == maxoff)
> ItemPointerSetInvalid(&ptr->parentkey);
> else
> ptr->parentkey = posting_item->key;
>
> But for (rightlink == InvalidBlockNumber && i == maxoff)
> posting_item->key is always (0,0) (we check it a little bit earlier),
> so I think we can simplify it:
>
> ptr->parentkey = posting_item->key;
>
> 8) In the function gin_refind_parent() the code
>
> if (ItemPointerGetBlockNumber(&(itup->t_tid)) == childblkno)
>
> triggers Assert(ItemPointerIsValid(pointer)) within the
> ItemPointerGetBlockNumber(), because itup->t_tid could be invalid.
> AFAIS GIN code uses a special method GinGetDownlink(itup) that avoids
> this Assert. So we can use it here too.
>
> Please find the attached patch with fixes for issues above. Also there
> are added regression test for multicolumn index,
> and several tap tests with some basic corrupted index cases. I'm not
> sure if it's the right way to write such tests and would
> be glad to hear any feedback, especially about
> invalid_entry_columns_order_test() where it seems important to
> preserve
> byte ordering. Also all tests expect standard page size 8192 now.
>
>
> Also there are several points that I think also worth addressing:
>
> 9) Field 'parentlsn' is set but never actually used for any check. Or
> I missed something.
>
> 10) README says "Vacuum never deletes tuples or pages from the entry
> tree." But check assumes that it's possible to have
> deleted leaf page with 0 entries.
>
> if (GinPageIsDeleted(page))
> {
> if (!GinPageIsLeaf(page))
> ereport(ERROR,
> (errcode(ERRCODE_INDEX_CORRUPTED),
> errmsg("index \"%s\" has deleted internal page %u",
> RelationGetRelationName(rel), blockNo)));
> if (PageGetMaxOffsetNumber(page) > InvalidOffsetNumber)
> ereport(ERROR,
> (errcode(ERRCODE_INDEX_CORRUPTED),
> errmsg("index \"%s\" has deleted page %u with tuples",
> RelationGetRelationName(rel), blockNo)));
> }
> 11) When we compare entry tree max page key with parent key:
>
> if (ginCompareAttEntries(&state, attnum, current_key,
> current_key_category, parent_key_attnum,
> parent_key, parent_key_category) > 0)
> {
> /*
> * There was a discrepancy between parent and child
> * tuples. We need to verify it is not a result of
> * concurrent call of gistplacetopage(). So, lock parent
> * and try to find downlink for current page. It may be
> * missing due to concurrent page split, this is OK.
> */
> pfree(stack->parenttup);
> stack->parenttup = gin_refind_parent(rel, stack->parentblk,
> stack->blkno, strategy);
>
> I think we can remove gin_refind_parent() and do ereport right away here.
> The same logic as with 3). AFAIK it's impossible to have a child item
> with a key that is higher than the cached parent key.
> Parent key bounds what keys we can insert into the child page, so it
> seems there is no way how they can appear there.
>

These look like good points. I've added it to open items so that we
don't forget about this, I won't have time to look at this until after
pgconf.dev.

thanks

--
Tomas Vondra