Skip to main content

umadb_core/
mvcc.rs

1use crate::common::Position;
2use crate::common::{PageID, Tsn};
3use crate::db::{DB_SCHEMA_VERSION, clone_dcb_error};
4use crate::events_tree_nodes::EventLeafNode;
5use crate::free_lists_tree_nodes::{
6    FreeListInternalNode, FreeListLeafNode, FreeListLeafValue, FreeListTsnLeafNode,
7};
8use crate::header_node::HeaderNode;
9use crate::node::Node;
10use crate::page::{PAGE_HEADER_SIZE, Page, page_approx_deserialized_bytes, serialize_page_into};
11use crate::pager::{Pager, ReadMethod};
12use crate::tags_tree_nodes::TagsLeafNode;
13use crate::tags_tree_nodes::set_tag_key_width;
14use moka::sync::Cache;
15use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet};
16use std::collections::BTreeMap;
17use std::collections::VecDeque;
18use std::path::{Path, PathBuf};
19use std::sync::Arc;
20// use std::sync::atomic::{AtomicU64, Ordering};
21use arc_swap::ArcSwap;
22use parking_lot::Mutex;
23use std::collections::hash_map::Entry;
24use std::thread::sleep;
25use std::time::Duration;
26use umadb_dcb::DcbError::InternalError;
27use umadb_dcb::{DcbError, DcbResult};
28
29const GET_LATEST_HEADER_RETRIES: usize = 5;
30const GET_LATEST_HEADER_DELAY: Duration = Duration::from_millis(10);
31const HEADER_PAGE_ID_0: PageID = PageID(0);
32const HEADER_PAGE_ID_1: PageID = PageID(1);
33
34pub const DEFAULT_PAGE_SIZE: usize = 4096;
35pub const DEFAULT_DB_FILENAME: &str = "uma.db";
36
37#[derive(Debug, Clone)]
38pub struct StorageOptions {
39    pub db_path: PathBuf,
40    pub page_size: usize,
41    pub read_method: ReadMethod,
42    pub page_cache_max_pages: usize,
43    pub page_cache_max_mb: usize,
44    pub zero_fill_pages: bool,
45    pub pipelined_writer: bool,
46}
47
48impl Default for StorageOptions {
49    fn default() -> Self {
50        Self {
51            db_path: DEFAULT_DB_FILENAME.into(),
52            page_size: DEFAULT_PAGE_SIZE,
53            read_method: ReadMethod::default(),
54            page_cache_max_pages: 0,
55            page_cache_max_mb: 0,
56            zero_fill_pages: true,
57            pipelined_writer: false,
58        }
59    }
60}
61
62impl StorageOptions {
63    pub fn db_path<P: AsRef<Path>>(self, db_path: P) -> Self {
64        let p = db_path.as_ref();
65        let db_path = if p.is_dir() {
66            p.join(DEFAULT_DB_FILENAME)
67        } else {
68            p.to_path_buf()
69        };
70        Self { db_path, ..self }
71    }
72
73    pub fn page_size(self, page_size: usize) -> Self {
74        Self { page_size, ..self }
75    }
76
77    pub fn read_method(self, read_method: ReadMethod) -> Self {
78        Self {
79            read_method,
80            ..self
81        }
82    }
83
84    pub fn page_cache_max_pages(self, page_cache_max_pages: usize) -> Self {
85        Self {
86            page_cache_max_pages,
87            ..self
88        }
89    }
90
91    pub fn page_cache_max_mb(self, page_cache_max_mb: usize) -> Self {
92        Self {
93            page_cache_max_mb,
94            ..self
95        }
96    }
97
98    pub fn zero_fill_pages(self, zero_fill_pages: bool) -> Self {
99        Self {
100            zero_fill_pages,
101            ..self
102        }
103    }
104
105    pub fn pipelined_writer(self, pipelined_writer: bool) -> Self {
106        Self {
107            pipelined_writer,
108            ..self
109        }
110    }
111}
112
113/// Tracks the snapshot TSN held by every live reader, as a counting multiset keyed
114/// by TSN (value = number of live readers currently holding that TSN).
115///
116/// The writer needs the lowest live reader TSN to decide which freed pages are safe
117/// to reuse. Keys are removed the moment their count reaches zero, so the smallest
118/// present key is always exactly the lowest live reader TSN — obtained via
119/// `min()` in `O(log n)` (the leftmost key) instead of scanning every reader.
120///
121/// Readers commonly share a TSN (they register against the same latest snapshot
122/// between commits), so distinct keys are typically far fewer than live readers.
123#[derive(Debug, Default)]
124pub struct ReaderTsnRegistry {
125    counts: Mutex<BTreeMap<Tsn, usize>>,
126}
127
128impl ReaderTsnRegistry {
129    /// Publish a live reader holding snapshot `tsn` (called from `Mvcc::reader`).
130    pub fn register(&self, tsn: Tsn) {
131        let mut counts = self.counts.lock();
132        *counts.entry(tsn).or_insert(0) += 1;
133    }
134
135    /// Retire a live reader holding snapshot `tsn` (called from `Reader::drop`, and
136    /// to roll back a tentative registration in `reader`'s retry loop).
137    pub fn unregister(&self, tsn: Tsn) {
138        let mut counts = self.counts.lock();
139        if let Some(count) = counts.get_mut(&tsn) {
140            *count -= 1;
141            if *count == 0 {
142                counts.remove(&tsn);
143            }
144        }
145    }
146
147    /// The lowest TSN held by any live reader, or `None` if there are none.
148    pub fn min(&self) -> Option<Tsn> {
149        self.counts.lock().first_key_value().map(|(&tsn, _)| tsn)
150    }
151
152    /// Total number of live readers (sum of counts).
153    #[cfg(test)]
154    pub fn live_reader_count(&self) -> usize {
155        self.counts.lock().values().copied().sum()
156    }
157
158    /// Whether any live reader currently holds `tsn`.
159    #[cfg(test)]
160    pub fn contains_tsn(&self, tsn: Tsn) -> bool {
161        self.counts.lock().contains_key(&tsn)
162    }
163
164    /// Live reader TSNs in ascending order, each repeated by its count.
165    #[cfg(test)]
166    pub fn live_tsns_sorted(&self) -> Vec<Tsn> {
167        let counts = self.counts.lock();
168        let mut out = Vec::new();
169        for (&tsn, &count) in counts.iter() {
170            for _ in 0..count {
171                out.push(tsn);
172            }
173        }
174        out
175    }
176}
177
178pub struct PageRW {
179    pub pager: Pager,
180    read_method: ReadMethod,
181}
182
183impl PageRW {
184    pub fn read_page(&self, page_id: PageID) -> DcbResult<Arc<Page>> {
185        let page = match self.read_method {
186            ReadMethod::Mmap => {
187                let mapped = self.pager.read_page_mmap_slice(page_id)?;
188                Page::deserialize(page_id, mapped.as_slice())?
189            }
190            ReadMethod::FileIo => {
191                let page = self.pager.read_page_from_file(page_id)?;
192                Page::deserialize(page_id, &page)?
193            }
194        };
195        Ok(Arc::new(page))
196    }
197
198    pub fn write_page(
199        &self,
200        page_id: PageID,
201        page: &Page,
202        buf: &mut [u8],
203        zero_fill_pages: bool,
204    ) -> DcbResult<()> {
205        page.serialize_into(buf, zero_fill_pages)?;
206        self.pager.write_page_data(page_id, &buf)
207    }
208}
209
210pub trait MvccSnapshot {
211    fn read_page(&self, page_id: PageID) -> DcbResult<Arc<Page>>;
212}
213
214// Main MVCC structure
215pub struct Mvcc {
216    pub db_path: PathBuf,
217    pub rw: PageRW,
218    pub reader_tsns: Arc<ReaderTsnRegistry>,
219    pub page_size: usize,
220    pub max_node_size: usize,
221    page_buf: Mutex<Vec<u8>>,
222    pub verbose: bool,
223    pub zero_fill_pages: bool,
224    page_cache: Option<Cache<PageID, Arc<Page>, FxBuildHasher>>,
225    pinned_headers: [ArcSwap<Page>; 2],
226    // // Cache monitoring counters
227    // cache_hits: AtomicU64,
228    // cache_misses: AtomicU64,
229    // last_stats_print: AtomicU64, // Stores millis since process start
230    // start_time: Instant,
231}
232
233pub struct PreparedCommit {
234    pub header_to_write: (PageID, Vec<u8>),
235    pub pages_to_write: Vec<(PageID, Vec<u8>)>,
236}
237
238impl Mvcc {
239    pub fn new(verbose: bool, options: StorageOptions) -> DcbResult<Self> {
240        let pager = Pager::new(&options.db_path, options.page_size)?;
241        let rw = PageRW {
242            pager,
243            read_method: options.read_method,
244        };
245        println!(
246            "UmaDB opened file {}",
247            options.db_path.canonicalize()?.display()
248        );
249
250        println!(
251            "UmaDB reading with {}",
252            match options.read_method {
253                ReadMethod::Mmap => "memory map",
254                ReadMethod::FileIo => "file I/O",
255            }
256        );
257
258        println!(
259            "UmaDB zero-fill pages: {}",
260            if options.zero_fill_pages {
261                "true"
262            } else {
263                "false"
264            }
265        );
266
267        println!(
268            "UmaDB writing with {}",
269            if options.pipelined_writer {
270                "pipeline mode"
271            } else {
272                "synchronous mode"
273            }
274        );
275
276        let page_cache = if options.page_cache_max_mb > 0 {
277            println!("UmaDB page cache max MB: {}", options.page_cache_max_mb);
278            Some(
279                Cache::builder()
280                    .max_capacity(1000000 * options.page_cache_max_mb as u64)
281                    .weigher(|_page_id, page: &Arc<Page>| {
282                        page_approx_deserialized_bytes(page.as_ref()).min(u32::MAX as usize) as u32
283                    })
284                    .build_with_hasher(FxBuildHasher::default()),
285            )
286        } else if options.page_cache_max_pages > 0 {
287            println!(
288                "UmaDB page cache max pages: {}",
289                options.page_cache_max_pages
290            );
291            Some(
292                Cache::builder()
293                    .max_capacity(options.page_cache_max_pages as u64)
294                    .build_with_hasher(FxBuildHasher::default()),
295            )
296        } else {
297            println!("UmaDB page cache not enabled");
298            None
299        };
300
301        let reader_tsns = Arc::new(ReaderTsnRegistry::default());
302        let page_buf = Mutex::new(vec![0u8; options.page_size]);
303        let max_node_size = options.page_size - PAGE_HEADER_SIZE;
304
305        if rw.pager.is_file_new {
306            // Newly created DB uses 128-bit tag hashes.
307            set_tag_key_width(crate::tags_tree_nodes::TAG_HASH_LEN);
308
309            // Initialize new database
310            let initial_tsn = Tsn(0);
311            let initial_free_lists_tree_root_id = PageID(2);
312            let initial_events_tree_root_id = PageID(3);
313            let initial_tags_tree_root_id = PageID(4);
314            let initial_next_page_id = PageID(5);
315            let initial_next_position = Position(1);
316            // Write header 0.
317            let header0 = Arc::new(Page {
318                page_id: HEADER_PAGE_ID_0,
319                node: Node::Header(HeaderNode {
320                    tsn: initial_tsn,
321                    free_lists_tree_root_id: initial_free_lists_tree_root_id,
322                    events_tree_root_id: initial_events_tree_root_id,
323                    tags_tree_root_id: initial_tags_tree_root_id,
324                    next_page_id: initial_next_page_id,
325                    next_position: initial_next_position,
326                    schema_version: DB_SCHEMA_VERSION,
327                    tracking_tree_root_id: PageID(0),
328                }),
329            });
330            // Write header 1.
331            let header1 = Arc::new(Page {
332                page_id: HEADER_PAGE_ID_1,
333                node: Node::Header(HeaderNode {
334                    tsn: initial_tsn,
335                    free_lists_tree_root_id: initial_free_lists_tree_root_id,
336                    events_tree_root_id: initial_events_tree_root_id,
337                    tags_tree_root_id: initial_tags_tree_root_id,
338                    next_page_id: initial_next_page_id,
339                    next_position: initial_next_position,
340                    schema_version: DB_SCHEMA_VERSION,
341                    tracking_tree_root_id: PageID(0),
342                }),
343            });
344
345            let mvcc = Self {
346                db_path: options.db_path,
347                rw,
348                reader_tsns,
349                page_size: options.page_size,
350                max_node_size,
351                page_buf,
352                verbose,
353                zero_fill_pages: options.zero_fill_pages,
354                page_cache,
355                pinned_headers: [ArcSwap::new(header0.clone()), ArcSwap::new(header1.clone())],
356                // cache_hits: AtomicU64::new(0),
357                // cache_misses: AtomicU64::new(0),
358                // last_stats_print: AtomicU64::new(0),
359                // start_time: Instant::now(),
360            };
361
362            // Create and write an empty free lists tree root page.
363            let free_list_leaf = FreeListLeafNode {
364                keys: Vec::new(),
365                values: Vec::new(),
366            };
367            let free_list_page = Page::new(
368                initial_free_lists_tree_root_id,
369                Node::FreeListLeaf(free_list_leaf),
370            );
371
372            // Create and write an empty events tree root page.
373            let event_leaf = EventLeafNode {
374                keys: Vec::new(),
375                values: Vec::new(),
376            };
377            let position_page = Page::new(initial_events_tree_root_id, Node::EventLeaf(event_leaf));
378
379            // Create and write an empty tags tree root page.
380            let tags_leaf = TagsLeafNode {
381                keys: Vec::new(),
382                values: Vec::new(),
383            };
384            let tags_page = Page::new(initial_tags_tree_root_id, Node::TagsLeaf(tags_leaf));
385
386            // Write all new root pages.
387            let new_root_pages = [&free_list_page, &position_page, &tags_page];
388            let mut buffer: Vec<u8> = Vec::with_capacity(new_root_pages.len());
389            let _ = mvcc.write_pages(new_root_pages.into_iter(), &mut buffer)?;
390
391            // Sync the file to disk.
392            mvcc.fsync()?;
393
394            mvcc.write_header(&header1)?;
395            mvcc.write_header(&header0)?;
396
397            // Sync the file to disk.
398            mvcc.fsync()?;
399
400            Ok(mvcc)
401        } else {
402            // Existing DB: read headers from disk, repairing corruption if possible.
403            let maybe_header0 = rw.read_page(HEADER_PAGE_ID_0);
404            let maybe_header1 = rw.read_page(HEADER_PAGE_ID_1);
405
406            let (header0, header1) = match maybe_header0 {
407                Ok(header0) => match maybe_header1 {
408                    Ok(header1) => (header0, header1),
409                    Err(_) => {
410                        let mut buf = page_buf.lock();
411                        rw.write_page(
412                            HEADER_PAGE_ID_1,
413                            &header0,
414                            &mut buf,
415                            options.zero_fill_pages,
416                        )?;
417                        (header0.clone(), Arc::new(header0.as_ref().clone()))
418                    }
419                },
420                Err(err_header0) => match maybe_header1 {
421                    Ok(header1) => {
422                        let mut buf = page_buf.lock();
423                        header1.serialize_into(&mut buf, options.zero_fill_pages)?;
424                        rw.write_page(
425                            HEADER_PAGE_ID_0,
426                            &header1,
427                            &mut buf,
428                            options.zero_fill_pages,
429                        )?;
430                        (Arc::new(header1.as_ref().clone()), header1)
431                    }
432                    Err(_) => {
433                        return Err(err_header0);
434                    }
435                },
436            };
437
438            let mvcc = Self {
439                db_path: options.db_path,
440                rw,
441                reader_tsns,
442                page_size: options.page_size,
443                max_node_size,
444                page_buf,
445                verbose,
446                zero_fill_pages: options.zero_fill_pages,
447                page_cache,
448                pinned_headers: [ArcSwap::new(header0), ArcSwap::new(header1)],
449                // cache_hits: AtomicU64::new(0),
450                // cache_misses: AtomicU64::new(0),
451                // last_stats_print: AtomicU64::new(0),
452                // start_time: Instant::now(),
453            };
454
455            // Set tag key width based on latest header.
456            if let Ok(header_page) = mvcc.get_latest_header_page() {
457                let header_node = header_page.as_header_node()?;
458
459                // Check the database file length.
460                mvcc.rw.pager.verify_file_size(header_node.next_page_id)?;
461
462                // Don't proceed if this software is too old.
463                if header_node.schema_version > DB_SCHEMA_VERSION {
464                    let schema_version = header_node.schema_version;
465                    return Err(InternalError(format!(
466                        "Software version is too old. This software supports schema version {DB_SCHEMA_VERSION} but the database file has schema version {schema_version}."
467                    )));
468                }
469
470                // Set key width first from the reported header schema
471                if header_node.schema_version == 0 {
472                    set_tag_key_width(8);
473                } else {
474                    set_tag_key_width(crate::tags_tree_nodes::TAG_HASH_LEN);
475                }
476
477                // Defensive check: if header says schema_version=1, verify tags root deserializes at width=16.
478                // If it fails but succeeds at width=8, downgrade schema_version to 0 in both headers.
479                if header_node.schema_version == 1 {
480                    use crate::node::Node;
481                    let tags_root = header_node.tags_tree_root_id;
482                    // Try with width=16
483                    set_tag_key_width(crate::tags_tree_nodes::TAG_HASH_LEN);
484                    let sixteen_ok = mvcc
485                        .read_page(tags_root)
486                        .map(|p| matches!(p.node, Node::TagsLeaf(_) | Node::TagsInternal(_)))
487                        .is_ok();
488                    if !sixteen_ok {
489                        return Err(DcbError::InitializationError(
490                            "Tag key width is too small for schema version.".to_string(),
491                        ));
492                    }
493                }
494            }
495
496            // Check we can read all the root pages.
497            let header_page = mvcc.get_latest_header_page()?;
498            let header_node = header_page.as_header_node()?;
499            if !matches!(
500                mvcc.read_page(header_node.free_lists_tree_root_id)?.node,
501                Node::FreeListInternal(_) | Node::FreeListLeaf(_)
502            ) {
503                return Err(DcbError::DatabaseCorrupted(format!(
504                    "Page {} is not a free list page",
505                    header_node.free_lists_tree_root_id.0
506                )));
507            };
508            if !matches!(
509                mvcc.read_page(header_node.tags_tree_root_id)?.node,
510                Node::TagsInternal(_) | Node::TagsLeaf(_)
511            ) {
512                return Err(DcbError::DatabaseCorrupted(format!(
513                    "Page {} is not a tags tree page",
514                    header_node.tags_tree_root_id.0
515                )));
516            };
517            if !matches!(
518                mvcc.read_page(header_node.events_tree_root_id)?.node,
519                Node::EventInternal(_) | Node::EventLeaf(_)
520            ) {
521                return Err(DcbError::DatabaseCorrupted(format!(
522                    "Page {} is not a event tree page",
523                    header_node.events_tree_root_id.0
524                )));
525            };
526            if header_node.tracking_tree_root_id != PageID(0) {
527                if !matches!(
528                    mvcc.read_page(header_node.tracking_tree_root_id)?.node,
529                    Node::TrackingInternal(_) | Node::TrackingLeaf(_)
530                ) {
531                    return Err(DcbError::DatabaseCorrupted(format!(
532                        "Page {} is not a tracking tree page",
533                        header_node.tracking_tree_root_id.0
534                    )));
535                };
536            }
537            println!("UmaDB root pages found");
538            Ok(mvcc)
539        }
540    }
541
542    pub fn get_latest_header_page(&self) -> DcbResult<Arc<Page>> {
543        for attempt in 0..GET_LATEST_HEADER_RETRIES {
544            let h0 = self.read_header(HEADER_PAGE_ID_0);
545            let h1 = self.read_header(HEADER_PAGE_ID_1);
546
547            match (h0, h1) {
548                (Ok(page0), Ok(page1)) => {
549                    let node0 = page0.as_header_node()?;
550                    let node1 = page1.as_header_node()?;
551
552                    if node1.tsn > node0.tsn {
553                        return Ok(page1);
554                    } else {
555                        return Ok(page0);
556                    }
557                }
558                (Ok(page0), Err(_)) => {
559                    let _ = page0.as_header_node()?;
560                    return Ok(page0);
561                }
562                (Err(_), Ok(page1)) => {
563                    let _ = page1.as_header_node()?;
564                    return Ok(page1);
565                }
566                (Err(e0), Err(e1)) => {
567                    if attempt + 1 < GET_LATEST_HEADER_RETRIES {
568                        if self.verbose {
569                            println!(
570                                "Both headers invalid on attempt {}: {:?} | {:?}. Retrying...",
571                                attempt + 1,
572                                e0,
573                                e1
574                            );
575                        }
576                        sleep(GET_LATEST_HEADER_DELAY);
577                        continue;
578                    } else {
579                        return Err(DcbError::DatabaseCorrupted(format!(
580                            "Both header pages appear corrupted after {} attempts: ({:?}) and ({:?})",
581                            GET_LATEST_HEADER_RETRIES, e0, e1
582                        )));
583                    }
584                }
585            }
586        }
587        // Unreachable due to returns in match and final error, but keep to satisfy type checker
588        Err(DcbError::DatabaseCorrupted(
589            "Unable to read a valid header".to_string(),
590        ))
591    }
592
593    fn write_header(&self, page: &Page) -> DcbResult<()> {
594        let mut buf = self.page_buf.lock();
595        self.rw
596            .write_page(page.page_id, &page, &mut buf, self.zero_fill_pages)
597    }
598
599    pub fn pin_header(&self, page: Arc<Page>) {
600        let header_idx = (page.page_id != HEADER_PAGE_ID_0) as usize;
601        self.pinned_headers[header_idx].store(page);
602    }
603
604    pub fn read_header(&self, page_id: PageID) -> DcbResult<Arc<Page>> {
605        let header_idx = (page_id != HEADER_PAGE_ID_0) as usize;
606        Ok(self.pinned_headers[header_idx].load_full())
607    }
608
609    pub fn read_page(&self, page_id: PageID) -> DcbResult<Arc<Page>> {
610        match page_id {
611            HEADER_PAGE_ID_0 | HEADER_PAGE_ID_1 => Err(InternalError(
612                "Do not read headers with read_page".to_string(),
613            )),
614            _ => {
615                // Try to get the page from the deserialized page cache.
616                if let Some(ref page_cache) = self.page_cache {
617                    let page = page_cache
618                        .try_get_with(page_id, || {
619                            // Init closure, reads once from disk for all blocked waiters.
620                            self.rw.read_page(page_id)
621                        })
622                        .map_err(|err| clone_dcb_error(&err))?;
623                    Ok(page)
624                } else {
625                    Ok(self.rw.read_page(page_id)?)
626                }
627            }
628        }
629    }
630
631    // pub fn read_page(&self, page_id: PageID) -> DcbResult<Arc<Page>> {
632    //     match page_id {
633    //         HEADER_PAGE_ID_0 => return Err(InternalError("Do not read headers with read_page".to_string())),
634    //         HEADER_PAGE_ID_1 => return Err(InternalError("Do not read headers with read_page".to_string())),
635    //         _ => {
636    //             if let Some(ref page_cache) = self.page_cache {
637    //                 // Track whether the closure was actually invoked (a cache miss)
638    //                 let mut was_miss = false;
639    //
640    //                 let page = page_cache
641    //                     .try_get_with(page_id, || {
642    //                         was_miss = true;
643    //                         let page = self.rw.read_page(page_id)?;
644    //
645    //                         println!("Read page: {:?}", page.clone().node.type_name());
646    //                         Ok(page)
647    //                     })
648    //                     .map_err(|err| clone_dcb_error(&err))?;
649    //
650    //                 // 1. Record hit or miss atomically
651    //                 if was_miss {
652    //                     self.cache_misses.fetch_add(1, Ordering::Relaxed);
653    //                 } else {
654    //                     self.cache_hits.fetch_add(1, Ordering::Relaxed);
655    //                 }
656    //
657    //                 // 2. Check if ~1 second has elapsed and print
658    //                 self.maybe_print_cache_stats();
659    //
660    //                 Ok(page)
661    //             } else {
662    //                 Ok(self.rw.read_page(page_id)?)
663    //             }
664    //         }
665    //     }
666    // }
667    //
668    // fn maybe_print_cache_stats(&self) {
669    //     let now_ms = self.start_time.elapsed().as_millis() as u64;
670    //     let last_ms = self.last_stats_print.load(Ordering::Relaxed);
671    //
672    //     // Rate-limit check: Has 1,000ms passed since last print?
673    //     if now_ms >= last_ms + 1000 {
674    //         // Atomic compare-exchange ensures ONLY ONE THREAD prints per second
675    //         if self
676    //             .last_stats_print
677    //             .compare_exchange(last_ms, now_ms, Ordering::SeqCst, Ordering::Relaxed)
678    //             .is_ok()
679    //         {
680    //             let hits = self.cache_hits.swap(0, Ordering::Relaxed);
681    //             let misses = self.cache_misses.swap(0, Ordering::Relaxed);
682    //             let total = hits + misses;
683    //
684    //             if total > 0 {
685    //                 let hit_ratio = (hits as f64 / total as f64) * 100.0;
686    //                 println!(
687    //                     "[CACHE STATS] Last ~1s -> Hits: {hits} | Misses (Disk Reads): {misses} | Total Ops: {total} | Hit Ratio: {hit_ratio:.2}%"
688    //                 );
689    //             }
690    //         }
691    //     }
692    // }
693
694    pub fn reader(&self) -> DcbResult<Reader> {
695        // Need to be careful here about time-of-check to time-of-use (TOCTOU).
696        loop {
697            // Observe latest, publish our guard, then re-observe.
698            let header_page = self.get_latest_header_page()?;
699            let header_node = header_page.as_header_node()?;
700
701            // Publish our guard for this snapshot's TSN.
702            let tsn = header_node.tsn;
703            self.reader_tsns.register(tsn);
704
705            // Re-read: if latest is still tsn, no writer has committed past our
706            // snapshot since we published, so its pages cannot have been reused.
707            let recheck = self.get_latest_header_page()?;
708            let recheck_node = recheck.as_header_node()?;
709            if recheck_node.tsn == tsn {
710                return Ok(Reader {
711                    header_page_id: header_page.page_id,
712                    tsn: header_node.tsn,
713                    events_tree_root_id: header_node.events_tree_root_id,
714                    tags_tree_root_id: header_node.tags_tree_root_id,
715                    next_position: header_node.next_position,
716                    tracking_tree_root_id: header_node.tracking_tree_root_id,
717                    reader_tsns: Arc::clone(&self.reader_tsns),
718                });
719            }
720            // Snapshot advanced during registration; our guard may be stale. Roll
721            // back the tentative registration (otherwise a phantom count leaks on
722            // the stale, lower TSN and pins reclamation forever) and re-register
723            // against the newer snapshot.
724            self.reader_tsns.unregister(tsn);
725        }
726    }
727
728    pub fn writer(&self) -> DcbResult<Writer> {
729        if self.verbose {
730            println!();
731            println!("Constructing writer...");
732        }
733
734        // Get the latest header
735        let header_page = self.get_latest_header_page()?;
736        let header_node = header_page.as_header_node()?;
737
738        // Create the writer
739        let mut writer = Writer::new(
740            header_page.clone(),
741            Tsn(header_node.tsn.0 + 1),
742            header_node.next_page_id,
743            header_node.free_lists_tree_root_id,
744            header_node.events_tree_root_id,
745            header_node.tags_tree_root_id,
746            header_node.tracking_tree_root_id,
747            header_node.next_position,
748            self.verbose,
749            self.page_size,
750            self.max_node_size,
751        );
752
753        if self.verbose {
754            println!("Constructed writer with {:?}", writer.tsn);
755        }
756
757        // Find the reusable page IDs.
758        writer.find_reusable_page_ids(self)?;
759
760        Ok(writer)
761    }
762
763    /// Extracts contiguous runs of pages and writes them to disk in batches.
764    /// Returns the number of pages written.
765    pub fn write_pages<'a, I>(&self, pages: I, writer_buffer: &mut Vec<u8>) -> DcbResult<usize>
766    where
767        I: IntoIterator<Item = &'a Page>,
768    {
769        // 1. Collect and Sort
770        let mut pages_vec: Vec<&'a Page> = pages.into_iter().collect();
771        if pages_vec.is_empty() {
772            return Ok(0);
773        }
774
775        pages_vec.sort_unstable_by_key(|p| p.page_id.0);
776
777        let mut count = 0usize;
778
779        // 2. Group into contiguous chunks
780        let chunked_pages = pages_vec.chunk_by(|a, b| a.page_id.0 + 1 == b.page_id.0);
781
782        // 3. Process and write each chunk
783        for contiguous_pages in chunked_pages {
784            let start_page_id = contiguous_pages[0].page_id;
785            let chunk_len = contiguous_pages.len();
786
787            // Prepare the batch buffer
788            let needed_bytes = chunk_len * self.page_size;
789            if writer_buffer.len() < needed_bytes {
790                writer_buffer.resize(needed_bytes, 0);
791            }
792
793            // Borrow a slice of the exact size needed
794            let needed_buf = &mut writer_buffer[..needed_bytes];
795
796            // Serialize all pages in this chunk into the buffer
797            for (idx, page) in contiguous_pages.iter().enumerate() {
798                let byte_start = idx * self.page_size;
799                let byte_end = byte_start + self.page_size;
800
801                page.serialize_into(&mut needed_buf[byte_start..byte_end], self.zero_fill_pages)?;
802            }
803
804            // if chunk_len > 1 {
805            //     println!("Got {} pages in chunk", chunk_len);
806            // }
807
808            // Write the entire batch in a single system call
809            self.rw
810                .pager
811                .write_contiguous_pages(start_page_id, needed_buf)?;
812
813            count += chunk_len;
814        }
815
816        Ok(count)
817    }
818
819    pub fn commit(&self, writer: &mut Writer) -> DcbResult<()> {
820        // Process reused and freed page IDs
821        if self.verbose {
822            println!();
823            println!("Commiting writer with {:?}", writer.tsn);
824        }
825
826        writer.process_freed_page_ids(self, self.max_node_size, self.page_size)?;
827
828        // Write all dirty pages (except for the header page) to the file
829        if !writer.dirty.is_empty() {
830            let count = { self.write_pages(writer.dirty.values(), &mut writer.writer_buffer)? };
831            if self.verbose {
832                println!("Wrote {} dirty page(s) to file", count);
833            }
834        }
835
836        // Sync the file to disk
837        self.fsync()?;
838
839        // Cache the new pages without cloning by draining dirty pages.
840        if let Some(ref page_cache) = self.page_cache {
841            for (page_id, page) in writer.dirty.drain() {
842                page_cache.insert(page_id, Arc::new(page));
843            }
844        } else {
845            writer.dirty.clear();
846        }
847
848        // Mutate and write header page.
849        let next_header_page = writer.cow_header_page()?;
850        self.write_header(&next_header_page)?;
851
852        // Sync the file to disk
853        self.fsync()?;
854
855        // Pin the header page.
856        self.pin_header(Arc::new(next_header_page));
857
858        if self.verbose {
859            println!("Committed writer with {:?}", writer.tsn);
860        }
861
862        Ok(())
863    }
864
865    pub fn prepare_commit<T: MvccSnapshot>(
866        &self,
867        writer: &mut Writer,
868        mvcc: &T,
869    ) -> DcbResult<(PreparedCommit, FxHashMap<PageID, Arc<Page>>, Arc<Page>)> {
870        writer.process_freed_page_ids(mvcc, self.max_node_size, self.page_size)?;
871
872        let mut wet_pages =
873            FxHashMap::with_capacity_and_hasher(writer.dirty.len() + 1, Default::default());
874
875        // Copy-on-write the header page.
876        let dirty_header = writer.cow_header_page()?;
877        let next_header_page_id = dirty_header.page_id;
878
879        // Serialize the header.
880        let mut serialized_header: Vec<u8> = vec![0u8; writer.page_size];
881        serialize_page_into(
882            &mut serialized_header,
883            &dirty_header.node,
884            self.zero_fill_pages,
885        )?;
886
887        // Prepare the commit.
888        let mut prepared_commit = PreparedCommit {
889            header_to_write: (next_header_page_id, serialized_header),
890            pages_to_write: Vec::with_capacity(writer.dirty.len()),
891        };
892
893        // Drain the dirty pages.
894        for (page_id, page) in writer.dirty.drain() {
895            // Serialize the dirty page.
896            let mut serialized_page = vec![0u8; DEFAULT_PAGE_SIZE];
897            serialize_page_into(&mut serialized_page, &page.node, true)?;
898            prepared_commit
899                .pages_to_write
900                .push((page_id.clone(), serialized_page));
901
902            // Remember the "wet" page for the writer snapshot.
903            wet_pages.insert(page_id, Arc::new(page));
904        }
905
906        // Remember the "wet" header for the writer snapshot.
907        let wet_header = Arc::new(dirty_header);
908
909        // Advance the writer so it is primed for the NEXT pipelined batch. The
910        // writer is persisted across batches (it is the sole authority on future
911        // DB state and cannot be re-derived from the on-disk header, which lags behind by
912        // one in-flight batch), so the bookkeeping that `Mvcc::writer()` used to do
913        // per batch must be done here instead:
914        //  - flip to the header slot we just generated (headers are double-buffered),
915        //  - bump the TSN. Every committed batch MUST have a strictly greater TSN:
916        //    `get_latest_header_page` picks the higher-TSN slot, `reader()`'s TOCTOU
917        //    guard assumes the TSN advances when a writer commits, and page
918        //    reclamation gates reuse on the freed TSN vs. the smallest live reader
919        //    TSN. Note frees were already stamped with the pre-bump TSN above.
920        //  - clear the per-page deserialization cache. It is a `PageID -> content`
921        //    cache that is only sound while a page ID's content is immutable — true
922        //    within a single batch, but false across batches once a freed page ID is
923        //    reused, which would otherwise return stale nodes for that ID.
924        writer.header_page = wet_header.clone();
925        writer.tsn = Tsn(writer.tsn.0 + 1);
926        writer.deserialized.clear();
927
928        Ok((prepared_commit, wet_pages, wet_header))
929    }
930
931    pub fn update_page_cache(&self, mut wet_pages: FxHashMap<PageID, Arc<Page>>) -> DcbResult<()> {
932        // Cache the new pages without cloning by draining dirty pages.
933        if let Some(ref page_cache) = self.page_cache {
934            for (page_id, page) in wet_pages.drain() {
935                page_cache.insert(page_id, page);
936            }
937        }
938        Ok(())
939    }
940
941    pub fn fsync(&self) -> DcbResult<()> {
942        self.rw.pager.fsync()?;
943        Ok(())
944    }
945}
946
947impl MvccSnapshot for Mvcc {
948    fn read_page(&self, page_id: PageID) -> DcbResult<Arc<Page>> {
949        self.read_page(page_id)
950    }
951}
952
953pub struct WriterSnapshot<'a> {
954    // Fully durable pages.
955    pub base_mvcc: &'a Mvcc,
956
957    // The dirty pages modified in the previous batch
958    // that haven't been fully committed/fsynced yet.
959    pub wet_pages: &'a FxHashMap<PageID, Arc<Page>>,
960}
961
962impl<'a> MvccSnapshot for WriterSnapshot<'a> {
963    fn read_page(&self, page_id: PageID) -> DcbResult<Arc<Page>> {
964        // 1. Check if the writer has modified this page recently
965        if let Some(wet_page) = self.wet_pages.get(&page_id) {
966            return Ok(wet_page.clone());
967        }
968
969        // 2. If not, fall back to the globally committed disk/cache state
970        self.base_mvcc.read_page(page_id)
971    }
972}
973
974// Writer transaction
975pub struct Writer {
976    pub header_page: Arc<Page>,
977    pub tsn: Tsn,
978    pub next_page_id: PageID,
979    pub free_lists_tree_root_id: PageID,
980    pub events_tree_root_id: PageID,
981    pub tags_tree_root_id: PageID,
982    pub tracking_tree_root_id: PageID,
983    pub next_position: Position,
984    pub reusable_page_ids: VecDeque<(PageID, Tsn)>,
985    pub freed_page_ids: FxHashSet<PageID>,
986    pub deserialized: FxHashMap<PageID, Arc<Page>>,
987    pub dirty: FxHashMap<PageID, Page>,
988    pub reused_page_ids: VecDeque<(PageID, Tsn)>,
989    pub verbose: bool,
990    pub page_size: usize,
991    pub max_node_size: usize,
992    pub writer_buffer: Vec<u8>,
993}
994
995impl Writer {
996    pub fn new(
997        header_page: Arc<Page>,
998        tsn: Tsn,
999        next_page_id: PageID,
1000        free_lists_tree_root_id: PageID,
1001        events_tree_root_id: PageID,
1002        tags_tree_root_id: PageID,
1003        tracking_tree_root_id: PageID,
1004        next_position: Position,
1005        verbose: bool,
1006        page_size: usize,
1007        max_node_size: usize,
1008    ) -> Self {
1009        Self {
1010            header_page,
1011            tsn,
1012            next_page_id,
1013            free_lists_tree_root_id,
1014            events_tree_root_id,
1015            tags_tree_root_id,
1016            tracking_tree_root_id,
1017            next_position,
1018            reusable_page_ids: VecDeque::new(),
1019            freed_page_ids: FxHashSet::default(),
1020            deserialized: FxHashMap::default(),
1021            dirty: FxHashMap::default(),
1022            reused_page_ids: VecDeque::new(),
1023            verbose,
1024            page_size,
1025            max_node_size,
1026            writer_buffer: Vec::with_capacity(page_size * 20),
1027        }
1028    }
1029
1030    pub fn reset(&mut self, mvcc: &Mvcc) -> DcbResult<()> {
1031        // Get the latest header
1032        let header_page = mvcc.get_latest_header_page()?;
1033        let header_node = header_page.as_header_node()?;
1034
1035        // Set values from the header: TSN, root page IDs, next page Id, next sequence position.
1036        self.header_page = header_page.clone();
1037        self.tsn = Tsn(header_node.tsn.0 + 1);
1038        self.next_page_id = header_node.next_page_id;
1039        self.free_lists_tree_root_id = header_node.free_lists_tree_root_id;
1040        self.events_tree_root_id = header_node.events_tree_root_id;
1041        self.tags_tree_root_id = header_node.tags_tree_root_id;
1042        self.tracking_tree_root_id = header_node.tracking_tree_root_id;
1043        self.next_position = header_node.next_position;
1044
1045        if self.verbose {
1046            println!("Reset writer with {:?}", self.tsn);
1047        }
1048
1049        // Find the reusable page IDs.
1050        self.find_reusable_page_ids(mvcc)?;
1051
1052        // Also clear everything else.
1053        self.freed_page_ids.clear();
1054        self.deserialized.clear();
1055        self.dirty.clear();
1056        self.reused_page_ids.clear();
1057
1058        Ok(())
1059    }
1060
1061    /// Returns the current issue position and increments the next position.
1062    ///
1063    /// Returns:
1064    ///
1065    /// The current issue position.
1066    pub fn issue_position(&mut self) -> Position {
1067        let pos = self.next_position;
1068        self.next_position = Position(self.next_position.0 + 1);
1069        pos
1070    }
1071
1072    /// Retrieves a reference to the page with the given ID.
1073    ///
1074    /// First checks the dirty pages map, then the deserialized pages map.
1075    /// If the page is not found in either map, it is deserialized from the MVCC.
1076    ///
1077    /// # Arguments
1078    ///
1079    /// * `mvcc`: A reference to the MVCC.
1080    /// * `page_id`: The ID of the page to retrieve.
1081    ///
1082    /// # Returns
1083    ///
1084    /// A `DcbResult` containing a reference to the page if found, or an error if the page could not be found.
1085    pub fn get_page_ref<T: MvccSnapshot>(&mut self, mvcc: &T, page_id: PageID) -> DcbResult<&Page> {
1086        // 1. Check dirty pages first (Single lookup using if let)
1087        if let Some(page) = self.dirty.get(&page_id) {
1088            return Ok(page);
1089        }
1090
1091        // 2. Single lookup for deserialized pages (Inserts & returns ref if missing)
1092        let page_arc = match self.deserialized.entry(page_id) {
1093            Entry::Occupied(entry) => entry.into_mut(),
1094            Entry::Vacant(entry) => {
1095                let deserialized_page = mvcc.read_page(page_id)?;
1096                entry.insert(deserialized_page)
1097            }
1098        };
1099
1100        Ok(page_arc)
1101    }
1102
1103    pub fn get_mut_dirty(&mut self, page_id: PageID) -> DcbResult<&mut Page> {
1104        if let Some(page) = self.dirty.get_mut(&page_id) {
1105            Ok(page)
1106        } else {
1107            Err(DcbError::DirtyPageNotFound(page_id.0))
1108        }
1109    }
1110
1111    pub fn insert_dirty(&mut self, page: Page) -> DcbResult<()> {
1112        if self.freed_page_ids.contains(&page.page_id) {
1113            return Err(DcbError::PageAlreadyFreed(page.page_id.0));
1114        }
1115
1116        match self.dirty.entry(page.page_id) {
1117            Entry::Occupied(_) => Err(DcbError::PageAlreadyDirty(page.page_id.0)),
1118            Entry::Vacant(entry) => {
1119                entry.insert(page);
1120                Ok(())
1121            }
1122        }
1123    }
1124
1125    pub fn alloc_page_id(&mut self) -> PageID {
1126        if let Some((free_page_id, tsn)) = self.reusable_page_ids.pop_front() {
1127            self.reused_page_ids.push_back((free_page_id, tsn));
1128            return free_page_id;
1129        }
1130
1131        let next_page_id = self.next_page_id;
1132        self.next_page_id = PageID(next_page_id.0 + 1);
1133        next_page_id
1134    }
1135
1136    pub fn get_dirty_page_id(&mut self, page_id: PageID) -> DcbResult<PageID> {
1137        // 1. Guard Clause: Fast O(1) set lookup
1138        if self.freed_page_ids.contains(&page_id) {
1139            return Err(DcbError::PageAlreadyFreed(page_id.0));
1140        }
1141
1142        // 2. Early return if already dirty
1143        if self.dirty.contains_key(&page_id) {
1144            // if self.verbose {
1145            //     println!("{page_id:?} is already dirty");
1146            // }
1147            return Ok(page_id);
1148        }
1149
1150        // 3. CoW Path: The page is clean, so we must copy it to a new PageID.
1151        self.freed_page_ids.insert(page_id);
1152
1153        let new_page_id = self.alloc_page_id();
1154        let mut new_page =
1155            Arc::unwrap_or_clone(self.deserialized.remove(&page_id).ok_or_else(|| {
1156                DcbError::DatabaseCorrupted(format!(
1157                    "Deserialized page {page_id:?} not found to make dirty"
1158                ))
1159            })?);
1160
1161        new_page.page_id = new_page_id;
1162
1163        // if self.verbose {
1164        //     println!(
1165        //         "Copied {page_id:?} to {new_page_id:?}: {:?}",
1166        //         new_page.node
1167        //     );
1168        // }
1169
1170        self.dirty.insert(new_page_id, new_page);
1171
1172        Ok(new_page_id)
1173    }
1174
1175    pub fn append_freed_page_id(&mut self, page_id: PageID) {
1176        if self.freed_page_ids.insert(page_id) {
1177            self.dirty.remove(&page_id);
1178        }
1179    }
1180
1181    pub fn find_reusable_page_ids(&mut self, mvcc: &Mvcc) -> DcbResult<()> {
1182        // Find the smallest live reader TSN (O(log n): the leftmost key of the multiset)
1183        let smallest_reader_tsn = mvcc.reader_tsns.min();
1184        self.find_reusable_page_ids_with_snapshot(mvcc, smallest_reader_tsn)
1185    }
1186
1187    /// Snapshot-aware variant used by the pipelined writer thread. It reads free-list
1188    /// pages through an `MvccSnapshot` so it can see the previous in-flight batch's
1189    /// not-yet-durable `wet_pages`, and takes the smallest live reader TSN explicitly
1190    /// (the caller reads it from the base `Mvcc`).
1191    pub fn find_reusable_page_ids_with_snapshot<T: MvccSnapshot>(
1192        &mut self,
1193        mvcc: &T,
1194        smallest_reader_tsn: Option<Tsn>,
1195    ) -> DcbResult<()> {
1196        let verbose = self.verbose;
1197        let mut reusable_page_ids: VecDeque<(PageID, Tsn)> = VecDeque::new();
1198        // Get free page IDs
1199        if verbose {
1200            println!("Finding reusable page IDs for TSN {:?}...", self.tsn);
1201        }
1202        if verbose {
1203            println!("Smallest reader TSN: {smallest_reader_tsn:?}");
1204        }
1205
1206        if verbose {
1207            println!("Root is {:?}", self.free_lists_tree_root_id);
1208        }
1209        // Walk the tree to find leaf nodes
1210        let mut stack = vec![(self.free_lists_tree_root_id, 0)];
1211        let mut is_finished = false;
1212
1213        while let Some((page_id, idx)) = stack.pop() {
1214            if is_finished {
1215                break;
1216            }
1217            let node_owned = {
1218                match self.get_page_ref(mvcc, page_id) {
1219                    Ok(p) => p.node.clone(),
1220                    Err(e) => {
1221                        return Err(DcbError::DatabaseCorrupted(format!(
1222                            "Free list page {:?} load error: {:?}",
1223                            page_id, e
1224                        )));
1225                    }
1226                }
1227            };
1228            match node_owned {
1229                Node::FreeListInternal(node) => {
1230                    if verbose {
1231                        println!("{:?} is internal node", page_id);
1232                    }
1233                    if idx < node.child_ids.len() {
1234                        let child_page_id = node.child_ids[idx];
1235                        stack.push((page_id, idx + 1));
1236                        stack.push((child_page_id, 0));
1237                    }
1238                }
1239                Node::FreeListLeaf(node) => {
1240                    if verbose {
1241                        println!("{:?} is leaf node", page_id);
1242                    }
1243                    for i in 0..node.keys.len() {
1244                        let tsn = node.keys[i];
1245                        if let Some(smallest) = smallest_reader_tsn
1246                            && tsn > smallest
1247                        {
1248                            is_finished = true;
1249                            break;
1250                        }
1251
1252                        let leaf_value = &node.values[i];
1253                        if leaf_value.root_id == PageID(0) {
1254                            for &page_id in &leaf_value.page_ids {
1255                                reusable_page_ids.push_back((page_id, tsn));
1256                            }
1257                        } else {
1258                            // Traverse into the TSN-subtree rooted at root_id using the same (node, idx)
1259                            // iterative DFS pattern as the main FreeList traversal. This preserves
1260                            // left-to-right order deterministically.
1261                            let mut tsn_stack: Vec<(PageID, usize)> = vec![(leaf_value.root_id, 0)];
1262                            if self.verbose {
1263                                println!("TSN-subtree root_id: {:?}", leaf_value.root_id);
1264                            }
1265                            if self.verbose {
1266                                println!(
1267                                    "root_id in dirty? {}",
1268                                    self.dirty.contains_key(&leaf_value.root_id)
1269                                );
1270                            }
1271                            while let Some((sub_id, sidx)) = tsn_stack.pop() {
1272                                let sub_node = {
1273                                    match self.get_page_ref(mvcc, sub_id) {
1274                                        Ok(p) => p.node.clone(),
1275                                        Err(e) => {
1276                                            return Err(DcbError::DatabaseCorrupted(format!(
1277                                                "TSN subtree page {:?} load error: {:?}",
1278                                                sub_id, e
1279                                            )));
1280                                        }
1281                                    }
1282                                };
1283                                match sub_node {
1284                                    Node::FreeListTsnInternal(tsn_internal) => {
1285                                        if sidx < tsn_internal.child_ids.len() {
1286                                            let child_id = tsn_internal.child_ids[sidx];
1287                                            tsn_stack.push((sub_id, sidx + 1));
1288                                            tsn_stack.push((child_id, 0));
1289                                        }
1290                                    }
1291                                    Node::FreeListTsnLeaf(tsn_leaf) => {
1292                                        for &pid in &tsn_leaf.page_ids {
1293                                            reusable_page_ids.push_back((pid, tsn));
1294                                        }
1295                                    }
1296                                    other => {
1297                                        return Err(DcbError::DatabaseCorrupted(format!(
1298                                            "Invalid node type in TSN subtree: {}",
1299                                            other.type_name()
1300                                        )));
1301                                    }
1302                                }
1303                            }
1304                        }
1305                    }
1306                }
1307                _ => {
1308                    return Err(DcbError::DatabaseCorrupted(
1309                        "Invalid node type in free list tree".to_string(),
1310                    ));
1311                }
1312            }
1313        }
1314
1315        // --- NEW EXTENT-BASED ALLOCATION LOGIC ---
1316
1317        // 1. Convert the collected pages to a Vec and sort them strictly by PageID
1318        let mut pages_vec: Vec<(PageID, Tsn)> = reusable_page_ids.into();
1319        pages_vec.sort_unstable_by_key(|(pid, _)| pid.0);
1320
1321        // 2. Group the sorted pages into contiguous extents
1322        let mut extents: Vec<VecDeque<(PageID, Tsn)>> = Vec::new();
1323        let mut current_extent: VecDeque<(PageID, Tsn)> = VecDeque::new();
1324
1325        for (pid, tsn) in pages_vec {
1326            if let Some((last_pid, _)) = current_extent.back() {
1327                if pid.0 == last_pid.0 + 1 {
1328                    current_extent.push_back((pid, tsn));
1329                } else {
1330                    extents.push(current_extent);
1331                    current_extent = VecDeque::new();
1332                    current_extent.push_back((pid, tsn));
1333                }
1334            } else {
1335                current_extent.push_back((pid, tsn));
1336            }
1337        }
1338        if !current_extent.is_empty() {
1339            extents.push(current_extent);
1340        }
1341
1342        // 3. Sort the extents deterministically
1343        extents.sort_unstable_by(|a, b| {
1344            // Primary sort: Largest extents first
1345            b.len()
1346                .cmp(&a.len())
1347                // Secondary sort (Tie-breaker): Lowest starting PageID first
1348                .then(a[0].0.cmp(&b[0].0))
1349        });
1350
1351        let extents_count = extents.len();
1352
1353        // 4. Flatten back into the queue of reusable page IDs
1354        self.reusable_page_ids.clear();
1355        for mut extent in extents {
1356            self.reusable_page_ids.append(&mut extent);
1357        }
1358
1359        if verbose {
1360            println!(
1361                "Found {} reusable pages, optimized into {} contiguous extents.",
1362                self.reusable_page_ids.len(),
1363                extents_count
1364            );
1365        }
1366
1367        Ok(())
1368    }
1369
1370    pub fn process_freed_page_ids<T: MvccSnapshot>(
1371        &mut self,
1372        snapshot: &T,
1373        max_node_size: usize,
1374        page_size: usize,
1375    ) -> DcbResult<()> {
1376        while !self.reused_page_ids.is_empty() || !self.freed_page_ids.is_empty() {
1377            // Remove reused page IDs from free lists.
1378            while let Some((reused_page_id, tsn)) = self.reused_page_ids.pop_front() {
1379                // Remove the reused page ID from the freed list tree
1380                self.remove_free_page_id(snapshot, tsn, reused_page_id)?;
1381            }
1382
1383            // Process freed page IDs by taking ownership of the current batch.
1384            // This leaves self.freed_page_ids empty and ready to receive any newly
1385            // freed pages generated by the B-tree inserts below.
1386            let freed_page_ids = std::mem::take(&mut self.freed_page_ids);
1387
1388            for freed_page_id in freed_page_ids {
1389                // Remove dirty pages that were also freed
1390                self.dirty.remove(&freed_page_id);
1391
1392                // Insert the page ID in the freed list tree
1393                self.insert_freed_page_id(
1394                    snapshot,
1395                    self.tsn,
1396                    freed_page_id,
1397                    max_node_size,
1398                    page_size,
1399                )?;
1400            }
1401        }
1402        Ok(())
1403    }
1404
1405    // Free list tree methods
1406    pub fn insert_freed_page_id<T: MvccSnapshot>(
1407        &mut self,
1408        snapshot: &T,
1409        tsn: Tsn,
1410        freed_page_id: PageID,
1411        max_node_size: usize,
1412        page_size: usize,
1413    ) -> DcbResult<()> {
1414        let verbose = self.verbose;
1415        if verbose {
1416            println!("Inserting {freed_page_id:?} for {tsn:?}");
1417            println!("Root is {:?}", self.free_lists_tree_root_id);
1418        }
1419        // Get the root page ID.
1420        let mut current_page_id = self.free_lists_tree_root_id;
1421
1422        // Traverse the tree to find a leaf node
1423        let mut stack: Vec<PageID> = Vec::new();
1424        let plan: FreePageIDInsertStrategy;
1425        loop {
1426            let current_page_ref = self.get_page_ref(snapshot, current_page_id)?;
1427            if let Node::FreeListLeaf(leaf_node) = &current_page_ref.node {
1428                let len_keys = leaf_node.keys.len();
1429                if len_keys == 0 {
1430                    if !leaf_node.would_fit_new_tsn_and_page_id(max_node_size) {
1431                        return Err(DcbError::InternalError("Page size too small".to_string()));
1432                    }
1433                    plan = FreePageIDInsertStrategy::PushTsnOntoFreeListLeaf;
1434                } else {
1435                    let last_idx = len_keys - 1;
1436                    let last_key = leaf_node.keys[last_idx];
1437                    if tsn == last_key {
1438                        // Append to the existing last TSN
1439                        if leaf_node.values[last_idx].root_id != PageID(0) {
1440                            plan = FreePageIDInsertStrategy::PushPageIdOntoExistingTsnSubtree;
1441                        } else if leaf_node.would_fit_new_page_id(max_node_size) {
1442                            plan = FreePageIDInsertStrategy::PushPageIdOntoFreeListLeaf(last_idx);
1443                        } else if leaf_node.keys.len() == 1 {
1444                            plan = FreePageIDInsertStrategy::MoveTsnToNewTsnSubtree;
1445                        } else {
1446                            plan = FreePageIDInsertStrategy::SplitFreeListLeaf;
1447                        }
1448                    } else if tsn > last_key {
1449                        // New last TSN
1450                        if leaf_node.would_fit_new_tsn_and_page_id(max_node_size) {
1451                            plan = FreePageIDInsertStrategy::PushTsnOntoFreeListLeaf;
1452                        } else {
1453                            plan = FreePageIDInsertStrategy::CreateAndPromoteFreeListLeaf;
1454                        }
1455                    } else {
1456                        // We assume freed page IDs are always inserted for the last TSN
1457                        return Err(DcbError::InternalError(
1458                            "Insertion only supported for last TSN in leaf".to_string(),
1459                        ));
1460                    }
1461                }
1462                break;
1463            }
1464            if let Node::FreeListInternal(internal_node) = &current_page_ref.node {
1465                if verbose {
1466                    println!("{:?} is internal node", current_page_ref.page_id);
1467                }
1468                stack.push(current_page_id);
1469                current_page_id = *internal_node
1470                    .child_ids
1471                    .last()
1472                    .expect("FreeListInternal node should have a child");
1473            } else {
1474                return Err(DcbError::DatabaseCorrupted(
1475                    "Expected FreeListInternal node".to_string(),
1476                ));
1477            }
1478        }
1479        if verbose {
1480            println!("{current_page_id:?} is leaf node");
1481        }
1482        // Make the leaf page dirty
1483        let dirty_leaf_page_id = { self.get_dirty_page_id(current_page_id)? };
1484        let replacement_info: Option<(PageID, PageID)> = {
1485            if dirty_leaf_page_id != current_page_id {
1486                Some((current_page_id, dirty_leaf_page_id))
1487            } else {
1488                None
1489            }
1490        };
1491        // Proactive insert logic with capacity checks and optional split
1492        let mut split_info: Option<(Tsn, PageID)> = None;
1493
1494        // First handle TSN-subtree plans without holding a mutable borrow to the freelist leaf
1495        match plan {
1496            FreePageIDInsertStrategy::PushPageIdOntoExistingTsnSubtree => {
1497                // Read leaf immutably to find last_idx and current root_id
1498                let leaf_snapshot = { self.get_page_ref(snapshot, dirty_leaf_page_id)? };
1499                let Node::FreeListLeaf(leaf_ro) = &leaf_snapshot.node else {
1500                    return Err(DcbError::DatabaseCorrupted(
1501                        "Expected FreeListLeaf node".to_string(),
1502                    ));
1503                };
1504                let last_idx = leaf_ro.keys.len() - 1;
1505                let tsn_root_id = leaf_ro.values[last_idx].root_id;
1506                if tsn_root_id == PageID(0) {
1507                    return Err(DcbError::DatabaseCorrupted(
1508                        "Expected TSN-subtree root_id to be set".to_string(),
1509                    ));
1510                }
1511                let new_root_id =
1512                    self.tsn_subtree_insert(snapshot, tsn_root_id, freed_page_id, max_node_size)?;
1513                if new_root_id != tsn_root_id {
1514                    // Now mutate the freelist leaf to update root_id
1515                    let dirty_leaf_page = self.get_mut_dirty(dirty_leaf_page_id)?;
1516                    let Node::FreeListLeaf(dirty_leaf_node2) = &mut dirty_leaf_page.node else {
1517                        return Err(DcbError::DatabaseCorrupted(
1518                            "Expected FreeListLeaf node".to_string(),
1519                        ));
1520                    };
1521                    dirty_leaf_node2.values[last_idx].root_id = new_root_id;
1522                }
1523            }
1524            FreePageIDInsertStrategy::MoveTsnToNewTsnSubtree => {
1525                // Read leaf immutably to capture inline page_ids
1526                let leaf_snapshot = { self.get_page_ref(snapshot, dirty_leaf_page_id)? };
1527                let Node::FreeListLeaf(leaf_ro) = &leaf_snapshot.node else {
1528                    return Err(DcbError::DatabaseCorrupted(
1529                        "Expected FreeListLeaf node".to_string(),
1530                    ));
1531                };
1532                let last_idx = leaf_ro.keys.len() - 1;
1533                let mut page_ids = leaf_ro.values[last_idx].page_ids.clone();
1534                page_ids.push(freed_page_id);
1535                // sort + dedup the inline ids plus the new id
1536                page_ids.sort_by_key(|pid| pid.0);
1537                page_ids.dedup();
1538                // Build the initial TSN-subtree: start with a single leaf that fits, then insert the rest
1539                // Create an empty leaf and add as many as fit by size
1540                let mut initial_ids: Vec<PageID> = Vec::new();
1541                let mut tmp_leaf = FreeListTsnLeafNode {
1542                    page_ids: Vec::new(),
1543                };
1544                for pid in &page_ids {
1545                    let mut candidate = tmp_leaf.clone();
1546                    candidate.page_ids.push(*pid);
1547                    let candidate_page = Page::new(PageID(0), Node::FreeListTsnLeaf(candidate));
1548                    if candidate_page.calc_serialized_size() <= page_size {
1549                        tmp_leaf.page_ids.push(*pid);
1550                        initial_ids.push(*pid);
1551                    } else {
1552                        break;
1553                    }
1554                }
1555                if initial_ids.is_empty() {
1556                    return Err(DcbError::InternalError(
1557                        "Page size too small for TSN-subtree leaf with one PageID".to_string(),
1558                    ));
1559                }
1560                let tsn_leaf_id = self.alloc_page_id();
1561                let tsn_leaf_page = Page::new(tsn_leaf_id, Node::FreeListTsnLeaf(tmp_leaf));
1562                self.insert_dirty(tsn_leaf_page)?;
1563                // Root id starts as this leaf
1564                let mut tsn_root_id = tsn_leaf_id;
1565                // Insert remaining ids via general insert, root may change
1566                for pid in page_ids.into_iter().filter(|p| !initial_ids.contains(p)) {
1567                    tsn_root_id =
1568                        self.tsn_subtree_insert(snapshot, tsn_root_id, pid, max_node_size)?;
1569                }
1570                // Now mutate the freelist leaf to clear inline and set root
1571                let dirty_leaf_page = self.get_mut_dirty(dirty_leaf_page_id)?;
1572                let Node::FreeListLeaf(dirty_leaf_node2) = &mut dirty_leaf_page.node else {
1573                    return Err(DcbError::DatabaseCorrupted(
1574                        "Expected FreeListLeaf node".to_string(),
1575                    ));
1576                };
1577                dirty_leaf_node2.values[last_idx].page_ids.clear();
1578                dirty_leaf_node2.values[last_idx].root_id = tsn_root_id;
1579                if verbose {
1580                    println!("Moved inline page IDs to TSN-subtree {:?}", tsn_root_id);
1581                }
1582            }
1583            _ => { /* handled below with a mutable freelist leaf borrow */ }
1584        }
1585
1586        // Now handle the remaining plans that only mutate the freelist leaf
1587        let dirty_leaf_page = self.get_mut_dirty(dirty_leaf_page_id)?;
1588        if let Node::FreeListLeaf(dirty_leaf_node) = &mut dirty_leaf_page.node {
1589            match plan {
1590                FreePageIDInsertStrategy::PushTsnOntoFreeListLeaf => {
1591                    dirty_leaf_node.push_new_key_and_value(tsn, freed_page_id);
1592                    if verbose {
1593                        println!(
1594                            "Inserted first pair ({tsn:?} -> {freed_page_id:?}) in {dirty_leaf_page_id:?}: {:?}",
1595                            dirty_leaf_node
1596                        );
1597                    }
1598                }
1599                FreePageIDInsertStrategy::PushPageIdOntoFreeListLeaf(last_idx) => {
1600                    dirty_leaf_node.push_new_page_id(last_idx, freed_page_id);
1601                    if verbose {
1602                        println!(
1603                            "Appended {freed_page_id:?} for existing last {tsn:?} in {dirty_leaf_page_id:?}: {:?}",
1604                            dirty_leaf_node
1605                        );
1606                    }
1607                }
1608                FreePageIDInsertStrategy::PushPageIdOntoExistingTsnSubtree => { /* handled earlier */
1609                }
1610                FreePageIDInsertStrategy::MoveTsnToNewTsnSubtree => { /* handled earlier */ }
1611                FreePageIDInsertStrategy::SplitFreeListLeaf => {
1612                    let (popped_key, mut popped_value) =
1613                        dirty_leaf_node.pop_last_key_and_value()?;
1614                    debug_assert_eq!(popped_key, tsn);
1615                    if verbose {
1616                        println!(
1617                            "Split (last TSN) leaf {:?}: {:?}",
1618                            dirty_leaf_page_id,
1619                            dirty_leaf_node.clone()
1620                        );
1621                    }
1622                    // Move the overflowing TSN to a new page and append there
1623                    popped_value.page_ids.push(freed_page_id);
1624                    let new_leaf_node = FreeListLeafNode {
1625                        keys: vec![popped_key],
1626                        values: vec![popped_value],
1627                    };
1628                    let new_leaf_page_id = self.alloc_page_id();
1629                    let new_leaf_page =
1630                        Page::new(new_leaf_page_id, Node::FreeListLeaf(new_leaf_node));
1631                    // let serialized_size = new_leaf_page.calc_serialized_size();
1632                    // if serialized_size > mvcc.page_size {
1633                    //     return Err(DCBError::InternalError(
1634                    //         "Shouldn't get here: page size is too small for a FreeListLeafNode with one TSN and one PageID".to_string(),
1635                    //     ));
1636                    // }
1637                    if verbose {
1638                        println!(
1639                            "Created new leaf {:?} (moved last TSN): {:?}",
1640                            new_leaf_page_id, new_leaf_page.node
1641                        );
1642                    }
1643                    self.insert_dirty(new_leaf_page)?;
1644                    split_info = Some((tsn, new_leaf_page_id));
1645                }
1646                FreePageIDInsertStrategy::CreateAndPromoteFreeListLeaf => {
1647                    // Create a new leaf containing only this last TSN and promote it
1648                    let new_leaf_node = FreeListLeafNode {
1649                        keys: vec![tsn],
1650                        values: vec![FreeListLeafValue {
1651                            page_ids: vec![freed_page_id],
1652                            root_id: PageID(0),
1653                        }],
1654                    };
1655                    let new_leaf_page_id = self.alloc_page_id();
1656                    let new_leaf_page =
1657                        Page::new(new_leaf_page_id, Node::FreeListLeaf(new_leaf_node));
1658                    // let serialized_size = new_leaf_page.calc_serialized_size();
1659                    // if serialized_size > mvcc.page_size {
1660                    //     return Err(DCBError::InternalError(
1661                    //         "Shouldn't get here: page size is too small for a FreeListLeafNode with one TSN and one PageID".to_string(),
1662                    //     ));
1663                    // }
1664                    if verbose {
1665                        println!(
1666                            "Created new leaf {:?} (new last TSN): {:?}",
1667                            new_leaf_page_id, new_leaf_page.node
1668                        );
1669                    }
1670                    self.insert_dirty(new_leaf_page)?;
1671                    split_info = Some((tsn, new_leaf_page_id));
1672                }
1673            }
1674        } else {
1675            return Err(DcbError::DatabaseCorrupted(
1676                "Expected FreeListLeaf node".to_string(),
1677            ));
1678        }
1679        // Propagate splits and replacements up the stack
1680        let mut current_replacement_info = replacement_info;
1681        while let Some(parent_page_id) = stack.pop() {
1682            // Make the internal page dirty
1683            let dirty_page_id = { self.get_dirty_page_id(parent_page_id)? };
1684            let parent_replacement_info: Option<(PageID, PageID)> = {
1685                if dirty_page_id != parent_page_id {
1686                    Some((parent_page_id, dirty_page_id))
1687                } else {
1688                    None
1689                }
1690            };
1691            // Get a mutable internal node....
1692            let dirty_internal_page = self.get_mut_dirty(dirty_page_id)?;
1693
1694            if let Node::FreeListInternal(dirty_internal_node) = &mut dirty_internal_page.node {
1695                if let Some((old_id, new_id)) = current_replacement_info {
1696                    dirty_internal_node.replace_last_child_id(old_id, new_id)?;
1697                    if verbose {
1698                        println!(
1699                            "Replaced {old_id:?} with {new_id:?} in {dirty_page_id:?}: {dirty_internal_node:?}"
1700                        );
1701                    }
1702                } else if verbose {
1703                    println!("Nothing to replace in {dirty_page_id:?}")
1704                }
1705            } else {
1706                return Err(DcbError::DatabaseCorrupted(
1707                    "Expected FreeListInternal node".to_string(),
1708                ));
1709            }
1710
1711            if let Some((promoted_key, promoted_page_id)) = split_info {
1712                if let Node::FreeListInternal(dirty_internal_node) = &mut dirty_internal_page.node {
1713                    // Add the promoted key and page ID
1714                    dirty_internal_node
1715                        .append_promoted_key_and_page_id(promoted_key, promoted_page_id)?;
1716
1717                    if verbose {
1718                        println!(
1719                            "Appended promoted key {promoted_key:?} and child {promoted_page_id:?} in {dirty_page_id:?}: {dirty_internal_node:?}"
1720                        );
1721                    }
1722                } else {
1723                    return Err(DcbError::DatabaseCorrupted(
1724                        "Expected FreeListInternal node".to_string(),
1725                    ));
1726                }
1727            }
1728
1729            // Check if the internal page needs splitting
1730
1731            if dirty_internal_page.calc_serialized_size() > page_size {
1732                if let Node::FreeListInternal(dirty_internal_node) = &mut dirty_internal_page.node {
1733                    if verbose {
1734                        println!("Splitting internal {dirty_page_id:?}...");
1735                    }
1736                    // Split the internal node
1737                    // Ensure we have at least 3 keys and 4 child IDs before splitting
1738                    if dirty_internal_node.keys.len() < 3 || dirty_internal_node.child_ids.len() < 4
1739                    {
1740                        return Err(DcbError::DatabaseCorrupted(
1741                            "Cannot split internal node with too few keys/children".to_string(),
1742                        ));
1743                    }
1744
1745                    // Move the right-most key to a new node. Promote the next right-most key.
1746                    let (promoted_key, new_keys, new_child_ids) =
1747                        dirty_internal_node.split_off()?;
1748
1749                    // Ensure old node maintain the B-tree invariant: n keys should have n+1 child pointers
1750                    assert_eq!(
1751                        dirty_internal_node.keys.len() + 1,
1752                        dirty_internal_node.child_ids.len()
1753                    );
1754
1755                    let new_internal_node = FreeListInternalNode {
1756                        keys: new_keys,
1757                        child_ids: new_child_ids,
1758                    };
1759
1760                    // Ensure the new node also maintains the invariant
1761                    assert_eq!(
1762                        new_internal_node.keys.len() + 1,
1763                        new_internal_node.child_ids.len()
1764                    );
1765
1766                    // Create a new internal page.
1767                    let new_internal_page_id = self.alloc_page_id();
1768                    let new_internal_page = Page::new(
1769                        new_internal_page_id,
1770                        Node::FreeListInternal(new_internal_node),
1771                    );
1772                    if verbose {
1773                        println!(
1774                            "Created internal {:?}: {:?}",
1775                            new_internal_page_id, new_internal_page.node
1776                        );
1777                    }
1778                    self.insert_dirty(new_internal_page)?;
1779
1780                    split_info = Some((promoted_key, new_internal_page_id));
1781                } else {
1782                    return Err(DcbError::DatabaseCorrupted(
1783                        "Expected FreeListInternal node".to_string(),
1784                    ));
1785                }
1786            } else {
1787                split_info = None;
1788            }
1789            current_replacement_info = parent_replacement_info;
1790        }
1791
1792        if let Some((old_id, new_id)) = current_replacement_info {
1793            if self.free_lists_tree_root_id == old_id {
1794                self.free_lists_tree_root_id = new_id;
1795                if verbose {
1796                    println!("Replaced root {old_id:?} with {new_id:?}");
1797                }
1798            } else {
1799                return Err(DcbError::RootIDMismatch(old_id.0, new_id.0));
1800            }
1801        }
1802
1803        if let Some((promoted_key, promoted_page_id)) = split_info {
1804            // Create a new root
1805            let new_internal_node = FreeListInternalNode {
1806                keys: vec![promoted_key],
1807                child_ids: vec![self.free_lists_tree_root_id, promoted_page_id],
1808            };
1809
1810            let new_root_page_id = self.alloc_page_id();
1811            let new_root_page =
1812                Page::new(new_root_page_id, Node::FreeListInternal(new_internal_node));
1813            if verbose {
1814                println!(
1815                    "Created new internal root {:?}: {:?}",
1816                    new_root_page_id, new_root_page.node
1817                );
1818            }
1819            self.insert_dirty(new_root_page)?;
1820
1821            self.free_lists_tree_root_id = new_root_page_id;
1822        }
1823
1824        Ok(())
1825    }
1826
1827    /// Insert a PageID into the TSN-subtree rooted at `root_id`, maintaining sorted order.
1828    /// Returns the root id (maybe the same or a new root if promoted).
1829    fn tsn_subtree_insert<T: MvccSnapshot>(
1830        &mut self,
1831        mvcc: &T,
1832        root_id: PageID,
1833        key: PageID,
1834        max_node_size: usize,
1835    ) -> DcbResult<PageID> {
1836        let verbose = self.verbose;
1837        let mut stack: Vec<(PageID, usize)> = Vec::new();
1838        let mut current_id = root_id;
1839        loop {
1840            let current_page_ref = self.get_page_ref(mvcc, current_id)?;
1841            match &current_page_ref.node {
1842                Node::FreeListTsnLeaf(_) => break,
1843                Node::FreeListTsnInternal(internal) => {
1844                    // Note: we never actually match Ok(idx) because inserted PageIDs are unique.
1845                    let child_idx = match internal.keys.binary_search_by(|k| k.0.cmp(&key.0)) {
1846                        Ok(idx) => idx + 1, // on equal, go right (matches existing >= loop)
1847                        Err(idx) => idx,    // first separator greater than key
1848                    };
1849                    let next_id = internal.child_ids[child_idx];
1850                    stack.push((current_id, child_idx));
1851                    current_id = next_id;
1852                }
1853                other => {
1854                    return Err(DcbError::DatabaseCorrupted(format!(
1855                        "Unexpected node type in TSN-subtree during insert: {}",
1856                        other.type_name()
1857                    )));
1858                }
1859            }
1860        }
1861
1862        // Please note, all pages will be already dirty, because all freed PageIDs for a TSN
1863        // are inserted in the same transaction, so we don't need to replace any CoW PageIDs.
1864        {
1865            let leaf_page = self.get_mut_dirty(current_id)?;
1866            let Node::FreeListTsnLeaf(ref mut leaf) = leaf_page.node else {
1867                return Err(DcbError::DatabaseCorrupted(
1868                    "Expected TSN-subtree leaf".to_string(),
1869                ));
1870            };
1871            // Binary search by key
1872            match leaf.page_ids.binary_search_by(|pid| pid.0.cmp(&key.0)) {
1873                Ok(_) => {
1874                    // Duplicate; nothing to do
1875                    if verbose {
1876                        println!("Duplicate PageID {:?} ignored in TSN-subtree", key);
1877                    }
1878                }
1879                Err(ins) => {
1880                    leaf.page_ids.insert(ins, key);
1881                    if leaf.calc_serialized_size() <= max_node_size {
1882                        return Ok(root_id);
1883                    }
1884                    // Split the leaf in half without cloning the entire vector.
1885                    let mid = leaf.page_ids.len() / 2; // left gets floor(n/2), right gets ceil(n/2)
1886                    let right_ids: Vec<PageID> = leaf.page_ids.split_off(mid);
1887                    let promoted_key = right_ids[0];
1888                    // Create right leaf page
1889                    let right_leaf_id = self.alloc_page_id();
1890                    let right_leaf_node = FreeListTsnLeafNode {
1891                        page_ids: right_ids,
1892                    };
1893                    let right_leaf_page =
1894                        Page::new(right_leaf_id, Node::FreeListTsnLeaf(right_leaf_node));
1895                    self.insert_dirty(right_leaf_page)?;
1896                    // Propagate to parents
1897                    let mut promoted: Option<(PageID, PageID)> =
1898                        Some((promoted_key, right_leaf_id));
1899                    // Walk up the path
1900                    for (parent_id, child_idx) in stack.into_iter().rev() {
1901                        if let Some((prom_key, prom_right_id)) = promoted.take() {
1902                            let parent_page = self.get_mut_dirty(parent_id)?;
1903                            let Node::FreeListTsnInternal(ref mut parent_node) = parent_page.node
1904                            else {
1905                                return Err(DcbError::DatabaseCorrupted(
1906                                    "Expected TSN-subtree internal".to_string(),
1907                                ));
1908                            };
1909
1910                            // Insert promoted key and child at child_idx
1911                            parent_node.keys.insert(child_idx, prom_key);
1912                            parent_node.child_ids.insert(child_idx + 1, prom_right_id);
1913                            if parent_node.calc_serialized_size() <= max_node_size {
1914                                // Fits; continue upward, no further promotion from this parent
1915                                current_id = parent_id;
1916                                continue;
1917                            }
1918                            // Overflow: split parent by midpoint and promote the right-min key
1919                            let total_keys = parent_node.keys.len();
1920                            debug_assert!(
1921                                total_keys >= 2,
1922                                "splitting parent with <2 keys after insert"
1923                            );
1924                            let mid = total_keys / 2; // left = 0..mid, promote = mid, right = mid+1..
1925                            let promote_up_key = parent_node.keys[mid];
1926                            // Build left side in place
1927                            let left_keys: Vec<PageID> = parent_node.keys[..mid].to_vec();
1928                            let left_child_ids: Vec<PageID> =
1929                                parent_node.child_ids[..=mid].to_vec();
1930                            // Build right side
1931                            let right_keys: Vec<PageID> = parent_node.keys[mid + 1..].to_vec();
1932                            let right_child_ids: Vec<PageID> =
1933                                parent_node.child_ids[mid + 1..].to_vec();
1934                            if right_child_ids.len() != right_keys.len() + 1 {
1935                                return Err(DcbError::DatabaseCorrupted(
1936                                    "TSN-subtree internal split produced invalid right arity"
1937                                        .to_string(),
1938                                ));
1939                            }
1940                            if left_child_ids.len() != left_keys.len() + 1 {
1941                                return Err(DcbError::DatabaseCorrupted(
1942                                    "TSN-subtree internal split produced invalid left arity"
1943                                        .to_string(),
1944                                ));
1945                            }
1946                            // Rewrite left into parent
1947                            parent_node.keys = left_keys;
1948                            parent_node.child_ids = left_child_ids;
1949                            // Create right internal node
1950                            let right_internal_id = self.alloc_page_id();
1951                            let right_internal =
1952                                crate::free_lists_tree_nodes::FreeListTsnInternalNode {
1953                                    keys: right_keys,
1954                                    child_ids: right_child_ids,
1955                                };
1956                            let right_internal_page = Page::new(
1957                                right_internal_id,
1958                                Node::FreeListTsnInternal(right_internal),
1959                            );
1960                            self.insert_dirty(right_internal_page)?;
1961                            // Set promoted to propagate upward
1962                            promoted = Some((promote_up_key, right_internal_id));
1963                        }
1964                        current_id = parent_id;
1965                    }
1966                    // If a promotion remains after processing all parents, create new root
1967                    if let Some((prom_key, prom_right_id)) = promoted.take() {
1968                        let new_root_id = self.alloc_page_id();
1969                        let left_id = current_id;
1970                        let new_root = crate::free_lists_tree_nodes::FreeListTsnInternalNode {
1971                            keys: vec![prom_key],
1972                            child_ids: vec![left_id, prom_right_id],
1973                        };
1974                        let new_root_page =
1975                            Page::new(new_root_id, Node::FreeListTsnInternal(new_root));
1976                        self.insert_dirty(new_root_page)?;
1977                        if verbose {
1978                            println!("Promoted new TSN-subtree root {:?}", new_root_id);
1979                        }
1980                        return Ok(new_root_id);
1981                    }
1982                }
1983            };
1984            Ok(root_id)
1985        }
1986    }
1987
1988    pub fn remove_free_page_id<T: MvccSnapshot>(
1989        &mut self,
1990        mvcc: &T,
1991        tsn: Tsn,
1992        used_page_id: PageID,
1993    ) -> DcbResult<()> {
1994        let verbose = self.verbose;
1995        if verbose {
1996            println!();
1997            println!("Removing {used_page_id:?} from {tsn:?}...");
1998            println!("Root is {:?}", self.free_lists_tree_root_id);
1999        }
2000        // Get the root page
2001        let mut current_page_id = self.free_lists_tree_root_id;
2002
2003        // Traverse the tree to find a leaf node
2004        let mut stack: Vec<(PageID, usize)> = Vec::new();
2005        let mut removed_page_ids: Vec<PageID> = Vec::new();
2006
2007        loop {
2008            let current_page_ref = self.get_page_ref(mvcc, current_page_id)?;
2009            if matches!(current_page_ref.node, Node::FreeListLeaf(_)) {
2010                break;
2011            }
2012            if let Node::FreeListInternal(internal_node) = &current_page_ref.node {
2013                if verbose {
2014                    println!("Page {:?} is internal node", current_page_ref.page_id);
2015                }
2016                let mut child_idx = 0;
2017                while child_idx < internal_node.keys.len() && tsn >= internal_node.keys[child_idx] {
2018                    child_idx += 1;
2019                }
2020                stack.push((current_page_id, child_idx));
2021                current_page_id = internal_node.child_ids[child_idx];
2022            } else {
2023                return Err(DcbError::DatabaseCorrupted(
2024                    "Expected FreeListInternal node".to_string(),
2025                ));
2026            }
2027        }
2028        if verbose {
2029            println!("Page {current_page_id:?} is leaf node");
2030        }
2031
2032        // We'll defer making the main leaf page dirty until we know we need to mutate it,
2033        // to avoid overlapping mutable borrows when also mutating the TSN-subtree.
2034        let mut replacement_info: Option<(PageID, PageID)> = None;
2035        let mut removal_info = None;
2036
2037        // Read the current leaf immutably to decide the path (inline vs TSN-subtree)
2038        let leaf_snapshot = { self.get_page_ref(mvcc, current_page_id)? };
2039        let Node::FreeListLeaf(leaf_node_ro) = &leaf_snapshot.node else {
2040            return Err(DcbError::DatabaseCorrupted(
2041                "Expected FreeListLeaf node".to_string(),
2042            ));
2043        };
2044
2045        // Find the index of the TSN in the leaf node
2046        let leaf_idx = leaf_node_ro
2047            .keys
2048            .iter()
2049            .position(|&k| k == tsn)
2050            .ok_or_else(|| {
2051                DcbError::DatabaseCorrupted(format!(
2052                    "Expected TSN {} not found in leaf: {:?}",
2053                    tsn.0, leaf_node_ro
2054                ))
2055            })?;
2056        let leaf_value_root_id = leaf_node_ro.values[leaf_idx].root_id;
2057
2058        // let mut leaf_inline_page_ids: Option<Vec<PageID>> = None;
2059        // if leaf_value_root_id == PageID(0) {
2060        //     leaf_inline_page_ids = Some(leaf_node_ro.values[0].page_ids.clone());
2061        // }
2062
2063        if leaf_value_root_id == PageID(0) {
2064            // Inline list case: make the leaf dirty and remove from inline list
2065            let dirty_page_id = { self.get_dirty_page_id(current_page_id)? };
2066            if dirty_page_id != current_page_id {
2067                replacement_info = Some((current_page_id, dirty_page_id));
2068            }
2069            let dirty_leaf_page = self.get_mut_dirty(dirty_page_id)?;
2070            if let Node::FreeListLeaf(dirty_leaf_node) = &mut dirty_leaf_page.node {
2071                let leaf_value = &mut dirty_leaf_node.values[leaf_idx];
2072                if let Some(pos) = leaf_value
2073                    .page_ids
2074                    .iter()
2075                    .position(|&id| id == used_page_id)
2076                {
2077                    leaf_value.page_ids.remove(pos);
2078                } else {
2079                    return Err(DcbError::DatabaseCorrupted(format!(
2080                        "{used_page_id:?} not found in {tsn:?}"
2081                    )));
2082                }
2083                if verbose {
2084                    println!("Removed {used_page_id:?} from {tsn:?} in {dirty_page_id:?}");
2085                }
2086                if leaf_value.page_ids.is_empty() {
2087                    dirty_leaf_node.keys.remove(leaf_idx);
2088                    dirty_leaf_node.values.remove(leaf_idx);
2089                    if verbose {
2090                        println!("Removed {tsn:?} from {dirty_page_id:?}");
2091                    }
2092                    if dirty_leaf_node.keys.is_empty() {
2093                        if verbose {
2094                            println!("Empty leaf page {dirty_page_id:?}: {dirty_leaf_node:?}");
2095                        }
2096                        removal_info = Some(dirty_page_id);
2097                    } else if verbose {
2098                        println!("Leaf page not empty {dirty_page_id:?}: {dirty_leaf_node:?}");
2099                    }
2100                } else if verbose {
2101                    println!("Leaf value not empty {tsn:?}: {leaf_value:?}");
2102                }
2103            } else {
2104                return Err(DcbError::DatabaseCorrupted(
2105                    "Expected FreeListLeaf node".to_string(),
2106                ));
2107            }
2108        } else {
2109            // TSN-subtree case: mutate the TSN leaf first
2110            let tsn_root_id = leaf_value_root_id;
2111            // Ensure we have a deserialized page to make dirty.
2112            // - unusually here we first make pages dirty and then change them
2113            let _ = self.get_page_ref(mvcc, tsn_root_id);
2114            let dirty_tsn_root_id = self.get_dirty_page_id(tsn_root_id)?;
2115            let mut tsn_root_replaced: Option<PageID> = None;
2116            let dirty_tsn_root_page = self.get_mut_dirty(dirty_tsn_root_id)?;
2117            let mut tsn_leaf_became_empty = false;
2118            let mut tsn_child_leaf_became_empty = false;
2119            match &mut dirty_tsn_root_page.node {
2120                Node::FreeListTsnLeaf(tsn_leaf_node) => {
2121                    if let Some(pos) = tsn_leaf_node
2122                        .page_ids
2123                        .iter()
2124                        .position(|&id| id == used_page_id)
2125                    {
2126                        tsn_leaf_node.page_ids.remove(pos);
2127                    } else {
2128                        return Err(DcbError::DatabaseCorrupted(format!(
2129                            "{used_page_id:?} not found in TSN-subtree for {tsn:?}"
2130                        )));
2131                    }
2132                    if verbose {
2133                        println!(
2134                            "Removed {used_page_id:?} from TSN-subtree leaf {dirty_tsn_root_id:?} for {tsn:?}"
2135                        );
2136                    }
2137                    if tsn_leaf_node.page_ids.is_empty() {
2138                        tsn_leaf_became_empty = true;
2139                        removed_page_ids.push(dirty_tsn_root_id);
2140                    }
2141                }
2142                Node::FreeListTsnInternal(_) => {
2143                    // General TSN-subtree removal with arbitrary depth. We will:
2144                    // 1) Descend using separator keys to locate the target leaf containing used_page_id.
2145                    // 2) Make a copy-on-write path from root to that leaf, updating parent->child links
2146                    //    if any node gets a new dirty page id.
2147                    // 3) Remove the page id from the leaf. If the leaf becomes empty, remove the child
2148                    //    from its parent, adjust separator keys, and if the internal ends up with a
2149                    //    single child, promote that child. Propagate promotions up as needed.
2150
2151                    // Build the path of (internal_id, child_index_chosen) down to the leaf.
2152                    let mut path: Vec<(PageID, usize)> = Vec::new();
2153                    let mut current_id = dirty_tsn_root_id;
2154                    loop {
2155                        let node_owned = { self.get_page_ref(mvcc, current_id)?.node.clone() };
2156                        match node_owned {
2157                            Node::FreeListTsnLeaf(_) => {
2158                                break; // current_id is the leaf
2159                            }
2160                            Node::FreeListTsnInternal(internal) => {
2161                                // Choose child index by separator keys: count keys <= used_page_id
2162                                let mut child_idx = 0usize;
2163                                while child_idx < internal.keys.len()
2164                                    && used_page_id >= internal.keys[child_idx]
2165                                {
2166                                    child_idx += 1;
2167                                }
2168                                let next_id = internal.child_ids[child_idx];
2169                                path.push((current_id, child_idx));
2170                                current_id = next_id;
2171                            }
2172                            other => {
2173                                return Err(DcbError::DatabaseCorrupted(format!(
2174                                    "Unexpected node type in TSN-subtree during descent: {}",
2175                                    other.type_name()
2176                                )));
2177                            }
2178                        }
2179                    }
2180
2181                    // Now current_id points to the target leaf. Make it dirty and remove the page id.
2182                    let mut dirty_child_id = { self.get_dirty_page_id(current_id)? };
2183                    {
2184                        let child_page = self.get_mut_dirty(dirty_child_id)?;
2185                        match &mut child_page.node {
2186                            Node::FreeListTsnLeaf(leaf_node) => {
2187                                if let Some(pos) =
2188                                    leaf_node.page_ids.iter().position(|&id| id == used_page_id)
2189                                {
2190                                    leaf_node.page_ids.remove(pos);
2191                                } else {
2192                                    return Err(DcbError::DatabaseCorrupted(format!(
2193                                        "{used_page_id:?} not found in TSN-subtree for {tsn:?}"
2194                                    )));
2195                                }
2196                                if verbose {
2197                                    println!(
2198                                        "Removed {used_page_id:?} from TSN-subtree leaf {dirty_child_id:?} for {tsn:?}"
2199                                    );
2200                                }
2201                                if leaf_node.page_ids.is_empty() {
2202                                    tsn_child_leaf_became_empty = true;
2203                                    removed_page_ids.push(dirty_child_id);
2204                                }
2205                            }
2206                            other => {
2207                                return Err(DcbError::DatabaseCorrupted(format!(
2208                                    "Expected TSN-subtree leaf, got {}",
2209                                    other.type_name()
2210                                )));
2211                            }
2212                        }
2213                    }
2214
2215                    // Walk back up the path, ensuring parents are dirty and applying updates.
2216                    let mut subtree_emptied = false;
2217                    let mut new_root_id_opt: Option<PageID> = None;
2218
2219                    let path_len = path.len();
2220                    for (level, (parent_id, child_idx)) in path.into_iter().rev().enumerate() {
2221                        // Make parent dirty (COW) if needed
2222                        let parent_dirty_id = { self.get_dirty_page_id(parent_id)? };
2223
2224                        // If parent was COW-ed, its own parent (next iteration) must update pointer to it.
2225                        // We achieve this by propagating parent_dirty_id via dirty_child_id variable at end.
2226
2227                        // Mutate the parent
2228                        let parent_page = self.get_mut_dirty(parent_dirty_id)?;
2229                        let Node::FreeListTsnInternal(ref mut parent_node) = parent_page.node
2230                        else {
2231                            return Err(DcbError::DatabaseCorrupted(
2232                                "Expected TSN-subtree internal node".to_string(),
2233                            ));
2234                        };
2235
2236                        if tsn_child_leaf_became_empty && level == 0 {
2237                            // Remove the empty leaf child from this parent
2238                            parent_node.child_ids.remove(child_idx);
2239                            if !parent_node.keys.is_empty() {
2240                                let key_remove_idx = if child_idx == 0 { 0 } else { child_idx - 1 };
2241                                if key_remove_idx < parent_node.keys.len() {
2242                                    parent_node.keys.remove(key_remove_idx);
2243                                }
2244                            }
2245
2246                            // After removal, decide on collapse/promotion
2247                            match parent_node.child_ids.len() {
2248                                0 => {
2249                                    // Whole TSN-subtree emptied
2250                                    subtree_emptied = true;
2251                                    removed_page_ids.push(parent_dirty_id);
2252                                }
2253                                1 => {
2254                                    // Promote sole remaining child
2255                                    let remaining_child = parent_node.child_ids[0];
2256                                    removed_page_ids.push(parent_dirty_id);
2257                                    // For upper level (or main leaf if this was the root), this node is replaced by remaining_child
2258                                    dirty_child_id = remaining_child;
2259                                    new_root_id_opt = Some(remaining_child);
2260                                }
2261                                _ => {
2262                                    // Parent remains; propagate its (possibly COW-ed) id upward
2263                                    dirty_child_id = parent_dirty_id;
2264                                    if level == path_len - 1 {
2265                                        // If this was the root parent (topmost), remember it as new root when applicable
2266                                        new_root_id_opt = Some(parent_dirty_id);
2267                                    }
2268                                }
2269                            }
2270                        } else {
2271                            // Child was not removed; update the pointer if it changed due to COW
2272                            if parent_node.child_ids[child_idx] != dirty_child_id {
2273                                parent_node.child_ids[child_idx] = dirty_child_id;
2274                            }
2275                            // Propagate upward: the current parent may itself have been COW-ed
2276                            dirty_child_id = parent_dirty_id;
2277                            if level == path_len - 1 {
2278                                new_root_id_opt = Some(parent_dirty_id);
2279                            }
2280                        }
2281                    }
2282
2283                    // Determine if the TSN-subtree root changed. Prefer promotion result if set; otherwise, if
2284                    // root was COW-ed or updated, use new_root_id_opt.
2285                    if subtree_emptied {
2286                        tsn_leaf_became_empty = true;
2287                    } else if let Some(new_root) = new_root_id_opt
2288                        && new_root != dirty_tsn_root_id
2289                    {
2290                        tsn_root_replaced = Some(new_root);
2291                    }
2292                }
2293                _ => {
2294                    return Err(DcbError::DatabaseCorrupted(
2295                        "Expected TSN-subtree node".to_string(),
2296                    ));
2297                }
2298            }
2299
2300            // Now mutate the main leaf as needed
2301            let dirty_page_id = { self.get_dirty_page_id(current_page_id)? };
2302            if dirty_page_id != current_page_id {
2303                replacement_info = Some((current_page_id, dirty_page_id));
2304            }
2305            let dirty_leaf_page = self.get_mut_dirty(dirty_page_id)?;
2306            if let Node::FreeListLeaf(dirty_leaf_node) = &mut dirty_leaf_page.node {
2307                // Ensure expected TSN still at index 'leaf_idx'
2308                if dirty_leaf_node.keys.is_empty() || dirty_leaf_node.keys[leaf_idx] != tsn {
2309                    return Err(DcbError::DatabaseCorrupted(format!(
2310                        "Expected TSN {} not found in dirty leaf: {:?}",
2311                        tsn.0, dirty_leaf_node
2312                    )));
2313                }
2314                if tsn_leaf_became_empty {
2315                    // Remove the TSN entry entirely
2316                    dirty_leaf_node.keys.remove(leaf_idx);
2317                    dirty_leaf_node.values.remove(leaf_idx);
2318                    if verbose {
2319                        println!("Removed {tsn:?} from {dirty_page_id:?}");
2320                    }
2321                    if dirty_leaf_node.keys.is_empty() {
2322                        if verbose {
2323                            println!("Empty leaf page {dirty_page_id:?}: {dirty_leaf_node:?}");
2324                        }
2325                        removal_info = Some(dirty_page_id);
2326                    } else if verbose {
2327                        println!("Leaf page not empty {dirty_page_id:?}: {dirty_leaf_node:?}");
2328                    }
2329                } else if let Some(new_root) = tsn_root_replaced {
2330                    // TSN-subtree root changed (internal collapsed to single child)
2331                    dirty_leaf_node.values[leaf_idx].root_id = new_root;
2332                } else if dirty_tsn_root_id != tsn_root_id {
2333                    // Update the pointer to the new dirty TSN leaf (COW of root leaf)
2334                    dirty_leaf_node.values[leaf_idx].root_id = dirty_tsn_root_id;
2335                }
2336            } else {
2337                return Err(DcbError::DatabaseCorrupted(
2338                    "Expected FreeListLeaf node".to_string(),
2339                ));
2340            }
2341        }
2342
2343        // Propagate replacements and removals up the stack
2344        let mut current_replacement_info = replacement_info;
2345
2346        while let Some((parent_page_id, child_idx)) = stack.pop() {
2347            // Make the internal page dirty
2348            let dirty_page_id = { self.get_dirty_page_id(parent_page_id)? };
2349            let parent_replacement_info: Option<(PageID, PageID)> = {
2350                if dirty_page_id != parent_page_id {
2351                    Some((parent_page_id, dirty_page_id))
2352                } else {
2353                    None
2354                }
2355            };
2356            // Get a mutable internal node....
2357            let dirty_internal_page = self.get_mut_dirty(dirty_page_id)?;
2358
2359            if let Some((old_id, new_id)) = current_replacement_info {
2360                if let Node::FreeListInternal(dirty_internal_node) = &mut dirty_internal_page.node {
2361                    // Replace the child ID
2362                    if dirty_internal_node.child_ids[child_idx] == old_id {
2363                        dirty_internal_node.child_ids[child_idx] = new_id;
2364                        if verbose {
2365                            println!(
2366                                "Replaced {old_id:?} with {new_id:?} in {dirty_page_id:?}: {dirty_internal_page:?}"
2367                            );
2368                        }
2369                    } else {
2370                        return Err(DcbError::DatabaseCorrupted("Child ID mismatch".to_string()));
2371                    }
2372                } else {
2373                    return Err(DcbError::DatabaseCorrupted(
2374                        "Expected FreeListInternal node".to_string(),
2375                    ));
2376                }
2377            }
2378            current_replacement_info = parent_replacement_info;
2379
2380            if let Some(removed_page_id) = removal_info {
2381                removed_page_ids.push(removed_page_id);
2382
2383                if let Node::FreeListInternal(dirty_internal_node) = &mut dirty_internal_page.node {
2384                    // Remove the child ID and key
2385                    if dirty_internal_node.child_ids[child_idx] != removed_page_id {
2386                        return Err(DcbError::DatabaseCorrupted("Child ID mismatch".to_string()));
2387                    }
2388
2389                    dirty_internal_node.child_ids.remove(child_idx);
2390                    let key_remove_idx = if child_idx == 0 { 0 } else { child_idx - 1 };
2391                    if key_remove_idx < dirty_internal_node.keys.len() {
2392                        dirty_internal_node.keys.remove(key_remove_idx);
2393                    }
2394
2395                    if verbose {
2396                        println!(
2397                            "Removed {removed_page_id:?} from {dirty_page_id:?}: {dirty_internal_node:?}"
2398                        );
2399                    }
2400
2401                    // If the internal node is empty or has only one child, mark it for removal
2402                    if dirty_internal_node.keys.is_empty() {
2403                        if verbose {
2404                            println!(
2405                                "Empty internal page {dirty_page_id:?}: {dirty_internal_node:?}"
2406                            );
2407                        }
2408                        assert_eq!(dirty_internal_node.child_ids.len(), 1);
2409                        let orphaned_child_id = dirty_internal_node.child_ids[0];
2410
2411                        removed_page_ids.push(dirty_page_id);
2412
2413                        if let Some((old_id, _)) = parent_replacement_info {
2414                            current_replacement_info = Some((old_id, orphaned_child_id));
2415                        } else {
2416                            current_replacement_info = Some((dirty_page_id, orphaned_child_id));
2417                        }
2418                    }
2419                } else {
2420                    return Err(DcbError::DatabaseCorrupted(
2421                        "Expected FreeListInternal node".to_string(),
2422                    ));
2423                }
2424
2425                removal_info = None;
2426            }
2427        }
2428
2429        for &removed_page_id in &removed_page_ids {
2430            self.append_freed_page_id(removed_page_id);
2431        }
2432
2433        // Update the free_lists_tree_root_id if needed (it might already have been
2434        // updated with the page ID of a dirty page.
2435        if let Some((old_id, new_id)) = current_replacement_info {
2436            if self.free_lists_tree_root_id == old_id {
2437                self.append_freed_page_id(old_id);
2438                self.free_lists_tree_root_id = new_id;
2439                if verbose {
2440                    println!("Replaced root {old_id:?} with {new_id:?}");
2441                }
2442            } else {
2443                return Err(DcbError::RootIDMismatch(old_id.0, new_id.0));
2444            }
2445        }
2446
2447        Ok(())
2448    }
2449
2450    pub fn cow_header_page(&self) -> DcbResult<Page> {
2451        let alternate_header_page_id = if self.header_page.page_id == HEADER_PAGE_ID_0 {
2452            HEADER_PAGE_ID_1
2453        } else {
2454            HEADER_PAGE_ID_0
2455        };
2456        let header_node = self.header_page.as_header_node()?;
2457        let page = Page {
2458            page_id: alternate_header_page_id,
2459            node: Node::Header(HeaderNode {
2460                tsn: self.tsn,
2461                free_lists_tree_root_id: self.free_lists_tree_root_id,
2462                events_tree_root_id: self.events_tree_root_id,
2463                tags_tree_root_id: self.tags_tree_root_id,
2464                next_page_id: self.next_page_id,
2465                next_position: self.next_position,
2466                schema_version: header_node.schema_version,
2467                tracking_tree_root_id: self.tracking_tree_root_id,
2468            }),
2469        };
2470        Ok(page)
2471    }
2472}
2473
2474enum FreePageIDInsertStrategy {
2475    PushTsnOntoFreeListLeaf,
2476    PushPageIdOntoFreeListLeaf(usize),
2477    PushPageIdOntoExistingTsnSubtree,
2478    MoveTsnToNewTsnSubtree,
2479    SplitFreeListLeaf,
2480    CreateAndPromoteFreeListLeaf,
2481}
2482
2483// Reader transaction
2484pub struct Reader {
2485    pub header_page_id: PageID,
2486    pub tsn: Tsn,
2487    pub events_tree_root_id: PageID,
2488    pub tags_tree_root_id: PageID,
2489    pub next_position: Position,
2490    pub tracking_tree_root_id: PageID,
2491    reader_tsns: Arc<ReaderTsnRegistry>,
2492}
2493
2494impl Drop for Reader {
2495    fn drop(&mut self) {
2496        // Retire this reader's snapshot TSN from the registry.
2497        self.reader_tsns.unregister(self.tsn);
2498    }
2499}
2500
2501#[cfg(test)]
2502mod tests {
2503    use super::*;
2504    use crate::free_lists_tree_nodes::FreeListLeafValue;
2505    use serial_test::serial;
2506    use tempfile::tempdir;
2507
2508    static VERBOSE: bool = false;
2509
2510    #[test]
2511    #[serial]
2512    fn test_mvcc_init() {
2513        let temp_dir = tempdir().unwrap();
2514        let db_path = temp_dir.path().join("mvcc-test.db");
2515
2516        {
2517            let db = Mvcc::new(
2518                VERBOSE,
2519                StorageOptions::default()
2520                    .db_path(db_path.clone())
2521                    .page_size(4096),
2522            )
2523            .unwrap();
2524            assert!(db.rw.pager.is_file_new);
2525        }
2526
2527        {
2528            let db = Mvcc::new(
2529                VERBOSE,
2530                StorageOptions::default()
2531                    .db_path(db_path.clone())
2532                    .page_size(4096),
2533            )
2534            .unwrap();
2535            assert!(!db.rw.pager.is_file_new);
2536        }
2537    }
2538
2539    #[test]
2540    #[serial]
2541    fn test_write_transaction_incrementing_tsn_and_alternating_header() {
2542        let temp_dir = tempdir().unwrap();
2543        let db_path = temp_dir.path().join("mvcc-test.db");
2544        let db = Mvcc::new(
2545            VERBOSE,
2546            StorageOptions::default().db_path(db_path).page_size(4096),
2547        )
2548        .unwrap();
2549
2550        {
2551            let mut writer = db.writer().unwrap();
2552            assert_eq!(Tsn(1), writer.tsn);
2553            assert_eq!(PageID(0), writer.header_page.page_id);
2554            db.commit(&mut writer).unwrap();
2555        }
2556
2557        {
2558            let mut writer = db.writer().unwrap();
2559            assert_eq!(Tsn(2), writer.tsn);
2560            assert_eq!(PageID(1), writer.header_page.page_id);
2561            db.commit(&mut writer).unwrap();
2562        }
2563
2564        {
2565            let mut writer = db.writer().unwrap();
2566            assert_eq!(Tsn(3), writer.tsn);
2567            assert_eq!(PageID(0), writer.header_page.page_id);
2568            db.commit(&mut writer).unwrap();
2569        }
2570
2571        {
2572            let mut writer = db.writer().unwrap();
2573            assert_eq!(Tsn(4), writer.tsn);
2574            assert_eq!(PageID(1), writer.header_page.page_id);
2575            db.commit(&mut writer).unwrap();
2576        }
2577
2578        {
2579            let mut writer = db.writer().unwrap();
2580            assert_eq!(Tsn(5), writer.tsn);
2581            assert_eq!(PageID(0), writer.header_page.page_id);
2582            db.commit(&mut writer).unwrap();
2583        }
2584    }
2585
2586    #[test]
2587    #[serial]
2588    fn test_read_transaction_header_and_tsn() {
2589        let temp_dir = tempdir().unwrap();
2590        let db_path = temp_dir.path().join("mvcc-test.db");
2591        let db = Mvcc::new(
2592            VERBOSE,
2593            StorageOptions::default().db_path(db_path).page_size(4096),
2594        )
2595        .unwrap();
2596
2597        // Initial reader should see TSN 0
2598        {
2599            assert_eq!(0, db.reader_tsns.live_reader_count());
2600            let reader = db.reader().unwrap();
2601            assert_eq!(1, db.reader_tsns.live_reader_count());
2602            assert_eq!(vec![Tsn(0)], db.reader_tsns.live_tsns_sorted());
2603            assert_eq!(PageID(0), reader.header_page_id);
2604            assert_eq!(Tsn(0), reader.tsn);
2605        }
2606        assert_eq!(0, db.reader_tsns.live_reader_count());
2607
2608        // Multiple nested readers
2609        {
2610            let reader1 = db.reader().unwrap();
2611            assert_eq!(vec![Tsn(0)], db.reader_tsns.live_tsns_sorted());
2612            assert_eq!(PageID(0), reader1.header_page_id);
2613            assert_eq!(Tsn(0), reader1.tsn);
2614
2615            {
2616                let reader2 = db.reader().unwrap();
2617                assert_eq!(vec![Tsn(0), Tsn(0)], db.reader_tsns.live_tsns_sorted());
2618                assert_eq!(PageID(0), reader2.header_page_id);
2619                assert_eq!(Tsn(0), reader2.tsn);
2620
2621                {
2622                    let reader3 = db.reader().unwrap();
2623                    assert_eq!(
2624                        vec![Tsn(0), Tsn(0), Tsn(0)],
2625                        db.reader_tsns.live_tsns_sorted()
2626                    );
2627                    assert_eq!(PageID(0), reader3.header_page_id);
2628                    assert_eq!(Tsn(0), reader3.tsn);
2629                }
2630            }
2631        }
2632        assert_eq!(0, db.reader_tsns.live_reader_count());
2633
2634        // Writer transaction
2635        {
2636            let mut writer = db.writer().unwrap();
2637            assert_eq!(0, db.reader_tsns.live_reader_count());
2638            assert_eq!(Tsn(1), writer.tsn);
2639            assert_eq!(PageID(0), writer.header_page.page_id);
2640            db.commit(&mut writer).unwrap();
2641        }
2642
2643        // Reader after writer
2644        {
2645            let reader = db.reader().unwrap();
2646            assert_eq!(vec![Tsn(1)], db.reader_tsns.live_tsns_sorted());
2647            assert_eq!(PageID(1), reader.header_page_id);
2648            assert_eq!(Tsn(1), reader.tsn);
2649        }
2650    }
2651
2652    #[test]
2653    #[serial]
2654    fn test_copy_on_write_page_reuse() {
2655        let temp_dir = tempdir().unwrap();
2656        let db_path = temp_dir.path().join("mvcc-test.db");
2657        let db = Mvcc::new(
2658            VERBOSE,
2659            StorageOptions::default().db_path(db_path).page_size(4096),
2660        )
2661        .unwrap();
2662        // First transaction
2663        {
2664            let mut writer = db.writer().unwrap();
2665
2666            // Check there are no free pages
2667            assert_eq!(0, writer.reusable_page_ids.len());
2668
2669            // Check the free list root is page 2
2670            assert_eq!(PageID(2), writer.free_lists_tree_root_id);
2671
2672            // Check the position root is page 3
2673            assert_eq!(PageID(3), writer.events_tree_root_id);
2674
2675            // Allocate and insert free page ID.
2676            let free_page_id = writer.alloc_page_id();
2677            assert_eq!(PageID(5), free_page_id);
2678            writer
2679                .insert_freed_page_id(
2680                    &db,
2681                    writer.tsn,
2682                    free_page_id,
2683                    db.max_node_size,
2684                    db.page_size,
2685                )
2686                .unwrap();
2687
2688            // Check the dirty page IDs
2689            assert_eq!(1, writer.dirty.len());
2690            assert_eq!(PageID(6), *writer.dirty.keys().collect::<Vec<_>>()[0]);
2691
2692            // Check the freed page IDs
2693            assert_eq!(1, writer.freed_page_ids.len());
2694            assert!(writer.freed_page_ids.contains(&PageID(2)));
2695
2696            db.commit(&mut writer).unwrap();
2697        }
2698
2699        // Second transaction
2700        {
2701            let mut writer = db.writer().unwrap();
2702
2703            // Check there are two free pages
2704            assert_eq!(2, writer.reusable_page_ids.len());
2705            assert_eq!((PageID(2), Tsn(1)), writer.reusable_page_ids[0]);
2706            assert_eq!((PageID(5), Tsn(1)), writer.reusable_page_ids[1]);
2707
2708            // Check the free list root is page 2
2709            assert_eq!(PageID(6), writer.free_lists_tree_root_id);
2710
2711            // Check the position root is page 3
2712            assert_eq!(PageID(3), writer.events_tree_root_id);
2713
2714            // Allocate and insert free page ID.
2715            let free_page_id = writer.alloc_page_id();
2716            assert_eq!(PageID(2), free_page_id);
2717            writer
2718                .insert_freed_page_id(
2719                    &db,
2720                    writer.tsn,
2721                    free_page_id,
2722                    db.max_node_size,
2723                    db.page_size,
2724                )
2725                .unwrap();
2726
2727            // Check the dirty page IDs
2728            assert_eq!(1, writer.dirty.len());
2729            assert_eq!(PageID(5), *writer.dirty.keys().collect::<Vec<_>>()[0]);
2730
2731            // Check the freed page IDs
2732            assert_eq!(1, writer.freed_page_ids.len());
2733            assert!(writer.freed_page_ids.contains(&PageID(6)));
2734
2735            db.commit(&mut writer).unwrap();
2736        }
2737
2738        // Third transaction
2739        {
2740            let mut writer = db.writer().unwrap();
2741
2742            // Check there are two free pages
2743            assert_eq!(2, writer.reusable_page_ids.len());
2744            assert_eq!((PageID(2), Tsn(2)), writer.reusable_page_ids[0]);
2745            assert_eq!((PageID(6), Tsn(2)), writer.reusable_page_ids[1]);
2746
2747            // Check the free list root is page 2
2748            assert_eq!(PageID(5), writer.free_lists_tree_root_id);
2749
2750            // Check the position root is page 3
2751            assert_eq!(PageID(3), writer.events_tree_root_id);
2752
2753            // Allocate and insert free page ID.
2754            let free_page_id = writer.alloc_page_id();
2755            assert_eq!(PageID(2), free_page_id);
2756            writer
2757                .insert_freed_page_id(
2758                    &db,
2759                    writer.tsn,
2760                    free_page_id,
2761                    db.max_node_size,
2762                    db.page_size,
2763                )
2764                .unwrap();
2765
2766            // Check the dirty page IDs
2767            assert_eq!(1, writer.dirty.len());
2768            assert_eq!(PageID(6), *writer.dirty.keys().collect::<Vec<_>>()[0]);
2769
2770            // Check the freed page IDs
2771            assert_eq!(1, writer.freed_page_ids.len());
2772            assert!(writer.freed_page_ids.contains(&PageID(5)));
2773
2774            db.commit(&mut writer).unwrap();
2775        }
2776    }
2777
2778    // FreeListTree tests
2779    mod free_list_tree_tests {
2780        use super::*;
2781        use serial_test::serial;
2782        use tempfile::tempdir;
2783
2784        // Helper function to create a test database with a specified page size
2785        fn construct_mvcc(page_size: usize) -> (tempfile::TempDir, Mvcc) {
2786            let temp_dir = tempdir().unwrap();
2787            let db_path = temp_dir.path().join("mvcc-test.db");
2788            let db = Mvcc::new(
2789                VERBOSE,
2790                StorageOptions::default()
2791                    .db_path(db_path)
2792                    .page_size(page_size),
2793            )
2794            .unwrap();
2795            (temp_dir, db)
2796        }
2797
2798        #[test]
2799        #[serial]
2800        fn test_find_reusable_page_ids_empty_no_entries() {
2801            let (_temp_dir, db) = construct_mvcc(64);
2802            // New writer invokes find_reusable_page_ids in Mvcc::writer
2803            let writer = db.writer().unwrap();
2804            assert_eq!(0, writer.reusable_page_ids.len());
2805        }
2806
2807        #[test]
2808        #[serial]
2809        fn test_find_reusable_page_ids_leaf() {
2810            let (_temp_dir, db) = construct_mvcc(64);
2811            let mut writer = db.writer().unwrap();
2812
2813            let (tsn, free_pid1, free_pid2) = build_free_list_tree_leaf(&mut writer);
2814
2815            // Recompute
2816            writer.find_reusable_page_ids(&db).unwrap();
2817            assert_eq!(2, writer.reusable_page_ids.len());
2818            assert_eq!((free_pid1, tsn), writer.reusable_page_ids[0]);
2819            assert_eq!((free_pid2, tsn), writer.reusable_page_ids[1]);
2820        }
2821
2822        #[test]
2823        #[serial]
2824        fn test_find_reusable_page_ids_internal_leaf() {
2825            let (_temp_dir, db) = construct_mvcc(128);
2826            let mut writer = db.writer().unwrap();
2827
2828            let (tsn1, tsn2, pid1, pid2, pid3, pid4) =
2829                build_free_list_tree_internal_leaf(&mut writer);
2830
2831            // Recompute
2832            writer.find_reusable_page_ids(&db).unwrap();
2833            // Expect entries from leaf1 then leaf2
2834            assert_eq!(4, writer.reusable_page_ids.len());
2835            assert_eq!((pid1, tsn1), writer.reusable_page_ids[0]);
2836            assert_eq!((pid2, tsn1), writer.reusable_page_ids[1]);
2837            assert_eq!((pid3, tsn2), writer.reusable_page_ids[2]);
2838            assert_eq!((pid4, tsn2), writer.reusable_page_ids[3]);
2839        }
2840
2841        #[test]
2842        #[serial]
2843        fn test_find_reusable_page_ids_internal_internal_leaf() {
2844            let (_temp_dir, db) = construct_mvcc(128);
2845            let mut writer = db.writer().unwrap();
2846
2847            let (tsn1, tsn2, tsn3, tsn4, pid1, pid2, pid3, pid4, pid5, pid6, pid7, pid8) =
2848                build_free_list_tree_internal_internal_leaf(&mut writer);
2849
2850            // Recompute
2851            writer.find_reusable_page_ids(&db).unwrap();
2852            // Expect entries from leaf1 then leaf2
2853            assert_eq!(8, writer.reusable_page_ids.len());
2854            assert_eq!((pid1, tsn1), writer.reusable_page_ids[0]);
2855            assert_eq!((pid2, tsn1), writer.reusable_page_ids[1]);
2856            assert_eq!((pid3, tsn2), writer.reusable_page_ids[2]);
2857            assert_eq!((pid4, tsn2), writer.reusable_page_ids[3]);
2858            assert_eq!((pid5, tsn3), writer.reusable_page_ids[4]);
2859            assert_eq!((pid6, tsn3), writer.reusable_page_ids[5]);
2860            assert_eq!((pid7, tsn4), writer.reusable_page_ids[6]);
2861            assert_eq!((pid8, tsn4), writer.reusable_page_ids[7]);
2862        }
2863
2864        #[test]
2865        #[serial]
2866        fn test_find_reusable_page_ids_leaf_tsn_subtree_leaf() {
2867            let (_temp_dir, db) = construct_mvcc(64);
2868            let mut writer = db.writer().unwrap();
2869
2870            let (pid1, pid2, tsn) = build_free_list_tree_leaf_tsn_subtree_leaf(&mut writer);
2871
2872            // Recompute
2873            writer.find_reusable_page_ids(&db).unwrap();
2874            // Expect entries from leaf1 then leaf2
2875            assert_eq!(2, writer.reusable_page_ids.len());
2876            assert_eq!((pid1, tsn), writer.reusable_page_ids[0]);
2877            assert_eq!((pid2, tsn), writer.reusable_page_ids[1]);
2878        }
2879
2880        #[test]
2881        #[serial]
2882        fn test_find_reusable_page_ids_leaf_tsn_subtree_internal_leaf() {
2883            let (_temp_dir, db) = construct_mvcc(64);
2884            let mut writer = db.writer().unwrap();
2885
2886            let (pid1, pid2, pid3, pid4, tsn) =
2887                build_free_list_tree_leaf_tsn_subtree_internal_leaf(&mut writer);
2888
2889            // Recompute
2890            writer.find_reusable_page_ids(&db).unwrap();
2891            // Expect entries from leaf1 then leaf2
2892            assert_eq!(4, writer.reusable_page_ids.len());
2893            assert_eq!((pid1, tsn), writer.reusable_page_ids[0]);
2894            assert_eq!((pid2, tsn), writer.reusable_page_ids[1]);
2895            assert_eq!((pid3, tsn), writer.reusable_page_ids[2]);
2896            assert_eq!((pid4, tsn), writer.reusable_page_ids[3]);
2897        }
2898
2899        #[test]
2900        #[serial]
2901        fn test_find_reusable_page_ids_leaf_tsn_subtree_internal_internal_leaf() {
2902            let (_temp_dir, db) = construct_mvcc(64);
2903            let mut writer = db.writer().unwrap();
2904
2905            let (pid1, pid2, pid3, pid4, pid5, pid6, pid7, pid8, tsn) =
2906                build_free_list_tree_leaf_tsn_subtree_internal_internal_leaf(&mut writer);
2907
2908            // Recompute
2909            writer.find_reusable_page_ids(&db).unwrap();
2910            // Expect entries from leaf1 then leaf2
2911            assert_eq!(8, writer.reusable_page_ids.len());
2912            assert_eq!((pid1, tsn), writer.reusable_page_ids[0]);
2913            assert_eq!((pid2, tsn), writer.reusable_page_ids[1]);
2914            assert_eq!((pid3, tsn), writer.reusable_page_ids[2]);
2915            assert_eq!((pid4, tsn), writer.reusable_page_ids[3]);
2916            assert_eq!((pid5, tsn), writer.reusable_page_ids[4]);
2917            assert_eq!((pid6, tsn), writer.reusable_page_ids[5]);
2918            assert_eq!((pid7, tsn), writer.reusable_page_ids[6]);
2919            assert_eq!((pid8, tsn), writer.reusable_page_ids[7]);
2920        }
2921
2922        fn build_free_list_tree_leaf(writer: &mut Writer) -> (Tsn, PageID, PageID) {
2923            // Build a leaf node with one TSN and one PageID
2924            let tsn = Tsn(123);
2925            let free_pid1 = writer.alloc_page_id();
2926            let free_pid2 = writer.alloc_page_id();
2927            let leaf = FreeListLeafNode {
2928                keys: vec![tsn],
2929                values: vec![FreeListLeafValue {
2930                    page_ids: vec![free_pid1, free_pid2],
2931                    root_id: PageID(0),
2932                }],
2933            };
2934            let root_id = writer.alloc_page_id();
2935            let page = Page::new(root_id, Node::FreeListLeaf(leaf));
2936            writer.insert_dirty(page).unwrap();
2937            writer.append_freed_page_id(writer.free_lists_tree_root_id);
2938            writer.free_lists_tree_root_id = root_id;
2939            (tsn, free_pid1, free_pid2)
2940        }
2941
2942        fn build_free_list_tree_internal_leaf(
2943            writer: &mut Writer,
2944        ) -> (Tsn, Tsn, PageID, PageID, PageID, PageID) {
2945            // Two leaves each with one (TSN -> [PageID])
2946            let tsn1 = Tsn(10);
2947            let tsn2 = Tsn(20);
2948            let pid1 = writer.alloc_page_id();
2949            let pid2 = writer.alloc_page_id();
2950            let pid3 = writer.alloc_page_id();
2951            let pid4 = writer.alloc_page_id();
2952
2953            let leaf1_id = writer.alloc_page_id();
2954            let leaf2_id = writer.alloc_page_id();
2955            let leaf1 = FreeListLeafNode {
2956                keys: vec![tsn1],
2957                values: vec![FreeListLeafValue {
2958                    page_ids: vec![pid1, pid2],
2959                    root_id: PageID(0),
2960                }],
2961            };
2962            let leaf2 = FreeListLeafNode {
2963                keys: vec![tsn2],
2964                values: vec![FreeListLeafValue {
2965                    page_ids: vec![pid3, pid4],
2966                    root_id: PageID(0),
2967                }],
2968            };
2969            writer
2970                .insert_dirty(Page::new(leaf1_id, Node::FreeListLeaf(leaf1)))
2971                .unwrap();
2972            writer
2973                .insert_dirty(Page::new(leaf2_id, Node::FreeListLeaf(leaf2)))
2974                .unwrap();
2975
2976            // Internal root pointing to the two leaves (keys are not used by traversal here)
2977            let internal = FreeListInternalNode {
2978                keys: vec![tsn1],
2979                child_ids: vec![leaf1_id, leaf2_id],
2980            };
2981            let root_id = writer.alloc_page_id();
2982            writer
2983                .insert_dirty(Page::new(root_id, Node::FreeListInternal(internal)))
2984                .unwrap();
2985            writer.append_freed_page_id(writer.free_lists_tree_root_id);
2986            writer.free_lists_tree_root_id = root_id;
2987            (tsn1, tsn2, pid1, pid2, pid3, pid4)
2988        }
2989
2990        fn build_free_list_tree_internal_internal_leaf(
2991            writer: &mut Writer,
2992        ) -> (
2993            Tsn,
2994            Tsn,
2995            Tsn,
2996            Tsn,
2997            PageID,
2998            PageID,
2999            PageID,
3000            PageID,
3001            PageID,
3002            PageID,
3003            PageID,
3004            PageID,
3005        ) {
3006            // Two leaves each with one (TSN -> [PageID])
3007            let tsn1 = Tsn(10);
3008            let tsn2 = Tsn(20);
3009            let tsn3 = Tsn(30);
3010            let tsn4 = Tsn(40);
3011            let pid1 = writer.alloc_page_id();
3012            let pid2 = writer.alloc_page_id();
3013            let pid3 = writer.alloc_page_id();
3014            let pid4 = writer.alloc_page_id();
3015            let pid5 = writer.alloc_page_id();
3016            let pid6 = writer.alloc_page_id();
3017            let pid7 = writer.alloc_page_id();
3018            let pid8 = writer.alloc_page_id();
3019
3020            let leaf1_id = writer.alloc_page_id();
3021            let leaf2_id = writer.alloc_page_id();
3022            let leaf3_id = writer.alloc_page_id();
3023            let leaf4_id = writer.alloc_page_id();
3024            let leaf1 = FreeListLeafNode {
3025                keys: vec![tsn1],
3026                values: vec![FreeListLeafValue {
3027                    page_ids: vec![pid1, pid2],
3028                    root_id: PageID(0),
3029                }],
3030            };
3031            let leaf2 = FreeListLeafNode {
3032                keys: vec![tsn2],
3033                values: vec![FreeListLeafValue {
3034                    page_ids: vec![pid3, pid4],
3035                    root_id: PageID(0),
3036                }],
3037            };
3038            let leaf3 = FreeListLeafNode {
3039                keys: vec![tsn3],
3040                values: vec![FreeListLeafValue {
3041                    page_ids: vec![pid5, pid6],
3042                    root_id: PageID(0),
3043                }],
3044            };
3045            let leaf4 = FreeListLeafNode {
3046                keys: vec![tsn4],
3047                values: vec![FreeListLeafValue {
3048                    page_ids: vec![pid7, pid8],
3049                    root_id: PageID(0),
3050                }],
3051            };
3052            writer
3053                .insert_dirty(Page::new(leaf1_id, Node::FreeListLeaf(leaf1)))
3054                .unwrap();
3055            writer
3056                .insert_dirty(Page::new(leaf2_id, Node::FreeListLeaf(leaf2)))
3057                .unwrap();
3058            writer
3059                .insert_dirty(Page::new(leaf3_id, Node::FreeListLeaf(leaf3)))
3060                .unwrap();
3061            writer
3062                .insert_dirty(Page::new(leaf4_id, Node::FreeListLeaf(leaf4)))
3063                .unwrap();
3064
3065            // Internal root pointing to the two leaves (keys are not used by traversal here)
3066            let internal1 = FreeListInternalNode {
3067                keys: vec![tsn2],
3068                child_ids: vec![leaf1_id, leaf2_id],
3069            };
3070            let internal1_id = writer.alloc_page_id();
3071            let internal2 = FreeListInternalNode {
3072                keys: vec![tsn4],
3073                child_ids: vec![leaf3_id, leaf4_id],
3074            };
3075            let internal2_id = writer.alloc_page_id();
3076            let internal3 = FreeListInternalNode {
3077                keys: vec![tsn3],
3078                child_ids: vec![internal1_id, internal2_id],
3079            };
3080            let internal3_id = writer.alloc_page_id();
3081            writer
3082                .insert_dirty(Page::new(internal1_id, Node::FreeListInternal(internal1)))
3083                .unwrap();
3084            writer
3085                .insert_dirty(Page::new(internal2_id, Node::FreeListInternal(internal2)))
3086                .unwrap();
3087            writer
3088                .insert_dirty(Page::new(internal3_id, Node::FreeListInternal(internal3)))
3089                .unwrap();
3090            writer.append_freed_page_id(writer.free_lists_tree_root_id);
3091            writer.free_lists_tree_root_id = internal3_id;
3092            (
3093                tsn1, tsn2, tsn3, tsn4, pid1, pid2, pid3, pid4, pid5, pid6, pid7, pid8,
3094            )
3095        }
3096
3097        fn build_free_list_tree_leaf_tsn_subtree_leaf(
3098            writer: &mut Writer,
3099        ) -> (PageID, PageID, Tsn) {
3100            // Create a TSN-subtree leaf node that has two PageIDs.
3101            // - this will be the root of the subtree.
3102            let tsn_sub_leaf_id = writer.alloc_page_id();
3103            let pid1 = writer.alloc_page_id();
3104            let pid2 = writer.alloc_page_id();
3105            let tsn_sub_leaf = crate::free_lists_tree_nodes::FreeListTsnLeafNode {
3106                page_ids: vec![pid1, pid2],
3107            };
3108            // Insert it as a "dirty" page.
3109            writer
3110                .insert_dirty(Page::new(
3111                    tsn_sub_leaf_id,
3112                    Node::FreeListTsnLeaf(tsn_sub_leaf),
3113                ))
3114                .unwrap();
3115
3116            // Create a TSN tree leaf node that points to the subtree node.
3117            // - this will be the new root of the TSN tree.
3118            let tsn = Tsn(33); // the TSN the subtree has PageIDs from
3119            let leaf = FreeListLeafNode {
3120                keys: vec![tsn],
3121                values: vec![FreeListLeafValue {
3122                    page_ids: vec![],
3123                    root_id: tsn_sub_leaf_id,
3124                }],
3125            };
3126
3127            // Insert it as a "dirty" page.
3128            let root_id = writer.alloc_page_id();
3129            writer
3130                .insert_dirty(Page::new(root_id, Node::FreeListLeaf(leaf)))
3131                .unwrap();
3132
3133            // Set the old TSN root page ID free.
3134            writer.append_freed_page_id(writer.free_lists_tree_root_id);
3135            // Replace the new TSN root page ID in the writer.
3136            writer.free_lists_tree_root_id = root_id;
3137
3138            // Return the two PageIDs (in the subtree) and their TSN
3139            (pid1, pid2, tsn)
3140        }
3141
3142        fn build_free_list_tree_leaf_tsn_subtree_internal_leaf(
3143            writer: &mut Writer,
3144        ) -> (PageID, PageID, PageID, PageID, Tsn) {
3145            // Create a TSN-subtree leaf with a PageID
3146            let tsn_sub_leaf_id1 = writer.alloc_page_id();
3147            let pid1 = writer.alloc_page_id();
3148            let pid2 = writer.alloc_page_id();
3149            let tsn_sub_leaf1 = crate::free_lists_tree_nodes::FreeListTsnLeafNode {
3150                page_ids: vec![pid1, pid2],
3151            };
3152            writer
3153                .insert_dirty(Page::new(
3154                    tsn_sub_leaf_id1,
3155                    Node::FreeListTsnLeaf(tsn_sub_leaf1),
3156                ))
3157                .unwrap();
3158
3159            // Create a TSN-subtree leaf with a PageID
3160            let tsn_sub_leaf_id2 = writer.alloc_page_id();
3161            let pid3 = writer.alloc_page_id();
3162            let pid4 = writer.alloc_page_id();
3163            let tsn_sub_leaf2 = crate::free_lists_tree_nodes::FreeListTsnLeafNode {
3164                page_ids: vec![pid3, pid4],
3165            };
3166            writer
3167                .insert_dirty(Page::new(
3168                    tsn_sub_leaf_id2,
3169                    Node::FreeListTsnLeaf(tsn_sub_leaf2),
3170                ))
3171                .unwrap();
3172
3173            // Create a TSN-subtree internal node
3174            let tsn_sub_internal_id = writer.alloc_page_id();
3175            let tsn_sub_internal = crate::free_lists_tree_nodes::FreeListTsnInternalNode {
3176                keys: vec![pid3],
3177                child_ids: vec![tsn_sub_leaf_id1, tsn_sub_leaf_id2],
3178            };
3179            writer
3180                .insert_dirty(Page::new(
3181                    tsn_sub_internal_id,
3182                    Node::FreeListTsnInternal(tsn_sub_internal),
3183                ))
3184                .unwrap();
3185
3186            // Make a leaf value point to the internal node
3187            let tsn = Tsn(33);
3188            let leaf = FreeListLeafNode {
3189                keys: vec![tsn],
3190                values: vec![FreeListLeafValue {
3191                    page_ids: vec![],
3192                    root_id: tsn_sub_internal_id,
3193                }],
3194            };
3195            let root_id = writer.alloc_page_id();
3196            writer
3197                .insert_dirty(Page::new(root_id, Node::FreeListLeaf(leaf)))
3198                .unwrap();
3199            writer.append_freed_page_id(writer.free_lists_tree_root_id);
3200            writer.free_lists_tree_root_id = root_id;
3201            (pid1, pid2, pid3, pid4, tsn)
3202        }
3203
3204        fn build_free_list_tree_leaf_tsn_subtree_internal_internal_leaf(
3205            writer: &mut Writer,
3206        ) -> (
3207            PageID,
3208            PageID,
3209            PageID,
3210            PageID,
3211            PageID,
3212            PageID,
3213            PageID,
3214            PageID,
3215            Tsn,
3216        ) {
3217            // Create a TSN-subtree leaf with a PageID
3218            let tsn_sub_leaf_id1 = writer.alloc_page_id();
3219            let pid1 = writer.alloc_page_id();
3220            let pid2 = writer.alloc_page_id();
3221            let tsn_sub_leaf1 = crate::free_lists_tree_nodes::FreeListTsnLeafNode {
3222                page_ids: vec![pid1, pid2],
3223            };
3224            writer
3225                .insert_dirty(Page::new(
3226                    tsn_sub_leaf_id1,
3227                    Node::FreeListTsnLeaf(tsn_sub_leaf1),
3228                ))
3229                .unwrap();
3230
3231            // Create a TSN-subtree leaf with a PageID
3232            let tsn_sub_leaf_id2 = writer.alloc_page_id();
3233            let pid3 = writer.alloc_page_id();
3234            let pid4 = writer.alloc_page_id();
3235            let tsn_sub_leaf2 = crate::free_lists_tree_nodes::FreeListTsnLeafNode {
3236                page_ids: vec![pid3, pid4],
3237            };
3238            writer
3239                .insert_dirty(Page::new(
3240                    tsn_sub_leaf_id2,
3241                    Node::FreeListTsnLeaf(tsn_sub_leaf2),
3242                ))
3243                .unwrap();
3244
3245            // Create a TSN-subtree internal node
3246            let tsn_sub_internal_id1 = writer.alloc_page_id();
3247            let tsn_sub_internal1 = crate::free_lists_tree_nodes::FreeListTsnInternalNode {
3248                keys: vec![pid3],
3249                child_ids: vec![tsn_sub_leaf_id1, tsn_sub_leaf_id2],
3250            };
3251            writer
3252                .insert_dirty(Page::new(
3253                    tsn_sub_internal_id1,
3254                    Node::FreeListTsnInternal(tsn_sub_internal1),
3255                ))
3256                .unwrap();
3257
3258            // Create a TSN-subtree leaf with a PageID
3259            let tsn_sub_leaf_id3 = writer.alloc_page_id();
3260            let pid5 = writer.alloc_page_id();
3261            let pid6 = writer.alloc_page_id();
3262            let tsn_sub_leaf3 = crate::free_lists_tree_nodes::FreeListTsnLeafNode {
3263                page_ids: vec![pid5, pid6],
3264            };
3265            writer
3266                .insert_dirty(Page::new(
3267                    tsn_sub_leaf_id3,
3268                    Node::FreeListTsnLeaf(tsn_sub_leaf3),
3269                ))
3270                .unwrap();
3271
3272            // Create a TSN-subtree leaf with a PageID
3273            let tsn_sub_leaf_id4 = writer.alloc_page_id();
3274            let pid7 = writer.alloc_page_id();
3275            let pid8 = writer.alloc_page_id();
3276            let tsn_sub_leaf4 = crate::free_lists_tree_nodes::FreeListTsnLeafNode {
3277                page_ids: vec![pid7, pid8],
3278            };
3279            writer
3280                .insert_dirty(Page::new(
3281                    tsn_sub_leaf_id4,
3282                    Node::FreeListTsnLeaf(tsn_sub_leaf4),
3283                ))
3284                .unwrap();
3285
3286            // Create a TSN-subtree internal node
3287            let tsn_sub_internal_id2 = writer.alloc_page_id();
3288            let tsn_sub_internal2 = crate::free_lists_tree_nodes::FreeListTsnInternalNode {
3289                keys: vec![pid7],
3290                child_ids: vec![tsn_sub_leaf_id3, tsn_sub_leaf_id4],
3291            };
3292            writer
3293                .insert_dirty(Page::new(
3294                    tsn_sub_internal_id2,
3295                    Node::FreeListTsnInternal(tsn_sub_internal2),
3296                ))
3297                .unwrap();
3298
3299            // Create a TSN-subtree internal node
3300            let tsn_sub_internal_id3 = writer.alloc_page_id();
3301            let tsn_sub_internal3 = crate::free_lists_tree_nodes::FreeListTsnInternalNode {
3302                keys: vec![pid5],
3303                child_ids: vec![tsn_sub_internal_id1, tsn_sub_internal_id2],
3304            };
3305            writer
3306                .insert_dirty(Page::new(
3307                    tsn_sub_internal_id3,
3308                    Node::FreeListTsnInternal(tsn_sub_internal3),
3309                ))
3310                .unwrap();
3311
3312            // Make a leaf value point to the internal node
3313            let tsn = writer.tsn;
3314            let leaf = FreeListLeafNode {
3315                keys: vec![tsn],
3316                values: vec![FreeListLeafValue {
3317                    page_ids: vec![],
3318                    root_id: tsn_sub_internal_id3,
3319                }],
3320            };
3321            let root_id = writer.alloc_page_id();
3322            writer
3323                .insert_dirty(Page::new(root_id, Node::FreeListLeaf(leaf)))
3324                .unwrap();
3325            writer.append_freed_page_id(writer.free_lists_tree_root_id);
3326            writer.free_lists_tree_root_id = root_id;
3327            (pid1, pid2, pid3, pid4, pid5, pid6, pid7, pid8, tsn)
3328        }
3329
3330        #[test]
3331        #[serial]
3332        fn test_insert_freed_page_id_to_empty_leaf_root() {
3333            let (_temp_dir, db) = construct_mvcc(64);
3334
3335            // Get latest header
3336            let header_page = db.get_latest_header_page().unwrap();
3337            let header_node = header_page.as_header_node().unwrap();
3338            let header_page_id = header_page.page_id;
3339            assert_eq!(PageID(0), header_page_id);
3340
3341            // Get next page ID
3342            assert_eq!(PageID(5), header_node.next_page_id);
3343
3344            // Construct a writer
3345            let tsn = Tsn(1001);
3346
3347            let mut writer = Writer::new(
3348                header_page.clone(),
3349                tsn,
3350                header_node.next_page_id,
3351                header_node.free_lists_tree_root_id,
3352                header_node.events_tree_root_id,
3353                header_node.tags_tree_root_id,
3354                header_node.tracking_tree_root_id,
3355                header_node.next_position,
3356                VERBOSE,
3357                db.page_size,
3358                db.max_node_size,
3359            );
3360
3361            // Check the free list tree root ID
3362            let initial_root_id = writer.free_lists_tree_root_id;
3363            assert_eq!(PageID(2), initial_root_id);
3364
3365            // Allocate a page ID (to be inserted as "freed")
3366            let page_id = writer.alloc_page_id();
3367
3368            // Check the allocated page ID is the "next" page ID
3369            assert_eq!(header_node.next_page_id, page_id);
3370
3371            // Insert the allocated page ID in the free list tree
3372            let current_tsn = writer.tsn;
3373            writer
3374                .insert_freed_page_id(&db, current_tsn, page_id, db.max_node_size, db.page_size)
3375                .unwrap();
3376
3377            // Check the root page has been CoW-ed
3378            let expected_new_root_id = PageID(header_node.next_page_id.0 + 1);
3379            assert_eq!(expected_new_root_id, writer.free_lists_tree_root_id);
3380            assert_eq!(1, writer.dirty.len());
3381            assert!(writer.dirty.contains_key(&expected_new_root_id));
3382
3383            let new_root_page = writer.dirty.get(&expected_new_root_id).unwrap();
3384            assert_eq!(expected_new_root_id, new_root_page.page_id);
3385
3386            let freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
3387            assert_eq!(vec![initial_root_id], freed_page_ids);
3388
3389            // Check keys and values of the new root page
3390            match &new_root_page.node {
3391                Node::FreeListLeaf(node) => {
3392                    let expected_keys = vec![tsn];
3393                    assert_eq!(expected_keys, node.keys);
3394
3395                    let expected_values = vec![FreeListLeafValue {
3396                        page_ids: vec![header_node.next_page_id],
3397                        root_id: PageID(0),
3398                    }];
3399                    assert_eq!(expected_values, node.values);
3400                }
3401                _ => panic!("Expected FreeListLeaf node"),
3402            }
3403        }
3404
3405        #[test]
3406        #[serial]
3407        fn test_remove_freed_page_id_from_root_leaf_root() {
3408            let (_temp_dir, db) = construct_mvcc(64);
3409
3410            // First, insert a page ID
3411            let mut writer;
3412            let inserted_tsn;
3413            let inserted_page_id;
3414            let previous_root_id;
3415
3416            {
3417                // Get a writer
3418                writer = db.writer().unwrap();
3419
3420                // Remember the initial root ID
3421                previous_root_id = writer.free_lists_tree_root_id;
3422
3423                // Allocate a page ID
3424                inserted_page_id = writer.alloc_page_id();
3425
3426                // Insert the page ID
3427                inserted_tsn = writer.tsn;
3428                writer
3429                    .insert_freed_page_id(
3430                        &db,
3431                        inserted_tsn,
3432                        inserted_page_id,
3433                        db.max_node_size,
3434                        db.page_size,
3435                    )
3436                    .unwrap();
3437
3438                // Commit the transaction
3439                db.commit(&mut writer).unwrap();
3440            }
3441
3442            // Block inserted page IDs from being reused
3443            {
3444                db.reader_tsns.register(Tsn(0));
3445            }
3446
3447            // Start a new writer to remove inserted freed page ID
3448            {
3449                writer = db.writer().unwrap();
3450
3451                // Check there are no free pages (because we blocked them with a reader)
3452                assert_eq!(0, writer.reusable_page_ids.len());
3453
3454                // Remember the initial root ID and next page ID
3455                let initial_root_id = writer.free_lists_tree_root_id;
3456                let next_page_id = writer.next_page_id;
3457
3458                // Remove what was inserted
3459                writer
3460                    .remove_free_page_id(&db, inserted_tsn, inserted_page_id)
3461                    .unwrap();
3462
3463                // Check the root page has been CoW-ed
3464                let expected_new_root_id = next_page_id;
3465                assert_eq!(expected_new_root_id, writer.free_lists_tree_root_id);
3466                assert_eq!(1, writer.dirty.len());
3467                assert!(writer.dirty.contains_key(&expected_new_root_id));
3468
3469                let new_root_page = writer.dirty.get(&expected_new_root_id).unwrap();
3470                assert_eq!(expected_new_root_id, new_root_page.page_id);
3471
3472                let freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
3473                assert_eq!(vec![initial_root_id], freed_page_ids);
3474
3475                // Check keys and values of the new root page
3476                match &new_root_page.node {
3477                    Node::FreeListLeaf(node) => {
3478                        let expected_keys = vec![inserted_tsn];
3479                        assert_eq!(expected_keys, node.keys);
3480
3481                        let expected_values = vec![FreeListLeafValue {
3482                            page_ids: vec![previous_root_id],
3483                            root_id: PageID(0),
3484                        }];
3485                        assert_eq!(expected_values, node.values);
3486                    }
3487                    _ => panic!("Expected FreeListLeaf node"),
3488                }
3489            }
3490        }
3491
3492        #[test]
3493        #[serial]
3494        fn test_insert_freed_page_ids_until_split_leaf() {
3495            let (_temp_dir, db) = construct_mvcc(64);
3496
3497            // Get latest header
3498            let header_page = db.get_latest_header_page().unwrap();
3499            let header_node = header_page.as_header_node().unwrap();
3500
3501            // Create a writer
3502            let mut tsn = Tsn(100);
3503            let mut writer = Writer::new(
3504                header_page.clone(),
3505                Tsn(header_node.tsn.0 + 1),
3506                header_node.next_page_id,
3507                header_node.free_lists_tree_root_id,
3508                header_node.events_tree_root_id,
3509                header_node.tags_tree_root_id,
3510                header_node.tracking_tree_root_id,
3511                header_node.next_position,
3512                VERBOSE,
3513                db.page_size,
3514                db.max_node_size,
3515            );
3516
3517            let mut has_split_leaf = false;
3518            let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
3519
3520            // Insert page IDs until we split a leaf
3521            while !has_split_leaf {
3522                // Allocate and insert the first page ID
3523                let page_id1 = writer.alloc_page_id();
3524                writer
3525                    .insert_freed_page_id(&db, tsn, page_id1, db.max_node_size, db.page_size)
3526                    .unwrap();
3527                inserted.push((tsn, page_id1));
3528
3529                // Allocate and insert second page ID
3530                let page_id2 = writer.alloc_page_id();
3531                writer
3532                    .insert_freed_page_id(&db, tsn, page_id2, db.max_node_size, db.page_size)
3533                    .unwrap();
3534                inserted.push((tsn, page_id2));
3535
3536                // Increment TSN for next iteration
3537                tsn = Tsn(tsn.0 + 1);
3538
3539                // Check if we've split the leaf
3540                let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
3541                match &root_page.node {
3542                    Node::FreeListInternal(_) => {
3543                        has_split_leaf = true;
3544                    }
3545                    _ => {}
3546                }
3547            }
3548
3549            // Check keys and values of all pages
3550            let mut copy_inserted = inserted.clone();
3551
3552            // Get the root node
3553            let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
3554            let root_node = match &root_page.node {
3555                Node::FreeListInternal(node) => node,
3556                _ => panic!("Expected FreeListInternal node"),
3557            };
3558
3559            // Collect active page IDs
3560            let mut active_page_ids = vec![
3561                HEADER_PAGE_ID_0,
3562                HEADER_PAGE_ID_1,
3563                writer.free_lists_tree_root_id,
3564                writer.events_tree_root_id,
3565                writer.tags_tree_root_id,
3566            ];
3567
3568            // Collect freed page IDs
3569            let mut freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
3570
3571            // Check each child of the root
3572            for (i, &child_id) in root_node.child_ids.iter().enumerate() {
3573                active_page_ids.push(child_id);
3574
3575                let child_page = writer.dirty.get(&child_id).unwrap();
3576                assert_eq!(child_id, child_page.page_id);
3577
3578                let child_node = match &child_page.node {
3579                    Node::FreeListLeaf(node) => node,
3580                    _ => panic!("Expected FreeListLeaf node"),
3581                };
3582
3583                // Check that the keys are properly ordered
3584                if i > 0 {
3585                    assert_eq!(root_node.keys[i - 1], child_node.keys[0]);
3586                }
3587
3588                // Check each key and value in the child
3589                for (k, &key) in child_node.keys.iter().enumerate() {
3590                    for &value in &child_node.values[k].page_ids {
3591                        let (inserted_tsn, inserted_page_id) = copy_inserted.remove(0);
3592                        assert_eq!(inserted_tsn, key);
3593                        assert_eq!(inserted_page_id, value);
3594                        freed_page_ids.push(value);
3595                    }
3596                }
3597            }
3598
3599            // We just split a leaf, so now we have 6 pages
3600            assert_eq!(7, active_page_ids.len());
3601
3602            // Audit page IDs
3603            let mut all_page_ids = active_page_ids.clone();
3604            all_page_ids.extend(freed_page_ids.clone());
3605            all_page_ids.sort();
3606            all_page_ids.dedup();
3607
3608            assert_eq!(
3609                all_page_ids.len(),
3610                active_page_ids.len() + freed_page_ids.len()
3611                    - active_page_ids
3612                        .iter()
3613                        .filter(|id| freed_page_ids.contains(id))
3614                        .count()
3615            );
3616
3617            // Check that all page IDs are accounted for
3618            let expected_page_ids: Vec<PageID> = (0..writer.next_page_id.0).map(PageID).collect();
3619            assert_eq!(expected_page_ids, all_page_ids);
3620        }
3621
3622        #[test]
3623        #[serial]
3624        fn test_insert_freed_page_ids_until_replace_internal_node_child_id() {
3625            let (_temp_dir, db) = construct_mvcc(128);
3626
3627            // Block inserted page IDs from being reused
3628            {
3629                db.reader_tsns.register(Tsn(0));
3630            }
3631
3632            let mut has_split_leaf = false;
3633            let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
3634
3635            // Insert page IDs until we split a leaf
3636            while !has_split_leaf {
3637                // Create a writer
3638                let mut writer = db.writer().unwrap();
3639                // Allocate and insert the first page ID
3640                let page_id1 = writer.alloc_page_id();
3641                writer
3642                    .insert_freed_page_id(&db, writer.tsn, page_id1, db.max_node_size, db.page_size)
3643                    .unwrap();
3644                inserted.push((writer.tsn, page_id1));
3645
3646                // Check if we've split the leaf
3647                let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
3648                match &root_page.node {
3649                    Node::FreeListInternal(_) => {
3650                        has_split_leaf = true;
3651                    }
3652                    _ => {}
3653                }
3654
3655                if !has_split_leaf {
3656                    // Allocate and insert second page ID
3657                    let page_id2 = writer.alloc_page_id();
3658                    writer
3659                        .insert_freed_page_id(
3660                            &db,
3661                            writer.tsn,
3662                            page_id2,
3663                            db.max_node_size,
3664                            db.page_size,
3665                        )
3666                        .unwrap();
3667                    inserted.push((writer.tsn, page_id2));
3668
3669                    // Check if we've split the leaf
3670                    let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
3671                    match &root_page.node {
3672                        Node::FreeListInternal(_) => {
3673                            has_split_leaf = true;
3674                        }
3675                        _ => {}
3676                    }
3677                }
3678
3679                db.commit(&mut writer).unwrap();
3680            }
3681
3682            let mut writer = db.writer().unwrap();
3683            let page_id3 = writer.alloc_page_id();
3684            writer
3685                .insert_freed_page_id(&db, writer.tsn, page_id3, db.max_node_size, db.page_size)
3686                .unwrap();
3687            db.commit(&mut writer).unwrap();
3688            inserted.push((writer.tsn, page_id3));
3689
3690            writer = db.writer().unwrap();
3691            let page_id4 = writer.alloc_page_id();
3692            writer
3693                .insert_freed_page_id(&db, writer.tsn, page_id4, db.max_node_size, db.page_size)
3694                .unwrap();
3695            db.commit(&mut writer).unwrap();
3696            inserted.push((writer.tsn, page_id4));
3697
3698            // Get the root node
3699            writer = db.writer().unwrap();
3700            let root_page = db.read_page(writer.free_lists_tree_root_id).unwrap();
3701            let root_node = match &root_page.node {
3702                Node::FreeListInternal(node) => node,
3703                _ => panic!("Expected FreeListInternal node"),
3704            };
3705
3706            // Collect active page IDs
3707            let mut active_page_ids = vec![
3708                HEADER_PAGE_ID_0,
3709                HEADER_PAGE_ID_1,
3710                writer.free_lists_tree_root_id,
3711                writer.events_tree_root_id,
3712                writer.tags_tree_root_id,
3713            ];
3714
3715            // Collect freed page IDs from the writer
3716            let mut freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
3717
3718            // Collect child page IDs
3719            for (i, &child_id) in root_node.child_ids.iter().enumerate() {
3720                active_page_ids.push(child_id);
3721
3722                // Check each child page
3723                let child_page = db.read_page(child_id).unwrap();
3724                assert_eq!(child_id, child_page.page_id);
3725
3726                let child_node = match &child_page.node {
3727                    Node::FreeListLeaf(node) => node,
3728                    _ => panic!("Expected FreeListLeaf node"),
3729                };
3730
3731                // Check that the keys are properly ordered
3732                if i > 0 {
3733                    assert_eq!(root_node.keys[i - 1], child_node.keys[0]);
3734                }
3735
3736                // Collect freed page IDs from the child page values
3737                for child_value in child_node.values.clone() {
3738                    for page_id in child_value.page_ids {
3739                        freed_page_ids.push(page_id);
3740                    }
3741                }
3742            }
3743
3744            // We have split a leaf node, so now we have 8 active pages
3745            assert_eq!(8, active_page_ids.len());
3746
3747            // Audit page IDs
3748            let mut all_page_ids = active_page_ids.clone();
3749            all_page_ids.extend(freed_page_ids.clone());
3750            all_page_ids.sort();
3751            all_page_ids.dedup();
3752
3753            assert_eq!(
3754                all_page_ids.len(),
3755                active_page_ids.len() + freed_page_ids.len()
3756                    - active_page_ids
3757                        .iter()
3758                        .filter(|id| freed_page_ids.contains(id))
3759                        .count()
3760            );
3761
3762            // Check that all page IDs are accounted for
3763            let expected_page_ids: Vec<PageID> = (0..writer.next_page_id.0).map(PageID).collect();
3764            assert_eq!(expected_page_ids, all_page_ids);
3765        }
3766
3767        #[test]
3768        #[serial]
3769        fn test_remove_freed_page_ids_from_split_leaf() {
3770            let (_temp_dir, db) = construct_mvcc(128);
3771
3772            // First, insert page IDs until we split a leaf
3773            if VERBOSE {
3774                println!("Inserting page IDs......");
3775            }
3776            let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
3777            let previous_root_id;
3778            let previous_writer_tsn;
3779
3780            {
3781                // Get a writer
3782                let mut writer = db.writer().unwrap();
3783
3784                // Remember the initial root ID
3785                previous_root_id = writer.free_lists_tree_root_id;
3786
3787                // Insert page IDs until we split a leaf
3788                let mut has_split_leaf = false;
3789                let mut tsn = writer.tsn;
3790
3791                while !has_split_leaf {
3792                    // Increment TSN
3793                    tsn = Tsn(tsn.0 + 1);
3794
3795                    // Allocate and insert the first page ID
3796                    let page_id1 = writer.alloc_page_id();
3797                    writer
3798                        .insert_freed_page_id(&db, tsn, page_id1, db.max_node_size, db.page_size)
3799                        .unwrap();
3800                    inserted.push((tsn, page_id1));
3801
3802                    // Allocate and insert second page ID
3803                    let page_id2 = writer.alloc_page_id();
3804                    writer
3805                        .insert_freed_page_id(&db, tsn, page_id2, db.max_node_size, db.page_size)
3806                        .unwrap();
3807                    inserted.push((tsn, page_id2));
3808
3809                    // Check if we've split the leaf
3810                    let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
3811                    match &root_page.node {
3812                        Node::FreeListInternal(_) => {
3813                            has_split_leaf = true;
3814                        }
3815                        _ => {}
3816                    }
3817                }
3818
3819                // Remember the final TSN
3820                writer.tsn = Tsn(tsn.0 + 1);
3821                previous_writer_tsn = writer.tsn;
3822
3823                // Commit the transaction
3824                db.commit(&mut writer).unwrap();
3825            }
3826
3827            // Now remove all the inserted freed page IDs
3828            if VERBOSE {
3829                println!();
3830                println!("Removing all inserted page IDs......");
3831            }
3832
3833            {
3834                // Get latest header
3835                let header_page = db.get_latest_header_page().unwrap();
3836                let header_node = header_page.as_header_node().unwrap();
3837
3838                // Create a new writer
3839                let mut writer = Writer::new(
3840                    header_page.clone(),
3841                    Tsn(header_node.tsn.0 + 1),
3842                    header_node.next_page_id,
3843                    header_node.free_lists_tree_root_id,
3844                    header_node.events_tree_root_id,
3845                    header_node.tags_tree_root_id,
3846                    header_node.tracking_tree_root_id,
3847                    header_node.next_position,
3848                    VERBOSE,
3849                    db.page_size,
3850                    db.max_node_size,
3851                );
3852
3853                // Remember the initial root ID
3854                let old_root_id = writer.free_lists_tree_root_id;
3855
3856                // Remove all inserted page IDs
3857                for (tsn, page_id) in inserted.iter() {
3858                    writer.remove_free_page_id(&db, *tsn, *page_id).unwrap();
3859                    if VERBOSE {
3860                        println!("Dirty pages: {:?}", writer.dirty.keys());
3861                    }
3862                }
3863
3864                // Check the root page has been CoW-ed
3865                assert_ne!(old_root_id, writer.free_lists_tree_root_id);
3866
3867                assert_eq!(1, writer.dirty.len());
3868                assert!(writer.dirty.contains_key(&writer.free_lists_tree_root_id));
3869
3870                let new_root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
3871                assert_eq!(writer.free_lists_tree_root_id, new_root_page.page_id);
3872
3873                // Check old root ID is in freed page IDs
3874                let freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
3875                assert!(freed_page_ids.contains(&old_root_id));
3876
3877                // There were three pages, and now we have one. We have
3878                // freed page IDs for three old pages and two CoW pages.
3879                assert_eq!(5, writer.freed_page_ids.len());
3880
3881                // Check keys and values of the new root page
3882                match &new_root_page.node {
3883                    Node::FreeListLeaf(node) => {
3884                        let expected_keys = vec![previous_writer_tsn];
3885                        assert_eq!(expected_keys, node.keys);
3886
3887                        let expected_values = vec![FreeListLeafValue {
3888                            page_ids: vec![previous_root_id],
3889                            root_id: PageID(0),
3890                        }];
3891                        assert_eq!(expected_values, node.values);
3892                    }
3893                    _ => panic!("Expected FreeListLeaf node"),
3894                }
3895
3896                // Audit page IDs
3897                let active_page_ids = vec![
3898                    HEADER_PAGE_ID_0,
3899                    HEADER_PAGE_ID_1,
3900                    writer.free_lists_tree_root_id,
3901                    writer.events_tree_root_id,
3902                    writer.tags_tree_root_id,
3903                ];
3904
3905                // Collect all freed page IDs
3906                let mut all_freed_page_ids = freed_page_ids.clone();
3907
3908                // Add page IDs from the leaf node
3909                match &new_root_page.node {
3910                    Node::FreeListLeaf(node) => {
3911                        for (_, value) in node.keys.iter().zip(node.values.iter()) {
3912                            all_freed_page_ids.extend(value.page_ids.clone());
3913                        }
3914                    }
3915                    _ => panic!("Expected FreeListLeaf node"),
3916                }
3917
3918                // Add inserted page IDs
3919                let inserted_page_ids: Vec<PageID> = inserted.iter().map(|(_, id)| *id).collect();
3920
3921                // Collect all page IDs
3922                let mut all_page_ids = active_page_ids.clone();
3923                all_page_ids.extend(all_freed_page_ids.clone());
3924                all_page_ids.extend(inserted_page_ids.clone());
3925                all_page_ids.sort();
3926                all_page_ids.dedup();
3927
3928                // Check that all page IDs are accounted for
3929                let expected_page_ids: Vec<PageID> =
3930                    (0..writer.next_page_id.0).map(PageID).collect();
3931                assert_eq!(expected_page_ids, all_page_ids);
3932            }
3933        }
3934
3935        #[test]
3936        #[serial]
3937        fn test_insert_freed_page_ids_until_split_internal() {
3938            let (_temp_dir, db) = construct_mvcc(64);
3939
3940            // Get latest header
3941            let header_page = db.get_latest_header_page().unwrap();
3942            let header_node = header_page.as_header_node().unwrap();
3943
3944            // Create a writer
3945            let mut writer = Writer::new(
3946                header_page.clone(),
3947                Tsn(header_node.tsn.0 + 1),
3948                header_node.next_page_id,
3949                header_node.free_lists_tree_root_id,
3950                header_node.events_tree_root_id,
3951                header_node.tags_tree_root_id,
3952                header_node.tracking_tree_root_id,
3953                header_node.next_position,
3954                VERBOSE,
3955                db.page_size,
3956                db.max_node_size,
3957            );
3958
3959            // Start with TSN 100
3960            let mut tsn = Tsn(100);
3961            let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
3962            let mut has_split_internal = false;
3963
3964            // Insert page IDs until we split an internal node
3965            while !has_split_internal {
3966                // Allocate and insert the first page ID
3967                let page_id1 = writer.alloc_page_id();
3968                writer
3969                    .insert_freed_page_id(&db, tsn, page_id1, db.max_node_size, db.page_size)
3970                    .unwrap();
3971                inserted.push((tsn, page_id1));
3972
3973                // Allocate and insert second page ID
3974                let page_id2 = writer.alloc_page_id();
3975                writer
3976                    .insert_freed_page_id(&db, tsn, page_id2, db.max_node_size, db.page_size)
3977                    .unwrap();
3978                inserted.push((tsn, page_id2));
3979
3980                // Increment TSN for next iteration
3981                tsn = Tsn(tsn.0 + 1);
3982
3983                // Check if we've split an internal node
3984                let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
3985                match &root_page.node {
3986                    Node::FreeListInternal(root_node) => {
3987                        // Check if the first child is an internal node
3988                        if !root_node.child_ids.is_empty() {
3989                            let child_id = root_node.child_ids[0];
3990                            if let Some(child_page) = writer.dirty.get(&child_id) {
3991                                match &child_page.node {
3992                                    Node::FreeListInternal(_) => {
3993                                        has_split_internal = true;
3994                                    }
3995                                    _ => {}
3996                                }
3997                            }
3998                        }
3999                    }
4000                    _ => {}
4001                }
4002                if inserted.len() > 100 {
4003                    panic!("Too many inserted page IDs");
4004                }
4005            }
4006
4007            // Check keys and values of all pages
4008            let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
4009            let root_node = match &root_page.node {
4010                Node::FreeListInternal(node) => node,
4011                _ => panic!("Expected FreeListInternal node"),
4012            };
4013
4014            // Collect active page IDs
4015            let mut active_page_ids = vec![
4016                HEADER_PAGE_ID_0,
4017                HEADER_PAGE_ID_1,
4018                writer.free_lists_tree_root_id,
4019                writer.events_tree_root_id,
4020                writer.tags_tree_root_id,
4021            ];
4022
4023            // Collect freed page IDs
4024            let mut freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
4025
4026            // Track the previous child for key ordering checks
4027            let mut previous_child: Option<&FreeListInternalNode> = None;
4028
4029            // Check each child of the root
4030            for (i, &child_id) in root_node.child_ids.iter().enumerate() {
4031                active_page_ids.push(child_id);
4032
4033                let child_page = writer.dirty.get(&child_id).unwrap();
4034                assert_eq!(child_id, child_page.page_id);
4035
4036                let child_node = match &child_page.node {
4037                    Node::FreeListInternal(node) => node,
4038                    _ => panic!("Expected FreeListInternal node"),
4039                };
4040
4041                // Check key ordering between root and child
4042                if i > 0 {
4043                    assert!(root_node.keys[i - 1] < child_node.keys[0]);
4044
4045                    // Check key ordering between previous child and current child
4046                    if let Some(prev_child) = previous_child {
4047                        assert!(root_node.keys[i - 1] > *prev_child.keys.last().unwrap());
4048                    }
4049                }
4050
4051                previous_child = Some(child_node);
4052
4053                // Check each grandchild
4054                for (j, &grand_child_id) in child_node.child_ids.iter().enumerate() {
4055                    active_page_ids.push(grand_child_id);
4056
4057                    let grand_child_page = writer.dirty.get(&grand_child_id).unwrap();
4058                    assert_eq!(grand_child_id, grand_child_page.page_id);
4059
4060                    let grand_child_node = match &grand_child_page.node {
4061                        Node::FreeListLeaf(node) => node,
4062                        _ => panic!("Expected FreeListLeaf node"),
4063                    };
4064
4065                    // Check key ordering between child and grandchild
4066                    if j > 0 {
4067                        assert_eq!(child_node.keys[j - 1], grand_child_node.keys[0]);
4068                    }
4069
4070                    // Check each key and value in the grandchild
4071                    for (k, &key) in grand_child_node.keys.iter().enumerate() {
4072                        for &value in &grand_child_node.values[k].page_ids {
4073                            // Find the matching inserted item
4074                            let pos = inserted.iter().position(|&(t, p)| t == key && p == value);
4075                            if let Some(idx) = pos {
4076                                inserted.remove(idx);
4077                            }
4078                            freed_page_ids.push(value);
4079                        }
4080                    }
4081                }
4082            }
4083
4084            // We should have processed all inserted items
4085            assert!(inserted.is_empty());
4086
4087            // We should have 10 active pages
4088            assert_eq!(11, active_page_ids.len());
4089
4090            // Audit page IDs
4091            let mut all_page_ids = active_page_ids.clone();
4092            all_page_ids.extend(freed_page_ids.clone());
4093            all_page_ids.sort();
4094            all_page_ids.dedup();
4095
4096            // Check that all page IDs are accounted for
4097            let expected_page_ids: Vec<PageID> = (0..writer.next_page_id.0).map(PageID).collect();
4098            assert_eq!(expected_page_ids, all_page_ids);
4099        }
4100
4101        #[test]
4102        #[serial]
4103        fn test_remove_freed_page_ids_from_split_internal() {
4104            let (_temp_dir, db) = construct_mvcc(64);
4105
4106            // First, insert page IDs until we split an internal node
4107            let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
4108            let previous_root_id;
4109            let previous_writer_tsn;
4110
4111            {
4112                // Get a writer
4113                let mut writer = db.writer().unwrap();
4114
4115                // Remember the initial root ID
4116                previous_root_id = writer.free_lists_tree_root_id;
4117
4118                // Insert page IDs until we split an internal node
4119                let mut has_split_internal = false;
4120                let mut tsn = writer.tsn;
4121
4122                while !has_split_internal {
4123                    // Increment TSN
4124                    tsn = Tsn(tsn.0 + 1);
4125                    writer.tsn = tsn;
4126
4127                    // Allocate and insert the first page ID
4128                    let page_id1 = writer.alloc_page_id();
4129                    writer
4130                        .insert_freed_page_id(&db, tsn, page_id1, db.max_node_size, db.page_size)
4131                        .unwrap();
4132                    inserted.push((tsn, page_id1));
4133
4134                    // Allocate and insert second page ID
4135                    let page_id2 = writer.alloc_page_id();
4136                    writer
4137                        .insert_freed_page_id(&db, tsn, page_id2, db.max_node_size, db.page_size)
4138                        .unwrap();
4139                    inserted.push((tsn, page_id2));
4140
4141                    // Check if we've split an internal node
4142                    let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
4143                    match &root_page.node {
4144                        Node::FreeListInternal(root_node) => {
4145                            // Check if the first child is an internal node
4146                            if !root_node.child_ids.is_empty() {
4147                                let child_id = root_node.child_ids[0];
4148                                if let Some(child_page) = writer.dirty.get(&child_id) {
4149                                    match &child_page.node {
4150                                        Node::FreeListInternal(_) => {
4151                                            has_split_internal = true;
4152                                        }
4153                                        _ => {}
4154                                    }
4155                                }
4156                            }
4157                        }
4158                        _ => {}
4159                    }
4160                }
4161
4162                // Remember the final TSN
4163                previous_writer_tsn = writer.tsn;
4164
4165                // Commit the transaction
4166                db.commit(&mut writer).unwrap();
4167            }
4168
4169            // Now remove all the inserted freed page IDs
4170            {
4171                // Get latest header
4172                let header_page = db.get_latest_header_page().unwrap();
4173                let header_node = header_page.as_header_node().unwrap();
4174
4175                // Create a new writer
4176                let mut writer = Writer::new(
4177                    header_page.clone(),
4178                    Tsn(header_node.tsn.0 + 1),
4179                    header_node.next_page_id,
4180                    header_node.free_lists_tree_root_id,
4181                    header_node.events_tree_root_id,
4182                    header_node.tags_tree_root_id,
4183                    header_node.tracking_tree_root_id,
4184                    header_node.next_position,
4185                    VERBOSE,
4186                    db.page_size,
4187                    db.max_node_size,
4188                );
4189
4190                // Remember the initial root ID
4191                let old_root_id = writer.free_lists_tree_root_id;
4192
4193                // Remove all inserted page IDs
4194                for (tsn, page_id) in inserted.iter() {
4195                    writer.remove_free_page_id(&db, *tsn, *page_id).unwrap();
4196                }
4197
4198                // Check the root page has been CoW-ed
4199                assert_ne!(old_root_id, writer.free_lists_tree_root_id);
4200                assert_eq!(1, writer.dirty.len());
4201                assert!(writer.dirty.contains_key(&writer.free_lists_tree_root_id));
4202
4203                let new_root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
4204                assert_eq!(writer.free_lists_tree_root_id, new_root_page.page_id);
4205
4206                // Check old root ID is in freed page IDs
4207                let freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
4208                assert!(freed_page_ids.contains(&old_root_id));
4209
4210                // There were 14 pages, and now we have 1. We have
4211                // freed page IDs for 7 old pages and 6 CoW pages.
4212                assert_eq!(13, writer.freed_page_ids.len());
4213
4214                // Check keys and values of the new root page
4215                match &new_root_page.node {
4216                    Node::FreeListLeaf(node) => {
4217                        let expected_keys = vec![previous_writer_tsn];
4218                        assert_eq!(expected_keys, node.keys);
4219
4220                        let expected_values = vec![FreeListLeafValue {
4221                            page_ids: vec![previous_root_id],
4222                            root_id: PageID(0),
4223                        }];
4224                        assert_eq!(expected_values, node.values);
4225                    }
4226                    _ => panic!("Expected FreeListLeaf node"),
4227                }
4228
4229                // Audit page IDs
4230                let active_page_ids = vec![
4231                    HEADER_PAGE_ID_0,
4232                    HEADER_PAGE_ID_1,
4233                    writer.free_lists_tree_root_id,
4234                    writer.events_tree_root_id,
4235                    writer.tags_tree_root_id,
4236                ];
4237
4238                // Collect all freed page IDs
4239                let mut all_freed_page_ids = freed_page_ids.clone();
4240
4241                // Add page IDs from the leaf node
4242                match &new_root_page.node {
4243                    Node::FreeListLeaf(node) => {
4244                        for (_, value) in node.keys.iter().zip(node.values.iter()) {
4245                            all_freed_page_ids.extend(value.page_ids.clone());
4246                        }
4247                    }
4248                    _ => panic!("Expected FreeListLeaf node"),
4249                }
4250
4251                // Add inserted page IDs
4252                let inserted_page_ids: Vec<PageID> = inserted.iter().map(|(_, id)| *id).collect();
4253
4254                // Collect all page IDs
4255                let mut all_page_ids = active_page_ids.clone();
4256                all_page_ids.extend(all_freed_page_ids.clone());
4257                all_page_ids.extend(inserted_page_ids.clone());
4258                all_page_ids.sort();
4259                all_page_ids.dedup();
4260
4261                // Check that all page IDs are accounted for
4262                let expected_page_ids: Vec<PageID> =
4263                    (0..writer.next_page_id.0).map(PageID).collect();
4264                assert_eq!(expected_page_ids, all_page_ids);
4265            }
4266        }
4267
4268        #[test]
4269        #[serial]
4270        fn test_remove_freed_page_ids_until_replace_old_id_with_orphaned_child_id() {
4271            // This test covers the case where an internal node is removed but leaving a
4272            // child page ID that must be replaced in the parent page, when the parent
4273            // page is not yet dirty. So, here, we must contrive to replace an old ID
4274            // with an orphaned child ID. We can do this by inserting freed page IDs
4275            // until there is an internal page split, and then removing them in order
4276            // until the first internal node is removed, using a new writer each time
4277            // to avoid the internal node becoming dirty before the last key is removed,
4278            // so that its parent internal node (which is the root internal node here)
4279            // will not already have the old child page ID replaced with a dirty
4280            // child page ID.
4281            let (_temp_dir, db) = construct_mvcc(128);
4282
4283            // First, insert page IDs until we split an internal node
4284            let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
4285
4286            {
4287                // Get a writer
4288                let mut writer = db.writer().unwrap();
4289
4290                // Insert page IDs until we split an internal node
4291                let mut has_split_internal = false;
4292                let mut tsn = writer.tsn;
4293
4294                while !has_split_internal {
4295                    // Increment TSN
4296                    tsn = Tsn(tsn.0 + 1);
4297                    writer.tsn = tsn;
4298
4299                    // Allocate and insert the first page ID
4300                    let page_id1 = writer.alloc_page_id();
4301                    writer
4302                        .insert_freed_page_id(&db, tsn, page_id1, db.max_node_size, db.page_size)
4303                        .unwrap();
4304                    inserted.push((tsn, page_id1));
4305
4306                    // Allocate and insert second page ID
4307                    let page_id2 = writer.alloc_page_id();
4308                    writer
4309                        .insert_freed_page_id(&db, tsn, page_id2, db.max_node_size, db.page_size)
4310                        .unwrap();
4311                    inserted.push((tsn, page_id2));
4312
4313                    // Check if we've split an internal node
4314                    let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
4315                    match &root_page.node {
4316                        Node::FreeListInternal(root_node) => {
4317                            // Check if the first child is an internal node
4318                            if !root_node.child_ids.is_empty() {
4319                                let child_id = root_node.child_ids[0];
4320                                if let Some(child_page) = writer.dirty.get(&child_id) {
4321                                    match &child_page.node {
4322                                        Node::FreeListInternal(_) => {
4323                                            has_split_internal = true;
4324                                        }
4325                                        _ => {}
4326                                    }
4327                                }
4328                            }
4329                        }
4330                        _ => {}
4331                    }
4332                }
4333
4334                // Commit the transaction
4335                db.commit(&mut writer).unwrap();
4336            }
4337
4338            // Get all the free page IDs.
4339            db.reader_tsns.unregister(Tsn(0));
4340            let writer = db.writer().unwrap();
4341            let reusable_page_ids = writer.reusable_page_ids.clone();
4342
4343            // Block inserted page IDs from being reused
4344            db.reader_tsns.register(Tsn(0));
4345
4346            // Remove each free page ID.
4347            for (page_id, tsn) in reusable_page_ids {
4348                let mut writer = db.writer().unwrap();
4349                writer.remove_free_page_id(&db, tsn, page_id).unwrap();
4350                db.commit(&mut writer).unwrap();
4351            }
4352        }
4353
4354        #[test]
4355        #[serial]
4356        fn test_insert_freed_page_ids_overflow_single_key_moves_to_tsn_subtree() {
4357            // Use tiny pages to force the inline list to overflow quickly
4358            let page_size = 64;
4359            let (_temp_dir, db) = construct_mvcc(page_size);
4360
4361            // Start a writer
4362            let mut writer = db.writer().unwrap();
4363            let tsn = writer.tsn;
4364
4365            // With page_size=64, max_node_size = 55. A single key/value with 4 page IDs
4366            // takes 52 bytes, and adding the 5th (+8) would exceed capacity.
4367            let mut inserted_count: usize = 0;
4368            loop {
4369                let pid = writer.alloc_page_id();
4370                writer
4371                    .insert_freed_page_id(&db, tsn, pid, db.max_node_size, db.page_size)
4372                    .unwrap();
4373                inserted_count += 1;
4374                let dirty_page_id = {
4375                    let mut keys = writer.dirty.keys();
4376                    assert_eq!(keys.len(), 1);
4377                    *keys.next().unwrap()
4378                };
4379                let dirty_page = writer.get_mut_dirty(dirty_page_id).unwrap();
4380                if let Node::FreeListLeaf(leaf_node) = &dirty_page.node {
4381                    if !leaf_node.would_fit_new_page_id(db.max_node_size) {
4382                        break;
4383                    }
4384                } else {
4385                    panic!("Expected leaf node")
4386                }
4387            }
4388
4389            // The next insert for the same TSN should succeed by creating a TSN-subtree
4390            let pid5 = writer.alloc_page_id();
4391            writer
4392                .insert_freed_page_id(&db, tsn, pid5, db.max_node_size, db.page_size)
4393                .unwrap();
4394            inserted_count += 1;
4395
4396            // Insert two more page IDs for the same TSN into the TSN-subtree
4397            let pid6 = writer.alloc_page_id();
4398            writer
4399                .insert_freed_page_id(&db, tsn, pid6, db.max_node_size, db.page_size)
4400                .unwrap();
4401            inserted_count += 1;
4402
4403            let pid7 = writer.alloc_page_id();
4404            writer
4405                .insert_freed_page_id(&db, tsn, pid7, db.max_node_size, db.page_size)
4406                .unwrap();
4407            inserted_count += 1;
4408
4409            // Verify that the leaf now points to a TSN-subtree for this TSN, and that the TSN-subtree root is an internal node (leaf split)
4410            let dirty_ids: Vec<PageID> = { writer.dirty.keys().cloned().collect() };
4411            let mut tsn_root_id = PageID(0);
4412            for dirty_page_id in dirty_ids {
4413                let dirty_page = writer.get_mut_dirty(dirty_page_id).unwrap();
4414                if let Node::FreeListLeaf(leaf_node) = &dirty_page.node {
4415                    assert_eq!(1, leaf_node.keys.len());
4416                    assert_eq!(tsn, leaf_node.keys[0]);
4417                    let val = &leaf_node.values[0];
4418                    assert_eq!(0, val.page_ids.len());
4419                    assert_ne!(PageID(0), val.root_id);
4420                    tsn_root_id = val.root_id;
4421                    break;
4422                }
4423            }
4424            assert_ne!(PageID(0), tsn_root_id);
4425            // The TSN-subtree leaf should have split, so the root must now be internal
4426            // With page_size=64, max_node_size = 55. Seven page IDs exceeds capacity (2 + 8 * 7).
4427            let tsn_root_page = writer.get_page_ref(&db, tsn_root_id).unwrap();
4428            match &tsn_root_page.node {
4429                Node::FreeListTsnInternal(internal) => {
4430                    assert_eq!(2, internal.child_ids.len());
4431                    assert_eq!(1, internal.keys.len());
4432                }
4433                other => panic!(
4434                    "Expected TSN-subtree internal node, got {:?}",
4435                    other.type_name()
4436                ),
4437            }
4438
4439            // Continue inserting page IDs for the same TSN until the TSN-subtree internal node splits
4440            let mut extra_inserts = 0usize;
4441            let mut guard = 0usize;
4442            loop {
4443                guard += 1;
4444                assert!(
4445                    guard < 200,
4446                    "guard hit while waiting for TSN-subtree internal split"
4447                );
4448                let pid = writer.alloc_page_id();
4449                writer
4450                    .insert_freed_page_id(&db, tsn, pid, db.max_node_size, db.page_size)
4451                    .unwrap();
4452                extra_inserts += 1;
4453
4454                // Refresh tsn_root_id from the FreeList leaf since the root may change when it splits
4455                let dirty_ids: Vec<PageID> = writer.dirty.keys().cloned().collect();
4456                tsn_root_id = PageID(0);
4457                for dirty_page_id in dirty_ids {
4458                    let dirty_page = writer.get_mut_dirty(dirty_page_id).unwrap();
4459                    if let Node::FreeListLeaf(leaf_node) = &dirty_page.node {
4460                        assert_eq!(1, leaf_node.keys.len());
4461                        assert_eq!(tsn, leaf_node.keys[0]);
4462                        let val = &leaf_node.values[0];
4463                        assert_eq!(0, val.page_ids.len());
4464                        assert_ne!(PageID(0), val.root_id);
4465                        tsn_root_id = val.root_id;
4466                        break;
4467                    }
4468                }
4469                assert_ne!(PageID(0), tsn_root_id);
4470
4471                let root_node_owned =
4472                    { writer.get_page_ref(&db, tsn_root_id).unwrap().node.clone() };
4473                match root_node_owned {
4474                    Node::FreeListTsnInternal(internal_root) => {
4475                        // If the first child is also an internal node, then the previous internal split promoted a new root
4476                        let first_child_id = internal_root.child_ids[0];
4477                        let first_child_node = {
4478                            writer
4479                                .get_page_ref(&db, first_child_id)
4480                                .unwrap()
4481                                .node
4482                                .clone()
4483                        };
4484                        if matches!(first_child_node, Node::FreeListTsnInternal(_)) {
4485                            // We have achieved an internal split in the TSN-subtree
4486                            // The new root should have exactly 1 key and 2 children after promotion
4487                            assert_eq!(1, internal_root.keys.len());
4488                            assert_eq!(2, internal_root.child_ids.len());
4489                            break;
4490                        }
4491                    }
4492                    other => panic!(
4493                        "Expected TSN-subtree internal node, got {:?}",
4494                        other.type_name()
4495                    ),
4496                }
4497            }
4498
4499            // Now add another PageID to the internal->internal->leaf.
4500            let pid = writer.alloc_page_id();
4501            writer
4502                .insert_freed_page_id(&db, tsn, pid, db.max_node_size, db.page_size)
4503                .unwrap();
4504            extra_inserts += 1;
4505
4506            // Verify all page IDs are discoverable via find_reusable_page_ids
4507            writer.find_reusable_page_ids(&db).unwrap();
4508            assert_eq!(
4509                inserted_count + extra_inserts,
4510                writer.reusable_page_ids.len()
4511            );
4512            for &(_pid, _tsn) in writer.reusable_page_ids.iter() {
4513                assert_eq!(tsn, _tsn);
4514            }
4515        }
4516
4517        #[test]
4518        #[serial]
4519        fn test_remove_freed_page_id_from_tsn_subtree_leaf_pid1() {
4520            let (_temp_dir, db) = construct_mvcc(128);
4521            let mut writer = db.writer().unwrap();
4522
4523            let (pid1, pid2, tsn1) = build_free_list_tree_leaf_tsn_subtree_leaf(&mut writer);
4524
4525            writer.find_reusable_page_ids(&db).unwrap();
4526            assert_eq!(2, writer.reusable_page_ids.len());
4527            assert_eq!((pid1, tsn1), writer.reusable_page_ids[0]);
4528            assert_eq!((pid2, tsn1), writer.reusable_page_ids[1]);
4529
4530            writer.remove_free_page_id(&db, tsn1, pid1).unwrap();
4531            writer.find_reusable_page_ids(&db).unwrap();
4532            assert_eq!(1, writer.reusable_page_ids.len());
4533            assert_eq!((pid2, tsn1), writer.reusable_page_ids[0]);
4534        }
4535
4536        #[test]
4537        #[serial]
4538        fn test_remove_freed_page_id_from_tsn_subtree_leaf_pid2() {
4539            let (_temp_dir, db) = construct_mvcc(128);
4540            let mut writer = db.writer().unwrap();
4541
4542            let (pid1, pid2, tsn1) = build_free_list_tree_leaf_tsn_subtree_leaf(&mut writer);
4543
4544            writer.remove_free_page_id(&db, tsn1, pid2).unwrap();
4545            writer.find_reusable_page_ids(&db).unwrap();
4546            assert_eq!(1, writer.reusable_page_ids.len());
4547            assert_eq!((pid1, tsn1), writer.reusable_page_ids[0]);
4548        }
4549
4550        #[test]
4551        #[serial]
4552        fn test_tsn_subtree_random_order_insert_and_ordering() {
4553            // Moderate page size to force multiple leaves and internals
4554            let page_size = 256;
4555            let (_temp_dir, db) = construct_mvcc(page_size);
4556            let mut writer = db.writer().unwrap();
4557            let tsn = writer.tsn;
4558
4559            // Generate many distinct PageIDs, then shuffle their insertion order
4560            let n = 100usize;
4561            let mut pids: Vec<PageID> = Vec::with_capacity(n);
4562            for _ in 0..n {
4563                pids.push(writer.alloc_page_id());
4564            }
4565            // Shuffle by swapping using a simple deterministic pattern to avoid extra deps
4566            for i in 0..pids.len() {
4567                let j = (i * 37 + 13) % pids.len();
4568                pids.swap(i, j);
4569            }
4570            // Insert them all for the same TSN in random order
4571            for pid in &pids {
4572                writer
4573                    .insert_freed_page_id(&db, tsn, *pid, db.max_node_size, db.page_size)
4574                    .unwrap();
4575            }
4576            // Insert a duplicate of the first ID and ensure it is ignored
4577            let dup = pids[0];
4578            writer
4579                .insert_freed_page_id(&db, tsn, dup, db.max_node_size, db.page_size)
4580                .unwrap();
4581
4582            // Verify via reusable_page_ids
4583            writer.find_reusable_page_ids(&db).unwrap();
4584            assert_eq!(n, writer.reusable_page_ids.len());
4585            for &(_pid, _tsn) in writer.reusable_page_ids.iter() {
4586                assert_eq!(tsn, _tsn);
4587            }
4588
4589            // Inspect the TSN-subtree shape: root should be internal for this many ids
4590            // Find the freelist leaf that holds this TSN and get its root_id
4591            let mut tsn_root_id = PageID(0);
4592            for page_id in writer.dirty.keys().cloned().collect::<Vec<_>>() {
4593                let page = writer.get_mut_dirty(page_id).unwrap();
4594                if let Node::FreeListLeaf(leaf_node) = &page.node {
4595                    if !leaf_node.keys.is_empty() && leaf_node.keys[0] == tsn {
4596                        tsn_root_id = leaf_node.values[0].root_id;
4597                        break;
4598                    }
4599                }
4600            }
4601            assert_ne!(PageID(0), tsn_root_id);
4602            let root_node_owned = { writer.get_page_ref(&db, tsn_root_id).unwrap().node.clone() };
4603            match root_node_owned {
4604                Node::FreeListTsnInternal(internal_root) => {
4605                    // It’s likely that at least one child is internal for n=100 at this page size
4606                    let first_child_id = internal_root.child_ids[0];
4607                    let first_child_node = {
4608                        writer
4609                            .get_page_ref(&db, first_child_id)
4610                            .unwrap()
4611                            .node
4612                            .clone()
4613                    };
4614                    if let Node::FreeListTsnInternal(_in2) = first_child_node {
4615                        // ok, internal->internal exists
4616                    }
4617                }
4618                Node::FreeListTsnLeaf(_) => {
4619                    // With small n this could still be a leaf root; accept but ensure ordering via reusable_page_ids
4620                }
4621                other => panic!("Unexpected node type: {}", other.type_name()),
4622            }
4623        }
4624
4625        #[test]
4626        #[serial]
4627        fn test_upgrade_inline_to_tsn_subtree_with_random_inserts_and_duplicates() {
4628            // Small page size to quickly overflow inline and create a TSN-subtree
4629            let page_size = 96;
4630            let (_temp_dir, db) = construct_mvcc(page_size);
4631            let mut writer = db.writer().unwrap();
4632            let tsn = writer.tsn;
4633
4634            // Insert a few to fill inline list close to capacity
4635            let mut inline_ids = Vec::new();
4636            loop {
4637                let pid = writer.alloc_page_id();
4638                let res =
4639                    writer.insert_freed_page_id(&db, tsn, pid, db.max_node_size, db.page_size);
4640                if res.is_err() {
4641                    panic!("unexpected error inserting into inline");
4642                }
4643                inline_ids.push(pid);
4644                // Heuristic to break when the next inline would likely overflow and cause move-to-subtree
4645                let dirty_id = writer.dirty.keys().cloned().next().unwrap();
4646                if let Node::FreeListLeaf(leaf_node) = &writer.get_mut_dirty(dirty_id).unwrap().node
4647                {
4648                    if !leaf_node.would_fit_new_page_id(db.max_node_size) {
4649                        break;
4650                    }
4651                }
4652            }
4653
4654            // Now insert a batch of random ids including some duplicates
4655            let mut extra_ids = Vec::new();
4656            for _ in 0..30 {
4657                extra_ids.push(writer.alloc_page_id());
4658            }
4659            // Shuffle simple
4660            for i in 0..extra_ids.len() {
4661                let j = (i * 29 + 7) % extra_ids.len();
4662                extra_ids.swap(i, j);
4663            }
4664            // Add some duplicates from earlier inline ids
4665            if !inline_ids.is_empty() {
4666                extra_ids.push(inline_ids[0]);
4667            }
4668            if inline_ids.len() > 1 {
4669                extra_ids.push(inline_ids[1]);
4670            }
4671
4672            for pid in &extra_ids {
4673                writer
4674                    .insert_freed_page_id(&db, tsn, *pid, db.max_node_size, db.page_size)
4675                    .unwrap();
4676            }
4677
4678            // Verify no duplicates and all ids present
4679            writer.find_reusable_page_ids(&db).unwrap();
4680            let mut expected: Vec<PageID> = inline_ids.clone();
4681            for p in extra_ids {
4682                if !expected.contains(&p) {
4683                    expected.push(p);
4684                }
4685            }
4686            expected.sort_by_key(|p| p.0);
4687            expected.dedup();
4688            let mut actual: Vec<PageID> =
4689                writer.reusable_page_ids.iter().map(|(p, _)| *p).collect();
4690            actual.sort_by_key(|p| p.0);
4691            assert_eq!(expected, actual);
4692        }
4693
4694        #[test]
4695        #[serial]
4696        fn test_remove_freed_page_id_from_tsn_subtree_leaf_all_with_dirty_pages() {
4697            let (_temp_dir, db) = construct_mvcc(128);
4698            let mut writer = db.writer().unwrap();
4699
4700            let (pid1, pid2, tsn1) = build_free_list_tree_leaf_tsn_subtree_leaf(&mut writer);
4701
4702            writer.remove_free_page_id(&db, tsn1, pid1).unwrap();
4703            writer.remove_free_page_id(&db, tsn1, pid2).unwrap();
4704            writer.find_reusable_page_ids(&db).unwrap();
4705            assert_eq!(0, writer.reusable_page_ids.len());
4706
4707            assert_eq!(2, writer.freed_page_ids.len());
4708        }
4709
4710        #[test]
4711        #[serial]
4712        fn test_remove_freed_page_id_from_tsn_subtree_leaf_all_after_commit() {
4713            // In this test we are trying to arrange the writer to remove a
4714            // PageID for a TSN that has a subtree, without dirty pages, so
4715            // that it must deserialize the TSN subtree root page.
4716            let (_temp_dir, db) = construct_mvcc(128);
4717            let mut writer = db.writer().unwrap();
4718
4719            // Bigger TSN than the value used in build_free_list_tree_leaf_tsn_subtree_leaf.
4720            writer.tsn = Tsn(40);
4721
4722            // This inserts two dirty pages and changes the `orig_free_lists_tree_root_id`.
4723            let (pid1, pid2, tsn1) = build_free_list_tree_leaf_tsn_subtree_leaf(&mut writer);
4724
4725            // Just commit the dirty pages, and then .
4726            writer.freed_page_ids.clear();
4727            db.commit(&mut writer).unwrap();
4728
4729            // Reset the writer, which should find the two PageIDs are reusable.
4730            writer.reset(&db).unwrap();
4731
4732            assert_eq!(2, writer.reusable_page_ids.len());
4733            assert_eq!((pid1, tsn1), writer.reusable_page_ids[0]);
4734            assert_eq!((pid2, tsn1), writer.reusable_page_ids[1]);
4735            assert_eq!(0, writer.freed_page_ids.len());
4736
4737            // Now remove the PageIDs (and therefore the TSN) from the TSN subtree.
4738            // - two pages were CoW-ed.
4739            writer.remove_free_page_id(&db, tsn1, pid1).unwrap();
4740            assert_eq!(2, writer.freed_page_ids.len());
4741            // - the TSN subtree root page was removed, TSN root page dirty and updated.
4742            writer.remove_free_page_id(&db, tsn1, pid2).unwrap();
4743            assert_eq!(3, writer.freed_page_ids.len());
4744
4745            // Find reusable PageIDs - should be none.
4746            writer.find_reusable_page_ids(&db).unwrap();
4747            assert_eq!(0, writer.reusable_page_ids.len());
4748        }
4749
4750        #[test]
4751        #[serial]
4752        fn test_remove_freed_page_id_from_tsn_subtree_internal_leaf_pid1() {
4753            let (_temp_dir, db) = construct_mvcc(128);
4754            let mut writer = db.writer().unwrap();
4755
4756            let (pid1, pid2, pid3, pid4, tsn1) =
4757                build_free_list_tree_leaf_tsn_subtree_internal_leaf(&mut writer);
4758
4759            writer.remove_free_page_id(&db, tsn1, pid1).unwrap();
4760            writer.find_reusable_page_ids(&db).unwrap();
4761            assert_eq!(3, writer.reusable_page_ids.len());
4762            assert_eq!((pid3, tsn1), writer.reusable_page_ids[0]);
4763            assert_eq!((pid4, tsn1), writer.reusable_page_ids[1]);
4764            assert_eq!((pid2, tsn1), writer.reusable_page_ids[2]);
4765
4766            assert_eq!(1, writer.freed_page_ids.len());
4767
4768            writer.remove_free_page_id(&db, tsn1, pid2).unwrap();
4769            writer.find_reusable_page_ids(&db).unwrap();
4770            assert_eq!(2, writer.reusable_page_ids.len());
4771            assert_eq!((pid3, tsn1), writer.reusable_page_ids[0]);
4772            assert_eq!((pid4, tsn1), writer.reusable_page_ids[1]);
4773
4774            assert_eq!(3, writer.freed_page_ids.len());
4775
4776            writer.remove_free_page_id(&db, tsn1, pid3).unwrap();
4777            writer.find_reusable_page_ids(&db).unwrap();
4778            assert_eq!(1, writer.reusable_page_ids.len());
4779            assert_eq!((pid4, tsn1), writer.reusable_page_ids[0]);
4780
4781            assert_eq!(3, writer.freed_page_ids.len());
4782
4783            writer.remove_free_page_id(&db, tsn1, pid4).unwrap();
4784            writer.find_reusable_page_ids(&db).unwrap();
4785            assert_eq!(0, writer.reusable_page_ids.len());
4786
4787            assert_eq!(4, writer.freed_page_ids.len());
4788        }
4789
4790        #[test]
4791        #[serial]
4792        fn test_remove_freed_page_id_from_tsn_subtree_internal_internal_leaf_pid1() {
4793            let (_temp_dir, db) = construct_mvcc(128);
4794            let mut writer = db.writer().unwrap();
4795
4796            let (pid1, pid2, pid3, pid4, pid5, pid6, pid7, pid8, tsn) =
4797                build_free_list_tree_leaf_tsn_subtree_internal_internal_leaf(&mut writer);
4798
4799            writer.remove_free_page_id(&db, tsn, pid1).unwrap();
4800            writer.find_reusable_page_ids(&db).unwrap();
4801            assert_eq!(7, writer.reusable_page_ids.len());
4802            assert_eq!((pid3, tsn), writer.reusable_page_ids[0]);
4803            assert_eq!((pid4, tsn), writer.reusable_page_ids[1]);
4804            assert_eq!((pid5, tsn), writer.reusable_page_ids[2]);
4805            assert_eq!((pid6, tsn), writer.reusable_page_ids[3]);
4806            assert_eq!((pid7, tsn), writer.reusable_page_ids[4]);
4807            assert_eq!((pid8, tsn), writer.reusable_page_ids[5]);
4808            assert_eq!((pid2, tsn), writer.reusable_page_ids[6]);
4809
4810            assert_eq!(1, writer.freed_page_ids.len());
4811        }
4812
4813        #[test]
4814        #[serial]
4815        fn test_remove_freed_page_id_cow_does_not_leak_ids_in_tsn_subtree() {
4816            // Build a TSN-subtree with depth (internal->internal->leaf), commit it, then
4817            // perform a removal in a new writer to force copy-on-write on the subtree path.
4818            let (_temp_dir, db) = construct_mvcc(128);
4819
4820            // First writer builds the TSN-subtree and commits
4821            let w1_tsn = {
4822                let mut w1 = db.writer().unwrap();
4823                let (_pid1, _pid2, _pid3, _pid4, _pid5, _pid6, _pid7, _pid8, tsn) =
4824                    build_free_list_tree_leaf_tsn_subtree_internal_internal_leaf(&mut w1);
4825                // Commit so that subsequent modifications must use COW
4826                db.commit(&mut w1).unwrap();
4827                // Keep tsn for next phase via storing in header
4828                tsn
4829            };
4830
4831            // Second writer removes a page id to trigger COW on nodes along the path
4832            let mut w2 = db.writer().unwrap();
4833            // Find one reusable pid to remove via API, ensure tree populated
4834            w2.find_reusable_page_ids(&db).unwrap();
4835            assert!(w2.reusable_page_ids.len() >= 1);
4836            let (remove_pid, remove_tsn) = w2.reusable_page_ids[0];
4837            assert_eq!(remove_tsn, w1_tsn); // All built under this tsn in the helper
4838            w2.remove_free_page_id(&db, remove_tsn, remove_pid).unwrap();
4839
4840            // Now audit: every page id from 0..next_page_id must be either active or freed.
4841            // Collect active page ids by traversing the current free list tree, including TSN-subtrees.
4842            let mut active: Vec<PageID> = Vec::new();
4843            let mut freed_tree: Vec<PageID> = Vec::new();
4844            // Always-active headers and roots
4845            active.push(HEADER_PAGE_ID_0);
4846            active.push(HEADER_PAGE_ID_1);
4847            active.push(w2.free_lists_tree_root_id);
4848            active.push(w2.events_tree_root_id);
4849            active.push(w2.tags_tree_root_id);
4850
4851            // Traverse free list tree from current root, reading nodes from disk or cache
4852            let mut stack: Vec<PageID> = vec![w2.free_lists_tree_root_id];
4853            while let Some(pid) = stack.pop() {
4854                if active.contains(&pid) == false {
4855                    active.push(pid);
4856                }
4857                let node_owned = { w2.get_page_ref(&db, pid).unwrap().node.clone() };
4858                match node_owned {
4859                    Node::FreeListInternal(internal) => {
4860                        for child in internal.child_ids {
4861                            stack.push(child);
4862                        }
4863                    }
4864                    Node::FreeListLeaf(leaf) => {
4865                        // Any inline free page IDs are considered freed
4866                        for val in &leaf.values {
4867                            for &p in &val.page_ids {
4868                                freed_tree.push(p);
4869                            }
4870                        }
4871                        // If TSN-subtree root exists, traverse it too
4872                        for val in leaf.values {
4873                            if val.root_id != PageID(0) {
4874                                let mut tsn_stack: Vec<PageID> = vec![val.root_id];
4875                                while let Some(tid) = tsn_stack.pop() {
4876                                    if active.contains(&tid) == false {
4877                                        active.push(tid);
4878                                    }
4879                                    let tnode = { w2.get_page_ref(&db, tid).unwrap().node.clone() };
4880                                    match tnode {
4881                                        Node::FreeListTsnInternal(tint) => {
4882                                            for c in tint.child_ids {
4883                                                tsn_stack.push(c);
4884                                            }
4885                                        }
4886                                        Node::FreeListTsnLeaf(tleaf) => {
4887                                            for &p in &tleaf.page_ids {
4888                                                freed_tree.push(p);
4889                                            }
4890                                        }
4891                                        _ => panic!("Unexpected node type in TSN-subtree"),
4892                                    }
4893                                }
4894                            }
4895                        }
4896                    }
4897                    _ => panic!("Unexpected node type in free list tree"),
4898                }
4899            }
4900
4901            // Also include any currently-dirty pages (new COW copies) as active
4902            for (&pid, _page) in w2.dirty.iter() {
4903                if !active.contains(&pid) {
4904                    active.push(pid);
4905                }
4906            }
4907            // And include any pages we've read/deserialized during traversal
4908            for (&pid, _page) in w2.deserialized.iter() {
4909                if !active.contains(&pid) {
4910                    active.push(pid);
4911                }
4912            }
4913
4914            // Collect freed ids recorded by writer due to COW or structural removals
4915            let mut freed: Vec<PageID> = w2.freed_page_ids.iter().cloned().collect();
4916            // Include the reusable ids present in the tree itself
4917            freed.extend(freed_tree);
4918            // Include the reusable ids tracked by the writer snapshot
4919            for (pid, _tsn) in w2.reusable_page_ids.iter() {
4920                freed.push(*pid);
4921            }
4922
4923            // Validate coverage
4924            active.sort_by_key(|p| p.0);
4925            active.dedup();
4926            freed.sort_by_key(|p| p.0);
4927            freed.dedup();
4928            let mut union = active.clone();
4929            for id in &freed {
4930                if !union.contains(id) {
4931                    union.push(*id);
4932                }
4933            }
4934            union.sort_by_key(|p| p.0);
4935
4936            let expected: Vec<PageID> = (0..w2.next_page_id.0).map(PageID).collect();
4937            if expected != union {
4938                let mut missing: Vec<PageID> = expected
4939                    .iter()
4940                    .cloned()
4941                    .filter(|p| !union.contains(p))
4942                    .collect();
4943                let mut unexpected: Vec<PageID> = union
4944                    .iter()
4945                    .cloned()
4946                    .filter(|p| !expected.contains(p))
4947                    .collect();
4948                missing.sort_by_key(|p| p.0);
4949                unexpected.sort_by_key(|p| p.0);
4950                panic!(
4951                    "Missing: {:?} Unexpected: {:?}\nactive: {:?}\nfreed: {:?}",
4952                    missing, unexpected, active, freed
4953                );
4954            }
4955            assert_eq!(
4956                expected, union,
4957                "All page IDs must be accounted for (active or freed)"
4958            );
4959        }
4960    }
4961
4962    #[cfg(test)]
4963    mod schema_version_tests {
4964        use super::*;
4965        use serial_test::serial;
4966        use tempfile::tempdir;
4967
4968        #[test]
4969        #[serial]
4970        fn opening_db_with_newer_schema_version_errors() {
4971            // 1) Create a new database
4972            let temp_dir = tempdir().unwrap();
4973            let db_path = temp_dir.path().join("schema-guard.db");
4974            let page_size = 64usize; // small is fine for tests
4975            let verbose = false;
4976
4977            let mvcc = Mvcc::new(
4978                verbose,
4979                StorageOptions::default()
4980                    .db_path(db_path.clone())
4981                    .page_size(page_size),
4982            )
4983            .expect("must create new db");
4984
4985            // 2) Read header[0], bump its schema_version, write it back via pager
4986            let h0 = mvcc.read_header(HEADER_PAGE_ID_0).expect("read header 0");
4987            let mut n0 = h0.as_header_node().unwrap().clone();
4988            n0.schema_version = DB_SCHEMA_VERSION + 1;
4989
4990            // Recreate a Page with modified header and write it
4991            let page = Page::new(HEADER_PAGE_ID_0, Node::Header(n0));
4992            {
4993                let mut buf = mvcc.page_buf.lock();
4994                serialize_page_into(&mut buf, &page.node, mvcc.zero_fill_pages)
4995                    .expect("serialize header page");
4996                mvcc.rw
4997                    .pager
4998                    .write_page_data(page.page_id, &buf)
4999                    .expect("write modified header 0");
5000            }
5001
5002            // Ensure data is flushed (optional but nice to have)
5003            mvcc.fsync().ok();
5004
5005            // 3) Drop the instance to release the fs2 file lock so we can reopen
5006            drop(mvcc);
5007
5008            // 4) Attempt to open again; expect an InternalError complaining about schema version
5009            match Mvcc::new(
5010                verbose,
5011                StorageOptions::default()
5012                    .db_path(db_path)
5013                    .page_size(page_size),
5014            ) {
5015                Ok(_) => panic!("opening should have failed due to newer on-disk schema"),
5016                Err(DcbError::InternalError(msg)) => {
5017                    assert!(
5018                        msg.contains("Software version is too old"),
5019                        "unexpected error message: {msg}"
5020                    );
5021                }
5022                Err(other) => panic!("unexpected error type: {other:?}"),
5023            }
5024        }
5025    }
5026
5027    #[cfg(test)]
5028    mod page_cache_tests {
5029        use super::*;
5030        use serial_test::serial;
5031        use tempfile::tempdir;
5032
5033        #[test]
5034        #[serial]
5035        fn test_mvcc_page_cache_max_pages() {
5036            let temp_dir = tempdir().unwrap();
5037            let db_path = temp_dir.path().join("cache-pages.db");
5038            let options = StorageOptions::default()
5039                .db_path(&db_path)
5040                .page_cache_max_pages(10);
5041
5042            let mvcc = Mvcc::new(false, options).expect("mvcc new");
5043            assert!(mvcc.page_cache.is_some());
5044
5045            // Write some data
5046            let mut writer = mvcc.writer().expect("writer");
5047            let p1 = writer.alloc_page_id();
5048            let page = Page::new(
5049                p1,
5050                Node::FreeListLeaf(crate::free_lists_tree_nodes::FreeListLeafNode::default()),
5051            );
5052            writer.insert_dirty(page).expect("insert dirty");
5053            mvcc.commit(&mut writer).expect("commit");
5054
5055            // Page should be in cache now after commit
5056            {
5057                let cache = mvcc.page_cache.as_ref().unwrap();
5058                assert!(cache.get(&p1).is_some());
5059            }
5060
5061            // Read page - should hit cache
5062            let _read_page = mvcc.read_page(p1).expect("read page");
5063        }
5064
5065        #[test]
5066        #[serial]
5067        fn test_mvcc_page_cache_max_mb() {
5068            let temp_dir = tempdir().unwrap();
5069            let db_path = temp_dir.path().join("cache-mb.db");
5070            let options = StorageOptions::default()
5071                .db_path(&db_path)
5072                .page_cache_max_mb(1); // 1 MB
5073
5074            let mvcc = Mvcc::new(false, options).expect("mvcc new");
5075            assert!(mvcc.page_cache.is_some());
5076
5077            // Write some data
5078            let mut writer = mvcc.writer().expect("writer");
5079            let p1 = writer.alloc_page_id();
5080            let page = Page::new(
5081                p1,
5082                Node::FreeListLeaf(crate::free_lists_tree_nodes::FreeListLeafNode::default()),
5083            );
5084            writer.insert_dirty(page).expect("insert dirty");
5085            mvcc.commit(&mut writer).expect("commit");
5086
5087            // Page should be in cache
5088            {
5089                let cache = mvcc.page_cache.as_ref().unwrap();
5090                assert!(cache.get(&p1).is_some());
5091            }
5092
5093            // Read page
5094            let _read_page = mvcc.read_page(p1).expect("read page");
5095        }
5096
5097        #[test]
5098        #[serial]
5099        fn test_mvcc_page_cache_eviction() {
5100            let temp_dir = tempdir().unwrap();
5101            let db_path = temp_dir.path().join("cache-eviction.db");
5102            let options = StorageOptions::default()
5103                .db_path(&db_path)
5104                .page_cache_max_pages(2);
5105
5106            let mvcc = Mvcc::new(false, options).expect("mvcc new");
5107
5108            // 1. Write 3 pages. Cache limit is 2.
5109            // Commit will try to insert all dirty pages + header.
5110            let mut writer = mvcc.writer().expect("writer");
5111            let p1 = writer.alloc_page_id();
5112            let p2 = writer.alloc_page_id();
5113            let p3 = writer.alloc_page_id();
5114
5115            writer
5116                .insert_dirty(Page::new(p1, Node::FreeListLeaf(Default::default())))
5117                .unwrap();
5118            writer
5119                .insert_dirty(Page::new(p2, Node::FreeListLeaf(Default::default())))
5120                .unwrap();
5121            writer
5122                .insert_dirty(Page::new(p3, Node::FreeListLeaf(Default::default())))
5123                .unwrap();
5124
5125            mvcc.commit(&mut writer).expect("commit");
5126
5127            // Some pages should have been evicted or not admitted if we exceed 2.
5128            // Moka cache might not evict immediately, but let's check entry count.
5129            let cache = mvcc.page_cache.as_ref().unwrap();
5130            // We can't strictly assert count == 2 because eviction is async in moka,
5131            // but we can call run_pending_tasks if available or just wait.
5132            cache.run_pending_tasks();
5133            assert!(cache.entry_count() <= 2);
5134        }
5135    }
5136}
5137
5138#[cfg(test)]
5139mod high_level_mvcc_tests {
5140    use super::*;
5141    use crate::db::UmaDb;
5142    use serial_test::serial;
5143    use std::sync::Arc;
5144    use tempfile::tempdir;
5145    use umadb_dcb::{DcbError, DcbEvent, DcbEventStoreSync};
5146
5147    #[test]
5148    #[serial]
5149    fn test_append_event_with_tag_larger_than_page_size_via_mvcc() {
5150        // This test was created when I realized that even though
5151        // page data and metadata overflows, it may be that the
5152        // tags or the type is so large that it can't possibly
5153        // fit in one page... the append operation should detect
5154        // this before making any changes.
5155        let temp_dir = tempdir().unwrap();
5156        let db_path = temp_dir.path().join("mvcc-high-level-tag.db");
5157        let page_size = 512;
5158
5159        let options = StorageOptions::default()
5160            .db_path(&db_path)
5161            .page_size(page_size);
5162
5163        let mvcc = Mvcc::new(true, options).expect("mvcc new");
5164        let uma = UmaDb::from_arc(Arc::new(mvcc));
5165
5166        let header_before = uma.mvcc.get_latest_header_page().expect("header before");
5167        let header_before = header_before.as_header_node().expect("header before node");
5168        let free_root_before = uma
5169            .mvcc
5170            .read_page(header_before.free_lists_tree_root_id)
5171            .expect("free root before");
5172        let events_root_before = uma
5173            .mvcc
5174            .read_page(header_before.events_tree_root_id)
5175            .expect("events root before");
5176        let tags_root_before = uma
5177            .mvcc
5178            .read_page(header_before.tags_tree_root_id)
5179            .expect("tags root before");
5180
5181        let tsn_before = header_before.tsn;
5182        let next_page_id_before = header_before.next_page_id;
5183        let next_position_before = header_before.next_position;
5184        let free_lists_tree_root_id_before = header_before.free_lists_tree_root_id;
5185        let events_tree_root_id_before = header_before.events_tree_root_id;
5186        let tags_tree_root_id_before = header_before.tags_tree_root_id;
5187        let tracking_root_page_id_before = header_before.tracking_tree_root_id;
5188
5189        let free_root_node_before = free_root_before.node.clone();
5190        let events_root_node_before = events_root_before.node.clone();
5191        let tags_root_node_before = tags_root_before.node.clone();
5192
5193        let large_tag = "t".repeat(600);
5194        let event = DcbEvent::new()
5195            .event_type("Type")
5196            .data(vec![1, 2, 3])
5197            .tags(vec![large_tag]);
5198
5199        println!(
5200            "Attempting to append event with tag of size 600 using UmaDb/Mvcc (page size 512)"
5201        );
5202        let result = uma.append(vec![event], None, None);
5203        match result {
5204            Err(DcbError::InvalidArgument(_)) => {}
5205            other => panic!("Expected InvalidArgument, got {other:?}"),
5206        }
5207
5208        let header_after = uma.mvcc.get_latest_header_page().expect("header after");
5209        let header_after = header_after.as_header_node().expect("header after node");
5210
5211        assert_eq!(tsn_before, header_after.tsn);
5212        assert_eq!(next_page_id_before, header_after.next_page_id);
5213        assert_eq!(next_position_before, header_after.next_position);
5214        assert_eq!(
5215            free_lists_tree_root_id_before,
5216            header_after.free_lists_tree_root_id
5217        );
5218        assert_eq!(events_tree_root_id_before, header_after.events_tree_root_id);
5219        assert_eq!(tags_tree_root_id_before, header_after.tags_tree_root_id);
5220        assert_eq!(
5221            tracking_root_page_id_before,
5222            header_after.tracking_tree_root_id
5223        );
5224
5225        let free_root_after = uma
5226            .mvcc
5227            .read_page(header_after.free_lists_tree_root_id)
5228            .expect("free root after");
5229        let events_root_after = uma
5230            .mvcc
5231            .read_page(header_after.events_tree_root_id)
5232            .expect("events root after");
5233        let tags_root_after = uma
5234            .mvcc
5235            .read_page(header_after.tags_tree_root_id)
5236            .expect("tags root after");
5237
5238        assert_eq!(free_root_node_before, free_root_after.node);
5239        assert_eq!(events_root_node_before, events_root_after.node);
5240        assert_eq!(tags_root_node_before, tags_root_after.node);
5241    }
5242
5243    /// Helper: compute the mmap chunk size the same way `Pager::new` does.
5244    fn compute_chunk_size(page_size: usize) -> u64 {
5245        let os_ps = unsafe {
5246            let sz = libc::sysconf(libc::_SC_PAGESIZE);
5247            if sz <= 0 { 4096usize } else { sz as usize }
5248        };
5249        let g = {
5250            let (mut a, mut b) = (os_ps, page_size);
5251            while b != 0 {
5252                let t = b;
5253                b = a % t;
5254                a = t;
5255            }
5256            a
5257        };
5258        let align_pages = usize::max(1, os_ps / g);
5259        let min_window_bytes: usize = 256 * 1024 * 1024;
5260        let min_pages = min_window_bytes.div_ceil(page_size);
5261        let k = if min_pages == 0 {
5262            1
5263        } else {
5264            min_pages.div_ceil(align_pages)
5265        };
5266        let mmap_pages_per_map = align_pages * usize::max(1, k);
5267        (mmap_pages_per_map * page_size) as u64
5268    }
5269
5270    #[test]
5271    #[serial]
5272    fn test_truncate_below_logical_length_errors_on_reopen() {
5273        let page_size = 4096;
5274        let temp_dir = tempdir().unwrap();
5275        let db_path = temp_dir.path().join("truncate-error.db");
5276
5277        // Create a database and write some events so logical length grows beyond headers.
5278        {
5279            let options = StorageOptions::default()
5280                .db_path(&db_path)
5281                .page_size(page_size);
5282            let mvcc = Mvcc::new(true, options).expect("create db");
5283            let uma = UmaDb::from_arc(Arc::new(mvcc));
5284
5285            for i in 0..5 {
5286                let event = DcbEvent::new()
5287                    .event_type("TestType")
5288                    .data(vec![i; 64])
5289                    .tags(vec![format!("tag-{i}")]);
5290                uma.append(vec![event], None, None).expect("append event");
5291            }
5292        }
5293
5294        // Read the header to find logical length, then truncate below it.
5295        let logical_len = {
5296            let options = StorageOptions::default()
5297                .db_path(&db_path)
5298                .page_size(page_size);
5299            let mvcc = Mvcc::new(true, options).expect("reopen for inspection");
5300            let header = mvcc.get_latest_header_page().expect("header");
5301            let header_node = header.as_header_node().expect("header node");
5302            header_node.next_page_id.0 * (page_size as u64)
5303        };
5304
5305        // Truncate the file below the logical data length.
5306        assert!(logical_len > 0);
5307        let truncate_to = logical_len - (page_size as u64);
5308        {
5309            let file = std::fs::OpenOptions::new()
5310                .write(true)
5311                .open(&db_path)
5312                .expect("open for truncate");
5313            file.set_len(truncate_to).expect("truncate");
5314        }
5315
5316        // Reopening should fail with DatabaseCorrupted.
5317        let result = Mvcc::new(
5318            true,
5319            StorageOptions::default()
5320                .db_path(&db_path)
5321                .page_size(page_size),
5322        );
5323        match result {
5324            Err(DcbError::DatabaseCorrupted(msg)) => {
5325                assert!(
5326                    msg.contains("truncated"),
5327                    "Expected truncation message, got: {msg}"
5328                );
5329            }
5330            Ok(_) => panic!("Expected DatabaseCorrupted error, but Mvcc::new succeeded"),
5331            Err(other) => panic!("Expected DatabaseCorrupted error, got: {other}"),
5332        }
5333    }
5334
5335    #[test]
5336    #[serial]
5337    fn test_truncate_below_aligned_length_recovers_on_reopen() {
5338        let page_size = 4096;
5339        let temp_dir = tempdir().unwrap();
5340        let db_path = temp_dir.path().join("truncate-recover.db");
5341        let chunk_size = compute_chunk_size(page_size);
5342
5343        // Create a database and write some events.
5344        {
5345            let options = StorageOptions::default()
5346                .db_path(&db_path)
5347                .page_size(page_size);
5348            let mvcc = Mvcc::new(true, options).expect("create db");
5349            let uma = UmaDb::from_arc(Arc::new(mvcc));
5350
5351            for i in 0..5 {
5352                let event = DcbEvent::new()
5353                    .event_type("TestType")
5354                    .data(vec![i; 64])
5355                    .tags(vec![format!("tag-{i}")]);
5356                uma.append(vec![event], None, None).expect("append event");
5357            }
5358        }
5359
5360        // Read logical length and the full aligned file size.
5361        let (logical_len, original_file_size) = {
5362            let options = StorageOptions::default()
5363                .db_path(&db_path)
5364                .page_size(page_size);
5365            let mvcc = Mvcc::new(true, options).expect("reopen for inspection");
5366            let header = mvcc.get_latest_header_page().expect("header");
5367            let header_node = header.as_header_node().expect("header node");
5368            let logical = header_node.next_page_id.0 * (page_size as u64);
5369            let file_size = std::fs::metadata(&db_path).expect("metadata").len();
5370            (logical, file_size)
5371        };
5372
5373        // The expected aligned size is logical_len rounded up to the next chunk boundary.
5374        let expected_aligned_len = logical_len.div_ceil(chunk_size) * chunk_size;
5375
5376        // Sanity: the file should already be at the aligned size.
5377        assert_eq!(
5378            original_file_size, expected_aligned_len,
5379            "File should be chunk-aligned before truncation"
5380        );
5381
5382        // Truncate the file to a size above logical data but below the aligned boundary.
5383        // Pick a point halfway between logical_len and expected_aligned_len.
5384        let truncate_to = logical_len + (expected_aligned_len - logical_len) / 2;
5385        assert!(
5386            truncate_to >= logical_len && truncate_to < expected_aligned_len,
5387            "Truncation point {truncate_to} should be in [{logical_len}, {expected_aligned_len})"
5388        );
5389        {
5390            let file = std::fs::OpenOptions::new()
5391                .write(true)
5392                .open(&db_path)
5393                .expect("open for truncate");
5394            file.set_len(truncate_to).expect("truncate");
5395        }
5396
5397        // Verify the file is now shorter than aligned.
5398        let size_after_truncate = std::fs::metadata(&db_path).expect("metadata").len();
5399        assert_eq!(size_after_truncate, truncate_to);
5400
5401        // Reopen — should succeed and recover the alignment.
5402        {
5403            let options = StorageOptions::default()
5404                .db_path(&db_path)
5405                .page_size(page_size);
5406            let _mvcc = Mvcc::new(true, options).expect("reopen should recover alignment");
5407        }
5408
5409        // After recovery, ensure_required_len grows the file from truncate_to by
5410        // whole chunks, so the final size is truncate_to + ceil((expected - truncate_to) / chunk) * chunk.
5411        let extra_needed = expected_aligned_len - truncate_to;
5412        let final_expected = truncate_to + extra_needed.div_ceil(chunk_size) * chunk_size;
5413
5414        let size_after_reopen = std::fs::metadata(&db_path).expect("metadata").len();
5415        assert_eq!(
5416            size_after_reopen, final_expected,
5417            "File should be re-extended to at least the chunk-aligned size after recovery"
5418        );
5419        assert!(
5420            size_after_reopen >= expected_aligned_len,
5421            "Recovered file ({size_after_reopen}) must be at least the expected aligned length ({expected_aligned_len})"
5422        );
5423    }
5424}