tidstore.c File Reference

#include "postgres.h"
#include "access/tidstore.h"
#include "miscadmin.h"
#include "nodes/bitmapset.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"
#include "lib/radixtree.h"

Include dependency graph for tidstore.c:

Go to the source code of this file.

Data Structures
struct	BlocktableEntry
struct	TidStore
struct	TidStoreIter

Macros
#define	WORDNUM(x)   ((x) / BITS_PER_BITMAPWORD)
#define	BITNUM(x)   ((x) % BITS_PER_BITMAPWORD)
#define	WORDS_PER_PAGE(n)   ((n) / BITS_PER_BITMAPWORD + 1)
#define	NUM_FULL_OFFSETS   ((sizeof(uintptr_t) - sizeof(uint8) - sizeof(int8)) / sizeof(OffsetNumber))
#define	MAX_OFFSET_IN_BITMAP   Min(BITS_PER_BITMAPWORD * PG_INT8_MAX - 1, MaxOffsetNumber)
#define	MaxBlocktableEntrySize
#define	RT_PREFIX   local_ts
#define	RT_SCOPE   static
#define	RT_DECLARE
#define	RT_DEFINE
#define	RT_VALUE_TYPE   BlocktableEntry
#define	RT_VARLEN_VALUE_SIZE(page)
#define	RT_RUNTIME_EMBEDDABLE_VALUE
#define	RT_PREFIX   shared_ts
#define	RT_SHMEM
#define	RT_SCOPE   static
#define	RT_DECLARE
#define	RT_DEFINE
#define	RT_VALUE_TYPE   BlocktableEntry
#define	RT_VARLEN_VALUE_SIZE(page)
#define	RT_RUNTIME_EMBEDDABLE_VALUE
#define	TidStoreIsShared(ts)   ((ts)->area != NULL)

Typedefs
typedef struct BlocktableEntry	BlocktableEntry

Functions
static void	tidstore_iter_extract_tids (TidStoreIter *iter, BlockNumber blkno, BlocktableEntry *page)
TidStore *	TidStoreCreateLocal (size_t max_bytes, bool insert_only)
TidStore *	TidStoreCreateShared (size_t max_bytes, int tranche_id)
TidStore *	TidStoreAttach (dsa_handle area_handle, dsa_pointer handle)
void	TidStoreDetach (TidStore *ts)
void	TidStoreLockExclusive (TidStore *ts)
void	TidStoreLockShare (TidStore *ts)
void	TidStoreUnlock (TidStore *ts)
void	TidStoreDestroy (TidStore *ts)
void	TidStoreSetBlockOffsets (TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, int num_offsets)
bool	TidStoreIsMember (TidStore *ts, ItemPointer tid)
TidStoreIter *	TidStoreBeginIterate (TidStore *ts)
TidStoreIterResult *	TidStoreIterateNext (TidStoreIter *iter)
void	TidStoreEndIterate (TidStoreIter *iter)
size_t	TidStoreMemoryUsage (TidStore *ts)
dsa_area *	TidStoreGetDSA (TidStore *ts)
dsa_pointer	TidStoreGetHandle (TidStore *ts)

Macro Definition Documentation

BITNUM

#define BITNUM

(

x

)

((x) % BITS_PER_BITMAPWORD)

Definition at line 32 of file tidstore.c.

MAX_OFFSET_IN_BITMAP

#define MAX_OFFSET_IN_BITMAP   Min(BITS_PER_BITMAPWORD * PG_INT8_MAX - 1, MaxOffsetNumber)

Definition at line 84 of file tidstore.c.

MaxBlocktableEntrySize

#define MaxBlocktableEntrySize

Value:

    offsetof(BlocktableEntry, words) + \
        (sizeof(bitmapword) * WORDS_PER_PAGE(MAX_OFFSET_IN_BITMAP))

Definition at line 86 of file tidstore.c.

NUM_FULL_OFFSETS

#define NUM_FULL_OFFSETS   ((sizeof(uintptr_t) - sizeof(uint8) - sizeof(int8)) / sizeof(OffsetNumber))

Definition at line 38 of file tidstore.c.

RT_DECLARE [1/2]

#define RT_DECLARE

