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

guestmem/
ranges.rs
