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