1 //! Memory blocks. 2 //! 3 //! Blocks are the main unit for the memory bookkeeping. A block is a simple construct with a 4 //! `Pointer` pointer and a size. Occupied (non-free) blocks are represented by a zero-sized block. 5 6 // TODO: Check the allow(cast_possible_wrap)s again. 7 8 use prelude::*; 9 10 use {sys, fail}; 11 12 use core::{ptr, cmp, mem, fmt}; 13 14 /// A contiguous memory block. 15 /// 16 /// This provides a number of guarantees, 17 /// 18 /// 1. The buffer is valid for the block's lifetime, but not necessarily initialized. 19 /// 2. The Block "owns" the inner data. 20 /// 3. There is no interior mutability. Mutation requires either mutable access or ownership over 21 /// the block. 22 /// 4. The buffer is not aliased. That is, it do not overlap with other blocks or is aliased in any 23 /// way. 24 /// 25 /// All this is enforced through the type system. These invariants can only be broken through 26 /// unsafe code. 27 /// 28 /// Accessing it through an immutable reference does not break these guarantees. That is, you are 29 /// not able to read/mutate without acquiring a _mutable_ reference. 30 #[must_use] 31 pub struct Block { 32 /// The size of this block, in bytes. 33 size: usize, 34 /// The pointer to the start of this block. 35 ptr: Pointer<u8>, 36 } 37 38 impl Block { 39 /// Construct a block from its raw parts (pointer and size). 40 #[inline] 41 pub unsafe fn from_raw_parts(ptr: Pointer<u8>, size: usize) -> Block { 42 Block { 43 size: size, 44 ptr: ptr, 45 } 46 } 47 48 /// BRK allocate a block. 49 #[inline] 50 #[allow(cast_possible_wrap)] 51 pub fn brk(size: usize) -> Block { 52 Block { 53 size: size, 54 ptr: unsafe { 55 Pointer::new(sys::sbrk(size as isize).unwrap_or_else(|()| fail::oom())) 56 }, 57 } 58 } 59 60 /// Create an empty block starting at `ptr`. 61 #[inline] 62 pub fn empty(ptr: Pointer<u8>) -> Block { 63 Block { 64 size: 0, 65 // This won't alias `ptr`, since the block is empty. 66 ptr: unsafe { Pointer::new(*ptr) }, 67 } 68 } 69 70 /// Create an empty block representing the left edge of this block 71 #[inline] 72 pub fn empty_left(&self) -> Block { 73 Block { 74 size: 0, 75 ptr: unsafe { Pointer::new(*self.ptr) }, 76 } 77 } 78 79 /// Create an empty block representing the right edge of this block 80 #[inline] 81 #[allow(cast_possible_wrap)] 82 pub fn empty_right(&self) -> Block { 83 Block { 84 size: 0, 85 ptr: unsafe { 86 // By the invariants of this type (the end is addressable), this conversion isn't 87 // overflowing. 88 Pointer::new(*self.ptr).offset(self.size as isize) 89 }, 90 } 91 } 92 93 /// Merge this block with a block to the right. 94 /// 95 /// This will simply extend the block, adding the size of the block, and then set the size to 96 /// zero. The return value is `Ok(())` on success, and `Err(())` on failure (e.g., the blocks 97 /// are not adjacent). 98 /// 99 /// If you merge with a zero sized block, it will succeed, even if they are not adjacent. 100 #[inline] 101 pub fn merge_right(&mut self, block: &mut Block) -> Result<(), ()> { 102 if block.is_empty() { 103 Ok(()) 104 } else if self.left_to(block) { 105 // Since the end of `block` is bounded by the address space, adding them cannot 106 // overflow. 107 self.size += block.pop().size; 108 // We pop it to make sure it isn't aliased. 109 110 Ok(()) 111 } else { Err(()) } 112 } 113 114 /// Is this block empty/free? 115 #[inline] 116 pub fn is_empty(&self) -> bool { 117 self.size == 0 118 } 119 120 /// Get the size of the block. 121 pub fn size(&self) -> usize { 122 self.size 123 } 124 125 /// Is this block aligned to `align`? 126 #[inline] 127 pub fn aligned_to(&self, align: usize) -> bool { 128 *self.ptr as usize % align == 0 129 } 130 131 /// memcpy the block to another pointer. 132 /// 133 /// # Panics 134 /// 135 /// This will panic if the target block is smaller than the source. 136 #[inline] 137 pub fn copy_to(&self, block: &mut Block) { 138 // Bound check. 139 assert!(self.size <= block.size, "Block too small."); 140 141 unsafe { 142 ptr::copy_nonoverlapping(*self.ptr, *block.ptr, self.size); 143 } 144 } 145 146 /// Volatile zero this memory. 147 pub fn sec_zero(&mut self) { 148 use core::intrinsics; 149 150 if cfg!(feature = "security") { 151 unsafe { 152 intrinsics::volatile_set_memory(*self.ptr, 0, self.size); 153 } 154 } 155 } 156 157 /// "Pop" this block. 158 /// 159 /// This marks it as free, and returns the old value. 160 #[inline] 161 pub fn pop(&mut self) -> Block { 162 unborrow!(mem::replace(self, Block::empty(self.ptr.clone()))) 163 } 164 165 /// Is this block placed left to the given other block? 166 #[inline] 167 pub fn left_to(&self, to: &Block) -> bool { 168 // This won't overflow due to the end being bounded by the address space. 169 self.size + *self.ptr as usize == *to.ptr as usize 170 } 171 172 /// Split the block at some position. 173 /// 174 /// # Panics 175 /// 176 /// Panics if `pos` is out of bound. 177 #[inline] 178 #[allow(cast_possible_wrap)] 179 pub fn split(self, pos: usize) -> (Block, Block) { 180 assert!(pos <= self.size, "Split {} out of bound (size is {})!", pos, self.size); 181 182 ( 183 Block { 184 size: pos, 185 ptr: self.ptr.clone(), 186 }, 187 Block { 188 size: self.size - pos, 189 ptr: unsafe { 190 // This won't overflow due to the assertion above, ensuring that it is bounded 191 // by the address space. See the `split_at_mut` source from libcore. 192 self.ptr.offset(pos as isize) 193 }, 194 } 195 ) 196 } 197 198 /// Split this block, such that the second block is aligned to `align`. 199 /// 200 /// Returns an `None` holding the intact block if `align` is out of bounds. 201 #[inline] 202 #[allow(cast_possible_wrap)] 203 pub fn align(&mut self, align: usize) -> Option<(Block, Block)> { 204 // Calculate the aligner, which defines the smallest size required as precursor to align 205 // the block to `align`. 206 let aligner = (align - *self.ptr as usize % align) % align; 207 // ^^^^^^^^ 208 // To avoid wasting space on the case where the block is already aligned, we calculate it 209 // modulo `align`. 210 211 // Bound check. 212 if aligner < self.size { 213 // Invalidate the old block. 214 let old = self.pop(); 215 216 Some(( 217 Block { 218 size: aligner, 219 ptr: old.ptr.clone(), 220 }, 221 Block { 222 size: old.size - aligner, 223 ptr: unsafe { 224 // The aligner is bounded by the size, which itself is bounded by the 225 // address space. Therefore, this conversion cannot overflow. 226 old.ptr.offset(aligner as isize) 227 }, 228 } 229 )) 230 } else { None } 231 } 232 } 233 234 impl From<Block> for Pointer<u8> { 235 fn from(from: Block) -> Pointer<u8> { 236 from.ptr 237 } 238 } 239 240 /// Compare the blocks address. 241 impl PartialOrd for Block { 242 #[inline] 243 fn partial_cmp(&self, other: &Block) -> Option<cmp::Ordering> { 244 self.ptr.partial_cmp(&other.ptr) 245 } 246 } 247 248 /// Compare the blocks address. 249 impl Ord for Block { 250 #[inline] 251 fn cmp(&self, other: &Block) -> cmp::Ordering { 252 self.ptr.cmp(&other.ptr) 253 } 254 } 255 256 impl cmp::PartialEq for Block { 257 #[inline] 258 fn eq(&self, other: &Block) -> bool { 259 *self.ptr == *other.ptr 260 } 261 } 262 263 impl cmp::Eq for Block {} 264 265 impl fmt::Debug for Block { 266 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 267 write!(f, "0x{:x}[{}]", *self.ptr as usize, self.size) 268 } 269 } 270 271 #[cfg(test)] 272 mod test { 273 use prelude::*; 274 275 #[test] 276 fn test_array() { 277 let arr = b"Lorem ipsum dolor sit amet"; 278 let block = unsafe { 279 Block::from_raw_parts(Pointer::new(arr.as_ptr() as *mut u8), arr.len()) 280 }; 281 282 // Test split. 283 let (mut lorem, mut rest) = block.split(5); 284 assert_eq!(lorem.size(), 5); 285 assert_eq!(lorem.size() + rest.size(), arr.len()); 286 assert!(lorem < rest); 287 288 assert_eq!(lorem, lorem); 289 assert!(!rest.is_empty()); 290 assert!(lorem.align(2).unwrap().1.aligned_to(2)); 291 assert!(rest.align(15).unwrap().1.aligned_to(15)); 292 assert_eq!(*Pointer::from(lorem) as usize + 5, *Pointer::from(rest) as usize); 293 } 294 295 #[test] 296 fn test_merge() { 297 let arr = b"Lorem ipsum dolor sit amet"; 298 let block = unsafe { 299 Block::from_raw_parts(Pointer::new(arr.as_ptr() as *mut u8), arr.len()) 300 }; 301 302 let (mut lorem, mut rest) = block.split(5); 303 lorem.merge_right(&mut rest).unwrap(); 304 305 let mut tmp = rest.split(0).0; 306 assert!(tmp.is_empty()); 307 lorem.split(2).0.merge_right(&mut tmp).unwrap(); 308 } 309 310 #[test] 311 #[should_panic] 312 fn test_oob() { 313 let arr = b"lorem"; 314 let block = unsafe { 315 Block::from_raw_parts(Pointer::new(arr.as_ptr() as *mut u8), arr.len()) 316 }; 317 318 // Test OOB. 319 block.split(6); 320 } 321 322 #[test] 323 fn test_mutate() { 324 let mut arr = [0u8, 2, 0, 0, 255, 255]; 325 326 let block = unsafe { 327 Block::from_raw_parts(Pointer::new(&mut arr[0] as *mut u8), 6) 328 }; 329 330 let (a, mut b) = block.split(2); 331 a.copy_to(&mut b); 332 333 assert_eq!(arr, [0, 2, 0, 2, 255, 255]); 334 } 335 336 #[test] 337 fn test_empty_lr() { 338 let arr = b"Lorem ipsum dolor sit amet"; 339 let block = unsafe { 340 Block::from_raw_parts(Pointer::new(arr.as_ptr() as *mut u8), arr.len()) 341 }; 342 343 assert!(block.empty_left().is_empty()); 344 assert!(block.empty_right().is_empty()); 345 assert_eq!(*Pointer::from(block.empty_left()) as *const u8, arr.as_ptr()); 346 assert_eq!(block.empty_right(), block.split(arr.len()).1); 347 } 348 349 #[test] 350 fn test_brk_grow_up() { 351 let brk1 = Block::brk(5); 352 let brk2 = Block::brk(100); 353 354 assert!(brk1 < brk2); 355 } 356 } 357