PostgreSQL Source Code  git master
freespace.c File Reference
#include "postgres.h"
#include "access/htup_details.h"
#include "access/xloginsert.h"
#include "access/xlogutils.h"
#include "miscadmin.h"
#include "storage/freespace.h"
#include "storage/fsm_internals.h"
#include "storage/smgr.h"
#include "utils/rel.h"
Include dependency graph for freespace.c:

Go to the source code of this file.

Data Structures

struct  FSMAddress
 

Macros

#define FSM_CATEGORIES   256
 
#define FSM_CAT_STEP   (BLCKSZ / FSM_CATEGORIES)
 
#define MaxFSMRequestSize   MaxHeapTupleSize
 
#define FSM_TREE_DEPTH   ((SlotsPerFSMPage >= 1626) ? 3 : 4)
 
#define FSM_ROOT_LEVEL   (FSM_TREE_DEPTH - 1)
 
#define FSM_BOTTOM_LEVEL   0
 

Functions

static FSMAddress fsm_get_child (FSMAddress parent, uint16 slot)
 
static FSMAddress fsm_get_parent (FSMAddress child, uint16 *slot)
 
static FSMAddress fsm_get_location (BlockNumber heapblk, uint16 *slot)
 
static BlockNumber fsm_get_heap_blk (FSMAddress addr, uint16 slot)
 
static BlockNumber fsm_logical_to_physical (FSMAddress addr)
 
static Buffer fsm_readbuf (Relation rel, FSMAddress addr, bool extend)
 
static Buffer fsm_extend (Relation rel, BlockNumber fsm_nblocks)
 
static uint8 fsm_space_avail_to_cat (Size avail)
 
static uint8 fsm_space_needed_to_cat (Size needed)
 
static Size fsm_space_cat_to_avail (uint8 cat)
 
static int fsm_set_and_search (Relation rel, FSMAddress addr, uint16 slot, uint8 newValue, uint8 minValue)
 
static BlockNumber fsm_search (Relation rel, uint8 min_cat)
 
static uint8 fsm_vacuum_page (Relation rel, FSMAddress addr, BlockNumber start, BlockNumber end, bool *eof_p)
 
static bool fsm_does_block_exist (Relation rel, BlockNumber blknumber)
 
BlockNumber GetPageWithFreeSpace (Relation rel, Size spaceNeeded)
 
BlockNumber RecordAndGetPageWithFreeSpace (Relation rel, BlockNumber oldPage, Size oldSpaceAvail, Size spaceNeeded)
 
void RecordPageWithFreeSpace (Relation rel, BlockNumber heapBlk, Size spaceAvail)
 
void XLogRecordPageWithFreeSpace (RelFileLocator rlocator, BlockNumber heapBlk, Size spaceAvail)
 
Size GetRecordedFreeSpace (Relation rel, BlockNumber heapBlk)
 
BlockNumber FreeSpaceMapPrepareTruncateRel (Relation rel, BlockNumber nblocks)
 
void FreeSpaceMapVacuum (Relation rel)
 
void FreeSpaceMapVacuumRange (Relation rel, BlockNumber start, BlockNumber end)
 

Variables

static const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0}
 

Macro Definition Documentation

◆ FSM_BOTTOM_LEVEL

#define FSM_BOTTOM_LEVEL   0

Definition at line 78 of file freespace.c.

◆ FSM_CAT_STEP

#define FSM_CAT_STEP   (BLCKSZ / FSM_CATEGORIES)

Definition at line 65 of file freespace.c.

◆ FSM_CATEGORIES

#define FSM_CATEGORIES   256

Definition at line 64 of file freespace.c.

◆ FSM_ROOT_LEVEL

#define FSM_ROOT_LEVEL   (FSM_TREE_DEPTH - 1)

Definition at line 77 of file freespace.c.

◆ FSM_TREE_DEPTH

#define FSM_TREE_DEPTH   ((SlotsPerFSMPage >= 1626) ? 3 : 4)

Definition at line 75 of file freespace.c.

◆ MaxFSMRequestSize

#define MaxFSMRequestSize   MaxHeapTupleSize

Definition at line 66 of file freespace.c.

Function Documentation

◆ FreeSpaceMapPrepareTruncateRel()

BlockNumber FreeSpaceMapPrepareTruncateRel ( Relation  rel,
BlockNumber  nblocks 
)

Definition at line 275 of file freespace.c.

