PostgreSQL Source Code  git master
freespace.c File Reference
#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"
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)
 
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 (RelFileNode rnode, 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

◆ FSM_CAT_STEP

#define FSM_CAT_STEP   (BLCKSZ / FSM_CATEGORIES)

◆ FSM_CATEGORIES

#define FSM_CATEGORIES   256

Definition at line 63 of file freespace.c.

◆ FSM_ROOT_LEVEL

#define FSM_ROOT_LEVEL   (FSM_TREE_DEPTH - 1)

Definition at line 76 of file freespace.c.

Referenced by fsm_get_parent(), and fsm_search().

◆ FSM_TREE_DEPTH

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

Definition at line 74 of file freespace.c.

Referenced by fsm_logical_to_physical().

◆ MaxFSMRequestSize

#define MaxFSMRequestSize   MaxHeapTupleSize

Function Documentation

◆ FreeSpaceMapPrepareTruncateRel()

BlockNumber FreeSpaceMapPrepareTruncateRel ( Relation  rel,
BlockNumber  nblocks 
)

Definition at line 261 of file freespace.c.

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(), RelationData::rd_smgr, RelationNeedsWAL, RelationOpenSmgr, smgrexists(), smgrnblocks(), START_CRIT_SECTION, UnlockReleaseBuffer(), and XLogHintBitIsNeeded.

Referenced by RelationTruncate(), and smgr_redo().

262 {
263  BlockNumber new_nfsmblocks;
264  FSMAddress first_removed_address;
265  uint16 first_removed_slot;
266  Buffer buf;
267 
268  RelationOpenSmgr(rel);
269 
270  /*
271  * If no FSM has been created yet for this relation, there's nothing to
272  * truncate.
273  */
274  if (!smgrexists(rel->rd_smgr, FSM_FORKNUM))
275  return InvalidBlockNumber;
276 
277  /* Get the location in the FSM of the first removed heap block */
278  first_removed_address = fsm_get_location(nblocks, &first_removed_slot);
279 
280  /*
281  * Zero out the tail of the last remaining FSM page. If the slot
282  * representing the first removed heap block is at a page boundary, as the
283  * first slot on the FSM page that first_removed_address points to, we can
284  * just truncate that page altogether.
285  */
286  if (first_removed_slot > 0)
287  {
288  buf = fsm_readbuf(rel, first_removed_address, false);
289  if (!BufferIsValid(buf))
290  return InvalidBlockNumber; /* nothing to do; the FSM was already
291  * smaller */
293 
294  /* NO EREPORT(ERROR) from here till changes are logged */
296 
297  fsm_truncate_avail(BufferGetPage(buf), first_removed_slot);
298 
299  /*
300  * Truncation of a relation is WAL-logged at a higher-level, and we
301  * will be called at WAL replay. But if checksums are enabled, we need
302  * to still write a WAL record to protect against a torn page, if the
303  * page is flushed to disk before the truncation WAL record. We cannot
304  * use MarkBufferDirtyHint here, because that will not dirty the page
305  * during recovery.
306  */
307  MarkBufferDirty(buf);
309  log_newpage_buffer(buf, false);
310 
312 
313  UnlockReleaseBuffer(buf);
314 
315  new_nfsmblocks = fsm_logical_to_physical(first_removed_address) + 1;
316  }
317  else
318  {
319  new_nfsmblocks = fsm_logical_to_physical(first_removed_address);
320  if (smgrnblocks(rel->rd_smgr, FSM_FORKNUM) <= new_nfsmblocks)
321  return InvalidBlockNumber; /* nothing to do; the FSM was already
322  * smaller */
323  }
324 
325  return new_nfsmblocks;
326 }
bool fsm_truncate_avail(Page page, int nslots)
Definition: fsmpage.c:313
XLogRecPtr log_newpage_buffer(Buffer buffer, bool page_std)
Definition: xloginsert.c:1014
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1468
struct SMgrRelationData * rd_smgr
Definition: rel.h:57
bool InRecovery
Definition: xlog.c:204
#define END_CRIT_SECTION()
Definition: miscadmin.h:134
#define START_CRIT_SECTION()
Definition: miscadmin.h:132
uint32 BlockNumber
Definition: block.h:31
bool smgrexists(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:247
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:98
#define RelationOpenSmgr(relation)
Definition: rel.h:513
unsigned short uint16
Definition: c.h:366
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3506
static char * buf
Definition: pg_test_fsync.c:67
static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot)
Definition: freespace.c:468
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3722
BlockNumber smgrnblocks(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:538
#define InvalidBlockNumber
Definition: block.h:33
static BlockNumber fsm_logical_to_physical(FSMAddress addr)
Definition: freespace.c:432
#define BufferIsValid(bufnum)
Definition: bufmgr.h:123
#define RelationNeedsWAL(relation)
Definition: rel.h:562
static Buffer fsm_readbuf(Relation rel, FSMAddress addr, bool extend)
Definition: freespace.c:531
int Buffer
Definition: buf.h:23
#define XLogHintBitIsNeeded()
Definition: xlog.h:202

◆ FreeSpaceMapVacuum()

void FreeSpaceMapVacuum ( Relation  rel)

Definition at line 335 of file freespace.c.

References fsm_vacuum_page(), and InvalidBlockNumber.

Referenced by brin_vacuum_scan(), and IndexFreeSpaceMapVacuum().

336 {
337  bool dummy;
338 
339  /* Recursively scan the tree, starting at the root */
340  (void) fsm_vacuum_page(rel, FSM_ROOT_ADDRESS,
342  &dummy);
343 }
uint32 BlockNumber
Definition: block.h:31
static uint8 fsm_vacuum_page(Relation rel, FSMAddress addr, BlockNumber start, BlockNumber end, bool *eof)
Definition: freespace.c:787
static const FSMAddress FSM_ROOT_ADDRESS
Definition: freespace.c:90
#define InvalidBlockNumber
Definition: block.h:33

◆ FreeSpaceMapVacuumRange()

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

Definition at line 354 of file freespace.c.

References fsm_vacuum_page().

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

355 {
356  bool dummy;
357 
358  /* Recursively scan the tree, starting at the root */
359  if (end > start)
360  (void) fsm_vacuum_page(rel, FSM_ROOT_ADDRESS, start, end, &dummy);
361 }
static uint8 fsm_vacuum_page(Relation rel, FSMAddress addr, BlockNumber start, BlockNumber end, bool *eof)
Definition: freespace.c:787
static const FSMAddress FSM_ROOT_ADDRESS
Definition: freespace.c:90

◆ fsm_extend()

static void fsm_extend ( Relation  rel,
BlockNumber  fsm_nblocks 
)
static

Definition at line 601 of file freespace.c.

References PGAlignedBlock::data, ExclusiveLock, FSM_FORKNUM, InvalidBlockNumber, LockRelationForExtension(), PageInit(), PageSetChecksumInplace(), RelationData::rd_smgr, RelationOpenSmgr, SMgrRelationData::smgr_fsm_nblocks, smgrcreate(), smgrexists(), smgrextend(), smgrnblocks(), and UnlockRelationForExtension().

Referenced by fsm_readbuf().

602 {
603  BlockNumber fsm_nblocks_now;
604  PGAlignedBlock pg;
605 
606  PageInit((Page) pg.data, BLCKSZ, 0);
607 
608  /*
609  * We use the relation extension lock to lock out other backends trying to
610  * extend the FSM at the same time. It also locks out extension of the
611  * main fork, unnecessarily, but extending the FSM happens seldom enough
612  * that it doesn't seem worthwhile to have a separate lock tag type for
613  * it.
614  *
615  * Note that another backend might have extended or created the relation
616  * by the time we get the lock.
617  */
619 
620  /* Might have to re-open if a cache flush happened */
621  RelationOpenSmgr(rel);
622 
623  /*
624  * Create the FSM file first if it doesn't exist. If smgr_fsm_nblocks is
625  * positive then it must exist, no need for an smgrexists call.
626  */
627  if ((rel->rd_smgr->smgr_fsm_nblocks == 0 ||
630  smgrcreate(rel->rd_smgr, FSM_FORKNUM, false);
631 
632  fsm_nblocks_now = smgrnblocks(rel->rd_smgr, FSM_FORKNUM);
633 
634  while (fsm_nblocks_now < fsm_nblocks)
635  {
636  PageSetChecksumInplace((Page) pg.data, fsm_nblocks_now);
637 
638  smgrextend(rel->rd_smgr, FSM_FORKNUM, fsm_nblocks_now,
639  pg.data, false);
640  fsm_nblocks_now++;
641  }
642 
643  /* Update local cache with the up-to-date size */
644  rel->rd_smgr->smgr_fsm_nblocks = fsm_nblocks_now;
645 
647 }
void smgrcreate(SMgrRelation reln, ForkNumber forknum, bool isRedo)
Definition: smgr.c:333
#define ExclusiveLock
Definition: lockdefs.h:44
struct SMgrRelationData * rd_smgr
Definition: rel.h:57
uint32 BlockNumber
Definition: block.h:31
BlockNumber smgr_fsm_nblocks
Definition: smgr.h:55
bool smgrexists(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:247
#define RelationOpenSmgr(relation)
Definition: rel.h:513
char data[BLCKSZ]
Definition: c.h:1104
void LockRelationForExtension(Relation relation, LOCKMODE lockmode)
Definition: lmgr.c:402
void UnlockRelationForExtension(Relation relation, LOCKMODE lockmode)
Definition: lmgr.c:452
BlockNumber smgrnblocks(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:538
#define InvalidBlockNumber
Definition: block.h:33
void PageSetChecksumInplace(Page page, BlockNumber blkno)
Definition: bufpage.c:1194
void smgrextend(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer, bool skipFsync)
Definition: smgr.c:462
Pointer Page
Definition: bufpage.h:78
void PageInit(Page page, Size pageSize, Size specialSize)
Definition: bufpage.c:42

◆ fsm_get_child()

static FSMAddress fsm_get_child ( FSMAddress  parent,
uint16  slot 
)
static

Definition at line 512 of file freespace.c.

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

Referenced by fsm_search(), and fsm_vacuum_page().

513 {
514  FSMAddress child;
515 
516  Assert(parent.level > FSM_BOTTOM_LEVEL);
517 
518  child.level = parent.level - 1;
519  child.logpageno = parent.logpageno * SlotsPerFSMPage + slot;
520 
521  return child;
522 }
#define SlotsPerFSMPage
Definition: fsm_internals.h:61
int logpageno
Definition: freespace.c:86
#define FSM_BOTTOM_LEVEL
Definition: freespace.c:77
int level
Definition: freespace.c:85
#define Assert(condition)
Definition: c.h:738

◆ fsm_get_heap_blk()

static BlockNumber fsm_get_heap_blk ( FSMAddress  addr,
uint16  slot 
)
static

Definition at line 483 of file freespace.c.

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

Referenced by fsm_search(), and RecordAndGetPageWithFreeSpace().

484 {
485  Assert(addr.level == FSM_BOTTOM_LEVEL);
486  return ((unsigned int) addr.logpageno) * SlotsPerFSMPage + slot;
487 }
#define SlotsPerFSMPage
Definition: fsm_internals.h:61
int logpageno
Definition: freespace.c:86
#define FSM_BOTTOM_LEVEL
Definition: freespace.c:77
int level
Definition: freespace.c:85
#define Assert(condition)
Definition: c.h:738

◆ fsm_get_location()

static FSMAddress fsm_get_location ( BlockNumber  heapblk,
uint16 slot 
)
static

Definition at line 468 of file freespace.c.

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

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

469 {
470  FSMAddress addr;
471 
472  addr.level = FSM_BOTTOM_LEVEL;
473  addr.logpageno = heapblk / SlotsPerFSMPage;
474  *slot = heapblk % SlotsPerFSMPage;
475 
476  return addr;
477 }
#define SlotsPerFSMPage
Definition: fsm_internals.h:61
int logpageno
Definition: freespace.c:86
#define FSM_BOTTOM_LEVEL
Definition: freespace.c:77
int level
Definition: freespace.c:85

◆ fsm_get_parent()

static FSMAddress fsm_get_parent ( FSMAddress  child,
uint16 slot 
)
static

Definition at line 494 of file freespace.c.

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

Referenced by fsm_search(), and fsm_vacuum_page().

495 {
496  FSMAddress parent;
497 
498  Assert(child.level < FSM_ROOT_LEVEL);
499 
500  parent.level = child.level + 1;
501  parent.logpageno = child.logpageno / SlotsPerFSMPage;
502  *slot = child.logpageno % SlotsPerFSMPage;
503 
504  return parent;
505 }
#define SlotsPerFSMPage
Definition: fsm_internals.h:61
int logpageno
Definition: freespace.c:86
#define FSM_ROOT_LEVEL
Definition: freespace.c:76
int level
Definition: freespace.c:85
#define Assert(condition)
Definition: c.h:738

◆ fsm_logical_to_physical()

static BlockNumber fsm_logical_to_physical ( FSMAddress  addr)
static

Definition at line 432 of file freespace.c.

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

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

433 {
434  BlockNumber pages;
435  int leafno;
436  int l;
437 
438  /*
439  * Calculate the logical page number of the first leaf page below the
440  * given page.
441  */
442  leafno = addr.logpageno;
443  for (l = 0; l < addr.level; l++)
444  leafno *= SlotsPerFSMPage;
445 
446  /* Count upper level nodes required to address the leaf page */
447  pages = 0;
448  for (l = 0; l < FSM_TREE_DEPTH; l++)
449  {
450  pages += leafno + 1;
451  leafno /= SlotsPerFSMPage;
452  }
453 
454  /*
455  * If the page we were asked for wasn't at the bottom level, subtract the
456  * additional lower level pages we counted above.
457  */
458  pages -= addr.level;
459 
460  /* Turn the page count into 0-based block number */
461  return pages - 1;
462 }
#define SlotsPerFSMPage
Definition: fsm_internals.h:61
int logpageno
Definition: freespace.c:86
uint32 BlockNumber
Definition: block.h:31
int level
Definition: freespace.c:85
#define FSM_TREE_DEPTH
Definition: freespace.c:74

◆ fsm_readbuf()

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

Definition at line 531 of file freespace.c.

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, RelationData::rd_smgr, ReadBufferExtended(), RelationOpenSmgr, SMgrRelationData::smgr_fsm_nblocks, smgrexists(), and smgrnblocks().

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

532 {
533  BlockNumber blkno = fsm_logical_to_physical(addr);
534  Buffer buf;
535 
536  RelationOpenSmgr(rel);
537 
538  /*
539  * If we haven't cached the size of the FSM yet, check it first. Also
540  * recheck if the requested block seems to be past end, since our cached
541  * value might be stale. (We send smgr inval messages on truncation, but
542  * not on extension.)
543  */
545  blkno >= rel->rd_smgr->smgr_fsm_nblocks)
546  {
547  if (smgrexists(rel->rd_smgr, FSM_FORKNUM))
549  FSM_FORKNUM);
550  else
551  rel->rd_smgr->smgr_fsm_nblocks = 0;
552  }
553 
554  /* Handle requests beyond EOF */
555  if (blkno >= rel->rd_smgr->smgr_fsm_nblocks)
556  {
557  if (extend)
558  fsm_extend(rel, blkno + 1);
559  else
560  return InvalidBuffer;
561  }
562 
563  /*
564  * Use ZERO_ON_ERROR mode, and initialize the page if necessary. The FSM
565  * information is not accurate anyway, so it's better to clear corrupt
566  * pages than error out. Since the FSM changes are not WAL-logged, the
567  * so-called torn page problem on crash can lead to pages with corrupt
568  * headers, for example.
569  *
570  * The initialize-the-page part is trickier than it looks, because of the
571  * possibility of multiple backends doing this concurrently, and our
572  * desire to not uselessly take the buffer lock in the normal path where
573  * the page is OK. We must take the lock to initialize the page, so
574  * recheck page newness after we have the lock, in case someone else
575  * already did it. Also, because we initially check PageIsNew with no
576  * lock, it's possible to fall through and return the buffer while someone
577  * else is still initializing the page (i.e., we might see pd_upper as set
578  * but other page header fields are still zeroes). This is harmless for
579  * callers that will take a buffer lock themselves, but some callers
580  * inspect the page without any lock at all. The latter is OK only so
581  * long as it doesn't depend on the page header having correct contents.
582  * Current usage is safe because PageGetContents() does not require that.
583  */
584  buf = ReadBufferExtended(rel, FSM_FORKNUM, blkno, RBM_ZERO_ON_ERROR, NULL);
585  if (PageIsNew(BufferGetPage(buf)))
586  {
588  if (PageIsNew(BufferGetPage(buf)))
589  PageInit(BufferGetPage(buf), BLCKSZ, 0);
591  }
592  return buf;
593 }
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:96
struct SMgrRelationData * rd_smgr
Definition: rel.h:57
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:652
#define InvalidBuffer
Definition: buf.h:25
uint32 BlockNumber
Definition: block.h:31
BlockNumber smgr_fsm_nblocks
Definition: smgr.h:55
bool smgrexists(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:247
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:98
#define RelationOpenSmgr(relation)
Definition: rel.h:513
static char * buf
Definition: pg_test_fsync.c:67
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3722
static void fsm_extend(Relation rel, BlockNumber fsm_nblocks)
Definition: freespace.c:601
BlockNumber smgrnblocks(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:538
#define InvalidBlockNumber
Definition: block.h:33
static BlockNumber fsm_logical_to_physical(FSMAddress addr)
Definition: freespace.c:432
#define PageIsNew(page)
Definition: bufpage.h:229
int Buffer
Definition: buf.h:23
void PageInit(Page page, Size pageSize, Size specialSize)
Definition: bufpage.c:42

◆ fsm_search()

static BlockNumber fsm_search ( Relation  rel,
uint8  min_cat 
)
static

Definition at line 689 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_ADDRESS, FSM_ROOT_LEVEL, fsm_search_avail(), fsm_set_and_search(), InvalidBlockNumber, FSMAddress::level, LockBuffer(), and UnlockReleaseBuffer().

Referenced by GetPageWithFreeSpace(), and RecordAndGetPageWithFreeSpace().

690 {
691  int restarts = 0;
693 
694  for (;;)
695  {
696  int slot;
697  Buffer buf;
698  uint8 max_avail = 0;
699 
700  /* Read the FSM page. */
701  buf = fsm_readbuf(rel, addr, false);
702 
703  /* Search within the page */
704  if (BufferIsValid(buf))
705  {
707  slot = fsm_search_avail(buf, min_cat,
708  (addr.level == FSM_BOTTOM_LEVEL),
709  false);
710  if (slot == -1)
711  max_avail = fsm_get_max_avail(BufferGetPage(buf));
712  UnlockReleaseBuffer(buf);
713  }
714  else
715  slot = -1;
716 
717  if (slot != -1)
718  {
719  /*
720  * Descend the tree, or return the found block if we're at the
721  * bottom.
722  */
723  if (addr.level == FSM_BOTTOM_LEVEL)
724  return fsm_get_heap_blk(addr, slot);
725 
726  addr = fsm_get_child(addr, slot);
727  }
728  else if (addr.level == FSM_ROOT_LEVEL)
729  {
730  /*
731  * At the root, failure means there's no page with enough free
732  * space in the FSM. Give up.
733  */
734  return InvalidBlockNumber;
735  }
736  else
737  {
738  uint16 parentslot;
739  FSMAddress parent;
740 
741  /*
742  * At lower level, failure can happen if the value in the upper-
743  * level node didn't reflect the value on the lower page. Update
744  * the upper node, to avoid falling into the same trap again, and
745  * start over.
746  *
747  * There's a race condition here, if another backend updates this
748  * page right after we release it, and gets the lock on the parent
749  * page before us. We'll then update the parent page with the now
750  * stale information we had. It's OK, because it should happen
751  * rarely, and will be fixed by the next vacuum.
752  */
753  parent = fsm_get_parent(addr, &parentslot);
754  fsm_set_and_search(rel, parent, parentslot, max_avail, 0);
755 
756  /*
757  * If the upper pages are badly out of date, we might need to loop
758  * quite a few times, updating them as we go. Any inconsistencies
759  * should eventually be corrected and the loop should end. Looping
760  * indefinitely is nevertheless scary, so provide an emergency
761  * valve.
762  */
763  if (restarts++ > 10000)
764  return InvalidBlockNumber;
765 
766  /* Start search all over from the root */
767  addr = FSM_ROOT_ADDRESS;
768  }
769  }
770 }
uint8 fsm_get_max_avail(Page page)
Definition: fsmpage.c:138
#define FSM_BOTTOM_LEVEL
Definition: freespace.c:77
static FSMAddress fsm_get_parent(FSMAddress child, uint16 *slot)
Definition: freespace.c:494
unsigned char uint8
Definition: c.h:365
static BlockNumber fsm_get_heap_blk(FSMAddress addr, uint16 slot)
Definition: freespace.c:483
static FSMAddress fsm_get_child(FSMAddress parent, uint16 slot)
Definition: freespace.c:512
static const FSMAddress FSM_ROOT_ADDRESS
Definition: freespace.c:90
unsigned short uint16
Definition: c.h:366
#define FSM_ROOT_LEVEL
Definition: freespace.c:76
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3506
int level
Definition: freespace.c:85
static char * buf
Definition: pg_test_fsync.c:67
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3722
static int fsm_set_and_search(Relation rel, FSMAddress addr, uint16 slot, uint8 newValue, uint8 minValue)
Definition: freespace.c:657
#define InvalidBlockNumber
Definition: block.h:33
#define BufferIsValid(bufnum)
Definition: bufmgr.h:123
static Buffer fsm_readbuf(Relation rel, FSMAddress addr, bool extend)
Definition: freespace.c:531
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:97
int Buffer
Definition: buf.h:23
int fsm_search_avail(Buffer buf, uint8 minvalue, bool advancenext, bool exclusive_lock_held)
Definition: fsmpage.c:158

◆ fsm_set_and_search()

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

Definition at line 657 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().

659 {
660  Buffer buf;
661  Page page;
662  int newslot = -1;
663 
664  buf = fsm_readbuf(rel, addr, true);
666 
667  page = BufferGetPage(buf);
668 
669  if (fsm_set_avail(page, slot, newValue))
670  MarkBufferDirtyHint(buf, false);
671 
672  if (minValue != 0)
673  {
674  /* Search while we still hold the lock */
675  newslot = fsm_search_avail(buf, minValue,
676  addr.level == FSM_BOTTOM_LEVEL,
677  true);
678  }
679 
680  UnlockReleaseBuffer(buf);
681 
682  return newslot;
683 }
#define FSM_BOTTOM_LEVEL
Definition: freespace.c:77
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:3553
bool fsm_set_avail(Page page, int slot, uint8 value)
Definition: fsmpage.c:63
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:98
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3506
int level
Definition: freespace.c:85
static char * buf
Definition: pg_test_fsync.c:67
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3722
static Buffer fsm_readbuf(Relation rel, FSMAddress addr, bool extend)
Definition: freespace.c:531
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:78
int fsm_search_avail(Buffer buf, uint8 minvalue, bool advancenext, bool exclusive_lock_held)
Definition: fsmpage.c:158

◆ fsm_space_avail_to_cat()

static uint8 fsm_space_avail_to_cat ( Size  avail)
static

Definition at line 369 of file freespace.c.

References Assert, FSM_CAT_STEP, and MaxFSMRequestSize.

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

370 {
371  int cat;
372 
373  Assert(avail < BLCKSZ);
374 
375  if (avail >= MaxFSMRequestSize)
376  return 255;
377 
378  cat = avail / FSM_CAT_STEP;
379 
380  /*
381  * The highest category, 255, is reserved for MaxFSMRequestSize bytes or
382  * more.
383  */
384  if (cat > 254)
385  cat = 254;
386 
387  return (uint8) cat;
388 }
unsigned char uint8
Definition: c.h:365
#define FSM_CAT_STEP
Definition: freespace.c:64
#define Assert(condition)
Definition: c.h:738
#define MaxFSMRequestSize
Definition: freespace.c:65

◆ fsm_space_cat_to_avail()

static Size fsm_space_cat_to_avail ( uint8  cat)
static

Definition at line 395 of file freespace.c.

References FSM_CAT_STEP, and MaxFSMRequestSize.

Referenced by GetRecordedFreeSpace().

396 {
397  /* The highest category represents exactly MaxFSMRequestSize bytes. */
398  if (cat == 255)
399  return MaxFSMRequestSize;
400  else
401  return cat * FSM_CAT_STEP;
402 }
#define FSM_CAT_STEP
Definition: freespace.c:64
#define MaxFSMRequestSize
Definition: freespace.c:65

◆ fsm_space_needed_to_cat()

static uint8 fsm_space_needed_to_cat ( Size  needed)
static

Definition at line 409 of file freespace.c.

References elog, ERROR, FSM_CAT_STEP, and MaxFSMRequestSize.

Referenced by GetPageWithFreeSpace(), and RecordAndGetPageWithFreeSpace().

410 {
411  int cat;
412 
413  /* Can't ask for more space than the highest category represents */
414  if (needed > MaxFSMRequestSize)
415  elog(ERROR, "invalid FSM request size %zu", needed);
416 
417  if (needed == 0)
418  return 1;
419 
420  cat = (needed + FSM_CAT_STEP - 1) / FSM_CAT_STEP;
421 
422  if (cat > 255)
423  cat = 255;
424 
425  return (uint8) cat;
426 }
unsigned char uint8
Definition: c.h:365
#define FSM_CAT_STEP
Definition: freespace.c:64
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:214
#define MaxFSMRequestSize
Definition: freespace.c:65

◆ fsm_vacuum_page()

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

Definition at line 787 of file freespace.c.

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

790 {
791  Buffer buf;
792  Page page;
793  uint8 max_avail;
794 
795  /* Read the page if it exists, or return EOF */
796  buf = fsm_readbuf(rel, addr, false);
797  if (!BufferIsValid(buf))
798  {
799  *eof_p = true;
800  return 0;
801  }
802  else
803  *eof_p = false;
804 
805  page = BufferGetPage(buf);
806 
807  /*
808  * If we're above the bottom level, recurse into children, and fix the
809  * information stored about them at this level.
810  */
811  if (addr.level > FSM_BOTTOM_LEVEL)
812  {
813  FSMAddress fsm_start,
814  fsm_end;
815  uint16 fsm_start_slot,
816  fsm_end_slot;
817  int slot,
818  start_slot,
819  end_slot;
820  bool eof = false;
821 
822  /*
823  * Compute the range of slots we need to update on this page, given
824  * the requested range of heap blocks to consider. The first slot to
825  * update is the one covering the "start" block, and the last slot is
826  * the one covering "end - 1". (Some of this work will be duplicated
827  * in each recursive call, but it's cheap enough to not worry about.)
828  */
829  fsm_start = fsm_get_location(start, &fsm_start_slot);
830  fsm_end = fsm_get_location(end - 1, &fsm_end_slot);
831 
832  while (fsm_start.level < addr.level)
833  {
834  fsm_start = fsm_get_parent(fsm_start, &fsm_start_slot);
835  fsm_end = fsm_get_parent(fsm_end, &fsm_end_slot);
836  }
837  Assert(fsm_start.level == addr.level);
838 
839  if (fsm_start.logpageno == addr.logpageno)
840  start_slot = fsm_start_slot;
841  else if (fsm_start.logpageno > addr.logpageno)
842  start_slot = SlotsPerFSMPage; /* shouldn't get here... */
843  else
844  start_slot = 0;
845 
846  if (fsm_end.logpageno == addr.logpageno)
847  end_slot = fsm_end_slot;
848  else if (fsm_end.logpageno > addr.logpageno)
849  end_slot = SlotsPerFSMPage - 1;
850  else
851  end_slot = -1; /* shouldn't get here... */
852 
853  for (slot = start_slot; slot <= end_slot; slot++)
854  {
855  int child_avail;
856 
858 
859  /* After we hit end-of-file, just clear the rest of the slots */
860  if (!eof)
861  child_avail = fsm_vacuum_page(rel, fsm_get_child(addr, slot),
862  start, end,
863  &eof);
864  else
865  child_avail = 0;
866 
867  /* Update information about the child */
868  if (fsm_get_avail(page, slot) != child_avail)
869  {
871  fsm_set_avail(page, slot, child_avail);
872  MarkBufferDirtyHint(buf, false);
874  }
875  }
876  }
877 
878  /* Now get the maximum value on the page, to return to caller */
879  max_avail = fsm_get_max_avail(page);
880 
881  /*
882  * Reset the next slot pointer. This encourages the use of low-numbered
883  * pages, increasing the chances that a later vacuum can truncate the
884  * relation. We don't bother with a lock here, nor with marking the page
885  * dirty if it wasn't already, since this is just a hint.
886  */
887  ((FSMPage) PageGetContents(page))->fp_next_slot = 0;
888 
889  ReleaseBuffer(buf);
890 
891  return max_avail;
892 }
#define SlotsPerFSMPage
Definition: fsm_internals.h:61
int logpageno
Definition: freespace.c:86
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:96
uint8 fsm_get_max_avail(Page page)
Definition: fsmpage.c:138
#define FSM_BOTTOM_LEVEL
Definition: freespace.c:77
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:3553
static FSMAddress fsm_get_parent(FSMAddress child, uint16 *slot)
Definition: freespace.c:494
bool fsm_set_avail(Page page, int slot, uint8 value)
Definition: fsmpage.c:63
unsigned char uint8
Definition: c.h:365
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3483
static uint8 fsm_vacuum_page(Relation rel, FSMAddress addr, BlockNumber start, BlockNumber end, bool *eof)
Definition: freespace.c:787
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:98
static FSMAddress fsm_get_child(FSMAddress parent, uint16 slot)
Definition: freespace.c:512
unsigned short uint16
Definition: c.h:366
int level
Definition: freespace.c:85
FSMPageData * FSMPage
Definition: fsm_internals.h:45
static char * buf
Definition: pg_test_fsync.c:67
static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot)
Definition: freespace.c:468
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
#define PageGetContents(page)
Definition: bufpage.h:246
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3722
#define Assert(condition)
Definition: c.h:738
#define BufferIsValid(bufnum)
Definition: bufmgr.h:123
uint8 fsm_get_avail(Page page, int slot)
Definition: fsmpage.c:122
static Buffer fsm_readbuf(Relation rel, FSMAddress addr, bool extend)
Definition: freespace.c:531
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:78

◆ GetPageWithFreeSpace()

BlockNumber GetPageWithFreeSpace ( Relation  rel,
Size  spaceNeeded 
)

Definition at line 132 of file freespace.c.

References fsm_search(), and fsm_space_needed_to_cat().

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

133 {
134  uint8 min_cat = fsm_space_needed_to_cat(spaceNeeded);
135 
136  return fsm_search(rel, min_cat);
137 }
unsigned char uint8
Definition: c.h:365
static uint8 fsm_space_needed_to_cat(Size needed)
Definition: freespace.c:409
static BlockNumber fsm_search(Relation rel, uint8 min_cat)
Definition: freespace.c:689

◆ GetRecordedFreeSpace()

Size GetRecordedFreeSpace ( Relation  rel,
BlockNumber  heapBlk 
)

Definition at line 230 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 lazy_scan_heap(), pg_freespace(), and statapprox_heap().

231 {
232  FSMAddress addr;
233  uint16 slot;
234  Buffer buf;
235  uint8 cat;
236 
237  /* Get the location of the FSM byte representing the heap block */
238  addr = fsm_get_location(heapBlk, &slot);
239 
240  buf = fsm_readbuf(rel, addr, false);
241  if (!BufferIsValid(buf))
242  return 0;
243  cat = fsm_get_avail(BufferGetPage(buf), slot);
244  ReleaseBuffer(buf);
245 
246  return fsm_space_cat_to_avail(cat);
247 }
unsigned char uint8
Definition: c.h:365
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3483
unsigned short uint16
Definition: c.h:366
static Size fsm_space_cat_to_avail(uint8 cat)
Definition: freespace.c:395
static char * buf
Definition: pg_test_fsync.c:67
static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot)
Definition: freespace.c:468
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
#define BufferIsValid(bufnum)
Definition: bufmgr.h:123
uint8 fsm_get_avail(Page page, int slot)
Definition: fsmpage.c:122
static Buffer fsm_readbuf(Relation rel, FSMAddress addr, bool extend)
Definition: freespace.c:531
int Buffer
Definition: buf.h:23

◆ RecordAndGetPageWithFreeSpace()

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

Definition at line 149 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 brin_getinsertbuffer(), and RelationGetBufferForTuple().

151 {
152  int old_cat = fsm_space_avail_to_cat(oldSpaceAvail);
153  int search_cat = fsm_space_needed_to_cat(spaceNeeded);
154  FSMAddress addr;
155  uint16 slot;
156  int search_slot;
157 
158  /* Get the location of the FSM byte representing the heap block */
159  addr = fsm_get_location(oldPage, &slot);
160 
161  search_slot = fsm_set_and_search(rel, addr, slot, old_cat, search_cat);
162 
163  /*
164  * If fsm_set_and_search found a suitable new block, return that.
165  * Otherwise, search as usual.
166  */
167  if (search_slot != -1)
168  return fsm_get_heap_blk(addr, search_slot);
169  else
170  return fsm_search(rel, search_cat);
171 }
static BlockNumber fsm_get_heap_blk(FSMAddress addr, uint16 slot)
Definition: freespace.c:483
unsigned short uint16
Definition: c.h:366
static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot)
Definition: freespace.c:468
static uint8 fsm_space_avail_to_cat(Size avail)
Definition: freespace.c:369
static uint8 fsm_space_needed_to_cat(Size needed)
Definition: freespace.c:409
static int fsm_set_and_search(Relation rel, FSMAddress addr, uint16 slot, uint8 newValue, uint8 minValue)
Definition: freespace.c:657
static BlockNumber fsm_search(Relation rel, uint8 min_cat)
Definition: freespace.c:689

◆ RecordPageWithFreeSpace()

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

Definition at line 181 of file freespace.c.

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_vacuum_heap(), RecordFreeIndexPage(), RecordUsedIndexPage(), RelationAddExtraBlocks(), and terminate_brin_buildstate().

182 {
183  int new_cat = fsm_space_avail_to_cat(spaceAvail);
184  FSMAddress addr;
185  uint16 slot;
186 
187  /* Get the location of the FSM byte representing the heap block */
188  addr = fsm_get_location(heapBlk, &slot);
189 
190  fsm_set_and_search(rel, addr, slot, new_cat, 0);
191 }
unsigned short uint16
Definition: c.h:366
static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot)
Definition: freespace.c:468
static uint8 fsm_space_avail_to_cat(Size avail)
Definition: freespace.c:369
static int fsm_set_and_search(Relation rel, FSMAddress addr, uint16 slot, uint8 newValue, uint8 minValue)
Definition: freespace.c:657

◆ XLogRecordPageWithFreeSpace()

void XLogRecordPageWithFreeSpace ( RelFileNode  rnode,
BlockNumber  heapBlk,
Size  spaceAvail 
)

Definition at line 198 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(), heap_xlog_update(), and heap_xlog_visible().

200 {
201  int new_cat = fsm_space_avail_to_cat(spaceAvail);
202  FSMAddress addr;
203  uint16 slot;
204  BlockNumber blkno;
205  Buffer buf;
206  Page page;
207 
208  /* Get the location of the FSM byte representing the heap block */
209  addr = fsm_get_location(heapBlk, &slot);
210  blkno = fsm_logical_to_physical(addr);
211 
212  /* If the page doesn't exist already, extend */
215 
216  page = BufferGetPage(buf);
217  if (PageIsNew(page))
218  PageInit(page, BLCKSZ, 0);
219 
220  if (fsm_set_avail(page, slot, new_cat))
221  MarkBufferDirtyHint(buf, false);
222  UnlockReleaseBuffer(buf);
223 }
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:3553
bool fsm_set_avail(Page page, int slot, uint8 value)
Definition: fsmpage.c:63
Buffer XLogReadBufferExtended(RelFileNode rnode, ForkNumber forknum, BlockNumber blkno, ReadBufferMode mode)
Definition: xlogutils.c:442
uint32 BlockNumber
Definition: block.h:31
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:98
unsigned short uint16
Definition: c.h:366
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3506
static char * buf
Definition: pg_test_fsync.c:67
static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot)
Definition: freespace.c:468
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
static uint8 fsm_space_avail_to_cat(Size avail)
Definition: freespace.c:369
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3722
static BlockNumber fsm_logical_to_physical(FSMAddress addr)
Definition: freespace.c:432
#define PageIsNew(page)
Definition: bufpage.h:229
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:78
void PageInit(Page page, Size pageSize, Size specialSize)
Definition: bufpage.c:42

Variable Documentation

◆ FSM_ROOT_ADDRESS

const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0}
static

Definition at line 90 of file freespace.c.

Referenced by fsm_search().