Definition at line 104 of file tidstore.c.

RT_DECLARE [2/2]

#define RT_DECLARE

Definition at line 104 of file tidstore.c.

RT_DEFINE [1/2]

#define RT_DEFINE

Definition at line 105 of file tidstore.c.

RT_DEFINE [2/2]

#define RT_DEFINE

Definition at line 105 of file tidstore.c.

RT_PREFIX [1/2]

#define RT_PREFIX   local_ts

Definition at line 101 of file tidstore.c.

RT_PREFIX [2/2]

#define RT_PREFIX   shared_ts

Definition at line 101 of file tidstore.c.

RT_RUNTIME_EMBEDDABLE_VALUE [1/2]

#define RT_RUNTIME_EMBEDDABLE_VALUE

Definition at line 110 of file tidstore.c.

RT_RUNTIME_EMBEDDABLE_VALUE [2/2]

#define RT_RUNTIME_EMBEDDABLE_VALUE

Definition at line 110 of file tidstore.c.

RT_SCOPE [1/2]

#define RT_SCOPE   static

Definition at line 103 of file tidstore.c.

RT_SCOPE [2/2]

#define RT_SCOPE   static

Definition at line 103 of file tidstore.c.

RT_SHMEM

#define RT_SHMEM

Definition at line 102 of file tidstore.c.

RT_VALUE_TYPE [1/2]

#define RT_VALUE_TYPE   BlocktableEntry

Definition at line 106 of file tidstore.c.

RT_VALUE_TYPE [2/2]

#define RT_VALUE_TYPE   BlocktableEntry

Definition at line 106 of file tidstore.c.

RT_VARLEN_VALUE_SIZE [1/2]

#define RT_VARLEN_VALUE_SIZE

(

page

)

Value:

    (offsetof(BlocktableEntry, words) + \
    sizeof(bitmapword) * (page)->header.nwords)

Definition at line 107 of file tidstore.c.

RT_VARLEN_VALUE_SIZE [2/2]

#define RT_VARLEN_VALUE_SIZE

(

page

)

Value:

    (offsetof(BlocktableEntry, words) + \
    sizeof(bitmapword) * (page)->header.nwords)

Definition at line 107 of file tidstore.c.

TidStoreIsShared

#define TidStoreIsShared

(

ts

)

((ts)->area != NULL)

Definition at line 132 of file tidstore.c.

WORDNUM

#define WORDNUM

(

x

)

((x) / BITS_PER_BITMAPWORD)

Definition at line 31 of file tidstore.c.

WORDS_PER_PAGE

#define WORDS_PER_PAGE

(

n

)

((n) / BITS_PER_BITMAPWORD + 1)

Definition at line 35 of file tidstore.c.

Typedef Documentation

BlocktableEntry

typedef struct BlocktableEntry BlocktableEntry

Function Documentation

tidstore_iter_extract_tids()

static void tidstore_iter_extract_tids ( TidStoreIter *  iter, BlockNumber  blkno, BlocktableEntry *  page  )

static

Definition at line 580 of file tidstore.c.

{
    TidStoreIterResult *result = (&iter->output);
    int         wordnum;
 
    result->num_offsets = 0;
    result->blkno = blkno;
 
    if (page->header.nwords == 0)
    {
        /* we have offsets in the header */
        for (int i = 0; i < NUM_FULL_OFFSETS; i++)
        {
            if (page->header.full_offsets[i] != InvalidOffsetNumber)
                result->offsets[result->num_offsets++] = page->header.full_offsets[i];
        }
    }
    else
    {
        for (wordnum = 0; wordnum < page->header.nwords; wordnum++)
        {
            bitmapword  w = page->words[wordnum];
            int         off = wordnum * BITS_PER_BITMAPWORD;
 
            /* Make sure there is enough space to add offsets */
            if ((result->num_offsets + BITS_PER_BITMAPWORD) > result->max_offset)
            {
                result->max_offset *= 2;
                result->offsets = repalloc(result->offsets,
                                           sizeof(OffsetNumber) * result->max_offset);
            }
 
            while (w != 0)
            {
                if (w & 1)
                    result->offsets[result->num_offsets++] = (OffsetNumber) off;
                off++;
                w >>= 1;
            }
        }
    }
}

