dbs_allocator/
lib.rs

1// Copyright (C) 2019, 2022 Alibaba Cloud. All rights reserved.
2// SPDX-License-Identifier: Apache-2.0
3
4//! Data structures and algorithms to support resource allocation and management.
5//!
6//! The `dbs-allocator` crate provides data structures and algorithms to manage and allocate
7//! integer identifiable resources. The resource manager in virtual machine monitor (VMM) may
8//! manage and allocate resources for virtual machines by using:
9//! - [Constraint]: Struct to declare constraints for resource allocation.
10//! - [IntervalTree]: An interval tree implementation specialized for VMM resource management.
11
12#![deny(missing_docs)]
13
14pub mod interval_tree;
15pub use interval_tree::{IntervalTree, NodeState, Range};
16
17/// Error codes for resource allocation operations.
18#[derive(thiserror::Error, Debug, Eq, PartialEq)]
19pub enum Error {
20    /// Invalid boundary for resource allocation.
21    #[error("invalid boundary constraint: min ({0}), max ({1})")]
22    InvalidBoundary(u64, u64),
23}
24
25/// Specialized version of [`std::result::Result`] for resource allocation operations.
26pub type Result<T> = std::result::Result<T, Error>;
27
28/// Resource allocation policies.
29#[derive(Copy, Clone, Debug, Eq, PartialEq)]
30pub enum AllocPolicy {
31    /// Default resource allocation policy.
32    Default,
33    /// Return the first available resource matching the allocation constraints.
34    FirstMatch,
35}
36
37/// Struct to declare resource allocation constraints.
38#[derive(Copy, Clone, Debug)]
39pub struct Constraint {
40    /// Size of resource to allocate.
41    pub size: u64,
42    /// Lower boundary for resource allocation.
43    pub min: u64,
44    /// Upper boundary for resource allocation.
45    pub max: u64,
46    /// Alignment for allocated resource.
47    pub align: u64,
48    /// Policy for resource allocation.
49    pub policy: AllocPolicy,
50}
51
52impl Constraint {
53    /// Create a new instance of [`Constraint`] with default settings.
54    pub fn new<T>(size: T) -> Self
55    where
56        u64: From<T>,
57    {
58        Constraint {
59            size: u64::from(size),
60            min: 0,
61            max: u64::MAX,
62            align: 1,
63            policy: AllocPolicy::Default,
64        }
65    }
66
67    /// Set the lower boundary constraint for resource allocation.
68    pub fn min<T>(mut self, min: T) -> Self
69    where
70        u64: From<T>,
71    {
72        self.min = u64::from(min);
73        self
74    }
75
76    /// Set the upper boundary constraint for resource allocation.
77    pub fn max<T>(mut self, max: T) -> Self
78    where
79        u64: From<T>,
80    {
81        self.max = u64::from(max);
82        self
83    }
84
85    /// Set the alignment constraint for allocated resource.
86    pub fn align<T>(mut self, align: T) -> Self
87    where
88        u64: From<T>,
89    {
90        self.align = u64::from(align);
91        self
92    }
93
94    /// Set the resource allocation policy.
95    pub fn policy(mut self, policy: AllocPolicy) -> Self {
96        self.policy = policy;
97        self
98    }
99
100    /// Validate the resource allocation constraints.
101    pub fn validate(&self) -> Result<()> {
102        if self.max < self.min {
103            return Err(Error::InvalidBoundary(self.min, self.max));
104        }
105        Ok(())
106    }
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112    #[test]
113    fn test_set_min() {
114        let constraint = Constraint::new(2_u64).min(1_u64);
115        assert_eq!(constraint.min, 1_u64);
116    }
117
118    #[test]
119    fn test_set_max() {
120        let constraint = Constraint::new(2_u64).max(100_u64);
121        assert_eq!(constraint.max, 100_u64);
122    }
123
124    #[test]
125    fn test_set_align() {
126        let constraint = Constraint::new(2_u64).align(8_u64);
127        assert_eq!(constraint.align, 8_u64);
128    }
129
130    #[test]
131    fn test_set_policy() {
132        let mut constraint = Constraint::new(2_u64).policy(AllocPolicy::FirstMatch);
133        assert_eq!(constraint.policy, AllocPolicy::FirstMatch);
134        constraint = constraint.policy(AllocPolicy::Default);
135        assert_eq!(constraint.policy, AllocPolicy::Default);
136    }
137
138    #[test]
139    fn test_consistently_change_constraint() {
140        let constraint = Constraint::new(2_u64)
141            .min(1_u64)
142            .max(100_u64)
143            .align(8_u64)
144            .policy(AllocPolicy::FirstMatch);
145        assert_eq!(constraint.min, 1_u64);
146        assert_eq!(constraint.max, 100_u64);
147        assert_eq!(constraint.align, 8_u64);
148        assert_eq!(constraint.policy, AllocPolicy::FirstMatch);
149    }
150
151    #[test]
152    fn test_set_invalid_boundary() {
153        // Normal case.
154        let constraint = Constraint::new(2_u64).max(1000_u64).min(999_u64);
155        assert!(constraint.validate().is_ok());
156
157        // Error case.
158        let constraint = Constraint::new(2_u64).max(999_u64).min(1000_u64);
159        assert_eq!(
160            constraint.validate(),
161            Err(Error::InvalidBoundary(1000u64, 999u64))
162        );
163    }
164}
dbs_allocator/lib.rs

dbs_allocator/
lib.rs
