Repository: cberner/redb
Pull request #216 (2022-03-07 06:08:13)

Refactor of allocator code & remove Database::resize()


Patch:
diff --git a/src/db.rs b/src/db.rs
index cb469de..ef93009 100644
--- a/src/db.rs
+++ b/src/db.rs
@@ -1,8 +1,7 @@
 use crate::multimap_table::MultimapTable;
 use crate::table::{ReadOnlyTable, Table};
 use crate::tree_store::{
-    expand_db_size, get_db_size, DatabaseStats, PageNumber, Storage, TableType, TransactionId,
-    FREED_TABLE,
+    get_db_size, DatabaseStats, PageNumber, Storage, TableType, TransactionId, FREED_TABLE,
 };
 use crate::types::{RedbKey, RedbValue};
 use crate::Result;
@@ -127,17 +126,6 @@ impl Database {
         DatabaseBuilder::new()
     }
 
-    /// # Safety
-    ///
-    /// The file referenced by `path` must not be concurrently modified by any other process
-    pub unsafe fn resize(path: impl AsRef<Path>, new_size: usize) -> Result {
-        expand_db_size(path.as_ref(), new_size)?;
-        // Open the database to rebuild the allocator state
-        Self::create(path, new_size)?;
-
-        Ok(())
-    }
-
     pub fn begin_write(&self) -> Result<WriteTransaction> {
         WriteTransaction::new(&self.storage)
     }
diff --git a/src/tree_store/mod.rs b/src/tree_store/mod.rs
index 6905a8f..bf6631f 100644
--- a/src/tree_store/mod.rs
+++ b/src/tree_store/mod.rs
@@ -7,6 +7,6 @@ mod storage;
 pub use btree_base::AccessGuard;
 pub(crate) use btree_base::AccessGuardMut;
 pub(crate) use btree_iters::BtreeRangeIter;
-pub(crate) use page_store::{expand_db_size, get_db_size, PageNumber};
+pub(crate) use page_store::{get_db_size, PageNumber};
 pub use storage::DatabaseStats;
 pub(crate) use storage::{Storage, TableType, TransactionId, FREED_TABLE};
