PostgreSQL Source Code  git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
tidbitmap.h File Reference
#include "storage/itemptr.h"
#include "utils/dsa.h"
Include dependency graph for tidbitmap.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  TBMIterateResult
 

Typedefs

typedef struct TIDBitmap TIDBitmap
 
typedef struct TBMIterator TBMIterator
 
typedef struct TBMSharedIterator TBMSharedIterator
 
typedef struct TBMIterateResult TBMIterateResult
 

Functions

TIDBitmaptbm_create (long maxbytes, dsa_area *dsa)
 
void tbm_free (TIDBitmap *tbm)
 
void tbm_free_shared_area (dsa_area *dsa, dsa_pointer dp)
 
void tbm_add_tuples (TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
 
void tbm_add_page (TIDBitmap *tbm, BlockNumber pageno)
 
void tbm_union (TIDBitmap *a, const TIDBitmap *b)
 
void tbm_intersect (TIDBitmap *a, const TIDBitmap *b)
 
bool tbm_is_empty (const TIDBitmap *tbm)
 
TBMIteratortbm_begin_iterate (TIDBitmap *tbm)
 
dsa_pointer tbm_prepare_shared_iterate (TIDBitmap *tbm)
 
TBMIterateResulttbm_iterate (TBMIterator *iterator)
 
TBMIterateResulttbm_shared_iterate (TBMSharedIterator *iterator)
 
void tbm_end_iterate (TBMIterator *iterator)
 
void tbm_end_shared_iterate (TBMSharedIterator *iterator)
 
TBMSharedIteratortbm_attach_shared_iterate (dsa_area *dsa, dsa_pointer dp)
 
long tbm_calculate_entries (double maxbytes)
 

Typedef Documentation

◆ TBMIterateResult

◆ TBMIterator

typedef struct TBMIterator TBMIterator

Definition at line 1 of file tidbitmap.h.

◆ TBMSharedIterator

Definition at line 1 of file tidbitmap.h.

◆ TIDBitmap

typedef struct TIDBitmap TIDBitmap

Definition at line 1 of file tidbitmap.h.

Function Documentation

◆ tbm_add_page()

void tbm_add_page ( TIDBitmap tbm,
BlockNumber  pageno 
)

Definition at line 443 of file tidbitmap.c.

444 {
445  /* Enter the page in the bitmap, or mark it lossy if already present */
446  tbm_mark_page_lossy(tbm, pageno);
447  /* If we went over the memory limit, lossify some more pages */
448  if (tbm->nentries > tbm->maxentries)
449  tbm_lossify(tbm);
450 }
int nentries
Definition: tidbitmap.c:155
int maxentries
Definition: tidbitmap.c:156
static void tbm_lossify(TIDBitmap *tbm)
Definition: tidbitmap.c:1355
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:1283

References TIDBitmap::maxentries, TIDBitmap::nentries, tbm_lossify(), and tbm_mark_page_lossy().

Referenced by bringetbitmap(), and gingetbitmap().

◆ tbm_add_tuples()

void tbm_add_tuples ( TIDBitmap tbm,
const ItemPointer  tids,
int  ntids,
bool  recheck 
)

Definition at line 377 of file tidbitmap.c.

379 {
381  PagetableEntry *page = NULL; /* only valid when currblk is valid */
382  int i;
383 
385  for (i = 0; i < ntids; i++)
386  {
389  int wordnum,
390  bitnum;
391 
392  /* safety check to ensure we don't overrun bit array bounds */
393  if (off < 1 || off > MAX_TUPLES_PER_PAGE)
394  elog(ERROR, "tuple offset out of range: %u", off);
395 
396  /*
397  * Look up target page unless we already did. This saves cycles when
398  * the input includes consecutive tuples on the same page, which is
399  * common enough to justify an extra test here.
400  */
401  if (blk != currblk)
402  {
403  if (tbm_page_is_lossy(tbm, blk))
404  page = NULL; /* remember page is lossy */
405  else
406  page = tbm_get_pageentry(tbm, blk);
407  currblk = blk;
408  }
409 
410  if (page == NULL)
411  continue; /* whole page is already marked */
412 
413  if (page->ischunk)
414  {
415  /* The page is a lossy chunk header, set bit for itself */
416  wordnum = bitnum = 0;
417  }
418  else
419  {
420  /* Page is exact, so set bit for individual tuple */
421  wordnum = WORDNUM(off - 1);
422  bitnum = BITNUM(off - 1);
423  }
424  page->words[wordnum] |= ((bitmapword) 1 << bitnum);
425  page->recheck |= recheck;
426 
427  if (tbm->nentries > tbm->maxentries)
428  {
429  tbm_lossify(tbm);
430  /* Page could have been converted to lossy, so force new lookup */
431  currblk = InvalidBlockNumber;
432  }
433  }
434 }
uint32 bitmapword
Definition: bitmapset.h:44
uint32 BlockNumber
Definition: block.h:31
#define InvalidBlockNumber
Definition: block.h:33
#define Assert(condition)
Definition: c.h:863
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
int i
Definition: isn.c:72
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
uint16 OffsetNumber
Definition: off.h:24
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:106
TBMIteratingState iterating
Definition: tidbitmap.c:159
#define MAX_TUPLES_PER_PAGE
Definition: tidbitmap.c:57
#define WORDNUM(x)
Definition: tidbitmap.c:78
@ TBM_NOT_ITERATING
Definition: tidbitmap.c:141
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:1249
#define BITNUM(x)
Definition: tidbitmap.c:79
static PagetableEntry * tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:1202

References Assert, BITNUM, elog, ERROR, i, InvalidBlockNumber, PagetableEntry::ischunk, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), TIDBitmap::iterating, MAX_TUPLES_PER_PAGE, TIDBitmap::maxentries, TIDBitmap::nentries, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), TBM_NOT_ITERATING, tbm_page_is_lossy(), WORDNUM, and PagetableEntry::words.

