From 3291ea405b60695a25703e713c7fc47dda602e8d Mon Sep 17 00:00:00 2001 From: tcmal Date: Sat, 17 Jun 2023 14:21:15 +0000 Subject: avoid deadlocks by no longer returning read guard --- incria/Cargo.lock | 65 ++++++++++++++++++++++++++++++++++++++++++++++ incria/Cargo.toml | 3 ++- incria/benches/pascal.rs | 2 +- incria/src/lazy_mapping.rs | 47 +++++++++++++++++++++------------ incria/src/thunk.rs | 4 +++ 5 files changed, 103 insertions(+), 18 deletions(-) diff --git a/incria/Cargo.lock b/incria/Cargo.lock index 315a8a8..9a19675 100644 --- a/incria/Cargo.lock +++ b/incria/Cargo.lock @@ -2,6 +2,12 @@ # It is not intended for manual editing. version = 3 +[[package]] +name = "allocator-api2" +version = "0.2.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "56fc6cf8dc8c4158eed8649f9b8b0ea1518eb62b544fe9490d66fa0b349eafe9" + [[package]] name = "anes" version = "0.1.6" @@ -31,6 +37,16 @@ version = "1.3.2" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" +[[package]] +name = "blink-alloc" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eedafeef9c2d56b08e6d14b0f9b22e371261a38c81cbfc69a4014b0f2d1094a7" +dependencies = [ + "allocator-api2", + "parking_lot", +] + [[package]] name = "bumpalo" version = "3.13.0" @@ -279,6 +295,7 @@ dependencies = [ name = "incria" version = "0.1.0" dependencies = [ + "blink-alloc", "criterion", "tokio", ] @@ -329,6 +346,16 @@ version = "0.2.144" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "2b00cc1c228a6782d0f076e7b232802e0c5689d41bb5df366f2a6b6621cfdfe1" +[[package]] +name = "lock_api" +version = "0.4.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c1cc9717a20b1bb222f333e6a92fd32f7d8a18ddc5a3191a11af45dcbf4dcd16" +dependencies = [ + "autocfg", + "scopeguard", +] + [[package]] name = "log" version = "0.4.18" @@ -381,6 +408,29 @@ version = "6.5.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "ceedf44fb00f2d1984b0bc98102627ce622e083e49a5bacdb3e514fa4238e267" +[[package]] +name = "parking_lot" +version = "0.12.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3742b2c103b9f06bc9fff0a37ff4912935851bee6d36f3c02bcc755bcfec228f" +dependencies = [ + "lock_api", + "parking_lot_core", +] + +[[package]] +name = "parking_lot_core" +version = "0.9.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "93f00c865fe7cabf650081affecd3871070f26767e7b2070a3ffae14c654b447" +dependencies = [ + "cfg-if", + "libc", + "redox_syscall", + "smallvec", + "windows-targets", +] + [[package]] name = "pin-project-lite" version = "0.2.9" @@ -461,6 +511,15 @@ dependencies = [ "num_cpus", ] +[[package]] +name = "redox_syscall" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "567664f262709473930a4bf9e51bf2ebf3348f2e748ccc50dea20646858f8f29" +dependencies = [ + "bitflags", +] + [[package]] name = "regex" version = "1.8.3" @@ -528,6 +587,12 @@ dependencies = [ "serde", ] +[[package]] +name = "smallvec" +version = "1.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a507befe795404456341dfab10cef66ead4c041f62b8b11bbb92bffe5d0953e0" + [[package]] name = "syn" version = "2.0.16" diff --git a/incria/Cargo.toml b/incria/Cargo.toml index 2dbe28a..55e6cdf 100644 --- a/incria/Cargo.toml +++ b/incria/Cargo.toml @@ -4,6 +4,7 @@ version = "0.1.0" edition = "2021" [dependencies] +blink-alloc = { version = "0.3.0", features = ["sync"] } tokio = { version = "1.28.1", features = ["sync", "rt"] } [dev-dependencies] @@ -16,4 +17,4 @@ path = "benches/pascal.rs" [[bench]] name = "pascal" -harness = false \ No newline at end of file +harness = false diff --git a/incria/benches/pascal.rs b/incria/benches/pascal.rs index 3c06de1..01befe5 100644 --- a/incria/benches/pascal.rs +++ b/incria/benches/pascal.rs @@ -85,7 +85,7 @@ fn benchmarks_with_n(c: &mut Criterion, n: isize) { #[inline(always)] async fn do_calc(key: &Key) { - drop(deps::with_node_id(deps::next_node_id(), pascal_mapping().get(key)).await); + deps::with_node_id(deps::next_node_id(), pascal_mapping().get(key)).await; } #[inline(always)] diff --git a/incria/src/lazy_mapping.rs b/incria/src/lazy_mapping.rs index bef3a3d..27bd76e 100644 --- a/incria/src/lazy_mapping.rs +++ b/incria/src/lazy_mapping.rs @@ -1,5 +1,8 @@ -use std::{collections::HashMap, future::Future, hash::Hash, sync::Arc}; +use std::{ + collections::HashMap, fmt::Debug, future::Future, hash::Hash, mem::transmute, sync::Arc, +}; +use blink_alloc::{Blink, SyncBlinkAlloc}; use tokio::sync::{Mutex, Notify, RwLock, RwLockReadGuard}; use crate::{ @@ -12,13 +15,15 @@ pub trait LazyMappingBackend { fn compute(&self, key: K) -> impl Future + Send + '_; } -#[derive(Debug, Default)] -pub struct LazyMapper { +#[derive(Default)] +pub struct LazyMapper { /// The backend we use to compute values and check dirtiness backend: B, + values: SyncBlinkAlloc, + /// Map of all values we've calculated already - calculated: RwLock>, + calculated: RwLock>, /// Values we're currently calculating /// The Notify will be triggered when computation is done. @@ -34,6 +39,7 @@ impl Mapper for LazyMapper where - K: Clone + Eq + Hash + Send + Sync, - V: Send + Sync, + K: Clone + Eq + Hash + Send + Sync + Debug, + V: Send + Sync + 'static, B: LazyMappingBackend, { type Key = K; type Value = V; - type Wrapper<'a> = RwLockReadGuard<'a, V> where V: 'a; + type Wrapper<'a> = &'a V where V: 'a; async fn get<'a>(&'a self, key: &Self::Key) -> Self::Wrapper<'a> { // Attempt to reuse or evict the existing value let mut reuse_dep_id = None; { let finished = self.calculated.read().await; - if let Some((_, node)) = finished.get(key) { + if let Some((val, node)) = finished.get(key) { let dirty = deps::is_dirty(*node) || self.backend.is_dirty(key).await; if !dirty { deps::add_dep(*node); - return RwLockReadGuard::map(finished, |hm| &hm.get(key).unwrap().0); + return val; } else { reuse_dep_id = Some(*node); drop(finished); @@ -85,10 +91,12 @@ where // Waiting for completion barrier.notified().await; - let val = RwLockReadGuard::map(self.calculated.read().await, |hm| hm.get(key).unwrap()); - deps::add_dep(val.1); + let (value, node_id) = + *RwLockReadGuard::map(self.calculated.read().await, |hm| hm.get(key).unwrap()); + + deps::add_dep(node_id); - return RwLockReadGuard::map(val, |inf| &inf.0); + value } else { // Needs calculated let notify = Arc::new(Notify::new()); @@ -105,19 +113,26 @@ where }; let val = deps::with_node_id(dep, self.backend.compute(key.clone())).await; + let val_ref: &'static V = unsafe { transmute(Blink::new_in(&self.values).put(val)) }; deps::add_dep(dep); self.calculated .write() .await - .insert(key.clone(), (val, dep)); + .insert(key.clone(), (val_ref, dep)); self.waiting.lock().await.remove(key); notify.notify_waiters(); - return RwLockReadGuard::map(self.calculated.read().await, |hm| { - &hm.get(key).unwrap().0 - }); + val_ref } } } + +impl Debug for LazyMapper { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.debug_struct("LazyMapper") + .field("backend", &self.backend) + .finish_non_exhaustive() + } +} diff --git a/incria/src/thunk.rs b/incria/src/thunk.rs index 937f109..2fe7873 100644 --- a/incria/src/thunk.rs +++ b/incria/src/thunk.rs @@ -19,6 +19,10 @@ impl ThunkBackend { pub fn new(thunk: T) -> Self { Self { thunk } } + + pub fn thunk(&self) -> &T { + &self.thunk + } } impl LazyMappingBackend for ThunkBackend -- cgit v1.2.3