1 // Copyright 2018 Amazon.com, Inc. or its affiliates. All Rights Reserved. 2 // SPDX-License-Identifier: Apache-2.0 3 // 4 // Portions Copyright 2017 The Chromium OS Authors. All rights reserved. 5 // Use of this source code is governed by a BSD-style license that can be 6 // found in the LICENSE-BSD-3-Clause file. 7 8 //! Handles routing to devices in an address space. 9 10 use std::cmp::Ordering; 11 use std::collections::btree_map::BTreeMap; 12 use std::sync::{Arc, Barrier, Mutex, RwLock, Weak}; 13 use std::{convert, io, result}; 14 15 use thiserror::Error; 16 17 /// Trait for devices that respond to reads or writes in an arbitrary address space. 18 /// 19 /// The device does not care where it exists in address space as each method is only given an offset 20 /// into its allocated portion of address space. 21 #[allow(unused_variables)] 22 pub trait BusDevice: Send { 23 /// Reads at `offset` from this device 24 fn read(&mut self, base: u64, offset: u64, data: &mut [u8]) {} 25 /// Writes at `offset` into this device 26 fn write(&mut self, base: u64, offset: u64, data: &[u8]) -> Option<Arc<Barrier>> { 27 None 28 } 29 } 30 31 #[allow(unused_variables)] 32 pub trait BusDeviceSync: Send + Sync { 33 /// Reads at `offset` from this device 34 fn read(&self, base: u64, offset: u64, data: &mut [u8]) {} 35 /// Writes at `offset` into this device 36 fn write(&self, base: u64, offset: u64, data: &[u8]) -> Option<Arc<Barrier>> { 37 None 38 } 39 } 40 41 impl<B: BusDevice> BusDeviceSync for Mutex<B> { 42 /// Reads at `offset` from this device 43 fn read(&self, base: u64, offset: u64, data: &mut [u8]) { 44 self.lock() 45 .expect("Failed to acquire device lock") 46 .read(base, offset, data) 47 } 48 /// Writes at `offset` into this device 49 fn write(&self, base: u64, offset: u64, data: &[u8]) -> Option<Arc<Barrier>> { 50 self.lock() 51 .expect("Failed to acquire device lock") 52 .write(base, offset, data) 53 } 54 } 55 56 #[derive(Error, Debug)] 57 pub enum Error { 58 /// The insertion failed because the new device overlapped with an old device. 59 #[error("The insertion failed because the new device overlapped with an old device")] 60 Overlap, 61 /// Failed to operate on zero sized range. 62 #[error("Failed to operate on zero sized range")] 63 ZeroSizedRange, 64 /// Failed to find address range. 65 #[error("Failed to find address range")] 66 MissingAddressRange, 67 } 68 69 pub type Result<T> = result::Result<T, Error>; 70 71 impl convert::From<Error> for io::Error { 72 fn from(e: Error) -> Self { 73 io::Error::other(e) 74 } 75 } 76 77 /// Holds a base and length representing the address space occupied by a `BusDevice`. 78 /// 79 /// * base - The address at which the range start. 80 /// * len - The length of the range in bytes. 81 #[derive(Debug, Copy, Clone)] 82 pub struct BusRange { 83 pub base: u64, 84 pub len: u64, 85 } 86 87 impl BusRange { 88 /// Returns true if there is overlap with the given range. 89 pub fn overlaps(&self, base: u64, len: u64) -> bool { 90 self.base < (base + len) && base < self.base + self.len 91 } 92 } 93 94 impl Eq for BusRange {} 95 96 impl PartialEq for BusRange { 97 fn eq(&self, other: &BusRange) -> bool { 98 self.base == other.base 99 } 100 } 101 102 impl Ord for BusRange { 103 fn cmp(&self, other: &BusRange) -> Ordering { 104 self.base.cmp(&other.base) 105 } 106 } 107 108 impl PartialOrd for BusRange { 109 fn partial_cmp(&self, other: &BusRange) -> Option<Ordering> { 110 Some(self.cmp(other)) 111 } 112 } 113 114 /// A device container for routing reads and writes over some address space. 115 /// 116 /// This doesn't have any restrictions on what kind of device or address space this applies to. The 117 /// only restriction is that no two devices can overlap in this address space. 118 #[derive(Default)] 119 pub struct Bus { 120 devices: RwLock<BTreeMap<BusRange, Weak<dyn BusDeviceSync>>>, 121 } 122 123 impl Bus { 124 /// Constructs an a bus with an empty address space. 125 pub fn new() -> Bus { 126 Bus { 127 devices: RwLock::new(BTreeMap::new()), 128 } 129 } 130 131 fn first_before(&self, addr: u64) -> Option<(BusRange, Arc<dyn BusDeviceSync>)> { 132 let devices = self.devices.read().unwrap(); 133 let (range, dev) = devices 134 .range(..=BusRange { base: addr, len: 1 }) 135 .next_back()?; 136 dev.upgrade().map(|d| (*range, d.clone())) 137 } 138 139 #[allow(clippy::type_complexity)] 140 fn resolve(&self, addr: u64) -> Option<(u64, u64, Arc<dyn BusDeviceSync>)> { 141 if let Some((range, dev)) = self.first_before(addr) { 142 let offset = addr - range.base; 143 if offset < range.len { 144 return Some((range.base, offset, dev)); 145 } 146 } 147 None 148 } 149 150 pub fn insert(&self, device: Arc<dyn BusDeviceSync>, base: u64, len: u64) -> Result<()> { 151 if len == 0 { 152 return Err(Error::ZeroSizedRange); 153 } 154 155 // Reject all cases where the new device's range overlaps with an existing device. 156 if self 157 .devices 158 .read() 159 .unwrap() 160 .iter() 161 .any(|(range, _dev)| range.overlaps(base, len)) 162 { 163 return Err(Error::Overlap); 164 } 165 166 if self 167 .devices 168 .write() 169 .unwrap() 170 .insert(BusRange { base, len }, Arc::downgrade(&device)) 171 .is_some() 172 { 173 return Err(Error::Overlap); 174 } 175 176 Ok(()) 177 } 178 179 /// Removes the device at the given address space range. 180 pub fn remove(&self, base: u64, len: u64) -> Result<()> { 181 if len == 0 { 182 return Err(Error::ZeroSizedRange); 183 } 184 185 let bus_range = BusRange { base, len }; 186 187 if self.devices.write().unwrap().remove(&bus_range).is_none() { 188 return Err(Error::MissingAddressRange); 189 } 190 191 Ok(()) 192 } 193 194 /// Removes all entries referencing the given device. 195 pub fn remove_by_device(&self, device: &Arc<dyn BusDeviceSync>) -> Result<()> { 196 let mut device_list = self.devices.write().unwrap(); 197 let mut remove_key_list = Vec::new(); 198 199 for (key, value) in device_list.iter() { 200 if Arc::ptr_eq(&value.upgrade().unwrap(), device) { 201 remove_key_list.push(*key); 202 } 203 } 204 205 for key in remove_key_list.iter() { 206 device_list.remove(key); 207 } 208 209 Ok(()) 210 } 211 212 /// Updates the address range for an existing device. 213 pub fn update_range( 214 &self, 215 old_base: u64, 216 old_len: u64, 217 new_base: u64, 218 new_len: u64, 219 ) -> Result<()> { 220 // Retrieve the device corresponding to the range 221 let device = if let Some((_, _, dev)) = self.resolve(old_base) { 222 dev.clone() 223 } else { 224 return Err(Error::MissingAddressRange); 225 }; 226 227 // Remove the old address range 228 self.remove(old_base, old_len)?; 229 230 // Insert the new address range 231 self.insert(device, new_base, new_len) 232 } 233 234 /// Reads data from the device that owns the range containing `addr` and puts it into `data`. 235 /// 236 /// Returns true on success, otherwise `data` is untouched. 237 pub fn read(&self, addr: u64, data: &mut [u8]) -> Result<()> { 238 if let Some((base, offset, dev)) = self.resolve(addr) { 239 // OK to unwrap as lock() failing is a serious error condition and should panic. 240 dev.read(base, offset, data); 241 Ok(()) 242 } else { 243 Err(Error::MissingAddressRange) 244 } 245 } 246 247 /// Writes `data` to the device that owns the range containing `addr`. 248 /// 249 /// Returns true on success, otherwise `data` is untouched. 250 pub fn write(&self, addr: u64, data: &[u8]) -> Result<Option<Arc<Barrier>>> { 251 if let Some((base, offset, dev)) = self.resolve(addr) { 252 // OK to unwrap as lock() failing is a serious error condition and should panic. 253 Ok(dev.write(base, offset, data)) 254 } else { 255 Err(Error::MissingAddressRange) 256 } 257 } 258 } 259 260 #[cfg(test)] 261 mod tests { 262 use super::*; 263 264 struct DummyDevice; 265 impl BusDeviceSync for DummyDevice {} 266 267 struct ConstantDevice; 268 impl BusDeviceSync for ConstantDevice { 269 fn read(&self, _base: u64, offset: u64, data: &mut [u8]) { 270 for (i, v) in data.iter_mut().enumerate() { 271 *v = (offset as u8) + (i as u8); 272 } 273 } 274 275 fn write(&self, _base: u64, offset: u64, data: &[u8]) -> Option<Arc<Barrier>> { 276 for (i, v) in data.iter().enumerate() { 277 assert_eq!(*v, (offset as u8) + (i as u8)) 278 } 279 280 None 281 } 282 } 283 284 #[test] 285 fn bus_insert() { 286 let bus = Bus::new(); 287 let dummy = Arc::new(DummyDevice); 288 bus.insert(dummy.clone(), 0x10, 0).unwrap_err(); 289 bus.insert(dummy.clone(), 0x10, 0x10).unwrap(); 290 291 let result = bus.insert(dummy.clone(), 0x0f, 0x10); 292 assert_eq!(format!("{result:?}"), "Err(Overlap)"); 293 294 bus.insert(dummy.clone(), 0x10, 0x10).unwrap_err(); 295 bus.insert(dummy.clone(), 0x10, 0x15).unwrap_err(); 296 bus.insert(dummy.clone(), 0x12, 0x15).unwrap_err(); 297 bus.insert(dummy.clone(), 0x12, 0x01).unwrap_err(); 298 bus.insert(dummy.clone(), 0x0, 0x20).unwrap_err(); 299 bus.insert(dummy.clone(), 0x20, 0x05).unwrap(); 300 bus.insert(dummy.clone(), 0x25, 0x05).unwrap(); 301 bus.insert(dummy, 0x0, 0x10).unwrap(); 302 } 303 304 #[test] 305 #[allow(clippy::redundant_clone)] 306 fn bus_read_write() { 307 let bus = Bus::new(); 308 let dummy = Arc::new(DummyDevice); 309 bus.insert(dummy.clone(), 0x10, 0x10).unwrap(); 310 bus.read(0x10, &mut [0, 0, 0, 0]).unwrap(); 311 bus.write(0x10, &[0, 0, 0, 0]).unwrap(); 312 bus.read(0x11, &mut [0, 0, 0, 0]).unwrap(); 313 bus.write(0x11, &[0, 0, 0, 0]).unwrap(); 314 bus.read(0x16, &mut [0, 0, 0, 0]).unwrap(); 315 bus.write(0x16, &[0, 0, 0, 0]).unwrap(); 316 bus.read(0x20, &mut [0, 0, 0, 0]).unwrap_err(); 317 bus.write(0x20, &[0, 0, 0, 0]).unwrap_err(); 318 bus.read(0x06, &mut [0, 0, 0, 0]).unwrap_err(); 319 bus.write(0x06, &[0, 0, 0, 0]).unwrap_err(); 320 } 321 322 #[test] 323 #[allow(clippy::redundant_clone)] 324 fn bus_read_write_values() { 325 let bus = Bus::new(); 326 let dummy = Arc::new(ConstantDevice); 327 bus.insert(dummy.clone(), 0x10, 0x10).unwrap(); 328 329 let mut values = [0, 1, 2, 3]; 330 bus.read(0x10, &mut values).unwrap(); 331 assert_eq!(values, [0, 1, 2, 3]); 332 bus.write(0x10, &values).unwrap(); 333 bus.read(0x15, &mut values).unwrap(); 334 assert_eq!(values, [5, 6, 7, 8]); 335 bus.write(0x15, &values).unwrap(); 336 } 337 338 #[test] 339 #[allow(clippy::redundant_clone)] 340 fn busrange_cmp() { 341 let range = BusRange { base: 0x10, len: 2 }; 342 assert_eq!(range, BusRange { base: 0x10, len: 3 }); 343 assert_eq!(range, BusRange { base: 0x10, len: 2 }); 344 345 assert!(range < BusRange { base: 0x12, len: 1 }); 346 assert!(range < BusRange { base: 0x12, len: 3 }); 347 348 assert_eq!(range, range.clone()); 349 350 let bus = Bus::new(); 351 let mut data = [1, 2, 3, 4]; 352 let device = Arc::new(DummyDevice); 353 bus.insert(device.clone(), 0x10, 0x10).unwrap(); 354 bus.write(0x10, &data).unwrap(); 355 bus.read(0x10, &mut data).unwrap(); 356 assert_eq!(data, [1, 2, 3, 4]); 357 } 358 359 #[test] 360 fn bus_range_overlap() { 361 let a = BusRange { 362 base: 0x1000, 363 len: 0x400, 364 }; 365 assert!(a.overlaps(0x1000, 0x400)); 366 assert!(a.overlaps(0xf00, 0x400)); 367 assert!(a.overlaps(0x1000, 0x01)); 368 assert!(a.overlaps(0xfff, 0x02)); 369 assert!(a.overlaps(0x1100, 0x100)); 370 assert!(a.overlaps(0x13ff, 0x100)); 371 assert!(!a.overlaps(0x1400, 0x100)); 372 assert!(!a.overlaps(0xf00, 0x100)); 373 } 374 } 375