Debian Codegraph @

src/backend/nodes/tidbitmap.c

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