#include "postgres.h"
#include "access/htup_details.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"
Go to the source code of this file.
#define FSM_BOTTOM_LEVEL 0 |
Definition at line 77 of file freespace.c.
Referenced by fsm_get_child(), fsm_get_heap_blk(), fsm_search(), fsm_set_and_search(), and fsm_vacuum_page().
#define FSM_CAT_STEP (BLCKSZ / FSM_CATEGORIES) |
Definition at line 64 of file freespace.c.
Referenced by fsm_space_needed_to_cat().
#define FSM_CATEGORIES 256 |
Definition at line 63 of file freespace.c.
#define FSM_ROOT_LEVEL (FSM_TREE_DEPTH - 1) |
Definition at line 76 of file freespace.c.
Referenced by fsm_get_parent(), and fsm_search().
#define FSM_TREE_DEPTH ((SlotsPerFSMPage >= 1626) ? 3 : 4) |
Definition at line 74 of file freespace.c.
#define MaxFSMRequestSize MaxHeapTupleSize |
Definition at line 65 of file freespace.c.
Referenced by fsm_space_avail_to_cat(), and fsm_space_needed_to_cat().
void FreeSpaceMapTruncateRel | ( | Relation | rel, | |
BlockNumber | nblocks | |||
) |
Definition at line 257 of file freespace.c.
References buf, BUFFER_LOCK_EXCLUSIVE, BufferGetPage, BufferIsValid, FSM_FORKNUM, fsm_get_location(), fsm_logical_to_physical(), fsm_readbuf(), fsm_truncate_avail(), LockBuffer(), MarkBufferDirtyHint(), RelationData::rd_smgr, RelationOpenSmgr, SMgrRelationData::smgr_fsm_nblocks, smgrexists(), smgrnblocks(), smgrtruncate(), and UnlockReleaseBuffer().
Referenced by RelationTruncate(), and smgr_redo().
{ BlockNumber new_nfsmblocks; FSMAddress first_removed_address; uint16 first_removed_slot; Buffer buf; RelationOpenSmgr(rel); /* * If no FSM has been created yet for this relation, there's nothing to * truncate. */ if (!smgrexists(rel->rd_smgr, FSM_FORKNUM)) return; /* 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; /* nothing to do; the FSM was already smaller */ LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE); fsm_truncate_avail(BufferGetPage(buf), first_removed_slot); MarkBufferDirtyHint(buf); UnlockReleaseBuffer(buf); new_nfsmblocks = fsm_logical_to_physical(first_removed_address) + 1; } else { new_nfsmblocks = fsm_logical_to_physical(first_removed_address); if (smgrnblocks(rel->rd_smgr, FSM_FORKNUM) <= new_nfsmblocks) return; /* nothing to do; the FSM was already smaller */ } /* Truncate the unused FSM pages, and send smgr inval message */ smgrtruncate(rel->rd_smgr, FSM_FORKNUM, new_nfsmblocks); /* * We might as well update the local smgr_fsm_nblocks setting. * smgrtruncate sent an smgr cache inval message, which will cause other * backends to invalidate their copy of smgr_fsm_nblocks, and this one too * at the next command boundary. But this ensures it isn't outright wrong * until then. */ if (rel->rd_smgr) rel->rd_smgr->smgr_fsm_nblocks = new_nfsmblocks; }
void FreeSpaceMapVacuum | ( | Relation | rel | ) |
Definition at line 319 of file freespace.c.
References fsm_vacuum_page().
Referenced by IndexFreeSpaceMapVacuum(), and lazy_vacuum_rel().
{ bool dummy; /* * Traverse the tree in depth-first order. The tree is stored physically * in depth-first order, so this should be pretty I/O efficient. */ fsm_vacuum_page(rel, FSM_ROOT_ADDRESS, &dummy); }
static void fsm_extend | ( | Relation | rel, | |
BlockNumber | fsm_nblocks | |||
) | [static] |
Definition at line 550 of file freespace.c.
References ExclusiveLock, FSM_FORKNUM, InvalidBlockNumber, LockRelationForExtension(), PageInit(), PageSetChecksumInplace(), palloc(), pfree(), RelationData::rd_smgr, RelationOpenSmgr, SMgrRelationData::smgr_fsm_nblocks, smgrcreate(), smgrexists(), smgrextend(), smgrnblocks(), and UnlockRelationForExtension().
Referenced by fsm_readbuf().
{ BlockNumber fsm_nblocks_now; Page pg; pg = (Page) palloc(BLCKSZ); PageInit(pg, 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); /* Might have to re-open if a cache flush happened */ RelationOpenSmgr(rel); /* * Create the FSM file first if it doesn't exist. If smgr_fsm_nblocks is * positive then it must exist, no need for an smgrexists call. */ if ((rel->rd_smgr->smgr_fsm_nblocks == 0 || rel->rd_smgr->smgr_fsm_nblocks == InvalidBlockNumber) && !smgrexists(rel->rd_smgr, FSM_FORKNUM)) smgrcreate(rel->rd_smgr, FSM_FORKNUM, false); fsm_nblocks_now = smgrnblocks(rel->rd_smgr, FSM_FORKNUM); while (fsm_nblocks_now < fsm_nblocks) { PageSetChecksumInplace(pg, fsm_nblocks_now); smgrextend(rel->rd_smgr, FSM_FORKNUM, fsm_nblocks_now, (char *) pg, false); fsm_nblocks_now++; } /* Update local cache with the up-to-date size */ rel->rd_smgr->smgr_fsm_nblocks = fsm_nblocks_now; UnlockRelationForExtension(rel, ExclusiveLock); pfree(pg); }
static FSMAddress fsm_get_child | ( | FSMAddress | parent, | |
uint16 | slot | |||
) | [static] |
Definition at line 480 of file freespace.c.
References Assert, FSM_BOTTOM_LEVEL, FSMAddress::level, FSMAddress::logpageno, and SlotsPerFSMPage.
Referenced by fsm_search(), and fsm_vacuum_page().
{ FSMAddress child; Assert(parent.level > FSM_BOTTOM_LEVEL); child.level = parent.level - 1; child.logpageno = parent.logpageno * SlotsPerFSMPage + slot; return child; }
static BlockNumber fsm_get_heap_blk | ( | FSMAddress | addr, | |
uint16 | slot | |||
) | [static] |
Definition at line 451 of file freespace.c.
References Assert, FSM_BOTTOM_LEVEL, FSMAddress::level, FSMAddress::logpageno, and SlotsPerFSMPage.
Referenced by fsm_search(), and RecordAndGetPageWithFreeSpace().
{ Assert(addr.level == FSM_BOTTOM_LEVEL); return ((unsigned int) addr.logpageno) * SlotsPerFSMPage + slot; }
static FSMAddress fsm_get_location | ( | BlockNumber | heapblk, | |
uint16 * | slot | |||
) | [static] |
Definition at line 436 of file freespace.c.
References FSMAddress::level, and FSMAddress::logpageno.
Referenced by FreeSpaceMapTruncateRel(), GetRecordedFreeSpace(), RecordAndGetPageWithFreeSpace(), RecordPageWithFreeSpace(), and XLogRecordPageWithFreeSpace().
{ FSMAddress addr; addr.level = FSM_BOTTOM_LEVEL; addr.logpageno = heapblk / SlotsPerFSMPage; *slot = heapblk % SlotsPerFSMPage; return addr; }
static FSMAddress fsm_get_parent | ( | FSMAddress | child, | |
uint16 * | slot | |||
) | [static] |
Definition at line 462 of file freespace.c.
References Assert, FSM_ROOT_LEVEL, FSMAddress::level, and FSMAddress::logpageno.
Referenced by fsm_search().
{ FSMAddress parent; Assert(child.level < FSM_ROOT_LEVEL); parent.level = child.level + 1; parent.logpageno = child.logpageno / SlotsPerFSMPage; *slot = child.logpageno % SlotsPerFSMPage; return parent; }
static BlockNumber fsm_logical_to_physical | ( | FSMAddress | addr | ) | [static] |
Definition at line 400 of file freespace.c.
References FSMAddress::level, FSMAddress::logpageno, and SlotsPerFSMPage.
Referenced by FreeSpaceMapTruncateRel(), fsm_readbuf(), and XLogRecordPageWithFreeSpace().
{ 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; }
static Buffer fsm_readbuf | ( | Relation | rel, | |
FSMAddress | addr, | |||
bool | extend | |||
) | [static] |
Definition at line 499 of file freespace.c.
References buf, BufferGetPage, fsm_extend(), FSM_FORKNUM, fsm_logical_to_physical(), InvalidBlockNumber, NULL, PageInit(), PageIsNew, RBM_ZERO_ON_ERROR, RelationData::rd_smgr, ReadBufferExtended(), RelationOpenSmgr, SMgrRelationData::smgr_fsm_nblocks, smgrexists(), and smgrnblocks().
Referenced by FreeSpaceMapTruncateRel(), fsm_search(), fsm_set_and_search(), fsm_vacuum_page(), and GetRecordedFreeSpace().
{ BlockNumber blkno = fsm_logical_to_physical(addr); Buffer buf; RelationOpenSmgr(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 (rel->rd_smgr->smgr_fsm_nblocks == InvalidBlockNumber || blkno >= rel->rd_smgr->smgr_fsm_nblocks) { if (smgrexists(rel->rd_smgr, FSM_FORKNUM)) rel->rd_smgr->smgr_fsm_nblocks = smgrnblocks(rel->rd_smgr, FSM_FORKNUM); else rel->rd_smgr->smgr_fsm_nblocks = 0; } /* Handle requests beyond EOF */ if (blkno >= rel->rd_smgr->smgr_fsm_nblocks) { 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. */ buf = ReadBufferExtended(rel, FSM_FORKNUM, blkno, RBM_ZERO_ON_ERROR, NULL); if (PageIsNew(BufferGetPage(buf))) PageInit(BufferGetPage(buf), BLCKSZ, 0); return buf; }
static BlockNumber fsm_search | ( | Relation | rel, | |
uint8 | min_cat | |||
) | [static] |
Definition at line 641 of file freespace.c.
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_LEVEL, fsm_search_avail(), fsm_set_and_search(), FSMAddress::level, LockBuffer(), and UnlockReleaseBuffer().
Referenced by GetPageWithFreeSpace(), and RecordAndGetPageWithFreeSpace().
{ 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; } } }
static int fsm_set_and_search | ( | Relation | rel, | |
FSMAddress | addr, | |||
uint16 | slot, | |||
uint8 | newValue, | |||
uint8 | minValue | |||
) | [static] |
Definition at line 609 of file freespace.c.
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().
{ 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); 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; }
Definition at line 336 of file freespace.c.
References Assert, and MaxFSMRequestSize.
Referenced by RecordAndGetPageWithFreeSpace(), RecordPageWithFreeSpace(), and XLogRecordPageWithFreeSpace().
{ 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; }
Definition at line 362 of file freespace.c.
Referenced by GetRecordedFreeSpace().
{ /* The highest category represents exactly MaxFSMRequestSize bytes. */ if (cat == 255) return MaxFSMRequestSize; else return cat * FSM_CAT_STEP; }
Definition at line 376 of file freespace.c.
References elog, ERROR, FSM_CAT_STEP, and MaxFSMRequestSize.
Referenced by GetPageWithFreeSpace(), and RecordAndGetPageWithFreeSpace().
{ int cat; /* Can't ask for more space than the highest category represents */ if (needed > MaxFSMRequestSize) elog(ERROR, "invalid FSM request size %lu", (unsigned long) needed); if (needed == 0) return 1; cat = (needed + FSM_CAT_STEP - 1) / FSM_CAT_STEP; if (cat > 255) cat = 255; return (uint8) cat; }
static uint8 fsm_vacuum_page | ( | Relation | rel, | |
FSMAddress | addr, | |||
bool * | eof | |||
) | [static] |
Definition at line 729 of file freespace.c.
References buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, BufferIsValid, CHECK_FOR_INTERRUPTS, FSM_BOTTOM_LEVEL, fsm_get_avail(), fsm_get_child(), fsm_get_max_avail(), fsm_readbuf(), fsm_set_avail(), FSMAddress::level, LockBuffer(), MarkBufferDirtyHint(), PageGetContents, and ReleaseBuffer().
Referenced by FreeSpaceMapVacuum().
{ 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); /* * Recurse into children, and fix the information stored about them at * this level. */ if (addr.level > FSM_BOTTOM_LEVEL) { int slot; bool eof = false; for (slot = 0; slot < SlotsPerFSMPage; 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), &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(BufferGetPage(buf), slot, child_avail); MarkBufferDirtyHint(buf); LockBuffer(buf, BUFFER_LOCK_UNLOCK); } } } max_avail = fsm_get_max_avail(BufferGetPage(buf)); /* * Reset the next slot pointer. This encourages the use of low-numbered * pages, increasing the chances that a later vacuum can truncate the * relation. */ ((FSMPage) PageGetContents(page))->fp_next_slot = 0; ReleaseBuffer(buf); return max_avail; }
BlockNumber GetPageWithFreeSpace | ( | Relation | rel, | |
Size | spaceNeeded | |||
) |
Definition at line 130 of file freespace.c.
References fsm_search(), and fsm_space_needed_to_cat().
Referenced by GetFreeIndexPage(), and RelationGetBufferForTuple().
{ uint8 min_cat = fsm_space_needed_to_cat(spaceNeeded); return fsm_search(rel, min_cat); }
Size GetRecordedFreeSpace | ( | Relation | rel, | |
BlockNumber | heapBlk | |||
) |
Definition at line 228 of file freespace.c.
References buf, BufferGetPage, BufferIsValid, fsm_get_avail(), fsm_get_location(), fsm_readbuf(), fsm_space_cat_to_avail(), and ReleaseBuffer().
Referenced by pg_freespace().
{ 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); }
BlockNumber RecordAndGetPageWithFreeSpace | ( | Relation | rel, | |
BlockNumber | oldPage, | |||
Size | oldSpaceAvail, | |||
Size | spaceNeeded | |||
) |
Definition at line 147 of file freespace.c.
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 RelationGetBufferForTuple().
{ 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); }
void RecordPageWithFreeSpace | ( | Relation | rel, | |
BlockNumber | heapBlk, | |||
Size | spaceAvail | |||
) |
Definition at line 179 of file freespace.c.
References fsm_get_location(), fsm_set_and_search(), and fsm_space_avail_to_cat().
Referenced by lazy_scan_heap(), lazy_vacuum_heap(), RecordFreeIndexPage(), and RecordUsedIndexPage().
{ 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); }
void XLogRecordPageWithFreeSpace | ( | RelFileNode | rnode, | |
BlockNumber | heapBlk, | |||
Size | spaceAvail | |||
) |
Definition at line 196 of file freespace.c.
References buf, BUFFER_LOCK_EXCLUSIVE, BufferGetPage, FSM_FORKNUM, fsm_get_location(), fsm_logical_to_physical(), fsm_set_avail(), fsm_space_avail_to_cat(), LockBuffer(), MarkBufferDirtyHint(), PageInit(), PageIsNew, RBM_ZERO_ON_ERROR, UnlockReleaseBuffer(), and XLogReadBufferExtended().
Referenced by heap_xlog_clean(), heap_xlog_insert(), heap_xlog_multi_insert(), and heap_xlog_update().
{ 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(rnode, FSM_FORKNUM, blkno, RBM_ZERO_ON_ERROR); 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); UnlockReleaseBuffer(buf); }
const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0} [static] |
Definition at line 90 of file freespace.c.