src/tools/miri/src/concurrency/range_object_map.rs

   1 //! Implements a map from allocation ranges to data. This is somewhat similar to RangeMap, but the
   2 //! ranges and data are discrete and non-splittable -- they represent distinct "objects". An
   3 //! allocation in the map will always have the same range until explicitly removed
   4
   5 use rustc_target::abi::Size;
   6 use std::ops::{Index, IndexMut, Range};
   7
   8 use rustc_const_eval::interpret::AllocRange;
   9
  10 #[derive(Clone, Debug)]
  11 struct Elem<T> {
  12     /// The range covered by this element; never empty.
  13     range: AllocRange,
  14     /// The data stored for this element.
  15     data: T,
  16 }
  17
  18 /// Index of an allocation within the map
  19 type Position = usize;
  20
  21 #[derive(Clone, Debug)]
  22 pub struct RangeObjectMap<T> {
  23     v: Vec<Elem<T>>,
  24 }
  25
  26 #[derive(Clone, Debug, PartialEq)]
  27 pub enum AccessType {
  28     /// The access perfectly overlaps (same offset and range) with the exsiting allocation
  29     PerfectlyOverlapping(Position),
  30     /// The access does not touch any exising allocation
  31     Empty(Position),
  32     /// The access overlaps with one or more existing allocations
  33     ImperfectlyOverlapping(Range<Position>),
  34 }
  35
  36 impl<T> RangeObjectMap<T> {
  37     pub fn new() -> Self {
  38         Self { v: Vec::new() }
  39     }
  40
  41     /// Finds the position of the allocation containing the given offset. If the offset is not
  42     /// in an existing allocation, then returns Err containing the position
  43     /// where such allocation should be inserted
  44     fn find_offset(&self, offset: Size) -> Result<Position, Position> {
  45         // We do a binary search.
  46         let mut left = 0usize; // inclusive
  47         let mut right = self.v.len(); // exclusive
  48         loop {
  49             if left == right {
  50                 // No element contains the given offset. But the
  51                 // position is where such element should be placed at.
  52                 return Err(left);
  53             }
  54             let candidate = left.checked_add(right).unwrap() / 2;
  55             let elem = &self.v[candidate];
  56             if offset < elem.range.start {
  57                 // We are too far right (offset is further left).
  58                 debug_assert!(candidate < right); // we are making progress
  59                 right = candidate;
  60             } else if offset >= elem.range.end() {
  61                 // We are too far left (offset is further right).
  62                 debug_assert!(candidate >= left); // we are making progress
  63                 left = candidate + 1;
  64             } else {
  65                 // This is it!
  66                 return Ok(candidate);
  67             }
  68         }
  69     }
  70
  71     /// Determines whether a given access on `range` overlaps with
  72     /// an existing allocation
  73     pub fn access_type(&self, range: AllocRange) -> AccessType {
  74         match self.find_offset(range.start) {
  75             Ok(pos) => {
  76                 // Start of the range belongs to an existing object, now let's check the overlapping situation
  77                 let elem = &self.v[pos];
  78                 // FIXME: derive Eq for AllocRange in rustc
  79                 if elem.range.start == range.start && elem.range.size == range.size {
  80                     // Happy case: perfectly overlapping access
  81                     AccessType::PerfectlyOverlapping(pos)
  82                 } else {
  83                     // FIXME: add a last() method to AllocRange that returns the last inclusive offset (end() is exclusive)
  84                     let end_pos = match self.find_offset(range.end() - Size::from_bytes(1)) {
  85                         // If the end lands in an existing object, add one to get the exclusive position
  86                         Ok(inclusive_pos) => inclusive_pos + 1,
  87                         Err(exclusive_pos) => exclusive_pos,
  88                     };
  89
  90                     AccessType::ImperfectlyOverlapping(pos..end_pos)
  91                 }
  92             }
  93             Err(pos) => {
  94                 // Start of the range doesn't belong to an existing object
  95                 match self.find_offset(range.end() - Size::from_bytes(1)) {
  96                     // Neither does the end
  97                     Err(end_pos) =>
  98                         if pos == end_pos {
  99                             // There's nothing between the start and the end, so the range thing is empty
 100                             AccessType::Empty(pos)
 101                         } else {
 102                             // Otherwise we have entirely covered an existing object
 103                             AccessType::ImperfectlyOverlapping(pos..end_pos)
 104                         },
 105                     // Otherwise at least part of it overlaps with something else
 106                     Ok(end_pos) => AccessType::ImperfectlyOverlapping(pos..end_pos + 1),
 107                 }
 108             }
 109         }
 110     }
 111
 112     /// Inserts an object and its occupied range at given position
 113     // The Position can be calculated from AllocRange, but the only user of AllocationMap
 114     // always calls access_type before calling insert/index/index_mut, and we don't
 115     // want to repeat the binary search on each time, so we ask the caller to supply Position
 116     pub fn insert_at_pos(&mut self, pos: Position, range: AllocRange, data: T) {
 117         self.v.insert(pos, Elem { range, data });
 118         // If we aren't the first element, then our start must be greater than the preivous element's end
 119         if pos > 0 {
 120             assert!(self.v[pos - 1].range.end() <= range.start);
 121         }
 122         // If we aren't the last element, then our end must be smaller than next element's start
 123         if pos < self.v.len() - 1 {
 124             assert!(range.end() <= self.v[pos + 1].range.start);
 125         }
 126     }
 127
 128     pub fn remove_pos_range(&mut self, pos_range: Range<Position>) {
 129         self.v.drain(pos_range);
 130     }
 131
 132     pub fn remove_from_pos(&mut self, pos: Position) {
 133         self.v.remove(pos);
 134     }
 135
 136     pub fn iter(&self) -> impl Iterator<Item = &T> {
 137         self.v.iter().map(|e| &e.data)
 138     }
 139 }
 140
 141 impl<T> Index<Position> for RangeObjectMap<T> {
 142     type Output = T;
 143
 144     fn index(&self, pos: Position) -> &Self::Output {
 145         &self.v[pos].data
 146     }
 147 }
 148
 149 impl<T> IndexMut<Position> for RangeObjectMap<T> {
 150     fn index_mut(&mut self, pos: Position) -> &mut Self::Output {
 151         &mut self.v[pos].data
 152     }
 153 }
 154
 155 #[cfg(test)]
 156 mod tests {
 157     use rustc_const_eval::interpret::alloc_range;
 158
 159     use super::*;
 160
 161     #[test]
 162     fn empty_map() {
 163         // FIXME: make Size::from_bytes const
 164         let four = Size::from_bytes(4);
 165         let map = RangeObjectMap::<()>::new();
 166
 167         // Correctly tells where we should insert the first element (at position 0)
 168         assert_eq!(map.find_offset(Size::from_bytes(3)), Err(0));
 169
 170         // Correctly tells the access type along with the supposed position
 171         assert_eq!(map.access_type(alloc_range(Size::ZERO, four)), AccessType::Empty(0));
 172     }
 173
 174     #[test]
 175     #[should_panic]
 176     fn no_overlapping_inserts() {
 177         let four = Size::from_bytes(4);
 178
 179         let mut map = RangeObjectMap::<&str>::new();
 180
 181         // |_|_|_|_|#|#|#|#|_|_|_|_|...
 182         //  0 1 2 3 4 5 6 7 8 9 a b c d
 183         map.insert_at_pos(0, alloc_range(four, four), "#");
 184         // |_|_|_|_|#|#|#|#|_|_|_|_|...
 185         //  0 ^ ^ ^ ^ 5 6 7 8 9 a b c d
 186         map.insert_at_pos(0, alloc_range(Size::from_bytes(1), four), "@");
 187     }
 188
 189     #[test]
 190     fn boundaries() {
 191         let four = Size::from_bytes(4);
 192
 193         let mut map = RangeObjectMap::<&str>::new();
 194
 195         // |#|#|#|#|_|_|...
 196         //  0 1 2 3 4 5
 197         map.insert_at_pos(0, alloc_range(Size::ZERO, four), "#");
 198         // |#|#|#|#|_|_|...
 199         //  0 1 2 3 ^ 5
 200         assert_eq!(map.find_offset(four), Err(1));
 201         // |#|#|#|#|_|_|_|_|_|...
 202         //  0 1 2 3 ^ ^ ^ ^ 8
 203         assert_eq!(map.access_type(alloc_range(four, four)), AccessType::Empty(1));
 204
 205         let eight = Size::from_bytes(8);
 206         // |#|#|#|#|_|_|_|_|@|@|@|@|_|_|...
 207         //  0 1 2 3 4 5 6 7 8 9 a b c d
 208         map.insert_at_pos(1, alloc_range(eight, four), "@");
 209         // |#|#|#|#|_|_|_|_|@|@|@|@|_|_|...
 210         //  0 1 2 3 4 5 6 ^ 8 9 a b c d
 211         assert_eq!(map.find_offset(Size::from_bytes(7)), Err(1));
 212         // |#|#|#|#|_|_|_|_|@|@|@|@|_|_|...
 213         //  0 1 2 3 ^ ^ ^ ^ 8 9 a b c d
 214         assert_eq!(map.access_type(alloc_range(four, four)), AccessType::Empty(1));
 215     }
 216
 217     #[test]
 218     fn perfectly_overlapping() {
 219         let four = Size::from_bytes(4);
 220
 221         let mut map = RangeObjectMap::<&str>::new();
 222
 223         // |#|#|#|#|_|_|...
 224         //  0 1 2 3 4 5
 225         map.insert_at_pos(0, alloc_range(Size::ZERO, four), "#");
 226         // |#|#|#|#|_|_|...
 227         //  ^ ^ ^ ^ 4 5
 228         assert_eq!(map.find_offset(Size::ZERO), Ok(0));
 229         assert_eq!(
 230             map.access_type(alloc_range(Size::ZERO, four)),
 231             AccessType::PerfectlyOverlapping(0)
 232         );
 233
 234         // |#|#|#|#|@|@|@|@|_|...
 235         //  0 1 2 3 4 5 6 7 8
 236         map.insert_at_pos(1, alloc_range(four, four), "@");
 237         // |#|#|#|#|@|@|@|@|_|...
 238         //  0 1 2 3 ^ ^ ^ ^ 8
 239         assert_eq!(map.find_offset(four), Ok(1));
 240         assert_eq!(map.access_type(alloc_range(four, four)), AccessType::PerfectlyOverlapping(1));
 241     }
 242
 243     #[test]
 244     fn straddling() {
 245         let four = Size::from_bytes(4);
 246
 247         let mut map = RangeObjectMap::<&str>::new();
 248
 249         // |_|_|_|_|#|#|#|#|_|_|_|_|...
 250         //  0 1 2 3 4 5 6 7 8 9 a b c d
 251         map.insert_at_pos(0, alloc_range(four, four), "#");
 252         // |_|_|_|_|#|#|#|#|_|_|_|_|...
 253         //  0 1 ^ ^ ^ ^ 6 7 8 9 a b c d
 254         assert_eq!(
 255             map.access_type(alloc_range(Size::from_bytes(2), four)),
 256             AccessType::ImperfectlyOverlapping(0..1)
 257         );
 258         // |_|_|_|_|#|#|#|#|_|_|_|_|...
 259         //  0 1 2 3 4 5 ^ ^ ^ ^ a b c d
 260         assert_eq!(
 261             map.access_type(alloc_range(Size::from_bytes(6), four)),
 262             AccessType::ImperfectlyOverlapping(0..1)
 263         );
 264         // |_|_|_|_|#|#|#|#|_|_|_|_|...
 265         //  0 1 ^ ^ ^ ^ ^ ^ ^ ^ a b c d
 266         assert_eq!(
 267             map.access_type(alloc_range(Size::from_bytes(2), Size::from_bytes(8))),
 268             AccessType::ImperfectlyOverlapping(0..1)
 269         );
 270
 271         // |_|_|_|_|#|#|#|#|_|_|@|@|_|_|...
 272         //  0 1 2 3 4 5 6 7 8 9 a b c d
 273         map.insert_at_pos(1, alloc_range(Size::from_bytes(10), Size::from_bytes(2)), "@");
 274         // |_|_|_|_|#|#|#|#|_|_|@|@|_|_|...
 275         //  0 1 2 3 4 5 ^ ^ ^ ^ ^ ^ ^ ^
 276         assert_eq!(
 277             map.access_type(alloc_range(Size::from_bytes(6), Size::from_bytes(8))),
 278             AccessType::ImperfectlyOverlapping(0..2)
 279         );
 280     }
 281 }