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.

{
    BlockNumber new_nfsmblocks;
    FSMAddress  first_removed_address;
    uint16      first_removed_slot;
    Buffer      buf;
 
    /*
     * If no FSM has been created yet for this relation, there's nothing to
     * truncate.
     */
    if (!smgrexists(RelationGetSmgr(rel), FSM_FORKNUM))
        return InvalidBlockNumber;
 
    /* Get the location in the FSM of the first removed heap block */
    first_removed_address = fsm_get_location(nblocks, &first_removed_slot);
 
    /*
     * Zero out the tail of the last remaining FSM page. If the slot
     * representing the first removed heap block is at a page boundary, as the
     * first slot on the FSM page that first_removed_address points to, we can
     * just truncate that page altogether.
     */
    if (first_removed_slot > 0)
    {
        buf = fsm_readbuf(rel, first_removed_address, false);
        if (!BufferIsValid(buf))
            return InvalidBlockNumber;  /* nothing to do; the FSM was already
                                         * smaller */
        LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
 
        /* NO EREPORT(ERROR) from here till changes are logged */
        START_CRIT_SECTION();
 
        fsm_truncate_avail(BufferGetPage(buf), first_removed_slot);
 
        /*
         * This change is non-critical, because fsm_does_block_exist() would
         * stop us from returning a truncated-away block.  However, since this
         * may remove up to SlotsPerFSMPage slots, it's nice to avoid the cost
         * of that many fsm_does_block_exist() rejections.  Use a full
         * MarkBufferDirty(), not MarkBufferDirtyHint().
         */
        MarkBufferDirty(buf);
 
        /*
         * WAL-log like MarkBufferDirtyHint() might have done, just to avoid
         * differing from the rest of the file in this respect.  This is
         * optional; see README mention of full page images.  XXX consider
         * XLogSaveBufferForHint() for even closer similarity.
         *
         * A higher-level operation calls us at WAL replay.  If we crash
         * before the XLOG_SMGR_TRUNCATE flushes to disk, main fork length has
         * not changed, and our fork remains valid.  If we crash after that
         * flush, redo will return here.
         */
        if (!InRecovery && RelationNeedsWAL(rel) && XLogHintBitIsNeeded())
            log_newpage_buffer(buf, false);
 
        END_CRIT_SECTION();
 
        UnlockReleaseBuffer(buf);
 
        new_nfsmblocks = fsm_logical_to_physical(first_removed_address) + 1;
    }
    else
    {
        new_nfsmblocks = fsm_logical_to_physical(first_removed_address);
        if (smgrnblocks(RelationGetSmgr(rel), FSM_FORKNUM) <= new_nfsmblocks)
            return InvalidBlockNumber;  /* nothing to do; the FSM was already
                                         * smaller */
    }
 
    return new_nfsmblocks;
}

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.

{
    bool        dummy;
 
    /* Recursively scan the tree, starting at the root */
    (void) fsm_vacuum_page(rel, FSM_ROOT_ADDRESS,
                           (BlockNumber) 0, InvalidBlockNumber,
                           &dummy);
}

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.

{
    bool        dummy;
 
    /* Recursively scan the tree, starting at the root */
    if (end > start)
        (void) fsm_vacuum_page(rel, FSM_ROOT_ADDRESS, start, end, &dummy);
}

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.

{
    SMgrRelation smgr = RelationGetSmgr(rel);
 
    /*
     * If below the cached nblocks, the block surely exists.  Otherwise, we
     * face a trade-off.  We opt to compare to a fresh nblocks, incurring
     * lseek() overhead.  The alternative would be to assume the block does
     * not exist, but that would cause FSM to set zero space available for
     * blocks that main fork extension just recorded.
     */
    return ((BlockNumberIsValid(smgr->smgr_cached_nblocks[MAIN_FORKNUM]) &&
             blknumber < smgr->smgr_cached_nblocks[MAIN_FORKNUM]) ||
            blknumber < RelationGetNumberOfBlocks(rel));
}

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.

