Repository: cberner/redb
Pull request #227 (2022-03-19 17:55:59)

Fix OutOfSpace error when storing values > ~1MB


Patch:
diff --git a/src/tree_store/page_store/buddy_allocator.rs b/src/tree_store/page_store/buddy_allocator.rs
index 88d68d5..bec8ee0 100644
--- a/src/tree_store/page_store/buddy_allocator.rs
+++ b/src/tree_store/page_store/buddy_allocator.rs
@@ -92,7 +92,7 @@ impl BuddyAllocator {
             let order_size = 2usize.pow(order as u32);
             let page = processed_pages / order_size;
             debug_assert_eq!(processed_pages % order_size, 0);
-            if order >= self.orders.len() {
+            if order >= self.orders.len() || processed_pages + order_size > new_size {
                 break;
             }
             let order_data = Self::get_order_bytes_mut(data, order);
diff --git a/src/tree_store/page_store/page_manager.rs b/src/tree_store/page_store/page_manager.rs
index 6cc8abc..28dcdcb 100644
--- a/src/tree_store/page_store/page_manager.rs
+++ b/src/tree_store/page_store/page_manager.rs
@@ -4,7 +4,7 @@ use crate::tree_store::page_store::mmap::Mmap;
 use crate::tree_store::page_store::utils::get_page_size;
 use crate::Error;
 use crate::Result;
-use std::cmp::min;
+use std::cmp::{max, min};
 use std::collections::HashSet;
 use std::convert::TryInto;
 use std::fmt::{Debug, Formatter};
@@ -528,7 +528,7 @@ impl RegionLayout {
 
     fn max_order(&self) -> usize {
         Self::calculate_usable_order(
-            self.allocator_state.start,
+            MAX_USABLE_REGION_SPACE,
             self.allocator_state.start / self.num_pages,
         )
         .unwrap()
@@ -1239,13 +1239,23 @@ impl TransactionalMemory {
         ))
     }
 
-    fn grow(&self, metadata: &mut MetadataAccessor, layout: &mut DatabaseLayout) -> Result<()> {
+    fn grow(
+        &self,
+        metadata: &mut MetadataAccessor,
+        layout: &mut DatabaseLayout,
+        required_order_allocation: usize,
+    ) -> Result<()> {
         let next_desired_size = if layout.num_full_regions > 0 {
             // Grow by 1 region
             // TODO: prune the trailing partial region, if it exists
             layout.usable_bytes() + MAX_USABLE_REGION_SPACE
         } else {
-            layout.usable_bytes() * 2
+            let required_growth =
+                2usize.pow(required_order_allocation as u32) * metadata.get_page_size();
+            max(
+                layout.usable_bytes() * 2,
+                layout.usable_bytes() + required_growth * 2,
+            )
         };
         let new_layout = DatabaseLayout::calculate(
             metadata.get_max_capacity(),
@@ -1329,7 +1339,7 @@ impl TransactionalMemory {
             Ok(page_number) => page_number,
             Err(err) => {
                 if matches!(err, Error::OutOfSpace) && layout.len() < max_capacity {
-                    self.grow(&mut metadata, &mut layout)?;
+                    self.grow(&mut metadata, &mut layout, required_order)?;
                     self.allocate_helper(&mut metadata, &layout, required_order)?
                 } else {
                     return Err(err);


Test patch:
diff --git a/tests/integration_tests.rs b/tests/integration_tests.rs
index 6dc8010..4848b83 100644
--- a/tests/integration_tests.rs
+++ b/tests/integration_tests.rs
@@ -197,6 +197,36 @@ fn free() {
     assert_eq!(free_pages, db.stats().unwrap().free_pages());
 }
 
+#[test]
+fn large_values() {
+    let tmpfile: NamedTempFile = NamedTempFile::new().unwrap();
+
+    let db_size = 50 * 1024 * 1024;
+    let db = unsafe { Database::create(tmpfile.path(), db_size).unwrap() };
+    let txn = db.begin_write().unwrap();
+
+    let mut key = vec![0; 1024];
+    let value = vec![0; 2_000_000];
+    {
+        let mut table = txn.open_table(SLICE_TABLE).unwrap();
+        for i in 0..5 {
+            key[0] = i;
+            table.insert(&key, &value).unwrap();
+        }
+    }
+    txn.commit().unwrap();
+
+    let txn = db.begin_write().unwrap();
+    {
+        let mut table = txn.open_table(SLICE_TABLE).unwrap();
+        for i in 0..5 {
+            key[0] = i;
+            table.remove(&key).unwrap();
+        }
+    }
+    txn.commit().unwrap();
+}
+
 #[test]
 fn large_keys() {
     let tmpfile: NamedTempFile = NamedTempFile::new().unwrap();