LCOV - code coverage report
Current view: top level - src/backend/nodes - tidbitmap.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 427 486 87.9 %
Date: 2023-11-29 04:11:06 Functions: 28 30 93.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * tidbitmap.c
       4             :  *    PostgreSQL tuple-id (TID) bitmap package
       5             :  *
       6             :  * This module provides bitmap data structures that are spiritually
       7             :  * similar to Bitmapsets, but are specially adapted to store sets of
       8             :  * tuple identifiers (TIDs), or ItemPointers.  In particular, the division
       9             :  * of an ItemPointer into BlockNumber and OffsetNumber is catered for.
      10             :  * Also, since we wish to be able to store very large tuple sets in
      11             :  * memory with this data structure, we support "lossy" storage, in which
      12             :  * we no longer remember individual tuple offsets on a page but only the
      13             :  * fact that a particular page needs to be visited.
      14             :  *
      15             :  * The "lossy" storage uses one bit per disk page, so at the standard 8K
      16             :  * BLCKSZ, we can represent all pages in 64Gb of disk space in about 1Mb
      17             :  * of memory.  People pushing around tables of that size should have a
      18             :  * couple of Mb to spare, so we don't worry about providing a second level
      19             :  * of lossiness.  In theory we could fall back to page ranges at some
      20             :  * point, but for now that seems useless complexity.
      21             :  *
      22             :  * We also support the notion of candidate matches, or rechecking.  This
      23             :  * means we know that a search need visit only some tuples on a page,
      24             :  * but we are not certain that all of those tuples are real matches.
      25             :  * So the eventual heap scan must recheck the quals for these tuples only,
      26             :  * rather than rechecking the quals for all tuples on the page as in the
      27             :  * lossy-bitmap case.  Rechecking can be specified when TIDs are inserted
      28             :  * into a bitmap, and it can also happen internally when we AND a lossy
      29             :  * and a non-lossy page.
      30             :  *
      31             :  *
      32             :  * Copyright (c) 2003-2023, PostgreSQL Global Development Group
      33             :  *
      34             :  * IDENTIFICATION
      35             :  *    src/backend/nodes/tidbitmap.c
      36             :  *
      37             :  *-------------------------------------------------------------------------
      38             :  */
      39             : #include "postgres.h"
      40             : 
      41             : #include <limits.h>
      42             : 
      43             : #include "access/htup_details.h"
      44             : #include "common/hashfn.h"
      45             : #include "nodes/bitmapset.h"
      46             : #include "nodes/tidbitmap.h"
      47             : #include "storage/lwlock.h"
      48             : #include "utils/dsa.h"
      49             : 
      50             : /*
      51             :  * The maximum number of tuples per page is not large (typically 256 with
      52             :  * 8K pages, or 1024 with 32K pages).  So there's not much point in making
      53             :  * the per-page bitmaps variable size.  We just legislate that the size
      54             :  * is this:
      55             :  */
      56             : #define MAX_TUPLES_PER_PAGE  MaxHeapTuplesPerPage
      57             : 
      58             : /*
      59             :  * When we have to switch over to lossy storage, we use a data structure
      60             :  * with one bit per page, where all pages having the same number DIV
      61             :  * PAGES_PER_CHUNK are aggregated into one chunk.  When a chunk is present
      62             :  * and has the bit set for a given page, there must not be a per-page entry
      63             :  * for that page in the page table.
      64             :  *
      65             :  * We actually store both exact pages and lossy chunks in the same hash
      66             :  * table, using identical data structures.  (This is because the memory
      67             :  * management for hashtables doesn't easily/efficiently allow space to be
      68             :  * transferred easily from one hashtable to another.)  Therefore it's best
      69             :  * if PAGES_PER_CHUNK is the same as MAX_TUPLES_PER_PAGE, or at least not
      70             :  * too different.  But we also want PAGES_PER_CHUNK to be a power of 2 to
      71             :  * avoid expensive integer remainder operations.  So, define it like this:
      72             :  */
      73             : #define PAGES_PER_CHUNK  (BLCKSZ / 32)
      74             : 
      75             : /* We use BITS_PER_BITMAPWORD and typedef bitmapword from nodes/bitmapset.h */
      76             : 
      77             : #define WORDNUM(x)  ((x) / BITS_PER_BITMAPWORD)
      78             : #define BITNUM(x)   ((x) % BITS_PER_BITMAPWORD)
      79             : 
      80             : /* number of active words for an exact page: */
      81             : #define WORDS_PER_PAGE  ((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1)
      82             : /* number of active words for a lossy chunk: */
      83             : #define WORDS_PER_CHUNK  ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)
      84             : 
      85             : /*
      86             :  * The hashtable entries are represented by this data structure.  For
      87             :  * an exact page, blockno is the page number and bit k of the bitmap
      88             :  * represents tuple offset k+1.  For a lossy chunk, blockno is the first
      89             :  * page in the chunk (this must be a multiple of PAGES_PER_CHUNK) and
      90             :  * bit k represents page blockno+k.  Note that it is not possible to
      91             :  * have exact storage for the first page of a chunk if we are using
      92             :  * lossy storage for any page in the chunk's range, since the same
      93             :  * hashtable entry has to serve both purposes.
      94             :  *
      95             :  * recheck is used only on exact pages --- it indicates that although
      96             :  * only the stated tuples need be checked, the full index qual condition
      97             :  * must be checked for each (ie, these are candidate matches).
      98             :  */
      99             : typedef struct PagetableEntry
     100             : {
     101             :     BlockNumber blockno;        /* page number (hashtable key) */
     102             :     char        status;         /* hash entry status */
     103             :     bool        ischunk;        /* T = lossy storage, F = exact */
     104             :     bool        recheck;        /* should the tuples be rechecked? */
     105             :     bitmapword  words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];
     106             : } PagetableEntry;
     107             : 
     108             : /*
     109             :  * Holds array of pagetable entries.
     110             :  */
     111             : typedef struct PTEntryArray
     112             : {
     113             :     pg_atomic_uint32 refcount;  /* no. of iterator attached */
     114             :     PagetableEntry ptentry[FLEXIBLE_ARRAY_MEMBER];
     115             : } PTEntryArray;
     116             : 
     117             : /*
     118             :  * We want to avoid the overhead of creating the hashtable, which is
     119             :  * comparatively large, when not necessary. Particularly when we are using a
     120             :  * bitmap scan on the inside of a nestloop join: a bitmap may well live only
     121             :  * long enough to accumulate one entry in such cases.  We therefore avoid
     122             :  * creating an actual hashtable until we need two pagetable entries.  When
     123             :  * just one pagetable entry is needed, we store it in a fixed field of
     124             :  * TIDBitMap.  (NOTE: we don't get rid of the hashtable if the bitmap later
     125             :  * shrinks down to zero or one page again.  So, status can be TBM_HASH even
     126             :  * when nentries is zero or one.)
     127             :  */
     128             : typedef enum
     129             : {
     130             :     TBM_EMPTY,                  /* no hashtable, nentries == 0 */
     131             :     TBM_ONE_PAGE,               /* entry1 contains the single entry */
     132             :     TBM_HASH,                   /* pagetable is valid, entry1 is not */
     133             : } TBMStatus;
     134             : 
     135             : /*
     136             :  * Current iterating state of the TBM.
     137             :  */
     138             : typedef enum
     139             : {
     140             :     TBM_NOT_ITERATING,          /* not yet converted to page and chunk array */
     141             :     TBM_ITERATING_PRIVATE,      /* converted to local page and chunk array */
     142             :     TBM_ITERATING_SHARED,       /* converted to shared page and chunk array */
     143             : } TBMIteratingState;
     144             : 
     145             : /*
     146             :  * Here is the representation for a whole TIDBitMap:
     147             :  */
     148             : struct TIDBitmap
     149             : {
     150             :     NodeTag     type;           /* to make it a valid Node */
     151             :     MemoryContext mcxt;         /* memory context containing me */
     152             :     TBMStatus   status;         /* see codes above */
     153             :     struct pagetable_hash *pagetable;   /* hash table of PagetableEntry's */
     154             :     int         nentries;       /* number of entries in pagetable */
     155             :     int         maxentries;     /* limit on same to meet maxbytes */
     156             :     int         npages;         /* number of exact entries in pagetable */
     157             :     int         nchunks;        /* number of lossy entries in pagetable */
     158             :     TBMIteratingState iterating;    /* tbm_begin_iterate called? */
     159             :     uint32      lossify_start;  /* offset to start lossifying hashtable at */
     160             :     PagetableEntry entry1;      /* used when status == TBM_ONE_PAGE */
     161             :     /* these are valid when iterating is true: */
     162             :     PagetableEntry **spages;    /* sorted exact-page list, or NULL */
     163             :     PagetableEntry **schunks;   /* sorted lossy-chunk list, or NULL */
     164             :     dsa_pointer dsapagetable;   /* dsa_pointer to the element array */
     165             :     dsa_pointer dsapagetableold;    /* dsa_pointer to the old element array */
     166             :     dsa_pointer ptpages;        /* dsa_pointer to the page array */
     167             :     dsa_pointer ptchunks;       /* dsa_pointer to the chunk array */
     168             :     dsa_area   *dsa;            /* reference to per-query dsa area */
     169             : };
     170             : 
     171             : /*
     172             :  * When iterating over a bitmap in sorted order, a TBMIterator is used to
     173             :  * track our progress.  There can be several iterators scanning the same
     174             :  * bitmap concurrently.  Note that the bitmap becomes read-only as soon as
     175             :  * any iterator is created.
     176             :  */
     177             : struct TBMIterator
     178             : {
     179             :     TIDBitmap  *tbm;            /* TIDBitmap we're iterating over */
     180             :     int         spageptr;       /* next spages index */
     181             :     int         schunkptr;      /* next schunks index */
     182             :     int         schunkbit;      /* next bit to check in current schunk */
     183             :     TBMIterateResult output;    /* MUST BE LAST (because variable-size) */
     184             : };
     185             : 
     186             : /*
     187             :  * Holds the shared members of the iterator so that multiple processes
     188             :  * can jointly iterate.
     189             :  */
     190             : typedef struct TBMSharedIteratorState
     191             : {
     192             :     int         nentries;       /* number of entries in pagetable */
     193             :     int         maxentries;     /* limit on same to meet maxbytes */
     194             :     int         npages;         /* number of exact entries in pagetable */
     195             :     int         nchunks;        /* number of lossy entries in pagetable */
     196             :     dsa_pointer pagetable;      /* dsa pointers to head of pagetable data */
     197             :     dsa_pointer spages;         /* dsa pointer to page array */
     198             :     dsa_pointer schunks;        /* dsa pointer to chunk array */
     199             :     LWLock      lock;           /* lock to protect below members */
     200             :     int         spageptr;       /* next spages index */
     201             :     int         schunkptr;      /* next schunks index */
     202             :     int         schunkbit;      /* next bit to check in current schunk */
     203             : } TBMSharedIteratorState;
     204             : 
     205             : /*
     206             :  * pagetable iteration array.
     207             :  */
     208             : typedef struct PTIterationArray
     209             : {
     210             :     pg_atomic_uint32 refcount;  /* no. of iterator attached */
     211             :     int         index[FLEXIBLE_ARRAY_MEMBER];   /* index array */
     212             : } PTIterationArray;
     213             : 
     214             : /*
     215             :  * same as TBMIterator, but it is used for joint iteration, therefore this
     216             :  * also holds a reference to the shared state.
     217             :  */
     218             : struct TBMSharedIterator
     219             : {
     220             :     TBMSharedIteratorState *state;  /* shared state */
     221             :     PTEntryArray *ptbase;       /* pagetable element array */
     222             :     PTIterationArray *ptpages;  /* sorted exact page index list */
     223             :     PTIterationArray *ptchunks; /* sorted lossy page index list */
     224             :     TBMIterateResult output;    /* MUST BE LAST (because variable-size) */
     225             : };
     226             : 
     227             : /* Local function prototypes */
     228             : static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage);
     229             : static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage,
     230             :                                const TIDBitmap *b);
     231             : static const PagetableEntry *tbm_find_pageentry(const TIDBitmap *tbm,
     232             :                                                 BlockNumber pageno);
     233             : static PagetableEntry *tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno);
     234             : static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno);
     235             : static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno);
     236             : static void tbm_lossify(TIDBitmap *tbm);
     237             : static int  tbm_comparator(const void *left, const void *right);
     238             : static int  tbm_shared_comparator(const void *left, const void *right,
     239             :                                   void *arg);
     240             : 
     241             : /* define hashtable mapping block numbers to PagetableEntry's */
     242             : #define SH_USE_NONDEFAULT_ALLOCATOR
     243             : #define SH_PREFIX pagetable
     244             : #define SH_ELEMENT_TYPE PagetableEntry
     245             : #define SH_KEY_TYPE BlockNumber
     246             : #define SH_KEY blockno
     247             : #define SH_HASH_KEY(tb, key) murmurhash32(key)
     248             : #define SH_EQUAL(tb, a, b) a == b
     249             : #define SH_SCOPE static inline
     250             : #define SH_DEFINE
     251             : #define SH_DECLARE
     252             : #include "lib/simplehash.h"
     253             : 
     254             : 
     255             : /*
     256             :  * tbm_create - create an initially-empty bitmap
     257             :  *
     258             :  * The bitmap will live in the memory context that is CurrentMemoryContext
     259             :  * at the time of this call.  It will be limited to (approximately) maxbytes
     260             :  * total memory consumption.  If the DSA passed to this function is not NULL
     261             :  * then the memory for storing elements of the underlying page table will
     262             :  * be allocated from the DSA.
     263             :  */
     264             : TIDBitmap *
     265       16720 : tbm_create(long maxbytes, dsa_area *dsa)
     266             : {
     267             :     TIDBitmap  *tbm;
     268             : 
     269             :     /* Create the TIDBitmap struct and zero all its fields */
     270       16720 :     tbm = makeNode(TIDBitmap);
     271             : 
     272       16720 :     tbm->mcxt = CurrentMemoryContext;
     273       16720 :     tbm->status = TBM_EMPTY;
     274             : 
     275       16720 :     tbm->maxentries = (int) tbm_calculate_entries(maxbytes);
     276       16720 :     tbm->lossify_start = 0;
     277       16720 :     tbm->dsa = dsa;
     278       16720 :     tbm->dsapagetable = InvalidDsaPointer;
     279       16720 :     tbm->dsapagetableold = InvalidDsaPointer;
     280       16720 :     tbm->ptpages = InvalidDsaPointer;
     281       16720 :     tbm->ptchunks = InvalidDsaPointer;
     282             : 
     283       16720 :     return tbm;
     284             : }
     285             : 
     286             : /*
     287             :  * Actually create the hashtable.  Since this is a moderately expensive
     288             :  * proposition, we don't do it until we have to.
     289             :  */
     290             : static void
     291        7918 : tbm_create_pagetable(TIDBitmap *tbm)
     292             : {
     293             :     Assert(tbm->status != TBM_HASH);
     294             :     Assert(tbm->pagetable == NULL);
     295             : 
     296        7918 :     tbm->pagetable = pagetable_create(tbm->mcxt, 128, tbm);
     297             : 
     298             :     /* If entry1 is valid, push it into the hashtable */
     299        7918 :     if (tbm->status == TBM_ONE_PAGE)
     300             :     {
     301             :         PagetableEntry *page;
     302             :         bool        found;
     303             :         char        oldstatus;
     304             : 
     305        5050 :         page = pagetable_insert(tbm->pagetable,
     306             :                                 tbm->entry1.blockno,
     307             :                                 &found);
     308             :         Assert(!found);
     309        5050 :         oldstatus = page->status;
     310        5050 :         memcpy(page, &tbm->entry1, sizeof(PagetableEntry));
     311        5050 :         page->status = oldstatus;
     312             :     }
     313             : 
     314        7918 :     tbm->status = TBM_HASH;
     315        7918 : }
     316             : 
     317             : /*
     318             :  * tbm_free - free a TIDBitmap
     319             :  */
     320             : void
     321       16654 : tbm_free(TIDBitmap *tbm)
     322             : {
     323       16654 :     if (tbm->pagetable)
     324        7914 :         pagetable_destroy(tbm->pagetable);
     325       16654 :     if (tbm->spages)
     326        4900 :         pfree(tbm->spages);
     327       16654 :     if (tbm->schunks)
     328        2880 :         pfree(tbm->schunks);
     329       16654 :     pfree(tbm);
     330       16654 : }
     331             : 
     332             : /*
     333             :  * tbm_free_shared_area - free shared state
     334             :  *
     335             :  * Free shared iterator state, Also free shared pagetable and iterator arrays
     336             :  * memory if they are not referred by any of the shared iterator i.e recount
     337             :  * is becomes 0.
     338             :  */
     339             : void
     340         108 : tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp)
     341             : {
     342         108 :     TBMSharedIteratorState *istate = dsa_get_address(dsa, dp);
     343             :     PTEntryArray *ptbase;
     344             :     PTIterationArray *ptpages;
     345             :     PTIterationArray *ptchunks;
     346             : 
     347         108 :     if (DsaPointerIsValid(istate->pagetable))
     348             :     {
     349         108 :         ptbase = dsa_get_address(dsa, istate->pagetable);
     350         108 :         if (pg_atomic_sub_fetch_u32(&ptbase->refcount, 1) == 0)
     351          54 :             dsa_free(dsa, istate->pagetable);
     352             :     }
     353         108 :     if (DsaPointerIsValid(istate->spages))
     354             :     {
     355         108 :         ptpages = dsa_get_address(dsa, istate->spages);
     356         108 :         if (pg_atomic_sub_fetch_u32(&ptpages->refcount, 1) == 0)
     357          54 :             dsa_free(dsa, istate->spages);
     358             :     }
     359         108 :     if (DsaPointerIsValid(istate->schunks))
     360             :     {
     361           0 :         ptchunks = dsa_get_address(dsa, istate->schunks);
     362           0 :         if (pg_atomic_sub_fetch_u32(&ptchunks->refcount, 1) == 0)
     363           0 :             dsa_free(dsa, istate->schunks);
     364             :     }
     365             : 
     366         108 :     dsa_free(dsa, dp);
     367         108 : }
     368             : 
     369             : /*
     370             :  * tbm_add_tuples - add some tuple IDs to a TIDBitmap
     371             :  *
     372             :  * If recheck is true, then the recheck flag will be set in the
     373             :  * TBMIterateResult when any of these tuples are reported out.
     374             :  */
     375             : void
     376     6313118 : tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids,
     377             :                bool recheck)
     378             : {
     379     6313118 :     BlockNumber currblk = InvalidBlockNumber;
     380     6313118 :     PagetableEntry *page = NULL;    /* only valid when currblk is valid */
     381             :     int         i;
     382             : 
     383             :     Assert(tbm->iterating == TBM_NOT_ITERATING);
     384    14807670 :     for (i = 0; i < ntids; i++)
     385             :     {
     386     8494552 :         BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
     387     8494552 :         OffsetNumber off = ItemPointerGetOffsetNumber(tids + i);
     388             :         int         wordnum,
     389             :                     bitnum;
     390             : 
     391             :         /* safety check to ensure we don't overrun bit array bounds */
     392     8494552 :         if (off < 1 || off > MAX_TUPLES_PER_PAGE)
     393           0 :             elog(ERROR, "tuple offset out of range: %u", off);
     394             : 
     395             :         /*
     396             :          * Look up target page unless we already did.  This saves cycles when
     397             :          * the input includes consecutive tuples on the same page, which is
     398             :          * common enough to justify an extra test here.
     399             :          */
     400     8494552 :         if (blk != currblk)
     401             :         {
     402     7089824 :             if (tbm_page_is_lossy(tbm, blk))
     403        2856 :                 page = NULL;    /* remember page is lossy */
     404             :             else
     405     7086968 :                 page = tbm_get_pageentry(tbm, blk);
     406     7089824 :             currblk = blk;
     407             :         }
     408             : 
     409     8494552 :         if (page == NULL)
     410        2856 :             continue;           /* whole page is already marked */
     411             : 
     412     8491696 :         if (page->ischunk)
     413             :         {
     414             :             /* The page is a lossy chunk header, set bit for itself */
     415           0 :             wordnum = bitnum = 0;
     416             :         }
     417             :         else
     418             :         {
     419             :             /* Page is exact, so set bit for individual tuple */
     420     8491696 :             wordnum = WORDNUM(off - 1);
     421     8491696 :             bitnum = BITNUM(off - 1);
     422             :         }
     423     8491696 :         page->words[wordnum] |= ((bitmapword) 1 << bitnum);
     424     8491696 :         page->recheck |= recheck;
     425             : 
     426     8491696 :         if (tbm->nentries > tbm->maxentries)
     427             :         {
     428          24 :             tbm_lossify(tbm);
     429             :             /* Page could have been converted to lossy, so force new lookup */
     430          24 :             currblk = InvalidBlockNumber;
     431             :         }
     432             :     }
     433     6313118 : }
     434             : 
     435             : /*
     436             :  * tbm_add_page - add a whole page to a TIDBitmap
     437             :  *
     438             :  * This causes the whole page to be reported (with the recheck flag)
     439             :  * when the TIDBitmap is scanned.
     440             :  */
     441             : void
     442      147980 : tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
     443             : {
     444             :     /* Enter the page in the bitmap, or mark it lossy if already present */
     445      147980 :     tbm_mark_page_lossy(tbm, pageno);
     446             :     /* If we went over the memory limit, lossify some more pages */
     447      147980 :     if (tbm->nentries > tbm->maxentries)
     448           0 :         tbm_lossify(tbm);
     449      147980 : }
     450             : 
     451             : /*
     452             :  * tbm_union - set union
     453             :  *
     454             :  * a is modified in-place, b is not changed
     455             :  */
     456             : void
     457           0 : tbm_union(TIDBitmap *a, const TIDBitmap *b)
     458             : {
     459             :     Assert(!a->iterating);
     460             :     /* Nothing to do if b is empty */
     461           0 :     if (b->nentries == 0)
     462           0 :         return;
     463             :     /* Scan through chunks and pages in b, merge into a */
     464           0 :     if (b->status == TBM_ONE_PAGE)
     465           0 :         tbm_union_page(a, &b->entry1);
     466             :     else
     467             :     {
     468             :         pagetable_iterator i;
     469             :         PagetableEntry *bpage;
     470             : 
     471             :         Assert(b->status == TBM_HASH);
     472           0 :         pagetable_start_iterate(b->pagetable, &i);
     473           0 :         while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
     474           0 :             tbm_union_page(a, bpage);
     475             :     }
     476             : }
     477             : 
     478             : /* Process one page of b during a union op */
     479             : static void
     480           0 : tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
     481             : {
     482             :     PagetableEntry *apage;
     483             :     int         wordnum;
     484             : 
     485           0 :     if (bpage->ischunk)
     486             :     {
     487             :         /* Scan b's chunk, mark each indicated page lossy in a */
     488           0 :         for (wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
     489             :         {
     490           0 :             bitmapword  w = bpage->words[wordnum];
     491             : 
     492           0 :             if (w != 0)
     493             :             {
     494             :                 BlockNumber pg;
     495             : 
     496           0 :                 pg = bpage->blockno + (wordnum * BITS_PER_BITMAPWORD);
     497           0 :                 while (w != 0)
     498             :                 {
     499           0 :                     if (w & 1)
     500           0 :                         tbm_mark_page_lossy(a, pg);
     501           0 :                     pg++;
     502           0 :                     w >>= 1;
     503             :                 }
     504             :             }
     505             :         }
     506             :     }
     507           0 :     else if (tbm_page_is_lossy(a, bpage->blockno))
     508             :     {
     509             :         /* page is already lossy in a, nothing to do */
     510           0 :         return;
     511             :     }
     512             :     else
     513             :     {
     514           0 :         apage = tbm_get_pageentry(a, bpage->blockno);
     515           0 :         if (apage->ischunk)
     516             :         {
     517             :             /* The page is a lossy chunk header, set bit for itself */
     518           0 :             apage->words[0] |= ((bitmapword) 1 << 0);
     519             :         }
     520             :         else
     521             :         {
     522             :             /* Both pages are exact, merge at the bit level */
     523           0 :             for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
     524           0 :                 apage->words[wordnum] |= bpage->words[wordnum];
     525           0 :             apage->recheck |= bpage->recheck;
     526             :         }
     527             :     }
     528             : 
     529           0 :     if (a->nentries > a->maxentries)
     530           0 :         tbm_lossify(a);
     531             : }
     532             : 
     533             : /*
     534             :  * tbm_intersect - set intersection
     535             :  *
     536             :  * a is modified in-place, b is not changed
     537             :  */
     538             : void
     539          68 : tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
     540             : {
     541             :     Assert(!a->iterating);
     542             :     /* Nothing to do if a is empty */
     543          68 :     if (a->nentries == 0)
     544           0 :         return;
     545             :     /* Scan through chunks and pages in a, try to match to b */
     546          68 :     if (a->status == TBM_ONE_PAGE)
     547             :     {
     548          40 :         if (tbm_intersect_page(a, &a->entry1, b))
     549             :         {
     550             :             /* Page is now empty, remove it from a */
     551             :             Assert(!a->entry1.ischunk);
     552           0 :             a->npages--;
     553           0 :             a->nentries--;
     554             :             Assert(a->nentries == 0);
     555           0 :             a->status = TBM_EMPTY;
     556             :         }
     557             :     }
     558             :     else
     559             :     {
     560             :         pagetable_iterator i;
     561             :         PagetableEntry *apage;
     562             : 
     563             :         Assert(a->status == TBM_HASH);
     564          28 :         pagetable_start_iterate(a->pagetable, &i);
     565        4814 :         while ((apage = pagetable_iterate(a->pagetable, &i)) != NULL)
     566             :         {
     567        4786 :             if (tbm_intersect_page(a, apage, b))
     568             :             {
     569             :                 /* Page or chunk is now empty, remove it from a */
     570        4608 :                 if (apage->ischunk)
     571           0 :                     a->nchunks--;
     572             :                 else
     573        4608 :                     a->npages--;
     574        4608 :                 a->nentries--;
     575        4608 :                 if (!pagetable_delete(a->pagetable, apage->blockno))
     576           0 :                     elog(ERROR, "hash table corrupted");
     577             :             }
     578             :         }
     579             :     }
     580             : }
     581             : 
     582             : /*
     583             :  * Process one page of a during an intersection op
     584             :  *
     585             :  * Returns true if apage is now empty and should be deleted from a
     586             :  */
     587             : static bool
     588        4826 : tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
     589             : {
     590             :     const PagetableEntry *bpage;
     591             :     int         wordnum;
     592             : 
     593        4826 :     if (apage->ischunk)
     594             :     {
     595             :         /* Scan each bit in chunk, try to clear */
     596          30 :         bool        candelete = true;
     597             : 
     598         150 :         for (wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
     599             :         {
     600         120 :             bitmapword  w = apage->words[wordnum];
     601             : 
     602         120 :             if (w != 0)
     603             :             {
     604         108 :                 bitmapword  neww = w;
     605             :                 BlockNumber pg;
     606             :                 int         bitnum;
     607             : 
     608         108 :                 pg = apage->blockno + (wordnum * BITS_PER_BITMAPWORD);
     609         108 :                 bitnum = 0;
     610        6606 :                 while (w != 0)
     611             :                 {
     612        6498 :                     if (w & 1)
     613             :                     {
     614        3360 :                         if (!tbm_page_is_lossy(b, pg) &&
     615         252 :                             tbm_find_pageentry(b, pg) == NULL)
     616             :                         {
     617             :                             /* Page is not in b at all, lose lossy bit */
     618           0 :                             neww &= ~((bitmapword) 1 << bitnum);
     619             :                         }
     620             :                     }
     621        6498 :                     pg++;
     622        6498 :                     bitnum++;
     623        6498 :                     w >>= 1;
     624             :                 }
     625         108 :                 apage->words[wordnum] = neww;
     626         108 :                 if (neww != 0)
     627         108 :                     candelete = false;
     628             :             }
     629             :         }
     630          30 :         return candelete;
     631             :     }
     632        4796 :     else if (tbm_page_is_lossy(b, apage->blockno))
     633             :     {
     634             :         /*
     635             :          * Some of the tuples in 'a' might not satisfy the quals for 'b', but
     636             :          * because the page 'b' is lossy, we don't know which ones. Therefore
     637             :          * we mark 'a' as requiring rechecks, to indicate that at most those
     638             :          * tuples set in 'a' are matches.
     639             :          */
     640           0 :         apage->recheck = true;
     641           0 :         return false;
     642             :     }
     643             :     else
     644             :     {
     645        4796 :         bool        candelete = true;
     646             : 
     647        4796 :         bpage = tbm_find_pageentry(b, apage->blockno);
     648        4796 :         if (bpage != NULL)
     649             :         {
     650             :             /* Both pages are exact, merge at the bit level */
     651             :             Assert(!bpage->ischunk);
     652       25704 :             for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
     653             :             {
     654       21420 :                 apage->words[wordnum] &= bpage->words[wordnum];
     655       21420 :                 if (apage->words[wordnum] != 0)
     656         190 :                     candelete = false;
     657             :             }
     658        4284 :             apage->recheck |= bpage->recheck;
     659             :         }
     660             :         /* If there is no matching b page, we can just delete the a page */
     661        4796 :         return candelete;
     662             :     }
     663             : }
     664             : 
     665             : /*
     666             :  * tbm_is_empty - is a TIDBitmap completely empty?
     667             :  */
     668             : bool
     669         670 : tbm_is_empty(const TIDBitmap *tbm)
     670             : {
     671         670 :     return (tbm->nentries == 0);
     672             : }
     673             : 
     674             : /*
     675             :  * tbm_begin_iterate - prepare to iterate through a TIDBitmap
     676             :  *
     677             :  * The TBMIterator struct is created in the caller's memory context.
     678             :  * For a clean shutdown of the iteration, call tbm_end_iterate; but it's
     679             :  * okay to just allow the memory context to be released, too.  It is caller's
     680             :  * responsibility not to touch the TBMIterator anymore once the TIDBitmap
     681             :  * is freed.
     682             :  *
     683             :  * NB: after this is called, it is no longer allowed to modify the contents
     684             :  * of the bitmap.  However, you can call this multiple times to scan the
     685             :  * contents repeatedly, including parallel scans.
     686             :  */
     687             : TBMIterator *
     688       32512 : tbm_begin_iterate(TIDBitmap *tbm)
     689             : {
     690             :     TBMIterator *iterator;
     691             : 
     692             :     Assert(tbm->iterating != TBM_ITERATING_SHARED);
     693             : 
     694             :     /*
     695             :      * Create the TBMIterator struct, with enough trailing space to serve the
     696             :      * needs of the TBMIterateResult sub-struct.
     697             :      */
     698       32512 :     iterator = (TBMIterator *) palloc(sizeof(TBMIterator) +
     699             :                                       MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
     700       32512 :     iterator->tbm = tbm;
     701             : 
     702             :     /*
     703             :      * Initialize iteration pointers.
     704             :      */
     705       32512 :     iterator->spageptr = 0;
     706       32512 :     iterator->schunkptr = 0;
     707       32512 :     iterator->schunkbit = 0;
     708             : 
     709             :     /*
     710             :      * If we have a hashtable, create and fill the sorted page lists, unless
     711             :      * we already did that for a previous iterator.  Note that the lists are
     712             :      * attached to the bitmap not the iterator, so they can be used by more
     713             :      * than one iterator.
     714             :      */
     715       32512 :     if (tbm->status == TBM_HASH && tbm->iterating == TBM_NOT_ITERATING)
     716             :     {
     717             :         pagetable_iterator i;
     718             :         PagetableEntry *page;
     719             :         int         npages;
     720             :         int         nchunks;
     721             : 
     722        7778 :         if (!tbm->spages && tbm->npages > 0)
     723        4904 :             tbm->spages = (PagetableEntry **)
     724        4904 :                 MemoryContextAlloc(tbm->mcxt,
     725        4904 :                                    tbm->npages * sizeof(PagetableEntry *));
     726        7778 :         if (!tbm->schunks && tbm->nchunks > 0)
     727        2880 :             tbm->schunks = (PagetableEntry **)
     728        2880 :                 MemoryContextAlloc(tbm->mcxt,
     729        2880 :                                    tbm->nchunks * sizeof(PagetableEntry *));
     730             : 
     731        7778 :         npages = nchunks = 0;
     732        7778 :         pagetable_start_iterate(tbm->pagetable, &i);
     733      210916 :         while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
     734             :         {
     735      203138 :             if (page->ischunk)
     736        2922 :                 tbm->schunks[nchunks++] = page;
     737             :             else
     738      200216 :                 tbm->spages[npages++] = page;
     739             :         }
     740             :         Assert(npages == tbm->npages);
     741             :         Assert(nchunks == tbm->nchunks);
     742        7778 :         if (npages > 1)
     743        4900 :             qsort(tbm->spages, npages, sizeof(PagetableEntry *),
     744             :                   tbm_comparator);
     745        7778 :         if (nchunks > 1)
     746          12 :             qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
     747             :                   tbm_comparator);
     748             :     }
     749             : 
     750       32512 :     tbm->iterating = TBM_ITERATING_PRIVATE;
     751             : 
     752       32512 :     return iterator;
     753             : }
     754             : 
     755             : /*
     756             :  * tbm_prepare_shared_iterate - prepare shared iteration state for a TIDBitmap.
     757             :  *
     758             :  * The necessary shared state will be allocated from the DSA passed to
     759             :  * tbm_create, so that multiple processes can attach to it and iterate jointly.
     760             :  *
     761             :  * This will convert the pagetable hash into page and chunk array of the index
     762             :  * into pagetable array.
     763             :  */
     764             : dsa_pointer
     765         144 : tbm_prepare_shared_iterate(TIDBitmap *tbm)
     766             : {
     767             :     dsa_pointer dp;
     768             :     TBMSharedIteratorState *istate;
     769         144 :     PTEntryArray *ptbase = NULL;
     770         144 :     PTIterationArray *ptpages = NULL;
     771         144 :     PTIterationArray *ptchunks = NULL;
     772             : 
     773             :     Assert(tbm->dsa != NULL);
     774             :     Assert(tbm->iterating != TBM_ITERATING_PRIVATE);
     775             : 
     776             :     /*
     777             :      * Allocate TBMSharedIteratorState from DSA to hold the shared members and
     778             :      * lock, this will also be used by multiple worker for shared iterate.
     779             :      */
     780         144 :     dp = dsa_allocate0(tbm->dsa, sizeof(TBMSharedIteratorState));
     781         144 :     istate = dsa_get_address(tbm->dsa, dp);
     782             : 
     783             :     /*
     784             :      * If we're not already iterating, create and fill the sorted page lists.
     785             :      * (If we are, the sorted page lists are already stored in the TIDBitmap,
     786             :      * and we can just reuse them.)
     787             :      */
     788         144 :     if (tbm->iterating == TBM_NOT_ITERATING)
     789             :     {
     790             :         pagetable_iterator i;
     791             :         PagetableEntry *page;
     792             :         int         idx;
     793             :         int         npages;
     794             :         int         nchunks;
     795             : 
     796             :         /*
     797             :          * Allocate the page and chunk array memory from the DSA to share
     798             :          * across multiple processes.
     799             :          */
     800          72 :         if (tbm->npages)
     801             :         {
     802          72 :             tbm->ptpages = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
     803             :                                         tbm->npages * sizeof(int));
     804          72 :             ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
     805          72 :             pg_atomic_init_u32(&ptpages->refcount, 0);
     806             :         }
     807          72 :         if (tbm->nchunks)
     808             :         {
     809           6 :             tbm->ptchunks = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
     810             :                                          tbm->nchunks * sizeof(int));
     811           6 :             ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
     812           6 :             pg_atomic_init_u32(&ptchunks->refcount, 0);
     813             :         }
     814             : 
     815             :         /*
     816             :          * If TBM status is TBM_HASH then iterate over the pagetable and
     817             :          * convert it to page and chunk arrays.  But if it's in the
     818             :          * TBM_ONE_PAGE mode then directly allocate the space for one entry
     819             :          * from the DSA.
     820             :          */
     821          72 :         npages = nchunks = 0;
     822          72 :         if (tbm->status == TBM_HASH)
     823             :         {
     824          72 :             ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
     825             : 
     826          72 :             pagetable_start_iterate(tbm->pagetable, &i);
     827       27102 :             while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
     828             :             {
     829       27030 :                 idx = page - ptbase->ptentry;
     830       27030 :                 if (page->ischunk)
     831          24 :                     ptchunks->index[nchunks++] = idx;
     832             :                 else
     833       27006 :                     ptpages->index[npages++] = idx;
     834             :             }
     835             : 
     836             :             Assert(npages == tbm->npages);
     837             :             Assert(nchunks == tbm->nchunks);
     838             :         }
     839           0 :         else if (tbm->status == TBM_ONE_PAGE)
     840             :         {
     841             :             /*
     842             :              * In one page mode allocate the space for one pagetable entry,
     843             :              * initialize it, and directly store its index (i.e. 0) in the
     844             :              * page array.
     845             :              */
     846           0 :             tbm->dsapagetable = dsa_allocate(tbm->dsa, sizeof(PTEntryArray) +
     847             :                                              sizeof(PagetableEntry));
     848           0 :             ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
     849           0 :             memcpy(ptbase->ptentry, &tbm->entry1, sizeof(PagetableEntry));
     850           0 :             ptpages->index[0] = 0;
     851             :         }
     852             : 
     853          72 :         if (ptbase != NULL)
     854          72 :             pg_atomic_init_u32(&ptbase->refcount, 0);
     855          72 :         if (npages > 1)
     856          72 :             qsort_arg(ptpages->index, npages, sizeof(int),
     857          72 :                       tbm_shared_comparator, ptbase->ptentry);
     858          72 :         if (nchunks > 1)
     859           6 :             qsort_arg(ptchunks->index, nchunks, sizeof(int),
     860           6 :                       tbm_shared_comparator, ptbase->ptentry);
     861             :     }
     862             : 
     863             :     /*
     864             :      * Store the TBM members in the shared state so that we can share them
     865             :      * across multiple processes.
     866             :      */
     867         144 :     istate->nentries = tbm->nentries;
     868         144 :     istate->maxentries = tbm->maxentries;
     869         144 :     istate->npages = tbm->npages;
     870         144 :     istate->nchunks = tbm->nchunks;
     871         144 :     istate->pagetable = tbm->dsapagetable;
     872         144 :     istate->spages = tbm->ptpages;
     873         144 :     istate->schunks = tbm->ptchunks;
     874             : 
     875         144 :     ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
     876         144 :     ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
     877         144 :     ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
     878             : 
     879             :     /*
     880             :      * For every shared iterator, referring to pagetable and iterator array,
     881             :      * increase the refcount by 1 so that while freeing the shared iterator we
     882             :      * don't free pagetable and iterator array until its refcount becomes 0.
     883             :      */
     884         144 :     if (ptbase != NULL)
     885         144 :         pg_atomic_add_fetch_u32(&ptbase->refcount, 1);
     886         144 :     if (ptpages != NULL)
     887         144 :         pg_atomic_add_fetch_u32(&ptpages->refcount, 1);
     888         144 :     if (ptchunks != NULL)
     889          12 :         pg_atomic_add_fetch_u32(&ptchunks->refcount, 1);
     890             : 
     891             :     /* Initialize the iterator lock */
     892         144 :     LWLockInitialize(&istate->lock, LWTRANCHE_SHARED_TIDBITMAP);
     893             : 
     894             :     /* Initialize the shared iterator state */
     895         144 :     istate->schunkbit = 0;
     896         144 :     istate->schunkptr = 0;
     897         144 :     istate->spageptr = 0;
     898             : 
     899         144 :     tbm->iterating = TBM_ITERATING_SHARED;
     900             : 
     901         144 :     return dp;
     902             : }
     903             : 
     904             : /*
     905             :  * tbm_extract_page_tuple - extract the tuple offsets from a page
     906             :  *
     907             :  * The extracted offsets are stored into TBMIterateResult.
     908             :  */
     909             : static inline int
     910      459174 : tbm_extract_page_tuple(PagetableEntry *page, TBMIterateResult *output)
     911             : {
     912             :     int         wordnum;
     913      459174 :     int         ntuples = 0;
     914             : 
     915     2755044 :     for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
     916             :     {
     917     2295870 :         bitmapword  w = page->words[wordnum];
     918             : 
     919     2295870 :         if (w != 0)
     920             :         {
     921     1090270 :             int         off = wordnum * BITS_PER_BITMAPWORD + 1;
     922             : 
     923    47395218 :             while (w != 0)
     924             :             {
     925    46304948 :                 if (w & 1)
     926    11169200 :                     output->offsets[ntuples++] = (OffsetNumber) off;
     927    46304948 :                 off++;
     928    46304948 :                 w >>= 1;
     929             :             }
     930             :         }
     931             :     }
     932             : 
     933      459174 :     return ntuples;
     934             : }
     935             : 
     936             : /*
     937             :  *  tbm_advance_schunkbit - Advance the schunkbit
     938             :  */
     939             : static inline void
     940      332680 : tbm_advance_schunkbit(PagetableEntry *chunk, int *schunkbitp)
     941             : {
     942      332680 :     int         schunkbit = *schunkbitp;
     943             : 
     944     1526448 :     while (schunkbit < PAGES_PER_CHUNK)
     945             :     {
     946     1520556 :         int         wordnum = WORDNUM(schunkbit);
     947     1520556 :         int         bitnum = BITNUM(schunkbit);
     948             : 
     949     1520556 :         if ((chunk->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
     950      326788 :             break;
     951     1193768 :         schunkbit++;
     952             :     }
     953             : 
     954      332680 :     *schunkbitp = schunkbit;
     955      332680 : }
     956             : 
     957             : /*
     958             :  * tbm_iterate - scan through next page of a TIDBitmap
     959             :  *
     960             :  * Returns a TBMIterateResult representing one page, or NULL if there are
     961             :  * no more pages to scan.  Pages are guaranteed to be delivered in numerical
     962             :  * order.  If result->ntuples < 0, then the bitmap is "lossy" and failed to
     963             :  * remember the exact tuples to look at on this page --- the caller must
     964             :  * examine all tuples on the page and check if they meet the intended
     965             :  * condition.  If result->recheck is true, only the indicated tuples need
     966             :  * be examined, but the condition must be rechecked anyway.  (For ease of
     967             :  * testing, recheck is always set true when ntuples < 0.)
     968             :  */
     969             : TBMIterateResult *
     970      742606 : tbm_iterate(TBMIterator *iterator)
     971             : {
     972      742606 :     TIDBitmap  *tbm = iterator->tbm;
     973      742606 :     TBMIterateResult *output = &(iterator->output);
     974             : 
     975             :     Assert(tbm->iterating == TBM_ITERATING_PRIVATE);
     976             : 
     977             :     /*
     978             :      * If lossy chunk pages remain, make sure we've advanced schunkptr/
     979             :      * schunkbit to the next set bit.
     980             :      */
     981      748450 :     while (iterator->schunkptr < tbm->nchunks)
     982             :     {
     983      320380 :         PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
     984      320380 :         int         schunkbit = iterator->schunkbit;
     985             : 
     986      320380 :         tbm_advance_schunkbit(chunk, &schunkbit);
     987      320380 :         if (schunkbit < PAGES_PER_CHUNK)
     988             :         {
     989      314536 :             iterator->schunkbit = schunkbit;
     990      314536 :             break;
     991             :         }
     992             :         /* advance to next chunk */
     993        5844 :         iterator->schunkptr++;
     994        5844 :         iterator->schunkbit = 0;
     995             :     }
     996             : 
     997             :     /*
     998             :      * If both chunk and per-page data remain, must output the numerically
     999             :      * earlier page.
    1000             :      */
    1001      742606 :     if (iterator->schunkptr < tbm->nchunks)
    1002             :     {
    1003      314536 :         PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
    1004             :         BlockNumber chunk_blockno;
    1005             : 
    1006      314536 :         chunk_blockno = chunk->blockno + iterator->schunkbit;
    1007      314536 :         if (iterator->spageptr >= tbm->npages ||
    1008       18576 :             chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
    1009             :         {
    1010             :             /* Return a lossy page indicator from the chunk */
    1011      308380 :             output->blockno = chunk_blockno;
    1012      308380 :             output->ntuples = -1;
    1013      308380 :             output->recheck = true;
    1014      308380 :             iterator->schunkbit++;
    1015      308380 :             return output;
    1016             :         }
    1017             :     }
    1018             : 
    1019      434226 :     if (iterator->spageptr < tbm->npages)
    1020             :     {
    1021             :         PagetableEntry *page;
    1022             :         int         ntuples;
    1023             : 
    1024             :         /* In TBM_ONE_PAGE state, we don't allocate an spages[] array */
    1025      405162 :         if (tbm->status == TBM_ONE_PAGE)
    1026       11946 :             page = &tbm->entry1;
    1027             :         else
    1028      393216 :             page = tbm->spages[iterator->spageptr];
    1029             : 
    1030             :         /* scan bitmap to extract individual offset numbers */
    1031      405162 :         ntuples = tbm_extract_page_tuple(page, output);
    1032      405162 :         output->blockno = page->blockno;
    1033      405162 :         output->ntuples = ntuples;
    1034      405162 :         output->recheck = page->recheck;
    1035      405162 :         iterator->spageptr++;
    1036      405162 :         return output;
    1037             :     }
    1038             : 
    1039             :     /* Nothing more in the bitmap */
    1040       29064 :     return NULL;
    1041             : }
    1042             : 
    1043             : /*
    1044             :  *  tbm_shared_iterate - scan through next page of a TIDBitmap
    1045             :  *
    1046             :  *  As above, but this will iterate using an iterator which is shared
    1047             :  *  across multiple processes.  We need to acquire the iterator LWLock,
    1048             :  *  before accessing the shared members.
    1049             :  */
    1050             : TBMIterateResult *
    1051       60636 : tbm_shared_iterate(TBMSharedIterator *iterator)
    1052             : {
    1053       60636 :     TBMIterateResult *output = &iterator->output;
    1054       60636 :     TBMSharedIteratorState *istate = iterator->state;
    1055       60636 :     PagetableEntry *ptbase = NULL;
    1056       60636 :     int        *idxpages = NULL;
    1057       60636 :     int        *idxchunks = NULL;
    1058             : 
    1059       60636 :     if (iterator->ptbase != NULL)
    1060       60636 :         ptbase = iterator->ptbase->ptentry;
    1061       60636 :     if (iterator->ptpages != NULL)
    1062       60636 :         idxpages = iterator->ptpages->index;
    1063       60636 :     if (iterator->ptchunks != NULL)
    1064       14856 :         idxchunks = iterator->ptchunks->index;
    1065             : 
    1066             :     /* Acquire the LWLock before accessing the shared members */
    1067       60636 :     LWLockAcquire(&istate->lock, LW_EXCLUSIVE);
    1068             : 
    1069             :     /*
    1070             :      * If lossy chunk pages remain, make sure we've advanced schunkptr/
    1071             :      * schunkbit to the next set bit.
    1072             :      */
    1073       60684 :     while (istate->schunkptr < istate->nchunks)
    1074             :     {
    1075       12300 :         PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
    1076       12300 :         int         schunkbit = istate->schunkbit;
    1077             : 
    1078       12300 :         tbm_advance_schunkbit(chunk, &schunkbit);
    1079       12300 :         if (schunkbit < PAGES_PER_CHUNK)
    1080             :         {
    1081       12252 :             istate->schunkbit = schunkbit;
    1082       12252 :             break;
    1083             :         }
    1084             :         /* advance to next chunk */
    1085          48 :         istate->schunkptr++;
    1086          48 :         istate->schunkbit = 0;
    1087             :     }
    1088             : 
    1089             :     /*
    1090             :      * If both chunk and per-page data remain, must output the numerically
    1091             :      * earlier page.
    1092             :      */
    1093       60636 :     if (istate->schunkptr < istate->nchunks)
    1094             :     {
    1095       12252 :         PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
    1096             :         BlockNumber chunk_blockno;
    1097             : 
    1098       12252 :         chunk_blockno = chunk->blockno + istate->schunkbit;
    1099             : 
    1100       12252 :         if (istate->spageptr >= istate->npages ||
    1101       12252 :             chunk_blockno < ptbase[idxpages[istate->spageptr]].blockno)
    1102             :         {
    1103             :             /* Return a lossy page indicator from the chunk */
    1104        6204 :             output->blockno = chunk_blockno;
    1105        6204 :             output->ntuples = -1;
    1106        6204 :             output->recheck = true;
    1107        6204 :             istate->schunkbit++;
    1108             : 
    1109        6204 :             LWLockRelease(&istate->lock);
    1110        6204 :             return output;
    1111             :         }
    1112             :     }
    1113             : 
    1114       54432 :     if (istate->spageptr < istate->npages)
    1115             :     {
    1116       54012 :         PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
    1117             :         int         ntuples;
    1118             : 
    1119             :         /* scan bitmap to extract individual offset numbers */
    1120       54012 :         ntuples = tbm_extract_page_tuple(page, output);
    1121       54012 :         output->blockno = page->blockno;
    1122       54012 :         output->ntuples = ntuples;
    1123       54012 :         output->recheck = page->recheck;
    1124       54012 :         istate->spageptr++;
    1125             : 
    1126       54012 :         LWLockRelease(&istate->lock);
    1127             : 
    1128       54012 :         return output;
    1129             :     }
    1130             : 
    1131         420 :     LWLockRelease(&istate->lock);
    1132             : 
    1133             :     /* Nothing more in the bitmap */
    1134         420 :     return NULL;
    1135             : }
    1136             : 
    1137             : /*
    1138             :  * tbm_end_iterate - finish an iteration over a TIDBitmap
    1139             :  *
    1140             :  * Currently this is just a pfree, but it might do more someday.  (For
    1141             :  * instance, it could be useful to count open iterators and allow the
    1142             :  * bitmap to return to read/write status when there are no more iterators.)
    1143             :  */
    1144             : void
    1145       32434 : tbm_end_iterate(TBMIterator *iterator)
    1146             : {
    1147       32434 :     pfree(iterator);
    1148       32434 : }
    1149             : 
    1150             : /*
    1151             :  * tbm_end_shared_iterate - finish a shared iteration over a TIDBitmap
    1152             :  *
    1153             :  * This doesn't free any of the shared state associated with the iterator,
    1154             :  * just our backend-private state.
    1155             :  */
    1156             : void
    1157         696 : tbm_end_shared_iterate(TBMSharedIterator *iterator)
    1158             : {
    1159         696 :     pfree(iterator);
    1160         696 : }
    1161             : 
    1162             : /*
    1163             :  * tbm_find_pageentry - find a PagetableEntry for the pageno
    1164             :  *
    1165             :  * Returns NULL if there is no non-lossy entry for the pageno.
    1166             :  */
    1167             : static const PagetableEntry *
    1168        5048 : tbm_find_pageentry(const TIDBitmap *tbm, BlockNumber pageno)
    1169             : {
    1170             :     const PagetableEntry *page;
    1171             : 
    1172        5048 :     if (tbm->nentries == 0)      /* in case pagetable doesn't exist */
    1173           0 :         return NULL;
    1174             : 
    1175        5048 :     if (tbm->status == TBM_ONE_PAGE)
    1176             :     {
    1177           0 :         page = &tbm->entry1;
    1178           0 :         if (page->blockno != pageno)
    1179           0 :             return NULL;
    1180             :         Assert(!page->ischunk);
    1181           0 :         return page;
    1182             :     }
    1183             : 
    1184        5048 :     page = pagetable_lookup(tbm->pagetable, pageno);
    1185        5048 :     if (page == NULL)
    1186         512 :         return NULL;
    1187        4536 :     if (page->ischunk)
    1188           0 :         return NULL;            /* don't want a lossy chunk header */
    1189        4536 :     return page;
    1190             : }
    1191             : 
    1192             : /*
    1193             :  * tbm_get_pageentry - find or create a PagetableEntry for the pageno
    1194             :  *
    1195             :  * If new, the entry is marked as an exact (non-chunk) entry.
    1196             :  *
    1197             :  * This may cause the table to exceed the desired memory size.  It is
    1198             :  * up to the caller to call tbm_lossify() at the next safe point if so.
    1199             :  */
    1200             : static PagetableEntry *
    1201     7086968 : tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
    1202             : {
    1203             :     PagetableEntry *page;
    1204             :     bool        found;
    1205             : 
    1206     7086968 :     if (tbm->status == TBM_EMPTY)
    1207             :     {
    1208             :         /* Use the fixed slot */
    1209       11148 :         page = &tbm->entry1;
    1210       11148 :         found = false;
    1211       11148 :         tbm->status = TBM_ONE_PAGE;
    1212             :     }
    1213             :     else
    1214             :     {
    1215     7075820 :         if (tbm->status == TBM_ONE_PAGE)
    1216             :         {
    1217       78422 :             page = &tbm->entry1;
    1218       78422 :             if (page->blockno == pageno)
    1219       73372 :                 return page;
    1220             :             /* Time to switch from one page to a hashtable */
    1221        5050 :             tbm_create_pagetable(tbm);
    1222             :         }
    1223             : 
    1224             :         /* Look up or create an entry */
    1225     7002448 :         page = pagetable_insert(tbm->pagetable, pageno, &found);
    1226             :     }
    1227             : 
    1228             :     /* Initialize it if not present before */
    1229     7013596 :     if (!found)
    1230             :     {
    1231      255280 :         char        oldstatus = page->status;
    1232             : 
    1233     1786960 :         MemSet(page, 0, sizeof(PagetableEntry));
    1234      255280 :         page->status = oldstatus;
    1235      255280 :         page->blockno = pageno;
    1236             :         /* must count it too */
    1237      255280 :         tbm->nentries++;
    1238      255280 :         tbm->npages++;
    1239             :     }
    1240             : 
    1241     7013596 :     return page;
    1242             : }
    1243             : 
    1244             : /*
    1245             :  * tbm_page_is_lossy - is the page marked as lossily stored?
    1246             :  */
    1247             : static bool
    1248     7097728 : tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
    1249             : {
    1250             :     PagetableEntry *page;
    1251             :     BlockNumber chunk_pageno;
    1252             :     int         bitno;
    1253             : 
    1254             :     /* we can skip the lookup if there are no lossy chunks */
    1255     7097728 :     if (tbm->nchunks == 0)
    1256     6977098 :         return false;
    1257             :     Assert(tbm->status == TBM_HASH);
    1258             : 
    1259      120630 :     bitno = pageno % PAGES_PER_CHUNK;
    1260      120630 :     chunk_pageno = pageno - bitno;
    1261             : 
    1262      120630 :     page = pagetable_lookup(tbm->pagetable, chunk_pageno);
    1263             : 
    1264      120630 :     if (page != NULL && page->ischunk)
    1265             :     {
    1266       12432 :         int         wordnum = WORDNUM(bitno);
    1267       12432 :         int         bitnum = BITNUM(bitno);
    1268             : 
    1269       12432 :         if ((page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
    1270        5712 :             return true;
    1271             :     }
    1272      114918 :     return false;
    1273             : }
    1274             : 
    1275             : /*
    1276             :  * tbm_mark_page_lossy - mark the page number as lossily stored
    1277             :  *
    1278             :  * This may cause the table to exceed the desired memory size.  It is
    1279             :  * up to the caller to call tbm_lossify() at the next safe point if so.
    1280             :  */
    1281             : static void
    1282      160292 : tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
    1283             : {
    1284             :     PagetableEntry *page;
    1285             :     bool        found;
    1286             :     BlockNumber chunk_pageno;
    1287             :     int         bitno;
    1288             :     int         wordnum;
    1289             :     int         bitnum;
    1290             : 
    1291             :     /* We force the bitmap into hashtable mode whenever it's lossy */
    1292      160292 :     if (tbm->status != TBM_HASH)
    1293        2868 :         tbm_create_pagetable(tbm);
    1294             : 
    1295      160292 :     bitno = pageno % PAGES_PER_CHUNK;
    1296      160292 :     chunk_pageno = pageno - bitno;
    1297             : 
    1298             :     /*
    1299             :      * Remove any extant non-lossy entry for the page.  If the page is its own
    1300             :      * chunk header, however, we skip this and handle the case below.
    1301             :      */
    1302      160292 :     if (bitno != 0)
    1303             :     {
    1304      157964 :         if (pagetable_delete(tbm->pagetable, pageno))
    1305             :         {
    1306             :             /* It was present, so adjust counts */
    1307       12312 :             tbm->nentries--;
    1308       12312 :             tbm->npages--;       /* assume it must have been non-lossy */
    1309             :         }
    1310             :     }
    1311             : 
    1312             :     /* Look up or create entry for chunk-header page */
    1313      160292 :     page = pagetable_insert(tbm->pagetable, chunk_pageno, &found);
    1314             : 
    1315             :     /* Initialize it if not present before */
    1316      160292 :     if (!found)
    1317             :     {
    1318        2868 :         char        oldstatus = page->status;
    1319             : 
    1320       20076 :         MemSet(page, 0, sizeof(PagetableEntry));
    1321        2868 :         page->status = oldstatus;
    1322        2868 :         page->blockno = chunk_pageno;
    1323        2868 :         page->ischunk = true;
    1324             :         /* must count it too */
    1325        2868 :         tbm->nentries++;
    1326        2868 :         tbm->nchunks++;
    1327             :     }
    1328      157424 :     else if (!page->ischunk)
    1329             :     {
    1330         102 :         char        oldstatus = page->status;
    1331             : 
    1332             :         /* chunk header page was formerly non-lossy, make it lossy */
    1333         714 :         MemSet(page, 0, sizeof(PagetableEntry));
    1334         102 :         page->status = oldstatus;
    1335         102 :         page->blockno = chunk_pageno;
    1336         102 :         page->ischunk = true;
    1337             :         /* we assume it had some tuple bit(s) set, so mark it lossy */
    1338         102 :         page->words[0] = ((bitmapword) 1 << 0);
    1339             :         /* adjust counts */
    1340         102 :         tbm->nchunks++;
    1341         102 :         tbm->npages--;
    1342             :     }
    1343             : 
    1344             :     /* Now set the original target page's bit */
    1345      160292 :     wordnum = WORDNUM(bitno);
    1346      160292 :     bitnum = BITNUM(bitno);
    1347      160292 :     page->words[wordnum] |= ((bitmapword) 1 << bitnum);
    1348      160292 : }
    1349             : 
    1350             : /*
    1351             :  * tbm_lossify - lose some information to get back under the memory limit
    1352             :  */
    1353             : static void
    1354          24 : tbm_lossify(TIDBitmap *tbm)
    1355             : {
    1356             :     pagetable_iterator i;
    1357             :     PagetableEntry *page;
    1358             : 
    1359             :     /*
    1360             :      * XXX Really stupid implementation: this just lossifies pages in
    1361             :      * essentially random order.  We should be paying some attention to the
    1362             :      * number of bits set in each page, instead.
    1363             :      *
    1364             :      * Since we are called as soon as nentries exceeds maxentries, we should
    1365             :      * push nentries down to significantly less than maxentries, or else we'll
    1366             :      * just end up doing this again very soon.  We shoot for maxentries/2.
    1367             :      */
    1368             :     Assert(tbm->iterating == TBM_NOT_ITERATING);
    1369             :     Assert(tbm->status == TBM_HASH);
    1370             : 
    1371          24 :     pagetable_start_iterate_at(tbm->pagetable, &i, tbm->lossify_start);
    1372       12330 :     while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
    1373             :     {
    1374       12330 :         if (page->ischunk)
    1375           0 :             continue;           /* already a chunk header */
    1376             : 
    1377             :         /*
    1378             :          * If the page would become a chunk header, we won't save anything by
    1379             :          * converting it to lossy, so skip it.
    1380             :          */
    1381       12330 :         if ((page->blockno % PAGES_PER_CHUNK) == 0)
    1382          18 :             continue;
    1383             : 
    1384             :         /* This does the dirty work ... */
    1385       12312 :         tbm_mark_page_lossy(tbm, page->blockno);
    1386             : 
    1387       12312 :         if (tbm->nentries <= tbm->maxentries / 2)
    1388             :         {
    1389             :             /*
    1390             :              * We have made enough room. Remember where to start lossifying
    1391             :              * next round, so we evenly iterate over the hashtable.
    1392             :              */
    1393          24 :             tbm->lossify_start = i.cur;
    1394          24 :             break;
    1395             :         }
    1396             : 
    1397             :         /*
    1398             :          * Note: tbm_mark_page_lossy may have inserted a lossy chunk into the
    1399             :          * hashtable and may have deleted the non-lossy chunk.  We can
    1400             :          * continue the same hash table scan, since failure to visit one
    1401             :          * element or visiting the newly inserted element, isn't fatal.
    1402             :          */
    1403             :     }
    1404             : 
    1405             :     /*
    1406             :      * With a big bitmap and small work_mem, it's possible that we cannot get
    1407             :      * under maxentries.  Again, if that happens, we'd end up uselessly
    1408             :      * calling tbm_lossify over and over.  To prevent this from becoming a
    1409             :      * performance sink, force maxentries up to at least double the current
    1410             :      * number of entries.  (In essence, we're admitting inability to fit
    1411             :      * within work_mem when we do this.)  Note that this test will not fire if
    1412             :      * we broke out of the loop early; and if we didn't, the current number of
    1413             :      * entries is simply not reducible any further.
    1414             :      */
    1415          24 :     if (tbm->nentries > tbm->maxentries / 2)
    1416           0 :         tbm->maxentries = Min(tbm->nentries, (INT_MAX - 1) / 2) * 2;
    1417          24 : }
    1418             : 
    1419             : /*
    1420             :  * qsort comparator to handle PagetableEntry pointers.
    1421             :  */
    1422             : static int
    1423     1342562 : tbm_comparator(const void *left, const void *right)
    1424             : {
    1425     1342562 :     BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
    1426     1342562 :     BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
    1427             : 
    1428     1342562 :     if (l < r)
    1429      620542 :         return -1;
    1430      722020 :     else if (l > r)
    1431      722020 :         return 1;
    1432           0 :     return 0;
    1433             : }
    1434             : 
    1435             : /*
    1436             :  * As above, but this will get index into PagetableEntry array.  Therefore,
    1437             :  * it needs to get actual PagetableEntry using the index before comparing the
    1438             :  * blockno.
    1439             :  */
    1440             : static int
    1441      238290 : tbm_shared_comparator(const void *left, const void *right, void *arg)
    1442             : {
    1443      238290 :     PagetableEntry *base = (PagetableEntry *) arg;
    1444      238290 :     PagetableEntry *lpage = &base[*(int *) left];
    1445      238290 :     PagetableEntry *rpage = &base[*(int *) right];
    1446             : 
    1447      238290 :     if (lpage->blockno < rpage->blockno)
    1448      108966 :         return -1;
    1449      129324 :     else if (lpage->blockno > rpage->blockno)
    1450      129324 :         return 1;
    1451           0 :     return 0;
    1452             : }
    1453             : 
    1454             : /*
    1455             :  *  tbm_attach_shared_iterate
    1456             :  *
    1457             :  *  Allocate a backend-private iterator and attach the shared iterator state
    1458             :  *  to it so that multiple processed can iterate jointly.
    1459             :  *
    1460             :  *  We also converts the DSA pointers to local pointers and store them into
    1461             :  *  our private iterator.
    1462             :  */
    1463             : TBMSharedIterator *
    1464         696 : tbm_attach_shared_iterate(dsa_area *dsa, dsa_pointer dp)
    1465             : {
    1466             :     TBMSharedIterator *iterator;
    1467             :     TBMSharedIteratorState *istate;
    1468             : 
    1469             :     /*
    1470             :      * Create the TBMSharedIterator struct, with enough trailing space to
    1471             :      * serve the needs of the TBMIterateResult sub-struct.
    1472             :      */
    1473         696 :     iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator) +
    1474             :                                              MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
    1475             : 
    1476         696 :     istate = (TBMSharedIteratorState *) dsa_get_address(dsa, dp);
    1477             : 
    1478         696 :     iterator->state = istate;
    1479             : 
    1480         696 :     iterator->ptbase = dsa_get_address(dsa, istate->pagetable);
    1481             : 
    1482         696 :     if (istate->npages)
    1483         696 :         iterator->ptpages = dsa_get_address(dsa, istate->spages);
    1484         696 :     if (istate->nchunks)
    1485          60 :         iterator->ptchunks = dsa_get_address(dsa, istate->schunks);
    1486             : 
    1487         696 :     return iterator;
    1488             : }
    1489             : 
    1490             : /*
    1491             :  * pagetable_allocate
    1492             :  *
    1493             :  * Callback function for allocating the memory for hashtable elements.
    1494             :  * Allocate memory for hashtable elements, using DSA if available.
    1495             :  */
    1496             : static inline void *
    1497        8268 : pagetable_allocate(pagetable_hash *pagetable, Size size)
    1498             : {
    1499        8268 :     TIDBitmap  *tbm = (TIDBitmap *) pagetable->private_data;
    1500             :     PTEntryArray *ptbase;
    1501             : 
    1502        8268 :     if (tbm->dsa == NULL)
    1503        8112 :         return MemoryContextAllocExtended(pagetable->ctx, size,
    1504             :                                           MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO);
    1505             : 
    1506             :     /*
    1507             :      * Save the dsapagetable reference in dsapagetableold before allocating
    1508             :      * new memory so that pagetable_free can free the old entry.
    1509             :      */
    1510         156 :     tbm->dsapagetableold = tbm->dsapagetable;
    1511         156 :     tbm->dsapagetable = dsa_allocate_extended(tbm->dsa,
    1512             :                                               sizeof(PTEntryArray) + size,
    1513             :                                               DSA_ALLOC_HUGE | DSA_ALLOC_ZERO);
    1514         156 :     ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
    1515             : 
    1516         156 :     return ptbase->ptentry;
    1517             : }
    1518             : 
    1519             : /*
    1520             :  * pagetable_free
    1521             :  *
    1522             :  * Callback function for freeing hash table elements.
    1523             :  */
    1524             : static inline void
    1525        8264 : pagetable_free(pagetable_hash *pagetable, void *pointer)
    1526             : {
    1527        8264 :     TIDBitmap  *tbm = (TIDBitmap *) pagetable->private_data;
    1528             : 
    1529             :     /* pfree the input pointer if DSA is not available */
    1530        8264 :     if (tbm->dsa == NULL)
    1531        8108 :         pfree(pointer);
    1532         156 :     else if (DsaPointerIsValid(tbm->dsapagetableold))
    1533             :     {
    1534          84 :         dsa_free(tbm->dsa, tbm->dsapagetableold);
    1535          84 :         tbm->dsapagetableold = InvalidDsaPointer;
    1536             :     }
    1537        8264 : }
    1538             : 
    1539             : /*
    1540             :  * tbm_calculate_entries
    1541             :  *
    1542             :  * Estimate number of hashtable entries we can have within maxbytes.
    1543             :  */
    1544             : long
    1545      532584 : tbm_calculate_entries(double maxbytes)
    1546             : {
    1547             :     long        nbuckets;
    1548             : 
    1549             :     /*
    1550             :      * Estimate number of hashtable entries we can have within maxbytes. This
    1551             :      * estimates the hash cost as sizeof(PagetableEntry), which is good enough
    1552             :      * for our purpose.  Also count an extra Pointer per entry for the arrays
    1553             :      * created during iteration readout.
    1554             :      */
    1555      532584 :     nbuckets = maxbytes /
    1556             :         (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
    1557      532584 :     nbuckets = Min(nbuckets, INT_MAX - 1);  /* safety limit */
    1558      532584 :     nbuckets = Max(nbuckets, 16);   /* sanity limit */
    1559             : 
    1560      532584 :     return nbuckets;
    1561             : }

Generated by: LCOV version 1.14