This repository has been archived by the owner on Dec 1, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 8
/
verify_nbtree.c
2016 lines (1828 loc) · 75.7 KB
/
verify_nbtree.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*-------------------------------------------------------------------------
*
* verify_nbtree.c
* Verifies the integrity of nbtree indexes based on invariants.
*
* For B-Tree indexes, verification includes checking that each page in the
* target index has items in logical order as reported by an insertion scankey
* (the insertion scankey sort-wise NULL semantics are needed for
* verification).
*
* When index-to-heap verification is requested, a Bloom filter is used to
* fingerprint all tuples in the target index, as the index is traversed to
* verify its structure. A heap scan later uses Bloom filter probes to verify
* that every visible heap tuple has a matching index tuple.
*
*
* Portions Copyright (c) 2016-2020, Peter Geoghegan
* Portions Copyright (c) 1996-2020, The PostgreSQL Global Development Group
* Portions Copyright (c) 1994, The Regents of the University of California
*
* IDENTIFICATION
* amcheck_next/verify_nbtree.c
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
#include "access/htup_details.h"
#include "access/nbtree.h"
#include "access/transam.h"
#include "bloomfilter.h"
#include "catalog/index.h"
#include "catalog/pg_am.h"
#include "commands/tablecmds.h"
#include "miscadmin.h"
#include "storage/lmgr.h"
#include "utils/memutils.h"
#include "utils/snapmgr.h"
PG_MODULE_MAGIC;
/*
* A B-Tree cannot possibly have this many levels, since there must be one
* block per level, which is bound by the range of BlockNumber:
*/
#define InvalidBtreeLevel ((uint32) InvalidBlockNumber)
/*
* State associated with verifying a B-Tree index
*
* target is the point of reference for a verification operation.
*
* Other B-Tree pages may be allocated, but those are always auxiliary (e.g.,
* they are current target's child pages). Conceptually, problems are only
* ever found in the current target page (or for a particular heap tuple during
* heapallindexed verification). Each page found by verification's left/right,
* top/bottom scan becomes the target exactly once.
*/
typedef struct BtreeCheckState
{
/*
* Unchanging state, established at start of verification:
*/
/* B-Tree Index Relation and associated heap relation */
Relation rel;
Relation heaprel;
/* ShareLock held on heap/index, rather than AccessShareLock? */
bool readonly;
/* Also verifying heap has no unindexed tuples? */
bool heapallindexed;
/* Per-page context */
MemoryContext targetcontext;
/* Buffer access strategy */
BufferAccessStrategy checkstrategy;
/*
* Mutable state, for verification of particular page:
*/
/* Current target page */
Page target;
/* Target block number */
BlockNumber targetblock;
/* Target page's LSN */
XLogRecPtr targetlsn;
/*
* Mutable state, for optional heapallindexed verification:
*/
/* Bloom filter fingerprints B-Tree index */
bloom_filter *filter;
/* Bloom filter fingerprints downlink blocks within tree */
bloom_filter *downlinkfilter;
/* Right half of incomplete split marker */
bool rightsplit;
/* Debug counter */
int64 heaptuplespresent;
} BtreeCheckState;
/*
* Starting point for verifying an entire B-Tree index level
*/
typedef struct BtreeLevel
{
/* Level number (0 is leaf page level). */
uint32 level;
/* Left most block on level. Scan of level begins here. */
BlockNumber leftmost;
/* Is this level reported as "true" root level by meta page? */
bool istruerootlevel;
} BtreeLevel;
PG_FUNCTION_INFO_V1(bt_index_check_next);
PG_FUNCTION_INFO_V1(bt_index_parent_check_next);
static void bt_index_check_internal(Oid indrelid, bool parentcheck,
bool heapallindexed);
static inline void btree_index_checkable(Relation rel);
static void bt_check_every_level(Relation rel, Relation heaprel,
bool readonly, bool heapallindexed);
static BtreeLevel bt_check_level_from_leftmost(BtreeCheckState *state,
BtreeLevel level);
static void bt_target_page_check(BtreeCheckState *state);
static ScanKey bt_right_page_check_scankey(BtreeCheckState *state);
static void bt_downlink_check(BtreeCheckState *state, BlockNumber childblock,
ScanKey targetkey);
static void bt_downlink_missing_check(BtreeCheckState *state);
static void bt_tuple_present_callback(Relation index, HeapTuple htup,
Datum *values, bool *isnull,
bool tupleIsAlive, void *checkstate);
static IndexTuple bt_normalize_tuple(BtreeCheckState *state,
IndexTuple itup);
static inline bool offset_is_negative_infinity(BTPageOpaque opaque,
OffsetNumber offset);
static inline bool invariant_leq_offset(BtreeCheckState *state,
ScanKey key,
OffsetNumber upperbound);
static inline bool invariant_geq_offset(BtreeCheckState *state,
ScanKey key,
OffsetNumber lowerbound);
static inline bool invariant_leq_nontarget_offset(BtreeCheckState *state,
Page other,
ScanKey key,
OffsetNumber upperbound);
static Page palloc_btree_page(BtreeCheckState *state, BlockNumber blocknum);
/*
* bt_index_check(index regclass, heapallindexed boolean)
*
* Note that the symbol name is appended with "_next", to avoid symbol clashes
* with contrib/amcheck.
*
* Verify integrity of B-Tree index.
*
* Acquires AccessShareLock on heap & index relations. Does not consider
* invariants that exist between parent/child pages. Optionally verifies
* that heap does not contain any unindexed or incorrectly indexed tuples.
*/
Datum
bt_index_check_next(PG_FUNCTION_ARGS)
{
Oid indrelid = PG_GETARG_OID(0);
bool heapallindexed = false;
if (PG_NARGS() == 2)
heapallindexed = PG_GETARG_BOOL(1);
bt_index_check_internal(indrelid, false, heapallindexed);
PG_RETURN_VOID();
}
/*
* bt_index_parent_check(index regclass, heapallindexed boolean)
*
* Note that the symbol name is appended with "_next", to avoid symbol clashes
* with contrib/amcheck.
*
* Verify integrity of B-Tree index.
*
* Acquires ShareLock on heap & index relations. Verifies that downlinks in
* parent pages are valid lower bounds on child pages. Optionally verifies
* that heap does not contain any unindexed or incorrectly indexed tuples.
*/
Datum
bt_index_parent_check_next(PG_FUNCTION_ARGS)
{
Oid indrelid = PG_GETARG_OID(0);
bool heapallindexed = false;
if (PG_NARGS() == 2)
heapallindexed = PG_GETARG_BOOL(1);
bt_index_check_internal(indrelid, true, heapallindexed);
PG_RETURN_VOID();
}
/*
* Helper for bt_index_[parent_]check, coordinating the bulk of the work.
*/
static void
bt_index_check_internal(Oid indrelid, bool parentcheck, bool heapallindexed)
{
Oid heapid;
Relation indrel;
Relation heaprel;
LOCKMODE lockmode;
if (parentcheck)
lockmode = ShareLock;
else
lockmode = AccessShareLock;
/*
* We must lock table before index to avoid deadlocks. However, if the
* passed indrelid isn't an index then IndexGetRelation() will fail.
* Rather than emitting a not-very-helpful error message, postpone
* complaining, expecting that the is-it-an-index test below will fail.
*
* In hot standby mode this will raise an error when parentcheck is true.
*/
heapid = IndexGetRelation(indrelid, true);
if (OidIsValid(heapid))
heaprel = heap_open(heapid, lockmode);
else
heaprel = NULL;
/*
* Open the target index relations separately (like relation_openrv(), but
* with heap relation locked first to prevent deadlocking). In hot
* standby mode this will raise an error when parentcheck is true.
*
* There is no need for the usual indcheckxmin usability horizon test here,
* even in the heapallindexed case, because index undergoing verification
* only needs to have entries for a new transaction snapshot, which is a
* behavior we're able to approximate. (If this is a parentcheck
* verification, there is no question about committed or recently dead heap
* tuples lacking index entries due to concurrent activity.)
*/
indrel = index_open(indrelid, lockmode);
/*
* Since we did the IndexGetRelation call above without any lock, it's
* barely possible that a race against an index drop/recreation could have
* netted us the wrong table.
*/
if (heaprel == NULL || heapid != IndexGetRelation(indrelid, false))
ereport(ERROR,
(errcode(ERRCODE_UNDEFINED_TABLE),
errmsg("could not open parent table of index %s",
RelationGetRelationName(indrel))));
/* Relation suitable for checking as B-Tree? */
btree_index_checkable(indrel);
/* Check index, possibly against table it is an index on */
bt_check_every_level(indrel, heaprel, parentcheck, heapallindexed);
/*
* Release locks early. That's ok here because nothing in the called
* routines will trigger shared cache invalidations to be sent, so we can
* relax the usual pattern of only releasing locks after commit.
*/
index_close(indrel, lockmode);
if (heaprel)
heap_close(heaprel, lockmode);
}
/*
* Basic checks about the suitability of a relation for checking as a B-Tree
* index.
*
* NB: Intentionally not checking permissions, the function is normally not
* callable by non-superusers. If granted, it's useful to be able to check a
* whole cluster.
*/
static inline void
btree_index_checkable(Relation rel)
{
if (rel->rd_rel->relkind != RELKIND_INDEX ||
rel->rd_rel->relam != BTREE_AM_OID)
ereport(ERROR,
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
errmsg("only B-Tree indexes are supported as targets for verification"),
errdetail("Relation \"%s\" is not a B-Tree index.",
RelationGetRelationName(rel))));
if (RELATION_IS_OTHER_TEMP(rel))
ereport(ERROR,
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
errmsg("cannot access temporary tables of other sessions"),
errdetail("Index \"%s\" is associated with temporary relation.",
RelationGetRelationName(rel))));
if (!IndexIsValid(rel->rd_index))
ereport(ERROR,
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
errmsg("cannot check index \"%s\"",
RelationGetRelationName(rel)),
errdetail("Index is not valid.")));
}
/*
* Main entry point for B-Tree SQL-callable functions. Walks the B-Tree in
* logical order, verifying invariants as it goes. Optionally, verification
* checks if the heap relation contains any tuples that are not represented in
* the index but should be.
*
* It is the caller's responsibility to acquire appropriate heavyweight lock on
* the index relation, and advise us if extra checks are safe when a ShareLock
* is held. (A lock of the same type must also have been acquired on the heap
* relation.)
*
* A ShareLock is generally assumed to prevent any kind of physical
* modification to the index structure, including modifications that VACUUM may
* make. This does not include setting of the LP_DEAD bit by concurrent index
* scans, although that is just metadata that is not able to directly affect
* any check performed here. Any concurrent process that might act on the
* LP_DEAD bit being set (recycle space) requires a heavyweight lock that
* cannot be held while we hold a ShareLock. (Besides, even if that could
* happen, the ad-hoc recycling when a page might otherwise split is performed
* per-page, and requires an exclusive buffer lock, which wouldn't cause us
* trouble. _bt_delitems_vacuum() may only delete leaf items, and so the extra
* parent/child check cannot be affected.)
*/
static void
bt_check_every_level(Relation rel, Relation heaprel, bool readonly,
bool heapallindexed)
{
BtreeCheckState *state;
Page metapage;
BTMetaPageData *metad;
uint32 previouslevel;
BtreeLevel current;
/*
* RecentGlobalXmin assertion matches index_getnext_tid(). See note on
* RecentGlobalXmin/B-Tree page deletion.
*
* We also rely on TransactionXmin having been initialized by now.
*/
Assert(TransactionIdIsValid(RecentGlobalXmin));
Assert(TransactionIdIsNormal(TransactionXmin));
/*
* Initialize state for entire verification operation
*/
state = palloc0(sizeof(BtreeCheckState));
state->rel = rel;
state->heaprel = heaprel;
state->readonly = readonly;
state->heapallindexed = heapallindexed;
if (state->heapallindexed)
{
int64 total_elems;
uint64 seed;
/* Size Bloom filter based on estimated number of tuples in index */
total_elems = (int64) state->rel->rd_rel->reltuples;
/* Random seed relies on backend srandom() call to avoid repetition */
seed = random();
/* Create Bloom filter to fingerprint index */
state->filter = bloom_create(total_elems, maintenance_work_mem, seed);
state->heaptuplespresent = 0;
if (!state->readonly)
{
/*
* contrib/amcheck from PostgreSQL 11 must defend against the
* possibility that an old xact snapshot was returned at higher
* isolation levels when that snapshot is not safe for index scans
* of the target index. This is possible with that version when
* the snapshot sees tuples that are before the index's
* indcheckxmin horizon.
*
* We don't do the same IsolationUsesXactSnapshot() test here, as
* we don't even have a snapshot to test at this point. This is
* correct because we're already using TransactionXmin to simulate
* using a snapshot acquired at the beginning of our xact, so the
* isolation level cannot change the number of tuples that are
* verrified as having index entries through fingerprinting. See
* bt_tuple_present_callback() for full details.
*/
}
else
{
int64 total_pages;
/*
* Extra readonly downlink check.
*
* In readonly case, we know that there cannot be a concurrent page
* split or a concurrent page deletion, which gives us the
* opportunity to verify that every non-ignorable page had a
* downlink one level up. We must be tolerant of interrupted page
* splits and page deletions, though. This is taken care of in
* bt_downlink_missing_check().
*/
total_pages = (int64) state->rel->rd_rel->relpages;
state->downlinkfilter = bloom_create(total_pages, work_mem, seed);
}
}
/* Create context for page */
state->targetcontext = AllocSetContextCreate(CurrentMemoryContext,
"amcheck context",
#if PG_VERSION_NUM >= 110000
ALLOCSET_DEFAULT_SIZES);
#else
ALLOCSET_DEFAULT_MINSIZE,
ALLOCSET_DEFAULT_INITSIZE,
ALLOCSET_DEFAULT_MAXSIZE);
#endif
state->checkstrategy = GetAccessStrategy(BAS_BULKREAD);
/* Get true root block from meta-page */
metapage = palloc_btree_page(state, BTREE_METAPAGE);
metad = BTPageGetMeta(metapage);
/*
* Certain deletion patterns can result in "skinny" B-Tree indexes, where
* the fast root and true root differ.
*
* Start from the true root, not the fast root, unlike conventional index
* scans. This approach is more thorough, and removes the risk of
* following a stale fast root from the meta page.
*/
if (metad->btm_fastroot != metad->btm_root)
ereport(DEBUG1,
(errcode(ERRCODE_NO_DATA),
errmsg("harmless fast root mismatch in index %s",
RelationGetRelationName(rel)),
errdetail_internal("Fast root block %u (level %u) differs from true root block %u (level %u).",
metad->btm_fastroot, metad->btm_fastlevel,
metad->btm_root, metad->btm_level)));
/*
* Starting at the root, verify every level. Move left to right, top to
* bottom. Note that there may be no pages other than the meta page (meta
* page can indicate that root is P_NONE when the index is totally empty).
*/
previouslevel = InvalidBtreeLevel;
current.level = metad->btm_level;
current.leftmost = metad->btm_root;
current.istruerootlevel = true;
while (current.leftmost != P_NONE)
{
/*
* Leftmost page on level cannot be right half of incomplete split.
* This can go stale immediately in !readonly case.
*/
state->rightsplit = false;
/*
* Verify this level, and get left most page for next level down, if
* not at leaf level
*/
current = bt_check_level_from_leftmost(state, current);
if (current.leftmost == InvalidBlockNumber)
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("index \"%s\" has no valid pages on level below %u or first level",
RelationGetRelationName(rel), previouslevel)));
previouslevel = current.level;
}
/*
* * Check whether heap contains unindexed/malformed tuples *
*/
if (state->heapallindexed)
{
IndexInfo *indexinfo = BuildIndexInfo(state->rel);
/* Report on extra downlink checks performed in readonly case */
if (state->readonly)
{
ereport(DEBUG1,
(errmsg_internal("finished verifying presence of downlink blocks within index \"%s\" with bitset %.2f%% set",
RelationGetRelationName(rel),
100.0 * bloom_prop_bits_set(state->downlinkfilter))));
bloom_free(state->downlinkfilter);
}
/*
* Scan will behave as the first scan of a CREATE INDEX CONCURRENTLY
* behaves in !readonly case.
*
* It's okay that we don't actually use the same lock strength for the
* heap relation as any other ii_Concurrent caller would in !readonly
* case. We have no reason to care about a concurrent VACUUM
* operation, since there isn't going to be a second scan of the heap
* that needs to be sure that there was no concurrent recycling of
* TIDs.
*/
indexinfo->ii_Concurrent = !state->readonly;
/*
* Don't wait for uncommitted tuple xact commit/abort when index is a
* unique index on a catalog (or an index used by an exclusion
* constraint). This could otherwise happen in the readonly case.
*/
indexinfo->ii_Unique = false;
indexinfo->ii_ExclusionOps = NULL;
indexinfo->ii_ExclusionProcs = NULL;
indexinfo->ii_ExclusionStrats = NULL;
elog(DEBUG1, "verifying that tuples from index \"%s\" are present in \"%s\"",
RelationGetRelationName(state->rel),
RelationGetRelationName(state->heaprel));
IndexBuildHeapScan(state->heaprel, state->rel, indexinfo, true,
#if PG_VERSION_NUM >= 110000
bt_tuple_present_callback, (void *) state, NULL);
#else
bt_tuple_present_callback, (void *) state);
#endif
ereport(DEBUG1,
(errmsg_internal("finished verifying presence of " INT64_FORMAT " tuples from table \"%s\" with bitset %.2f%% set",
state->heaptuplespresent, RelationGetRelationName(heaprel),
100.0 * bloom_prop_bits_set(state->filter))));
bloom_free(state->filter);
}
/* Be tidy: */
MemoryContextDelete(state->targetcontext);
}
/*
* Given a left-most block at some level, move right, verifying each page
* individually (with more verification across pages for "readonly"
* callers). Caller should pass the true root page as the leftmost initially,
* working their way down by passing what is returned for the last call here
* until level 0 (leaf page level) was reached.
*
* Returns state for next call, if any. This includes left-most block number
* one level lower that should be passed on next level/call, which is set to
* P_NONE on last call here (when leaf level is verified). Level numbers
* follow the nbtree convention: higher levels have higher numbers, because new
* levels are added only due to a root page split. Note that prior to the
* first root page split, the root is also a leaf page, so there is always a
* level 0 (leaf level), and it's always the last level processed.
*
* Note on memory management: State's per-page context is reset here, between
* each call to bt_target_page_check().
*/
static BtreeLevel
bt_check_level_from_leftmost(BtreeCheckState *state, BtreeLevel level)
{
/* State to establish early, concerning entire level */
BTPageOpaque opaque;
MemoryContext oldcontext;
BtreeLevel nextleveldown;
/* Variables for iterating across level using right links */
BlockNumber leftcurrent = P_NONE;
BlockNumber current = level.leftmost;
/* Initialize return state */
nextleveldown.leftmost = InvalidBlockNumber;
nextleveldown.level = InvalidBtreeLevel;
nextleveldown.istruerootlevel = false;
/* Use page-level context for duration of this call */
oldcontext = MemoryContextSwitchTo(state->targetcontext);
elog(DEBUG2, "verifying level %u%s", level.level,
level.istruerootlevel ?
" (true root level)" : level.level == 0 ? " (leaf level)" : "");
do
{
/* Don't rely on CHECK_FOR_INTERRUPTS() calls at lower level */
CHECK_FOR_INTERRUPTS();
/* Initialize state for this iteration */
state->targetblock = current;
state->target = palloc_btree_page(state, state->targetblock);
state->targetlsn = PageGetLSN(state->target);
opaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
if (P_IGNORE(opaque))
{
/*
* Since there cannot be a concurrent VACUUM operation in readonly
* mode, and since a page has no links within other pages (siblings
* and parent) once it is marked fully deleted, it should be
* impossible to land on a fully deleted page in readonly mode.
* See bt_downlink_check() for further details.
*
* The bt_downlink_check() P_ISDELETED() check is repeated here so
* that pages that are only reachable through sibling links get
* checked.
*/
if (state->readonly && P_ISDELETED(opaque))
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("downlink or sibling link points to deleted block in index \"%s\"",
RelationGetRelationName(state->rel)),
errdetail_internal("Block=%u left block=%u left link from block=%u.",
current, leftcurrent, opaque->btpo_prev)));
if (P_RIGHTMOST(opaque))
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("block %u fell off the end of index \"%s\"",
current, RelationGetRelationName(state->rel))));
else
ereport(DEBUG1,
(errcode(ERRCODE_NO_DATA),
errmsg("block %u of index \"%s\" ignored",
current, RelationGetRelationName(state->rel))));
goto nextpage;
}
else if (nextleveldown.leftmost == InvalidBlockNumber)
{
/*
* A concurrent page split could make the caller supplied leftmost
* block no longer contain the leftmost page, or no longer be the
* true root, but where that isn't possible due to heavyweight
* locking, check that the first valid page meets caller's
* expectations.
*/
if (state->readonly)
{
if (!P_LEFTMOST(opaque))
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("block %u is not leftmost in index \"%s\"",
current, RelationGetRelationName(state->rel))));
if (level.istruerootlevel && !P_ISROOT(opaque))
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("block %u is not true root in index \"%s\"",
current, RelationGetRelationName(state->rel))));
}
/*
* Before beginning any non-trivial examination of level, prepare
* state for next bt_check_level_from_leftmost() invocation for
* the next level for the next level down (if any).
*
* There should be at least one non-ignorable page per level,
* unless this is the leaf level, which is assumed by caller to be
* final level.
*/
if (!P_ISLEAF(opaque))
{
IndexTuple itup;
ItemId itemid;
/* Internal page -- downlink gets leftmost on next level */
itemid = PageGetItemId(state->target, P_FIRSTDATAKEY(opaque));
itup = (IndexTuple) PageGetItem(state->target, itemid);
nextleveldown.leftmost = ItemPointerGetBlockNumber(&(itup->t_tid));
nextleveldown.level = opaque->btpo.level - 1;
}
else
{
/*
* Leaf page -- final level caller must process.
*
* Note that this could also be the root page, if there has
* been no root page split yet.
*/
nextleveldown.leftmost = P_NONE;
nextleveldown.level = InvalidBtreeLevel;
}
/*
* Finished setting up state for this call/level. Control will
* never end up back here in any future loop iteration for this
* level.
*/
}
/*
* readonly mode can only ever land on live pages and half-dead pages,
* so sibling pointers should always be in mutual agreement
*/
if (state->readonly && opaque->btpo_prev != leftcurrent)
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("left link/right link pair in index \"%s\" not in agreement",
RelationGetRelationName(state->rel)),
errdetail_internal("Block=%u left block=%u left link from block=%u.",
current, leftcurrent, opaque->btpo_prev)));
/* Check level, which must be valid for non-ignorable page */
if (level.level != opaque->btpo.level)
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("leftmost down link for level points to block in index \"%s\" whose level is not one level down",
RelationGetRelationName(state->rel)),
errdetail_internal("Block pointed to=%u expected level=%u level in pointed to block=%u.",
current, level.level, opaque->btpo.level)));
/* Verify invariants for page */
bt_target_page_check(state);
nextpage:
/* Try to detect circular links */
if (current == leftcurrent || current == opaque->btpo_prev)
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("circular link chain found in block %u of index \"%s\"",
current, RelationGetRelationName(state->rel))));
/*
* Record if page that is about to become target is the right half of
* an incomplete page split. This can go stale immediately in
* !readonly case.
*/
state->rightsplit = P_INCOMPLETE_SPLIT(opaque);
leftcurrent = current;
current = opaque->btpo_next;
/* Free page and associated memory for this iteration */
MemoryContextReset(state->targetcontext);
}
while (current != P_NONE);
/* Don't change context for caller */
MemoryContextSwitchTo(oldcontext);
return nextleveldown;
}
/*
* Function performs the following checks on target page, or pages ancillary to
* target page:
*
* - That every "real" data item is less than or equal to the high key, which
* is an upper bound on the items on the pages (where there is a high key at
* all -- pages that are rightmost lack one).
*
* - That within the page, every "real" item is less than or equal to the item
* immediately to its right, if any (i.e., that the items are in order within
* the page, so that the binary searches performed by index scans are sane).
*
* - That the last item stored on the page is less than or equal to the first
* "real" data item on the page to the right (if such a first item is
* available).
*
* - That tuples report that they have the expected number of attributes.
* INCLUDE index pivot tuples should not contain non-key attributes.
*
* Furthermore, when state passed shows ShareLock held, function also checks:
*
* - That all child pages respect downlinks lower bound.
*
* - That downlink to block was encountered in parent where that's expected.
* (Limited to heapallindexed readonly callers.)
*
* This is also where heapallindexed callers use their Bloom filter to
* fingerprint IndexTuples for later IndexBuildHeapScan() verification.
*
* Note: Memory allocated in this routine is expected to be released by caller
* resetting state->targetcontext.
*/
static void
bt_target_page_check(BtreeCheckState *state)
{
OffsetNumber offset;
OffsetNumber max;
BTPageOpaque topaque;
topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
max = PageGetMaxOffsetNumber(state->target);
elog(DEBUG2, "verifying %u items on %s block %u", max,
P_ISLEAF(topaque) ? "leaf" : "internal", state->targetblock);
/*
* Loop over page items, starting from first non-highkey item, not high
* key (if any). Most tests are not performed for the "negative infinity"
* real item (if any).
*/
for (offset = P_FIRSTDATAKEY(topaque);
offset <= max;
offset = OffsetNumberNext(offset))
{
ItemId itemid;
IndexTuple itup;
ScanKey skey;
size_t tupsize;
CHECK_FOR_INTERRUPTS();
itemid = PageGetItemId(state->target, offset);
itup = (IndexTuple) PageGetItem(state->target, itemid);
tupsize = IndexTupleSize(itup);
/*
* lp_len should match the IndexTuple reported length exactly, since
* lp_len is completely redundant in indexes, and both sources of tuple
* length are MAXALIGN()'d. nbtree does not use lp_len all that
* frequently, and is surprisingly tolerant of corrupt lp_len fields.
*/
if (tupsize != ItemIdGetLength(itemid))
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("index tuple size does not equal lp_len in index \"%s\"",
RelationGetRelationName(state->rel)),
errdetail_internal("Index tid=(%u,%u) tuple size=%zu lp_len=%u page lsn=%X/%X.",
state->targetblock, offset,
tupsize, ItemIdGetLength(itemid),
(uint32) (state->targetlsn >> 32),
(uint32) state->targetlsn),
errhint("This could be a torn page problem.")));
/* Fingerprint downlink blocks in heapallindexed + readonly case */
if (state->heapallindexed && state->readonly && !P_ISLEAF(topaque))
{
BlockNumber childblock = ItemPointerGetBlockNumber(&itup->t_tid);
bloom_add_element(state->downlinkfilter,
(unsigned char *) &childblock,
sizeof(BlockNumber));
}
/*
* Don't try to generate scankey using "negative infinity" item on
* internal pages. They are always truncated to zero attributes.
*/
if (offset_is_negative_infinity(topaque, offset))
continue;
/* Build insertion scankey for current page offset */
skey = _bt_mkscankey(state->rel, itup);
/* Fingerprint leaf page tuples (those that point to the heap) */
if (state->heapallindexed && P_ISLEAF(topaque) && !ItemIdIsDead(itemid))
{
IndexTuple norm;
norm = bt_normalize_tuple(state, itup);
bloom_add_element(state->filter, (unsigned char *) norm,
IndexTupleSize(norm));
/* Be tidy */
if (norm != itup)
pfree(norm);
}
/*
* * High key check *
*
* If there is a high key (if this is not the rightmost page on its
* entire level), check that high key actually is upper bound on all
* page items.
*
* We prefer to check all items against high key rather than checking
* just the last and trusting that the operator class obeys the
* transitive law (which implies that all previous items also
* respected the high key invariant if they pass the item order
* check).
*
* Ideally, we'd compare every item in the index against every other
* item in the index, and not trust opclass obedience of the
* transitive law to bridge the gap between children and their
* grandparents (as well as great-grandparents, and so on). We don't
* go to those lengths because that would be prohibitively expensive,
* and probably not markedly more effective in practice.
*/
if (!P_RIGHTMOST(topaque) &&
!invariant_leq_offset(state, skey, P_HIKEY))
{
char *itid,
*htid;
itid = psprintf("(%u,%u)", state->targetblock, offset);
htid = psprintf("(%u,%u)",
ItemPointerGetBlockNumber(&(itup->t_tid)),
ItemPointerGetOffsetNumber(&(itup->t_tid)));
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("high key invariant violated for index \"%s\"",
RelationGetRelationName(state->rel)),
errdetail_internal("Index tid=%s points to %s tid=%s page lsn=%X/%X.",
itid,
P_ISLEAF(topaque) ? "heap" : "index",
htid,
(uint32) (state->targetlsn >> 32),
(uint32) state->targetlsn)));
}
/*
* * Item order check *
*
* Check that items are stored on page in logical order, by checking
* current item is less than or equal to next item (if any).
*/
if (OffsetNumberNext(offset) <= max &&
!invariant_leq_offset(state, skey,
OffsetNumberNext(offset)))
{
char *itid,
*htid,
*nitid,
*nhtid;
itid = psprintf("(%u,%u)", state->targetblock, offset);
htid = psprintf("(%u,%u)",
ItemPointerGetBlockNumber(&(itup->t_tid)),
ItemPointerGetOffsetNumber(&(itup->t_tid)));
nitid = psprintf("(%u,%u)", state->targetblock,
OffsetNumberNext(offset));
/* Reuse itup to get pointed-to heap location of second item */
itemid = PageGetItemId(state->target, OffsetNumberNext(offset));
itup = (IndexTuple) PageGetItem(state->target, itemid);
nhtid = psprintf("(%u,%u)",
ItemPointerGetBlockNumber(&(itup->t_tid)),
ItemPointerGetOffsetNumber(&(itup->t_tid)));
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("item order invariant violated for index \"%s\"",
RelationGetRelationName(state->rel)),
errdetail_internal("Lower index tid=%s (points to %s tid=%s) "
"higher index tid=%s (points to %s tid=%s) "
"page lsn=%X/%X.",
itid,
P_ISLEAF(topaque) ? "heap" : "index",
htid,
nitid,
P_ISLEAF(topaque) ? "heap" : "index",
nhtid,
(uint32) (state->targetlsn >> 32),
(uint32) state->targetlsn)));
}
/*
* * Last item check *
*
* Check last item against next/right page's first data item's when
* last item on page is reached. This additional check will detect
* transposed pages iff the supposed right sibling page happens to
* belong before target in the key space. (Otherwise, a subsequent
* heap verification will probably detect the problem.)
*
* This check is similar to the item order check that will have
* already been performed for every other "real" item on target page
* when last item is checked. The difference is that the next item
* (the item that is compared to target's last item) needs to come
* from the next/sibling page. There may not be such an item
* available from sibling for various reasons, though (e.g., target is
* the rightmost page on level).
*/
else if (offset == max)
{
ScanKey rightkey;
/* Get item in next/right page */
rightkey = bt_right_page_check_scankey(state);
if (rightkey &&
!invariant_geq_offset(state, rightkey, max))
{
/*
* As explained at length in bt_right_page_check_scankey(),
* there is a known !readonly race that could account for
* apparent violation of invariant, which we must check for
* before actually proceeding with raising error. Our canary
* condition is that target page was deleted.
*/
if (!state->readonly)
{
/* Get fresh copy of target page */
state->target = palloc_btree_page(state, state->targetblock);
/* Note that we deliberately do not update target LSN */
topaque = (BTPageOpaque) PageGetSpecialPointer(state->target);
/*
* All !readonly checks now performed; just return
*/
if (P_IGNORE(topaque))
return;
}
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("cross page item order invariant violated for index \"%s\"",
RelationGetRelationName(state->rel)),
errdetail_internal("Last item on page tid=(%u,%u) page lsn=%X/%X.",