276 {
277  BlockNumber new_nfsmblocks;
278  FSMAddress first_removed_address;
279  uint16 first_removed_slot;
280  Buffer buf;
281 
282  /*
283  * If no FSM has been created yet for this relation, there's nothing to
284  * truncate.
285  */
287  return InvalidBlockNumber;
288 
289  /* Get the location in the FSM of the first removed heap block */
290  first_removed_address = fsm_get_location(nblocks, &first_removed_slot);
291 
292  /*
293  * Zero out the tail of the last remaining FSM page. If the slot
294  * representing the first removed heap block is at a page boundary, as the
295  * first slot on the FSM page that first_removed_address points to, we can
296  * just truncate that page altogether.
297  */
298  if (first_removed_slot > 0)
299  {
300  buf = fsm_readbuf(rel, first_removed_address, false);
301  if (!BufferIsValid(buf))
302  return InvalidBlockNumber; /* nothing to do; the FSM was already
303  * smaller */
305 
306  /* NO EREPORT(ERROR) from here till changes are logged */
308 
309  fsm_truncate_avail(BufferGetPage(buf), first_removed_slot);
310 
311  /*
312  * This change is non-critical, because fsm_does_block_exist() would
313  * stop us from returning a truncated-away block. However, since this
314  * may remove up to SlotsPerFSMPage slots, it's nice to avoid the cost
315  * of that many fsm_does_block_exist() rejections. Use a full
316  * MarkBufferDirty(), not MarkBufferDirtyHint().
317  */
319 
320  /*
321  * WAL-log like MarkBufferDirtyHint() might have done, just to avoid
322  * differing from the rest of the file in this respect. This is
323  * optional; see README mention of full page images. XXX consider
324  * XLogSaveBufferForHint() for even closer similarity.
325  *
326  * A higher-level operation calls us at WAL replay. If we crash
327  * before the XLOG_SMGR_TRUNCATE flushes to disk, main fork length has
328  * not changed, and our fork remains valid. If we crash after that
329  * flush, redo will return here.
330  */
332  log_newpage_buffer(buf, false);
333 
335 
337 
338  new_nfsmblocks = fsm_logical_to_physical(first_removed_address) + 1;
339  }
340  else
341  {
342  new_nfsmblocks = fsm_logical_to_physical(first_removed_address);
343  if (smgrnblocks(RelationGetSmgr(rel), FSM_FORKNUM) <= new_nfsmblocks)
344  return InvalidBlockNumber; /* nothing to do; the FSM was already
345  * smaller */
346  }
347 
348  return new_nfsmblocks;
349 }
uint32 BlockNumber
Definition: block.h:31
#define InvalidBlockNumber
Definition: block.h:33
int Buffer
Definition: buf.h:23
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4913
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:2520
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:5131
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:404
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:195
static bool BufferIsValid(Buffer bufnum)
Definition: bufmgr.h:355
unsigned short uint16
Definition: c.h:505
static BlockNumber fsm_logical_to_physical(FSMAddress addr)
Definition: freespace.c:455
static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot)
Definition: freespace.c:491
static Buffer fsm_readbuf(Relation rel, FSMAddress addr, bool extend)
Definition: freespace.c:554
bool fsm_truncate_avail(Page page, int nslots)
Definition: fsmpage.c:313
#define START_CRIT_SECTION()
Definition: miscadmin.h:149
#define END_CRIT_SECTION()
Definition: miscadmin.h:151
static char * buf
Definition: pg_test_fsync.c:73
static SMgrRelation RelationGetSmgr(Relation rel)
Definition: rel.h:567
#define RelationNeedsWAL(relation)
Definition: rel.h:628
@ FSM_FORKNUM
Definition: relpath.h:51
BlockNumber smgrnblocks(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:655
bool smgrexists(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:398
#define XLogHintBitIsNeeded()
Definition: xlog.h:118
XLogRecPtr log_newpage_buffer(Buffer buffer, bool page_std)
Definition: xloginsert.c:1237
bool InRecovery
Definition: xlogutils.c:50

References buf, BUFFER_LOCK_EXCLUSIVE, BufferGetPage(), BufferIsValid(), END_CRIT_SECTION, FSM_FORKNUM, fsm_get_location(), fsm_logical_to_physical(), fsm_readbuf(), fsm_truncate_avail(), InRecovery, InvalidBlockNumber, LockBuffer(), log_newpage_buffer(), MarkBufferDirty(), RelationGetSmgr(), RelationNeedsWAL, smgrexists(), smgrnblocks(), START_CRIT_SECTION, UnlockReleaseBuffer(), and XLogHintBitIsNeeded.

Referenced by RelationTruncate(), and smgr_redo().

◆ FreeSpaceMapVacuum()

void FreeSpaceMapVacuum ( Relation  rel)

Definition at line 358 of file freespace.c.

359 {
360  bool dummy;
361 
362  /* Recursively scan the tree, starting at the root */
363  (void) fsm_vacuum_page(rel, FSM_ROOT_ADDRESS,
365  &dummy);
366 }
static uint8 fsm_vacuum_page(Relation rel, FSMAddress addr, BlockNumber start, BlockNumber end, bool *eof_p)
Definition: freespace.c:812
static const FSMAddress FSM_ROOT_ADDRESS
Definition: freespace.c:91

References FSM_ROOT_ADDRESS, fsm_vacuum_page(), and InvalidBlockNumber.

Referenced by brin_vacuum_scan(), and IndexFreeSpaceMapVacuum().

◆ FreeSpaceMapVacuumRange()

void FreeSpaceMapVacuumRange ( Relation  rel,
BlockNumber  start,
BlockNumber  end 
)

Definition at line 377 of file freespace.c.

378 {
379  bool dummy;
380 
381  /* Recursively scan the tree, starting at the root */
382  if (end > start)
383  (void) fsm_vacuum_page(rel, FSM_ROOT_ADDRESS, start, end, &dummy);
384 }
return str start

References FSM_ROOT_ADDRESS, fsm_vacuum_page(), and start.

Referenced by brin_doinsert(), brin_doupdate(), brin_getinsertbuffer(), lazy_scan_heap(), RelationAddBlocks(), RelationTruncate(), smgr_redo(), and terminate_brin_buildstate().

◆ fsm_does_block_exist()

static bool fsm_does_block_exist ( Relation  rel,
BlockNumber  blknumber 
)
static

Definition at line 926 of file freespace.c.

927 {
928  SMgrRelation smgr = RelationGetSmgr(rel);
929 
930  /*
931  * If below the cached nblocks, the block surely exists. Otherwise, we
932  * face a trade-off. We opt to compare to a fresh nblocks, incurring
933  * lseek() overhead. The alternative would be to assume the block does
934  * not exist, but that would cause FSM to set zero space available for
935  * blocks that main fork extension just recorded.
936  */
938  blknumber < smgr->smgr_cached_nblocks[MAIN_FORKNUM]) ||
939  blknumber < RelationGetNumberOfBlocks(rel));
940 }
static bool BlockNumberIsValid(BlockNumber blockNumber)
Definition: block.h:71
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:277
@ MAIN_FORKNUM
Definition: relpath.h:50
BlockNumber smgr_cached_nblocks[MAX_FORKNUM+1]
Definition: smgr.h:46