diff --git a/src/tree_store/page_store/buddy_allocator.rs b/src/tree_store/page_store/buddy_allocator.rs
new file mode 100644
index 0000000..2b722e0
--- /dev/null
+++ b/src/tree_store/page_store/buddy_allocator.rs
@@ -0,0 +1,264 @@
+use crate::tree_store::page_store::page_allocator::PageAllocator;
+use crate::Error;
+use crate::Result;
+use std::mem::size_of;
+
+#[derive(Clone)]
+pub(crate) struct BuddyAllocator {
+    orders: Vec<PageAllocator>,
+}
+
+// Handles allocation of dynamically sized pages, supports pages of up to page_size * 2^max_order bytes
+//
+// Pages are marked free at only a single order, and it must always be the largest order
+//
+// Data structure format:
+// max_order: big endian u64
+// order_offsets: array of (u64, u64), with offset & length for PageAllocator structure for the given order
+// ... PageAllocator structures
+impl BuddyAllocator {
+    pub(crate) fn new(mut num_pages: usize, max_order: usize) -> Self {
+        let mut orders = vec![];
+        for _ in 0..=max_order {
+            orders.push(PageAllocator::new(num_pages));
+            num_pages = Self::next_higher_order(num_pages as u64) as usize;
+        }
+
+        Self { orders }
+    }
+
+    pub(crate) fn init_new(data: &mut [u8], mut num_pages: usize, max_order: usize) -> Self {
+        assert!(data.len() >= Self::required_space(num_pages, max_order));
+        data[..size_of::<u64>()].copy_from_slice(&(max_order as u64).to_be_bytes());
+
+        let mut metadata_offset = size_of::<u64>();
+        let mut data_offset = size_of::<u64>() + 2 * (max_order + 1) * size_of::<u64>();
+
+        let mut orders = vec![];
+        for order in 0..=max_order {
+            let required = PageAllocator::required_space(num_pages);
+            data[metadata_offset..metadata_offset + size_of::<u64>()]
+                .copy_from_slice(&(data_offset as u64).to_be_bytes());
+            data[metadata_offset + size_of::<u64>()..metadata_offset + 2 * size_of::<u64>()]
+                .copy_from_slice(&(required as u64).to_be_bytes());
+            orders.push(PageAllocator::init_new(
+                Self::get_order_bytes_mut(data, order),
+                num_pages,
+            ));
+            num_pages = Self::next_higher_order(num_pages as u64) as usize;
+            metadata_offset += 2 * size_of::<u64>();
+            data_offset += required;
+        }
+
+        // Mark all the lower pages which exist in upper orders
+        for (order, allocator) in orders.iter().enumerate() {
+            if let Some(next_allocator) = orders.get(order + 1) {
+                let next_bytes = Self::get_order_bytes_mut(data, order + 1);
+                let next_pages = next_allocator.count_free_pages(next_bytes) as u64;
+                let bytes = Self::get_order_bytes_mut(data, order);
+                for i in 0..(2 * next_pages) {
+                    allocator.record_alloc(bytes, i);
+                }
+            }
+        }
+
+        Self { orders }
+    }
+
+    /// Returns the number of bytes required for the data argument of new()
+    pub(crate) fn required_space(mut num_pages: usize, max_order: usize) -> usize {
+        let mut required = size_of::<u64>() + 2 * (max_order + 1) * size_of::<u64>();
+        for _ in 0..=max_order {
+            required += PageAllocator::required_space(num_pages);
+            num_pages = Self::next_higher_order(num_pages as u64) as usize;
+        }
+
+        required
+    }
+
+    pub(crate) fn count_free_pages(&self, data: &[u8]) -> usize {
+        let mut pages = 0;
+        for (order, allocator) in self.orders.iter().enumerate() {
+            pages += allocator.count_free_pages(Self::get_order_bytes(data, order))
+                * 2usize.pow(order as u32);
+        }
+
+        pages
+    }
+
+    fn get_order_offset_and_length(data: &[u8], order: usize) -> (usize, usize) {
+        let max_order = u64::from_be_bytes(data[..size_of::<u64>()].try_into().unwrap()) as usize;
+        assert!(order <= max_order);
+        let base = size_of::<u64>() + order * 2 * size_of::<u64>();
+        let offset =
+            u64::from_be_bytes(data[base..base + size_of::<u64>()].try_into().unwrap()) as usize;
+        let length = u64::from_be_bytes(
+            data[base + size_of::<u64>()..base + 2 * size_of::<u64>()]
+                .try_into()
+                .unwrap(),
+        ) as usize;
+
+        (offset, length)
+    }
+
+    fn get_order_bytes(data: &[u8], order: usize) -> &[u8] {
+        let (offset, length) = Self::get_order_offset_and_length(data, order);
+        &data[offset..(offset + length)]
+    }
+
+    fn get_order_bytes_mut(data: &mut [u8], order: usize) -> &mut [u8] {
+        let (offset, length) = Self::get_order_offset_and_length(data, order);
+        &mut data[offset..(offset + length)]
+    }
+
+    fn next_higher_order(page_number: u64) -> u64 {
+        page_number / 2
+    }
+
+    fn buddy_page(page_number: u64) -> u64 {
+        page_number ^ 1
+    }
+
+    /// data must have been initialized by Self::init_new()
+    pub(crate) fn alloc(&self, data: &mut [u8], order: usize) -> Result<u64> {
+        if order >= self.orders.len() {
+            return Err(Error::OutOfSpace);
+        }
+        match self.orders[order].alloc(Self::get_order_bytes_mut(data, order)) {
+            Ok(x) => Ok(x),
+            Err(e) => {
+                match e {
+                    Error::OutOfSpace => {
+                        // Try to allocate a higher order page and split it
+                        let upper_page = self.alloc(data, order + 1)?;
+                        let (free1, free2) = (upper_page * 2, upper_page * 2 + 1);
+                        debug_assert!(self.orders[order]
+                            .is_allocated(Self::get_order_bytes_mut(data, order), free1));
+                        debug_assert!(self.orders[order]
+                            .is_allocated(Self::get_order_bytes_mut(data, order), free2));
+                        self.orders[order].free(Self::get_order_bytes_mut(data, order), free2);
+
+                        Ok(free1)
+                    }
+                    other => Err(other),
+                }
+            }
+        }
+    }
+
+    /// data must have been initialized by Self::init_new(), and page_number must be free
+    pub(crate) fn record_alloc(&self, data: &mut [u8], page_number: u64, order: usize) {
+        assert!(order < self.orders.len());
+        if self.orders[order].is_allocated(Self::get_order_bytes_mut(data, order), page_number) {
+            // Need to split parent page
+            let upper_page = Self::next_higher_order(page_number);
+            self.record_alloc(data, upper_page, order + 1);
+
+            let (free1, free2) = (upper_page * 2, upper_page * 2 + 1);
+            debug_assert!(free1 == page_number || free2 == page_number);
+            if free1 == page_number {
+                self.orders[order].free(Self::get_order_bytes_mut(data, order), free2);
+            } else {
+                self.orders[order].free(Self::get_order_bytes_mut(data, order), free1);
+            }
+        } else {
+            self.orders[order].record_alloc(Self::get_order_bytes_mut(data, order), page_number);
+        }
+    }
+
+    /// data must have been initialized by Self::init_new()
+    pub(crate) fn free(&self, data: &mut [u8], page_number: u64, order: usize) {
+        if order == self.orders.len() - 1 {
+            self.orders[order].free(Self::get_order_bytes_mut(data, order), page_number);
+            return;
+        }
+
+        let buddy = Self::buddy_page(page_number);
+        if self.orders[order].is_allocated(Self::get_order_bytes_mut(data, order), buddy) {
+            self.orders[order].free(Self::get_order_bytes_mut(data, order), page_number);
+        } else {
+            // Merge into higher order page
+            self.orders[order].record_alloc(Self::get_order_bytes_mut(data, order), buddy);
+            self.free(data, Self::next_higher_order(page_number), order + 1);
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use crate::tree_store::page_store::buddy_allocator::BuddyAllocator;
+    use crate::Error;
+
+    #[test]
+    fn record_alloc_buddy() {
+        let num_pages = 256;
+        let max_order = 7;
+        let mut data = vec![0; BuddyAllocator::required_space(num_pages, max_order)];
+        let allocator = BuddyAllocator::init_new(&mut data, num_pages, max_order);
+        assert_eq!(allocator.count_free_pages(&data), num_pages);
+
+        for page in 0..num_pages {
+            allocator.record_alloc(&mut data, page as u64, 0);
+        }
+        assert_eq!(allocator.count_free_pages(&data), 0);
+
+        assert!(matches!(
+            allocator.alloc(&mut data, 0).unwrap_err(),
+            Error::OutOfSpace
+        ));
+
+        for page in 0..num_pages {
+            allocator.free(&mut data, page as u64, 0);
+        }
+        assert_eq!(allocator.count_free_pages(&data), num_pages);
+    }
+
+    #[test]
+    fn buddy_merge() {
+        let num_pages = 256;
+        let max_order = 7;
+        let mut data = vec![0; BuddyAllocator::required_space(num_pages, max_order)];
+        let allocator = BuddyAllocator::init_new(&mut data, num_pages, max_order);
+        assert_eq!(allocator.count_free_pages(&data), num_pages);
+
+        for _ in 0..num_pages {
+            allocator.alloc(&mut data, 0).unwrap();
+        }
+        for page in 0..num_pages {
+            allocator.free(&mut data, page as u64, 0);
+        }
+        assert_eq!(allocator.count_free_pages(&data), num_pages);
+
+        // Test that everything got merged back together, so that we fill order 7 allocations
+        for _ in 0..(num_pages / 2usize.pow(7)) {
+            allocator.alloc(&mut data, 7).unwrap();
+        }
+    }
+
+    #[test]
+    fn alloc_large() {
+        let num_pages = 256;
+        let max_order = 7;
+        let mut data = vec![0; BuddyAllocator::required_space(num_pages, max_order)];
+        let allocator = BuddyAllocator::init_new(&mut data, num_pages, max_order);
+        assert_eq!(allocator.count_free_pages(&data), num_pages);
+
+        let mut allocated = vec![];
+        for order in 0..=max_order {
+            allocated.push((allocator.alloc(&mut data, order).unwrap(), order));
+        }
+        assert_eq!(allocator.count_free_pages(&data), 1);
+
+        for order in 1..=max_order {
+            assert!(matches!(
+                allocator.alloc(&mut data, order).unwrap_err(),
+                Error::OutOfSpace
+            ));
+        }
+
+        for (page, order) in allocated {
+            allocator.free(&mut data, page, order);
+        }
+        assert_eq!(allocator.count_free_pages(&data), num_pages);
+    }
+}
diff --git a/src/tree_store/page_store/grouped_bitmap.rs b/src/tree_store/page_store/grouped_bitmap.rs
new file mode 100644
index 0000000..64e0ccc
--- /dev/null
+++ b/src/tree_store/page_store/grouped_bitmap.rs
@@ -0,0 +1,76 @@
+// A bitmap which groups consecutive groups of 64bits together
+
+use std::mem::size_of;
+
+pub(crate) struct U64GroupedBitMap<'a> {
+    data: &'a [u8],
+}
+
+impl<'a> U64GroupedBitMap<'a> {
+    pub(crate) fn new(data: &'a [u8]) -> Self {
+        assert_eq!(data.len() % 8, 0);
+        Self { data }
+    }
+
+    pub(crate) fn count_unset(&self) -> usize {
+        self.data.iter().map(|x| x.count_zeros() as usize).sum()
+    }
+}
+
+pub(crate) struct U64GroupedBitMapMut<'a> {
+    data: &'a mut [u8],
+}
+
+impl<'a> U64GroupedBitMapMut<'a> {
+    pub(crate) fn new(data: &'a mut [u8]) -> Self {
+        assert_eq!(data.len() % 8, 0);
+        Self { data }
+    }
+
+    pub(crate) fn len(&self) -> usize {
+        self.data.len() * 8
+    }
+
+    // Returns true iff the bit's group is all set
+    pub(crate) fn set(&mut self, bit: usize) -> bool {
+        let (index, bit_index) = self.data_index_of(bit);
+        let mut group = u64::from_be_bytes(self.data[index..(index + 8)].try_into().unwrap());
+        group |= Self::select_mask(bit_index);
+        self.data[index..(index + 8)].copy_from_slice(&group.to_be_bytes());
+
+        group == u64::MAX
+    }
+
+    pub(crate) fn get(&mut self, bit: usize) -> bool {
+        let (index, bit_index) = self.data_index_of(bit);
+        let group = u64::from_be_bytes(self.data[index..(index + 8)].try_into().unwrap());
+        group & Self::select_mask(bit_index) != 0
+    }
+
+    pub(crate) fn clear(&mut self, bit: usize) {
+        let (index, bit_index) = self.data_index_of(bit);
+        let mut group = u64::from_be_bytes(self.data[index..(index + 8)].try_into().unwrap());
+        group &= !Self::select_mask(bit_index);
+        self.data[index..(index + 8)].copy_from_slice(&group.to_be_bytes());
+    }
+
+    pub(crate) fn first_unset(&self, start_bit: usize, end_bit: usize) -> Option<usize> {
+        assert_eq!(start_bit % 64, 0);
+        assert_eq!(end_bit, start_bit + 64);
+
+        let (index, _) = self.data_index_of(start_bit);
+        let group = u64::from_be_bytes(self.data[index..(index + 8)].try_into().unwrap());
+        match group.trailing_ones() {
+            64 => None,
+            x => Some(start_bit + x as usize),
+        }
+    }
+
+    fn data_index_of(&self, bit: usize) -> (usize, usize) {
+        ((bit / 64) as usize * size_of::<u64>(), (bit % 64) as usize)
+    }
+
+    fn select_mask(bit: usize) -> u64 {
+        1u64 << (bit as u64)
+    }
+}
diff --git a/src/tree_store/page_store/mod.rs b/src/tree_store/page_store/mod.rs
index 94ef769..6b3dc87 100644
--- a/src/tree_store/page_store/mod.rs
+++ b/src/tree_store/page_store/mod.rs
@@ -1,8 +1,10 @@
+mod buddy_allocator;
+mod grouped_bitmap;
 mod mmap;
 mod page_allocator;
 mod page_manager;
 mod utils;
 
