From dea77cef92ffb64551451b133bd3d1f0f50e001e Mon Sep 17 00:00:00 2001 From: Dylan Reid Date: Wed, 23 May 2018 12:59:11 -0700 Subject: 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 Reviewed-on: https://chromium-review.googlesource.com/1072570 Reviewed-by: Sonny Rao --- resources/Cargo.toml | 7 +++ resources/src/address_allocator.rs | 111 +++++++++++++++++++++++++++++++++++++ resources/src/lib.rs | 9 +++ 3 files changed, 127 insertions(+) create mode 100644 resources/Cargo.toml create mode 100644 resources/src/address_allocator.rs create mode 100644 resources/src/lib.rs (limited to 'resources') 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) -> Option { + 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 { + 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; -- cgit 1.4.1