Move crosvm/hw to a new devices module

Moving the devices to their own module makes it easier to add tests that
use them.

Change-Id: I61bfef4037d16b20145b5fddce604835cdc4f67b
Signed-off-by: Dylan Reid <dgreid@chromium.org>
Reviewed-on: https://chromium-review.googlesource.com/706559
Reviewed-by: Zach Reizner <zachr@chromium.org>

1 files changed, 217 insertions, 0 deletions

diff --git a/devices/src/bus.rs b/devices/src/bus.rs
new file mode 100644
index 0000000..030694a
--- /dev/null
+++ b/devices/src/bus.rs
@@ -0,0 +1,217 @@
+// Copyright 2017 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+//! Handles routing to devices in an address space.
+
+use std::cmp::{Ord, PartialOrd, PartialEq, Ordering};
+use std::collections::btree_map::BTreeMap;
+use std::result;
+use std::sync::{Arc, Mutex};
+
+/// Trait for devices that respond to reads or writes in an arbitrary address space.
+///
+/// The device does not care where it exists in address space as each method is only given an offset
+/// into its allocated portion of address space.
+#[allow(unused_variables)]
+pub trait BusDevice: Send {
+    /// Reads at `offset` from this device
+    fn read(&mut self, offset: u64, data: &mut [u8]) {}
+    /// Writes at `offset` into this device
+    fn write(&mut self, offset: u64, data: &[u8]) {}
+}
+
+#[derive(Debug)]
+pub enum Error {
+    /// The insertion failed because the new device overlapped with an old device.
+    Overlap,
+}
+
+pub type Result<T> = result::Result<T, Error>;
+
+#[derive(Debug, Copy, Clone)]
+struct BusRange(u64, u64);
+
+impl Eq for BusRange {}
+
+impl PartialEq for BusRange {
+    fn eq(&self, other: &BusRange) -> bool {
+        self.0 == other.0
+    }
+}
+
+impl Ord for BusRange {
+    fn cmp(&self, other: &BusRange) -> Ordering {
+        self.0.cmp(&other.0)
+    }
+}
+
+impl PartialOrd for BusRange {
+    fn partial_cmp(&self, other: &BusRange) -> Option<Ordering> {
+        self.0.partial_cmp(&other.0)
+    }
+}
+
+/// A device container for routing reads and writes over some address space.
+///
+/// This doesn't have any restrictions on what kind of device or address space this applies to. The
+/// only restriction is that no two devices can overlap in this address space.
+#[derive(Clone)]
+pub struct Bus {
+    devices: BTreeMap<BusRange, Arc<Mutex<BusDevice>>>,
+}
+
+impl Bus {
+    /// Constructs an a bus with an empty address space.
+    pub fn new() -> Bus {
+        Bus { devices: BTreeMap::new() }
+    }
+
+    fn first_before(&self, addr: u64) -> Option<(BusRange, &Mutex<BusDevice>)> {
+        // for when we switch to rustc 1.17: self.devices.range(..addr).iter().rev().next()
+        for (range, dev) in self.devices.iter().rev() {
+            if range.0 <= addr {
+                return Some((*range, dev));
+            }
+        }
+        None
+    }
+
+    fn get_device(&self, addr: u64) -> Option<(u64, &Mutex<BusDevice>)> {
+        if let Some((BusRange(start, len), dev)) = self.first_before(addr) {
+            let offset = addr - start;
+            if offset < len {
+                return Some((offset, dev));
+            }
+        }
+        None
+    }
+
+    /// Puts the given device at the given address space.
+    pub fn insert(&mut self, device: Arc<Mutex<BusDevice>>, base: u64, len: u64) -> Result<()> {
+        if len == 0 {
+            return Err(Error::Overlap);
+        }
+
+        // Reject all cases where the new device's base is within an old device's range.
+        if self.get_device(base).is_some() {
+            return Err(Error::Overlap);
+        }
+
+        // The above check will miss an overlap in which the new device's base address is before the
+        // range of another device. To catch that case, we search for a device with a range before
+        // the new device's range's end. If there is no existing device in that range that starts
+        // after the new device, then there will be no overlap.
+        if let Some((BusRange(start, _), _)) = self.first_before(base + len - 1) {
+            // Such a device only conflicts with the new device if it also starts after the new
+            // device because of our initial `get_device` check above.
+            if start >= base {
+                return Err(Error::Overlap);
+            }
+        }
+
+        if self.devices
+               .insert(BusRange(base, len), device)
+               .is_some() {
+            return Err(Error::Overlap);
+        }
+
+        Ok(())
+    }
+
+    /// Reads data from the device that owns the range containing `addr` and puts it into `data`.
+    ///
+    /// Returns true on success, otherwise `data` is untouched.
+    pub fn read(&self, addr: u64, data: &mut [u8]) -> bool {
+        if let Some((offset, dev)) = self.get_device(addr) {
+            dev.lock().unwrap().read(offset, data);
+            true
+        } else {
+            false
+        }
+    }
+
+    /// Writes `data` to the device that owns the range containing `addr`.
+    ///
+    /// Returns true on success, otherwise `data` is untouched.
+    pub fn write(&self, addr: u64, data: &[u8]) -> bool {
+        if let Some((offset, dev)) = self.get_device(addr) {
+            dev.lock().unwrap().write(offset, data);
+            true
+        } else {
+            false
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    struct DummyDevice;
+    impl BusDevice for DummyDevice {}
+
+    struct ConstantDevice;
+    impl BusDevice for ConstantDevice {
+        fn read(&mut self, offset: u64, data: &mut [u8]) {
+            for (i, v) in data.iter_mut().enumerate() {
+                *v = (offset as u8) + (i as u8);
+            }
+        }
+
+        fn write(&mut self, offset: u64, data: &[u8]) {
+            for (i, v) in data.iter().enumerate() {
+                assert_eq!(*v, (offset as u8) + (i as u8))
+            }
+        }
+    }
+
+    #[test]
+    fn bus_insert() {
+        let mut bus = Bus::new();
+        let dummy = Arc::new(Mutex::new(DummyDevice));
+        assert!(bus.insert(dummy.clone(), 0x10, 0).is_err());
+        assert!(bus.insert(dummy.clone(), 0x10, 0x10).is_ok());
+        assert!(bus.insert(dummy.clone(), 0x0f, 0x10).is_err());
+        assert!(bus.insert(dummy.clone(), 0x10, 0x10).is_err());
+        assert!(bus.insert(dummy.clone(), 0x10, 0x15).is_err());
+        assert!(bus.insert(dummy.clone(), 0x12, 0x15).is_err());
+        assert!(bus.insert(dummy.clone(), 0x12, 0x01).is_err());
+        assert!(bus.insert(dummy.clone(), 0x0, 0x20).is_err());
+        assert!(bus.insert(dummy.clone(), 0x20, 0x05).is_ok());
+        assert!(bus.insert(dummy.clone(), 0x25, 0x05).is_ok());
+        assert!(bus.insert(dummy.clone(), 0x0, 0x10).is_ok());
+    }
+
+    #[test]
+    fn bus_read_write() {
+        let mut bus = Bus::new();
+        let dummy = Arc::new(Mutex::new(DummyDevice));
+        assert!(bus.insert(dummy.clone(), 0x10, 0x10).is_ok());
+        assert!(bus.read(0x10, &mut [0, 0, 0, 0]));
+        assert!(bus.write(0x10, &[0, 0, 0, 0]));
+        assert!(bus.read(0x11, &mut [0, 0, 0, 0]));
+        assert!(bus.write(0x11, &[0, 0, 0, 0]));
+        assert!(bus.read(0x16, &mut [0, 0, 0, 0]));
+        assert!(bus.write(0x16, &[0, 0, 0, 0]));
+        assert!(!bus.read(0x20, &mut [0, 0, 0, 0]));
+        assert!(!bus.write(0x20, &mut [0, 0, 0, 0]));
+        assert!(!bus.read(0x06, &mut [0, 0, 0, 0]));
+        assert!(!bus.write(0x06, &mut [0, 0, 0, 0]));
+    }
+
+    #[test]
+    fn bus_read_write_values() {
+        let mut bus = Bus::new();
+        let dummy = Arc::new(Mutex::new(ConstantDevice));
+        assert!(bus.insert(dummy.clone(), 0x10, 0x10).is_ok());
+
+        let mut values = [0, 1, 2, 3];
+        assert!(bus.read(0x10, &mut values));
+        assert_eq!(values, [0, 1, 2, 3]);
+        assert!(bus.write(0x10, &values));
+        assert!(bus.read(0x15, &mut values));
+        assert_eq!(values, [5, 6, 7, 8]);
+        assert!(bus.write(0x15, &values));
+    }
+}