| 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.h - Posting list page format | ||
| 6 | * | ||
| 7 | * Stores per-cluster posting data using an AoS layout: each entry | ||
| 8 | * is a fixed-size block packing meta + factors + bits together. | ||
| 9 | * | ||
| 10 | * Paged mode (BLCKSZ pages): | ||
| 11 | * PageHeader (PG-compatible, 24B) | ||
| 12 | * (reference prefix — on a list's first entry page only) | ||
| 13 | * entry[0], entry[1], ... | ||
| 14 | * PrismPostingPageOpaque (16B at page end) | ||
| 15 | * | ||
| 16 | * Flat mode (one buffer per cluster): | ||
| 17 | * PrismFlatPostingHeader (16B) | ||
| 18 | * entry[0], entry[1], ... | ||
| 19 | * | ||
| 20 | * Per-entry block (size = PRISM_POSTING_ENTRY_SIZE(dim) bytes): | ||
| 21 | * PrismPostingEntryHeader 20B (tid + flags + f_add/rescale/error) | ||
| 22 | * uint8_t bits[packed_bytes] (dim-dependent, 96B at dim=768) | ||
| 23 | * | ||
| 24 | * Why AoS: when the SIMD kernel strides through entries at | ||
| 25 | * stride=PRISM_POSTING_ENTRY_SIZE(dim), consecutive pages' bit | ||
| 26 | * regions are separated by only ~72 bytes of page-boundary overhead | ||
| 27 | * (opaque + next PageHeader) instead of the ~1472 bytes that an | ||
| 28 | * SoA layout interleaves (metas + f_add + f_rescale + f_error of | ||
| 29 | * the next page before its bits). A small per-page perturbation is | ||
| 30 | * much easier for the HW prefetcher to absorb than a multi-KB | ||
| 31 | * discontinuity — see the BLCKSZ experiment that confirmed the gap | ||
| 32 | * lives at those region transitions. | ||
| 33 | * | ||
| 34 | * Side benefit: reading bits at stride=entry_size also pulls each | ||
| 35 | * entry's f_add/f_rescale/f_error/meta into L1 for free, so phase 3 | ||
| 36 | * (distance conversion + prune) finds them hot. | ||
| 37 | */ | ||
| 38 | |||
| 39 | #ifndef PRISM_POSTING_PAGE_H | ||
| 40 | #define PRISM_POSTING_PAGE_H | ||
| 41 | |||
| 42 | #include <assert.h> /* static_assert pre-C23 (e.g. gcc 11's -std=c2x) */ | ||
| 43 | #include <stdbool.h> | ||
| 44 | #include <stdint.h> | ||
| 45 | #include <string.h> | ||
| 46 | |||
| 47 | #include "core/types.h" | ||
| 48 | #include "index/storage.h" | ||
| 49 | #include "quant/rabitq.h" | ||
| 50 | |||
| 51 | /* ---------------------------------------------------------------- | ||
| 52 | * Constants | ||
| 53 | * ---------------------------------------------------------------- */ | ||
| 54 | |||
| 55 | #define PRISM_POSTING_PAGE_ID 0x4D50 /* "MP" */ | ||
| 56 | |||
| 57 | /* Entry flags */ | ||
| 58 | #define PRISM_POSTING_FLAG_DELETED 0x01 | ||
| 59 | #define PRISM_POSTING_FLAG_BOUNDARY 0x02 | ||
| 60 | |||
| 61 | /* | ||
| 62 | * Page flags. | ||
| 63 | * | ||
| 64 | * The low two bits are a field, not two flags: the page's part of its | ||
| 65 | * list's head. A list's head is the pages that carry its encode reference | ||
| 66 | * (P^T * centroid, 4 * dim bytes). An inline list's head is its first page, | ||
| 67 | * which holds the whole reference followed by entries. A spilled list | ||
| 68 | * (prism_posting_spilled, past 1968 dimensions) spreads the reference over | ||
| 69 | * prism_posting_reference_pages(dim) pages, which the bulk build lays out | ||
| 70 | * contiguously after the first: | ||
| 71 | * | ||
| 72 | * head part inline list spilled list | ||
| 73 | * START whole reference, then entries a page of reference only | ||
| 74 | * MIDDLE (none) a page of reference only | ||
| 75 | * END (none) rest of reference, entries | ||
| 76 | * NONE entries entries | ||
| 77 | * | ||
| 78 | * START means the same on every list: the list's first page, which carries | ||
| 79 | * the head metadata in the opaque and is what a leaf centroid points at. | ||
| 80 | * Whether it also holds entries follows from the dimension. The values share | ||
| 81 | * bits (END includes START's), so read the field with | ||
| 82 | * prism_posting_head_part and compare it; never test one of its bits alone. | ||
| 83 | */ | ||
| 84 | #define PRISM_POSTING_PAGE_HEAD_MASK 0x0003 | ||
| 85 | #define PRISM_POSTING_HEAD_NONE 0x0000 | ||
| 86 | #define PRISM_POSTING_HEAD_START 0x0001 | ||
| 87 | #define PRISM_POSTING_HEAD_MIDDLE 0x0002 | ||
| 88 | #define PRISM_POSTING_HEAD_END 0x0003 | ||
| 89 | |||
| 90 | /* The page's entries are in the fastscan format, not AoS. */ | ||
| 91 | #define PRISM_POSTING_PAGE_FASTSCAN 0x0004 | ||
| 92 | /* | ||
| 93 | * Every entry on the page is dead (AoS: all entries flagged; FASTSCAN: every | ||
| 94 | * lane of every group's tombstone_mask set). Both formats mark entries | ||
| 95 | * individually; this flag is the scan-side shortcut that lets a fully dead | ||
| 96 | * page skip its scoring kernel outright. The page stays linked so compaction | ||
| 97 | * can later reclaim it. Cleared if the page is ever reused for new entries. | ||
| 98 | */ | ||
| 99 | #define PRISM_POSTING_PAGE_TOMBSTONED 0x0008 | ||
| 100 | /* | ||
| 101 | * The page belongs to a chain that has been logically retired — no longer | ||
| 102 | * reachable through the centroid tree — and is awaiting physical reclaim. A | ||
| 103 | * posting-list split sets this on every page of the old chain (head included) | ||
| 104 | * once it has repointed the leaf at the new heads. | ||
| 105 | * | ||
| 106 | * Distinct from TOMBSTONED: a tombstoned page is all-dead but still a live | ||
| 107 | * part of its cluster, so scans skip it and follow the chain past it. A | ||
| 108 | * DELETED chain is off the tree but stays physically LINKED and readable until | ||
| 109 | * reclaim, so an in-flight scanner that already followed a stale leaf pointer | ||
| 110 | * into it still sees a consistent list rather than a gap. | ||
| 111 | * | ||
| 112 | * When this flag is set on a head, the head-metadata overlay in the opaque | ||
| 113 | * (see the union below) holds the deletion XID instead of | ||
| 114 | * live_count/tail_blkno. The reclaim gate compares that XID against the global | ||
| 115 | * visibility horizon before physically reclaiming the chain, so a scanner that | ||
| 116 | * still holds a stale pointer can never have it repurposed underneath it. | ||
| 117 | * Unlike TOMBSTONED, this flag therefore does apply to chain heads: a split | ||
| 118 | * retires the whole old chain, head and all. | ||
| 119 | */ | ||
| 120 | #define PRISM_POSTING_PAGE_DELETED 0x0010 | ||
| 121 | |||
| 122 | /* ---------------------------------------------------------------- | ||
| 123 | * Structs | ||
| 124 | * ---------------------------------------------------------------- */ | ||
| 125 | |||
| 126 | /* | ||
| 127 | * Per-entry metadata. | ||
| 128 | * | ||
| 129 | * In PG: tid is a heap TID for reranking via buffer cache. | ||
| 130 | * In standalone: vector_id packed into tid via ItemPointerSet. | ||
| 131 | */ | ||
| 132 | typedef struct PrismPostingEntryMeta | ||
| 133 | { | ||
| 134 | ItemPointerData tid; /* 6B */ | ||
| 135 | uint8_t flags; | ||
| 136 | uint8_t reserved; | ||
| 137 | } PrismPostingEntryMeta; /* 8B */ | ||
| 138 | |||
| 139 | /* | ||
| 140 | * Per-entry header in the AoS layout: meta + the three RaBitQ | ||
| 141 | * scalar factors, followed by a flexible array of quantized bits | ||
| 142 | * (VS_RABITQ_BYTES(dim) bytes at runtime). | ||
| 143 | * | ||
| 144 | * sizeof(PrismPostingEntryHeader) is 20B — the FAM doesn't contribute | ||
| 145 | * to the struct's static size, so PRISM_POSTING_ENTRY_HEADER_SIZE | ||
| 146 | * stays a clean compile-time constant. The bits array extends past | ||
| 147 | * the struct in memory; callers compute per-entry offsets via | ||
| 148 | * PRISM_POSTING_ENTRY_SIZE(dim) and access bits as `hdr->bits`. | ||
| 149 | */ | ||
| 150 | typedef struct PrismPostingEntryHeader | ||
| 151 | { | ||
| 152 | PrismPostingEntryMeta meta; /* 8B */ | ||
| 153 | float f_add; /* 4B */ | ||
| 154 | float f_rescale; /* 4B */ | ||
| 155 | float f_error; /* 4B */ | ||
| 156 | uint8_t bits[FLEXIBLE_ARRAY_MEMBER]; | ||
| 157 | } PrismPostingEntryHeader; /* 20B + dim-dependent bits */ | ||
| 158 | |||
| 159 | /* | ||
| 160 | * Paged-mode opaque (at end of every BLCKSZ posting page). | ||
| 161 | */ | ||
| 162 | typedef struct PrismPostingPageOpaque | ||
| 163 | { | ||
| 164 | BlockNumber next_blkno; /* next page in chain */ | ||
| 165 | uint32_t cluster_id; | ||
| 166 | uint16_t entry_count; /* entries on this page */ | ||
| 167 | uint16_t flags; /* PRISM_POSTING_PAGE_* */ | ||
| 168 | uint16_t page_id; /* PRISM_POSTING_PAGE_ID */ | ||
| 169 | |||
| 170 | /* | ||
| 171 | * An AoS page's capacity. A fastscan page takes no inserts, so it holds | ||
| 172 | * the length of its run of the list's code stream instead (see the | ||
| 173 | * fastscan page format below). | ||
| 174 | */ | ||
| 175 | union | ||
| 176 | { | ||
| 177 | uint16_t max_entries; | ||
| 178 | uint16_t code_bytes; | ||
| 179 | }; | ||
| 180 | |||
| 181 | /* | ||
| 182 | * Overlay (8 bytes). On a live page these are the per-cluster head | ||
| 183 | * metadata; on a page flagged PRISM_POSTING_PAGE_DELETED they instead | ||
| 184 | * carry the deletion XID for the reclaim gate. The DELETED flag is the | ||
| 185 | * sole discriminator — always read live_count/tail_blkno only when it is | ||
| 186 | * clear and delete_xid only when it is set. A posting-list split retires | ||
| 187 | * the whole old chain, its START page included, so a DELETED head does | ||
| 188 | * carry delete_xid here rather than head metadata; readers of head | ||
| 189 | * metadata (insert, split) first check the flag and treat a retired head | ||
| 190 | * as gone, so the two uses never collide. The anonymous struct/union keeps | ||
| 191 | * op->live_count, op->tail_blkno, and op->delete_xid all directly | ||
| 192 | * accessible. Storing the XID as a backend-neutral uint64_t (not PG's | ||
| 193 | * FullTransactionId) keeps this header usable by the standalone engine; | ||
| 194 | * the PG side converts via U64FromFullTransactionId / the inverse. | ||
| 195 | */ | ||
| 196 | union | ||
| 197 | { | ||
| 198 | struct | ||
| 199 | { | ||
| 200 | /* | ||
| 201 | * Lets the runtime insert path find the chain tail in O(1) and | ||
| 202 | * track per-cluster live size (for LIRE split/merge in a later | ||
| 203 | * phase). tail_blkno == InvalidBlockNumber means "not yet | ||
| 204 | * computed": the first insert walks the chain to fill both fields, | ||
| 205 | * then maintains them incrementally. Left zero / Invalid on | ||
| 206 | * overflow (non-first) pages. | ||
| 207 | */ | ||
| 208 | uint32_t live_count; | ||
| 209 | BlockNumber tail_blkno; | ||
| 210 | }; | ||
| 211 | |||
| 212 | /* Valid only when PRISM_POSTING_PAGE_DELETED is set (see flag | ||
| 213 | * comment). | ||
| 214 | */ | ||
| 215 | uint64_t delete_xid; | ||
| 216 | }; | ||
| 217 | } PrismPostingPageOpaque; /* 24B */ | ||
| 218 | |||
| 219 | /* | ||
| 220 | * True when this page's entries are gone for good, as opposed to moved. | ||
| 221 | * | ||
| 222 | * TOMBSTONED means "nothing here worth scoring" and the scan skips the page. | ||
| 223 | * The reclaim pass sets the same bit on a retired chain, whose entries are not | ||
| 224 | * dead at all -- they were rewritten into the chain's replacements -- so | ||
| 225 | * skipping there drops results that a stale-pointer scan is entitled to see. | ||
| 226 | * DELETED separates the two: it is set only by the retire pass, so a page | ||
| 227 | * carrying both moved rather than died, and its contents are still intact and | ||
| 228 | * linked until #224 makes the pages reusable. | ||
| 229 | */ | ||
| 230 | static inline bool | ||
| 231 | 59971 | prism_posting_page_all_dead(const PrismPostingPageOpaque *op) | |
| 232 | { | ||
| 233 |
6/8✓ Branch 0 taken 21 times.
✓ Branch 1 taken 57402 times.
✓ Branch 2 taken 7 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 92 times.
✓ Branch 5 taken 2456 times.
✓ Branch 6 taken 92 times.
✗ Branch 7 not taken.
|
59985 | return (op->flags & PRISM_POSTING_PAGE_TOMBSTONED) != 0 && |
| 234 |
2/2✓ Branch 0 taken 12 times.
✓ Branch 1 taken 2 times.
|
14 | (op->flags & PRISM_POSTING_PAGE_DELETED) == 0; |
| 235 | } | ||
| 236 | |||
| 237 | /* | ||
| 238 | * Flat-mode header (at start of flat page buffer). | ||
| 239 | * No PG PageHeaderData — avoids the uint16_t page size limit. | ||
| 240 | */ | ||
| 241 | typedef struct PrismFlatPostingHeader | ||
| 242 | { | ||
| 243 | uint32_t max_entries; /* == capacity (sized for count) */ | ||
| 244 | uint32_t entry_count; | ||
| 245 | uint32_t cluster_id; | ||
| 246 | uint32_t _pad; | ||
| 247 | } PrismFlatPostingHeader; /* 16B */ | ||
| 248 | |||
| 249 | /* ---------------------------------------------------------------- | ||
| 250 | * Size calculations | ||
| 251 | * ---------------------------------------------------------------- */ | ||
| 252 | |||
| 253 | /* Bytes in the per-entry header (meta + 3 floats) */ | ||
| 254 | #define PRISM_POSTING_ENTRY_HEADER_SIZE \ | ||
| 255 | sizeof(PrismPostingEntryHeader) /* 20B */ | ||
| 256 | |||
| 257 | /* Byte offset of bits[] within one entry. Equal to the header size | ||
| 258 | * because bits[] is the FAM right after the header. */ | ||
| 259 | #define PRISM_POSTING_ENTRY_BITS_OFFSET offsetof(PrismPostingEntryHeader, bits) | ||
| 260 | |||
| 261 | /* Bytes per entry in bits region */ | ||
| 262 | #define PRISM_POSTING_BITS_PER_ENTRY(dim) VS_RABITQ_BYTES(dim) | ||
| 263 | |||
| 264 | /* Entry stride must be a multiple of PrismPostingEntryHeader's alignment | ||
| 265 | * (4 bytes — the float fields) so entry i's float members land on | ||
| 266 | * properly aligned addresses regardless of `i`. For dim values where | ||
| 267 | * VS_RABITQ_BYTES(dim) isn't already a multiple of 4 (i.e., dim not | ||
| 268 | * a multiple of 32, such as dim=16 or dim=100), we pad up. */ | ||
| 269 | #define PRISM_POSTING_ENTRY_ALIGN 4u | ||
| 270 | |||
| 271 | /* Total bytes per entry: header + bits, padded up to entry alignment | ||
| 272 | * (= 116 at dim=768; 24 at dim=16). */ | ||
| 273 | #define PRISM_POSTING_ENTRY_SIZE(dim) \ | ||
| 274 | (((PRISM_POSTING_ENTRY_HEADER_SIZE + PRISM_POSTING_BITS_PER_ENTRY(dim)) + \ | ||
| 275 | PRISM_POSTING_ENTRY_ALIGN - 1u) & \ | ||
| 276 | ~(PRISM_POSTING_ENTRY_ALIGN - 1u)) | ||
| 277 | |||
| 278 | /* | ||
| 279 | * A posting list's first page holds a full-precision encode reference (a | ||
| 280 | * vector of 32-bit floats). The reference fits into the first page, together | ||
| 281 | * with at least one entry, up to dimension PRISM_INDEX_NARROW_MAX_DIM. | ||
| 282 | * Vectors of higher dimensions spill over to the following page(s) in a | ||
| 283 | * chain of reference pages (prism_posting_spilled). | ||
| 284 | * | ||
| 285 | * Derived at 8-byte alignment, the largest MAXALIGN PostgreSQL uses, so it | ||
| 286 | * is one constant on every platform; where MAXALIGN is smaller the head has | ||
| 287 | * a few bytes of slack and the threshold is merely conservative. The static | ||
| 288 | * asserts keep the number honest against layout changes. | ||
| 289 | */ | ||
| 290 | #define PRISM_INDEX_NARROW_MAX_DIM 1968 | ||
| 291 | |||
| 292 | #define PRISM_CEILING_ALIGN(len) (((size_t)(len) + 7) & ~(size_t)7) | ||
| 293 | |||
| 294 | static_assert( | ||
| 295 | BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - | ||
| 296 | sizeof(PrismPostingPageOpaque) - | ||
| 297 | PRISM_CEILING_ALIGN( | ||
| 298 | PRISM_INDEX_NARROW_MAX_DIM * sizeof(float)) >= | ||
| 299 | PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_NARROW_MAX_DIM), | ||
| 300 | "an inline head must fit the encode reference plus one entry"); | ||
| 301 | static_assert( | ||
| 302 | BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - | ||
| 303 | sizeof(PrismPostingPageOpaque) - | ||
| 304 | PRISM_CEILING_ALIGN( | ||
| 305 | (PRISM_INDEX_NARROW_MAX_DIM + 1) * | ||
| 306 | sizeof(float)) < | ||
| 307 | PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_NARROW_MAX_DIM + 1), | ||
| 308 | "the inline threshold is tight: one dimension more must not fit"); | ||
| 309 | |||
| 310 | /* | ||
| 311 | * Hard dimension ceiling for the index layout, which is imposed by the | ||
| 312 | * Hadamard fast-rotation bound. | ||
| 313 | * | ||
| 314 | * A dimension above PRISM_INDEX_NARROW_MAX_DIM is admitted only when | ||
| 315 | * vs_fast_rotate_supported() holds (see prism_index_dim_supported), and | ||
| 316 | * the Hadamard transform's inline sign storage stops at | ||
| 317 | * VS_FAST_ROTATE_MAX_DIM. | ||
| 318 | */ | ||
| 319 | #define PRISM_INDEX_MAX_DIM 8192 | ||
| 320 | |||
| 321 | static_assert( | ||
| 322 | PRISM_INDEX_MAX_DIM <= VS_FAST_ROTATE_MAX_DIM, | ||
| 323 | "every admitted dimension must rotate through the fast path"); | ||
| 324 | |||
| 325 | /* | ||
| 326 | * The one gate every build applies: an inline layout up to the narrow | ||
| 327 | * threshold, and past it a spilled layout only where the fast rotation | ||
| 328 | * applies (dim = 2^m * k with 2^m >= 4 and odd k <= 8: 2048, 3072, 4096, | ||
| 329 | * 6144, 8192 pass; 3000 does not). Takes a uint32_t so a wider dimension | ||
| 330 | * is range-checked before it narrows to a Dimension. | ||
| 331 | */ | ||
| 332 | static inline bool | ||
| 333 | 16801 | prism_index_dim_supported(uint32_t dim) | |
| 334 | { | ||
| 335 |
4/4✓ Branch 0 taken 16798 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 16536 times.
|
16801 | if (dim == 0 || dim > PRISM_INDEX_MAX_DIM) |
| 336 | 8 | return false; | |
| 337 |
2/2✓ Branch 0 taken 4085 times.
✓ Branch 1 taken 12707 times.
|
16792 | if (dim <= PRISM_INDEX_NARROW_MAX_DIM) |
| 338 | 4050 | return true; | |
| 339 | 12521 | return vs_fast_rotate_supported((Dimension)dim); | |
| 340 | } | ||
| 341 | |||
| 342 | static_assert( | ||
| 343 | BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - | ||
| 344 | sizeof(PrismPostingPageOpaque) >= | ||
| 345 | PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_MAX_DIM), | ||
| 346 | "an overflow page must hold one entry at the ceiling"); | ||
| 347 | |||
| 348 | /* Usable space on a BLCKSZ page (between content start and opaque) */ | ||
| 349 | static inline uint32_t | ||
| 350 | 14406274 | prism_posting_page_usable(void) | |
| 351 | { | ||
| 352 | 14406274 | return BLCKSZ - (uint32_t)MAXALIGN(SizeOfPageHeaderData) - | |
| 353 | sizeof(PrismPostingPageOpaque); | ||
| 354 | } | ||
| 355 | |||
| 356 | /* Space occupied by P^T * centroid on an inline first page (MAXALIGN'd) */ | ||
| 357 | static inline uint32_t | ||
| 358 | 69815945 | prism_posting_pt_centroid_size(Dimension dim) | |
| 359 | { | ||
| 360 | 69815945 | return (uint32_t)MAXALIGN(dim * sizeof(float)); | |
| 361 | } | ||
| 362 | |||
| 363 | /* | ||
| 364 | * True when the encode reference no longer fits beside one entry on the | ||
| 365 | * first page, so the list spreads it over several head pages. Equivalent to | ||
| 366 | * dim > PRISM_INDEX_NARROW_MAX_DIM at 8-byte MAXALIGN; computed from the | ||
| 367 | * layout so a different alignment cannot disagree with the pages. | ||
| 368 | */ | ||
| 369 | static inline bool | ||
| 370 | 69604647 | prism_posting_spilled(Dimension dim) | |
| 371 | { | ||
| 372 | 69604647 | return prism_posting_pt_centroid_size(dim) + | |
| 373 |
7/8✓ Branch 0 taken 14607 times.
✓ Branch 1 taken 17618 times.
✓ Branch 2 taken 2722 times.
✓ Branch 3 taken 29053 times.
✓ Branch 4 taken 273 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 124554 times.
✓ Branch 7 taken 10862570 times.
|
54058171 | PRISM_POSTING_ENTRY_SIZE(dim) > |
| 374 | 14324954 | prism_posting_page_usable(); | |
| 375 | } | ||
| 376 | |||
| 377 | /* Floats of the reference on a full head page: its whole usable area. */ | ||
| 378 | #define PRISM_POSTING_REFERENCE_PAGE_FLOATS \ | ||
| 379 | ((BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - \ | ||
| 380 | sizeof(PrismPostingPageOpaque)) / \ | ||
| 381 | sizeof(float)) | ||
| 382 | |||
| 383 | /* | ||
| 384 | * Pages that carry the encode reference, the list's head pages: one for an | ||
| 385 | * inline layout, else START, MIDDLE and END. This is also the head stride of | ||
| 386 | * the bulk-built head region (prism_leaf_head_blkno), so a leaf's head pages | ||
| 387 | * are contiguous. | ||
| 388 | * | ||
| 389 | * A spilled list always has a START and an END page: the smallest spilled | ||
| 390 | * dimension the index accepts (2048) takes more than a page of floats. | ||
| 391 | */ | ||
| 392 | static inline uint32_t | ||
| 393 | 41326100 | prism_posting_reference_pages(Dimension dim) | |
| 394 | { | ||
| 395 |
3/3✓ Branch 0 taken 297275 times.
✓ Branch 1 taken 40459146 times.
✓ Branch 2 taken 569679 times.
|
41326100 | if (!prism_posting_spilled(dim)) |
| 396 | 7767488 | return 1; | |
| 397 | 866954 | return ((uint32_t)dim + PRISM_POSTING_REFERENCE_PAGE_FLOATS - 1) / | |
| 398 | PRISM_POSTING_REFERENCE_PAGE_FLOATS; | ||
| 399 | } | ||
| 400 | |||
| 401 | /* Floats of the reference on head page i of a spilled list (0 = START). */ | ||
| 402 | static inline uint32_t | ||
| 403 | 377662 | prism_posting_reference_page_floats(Dimension dim, uint32_t i) | |
| 404 | { | ||
| 405 | 377662 | uint32_t start = i * (uint32_t)PRISM_POSTING_REFERENCE_PAGE_FLOATS; | |
| 406 | |||
| 407 |
3/4✓ Branch 0 taken 124888 times.
✓ Branch 1 taken 247315 times.
✓ Branch 2 taken 545 times.
✗ Branch 3 not taken.
|
376484 | if (start >= dim) |
| 408 | 334 | return 0; | |
| 409 | 374835 | return (dim - start) < PRISM_POSTING_REFERENCE_PAGE_FLOATS | |
| 410 | ? (dim - start) | ||
| 411 | 377328 | : (uint32_t)PRISM_POSTING_REFERENCE_PAGE_FLOATS; | |
| 412 | } | ||
| 413 | |||
| 414 | /* The page's part of its list's head (see the page flags above). */ | ||
| 415 | static inline uint16_t | ||
| 416 | 28298718 | prism_posting_head_part(uint16_t flags) | |
| 417 | { | ||
| 418 |
3/4✓ Branch 0 taken 10987414 times.
✓ Branch 1 taken 141 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 148 times.
|
17091567 | return flags & PRISM_POSTING_PAGE_HEAD_MASK; |
| 419 | } | ||
| 420 | |||
| 421 | /* Whether the page is its list's first page, the one with head metadata. */ | ||
| 422 | static inline bool | ||
| 423 | 18871 | prism_posting_is_head_start(uint16_t flags) | |
| 424 | { | ||
| 425 |
3/4✓ Branch 0 taken 2008 times.
✓ Branch 1 taken 14454 times.
✓ Branch 2 taken 455 times.
✗ Branch 3 not taken.
|
18871 | return prism_posting_head_part(flags) == PRISM_POSTING_HEAD_START; |
| 426 | } | ||
| 427 | |||
| 428 | /* | ||
| 429 | * Whether the page holds part of the reference and no entries: a spilled | ||
| 430 | * list's START page, or a MIDDLE page. Code that looks at a page on its | ||
| 431 | * own uses this to tell it from a page with entries: its capacity is 0, the | ||
| 432 | * builder writes no entries to it, and conversion and inspection count it | ||
| 433 | * as reference. An END page also holds reference, but entries follow it. | ||
| 434 | */ | ||
| 435 | static inline bool | ||
| 436 | 13938430 | prism_posting_is_reference_only_page(uint16_t flags, Dimension dim) | |
| 437 | { | ||
| 438 | 13938430 | uint16_t part = prism_posting_head_part(flags); | |
| 439 | |||
| 440 |
2/2✓ Branch 0 taken 11065144 times.
✓ Branch 1 taken 2873286 times.
|
13938430 | if (part == PRISM_POSTING_HEAD_MIDDLE) |
| 441 | 46390 | return true; | |
| 442 |
5/5✓ Branch 0 taken 13680664 times.
✓ Branch 1 taken 168170 times.
✓ Branch 2 taken 10923421 times.
✓ Branch 3 taken 134505 times.
✓ Branch 4 taken 2622738 times.
|
24827019 | return part == PRISM_POSTING_HEAD_START && prism_posting_spilled(dim); |
| 443 | } | ||
| 444 | |||
| 445 | /* | ||
| 446 | * The reference prefix: the part of the reference a list's first entry page | ||
| 447 | * holds ahead of its entries. That is the whole reference on an inline | ||
| 448 | * START page and the rest of it on an END page. Entries, AoS or fastscan, | ||
| 449 | * start this many bytes into the page content, so the prefix sets where a | ||
| 450 | * reader finds them and how many fit. MAXALIGN'd so the entries start | ||
| 451 | * aligned. | ||
| 452 | */ | ||
| 453 | static inline uint32_t | ||
| 454 | 358242 | prism_posting_ref_prefix_size(Dimension dim) | |
| 455 | { | ||
| 456 |
3/3✓ Branch 0 taken 2421 times.
✓ Branch 1 taken 343086 times.
✓ Branch 2 taken 12735 times.
|
358242 | if (!prism_posting_spilled(dim)) |
| 457 | 211298 | return prism_posting_pt_centroid_size(dim); | |
| 458 | |||
| 459 | 15156 | uint32_t last = prism_posting_reference_pages(dim) - 1; | |
| 460 | |||
| 461 |
1/2✓ Branch 0 taken 2421 times.
✗ Branch 1 not taken.
|
17577 | return (uint32_t)MAXALIGN( |
| 462 | prism_posting_reference_page_floats(dim, last) * sizeof(float)); | ||
| 463 | } | ||
| 464 | |||
| 465 | /* | ||
| 466 | * Whether the page has a reference prefix, so its entries start after it: | ||
| 467 | * an inline START page or an END page. Every other page that holds entries | ||
| 468 | * has them from the start of its content. | ||
| 469 | */ | ||
| 470 | static inline bool | ||
| 471 | 533930 | prism_posting_has_ref_prefix(uint16_t flags, Dimension dim) | |
| 472 | { | ||
| 473 | 533930 | uint16_t part = prism_posting_head_part(flags); | |
| 474 | |||
| 475 |
2/2✓ Branch 0 taken 192780 times.
✓ Branch 1 taken 341150 times.
|
533930 | if (part == PRISM_POSTING_HEAD_END) |
| 476 | 12965 | return true; | |
| 477 |
5/5✓ Branch 0 taken 353650 times.
✓ Branch 1 taken 164903 times.
✓ Branch 2 taken 575 times.
✓ Branch 3 taken 352727 times.
✓ Branch 4 taken 348 times.
|
557779 | return part == PRISM_POSTING_HEAD_START && !prism_posting_spilled(dim); |
| 478 | } | ||
| 479 | |||
| 480 | /* | ||
| 481 | * Head block of a leaf, and back. Heads sit in a region at first_posting | ||
| 482 | * with a fixed stride: 1 for an inline layout, | ||
| 483 | * prism_posting_reference_pages(dim) for a spilled one, so the reference | ||
| 484 | * pages follow their head. The stride is passed rather than derived from | ||
| 485 | * dim because the standalone in-RAM build addresses leaves by index | ||
| 486 | * (first_posting 0, stride 1). | ||
| 487 | */ | ||
| 488 | static inline BlockNumber | ||
| 489 | 38260 | prism_leaf_head_blkno( | |
| 490 | BlockNumber first_posting, uint32_t leaf, uint32_t stride) | ||
| 491 | { | ||
| 492 | 38260 | return first_posting + (BlockNumber)leaf * stride; | |
| 493 | } | ||
| 494 | |||
| 495 | static inline uint32_t | ||
| 496 | 13645470 | prism_route_head_to_leaf( | |
| 497 | BlockNumber first_posting, BlockNumber head, uint32_t stride) | ||
| 498 | { | ||
| 499 |
2/2✓ Branch 0 taken 48600 times.
✓ Branch 1 taken 24000 times.
|
13645470 | return (uint32_t)(head - first_posting) / stride; |
| 500 | } | ||
| 501 | |||
| 502 | /* Max entries on a page with no reference ahead of its entries */ | ||
| 503 | static inline uint32_t | ||
| 504 | 49386 | prism_posting_max_entries(Dimension dim) | |
| 505 | { | ||
| 506 | 48329 | return prism_posting_page_usable() / PRISM_POSTING_ENTRY_SIZE(dim); | |
| 507 | } | ||
| 508 | |||
| 509 | /* | ||
| 510 | * Max entries on a list's first entry page, after its reference prefix | ||
| 511 | * (prism_posting_ref_prefix_size): an inline START page or an END page. | ||
| 512 | */ | ||
| 513 | static inline uint32_t | ||
| 514 | 45463 | prism_posting_max_entries_first(Dimension dim) | |
| 515 | { | ||
| 516 | 45463 | return (prism_posting_page_usable() - prism_posting_ref_prefix_size(dim)) / | |
| 517 | 45463 | PRISM_POSTING_ENTRY_SIZE(dim); | |
| 518 | } | ||
| 519 | |||
| 520 | /* Buffer size for a flat page with count entries */ | ||
| 521 | static inline size_t | ||
| 522 | 188 | prism_posting_flat_page_size(Dimension dim, uint32_t count) | |
| 523 | { | ||
| 524 | 376 | return sizeof(PrismFlatPostingHeader) + | |
| 525 | 188 | (size_t)count * PRISM_POSTING_ENTRY_SIZE(dim); | |
| 526 | } | ||
| 527 | |||
| 528 | /* ---------------------------------------------------------------- | ||
| 529 | * Paged-mode access — opaque via PG PageGetSpecialPointer | ||
| 530 | * ---------------------------------------------------------------- */ | ||
| 531 | |||
| 532 | static inline PrismPostingPageOpaque * | ||
| 533 | 29325052 | prism_posting_opaque(Page page) | |
| 534 | { | ||
| 535 |
17/18✓ Branch 1 taken 789 times.
✓ Branch 2 taken 10056 times.
✓ Branch 3 taken 1283 times.
✓ Branch 4 taken 22202 times.
✓ Branch 5 taken 2805 times.
✓ Branch 6 taken 290 times.
✓ Branch 7 taken 141 times.
✓ Branch 8 taken 1 times.
✓ Branch 9 taken 32818 times.
✓ Branch 10 taken 19594 times.
✓ Branch 11 taken 19842 times.
✓ Branch 12 taken 2599 times.
✓ Branch 13 taken 3720 times.
✓ Branch 14 taken 33849 times.
✓ Branch 15 taken 107 times.
✓ Branch 16 taken 206 times.
✗ Branch 19 not taken.
✓ Branch 20 taken 148 times.
|
29077109 | return (PrismPostingPageOpaque *)PageGetSpecialPointer(page); |
| 536 | } | ||
| 537 | |||
| 538 | /* | ||
| 539 | * Is this page a posting page at all (not a wrong-kind page, and not one | ||
| 540 | * only extended but never initialized)? Guard on the special-area size | ||
| 541 | * before reading the opaque, so a page of another kind is never misread | ||
| 542 | * through the posting layout. MAXALIGN, not a bare sizeof: PageGetSpecialSize | ||
| 543 | * reports the on-disk (MAXALIGN'd) special-area size PageInit reserved, and a | ||
| 544 | * struct whose size isn't already a multiple of MAXIMUM_ALIGNOF would | ||
| 545 | * otherwise silently stop matching the moment a field is added. | ||
| 546 | */ | ||
| 547 | static inline bool | ||
| 548 | 13814412 | prism_page_is_posting(Page page) | |
| 549 | { | ||
| 550 |
2/3✓ Branch 0 taken 10993828 times.
✓ Branch 1 taken 2820584 times.
✗ Branch 2 not taken.
|
16634986 | return !PageIsNew(page) && |
| 551 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 10993821 times.
|
13814402 | PageGetSpecialSize(page) == |
| 552 |
2/2✓ Branch 0 taken 13814402 times.
✓ Branch 1 taken 10 times.
|
16634986 | MAXALIGN(sizeof(PrismPostingPageOpaque)) && |
| 553 |
1/3✗ Branch 0 not taken.
✓ Branch 1 taken 13814395 times.
✗ Branch 2 not taken.
|
13814395 | prism_posting_opaque(page)->page_id == PRISM_POSTING_PAGE_ID; |
| 554 | } | ||
| 555 | |||
| 556 | static inline uint32_t | ||
| 557 | 1069 | prism_posting_page_count(Page page) | |
| 558 | { | ||
| 559 | 1069 | return prism_posting_opaque(page)->entry_count; | |
| 560 | } | ||
| 561 | |||
| 562 | /* Room for one more AoS entry. A fastscan page never takes one. */ | ||
| 563 | static inline bool | ||
| 564 | 573222 | prism_posting_page_has_room(Page page) | |
| 565 | { | ||
| 566 | 573222 | PrismPostingPageOpaque *op = prism_posting_opaque(page); | |
| 567 |
1/2✓ Branch 0 taken 573222 times.
✗ Branch 1 not taken.
|
1018255 | return !(op->flags & PRISM_POSTING_PAGE_FASTSCAN) && |
| 568 |
2/2✓ Branch 0 taken 444563 times.
✓ Branch 1 taken 128659 times.
|
573222 | op->entry_count < op->max_entries; |
| 569 | } | ||
| 570 | |||
| 571 | /* | ||
| 572 | * Per-cluster head metadata (read from the START page). tail_blkno == | ||
| 573 | * InvalidBlockNumber means it has not been computed yet — see | ||
| 574 | * prism_posting_insert_one, which fills it lazily on the first insert. | ||
| 575 | */ | ||
| 576 | static inline uint32_t | ||
| 577 | 804 | prism_posting_head_live_count(Page head) | |
| 578 | { | ||
| 579 | 804 | return prism_posting_opaque(head)->live_count; | |
| 580 | } | ||
| 581 | |||
| 582 | static inline BlockNumber | ||
| 583 | 288 | prism_posting_head_tail(Page head) | |
| 584 | { | ||
| 585 | 288 | return prism_posting_opaque(head)->tail_blkno; | |
| 586 | } | ||
| 587 | |||
| 588 | /* ---------------------------------------------------------------- | ||
| 589 | * Content-based AoS access — header-agnostic | ||
| 590 | * | ||
| 591 | * Entries are laid out contiguously: entry i starts at | ||
| 592 | * content + i * PRISM_POSTING_ENTRY_SIZE(dim) | ||
| 593 | * and consists of an PrismPostingEntryHeader followed by | ||
| 594 | * VS_RABITQ_BYTES(dim) bytes of bits. The SIMD kernel strides | ||
| 595 | * through bits[] at stride = PRISM_POSTING_ENTRY_SIZE(dim), starting | ||
| 596 | * from prism_posting_first_bits(content). | ||
| 597 | * ---------------------------------------------------------------- */ | ||
| 598 | |||
| 599 | /* Header for entry i (access fields via the struct: hdr->meta, | ||
| 600 | * hdr->f_add, hdr->f_rescale, hdr->f_error). */ | ||
| 601 | static inline PrismPostingEntryHeader * | ||
| 602 | 6602465 | prism_posting_entry_at(char *content, uint32_t i, Dimension dim) | |
| 603 | { | ||
| 604 | 12882821 | return (PrismPostingEntryHeader *)(content + | |
| 605 | 6602465 | (size_t)i * | |
| 606 |
4/4✓ Branch 0 taken 73870 times.
✓ Branch 1 taken 80444 times.
✓ Branch 2 taken 82561 times.
✓ Branch 3 taken 10017 times.
|
6602465 | PRISM_POSTING_ENTRY_SIZE(dim)); |
| 607 | } | ||
| 608 | |||
| 609 | /* Bits pointer for entry i (immediately follows entry i's header). */ | ||
| 610 | static inline uint8_t * | ||
| 611 | 2 | prism_posting_entry_bits_at( | |
| 612 | char *content, uint32_t max_entries, Dimension dim, uint32_t i) | ||
| 613 | { | ||
| 614 | (void)max_entries; | ||
| 615 | 2 | return prism_posting_entry_at(content, i, dim)->bits; | |
| 616 | } | ||
| 617 | |||
| 618 | /* Pointer to entry 0's bits — the base the SIMD kernel uses, with | ||
| 619 | * stride = PRISM_POSTING_ENTRY_SIZE(dim). */ | ||
| 620 | static inline uint8_t * | ||
| 621 | 41433 | prism_posting_first_bits(char *content) | |
| 622 | { | ||
| 623 | 41433 | return ((PrismPostingEntryHeader *)content)->bits; | |
| 624 | } | ||
| 625 | |||
| 626 | /* ---------------------------------------------------------------- | ||
| 627 | * Paged-mode convenience wrappers | ||
| 628 | * | ||
| 629 | * These use PageGetContents for the content pointer and read | ||
| 630 | * max_entries from the opaque. Used by page init/add and tests. | ||
| 631 | * ---------------------------------------------------------------- */ | ||
| 632 | |||
| 633 | static inline char * | ||
| 634 | 401184 | prism_posting_content(Page page) | |
| 635 | { | ||
| 636 | 401184 | return PageGetContents(page); | |
| 637 | } | ||
| 638 | |||
| 639 | /* | ||
| 640 | * On an inline first page, P^T * centroid is stored right after PageHeader, | ||
| 641 | * before the entries. On a spilled list's head pages it is that page's | ||
| 642 | * floats of the reference; prism_posting_reference_read gathers the whole | ||
| 643 | * vector. | ||
| 644 | */ | ||
| 645 | static inline const float * | ||
| 646 | 13853330 | prism_posting_pt_centroid(Page page) | |
| 647 | { | ||
| 648 | 13853330 | return (const float *)PageGetContents(page); | |
| 649 | } | ||
| 650 | |||
| 651 | static inline float * | ||
| 652 | 13832 | prism_posting_pt_centroid_mut(Page page) | |
| 653 | { | ||
| 654 | 13832 | return (float *)PageGetContents(page); | |
| 655 | } | ||
| 656 | |||
| 657 | /* | ||
| 658 | * Gather a posting list's encode reference, inline or spilled, into `out` | ||
| 659 | * (dim floats). Reads the head pages one at a time, releasing each before | ||
| 660 | * the next (the PG storage pins a single buffer). Returns the first page | ||
| 661 | * that holds entries: the START page for an inline layout, the END page for | ||
| 662 | * a spilled one. Errors out on a chain that is not what the layout says it | ||
| 663 | * must be. | ||
| 664 | */ | ||
| 665 | BlockNumber prism_posting_reference_read( | ||
| 666 | VsStorage *storage, BlockNumber head, Dimension dim, float *out); | ||
| 667 | |||
| 668 | /* | ||
| 669 | * prism_posting_reference_read without the floats on the head's END page: | ||
| 670 | * returns that page, for a caller that reads it for its entries anyway and | ||
| 671 | * takes the floats from it with prism_posting_reference_read_end. Sets | ||
| 672 | * *cluster_id to the list's. For an inline layout this is the whole gather. | ||
| 673 | */ | ||
| 674 | BlockNumber prism_posting_reference_read_to_end( | ||
| 675 | VsStorage *storage, | ||
| 676 | BlockNumber head, | ||
| 677 | Dimension dim, | ||
| 678 | float *out, | ||
| 679 | uint32_t *cluster_id); | ||
| 680 | |||
| 681 | /* | ||
| 682 | * Check that `page`, at blk, is the head END page of the list at head | ||
| 683 | * with cluster_id, and copy its floats of the reference into out. | ||
| 684 | */ | ||
| 685 | void prism_posting_reference_read_end( | ||
| 686 | BlockNumber head, | ||
| 687 | BlockNumber blk, | ||
| 688 | Page page, | ||
| 689 | uint32_t cluster_id, | ||
| 690 | Dimension dim, | ||
| 691 | float *out); | ||
| 692 | |||
| 693 | /* | ||
| 694 | * The same gather for a caller that already copied the START page's floats | ||
| 695 | * while it had the head pinned: continues at `next`, the head's next_blkno, | ||
| 696 | * with head page 1. Inline layouts have nothing left to read and get `next` | ||
| 697 | * back unchanged. | ||
| 698 | */ | ||
| 699 | BlockNumber prism_posting_reference_read_rest( | ||
| 700 | VsStorage *storage, | ||
| 701 | BlockNumber head, | ||
| 702 | BlockNumber next, | ||
| 703 | uint32_t cluster_id, | ||
| 704 | Dimension dim, | ||
| 705 | float *out); | ||
| 706 | |||
| 707 | /* | ||
| 708 | * Lay out head page i of a spilled list in `page`: init it as the head's | ||
| 709 | * START page for i = 0, its END page for the last, else a MIDDLE page, plus | ||
| 710 | * `extra_flags`, and copy its floats of `ref`. An END page starts with no | ||
| 711 | * entries. next_blkno is left Invalid for the caller to link. | ||
| 712 | */ | ||
| 713 | void prism_posting_reference_page_fill( | ||
| 714 | Page page, | ||
| 715 | uint32_t cluster_id, | ||
| 716 | Dimension dim, | ||
| 717 | uint32_t i, | ||
| 718 | const float *ref, | ||
| 719 | uint16_t extra_flags); | ||
| 720 | |||
| 721 | /* ---------------------------------------------------------------- | ||
| 722 | * Chain walks | ||
| 723 | * | ||
| 724 | * A posting list is a chain of pages linked by next_blkno. Every caller | ||
| 725 | * that traverses one has to read the link before releasing the page and | ||
| 726 | * release it before moving on; these keep that order in one place. | ||
| 727 | * | ||
| 728 | * The scan path deliberately does not use them. It holds a page across the | ||
| 729 | * SIMD kernels that consume it, interleaves the next page's prefetch, and | ||
| 730 | * handles flat mode (a single page, no chain) and page_base mode (memory it | ||
| 731 | * does not release) -- so its stepping is a different shape, not a | ||
| 732 | * duplicate of this one. | ||
| 733 | * ---------------------------------------------------------------- */ | ||
| 734 | |||
| 735 | /* | ||
| 736 | * Where a read walk currently is. The callback may release the page early | ||
| 737 | * and keep working: the next block is already read, so the walk does not | ||
| 738 | * need it afterwards. That matters for work which must not hold a page -- | ||
| 739 | * fetching heap tuples through the same storage, which holds one page at a | ||
| 740 | * time and would take over the slot. | ||
| 741 | */ | ||
| 742 | typedef struct PrismPostingChainPos | ||
| 743 | { | ||
| 744 | VsStorage *storage; | ||
| 745 | BlockNumber blkno; | ||
| 746 | Page page; /* NULL once released */ | ||
| 747 | BlockNumber next; /* read before the callback runs */ | ||
| 748 | bool first; | ||
| 749 | } PrismPostingChainPos; | ||
| 750 | |||
| 751 | static inline void | ||
| 752 | 8105 | prism_posting_chain_release(PrismPostingChainPos *pos) | |
| 753 | { | ||
| 754 |
2/2✓ Branch 0 taken 7090 times.
✓ Branch 1 taken 1015 times.
|
8105 | if (pos->page != NULL) |
| 755 | { | ||
| 756 | 7090 | vs_storage_release_page(pos->storage, pos->blkno); | |
| 757 | 7090 | pos->page = NULL; | |
| 758 | } | ||
| 759 | 8105 | } | |
| 760 | |||
| 761 | /* Return false to stop the walk. */ | ||
| 762 | typedef bool (*PrismPostingChainCb)(PrismPostingChainPos *pos, void *state); | ||
| 763 | |||
| 764 | void prism_posting_chain_walk( | ||
| 765 | VsStorage *storage, | ||
| 766 | BlockNumber head, | ||
| 767 | PrismPostingChainCb cb, | ||
| 768 | void *state); | ||
| 769 | |||
| 770 | /* | ||
| 771 | * Mutating walk: the callback gets the opaque of a page held for write, and | ||
| 772 | * every page is committed. For chain-wide flag changes, where the body is a | ||
| 773 | * line or two and the walk is all of the code. | ||
| 774 | */ | ||
| 775 | typedef void (*PrismPostingChainMutateCb)( | ||
| 776 | PrismPostingPageOpaque *op, void *state); | ||
| 777 | |||
| 778 | void prism_posting_chain_mutate( | ||
| 779 | VsStorage *storage, | ||
| 780 | BlockNumber head, | ||
| 781 | PrismPostingChainMutateCb cb, | ||
| 782 | void *state); | ||
| 783 | |||
| 784 | /* | ||
| 785 | * Entry content of any posting page: past the reference prefix on an inline | ||
| 786 | * START page or an END page, else the start of the page. A page that holds | ||
| 787 | * only reference has no entries, so its content is the (empty) start of the | ||
| 788 | * page. | ||
| 789 | */ | ||
| 790 | static inline char * | ||
| 791 | 401184 | prism_posting_page_content(Page page, Dimension dim) | |
| 792 | { | ||
| 793 | 401184 | uint16_t flags = prism_posting_opaque(page)->flags; | |
| 794 |
2/2✓ Branch 0 taken 91713 times.
✓ Branch 1 taken 27382 times.
|
401184 | char *start = prism_posting_content(page); |
| 795 | |||
| 796 | 401184 | return prism_posting_has_ref_prefix(flags, dim) | |
| 797 | 273714 | ? start + prism_posting_ref_prefix_size(dim) | |
| 798 |
2/2✓ Branch 0 taken 273714 times.
✓ Branch 1 taken 127470 times.
|
583185 | : start; |
| 799 | } | ||
| 800 | |||
| 801 | /* Paged-mode convenience wrappers — these assume pages with no reference | ||
| 802 | * prefix (content starts right after PageHeader). For the others, go | ||
| 803 | * through prism_posting_page_content. */ | ||
| 804 | static inline PrismPostingEntryHeader * | ||
| 805 | 2 | prism_posting_entry(Page page, uint32_t i, Dimension dim) | |
| 806 | { | ||
| 807 | 2 | return prism_posting_entry_at(PageGetContents(page), i, dim); | |
| 808 | } | ||
| 809 | |||
| 810 | static inline uint8_t * | ||
| 811 | 2 | prism_posting_entry_bits( | |
| 812 | Page page, uint32_t max_entries, Dimension dim, uint32_t i) | ||
| 813 | { | ||
| 814 | 2 | return prism_posting_entry_bits_at( | |
| 815 | PageGetContents(page), max_entries, dim, i); | ||
| 816 | } | ||
| 817 | |||
| 818 | /* ---------------------------------------------------------------- | ||
| 819 | * Flat-mode access | ||
| 820 | * ---------------------------------------------------------------- */ | ||
| 821 | |||
| 822 | static inline PrismFlatPostingHeader * | ||
| 823 | 13130 | prism_flat_posting_header(char *buf) | |
| 824 | { | ||
| 825 | 13130 | return (PrismFlatPostingHeader *)buf; | |
| 826 | } | ||
| 827 | |||
| 828 | static inline char * | ||
| 829 | 12942 | prism_flat_posting_content(char *buf) | |
| 830 | { | ||
| 831 |
0/2✗ Branch 0 not taken.
✗ Branch 1 not taken.
|
12942 | return buf + sizeof(PrismFlatPostingHeader); |
| 832 | } | ||
| 833 | |||
| 834 | /* ---------------------------------------------------------------- | ||
| 835 | * Standalone helper: pack/extract vector_id in ItemPointerData | ||
| 836 | * ---------------------------------------------------------------- */ | ||
| 837 | |||
| 838 | static inline void | ||
| 839 | 37664 | prism_posting_set_vector_id(ItemPointerData *tid, uint32_t vector_id) | |
| 840 | { | ||
| 841 | 37664 | ItemPointerSet(tid, (BlockNumber)vector_id, 0); | |
| 842 | 37664 | } | |
| 843 | |||
| 844 | static inline uint32_t | ||
| 845 | 159470 | prism_posting_get_vector_id(const ItemPointerData *tid) | |
| 846 | { | ||
| 847 | 159470 | return (uint32_t)ItemPointerGetBlockNumber(tid); | |
| 848 | } | ||
| 849 | |||
| 850 | /* ---------------------------------------------------------------- | ||
| 851 | * TID ↔ uint64_t encoding for VsTopK | ||
| 852 | * | ||
| 853 | * Both standalone and PG store TIDs in VsTopK's uint64_t id field. | ||
| 854 | * For standalone: vector_id is packed in BlockNumber with offset=0, | ||
| 855 | * so encode yields (vector_id << 16) and decode_vector_id shifts | ||
| 856 | * back. For PG: full ItemPointerData (block + offset) fits in 48 | ||
| 857 | * bits of the uint64_t. | ||
| 858 | * ---------------------------------------------------------------- */ | ||
| 859 | |||
| 860 | static inline uint64_t | ||
| 861 | 777094 | prism_posting_encode_tid(const ItemPointerData *tid) | |
| 862 | { | ||
| 863 | 777094 | return ((uint64_t)ItemPointerGetBlockNumber(tid) << 16) | | |
| 864 | 777094 | (uint64_t)ItemPointerGetOffsetNumber(tid); | |
| 865 | } | ||
| 866 | |||
| 867 | static inline ItemPointerData | ||
| 868 | 41921 | prism_posting_decode_tid(uint64_t id) | |
| 869 | { | ||
| 870 | 41921 | ItemPointerData tid; | |
| 871 | 41921 | ItemPointerSet(&tid, (BlockNumber)(id >> 16), (OffsetNumber)(id & 0xFFFF)); | |
| 872 | 41921 | return tid; | |
| 873 | } | ||
| 874 | |||
| 875 | /* Convenience for standalone: extract vector_id from encoded TID. | ||
| 876 | * Works because prism_posting_set_vector_id stores vid in BlockNumber | ||
| 877 | * with offset=0, so (id >> 16) == vid. */ | ||
| 878 | static inline uint32_t | ||
| 879 | 148417 | prism_posting_decode_vector_id(uint64_t id) | |
| 880 | { | ||
| 881 | 148417 | return (uint32_t)(id >> 16); | |
| 882 | } | ||
| 883 | |||
| 884 | /* ---------------------------------------------------------------- | ||
| 885 | * Paged-mode page operations | ||
| 886 | * ---------------------------------------------------------------- */ | ||
| 887 | |||
| 888 | /* | ||
| 889 | * Initialize an empty BLCKSZ posting page. | ||
| 890 | */ | ||
| 891 | void prism_posting_page_init( | ||
| 892 | Page page, uint32_t cluster_id, Dimension dim, uint16_t flags); | ||
| 893 | |||
| 894 | /* | ||
| 895 | * Add one entry to a BLCKSZ page. Returns false if page is full. | ||
| 896 | */ | ||
| 897 | bool prism_posting_page_add( | ||
| 898 | Page page, | ||
| 899 | Dimension dim, | ||
| 900 | ItemPointerData tid, | ||
| 901 | float f_add, | ||
| 902 | float f_rescale, | ||
| 903 | float f_error, | ||
| 904 | const uint8_t *bits, | ||
| 905 | uint8_t entry_flags); | ||
| 906 | |||
| 907 | /* ---------------------------------------------------------------- | ||
| 908 | * Flat-mode page operations | ||
| 909 | * ---------------------------------------------------------------- */ | ||
| 910 | |||
| 911 | /* | ||
| 912 | * Initialize a flat posting page buffer. buf must be at least | ||
| 913 | * prism_posting_flat_page_size(dim, max_entries) bytes. | ||
| 914 | */ | ||
| 915 | void | ||
| 916 | prism_posting_flat_init(char *buf, uint32_t max_entries, uint32_t cluster_id); | ||
| 917 | |||
| 918 | /* | ||
| 919 | * Add one entry to a flat page. Returns false if full. | ||
| 920 | */ | ||
| 921 | bool prism_posting_flat_add( | ||
| 922 | char *buf, | ||
| 923 | Dimension dim, | ||
| 924 | ItemPointerData tid, | ||
| 925 | float f_add, | ||
| 926 | float f_rescale, | ||
| 927 | float f_error, | ||
| 928 | const uint8_t *bits, | ||
| 929 | uint8_t entry_flags); | ||
| 930 | |||
| 931 | /* ---------------------------------------------------------------- | ||
| 932 | * Fastscan page format | ||
| 933 | * | ||
| 934 | * Fastscan scores 32 vectors at once with in-register table lookups on | ||
| 935 | * their 1-bit codes, which is much faster than scoring AoS entries one at a | ||
| 936 | * time. A fastscan list stores its vectors in 32-vector groups. Each group | ||
| 937 | * has codes, VS_FASTSCAN_GROUP_BYTES(dim) bytes interleaved for the kernel, | ||
| 938 | * and 580 bytes of group metadata: | ||
| 939 | * ItemPointerData tids[32] 192B | ||
| 940 | * float f_add[32] 128B | ||
| 941 | * float f_rescale[32] 128B | ||
| 942 | * float f_error[32] 128B | ||
| 943 | * uint32_t tombstone_mask 4B (bit v set => lane v is dead) | ||
| 944 | * | ||
| 945 | * Page content (after the reference prefix on a list's first entry page): | ||
| 946 | * group metadata[ngroups] ngroups × 580B | ||
| 947 | * codes[code_bytes] the page's run of the code stream | ||
| 948 | * | ||
| 949 | * A spilled list's stream starts on its head's END page, after the rest of | ||
| 950 | * the reference. | ||
| 951 | * | ||
| 952 | * The codes of all groups form one stream that continues from page to page. | ||
| 953 | * A group's codes can break at any PRISM_FASTSCAN_CHUNK_BYTES (64-byte) | ||
| 954 | * boundary, so a page wastes less than 64 bytes instead of the gap a whole | ||
| 955 | * group does not fit. Every kernel steps in sizes that divide 64 bytes, so | ||
| 956 | * the scan scores a split group in place, one page at a time. | ||
| 957 | * | ||
| 958 | * Group metadata never splits. It goes on the page where its group's codes | ||
| 959 | * end, because that is where the scan has the complete sums to prune with, | ||
| 960 | * and the scan holds one page at a time. When it does not fit there, it is | ||
| 961 | * deferred to the start of the next page and the next group's codes use the | ||
| 962 | * space. | ||
| 963 | * | ||
| 964 | * Metadata comes first on the page so readers that need only metadata | ||
| 965 | * (deleted-vector marking, split, inspect) find group g's at a fixed offset, | ||
| 966 | * without knowing where groups start in the code stream. | ||
| 967 | * | ||
| 968 | * In the opaque, entry_count counts the vectors whose metadata is on the | ||
| 969 | * page and code_bytes is the length of its code run. Only the list's last | ||
| 970 | * group can be partial, so a page holds ceil(entry_count / 32) groups' | ||
| 971 | * metadata. A page's position in the stream is not stored: the scan reads a | ||
| 972 | * list from its head and carries the position from page to page. | ||
| 973 | * | ||
| 974 | * tombstone_mask is the per-lane analog of an AoS entry's | ||
| 975 | * PRISM_POSTING_FLAG_DELETED (see fastscan-design.md for why the codes | ||
| 976 | * can't be marked in place). The builder writes it as zero. | ||
| 977 | * | ||
| 978 | * Pages are identified by PRISM_POSTING_PAGE_FASTSCAN in opaque flags. | ||
| 979 | * ---------------------------------------------------------------- */ | ||
| 980 | |||
| 981 | #include "quant/fastscan.h" | ||
| 982 | |||
| 983 | static_assert( | ||
| 984 | VS_FASTSCAN_GROUP == 32, | ||
| 985 | "tombstone_mask packs one bit per lane into a uint32_t"); | ||
| 986 | |||
| 987 | /* | ||
| 988 | * Code bytes per split unit: 16 dimensions of 32 vectors. The widest kernel | ||
| 989 | * step (AVX-512, 64 bytes) and the 16-bit lookup table's 128-byte block of | ||
| 990 | * two columns both line up with it, so a kernel call can start at any chunk. | ||
| 991 | */ | ||
| 992 | #define PRISM_FASTSCAN_CHUNK_BYTES 64u | ||
| 993 | |||
| 994 | /* | ||
| 995 | * Most groups a scan can have in flight, meaning it has started summing | ||
| 996 | * their codes but not yet reached their metadata. That is the group whose | ||
| 997 | * codes it is reading plus up to two whose metadata was deferred to the next | ||
| 998 | * page. The scan keeps running sums for each, so the bound keeps its state | ||
| 999 | * fixed. Two deferred groups are enough to fill the space deferred metadata | ||
| 1000 | * leaves with codes at every dimension above about 72. | ||
| 1001 | */ | ||
| 1002 | #define PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS 3u | ||
| 1003 | |||
| 1004 | /* Bytes of one group's metadata. */ | ||
| 1005 | #define PRISM_FASTSCAN_META_BYTES \ | ||
| 1006 | ((uint32_t)(VS_FASTSCAN_GROUP * sizeof(ItemPointerData) + \ | ||
| 1007 | VS_FASTSCAN_GROUP * 3 * sizeof(float) + sizeof(uint32_t))) | ||
| 1008 | |||
| 1009 | static_assert( | ||
| 1010 | PRISM_FASTSCAN_META_BYTES % sizeof(float) == 0, | ||
| 1011 | "group metadata keeps the floats of the next group's aligned"); | ||
| 1012 | |||
| 1013 | /* Bytes per 32-vector group, metadata and codes together */ | ||
| 1014 | static inline uint32_t | ||
| 1015 | 497 | prism_fastscan_group_section_bytes(Dimension dim) | |
| 1016 | { | ||
| 1017 | 497 | return PRISM_FASTSCAN_META_BYTES + VS_FASTSCAN_GROUP_BYTES(dim); | |
| 1018 | } | ||
| 1019 | |||
| 1020 | /* | ||
| 1021 | * Bytes for metadata and codes on a fastscan page, after the reference | ||
| 1022 | * prefix when the page is a list's first entry page (ref_prefix). | ||
| 1023 | */ | ||
| 1024 | static inline uint32_t | ||
| 1025 | 58153 | prism_fastscan_page_space(Dimension dim, bool ref_prefix) | |
| 1026 | { | ||
| 1027 | 58650 | uint32_t usable = prism_posting_page_usable(); | |
| 1028 | |||
| 1029 |
2/2✓ Branch 0 taken 34536 times.
✓ Branch 1 taken 17978 times.
|
56354 | return ref_prefix ? usable - prism_posting_ref_prefix_size(dim) : usable; |
| 1030 | } | ||
| 1031 | |||
| 1032 | /* Groups with metadata on a fastscan page, from its vector count. */ | ||
| 1033 | static inline uint32_t | ||
| 1034 | 42865 | prism_fastscan_page_groups(const PrismPostingPageOpaque *op) | |
| 1035 | { | ||
| 1036 |
2/2✓ Branch 0 taken 12709 times.
✓ Branch 1 taken 9108 times.
|
42865 | return ((uint32_t)op->entry_count + VS_FASTSCAN_GROUP - 1) / |
| 1037 | VS_FASTSCAN_GROUP; | ||
| 1038 | } | ||
| 1039 | |||
| 1040 | /* | ||
| 1041 | * The max number of groups' metadata a page can hold. Besides the metadata | ||
| 1042 | * deferred from the previous page, a page holds metadata only for groups | ||
| 1043 | * whose codes end on it, and its code bytes reach the end of at most | ||
| 1044 | * space / group-code-size + 1 groups. | ||
| 1045 | */ | ||
| 1046 | static inline uint32_t | ||
| 1047 | 15088 | prism_fastscan_max_groups(Dimension dim, bool ref_prefix) | |
| 1048 | { | ||
| 1049 |
2/2✓ Branch 0 taken 3840 times.
✓ Branch 1 taken 1446 times.
|
15088 | uint32_t space = prism_fastscan_page_space(dim, ref_prefix); |
| 1050 | 15088 | uint32_t deferred = PRISM_FASTSCAN_MAX_INFLIGHT_GROUPS - 1; | |
| 1051 | 15088 | uint32_t by_meta = space / PRISM_FASTSCAN_META_BYTES; | |
| 1052 | 15088 | uint32_t by_code = deferred + 1 + space / VS_FASTSCAN_GROUP_BYTES(dim); | |
| 1053 | |||
| 1054 | 15088 | return by_meta < by_code ? by_meta : by_code; | |
| 1055 | } | ||
| 1056 | |||
| 1057 | /* Max entries on a fastscan page with no reference prefix */ | ||
| 1058 | static inline uint32_t | ||
| 1059 | 10666 | prism_fastscan_max_entries(Dimension dim) | |
| 1060 | { | ||
| 1061 | 10666 | return prism_fastscan_max_groups(dim, false) * VS_FASTSCAN_GROUP; | |
| 1062 | } | ||
| 1063 | |||
| 1064 | /* Max entries on a list's first fastscan entry page, after the prefix */ | ||
| 1065 | static inline uint32_t | ||
| 1066 | 4088 | prism_fastscan_max_entries_first(Dimension dim) | |
| 1067 | { | ||
| 1068 | 4088 | return prism_fastscan_max_groups(dim, true) * VS_FASTSCAN_GROUP; | |
| 1069 | } | ||
| 1070 | |||
| 1071 | /* | ||
| 1072 | * Entries a full page holds on average, for cost estimates. Fastscan pages | ||
| 1073 | * waste under a chunk each, so the code and metadata bytes per vector set | ||
| 1074 | * the density. | ||
| 1075 | */ | ||
| 1076 | static inline double | ||
| 1077 | 497 | prism_fastscan_entries_per_page(Dimension dim) | |
| 1078 | { | ||
| 1079 | 497 | return (double)prism_fastscan_page_space(dim, false) * VS_FASTSCAN_GROUP / | |
| 1080 | 497 | prism_fastscan_group_section_bytes(dim); | |
| 1081 | } | ||
| 1082 | |||
| 1083 | /* | ||
| 1084 | * Upper bound on the entries a single posting page can hold, whatever format | ||
| 1085 | * it is in. Neither format's figure bounds the other: fastscan packs more | ||
| 1086 | * than AoS at low dimension and allows for deferred group metadata, while | ||
| 1087 | * AoS packs more where a page holds under one group's codes. The figures | ||
| 1088 | * for a page without a reference prefix bound the others too. Callers sizing a | ||
| 1089 | * buffer for one page's worth of entries want this rather than either half. | ||
| 1090 | */ | ||
| 1091 | static inline uint32_t | ||
| 1092 | 4407 | prism_posting_max_entries_any_format(Dimension dim) | |
| 1093 | { | ||
| 1094 | 4407 | uint32_t aos = prism_posting_max_entries(dim); | |
| 1095 | 4407 | uint32_t fs = prism_fastscan_max_entries(dim); | |
| 1096 | 4407 | return aos > fs ? aos : fs; | |
| 1097 | } | ||
| 1098 | |||
| 1099 | /* Entries a full page holds in the denser of the two formats. */ | ||
| 1100 | static inline double | ||
| 1101 | 497 | prism_posting_entries_per_page(Dimension dim) | |
| 1102 | { | ||
| 1103 | 497 | double aos = (double)prism_posting_max_entries(dim); | |
| 1104 | 497 | double fs = prism_fastscan_entries_per_page(dim); | |
| 1105 | 497 | return aos > fs ? aos : fs; | |
| 1106 | } | ||
| 1107 | |||
| 1108 | /* | ||
| 1109 | * The entry ceiling a page of this format and position really has. All four | ||
| 1110 | * combinations differ: a fastscan page packs more entries than an AoS one, | ||
| 1111 | * and a list's first entry page gives up room to the reference prefix. | ||
| 1112 | * Bounding an AoS page by the fastscan figure (or by the larger of the two) | ||
| 1113 | * would still let prism_posting_entry_at walk off the page. | ||
| 1114 | */ | ||
| 1115 | static inline uint32_t | ||
| 1116 | 61049 | prism_posting_page_cap(const PrismPostingPageOpaque *op, Dimension dim) | |
| 1117 | { | ||
| 1118 | 61049 | bool first = prism_posting_has_ref_prefix(op->flags, dim); | |
| 1119 | |||
| 1120 |
3/3✓ Branch 0 taken 12312 times.
✓ Branch 1 taken 1098 times.
✓ Branch 2 taken 47639 times.
|
61049 | if (prism_posting_is_reference_only_page(op->flags, dim)) |
| 1121 | 350 | return 0; | |
| 1122 |
2/2✓ Branch 0 taken 4895 times.
✓ Branch 1 taken 55056 times.
|
59951 | if (op->flags & PRISM_POSTING_PAGE_FASTSCAN) |
| 1123 | 3577 | return first ? prism_fastscan_max_entries_first(dim) | |
| 1124 |
2/2✓ Branch 0 taken 3577 times.
✓ Branch 1 taken 1318 times.
|
4985 | : prism_fastscan_max_entries(dim); |
| 1125 | |||
| 1126 | 42614 | return first ? prism_posting_max_entries_first(dim) | |
| 1127 |
2/2✓ Branch 0 taken 42614 times.
✓ Branch 1 taken 12442 times.
|
55056 | : prism_posting_max_entries(dim); |
| 1128 | } | ||
| 1129 | |||
| 1130 | /* | ||
| 1131 | * Reject an on-disk entry_count past that ceiling before it drives a loop, so | ||
| 1132 | * a corrupt or truncated page cannot read past the page end. A fastscan page | ||
| 1133 | * also has its group metadata and code run checked to fit. | ||
| 1134 | */ | ||
| 1135 | void prism_posting_check_count(BlockNumber blkno, Page page, Dimension dim); | ||
| 1136 | |||
| 1137 | /* | ||
| 1138 | * The fastscan half of prism_posting_check_count, against the entry ceiling | ||
| 1139 | * and content space of a page in this one's position. The scan passes bounds | ||
| 1140 | * it computed once, since it checks every page it reads. | ||
| 1141 | */ | ||
| 1142 | void prism_fastscan_check_page( | ||
| 1143 | BlockNumber blkno, | ||
| 1144 | const PrismPostingPageOpaque *op, | ||
| 1145 | uint32_t cap, | ||
| 1146 | uint32_t space); | ||
| 1147 | |||
| 1148 | /* ---------------------------------------------------------------- | ||
| 1149 | * Fastscan page accessors | ||
| 1150 | * | ||
| 1151 | * All take the content pointer (past PageHeader, past pt_centroid on first | ||
| 1152 | * pages). The group index g counts the groups with metadata on that page. | ||
| 1153 | * ---------------------------------------------------------------- */ | ||
| 1154 | |||
| 1155 | static inline char * | ||
| 1156 | 143672 | prism_fastscan_group_base(char *content, uint32_t g) | |
| 1157 | { | ||
| 1158 | 143672 | return content + (size_t)g * PRISM_FASTSCAN_META_BYTES; | |
| 1159 | } | ||
| 1160 | |||
| 1161 | /* The page's run of the code stream, after the metadata of ngroups groups. */ | ||
| 1162 | static inline uint8_t * | ||
| 1163 | 39673 | prism_fastscan_page_codes(char *content, uint32_t ngroups) | |
| 1164 | { | ||
| 1165 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 9108 times.
|
39673 | return (uint8_t *)content + (size_t)ngroups * PRISM_FASTSCAN_META_BYTES; |
| 1166 | } | ||
| 1167 | |||
| 1168 | static inline ItemPointerData * | ||
| 1169 | 33420 | prism_fastscan_group_tids(char *content, uint32_t g) | |
| 1170 | { | ||
| 1171 |
6/6✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
|
33744 | return (ItemPointerData *)prism_fastscan_group_base(content, g); |
| 1172 | } | ||
| 1173 | |||
| 1174 | static inline float * | ||
| 1175 | 102030 | prism_fastscan_group_f_add(char *content, uint32_t g) | |
| 1176 | { | ||
| 1177 |
6/6✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
|
102929 | return (float *)(prism_fastscan_group_base(content, g) + |
| 1178 | VS_FASTSCAN_GROUP * sizeof(ItemPointerData)); | ||
| 1179 | } | ||
| 1180 | |||
| 1181 | static inline float * | ||
| 1182 | 79836 | prism_fastscan_group_f_rescale(char *content, uint32_t g) | |
| 1183 | { | ||
| 1184 |
6/6✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
|
80735 | return prism_fastscan_group_f_add(content, g) + VS_FASTSCAN_GROUP; |
| 1185 | } | ||
| 1186 | |||
| 1187 | static inline float * | ||
| 1188 | 57642 | prism_fastscan_group_f_error(char *content, uint32_t g) | |
| 1189 | { | ||
| 1190 |
6/6✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
|
58541 | return prism_fastscan_group_f_rescale(content, g) + VS_FASTSCAN_GROUP; |
| 1191 | } | ||
| 1192 | |||
| 1193 | /* | ||
| 1194 | * Per-group dead-lane bitmap: bit v set means lane v's TID is dead. Read and | ||
| 1195 | * write through this pointer directly (it aliases the live page); there is no | ||
| 1196 | * copy to write back. Only valid lanes (v < the group's entry count) are ever | ||
| 1197 | * set -- the builder writes the word as zero and nothing else touches it, so | ||
| 1198 | * an unmarked lane, including every lane past entry_count on a partial final | ||
| 1199 | * group, reads as live. | ||
| 1200 | */ | ||
| 1201 | static inline uint32_t * | ||
| 1202 | 36347 | prism_fastscan_group_tombstone_mask(char *content, uint32_t g) | |
| 1203 | { | ||
| 1204 |
6/6✓ Branch 0 taken 8 times.
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 3848 times.
✓ Branch 3 taken 5283 times.
✓ Branch 4 taken 310 times.
✓ Branch 5 taken 127 times.
|
36347 | return (uint32_t *)(prism_fastscan_group_f_error(content, g) + |
| 1205 | VS_FASTSCAN_GROUP); | ||
| 1206 | } | ||
| 1207 | |||
| 1208 | /* | ||
| 1209 | * Bit test and set for one lane of a tombstone_mask word already read out | ||
| 1210 | * of (or about to be written back into) a page via the accessor above. | ||
| 1211 | * Every reader and writer of the mask goes through these two rather than | ||
| 1212 | * writing out the bit math itself, so there is exactly one place that | ||
| 1213 | * says "lane v is bit 1u << v". | ||
| 1214 | */ | ||
| 1215 | static inline bool | ||
| 1216 | 160542 | prism_fastscan_lane_is_tombstoned(uint32_t mask, uint32_t lane) | |
| 1217 | { | ||
| 1218 |
6/6✓ Branch 0 taken 2160 times.
✓ Branch 1 taken 27447 times.
✓ Branch 2 taken 71 times.
✓ Branch 3 taken 73799 times.
✓ Branch 4 taken 30 times.
✓ Branch 5 taken 1399 times.
|
160542 | return (mask & (1u << lane)) != 0; |
| 1219 | } | ||
| 1220 | |||
| 1221 | static inline uint32_t | ||
| 1222 | 2147 | prism_fastscan_lane_set_tombstone(uint32_t mask, uint32_t lane) | |
| 1223 | { | ||
| 1224 | 2147 | return mask | (1u << lane); | |
| 1225 | } | ||
| 1226 | |||
| 1227 | #endif /* PRISM_POSTING_PAGE_H */ | ||
| 1228 |