Repository: cberner/redb
Pull request #153 (2022-02-04 06:35:25)

Fix regression
Deleting a key from the last leaf of an internal node could cause the
other entries to be dropped, if the leaf became partial and needed to be
merged, due to a bug in the child repair code


Patch:
diff --git a/src/tree_store/btree_utils.rs b/src/tree_store/btree_utils.rs
index 7d75e28..c93a4c2 100644
--- a/src/tree_store/btree_utils.rs
+++ b/src/tree_store/btree_utils.rs
@@ -378,30 +378,35 @@ fn repair_children<K: RedbKey + ?Sized>(
             })
             .collect();
         Ok(page_numbers)
-    } else if children.iter().any(|x| matches!(x, PartialLeaf(_))) {
+    } else if let Some(position) = children.iter().position(|x| matches!(x, PartialLeaf(_))) {
+        let merge_with = if position == 0 { 1 } else { position - 1 };
         let mut result = vec![];
-        let mut repaired = false;
-        // For each whole subtree, try to merge it with a partial left to repair it, if one is neighboring
         for i in 0..children.len() {
-            if let Subtree(handle) = &children[i] {
-                if repaired {
-                    result.push(*handle);
-                    continue;
-                }
-                let offset = if i > 0 { i - 1 } else { i + 1 };
-                if let Some(PartialLeaf(partials)) = children.get(offset) {
-                    if let Some(new_page) = merge_leaf::<K>(*handle, partials, freed, manager)? {
-                        result.push(new_page);
+            match &children[i] {
+                Subtree(handle) => {
+                    if i == merge_with {
+                        if let PartialLeaf(partials) = children.get(position).unwrap() {
+                            if let Some(new_page) =
+                                merge_leaf::<K>(*handle, partials, freed, manager)?
+                            {
+                                result.push(new_page);
+                            } else {
+                                let (page1, page2) =
+                                    split_leaf::<K>(*handle, partials, manager, freed)?;
+                                result.push(page1);
+                                result.push(page2);
+                            }
+                        } else {
+                            unreachable!()
+                        };
                     } else {
-                        let (page1, page2) = split_leaf::<K>(*handle, partials, manager, freed)?;
-                        result.push(page1);
-                        result.push(page2);
+                        result.push(*handle);
                     }
-                    repaired = true;
-                } else {
-                    // No adjacent partial
-                    result.push(*handle);
                 }
+                PartialLeaf(_) => {
+                    // continue
+                }
+                PartialInternal(_) => unreachable!(),
             }
         }
         Ok(result)


Test patch:
diff --git a/tests/integration_tests.rs b/tests/integration_tests.rs
index 6783130..b25f4d8 100644
--- a/tests/integration_tests.rs
+++ b/tests/integration_tests.rs
@@ -369,6 +369,29 @@ fn regression2() {
     assert!(b.get(b"hi").unwrap().is_none());
 }
 
+#[test]
+// Test for a bug in deletion code, where deletions could delete neighboring keys in a leaf,
+// due to the partial leaf entries being dropped
+fn regression3() {
+    let tmpfile: NamedTempFile = NamedTempFile::new().unwrap();
+
+    let db_size = 1024 * 1024;
+    let db = unsafe { Database::open(tmpfile.path(), db_size).unwrap() };
+    let tx = db.begin_write().unwrap();
+    let mut t: Table<[u8], [u8]> = tx.open_table("x").unwrap();
+    let big_value = vec![0u8; 1000];
+    for i in 0..20 {
+        t.insert(&[i], &big_value).unwrap();
+    }
+    for i in (10..20).rev() {
+        t.remove(&[i]).unwrap();
+        for j in 0..i {
+            assert!(t.get(&[j]).unwrap().is_some());
+        }
+    }
+    tx.commit().unwrap();
+}
+
 #[test]
 fn non_durable_read_isolation() {
     let tmpfile: NamedTempFile = NamedTempFile::new().unwrap();