miri/alloc_addresses/
reuse_pool.rs

Help
1//! Manages a pool of addresses that can be reused.
2
3use rand::Rng;
4use rustc_abi::{Align, Size};
5
6use crate::concurrency::VClock;
7use crate::{MemoryKind, MiriConfig, ThreadId};
8
9const MAX_POOL_SIZE: usize = 64;
10
11/// The pool strikes a balance between exploring more possible executions and making it more likely
12/// to find bugs. The hypothesis is that bugs are more likely to occur when reuse happens for
13/// allocations with the same layout, since that can trigger e.g. ABA issues in a concurrent data
14/// structure. Therefore we only reuse allocations when size and alignment match exactly.
15#[derive(Debug)]
16pub struct ReusePool {
17    address_reuse_rate: f64,
18    address_reuse_cross_thread_rate: f64,
19    /// The i-th element in `pool` stores allocations of alignment `2^i`. We store these reusable
20    /// allocations as address-size pairs, the list must be sorted by the size and then the thread ID.
21    ///
22    /// Each of these maps has at most MAX_POOL_SIZE elements, and since alignment is limited to
23    /// less than 64 different possible value, that bounds the overall size of the pool.
24    ///
25    /// We also store the ID and the data-race clock of the thread that donated this pool element,
26    /// to ensure synchronization with the thread that picks up this address.
27    pool: Vec<Vec<(u64, Size, ThreadId, VClock)>>,
28}
29
30impl ReusePool {
31    pub fn new(config: &MiriConfig) -> Self {
32        ReusePool {
33            address_reuse_rate: config.address_reuse_rate,
34            address_reuse_cross_thread_rate: config.address_reuse_cross_thread_rate,
35            pool: vec![],
36        }
37    }
38
39    fn subpool(&mut self, align: Align) -> &mut Vec<(u64, Size, ThreadId, VClock)> {
40        let pool_idx: usize = align.bytes().trailing_zeros().try_into().unwrap();
41        if self.pool.len() <= pool_idx {
42            self.pool.resize(pool_idx + 1, Vec::new());
43        }
44        &mut self.pool[pool_idx]
45    }
46
47    pub fn add_addr(
48        &mut self,
49        rng: &mut impl Rng,
50        addr: u64,
51        size: Size,
52        align: Align,
53        kind: MemoryKind,
54        thread: ThreadId,
55        clock: impl FnOnce() -> VClock,
56    ) {
57        // Let's see if we even want to remember this address.
58        // We don't remember stack addresses: there's a lot of them (so the perf impact is big),
59        // and we only want to reuse stack slots within the same thread or else we'll add a lot of
60        // undesired synchronization.
61        if kind == MemoryKind::Stack || !rng.random_bool(self.address_reuse_rate) {
62            return;
63        }
64        let clock = clock();
65        // Determine the pool to add this to, and where in the pool to put it.
66        let subpool = self.subpool(align);
67        let pos = subpool.partition_point(|(_addr, other_size, other_thread, _)| {
68            (*other_size, *other_thread) < (size, thread)
69        });
70        // Make sure the pool does not grow too big.
71        if subpool.len() >= MAX_POOL_SIZE {
72            // Pool full. Replace existing element, or last one if this would be even bigger.
73            let clamped_pos = pos.min(subpool.len() - 1);
74            subpool[clamped_pos] = (addr, size, thread, clock);
75            return;
76        }
77        // Add address to pool, at the right position.
78        subpool.insert(pos, (addr, size, thread, clock));
79    }
80
81    /// Returns the address to use and optionally a clock we have to synchronize with.
82    pub fn take_addr(
83        &mut self,
84        rng: &mut impl Rng,
85        size: Size,
86        align: Align,
87        kind: MemoryKind,
88        thread: ThreadId,
89    ) -> Option<(u64, Option<VClock>)> {
90        // Determine whether we'll even attempt a reuse. As above, we don't do reuse for stack addresses.
91        if kind == MemoryKind::Stack || !rng.random_bool(self.address_reuse_rate) {
92            return None;
93        }
94        let cross_thread_reuse = rng.random_bool(self.address_reuse_cross_thread_rate);
95        // Determine the pool to take this from.
96        let subpool = self.subpool(align);
97        // Let's see if we can find something of the right size. We want to find the full range of
98        // such items, beginning with the first, so we can't use `binary_search_by_key`. If we do
99        // *not* want to consider other thread's allocations, we effectively use the lexicographic
100        // order on `(size, thread)`.
101        let begin = subpool.partition_point(|(_addr, other_size, other_thread, _)| {
102            *other_size < size
103                || (*other_size == size && !cross_thread_reuse && *other_thread < thread)
104        });
105        let mut end = begin;
106        while let Some((_addr, other_size, other_thread, _)) = subpool.get(end) {
107            if *other_size != size {
108                break;
109            }
110            if !cross_thread_reuse && *other_thread != thread {
111                // We entered the allocations of another thread.
112                break;
113            }
114            end += 1;
115        }
116        if end == begin {
117            // Could not find any item of the right size.
118            return None;
119        }
120        // Pick a random element with the desired size.
121        let idx = rng.random_range(begin..end);
122        // Remove it from the pool and return.
123        let (chosen_addr, chosen_size, chosen_thread, clock) = subpool.remove(idx);
124        debug_assert!(chosen_size >= size && chosen_addr % align.bytes() == 0);
125        debug_assert!(cross_thread_reuse || chosen_thread == thread);
126        // No synchronization needed if we reused from the current thread.
127        Some((chosen_addr, if chosen_thread == thread { None } else { Some(clock) }))
128    }
129}
miri/alloc_addresses/reuse_pool.rs

miri/alloc_addresses/
reuse_pool.rs