-pub(crate) use page_manager::{expand_db_size, get_db_size, PageNumber};
+pub(crate) use page_manager::{get_db_size, PageNumber};
 
 pub(in crate::tree_store) use page_manager::{Page, PageImpl, PageMut, TransactionalMemory};
diff --git a/src/tree_store/page_store/page_allocator.rs b/src/tree_store/page_store/page_allocator.rs
index 014218a..349ea26 100644
--- a/src/tree_store/page_store/page_allocator.rs
+++ b/src/tree_store/page_store/page_allocator.rs
@@ -1,72 +1,10 @@
+use crate::tree_store::page_store::grouped_bitmap::{U64GroupedBitMap, U64GroupedBitMapMut};
 use crate::Error;
 use crate::Result;
-use std::convert::TryInto;
 use std::mem::size_of;
 
-struct U64GroupedBitMap<'a> {
-    data: &'a [u8],
-}
-
-impl<'a> U64GroupedBitMap<'a> {
-    fn count_unset(&self) -> usize {
-        self.data.iter().map(|x| x.count_zeros() as usize).sum()
-    }
-}
-
-struct U64GroupedBitMapMut<'a> {
-    data: &'a mut [u8],
-}
-
-impl<'a> U64GroupedBitMapMut<'a> {
-    fn data_index_of(&self, bit: usize) -> (usize, usize) {
-        ((bit / 64) as usize * size_of::<u64>(), (bit % 64) as usize)
-    }
-
-    fn select_mask(bit: usize) -> u64 {
-        1u64 << (bit as u64)
-    }
-
-    fn len(&self) -> usize {
-        self.data.len() * 8
-    }
-
-    // Returns true iff the bit's group is all set
-    fn set(&mut self, bit: usize) -> bool {
-        let (index, bit_index) = self.data_index_of(bit);
-        let mut group = u64::from_be_bytes(self.data[index..(index + 8)].try_into().unwrap());
-        group |= Self::select_mask(bit_index);
-        self.data[index..(index + 8)].copy_from_slice(&group.to_be_bytes());
-
-        group == u64::MAX
-    }
-
-    fn get(&mut self, bit: usize) -> bool {
-        let (index, bit_index) = self.data_index_of(bit);
-        let group = u64::from_be_bytes(self.data[index..(index + 8)].try_into().unwrap());
-        group & Self::select_mask(bit_index) != 0
-    }
-
-    fn clear(&mut self, bit: usize) {
-        let (index, bit_index) = self.data_index_of(bit);
-        let mut group = u64::from_be_bytes(self.data[index..(index + 8)].try_into().unwrap());
-        group &= !Self::select_mask(bit_index);
-        self.data[index..(index + 8)].copy_from_slice(&group.to_be_bytes());
-    }
-
-    fn first_unset(&self, start_bit: usize, end_bit: usize) -> Option<usize> {
-        assert_eq!(start_bit % 64, 0);
-        assert_eq!(end_bit, start_bit + 64);
-
-        let (index, _) = self.data_index_of(start_bit);
-        let group = u64::from_be_bytes(self.data[index..(index + 8)].try_into().unwrap());
-        match group.trailing_ones() {
-            64 => None,
-            x => Some(start_bit + x as usize),
-        }
-    }
-}
-
-struct PageAllocator {
+#[derive(Clone)]
+pub(crate) struct PageAllocator {
     num_pages: usize,
     tree_level_offsets: Vec<(usize, usize)>,
 }
@@ -81,7 +19,7 @@ struct PageAllocator {
 // subtree layer: 2-64 u64s
 // ...consecutive layers. Except for the last level, all sub-trees of the root must be complete
 impl PageAllocator {
-    fn new(num_pages: usize) -> Self {
+    pub(crate) fn new(num_pages: usize) -> Self {
         let mut tree_level_offsets = vec![];
 
         let mut offset = 0;
@@ -119,7 +57,7 @@ impl PageAllocator {
         }
     }
 
-    fn init_new(data: &mut [u8], num_pages: usize) -> Self {
+    pub(crate) fn init_new(data: &mut [u8], num_pages: usize) -> Self {
         assert!(data.len() >= Self::required_space(num_pages));
         // Zero the memory, so that all pages are free
         for value in data.iter_mut() {
@@ -156,7 +94,7 @@ impl PageAllocator {
     }
 
     /// Returns the number of bytes required for the data argument of new()
-    fn required_space(num_pages: usize) -> usize {
+    pub(crate) fn required_space(num_pages: usize) -> usize {
         if Self::required_tree_height(num_pages) == 1 {
             assert!(num_pages <= 64);
             // Space for num_pages header, and root
@@ -202,22 +140,18 @@ impl PageAllocator {
         height
     }
 
-    fn count_free_pages(&self, data: &[u8]) -> usize {
+    pub(crate) fn count_free_pages(&self, data: &[u8]) -> usize {
         self.get_level(data, self.get_height() - 1).count_unset()
     }
 
     fn get_level<'a>(&self, data: &'a [u8], i: usize) -> U64GroupedBitMap<'a> {
         let (start, end) = self.tree_level_offsets[i];
-        U64GroupedBitMap {
-            data: &data[start..end],
-        }
+        U64GroupedBitMap::new(&data[start..end])
     }
 
     fn get_level_mut<'a>(&self, data: &'a mut [u8], i: usize) -> U64GroupedBitMapMut<'a> {
         let (start, end) = self.tree_level_offsets[i];
-        U64GroupedBitMapMut {
-            data: &mut data[start..end],
-        }
+        U64GroupedBitMapMut::new(&mut data[start..end])
     }
 
     fn get_num_pages(&self) -> u64 {
@@ -253,13 +187,13 @@ impl PageAllocator {
         }
     }
 
-    fn is_allocated(&self, data: &mut [u8], page_number: u64) -> bool {
+    pub(crate) fn is_allocated(&self, data: &mut [u8], page_number: u64) -> bool {
         self.get_level_mut(data, self.get_height() - 1)
             .get(page_number as usize)
     }
 
     /// data must have been initialized by Self::init_new()
-    fn alloc(&self, data: &mut [u8]) -> Result<u64> {
+    pub(crate) fn alloc(&self, data: &mut [u8]) -> Result<u64> {
         if let Some(mut entry) = self.get_level_mut(data, 0).first_unset(0, 64) {
             let mut height = 0;
 
@@ -281,7 +215,7 @@ impl PageAllocator {
     }
 
     /// data must have been initialized by Self::init_new()
-    fn record_alloc(&self, data: &mut [u8], page_number: u64) {
+    pub(crate) fn record_alloc(&self, data: &mut [u8], page_number: u64) {
         assert!(page_number < self.get_num_pages());
         let full = self
             .get_level_mut(data, self.get_height() - 1)
@@ -290,7 +224,7 @@ impl PageAllocator {
     }
 
     /// data must have been initialized by Self::init_new()
-    fn free(&self, data: &mut [u8], page_number: u64) {
+    pub(crate) fn free(&self, data: &mut [u8], page_number: u64) {
         assert!(page_number < self.get_num_pages());
         self.get_level_mut(data, self.get_height() - 1)
             .clear(page_number as usize);
@@ -298,189 +232,9 @@ impl PageAllocator {
     }
 }
 
-pub(crate) struct BuddyAllocator {
-    orders: Vec<PageAllocator>,
-}
-
-// Handles allocation of dynamically sized pages, supports pages of up to page_size * 2^max_order bytes
-//
-// Pages are marked free at only a single order, and it must always be the largest order
-//
-// Data structure format:
-// max_order: big endian u64
-// order_offsets: array of (u64, u64), with offset & length for PageAllocator structure for the given order
-// ... PageAllocator structures
-impl BuddyAllocator {
-    pub(crate) fn new(mut num_pages: usize, max_order: usize) -> Self {
-        let mut orders = vec![];
-        for _ in 0..=max_order {
-            orders.push(PageAllocator::new(num_pages));
-            num_pages = Self::next_higher_order(num_pages as u64) as usize;
-        }
-
-        Self { orders }
-    }
-
-    pub(crate) fn init_new(data: &mut [u8], mut num_pages: usize, max_order: usize) -> Self {
-        assert!(data.len() >= Self::required_space(num_pages, max_order));
-        data[..size_of::<u64>()].copy_from_slice(&(max_order as u64).to_be_bytes());
-
-        let mut metadata_offset = size_of::<u64>();
-        let mut data_offset = size_of::<u64>() + 2 * (max_order + 1) * size_of::<u64>();
-
-        let mut orders = vec![];
-        for order in 0..=max_order {
-            let required = PageAllocator::required_space(num_pages);
-            data[metadata_offset..metadata_offset + size_of::<u64>()]
-                .copy_from_slice(&(data_offset as u64).to_be_bytes());
-            data[metadata_offset + size_of::<u64>()..metadata_offset + 2 * size_of::<u64>()]
-                .copy_from_slice(&(required as u64).to_be_bytes());
-            orders.push(PageAllocator::init_new(
-                Self::get_order_bytes_mut(data, order),
-                num_pages,
-            ));
-            num_pages = Self::next_higher_order(num_pages as u64) as usize;
-            metadata_offset += 2 * size_of::<u64>();
-            data_offset += required;
-        }
-
-        // Mark all the lower pages which exist in upper orders
-        for (order, allocator) in orders.iter().enumerate() {
-            if let Some(next_allocator) = orders.get(order + 1) {
-                let next_bytes = Self::get_order_bytes_mut(data, order + 1);
-                let next_pages = next_allocator.count_free_pages(next_bytes) as u64;
-                let bytes = Self::get_order_bytes_mut(data, order);
-                for i in 0..(2 * next_pages) {
-                    allocator.record_alloc(bytes, i);
-                }
-            }
-        }
-
-        Self { orders }
-    }
-
-    /// Returns the number of bytes required for the data argument of new()
-    pub(crate) fn required_space(mut num_pages: usize, max_order: usize) -> usize {
-        let mut required = size_of::<u64>() + 2 * (max_order + 1) * size_of::<u64>();
-        for _ in 0..=max_order {
-            required += PageAllocator::required_space(num_pages);
-            num_pages = Self::next_higher_order(num_pages as u64) as usize;
-        }
-
-        required
-    }
-
-    pub(crate) fn count_free_pages(&self, data: &[u8]) -> usize {
-        let mut pages = 0;
-        for (order, allocator) in self.orders.iter().enumerate() {
-            pages += allocator.count_free_pages(Self::get_order_bytes(data, order))
-                * 2usize.pow(order as u32);
-        }
-
-        pages
-    }
-
-    fn get_order_offset_and_length(data: &[u8], order: usize) -> (usize, usize) {
-        let max_order = u64::from_be_bytes(data[..size_of::<u64>()].try_into().unwrap()) as usize;
-        assert!(order <= max_order);
-        let base = size_of::<u64>() + order * 2 * size_of::<u64>();
-        let offset =
-            u64::from_be_bytes(data[base..base + size_of::<u64>()].try_into().unwrap()) as usize;
-        let length = u64::from_be_bytes(
-            data[base + size_of::<u64>()..base + 2 * size_of::<u64>()]
-                .try_into()
-                .unwrap(),
-        ) as usize;
-
-        (offset, length)
-    }
-
-    fn get_order_bytes(data: &[u8], order: usize) -> &[u8] {
-        let (offset, length) = Self::get_order_offset_and_length(data, order);
-        &data[offset..(offset + length)]
-    }
-
-    fn get_order_bytes_mut(data: &mut [u8], order: usize) -> &mut [u8] {
-        let (offset, length) = Self::get_order_offset_and_length(data, order);
-        &mut data[offset..(offset + length)]
-    }
-
-    fn next_higher_order(page_number: u64) -> u64 {
-        page_number / 2
-    }
-
-    fn buddy_page(page_number: u64) -> u64 {
-        page_number ^ 1
-    }
-
-    /// data must have been initialized by Self::init_new()
-    pub(crate) fn alloc(&self, data: &mut [u8], order: usize) -> Result<u64> {
-        if order >= self.orders.len() {
-            return Err(Error::OutOfSpace);
-        }
-        match self.orders[order].alloc(Self::get_order_bytes_mut(data, order)) {
-            Ok(x) => Ok(x),
-            Err(e) => {
-                match e {
-                    Error::OutOfSpace => {
-                        // Try to allocate a higher order page and split it
-                        let upper_page = self.alloc(data, order + 1)?;
-                        let (free1, free2) = (upper_page * 2, upper_page * 2 + 1);
-                        debug_assert!(self.orders[order]
-                            .is_allocated(Self::get_order_bytes_mut(data, order), free1));
-                        debug_assert!(self.orders[order]
-                            .is_allocated(Self::get_order_bytes_mut(data, order), free2));
-                        self.orders[order].free(Self::get_order_bytes_mut(data, order), free2);
-
-                        Ok(free1)
-                    }
-                    other => Err(other),
-                }
-            }
-        }
-    }
-
-    /// data must have been initialized by Self::init_new(), and page_number must be free
-    pub(crate) fn record_alloc(&self, data: &mut [u8], page_number: u64, order: usize) {
-        assert!(order < self.orders.len());
-        if self.orders[order].is_allocated(Self::get_order_bytes_mut(data, order), page_number) {
-            // Need to split parent page
-            let upper_page = Self::next_higher_order(page_number);
-            self.record_alloc(data, upper_page, order + 1);
-
-            let (free1, free2) = (upper_page * 2, upper_page * 2 + 1);
-            debug_assert!(free1 == page_number || free2 == page_number);
-            if free1 == page_number {
-                self.orders[order].free(Self::get_order_bytes_mut(data, order), free2);
-            } else {
-                self.orders[order].free(Self::get_order_bytes_mut(data, order), free1);
-            }
-        } else {
-            self.orders[order].record_alloc(Self::get_order_bytes_mut(data, order), page_number);
-        }
-    }
-
-    /// data must have been initialized by Self::init_new()
-    pub(crate) fn free(&self, data: &mut [u8], page_number: u64, order: usize) {
-        if order == self.orders.len() - 1 {
-            self.orders[order].free(Self::get_order_bytes_mut(data, order), page_number);
-            return;
-        }
-
-        let buddy = Self::buddy_page(page_number);
-        if self.orders[order].is_allocated(Self::get_order_bytes_mut(data, order), buddy) {
-            self.orders[order].free(Self::get_order_bytes_mut(data, order), page_number);
-        } else {
-            // Merge into higher order page
-            self.orders[order].record_alloc(Self::get_order_bytes_mut(data, order), buddy);
-            self.free(data, Self::next_higher_order(page_number), order + 1);
-        }
-    }
-}
-
 #[cfg(test)]
 mod test {
-    use crate::tree_store::page_store::page_allocator::{BuddyAllocator, PageAllocator};
+    use crate::tree_store::page_store::page_allocator::PageAllocator;
     use crate::Error;
     use rand::prelude::IteratorRandom;
     use rand::rngs::StdRng;
@@ -502,79 +256,6 @@ mod test {
         ));
     }
 
-    #[test]
-    fn record_alloc_buddy() {
-        let num_pages = 256;
-        let max_order = 7;
-        let mut data = vec![0; BuddyAllocator::required_space(num_pages, max_order)];
-        let allocator = BuddyAllocator::init_new(&mut data, num_pages, max_order);
-        assert_eq!(allocator.count_free_pages(&data), num_pages);
-
-        for page in 0..num_pages {
-            allocator.record_alloc(&mut data, page as u64, 0);
-        }
-        assert_eq!(allocator.count_free_pages(&data), 0);
-
-        assert!(matches!(
-            allocator.alloc(&mut data, 0).unwrap_err(),
-            Error::OutOfSpace
-        ));
-
-        for page in 0..num_pages {
-            allocator.free(&mut data, page as u64, 0);
-        }
-        assert_eq!(allocator.count_free_pages(&data), num_pages);
-    }
-
-    #[test]
-    fn buddy_merge() {
-        let num_pages = 256;
-        let max_order = 7;
-        let mut data = vec![0; BuddyAllocator::required_space(num_pages, max_order)];
-        let allocator = BuddyAllocator::init_new(&mut data, num_pages, max_order);
-        assert_eq!(allocator.count_free_pages(&data), num_pages);
-
-        for _ in 0..num_pages {
-            allocator.alloc(&mut data, 0).unwrap();
-        }
-        for page in 0..num_pages {
-            allocator.free(&mut data, page as u64, 0);
-        }
-        assert_eq!(allocator.count_free_pages(&data), num_pages);
-
-        // Test that everything got merged back together, so that we fill order 7 allocations
-        for _ in 0..(num_pages / 2usize.pow(7)) {
-            allocator.alloc(&mut data, 7).unwrap();
-        }
-    }
-
-    #[test]
-    fn alloc_large() {
-        let num_pages = 256;
-        let max_order = 7;
-        let mut data = vec![0; BuddyAllocator::required_space(num_pages, max_order)];
-        let allocator = BuddyAllocator::init_new(&mut data, num_pages, max_order);
-        assert_eq!(allocator.count_free_pages(&data), num_pages);
-
-        let mut allocated = vec![];
-        for order in 0..=max_order {
-            allocated.push((allocator.alloc(&mut data, order).unwrap(), order));
-        }
-        assert_eq!(allocator.count_free_pages(&data), 1);
-
-        for order in 1..=max_order {
-            assert!(matches!(
-                allocator.alloc(&mut data, order).unwrap_err(),
-                Error::OutOfSpace
-            ));
-        }
-
-        for (page, order) in allocated {
-            allocator.free(&mut data, page, order);
-        }
-        assert_eq!(allocator.count_free_pages(&data), num_pages);
-    }
-
     #[test]
     fn record_alloc() {
         let mut data = vec![0; PageAllocator::required_space(2)];
diff --git a/src/tree_store/page_store/page_manager.rs b/src/tree_store/page_store/page_manager.rs
index ccd3f8c..de9126c 100644
--- a/src/tree_store/page_store/page_manager.rs
+++ b/src/tree_store/page_store/page_manager.rs
@@ -1,5 +1,5 @@
+use crate::tree_store::page_store::buddy_allocator::BuddyAllocator;
 use crate::tree_store::page_store::mmap::Mmap;
-use crate::tree_store::page_store::page_allocator::BuddyAllocator;
 use crate::tree_store::page_store::utils::get_page_size;
 use crate::Error;
 use crate::Result;
@@ -7,9 +7,9 @@ use std::cmp::min;
 use std::collections::HashSet;
 use std::convert::TryInto;
 use std::fmt::{Debug, Formatter};
-use std::fs::{File, OpenOptions};
+use std::fs::File;
 use std::io;
-use std::io::{Read, Seek, SeekFrom, Write};
+use std::io::{Read, Seek, SeekFrom};
 use std::mem::size_of;
 use std::ops::Range;
 use std::path::Path;
@@ -102,79 +102,6 @@ pub(crate) fn get_db_size(path: impl AsRef<Path>) -> Result<usize, io::Error> {
     Ok(u64::from_be_bytes(db_size) as usize)
 }
 
-pub(crate) fn expand_db_size(path: impl AsRef<Path>, new_size: usize) -> Result {
-    let old_size = get_db_size(path.as_ref())?;
-
-    let mut file = OpenOptions::new().read(true).write(true).open(path)?;
-    file.seek(SeekFrom::Start(PAGE_SIZE_OFFSET as u64))?;
-    let mut buffer = [0; 1];
-    file.read_exact(&mut buffer)?;
-
-    let page_size = 1usize << buffer[0];
-    let max_order = TransactionalMemory::calculate_usable_order(old_size, page_size as usize);
-    let old_usable_pages =
-        TransactionalMemory::calculate_usable_pages(old_size, page_size as usize, max_order);
-    let max_order = TransactionalMemory::calculate_usable_order(new_size, page_size as usize);
-    let usable_pages =
-        TransactionalMemory::calculate_usable_pages(new_size, page_size as usize, max_order);
-
-    let allocator_state_size = BuddyAllocator::required_space(usable_pages, max_order);
-    assert!(usable_pages >= old_usable_pages);
-    assert!(usable_pages * page_size + allocator_state_size * 2 <= new_size);
-
-    // Write the WAL
-    file.seek(SeekFrom::Start(UPGRADE_LOG_OFFSET as u64))?;
-    file.write_all(&(old_size as u64).to_be_bytes())?;
-    file.seek(SeekFrom::Start(UPGRADE_LOG_LEN_OFFSET as u64))?;
-    file.write_all(&(size_of::<u64>() as u64).to_be_bytes())?;
-    file.sync_all()?;
-
-    // Dirty the allocator state, so that it will be rebuilt
-    file.seek(SeekFrom::Start(GOD_BYTE_OFFSET as u64))?;
-    let mut buffer = [0u8; 1];
-    file.read_exact(&mut buffer)?;
-    let in_progress_god_byte =
-        buffer[0] | ALLOCATOR_STATE_0_DIRTY | ALLOCATOR_STATE_1_DIRTY | UPGRADE_IN_PROGRESS;
-    let final_god_byte = buffer[0] | ALLOCATOR_STATE_0_DIRTY | ALLOCATOR_STATE_1_DIRTY;
-    file.seek(SeekFrom::Start(GOD_BYTE_OFFSET as u64))?;
-    file.write_all(&[in_progress_god_byte])?;
-    file.sync_all()?;
-
-    file.set_len(new_size as u64)?;
-    file.sync_all()?;
-
-    // Write the new allocator state pointers
-    let start = new_size - 2 * allocator_state_size;
-    file.seek(SeekFrom::Start(
-        (TRANSACTION_0_OFFSET + ALLOCATOR_STATE_PTR_OFFSET) as u64,
-    ))?;
-    file.write_all(&(start as u64).to_be_bytes())?;
-    file.seek(SeekFrom::Start(
-        (TRANSACTION_0_OFFSET + ALLOCATOR_STATE_LEN_OFFSET) as u64,
-    ))?;
-    file.write_all(&(allocator_state_size as u64).to_be_bytes())?;
-    let start = new_size - allocator_state_size;
-    file.seek(SeekFrom::Start(
-        (TRANSACTION_1_OFFSET + ALLOCATOR_STATE_PTR_OFFSET) as u64,
-    ))?;
-    file.write_all(&(start as u64).to_be_bytes())?;
-    file.seek(SeekFrom::Start(
-        (TRANSACTION_1_OFFSET + ALLOCATOR_STATE_LEN_OFFSET) as u64,
-    ))?;
-    file.write_all(&(allocator_state_size as u64).to_be_bytes())?;
-
-    file.sync_all()?;
-    file.seek(SeekFrom::Start(DB_SIZE_OFFSET as u64))?;
-    file.write_all(&(new_size as u64).to_be_bytes())?;
-    file.sync_all()?;
-
-    file.seek(SeekFrom::Start(GOD_BYTE_OFFSET as u64))?;
-    file.write_all(&[final_god_byte])?;
-    file.sync_all()?;
-
-    Ok(())
-}
-
 // Marker struct for the mutex guarding the meta page
 struct MetapageGuard;
 


Test patch:
diff --git a/tests/integration_tests.rs b/tests/integration_tests.rs
index b351b2e..2753cd7 100644
--- a/tests/integration_tests.rs
+++ b/tests/integration_tests.rs
@@ -141,133 +141,6 @@ fn change_db_size() {
     assert!(matches!(db.err().unwrap(), Error::DbSizeMismatch { .. }));
 }
 
-#[test]
-fn resize_db() {
-    let tmpfile: NamedTempFile = NamedTempFile::new().unwrap();
-
-    let definition: TableDefinition<u128, u128> = TableDefinition::new("x");
-    let db_size = 64 * 1024;
-    let db = unsafe {
-        DatabaseBuilder::new()
-            .set_page_size(4096)
-            .create(tmpfile.path(), db_size)
-            .unwrap()
-    };
-    let mut i = 0u128;
-    loop {
-        let txn = db.begin_write().unwrap();
-        let mut table = txn.open_table(definition).unwrap();
-        // Fill the database
-        match table.insert(&i, &i) {
-            Ok(_) => {}
-            Err(err) => match err {
-                Error::OutOfSpace => {
-                    txn.abort().unwrap();
-                    break;
-                }
-                _ => unreachable!(),
-            },
-        }
-        match txn.commit() {
-            Ok(_) => {}
-            Err(err) => match err {
-                Error::OutOfSpace => break,
-                _ => unreachable!(),
-            },
-        };
-        i += 1;
-    }
-
-    let txn = db.begin_write().unwrap();
-    let mut table = txn.open_table(definition).unwrap();
-    let mut found = false;
-    let mut j = i;
-    for _ in 0..999 {
-        if matches!(table.insert(&j, &j), Err(Error::OutOfSpace)) {
-            found = true;
-            break;
-        }
-        j += 1;
-    }
-    assert!(found);
-    txn.abort().unwrap();
-    drop(db);
-
-    unsafe {
-        Database::resize(tmpfile.path(), db_size * 2).unwrap();
-    }
-
-    let db = unsafe { Database::open(tmpfile.path()).unwrap() };
-    let txn = db.begin_write().unwrap();
-    let mut table = txn.open_table(definition).unwrap();
-    for k in i..(j + 2) {
-        table.insert(&k, &k).unwrap();
-    }
-    txn.commit().unwrap();
-}
-
-// Test for bug in resize where a double free could occur if there were pending pages to free
-// in the internal "freed" table
-#[test]
-fn regression4() {
-    let tmpfile: NamedTempFile = NamedTempFile::new().unwrap();
-
-    let db_size = 16 * 1024 * 1024;
-    let db = unsafe { Database::create(tmpfile.path(), db_size).unwrap() };
-    let mut i = 0u64;
-    loop {
-        let mut txn = db.begin_write().unwrap();
-        txn.set_durability(Durability::None);
-        let mut table = txn.open_table(U64_TABLE).unwrap();
-        // Fill the database
-        match table.insert(&i, &i) {
-            Ok(_) => {}
-            Err(err) => match err {
-                Error::OutOfSpace => {
-                    txn.abort().unwrap();
-                    break;
-                }
-                _ => unreachable!(),
-            },
-        }
-        match txn.commit() {
-            Ok(_) => {}
-            Err(err) => match err {
-                Error::OutOfSpace => break,
-                _ => unreachable!(),
-            },
-        };
-        i += 1;
-    }
-
-    let txn = db.begin_write().unwrap();
-    let mut table = txn.open_table(U64_TABLE).unwrap();
-    let mut found = false;
-    let mut j = i;
-    for _ in 0..999 {
-        if matches!(table.insert(&j, &j), Err(Error::OutOfSpace)) {
-            found = true;
-            break;
-        }
-        j += 1;
-    }
-    assert!(found);
-    txn.abort().unwrap();
-    drop(db);
-
-    unsafe {
-        Database::resize(tmpfile.path(), db_size * 2).unwrap();
-    }
-
-    let db = unsafe { Database::open(tmpfile.path()).unwrap() };
-    let txn = db.begin_write().unwrap();
-    let mut table = txn.open_table(U64_TABLE).unwrap();
-    for k in i..(j + 2) {
-        table.insert(&k, &k).unwrap();
-    }
-    txn.commit().unwrap();
-}
-
 #[test]
 fn free() {
     let tmpfile: NamedTempFile = NamedTempFile::new().unwrap();