PostgreSQL Source Code  git master
nbtpage.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * nbtpage.c
4  * BTree-specific page management code for the Postgres btree access
5  * method.
6  *
7  * Portions Copyright (c) 1996-2023, 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 "miscadmin.h"
32 #include "storage/indexfsm.h"
33 #include "storage/lmgr.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
67 _bt_initmetapage(Page page, BlockNumber rootbknum, uint32 level,
68  bool allequalimage)
69 {
70  BTMetaPageData *metad;
71  BTPageOpaque metaopaque;
72 
73  _bt_pageinit(page, BLCKSZ);
74 
75  metad = BTPageGetMeta(page);
76  metad->btm_magic = BTREE_MAGIC;
77  metad->btm_version = BTREE_VERSION;
78  metad->btm_root = rootbknum;
79  metad->btm_level = level;
80  metad->btm_fastroot = rootbknum;
81  metad->btm_fastlevel = level;
84  metad->btm_allequalimage = allequalimage;
85 
86  metaopaque = BTPageGetOpaque(page);
87  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  */
94  ((PageHeader) page)->pd_lower =
95  ((char *) metad + sizeof(BTMetaPageData)) - (char *) page;
96 }
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
108 {
109  BTMetaPageData *metad;
111 
112  metad = BTPageGetMeta(page);
113  metaopaque = BTPageGetOpaque(page);
114 
115  /* It must be really a meta page of upgradable version */
116  Assert(metaopaque->btpo_flags & BTP_META);
119 
120  /* Set version number and fill extra fields added into version 3 */
123  metad->btm_last_cleanup_num_heap_tuples = -1.0;
124  /* Only a REINDEX can set this field */
125  Assert(!metad->btm_allequalimage);
126  metad->btm_allequalimage = false;
127 
128  /* Adjust pd_lower (see _bt_initmetapage() for details) */
129  ((PageHeader) page)->pd_lower =
130  ((char *) metad + sizeof(BTMetaPageData)) - (char *) page;
131 }
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 *
143 {
144  Page metapg;
145  BTPageOpaque metaopaque;
146  BTMetaPageData *metad;
147 
148  metapg = BufferGetPage(metabuf);
149  metaopaque = BTPageGetOpaque(metapg);
150  metad = BTPageGetMeta(metapg);
151 
152  /* sanity-check the metapage */
153  if (!P_ISMETA(metaopaque) ||
154  metad->btm_magic != BTREE_MAGIC)
155  ereport(ERROR,
156  (errcode(ERRCODE_INDEX_CORRUPTED),
157  errmsg("index \"%s\" is not a btree",
158  RelationGetRelationName(rel))));
159 
160  if (metad->btm_version < BTREE_MIN_VERSION ||
161  metad->btm_version > BTREE_VERSION)
162  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",
168 
169  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
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  metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
193  metapg = BufferGetPage(metabuf);
194  metad = BTPageGetMeta(metapg);
195  btm_version = metad->btm_version;
196 
197  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  */
203  _bt_relbuf(rel, metabuf);
204  return true;
205  }
206 
207  prev_num_delpages = metad->btm_last_cleanup_num_delpages;
208  _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  if (prev_num_delpages > 0 &&
219  prev_num_delpages > RelationGetNumberOfBlocks(rel) / 20)
220  return true;
221 
222  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
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  metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
257  metapg = BufferGetPage(metabuf);
258  metad = BTPageGetMeta(metapg);
259 
260  /* Don't miss chance to upgrade index/metapage when BTREE_MIN_VERSION */
261  if (metad->btm_version >= BTREE_NOVAC_VERSION &&
262  metad->btm_last_cleanup_num_delpages == num_delpages)
263  {
264  /* Usually means index continues to have num_delpages of 0 */
265  _bt_relbuf(rel, metabuf);
266  return;
267  }
268 
269  /* trade in our read lock for a write lock */
270  _bt_unlockbuf(rel, metabuf);
271  _bt_lockbuf(rel, metabuf, BT_WRITE);
272 
274 
275  /* upgrade meta-page if needed */
276  if (metad->btm_version < BTREE_NOVAC_VERSION)
277  _bt_upgrademetapage(metapg);
278 
279  /* update cleanup-related information */
280  metad->btm_last_cleanup_num_delpages = num_delpages;
281  metad->btm_last_cleanup_num_heap_tuples = -1.0;
282  MarkBufferDirty(metabuf);
283 
284  /* write wal record if needed */
285  if (RelationNeedsWAL(rel))
286  {
288  XLogRecPtr recptr;
289 
290  XLogBeginInsert();
292 
294  md.version = metad->btm_version;
295  md.root = metad->btm_root;
296  md.level = metad->btm_level;
297  md.fastroot = metad->btm_fastroot;
298  md.fastlevel = metad->btm_fastlevel;
299  md.last_cleanup_num_delpages = num_delpages;
300  md.allequalimage = metad->btm_allequalimage;
301 
302  XLogRegisterBufData(0, (char *) &md, sizeof(xl_btree_metadata));
303 
304  recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_META_CLEANUP);
305 
306  PageSetLSN(metapg, recptr);
307  }
308 
310 
311  _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
345 {
346  Buffer metabuf;
347  Buffer rootbuf;
348  Page rootpage;
349  BTPageOpaque rootopaque;
350  BlockNumber rootblkno;
351  uint32 rootlevel;
352  BTMetaPageData *metad;
353 
354  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  */
361  if (rel->rd_amcache != NULL)
362  {
363  metad = (BTMetaPageData *) rel->rd_amcache;
364  /* We shouldn't have cached it if any of these fail */
365  Assert(metad->btm_magic == BTREE_MAGIC);
367  Assert(metad->btm_version <= BTREE_VERSION);
368  Assert(!metad->btm_allequalimage ||
370  Assert(metad->btm_root != P_NONE);
371 
372  rootblkno = metad->btm_fastroot;
373  Assert(rootblkno != P_NONE);
374  rootlevel = metad->btm_fastlevel;
375 
376  rootbuf = _bt_getbuf(rel, rootblkno, BT_READ);
377  rootpage = BufferGetPage(rootbuf);
378  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  */
387  if (!P_IGNORE(rootopaque) &&
388  rootopaque->btpo_level == rootlevel &&
389  P_LEFTMOST(rootopaque) &&
390  P_RIGHTMOST(rootopaque))
391  {
392  /* OK, accept cached page as the root */
393  return rootbuf;
394  }
395  _bt_relbuf(rel, rootbuf);
396  /* Cache is stale, throw it away */
397  if (rel->rd_amcache)
398  pfree(rel->rd_amcache);
399  rel->rd_amcache = NULL;
400  }
401 
402  metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
403  metad = _bt_getmeta(rel, metabuf);
404 
405  /* if no root page initialized yet, do it */
406  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 */
411  if (access == BT_READ)
412  {
413  _bt_relbuf(rel, metabuf);
414  return InvalidBuffer;
415  }
416 
417  /* trade in our read lock for a write lock */
418  _bt_unlockbuf(rel, metabuf);
419  _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  */
426  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  */
434  _bt_relbuf(rel, metabuf);
435  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  */
443  rootbuf = _bt_allocbuf(rel, heaprel);
444  rootblkno = BufferGetBlockNumber(rootbuf);
445  rootpage = BufferGetPage(rootbuf);
446  rootopaque = BTPageGetOpaque(rootpage);
447  rootopaque->btpo_prev = rootopaque->btpo_next = P_NONE;
448  rootopaque->btpo_flags = (BTP_LEAF | BTP_ROOT);
449  rootopaque->btpo_level = 0;
450  rootopaque->btpo_cycleid = 0;
451  /* Get raw page pointer for metapage */
452  metapg = BufferGetPage(metabuf);
453 
454  /* NO ELOG(ERROR) till meta is updated */
456 
457  /* upgrade metapage if needed */
458  if (metad->btm_version < BTREE_NOVAC_VERSION)
459  _bt_upgrademetapage(metapg);
460 
461  metad->btm_root = rootblkno;
462  metad->btm_level = 0;
463  metad->btm_fastroot = rootblkno;
464  metad->btm_fastlevel = 0;
466  metad->btm_last_cleanup_num_heap_tuples = -1.0;
467 
468  MarkBufferDirty(rootbuf);
469  MarkBufferDirty(metabuf);
470 
471  /* XLOG stuff */
472  if (RelationNeedsWAL(rel))
473  {
474  xl_btree_newroot xlrec;
475  XLogRecPtr recptr;
477 
478  XLogBeginInsert();
481 
483  md.version = metad->btm_version;
484  md.root = rootblkno;
485  md.level = 0;
486  md.fastroot = rootblkno;
487  md.fastlevel = 0;
489  md.allequalimage = metad->btm_allequalimage;
490 
491  XLogRegisterBufData(2, (char *) &md, sizeof(xl_btree_metadata));
492 
493  xlrec.rootblk = rootblkno;
494  xlrec.level = 0;
495 
496  XLogRegisterData((char *) &xlrec, SizeOfBtreeNewroot);
497 
498  recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_NEWROOT);
499 
500  PageSetLSN(rootpage, recptr);
501  PageSetLSN(metapg, recptr);
502  }
503 
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  */
511  _bt_unlockbuf(rel, rootbuf);
512  _bt_lockbuf(rel, rootbuf, BT_READ);
513 
514  /* okay, metadata is correct, release lock on it without caching */
515  _bt_relbuf(rel, metabuf);
516  }
517  else
518  {
519  rootblkno = metad->btm_fastroot;
520  Assert(rootblkno != P_NONE);
521  rootlevel = metad->btm_fastlevel;
522 
523  /*
524  * Cache the metapage data for next time
525  */
527  sizeof(BTMetaPageData));
528  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  */
534  rootbuf = metabuf;
535 
536  for (;;)
537  {
538  rootbuf = _bt_relandgetbuf(rel, rootbuf, rootblkno, BT_READ);
539  rootpage = BufferGetPage(rootbuf);
540  rootopaque = BTPageGetOpaque(rootpage);
541 
542  if (!P_IGNORE(rootopaque))
543  break;
544 
545  /* it's dead, Jim. step right one page */
546  if (P_RIGHTMOST(rootopaque))
547  elog(ERROR, "no live root page found in index \"%s\"",
549  rootblkno = rootopaque->btpo_next;
550  }
551 
552  if (rootopaque->btpo_level != rootlevel)
553  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  */
562  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
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  */
598  if (rel->rd_amcache)
599  pfree(rel->rd_amcache);
600  rel->rd_amcache = NULL;
601 
602  metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
603  metapg = BufferGetPage(metabuf);
604  metaopaque = BTPageGetOpaque(metapg);
605  metad = BTPageGetMeta(metapg);
606 
607  if (!P_ISMETA(metaopaque) ||
608  metad->btm_magic != BTREE_MAGIC)
609  ereport(ERROR,
610  (errcode(ERRCODE_INDEX_CORRUPTED),
611  errmsg("index \"%s\" is not a btree",
612  RelationGetRelationName(rel))));
613 
614  if (metad->btm_version < BTREE_MIN_VERSION ||
615  metad->btm_version > BTREE_VERSION)
616  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",
622 
623  /* if no root page initialized yet, fail */
624  if (metad->btm_root == P_NONE)
625  {
626  _bt_relbuf(rel, metabuf);
627  return InvalidBuffer;
628  }
629 
630  rootblkno = metad->btm_root;
631  rootlevel = metad->btm_level;
632 
633  /*
634  * We are done with the metapage; arrange to release it via first
635  * _bt_relandgetbuf call
636  */
637  rootbuf = metabuf;
638 
639  for (;;)
640  {
641  rootbuf = _bt_relandgetbuf(rel, rootbuf, rootblkno, BT_READ);
642  rootpage = BufferGetPage(rootbuf);
643  rootopaque = BTPageGetOpaque(rootpage);
644 
645  if (!P_IGNORE(rootopaque))
646  break;
647 
648  /* it's dead, Jim. step right one page */
649  if (P_RIGHTMOST(rootopaque))
650  elog(ERROR, "no live root page found in index \"%s\"",
652  rootblkno = rootopaque->btpo_next;
653  }
654 
655  if (rootopaque->btpo_level != rootlevel)
656  elog(ERROR, "root page %u of index \"%s\" has level %u, expected %u",
657  rootblkno, RelationGetRelationName(rel),
658  rootopaque->btpo_level, rootlevel);
659 
660  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
676 {
677  BTMetaPageData *metad;
678 
679  if (rel->rd_amcache == NULL)
680  {
681  Buffer metabuf;
682 
683  metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
684  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  */
691  if (metad->btm_root == P_NONE)
692  {
693  _bt_relbuf(rel, metabuf);
694  return 0;
695  }
696 
697  /*
698  * Cache the metapage data for next time
699  */
701  sizeof(BTMetaPageData));
702  memcpy(rel->rd_amcache, metad, sizeof(BTMetaPageData));
703  _bt_relbuf(rel, metabuf);
704  }
705 
706  /* Get cached page */
707  metad = (BTMetaPageData *) rel->rd_amcache;
708  /* We shouldn't have cached it if any of these fail */
709  Assert(metad->btm_magic == BTREE_MAGIC);
711  Assert(metad->btm_version <= BTREE_VERSION);
712  Assert(!metad->btm_allequalimage ||
714  Assert(metad->btm_fastroot != P_NONE);
715 
716  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
739 _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
740 {
741  BTMetaPageData *metad;
742 
743  if (rel->rd_amcache == NULL)
744  {
745  Buffer metabuf;
746 
747  metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
748  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  if (metad->btm_root == P_NONE)
756  {
757  *heapkeyspace = metad->btm_version > BTREE_NOVAC_VERSION;
758  *allequalimage = metad->btm_allequalimage;
759 
760  _bt_relbuf(rel, metabuf);
761  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  */
774  sizeof(BTMetaPageData));
775  memcpy(rel->rd_amcache, metad, sizeof(BTMetaPageData));
776  _bt_relbuf(rel, metabuf);
777  }
778 
779  /* Get cached page */
780  metad = (BTMetaPageData *) rel->rd_amcache;
781  /* We shouldn't have cached it if any of these fail */
782  Assert(metad->btm_magic == BTREE_MAGIC);
784  Assert(metad->btm_version <= BTREE_VERSION);
785  Assert(!metad->btm_allequalimage ||
787  Assert(metad->btm_fastroot != P_NONE);
788 
789  *heapkeyspace = metad->btm_version > BTREE_NOVAC_VERSION;
790  *allequalimage = metad->btm_allequalimage;
791 }
792 
793 /*
794  * _bt_checkpage() -- Verify that a freshly-read page looks sane.
795  */
796 void
798 {
799  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  */
807  if (PageIsNew(page))
808  ereport(ERROR,
809  (errcode(ERRCODE_INDEX_CORRUPTED),
810  errmsg("index \"%s\" contains unexpected zero page at block %u",
813  errhint("Please REINDEX it.")));
814 
815  /*
816  * Additionally check that the special area looks sane.
817  */
818  if (PageGetSpecialSize(page) != MAXALIGN(sizeof(BTPageOpaqueData)))
819  ereport(ERROR,
820  (errcode(ERRCODE_INDEX_CORRUPTED),
821  errmsg("index \"%s\" contains corrupted page at block %u",
824  errhint("Please REINDEX it.")));
825 }
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
846 {
847  Buffer buf;
848 
849  Assert(BlockNumberIsValid(blkno));
850 
851  /* Read an existing block of the relation */
852  buf = ReadBuffer(rel, blkno);
853  _bt_lockbuf(rel, buf, access);
854  _bt_checkpage(rel, buf);
855 
856  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
870 {
871  Buffer buf;
872  BlockNumber blkno;
873  Page page;
874 
875  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  blkno = GetFreeIndexPage(rel);
904  if (blkno == InvalidBlockNumber)
905  break;
906  buf = ReadBuffer(rel, blkno);
907  if (_bt_conditionallockbuf(rel, buf))
908  {
909  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  if (PageIsNew(page))
919  {
920  /* Okay to use page. Initialize and return it. */
922  return buf;
923  }
924 
925  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  */
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  xlrec_reuse.locator = rel->rd_locator;
945  xlrec_reuse.block = blkno;
946  xlrec_reuse.snapshotConflictHorizon = BTPageGetDeleteXid(page);
947  xlrec_reuse.isCatalogRel =
949 
950  XLogBeginInsert();
951  XLogRegisterData((char *) &xlrec_reuse, SizeOfBtreeReusePage);
952 
953  XLogInsert(RM_BTREE_ID, XLOG_BTREE_REUSE_PAGE);
954  }
955 
956  /* Okay to use page. Re-initialize and return it. */
958  return buf;
959  }
960  elog(DEBUG2, "FSM returned nonrecyclable page");
961  _bt_relbuf(rel, buf);
962  }
963  else
964  {
965  elog(DEBUG2, "FSM returned nonlockable page");
966  /* couldn't get lock, so just drop pin */
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  */
979  if (!RelationUsesLocalBuffers(rel))
981 
982  /* Initialize the new page before returning it */
983  page = BufferGetPage(buf);
984  Assert(PageIsNew(page));
986 
987  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
1004 {
1005  Buffer buf;
1006 
1007  Assert(BlockNumberIsValid(blkno));
1008  if (BufferIsValid(obuf))
1009  _bt_unlockbuf(rel, obuf);
1010  buf = ReleaseAndReadBuffer(obuf, rel, blkno);
1011  _bt_lockbuf(rel, buf, access);
1012 
1013  _bt_checkpage(rel, buf);
1014  return buf;
1015 }
1016 
1017 /*
1018  * _bt_relbuf() -- release a locked buffer.
1019  *
1020  * Lock and pin (refcount) are both dropped.
1021  */
1022 void
1024 {
1025  _bt_unlockbuf(rel, buf);
1026  ReleaseBuffer(buf);
1027 }
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
1040 {
1041  /* LockBuffer() asserts that pin is held by this backend */
1042  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  if (!RelationUsesLocalBuffers(rel))
1064 }
1065 
1066 /*
1067  * _bt_unlockbuf() -- unlock a pinned buffer.
1068  */
1069 void
1071 {
1072  /*
1073  * Buffer is pinned and locked, which means that it is expected to be
1074  * defined and addressable. Check that proactively.
1075  */
1077 
1078  /* LockBuffer() asserts that pin is held by this backend */
1080 
1081  if (!RelationUsesLocalBuffers(rel))
1083 }
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
1094 {
1095  /* ConditionalLockBuffer() asserts that pin is held by this backend */
1096  if (!ConditionalLockBuffer(buf))
1097  return false;
1098 
1099  if (!RelationUsesLocalBuffers(rel))
1101 
1102  return true;
1103 }
1104 
1105 /*
1106  * _bt_upgradelockbufcleanup() -- upgrade lock to a full cleanup lock.
1107  */
1108 void
1110 {
1111  /*
1112  * Buffer is pinned and locked, which means that it is expected to be
1113  * defined and addressable. Check that proactively.
1114  */
1116 
1117  /* LockBuffer() asserts that pin is held by this backend */
1120 }
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
1130 {
1131  PageInit(page, size, sizeof(BTPageOpaqueData));
1132 }
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
1155  OffsetNumber *deletable, int ndeletable,
1156  BTVacuumPosting *updatable, int nupdatable)
1157 {
1158  Page page = BufferGetPage(buf);
1159  BTPageOpaque opaque;
1160  bool needswal = RelationNeedsWAL(rel);
1161  char *updatedbuf = NULL;
1162  Size updatedbuflen = 0;
1163  OffsetNumber updatedoffsets[MaxIndexTuplesPerPage];
1164 
1165  /* Shouldn't be called unless there's something to do */
1166  Assert(ndeletable > 0 || nupdatable > 0);
1167 
1168  /* Generate new version of posting lists without deleted TIDs */
1169  if (nupdatable > 0)
1170  updatedbuf = _bt_delitems_update(updatable, nupdatable,
1171  updatedoffsets, &updatedbuflen,
1172  needswal);
1173 
1174  /* No ereport(ERROR) until changes are logged */
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  */
1189  for (int i = 0; i < nupdatable; i++)
1190  {
1191  OffsetNumber updatedoffset = updatedoffsets[i];
1192  IndexTuple itup;
1193  Size itemsz;
1194 
1195  itup = updatable[i]->itup;
1196  itemsz = MAXALIGN(IndexTupleSize(itup));
1197  if (!PageIndexTupleOverwrite(page, updatedoffset, (Item) itup,
1198  itemsz))
1199  elog(PANIC, "failed to update partially dead item in block %u of index \"%s\"",
1201  }
1202 
1203  /* Now handle simple deletes of entire tuples */
1204  if (ndeletable > 0)
1205  PageIndexMultiDelete(page, deletable, ndeletable);
1206 
1207  /*
1208  * We can clear the vacuum cycle ID since this page has certainly been
1209  * processed by the current vacuum scan.
1210  */
1211  opaque = BTPageGetOpaque(page);
1212  opaque->btpo_cycleid = 0;
1213 
1214  /*
1215  * Clear the BTP_HAS_GARBAGE page flag.
1216  *
1217  * This flag indicates the presence of LP_DEAD items on the page (though
1218  * not reliably). Note that we only rely on it with pg_upgrade'd
1219  * !heapkeyspace indexes. That's why clearing it here won't usually
1220  * interfere with simple index tuple deletion.
1221  */
1222  opaque->btpo_flags &= ~BTP_HAS_GARBAGE;
1223 
1225 
1226  /* XLOG stuff */
1227  if (needswal)
1228  {
1229  XLogRecPtr recptr;
1230  xl_btree_vacuum xlrec_vacuum;
1231 
1232  xlrec_vacuum.ndeleted = ndeletable;
1233  xlrec_vacuum.nupdated = nupdatable;
1234 
1235  XLogBeginInsert();
1237  XLogRegisterData((char *) &xlrec_vacuum, SizeOfBtreeVacuum);
1238 
1239  if (ndeletable > 0)
1240  XLogRegisterBufData(0, (char *) deletable,
1241  ndeletable * sizeof(OffsetNumber));
1242 
1243  if (nupdatable > 0)
1244  {
1245  XLogRegisterBufData(0, (char *) updatedoffsets,
1246  nupdatable * sizeof(OffsetNumber));
1247  XLogRegisterBufData(0, updatedbuf, updatedbuflen);
1248  }
1249 
1250  recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_VACUUM);
1251 
1252  PageSetLSN(page, recptr);
1253  }
1254 
1255  END_CRIT_SECTION();
1256 
1257  /* can't leak memory here */
1258  if (updatedbuf != NULL)
1259  pfree(updatedbuf);
1260  /* free tuples allocated within _bt_delitems_update() */
1261  for (int i = 0; i < nupdatable; i++)
1262  pfree(updatable[i]->itup);
1263 }
1264 
1265 /*
1266  * Delete item(s) from a btree leaf page during single-page cleanup.
1267  *
1268  * This routine assumes that the caller has pinned and write locked the
1269  * buffer. Also, the given deletable and updatable arrays *must* be sorted in
1270  * ascending order.
1271  *
1272  * Routine deals with deleting TIDs when some (but not all) of the heap TIDs
1273  * in an existing posting list item are to be removed. This works by
1274  * updating/overwriting an existing item with caller's new version of the item
1275  * (a version that lacks the TIDs that are to be deleted).
1276  *
1277  * This is nearly the same as _bt_delitems_vacuum as far as what it does to
1278  * the page, but it needs its own snapshotConflictHorizon and isCatalogRel
1279  * (from the tableam). This is used by the REDO routine to generate recovery
1280  * conflicts. The other difference is that only _bt_delitems_vacuum will
1281  * clear page's VACUUM cycle ID.
1282  */
1283 static void
1285  TransactionId snapshotConflictHorizon, bool isCatalogRel,
1286  OffsetNumber *deletable, int ndeletable,
1287  BTVacuumPosting *updatable, int nupdatable)
1288 {
1289  Page page = BufferGetPage(buf);
1290  BTPageOpaque opaque;
1291  bool needswal = RelationNeedsWAL(rel);
1292  char *updatedbuf = NULL;
1293  Size updatedbuflen = 0;
1294  OffsetNumber updatedoffsets[MaxIndexTuplesPerPage];
1295 
1296  /* Shouldn't be called unless there's something to do */
1297  Assert(ndeletable > 0 || nupdatable > 0);
1298 
1299  /* Generate new versions of posting lists without deleted TIDs */
1300  if (nupdatable > 0)
1301  updatedbuf = _bt_delitems_update(updatable, nupdatable,
1302  updatedoffsets, &updatedbuflen,
1303  needswal);
1304 
1305  /* No ereport(ERROR) until changes are logged */
1307 
1308  /* Handle updates and deletes just like _bt_delitems_vacuum */
1309  for (int i = 0; i < nupdatable; i++)
1310  {
1311  OffsetNumber updatedoffset = updatedoffsets[i];
1312  IndexTuple itup;
1313  Size itemsz;
1314 
1315  itup = updatable[i]->itup;
1316  itemsz = MAXALIGN(IndexTupleSize(itup));
1317  if (!PageIndexTupleOverwrite(page, updatedoffset, (Item) itup,
1318  itemsz))
1319  elog(PANIC, "failed to update partially dead item in block %u of index \"%s\"",
1321  }
1322 
1323  if (ndeletable > 0)
1324  PageIndexMultiDelete(page, deletable, ndeletable);
1325 
1326  /*
1327  * Unlike _bt_delitems_vacuum, we *must not* clear the vacuum cycle ID at
1328  * this point. The VACUUM command alone controls vacuum cycle IDs.
1329  */
1330  opaque = BTPageGetOpaque(page);
1331 
1332  /*
1333  * Clear the BTP_HAS_GARBAGE page flag.
1334  *
1335  * This flag indicates the presence of LP_DEAD items on the page (though
1336  * not reliably). Note that we only rely on it with pg_upgrade'd
1337  * !heapkeyspace indexes.
1338  */
1339  opaque->btpo_flags &= ~BTP_HAS_GARBAGE;
1340 
1342 
1343  /* XLOG stuff */
1344  if (needswal)
1345  {
1346  XLogRecPtr recptr;
1347  xl_btree_delete xlrec_delete;
1348 
1349  xlrec_delete.snapshotConflictHorizon = snapshotConflictHorizon;
1350  xlrec_delete.ndeleted = ndeletable;
1351  xlrec_delete.nupdated = nupdatable;
1352  xlrec_delete.isCatalogRel = isCatalogRel;
1353 
1354  XLogBeginInsert();
1356  XLogRegisterData((char *) &xlrec_delete, SizeOfBtreeDelete);
1357 
1358  if (ndeletable > 0)
1359  XLogRegisterBufData(0, (char *) deletable,
1360  ndeletable * sizeof(OffsetNumber));
1361 
1362  if (nupdatable > 0)
1363  {
1364  XLogRegisterBufData(0, (char *) updatedoffsets,
1365  nupdatable * sizeof(OffsetNumber));
1366  XLogRegisterBufData(0, updatedbuf, updatedbuflen);
1367  }
1368 
1369  recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_DELETE);
1370 
1371  PageSetLSN(page, recptr);
1372  }
1373 
1374  END_CRIT_SECTION();
1375 
1376  /* can't leak memory here */
1377  if (updatedbuf != NULL)
1378  pfree(updatedbuf);
1379  /* free tuples allocated within _bt_delitems_update() */
1380  for (int i = 0; i < nupdatable; i++)
1381  pfree(updatable[i]->itup);
1382 }
1383 
1384 /*
1385  * Set up state needed to delete TIDs from posting list tuples via "updating"
1386  * the tuple. Performs steps common to both _bt_delitems_vacuum and
1387  * _bt_delitems_delete. These steps must take place before each function's
1388  * critical section begins.
1389  *
1390  * updatable and nupdatable are inputs, though note that we will use
1391  * _bt_update_posting() to replace the original itup with a pointer to a final
1392  * version in palloc()'d memory. Caller should free the tuples when its done.
1393  *
1394  * The first nupdatable entries from updatedoffsets are set to the page offset
1395  * number for posting list tuples that caller updates. This is mostly useful
1396  * because caller may need to WAL-log the page offsets (though we always do
1397  * this for caller out of convenience).
1398  *
1399  * Returns buffer consisting of an array of xl_btree_update structs that
1400  * describe the steps we perform here for caller (though only when needswal is
1401  * true). Also sets *updatedbuflen to the final size of the buffer. This
1402  * buffer is used by caller when WAL logging is required.
1403  */
1404 static char *
1405 _bt_delitems_update(BTVacuumPosting *updatable, int nupdatable,
1406  OffsetNumber *updatedoffsets, Size *updatedbuflen,
1407  bool needswal)
1408 {
1409  char *updatedbuf = NULL;
1410  Size buflen = 0;
1411 
1412  /* Shouldn't be called unless there's something to do */
1413  Assert(nupdatable > 0);
1414 
1415  for (int i = 0; i < nupdatable; i++)
1416  {
1417  BTVacuumPosting vacposting = updatable[i];
1418  Size itemsz;
1419 
1420  /* Replace work area IndexTuple with updated version */
1421  _bt_update_posting(vacposting);
1422 
1423  /* Keep track of size of xl_btree_update for updatedbuf in passing */
1424  itemsz = SizeOfBtreeUpdate + vacposting->ndeletedtids * sizeof(uint16);
1425  buflen += itemsz;
1426 
1427  /* Build updatedoffsets buffer in passing */
1428  updatedoffsets[i] = vacposting->updatedoffset;
1429  }
1430 
1431  /* XLOG stuff */
1432  if (needswal)
1433  {
1434  Size offset = 0;
1435 
1436  /* Allocate, set final size for caller */
1437  updatedbuf = palloc(buflen);
1438  *updatedbuflen = buflen;
1439  for (int i = 0; i < nupdatable; i++)
1440  {
1441  BTVacuumPosting vacposting = updatable[i];
1442  Size itemsz;
1443  xl_btree_update update;
1444 
1445  update.ndeletedtids = vacposting->ndeletedtids;
1446  memcpy(updatedbuf + offset, &update.ndeletedtids,
1448  offset += SizeOfBtreeUpdate;
1449 
1450  itemsz = update.ndeletedtids * sizeof(uint16);
1451  memcpy(updatedbuf + offset, vacposting->deletetids, itemsz);
1452  offset += itemsz;
1453  }
1454  }
1455 
1456  return updatedbuf;
1457 }
1458 
1459 /*
1460  * Comparator used by _bt_delitems_delete_check() to restore deltids array
1461  * back to its original leaf-page-wise sort order
1462  */
1463 static int
1464 _bt_delitems_cmp(const void *a, const void *b)
1465 {
1466  TM_IndexDelete *indexdelete1 = (TM_IndexDelete *) a;
1467  TM_IndexDelete *indexdelete2 = (TM_IndexDelete *) b;
1468 
1469  if (indexdelete1->id > indexdelete2->id)
1470  return 1;
1471  if (indexdelete1->id < indexdelete2->id)
1472  return -1;
1473 
1474  Assert(false);
1475 
1476  return 0;
1477 }
1478 
1479 /*
1480  * Try to delete item(s) from a btree leaf page during single-page cleanup.
1481  *
1482  * nbtree interface to table_index_delete_tuples(). Deletes a subset of index
1483  * tuples from caller's deltids array: those whose TIDs are found safe to
1484  * delete by the tableam (or already marked LP_DEAD in index, and so already
1485  * known to be deletable by our simple index deletion caller). We physically
1486  * delete index tuples from buf leaf page last of all (for index tuples where
1487  * that is known to be safe following our table_index_delete_tuples() call).
1488  *
1489  * Simple index deletion caller only includes TIDs from index tuples marked
1490  * LP_DEAD, as well as extra TIDs it found on the same leaf page that can be
1491  * included without increasing the total number of distinct table blocks for
1492  * the deletion operation as a whole. This approach often allows us to delete
1493  * some extra index tuples that were practically free for tableam to check in
1494  * passing (when they actually turn out to be safe to delete). It probably
1495  * only makes sense for the tableam to go ahead with these extra checks when
1496  * it is block-oriented (otherwise the checks probably won't be practically
1497  * free, which we rely on). The tableam interface requires the tableam side
1498  * to handle the problem, though, so this is okay (we as an index AM are free
1499  * to make the simplifying assumption that all tableams must be block-based).
1500  *
1501  * Bottom-up index deletion caller provides all the TIDs from the leaf page,
1502  * without expecting that tableam will check most of them. The tableam has
1503  * considerable discretion around which entries/blocks it checks. Our role in
1504  * costing the bottom-up deletion operation is strictly advisory.
1505  *
1506  * Note: Caller must have added deltids entries (i.e. entries that go in
1507  * delstate's main array) in leaf-page-wise order: page offset number order,
1508  * TID order among entries taken from the same posting list tuple (tiebreak on
1509  * TID). This order is convenient to work with here.
1510  *
1511  * Note: We also rely on the id field of each deltids element "capturing" this
1512  * original leaf-page-wise order. That is, we expect to be able to get back
1513  * to the original leaf-page-wise order just by sorting deltids on the id
1514  * field (tableam will sort deltids for its own reasons, so we'll need to put
1515  * it back in leaf-page-wise order afterwards).
1516  */
1517 void
1519  TM_IndexDeleteOp *delstate)
1520 {
1521  Page page = BufferGetPage(buf);
1522  TransactionId snapshotConflictHorizon;
1523  bool isCatalogRel;
1524  OffsetNumber postingidxoffnum = InvalidOffsetNumber;
1525  int ndeletable = 0,
1526  nupdatable = 0;
1529 
1530  /* Use tableam interface to determine which tuples to delete first */
1531  snapshotConflictHorizon = table_index_delete_tuples(heapRel, delstate);
1532  isCatalogRel = RelationIsAccessibleInLogicalDecoding(heapRel);
1533 
1534  /* Should not WAL-log snapshotConflictHorizon unless it's required */
1535  if (!XLogStandbyInfoActive())
1536  snapshotConflictHorizon = InvalidTransactionId;
1537 
1538  /*
1539  * Construct a leaf-page-wise description of what _bt_delitems_delete()
1540  * needs to do to physically delete index tuples from the page.
1541  *
1542  * Must sort deltids array to restore leaf-page-wise order (original order
1543  * before call to tableam). This is the order that the loop expects.
1544  *
1545  * Note that deltids array might be a lot smaller now. It might even have
1546  * no entries at all (with bottom-up deletion caller), in which case there
1547  * is nothing left to do.
1548  */
1549  qsort(delstate->deltids, delstate->ndeltids, sizeof(TM_IndexDelete),
1551  if (delstate->ndeltids == 0)
1552  {
1553  Assert(delstate->bottomup);
1554  return;
1555  }
1556 
1557  /* We definitely have to delete at least one index tuple (or one TID) */
1558  for (int i = 0; i < delstate->ndeltids; i++)
1559  {
1560  TM_IndexStatus *dstatus = delstate->status + delstate->deltids[i].id;
1561  OffsetNumber idxoffnum = dstatus->idxoffnum;
1562  ItemId itemid = PageGetItemId(page, idxoffnum);
1563  IndexTuple itup = (IndexTuple) PageGetItem(page, itemid);
1564  int nestedi,
1565  nitem;
1566  BTVacuumPosting vacposting;
1567 
1568  Assert(OffsetNumberIsValid(idxoffnum));
1569 
1570  if (idxoffnum == postingidxoffnum)
1571  {
1572  /*
1573  * This deltid entry is a TID from a posting list tuple that has
1574  * already been completely processed
1575  */
1576  Assert(BTreeTupleIsPosting(itup));
1578  &delstate->deltids[i].tid) < 0);
1580  &delstate->deltids[i].tid) >= 0);
1581  continue;
1582  }
1583 
1584  if (!BTreeTupleIsPosting(itup))
1585  {
1586  /* Plain non-pivot tuple */
1587  Assert(ItemPointerEquals(&itup->t_tid, &delstate->deltids[i].tid));
1588  if (dstatus->knowndeletable)
1589  deletable[ndeletable++] = idxoffnum;
1590  continue;
1591  }
1592 
1593  /*
1594  * itup is a posting list tuple whose lowest deltids entry (which may
1595  * or may not be for the first TID from itup) is considered here now.
1596  * We should process all of the deltids entries for the posting list
1597  * together now, though (not just the lowest). Remember to skip over
1598  * later itup-related entries during later iterations of outermost
1599  * loop.
1600  */
1601  postingidxoffnum = idxoffnum; /* Remember work in outermost loop */
1602  nestedi = i; /* Initialize for first itup deltids entry */
1603  vacposting = NULL; /* Describes final action for itup */
1604  nitem = BTreeTupleGetNPosting(itup);
1605  for (int p = 0; p < nitem; p++)
1606  {
1607  ItemPointer ptid = BTreeTupleGetPostingN(itup, p);
1608  int ptidcmp = -1;
1609 
1610  /*
1611  * This nested loop reuses work across ptid TIDs taken from itup.
1612  * We take advantage of the fact that both itup's TIDs and deltids
1613  * entries (within a single itup/posting list grouping) must both
1614  * be in ascending TID order.
1615  */
1616  for (; nestedi < delstate->ndeltids; nestedi++)
1617  {
1618  TM_IndexDelete *tcdeltid = &delstate->deltids[nestedi];
1619  TM_IndexStatus *tdstatus = (delstate->status + tcdeltid->id);
1620 
1621  /* Stop once we get past all itup related deltids entries */
1622  Assert(tdstatus->idxoffnum >= idxoffnum);
1623  if (tdstatus->idxoffnum != idxoffnum)
1624  break;
1625 
1626  /* Skip past non-deletable itup related entries up front */
1627  if (!tdstatus->knowndeletable)
1628  continue;
1629 
1630  /* Entry is first partial ptid match (or an exact match)? */
1631  ptidcmp = ItemPointerCompare(&tcdeltid->tid, ptid);
1632  if (ptidcmp >= 0)
1633  {
1634  /* Greater than or equal (partial or exact) match... */
1635  break;
1636  }
1637  }
1638 
1639  /* ...exact ptid match to a deletable deltids entry? */
1640  if (ptidcmp != 0)
1641  continue;
1642 
1643  /* Exact match for deletable deltids entry -- ptid gets deleted */
1644  if (vacposting == NULL)
1645  {
1646  vacposting = palloc(offsetof(BTVacuumPostingData, deletetids) +
1647  nitem * sizeof(uint16));
1648  vacposting->itup = itup;
1649  vacposting->updatedoffset = idxoffnum;
1650  vacposting->ndeletedtids = 0;
1651  }
1652  vacposting->deletetids[vacposting->ndeletedtids++] = p;
1653  }
1654 
1655  /* Final decision on itup, a posting list tuple */
1656 
1657  if (vacposting == NULL)
1658  {
1659  /* No TIDs to delete from itup -- do nothing */
1660  }
1661  else if (vacposting->ndeletedtids == nitem)
1662  {
1663  /* Straight delete of itup (to delete all TIDs) */
1664  deletable[ndeletable++] = idxoffnum;
1665  /* Turns out we won't need granular information */
1666  pfree(vacposting);
1667  }
1668  else
1669  {
1670  /* Delete some (but not all) TIDs from itup */
1671  Assert(vacposting->ndeletedtids > 0 &&
1672  vacposting->ndeletedtids < nitem);
1673  updatable[nupdatable++] = vacposting;
1674  }
1675  }
1676 
1677  /* Physically delete tuples (or TIDs) using deletable (or updatable) */
1678  _bt_delitems_delete(rel, buf, snapshotConflictHorizon, isCatalogRel,
1679  deletable, ndeletable, updatable, nupdatable);
1680 
1681  /* be tidy */
1682  for (int i = 0; i < nupdatable; i++)
1683  pfree(updatable[i]);
1684 }
1685 
1686 /*
1687  * Check that leftsib page (the btpo_prev of target page) is not marked with
1688  * INCOMPLETE_SPLIT flag. Used during page deletion.
1689  *
1690  * Returning true indicates that page flag is set in leftsib (which is
1691  * definitely still the left sibling of target). When that happens, the
1692  * target doesn't have a downlink in parent, and the page deletion algorithm
1693  * isn't prepared to handle that. Deletion of the target page (or the whole
1694  * subtree that contains the target page) cannot take place.
1695  *
1696  * Caller should not have a lock on the target page itself, since pages on the
1697  * same level must always be locked left to right to avoid deadlocks.
1698  */
1699 static bool
1701 {
1702  Buffer buf;
1703  Page page;
1704  BTPageOpaque opaque;
1705  bool result;
1706 
1707  /* Easy case: No left sibling */
1708  if (leftsib == P_NONE)
1709  return false;
1710 
1711  buf = _bt_getbuf(rel, leftsib, BT_READ);
1712  page = BufferGetPage(buf);
1713  opaque = BTPageGetOpaque(page);
1714 
1715  /*
1716  * If the left sibling was concurrently split, so that its next-pointer
1717  * doesn't point to the current page anymore, the split that created
1718  * target must be completed. Caller can reasonably expect that there will
1719  * be a downlink to the target page that it can relocate using its stack.
1720  * (We don't allow splitting an incompletely split page again until the
1721  * previous split has been completed.)
1722  */
1723  result = (opaque->btpo_next == target && P_INCOMPLETE_SPLIT(opaque));
1724  _bt_relbuf(rel, buf);
1725 
1726  return result;
1727 }
1728 
1729 /*
1730  * Check that leafrightsib page (the btpo_next of target leaf page) is not
1731  * marked with ISHALFDEAD flag. Used during page deletion.
1732  *
1733  * Returning true indicates that page flag is set in leafrightsib, so page
1734  * deletion cannot go ahead. Our caller is not prepared to deal with the case
1735  * where the parent page does not have a pivot tuples whose downlink points to
1736  * leafrightsib (due to an earlier interrupted VACUUM operation). It doesn't
1737  * seem worth going to the trouble of teaching our caller to deal with it.
1738  * The situation will be resolved after VACUUM finishes the deletion of the
1739  * half-dead page (when a future VACUUM operation reaches the target page
1740  * again).
1741  *
1742  * _bt_leftsib_splitflag() is called for both leaf pages and internal pages.
1743  * _bt_rightsib_halfdeadflag() is only called for leaf pages, though. This is
1744  * okay because of the restriction on deleting pages that are the rightmost
1745  * page of their parent (i.e. that such deletions can only take place when the
1746  * entire subtree must be deleted). The leaf level check made here will apply
1747  * to a right "cousin" leaf page rather than a simple right sibling leaf page
1748  * in cases where caller actually goes on to attempt deleting pages that are
1749  * above the leaf page. The right cousin leaf page is representative of the
1750  * left edge of the subtree to the right of the to-be-deleted subtree as a
1751  * whole, which is exactly the condition that our caller cares about.
1752  * (Besides, internal pages are never marked half-dead, so it isn't even
1753  * possible to _directly_ assess if an internal page is part of some other
1754  * to-be-deleted subtree.)
1755  */
1756 static bool
1758 {
1759  Buffer buf;
1760  Page page;
1761  BTPageOpaque opaque;
1762  bool result;
1763 
1764  Assert(leafrightsib != P_NONE);
1765 
1766  buf = _bt_getbuf(rel, leafrightsib, BT_READ);
1767  page = BufferGetPage(buf);
1768  opaque = BTPageGetOpaque(page);
1769 
1770  Assert(P_ISLEAF(opaque) && !P_ISDELETED(opaque));
1771  result = P_ISHALFDEAD(opaque);
1772  _bt_relbuf(rel, buf);
1773 
1774  return result;
1775 }
1776 
1777 /*
1778  * _bt_pagedel() -- Delete a leaf page from the b-tree, if legal to do so.
1779  *
1780  * This action unlinks the leaf page from the b-tree structure, removing all
1781  * pointers leading to it --- but not touching its own left and right links.
1782  * The page cannot be physically reclaimed right away, since other processes
1783  * may currently be trying to follow links leading to the page; they have to
1784  * be allowed to use its right-link to recover. See nbtree/README.
1785  *
1786  * On entry, the target buffer must be pinned and locked (either read or write
1787  * lock is OK). The page must be an empty leaf page, which may be half-dead
1788  * already (a half-dead page should only be passed to us when an earlier
1789  * VACUUM operation was interrupted, though). Note in particular that caller
1790  * should never pass a buffer containing an existing deleted page here. The
1791  * lock and pin on caller's buffer will be dropped before we return.
1792  *
1793  * Maintains bulk delete stats for caller, which are taken from vstate. We
1794  * need to cooperate closely with caller here so that whole VACUUM operation
1795  * reliably avoids any double counting of subsidiary-to-leafbuf pages that we
1796  * delete in passing. If such pages happen to be from a block number that is
1797  * ahead of the current scanblkno position, then caller is expected to count
1798  * them directly later on. It's simpler for us to understand caller's
1799  * requirements than it would be for caller to understand when or how a
1800  * deleted page became deleted after the fact.
1801  *
1802  * NOTE: this leaks memory. Rather than trying to clean up everything
1803  * carefully, it's better to run it in a temp context that can be reset
1804  * frequently.
1805  */
1806 void
1807 _bt_pagedel(Relation rel, Buffer leafbuf, BTVacState *vstate)
1808 {
1809  BlockNumber rightsib;
1810  bool rightsib_empty;
1811  Page page;
1812  BTPageOpaque opaque;
1813 
1814  /*
1815  * Save original leafbuf block number from caller. Only deleted blocks
1816  * that are <= scanblkno are added to bulk delete stat's pages_deleted
1817  * count.
1818  */
1819  BlockNumber scanblkno = BufferGetBlockNumber(leafbuf);
1820 
1821  /*
1822  * "stack" is a search stack leading (approximately) to the target page.
1823  * It is initially NULL, but when iterating, we keep it to avoid
1824  * duplicated search effort.
1825  *
1826  * Also, when "stack" is not NULL, we have already checked that the
1827  * current page is not the right half of an incomplete split, i.e. the
1828  * left sibling does not have its INCOMPLETE_SPLIT flag set, including
1829  * when the current target page is to the right of caller's initial page
1830  * (the scanblkno page).
1831  */
1832  BTStack stack = NULL;
1833 
1834  for (;;)
1835  {
1836  page = BufferGetPage(leafbuf);
1837  opaque = BTPageGetOpaque(page);
1838 
1839  /*
1840  * Internal pages are never deleted directly, only as part of deleting
1841  * the whole subtree all the way down to leaf level.
1842  *
1843  * Also check for deleted pages here. Caller never passes us a fully
1844  * deleted page. Only VACUUM can delete pages, so there can't have
1845  * been a concurrent deletion. Assume that we reached any deleted
1846  * page encountered here by following a sibling link, and that the
1847  * index is corrupt.
1848  */
1849  Assert(!P_ISDELETED(opaque));
1850  if (!P_ISLEAF(opaque) || P_ISDELETED(opaque))
1851  {
1852  /*
1853  * Pre-9.4 page deletion only marked internal pages as half-dead,
1854  * but now we only use that flag on leaf pages. The old algorithm
1855  * was never supposed to leave half-dead pages in the tree, it was
1856  * just a transient state, but it was nevertheless possible in
1857  * error scenarios. We don't know how to deal with them here. They
1858  * are harmless as far as searches are considered, but inserts
1859  * into the deleted keyspace could add out-of-order downlinks in
1860  * the upper levels. Log a notice, hopefully the admin will notice
1861  * and reindex.
1862  */
1863  if (P_ISHALFDEAD(opaque))
1864  ereport(LOG,
1865  (errcode(ERRCODE_INDEX_CORRUPTED),
1866  errmsg("index \"%s\" contains a half-dead internal page",
1868  errhint("This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));
1869 
1870  if (P_ISDELETED(opaque))
1871  ereport(LOG,
1872  (errcode(ERRCODE_INDEX_CORRUPTED),
1873  errmsg_internal("found deleted block %u while following right link from block %u in index \"%s\"",
1874  BufferGetBlockNumber(leafbuf),
1875  scanblkno,
1876  RelationGetRelationName(rel))));
1877 
1878  _bt_relbuf(rel, leafbuf);
1879  return;
1880  }
1881 
1882  /*
1883  * We can never delete rightmost pages nor root pages. While at it,
1884  * check that page is empty, since it's possible that the leafbuf page
1885  * was empty a moment ago, but has since had some inserts.
1886  *
1887  * To keep the algorithm simple, we also never delete an incompletely
1888  * split page (they should be rare enough that this doesn't make any
1889  * meaningful difference to disk usage):
1890  *
1891  * The INCOMPLETE_SPLIT flag on the page tells us if the page is the
1892  * left half of an incomplete split, but ensuring that it's not the
1893  * right half is more complicated. For that, we have to check that
1894  * the left sibling doesn't have its INCOMPLETE_SPLIT flag set using
1895  * _bt_leftsib_splitflag(). On the first iteration, we temporarily
1896  * release the lock on scanblkno/leafbuf, check the left sibling, and
1897  * construct a search stack to scanblkno. On subsequent iterations,
1898  * we know we stepped right from a page that passed these tests, so
1899  * it's OK.
1900  */
1901  if (P_RIGHTMOST(opaque) || P_ISROOT(opaque) ||
1902  P_FIRSTDATAKEY(opaque) <= PageGetMaxOffsetNumber(page) ||
1903  P_INCOMPLETE_SPLIT(opaque))
1904  {
1905  /* Should never fail to delete a half-dead page */
1906  Assert(!P_ISHALFDEAD(opaque));
1907 
1908  _bt_relbuf(rel, leafbuf);
1909  return;
1910  }
1911 
1912  /*
1913  * First, remove downlink pointing to the page (or a parent of the
1914  * page, if we are going to delete a taller subtree), and mark the
1915  * leafbuf page half-dead
1916  */
1917  if (!P_ISHALFDEAD(opaque))
1918  {
1919  /*
1920  * We need an approximate pointer to the page's parent page. We
1921  * use a variant of the standard search mechanism to search for
1922  * the page's high key; this will give us a link to either the
1923  * current parent or someplace to its left (if there are multiple
1924  * equal high keys, which is possible with !heapkeyspace indexes).
1925  *
1926  * Also check if this is the right-half of an incomplete split
1927  * (see comment above).
1928  */
1929  if (!stack)
1930  {
1931  BTScanInsert itup_key;
1932  ItemId itemid;
1933  IndexTuple targetkey;
1934  BlockNumber leftsib,
1935  leafblkno;
1936  Buffer sleafbuf;
1937 
1938  itemid = PageGetItemId(page, P_HIKEY);
1939  targetkey = CopyIndexTuple((IndexTuple) PageGetItem(page, itemid));
1940 
1941  leftsib = opaque->btpo_prev;
1942  leafblkno = BufferGetBlockNumber(leafbuf);
1943 
1944  /*
1945  * To avoid deadlocks, we'd better drop the leaf page lock
1946  * before going further.
1947  */
1948  _bt_unlockbuf(rel, leafbuf);
1949 
1950  /*
1951  * Check that the left sibling of leafbuf (if any) is not
1952  * marked with INCOMPLETE_SPLIT flag before proceeding
1953  */
1954  Assert(leafblkno == scanblkno);
1955  if (_bt_leftsib_splitflag(rel, leftsib, leafblkno))
1956  {
1957  ReleaseBuffer(leafbuf);
1958  return;
1959  }
1960 
1961  /* we need an insertion scan key for the search, so build one */
1962  itup_key = _bt_mkscankey(rel, targetkey);
1963  /* find the leftmost leaf page with matching pivot/high key */
1964  itup_key->pivotsearch = true;
1965  stack = _bt_search(rel, NULL, itup_key, &sleafbuf, BT_READ);
1966  /* won't need a second lock or pin on leafbuf */
1967  _bt_relbuf(rel, sleafbuf);
1968 
1969  /*
1970  * Re-lock the leaf page, and start over to use our stack
1971  * within _bt_mark_page_halfdead. We must do it that way
1972  * because it's possible that leafbuf can no longer be
1973  * deleted. We need to recheck.
1974  *
1975  * Note: We can't simply hold on to the sleafbuf lock instead,
1976  * because it's barely possible that sleafbuf is not the same
1977  * page as leafbuf. This happens when leafbuf split after our
1978  * original lock was dropped, but before _bt_search finished
1979  * its descent. We rely on the assumption that we'll find
1980  * leafbuf isn't safe to delete anymore in this scenario.
1981  * (Page deletion can cope with the stack being to the left of
1982  * leafbuf, but not to the right of leafbuf.)
1983  */
1984  _bt_lockbuf(rel, leafbuf, BT_WRITE);
1985  continue;
1986  }
1987 
1988  /*
1989  * See if it's safe to delete the leaf page, and determine how
1990  * many parent/internal pages above the leaf level will be
1991  * deleted. If it's safe then _bt_mark_page_halfdead will also
1992  * perform the first phase of deletion, which includes marking the
1993  * leafbuf page half-dead.
1994  */
1995  Assert(P_ISLEAF(opaque) && !P_IGNORE(opaque));
1996  if (!_bt_mark_page_halfdead(rel, vstate->info->heaprel, leafbuf,
1997  stack))
1998  {
1999  _bt_relbuf(rel, leafbuf);
2000  return;
2001  }
2002  }
2003 
2004  /*
2005  * Then unlink it from its siblings. Each call to
2006  * _bt_unlink_halfdead_page unlinks the topmost page from the subtree,
2007  * making it shallower. Iterate until the leafbuf page is deleted.
2008  */
2009  rightsib_empty = false;
2010  Assert(P_ISLEAF(opaque) && P_ISHALFDEAD(opaque));
2011  while (P_ISHALFDEAD(opaque))
2012  {
2013  /* Check for interrupts in _bt_unlink_halfdead_page */
2014  if (!_bt_unlink_halfdead_page(rel, leafbuf, scanblkno,
2015  &rightsib_empty, vstate))
2016  {
2017  /*
2018  * _bt_unlink_halfdead_page should never fail, since we
2019  * established that deletion is generally safe in
2020  * _bt_mark_page_halfdead -- index must be corrupt.
2021  *
2022  * Note that _bt_unlink_halfdead_page already released the
2023  * lock and pin on leafbuf for us.
2024  */
2025  Assert(false);
2026  return;
2027  }
2028  }
2029 
2030  Assert(P_ISLEAF(opaque) && P_ISDELETED(opaque));
2031 
2032  rightsib = opaque->btpo_next;
2033 
2034  _bt_relbuf(rel, leafbuf);
2035 
2036  /*
2037  * Check here, as calling loops will have locks held, preventing
2038  * interrupts from being processed.
2039  */
2041 
2042  /*
2043  * The page has now been deleted. If its right sibling is completely
2044  * empty, it's possible that the reason we haven't deleted it earlier
2045  * is that it was the rightmost child of the parent. Now that we
2046  * removed the downlink for this page, the right sibling might now be
2047  * the only child of the parent, and could be removed. It would be
2048  * picked up by the next vacuum anyway, but might as well try to
2049  * remove it now, so loop back to process the right sibling.
2050  *
2051  * Note: This relies on the assumption that _bt_getstackbuf() will be
2052  * able to reuse our original descent stack with a different child
2053  * block (provided that the child block is to the right of the
2054  * original leaf page reached by _bt_search()). It will even update
2055  * the descent stack each time we loop around, avoiding repeated work.
2056  */
2057  if (!rightsib_empty)
2058  break;
2059 
2060  leafbuf = _bt_getbuf(rel, rightsib, BT_WRITE);
2061  }
2062 }
2063 
2064 /*
2065  * First stage of page deletion.
2066  *
2067  * Establish the height of the to-be-deleted subtree with leafbuf at its
2068  * lowest level, remove the downlink to the subtree, and mark leafbuf
2069  * half-dead. The final to-be-deleted subtree is usually just leafbuf itself,
2070  * but may include additional internal pages (at most one per level of the
2071  * tree below the root).
2072  *
2073  * Caller must pass a valid heaprel, since it's just about possible that our
2074  * call to _bt_lock_subtree_parent will need to allocate a new index page to
2075  * complete a page split. Every call to _bt_allocbuf needs to pass a heaprel.
2076  *
2077  * Returns 'false' if leafbuf is unsafe to delete, usually because leafbuf is
2078  * the rightmost child of its parent (and parent has more than one downlink).
2079  * Returns 'true' when the first stage of page deletion completed
2080  * successfully.
2081  */
2082 static bool
2084  BTStack stack)
2085 {
2086  BlockNumber leafblkno;
2087  BlockNumber leafrightsib;
2088  BlockNumber topparent;
2089  BlockNumber topparentrightsib;
2090  ItemId itemid;
2091  Page page;
2092  BTPageOpaque opaque;
2093  Buffer subtreeparent;
2094  OffsetNumber poffset;
2095  OffsetNumber nextoffset;
2096  IndexTuple itup;
2097  IndexTupleData trunctuple;
2098 
2099  page = BufferGetPage(leafbuf);
2100  opaque = BTPageGetOpaque(page);
2101 
2102  Assert(!P_RIGHTMOST(opaque) && !P_ISROOT(opaque) &&
2103  P_ISLEAF(opaque) && !P_IGNORE(opaque) &&
2104  P_FIRSTDATAKEY(opaque) > PageGetMaxOffsetNumber(page));
2105  Assert(heaprel != NULL);
2106 
2107  /*
2108  * Save info about the leaf page.
2109  */
2110  leafblkno = BufferGetBlockNumber(leafbuf);
2111  leafrightsib = opaque->btpo_next;
2112 
2113  /*
2114  * Before attempting to lock the parent page, check that the right sibling
2115  * is not in half-dead state. A half-dead right sibling would have no
2116  * downlink in the parent, which would be highly confusing later when we
2117  * delete the downlink. It would fail the "right sibling of target page
2118  * is also the next child in parent page" cross-check below.
2119  */
2120  if (_bt_rightsib_halfdeadflag(rel, leafrightsib))
2121  {
2122  elog(DEBUG1, "could not delete page %u because its right sibling %u is half-dead",
2123  leafblkno, leafrightsib);
2124  return false;
2125  }
2126 
2127  /*
2128  * We cannot delete a page that is the rightmost child of its immediate
2129  * parent, unless it is the only child --- in which case the parent has to
2130  * be deleted too, and the same condition applies recursively to it. We
2131  * have to check this condition all the way up before trying to delete,
2132  * and lock the parent of the root of the to-be-deleted subtree (the
2133  * "subtree parent"). _bt_lock_subtree_parent() locks the subtree parent
2134  * for us. We remove the downlink to the "top parent" page (subtree root
2135  * page) from the subtree parent page below.
2136  *
2137  * Initialize topparent to be leafbuf page now. The final to-be-deleted
2138  * subtree is often a degenerate one page subtree consisting only of the
2139  * leafbuf page. When that happens, the leafbuf page is the final subtree
2140  * root page/top parent page.
2141  */
2142  topparent = leafblkno;
2143  topparentrightsib = leafrightsib;
2144  if (!_bt_lock_subtree_parent(rel, heaprel, leafblkno, stack,
2145  &subtreeparent, &poffset,
2146  &topparent, &topparentrightsib))
2147  return false;
2148 
2149  page = BufferGetPage(subtreeparent);
2150  opaque = BTPageGetOpaque(page);
2151 
2152 #ifdef USE_ASSERT_CHECKING
2153 
2154  /*
2155  * This is just an assertion because _bt_lock_subtree_parent should have
2156  * guaranteed tuple has the expected contents
2157  */
2158  itemid = PageGetItemId(page, poffset);
2159  itup = (IndexTuple) PageGetItem(page, itemid);
2160  Assert(BTreeTupleGetDownLink(itup) == topparent);
2161 #endif
2162 
2163  nextoffset = OffsetNumberNext(poffset);
2164  itemid = PageGetItemId(page, nextoffset);
2165  itup = (IndexTuple) PageGetItem(page, itemid);
2166 
2167  /*
2168  * Check that the parent-page index items we're about to delete/overwrite
2169  * in subtree parent page contain what we expect. This can fail if the
2170  * index has become corrupt for some reason. When that happens we back
2171  * out of deletion of the leafbuf subtree. (This is just like the case
2172  * where _bt_lock_subtree_parent() cannot "re-find" leafbuf's downlink.)
2173  */
2174  if (BTreeTupleGetDownLink(itup) != topparentrightsib)
2175  {
2176  ereport(LOG,
2177  (errcode(ERRCODE_INDEX_CORRUPTED),
2178  errmsg_internal("right sibling %u of block %u is not next child %u of block %u in index \"%s\"",
2179  topparentrightsib, topparent,
2180  BTreeTupleGetDownLink(itup),
2181  BufferGetBlockNumber(subtreeparent),
2182  RelationGetRelationName(rel))));
2183 
2184  _bt_relbuf(rel, subtreeparent);
2185  Assert(false);
2186  return false;
2187  }
2188 
2189  /*
2190  * Any insert which would have gone on the leaf block will now go to its
2191  * right sibling. In other words, the key space moves right.
2192  */
2193  PredicateLockPageCombine(rel, leafblkno, leafrightsib);
2194 
2195  /* No ereport(ERROR) until changes are logged */
2197 
2198  /*
2199  * Update parent of subtree. We want to delete the downlink to the top
2200  * parent page/root of the subtree, and the *following* key. Easiest way
2201  * is to copy the right sibling's downlink over the downlink that points
2202  * to top parent page, and then delete the right sibling's original pivot
2203  * tuple.
2204  *
2205  * Lanin and Shasha make the key space move left when deleting a page,
2206  * whereas the key space moves right here. That's why we cannot simply
2207  * delete the pivot tuple with the downlink to the top parent page. See
2208  * nbtree/README.
2209  */
2210  page = BufferGetPage(subtreeparent);
2211  opaque = BTPageGetOpaque(page);
2212 
2213  itemid = PageGetItemId(page, poffset);
2214  itup = (IndexTuple) PageGetItem(page, itemid);
2215  BTreeTupleSetDownLink(itup, topparentrightsib);
2216 
2217  nextoffset = OffsetNumberNext(poffset);
2218  PageIndexTupleDelete(page, nextoffset);
2219 
2220  /*
2221  * Mark the leaf page as half-dead, and stamp it with a link to the top
2222  * parent page. When the leaf page is also the top parent page, the link
2223  * is set to InvalidBlockNumber.
2224  */
2225  page = BufferGetPage(leafbuf);
2226  opaque = BTPageGetOpaque(page);
2227  opaque->btpo_flags |= BTP_HALF_DEAD;
2228 
2230  MemSet(&trunctuple, 0, sizeof(IndexTupleData));
2231  trunctuple.t_info = sizeof(IndexTupleData);
2232  if (topparent != leafblkno)
2233  BTreeTupleSetTopParent(&trunctuple, topparent);
2234  else
2236 
2237  if (!PageIndexTupleOverwrite(page, P_HIKEY, (Item) &trunctuple,
2238  IndexTupleSize(&trunctuple)))
2239  elog(ERROR, "could not overwrite high key in half-dead page");
2240 
2241  /* Must mark buffers dirty before XLogInsert */
2242  MarkBufferDirty(subtreeparent);
2243  MarkBufferDirty(leafbuf);
2244 
2245  /* XLOG stuff */
2246  if (RelationNeedsWAL(rel))
2247  {
2249  XLogRecPtr recptr;
2250 
2251  xlrec.poffset = poffset;
2252  xlrec.leafblk = leafblkno;
2253  if (topparent != leafblkno)
2254  xlrec.topparent = topparent;
2255  else
2256  xlrec.topparent = InvalidBlockNumber;
2257 
2258  XLogBeginInsert();
2259  XLogRegisterBuffer(0, leafbuf, REGBUF_WILL_INIT);
2260  XLogRegisterBuffer(1, subtreeparent, REGBUF_STANDARD);
2261 
2262  page = BufferGetPage(leafbuf);
2263  opaque = BTPageGetOpaque(page);
2264  xlrec.leftblk = opaque->btpo_prev;
2265  xlrec.rightblk = opaque->btpo_next;
2266 
2268 
2269  recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_MARK_PAGE_HALFDEAD);
2270 
2271  page = BufferGetPage(subtreeparent);
2272  PageSetLSN(page, recptr);
2273  page = BufferGetPage(leafbuf);
2274  PageSetLSN(page, recptr);
2275  }
2276 
2277  END_CRIT_SECTION();
2278 
2279  _bt_relbuf(rel, subtreeparent);
2280  return true;
2281 }
2282 
2283 /*
2284  * Second stage of page deletion.
2285  *
2286  * Unlinks a single page (in the subtree undergoing deletion) from its
2287  * siblings. Also marks the page deleted.
2288  *
2289  * To get rid of the whole subtree, including the leaf page itself, call here
2290  * until the leaf page is deleted. The original "top parent" established in
2291  * the first stage of deletion is deleted in the first call here, while the
2292  * leaf page is deleted in the last call here. Note that the leaf page itself
2293  * is often the initial top parent page.
2294  *
2295  * Returns 'false' if the page could not be unlinked (shouldn't happen). If
2296  * the right sibling of the current target page is empty, *rightsib_empty is
2297  * set to true, allowing caller to delete the target's right sibling page in
2298  * passing. Note that *rightsib_empty is only actually used by caller when
2299  * target page is leafbuf, following last call here for leafbuf/the subtree
2300  * containing leafbuf. (We always set *rightsib_empty for caller, just to be
2301  * consistent.)
2302  *
2303  * Must hold pin and lock on leafbuf at entry (read or write doesn't matter).
2304  * On success exit, we'll be holding pin and write lock. On failure exit,
2305  * we'll release both pin and lock before returning (we define it that way
2306  * to avoid having to reacquire a lock we already released).
2307  */
2308 static bool
2310  bool *rightsib_empty, BTVacState *vstate)
2311 {
2312  BlockNumber leafblkno = BufferGetBlockNumber(leafbuf);
2313  IndexBulkDeleteResult *stats = vstate->stats;
2314  BlockNumber leafleftsib;
2315  BlockNumber leafrightsib;
2316  BlockNumber target;
2317  BlockNumber leftsib;
2318  BlockNumber rightsib;
2319  Buffer lbuf = InvalidBuffer;
2320  Buffer buf;
2321  Buffer rbuf;
2322  Buffer metabuf = InvalidBuffer;
2323  Page metapg = NULL;
2324  BTMetaPageData *metad = NULL;
2325  ItemId itemid;
2326  Page page;
2327  BTPageOpaque opaque;
2328  FullTransactionId safexid;
2329  bool rightsib_is_rightmost;
2330  uint32 targetlevel;
2331  IndexTuple leafhikey;
2332  BlockNumber leaftopparent;
2333 
2334  page = BufferGetPage(leafbuf);
2335  opaque = BTPageGetOpaque(page);
2336 
2337  Assert(P_ISLEAF(opaque) && !P_ISDELETED(opaque) && P_ISHALFDEAD(opaque));
2338 
2339  /*
2340  * Remember some information about the leaf page.
2341  */
2342  itemid = PageGetItemId(page, P_HIKEY);
2343  leafhikey = (IndexTuple) PageGetItem(page, itemid);
2344  target = BTreeTupleGetTopParent(leafhikey);
2345  leafleftsib = opaque->btpo_prev;
2346  leafrightsib = opaque->btpo_next;
2347 
2348  _bt_unlockbuf(rel, leafbuf);
2349 
2350  /*
2351  * Check here, as calling loops will have locks held, preventing
2352  * interrupts from being processed.
2353  */
2355 
2356  /* Unlink the current top parent of the subtree */
2357  if (!BlockNumberIsValid(target))
2358  {
2359  /* Target is leaf page (or leaf page is top parent, if you prefer) */
2360  target = leafblkno;
2361 
2362  buf = leafbuf;
2363  leftsib = leafleftsib;
2364  targetlevel = 0;
2365  }
2366  else
2367  {
2368  /* Target is the internal page taken from leaf's top parent link */
2369  Assert(target != leafblkno);
2370 
2371  /* Fetch the block number of the target's left sibling */
2372  buf = _bt_getbuf(rel, target, BT_READ);
2373  page = BufferGetPage(buf);
2374  opaque = BTPageGetOpaque(page);
2375  leftsib = opaque->btpo_prev;
2376  targetlevel = opaque->btpo_level;
2377  Assert(targetlevel > 0);
2378 
2379  /*
2380  * To avoid deadlocks, we'd better drop the target page lock before
2381  * going further.
2382  */
2383  _bt_unlockbuf(rel, buf);
2384  }
2385 
2386  /*
2387  * We have to lock the pages we need to modify in the standard order:
2388  * moving right, then up. Else we will deadlock against other writers.
2389  *
2390  * So, first lock the leaf page, if it's not the target. Then find and
2391  * write-lock the current left sibling of the target page. The sibling
2392  * that was current a moment ago could have split, so we may have to move
2393  * right.
2394  */
2395  if (target != leafblkno)
2396  _bt_lockbuf(rel, leafbuf, BT_WRITE);
2397  if (leftsib != P_NONE)
2398  {
2399  lbuf = _bt_getbuf(rel, leftsib, BT_WRITE);
2400  page = BufferGetPage(lbuf);
2401  opaque = BTPageGetOpaque(page);
2402  while (P_ISDELETED(opaque) || opaque->btpo_next != target)
2403  {
2404  bool leftsibvalid = true;
2405 
2406  /*
2407  * Before we follow the link from the page that was the left
2408  * sibling mere moments ago, validate its right link. This
2409  * reduces the opportunities for loop to fail to ever make any
2410  * progress in the presence of index corruption.
2411  *
2412  * Note: we rely on the assumption that there can only be one
2413  * vacuum process running at a time (against the same index).
2414  */
2415  if (P_RIGHTMOST(opaque) || P_ISDELETED(opaque) ||
2416  leftsib == opaque->btpo_next)
2417  leftsibvalid = false;
2418 
2419  leftsib = opaque->btpo_next;
2420  _bt_relbuf(rel, lbuf);
2421 
2422  if (!leftsibvalid)
2423  {
2424  /*
2425  * This is known to fail in the field; sibling link corruption
2426  * is relatively common. Press on with vacuuming rather than
2427  * just throwing an ERROR.
2428  */
2429  ereport(LOG,
2430  (errcode(ERRCODE_INDEX_CORRUPTED),
2431  errmsg_internal("valid left sibling for deletion target could not be located: "
2432  "left sibling %u of target %u with leafblkno %u and scanblkno %u on level %u of index \"%s\"",
2433  leftsib, target, leafblkno, scanblkno,
2434  targetlevel, RelationGetRelationName(rel))));
2435 
2436  /* Must release all pins and locks on failure exit */
2437  ReleaseBuffer(buf);
2438  if (target != leafblkno)
2439  _bt_relbuf(rel, leafbuf);
2440 
2441  return false;
2442  }
2443 
2445 
2446  /* step right one page */
2447  lbuf = _bt_getbuf(rel, leftsib, BT_WRITE);
2448  page = BufferGetPage(lbuf);
2449  opaque = BTPageGetOpaque(page);
2450  }
2451  }
2452  else
2453  lbuf = InvalidBuffer;
2454 
2455  /* Next write-lock the target page itself */
2456  _bt_lockbuf(rel, buf, BT_WRITE);
2457  page = BufferGetPage(buf);
2458  opaque = BTPageGetOpaque(page);
2459 
2460  /*
2461  * Check page is still empty etc, else abandon deletion. This is just for
2462  * paranoia's sake; a half-dead page cannot resurrect because there can be
2463  * only one vacuum process running at a time.
2464  */
2465  if (P_RIGHTMOST(opaque) || P_ISROOT(opaque) || P_ISDELETED(opaque))
2466  elog(ERROR, "target page changed status unexpectedly in block %u of index \"%s\"",
2467  target, RelationGetRelationName(rel));
2468 
2469  if (opaque->btpo_prev != leftsib)
2470  ereport(ERROR,
2471  (errcode(ERRCODE_INDEX_CORRUPTED),
2472  errmsg_internal("target page left link unexpectedly changed from %u to %u in block %u of index \"%s\"",
2473  leftsib, opaque->btpo_prev, target,
2474  RelationGetRelationName(rel))));
2475 
2476  if (target == leafblkno)
2477  {
2478  if (P_FIRSTDATAKEY(opaque) <= PageGetMaxOffsetNumber(page) ||
2479  !P_ISLEAF(opaque) || !P_ISHALFDEAD(opaque))
2480  elog(ERROR, "target leaf page changed status unexpectedly in block %u of index \"%s\"",
2481  target, RelationGetRelationName(rel));
2482 
2483  /* Leaf page is also target page: don't set leaftopparent */
2484  leaftopparent = InvalidBlockNumber;
2485  }
2486  else
2487  {
2488  IndexTuple finaldataitem;
2489 
2490  if (P_FIRSTDATAKEY(opaque) != PageGetMaxOffsetNumber(page) ||
2491  P_ISLEAF(opaque))
2492  elog(ERROR, "target internal page on level %u changed status unexpectedly in block %u of index \"%s\"",
2493  targetlevel, target, RelationGetRelationName(rel));
2494 
2495  /* Target is internal: set leaftopparent for next call here... */
2496  itemid = PageGetItemId(page, P_FIRSTDATAKEY(opaque));
2497  finaldataitem = (IndexTuple) PageGetItem(page, itemid);
2498  leaftopparent = BTreeTupleGetDownLink(finaldataitem);
2499  /* ...except when it would be a redundant pointer-to-self */
2500  if (leaftopparent == leafblkno)
2501  leaftopparent = InvalidBlockNumber;
2502  }
2503 
2504  /* No leaftopparent for level 0 (leaf page) or level 1 target */
2505  Assert(!BlockNumberIsValid(leaftopparent) || targetlevel > 1);
2506 
2507  /*
2508  * And next write-lock the (current) right sibling.
2509  */
2510  rightsib = opaque->btpo_next;
2511  rbuf = _bt_getbuf(rel, rightsib, BT_WRITE);
2512  page = BufferGetPage(rbuf);
2513  opaque = BTPageGetOpaque(page);
2514 
2515  /*
2516  * Validate target's right sibling page. Its left link must point back to
2517  * the target page.
2518  */
2519  if (opaque->btpo_prev != target)
2520  {
2521  /*
2522  * This is known to fail in the field; sibling link corruption is
2523  * relatively common. Press on with vacuuming rather than just
2524  * throwing an ERROR (same approach used for left-sibling's-right-link
2525  * validation check a moment ago).
2526  */
2527  ereport(LOG,
2528  (errcode(ERRCODE_INDEX_CORRUPTED),
2529  errmsg_internal("right sibling's left-link doesn't match: "
2530  "right sibling %u of target %u with leafblkno %u "
2531  "and scanblkno %u spuriously links to non-target %u "
2532  "on level %u of index \"%s\"",
2533  rightsib, target, leafblkno,
2534  scanblkno, opaque->btpo_prev,
2535  targetlevel, RelationGetRelationName(rel))));
2536 
2537  /* Must release all pins and locks on failure exit */
2538  if (BufferIsValid(lbuf))
2539  _bt_relbuf(rel, lbuf);
2540  _bt_relbuf(rel, rbuf);
2541  _bt_relbuf(rel, buf);
2542  if (target != leafblkno)
2543  _bt_relbuf(rel, leafbuf);
2544 
2545  return false;
2546  }
2547 
2548  rightsib_is_rightmost = P_RIGHTMOST(opaque);
2549  *rightsib_empty = (P_FIRSTDATAKEY(opaque) > PageGetMaxOffsetNumber(page));
2550 
2551  /*
2552  * If we are deleting the next-to-last page on the target's level, then
2553  * the rightsib is a candidate to become the new fast root. (In theory, it
2554  * might be possible to push the fast root even further down, but the odds
2555  * of doing so are slim, and the locking considerations daunting.)
2556  *
2557  * We can safely acquire a lock on the metapage here --- see comments for
2558  * _bt_newlevel().
2559  */
2560  if (leftsib == P_NONE && rightsib_is_rightmost)
2561  {
2562  page = BufferGetPage(rbuf);
2563  opaque = BTPageGetOpaque(page);
2564  if (P_RIGHTMOST(opaque))
2565  {
2566  /* rightsib will be the only one left on the level */
2567  metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
2568  metapg = BufferGetPage(metabuf);
2569  metad = BTPageGetMeta(metapg);
2570 
2571  /*
2572  * The expected case here is btm_fastlevel == targetlevel+1; if
2573  * the fastlevel is <= targetlevel, something is wrong, and we
2574  * choose to overwrite it to fix it.
2575  */
2576  if (metad->btm_fastlevel > targetlevel + 1)
2577  {
2578  /* no update wanted */
2579  _bt_relbuf(rel, metabuf);
2580  metabuf = InvalidBuffer;
2581  }
2582  }
2583  }
2584 
2585  /*
2586  * Here we begin doing the deletion.
2587  */
2588 
2589  /* No ereport(ERROR) until changes are logged */
2591 
2592  /*
2593  * Update siblings' side-links. Note the target page's side-links will
2594  * continue to point to the siblings. Asserts here are just rechecking
2595  * things we already verified above.
2596  */
2597  if (BufferIsValid(lbuf))
2598  {
2599  page = BufferGetPage(lbuf);
2600  opaque = BTPageGetOpaque(page);
2601  Assert(opaque->btpo_next == target);
2602  opaque->btpo_next = rightsib;
2603  }
2604  page = BufferGetPage(rbuf);
2605  opaque = BTPageGetOpaque(page);
2606  Assert(opaque->btpo_prev == target);
2607  opaque->btpo_prev = leftsib;
2608 
2609  /*
2610  * If we deleted a parent of the targeted leaf page, instead of the leaf
2611  * itself, update the leaf to point to the next remaining child in the
2612  * subtree.
2613  *
2614  * Note: We rely on the fact that a buffer pin on the leaf page has been
2615  * held since leafhikey was initialized. This is safe, though only
2616  * because the page was already half-dead at that point. The leaf page
2617  * cannot have been modified by any other backend during the period when
2618  * no lock was held.
2619  */
2620  if (target != leafblkno)
2621  BTreeTupleSetTopParent(leafhikey, leaftopparent);
2622 
2623  /*
2624  * Mark the page itself deleted. It can be recycled when all current
2625  * transactions are gone. Storing GetTopTransactionId() would work, but
2626  * we're in VACUUM and would not otherwise have an XID. Having already
2627  * updated links to the target, ReadNextFullTransactionId() suffices as an
2628  * upper bound. Any scan having retained a now-stale link is advertising
2629  * in its PGPROC an xmin less than or equal to the value we read here. It
2630  * will continue to do so, holding back the xmin horizon, for the duration
2631  * of that scan.
2632  */
2633  page = BufferGetPage(buf);
2634  opaque = BTPageGetOpaque(page);
2635  Assert(P_ISHALFDEAD(opaque) || !P_ISLEAF(opaque));
2636 
2637  /*
2638  * Store upper bound XID that's used to determine when deleted page is no
2639  * longer needed as a tombstone
2640  */
2641  safexid = ReadNextFullTransactionId();
2642  BTPageSetDeleted(page, safexid);
2643  opaque->btpo_cycleid = 0;
2644 
2645  /* And update the metapage, if needed */
2646  if (BufferIsValid(metabuf))
2647  {
2648  /* upgrade metapage if needed */
2649  if (metad->btm_version < BTREE_NOVAC_VERSION)
2650  _bt_upgrademetapage(metapg);
2651  metad->btm_fastroot = rightsib;
2652  metad->btm_fastlevel = targetlevel;
2653  MarkBufferDirty(metabuf);
2654  }
2655 
2656  /* Must mark buffers dirty before XLogInsert */
2657  MarkBufferDirty(rbuf);
2659  if (BufferIsValid(lbuf))
2660  MarkBufferDirty(lbuf);
2661  if (target != leafblkno)
2662  MarkBufferDirty(leafbuf);
2663 
2664  /* XLOG stuff */
2665  if (RelationNeedsWAL(rel))
2666  {
2667  xl_btree_unlink_page xlrec;
2668  xl_btree_metadata xlmeta;
2669  uint8 xlinfo;
2670  XLogRecPtr recptr;
2671 
2672  XLogBeginInsert();
2673 
2675  if (BufferIsValid(lbuf))
2678  if (target != leafblkno)
2679  XLogRegisterBuffer(3, leafbuf, REGBUF_WILL_INIT);
2680 
2681  /* information stored on the target/to-be-unlinked block */
2682  xlrec.leftsib = leftsib;
2683  xlrec.rightsib = rightsib;
2684  xlrec.level = targetlevel;
2685  xlrec.safexid = safexid;
2686 
2687  /* information needed to recreate the leaf block (if not the target) */
2688  xlrec.leafleftsib = leafleftsib;
2689  xlrec.leafrightsib = leafrightsib;
2690  xlrec.leaftopparent = leaftopparent;
2691 
2692  XLogRegisterData((char *) &xlrec, SizeOfBtreeUnlinkPage);
2693 
2694  if (BufferIsValid(metabuf))
2695  {
2697 
2699  xlmeta.version = metad->btm_version;
2700  xlmeta.root = metad->btm_root;
2701  xlmeta.level = metad->btm_level;
2702  xlmeta.fastroot = metad->btm_fastroot;
2703  xlmeta.fastlevel = metad->btm_fastlevel;
2705  xlmeta.allequalimage = metad->btm_allequalimage;
2706 
2707  XLogRegisterBufData(4, (char *) &xlmeta, sizeof(xl_btree_metadata));
2708  xlinfo = XLOG_BTREE_UNLINK_PAGE_META;
2709  }
2710  else
2711  xlinfo = XLOG_BTREE_UNLINK_PAGE;
2712 
2713  recptr = XLogInsert(RM_BTREE_ID, xlinfo);
2714 
2715  if (BufferIsValid(metabuf))
2716  {
2717  PageSetLSN(metapg, recptr);
2718  }
2719  page = BufferGetPage(rbuf);
2720  PageSetLSN(page, recptr);
2721  page = BufferGetPage(buf);
2722  PageSetLSN(page, recptr);
2723  if (BufferIsValid(lbuf))
2724  {
2725  page = BufferGetPage(lbuf);
2726  PageSetLSN(page, recptr);
2727  }
2728  if (target != leafblkno)
2729  {
2730  page = BufferGetPage(leafbuf);
2731  PageSetLSN(page, recptr);
2732  }
2733  }
2734 
2735  END_CRIT_SECTION();
2736 
2737  /* release metapage */
2738  if (BufferIsValid(metabuf))
2739  _bt_relbuf(rel, metabuf);
2740 
2741  /* release siblings */
2742  if (BufferIsValid(lbuf))
2743  _bt_relbuf(rel, lbuf);
2744  _bt_relbuf(rel, rbuf);
2745 
2746  /* If the target is not leafbuf, we're done with it now -- release it */
2747  if (target != leafblkno)
2748  _bt_relbuf(rel, buf);
2749 
2750  /*
2751  * Maintain pages_newly_deleted, which is simply the number of pages
2752  * deleted by the ongoing VACUUM operation.
2753  *
2754  * Maintain pages_deleted in a way that takes into account how
2755  * btvacuumpage() will count deleted pages that have yet to become
2756  * scanblkno -- only count page when it's not going to get that treatment
2757  * later on.
2758  */
2759  stats->pages_newly_deleted++;
2760  if (target <= scanblkno)
2761  stats->pages_deleted++;
2762 
2763  /*
2764  * Remember information about the target page (now a newly deleted page)
2765  * in dedicated vstate space for later. The page will be considered as a
2766  * candidate to place in the FSM at the end of the current btvacuumscan()
2767  * call.
2768  */
2769  _bt_pendingfsm_add(vstate, target, safexid);
2770 
2771  /* Success - hold on to lock on leafbuf (might also have been target) */
2772  return true;
2773 }
2774 
2775 /*
2776  * Establish how tall the to-be-deleted subtree will be during the first stage
2777  * of page deletion.
2778  *
2779  * Caller's child argument is the block number of the page caller wants to
2780  * delete (this is leafbuf's block number, except when we're called
2781  * recursively). stack is a search stack leading to it. Note that we will
2782  * update the stack entry(s) to reflect current downlink positions --- this is
2783  * similar to the corresponding point in page split handling.
2784  *
2785  * If "first stage" caller cannot go ahead with deleting _any_ pages, returns
2786  * false. Returns true on success, in which case caller can use certain
2787  * details established here to perform the first stage of deletion. This
2788  * function is the last point at which page deletion may be deemed unsafe
2789  * (barring index corruption, or unexpected concurrent page deletions).
2790  *
2791  * We write lock the parent of the root of the to-be-deleted subtree for
2792  * caller on success (i.e. we leave our lock on the *subtreeparent buffer for
2793  * caller). Caller will have to remove a downlink from *subtreeparent. We
2794  * also set a *subtreeparent offset number in *poffset, to indicate the
2795  * location of the pivot tuple that contains the relevant downlink.
2796  *
2797  * The root of the to-be-deleted subtree is called the "top parent". Note
2798  * that the leafbuf page is often the final "top parent" page (you can think
2799  * of the leafbuf page as a degenerate single page subtree when that happens).
2800  * Caller should initialize *topparent to the target leafbuf page block number
2801  * (while *topparentrightsib should be set to leafbuf's right sibling block
2802  * number). We will update *topparent (and *topparentrightsib) for caller
2803  * here, though only when it turns out that caller will delete at least one
2804  * internal page (i.e. only when caller needs to store a valid link to the top
2805  * parent block in the leafbuf page using BTreeTupleSetTopParent()).
2806  */
2807 static bool
2809  BTStack stack, Buffer *subtreeparent,
2810  OffsetNumber *poffset, BlockNumber *topparent,
2811  BlockNumber *topparentrightsib)
2812 {
2813  BlockNumber parent,
2814  leftsibparent;
2815  OffsetNumber parentoffset,
2816  maxoff;
2817  Buffer pbuf;
2818  Page page;
2819  BTPageOpaque opaque;
2820 
2821  /*
2822  * Locate the pivot tuple whose downlink points to "child". Write lock
2823  * the parent page itself.
2824  */
2825  pbuf = _bt_getstackbuf(rel, heaprel, stack, child);
2826  if (pbuf == InvalidBuffer)
2827  {
2828  /*
2829  * Failed to "re-find" a pivot tuple whose downlink matched our child
2830  * block number on the parent level -- the index must be corrupt.
2831  * Don't even try to delete the leafbuf subtree. Just report the
2832  * issue and press on with vacuuming the index.
2833  *
2834  * Note: _bt_getstackbuf() recovers from concurrent page splits that
2835  * take place on the parent level. Its approach is a near-exhaustive
2836  * linear search. This also gives it a surprisingly good chance of
2837  * recovering in the event of a buggy or inconsistent opclass. But we
2838  * don't rely on that here.
2839  */
2840  ereport(LOG,
2841  (errcode(ERRCODE_INDEX_CORRUPTED),
2842  errmsg_internal("failed to re-find parent key in index \"%s\" for deletion target page %u",
2843  RelationGetRelationName(rel), child)));
2844  Assert(false);
2845  return false;
2846  }
2847 
2848  parent = stack->bts_blkno;
2849  parentoffset = stack->bts_offset;
2850 
2851  page = BufferGetPage(pbuf);
2852  opaque = BTPageGetOpaque(page);
2853  maxoff = PageGetMaxOffsetNumber(page);
2854  leftsibparent = opaque->btpo_prev;
2855 
2856  /*
2857  * _bt_getstackbuf() completes page splits on returned parent buffer when
2858  * required.
2859  *
2860  * In general it's a bad idea for VACUUM to use up more disk space, which
2861  * is why page deletion does not finish incomplete page splits most of the
2862  * time. We allow this limited exception because the risk is much lower,
2863  * and the potential downside of not proceeding is much higher: A single
2864  * internal page with the INCOMPLETE_SPLIT flag set might otherwise
2865  * prevent us from deleting hundreds of empty leaf pages from one level
2866  * down.
2867  */
2868  Assert(!P_INCOMPLETE_SPLIT(opaque));
2869 
2870  if (parentoffset < maxoff)
2871  {
2872  /*
2873  * Child is not the rightmost child in parent, so it's safe to delete
2874  * the subtree whose root/topparent is child page
2875  */
2876  *subtreeparent = pbuf;
2877  *poffset = parentoffset;
2878  return true;
2879  }
2880 
2881  /*
2882  * Child is the rightmost child of parent.
2883  *
2884  * Since it's the rightmost child of parent, deleting the child (or
2885  * deleting the subtree whose root/topparent is the child page) is only
2886  * safe when it's also possible to delete the parent.
2887  */
2888  Assert(parentoffset == maxoff);
2889  if (parentoffset != P_FIRSTDATAKEY(opaque) || P_RIGHTMOST(opaque))
2890  {
2891  /*
2892  * Child isn't parent's only child, or parent is rightmost on its
2893  * entire level. Definitely cannot delete any pages.
2894  */
2895  _bt_relbuf(rel, pbuf);
2896  return false;
2897  }
2898 
2899  /*
2900  * Now make sure that the parent deletion is itself safe by examining the
2901  * child's grandparent page. Recurse, passing the parent page as the
2902  * child page (child's grandparent is the parent on the next level up). If
2903  * parent deletion is unsafe, then child deletion must also be unsafe (in
2904  * which case caller cannot delete any pages at all).
2905  */
2906  *topparent = parent;
2907  *topparentrightsib = opaque->btpo_next;
2908 
2909  /*
2910  * Release lock on parent before recursing.
2911  *
2912  * It's OK to release page locks on parent before recursive call locks
2913  * grandparent. An internal page can only acquire an entry if the child
2914  * is split, but that cannot happen as long as we still hold a lock on the
2915  * leafbuf page.
2916  */
2917  _bt_relbuf(rel, pbuf);
2918 
2919  /*
2920  * Before recursing, check that the left sibling of parent (if any) is not
2921  * marked with INCOMPLETE_SPLIT flag first (must do so after we drop the
2922  * parent lock).
2923  *
2924  * Note: We deliberately avoid completing incomplete splits here.
2925  */
2926  if (_bt_leftsib_splitflag(rel, leftsibparent, parent))
2927  return false;
2928 
2929  /* Recurse to examine child page's grandparent page */
2930  return _bt_lock_subtree_parent(rel, heaprel, parent, stack->bts_parent,
2931  subtreeparent, poffset,
2932  topparent, topparentrightsib);
2933 }
2934 
2935 /*
2936  * Initialize local memory state used by VACUUM for _bt_pendingfsm_finalize
2937  * optimization.
2938  *
2939  * Called at the start of a btvacuumscan(). Caller's cleanuponly argument
2940  * indicates if ongoing VACUUM has not (and will not) call btbulkdelete().
2941  *
2942  * We expect to allocate memory inside VACUUM's top-level memory context here.
2943  * The working buffer is subject to a limit based on work_mem. Our strategy
2944  * when the array can no longer grow within the bounds of that limit is to
2945  * stop saving additional newly deleted pages, while proceeding as usual with
2946  * the pages that we can fit.
2947  */
2948 void
2949 _bt_pendingfsm_init(Relation rel, BTVacState *vstate, bool cleanuponly)
2950 {
2951  int64 maxbufsize;
2952 
2953  /*
2954  * Don't bother with optimization in cleanup-only case -- we don't expect
2955  * any newly deleted pages. Besides, cleanup-only calls to btvacuumscan()
2956  * can only take place because this optimization didn't work out during
2957  * the last VACUUM.
2958  */
2959  if (cleanuponly)
2960  return;
2961 
2962  /*
2963  * Cap maximum size of array so that we always respect work_mem. Avoid
2964  * int overflow here.
2965  */
2966  vstate->bufsize = 256;
2967  maxbufsize = (work_mem * 1024L) / sizeof(BTPendingFSM);
2968  maxbufsize = Min(maxbufsize, INT_MAX);
2969  maxbufsize = Min(maxbufsize, MaxAllocSize / sizeof(BTPendingFSM));
2970  /* Stay sane with small work_mem */
2971  maxbufsize = Max(maxbufsize, vstate->bufsize);
2972  vstate->maxbufsize = maxbufsize;
2973 
2974  /* Allocate buffer, indicate that there are currently 0 pending pages */
2975  vstate->pendingpages = palloc(sizeof(BTPendingFSM) * vstate->bufsize);
2976  vstate->npendingpages = 0;
2977 }
2978 
2979 /*
2980  * Place any newly deleted pages (i.e. pages that _bt_pagedel() deleted during
2981  * the ongoing VACUUM operation) into the free space map -- though only when
2982  * it is actually safe to do so by now.
2983  *
2984  * Called at the end of a btvacuumscan(), just before free space map vacuuming
2985  * takes place.
2986  *
2987  * Frees memory allocated by _bt_pendingfsm_init(), if any.
2988  */
2989 void
2991 {
2992  IndexBulkDeleteResult *stats = vstate->stats;
2993  Relation heaprel = vstate->info->heaprel;
2994 
2995  Assert(stats->pages_newly_deleted >= vstate->npendingpages);
2996  Assert(heaprel != NULL);
2997 
2998  if (vstate->npendingpages == 0)
2999  {
3000  /* Just free memory when nothing to do */
3001  if (vstate->pendingpages)
3002  pfree(vstate->pendingpages);
3003 
3004  return;
3005  }
3006 
3007 #ifdef DEBUG_BTREE_PENDING_FSM
3008 
3009  /*
3010  * Debugging aid: Sleep for 5 seconds to greatly increase the chances of
3011  * placing pending pages in the FSM. Note that the optimization will
3012  * never be effective without some other backend concurrently consuming an
3013  * XID.
3014  */
3015  pg_usleep(5000000L);
3016 #endif
3017 
3018  /*
3019  * Recompute VACUUM XID boundaries.
3020  *
3021  * We don't actually care about the oldest non-removable XID. Computing
3022  * the oldest such XID has a useful side-effect that we rely on: it
3023  * forcibly updates the XID horizon state for this backend. This step is
3024  * essential; GlobalVisCheckRemovableFullXid() will not reliably recognize
3025  * that it is now safe to recycle newly deleted pages without this step.
3026  */
3028 
3029  for (int i = 0; i < vstate->npendingpages; i++)
3030  {
3031  BlockNumber target = vstate->pendingpages[i].target;
3032  FullTransactionId safexid = vstate->pendingpages[i].safexid;
3033 
3034  /*
3035  * Do the equivalent of checking BTPageIsRecyclable(), but without
3036  * accessing the page again a second time.
3037  *
3038  * Give up on finding the first non-recyclable page -- all later pages
3039  * must be non-recyclable too, since _bt_pendingfsm_add() adds pages
3040  * to the array in safexid order.
3041  */
3042  if (!GlobalVisCheckRemovableFullXid(heaprel, safexid))
3043  break;
3044 
3045  RecordFreeIndexPage(rel, target);
3046  stats->pages_free++;
3047  }
3048 
3049  pfree(vstate->pendingpages);
3050 }
3051 
3052 /*
3053  * Maintain array of pages that were deleted during current btvacuumscan()
3054  * call, for use in _bt_pendingfsm_finalize()
3055  */
3056 static void
3058  BlockNumber target,
3059  FullTransactionId safexid)
3060 {
3061  Assert(vstate->npendingpages <= vstate->bufsize);
3062  Assert(vstate->bufsize <= vstate->maxbufsize);
3063 
3064 #ifdef USE_ASSERT_CHECKING
3065 
3066  /*
3067  * Verify an assumption made by _bt_pendingfsm_finalize(): pages from the
3068  * array will always be in safexid order (since that is the order that we
3069  * save them in here)
3070  */
3071  if (vstate->npendingpages > 0)
3072  {
3073  FullTransactionId lastsafexid =
3074  vstate->pendingpages[vstate->npendingpages - 1].safexid;
3075 
3076  Assert(FullTransactionIdFollowsOrEquals(safexid, lastsafexid));
3077  }
3078 #endif
3079 
3080  /*
3081  * If temp buffer reaches maxbufsize/work_mem capacity then we discard
3082  * information about this page.
3083  *
3084  * Note that this also covers the case where we opted to not use the
3085  * optimization in _bt_pendingfsm_init().
3086  */
3087  if (vstate->npendingpages == vstate->maxbufsize)
3088  return;
3089 
3090  /* Consider enlarging buffer */
3091  if (vstate->npendingpages == vstate->bufsize)
3092  {
3093  int newbufsize = vstate->bufsize * 2;
3094 
3095  /* Respect work_mem */
3096  if (newbufsize > vstate->maxbufsize)
3097  newbufsize = vstate->maxbufsize;
3098 
3099  vstate->bufsize = newbufsize;
3100  vstate->pendingpages =
3101  repalloc(vstate->pendingpages,
3102  sizeof(BTPendingFSM) * vstate->bufsize);
3103  }
3104 
3105  /* Save metadata for newly deleted page */
3106  vstate->pendingpages[vstate->npendingpages].target = target;
3107  vstate->pendingpages[vstate->npendingpages].safexid = safexid;
3108  vstate->npendingpages++;
3109 }
uint32 BlockNumber
Definition: block.h:31
#define InvalidBlockNumber
Definition: block.h:33
static bool BlockNumberIsValid(BlockNumber blockNumber)
Definition: block.h:71
int Buffer
Definition: buf.h:23
#define InvalidBuffer
Definition: buf.h:25
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:3386
Buffer ReleaseAndReadBuffer(Buffer buffer, Relation relation, BlockNumber blockNum)
Definition: bufmgr.c:2261
Buffer ExtendBufferedRel(BufferManagerRelation bmr, ForkNumber forkNum, BufferAccessStrategy strategy, uint32 flags)
Definition: bufmgr.c:839
bool ConditionalLockBuffer(Buffer buffer)
Definition: bufmgr.c:4834
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4573
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:2198
void LockBufferForCleanup(Buffer buffer)
Definition: bufmgr.c:4888
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4808
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:735
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:157
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:229
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:350
static Size BufferGetPageSize(Buffer buffer)
Definition: bufmgr.h:339
@ EB_LOCK_FIRST
Definition: bufmgr.h:85
#define BMR_REL(p_rel)
Definition: bufmgr.h:106
static bool BufferIsValid(Buffer bufnum)
Definition: bufmgr.h:301
void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
Definition: bufpage.c:1161
bool PageIndexTupleOverwrite(Page page, OffsetNumber offnum, Item newtup, Size newsize)
Definition: bufpage.c:1405
void PageIndexTupleDelete(Page page, OffsetNumber offnum)
Definition: bufpage.c:1052
void PageInit(Page page, Size pageSize, Size specialSize)
Definition: bufpage.c:42
PageHeaderData * PageHeader
Definition: bufpage.h:170
Pointer Page
Definition: bufpage.h:78
static Item PageGetItem(Page page, ItemId itemId)
Definition: bufpage.h:351
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:240
static bool PageIsNew(Page page)
Definition: bufpage.h:230
static void PageSetLSN(Page page, XLogRecPtr lsn)
Definition: bufpage.h:388
static OffsetNumber PageGetMaxOffsetNumber(Page page)
Definition: bufpage.h:369
static uint16 PageGetSpecialSize(Page page)
Definition: bufpage.h:313
unsigned short uint16
Definition: c.h:494
unsigned int uint32
Definition: c.h:495
#define Min(x, y)
Definition: c.h:993
#define MAXALIGN(LEN)
Definition: c.h:800
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:171
#define Max(x, y)
Definition: c.h:987
unsigned char uint8
Definition: c.h:493
#define MemSet(start, val, len)
Definition: c.h:1009
uint32 TransactionId
Definition: c.h:641
size_t Size
Definition: c.h:594
int errmsg_internal(const char *fmt,...)
Definition: elog.c:1156
int errhint(const char *fmt,...)
Definition: elog.c:1316
int errcode(int sqlerrcode)
Definition: elog.c:858
int errmsg(const char *fmt,...)
Definition: elog.c:1069
#define LOG
Definition: elog.h:31
#define DEBUG2
Definition: elog.h:29
#define PANIC
Definition: elog.h:42
#define DEBUG1
Definition: elog.h:30
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
int work_mem
Definition: globals.c:127
BlockNumber GetFreeIndexPage(Relation rel)
Definition: indexfsm.c:38
void RecordFreeIndexPage(Relation rel, BlockNumber freeBlock)
Definition: indexfsm.c:52
IndexTuple CopyIndexTuple(IndexTuple source)
Definition: indextuple.c:547
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int i
Definition: isn.c:73
Pointer Item
Definition: item.h:17
int32 ItemPointerCompare(ItemPointer arg1, ItemPointer arg2)
Definition: itemptr.c:51
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:35
IndexTupleData * IndexTuple
Definition: itup.h:53
#define IndexTupleSize(itup)
Definition: itup.h:70
struct IndexTupleData IndexTupleData
#define MaxIndexTuplesPerPage
Definition: itup.h:165
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1456
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1476
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1021
void * palloc(Size size)
Definition: mcxt.c:1226
#define VALGRIND_MAKE_MEM_DEFINED(addr, size)
Definition: memdebug.h:26
#define VALGRIND_CHECK_MEM_IS_DEFINED(addr, size)
Definition: memdebug.h:23
#define VALGRIND_MAKE_MEM_NOACCESS(addr, size)
Definition: memdebug.h:27
#define MaxAllocSize
Definition: memutils.h:40
#define START_CRIT_SECTION()
Definition: miscadmin.h:148
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:121
#define END_CRIT_SECTION()
Definition: miscadmin.h:150
void _bt_update_posting(BTVacuumPosting vacposting)
Definition: nbtdedup.c:924
Buffer _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack, BlockNumber child)
Definition: nbtinsert.c:2319
Buffer _bt_relandgetbuf(Relation rel, Buffer obuf, BlockNumber blkno, int access)
Definition: nbtpage.c:1003
static bool _bt_lock_subtree_parent(Relation rel, Relation heaprel, BlockNumber child, BTStack stack, Buffer *subtreeparent, OffsetNumber *poffset, BlockNumber *topparent, BlockNumber *topparentrightsib)
Definition: nbtpage.c:2808
void _bt_upgrademetapage(Page page)
Definition: nbtpage.c:107
void _bt_relbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1023
Buffer _bt_gettrueroot(Relation rel)
Definition: nbtpage.c:580
int _bt_getrootheight(Relation rel)
Definition: nbtpage.c:675
void _bt_pageinit(Page page, Size size)
Definition: nbtpage.c:1129
static bool _bt_rightsib_halfdeadflag(Relation rel, BlockNumber leafrightsib)
Definition: nbtpage.c:1757
void _bt_pagedel(Relation rel, Buffer leafbuf, BTVacState *vstate)
Definition: nbtpage.c:1807
Buffer _bt_allocbuf(Relation rel, Relation heaprel)
Definition: nbtpage.c:869
void _bt_delitems_vacuum(Relation rel, Buffer buf, OffsetNumber *deletable, int ndeletable, BTVacuumPosting *updatable, int nupdatable)
Definition: nbtpage.c:1154
static bool _bt_leftsib_splitflag(Relation rel, BlockNumber leftsib, BlockNumber target)
Definition: nbtpage.c:1700
void _bt_checkpage(Relation rel, Buffer buf)
Definition: nbtpage.c:797
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
Definition: nbtpage.c:739
static BTMetaPageData * _bt_getmeta(Relation rel, Buffer metabuf)
Definition: nbtpage.c:142
static void _bt_delitems_delete(Relation rel, Buffer buf, TransactionId snapshotConflictHorizon, bool isCatalogRel, OffsetNumber *deletable, int ndeletable, BTVacuumPosting *updatable, int nupdatable)
Definition: nbtpage.c:1284
void _bt_set_cleanup_info(Relation rel, BlockNumber num_delpages)
Definition: nbtpage.c:232
static bool _bt_mark_page_halfdead(Relation rel, Relation heaprel, Buffer leafbuf, BTStack stack)
Definition: nbtpage.c:2083
bool _bt_conditionallockbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1093
Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access)
Definition: nbtpage.c:845
void _bt_unlockbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1070
void _bt_upgradelockbufcleanup(Relation rel, Buffer buf)
Definition: nbtpage.c:1109
void _bt_initmetapage(Page page, BlockNumber rootbknum, uint32 level, bool allequalimage)
Definition: nbtpage.c:67
void _bt_delitems_delete_check(Relation rel, Buffer buf, Relation heapRel, TM_IndexDeleteOp *delstate)
Definition: nbtpage.c:1518
bool _bt_vacuum_needs_cleanup(Relation rel)
Definition: nbtpage.c:179
static char * _bt_delitems_update(BTVacuumPosting *updatable, int nupdatable, OffsetNumber *updatedoffsets, Size *updatedbuflen, bool needswal)
Definition: nbtpage.c:1405
static int _bt_delitems_cmp(const void *a, const void *b)
Definition: nbtpage.c:1464
void _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate)
Definition: nbtpage.c:2990
void _bt_lockbuf(Relation rel, Buffer buf, int access)
Definition: nbtpage.c:1039
Buffer _bt_getroot(Relation rel, Relation heaprel, int access)
Definition: nbtpage.c:344
void _bt_pendingfsm_init(Relation rel, BTVacState *vstate, bool cleanuponly)
Definition: nbtpage.c:2949
static void _bt_pendingfsm_add(BTVacState *vstate, BlockNumber target, FullTransactionId safexid)
Definition: nbtpage.c:3057
static bool _bt_unlink_halfdead_page(Relation rel, Buffer leafbuf, BlockNumber scanblkno, bool *rightsib_empty, BTVacState *vstate)
Definition: nbtpage.c:2309
#define P_ISHALFDEAD(opaque)
Definition: nbtree.h:224
static uint16 BTreeTupleGetNPosting(IndexTuple posting)
Definition: nbtree.h:518
#define BTPageGetMeta(p)
Definition: nbtree.h:121
#define P_ISLEAF(opaque)
Definition: nbtree.h:220
static FullTransactionId BTPageGetDeleteXid(Page page)
Definition: nbtree.h:260
#define BTREE_MIN_VERSION
Definition: nbtree.h:151
#define BTP_LEAF
Definition: nbtree.h:76
#define BTP_HALF_DEAD
Definition: nbtree.h:80
#define P_HIKEY
Definition: nbtree.h:367
static void BTreeTupleSetTopParent(IndexTuple leafhikey, BlockNumber blkno)
Definition: nbtree.h:626
#define P_ISMETA(opaque)
Definition: nbtree.h:223
#define BTP_HAS_GARBAGE
Definition: nbtree.h:82
#define P_LEFTMOST(opaque)
Definition: nbtree.h:218
#define BTPageGetOpaque(page)
Definition: nbtree.h:73
#define P_ISDELETED(opaque)
Definition: nbtree.h:222
#define BTREE_MAGIC
Definition: nbtree.h:149
#define BTP_META
Definition: nbtree.h:79
#define BTREE_VERSION
Definition: nbtree.h:150
static BlockNumber BTreeTupleGetTopParent(IndexTuple leafhikey)
Definition: nbtree.h:620
#define BTP_ROOT
Definition: nbtree.h:77
static void BTreeTupleSetDownLink(IndexTuple pivot, BlockNumber blkno)
Definition: nbtree.h:562
#define P_FIRSTDATAKEY(opaque)
Definition: nbtree.h:369
#define P_ISROOT(opaque)
Definition: nbtree.h:221
#define P_NONE
Definition: nbtree.h:212
#define P_RIGHTMOST(opaque)
Definition: nbtree.h:219
#define P_INCOMPLETE_SPLIT(opaque)
Definition: nbtree.h:227
#define BTREE_METAPAGE
Definition: nbtree.h:148
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
Definition: nbtree.h:544
#define BT_READ
Definition: nbtree.h:719
static bool BTPageIsRecyclable(Page page, Relation heaprel)
Definition: nbtree.h:291
static BlockNumber BTreeTupleGetDownLink(IndexTuple pivot)
Definition: nbtree.h:556
#define P_IGNORE(opaque)
Definition: nbtree.h:225
static ItemPointer BTreeTupleGetMaxHeapTID(IndexTuple itup)
Definition: nbtree.h:664
static bool BTreeTupleIsPosting(IndexTuple itup)
Definition: nbtree.h:492
static void BTPageSetDeleted(Page page, FullTransactionId safexid)
Definition: nbtree.h:239
#define BTREE_NOVAC_VERSION
Definition: nbtree.h:152
static ItemPointer BTreeTupleGetHeapTID(IndexTuple itup)
Definition: nbtree.h:638
#define BT_WRITE
Definition: nbtree.h:720
BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access)
Definition: nbtsearch.c:96
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
#define SizeOfBtreeVacuum
Definition: nbtxlog.h:234
#define XLOG_BTREE_META_CLEANUP
Definition: nbtxlog.h:41
#define SizeOfBtreeUpdate
Definition: nbtxlog.h:268
#define XLOG_BTREE_VACUUM
Definition: nbtxlog.h:39
#define SizeOfBtreeDelete
Definition: nbtxlog.h:253
#define SizeOfBtreeMarkPageHalfDead
Definition: nbtxlog.h:291
#define XLOG_BTREE_UNLINK_PAGE
Definition: nbtxlog.h:35
#define XLOG_BTREE_UNLINK_PAGE_META
Definition: nbtxlog.h:36
#define SizeOfBtreeNewroot
Definition: nbtxlog.h:347
#define XLOG_BTREE_MARK_PAGE_HALFDEAD
Definition: nbtxlog.h:38
#define XLOG_BTREE_REUSE_PAGE
Definition: nbtxlog.h:40
#define SizeOfBtreeUnlinkPage
Definition: nbtxlog.h:328
#define SizeOfBtreeReusePage
Definition: nbtxlog.h:192
#define XLOG_BTREE_NEWROOT
Definition: nbtxlog.h:37
#define XLOG_BTREE_DELETE
Definition: nbtxlog.h:34
#define InvalidOffsetNumber
Definition: off.h:26
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:39
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
uint16 OffsetNumber
Definition: off.h:24
static char * buf
Definition: pg_test_fsync.c:73
#define qsort(a, b, c, d)
Definition: port.h:445
void PredicateLockPageCombine(Relation relation, BlockNumber oldblkno, BlockNumber newblkno)
Definition: predicate.c:3180
short access
Definition: preproc-type.c:36
TransactionId GetOldestNonRemovableTransactionId(Relation rel)
Definition: procarray.c:1986
bool GlobalVisCheckRemovableFullXid(Relation rel, FullTransactionId fxid)
Definition: procarray.c:4219
#define RelationGetRelationName(relation)
Definition: rel.h:538
#define RelationIsAccessibleInLogicalDecoding(relation)
Definition: rel.h:685
#define RelationNeedsWAL(relation)
Definition: rel.h:629
#define RelationUsesLocalBuffers(relation)
Definition: rel.h:638
@ MAIN_FORKNUM
Definition: relpath.h:50
void pg_usleep(long microsec)
Definition: signal.c:53
uint32 btm_last_cleanup_num_delpages
Definition: nbtree.h:114
uint32 btm_level
Definition: nbtree.h:108
float8 btm_last_cleanup_num_heap_tuples
Definition: nbtree.h:116
BlockNumber btm_fastroot
Definition: nbtree.h:109
uint32 btm_version
Definition: nbtree.h:106
uint32 btm_magic
Definition: nbtree.h:105
BlockNumber btm_root
Definition: nbtree.h:107
bool btm_allequalimage
Definition: nbtree.h:118
uint32 btm_fastlevel
Definition: nbtree.h:110
BlockNumber btpo_next
Definition: nbtree.h:65
BlockNumber btpo_prev
Definition: nbtree.h:64
uint16 btpo_flags
Definition: nbtree.h:67
uint32 btpo_level
Definition: nbtree.h:66
BTCycleId btpo_cycleid
Definition: nbtree.h:68
FullTransactionId safexid
Definition: nbtree.h:327
BlockNumber target
Definition: nbtree.h:326
bool pivotsearch
Definition: nbtree.h:795
BlockNumber bts_blkno
Definition: nbtree.h:734
struct BTStackData * bts_parent
Definition: nbtree.h:736
OffsetNumber bts_offset
Definition: nbtree.h:735
IndexBulkDeleteResult * stats
Definition: nbtree.h:333
BTPendingFSM * pendingpages
Definition: nbtree.h:344
int npendingpages
Definition: nbtree.h:345
IndexVacuumInfo * info
Definition: nbtree.h:332
int bufsize
Definition: nbtree.h:342
int maxbufsize
Definition: nbtree.h:343
uint16 deletetids[FLEXIBLE_ARRAY_MEMBER]
Definition: nbtree.h:916
uint16 ndeletedtids
Definition: nbtree.h:915
IndexTuple itup
Definition: nbtree.h:911
OffsetNumber updatedoffset
Definition: nbtree.h:912
BlockNumber pages_deleted
Definition: genam.h:82
BlockNumber pages_newly_deleted
Definition: genam.h:81
BlockNumber pages_free
Definition: genam.h:83
ItemPointerData t_tid
Definition: itup.h:37
unsigned short t_info
Definition: itup.h:49
Relation heaprel
Definition: genam.h:47
void * rd_amcache
Definition: rel.h:228
MemoryContext rd_indexcxt
Definition: rel.h:203
RelFileLocator rd_locator
Definition: rel.h:57
TM_IndexStatus * status
Definition: tableam.h:247
TM_IndexDelete * deltids
Definition: tableam.h:246
ItemPointerData tid
Definition: tableam.h:205
bool knowndeletable
Definition: tableam.h:212
OffsetNumber idxoffnum
Definition: tableam.h:211
TransactionId snapshotConflictHorizon
Definition: nbtxlog.h:238
bool isCatalogRel
Definition: nbtxlog.h:241
uint16 ndeleted
Definition: nbtxlog.h:239
uint16 nupdated
Definition: nbtxlog.h:240
uint32 level
Definition: nbtxlog.h:50
uint32 version
Definition: nbtxlog.h:48
bool allequalimage
Definition: nbtxlog.h:54
BlockNumber fastroot
Definition: nbtxlog.h:51
uint32 fastlevel
Definition: nbtxlog.h:52
BlockNumber root
Definition: nbtxlog.h:49
uint32 last_cleanup_num_delpages
Definition: nbtxlog.h:53
uint32 level
Definition: nbtxlog.h:344
BlockNumber rootblk
Definition: nbtxlog.h:343
FullTransactionId snapshotConflictHorizon
Definition: nbtxlog.h:187
RelFileLocator locator
Definition: nbtxlog.h:185
BlockNumber block
Definition: nbtxlog.h:186
uint16 ndeletedtids
Definition: nbtxlog.h:263
uint16 ndeleted
Definition: nbtxlog.h:222
uint16 nupdated
Definition: nbtxlog.h:223
static TransactionId table_index_delete_tuples(Relation rel, TM_IndexDeleteOp *delstate)
Definition: tableam.h:1351
#define InvalidTransactionId
Definition: transam.h:31
#define FullTransactionIdFollowsOrEquals(a, b)
Definition: transam.h:54
FullTransactionId ReadNextFullTransactionId(void)
Definition: varsup.c:261
#define XLogStandbyInfoActive()
Definition: xlog.h:121
uint64 XLogRecPtr
Definition: xlogdefs.h:21
void XLogRegisterData(char *data, uint32 len)
Definition: xloginsert.c:365
XLogRecPtr XLogInsert(RmgrId rmid, uint8 info)
Definition: xloginsert.c:475
void XLogRegisterBufData(uint8 block_id, char *data, uint32 len)
Definition: xloginsert.c:406
void XLogRegisterBuffer(uint8 block_id, Buffer buffer, uint8 flags)
Definition: xloginsert.c:243
void XLogBeginInsert(void)
Definition: xloginsert.c:150
#define REGBUF_STANDARD
Definition: xloginsert.h:34
#define REGBUF_WILL_INIT
Definition: xloginsert.h:33