vm_memory/
address.rs

1// Copyright (C) 2019 Alibaba Cloud Computing. All rights reserved.
2//
3// Portions Copyright 2018 Amazon.com, Inc. or its affiliates. All Rights Reserved.
4//
5// Portions Copyright 2017 The Chromium OS Authors. All rights reserved.
6// Use of this source code is governed by a BSD-style license that can be
7// found in the LICENSE-BSD-3-Clause file.
8//
9// SPDX-License-Identifier: Apache-2.0 OR BSD-3-Clause
10
11//! Traits to represent an address within an address space.
12//!
13//! Two traits are defined to represent an address within an address space:
14//! - [`AddressValue`](trait.AddressValue.html): stores the raw value of an address. Typically
15//! `u32`,`u64` or `usize` is used to store the raw value. But pointers, such as `*u8`, can't be used
16//! because they don't implement the [`Add`](https://doc.rust-lang.org/std/ops/trait.Add.html) and
17//! [`Sub`](https://doc.rust-lang.org/std/ops/trait.Sub.html) traits.
18//! - [Address](trait.Address.html): encapsulates an [`AddressValue`](trait.AddressValue.html)
19//! object and defines methods to access and manipulate it.
20
21use std::cmp::{Eq, Ord, PartialEq, PartialOrd};
22use std::fmt::Debug;
23use std::ops::{Add, BitAnd, BitOr, Not, Sub};
24
25/// Simple helper trait used to store a raw address value.
26pub trait AddressValue {
27    /// Type of the raw address value.
28    type V: Copy
29        + PartialEq
30        + Eq
31        + PartialOrd
32        + Ord
33        + Not<Output = Self::V>
34        + Add<Output = Self::V>
35        + Sub<Output = Self::V>
36        + BitAnd<Output = Self::V>
37        + BitOr<Output = Self::V>
38        + Debug
39        + From<u8>;
40
41    /// Return the value zero, coerced into the value type `Self::V`
42    fn zero() -> Self::V {
43        0u8.into()
44    }
45
46    /// Return the value zero, coerced into the value type `Self::V`
47    fn one() -> Self::V {
48        1u8.into()
49    }
50}
51
52/// Trait to represent an address within an address space.
53///
54/// To simplify the design and implementation, assume the same raw data type `(AddressValue::V)`
55/// could be used to store address, size and offset for the address space. Thus the `Address` trait
56/// could be used to manage address, size and offset. On the other hand, type aliases may be
57/// defined to improve code readability.
58///
59/// One design rule is applied to the `Address` trait, namely that operators (+, -, &, | etc) are
60/// not supported and it forces clients to explicitly invoke corresponding methods. But there are
61/// always exceptions:
62///     `Address` (BitAnd|BitOr) `AddressValue` are supported.
63pub trait Address:
64    AddressValue
65    + Sized
66    + Default
67    + Copy
68    + Eq
69    + PartialEq
70    + Ord
71    + PartialOrd
72    + BitAnd<<Self as AddressValue>::V, Output = Self>
73    + BitOr<<Self as AddressValue>::V, Output = Self>
74{
75    /// Creates an address from a raw address value.
76    fn new(addr: Self::V) -> Self;
77
78    /// Returns the raw value of the address.
79    fn raw_value(&self) -> Self::V;
80
81    /// Returns the bitwise and of the address with the given mask.
82    fn mask(&self, mask: Self::V) -> Self::V {
83        self.raw_value() & mask
84    }
85
86    /// Computes the offset from this address to the given base address.
87    ///
88    /// Returns `None` if there is underflow.
89    fn checked_offset_from(&self, base: Self) -> Option<Self::V>;
90
91    /// Computes the offset from this address to the given base address.
92    ///
93    /// In the event of overflow, follows standard Rust behavior, i.e. panic in debug builds,
94    /// silently wrap in release builds.
95    ///
96    /// Note that, unlike the `unchecked_*` methods in std, this method never invokes undefined
97    /// behavior.
98    /// # Examples
99    ///
100    /// ```
101    /// # use vm_memory::{Address, GuestAddress};
102    /// #
103    /// let base = GuestAddress(0x100);
104    /// let addr = GuestAddress(0x150);
105    /// assert_eq!(addr.unchecked_offset_from(base), 0x50);
106    /// ```
107    fn unchecked_offset_from(&self, base: Self) -> Self::V {
108        self.raw_value() - base.raw_value()
109    }
110
111    /// Returns self, aligned to the given power of two.
112    fn checked_align_up(&self, power_of_two: Self::V) -> Option<Self> {
113        let mask = power_of_two - Self::one();
114        assert_ne!(power_of_two, Self::zero());
115        assert_eq!(power_of_two & mask, Self::zero());
116        self.checked_add(mask).map(|x| x & !mask)
117    }
118
119    /// Returns self, aligned to the given power of two.
120    /// Only use this when the result is guaranteed not to overflow.
121    fn unchecked_align_up(&self, power_of_two: Self::V) -> Self {
122        let mask = power_of_two - Self::one();
123        self.unchecked_add(mask) & !mask
124    }
125
126    /// Computes `self + other`, returning `None` if overflow occurred.
127    fn checked_add(&self, other: Self::V) -> Option<Self>;
128
129    /// Computes `self + other`.
130    ///
131    /// Returns a tuple of the addition result along with a boolean indicating whether an arithmetic
132    /// overflow would occur. If an overflow would have occurred then the wrapped address
133    /// is returned.
134    fn overflowing_add(&self, other: Self::V) -> (Self, bool);
135
136    /// Computes `self + offset`.
137    ///
138    /// In the event of overflow, follows standard Rust behavior, i.e. panic in debug builds,
139    /// silently wrap in release builds.
140    ///
141    /// Note that, unlike the `unchecked_*` methods in std, this method never invokes undefined
142    /// behavior..
143    fn unchecked_add(&self, offset: Self::V) -> Self;
144
145    /// Subtracts two addresses, checking for underflow. If underflow happens, `None` is returned.
146    fn checked_sub(&self, other: Self::V) -> Option<Self>;
147
148    /// Computes `self - other`.
149    ///
150    /// Returns a tuple of the subtraction result along with a boolean indicating whether an
151    /// arithmetic overflow would occur. If an overflow would have occurred then the wrapped
152    /// address is returned.
153    fn overflowing_sub(&self, other: Self::V) -> (Self, bool);
154
155    /// Computes `self - other`.
156    ///
157    /// In the event of underflow, follows standard Rust behavior, i.e. panic in debug builds,
158    /// silently wrap in release builds.
159    ///
160    /// Note that, unlike the `unchecked_*` methods in std, this method never invokes undefined
161    /// behavior.
162    fn unchecked_sub(&self, other: Self::V) -> Self;
163}
164
165macro_rules! impl_address_ops {
166    ($T:ident, $V:ty) => {
167        impl AddressValue for $T {
168            type V = $V;
169        }
170
171        impl Address for $T {
172            fn new(value: $V) -> $T {
173                $T(value)
174            }
175
176            fn raw_value(&self) -> $V {
177                self.0
178            }
179
180            fn checked_offset_from(&self, base: $T) -> Option<$V> {
181                self.0.checked_sub(base.0)
182            }
183
184            fn checked_add(&self, other: $V) -> Option<$T> {
185                self.0.checked_add(other).map($T)
186            }
187
188            fn overflowing_add(&self, other: $V) -> ($T, bool) {
189                let (t, ovf) = self.0.overflowing_add(other);
190                ($T(t), ovf)
191            }
192
193            fn unchecked_add(&self, offset: $V) -> $T {
194                $T(self.0 + offset)
195            }
196
197            fn checked_sub(&self, other: $V) -> Option<$T> {
198                self.0.checked_sub(other).map($T)
199            }
200
201            fn overflowing_sub(&self, other: $V) -> ($T, bool) {
202                let (t, ovf) = self.0.overflowing_sub(other);
203                ($T(t), ovf)
204            }
205
206            fn unchecked_sub(&self, other: $V) -> $T {
207                $T(self.0 - other)
208            }
209        }
210
211        impl Default for $T {
212            fn default() -> $T {
213                Self::new(0 as $V)
214            }
215        }
216
217        impl BitAnd<$V> for $T {
218            type Output = $T;
219
220            fn bitand(self, other: $V) -> $T {
221                $T(self.0 & other)
222            }
223        }
224
225        impl BitOr<$V> for $T {
226            type Output = $T;
227
228            fn bitor(self, other: $V) -> $T {
229                $T(self.0 | other)
230            }
231        }
232    };
233}
234
235#[cfg(test)]
236mod tests {
237    use super::*;
238
239    #[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
240    struct MockAddress(pub u64);
241    impl_address_ops!(MockAddress, u64);
242
243    #[test]
244    fn test_new() {
245        assert_eq!(MockAddress::new(0), MockAddress(0));
246        assert_eq!(MockAddress::new(std::u64::MAX), MockAddress(std::u64::MAX));
247    }
248
249    #[test]
250    fn test_offset_from() {
251        let base = MockAddress(0x100);
252        let addr = MockAddress(0x150);
253        assert_eq!(addr.unchecked_offset_from(base), 0x50u64);
254        assert_eq!(addr.checked_offset_from(base), Some(0x50u64));
255        assert_eq!(base.checked_offset_from(addr), None);
256    }
257
258    #[test]
259    fn test_equals() {
260        let a = MockAddress(0x300);
261        let b = MockAddress(0x300);
262        let c = MockAddress(0x301);
263        assert_eq!(a, MockAddress(a.raw_value()));
264        assert_eq!(a, b);
265        assert_eq!(b, a);
266        assert_ne!(a, c);
267        assert_ne!(c, a);
268    }
269
270    #[test]
271    fn test_cmp() {
272        let a = MockAddress(0x300);
273        let b = MockAddress(0x301);
274        assert!(a < b);
275    }
276
277    #[test]
278    fn test_checked_align_up() {
279        assert_eq!(
280            MockAddress::new(0x128).checked_align_up(8),
281            Some(MockAddress(0x128))
282        );
283        assert_eq!(
284            MockAddress::new(0x128).checked_align_up(16),
285            Some(MockAddress(0x130))
286        );
287        assert_eq!(
288            MockAddress::new(std::u64::MAX - 0x3fff).checked_align_up(0x10000),
289            None
290        );
291    }
292
293    #[test]
294    #[should_panic]
295    fn test_checked_align_up_invalid() {
296        let _ = MockAddress::new(0x128).checked_align_up(12);
297    }
298
299    #[test]
300    fn test_unchecked_align_up() {
301        assert_eq!(
302            MockAddress::new(0x128).unchecked_align_up(8),
303            MockAddress(0x128)
304        );
305        assert_eq!(
306            MockAddress::new(0x128).unchecked_align_up(16),
307            MockAddress(0x130)
308        );
309    }
310
311    #[test]
312    fn test_mask() {
313        let a = MockAddress(0x5050);
314        assert_eq!(MockAddress(0x5000), a & 0xff00u64);
315        assert_eq!(0x5000, a.mask(0xff00u64));
316        assert_eq!(MockAddress(0x5055), a | 0x0005u64);
317    }
318
319    fn check_add(a: u64, b: u64, expected_overflow: bool, expected_result: u64) {
320        assert_eq!(
321            (MockAddress(expected_result), expected_overflow),
322            MockAddress(a).overflowing_add(b)
323        );
324        if expected_overflow {
325            assert!(MockAddress(a).checked_add(b).is_none());
326            #[cfg(debug_assertions)]
327            assert!(std::panic::catch_unwind(|| MockAddress(a).unchecked_add(b)).is_err());
328        } else {
329            assert_eq!(
330                Some(MockAddress(expected_result)),
331                MockAddress(a).checked_add(b)
332            );
333            assert_eq!(
334                MockAddress(expected_result),
335                MockAddress(a).unchecked_add(b)
336            );
337        }
338    }
339
340    #[test]
341    fn test_add() {
342        // without overflow
343        // normal case
344        check_add(10, 10, false, 20);
345        // edge case
346        check_add(std::u64::MAX - 1, 1, false, std::u64::MAX);
347
348        // with overflow
349        check_add(std::u64::MAX, 1, true, 0);
350    }
351
352    fn check_sub(a: u64, b: u64, expected_overflow: bool, expected_result: u64) {
353        assert_eq!(
354            (MockAddress(expected_result), expected_overflow),
355            MockAddress(a).overflowing_sub(b)
356        );
357        if expected_overflow {
358            assert!(MockAddress(a).checked_sub(b).is_none());
359            assert!(MockAddress(a).checked_offset_from(MockAddress(b)).is_none());
360            #[cfg(debug_assertions)]
361            assert!(std::panic::catch_unwind(|| MockAddress(a).unchecked_sub(b)).is_err());
362        } else {
363            assert_eq!(
364                Some(MockAddress(expected_result)),
365                MockAddress(a).checked_sub(b)
366            );
367            assert_eq!(
368                Some(expected_result),
369                MockAddress(a).checked_offset_from(MockAddress(b))
370            );
371            assert_eq!(
372                MockAddress(expected_result),
373                MockAddress(a).unchecked_sub(b)
374            );
375        }
376    }
377
378    #[test]
379    fn test_sub() {
380        // without overflow
381        // normal case
382        check_sub(20, 10, false, 10);
383        // edge case
384        check_sub(1, 1, false, 0);
385
386        // with underflow
387        check_sub(0, 1, true, std::u64::MAX);
388    }
389
390    #[test]
391    fn test_default() {
392        assert_eq!(MockAddress::default(), MockAddress(0));
393    }
394
395    #[test]
396    fn test_bit_and() {
397        let a = MockAddress(0x0ff0);
398        assert_eq!(a & 0xf00f, MockAddress(0));
399    }
400
401    #[test]
402    fn test_bit_or() {
403        let a = MockAddress(0x0ff0);
404        assert_eq!(a | 0xf00f, MockAddress(0xffff));
405    }
406}
vm_memory/address.rs

vm_memory/
address.rs
