25341664142

Committed 04 May 2026 08:25PM UTC coverage: 62.595% (+1.2%) from 61.422%

Build # 25341664142

Build Type

push

github

Committed by

web-flow

Commit Message

feat(storage): free-list + VACUUM to reclaim orphan pages (SQLR-6) (#89)

DROP TABLE / DROP INDEX / ALTER TABLE DROP COLUMN now route the dropped
object's pages onto a persisted free-page list (header bytes [28..32],
chained `FreelistTrunk` pages, format version v6 on demand). Subsequent
saves draw from the freelist before extending the file, so unrelated
tables keep their page numbers across drops and the diff pager skips
their byte-identical re-stages. `VACUUM;` (new SQL statement) compacts
the file by ignoring the freelist and allocating contiguously from
page 1, then double-checkpoints so the on-disk shrink is visible
immediately.

Co-authored-by: Claude Opus 4.7 (1M context) <noreply@anthropic.com>

Coverage Stats

488 of 526 new or added lines in 7 files covered. (92.78%)

2 existing lines in 2 files now uncovered.

7400 of 11822 relevant lines covered (62.6%)

1.2 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.59

/src/sql/pager/allocator.rs

//! Page allocator for `save_database` (SQLR-6).
//!
//! Replaces the bare `next_free_page: u32` counter that the staging code
//! used to thread through every `stage_*_btree` function. The allocator
//! draws from three pools, in order of preference:
//!
//! 1. **Per-table preferred pool** — pages the table previously occupied,
//!    seeded by [`set_preferred`]. An unchanged table's stage produces
//!    byte-identical pages at the same numbers, so the diff pager skips
//!    every write for it.
//! 2. **Global freelist** — pages dropped tables/indexes used to occupy
//!    plus the trunk pages of the previously-persisted freelist.
//! 3. **Extend** — `next_extend++`, monotonic past the current high water.
//!
//! After staging finishes, [`high_water`] is the new `page_count` and
//! [`used`] enumerates every page actually written this save (so the
//! caller can compute the new freelist as `old_live − used`).

use std::collections::{HashSet, VecDeque};

/// Hands out page numbers during a save.
///
/// Lifetime: one allocator per `save_database` call. Not thread-safe; not
/// shared across saves.
pub struct PageAllocator {
    /// Pages available globally. Drained after the per-table pool is empty.
    /// Stored as a VecDeque so callers can append (push_back) and we always
    /// hand them out front-first for ascending-order determinism.
    freelist: VecDeque<u32>,
    /// The current table's preferred pool (its previous-rootpage pages).
    /// Drained before [`freelist`]. Cleared between tables by
    /// [`finish_preferred`].
    preferred: VecDeque<u32>,
    /// Next page number for fresh extension. Page 0 is the header, so
    /// the first alloc always returns ≥ 1.
    next_extend: u32,
    /// Every page handed out this save. Used to compute the newly-freed
    /// set after staging completes.
    used: HashSet<u32>,
}

impl PageAllocator {
    /// `freelist` carries the pages from the previously-persisted
    /// freelist (sorted ascending by the caller). `next_extend` is
    /// typically `1` for a brand-new save.
    pub fn new(freelist: VecDeque<u32>, next_extend: u32) -> Self {
        let mut alloc = Self {
            freelist,
            preferred: VecDeque::new(),
            next_extend,
            used: HashSet::new(),
        };
        // Defensive: a corrupt freelist could push the high-water mark
        // higher than `next_extend` claims. Bump so we never hand out a
        // duplicate page on extend.
        let max_free = alloc.freelist.iter().copied().max().unwrap_or(0);
        if max_free + 1 > alloc.next_extend {
            alloc.next_extend = max_free + 1;
        }
        alloc
    }

    /// Seeds the per-table preferred pool. Drained on subsequent
    /// [`allocate`] calls before any other source.
    pub fn set_preferred(&mut self, mut pool: Vec<u32>) {
        // Sort ascending so the order matches the linear staging order
        // and unchanged tables get byte-identical leaves.
        pool.sort_unstable();
        pool.dedup();
        // Filter out anything the allocator has already handed out
        // (defensive — shouldn't happen but keeps the invariant tidy).
        pool.retain(|p| !self.used.contains(p));
        self.preferred = VecDeque::from(pool);
    }

    /// Empties the per-table preferred pool, returning any leftover
    /// pages to the global freelist (they're now free again).
    pub fn finish_preferred(&mut self) {
        while let Some(p) = self.preferred.pop_front() {
            if !self.used.contains(&p) {
                self.freelist.push_back(p);
            }
        }
    }

