chashmap: deadlock
Created by: m4b
Please excuse me if there's an obvious error, but the following code seems to deadlock, but I was somewhat surprised at this. (do cargo new --bin deadlock
and add chashmap
and rayon
as deps):
extern crate chashmap;
extern crate rayon;
use chashmap::CHashMap;
use rayon::prelude::*;
#[derive(Debug)]
struct BackingData<'a> {
name: &'a str,
references: Vec<&'a str>
}
#[derive(Debug, Ord, PartialOrd, Eq, PartialEq)]
struct Data {
pub val: usize
}
#[derive(Debug)]
struct Records<'a> {
records: Vec<BackingData<'a>>
}
impl<'a> Records<'a> {
pub fn new(count: usize, lifetimedata: &[&'a str]) -> Self {
let mut records = Vec::with_capacity(count);
for i in 0..count {
let name = lifetimedata[i];
let mut references = Vec::with_capacity(i+1);
// fill up some test data
for j in 0..i {
// we will never have our own key in our references
if j != i {
references.push(lifetimedata[j]);
}
}
records.push(BackingData {
name,
references,
});
}
Records {
records
}
}
// this can leave out stuff but who cares
pub fn shard(&self, count: usize) -> Vec<&[BackingData<'a>]> {
let mut shards = Vec::with_capacity(count);
let size = self.records.len() / count;
for i in 0..count {
let offset = i * size;
let records = &self.records[offset..offset+size];
shards.push(records);
}
shards
}
}
// try: `for i in {0..100}; do cargo run; done`
// should see a deadlock after a few iterations according to instructions in comments
fn main() {
let lifetime_data = vec!["hello", "world", "foo", "bar", "baz", "borp", "bilz", "zilp", "zoom", "zam", "abra", "cadabra", "soon", "more", "dog", "food", "is", "good", "lol", "hi", "hiya"];
let records = Records::new(16, lifetime_data.as_slice());
println!("records: {}", records.records.len());
let map = CHashMap::new();
records.records.par_iter().enumerate().for_each(|(val, record)| {
map.insert(record.name, Data { val });
});
println!("map: {:#?}", map);
let shards = records.shard(4);
println!("shards: {:#?}", shards);
for shard in shards {
shard.par_iter().enumerate().for_each(|(i, data)| {
println!("({}) -> {:?}", i, data);
let item = map.get_mut(&data.name).unwrap();
let val = item.val * (i + 1);
// if we move this get_mut into a block, no locking
// let val = {
// let item = map.get_mut(&data.name).unwrap();
// item.val * (val + 1)
// };
for reference in &data.references {
print!("({}) ref {} ", i, reference);
// remember, we never have a reference to ourself in references, only other backingdata have a reference to us
let mut data = map.get_mut(&reference).unwrap();
data.val = data.val.saturating_mul(val);
// can't print until my patch goes in ;)
//println!("data: {:?}", data);
}
});
}
println!("map final: {:#?}", map);
let mut res = map.into_iter().collect::<Vec<(&str, Data)>>();
res.sort();
for (name, data) in res {
println!("{}: {:#?}", name, data.val);
}
}
So basically the above code deadlocks when the write lock is obtained for name
and held while it gets the locks for it's references (which never includes itself), and updates them.
If the lock is dropped earlier via a block as the above comment suggests, it does not ever seem to deadlock.
This was surprising to me, primarily because I don't see much of a difference, except for performance (although admittedly I haven't analyzed the the possible interleavings of both versions too much).
I guess this could be a stupid question, and perhaps I've been lulled into a false sense of safety in multi-threaded situations, but as I understand it: does this mean one still has to be very careful not to deadlock when using chashmap?
Thanks and I really appreciate the work that's gone into this crate, it's really totally awesome :)