#![deny(missing_docs)]
mod address_allocator;
mod allocation_engine;
mod id_allocator;
use std::{cmp::max, cmp::min, result};
use thiserror::Error;
use crate::allocation_engine::NodeState;
pub use crate::{address_allocator::AddressAllocator, id_allocator::IdAllocator};
pub const DEFAULT_CONSTRAINT_ALIGN: u64 = 4;
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Error)]
pub enum Error {
#[error("Management operations on desired resource resulted in overflow.")]
Overflow,
#[error("Specified id: {0} is not in the range.")]
OutOfRange(u32),
#[error("Specified id: {0} is already released.")]
AlreadyReleased(u32),
#[error("Specified id: {0} was never allocated, can't release it.")]
NeverAllocated(u32),
#[error("The requested resource is not available.")]
ResourceNotAvailable,
#[error("The range specified: {0}-{1} is not valid.")]
InvalidRange(u64, u64),
#[error("Alignment value is invalid.")]
InvalidAlignment,
#[error("Addresses are overlapping.{0:?} intersects with existing {1:?}")]
Overlap(RangeInclusive, RangeInclusive),
#[error("Invalid state transition for node {0:?} from {1:?} to NodeState::Free")]
InvalidStateTransition(RangeInclusive, NodeState),
#[error("The address is not aligned.")]
UnalignedAddress,
#[error("Management operations on desired resource resulted in underflow.")]
Underflow,
#[error("The specified size: {0} is not valid.")]
InvalidSize(u64),
}
pub type Result<T> = result::Result<T, Error>;
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Hash, Ord, Debug)]
pub struct RangeInclusive {
start: u64,
end: u64,
}
#[allow(clippy::len_without_is_empty)]
impl RangeInclusive {
pub fn new(start: u64, end: u64) -> Result<Self> {
if start >= end || (start == 0 && end == u64::MAX) {
return Err(Error::InvalidRange(start, end));
}
Ok(RangeInclusive { start, end })
}
pub fn len(&self) -> u64 {
self.end - self.start + 1
}
pub fn overlaps(&self, other: &RangeInclusive) -> bool {
max(self.start, other.start) <= min(self.end, other.end)
}
pub fn contains(&self, other: &RangeInclusive) -> bool {
self.start <= other.start && self.end >= other.end
}
pub fn start(&self) -> u64 {
self.start
}
pub fn end(&self) -> u64 {
self.end
}
}
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct Constraint {
size: u64,
align: u64,
policy: AllocPolicy,
}
impl Constraint {
pub fn new(size: u64, align: u64, policy: AllocPolicy) -> Result<Self> {
if size == 0 {
return Err(Error::InvalidSize(size));
}
if !align.is_power_of_two() || align == 0 {
return Err(Error::InvalidAlignment);
}
if let AllocPolicy::ExactMatch(start_address) = policy {
if start_address % align != 0 {
return Err(Error::UnalignedAddress);
}
}
Ok(Constraint {
size,
align,
policy,
})
}
pub fn align(self) -> u64 {
self.align
}
pub fn size(self) -> u64 {
self.size
}
}
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum AllocPolicy {
FirstMatch,
LastMatch,
ExactMatch(u64),
}
impl Default for AllocPolicy {
fn default() -> Self {
AllocPolicy::FirstMatch
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_new_range() {
assert_eq!(
RangeInclusive::new(2, 1).unwrap_err(),
Error::InvalidRange(2, 1)
);
assert_eq!(
RangeInclusive::new(1, 1).unwrap_err(),
Error::InvalidRange(1, 1)
);
}
#[test]
fn test_range_overlaps() {
let range_a = RangeInclusive::new(1u64, 4u64).unwrap();
let range_b = RangeInclusive::new(4u64, 6u64).unwrap();
let range_c = RangeInclusive::new(2u64, 3u64).unwrap();
let range_e = RangeInclusive::new(5u64, 6u64).unwrap();
assert!(range_a.overlaps(&range_b));
assert!(range_b.overlaps(&range_a));
assert!(range_a.overlaps(&range_c));
assert!(range_c.overlaps(&range_a));
assert!(!range_a.overlaps(&range_e));
assert!(!range_e.overlaps(&range_a));
assert_eq!(range_a.len(), 4);
}
#[test]
fn test_range_contain() {
let range_a = RangeInclusive::new(2u64, 6u64).unwrap();
assert!(range_a.contains(&RangeInclusive::new(2u64, 3u64).unwrap()));
assert!(range_a.contains(&RangeInclusive::new(3u64, 4u64).unwrap()));
assert!(range_a.contains(&RangeInclusive::new(5u64, 6u64).unwrap()));
assert!(!range_a.contains(&RangeInclusive::new(1u64, 2u64).unwrap()));
assert!(!range_a.contains(&RangeInclusive::new(1u64, 3u64).unwrap()));
assert!(!range_a.contains(&RangeInclusive::new(1u64, 7u64).unwrap()));
assert!(!range_a.contains(&RangeInclusive::new(7u64, 8u64).unwrap()));
assert!(!range_a.contains(&RangeInclusive::new(6u64, 7u64).unwrap()));
assert!(!range_a.contains(&RangeInclusive::new(7u64, 8u64).unwrap()));
}
#[test]
fn test_range_ord() {
let range_a = RangeInclusive::new(1, 4).unwrap();
let range_b = RangeInclusive::new(1, 4).unwrap();
let range_c = RangeInclusive::new(1, 3).unwrap();
let range_d = RangeInclusive::new(1, 5).unwrap();
assert_eq!(range_a, range_b);
assert_eq!(range_b, range_a);
assert!(range_a > range_c);
assert!(range_c < range_a);
assert!(range_a < range_d);
assert!(range_d > range_a);
}
#[test]
fn test_getters() {
let range = RangeInclusive::new(3, 5).unwrap();
assert_eq!(range.start(), 3);
assert_eq!(range.end(), 5);
}
#[test]
fn test_range_upper_bound() {
let range = RangeInclusive::new(0, u64::MAX);
assert_eq!(range.unwrap_err(), Error::InvalidRange(0, u64::MAX));
}
#[test]
fn constraint_getter() {
let bad_constraint = Constraint::new(0x1000, 0x1000, AllocPolicy::ExactMatch(0xC));
assert_eq!(bad_constraint.unwrap_err(), Error::UnalignedAddress);
let constraint = Constraint::new(0x1000, 0x1000, AllocPolicy::default()).unwrap();
assert_eq!(constraint.align(), 0x1000);
assert_eq!(constraint.size(), 0x1000);
}
}