vm_topology/
layout.rs

1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4//! VM address-space layout allocator.
5//!
6//! This module provides a pure-math layout allocator that places reserved and
7//! fixed ranges, 32-bit MMIO, ordinary RAM, 64-bit MMIO, and post-MMIO ranges in
8//! a flat guest physical address map. It has no knowledge of specific
9//! architectures, firmware types, or chipset conventions; callers express those
10//! policies as reserved/fixed ranges and dynamic requests.
11//!
12//! # Usage
13//!
14//! ```
15//! use memory_range::MemoryRange;
16//! use vm_topology::layout::{LayoutBuilder, Placement};
17//!
18//! let mut ram = Vec::new();
19//! let mut vmbus = MemoryRange::EMPTY;
20//!
21//! let mut builder = LayoutBuilder::new();
22//! builder.fixed(
23//!     "reserved",
24//!     MemoryRange::new(0xFE00_0000..0x1_0000_0000),
25//! );
26//! builder.request(
27//!     "vmbus",
28//!     &mut vmbus,
29//!     128 * 1024 * 1024,
30//!     1024 * 1024,
31//!     Placement::Mmio32,
32//! );
33//! builder.ram("ram", &mut ram, 2 * 1024 * 1024 * 1024, 4096);
34//!
35//! let sorted = builder.allocate().unwrap();
36//! assert_eq!(ram, [MemoryRange::new(0..0x8000_0000)]);
37//! assert_eq!(vmbus.end(), 0xFE00_0000);
38//! assert_eq!(sorted.len(), 3);
39//! ```
40
41use memory_range::MemoryRange;
42use std::sync::Arc;
43use thiserror::Error;
44
45const PAGE_SIZE: u64 = 4096;
46const FOUR_GIB: u64 = 0x1_0000_0000;
47const ADDRESS_LIMIT: u64 = MemoryRange::MAX_ADDRESS;
48
49/// The placement class for a dynamic single-range layout request.
50#[derive(Debug, Clone, Copy, PartialEq, Eq)]
51pub enum Placement {
52    /// The allocation must fit below the 4 GiB boundary and is placed top down.
53    Mmio32,
54    /// The allocation must sit above the 4 GiB boundary and is placed bottom
55    /// up above RAM.
56    Mmio64,
57    /// The allocation is placed bottom up after RAM and all MMIO allocations.
58    ///
59    /// Post-MMIO requests are allocated in caller order, not sorted by size or
60    /// alignment, so they can be used for private implementation ranges that
61    /// must not perturb the guest-visible RAM/MMIO layout.
62    PostMmio,
63}
64
65/// The kind of a produced allocation.
66#[derive(Debug, Clone, Copy, PartialEq, Eq)]
67pub enum PlacedRangeKind {
68    /// A reserved range supplied by the caller.
69    Reserved,
70    /// A fixed allocation supplied by the caller.
71    Fixed,
72    /// A 32-bit MMIO allocation.
73    Mmio32,
74    /// An ordinary RAM allocation.
75    Ram,
76    /// A 64-bit MMIO allocation.
77    Mmio64,
78    /// A post-MMIO allocation.
79    PostMmio,
80}
81
82/// Allocation phase reported in [`AllocateError::Exhausted`].
83#[derive(Debug, Clone, Copy, PartialEq, Eq)]
84pub enum AllocationPhase {
85    /// 32-bit MMIO placement.
86    Mmio32,
87    /// RAM placement.
88    Ram,
89    /// 64-bit MMIO placement.
90    Mmio64,
91    /// Post-MMIO placement.
92    PostMmio,
93}
94
95/// A placed range returned by [`LayoutBuilder::allocate`].
96#[derive(Debug, Clone, PartialEq, Eq)]
97pub struct PlacedRange {
98    /// The caller-supplied tag for the request.
99    pub tag: Arc<str>,
100    /// The kind of allocation.
101    pub kind: PlacedRangeKind,
102    /// The placed range.
103    pub range: MemoryRange,
104}
105
106/// A builder for computing a deterministic VM address-space layout.
107pub struct LayoutBuilder<'a> {
108    reserved: Vec<ReservedRequest>,
109    fixed: Vec<FixedRequest>,
110    mmio32: Vec<DynamicRequest<'a>>,
111    ram: Vec<RamRequest<'a>>,
112    mmio64: Vec<DynamicRequest<'a>>,
113    post_mmio: Vec<DynamicRequest<'a>>,
114}
115
116struct ReservedRequest {
117    tag: Arc<str>,
118    range: MemoryRange,
119}
120
121struct FixedRequest {
122    tag: Arc<str>,
123    range: MemoryRange,
124}
125
126struct DynamicRequest<'a> {
127    tag: Arc<str>,
128    target: &'a mut MemoryRange,
129    size: u64,
130    alignment: u64,
131}
132
133impl DynamicRequest<'_> {
134    /// Sort key for the dynamic placement phases: larger alignment first, then
135    /// larger size first. Wrapping with `Reverse` makes the descending order
136    /// self-evident at the call site.
137    fn placement_sort_key(&self) -> std::cmp::Reverse<(u64, u64)> {
138        std::cmp::Reverse((self.alignment, self.size))
139    }
140}
141
142struct RamRequest<'a> {
143    tag: Arc<str>,
144    target: &'a mut Vec<MemoryRange>,
145    size: u64,
146    alignment: u64,
147}
148
149struct AllocationState {
150    // Sorted, non-overlapping, non-empty ranges not yet consumed by any
151    // request. Keeping free space as the primary state lets each phase update
152    // the map incrementally instead of repeatedly subtracting all allocations
153    // from the whole address space.
154    //
155    // The non-empty invariant lets `remove_free_range` locate the containing
156    // free range with a single `partition_point` lookup.
157    free: Vec<MemoryRange>,
158    allocations: Vec<PlacedRange>,
159    // Highest end address of ordinary RAM. High MMIO starts here so the layout
160    // top is driven by requested topology rather than a caller-provided high
161    // MMIO bucket size or host physical-address width.
162    ram_end: u64,
163}
164
165impl AllocationState {
166    fn new() -> Self {
167        Self {
168            free: vec![MemoryRange::new(0..ADDRESS_LIMIT)],
169            allocations: Vec::new(),
170            ram_end: 0,
171        }
172    }
173
174    fn place_fixed(&mut self, requests: &[FixedRequest]) -> Result<(), AllocateError> {
175        for request in requests {
176            self.allocate_range(&request.tag, PlacedRangeKind::Fixed, request.range);
177        }
178
179        Ok(())
180    }
181
182    fn place_reserved(&mut self, requests: &[ReservedRequest]) {
183        for request in requests {
184            self.allocate_range(&request.tag, PlacedRangeKind::Reserved, request.range);
185        }
186    }
187
188    fn place_mmio32(&mut self, requests: &mut [DynamicRequest<'_>]) -> Result<(), AllocateError> {
189        // Pack 32-bit MMIO from the top of the 4 GiB window downward so RAM can
190        // start at GPA 0 and grow upward through the lowest remaining space.
191        // Alignment/size ordering keeps large, constrained windows from being
192        // fragmented by small devices. `sort_by_key` is stable, so otherwise
193        // equal requests keep caller order.
194        requests.sort_by_key(|r| r.placement_sort_key());
195
196        for request in requests {
197            let Some(start) =
198                find_highest_fit(&self.free, request.size, request.alignment, 0, FOUR_GIB)
199            else {
200                return Err(exhausted_error(
201                    &request.tag,
202                    request.size,
203                    request.alignment,
204                    AllocationPhase::Mmio32,
205                    &self.free,
206                    0,
207                    FOUR_GIB,
208                ));
209            };
210
211            let range = MemoryRange::new(start..start + request.size);
212            *request.target = range;
213            self.allocate_range(&request.tag, PlacedRangeKind::Mmio32, range);
214        }
215
216        Ok(())
217    }
218
219    fn place_ram(&mut self, requests: &mut [RamRequest<'_>]) -> Result<(), AllocateError> {
220        // Ordinary RAM is the only splittable request type in this API. It is
221        // placed after low MMIO so the resulting RAM extents describe the
222        // actual guest-visible memory map, including holes below 4 GiB.
223        //
224        // Requests are placed in caller order, and each request starts at or
225        // above the highest address used by previous RAM requests. A later
226        // RAM request never backfills a fragment that an earlier one skipped:
227        // this keeps the flattened RAM list sorted by address (matching the
228        // invariant `MemoryLayout` validates) and turns vnode order into a
229        // clean compatibility surface, since adding new fixed or reserved
230        // ranges only shifts vnodes whose own span actually covers them.
231        for request in requests {
232            let floor = self.ram_end;
233            let ranges = find_lowest_splittable_fit(
234                &self.free,
235                request.size,
236                request.alignment,
237                floor,
238                ADDRESS_LIMIT,
239            )
240            .ok_or_else(|| {
241                exhausted_error(
242                    &request.tag,
243                    request.size,
244                    request.alignment,
245                    AllocationPhase::Ram,
246                    &self.free,
247                    floor,
248                    ADDRESS_LIMIT,
249                )
250            })?;
251
252            request.target.clear();
253            request.target.extend_from_slice(&ranges);
254            for range in ranges {
255                self.allocate_range(&request.tag, PlacedRangeKind::Ram, range);
256            }
257        }
258
259        Ok(())
260    }
261
262    fn place_mmio64(&mut self, requests: &mut [DynamicRequest<'_>]) -> Result<(), AllocateError> {
263        // High MMIO is allocated bottom up above RAM, but never below the
264        // 4 GiB boundary: it is "64-bit" MMIO and must not overlap the 32-bit
265        // window even when RAM is small. The allocator intentionally does not
266        // take host physical-address width as an input; callers validate the
267        // resulting top against host capabilities later.
268        requests.sort_by_key(|r| r.placement_sort_key());
269
270        let floor = self.ram_end.max(FOUR_GIB);
271        for request in requests {
272            let Some(start) = find_lowest_fit(
273                &self.free,
274                request.size,
275                request.alignment,
276                floor,
277                ADDRESS_LIMIT,
278            ) else {
279                return Err(exhausted_error(
280                    &request.tag,
281                    request.size,
282                    request.alignment,
283                    AllocationPhase::Mmio64,
284                    &self.free,
285                    floor,
286                    ADDRESS_LIMIT,
287                ));
288            };
289
290            let range = MemoryRange::new(start..start + request.size);
291            *request.target = range;
292            self.allocate_range(&request.tag, PlacedRangeKind::Mmio64, range);
293        }
294
295        Ok(())
296    }
297
298    fn place_post_mmio(
299        &mut self,
300        requests: &mut [DynamicRequest<'_>],
301    ) -> Result<(), AllocateError> {
302        // These ranges are intentionally placed after all RAM/MMIO work and in
303        // caller order. They are for implementation-private ranges that should
304        // not change the VTL0-visible layout or be reordered by alignment.
305        for request in requests {
306            let layout_top = self.layout_top();
307            let Some(start) = find_lowest_fit(
308                &self.free,
309                request.size,
310                request.alignment,
311                layout_top,
312                ADDRESS_LIMIT,
313            ) else {
314                return Err(exhausted_error(
315                    &request.tag,
316                    request.size,
317                    request.alignment,
318                    AllocationPhase::PostMmio,
319                    &self.free,
320                    layout_top,
321                    ADDRESS_LIMIT,
322                ));
323            };
324
325            let range = MemoryRange::new(start..start + request.size);
326            *request.target = range;
327            self.allocate_range(&request.tag, PlacedRangeKind::PostMmio, range);
328        }
329
330        Ok(())
331    }
332
333    fn layout_top(&self) -> u64 {
334        self.allocations
335            .iter()
336            .filter(|allocation| allocation.kind != PlacedRangeKind::Reserved)
337            .map(|allocation| allocation.range.end())
338            .max()
339            .unwrap_or(0)
340    }
341
342    fn allocate_range(&mut self, tag: &Arc<str>, kind: PlacedRangeKind, range: MemoryRange) {
343        self.remove_free_range(range);
344        self.allocations.push(PlacedRange {
345            tag: tag.clone(),
346            kind,
347            range,
348        });
349        if kind == PlacedRangeKind::Ram {
350            self.ram_end = self.ram_end.max(range.end());
351        }
352    }
353
354    fn remove_free_range(&mut self, allocated: MemoryRange) {
355        let free_index = self
356            .free
357            .partition_point(|range| range.start() <= allocated.start())
358            .checked_sub(1)
359            .expect("allocated range must be contained in the free list");
360        assert!(self.free[free_index].contains(&allocated));
361        let free_range = self.free.remove(free_index);
362
363        let mut insert_index = free_index;
364        if free_range.start() < allocated.start() {
365            self.free.insert(
366                insert_index,
367                MemoryRange::new(free_range.start()..allocated.start()),
368            );
369            insert_index += 1;
370        }
371        if allocated.end() < free_range.end() {
372            self.free.insert(
373                insert_index,
374                MemoryRange::new(allocated.end()..free_range.end()),
375            );
376        }
377    }
378}
379
380/// Error returned by [`LayoutBuilder::allocate`].
381#[derive(Debug, Error)]
382pub enum AllocateError {
383    /// A request has an invalid size.
384    #[error("{tag}: invalid size {size:#x} (must be > 0 and a multiple of {PAGE_SIZE:#x})")]
385    InvalidSize {
386        /// The tag identifying the request.
387        tag: Arc<str>,
388        /// The invalid size.
389        size: u64,
390    },
391    /// A request has an invalid alignment.
392    #[error("{tag}: invalid alignment {alignment:#x} (must be >= {PAGE_SIZE:#x} and a power of 2)")]
393    InvalidAlignment {
394        /// The tag identifying the request.
395        tag: Arc<str>,
396        /// The invalid alignment.
397        alignment: u64,
398    },
399    /// Two fixed or reserved requests overlap.
400    #[error("fixed/reserved requests {tag_a} ({range_a}) and {tag_b} ({range_b}) overlap")]
401    FixedOverlap {
402        /// The tag of the first request.
403        tag_a: Arc<str>,
404        /// The range of the first request.
405        range_a: MemoryRange,
406        /// The tag of the second request.
407        tag_b: Arc<str>,
408        /// The range of the second request.
409        range_b: MemoryRange,
410    },
411    /// A dynamic request could not be satisfied.
412    #[error(
413        "{tag}: cannot allocate {size:#x} bytes with alignment {alignment:#x} during {phase:?}; remaining free space in phase: {free_space:#x} bytes"
414    )]
415    Exhausted {
416        /// The tag identifying the request.
417        tag: Arc<str>,
418        /// The requested size.
419        size: u64,
420        /// The requested alignment.
421        alignment: u64,
422        /// The allocation phase.
423        phase: AllocationPhase,
424        /// The remaining free space in the phase.
425        free_space: u64,
426    },
427}
428
429impl<'a> LayoutBuilder<'a> {
430    /// Creates a new layout builder.
431    pub fn new() -> Self {
432        Self {
433            reserved: Vec::new(),
434            fixed: Vec::new(),
435            mmio32: Vec::new(),
436            ram: Vec::new(),
437            mmio64: Vec::new(),
438            post_mmio: Vec::new(),
439        }
440    }
441
442    /// Reserves a range so no allocation can use it.
443    ///
444    /// Reserved ranges are removed from the free list and may appear in the
445    /// returned [`PlacedRange`] list, but they do not affect post-MMIO
446    /// placement. Trailing reserved ranges are omitted from the returned list.
447    pub fn reserve(&mut self, tag: impl Into<Arc<str>>, range: MemoryRange) {
448        self.reserved.push(ReservedRequest {
449            tag: tag.into(),
450            range,
451        });
452    }
453
454    /// Adds a fixed range request to the builder.
455    ///
456    pub fn fixed(&mut self, tag: impl Into<Arc<str>>, range: MemoryRange) {
457        self.fixed.push(FixedRequest {
458            tag: tag.into(),
459            range,
460        });
461    }
462
463    /// Adds a dynamic single-range request to the builder.
464    ///
465    /// The target is filled in when [`Self::allocate`] succeeds.
466    pub fn request(
467        &mut self,
468        tag: impl Into<Arc<str>>,
469        target: &'a mut MemoryRange,
470        size: u64,
471        alignment: u64,
472        placement: Placement,
473    ) {
474        let request = DynamicRequest {
475            tag: tag.into(),
476            target,
477            size,
478            alignment,
479        };
480        match placement {
481            Placement::Mmio32 => self.mmio32.push(request),
482            Placement::Mmio64 => self.mmio64.push(request),
483            Placement::PostMmio => self.post_mmio.push(request),
484        }
485    }
486
487    /// Adds an ordinary RAM request to the builder.
488    ///
489    /// RAM requests are placed in caller order. The first request is placed
490    /// bottom up from GPA 0; each subsequent request starts at or above the
491    /// highest address used by previous RAM requests, so later requests never
492    /// backfill fragments skipped by earlier ones. A single request may still
493    /// split around fixed and Mmio32 ranges encountered inside its own span;
494    /// each extent starts at `alignment`, and split extents that do not
495    /// satisfy the rest of the request are rounded down to `alignment` so
496    /// large aligned requests are not fragmented into smaller chunks. The
497    /// target vector is replaced with the placed RAM extents when
498    /// [`Self::allocate`] succeeds.
499    pub fn ram(
500        &mut self,
501        tag: impl Into<Arc<str>>,
502        target: &'a mut Vec<MemoryRange>,
503        size: u64,
504        alignment: u64,
505    ) {
506        self.ram.push(RamRequest {
507            tag: tag.into(),
508            target,
509            size,
510            alignment,
511        });
512    }
513
514    /// Allocates all requests, fills in each target, and returns every placed
515    /// range sorted by address.
516    pub fn allocate(mut self) -> Result<Vec<PlacedRange>, AllocateError> {
517        validate_requests(&self.reserved, |r| (&r.tag, r.range.len(), PAGE_SIZE))?;
518        validate_requests(&self.fixed, |r| (&r.tag, r.range.len(), PAGE_SIZE))?;
519        validate_pinned_ranges(&self.reserved, &self.fixed)?;
520        validate_requests(&self.mmio32, |r| (&r.tag, r.size, r.alignment))?;
521        validate_requests(&self.ram, |r| (&r.tag, r.size, r.alignment))?;
522        validate_requests(&self.mmio64, |r| (&r.tag, r.size, r.alignment))?;
523        validate_requests(&self.post_mmio, |r| (&r.tag, r.size, r.alignment))?;
524
525        let mut state = AllocationState::new();
526        state.place_reserved(&self.reserved);
527        state.place_fixed(&self.fixed)?;
528        state.place_mmio32(&mut self.mmio32)?;
529        state.place_ram(&mut self.ram)?;
530        state.place_mmio64(&mut self.mmio64)?;
531        state.place_post_mmio(&mut self.post_mmio)?;
532
533        state.allocations.sort_by_key(|allocation| allocation.range);
534        // Trailing reserved ranges sit above every guest-visible allocation and
535        // exist only to keep that space out of the free list during placement.
536        // Returning them would bloat the layout without informing any
537        // consumer, so drop them. Reserved ranges interleaved with real
538        // allocations are still reported.
539        while state
540            .allocations
541            .last()
542            .is_some_and(|allocation| allocation.kind == PlacedRangeKind::Reserved)
543        {
544            state.allocations.pop();
545        }
546        Ok(state.allocations)
547    }
548}
549
550impl Default for LayoutBuilder<'_> {
551    fn default() -> Self {
552        Self::new()
553    }
554}
555
556fn validate_size_alignment(tag: &Arc<str>, size: u64, alignment: u64) -> Result<(), AllocateError> {
557    if size == 0 || !size.is_multiple_of(PAGE_SIZE) {
558        return Err(AllocateError::InvalidSize {
559            tag: tag.clone(),
560            size,
561        });
562    }
563
564    if alignment < PAGE_SIZE || !alignment.is_power_of_two() {
565        return Err(AllocateError::InvalidAlignment {
566            tag: tag.clone(),
567            alignment,
568        });
569    }
570
571    Ok(())
572}
573
574fn validate_requests<T>(
575    requests: &[T],
576    get: impl Fn(&T) -> (&Arc<str>, u64, u64),
577) -> Result<(), AllocateError> {
578    for request in requests {
579        let (tag, size, alignment) = get(request);
580        validate_size_alignment(tag, size, alignment)?;
581    }
582
583    Ok(())
584}
585
586fn validate_pinned_ranges(
587    reserved_requests: &[ReservedRequest],
588    fixed_requests: &[FixedRequest],
589) -> Result<(), AllocateError> {
590    let mut pinned = reserved_requests
591        .iter()
592        .map(|request| (request.range, &request.tag))
593        .chain(
594            fixed_requests
595                .iter()
596                .map(|request| (request.range, &request.tag)),
597        )
598        .collect::<Vec<_>>();
599
600    pinned.sort_by_key(|(range, _)| range.start());
601
602    for &[(range_a, tag_a), (range_b, tag_b)] in pinned.array_windows() {
603        if range_a.overlaps(&range_b) {
604            return Err(AllocateError::FixedOverlap {
605                tag_a: tag_a.clone(),
606                range_a,
607                tag_b: tag_b.clone(),
608                range_b,
609            });
610        }
611    }
612
613    Ok(())
614}
615
616fn exhausted_error(
617    tag: &Arc<str>,
618    size: u64,
619    alignment: u64,
620    phase: AllocationPhase,
621    free_ranges: &[MemoryRange],
622    region_start: u64,
623    region_end: u64,
624) -> AllocateError {
625    AllocateError::Exhausted {
626        tag: tag.clone(),
627        size,
628        alignment,
629        phase,
630        free_space: free_space_in_region(free_ranges, region_start, region_end),
631    }
632}
633
634fn free_space_in_region(free_ranges: &[MemoryRange], region_start: u64, region_end: u64) -> u64 {
635    free_ranges
636        .iter()
637        .filter_map(|range| clamp_to_region(*range, region_start, region_end))
638        .map(|(start, end)| end - start)
639        .sum()
640}
641
642/// Clamps a free range to the requested placement region. Returns `None` when
643/// the intersection is empty.
644fn clamp_to_region(range: MemoryRange, region_start: u64, region_end: u64) -> Option<(u64, u64)> {
645    let start = range.start().max(region_start);
646    let end = range.end().min(region_end);
647    (start < end).then_some((start, end))
648}
649
650fn find_highest_fit(
651    free_ranges: &[MemoryRange],
652    size: u64,
653    alignment: u64,
654    region_start: u64,
655    region_end: u64,
656) -> Option<u64> {
657    for range in free_ranges.iter().rev() {
658        let Some((effective_start, effective_end)) =
659            clamp_to_region(*range, region_start, region_end)
660        else {
661            continue;
662        };
663        if effective_end - effective_start < size {
664            continue;
665        }
666        let aligned_start = align_down(effective_end - size, alignment);
667        if aligned_start >= effective_start {
668            return Some(aligned_start);
669        }
670    }
671
672    None
673}
674
675fn find_lowest_fit(
676    free_ranges: &[MemoryRange],
677    size: u64,
678    alignment: u64,
679    region_start: u64,
680    region_end: u64,
681) -> Option<u64> {
682    for range in free_ranges {
683        let Some((effective_start, effective_end)) =
684            clamp_to_region(*range, region_start, region_end)
685        else {
686            continue;
687        };
688        let Some(aligned_start) = align_up(effective_start, alignment) else {
689            continue;
690        };
691        let Some(end) = aligned_start.checked_add(size) else {
692            continue;
693        };
694        if end <= effective_end {
695            return Some(aligned_start);
696        }
697    }
698
699    None
700}
701
702fn find_lowest_splittable_fit(
703    free_ranges: &[MemoryRange],
704    size: u64,
705    alignment: u64,
706    region_start: u64,
707    region_end: u64,
708) -> Option<Vec<MemoryRange>> {
709    let mut remaining = size;
710    let mut ranges = Vec::new();
711
712    for range in free_ranges {
713        let Some((effective_start, effective_end)) =
714            clamp_to_region(*range, region_start, region_end)
715        else {
716            continue;
717        };
718        let Some(aligned_start) = align_up(effective_start, alignment) else {
719            continue;
720        };
721        if aligned_start >= effective_end {
722            continue;
723        }
724
725        let available = effective_end - aligned_start;
726        let allocation_size = if available >= remaining {
727            remaining
728        } else {
729            align_down(available, alignment)
730        };
731        if allocation_size == 0 {
732            continue;
733        }
734        ranges.push(MemoryRange::new(
735            aligned_start..aligned_start + allocation_size,
736        ));
737        remaining -= allocation_size;
738
739        if remaining == 0 {
740            return Some(ranges);
741        }
742    }
743
744    None
745}
746
747fn align_down(value: u64, alignment: u64) -> u64 {
748    value & !(alignment - 1)
749}
750
751fn align_up(value: u64, alignment: u64) -> Option<u64> {
752    value
753        .checked_add(alignment - 1)
754        .map(|value| align_down(value, alignment))
755}
756
757#[cfg(test)]
758mod tests {
759    use super::*;
760
761    const KIB: u64 = 1024;
762    const MIB: u64 = 1024 * KIB;
763    const GIB: u64 = 1024 * MIB;
764
765    #[test]
766    fn empty_input() {
767        let sorted = LayoutBuilder::new().allocate().unwrap();
768        assert!(sorted.is_empty());
769    }
770
771    #[test]
772    fn fixed_request_is_reported() {
773        let mut builder = LayoutBuilder::new();
774        let range = MemoryRange::new(0xFC00_0000..0xFC40_0000);
775        builder.fixed("fixed", range);
776
777        let sorted = builder.allocate().unwrap();
778
779        assert_eq!(sorted[0].range, range);
780        assert_eq!(sorted[0].kind, PlacedRangeKind::Fixed);
781    }
782
783    #[test]
784    fn fixed_overlap_rejected() {
785        let mut builder = LayoutBuilder::new();
786        builder.fixed("first", MemoryRange::new(0x1000..0x3000));
787        builder.fixed("second", MemoryRange::new(0x2000..0x3000));
788
789        let error = builder.allocate().unwrap_err();
790
791        assert!(matches!(error, AllocateError::FixedOverlap { .. }));
792    }
793
794    #[test]
795    fn invalid_request_rejected() {
796        let mut target = MemoryRange::EMPTY;
797        let mut builder = LayoutBuilder::new();
798        builder.request("zero", &mut target, 0, PAGE_SIZE, Placement::Mmio32);
799        assert!(matches!(
800            builder.allocate().unwrap_err(),
801            AllocateError::InvalidSize { .. }
802        ));
803
804        let mut target = MemoryRange::EMPTY;
805        let mut builder = LayoutBuilder::new();
806        builder.request("alignment", &mut target, PAGE_SIZE, KIB, Placement::Mmio32);
807        assert!(matches!(
808            builder.allocate().unwrap_err(),
809            AllocateError::InvalidAlignment { .. }
810        ));
811    }
812
813    #[test]
814    fn reserved_overlap_rejected() {
815        let mut builder = LayoutBuilder::new();
816        builder.reserve("reserved", MemoryRange::new(GIB..GIB + MIB));
817        builder.fixed(
818            "fixed",
819            MemoryRange::new(GIB + PAGE_SIZE..GIB + PAGE_SIZE + MIB),
820        );
821
822        let error = builder.allocate().unwrap_err();
823
824        assert!(matches!(error, AllocateError::FixedOverlap { .. }));
825    }
826
827    #[test]
828    fn mmio32_uses_top_down_placement_below_4_gib() {
829        let mut first = MemoryRange::EMPTY;
830        let mut second = MemoryRange::EMPTY;
831        let mut builder = LayoutBuilder::new();
832        builder.fixed("reserved", MemoryRange::new(0xFE00_0000..0x1_0000_0000));
833        builder.request("first", &mut first, MIB, MIB, Placement::Mmio32);
834        builder.request("second", &mut second, MIB, MIB, Placement::Mmio32);
835
836        builder.allocate().unwrap();
837
838        assert_eq!(first, MemoryRange::new(0xFDF0_0000..0xFE00_0000));
839        assert_eq!(second, MemoryRange::new(0xFDE0_0000..0xFDF0_0000));
840    }
841
842    #[test]
843    fn mmio32_orders_by_alignment_then_size_then_request_order() {
844        let mut small = MemoryRange::EMPTY;
845        let mut aligned = MemoryRange::EMPTY;
846        let mut large = MemoryRange::EMPTY;
847        let mut builder = LayoutBuilder::new();
848        builder.request("small", &mut small, MIB, MIB, Placement::Mmio32);
849        builder.request("aligned", &mut aligned, MIB, 256 * MIB, Placement::Mmio32);
850        builder.request("large", &mut large, 4 * MIB, MIB, Placement::Mmio32);
851
852        builder.allocate().unwrap();
853
854        assert_eq!(aligned.start() % (256 * MIB), 0);
855        assert_eq!(large.len(), 4 * MIB);
856        assert_eq!(small.len(), MIB);
857        assert!(!aligned.overlaps(&large));
858        assert!(!aligned.overlaps(&small));
859        assert!(!large.overlaps(&small));
860    }
861
862    #[test]
863    fn ram_starts_at_zero() {
864        let mut ram = Vec::new();
865        let mut builder = LayoutBuilder::new();
866        builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
867
868        let sorted = builder.allocate().unwrap();
869
870        assert_eq!(ram, [MemoryRange::new(0..2 * GIB)]);
871        assert_eq!(sorted[0].kind, PlacedRangeKind::Ram);
872        assert_eq!(sorted[0].range, ram[0]);
873    }
874
875    #[test]
876    fn ram_splits_around_fixed_ranges_and_mmio32() {
877        let mut mmio32 = MemoryRange::EMPTY;
878        let mut ram = Vec::new();
879        let mut builder = LayoutBuilder::new();
880        builder.fixed("fixed", MemoryRange::new(GIB..GIB + MIB));
881        builder.request("mmio32", &mut mmio32, 2 * GIB, MIB, Placement::Mmio32);
882        builder.ram("ram", &mut ram, 3 * GIB, PAGE_SIZE);
883
884        builder.allocate().unwrap();
885
886        assert_eq!(
887            ram,
888            [
889                MemoryRange::new(0..GIB),
890                MemoryRange::new(GIB + MIB..2 * GIB),
891                MemoryRange::new(FOUR_GIB..FOUR_GIB + GIB + MIB),
892            ]
893        );
894    }
895
896    #[test]
897    fn ram_split_chunks_round_down_to_alignment() {
898        let mut ram = Vec::new();
899        let mut builder = LayoutBuilder::new();
900        builder.fixed("fixed", MemoryRange::new(GIB + MIB..GIB + 2 * MIB));
901        builder.ram("ram", &mut ram, 2 * GIB, GIB);
902
903        builder.allocate().unwrap();
904
905        assert_eq!(
906            ram,
907            [MemoryRange::new(0..GIB), MemoryRange::new(2 * GIB..3 * GIB),]
908        );
909    }
910
911    #[test]
912    fn ram_requests_are_placed_in_order() {
913        // Two RAM requests must not interleave: the second request starts at
914        // or above the maximum end address of the first, so the flattened
915        // RAM list is always sorted by address.
916        let mut first = Vec::new();
917        let mut second = Vec::new();
918        let mut builder = LayoutBuilder::new();
919        builder.ram("first", &mut first, 2 * GIB, PAGE_SIZE);
920        builder.ram("second", &mut second, GIB, PAGE_SIZE);
921
922        builder.allocate().unwrap();
923
924        assert_eq!(first, [MemoryRange::new(0..2 * GIB)]);
925        assert_eq!(second, [MemoryRange::new(2 * GIB..3 * GIB)]);
926    }
927
928    #[test]
929    fn ram_request_does_not_backfill_earlier_fragments() {
930        // A small fixed range below the first RAM request's end leaves an
931        // unaligned fragment that the first request skips. An earlier
932        // best-fit policy would have allowed a smaller-aligned later RAM
933        // request to backfill that fragment, producing an out-of-order RAM
934        // list. In-order placement floors each request at the previous
935        // request's end, so the fragment stays unallocated and vnode order
936        // matches address order.
937        let mut first = Vec::new();
938        let mut second = Vec::new();
939        let mut builder = LayoutBuilder::new();
940        // Carve a tiny hole inside what the first request would otherwise
941        // round down to a GiB-aligned chunk.
942        builder.fixed("hole", MemoryRange::new(GIB + MIB..GIB + 2 * MIB));
943        builder.ram("first", &mut first, 2 * GIB, GIB);
944        builder.ram("second", &mut second, 256 * MIB, PAGE_SIZE);
945        builder.allocate().unwrap();
946
947        // First request lands at [0, 1 GiB) and [2 GiB, 3 GiB); the fragment
948        // at [1 GiB + 2 MiB, 2 GiB) is left free.
949        assert_eq!(
950            first,
951            [MemoryRange::new(0..GIB), MemoryRange::new(2 * GIB..3 * GIB)]
952        );
953        // The 256 MiB second request would fit at 1 GiB + 2 MiB if backfill
954        // were allowed; instead it must come after the first request's max
955        // end (3 GiB).
956        assert_eq!(second.len(), 1);
957        assert!(
958            second[0].start() >= first.iter().map(|r| r.end()).max().unwrap(),
959            "second RAM request backfilled below first request's end: {second:?}"
960        );
961        assert_eq!(second, [MemoryRange::new(3 * GIB..3 * GIB + 256 * MIB)]);
962    }
963
964    #[test]
965    fn ram_in_order_keeps_flattened_list_sorted_with_mmio32() {
966        // Reproduces the scenario that would have produced an unsorted RAM
967        // list under best-fit: a fixed Mmio32-style range low in memory plus
968        // a small second vnode that could otherwise be placed before the
969        // first vnode's tail.
970        let mut first = Vec::new();
971        let mut second = Vec::new();
972        let mut builder = LayoutBuilder::new();
973        // A 1 MiB fixed range (e.g. a PCIe BAR) just above 1 GiB.
974        builder.fixed("pcie_bar", MemoryRange::new(0x4010_0000..0x4020_0000));
975        builder.ram("first", &mut first, 2 * GIB, PAGE_SIZE);
976        builder.ram("second", &mut second, 512 * MIB, PAGE_SIZE);
977
978        builder.allocate().unwrap();
979
980        let first_end = first.iter().map(|r| r.end()).max().unwrap();
981        assert!(
982            second.iter().all(|r| r.start() >= first_end),
983            "second vnode placed below first vnode's end: first={first:?} second={second:?}"
984        );
985
986        let mut all: Vec<_> = first.iter().chain(second.iter()).copied().collect();
987        let sorted = {
988            let mut s = all.clone();
989            s.sort_by_key(|r| r.start());
990            s
991        };
992        assert_eq!(all, sorted, "flattened RAM list must be sorted");
993        // Sanity: no overlaps either.
994        all.sort_by_key(|r| r.start());
995        for pair in all.windows(2) {
996            assert!(
997                pair[0].end() <= pair[1].start(),
998                "overlapping RAM ranges: {pair:?}"
999            );
1000        }
1001    }
1002
1003    #[test]
1004    fn mmio64_uses_bottom_up_placement_above_four_gib() {
1005        let mut ram = Vec::new();
1006        let mut first = MemoryRange::EMPTY;
1007        let mut second = MemoryRange::EMPTY;
1008        let mut builder = LayoutBuilder::new();
1009        builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
1010        builder.request("first", &mut first, MIB, MIB, Placement::Mmio64);
1011        builder.request("second", &mut second, MIB, MIB, Placement::Mmio64);
1012
1013        builder.allocate().unwrap();
1014
1015        // Mmio64 is floored at 4 GiB even when RAM ends below it.
1016        assert_eq!(first, MemoryRange::new(FOUR_GIB..FOUR_GIB + MIB));
1017        assert_eq!(second, MemoryRange::new(FOUR_GIB + MIB..FOUR_GIB + 2 * MIB));
1018    }
1019
1020    #[test]
1021    fn mmio64_starts_above_ram_when_ram_exceeds_four_gib() {
1022        let mut ram = Vec::new();
1023        let mut mmio64 = MemoryRange::EMPTY;
1024        let mut builder = LayoutBuilder::new();
1025        builder.ram("ram", &mut ram, 6 * GIB, PAGE_SIZE);
1026        builder.request("mmio64", &mut mmio64, MIB, MIB, Placement::Mmio64);
1027
1028        builder.allocate().unwrap();
1029
1030        // RAM occupies [0, 4 GiB) and [4 GiB + low MMIO ..]; with no Mmio32
1031        // requests, the second RAM extent starts at 4 GiB and ends at 6 GiB +
1032        // (low MMIO hole) above 4 GiB. Mmio64 is placed bottom-up above RAM.
1033        let ram_end = ram.iter().map(|r| r.end()).max().unwrap();
1034        assert_eq!(mmio64, MemoryRange::new(ram_end..ram_end + MIB));
1035        assert!(mmio64.start() >= FOUR_GIB);
1036    }
1037
1038    #[test]
1039    fn mmio64_skips_fixed_ranges_above_four_gib() {
1040        let mut ram = Vec::new();
1041        let mut mmio64 = MemoryRange::EMPTY;
1042        let mut builder = LayoutBuilder::new();
1043        builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
1044        builder.fixed("fixed", MemoryRange::new(FOUR_GIB..FOUR_GIB + MIB));
1045        builder.request("mmio64", &mut mmio64, MIB, MIB, Placement::Mmio64);
1046
1047        builder.allocate().unwrap();
1048
1049        assert_eq!(mmio64, MemoryRange::new(FOUR_GIB + MIB..FOUR_GIB + 2 * MIB));
1050    }
1051
1052    #[test]
1053    fn post_mmio_uses_bottom_up_placement_after_all_mmio() {
1054        let mut ram = Vec::new();
1055        let mut mmio64 = MemoryRange::EMPTY;
1056        let mut post_mmio = MemoryRange::EMPTY;
1057        let mut builder = LayoutBuilder::new();
1058        builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
1059        builder.request("mmio64", &mut mmio64, MIB, MIB, Placement::Mmio64);
1060        builder.request("post_mmio", &mut post_mmio, MIB, MIB, Placement::PostMmio);
1061
1062        builder.allocate().unwrap();
1063
1064        assert_eq!(mmio64, MemoryRange::new(FOUR_GIB..FOUR_GIB + MIB));
1065        assert_eq!(
1066            post_mmio,
1067            MemoryRange::new(FOUR_GIB + MIB..FOUR_GIB + 2 * MIB)
1068        );
1069    }
1070
1071    #[test]
1072    fn post_mmio_preserves_request_order() {
1073        let mut ram = Vec::new();
1074        let mut first = MemoryRange::EMPTY;
1075        let mut aligned = MemoryRange::EMPTY;
1076        let mut builder = LayoutBuilder::new();
1077        builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
1078        builder.request("first", &mut first, MIB, MIB, Placement::PostMmio);
1079        builder.request("aligned", &mut aligned, MIB, GIB, Placement::PostMmio);
1080
1081        builder.allocate().unwrap();
1082
1083        assert_eq!(first, MemoryRange::new(2 * GIB..2 * GIB + MIB));
1084        assert_eq!(aligned, MemoryRange::new(3 * GIB..3 * GIB + MIB));
1085    }
1086
1087    #[test]
1088    fn high_reserved_range_does_not_affect_post_mmio_placement() {
1089        let mut ram = Vec::new();
1090        let mut post_mmio = MemoryRange::EMPTY;
1091        let mut builder = LayoutBuilder::new();
1092        builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
1093        builder.reserve(
1094            "high_reserved",
1095            MemoryRange::new(0xFD_0000_0000..0xFD_4000_0000),
1096        );
1097        builder.request("post_mmio", &mut post_mmio, MIB, MIB, Placement::PostMmio);
1098
1099        let sorted = builder.allocate().unwrap();
1100
1101        assert_eq!(post_mmio, MemoryRange::new(2 * GIB..2 * GIB + MIB));
1102        assert!(
1103            !sorted
1104                .iter()
1105                .any(|allocation| allocation.kind == PlacedRangeKind::Reserved)
1106        );
1107    }
1108
1109    #[test]
1110    fn reserved_range_between_allocations_is_reported() {
1111        let mut ram = Vec::new();
1112        let mut post_mmio = MemoryRange::EMPTY;
1113        let mut builder = LayoutBuilder::new();
1114        builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
1115        builder.reserve("reserved", MemoryRange::new(2 * GIB..2 * GIB + MIB));
1116        builder.request("post_mmio", &mut post_mmio, MIB, MIB, Placement::PostMmio);
1117
1118        let sorted = builder.allocate().unwrap();
1119
1120        assert_eq!(
1121            post_mmio,
1122            MemoryRange::new(2 * GIB + MIB..2 * GIB + 2 * MIB)
1123        );
1124        assert!(sorted.iter().any(|allocation| {
1125            allocation.kind == PlacedRangeKind::Reserved
1126                && allocation.range == MemoryRange::new(2 * GIB..2 * GIB + MIB)
1127        }));
1128    }
1129
1130    #[test]
1131    fn fixed_hypertransport_hole_is_regular_fixed_placement() {
1132        let mut ram = Vec::new();
1133        let mut builder = LayoutBuilder::new();
1134        builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
1135        let hypertransport = MemoryRange::new(0xFD_0000_0000..0xFD_4000_0000);
1136        builder.fixed("amd_hypertransport_hole", hypertransport);
1137
1138        let sorted = builder.allocate().unwrap();
1139
1140        assert_eq!(sorted.last().unwrap().range, hypertransport);
1141    }
1142
1143    #[test]
1144    fn exhaustion_reports_phase() {
1145        let mut mmio32 = MemoryRange::EMPTY;
1146        let mut builder = LayoutBuilder::new();
1147        builder.request(
1148            "too_big",
1149            &mut mmio32,
1150            4 * GIB + PAGE_SIZE,
1151            PAGE_SIZE,
1152            Placement::Mmio32,
1153        );
1154        assert!(matches!(
1155            builder.allocate().unwrap_err(),
1156            AllocateError::Exhausted {
1157                phase: AllocationPhase::Mmio32,
1158                ..
1159            }
1160        ));
1161
1162        let mut ram = Vec::new();
1163        let mut builder = LayoutBuilder::new();
1164        builder.fixed("fixed", MemoryRange::new(0..ADDRESS_LIMIT));
1165        builder.ram("ram", &mut ram, PAGE_SIZE, PAGE_SIZE);
1166        assert!(matches!(
1167            builder.allocate().unwrap_err(),
1168            AllocateError::Exhausted {
1169                phase: AllocationPhase::Ram,
1170                ..
1171            }
1172        ));
1173
1174        let mut ram = Vec::new();
1175        let mut mmio64 = MemoryRange::EMPTY;
1176        let mut builder = LayoutBuilder::new();
1177        builder.ram("ram", &mut ram, PAGE_SIZE, PAGE_SIZE);
1178        builder.fixed("fixed", MemoryRange::new(PAGE_SIZE..ADDRESS_LIMIT));
1179        builder.request(
1180            "mmio64",
1181            &mut mmio64,
1182            PAGE_SIZE,
1183            PAGE_SIZE,
1184            Placement::Mmio64,
1185        );
1186        assert!(matches!(
1187            builder.allocate().unwrap_err(),
1188            AllocateError::Exhausted {
1189                phase: AllocationPhase::Mmio64,
1190                ..
1191            }
1192        ));
1193    }
1194
1195    #[test]
1196    fn sorted_result_preserves_tags_and_kinds() {
1197        let mut ram = Vec::new();
1198        let mut mmio32 = MemoryRange::EMPTY;
1199        let mut mmio64 = MemoryRange::EMPTY;
1200        let mut builder = LayoutBuilder::new();
1201        builder.ram("ram", &mut ram, GIB, PAGE_SIZE);
1202        builder.request("mmio32", &mut mmio32, MIB, MIB, Placement::Mmio32);
1203        builder.request("mmio64", &mut mmio64, MIB, MIB, Placement::Mmio64);
1204
1205        let sorted = builder.allocate().unwrap();
1206
1207        // mmio32 sits just below 4 GiB; mmio64 sits at 4 GiB or above.
1208        assert_eq!(&*sorted[0].tag, "ram");
1209        assert_eq!(sorted[0].kind, PlacedRangeKind::Ram);
1210        assert_eq!(&*sorted[1].tag, "mmio32");
1211        assert_eq!(sorted[1].kind, PlacedRangeKind::Mmio32);
1212        assert_eq!(&*sorted[2].tag, "mmio64");
1213        assert_eq!(sorted[2].kind, PlacedRangeKind::Mmio64);
1214    }
1215
1216    #[test]
1217    fn deterministic() {
1218        let mut previous = None;
1219
1220        for _ in 0..10 {
1221            let mut ram = Vec::new();
1222            let mut vmbus_low = MemoryRange::EMPTY;
1223            let mut pcie_ecam = MemoryRange::EMPTY;
1224            let mut pcie_high = MemoryRange::EMPTY;
1225            let mut virtio = MemoryRange::EMPTY;
1226            let mut builder = LayoutBuilder::new();
1227            builder.ram("ram", &mut ram, 2 * GIB, PAGE_SIZE);
1228            builder.fixed("reserved", MemoryRange::new(0xFE00_0000..0x1_0000_0000));
1229            builder.request(
1230                "vmbus_low",
1231                &mut vmbus_low,
1232                128 * MIB,
1233                MIB,
1234                Placement::Mmio32,
1235            );
1236            builder.request(
1237                "pcie_ecam",
1238                &mut pcie_ecam,
1239                256 * MIB,
1240                256 * MIB,
1241                Placement::Mmio32,
1242            );
1243            builder.request("pcie_high", &mut pcie_high, GIB, MIB, Placement::Mmio64);
1244            builder.request(
1245                "virtio",
1246                &mut virtio,
1247                PAGE_SIZE,
1248                PAGE_SIZE,
1249                Placement::Mmio32,
1250            );
1251
1252            let sorted = builder.allocate().unwrap();
1253            if let Some(previous) = &previous {
1254                assert_eq!(previous, &sorted);
1255            }
1256            previous = Some(sorted);
1257        }
1258    }
1259}
vm_topology/layout.rs

vm_topology/
layout.rs