Referenced by blgetbitmap(), btgetbitmap(), collectMatchBitmap(), GinDataLeafPageGetItemsToTbm(), gingetbitmap(), ginPostingListDecodeAllSegmentsToTbm(), gistScanPage(), hashgetbitmap(), scanPendingInsert(), and storeBitmap().

◆ tbm_attach_shared_iterate()

TBMSharedIterator* tbm_attach_shared_iterate ( dsa_area dsa,
dsa_pointer  dp 
)

Definition at line 1461 of file tidbitmap.c.

1462 {
1463  TBMSharedIterator *iterator;
1464  TBMSharedIteratorState *istate;
1465 
1466  /*
1467  * Create the TBMSharedIterator struct, with enough trailing space to
1468  * serve the needs of the TBMIterateResult sub-struct.
1469  */
1470  iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator) +
1471  MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
1472 
1473  istate = (TBMSharedIteratorState *) dsa_get_address(dsa, dp);
1474 
1475  iterator->state = istate;
1476 
1477  iterator->ptbase = dsa_get_address(dsa, istate->pagetable);
1478 
1479  if (istate->npages)
1480  iterator->ptpages = dsa_get_address(dsa, istate->spages);
1481  if (istate->nchunks)
1482  iterator->ptchunks = dsa_get_address(dsa, istate->schunks);
1483 
1484  return iterator;
1485 }
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:942
void * palloc0(Size size)
Definition: mcxt.c:1347
dsa_pointer pagetable
Definition: tidbitmap.c:197
dsa_pointer spages
Definition: tidbitmap.c:198
dsa_pointer schunks
Definition: tidbitmap.c:199
TBMSharedIteratorState * state
Definition: tidbitmap.c:221
PTEntryArray * ptbase
Definition: tidbitmap.c:222
PTIterationArray * ptchunks
Definition: tidbitmap.c:224
PTIterationArray * ptpages
Definition: tidbitmap.c:223

References dsa_get_address(), MAX_TUPLES_PER_PAGE, TBMSharedIteratorState::nchunks, TBMSharedIteratorState::npages, TBMSharedIteratorState::pagetable, palloc0(), TBMSharedIterator::ptbase, TBMSharedIterator::ptchunks, TBMSharedIterator::ptpages, TBMSharedIteratorState::schunks, TBMSharedIteratorState::spages, and TBMSharedIterator::state.

Referenced by BitmapHeapNext().

◆ tbm_begin_iterate()

TBMIterator* tbm_begin_iterate ( TIDBitmap tbm)

Definition at line 689 of file tidbitmap.c.

