src/vector_clock.rs

   1 use rustc_index::vec::Idx;
   2 use smallvec::SmallVec;
   3 use std::{
   4     cmp::Ordering,
   5     convert::TryFrom,
   6     fmt::Debug,
   7     ops::Index,
   8 };
   9
  10 /// A vector clock index, this is associated with a thread id
  11 /// but in some cases one vector index may be shared with
  12 /// multiple thread ids if it safe to do so.
  13 #[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
  14 pub struct VectorIdx(u32);
  15
  16 impl VectorIdx {
  17     #[inline(always)]
  18     pub fn to_u32(self) -> u32 {
  19         self.0
  20     }
  21
  22     pub const MAX_INDEX: VectorIdx = VectorIdx(u32::MAX);
  23 }
  24
  25 impl Idx for VectorIdx {
  26     #[inline]
  27     fn new(idx: usize) -> Self {
  28         VectorIdx(u32::try_from(idx).unwrap())
  29     }
  30
  31     #[inline]
  32     fn index(self) -> usize {
  33         usize::try_from(self.0).unwrap()
  34     }
  35 }
  36
  37 impl From<u32> for VectorIdx {
  38     #[inline]
  39     fn from(id: u32) -> Self {
  40         Self(id)
  41     }
  42 }
  43
  44 /// The size of the vector-clock to store inline
  45 /// clock vectors larger than this will be stored on the heap
  46 const SMALL_VECTOR: usize = 4;
  47
  48 /// The type of the time-stamps recorded in the data-race detector
  49 /// set to a type of unsigned integer
  50 pub type VTimestamp = u32;
  51
  52 /// A vector clock for detecting data-races, this is conceptually
  53 /// a map from a vector index (and thus a thread id) to a timestamp.
  54 /// The compare operations require that the invariant that the last
  55 /// element in the internal timestamp slice must not be a 0, hence
  56 /// all zero vector clocks are always represented by the empty slice;
  57 /// and allows for the implementation of compare operations to short
  58 /// circuit the calculation and return the correct result faster,
  59 /// also this means that there is only one unique valid length
  60 /// for each set of vector clock values and hence the PartialEq
  61 //  and Eq derivations are correct.
  62 #[derive(PartialEq, Eq, Default, Debug)]
  63 pub struct VClock(SmallVec<[VTimestamp; SMALL_VECTOR]>);
  64
  65 impl VClock {
  66     /// Create a new vector-clock containing all zeros except
  67     /// for a value at the given index
  68     pub fn new_with_index(index: VectorIdx, timestamp: VTimestamp) -> VClock {
  69         let len = index.index() + 1;
  70         let mut vec = smallvec::smallvec![0; len];
  71         vec[index.index()] = timestamp;
  72         VClock(vec)
  73     }
  74
  75     /// Load the internal timestamp slice in the vector clock
  76     #[inline]
  77     pub fn as_slice(&self) -> &[VTimestamp] {
  78         self.0.as_slice()
  79     }
  80
  81     /// Get a mutable slice to the internal vector with minimum `min_len`
  82     /// elements, to preserve invariants this vector must modify
  83     /// the `min_len`-1 nth element to a non-zero value
  84     #[inline]
  85     fn get_mut_with_min_len(&mut self, min_len: usize) -> &mut [VTimestamp] {
  86         if self.0.len() < min_len {
  87             self.0.resize(min_len, 0);
  88         }
  89         assert!(self.0.len() >= min_len);
  90         self.0.as_mut_slice()
  91     }
  92
  93     /// Increment the vector clock at a known index
  94     /// this will panic if the vector index overflows
  95     #[inline]
  96     pub fn increment_index(&mut self, idx: VectorIdx) {
  97         let idx = idx.index();
  98         let mut_slice = self.get_mut_with_min_len(idx + 1);
  99         let idx_ref = &mut mut_slice[idx];
 100         *idx_ref = idx_ref.checked_add(1).expect("Vector clock overflow")
 101     }
 102
 103     // Join the two vector-clocks together, this
 104     // sets each vector-element to the maximum value
 105     // of that element in either of the two source elements.
 106     pub fn join(&mut self, other: &Self) {
 107         let rhs_slice = other.as_slice();
 108         let lhs_slice = self.get_mut_with_min_len(rhs_slice.len());
 109         for (l, &r) in lhs_slice.iter_mut().zip(rhs_slice.iter()) {
 110             *l = r.max(*l);
 111         }
 112     }
 113
 114     /// Set the element at the current index of the vector
 115     pub fn set_at_index(&mut self, other: &Self, idx: VectorIdx) {
 116         let idx = idx.index();
 117         let mut_slice = self.get_mut_with_min_len(idx + 1);
 118         let slice = other.as_slice();
 119         mut_slice[idx] = slice[idx];
 120     }
 121
 122     /// Set the vector to the all-zero vector
 123     #[inline]
 124     pub fn set_zero_vector(&mut self) {
 125         self.0.clear();
 126     }
 127
 128     /// Return if this vector is the all-zero vector
 129     pub fn is_zero_vector(&self) -> bool {
 130         self.0.is_empty()
 131     }
 132 }
 133
 134 impl Clone for VClock {
 135     fn clone(&self) -> Self {
 136         VClock(self.0.clone())
 137     }
 138
 139     // Optimized clone-from, can be removed
 140     // and replaced with a derive once a similar
 141     // optimization is inserted into SmallVec's
 142     // clone implementation.
 143     fn clone_from(&mut self, source: &Self) {
 144         let source_slice = source.as_slice();
 145         self.0.clear();
 146         self.0.extend_from_slice(source_slice);
 147     }
 148 }
 149
 150 impl PartialOrd for VClock {
 151     fn partial_cmp(&self, other: &VClock) -> Option<Ordering> {
 152         // Load the values as slices
 153         let lhs_slice = self.as_slice();
 154         let rhs_slice = other.as_slice();
 155
 156         // Iterate through the combined vector slice continuously updating
 157         // the value of `order` to the current comparison of the vector from
 158         // index 0 to the currently checked index.
 159         // An Equal ordering can be converted into Less or Greater ordering
 160         // on finding an element that is less than or greater than the other
 161         // but if one Greater and one Less element-wise comparison is found
 162         // then no ordering is possible and so directly return an ordering
 163         // of None.
 164         let mut iter = lhs_slice.iter().zip(rhs_slice.iter());
 165         let mut order = match iter.next() {
 166             Some((lhs, rhs)) => lhs.cmp(rhs),
 167             None => Ordering::Equal,
 168         };
 169         for (l, r) in iter {
 170             match order {
 171                 Ordering::Equal => order = l.cmp(r),
 172                 Ordering::Less =>
 173                     if l > r {
 174                         return None;
 175                     },
 176                 Ordering::Greater =>
 177                     if l < r {
 178                         return None;
 179                     },
 180             }
 181         }
 182
 183         // Now test if either left or right have trailing elements,
 184         // by the invariant the trailing elements have at least 1
 185         // non zero value, so no additional calculation is required
 186         // to determine the result of the PartialOrder.
 187         let l_len = lhs_slice.len();
 188         let r_len = rhs_slice.len();
 189         match l_len.cmp(&r_len) {
 190             // Equal means no additional elements: return current order
 191             Ordering::Equal => Some(order),
 192             // Right has at least 1 element > than the implicit 0,
 193             // so the only valid values are Ordering::Less or None.
 194             Ordering::Less => match order {
 195                 Ordering::Less | Ordering::Equal => Some(Ordering::Less),
 196                 Ordering::Greater => None,
 197             },
 198             // Left has at least 1 element > than the implicit 0,
 199             // so the only valid values are Ordering::Greater or None.
 200             Ordering::Greater => match order {
 201                 Ordering::Greater | Ordering::Equal => Some(Ordering::Greater),
 202                 Ordering::Less => None,
 203             },
 204         }
 205     }
 206
 207     fn lt(&self, other: &VClock) -> bool {
 208         // Load the values as slices
 209         let lhs_slice = self.as_slice();
 210         let rhs_slice = other.as_slice();
 211
 212         // If l_len > r_len then at least one element
 213         // in l_len is > than r_len, therefore the result
 214         // is either Some(Greater) or None, so return false
 215         // early.
 216         let l_len = lhs_slice.len();
 217         let r_len = rhs_slice.len();
 218         if l_len <= r_len {
 219             // If any elements on the left are greater than the right
 220             // then the result is None or Some(Greater), both of which
 221             // return false, the earlier test asserts that no elements in the
 222             // extended tail violate this assumption. Otherwise l <= r, finally
 223             // the case where the values are potentially equal needs to be considered
 224             // and false returned as well
 225             let mut equal = l_len == r_len;
 226             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 227                 if l > r {
 228                     return false;
 229                 } else if l < r {
 230                     equal = false;
 231                 }
 232             }
 233             !equal
 234         } else {
 235             false
 236         }
 237     }
 238
 239     fn le(&self, other: &VClock) -> bool {
 240         // Load the values as slices
 241         let lhs_slice = self.as_slice();
 242         let rhs_slice = other.as_slice();
 243
 244         // If l_len > r_len then at least one element
 245         // in l_len is > than r_len, therefore the result
 246         // is either Some(Greater) or None, so return false
 247         // early.
 248         let l_len = lhs_slice.len();
 249         let r_len = rhs_slice.len();
 250         if l_len <= r_len {
 251             // If any elements on the left are greater than the right
 252             // then the result is None or Some(Greater), both of which
 253             // return false, the earlier test asserts that no elements in the
 254             // extended tail violate this assumption. Otherwise l <= r
 255             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l > r)
 256         } else {
 257             false
 258         }
 259     }
 260
 261     fn gt(&self, other: &VClock) -> bool {
 262         // Load the values as slices
 263         let lhs_slice = self.as_slice();
 264         let rhs_slice = other.as_slice();
 265
 266         // If r_len > l_len then at least one element
 267         // in r_len is > than l_len, therefore the result
 268         // is either Some(Less) or None, so return false
 269         // early.
 270         let l_len = lhs_slice.len();
 271         let r_len = rhs_slice.len();
 272         if l_len >= r_len {
 273             // If any elements on the left are less than the right
 274             // then the result is None or Some(Less), both of which
 275             // return false, the earlier test asserts that no elements in the
 276             // extended tail violate this assumption. Otherwise l >=, finally
 277             // the case where the values are potentially equal needs to be considered
 278             // and false returned as well
 279             let mut equal = l_len == r_len;
 280             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 281                 if l < r {
 282                     return false;
 283                 } else if l > r {
 284                     equal = false;
 285                 }
 286             }
 287             !equal
 288         } else {
 289             false
 290         }
 291     }
 292
 293     fn ge(&self, other: &VClock) -> bool {
 294         // Load the values as slices
 295         let lhs_slice = self.as_slice();
 296         let rhs_slice = other.as_slice();
 297
 298         // If r_len > l_len then at least one element
 299         // in r_len is > than l_len, therefore the result
 300         // is either Some(Less) or None, so return false
 301         // early.
 302         let l_len = lhs_slice.len();
 303         let r_len = rhs_slice.len();
 304         if l_len >= r_len {
 305             // If any elements on the left are less than the right
 306             // then the result is None or Some(Less), both of which
 307             // return false, the earlier test asserts that no elements in the
 308             // extended tail violate this assumption. Otherwise l >= r
 309             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l < r)
 310         } else {
 311             false
 312         }
 313     }
 314 }
 315
 316 impl Index<VectorIdx> for VClock {
 317     type Output = VTimestamp;
 318
 319     #[inline]
 320     fn index(&self, index: VectorIdx) -> &VTimestamp {
 321         self.as_slice().get(index.to_u32() as usize).unwrap_or(&0)
 322     }
 323 }
 324
 325 /// Test vector clock ordering operations
 326 ///  data-race detection is tested in the external
 327 ///  test suite
 328 #[cfg(test)]
 329 mod tests {
 330
 331     use super::{VClock, VTimestamp, VectorIdx};
 332     use std::cmp::Ordering;
 333
 334     #[test]
 335     fn test_equal() {
 336         let mut c1 = VClock::default();
 337         let mut c2 = VClock::default();
 338         assert_eq!(c1, c2);
 339         c1.increment_index(VectorIdx(5));
 340         assert_ne!(c1, c2);
 341         c2.increment_index(VectorIdx(53));
 342         assert_ne!(c1, c2);
 343         c1.increment_index(VectorIdx(53));
 344         assert_ne!(c1, c2);
 345         c2.increment_index(VectorIdx(5));
 346         assert_eq!(c1, c2);
 347     }
 348
 349     #[test]
 350     fn test_partial_order() {
 351         // Small test
 352         assert_order(&[1], &[1], Some(Ordering::Equal));
 353         assert_order(&[1], &[2], Some(Ordering::Less));
 354         assert_order(&[2], &[1], Some(Ordering::Greater));
 355         assert_order(&[1], &[1, 2], Some(Ordering::Less));
 356         assert_order(&[2], &[1, 2], None);
 357
 358         // Misc tests
 359         assert_order(&[400], &[0, 1], None);
 360
 361         // Large test
 362         assert_order(
 363             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 364             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 365             Some(Ordering::Equal),
 366         );
 367         assert_order(
 368             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 369             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 370             Some(Ordering::Less),
 371         );
 372         assert_order(
 373             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
 374             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 375             Some(Ordering::Greater),
 376         );
 377         assert_order(
 378             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
 379             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 380             None,
 381         );
 382         assert_order(
 383             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9],
 384             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 385             Some(Ordering::Less),
 386         );
 387         assert_order(
 388             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9],
 389             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 390             Some(Ordering::Less),
 391         );
 392     }
 393
 394     fn from_slice(mut slice: &[VTimestamp]) -> VClock {
 395         while let Some(0) = slice.last() {
 396             slice = &slice[..slice.len() - 1]
 397         }
 398         VClock(smallvec::SmallVec::from_slice(slice))
 399     }
 400
 401     fn assert_order(l: &[VTimestamp], r: &[VTimestamp], o: Option<Ordering>) {
 402         let l = from_slice(l);
 403         let r = from_slice(r);
 404
 405         //Test partial_cmp
 406         let compare = l.partial_cmp(&r);
 407         assert_eq!(compare, o, "Invalid comparison\n l: {:?}\n r: {:?}", l, r);
 408         let alt_compare = r.partial_cmp(&l);
 409         assert_eq!(
 410             alt_compare,
 411             o.map(Ordering::reverse),
 412             "Invalid alt comparison\n l: {:?}\n r: {:?}",
 413             l,
 414             r
 415         );
 416
 417         //Test operators with faster implementations
 418         assert_eq!(
 419             matches!(compare, Some(Ordering::Less)),
 420             l < r,
 421             "Invalid (<):\n l: {:?}\n r: {:?}",
 422             l,
 423             r
 424         );
 425         assert_eq!(
 426             matches!(compare, Some(Ordering::Less) | Some(Ordering::Equal)),
 427             l <= r,
 428             "Invalid (<=):\n l: {:?}\n r: {:?}",
 429             l,
 430             r
 431         );
 432         assert_eq!(
 433             matches!(compare, Some(Ordering::Greater)),
 434             l > r,
 435             "Invalid (>):\n l: {:?}\n r: {:?}",
 436             l,
 437             r
 438         );
 439         assert_eq!(
 440             matches!(compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
 441             l >= r,
 442             "Invalid (>=):\n l: {:?}\n r: {:?}",
 443             l,
 444             r
 445         );
 446         assert_eq!(
 447             matches!(alt_compare, Some(Ordering::Less)),
 448             r < l,
 449             "Invalid alt (<):\n l: {:?}\n r: {:?}",
 450             l,
 451             r
 452         );
 453         assert_eq!(
 454             matches!(alt_compare, Some(Ordering::Less) | Some(Ordering::Equal)),
 455             r <= l,
 456             "Invalid alt (<=):\n l: {:?}\n r: {:?}",
 457             l,
 458             r
 459         );
 460         assert_eq!(
 461             matches!(alt_compare, Some(Ordering::Greater)),
 462             r > l,
 463             "Invalid alt (>):\n l: {:?}\n r: {:?}",
 464             l,
 465             r
 466         );
 467         assert_eq!(
 468             matches!(alt_compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
 469             r >= l,
 470             "Invalid alt (>=):\n l: {:?}\n r: {:?}",
 471             l,
 472             r
 473         );
 474     }
 475 }