verify_nbtree.c File Reference
#include "postgres.h"#include "access/heaptoast.h"#include "access/htup_details.h"#include "access/nbtree.h"#include "access/table.h"#include "access/tableam.h"#include "access/transam.h"#include "access/xact.h"#include "verify_common.h"#include "catalog/index.h"#include "catalog/pg_am.h"#include "catalog/pg_opfamily_d.h"#include "common/pg_prng.h"#include "lib/bloomfilter.h"#include "miscadmin.h"#include "storage/smgr.h"#include "utils/guc.h"#include "utils/memutils.h"#include "utils/snapmgr.h"
Include dependency graph for verify_nbtree.c:
Go to the source code of this file.
Data Structures | |
| struct | BtreeCheckState |
| struct | BtreeLevel |
| struct | BtreeLastVisibleEntry |
| struct | BTCallbackState |
Macros | |
| #define | InvalidBtreeLevel ((uint32) InvalidBlockNumber) |
| #define | BTreeTupleGetNKeyAtts(itup, rel) Min(IndexRelationGetNumberOfKeyAttributes(rel), BTreeTupleGetNAtts(itup, rel)) |
Typedefs | |
| typedef struct BtreeCheckState | BtreeCheckState |
| typedef struct BtreeLevel | BtreeLevel |
| typedef struct BtreeLastVisibleEntry | BtreeLastVisibleEntry |
| typedef struct BTCallbackState | BTCallbackState |
Macro Definition Documentation
◆ BTreeTupleGetNKeyAtts
| #define BTreeTupleGetNKeyAtts | ( | itup, | |
| rel | |||
| ) | Min(IndexRelationGetNumberOfKeyAttributes(rel), BTreeTupleGetNAtts(itup, rel)) |
Definition at line 56 of file verify_nbtree.c.
◆ InvalidBtreeLevel
| #define InvalidBtreeLevel ((uint32) InvalidBlockNumber) |
Definition at line 55 of file verify_nbtree.c.
Typedef Documentation
◆ BTCallbackState
| typedef struct BTCallbackState BTCallbackState |
◆ BtreeCheckState
| typedef struct BtreeCheckState BtreeCheckState |
◆ BtreeLastVisibleEntry
| typedef struct BtreeLastVisibleEntry BtreeLastVisibleEntry |
◆ BtreeLevel
| typedef struct BtreeLevel BtreeLevel |
Function Documentation
◆ bt_check_every_level()
|
static |
Definition at line 376 of file verify_nbtree.c.
379{
381 Page metapage;
382 BTMetaPageData *metad;
383 uint32 previouslevel;
384 BtreeLevel current;
385
386 if (!readonly)
388 RelationGetRelationName(rel));
389 else
390 elog(DEBUG1, "verifying consistency of tree structure for index \"%s\" with cross-level checks",
391 RelationGetRelationName(rel));
392
393 /*
394 * This assertion matches the one in index_getnext_tid(). See page
395 * recycling/"visible to everyone" notes in nbtree README.
396 */
398
399 /*
400 * Initialize state for entire verification operation
401 */
403 state->rel = rel;
404 state->heaprel = heaprel;
405 state->heapkeyspace = heapkeyspace;
406 state->readonly = readonly;
407 state->heapallindexed = heapallindexed;
408 state->rootdescend = rootdescend;
409 state->checkunique = checkunique;
411
413 {
414 int64 total_pages;
415 int64 total_elems;
416 uint64 seed;
417
418 /*
419 * Size Bloom filter based on estimated number of tuples in index,
420 * while conservatively assuming that each block must contain at least
421 * MaxTIDsPerBTreePage / 3 "plain" tuples -- see
422 * bt_posting_plain_tuple() for definition, and details of how posting
423 * list tuples are handled.
424 */
425 total_pages = RelationGetNumberOfBlocks(rel);
428 /* Generate a random seed to avoid repetition */
430 /* Create Bloom filter to fingerprint index */
432 state->heaptuplespresent = 0;
433
434 /*
435 * Register our own snapshot for heapallindexed, rather than asking
436 * table_index_build_scan() to do this for us later. This needs to
437 * happen before index fingerprinting begins, so we can later be
438 * certain that index fingerprinting should have reached all tuples
439 * returned by table_index_build_scan().
440 */
442
443 /*
444 * GetTransactionSnapshot() always acquires a new MVCC snapshot in
445 * READ COMMITTED mode. A new snapshot is guaranteed to have all the
446 * entries it requires in the index.
447 *
448 * We must defend against the possibility that an old xact snapshot
449 * was returned at higher isolation levels when that snapshot is not
450 * safe for index scans of the target index. This is possible when
451 * the snapshot sees tuples that are before the index's indcheckxmin
452 * horizon. Throwing an error here should be very rare. It doesn't
453 * seem worth using a secondary snapshot to avoid this.
454 */
457 state->snapshot->xmin))
461 RelationGetRelationName(rel)));
462 }
463
464 /*
465 * We need a snapshot to check the uniqueness of the index. For better
466 * performance, take it once per index check. If one was already taken
467 * above, use that.
468 */
470 {
472
475 }
476
480 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
481 errmsg("cannot verify that tuples from index \"%s\" can each be found by an independent index search",
482 RelationGetRelationName(rel)),
484
485 /* Create context for page */
487 "amcheck context",
488 ALLOCSET_DEFAULT_SIZES);
490
491 /* Get true root block from meta-page */
493 metad = BTPageGetMeta(metapage);
494
495 /*
496 * Certain deletion patterns can result in "skinny" B-Tree indexes, where
497 * the fast root and true root differ.
498 *
499 * Start from the true root, not the fast root, unlike conventional index
500 * scans. This approach is more thorough, and removes the risk of
501 * following a stale fast root from the meta page.
502 */
505 (errcode(ERRCODE_NO_DATA),
507 RelationGetRelationName(rel)),
511
512 /*
513 * Starting at the root, verify every level. Move left to right, top to
514 * bottom. Note that there may be no pages other than the meta page (meta
515 * page can indicate that root is P_NONE when the index is totally empty).
516 */
517 previouslevel = InvalidBtreeLevel;
522 {
523 /*
524 * Verify this level, and get left most page for next level down, if
525 * not at leaf level
526 */
528
531 (errcode(ERRCODE_INDEX_CORRUPTED),
533 RelationGetRelationName(rel), previouslevel)));
534
535 previouslevel = current.level;
536 }
537
538 /*
539 * * Check whether heap contains unindexed/malformed tuples *
540 */
542 {
544 TableScanDesc scan;
545
546 /*
547 * Create our own scan for table_index_build_scan(), rather than
548 * getting it to do so for us. This is required so that we can
549 * actually use the MVCC snapshot registered earlier.
550 *
551 * Note that table_index_build_scan() calls heap_endscan() for us.
552 */
555 0, /* number of keys */
556 NULL, /* scan key */
557 true, /* buffer access strategy OK */
558 true); /* syncscan OK? */
559
560 /*
561 * Scan will behave as the first scan of a CREATE INDEX CONCURRENTLY
562 * behaves.
563 *
564 * It's okay that we don't actually use the same lock strength for the
565 * heap relation as any other ii_Concurrent caller would. We have no
566 * reason to care about a concurrent VACUUM operation, since there
567 * isn't going to be a second scan of the heap that needs to be sure
568 * that there was no concurrent recycling of TIDs.
569 */
571
572 /*
573 * Don't wait for uncommitted tuple xact commit/abort when index is a
574 * unique index on a catalog (or an index used by an exclusion
575 * constraint). This could otherwise happen in the readonly case.
576 */
578 indexinfo->ii_ExclusionOps = NULL;
579 indexinfo->ii_ExclusionProcs = NULL;
580 indexinfo->ii_ExclusionStrats = NULL;
581
585
588
590 (errmsg_internal("finished verifying presence of " INT64_FORMAT " tuples from table \"%s\" with bitset %.2f%% set",
593
595 }
596
597 /* Be tidy: */
601}
bloom_filter * bloom_create(int64 total_elems, int bloom_work_mem, uint64 seed)
Definition: bloomfilter.c:87
BufferAccessStrategy GetAccessStrategy(BufferAccessStrategyType btype)
Definition: freelist.c:461
Assert(PointerIsAligned(start, uint64))
static TransactionId HeapTupleHeaderGetXmin(const HeapTupleHeaderData *tup)
Definition: htup_details.h:324
Definition: nbtree.h:105
Definition: verify_nbtree.c:71
Definition: verify_nbtree.c:139
Definition: execnodes.h:163
Definition: relscan.h:34
Definition: regguts.h:323
static double table_index_build_scan(Relation table_rel, Relation index_rel, IndexInfo *index_info, bool allow_sync, bool progress, IndexBuildCallback callback, void *callback_state, TableScanDesc scan)
Definition: tableam.h:1754
static TableScanDesc table_beginscan_strat(Relation rel, Snapshot snapshot, int nkeys, ScanKeyData *key, bool allow_strat, bool allow_sync)
Definition: tableam.h:900
static bool TransactionIdPrecedes(TransactionId id1, TransactionId id2)
Definition: transam.h:263
static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
Definition: verify_nbtree.c:622
static void bt_tuple_present_callback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *checkstate)
Definition: verify_nbtree.c:2778
static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum)
Definition: verify_nbtree.c:3288
References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, Assert(), BAS_BULKREAD, bloom_create(), bloom_free(), bloom_prop_bits_set(), bt_check_level_from_leftmost(), bt_tuple_present_callback(), BTMetaPageData::btm_fastlevel, BTMetaPageData::btm_fastroot, BTMetaPageData::btm_level, BTMetaPageData::btm_root, BTPageGetMeta, BTREE_METAPAGE, BuildIndexInfo(), CurrentMemoryContext, DEBUG1, elog, ereport, errcode(), ERRCODE_T_R_SERIALIZATION_FAILURE, errdetail_internal(), errhint(), errmsg(), errmsg_internal(), ERROR, GetAccessStrategy(), GetTransactionSnapshot(), HeapTupleHeaderGetXmin(), IndexInfo::ii_Concurrent, IndexInfo::ii_ExclusionOps, IndexInfo::ii_ExclusionProcs, IndexInfo::ii_ExclusionStrats, IndexInfo::ii_Unique, INT64_FORMAT, InvalidBlockNumber, InvalidBtreeLevel, InvalidSnapshot, IsolationUsesXactSnapshot, BtreeLevel::istruerootlevel, BtreeLevel::leftmost, BtreeLevel::level, maintenance_work_mem, Max, MaxTIDsPerBTreePage, MemoryContextDelete(), P_NONE, palloc0(), palloc_btree_page(), pg_global_prng_state, pg_prng_uint64(), RelationData::rd_index, RelationData::rd_indextuple, RecentXmin, RegisterSnapshot(), RelationGetNumberOfBlocks, RelationGetRelationName, HeapTupleData::t_data, table_beginscan_strat(), table_index_build_scan(), TransactionIdIsValid, TransactionIdPrecedes(), and UnregisterSnapshot().
Referenced by bt_index_check_callback().
◆ bt_check_level_from_leftmost()
|
static |
Definition at line 622 of file verify_nbtree.c.
623{
624 /* State to establish early, concerning entire level */
625 BTPageOpaque opaque;
626 MemoryContext oldcontext;
627 BtreeLevel nextleveldown;
628
629 /* Variables for iterating across level using right links */
632
633 /* Initialize return state */
637
638 /* Use page-level context for duration of this call */
640
642 level.istruerootlevel ?
644
647
648 do
649 {
650 /* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
651 CHECK_FOR_INTERRUPTS();
652
653 /* Initialize state for this iteration */
654 state->targetblock = current;
657
659
661 {
662 /*
663 * Since there cannot be a concurrent VACUUM operation in readonly
664 * mode, and since a page has no links within other pages
665 * (siblings and parent) once it is marked fully deleted, it
666 * should be impossible to land on a fully deleted page in
667 * readonly mode. See bt_child_check() for further details.
668 *
669 * The bt_child_check() P_ISDELETED() check is repeated here so
670 * that pages that are only reachable through sibling links get
671 * checked.
672 */
675 (errcode(ERRCODE_INDEX_CORRUPTED),
679 current, leftcurrent, opaque->btpo_prev)));
680
683 (errcode(ERRCODE_INDEX_CORRUPTED),
686 else
688 (errcode(ERRCODE_NO_DATA),
691 goto nextpage;
692 }
694 {
695 /*
696 * A concurrent page split could make the caller supplied leftmost
697 * block no longer contain the leftmost page, or no longer be the
698 * true root, but where that isn't possible due to heavyweight
699 * locking, check that the first valid page meets caller's
700 * expectations.
701 */
703 {
706 (errcode(ERRCODE_INDEX_CORRUPTED),
709
712 (errcode(ERRCODE_INDEX_CORRUPTED),
715 }
716
717 /*
718 * Before beginning any non-trivial examination of level, prepare
719 * state for next bt_check_level_from_leftmost() invocation for
720 * the next level for the next level down (if any).
721 *
722 * There should be at least one non-ignorable page per level,
723 * unless this is the leaf level, which is assumed by caller to be
724 * final level.
725 */
727 {
728 IndexTuple itup;
729 ItemId itemid;
730
731 /* Internal page -- downlink gets leftmost on next level */
733 state->target,
734 P_FIRSTDATAKEY(opaque));
738 }
739 else
740 {
741 /*
742 * Leaf page -- final level caller must process.
743 *
744 * Note that this could also be the root page, if there has
745 * been no root page split yet.
746 */
749 }
750
751 /*
752 * Finished setting up state for this call/level. Control will
753 * never end up back here in any future loop iteration for this
754 * level.
755 */
756 }
757
758 /*
759 * Sibling links should be in mutual agreement. There arises
760 * leftcurrent == P_NONE && btpo_prev != P_NONE when the left sibling
761 * of the parent's low-key downlink is half-dead. (A half-dead page
762 * has no downlink from its parent.) Under heavyweight locking, the
763 * last bt_leftmost_ignoring_half_dead() validated this btpo_prev.
764 * Without heavyweight locking, validation of the P_NONE case remains
765 * unimplemented.
766 */
769
770 /* Check level */
773 (errcode(ERRCODE_INDEX_CORRUPTED),
774 errmsg("leftmost down link for level points to block in index \"%s\" whose level is not one level down",
778
779 /* Verify invariants for page */
781
782nextpage:
783
784 /* Try to detect circular links */
787 (errcode(ERRCODE_INDEX_CORRUPTED),
790
791 leftcurrent = current;
792 current = opaque->btpo_next;
793
795 {
798 state->lowkey = NULL;
799 }
800
801 /*
802 * Copy current target high key as the low key of right sibling.
803 * Allocate memory in upper level context, so it would be cleared
804 * after reset of target context.
805 *
806 * We only need the low key in corner cases of checking child high
807 * keys. We use high key only when incomplete split on the child level
808 * falls to the boundary of pages on the target level. See
809 * bt_child_highkey_check() for details. So, typically we won't end
810 * up doing anything with low key, but it's simpler for general case
811 * high key verification to always have it available.
812 *
813 * The correctness of managing low key in the case of concurrent
814 * splits wasn't investigated yet. Thankfully we only need low key
815 * for readonly verification and concurrent splits won't happen.
816 */
818 {
819 IndexTuple itup;
820 ItemId itemid;
821
825
828 }
829
830 /* Free page and associated memory for this iteration */
832 }
834
836 {
839 state->lowkey = NULL;
840 }
841
842 /* Don't change context for caller */
843 MemoryContextSwitchTo(oldcontext);
844
845 return nextleveldown;
846}
static void * PageGetItem(const PageData *page, const ItemIdData *itemId)
Definition: bufpage.h:353
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1229
static BlockNumber BTreeTupleGetDownLink(IndexTuple pivot)
Definition: nbtree.h:557
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
Definition: nbtree.h:64
Definition: itup.h:36
Definition: itemid.h:26
Definition: memnodes.h:118
static bool bt_leftmost_ignoring_half_dead(BtreeCheckState *state, BlockNumber start, BTPageOpaque start_opaque)
Definition: verify_nbtree.c:1008
static void bt_target_page_check(BtreeCheckState *state)
Definition: verify_nbtree.c:1237
static ItemId PageGetItemIdCareful(BtreeCheckState *state, BlockNumber block, Page page, OffsetNumber offset)
Definition: verify_nbtree.c:3490
static void bt_recheck_sibling_links(BtreeCheckState *state, BlockNumber btpo_prev_from_target, BlockNumber leftcurrent)
Definition: verify_nbtree.c:1097
References Assert(), bt_leftmost_ignoring_half_dead(), bt_recheck_sibling_links(), bt_target_page_check(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BTreeTupleGetDownLink(), CHECK_FOR_INTERRUPTS, DEBUG1, elog, ereport, errcode(), errdetail_internal(), errmsg(), errmsg_internal(), ERROR, IndexTupleSize(), InvalidBlockNumber, InvalidBtreeLevel, BtreeLevel::istruerootlevel, BtreeLevel::leftmost, BtreeLevel::level, MemoryContextAlloc(), MemoryContextReset(), MemoryContextSwitchTo(), P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_ISDELETED, P_ISLEAF, P_ISROOT, P_NONE, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetLSN(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_check_every_level().
◆ bt_child_check()
|
static |
Definition at line 2390 of file verify_nbtree.c.
2392{
2393 ItemId itemid;
2394 IndexTuple itup;
2395 BlockNumber childblock;
2396 OffsetNumber offset;
2397 OffsetNumber maxoffset;
2398 Page child;
2399 BTPageOpaque copaque;
2400 BTPageOpaque topaque;
2401
2403 state->target, downlinkoffnum);
2405 childblock = BTreeTupleGetDownLink(itup);
2406
2407 /*
2408 * Caller must have ShareLock on target relation, because of
2409 * considerations around page deletion by VACUUM.
2410 *
2411 * NB: In general, page deletion deletes the right sibling's downlink, not
2412 * the downlink of the page being deleted; the deleted page's downlink is
2413 * reused for its sibling. The key space is thereby consolidated between
2414 * the deleted page and its right sibling. (We cannot delete a parent
2415 * page's rightmost child unless it is the last child page, and we intend
2416 * to also delete the parent itself.)
2417 *
2418 * If this verification happened without a ShareLock, the following race
2419 * condition could cause false positives:
2420 *
2421 * In general, concurrent page deletion might occur, including deletion of
2422 * the left sibling of the child page that is examined here. If such a
2423 * page deletion were to occur, closely followed by an insertion into the
2424 * newly expanded key space of the child, a window for the false positive
2425 * opens up: the stale parent/target downlink originally followed to get
2426 * to the child legitimately ceases to be a lower bound on all items in
2427 * the page, since the key space was concurrently expanded "left".
2428 * (Insertion followed the "new" downlink for the child, not our now-stale
2429 * downlink, which was concurrently physically removed in target/parent as
2430 * part of deletion's first phase.)
2431 *
2432 * While we use various techniques elsewhere to perform cross-page
2433 * verification for !readonly callers, a similar trick seems difficult
2434 * here. The tricks used by bt_recheck_sibling_links and by
2435 * bt_right_page_check_scankey both involve verification of a same-level,
2436 * cross-sibling invariant. Cross-level invariants are far more squishy,
2437 * though. The nbtree REDO routines do not actually couple buffer locks
2438 * across levels during page splits, so making any cross-level check work
2439 * reliably in !readonly mode may be impossible.
2440 */
2442
2443 /*
2444 * Verify child page has the downlink key from target page (its parent) as
2445 * a lower bound; downlink must be strictly less than all keys on the
2446 * page.
2447 *
2448 * Check all items, rather than checking just the first and trusting that
2449 * the operator class obeys the transitive law.
2450 */
2453 copaque = BTPageGetOpaque(child);
2454 maxoffset = PageGetMaxOffsetNumber(child);
2455
2456 /*
2457 * Since we've already loaded the child block, combine this check with
2458 * check for downlink connectivity.
2459 */
2461 child, topaque->btpo_level);
2462
2463 /*
2464 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2465 * and since a page has no links within other pages (siblings and parent)
2466 * once it is marked fully deleted, it should be impossible to land on a
2467 * fully deleted page.
2468 *
2469 * It does not quite make sense to enforce that the page cannot even be
2470 * half-dead, despite the fact the downlink is modified at the same stage
2471 * that the child leaf page is marked half-dead. That's incorrect because
2472 * there may occasionally be multiple downlinks from a chain of pages
2473 * undergoing deletion, where multiple successive calls are made to
2474 * _bt_unlink_halfdead_page() by VACUUM before it can finally safely mark
2475 * the leaf page as fully dead. While _bt_mark_page_halfdead() usually
2476 * removes the downlink to the leaf page that is marked half-dead, that's
2477 * not guaranteed, so it's possible we'll land on a half-dead page with a
2478 * downlink due to an interrupted multi-level page deletion.
2479 *
2480 * We go ahead with our checks if the child page is half-dead. It's safe
2481 * to do so because we do not test the child's high key, so it does not
2482 * matter that the original high key will have been replaced by a dummy
2483 * truncated high key within _bt_mark_page_halfdead(). All other page
2484 * items are left intact on a half-dead page, so there is still something
2485 * to test.
2486 */
2489 (errcode(ERRCODE_INDEX_CORRUPTED),
2493 state->targetblock, childblock,
2495
2497 offset <= maxoffset;
2498 offset = OffsetNumberNext(offset))
2499 {
2500 /*
2501 * Skip comparison of target page key against "negative infinity"
2502 * item, if any. Checking it would indicate that it's not a strict
2503 * lower bound, but that's only because of the hard-coding for
2504 * negative infinity items within _bt_compare().
2505 *
2506 * If nbtree didn't truncate negative infinity tuples during internal
2507 * page splits then we'd expect child's negative infinity key to be
2508 * equal to the scankey/downlink from target/parent (it would be a
2509 * "low key" in this hypothetical scenario, and so it would still need
2510 * to be treated as a special case here).
2511 *
2512 * Negative infinity items can be thought of as a strict lower bound
2513 * that works transitively, with the last non-negative-infinity pivot
2514 * followed during a descent from the root as its "true" strict lower
2515 * bound. Only a small number of negative infinity items are truly
2516 * negative infinity; those that are the first items of leftmost
2517 * internal pages. In more general terms, a negative infinity item is
2518 * only negative infinity with respect to the subtree that the page is
2519 * at the root of.
2520 *
2521 * See also: bt_rootdescend(), which can even detect transitive
2522 * inconsistencies on cousin leaf pages.
2523 */
2525 continue;
2526
2528 offset))
2530 (errcode(ERRCODE_INDEX_CORRUPTED),
2534 state->targetblock, childblock, offset,
2536 }
2537
2538 pfree(child);
2539}
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
Definition: bufpage.h:371
static bool offset_is_negative_infinity(BTPageOpaque opaque, OffsetNumber offset)
Definition: verify_nbtree.c:3071
static void bt_child_highkey_check(BtreeCheckState *state, OffsetNumber target_downlinkoffnum, Page loaded_child, uint32 target_level)
Definition: verify_nbtree.c:2143
static bool invariant_l_nontarget_offset(BtreeCheckState *state, BTScanInsert key, BlockNumber nontargetblock, Page nontarget, OffsetNumber upperbound)
Definition: verify_nbtree.c:3228
References Assert(), bt_child_highkey_check(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTreeTupleGetDownLink(), ereport, errcode(), errdetail_internal(), errmsg(), ERROR, invariant_l_nontarget_offset(), LSN_FORMAT_ARGS, offset_is_negative_infinity(), OffsetNumberNext, P_FIRSTDATAKEY, P_ISDELETED, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_target_page_check().
◆ bt_child_highkey_check()
|
static |
Definition at line 2143 of file verify_nbtree.c.
2147{
2149 Page page;
2150 BTPageOpaque opaque;
2152 bool first = true;
2153 ItemId itemid;
2154 IndexTuple itup;
2155 BlockNumber downlink;
2156
2158 {
2160 state->target, target_downlinkoffnum);
2162 downlink = BTreeTupleGetDownLink(itup);
2163 }
2164 else
2165 {
2166 downlink = P_NONE;
2167 }
2168
2169 /*
2170 * If no previous rightlink is memorized for current level just below
2171 * target page's level, we are about to start from the leftmost page. We
2172 * can't follow rightlinks from previous page, because there is no
2173 * previous page. But we still can match high key.
2174 *
2175 * So we initialize variables for the loop above like there is previous
2176 * page referencing current child. Also we imply previous page to not
2177 * have incomplete split flag, that would make us require downlink for
2178 * current child. That's correct, because leftmost page on the level
2179 * should always have parent downlink.
2180 */
2182 {
2183 blkno = downlink;
2184 rightsplit = false;
2185 }
2186
2187 /* Move to the right on the child level */
2188 while (true)
2189 {
2190 /*
2191 * Did we traverse the whole tree level and this is check for pages to
2192 * the right of rightmost downlink?
2193 */
2195 {
2198 return;
2199 }
2200
2201 /* Did we traverse the whole tree level and don't find next downlink? */
2204 (errcode(ERRCODE_INDEX_CORRUPTED),
2206 state->prevrightlink, downlink,
2208
2209 /* Load page contents */
2210 if (blkno == downlink && loaded_child)
2211 page = loaded_child;
2212 else
2214
2215 opaque = BTPageGetOpaque(page);
2216
2217 /* The first page we visit at the level should be leftmost */
2221 (errcode(ERRCODE_INDEX_CORRUPTED),
2225 state->targetblock, blkno,
2227
2228 /* Do level sanity check */
2230 opaque->btpo_level != target_level - 1)
2232 (errcode(ERRCODE_INDEX_CORRUPTED),
2236 blkno, target_level - 1, opaque->btpo_level)));
2237
2238 /* Try to detect circular links */
2241 (errcode(ERRCODE_INDEX_CORRUPTED),
2244
2246 {
2247 /* blkno probably has missing parent downlink */
2249 }
2250
2251 rightsplit = P_INCOMPLETE_SPLIT(opaque);
2252
2253 /*
2254 * If we visit page with high key, check that it is equal to the
2255 * target key next to corresponding downlink.
2256 */
2258 {
2259 BTPageOpaque topaque;
2260 IndexTuple highkey;
2261 OffsetNumber pivotkey_offset;
2262
2263 /* Get high key */
2266
2267 /*
2268 * There might be two situations when we examine high key. If
2269 * current child page is referenced by given target downlink, we
2270 * should look to the next offset number for matching key from
2271 * target page.
2272 *
2273 * Alternatively, we're following rightlinks somewhere in the
2274 * middle between page referenced by previous target's downlink
2275 * and the page referenced by current target's downlink. If
2276 * current child page hasn't incomplete split flag set, then its
2277 * high key should match to the target's key of current offset
2278 * number. This happens when a previous call here (to
2279 * bt_child_highkey_check()) found an incomplete split, and we
2280 * reach a right sibling page without a downlink -- the right
2281 * sibling page's high key still needs to be matched to a
2282 * separator key on the parent/target level.
2283 *
2284 * Don't apply OffsetNumberNext() to target_downlinkoffnum when we
2285 * already had to step right on the child level. Our traversal of
2286 * the child level must try to move in perfect lockstep behind (to
2287 * the left of) the target/parent level traversal.
2288 */
2289 if (blkno == downlink)
2290 pivotkey_offset = OffsetNumberNext(target_downlinkoffnum);
2291 else
2292 pivotkey_offset = target_downlinkoffnum;
2293
2295
2297 {
2298 /*
2299 * If we're looking for the next pivot tuple in target page,
2300 * but there is no more pivot tuples, then we should match to
2301 * high key instead.
2302 */
2304 {
2307 (errcode(ERRCODE_INDEX_CORRUPTED),
2311 state->targetblock, blkno,
2313 pivotkey_offset = P_HIKEY;
2314 }
2316 state->target, pivotkey_offset);
2318 }
2319 else
2320 {
2321 /*
2322 * We cannot try to match child's high key to a negative
2323 * infinity key in target, since there is nothing to compare.
2324 * However, it's still possible to match child's high key
2325 * outside of target page. The reason why we're are is that
2326 * bt_child_highkey_check() was previously called for the
2327 * cousin page of 'loaded_child', which is incomplete split.
2328 * So, now we traverse to the right of that cousin page and
2329 * current child level page under consideration still belongs
2330 * to the subtree of target's left sibling. Thus, we need to
2331 * match child's high key to its left uncle page high key.
2332 * Thankfully we saved it, it's called a "low key" of target
2333 * page.
2334 */
2337 (errcode(ERRCODE_INDEX_CORRUPTED),
2341 state->targetblock, blkno,
2343 itup = state->lowkey;
2344 }
2345
2347 {
2349 (errcode(ERRCODE_INDEX_CORRUPTED),
2353 state->targetblock, blkno,
2355 }
2356 }
2357
2358 /* Exit if we already found next downlink */
2359 if (blkno == downlink)
2360 {
2362 state->previncompletesplit = rightsplit;
2363 return;
2364 }
2365
2366 /* Traverse to the next page using rightlink */
2367 blkno = opaque->btpo_next;
2368
2369 /* Free page contents if it's allocated by us */
2370 if (page != loaded_child)
2371 pfree(page);
2372 first = false;
2373 }
2374}
static bool bt_pivot_tuple_identical(bool heapkeyspace, IndexTuple itup1, IndexTuple itup2)
Definition: verify_nbtree.c:2070
static void bt_downlink_missing_check(BtreeCheckState *state, bool rightsplit, BlockNumber blkno, Page page)
Definition: verify_nbtree.c:2555
References BlockNumberIsValid(), bt_downlink_missing_check(), bt_leftmost_ignoring_half_dead(), bt_pivot_tuple_identical(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BTreeTupleGetDownLink(), ereport, errcode(), errdetail_internal(), errmsg(), ERROR, InvalidBlockNumber, LSN_FORMAT_ARGS, offset_is_negative_infinity(), OffsetNumberIsValid, OffsetNumberNext, P_HAS_FULLXID, P_HIKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_ISDELETED, P_ISHALFDEAD, P_NONE, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_child_check(), and bt_target_page_check().
◆ bt_downlink_missing_check()
|
static |
Definition at line 2555 of file verify_nbtree.c.
2557{
2559 ItemId itemid;
2560 IndexTuple itup;
2561 Page child;
2562 BTPageOpaque copaque;
2563 uint32 level;
2564 BlockNumber childblk;
2565 XLogRecPtr pagelsn;
2566
2569
2570 /* No next level up with downlinks to fingerprint from the true root */
2572 return;
2573
2574 pagelsn = PageGetLSN(page);
2575
2576 /*
2577 * Incomplete (interrupted) page splits can account for the lack of a
2578 * downlink. Some inserting transaction should eventually complete the
2579 * page split in passing, when it notices that the left sibling page is
2580 * P_INCOMPLETE_SPLIT().
2581 *
2582 * In general, VACUUM is not prepared for there to be no downlink to a
2583 * page that it deletes. This is the main reason why the lack of a
2584 * downlink can be reported as corruption here. It's not obvious that an
2585 * invalid missing downlink can result in wrong answers to queries,
2586 * though, since index scans that land on the child may end up
2587 * consistently moving right. The handling of concurrent page splits (and
2588 * page deletions) within _bt_moveright() cannot distinguish
2589 * inconsistencies that last for a moment from inconsistencies that are
2590 * permanent and irrecoverable.
2591 *
2592 * VACUUM isn't even prepared to delete pages that have no downlink due to
2593 * an incomplete page split, but it can detect and reason about that case
2594 * by design, so it shouldn't be taken to indicate corruption. See
2595 * _bt_pagedel() for full details.
2596 */
2597 if (rightsplit)
2598 {
2600 (errcode(ERRCODE_NO_DATA),
2604 blkno, opaque->btpo_level,
2605 opaque->btpo_prev,
2606 LSN_FORMAT_ARGS(pagelsn))));
2607 return;
2608 }
2609
2610 /*
2611 * Page under check is probably the "top parent" of a multi-level page
2612 * deletion. We'll need to descend the subtree to make sure that
2613 * descendant pages are consistent with that, though.
2614 *
2615 * If the page (which must be non-ignorable) is a leaf page, then clearly
2616 * it can't be the top parent. The lack of a downlink is probably a
2617 * symptom of a broad problem that could just as easily cause
2618 * inconsistencies anywhere else.
2619 */
2622 (errcode(ERRCODE_INDEX_CORRUPTED),
2626 blkno,
2627 LSN_FORMAT_ARGS(pagelsn))));
2628
2629 /* Descend from the given page, which is an internal page */
2630 elog(DEBUG1, "checking for interrupted multi-level deletion due to missing downlink in index \"%s\"",
2632
2633 level = opaque->btpo_level;
2636 childblk = BTreeTupleGetDownLink(itup);
2637 for (;;)
2638 {
2639 CHECK_FOR_INTERRUPTS();
2640
2642 copaque = BTPageGetOpaque(child);
2643
2645 break;
2646
2647 /* Do an extra sanity check in passing on internal pages */
2650 (errcode(ERRCODE_INDEX_CORRUPTED),
2653 errdetail_internal("Top parent/under check block=%u block pointed to=%u expected level=%u level in pointed to block=%u.",
2654 blkno, childblk,
2655 level - 1, copaque->btpo_level)));
2656
2657 level = copaque->btpo_level;
2659 P_FIRSTDATAKEY(copaque));
2661 childblk = BTreeTupleGetDownLink(itup);
2662 /* Be slightly more pro-active in freeing this memory, just in case */
2663 pfree(child);
2664 }
2665
2666 /*
2667 * Since there cannot be a concurrent VACUUM operation in readonly mode,
2668 * and since a page has no links within other pages (siblings and parent)
2669 * once it is marked fully deleted, it should be impossible to land on a
2670 * fully deleted page. See bt_child_check() for further details.
2671 *
2672 * The bt_child_check() P_ISDELETED() check is repeated here because
2673 * bt_child_check() does not visit pages reachable through negative
2674 * infinity items. Besides, bt_child_check() is unwilling to descend
2675 * multiple levels. (The similar bt_child_check() P_ISDELETED() check
2676 * within bt_check_level_from_leftmost() won't reach the page either,
2677 * since the leaf's live siblings should have their sibling links updated
2678 * to bypass the deletion target page when it is marked fully dead.)
2679 *
2680 * If this error is raised, it might be due to a previous multi-level page
2681 * deletion that failed to realize that it wasn't yet safe to mark the
2682 * leaf page as fully dead. A "dangling downlink" will still remain when
2683 * this happens. The fact that the dangling downlink's page (the leaf's
2684 * parent/ancestor page) lacked a downlink is incidental.
2685 */
2688 (errcode(ERRCODE_INDEX_CORRUPTED),
2691 errdetail_internal("Top parent/target block=%u leaf block=%u top parent/under check lsn=%X/%08X.",
2692 blkno, childblk,
2693 LSN_FORMAT_ARGS(pagelsn))));
2694
2695 /*
2696 * Iff leaf page is half-dead, its high key top parent link should point
2697 * to what VACUUM considered to be the top parent page at the instant it
2698 * was interrupted. Provided the high key link actually points to the
2699 * page under check, the missing downlink we detected is consistent with
2700 * there having been an interrupted multi-level page deletion. This means
2701 * that the subtree with the page under check at its root (a page deletion
2702 * chain) is in a consistent state, enabling VACUUM to resume deleting the
2703 * entire chain the next time it encounters the half-dead leaf page.
2704 */
2706 {
2710 return;
2711 }
2712
2714 (errcode(ERRCODE_INDEX_CORRUPTED),
2718 blkno, opaque->btpo_level,
2719 LSN_FORMAT_ARGS(pagelsn))));
2720}
static BlockNumber BTreeTupleGetTopParent(IndexTuple leafhikey)
Definition: nbtree.h:621
References Assert(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_prev, BTreeTupleGetDownLink(), BTreeTupleGetTopParent(), CHECK_FOR_INTERRUPTS, DEBUG1, elog, ereport, errcode(), errdetail_internal(), errmsg(), errmsg_internal(), ERROR, LSN_FORMAT_ARGS, P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_ISDELETED, P_ISHALFDEAD, P_ISLEAF, P_ISROOT, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetLSN(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_child_highkey_check().
◆ bt_entry_unique_check()
|
static |
Definition at line 909 of file verify_nbtree.c.
912{
913 ItemPointer tid;
914 bool has_visible_entry = false;
915
917
918 /*
919 * Current tuple has posting list. Report duplicate if TID of any posting
920 * list entry is visible and lVis->tid is valid.
921 */
923 {
925 {
928 {
929 has_visible_entry = true;
931 {
933 lVis,
934 tid, targetblock,
935 offset, i);
936 }
937
938 /*
939 * Prevent double reporting unique constraint violation
940 * between the posting list entries of the first tuple on the
941 * page after cross-page check.
942 */
944 return;
945
946 lVis->blkno = targetblock;
947 lVis->offset = offset;
949 lVis->tid = tid;
950 }
951 }
952 }
953
954 /*
955 * Current tuple has no posting list. If TID is visible save info about it
956 * for the next comparisons in the loop in bt_target_page_check(). Report
957 * duplicate if lVis->tid is already valid.
958 */
959 else
960 {
961 tid = BTreeTupleGetHeapTID(itup);
963 {
964 has_visible_entry = true;
966 {
968 lVis,
969 tid, targetblock,
970 offset, -1);
971 }
972
973 lVis->blkno = targetblock;
974 lVis->offset = offset;
975 lVis->tid = tid;
976 lVis->postingIndex = -1;
977 }
978 }
979
980 if (!has_visible_entry &&
982 lVis->blkno != targetblock)
983 {
984 char *posting = "";
985
989 (errcode(ERRCODE_NO_DATA),
991 targetblock, offset,
993 errdetail("It doesn't have visible heap tids and key is equal to the tid=(%u,%u)%s (points to heap tid=(%u,%u)).",
998 }
999}
static OffsetNumber ItemPointerGetOffsetNumberNoCheck(const ItemPointerData *pointer)
Definition: itemptr.h:114
static BlockNumber ItemPointerGetBlockNumberNoCheck(const ItemPointerData *pointer)
Definition: itemptr.h:93
static bool ItemPointerIsValid(const ItemPointerData *pointer)
Definition: itemptr.h:83
static uint16 BTreeTupleGetNPosting(IndexTuple posting)
Definition: nbtree.h:519
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
Definition: nbtree.h:545
static ItemPointer BTreeTupleGetHeapTID(IndexTuple itup)
Definition: nbtree.h:639
Definition: itemptr.h:37
static void bt_report_duplicate(BtreeCheckState *state, BtreeLastVisibleEntry *lVis, ItemPointer nexttid, BlockNumber nblock, OffsetNumber noffset, int nposting)
Definition: verify_nbtree.c:869
static bool heap_entry_is_visible(BtreeCheckState *state, ItemPointer tid)
Definition: verify_nbtree.c:850
References Assert(), BtreeLastVisibleEntry::blkno, bt_report_duplicate(), BTreeTupleGetHeapTID(), BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), DEBUG1, ereport, errcode(), errdetail(), errhint(), errmsg(), heap_entry_is_visible(), i, InvalidBlockNumber, ItemPointerGetBlockNumberNoCheck(), ItemPointerGetOffsetNumberNoCheck(), ItemPointerIsValid(), BtreeLastVisibleEntry::offset, P_NONE, BtreeLastVisibleEntry::postingIndex, psprintf(), RelationGetRelationName, and BtreeLastVisibleEntry::tid.
Referenced by bt_target_page_check().
◆ bt_index_check()
| Datum bt_index_check | ( | PG_FUNCTION_ARGS | ) |
Definition at line 250 of file verify_nbtree.c.
251{
254
259
264
265 amcheck_lock_relation_and_check(indrelid, BTREE_AM_OID,
268
269 PG_RETURN_VOID();
270}
Definition: verify_nbtree.c:167
void amcheck_lock_relation_and_check(Oid indrelid, Oid am_id, IndexDoCheckCallback check, LOCKMODE lockmode, void *state)
Definition: verify_common.c:62
static void bt_index_check_callback(Relation indrel, Relation heaprel, void *state, bool readonly)
Definition: verify_nbtree.c:310
References AccessShareLock, amcheck_lock_relation_and_check(), generate_unaccent_rules::args, bt_index_check_callback(), PG_GETARG_BOOL, PG_GETARG_OID, PG_NARGS, and PG_RETURN_VOID.
◆ bt_index_check_callback()
|
static |
Definition at line 310 of file verify_nbtree.c.
311{
313 bool heapkeyspace,
314 allequalimage;
315
318 (errcode(ERRCODE_INDEX_CORRUPTED),
320 RelationGetRelationName(indrel))));
321
322 /* Extract metadata from metapage, and sanitize it in passing */
323 _bt_metaversion(indrel, &heapkeyspace, &allequalimage);
324 if (allequalimage && !heapkeyspace)
326 (errcode(ERRCODE_INDEX_CORRUPTED),
328 RelationGetRelationName(indrel))));
330 {
331 bool has_interval_ops = false;
332
335 {
336 has_interval_ops = true;
338 (errcode(ERRCODE_INDEX_CORRUPTED),
340 RelationGetRelationName(indrel)),
341 has_interval_ops
343 : 0));
344 }
345 }
346
347 /* Check index, possibly against table it is an index on */
348 bt_check_every_level(indrel, heaprel, heapkeyspace, readonly,
350}
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
Definition: nbtpage.c:740
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:534
static void bt_check_every_level(Relation rel, Relation heaprel, bool heapkeyspace, bool readonly, bool heapallindexed, bool rootdescend, bool checkunique)
Definition: verify_nbtree.c:376
References _bt_allequalimage(), _bt_metaversion(), generate_unaccent_rules::args, bt_check_every_level(), ereport, errcode(), errhint(), errmsg(), ERROR, i, IndexRelationGetNumberOfKeyAttributes, MAIN_FORKNUM, RelationData::rd_opfamily, RelationGetRelationName, RelationGetSmgr(), and smgrexists().
Referenced by bt_index_check(), and bt_index_parent_check().
◆ bt_index_parent_check()
| Datum bt_index_parent_check | ( | PG_FUNCTION_ARGS | ) |
Definition at line 282 of file verify_nbtree.c.
283{
286
291
298
299 amcheck_lock_relation_and_check(indrelid, BTREE_AM_OID,
302
303 PG_RETURN_VOID();
304}
References amcheck_lock_relation_and_check(), generate_unaccent_rules::args, bt_index_check_callback(), PG_GETARG_BOOL, PG_GETARG_OID, PG_NARGS, PG_RETURN_VOID, and ShareLock.
◆ bt_leftmost_ignoring_half_dead()
|
static |
Definition at line 1008 of file verify_nbtree.c.
1011{
1013 reached_from = start;
1014 bool all_half_dead = true;
1015
1016 /*
1017 * To handle the !readonly case, we'd need to accept BTP_DELETED pages and
1018 * potentially observe nbtree/README "Page deletion and backwards scans".
1019 */
1021
1023 {
1026
1027 CHECK_FOR_INTERRUPTS();
1028
1029 /*
1030 * Try to detect btpo_prev circular links. _bt_unlink_halfdead_page()
1031 * writes that side-links will continue to point to the siblings.
1032 * Check btpo_next for that property.
1033 */
1034 all_half_dead = P_ISHALFDEAD(reached_opaque) &&
1035 reached != start &&
1036 reached != reached_from &&
1037 reached_opaque->btpo_next == reached_from;
1038 if (all_half_dead)
1039 {
1041
1042 /* pagelsn should point to an XLOG_BTREE_MARK_PAGE_HALFDEAD */
1044 (errcode(ERRCODE_NO_DATA),
1048 reached, reached_from,
1049 LSN_FORMAT_ARGS(pagelsn))));
1050
1051 reached_from = reached;
1052 reached = reached_opaque->btpo_prev;
1053 }
1054
1055 pfree(page);
1056 }
1057
1058 return all_half_dead;
1059}
References Assert(), BTPageGetOpaque, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, CHECK_FOR_INTERRUPTS, DEBUG1, ereport, errcode(), errdetail_internal(), errmsg_internal(), LSN_FORMAT_ARGS, P_ISHALFDEAD, P_NONE, PageGetLSN(), palloc_btree_page(), pfree(), RelationGetRelationName, and start.
Referenced by bt_check_level_from_leftmost(), and bt_child_highkey_check().
◆ bt_mkscankey_pivotsearch()
|
inlinestatic |
Definition at line 3466 of file verify_nbtree.c.
3467{
3468 BTScanInsert skey;
3469
3470 skey = _bt_mkscankey(rel, itup);
3472
3473 return skey;
3474}
Definition: nbtree.h:796
References _bt_mkscankey(), and BTScanInsertData::backward.
Referenced by bt_right_page_check_scankey(), and bt_target_page_check().
◆ bt_normalize_tuple()
|
static |
Definition at line 2846 of file verify_nbtree.c.
2847{
2852 bool formnewtup = false;
2853 IndexTuple reformed;
2855
2856 /* Caller should only pass "logical" non-pivot tuples here */
2858
2859 /* Easy case: It's immediately clear that tuple has no varlena datums */
2861 return itup;
2862
2864 {
2865 Form_pg_attribute att;
2866
2868
2869 /* Assume untoasted/already normalized datum initially */
2872 tupleDescriptor,
2873 &isnull[i]);
2875 continue;
2876
2877 /*
2878 * Callers always pass a tuple that could safely be inserted into the
2879 * index without further processing, so an external varlena header
2880 * should never be encountered here
2881 */
2884 (errcode(ERRCODE_INDEX_CORRUPTED),
2891 (att->attstorage == TYPSTORAGE_EXTENDED ||
2892 att->attstorage == TYPSTORAGE_MAIN))
2893 {
2894 /*
2895 * This value will be compressed by index_form_tuple() with the
2896 * current storage settings. We may be here because this tuple
2897 * was formed with different storage settings. So, force forming.
2898 */
2899 formnewtup = true;
2900 }
2902 {
2903 formnewtup = true;
2906 }
2907
2908 /*
2909 * Short tuples may have 1B or 4B header. Convert 4B header of short
2910 * tuples to 1B
2911 */
2913 {
2914 /* convert to short varlena */
2917
2920
2921 formnewtup = true;
2924 }
2925 }
2926
2927 /*
2928 * Easier case: Tuple has varlena datums, none of which are compressed or
2929 * short with 4B header
2930 */
2931 if (!formnewtup)
2932 return itup;
2933
2934 /*
2935 * Hard case: Tuple had compressed varlena datums that necessitate
2936 * creating normalized version of the tuple from uncompressed input datums
2937 * (normalized input datums). This is rather naive, but shouldn't be
2938 * necessary too often.
2939 *
2940 * In the heap, tuples may contain short varlena datums with both 1B
2941 * header and 4B headers. But the corresponding index tuple should always
2942 * have such varlena's with 1B headers. So, if there is a short varlena
2943 * with 4B header, we need to convert it for fingerprinting.
2944 *
2945 * Note that we rely on deterministic index_form_tuple() TOAST compression
2946 * of normalized input.
2947 */
2948 reformed = index_form_tuple(tupleDescriptor, normalized, isnull);
2950
2951 /* Cannot leak memory here */
2955
2956 return reformed;
2957}
IndexTuple index_form_tuple(TupleDesc tupleDescriptor, const Datum *values, const bool *isnull)
Definition: indextuple.c:44
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
static bool IndexTupleHasVarwidths(const IndexTupleData *itup)
Definition: itup.h:83
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: itup.h:131
Definition: tupdesc.h:136
static FormData_pg_attribute * TupleDescAttr(TupleDesc tupdesc, int i)
Definition: tupdesc.h:160
static Size VARATT_CONVERTED_SHORT_SIZE(const void *PTR)
Definition: varatt.h:425
References Assert(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), data, DatumGetPointer(), ereport, errcode(), errmsg(), ERROR, i, index_form_tuple(), index_getattr(), INDEX_MAX_KEYS, IndexTupleHasVarwidths(), ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), len, TupleDescData::natts, palloc(), pfree(), PG_DETOAST_DATUM, PointerGetDatum(), RelationGetDescr, RelationGetRelationName, SET_VARSIZE_SHORT(), IndexTupleData::t_tid, TOAST_INDEX_TARGET, TupleDescAttr(), VARATT_CAN_MAKE_SHORT(), VARATT_CONVERTED_SHORT_SIZE(), VARATT_IS_COMPRESSED(), VARATT_IS_EXTERNAL(), VARDATA(), and VARSIZE().
Referenced by bt_target_page_check(), and bt_tuple_present_callback().
◆ bt_pivot_tuple_identical()
|
static |
Definition at line 2070 of file verify_nbtree.c.
2071{
2073 return false;
2074
2075 if (heapkeyspace)
2076 {
2077 /*
2078 * Offset number will contain important information in heapkeyspace
2079 * indexes: the number of attributes left in the pivot tuple following
2080 * suffix truncation. Don't skip over it (compare it too).
2081 */
2083 IndexTupleSize(itup1) -
2084 offsetof(ItemPointerData, ip_posid)) != 0)
2085 return false;
2086 }
2087 else
2088 {
2089 /*
2090 * Cannot rely on offset number field having consistent value across
2091 * levels on pg_upgrade'd !heapkeyspace indexes. Compare contents of
2092 * tuple starting from just after item pointer (i.e. after block
2093 * number and offset number).
2094 */
2096 IndexTupleSize(itup1) -
2097 offsetof(IndexTupleData, t_info)) != 0)
2098 return false;
2099 }
2100
2101 return true;
2102}
References IndexTupleSize(), ItemPointerData::ip_posid, IndexTupleData::t_info, and IndexTupleData::t_tid.
Referenced by bt_child_highkey_check().
◆ bt_posting_plain_tuple()
|
inlinestatic |
Definition at line 2974 of file verify_nbtree.c.
2975{
2977
2978 /* Returns non-posting-list tuple */
2980}
IndexTuple _bt_form_posting(IndexTuple base, const ItemPointerData *htids, int nhtids)
Definition: nbtdedup.c:862
References _bt_form_posting(), Assert(), BTreeTupleGetPostingN(), and BTreeTupleIsPosting().
Referenced by bt_target_page_check().
◆ bt_recheck_sibling_links()
|
static |
Definition at line 1097 of file verify_nbtree.c.
1100{
1101 /* passing metapage to BTPageGetOpaque() would give irrelevant findings */
1103
1105 {
1106 Buffer lbuf;
1107 Buffer newtargetbuf;
1108 Page page;
1109 BTPageOpaque opaque;
1110 BlockNumber newtargetblock;
1111
1112 /* Couple locks in the usual order for nbtree: Left to right */
1117 page = BufferGetPage(lbuf);
1118 opaque = BTPageGetOpaque(page);
1120 {
1121 /*
1122 * Cannot reason about concurrently deleted page -- the left link
1123 * in the page to the right is expected to point to some other
1124 * page to the left (not leftcurrent page).
1125 *
1126 * Note that we deliberately don't give up with a half-dead page.
1127 */
1128 UnlockReleaseBuffer(lbuf);
1129 return;
1130 }
1131
1132 newtargetblock = opaque->btpo_next;
1133 /* Avoid self-deadlock when newtargetblock == leftcurrent */
1134 if (newtargetblock != leftcurrent)
1135 {
1137 newtargetblock, RBM_NORMAL,
1138 state->checkstrategy);
1141 page = BufferGetPage(newtargetbuf);
1142 opaque = BTPageGetOpaque(page);
1143 /* btpo_prev_from_target may have changed; update it */
1144 btpo_prev_from_target = opaque->btpo_prev;
1145 }
1146 else
1147 {
1148 /*
1149 * leftcurrent right sibling points back to leftcurrent block.
1150 * Index is corrupt. Easiest way to handle this is to pretend
1151 * that we actually read from a distinct page that has an invalid
1152 * block number in its btpo_prev.
1153 */
1154 newtargetbuf = InvalidBuffer;
1155 btpo_prev_from_target = InvalidBlockNumber;
1156 }
1157
1158 /*
1159 * No need to check P_ISDELETED here, since new target block cannot be
1160 * marked deleted as long as we hold a lock on lbuf
1161 */
1163 UnlockReleaseBuffer(newtargetbuf);
1164 UnlockReleaseBuffer(lbuf);
1165
1166 if (btpo_prev_from_target == leftcurrent)
1167 {
1168 /* Report split in left sibling, not target (or new target) */
1170 (errcode(ERRCODE_INTERNAL_ERROR),
1174 leftcurrent, newtargetblock,
1175 state->targetblock)));
1176 return;
1177 }
1178
1179 /*
1180 * Index is corrupt. Make sure that we report correct target page.
1181 *
1182 * This could have changed in cases where there was a concurrent page
1183 * split, as well as index corruption (at least in theory). Note that
1184 * btpo_prev_from_target was already updated above.
1185 */
1186 state->targetblock = newtargetblock;
1187 }
1188
1190 (errcode(ERRCODE_INDEX_CORRUPTED),
1194 state->targetblock, leftcurrent,
1195 btpo_prev_from_target)));
1196}
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:792
References _bt_checkpage(), Assert(), BT_READ, BTPageGetOpaque, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BufferGetPage(), BufferIsValid(), DEBUG1, ereport, errcode(), errdetail_internal(), errmsg(), errmsg_internal(), ERROR, InvalidBlockNumber, InvalidBuffer, LockBuffer(), MAIN_FORKNUM, P_ISDELETED, P_NONE, RBM_NORMAL, ReadBufferExtended(), RelationGetRelationName, and UnlockReleaseBuffer().
Referenced by bt_check_level_from_leftmost().
◆ bt_report_duplicate()
|
static |
Definition at line 869 of file verify_nbtree.c.
873{
874 char *htid,
875 *nhtid,
876 *itid,
877 *nitid = "",
878 *pposting = "",
879 *pnposting = "";
880
885 ItemPointerGetBlockNumberNoCheck(nexttid),
886 ItemPointerGetOffsetNumberNoCheck(nexttid));
888
891
894
895 if (nposting >= 0)
897
899 (errcode(ERRCODE_INDEX_CORRUPTED),
903 itid, pposting, nitid, pnposting, htid, nhtid,
905}
References BtreeLastVisibleEntry::blkno, ereport, errcode(), errdetail(), errmsg(), ERROR, ItemPointerGetBlockNumberNoCheck(), ItemPointerGetOffsetNumberNoCheck(), LSN_FORMAT_ARGS, BtreeLastVisibleEntry::offset, BtreeLastVisibleEntry::postingIndex, psprintf(), RelationGetRelationName, and BtreeLastVisibleEntry::tid.
Referenced by bt_entry_unique_check().
◆ bt_right_page_check_scankey()
|
static |
Definition at line 1863 of file verify_nbtree.c.
1864{
1865 BTPageOpaque opaque;
1866 ItemId rightitem;
1867 IndexTuple firstitup;
1868 BlockNumber targetnext;
1869 Page rightpage;
1870 OffsetNumber nline;
1871
1872 /* Determine target's next block number */
1874
1875 /* If target is already rightmost, no right sibling; nothing to do here */
1877 return NULL;
1878
1879 /*
1880 * General notes on concurrent page splits and page deletion:
1881 *
1882 * Routines like _bt_search() don't require *any* page split interlock
1883 * when descending the tree, including something very light like a buffer
1884 * pin. That's why it's okay that we don't either. This avoidance of any
1885 * need to "couple" buffer locks is the raison d' etre of the Lehman & Yao
1886 * algorithm, in fact.
1887 *
1888 * That leaves deletion. A deleted page won't actually be recycled by
1889 * VACUUM early enough for us to fail to at least follow its right link
1890 * (or left link, or downlink) and find its sibling, because recycling
1891 * does not occur until no possible index scan could land on the page.
1892 * Index scans can follow links with nothing more than their snapshot as
1893 * an interlock and be sure of at least that much. (See page
1894 * recycling/"visible to everyone" notes in nbtree README.)
1895 *
1896 * Furthermore, it's okay if we follow a rightlink and find a half-dead or
1897 * dead (ignorable) page one or more times. There will either be a
1898 * further right link to follow that leads to a live page before too long
1899 * (before passing by parent's rightmost child), or we will find the end
1900 * of the entire level instead (possible when parent page is itself the
1901 * rightmost on its level).
1902 */
1903 targetnext = opaque->btpo_next;
1904 for (;;)
1905 {
1906 CHECK_FOR_INTERRUPTS();
1907
1909 opaque = BTPageGetOpaque(rightpage);
1910
1912 break;
1913
1914 /*
1915 * We landed on a deleted or half-dead sibling page. Step right until
1916 * we locate a live sibling page.
1917 */
1919 (errcode(ERRCODE_NO_DATA),
1920 errmsg_internal("level %u sibling page in block %u of index \"%s\" was found deleted or half dead",
1923
1924 targetnext = opaque->btpo_next;
1925
1926 /* Be slightly more pro-active in freeing this memory, just in case */
1927 pfree(rightpage);
1928 }
1929
1930 /*
1931 * No ShareLock held case -- why it's safe to proceed.
1932 *
1933 * Problem:
1934 *
1935 * We must avoid false positive reports of corruption when caller treats
1936 * item returned here as an upper bound on target's last item. In
1937 * general, false positives are disallowed. Avoiding them here when
1938 * caller is !readonly is subtle.
1939 *
1940 * A concurrent page deletion by VACUUM of the target page can result in
1941 * the insertion of items on to this right sibling page that would
1942 * previously have been inserted on our target page. There might have
1943 * been insertions that followed the target's downlink after it was made
1944 * to point to right sibling instead of target by page deletion's first
1945 * phase. The inserters insert items that would belong on target page.
1946 * This race is very tight, but it's possible. This is our only problem.
1947 *
1948 * Non-problems:
1949 *
1950 * We are not hindered by a concurrent page split of the target; we'll
1951 * never land on the second half of the page anyway. A concurrent split
1952 * of the right page will also not matter, because the first data item
1953 * remains the same within the left half, which we'll reliably land on. If
1954 * we had to skip over ignorable/deleted pages, it cannot matter because
1955 * their key space has already been atomically merged with the first
1956 * non-ignorable page we eventually find (doesn't matter whether the page
1957 * we eventually find is a true sibling or a cousin of target, which we go
1958 * into below).
1959 *
1960 * Solution:
1961 *
1962 * Caller knows that it should reverify that target is not ignorable
1963 * (half-dead or deleted) when cross-page sibling item comparison appears
1964 * to indicate corruption (invariant fails). This detects the single race
1965 * condition that exists for caller. This is correct because the
1966 * continued existence of target block as non-ignorable (not half-dead or
1967 * deleted) implies that target page was not merged into from the right by
1968 * deletion; the key space at or after target never moved left. Target's
1969 * parent either has the same downlink to target as before, or a <
1970 * downlink due to deletion at the left of target. Target either has the
1971 * same highkey as before, or a highkey < before when there is a page
1972 * split. (The rightmost concurrently-split-from-target-page page will
1973 * still have the same highkey as target was originally found to have,
1974 * which for our purposes is equivalent to target's highkey itself never
1975 * changing, since we reliably skip over
1976 * concurrently-split-from-target-page pages.)
1977 *
1978 * In simpler terms, we allow that the key space of the target may expand
1979 * left (the key space can move left on the left side of target only), but
1980 * the target key space cannot expand right and get ahead of us without
1981 * our detecting it. The key space of the target cannot shrink, unless it
1982 * shrinks to zero due to the deletion of the original page, our canary
1983 * condition. (To be very precise, we're a bit stricter than that because
1984 * it might just have been that the target page split and only the
1985 * original target page was deleted. We can be more strict, just not more
1986 * lax.)
1987 *
1988 * Top level tree walk caller moves on to next page (makes it the new
1989 * target) following recovery from this race. (cf. The rationale for
1990 * child/downlink verification needing a ShareLock within
1991 * bt_child_check(), where page deletion is also the main source of
1992 * trouble.)
1993 *
1994 * Note that it doesn't matter if right sibling page here is actually a
1995 * cousin page, because in order for the key space to be readjusted in a
1996 * way that causes us issues in next level up (guiding problematic
1997 * concurrent insertions to the cousin from the grandparent rather than to
1998 * the sibling from the parent), there'd have to be page deletion of
1999 * target's parent page (affecting target's parent's downlink in target's
2000 * grandparent page). Internal page deletion only occurs when there are
2001 * no child pages (they were all fully deleted), and caller is checking
2002 * that the target's parent has at least one non-deleted (so
2003 * non-ignorable) child: the target page. (Note that the first phase of
2004 * deletion atomically marks the page to be deleted half-dead/ignorable at
2005 * the same time downlink in its parent is removed, so caller will
2006 * definitely not fail to detect that this happened.)
2007 *
2008 * This trick is inspired by the method backward scans use for dealing
2009 * with concurrent page splits; concurrent page deletion is a problem that
2010 * similarly receives special consideration sometimes (it's possible that
2011 * the backwards scan will re-read its "original" block after failing to
2012 * find a right-link to it, having already moved in the opposite direction
2013 * (right/"forwards") a few times to try to locate one). Just like us,
2014 * that happens only to determine if there was a concurrent page deletion
2015 * of a reference page, and just like us if there was a page deletion of
2016 * that reference page it means we can move on from caring about the
2017 * reference page. See the nbtree README for a full description of how
2018 * that works.
2019 */
2020 nline = PageGetMaxOffsetNumber(rightpage);
2021
2022 /*
2023 * Get first data item, if any
2024 */
2026 {
2027 /* Return first data item (if any) */
2029 P_FIRSTDATAKEY(opaque));
2030 *rightfirstoffset = P_FIRSTDATAKEY(opaque);
2031 }
2034 {
2035 /*
2036 * Return first item after the internal page's "negative infinity"
2037 * item
2038 */
2041 }
2042 else
2043 {
2044 /*
2045 * No first item. Page is probably empty leaf page, but it's also
2046 * possible that it's an internal page with only a negative infinity
2047 * item.
2048 */
2050 (errcode(ERRCODE_NO_DATA),
2054 return NULL;
2055 }
2056
2057 /*
2058 * Return first real item scankey. Note that this relies on right page
2059 * memory remaining allocated.
2060 */
2063}
static BTScanInsert bt_mkscankey_pivotsearch(Relation rel, IndexTuple itup)
Definition: verify_nbtree.c:3466
References bt_mkscankey_pivotsearch(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, CHECK_FOR_INTERRUPTS, DEBUG2, ereport, errcode(), errdetail_internal(), errmsg_internal(), OffsetNumberNext, P_FIRSTDATAKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), and RelationGetRelationName.
Referenced by bt_target_page_check().
◆ bt_rootdescend()
|
static |
Definition at line 3007 of file verify_nbtree.c.
3008{
3010 BTStack stack;
3011 Buffer lbuf;
3012 bool exists;
3013
3016
3017 /*
3018 * Search from root.
3019 *
3020 * Ideally, we would arrange to only move right within _bt_search() when
3021 * an interrupted page split is detected (i.e. when the incomplete split
3022 * bit is found to be set), but for now we accept the possibility that
3023 * that could conceal an inconsistency.
3024 */
3026 exists = false;
3028
3030 {
3031 BTInsertStateData insertstate;
3032 OffsetNumber offnum;
3033 Page page;
3034
3035 insertstate.itup = itup;
3038 insertstate.postingoff = 0;
3040 insertstate.buf = lbuf;
3041
3042 /* Get matching tuple on leaf page */
3044 /* Compare first >= matching item on leaf page, if any */
3045 page = BufferGetPage(lbuf);
3046 /* Should match on first heap TID when tuple has a posting list */
3048 insertstate.postingoff <= 0 &&
3050 exists = true;
3052 }
3053
3054 _bt_freestack(stack);
3056
3057 return exists;
3058}
BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access)
Definition: nbtsearch.c:107
OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
Definition: nbtsearch.c:479
int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum)
Definition: nbtsearch.c:693
Definition: nbtree.h:821
Definition: nbtree.h:744
References _bt_binsrch_insert(), _bt_compare(), _bt_freestack(), _bt_mkscankey(), _bt_relbuf(), _bt_search(), Assert(), BTInsertStateData::bounds_valid, BT_READ, BTInsertStateData::buf, BufferGetPage(), BufferIsValid(), IndexTupleSize(), BTInsertStateData::itemsz, BTInsertStateData::itup, BTInsertStateData::itup_key, sort-test::key, MAXALIGN, PageGetMaxOffsetNumber(), pfree(), and BTInsertStateData::postingoff.
Referenced by bt_target_page_check().
◆ bt_target_page_check()
|
static |
Definition at line 1237 of file verify_nbtree.c.
1238{
1239 OffsetNumber offset;
1240 OffsetNumber max;
1241 BTPageOpaque topaque;
1242
1243 /* Last visible entry info for checking indexes with unique constraint */
1245
1248
1251
1252 /*
1253 * Check the number of attributes in high key. Note, rightmost page
1254 * doesn't contain a high key, so nothing to check
1255 */
1257 {
1258 ItemId itemid;
1259 IndexTuple itup;
1260
1261 /* Verify line pointer before checking tuple */
1265 P_HIKEY))
1266 {
1269 (errcode(ERRCODE_INDEX_CORRUPTED),
1273 state->targetblock,
1277 }
1278 }
1279
1280 /*
1281 * Loop over page items, starting from first non-highkey item, not high
1282 * key (if any). Most tests are not performed for the "negative infinity"
1283 * real item (if any).
1284 */
1286 offset <= max;
1287 offset = OffsetNumberNext(offset))
1288 {
1289 ItemId itemid;
1290 IndexTuple itup;
1291 size_t tupsize;
1292 BTScanInsert skey;
1293 bool lowersizelimit;
1294 ItemPointer scantid;
1295
1296 /*
1297 * True if we already called bt_entry_unique_check() for the current
1298 * item. This helps to avoid visiting the heap for keys, which are
1299 * anyway presented only once and can't comprise a unique violation.
1300 */
1301 bool unique_checked = false;
1302
1303 CHECK_FOR_INTERRUPTS();
1304
1306 state->target, offset);
1308 tupsize = IndexTupleSize(itup);
1309
1310 /*
1311 * lp_len should match the IndexTuple reported length exactly, since
1312 * lp_len is completely redundant in indexes, and both sources of
1313 * tuple length are MAXALIGN()'d. nbtree does not use lp_len all that
1314 * frequently, and is surprisingly tolerant of corrupt lp_len fields.
1315 */
1318 (errcode(ERRCODE_INDEX_CORRUPTED),
1322 state->targetblock, offset,
1323 tupsize, ItemIdGetLength(itemid),
1326
1327 /* Check the number of index tuple attributes */
1329 offset))
1330 {
1331 ItemPointer tid;
1332 char *itid,
1333 *htid;
1334
1336 tid = BTreeTupleGetPointsToTID(itup);
1338 ItemPointerGetBlockNumberNoCheck(tid),
1339 ItemPointerGetOffsetNumberNoCheck(tid));
1340
1342 (errcode(ERRCODE_INDEX_CORRUPTED),
1346 itid,
1349 htid,
1351 }
1352
1353 /*
1354 * Don't try to generate scankey using "negative infinity" item on
1355 * internal pages. They are always truncated to zero attributes.
1356 */
1358 {
1359 /*
1360 * We don't call bt_child_check() for "negative infinity" items.
1361 * But if we're performing downlink connectivity check, we do it
1362 * for every item including "negative infinity" one.
1363 */
1365 {
1367 offset,
1368 NULL,
1369 topaque->btpo_level);
1370 }
1371 continue;
1372 }
1373
1374 /*
1375 * Readonly callers may optionally verify that non-pivot tuples can
1376 * each be found by an independent search that starts from the root.
1377 * Note that we deliberately don't do individual searches for each
1378 * TID, since the posting list itself is validated by other checks.
1379 */
1382 {
1384 char *itid,
1385 *htid;
1386
1389 ItemPointerGetOffsetNumber(tid));
1390
1392 (errcode(ERRCODE_INDEX_CORRUPTED),
1396 itid, htid,
1398 }
1399
1400 /*
1401 * If tuple is a posting list tuple, make sure posting list TIDs are
1402 * in order
1403 */
1405 {
1406 ItemPointerData last;
1407 ItemPointer current;
1408
1410
1412 {
1413
1415
1417 {
1419
1421 (errcode(ERRCODE_INDEX_CORRUPTED),
1425 itid, i,
1427 }
1428
1429 ItemPointerCopy(current, &last);
1430 }
1431 }
1432
1433 /* Build insertion scankey for current page offset */
1435
1436 /*
1437 * Make sure tuple size does not exceed the relevant BTREE_VERSION
1438 * specific limit.
1439 *
1440 * BTREE_VERSION 4 (which introduced heapkeyspace rules) requisitioned
1441 * a small amount of space from BTMaxItemSize() in order to ensure
1442 * that suffix truncation always has enough space to add an explicit
1443 * heap TID back to a tuple -- we pessimistically assume that every
1444 * newly inserted tuple will eventually need to have a heap TID
1445 * appended during a future leaf page split, when the tuple becomes
1446 * the basis of the new high key (pivot tuple) for the leaf page.
1447 *
1448 * Since the reclaimed space is reserved for that purpose, we must not
1449 * enforce the slightly lower limit when the extra space has been used
1450 * as intended. In other words, there is only a cross-version
1451 * difference in the limit on tuple size within leaf pages.
1452 *
1453 * Still, we're particular about the details within BTREE_VERSION 4
1454 * internal pages. Pivot tuples may only use the extra space for its
1455 * designated purpose. Enforce the lower limit for pivot tuples when
1456 * an explicit heap TID isn't actually present. (In all other cases
1457 * suffix truncation is guaranteed to generate a pivot tuple that's no
1458 * larger than the firstright tuple provided to it by its caller.)
1459 */
1460 lowersizelimit = skey->heapkeyspace &&
1463 {
1465 char *itid,
1466 *htid;
1467
1470 ItemPointerGetBlockNumberNoCheck(tid),
1471 ItemPointerGetOffsetNumberNoCheck(tid));
1472
1474 (errcode(ERRCODE_INDEX_CORRUPTED),
1478 itid,
1480 htid,
1482 }
1483
1484 /* Fingerprint leaf page tuples (those that point to the heap) */
1486 {
1487 IndexTuple norm;
1488
1490 {
1491 /* Fingerprint all elements as distinct "plain" tuples */
1493 {
1494 IndexTuple logtuple;
1495
1499 IndexTupleSize(norm));
1500 /* Be tidy */
1501 if (norm != logtuple)
1502 pfree(norm);
1503 pfree(logtuple);
1504 }
1505 }
1506 else
1507 {
1510 IndexTupleSize(norm));
1511 /* Be tidy */
1512 if (norm != itup)
1513 pfree(norm);
1514 }
1515 }
1516
1517 /*
1518 * * High key check *
1519 *
1520 * If there is a high key (if this is not the rightmost page on its
1521 * entire level), check that high key actually is upper bound on all
1522 * page items. If this is a posting list tuple, we'll need to set
1523 * scantid to be highest TID in posting list.
1524 *
1525 * We prefer to check all items against high key rather than checking
1526 * just the last and trusting that the operator class obeys the
1527 * transitive law (which implies that all previous items also
1528 * respected the high key invariant if they pass the item order
1529 * check).
1530 *
1531 * Ideally, we'd compare every item in the index against every other
1532 * item in the index, and not trust opclass obedience of the
1533 * transitive law to bridge the gap between children and their
1534 * grandparents (as well as great-grandparents, and so on). We don't
1535 * go to those lengths because that would be prohibitively expensive,
1536 * and probably not markedly more effective in practice.
1537 *
1538 * On the leaf level, we check that the key is <= the highkey.
1539 * However, on non-leaf levels we check that the key is < the highkey,
1540 * because the high key is "just another separator" rather than a copy
1541 * of some existing key item; we expect it to be unique among all keys
1542 * on the same level. (Suffix truncation will sometimes produce a
1543 * leaf highkey that is an untruncated copy of the lastleft item, but
1544 * never any other item, which necessitates weakening the leaf level
1545 * check to <=.)
1546 *
1547 * Full explanation for why a highkey is never truly a copy of another
1548 * item from the same level on internal levels:
1549 *
1550 * While the new left page's high key is copied from the first offset
1551 * on the right page during an internal page split, that's not the
1552 * full story. In effect, internal pages are split in the middle of
1553 * the firstright tuple, not between the would-be lastleft and
1554 * firstright tuples: the firstright key ends up on the left side as
1555 * left's new highkey, and the firstright downlink ends up on the
1556 * right side as right's new "negative infinity" item. The negative
1557 * infinity tuple is truncated to zero attributes, so we're only left
1558 * with the downlink. In other words, the copying is just an
1559 * implementation detail of splitting in the middle of a (pivot)
1560 * tuple. (See also: "Notes About Data Representation" in the nbtree
1561 * README.)
1562 */
1563 scantid = skey->scantid;
1566
1570 {
1572 char *itid,
1573 *htid;
1574
1577 ItemPointerGetBlockNumberNoCheck(tid),
1578 ItemPointerGetOffsetNumberNoCheck(tid));
1579
1581 (errcode(ERRCODE_INDEX_CORRUPTED),
1585 itid,
1587 htid,
1589 }
1590 /* Reset, in case scantid was set to (itup) posting tuple's max TID */
1591 skey->scantid = scantid;
1592
1593 /*
1594 * * Item order check *
1595 *
1596 * Check that items are stored on page in logical order, by checking
1597 * current item is strictly less than next item (if any).
1598 */
1601 {
1602 ItemPointer tid;
1603 char *itid,
1604 *htid,
1605 *nitid,
1606 *nhtid;
1607
1609 tid = BTreeTupleGetPointsToTID(itup);
1611 ItemPointerGetBlockNumberNoCheck(tid),
1612 ItemPointerGetOffsetNumberNoCheck(tid));
1614 OffsetNumberNext(offset));
1615
1616 /* Reuse itup to get pointed-to heap location of second item */
1618 state->target,
1619 OffsetNumberNext(offset));
1621 tid = BTreeTupleGetPointsToTID(itup);
1623 ItemPointerGetBlockNumberNoCheck(tid),
1624 ItemPointerGetOffsetNumberNoCheck(tid));
1625
1627 (errcode(ERRCODE_INDEX_CORRUPTED),
1630 errdetail_internal("Lower index tid=%s (points to %s tid=%s) higher index tid=%s (points to %s tid=%s) page lsn=%X/%08X.",
1631 itid,
1633 htid,
1634 nitid,
1636 nhtid,
1638 }
1639
1640 /*
1641 * If the index is unique verify entries uniqueness by checking the
1642 * heap tuples visibility. Immediately check posting tuples and
1643 * tuples with repeated keys. Postpone check for keys, which have the
1644 * first appearance.
1645 */
1649 {
1651 &lVis);
1652 unique_checked = true;
1653 }
1654
1657 {
1658 /* Save current scankey tid */
1659 scantid = skey->scantid;
1660
1661 /*
1662 * Invalidate scankey tid to make _bt_compare compare only keys in
1663 * the item to report equality even if heap TIDs are different
1664 */
1665 skey->scantid = NULL;
1666
1667 /*
1668 * If next key tuple is different, invalidate last visible entry
1669 * data (whole index tuple or last posting in index tuple). Key
1670 * containing null value does not violate unique constraint and
1671 * treated as different to any other key.
1672 *
1673 * If the next key is the same as the previous one, do the
1674 * bt_entry_unique_check() call if it was postponed.
1675 */
1678 {
1681 lVis.postingIndex = -1;
1682 lVis.tid = NULL;
1683 }
1684 else if (!unique_checked)
1685 {
1687 &lVis);
1688 }
1690 }
1691
1692 /*
1693 * * Last item check *
1694 *
1695 * Check last item against next/right page's first data item's when
1696 * last item on page is reached. This additional check will detect
1697 * transposed pages iff the supposed right sibling page happens to
1698 * belong before target in the key space. (Otherwise, a subsequent
1699 * heap verification will probably detect the problem.)
1700 *
1701 * This check is similar to the item order check that will have
1702 * already been performed for every other "real" item on target page
1703 * when last item is checked. The difference is that the next item
1704 * (the item that is compared to target's last item) needs to come
1705 * from the next/sibling page. There may not be such an item
1706 * available from sibling for various reasons, though (e.g., target is
1707 * the rightmost page on level).
1708 */
1709 if (offset == max)
1710 {
1711 BTScanInsert rightkey;
1712
1713 /* first offset on a right index page (log only) */
1715
1716 /* Get item in next/right page */
1718
1719 if (rightkey &&
1721 {
1722 /*
1723 * As explained at length in bt_right_page_check_scankey(),
1724 * there is a known !readonly race that could account for
1725 * apparent violation of invariant, which we must check for
1726 * before actually proceeding with raising error. Our canary
1727 * condition is that target page was deleted.
1728 */
1730 {
1731 /* Get fresh copy of target page */
1733 /* Note that we deliberately do not update target LSN */
1735
1736 /*
1737 * All !readonly checks now performed; just return
1738 */
1740 return;
1741 }
1742
1744 (errcode(ERRCODE_INDEX_CORRUPTED),
1748 state->targetblock, offset,
1750 }
1751
1752 /*
1753 * If index has unique constraint make sure that no more than one
1754 * found equal items is visible.
1755 */
1758 {
1760
1762
1763 /*
1764 * Make _bt_compare compare only index keys without heap TIDs.
1765 * rightkey->scantid is modified destructively but it is ok
1766 * for it is not used later.
1767 */
1768 rightkey->scantid = NULL;
1769
1770 /* The first key on the next page is the same */
1772 !rightkey->anynullkeys)
1773 {
1774 Page rightpage;
1775
1776 /*
1777 * Do the bt_entry_unique_check() call if it was
1778 * postponed.
1779 */
1780 if (!unique_checked)
1782 offset, &lVis);
1783
1786 rightblock_number);
1787 topaque = BTPageGetOpaque(rightpage);
1788
1790 {
1791 pfree(rightpage);
1792 break;
1793 }
1794
1797 (errcode(ERRCODE_INDEX_CORRUPTED),
1801 state->targetblock,
1803
1805 rightpage,
1806 rightfirstoffset);
1808
1810
1811 pfree(rightpage);
1812 }
1813 }
1814 }
1815
1816 /*
1817 * * Downlink check *
1818 *
1819 * Additional check of child items iff this is an internal page and
1820 * caller holds a ShareLock. This happens for every downlink (item)
1821 * in target excluding the negative-infinity downlink (again, this is
1822 * because it has no useful value to compare).
1823 */
1826 }
1827
1828 /*
1829 * Special case bt_child_highkey_check() call
1830 *
1831 * We don't pass a real downlink, but we've to finish the level
1832 * processing. If condition is satisfied, we've already processed all the
1833 * downlinks from the target level. But there still might be pages to the
1834 * right of the child page pointer to by our rightmost downlink. And they
1835 * might have missing downlinks. This final call checks for them.
1836 */
1838 {
1840 NULL, topaque->btpo_level);
1841 }
1842}
void bloom_add_element(bloom_filter *filter, unsigned char *elem, size_t len)
Definition: bloomfilter.c:135
int32 ItemPointerCompare(const ItemPointerData *arg1, const ItemPointerData *arg2)
Definition: itemptr.c:51
static void ItemPointerCopy(const ItemPointerData *fromPointer, ItemPointerData *toPointer)
Definition: itemptr.h:172
static ItemPointer BTreeTupleGetMaxHeapTID(IndexTuple itup)
Definition: nbtree.h:665
bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
Definition: nbtutils.c:4149
Definition: verify_nbtree.c:155
static bool invariant_l_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber upperbound)
Definition: verify_nbtree.c:3106
static ItemPointer BTreeTupleGetPointsToTID(IndexTuple itup)
Definition: verify_nbtree.c:3578
static IndexTuple bt_posting_plain_tuple(IndexTuple itup, int n)
Definition: verify_nbtree.c:2974
static bool invariant_leq_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber upperbound)
Definition: verify_nbtree.c:3169
static bool bt_rootdescend(BtreeCheckState *state, IndexTuple itup)
Definition: verify_nbtree.c:3007
static BTScanInsert bt_right_page_check_scankey(BtreeCheckState *state, OffsetNumber *rightfirstoffset)
Definition: verify_nbtree.c:1863
static bool invariant_g_offset(BtreeCheckState *state, BTScanInsert key, OffsetNumber lowerbound)
Definition: verify_nbtree.c:3192
static IndexTuple bt_normalize_tuple(BtreeCheckState *state, IndexTuple itup)
Definition: verify_nbtree.c:2846
static void bt_child_check(BtreeCheckState *state, BTScanInsert targetkey, OffsetNumber downlinkoffnum)
Definition: verify_nbtree.c:2390
static void bt_entry_unique_check(BtreeCheckState *state, IndexTuple itup, BlockNumber targetblock, OffsetNumber offset, BtreeLastVisibleEntry *lVis)
Definition: verify_nbtree.c:909
References _bt_check_natts(), _bt_compare(), BTScanInsertData::anynullkeys, BtreeLastVisibleEntry::blkno, bloom_add_element(), bt_child_check(), bt_child_highkey_check(), bt_entry_unique_check(), bt_mkscankey_pivotsearch(), bt_normalize_tuple(), bt_posting_plain_tuple(), bt_right_page_check_scankey(), bt_rootdescend(), BTMaxItemSize, BTMaxItemSizeNoHeapTid, BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNAtts, BTreeTupleGetNPosting(), BTreeTupleGetPointsToTID(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), CHECK_FOR_INTERRUPTS, DEBUG2, elog, ereport, errcode(), errdetail_internal(), errhint(), errmsg(), errmsg_internal(), ERROR, BTScanInsertData::heapkeyspace, i, IndexTupleSize(), InvalidBlockNumber, InvalidOffsetNumber, invariant_g_offset(), invariant_l_offset(), invariant_leq_offset(), ItemIdGetLength, ItemIdIsDead, ItemPointerCompare(), ItemPointerCopy(), ItemPointerGetBlockNumber(), ItemPointerGetBlockNumberNoCheck(), ItemPointerGetOffsetNumber(), ItemPointerGetOffsetNumberNoCheck(), ItemPointerIsValid(), LSN_FORMAT_ARGS, BtreeLastVisibleEntry::offset, offset_is_negative_infinity(), OffsetNumberNext, P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetItem(), PageGetItemIdCareful(), PageGetMaxOffsetNumber(), palloc_btree_page(), pfree(), BtreeLastVisibleEntry::postingIndex, psprintf(), RelationGetRelationName, BTScanInsertData::scantid, BtreeLastVisibleEntry::tid, and unlikely.
Referenced by bt_check_level_from_leftmost().
◆ bt_tuple_present_callback()
|
static |
Definition at line 2778 of file verify_nbtree.c.
2780{
2782 IndexTuple itup,
2783 norm;
2784
2786
2787 /* Generate a normalized index tuple for fingerprinting */
2789 itup->t_tid = *tid;
2791
2792 /* Probe Bloom filter -- tuple should be present */
2794 IndexTupleSize(norm)))
2802 !state->readonly
2803 ? errhint("Retrying verification using the function bt_index_parent_check() might provide a more specific error.")
2804 : 0));
2805
2806 state->heaptuplespresent++;
2807 pfree(itup);
2808 /* Cannot leak memory here */
2809 if (norm != itup)
2810 pfree(norm);
2811}
bool bloom_lacks_element(bloom_filter *filter, unsigned char *elem, size_t len)
Definition: bloomfilter.c:157
References Assert(), bloom_lacks_element(), bt_normalize_tuple(), ereport, errcode(), ERRCODE_DATA_CORRUPTED, errhint(), errmsg(), ERROR, index_form_tuple(), IndexTupleSize(), ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), pfree(), RelationGetDescr, RelationGetRelationName, IndexTupleData::t_tid, and values.
Referenced by bt_check_every_level().
◆ BTreeTupleGetHeapTIDCareful()
|
inlinestatic |
Definition at line 3530 of file verify_nbtree.c.
3532{
3533 ItemPointer htid;
3534
3535 /*
3536 * Caller determines whether this is supposed to be a pivot or non-pivot
3537 * tuple using page type and item offset number. Verify that tuple
3538 * metadata agrees with this.
3539 */
3543 (errcode(ERRCODE_INDEX_CORRUPTED),
3544 errmsg_internal("block %u or its right sibling block or child block in index \"%s\" has unexpected pivot tuple",
3545 state->targetblock,
3547
3550 (errcode(ERRCODE_INDEX_CORRUPTED),
3551 errmsg_internal("block %u or its right sibling block or child block in index \"%s\" has unexpected non-pivot tuple",
3552 state->targetblock,
3554
3555 htid = BTreeTupleGetHeapTID(itup);
3558 (errcode(ERRCODE_INDEX_CORRUPTED),
3559 errmsg("block %u or its right sibling block or child block in index \"%s\" contains non-pivot tuple that lacks a heap TID",
3560 state->targetblock,
3562
3563 return htid;
3564}
References Assert(), BTreeTupleGetHeapTID(), BTreeTupleIsPivot(), ereport, errcode(), errmsg(), errmsg_internal(), ERROR, ItemPointerIsValid(), and RelationGetRelationName.
Referenced by invariant_l_nontarget_offset(), and invariant_l_offset().
◆ BTreeTupleGetPointsToTID()
|
inlinestatic |
Definition at line 3578 of file verify_nbtree.c.
3579{
3580 /*
3581 * Rely on the assumption that !heapkeyspace internal page data items will
3582 * correctly return TID with downlink here -- BTreeTupleGetHeapTID() won't
3583 * recognize it as a pivot tuple, but everything still works out because
3584 * the t_tid field is still returned
3585 */
3588
3589 /* Pivot tuple returns TID with downlink block (heapkeyspace variant) */
3591}
References BTreeTupleGetHeapTID(), BTreeTupleIsPivot(), and IndexTupleData::t_tid.
Referenced by bt_target_page_check().
◆ heap_entry_is_visible()
|
static |
Definition at line 850 of file verify_nbtree.c.
851{
852 bool tid_visible;
853
855
857 tid, state->snapshot, slot);
858 if (slot != NULL)
859 ExecDropSingleTupleTableSlot(slot);
860
861 return tid_visible;
862}
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:1443
Definition: tuptable.h:114
TupleTableSlot * table_slot_create(Relation relation, List **reglist)
Definition: tableam.c:92
static bool table_tuple_fetch_row_version(Relation rel, ItemPointer tid, Snapshot snapshot, TupleTableSlot *slot)
Definition: tableam.h:1263
References ExecDropSingleTupleTableSlot(), table_slot_create(), and table_tuple_fetch_row_version().
Referenced by bt_entry_unique_check().
◆ invariant_g_offset()
|
inlinestatic |
Definition at line 3192 of file verify_nbtree.c.
3194{
3196
3198
3200
3201 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3204
3205 /*
3206 * No need to consider the possibility that scankey has attributes that we
3207 * need to force to be interpreted as negative infinity. _bt_compare() is
3208 * able to determine that scankey is greater than negative infinity. The
3209 * distinction between "==" and "<" isn't interesting here, since
3210 * corruption is indicated either way.
3211 */
3213}
References _bt_compare(), Assert(), cmp(), and sort-test::key.
Referenced by bt_target_page_check().
◆ invariant_l_nontarget_offset()
|
inlinestatic |
Definition at line 3228 of file verify_nbtree.c.
3231{
3232 ItemId itemid;
3234
3236
3237 /* Verify line pointer before checking tuple */
3239 upperbound);
3241
3242 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3245
3246 /* See invariant_l_offset() for an explanation of this extra step */
3248 {
3249 IndexTuple child;
3250 int uppnkeyatts;
3251 ItemPointer childheaptid;
3252 BTPageOpaque copaque;
3253 bool nonpivot;
3254
3256 copaque = BTPageGetOpaque(nontarget);
3258
3259 /* Get number of keys + heap TID for child/non-target item */
3262
3263 /* Heap TID is tiebreaker key attribute */
3266
3268 }
3269
3271}
static ItemPointer BTreeTupleGetHeapTIDCareful(BtreeCheckState *state, IndexTuple itup, bool nonpivot)
Definition: verify_nbtree.c:3530
References _bt_compare(), Assert(), BTPageGetOpaque, BTreeTupleGetHeapTIDCareful(), BTreeTupleGetNKeyAtts, cmp(), sort-test::key, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem(), and PageGetItemIdCareful().
Referenced by bt_child_check().
◆ invariant_l_offset()
|
inlinestatic |
Definition at line 3106 of file verify_nbtree.c.
3108{
3109 ItemId itemid;
3111
3113
3114 /* Verify line pointer before checking tuple */
3116 upperbound);
3117 /* pg_upgrade'd indexes may legally have equal sibling tuples */
3120
3122
3123 /*
3124 * _bt_compare() is capable of determining that a scankey with a
3125 * filled-out attribute is greater than pivot tuples where the comparison
3126 * is resolved at a truncated attribute (value of attribute in pivot is
3127 * minus infinity). However, it is not capable of determining that a
3128 * scankey is _less than_ a tuple on the basis of a comparison resolved at
3129 * _scankey_ minus infinity attribute. Complete an extra step to simulate
3130 * having minus infinity values for omitted scankey attribute(s).
3131 */
3133 {
3134 BTPageOpaque topaque;
3135 IndexTuple ritup;
3136 int uppnkeyatts;
3137 ItemPointer rheaptid;
3138 bool nonpivot;
3139
3143
3144 /* Get number of keys + heap TID for item to the right */
3147
3148 /* Heap TID is tiebreaker key attribute */
3151
3153 }
3154
3156}
References _bt_compare(), Assert(), BTPageGetOpaque, BTreeTupleGetHeapTIDCareful(), BTreeTupleGetNKeyAtts, cmp(), invariant_leq_offset(), sort-test::key, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem(), and PageGetItemIdCareful().
Referenced by bt_target_page_check().
◆ invariant_leq_offset()
|
inlinestatic |
Definition at line 3169 of file verify_nbtree.c.
3171{
3173
3175
3177
3179}
References _bt_compare(), Assert(), cmp(), and sort-test::key.
Referenced by bt_target_page_check(), and invariant_l_offset().
◆ offset_is_negative_infinity()
|
inlinestatic |
Definition at line 3071 of file verify_nbtree.c.
3072{
3073 /*
3074 * For internal pages only, the first item after high key, if any, is
3075 * negative infinity item. Internal pages always have a negative infinity
3076 * item, whereas leaf pages never have one. This implies that negative
3077 * infinity item is either first or second line item, or there is none
3078 * within page.
3079 *
3080 * Negative infinity items are a special case among pivot tuples. They
3081 * always have zero attributes, while all other pivot tuples always have
3082 * nkeyatts attributes.
3083 *
3084 * Right-most pages don't have a high key, but could be said to
3085 * conceptually have a "positive infinity" high key. Thus, there is a
3086 * symmetry between down link items in parent pages, and high keys in
3087 * children. Together, they represent the part of the key space that
3088 * belongs to each page in the index. For example, all children of the
3089 * root page will have negative infinity as a lower bound from root
3090 * negative infinity downlink, and positive infinity as an upper bound
3091 * (implicitly, from "imaginary" positive infinity high key in root).
3092 */
3094}
References P_FIRSTDATAKEY, and P_ISLEAF.
Referenced by bt_child_check(), bt_child_highkey_check(), and bt_target_page_check().
◆ PageGetItemIdCareful()
|
static |
Definition at line 3490 of file verify_nbtree.c.
3492{
3494
3498 (errcode(ERRCODE_INDEX_CORRUPTED),
3502 block, offset, ItemIdGetOffset(itemid),
3503 ItemIdGetLength(itemid),
3504 ItemIdGetFlags(itemid))));
3505
3506 /*
3507 * Verify that line pointer isn't LP_REDIRECT or LP_UNUSED, since nbtree
3508 * never uses either. Verify that line pointer has storage, too, since
3509 * even LP_DEAD items should within nbtree.
3510 */
3512 ItemIdGetLength(itemid) == 0)
3514 (errcode(ERRCODE_INDEX_CORRUPTED),
3518 block, offset, ItemIdGetOffset(itemid),
3519 ItemIdGetLength(itemid),
3520 ItemIdGetFlags(itemid))));
3521
3522 return itemid;
3523}
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:243
References ereport, errcode(), errdetail_internal(), errmsg(), ERROR, ItemIdGetFlags, ItemIdGetLength, ItemIdGetOffset, ItemIdIsRedirected, ItemIdIsUsed, MAXALIGN, PageGetItemId(), and RelationGetRelationName.
Referenced by bt_check_level_from_leftmost(), bt_child_check(), bt_child_highkey_check(), bt_downlink_missing_check(), bt_right_page_check_scankey(), bt_target_page_check(), invariant_l_nontarget_offset(), and invariant_l_offset().
◆ palloc_btree_page()
|
static |
Definition at line 3288 of file verify_nbtree.c.
3289{
3290 Buffer buffer;
3291 Page page;
3292 BTPageOpaque opaque;
3293 OffsetNumber maxoffset;
3294
3295 page = palloc(BLCKSZ);
3296
3297 /*
3298 * We copy the page into local storage to avoid holding pin on the buffer
3299 * longer than we must.
3300 */
3302 state->checkstrategy);
3304
3305 /*
3306 * Perform the same basic sanity checking that nbtree itself performs for
3307 * every page:
3308 */
3310
3311 /* Only use copy of page in palloc()'d memory */
3312 memcpy(page, BufferGetPage(buffer), BLCKSZ);
3313 UnlockReleaseBuffer(buffer);
3314
3315 opaque = BTPageGetOpaque(page);
3316
3319 (errcode(ERRCODE_INDEX_CORRUPTED),
3322
3323 /* Check page from block that ought to be meta page */
3325 {
3327
3331 (errcode(ERRCODE_INDEX_CORRUPTED),
3334
3338 (errcode(ERRCODE_INDEX_CORRUPTED),
3340 "current version %d, minimum supported version %d",
3343 BTREE_MIN_VERSION)));
3344
3345 /* Finished with metapage checks */
3346 return page;
3347 }
3348
3349 /*
3350 * Deleted pages that still use the old 32-bit XID representation have no
3351 * sane "level" field because they type pun the field, but all other pages
3352 * (including pages deleted on Postgres 14+) have a valid value.
3353 */
3355 {
3356 /* Okay, no reason not to trust btpo_level field from page */
3357
3360 (errcode(ERRCODE_INDEX_CORRUPTED),
3362 opaque->btpo_level, blocknum,
3364
3367 (errcode(ERRCODE_INDEX_CORRUPTED),
3369 blocknum,
3371 }
3372
3373 /*
3374 * Sanity checks for number of items on page.
3375 *
3376 * As noted at the beginning of _bt_binsrch(), an internal page must have
3377 * children, since there must always be a negative infinity downlink
3378 * (there may also be a highkey). In the case of non-rightmost leaf
3379 * pages, there must be at least a highkey. The exceptions are deleted
3380 * pages, which contain no items.
3381 *
3382 * This is correct when pages are half-dead, since internal pages are
3383 * never half-dead, and leaf pages must have a high key when half-dead
3384 * (the rightmost page can never be deleted). It's also correct with
3385 * fully deleted pages: _bt_unlink_halfdead_page() doesn't change anything
3386 * about the target page other than setting the page as fully dead, and
3387 * setting its xact field. In particular, it doesn't change the sibling
3388 * links in the deletion target itself, since they're required when index
3389 * scans land on the deletion target, and then need to move right (or need
3390 * to move left, in the case of backward index scans).
3391 */
3392 maxoffset = PageGetMaxOffsetNumber(page);
3395 (errcode(ERRCODE_INDEX_CORRUPTED),
3398 MaxIndexTuplesPerPage)));
3399
3402 (errcode(ERRCODE_INDEX_CORRUPTED),
3405
3408 (errcode(ERRCODE_INDEX_CORRUPTED),
3411
3412 /*
3413 * In general, internal pages are never marked half-dead, except on
3414 * versions of Postgres prior to 9.4, where it can be valid transient
3415 * state. This state is nonetheless treated as corruption by VACUUM on
3416 * from version 9.4 on, so do the same here. See _bt_pagedel() for full
3417 * details.
3418 */
3421 (errcode(ERRCODE_INDEX_CORRUPTED),
3424 errhint("This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));
3425
3426 /*
3427 * Check that internal pages have no garbage items, and that no page has
3428 * an invalid combination of deletion-related page level flags
3429 */
3432 (errcode(ERRCODE_INDEX_CORRUPTED),
3435
3438 (errcode(ERRCODE_INDEX_CORRUPTED),
3439 errmsg_internal("full transaction id page flag appears in non-deleted block %u in index \"%s\"",
3441
3444 (errcode(ERRCODE_INDEX_CORRUPTED),
3447
3448 return page;
3449}
References _bt_checkpage(), BT_READ, BTMetaPageData::btm_magic, BTMetaPageData::btm_version, BTPageGetMeta, BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTREE_MAGIC, BTREE_METAPAGE, BTREE_MIN_VERSION, BTREE_VERSION, BufferGetPage(), ereport, errcode(), errhint(), errmsg(), errmsg_internal(), ERROR, LockBuffer(), MAIN_FORKNUM, MaxIndexTuplesPerPage, P_FIRSTDATAKEY, P_HAS_FULLXID, P_HAS_GARBAGE, P_HIKEY, P_ISDELETED, P_ISHALFDEAD, P_ISLEAF, P_ISMETA, P_RIGHTMOST, PageGetMaxOffsetNumber(), palloc(), RBM_NORMAL, ReadBufferExtended(), RelationGetRelationName, and UnlockReleaseBuffer().
Referenced by bt_check_every_level(), bt_check_level_from_leftmost(), bt_child_check(), bt_child_highkey_check(), bt_downlink_missing_check(), bt_leftmost_ignoring_half_dead(), bt_right_page_check_scankey(), and bt_target_page_check().
◆ PG_FUNCTION_INFO_V1() [1/2]
| PG_FUNCTION_INFO_V1 | ( | bt_index_check | ) |
◆ PG_FUNCTION_INFO_V1() [2/2]
| PG_FUNCTION_INFO_V1 | ( | bt_index_parent_check | ) |
◆ PG_MODULE_MAGIC_EXT()
| PG_MODULE_MAGIC_EXT | ( | . | name = "amcheck", |
| . | version = PG_VERSION |
||
| ) |