References BlockNumberIsValid(), MAIN_FORKNUM, RelationGetNumberOfBlocks, RelationGetSmgr(), and SMgrRelationData::smgr_cached_nblocks.

Referenced by fsm_search(), and RecordAndGetPageWithFreeSpace().

◆ fsm_extend()

static Buffer fsm_extend ( Relation  rel,
BlockNumber  fsm_nblocks 
)
static

Definition at line 629 of file freespace.c.

630 {
631  return ExtendBufferedRelTo(BMR_REL(rel), FSM_FORKNUM, NULL,
634  fsm_nblocks,
636 }
Buffer ExtendBufferedRelTo(BufferManagerRelation bmr, ForkNumber fork, BufferAccessStrategy strategy, uint32 flags, BlockNumber extend_to, ReadBufferMode mode)
Definition: bufmgr.c:909
@ EB_CLEAR_SIZE_CACHE
Definition: bufmgr.h:89
@ EB_CREATE_FORK_IF_NEEDED
Definition: bufmgr.h:83
@ RBM_ZERO_ON_ERROR
Definition: bufmgr.h:50
#define BMR_REL(p_rel)
Definition: bufmgr.h:107

References BMR_REL, EB_CLEAR_SIZE_CACHE, EB_CREATE_FORK_IF_NEEDED, ExtendBufferedRelTo(), FSM_FORKNUM, and RBM_ZERO_ON_ERROR.

Referenced by fsm_readbuf().

◆ fsm_get_child()

static FSMAddress fsm_get_child ( FSMAddress  parent,
uint16  slot 
)
static

Definition at line 535 of file freespace.c.

536 {
537  FSMAddress child;
538 
539  Assert(parent.level > FSM_BOTTOM_LEVEL);
540 
541  child.level = parent.level - 1;
542  child.logpageno = parent.logpageno * SlotsPerFSMPage + slot;
543 
544  return child;
545 }
#define Assert(condition)
Definition: c.h:858
#define FSM_BOTTOM_LEVEL
Definition: freespace.c:78
#define SlotsPerFSMPage
Definition: fsm_internals.h:61
int logpageno
Definition: freespace.c:87
int level
Definition: freespace.c:86

References Assert, FSM_BOTTOM_LEVEL, FSMAddress::level, FSMAddress::logpageno, and SlotsPerFSMPage.

Referenced by fsm_search(), and fsm_vacuum_page().

◆ fsm_get_heap_blk()

static BlockNumber fsm_get_heap_blk ( FSMAddress  addr,
uint16  slot 
)
static

Definition at line 506 of file freespace.c.

507 {
508  Assert(addr.level == FSM_BOTTOM_LEVEL);
509  return ((unsigned int) addr.logpageno) * SlotsPerFSMPage + slot;
510 }

References Assert, FSM_BOTTOM_LEVEL, FSMAddress::level, FSMAddress::logpageno, and SlotsPerFSMPage.

Referenced by fsm_search(), and RecordAndGetPageWithFreeSpace().

◆ fsm_get_location()

static FSMAddress fsm_get_location ( BlockNumber  heapblk,
uint16 slot 
)
static

Definition at line 491 of file freespace.c.

492 {
493  FSMAddress addr;
494 
495  addr.level = FSM_BOTTOM_LEVEL;
496  addr.logpageno = heapblk / SlotsPerFSMPage;
497  *slot = heapblk % SlotsPerFSMPage;
498 
499  return addr;
500 }

References FSM_BOTTOM_LEVEL, FSMAddress::level, FSMAddress::logpageno, and SlotsPerFSMPage.

Referenced by FreeSpaceMapPrepareTruncateRel(), fsm_vacuum_page(), GetRecordedFreeSpace(), RecordAndGetPageWithFreeSpace(), RecordPageWithFreeSpace(), and XLogRecordPageWithFreeSpace().

◆ fsm_get_parent()

static FSMAddress fsm_get_parent ( FSMAddress  child,
uint16 slot 
)
static

Definition at line 517 of file freespace.c.

518 {
519  FSMAddress parent;
520 
521  Assert(child.level < FSM_ROOT_LEVEL);
522 
523  parent.level = child.level + 1;
524  parent.logpageno = child.logpageno / SlotsPerFSMPage;
525  *slot = child.logpageno % SlotsPerFSMPage;
526 
527  return parent;
528 }
#define FSM_ROOT_LEVEL
Definition: freespace.c:77

References Assert, FSM_ROOT_LEVEL, FSMAddress::level, FSMAddress::logpageno, and SlotsPerFSMPage.

Referenced by fsm_search(), and fsm_vacuum_page().

◆ fsm_logical_to_physical()

static BlockNumber fsm_logical_to_physical ( FSMAddress  addr)
static

Definition at line 455 of file freespace.c.

456 {
457  BlockNumber pages;
458  int leafno;
459  int l;
460 
461  /*
462  * Calculate the logical page number of the first leaf page below the
463  * given page.
464  */
465  leafno = addr.logpageno;
466  for (l = 0; l < addr.level; l++)
467  leafno *= SlotsPerFSMPage;
468 
469  /* Count upper level nodes required to address the leaf page */
470  pages = 0;
471  for (l = 0; l < FSM_TREE_DEPTH; l++)
472  {
473  pages += leafno + 1;
474  leafno /= SlotsPerFSMPage;
475  }
476 
477  /*
478  * If the page we were asked for wasn't at the bottom level, subtract the
479  * additional lower level pages we counted above.
480  */
481  pages -= addr.level;
482 
483  /* Turn the page count into 0-based block number */
484  return pages - 1;
485 }
#define FSM_TREE_DEPTH
Definition: freespace.c:75

References FSM_TREE_DEPTH, FSMAddress::level, FSMAddress::logpageno, and SlotsPerFSMPage.

Referenced by FreeSpaceMapPrepareTruncateRel(), fsm_readbuf(), and XLogRecordPageWithFreeSpace().

◆ fsm_readbuf()

static Buffer fsm_readbuf ( Relation  rel,
FSMAddress  addr,
bool  extend 
)
static

Definition at line 554 of file freespace.c.

555 {
556  BlockNumber blkno = fsm_logical_to_physical(addr);
557  Buffer buf;
558  SMgrRelation reln = RelationGetSmgr(rel);
559 
560  /*
561  * If we haven't cached the size of the FSM yet, check it first. Also
562  * recheck if the requested block seems to be past end, since our cached
563  * value might be stale. (We send smgr inval messages on truncation, but
564  * not on extension.)
565  */
567  blkno >= reln->smgr_cached_nblocks[FSM_FORKNUM])
568  {
569  /* Invalidate the cache so smgrnblocks asks the kernel. */
571  if (smgrexists(reln, FSM_FORKNUM))
572  smgrnblocks(reln, FSM_FORKNUM);
573  else
574  reln->smgr_cached_nblocks[FSM_FORKNUM] = 0;
575  }
576 
577  /*
578  * For reading we use ZERO_ON_ERROR mode, and initialize the page if
579  * necessary. The FSM information is not accurate anyway, so it's better
580  * to clear corrupt pages than error out. Since the FSM changes are not
581  * WAL-logged, the so-called torn page problem on crash can lead to pages
582  * with corrupt headers, for example.
583  *
584  * We use the same path below to initialize pages when extending the
585  * relation, as a concurrent extension can end up with vm_extend()
586  * returning an already-initialized page.
587  */
588  if (blkno >= reln->smgr_cached_nblocks[FSM_FORKNUM])
589  {
590  if (extend)
591  buf = fsm_extend(rel, blkno + 1);
592  else
593  return InvalidBuffer;
594  }
595  else
596  buf = ReadBufferExtended(rel, FSM_FORKNUM, blkno, RBM_ZERO_ON_ERROR, NULL);
597 
598  /*
599  * Initializing the page when needed is trickier than it looks, because of
600  * the possibility of multiple backends doing this concurrently, and our
601  * desire to not uselessly take the buffer lock in the normal path where
602  * the page is OK. We must take the lock to initialize the page, so
603  * recheck page newness after we have the lock, in case someone else
604  * already did it. Also, because we initially check PageIsNew with no
605  * lock, it's possible to fall through and return the buffer while someone
606  * else is still initializing the page (i.e., we might see pd_upper as set
607  * but other page header fields are still zeroes). This is harmless for
608  * callers that will take a buffer lock themselves, but some callers
609  * inspect the page without any lock at all. The latter is OK only so
610  * long as it doesn't depend on the page header having correct contents.
611  * Current usage is safe because PageGetContents() does not require that.
612  */
614  {
617  PageInit(BufferGetPage(buf), BLCKSZ, 0);
619  }
620  return buf;
621 }
#define InvalidBuffer
Definition: buf.h:25
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:792
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:193
void PageInit(Page page, Size pageSize, Size specialSize)
Definition: bufpage.c:42
static bool PageIsNew(Page page)
Definition: bufpage.h:230
static Buffer fsm_extend(Relation rel, BlockNumber fsm_nblocks)
Definition: freespace.c:629

References buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage(), fsm_extend(), FSM_FORKNUM, fsm_logical_to_physical(), InvalidBlockNumber, InvalidBuffer, LockBuffer(), PageInit(), PageIsNew(), RBM_ZERO_ON_ERROR, ReadBufferExtended(), RelationGetSmgr(), SMgrRelationData::smgr_cached_nblocks, smgrexists(), and smgrnblocks().

Referenced by FreeSpaceMapPrepareTruncateRel(), fsm_search(), fsm_set_and_search(), fsm_vacuum_page(), and GetRecordedFreeSpace().

◆ fsm_search()

static BlockNumber fsm_search ( Relation  rel,
uint8  min_cat 
)
static

Definition at line 678 of file freespace.c.

679 {
680  int restarts = 0;
682 
683  for (;;)
684  {
685  int slot;
686  Buffer buf;
687  uint8 max_avail = 0;
688 
689  /* Read the FSM page. */
690  buf = fsm_readbuf(rel, addr, false);
691 
692  /* Search within the page */
693  if (BufferIsValid(buf))
694  {
696  slot = fsm_search_avail(buf, min_cat,
697  (addr.level == FSM_BOTTOM_LEVEL),
698  false);
699  if (slot == -1)
700  {
701  max_avail = fsm_get_max_avail(BufferGetPage(buf));
703  }
704  else
705  {
706  /* Keep the pin for possible update below */
708  }
709  }
710  else
711  slot = -1;
712 
713  if (slot != -1)
714  {
715  /*
716  * Descend the tree, or return the found block if we're at the
717  * bottom.
718  */
719  if (addr.level == FSM_BOTTOM_LEVEL)
720  {
721  BlockNumber blkno = fsm_get_heap_blk(addr, slot);
722  Page page;
723 
724  if (fsm_does_block_exist(rel, blkno))
725  {
727  return blkno;
728  }
729 
730  /*
731  * Block is past the end of the relation. Update FSM, and
732  * restart from root. The usual "advancenext" behavior is
733  * pessimal for this rare scenario, since every later slot is
734  * unusable in the same way. We could zero all affected slots
735  * on the same FSM page, but don't bet on the benefits of that
736  * optimization justifying its compiled code bulk.
737  */
738  page = BufferGetPage(buf);
740  fsm_set_avail(page, slot, 0);
741  MarkBufferDirtyHint(buf, false);
743  if (restarts++ > 10000) /* same rationale as below */
744  return InvalidBlockNumber;
745  addr = FSM_ROOT_ADDRESS;
746  }
747  else
748  {
750  }
751  addr = fsm_get_child(addr, slot);
752  }
753  else if (addr.level == FSM_ROOT_LEVEL)
754  {
755  /*
756  * At the root, failure means there's no page with enough free
757  * space in the FSM. Give up.
758  */
759  return InvalidBlockNumber;
760  }
761  else
762  {
763  uint16 parentslot;
764  FSMAddress parent;
765 
766  /*
767  * At lower level, failure can happen if the value in the upper-
768  * level node didn't reflect the value on the lower page. Update
769  * the upper node, to avoid falling into the same trap again, and
770  * start over.
771  *
772  * There's a race condition here, if another backend updates this
773  * page right after we release it, and gets the lock on the parent
774  * page before us. We'll then update the parent page with the now
775  * stale information we had. It's OK, because it should happen
776  * rarely, and will be fixed by the next vacuum.
777  */
778  parent = fsm_get_parent(addr, &parentslot);
779  fsm_set_and_search(rel, parent, parentslot, max_avail, 0);
780 
781  /*
782  * If the upper pages are badly out of date, we might need to loop
783  * quite a few times, updating them as we go. Any inconsistencies
784  * should eventually be corrected and the loop should end. Looping
785  * indefinitely is nevertheless scary, so provide an emergency
786  * valve.
787  */
788  if (restarts++ > 10000)
789  return InvalidBlockNumber;
790 
791  /* Start search all over from the root */
792  addr = FSM_ROOT_ADDRESS;
793  }
794  }
795 }
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4896
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:4960
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:194
Pointer Page
Definition: bufpage.h:78
unsigned char uint8
Definition: c.h:504
static FSMAddress fsm_get_child(FSMAddress parent, uint16 slot)
Definition: freespace.c:535
static bool fsm_does_block_exist(Relation rel, BlockNumber blknumber)
Definition: freespace.c:926
static FSMAddress fsm_get_parent(FSMAddress child, uint16 *slot)
Definition: freespace.c:517
static int fsm_set_and_search(Relation rel, FSMAddress addr, uint16 slot, uint8 newValue, uint8 minValue)
Definition: freespace.c:646
static BlockNumber fsm_get_heap_blk(FSMAddress addr, uint16 slot)
Definition: freespace.c:506
uint8 fsm_get_max_avail(Page page)
Definition: fsmpage.c:138
bool fsm_set_avail(Page page, int slot, uint8 value)
Definition: fsmpage.c:63
int fsm_search_avail(Buffer buf, uint8 minvalue, bool advancenext, bool exclusive_lock_held)
Definition: fsmpage.c:158

References buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_SHARE, BUFFER_LOCK_UNLOCK, BufferGetPage(), BufferIsValid(), FSM_BOTTOM_LEVEL, fsm_does_block_exist(), fsm_get_child(), fsm_get_heap_blk(), fsm_get_max_avail(), fsm_get_parent(), fsm_readbuf(), FSM_ROOT_ADDRESS, FSM_ROOT_LEVEL, fsm_search_avail(), fsm_set_and_search(), fsm_set_avail(), InvalidBlockNumber, FSMAddress::level, LockBuffer(), MarkBufferDirtyHint(), ReleaseBuffer(), and UnlockReleaseBuffer().

Referenced by GetPageWithFreeSpace(), and RecordAndGetPageWithFreeSpace().

◆ fsm_set_and_search()

static int fsm_set_and_search ( Relation  rel,
FSMAddress  addr,
uint16  slot,
uint8  newValue,
uint8  minValue 
)
static

Definition at line 646 of file freespace.c.

648 {
649  Buffer buf;
650  Page page;
651  int newslot = -1;
652 
653  buf = fsm_readbuf(rel, addr, true);
655 
656  page = BufferGetPage(buf);
657 
658  if (fsm_set_avail(page, slot, newValue))
659  MarkBufferDirtyHint(buf, false);
660 
661  if (minValue != 0)
662  {
663  /* Search while we still hold the lock */
664  newslot = fsm_search_avail(buf, minValue,
665  addr.level == FSM_BOTTOM_LEVEL,
666  true);
667  }
668 
670 
671  return newslot;
672 }

