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 /// Mark this block free to the debugger. 234 /// 235 /// The debugger might do things like memleak and use-after-free checks. This methods informs 236 /// the debugger that this block is freed. 237 #[inline] 238 pub fn mark_free(self) -> Block { 239 sys::mark_free(*self.ptr as *const u8, self.size); 240 241 self 242 } 243 244 /// Mark this block uninitialized to the debugger. 245 /// 246 /// To detect use-after-free, the allocator need to mark 247 #[inline] 248 pub fn mark_uninitialized(self) -> Block { 249 sys::mark_uninitialized(*self.ptr as *const u8, self.size); 250 251 self 252 } 253 } 254 255 impl From<Block> for Pointer<u8> { 256 fn from(from: Block) -> Pointer<u8> { 257 from.ptr 258 } 259 } 260 261 /// Compare the blocks address. 262 impl PartialOrd for Block { 263 #[inline] 264 fn partial_cmp(&self, other: &Block) -> Option<cmp::Ordering> { 265 self.ptr.partial_cmp(&other.ptr) 266 } 267 } 268 269 /// Compare the blocks address. 270 impl Ord for Block { 271 #[inline] 272 fn cmp(&self, other: &Block) -> cmp::Ordering { 273 self.ptr.cmp(&other.ptr) 274 } 275 } 276 277 impl cmp::PartialEq for Block { 278 #[inline] 279 fn eq(&self, other: &Block) -> bool { 280 *self.ptr == *other.ptr 281 } 282 } 283 284 impl cmp::Eq for Block {} 285 286 impl fmt::Debug for Block { 287 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 288 write!(f, "0x{:x}[{}]", *self.ptr as usize, self.size) 289 } 290 } 291 292 #[cfg(test)] 293 mod test { 294 use prelude::*; 295 296 #[test] 297 fn test_array() { 298 let arr = b"Lorem ipsum dolor sit amet"; 299 let block = unsafe { 300 Block::from_raw_parts(Pointer::new(arr.as_ptr() as *mut u8), arr.len()) 301 }; 302 303 // Test split. 304 let (mut lorem, mut rest) = block.split(5); 305 assert_eq!(lorem.size(), 5); 306 assert_eq!(lorem.size() + rest.size(), arr.len()); 307 assert!(lorem < rest); 308 309 assert_eq!(lorem, lorem); 310 assert!(!rest.is_empty()); 311 assert!(lorem.align(2).unwrap().1.aligned_to(2)); 312 assert!(rest.align(15).unwrap().1.aligned_to(15)); 313 assert_eq!(*Pointer::from(lorem) as usize + 5, *Pointer::from(rest) as usize); 314 } 315 316 #[test] 317 fn test_merge() { 318 let arr = b"Lorem ipsum dolor sit amet"; 319 let block = unsafe { 320 Block::from_raw_parts(Pointer::new(arr.as_ptr() as *mut u8), arr.len()) 321 }; 322 323 let (mut lorem, mut rest) = block.split(5); 324 lorem.merge_right(&mut rest).unwrap(); 325 326 let mut tmp = rest.split(0).0; 327 assert!(tmp.is_empty()); 328 lorem.split(2).0.merge_right(&mut tmp).unwrap(); 329 } 330 331 #[test] 332 #[should_panic] 333 fn test_oob() { 334 let arr = b"lorem"; 335 let block = unsafe { 336 Block::from_raw_parts(Pointer::new(arr.as_ptr() as *mut u8), arr.len()) 337 }; 338 339 // Test OOB. 340 block.split(6); 341 } 342 343 #[test] 344 fn test_mutate() { 345 let mut arr = [0u8, 2, 0, 0, 255, 255]; 346 347 let block = unsafe { 348 Block::from_raw_parts(Pointer::new(&mut arr[0] as *mut u8), 6) 349 }; 350 351 let (a, mut b) = block.split(2); 352 a.copy_to(&mut b); 353 354 assert_eq!(arr, [0, 2, 0, 2, 255, 255]); 355 } 356 357 #[test] 358 fn test_empty_lr() { 359 let arr = b"Lorem ipsum dolor sit amet"; 360 let block = unsafe { 361 Block::from_raw_parts(Pointer::new(arr.as_ptr() as *mut u8), arr.len()) 362 }; 363 364 assert!(block.empty_left().is_empty()); 365 assert!(block.empty_right().is_empty()); 366 assert_eq!(*Pointer::from(block.empty_left()) as *const u8, arr.as_ptr()); 367 assert_eq!(block.empty_right(), block.split(arr.len()).1); 368 } 369 370 #[test] 371 fn test_brk_grow_up() { 372 let brk1 = Block::brk(5); 373 let brk2 = Block::brk(100); 374 375 assert!(brk1 < brk2); 376 } 377 } 378