690 {
691  TBMIterator *iterator;
692 
694 
695  /*
696  * Create the TBMIterator struct, with enough trailing space to serve the
697  * needs of the TBMIterateResult sub-struct.
698  */
699  iterator = (TBMIterator *) palloc(sizeof(TBMIterator) +
701  iterator->tbm = tbm;
702 
703  /*
704  * Initialize iteration pointers.
705  */
706  iterator->spageptr = 0;
707  iterator->schunkptr = 0;
708  iterator->schunkbit = 0;
709 
710  /*
711  * If we have a hashtable, create and fill the sorted page lists, unless
712  * we already did that for a previous iterator. Note that the lists are
713  * attached to the bitmap not the iterator, so they can be used by more
714  * than one iterator.
715  */
716  if (tbm->status == TBM_HASH && tbm->iterating == TBM_NOT_ITERATING)
717  {
718  pagetable_iterator i;
719  PagetableEntry *page;
720  int npages;
721  int nchunks;
722 
723  if (!tbm->spages && tbm->npages > 0)
724  tbm->spages = (PagetableEntry **)
726  tbm->npages * sizeof(PagetableEntry *));
727  if (!tbm->schunks && tbm->nchunks > 0)
728  tbm->schunks = (PagetableEntry **)
730  tbm->nchunks * sizeof(PagetableEntry *));
731 
732  npages = nchunks = 0;
733  pagetable_start_iterate(tbm->pagetable, &i);
734  while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
735  {
736  if (page->ischunk)
737  tbm->schunks[nchunks++] = page;
738  else
739  tbm->spages[npages++] = page;
740  }
741  Assert(npages == tbm->npages);
742  Assert(nchunks == tbm->nchunks);
743  if (npages > 1)
744  qsort(tbm->spages, npages, sizeof(PagetableEntry *),
746  if (nchunks > 1)
747  qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
749  }
750 
752 
753  return iterator;
754 }
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1181
void * palloc(Size size)
Definition: mcxt.c:1317
#define qsort(a, b, c, d)
Definition: port.h:447
int spageptr
Definition: tidbitmap.c:181
TIDBitmap * tbm
Definition: tidbitmap.c:180
int schunkbit
Definition: tidbitmap.c:183
int schunkptr
Definition: tidbitmap.c:182
struct pagetable_hash * pagetable
Definition: tidbitmap.c:154
PagetableEntry ** schunks
Definition: tidbitmap.c:164
MemoryContext mcxt
Definition: tidbitmap.c:152
int npages
Definition: tidbitmap.c:157
int nchunks
Definition: tidbitmap.c:158
TBMStatus status
Definition: tidbitmap.c:153
PagetableEntry ** spages
Definition: tidbitmap.c:163
@ TBM_ITERATING_SHARED
Definition: tidbitmap.c:143
@ TBM_ITERATING_PRIVATE
Definition: tidbitmap.c:142
@ TBM_HASH
Definition: tidbitmap.c:133
static int tbm_comparator(const void *left, const void *right)
Definition: tidbitmap.c:1424

References Assert, i, PagetableEntry::ischunk, TIDBitmap::iterating, MAX_TUPLES_PER_PAGE, TIDBitmap::mcxt, MemoryContextAlloc(), TIDBitmap::nchunks, TIDBitmap::npages, TIDBitmap::pagetable, palloc(), qsort, TBMIterator::schunkbit, TBMIterator::schunkptr, TIDBitmap::schunks, TBMIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMIterator::tbm, tbm_comparator(), TBM_HASH, TBM_ITERATING_PRIVATE, TBM_ITERATING_SHARED, and TBM_NOT_ITERATING.

Referenced by BitmapHeapNext(), and startScanEntry().

◆ tbm_calculate_entries()

long tbm_calculate_entries ( double  maxbytes)

Definition at line 1542 of file tidbitmap.c.