References BITS_PER_BITMAPWORD, TidStoreIterResult::blkno, BlocktableEntry::full_offsets, BlocktableEntry::header, i, InvalidOffsetNumber, TidStoreIterResult::max_offset, NUM_FULL_OFFSETS, TidStoreIterResult::num_offsets, BlocktableEntry::nwords, TidStoreIterResult::offsets, TidStoreIter::output, repalloc(), and BlocktableEntry::words.

Referenced by TidStoreIterateNext().

TidStoreAttach()

TidStore* TidStoreAttach	(	dsa_handle	area_handle,
		dsa_pointer	handle
	)

Definition at line 255 of file tidstore.c.

{
    TidStore   *ts;
    dsa_area   *area;
 
    Assert(area_handle != DSA_HANDLE_INVALID);
    Assert(DsaPointerIsValid(handle));
 
    /* create per-backend state */
    ts = palloc0(sizeof(TidStore));
 
    area = dsa_attach(area_handle);
 
    /* Find the shared the shared radix tree */
    ts->tree.shared = shared_ts_attach(area, handle);
    ts->area = area;
 
    return ts;
}

References TidStore::area, Assert, dsa_attach(), DSA_HANDLE_INVALID, DsaPointerIsValid, palloc0(), TidStore::shared, and TidStore::tree.

Referenced by parallel_vacuum_main().

TidStoreBeginIterate()

TidStoreIter* TidStoreBeginIterate

(

TidStore *

ts

)

Definition at line 482 of file tidstore.c.

{
    TidStoreIter *iter;
 
    iter = palloc0(sizeof(TidStoreIter));
    iter->ts = ts;
 
    /*
     * We start with an array large enough to contain at least the offsets
     * from one completely full bitmap element.
     */
    iter->output.max_offset = 2 * BITS_PER_BITMAPWORD;
    iter->output.offsets = palloc(sizeof(OffsetNumber) * iter->output.max_offset);
 
    if (TidStoreIsShared(ts))
        iter->tree_iter.shared = shared_ts_begin_iterate(ts->tree.shared);
    else
        iter->tree_iter.local = local_ts_begin_iterate(ts->tree.local);
 
    return iter;
}

References BITS_PER_BITMAPWORD, TidStore::local, TidStoreIter::local, TidStoreIterResult::max_offset, TidStoreIterResult::offsets, TidStoreIter::output, palloc(), palloc0(), TidStore::shared, TidStoreIter::shared, TidStoreIsShared, TidStore::tree, TidStoreIter::tree_iter, and TidStoreIter::ts.

Referenced by check_set_block_offsets(), and lazy_vacuum_heap_rel().

TidStoreCreateLocal()

TidStore* TidStoreCreateLocal	(	size_t	max_bytes,
		bool	insert_only
	)

Definition at line 165 of file tidstore.c.

{
    TidStore   *ts;
    size_t      initBlockSize = ALLOCSET_DEFAULT_INITSIZE;
    size_t      minContextSize = ALLOCSET_DEFAULT_MINSIZE;
    size_t      maxBlockSize = ALLOCSET_DEFAULT_MAXSIZE;
 
    ts = palloc0(sizeof(TidStore));
    ts->context = CurrentMemoryContext;
 
    /* choose the maxBlockSize to be no larger than 1/16 of max_bytes */
    while (16 * maxBlockSize > max_bytes)
        maxBlockSize >>= 1;
 
    if (maxBlockSize < ALLOCSET_DEFAULT_INITSIZE)
        maxBlockSize = ALLOCSET_DEFAULT_INITSIZE;
 
    /* Create a memory context for the TID storage */
    if (insert_only)
    {
        ts->rt_context = BumpContextCreate(CurrentMemoryContext,
                                           "TID storage",
                                           minContextSize,
                                           initBlockSize,
                                           maxBlockSize);
    }
    else
    {
        ts->rt_context = AllocSetContextCreate(CurrentMemoryContext,
                                               "TID storage",
                                               minContextSize,
                                               initBlockSize,
                                               maxBlockSize);
    }
 
    ts->tree.local = local_ts_create(ts->rt_context);
 
    return ts;
}