{
    return ExtendBufferedRelTo(BMR_REL(rel), FSM_FORKNUM, NULL,
                               EB_CREATE_FORK_IF_NEEDED |
                               EB_CLEAR_SIZE_CACHE,
                               fsm_nblocks,
                               RBM_ZERO_ON_ERROR);
}

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.

{
    FSMAddress  child;
 
    Assert(parent.level > FSM_BOTTOM_LEVEL);
 
    child.level = parent.level - 1;
    child.logpageno = parent.logpageno * SlotsPerFSMPage + slot;
 
    return child;
}

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.

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

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.

{
    FSMAddress  addr;
 
    addr.level = FSM_BOTTOM_LEVEL;
    addr.logpageno = heapblk / SlotsPerFSMPage;
    *slot = heapblk % SlotsPerFSMPage;
 
    return addr;
}

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.

{
    FSMAddress  parent;
 
    Assert(child.level < FSM_ROOT_LEVEL);
 
    parent.level = child.level + 1;
    parent.logpageno = child.logpageno / SlotsPerFSMPage;
    *slot = child.logpageno % SlotsPerFSMPage;
 
    return parent;
}

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.

{
    BlockNumber pages;
    int         leafno;
    int         l;
 
    /*
     * Calculate the logical page number of the first leaf page below the
     * given page.
     */
    leafno = addr.logpageno;
    for (l = 0; l < addr.level; l++)
        leafno *= SlotsPerFSMPage;
 
    /* Count upper level nodes required to address the leaf page */
    pages = 0;
    for (l = 0; l < FSM_TREE_DEPTH; l++)
    {
        pages += leafno + 1;
        leafno /= SlotsPerFSMPage;
    }
 
    /*
     * If the page we were asked for wasn't at the bottom level, subtract the
     * additional lower level pages we counted above.
     */
    pages -= addr.level;
 
    /* Turn the page count into 0-based block number */
    return pages - 1;
}

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.

{
    BlockNumber blkno = fsm_logical_to_physical(addr);
    Buffer      buf;
    SMgrRelation reln = RelationGetSmgr(rel);
 
    /*
     * If we haven't cached the size of the FSM yet, check it first.  Also
     * recheck if the requested block seems to be past end, since our cached
     * value might be stale.  (We send smgr inval messages on truncation, but
     * not on extension.)
     */
    if (reln->smgr_cached_nblocks[FSM_FORKNUM] == InvalidBlockNumber ||
        blkno >= reln->smgr_cached_nblocks[FSM_FORKNUM])
    {
        /* Invalidate the cache so smgrnblocks asks the kernel. */
        reln->smgr_cached_nblocks[FSM_FORKNUM] = InvalidBlockNumber;
        if (smgrexists(reln, FSM_FORKNUM))
            smgrnblocks(reln, FSM_FORKNUM);
        else
            reln->smgr_cached_nblocks[FSM_FORKNUM] = 0;
    }
 
    /*
     * For reading we use ZERO_ON_ERROR mode, and initialize the page if
     * necessary.  The FSM information is not accurate anyway, so it's better
     * to clear corrupt pages than error out. Since the FSM changes are not
     * WAL-logged, the so-called torn page problem on crash can lead to pages
     * with corrupt headers, for example.
     *
     * We use the same path below to initialize pages when extending the
     * relation, as a concurrent extension can end up with vm_extend()
     * returning an already-initialized page.
     */
    if (blkno >= reln->smgr_cached_nblocks[FSM_FORKNUM])
    {
        if (extend)
            buf = fsm_extend(rel, blkno + 1);
        else
            return InvalidBuffer;
    }
    else
        buf = ReadBufferExtended(rel, FSM_FORKNUM, blkno, RBM_ZERO_ON_ERROR, NULL);
 
    /*
     * Initializing the page when needed is trickier than it looks, because of
     * the possibility of multiple backends doing this concurrently, and our
     * desire to not uselessly take the buffer lock in the normal path where
     * the page is OK.  We must take the lock to initialize the page, so
     * recheck page newness after we have the lock, in case someone else
     * already did it.  Also, because we initially check PageIsNew with no
     * lock, it's possible to fall through and return the buffer while someone
     * else is still initializing the page (i.e., we might see pd_upper as set
     * but other page header fields are still zeroes).  This is harmless for
     * callers that will take a buffer lock themselves, but some callers
     * inspect the page without any lock at all.  The latter is OK only so
     * long as it doesn't depend on the page header having correct contents.
     * Current usage is safe because PageGetContents() does not require that.
     */
    if (PageIsNew(BufferGetPage(buf)))
    {
        LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
        if (PageIsNew(BufferGetPage(buf)))
            PageInit(BufferGetPage(buf), BLCKSZ, 0);
        LockBuffer(buf, BUFFER_LOCK_UNLOCK);
    }
    return buf;
}

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.

