| 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 | * (pt_centroid — on first 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 | /* Page flags */ | ||
| 62 | #define PRISM_POSTING_PAGE_FIRST 0x0001 | ||
| 63 | #define PRISM_POSTING_PAGE_OVERFLOW 0x0002 | ||
| 64 | #define PRISM_POSTING_PAGE_FASTSCAN 0x0004 /* reserved for phase 2 */ | ||
| 65 | /* | ||
| 66 | * Every entry on the page is dead (AoS: all entries flagged; FASTSCAN: every | ||
| 67 | * lane of every group's tombstone_mask set). Both formats mark entries | ||
| 68 | * individually; this flag is the scan-side shortcut that lets a fully dead | ||
| 69 | * page skip its scoring kernel outright. The page stays linked so compaction | ||
| 70 | * can later reclaim it. Cleared if the page is ever reused for new entries. | ||
| 71 | */ | ||
| 72 | #define PRISM_POSTING_PAGE_TOMBSTONED 0x0008 | ||
| 73 | /* | ||
| 74 | * The page belongs to a chain that has been logically retired — no longer | ||
| 75 | * reachable through the centroid tree — and is awaiting physical reclaim. A | ||
| 76 | * posting-list split sets this on every page of the old chain (head included) | ||
| 77 | * once it has repointed the leaf at the new heads. | ||
| 78 | * | ||
| 79 | * Distinct from TOMBSTONED: a tombstoned page is all-dead but still a live | ||
| 80 | * part of its cluster, so scans skip it and follow the chain past it. A | ||
| 81 | * DELETED chain is off the tree but stays physically LINKED and readable until | ||
| 82 | * reclaim, so an in-flight scanner that already followed a stale leaf pointer | ||
| 83 | * into it still sees a consistent list rather than a gap. | ||
| 84 | * | ||
| 85 | * When this flag is set on a head, the head-metadata overlay in the opaque | ||
| 86 | * (see the union below) holds the deletion XID instead of | ||
| 87 | * live_count/tail_blkno. The reclaim gate compares that XID against the global | ||
| 88 | * visibility horizon before physically reclaiming the chain, so a scanner that | ||
| 89 | * still holds a stale pointer can never have it repurposed underneath it. | ||
| 90 | * Unlike TOMBSTONED, this flag therefore does apply to chain heads: a split | ||
| 91 | * retires the whole old chain, head and all. | ||
| 92 | */ | ||
| 93 | #define PRISM_POSTING_PAGE_DELETED 0x0010 | ||
| 94 | |||
| 95 | /* ---------------------------------------------------------------- | ||
| 96 | * Structs | ||
| 97 | * ---------------------------------------------------------------- */ | ||
| 98 | |||
| 99 | /* | ||
| 100 | * Per-entry metadata. | ||
| 101 | * | ||
| 102 | * In PG: tid is a heap TID for reranking via buffer cache. | ||
| 103 | * In standalone: vector_id packed into tid via ItemPointerSet. | ||
| 104 | */ | ||
| 105 | typedef struct PrismPostingEntryMeta | ||
| 106 | { | ||
| 107 | ItemPointerData tid; /* 6B */ | ||
| 108 | uint8_t flags; | ||
| 109 | uint8_t reserved; | ||
| 110 | } PrismPostingEntryMeta; /* 8B */ | ||
| 111 | |||
| 112 | /* | ||
| 113 | * Per-entry header in the AoS layout: meta + the three RaBitQ | ||
| 114 | * scalar factors, followed by a flexible array of quantized bits | ||
| 115 | * (VS_RABITQ_BYTES(dim) bytes at runtime). | ||
| 116 | * | ||
| 117 | * sizeof(PrismPostingEntryHeader) is 20B — the FAM doesn't contribute | ||
| 118 | * to the struct's static size, so PRISM_POSTING_ENTRY_HEADER_SIZE | ||
| 119 | * stays a clean compile-time constant. The bits array extends past | ||
| 120 | * the struct in memory; callers compute per-entry offsets via | ||
| 121 | * PRISM_POSTING_ENTRY_SIZE(dim) and access bits as `hdr->bits`. | ||
| 122 | */ | ||
| 123 | typedef struct PrismPostingEntryHeader | ||
| 124 | { | ||
| 125 | PrismPostingEntryMeta meta; /* 8B */ | ||
| 126 | float f_add; /* 4B */ | ||
| 127 | float f_rescale; /* 4B */ | ||
| 128 | float f_error; /* 4B */ | ||
| 129 | uint8_t bits[FLEXIBLE_ARRAY_MEMBER]; | ||
| 130 | } PrismPostingEntryHeader; /* 20B + dim-dependent bits */ | ||
| 131 | |||
| 132 | /* | ||
| 133 | * Paged-mode opaque (at end of every BLCKSZ posting page). | ||
| 134 | */ | ||
| 135 | typedef struct PrismPostingPageOpaque | ||
| 136 | { | ||
| 137 | BlockNumber next_blkno; /* next page in chain */ | ||
| 138 | uint32_t cluster_id; | ||
| 139 | uint16_t entry_count; /* entries on this page */ | ||
| 140 | uint16_t flags; /* FIRST | OVERFLOW | FASTSCAN | TOMBSTONED | | ||
| 141 | * DELETED */ | ||
| 142 | uint16_t page_id; /* PRISM_POSTING_PAGE_ID */ | ||
| 143 | uint16_t max_entries; /* capacity of this page */ | ||
| 144 | |||
| 145 | /* | ||
| 146 | * Overlay (8 bytes). On a live page these are the per-cluster head | ||
| 147 | * metadata; on a page flagged PRISM_POSTING_PAGE_DELETED they instead | ||
| 148 | * carry the deletion XID for the reclaim gate. The DELETED flag is the | ||
| 149 | * sole discriminator — always read live_count/tail_blkno only when it is | ||
| 150 | * clear and delete_xid only when it is set. A posting-list split retires | ||
| 151 | * the whole old chain, its FIRST head included, so a DELETED head does | ||
| 152 | * carry delete_xid here rather than head metadata; readers of head | ||
| 153 | * metadata (insert, split) first check the flag and treat a retired head | ||
| 154 | * as gone, so the two uses never collide. The anonymous struct/union keeps | ||
| 155 | * op->live_count, op->tail_blkno, and op->delete_xid all directly | ||
| 156 | * accessible. Storing the XID as a backend-neutral uint64_t (not PG's | ||
| 157 | * FullTransactionId) keeps this header usable by the standalone engine; | ||
| 158 | * the PG side converts via U64FromFullTransactionId / the inverse. | ||
| 159 | */ | ||
| 160 | union | ||
| 161 | { | ||
| 162 | struct | ||
| 163 | { | ||
| 164 | /* | ||
| 165 | * Lets the runtime insert path find the chain tail in O(1) and | ||
| 166 | * track per-cluster live size (for LIRE split/merge in a later | ||
| 167 | * phase). tail_blkno == InvalidBlockNumber means "not yet | ||
| 168 | * computed": the first insert walks the chain to fill both fields, | ||
| 169 | * then maintains them incrementally. Left zero / Invalid on | ||
| 170 | * overflow (non-first) pages. | ||
| 171 | */ | ||
| 172 | uint32_t live_count; | ||
| 173 | BlockNumber tail_blkno; | ||
| 174 | }; | ||
| 175 | |||
| 176 | /* Valid only when PRISM_POSTING_PAGE_DELETED is set (see flag | ||
| 177 | * comment). | ||
| 178 | */ | ||
| 179 | uint64_t delete_xid; | ||
| 180 | }; | ||
| 181 | } PrismPostingPageOpaque; /* 24B */ | ||
| 182 | |||
| 183 | /* | ||
| 184 | * True when this page's entries are gone for good, as opposed to moved. | ||
| 185 | * | ||
| 186 | * TOMBSTONED means "nothing here worth scoring" and the scan skips the page. | ||
| 187 | * The reclaim pass sets the same bit on a retired chain, whose entries are not | ||
| 188 | * dead at all -- they were rewritten into the chain's replacements -- so | ||
| 189 | * skipping there drops results that a stale-pointer scan is entitled to see. | ||
| 190 | * DELETED separates the two: it is set only by the retire pass, so a page | ||
| 191 | * carrying both moved rather than died, and its contents are still intact and | ||
| 192 | * linked until #224 makes the pages reusable. | ||
| 193 | */ | ||
| 194 | static inline bool | ||
| 195 | 38863 | prism_posting_page_all_dead(const PrismPostingPageOpaque *op) | |
| 196 | { | ||
| 197 |
4/4✓ Branch 0 taken 10 times.
✓ Branch 1 taken 37194 times.
✓ Branch 2 taken 1651 times.
✓ Branch 3 taken 8 times.
|
38873 | return (op->flags & PRISM_POSTING_PAGE_TOMBSTONED) != 0 && |
| 198 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
|
10 | (op->flags & PRISM_POSTING_PAGE_DELETED) == 0; |
| 199 | } | ||
| 200 | |||
| 201 | /* | ||
| 202 | * Flat-mode header (at start of flat page buffer). | ||
| 203 | * No PG PageHeaderData — avoids the uint16_t page size limit. | ||
| 204 | */ | ||
| 205 | typedef struct PrismFlatPostingHeader | ||
| 206 | { | ||
| 207 | uint32_t max_entries; /* == capacity (sized for count) */ | ||
| 208 | uint32_t entry_count; | ||
| 209 | uint32_t cluster_id; | ||
| 210 | uint32_t _pad; | ||
| 211 | } PrismFlatPostingHeader; /* 16B */ | ||
| 212 | |||
| 213 | /* ---------------------------------------------------------------- | ||
| 214 | * Size calculations | ||
| 215 | * ---------------------------------------------------------------- */ | ||
| 216 | |||
| 217 | /* Bytes in the per-entry header (meta + 3 floats) */ | ||
| 218 | #define PRISM_POSTING_ENTRY_HEADER_SIZE \ | ||
| 219 | sizeof(PrismPostingEntryHeader) /* 20B */ | ||
| 220 | |||
| 221 | /* Byte offset of bits[] within one entry. Equal to the header size | ||
| 222 | * because bits[] is the FAM right after the header. */ | ||
| 223 | #define PRISM_POSTING_ENTRY_BITS_OFFSET offsetof(PrismPostingEntryHeader, bits) | ||
| 224 | |||
| 225 | /* Bytes per entry in bits region */ | ||
| 226 | #define PRISM_POSTING_BITS_PER_ENTRY(dim) VS_RABITQ_BYTES(dim) | ||
| 227 | |||
| 228 | /* Entry stride must be a multiple of PrismPostingEntryHeader's alignment | ||
| 229 | * (4 bytes — the float fields) so entry i's float members land on | ||
| 230 | * properly aligned addresses regardless of `i`. For dim values where | ||
| 231 | * VS_RABITQ_BYTES(dim) isn't already a multiple of 4 (i.e., dim not | ||
| 232 | * a multiple of 32, such as dim=16 or dim=100), we pad up. */ | ||
| 233 | #define PRISM_POSTING_ENTRY_ALIGN 4u | ||
| 234 | |||
| 235 | /* Total bytes per entry: header + bits, padded up to entry alignment | ||
| 236 | * (= 116 at dim=768; 24 at dim=16). */ | ||
| 237 | #define PRISM_POSTING_ENTRY_SIZE(dim) \ | ||
| 238 | (((PRISM_POSTING_ENTRY_HEADER_SIZE + PRISM_POSTING_BITS_PER_ENTRY(dim)) + \ | ||
| 239 | PRISM_POSTING_ENTRY_ALIGN - 1u) & \ | ||
| 240 | ~(PRISM_POSTING_ENTRY_ALIGN - 1u)) | ||
| 241 | |||
| 242 | /* | ||
| 243 | * Hard dimension ceiling for the index layout. A posting list's first page | ||
| 244 | * carries the list's float encode reference (MAXALIGN(dim * sizeof(float)) | ||
| 245 | * bytes) and must still hold at least one posting entry; that binds before | ||
| 246 | * the float-format centroid page (one dim * sizeof(float) entry, ~2036) and | ||
| 247 | * the metadata page's inline mean. Past the ceiling the first-page capacity | ||
| 248 | * arithmetic underflows, so index creation must reject the dimension up | ||
| 249 | * front. | ||
| 250 | * | ||
| 251 | * The number is derived at 8-byte alignment, the largest MAXALIGN | ||
| 252 | * PostgreSQL uses, so it is one constant on every platform. Where MAXALIGN | ||
| 253 | * is smaller (32-bit x86) the first page has a few bytes of slack and the | ||
| 254 | * ceiling is merely conservative. The static asserts keep the number honest | ||
| 255 | * against layout changes, at that same fixed alignment. | ||
| 256 | */ | ||
| 257 | #define PRISM_INDEX_MAX_DIM 1968 | ||
| 258 | |||
| 259 | #define PRISM_CEILING_ALIGN(len) (((size_t)(len) + 7) & ~(size_t)7) | ||
| 260 | |||
| 261 | static_assert( | ||
| 262 | BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - | ||
| 263 | sizeof(PrismPostingPageOpaque) - | ||
| 264 | PRISM_CEILING_ALIGN( | ||
| 265 | PRISM_INDEX_MAX_DIM * sizeof(float)) >= | ||
| 266 | PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_MAX_DIM), | ||
| 267 | "posting first page must fit the encode reference plus one entry"); | ||
| 268 | static_assert( | ||
| 269 | BLCKSZ - PRISM_CEILING_ALIGN(SizeOfPageHeaderData) - | ||
| 270 | sizeof(PrismPostingPageOpaque) - | ||
| 271 | PRISM_CEILING_ALIGN( | ||
| 272 | (PRISM_INDEX_MAX_DIM + 1) * sizeof(float)) < | ||
| 273 | PRISM_POSTING_ENTRY_SIZE(PRISM_INDEX_MAX_DIM + 1), | ||
| 274 | "the ceiling is tight: one dimension more must not fit"); | ||
| 275 | |||
| 276 | /* Usable space on a BLCKSZ page (between content start and opaque) */ | ||
| 277 | static inline uint32_t | ||
| 278 | 9300 | prism_posting_page_usable(void) | |
| 279 | { | ||
| 280 | 9300 | return BLCKSZ - (uint32_t)MAXALIGN(SizeOfPageHeaderData) - | |
| 281 | sizeof(PrismPostingPageOpaque); | ||
| 282 | } | ||
| 283 | |||
| 284 | /* Space occupied by P^T * centroid on first pages (MAXALIGN'd) */ | ||
| 285 | static inline uint32_t | ||
| 286 | 282595 | prism_posting_pt_centroid_size(Dimension dim) | |
| 287 | { | ||
| 288 | 282595 | return (uint32_t)MAXALIGN(dim * sizeof(float)); | |
| 289 | } | ||
| 290 | |||
| 291 | /* Max entries on an overflow page (no pt_centroid) */ | ||
| 292 | static inline uint32_t | ||
| 293 | 40506 | prism_posting_max_entries(Dimension dim) | |
| 294 | { | ||
| 295 | 40255 | return prism_posting_page_usable() / PRISM_POSTING_ENTRY_SIZE(dim); | |
| 296 | } | ||
| 297 | |||
| 298 | /* Max entries on a first page (with pt_centroid) */ | ||
| 299 | static inline uint32_t | ||
| 300 | 14488 | prism_posting_max_entries_first(Dimension dim) | |
| 301 | { | ||
| 302 | 14488 | uint32_t usable = prism_posting_page_usable(); | |
| 303 | 14488 | uint32_t pt = prism_posting_pt_centroid_size(dim); | |
| 304 | |||
| 305 | /* Past PRISM_INDEX_MAX_DIM the reference alone overruns the page, and an | ||
| 306 | * unsigned subtraction would report a capacity of millions -- which the | ||
| 307 | * count checks use as their bound. */ | ||
| 308 |
2/2✓ Branch 0 taken 13028 times.
✓ Branch 1 taken 1460 times.
|
14488 | if (pt >= usable) |
| 309 | 334 | return 0; | |
| 310 | |||
| 311 | 14154 | return (usable - pt) / PRISM_POSTING_ENTRY_SIZE(dim); | |
| 312 | } | ||
| 313 | |||
| 314 | /* Buffer size for a flat page with count entries */ | ||
| 315 | static inline size_t | ||
| 316 | 168 | prism_posting_flat_page_size(Dimension dim, uint32_t count) | |
| 317 | { | ||
| 318 | 336 | return sizeof(PrismFlatPostingHeader) + | |
| 319 | 168 | (size_t)count * PRISM_POSTING_ENTRY_SIZE(dim); | |
| 320 | } | ||
| 321 | |||
| 322 | /* ---------------------------------------------------------------- | ||
| 323 | * Paged-mode access — opaque via PG PageGetSpecialPointer | ||
| 324 | * ---------------------------------------------------------------- */ | ||
| 325 | |||
| 326 | static inline PrismPostingPageOpaque * | ||
| 327 | 1375865 | prism_posting_opaque(Page page) | |
| 328 | { | ||
| 329 |
13/14✓ Branch 1 taken 412 times.
✓ Branch 2 taken 8963 times.
✓ Branch 3 taken 85 times.
✓ Branch 4 taken 12518 times.
✓ Branch 5 taken 8509 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1651 times.
✓ Branch 8 taken 9 times.
✓ Branch 9 taken 17419 times.
✓ Branch 11 taken 17323 times.
✓ Branch 12 taken 96 times.
✓ Branch 13 taken 10993 times.
✓ Branch 15 taken 99 times.
✓ Branch 16 taken 25 times.
|
1173187 | return (PrismPostingPageOpaque *)PageGetSpecialPointer(page); |
| 330 | } | ||
| 331 | |||
| 332 | /* | ||
| 333 | * Is this page a posting page at all (not a wrong-kind page, and not one | ||
| 334 | * only extended but never initialized)? Guard on the special-area size | ||
| 335 | * before reading the opaque, so a page of another kind is never misread | ||
| 336 | * through the posting layout. MAXALIGN, not a bare sizeof: PageGetSpecialSize | ||
| 337 | * reports the on-disk (MAXALIGN'd) special-area size PageInit reserved, and a | ||
| 338 | * struct whose size isn't already a multiple of MAXIMUM_ALIGNOF would | ||
| 339 | * otherwise silently stop matching the moment a field is added. | ||
| 340 | */ | ||
| 341 | static inline bool | ||
| 342 | 5371 | prism_page_is_posting(Page page) | |
| 343 | { | ||
| 344 |
2/3✓ Branch 0 taken 4555 times.
✓ Branch 1 taken 816 times.
✗ Branch 2 not taken.
|
6177 | return !PageIsNew(page) && |
| 345 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4549 times.
|
5361 | PageGetSpecialSize(page) == |
| 346 |
2/2✓ Branch 0 taken 5361 times.
✓ Branch 1 taken 10 times.
|
6177 | MAXALIGN(sizeof(PrismPostingPageOpaque)) && |
| 347 |
1/3✗ Branch 0 not taken.
✓ Branch 1 taken 5355 times.
✗ Branch 2 not taken.
|
5355 | prism_posting_opaque(page)->page_id == PRISM_POSTING_PAGE_ID; |
| 348 | } | ||
| 349 | |||
| 350 | static inline uint32_t | ||
| 351 | 528 | prism_posting_page_count(Page page) | |
| 352 | { | ||
| 353 | 528 | return prism_posting_opaque(page)->entry_count; | |
| 354 | } | ||
| 355 | |||
| 356 | static inline bool | ||
| 357 | 521543 | prism_posting_page_has_room(Page page) | |
| 358 | { | ||
| 359 | 521543 | PrismPostingPageOpaque *op = prism_posting_opaque(page); | |
| 360 | 521543 | return op->entry_count < op->max_entries; | |
| 361 | } | ||
| 362 | |||
| 363 | /* | ||
| 364 | * Per-cluster head metadata (read from the FIRST page). tail_blkno == | ||
| 365 | * InvalidBlockNumber means it has not been computed yet — see | ||
| 366 | * prism_posting_insert_one, which fills it lazily on the first insert. | ||
| 367 | */ | ||
| 368 | static inline uint32_t | ||
| 369 | 627 | prism_posting_head_live_count(Page head) | |
| 370 | { | ||
| 371 | 627 | return prism_posting_opaque(head)->live_count; | |
| 372 | } | ||
| 373 | |||
| 374 | static inline BlockNumber | ||
| 375 | 198 | prism_posting_head_tail(Page head) | |
| 376 | { | ||
| 377 | 198 | return prism_posting_opaque(head)->tail_blkno; | |
| 378 | } | ||
| 379 | |||
| 380 | /* ---------------------------------------------------------------- | ||
| 381 | * Content-based AoS access — header-agnostic | ||
| 382 | * | ||
| 383 | * Entries are laid out contiguously: entry i starts at | ||
| 384 | * content + i * PRISM_POSTING_ENTRY_SIZE(dim) | ||
| 385 | * and consists of an PrismPostingEntryHeader followed by | ||
| 386 | * VS_RABITQ_BYTES(dim) bytes of bits. The SIMD kernel strides | ||
| 387 | * through bits[] at stride = PRISM_POSTING_ENTRY_SIZE(dim), starting | ||
| 388 | * from prism_posting_first_bits(content). | ||
| 389 | * ---------------------------------------------------------------- */ | ||
| 390 | |||
| 391 | /* Header for entry i (access fields via the struct: hdr->meta, | ||
| 392 | * hdr->f_add, hdr->f_rescale, hdr->f_error). */ | ||
| 393 | static inline PrismPostingEntryHeader * | ||
| 394 | 6134482 | prism_posting_entry_at(char *content, uint32_t i, Dimension dim) | |
| 395 | { | ||
| 396 | 11990644 | return (PrismPostingEntryHeader *)(content + | |
| 397 | 6134482 | (size_t)i * | |
| 398 |
4/4✓ Branch 0 taken 67479 times.
✓ Branch 1 taken 67894 times.
✓ Branch 2 taken 73423 times.
✓ Branch 3 taken 8020 times.
|
6134482 | PRISM_POSTING_ENTRY_SIZE(dim)); |
| 399 | } | ||
| 400 | |||
| 401 | /* Bits pointer for entry i (immediately follows entry i's header). */ | ||
| 402 | static inline uint8_t * | ||
| 403 | 2 | prism_posting_entry_bits_at( | |
| 404 | char *content, uint32_t max_entries, Dimension dim, uint32_t i) | ||
| 405 | { | ||
| 406 | (void)max_entries; | ||
| 407 | 2 | return prism_posting_entry_at(content, i, dim)->bits; | |
| 408 | } | ||
| 409 | |||
| 410 | /* Pointer to entry 0's bits — the base the SIMD kernel uses, with | ||
| 411 | * stride = PRISM_POSTING_ENTRY_SIZE(dim). */ | ||
| 412 | static inline uint8_t * | ||
| 413 | 28471 | prism_posting_first_bits(char *content) | |
| 414 | { | ||
| 415 | 28471 | return ((PrismPostingEntryHeader *)content)->bits; | |
| 416 | } | ||
| 417 | |||
| 418 | /* ---------------------------------------------------------------- | ||
| 419 | * Paged-mode convenience wrappers | ||
| 420 | * | ||
| 421 | * These use PageGetContents for the content pointer and read | ||
| 422 | * max_entries from the opaque. Used by page init/add and tests. | ||
| 423 | * ---------------------------------------------------------------- */ | ||
| 424 | |||
| 425 | static inline char * | ||
| 426 | 93203 | prism_posting_content(Page page) | |
| 427 | { | ||
| 428 | 93203 | return PageGetContents(page); | |
| 429 | } | ||
| 430 | |||
| 431 | /* | ||
| 432 | * On first pages, P^T * centroid is stored right after PageHeader, | ||
| 433 | * before the SoA content. Content starts after pt_centroid area. | ||
| 434 | */ | ||
| 435 | static inline const float * | ||
| 436 | 13378607 | prism_posting_pt_centroid(Page page) | |
| 437 | { | ||
| 438 | 13396026 | return (const float *)PageGetContents(page); | |
| 439 | } | ||
| 440 | |||
| 441 | static inline float * | ||
| 442 | 12008 | prism_posting_pt_centroid_mut(Page page) | |
| 443 | { | ||
| 444 | 12008 | return (float *)PageGetContents(page); | |
| 445 | } | ||
| 446 | |||
| 447 | static inline char * | ||
| 448 | 236846 | prism_posting_content_first(Page page, Dimension dim) | |
| 449 | { | ||
| 450 | 236846 | return PageGetContents(page) + prism_posting_pt_centroid_size(dim); | |
| 451 | } | ||
| 452 | |||
| 453 | /* ---------------------------------------------------------------- | ||
| 454 | * Chain walks | ||
| 455 | * | ||
| 456 | * A posting list is a chain of pages linked by next_blkno. Every caller | ||
| 457 | * that traverses one has to read the link before releasing the page and | ||
| 458 | * release it before moving on; these keep that order in one place. | ||
| 459 | * | ||
| 460 | * The scan path deliberately does not use them. It holds a page across the | ||
| 461 | * SIMD kernels that consume it, interleaves the next page's prefetch, and | ||
| 462 | * handles flat mode (a single page, no chain) and page_base mode (memory it | ||
| 463 | * does not release) -- so its stepping is a different shape, not a | ||
| 464 | * duplicate of this one. | ||
| 465 | * ---------------------------------------------------------------- */ | ||
| 466 | |||
| 467 | /* | ||
| 468 | * Where a read walk currently is. The callback may release the page early | ||
| 469 | * and keep working: the next block is already read, so the walk does not | ||
| 470 | * need it afterwards. That matters for work which must not hold a page -- | ||
| 471 | * fetching heap tuples through the same storage, which holds one page at a | ||
| 472 | * time and would take over the slot. | ||
| 473 | */ | ||
| 474 | typedef struct PrismPostingChainPos | ||
| 475 | { | ||
| 476 | VsStorage *storage; | ||
| 477 | BlockNumber blkno; | ||
| 478 | Page page; /* NULL once released */ | ||
| 479 | BlockNumber next; /* read before the callback runs */ | ||
| 480 | bool first; | ||
| 481 | } PrismPostingChainPos; | ||
| 482 | |||
| 483 | static inline void | ||
| 484 | 5226 | prism_posting_chain_release(PrismPostingChainPos *pos) | |
| 485 | { | ||
| 486 |
2/2✓ Branch 0 taken 4418 times.
✓ Branch 1 taken 808 times.
|
5226 | if (pos->page != NULL) |
| 487 | { | ||
| 488 | 4418 | vs_storage_release_page(pos->storage, pos->blkno); | |
| 489 | 4418 | pos->page = NULL; | |
| 490 | } | ||
| 491 | 5226 | } | |
| 492 | |||
| 493 | /* Return false to stop the walk. */ | ||
| 494 | typedef bool (*PrismPostingChainCb)(PrismPostingChainPos *pos, void *state); | ||
| 495 | |||
| 496 | void prism_posting_chain_walk( | ||
| 497 | VsStorage *storage, | ||
| 498 | BlockNumber head, | ||
| 499 | PrismPostingChainCb cb, | ||
| 500 | void *state); | ||
| 501 | |||
| 502 | /* | ||
| 503 | * Mutating walk: the callback gets the opaque of a page held for write, and | ||
| 504 | * every page is committed. For chain-wide flag changes, where the body is a | ||
| 505 | * line or two and the walk is all of the code. | ||
| 506 | */ | ||
| 507 | typedef void (*PrismPostingChainMutateCb)( | ||
| 508 | PrismPostingPageOpaque *op, void *state); | ||
| 509 | |||
| 510 | void prism_posting_chain_mutate( | ||
| 511 | VsStorage *storage, | ||
| 512 | BlockNumber head, | ||
| 513 | PrismPostingChainMutateCb cb, | ||
| 514 | void *state); | ||
| 515 | |||
| 516 | /* | ||
| 517 | * Content of any posting page, first or not. | ||
| 518 | * | ||
| 519 | * A first page carries pt_centroid ahead of its entries, so the offset | ||
| 520 | * differs; every caller that walks a chain meets both kinds and was | ||
| 521 | * repeating this test. Inline, so the scan pays nothing for it. | ||
| 522 | */ | ||
| 523 | static inline char * | ||
| 524 | 282304 | prism_posting_page_content(Page page, Dimension dim) | |
| 525 | { | ||
| 526 | 282304 | return (prism_posting_opaque(page)->flags & PRISM_POSTING_PAGE_FIRST) | |
| 527 | 192104 | ? prism_posting_content_first(page, dim) | |
| 528 |
2/2✓ Branch 0 taken 192104 times.
✓ Branch 1 taken 90200 times.
|
414062 | : prism_posting_content(page); |
| 529 | } | ||
| 530 | |||
| 531 | /* Paged-mode convenience wrappers — these assume non-first pages | ||
| 532 | * (content starts right after PageHeader). For first pages with | ||
| 533 | * pt_centroid, go through prism_posting_content_first. */ | ||
| 534 | static inline PrismPostingEntryHeader * | ||
| 535 | 2 | prism_posting_entry(Page page, uint32_t i, Dimension dim) | |
| 536 | { | ||
| 537 | 2 | return prism_posting_entry_at(PageGetContents(page), i, dim); | |
| 538 | } | ||
| 539 | |||
| 540 | static inline uint8_t * | ||
| 541 | 2 | prism_posting_entry_bits( | |
| 542 | Page page, uint32_t max_entries, Dimension dim, uint32_t i) | ||
| 543 | { | ||
| 544 | 2 | return prism_posting_entry_bits_at( | |
| 545 | PageGetContents(page), max_entries, dim, i); | ||
| 546 | } | ||
| 547 | |||
| 548 | /* ---------------------------------------------------------------- | ||
| 549 | * Flat-mode access | ||
| 550 | * ---------------------------------------------------------------- */ | ||
| 551 | |||
| 552 | static inline PrismFlatPostingHeader * | ||
| 553 | 11388 | prism_flat_posting_header(char *buf) | |
| 554 | { | ||
| 555 | 11388 | return (PrismFlatPostingHeader *)buf; | |
| 556 | } | ||
| 557 | |||
| 558 | static inline char * | ||
| 559 | 11220 | prism_flat_posting_content(char *buf) | |
| 560 | { | ||
| 561 |
0/2✗ Branch 0 not taken.
✗ Branch 1 not taken.
|
11220 | return buf + sizeof(PrismFlatPostingHeader); |
| 562 | } | ||
| 563 | |||
| 564 | /* ---------------------------------------------------------------- | ||
| 565 | * Standalone helper: pack/extract vector_id in ItemPointerData | ||
| 566 | * ---------------------------------------------------------------- */ | ||
| 567 | |||
| 568 | static inline void | ||
| 569 | 12442 | prism_posting_set_vector_id(ItemPointerData *tid, uint32_t vector_id) | |
| 570 | { | ||
| 571 | 12442 | ItemPointerSet(tid, (BlockNumber)vector_id, 0); | |
| 572 | 12442 | } | |
| 573 | |||
| 574 | static inline uint32_t | ||
| 575 | 158140 | prism_posting_get_vector_id(const ItemPointerData *tid) | |
| 576 | { | ||
| 577 | 158140 | return (uint32_t)ItemPointerGetBlockNumber(tid); | |
| 578 | } | ||
| 579 | |||
| 580 | /* ---------------------------------------------------------------- | ||
| 581 | * TID ↔ uint64_t encoding for VsTopK | ||
| 582 | * | ||
| 583 | * Both standalone and PG store TIDs in VsTopK's uint64_t id field. | ||
| 584 | * For standalone: vector_id is packed in BlockNumber with offset=0, | ||
| 585 | * so encode yields (vector_id << 16) and decode_vector_id shifts | ||
| 586 | * back. For PG: full ItemPointerData (block + offset) fits in 48 | ||
| 587 | * bits of the uint64_t. | ||
| 588 | * ---------------------------------------------------------------- */ | ||
| 589 | |||
| 590 | static inline uint64_t | ||
| 591 | 606729 | prism_posting_encode_tid(const ItemPointerData *tid) | |
| 592 | { | ||
| 593 | 606729 | return ((uint64_t)ItemPointerGetBlockNumber(tid) << 16) | | |
| 594 | 606729 | (uint64_t)ItemPointerGetOffsetNumber(tid); | |
| 595 | } | ||
| 596 | |||
| 597 | static inline ItemPointerData | ||
| 598 | 31671 | prism_posting_decode_tid(uint64_t id) | |
| 599 | { | ||
| 600 | 31671 | ItemPointerData tid; | |
| 601 | 31671 | ItemPointerSet(&tid, (BlockNumber)(id >> 16), (OffsetNumber)(id & 0xFFFF)); | |
| 602 | 31671 | return tid; | |
| 603 | } | ||
| 604 | |||
| 605 | /* Convenience for standalone: extract vector_id from encoded TID. | ||
| 606 | * Works because prism_posting_set_vector_id stores vid in BlockNumber | ||
| 607 | * with offset=0, so (id >> 16) == vid. */ | ||
| 608 | static inline uint32_t | ||
| 609 | 82088 | prism_posting_decode_vector_id(uint64_t id) | |
| 610 | { | ||
| 611 | 82088 | return (uint32_t)(id >> 16); | |
| 612 | } | ||
| 613 | |||
| 614 | /* ---------------------------------------------------------------- | ||
| 615 | * Paged-mode page operations | ||
| 616 | * ---------------------------------------------------------------- */ | ||
| 617 | |||
| 618 | /* | ||
| 619 | * Initialize an empty BLCKSZ posting page. | ||
| 620 | */ | ||
| 621 | void prism_posting_page_init( | ||
| 622 | Page page, uint32_t cluster_id, Dimension dim, uint16_t flags); | ||
| 623 | |||
| 624 | /* | ||
| 625 | * Add one entry to a BLCKSZ page. Returns false if page is full. | ||
| 626 | */ | ||
| 627 | bool prism_posting_page_add( | ||
| 628 | Page page, | ||
| 629 | Dimension dim, | ||
| 630 | ItemPointerData tid, | ||
| 631 | float f_add, | ||
| 632 | float f_rescale, | ||
| 633 | float f_error, | ||
| 634 | const uint8_t *bits, | ||
| 635 | uint8_t entry_flags); | ||
| 636 | |||
| 637 | /* ---------------------------------------------------------------- | ||
| 638 | * Flat-mode page operations | ||
| 639 | * ---------------------------------------------------------------- */ | ||
| 640 | |||
| 641 | /* | ||
| 642 | * Initialize a flat posting page buffer. buf must be at least | ||
| 643 | * prism_posting_flat_page_size(dim, max_entries) bytes. | ||
| 644 | */ | ||
| 645 | void | ||
| 646 | prism_posting_flat_init(char *buf, uint32_t max_entries, uint32_t cluster_id); | ||
| 647 | |||
| 648 | /* | ||
| 649 | * Add one entry to a flat page. Returns false if full. | ||
| 650 | */ | ||
| 651 | bool prism_posting_flat_add( | ||
| 652 | char *buf, | ||
| 653 | Dimension dim, | ||
| 654 | ItemPointerData tid, | ||
| 655 | float f_add, | ||
| 656 | float f_rescale, | ||
| 657 | float f_error, | ||
| 658 | const uint8_t *bits, | ||
| 659 | uint8_t entry_flags); | ||
| 660 | |||
| 661 | /* ---------------------------------------------------------------- | ||
| 662 | * Fastscan page format | ||
| 663 | * | ||
| 664 | * SoA layout organized into 32-vector group sections. | ||
| 665 | * Each group section: | ||
| 666 | * ItemPointerData tids[32] 192B | ||
| 667 | * float f_add[32] 128B | ||
| 668 | * float f_rescale[32] 128B | ||
| 669 | * float f_error[32] 128B | ||
| 670 | * uint8_t codes[nsq_pairs × 32] variable (3072B at dim=768) | ||
| 671 | * uint32_t tombstone_mask 4B (bit v set => lane v is dead) | ||
| 672 | * | ||
| 673 | * tombstone_mask is the per-lane analog of an AoS entry's | ||
| 674 | * PRISM_POSTING_FLAG_DELETED (see fastscan-design.md for why the codes | ||
| 675 | * themselves can't be marked in place). A page starts with every mask word | ||
| 676 | * zero (PageInit zeroes the page; a fresh group's tail is never written | ||
| 677 | * otherwise), so an unmarked lane reads as live. | ||
| 678 | * | ||
| 679 | * Pages are identified by PRISM_POSTING_PAGE_FASTSCAN in opaque flags. | ||
| 680 | * ---------------------------------------------------------------- */ | ||
| 681 | |||
| 682 | #include "quant/fastscan.h" | ||
| 683 | |||
| 684 | static_assert( | ||
| 685 | VS_FASTSCAN_GROUP == 32, | ||
| 686 | "tombstone_mask packs one bit per lane into a uint32_t"); | ||
| 687 | |||
| 688 | /* Bytes per 32-vector group section (metadata + packed codes + tombstone | ||
| 689 | * mask) */ | ||
| 690 | static inline uint32_t | ||
| 691 | 119264 | prism_fastscan_group_section_bytes(Dimension dim) | |
| 692 | { | ||
| 693 | 164142 | return (uint32_t)(VS_FASTSCAN_GROUP * sizeof(ItemPointerData) + | |
| 694 | VS_FASTSCAN_GROUP * 3 * sizeof(float) + | ||
| 695 | 119264 | VS_FASTSCAN_GROUP_BYTES(dim) + sizeof(uint32_t)); | |
| 696 | } | ||
| 697 | |||
| 698 | /* Max entries on a fastscan overflow page */ | ||
| 699 | static inline uint32_t | ||
| 700 | 2179 | prism_fastscan_max_entries(Dimension dim) | |
| 701 | { | ||
| 702 | 2179 | uint32_t section = prism_fastscan_group_section_bytes(dim); | |
| 703 | 2179 | uint32_t usable = prism_posting_page_usable(); | |
| 704 | 2179 | uint32_t ngroups = usable / section; | |
| 705 | 2179 | return ngroups * VS_FASTSCAN_GROUP; | |
| 706 | } | ||
| 707 | |||
| 708 | /* Max entries on a fastscan first page (with pt_centroid) */ | ||
| 709 | static inline uint32_t | ||
| 710 | 12346 | prism_fastscan_max_entries_first(Dimension dim) | |
| 711 | { | ||
| 712 | 12346 | uint32_t section = prism_fastscan_group_section_bytes(dim); | |
| 713 | 12346 | uint32_t usable = prism_posting_page_usable(); | |
| 714 | 12346 | uint32_t pt = prism_posting_pt_centroid_size(dim); | |
| 715 | |||
| 716 |
2/2✓ Branch 0 taken 11334 times.
✓ Branch 1 taken 1012 times.
|
12346 | if (pt >= usable) |
| 717 | 334 | return 0; /* see prism_posting_max_entries_first */ | |
| 718 | |||
| 719 | 12012 | uint32_t ngroups = (usable - pt) / section; | |
| 720 | 12012 | return ngroups * VS_FASTSCAN_GROUP; | |
| 721 | } | ||
| 722 | |||
| 723 | /* | ||
| 724 | * Upper bound on the entries a single posting page can hold, whatever format | ||
| 725 | * it is in. Neither format's figure bounds the other: fastscan packs more | ||
| 726 | * than AoS at low dimension (416 vs 339 at dim 4) and fewer at high (64 vs 67 | ||
| 727 | * at dim 768, and none at all once a group stops fitting). The overflow-page | ||
| 728 | * figures bound a first page too, since that gives up room to the encode | ||
| 729 | * reference. Callers sizing a buffer for one page's worth of entries want | ||
| 730 | * this rather than either half. | ||
| 731 | */ | ||
| 732 | static inline uint32_t | ||
| 733 | 672 | prism_posting_max_entries_any_format(Dimension dim) | |
| 734 | { | ||
| 735 | 672 | uint32_t aos = prism_posting_max_entries(dim); | |
| 736 | 672 | uint32_t fs = prism_fastscan_max_entries(dim); | |
| 737 | 672 | return aos > fs ? aos : fs; | |
| 738 | } | ||
| 739 | |||
| 740 | /* | ||
| 741 | * The entry ceiling a page of this format and position really has. All four | ||
| 742 | * combinations differ: a fastscan page packs more entries than an AoS one, | ||
| 743 | * and a first page gives up room to the encode reference. Bounding an AoS | ||
| 744 | * page by the fastscan figure (or by the larger of the two) would still let | ||
| 745 | * prism_posting_entry_at walk off the page. | ||
| 746 | */ | ||
| 747 | static inline uint32_t | ||
| 748 | 4604 | prism_posting_page_cap(const PrismPostingPageOpaque *op, Dimension dim) | |
| 749 | { | ||
| 750 | 4604 | bool first = (op->flags & PRISM_POSTING_PAGE_FIRST) != 0; | |
| 751 | |||
| 752 |
2/2✓ Branch 0 taken 1897 times.
✓ Branch 1 taken 2707 times.
|
4604 | if (op->flags & PRISM_POSTING_PAGE_FASTSCAN) |
| 753 | 1828 | return first ? prism_fastscan_max_entries_first(dim) | |
| 754 |
2/2✓ Branch 0 taken 1828 times.
✓ Branch 1 taken 69 times.
|
1919 | : prism_fastscan_max_entries(dim); |
| 755 | |||
| 756 | 2136 | return first ? prism_posting_max_entries_first(dim) | |
| 757 |
2/2✓ Branch 0 taken 2136 times.
✓ Branch 1 taken 571 times.
|
2801 | : prism_posting_max_entries(dim); |
| 758 | } | ||
| 759 | |||
| 760 | /* | ||
| 761 | * Reject an on-disk entry_count past that ceiling before it drives a loop, so | ||
| 762 | * a corrupt or truncated page cannot read past the page end. The bound the | ||
| 763 | * scan path already applies (posting_scan.c), in the form the shared read | ||
| 764 | * paths need. | ||
| 765 | */ | ||
| 766 | void prism_posting_check_count( | ||
| 767 | BlockNumber blkno, const PrismPostingPageOpaque *op, Dimension dim); | ||
| 768 | |||
| 769 | /* Max groups on a page */ | ||
| 770 | static inline uint32_t | ||
| 771 | 34900 | prism_fastscan_max_groups(Dimension dim, bool is_first) | |
| 772 | { | ||
| 773 | 34900 | uint32_t section = prism_fastscan_group_section_bytes(dim); | |
| 774 | 34900 | uint32_t usable = prism_posting_page_usable(); | |
| 775 |
2/2✓ Branch 0 taken 154 times.
✓ Branch 1 taken 237 times.
|
34900 | if (is_first) |
| 776 | 18915 | usable -= prism_posting_pt_centroid_size(dim); | |
| 777 |
3/3✓ Branch 0 taken 10 times.
✓ Branch 1 taken 161 times.
✓ Branch 2 taken 24 times.
|
9559 | return usable / section; |
| 778 | } | ||
| 779 | |||
| 780 | /* ---------------------------------------------------------------- | ||
| 781 | * Fastscan group accessors | ||
| 782 | * | ||
| 783 | * All take content pointer (past PageHeader, past pt_centroid on | ||
| 784 | * first pages) and group index g. | ||
| 785 | * ---------------------------------------------------------------- */ | ||
| 786 | |||
| 787 | static inline char * | ||
| 788 | 73311 | prism_fastscan_group_base(char *content, uint32_t g, Dimension dim) | |
| 789 | { | ||
| 790 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 9045 times.
|
85318 | return content + (size_t)g * prism_fastscan_group_section_bytes(dim); |
| 791 | } | ||
| 792 | |||
| 793 | static inline ItemPointerData * | ||
| 794 | 18093 | prism_fastscan_group_tids(char *content, uint32_t g, Dimension dim) | |
| 795 | { | ||
| 796 | 18307 | return (ItemPointerData *)prism_fastscan_group_base(content, g, dim); | |
| 797 | } | ||
| 798 | |||
| 799 | static inline float * | ||
| 800 | 43358 | prism_fastscan_group_f_add(char *content, uint32_t g, Dimension dim) | |
| 801 | { | ||
| 802 | 44070 | return (float *)(prism_fastscan_group_base(content, g, dim) + | |
| 803 | VS_FASTSCAN_GROUP * sizeof(ItemPointerData)); | ||
| 804 | } | ||
| 805 | |||
| 806 | static inline float * | ||
| 807 | 42175 | prism_fastscan_group_f_rescale(char *content, uint32_t g, Dimension dim) | |
| 808 | { | ||
| 809 | 42887 | return prism_fastscan_group_f_add(content, g, dim) + VS_FASTSCAN_GROUP; | |
| 810 | } | ||
| 811 | |||
| 812 | static inline float * | ||
| 813 | 40992 | prism_fastscan_group_f_error(char *content, uint32_t g, Dimension dim) | |
| 814 | { | ||
| 815 | 41704 | return prism_fastscan_group_f_rescale(content, g, dim) + VS_FASTSCAN_GROUP; | |
| 816 | } | ||
| 817 | |||
| 818 | static inline uint8_t * | ||
| 819 | 39809 | prism_fastscan_group_codes(char *content, uint32_t g, Dimension dim) | |
| 820 | { | ||
| 821 | 40521 | return (uint8_t *)(prism_fastscan_group_f_error(content, g, dim) + | |
| 822 | VS_FASTSCAN_GROUP); | ||
| 823 | } | ||
| 824 | |||
| 825 | /* | ||
| 826 | * Per-group dead-lane bitmap: bit v set means lane v's TID is dead. Read and | ||
| 827 | * write through this pointer directly (it aliases the live page); there is no | ||
| 828 | * copy to write back. Only valid lanes (v < the group's entry count) are ever | ||
| 829 | * set -- PageInit zeroes a fresh page and nothing else touches this word, so | ||
| 830 | * an unmarked lane, including every lane past entry_count on a partial final | ||
| 831 | * group, reads as live. | ||
| 832 | */ | ||
| 833 | static inline uint32_t * | ||
| 834 | 4037 | prism_fastscan_group_tombstone_mask(char *content, uint32_t g, Dimension dim) | |
| 835 | { | ||
| 836 | 4037 | return (uint32_t *)(prism_fastscan_group_codes(content, g, dim) + | |
| 837 | 4037 | VS_FASTSCAN_GROUP_BYTES(dim)); | |
| 838 | } | ||
| 839 | |||
| 840 | /* | ||
| 841 | * Bit test and set for one lane of a tombstone_mask word already read out | ||
| 842 | * of (or about to be written back into) a page via the accessor above. | ||
| 843 | * Every reader and writer of the mask goes through these two rather than | ||
| 844 | * writing out the bit math itself, so there is exactly one place that | ||
| 845 | * says "lane v is bit 1u << v". | ||
| 846 | */ | ||
| 847 | static inline bool | ||
| 848 | 134497 | prism_fastscan_lane_is_tombstoned(uint32_t mask, uint32_t lane) | |
| 849 | { | ||
| 850 |
4/4✓ Branch 0 taken 2011 times.
✓ Branch 1 taken 89063 times.
✓ Branch 2 taken 20 times.
✓ Branch 3 taken 2533 times.
|
134497 | return (mask & (1u << lane)) != 0; |
| 851 | } | ||
| 852 | |||
| 853 | static inline uint32_t | ||
| 854 | 832 | prism_fastscan_lane_set_tombstone(uint32_t mask, uint32_t lane) | |
| 855 | { | ||
| 856 | 832 | return mask | (1u << lane); | |
| 857 | } | ||
| 858 | |||
| 859 | #endif /* PRISM_POSTING_PAGE_H */ | ||
| 860 |