Re: Gin page deletion bug

On 07.11.2013 22:49, Heikki Linnakangas wrote:
> Gin page deletion fails to take into account that there might be a
> search in-flight to the page that is deleted. If the page is reused for
> something else, the search can get very confused.
>
> ...
>
> The regular b-tree code solves this by stamping deleted pages with the
> current XID, and only allowing them to be reused once that XID becomes
> old enough (< RecentGlobalXmin). Another approach might be to grab a
> cleanup-strength lock on the left and parent pages when deleting a page,
> and requiring search to keep the pin on the page its coming from, until
> it has locked the next page.

I came up with the attached fix. In a nutshell, when walking along a
right-link, the new page is locked before releasing the lock on the old
one. Also, never delete the leftmost branch of a posting tree. I believe
these changes are sufficient to fix the problem, because of the way the
posting tree is searched:

All searches on a posting tree are "full searches", scanning the whole
tree from left to right. Insertions do seek to the middle of the tree,
but they are locked out during vacuum by holding a cleanup lock on the
posting tree root (even without this patch). Thanks to this property, a
search cannot step on a page that's being deleted by following a
downlink, if we refrain from deleting the leftmost page on a level, as
searches only descend down the leftmost branch.

It would be nice to improve that in master - holding an exclusive lock
on the root page is pretty horrible - but this is a nice back-patchable
patch. I'm not worried about the loss of concurrency because we now have
to hold the lock on previous page when stepping to next page. In
searches, it's only a share-lock, and in insertions, it's very rare that
you have to step right.

The patch also adds some sanity checks to stepping right: the next page
should be of the same type as the current page, e.g stepping right
should not go from leaf to non-leaf or vice versa.

- Heikki