References ALLOCSET_DEFAULT_INITSIZE, ALLOCSET_DEFAULT_MAXSIZE, ALLOCSET_DEFAULT_MINSIZE, AllocSetContextCreate, BumpContextCreate(), TidStore::context, CurrentMemoryContext, TidStore::local, palloc0(), TidStore::rt_context, and TidStore::tree.

Referenced by dead_items_alloc(), dead_items_reset(), and test_create().

TidStoreCreateShared()

TidStore* TidStoreCreateShared	(	size_t	max_bytes,
		int	tranche_id
	)

Definition at line 213 of file tidstore.c.

{
    TidStore   *ts;
    dsa_area   *area;
    size_t      dsa_init_size = DSA_DEFAULT_INIT_SEGMENT_SIZE;
    size_t      dsa_max_size = DSA_MAX_SEGMENT_SIZE;
 
    ts = palloc0(sizeof(TidStore));
    ts->context = CurrentMemoryContext;
 
    ts->rt_context = AllocSetContextCreate(CurrentMemoryContext,
                                           "TID storage meta data",
                                           ALLOCSET_SMALL_SIZES);
 
    /*
     * Choose the initial and maximum DSA segment sizes to be no longer than
     * 1/8 of max_bytes.
     */
    while (8 * dsa_max_size > max_bytes)
        dsa_max_size >>= 1;
 
    if (dsa_max_size < DSA_MIN_SEGMENT_SIZE)
        dsa_max_size = DSA_MIN_SEGMENT_SIZE;
 
    if (dsa_init_size > dsa_max_size)
        dsa_init_size = dsa_max_size;
 
    area = dsa_create_ext(tranche_id, dsa_init_size, dsa_max_size);
    ts->tree.shared = shared_ts_create(ts->rt_context, area,
                                       tranche_id);
    ts->area = area;
 
    return ts;
}

References ALLOCSET_SMALL_SIZES, AllocSetContextCreate, TidStore::area, TidStore::context, CurrentMemoryContext, dsa_create_ext(), DSA_DEFAULT_INIT_SEGMENT_SIZE, DSA_MAX_SEGMENT_SIZE, DSA_MIN_SEGMENT_SIZE, palloc0(), TidStore::rt_context, TidStore::shared, and TidStore::tree.

Referenced by parallel_vacuum_init(), parallel_vacuum_reset_dead_items(), and test_create().

TidStoreDestroy()

void TidStoreDestroy

(

TidStore *

ts

)

Definition at line 328 of file tidstore.c.

{
    /* Destroy underlying radix tree */
    if (TidStoreIsShared(ts))
    {
        shared_ts_free(ts->tree.shared);
 
        dsa_detach(ts->area);
    }
    else
        local_ts_free(ts->tree.local);
 
    MemoryContextDelete(ts->rt_context);
 
    pfree(ts);
}

References TidStore::area, dsa_detach(), TidStore::local, MemoryContextDelete(), pfree(), TidStore::rt_context, TidStore::shared, TidStoreIsShared, and TidStore::tree.

Referenced by dead_items_reset(), parallel_vacuum_end(), parallel_vacuum_reset_dead_items(), and test_destroy().

TidStoreDetach()

void TidStoreDetach

(

TidStore *

ts

)

Definition at line 280 of file tidstore.c.

{
    Assert(TidStoreIsShared(ts));
 
    shared_ts_detach(ts->tree.shared);
    dsa_detach(ts->area);
 
    pfree(ts);
}

References TidStore::area, Assert, dsa_detach(), pfree(), TidStore::shared, TidStoreIsShared, and TidStore::tree.

Referenced by parallel_vacuum_main().

TidStoreEndIterate()

void TidStoreEndIterate

(

TidStoreIter *

iter

)

Definition at line 536 of file tidstore.c.

{
    if (TidStoreIsShared(iter->ts))
        shared_ts_end_iterate(iter->tree_iter.shared);
    else
        local_ts_end_iterate(iter->tree_iter.local);
 
    pfree(iter->output.offsets);
    pfree(iter);
}

