wasm_dbms_memory/
unclaimed_pages.rs

1// Rust guideline compliant 2026-04-27
2// X-WHERE-CLAUSE, M-CANONICAL-DOCS
3
4//! Unclaimed-pages ledger persisted on the reserved page
5//! [`crate::memory_manager::UNCLAIMED_PAGES_PAGE`].
6//!
7//! Tracks pages that have been released by destructive operations (e.g.
8//! `MigrationOp::DropTable`) so that they can be reused by future
9//! [`MemoryAccess::claim_page`](crate::MemoryAccess::claim_page) calls
10//! before bumping the high-water mark via the underlying provider.
11
12use std::borrow::Cow;
13
14use wasm_dbms_api::prelude::{
15    DEFAULT_ALIGNMENT, DataSize, DecodeError, Encode, MSize, MemoryError, MemoryResult, Page,
16    PageOffset,
17};
18
19/// Bytes of the on-page header (`u32` length prefix).
20const HEADER_SIZE: u64 = 4;
21/// Bytes of one page entry (`u32`).
22const ENTRY_SIZE: u64 = 4;
23
24/// Maximum number of entries that fit in the reserved page (64 KiB).
25///
26/// Computed at build time so that the encoded ledger size stays within
27/// [`MSize`] (`u16`). Currently 16382 entries.
28pub const UNCLAIMED_PAGES_CAPACITY: u32 = {
29    let max_bytes = MSize::MAX as u64;
30    let entries = (max_bytes - HEADER_SIZE) / ENTRY_SIZE;
31    entries as u32
32};
33
34/// On-disk representation of the unclaimed-pages ledger.
35///
36/// The ledger is a LIFO stack of [`Page`] numbers. Push appends, pop
37/// removes from the tail.
38#[derive(Debug, Clone, Default, PartialEq, Eq)]
39pub struct UnclaimedPages {
40    pages: Vec<Page>,
41}
42
43impl UnclaimedPages {
44    /// Returns an empty ledger.
45    pub fn new() -> Self {
46        Self::default()
47    }
48
49    /// Returns the number of pages currently in the ledger.
50    pub fn len(&self) -> usize {
51        self.pages.len()
52    }
53
54    /// Returns how many additional pages can still be tracked.
55    pub fn remaining_capacity(&self) -> u32 {
56        UNCLAIMED_PAGES_CAPACITY - (self.pages.len() as u32)
57    }
58
59    /// Returns `true` when no pages are currently tracked.
60    pub fn is_empty(&self) -> bool {
61        self.pages.is_empty()
62    }
63
64    /// Removes and returns the last unclaimed page, if any.
65    pub fn pop(&mut self) -> Option<Page> {
66        self.pages.pop()
67    }
68
69    /// Appends `page` to the ledger.
70    ///
71    /// # Errors
72    ///
73    /// [`MemoryError::UnclaimedPagesFull`] when the ledger is at capacity.
74    pub fn push(&mut self, page: Page) -> MemoryResult<()> {
75        if self.pages.len() as u32 >= UNCLAIMED_PAGES_CAPACITY {
76            return Err(MemoryError::UnclaimedPagesFull {
77                capacity: UNCLAIMED_PAGES_CAPACITY,
78            });
79        }
80        self.pages.push(page);
81        Ok(())
82    }
83
84    /// Returns a slice over the tracked pages (oldest first).
85    pub fn as_slice(&self) -> &[Page] {
86        &self.pages
87    }
88}
89
90impl Encode for UnclaimedPages {
91    const SIZE: DataSize = DataSize::Dynamic;
92    const ALIGNMENT: PageOffset = DEFAULT_ALIGNMENT;
93
94    fn encode(&'_ self) -> Cow<'_, [u8]> {
95        let mut buf = Vec::with_capacity(self.size() as usize);
96        buf.extend_from_slice(&(self.pages.len() as u32).to_le_bytes());
97        for &page in &self.pages {
98            buf.extend_from_slice(&page.to_le_bytes());
99        }
100        Cow::Owned(buf)
101    }
102
103    fn decode(data: Cow<[u8]>) -> MemoryResult<Self>
104    where
105        Self: Sized,
106    {
107        if data.len() < HEADER_SIZE as usize {
108            return Err(MemoryError::DecodeError(DecodeError::TooShort));
109        }
110        let count = u32::from_le_bytes(data[0..4].try_into()?) as usize;
111        if count > UNCLAIMED_PAGES_CAPACITY as usize {
112            return Err(MemoryError::UnclaimedPagesFull {
113                capacity: UNCLAIMED_PAGES_CAPACITY,
114            });
115        }
116        // `count` is bounded by the capacity, so this cannot overflow.
117        let required = HEADER_SIZE as usize + count * ENTRY_SIZE as usize;
118        if data.len() < required {
119            return Err(MemoryError::DecodeError(DecodeError::TooShort));
120        }
121        let pages = data[HEADER_SIZE as usize..required]
122            .as_chunks::<{ ENTRY_SIZE as usize }>()
123            .0
124            .iter()
125            .map(|entry| Page::from_le_bytes(*entry))
126            .collect();
127        Ok(Self { pages })
128    }
129
130    fn size(&self) -> MSize {
131        (HEADER_SIZE as MSize) + (self.pages.len() as MSize) * (ENTRY_SIZE as MSize)
132    }
133}
134
135#[cfg(test)]
136mod tests {
137    use wasm_dbms_api::prelude::DecodeError;
138
139    use super::*;
140
141    #[test]
142    fn test_should_be_empty_by_default() {
143        let ledger = UnclaimedPages::new();
144        assert!(ledger.is_empty());
145        assert_eq!(ledger.len(), 0);
146    }
147
148    #[test]
149    fn test_should_push_and_pop() {
150        let mut ledger = UnclaimedPages::new();
151        ledger.push(10).expect("push");
152        ledger.push(20).expect("push");
153        ledger.push(30).expect("push");
154
155        assert_eq!(ledger.len(), 3);
156        assert_eq!(ledger.pop(), Some(30));
157        assert_eq!(ledger.pop(), Some(20));
158        assert_eq!(ledger.pop(), Some(10));
159        assert_eq!(ledger.pop(), None);
160    }
161
162    #[test]
163    fn test_should_round_trip_encode_decode() {
164        let mut ledger = UnclaimedPages::new();
165        for page in [3u32, 5, 7, 11] {
166            ledger.push(page).expect("push");
167        }
168
169        let encoded = ledger.encode();
170        let decoded = UnclaimedPages::decode(encoded).expect("decode");
171        assert_eq!(ledger, decoded);
172    }
173
174    #[test]
175    fn test_should_decode_empty_buffer_as_empty_ledger() {
176        let buf = vec![0u8; 65536];
177        let ledger = UnclaimedPages::decode(Cow::Owned(buf)).expect("decode");
178        assert!(ledger.is_empty());
179    }
180
181    #[test]
182    fn test_should_reject_truncated_buffers() {
183        // Header shorter than 4 bytes.
184        let short_header = UnclaimedPages::decode(Cow::Borrowed(&[1u8, 0][..]));
185        assert!(matches!(
186            short_header,
187            Err(MemoryError::DecodeError(DecodeError::TooShort))
188        ));
189
190        // Header declares one entry, but no entry bytes follow.
191        let missing_entry = UnclaimedPages::decode(Cow::Borrowed(&[1u8, 0, 0, 0][..]));
192        assert!(matches!(
193            missing_entry,
194            Err(MemoryError::DecodeError(DecodeError::TooShort))
195        ));
196    }
197
198    #[test]
199    fn test_should_reject_push_when_full() {
200        let mut ledger = UnclaimedPages {
201            pages: vec![0; UNCLAIMED_PAGES_CAPACITY as usize],
202        };
203        let err = ledger.push(42).expect_err("push at capacity");
204        assert!(matches!(err, MemoryError::UnclaimedPagesFull { .. }));
205    }
206
207    #[test]
208    fn test_size_matches_encoded_length() {
209        let mut ledger = UnclaimedPages::new();
210        ledger.push(1).expect("push");
211        ledger.push(2).expect("push");
212        let encoded = ledger.encode();
213        assert_eq!(ledger.size() as usize, encoded.len());
214    }
215}
wasm_dbms_memory/unclaimed_pages.rs

wasm_dbms_memory/
unclaimed_pages.rs