1543 {
1544  long nbuckets;
1545 
1546  /*
1547  * Estimate number of hashtable entries we can have within maxbytes. This
1548  * estimates the hash cost as sizeof(PagetableEntry), which is good enough
1549  * for our purpose. Also count an extra Pointer per entry for the arrays
1550  * created during iteration readout.
1551  */
1552  nbuckets = maxbytes /
1553  (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
1554  nbuckets = Min(nbuckets, INT_MAX - 1); /* safety limit */
1555  nbuckets = Max(nbuckets, 16); /* sanity limit */
1556 
1557  return nbuckets;
1558 }
#define Min(x, y)
Definition: c.h:1009
#define Max(x, y)
Definition: c.h:1003
char * Pointer
Definition: c.h:498
struct PagetableEntry PagetableEntry

References Max, and Min.

Referenced by compute_bitmap_pages(), and tbm_create().

◆ tbm_create()

TIDBitmap* tbm_create ( long  maxbytes,
dsa_area dsa 
)

Definition at line 266 of file tidbitmap.c.

267 {
268  TIDBitmap *tbm;
269 
270  /* Create the TIDBitmap struct and zero all its fields */
271  tbm = makeNode(TIDBitmap);
272 
273  tbm->mcxt = CurrentMemoryContext;
274  tbm->status = TBM_EMPTY;
275 
276  tbm->maxentries = (int) tbm_calculate_entries(maxbytes);
277  tbm->lossify_start = 0;
278  tbm->dsa = dsa;
281  tbm->ptpages = InvalidDsaPointer;
283 
284  return tbm;
285 }
#define InvalidDsaPointer
Definition: dsa.h:78
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
#define makeNode(_type_)
Definition: nodes.h:155
dsa_pointer ptpages
Definition: tidbitmap.c:167
dsa_pointer dsapagetableold
Definition: tidbitmap.c:166
uint32 lossify_start
Definition: tidbitmap.c:160
dsa_pointer ptchunks
Definition: tidbitmap.c:168
dsa_area * dsa
Definition: tidbitmap.c:169
dsa_pointer dsapagetable
Definition: tidbitmap.c:165
long tbm_calculate_entries(double maxbytes)
Definition: tidbitmap.c:1542
@ TBM_EMPTY
Definition: tidbitmap.c:131

References CurrentMemoryContext, TIDBitmap::dsa, TIDBitmap::dsapagetable, TIDBitmap::dsapagetableold, InvalidDsaPointer, TIDBitmap::lossify_start, makeNode, TIDBitmap::maxentries, TIDBitmap::mcxt, TIDBitmap::ptchunks, TIDBitmap::ptpages, TIDBitmap::status, tbm_calculate_entries(), and TBM_EMPTY.

Referenced by collectMatchBitmap(), MultiExecBitmapIndexScan(), and MultiExecBitmapOr().

◆ tbm_end_iterate()

void tbm_end_iterate ( TBMIterator iterator)

Definition at line 1146 of file tidbitmap.c.

1147 {
1148  pfree(iterator);
1149 }
void pfree(void *pointer)
Definition: mcxt.c:1521

References pfree().

Referenced by BitmapPrefetch(), entryGetItem(), ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), ginFreeScanKeys(), and startScanEntry().

◆ tbm_end_shared_iterate()

void tbm_end_shared_iterate ( TBMSharedIterator iterator)

Definition at line 1158 of file tidbitmap.c.

1159 {
1160  pfree(iterator);
1161 }

References pfree().

Referenced by BitmapPrefetch(), ExecEndBitmapHeapScan(), and ExecReScanBitmapHeapScan().

◆ tbm_free()

void tbm_free ( TIDBitmap tbm)

Definition at line 322 of file tidbitmap.c.

323 {
324  if (tbm->pagetable)
325  pagetable_destroy(tbm->pagetable);
326  if (tbm->spages)
327  pfree(tbm->spages);
328  if (tbm->schunks)
329  pfree(tbm->schunks);
330  pfree(tbm);
331 }

References TIDBitmap::pagetable, pfree(), TIDBitmap::schunks, and TIDBitmap::spages.

Referenced by ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), ginFreeScanKeys(), MultiExecBitmapAnd(), MultiExecBitmapOr(), and startScanEntry().

◆ tbm_free_shared_area()

void tbm_free_shared_area ( dsa_area dsa,
dsa_pointer  dp 
)

Definition at line 341 of file tidbitmap.c.

342 {
343  TBMSharedIteratorState *istate = dsa_get_address(dsa, dp);
344  PTEntryArray *ptbase;
345  PTIterationArray *ptpages;
346  PTIterationArray *ptchunks;
347 
348  if (DsaPointerIsValid(istate->pagetable))
349  {
350  ptbase = dsa_get_address(dsa, istate->pagetable);
351  if (pg_atomic_sub_fetch_u32(&ptbase->refcount, 1) == 0)
352  dsa_free(dsa, istate->pagetable);
353  }
354  if (DsaPointerIsValid(istate->spages))
355  {
356  ptpages = dsa_get_address(dsa, istate->spages);
357  if (pg_atomic_sub_fetch_u32(&ptpages->refcount, 1) == 0)
358  dsa_free(dsa, istate->spages);
359  }
360  if (DsaPointerIsValid(istate->schunks))
361  {
362  ptchunks = dsa_get_address(dsa, istate->schunks);
363  if (pg_atomic_sub_fetch_u32(&ptchunks->refcount, 1) == 0)
364  dsa_free(dsa, istate->schunks);
365  }
366 
367  dsa_free(dsa, dp);
368 }
static uint32 pg_atomic_sub_fetch_u32(volatile pg_atomic_uint32 *ptr, int32 sub_)
Definition: atomics.h:439
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:826
#define DsaPointerIsValid(x)
Definition: dsa.h:106
pg_atomic_uint32 refcount
Definition: tidbitmap.c:114
pg_atomic_uint32 refcount
Definition: tidbitmap.c:211