References buf, BUFFER_LOCK_EXCLUSIVE, BufferGetPage(), FSM_BOTTOM_LEVEL, fsm_readbuf(), fsm_search_avail(), fsm_set_avail(), FSMAddress::level, LockBuffer(), MarkBufferDirtyHint(), and UnlockReleaseBuffer().

Referenced by fsm_search(), RecordAndGetPageWithFreeSpace(), and RecordPageWithFreeSpace().

◆ fsm_space_avail_to_cat()

static uint8 fsm_space_avail_to_cat ( Size  avail)
static

Definition at line 392 of file freespace.c.

393 {
394  int cat;
395 
396  Assert(avail < BLCKSZ);
397 
398  if (avail >= MaxFSMRequestSize)
399  return 255;
400 
401  cat = avail / FSM_CAT_STEP;
402 
403  /*
404  * The highest category, 255, is reserved for MaxFSMRequestSize bytes or
405  * more.
406  */
407  if (cat > 254)
408  cat = 254;
409 
410  return (uint8) cat;
411 }
#define MaxFSMRequestSize
Definition: freespace.c:66
#define FSM_CAT_STEP
Definition: freespace.c:65

References Assert, FSM_CAT_STEP, and MaxFSMRequestSize.

Referenced by RecordAndGetPageWithFreeSpace(), RecordPageWithFreeSpace(), and XLogRecordPageWithFreeSpace().

◆ fsm_space_cat_to_avail()

static Size fsm_space_cat_to_avail ( uint8  cat)
static

Definition at line 418 of file freespace.c.

419 {
420  /* The highest category represents exactly MaxFSMRequestSize bytes. */
421  if (cat == 255)
422  return MaxFSMRequestSize;
423  else
424  return cat * FSM_CAT_STEP;
425 }

References FSM_CAT_STEP, and MaxFSMRequestSize.

Referenced by GetRecordedFreeSpace().

◆ fsm_space_needed_to_cat()

static uint8 fsm_space_needed_to_cat ( Size  needed)
static

Definition at line 432 of file freespace.c.

433 {
434  int cat;
435 
436  /* Can't ask for more space than the highest category represents */
437  if (needed > MaxFSMRequestSize)
438  elog(ERROR, "invalid FSM request size %zu", needed);
439 
440  if (needed == 0)
441  return 1;
442 
443  cat = (needed + FSM_CAT_STEP - 1) / FSM_CAT_STEP;
444 
445  if (cat > 255)
446  cat = 255;
447 
448  return (uint8) cat;
449 }
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224

References elog, ERROR, FSM_CAT_STEP, and MaxFSMRequestSize.

Referenced by GetPageWithFreeSpace(), and RecordAndGetPageWithFreeSpace().

◆ fsm_vacuum_page()

static uint8 fsm_vacuum_page ( Relation  rel,
FSMAddress  addr,
BlockNumber  start,
BlockNumber  end,
bool eof_p 
)
static

Definition at line 812 of file freespace.c.

