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