14b65baa3Sticki# ralloc 26c5a0b16Sticki 36e3426f3StickiA fast & memory efficient userspace allocator. 46e3426f3Sticki 56e3426f3StickiThis allocator is used as the default Redox. 64b65baa3Sticki 7fc19fb6dSticki## A note on its state. 8fc19fb6dSticki 9829bb37fSEdwin AmslerIt fully works, although it is somewhat slower than jemalloc, since it hasn't 10ab47feeaStickibeen optimized yet. 11fc19fb6dSticki 12fc19fb6dStickiI consider the state of the code quality very good. 13fc19fb6dSticki 146e3426f3Sticki## Platforms supported out-of-the-box 156e3426f3Sticki 166e3426f3Sticki- [x] BSD 176e3426f3Sticki- [x] Linux 18*342e9023SLuca Barbato- [ ] Mac OS X 196e3426f3Sticki- [x] Redox 206e3426f3Sticki- [ ] Windows 216e3426f3Sticki 227f66ee45Sticki## Using ralloc 237f66ee45Sticki 24e081fde1StickiMake sure you have Rust nightly. 25b7c1f1bfSticki 266e3426f3StickiAdd `ralloc` to `Cargo.toml`: 277f66ee45Sticki 287f66ee45Sticki```toml 297f66ee45Sticki[dependencies.ralloc] 307f66ee45Stickigit = "https://github.com/redox-os/ralloc.git" 317f66ee45Sticki``` 327f66ee45Sticki 337f66ee45Stickithen import it in your main file: 347f66ee45Sticki 357f66ee45Sticki```rust 367f66ee45Stickiextern crate ralloc; 377f66ee45Sticki``` 387f66ee45Sticki 396e3426f3Sticki`ralloc` is now ready to roll! 407f66ee45Sticki 416e3426f3StickiNote that `ralloc` cannot coexist with another allocator, unless they're deliberately compatible. 42fc19fb6dSticki 434b65baa3Sticki## Features 444b65baa3Sticki 45cdec4b0eSticki### Thread-local allocation 46cdec4b0eSticki 47cdec4b0eStickiRalloc makes use of a global-local model allowing one to allocate or deallocate 480f78e690SBruce Mitchenerwithout locks, synchronization, or atomic writes. This provides reasonable 49cdec4b0eStickiperformance, while preserving flexibility and ability to multithread. 50cdec4b0eSticki 51b7c1f1bfSticki### First-class debugger (default: valgrind) support 52b7c1f1bfSticki 53b7c1f1bfSticki`ralloc` gives data to two debugger symbols specified in `ralloc_shim`, when 54b7c1f1bfStickithe `debugger` feature is enabled. The default `shim` implementation is wired 55b7c1f1bfStickito `valgrind`, which can thus be used with `ralloc` to detect memory leaks and 56b7c1f1bfStickiuninitialized use out-of-the-box. 57b7c1f1bfSticki 582c55fb11Sticki### Everything is customizable 592c55fb11Sticki 602c55fb11StickiYou can configure, tweak, and customize almost everything in `ralloc`. By 612c55fb11Stickichanging the `shim` module, this is easily achieved. 622c55fb11Sticki 632c55fb11StickiFor example, you can change the reallocation strategy, the memtrim limits, the 642c55fb11Stickilog target, and so on. 652c55fb11Sticki 662c55fb11Sticki### Logging 672c55fb11Sticki 682c55fb11StickiIf you enable the `log` feature, you get detailed logging of the allocator, e.g. 692c55fb11Sticki 702c55fb11Sticki``` 712c55fb11Sticki| : BRK'ing a block of size, 80, and alignment 8. (at bookkeeper.rs:458) 722c55fb11Sticki| : Pushing 0x5578dacb2000[0x0] and 0x5578dacb2050[0xffb8]. (at bookkeeper.rs:490) 732c55fb11Sticki|x : Freeing 0x1[0x0]. (at bookkeeper.rs:409) 742c55fb11Stickix| : BRK'ing a block of size, 4, and alignment 1. (at bookkeeper.rs:458) 752c55fb11Stickix| : Pushing 0x5578dacc2008[0x0] and 0x5578dacc200c[0xfffd]. (at bookkeeper.rs:490) 762c55fb11Stickix|x : Reallocating 0x5578dacc2008[0x4] to size 8 with align 1. (at bookkeeper.rs:272) 772c55fb11Stickix|x : Inplace reallocating 0x5578dacc2008[0x4] to size 8. (at bookkeeper.rs:354) 782c55fb11Sticki_|x : Freeing 0x5578dacb2058[0xffb0]. (at bookkeeper.rs:409) 792c55fb11Sticki_|x : Inserting block 0x5578dacb2058[0xffb0]. (at bookkeeper.rs:635) 802c55fb11Sticki``` 812c55fb11Sticki 822c55fb11StickiTo the left, you can see the state of the block pool. `x` denotes a non-empty 832c55fb11Stickiblock, `_` denotes an empty block, and `|` denotes the cursor. 842c55fb11Sticki 852c55fb11StickiThe `a[b]` is a syntax for block on address `a` with size `b`. 862c55fb11Sticki 872c55fb11StickiYou can set the log level (e.g. to avoid too much information) in `shim`. 882c55fb11Sticki 894b65baa3Sticki### Custom out-of-memory handlers 904b65baa3Sticki 914b65baa3StickiYou can set custom OOM handlers, by: 924b65baa3Sticki 934b65baa3Sticki```rust 944b65baa3Stickiextern crate ralloc; 954b65baa3Sticki 964b65baa3Stickifn my_handler() -> ! { 97a4bc061aSTaylor Cramer println!("Oh no! You ran out of memory."); 984b65baa3Sticki} 994b65baa3Sticki 1004b65baa3Stickifn main() { 1016e3426f3Sticki ralloc::set_oom_handler(my_handler); 1024b65baa3Sticki // Do some stuff... 1034b65baa3Sticki} 1044b65baa3Sticki``` 1054b65baa3Sticki 106c8adc1eaSticki### Thread-specific OOM handlers. 107c8adc1eaSticki 108c8adc1eaStickiYou can override the global OOM handler for your current thread. Enable the `thread_oom` feature, and then do: 109c8adc1eaSticki 110c8adc1eaSticki```rust 111c8adc1eaStickiextern crate ralloc; 112c8adc1eaSticki 113c8adc1eaStickifn my_handler() -> ! { 114a4bc061aSTaylor Cramer println!("Oh no! You ran out of memory."); 115c8adc1eaSticki} 116c8adc1eaSticki 117c8adc1eaStickifn main() { 118c8adc1eaSticki ralloc::set_thread_oom_handler(my_handler); 119c8adc1eaSticki // Do some stuff... 120c8adc1eaSticki} 121c8adc1eaSticki``` 122c8adc1eaSticki 1234b65baa3Sticki### Partial deallocation 1244b65baa3Sticki 1254b65baa3StickiMany allocators limits deallocations to be allocated block, that is, you cannot 1266e3426f3Stickiperform arithmetics or split it. `ralloc` does not have such a limitation: 1274b65baa3Sticki 1284b65baa3Sticki```rust 129146a5db9Stickiextern crate ralloc; 130146a5db9Sticki 1314b65baa3Stickiuse std::mem; 132146a5db9Sticki 1334b65baa3Stickifn main() { 1344b65baa3Sticki // We allocate 200 bytes. 1354b65baa3Sticki let vec = vec![0u8; 200]; 1364b65baa3Sticki // Cast it to a pointer. 1374b65baa3Sticki let ptr = vec.as_mut_ptr(); 1384b65baa3Sticki 1394b65baa3Sticki // To avoid UB, we leak the vector. 1404b65baa3Sticki mem::forget(vec); 1414b65baa3Sticki 1424b65baa3Sticki // Now, we create two vectors, each being 100 bytes long, effectively 1434b65baa3Sticki // splitting the original vector in half. 1444b65baa3Sticki let a = Vec::from_raw_parts(ptr, 100, 100); 1454b65baa3Sticki let b = Vec::from_raw_parts(ptr.offset(100), 100, 100); 1464b65baa3Sticki 1474b65baa3Sticki // Now, the destructor of a and b is called... Without a segfault! 1484b65baa3Sticki} 1494b65baa3Sticki``` 1504b65baa3Sticki 151146a5db9Sticki### Top notch security 1524b65baa3Sticki 153146a5db9StickiIf you are willing to trade a little performance, for extra security you can 1546e3426f3Stickicompile `ralloc` with the `security` flag. This will, along with other things, 155146a5db9Stickimake frees zeroing. 1564b65baa3Sticki 157146a5db9StickiIn other words, an attacker cannot for example inject malicious code or data, 158146a5db9Stickiwhich can be exploited when forgetting to initialize the data you allocate. 1594b65baa3Sticki 1606e3426f3Sticki### Code verification 1616e3426f3Sticki 1626e3426f3StickiAllocators are extremely security critical. If the same address is allocated to 1636e3426f3Stickitwo different callers, you risk all sorts of vulnerabilities. For this reason, 1646e3426f3Stickiit is important that the code is reviewed and verified. 1656e3426f3Sticki 1666e3426f3Sticki`ralloc` uses a multi-stage verification model: 1676e3426f3Sticki 1686e3426f3Sticki1. The type checker. A significant part of the verification is done entirely 1696e3426f3Sticki statically, and enforced through the type checker. We make excessive use of 1706e3426f3Sticki Rust's safety features and especially affine types. 1716e3426f3Sticki2. Unit testing. `ralloc` has full-coverage unit tests, even for private 1726e3426f3Sticki interfaces. 1736e3426f3Sticki3. Integration testing suit. `ralloc` uses a form of generative testing, where 1746e3426f3Sticki tests are "expanded" through a fixed set of functions. This allows 1756e3426f3Sticki relatively few tests (e.g., a few hundreds of lines) to multiply and become 1766e3426f3Sticki even more effective. 1776e3426f3Sticki4. Runtime checks. `ralloc` tries to avoid runtime tests, whenever it can, but 1786e3426f3Sticki that is not always possible. When the security gain is determined to be 1796e3426f3Sticki significant, and the performance loss is small, we use runtime checks (like 1806e3426f3Sticki checks for buffer overflows). 1816e3426f3Sticki5. Debug assertions. `ralloc` contains numerous debug assertions, enabled in 1826e3426f3Sticki debug mode. These allows for very careful testing for things like double 1836e3426f3Sticki free, memory corruption, as well as leaks and alignment checks. 1846e3426f3Sticki6. Manual reviewing. One or more persons reviews patches to ensure high 1856e3426f3Sticki security. 1866e3426f3Sticki 187146a5db9Sticki### Security through the type system 188146a5db9Sticki 1896e3426f3Sticki`ralloc` makes heavy use of Rust's type system, to make safety guarantees. 1906e3426f3StickiInternally, `ralloc` has a primitive named `Block`. This is fairly simple, 1910f78e690SBruce Mitchenerdenoting a contiguous segment of memory, but what is interesting is how it is 192146a5db9Stickichecked at compile time to be unique. This is done through the affine type 193146a5db9Stickisystem. 194146a5db9Sticki 195146a5db9StickiThis is just one of many examples. 1964b65baa3Sticki 1974b65baa3Sticki### Platform agnostic 1984b65baa3Sticki 1996e3426f3Sticki`ralloc` is platform independent. It depends on `ralloc_shim`, a minimal 200c8adc1eaStickiinterface for platform dependent functions. An default implementation of 201c8adc1eaSticki`ralloc_shim` is provided (supporting Mac OS, Linux, and BSD). 202146a5db9Sticki 203cdec4b0eSticki### Forcing inplace reallocation 204146a5db9Sticki 205cdec4b0eStickiInplace reallocation can be significantly faster than memcpy'ing reallocation. 206cdec4b0eStickiA limitation of libc is that you cannot do reallocation inplace-only (a 207cdec4b0eStickifailable method that guarantees the absence of memcpy of the buffer). 208cdec4b0eSticki 209cdec4b0eStickiHaving a failable way to do inplace reallocation provides some interesting possibilities. 210146a5db9Sticki 211146a5db9Sticki```rust 212146a5db9Stickiextern crate ralloc; 213146a5db9Sticki 214146a5db9Stickifn main() { 215cdec4b0eSticki let buf = ralloc::alloc(40, 1); 216cdec4b0eSticki // BRK'ing 20 bytes... 217cdec4b0eSticki let ptr = unsafe { ralloc::inplace_realloc(buf, 40, 45).unwrap() }; 218146a5db9Sticki 219cdec4b0eSticki // The buffer is now 45 bytes long! 220146a5db9Sticki} 221146a5db9Sticki``` 222146a5db9Sticki 223146a5db9Sticki### Safe SBRK 224146a5db9Sticki 2256e3426f3Sticki`ralloc` provides a `sbrk`, which can be used safely without breaking the allocator: 2266e3426f3Sticki 2276e3426f3Sticki```rust 2286e3426f3Stickiextern crate ralloc; 2296e3426f3Sticki 2306e3426f3Stickifn main() { 2316e3426f3Sticki // BRK'ing 20 bytes... 2326e3426f3Sticki let ptr = unsafe { ralloc::sbrk(20) }; 2336e3426f3Sticki} 2346e3426f3Sticki``` 23566cbc420Sticki 2366e3426f3Sticki### Useless alignments 2376e3426f3Sticki 2386e3426f3StickiAlignments doesn't have to be a power of two. 2396e3426f3Sticki 2406e3426f3Sticki## Planned features 2416e3426f3Sticki 2426e3426f3Sticki### Failable allocations 2436e3426f3Sticki 2446e3426f3StickiOften you are interested in handling OOM on a case-by-case basis. This is 2456e3426f3Stickiespecially true when dealing with very big allocation. 2466e3426f3Sticki 2476e3426f3Sticki`ralloc` allows that: 2486e3426f3Sticki 2496e3426f3Sticki```rust 2506e3426f3Stickiextern crate ralloc; 2516e3426f3Sticki 2526e3426f3Stickifn main() { 253cdec4b0eSticki let buf = ralloc::try_alloc(8, 4); 2546e3426f3Sticki // `buf` is a Result: It is Err(()) if the allocation failed. 2556e3426f3Sticki} 2566e3426f3Sticki``` 257