1 use std::cell::RefCell; 2 use std::cmp::max; 3 use std::collections::hash_map::Entry; 4 5 use log::trace; 6 use rand::Rng; 7 8 use rustc_data_structures::fx::{FxHashMap, FxHashSet}; 9 use rustc_span::Span; 10 use rustc_target::abi::{HasDataLayout, Size}; 11 12 use crate::*; 13 14 #[derive(Copy, Clone, Debug, PartialEq, Eq)] 15 pub enum ProvenanceMode { 16 /// We support `expose_addr`/`from_exposed_addr` via "wildcard" provenance. 17 /// However, we want on `from_exposed_addr` to alert the user of the precision loss. 18 Default, 19 /// Like `Default`, but without the warning. 20 Permissive, 21 /// We error on `from_exposed_addr`, ensuring no precision loss. 22 Strict, 23 } 24 25 pub type GlobalState = RefCell<GlobalStateInner>; 26 27 #[derive(Clone, Debug)] 28 pub struct GlobalStateInner { 29 /// This is used as a map between the address of each allocation and its `AllocId`. 30 /// It is always sorted 31 int_to_ptr_map: Vec<(u64, AllocId)>, 32 /// The base address for each allocation. We cannot put that into 33 /// `AllocExtra` because function pointers also have a base address, and 34 /// they do not have an `AllocExtra`. 35 /// This is the inverse of `int_to_ptr_map`. 36 base_addr: FxHashMap<AllocId, u64>, 37 /// Whether an allocation has been exposed or not. This cannot be put 38 /// into `AllocExtra` for the same reason as `base_addr`. 39 exposed: FxHashSet<AllocId>, 40 /// This is used as a memory address when a new pointer is casted to an integer. It 41 /// is always larger than any address that was previously made part of a block. 42 next_base_addr: u64, 43 /// The provenance to use for int2ptr casts 44 provenance_mode: ProvenanceMode, 45 } 46 47 impl VisitTags for GlobalStateInner { visit_tags(&self, _visit: &mut dyn FnMut(BorTag))48 fn visit_tags(&self, _visit: &mut dyn FnMut(BorTag)) { 49 // Nothing to visit here. 50 } 51 } 52 53 impl GlobalStateInner { new(config: &MiriConfig, stack_addr: u64) -> Self54 pub fn new(config: &MiriConfig, stack_addr: u64) -> Self { 55 GlobalStateInner { 56 int_to_ptr_map: Vec::default(), 57 base_addr: FxHashMap::default(), 58 exposed: FxHashSet::default(), 59 next_base_addr: stack_addr, 60 provenance_mode: config.provenance_mode, 61 } 62 } 63 } 64 65 impl<'mir, 'tcx> GlobalStateInner { 66 // Returns the exposed `AllocId` that corresponds to the specified addr, 67 // or `None` if the addr is out of bounds alloc_id_from_addr(ecx: &MiriInterpCx<'mir, 'tcx>, addr: u64) -> Option<AllocId>68 fn alloc_id_from_addr(ecx: &MiriInterpCx<'mir, 'tcx>, addr: u64) -> Option<AllocId> { 69 let global_state = ecx.machine.intptrcast.borrow(); 70 assert!(global_state.provenance_mode != ProvenanceMode::Strict); 71 72 let pos = global_state.int_to_ptr_map.binary_search_by_key(&addr, |(addr, _)| *addr); 73 74 // Determine the in-bounds provenance for this pointer. 75 // (This is only called on an actual access, so in-bounds is the only possible kind of provenance.) 76 let alloc_id = match pos { 77 Ok(pos) => Some(global_state.int_to_ptr_map[pos].1), 78 Err(0) => None, 79 Err(pos) => { 80 // This is the largest of the addresses smaller than `int`, 81 // i.e. the greatest lower bound (glb) 82 let (glb, alloc_id) = global_state.int_to_ptr_map[pos - 1]; 83 // This never overflows because `addr >= glb` 84 let offset = addr - glb; 85 // If the offset exceeds the size of the allocation, don't use this `alloc_id`. 86 let size = ecx.get_alloc_info(alloc_id).0; 87 if offset <= size.bytes() { Some(alloc_id) } else { None } 88 } 89 }?; 90 91 // We only use this provenance if it has been exposed, *and* is still live. 92 if global_state.exposed.contains(&alloc_id) { 93 let (_size, _align, kind) = ecx.get_alloc_info(alloc_id); 94 match kind { 95 AllocKind::LiveData | AllocKind::Function | AllocKind::VTable => { 96 return Some(alloc_id); 97 } 98 AllocKind::Dead => {} 99 } 100 } 101 102 None 103 } 104 expose_ptr( ecx: &mut MiriInterpCx<'mir, 'tcx>, alloc_id: AllocId, tag: BorTag, ) -> InterpResult<'tcx>105 pub fn expose_ptr( 106 ecx: &mut MiriInterpCx<'mir, 'tcx>, 107 alloc_id: AllocId, 108 tag: BorTag, 109 ) -> InterpResult<'tcx> { 110 let global_state = ecx.machine.intptrcast.get_mut(); 111 // In strict mode, we don't need this, so we can save some cycles by not tracking it. 112 if global_state.provenance_mode != ProvenanceMode::Strict { 113 trace!("Exposing allocation id {alloc_id:?}"); 114 global_state.exposed.insert(alloc_id); 115 if ecx.machine.borrow_tracker.is_some() { 116 ecx.expose_tag(alloc_id, tag)?; 117 } 118 } 119 Ok(()) 120 } 121 ptr_from_addr_transmute( _ecx: &MiriInterpCx<'mir, 'tcx>, addr: u64, ) -> Pointer<Option<Provenance>>122 pub fn ptr_from_addr_transmute( 123 _ecx: &MiriInterpCx<'mir, 'tcx>, 124 addr: u64, 125 ) -> Pointer<Option<Provenance>> { 126 trace!("Transmuting {:#x} to a pointer", addr); 127 128 // We consider transmuted pointers to be "invalid" (`None` provenance). 129 Pointer::new(None, Size::from_bytes(addr)) 130 } 131 ptr_from_addr_cast( ecx: &MiriInterpCx<'mir, 'tcx>, addr: u64, ) -> InterpResult<'tcx, Pointer<Option<Provenance>>>132 pub fn ptr_from_addr_cast( 133 ecx: &MiriInterpCx<'mir, 'tcx>, 134 addr: u64, 135 ) -> InterpResult<'tcx, Pointer<Option<Provenance>>> { 136 trace!("Casting {:#x} to a pointer", addr); 137 138 let global_state = ecx.machine.intptrcast.borrow(); 139 140 match global_state.provenance_mode { 141 ProvenanceMode::Default => { 142 // The first time this happens at a particular location, print a warning. 143 thread_local! { 144 // `Span` is non-`Send`, so we use a thread-local instead. 145 static PAST_WARNINGS: RefCell<FxHashSet<Span>> = RefCell::default(); 146 } 147 PAST_WARNINGS.with_borrow_mut(|past_warnings| { 148 let first = past_warnings.is_empty(); 149 if past_warnings.insert(ecx.cur_span()) { 150 // Newly inserted, so first time we see this span. 151 ecx.emit_diagnostic(NonHaltingDiagnostic::Int2Ptr { details: first }); 152 } 153 }); 154 } 155 ProvenanceMode::Strict => { 156 throw_machine_stop!(TerminationInfo::Int2PtrWithStrictProvenance); 157 } 158 ProvenanceMode::Permissive => {} 159 } 160 161 // This is how wildcard pointers are born. 162 Ok(Pointer::new(Some(Provenance::Wildcard), Size::from_bytes(addr))) 163 } 164 alloc_base_addr( ecx: &MiriInterpCx<'mir, 'tcx>, alloc_id: AllocId, ) -> InterpResult<'tcx, u64>165 fn alloc_base_addr( 166 ecx: &MiriInterpCx<'mir, 'tcx>, 167 alloc_id: AllocId, 168 ) -> InterpResult<'tcx, u64> { 169 let mut global_state = ecx.machine.intptrcast.borrow_mut(); 170 let global_state = &mut *global_state; 171 172 Ok(match global_state.base_addr.entry(alloc_id) { 173 Entry::Occupied(entry) => *entry.get(), 174 Entry::Vacant(entry) => { 175 // There is nothing wrong with a raw pointer being cast to an integer only after 176 // it became dangling. Hence we allow dead allocations. 177 let (size, align, _kind) = ecx.get_alloc_info(alloc_id); 178 179 // This allocation does not have a base address yet, pick one. 180 // Leave some space to the previous allocation, to give it some chance to be less aligned. 181 let slack = { 182 let mut rng = ecx.machine.rng.borrow_mut(); 183 // This means that `(global_state.next_base_addr + slack) % 16` is uniformly distributed. 184 rng.gen_range(0..16) 185 }; 186 // From next_base_addr + slack, round up to adjust for alignment. 187 let base_addr = global_state 188 .next_base_addr 189 .checked_add(slack) 190 .ok_or_else(|| err_exhaust!(AddressSpaceFull))?; 191 let base_addr = Self::align_addr(base_addr, align.bytes()); 192 entry.insert(base_addr); 193 trace!( 194 "Assigning base address {:#x} to allocation {:?} (size: {}, align: {}, slack: {})", 195 base_addr, 196 alloc_id, 197 size.bytes(), 198 align.bytes(), 199 slack, 200 ); 201 202 // Remember next base address. If this allocation is zero-sized, leave a gap 203 // of at least 1 to avoid two allocations having the same base address. 204 // (The logic in `alloc_id_from_addr` assumes unique addresses, and different 205 // function/vtable pointers need to be distinguishable!) 206 global_state.next_base_addr = base_addr 207 .checked_add(max(size.bytes(), 1)) 208 .ok_or_else(|| err_exhaust!(AddressSpaceFull))?; 209 // Even if `Size` didn't overflow, we might still have filled up the address space. 210 if global_state.next_base_addr > ecx.target_usize_max() { 211 throw_exhaust!(AddressSpaceFull); 212 } 213 // Given that `next_base_addr` increases in each allocation, pushing the 214 // corresponding tuple keeps `int_to_ptr_map` sorted 215 global_state.int_to_ptr_map.push((base_addr, alloc_id)); 216 217 base_addr 218 } 219 }) 220 } 221 222 /// Convert a relative (tcx) pointer to an absolute address. rel_ptr_to_addr( ecx: &MiriInterpCx<'mir, 'tcx>, ptr: Pointer<AllocId>, ) -> InterpResult<'tcx, u64>223 pub fn rel_ptr_to_addr( 224 ecx: &MiriInterpCx<'mir, 'tcx>, 225 ptr: Pointer<AllocId>, 226 ) -> InterpResult<'tcx, u64> { 227 let (alloc_id, offset) = ptr.into_parts(); // offset is relative (AllocId provenance) 228 let base_addr = GlobalStateInner::alloc_base_addr(ecx, alloc_id)?; 229 230 // Add offset with the right kind of pointer-overflowing arithmetic. 231 let dl = ecx.data_layout(); 232 Ok(dl.overflowing_offset(base_addr, offset.bytes()).0) 233 } 234 235 /// When a pointer is used for a memory access, this computes where in which allocation the 236 /// access is going. abs_ptr_to_rel( ecx: &MiriInterpCx<'mir, 'tcx>, ptr: Pointer<Provenance>, ) -> Option<(AllocId, Size)>237 pub fn abs_ptr_to_rel( 238 ecx: &MiriInterpCx<'mir, 'tcx>, 239 ptr: Pointer<Provenance>, 240 ) -> Option<(AllocId, Size)> { 241 let (tag, addr) = ptr.into_parts(); // addr is absolute (Tag provenance) 242 243 let alloc_id = if let Provenance::Concrete { alloc_id, .. } = tag { 244 alloc_id 245 } else { 246 // A wildcard pointer. 247 GlobalStateInner::alloc_id_from_addr(ecx, addr.bytes())? 248 }; 249 250 // This cannot fail: since we already have a pointer with that provenance, rel_ptr_to_addr 251 // must have been called in the past. 252 let base_addr = GlobalStateInner::alloc_base_addr(ecx, alloc_id).unwrap(); 253 254 // Wrapping "addr - base_addr" 255 let dl = ecx.data_layout(); 256 #[allow(clippy::cast_possible_wrap)] // we want to wrap here 257 let neg_base_addr = (base_addr as i64).wrapping_neg(); 258 Some(( 259 alloc_id, 260 Size::from_bytes(dl.overflowing_signed_offset(addr.bytes(), neg_base_addr).0), 261 )) 262 } 263 264 /// Shifts `addr` to make it aligned with `align` by rounding `addr` to the smallest multiple 265 /// of `align` that is larger or equal to `addr` align_addr(addr: u64, align: u64) -> u64266 fn align_addr(addr: u64, align: u64) -> u64 { 267 match addr % align { 268 0 => addr, 269 rem => addr.checked_add(align).unwrap() - rem, 270 } 271 } 272 } 273 274 #[cfg(test)] 275 mod tests { 276 use super::*; 277 278 #[test] test_align_addr()279 fn test_align_addr() { 280 assert_eq!(GlobalStateInner::align_addr(37, 4), 40); 281 assert_eq!(GlobalStateInner::align_addr(44, 4), 44); 282 } 283 } 284