815 {
816  Buffer buf;
817  Page page;
818  uint8 max_avail;
819 
820  /* Read the page if it exists, or return EOF */
821  buf = fsm_readbuf(rel, addr, false);
822  if (!BufferIsValid(buf))
823  {
824  *eof_p = true;
825  return 0;
826  }
827  else
828  *eof_p = false;
829 
830  page = BufferGetPage(buf);
831 
832  /*
833  * If we're above the bottom level, recurse into children, and fix the
834  * information stored about them at this level.
835  */
836  if (addr.level > FSM_BOTTOM_LEVEL)
837  {
838  FSMAddress fsm_start,
839  fsm_end;
840  uint16 fsm_start_slot,
841  fsm_end_slot;
842  int slot,
843  start_slot,
844  end_slot;
845  bool eof = false;
846 
847  /*
848  * Compute the range of slots we need to update on this page, given
849  * the requested range of heap blocks to consider. The first slot to
850  * update is the one covering the "start" block, and the last slot is
851  * the one covering "end - 1". (Some of this work will be duplicated
852  * in each recursive call, but it's cheap enough to not worry about.)
853  */
854  fsm_start = fsm_get_location(start, &fsm_start_slot);
855  fsm_end = fsm_get_location(end - 1, &fsm_end_slot);
856 
857  while (fsm_start.level < addr.level)
858  {
859  fsm_start = fsm_get_parent(fsm_start, &fsm_start_slot);
860  fsm_end = fsm_get_parent(fsm_end, &fsm_end_slot);
861  }
862  Assert(fsm_start.level == addr.level);
863 
864  if (fsm_start.logpageno == addr.logpageno)
865  start_slot = fsm_start_slot;
866  else if (fsm_start.logpageno > addr.logpageno)
867  start_slot = SlotsPerFSMPage; /* shouldn't get here... */
868  else
869  start_slot = 0;
870 
871  if (fsm_end.logpageno == addr.logpageno)
872  end_slot = fsm_end_slot;
873  else if (fsm_end.logpageno > addr.logpageno)
874  end_slot = SlotsPerFSMPage - 1;
875  else
876  end_slot = -1; /* shouldn't get here... */
877 
878  for (slot = start_slot; slot <= end_slot; slot++)
879  {
880  int child_avail;
881 
883 
884  /* After we hit end-of-file, just clear the rest of the slots */
885  if (!eof)
886  child_avail = fsm_vacuum_page(rel, fsm_get_child(addr, slot),
887  start, end,
888  &eof);
889  else
890  child_avail = 0;
891 
892  /* Update information about the child */
893  if (fsm_get_avail(page, slot) != child_avail)
894  {
896  fsm_set_avail(page, slot, child_avail);
897  MarkBufferDirtyHint(buf, false);
899  }
900  }
901  }
902 
903  /* Now get the maximum value on the page, to return to caller */
904  max_avail = fsm_get_max_avail(page);
905 
906  /*
907  * Reset the next slot pointer. This encourages the use of low-numbered
908  * pages, increasing the chances that a later vacuum can truncate the
909  * relation. We don't bother with a lock here, nor with marking the page
910  * dirty if it wasn't already, since this is just a hint.
911  */
912  ((FSMPage) PageGetContents(page))->fp_next_slot = 0;
913 
915 
916  return max_avail;
917 }
static char * PageGetContents(Page page)
Definition: bufpage.h:254
FSMPageData * FSMPage
Definition: fsm_internals.h:45
uint8 fsm_get_avail(Page page, int slot)
Definition: fsmpage.c:122
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122

References Assert, buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage(), BufferIsValid(), CHECK_FOR_INTERRUPTS, FSM_BOTTOM_LEVEL, fsm_get_avail(), fsm_get_child(), fsm_get_location(), fsm_get_max_avail(), fsm_get_parent(), fsm_readbuf(), fsm_set_avail(), FSMAddress::level, LockBuffer(), FSMAddress::logpageno, MarkBufferDirtyHint(), PageGetContents(), ReleaseBuffer(), SlotsPerFSMPage, and start.

Referenced by FreeSpaceMapVacuum(), and FreeSpaceMapVacuumRange().

◆ GetPageWithFreeSpace()

BlockNumber GetPageWithFreeSpace ( Relation  rel,
Size  spaceNeeded 
)

Definition at line 137 of file freespace.c.

138 {
139  uint8 min_cat = fsm_space_needed_to_cat(spaceNeeded);
140 
141  return fsm_search(rel, min_cat);
142 }
static uint8 fsm_space_needed_to_cat(Size needed)
Definition: freespace.c:432
static BlockNumber fsm_search(Relation rel, uint8 min_cat)
Definition: freespace.c:678

References fsm_search(), and fsm_space_needed_to_cat().

Referenced by brin_getinsertbuffer(), GetFreeIndexPage(), and RelationGetBufferForTuple().

◆ GetRecordedFreeSpace()

Size GetRecordedFreeSpace ( Relation  rel,
BlockNumber  heapBlk 
)

Definition at line 244 of file freespace.c.

245 {
246  FSMAddress addr;
247  uint16 slot;
248  Buffer buf;
249  uint8 cat;
250 
251  /* Get the location of the FSM byte representing the heap block */
252  addr = fsm_get_location(heapBlk, &slot);
253 
254  buf = fsm_readbuf(rel, addr, false);
255  if (!BufferIsValid(buf))
256  return 0;
257  cat = fsm_get_avail(BufferGetPage(buf), slot);
259 
260  return fsm_space_cat_to_avail(cat);
261 }
static Size fsm_space_cat_to_avail(uint8 cat)
Definition: freespace.c:418

