vm_allocator/
lib.rs

1// Copyright 2020 Amazon.com, Inc. or its affiliates. All Rights Reserved.
2// SPDX-License-Identifier: Apache-2.0 OR BSD-3-Clause
3
4//! Manages system resources that can be allocated to VMs and their devices.
5//!
6//! # Example
7//!
8//! Depending on the use case of the VMM, both the `IDAllocator` and the `AddressAllocator`
9//! can be used. In the example below we assume that the `IDAllocator` is used for allocating
10//! unique identifiers for VM devices. We use the address allocator for allocating MMIO ranges
11//! for virtio devices.
12//!
13//! In the example below we use constants that are typical for the x86 platform, but this has no
14//! impact on the code actually working on aarch64.
15//!
16//! ```rust
17//! use std::collections::HashMap;
18//! use std::process::id;
19//! use vm_allocator::{AddressAllocator, AllocPolicy, Error, IdAllocator, RangeInclusive, Result};
20//!
21//! const FIRST_ADDR_PAST_32BITS: u64 = 1 << 32;
22//! const MEM_32BIT_GAP_SIZE: u64 = 768 << 20;
23//! const MMIO_MEM_START: u64 = FIRST_ADDR_PAST_32BITS - MEM_32BIT_GAP_SIZE;
24//! const PAGE_SIZE: u64 = 0x1000;
25//!
26//! struct DeviceManager {
27//!     id_allocator: IdAllocator,
28//!     mmio_allocator: AddressAllocator,
29//!     slots: HashMap<u32, RangeInclusive>,
30//! }
31//!
32//! #[derive(Clone, Copy)]
33//! struct DeviceSlot {
34//!     id: u32,
35//!     mmio_range: RangeInclusive,
36//! }
37//!
38//! impl DeviceManager {
39//!     pub fn new() -> Result<Self> {
40//!         Ok(DeviceManager {
41//!             id_allocator: IdAllocator::new(0, 100)?,
42//!             mmio_allocator: AddressAllocator::new(MMIO_MEM_START, MEM_32BIT_GAP_SIZE)?,
43//!             slots: HashMap::new(),
44//!         })
45//!     }
46//!
47//!     pub fn reserve_device_slot(&mut self) -> Result<DeviceSlot> {
48//!         // We're reserving the first available address that is aligned to the page size.
49//!         // For each device we reserve one page of addresses.
50//!         let mmio_range =
51//!             self.mmio_allocator
52//!                 .allocate(PAGE_SIZE, PAGE_SIZE, AllocPolicy::FirstMatch)?;
53//!         let slot = DeviceSlot {
54//!             id: self.id_allocator.allocate_id()?,
55//!             mmio_range,
56//!         };
57//!         self.slots.insert(slot.id, slot.mmio_range);
58//!         Ok(slot)
59//!     }
60//!
61//!     // Free the device slot corresponding to the passed device ID.
62//!     pub fn free_device_slot(&mut self, id: u32) -> Result<()> {
63//!         let mmio_range = self.slots.get(&id).ok_or(Error::NeverAllocated(id))?;
64//!         let _ = self.id_allocator.free_id(id)?;
65//!         self.mmio_allocator.free(mmio_range)
66//!     }
67//! }
68//!
69//! # fn main() {
70//! #     let mut dm = DeviceManager::new().unwrap();
71//! #    let slot = dm.reserve_device_slot().unwrap();
72//! #    dm.free_device_slot(slot.id).unwrap();
73//! # }
74//! ```
75
76#![deny(missing_docs)]
77
78mod address_allocator;
79/// Allocation engine used by address allocator.
80mod allocation_engine;
81mod id_allocator;
82
83use std::{cmp::max, cmp::min, result};
84use thiserror::Error;
85
86use crate::allocation_engine::NodeState;
87pub use crate::{address_allocator::AddressAllocator, id_allocator::IdAllocator};
88
89/// Default alignment that can be used for creating a `Constraint`.
90pub const DEFAULT_CONSTRAINT_ALIGN: u64 = 4;
91
92/// Error type for IdAllocator usage.
93#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Error)]
94pub enum Error {
95    /// Management operations on desired resource resulted in overflow.
96    #[error("Management operations on desired resource resulted in overflow.")]
97    Overflow,
98    /// An id that is not part of the specified range was requested to be released.
99    #[error("Specified id: {0} is not in the range.")]
100    OutOfRange(u32),
101    /// An id that was already released was requested to be released.
102    #[error("Specified id: {0} is already released.")]
103    AlreadyReleased(u32),
104    /// An id  that was never allocated was requested to be released.
105    #[error("Specified id: {0} was never allocated, can't release it.")]
106    NeverAllocated(u32),
107    /// The resource we want to use or update is not available.
108    #[error("The requested resource is not available.")]
109    ResourceNotAvailable,
110    /// The range to manage is invalid.
111    #[error("The range specified: {0}-{1} is not valid.")]
112    InvalidRange(u64, u64),
113    /// Alignment value is invalid
114    #[error("Alignment value is invalid.")]
115    InvalidAlignment,
116    /// The range that we try to insert into the interval tree is overlapping
117    /// with another node from the tree.
118    #[error("Addresses are overlapping.{0:?} intersects with existing {1:?}")]
119    Overlap(RangeInclusive, RangeInclusive),
120    /// A node state can be changed just from Free to Allocated, other transitions
121    /// are not valid.
122    #[error("Invalid state transition for node {0:?} from {1:?} to NodeState::Free")]
123    InvalidStateTransition(RangeInclusive, NodeState),
124    /// Address is unaligned
125    #[error("The address is not aligned.")]
126    UnalignedAddress,
127    /// Management operations on desired resource resulted in underflow.
128    #[error("Management operations on desired resource resulted in underflow.")]
129    Underflow,
130    /// The size of the desired resource is not invalid.
131    #[error("The specified size: {0} is not valid.")]
132    InvalidSize(u64),
133}
134
135/// Wrapper over std::result::Result
136pub type Result<T> = result::Result<T, Error>;
137
138/// A closed interval range [start, end].
139/// The range describes a memory slot which is assigned by the VMM to a device.
140///
141/// # Example
142///
143/// ```rust
144/// use vm_allocator::RangeInclusive;
145///
146/// let r = RangeInclusive::new(0x0, 0x100).unwrap();
147/// assert_eq!(r.len(), 0x101);
148/// assert_eq!(r.start(), 0x0);
149/// assert_eq!(r.end(), 0x100);
150///
151/// // Check if a region contains another region.
152/// let other = RangeInclusive::new(0x50, 0x80).unwrap();
153/// assert!(r.contains(&other));
154///
155/// // Check if a region overlaps with another one.
156/// let other = RangeInclusive::new(0x99, 0x150).unwrap();
157/// assert!(r.overlaps(&other));
158/// ```
159// This structure represents the key of the Node object in the interval tree implementation.
160#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Hash, Ord, Debug)]
161pub struct RangeInclusive {
162    /// Lower boundary of the interval.
163    start: u64,
164    /// Upper boundary of the interval.
165    end: u64,
166}
167
168#[allow(clippy::len_without_is_empty)]
169impl RangeInclusive {
170    /// Creates a new RangeInclusive.
171    pub fn new(start: u64, end: u64) -> Result<Self> {
172        // The length of the interval [0, u64::MAX] is u64::MAX + 1 which does
173        // not fit in a u64::MAX, hence we return `Error::InvalidRange` when
174        // there is an attempt to use that range.
175        if start > end || (start == 0 && end == u64::MAX) {
176            return Err(Error::InvalidRange(start, end));
177        }
178        Ok(RangeInclusive { start, end })
179    }
180
181    /// Returns the length of the range.
182    pub fn len(&self) -> u64 {
183        self.end - self.start + 1
184    }
185
186    /// Returns true if the regions overlap.
187    pub fn overlaps(&self, other: &RangeInclusive) -> bool {
188        max(self.start, other.start) <= min(self.end, other.end)
189    }
190
191    /// Returns true if the current range contains the range passed as a parameter.
192    pub fn contains(&self, other: &RangeInclusive) -> bool {
193        self.start <= other.start && self.end >= other.end
194    }
195
196    /// Returns the lower boundary of the range.
197    pub fn start(&self) -> u64 {
198        self.start
199    }
200
201    /// Returns the upper boundary of the range.
202    pub fn end(&self) -> u64 {
203        self.end
204    }
205}
206
207/// A resource allocation constraint.
208///
209/// # Example
210///
211/// ```rust
212/// use vm_allocator::{AllocPolicy, Constraint, Error, IdAllocator, DEFAULT_CONSTRAINT_ALIGN};
213///
214/// let constraint =
215///     Constraint::new(0x4, DEFAULT_CONSTRAINT_ALIGN, AllocPolicy::FirstMatch).unwrap();
216/// assert_eq!(constraint.size(), 0x4);
217/// assert_eq!(constraint.align(), 0x4);
218///
219/// // Alignments need to be a power of 2, otherwise an error is returned.
220/// assert_eq!(
221///     Constraint::new(0x4, 0x3, AllocPolicy::LastMatch).unwrap_err(),
222///     Error::InvalidAlignment
223/// );
224///
225/// // When using the ExactMatch policy, the start address must also be aligned, otherwise
226/// // an error is returned.
227/// assert_eq!(
228///     Constraint::new(0x4, 0x4, AllocPolicy::ExactMatch(0x3)).unwrap_err(),
229///     Error::UnalignedAddress
230/// );
231/// ```
232#[derive(Copy, Clone, Debug, Eq, PartialEq)]
233pub struct Constraint {
234    /// Size to allocate.
235    size: u64,
236    /// Alignment for the allocated resource.
237    align: u64,
238    /// Resource allocation policy.
239    policy: AllocPolicy,
240}
241
242impl Constraint {
243    /// Creates a new constraint based on the passed configuration.
244    ///
245    /// When the `ExactMatch` policy is used, the start address MUST be aligned to the
246    /// alignment passed as a parameter.
247    ///
248    /// # Arguments:
249    /// - `size`: size to allocate.
250    /// - `align`: alignment to be used for the allocated resources.
251    ///            Valid alignments are a power of 2.
252    /// - `policy`: allocation policy.
253    pub fn new(size: u64, align: u64, policy: AllocPolicy) -> Result<Self> {
254        if size == 0 {
255            return Err(Error::InvalidSize(size));
256        }
257
258        if !align.is_power_of_two() || align == 0 {
259            return Err(Error::InvalidAlignment);
260        }
261
262        if let AllocPolicy::ExactMatch(start_address) = policy {
263            if start_address % align != 0 {
264                return Err(Error::UnalignedAddress);
265            }
266        }
267
268        Ok(Constraint {
269            size,
270            align,
271            policy,
272        })
273    }
274
275    /// Returns the alignment constraint.
276    pub fn align(self) -> u64 {
277        self.align
278    }
279
280    /// Returns the size constraint.
281    pub fn size(self) -> u64 {
282        self.size
283    }
284}
285
286/// Policy for resource allocation.
287#[derive(Copy, Clone, Debug, Eq, PartialEq, Default)]
288pub enum AllocPolicy {
289    /// Allocate the first matched entry.
290    #[default]
291    FirstMatch,
292    /// Allocate first matched entry from the end of the range.
293    LastMatch,
294    /// Allocate a memory slot starting with the specified address
295    /// if it is available.
296    ExactMatch(u64),
297}
298
299#[cfg(test)]
300mod tests {
301    use super::*;
302
303    #[test]
304    fn test_new_range() {
305        assert_eq!(
306            RangeInclusive::new(2, 1).unwrap_err(),
307            Error::InvalidRange(2, 1)
308        );
309        assert_eq!(
310            RangeInclusive::new(0, u64::MAX).unwrap_err(),
311            Error::InvalidRange(0, u64::MAX)
312        );
313    }
314
315    #[test]
316    fn test_range_overlaps() {
317        let range_a = RangeInclusive::new(1u64, 4u64).unwrap();
318        let range_b = RangeInclusive::new(4u64, 6u64).unwrap();
319        let range_c = RangeInclusive::new(2u64, 3u64).unwrap();
320        let range_e = RangeInclusive::new(5u64, 6u64).unwrap();
321
322        assert!(range_a.overlaps(&range_b));
323        assert!(range_b.overlaps(&range_a));
324        assert!(range_a.overlaps(&range_c));
325        assert!(range_c.overlaps(&range_a));
326        assert!(!range_a.overlaps(&range_e));
327        assert!(!range_e.overlaps(&range_a));
328
329        assert_eq!(range_a.len(), 4);
330    }
331
332    #[test]
333    fn test_range_contain() {
334        let range_a = RangeInclusive::new(2u64, 6u64).unwrap();
335        assert!(range_a.contains(&RangeInclusive::new(2u64, 3u64).unwrap()));
336        assert!(range_a.contains(&RangeInclusive::new(3u64, 4u64).unwrap()));
337        assert!(range_a.contains(&RangeInclusive::new(5u64, 6u64).unwrap()));
338        assert!(!range_a.contains(&RangeInclusive::new(1u64, 2u64).unwrap()));
339        assert!(!range_a.contains(&RangeInclusive::new(1u64, 3u64).unwrap()));
340        assert!(!range_a.contains(&RangeInclusive::new(1u64, 7u64).unwrap()));
341        assert!(!range_a.contains(&RangeInclusive::new(7u64, 8u64).unwrap()));
342        assert!(!range_a.contains(&RangeInclusive::new(6u64, 7u64).unwrap()));
343        assert!(!range_a.contains(&RangeInclusive::new(7u64, 8u64).unwrap()));
344    }
345
346    #[test]
347    fn test_range_ord() {
348        let range_a = RangeInclusive::new(1, 4).unwrap();
349        let range_b = RangeInclusive::new(1, 4).unwrap();
350        let range_c = RangeInclusive::new(1, 3).unwrap();
351        let range_d = RangeInclusive::new(1, 5).unwrap();
352
353        assert_eq!(range_a, range_b);
354        assert_eq!(range_b, range_a);
355        assert!(range_a > range_c);
356        assert!(range_c < range_a);
357        assert!(range_a < range_d);
358        assert!(range_d > range_a);
359    }
360
361    #[test]
362    fn test_getters() {
363        let range = RangeInclusive::new(3, 5).unwrap();
364        assert_eq!(range.start(), 3);
365        assert_eq!(range.end(), 5);
366    }
367
368    #[test]
369    fn test_range_upper_bound() {
370        let range = RangeInclusive::new(0, u64::MAX);
371        assert_eq!(range.unwrap_err(), Error::InvalidRange(0, u64::MAX));
372    }
373
374    #[test]
375    fn constraint_getter() {
376        let bad_constraint = Constraint::new(0x1000, 0x1000, AllocPolicy::ExactMatch(0xC));
377        assert_eq!(bad_constraint.unwrap_err(), Error::UnalignedAddress);
378        let constraint = Constraint::new(0x1000, 0x1000, AllocPolicy::default()).unwrap();
379        assert_eq!(constraint.align(), 0x1000);
380        assert_eq!(constraint.size(), 0x1000);
381    }
382}
vm_allocator/lib.rs

vm_allocator/
lib.rs
