Repository navigation
skiplist: dropping a map leaks removed nodes linked only above level 0 #1343
Description
Replacing keys and then iterating can leave a value unfreed after the map is dropped. The example below reproduces this in a single thread, with or without calling clear().
Tested on Debian 13, Linux x86_64, Rust 1.99.0, at Crossbeam commit 099d0469efcfacb32527bd9451a4fb62586ae537.
Reproduction
Cargo.toml:
[package]
name = "skipmap-drop-leak-repro"
version = "0.0.0"
edition = "2021"
publish = false
[dependencies]
crossbeam-skiplist = { git = "https://github.com/crossbeam-rs/crossbeam", rev = "099d0469efcfacb32527bd9451a4fb62586ae537" }
crossbeam-epoch = { git = "https://github.com/crossbeam-rs/crossbeam", rev = "099d0469efcfacb32527bd9451a4fb62586ae537" }
[workspace]src/main.rs:
use std::sync::{
atomic::{AtomicUsize, Ordering},
Arc,
};
struct Value {
id: usize,
drops: Arc<Vec<AtomicUsize>>,
}
impl Drop for Value {
fn drop(&mut self) {
assert_eq!(self.drops[self.id].fetch_add(1, Ordering::Relaxed), 0);
}
}
fn main() {
let clear = std::env::args().any(|arg| arg == "--clear");
let cleanup = std::env::args().any(|arg| arg == "--cleanup");
let keys = [0_u64, 0, 0, 0, 0, 0, 1, 0, 1];
let drops = Arc::new(
(0..keys.len())
.map(|_| AtomicUsize::new(0))
.collect::<Vec<_>>(),
);
let map = crossbeam_skiplist::SkipMap::new();
for (id, key) in keys.into_iter().enumerate() {
drop(map.insert(
key,
Value {
id,
drops: drops.clone(),
},
));
}
let _: Vec<_> = map.iter().map(|entry| *entry.key()).collect();
if clear {
map.clear();
}
if cleanup {
drop(map.lower_bound(std::ops::Bound::<&u64>::Unbounded));
}
drop(map);
for _ in 0..65_536 {
let guard = crossbeam_epoch::pin();
guard.flush();
}
let missing: Vec<_> = drops
.iter()
.enumerate()
.filter_map(|(id, count)| (count.load(Ordering::Relaxed) == 0).then_some(id))
.collect();
println!("clear={clear} cleanup={cleanup} missing={missing:?}");
assert!(missing.is_empty());
}Run each command in a separate process:
cargo run --release --
cargo run --release -- --clear
cargo run --release -- --clear --cleanupObserved output:
clear=false cleanup=false missing=[6] # assertion fails
clear=true cleanup=false missing=[6] # assertion fails
clear=true cleanup=true missing=[] # succeeds
Expected: all nine values are eventually dropped. The example reports insertion 6 as missing after dropping the map and repeatedly pinning/flushing. Calling clear() followed by an additional search before dropping the map makes the example pass.
Cause
Iteration unlinks the replaced node at level 0, but the node remains linked at level 1 with a reference count of 1. SkipList::drop() only walks level 0, so it misses the node. The remaining reference also prevents the node from being deferred to the epoch collector.
Regression
With Rust 1.77.2, the same nine-insertion sequence passes on 2128578c992a2415d34b1845494d74e0e40e8722 and fails on its immediate successor, e7b5922ec9da940d2630099c5d6b4877d2463de4 (#1101). This holds both with and without clear(). That commit changes the replacement insertion order; it does not change Drop or clear().
Related reports: #540 and #1178. The revision tested here already includes the range-iteration fix in #1217.
Activity