BptreeMap can drop invalid objects if clone panics

[ammaraskar]

Hi there, we (Rust group @sslab-gatech) are scanning crates on crates.io for potential soundness bugs. We noticed a panic safety issue in the BptreeMapWriteTxn::insert function.

If a key being inserted panics during its clone then it can leave the BptreeMap in an inconsistent state and cause invalid objects to be dropped.

See this example:

#![forbid(unsafe_code)]

use concread::bptree::BptreeMap;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct DropDetector(u32);

impl Clone for DropDetector {
    fn clone(&self) -> Self {
        panic!("Panic on clone!");
    }
}

impl Drop for DropDetector {
    fn drop(&mut self) {
        println!("Dropping {}", self.0);
    }
}

fn main() {
    let tree : BptreeMap<DropDetector, i32> = BptreeMap::new();
    let mut writer = tree.write();

    writer.insert(DropDetector(1), 1);
    writer.commit();

    let mut writer = tree.write();
    writer.insert(DropDetector(0), 0);
}

which outputs:

thread 'main' panicked at 'Panic on clone!', src/main.rs:25:9
stack backtrace:
   0: std::panicking::begin_panic
             at /home/ammar/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:505
   1: <rudra_poc_0156::DropDetector as core::clone::Clone>::clone
             at ./src/main.rs:25
   2: concread::bptree::node::Leaf<K,V>::req_clone
             at /home/ammar/.cargo/registry/src/github.com-1ecc6299db9ec823/concread-0.2.8/src/bptree/node.rs:589
   3: concread::bptree::cursor::clone_and_insert
             at /home/ammar/.cargo/registry/src/github.com-1ecc6299db9ec823/concread-0.2.8/src/bptree/cursor.rs:630
   4: concread::bptree::cursor::CursorWrite<K,V>::insert
             at /home/ammar/.cargo/registry/src/github.com-1ecc6299db9ec823/concread-0.2.8/src/bptree/cursor.rs:250
   5: concread::bptree::BptreeMapWriteTxn<K,V>::insert
             at /home/ammar/.cargo/registry/src/github.com-1ecc6299db9ec823/concread-0.2.8/src/bptree/mod.rs:301
   6: rudra_poc_0156::main
             at ./src/main.rs:43
   7: core::ops::function::FnOnce::call_once
             at /home/ammar/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
Dropping 32659
Dropping 0
Dropping 1

Notice the weird Dropping 32659 indicating some uninitialized or re-used memory is being dropped.

[Firstyear]

I think the fix here won't be "too bad". In theory we could also panic on keys too not just the values.

https://github.com/kanidm/concread/blob/master/src/bptree/node.rs#L578

We present the metadata count as we clone, but similar to the link, we could mask this out in the copy, and then update the count after.

This probably also affects branches.