miri/concurrency/
range_object_map.rs

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

miri/concurrency/
range_object_map.rs
