Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitac4ab97

Browse files
committed
Fix race condition in GIN posting tree page deletion.
If a page is deleted, and reused for something else, just as a search isfollowing a rightlink to it from its left sibling, the search would continuescanning whatever the new contents of the page are. That could lead toincorrect query results, or even something more curious if the page isreused for a different kind of a page.To fix, modify the search algorithm to lock the next page before releasingthe previous one, and refrain from deleting pages from the leftmost branchof the tree.Add a new Concurrency section to the README, explaining why this works.There is a lot more one could say about concurrency in GIN, but that's foranother patch.Backpatch to all supported versions.
1 parent636b868 commitac4ab97

File tree

5 files changed

+121
-59
lines changed

5 files changed

+121
-59
lines changed

‎src/backend/access/gin/README

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -210,6 +210,56 @@ fit on one pending-list page must have those pages to itself, even if this
210210
results in wasting much of the space on the preceding page and the last
211211
page for the tuple.)
212212

213+
Concurrency
214+
-----------
215+
216+
The entry tree and each posting tree is a B-tree, with right-links connecting
217+
sibling pages at the same level. This is the same structure that is used in
218+
the regular B-tree indexam (invented by Lehman & Yao), but we don't support
219+
scanning a GIN trees backwards, so we don't need left-links.
220+
221+
To avoid deadlocks, B-tree pages must always be locked in the same order:
222+
left to right, and bottom to top. When searching, the tree is traversed from
223+
top to bottom, so the lock on the parent page must be released before
224+
descending to the next level. Concurrent page splits move the keyspace to
225+
right, so after following a downlink, the page actually containing the key
226+
we're looking for might be somewhere to the right of the page we landed on.
227+
In that case, we follow the right-links until we find the page we're looking
228+
for.
229+
230+
To delete a page, the page's left sibling, the target page, and its parent,
231+
are locked in that order, and the page is marked as deleted. However, a
232+
concurrent search might already have read a pointer to the page, and might be
233+
just about to follow it. A page can be reached via the right-link of its left
234+
sibling, or via its downlink in the parent.
235+
236+
To prevent a backend from reaching a deleted page via a right-link, when
237+
following a right-link the lock on the previous page is not released until
238+
the lock on next page has been acquired.
239+
240+
The downlink is more tricky. A search descending the tree must release the
241+
lock on the parent page before locking the child, or it could deadlock with
242+
a concurrent split of the child page; a page split locks the parent, while
243+
already holding a lock on the child page. However, posting trees are only
244+
fully searched from left to right, starting from the leftmost leaf. (The
245+
tree-structure is only needed by insertions, to quickly find the correct
246+
insert location). So as long as we don't delete the leftmost page on each
247+
level, a search can never follow a downlink to page that's about to be
248+
deleted.
249+
250+
The previous paragraph's reasoning only applies to searches, and only to
251+
posting trees. To protect from inserters following a downlink to a deleted
252+
page, vacuum simply locks out all concurrent insertions to the posting tree,
253+
by holding a super-exclusive lock on the posting tree root. Inserters hold a
254+
pin on the root page, but searches do not, so while new searches cannot begin
255+
while root page is locked, any already-in-progress scans can continue
256+
concurrently with vacuum. In the entry tree, we never delete pages.
257+
258+
(This is quite different from the mechanism the btree indexam uses to make
259+
page-deletions safe; it stamps the deleted pages with an XID and keeps the
260+
deleted pages around with the right-link intact until all concurrent scans
261+
have finished.)
262+
213263
Limitations
214264
-----------
215265

‎src/backend/access/gin/ginbtree.c

Lines changed: 42 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -112,10 +112,8 @@ ginFindLeafPage(GinBtree btree, GinBtreeStack *stack)
112112
/* rightmost page */
113113
break;
114114

115+
stack->buffer=ginStepRight(stack->buffer,btree->index,access);
115116
stack->blkno=rightlink;
116-
LockBuffer(stack->buffer,GIN_UNLOCK);
117-
stack->buffer=ReleaseAndReadBuffer(stack->buffer,btree->index,stack->blkno);
118-
LockBuffer(stack->buffer,access);
119117
page=BufferGetPage(stack->buffer);
120118
}
121119