    /// Returns the next page to write. Picks from preferred → freelist →
    /// extend. Records the result in `used` and bumps `next_extend` if
    /// the page came from one of the pools and was past the current
    /// high water.
    pub fn allocate(&mut self) -> u32 {
        let page = if let Some(p) = self.preferred.pop_front() {
            p
        } else if let Some(p) = self.freelist.pop_front() {
            p
        } else {
            let p = self.next_extend;
            self.next_extend += 1;
            p
        };
        if page >= self.next_extend {
            self.next_extend = page + 1;
        }
        // A double-allocation is an internal bug; assert in debug.
        debug_assert!(
            !self.used.contains(&page),
            "PageAllocator handed out page {page} twice"
        );
        self.used.insert(page);
        page
    }

    /// Adds pages to the global freelist. Used to drop pages that the
    /// caller traversed but didn't end up restaging (e.g., a dropped
    /// table's leaves; the previous freelist's trunk pages).
    ///
    /// Bumps `next_extend` past any added page so the final page_count
    /// covers freelist trunks even if they live past the highest used
    /// payload page.
    pub fn add_to_freelist(&mut self, pages: impl IntoIterator<Item = u32>) {
        for p in pages {
            // Skip pages already used (we already restaged them) or
            // already on the list.
            if !self.used.contains(&p) && !self.freelist.contains(&p) {
                self.freelist.push_back(p);
                if p + 1 > self.next_extend {
                    self.next_extend = p + 1;
                }
            }
        }
    }

    /// Page-count to publish in the new header. Equal to
    /// `1 + max page handed out` after staging.
    pub fn high_water(&self) -> u32 {
        self.next_extend
    }

    /// Every page handed out this save.
    pub fn used(&self) -> &HashSet<u32> {
        &self.used
    }