References TidStoreIter::local, TidStoreIterResult::offsets, TidStoreIter::output, pfree(), TidStoreIter::shared, TidStoreIsShared, TidStoreIter::tree_iter, and TidStoreIter::ts.

Referenced by check_set_block_offsets(), and lazy_vacuum_heap_rel().

TidStoreGetDSA()

dsa_area* TidStoreGetDSA

(

TidStore *

ts

)

Definition at line 563 of file tidstore.c.

{
    Assert(TidStoreIsShared(ts));
 
    return ts->area;
}

References TidStore::area, Assert, and TidStoreIsShared.

Referenced by parallel_vacuum_init(), parallel_vacuum_reset_dead_items(), and test_create().

TidStoreGetHandle()

dsa_pointer TidStoreGetHandle

(

TidStore *

ts

)

Definition at line 571 of file tidstore.c.

{
    Assert(TidStoreIsShared(ts));
 
    return (dsa_pointer) shared_ts_get_handle(ts->tree.shared);
}

References Assert, TidStore::shared, TidStoreIsShared, and TidStore::tree.

Referenced by parallel_vacuum_init(), and parallel_vacuum_reset_dead_items().

TidStoreIsMember()

bool TidStoreIsMember	(	TidStore *	ts,
		ItemPointer	tid
	)

Definition at line 432 of file tidstore.c.

{
    int         wordnum;
    int         bitnum;
    BlocktableEntry *page;
    BlockNumber blk = ItemPointerGetBlockNumber(tid);
    OffsetNumber off = ItemPointerGetOffsetNumber(tid);
 
    if (TidStoreIsShared(ts))
        page = shared_ts_find(ts->tree.shared, blk);
    else
        page = local_ts_find(ts->tree.local, blk);
 
    /* no entry for the blk */
    if (page == NULL)
        return false;
 
    if (page->header.nwords == 0)
    {
        /* we have offsets in the header */
        for (int i = 0; i < NUM_FULL_OFFSETS; i++)
        {
            if (page->header.full_offsets[i] == off)
                return true;
        }
        return false;
    }
    else
    {
        wordnum = WORDNUM(off);
        bitnum = BITNUM(off);
 
        /* no bitmap for the off */
        if (wordnum >= page->header.nwords)
            return false;
 
        return (page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0;
    }
}

References BITNUM, BlocktableEntry::full_offsets, BlocktableEntry::header, i, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), TidStore::local, NUM_FULL_OFFSETS, BlocktableEntry::nwords, TidStore::shared, TidStoreIsShared, TidStore::tree, WORDNUM, and BlocktableEntry::words.

Referenced by check_set_block_offsets(), and vac_tid_reaped().

TidStoreIterateNext()

TidStoreIterResult* TidStoreIterateNext

(

TidStoreIter *

iter

)

Definition at line 511 of file tidstore.c.

{
    uint64      key;
    BlocktableEntry *page;
 
    if (TidStoreIsShared(iter->ts))
        page = shared_ts_iterate_next(iter->tree_iter.shared, &key);
    else
        page = local_ts_iterate_next(iter->tree_iter.local, &key);
 
    if (page == NULL)
        return NULL;
 
    /* Collect TIDs from the key-value pair */
    tidstore_iter_extract_tids(iter, (BlockNumber) key, page);
 
    return &(iter->output);
}

References sort-test::key, TidStoreIter::local, TidStoreIter::output, TidStoreIter::shared, tidstore_iter_extract_tids(), TidStoreIsShared, TidStoreIter::tree_iter, and TidStoreIter::ts.

Referenced by check_set_block_offsets(), and lazy_vacuum_heap_rel().

TidStoreLockExclusive()

void TidStoreLockExclusive

(

TidStore *

ts

)

Definition at line 298 of file tidstore.c.

{
    if (TidStoreIsShared(ts))
        shared_ts_lock_exclusive(ts->tree.shared);
}

References TidStore::shared, TidStoreIsShared, and TidStore::tree.

Referenced by do_set_block_offsets().

TidStoreLockShare()

void TidStoreLockShare

(

TidStore *

ts

)

Definition at line 305 of file tidstore.c.

{
    if (TidStoreIsShared(ts))
        shared_ts_lock_share(ts->tree.shared);
}

References TidStore::shared, TidStoreIsShared, and TidStore::tree.

Referenced by check_set_block_offsets().

TidStoreMemoryUsage()

size_t TidStoreMemoryUsage

(

TidStore *

ts

)

Definition at line 551 of file tidstore.c.

{
    if (TidStoreIsShared(ts))
        return shared_ts_memory_usage(ts->tree.shared);
    else
        return local_ts_memory_usage(ts->tree.local);
}

References TidStore::local, TidStore::shared, TidStoreIsShared, and TidStore::tree.

Referenced by dead_items_add(), lazy_scan_heap(), lazy_vacuum(), test_create(), and test_is_full().

TidStoreSetBlockOffsets()

void TidStoreSetBlockOffsets	(	TidStore *	ts,
		BlockNumber	blkno,
		OffsetNumber *	offsets,
		int	num_offsets
	)

Definition at line 356 of file tidstore.c.

{
    union
    {
        char        data[MaxBlocktableEntrySize];
        BlocktableEntry force_align_entry;
    }           data;
    BlocktableEntry *page = (BlocktableEntry *) data.data;
    bitmapword  word;
    int         wordnum;
    int         next_word_threshold;
    int         idx = 0;
 
    Assert(num_offsets > 0);
 
    /* Check if the given offset numbers are ordered */
    for (int i = 1; i < num_offsets; i++)
        Assert(offsets[i] > offsets[i - 1]);
 
    memset(page, 0, offsetof(BlocktableEntry, words));
 
    if (num_offsets <= NUM_FULL_OFFSETS)
    {
        for (int i = 0; i < num_offsets; i++)
        {
            OffsetNumber off = offsets[i];
 
            /* safety check to ensure we don't overrun bit array bounds */
            if (off == InvalidOffsetNumber || off > MAX_OFFSET_IN_BITMAP)
                elog(ERROR, "tuple offset out of range: %u", off);
 
            page->header.full_offsets[i] = off;
        }
 
        page->header.nwords = 0;
    }
    else
    {
        for (wordnum = 0, next_word_threshold = BITS_PER_BITMAPWORD;
             wordnum <= WORDNUM(offsets[num_offsets - 1]);
             wordnum++, next_word_threshold += BITS_PER_BITMAPWORD)
        {
            word = 0;
 
            while (idx < num_offsets)
            {
                OffsetNumber off = offsets[idx];
 
                /* safety check to ensure we don't overrun bit array bounds */
                if (off == InvalidOffsetNumber || off > MAX_OFFSET_IN_BITMAP)
                    elog(ERROR, "tuple offset out of range: %u", off);
 
                if (off >= next_word_threshold)
                    break;
 
                word |= ((bitmapword) 1 << BITNUM(off));
                idx++;
            }
 
            /* write out offset bitmap for this wordnum */
            page->words[wordnum] = word;
        }
 
        page->header.nwords = wordnum;
        Assert(page->header.nwords == WORDS_PER_PAGE(offsets[num_offsets - 1]));
    }
 
    if (TidStoreIsShared(ts))
        shared_ts_set(ts->tree.shared, blkno, page);
    else
        local_ts_set(ts->tree.local, blkno, page);
}

References Assert, BITNUM, BITS_PER_BITMAPWORD, data, elog, ERROR, BlocktableEntry::full_offsets, BlocktableEntry::header, i, idx(), InvalidOffsetNumber, TidStore::local, MAX_OFFSET_IN_BITMAP, MaxBlocktableEntrySize, NUM_FULL_OFFSETS, BlocktableEntry::nwords, TidStore::shared, TidStoreIsShared, TidStore::tree, word(), WORDNUM, BlocktableEntry::words, and WORDS_PER_PAGE.

Referenced by dead_items_add(), and do_set_block_offsets().

TidStoreUnlock()

void TidStoreUnlock

(

TidStore *

ts

)

Definition at line 312 of file tidstore.c.

{
    if (TidStoreIsShared(ts))
        shared_ts_unlock(ts->tree.shared);
}

References TidStore::shared, TidStoreIsShared, and TidStore::tree.

Referenced by check_set_block_offsets(), and do_set_block_offsets().