References dsa_free(), dsa_get_address(), DsaPointerIsValid, TBMSharedIteratorState::pagetable, pg_atomic_sub_fetch_u32(), PTEntryArray::refcount, PTIterationArray::refcount, TBMSharedIteratorState::schunks, and TBMSharedIteratorState::spages.

Referenced by ExecBitmapHeapReInitializeDSM().

◆ tbm_intersect()

void tbm_intersect ( TIDBitmap a,
const TIDBitmap b 
)

Definition at line 540 of file tidbitmap.c.

541 {
542  Assert(!a->iterating);
543  /* Nothing to do if a is empty */
544  if (a->nentries == 0)
545  return;
546  /* Scan through chunks and pages in a, try to match to b */
547  if (a->status == TBM_ONE_PAGE)
548  {
549  if (tbm_intersect_page(a, &a->entry1, b))
550  {
551  /* Page is now empty, remove it from a */
552  Assert(!a->entry1.ischunk);
553  a->npages--;
554  a->nentries--;
555  Assert(a->nentries == 0);
556  a->status = TBM_EMPTY;
557  }
558  }
559  else
560  {
561  pagetable_iterator i;
562  PagetableEntry *apage;
563 
564  Assert(a->status == TBM_HASH);
565  pagetable_start_iterate(a->pagetable, &i);
566  while ((apage = pagetable_iterate(a->pagetable, &i)) != NULL)
567  {
568  if (tbm_intersect_page(a, apage, b))
569  {
570  /* Page or chunk is now empty, remove it from a */
571  if (apage->ischunk)
572  a->nchunks--;
573  else
574  a->npages--;
575  a->nentries--;
576  if (!pagetable_delete(a->pagetable, apage->blockno))
577  elog(ERROR, "hash table corrupted");
578  }
579  }
580  }
581 }
int b
Definition: isn.c:69
int a
Definition: isn.c:68
BlockNumber blockno
Definition: tidbitmap.c:102
@ TBM_ONE_PAGE
Definition: tidbitmap.c:132
static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
Definition: tidbitmap.c:589

References a, Assert, b, PagetableEntry::blockno, elog, ERROR, i, PagetableEntry::ischunk, TBM_EMPTY, TBM_HASH, tbm_intersect_page(), and TBM_ONE_PAGE.

Referenced by MultiExecBitmapAnd().

◆ tbm_is_empty()

bool tbm_is_empty ( const TIDBitmap tbm)

Definition at line 670 of file tidbitmap.c.

671 {
672  return (tbm->nentries == 0);
673 }

References TIDBitmap::nentries.

Referenced by MultiExecBitmapAnd(), and startScanEntry().

◆ tbm_iterate()

TBMIterateResult* tbm_iterate ( TBMIterator iterator)

Definition at line 971 of file tidbitmap.c.