    /// Snapshot of pages still on the global freelist (i.e., free pages
    /// that need to be persisted into trunk pages). Sorted ascending so
    /// the encoded freelist trunks are deterministic.
    pub fn drain_freelist(&mut self) -> Vec<u32> {
        let mut v: Vec<u32> = self.freelist.drain(..).collect();
        v.sort_unstable();
        v.dedup();
        v
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn allocate_extends_when_pools_empty() {
        let mut a = PageAllocator::new(VecDeque::new(), 1);
        assert_eq!(a.allocate(), 1);
        assert_eq!(a.allocate(), 2);
        assert_eq!(a.allocate(), 3);
        assert_eq!(a.high_water(), 4);
    }

    #[test]
    fn preferred_pool_drains_first() {
        let mut a = PageAllocator::new(VecDeque::from([8, 9]), 1);
        a.set_preferred(vec![3, 4]);
        assert_eq!(a.allocate(), 3);
        assert_eq!(a.allocate(), 4);
        // After preferred drains, freelist takes over.
        assert_eq!(a.allocate(), 8);
        assert_eq!(a.allocate(), 9);
        // Then extend.
        assert_eq!(a.allocate(), 10);
    }

    #[test]
    fn freelist_drains_after_preferred() {
        let mut a = PageAllocator::new(VecDeque::from([5, 7]), 1);
        assert_eq!(a.allocate(), 5);
        assert_eq!(a.allocate(), 7);
        assert_eq!(a.allocate(), 8); // extend bumped because max free was 7
    }

    #[test]
    fn finish_preferred_returns_leftovers_to_freelist() {
        let mut a = PageAllocator::new(VecDeque::new(), 1);
        a.set_preferred(vec![3, 4, 5]);
        assert_eq!(a.allocate(), 3); // used 3
        a.finish_preferred();
        // Now 4 and 5 should be on the freelist.
        assert_eq!(a.allocate(), 4);
        assert_eq!(a.allocate(), 5);
    }

    #[test]
    fn add_to_freelist_skips_already_used() {
        let mut a = PageAllocator::new(VecDeque::new(), 1);
        let p = a.allocate(); // 1
        a.add_to_freelist([p, 5, 6]);
        let drained = a.drain_freelist();
        assert!(
            !drained.contains(&p),
            "used page should not land on freelist"
        );
        assert_eq!(drained, vec![5, 6]);
    }

    #[test]
    fn next_extend_respects_max_free() {
        // High pages on the freelist should bump next_extend so the
        // allocator never collides with them on extend.
        let mut a = PageAllocator::new(VecDeque::from([100]), 1);
        // First alloc draws from freelist.
        assert_eq!(a.allocate(), 100);
        // Subsequent extend lands at 101, not 1.
        assert_eq!(a.allocate(), 101);
    }
}

1	//! Page allocator for `save_database` (SQLR-6).
2	//!
3	//! Replaces the bare `next_free_page: u32` counter that the staging code
4	//! used to thread through every `stage_*_btree` function. The allocator
5	//! draws from three pools, in order of preference:
6	//!
7	//! 1. Per-table preferred pool — pages the table previously occupied,
8	//! seeded by [`set_preferred`]. An unchanged table's stage produces
9	//! byte-identical pages at the same numbers, so the diff pager skips
10	//! every write for it.
11	//! 2. Global freelist — pages dropped tables/indexes used to occupy
12	//! plus the trunk pages of the previously-persisted freelist.
13	//! 3. Extend — `next_extend++`, monotonic past the current high water.
14	//!
15	//! After staging finishes, [`high_water`] is the new `page_count` and
16	//! [`used`] enumerates every page actually written this save (so the
17	//! caller can compute the new freelist as `old_live − used`).
18
19	use std::collections::{HashSet, VecDeque};
20
21	/// Hands out page numbers during a save.
22	///
23	/// Lifetime: one allocator per `save_database` call. Not thread-safe; not
24	/// shared across saves.
25	pub struct PageAllocator {
26	/// Pages available globally. Drained after the per-table pool is empty.
27	/// Stored as a VecDeque so callers can append (push_back) and we always
28	/// hand them out front-first for ascending-order determinism.
29	freelist: VecDeque<u32>,
30	/// The current table's preferred pool (its previous-rootpage pages).
31	/// Drained before [`freelist`]. Cleared between tables by
32	/// [`finish_preferred`].
33	preferred: VecDeque<u32>,
34	/// Next page number for fresh extension. Page 0 is the header, so
35	/// the first alloc always returns ≥ 1.
36	next_extend: u32,
37	/// Every page handed out this save. Used to compute the newly-freed
38	/// set after staging completes.
39	used: HashSet<u32>,
40	}
41
42	impl PageAllocator {
43	/// `freelist` carries the pages from the previously-persisted
44	/// freelist (sorted ascending by the caller). `next_extend` is
45	/// typically `1` for a brand-new save.
46	pub fn new(freelist: VecDeque<u32>, next_extend: u32) -> Self {	2✔
47	let mut alloc = Self {
48	freelist,
49	preferred: VecDeque::new(),	2✔
50	next_extend,
51	used: HashSet::new(),	2✔
52	};
53	// Defensive: a corrupt freelist could push the high-water mark
54	// higher than `next_extend` claims. Bump so we never hand out a
55	// duplicate page on extend.
56	let max_free = alloc.freelist.iter().copied().max().unwrap_or(0);	4✔
57	if max_free + 1 > alloc.next_extend {	3✔
58	alloc.next_extend = max_free + 1;	1✔
59	}
60	alloc	2✔
61	}
62
63	/// Seeds the per-table preferred pool. Drained on subsequent
64	/// [`allocate`] calls before any other source.
65	pub fn set_preferred(&mut self, mut pool: Vec<u32>) {	2✔
66	// Sort ascending so the order matches the linear staging order
67	// and unchanged tables get byte-identical leaves.
68	pool.sort_unstable();	4✔
69	pool.dedup();	2✔
70	// Filter out anything the allocator has already handed out
71	// (defensive — shouldn't happen but keeps the invariant tidy).
72	pool.retain(\|p\| !self.used.contains(p));	6✔
73	self.preferred = VecDeque::from(pool);	2✔
74	}
75
76	/// Empties the per-table preferred pool, returning any leftover
77	/// pages to the global freelist (they're now free again).
78	pub fn finish_preferred(&mut self) {	2✔
79	while let Some(p) = self.preferred.pop_front() {	2✔
80	if !self.used.contains(&p) {	1✔
81	self.freelist.push_back(p);	1✔
82	}
83	}
84	}
85
86	/// Returns the next page to write. Picks from preferred → freelist →
87	/// extend. Records the result in `used` and bumps `next_extend` if
88	/// the page came from one of the pools and was past the current
89	/// high water.
90	pub fn allocate(&mut self) -> u32 {	2✔
91	let page = if let Some(p) = self.preferred.pop_front() {	4✔
92	p	2✔
93	} else if let Some(p) = self.freelist.pop_front() {	6✔
94	p	1✔
95	} else {
96	let p = self.next_extend;	2✔
97	self.next_extend += 1;	2✔
98	p	2✔
99	};
100	if page >= self.next_extend {	4✔
101	self.next_extend = page + 1;	2✔
102	}
103	// A double-allocation is an internal bug; assert in debug.
NEW 104	debug_assert!(	×
105	!self.used.contains(&page),	2✔
106	"PageAllocator handed out page {page} twice"
107	);
108	self.used.insert(page);	2✔
109	page	2✔
110	}
111
112	/// Adds pages to the global freelist. Used to drop pages that the
113	/// caller traversed but didn't end up restaging (e.g., a dropped
114	/// table's leaves; the previous freelist's trunk pages).
115	///
116	/// Bumps `next_extend` past any added page so the final page_count
117	/// covers freelist trunks even if they live past the highest used
118	/// payload page.
119	pub fn add_to_freelist(&mut self, pages: impl IntoIterator<Item = u32>) {	3✔
120	for p in pages {	6✔
121	// Skip pages already used (we already restaged them) or
122	// already on the list.
123	if !self.used.contains(&p) && !self.freelist.contains(&p) {	4✔
124	self.freelist.push_back(p);	2✔
125	if p + 1 > self.next_extend {	3✔
126	self.next_extend = p + 1;	1✔
127	}
128	}
129	}
130	}
131
132	/// Page-count to publish in the new header. Equal to
133	/// `1 + max page handed out` after staging.
134	pub fn high_water(&self) -> u32 {	2✔
135	self.next_extend	2✔
136	}
137
138	/// Every page handed out this save.
139	pub fn used(&self) -> &HashSet<u32> {	2✔
140	&self.used	2✔
141	}
142
143	/// Snapshot of pages still on the global freelist (i.e., free pages
144	/// that need to be persisted into trunk pages). Sorted ascending so
145	/// the encoded freelist trunks are deterministic.
146	pub fn drain_freelist(&mut self) -> Vec<u32> {	2✔
147	let mut v: Vec<u32> = self.freelist.drain(..).collect();	2✔
148	v.sort_unstable();	4✔
149	v.dedup();	2✔
150	v	2✔
151	}
152	}
153
154	#[cfg(test)]
155	mod tests {
156	use super::*;
157
158	#[test]
159	fn allocate_extends_when_pools_empty() {	3✔
160	let mut a = PageAllocator::new(VecDeque::new(), 1);	1✔
161	assert_eq!(a.allocate(), 1);	2✔
162	assert_eq!(a.allocate(), 2);	1✔
163	assert_eq!(a.allocate(), 3);	1✔
164	assert_eq!(a.high_water(), 4);	1✔
165	}
166
167	#[test]
168	fn preferred_pool_drains_first() {	3✔
169	let mut a = PageAllocator::new(VecDeque::from([8, 9]), 1);	1✔
170	a.set_preferred(vec![3, 4]);	2✔
171	assert_eq!(a.allocate(), 3);	1✔
172	assert_eq!(a.allocate(), 4);	1✔
173	// After preferred drains, freelist takes over.
174	assert_eq!(a.allocate(), 8);	1✔
175	assert_eq!(a.allocate(), 9);	1✔
176	// Then extend.
177	assert_eq!(a.allocate(), 10);	1✔
178	}
179
180	#[test]
181	fn freelist_drains_after_preferred() {	3✔
182	let mut a = PageAllocator::new(VecDeque::from([5, 7]), 1);	1✔
183	assert_eq!(a.allocate(), 5);	2✔
184	assert_eq!(a.allocate(), 7);	1✔
185	assert_eq!(a.allocate(), 8); // extend bumped because max free was 7	1✔
186	}
187
188	#[test]
189	fn finish_preferred_returns_leftovers_to_freelist() {	3✔
190	let mut a = PageAllocator::new(VecDeque::new(), 1);	1✔
191	a.set_preferred(vec![3, 4, 5]);	2✔
192	assert_eq!(a.allocate(), 3); // used 3	1✔
193	a.finish_preferred();	1✔
194	// Now 4 and 5 should be on the freelist.
195	assert_eq!(a.allocate(), 4);	1✔
196	assert_eq!(a.allocate(), 5);	1✔
197	}
198
199	#[test]
200	fn add_to_freelist_skips_already_used() {	3✔
201	let mut a = PageAllocator::new(VecDeque::new(), 1);	1✔
202	let p = a.allocate(); // 1	2✔
203	a.add_to_freelist([p, 5, 6]);	1✔
204	let drained = a.drain_freelist();	1✔
NEW 205	assert!(	×
206	!drained.contains(&p),	2✔
207	"used page should not land on freelist"
208	);
209	assert_eq!(drained, vec![5, 6]);	2✔
210	}
211
212	#[test]
213	fn next_extend_respects_max_free() {	3✔
214	// High pages on the freelist should bump next_extend so the
215	// allocator never collides with them on extend.
216	let mut a = PageAllocator::new(VecDeque::from([100]), 1);	1✔
217	// First alloc draws from freelist.
218	assert_eq!(a.allocate(), 100);	2✔
219	// Subsequent extend lands at 101, not 1.
220	assert_eq!(a.allocate(), 101);	1✔
221	}
222	}

joaoh82 / rust_sqlite / 25341664142

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous