fsm_internals.h File Reference

#include "storage/buf.h"
#include "storage/bufpage.h"

Include dependency graph for fsm_internals.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	FSMPageData

Macros
#define	NodesPerPage
#define	NonLeafNodesPerPage   (BLCKSZ / 2 - 1)
#define	LeafNodesPerPage   (NodesPerPage - NonLeafNodesPerPage)
#define	SlotsPerFSMPage   LeafNodesPerPage

Typedefs
typedef FSMPageData *	FSMPage

Functions
int	fsm_search_avail (Buffer buf, uint8 minvalue, bool advancenext, bool exclusive_lock_held)
uint8	fsm_get_avail (Page page, int slot)
uint8	fsm_get_max_avail (Page page)
bool	fsm_set_avail (Page page, int slot, uint8 value)
bool	fsm_truncate_avail (Page page, int nslots)
bool	fsm_rebuild_page (Page page)

Macro Definition Documentation

LeafNodesPerPage

#define LeafNodesPerPage   (NodesPerPage - NonLeafNodesPerPage)

Definition at line 55 of file fsm_internals.h.

NodesPerPage

#define NodesPerPage

Value:

                      (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \
                      offsetof(FSMPageData, fp_nodes))

Definition at line 51 of file fsm_internals.h.

NonLeafNodesPerPage

#define NonLeafNodesPerPage   (BLCKSZ / 2 - 1)

Definition at line 54 of file fsm_internals.h.

SlotsPerFSMPage

#define SlotsPerFSMPage   LeafNodesPerPage

Definition at line 61 of file fsm_internals.h.

Typedef Documentation

FSMPage

typedef FSMPageData* FSMPage

Definition at line 45 of file fsm_internals.h.

Function Documentation

fsm_get_avail()

uint8 fsm_get_avail	(	Page	page,
		int	slot
	)

Definition at line 122 of file fsmpage.c.

{
    FSMPage     fsmpage = (FSMPage) PageGetContents(page);
 
    Assert(slot < LeafNodesPerPage);
 
    return fsmpage->fp_nodes[NonLeafNodesPerPage + slot];
}

References Assert(), FSMPageData::fp_nodes, LeafNodesPerPage, NonLeafNodesPerPage, and PageGetContents().

Referenced by fsm_vacuum_page(), and GetRecordedFreeSpace().

fsm_get_max_avail()

uint8 fsm_get_max_avail

(

Page

page

)

Definition at line 138 of file fsmpage.c.

{
    FSMPage     fsmpage = (FSMPage) PageGetContents(page);
 
    return fsmpage->fp_nodes[0];
}

References FSMPageData::fp_nodes, and PageGetContents().

Referenced by fsm_search(), and fsm_vacuum_page().

fsm_rebuild_page()

bool fsm_rebuild_page

(

Page

page

)

Definition at line 342 of file fsmpage.c.

{
    FSMPage     fsmpage = (FSMPage) PageGetContents(page);
    bool        changed = false;
    int         nodeno;
 
    /*
     * Start from the lowest non-leaf level, at last node, working our way
     * backwards, through all non-leaf nodes at all levels, up to the root.
     */
    for (nodeno = NonLeafNodesPerPage - 1; nodeno >= 0; nodeno--)
    {
        int         lchild = leftchild(nodeno);
        int         rchild = lchild + 1;
        uint8       newvalue = 0;
 
        /* The first few nodes we examine might have zero or one child. */
        if (lchild < NodesPerPage)
            newvalue = fsmpage->fp_nodes[lchild];
 
        if (rchild < NodesPerPage)
            newvalue = Max(newvalue,
                           fsmpage->fp_nodes[rchild]);
 
        if (fsmpage->fp_nodes[nodeno] != newvalue)
        {
            fsmpage->fp_nodes[nodeno] = newvalue;
            changed = true;
        }
    }
 
    return changed;
}

References FSMPageData::fp_nodes, leftchild, Max, NodesPerPage, NonLeafNodesPerPage, and PageGetContents().

Referenced by fsm_search_avail(), fsm_set_avail(), and fsm_truncate_avail().

fsm_search_avail()

int fsm_search_avail	(	Buffer	buf,
		uint8	minvalue,
		bool	advancenext,
		bool	exclusive_lock_held
	)

