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;
20use 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#[derive(Debug, Default)]
124pub struct ReaderTsnRegistry {
125 counts: Mutex<BTreeMap<Tsn, usize>>,
126}
127
128impl ReaderTsnRegistry {
129 pub fn register(&self, tsn: Tsn) {
131 let mut counts = self.counts.lock();
132 *counts.entry(tsn).or_insert(0) += 1;
133 }
134
135 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 pub fn min(&self) -> Option<Tsn> {
149 self.counts.lock().first_key_value().map(|(&tsn, _)| tsn)
150 }
151
152 #[cfg(test)]
154 pub fn live_reader_count(&self) -> usize {
155 self.counts.lock().values().copied().sum()
156 }
157
158 #[cfg(test)]
160 pub fn contains_tsn(&self, tsn: Tsn) -> bool {
161 self.counts.lock().contains_key(&tsn)
162 }
163
164 #[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
214pub 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 }
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 set_tag_key_width(crate::tags_tree_nodes::TAG_HASH_LEN);
308
309 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 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 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 };
361
362 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 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 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 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 mvcc.fsync()?;
393
394 mvcc.write_header(&header1)?;
395 mvcc.write_header(&header0)?;
396
397 mvcc.fsync()?;
399
400 Ok(mvcc)
401 } else {
402 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 };
454
455 if let Ok(header_page) = mvcc.get_latest_header_page() {
457 let header_node = header_page.as_header_node()?;
458
459 mvcc.rw.pager.verify_file_size(header_node.next_page_id)?;
461
462 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 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 if header_node.schema_version == 1 {
480 use crate::node::Node;
481 let tags_root = header_node.tags_tree_root_id;
482 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 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 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 if let Some(ref page_cache) = self.page_cache {
617 let page = page_cache
618 .try_get_with(page_id, || {
619 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 reader(&self) -> DcbResult<Reader> {
695 loop {
697 let header_page = self.get_latest_header_page()?;
699 let header_node = header_page.as_header_node()?;
700
701 let tsn = header_node.tsn;
703 self.reader_tsns.register(tsn);
704
705 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 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 let header_page = self.get_latest_header_page()?;
736 let header_node = header_page.as_header_node()?;
737
738 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 writer.find_reusable_page_ids(self)?;
759
760 Ok(writer)
761 }
762
763 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 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 let chunked_pages = pages_vec.chunk_by(|a, b| a.page_id.0 + 1 == b.page_id.0);
781
782 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 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 let needed_buf = &mut writer_buffer[..needed_bytes];
795
796 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 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 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 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 self.fsync()?;
838
839 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 let next_header_page = writer.cow_header_page()?;
850 self.write_header(&next_header_page)?;
851
852 self.fsync()?;
854
855 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 let dirty_header = writer.cow_header_page()?;
877 let next_header_page_id = dirty_header.page_id;
878
879 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 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 for (page_id, page) in writer.dirty.drain() {
895 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 wet_pages.insert(page_id, Arc::new(page));
904 }
905
906 let wet_header = Arc::new(dirty_header);
908
909 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 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 pub base_mvcc: &'a Mvcc,
956
957 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 if let Some(wet_page) = self.wet_pages.get(&page_id) {
966 return Ok(wet_page.clone());
967 }
968
969 self.base_mvcc.read_page(page_id)
971 }
972}
973
974pub 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 let header_page = mvcc.get_latest_header_page()?;
1033 let header_node = header_page.as_header_node()?;
1034
1035 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 self.find_reusable_page_ids(mvcc)?;
1051
1052 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 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 pub fn get_page_ref<T: MvccSnapshot>(&mut self, mvcc: &T, page_id: PageID) -> DcbResult<&Page> {
1086 if let Some(page) = self.dirty.get(&page_id) {
1088 return Ok(page);
1089 }
1090
1091 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 if self.freed_page_ids.contains(&page_id) {
1139 return Err(DcbError::PageAlreadyFreed(page_id.0));
1140 }
1141
1142 if self.dirty.contains_key(&page_id) {
1144 return Ok(page_id);
1148 }
1149
1150 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 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 let smallest_reader_tsn = mvcc.reader_tsns.min();
1184 self.find_reusable_page_ids_with_snapshot(mvcc, smallest_reader_tsn)
1185 }
1186
1187 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 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 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 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 let mut pages_vec: Vec<(PageID, Tsn)> = reusable_page_ids.into();
1319 pages_vec.sort_unstable_by_key(|(pid, _)| pid.0);
1320
1321 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 extents.sort_unstable_by(|a, b| {
1344 b.len()
1346 .cmp(&a.len())
1347 .then(a[0].0.cmp(&b[0].0))
1349 });
1350
1351 let extents_count = extents.len();
1352
1353 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 while let Some((reused_page_id, tsn)) = self.reused_page_ids.pop_front() {
1379 self.remove_free_page_id(snapshot, tsn, reused_page_id)?;
1381 }
1382
1383 let freed_page_ids = std::mem::take(&mut self.freed_page_ids);
1387
1388 for freed_page_id in freed_page_ids {
1389 self.dirty.remove(&freed_page_id);
1391
1392 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 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 let mut current_page_id = self.free_lists_tree_root_id;
1421
1422 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) = ¤t_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 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 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 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) = ¤t_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 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 let mut split_info: Option<(Tsn, PageID)> = None;
1493
1494 match plan {
1496 FreePageIDInsertStrategy::PushPageIdOntoExistingTsnSubtree => {
1497 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 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 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 page_ids.sort_by_key(|pid| pid.0);
1537 page_ids.dedup();
1538 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 let mut tsn_root_id = tsn_leaf_id;
1565 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 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 _ => { }
1584 }
1585
1586 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 => { }
1610 FreePageIDInsertStrategy::MoveTsnToNewTsnSubtree => { }
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 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 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 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 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 let mut current_replacement_info = replacement_info;
1681 while let Some(parent_page_id) = stack.pop() {
1682 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 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 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 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 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 let (promoted_key, new_keys, new_child_ids) =
1747 dirty_internal_node.split_off()?;
1748
1749 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 assert_eq!(
1762 new_internal_node.keys.len() + 1,
1763 new_internal_node.child_ids.len()
1764 );
1765
1766 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 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 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 ¤t_page_ref.node {
1842 Node::FreeListTsnLeaf(_) => break,
1843 Node::FreeListTsnInternal(internal) => {
1844 let child_idx = match internal.keys.binary_search_by(|k| k.0.cmp(&key.0)) {
1846 Ok(idx) => idx + 1, Err(idx) => idx, };
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 {
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 match leaf.page_ids.binary_search_by(|pid| pid.0.cmp(&key.0)) {
1873 Ok(_) => {
1874 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 let mid = leaf.page_ids.len() / 2; let right_ids: Vec<PageID> = leaf.page_ids.split_off(mid);
1887 let promoted_key = right_ids[0];
1888 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 let mut promoted: Option<(PageID, PageID)> =
1898 Some((promoted_key, right_leaf_id));
1899 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 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 current_id = parent_id;
1916 continue;
1917 }
1918 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; let promote_up_key = parent_node.keys[mid];
1926 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 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 parent_node.keys = left_keys;
1948 parent_node.child_ids = left_child_ids;
1949 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 promoted = Some((promote_up_key, right_internal_id));
1963 }
1964 current_id = parent_id;
1965 }
1966 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 let mut current_page_id = self.free_lists_tree_root_id;
2002
2003 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) = ¤t_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 let mut replacement_info: Option<(PageID, PageID)> = None;
2035 let mut removal_info = None;
2036
2037 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 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 if leaf_value_root_id == PageID(0) {
2064 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 let tsn_root_id = leaf_value_root_id;
2111 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 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; }
2160 Node::FreeListTsnInternal(internal) => {
2161 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 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 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 let parent_dirty_id = { self.get_dirty_page_id(parent_id)? };
2223
2224 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 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 match parent_node.child_ids.len() {
2248 0 => {
2249 subtree_emptied = true;
2251 removed_page_ids.push(parent_dirty_id);
2252 }
2253 1 => {
2254 let remaining_child = parent_node.child_ids[0];
2256 removed_page_ids.push(parent_dirty_id);
2257 dirty_child_id = remaining_child;
2259 new_root_id_opt = Some(remaining_child);
2260 }
2261 _ => {
2262 dirty_child_id = parent_dirty_id;
2264 if level == path_len - 1 {
2265 new_root_id_opt = Some(parent_dirty_id);
2267 }
2268 }
2269 }
2270 } else {
2271 if parent_node.child_ids[child_idx] != dirty_child_id {
2273 parent_node.child_ids[child_idx] = dirty_child_id;
2274 }
2275 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 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 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 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 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 dirty_leaf_node.values[leaf_idx].root_id = new_root;
2332 } else if dirty_tsn_root_id != tsn_root_id {
2333 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 let mut current_replacement_info = replacement_info;
2345
2346 while let Some((parent_page_id, child_idx)) = stack.pop() {
2347 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 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 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 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 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 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
2483pub 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 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 {
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 {
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 {
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 {
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 {
2664 let mut writer = db.writer().unwrap();
2665
2666 assert_eq!(0, writer.reusable_page_ids.len());
2668
2669 assert_eq!(PageID(2), writer.free_lists_tree_root_id);
2671
2672 assert_eq!(PageID(3), writer.events_tree_root_id);
2674
2675 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 assert_eq!(1, writer.dirty.len());
2690 assert_eq!(PageID(6), *writer.dirty.keys().collect::<Vec<_>>()[0]);
2691
2692 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 {
2701 let mut writer = db.writer().unwrap();
2702
2703 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 assert_eq!(PageID(6), writer.free_lists_tree_root_id);
2710
2711 assert_eq!(PageID(3), writer.events_tree_root_id);
2713
2714 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 assert_eq!(1, writer.dirty.len());
2729 assert_eq!(PageID(5), *writer.dirty.keys().collect::<Vec<_>>()[0]);
2730
2731 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 {
2740 let mut writer = db.writer().unwrap();
2741
2742 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 assert_eq!(PageID(5), writer.free_lists_tree_root_id);
2749
2750 assert_eq!(PageID(3), writer.events_tree_root_id);
2752
2753 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 assert_eq!(1, writer.dirty.len());
2768 assert_eq!(PageID(6), *writer.dirty.keys().collect::<Vec<_>>()[0]);
2769
2770 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 mod free_list_tree_tests {
2780 use super::*;
2781 use serial_test::serial;
2782 use tempfile::tempdir;
2783
2784 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 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 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 writer.find_reusable_page_ids(&db).unwrap();
2833 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 writer.find_reusable_page_ids(&db).unwrap();
2852 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 writer.find_reusable_page_ids(&db).unwrap();
2874 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 writer.find_reusable_page_ids(&db).unwrap();
2891 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 writer.find_reusable_page_ids(&db).unwrap();
2910 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 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 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 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 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 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 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 writer
3110 .insert_dirty(Page::new(
3111 tsn_sub_leaf_id,
3112 Node::FreeListTsnLeaf(tsn_sub_leaf),
3113 ))
3114 .unwrap();
3115
3116 let tsn = Tsn(33); 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 let root_id = writer.alloc_page_id();
3129 writer
3130 .insert_dirty(Page::new(root_id, Node::FreeListLeaf(leaf)))
3131 .unwrap();
3132
3133 writer.append_freed_page_id(writer.free_lists_tree_root_id);
3135 writer.free_lists_tree_root_id = root_id;
3137
3138 (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 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 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 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 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 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 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 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 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 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 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 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 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 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 assert_eq!(PageID(5), header_node.next_page_id);
3343
3344 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 let initial_root_id = writer.free_lists_tree_root_id;
3363 assert_eq!(PageID(2), initial_root_id);
3364
3365 let page_id = writer.alloc_page_id();
3367
3368 assert_eq!(header_node.next_page_id, page_id);
3370
3371 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 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 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 let mut writer;
3412 let inserted_tsn;
3413 let inserted_page_id;
3414 let previous_root_id;
3415
3416 {
3417 writer = db.writer().unwrap();
3419
3420 previous_root_id = writer.free_lists_tree_root_id;
3422
3423 inserted_page_id = writer.alloc_page_id();
3425
3426 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 db.commit(&mut writer).unwrap();
3440 }
3441
3442 {
3444 db.reader_tsns.register(Tsn(0));
3445 }
3446
3447 {
3449 writer = db.writer().unwrap();
3450
3451 assert_eq!(0, writer.reusable_page_ids.len());
3453
3454 let initial_root_id = writer.free_lists_tree_root_id;
3456 let next_page_id = writer.next_page_id;
3457
3458 writer
3460 .remove_free_page_id(&db, inserted_tsn, inserted_page_id)
3461 .unwrap();
3462
3463 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 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 let header_page = db.get_latest_header_page().unwrap();
3499 let header_node = header_page.as_header_node().unwrap();
3500
3501 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 while !has_split_leaf {
3522 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 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 tsn = Tsn(tsn.0 + 1);
3538
3539 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 let mut copy_inserted = inserted.clone();
3551
3552 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 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 let mut freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
3570
3571 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 if i > 0 {
3585 assert_eq!(root_node.keys[i - 1], child_node.keys[0]);
3586 }
3587
3588 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 assert_eq!(7, active_page_ids.len());
3601
3602 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 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 {
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 while !has_split_leaf {
3637 let mut writer = db.writer().unwrap();
3639 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 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 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 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 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 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 let mut freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
3717
3718 for (i, &child_id) in root_node.child_ids.iter().enumerate() {
3720 active_page_ids.push(child_id);
3721
3722 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 if i > 0 {
3733 assert_eq!(root_node.keys[i - 1], child_node.keys[0]);
3734 }
3735
3736 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 assert_eq!(8, active_page_ids.len());
3746
3747 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 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 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 let mut writer = db.writer().unwrap();
3783
3784 previous_root_id = writer.free_lists_tree_root_id;
3786
3787 let mut has_split_leaf = false;
3789 let mut tsn = writer.tsn;
3790
3791 while !has_split_leaf {
3792 tsn = Tsn(tsn.0 + 1);
3794
3795 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 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 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 writer.tsn = Tsn(tsn.0 + 1);
3821 previous_writer_tsn = writer.tsn;
3822
3823 db.commit(&mut writer).unwrap();
3825 }
3826
3827 if VERBOSE {
3829 println!();
3830 println!("Removing all inserted page IDs......");
3831 }
3832
3833 {
3834 let header_page = db.get_latest_header_page().unwrap();
3836 let header_node = header_page.as_header_node().unwrap();
3837
3838 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 let old_root_id = writer.free_lists_tree_root_id;
3855
3856 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 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 let freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
3875 assert!(freed_page_ids.contains(&old_root_id));
3876
3877 assert_eq!(5, writer.freed_page_ids.len());
3880
3881 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 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 let mut all_freed_page_ids = freed_page_ids.clone();
3907
3908 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 let inserted_page_ids: Vec<PageID> = inserted.iter().map(|(_, id)| *id).collect();
3920
3921 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 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 let header_page = db.get_latest_header_page().unwrap();
3942 let header_node = header_page.as_header_node().unwrap();
3943
3944 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 let mut tsn = Tsn(100);
3961 let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
3962 let mut has_split_internal = false;
3963
3964 while !has_split_internal {
3966 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 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 tsn = Tsn(tsn.0 + 1);
3982
3983 let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
3985 match &root_page.node {
3986 Node::FreeListInternal(root_node) => {
3987 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 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 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 let mut freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
4025
4026 let mut previous_child: Option<&FreeListInternalNode> = None;
4028
4029 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 if i > 0 {
4043 assert!(root_node.keys[i - 1] < child_node.keys[0]);
4044
4045 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 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 if j > 0 {
4067 assert_eq!(child_node.keys[j - 1], grand_child_node.keys[0]);
4068 }
4069
4070 for (k, &key) in grand_child_node.keys.iter().enumerate() {
4072 for &value in &grand_child_node.values[k].page_ids {
4073 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 assert!(inserted.is_empty());
4086
4087 assert_eq!(11, active_page_ids.len());
4089
4090 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 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 let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
4108 let previous_root_id;
4109 let previous_writer_tsn;
4110
4111 {
4112 let mut writer = db.writer().unwrap();
4114
4115 previous_root_id = writer.free_lists_tree_root_id;
4117
4118 let mut has_split_internal = false;
4120 let mut tsn = writer.tsn;
4121
4122 while !has_split_internal {
4123 tsn = Tsn(tsn.0 + 1);
4125 writer.tsn = tsn;
4126
4127 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 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 let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
4143 match &root_page.node {
4144 Node::FreeListInternal(root_node) => {
4145 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 previous_writer_tsn = writer.tsn;
4164
4165 db.commit(&mut writer).unwrap();
4167 }
4168
4169 {
4171 let header_page = db.get_latest_header_page().unwrap();
4173 let header_node = header_page.as_header_node().unwrap();
4174
4175 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 let old_root_id = writer.free_lists_tree_root_id;
4192
4193 for (tsn, page_id) in inserted.iter() {
4195 writer.remove_free_page_id(&db, *tsn, *page_id).unwrap();
4196 }
4197
4198 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 let freed_page_ids: Vec<PageID> = writer.freed_page_ids.iter().cloned().collect();
4208 assert!(freed_page_ids.contains(&old_root_id));
4209
4210 assert_eq!(13, writer.freed_page_ids.len());
4213
4214 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 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 let mut all_freed_page_ids = freed_page_ids.clone();
4240
4241 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 let inserted_page_ids: Vec<PageID> = inserted.iter().map(|(_, id)| *id).collect();
4253
4254 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 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 let (_temp_dir, db) = construct_mvcc(128);
4282
4283 let mut inserted: Vec<(Tsn, PageID)> = Vec::new();
4285
4286 {
4287 let mut writer = db.writer().unwrap();
4289
4290 let mut has_split_internal = false;
4292 let mut tsn = writer.tsn;
4293
4294 while !has_split_internal {
4295 tsn = Tsn(tsn.0 + 1);
4297 writer.tsn = tsn;
4298
4299 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 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 let root_page = writer.dirty.get(&writer.free_lists_tree_root_id).unwrap();
4315 match &root_page.node {
4316 Node::FreeListInternal(root_node) => {
4317 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 db.commit(&mut writer).unwrap();
4336 }
4337
4338 db.reader_tsns.unregister(Tsn(0));
4340 let writer = db.writer().unwrap();
4341 let reusable_page_ids = writer.reusable_page_ids.clone();
4342
4343 db.reader_tsns.register(Tsn(0));
4345
4346 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 let page_size = 64;
4359 let (_temp_dir, db) = construct_mvcc(page_size);
4360
4361 let mut writer = db.writer().unwrap();
4363 let tsn = writer.tsn;
4364
4365 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 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 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 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 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 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 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 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 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 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 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 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 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 for i in 0..pids.len() {
4567 let j = (i * 37 + 13) % pids.len();
4568 pids.swap(i, j);
4569 }
4570 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 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 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 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 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 }
4617 }
4618 Node::FreeListTsnLeaf(_) => {
4619 }
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 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 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 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 let mut extra_ids = Vec::new();
4656 for _ in 0..30 {
4657 extra_ids.push(writer.alloc_page_id());
4658 }
4659 for i in 0..extra_ids.len() {
4661 let j = (i * 29 + 7) % extra_ids.len();
4662 extra_ids.swap(i, j);
4663 }
4664 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 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 let (_temp_dir, db) = construct_mvcc(128);
4717 let mut writer = db.writer().unwrap();
4718
4719 writer.tsn = Tsn(40);
4721
4722 let (pid1, pid2, tsn1) = build_free_list_tree_leaf_tsn_subtree_leaf(&mut writer);
4724
4725 writer.freed_page_ids.clear();
4727 db.commit(&mut writer).unwrap();
4728
4729 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 writer.remove_free_page_id(&db, tsn1, pid1).unwrap();
4740 assert_eq!(2, writer.freed_page_ids.len());
4741 writer.remove_free_page_id(&db, tsn1, pid2).unwrap();
4743 assert_eq!(3, writer.freed_page_ids.len());
4744
4745 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 let (_temp_dir, db) = construct_mvcc(128);
4819
4820 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 db.commit(&mut w1).unwrap();
4827 tsn
4829 };
4830
4831 let mut w2 = db.writer().unwrap();
4833 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); w2.remove_free_page_id(&db, remove_tsn, remove_pid).unwrap();
4839
4840 let mut active: Vec<PageID> = Vec::new();
4843 let mut freed_tree: Vec<PageID> = Vec::new();
4844 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 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 for val in &leaf.values {
4867 for &p in &val.page_ids {
4868 freed_tree.push(p);
4869 }
4870 }
4871 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 for (&pid, _page) in w2.dirty.iter() {
4903 if !active.contains(&pid) {
4904 active.push(pid);
4905 }
4906 }
4907 for (&pid, _page) in w2.deserialized.iter() {
4909 if !active.contains(&pid) {
4910 active.push(pid);
4911 }
4912 }
4913
4914 let mut freed: Vec<PageID> = w2.freed_page_ids.iter().cloned().collect();
4916 freed.extend(freed_tree);
4918 for (pid, _tsn) in w2.reusable_page_ids.iter() {
4920 freed.push(*pid);
4921 }
4922
4923 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 let temp_dir = tempdir().unwrap();
4973 let db_path = temp_dir.path().join("schema-guard.db");
4974 let page_size = 64usize; 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 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 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 mvcc.fsync().ok();
5004
5005 drop(mvcc);
5007
5008 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 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 {
5057 let cache = mvcc.page_cache.as_ref().unwrap();
5058 assert!(cache.get(&p1).is_some());
5059 }
5060
5061 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); let mvcc = Mvcc::new(false, options).expect("mvcc new");
5075 assert!(mvcc.page_cache.is_some());
5076
5077 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 {
5089 let cache = mvcc.page_cache.as_ref().unwrap();
5090 assert!(cache.get(&p1).is_some());
5091 }
5092
5093 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 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 let cache = mvcc.page_cache.as_ref().unwrap();
5130 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 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 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 {
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 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 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 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 {
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 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 let expected_aligned_len = logical_len.div_ceil(chunk_size) * chunk_size;
5375
5376 assert_eq!(
5378 original_file_size, expected_aligned_len,
5379 "File should be chunk-aligned before truncation"
5380 );
5381
5382 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 let size_after_truncate = std::fs::metadata(&db_path).expect("metadata").len();
5399 assert_eq!(size_after_truncate, truncate_to);
5400
5401 {
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 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}