GCC Code Coverage Report


Directory: src/
File: src/index/posting_page.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 163 181 90.1%
Functions: 17 19 89.5%
Branches: 65 98 66.3%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * posting_page.c - Posting list page operations
6 */
7
8 #include "vs_config.h"
9
10 #include "core/log.h"
11 #include "index/posting_page.h"
12
13 #ifndef VS_STANDALONE
14 #include <miscadmin.h> /* CHECK_FOR_INTERRUPTS */
15 #endif
16
17 void
18 23269 prism_fastscan_check_page(
19 BlockNumber blkno,
20 const PrismPostingPageOpaque *op,
21 uint32_t cap,
22 uint32_t space)
23 {
24
1/2
✓ Branch 0 taken 12709 times.
✗ Branch 1 not taken.
23269 uint32_t groups = prism_fastscan_page_groups(op);
25 23269 uint32_t col_len = VS_FASTSCAN_GROUP_BYTES(8); /* one 8-dim column */
26
27
1/2
✓ Branch 0 taken 23269 times.
✗ Branch 1 not taken.
23269 if (op->entry_count > cap ||
28
2/4
✓ Branch 0 taken 23269 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 12709 times.
23269 (size_t)groups * PRISM_FASTSCAN_META_BYTES + op->code_bytes > space ||
29
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10560 times.
10560 op->code_bytes % col_len != 0)
30 ✗ vs_error(
31 VS_EXTENSION_NAME
32 ": fastscan posting page %u does not fit its page "
33 "(%u entries, %u code bytes); "
34 "the index may be corrupted -- REINDEX it",
35 blkno,
36 (unsigned)op->entry_count,
37 (unsigned)op->code_bytes);
38 23269 }
39
40 void
41 7237 prism_posting_check_count(BlockNumber blkno, Page page, Dimension dim)
42 {
43 7237 const PrismPostingPageOpaque *op = prism_posting_opaque(page);
44 7237 uint32_t cap = prism_posting_page_cap(op, dim);
45
46
2/2
✓ Branch 0 taken 3013 times.
✓ Branch 1 taken 4224 times.
7237 if (op->flags & PRISM_POSTING_PAGE_FASTSCAN)
47 {
48 3013 bool prefix = prism_posting_has_ref_prefix(op->flags, dim);
49
50
2/2
✓ Branch 0 taken 1906 times.
✓ Branch 1 taken 579 times.
3013 prism_fastscan_check_page(
51 blkno, op, cap, prism_fastscan_page_space(dim, prefix));
52 3013 return;
53 }
54
55
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4224 times.
4224 if (op->entry_count > cap)
56 ✗ vs_error(
57 VS_EXTENSION_NAME
58 ": posting page %u has an invalid entry count (%u > %u); "
59 "the index may be corrupted -- REINDEX it",
60 blkno,
61 (unsigned)op->entry_count,
62 cap);
63 }
64
65 /* ----------------------------------------------------------------
66 * Paged mode (BLCKSZ pages with PG header + opaque)
67 * ---------------------------------------------------------------- */
68
69 void
70 38203 prism_posting_page_init(
71 Page page, uint32_t cluster_id, Dimension dim, uint16_t flags)
72 {
73 38203 PageInit(page, BLCKSZ, sizeof(PrismPostingPageOpaque));
74
75 /* A list's first entry page gives up room to the reference prefix, and
76 * a page that holds only reference has no room for entries. A fastscan
77 * page keeps its code length in the same field, and starts with none. */
78 38203 uint32_t max = 0;
79
2/2
✓ Branch 0 taken 10316 times.
✓ Branch 1 taken 27887 times.
38203 if (!(flags & PRISM_POSTING_PAGE_FASTSCAN) &&
80
3/3
✓ Branch 0 taken 3514 times.
✓ Branch 1 taken 6234 times.
✓ Branch 2 taken 568 times.
10316 !prism_posting_is_reference_only_page(flags, dim))
81 9381 max = prism_posting_has_ref_prefix(flags, dim)
82 2829 ? prism_posting_max_entries_first(dim)
83
2/2
✓ Branch 0 taken 2829 times.
✓ Branch 1 taken 6552 times.
9381 : prism_posting_max_entries(dim);
84 38203 PrismPostingPageOpaque *opaque = prism_posting_opaque(page);
85 38203 opaque->next_blkno = InvalidBlockNumber;
86 38203 opaque->cluster_id = cluster_id;
87 38203 opaque->entry_count = 0;
88 38203 opaque->flags = flags;
89 38203 opaque->page_id = PRISM_POSTING_PAGE_ID;
90 38203 opaque->max_entries = (uint16_t)max;
91 /* Head metadata starts "not computed"; the first insert fills it (the
92 * fields are only consulted on the START page). */
93 38203 opaque->live_count = 0;
94 38203 opaque->tail_blkno = InvalidBlockNumber;
95 38203 }
96
97 bool
98 286322 prism_posting_page_add(
99 Page page,
100 Dimension dim,
101 ItemPointerData tid,
102 float f_add,
103 float f_rescale,
104 float f_error,
105 const uint8_t *bits,
106 uint8_t entry_flags)
107 {
108
2/2
✓ Branch 1 taken 64030 times.
✓ Branch 2 taken 222292 times.
286322 if (!prism_posting_page_has_room(page))
109 2 return false;
110
111 286320 PrismPostingPageOpaque *opaque = prism_posting_opaque(page);
112 286320 uint32_t i = opaque->entry_count;
113 286320 char *content = prism_posting_page_content(page, dim);
114
115 /* Write the entry header (meta + factors) + bits in one contiguous
116 * block at content + i * entry_size. */
117
1/2
✓ Branch 0 taken 64028 times.
✗ Branch 1 not taken.
286320 PrismPostingEntryHeader *hdr = prism_posting_entry_at(content, i, dim);
118 286320 hdr->meta.tid = tid;
119 286320 hdr->meta.flags = entry_flags;
120 286320 hdr->meta.reserved = 0;
121 286320 hdr->f_add = f_add;
122 286320 hdr->f_rescale = f_rescale;
123 286320 hdr->f_error = f_error;
124
1/2
✓ Branch 0 taken 64028 times.
✗ Branch 1 not taken.
286320 memcpy(hdr->bits, bits, VS_RABITQ_BYTES(dim));
125
126 286320 opaque->entry_count = i + 1;
127
128 /* A live entry means the page is no longer wholly dead, so drop the
129 * scan-side shortcut -- see PRISM_POSTING_PAGE_TOMBSTONED. */
130
1/2
✓ Branch 0 taken 286320 times.
✗ Branch 1 not taken.
286320 if ((entry_flags & PRISM_POSTING_FLAG_DELETED) == 0)
131 286320 opaque->flags &= (uint16_t)~PRISM_POSTING_PAGE_TOMBSTONED;
132
133 222292 return true;
134 }
135
136 /* ----------------------------------------------------------------
137 * Encode reference, inline or spilled
138 * ---------------------------------------------------------------- */
139
140 /* The head part of head page i of a spilled list (0 = START). */
141 static uint16_t
142 27609784 reference_page_kind(Dimension dim, uint32_t i)
143 {
144
2/2
✓ Branch 0 taken 5528805 times.
✓ Branch 1 taken 22080979 times.
27609784 if (i == 0)
145 5359196 return PRISM_POSTING_HEAD_START;
146
3/3
✓ Branch 0 taken 84483 times.
✓ Branch 1 taken 268762 times.
✓ Branch 2 taken 92432 times.
445677 if (i == prism_posting_reference_pages(dim) - 1)
147 268119 return PRISM_POSTING_HEAD_END;
148 92432 return PRISM_POSTING_HEAD_MIDDLE;
149 }
150
151 void
152 1519 prism_posting_reference_page_fill(
153 Page page,
154 uint32_t cluster_id,
155 Dimension dim,
156 uint32_t i,
157 const float *ref,
158 uint16_t extra_flags)
159 {
160 1519 uint16_t flags = reference_page_kind(dim, i) | extra_flags;
161 1519 uint32_t start = i * (uint32_t)PRISM_POSTING_REFERENCE_PAGE_FLOATS;
162
1/2
✓ Branch 0 taken 545 times.
✗ Branch 1 not taken.
1519 uint32_t nfloats = prism_posting_reference_page_floats(dim, i);
163
164 1519 prism_posting_page_init(page, cluster_id, dim, flags);
165 2493 memcpy(prism_posting_pt_centroid_mut(page),
166 1519 ref + start,
167 1519 (size_t)nfloats * sizeof(float));
168 1519 }
169
170 /*
171 * Whether a page read while gathering a list's reference is the head page
172 * expected at position i: START first, then MIDDLE pages, then END, all of
173 * the START page's cluster. `opaque` is the page's opaque. The START page
174 * (i = 0) sets *cluster_id for the later pages to match. A page that does
175 * not match means the chain is corrupt, and the caller reports it rather
176 * than read its contents as reference.
177 */
178 static bool
179 13805720 reference_page_matches(
180 const PrismPostingPageOpaque *opaque,
181 uint32_t i,
182 uint32_t *cluster_id,
183 Dimension dim)
184 {
185
2/2
✓ Branch 0 taken 13581760 times.
✓ Branch 1 taken 223960 times.
13805720 if (i == 0)
186 13581760 *cluster_id = opaque->cluster_id;
187
1/2
✓ Branch 0 taken 10987124 times.
✗ Branch 1 not taken.
13805720 return prism_posting_head_part(opaque->flags) ==
188
2/3
✓ Branch 0 taken 10987124 times.
✓ Branch 1 taken 2818596 times.
✗ Branch 2 not taken.
16624316 reference_page_kind(dim, i) &&
189
2/2
✓ Branch 0 taken 2818596 times.
✓ Branch 1 taken 10987124 times.
13805720 opaque->cluster_id == *cluster_id;
190 }
191
192 /* Copy head page i's floats of the reference into out. */
193 static void
194 13805720 reference_copy_page(Page page, uint32_t i, Dimension dim, float *out)
195 {
196 13805720 uint32_t start = i * (uint32_t)PRISM_POSTING_REFERENCE_PAGE_FLOATS;
197
2/2
✓ Branch 0 taken 124554 times.
✓ Branch 1 taken 10862570 times.
16392094 uint32_t nfloats = prism_posting_spilled(dim)
198 11219346 ? prism_posting_reference_page_floats(dim, i)
199
2/2
✓ Branch 0 taken 356776 times.
✓ Branch 1 taken 13448944 times.
13805720 : dim;
200
201 13805720 memcpy(out + start,
202 13805720 prism_posting_pt_centroid(page),
203 13805720 (size_t)nfloats * sizeof(float));
204 13805720 }
205
206 static void
207 ✗ reference_page_error(
208 BlockNumber head,
209 BlockNumber blk,
210 uint32_t i,
211 uint16_t flags,
212 uint32_t cluster_id)
213 {
214 ✗ vs_error(
215 VS_EXTENSION_NAME
216 ": block %u is not reference page %u of posting list "
217 "%u (flags 0x%04X, cluster %u); the index may be "
218 "corrupted -- REINDEX it",
219 blk,
220 i,
221 head,
222 flags,
223 cluster_id);
224 }
225
226 static void
227 ✗ not_posting_page_error(BlockNumber head, BlockNumber blk)
228 {
229 ✗ vs_error(
230 VS_EXTENSION_NAME
231 ": block %u of posting list %u is not a posting page; "
232 "the index may be corrupted -- REINDEX it",
233 blk,
234 head);
235 }
236
237 /*
238 * Copy the reference from head pages [first, end) of a list, starting at
239 * blk. Returns the page the list's entries start on once the chain reaches
240 * it (an inline START page or an END page), else the next page to read.
241 */
242 static BlockNumber
243 13584299 posting_reference_read_chain(
244 VsStorage *storage,
245 BlockNumber head,
246 BlockNumber blk,
247 uint32_t first,
248 uint32_t end,
249 uint32_t *cluster_id,
250 Dimension dim,
251 float *out)
252 {
253 13584299 uint32_t npages = prism_posting_reference_pages(dim);
254
255
2/2
✓ Branch 0 taken 13802545 times.
✓ Branch 1 taken 3175 times.
13805720 for (uint32_t i = first; i < end; i++)
256 {
257
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13802545 times.
13802545 if (blk == InvalidBlockNumber)
258 ✗ vs_error(
259 VS_EXTENSION_NAME
260 ": posting list %u ends after %u of %u reference "
261 "pages; the index may be corrupted -- REINDEX it",
262 head,
263 i,
264 npages);
265
266 13802545 Page page = vs_storage_read_page(storage, blk);
267
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 13802545 times.
13802545 if (!prism_page_is_posting(page))
268 {
269 ✗ vs_storage_release_page(storage, blk);
270 ✗ not_posting_page_error(head, blk);
271 }
272
273 13802545 const PrismPostingPageOpaque *op = prism_posting_opaque(page);
274
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 13802545 times.
13802545 if (!reference_page_matches(op, i, cluster_id, dim))
275 {
276 ✗ uint16_t flags = op->flags;
277 ✗ uint32_t cid = op->cluster_id;
278
279 ✗ vs_storage_release_page(storage, blk);
280 ✗ reference_page_error(head, blk, i, flags, cid);
281 }
282
283 13802545 reference_copy_page(page, i, dim, out);
284 13802545 BlockNumber next = op->next_blkno;
285 13802545 vs_storage_release_page(storage, blk);
286
287
2/2
✓ Branch 1 taken 2676538 times.
✓ Branch 2 taken 139156 times.
13802545 if (!prism_posting_is_reference_only_page(
288
2/2
✓ Branch 0 taken 82265 times.
✓ Branch 1 taken 10904586 times.
13802545 reference_page_kind(dim, i), dim))
289 2676538 return blk;
290 221421 blk = next;
291 }
292 2902 return blk;
293 }
294
295 BlockNumber
296 13578585 prism_posting_reference_read(
297 VsStorage *storage, BlockNumber head, Dimension dim, float *out)
298 {
299 13578585 uint32_t cluster_id = 0;
300
301 13578585 return posting_reference_read_chain(
302 storage,
303 head,
304 head,
305 0,
306 prism_posting_reference_pages(dim),
307 &cluster_id,
308 dim,
309 out);
310 }
311
312 BlockNumber
313 3175 prism_posting_reference_read_to_end(
314 VsStorage *storage,
315 BlockNumber head,
316 Dimension dim,
317 float *out,
318 uint32_t *cluster_id)
319 {
320 3175 uint32_t npages = prism_posting_reference_pages(dim);
321
2/3
✓ Branch 0 taken 273 times.
✓ Branch 1 taken 2902 times.
✗ Branch 2 not taken.
3175 uint32_t end = prism_posting_spilled(dim) ? npages - 1 : npages;
322
323 3175 return posting_reference_read_chain(
324 storage, head, head, 0, end, cluster_id, dim, out);
325 }
326
327 void
328 3175 prism_posting_reference_read_end(
329 BlockNumber head,
330 BlockNumber blk,
331 Page page,
332 uint32_t cluster_id,
333 Dimension dim,
334 float *out)
335 {
336 3175 uint32_t last = prism_posting_reference_pages(dim) - 1;
337
338
2/3
✗ Branch 0 not taken.
✓ Branch 1 taken 273 times.
✓ Branch 2 taken 2902 times.
3175 Assert(prism_posting_spilled(dim));
339
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3175 times.
3175 if (!prism_page_is_posting(page))
340 ✗ not_posting_page_error(head, blk);
341
342 3175 const PrismPostingPageOpaque *op = prism_posting_opaque(page);
343
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3175 times.
3175 if (!reference_page_matches(op, last, &cluster_id, dim))
344 ✗ reference_page_error(head, blk, last, op->flags, op->cluster_id);
345 3175 reference_copy_page(page, last, dim, out);
346 3175 }
347
348 BlockNumber
349 2539 prism_posting_reference_read_rest(
350 VsStorage *storage,
351 BlockNumber head,
352 BlockNumber next,
353 uint32_t cluster_id,
354 Dimension dim,
355 float *out)
356 {
357
2/3
✓ Branch 0 taken 2493 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 46 times.
2539 if (!prism_posting_spilled(dim))
358 ✗ return next;
359 2539 return posting_reference_read_chain(
360 storage,
361 head,
362 next,
363 1,
364 prism_posting_reference_pages(dim),
365 &cluster_id,
366 dim,
367 out);
368 }
369
370 /* ----------------------------------------------------------------
371 * Chain walks
372 * ---------------------------------------------------------------- */
373
374 void
375 4045 prism_posting_chain_walk(
376 VsStorage *storage,
377 BlockNumber head,
378 PrismPostingChainCb cb,
379 void *state)
380 {
381 4045 PrismPostingChainPos pos = {.storage = storage, .first = true};
382 4045 BlockNumber blk = head;
383
384
2/2
✓ Branch 0 taken 7090 times.
✓ Branch 1 taken 4036 times.
11126 while (blk != InvalidBlockNumber)
385 {
386
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5112 times.
5112 CHECK_FOR_INTERRUPTS();
387
388 7090 pos.blkno = blk;
389 7090 pos.page = vs_storage_read_page(storage, blk);
390
391 /*
392 * Reading next_blkno means casting the special area, so establish
393 * that it is a posting page first -- the same guard every other
394 * page read applies. A chain that leaves posting pages is a
395 * corrupt chain, and ends the walk rather than being followed.
396 */
397
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 7090 times.
7090 if (!prism_page_is_posting(pos.page))
398 {
399 ✗ prism_posting_chain_release(&pos);
400 8 return;
401 }
402
403 7090 pos.next = prism_posting_opaque(pos.page)->next_blkno;
404
405 7090 bool keep_going = cb(&pos, state);
406
407 /* No-op when the callback released it already. */
408 7089 prism_posting_chain_release(&pos);
409
410
2/2
✓ Branch 0 taken 5115 times.
✓ Branch 1 taken 1974 times.
7089 if (!keep_going)
411 6 return;
412
413 7081 pos.first = false;
414 7081 blk = pos.next;
415 }
416 }
417
418 void
419 176 prism_posting_chain_mutate(
420 VsStorage *storage,
421 BlockNumber head,
422 PrismPostingChainMutateCb cb,
423 void *state)
424 {
425 176 BlockNumber blk = head;
426
427
2/2
✓ Branch 0 taken 528 times.
✓ Branch 1 taken 176 times.
704 while (blk != InvalidBlockNumber)
428 {
429 528 Page page = vs_storage_write_page(storage, blk);
430 528 PrismPostingPageOpaque *op = prism_posting_opaque(page);
431 528 BlockNumber next = op->next_blkno;
432
433 528 cb(op, state);
434
435 528 vs_storage_commit_page(storage, blk);
436 528 blk = next;
437 }
438 176 }
439
440 /* ----------------------------------------------------------------
441 * Flat mode (one buffer per cluster, custom header)
442 * ---------------------------------------------------------------- */
443
444 void
445 188 prism_posting_flat_init(char *buf, uint32_t max_entries, uint32_t cluster_id)
446 {
447 188 PrismFlatPostingHeader *hdr = prism_flat_posting_header(buf);
448 188 hdr->max_entries = max_entries;
449 188 hdr->entry_count = 0;
450 188 hdr->cluster_id = cluster_id;
451 188 hdr->_pad = 0;
452 188 }
453
454 bool
455 12240 prism_posting_flat_add(
456 char *buf,
457 Dimension dim,
458 ItemPointerData tid,
459 float f_add,
460 float f_rescale,
461 float f_error,
462 const uint8_t *bits,
463 uint8_t entry_flags)
464 {
465 12240 PrismFlatPostingHeader *flat_hdr = prism_flat_posting_header(buf);
466
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12240 times.
12240 if (flat_hdr->entry_count >= flat_hdr->max_entries)
467 ✗ return false;
468
469 12240 uint32_t i = flat_hdr->entry_count;
470 12240 char *content = prism_flat_posting_content(buf);
471
472 12240 PrismPostingEntryHeader *hdr = prism_posting_entry_at(content, i, dim);
473 12240 hdr->meta.tid = tid;
474 12240 hdr->meta.flags = entry_flags;
475 12240 hdr->meta.reserved = 0;
476 12240 hdr->f_add = f_add;
477 12240 hdr->f_rescale = f_rescale;
478 12240 hdr->f_error = f_error;
479 12240 memcpy(hdr->bits, bits, VS_RABITQ_BYTES(dim));
480
481 12240 flat_hdr->entry_count = i + 1;
482 12240 return true;
483 }
484