guestmem/
ranges.rs

1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4//! Types representing contiguous and discontiguous ranges of guest memory.
5//!
6//! The primary type is [`PagedRange`], which describes a single logically
7//! contiguous byte range scattered across potentially-discontiguous guest
8//! pages. It is used throughout the storage and virtio stacks to describe
9//! IO buffers.
10//!
11//! # Memory model
12//!
13//! A `PagedRange` is defined by a GPN (guest page number) list, a starting
14//! byte offset, and a length. The byte range is a contiguous window into the
15//! flat byte space implied by concatenating the pages:
16//!
17//! ```text
18//!   gpns:   [ GPN_0 ]  [ GPN_1 ]  [ GPN_2 ]  [ GPN_3 ]
19//!   bytes:  0    4095  4096  8191  8192 12287 12288 16383
20//!
21//!                start                            end
22//!                  │                               │
23//!   GPN_0:  ░░░░░░░█████████   ◄── first page: partial (offset > 0)
24//!   GPN_1:  ██████████████████ ◄── interior page: always fully covered
25//!   GPN_2:  ██████████████████ ◄── interior page: always fully covered
26//!   GPN_3:  █████████░░░░░░░░░ ◄── last page: partial (end < page boundary)
27//! ```
28//!
29//! **Key constraint:** only the first and last pages may be partially
30//! covered. All interior pages are implicitly fully used. There is no way
31//! to express a gap or a non-zero starting offset on an interior page.
32//!
33//! This means you **cannot** combine two arbitrary guest memory regions
34//! (e.g., two virtio descriptors with arbitrary GPAs) into a single
35//! `PagedRange` unless every region boundary falls on a page boundary.
36//! See [`PagedRanges`] for a type that can represent multiple disjoint
37//! `PagedRange`s as a single logical buffer.
38
39#![warn(missing_docs)]
40
41use super::AccessError;
42use super::GuestMemory;
43use super::MemoryRead;
44use super::MemoryWrite;
45use super::PAGE_SIZE;
46use super::PAGE_SIZE64;
47use crate::InvalidGpn;
48
49/// A range of bytes in the guest address space.
50#[derive(Debug, Copy, Clone, PartialEq, Eq)]
51pub struct AddressRange {
52    /// The inclusive starting byte offset.
53    pub start: u64,
54    /// The exclusive ending byte offset.
55    pub end: u64,
56}
57
58impl AddressRange {
59    /// Returns the length of the range in bytes.
60    pub fn len(&self) -> u64 {
61        self.end - self.start
62    }
63
64    /// Returns whether the range is empty.
65    pub fn is_empty(&self) -> bool {
66        self.end == self.start
67    }
68}
69
70impl From<std::ops::Range<u64>> for AddressRange {
71    fn from(range: std::ops::Range<u64>) -> Self {
72        Self {
73            start: range.start,
74            end: range.end,
75        }
76    }
77}
78
79/// A single logically-contiguous byte range spread across guest pages.
80///
81/// `PagedRange` is defined by a GPN (guest page number) slice, a byte
82/// offset into that slice's implied flat address space, and a length.
83///
84/// # Interior-page constraint
85///
86/// The first page may start at an arbitrary byte offset and the last page
87/// may end before the page boundary, but **all interior pages are fully
88/// covered**. There is no way to skip bytes within an interior page.
89///
90/// ```text
91///   VALID:     ░░████  ██████  ██████  ███░░░
92///   INVALID:   ░░████  ░░████  ██████  ███░░░
93///                       ▲ interior page cannot start at non-zero offset
94/// ```
95///
96/// This means two guest memory regions starting at arbitrary GPAs cannot
97/// always be represented by a single `PagedRange`. Use [`PagedRanges`]
98/// when you need to concatenate multiple independent regions.
99///
100/// # Construction
101///
102/// Use [`PagedRange::new(offset, len, gpns)`](PagedRange::new) where
103/// `offset` is the byte offset into the page list and `len` is the total
104/// byte length. The GPN slice must be large enough to cover
105/// `offset + len` bytes.
106#[derive(Debug, Copy, Clone)]
107pub struct PagedRange<'a> {
108    /// The starting offset in bytes from the beginning of the range described
109    /// by `gpns`.
110    start: usize,
111    /// The ending offset in bytes from the beginning of the range described by
112    /// `gpns`.
113    end: usize,
114    /// The page list describing the range that this is a subset of.
115    gpns: &'a [u64],
116}
117
118impl<'a> PagedRange<'a> {
119    /// The page size for GPNs. This is always 4KB.
120    pub const PAGE_SIZE: usize = PAGE_SIZE;
121
122    /// Creates a new range over `gpns`, starting at `offset` bytes into the page list, extending for `len` bytes.
123    ///
124    /// Returns `None` if `offset` or `len` are out of bounds.
125    pub const fn new(offset: usize, len: usize, gpns: &'a [u64]) -> Option<Self> {
126        let maxlen = gpns.len() * PAGE_SIZE;
127        if maxlen < offset || maxlen - offset < len {
128            return None;
129        }
130        Some(PagedRange {
131            start: offset,
132            end: offset + len,
133            gpns,
134        })
135    }
136
137    /// Returns the empty range.
138    pub const fn empty() -> Self {
139        PagedRange {
140            start: 0,
141            end: 0,
142            gpns: &[],
143        }
144    }
145
146    /// Returns a subrange of this range, or `None` if the subrange is outside this range.
147    pub fn try_subrange(&self, offset: usize, len: usize) -> Option<Self> {
148        if self.len() >= offset && self.len() - offset >= len {
149            Some(PagedRange {
150                start: self.start + offset,
151                end: self.start + offset + len,
152                gpns: self.gpns,
153            })
154        } else {
155            None
156        }
157    }
158
159    /// Returns a subrange of this range.
160    ///
161    /// Panics if the subrange is outside this range.
162    #[track_caller]
163    pub fn subrange(&self, offset: usize, len: usize) -> Self {
164        self.try_subrange(offset, len)
165            .unwrap_or_else(|| panic!("invalid subrange: {} + {} > {}", offset, len, self.len()))
166    }
167
168    /// Returns the length of the range in bytes.
169    pub fn len(&self) -> usize {
170        self.end - self.start
171    }
172
173    /// Returns whether the range is empty.
174    pub fn is_empty(&self) -> bool {
175        self.start == self.end
176    }
177
178    /// Returns the byte offset into the first page of the range.
179    ///
180    /// Only the first page can have a non-zero offset; all subsequent
181    /// pages covered by the range are implicitly page-aligned.
182    pub fn offset(&self) -> usize {
183        self.start % PAGE_SIZE
184    }
185
186    /// Returns the range's list of page numbers.
187    pub fn gpns(&self) -> &'a [u64] {
188        let start_page = self.start / PAGE_SIZE;
189        let end_page = self.end.div_ceil(PAGE_SIZE);
190        &self.gpns[start_page..end_page]
191    }
192
193    /// Skips the first `len` bytes of the range.
194    ///
195    /// Panics if `len` is larger than the range's length.
196    pub fn skip(&mut self, len: usize) {
197        assert!(self.len() >= len);
198        self.start += len;
199    }
200
201    /// Truncates the range to `len` bytes.
202    ///
203    /// Panics if `len` is larger than the range's length.
204    pub fn truncate(&mut self, len: usize) {
205        assert!(self.len() >= len);
206        self.end = self.start + len;
207    }
208
209    /// Splits the range at `offset`.
210    ///
211    /// Panics if `offset` is outside the range.
212    pub fn split(self, offset: usize) -> (Self, Self) {
213        assert!(self.len() >= offset);
214        (
215            Self {
216                start: self.start,
217                end: self.start + offset,
218                gpns: self.gpns,
219            },
220            Self {
221                start: self.start + offset,
222                end: self.end,
223                gpns: self.gpns,
224            },
225        )
226    }
227
228    /// Splits the range at `offset`, returning `None` if `offset` is outside
229    /// the range.
230    pub fn try_split(self, offset: usize) -> Option<(Self, Self)> {
231        if self.len() >= offset {
232            Some((
233                Self {
234                    start: self.start,
235                    end: self.start + offset,
236                    gpns: self.gpns,
237                },
238                Self {
239                    start: self.start + offset,
240                    end: self.end,
241                    gpns: self.gpns,
242                },
243            ))
244        } else {
245            None
246        }
247    }
248
249    /// Removes and returns the first contiguous range.
250    pub fn pop_front_range(&mut self) -> Option<Result<AddressRange, InvalidGpn>> {
251        if self.is_empty() {
252            None
253        } else {
254            let start_page = self.start / PAGE_SIZE;
255            let end_page = self.end.div_ceil(PAGE_SIZE);
256            let mut page = start_page + 1;
257            while page < end_page && self.gpns[page - 1] + 1 == self.gpns[page] {
258                page += 1;
259            }
260
261            let end = (page * PAGE_SIZE).min(self.end);
262
263            let gpa = match crate::gpn_to_gpa(self.gpns[start_page]) {
264                Ok(gpa) => gpa,
265                Err(e) => return Some(Err(e)),
266            };
267            let start_gpa = gpa + self.start as u64 % PAGE_SIZE64;
268            let range = AddressRange {
269                start: start_gpa,
270                end: start_gpa + (end - self.start) as u64,
271            };
272            self.start = end;
273            Some(Ok(range))
274        }
275    }
276
277    /// Returns a [`MemoryRead`] implementation.
278    pub fn reader(self, mem: &'a GuestMemory) -> PagedRangeReader<'a> {
279        PagedRangeReader { range: self, mem }
280    }
281
282    /// Returns a [`MemoryWrite`] implementation.
283    pub fn writer(self, mem: &'a GuestMemory) -> PagedRangeWriter<'a> {
284        PagedRangeWriter { range: self, mem }
285    }
286
287    /// Returns an iterator over the [`AddressRange`]s represented by this
288    /// range.
289    pub fn ranges(self) -> PagedRangeRangeIter<'a> {
290        PagedRangeRangeIter(self)
291    }
292}
293
294/// An iterator returned by [`PagedRange::ranges()`].
295#[derive(Debug, Clone)]
296pub struct PagedRangeRangeIter<'a>(PagedRange<'a>);
297
298impl Iterator for PagedRangeRangeIter<'_> {
299    type Item = Result<AddressRange, InvalidGpn>;
300
301    fn next(&mut self) -> Option<Self::Item> {
302        self.0.pop_front_range()
303    }
304}
305
306/// A [`MemoryRead`] implementation for [`PagedRange`].
307pub struct PagedRangeReader<'a> {
308    range: PagedRange<'a>,
309    mem: &'a GuestMemory,
310}
311
312impl MemoryRead for PagedRangeReader<'_> {
313    fn read(&mut self, data: &mut [u8]) -> Result<&mut Self, AccessError> {
314        let range = self
315            .range
316            .try_subrange(0, data.len())
317            .ok_or_else(|| AccessError::OutOfRange(self.len(), data.len()))?;
318        self.mem
319            .read_range(&range, data)
320            .map_err(AccessError::Memory)?;
321        self.range.skip(data.len());
322        Ok(self)
323    }
324
325    fn skip(&mut self, len: usize) -> Result<&mut Self, AccessError> {
326        if self.len() < len {
327            return Err(AccessError::OutOfRange(self.len(), len));
328        }
329        self.range.skip(len);
330        Ok(self)
331    }
332
333    fn len(&self) -> usize {
334        self.range.len()
335    }
336}
337
338/// A [`MemoryWrite`] implementation for [`PagedRange`].
339pub struct PagedRangeWriter<'a> {
340    range: PagedRange<'a>,
341    mem: &'a GuestMemory,
342}
343
344impl MemoryWrite for PagedRangeWriter<'_> {
345    fn write(&mut self, data: &[u8]) -> Result<(), AccessError> {
346        let range = self
347            .range
348            .try_subrange(0, data.len())
349            .ok_or_else(|| AccessError::OutOfRange(self.len(), data.len()))?;
350        self.mem
351            .write_range(&range, data)
352            .map_err(AccessError::Memory)?;
353        self.range.skip(data.len());
354        Ok(())
355    }
356
357    fn fill(&mut self, val: u8, len: usize) -> Result<(), AccessError> {
358        let range = self
359            .range
360            .try_subrange(0, len)
361            .ok_or_else(|| AccessError::OutOfRange(self.len(), len))?;
362        self.mem
363            .fill_range(&range, val)
364            .map_err(AccessError::Memory)?;
365        self.range.skip(len);
366        Ok(())
367    }
368
369    fn len(&self) -> usize {
370        self.range.len()
371    }
372}
373
374/// A list of [`PagedRange`]s.
375#[derive(Debug, Clone)]
376pub struct PagedRanges<'a, T> {
377    ranges: T,
378    current: Option<PagedRange<'a>>,
379    start: usize,
380    end: usize,
381}
382
383impl<'a, T: Iterator<Item = PagedRange<'a>> + Clone> PagedRanges<'a, T> {
384    /// Constructs a list wrapping an iterator.
385    pub fn new<I>(ranges: I) -> Self
386    where
387        I: IntoIterator<IntoIter = T>,
388    {
389        let ranges = ranges.into_iter();
390        let len = ranges.clone().map(|range| range.len()).sum();
391        Self {
392            ranges,
393            current: None,
394            start: 0,
395            end: len,
396        }
397    }
398}
399
400impl<'a, T: Iterator<Item = PagedRange<'a>>> PagedRanges<'a, T> {
401    /// Returns the total length in bytes of the ranges.
402    pub fn len(&self) -> usize {
403        self.end - self.start
404    }
405
406    /// Returns true if the range list is empty.
407    pub fn is_empty(&self) -> bool {
408        self.start == self.end
409    }
410
411    /// Advances the range list by `len` bytes.
412    pub fn skip(&mut self, mut len: usize) {
413        assert!(self.len() >= len);
414        while len > 0 {
415            let n = self.current(len).len();
416            self.advance(n);
417            len -= n;
418        }
419    }
420
421    /// Returns a new list limited to `len` bytes.
422    ///
423    /// Panics if `len` is larger than the range's length.
424    pub fn truncate(&mut self, len: usize) {
425        assert!(self.len() >= len);
426        self.end = self.start + len;
427    }
428
429    /// Returns an iterator of the remaining paged ranges.
430    pub fn paged_ranges(self) -> PagedRangesIter<'a, T> {
431        PagedRangesIter(self)
432    }
433
434    /// Returns a [`MemoryRead`] implementation for the ranges.
435    pub fn reader(self, mem: &'a GuestMemory) -> PagedRangesReader<'a, T> {
436        PagedRangesReader { views: self, mem }
437    }
438
439    /// Returns a [`MemoryWrite`] implementation for the ranges.
440    pub fn writer(self, mem: &'a GuestMemory) -> PagedRangesWriter<'a, T> {
441        PagedRangesWriter { views: self, mem }
442    }
443
444    fn current(&mut self, max_len: usize) -> PagedRange<'a> {
445        debug_assert!(max_len <= self.len());
446        if self.current.is_none() {
447            self.current = self.ranges.next();
448        }
449        let range = self.current.unwrap();
450        range.subrange(self.start, max_len.min(range.len() - self.start))
451    }
452
453    fn advance(&mut self, n: usize) {
454        let current = self.current.as_ref().unwrap();
455        self.start += n;
456        if self.start == current.len() {
457            self.current = None;
458            self.end -= self.start;
459            self.start = 0;
460        }
461    }
462}
463
464/// An iterator returned by [`PagedRanges::paged_ranges`].
465pub struct PagedRangesIter<'a, T>(PagedRanges<'a, T>);
466
467impl<'a, T: Iterator<Item = PagedRange<'a>>> Iterator for PagedRangesIter<'a, T> {
468    type Item = PagedRange<'a>;
469
470    fn next(&mut self) -> Option<Self::Item> {
471        if self.0.is_empty() {
472            return None;
473        }
474        let current = self
475            .0
476            .current
477            .take()
478            .or_else(|| self.0.ranges.next())
479            .unwrap();
480        let offset = self.0.start;
481        let len = self.0.end.min(current.len()) - offset;
482        self.0.end -= offset + len;
483        self.0.current = None;
484        self.0.start = 0;
485        Some(current.subrange(offset, len))
486    }
487}
488
489/// A [`MemoryRead`] implementation for [`PagedRanges`].
490#[derive(Debug, Clone)]
491pub struct PagedRangesReader<'a, T> {
492    views: PagedRanges<'a, T>,
493    mem: &'a GuestMemory,
494}
495
496impl<'a, T> PagedRangesReader<'a, T> {
497    /// Returns the inner ranges.
498    pub fn into_inner(self) -> PagedRanges<'a, T> {
499        self.views
500    }
501}
502
503impl<'a, T: Iterator<Item = PagedRange<'a>>> MemoryRead for PagedRangesReader<'a, T> {
504    fn read(&mut self, mut data: &mut [u8]) -> Result<&mut Self, AccessError> {
505        if self.len() < data.len() {
506            return Err(AccessError::OutOfRange(self.len(), data.len()));
507        }
508        while !data.is_empty() {
509            let range = self.views.current(data.len());
510            let (buf, rest) = data.split_at_mut(range.len());
511            self.mem
512                .read_range(&range, buf)
513                .map_err(AccessError::Memory)?;
514            self.views.advance(range.len());
515            data = rest;
516        }
517        Ok(self)
518    }
519
520    fn skip(&mut self, len: usize) -> Result<&mut Self, AccessError> {
521        if self.len() < len {
522            return Err(AccessError::OutOfRange(self.len(), len));
523        }
524        self.views.skip(len);
525        Ok(self)
526    }
527
528    fn len(&self) -> usize {
529        self.views.len()
530    }
531}
532
533/// A [`MemoryWrite`] implementation for [`PagedRanges`].
534#[derive(Debug)]
535pub struct PagedRangesWriter<'a, T> {
536    views: PagedRanges<'a, T>,
537    mem: &'a GuestMemory,
538}
539
540impl<'a, T> PagedRangesWriter<'a, T> {
541    /// Returns the inner ranges.
542    pub fn into_inner(self) -> PagedRanges<'a, T> {
543        self.views
544    }
545}
546
547impl<'a, T: Iterator<Item = PagedRange<'a>>> MemoryWrite for PagedRangesWriter<'a, T> {
548    fn write(&mut self, mut data: &[u8]) -> Result<(), AccessError> {
549        if self.len() < data.len() {
550            return Err(AccessError::OutOfRange(self.len(), data.len()));
551        }
552        while !data.is_empty() {
553            let range = self.views.current(data.len());
554            let (buf, rest) = data.split_at(range.len());
555            self.mem
556                .write_range(&range, buf)
557                .map_err(AccessError::Memory)?;
558            self.views.advance(range.len());
559            data = rest;
560        }
561        Ok(())
562    }
563
564    fn fill(&mut self, val: u8, mut len: usize) -> Result<(), AccessError> {
565        if self.len() < len {
566            return Err(AccessError::OutOfRange(self.len(), len));
567        }
568        while len > 0 {
569            let range = self.views.current(len);
570            self.mem
571                .fill_range(&range, val)
572                .map_err(AccessError::Memory)?;
573            self.views.advance(range.len());
574            len -= range.len();
575        }
576        Ok(())
577    }
578
579    fn len(&self) -> usize {
580        self.views.len()
581    }
582}
583
584#[cfg(test)]
585mod tests {
586    use super::*;
587
588    #[test]
589    fn test_ranges() {
590        assert!(PagedRange::new(1, PAGE_SIZE, &[1]).is_none());
591
592        let view1 = PagedRange::new(0x123, 0x2012, &[0x11, 0x22, 0x33]).unwrap();
593        let view2 = PagedRange::new(0x456, 0x2017, &[0x111, 0x112, 0x222]).unwrap();
594        let views = [view1, view2];
595        let mut multi = PagedRanges::new(views.iter().copied());
596        multi.skip(0x100);
597        multi.truncate(0x2f29);
598
599        let r1: Result<Vec<_>, _> = multi.paged_ranges().flat_map(|r| r.ranges()).collect();
600        let r2: Vec<_> = [
601            0x11223..0x12000,
602            0x22000..0x23000,
603            0x33000..0x33135,
604            0x111456..0x11246d,
605        ]
606        .map(AddressRange::from)
607        .to_vec();
608
609        assert_eq!(&r1.unwrap(), &r2);
610    }
611}
guestmem/ranges.rs

guestmem/
ranges.rs