{
    int         restarts = 0;
    FSMAddress  addr = FSM_ROOT_ADDRESS;
 
    for (;;)
    {
        int         slot;
        Buffer      buf;
        uint8       max_avail = 0;
 
        /* Read the FSM page. */
        buf = fsm_readbuf(rel, addr, false);
 
        /* Search within the page */
        if (BufferIsValid(buf))
        {
            LockBuffer(buf, BUFFER_LOCK_SHARE);
            slot = fsm_search_avail(buf, min_cat,
                                    (addr.level == FSM_BOTTOM_LEVEL),
                                    false);
            if (slot == -1)
            {
                max_avail = fsm_get_max_avail(BufferGetPage(buf));
                UnlockReleaseBuffer(buf);
            }
            else
            {
                /* Keep the pin for possible update below */
                LockBuffer(buf, BUFFER_LOCK_UNLOCK);
            }
        }
        else
            slot = -1;
 
        if (slot != -1)
        {
            /*
             * Descend the tree, or return the found block if we're at the
             * bottom.
             */
            if (addr.level == FSM_BOTTOM_LEVEL)
            {
                BlockNumber blkno = fsm_get_heap_blk(addr, slot);
                Page        page;
 
                if (fsm_does_block_exist(rel, blkno))
                {
                    ReleaseBuffer(buf);
                    return blkno;
                }
 
                /*
                 * Block is past the end of the relation.  Update FSM, and
                 * restart from root.  The usual "advancenext" behavior is
                 * pessimal for this rare scenario, since every later slot is
                 * unusable in the same way.  We could zero all affected slots
                 * on the same FSM page, but don't bet on the benefits of that
                 * optimization justifying its compiled code bulk.
                 */
                page = BufferGetPage(buf);
                LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
                fsm_set_avail(page, slot, 0);
                MarkBufferDirtyHint(buf, false);
                UnlockReleaseBuffer(buf);
                if (restarts++ > 10000) /* same rationale as below */
                    return InvalidBlockNumber;
                addr = FSM_ROOT_ADDRESS;
            }
            else
            {
                ReleaseBuffer(buf);
            }
            addr = fsm_get_child(addr, slot);
        }
        else if (addr.level == FSM_ROOT_LEVEL)
        {
            /*
             * At the root, failure means there's no page with enough free
             * space in the FSM. Give up.
             */
            return InvalidBlockNumber;
        }
        else
        {
            uint16      parentslot;
            FSMAddress  parent;
 
            /*
             * At lower level, failure can happen if the value in the upper-
             * level node didn't reflect the value on the lower page. Update
             * the upper node, to avoid falling into the same trap again, and
             * start over.
             *
             * There's a race condition here, if another backend updates this
             * page right after we release it, and gets the lock on the parent
             * page before us. We'll then update the parent page with the now
             * stale information we had. It's OK, because it should happen
             * rarely, and will be fixed by the next vacuum.
             */
            parent = fsm_get_parent(addr, &parentslot);
            fsm_set_and_search(rel, parent, parentslot, max_avail, 0);
 
            /*
             * If the upper pages are badly out of date, we might need to loop
             * quite a few times, updating them as we go. Any inconsistencies
             * should eventually be corrected and the loop should end. Looping
             * indefinitely is nevertheless scary, so provide an emergency
             * valve.
             */
            if (restarts++ > 10000)
                return InvalidBlockNumber;
 
            /* Start search all over from the root */
            addr = FSM_ROOT_ADDRESS;
        }
    }
}

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.

