xref: /cloud-hypervisor/vm-allocator/src/address.rs (revision b686a5bb24f949e3b201308d69b01e85c14f1ad6)
1db7937d4SSamuel Ortiz // Copyright 2018 The Chromium OS Authors. All rights reserved.
2db7937d4SSamuel Ortiz // Copyright © 2019 Intel Corporation
3db7937d4SSamuel Ortiz //
4db7937d4SSamuel Ortiz // Portions Copyright 2017 The Chromium OS Authors. All rights reserved.
5db7937d4SSamuel Ortiz // Use of this source code is governed by a BSD-style license that can be
6040ea543SSamuel Ortiz // found in the LICENSE-BSD-3-Clause file.
7040ea543SSamuel Ortiz //
8040ea543SSamuel Ortiz // SPDX-License-Identifier: Apache-2.0 AND BSD-3-Clause
9db7937d4SSamuel Ortiz 
10db7937d4SSamuel Ortiz use std::collections::btree_map::BTreeMap;
11db7937d4SSamuel Ortiz use std::result;
1288a9f799SRob Bradford 
13db7937d4SSamuel Ortiz use vm_memory::{Address, GuestAddress, GuestUsize};
14db7937d4SSamuel Ortiz 
15db7937d4SSamuel Ortiz #[derive(Debug)]
16db7937d4SSamuel Ortiz pub enum Error {
17db7937d4SSamuel Ortiz     Overflow,
18db7937d4SSamuel Ortiz     Overlap,
19db7937d4SSamuel Ortiz     UnalignedAddress,
20db7937d4SSamuel Ortiz }
21db7937d4SSamuel Ortiz 
22db7937d4SSamuel Ortiz pub type Result<T> = result::Result<T, Error>;
23db7937d4SSamuel Ortiz 
24db7937d4SSamuel Ortiz /// Manages allocating address ranges.
25db7937d4SSamuel Ortiz /// Use `AddressAllocator` whenever an address range needs to be allocated to different users.
26db7937d4SSamuel Ortiz ///
27db7937d4SSamuel Ortiz /// # Examples
28db7937d4SSamuel Ortiz ///
29db7937d4SSamuel Ortiz /// ```
30db7937d4SSamuel Ortiz /// # use vm_allocator::AddressAllocator;
31db7937d4SSamuel Ortiz /// # use vm_memory::{Address, GuestAddress, GuestUsize};
3296fb38a5SChao Peng ///   AddressAllocator::new(GuestAddress(0x1000), 0x10000).map(|mut pool| {
3396fb38a5SChao Peng ///       assert_eq!(pool.allocate(None, 0x110, Some(0x100)), Some(GuestAddress(0x10e00)));
340ff074d2SSebastien Boeuf ///       assert_eq!(pool.allocate(None, 0x100, Some(0x100)), Some(GuestAddress(0x10d00)));
35db7937d4SSamuel Ortiz ///   });
36db7937d4SSamuel Ortiz /// ```
37db7937d4SSamuel Ortiz #[derive(Debug, Eq, PartialEq)]
38db7937d4SSamuel Ortiz pub struct AddressAllocator {
39db7937d4SSamuel Ortiz     base: GuestAddress,
40db7937d4SSamuel Ortiz     end: GuestAddress,
41db7937d4SSamuel Ortiz     ranges: BTreeMap<GuestAddress, GuestUsize>,
42db7937d4SSamuel Ortiz }
43db7937d4SSamuel Ortiz 
44db7937d4SSamuel Ortiz impl AddressAllocator {
45db7937d4SSamuel Ortiz     /// Creates a new `AddressAllocator` for managing a range of addresses.
4696fb38a5SChao Peng     /// Can return `None` if `base` + `size` overflows a u64.
47db7937d4SSamuel Ortiz     ///
4896fb38a5SChao Peng     /// * `base` - The starting address of the range to manage.
4996fb38a5SChao Peng     /// * `size` - The size of the address range in bytes.
new(base: GuestAddress, size: GuestUsize) -> Option<Self>5096fb38a5SChao Peng     pub fn new(base: GuestAddress, size: GuestUsize) -> Option<Self> {
51db7937d4SSamuel Ortiz         if size == 0 {
52db7937d4SSamuel Ortiz             return None;
53db7937d4SSamuel Ortiz         }
54db7937d4SSamuel Ortiz 
55db7937d4SSamuel Ortiz         let end = base.checked_add(size - 1)?;
56db7937d4SSamuel Ortiz 
57db7937d4SSamuel Ortiz         let mut allocator = AddressAllocator {
58db7937d4SSamuel Ortiz             base,
59db7937d4SSamuel Ortiz             end,
60db7937d4SSamuel Ortiz             ranges: BTreeMap::new(),
61db7937d4SSamuel Ortiz         };
62db7937d4SSamuel Ortiz 
63db7937d4SSamuel Ortiz         // Insert the last address as a zero size range.
64db7937d4SSamuel Ortiz         // This is our end of address space marker.
65db7937d4SSamuel Ortiz         allocator.ranges.insert(base.checked_add(size)?, 0);
66db7937d4SSamuel Ortiz 
67db7937d4SSamuel Ortiz         Some(allocator)
68db7937d4SSamuel Ortiz     }
69db7937d4SSamuel Ortiz 
align_address(&self, address: GuestAddress, alignment: GuestUsize) -> GuestAddress7096fb38a5SChao Peng     fn align_address(&self, address: GuestAddress, alignment: GuestUsize) -> GuestAddress {
7196fb38a5SChao Peng         let align_adjust = if address.raw_value() % alignment != 0 {
7296fb38a5SChao Peng             alignment - (address.raw_value() % alignment)
73db7937d4SSamuel Ortiz         } else {
74db7937d4SSamuel Ortiz             0
75db7937d4SSamuel Ortiz         };
76db7937d4SSamuel Ortiz 
77db7937d4SSamuel Ortiz         address.unchecked_add(align_adjust)
78db7937d4SSamuel Ortiz     }
79db7937d4SSamuel Ortiz 
available_range( &self, req_address: GuestAddress, req_size: GuestUsize, alignment: GuestUsize, ) -> Result<GuestAddress>80db7937d4SSamuel Ortiz     fn available_range(
81db7937d4SSamuel Ortiz         &self,
82db7937d4SSamuel Ortiz         req_address: GuestAddress,
83db7937d4SSamuel Ortiz         req_size: GuestUsize,
8496fb38a5SChao Peng         alignment: GuestUsize,
85db7937d4SSamuel Ortiz     ) -> Result<GuestAddress> {
8696fb38a5SChao Peng         let aligned_address = self.align_address(req_address, alignment);
87db7937d4SSamuel Ortiz 
88db7937d4SSamuel Ortiz         // The requested address should be aligned.
89db7937d4SSamuel Ortiz         if aligned_address != req_address {
90db7937d4SSamuel Ortiz             return Err(Error::UnalignedAddress);
91db7937d4SSamuel Ortiz         }
92db7937d4SSamuel Ortiz 
93db7937d4SSamuel Ortiz         // The aligned address should be within the address space range.
94a761b820SSebastien Boeuf         if aligned_address >= self.end || aligned_address < self.base {
95db7937d4SSamuel Ortiz             return Err(Error::Overflow);
96db7937d4SSamuel Ortiz         }
97db7937d4SSamuel Ortiz 
98db7937d4SSamuel Ortiz         let mut prev_end_address = self.base;
99db7937d4SSamuel Ortiz         for (address, size) in self.ranges.iter() {
100db7937d4SSamuel Ortiz             if aligned_address <= *address {
101db7937d4SSamuel Ortiz                 // Do we overlap with the previous range?
102db7937d4SSamuel Ortiz                 if prev_end_address > aligned_address {
103db7937d4SSamuel Ortiz                     return Err(Error::Overlap);
104db7937d4SSamuel Ortiz                 }
105db7937d4SSamuel Ortiz 
106db7937d4SSamuel Ortiz                 // Do we have enough space?
107db7937d4SSamuel Ortiz                 if address
108db7937d4SSamuel Ortiz                     .unchecked_sub(aligned_address.raw_value())
109db7937d4SSamuel Ortiz                     .raw_value()
110db7937d4SSamuel Ortiz                     < req_size
111db7937d4SSamuel Ortiz                 {
112db7937d4SSamuel Ortiz                     return Err(Error::Overlap);
113db7937d4SSamuel Ortiz                 }
114db7937d4SSamuel Ortiz 
115db7937d4SSamuel Ortiz                 return Ok(aligned_address);
116db7937d4SSamuel Ortiz             }
117db7937d4SSamuel Ortiz 
118db7937d4SSamuel Ortiz             prev_end_address = address.unchecked_add(*size);
119db7937d4SSamuel Ortiz         }
120db7937d4SSamuel Ortiz 
121db7937d4SSamuel Ortiz         // We have not found a range that starts after the requested address,
122db7937d4SSamuel Ortiz         // despite having a marker at the end of our range.
123db7937d4SSamuel Ortiz         Err(Error::Overflow)
124db7937d4SSamuel Ortiz     }
125db7937d4SSamuel Ortiz 
first_available_range( &self, req_size: GuestUsize, alignment: GuestUsize, ) -> Option<GuestAddress>12696fb38a5SChao Peng     fn first_available_range(
12796fb38a5SChao Peng         &self,
12896fb38a5SChao Peng         req_size: GuestUsize,
12996fb38a5SChao Peng         alignment: GuestUsize,
13096fb38a5SChao Peng     ) -> Option<GuestAddress> {
13170914880SSebastien Boeuf         let reversed_ranges: Vec<(&GuestAddress, &GuestUsize)> = self.ranges.iter().rev().collect();
132db7937d4SSamuel Ortiz 
13370914880SSebastien Boeuf         for (idx, (address, _size)) in reversed_ranges.iter().enumerate() {
13470914880SSebastien Boeuf             let next_range_idx = idx + 1;
13570914880SSebastien Boeuf             let prev_end_address = if next_range_idx >= reversed_ranges.len() {
13670914880SSebastien Boeuf                 self.base
13770914880SSebastien Boeuf             } else {
13870914880SSebastien Boeuf                 reversed_ranges[next_range_idx]
13970914880SSebastien Boeuf                     .0
14070914880SSebastien Boeuf                     .unchecked_add(*(reversed_ranges[next_range_idx].1))
14170914880SSebastien Boeuf             };
14270914880SSebastien Boeuf 
143db7937d4SSamuel Ortiz             // If we have enough space between this range and the previous one,
144db7937d4SSamuel Ortiz             // we return the start of this range minus the requested size.
145db7937d4SSamuel Ortiz             // As each new range is allocated at the end of the available address space,
146db7937d4SSamuel Ortiz             // we will tend to always allocate new ranges there as well. In other words,
147db7937d4SSamuel Ortiz             // ranges accumulate at the end of the address space.
14870914880SSebastien Boeuf             if let Some(size_delta) =
14970914880SSebastien Boeuf                 address.checked_sub(self.align_address(prev_end_address, alignment).raw_value())
150db7937d4SSamuel Ortiz             {
151*b686a5bbSJinank Jain                 let adjust = alignment.saturating_sub(1);
15270914880SSebastien Boeuf                 if size_delta.raw_value() >= req_size {
15396fb38a5SChao Peng                     return Some(
1540ff074d2SSebastien Boeuf                         self.align_address(address.unchecked_sub(req_size + adjust), alignment),
15596fb38a5SChao Peng                     );
156db7937d4SSamuel Ortiz                 }
15770914880SSebastien Boeuf             }
158db7937d4SSamuel Ortiz         }
159db7937d4SSamuel Ortiz 
160db7937d4SSamuel Ortiz         None
161db7937d4SSamuel Ortiz     }
162db7937d4SSamuel Ortiz 
163db7937d4SSamuel Ortiz     /// Allocates a range of addresses from the managed region. Returns `Some(allocated_address)`
16496fb38a5SChao Peng     /// when successful, or `None` if an area of `size` can't be allocated or if alignment isn't
16596fb38a5SChao Peng     /// a power of two.
allocate( &mut self, address: Option<GuestAddress>, size: GuestUsize, align_size: Option<GuestUsize>, ) -> Option<GuestAddress>166db7937d4SSamuel Ortiz     pub fn allocate(
167db7937d4SSamuel Ortiz         &mut self,
168db7937d4SSamuel Ortiz         address: Option<GuestAddress>,
169db7937d4SSamuel Ortiz         size: GuestUsize,
17096fb38a5SChao Peng         align_size: Option<GuestUsize>,
171db7937d4SSamuel Ortiz     ) -> Option<GuestAddress> {
172db7937d4SSamuel Ortiz         if size == 0 {
173db7937d4SSamuel Ortiz             return None;
174db7937d4SSamuel Ortiz         }
175db7937d4SSamuel Ortiz 
17696fb38a5SChao Peng         let alignment = align_size.unwrap_or(4);
17796fb38a5SChao Peng         if !alignment.is_power_of_two() || alignment == 0 {
17896fb38a5SChao Peng             return None;
17996fb38a5SChao Peng         }
18096fb38a5SChao Peng 
181db7937d4SSamuel Ortiz         let new_addr = match address {
18296fb38a5SChao Peng             Some(req_address) => match self.available_range(req_address, size, alignment) {
183db7937d4SSamuel Ortiz                 Ok(addr) => addr,
184db7937d4SSamuel Ortiz                 Err(_) => {
185db7937d4SSamuel Ortiz                     return None;
186db7937d4SSamuel Ortiz                 }
187db7937d4SSamuel Ortiz             },
18896fb38a5SChao Peng             None => self.first_available_range(size, alignment)?,
189db7937d4SSamuel Ortiz         };
190db7937d4SSamuel Ortiz 
191db7937d4SSamuel Ortiz         self.ranges.insert(new_addr, size);
192db7937d4SSamuel Ortiz 
193db7937d4SSamuel Ortiz         Some(new_addr)
194db7937d4SSamuel Ortiz     }
1954b451b01SSamuel Ortiz 
1964b451b01SSamuel Ortiz     /// Free an already allocated address range.
1974b451b01SSamuel Ortiz     /// We can only free a range if it matches exactly an already allocated range.
free(&mut self, address: GuestAddress, size: GuestUsize)1984b451b01SSamuel Ortiz     pub fn free(&mut self, address: GuestAddress, size: GuestUsize) {
1994b451b01SSamuel Ortiz         if let Some(&range_size) = self.ranges.get(&address) {
2004b451b01SSamuel Ortiz             if size == range_size {
2014b451b01SSamuel Ortiz                 self.ranges.remove(&address);
2024b451b01SSamuel Ortiz             }
2034b451b01SSamuel Ortiz         }
2044b451b01SSamuel Ortiz     }
205a6456b50SRob Bradford 
206a6456b50SRob Bradford     /// Start address of the allocator
base(&self) -> GuestAddress207a6456b50SRob Bradford     pub fn base(&self) -> GuestAddress {
208a6456b50SRob Bradford         self.base
209a6456b50SRob Bradford     }
210a6456b50SRob Bradford 
211a6456b50SRob Bradford     /// Last address of the allocator
end(&self) -> GuestAddress212a6456b50SRob Bradford     pub fn end(&self) -> GuestAddress {
213a6456b50SRob Bradford         self.end
214a6456b50SRob Bradford     }
215db7937d4SSamuel Ortiz }
216db7937d4SSamuel Ortiz 
217db7937d4SSamuel Ortiz #[cfg(test)]
218db7937d4SSamuel Ortiz mod tests {
219db7937d4SSamuel Ortiz     use super::*;
220db7937d4SSamuel Ortiz 
221db7937d4SSamuel Ortiz     #[test]
new_fails_overflow()222db7937d4SSamuel Ortiz     fn new_fails_overflow() {
223f6cd3bd8SWei Liu         assert_eq!(AddressAllocator::new(GuestAddress(u64::MAX), 0x100), None);
224db7937d4SSamuel Ortiz     }
225db7937d4SSamuel Ortiz 
226db7937d4SSamuel Ortiz     #[test]
new_fails_size_zero()227db7937d4SSamuel Ortiz     fn new_fails_size_zero() {
22896fb38a5SChao Peng         assert_eq!(AddressAllocator::new(GuestAddress(0x1000), 0), None);
229db7937d4SSamuel Ortiz     }
230db7937d4SSamuel Ortiz 
231db7937d4SSamuel Ortiz     #[test]
allocate_fails_alignment_zero()23296fb38a5SChao Peng     fn allocate_fails_alignment_zero() {
23396fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x10000).unwrap();
234db7937d4SSamuel Ortiz         assert_eq!(
23596fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1000)), 0x100, Some(0)),
236db7937d4SSamuel Ortiz             None
237db7937d4SSamuel Ortiz         );
238db7937d4SSamuel Ortiz     }
239db7937d4SSamuel Ortiz 
240db7937d4SSamuel Ortiz     #[test]
allocate_fails_alignment_non_power_of_two()24196fb38a5SChao Peng     fn allocate_fails_alignment_non_power_of_two() {
24296fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x10000).unwrap();
243db7937d4SSamuel Ortiz         assert_eq!(
24496fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1000)), 0x100, Some(200)),
245db7937d4SSamuel Ortiz             None
246db7937d4SSamuel Ortiz         );
247db7937d4SSamuel Ortiz     }
248db7937d4SSamuel Ortiz 
249db7937d4SSamuel Ortiz     #[test]
allocate_fails_not_enough_space()250db7937d4SSamuel Ortiz     fn allocate_fails_not_enough_space() {
25196fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x1000).unwrap();
25296fb38a5SChao Peng         assert_eq!(
25396fb38a5SChao Peng             pool.allocate(None, 0x800, Some(0x100)),
2540ff074d2SSebastien Boeuf             Some(GuestAddress(0x1800))
25596fb38a5SChao Peng         );
25696fb38a5SChao Peng         assert_eq!(pool.allocate(None, 0x900, Some(0x100)), None);
25796fb38a5SChao Peng         assert_eq!(
25896fb38a5SChao Peng             pool.allocate(None, 0x400, Some(0x100)),
2590ff074d2SSebastien Boeuf             Some(GuestAddress(0x1400))
26096fb38a5SChao Peng         );
261db7937d4SSamuel Ortiz     }
262db7937d4SSamuel Ortiz 
263db7937d4SSamuel Ortiz     #[test]
allocate_alignment()264db7937d4SSamuel Ortiz     fn allocate_alignment() {
26596fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x10000).unwrap();
26696fb38a5SChao Peng         assert_eq!(
26796fb38a5SChao Peng             pool.allocate(None, 0x110, Some(0x100)),
26896fb38a5SChao Peng             Some(GuestAddress(0x10e00))
26996fb38a5SChao Peng         );
27096fb38a5SChao Peng         assert_eq!(
27196fb38a5SChao Peng             pool.allocate(None, 0x100, Some(0x100)),
2720ff074d2SSebastien Boeuf             Some(GuestAddress(0x10d00))
27396fb38a5SChao Peng         );
27496fb38a5SChao Peng         assert_eq!(
27596fb38a5SChao Peng             pool.allocate(None, 0x10, Some(0x100)),
2760ff074d2SSebastien Boeuf             Some(GuestAddress(0x10c00))
27796fb38a5SChao Peng         );
278db7937d4SSamuel Ortiz     }
279db7937d4SSamuel Ortiz 
280db7937d4SSamuel Ortiz     #[test]
allocate_address()281db7937d4SSamuel Ortiz     fn allocate_address() {
28296fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x1000).unwrap();
283db7937d4SSamuel Ortiz         assert_eq!(
28496fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x800, None),
285db7937d4SSamuel Ortiz             Some(GuestAddress(0x1200))
286db7937d4SSamuel Ortiz         );
287db7937d4SSamuel Ortiz 
288db7937d4SSamuel Ortiz         assert_eq!(
28996fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1a00)), 0x100, None),
290db7937d4SSamuel Ortiz             Some(GuestAddress(0x1a00))
291db7937d4SSamuel Ortiz         );
292db7937d4SSamuel Ortiz     }
293db7937d4SSamuel Ortiz 
294db7937d4SSamuel Ortiz     #[test]
allocate_address_alignment()295db7937d4SSamuel Ortiz     fn allocate_address_alignment() {
29696fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x1000).unwrap();
297db7937d4SSamuel Ortiz         assert_eq!(
29896fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x800, Some(0x100)),
299db7937d4SSamuel Ortiz             Some(GuestAddress(0x1200))
300db7937d4SSamuel Ortiz         );
301db7937d4SSamuel Ortiz 
302db7937d4SSamuel Ortiz         // Unaligned request
30396fb38a5SChao Peng         assert_eq!(
30496fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1210)), 0x800, Some(0x100)),
30596fb38a5SChao Peng             None
30696fb38a5SChao Peng         );
307db7937d4SSamuel Ortiz 
308db7937d4SSamuel Ortiz         // Aligned request
309db7937d4SSamuel Ortiz         assert_eq!(
31096fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1b00)), 0x100, Some(0x100)),
311db7937d4SSamuel Ortiz             Some(GuestAddress(0x1b00))
312db7937d4SSamuel Ortiz         );
313db7937d4SSamuel Ortiz     }
314db7937d4SSamuel Ortiz 
315db7937d4SSamuel Ortiz     #[test]
allocate_address_not_enough_space()316db7937d4SSamuel Ortiz     fn allocate_address_not_enough_space() {
31796fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x1000).unwrap();
318db7937d4SSamuel Ortiz 
319db7937d4SSamuel Ortiz         // First range is [0x1200:0x1a00]
320db7937d4SSamuel Ortiz         assert_eq!(
32196fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x800, Some(0x100)),
322db7937d4SSamuel Ortiz             Some(GuestAddress(0x1200))
323db7937d4SSamuel Ortiz         );
324db7937d4SSamuel Ortiz 
325db7937d4SSamuel Ortiz         // Second range is [0x1c00:0x1e00]
326db7937d4SSamuel Ortiz         assert_eq!(
32796fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1c00)), 0x200, Some(0x100)),
328db7937d4SSamuel Ortiz             Some(GuestAddress(0x1c00))
329db7937d4SSamuel Ortiz         );
330db7937d4SSamuel Ortiz 
331db7937d4SSamuel Ortiz         // There is 0x200 between the first 2 ranges.
332db7937d4SSamuel Ortiz         // We ask for an available address but the range is too big
33396fb38a5SChao Peng         assert_eq!(
33496fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1b00)), 0x800, Some(0x100)),
33596fb38a5SChao Peng             None
33696fb38a5SChao Peng         );
337db7937d4SSamuel Ortiz 
338db7937d4SSamuel Ortiz         // We ask for an available address, with a small enough range
339db7937d4SSamuel Ortiz         assert_eq!(
34096fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1b00)), 0x100, Some(0x100)),
341db7937d4SSamuel Ortiz             Some(GuestAddress(0x1b00))
342db7937d4SSamuel Ortiz         );
343db7937d4SSamuel Ortiz     }
3444b451b01SSamuel Ortiz 
3454b451b01SSamuel Ortiz     #[test]
allocate_address_free_and_realloc()3464b451b01SSamuel Ortiz     fn allocate_address_free_and_realloc() {
34796fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x1000).unwrap();
3484b451b01SSamuel Ortiz 
3494b451b01SSamuel Ortiz         // First range is [0x1200:0x1a00]
3504b451b01SSamuel Ortiz         assert_eq!(
35196fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x800, Some(0x100)),
3524b451b01SSamuel Ortiz             Some(GuestAddress(0x1200))
3534b451b01SSamuel Ortiz         );
3544b451b01SSamuel Ortiz 
3554b451b01SSamuel Ortiz         pool.free(GuestAddress(0x1200), 0x800);
3564b451b01SSamuel Ortiz 
3574b451b01SSamuel Ortiz         assert_eq!(
35896fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x800, Some(0x100)),
3594b451b01SSamuel Ortiz             Some(GuestAddress(0x1200))
3604b451b01SSamuel Ortiz         );
3614b451b01SSamuel Ortiz     }
3624b451b01SSamuel Ortiz 
3634b451b01SSamuel Ortiz     #[test]
allocate_address_free_fail_and_realloc()3644b451b01SSamuel Ortiz     fn allocate_address_free_fail_and_realloc() {
36596fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x1000).unwrap();
3664b451b01SSamuel Ortiz 
3674b451b01SSamuel Ortiz         // First range is [0x1200:0x1a00]
3684b451b01SSamuel Ortiz         assert_eq!(
36996fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x800, Some(0x100)),
3704b451b01SSamuel Ortiz             Some(GuestAddress(0x1200))
3714b451b01SSamuel Ortiz         );
3724b451b01SSamuel Ortiz 
3734b451b01SSamuel Ortiz         // We try to free a range smaller than the allocated one.
3744b451b01SSamuel Ortiz         pool.free(GuestAddress(0x1200), 0x100);
3754b451b01SSamuel Ortiz 
37696fb38a5SChao Peng         assert_eq!(
37796fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x800, Some(0x100)),
37896fb38a5SChao Peng             None
37996fb38a5SChao Peng         );
3804b451b01SSamuel Ortiz     }
3814b451b01SSamuel Ortiz 
3824b451b01SSamuel Ortiz     #[test]
allocate_address_fail_free_and_realloc()3834b451b01SSamuel Ortiz     fn allocate_address_fail_free_and_realloc() {
38496fb38a5SChao Peng         let mut pool = AddressAllocator::new(GuestAddress(0x1000), 0x1000).unwrap();
3854b451b01SSamuel Ortiz 
3864b451b01SSamuel Ortiz         // First allocation fails
38796fb38a5SChao Peng         assert_eq!(
38896fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x2000, Some(0x100)),
38996fb38a5SChao Peng             None
39096fb38a5SChao Peng         );
3914b451b01SSamuel Ortiz 
3924b451b01SSamuel Ortiz         // We try to free a range that was not allocated.
3934b451b01SSamuel Ortiz         pool.free(GuestAddress(0x1200), 0x2000);
3944b451b01SSamuel Ortiz 
3954b451b01SSamuel Ortiz         // Now we try an allocation that should succeed.
3964b451b01SSamuel Ortiz         assert_eq!(
39796fb38a5SChao Peng             pool.allocate(Some(GuestAddress(0x1200)), 0x800, Some(0x100)),
3984b451b01SSamuel Ortiz             Some(GuestAddress(0x1200))
3994b451b01SSamuel Ortiz         );
4004b451b01SSamuel Ortiz     }
401db7937d4SSamuel Ortiz }
402