@@ -148,6 +146,41 @@ ginFindLeafPage(GinBtree btree, GinBtreeStack *stack)
148146
}
149147
}
150148

149+
/*
150+
* Step right from current page.
151+
*
152+
* The next page is locked first, before releasing the current page. This is
153+
* crucial to protect from concurrent page deletion (see comment in
154+
* ginDeletePage).
155+
*/
156+
Buffer
157+
ginStepRight(Bufferbuffer,Relationindex,intlockmode)
158+
{
159+
Buffernextbuffer;
160+
Pagepage=BufferGetPage(buffer);
161+
boolisLeaf=GinPageIsLeaf(page);
162+
boolisData=GinPageIsData(page);
163+
BlockNumberblkno=GinPageGetOpaque(page)->rightlink;
164+
165+
nextbuffer=ReadBuffer(index,blkno);
166+
LockBuffer(nextbuffer,lockmode);
167+
UnlockReleaseBuffer(buffer);
168+
169+
/* Sanity check that the page we stepped to is of similar kind. */
170+
page=BufferGetPage(nextbuffer);
171+
if (isLeaf!=GinPageIsLeaf(page)||isData!=GinPageIsData(page))
172+
elog(ERROR,"right sibling of GIN page is of different type");
173+
174+
/*
175+
* Given the proper lock sequence above, we should never land on a
176+
* deleted page.
177+
*/
178+
if (GinPageIsDeleted(page))
179+
elog(ERROR,"right sibling of GIN page was deleted");
180+
181+
returnnextbuffer;
182+
}
183+
151184
void
152185
freeGinBtreeStack(GinBtreeStack*stack)
153186
{
@@ -235,12 +268,12 @@ ginFindParents(GinBtree btree, GinBtreeStack *stack,
235268
while ((offset=btree->findChildPtr(btree,page,stack->blkno,InvalidOffsetNumber))==InvalidOffsetNumber)
236269
{
237270
blkno=GinPageGetOpaque(page)->rightlink;
238-
LockBuffer(buffer,GIN_UNLOCK);
239-
ReleaseBuffer(buffer);
240271
if (blkno==InvalidBlockNumber)
272+
{
273+
UnlockReleaseBuffer(buffer);
241274
break;
242-
buffer=ReadBuffer(btree->index,blkno);
243-
LockBuffer(buffer,GIN_EXCLUSIVE);
275+
}
276+
buffer=ginStepRight(buffer,btree->index,GIN_EXCLUSIVE);
244277
page=BufferGetPage(buffer);
245278
}
246279

@@ -444,23 +477,21 @@ ginInsertValue(GinBtree btree, GinBtreeStack *stack, GinStatsData *buildStats)
444477
{
445478
BlockNumberrightlink=GinPageGetOpaque(page)->rightlink;
446479

447-
LockBuffer(parent->buffer,GIN_UNLOCK);
448-
449480
if (rightlink==InvalidBlockNumber)
450481
{
451482
/*
452483
* rightmost page, but we don't find parent, we should use
453484
* plain search...
454485
*/
486+
LockBuffer(parent->buffer,GIN_UNLOCK);
455487
ginFindParents(btree,stack,rootBlkno);
456488
parent=stack->parent;
457489
Assert(parent!=NULL);
458490
break;
459491
}
460492

493+
parent->buffer=ginStepRight(parent->buffer,btree->index,GIN_EXCLUSIVE);
461494
parent->blkno=rightlink;
462-
parent->buffer=ReleaseAndReadBuffer(parent->buffer,btree->index,parent->blkno);
463-
LockBuffer(parent->buffer,GIN_EXCLUSIVE);
464495
page=BufferGetPage(parent->buffer);
465496
}
466497

‎src/backend/access/gin/ginget.c

Lines changed: 8 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -105,16 +105,11 @@ moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack)
105105
/*
106106
* We scanned the whole page, so we should take right page
107107
*/
108-
stack->blkno=GinPageGetOpaque(page)->rightlink;
109-
110108
if (GinPageRightMost(page))
111109
return false;/* no more pages */
112110

113-
LockBuffer(stack->buffer,GIN_UNLOCK);
114-
stack->buffer=ReleaseAndReadBuffer(stack->buffer,
115-
btree->index,
116-
stack->blkno);
117-
LockBuffer(stack->buffer,GIN_SHARE);
111+
stack->buffer=ginStepRight(stack->buffer,btree->index,GIN_SHARE);
112+
stack->blkno=BufferGetBlockNumber(stack->buffer);
118113
stack->off=FirstOffsetNumber;
119114
}
120115

