Adding a contiguous memory allocator (for large blocks)

pmeunier

Dec 12, 2022, 8:04 PM

XOXTGNPZRTDWNCZ5BI723A6CZ6LLTP4RXIGVWYYK7NQVRWZEZ77AC

Dependencies

• [2] AI4NKV4J Don't load pages past the end of the file
• [3] IIIOKJTE Version bump
• [4] KK3SBH4P Adding sanakirja-core-async
• [5] ECPAFJSB add env_borrow for Txn and MutTxn
• [6] GGEFV4YY Some page splits were not properly handled in deletions
• [7] SYURNHHL Adding the `put_mut` and `set_left_child` methods
• [8] TJ2R4HAZ Accessing the root pages (unsafely, of course)
• [9] W2MIZD5B Single file databases + CRC for the root pages (checking the other pages makes everything very slow)
• [10] PRDUE4YA Cleanup + published on crates.io
• [11] 4Z4GEJTF Version bump
• [12] OP6SVMOD Resetting history
• [13] FQ567GAX Version bumps
• [14] P5NWMJ2H Version bump
• [15] J7LJZBME Setting reverse cursor to last by default
• [16] DASFQGOR Debugging
• [17] WS4ZQM4R Debugging, tests, etc.
• [18] 5LSYTRQ6 More docs, example, and fixing the free page diagnostic function for mutable transactions
• [19] VRAQTH26 Fixing two crashes on corrupted files
• [20] YXKP4AIW New file locks, with multiple sets of free pages
• [21] 2ZRCQBXP Version bump
• [22] 7T2CCH3P Fixing a segfault (wrong offset in page_unsized::del)
• [23] OFINGD26 implementing prev() on cursors (+ some cleanup)
• [24] 77TAHKV4 Fixing a logical error (again) in del
• [25] GPP7KJSF Version bump
• [26] M6PHQUGL fallocate only when necessary
• [27] Z33OHFPA Version bump
• [28] OHG5NX6K Refactoring, drop and the Check trait
• [29] PUOGOIJ3 Debugging, impls and version bump
• [30] BPR2HVMR Version bump
• [31] E4MD6T3L Proofreading and commenting of this crate (massive bug fixes included)
• [32] OHUZ73MK Versions
• [33] WTXLZDYI Fixing bus errors on a full disk
• [34] RLVQDUPY Fixing a double-free error introduced in 1.2.13
• [35] DEKK3RUI Fixing a bug when splitting unsized pages

Change contents

• replacement in sanakirja-core/Cargo.toml at line 3
  [5.70812]→[5.8123:8142](∅→∅)
  − version = "1.2.16"
  [5.70812]

  [5.70847]
  + version = "1.3.0"
