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/lmgr.h"
#include "storage/smgr.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 void	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)
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 263 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);
 
        /*
         * Truncation of a relation is WAL-logged at a higher-level, and we
         * will be called at WAL replay. But if checksums are enabled, we need
         * to still write a WAL record to protect against a torn page, if the
         * page is flushed to disk before the truncation WAL record. We cannot
         * use MarkBufferDirtyHint here, because that will not dirty the page
         * during recovery.
         */
        MarkBufferDirty(buf);
        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 335 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 354 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, and fsm_vacuum_page().

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

fsm_extend()

static void fsm_extend ( Relation  rel, BlockNumber  fsm_nblocks  )

static

Definition at line 608 of file freespace.c.

{
    BlockNumber fsm_nblocks_now;
    PGAlignedBlock pg;
    SMgrRelation reln;
 
    PageInit((Page) pg.data, BLCKSZ, 0);
 
    /*
     * We use the relation extension lock to lock out other backends trying to
     * extend the FSM at the same time. It also locks out extension of the
     * main fork, unnecessarily, but extending the FSM happens seldom enough
     * that it doesn't seem worthwhile to have a separate lock tag type for
     * it.
     *
     * Note that another backend might have extended or created the relation
     * by the time we get the lock.
     */
    LockRelationForExtension(rel, ExclusiveLock);
 
    /*
     * Caution: re-using this smgr pointer could fail if the relcache entry
     * gets closed.  It's safe as long as we only do smgr-level operations
     * between here and the last use of the pointer.
     */
    reln = RelationGetSmgr(rel);
 
    /*
     * Create the FSM file first if it doesn't exist.  If
     * smgr_cached_nblocks[FSM_FORKNUM] is positive then it must exist, no
     * need for an smgrexists call.
     */
    if ((reln->smgr_cached_nblocks[FSM_FORKNUM] == 0 ||
         reln->smgr_cached_nblocks[FSM_FORKNUM] == InvalidBlockNumber) &&
        !smgrexists(reln, FSM_FORKNUM))
        smgrcreate(reln, FSM_FORKNUM, false);
 
    /* Invalidate cache so that smgrnblocks() asks the kernel. */
    reln->smgr_cached_nblocks[FSM_FORKNUM] = InvalidBlockNumber;
    fsm_nblocks_now = smgrnblocks(reln, FSM_FORKNUM);
 
    /* Extend as needed. */
    while (fsm_nblocks_now < fsm_nblocks)
    {
        PageSetChecksumInplace((Page) pg.data, fsm_nblocks_now);
 
        smgrextend(reln, FSM_FORKNUM, fsm_nblocks_now,
                   pg.data, false);
        fsm_nblocks_now++;
    }
 
    UnlockRelationForExtension(rel, ExclusiveLock);
}

References PGAlignedBlock::data, ExclusiveLock, FSM_FORKNUM, InvalidBlockNumber, LockRelationForExtension(), PageInit(), PageSetChecksumInplace(), RelationGetSmgr(), SMgrRelationData::smgr_cached_nblocks, smgrcreate(), smgrexists(), smgrextend(), smgrnblocks(), and UnlockRelationForExtension().

Referenced by fsm_readbuf().

fsm_get_child()

static FSMAddress fsm_get_child ( FSMAddress  parent, uint16  slot  )

static

Definition at line 512 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 483 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 468 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 494 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 432 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 531 of file freespace.c.

{
    BlockNumber blkno = fsm_logical_to_physical(addr);
    Buffer      buf;
    SMgrRelation reln;
 
    /*
     * Caution: re-using this smgr pointer could fail if the relcache entry
     * gets closed.  It's safe as long as we only do smgr-level operations
     * between here and the last use of the pointer.
     */
    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;
    }
 
    /* Handle requests beyond EOF */
    if (blkno >= reln->smgr_cached_nblocks[FSM_FORKNUM])
    {
        if (extend)
            fsm_extend(rel, blkno + 1);
        else
            return InvalidBuffer;
    }
 
    /*
     * 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.
     *
     * The initialize-the-page part 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.
     */
    buf = ReadBufferExtended(rel, FSM_FORKNUM, blkno, RBM_ZERO_ON_ERROR, NULL);
    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 702 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
            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)
                return fsm_get_heap_blk(addr, slot);
 
            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_SHARE, BufferGetPage(), BufferIsValid(), FSM_BOTTOM_LEVEL, 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(), InvalidBlockNumber, FSMAddress::level, LockBuffer(), 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 670 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 369 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 395 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 409 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 800 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(), FSMAddress::level, LockBuffer(), FSMAddress::logpageno, MarkBufferDirtyHint(), PageGetContents(), ReleaseBuffer(), and SlotsPerFSMPage.

Referenced by FreeSpaceMapVacuum(), and FreeSpaceMapVacuumRange().

GetPageWithFreeSpace()

BlockNumber GetPageWithFreeSpace	(	Relation	rel,
		Size	spaceNeeded
	)

Definition at line 133 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 232 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 150 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)
        return fsm_get_heap_blk(addr, search_slot);
    else
        return fsm_search(rel, search_cat);
}

References 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 182 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(), RelationAddExtraBlocks(), and terminate_brin_buildstate().

XLogRecordPageWithFreeSpace()

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

Definition at line 199 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(), heap_xlog_update(), heap_xlog_vacuum(), 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().