@@ -132,7 +127,6 @@ scanPostingTree(Relation index, GinScanEntry scanEntry,
132127
GinPostingTreeScan*gdi;
133128
Bufferbuffer;
134129
Pagepage;
135-
BlockNumberblkno;
136130

137131
/* Descend to the leftmost leaf page */
138132
gdi=ginPrepareScanPostingTree(index,rootPostingTree, TRUE);
@@ -162,10 +156,7 @@ scanPostingTree(Relation index, GinScanEntry scanEntry,
162156
if (GinPageRightMost(page))
163157
break;/* no more pages */
164158

165-
blkno=GinPageGetOpaque(page)->rightlink;
166-
LockBuffer(buffer,GIN_UNLOCK);
167-
buffer=ReleaseAndReadBuffer(buffer,index,blkno);
168-
LockBuffer(buffer,GIN_SHARE);
159+
buffer=ginStepRight(buffer,index,GIN_SHARE);
169160
}
170161

171162
UnlockReleaseBuffer(buffer);
@@ -543,7 +534,6 @@ static void
543534
entryGetNextItem(GinState*ginstate,GinScanEntryentry)
544535
{
545536
Pagepage;
546-
BlockNumberblkno;
547537

548538
for (;;)
549539
{
@@ -561,23 +551,18 @@ entryGetNextItem(GinState *ginstate, GinScanEntry entry)
561551
* It's needed to go by right link. During that we should refind
562552
* first ItemPointer greater that stored
563553
*/
564-
565-
blkno=GinPageGetOpaque(page)->rightlink;
566-
567-
LockBuffer(entry->buffer,GIN_UNLOCK);
568-
if (blkno==InvalidBlockNumber)
554+
if (GinPageRightMost(page))
569555
{
570-
ReleaseBuffer(entry->buffer);
556+
UnlockReleaseBuffer(entry->buffer);
571557
ItemPointerSetInvalid(&entry->curItem);
572558
entry->buffer=InvalidBuffer;
573559
entry->isFinished= TRUE;
574560
return;
575561
}
576562

577-
entry->buffer=ReleaseAndReadBuffer(entry->buffer,
578-
ginstate->index,
579-
blkno);
580-
LockBuffer(entry->buffer,GIN_SHARE);
563+
entry->buffer=ginStepRight(entry->buffer,
564+
ginstate->index,
565+
GIN_SHARE);
581566
page=BufferGetPage(entry->buffer);
582567

583568
entry->offset=InvalidOffsetNumber;

‎src/backend/access/gin/ginvacuum.c

Lines changed: 20 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -240,6 +240,9 @@ ginVacuumPostingTreeLeaves(GinVacuumState *gvs, BlockNumber blkno, bool isRoot,
240240
returnhasVoidPage;
241241
}
242242

243+
/*
244+
* Delete a posting tree page.
245+
*/
243246
staticvoid
244247
ginDeletePage(GinVacuumState*gvs,BlockNumberdeleteBlkno,BlockNumberleftBlkno,
245248
BlockNumberparentBlkno,OffsetNumbermyoff,boolisParentRoot)
@@ -249,39 +252,35 @@ ginDeletePage(GinVacuumState *gvs, BlockNumber deleteBlkno, BlockNumber leftBlkn
249252
BufferpBuffer;
250253
Pagepage,
251254
parentPage;
255+
BlockNumberrightlink;
252256

257+
/*
258+
* Lock the pages in the same order as an insertion would, to avoid
259+
* deadlocks: left, then right, then parent.
260+
*/
261+
lBuffer=ReadBufferExtended(gvs->index,MAIN_FORKNUM,leftBlkno,
262+
RBM_NORMAL,gvs->strategy);
253263
dBuffer=ReadBufferExtended(gvs->index,MAIN_FORKNUM,deleteBlkno,
254264
RBM_NORMAL,gvs->strategy);
255-
256-
if (leftBlkno!=InvalidBlockNumber)
257-
lBuffer=ReadBufferExtended(gvs->index,MAIN_FORKNUM,leftBlkno,
258-
RBM_NORMAL,gvs->strategy);
259-
else
260-
lBuffer=InvalidBuffer;
261-
262265
pBuffer=ReadBufferExtended(gvs->index,MAIN_FORKNUM,parentBlkno,
263266
RBM_NORMAL,gvs->strategy);
264267

268+
LockBuffer(lBuffer,GIN_EXCLUSIVE);
265269
LockBuffer(dBuffer,GIN_EXCLUSIVE);
266270
if (!isParentRoot)/* parent is already locked by
267271
* LockBufferForCleanup() */
268272
LockBuffer(pBuffer,GIN_EXCLUSIVE);
269-
if (leftBlkno!=InvalidBlockNumber)
270-
LockBuffer(lBuffer,GIN_EXCLUSIVE);
271273

272274
START_CRIT_SECTION();
273275

274-
if (leftBlkno!=InvalidBlockNumber)
275-
{
276-
BlockNumberrightlink;
276+
/* Unlink the page by changing left sibling's rightlink */
277+
page=BufferGetPage(dBuffer);
278+
rightlink=GinPageGetOpaque(page)->rightlink;
277279

278-
page=BufferGetPage(dBuffer);
279-
rightlink=GinPageGetOpaque(page)->rightlink;
280-
281-
page=BufferGetPage(lBuffer);
282-
GinPageGetOpaque(page)->rightlink=rightlink;
283-
}
280+
page=BufferGetPage(lBuffer);
281+
GinPageGetOpaque(page)->rightlink=rightlink;
284282

283+
/* Delete downlink from parent */
285284
parentPage=BufferGetPage(pBuffer);
286285
#ifdefUSE_ASSERT_CHECKING
287286
do
@@ -363,10 +362,7 @@ ginDeletePage(GinVacuumState *gvs, BlockNumber deleteBlkno, BlockNumber leftBlkn
363362
if (!isParentRoot)
364363
LockBuffer(pBuffer,GIN_UNLOCK);
365364
ReleaseBuffer(pBuffer);
366-
367-
if (leftBlkno!=InvalidBlockNumber)
368-
UnlockReleaseBuffer(lBuffer);
369-
365+
UnlockReleaseBuffer(lBuffer);
370366
UnlockReleaseBuffer(dBuffer);
371367

372368
END_CRIT_SECTION();
@@ -435,10 +431,9 @@ ginScanToDelete(GinVacuumState *gvs, BlockNumber blkno, bool isRoot,
435431

436432
if (GinPageGetOpaque(page)->maxoff<FirstOffsetNumber)
437433
{
438-
/* thepage is empty */
439-
if (!(me->leftBlkno==InvalidBlockNumber&&GinPageRightMost(page)))
434+
/*we never deletetheleft- or rightmost branch */
435+
if (me->leftBlkno!=InvalidBlockNumber&&!GinPageRightMost(page))
440436
{
441-
/* we never delete right most branch */
442437
Assert(!isRoot);
443438
ginDeletePage(gvs,blkno,me->leftBlkno,me->parent->blkno,myoff,me->parent->isRoot);
444439
meDelete= TRUE;

‎src/include/access/gin_private.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -516,6 +516,7 @@ typedef struct GinBtreeData
516516

517517
externGinBtreeStack*ginPrepareFindLeafPage(GinBtreebtree,BlockNumberblkno);
518518
externGinBtreeStack*ginFindLeafPage(GinBtreebtree,GinBtreeStack*stack);
519+
externBufferginStepRight(Bufferbuffer,Relationindex,intlockmode);
519520
externvoidfreeGinBtreeStack(GinBtreeStack*stack);
520521
externvoidginInsertValue(GinBtreebtree,GinBtreeStack*stack,
521522
GinStatsData*buildStats);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp