From 01af6c09a786ec2d6475531a7dac873eeffa3a3e Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Mon, 2 Nov 2020 15:07:50 +0100 Subject: Fix simulation reaching different states when started from different snaphots. --- src/data/hashmap.rs | 137 ++++++++++++++++++++++++++++++++++++ src/data/maybe_serializable_data.rs | 14 ++++ src/data/mod.rs | 4 ++ 3 files changed, 155 insertions(+) create mode 100644 src/data/hashmap.rs create mode 100644 src/data/maybe_serializable_data.rs (limited to 'src/data') diff --git a/src/data/hashmap.rs b/src/data/hashmap.rs new file mode 100644 index 0000000..78f9797 --- /dev/null +++ b/src/data/hashmap.rs @@ -0,0 +1,137 @@ +//! A hash-map that behaves deterministically when the +//! `enhanced-determinism` feature is enabled. + +#[cfg(all(feature = "enhanced-determinism", feature = "serde-serialize"))] +use indexmap::IndexMap as StdHashMap; +#[cfg(all(not(feature = "enhanced-determinism"), feature = "serde-serialize"))] +use std::collections::HashMap as StdHashMap; + +/// Serializes only the capacity of a hash-map instead of its actual content. +#[cfg(feature = "serde-serialize")] +pub fn serialize_hashmap_capacity( + map: &StdHashMap, + s: S, +) -> Result { + s.serialize_u64(map.capacity() as u64) +} + +/// Creates a new hash-map with its capacity deserialized from `d`. +#[cfg(feature = "serde-serialize")] +pub fn deserialize_hashmap_capacity< + 'de, + D: serde::Deserializer<'de>, + K, + V, + H: std::hash::BuildHasher + Default, +>( + d: D, +) -> Result, D::Error> { + struct CapacityVisitor; + impl<'de> serde::de::Visitor<'de> for CapacityVisitor { + type Value = u64; + + fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result { + write!(formatter, "an integer between 0 and 2^64") + } + + fn visit_u64(self, val: u64) -> Result { + Ok(val) + } + } + + let capacity = d.deserialize_u64(CapacityVisitor)? as usize; + Ok(StdHashMap::with_capacity_and_hasher( + capacity, + Default::default(), + )) +} + +/* + * FxHasher taken from rustc_hash, except that it does not depend on the pointer size. + */ +#[cfg(feature = "enhanced-determinism")] +pub type FxHashMap32 = indexmap::IndexMap>; +#[cfg(not(feature = "enhanced-determinism"))] +pub use rustc_hash::{Entry, FxHashMap as HashMap}; +#[cfg(feature = "enhanced-determinism")] +pub use {self::FxHashMap32 as HashMap, indexmap::map::Entry}; + +const K: u32 = 0x9e3779b9; + +// Same as FxHasher, but with the guarantee that the internal hash is +// an u32 instead of something that depends on the platform. +pub struct FxHasher32 { + hash: u32, +} + +impl Default for FxHasher32 { + #[inline] + fn default() -> FxHasher32 { + FxHasher32 { hash: 0 } + } +} + +impl FxHasher32 { + #[inline] + fn add_to_hash(&mut self, i: u32) { + use std::ops::BitXor; + self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K); + } +} + +impl std::hash::Hasher for FxHasher32 { + #[inline] + fn write(&mut self, mut bytes: &[u8]) { + use std::convert::TryInto; + let read_u32 = |bytes: &[u8]| u32::from_ne_bytes(bytes[..4].try_into().unwrap()); + let mut hash = FxHasher32 { hash: self.hash }; + assert!(std::mem::size_of::() <= 8); + while bytes.len() >= std::mem::size_of::() { + hash.add_to_hash(read_u32(bytes) as u32); + bytes = &bytes[std::mem::size_of::()..]; + } + if (std::mem::size_of::() > 4) && (bytes.len() >= 4) { + hash.add_to_hash(u32::from_ne_bytes(bytes[..4].try_into().unwrap()) as u32); + bytes = &bytes[4..]; + } + if (std::mem::size_of::() > 2) && bytes.len() >= 2 { + hash.add_to_hash(u16::from_ne_bytes(bytes[..2].try_into().unwrap()) as u32); + bytes = &bytes[2..]; + } + if (std::mem::size_of::() > 1) && bytes.len() >= 1 { + hash.add_to_hash(bytes[0] as u32); + } + self.hash = hash.hash; + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.add_to_hash(i as u32); + } + + #[inline] + fn write_u16(&mut self, i: u16) { + self.add_to_hash(i as u32); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.add_to_hash(i as u32); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.add_to_hash(i as u32); + self.add_to_hash((i >> 32) as u32); + } + + #[inline] + fn write_usize(&mut self, i: usize) { + self.add_to_hash(i as u32); + } + + #[inline] + fn finish(&self) -> u64 { + self.hash as u64 + } +} diff --git a/src/data/maybe_serializable_data.rs b/src/data/maybe_serializable_data.rs new file mode 100644 index 0000000..db38963 --- /dev/null +++ b/src/data/maybe_serializable_data.rs @@ -0,0 +1,14 @@ +use downcast_rs::{impl_downcast, DowncastSync}; +#[cfg(feature = "serde-serialize")] +use erased_serde::Serialize; + +/// Piece of data that may be serializable. +pub trait MaybeSerializableData: DowncastSync { + /// Convert this shape as a serializable entity. + #[cfg(feature = "serde-serialize")] + fn as_serialize(&self) -> Option<(u32, &dyn Serialize)> { + None + } +} + +impl_downcast!(sync MaybeSerializableData); diff --git a/src/data/mod.rs b/src/data/mod.rs index 5d3efa6..0e0459e 100644 --- a/src/data/mod.rs +++ b/src/data/mod.rs @@ -1,5 +1,9 @@ //! Data structures modified with guaranteed deterministic behavior after deserialization. +pub use self::maybe_serializable_data::MaybeSerializableData; + pub mod arena; pub(crate) mod graph; +pub(crate) mod hashmap; +mod maybe_serializable_data; pub mod pubsub; -- cgit From 83482602717d1a9aebb181fb82456a292801cbdc Mon Sep 17 00:00:00 2001 From: Crozet Sébastien Date: Mon, 2 Nov 2020 17:57:48 +0100 Subject: Fix 2D compilation. --- src/data/hashmap.rs | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/data') diff --git a/src/data/hashmap.rs b/src/data/hashmap.rs index 78f9797..d2ea980 100644 --- a/src/data/hashmap.rs +++ b/src/data/hashmap.rs @@ -51,10 +51,10 @@ pub fn deserialize_hashmap_capacity< */ #[cfg(feature = "enhanced-determinism")] pub type FxHashMap32 = indexmap::IndexMap>; -#[cfg(not(feature = "enhanced-determinism"))] -pub use rustc_hash::{Entry, FxHashMap as HashMap}; #[cfg(feature = "enhanced-determinism")] pub use {self::FxHashMap32 as HashMap, indexmap::map::Entry}; +#[cfg(not(feature = "enhanced-determinism"))] +pub use {rustc_hash::FxHashMap as HashMap, std::collections::hash_map::Entry}; const K: u32 = 0x9e3779b9; -- cgit