References buf, BufferGetPage(), BufferIsValid(), fsm_get_avail(), fsm_get_location(), fsm_readbuf(), fsm_space_cat_to_avail(), and ReleaseBuffer().

Referenced by lazy_scan_new_or_empty(), pg_freespace(), and statapprox_heap().

◆ RecordAndGetPageWithFreeSpace()

BlockNumber RecordAndGetPageWithFreeSpace ( Relation  rel,
BlockNumber  oldPage,
Size  oldSpaceAvail,
Size  spaceNeeded 
)

Definition at line 154 of file freespace.c.

156 {
157  int old_cat = fsm_space_avail_to_cat(oldSpaceAvail);
158  int search_cat = fsm_space_needed_to_cat(spaceNeeded);
159  FSMAddress addr;
160  uint16 slot;
161  int search_slot;
162 
163  /* Get the location of the FSM byte representing the heap block */
164  addr = fsm_get_location(oldPage, &slot);
165 
166  search_slot = fsm_set_and_search(rel, addr, slot, old_cat, search_cat);
167 
168  /*
169  * If fsm_set_and_search found a suitable new block, return that.
170  * Otherwise, search as usual.
171  */
172  if (search_slot != -1)
173  {
174  BlockNumber blknum = fsm_get_heap_blk(addr, search_slot);
175 
176  /*
177  * Check that the blknum is actually in the relation. Don't try to
178  * update the FSM in that case, just fall back to the other case
179  */
180  if (fsm_does_block_exist(rel, blknum))
181  return blknum;
182  }
183  return fsm_search(rel, search_cat);
184 }
static uint8 fsm_space_avail_to_cat(Size avail)
Definition: freespace.c:392

References fsm_does_block_exist(), fsm_get_heap_blk(), fsm_get_location(), fsm_search(), fsm_set_and_search(), fsm_space_avail_to_cat(), and fsm_space_needed_to_cat().

Referenced by brin_getinsertbuffer(), and RelationGetBufferForTuple().

◆ RecordPageWithFreeSpace()

void RecordPageWithFreeSpace ( Relation  rel,
BlockNumber  heapBlk,
Size  spaceAvail 
)

Definition at line 194 of file freespace.c.

195 {
196  int new_cat = fsm_space_avail_to_cat(spaceAvail);
197  FSMAddress addr;
198  uint16 slot;
199 
200  /* Get the location of the FSM byte representing the heap block */
201  addr = fsm_get_location(heapBlk, &slot);
202 
203  fsm_set_and_search(rel, addr, slot, new_cat, 0);
204 }

References fsm_get_location(), fsm_set_and_search(), and fsm_space_avail_to_cat().

Referenced by brin_doinsert(), brin_doupdate(), brin_initialize_empty_new_buffer(), brin_page_cleanup(), lazy_scan_heap(), lazy_scan_new_or_empty(), lazy_vacuum_heap_rel(), RecordFreeIndexPage(), RecordUsedIndexPage(), RelationAddBlocks(), RelationGetBufferForTuple(), and terminate_brin_buildstate().

◆ XLogRecordPageWithFreeSpace()

void XLogRecordPageWithFreeSpace ( RelFileLocator  rlocator,
BlockNumber  heapBlk,
Size  spaceAvail 
)

Definition at line 211 of file freespace.c.

213 {
214  int new_cat = fsm_space_avail_to_cat(spaceAvail);
215  FSMAddress addr;
216  uint16 slot;
217  BlockNumber blkno;
218  Buffer buf;
219  Page page;
220 
221  /* Get the location of the FSM byte representing the heap block */
222  addr = fsm_get_location(heapBlk, &slot);
223  blkno = fsm_logical_to_physical(addr);
224 
225  /* If the page doesn't exist already, extend */
226  buf = XLogReadBufferExtended(rlocator, FSM_FORKNUM, blkno,
229 
230  page = BufferGetPage(buf);
231  if (PageIsNew(page))
232  PageInit(page, BLCKSZ, 0);
233 
234  if (fsm_set_avail(page, slot, new_cat))
235  MarkBufferDirtyHint(buf, false);
237 }
Buffer XLogReadBufferExtended(RelFileLocator rlocator, ForkNumber forknum, BlockNumber blkno, ReadBufferMode mode, Buffer recent_buffer)
Definition: xlogutils.c:471

References buf, BUFFER_LOCK_EXCLUSIVE, BufferGetPage(), FSM_FORKNUM, fsm_get_location(), fsm_logical_to_physical(), fsm_set_avail(), fsm_space_avail_to_cat(), InvalidBuffer, LockBuffer(), MarkBufferDirtyHint(), PageInit(), PageIsNew(), RBM_ZERO_ON_ERROR, UnlockReleaseBuffer(), and XLogReadBufferExtended().

Referenced by heap_xlog_insert(), heap_xlog_multi_insert(), heap_xlog_prune_freeze(), heap_xlog_update(), and heap_xlog_visible().

Variable Documentation

◆ FSM_ROOT_ADDRESS

const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0}
static

Definition at line 91 of file freespace.c.

Referenced by FreeSpaceMapVacuum(), FreeSpaceMapVacuumRange(), and fsm_search().