{
    Buffer      buf;
    Page        page;
    int         newslot = -1;
 
    buf = fsm_readbuf(rel, addr, true);
    LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
 
    page = BufferGetPage(buf);
 
    if (fsm_set_avail(page, slot, newValue))
        MarkBufferDirtyHint(buf, false);
 
    if (minValue != 0)
    {
        /* Search while we still hold the lock */
        newslot = fsm_search_avail(buf, minValue,
                                   addr.level == FSM_BOTTOM_LEVEL,
                                   true);
    }
 
    UnlockReleaseBuffer(buf);
 
    return newslot;
}

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.

{
    int         cat;
 
    Assert(avail < BLCKSZ);
 
    if (avail >= MaxFSMRequestSize)
        return 255;
 
    cat = avail / FSM_CAT_STEP;
 
    /*
     * The highest category, 255, is reserved for MaxFSMRequestSize bytes or
     * more.
     */
    if (cat > 254)
        cat = 254;
 
    return (uint8) cat;
}

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.

{
    /* The highest category represents exactly MaxFSMRequestSize bytes. */
    if (cat == 255)
        return MaxFSMRequestSize;
    else
        return cat * FSM_CAT_STEP;
}

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.

{
    int         cat;
 
    /* Can't ask for more space than the highest category represents */
    if (needed > MaxFSMRequestSize)
        elog(ERROR, "invalid FSM request size %zu", needed);
 
    if (needed == 0)
        return 1;
 
    cat = (needed + FSM_CAT_STEP - 1) / FSM_CAT_STEP;
 
    if (cat > 255)
        cat = 255;
 
    return (uint8) cat;
}

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.

{
    Buffer      buf;
    Page        page;
    uint8       max_avail;
 
    /* Read the page if it exists, or return EOF */
    buf = fsm_readbuf(rel, addr, false);
    if (!BufferIsValid(buf))
    {
        *eof_p = true;
        return 0;
    }
    else
        *eof_p = false;
 
    page = BufferGetPage(buf);
 
    /*
     * If we're above the bottom level, recurse into children, and fix the
     * information stored about them at this level.
     */
    if (addr.level > FSM_BOTTOM_LEVEL)
    {
        FSMAddress  fsm_start,
                    fsm_end;
        uint16      fsm_start_slot,
                    fsm_end_slot;
        int         slot,
                    start_slot,
                    end_slot;
        bool        eof = false;
 
        /*
         * Compute the range of slots we need to update on this page, given
         * the requested range of heap blocks to consider.  The first slot to
         * update is the one covering the "start" block, and the last slot is
         * the one covering "end - 1".  (Some of this work will be duplicated
         * in each recursive call, but it's cheap enough to not worry about.)
         */
        fsm_start = fsm_get_location(start, &fsm_start_slot);
        fsm_end = fsm_get_location(end - 1, &fsm_end_slot);
 
        while (fsm_start.level < addr.level)
        {
            fsm_start = fsm_get_parent(fsm_start, &fsm_start_slot);
            fsm_end = fsm_get_parent(fsm_end, &fsm_end_slot);
        }
        Assert(fsm_start.level == addr.level);
 
        if (fsm_start.logpageno == addr.logpageno)
            start_slot = fsm_start_slot;
        else if (fsm_start.logpageno > addr.logpageno)
            start_slot = SlotsPerFSMPage;   /* shouldn't get here... */
        else
            start_slot = 0;
 
        if (fsm_end.logpageno == addr.logpageno)
            end_slot = fsm_end_slot;
        else if (fsm_end.logpageno > addr.logpageno)
            end_slot = SlotsPerFSMPage - 1;
        else
            end_slot = -1;      /* shouldn't get here... */
 
        for (slot = start_slot; slot <= end_slot; slot++)
        {
            int         child_avail;
 
            CHECK_FOR_INTERRUPTS();
 
            /* After we hit end-of-file, just clear the rest of the slots */
            if (!eof)
                child_avail = fsm_vacuum_page(rel, fsm_get_child(addr, slot),
                                              start, end,
                                              &eof);
            else
                child_avail = 0;
 
            /* Update information about the child */
            if (fsm_get_avail(page, slot) != child_avail)
            {
                LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
                fsm_set_avail(page, slot, child_avail);
                MarkBufferDirtyHint(buf, false);
                LockBuffer(buf, BUFFER_LOCK_UNLOCK);
            }
        }
    }
 
    /* Now get the maximum value on the page, to return to caller */
    max_avail = fsm_get_max_avail(page);
 
    /*
     * Reset the next slot pointer. This encourages the use of low-numbered
     * pages, increasing the chances that a later vacuum can truncate the
     * relation.  We don't bother with a lock here, nor with marking the page
     * dirty if it wasn't already, since this is just a hint.
     */
    ((FSMPage) PageGetContents(page))->fp_next_slot = 0;
 
    ReleaseBuffer(buf);
 
    return max_avail;
}

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(), fsm_vacuum_page(), FSMAddress::level, LockBuffer(), FSMAddress::logpageno, MarkBufferDirtyHint(), PageGetContents(), ReleaseBuffer(), SlotsPerFSMPage, and start.

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