Definition at line 158 of file fsmpage.c.

{
    Page        page = BufferGetPage(buf);
    FSMPage     fsmpage = (FSMPage) PageGetContents(page);
    int         nodeno;
    int         target;
    uint16      slot;
 
restart:
 
    /*
     * Check the root first, and exit quickly if there's no leaf with enough
     * free space
     */
    if (fsmpage->fp_nodes[0] < minvalue)
        return -1;
 
    /*
     * Start search using fp_next_slot.  It's just a hint, so check that it's
     * sane.  (This also handles wrapping around when the prior call returned
     * the last slot on the page.)
     */
    target = fsmpage->fp_next_slot;
    if (target < 0 || target >= LeafNodesPerPage)
        target = 0;
    target += NonLeafNodesPerPage;
 
    /*----------
     * Start the search from the target slot.  At every step, move one
     * node to the right, then climb up to the parent.  Stop when we reach
     * a node with enough free space (as we must, since the root has enough
     * space).
     *
     * The idea is to gradually expand our "search triangle", that is, all
     * nodes covered by the current node, and to be sure we search to the
     * right from the start point.  At the first step, only the target slot
     * is examined.  When we move up from a left child to its parent, we are
     * adding the right-hand subtree of that parent to the search triangle.
     * When we move right then up from a right child, we are dropping the
     * current search triangle (which we know doesn't contain any suitable
     * page) and instead looking at the next-larger-size triangle to its
     * right.  So we never look left from our original start point, and at
     * each step the size of the search triangle doubles, ensuring it takes
     * only log2(N) work to search N pages.
     *
     * The "move right" operation will wrap around if it hits the right edge
     * of the tree, so the behavior is still good if we start near the right.
     * Note also that the move-and-climb behavior ensures that we can't end
     * up on one of the missing nodes at the right of the leaf level.
     *
     * For example, consider this tree:
     *
     *         7
     *     7       6
     *   5   7   6   5
     *  4 5 5 7 2 6 5 2
     *              T
     *
     * Assume that the target node is the node indicated by the letter T,
     * and we're searching for a node with value of 6 or higher. The search
     * begins at T. At the first iteration, we move to the right, then to the
     * parent, arriving at the rightmost 5. At the second iteration, we move
     * to the right, wrapping around, then climb up, arriving at the 7 on the
     * third level.  7 satisfies our search, so we descend down to the bottom,
     * following the path of sevens.  This is in fact the first suitable page
     * to the right of (allowing for wraparound) our start point.
     *----------
     */
    nodeno = target;
    while (nodeno > 0)
    {
        if (fsmpage->fp_nodes[nodeno] >= minvalue)
            break;
 
        /*
         * Move to the right, wrapping around on same level if necessary, then
         * climb up.
         */
        nodeno = parentof(rightneighbor(nodeno));
    }
 
    /*
     * We're now at a node with enough free space, somewhere in the middle of
     * the tree. Descend to the bottom, following a path with enough free
     * space, preferring to move left if there's a choice.
     */
    while (nodeno < NonLeafNodesPerPage)
    {
        int         childnodeno = leftchild(nodeno);
 
        if (childnodeno < NodesPerPage &&
            fsmpage->fp_nodes[childnodeno] >= minvalue)
        {
            nodeno = childnodeno;
            continue;
        }
        childnodeno++;          /* point to right child */
        if (childnodeno < NodesPerPage &&
            fsmpage->fp_nodes[childnodeno] >= minvalue)
        {
            nodeno = childnodeno;
        }
        else
        {
            /*
             * Oops. The parent node promised that either left or right child
             * has enough space, but neither actually did. This can happen in
             * case of a "torn page", IOW if we crashed earlier while writing
             * the page to disk, and only part of the page made it to disk.
             *
             * Fix the corruption and restart.
             */
            RelFileLocator rlocator;
            ForkNumber  forknum;
            BlockNumber blknum;
 
            BufferGetTag(buf, &rlocator, &forknum, &blknum);
            elog(DEBUG1, "fixing corrupt FSM block %u, relation %u/%u/%u",
                 blknum, rlocator.spcOid, rlocator.dbOid, rlocator.relNumber);
 
            /* make sure we hold an exclusive lock */
            if (!exclusive_lock_held)
            {
                LockBuffer(buf, BUFFER_LOCK_UNLOCK);
                LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
                exclusive_lock_held = true;
            }
            fsm_rebuild_page(page);
            MarkBufferDirtyHint(buf, false);
            goto restart;
        }
    }
 
    /* We're now at the bottom level, at a node with enough space. */
    slot = nodeno - NonLeafNodesPerPage;
 
    /*
     * Update the next-target pointer. Note that we do this even if we're only
     * holding a shared lock, on the grounds that it's better to use a shared
     * lock and get a garbled next pointer every now and then, than take the
     * concurrency hit of an exclusive lock.
     *
     * Wrap-around is handled at the beginning of this function.
     */
    fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);
 
    return slot;
}

References buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage(), BufferGetTag(), RelFileLocator::dbOid, DEBUG1, elog, FSMPageData::fp_next_slot, FSMPageData::fp_nodes, fsm_rebuild_page(), LeafNodesPerPage, leftchild, LockBuffer(), MarkBufferDirtyHint(), NodesPerPage, NonLeafNodesPerPage, PageGetContents(), parentof, RelFileLocator::relNumber, rightneighbor(), and RelFileLocator::spcOid.

Referenced by fsm_search(), and fsm_set_and_search().

fsm_set_avail()

bool fsm_set_avail	(	Page	page,
		int	slot,
		uint8	value
	)

Definition at line 63 of file fsmpage.c.

{
    int         nodeno = NonLeafNodesPerPage + slot;
    FSMPage     fsmpage = (FSMPage) PageGetContents(page);
    uint8       oldvalue;
 
    Assert(slot < LeafNodesPerPage);
 
    oldvalue = fsmpage->fp_nodes[nodeno];
 
    /* If the value hasn't changed, we don't need to do anything */
    if (oldvalue == value && value <= fsmpage->fp_nodes[0])
        return false;
 
    fsmpage->fp_nodes[nodeno] = value;
 
    /*
     * Propagate up, until we hit the root or a node that doesn't need to be
     * updated.
     */
    do
    {
        uint8       newvalue = 0;
        int         lchild;
        int         rchild;
 
        nodeno = parentof(nodeno);
        lchild = leftchild(nodeno);
        rchild = lchild + 1;
 
        newvalue = fsmpage->fp_nodes[lchild];
        if (rchild < NodesPerPage)
            newvalue = Max(newvalue,
                           fsmpage->fp_nodes[rchild]);
 
        oldvalue = fsmpage->fp_nodes[nodeno];
        if (oldvalue == newvalue)
            break;
 
        fsmpage->fp_nodes[nodeno] = newvalue;
    } while (nodeno > 0);
 
    /*
     * sanity check: if the new value is (still) higher than the value at the
     * top, the tree is corrupt.  If so, rebuild.
     */
    if (value > fsmpage->fp_nodes[0])
        fsm_rebuild_page(page);
 
    return true;
}

References Assert(), FSMPageData::fp_nodes, fsm_rebuild_page(), LeafNodesPerPage, leftchild, Max, NodesPerPage, NonLeafNodesPerPage, PageGetContents(), parentof, and value.

Referenced by fsm_search(), fsm_set_and_search(), fsm_vacuum_page(), and XLogRecordPageWithFreeSpace().

fsm_truncate_avail()

bool fsm_truncate_avail	(	Page	page,
		int	nslots
	)

Definition at line 313 of file fsmpage.c.

{
    FSMPage     fsmpage = (FSMPage) PageGetContents(page);
    uint8      *ptr;
    bool        changed = false;
 
    Assert(nslots >= 0 && nslots < LeafNodesPerPage);
 
    /* Clear all truncated leaf nodes */
    ptr = &fsmpage->fp_nodes[NonLeafNodesPerPage + nslots];
    for (; ptr < &fsmpage->fp_nodes[NodesPerPage]; ptr++)
    {
        if (*ptr != 0)
            changed = true;
        *ptr = 0;
    }
 
    /* Fix upper nodes. */
    if (changed)
        fsm_rebuild_page(page);
 
    return changed;
}

References Assert(), FSMPageData::fp_nodes, fsm_rebuild_page(), LeafNodesPerPage, NodesPerPage, NonLeafNodesPerPage, and PageGetContents().

Referenced by FreeSpaceMapPrepareTruncateRel().