• edit in sanakirja/src/environment/muttxn.rs at line 499
  [5.18878]

  [5.88410]
  + }

  + }

  + }

  +

  + /// Allocate many contiguous pages, return the first one

  + fn alloc_contiguous(&mut self, length: u64) -> Result<MutPage, Error> {

  + // Check that length is a multiple of the page size.

  + assert_eq!(length & (PAGE_SIZE as u64 - 1), 0);

  + self.free_owned_pages.sort_by(|a, b| b.cmp(a));

  + self.initial_free.sort_by(|a, b| b.cmp(a));

  + let mut i = self.free_owned_pages.len();

  + let mut ni = 0;

  + let mut j = self.initial_free.len();

  + let mut nj = 0;

  +

  + let mut result = 0u64;

  + let mut current = 0u64;

  + let mut current_p = std::ptr::null_mut();

  + while current + PAGE_SIZE as u64 - result < length {

  + // page allocated, consumed in i, consumed in j

  + let (m, ic, jc) = if i > 0 && j > 0 {

  + let a = self.free_owned_pages[i - 1];

  + let b = self.initial_free[j - 1];

  + if a < b {

  + i -= 1;

  + (a, 1, 0)

  + } else {

  + j -= 1;

  + (b, 0, 1)

  + }

  + } else if i > 0 {

  + i -= 1;

  + (self.free_owned_pages[i], 1, 0)

  + } else if j > 0 {

  + j -= 1;

  + let p = self.initial_free[j];

  + // Check whether p is available for all txns

  + if !self.free_for_all(p)? {

  + // Reset the current block, no free page was consumed.

  + ni = 0;

  + nj = 0;

  + current = result;

  + current_p = unsafe { self.env.borrow().find_offset(current)? };

  + continue;

  + }

  + (p, 0, 1)

  + } else if current == result {

  + // No current region, and we've reached the end of the file, just allocate there.

  + let offset = self.length;

  + let data = unsafe { self.env.borrow().find_offset(offset)? };

  + self.length += length;

  + return Ok(MutPage(CowPage { offset, data }));

  + } else if current + PAGE_SIZE as u64 == self.length {

  + // We've reached the end of the file, grow just one last time.

  + self.length += length - (current + PAGE_SIZE as u64 - result);

  + break;

  + } else {

  + unreachable!()

  + };

  + if current > 0 && m == current + PAGE_SIZE as u64 {

  + // We only have to check whether `current` is actually

  + // contiguous in terms of pointers.

  + let next_p = unsafe { self.env.borrow().find_offset(m)? };

  + if next_p as usize == current_p as usize + PAGE_SIZE {

  + ni += ic;

  + nj += jc;

  + } else {

  + // `m` is the first page in a new map, reset the block

  + result = m;

  + ni = ic;

  + nj = jc;

  + }

  + current = m;

  + current_p = next_p

  + } else {

  + // Initial region

  + result = m;

  + current = m;

  + current_p = unsafe { self.env.borrow().find_offset(m)? };

  + ni = ic;

  + nj = jc;
• edit in sanakirja/src/environment/muttxn.rs at line 581
  [5.88424]

  [5.88424]
  + }

  + for offset in self

  + .free_owned_pages

  + .drain(i..i + ni)

  + .chain(self.initial_free.drain(j..j + nj))

  + {

  + let data = unsafe { self.env.borrow().find_offset(offset)? };

  + self.occupied_owned_pages

  + .push(MutPage(CowPage { data, offset }))
• edit in sanakirja/src/environment/muttxn.rs at line 591
  [5.88434]

  [5.88434]
  +

  + let data = unsafe { self.env.borrow().find_offset(result)? };

  + Ok(MutPage(CowPage {

  + data,

  + offset: result,

  + }))
• replacement in sanakirja/src/environment/muttxn.rs at line 716
  [2.148]→[2.148:192](∅→∅)
  − return Err(Error::Corrupt(off))
  [2.148]

  [2.192]
  + return Err(Error::Corrupt(off));
• edit in sanakirja/src/environment/mod.rs at line 9
  [5.1301]

  [5.1301]
  + use log::*;
• edit in sanakirja/src/environment/mod.rs at line 18
  [5.1533]→[5.20092:20104](∅→∅)
  − use log::*;
• replacement in sanakirja/src/environment/mod.rs at line 177
  [5.155]→[5.155:206](∅→∅)
  − return Err(Error::VersionMismatch)
  [5.155]

  [5.206]
  + return Err(Error::VersionMismatch);
• replacement in sanakirja/src/environment/mod.rs at line 354
  [5.104214]→[5.20241:20369](∅→∅)
  − info!("find_offset, i = {:?}/{:?}, extending, offset = {:?}, length0 = {:?}", i, mmaps.len(), offset, length0);
  [5.104214]

  [5.246]
  + info!(

  + "find_offset, i = {:?}/{:?}, extending, offset = {:?}, length0 = {:?}",

  + i,

  + mmaps.len(),

  + offset,

  + length0

  + );
• edit in sanakirja/src/environment/mod.rs at line 471
  [5.126]→[5.126:127](∅→∅)
  −
• replacement in sanakirja/src/environment/mod.rs at line 472
  [5.157]→[5.157:237](∅→∅)
  − /// Borrow env

  − pub fn env_borrow(&self) -> &Env {

  − self.env.borrow()

  − }
  [5.157]

  [5.105581]
  + /// Borrow env

  + pub fn env_borrow(&self) -> &Env {

  + self.env.borrow()

  + }
• replacement in sanakirja/src/environment/mod.rs at line 573
  [2.732]→[2.732:776](∅→∅)
  − return Err(Error::Corrupt(off))
  [2.732]

  [2.776]
  + return Err(Error::Corrupt(off));
• replacement in sanakirja/src/environment/mod.rs at line 646
  [5.2848]→[5.2848:2965](∅→∅)
  − .ptr

  − .add(self.root * PAGE_SIZE + GLOBAL_HEADER_SIZE + 8 * n)

  − as *mut u64)
  [5.2848]

  [5.18025]
  + .ptr

  + .add(self.root * PAGE_SIZE + GLOBAL_HEADER_SIZE + 8 * n) as *mut u64)
• replacement in sanakirja/Cargo.toml at line 3
  [5.108441]→[3.0:19](∅→∅)
  − version = "1.2.16"
  [5.108441]

  [5.108459]
  + version = "1.3.0"
• replacement in sanakirja/Cargo.toml at line 32
  [5.84]→[5.3965:4033](∅→∅)
  − sanakirja-core = { path = "../sanakirja-core", version = "1.2.16" }
  [5.84]

  [5.5528]
  + sanakirja-core = { path = "../sanakirja-core", version = "1.3.0" }
• replacement in Cargo.toml at line 2
  [5.108848]→[4.221929:221996](∅→∅)
  − members = [ "sanakirja-core", "sanakirja", "sanakirja-core-async" ]
  [5.108848]
  + members = [ "sanakirja-core", "sanakirja", "sanakirja-core-async", "bla" ]