Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * verify_gin.c
4 : : * Verifies the integrity of GIN indexes based on invariants.
5 : : *
6 : : *
7 : : * GIN index verification checks a number of invariants:
8 : : *
9 : : * - consistency: Paths in GIN graph have to contain consistent keys: tuples
10 : : * on parent pages consistently include tuples from children pages.
11 : : *
12 : : * - graph invariants: Each internal page must have at least one downlink, and
13 : : * can reference either only leaf pages or only internal pages.
14 : : *
15 : : *
16 : : * Copyright (c) 2016-2026, PostgreSQL Global Development Group
17 : : *
18 : : * IDENTIFICATION
19 : : * contrib/amcheck/verify_gin.c
20 : : *
21 : : *-------------------------------------------------------------------------
22 : : */
23 : : #include "postgres.h"
24 : :
25 : : #include "access/gin_private.h"
26 : : #include "access/nbtree.h"
27 : : #include "catalog/pg_am.h"
28 : : #include "utils/memutils.h"
29 : : #include "utils/rel.h"
30 : : #include "verify_common.h"
31 : : #include "string.h"
32 : :
33 : : /*
34 : : * GinScanItem represents one item of depth-first scan of the index.
35 : : */
36 : : typedef struct GinScanItem
37 : : {
38 : : int depth;
39 : : IndexTuple parenttup;
40 : : BlockNumber parentblk;
41 : : BlockNumber blkno;
42 : : struct GinScanItem *next;
43 : : } GinScanItem;
44 : :
45 : : /*
46 : : * GinPostingTreeScanItem represents one item of a depth-first posting tree scan.
47 : : */
48 : : typedef struct GinPostingTreeScanItem
49 : : {
50 : : int depth;
51 : : ItemPointerData parentkey;
52 : : BlockNumber parentblk;
53 : : BlockNumber blkno;
54 : : struct GinPostingTreeScanItem *next;
55 : : } GinPostingTreeScanItem;
56 : :
57 : :
402 tomas.vondra@postgre 58 :CBC 29 : PG_FUNCTION_INFO_V1(gin_index_check);
59 : :
60 : : static void gin_check_parent_keys_consistency(Relation rel,
61 : : Relation heaprel,
62 : : void *callback_state, bool readonly);
63 : : static void check_index_page(Relation rel, Buffer buffer, BlockNumber blockNo);
64 : : static IndexTuple gin_refind_parent(Relation rel,
65 : : BlockNumber parentblkno,
66 : : BlockNumber childblkno,
67 : : BufferAccessStrategy strategy);
68 : : static ItemId PageGetItemIdCareful(Relation rel, BlockNumber block, Page page,
69 : : OffsetNumber offset);
70 : :
71 : : /*
72 : : * gin_index_check(index regclass)
73 : : *
74 : : * Verify integrity of GIN index.
75 : : *
76 : : * Acquires AccessShareLock on heap & index relations.
77 : : */
78 : : Datum
79 : 26 : gin_index_check(PG_FUNCTION_ARGS)
80 : : {
81 : 26 : Oid indrelid = PG_GETARG_OID(0);
82 : :
83 : 26 : amcheck_lock_relation_and_check(indrelid,
84 : : GIN_AM_OID,
85 : : gin_check_parent_keys_consistency,
86 : : AccessShareLock,
87 : : NULL);
88 : :
89 : 21 : PG_RETURN_VOID();
90 : : }
91 : :
92 : : /*
93 : : * Read item pointers from leaf entry tuple.
94 : : *
95 : : * Returns a palloc'd array of ItemPointers. The number of items is returned
96 : : * in *nitems.
97 : : */
98 : : static ItemPointer
99 : 1399 : ginReadTupleWithoutState(IndexTuple itup, int *nitems)
100 : : {
101 : 1399 : Pointer ptr = GinGetPosting(itup);
102 : 1399 : int nipd = GinGetNPosting(itup);
103 : : ItemPointer ipd;
104 : : int ndecoded;
105 : :
106 [ + - ]: 1399 : if (GinItupIsCompressed(itup))
107 : : {
108 [ + - ]: 1399 : if (nipd > 0)
109 : : {
152 peter@eisentraut.org 110 :GNC 1399 : ipd = ginPostingListDecode(ptr, &ndecoded);
402 tomas.vondra@postgre 111 [ - + ]:CBC 1399 : if (nipd != ndecoded)
402 tomas.vondra@postgre 112 [ # # ]:UBC 0 : elog(ERROR, "number of items mismatch in GIN entry tuple, %d in tuple header, %d decoded",
113 : : nipd, ndecoded);
114 : : }
115 : : else
116 : 0 : ipd = palloc(0);
117 : : }
118 : : else
119 : : {
151 michael@paquier.xyz 120 :UNC 0 : ipd = palloc_array(ItemPointerData, nipd);
402 tomas.vondra@postgre 121 :UBC 0 : memcpy(ipd, ptr, sizeof(ItemPointerData) * nipd);
122 : : }
402 tomas.vondra@postgre 123 :CBC 1399 : *nitems = nipd;
124 : 1399 : return ipd;
125 : : }
126 : :
127 : : /*
128 : : * Scans through a posting tree (given by the root), and verifies that the keys
129 : : * on a child keys are consistent with the parent.
130 : : *
131 : : * Allocates a separate memory context and scans through posting tree graph.
132 : : */
133 : : static void
402 tomas.vondra@postgre 134 :UBC 0 : gin_check_posting_tree_parent_keys_consistency(Relation rel, BlockNumber posting_tree_root)
135 : : {
136 : 0 : BufferAccessStrategy strategy = GetAccessStrategy(BAS_BULKREAD);
137 : : GinPostingTreeScanItem *stack;
138 : : MemoryContext mctx;
139 : : MemoryContext oldcontext;
140 : :
141 : : int leafdepth;
142 : :
143 : 0 : mctx = AllocSetContextCreate(CurrentMemoryContext,
144 : : "posting tree check context",
145 : : ALLOCSET_DEFAULT_SIZES);
146 : 0 : oldcontext = MemoryContextSwitchTo(mctx);
147 : :
148 : : /*
149 : : * We don't know the height of the tree yet, but as soon as we encounter a
150 : : * leaf page, we will set 'leafdepth' to its depth.
151 : : */
152 : 0 : leafdepth = -1;
153 : :
154 : : /* Start the scan at the root page */
151 michael@paquier.xyz 155 :UNC 0 : stack = palloc0_object(GinPostingTreeScanItem);
402 tomas.vondra@postgre 156 :UBC 0 : stack->depth = 0;
157 : 0 : ItemPointerSetInvalid(&stack->parentkey);
158 : 0 : stack->parentblk = InvalidBlockNumber;
159 : 0 : stack->blkno = posting_tree_root;
160 : :
161 [ # # ]: 0 : elog(DEBUG3, "processing posting tree at blk %u", posting_tree_root);
162 : :
163 [ # # ]: 0 : while (stack)
164 : : {
165 : : GinPostingTreeScanItem *stack_next;
166 : : Buffer buffer;
167 : : Page page;
168 : : OffsetNumber i,
169 : : maxoff;
170 : : BlockNumber rightlink;
171 : :
172 [ # # ]: 0 : CHECK_FOR_INTERRUPTS();
173 : :
174 : 0 : buffer = ReadBufferExtended(rel, MAIN_FORKNUM, stack->blkno,
175 : : RBM_NORMAL, strategy);
176 : 0 : LockBuffer(buffer, GIN_SHARE);
249 peter@eisentraut.org 177 :UNC 0 : page = BufferGetPage(buffer);
178 : :
402 tomas.vondra@postgre 179 [ # # ]:UBC 0 : Assert(GinPageIsData(page));
180 : :
181 : : /* Check that the tree has the same height in all branches */
182 [ # # ]: 0 : if (GinPageIsLeaf(page))
183 : : {
184 : : ItemPointerData minItem;
185 : : int nlist;
186 : : ItemPointerData *list;
187 : : char tidrange_buf[MAXPGPATH];
188 : :
189 : 0 : ItemPointerSetMin(&minItem);
190 : :
191 [ # # ]: 0 : elog(DEBUG1, "page blk: %u, type leaf", stack->blkno);
192 : :
193 [ # # ]: 0 : if (leafdepth == -1)
194 : 0 : leafdepth = stack->depth;
195 [ # # ]: 0 : else if (stack->depth != leafdepth)
196 [ # # ]: 0 : ereport(ERROR,
197 : : (errcode(ERRCODE_INDEX_CORRUPTED),
198 : : errmsg("index \"%s\": internal pages traversal encountered leaf page unexpectedly on block %u",
199 : : RelationGetRelationName(rel), stack->blkno)));
200 : 0 : list = GinDataLeafPageGetItems(page, &nlist, minItem);
201 : :
202 [ # # ]: 0 : if (nlist > 0)
203 : 0 : snprintf(tidrange_buf, sizeof(tidrange_buf),
204 : : "%d tids (%u, %u) - (%u, %u)",
205 : : nlist,
206 : : ItemPointerGetBlockNumberNoCheck(&list[0]),
207 : 0 : ItemPointerGetOffsetNumberNoCheck(&list[0]),
208 : 0 : ItemPointerGetBlockNumberNoCheck(&list[nlist - 1]),
209 : 0 : ItemPointerGetOffsetNumberNoCheck(&list[nlist - 1]));
210 : : else
211 : 0 : snprintf(tidrange_buf, sizeof(tidrange_buf), "0 tids");
212 : :
213 [ # # ]: 0 : if (stack->parentblk != InvalidBlockNumber)
214 [ # # ]: 0 : elog(DEBUG3, "blk %u: parent %u highkey (%u, %u), %s",
215 : : stack->blkno,
216 : : stack->parentblk,
217 : : ItemPointerGetBlockNumberNoCheck(&stack->parentkey),
218 : : ItemPointerGetOffsetNumberNoCheck(&stack->parentkey),
219 : : tidrange_buf);
220 : : else
221 [ # # ]: 0 : elog(DEBUG3, "blk %u: root leaf, %s",
222 : : stack->blkno,
223 : : tidrange_buf);
224 : :
225 [ # # # # ]: 0 : if (stack->parentblk != InvalidBlockNumber &&
226 : 0 : ItemPointerGetOffsetNumberNoCheck(&stack->parentkey) != InvalidOffsetNumber &&
227 [ # # # # ]: 0 : nlist > 0 && ItemPointerCompare(&stack->parentkey, &list[nlist - 1]) < 0)
228 [ # # ]: 0 : ereport(ERROR,
229 : : (errcode(ERRCODE_INDEX_CORRUPTED),
230 : : errmsg("index \"%s\": tid exceeds parent's high key in postingTree leaf on block %u",
231 : : RelationGetRelationName(rel), stack->blkno)));
232 : : }
233 : : else
234 : : {
235 : : LocationIndex pd_lower;
236 : : ItemPointerData bound;
237 : : int lowersize;
238 : :
239 : : /*
240 : : * Check that tuples in each page are properly ordered and
241 : : * consistent with parent high key
242 : : */
243 : 0 : maxoff = GinPageGetOpaque(page)->maxoff;
244 : 0 : rightlink = GinPageGetOpaque(page)->rightlink;
245 : :
246 [ # # ]: 0 : elog(DEBUG1, "page blk: %u, type data, maxoff %d", stack->blkno, maxoff);
247 : :
248 [ # # ]: 0 : if (stack->parentblk != InvalidBlockNumber)
249 [ # # ]: 0 : elog(DEBUG3, "blk %u: internal posting tree page with %u items, parent %u highkey (%u, %u)",
250 : : stack->blkno, maxoff, stack->parentblk,
251 : : ItemPointerGetBlockNumberNoCheck(&stack->parentkey),
252 : : ItemPointerGetOffsetNumberNoCheck(&stack->parentkey));
253 : : else
254 [ # # ]: 0 : elog(DEBUG3, "blk %u: root internal posting tree page with %u items",
255 : : stack->blkno, maxoff);
256 : :
257 : : /*
258 : : * A GIN posting tree internal page stores PostingItems in the
259 : : * 'lower' part of the page. The 'upper' part is unused. The
260 : : * number of elements is stored in the opaque area (maxoff). Make
261 : : * sure the size of the 'lower' part agrees with 'maxoff'
262 : : *
263 : : * We didn't set pd_lower until PostgreSQL version 9.4, so if this
264 : : * check fails, it could also be because the index was
265 : : * binary-upgraded from an earlier version. That was a long time
266 : : * ago, though, so let's warn if it doesn't match.
267 : : */
268 : 0 : pd_lower = ((PageHeader) page)->pd_lower;
269 : 0 : lowersize = pd_lower - MAXALIGN(SizeOfPageHeaderData);
270 [ # # ]: 0 : if ((lowersize - MAXALIGN(sizeof(ItemPointerData))) / sizeof(PostingItem) != maxoff)
271 [ # # ]: 0 : ereport(ERROR,
272 : : (errcode(ERRCODE_INDEX_CORRUPTED),
273 : : errmsg("index \"%s\" has unexpected pd_lower %u in posting tree block %u with maxoff %u)",
274 : : RelationGetRelationName(rel), pd_lower, stack->blkno, maxoff)));
275 : :
276 : : /*
277 : : * Before the PostingItems, there's one ItemPointerData in the
278 : : * 'lower' part that stores the page's high key.
279 : : */
280 : 0 : bound = *GinDataPageGetRightBound(page);
281 : :
282 : : /*
283 : : * Gin page right bound has a sane value only when not a highkey
284 : : * on the rightmost page (at a given level). For the rightmost
285 : : * page does not store the highkey explicitly, and the value is
286 : : * infinity.
287 : : */
288 [ # # # # ]: 0 : if (ItemPointerIsValid(&stack->parentkey) &&
289 : 0 : rightlink != InvalidBlockNumber &&
290 [ # # ]: 0 : !ItemPointerEquals(&stack->parentkey, &bound))
291 [ # # ]: 0 : ereport(ERROR,
292 : : (errcode(ERRCODE_INDEX_CORRUPTED),
293 : : errmsg("index \"%s\": posting tree page's high key (%u, %u) doesn't match the downlink on block %u (parent blk %u, key (%u, %u))",
294 : : RelationGetRelationName(rel),
295 : : ItemPointerGetBlockNumberNoCheck(&bound),
296 : : ItemPointerGetOffsetNumberNoCheck(&bound),
297 : : stack->blkno, stack->parentblk,
298 : : ItemPointerGetBlockNumberNoCheck(&stack->parentkey),
299 : : ItemPointerGetOffsetNumberNoCheck(&stack->parentkey))));
300 : :
301 [ # # ]: 0 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
302 : : {
303 : : GinPostingTreeScanItem *ptr;
304 : 0 : PostingItem *posting_item = GinDataPageGetPostingItem(page, i);
305 : :
306 : : /* ItemPointerGetOffsetNumber expects a valid pointer */
307 [ # # # # ]: 0 : if (!(i == maxoff &&
308 : : rightlink == InvalidBlockNumber))
309 [ # # ]: 0 : elog(DEBUG3, "key (%u, %u) -> %u",
310 : : ItemPointerGetBlockNumber(&posting_item->key),
311 : : ItemPointerGetOffsetNumber(&posting_item->key),
312 : : BlockIdGetBlockNumber(&posting_item->child_blkno));
313 : : else
314 [ # # ]: 0 : elog(DEBUG3, "key (%u, %u) -> %u",
315 : : 0, 0, BlockIdGetBlockNumber(&posting_item->child_blkno));
316 : :
317 [ # # # # ]: 0 : if (i == maxoff && rightlink == InvalidBlockNumber)
318 : : {
319 : : /*
320 : : * The rightmost item in the tree level has (0, 0) as the
321 : : * key
322 : : */
323 [ # # # # ]: 0 : if (ItemPointerGetBlockNumberNoCheck(&posting_item->key) != 0 ||
324 : 0 : ItemPointerGetOffsetNumberNoCheck(&posting_item->key) != 0)
325 [ # # ]: 0 : ereport(ERROR,
326 : : (errcode(ERRCODE_INDEX_CORRUPTED),
327 : : errmsg("index \"%s\": rightmost posting tree page (blk %u) has unexpected last key (%u, %u)",
328 : : RelationGetRelationName(rel),
329 : : stack->blkno,
330 : : ItemPointerGetBlockNumberNoCheck(&posting_item->key),
331 : : ItemPointerGetOffsetNumberNoCheck(&posting_item->key))));
332 : : }
333 [ # # ]: 0 : else if (i != FirstOffsetNumber)
334 : : {
335 : 0 : PostingItem *previous_posting_item = GinDataPageGetPostingItem(page, i - 1);
336 : :
337 [ # # ]: 0 : if (ItemPointerCompare(&posting_item->key, &previous_posting_item->key) < 0)
338 [ # # ]: 0 : ereport(ERROR,
339 : : (errcode(ERRCODE_INDEX_CORRUPTED),
340 : : errmsg("index \"%s\" has wrong tuple order in posting tree, block %u, offset %u",
341 : : RelationGetRelationName(rel), stack->blkno, i)));
342 : : }
343 : :
344 : : /*
345 : : * Check if this tuple is consistent with the downlink in the
346 : : * parent.
347 : : */
322 348 [ # # # # : 0 : if (i == maxoff && ItemPointerIsValid(&stack->parentkey) &&
# # ]
402 349 : 0 : ItemPointerCompare(&stack->parentkey, &posting_item->key) < 0)
350 [ # # ]: 0 : ereport(ERROR,
351 : : (errcode(ERRCODE_INDEX_CORRUPTED),
352 : : errmsg("index \"%s\": posting item exceeds parent's high key in postingTree internal page on block %u offset %u",
353 : : RelationGetRelationName(rel),
354 : : stack->blkno, i)));
355 : :
356 : : /* This is an internal page, recurse into the child. */
151 michael@paquier.xyz 357 :UNC 0 : ptr = palloc_object(GinPostingTreeScanItem);
402 tomas.vondra@postgre 358 :UBC 0 : ptr->depth = stack->depth + 1;
359 : :
360 : : /*
361 : : * The rightmost parent key is always invalid item pointer.
362 : : * Its value is 'Infinity' and not explicitly stored.
363 : : */
322 364 : 0 : ptr->parentkey = posting_item->key;
402 365 : 0 : ptr->parentblk = stack->blkno;
366 : 0 : ptr->blkno = BlockIdGetBlockNumber(&posting_item->child_blkno);
367 : 0 : ptr->next = stack->next;
368 : 0 : stack->next = ptr;
369 : : }
370 : : }
39 andres@anarazel.de 371 :UNC 0 : UnlockReleaseBuffer(buffer);
372 : :
373 : : /* Step to next item in the queue */
402 tomas.vondra@postgre 374 :UBC 0 : stack_next = stack->next;
375 : 0 : pfree(stack);
376 : 0 : stack = stack_next;
377 : : }
378 : :
379 : 0 : MemoryContextSwitchTo(oldcontext);
380 : 0 : MemoryContextDelete(mctx);
381 : 0 : }
382 : :
383 : : /*
384 : : * Main entry point for GIN checks.
385 : : *
386 : : * Allocates memory context and scans through the whole GIN graph.
387 : : */
388 : : static void
402 tomas.vondra@postgre 389 :CBC 26 : gin_check_parent_keys_consistency(Relation rel,
390 : : Relation heaprel,
391 : : void *callback_state,
392 : : bool readonly)
393 : : {
394 : 26 : BufferAccessStrategy strategy = GetAccessStrategy(BAS_BULKREAD);
395 : : GinScanItem *stack;
396 : : MemoryContext mctx;
397 : : MemoryContext oldcontext;
398 : : GinState state;
399 : : int leafdepth;
400 : :
401 : 26 : mctx = AllocSetContextCreate(CurrentMemoryContext,
402 : : "amcheck consistency check context",
403 : : ALLOCSET_DEFAULT_SIZES);
404 : 26 : oldcontext = MemoryContextSwitchTo(mctx);
405 : 26 : initGinState(&state, rel);
406 : :
407 : : /*
408 : : * We don't know the height of the tree yet, but as soon as we encounter a
409 : : * leaf page, we will set 'leafdepth' to its depth.
410 : : */
411 : 26 : leafdepth = -1;
412 : :
413 : : /* Start the scan at the root page */
151 michael@paquier.xyz 414 :GNC 26 : stack = palloc0_object(GinScanItem);
402 tomas.vondra@postgre 415 :CBC 26 : stack->depth = 0;
416 : 26 : stack->parenttup = NULL;
417 : 26 : stack->parentblk = InvalidBlockNumber;
418 : 26 : stack->blkno = GIN_ROOT_BLKNO;
419 : :
420 [ + + ]: 167 : while (stack)
421 : : {
422 : : GinScanItem *stack_next;
423 : : Buffer buffer;
424 : : Page page;
425 : : OffsetNumber i,
426 : : maxoff,
427 : : prev_attnum;
428 : : IndexTuple prev_tuple;
429 : : BlockNumber rightlink;
430 : :
431 [ - + ]: 146 : CHECK_FOR_INTERRUPTS();
432 : :
433 : 146 : buffer = ReadBufferExtended(rel, MAIN_FORKNUM, stack->blkno,
434 : : RBM_NORMAL, strategy);
435 : 146 : LockBuffer(buffer, GIN_SHARE);
249 peter@eisentraut.org 436 :GNC 146 : page = BufferGetPage(buffer);
402 tomas.vondra@postgre 437 :CBC 146 : maxoff = PageGetMaxOffsetNumber(page);
438 : 146 : rightlink = GinPageGetOpaque(page)->rightlink;
439 : :
440 : : /* Do basic sanity checks on the page headers */
441 : 146 : check_index_page(rel, buffer, stack->blkno);
442 : :
443 [ - + ]: 146 : elog(DEBUG3, "processing entry tree page at blk %u, maxoff: %u", stack->blkno, maxoff);
444 : :
445 : : /*
446 : : * It's possible that the page was split since we looked at the
447 : : * parent, so that we didn't missed the downlink of the right sibling
448 : : * when we scanned the parent. If so, add the right sibling to the
449 : : * stack now.
450 : : */
451 [ + + ]: 146 : if (stack->parenttup != NULL)
452 : : {
453 : : GinNullCategory parent_key_category;
454 : 115 : Datum parent_key = gintuple_get_key(&state,
455 : : stack->parenttup,
456 : : &parent_key_category);
322 457 : 115 : OffsetNumber parent_key_attnum = gintuple_get_attrnum(&state, stack->parenttup);
402 458 : 115 : ItemId iid = PageGetItemIdCareful(rel, stack->blkno,
459 : : page, maxoff);
460 : 115 : IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
322 461 : 115 : OffsetNumber page_max_key_attnum = gintuple_get_attrnum(&state, idxtuple);
462 : : GinNullCategory page_max_key_category;
402 463 : 115 : Datum page_max_key = gintuple_get_key(&state, idxtuple, &page_max_key_category);
464 : :
465 [ + - - + ]: 230 : if (rightlink != InvalidBlockNumber &&
322 466 : 115 : ginCompareAttEntries(&state, page_max_key_attnum, page_max_key,
467 : : page_max_key_category, parent_key_attnum,
468 : : parent_key, parent_key_category) < 0)
469 : : {
470 : : /* split page detected, install right link to the stack */
471 : : GinScanItem *ptr;
472 : :
402 tomas.vondra@postgre 473 [ # # ]:UBC 0 : elog(DEBUG3, "split detected for blk: %u, parent blk: %u", stack->blkno, stack->parentblk);
474 : :
151 michael@paquier.xyz 475 :UNC 0 : ptr = palloc_object(GinScanItem);
402 tomas.vondra@postgre 476 :UBC 0 : ptr->depth = stack->depth;
477 : 0 : ptr->parenttup = CopyIndexTuple(stack->parenttup);
478 : 0 : ptr->parentblk = stack->parentblk;
479 : 0 : ptr->blkno = rightlink;
480 : 0 : ptr->next = stack->next;
481 : 0 : stack->next = ptr;
482 : : }
483 : : }
484 : :
485 : : /* Check that the tree has the same height in all branches */
402 tomas.vondra@postgre 486 [ + + ]:CBC 146 : if (GinPageIsLeaf(page))
487 : : {
488 [ + + ]: 140 : if (leafdepth == -1)
489 : 25 : leafdepth = stack->depth;
490 [ - + ]: 115 : else if (stack->depth != leafdepth)
402 tomas.vondra@postgre 491 [ # # ]:UBC 0 : ereport(ERROR,
492 : : (errcode(ERRCODE_INDEX_CORRUPTED),
493 : : errmsg("index \"%s\": internal pages traversal encountered leaf page unexpectedly on block %u",
494 : : RelationGetRelationName(rel), stack->blkno)));
495 : : }
496 : :
497 : : /*
498 : : * Check that tuples in each page are properly ordered and consistent
499 : : * with parent high key
500 : : */
402 tomas.vondra@postgre 501 :CBC 146 : prev_tuple = NULL;
502 : 146 : prev_attnum = InvalidAttrNumber;
503 [ + + ]: 1666 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
504 : : {
505 : 1525 : ItemId iid = PageGetItemIdCareful(rel, stack->blkno, page, i);
506 : 1525 : IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
322 507 : 1525 : OffsetNumber current_attnum = gintuple_get_attrnum(&state, idxtuple);
508 : : GinNullCategory current_key_category;
509 : : Datum current_key;
510 : :
402 511 [ - + ]: 1525 : if (MAXALIGN(ItemIdGetLength(iid)) != MAXALIGN(IndexTupleSize(idxtuple)))
402 tomas.vondra@postgre 512 [ # # ]:UBC 0 : ereport(ERROR,
513 : : (errcode(ERRCODE_INDEX_CORRUPTED),
514 : : errmsg("index \"%s\" has inconsistent tuple sizes, block %u, offset %u",
515 : : RelationGetRelationName(rel), stack->blkno, i)));
516 : :
402 tomas.vondra@postgre 517 :CBC 1525 : current_key = gintuple_get_key(&state, idxtuple, ¤t_key_category);
518 : :
519 : : /*
520 : : * Compare the entry to the preceding one.
521 : : *
522 : : * Don't check for high key on the rightmost inner page, as this
523 : : * key is not really stored explicitly.
524 : : *
525 : : * The entries may be for different attributes, so make sure to
526 : : * use ginCompareAttEntries for comparison.
527 : : */
322 528 [ + + + + ]: 1525 : if ((i != FirstOffsetNumber) &&
529 [ + + + + ]: 145 : !(i == maxoff && rightlink == InvalidBlockNumber && !GinPageIsLeaf(page)))
530 : : {
531 : : Datum prev_key;
532 : : GinNullCategory prev_key_category;
533 : :
402 534 : 1374 : prev_key = gintuple_get_key(&state, prev_tuple, &prev_key_category);
322 535 [ + + ]: 1374 : if (ginCompareAttEntries(&state, prev_attnum, prev_key,
536 : : prev_key_category, current_attnum,
537 : : current_key, current_key_category) >= 0)
402 538 [ + - ]: 3 : ereport(ERROR,
539 : : (errcode(ERRCODE_INDEX_CORRUPTED),
540 : : errmsg("index \"%s\" has wrong tuple order on entry tree page, block %u, offset %u, rightlink %u",
541 : : RelationGetRelationName(rel), stack->blkno, i, rightlink)));
542 : : }
543 : :
544 : : /*
545 : : * Check if this tuple is consistent with the downlink in the
546 : : * parent.
547 : : */
548 [ + + + + ]: 1522 : if (stack->parenttup &&
549 : : i == maxoff)
550 : : {
551 : : GinNullCategory parent_key_category;
322 552 : 115 : OffsetNumber parent_key_attnum = gintuple_get_attrnum(&state, stack->parenttup);
402 553 : 115 : Datum parent_key = gintuple_get_key(&state,
554 : : stack->parenttup,
555 : : &parent_key_category);
556 : :
322 557 [ + + ]: 115 : if (ginCompareAttEntries(&state, current_attnum, current_key,
558 : : current_key_category, parent_key_attnum,
559 : : parent_key, parent_key_category) > 0)
560 : : {
561 : : /*
562 : : * There was a discrepancy between parent and child
563 : : * tuples. We need to verify it is not a result of
564 : : * concurrent call of gistplacetopage(). So, lock parent
565 : : * and try to find downlink for current page. It may be
566 : : * missing due to concurrent page split, this is OK.
567 : : */
402 568 : 2 : pfree(stack->parenttup);
569 : 2 : stack->parenttup = gin_refind_parent(rel, stack->parentblk,
570 : : stack->blkno, strategy);
571 : :
572 : : /* We found it - make a final check before failing */
573 [ - + ]: 2 : if (!stack->parenttup)
402 tomas.vondra@postgre 574 [ # # ]:UBC 0 : elog(NOTICE, "Unable to find parent tuple for block %u on block %u due to concurrent split",
575 : : stack->blkno, stack->parentblk);
576 : : else
577 : : {
322 tomas.vondra@postgre 578 :CBC 2 : parent_key_attnum = gintuple_get_attrnum(&state, stack->parenttup);
402 579 : 2 : parent_key = gintuple_get_key(&state,
580 : : stack->parenttup,
581 : : &parent_key_category);
582 : :
583 : : /*
584 : : * Check if it is properly adjusted. If succeed,
585 : : * proceed to the next key.
586 : : */
322 587 [ + - ]: 2 : if (ginCompareAttEntries(&state, current_attnum, current_key,
588 : : current_key_category, parent_key_attnum,
589 : : parent_key, parent_key_category) > 0)
402 590 [ + - ]: 2 : ereport(ERROR,
591 : : (errcode(ERRCODE_INDEX_CORRUPTED),
592 : : errmsg("index \"%s\" has inconsistent records on page %u offset %u",
593 : : RelationGetRelationName(rel), stack->blkno, i)));
594 : : }
595 : : }
596 : : }
597 : :
598 : : /* If this is an internal page, recurse into the child */
599 [ + + ]: 1520 : if (!GinPageIsLeaf(page))
600 : : {
601 : : GinScanItem *ptr;
602 : :
151 michael@paquier.xyz 603 :GNC 121 : ptr = palloc_object(GinScanItem);
402 tomas.vondra@postgre 604 :CBC 121 : ptr->depth = stack->depth + 1;
605 : : /* last tuple in layer has no high key */
322 606 [ + + + - ]: 121 : if (i == maxoff && rightlink == InvalidBlockNumber)
402 607 : 5 : ptr->parenttup = NULL;
608 : : else
322 609 : 116 : ptr->parenttup = CopyIndexTuple(idxtuple);
402 610 : 121 : ptr->parentblk = stack->blkno;
611 : 121 : ptr->blkno = GinGetDownlink(idxtuple);
612 : 121 : ptr->next = stack->next;
613 : 121 : stack->next = ptr;
614 : : }
615 : : /* If this item is a pointer to a posting tree, recurse into it */
616 [ - + ]: 1399 : else if (GinIsPostingTree(idxtuple))
617 : : {
402 tomas.vondra@postgre 618 :UBC 0 : BlockNumber rootPostingTree = GinGetPostingTree(idxtuple);
619 : :
620 : 0 : gin_check_posting_tree_parent_keys_consistency(rel, rootPostingTree);
621 : : }
622 : : else
623 : : {
624 : : ItemPointer ipd;
625 : : int nipd;
626 : :
402 tomas.vondra@postgre 627 :CBC 1399 : ipd = ginReadTupleWithoutState(idxtuple, &nipd);
628 : :
629 [ + + ]: 317511 : for (int j = 0; j < nipd; j++)
630 : : {
631 [ + - + - : 316112 : if (!OffsetNumberIsValid(ItemPointerGetOffsetNumber(&ipd[j])))
- + ]
402 tomas.vondra@postgre 632 [ # # ]:UBC 0 : ereport(ERROR,
633 : : (errcode(ERRCODE_INDEX_CORRUPTED),
634 : : errmsg("index \"%s\": posting list contains invalid heap pointer on block %u",
635 : : RelationGetRelationName(rel), stack->blkno)));
636 : : }
402 tomas.vondra@postgre 637 :CBC 1399 : pfree(ipd);
638 : : }
639 : :
640 : 1520 : prev_tuple = CopyIndexTuple(idxtuple);
322 641 : 1520 : prev_attnum = current_attnum;
642 : : }
643 : :
39 andres@anarazel.de 644 :GNC 141 : UnlockReleaseBuffer(buffer);
645 : :
646 : : /* Step to next item in the queue */
402 tomas.vondra@postgre 647 :CBC 141 : stack_next = stack->next;
648 [ + + ]: 141 : if (stack->parenttup)
649 : 113 : pfree(stack->parenttup);
650 : 141 : pfree(stack);
651 : 141 : stack = stack_next;
652 : : }
653 : :
654 : 21 : MemoryContextSwitchTo(oldcontext);
655 : 21 : MemoryContextDelete(mctx);
656 : 21 : }
657 : :
658 : : /*
659 : : * Verify that a freshly-read page looks sane.
660 : : */
661 : : static void
662 : 146 : check_index_page(Relation rel, Buffer buffer, BlockNumber blockNo)
663 : : {
664 : 146 : Page page = BufferGetPage(buffer);
665 : :
666 : : /*
667 : : * ReadBuffer verifies that every newly-read page passes
668 : : * PageHeaderIsValid, which means it either contains a reasonably sane
669 : : * page header or is all-zero. We have to defend against the all-zero
670 : : * case, however.
671 : : */
672 [ - + ]: 146 : if (PageIsNew(page))
402 tomas.vondra@postgre 673 [ # # ]:UBC 0 : ereport(ERROR,
674 : : (errcode(ERRCODE_INDEX_CORRUPTED),
675 : : errmsg("index \"%s\" contains unexpected zero page at block %u",
676 : : RelationGetRelationName(rel),
677 : : BufferGetBlockNumber(buffer)),
678 : : errhint("Please REINDEX it.")));
679 : :
680 : : /*
681 : : * Additionally check that the special area looks sane.
682 : : */
402 tomas.vondra@postgre 683 [ - + ]:CBC 146 : if (PageGetSpecialSize(page) != MAXALIGN(sizeof(GinPageOpaqueData)))
402 tomas.vondra@postgre 684 [ # # ]:UBC 0 : ereport(ERROR,
685 : : (errcode(ERRCODE_INDEX_CORRUPTED),
686 : : errmsg("index \"%s\" contains corrupted page at block %u",
687 : : RelationGetRelationName(rel),
688 : : BufferGetBlockNumber(buffer)),
689 : : errhint("Please REINDEX it.")));
690 : :
402 tomas.vondra@postgre 691 [ - + ]:CBC 146 : if (GinPageIsDeleted(page))
692 : : {
402 tomas.vondra@postgre 693 [ # # ]:UBC 0 : if (!GinPageIsLeaf(page))
694 [ # # ]: 0 : ereport(ERROR,
695 : : (errcode(ERRCODE_INDEX_CORRUPTED),
696 : : errmsg("index \"%s\" has deleted internal page %u",
697 : : RelationGetRelationName(rel), blockNo)));
698 [ # # ]: 0 : if (PageGetMaxOffsetNumber(page) > InvalidOffsetNumber)
699 [ # # ]: 0 : ereport(ERROR,
700 : : (errcode(ERRCODE_INDEX_CORRUPTED),
701 : : errmsg("index \"%s\" has deleted page %u with tuples",
702 : : RelationGetRelationName(rel), blockNo)));
703 : : }
402 tomas.vondra@postgre 704 [ - + ]:CBC 146 : else if (PageGetMaxOffsetNumber(page) > MaxIndexTuplesPerPage)
402 tomas.vondra@postgre 705 [ # # ]:UBC 0 : ereport(ERROR,
706 : : (errcode(ERRCODE_INDEX_CORRUPTED),
707 : : errmsg("index \"%s\" has page %u with exceeding count of tuples",
708 : : RelationGetRelationName(rel), blockNo)));
402 tomas.vondra@postgre 709 :CBC 146 : }
710 : :
711 : : /*
712 : : * Try to re-find downlink pointing to 'blkno', in 'parentblkno'.
713 : : *
714 : : * If found, returns a palloc'd copy of the downlink tuple. Otherwise,
715 : : * returns NULL.
716 : : */
717 : : static IndexTuple
718 : 2 : gin_refind_parent(Relation rel, BlockNumber parentblkno,
719 : : BlockNumber childblkno, BufferAccessStrategy strategy)
720 : : {
721 : : Buffer parentbuf;
722 : : Page parentpage;
723 : : OffsetNumber o,
724 : : parent_maxoff;
725 : 2 : IndexTuple result = NULL;
726 : :
727 : 2 : parentbuf = ReadBufferExtended(rel, MAIN_FORKNUM, parentblkno, RBM_NORMAL,
728 : : strategy);
729 : :
730 : 2 : LockBuffer(parentbuf, GIN_SHARE);
731 : 2 : parentpage = BufferGetPage(parentbuf);
732 : :
733 [ - + ]: 2 : if (GinPageIsLeaf(parentpage))
734 : : {
402 tomas.vondra@postgre 735 :UBC 0 : UnlockReleaseBuffer(parentbuf);
736 : 0 : return result;
737 : : }
738 : :
402 tomas.vondra@postgre 739 :CBC 2 : parent_maxoff = PageGetMaxOffsetNumber(parentpage);
740 [ + - ]: 2 : for (o = FirstOffsetNumber; o <= parent_maxoff; o = OffsetNumberNext(o))
741 : : {
742 : 2 : ItemId p_iid = PageGetItemIdCareful(rel, parentblkno, parentpage, o);
743 : 2 : IndexTuple itup = (IndexTuple) PageGetItem(parentpage, p_iid);
744 : :
322 745 [ + - ]: 2 : if (GinGetDownlink(itup) == childblkno)
746 : : {
747 : : /* Found it! Make copy and return it */
402 748 : 2 : result = CopyIndexTuple(itup);
749 : 2 : break;
750 : : }
751 : : }
752 : :
753 : 2 : UnlockReleaseBuffer(parentbuf);
754 : :
755 : 2 : return result;
756 : : }
757 : :
758 : : static ItemId
759 : 1642 : PageGetItemIdCareful(Relation rel, BlockNumber block, Page page,
760 : : OffsetNumber offset)
761 : : {
762 : 1642 : ItemId itemid = PageGetItemId(page, offset);
763 : :
764 [ - + ]: 1642 : if (ItemIdGetOffset(itemid) + ItemIdGetLength(itemid) >
765 : : BLCKSZ - MAXALIGN(sizeof(GinPageOpaqueData)))
402 tomas.vondra@postgre 766 [ # # ]:UBC 0 : ereport(ERROR,
767 : : (errcode(ERRCODE_INDEX_CORRUPTED),
768 : : errmsg("line pointer points past end of tuple space in index \"%s\"",
769 : : RelationGetRelationName(rel)),
770 : : errdetail_internal("Index tid=(%u,%u) lp_off=%u, lp_len=%u lp_flags=%u.",
771 : : block, offset, ItemIdGetOffset(itemid),
772 : : ItemIdGetLength(itemid),
773 : : ItemIdGetFlags(itemid))));
774 : :
775 : : /*
776 : : * Verify that line pointer isn't LP_REDIRECT or LP_UNUSED or LP_DEAD,
777 : : * since GIN never uses all three. Verify that line pointer has storage,
778 : : * too.
779 : : */
402 tomas.vondra@postgre 780 [ + - + - ]:CBC 1642 : if (ItemIdIsRedirected(itemid) || !ItemIdIsUsed(itemid) ||
781 [ + - - + ]: 1642 : ItemIdIsDead(itemid) || ItemIdGetLength(itemid) == 0)
402 tomas.vondra@postgre 782 [ # # ]:UBC 0 : ereport(ERROR,
783 : : (errcode(ERRCODE_INDEX_CORRUPTED),
784 : : errmsg("invalid line pointer storage in index \"%s\"",
785 : : RelationGetRelationName(rel)),
786 : : errdetail_internal("Index tid=(%u,%u) lp_off=%u, lp_len=%u lp_flags=%u.",
787 : : block, offset, ItemIdGetOffset(itemid),
788 : : ItemIdGetLength(itemid),
789 : : ItemIdGetFlags(itemid))));
790 : :
402 tomas.vondra@postgre 791 :CBC 1642 : return itemid;
792 : : }
|