972 {
973  TIDBitmap *tbm = iterator->tbm;
974  TBMIterateResult *output = &(iterator->output);
975 
977 
978  /*
979  * If lossy chunk pages remain, make sure we've advanced schunkptr/
980  * schunkbit to the next set bit.
981  */
982  while (iterator->schunkptr < tbm->nchunks)
983  {
984  PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
985  int schunkbit = iterator->schunkbit;
986 
987  tbm_advance_schunkbit(chunk, &schunkbit);
988  if (schunkbit < PAGES_PER_CHUNK)
989  {
990  iterator->schunkbit = schunkbit;
991  break;
992  }
993  /* advance to next chunk */
994  iterator->schunkptr++;
995  iterator->schunkbit = 0;
996  }
997 
998  /*
999  * If both chunk and per-page data remain, must output the numerically
1000  * earlier page.
1001  */
1002  if (iterator->schunkptr < tbm->nchunks)
1003  {
1004  PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
1005  BlockNumber chunk_blockno;
1006 
1007  chunk_blockno = chunk->blockno + iterator->schunkbit;
1008  if (iterator->spageptr >= tbm->npages ||
1009  chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
1010  {
1011  /* Return a lossy page indicator from the chunk */
1012  output->blockno = chunk_blockno;
1013  output->ntuples = -1;
1014  output->recheck = true;
1015  iterator->schunkbit++;
1016  return output;
1017  }
1018  }
1019 
1020  if (iterator->spageptr < tbm->npages)
1021  {
1022  PagetableEntry *page;
1023  int ntuples;
1024 
1025  /* In TBM_ONE_PAGE state, we don't allocate an spages[] array */
1026  if (tbm->status == TBM_ONE_PAGE)
1027  page = &tbm->entry1;
1028  else
1029  page = tbm->spages[iterator->spageptr];
1030 
1031  /* scan bitmap to extract individual offset numbers */
1032  ntuples = tbm_extract_page_tuple(page, output);
1033  output->blockno = page->blockno;
1034  output->ntuples = ntuples;
1035  output->recheck = page->recheck;
1036  iterator->spageptr++;
1037  return output;
1038  }
1039 
1040  /* Nothing more in the bitmap */
1041  return NULL;
1042 }
uint64 chunk
FILE * output
TBMIterateResult output
Definition: tidbitmap.c:184
PagetableEntry entry1
Definition: tidbitmap.c:161
static void tbm_advance_schunkbit(PagetableEntry *chunk, int *schunkbitp)
Definition: tidbitmap.c:941
#define PAGES_PER_CHUNK
Definition: tidbitmap.c:74
static int tbm_extract_page_tuple(PagetableEntry *page, TBMIterateResult *output)
Definition: tidbitmap.c:911

References Assert, PagetableEntry::blockno, chunk, TIDBitmap::entry1, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::npages, TBMIterator::output, output, PAGES_PER_CHUNK, PagetableEntry::recheck, TBMIterator::schunkbit, TBMIterator::schunkptr, TIDBitmap::schunks, TBMIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMIterator::tbm, tbm_advance_schunkbit(), tbm_extract_page_tuple(), TBM_ITERATING_PRIVATE, and TBM_ONE_PAGE.

Referenced by BitmapAdjustPrefetchIterator(), BitmapPrefetch(), entryGetItem(), and heapam_scan_bitmap_next_block().

◆ tbm_prepare_shared_iterate()

dsa_pointer tbm_prepare_shared_iterate ( TIDBitmap tbm)

Definition at line 766 of file tidbitmap.c.

767 {
768  dsa_pointer dp;
769  TBMSharedIteratorState *istate;
770  PTEntryArray *ptbase = NULL;
771  PTIterationArray *ptpages = NULL;
772  PTIterationArray *ptchunks = NULL;
773 
774  Assert(tbm->dsa != NULL);
776 
777  /*
778  * Allocate TBMSharedIteratorState from DSA to hold the shared members and
779  * lock, this will also be used by multiple worker for shared iterate.
780  */
781  dp = dsa_allocate0(tbm->dsa, sizeof(TBMSharedIteratorState));
782  istate = dsa_get_address(tbm->dsa, dp);
783 
784  /*
785  * If we're not already iterating, create and fill the sorted page lists.
786  * (If we are, the sorted page lists are already stored in the TIDBitmap,
787  * and we can just reuse them.)
788  */
789  if (tbm->iterating == TBM_NOT_ITERATING)
790  {
791  pagetable_iterator i;
792  PagetableEntry *page;
793  int idx;
794  int npages;
795  int nchunks;
796 
797  /*
798  * Allocate the page and chunk array memory from the DSA to share
799  * across multiple processes.
800  */
801  if (tbm->npages)
802  {
803  tbm->ptpages = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
804  tbm->npages * sizeof(int));
805  ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
806  pg_atomic_init_u32(&ptpages->refcount, 0);
807  }
808  if (tbm->nchunks)
809  {
810  tbm->ptchunks = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
811  tbm->nchunks * sizeof(int));
812  ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
813  pg_atomic_init_u32(&ptchunks->refcount, 0);
814  }
815 
816  /*
817  * If TBM status is TBM_HASH then iterate over the pagetable and
818  * convert it to page and chunk arrays. But if it's in the
819  * TBM_ONE_PAGE mode then directly allocate the space for one entry
820  * from the DSA.
821  */
822  npages = nchunks = 0;
823  if (tbm->status == TBM_HASH)
824  {
825  ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
826 
827  pagetable_start_iterate(tbm->pagetable, &i);
828  while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
829  {
830  idx = page - ptbase->ptentry;
831  if (page->ischunk)
832  ptchunks->index[nchunks++] = idx;
833  else
834  ptpages->index[npages++] = idx;
835  }
836 
837  Assert(npages == tbm->npages);
838  Assert(nchunks == tbm->nchunks);
839  }
840  else if (tbm->status == TBM_ONE_PAGE)
841  {
842  /*
843  * In one page mode allocate the space for one pagetable entry,
844  * initialize it, and directly store its index (i.e. 0) in the
845  * page array.
846  */
847  tbm->dsapagetable = dsa_allocate(tbm->dsa, sizeof(PTEntryArray) +
848  sizeof(PagetableEntry));
849  ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
850  memcpy(ptbase->ptentry, &tbm->entry1, sizeof(PagetableEntry));
851  ptpages->index[0] = 0;
852  }
853 
854  if (ptbase != NULL)
855  pg_atomic_init_u32(&ptbase->refcount, 0);
856  if (npages > 1)
857  qsort_arg(ptpages->index, npages, sizeof(int),
858  tbm_shared_comparator, ptbase->ptentry);
859  if (nchunks > 1)
860  qsort_arg(ptchunks->index, nchunks, sizeof(int),
861  tbm_shared_comparator, ptbase->ptentry);
862  }
863 
864  /*
865  * Store the TBM members in the shared state so that we can share them
866  * across multiple processes.
867  */
868  istate->nentries = tbm->nentries;
869  istate->maxentries = tbm->maxentries;
870  istate->npages = tbm->npages;
871  istate->nchunks = tbm->nchunks;
872  istate->pagetable = tbm->dsapagetable;
873  istate->spages = tbm->ptpages;
874  istate->schunks = tbm->ptchunks;
875 
876  ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
877  ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
878  ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
879 
880  /*
881  * For every shared iterator, referring to pagetable and iterator array,
882  * increase the refcount by 1 so that while freeing the shared iterator we
883  * don't free pagetable and iterator array until its refcount becomes 0.
884  */
885  if (ptbase != NULL)
886  pg_atomic_add_fetch_u32(&ptbase->refcount, 1);
887  if (ptpages != NULL)
888  pg_atomic_add_fetch_u32(&ptpages->refcount, 1);
889  if (ptchunks != NULL)
890  pg_atomic_add_fetch_u32(&ptchunks->refcount, 1);
891 
892  /* Initialize the iterator lock */
894 
895  /* Initialize the shared iterator state */
896  istate->schunkbit = 0;
897  istate->schunkptr = 0;
898  istate->spageptr = 0;
899 
901 
902  return dp;
903 }
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:259
static void pg_atomic_init_u32(volatile pg_atomic_uint32 *ptr, uint32 val)
Definition: atomics.h:221
static uint32 pg_atomic_add_fetch_u32(volatile pg_atomic_uint32 *ptr, int32 add_)
Definition: atomics.h:424
#define dsa_allocate0(area, size)
Definition: dsa.h:113
uint64 dsa_pointer
Definition: dsa.h:62
#define dsa_allocate(area, size)
Definition: dsa.h:109
void LWLockInitialize(LWLock *lock, int tranche_id)
Definition: lwlock.c:707
@ LWTRANCHE_SHARED_TIDBITMAP
Definition: lwlock.h:200
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
PagetableEntry ptentry[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.c:115
int index[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.c:212
static int tbm_shared_comparator(const void *left, const void *right, void *arg)
Definition: tidbitmap.c:1438

References Assert, TIDBitmap::dsa, dsa_allocate, dsa_allocate0, dsa_get_address(), TIDBitmap::dsapagetable, TIDBitmap::entry1, i, idx(), PTIterationArray::index, PagetableEntry::ischunk, TIDBitmap::iterating, TBMSharedIteratorState::lock, LWLockInitialize(), LWTRANCHE_SHARED_TIDBITMAP, TIDBitmap::maxentries, TBMSharedIteratorState::maxentries, TIDBitmap::nchunks, TBMSharedIteratorState::nchunks, TIDBitmap::nentries, TBMSharedIteratorState::nentries, TIDBitmap::npages, TBMSharedIteratorState::npages, TIDBitmap::pagetable, TBMSharedIteratorState::pagetable, pg_atomic_add_fetch_u32(), pg_atomic_init_u32(), TIDBitmap::ptchunks, PTEntryArray::ptentry, TIDBitmap::ptpages, qsort_arg(), PTEntryArray::refcount, PTIterationArray::refcount, TBMSharedIteratorState::schunkbit, TBMSharedIteratorState::schunkptr, TBMSharedIteratorState::schunks, TBMSharedIteratorState::spageptr, TBMSharedIteratorState::spages, TIDBitmap::status, TBM_HASH, TBM_ITERATING_PRIVATE, TBM_ITERATING_SHARED, TBM_NOT_ITERATING, TBM_ONE_PAGE, and tbm_shared_comparator().

Referenced by BitmapHeapNext().

◆ tbm_shared_iterate()

TBMIterateResult* tbm_shared_iterate ( TBMSharedIterator iterator)

Definition at line 1052 of file tidbitmap.c.

1053 {
1054  TBMIterateResult *output = &iterator->output;
1055  TBMSharedIteratorState *istate = iterator->state;
1056  PagetableEntry *ptbase = NULL;
1057  int *idxpages = NULL;
1058  int *idxchunks = NULL;
1059 
1060  if (iterator->ptbase != NULL)
1061  ptbase = iterator->ptbase->ptentry;
1062  if (iterator->ptpages != NULL)
1063  idxpages = iterator->ptpages->index;
1064  if (iterator->ptchunks != NULL)
1065  idxchunks = iterator->ptchunks->index;
1066 
1067  /* Acquire the LWLock before accessing the shared members */
1068  LWLockAcquire(&istate->lock, LW_EXCLUSIVE);
1069 
1070  /*
1071  * If lossy chunk pages remain, make sure we've advanced schunkptr/
1072  * schunkbit to the next set bit.
1073  */
1074  while (istate->schunkptr < istate->nchunks)
1075  {
1076  PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
1077  int schunkbit = istate->schunkbit;
1078 
1079  tbm_advance_schunkbit(chunk, &schunkbit);
1080  if (schunkbit < PAGES_PER_CHUNK)
1081  {
1082  istate->schunkbit = schunkbit;
1083  break;
1084  }
1085  /* advance to next chunk */
1086  istate->schunkptr++;
1087  istate->schunkbit = 0;
1088  }
1089 
1090  /*
1091  * If both chunk and per-page data remain, must output the numerically
1092  * earlier page.
1093  */
1094  if (istate->schunkptr < istate->nchunks)
1095  {
1096  PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
1097  BlockNumber chunk_blockno;
1098 
1099  chunk_blockno = chunk->blockno + istate->schunkbit;
1100 
1101  if (istate->spageptr >= istate->npages ||
1102  chunk_blockno < ptbase[idxpages[istate->spageptr]].blockno)
1103  {
1104  /* Return a lossy page indicator from the chunk */
1105  output->blockno = chunk_blockno;
1106  output->ntuples = -1;
1107  output->recheck = true;
1108  istate->schunkbit++;
1109 
1110  LWLockRelease(&istate->lock);
1111  return output;
1112  }
1113  }
1114 
1115  if (istate->spageptr < istate->npages)
1116  {
1117  PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
1118  int ntuples;
1119 
1120  /* scan bitmap to extract individual offset numbers */
1121  ntuples = tbm_extract_page_tuple(page, output);
1122  output->blockno = page->blockno;
1123  output->ntuples = ntuples;
1124  output->recheck = page->recheck;
1125  istate->spageptr++;
1126 
1127  LWLockRelease(&istate->lock);
1128 
1129  return output;
1130  }
1131 
1132  LWLockRelease(&istate->lock);
1133 
1134  /* Nothing more in the bitmap */
1135  return NULL;
1136 }
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1168
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1781
@ LW_EXCLUSIVE
Definition: lwlock.h:114
TBMIterateResult output
Definition: tidbitmap.c:225

References PagetableEntry::blockno, chunk, PTIterationArray::index, TBMSharedIteratorState::lock, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), TBMSharedIteratorState::nchunks, TBMSharedIteratorState::npages, TBMSharedIterator::output, output, PAGES_PER_CHUNK, TBMSharedIterator::ptbase, TBMSharedIterator::ptchunks, PTEntryArray::ptentry, TBMSharedIterator::ptpages, PagetableEntry::recheck, TBMSharedIteratorState::schunkbit, TBMSharedIteratorState::schunkptr, TBMSharedIteratorState::spageptr, TBMSharedIterator::state, tbm_advance_schunkbit(), and tbm_extract_page_tuple().

Referenced by BitmapAdjustPrefetchIterator(), BitmapPrefetch(), and heapam_scan_bitmap_next_block().

◆ tbm_union()

void tbm_union ( TIDBitmap a,
const TIDBitmap b 
)

Definition at line 458 of file tidbitmap.c.

459 {
460  Assert(!a->iterating);
461  /* Nothing to do if b is empty */
462  if (b->nentries == 0)
463  return;
464  /* Scan through chunks and pages in b, merge into a */
465  if (b->status == TBM_ONE_PAGE)
466  tbm_union_page(a, &b->entry1);
467  else
468  {
469  pagetable_iterator i;
470  PagetableEntry *bpage;
471 
472  Assert(b->status == TBM_HASH);
473  pagetable_start_iterate(b->pagetable, &i);
474  while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
475  tbm_union_page(a, bpage);
476  }
477 }
static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
Definition: tidbitmap.c:481

References a, Assert, b, i, TBM_HASH, TBM_ONE_PAGE, and tbm_union_page().

Referenced by MultiExecBitmapOr().