GetPageWithFreeSpace()

BlockNumber GetPageWithFreeSpace	(	Relation	rel,
		Size	spaceNeeded
	)

Definition at line 137 of file freespace.c.

{
    uint8       min_cat = fsm_space_needed_to_cat(spaceNeeded);
 
    return fsm_search(rel, min_cat);
}

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.

{
    FSMAddress  addr;
    uint16      slot;
    Buffer      buf;
    uint8       cat;
 
    /* Get the location of the FSM byte representing the heap block */
    addr = fsm_get_location(heapBlk, &slot);
 
    buf = fsm_readbuf(rel, addr, false);
    if (!BufferIsValid(buf))
        return 0;
    cat = fsm_get_avail(BufferGetPage(buf), slot);
    ReleaseBuffer(buf);
 
    return fsm_space_cat_to_avail(cat);
}

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.

{
    int         old_cat = fsm_space_avail_to_cat(oldSpaceAvail);
    int         search_cat = fsm_space_needed_to_cat(spaceNeeded);
    FSMAddress  addr;
    uint16      slot;
    int         search_slot;
 
    /* Get the location of the FSM byte representing the heap block */
    addr = fsm_get_location(oldPage, &slot);
 
    search_slot = fsm_set_and_search(rel, addr, slot, old_cat, search_cat);
 
    /*
     * If fsm_set_and_search found a suitable new block, return that.
     * Otherwise, search as usual.
     */
    if (search_slot != -1)
    {
        BlockNumber blknum = fsm_get_heap_blk(addr, search_slot);
 
        /*
         * Check that the blknum is actually in the relation. Don't try to
         * update the FSM in that case, just fall back to the other case
         */
        if (fsm_does_block_exist(rel, blknum))
            return blknum;
    }
    return fsm_search(rel, search_cat);
}

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.

{
    int         new_cat = fsm_space_avail_to_cat(spaceAvail);
    FSMAddress  addr;
    uint16      slot;
 
    /* Get the location of the FSM byte representing the heap block */
    addr = fsm_get_location(heapBlk, &slot);
 
    fsm_set_and_search(rel, addr, slot, new_cat, 0);
}

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.

{
    int         new_cat = fsm_space_avail_to_cat(spaceAvail);
    FSMAddress  addr;
    uint16      slot;
    BlockNumber blkno;
    Buffer      buf;
    Page        page;
 
    /* Get the location of the FSM byte representing the heap block */
    addr = fsm_get_location(heapBlk, &slot);
    blkno = fsm_logical_to_physical(addr);
 
    /* If the page doesn't exist already, extend */
    buf = XLogReadBufferExtended(rlocator, FSM_FORKNUM, blkno,
                                 RBM_ZERO_ON_ERROR, InvalidBuffer);
    LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
 
    page = BufferGetPage(buf);
    if (PageIsNew(page))
        PageInit(page, BLCKSZ, 0);
 
    if (fsm_set_avail(page, slot, new_cat))
        MarkBufferDirtyHint(buf, false);
    UnlockReleaseBuffer(buf);
}

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().