bonsai/storage/
page.rs

1//! See [bufpage.h](https://github.com/postgres/postgres/blob/master/src/include/storage/bufpage.h)
2//! and [bufpage.c](https://github.com/postgres/postgres/blob/master/src/backend/storage/page/bufpage.c).
3//!
4//! # Page layout
5//! ```text
6//! +--------+---------------+----------------+--------------+---------+
7//! | header | line pointers |→  free space  ←| tuple data   | special |
8//! +--------+---------------+----------------+--------------+---------+
9//! 0        24          pd_lower         pd_upper     pd_special    8192
10//! ```
11//!
12//! Fields are little-endian. Postgres uses the machine's byte order, which is
13//! little-endian on x86-64 and ARM64, so there the bytes match Postgres's.
14
15use std::{
16    borrow::Cow,
17    fmt,
18    ops::{Deref, DerefMut, Range},
19};
20
21use {
22    super::{BLCKSZ, BlockNumber, checksum::checksum_page},
23    crate::{TransactionId, XLogRecPtr},
24};
25
26/// An 8 KB block, exactly as stored on disk.
27#[derive(Clone, Debug, PartialEq, Eq)]
28pub struct Page {
29    pub bytes: [u8; BLCKSZ],
30}
31
32impl Deref for Page {
33    type Target = [u8];
34
35    fn deref(&self) -> &Self::Target {
36        &self.bytes
37    }
38}
39
40impl DerefMut for Page {
41    fn deref_mut(&mut self) -> &mut Self::Target {
42        &mut self.bytes
43    }
44}
45
46pub struct ValidatedPage<'a> {
47    page: Cow<'a, Page>,
48    block: BlockNumber,
49}
50
51impl ValidatedPage<'_> {
52    pub fn page(&self) -> &Page {
53        &self.page
54    }
55
56    /// The block the page's checksum was computed for.
57    pub fn block(&self) -> BlockNumber {
58        self.block
59    }
60}
61
62pub const HEADER_SIZE: usize = 24;
63
64/// Version of this layout, kept in the low byte of `pd_pagesize_version`.
65/// Postgres's `PG_PAGE_LAYOUT_VERSION`, which has been 4 since Postgres 8.3.
66pub const PAGE_LAYOUT_VERSION: u16 = 4;
67
68/// Where `pd_checksum` sits in the page.
69pub(crate) const PD_CHECKSUM: Range<usize> = 8..10;
70
71/// Postgres's `MAXIMUM_ALIGNOF`: This is the maximum alignment a basic C type may require.
72const MAXIMUM_ALIGNOF: usize = 8;
73
74/// Offset of a byte within a page. Postgres's `LocationIndex`.
75#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
76pub struct LocationIndex(pub u16);
77
78impl From<LocationIndex> for usize {
79    fn from(location: LocationIndex) -> Self {
80        usize::from(location.0)
81    }
82}
83
84#[derive(Clone, Copy, Debug, PartialEq, Eq)]
85pub struct Header {
86    /// Log Sequence Number: Position in the WAL just past the last record that changed the page,
87    /// or `None` (stored as 0) if no record has, as on a page fresh from [`Page::init`].
88    /// See [WAL Internals](https://www.postgresql.org/docs/current/wal-internals.html).
89    pub lsn: Option<XLogRecPtr>,
90    pub checksum: u16,
91    pub flags: PageFlags,
92    /// Offset of the start of free space, just past the last line pointer.
93    pub lower: LocationIndex,
94    /// Offset of the end of free space, where tuple data begins.
95    pub upper: LocationIndex,
96    /// Offset of the start of the special space, which the access method reserves.
97    /// See [Database Page Layout](https://www.postgresql.org/docs/current/storage-page-layout.html).
98    pub special: LocationIndex,
99    /// Page size in the high bits, layout version in the low byte.
100    pub pagesize_version: u16,
101    /// Oldest transaction whose deletions on this page could be pruned, or `None` (stored as 0)
102    /// if there are none. Postgres only treats it as a hint, and leaves it unused on index pages.
103    /// See [Heap-Only Tuples (HOT)](https://www.postgresql.org/docs/current/storage-hot.html),
104    /// and chapter 5, "Page Pruning and HOT Updates", of *PostgreSQL 14 Internals* by Egor Rogov.
105    pub prune_xid: Option<TransactionId>,
106}
107
108impl Page {
109    /// The page's header, parsed and checked by [`Header::try_from_raw`].
110    pub fn header(&self) -> Result<Header, InvalidHeader> {
111        Header::try_from_raw(self.header_raw())
112    }
113
114    /// The bytes of the page's header.
115    pub fn header_raw(&self) -> &[u8; HEADER_SIZE] {
116        self.bytes.first_chunk().unwrap()
117    }
118
119    /// Turns self into an empty page with at least `special_size` bytes of special space
120    /// at the end. Postgres's `PageInit`.
121    pub fn init(page: &mut Page, special_size: usize) {
122        let special_size = special_size.next_multiple_of(MAXIMUM_ALIGNOF);
123        assert!(
124            HEADER_SIZE + special_size <= BLCKSZ,
125            "special space too large"
126        );
127        let special = LocationIndex((BLCKSZ - special_size) as u16);
128        page.fill(0);
129        page.set_header(Header {
130            lsn: None,
131            checksum: 0,
132            flags: PageFlags::default(),
133            lower: LocationIndex(HEADER_SIZE as u16),
134            upper: special,
135            special,
136            pagesize_version: BLCKSZ as u16 | PAGE_LAYOUT_VERSION,
137            prune_xid: None,
138        });
139    }
140
141    pub fn is_uninitialized(&self) -> bool {
142        // `pd_upper`, read on its own: the rest of the header may not parse.
143        read_u16(self, 14) == 0
144    }
145
146    pub fn set_header(&mut self, header: Header) {
147        let lsn = header.lsn.map_or(0, u64::from);
148        write_u32(self, 0, (lsn >> 32) as u32);
149        write_u32(self, 4, lsn as u32);
150        write_u16(self, 8, header.checksum);
151        write_u16(self, 10, header.flags.into());
152        write_u16(self, 12, header.lower.0);
153        write_u16(self, 14, header.upper.0);
154        write_u16(self, 16, header.special.0);
155        write_u16(self, 18, header.pagesize_version);
156        write_u32(self, 20, header.prune_xid.map_or(0, u32::from));
157    }
158
159    /// Set the checksum for self at `block`, and locks self into a validated state.
160    pub fn try_set_checksum_for_block(
161        mut self,
162        block: BlockNumber,
163    ) -> Result<ValidatedPage<'static>, PageError> {
164        if self.is_uninitialized() {
165            return if self.iter().all(|&byte| byte == 0) {
166                Ok(ValidatedPage {
167                    page: Cow::Owned(self),
168                    block,
169                })
170            } else {
171                Err(PageError::InvalidHeader { block })
172            };
173        }
174
175        if self.header().is_err() {
176            return Err(PageError::InvalidHeader { block });
177        }
178
179        let checksum = checksum_page(&self, block);
180        self[PD_CHECKSUM].copy_from_slice(&checksum.to_le_bytes());
181        Ok(ValidatedPage {
182            page: Cow::Owned(self),
183            block,
184        })
185    }
186
187    /// Try to validate self for `block`. Returns an error if the checksum doesn't match or the
188    /// header is invalid.
189    pub fn try_validated_for_block<'a>(
190        &'a self,
191        block: BlockNumber,
192    ) -> Result<ValidatedPage<'a>, PageError> {
193        if self.is_uninitialized() {
194            return if self.iter().all(|&byte| byte == 0) {
195                Ok(ValidatedPage {
196                    page: Cow::Borrowed(self),
197                    block,
198                })
199            } else {
200                Err(PageError::InvalidHeader { block })
201            };
202        }
203        // Read on its own, so that a checksum mismatch is reported even when
204        // `header()` rejects the header.
205        let stored = read_u16(self, PD_CHECKSUM.start);
206        let computed = checksum_page(self, block);
207        if stored != computed {
208            return Err(PageError::ChecksumMismatch {
209                block,
210                stored,
211                computed,
212            });
213        }
214        if self.header().is_err() {
215            return Err(PageError::InvalidHeader { block });
216        }
217        Ok(ValidatedPage {
218            page: Cow::Borrowed(self),
219            block,
220        })
221    }
222}
223
224impl Header {
225    /// Parses a header, with the checks Postgres runs before letting a page
226    /// into the buffer pool. They don't prove the header right, only plausible.
227    pub fn try_from_raw(raw: &[u8; HEADER_SIZE]) -> Result<Self, InvalidHeader> {
228        // Postgres stores the LSN as two 32-bit halves, high half first.
229        let lsn = (u64::from(read_u32(raw, 0)) << 32) | u64::from(read_u32(raw, 4));
230        let header = Header {
231            lsn: XLogRecPtr::from_raw(lsn),
232            checksum: read_u16(raw, 8),
233            flags: PageFlags::try_from(read_u16(raw, 10))?,
234            lower: LocationIndex(read_u16(raw, 12)),
235            upper: LocationIndex(read_u16(raw, 14)),
236            special: LocationIndex(read_u16(raw, 16)),
237            pagesize_version: read_u16(raw, 18),
238            prune_xid: TransactionId::from_raw(read_u32(raw, 20)),
239        };
240        let Header {
241            lower,
242            upper,
243            special,
244            ..
245        } = header;
246        if !(lower <= upper
247            && upper <= special
248            && usize::from(special) <= BLCKSZ
249            && usize::from(special) % MAXIMUM_ALIGNOF == 0)
250        {
251            return Err(InvalidHeader::Offsets {
252                lower,
253                upper,
254                special,
255            });
256        }
257        Ok(header)
258    }
259}
260
261/// Why a header fails the checks Postgres runs before letting a page into the
262/// buffer pool.
263#[derive(Clone, Copy, Debug, PartialEq, Eq)]
264pub enum InvalidHeader {
265    /// `pd_flags` has a bit set that Postgres doesn't define.
266    Flags(u16),
267    /// `pd_lower`, `pd_upper` and `pd_special` are out of order or off the
268    /// page, or `pd_special` isn't aligned.
269    Offsets {
270        lower: LocationIndex,
271        upper: LocationIndex,
272        special: LocationIndex,
273    },
274}
275
276impl fmt::Display for InvalidHeader {
277    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
278        match self {
279            InvalidHeader::Flags(bits) => write!(f, "invalid page flags {bits:#06x}"),
280            InvalidHeader::Offsets {
281                lower,
282                upper,
283                special,
284            } => write!(
285                f,
286                "invalid page offsets: lower {}, upper {}, special {}",
287                lower.0, upper.0, special.0
288            ),
289        }
290    }
291}
292
293impl std::error::Error for InvalidHeader {}
294
295#[derive(Clone, Copy, Debug, PartialEq, Eq)]
296pub enum PageError {
297    ChecksumMismatch {
298        block: BlockNumber,
299        stored: u16,
300        computed: u16,
301    },
302    InvalidHeader {
303        block: BlockNumber,
304    },
305}
306
307impl fmt::Display for PageError {
308    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
309        match self {
310            PageError::ChecksumMismatch {
311                block,
312                stored,
313                computed,
314            } => write!(
315                f,
316                "page verification failed in block {block}: \
317                 calculated checksum {computed} but expected {stored}"
318            ),
319            PageError::InvalidHeader { block } => write!(f, "invalid page header in block {block}"),
320        }
321    }
322}
323
324impl std::error::Error for PageError {}
325
326/// The bits of `pd_flags`.
327#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
328pub struct PageFlags {
329    /// Some line pointers before `pd_lower` are unused and can be reused. A
330    /// hint: changes to it aren't WAL-logged. Postgres's `PD_HAS_FREE_LINES`.
331    pub has_free_lines: bool,
332    /// An UPDATE found no room on the page for its new row version, so pruning
333    /// the page may help. A hint too. Postgres's `PD_PAGE_FULL`.
334    pub page_full: bool,
335    /// Every row on the page is visible to every transaction, current and
336    /// future. Set by VACUUM, along with the page's bit in the visibility map.
337    /// Postgres's `PD_ALL_VISIBLE`.
338    pub all_visible: bool,
339}
340
341const PD_HAS_FREE_LINES: u16 = 0x0001;
342const PD_PAGE_FULL: u16 = 0x0002;
343const PD_ALL_VISIBLE: u16 = 0x0004;
344/// Every flag Postgres defines.
345const PD_VALID_FLAG_BITS: u16 = PD_HAS_FREE_LINES | PD_PAGE_FULL | PD_ALL_VISIBLE;
346
347/// Fails if a bit Postgres doesn't define is set.
348impl TryFrom<u16> for PageFlags {
349    type Error = InvalidHeader;
350
351    fn try_from(bits: u16) -> Result<Self, Self::Error> {
352        if bits & !PD_VALID_FLAG_BITS != 0 {
353            return Err(InvalidHeader::Flags(bits));
354        }
355        Ok(PageFlags {
356            has_free_lines: bits & PD_HAS_FREE_LINES != 0,
357            page_full: bits & PD_PAGE_FULL != 0,
358            all_visible: bits & PD_ALL_VISIBLE != 0,
359        })
360    }
361}
362
363impl From<PageFlags> for u16 {
364    fn from(flags: PageFlags) -> Self {
365        let mut bits = 0;
366        if flags.has_free_lines {
367            bits |= PD_HAS_FREE_LINES;
368        }
369        if flags.page_full {
370            bits |= PD_PAGE_FULL;
371        }
372        if flags.all_visible {
373            bits |= PD_ALL_VISIBLE;
374        }
375        bits
376    }
377}
378
379fn read_u16(bytes: &[u8], offset: usize) -> u16 {
380    u16::from_le_bytes([bytes[offset], bytes[offset + 1]])
381}
382
383fn read_u32(bytes: &[u8], offset: usize) -> u32 {
384    u32::from_le_bytes(bytes[offset..offset + 4].try_into().unwrap())
385}
386
387fn write_u16(page: &mut Page, offset: usize, value: u16) {
388    page[offset..offset + 2].copy_from_slice(&value.to_le_bytes());
389}
390
391fn write_u32(page: &mut Page, offset: usize, value: u32) {
392    page[offset..offset + 4].copy_from_slice(&value.to_le_bytes());
393}
394
395#[cfg(test)]
396mod tests {
397    use super::*;
398
399    /// An initialized page with some arbitrary bytes in its free space.
400    fn sample_page() -> Page {
401        let mut page = Page { bytes: [0; BLCKSZ] };
402        Page::init(&mut page, 16);
403        for (i, byte) in page[HEADER_SIZE..BLCKSZ - 16].iter_mut().enumerate() {
404            *byte = (i * 31 % 251) as u8;
405        }
406        page
407    }
408
409    /// `page` with its checksum set for `block`.
410    fn sealed(page: Page, block: BlockNumber) -> Page {
411        let validated = page.try_set_checksum_for_block(block).unwrap();
412        validated.page().clone()
413    }
414
415    #[test]
416    fn init_matches_page_init() {
417        let mut page = Page {
418            bytes: [0xAB; BLCKSZ],
419        };
420        Page::init(&mut page, 12);
421        let header = page.header().unwrap();
422        assert_eq!(header.lower, LocationIndex(24));
423        assert_eq!(header.upper, LocationIndex(8192 - 16));
424        assert_eq!(header.special, LocationIndex(8192 - 16));
425        assert_eq!(header.pagesize_version, 8196);
426        assert_eq!(header.lsn, None);
427        assert_eq!(header.prune_xid, None);
428        assert!(page[HEADER_SIZE..].iter().all(|&byte| byte == 0));
429    }
430
431    #[test]
432    fn header_round_trips() {
433        let header = Header {
434            lsn: XLogRecPtr::from_raw(0x0000_0001_0A2B_3C4D),
435            checksum: 0x1234,
436            flags: PageFlags {
437                has_free_lines: true,
438                page_full: false,
439                all_visible: true,
440            },
441            lower: LocationIndex(40),
442            upper: LocationIndex(8000),
443            special: LocationIndex(8176),
444            pagesize_version: 8196,
445            prune_xid: TransactionId::from_raw(742),
446        };
447        let mut page = Page { bytes: [0; BLCKSZ] };
448        page.set_header(header);
449        assert_eq!(page.header(), Ok(header));
450        // High half of the LSN first, each half little-endian.
451        assert_eq!(page[..8], [0x01, 0, 0, 0, 0x4D, 0x3C, 0x2B, 0x0A]);
452    }
453
454    #[test]
455    fn all_zero_page_verifies() {
456        // `extend` adds pages of zeros, which have no checksum.
457        let page = Page { bytes: [0; BLCKSZ] };
458        assert!(page.try_validated_for_block(BlockNumber(7)).is_ok());
459    }
460
461    #[test]
462    fn set_checksum_leaves_a_new_page_all_zeros() {
463        // A checksum would make the page no longer all zeros while `upper`
464        // is still 0, and `verify` would reject it as an invalid header.
465        let page = sealed(Page { bytes: [0; BLCKSZ] }, BlockNumber(7));
466        assert_eq!(page.bytes, [0; BLCKSZ]);
467    }
468
469    #[test]
470    fn checksummed_page_verifies() {
471        let page = sealed(sample_page(), BlockNumber(3));
472        assert_ne!(page.header().unwrap().checksum, 0);
473        assert!(page.try_validated_for_block(BlockNumber(3)).is_ok());
474    }
475
476    #[test]
477    fn every_flipped_byte_is_caught() {
478        let page = sealed(sample_page(), BlockNumber(0));
479        for i in 0..BLCKSZ {
480            let mut corrupt = page.clone();
481            corrupt[i] ^= 0xFF;
482            assert!(
483                corrupt.try_validated_for_block(BlockNumber(0)).is_err(),
484                "flipping byte {i} went unnoticed"
485            );
486        }
487    }
488
489    #[test]
490    fn page_at_the_wrong_block_is_caught() {
491        let page = sealed(sample_page(), BlockNumber(5));
492        for block in (0..1000u32).filter(|&block| block != 5) {
493            assert!(matches!(
494                page.try_validated_for_block(BlockNumber(block)),
495                Err(PageError::ChecksumMismatch { .. })
496            ));
497        }
498    }
499
500    #[test]
501    fn insane_header_is_caught_even_with_a_good_checksum() {
502        let mut page = sample_page();
503        let mut header = page.header().unwrap();
504        header.lower = LocationIndex(header.upper.0 + 8);
505        page.set_header(header);
506        assert!(matches!(page.header(), Err(InvalidHeader::Offsets { .. })));
507        // Sealing refuses such a page, so write its checksum directly.
508        let checksum = checksum_page(&page, BlockNumber(0));
509        page[PD_CHECKSUM].copy_from_slice(&checksum.to_le_bytes());
510        assert!(matches!(
511            page.try_validated_for_block(BlockNumber(0)),
512            Err(PageError::InvalidHeader {
513                block: BlockNumber(0)
514            })
515        ));
516    }
517
518    #[test]
519    fn unknown_flag_is_caught_even_with_a_good_checksum() {
520        let mut page = sample_page();
521        // No `PageFlags` can hold this bit, so write `pd_flags` directly.
522        write_u16(&mut page, 10, 0x0008);
523        assert_eq!(page.header(), Err(InvalidHeader::Flags(0x0008)));
524        let checksum = checksum_page(&page, BlockNumber(0));
525        page[PD_CHECKSUM].copy_from_slice(&checksum.to_le_bytes());
526        assert!(matches!(
527            page.try_validated_for_block(BlockNumber(0)),
528            Err(PageError::InvalidHeader {
529                block: BlockNumber(0)
530            })
531        ));
532    }
533
534    #[test]
535    fn sealing_an_insane_header_fails() {
536        let mut page = sample_page();
537        let mut header = page.header().unwrap();
538        header.lower = LocationIndex(header.upper.0 + 8);
539        page.set_header(header);
540        assert_eq!(
541            page.try_set_checksum_for_block(BlockNumber(0)).err(),
542            Some(PageError::InvalidHeader {
543                block: BlockNumber(0)
544            })
545        );
546    }
547
548    #[test]
549    fn zero_upper_with_data_is_not_a_new_page() {
550        let mut page = Page { bytes: [0; BLCKSZ] };
551        page[100] = 1;
552        assert!(matches!(
553            page.try_validated_for_block(BlockNumber(0)),
554            Err(PageError::InvalidHeader {
555                block: BlockNumber(0)
556            })
557        ));
558    }
559}
bonsai/storage/page.rs

bonsai/storage/
page.rs
