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#![cfg_attr(not(feature = "std"), no_std)]
78
79extern crate alloc;
80
81#[cfg(not(feature = "std"))]
82extern crate core as std;
83
84mod address_allocator;
85/// Allocation engine used by address allocator.
86mod allocation_engine;
87mod id_allocator;
88
89use std::{cmp::max, cmp::min, result};
90use thiserror::Error;
91
92use crate::allocation_engine::NodeState;
93pub use crate::{address_allocator::AddressAllocator, id_allocator::IdAllocator};
94
95/// Default alignment that can be used for creating a `Constraint`.
96pub const DEFAULT_CONSTRAINT_ALIGN: u64 = 4;
97
98/// Error type for IdAllocator usage.
99#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Error)]
100pub enum Error {
101    /// Management operations on desired resource resulted in overflow.
102    #[error("Management operations on desired resource resulted in overflow.")]
103    Overflow,
104    /// An id that is not part of the specified range was requested to be released.
105    #[error("Specified id: {0} is not in the range.")]
106    OutOfRange(u32),
107    /// An id that was already released was requested to be released.
108    #[error("Specified id: {0} is already released.")]
109    AlreadyReleased(u32),
110    /// An id  that was never allocated was requested to be released.
111    #[error("Specified id: {0} was never allocated, can't release it.")]
112    NeverAllocated(u32),
113    /// The resource we want to use or update is not available.
114    #[error("The requested resource is not available.")]
115    ResourceNotAvailable,
116    /// The range to manage is invalid.
117    #[error("The range specified: {0}-{1} is not valid.")]
118    InvalidRange(u64, u64),
119    /// Alignment value is invalid
120    #[error("Alignment value is invalid.")]
121    InvalidAlignment,
122    /// The range that we try to insert into the interval tree is overlapping
123    /// with another node from the tree.
124    #[error("Addresses are overlapping.{0:?} intersects with existing {1:?}")]
125    Overlap(RangeInclusive, RangeInclusive),
126    /// A node state can be changed just from Free to Allocated, other transitions
127    /// are not valid.
128    #[error("Invalid state transition for node {0:?} from {1:?} to NodeState::Free")]
129    InvalidStateTransition(RangeInclusive, NodeState),
130    /// Address is unaligned
131    #[error("The address is not aligned.")]
132    UnalignedAddress,
133    /// Management operations on desired resource resulted in underflow.
134    #[error("Management operations on desired resource resulted in underflow.")]
135    Underflow,
136    /// The size of the desired resource is not invalid.
137    #[error("The specified size: {0} is not valid.")]
138    InvalidSize(u64),
139}
140
141/// Wrapper over std::result::Result
142pub type Result<T> = result::Result<T, Error>;
143
144/// A closed interval range [start, end].
145/// The range describes a memory slot which is assigned by the VMM to a device.
146///
147/// # Example
148///
149/// ```rust
150/// use vm_allocator::RangeInclusive;
151///
152/// let r = RangeInclusive::new(0x0, 0x100).unwrap();
153/// assert_eq!(r.len(), 0x101);
154/// assert_eq!(r.start(), 0x0);
155/// assert_eq!(r.end(), 0x100);
156///
157/// // Check if a region contains another region.
158/// let other = RangeInclusive::new(0x50, 0x80).unwrap();
159/// assert!(r.contains(&other));
160///
161/// // Check if a region overlaps with another one.
162/// let other = RangeInclusive::new(0x99, 0x150).unwrap();
163/// assert!(r.overlaps(&other));
164/// ```
165// This structure represents the key of the Node object in the interval tree implementation.
166#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Hash, Ord, Debug)]
167#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
168pub struct RangeInclusive {
169    /// Lower boundary of the interval.
170    start: u64,
171    /// Upper boundary of the interval.
172    end: u64,
173}
174
175#[allow(clippy::len_without_is_empty)]
176impl RangeInclusive {
177    /// Creates a new RangeInclusive.
178    pub fn new(start: u64, end: u64) -> Result<Self> {
179        // The length of the interval [0, u64::MAX] is u64::MAX + 1 which does
180        // not fit in a u64::MAX, hence we return `Error::InvalidRange` when
181        // there is an attempt to use that range.
182        if start > end || (start == 0 && end == u64::MAX) {
183            return Err(Error::InvalidRange(start, end));
184        }
185        Ok(RangeInclusive { start, end })
186    }
187
188    /// Returns the length of the range.
189    pub fn len(&self) -> u64 {
190        self.end - self.start + 1
191    }
192
193    /// Returns true if the regions overlap.
194    pub fn overlaps(&self, other: &RangeInclusive) -> bool {
195        max(self.start, other.start) <= min(self.end, other.end)
196    }
197
198    /// Returns true if the current range contains the range passed as a parameter.
199    pub fn contains(&self, other: &RangeInclusive) -> bool {
200        self.start <= other.start && self.end >= other.end
201    }
202
203    /// Returns the lower boundary of the range.
204    pub fn start(&self) -> u64 {
205        self.start
206    }
207
208    /// Returns the upper boundary of the range.
209    pub fn end(&self) -> u64 {
210        self.end
211    }
212}
213
214/// A resource allocation constraint.
215///
216/// # Example
217///
218/// ```rust
219/// use vm_allocator::{AllocPolicy, Constraint, Error, IdAllocator, DEFAULT_CONSTRAINT_ALIGN};
220///
221/// let constraint =
222///     Constraint::new(0x4, DEFAULT_CONSTRAINT_ALIGN, AllocPolicy::FirstMatch).unwrap();
223/// assert_eq!(constraint.size(), 0x4);
224/// assert_eq!(constraint.align(), 0x4);
225///
226/// // Alignments need to be a power of 2, otherwise an error is returned.
227/// assert_eq!(
228///     Constraint::new(0x4, 0x3, AllocPolicy::LastMatch).unwrap_err(),
229///     Error::InvalidAlignment
230/// );
231///
232/// // When using the ExactMatch policy, the start address must also be aligned, otherwise
233/// // an error is returned.
234/// assert_eq!(
235///     Constraint::new(0x4, 0x4, AllocPolicy::ExactMatch(0x3)).unwrap_err(),
236///     Error::UnalignedAddress
237/// );
238/// ```
239#[derive(Copy, Clone, Debug, Eq, PartialEq)]
240pub struct Constraint {
241    /// Size to allocate.
242    size: u64,
243    /// Alignment for the allocated resource.
244    align: u64,
245    /// Resource allocation policy.
246    policy: AllocPolicy,
247}
248
249impl Constraint {
250    /// Creates a new constraint based on the passed configuration.
251    ///
252    /// When the `ExactMatch` policy is used, the start address MUST be aligned to the
253    /// alignment passed as a parameter.
254    ///
255    /// # Arguments:
256    /// - `size`: size to allocate.
257    /// - `align`: alignment to be used for the allocated resources.
258    ///   Valid alignments are a power of 2.
259    /// - `policy`: allocation policy.
260    pub fn new(size: u64, align: u64, policy: AllocPolicy) -> Result<Self> {
261        if size == 0 {
262            return Err(Error::InvalidSize(size));
263        }
264
265        if !align.is_power_of_two() || align == 0 {
266            return Err(Error::InvalidAlignment);
267        }
268
269        if let AllocPolicy::ExactMatch(start_address) = policy {
270            if start_address % align != 0 {
271                return Err(Error::UnalignedAddress);
272            }
273        }
274
275        Ok(Constraint {
276            size,
277            align,
278            policy,
279        })
280    }
281
282    /// Returns the alignment constraint.
283    pub fn align(self) -> u64 {
284        self.align
285    }
286
287    /// Returns the size constraint.
288    pub fn size(self) -> u64 {
289        self.size
290    }
291}
292
293/// Policy for resource allocation.
294#[derive(Copy, Clone, Debug, Eq, PartialEq, Default)]
295pub enum AllocPolicy {
296    /// Allocate the first matched entry.
297    #[default]
298    FirstMatch,
299    /// Allocate first matched entry from the end of the range.
300    LastMatch,
301    /// Allocate a memory slot starting with the specified address
302    /// if it is available.
303    ExactMatch(u64),
304}
305
306#[cfg(test)]
307mod tests {
308    use super::*;
309
310    #[test]
311    fn test_new_range() {
312        assert_eq!(
313            RangeInclusive::new(2, 1).unwrap_err(),
314            Error::InvalidRange(2, 1)
315        );
316        assert_eq!(
317            RangeInclusive::new(0, u64::MAX).unwrap_err(),
318            Error::InvalidRange(0, u64::MAX)
319        );
320    }
321
322    #[test]
323    fn test_range_overlaps() {
324        let range_a = RangeInclusive::new(1u64, 4u64).unwrap();
325        let range_b = RangeInclusive::new(4u64, 6u64).unwrap();
326        let range_c = RangeInclusive::new(2u64, 3u64).unwrap();
327        let range_e = RangeInclusive::new(5u64, 6u64).unwrap();
328
329        assert!(range_a.overlaps(&range_b));
330        assert!(range_b.overlaps(&range_a));
331        assert!(range_a.overlaps(&range_c));
332        assert!(range_c.overlaps(&range_a));
333        assert!(!range_a.overlaps(&range_e));
334        assert!(!range_e.overlaps(&range_a));
335
336        assert_eq!(range_a.len(), 4);
337    }
338
339    #[test]
340    fn test_range_contain() {
341        let range_a = RangeInclusive::new(2u64, 6u64).unwrap();
342        assert!(range_a.contains(&RangeInclusive::new(2u64, 3u64).unwrap()));
343        assert!(range_a.contains(&RangeInclusive::new(3u64, 4u64).unwrap()));
344        assert!(range_a.contains(&RangeInclusive::new(5u64, 6u64).unwrap()));
345        assert!(!range_a.contains(&RangeInclusive::new(1u64, 2u64).unwrap()));
346        assert!(!range_a.contains(&RangeInclusive::new(1u64, 3u64).unwrap()));
347        assert!(!range_a.contains(&RangeInclusive::new(1u64, 7u64).unwrap()));
348        assert!(!range_a.contains(&RangeInclusive::new(7u64, 8u64).unwrap()));
349        assert!(!range_a.contains(&RangeInclusive::new(6u64, 7u64).unwrap()));
350        assert!(!range_a.contains(&RangeInclusive::new(7u64, 8u64).unwrap()));
351    }
352
353    #[test]
354    fn test_range_ord() {
355        let range_a = RangeInclusive::new(1, 4).unwrap();
356        let range_b = RangeInclusive::new(1, 4).unwrap();
357        let range_c = RangeInclusive::new(1, 3).unwrap();
358        let range_d = RangeInclusive::new(1, 5).unwrap();
359
360        assert_eq!(range_a, range_b);
361        assert_eq!(range_b, range_a);
362        assert!(range_a > range_c);
363        assert!(range_c < range_a);
364        assert!(range_a < range_d);
365        assert!(range_d > range_a);
366    }
367
368    #[test]
369    fn test_getters() {
370        let range = RangeInclusive::new(3, 5).unwrap();
371        assert_eq!(range.start(), 3);
372        assert_eq!(range.end(), 5);
373    }
374
375    #[test]
376    fn test_range_upper_bound() {
377        let range = RangeInclusive::new(0, u64::MAX);
378        assert_eq!(range.unwrap_err(), Error::InvalidRange(0, u64::MAX));
379    }
380
381    #[test]
382    fn constraint_getter() {
383        let bad_constraint = Constraint::new(0x1000, 0x1000, AllocPolicy::ExactMatch(0xC));
384        assert_eq!(bad_constraint.unwrap_err(), Error::UnalignedAddress);
385        let constraint = Constraint::new(0x1000, 0x1000, AllocPolicy::default()).unwrap();
386        assert_eq!(constraint.align(), 0x1000);
387        assert_eq!(constraint.size(), 0x1000);
388    }
389}
vm_allocator/lib.rs

vm_allocator/
lib.rs
