kanidm / concread

Concurrently Readable Data Structures for Rust
Mozilla Public License 2.0
339 stars 15 forks source link

fix BptreeMap doube free on remove #121

Closed Erigara closed 2 months ago

Erigara commented 2 months ago

I've got double free on attempt to remove element from BptreeMap.

Here example i was able to find:

#[test]
fn bptree_remove_1() {
    let values = [
        4u8, 9, 12, 27, 34, 40, 59, 81, 89, 100, 142, 183, 189, 196, 218, 241,
    ];

    let to_remove = [9u8, 27, 40, 4].map(|v| v.to_string());

    let bptree_map = BptreeMap::from_iter(
        values
            .iter()
            .cloned()
            .map(|v| (v.to_string(), v.to_string())),
    );
    let mut bptree_map_write_tx = bptree_map.write();

    for key in to_remove {
        assert!(bptree_map_write_tx.remove(&key).is_some());
    }
}

I've manged to debug that start_idx inside take_from_l_to_r was not correct when removing keys. Though there is might be other corner cases not yet found.

Also i've added proptests to check consistency of BptreeMap with BTreeMap from std.