Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * ginbtree.c
4 : * page utilities routines for the postgres inverted index access method.
5 : *
6 : *
7 : * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8 : * Portions Copyright (c) 1994, Regents of the University of California
9 : *
10 : * IDENTIFICATION
11 : * src/backend/access/gin/ginbtree.c
12 : *-------------------------------------------------------------------------
13 : */
14 :
15 : #include "postgres.h"
16 :
17 : #include "access/gin_private.h"
18 : #include "access/ginxlog.h"
19 : #include "access/xloginsert.h"
20 : #include "miscadmin.h"
21 : #include "utils/memutils.h"
22 : #include "utils/rel.h"
23 :
24 : static void ginFindParents(GinBtree btree, GinBtreeStack *stack);
25 : static bool ginPlaceToPage(GinBtree btree, GinBtreeStack *stack,
26 : void *insertdata, BlockNumber updateblkno,
27 : Buffer childbuf, GinStatsData *buildStats);
28 : static void ginFinishSplit(GinBtree btree, GinBtreeStack *stack,
29 : bool freestack, GinStatsData *buildStats);
30 :
31 : /*
32 : * Lock buffer by needed method for search.
33 : */
34 : int
35 87994 : ginTraverseLock(Buffer buffer, bool searchMode)
36 : {
37 : Page page;
38 87994 : int access = GIN_SHARE;
39 :
40 87994 : LockBuffer(buffer, GIN_SHARE);
41 87994 : page = BufferGetPage(buffer);
42 87994 : if (GinPageIsLeaf(page))
43 : {
44 44947 : if (searchMode == FALSE)
45 : {
46 : /* we should relock our page */
47 44826 : LockBuffer(buffer, GIN_UNLOCK);
48 44826 : LockBuffer(buffer, GIN_EXCLUSIVE);
49 :
50 : /* But root can become non-leaf during relock */
51 44826 : if (!GinPageIsLeaf(page))
52 : {
53 : /* restore old lock type (very rare) */
54 0 : LockBuffer(buffer, GIN_UNLOCK);
55 0 : LockBuffer(buffer, GIN_SHARE);
56 : }
57 : else
58 44826 : access = GIN_EXCLUSIVE;
59 : }
60 : }
61 :
62 87994 : return access;
63 : }
64 :
65 : /*
66 : * Descend the tree to the leaf page that contains or would contain the key
67 : * we're searching for. The key should already be filled in 'btree', in
68 : * tree-type specific manner. If btree->fullScan is true, descends to the
69 : * leftmost leaf page.
70 : *
71 : * If 'searchmode' is false, on return stack->buffer is exclusively locked,
72 : * and the stack represents the full path to the root. Otherwise stack->buffer
73 : * is share-locked, and stack->parent is NULL.
74 : */
75 : GinBtreeStack *
76 44939 : ginFindLeafPage(GinBtree btree, bool searchMode, Snapshot snapshot)
77 : {
78 : GinBtreeStack *stack;
79 :
80 44939 : stack = (GinBtreeStack *) palloc(sizeof(GinBtreeStack));
81 44939 : stack->blkno = btree->rootBlkno;
82 44939 : stack->buffer = ReadBuffer(btree->index, btree->rootBlkno);
83 44939 : stack->parent = NULL;
84 44939 : stack->predictNumber = 1;
85 :
86 : for (;;)
87 : {
88 : Page page;
89 : BlockNumber child;
90 : int access;
91 :
92 87984 : stack->off = InvalidOffsetNumber;
93 :
94 87984 : page = BufferGetPage(stack->buffer);
95 87984 : TestForOldSnapshot(snapshot, btree->index, page);
96 :
97 87984 : access = ginTraverseLock(stack->buffer, searchMode);
98 :
99 : /*
100 : * If we're going to modify the tree, finish any incomplete splits we
101 : * encounter on the way.
102 : */
103 87984 : if (!searchMode && GinPageIsIncompleteSplit(page))
104 0 : ginFinishSplit(btree, stack, false, NULL);
105 :
106 : /*
107 : * ok, page is correctly locked, we should check to move right ..,
108 : * root never has a right link, so small optimization
109 : */
110 219011 : while (btree->fullScan == FALSE && stack->blkno != btree->rootBlkno &&
111 43043 : btree->isMoveRight(btree, page))
112 : {
113 0 : BlockNumber rightlink = GinPageGetOpaque(page)->rightlink;
114 :
115 0 : if (rightlink == InvalidBlockNumber)
116 : /* rightmost page */
117 0 : break;
118 :
119 0 : stack->buffer = ginStepRight(stack->buffer, btree->index, access);
120 0 : stack->blkno = rightlink;
121 0 : page = BufferGetPage(stack->buffer);
122 0 : TestForOldSnapshot(snapshot, btree->index, page);
123 :
124 0 : if (!searchMode && GinPageIsIncompleteSplit(page))
125 0 : ginFinishSplit(btree, stack, false, NULL);
126 : }
127 :
128 87984 : if (GinPageIsLeaf(page)) /* we found, return locked page */
129 89878 : return stack;
130 :
131 : /* now we have correct buffer, try to find child */
132 43045 : child = btree->findChildPage(btree, stack);
133 :
134 43045 : LockBuffer(stack->buffer, GIN_UNLOCK);
135 43045 : Assert(child != InvalidBlockNumber);
136 43045 : Assert(stack->blkno != child);
137 :
138 43045 : if (searchMode)
139 : {
140 : /* in search mode we may forget path to leaf */
141 75 : stack->blkno = child;
142 75 : stack->buffer = ReleaseAndReadBuffer(stack->buffer, btree->index, stack->blkno);
143 : }
144 : else
145 : {
146 42970 : GinBtreeStack *ptr = (GinBtreeStack *) palloc(sizeof(GinBtreeStack));
147 :
148 42970 : ptr->parent = stack;
149 42970 : stack = ptr;
150 42970 : stack->blkno = child;
151 42970 : stack->buffer = ReadBuffer(btree->index, stack->blkno);
152 42970 : stack->predictNumber = 1;
153 : }
154 43045 : }
155 : }
156 :
157 : /*
158 : * Step right from current page.
159 : *
160 : * The next page is locked first, before releasing the current page. This is
161 : * crucial to protect from concurrent page deletion (see comment in
162 : * ginDeletePage).
163 : */
164 : Buffer
165 39 : ginStepRight(Buffer buffer, Relation index, int lockmode)
166 : {
167 : Buffer nextbuffer;
168 39 : Page page = BufferGetPage(buffer);
169 39 : bool isLeaf = GinPageIsLeaf(page);
170 39 : bool isData = GinPageIsData(page);
171 39 : BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
172 :
173 39 : nextbuffer = ReadBuffer(index, blkno);
174 39 : LockBuffer(nextbuffer, lockmode);
175 39 : UnlockReleaseBuffer(buffer);
176 :
177 : /* Sanity check that the page we stepped to is of similar kind. */
178 39 : page = BufferGetPage(nextbuffer);
179 39 : if (isLeaf != GinPageIsLeaf(page) || isData != GinPageIsData(page))
180 0 : elog(ERROR, "right sibling of GIN page is of different type");
181 :
182 : /*
183 : * Given the proper lock sequence above, we should never land on a deleted
184 : * page.
185 : */
186 39 : if (GinPageIsDeleted(page))
187 0 : elog(ERROR, "right sibling of GIN page was deleted");
188 :
189 39 : return nextbuffer;
190 : }
191 :
192 : void
193 44939 : freeGinBtreeStack(GinBtreeStack *stack)
194 : {
195 177580 : while (stack)
196 : {
197 87702 : GinBtreeStack *tmp = stack->parent;
198 :
199 87702 : if (stack->buffer != InvalidBuffer)
200 87702 : ReleaseBuffer(stack->buffer);
201 :
202 87702 : pfree(stack);
203 87702 : stack = tmp;
204 : }
205 44939 : }
206 :
207 : /*
208 : * Try to find parent for current stack position. Returns correct parent and
209 : * child's offset in stack->parent. The root page is never released, to
210 : * to prevent conflict with vacuum process.
211 : */
212 : static void
213 0 : ginFindParents(GinBtree btree, GinBtreeStack *stack)
214 : {
215 : Page page;
216 : Buffer buffer;
217 : BlockNumber blkno,
218 : leftmostBlkno;
219 : OffsetNumber offset;
220 : GinBtreeStack *root;
221 : GinBtreeStack *ptr;
222 :
223 : /*
224 : * Unwind the stack all the way up to the root, leaving only the root
225 : * item.
226 : *
227 : * Be careful not to release the pin on the root page! The pin on root
228 : * page is required to lock out concurrent vacuums on the tree.
229 : */
230 0 : root = stack->parent;
231 0 : while (root->parent)
232 : {
233 0 : ReleaseBuffer(root->buffer);
234 0 : root = root->parent;
235 : }
236 :
237 0 : Assert(root->blkno == btree->rootBlkno);
238 0 : Assert(BufferGetBlockNumber(root->buffer) == btree->rootBlkno);
239 0 : root->off = InvalidOffsetNumber;
240 :
241 0 : blkno = root->blkno;
242 0 : buffer = root->buffer;
243 0 : offset = InvalidOffsetNumber;
244 :
245 0 : ptr = (GinBtreeStack *) palloc(sizeof(GinBtreeStack));
246 :
247 : for (;;)
248 : {
249 0 : LockBuffer(buffer, GIN_EXCLUSIVE);
250 0 : page = BufferGetPage(buffer);
251 0 : if (GinPageIsLeaf(page))
252 0 : elog(ERROR, "Lost path");
253 :
254 0 : if (GinPageIsIncompleteSplit(page))
255 : {
256 0 : Assert(blkno != btree->rootBlkno);
257 0 : ptr->blkno = blkno;
258 0 : ptr->buffer = buffer;
259 :
260 : /*
261 : * parent may be wrong, but if so, the ginFinishSplit call will
262 : * recurse to call ginFindParents again to fix it.
263 : */
264 0 : ptr->parent = root;
265 0 : ptr->off = InvalidOffsetNumber;
266 :
267 0 : ginFinishSplit(btree, ptr, false, NULL);
268 : }
269 :
270 0 : leftmostBlkno = btree->getLeftMostChild(btree, page);
271 :
272 0 : while ((offset = btree->findChildPtr(btree, page, stack->blkno, InvalidOffsetNumber)) == InvalidOffsetNumber)
273 : {
274 0 : blkno = GinPageGetOpaque(page)->rightlink;
275 0 : if (blkno == InvalidBlockNumber)
276 : {
277 0 : UnlockReleaseBuffer(buffer);
278 0 : break;
279 : }
280 0 : buffer = ginStepRight(buffer, btree->index, GIN_EXCLUSIVE);
281 0 : page = BufferGetPage(buffer);
282 :
283 : /* finish any incomplete splits, as above */
284 0 : if (GinPageIsIncompleteSplit(page))
285 : {
286 0 : Assert(blkno != btree->rootBlkno);
287 0 : ptr->blkno = blkno;
288 0 : ptr->buffer = buffer;
289 0 : ptr->parent = root;
290 0 : ptr->off = InvalidOffsetNumber;
291 :
292 0 : ginFinishSplit(btree, ptr, false, NULL);
293 : }
294 : }
295 :
296 0 : if (blkno != InvalidBlockNumber)
297 : {
298 0 : ptr->blkno = blkno;
299 0 : ptr->buffer = buffer;
300 0 : ptr->parent = root; /* it may be wrong, but in next call we will
301 : * correct */
302 0 : ptr->off = offset;
303 0 : stack->parent = ptr;
304 0 : return;
305 : }
306 :
307 : /* Descend down to next level */
308 0 : blkno = leftmostBlkno;
309 0 : buffer = ReadBuffer(btree->index, blkno);
310 0 : }
311 : }
312 :
313 : /*
314 : * Insert a new item to a page.
315 : *
316 : * Returns true if the insertion was finished. On false, the page was split and
317 : * the parent needs to be updated. (A root split returns true as it doesn't
318 : * need any further action by the caller to complete.)
319 : *
320 : * When inserting a downlink to an internal page, 'childbuf' contains the
321 : * child page that was split. Its GIN_INCOMPLETE_SPLIT flag will be cleared
322 : * atomically with the insert. Also, the existing item at offset stack->off
323 : * in the target page is updated to point to updateblkno.
324 : *
325 : * stack->buffer is locked on entry, and is kept locked.
326 : * Likewise for childbuf, if given.
327 : */
328 : static bool
329 41694 : ginPlaceToPage(GinBtree btree, GinBtreeStack *stack,
330 : void *insertdata, BlockNumber updateblkno,
331 : Buffer childbuf, GinStatsData *buildStats)
332 : {
333 41694 : Page page = BufferGetPage(stack->buffer);
334 : bool result;
335 : GinPlaceToPageRC rc;
336 41694 : uint16 xlflags = 0;
337 41694 : Page childpage = NULL;
338 41694 : Page newlpage = NULL,
339 41694 : newrpage = NULL;
340 41694 : void *ptp_workspace = NULL;
341 : MemoryContext tmpCxt;
342 : MemoryContext oldCxt;
343 :
344 : /*
345 : * We do all the work of this function and its subfunctions in a temporary
346 : * memory context. This avoids leakages and simplifies APIs, since some
347 : * subfunctions allocate storage that has to survive until we've finished
348 : * the WAL insertion.
349 : */
350 41694 : tmpCxt = AllocSetContextCreate(CurrentMemoryContext,
351 : "ginPlaceToPage temporary context",
352 : ALLOCSET_DEFAULT_SIZES);
353 41694 : oldCxt = MemoryContextSwitchTo(tmpCxt);
354 :
355 41694 : if (GinPageIsData(page))
356 3340 : xlflags |= GIN_INSERT_ISDATA;
357 41694 : if (GinPageIsLeaf(page))
358 : {
359 41487 : xlflags |= GIN_INSERT_ISLEAF;
360 41487 : Assert(!BufferIsValid(childbuf));
361 41487 : Assert(updateblkno == InvalidBlockNumber);
362 : }
363 : else
364 : {
365 207 : Assert(BufferIsValid(childbuf));
366 207 : Assert(updateblkno != InvalidBlockNumber);
367 207 : childpage = BufferGetPage(childbuf);
368 : }
369 :
370 : /*
371 : * See if the incoming tuple will fit on the page. beginPlaceToPage will
372 : * decide if the page needs to be split, and will compute the split
373 : * contents if so. See comments for beginPlaceToPage and execPlaceToPage
374 : * functions for more details of the API here.
375 : */
376 41694 : rc = btree->beginPlaceToPage(btree, stack->buffer, stack,
377 : insertdata, updateblkno,
378 : &ptp_workspace,
379 : &newlpage, &newrpage);
380 :
381 41694 : if (rc == GPTP_NO_WORK)
382 : {
383 : /* Nothing to do */
384 0 : result = true;
385 : }
386 41694 : else if (rc == GPTP_INSERT)
387 : {
388 : /* It will fit, perform the insertion */
389 41478 : START_CRIT_SECTION();
390 :
391 41478 : if (RelationNeedsWAL(btree->index))
392 : {
393 41461 : XLogBeginInsert();
394 41461 : XLogRegisterBuffer(0, stack->buffer, REGBUF_STANDARD);
395 41461 : if (BufferIsValid(childbuf))
396 207 : XLogRegisterBuffer(1, childbuf, REGBUF_STANDARD);
397 : }
398 :
399 : /* Perform the page update, and register any extra WAL data */
400 41478 : btree->execPlaceToPage(btree, stack->buffer, stack,
401 : insertdata, updateblkno, ptp_workspace);
402 :
403 41478 : MarkBufferDirty(stack->buffer);
404 :
405 : /* An insert to an internal page finishes the split of the child. */
406 41478 : if (BufferIsValid(childbuf))
407 : {
408 207 : GinPageGetOpaque(childpage)->flags &= ~GIN_INCOMPLETE_SPLIT;
409 207 : MarkBufferDirty(childbuf);
410 : }
411 :
412 41478 : if (RelationNeedsWAL(btree->index))
413 : {
414 : XLogRecPtr recptr;
415 : ginxlogInsert xlrec;
416 : BlockIdData childblknos[2];
417 :
418 41461 : xlrec.flags = xlflags;
419 :
420 41461 : XLogRegisterData((char *) &xlrec, sizeof(ginxlogInsert));
421 :
422 : /*
423 : * Log information about child if this was an insertion of a
424 : * downlink.
425 : */
426 41461 : if (BufferIsValid(childbuf))
427 : {
428 207 : BlockIdSet(&childblknos[0], BufferGetBlockNumber(childbuf));
429 207 : BlockIdSet(&childblknos[1], GinPageGetOpaque(childpage)->rightlink);
430 207 : XLogRegisterData((char *) childblknos,
431 : sizeof(BlockIdData) * 2);
432 : }
433 :
434 41461 : recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_INSERT);
435 41461 : PageSetLSN(page, recptr);
436 41461 : if (BufferIsValid(childbuf))
437 207 : PageSetLSN(childpage, recptr);
438 : }
439 :
440 41478 : END_CRIT_SECTION();
441 :
442 : /* Insertion is complete. */
443 41478 : result = true;
444 : }
445 216 : else if (rc == GPTP_SPLIT)
446 : {
447 : /*
448 : * Didn't fit, need to split. The split has been computed in newlpage
449 : * and newrpage, which are pointers to palloc'd pages, not associated
450 : * with buffers. stack->buffer is not touched yet.
451 : */
452 : Buffer rbuffer;
453 : BlockNumber savedRightLink;
454 : ginxlogSplit data;
455 216 : Buffer lbuffer = InvalidBuffer;
456 216 : Page newrootpg = NULL;
457 :
458 : /* Get a new index page to become the right page */
459 216 : rbuffer = GinNewBuffer(btree->index);
460 :
461 : /* During index build, count the new page */
462 216 : if (buildStats)
463 : {
464 94 : if (btree->isData)
465 1 : buildStats->nDataPages++;
466 : else
467 93 : buildStats->nEntryPages++;
468 : }
469 :
470 216 : savedRightLink = GinPageGetOpaque(page)->rightlink;
471 :
472 : /* Begin setting up WAL record */
473 216 : data.node = btree->index->rd_node;
474 216 : data.flags = xlflags;
475 216 : if (BufferIsValid(childbuf))
476 : {
477 0 : data.leftChildBlkno = BufferGetBlockNumber(childbuf);
478 0 : data.rightChildBlkno = GinPageGetOpaque(childpage)->rightlink;
479 : }
480 : else
481 216 : data.leftChildBlkno = data.rightChildBlkno = InvalidBlockNumber;
482 :
483 216 : if (stack->parent == NULL)
484 : {
485 : /*
486 : * splitting the root, so we need to allocate new left page and
487 : * place pointers to left and right page on root page.
488 : */
489 9 : lbuffer = GinNewBuffer(btree->index);
490 :
491 : /* During index build, count the new left page */
492 9 : if (buildStats)
493 : {
494 6 : if (btree->isData)
495 1 : buildStats->nDataPages++;
496 : else
497 5 : buildStats->nEntryPages++;
498 : }
499 :
500 9 : data.rrlink = InvalidBlockNumber;
501 9 : data.flags |= GIN_SPLIT_ROOT;
502 :
503 9 : GinPageGetOpaque(newrpage)->rightlink = InvalidBlockNumber;
504 9 : GinPageGetOpaque(newlpage)->rightlink = BufferGetBlockNumber(rbuffer);
505 :
506 : /*
507 : * Construct a new root page containing downlinks to the new left
508 : * and right pages. (Do this in a temporary copy rather than
509 : * overwriting the original page directly, since we're not in the
510 : * critical section yet.)
511 : */
512 9 : newrootpg = PageGetTempPage(newrpage);
513 9 : GinInitPage(newrootpg, GinPageGetOpaque(newlpage)->flags & ~(GIN_LEAF | GIN_COMPRESSED), BLCKSZ);
514 :
515 9 : btree->fillRoot(btree, newrootpg,
516 : BufferGetBlockNumber(lbuffer), newlpage,
517 : BufferGetBlockNumber(rbuffer), newrpage);
518 : }
519 : else
520 : {
521 : /* splitting a non-root page */
522 207 : data.rrlink = savedRightLink;
523 :
524 207 : GinPageGetOpaque(newrpage)->rightlink = savedRightLink;
525 207 : GinPageGetOpaque(newlpage)->flags |= GIN_INCOMPLETE_SPLIT;
526 207 : GinPageGetOpaque(newlpage)->rightlink = BufferGetBlockNumber(rbuffer);
527 : }
528 :
529 : /*
530 : * OK, we have the new contents of the left page in a temporary copy
531 : * now (newlpage), and likewise for the new contents of the
532 : * newly-allocated right block. The original page is still unchanged.
533 : *
534 : * If this is a root split, we also have a temporary page containing
535 : * the new contents of the root.
536 : */
537 :
538 216 : START_CRIT_SECTION();
539 :
540 216 : MarkBufferDirty(rbuffer);
541 216 : MarkBufferDirty(stack->buffer);
542 :
543 : /*
544 : * Restore the temporary copies over the real buffers.
545 : */
546 216 : if (stack->parent == NULL)
547 : {
548 : /* Splitting the root, three pages to update */
549 9 : MarkBufferDirty(lbuffer);
550 9 : memcpy(page, newrootpg, BLCKSZ);
551 9 : memcpy(BufferGetPage(lbuffer), newlpage, BLCKSZ);
552 9 : memcpy(BufferGetPage(rbuffer), newrpage, BLCKSZ);
553 : }
554 : else
555 : {
556 : /* Normal split, only two pages to update */
557 207 : memcpy(page, newlpage, BLCKSZ);
558 207 : memcpy(BufferGetPage(rbuffer), newrpage, BLCKSZ);
559 : }
560 :
561 : /* We also clear childbuf's INCOMPLETE_SPLIT flag, if passed */
562 216 : if (BufferIsValid(childbuf))
563 : {
564 0 : GinPageGetOpaque(childpage)->flags &= ~GIN_INCOMPLETE_SPLIT;
565 0 : MarkBufferDirty(childbuf);
566 : }
567 :
568 : /* write WAL record */
569 216 : if (RelationNeedsWAL(btree->index))
570 : {
571 : XLogRecPtr recptr;
572 :
573 216 : XLogBeginInsert();
574 :
575 : /*
576 : * We just take full page images of all the split pages. Splits
577 : * are uncommon enough that it's not worth complicating the code
578 : * to be more efficient.
579 : */
580 216 : if (stack->parent == NULL)
581 : {
582 9 : XLogRegisterBuffer(0, lbuffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
583 9 : XLogRegisterBuffer(1, rbuffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
584 9 : XLogRegisterBuffer(2, stack->buffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
585 : }
586 : else
587 : {
588 207 : XLogRegisterBuffer(0, stack->buffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
589 207 : XLogRegisterBuffer(1, rbuffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
590 : }
591 216 : if (BufferIsValid(childbuf))
592 0 : XLogRegisterBuffer(3, childbuf, REGBUF_STANDARD);
593 :
594 216 : XLogRegisterData((char *) &data, sizeof(ginxlogSplit));
595 :
596 216 : recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_SPLIT);
597 :
598 216 : PageSetLSN(page, recptr);
599 216 : PageSetLSN(BufferGetPage(rbuffer), recptr);
600 216 : if (stack->parent == NULL)
601 9 : PageSetLSN(BufferGetPage(lbuffer), recptr);
602 216 : if (BufferIsValid(childbuf))
603 0 : PageSetLSN(childpage, recptr);
604 : }
605 216 : END_CRIT_SECTION();
606 :
607 : /*
608 : * We can release the locks/pins on the new pages now, but keep
609 : * stack->buffer locked. childbuf doesn't get unlocked either.
610 : */
611 216 : UnlockReleaseBuffer(rbuffer);
612 216 : if (stack->parent == NULL)
613 9 : UnlockReleaseBuffer(lbuffer);
614 :
615 : /*
616 : * If we split the root, we're done. Otherwise the split is not
617 : * complete until the downlink for the new page has been inserted to
618 : * the parent.
619 : */
620 216 : result = (stack->parent == NULL);
621 : }
622 : else
623 : {
624 0 : elog(ERROR, "invalid return code from GIN placeToPage method: %d", rc);
625 : result = false; /* keep compiler quiet */
626 : }
627 :
628 : /* Clean up temp context */
629 41694 : MemoryContextSwitchTo(oldCxt);
630 41694 : MemoryContextDelete(tmpCxt);
631 :
632 41694 : return result;
633 : }
634 :
635 : /*
636 : * Finish a split by inserting the downlink for the new page to parent.
637 : *
638 : * On entry, stack->buffer is exclusively locked.
639 : *
640 : * If freestack is true, all the buffers are released and unlocked as we
641 : * crawl up the tree, and 'stack' is freed. Otherwise stack->buffer is kept
642 : * locked, and stack is unmodified, except for possibly moving right to find
643 : * the correct parent of page.
644 : */
645 : static void
646 207 : ginFinishSplit(GinBtree btree, GinBtreeStack *stack, bool freestack,
647 : GinStatsData *buildStats)
648 : {
649 : Page page;
650 : bool done;
651 207 : bool first = true;
652 :
653 : /*
654 : * freestack == false when we encounter an incompletely split page during
655 : * a scan, while freestack == true is used in the normal scenario that a
656 : * split is finished right after the initial insert.
657 : */
658 207 : if (!freestack)
659 0 : elog(DEBUG1, "finishing incomplete split of block %u in gin index \"%s\"",
660 : stack->blkno, RelationGetRelationName(btree->index));
661 :
662 : /* this loop crawls up the stack until the insertion is complete */
663 : do
664 : {
665 207 : GinBtreeStack *parent = stack->parent;
666 : void *insertdata;
667 : BlockNumber updateblkno;
668 :
669 : /* search parent to lock */
670 207 : LockBuffer(parent->buffer, GIN_EXCLUSIVE);
671 :
672 : /*
673 : * If the parent page was incompletely split, finish that split first,
674 : * then continue with the current one.
675 : *
676 : * Note: we have to finish *all* incomplete splits we encounter, even
677 : * if we have to move right. Otherwise we might choose as the target a
678 : * page that has no downlink in the parent, and splitting it further
679 : * would fail.
680 : */
681 207 : if (GinPageIsIncompleteSplit(BufferGetPage(parent->buffer)))
682 0 : ginFinishSplit(btree, parent, false, buildStats);
683 :
684 : /* move right if it's needed */
685 207 : page = BufferGetPage(parent->buffer);
686 414 : while ((parent->off = btree->findChildPtr(btree, page, stack->blkno, parent->off)) == InvalidOffsetNumber)
687 : {
688 0 : if (GinPageRightMost(page))
689 : {
690 : /*
691 : * rightmost page, but we don't find parent, we should use
692 : * plain search...
693 : */
694 0 : LockBuffer(parent->buffer, GIN_UNLOCK);
695 0 : ginFindParents(btree, stack);
696 0 : parent = stack->parent;
697 0 : Assert(parent != NULL);
698 0 : break;
699 : }
700 :
701 0 : parent->buffer = ginStepRight(parent->buffer, btree->index, GIN_EXCLUSIVE);
702 0 : parent->blkno = BufferGetBlockNumber(parent->buffer);
703 0 : page = BufferGetPage(parent->buffer);
704 :
705 0 : if (GinPageIsIncompleteSplit(BufferGetPage(parent->buffer)))
706 0 : ginFinishSplit(btree, parent, false, buildStats);
707 : }
708 :
709 : /* insert the downlink */
710 207 : insertdata = btree->prepareDownlink(btree, stack->buffer);
711 207 : updateblkno = GinPageGetOpaque(BufferGetPage(stack->buffer))->rightlink;
712 207 : done = ginPlaceToPage(btree, parent,
713 : insertdata, updateblkno,
714 : stack->buffer, buildStats);
715 207 : pfree(insertdata);
716 :
717 : /*
718 : * If the caller requested to free the stack, unlock and release the
719 : * child buffer now. Otherwise keep it pinned and locked, but if we
720 : * have to recurse up the tree, we can unlock the upper pages, only
721 : * keeping the page at the bottom of the stack locked.
722 : */
723 207 : if (!first || freestack)
724 207 : LockBuffer(stack->buffer, GIN_UNLOCK);
725 207 : if (freestack)
726 : {
727 207 : ReleaseBuffer(stack->buffer);
728 207 : pfree(stack);
729 : }
730 207 : stack = parent;
731 :
732 207 : first = false;
733 207 : } while (!done);
734 :
735 : /* unlock the parent */
736 207 : LockBuffer(stack->buffer, GIN_UNLOCK);
737 :
738 207 : if (freestack)
739 207 : freeGinBtreeStack(stack);
740 207 : }
741 :
742 : /*
743 : * Insert a value to tree described by stack.
744 : *
745 : * The value to be inserted is given in 'insertdata'. Its format depends
746 : * on whether this is an entry or data tree, ginInsertValue just passes it
747 : * through to the tree-specific callback function.
748 : *
749 : * During an index build, buildStats is non-null and the counters it contains
750 : * are incremented as needed.
751 : *
752 : * NB: the passed-in stack is freed, as though by freeGinBtreeStack.
753 : */
754 : void
755 41487 : ginInsertValue(GinBtree btree, GinBtreeStack *stack, void *insertdata,
756 : GinStatsData *buildStats)
757 : {
758 : bool done;
759 :
760 : /* If the leaf page was incompletely split, finish the split first */
761 41487 : if (GinPageIsIncompleteSplit(BufferGetPage(stack->buffer)))
762 0 : ginFinishSplit(btree, stack, false, buildStats);
763 :
764 41487 : done = ginPlaceToPage(btree, stack,
765 : insertdata, InvalidBlockNumber,
766 : InvalidBuffer, buildStats);
767 41487 : if (done)
768 : {
769 41280 : LockBuffer(stack->buffer, GIN_UNLOCK);
770 41280 : freeGinBtreeStack(stack);
771 : }
772 : else
773 207 : ginFinishSplit(btree, stack, true, buildStats);
774 41487 : }
|
