Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * nbtpage.c
4 : : * BTree-specific page management code for the Postgres btree access
5 : : * method.
6 : : *
7 : : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
8 : : * Portions Copyright (c) 1994, Regents of the University of California
9 : : *
10 : : *
11 : : * IDENTIFICATION
12 : : * src/backend/access/nbtree/nbtpage.c
13 : : *
14 : : * NOTES
15 : : * Postgres btree pages look like ordinary relation pages. The opaque
16 : : * data at high addresses includes pointers to left and right siblings
17 : : * and flag data describing page state. The first page in a btree, page
18 : : * zero, is special -- it stores meta-information describing the tree.
19 : : * Pages one and higher store the actual tree data.
20 : : *
21 : : *-------------------------------------------------------------------------
22 : : */
23 : : #include "postgres.h"
24 : :
25 : : #include "access/nbtree.h"
26 : : #include "access/nbtxlog.h"
27 : : #include "access/tableam.h"
28 : : #include "access/transam.h"
29 : : #include "access/xlog.h"
30 : : #include "access/xloginsert.h"
31 : : #include "common/int.h"
32 : : #include "miscadmin.h"
33 : : #include "storage/indexfsm.h"
34 : : #include "storage/predicate.h"
35 : : #include "storage/procarray.h"
36 : : #include "utils/memdebug.h"
37 : : #include "utils/memutils.h"
38 : : #include "utils/snapmgr.h"
39 : :
40 : : static BTMetaPageData *_bt_getmeta(Relation rel, Buffer metabuf);
41 : : static void _bt_delitems_delete(Relation rel, Buffer buf,
42 : : TransactionId snapshotConflictHorizon,
43 : : bool isCatalogRel,
44 : : OffsetNumber *deletable, int ndeletable,
45 : : BTVacuumPosting *updatable, int nupdatable);
46 : : static char *_bt_delitems_update(BTVacuumPosting *updatable, int nupdatable,
47 : : OffsetNumber *updatedoffsets,
48 : : Size *updatedbuflen, bool needswal);
49 : : static bool _bt_mark_page_halfdead(Relation rel, Relation heaprel,
50 : : Buffer leafbuf, BTStack stack);
51 : : static bool _bt_unlink_halfdead_page(Relation rel, Buffer leafbuf,
52 : : BlockNumber scanblkno,
53 : : bool *rightsib_empty,
54 : : BTVacState *vstate);
55 : : static bool _bt_lock_subtree_parent(Relation rel, Relation heaprel,
56 : : BlockNumber child, BTStack stack,
57 : : Buffer *subtreeparent, OffsetNumber *poffset,
58 : : BlockNumber *topparent,
59 : : BlockNumber *topparentrightsib);
60 : : static void _bt_pendingfsm_add(BTVacState *vstate, BlockNumber target,
61 : : FullTransactionId safexid);
62 : :
63 : : /*
64 : : * _bt_initmetapage() -- Fill a page buffer with a correct metapage image
65 : : */
66 : : void
2071 pg@bowt.ie 67 :CBC 25311 : _bt_initmetapage(Page page, BlockNumber rootbknum, uint32 level,
68 : : bool allequalimage)
69 : : {
70 : : BTMetaPageData *metad;
71 : : BTPageOpaque metaopaque;
72 : :
7818 tgl@sss.pgh.pa.us 73 : 25311 : _bt_pageinit(page, BLCKSZ);
74 : :
75 : 25311 : metad = BTPageGetMeta(page);
76 : 25311 : metad->btm_magic = BTREE_MAGIC;
77 : 25311 : metad->btm_version = BTREE_VERSION;
78 : 25311 : metad->btm_root = rootbknum;
79 : 25311 : metad->btm_level = level;
80 : 25311 : metad->btm_fastroot = rootbknum;
81 : 25311 : metad->btm_fastlevel = level;
1707 pg@bowt.ie 82 : 25311 : metad->btm_last_cleanup_num_delpages = 0;
2764 teodor@sigaev.ru 83 : 25311 : metad->btm_last_cleanup_num_heap_tuples = -1.0;
2071 pg@bowt.ie 84 : 25311 : metad->btm_allequalimage = allequalimage;
85 : :
1306 michael@paquier.xyz 86 : 25311 : metaopaque = BTPageGetOpaque(page);
7818 tgl@sss.pgh.pa.us 87 : 25311 : metaopaque->btpo_flags = BTP_META;
88 : :
89 : : /*
90 : : * Set pd_lower just past the end of the metadata. This is essential,
91 : : * because without doing so, metadata will be lost if xlog.c compresses
92 : : * the page.
93 : : */
7453 94 : 25311 : ((PageHeader) page)->pd_lower =
95 : 25311 : ((char *) metad + sizeof(BTMetaPageData)) - (char *) page;
7818 96 : 25311 : }
97 : :
98 : : /*
99 : : * _bt_upgrademetapage() -- Upgrade a meta-page from an old format to version
100 : : * 3, the last version that can be updated without broadly affecting
101 : : * on-disk compatibility. (A REINDEX is required to upgrade to v4.)
102 : : *
103 : : * This routine does purely in-memory image upgrade. Caller is
104 : : * responsible for locking, WAL-logging etc.
105 : : */
106 : : void
2764 teodor@sigaev.ru 107 :UBC 0 : _bt_upgrademetapage(Page page)
108 : : {
109 : : BTMetaPageData *metad;
110 : : BTPageOpaque metaopaque PG_USED_FOR_ASSERTS_ONLY;
111 : :
112 : 0 : metad = BTPageGetMeta(page);
1306 michael@paquier.xyz 113 : 0 : metaopaque = BTPageGetOpaque(page);
114 : :
115 : : /* It must be really a meta page of upgradable version */
2764 teodor@sigaev.ru 116 [ # # ]: 0 : Assert(metaopaque->btpo_flags & BTP_META);
2414 pg@bowt.ie 117 [ # # ]: 0 : Assert(metad->btm_version < BTREE_NOVAC_VERSION);
2764 teodor@sigaev.ru 118 [ # # ]: 0 : Assert(metad->btm_version >= BTREE_MIN_VERSION);
119 : :
120 : : /* Set version number and fill extra fields added into version 3 */
2414 pg@bowt.ie 121 : 0 : metad->btm_version = BTREE_NOVAC_VERSION;
1707 122 : 0 : metad->btm_last_cleanup_num_delpages = 0;
2764 teodor@sigaev.ru 123 : 0 : metad->btm_last_cleanup_num_heap_tuples = -1.0;
124 : : /* Only a REINDEX can set this field */
2071 pg@bowt.ie 125 [ # # ]: 0 : Assert(!metad->btm_allequalimage);
126 : 0 : metad->btm_allequalimage = false;
127 : :
128 : : /* Adjust pd_lower (see _bt_initmetapage() for details) */
2764 teodor@sigaev.ru 129 : 0 : ((PageHeader) page)->pd_lower =
130 : 0 : ((char *) metad + sizeof(BTMetaPageData)) - (char *) page;
131 : 0 : }
132 : :
133 : : /*
134 : : * Get metadata from share-locked buffer containing metapage, while performing
135 : : * standard sanity checks.
136 : : *
137 : : * Callers that cache data returned here in local cache should note that an
138 : : * on-the-fly upgrade using _bt_upgrademetapage() can change the version field
139 : : * and BTREE_NOVAC_VERSION specific fields without invalidating local cache.
140 : : */
141 : : static BTMetaPageData *
2414 pg@bowt.ie 142 :CBC 878957 : _bt_getmeta(Relation rel, Buffer metabuf)
143 : : {
144 : : Page metapg;
145 : : BTPageOpaque metaopaque;
146 : : BTMetaPageData *metad;
147 : :
148 : 878957 : metapg = BufferGetPage(metabuf);
1306 michael@paquier.xyz 149 : 878957 : metaopaque = BTPageGetOpaque(metapg);
2414 pg@bowt.ie 150 : 878957 : metad = BTPageGetMeta(metapg);
151 : :
152 : : /* sanity-check the metapage */
153 [ + - ]: 878957 : if (!P_ISMETA(metaopaque) ||
154 [ - + ]: 878957 : metad->btm_magic != BTREE_MAGIC)
2414 pg@bowt.ie 155 [ # # ]:UBC 0 : ereport(ERROR,
156 : : (errcode(ERRCODE_INDEX_CORRUPTED),
157 : : errmsg("index \"%s\" is not a btree",
158 : : RelationGetRelationName(rel))));
159 : :
2414 pg@bowt.ie 160 [ + - ]:CBC 878957 : if (metad->btm_version < BTREE_MIN_VERSION ||
161 [ - + ]: 878957 : metad->btm_version > BTREE_VERSION)
2414 pg@bowt.ie 162 [ # # ]:UBC 0 : ereport(ERROR,
163 : : (errcode(ERRCODE_INDEX_CORRUPTED),
164 : : errmsg("version mismatch in index \"%s\": file version %d, "
165 : : "current version %d, minimal supported version %d",
166 : : RelationGetRelationName(rel),
167 : : metad->btm_version, BTREE_VERSION, BTREE_MIN_VERSION)));
168 : :
2414 pg@bowt.ie 169 :CBC 878957 : return metad;
170 : : }
171 : :
172 : : /*
173 : : * _bt_vacuum_needs_cleanup() -- Checks if index needs cleanup
174 : : *
175 : : * Called by btvacuumcleanup when btbulkdelete was never called because no
176 : : * index tuples needed to be deleted.
177 : : */
178 : : bool
871 179 : 17060 : _bt_vacuum_needs_cleanup(Relation rel)
180 : : {
181 : : Buffer metabuf;
182 : : Page metapg;
183 : : BTMetaPageData *metad;
184 : : uint32 btm_version;
185 : : BlockNumber prev_num_delpages;
186 : :
187 : : /*
188 : : * Copy details from metapage to local variables quickly.
189 : : *
190 : : * Note that we deliberately avoid using cached version of metapage here.
191 : : */
192 : 17060 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
1691 193 : 17060 : metapg = BufferGetPage(metabuf);
194 : 17060 : metad = BTPageGetMeta(metapg);
195 : 17060 : btm_version = metad->btm_version;
196 : :
197 [ - + ]: 17060 : if (btm_version < BTREE_NOVAC_VERSION)
198 : : {
199 : : /*
200 : : * Metapage needs to be dynamically upgraded to store fields that are
201 : : * only present when btm_version >= BTREE_NOVAC_VERSION
202 : : */
1691 pg@bowt.ie 203 :UBC 0 : _bt_relbuf(rel, metabuf);
204 : 0 : return true;
205 : : }
206 : :
1691 pg@bowt.ie 207 :CBC 17060 : prev_num_delpages = metad->btm_last_cleanup_num_delpages;
208 : 17060 : _bt_relbuf(rel, metabuf);
209 : :
210 : : /*
211 : : * Trigger cleanup in rare cases where prev_num_delpages exceeds 5% of the
212 : : * total size of the index. We can reasonably expect (though are not
213 : : * guaranteed) to be able to recycle this many pages if we decide to do a
214 : : * btvacuumscan call during the ongoing btvacuumcleanup. For further
215 : : * details see the nbtree/README section on placing deleted pages in the
216 : : * FSM.
217 : : */
218 [ + + ]: 17060 : if (prev_num_delpages > 0 &&
219 [ + - ]: 8 : prev_num_delpages > RelationGetNumberOfBlocks(rel) / 20)
220 : 8 : return true;
221 : :
222 : 17052 : return false;
223 : : }
224 : :
225 : : /*
226 : : * _bt_set_cleanup_info() -- Update metapage for btvacuumcleanup.
227 : : *
228 : : * Called at the end of btvacuumcleanup, when num_delpages value has been
229 : : * finalized.
230 : : */
231 : : void
871 232 : 1229 : _bt_set_cleanup_info(Relation rel, BlockNumber num_delpages)
233 : : {
234 : : Buffer metabuf;
235 : : Page metapg;
236 : : BTMetaPageData *metad;
237 : :
238 : : /*
239 : : * On-disk compatibility note: The btm_last_cleanup_num_delpages metapage
240 : : * field started out as a TransactionId field called btm_oldest_btpo_xact.
241 : : * Both "versions" are just uint32 fields. It was convenient to repurpose
242 : : * the field when we began to use 64-bit XIDs in deleted pages.
243 : : *
244 : : * It's possible that a pg_upgrade'd database will contain an XID value in
245 : : * what is now recognized as the metapage's btm_last_cleanup_num_delpages
246 : : * field. _bt_vacuum_needs_cleanup() may even believe that this value
247 : : * indicates that there are lots of pages that it needs to recycle, when
248 : : * in reality there are only one or two. The worst that can happen is
249 : : * that there will be a call to btvacuumscan a little earlier, which will
250 : : * set btm_last_cleanup_num_delpages to a sane value when we're called.
251 : : *
252 : : * Note also that the metapage's btm_last_cleanup_num_heap_tuples field is
253 : : * no longer used as of PostgreSQL 14. We set it to -1.0 on rewrite, just
254 : : * to be consistent.
255 : : */
256 : 1229 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
2764 teodor@sigaev.ru 257 : 1229 : metapg = BufferGetPage(metabuf);
258 : 1229 : metad = BTPageGetMeta(metapg);
259 : :
260 : : /* Don't miss chance to upgrade index/metapage when BTREE_MIN_VERSION */
1693 pg@bowt.ie 261 [ + - ]: 1229 : if (metad->btm_version >= BTREE_NOVAC_VERSION &&
262 [ + + ]: 1229 : metad->btm_last_cleanup_num_delpages == num_delpages)
263 : : {
264 : : /* Usually means index continues to have num_delpages of 0 */
2764 teodor@sigaev.ru 265 : 1123 : _bt_relbuf(rel, metabuf);
266 : 1123 : return;
267 : : }
268 : :
269 : : /* trade in our read lock for a write lock */
1925 pg@bowt.ie 270 : 106 : _bt_unlockbuf(rel, metabuf);
271 : 106 : _bt_lockbuf(rel, metabuf, BT_WRITE);
272 : :
2764 teodor@sigaev.ru 273 : 106 : START_CRIT_SECTION();
274 : :
275 : : /* upgrade meta-page if needed */
2414 pg@bowt.ie 276 [ - + ]: 106 : if (metad->btm_version < BTREE_NOVAC_VERSION)
2764 teodor@sigaev.ru 277 :UBC 0 : _bt_upgrademetapage(metapg);
278 : :
279 : : /* update cleanup-related information */
1707 pg@bowt.ie 280 :CBC 106 : metad->btm_last_cleanup_num_delpages = num_delpages;
1693 281 : 106 : metad->btm_last_cleanup_num_heap_tuples = -1.0;
2764 teodor@sigaev.ru 282 : 106 : MarkBufferDirty(metabuf);
283 : :
284 : : /* write wal record if needed */
285 [ + - + + : 106 : if (RelationNeedsWAL(rel))
+ - + - ]
286 : : {
287 : : xl_btree_metadata md;
288 : : XLogRecPtr recptr;
289 : :
290 : 106 : XLogBeginInsert();
291 : 106 : XLogRegisterBuffer(0, metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);
292 : :
2414 pg@bowt.ie 293 [ - + ]: 106 : Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
294 : 106 : md.version = metad->btm_version;
2764 teodor@sigaev.ru 295 : 106 : md.root = metad->btm_root;
296 : 106 : md.level = metad->btm_level;
297 : 106 : md.fastroot = metad->btm_fastroot;
298 : 106 : md.fastlevel = metad->btm_fastlevel;
1707 pg@bowt.ie 299 : 106 : md.last_cleanup_num_delpages = num_delpages;
2071 300 : 106 : md.allequalimage = metad->btm_allequalimage;
301 : :
259 peter@eisentraut.org 302 : 106 : XLogRegisterBufData(0, &md, sizeof(xl_btree_metadata));
303 : :
2764 teodor@sigaev.ru 304 : 106 : recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_META_CLEANUP);
305 : :
306 : 106 : PageSetLSN(metapg, recptr);
307 : : }
308 : :
309 [ - + ]: 106 : END_CRIT_SECTION();
310 : :
311 : 106 : _bt_relbuf(rel, metabuf);
312 : : }
313 : :
314 : : /*
315 : : * _bt_getroot() -- Get the root page of the btree.
316 : : *
317 : : * Since the root page can move around the btree file, we have to read
318 : : * its location from the metadata page, and then read the root page
319 : : * itself. If no root page exists yet, we have to create one.
320 : : *
321 : : * The access type parameter (BT_READ or BT_WRITE) controls whether
322 : : * a new root page will be created or not. If access = BT_READ,
323 : : * and no root page exists, we just return InvalidBuffer. For
324 : : * BT_WRITE, we try to create the root page if it doesn't exist.
325 : : * NOTE that the returned root page will have only a read lock set
326 : : * on it even if access = BT_WRITE!
327 : : *
328 : : * If access = BT_WRITE, heaprel must be set; otherwise caller can just
329 : : * pass NULL. See _bt_allocbuf for an explanation.
330 : : *
331 : : * The returned page is not necessarily the true root --- it could be
332 : : * a "fast root" (a page that is alone in its level due to deletions).
333 : : * Also, if the root page is split while we are "in flight" to it,
334 : : * what we will return is the old root, which is now just the leftmost
335 : : * page on a probably-not-very-wide level. For most purposes this is
336 : : * as good as or better than the true root, so we do not bother to
337 : : * insist on finding the true root. We do, however, guarantee to
338 : : * return a live (not deleted or half-dead) page.
339 : : *
340 : : * On successful return, the root page is pinned and read-locked.
341 : : * The metadata page is not locked or pinned on exit.
342 : : */
343 : : Buffer
941 andres@anarazel.de 344 : 10959888 : _bt_getroot(Relation rel, Relation heaprel, int access)
345 : : {
346 : : Buffer metabuf;
347 : : Buffer rootbuf;
348 : : Page rootpage;
349 : : BTPageOpaque rootopaque;
350 : : BlockNumber rootblkno;
351 : : uint32 rootlevel;
352 : : BTMetaPageData *metad;
353 : :
871 pg@bowt.ie 354 [ + + - + ]: 10959888 : Assert(access == BT_READ || heaprel != NULL);
355 : :
356 : : /*
357 : : * Try to use previously-cached metapage data to find the root. This
358 : : * normally saves one buffer access per index search, which is a very
359 : : * helpful savings in bufmgr traffic and hence contention.
360 : : */
7126 tgl@sss.pgh.pa.us 361 [ + + ]: 10959888 : if (rel->rd_amcache != NULL)
362 : : {
363 : 10692249 : metad = (BTMetaPageData *) rel->rd_amcache;
364 : : /* We shouldn't have cached it if any of these fail */
365 [ - + ]: 10692249 : Assert(metad->btm_magic == BTREE_MAGIC);
2764 teodor@sigaev.ru 366 [ - + ]: 10692249 : Assert(metad->btm_version >= BTREE_MIN_VERSION);
367 [ - + ]: 10692249 : Assert(metad->btm_version <= BTREE_VERSION);
2071 pg@bowt.ie 368 [ + + - + ]: 10692249 : Assert(!metad->btm_allequalimage ||
369 : : metad->btm_version > BTREE_NOVAC_VERSION);
7126 tgl@sss.pgh.pa.us 370 [ - + ]: 10692249 : Assert(metad->btm_root != P_NONE);
371 : :
372 : 10692249 : rootblkno = metad->btm_fastroot;
373 [ - + ]: 10692249 : Assert(rootblkno != P_NONE);
374 : 10692249 : rootlevel = metad->btm_fastlevel;
375 : :
871 pg@bowt.ie 376 : 10692249 : rootbuf = _bt_getbuf(rel, rootblkno, BT_READ);
3478 kgrittn@postgresql.o 377 : 10692249 : rootpage = BufferGetPage(rootbuf);
1306 michael@paquier.xyz 378 : 10692249 : rootopaque = BTPageGetOpaque(rootpage);
379 : :
380 : : /*
381 : : * Since the cache might be stale, we check the page more carefully
382 : : * here than normal. We *must* check that it's not deleted. If it's
383 : : * not alone on its level, then we reject too --- this may be overly
384 : : * paranoid but better safe than sorry. Note we don't check P_ISROOT,
385 : : * because that's not set in a "fast root".
386 : : */
7126 tgl@sss.pgh.pa.us 387 [ + - ]: 10692249 : if (!P_IGNORE(rootopaque) &&
1707 pg@bowt.ie 388 [ + - ]: 10692249 : rootopaque->btpo_level == rootlevel &&
7126 tgl@sss.pgh.pa.us 389 [ + - ]: 10692249 : P_LEFTMOST(rootopaque) &&
390 [ + + ]: 10692249 : P_RIGHTMOST(rootopaque))
391 : : {
392 : : /* OK, accept cached page as the root */
393 : 10691491 : return rootbuf;
394 : : }
395 : 758 : _bt_relbuf(rel, rootbuf);
396 : : /* Cache is stale, throw it away */
397 [ + - ]: 758 : if (rel->rd_amcache)
398 : 758 : pfree(rel->rd_amcache);
399 : 758 : rel->rd_amcache = NULL;
400 : : }
401 : :
871 pg@bowt.ie 402 : 268397 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
2294 403 : 268397 : metad = _bt_getmeta(rel, metabuf);
404 : :
405 : : /* if no root page initialized yet, do it */
10278 bruce@momjian.us 406 [ + + ]: 268397 : if (metad->btm_root == P_NONE)
407 : : {
408 : : Page metapg;
409 : :
410 : : /* If access = BT_READ, caller doesn't want us to create root yet */
9230 tgl@sss.pgh.pa.us 411 [ + + ]: 267370 : if (access == BT_READ)
412 : : {
8871 413 : 261154 : _bt_relbuf(rel, metabuf);
9230 414 : 261154 : return InvalidBuffer;
415 : : }
416 : :
417 : : /* trade in our read lock for a write lock */
1925 pg@bowt.ie 418 : 6216 : _bt_unlockbuf(rel, metabuf);
419 : 6216 : _bt_lockbuf(rel, metabuf, BT_WRITE);
420 : :
421 : : /*
422 : : * Race condition: if someone else initialized the metadata between
423 : : * the time we released the read lock and acquired the write lock, we
424 : : * must avoid doing it again.
425 : : */
8284 tgl@sss.pgh.pa.us 426 [ - + ]: 6216 : if (metad->btm_root != P_NONE)
427 : : {
428 : : /*
429 : : * Metadata initialized by someone else. In order to guarantee no
430 : : * deadlocks, we have to release the metadata page and start all
431 : : * over again. (Is that really true? But it's hardly worth trying
432 : : * to optimize this case.)
433 : : */
8284 tgl@sss.pgh.pa.us 434 :UBC 0 : _bt_relbuf(rel, metabuf);
941 andres@anarazel.de 435 : 0 : return _bt_getroot(rel, heaprel, access);
436 : : }
437 : :
438 : : /*
439 : : * Get, initialize, write, and leave a lock of the appropriate type on
440 : : * the new root page. Since this is the first page in the tree, it's
441 : : * a leaf as well as the root.
442 : : */
871 pg@bowt.ie 443 :CBC 6216 : rootbuf = _bt_allocbuf(rel, heaprel);
8284 tgl@sss.pgh.pa.us 444 : 6216 : rootblkno = BufferGetBlockNumber(rootbuf);
3478 kgrittn@postgresql.o 445 : 6216 : rootpage = BufferGetPage(rootbuf);
1306 michael@paquier.xyz 446 : 6216 : rootopaque = BTPageGetOpaque(rootpage);
8284 tgl@sss.pgh.pa.us 447 : 6216 : rootopaque->btpo_prev = rootopaque->btpo_next = P_NONE;
448 : 6216 : rootopaque->btpo_flags = (BTP_LEAF | BTP_ROOT);
1707 pg@bowt.ie 449 : 6216 : rootopaque->btpo_level = 0;
7113 tgl@sss.pgh.pa.us 450 : 6216 : rootopaque->btpo_cycleid = 0;
451 : : /* Get raw page pointer for metapage */
2294 pg@bowt.ie 452 : 6216 : metapg = BufferGetPage(metabuf);
453 : :
454 : : /* NO ELOG(ERROR) till meta is updated */
8284 tgl@sss.pgh.pa.us 455 : 6216 : START_CRIT_SECTION();
456 : :
457 : : /* upgrade metapage if needed */
2414 pg@bowt.ie 458 [ - + ]: 6216 : if (metad->btm_version < BTREE_NOVAC_VERSION)
2708 teodor@sigaev.ru 459 :UBC 0 : _bt_upgrademetapage(metapg);
460 : :
8284 tgl@sss.pgh.pa.us 461 :CBC 6216 : metad->btm_root = rootblkno;
462 : 6216 : metad->btm_level = 0;
463 : 6216 : metad->btm_fastroot = rootblkno;
464 : 6216 : metad->btm_fastlevel = 0;
1707 pg@bowt.ie 465 : 6216 : metad->btm_last_cleanup_num_delpages = 0;
2764 teodor@sigaev.ru 466 : 6216 : metad->btm_last_cleanup_num_heap_tuples = -1.0;
467 : :
7151 tgl@sss.pgh.pa.us 468 : 6216 : MarkBufferDirty(rootbuf);
469 : 6216 : MarkBufferDirty(metabuf);
470 : :
471 : : /* XLOG stuff */
5433 rhaas@postgresql.org 472 [ + + + + : 6216 : if (RelationNeedsWAL(rel))
+ + + + ]
473 : : {
474 : : xl_btree_newroot xlrec;
475 : : XLogRecPtr recptr;
476 : : xl_btree_metadata md;
477 : :
3995 heikki.linnakangas@i 478 : 5976 : XLogBeginInsert();
479 : 5976 : XLogRegisterBuffer(0, rootbuf, REGBUF_WILL_INIT);
2916 tgl@sss.pgh.pa.us 480 : 5976 : XLogRegisterBuffer(2, metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);
481 : :
2414 pg@bowt.ie 482 [ - + ]: 5976 : Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
483 : 5976 : md.version = metad->btm_version;
3995 heikki.linnakangas@i 484 : 5976 : md.root = rootblkno;
485 : 5976 : md.level = 0;
486 : 5976 : md.fastroot = rootblkno;
487 : 5976 : md.fastlevel = 0;
1707 pg@bowt.ie 488 : 5976 : md.last_cleanup_num_delpages = 0;
2071 489 : 5976 : md.allequalimage = metad->btm_allequalimage;
490 : :
259 peter@eisentraut.org 491 : 5976 : XLogRegisterBufData(2, &md, sizeof(xl_btree_metadata));
492 : :
8284 tgl@sss.pgh.pa.us 493 : 5976 : xlrec.rootblk = rootblkno;
494 : 5976 : xlrec.level = 0;
495 : :
259 peter@eisentraut.org 496 : 5976 : XLogRegisterData(&xlrec, SizeOfBtreeNewroot);
497 : :
3995 heikki.linnakangas@i 498 : 5976 : recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_NEWROOT);
499 : :
8284 tgl@sss.pgh.pa.us 500 : 5976 : PageSetLSN(rootpage, recptr);
501 : 5976 : PageSetLSN(metapg, recptr);
502 : : }
503 : :
504 [ - + ]: 6216 : END_CRIT_SECTION();
505 : :
506 : : /*
507 : : * swap root write lock for read lock. There is no danger of anyone
508 : : * else accessing the new root page while it's unlocked, since no one
509 : : * else knows where it is yet.
510 : : */
1925 pg@bowt.ie 511 : 6216 : _bt_unlockbuf(rel, rootbuf);
512 : 6216 : _bt_lockbuf(rel, rootbuf, BT_READ);
513 : :
514 : : /* okay, metadata is correct, release lock on it without caching */
7151 tgl@sss.pgh.pa.us 515 : 6216 : _bt_relbuf(rel, metabuf);
516 : : }
517 : : else
518 : : {
8285 519 : 1027 : rootblkno = metad->btm_fastroot;
8284 520 [ - + ]: 1027 : Assert(rootblkno != P_NONE);
521 : 1027 : rootlevel = metad->btm_fastlevel;
522 : :
523 : : /*
524 : : * Cache the metapage data for next time
525 : : */
2294 pg@bowt.ie 526 : 1027 : rel->rd_amcache = MemoryContextAlloc(rel->rd_indexcxt,
527 : : sizeof(BTMetaPageData));
528 : 1027 : memcpy(rel->rd_amcache, metad, sizeof(BTMetaPageData));
529 : :
530 : : /*
531 : : * We are done with the metapage; arrange to release it via first
532 : : * _bt_relandgetbuf call
533 : : */
7860 tgl@sss.pgh.pa.us 534 : 1027 : rootbuf = metabuf;
535 : :
536 : : for (;;)
537 : : {
538 : 1027 : rootbuf = _bt_relandgetbuf(rel, rootbuf, rootblkno, BT_READ);
3478 kgrittn@postgresql.o 539 : 1027 : rootpage = BufferGetPage(rootbuf);
1306 michael@paquier.xyz 540 : 1027 : rootopaque = BTPageGetOpaque(rootpage);
541 : :
8284 tgl@sss.pgh.pa.us 542 [ + - ]: 1027 : if (!P_IGNORE(rootopaque))
543 : 1027 : break;
544 : :
545 : : /* it's dead, Jim. step right one page */
8284 tgl@sss.pgh.pa.us 546 [ # # ]:UBC 0 : if (P_RIGHTMOST(rootopaque))
6511 547 [ # # ]: 0 : elog(ERROR, "no live root page found in index \"%s\"",
548 : : RelationGetRelationName(rel));
8284 549 : 0 : rootblkno = rootopaque->btpo_next;
550 : : }
551 : :
1707 pg@bowt.ie 552 [ - + ]:CBC 1027 : if (rootopaque->btpo_level != rootlevel)
6511 tgl@sss.pgh.pa.us 553 [ # # ]:UBC 0 : elog(ERROR, "root page %u of index \"%s\" has level %u, expected %u",
554 : : rootblkno, RelationGetRelationName(rel),
555 : : rootopaque->btpo_level, rootlevel);
556 : : }
557 : :
558 : : /*
559 : : * By here, we have a pin and read lock on the root page, and no lock set
560 : : * on the metadata page. Return the root page's buffer.
561 : : */
8285 tgl@sss.pgh.pa.us 562 :CBC 7243 : return rootbuf;
563 : : }
564 : :
565 : : /*
566 : : * _bt_gettrueroot() -- Get the true root page of the btree.
567 : : *
568 : : * This is the same as the BT_READ case of _bt_getroot(), except
569 : : * we follow the true-root link not the fast-root link.
570 : : *
571 : : * By the time we acquire lock on the root page, it might have been split and
572 : : * not be the true root anymore. This is okay for the present uses of this
573 : : * routine; we only really need to be able to move up at least one tree level
574 : : * from whatever non-root page we were at. If we ever do need to lock the
575 : : * one true root page, we could loop here, re-reading the metapage on each
576 : : * failure. (Note that it wouldn't do to hold the lock on the metapage while
577 : : * moving to the root --- that'd deadlock against any concurrent root split.)
578 : : */
579 : : Buffer
871 pg@bowt.ie 580 : 12 : _bt_gettrueroot(Relation rel)
581 : : {
582 : : Buffer metabuf;
583 : : Page metapg;
584 : : BTPageOpaque metaopaque;
585 : : Buffer rootbuf;
586 : : Page rootpage;
587 : : BTPageOpaque rootopaque;
588 : : BlockNumber rootblkno;
589 : : uint32 rootlevel;
590 : : BTMetaPageData *metad;
591 : :
592 : : /*
593 : : * We don't try to use cached metapage data here, since (a) this path is
594 : : * not performance-critical, and (b) if we are here it suggests our cache
595 : : * is out-of-date anyway. In light of point (b), it's probably safest to
596 : : * actively flush any cached metapage info.
597 : : */
7126 tgl@sss.pgh.pa.us 598 [ + - ]: 12 : if (rel->rd_amcache)
599 : 12 : pfree(rel->rd_amcache);
600 : 12 : rel->rd_amcache = NULL;
601 : :
871 pg@bowt.ie 602 : 12 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
3478 kgrittn@postgresql.o 603 : 12 : metapg = BufferGetPage(metabuf);
1306 michael@paquier.xyz 604 : 12 : metaopaque = BTPageGetOpaque(metapg);
8285 tgl@sss.pgh.pa.us 605 : 12 : metad = BTPageGetMeta(metapg);
606 : :
2962 607 [ + - ]: 12 : if (!P_ISMETA(metaopaque) ||
8285 608 [ - + ]: 12 : metad->btm_magic != BTREE_MAGIC)
8135 tgl@sss.pgh.pa.us 609 [ # # ]:UBC 0 : ereport(ERROR,
610 : : (errcode(ERRCODE_INDEX_CORRUPTED),
611 : : errmsg("index \"%s\" is not a btree",
612 : : RelationGetRelationName(rel))));
613 : :
2764 teodor@sigaev.ru 614 [ + - ]:CBC 12 : if (metad->btm_version < BTREE_MIN_VERSION ||
615 [ - + ]: 12 : metad->btm_version > BTREE_VERSION)
8135 tgl@sss.pgh.pa.us 616 [ # # ]:UBC 0 : ereport(ERROR,
617 : : (errcode(ERRCODE_INDEX_CORRUPTED),
618 : : errmsg("version mismatch in index \"%s\": file version %d, "
619 : : "current version %d, minimal supported version %d",
620 : : RelationGetRelationName(rel),
621 : : metad->btm_version, BTREE_VERSION, BTREE_MIN_VERSION)));
622 : :
623 : : /* if no root page initialized yet, fail */
8285 tgl@sss.pgh.pa.us 624 [ - + ]:CBC 12 : if (metad->btm_root == P_NONE)
625 : : {
8285 tgl@sss.pgh.pa.us 626 :UBC 0 : _bt_relbuf(rel, metabuf);
627 : 0 : return InvalidBuffer;
628 : : }
629 : :
8285 tgl@sss.pgh.pa.us 630 :CBC 12 : rootblkno = metad->btm_root;
8284 631 : 12 : rootlevel = metad->btm_level;
632 : :
633 : : /*
634 : : * We are done with the metapage; arrange to release it via first
635 : : * _bt_relandgetbuf call
636 : : */
7860 637 : 12 : rootbuf = metabuf;
638 : :
639 : : for (;;)
640 : : {
641 : 12 : rootbuf = _bt_relandgetbuf(rel, rootbuf, rootblkno, BT_READ);
3478 kgrittn@postgresql.o 642 : 12 : rootpage = BufferGetPage(rootbuf);
1306 michael@paquier.xyz 643 : 12 : rootopaque = BTPageGetOpaque(rootpage);
644 : :
8284 tgl@sss.pgh.pa.us 645 [ + - ]: 12 : if (!P_IGNORE(rootopaque))
646 : 12 : break;
647 : :
648 : : /* it's dead, Jim. step right one page */
8284 tgl@sss.pgh.pa.us 649 [ # # ]:UBC 0 : if (P_RIGHTMOST(rootopaque))
6511 650 [ # # ]: 0 : elog(ERROR, "no live root page found in index \"%s\"",
651 : : RelationGetRelationName(rel));
8284 652 : 0 : rootblkno = rootopaque->btpo_next;
653 : : }
654 : :
1707 pg@bowt.ie 655 [ - + ]:CBC 12 : if (rootopaque->btpo_level != rootlevel)
6511 tgl@sss.pgh.pa.us 656 [ # # ]:UBC 0 : elog(ERROR, "root page %u of index \"%s\" has level %u, expected %u",
657 : : rootblkno, RelationGetRelationName(rel),
658 : : rootopaque->btpo_level, rootlevel);
659 : :
9919 bruce@momjian.us 660 :CBC 12 : return rootbuf;
661 : : }
662 : :
663 : : /*
664 : : * _bt_getrootheight() -- Get the height of the btree search tree.
665 : : *
666 : : * We return the level (counting from zero) of the current fast root.
667 : : * This represents the number of tree levels we'd have to descend through
668 : : * to start any btree index search.
669 : : *
670 : : * This is used by the planner for cost-estimation purposes. Since it's
671 : : * only an estimate, slightly-stale data is fine, hence we don't worry
672 : : * about updating previously cached data.
673 : : */
674 : : int
871 pg@bowt.ie 675 : 2400297 : _bt_getrootheight(Relation rel)
676 : : {
677 : : BTMetaPageData *metad;
678 : :
4673 tgl@sss.pgh.pa.us 679 [ + + ]: 2400297 : if (rel->rd_amcache == NULL)
680 : : {
681 : : Buffer metabuf;
682 : :
871 pg@bowt.ie 683 : 41675 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
2414 684 : 41675 : metad = _bt_getmeta(rel, metabuf);
685 : :
686 : : /*
687 : : * If there's no root page yet, _bt_getroot() doesn't expect a cache
688 : : * to be made, so just stop here and report the index height is zero.
689 : : * (XXX perhaps _bt_getroot() should be changed to allow this case.)
690 : : */
4673 tgl@sss.pgh.pa.us 691 [ + + ]: 41675 : if (metad->btm_root == P_NONE)
692 : : {
693 : 19881 : _bt_relbuf(rel, metabuf);
694 : 19881 : return 0;
695 : : }
696 : :
697 : : /*
698 : : * Cache the metapage data for next time
699 : : */
2294 pg@bowt.ie 700 : 21794 : rel->rd_amcache = MemoryContextAlloc(rel->rd_indexcxt,
701 : : sizeof(BTMetaPageData));
702 : 21794 : memcpy(rel->rd_amcache, metad, sizeof(BTMetaPageData));
4673 tgl@sss.pgh.pa.us 703 : 21794 : _bt_relbuf(rel, metabuf);
704 : : }
705 : :
706 : : /* Get cached page */
707 : 2380416 : metad = (BTMetaPageData *) rel->rd_amcache;
708 : : /* We shouldn't have cached it if any of these fail */
2294 pg@bowt.ie 709 [ - + ]: 2380416 : Assert(metad->btm_magic == BTREE_MAGIC);
710 [ - + ]: 2380416 : Assert(metad->btm_version >= BTREE_MIN_VERSION);
711 [ - + ]: 2380416 : Assert(metad->btm_version <= BTREE_VERSION);
2071 712 [ + + - + ]: 2380416 : Assert(!metad->btm_allequalimage ||
713 : : metad->btm_version > BTREE_NOVAC_VERSION);
2294 714 [ - + ]: 2380416 : Assert(metad->btm_fastroot != P_NONE);
715 : :
4673 tgl@sss.pgh.pa.us 716 : 2380416 : return metad->btm_fastlevel;
717 : : }
718 : :
719 : : /*
720 : : * _bt_metaversion() -- Get version/status info from metapage.
721 : : *
722 : : * Sets caller's *heapkeyspace and *allequalimage arguments using data
723 : : * from the B-Tree metapage (could be locally-cached version). This
724 : : * information needs to be stashed in insertion scankey, so we provide a
725 : : * single function that fetches both at once.
726 : : *
727 : : * This is used to determine the rules that must be used to descend a
728 : : * btree. Version 4 indexes treat heap TID as a tiebreaker attribute.
729 : : * pg_upgrade'd version 3 indexes need extra steps to preserve reasonable
730 : : * performance when inserting a new BTScanInsert-wise duplicate tuple
731 : : * among many leaf pages already full of such duplicates.
732 : : *
733 : : * Also sets allequalimage field, which indicates whether or not it is
734 : : * safe to apply deduplication. We rely on the assumption that
735 : : * btm_allequalimage will be zero'ed on heapkeyspace indexes that were
736 : : * pg_upgrade'd from Postgres 12.
737 : : */
738 : : void
871 pg@bowt.ie 739 : 13013351 : _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
740 : : {
741 : : BTMetaPageData *metad;
742 : :
2414 743 [ + + ]: 13013351 : if (rel->rd_amcache == NULL)
744 : : {
745 : : Buffer metabuf;
746 : :
871 747 : 568885 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
2414 748 : 568885 : metad = _bt_getmeta(rel, metabuf);
749 : :
750 : : /*
751 : : * If there's no root page yet, _bt_getroot() doesn't expect a cache
752 : : * to be made, so just stop here. (XXX perhaps _bt_getroot() should
753 : : * be changed to allow this case.)
754 : : */
755 [ + + ]: 568885 : if (metad->btm_root == P_NONE)
756 : : {
2071 757 : 262960 : *heapkeyspace = metad->btm_version > BTREE_NOVAC_VERSION;
758 : 262960 : *allequalimage = metad->btm_allequalimage;
759 : :
2414 760 : 262960 : _bt_relbuf(rel, metabuf);
2071 761 : 262960 : return;
762 : : }
763 : :
764 : : /*
765 : : * Cache the metapage data for next time
766 : : *
767 : : * An on-the-fly version upgrade performed by _bt_upgrademetapage()
768 : : * can change the nbtree version for an index without invalidating any
769 : : * local cache. This is okay because it can only happen when moving
770 : : * from version 2 to version 3, both of which are !heapkeyspace
771 : : * versions.
772 : : */
2294 773 : 305925 : rel->rd_amcache = MemoryContextAlloc(rel->rd_indexcxt,
774 : : sizeof(BTMetaPageData));
775 : 305925 : memcpy(rel->rd_amcache, metad, sizeof(BTMetaPageData));
2414 776 : 305925 : _bt_relbuf(rel, metabuf);
777 : : }
778 : :
779 : : /* Get cached page */
780 : 12750391 : metad = (BTMetaPageData *) rel->rd_amcache;
781 : : /* We shouldn't have cached it if any of these fail */
2294 782 [ - + ]: 12750391 : Assert(metad->btm_magic == BTREE_MAGIC);
783 [ - + ]: 12750391 : Assert(metad->btm_version >= BTREE_MIN_VERSION);
784 [ - + ]: 12750391 : Assert(metad->btm_version <= BTREE_VERSION);
2071 785 [ + + - + ]: 12750391 : Assert(!metad->btm_allequalimage ||
786 : : metad->btm_version > BTREE_NOVAC_VERSION);
2294 787 [ - + ]: 12750391 : Assert(metad->btm_fastroot != P_NONE);
788 : :
2071 789 : 12750391 : *heapkeyspace = metad->btm_version > BTREE_NOVAC_VERSION;
790 : 12750391 : *allequalimage = metad->btm_allequalimage;
791 : : }
792 : :
793 : : /*
794 : : * _bt_checkpage() -- Verify that a freshly-read page looks sane.
795 : : */
796 : : void
7296 tgl@sss.pgh.pa.us 797 : 20661314 : _bt_checkpage(Relation rel, Buffer buf)
798 : : {
3478 kgrittn@postgresql.o 799 : 20661314 : Page page = BufferGetPage(buf);
800 : :
801 : : /*
802 : : * ReadBuffer verifies that every newly-read page passes
803 : : * PageHeaderIsValid, which means it either contains a reasonably sane
804 : : * page header or is all-zero. We have to defend against the all-zero
805 : : * case, however.
806 : : */
7296 tgl@sss.pgh.pa.us 807 [ - + ]: 20661314 : if (PageIsNew(page))
7296 tgl@sss.pgh.pa.us 808 [ # # ]:UBC 0 : ereport(ERROR,
809 : : (errcode(ERRCODE_INDEX_CORRUPTED),
810 : : errmsg("index \"%s\" contains unexpected zero page at block %u",
811 : : RelationGetRelationName(rel),
812 : : BufferGetBlockNumber(buf)),
813 : : errhint("Please REINDEX it.")));
814 : :
815 : : /*
816 : : * Additionally check that the special area looks sane.
817 : : */
6316 tgl@sss.pgh.pa.us 818 [ - + ]:CBC 20661314 : if (PageGetSpecialSize(page) != MAXALIGN(sizeof(BTPageOpaqueData)))
7296 tgl@sss.pgh.pa.us 819 [ # # ]:UBC 0 : ereport(ERROR,
820 : : (errcode(ERRCODE_INDEX_CORRUPTED),
821 : : errmsg("index \"%s\" contains corrupted page at block %u",
822 : : RelationGetRelationName(rel),
823 : : BufferGetBlockNumber(buf)),
824 : : errhint("Please REINDEX it.")));
7296 tgl@sss.pgh.pa.us 825 :CBC 20661314 : }
826 : :
827 : : /*
828 : : * _bt_getbuf() -- Get an existing block in a buffer, for read or write.
829 : : *
830 : : * The general rule in nbtree is that it's never okay to access a
831 : : * page without holding both a buffer pin and a buffer lock on
832 : : * the page's buffer.
833 : : *
834 : : * When this routine returns, the appropriate lock is set on the
835 : : * requested buffer and its reference count has been incremented
836 : : * (ie, the buffer is "locked and pinned"). Also, we apply
837 : : * _bt_checkpage to sanity-check the page, and perform Valgrind
838 : : * client requests that help Valgrind detect unsafe page accesses.
839 : : *
840 : : * Note: raw LockBuffer() calls are disallowed in nbtree; all
841 : : * buffer lock requests need to go through wrapper functions such
842 : : * as _bt_lockbuf().
843 : : */
844 : : Buffer
871 pg@bowt.ie 845 : 11700179 : _bt_getbuf(Relation rel, BlockNumber blkno, int access)
846 : : {
847 : : Buffer buf;
848 : :
849 [ - + ]: 11700179 : Assert(BlockNumberIsValid(blkno));
850 : :
851 : : /* Read an existing block of the relation */
852 : 11700179 : buf = ReadBuffer(rel, blkno);
853 : 11700179 : _bt_lockbuf(rel, buf, access);
854 : 11700179 : _bt_checkpage(rel, buf);
855 : :
856 : 11700179 : return buf;
857 : : }
858 : :
859 : : /*
860 : : * _bt_allocbuf() -- Allocate a new block/page.
861 : : *
862 : : * Returns a write-locked buffer containing an unallocated nbtree page.
863 : : *
864 : : * Callers are required to pass a valid heaprel. We need heaprel so that we
865 : : * can handle generating a snapshotConflictHorizon that makes reusing a page
866 : : * from the FSM safe for queries that may be running on standbys.
867 : : */
868 : : Buffer
869 : 18362 : _bt_allocbuf(Relation rel, Relation heaprel)
870 : : {
871 : : Buffer buf;
872 : : BlockNumber blkno;
873 : : Page page;
874 : :
875 [ + - ]: 18362 : Assert(heaprel != NULL);
876 : :
877 : : /*
878 : : * First see if the FSM knows of any free pages.
879 : : *
880 : : * We can't trust the FSM's report unreservedly; we have to check that the
881 : : * page is still free. (For example, an already-free page could have been
882 : : * re-used between the time the last VACUUM scanned it and the time the
883 : : * VACUUM made its FSM updates.)
884 : : *
885 : : * In fact, it's worse than that: we can't even assume that it's safe to
886 : : * take a lock on the reported page. If somebody else has a lock on it,
887 : : * or even worse our own caller does, we could deadlock. (The own-caller
888 : : * scenario is actually not improbable. Consider an index on a serial or
889 : : * timestamp column. Nearly all splits will be at the rightmost page, so
890 : : * it's entirely likely that _bt_split will call us while holding a lock
891 : : * on the page most recently acquired from FSM. A VACUUM running
892 : : * concurrently with the previous split could well have placed that page
893 : : * back in FSM.)
894 : : *
895 : : * To get around that, we ask for only a conditional lock on the reported
896 : : * page. If we fail, then someone else is using the page, and we may
897 : : * reasonably assume it's not free. (If we happen to be wrong, the worst
898 : : * consequence is the page will be lost to use till the next VACUUM, which
899 : : * is no big problem.)
900 : : */
901 : : for (;;)
902 : : {
903 : 18362 : blkno = GetFreeIndexPage(rel);
904 [ + + ]: 18362 : if (blkno == InvalidBlockNumber)
905 : 17992 : break;
906 : 370 : buf = ReadBuffer(rel, blkno);
907 [ + - ]: 370 : if (_bt_conditionallockbuf(rel, buf))
908 : : {
909 : 370 : page = BufferGetPage(buf);
910 : :
911 : : /*
912 : : * It's possible to find an all-zeroes page in an index. For
913 : : * example, a backend might successfully extend the relation one
914 : : * page and then crash before it is able to make a WAL entry for
915 : : * adding the page. If we find a zeroed page then reclaim it
916 : : * immediately.
917 : : */
918 [ - + ]: 370 : if (PageIsNew(page))
919 : : {
920 : : /* Okay to use page. Initialize and return it. */
871 pg@bowt.ie 921 :UBC 0 : _bt_pageinit(page, BufferGetPageSize(buf));
922 : 0 : return buf;
923 : : }
924 : :
871 pg@bowt.ie 925 [ + - ]:CBC 370 : if (BTPageIsRecyclable(page, heaprel))
926 : : {
927 : : /*
928 : : * If we are generating WAL for Hot Standby then create a WAL
929 : : * record that will allow us to conflict with queries running
930 : : * on standby, in case they have snapshots older than safexid
931 : : * value
932 : : */
933 [ + - + + : 370 : if (RelationNeedsWAL(rel) && XLogStandbyInfoActive())
+ - + - +
+ ]
934 : : {
935 : : xl_btree_reuse_page xlrec_reuse;
936 : :
937 : : /*
938 : : * Note that we don't register the buffer with the record,
939 : : * because this operation doesn't modify the page (that
940 : : * already happened, back when VACUUM deleted the page).
941 : : * This record only exists to provide a conflict point for
942 : : * Hot Standby. See record REDO routine comments.
943 : : */
944 : 312 : xlrec_reuse.locator = rel->rd_locator;
945 : 312 : xlrec_reuse.block = blkno;
946 : 312 : xlrec_reuse.snapshotConflictHorizon = BTPageGetDeleteXid(page);
947 : 312 : xlrec_reuse.isCatalogRel =
948 [ - + - - : 312 : RelationIsAccessibleInLogicalDecoding(heaprel);
- - - - -
- - - - -
- - - - -
- ]
949 : :
950 : 312 : XLogBeginInsert();
259 peter@eisentraut.org 951 : 312 : XLogRegisterData(&xlrec_reuse, SizeOfBtreeReusePage);
952 : :
871 pg@bowt.ie 953 : 312 : XLogInsert(RM_BTREE_ID, XLOG_BTREE_REUSE_PAGE);
954 : : }
955 : :
956 : : /* Okay to use page. Re-initialize and return it. */
957 : 370 : _bt_pageinit(page, BufferGetPageSize(buf));
958 : 370 : return buf;
959 : : }
871 pg@bowt.ie 960 [ # # ]:UBC 0 : elog(DEBUG2, "FSM returned nonrecyclable page");
961 : 0 : _bt_relbuf(rel, buf);
962 : : }
963 : : else
964 : : {
965 [ # # ]: 0 : elog(DEBUG2, "FSM returned nonlockable page");
966 : : /* couldn't get lock, so just drop pin */
967 : 0 : ReleaseBuffer(buf);
968 : : }
969 : : }
970 : :
971 : : /*
972 : : * Extend the relation by one page. Need to use RBM_ZERO_AND_LOCK or we
973 : : * risk a race condition against btvacuumscan --- see comments therein.
974 : : * This forces us to repeat the valgrind request that _bt_lockbuf()
975 : : * otherwise would make, as we can't use _bt_lockbuf() without introducing
976 : : * a race.
977 : : */
797 tmunro@postgresql.or 978 :CBC 17992 : buf = ExtendBufferedRel(BMR_REL(rel), MAIN_FORKNUM, NULL, EB_LOCK_FIRST);
871 pg@bowt.ie 979 : 17992 : if (!RelationUsesLocalBuffers(rel))
980 : : VALGRIND_MAKE_MEM_DEFINED(BufferGetPage(buf), BLCKSZ);
981 : :
982 : : /* Initialize the new page before returning it */
983 : 17992 : page = BufferGetPage(buf);
984 [ - + ]: 17992 : Assert(PageIsNew(page));
985 : 17992 : _bt_pageinit(page, BufferGetPageSize(buf));
986 : :
9919 bruce@momjian.us 987 : 17992 : return buf;
988 : : }
989 : :
990 : : /*
991 : : * _bt_relandgetbuf() -- release a locked buffer and get another one.
992 : : *
993 : : * This is equivalent to _bt_relbuf followed by _bt_getbuf. Also, if obuf is
994 : : * InvalidBuffer then it reduces to just _bt_getbuf; allowing this case
995 : : * simplifies some callers.
996 : : *
997 : : * The original motivation for using this was to avoid two entries to the
998 : : * bufmgr when one would do. However, now it's mainly just a notational
999 : : * convenience. The only case where it saves work over _bt_relbuf/_bt_getbuf
1000 : : * is when the target page is the same one already in the buffer.
1001 : : */
1002 : : Buffer
7860 tgl@sss.pgh.pa.us 1003 : 8887525 : _bt_relandgetbuf(Relation rel, Buffer obuf, BlockNumber blkno, int access)
1004 : : {
1005 : : Buffer buf;
1006 : :
871 pg@bowt.ie 1007 [ - + ]: 8887525 : Assert(BlockNumberIsValid(blkno));
7860 tgl@sss.pgh.pa.us 1008 [ + + ]: 8887525 : if (BufferIsValid(obuf))
1925 pg@bowt.ie 1009 : 8879623 : _bt_unlockbuf(rel, obuf);
7860 tgl@sss.pgh.pa.us 1010 : 8887525 : buf = ReleaseAndReadBuffer(obuf, rel, blkno);
1925 pg@bowt.ie 1011 : 8887525 : _bt_lockbuf(rel, buf, access);
1012 : :
7296 tgl@sss.pgh.pa.us 1013 : 8887525 : _bt_checkpage(rel, buf);
7860 1014 : 8887525 : return buf;
1015 : : }
1016 : :
1017 : : /*
1018 : : * _bt_relbuf() -- release a locked buffer.
1019 : : *
1020 : : * Lock and pin (refcount) are both dropped.
1021 : : */
1022 : : void
8871 1023 : 9522165 : _bt_relbuf(Relation rel, Buffer buf)
1024 : : {
1925 pg@bowt.ie 1025 : 9522165 : _bt_unlockbuf(rel, buf);
1026 : 9522165 : ReleaseBuffer(buf);
1027 : 9522165 : }
1028 : :
1029 : : /*
1030 : : * _bt_lockbuf() -- lock a pinned buffer.
1031 : : *
1032 : : * Lock is acquired without acquiring another pin. This is like a raw
1033 : : * LockBuffer() call, but performs extra steps needed by Valgrind.
1034 : : *
1035 : : * Note: Caller may need to call _bt_checkpage() with buf when pin on buf
1036 : : * wasn't originally acquired in _bt_getbuf() or _bt_relandgetbuf().
1037 : : */
1038 : : void
1039 : 21087026 : _bt_lockbuf(Relation rel, Buffer buf, int access)
1040 : : {
1041 : : /* LockBuffer() asserts that pin is held by this backend */
1042 : 21087026 : LockBuffer(buf, access);
1043 : :
1044 : : /*
1045 : : * It doesn't matter that _bt_unlockbuf() won't get called in the event of
1046 : : * an nbtree error (e.g. a unique violation error). That won't cause
1047 : : * Valgrind false positives.
1048 : : *
1049 : : * The nbtree client requests are superimposed on top of the bufmgr.c
1050 : : * buffer pin client requests. In the event of an nbtree error the buffer
1051 : : * will certainly get marked as defined when the backend once again
1052 : : * acquires its first pin on the buffer. (Of course, if the backend never
1053 : : * touches the buffer again then it doesn't matter that it remains
1054 : : * non-accessible to Valgrind.)
1055 : : *
1056 : : * Note: When an IndexTuple C pointer gets computed using an ItemId read
1057 : : * from a page while a lock was held, the C pointer becomes unsafe to
1058 : : * dereference forever as soon as the lock is released. Valgrind can only
1059 : : * detect cases where the pointer gets dereferenced with no _current_
1060 : : * lock/pin held, though.
1061 : : */
1062 : 21087026 : if (!RelationUsesLocalBuffers(rel))
1063 : : VALGRIND_MAKE_MEM_DEFINED(BufferGetPage(buf), BLCKSZ);
1064 : 21087026 : }
1065 : :
1066 : : /*
1067 : : * _bt_unlockbuf() -- unlock a pinned buffer.
1068 : : */
1069 : : void
1070 : 21141329 : _bt_unlockbuf(Relation rel, Buffer buf)
1071 : : {
1072 : : /*
1073 : : * Buffer is pinned and locked, which means that it is expected to be
1074 : : * defined and addressable. Check that proactively.
1075 : : */
1076 : : VALGRIND_CHECK_MEM_IS_DEFINED(BufferGetPage(buf), BLCKSZ);
1077 : :
1078 : : /* LockBuffer() asserts that pin is held by this backend */
1079 : 21141329 : LockBuffer(buf, BUFFER_LOCK_UNLOCK);
1080 : :
1081 : 21141329 : if (!RelationUsesLocalBuffers(rel))
1082 : : VALGRIND_MAKE_MEM_NOACCESS(BufferGetPage(buf), BLCKSZ);
1083 : 21141329 : }
1084 : :
1085 : : /*
1086 : : * _bt_conditionallockbuf() -- conditionally BT_WRITE lock pinned
1087 : : * buffer.
1088 : : *
1089 : : * Note: Caller may need to call _bt_checkpage() with buf when pin on buf
1090 : : * wasn't originally acquired in _bt_getbuf() or _bt_relandgetbuf().
1091 : : */
1092 : : bool
1093 : 37258 : _bt_conditionallockbuf(Relation rel, Buffer buf)
1094 : : {
1095 : : /* ConditionalLockBuffer() asserts that pin is held by this backend */
1096 [ + + ]: 37258 : if (!ConditionalLockBuffer(buf))
1097 : 940 : return false;
1098 : :
1099 : 36318 : if (!RelationUsesLocalBuffers(rel))
1100 : : VALGRIND_MAKE_MEM_DEFINED(BufferGetPage(buf), BLCKSZ);
1101 : :
1102 : 36318 : return true;
1103 : : }
1104 : :
1105 : : /*
1106 : : * _bt_upgradelockbufcleanup() -- upgrade lock to a full cleanup lock.
1107 : : */
1108 : : void
1109 : 13110 : _bt_upgradelockbufcleanup(Relation rel, Buffer buf)
1110 : : {
1111 : : /*
1112 : : * Buffer is pinned and locked, which means that it is expected to be
1113 : : * defined and addressable. Check that proactively.
1114 : : */
1115 : : VALGRIND_CHECK_MEM_IS_DEFINED(BufferGetPage(buf), BLCKSZ);
1116 : :
1117 : : /* LockBuffer() asserts that pin is held by this backend */
1118 : 13110 : LockBuffer(buf, BUFFER_LOCK_UNLOCK);
1119 : 13110 : LockBufferForCleanup(buf);
10703 scrappy@hub.org 1120 : 13110 : }
1121 : :
1122 : : /*
1123 : : * _bt_pageinit() -- Initialize a new page.
1124 : : *
1125 : : * On return, the page header is initialized; data space is empty;
1126 : : * special space is zeroed out.
1127 : : */
1128 : : void
1129 : 85893 : _bt_pageinit(Page page, Size size)
1130 : : {
10278 bruce@momjian.us 1131 : 85893 : PageInit(page, size, sizeof(BTPageOpaqueData));
10703 scrappy@hub.org 1132 : 85893 : }
1133 : :
1134 : : /*
1135 : : * Delete item(s) from a btree leaf page during VACUUM.
1136 : : *
1137 : : * This routine assumes that the caller already has a full cleanup lock on
1138 : : * the buffer. Also, the given deletable and updatable arrays *must* be
1139 : : * sorted in ascending order.
1140 : : *
1141 : : * Routine deals with deleting TIDs when some (but not all) of the heap TIDs
1142 : : * in an existing posting list item are to be removed. This works by
1143 : : * updating/overwriting an existing item with caller's new version of the item
1144 : : * (a version that lacks the TIDs that are to be deleted).
1145 : : *
1146 : : * We record VACUUMs and b-tree deletes differently in WAL. Deletes must
1147 : : * generate their own snapshotConflictHorizon directly from the tableam,
1148 : : * whereas VACUUMs rely on the initial VACUUM table scan performing
1149 : : * WAL-logging that takes care of the issue for the table's indexes
1150 : : * indirectly. Also, we remove the VACUUM cycle ID from pages, which b-tree
1151 : : * deletes don't do.
1152 : : */
1153 : : void
5693 simon@2ndQuadrant.co 1154 : 8131 : _bt_delitems_vacuum(Relation rel, Buffer buf,
1155 : : OffsetNumber *deletable, int ndeletable,
1156 : : BTVacuumPosting *updatable, int nupdatable)
1157 : : {
3478 kgrittn@postgresql.o 1158 : 8131 : Page page = BufferGetPage(buf);
1159 : : BTPageOpaque opaque;
1749 pg@bowt.ie 1160 [ + + + + : 8131 : bool needswal = RelationNeedsWAL(rel);
+ - + - ]
2071 1161 : 8131 : char *updatedbuf = NULL;
1162 : 8131 : Size updatedbuflen = 0;
1163 : : OffsetNumber updatedoffsets[MaxIndexTuplesPerPage];
1164 : :
1165 : : /* Shouldn't be called unless there's something to do */
1166 [ + + - + ]: 8131 : Assert(ndeletable > 0 || nupdatable > 0);
1167 : :
1168 : : /* Generate new version of posting lists without deleted TIDs */
1749 1169 [ + + ]: 8131 : if (nupdatable > 0)
1170 : 916 : updatedbuf = _bt_delitems_update(updatable, nupdatable,
1171 : : updatedoffsets, &updatedbuflen,
1172 : : needswal);
1173 : :
1174 : : /* No ereport(ERROR) until changes are logged */
9055 tgl@sss.pgh.pa.us 1175 : 8131 : START_CRIT_SECTION();
1176 : :
1177 : : /*
1178 : : * Handle posting tuple updates.
1179 : : *
1180 : : * Deliberately do this before handling simple deletes. If we did it the
1181 : : * other way around (i.e. WAL record order -- simple deletes before
1182 : : * updates) then we'd have to make compensating changes to the 'updatable'
1183 : : * array of offset numbers.
1184 : : *
1185 : : * PageIndexTupleOverwrite() won't unset each item's LP_DEAD bit when it
1186 : : * happens to already be set. It's important that we not interfere with
1187 : : * any future simple index tuple deletion operations.
1188 : : */
2071 pg@bowt.ie 1189 [ + + ]: 30097 : for (int i = 0; i < nupdatable; i++)
1190 : : {
1191 : 21966 : OffsetNumber updatedoffset = updatedoffsets[i];
1192 : : IndexTuple itup;
1193 : : Size itemsz;
1194 : :
1195 : 21966 : itup = updatable[i]->itup;
1196 : 21966 : itemsz = MAXALIGN(IndexTupleSize(itup));
1 peter@eisentraut.org 1197 [ - + ]:GNC 21966 : if (!PageIndexTupleOverwrite(page, updatedoffset, itup, itemsz))
2071 pg@bowt.ie 1198 [ # # ]:UBC 0 : elog(PANIC, "failed to update partially dead item in block %u of index \"%s\"",
1199 : : BufferGetBlockNumber(buf), RelationGetRelationName(rel));
1200 : : }
1201 : :
1202 : : /* Now handle simple deletes of entire tuples */
2071 pg@bowt.ie 1203 [ + + ]:CBC 8131 : if (ndeletable > 0)
1204 : 7856 : PageIndexMultiDelete(page, deletable, ndeletable);
1205 : :
1206 : : /*
1207 : : * We can clear the vacuum cycle ID since this page has certainly been
1208 : : * processed by the current vacuum scan.
1209 : : */
1306 michael@paquier.xyz 1210 : 8131 : opaque = BTPageGetOpaque(page);
7113 tgl@sss.pgh.pa.us 1211 : 8131 : opaque->btpo_cycleid = 0;
1212 : :
1213 : : /*
1214 : : * Clear the BTP_HAS_GARBAGE page flag.
1215 : : *
1216 : : * This flag indicates the presence of LP_DEAD items on the page (though
1217 : : * not reliably). Note that we only rely on it with pg_upgrade'd
1218 : : * !heapkeyspace indexes. That's why clearing it here won't usually
1219 : : * interfere with simple index tuple deletion.
1220 : : */
7035 1221 : 8131 : opaque->btpo_flags &= ~BTP_HAS_GARBAGE;
1222 : :
5089 simon@2ndQuadrant.co 1223 : 8131 : MarkBufferDirty(buf);
1224 : :
1225 : : /* XLOG stuff */
1749 pg@bowt.ie 1226 [ + + ]: 8131 : if (needswal)
1227 : : {
1228 : : XLogRecPtr recptr;
1229 : : xl_btree_vacuum xlrec_vacuum;
1230 : :
2140 1231 : 8130 : xlrec_vacuum.ndeleted = ndeletable;
2071 1232 : 8130 : xlrec_vacuum.nupdated = nupdatable;
1233 : :
3995 heikki.linnakangas@i 1234 : 8130 : XLogBeginInsert();
1235 : 8130 : XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
259 peter@eisentraut.org 1236 : 8130 : XLogRegisterData(&xlrec_vacuum, SizeOfBtreeVacuum);
1237 : :
2071 pg@bowt.ie 1238 [ + + ]: 8130 : if (ndeletable > 0)
259 peter@eisentraut.org 1239 : 7855 : XLogRegisterBufData(0, deletable,
1240 : : ndeletable * sizeof(OffsetNumber));
1241 : :
2071 pg@bowt.ie 1242 [ + + ]: 8130 : if (nupdatable > 0)
1243 : : {
259 peter@eisentraut.org 1244 : 916 : XLogRegisterBufData(0, updatedoffsets,
1245 : : nupdatable * sizeof(OffsetNumber));
2071 pg@bowt.ie 1246 : 916 : XLogRegisterBufData(0, updatedbuf, updatedbuflen);
1247 : : }
1248 : :
3995 heikki.linnakangas@i 1249 : 8130 : recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_VACUUM);
1250 : :
5089 simon@2ndQuadrant.co 1251 : 8130 : PageSetLSN(page, recptr);
1252 : : }
1253 : :
5693 1254 [ - + ]: 8131 : END_CRIT_SECTION();
1255 : :
1256 : : /* can't leak memory here */
2071 pg@bowt.ie 1257 [ + + ]: 8131 : if (updatedbuf != NULL)
1258 : 916 : pfree(updatedbuf);
1259 : : /* free tuples allocated within _bt_delitems_update() */
1260 [ + + ]: 30097 : for (int i = 0; i < nupdatable; i++)
1261 : 21966 : pfree(updatable[i]->itup);
5693 simon@2ndQuadrant.co 1262 : 8131 : }
1263 : :
1264 : : /*
1265 : : * Delete item(s) from a btree leaf page during single-page cleanup.
1266 : : *
1267 : : * This routine assumes that the caller has pinned and write locked the
1268 : : * buffer. Also, the given deletable and updatable arrays *must* be sorted in
1269 : : * ascending order.
1270 : : *
1271 : : * Routine deals with deleting TIDs when some (but not all) of the heap TIDs
1272 : : * in an existing posting list item are to be removed. This works by
1273 : : * updating/overwriting an existing item with caller's new version of the item
1274 : : * (a version that lacks the TIDs that are to be deleted).
1275 : : *
1276 : : * This is nearly the same as _bt_delitems_vacuum as far as what it does to
1277 : : * the page, but it needs its own snapshotConflictHorizon and isCatalogRel
1278 : : * (from the tableam). This is used by the REDO routine to generate recovery
1279 : : * conflicts. The other difference is that only _bt_delitems_vacuum will
1280 : : * clear page's VACUUM cycle ID.
1281 : : */
1282 : : static void
871 pg@bowt.ie 1283 : 4030 : _bt_delitems_delete(Relation rel, Buffer buf,
1284 : : TransactionId snapshotConflictHorizon, bool isCatalogRel,
1285 : : OffsetNumber *deletable, int ndeletable,
1286 : : BTVacuumPosting *updatable, int nupdatable)
1287 : : {
3478 kgrittn@postgresql.o 1288 : 4030 : Page page = BufferGetPage(buf);
1289 : : BTPageOpaque opaque;
1749 pg@bowt.ie 1290 [ + - + + : 4030 : bool needswal = RelationNeedsWAL(rel);
+ + + - ]
1291 : 4030 : char *updatedbuf = NULL;
1292 : 4030 : Size updatedbuflen = 0;
1293 : : OffsetNumber updatedoffsets[MaxIndexTuplesPerPage];
1294 : :
1295 : : /* Shouldn't be called unless there's something to do */
1296 [ + + - + ]: 4030 : Assert(ndeletable > 0 || nupdatable > 0);
1297 : :
1298 : : /* Generate new versions of posting lists without deleted TIDs */
1299 [ + + ]: 4030 : if (nupdatable > 0)
1300 : 417 : updatedbuf = _bt_delitems_update(updatable, nupdatable,
1301 : : updatedoffsets, &updatedbuflen,
1302 : : needswal);
1303 : :
1304 : : /* No ereport(ERROR) until changes are logged */
5693 simon@2ndQuadrant.co 1305 : 4030 : START_CRIT_SECTION();
1306 : :
1307 : : /* Handle updates and deletes just like _bt_delitems_vacuum */
1749 pg@bowt.ie 1308 [ + + ]: 10076 : for (int i = 0; i < nupdatable; i++)
1309 : : {
1310 : 6046 : OffsetNumber updatedoffset = updatedoffsets[i];
1311 : : IndexTuple itup;
1312 : : Size itemsz;
1313 : :
1314 : 6046 : itup = updatable[i]->itup;
1315 : 6046 : itemsz = MAXALIGN(IndexTupleSize(itup));
1 peter@eisentraut.org 1316 [ - + ]:GNC 6046 : if (!PageIndexTupleOverwrite(page, updatedoffset, itup, itemsz))
1749 pg@bowt.ie 1317 [ # # ]:UBC 0 : elog(PANIC, "failed to update partially dead item in block %u of index \"%s\"",
1318 : : BufferGetBlockNumber(buf), RelationGetRelationName(rel));
1319 : : }
1320 : :
1749 pg@bowt.ie 1321 [ + + ]:CBC 4030 : if (ndeletable > 0)
1322 : 3954 : PageIndexMultiDelete(page, deletable, ndeletable);
1323 : :
1324 : : /*
1325 : : * Unlike _bt_delitems_vacuum, we *must not* clear the vacuum cycle ID at
1326 : : * this point. The VACUUM command alone controls vacuum cycle IDs.
1327 : : */
1306 michael@paquier.xyz 1328 : 4030 : opaque = BTPageGetOpaque(page);
1329 : :
1330 : : /*
1331 : : * Clear the BTP_HAS_GARBAGE page flag.
1332 : : *
1333 : : * This flag indicates the presence of LP_DEAD items on the page (though
1334 : : * not reliably). Note that we only rely on it with pg_upgrade'd
1335 : : * !heapkeyspace indexes.
1336 : : */
5693 simon@2ndQuadrant.co 1337 : 4030 : opaque->btpo_flags &= ~BTP_HAS_GARBAGE;
1338 : :
1339 : 4030 : MarkBufferDirty(buf);
1340 : :
1341 : : /* XLOG stuff */
1749 pg@bowt.ie 1342 [ + + ]: 4030 : if (needswal)
1343 : : {
1344 : : XLogRecPtr recptr;
1345 : : xl_btree_delete xlrec_delete;
1346 : :
1076 1347 : 4006 : xlrec_delete.snapshotConflictHorizon = snapshotConflictHorizon;
2125 1348 : 4006 : xlrec_delete.ndeleted = ndeletable;
1749 1349 : 4006 : xlrec_delete.nupdated = nupdatable;
871 1350 : 4006 : xlrec_delete.isCatalogRel = isCatalogRel;
1351 : :
3995 heikki.linnakangas@i 1352 : 4006 : XLogBeginInsert();
1353 : 4006 : XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
259 peter@eisentraut.org 1354 : 4006 : XLogRegisterData(&xlrec_delete, SizeOfBtreeDelete);
1355 : :
1749 pg@bowt.ie 1356 [ + + ]: 4006 : if (ndeletable > 0)
259 peter@eisentraut.org 1357 : 3930 : XLogRegisterBufData(0, deletable,
1358 : : ndeletable * sizeof(OffsetNumber));
1359 : :
1749 pg@bowt.ie 1360 [ + + ]: 4006 : if (nupdatable > 0)
1361 : : {
259 peter@eisentraut.org 1362 : 417 : XLogRegisterBufData(0, updatedoffsets,
1363 : : nupdatable * sizeof(OffsetNumber));
1749 pg@bowt.ie 1364 : 417 : XLogRegisterBufData(0, updatedbuf, updatedbuflen);
1365 : : }
1366 : :
3995 heikki.linnakangas@i 1367 : 4006 : recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_DELETE);
1368 : :
9155 vadim4o@yahoo.com 1369 : 4006 : PageSetLSN(page, recptr);
1370 : : }
1371 : :
8871 tgl@sss.pgh.pa.us 1372 [ - + ]: 4030 : END_CRIT_SECTION();
1373 : :
1374 : : /* can't leak memory here */
1749 pg@bowt.ie 1375 [ + + ]: 4030 : if (updatedbuf != NULL)
1376 : 417 : pfree(updatedbuf);
1377 : : /* free tuples allocated within _bt_delitems_update() */
1378 [ + + ]: 10076 : for (int i = 0; i < nupdatable; i++)
1379 : 6046 : pfree(updatable[i]->itup);
10703 scrappy@hub.org 1380 : 4030 : }
1381 : :
1382 : : /*
1383 : : * Set up state needed to delete TIDs from posting list tuples via "updating"
1384 : : * the tuple. Performs steps common to both _bt_delitems_vacuum and
1385 : : * _bt_delitems_delete. These steps must take place before each function's
1386 : : * critical section begins.
1387 : : *
1388 : : * updatable and nupdatable are inputs, though note that we will use
1389 : : * _bt_update_posting() to replace the original itup with a pointer to a final
1390 : : * version in palloc()'d memory. Caller should free the tuples when its done.
1391 : : *
1392 : : * The first nupdatable entries from updatedoffsets are set to the page offset
1393 : : * number for posting list tuples that caller updates. This is mostly useful
1394 : : * because caller may need to WAL-log the page offsets (though we always do
1395 : : * this for caller out of convenience).
1396 : : *
1397 : : * Returns buffer consisting of an array of xl_btree_update structs that
1398 : : * describe the steps we perform here for caller (though only when needswal is
1399 : : * true). Also sets *updatedbuflen to the final size of the buffer. This
1400 : : * buffer is used by caller when WAL logging is required.
1401 : : */
1402 : : static char *
1749 pg@bowt.ie 1403 : 1333 : _bt_delitems_update(BTVacuumPosting *updatable, int nupdatable,
1404 : : OffsetNumber *updatedoffsets, Size *updatedbuflen,
1405 : : bool needswal)
1406 : : {
1407 : 1333 : char *updatedbuf = NULL;
1408 : 1333 : Size buflen = 0;
1409 : :
1410 : : /* Shouldn't be called unless there's something to do */
1411 [ - + ]: 1333 : Assert(nupdatable > 0);
1412 : :
1413 [ + + ]: 29345 : for (int i = 0; i < nupdatable; i++)
1414 : : {
1415 : 28012 : BTVacuumPosting vacposting = updatable[i];
1416 : : Size itemsz;
1417 : :
1418 : : /* Replace work area IndexTuple with updated version */
1419 : 28012 : _bt_update_posting(vacposting);
1420 : :
1421 : : /* Keep track of size of xl_btree_update for updatedbuf in passing */
1422 : 28012 : itemsz = SizeOfBtreeUpdate + vacposting->ndeletedtids * sizeof(uint16);
1423 : 28012 : buflen += itemsz;
1424 : :
1425 : : /* Build updatedoffsets buffer in passing */
1426 : 28012 : updatedoffsets[i] = vacposting->updatedoffset;
1427 : : }
1428 : :
1429 : : /* XLOG stuff */
1430 [ + - ]: 1333 : if (needswal)
1431 : : {
1432 : 1333 : Size offset = 0;
1433 : :
1434 : : /* Allocate, set final size for caller */
1435 : 1333 : updatedbuf = palloc(buflen);
1436 : 1333 : *updatedbuflen = buflen;
1437 [ + + ]: 29345 : for (int i = 0; i < nupdatable; i++)
1438 : : {
1439 : 28012 : BTVacuumPosting vacposting = updatable[i];
1440 : : Size itemsz;
1441 : : xl_btree_update update;
1442 : :
1443 : 28012 : update.ndeletedtids = vacposting->ndeletedtids;
1444 : 28012 : memcpy(updatedbuf + offset, &update.ndeletedtids,
1445 : : SizeOfBtreeUpdate);
1446 : 28012 : offset += SizeOfBtreeUpdate;
1447 : :
1448 : 28012 : itemsz = update.ndeletedtids * sizeof(uint16);
1449 : 28012 : memcpy(updatedbuf + offset, vacposting->deletetids, itemsz);
1450 : 28012 : offset += itemsz;
1451 : : }
1452 : : }
1453 : :
1454 : 1333 : return updatedbuf;
1455 : : }
1456 : :
1457 : : /*
1458 : : * Comparator used by _bt_delitems_delete_check() to restore deltids array
1459 : : * back to its original leaf-page-wise sort order
1460 : : */
1461 : : static int
1462 : 2546009 : _bt_delitems_cmp(const void *a, const void *b)
1463 : : {
1464 : 2546009 : TM_IndexDelete *indexdelete1 = (TM_IndexDelete *) a;
1465 : 2546009 : TM_IndexDelete *indexdelete2 = (TM_IndexDelete *) b;
1466 : :
620 nathan@postgresql.or 1467 [ - + ]: 2546009 : Assert(indexdelete1->id != indexdelete2->id);
1468 : :
1469 : 2546009 : return pg_cmp_s16(indexdelete1->id, indexdelete2->id);
1470 : : }
1471 : :
1472 : : /*
1473 : : * Try to delete item(s) from a btree leaf page during single-page cleanup.
1474 : : *
1475 : : * nbtree interface to table_index_delete_tuples(). Deletes a subset of index
1476 : : * tuples from caller's deltids array: those whose TIDs are found safe to
1477 : : * delete by the tableam (or already marked LP_DEAD in index, and so already
1478 : : * known to be deletable by our simple index deletion caller). We physically
1479 : : * delete index tuples from buf leaf page last of all (for index tuples where
1480 : : * that is known to be safe following our table_index_delete_tuples() call).
1481 : : *
1482 : : * Simple index deletion caller only includes TIDs from index tuples marked
1483 : : * LP_DEAD, as well as extra TIDs it found on the same leaf page that can be
1484 : : * included without increasing the total number of distinct table blocks for
1485 : : * the deletion operation as a whole. This approach often allows us to delete
1486 : : * some extra index tuples that were practically free for tableam to check in
1487 : : * passing (when they actually turn out to be safe to delete). It probably
1488 : : * only makes sense for the tableam to go ahead with these extra checks when
1489 : : * it is block-oriented (otherwise the checks probably won't be practically
1490 : : * free, which we rely on). The tableam interface requires the tableam side
1491 : : * to handle the problem, though, so this is okay (we as an index AM are free
1492 : : * to make the simplifying assumption that all tableams must be block-based).
1493 : : *
1494 : : * Bottom-up index deletion caller provides all the TIDs from the leaf page,
1495 : : * without expecting that tableam will check most of them. The tableam has
1496 : : * considerable discretion around which entries/blocks it checks. Our role in
1497 : : * costing the bottom-up deletion operation is strictly advisory.
1498 : : *
1499 : : * Note: Caller must have added deltids entries (i.e. entries that go in
1500 : : * delstate's main array) in leaf-page-wise order: page offset number order,
1501 : : * TID order among entries taken from the same posting list tuple (tiebreak on
1502 : : * TID). This order is convenient to work with here.
1503 : : *
1504 : : * Note: We also rely on the id field of each deltids element "capturing" this
1505 : : * original leaf-page-wise order. That is, we expect to be able to get back
1506 : : * to the original leaf-page-wise order just by sorting deltids on the id
1507 : : * field (tableam will sort deltids for its own reasons, so we'll need to put
1508 : : * it back in leaf-page-wise order afterwards).
1509 : : */
1510 : : void
1749 pg@bowt.ie 1511 : 5591 : _bt_delitems_delete_check(Relation rel, Buffer buf, Relation heapRel,
1512 : : TM_IndexDeleteOp *delstate)
1513 : : {
1514 : 5591 : Page page = BufferGetPage(buf);
1515 : : TransactionId snapshotConflictHorizon;
1516 : : bool isCatalogRel;
1517 : 5591 : OffsetNumber postingidxoffnum = InvalidOffsetNumber;
1518 : 5591 : int ndeletable = 0,
1519 : 5591 : nupdatable = 0;
1520 : : OffsetNumber deletable[MaxIndexTuplesPerPage];
1521 : : BTVacuumPosting updatable[MaxIndexTuplesPerPage];
1522 : :
1523 : : /* Use tableam interface to determine which tuples to delete first */
1076 1524 : 5591 : snapshotConflictHorizon = table_index_delete_tuples(heapRel, delstate);
871 1525 [ + + + - : 5591 : isCatalogRel = RelationIsAccessibleInLogicalDecoding(heapRel);
- + - - -
- + + - +
- - - - -
- ]
1526 : :
1527 : : /* Should not WAL-log snapshotConflictHorizon unless it's required */
1076 1528 [ + + ]: 5591 : if (!XLogStandbyInfoActive())
1529 : 1557 : snapshotConflictHorizon = InvalidTransactionId;
1530 : :
1531 : : /*
1532 : : * Construct a leaf-page-wise description of what _bt_delitems_delete()
1533 : : * needs to do to physically delete index tuples from the page.
1534 : : *
1535 : : * Must sort deltids array to restore leaf-page-wise order (original order
1536 : : * before call to tableam). This is the order that the loop expects.
1537 : : *
1538 : : * Note that deltids array might be a lot smaller now. It might even have
1539 : : * no entries at all (with bottom-up deletion caller), in which case there
1540 : : * is nothing left to do.
1541 : : */
1749 1542 : 5591 : qsort(delstate->deltids, delstate->ndeltids, sizeof(TM_IndexDelete),
1543 : : _bt_delitems_cmp);
1544 [ + + ]: 5591 : if (delstate->ndeltids == 0)
1545 : : {
1546 [ - + ]: 1561 : Assert(delstate->bottomup);
1547 : 1561 : return;
1548 : : }
1549 : :
1550 : : /* We definitely have to delete at least one index tuple (or one TID) */
1551 [ + + ]: 371507 : for (int i = 0; i < delstate->ndeltids; i++)
1552 : : {
1553 : 367477 : TM_IndexStatus *dstatus = delstate->status + delstate->deltids[i].id;
1554 : 367477 : OffsetNumber idxoffnum = dstatus->idxoffnum;
1555 : 367477 : ItemId itemid = PageGetItemId(page, idxoffnum);
1556 : 367477 : IndexTuple itup = (IndexTuple) PageGetItem(page, itemid);
1557 : : int nestedi,
1558 : : nitem;
1559 : : BTVacuumPosting vacposting;
1560 : :
1561 [ + - + - : 367477 : Assert(OffsetNumberIsValid(idxoffnum));
- + ]
1562 : :
1563 [ + + ]: 367477 : if (idxoffnum == postingidxoffnum)
1564 : : {
1565 : : /*
1566 : : * This deltid entry is a TID from a posting list tuple that has
1567 : : * already been completely processed
1568 : : */
1569 [ - + ]: 13675 : Assert(BTreeTupleIsPosting(itup));
1570 [ - + ]: 13675 : Assert(ItemPointerCompare(BTreeTupleGetHeapTID(itup),
1571 : : &delstate->deltids[i].tid) < 0);
1572 [ - + ]: 13675 : Assert(ItemPointerCompare(BTreeTupleGetMaxHeapTID(itup),
1573 : : &delstate->deltids[i].tid) >= 0);
1574 : 13675 : continue;
1575 : : }
1576 : :
1577 [ + + ]: 353802 : if (!BTreeTupleIsPosting(itup))
1578 : : {
1579 : : /* Plain non-pivot tuple */
1580 [ - + ]: 339967 : Assert(ItemPointerEquals(&itup->t_tid, &delstate->deltids[i].tid));
1581 [ + + ]: 339967 : if (dstatus->knowndeletable)
1582 : 270692 : deletable[ndeletable++] = idxoffnum;
1583 : 339967 : continue;
1584 : : }
1585 : :
1586 : : /*
1587 : : * itup is a posting list tuple whose lowest deltids entry (which may
1588 : : * or may not be for the first TID from itup) is considered here now.
1589 : : * We should process all of the deltids entries for the posting list
1590 : : * together now, though (not just the lowest). Remember to skip over
1591 : : * later itup-related entries during later iterations of outermost
1592 : : * loop.
1593 : : */
1594 : 13835 : postingidxoffnum = idxoffnum; /* Remember work in outermost loop */
1595 : 13835 : nestedi = i; /* Initialize for first itup deltids entry */
1596 : 13835 : vacposting = NULL; /* Describes final action for itup */
1597 : 13835 : nitem = BTreeTupleGetNPosting(itup);
1598 [ + + ]: 63854 : for (int p = 0; p < nitem; p++)
1599 : : {
1600 : 50019 : ItemPointer ptid = BTreeTupleGetPostingN(itup, p);
1601 : 50019 : int ptidcmp = -1;
1602 : :
1603 : : /*
1604 : : * This nested loop reuses work across ptid TIDs taken from itup.
1605 : : * We take advantage of the fact that both itup's TIDs and deltids
1606 : : * entries (within a single itup/posting list grouping) must both
1607 : : * be in ascending TID order.
1608 : : */
1609 [ + + ]: 69473 : for (; nestedi < delstate->ndeltids; nestedi++)
1610 : : {
1611 : 66711 : TM_IndexDelete *tcdeltid = &delstate->deltids[nestedi];
1612 : 66711 : TM_IndexStatus *tdstatus = (delstate->status + tcdeltid->id);
1613 : :
1614 : : /* Stop once we get past all itup related deltids entries */
1615 [ - + ]: 66711 : Assert(tdstatus->idxoffnum >= idxoffnum);
1616 [ + + ]: 66711 : if (tdstatus->idxoffnum != idxoffnum)
1617 : 16183 : break;
1618 : :
1619 : : /* Skip past non-deletable itup related entries up front */
1620 [ + + ]: 50528 : if (!tdstatus->knowndeletable)
1621 : 4229 : continue;
1622 : :
1623 : : /* Entry is first partial ptid match (or an exact match)? */
1624 : 46299 : ptidcmp = ItemPointerCompare(&tcdeltid->tid, ptid);
1625 [ + + ]: 46299 : if (ptidcmp >= 0)
1626 : : {
1627 : : /* Greater than or equal (partial or exact) match... */
1628 : 31074 : break;
1629 : : }
1630 : : }
1631 : :
1632 : : /* ...exact ptid match to a deletable deltids entry? */
1633 [ + + ]: 50019 : if (ptidcmp != 0)
1634 : 26738 : continue;
1635 : :
1636 : : /* Exact match for deletable deltids entry -- ptid gets deleted */
1637 [ + + ]: 23281 : if (vacposting == NULL)
1638 : : {
1639 : 12493 : vacposting = palloc(offsetof(BTVacuumPostingData, deletetids) +
1640 : : nitem * sizeof(uint16));
1641 : 12493 : vacposting->itup = itup;
1642 : 12493 : vacposting->updatedoffset = idxoffnum;
1643 : 12493 : vacposting->ndeletedtids = 0;
1644 : : }
1645 : 23281 : vacposting->deletetids[vacposting->ndeletedtids++] = p;
1646 : : }
1647 : :
1648 : : /* Final decision on itup, a posting list tuple */
1649 : :
1650 [ + + ]: 13835 : if (vacposting == NULL)
1651 : : {
1652 : : /* No TIDs to delete from itup -- do nothing */
1653 : : }
1654 [ + + ]: 12493 : else if (vacposting->ndeletedtids == nitem)
1655 : : {
1656 : : /* Straight delete of itup (to delete all TIDs) */
1657 : 6447 : deletable[ndeletable++] = idxoffnum;
1658 : : /* Turns out we won't need granular information */
1659 : 6447 : pfree(vacposting);
1660 : : }
1661 : : else
1662 : : {
1663 : : /* Delete some (but not all) TIDs from itup */
1664 [ + - - + ]: 6046 : Assert(vacposting->ndeletedtids > 0 &&
1665 : : vacposting->ndeletedtids < nitem);
1666 : 6046 : updatable[nupdatable++] = vacposting;
1667 : : }
1668 : : }
1669 : :
1670 : : /* Physically delete tuples (or TIDs) using deletable (or updatable) */
871 1671 : 4030 : _bt_delitems_delete(rel, buf, snapshotConflictHorizon, isCatalogRel,
1672 : : deletable, ndeletable, updatable, nupdatable);
1673 : :
1674 : : /* be tidy */
1749 1675 [ + + ]: 10076 : for (int i = 0; i < nupdatable; i++)
1676 : 6046 : pfree(updatable[i]);
1677 : : }
1678 : :
1679 : : /*
1680 : : * Check that leftsib page (the btpo_prev of target page) is not marked with
1681 : : * INCOMPLETE_SPLIT flag. Used during page deletion.
1682 : : *
1683 : : * Returning true indicates that page flag is set in leftsib (which is
1684 : : * definitely still the left sibling of target). When that happens, the
1685 : : * target doesn't have a downlink in parent, and the page deletion algorithm
1686 : : * isn't prepared to handle that. Deletion of the target page (or the whole
1687 : : * subtree that contains the target page) cannot take place.
1688 : : *
1689 : : * Caller should not have a lock on the target page itself, since pages on the
1690 : : * same level must always be locked left to right to avoid deadlocks.
1691 : : */
1692 : : static bool
871 1693 : 3096 : _bt_leftsib_splitflag(Relation rel, BlockNumber leftsib, BlockNumber target)
1694 : : {
1695 : : Buffer buf;
1696 : : Page page;
1697 : : BTPageOpaque opaque;
1698 : : bool result;
1699 : :
1700 : : /* Easy case: No left sibling */
2000 1701 [ + + ]: 3096 : if (leftsib == P_NONE)
1702 : 2295 : return false;
1703 : :
871 1704 : 801 : buf = _bt_getbuf(rel, leftsib, BT_READ);
2000 1705 : 801 : page = BufferGetPage(buf);
1306 michael@paquier.xyz 1706 : 801 : opaque = BTPageGetOpaque(page);
1707 : :
1708 : : /*
1709 : : * If the left sibling was concurrently split, so that its next-pointer
1710 : : * doesn't point to the current page anymore, the split that created
1711 : : * target must be completed. Caller can reasonably expect that there will
1712 : : * be a downlink to the target page that it can relocate using its stack.
1713 : : * (We don't allow splitting an incompletely split page again until the
1714 : : * previous split has been completed.)
1715 : : */
2000 pg@bowt.ie 1716 [ + - - + ]: 801 : result = (opaque->btpo_next == target && P_INCOMPLETE_SPLIT(opaque));
1717 : 801 : _bt_relbuf(rel, buf);
1718 : :
1719 : 801 : return result;
1720 : : }
1721 : :
1722 : : /*
1723 : : * Check that leafrightsib page (the btpo_next of target leaf page) is not
1724 : : * marked with ISHALFDEAD flag. Used during page deletion.
1725 : : *
1726 : : * Returning true indicates that page flag is set in leafrightsib, so page
1727 : : * deletion cannot go ahead. Our caller is not prepared to deal with the case
1728 : : * where the parent page does not have a pivot tuples whose downlink points to
1729 : : * leafrightsib (due to an earlier interrupted VACUUM operation). It doesn't
1730 : : * seem worth going to the trouble of teaching our caller to deal with it.
1731 : : * The situation will be resolved after VACUUM finishes the deletion of the
1732 : : * half-dead page (when a future VACUUM operation reaches the target page
1733 : : * again).
1734 : : *
1735 : : * _bt_leftsib_splitflag() is called for both leaf pages and internal pages.
1736 : : * _bt_rightsib_halfdeadflag() is only called for leaf pages, though. This is
1737 : : * okay because of the restriction on deleting pages that are the rightmost
1738 : : * page of their parent (i.e. that such deletions can only take place when the
1739 : : * entire subtree must be deleted). The leaf level check made here will apply
1740 : : * to a right "cousin" leaf page rather than a simple right sibling leaf page
1741 : : * in cases where caller actually goes on to attempt deleting pages that are
1742 : : * above the leaf page. The right cousin leaf page is representative of the
1743 : : * left edge of the subtree to the right of the to-be-deleted subtree as a
1744 : : * whole, which is exactly the condition that our caller cares about.
1745 : : * (Besides, internal pages are never marked half-dead, so it isn't even
1746 : : * possible to _directly_ assess if an internal page is part of some other
1747 : : * to-be-deleted subtree.)
1748 : : */
1749 : : static bool
871 1750 : 2977 : _bt_rightsib_halfdeadflag(Relation rel, BlockNumber leafrightsib)
1751 : : {
1752 : : Buffer buf;
1753 : : Page page;
1754 : : BTPageOpaque opaque;
1755 : : bool result;
1756 : :
2000 1757 [ - + ]: 2977 : Assert(leafrightsib != P_NONE);
1758 : :
871 1759 : 2977 : buf = _bt_getbuf(rel, leafrightsib, BT_READ);
3478 kgrittn@postgresql.o 1760 : 2977 : page = BufferGetPage(buf);
1306 michael@paquier.xyz 1761 : 2977 : opaque = BTPageGetOpaque(page);
1762 : :
2000 pg@bowt.ie 1763 [ + - - + ]: 2977 : Assert(P_ISLEAF(opaque) && !P_ISDELETED(opaque));
4174 heikki.linnakangas@i 1764 : 2977 : result = P_ISHALFDEAD(opaque);
1765 : 2977 : _bt_relbuf(rel, buf);
1766 : :
1767 : 2977 : return result;
1768 : : }
1769 : :
1770 : : /*
1771 : : * _bt_pagedel() -- Delete a leaf page from the b-tree, if legal to do so.
1772 : : *
1773 : : * This action unlinks the leaf page from the b-tree structure, removing all
1774 : : * pointers leading to it --- but not touching its own left and right links.
1775 : : * The page cannot be physically reclaimed right away, since other processes
1776 : : * may currently be trying to follow links leading to the page; they have to
1777 : : * be allowed to use its right-link to recover. See nbtree/README.
1778 : : *
1779 : : * On entry, the target buffer must be pinned and locked (either read or write
1780 : : * lock is OK). The page must be an empty leaf page, which may be half-dead
1781 : : * already (a half-dead page should only be passed to us when an earlier
1782 : : * VACUUM operation was interrupted, though). Note in particular that caller
1783 : : * should never pass a buffer containing an existing deleted page here. The
1784 : : * lock and pin on caller's buffer will be dropped before we return.
1785 : : *
1786 : : * Maintains bulk delete stats for caller, which are taken from vstate. We
1787 : : * need to cooperate closely with caller here so that whole VACUUM operation
1788 : : * reliably avoids any double counting of subsidiary-to-leafbuf pages that we
1789 : : * delete in passing. If such pages happen to be from a block number that is
1790 : : * ahead of the current scanblkno position, then caller is expected to count
1791 : : * them directly later on. It's simpler for us to understand caller's
1792 : : * requirements than it would be for caller to understand when or how a
1793 : : * deleted page became deleted after the fact.
1794 : : *
1795 : : * NOTE: this leaks memory. Rather than trying to clean up everything
1796 : : * carefully, it's better to run it in a temp context that can be reset
1797 : : * frequently.
1798 : : */
1799 : : void
1706 pg@bowt.ie 1800 : 3068 : _bt_pagedel(Relation rel, Buffer leafbuf, BTVacState *vstate)
1801 : : {
1802 : : BlockNumber rightsib;
1803 : : bool rightsib_empty;
1804 : : Page page;
1805 : : BTPageOpaque opaque;
1806 : :
1807 : : /*
1808 : : * Save original leafbuf block number from caller. Only deleted blocks
1809 : : * that are <= scanblkno are added to bulk delete stat's pages_deleted
1810 : : * count.
1811 : : */
2006 1812 : 3068 : BlockNumber scanblkno = BufferGetBlockNumber(leafbuf);
1813 : :
1814 : : /*
1815 : : * "stack" is a search stack leading (approximately) to the target page.
1816 : : * It is initially NULL, but when iterating, we keep it to avoid
1817 : : * duplicated search effort.
1818 : : *
1819 : : * Also, when "stack" is not NULL, we have already checked that the
1820 : : * current page is not the right half of an incomplete split, i.e. the
1821 : : * left sibling does not have its INCOMPLETE_SPLIT flag set, including
1822 : : * when the current target page is to the right of caller's initial page
1823 : : * (the scanblkno page).
1824 : : */
4246 heikki.linnakangas@i 1825 : 3068 : BTStack stack = NULL;
1826 : :
1827 : : for (;;)
1828 : : {
2006 pg@bowt.ie 1829 : 6046 : page = BufferGetPage(leafbuf);
1306 michael@paquier.xyz 1830 : 6046 : opaque = BTPageGetOpaque(page);
1831 : :
1832 : : /*
1833 : : * Internal pages are never deleted directly, only as part of deleting
1834 : : * the whole subtree all the way down to leaf level.
1835 : : *
1836 : : * Also check for deleted pages here. Caller never passes us a fully
1837 : : * deleted page. Only VACUUM can delete pages, so there can't have
1838 : : * been a concurrent deletion. Assume that we reached any deleted
1839 : : * page encountered here by following a sibling link, and that the
1840 : : * index is corrupt.
1841 : : */
2006 pg@bowt.ie 1842 [ - + ]: 6046 : Assert(!P_ISDELETED(opaque));
1843 [ + - - + ]: 6046 : if (!P_ISLEAF(opaque) || P_ISDELETED(opaque))
1844 : : {
1845 : : /*
1846 : : * Pre-9.4 page deletion only marked internal pages as half-dead,
1847 : : * but now we only use that flag on leaf pages. The old algorithm
1848 : : * was never supposed to leave half-dead pages in the tree, it was
1849 : : * just a transient state, but it was nevertheless possible in
1850 : : * error scenarios. We don't know how to deal with them here. They
1851 : : * are harmless as far as searches are considered, but inserts
1852 : : * into the deleted keyspace could add out-of-order downlinks in
1853 : : * the upper levels. Log a notice, hopefully the admin will notice
1854 : : * and reindex.
1855 : : */
4246 heikki.linnakangas@i 1856 [ # # ]:UBC 0 : if (P_ISHALFDEAD(opaque))
1857 [ # # ]: 0 : ereport(LOG,
1858 : : (errcode(ERRCODE_INDEX_CORRUPTED),
1859 : : errmsg("index \"%s\" contains a half-dead internal page",
1860 : : RelationGetRelationName(rel)),
1861 : : errhint("This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));
1862 : :
2006 pg@bowt.ie 1863 [ # # ]: 0 : if (P_ISDELETED(opaque))
1864 [ # # ]: 0 : ereport(LOG,
1865 : : (errcode(ERRCODE_INDEX_CORRUPTED),
1866 : : errmsg_internal("found deleted block %u while following right link from block %u in index \"%s\"",
1867 : : BufferGetBlockNumber(leafbuf),
1868 : : scanblkno,
1869 : : RelationGetRelationName(rel))));
1870 : :
1871 : 0 : _bt_relbuf(rel, leafbuf);
1706 pg@bowt.ie 1872 :CBC 100 : return;
1873 : : }
1874 : :
1875 : : /*
1876 : : * We can never delete rightmost pages nor root pages. While at it,
1877 : : * check that page is empty, since it's possible that the leafbuf page
1878 : : * was empty a moment ago, but has since had some inserts.
1879 : : *
1880 : : * To keep the algorithm simple, we also never delete an incompletely
1881 : : * split page (they should be rare enough that this doesn't make any
1882 : : * meaningful difference to disk usage):
1883 : : *
1884 : : * The INCOMPLETE_SPLIT flag on the page tells us if the page is the
1885 : : * left half of an incomplete split, but ensuring that it's not the
1886 : : * right half is more complicated. For that, we have to check that
1887 : : * the left sibling doesn't have its INCOMPLETE_SPLIT flag set using
1888 : : * _bt_leftsib_splitflag(). On the first iteration, we temporarily
1889 : : * release the lock on scanblkno/leafbuf, check the left sibling, and
1890 : : * construct a search stack to scanblkno. On subsequent iterations,
1891 : : * we know we stepped right from a page that passed these tests, so
1892 : : * it's OK.
1893 : : */
2006 1894 [ + + + - ]: 6046 : if (P_RIGHTMOST(opaque) || P_ISROOT(opaque) ||
4242 heikki.linnakangas@i 1895 [ - + + - ]: 5950 : P_FIRSTDATAKEY(opaque) <= PageGetMaxOffsetNumber(page) ||
1896 [ - + ]: 5950 : P_INCOMPLETE_SPLIT(opaque))
1897 : : {
1898 : : /* Should never fail to delete a half-dead page */
4246 1899 [ - + ]: 96 : Assert(!P_ISHALFDEAD(opaque));
1900 : :
2006 pg@bowt.ie 1901 : 96 : _bt_relbuf(rel, leafbuf);
1706 1902 : 96 : return;
1903 : : }
1904 : :
1905 : : /*
1906 : : * First, remove downlink pointing to the page (or a parent of the
1907 : : * page, if we are going to delete a taller subtree), and mark the
1908 : : * leafbuf page half-dead
1909 : : */
4246 heikki.linnakangas@i 1910 [ + - ]: 5950 : if (!P_ISHALFDEAD(opaque))
1911 : : {
1912 : : /*
1913 : : * We need an approximate pointer to the page's parent page. We
1914 : : * use a variant of the standard search mechanism to search for
1915 : : * the page's high key; this will give us a link to either the
1916 : : * current parent or someplace to its left (if there are multiple
1917 : : * equal high keys, which is possible with !heapkeyspace indexes).
1918 : : *
1919 : : * Also check if this is the right-half of an incomplete split
1920 : : * (see comment above).
1921 : : */
1922 [ + + ]: 5950 : if (!stack)
1923 : 2973 : {
1924 : : BTScanInsert itup_key;
1925 : : ItemId itemid;
1926 : : IndexTuple targetkey;
1927 : : BlockNumber leftsib,
1928 : : leafblkno;
1929 : : Buffer sleafbuf;
1930 : :
1931 : 2973 : itemid = PageGetItemId(page, P_HIKEY);
1932 : 2973 : targetkey = CopyIndexTuple((IndexTuple) PageGetItem(page, itemid));
1933 : :
4242 1934 : 2973 : leftsib = opaque->btpo_prev;
1996 pg@bowt.ie 1935 : 2973 : leafblkno = BufferGetBlockNumber(leafbuf);
1936 : :
1937 : : /*
1938 : : * To avoid deadlocks, we'd better drop the leaf page lock
1939 : : * before going further.
1940 : : */
1925 1941 : 2973 : _bt_unlockbuf(rel, leafbuf);
1942 : :
1943 : : /*
1944 : : * Check that the left sibling of leafbuf (if any) is not
1945 : : * marked with INCOMPLETE_SPLIT flag before proceeding
1946 : : */
1996 1947 [ - + ]: 2973 : Assert(leafblkno == scanblkno);
871 1948 [ - + ]: 2973 : if (_bt_leftsib_splitflag(rel, leftsib, leafblkno))
1949 : : {
2000 pg@bowt.ie 1950 :UBC 0 : ReleaseBuffer(leafbuf);
1706 1951 : 0 : return;
1952 : : }
1953 : :
1954 : : /*
1955 : : * We need an insertion scan key, so build one.
1956 : : *
1957 : : * _bt_search searches for the leaf page that contains any
1958 : : * matching non-pivot tuples, but we need it to "search" for
1959 : : * the high key pivot from the page that we're set to delete.
1960 : : * Compensate for the mismatch by having _bt_search locate the
1961 : : * last position < equal-to-untruncated-prefix non-pivots.
1962 : : */
871 pg@bowt.ie 1963 :CBC 2973 : itup_key = _bt_mkscankey(rel, targetkey);
1964 : :
1965 : : /* Set up a BTLessStrategyNumber-like insertion scan key */
690 1966 : 2973 : itup_key->nextkey = false;
1967 : 2973 : itup_key->backward = true;
781 tmunro@postgresql.or 1968 : 2973 : stack = _bt_search(rel, NULL, itup_key, &sleafbuf, BT_READ);
1969 : : /* won't need a second lock or pin on leafbuf */
1996 pg@bowt.ie 1970 : 2973 : _bt_relbuf(rel, sleafbuf);
1971 : :
1972 : : /*
1973 : : * Re-lock the leaf page, and start over to use our stack
1974 : : * within _bt_mark_page_halfdead. We must do it that way
1975 : : * because it's possible that leafbuf can no longer be
1976 : : * deleted. We need to recheck.
1977 : : *
1978 : : * Note: We can't simply hold on to the sleafbuf lock instead,
1979 : : * because it's barely possible that sleafbuf is not the same
1980 : : * page as leafbuf. This happens when leafbuf split after our
1981 : : * original lock was dropped, but before _bt_search finished
1982 : : * its descent. We rely on the assumption that we'll find
1983 : : * leafbuf isn't safe to delete anymore in this scenario.
1984 : : * (Page deletion can cope with the stack being to the left of
1985 : : * leafbuf, but not to the right of leafbuf.)
1986 : : */
1925 1987 : 2973 : _bt_lockbuf(rel, leafbuf, BT_WRITE);
4246 heikki.linnakangas@i 1988 : 2973 : continue;
1989 : : }
1990 : :
1991 : : /*
1992 : : * See if it's safe to delete the leaf page, and determine how
1993 : : * many parent/internal pages above the leaf level will be
1994 : : * deleted. If it's safe then _bt_mark_page_halfdead will also
1995 : : * perform the first phase of deletion, which includes marking the
1996 : : * leafbuf page half-dead.
1997 : : */
2006 pg@bowt.ie 1998 [ + - - + ]: 2977 : Assert(P_ISLEAF(opaque) && !P_IGNORE(opaque));
871 1999 [ + + ]: 2977 : if (!_bt_mark_page_halfdead(rel, vstate->info->heaprel, leafbuf,
2000 : : stack))
2001 : : {
2006 2002 : 4 : _bt_relbuf(rel, leafbuf);
1706 2003 : 4 : return;
2004 : : }
2005 : : }
2006 : :
2007 : : /*
2008 : : * Then unlink it from its siblings. Each call to
2009 : : * _bt_unlink_halfdead_page unlinks the topmost page from the subtree,
2010 : : * making it shallower. Iterate until the leafbuf page is deleted.
2011 : : */
4246 heikki.linnakangas@i 2012 : 2973 : rightsib_empty = false;
2006 pg@bowt.ie 2013 [ + - - + ]: 2973 : Assert(P_ISLEAF(opaque) && P_ISHALFDEAD(opaque));
4246 heikki.linnakangas@i 2014 [ + + ]: 6060 : while (P_ISHALFDEAD(opaque))
2015 : : {
2016 : : /* Check for interrupts in _bt_unlink_halfdead_page */
2006 pg@bowt.ie 2017 [ - + ]: 3087 : if (!_bt_unlink_halfdead_page(rel, leafbuf, scanblkno,
2018 : : &rightsib_empty, vstate))
2019 : : {
2020 : : /*
2021 : : * _bt_unlink_halfdead_page should never fail, since we
2022 : : * established that deletion is generally safe in
2023 : : * _bt_mark_page_halfdead -- index must be corrupt.
2024 : : *
2025 : : * Note that _bt_unlink_halfdead_page already released the
2026 : : * lock and pin on leafbuf for us.
2027 : : */
1727 pg@bowt.ie 2028 :UBC 0 : Assert(false);
2029 : : return;
2030 : : }
2031 : : }
2032 : :
2006 pg@bowt.ie 2033 [ + - - + ]:CBC 2973 : Assert(P_ISLEAF(opaque) && P_ISDELETED(opaque));
2034 : :
4246 heikki.linnakangas@i 2035 : 2973 : rightsib = opaque->btpo_next;
2036 : :
2006 pg@bowt.ie 2037 : 2973 : _bt_relbuf(rel, leafbuf);
2038 : :
2039 : : /*
2040 : : * Check here, as calling loops will have locks held, preventing
2041 : : * interrupts from being processed.
2042 : : */
2673 andres@anarazel.de 2043 [ - + ]: 2973 : CHECK_FOR_INTERRUPTS();
2044 : :
2045 : : /*
2046 : : * The page has now been deleted. If its right sibling is completely
2047 : : * empty, it's possible that the reason we haven't deleted it earlier
2048 : : * is that it was the rightmost child of the parent. Now that we
2049 : : * removed the downlink for this page, the right sibling might now be
2050 : : * the only child of the parent, and could be removed. It would be
2051 : : * picked up by the next vacuum anyway, but might as well try to
2052 : : * remove it now, so loop back to process the right sibling.
2053 : : *
2054 : : * Note: This relies on the assumption that _bt_getstackbuf() will be
2055 : : * able to reuse our original descent stack with a different child
2056 : : * block (provided that the child block is to the right of the
2057 : : * original leaf page reached by _bt_search()). It will even update
2058 : : * the descent stack each time we loop around, avoiding repeated work.
2059 : : */
4246 heikki.linnakangas@i 2060 [ + + ]: 2973 : if (!rightsib_empty)
2061 : 2968 : break;
2062 : :
871 pg@bowt.ie 2063 : 5 : leafbuf = _bt_getbuf(rel, rightsib, BT_WRITE);
2064 : : }
2065 : : }
2066 : :
2067 : : /*
2068 : : * First stage of page deletion.
2069 : : *
2070 : : * Establish the height of the to-be-deleted subtree with leafbuf at its
2071 : : * lowest level, remove the downlink to the subtree, and mark leafbuf
2072 : : * half-dead. The final to-be-deleted subtree is usually just leafbuf itself,
2073 : : * but may include additional internal pages (at most one per level of the
2074 : : * tree below the root).
2075 : : *
2076 : : * Caller must pass a valid heaprel, since it's just about possible that our
2077 : : * call to _bt_lock_subtree_parent will need to allocate a new index page to
2078 : : * complete a page split. Every call to _bt_allocbuf needs to pass a heaprel.
2079 : : *
2080 : : * Returns 'false' if leafbuf is unsafe to delete, usually because leafbuf is
2081 : : * the rightmost child of its parent (and parent has more than one downlink).
2082 : : * Returns 'true' when the first stage of page deletion completed
2083 : : * successfully.
2084 : : */
2085 : : static bool
941 andres@anarazel.de 2086 : 2977 : _bt_mark_page_halfdead(Relation rel, Relation heaprel, Buffer leafbuf,
2087 : : BTStack stack)
2088 : : {
2089 : : BlockNumber leafblkno;
2090 : : BlockNumber leafrightsib;
2091 : : BlockNumber topparent;
2092 : : BlockNumber topparentrightsib;
2093 : : ItemId itemid;
2094 : : Page page;
2095 : : BTPageOpaque opaque;
2096 : : Buffer subtreeparent;
2097 : : OffsetNumber poffset;
2098 : : OffsetNumber nextoffset;
2099 : : IndexTuple itup;
2100 : : IndexTupleData trunctuple;
2101 : :
3478 kgrittn@postgresql.o 2102 : 2977 : page = BufferGetPage(leafbuf);
1306 michael@paquier.xyz 2103 : 2977 : opaque = BTPageGetOpaque(page);
2104 : :
1996 pg@bowt.ie 2105 [ + - + - : 2977 : Assert(!P_RIGHTMOST(opaque) && !P_ISROOT(opaque) &&
+ - + - -
+ - + ]
2106 : : P_ISLEAF(opaque) && !P_IGNORE(opaque) &&
2107 : : P_FIRSTDATAKEY(opaque) > PageGetMaxOffsetNumber(page));
871 2108 [ - + ]: 2977 : Assert(heaprel != NULL);
2109 : :
2110 : : /*
2111 : : * Save info about the leaf page.
2112 : : */
4246 heikki.linnakangas@i 2113 : 2977 : leafblkno = BufferGetBlockNumber(leafbuf);
2114 : 2977 : leafrightsib = opaque->btpo_next;
2115 : :
2116 : : /*
2117 : : * Before attempting to lock the parent page, check that the right sibling
2118 : : * is not in half-dead state. A half-dead right sibling would have no
2119 : : * downlink in the parent, which would be highly confusing later when we
2120 : : * delete the downlink. It would fail the "right sibling of target page
2121 : : * is also the next child in parent page" cross-check below.
2122 : : */
871 pg@bowt.ie 2123 [ - + ]: 2977 : if (_bt_rightsib_halfdeadflag(rel, leafrightsib))
2124 : : {
4174 heikki.linnakangas@i 2125 [ # # ]:UBC 0 : elog(DEBUG1, "could not delete page %u because its right sibling %u is half-dead",
2126 : : leafblkno, leafrightsib);
2127 : 0 : return false;
2128 : : }
2129 : :
2130 : : /*
2131 : : * We cannot delete a page that is the rightmost child of its immediate
2132 : : * parent, unless it is the only child --- in which case the parent has to
2133 : : * be deleted too, and the same condition applies recursively to it. We
2134 : : * have to check this condition all the way up before trying to delete,
2135 : : * and lock the parent of the root of the to-be-deleted subtree (the
2136 : : * "subtree parent"). _bt_lock_subtree_parent() locks the subtree parent
2137 : : * for us. We remove the downlink to the "top parent" page (subtree root
2138 : : * page) from the subtree parent page below.
2139 : : *
2140 : : * Initialize topparent to be leafbuf page now. The final to-be-deleted
2141 : : * subtree is often a degenerate one page subtree consisting only of the
2142 : : * leafbuf page. When that happens, the leafbuf page is the final subtree
2143 : : * root page/top parent page.
2144 : : */
1996 pg@bowt.ie 2145 :CBC 2977 : topparent = leafblkno;
2146 : 2977 : topparentrightsib = leafrightsib;
941 andres@anarazel.de 2147 [ + + ]: 2977 : if (!_bt_lock_subtree_parent(rel, heaprel, leafblkno, stack,
2148 : : &subtreeparent, &poffset,
2149 : : &topparent, &topparentrightsib))
4246 heikki.linnakangas@i 2150 : 4 : return false;
2151 : :
1996 pg@bowt.ie 2152 : 2973 : page = BufferGetPage(subtreeparent);
1306 michael@paquier.xyz 2153 : 2973 : opaque = BTPageGetOpaque(page);
2154 : :
2155 : : #ifdef USE_ASSERT_CHECKING
2156 : :
2157 : : /*
2158 : : * This is just an assertion because _bt_lock_subtree_parent should have
2159 : : * guaranteed tuple has the expected contents
2160 : : */
1996 pg@bowt.ie 2161 : 2973 : itemid = PageGetItemId(page, poffset);
4246 heikki.linnakangas@i 2162 : 2973 : itup = (IndexTuple) PageGetItem(page, itemid);
1996 pg@bowt.ie 2163 [ - + ]: 2973 : Assert(BTreeTupleGetDownLink(itup) == topparent);
2164 : : #endif
2165 : :
2166 : 2973 : nextoffset = OffsetNumberNext(poffset);
4246 heikki.linnakangas@i 2167 : 2973 : itemid = PageGetItemId(page, nextoffset);
2168 : 2973 : itup = (IndexTuple) PageGetItem(page, itemid);
2169 : :
2170 : : /*
2171 : : * Check that the parent-page index items we're about to delete/overwrite
2172 : : * in subtree parent page contain what we expect. This can fail if the
2173 : : * index has become corrupt for some reason. When that happens we back
2174 : : * out of deletion of the leafbuf subtree. (This is just like the case
2175 : : * where _bt_lock_subtree_parent() cannot "re-find" leafbuf's downlink.)
2176 : : */
1996 pg@bowt.ie 2177 [ - + ]: 2973 : if (BTreeTupleGetDownLink(itup) != topparentrightsib)
2178 : : {
860 pg@bowt.ie 2179 [ # # ]:UBC 0 : ereport(LOG,
2180 : : (errcode(ERRCODE_INDEX_CORRUPTED),
2181 : : errmsg_internal("right sibling %u of block %u is not next child %u of block %u in index \"%s\"",
2182 : : topparentrightsib, topparent,
2183 : : BTreeTupleGetDownLink(itup),
2184 : : BufferGetBlockNumber(subtreeparent),
2185 : : RelationGetRelationName(rel))));
2186 : :
2187 : 0 : _bt_relbuf(rel, subtreeparent);
2188 : 0 : Assert(false);
2189 : : return false;
2190 : : }
2191 : :
2192 : : /*
2193 : : * Any insert which would have gone on the leaf block will now go to its
2194 : : * right sibling. In other words, the key space moves right.
2195 : : */
4246 heikki.linnakangas@i 2196 :CBC 2973 : PredicateLockPageCombine(rel, leafblkno, leafrightsib);
2197 : :
2198 : : /* No ereport(ERROR) until changes are logged */
2199 : 2973 : START_CRIT_SECTION();
2200 : :
2201 : : /*
2202 : : * Update parent of subtree. We want to delete the downlink to the top
2203 : : * parent page/root of the subtree, and the *following* key. Easiest way
2204 : : * is to copy the right sibling's downlink over the downlink that points
2205 : : * to top parent page, and then delete the right sibling's original pivot
2206 : : * tuple.
2207 : : *
2208 : : * Lanin and Shasha make the key space move left when deleting a page,
2209 : : * whereas the key space moves right here. That's why we cannot simply
2210 : : * delete the pivot tuple with the downlink to the top parent page. See
2211 : : * nbtree/README.
2212 : : */
1996 pg@bowt.ie 2213 : 2973 : page = BufferGetPage(subtreeparent);
1306 michael@paquier.xyz 2214 : 2973 : opaque = BTPageGetOpaque(page);
2215 : :
1996 pg@bowt.ie 2216 : 2973 : itemid = PageGetItemId(page, poffset);
4246 heikki.linnakangas@i 2217 : 2973 : itup = (IndexTuple) PageGetItem(page, itemid);
1996 pg@bowt.ie 2218 : 2973 : BTreeTupleSetDownLink(itup, topparentrightsib);
2219 : :
2220 : 2973 : nextoffset = OffsetNumberNext(poffset);
4246 heikki.linnakangas@i 2221 : 2973 : PageIndexTupleDelete(page, nextoffset);
2222 : :
2223 : : /*
2224 : : * Mark the leaf page as half-dead, and stamp it with a link to the top
2225 : : * parent page. When the leaf page is also the top parent page, the link
2226 : : * is set to InvalidBlockNumber.
2227 : : */
3478 kgrittn@postgresql.o 2228 : 2973 : page = BufferGetPage(leafbuf);
1306 michael@paquier.xyz 2229 : 2973 : opaque = BTPageGetOpaque(page);
4246 heikki.linnakangas@i 2230 : 2973 : opaque->btpo_flags |= BTP_HALF_DEAD;
2231 : :
2268 pg@bowt.ie 2232 [ - + ]: 2973 : Assert(PageGetMaxOffsetNumber(page) == P_HIKEY);
4206 heikki.linnakangas@i 2233 [ + - + - : 5946 : MemSet(&trunctuple, 0, sizeof(IndexTupleData));
+ - + - +
+ ]
2234 : 2973 : trunctuple.t_info = sizeof(IndexTupleData);
1996 pg@bowt.ie 2235 [ + + ]: 2973 : if (topparent != leafblkno)
2236 : 55 : BTreeTupleSetTopParent(&trunctuple, topparent);
2237 : : else
2745 teodor@sigaev.ru 2238 : 2918 : BTreeTupleSetTopParent(&trunctuple, InvalidBlockNumber);
2239 : :
1 peter@eisentraut.org 2240 [ - + ]:GNC 2973 : if (!PageIndexTupleOverwrite(page, P_HIKEY, &trunctuple, IndexTupleSize(&trunctuple)))
2268 pg@bowt.ie 2241 [ # # ]:UBC 0 : elog(ERROR, "could not overwrite high key in half-dead page");
2242 : :
2243 : : /* Must mark buffers dirty before XLogInsert */
1996 pg@bowt.ie 2244 :CBC 2973 : MarkBufferDirty(subtreeparent);
4246 heikki.linnakangas@i 2245 : 2973 : MarkBufferDirty(leafbuf);
2246 : :
2247 : : /* XLOG stuff */
2248 [ + - + + : 2973 : if (RelationNeedsWAL(rel))
+ - + - ]
2249 : : {
2250 : : xl_btree_mark_page_halfdead xlrec;
2251 : : XLogRecPtr recptr;
2252 : :
1996 pg@bowt.ie 2253 : 2973 : xlrec.poffset = poffset;
4246 heikki.linnakangas@i 2254 : 2973 : xlrec.leafblk = leafblkno;
1996 pg@bowt.ie 2255 [ + + ]: 2973 : if (topparent != leafblkno)
2256 : 55 : xlrec.topparent = topparent;
2257 : : else
4206 heikki.linnakangas@i 2258 : 2918 : xlrec.topparent = InvalidBlockNumber;
2259 : :
3995 2260 : 2973 : XLogBeginInsert();
2261 : 2973 : XLogRegisterBuffer(0, leafbuf, REGBUF_WILL_INIT);
1996 pg@bowt.ie 2262 : 2973 : XLogRegisterBuffer(1, subtreeparent, REGBUF_STANDARD);
2263 : :
3478 kgrittn@postgresql.o 2264 : 2973 : page = BufferGetPage(leafbuf);
1306 michael@paquier.xyz 2265 : 2973 : opaque = BTPageGetOpaque(page);
4246 heikki.linnakangas@i 2266 : 2973 : xlrec.leftblk = opaque->btpo_prev;
2267 : 2973 : xlrec.rightblk = opaque->btpo_next;
2268 : :
259 peter@eisentraut.org 2269 : 2973 : XLogRegisterData(&xlrec, SizeOfBtreeMarkPageHalfDead);
2270 : :
3995 heikki.linnakangas@i 2271 : 2973 : recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_MARK_PAGE_HALFDEAD);
2272 : :
1996 pg@bowt.ie 2273 : 2973 : page = BufferGetPage(subtreeparent);
4246 heikki.linnakangas@i 2274 : 2973 : PageSetLSN(page, recptr);
3478 kgrittn@postgresql.o 2275 : 2973 : page = BufferGetPage(leafbuf);
4246 heikki.linnakangas@i 2276 : 2973 : PageSetLSN(page, recptr);
2277 : : }
2278 : :
2279 [ - + ]: 2973 : END_CRIT_SECTION();
2280 : :
1996 pg@bowt.ie 2281 : 2973 : _bt_relbuf(rel, subtreeparent);
4246 heikki.linnakangas@i 2282 : 2973 : return true;
2283 : : }
2284 : :
2285 : : /*
2286 : : * Second stage of page deletion.
2287 : : *
2288 : : * Unlinks a single page (in the subtree undergoing deletion) from its
2289 : : * siblings. Also marks the page deleted.
2290 : : *
2291 : : * To get rid of the whole subtree, including the leaf page itself, call here
2292 : : * until the leaf page is deleted. The original "top parent" established in
2293 : : * the first stage of deletion is deleted in the first call here, while the
2294 : : * leaf page is deleted in the last call here. Note that the leaf page itself
2295 : : * is often the initial top parent page.
2296 : : *
2297 : : * Returns 'false' if the page could not be unlinked (shouldn't happen). If
2298 : : * the right sibling of the current target page is empty, *rightsib_empty is
2299 : : * set to true, allowing caller to delete the target's right sibling page in
2300 : : * passing. Note that *rightsib_empty is only actually used by caller when
2301 : : * target page is leafbuf, following last call here for leafbuf/the subtree
2302 : : * containing leafbuf. (We always set *rightsib_empty for caller, just to be
2303 : : * consistent.)
2304 : : *
2305 : : * Must hold pin and lock on leafbuf at entry (read or write doesn't matter).
2306 : : * On success exit, we'll be holding pin and write lock. On failure exit,
2307 : : * we'll release both pin and lock before returning (we define it that way
2308 : : * to avoid having to reacquire a lock we already released).
2309 : : */
2310 : : static bool
2006 pg@bowt.ie 2311 : 3087 : _bt_unlink_halfdead_page(Relation rel, Buffer leafbuf, BlockNumber scanblkno,
2312 : : bool *rightsib_empty, BTVacState *vstate)
2313 : : {
4246 heikki.linnakangas@i 2314 : 3087 : BlockNumber leafblkno = BufferGetBlockNumber(leafbuf);
1706 pg@bowt.ie 2315 : 3087 : IndexBulkDeleteResult *stats = vstate->stats;
2316 : : BlockNumber leafleftsib;
2317 : : BlockNumber leafrightsib;
2318 : : BlockNumber target;
2319 : : BlockNumber leftsib;
2320 : : BlockNumber rightsib;
4246 heikki.linnakangas@i 2321 : 3087 : Buffer lbuf = InvalidBuffer;
2322 : : Buffer buf;
2323 : : Buffer rbuf;
2324 : 3087 : Buffer metabuf = InvalidBuffer;
2325 : 3087 : Page metapg = NULL;
2326 : 3087 : BTMetaPageData *metad = NULL;
2327 : : ItemId itemid;
2328 : : Page page;
2329 : : BTPageOpaque opaque;
2330 : : FullTransactionId safexid;
2331 : : bool rightsib_is_rightmost;
2332 : : uint32 targetlevel;
2333 : : IndexTuple leafhikey;
2334 : : BlockNumber leaftopparent;
2335 : :
3478 kgrittn@postgresql.o 2336 : 3087 : page = BufferGetPage(leafbuf);
1306 michael@paquier.xyz 2337 : 3087 : opaque = BTPageGetOpaque(page);
2338 : :
1996 pg@bowt.ie 2339 [ + - + - : 3087 : Assert(P_ISLEAF(opaque) && !P_ISDELETED(opaque) && P_ISHALFDEAD(opaque));
- + ]
2340 : :
2341 : : /*
2342 : : * Remember some information about the leaf page.
2343 : : */
4246 heikki.linnakangas@i 2344 : 3087 : itemid = PageGetItemId(page, P_HIKEY);
2745 teodor@sigaev.ru 2345 : 3087 : leafhikey = (IndexTuple) PageGetItem(page, itemid);
2012 pg@bowt.ie 2346 : 3087 : target = BTreeTupleGetTopParent(leafhikey);
4246 heikki.linnakangas@i 2347 : 3087 : leafleftsib = opaque->btpo_prev;
2348 : 3087 : leafrightsib = opaque->btpo_next;
2349 : :
1925 pg@bowt.ie 2350 : 3087 : _bt_unlockbuf(rel, leafbuf);
2351 : :
2352 : : /*
2353 : : * Check here, as calling loops will have locks held, preventing
2354 : : * interrupts from being processed.
2355 : : */
2673 andres@anarazel.de 2356 [ - + ]: 3087 : CHECK_FOR_INTERRUPTS();
2357 : :
2358 : : /* Unlink the current top parent of the subtree */
2012 pg@bowt.ie 2359 [ + + ]: 3087 : if (!BlockNumberIsValid(target))
2360 : : {
2361 : : /* Target is leaf page (or leaf page is top parent, if you prefer) */
2362 : 2973 : target = leafblkno;
2363 : :
2364 : 2973 : buf = leafbuf;
2365 : 2973 : leftsib = leafleftsib;
2366 : 2973 : targetlevel = 0;
2367 : : }
2368 : : else
2369 : : {
2370 : : /* Target is the internal page taken from leaf's top parent link */
3370 tgl@sss.pgh.pa.us 2371 [ - + ]: 114 : Assert(target != leafblkno);
2372 : :
2373 : : /* Fetch the block number of the target's left sibling */
871 pg@bowt.ie 2374 : 114 : buf = _bt_getbuf(rel, target, BT_READ);
3478 kgrittn@postgresql.o 2375 : 114 : page = BufferGetPage(buf);
1306 michael@paquier.xyz 2376 : 114 : opaque = BTPageGetOpaque(page);
4246 heikki.linnakangas@i 2377 : 114 : leftsib = opaque->btpo_prev;
1707 pg@bowt.ie 2378 : 114 : targetlevel = opaque->btpo_level;
2012 2379 [ - + ]: 114 : Assert(targetlevel > 0);
2380 : :
2381 : : /*
2382 : : * To avoid deadlocks, we'd better drop the target page lock before
2383 : : * going further.
2384 : : */
1925 2385 : 114 : _bt_unlockbuf(rel, buf);
2386 : : }
2387 : :
2388 : : /*
2389 : : * We have to lock the pages we need to modify in the standard order:
2390 : : * moving right, then up. Else we will deadlock against other writers.
2391 : : *
2392 : : * So, first lock the leaf page, if it's not the target. Then find and
2393 : : * write-lock the current left sibling of the target page. The sibling
2394 : : * that was current a moment ago could have split, so we may have to move
2395 : : * right.
2396 : : */
4246 heikki.linnakangas@i 2397 [ + + ]: 3087 : if (target != leafblkno)
1925 pg@bowt.ie 2398 : 114 : _bt_lockbuf(rel, leafbuf, BT_WRITE);
8283 tgl@sss.pgh.pa.us 2399 [ + + ]: 3087 : if (leftsib != P_NONE)
2400 : : {
871 pg@bowt.ie 2401 : 788 : lbuf = _bt_getbuf(rel, leftsib, BT_WRITE);
3478 kgrittn@postgresql.o 2402 : 788 : page = BufferGetPage(lbuf);
1306 michael@paquier.xyz 2403 : 788 : opaque = BTPageGetOpaque(page);
8283 tgl@sss.pgh.pa.us 2404 [ - + - + ]: 788 : while (P_ISDELETED(opaque) || opaque->btpo_next != target)
2405 : : {
1630 tgl@sss.pgh.pa.us 2406 :UBC 0 : bool leftsibvalid = true;
2407 : :
2408 : : /*
2409 : : * Before we follow the link from the page that was the left
2410 : : * sibling mere moments ago, validate its right link. This
2411 : : * reduces the opportunities for loop to fail to ever make any
2412 : : * progress in the presence of index corruption.
2413 : : *
2414 : : * Note: we rely on the assumption that there can only be one
2415 : : * vacuum process running at a time (against the same index).
2416 : : */
1727 pg@bowt.ie 2417 [ # # # # ]: 0 : if (P_RIGHTMOST(opaque) || P_ISDELETED(opaque) ||
2418 [ # # ]: 0 : leftsib == opaque->btpo_next)
2419 : 0 : leftsibvalid = false;
2420 : :
2421 : 0 : leftsib = opaque->btpo_next;
2422 : 0 : _bt_relbuf(rel, lbuf);
2423 : :
2424 [ # # ]: 0 : if (!leftsibvalid)
2425 : : {
2426 : : /*
2427 : : * This is known to fail in the field; sibling link corruption
2428 : : * is relatively common. Press on with vacuuming rather than
2429 : : * just throwing an ERROR.
2430 : : */
2431 [ # # ]: 0 : ereport(LOG,
2432 : : (errcode(ERRCODE_INDEX_CORRUPTED),
2433 : : errmsg_internal("valid left sibling for deletion target could not be located: "
2434 : : "left sibling %u of target %u with leafblkno %u and scanblkno %u on level %u of index \"%s\"",
2435 : : leftsib, target, leafblkno, scanblkno,
2436 : : targetlevel, RelationGetRelationName(rel))));
2437 : :
2438 : : /* Must release all pins and locks on failure exit */
887 2439 : 0 : ReleaseBuffer(buf);
2440 [ # # ]: 0 : if (target != leafblkno)
2441 : 0 : _bt_relbuf(rel, leafbuf);
2442 : :
4246 heikki.linnakangas@i 2443 : 0 : return false;
2444 : : }
2445 : :
1727 pg@bowt.ie 2446 [ # # ]: 0 : CHECK_FOR_INTERRUPTS();
2447 : :
2448 : : /* step right one page */
871 2449 : 0 : lbuf = _bt_getbuf(rel, leftsib, BT_WRITE);
3478 kgrittn@postgresql.o 2450 : 0 : page = BufferGetPage(lbuf);
1306 michael@paquier.xyz 2451 : 0 : opaque = BTPageGetOpaque(page);
2452 : : }
2453 : : }
2454 : : else
8283 tgl@sss.pgh.pa.us 2455 :CBC 2299 : lbuf = InvalidBuffer;
2456 : :
2457 : : /* Next write-lock the target page itself */
1925 pg@bowt.ie 2458 : 3087 : _bt_lockbuf(rel, buf, BT_WRITE);
3478 kgrittn@postgresql.o 2459 : 3087 : page = BufferGetPage(buf);
1306 michael@paquier.xyz 2460 : 3087 : opaque = BTPageGetOpaque(page);
2461 : :
2462 : : /*
2463 : : * Check page is still empty etc, else abandon deletion. This is just for
2464 : : * paranoia's sake; a half-dead page cannot resurrect because there can be
2465 : : * only one vacuum process running at a time.
2466 : : */
4246 heikki.linnakangas@i 2467 [ + - + - : 3087 : if (P_RIGHTMOST(opaque) || P_ISROOT(opaque) || P_ISDELETED(opaque))
- + ]
1701 pg@bowt.ie 2468 [ # # ]:UBC 0 : elog(ERROR, "target page changed status unexpectedly in block %u of index \"%s\"",
2469 : : target, RelationGetRelationName(rel));
2470 : :
8283 tgl@sss.pgh.pa.us 2471 [ - + ]:CBC 3087 : if (opaque->btpo_prev != leftsib)
2280 peter@eisentraut.org 2472 [ # # ]:UBC 0 : ereport(ERROR,
2473 : : (errcode(ERRCODE_INDEX_CORRUPTED),
2474 : : errmsg_internal("target page left link unexpectedly changed from %u to %u in block %u of index \"%s\"",
2475 : : leftsib, opaque->btpo_prev, target,
2476 : : RelationGetRelationName(rel))));
2477 : :
4246 heikki.linnakangas@i 2478 [ + + ]:CBC 3087 : if (target == leafblkno)
2479 : : {
2480 [ - + + - ]: 2973 : if (P_FIRSTDATAKEY(opaque) <= PageGetMaxOffsetNumber(page) ||
2481 [ + - - + ]: 2973 : !P_ISLEAF(opaque) || !P_ISHALFDEAD(opaque))
1701 pg@bowt.ie 2482 [ # # ]:UBC 0 : elog(ERROR, "target leaf page changed status unexpectedly in block %u of index \"%s\"",
2483 : : target, RelationGetRelationName(rel));
2484 : :
2485 : : /* Leaf page is also target page: don't set leaftopparent */
1707 pg@bowt.ie 2486 :CBC 2973 : leaftopparent = InvalidBlockNumber;
2487 : : }
2488 : : else
2489 : : {
2490 : : IndexTuple finaldataitem;
2491 : :
4246 heikki.linnakangas@i 2492 [ - + + - ]: 114 : if (P_FIRSTDATAKEY(opaque) != PageGetMaxOffsetNumber(page) ||
2493 [ - + ]: 114 : P_ISLEAF(opaque))
1701 pg@bowt.ie 2494 [ # # ]:UBC 0 : elog(ERROR, "target internal page on level %u changed status unexpectedly in block %u of index \"%s\"",
2495 : : targetlevel, target, RelationGetRelationName(rel));
2496 : :
2497 : : /* Target is internal: set leaftopparent for next call here... */
4246 heikki.linnakangas@i 2498 [ - + ]:CBC 114 : itemid = PageGetItemId(page, P_FIRSTDATAKEY(opaque));
1707 pg@bowt.ie 2499 : 114 : finaldataitem = (IndexTuple) PageGetItem(page, itemid);
2500 : 114 : leaftopparent = BTreeTupleGetDownLink(finaldataitem);
2501 : : /* ...except when it would be a redundant pointer-to-self */
2502 [ + + ]: 114 : if (leaftopparent == leafblkno)
2503 : 55 : leaftopparent = InvalidBlockNumber;
2504 : : }
2505 : :
2506 : : /* No leaftopparent for level 0 (leaf page) or level 1 target */
1701 2507 [ + + - + ]: 3087 : Assert(!BlockNumberIsValid(leaftopparent) || targetlevel > 1);
2508 : :
2509 : : /*
2510 : : * And next write-lock the (current) right sibling.
2511 : : */
8283 tgl@sss.pgh.pa.us 2512 : 3087 : rightsib = opaque->btpo_next;
871 pg@bowt.ie 2513 : 3087 : rbuf = _bt_getbuf(rel, rightsib, BT_WRITE);
3478 kgrittn@postgresql.o 2514 : 3087 : page = BufferGetPage(rbuf);
1306 michael@paquier.xyz 2515 : 3087 : opaque = BTPageGetOpaque(page);
2516 : :
2517 : : /*
2518 : : * Validate target's right sibling page. Its left link must point back to
2519 : : * the target page.
2520 : : */
5539 tgl@sss.pgh.pa.us 2521 [ - + ]: 3087 : if (opaque->btpo_prev != target)
2522 : : {
2523 : : /*
2524 : : * This is known to fail in the field; sibling link corruption is
2525 : : * relatively common. Press on with vacuuming rather than just
2526 : : * throwing an ERROR (same approach used for left-sibling's-right-link
2527 : : * validation check a moment ago).
2528 : : */
887 pg@bowt.ie 2529 [ # # ]:UBC 0 : ereport(LOG,
2530 : : (errcode(ERRCODE_INDEX_CORRUPTED),
2531 : : errmsg_internal("right sibling's left-link doesn't match: "
2532 : : "right sibling %u of target %u with leafblkno %u "
2533 : : "and scanblkno %u spuriously links to non-target %u "
2534 : : "on level %u of index \"%s\"",
2535 : : rightsib, target, leafblkno,
2536 : : scanblkno, opaque->btpo_prev,
2537 : : targetlevel, RelationGetRelationName(rel))));
2538 : :
2539 : : /* Must release all pins and locks on failure exit */
2540 [ # # ]: 0 : if (BufferIsValid(lbuf))
2541 : 0 : _bt_relbuf(rel, lbuf);
2542 : 0 : _bt_relbuf(rel, rbuf);
2543 : 0 : _bt_relbuf(rel, buf);
2544 [ # # ]: 0 : if (target != leafblkno)
2545 : 0 : _bt_relbuf(rel, leafbuf);
2546 : :
2547 : 0 : return false;
2548 : : }
2549 : :
4246 heikki.linnakangas@i 2550 :CBC 3087 : rightsib_is_rightmost = P_RIGHTMOST(opaque);
2551 [ + + ]: 3087 : *rightsib_empty = (P_FIRSTDATAKEY(opaque) > PageGetMaxOffsetNumber(page));
2552 : :
2553 : : /*
2554 : : * If we are deleting the next-to-last page on the target's level, then
2555 : : * the rightsib is a candidate to become the new fast root. (In theory, it
2556 : : * might be possible to push the fast root even further down, but the odds
2557 : : * of doing so are slim, and the locking considerations daunting.)
2558 : : *
2559 : : * We can safely acquire a lock on the metapage here --- see comments for
2560 : : * _bt_newlevel().
2561 : : */
2562 [ + + + + ]: 3087 : if (leftsib == P_NONE && rightsib_is_rightmost)
2563 : : {
3478 kgrittn@postgresql.o 2564 : 34 : page = BufferGetPage(rbuf);
1306 michael@paquier.xyz 2565 : 34 : opaque = BTPageGetOpaque(page);
8283 tgl@sss.pgh.pa.us 2566 [ + - ]: 34 : if (P_RIGHTMOST(opaque))
2567 : : {
2568 : : /* rightsib will be the only one left on the level */
871 pg@bowt.ie 2569 : 34 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
3478 kgrittn@postgresql.o 2570 : 34 : metapg = BufferGetPage(metabuf);
8283 tgl@sss.pgh.pa.us 2571 : 34 : metad = BTPageGetMeta(metapg);
2572 : :
2573 : : /*
2574 : : * The expected case here is btm_fastlevel == targetlevel+1; if
2575 : : * the fastlevel is <= targetlevel, something is wrong, and we
2576 : : * choose to overwrite it to fix it.
2577 : : */
8121 bruce@momjian.us 2578 [ - + ]: 34 : if (metad->btm_fastlevel > targetlevel + 1)
2579 : : {
2580 : : /* no update wanted */
8283 tgl@sss.pgh.pa.us 2581 :UBC 0 : _bt_relbuf(rel, metabuf);
2582 : 0 : metabuf = InvalidBuffer;
2583 : : }
2584 : : }
2585 : : }
2586 : :
2587 : : /*
2588 : : * Here we begin doing the deletion.
2589 : : */
2590 : :
2591 : : /* No ereport(ERROR) until changes are logged */
8283 tgl@sss.pgh.pa.us 2592 :CBC 3087 : START_CRIT_SECTION();
2593 : :
2594 : : /*
2595 : : * Update siblings' side-links. Note the target page's side-links will
2596 : : * continue to point to the siblings. Asserts here are just rechecking
2597 : : * things we already verified above.
2598 : : */
2599 [ + + ]: 3087 : if (BufferIsValid(lbuf))
2600 : : {
3478 kgrittn@postgresql.o 2601 : 788 : page = BufferGetPage(lbuf);
1306 michael@paquier.xyz 2602 : 788 : opaque = BTPageGetOpaque(page);
8283 tgl@sss.pgh.pa.us 2603 [ - + ]: 788 : Assert(opaque->btpo_next == target);
2604 : 788 : opaque->btpo_next = rightsib;
2605 : : }
3478 kgrittn@postgresql.o 2606 : 3087 : page = BufferGetPage(rbuf);
1306 michael@paquier.xyz 2607 : 3087 : opaque = BTPageGetOpaque(page);
8283 tgl@sss.pgh.pa.us 2608 [ - + ]: 3087 : Assert(opaque->btpo_prev == target);
2609 : 3087 : opaque->btpo_prev = leftsib;
2610 : :
2611 : : /*
2612 : : * If we deleted a parent of the targeted leaf page, instead of the leaf
2613 : : * itself, update the leaf to point to the next remaining child in the
2614 : : * subtree.
2615 : : *
2616 : : * Note: We rely on the fact that a buffer pin on the leaf page has been
2617 : : * held since leafhikey was initialized. This is safe, though only
2618 : : * because the page was already half-dead at that point. The leaf page
2619 : : * cannot have been modified by any other backend during the period when
2620 : : * no lock was held.
2621 : : */
4246 heikki.linnakangas@i 2622 [ + + ]: 3087 : if (target != leafblkno)
1707 pg@bowt.ie 2623 : 114 : BTreeTupleSetTopParent(leafhikey, leaftopparent);
2624 : :
2625 : : /*
2626 : : * Mark the page itself deleted. It can be recycled when all current
2627 : : * transactions are gone. Storing GetTopTransactionId() would work, but
2628 : : * we're in VACUUM and would not otherwise have an XID. Having already
2629 : : * updated links to the target, ReadNextFullTransactionId() suffices as an
2630 : : * upper bound. Any scan having retained a now-stale link is advertising
2631 : : * in its PGPROC an xmin less than or equal to the value we read here. It
2632 : : * will continue to do so, holding back the xmin horizon, for the duration
2633 : : * of that scan.
2634 : : */
3478 kgrittn@postgresql.o 2635 : 3087 : page = BufferGetPage(buf);
1306 michael@paquier.xyz 2636 : 3087 : opaque = BTPageGetOpaque(page);
2006 pg@bowt.ie 2637 [ + + - + ]: 3087 : Assert(P_ISHALFDEAD(opaque) || !P_ISLEAF(opaque));
2638 : :
2639 : : /*
2640 : : * Store upper bound XID that's used to determine when deleted page is no
2641 : : * longer needed as a tombstone
2642 : : */
1707 2643 : 3087 : safexid = ReadNextFullTransactionId();
2644 : 3087 : BTPageSetDeleted(page, safexid);
2645 : 3087 : opaque->btpo_cycleid = 0;
2646 : :
2647 : : /* And update the metapage, if needed */
8283 tgl@sss.pgh.pa.us 2648 [ + + ]: 3087 : if (BufferIsValid(metabuf))
2649 : : {
2650 : : /* upgrade metapage if needed */
2414 pg@bowt.ie 2651 [ - + ]: 34 : if (metad->btm_version < BTREE_NOVAC_VERSION)
2764 teodor@sigaev.ru 2652 :UBC 0 : _bt_upgrademetapage(metapg);
8283 tgl@sss.pgh.pa.us 2653 :CBC 34 : metad->btm_fastroot = rightsib;
2654 : 34 : metad->btm_fastlevel = targetlevel;
7151 2655 : 34 : MarkBufferDirty(metabuf);
2656 : : }
2657 : :
2658 : : /* Must mark buffers dirty before XLogInsert */
2659 : 3087 : MarkBufferDirty(rbuf);
2660 : 3087 : MarkBufferDirty(buf);
2661 [ + + ]: 3087 : if (BufferIsValid(lbuf))
2662 : 788 : MarkBufferDirty(lbuf);
4246 heikki.linnakangas@i 2663 [ + + ]: 3087 : if (target != leafblkno)
2664 : 114 : MarkBufferDirty(leafbuf);
2665 : :
2666 : : /* XLOG stuff */
5433 rhaas@postgresql.org 2667 [ + - + + : 3087 : if (RelationNeedsWAL(rel))
+ - + - ]
2668 : : {
2669 : : xl_btree_unlink_page xlrec;
2670 : : xl_btree_metadata xlmeta;
2671 : : uint8 xlinfo;
2672 : : XLogRecPtr recptr;
2673 : :
3995 heikki.linnakangas@i 2674 : 3087 : XLogBeginInsert();
2675 : :
2676 : 3087 : XLogRegisterBuffer(0, buf, REGBUF_WILL_INIT);
2677 [ + + ]: 3087 : if (BufferIsValid(lbuf))
2678 : 788 : XLogRegisterBuffer(1, lbuf, REGBUF_STANDARD);
2679 : 3087 : XLogRegisterBuffer(2, rbuf, REGBUF_STANDARD);
2680 [ + + ]: 3087 : if (target != leafblkno)
2681 : 114 : XLogRegisterBuffer(3, leafbuf, REGBUF_WILL_INIT);
2682 : :
2683 : : /* information stored on the target/to-be-unlinked block */
4246 2684 : 3087 : xlrec.leftsib = leftsib;
2685 : 3087 : xlrec.rightsib = rightsib;
1707 pg@bowt.ie 2686 : 3087 : xlrec.level = targetlevel;
2687 : 3087 : xlrec.safexid = safexid;
2688 : :
2689 : : /* information needed to recreate the leaf block (if not the target) */
4246 heikki.linnakangas@i 2690 : 3087 : xlrec.leafleftsib = leafleftsib;
2691 : 3087 : xlrec.leafrightsib = leafrightsib;
1707 pg@bowt.ie 2692 : 3087 : xlrec.leaftopparent = leaftopparent;
2693 : :
259 peter@eisentraut.org 2694 : 3087 : XLogRegisterData(&xlrec, SizeOfBtreeUnlinkPage);
2695 : :
8283 tgl@sss.pgh.pa.us 2696 [ + + ]: 3087 : if (BufferIsValid(metabuf))
2697 : : {
2916 2698 : 34 : XLogRegisterBuffer(4, metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);
2699 : :
2414 pg@bowt.ie 2700 [ - + ]: 34 : Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
2701 : 34 : xlmeta.version = metad->btm_version;
8283 tgl@sss.pgh.pa.us 2702 : 34 : xlmeta.root = metad->btm_root;
2703 : 34 : xlmeta.level = metad->btm_level;
2704 : 34 : xlmeta.fastroot = metad->btm_fastroot;
2705 : 34 : xlmeta.fastlevel = metad->btm_fastlevel;
1707 pg@bowt.ie 2706 : 34 : xlmeta.last_cleanup_num_delpages = metad->btm_last_cleanup_num_delpages;
2071 2707 : 34 : xlmeta.allequalimage = metad->btm_allequalimage;
2708 : :
259 peter@eisentraut.org 2709 : 34 : XLogRegisterBufData(4, &xlmeta, sizeof(xl_btree_metadata));
4246 heikki.linnakangas@i 2710 : 34 : xlinfo = XLOG_BTREE_UNLINK_PAGE_META;
2711 : : }
2712 : : else
2713 : 3053 : xlinfo = XLOG_BTREE_UNLINK_PAGE;
2714 : :
3995 2715 : 3087 : recptr = XLogInsert(RM_BTREE_ID, xlinfo);
2716 : :
8283 tgl@sss.pgh.pa.us 2717 [ + + ]: 3087 : if (BufferIsValid(metabuf))
2718 : : {
2719 : 34 : PageSetLSN(metapg, recptr);
2720 : : }
3478 kgrittn@postgresql.o 2721 : 3087 : page = BufferGetPage(rbuf);
8283 tgl@sss.pgh.pa.us 2722 : 3087 : PageSetLSN(page, recptr);
3478 kgrittn@postgresql.o 2723 : 3087 : page = BufferGetPage(buf);
8283 tgl@sss.pgh.pa.us 2724 : 3087 : PageSetLSN(page, recptr);
2725 [ + + ]: 3087 : if (BufferIsValid(lbuf))
2726 : : {
3478 kgrittn@postgresql.o 2727 : 788 : page = BufferGetPage(lbuf);
8283 tgl@sss.pgh.pa.us 2728 : 788 : PageSetLSN(page, recptr);
2729 : : }
4246 heikki.linnakangas@i 2730 [ + + ]: 3087 : if (target != leafblkno)
2731 : : {
3478 kgrittn@postgresql.o 2732 : 114 : page = BufferGetPage(leafbuf);
4246 heikki.linnakangas@i 2733 : 114 : PageSetLSN(page, recptr);
2734 : : }
2735 : : }
2736 : :
8283 tgl@sss.pgh.pa.us 2737 [ - + ]: 3087 : END_CRIT_SECTION();
2738 : :
2739 : : /* release metapage */
2740 [ + + ]: 3087 : if (BufferIsValid(metabuf))
7151 2741 : 34 : _bt_relbuf(rel, metabuf);
2742 : :
2743 : : /* release siblings */
8283 2744 [ + + ]: 3087 : if (BufferIsValid(lbuf))
7151 2745 : 788 : _bt_relbuf(rel, lbuf);
4246 heikki.linnakangas@i 2746 : 3087 : _bt_relbuf(rel, rbuf);
2747 : :
2748 : : /* If the target is not leafbuf, we're done with it now -- release it */
1707 pg@bowt.ie 2749 [ + + ]: 3087 : if (target != leafblkno)
2750 : 114 : _bt_relbuf(rel, buf);
2751 : :
2752 : : /*
2753 : : * Maintain pages_newly_deleted, which is simply the number of pages
2754 : : * deleted by the ongoing VACUUM operation.
2755 : : *
2756 : : * Maintain pages_deleted in a way that takes into account how
2757 : : * btvacuumpage() will count deleted pages that have yet to become
2758 : : * scanblkno -- only count page when it's not going to get that treatment
2759 : : * later on.
2760 : : */
1706 2761 : 3087 : stats->pages_newly_deleted++;
2006 2762 [ + + ]: 3087 : if (target <= scanblkno)
1706 2763 : 2987 : stats->pages_deleted++;
2764 : :
2765 : : /*
2766 : : * Remember information about the target page (now a newly deleted page)
2767 : : * in dedicated vstate space for later. The page will be considered as a
2768 : : * candidate to place in the FSM at the end of the current btvacuumscan()
2769 : : * call.
2770 : : */
1682 2771 : 3087 : _bt_pendingfsm_add(vstate, target, safexid);
2772 : :
2773 : : /* Success - hold on to lock on leafbuf (might also have been target) */
4246 heikki.linnakangas@i 2774 : 3087 : return true;
2775 : : }
2776 : :
2777 : : /*
2778 : : * Establish how tall the to-be-deleted subtree will be during the first stage
2779 : : * of page deletion.
2780 : : *
2781 : : * Caller's child argument is the block number of the page caller wants to
2782 : : * delete (this is leafbuf's block number, except when we're called
2783 : : * recursively). stack is a search stack leading to it. Note that we will
2784 : : * update the stack entry(s) to reflect current downlink positions --- this is
2785 : : * similar to the corresponding point in page split handling.
2786 : : *
2787 : : * If "first stage" caller cannot go ahead with deleting _any_ pages, returns
2788 : : * false. Returns true on success, in which case caller can use certain
2789 : : * details established here to perform the first stage of deletion. This
2790 : : * function is the last point at which page deletion may be deemed unsafe
2791 : : * (barring index corruption, or unexpected concurrent page deletions).
2792 : : *
2793 : : * We write lock the parent of the root of the to-be-deleted subtree for
2794 : : * caller on success (i.e. we leave our lock on the *subtreeparent buffer for
2795 : : * caller). Caller will have to remove a downlink from *subtreeparent. We
2796 : : * also set a *subtreeparent offset number in *poffset, to indicate the
2797 : : * location of the pivot tuple that contains the relevant downlink.
2798 : : *
2799 : : * The root of the to-be-deleted subtree is called the "top parent". Note
2800 : : * that the leafbuf page is often the final "top parent" page (you can think
2801 : : * of the leafbuf page as a degenerate single page subtree when that happens).
2802 : : * Caller should initialize *topparent to the target leafbuf page block number
2803 : : * (while *topparentrightsib should be set to leafbuf's right sibling block
2804 : : * number). We will update *topparent (and *topparentrightsib) for caller
2805 : : * here, though only when it turns out that caller will delete at least one
2806 : : * internal page (i.e. only when caller needs to store a valid link to the top
2807 : : * parent block in the leafbuf page using BTreeTupleSetTopParent()).
2808 : : */
2809 : : static bool
941 andres@anarazel.de 2810 : 3100 : _bt_lock_subtree_parent(Relation rel, Relation heaprel, BlockNumber child,
2811 : : BTStack stack, Buffer *subtreeparent,
2812 : : OffsetNumber *poffset, BlockNumber *topparent,
2813 : : BlockNumber *topparentrightsib)
2814 : : {
2815 : : BlockNumber parent,
2816 : : leftsibparent;
2817 : : OffsetNumber parentoffset,
2818 : : maxoff;
2819 : : Buffer pbuf;
2820 : : Page page;
2821 : : BTPageOpaque opaque;
2822 : :
2823 : : /*
2824 : : * Locate the pivot tuple whose downlink points to "child". Write lock
2825 : : * the parent page itself.
2826 : : */
2827 : 3100 : pbuf = _bt_getstackbuf(rel, heaprel, stack, child);
1996 pg@bowt.ie 2828 [ - + ]: 3100 : if (pbuf == InvalidBuffer)
2829 : : {
2830 : : /*
2831 : : * Failed to "re-find" a pivot tuple whose downlink matched our child
2832 : : * block number on the parent level -- the index must be corrupt.
2833 : : * Don't even try to delete the leafbuf subtree. Just report the
2834 : : * issue and press on with vacuuming the index.
2835 : : *
2836 : : * Note: _bt_getstackbuf() recovers from concurrent page splits that
2837 : : * take place on the parent level. Its approach is a near-exhaustive
2838 : : * linear search. This also gives it a surprisingly good chance of
2839 : : * recovering in the event of a buggy or inconsistent opclass. But we
2840 : : * don't rely on that here.
2841 : : */
1680 pg@bowt.ie 2842 [ # # ]:UBC 0 : ereport(LOG,
2843 : : (errcode(ERRCODE_INDEX_CORRUPTED),
2844 : : errmsg_internal("failed to re-find parent key in index \"%s\" for deletion target page %u",
2845 : : RelationGetRelationName(rel), child)));
860 2846 : 0 : Assert(false);
2847 : : return false;
2848 : : }
2849 : :
1996 pg@bowt.ie 2850 :CBC 3100 : parent = stack->bts_blkno;
2851 : 3100 : parentoffset = stack->bts_offset;
2852 : :
2853 : 3100 : page = BufferGetPage(pbuf);
1306 michael@paquier.xyz 2854 : 3100 : opaque = BTPageGetOpaque(page);
1996 pg@bowt.ie 2855 : 3100 : maxoff = PageGetMaxOffsetNumber(page);
2856 : 3100 : leftsibparent = opaque->btpo_prev;
2857 : :
2858 : : /*
2859 : : * _bt_getstackbuf() completes page splits on returned parent buffer when
2860 : : * required.
2861 : : *
2862 : : * In general it's a bad idea for VACUUM to use up more disk space, which
2863 : : * is why page deletion does not finish incomplete page splits most of the
2864 : : * time. We allow this limited exception because the risk is much lower,
2865 : : * and the potential downside of not proceeding is much higher: A single
2866 : : * internal page with the INCOMPLETE_SPLIT flag set might otherwise
2867 : : * prevent us from deleting hundreds of empty leaf pages from one level
2868 : : * down.
2869 : : */
2870 [ - + ]: 3100 : Assert(!P_INCOMPLETE_SPLIT(opaque));
2871 : :
2872 [ + + ]: 3100 : if (parentoffset < maxoff)
2873 : : {
2874 : : /*
2875 : : * Child is not the rightmost child in parent, so it's safe to delete
2876 : : * the subtree whose root/topparent is child page
2877 : : */
2878 : 2973 : *subtreeparent = pbuf;
2879 : 2973 : *poffset = parentoffset;
2880 : 2973 : return true;
2881 : : }
2882 : :
2883 : : /*
2884 : : * Child is the rightmost child of parent.
2885 : : *
2886 : : * Since it's the rightmost child of parent, deleting the child (or
2887 : : * deleting the subtree whose root/topparent is the child page) is only
2888 : : * safe when it's also possible to delete the parent.
2889 : : */
2890 [ - + ]: 127 : Assert(parentoffset == maxoff);
2891 [ - + + + : 127 : if (parentoffset != P_FIRSTDATAKEY(opaque) || P_RIGHTMOST(opaque))
- + ]
2892 : : {
2893 : : /*
2894 : : * Child isn't parent's only child, or parent is rightmost on its
2895 : : * entire level. Definitely cannot delete any pages.
2896 : : */
2897 : 4 : _bt_relbuf(rel, pbuf);
2898 : 4 : return false;
2899 : : }
2900 : :
2901 : : /*
2902 : : * Now make sure that the parent deletion is itself safe by examining the
2903 : : * child's grandparent page. Recurse, passing the parent page as the
2904 : : * child page (child's grandparent is the parent on the next level up). If
2905 : : * parent deletion is unsafe, then child deletion must also be unsafe (in
2906 : : * which case caller cannot delete any pages at all).
2907 : : */
2908 : 123 : *topparent = parent;
2909 : 123 : *topparentrightsib = opaque->btpo_next;
2910 : :
2911 : : /*
2912 : : * Release lock on parent before recursing.
2913 : : *
2914 : : * It's OK to release page locks on parent before recursive call locks
2915 : : * grandparent. An internal page can only acquire an entry if the child
2916 : : * is split, but that cannot happen as long as we still hold a lock on the
2917 : : * leafbuf page.
2918 : : */
2919 : 123 : _bt_relbuf(rel, pbuf);
2920 : :
2921 : : /*
2922 : : * Before recursing, check that the left sibling of parent (if any) is not
2923 : : * marked with INCOMPLETE_SPLIT flag first (must do so after we drop the
2924 : : * parent lock).
2925 : : *
2926 : : * Note: We deliberately avoid completing incomplete splits here.
2927 : : */
871 2928 [ - + ]: 123 : if (_bt_leftsib_splitflag(rel, leftsibparent, parent))
1996 pg@bowt.ie 2929 :UBC 0 : return false;
2930 : :
2931 : : /* Recurse to examine child page's grandparent page */
941 andres@anarazel.de 2932 :CBC 123 : return _bt_lock_subtree_parent(rel, heaprel, parent, stack->bts_parent,
2933 : : subtreeparent, poffset,
2934 : : topparent, topparentrightsib);
2935 : : }
2936 : :
2937 : : /*
2938 : : * Initialize local memory state used by VACUUM for _bt_pendingfsm_finalize
2939 : : * optimization.
2940 : : *
2941 : : * Called at the start of a btvacuumscan(). Caller's cleanuponly argument
2942 : : * indicates if ongoing VACUUM has not (and will not) call btbulkdelete().
2943 : : *
2944 : : * We expect to allocate memory inside VACUUM's top-level memory context here.
2945 : : * The working buffer is subject to a limit based on work_mem. Our strategy
2946 : : * when the array can no longer grow within the bounds of that limit is to
2947 : : * stop saving additional newly deleted pages, while proceeding as usual with
2948 : : * the pages that we can fit.
2949 : : */
2950 : : void
1682 pg@bowt.ie 2951 : 1570 : _bt_pendingfsm_init(Relation rel, BTVacState *vstate, bool cleanuponly)
2952 : : {
2953 : : Size maxbufsize;
2954 : :
2955 : : /*
2956 : : * Don't bother with optimization in cleanup-only case -- we don't expect
2957 : : * any newly deleted pages. Besides, cleanup-only calls to btvacuumscan()
2958 : : * can only take place because this optimization didn't work out during
2959 : : * the last VACUUM.
2960 : : */
2961 [ + + ]: 1570 : if (cleanuponly)
2962 : 8 : return;
2963 : :
2964 : : /*
2965 : : * Cap maximum size of array so that we always respect work_mem. Avoid
2966 : : * int overflow here.
2967 : : */
2968 : 1562 : vstate->bufsize = 256;
270 tgl@sss.pgh.pa.us 2969 : 1562 : maxbufsize = (work_mem * (Size) 1024) / sizeof(BTPendingFSM);
1682 pg@bowt.ie 2970 : 1562 : maxbufsize = Min(maxbufsize, MaxAllocSize / sizeof(BTPendingFSM));
2971 : : /* BTVacState.maxbufsize has type int */
270 tgl@sss.pgh.pa.us 2972 : 1562 : maxbufsize = Min(maxbufsize, INT_MAX);
2973 : : /* Stay sane with small work_mem */
1682 pg@bowt.ie 2974 : 1562 : maxbufsize = Max(maxbufsize, vstate->bufsize);
270 tgl@sss.pgh.pa.us 2975 : 1562 : vstate->maxbufsize = (int) maxbufsize;
2976 : :
2977 : : /* Allocate buffer, indicate that there are currently 0 pending pages */
1682 pg@bowt.ie 2978 : 1562 : vstate->pendingpages = palloc(sizeof(BTPendingFSM) * vstate->bufsize);
2979 : 1562 : vstate->npendingpages = 0;
2980 : : }
2981 : :
2982 : : /*
2983 : : * Place any newly deleted pages (i.e. pages that _bt_pagedel() deleted during
2984 : : * the ongoing VACUUM operation) into the free space map -- though only when
2985 : : * it is actually safe to do so by now.
2986 : : *
2987 : : * Called at the end of a btvacuumscan(), just before free space map vacuuming
2988 : : * takes place.
2989 : : *
2990 : : * Frees memory allocated by _bt_pendingfsm_init(), if any.
2991 : : */
2992 : : void
2993 : 1570 : _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate)
2994 : : {
2995 : 1570 : IndexBulkDeleteResult *stats = vstate->stats;
893 tgl@sss.pgh.pa.us 2996 : 1570 : Relation heaprel = vstate->info->heaprel;
2997 : :
1682 pg@bowt.ie 2998 [ - + ]: 1570 : Assert(stats->pages_newly_deleted >= vstate->npendingpages);
871 2999 [ - + ]: 1570 : Assert(heaprel != NULL);
3000 : :
1682 3001 [ + + ]: 1570 : if (vstate->npendingpages == 0)
3002 : : {
3003 : : /* Just free memory when nothing to do */
3004 [ + + ]: 1469 : if (vstate->pendingpages)
3005 : 1461 : pfree(vstate->pendingpages);
3006 : :
3007 : 1469 : return;
3008 : : }
3009 : :
3010 : : #ifdef DEBUG_BTREE_PENDING_FSM
3011 : :
3012 : : /*
3013 : : * Debugging aid: Sleep for 5 seconds to greatly increase the chances of
3014 : : * placing pending pages in the FSM. Note that the optimization will
3015 : : * never be effective without some other backend concurrently consuming an
3016 : : * XID.
3017 : : */
3018 : : pg_usleep(5000000L);
3019 : : #endif
3020 : :
3021 : : /*
3022 : : * Recompute VACUUM XID boundaries.
3023 : : *
3024 : : * We don't actually care about the oldest non-removable XID. Computing
3025 : : * the oldest such XID has a useful side-effect that we rely on: it
3026 : : * forcibly updates the XID horizon state for this backend. This step is
3027 : : * essential; GlobalVisCheckRemovableFullXid() will not reliably recognize
3028 : : * that it is now safe to recycle newly deleted pages without this step.
3029 : : */
939 3030 : 101 : GetOldestNonRemovableTransactionId(heaprel);
3031 : :
1682 3032 [ + + ]: 177 : for (int i = 0; i < vstate->npendingpages; i++)
3033 : : {
3034 : 175 : BlockNumber target = vstate->pendingpages[i].target;
3035 : 175 : FullTransactionId safexid = vstate->pendingpages[i].safexid;
3036 : :
3037 : : /*
3038 : : * Do the equivalent of checking BTPageIsRecyclable(), but without
3039 : : * accessing the page again a second time.
3040 : : *
3041 : : * Give up on finding the first non-recyclable page -- all later pages
3042 : : * must be non-recyclable too, since _bt_pendingfsm_add() adds pages
3043 : : * to the array in safexid order.
3044 : : */
939 3045 [ + + ]: 175 : if (!GlobalVisCheckRemovableFullXid(heaprel, safexid))
1682 3046 : 99 : break;
3047 : :
3048 : 76 : RecordFreeIndexPage(rel, target);
3049 : 76 : stats->pages_free++;
3050 : : }
3051 : :
3052 : 101 : pfree(vstate->pendingpages);
3053 : : }
3054 : :
3055 : : /*
3056 : : * Maintain array of pages that were deleted during current btvacuumscan()
3057 : : * call, for use in _bt_pendingfsm_finalize()
3058 : : */
3059 : : static void
3060 : 3087 : _bt_pendingfsm_add(BTVacState *vstate,
3061 : : BlockNumber target,
3062 : : FullTransactionId safexid)
3063 : : {
3064 [ - + ]: 3087 : Assert(vstate->npendingpages <= vstate->bufsize);
3065 [ - + ]: 3087 : Assert(vstate->bufsize <= vstate->maxbufsize);
3066 : :
3067 : : #ifdef USE_ASSERT_CHECKING
3068 : :
3069 : : /*
3070 : : * Verify an assumption made by _bt_pendingfsm_finalize(): pages from the
3071 : : * array will always be in safexid order (since that is the order that we
3072 : : * save them in here)
3073 : : */
3074 [ + + ]: 3087 : if (vstate->npendingpages > 0)
3075 : : {
3076 : 2986 : FullTransactionId lastsafexid =
893 tgl@sss.pgh.pa.us 3077 : 2986 : vstate->pendingpages[vstate->npendingpages - 1].safexid;
3078 : :
1682 pg@bowt.ie 3079 [ - + ]: 2986 : Assert(FullTransactionIdFollowsOrEquals(safexid, lastsafexid));
3080 : : }
3081 : : #endif
3082 : :
3083 : : /*
3084 : : * If temp buffer reaches maxbufsize/work_mem capacity then we discard
3085 : : * information about this page.
3086 : : *
3087 : : * Note that this also covers the case where we opted to not use the
3088 : : * optimization in _bt_pendingfsm_init().
3089 : : */
3090 [ - + ]: 3087 : if (vstate->npendingpages == vstate->maxbufsize)
1682 pg@bowt.ie 3091 :UBC 0 : return;
3092 : :
3093 : : /* Consider enlarging buffer */
1682 pg@bowt.ie 3094 [ + + ]:CBC 3087 : if (vstate->npendingpages == vstate->bufsize)
3095 : : {
3096 : 4 : int newbufsize = vstate->bufsize * 2;
3097 : :
3098 : : /* Respect work_mem */
3099 [ - + ]: 4 : if (newbufsize > vstate->maxbufsize)
1682 pg@bowt.ie 3100 :UBC 0 : newbufsize = vstate->maxbufsize;
3101 : :
1682 pg@bowt.ie 3102 :CBC 4 : vstate->bufsize = newbufsize;
3103 : 4 : vstate->pendingpages =
3104 : 4 : repalloc(vstate->pendingpages,
3105 : 4 : sizeof(BTPendingFSM) * vstate->bufsize);
3106 : : }
3107 : :
3108 : : /* Save metadata for newly deleted page */
3109 : 3087 : vstate->pendingpages[vstate->npendingpages].target = target;
3110 : 3087 : vstate->pendingpages[vstate->npendingpages].safexid = safexid;
3111 : 3087 : vstate->npendingpages++;
3112 : : }
|
