resources: Add address allocation helper

Add the AddressAllocator module that will be used by both architectures
to manage distributing address ranges to devices. This will make the
addition of PCI devices easier as now both MMIO and PCI will need to
share address space. Add this to a new resources crate.

Change-Id: I6a971dd795f2118bd6cfec7dc34a65b0d4a32f9b
Signed-off-by: Dylan Reid <dgreid@chromium.org>
Reviewed-on: https://chromium-review.googlesource.com/1072570
Reviewed-by: Sonny Rao <sonnyrao@chromium.org>

3 files changed, 127 insertions, 0 deletions

diff --git a/resources/Cargo.toml b/resources/Cargo.toml
new file mode 100644
index 0000000..74f0c35
--- /dev/null
+++ b/resources/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "resources"
+version = "0.1.0"
+authors = ["The Chromium OS Authors"]
+
+[dependencies]
+data_model = { path = "../data_model" }
diff --git a/resources/src/address_allocator.rs b/resources/src/address_allocator.rs
new file mode 100644
index 0000000..6c8513d
--- /dev/null
+++ b/resources/src/address_allocator.rs
@@ -0,0 +1,111 @@
+// Copyright 2018 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.
+
+/// Manages allocating address ranges.
+/// Use `AddressAllocator` whenever an address range needs to be allocated to different users.
+///
+/// # Examples
+///
+/// ```
+/// # use resources::AddressAllocator;
+///   AddressAllocator::new(0x1000, 0x10000, Some(0x100)).map(|mut pool| {
+///       assert_eq!(pool.allocate(0x110), Some(0x1000));
+///       assert_eq!(pool.allocate(0x100), Some(0x1200));
+///   });
+/// ```
+#[derive(Debug, Eq, PartialEq)]
+pub struct AddressAllocator {
+    pool_base: u64,
+    pool_end: u64,
+    alignment: u64,
+    next_addr: u64,
+}
+
+impl AddressAllocator {
+    /// Creates a new `AddressAllocator` for managing a range of addresses.
+    /// Can return `None` if `pool_base` + `pool_size` overflows a u64 or if alignment isn't a power
+    /// of two.
+    ///
+    /// * `pool_base` - The starting address of the range to manage.
+    /// * `pool_size` - The size of the address range in bytes.
+    /// * `align_size` - The minimum size of an address region to align to, defaults to four.
+    pub fn new(pool_base: u64, pool_size: u64, align_size: Option<u64>) -> Option<Self> {
+        if pool_size == 0 {
+            return None;
+        }
+        let pool_end = pool_base.checked_add(pool_size - 1)?;
+        let alignment = align_size.unwrap_or(4);
+        if !alignment.is_power_of_two() || alignment == 0 {
+            return None;
+        }
+        Some(AddressAllocator {
+            pool_base,
+            pool_end,
+            alignment,
+            next_addr: pool_base,
+        })
+    }
+
+    /// Allocates a range of addresses from the managed region. Returns `Some(allocated_address)`
+    /// when successful, or `None` if an area of `size` can't be allocated.
+    pub fn allocate(&mut self, size: u64) -> Option<u64> {
+        if size == 0 {
+            return None;
+        }
+        let align_adjust = if self.next_addr % self.alignment != 0 {
+            self.alignment - (self.next_addr % self.alignment)
+        } else {
+            0
+        };
+        let addr = self.next_addr.checked_add(align_adjust)?;
+        let end_addr = addr.checked_add(size - 1)?;
+        if end_addr > self.pool_end {
+            return None;
+        }
+        // TODO(dgreid): Use a smarter allocation strategy. The current strategy is just
+        // bumping this pointer, meaning it will eventually exhaust available addresses.
+        self.next_addr = end_addr.saturating_add(1);
+        Some(addr)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn new_fails_overflow() {
+        assert_eq!(AddressAllocator::new(u64::max_value(), 0x100, None), None);
+    }
+
+    #[test]
+    fn new_fails_size_zero() {
+        assert_eq!(AddressAllocator::new(0x1000, 0, None), None);
+    }
+
+    #[test]
+    fn new_fails_alignment_zero() {
+        assert_eq!(AddressAllocator::new(0x1000, 0x10000, Some(0)), None);
+    }
+
+    #[test]
+    fn new_fails_alignment_non_power_of_two() {
+        assert_eq!(AddressAllocator::new(0x1000, 0x10000, Some(200)), None);
+    }
+
+    #[test]
+    fn allocate_fails_not_enough_space() {
+        let mut pool = AddressAllocator::new(0x1000, 0x1000, Some(0x100)).unwrap();
+        assert_eq!(pool.allocate(0x800), Some(0x1000));
+        assert_eq!(pool.allocate(0x900), None);
+        assert_eq!(pool.allocate(0x800), Some(0x1800));
+    }
+
+    #[test]
+    fn allocate_alignment() {
+        let mut pool = AddressAllocator::new(0x1000, 0x10000, Some(0x100)).unwrap();
+        assert_eq!(pool.allocate(0x110), Some(0x1000));
+        assert_eq!(pool.allocate(0x100), Some(0x1200));
+    }
+}
diff --git a/resources/src/lib.rs b/resources/src/lib.rs
new file mode 100644
index 0000000..de87db6
--- /dev/null
+++ b/resources/src/lib.rs
@@ -0,0 +1,9 @@
+// Copyright 2018 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.
+
+//! Manages system resources that can be allocated to VMs and their devices.
+
+mod address_allocator;
+
+pub use address_allocator::AddressAllocator;