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 *
269 tgl@sss.pgh.pa.us 256 :CBC 10216 : tbm_create(Size maxbytes, dsa_area *dsa)
257 : : {
258 : : TIDBitmap *tbm;
259 : :
260 : : /* Create the TIDBitmap struct and zero all its fields */
6134 261 : 10216 : tbm = makeNode(TIDBitmap);
262 : :
7498 263 : 10216 : tbm->mcxt = CurrentMemoryContext;
7468 264 : 10216 : tbm->status = TBM_EMPTY;
265 : :
269 266 : 10216 : tbm->maxentries = tbm_calculate_entries(maxbytes);
3300 andres@anarazel.de 267 : 10216 : tbm->lossify_start = 0;
3155 rhaas@postgresql.org 268 : 10216 : tbm->dsa = dsa;
3147 269 : 10216 : tbm->dsapagetable = InvalidDsaPointer;
270 : 10216 : tbm->dsapagetableold = InvalidDsaPointer;
271 : 10216 : tbm->ptpages = InvalidDsaPointer;
272 : 10216 : tbm->ptchunks = InvalidDsaPointer;
273 : :
7468 tgl@sss.pgh.pa.us 274 : 10216 : 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 : 4545 : tbm_create_pagetable(TIDBitmap *tbm)
283 : : {
284 [ - + ]: 4545 : Assert(tbm->status != TBM_HASH);
285 [ - + ]: 4545 : Assert(tbm->pagetable == NULL);
286 : :
3155 rhaas@postgresql.org 287 : 4545 : tbm->pagetable = pagetable_create(tbm->mcxt, 128, tbm);
288 : :
289 : : /* If entry1 is valid, push it into the hashtable */
7468 tgl@sss.pgh.pa.us 290 [ + + ]: 4545 : if (tbm->status == TBM_ONE_PAGE)
291 : : {
292 : : PagetableEntry *page;
293 : : bool found;
294 : : char oldstatus;
295 : :
3300 andres@anarazel.de 296 : 3111 : page = pagetable_insert(tbm->pagetable,
297 : : tbm->entry1.blockno,
298 : : &found);
7468 tgl@sss.pgh.pa.us 299 [ - + ]: 3111 : Assert(!found);
3300 andres@anarazel.de 300 : 3111 : oldstatus = page->status;
7468 tgl@sss.pgh.pa.us 301 : 3111 : memcpy(page, &tbm->entry1, sizeof(PagetableEntry));
3300 andres@anarazel.de 302 : 3111 : page->status = oldstatus;
303 : : }
304 : :
7468 tgl@sss.pgh.pa.us 305 : 4545 : tbm->status = TBM_HASH;
7498 306 : 4545 : }
307 : :
308 : : /*
309 : : * tbm_free - free a TIDBitmap
310 : : */
311 : : void
312 : 10159 : tbm_free(TIDBitmap *tbm)
313 : : {
7468 314 [ + + ]: 10159 : if (tbm->pagetable)
3300 andres@anarazel.de 315 : 4543 : pagetable_destroy(tbm->pagetable);
7498 tgl@sss.pgh.pa.us 316 [ + + ]: 10159 : if (tbm->spages)
317 : 2973 : pfree(tbm->spages);
318 [ + + ]: 10159 : if (tbm->schunks)
319 : 1443 : pfree(tbm->schunks);
320 : 10159 : pfree(tbm);
321 : 10159 : }
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
3155 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 : :
3147 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 : : {
3155 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 : : }
3147 350 [ - + ]: 27 : if (DsaPointerIsValid(istate->schunks))
351 : : {
3155 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 : :
3155 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
6409 tgl@sss.pgh.pa.us 367 : 3247156 : tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids,
368 : : bool recheck)
369 : : {
3937 370 : 3247156 : BlockNumber currblk = InvalidBlockNumber;
371 : 3247156 : PagetableEntry *page = NULL; /* only valid when currblk is valid */
372 : : int i;
373 : :
3155 rhaas@postgresql.org 374 [ - + ]: 3247156 : Assert(tbm->iterating == TBM_NOT_ITERATING);
7498 tgl@sss.pgh.pa.us 375 [ + + ]: 7585041 : for (i = 0; i < ntids; i++)
376 : : {
377 : 4337885 : BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
378 : 4337885 : OffsetNumber off = ItemPointerGetOffsetNumber(tids + i);
379 : : int wordnum,
380 : : bitnum;
381 : :
382 : : /* safety check to ensure we don't overrun bit array bounds */
245 melanieplageman@gmai 383 [ + - - + ]: 4337885 : if (off < 1 || off > TBM_MAX_TUPLES_PER_PAGE)
7498 tgl@sss.pgh.pa.us 384 [ # # ]:UBC 0 : elog(ERROR, "tuple offset out of range: %u", off);
385 : :
386 : : /*
387 : : * Look up target page unless we already did. This saves cycles when
388 : : * the input includes consecutive tuples on the same page, which is
389 : : * common enough to justify an extra test here.
390 : : */
3937 tgl@sss.pgh.pa.us 391 [ + + ]:CBC 4337885 : if (blk != currblk)
392 : : {
andres@anarazel.de 393 [ + + ]: 3635511 : if (tbm_page_is_lossy(tbm, blk))
tgl@sss.pgh.pa.us 394 : 1428 : page = NULL; /* remember page is lossy */
395 : : else
396 : 3634083 : page = tbm_get_pageentry(tbm, blk);
397 : 3635511 : currblk = blk;
398 : : }
399 : :
400 [ + + ]: 4337885 : if (page == NULL)
401 : 1428 : continue; /* whole page is already marked */
402 : :
7498 403 [ - + ]: 4336457 : if (page->ischunk)
404 : : {
405 : : /* The page is a lossy chunk header, set bit for itself */
7498 tgl@sss.pgh.pa.us 406 :UBC 0 : wordnum = bitnum = 0;
407 : : }
408 : : else
409 : : {
410 : : /* Page is exact, so set bit for individual tuple */
7498 tgl@sss.pgh.pa.us 411 :CBC 4336457 : wordnum = WORDNUM(off - 1);
412 : 4336457 : bitnum = BITNUM(off - 1);
413 : : }
414 : 4336457 : page->words[wordnum] |= ((bitmapword) 1 << bitnum);
6409 415 : 4336457 : page->recheck |= recheck;
416 : :
7498 417 [ + + ]: 4336457 : if (tbm->nentries > tbm->maxentries)
418 : : {
419 : 18 : tbm_lossify(tbm);
420 : : /* Page could have been converted to lossy, so force new lookup */
3937 421 : 18 : currblk = InvalidBlockNumber;
422 : : }
423 : : }
7498 424 : 3247156 : }
425 : :
426 : : /*
427 : : * tbm_add_page - add a whole page to a TIDBitmap
428 : : *
429 : : * This causes the whole page to be reported (with the recheck flag)
430 : : * when the TIDBitmap is scanned.
431 : : */
432 : : void
6061 433 : 73980 : tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
434 : : {
435 : : /* Enter the page in the bitmap, or mark it lossy if already present */
436 : 73980 : tbm_mark_page_lossy(tbm, pageno);
437 : : /* If we went over the memory limit, lossify some more pages */
438 [ - + ]: 73980 : if (tbm->nentries > tbm->maxentries)
6061 tgl@sss.pgh.pa.us 439 :UBC 0 : tbm_lossify(tbm);
6061 tgl@sss.pgh.pa.us 440 :CBC 73980 : }
441 : :
442 : : /*
443 : : * tbm_union - set union
444 : : *
445 : : * a is modified in-place, b is not changed
446 : : */
447 : : void
7498 tgl@sss.pgh.pa.us 448 :UBC 0 : tbm_union(TIDBitmap *a, const TIDBitmap *b)
449 : : {
7468 450 [ # # ]: 0 : Assert(!a->iterating);
451 : : /* Nothing to do if b is empty */
452 [ # # ]: 0 : if (b->nentries == 0)
453 : 0 : return;
454 : : /* Scan through chunks and pages in b, merge into a */
455 [ # # ]: 0 : if (b->status == TBM_ONE_PAGE)
456 : 0 : tbm_union_page(a, &b->entry1);
457 : : else
458 : : {
459 : : pagetable_iterator i;
460 : : PagetableEntry *bpage;
461 : :
462 [ # # ]: 0 : Assert(b->status == TBM_HASH);
3300 andres@anarazel.de 463 : 0 : pagetable_start_iterate(b->pagetable, &i);
464 [ # # ]: 0 : while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
7468 tgl@sss.pgh.pa.us 465 : 0 : tbm_union_page(a, bpage);
466 : : }
467 : : }
468 : :
469 : : /* Process one page of b during a union op */
470 : : static void
471 : 0 : tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
472 : : {
473 : : PagetableEntry *apage;
474 : : int wordnum;
475 : :
476 [ # # ]: 0 : if (bpage->ischunk)
477 : : {
478 : : /* Scan b's chunk, mark each indicated page lossy in a */
4364 479 [ # # ]: 0 : for (wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
480 : : {
7468 481 : 0 : bitmapword w = bpage->words[wordnum];
482 : :
483 [ # # ]: 0 : if (w != 0)
484 : : {
485 : : BlockNumber pg;
486 : :
487 : 0 : pg = bpage->blockno + (wordnum * BITS_PER_BITMAPWORD);
488 [ # # ]: 0 : while (w != 0)
489 : : {
490 [ # # ]: 0 : if (w & 1)
491 : 0 : tbm_mark_page_lossy(a, pg);
492 : 0 : pg++;
493 : 0 : w >>= 1;
494 : : }
495 : : }
496 : : }
497 : : }
498 [ # # ]: 0 : else if (tbm_page_is_lossy(a, bpage->blockno))
499 : : {
500 : : /* page is already lossy in a, nothing to do */
501 : 0 : return;
502 : : }
503 : : else
504 : : {
505 : 0 : apage = tbm_get_pageentry(a, bpage->blockno);
506 [ # # ]: 0 : if (apage->ischunk)
507 : : {
508 : : /* The page is a lossy chunk header, set bit for itself */
509 : 0 : apage->words[0] |= ((bitmapword) 1 << 0);
510 : : }
511 : : else
512 : : {
513 : : /* Both pages are exact, merge at the bit level */
514 [ # # ]: 0 : for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
515 : 0 : apage->words[wordnum] |= bpage->words[wordnum];
6409 516 : 0 : apage->recheck |= bpage->recheck;
517 : : }
518 : : }
519 : :
7468 520 [ # # ]: 0 : if (a->nentries > a->maxentries)
521 : 0 : tbm_lossify(a);
522 : : }
523 : :
524 : : /*
525 : : * tbm_intersect - set intersection
526 : : *
527 : : * a is modified in-place, b is not changed
528 : : */
529 : : void
7498 tgl@sss.pgh.pa.us 530 :CBC 97 : tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
531 : : {
532 [ - + ]: 97 : Assert(!a->iterating);
533 : : /* Nothing to do if a is empty */
7468 534 [ - + ]: 97 : if (a->nentries == 0)
7468 tgl@sss.pgh.pa.us 535 :UBC 0 : return;
536 : : /* Scan through chunks and pages in a, try to match to b */
7468 tgl@sss.pgh.pa.us 537 [ + + ]:CBC 97 : if (a->status == TBM_ONE_PAGE)
538 : : {
7400 539 [ - + ]: 58 : if (tbm_intersect_page(a, &a->entry1, b))
540 : : {
541 : : /* Page is now empty, remove it from a */
7468 tgl@sss.pgh.pa.us 542 [ # # ]:UBC 0 : Assert(!a->entry1.ischunk);
543 : 0 : a->npages--;
544 : 0 : a->nentries--;
545 [ # # ]: 0 : Assert(a->nentries == 0);
546 : 0 : a->status = TBM_EMPTY;
547 : : }
548 : : }
549 : : else
550 : : {
551 : : pagetable_iterator i;
552 : : PagetableEntry *apage;
553 : :
7468 tgl@sss.pgh.pa.us 554 [ - + ]:CBC 39 : Assert(a->status == TBM_HASH);
3300 andres@anarazel.de 555 : 39 : pagetable_start_iterate(a->pagetable, &i);
556 [ + + ]: 5632 : while ((apage = pagetable_iterate(a->pagetable, &i)) != NULL)
557 : : {
7400 tgl@sss.pgh.pa.us 558 [ + + ]: 5554 : if (tbm_intersect_page(a, apage, b))
559 : : {
560 : : /* Page or chunk is now empty, remove it from a */
7468 561 [ - + ]: 5266 : if (apage->ischunk)
7468 tgl@sss.pgh.pa.us 562 :UBC 0 : a->nchunks--;
563 : : else
7468 tgl@sss.pgh.pa.us 564 :CBC 5266 : a->npages--;
565 : 5266 : a->nentries--;
3300 andres@anarazel.de 566 [ - + ]: 5266 : if (!pagetable_delete(a->pagetable, apage->blockno))
7498 tgl@sss.pgh.pa.us 567 [ # # ]:UBC 0 : elog(ERROR, "hash table corrupted");
568 : : }
569 : : }
570 : : }
571 : : }
572 : :
573 : : /*
574 : : * Process one page of a during an intersection op
575 : : *
576 : : * Returns true if apage is now empty and should be deleted from a
577 : : */
578 : : static bool
7400 tgl@sss.pgh.pa.us 579 :CBC 5612 : tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
580 : : {
581 : : const PagetableEntry *bpage;
582 : : int wordnum;
583 : :
7468 584 [ + + ]: 5612 : if (apage->ischunk)
585 : : {
586 : : /* Scan each bit in chunk, try to clear */
7317 bruce@momjian.us 587 : 30 : bool candelete = true;
588 : :
4364 tgl@sss.pgh.pa.us 589 [ + + ]: 150 : for (wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
590 : : {
7468 591 : 120 : bitmapword w = apage->words[wordnum];
592 : :
593 [ + + ]: 120 : if (w != 0)
594 : : {
595 : 108 : bitmapword neww = w;
596 : : BlockNumber pg;
597 : : int bitnum;
598 : :
599 : 108 : pg = apage->blockno + (wordnum * BITS_PER_BITMAPWORD);
600 : 108 : bitnum = 0;
601 [ + + ]: 6606 : while (w != 0)
602 : : {
603 [ + + ]: 6498 : if (w & 1)
604 : : {
605 [ + + - + ]: 3360 : if (!tbm_page_is_lossy(b, pg) &&
606 : 252 : tbm_find_pageentry(b, pg) == NULL)
607 : : {
608 : : /* Page is not in b at all, lose lossy bit */
7468 tgl@sss.pgh.pa.us 609 :UBC 0 : neww &= ~((bitmapword) 1 << bitnum);
610 : : }
611 : : }
7468 tgl@sss.pgh.pa.us 612 :CBC 6498 : pg++;
613 : 6498 : bitnum++;
614 : 6498 : w >>= 1;
615 : : }
616 : 108 : apage->words[wordnum] = neww;
617 [ + - ]: 108 : if (neww != 0)
618 : 108 : candelete = false;
619 : : }
620 : : }
621 : 30 : return candelete;
622 : : }
623 [ - + ]: 5582 : else if (tbm_page_is_lossy(b, apage->blockno))
624 : : {
625 : : /*
626 : : * Some of the tuples in 'a' might not satisfy the quals for 'b', but
627 : : * because the page 'b' is lossy, we don't know which ones. Therefore
628 : : * we mark 'a' as requiring rechecks, to indicate that at most those
629 : : * tuples set in 'a' are matches.
630 : : */
6409 tgl@sss.pgh.pa.us 631 :UBC 0 : apage->recheck = true;
7468 632 : 0 : return false;
633 : : }
634 : : else
635 : : {
7317 bruce@momjian.us 636 :CBC 5582 : bool candelete = true;
637 : :
7468 tgl@sss.pgh.pa.us 638 : 5582 : bpage = tbm_find_pageentry(b, apage->blockno);
639 [ + + ]: 5582 : if (bpage != NULL)
640 : : {
641 : : /* Both pages are exact, merge at the bit level */
642 [ - + ]: 4596 : Assert(!bpage->ischunk);
643 [ + + ]: 27576 : for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
644 : : {
645 : 22980 : apage->words[wordnum] &= bpage->words[wordnum];
646 [ + + ]: 22980 : if (apage->words[wordnum] != 0)
647 : 318 : candelete = false;
648 : : }
6409 649 : 4596 : apage->recheck |= bpage->recheck;
650 : : }
651 : : /* If there is no matching b page, we can just delete the a page */
7468 652 : 5582 : return candelete;
653 : : }
654 : : }
655 : :
656 : : /*
657 : : * tbm_is_empty - is a TIDBitmap completely empty?
658 : : */
659 : : bool
7365 660 : 634 : tbm_is_empty(const TIDBitmap *tbm)
661 : : {
662 : 634 : return (tbm->nentries == 0);
663 : : }
664 : :
665 : : /*
666 : : * tbm_begin_private_iterate - prepare to iterate through a TIDBitmap
667 : : *
668 : : * The TBMPrivateIterator struct is created in the caller's memory context.
669 : : * For a clean shutdown of the iteration, call tbm_end_private_iterate; but
670 : : * it's okay to just allow the memory context to be released, too. It is
671 : : * caller's responsibility not to touch the TBMPrivateIterator anymore once
672 : : * the TIDBitmap is freed.
673 : : *
674 : : * NB: after this is called, it is no longer allowed to modify the contents
675 : : * of the bitmap. However, you can call this multiple times to scan the
676 : : * contents repeatedly, including parallel scans.
677 : : */
678 : : TBMPrivateIterator *
313 melanieplageman@gmai 679 : 10003 : tbm_begin_private_iterate(TIDBitmap *tbm)
680 : : {
681 : : TBMPrivateIterator *iterator;
682 : :
3155 rhaas@postgresql.org 683 [ - + ]: 10003 : Assert(tbm->iterating != TBM_ITERATING_SHARED);
684 : :
685 : : /*
686 : : * Create the TBMPrivateIterator struct, with enough trailing space to
687 : : * serve the needs of the TBMIterateResult sub-struct.
688 : : */
245 melanieplageman@gmai 689 : 10003 : iterator = (TBMPrivateIterator *) palloc(sizeof(TBMPrivateIterator));
6134 tgl@sss.pgh.pa.us 690 : 10003 : iterator->tbm = tbm;
691 : :
692 : : /*
693 : : * Initialize iteration pointers.
694 : : */
695 : 10003 : iterator->spageptr = 0;
696 : 10003 : iterator->schunkptr = 0;
697 : 10003 : iterator->schunkbit = 0;
698 : :
699 : : /*
700 : : * If we have a hashtable, create and fill the sorted page lists, unless
701 : : * we already did that for a previous iterator. Note that the lists are
702 : : * attached to the bitmap not the iterator, so they can be used by more
703 : : * than one iterator.
704 : : */
3155 rhaas@postgresql.org 705 [ + + + - ]: 10003 : if (tbm->status == TBM_HASH && tbm->iterating == TBM_NOT_ITERATING)
706 : : {
707 : : pagetable_iterator i;
708 : : PagetableEntry *page;
709 : : int npages;
710 : : int nchunks;
711 : :
6134 tgl@sss.pgh.pa.us 712 [ + - + + ]: 4412 : if (!tbm->spages && tbm->npages > 0)
713 : 2975 : tbm->spages = (PagetableEntry **)
714 : 2975 : MemoryContextAlloc(tbm->mcxt,
715 : 2975 : tbm->npages * sizeof(PagetableEntry *));
716 [ + - + + ]: 4412 : if (!tbm->schunks && tbm->nchunks > 0)
717 : 1443 : tbm->schunks = (PagetableEntry **)
718 : 1443 : MemoryContextAlloc(tbm->mcxt,
719 : 1443 : tbm->nchunks * sizeof(PagetableEntry *));
720 : :
721 : 4412 : npages = nchunks = 0;
3300 andres@anarazel.de 722 : 4412 : pagetable_start_iterate(tbm->pagetable, &i);
723 [ + + ]: 110299 : while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
724 : : {
6134 tgl@sss.pgh.pa.us 725 [ + + ]: 105887 : if (page->ischunk)
726 : 1476 : tbm->schunks[nchunks++] = page;
727 : : else
728 : 104411 : tbm->spages[npages++] = page;
729 : : }
730 [ - + ]: 4412 : Assert(npages == tbm->npages);
731 [ - + ]: 4412 : Assert(nchunks == tbm->nchunks);
732 [ + + ]: 4412 : if (npages > 1)
733 : 2975 : qsort(tbm->spages, npages, sizeof(PagetableEntry *),
734 : : tbm_comparator);
735 [ + + ]: 4412 : if (nchunks > 1)
736 : 9 : qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
737 : : tbm_comparator);
738 : : }
739 : :
3155 rhaas@postgresql.org 740 : 10003 : tbm->iterating = TBM_ITERATING_PRIVATE;
741 : :
6134 tgl@sss.pgh.pa.us 742 : 10003 : return iterator;
743 : : }
744 : :
745 : : /*
746 : : * tbm_prepare_shared_iterate - prepare shared iteration state for a TIDBitmap.
747 : : *
748 : : * The necessary shared state will be allocated from the DSA passed to
749 : : * tbm_create, so that multiple processes can attach to it and iterate jointly.
750 : : *
751 : : * This will convert the pagetable hash into page and chunk array of the index
752 : : * into pagetable array.
753 : : */
754 : : dsa_pointer
3155 rhaas@postgresql.org 755 : 36 : tbm_prepare_shared_iterate(TIDBitmap *tbm)
756 : : {
757 : : dsa_pointer dp;
758 : : TBMSharedIteratorState *istate;
3147 759 : 36 : PTEntryArray *ptbase = NULL;
3155 tgl@sss.pgh.pa.us 760 : 36 : PTIterationArray *ptpages = NULL;
761 : 36 : PTIterationArray *ptchunks = NULL;
762 : :
rhaas@postgresql.org 763 [ - + ]: 36 : Assert(tbm->dsa != NULL);
764 [ - + ]: 36 : Assert(tbm->iterating != TBM_ITERATING_PRIVATE);
765 : :
766 : : /*
767 : : * Allocate TBMSharedIteratorState from DSA to hold the shared members and
768 : : * lock, this will also be used by multiple worker for shared iterate.
769 : : */
3147 770 : 36 : dp = dsa_allocate0(tbm->dsa, sizeof(TBMSharedIteratorState));
3155 771 : 36 : istate = dsa_get_address(tbm->dsa, dp);
772 : :
773 : : /*
774 : : * If we're not already iterating, create and fill the sorted page lists.
775 : : * (If we are, the sorted page lists are already stored in the TIDBitmap,
776 : : * and we can just reuse them.)
777 : : */
778 [ + - ]: 36 : if (tbm->iterating == TBM_NOT_ITERATING)
779 : : {
780 : : pagetable_iterator i;
781 : : PagetableEntry *page;
782 : : int idx;
783 : : int npages;
784 : : int nchunks;
785 : :
786 : : /*
787 : : * Allocate the page and chunk array memory from the DSA to share
788 : : * across multiple processes.
789 : : */
790 [ + - ]: 36 : if (tbm->npages)
791 : : {
792 : 36 : tbm->ptpages = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
793 : : tbm->npages * sizeof(int));
794 : 36 : ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
795 : 36 : pg_atomic_init_u32(&ptpages->refcount, 0);
796 : : }
797 [ + + ]: 36 : if (tbm->nchunks)
798 : : {
799 : 3 : tbm->ptchunks = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
800 : : tbm->nchunks * sizeof(int));
801 : 3 : ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
802 : 3 : pg_atomic_init_u32(&ptchunks->refcount, 0);
803 : : }
804 : :
805 : : /*
806 : : * If TBM status is TBM_HASH then iterate over the pagetable and
807 : : * convert it to page and chunk arrays. But if it's in the
808 : : * TBM_ONE_PAGE mode then directly allocate the space for one entry
809 : : * from the DSA.
810 : : */
811 : 36 : npages = nchunks = 0;
812 [ + - ]: 36 : if (tbm->status == TBM_HASH)
813 : : {
814 : 36 : ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
815 : :
816 : 36 : pagetable_start_iterate(tbm->pagetable, &i);
817 [ + + ]: 13551 : while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
818 : : {
819 : 13515 : idx = page - ptbase->ptentry;
820 [ + + ]: 13515 : if (page->ischunk)
821 : 12 : ptchunks->index[nchunks++] = idx;
822 : : else
823 : 13503 : ptpages->index[npages++] = idx;
824 : : }
825 : :
826 [ - + ]: 36 : Assert(npages == tbm->npages);
827 [ - + ]: 36 : Assert(nchunks == tbm->nchunks);
828 : : }
3147 rhaas@postgresql.org 829 [ # # ]:UBC 0 : else if (tbm->status == TBM_ONE_PAGE)
830 : : {
831 : : /*
832 : : * In one page mode allocate the space for one pagetable entry,
833 : : * initialize it, and directly store its index (i.e. 0) in the
834 : : * page array.
835 : : */
3155 836 : 0 : tbm->dsapagetable = dsa_allocate(tbm->dsa, sizeof(PTEntryArray) +
837 : : sizeof(PagetableEntry));
838 : 0 : ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
3121 839 : 0 : memcpy(ptbase->ptentry, &tbm->entry1, sizeof(PagetableEntry));
3155 840 : 0 : ptpages->index[0] = 0;
841 : : }
842 : :
3147 rhaas@postgresql.org 843 [ + - ]:CBC 36 : if (ptbase != NULL)
844 : 36 : pg_atomic_init_u32(&ptbase->refcount, 0);
3155 845 [ + - ]: 36 : if (npages > 1)
993 peter@eisentraut.org 846 : 36 : qsort_arg(ptpages->index, npages, sizeof(int),
847 : 36 : tbm_shared_comparator, ptbase->ptentry);
3155 rhaas@postgresql.org 848 [ + + ]: 36 : if (nchunks > 1)
993 peter@eisentraut.org 849 : 3 : qsort_arg(ptchunks->index, nchunks, sizeof(int),
850 : 3 : tbm_shared_comparator, ptbase->ptentry);
851 : : }
852 : :
853 : : /*
854 : : * Store the TBM members in the shared state so that we can share them
855 : : * across multiple processes.
856 : : */
3155 rhaas@postgresql.org 857 : 36 : istate->nentries = tbm->nentries;
858 : 36 : istate->maxentries = tbm->maxentries;
859 : 36 : istate->npages = tbm->npages;
860 : 36 : istate->nchunks = tbm->nchunks;
861 : 36 : istate->pagetable = tbm->dsapagetable;
862 : 36 : istate->spages = tbm->ptpages;
863 : 36 : istate->schunks = tbm->ptchunks;
864 : :
865 : 36 : ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
866 : 36 : ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
867 : 36 : ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
868 : :
869 : : /*
870 : : * For every shared iterator referring to pagetable and iterator array,
871 : : * increase the refcount by 1 so that while freeing the shared iterator we
872 : : * don't free pagetable and iterator array until its refcount becomes 0.
873 : : */
3147 874 [ + - ]: 36 : if (ptbase != NULL)
875 : 36 : pg_atomic_add_fetch_u32(&ptbase->refcount, 1);
876 [ + - ]: 36 : if (ptpages != NULL)
3155 877 : 36 : pg_atomic_add_fetch_u32(&ptpages->refcount, 1);
3147 878 [ + + ]: 36 : if (ptchunks != NULL)
3155 879 : 3 : pg_atomic_add_fetch_u32(&ptchunks->refcount, 1);
880 : :
881 : : /* Initialize the iterator lock */
1991 tgl@sss.pgh.pa.us 882 : 36 : LWLockInitialize(&istate->lock, LWTRANCHE_SHARED_TIDBITMAP);
883 : :
884 : : /* Initialize the shared iterator state */
3155 rhaas@postgresql.org 885 : 36 : istate->schunkbit = 0;
886 : 36 : istate->schunkptr = 0;
887 : 36 : istate->spageptr = 0;
888 : :
889 : 36 : tbm->iterating = TBM_ITERATING_SHARED;
890 : :
891 : 36 : return dp;
892 : : }
893 : :
894 : : /*
895 : : * tbm_extract_page_tuple - extract the tuple offsets from a page
896 : : *
897 : : * Returns the number of offsets it filled in if <= max_offsets. Otherwise,
898 : : * fills in as many offsets as fit and returns the total number of offsets in
899 : : * the page.
900 : : */
901 : : int
245 melanieplageman@gmai 902 : 121222 : tbm_extract_page_tuple(TBMIterateResult *iteritem,
903 : : OffsetNumber *offsets,
904 : : uint32 max_offsets)
905 : : {
906 : 121222 : PagetableEntry *page = iteritem->internal_page;
907 : : int wordnum;
3155 rhaas@postgresql.org 908 : 121222 : int ntuples = 0;
909 : :
910 [ + + ]: 727332 : for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
911 : : {
912 : 606110 : bitmapword w = page->words[wordnum];
913 : :
914 [ + + ]: 606110 : if (w != 0)
915 : : {
916 : 281908 : int off = wordnum * BITS_PER_BITMAPWORD + 1;
917 : :
918 [ + + ]: 12155832 : while (w != 0)
919 : : {
920 [ + + ]: 11873924 : if (w & 1)
921 : : {
245 melanieplageman@gmai 922 [ + - ]: 2936861 : if (ntuples < max_offsets)
923 : 2936861 : offsets[ntuples] = (OffsetNumber) off;
924 : 2936861 : ntuples++;
925 : : }
3155 rhaas@postgresql.org 926 : 11873924 : off++;
927 : 11873924 : w >>= 1;
928 : : }
929 : : }
930 : : }
931 : :
932 : 121222 : return ntuples;
933 : : }
934 : :
935 : : /*
936 : : * tbm_advance_schunkbit - Advance the schunkbit
937 : : */
938 : : static inline void
939 : 84756 : tbm_advance_schunkbit(PagetableEntry *chunk, int *schunkbitp)
940 : : {
941 : 84756 : int schunkbit = *schunkbitp;
942 : :
943 [ + + ]: 385494 : while (schunkbit < PAGES_PER_CHUNK)
944 : : {
945 : 384006 : int wordnum = WORDNUM(schunkbit);
946 : 384006 : int bitnum = BITNUM(schunkbit);
947 : :
948 [ + + ]: 384006 : if ((chunk->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
949 : 83268 : break;
950 : 300738 : schunkbit++;
951 : : }
952 : :
953 : 84756 : *schunkbitp = schunkbit;
954 : 84756 : }
955 : :
956 : : /*
957 : : * tbm_private_iterate - scan through next page of a TIDBitmap
958 : : *
959 : : * Caller must pass in a TBMIterateResult to be filled.
960 : : *
961 : : * Pages are guaranteed to be delivered in numerical order.
962 : : *
963 : : * Returns false when there are no more pages to scan and true otherwise. When
964 : : * there are no more pages to scan, tbmres->blockno is set to
965 : : * InvalidBlockNumber.
966 : : *
967 : : * If lossy is true, then the bitmap is "lossy" and failed to remember
968 : : * the exact tuples to look at on this page --- the caller must examine all
969 : : * tuples on the page and check if they meet the intended condition. If lossy
970 : : * is false, the caller must later extract the tuple offsets from the page
971 : : * pointed to by internal_page with tbm_extract_page_tuple.
972 : : *
973 : : * If tbmres->recheck is true, only the indicated tuples need be examined, but
974 : : * the condition must be rechecked anyway. (For ease of testing, recheck is
975 : : * always set true when lossy is true.)
976 : : */
977 : : bool
226 melanieplageman@gmai 978 : 196361 : tbm_private_iterate(TBMPrivateIterator *iterator, TBMIterateResult *tbmres)
979 : : {
5982 bruce@momjian.us 980 : 196361 : TIDBitmap *tbm = iterator->tbm;
981 : :
3155 rhaas@postgresql.org 982 [ - + ]: 196361 : Assert(tbm->iterating == TBM_ITERATING_PRIVATE);
983 : :
984 : : /*
985 : : * If lossy chunk pages remain, make sure we've advanced schunkptr/
986 : : * schunkbit to the next set bit.
987 : : */
6134 tgl@sss.pgh.pa.us 988 [ + + ]: 197837 : while (iterator->schunkptr < tbm->nchunks)
989 : : {
990 : 81681 : PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
991 : 81681 : int schunkbit = iterator->schunkbit;
992 : :
3155 rhaas@postgresql.org 993 : 81681 : tbm_advance_schunkbit(chunk, &schunkbit);
7498 tgl@sss.pgh.pa.us 994 [ + + ]: 81681 : if (schunkbit < PAGES_PER_CHUNK)
995 : : {
6134 996 : 80205 : iterator->schunkbit = schunkbit;
7498 997 : 80205 : break;
998 : : }
999 : : /* advance to next chunk */
6134 1000 : 1476 : iterator->schunkptr++;
1001 : 1476 : iterator->schunkbit = 0;
1002 : : }
1003 : :
1004 : : /*
1005 : : * If both chunk and per-page data remain, must output the numerically
1006 : : * earlier page.
1007 : : */
1008 [ + + ]: 196361 : if (iterator->schunkptr < tbm->nchunks)
1009 : : {
1010 : 80205 : PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
1011 : : BlockNumber chunk_blockno;
1012 : :
1013 : 80205 : chunk_blockno = chunk->blockno + iterator->schunkbit;
1014 [ + + ]: 80205 : if (iterator->spageptr >= tbm->npages ||
1015 [ + + ]: 6225 : chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
1016 : : {
1017 : : /* Return a lossy page indicator from the chunk */
226 melanieplageman@gmai 1018 : 78639 : tbmres->blockno = chunk_blockno;
1019 : 78639 : tbmres->lossy = true;
1020 : 78639 : tbmres->recheck = true;
1021 : 78639 : tbmres->internal_page = NULL;
6134 tgl@sss.pgh.pa.us 1022 : 78639 : iterator->schunkbit++;
226 melanieplageman@gmai 1023 : 78639 : return true;
1024 : : }
1025 : : }
1026 : :
6134 tgl@sss.pgh.pa.us 1027 [ + + ]: 117722 : if (iterator->spageptr < tbm->npages)
1028 : : {
1029 : : PagetableEntry *page;
1030 : :
1031 : : /* In TBM_ONE_PAGE state, we don't allocate an spages[] array */
7468 1032 [ + + ]: 107735 : if (tbm->status == TBM_ONE_PAGE)
1033 : 3973 : page = &tbm->entry1;
1034 : : else
6134 1035 : 103762 : page = tbm->spages[iterator->spageptr];
1036 : :
226 melanieplageman@gmai 1037 : 107735 : tbmres->internal_page = page;
1038 : 107735 : tbmres->blockno = page->blockno;
1039 : 107735 : tbmres->lossy = false;
1040 : 107735 : tbmres->recheck = page->recheck;
3155 rhaas@postgresql.org 1041 : 107735 : iterator->spageptr++;
226 melanieplageman@gmai 1042 : 107735 : return true;
1043 : : }
1044 : :
1045 : : /* Nothing more in the bitmap */
1046 : 9987 : tbmres->blockno = InvalidBlockNumber;
1047 : 9987 : return false;
1048 : : }
1049 : :
1050 : : /*
1051 : : * tbm_shared_iterate - scan through next page of a TIDBitmap
1052 : : *
1053 : : * As above, but this will iterate using an iterator which is shared
1054 : : * across multiple processes. We need to acquire the iterator LWLock,
1055 : : * before accessing the shared members.
1056 : : */
1057 : : bool
1058 : 15225 : tbm_shared_iterate(TBMSharedIterator *iterator, TBMIterateResult *tbmres)
1059 : : {
3155 rhaas@postgresql.org 1060 : 15225 : TBMSharedIteratorState *istate = iterator->state;
3147 1061 : 15225 : PagetableEntry *ptbase = NULL;
1062 : 15225 : int *idxpages = NULL;
1063 : 15225 : int *idxchunks = NULL;
1064 : :
1065 [ + - ]: 15225 : if (iterator->ptbase != NULL)
1066 : 15225 : ptbase = iterator->ptbase->ptentry;
1067 [ + - ]: 15225 : if (iterator->ptpages != NULL)
1068 : 15225 : idxpages = iterator->ptpages->index;
1069 [ + + ]: 15225 : if (iterator->ptchunks != NULL)
1070 : 3720 : idxchunks = iterator->ptchunks->index;
1071 : :
1072 : : /* Acquire the LWLock before accessing the shared members */
3155 1073 : 15225 : LWLockAcquire(&istate->lock, LW_EXCLUSIVE);
1074 : :
1075 : : /*
1076 : : * If lossy chunk pages remain, make sure we've advanced schunkptr/
1077 : : * schunkbit to the next set bit.
1078 : : */
1079 [ + + ]: 15237 : while (istate->schunkptr < istate->nchunks)
1080 : : {
1081 : 3075 : PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
1082 : 3075 : int schunkbit = istate->schunkbit;
1083 : :
1084 : 3075 : tbm_advance_schunkbit(chunk, &schunkbit);
1085 [ + + ]: 3075 : if (schunkbit < PAGES_PER_CHUNK)
1086 : : {
1087 : 3063 : istate->schunkbit = schunkbit;
1088 : 3063 : break;
1089 : : }
1090 : : /* advance to next chunk */
1091 : 12 : istate->schunkptr++;
1092 : 12 : istate->schunkbit = 0;
1093 : : }
1094 : :
1095 : : /*
1096 : : * If both chunk and per-page data remain, must output the numerically
1097 : : * earlier page.
1098 : : */
1099 [ + + ]: 15225 : if (istate->schunkptr < istate->nchunks)
1100 : : {
1101 : 3063 : PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
1102 : : BlockNumber chunk_blockno;
1103 : :
1104 : 3063 : chunk_blockno = chunk->blockno + istate->schunkbit;
1105 : :
1106 [ + - ]: 3063 : if (istate->spageptr >= istate->npages ||
3154 1107 [ + + ]: 3063 : chunk_blockno < ptbase[idxpages[istate->spageptr]].blockno)
1108 : : {
1109 : : /* Return a lossy page indicator from the chunk */
226 melanieplageman@gmai 1110 : 1551 : tbmres->blockno = chunk_blockno;
1111 : 1551 : tbmres->lossy = true;
1112 : 1551 : tbmres->recheck = true;
1113 : 1551 : tbmres->internal_page = NULL;
3155 rhaas@postgresql.org 1114 : 1551 : istate->schunkbit++;
1115 : :
1116 : 1551 : LWLockRelease(&istate->lock);
226 melanieplageman@gmai 1117 : 1551 : return true;
1118 : : }
1119 : : }
1120 : :
3155 rhaas@postgresql.org 1121 [ + + ]: 13674 : if (istate->spageptr < istate->npages)
1122 : : {
1123 : 13503 : PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
1124 : :
226 melanieplageman@gmai 1125 : 13503 : tbmres->internal_page = page;
1126 : 13503 : tbmres->blockno = page->blockno;
1127 : 13503 : tbmres->lossy = false;
1128 : 13503 : tbmres->recheck = page->recheck;
3155 rhaas@postgresql.org 1129 : 13503 : istate->spageptr++;
1130 : :
1131 : 13503 : LWLockRelease(&istate->lock);
1132 : :
226 melanieplageman@gmai 1133 : 13503 : return true;
1134 : : }
1135 : :
3155 rhaas@postgresql.org 1136 : 171 : LWLockRelease(&istate->lock);
1137 : :
1138 : : /* Nothing more in the bitmap */
226 melanieplageman@gmai 1139 : 171 : tbmres->blockno = InvalidBlockNumber;
1140 : 171 : return false;
1141 : : }
1142 : :
1143 : : /*
1144 : : * tbm_end_private_iterate - finish an iteration over a TIDBitmap
1145 : : *
1146 : : * Currently this is just a pfree, but it might do more someday. (For
1147 : : * instance, it could be useful to count open iterators and allow the
1148 : : * bitmap to return to read/write status when there are no more iterators.)
1149 : : */
1150 : : void
313 1151 : 9946 : tbm_end_private_iterate(TBMPrivateIterator *iterator)
1152 : : {
6134 tgl@sss.pgh.pa.us 1153 : 9946 : pfree(iterator);
1154 : 9946 : }
1155 : :
1156 : : /*
1157 : : * tbm_end_shared_iterate - finish a shared iteration over a TIDBitmap
1158 : : *
1159 : : * This doesn't free any of the shared state associated with the iterator,
1160 : : * just our backend-private state.
1161 : : */
1162 : : void
3155 rhaas@postgresql.org 1163 : 171 : tbm_end_shared_iterate(TBMSharedIterator *iterator)
1164 : : {
1165 : 171 : pfree(iterator);
1166 : 171 : }
1167 : :
1168 : : /*
1169 : : * tbm_find_pageentry - find a PagetableEntry for the pageno
1170 : : *
1171 : : * Returns NULL if there is no non-lossy entry for the pageno.
1172 : : */
1173 : : static const PagetableEntry *
7498 tgl@sss.pgh.pa.us 1174 : 5834 : tbm_find_pageentry(const TIDBitmap *tbm, BlockNumber pageno)
1175 : : {
1176 : : const PagetableEntry *page;
1177 : :
7468 1178 [ - + ]: 5834 : if (tbm->nentries == 0) /* in case pagetable doesn't exist */
7468 tgl@sss.pgh.pa.us 1179 :UBC 0 : return NULL;
1180 : :
7468 tgl@sss.pgh.pa.us 1181 [ - + ]:CBC 5834 : if (tbm->status == TBM_ONE_PAGE)
1182 : : {
7468 tgl@sss.pgh.pa.us 1183 :UBC 0 : page = &tbm->entry1;
1184 [ # # ]: 0 : if (page->blockno != pageno)
1185 : 0 : return NULL;
1186 [ # # ]: 0 : Assert(!page->ischunk);
1187 : 0 : return page;
1188 : : }
1189 : :
3300 andres@anarazel.de 1190 :CBC 5834 : page = pagetable_lookup(tbm->pagetable, pageno);
7498 tgl@sss.pgh.pa.us 1191 [ + + ]: 5834 : if (page == NULL)
1192 : 986 : return NULL;
1193 [ - + ]: 4848 : if (page->ischunk)
7498 tgl@sss.pgh.pa.us 1194 :UBC 0 : return NULL; /* don't want a lossy chunk header */
7498 tgl@sss.pgh.pa.us 1195 :CBC 4848 : return page;
1196 : : }
1197 : :
1198 : : /*
1199 : : * tbm_get_pageentry - find or create a PagetableEntry for the pageno
1200 : : *
1201 : : * If new, the entry is marked as an exact (non-chunk) entry.
1202 : : *
1203 : : * This may cause the table to exceed the desired memory size. It is
1204 : : * up to the caller to call tbm_lossify() at the next safe point if so.
1205 : : */
1206 : : static PagetableEntry *
1207 : 3634083 : tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
1208 : : {
1209 : : PagetableEntry *page;
1210 : : bool found;
1211 : :
7468 1212 [ + + ]: 3634083 : if (tbm->status == TBM_EMPTY)
1213 : : {
1214 : : /* Use the fixed slot */
1215 : 7084 : page = &tbm->entry1;
1216 : 7084 : found = false;
1217 : 7084 : tbm->status = TBM_ONE_PAGE;
1218 : : }
1219 : : else
1220 : : {
1221 [ + + ]: 3626999 : if (tbm->status == TBM_ONE_PAGE)
1222 : : {
1223 : 50920 : page = &tbm->entry1;
1224 [ + + ]: 50920 : if (page->blockno == pageno)
1225 : 47809 : return page;
1226 : : /* Time to switch from one page to a hashtable */
1227 : 3111 : tbm_create_pagetable(tbm);
1228 : : }
1229 : :
1230 : : /* Look up or create an entry */
3300 andres@anarazel.de 1231 : 3579190 : page = pagetable_insert(tbm->pagetable, pageno, &found);
1232 : : }
1233 : :
1234 : : /* Initialize it if not present before */
7498 tgl@sss.pgh.pa.us 1235 [ + + ]: 3586274 : if (!found)
1236 : : {
3300 andres@anarazel.de 1237 : 142469 : char oldstatus = page->status;
1238 : :
7498 tgl@sss.pgh.pa.us 1239 [ + - + - : 997283 : MemSet(page, 0, sizeof(PagetableEntry));
+ - + - +
+ ]
3300 andres@anarazel.de 1240 : 142469 : page->status = oldstatus;
7498 tgl@sss.pgh.pa.us 1241 : 142469 : page->blockno = pageno;
1242 : : /* must count it too */
1243 : 142469 : tbm->nentries++;
1244 : 142469 : tbm->npages++;
1245 : : }
1246 : :
1247 : 3586274 : return page;
1248 : : }
1249 : :
1250 : : /*
1251 : : * tbm_page_is_lossy - is the page marked as lossily stored?
1252 : : */
1253 : : static bool
1254 : 3644201 : tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
1255 : : {
1256 : : PagetableEntry *page;
1257 : : BlockNumber chunk_pageno;
1258 : : int bitno;
1259 : :
1260 : : /* we can skip the lookup if there are no lossy chunks */
1261 [ + + ]: 3644201 : if (tbm->nchunks == 0)
1262 : 3579068 : return false;
7468 1263 [ - + ]: 65133 : Assert(tbm->status == TBM_HASH);
1264 : :
7498 1265 : 65133 : bitno = pageno % PAGES_PER_CHUNK;
1266 : 65133 : chunk_pageno = pageno - bitno;
1267 : :
3300 andres@anarazel.de 1268 : 65133 : page = pagetable_lookup(tbm->pagetable, chunk_pageno);
1269 : :
7498 tgl@sss.pgh.pa.us 1270 [ + - + + ]: 65133 : if (page != NULL && page->ischunk)
1271 : : {
7317 bruce@momjian.us 1272 : 9567 : int wordnum = WORDNUM(bitno);
1273 : 9567 : int bitnum = BITNUM(bitno);
1274 : :
7498 tgl@sss.pgh.pa.us 1275 [ + + ]: 9567 : if ((page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
1276 : 4284 : return true;
1277 : : }
1278 : 60849 : return false;
1279 : : }
1280 : :
1281 : : /*
1282 : : * tbm_mark_page_lossy - mark the page number as lossily stored
1283 : : *
1284 : : * This may cause the table to exceed the desired memory size. It is
1285 : : * up to the caller to call tbm_lossify() at the next safe point if so.
1286 : : */
1287 : : static void
1288 : 83214 : tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
1289 : : {
1290 : : PagetableEntry *page;
1291 : : bool found;
1292 : : BlockNumber chunk_pageno;
1293 : : int bitno;
1294 : : int wordnum;
1295 : : int bitnum;
1296 : :
1297 : : /* We force the bitmap into hashtable mode whenever it's lossy */
7468 1298 [ + + ]: 83214 : if (tbm->status != TBM_HASH)
1299 : 1434 : tbm_create_pagetable(tbm);
1300 : :
7498 1301 : 83214 : bitno = pageno % PAGES_PER_CHUNK;
1302 : 83214 : chunk_pageno = pageno - bitno;
1303 : :
1304 : : /*
1305 : : * Remove any extant non-lossy entry for the page. If the page is its own
1306 : : * chunk header, however, we skip this and handle the case below.
1307 : : */
1308 [ + + ]: 83214 : if (bitno != 0)
1309 : : {
3300 andres@anarazel.de 1310 [ + + ]: 82050 : if (pagetable_delete(tbm->pagetable, pageno))
1311 : : {
1312 : : /* It was present, so adjust counts */
7498 tgl@sss.pgh.pa.us 1313 : 9234 : tbm->nentries--;
1314 : 9234 : tbm->npages--; /* assume it must have been non-lossy */
1315 : : }
1316 : : }
1317 : :
1318 : : /* Look up or create entry for chunk-header page */
3300 andres@anarazel.de 1319 : 83214 : page = pagetable_insert(tbm->pagetable, chunk_pageno, &found);
1320 : :
1321 : : /* Initialize it if not present before */
7498 tgl@sss.pgh.pa.us 1322 [ + + ]: 83214 : if (!found)
1323 : : {
3300 andres@anarazel.de 1324 : 1434 : char oldstatus = page->status;
1325 : :
7498 tgl@sss.pgh.pa.us 1326 [ + - + - : 10038 : MemSet(page, 0, sizeof(PagetableEntry));
+ - + - +
+ ]
3300 andres@anarazel.de 1327 : 1434 : page->status = oldstatus;
7498 tgl@sss.pgh.pa.us 1328 : 1434 : page->blockno = chunk_pageno;
1329 : 1434 : page->ischunk = true;
1330 : : /* must count it too */
1331 : 1434 : tbm->nentries++;
1332 : 1434 : tbm->nchunks++;
1333 : : }
1334 [ + + ]: 81780 : else if (!page->ischunk)
1335 : : {
3300 andres@anarazel.de 1336 : 78 : char oldstatus = page->status;
1337 : :
1338 : : /* chunk header page was formerly non-lossy, make it lossy */
7498 tgl@sss.pgh.pa.us 1339 [ + - + - : 546 : MemSet(page, 0, sizeof(PagetableEntry));
+ - + - +
+ ]
3300 andres@anarazel.de 1340 : 78 : page->status = oldstatus;
7498 tgl@sss.pgh.pa.us 1341 : 78 : page->blockno = chunk_pageno;
1342 : 78 : page->ischunk = true;
1343 : : /* we assume it had some tuple bit(s) set, so mark it lossy */
1344 : 78 : page->words[0] = ((bitmapword) 1 << 0);
1345 : : /* adjust counts */
1346 : 78 : tbm->nchunks++;
1347 : 78 : tbm->npages--;
1348 : : }
1349 : :
1350 : : /* Now set the original target page's bit */
1351 : 83214 : wordnum = WORDNUM(bitno);
1352 : 83214 : bitnum = BITNUM(bitno);
1353 : 83214 : page->words[wordnum] |= ((bitmapword) 1 << bitnum);
1354 : 83214 : }
1355 : :
1356 : : /*
1357 : : * tbm_lossify - lose some information to get back under the memory limit
1358 : : */
1359 : : static void
1360 : 18 : tbm_lossify(TIDBitmap *tbm)
1361 : : {
1362 : : pagetable_iterator i;
1363 : : PagetableEntry *page;
1364 : :
1365 : : /*
1366 : : * XXX Really stupid implementation: this just lossifies pages in
1367 : : * essentially random order. We should be paying some attention to the
1368 : : * number of bits set in each page, instead.
1369 : : *
1370 : : * Since we are called as soon as nentries exceeds maxentries, we should
1371 : : * push nentries down to significantly less than maxentries, or else we'll
1372 : : * just end up doing this again very soon. We shoot for maxentries/2.
1373 : : */
3155 rhaas@postgresql.org 1374 [ - + ]: 18 : Assert(tbm->iterating == TBM_NOT_ITERATING);
7468 tgl@sss.pgh.pa.us 1375 [ - + ]: 18 : Assert(tbm->status == TBM_HASH);
1376 : :
3300 andres@anarazel.de 1377 : 18 : pagetable_start_iterate_at(tbm->pagetable, &i, tbm->lossify_start);
1378 [ + - ]: 9246 : while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
1379 : : {
7498 tgl@sss.pgh.pa.us 1380 [ - + ]: 9246 : if (page->ischunk)
7498 tgl@sss.pgh.pa.us 1381 :UBC 0 : continue; /* already a chunk header */
1382 : :
1383 : : /*
1384 : : * If the page would become a chunk header, we won't save anything by
1385 : : * converting it to lossy, so skip it.
1386 : : */
7498 tgl@sss.pgh.pa.us 1387 [ + + ]:CBC 9246 : if ((page->blockno % PAGES_PER_CHUNK) == 0)
1388 : 12 : continue;
1389 : :
1390 : : /* This does the dirty work ... */
1391 : 9234 : tbm_mark_page_lossy(tbm, page->blockno);
1392 : :
5182 1393 [ + + ]: 9234 : if (tbm->nentries <= tbm->maxentries / 2)
1394 : : {
1395 : : /*
1396 : : * We have made enough room. Remember where to start lossifying
1397 : : * next round, so we evenly iterate over the hashtable.
1398 : : */
3300 andres@anarazel.de 1399 : 18 : tbm->lossify_start = i.cur;
6759 tgl@sss.pgh.pa.us 1400 : 18 : break;
1401 : : }
1402 : :
1403 : : /*
1404 : : * Note: tbm_mark_page_lossy may have inserted a lossy chunk into the
1405 : : * hashtable and may have deleted the non-lossy chunk. We can
1406 : : * continue the same hash table scan, since failure to visit one
1407 : : * element or visiting the newly inserted element, isn't fatal.
1408 : : */
1409 : : }
1410 : :
1411 : : /*
1412 : : * With a big bitmap and small work_mem, it's possible that we cannot get
1413 : : * under maxentries. Again, if that happens, we'd end up uselessly
1414 : : * calling tbm_lossify over and over. To prevent this from becoming a
1415 : : * performance sink, force maxentries up to at least double the current
1416 : : * number of entries. (In essence, we're admitting inability to fit
1417 : : * within work_mem when we do this.) Note that this test will not fire if
1418 : : * we broke out of the loop early; and if we didn't, the current number of
1419 : : * entries is simply not reducible any further.
1420 : : */
5182 1421 [ - + ]: 18 : if (tbm->nentries > tbm->maxentries / 2)
5182 tgl@sss.pgh.pa.us 1422 :UBC 0 : tbm->maxentries = Min(tbm->nentries, (INT_MAX - 1) / 2) * 2;
7498 tgl@sss.pgh.pa.us 1423 :CBC 18 : }
1424 : :
1425 : : /*
1426 : : * qsort comparator to handle PagetableEntry pointers.
1427 : : */
1428 : : static int
1429 : 689156 : tbm_comparator(const void *left, const void *right)
1430 : : {
4887 bruce@momjian.us 1431 : 689156 : BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
1432 : 689156 : BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
1433 : :
619 nathan@postgresql.or 1434 : 689156 : return pg_cmp_u32(l, r);
1435 : : }
1436 : :
1437 : : /*
1438 : : * As above, but this will get index into PagetableEntry array. Therefore,
1439 : : * it needs to get actual PagetableEntry using the index before comparing the
1440 : : * blockno.
1441 : : */
1442 : : static int
3155 rhaas@postgresql.org 1443 : 119145 : tbm_shared_comparator(const void *left, const void *right, void *arg)
1444 : : {
1445 : 119145 : PagetableEntry *base = (PagetableEntry *) arg;
1446 : 119145 : PagetableEntry *lpage = &base[*(int *) left];
1447 : 119145 : PagetableEntry *rpage = &base[*(int *) right];
1448 : :
1449 [ + + ]: 119145 : if (lpage->blockno < rpage->blockno)
1450 : 54483 : return -1;
1451 [ + - ]: 64662 : else if (lpage->blockno > rpage->blockno)
1452 : 64662 : return 1;
3155 rhaas@postgresql.org 1453 :UBC 0 : return 0;
1454 : : }
1455 : :
1456 : : /*
1457 : : * tbm_attach_shared_iterate
1458 : : *
1459 : : * Allocate a backend-private iterator and attach the shared iterator state
1460 : : * to it so that multiple processed can iterate jointly.
1461 : : *
1462 : : * We also converts the DSA pointers to local pointers and store them into
1463 : : * our private iterator.
1464 : : */
1465 : : TBMSharedIterator *
3155 rhaas@postgresql.org 1466 :CBC 171 : tbm_attach_shared_iterate(dsa_area *dsa, dsa_pointer dp)
1467 : : {
1468 : : TBMSharedIterator *iterator;
1469 : : TBMSharedIteratorState *istate;
1470 : :
1471 : : /*
1472 : : * Create the TBMSharedIterator struct, with enough trailing space to
1473 : : * serve the needs of the TBMIterateResult sub-struct.
1474 : : */
245 melanieplageman@gmai 1475 : 171 : iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator));
1476 : :
3155 rhaas@postgresql.org 1477 : 171 : istate = (TBMSharedIteratorState *) dsa_get_address(dsa, dp);
1478 : :
1479 : 171 : iterator->state = istate;
1480 : :
1481 : 171 : iterator->ptbase = dsa_get_address(dsa, istate->pagetable);
1482 : :
1483 [ + - ]: 171 : if (istate->npages)
1484 : 171 : iterator->ptpages = dsa_get_address(dsa, istate->spages);
1485 [ + + ]: 171 : if (istate->nchunks)
1486 : 15 : iterator->ptchunks = dsa_get_address(dsa, istate->schunks);
1487 : :
1488 : 171 : return iterator;
1489 : : }
1490 : :
1491 : : /*
1492 : : * pagetable_allocate
1493 : : *
1494 : : * Callback function for allocating the memory for hashtable elements.
1495 : : * Allocate memory for hashtable elements, using DSA if available.
1496 : : */
1497 : : static inline void *
1498 : 4741 : pagetable_allocate(pagetable_hash *pagetable, Size size)
1499 : : {
1500 : 4741 : TIDBitmap *tbm = (TIDBitmap *) pagetable->private_data;
1501 : : PTEntryArray *ptbase;
1502 : :
1503 [ + + ]: 4741 : if (tbm->dsa == NULL)
1504 : 4663 : return MemoryContextAllocExtended(pagetable->ctx, size,
1505 : : MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO);
1506 : :
1507 : : /*
1508 : : * Save the dsapagetable reference in dsapagetableold before allocating
1509 : : * new memory so that pagetable_free can free the old entry.
1510 : : */
1511 : 78 : tbm->dsapagetableold = tbm->dsapagetable;
3136 1512 : 78 : tbm->dsapagetable = dsa_allocate_extended(tbm->dsa,
1513 : : sizeof(PTEntryArray) + size,
1514 : : DSA_ALLOC_HUGE | DSA_ALLOC_ZERO);
3155 1515 : 78 : ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
1516 : :
1517 : 78 : return ptbase->ptentry;
1518 : : }
1519 : :
1520 : : /*
1521 : : * pagetable_free
1522 : : *
1523 : : * Callback function for freeing hash table elements.
1524 : : */
1525 : : static inline void
1526 : 4739 : pagetable_free(pagetable_hash *pagetable, void *pointer)
1527 : : {
1528 : 4739 : TIDBitmap *tbm = (TIDBitmap *) pagetable->private_data;
1529 : :
1530 : : /* pfree the input pointer if DSA is not available */
1531 [ + + ]: 4739 : if (tbm->dsa == NULL)
1532 : 4661 : pfree(pointer);
1533 [ + + ]: 78 : else if (DsaPointerIsValid(tbm->dsapagetableold))
1534 : : {
1535 : 42 : dsa_free(tbm->dsa, tbm->dsapagetableold);
1536 : 42 : tbm->dsapagetableold = InvalidDsaPointer;
1537 : : }
1538 : 4739 : }
1539 : :
1540 : : /*
1541 : : * tbm_calculate_entries
1542 : : *
1543 : : * Estimate number of hashtable entries we can have within maxbytes.
1544 : : */
1545 : : int
269 tgl@sss.pgh.pa.us 1546 : 356346 : tbm_calculate_entries(Size maxbytes)
1547 : : {
1548 : : Size nbuckets;
1549 : :
1550 : : /*
1551 : : * Estimate number of hashtable entries we can have within maxbytes. This
1552 : : * estimates the hash cost as sizeof(PagetableEntry), which is good enough
1553 : : * for our purpose. Also count an extra Pointer per entry for the arrays
1554 : : * created during iteration readout.
1555 : : */
2908 rhaas@postgresql.org 1556 : 356346 : nbuckets = maxbytes /
1557 : : (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
1558 : 356346 : nbuckets = Min(nbuckets, INT_MAX - 1); /* safety limit */
1559 : 356346 : nbuckets = Max(nbuckets, 16); /* sanity limit */
1560 : :
269 tgl@sss.pgh.pa.us 1561 : 356346 : return (int) nbuckets;
1562 : : }
1563 : :
1564 : : /*
1565 : : * Create a shared or private bitmap iterator and start iteration.
1566 : : *
1567 : : * `tbm` is only used to create the private iterator and dsa and dsp are only
1568 : : * used to create the shared iterator.
1569 : : *
1570 : : * Before invoking tbm_begin_iterate() to create a shared iterator, one
1571 : : * process must already have invoked tbm_prepare_shared_iterate() to create
1572 : : * and set up the TBMSharedIteratorState.
1573 : : */
1574 : : TBMIterator
313 melanieplageman@gmai 1575 : 9814 : tbm_begin_iterate(TIDBitmap *tbm, dsa_area *dsa, dsa_pointer dsp)
1576 : : {
1577 : 9814 : TBMIterator iterator = {0};
1578 : :
1579 : : /* Allocate a private iterator and attach the shared state to it */
1580 [ + + ]: 9814 : if (DsaPointerIsValid(dsp))
1581 : : {
1582 : 171 : iterator.shared = true;
1583 : 171 : iterator.i.shared_iterator = tbm_attach_shared_iterate(dsa, dsp);
1584 : : }
1585 : : else
1586 : : {
1587 : 9643 : iterator.shared = false;
1588 : 9643 : iterator.i.private_iterator = tbm_begin_private_iterate(tbm);
1589 : : }
1590 : :
1591 : 9814 : return iterator;
1592 : : }
1593 : :
1594 : : /*
1595 : : * Clean up shared or private bitmap iterator.
1596 : : */
1597 : : void
1598 : 9757 : tbm_end_iterate(TBMIterator *iterator)
1599 : : {
312 1600 [ + - - + ]: 9757 : Assert(iterator && !tbm_exhausted(iterator));
1601 : :
313 1602 [ + + ]: 9757 : if (iterator->shared)
1603 : 171 : tbm_end_shared_iterate(iterator->i.shared_iterator);
1604 : : else
1605 : 9586 : tbm_end_private_iterate(iterator->i.private_iterator);
1606 : :
1607 : 9757 : *iterator = (TBMIterator)
1608 : : {
1609 : : 0
1610 : : };
1611 : 9757 : }
1612 : :
1613 : : /*
1614 : : * Populate the next TBMIterateResult using the shared or private bitmap
1615 : : * iterator. Returns false when there is nothing more to scan.
1616 : : */
1617 : : bool
226 1618 : 208663 : tbm_iterate(TBMIterator *iterator, TBMIterateResult *tbmres)
1619 : : {
313 1620 [ - + ]: 208663 : Assert(iterator);
226 1621 [ - + ]: 208663 : Assert(tbmres);
1622 : :
313 1623 [ + + ]: 208663 : if (iterator->shared)
226 1624 : 15225 : return tbm_shared_iterate(iterator->i.shared_iterator, tbmres);
1625 : : else
1626 : 193438 : return tbm_private_iterate(iterator->i.private_iterator, tbmres);
1627 : : }
|
