1# ralloc 2 3A fast & memory efficient userspace allocator. 4 5This allocator is used as the default Redox. 6 7## A note on its state. 8 9It fully works, although it is somewhat slower than jemalloc, since it hasn't 10been optimized yet. 11 12I consider the state of the code quality very good. 13 14## Platforms supported out-of-the-box 15 16- [x] BSD 17- [x] Linux 18- [ ] Mac OS X 19- [x] Redox 20- [ ] Windows 21 22## Using ralloc 23 24Make sure you have Rust nightly. 25 26Add `ralloc` to `Cargo.toml`: 27 28```toml 29[dependencies.ralloc] 30git = "https://github.com/redox-os/ralloc.git" 31``` 32 33then import it in your main file: 34 35```rust 36extern crate ralloc; 37``` 38 39`ralloc` is now ready to roll! 40 41Note that `ralloc` cannot coexist with another allocator, unless they're deliberately compatible. 42 43## Features 44 45### Thread-local allocation 46 47Ralloc makes use of a global-local model allowing one to allocate or deallocate 48without locks, synchronization, or atomic writes. This provides reasonable 49performance, while preserving flexibility and ability to multithread. 50 51### First-class debugger (default: valgrind) support 52 53`ralloc` gives data to two debugger symbols specified in `ralloc_shim`, when 54the `debugger` feature is enabled. The default `shim` implementation is wired 55to `valgrind`, which can thus be used with `ralloc` to detect memory leaks and 56uninitialized use out-of-the-box. 57 58### Everything is customizable 59 60You can configure, tweak, and customize almost everything in `ralloc`. By 61changing the `shim` module, this is easily achieved. 62 63For example, you can change the reallocation strategy, the memtrim limits, the 64log target, and so on. 65 66### Logging 67 68If you enable the `log` feature, you get detailed logging of the allocator, e.g. 69 70``` 71| : BRK'ing a block of size, 80, and alignment 8. (at bookkeeper.rs:458) 72| : Pushing 0x5578dacb2000[0x0] and 0x5578dacb2050[0xffb8]. (at bookkeeper.rs:490) 73|x : Freeing 0x1[0x0]. (at bookkeeper.rs:409) 74x| : BRK'ing a block of size, 4, and alignment 1. (at bookkeeper.rs:458) 75x| : Pushing 0x5578dacc2008[0x0] and 0x5578dacc200c[0xfffd]. (at bookkeeper.rs:490) 76x|x : Reallocating 0x5578dacc2008[0x4] to size 8 with align 1. (at bookkeeper.rs:272) 77x|x : Inplace reallocating 0x5578dacc2008[0x4] to size 8. (at bookkeeper.rs:354) 78_|x : Freeing 0x5578dacb2058[0xffb0]. (at bookkeeper.rs:409) 79_|x : Inserting block 0x5578dacb2058[0xffb0]. (at bookkeeper.rs:635) 80``` 81 82To the left, you can see the state of the block pool. `x` denotes a non-empty 83block, `_` denotes an empty block, and `|` denotes the cursor. 84 85The `a[b]` is a syntax for block on address `a` with size `b`. 86 87You can set the log level (e.g. to avoid too much information) in `shim`. 88 89### Custom out-of-memory handlers 90 91You can set custom OOM handlers, by: 92 93```rust 94extern crate ralloc; 95 96fn my_handler() -> ! { 97 println!("Oh no! You ran out of memory."); 98} 99 100fn main() { 101 ralloc::set_oom_handler(my_handler); 102 // Do some stuff... 103} 104``` 105 106### Thread-specific OOM handlers. 107 108You can override the global OOM handler for your current thread. Enable the `thread_oom` feature, and then do: 109 110```rust 111extern crate ralloc; 112 113fn my_handler() -> ! { 114 println!("Oh no! You ran out of memory."); 115} 116 117fn main() { 118 ralloc::set_thread_oom_handler(my_handler); 119 // Do some stuff... 120} 121``` 122 123### Partial deallocation 124 125Many allocators limits deallocations to be allocated block, that is, you cannot 126perform arithmetics or split it. `ralloc` does not have such a limitation: 127 128```rust 129extern crate ralloc; 130 131use std::mem; 132 133fn main() { 134 // We allocate 200 bytes. 135 let vec = vec![0u8; 200]; 136 // Cast it to a pointer. 137 let ptr = vec.as_mut_ptr(); 138 139 // To avoid UB, we leak the vector. 140 mem::forget(vec); 141 142 // Now, we create two vectors, each being 100 bytes long, effectively 143 // splitting the original vector in half. 144 let a = Vec::from_raw_parts(ptr, 100, 100); 145 let b = Vec::from_raw_parts(ptr.offset(100), 100, 100); 146 147 // Now, the destructor of a and b is called... Without a segfault! 148} 149``` 150 151### Top notch security 152 153If you are willing to trade a little performance, for extra security you can 154compile `ralloc` with the `security` flag. This will, along with other things, 155make frees zeroing. 156 157In other words, an attacker cannot for example inject malicious code or data, 158which can be exploited when forgetting to initialize the data you allocate. 159 160### Code verification 161 162Allocators are extremely security critical. If the same address is allocated to 163two different callers, you risk all sorts of vulnerabilities. For this reason, 164it is important that the code is reviewed and verified. 165 166`ralloc` uses a multi-stage verification model: 167 1681. The type checker. A significant part of the verification is done entirely 169 statically, and enforced through the type checker. We make excessive use of 170 Rust's safety features and especially affine types. 1712. Unit testing. `ralloc` has full-coverage unit tests, even for private 172 interfaces. 1733. Integration testing suit. `ralloc` uses a form of generative testing, where 174 tests are "expanded" through a fixed set of functions. This allows 175 relatively few tests (e.g., a few hundreds of lines) to multiply and become 176 even more effective. 1774. Runtime checks. `ralloc` tries to avoid runtime tests, whenever it can, but 178 that is not always possible. When the security gain is determined to be 179 significant, and the performance loss is small, we use runtime checks (like 180 checks for buffer overflows). 1815. Debug assertions. `ralloc` contains numerous debug assertions, enabled in 182 debug mode. These allows for very careful testing for things like double 183 free, memory corruption, as well as leaks and alignment checks. 1846. Manual reviewing. One or more persons reviews patches to ensure high 185 security. 186 187### Security through the type system 188 189`ralloc` makes heavy use of Rust's type system, to make safety guarantees. 190Internally, `ralloc` has a primitive named `Block`. This is fairly simple, 191denoting a contiguous segment of memory, but what is interesting is how it is 192checked at compile time to be unique. This is done through the affine type 193system. 194 195This is just one of many examples. 196 197### Platform agnostic 198 199`ralloc` is platform independent. It depends on `ralloc_shim`, a minimal 200interface for platform dependent functions. An default implementation of 201`ralloc_shim` is provided (supporting Mac OS, Linux, and BSD). 202 203### Forcing inplace reallocation 204 205Inplace reallocation can be significantly faster than memcpy'ing reallocation. 206A limitation of libc is that you cannot do reallocation inplace-only (a 207failable method that guarantees the absence of memcpy of the buffer). 208 209Having a failable way to do inplace reallocation provides some interesting possibilities. 210 211```rust 212extern crate ralloc; 213 214fn main() { 215 let buf = ralloc::alloc(40, 1); 216 // BRK'ing 20 bytes... 217 let ptr = unsafe { ralloc::inplace_realloc(buf, 40, 45).unwrap() }; 218 219 // The buffer is now 45 bytes long! 220} 221``` 222 223### Safe SBRK 224 225`ralloc` provides a `sbrk`, which can be used safely without breaking the allocator: 226 227```rust 228extern crate ralloc; 229 230fn main() { 231 // BRK'ing 20 bytes... 232 let ptr = unsafe { ralloc::sbrk(20) }; 233} 234``` 235 236### Useless alignments 237 238Alignments doesn't have to be a power of two. 239 240## Planned features 241 242### Failable allocations 243 244Often you are interested in handling OOM on a case-by-case basis. This is 245especially true when dealing with very big allocation. 246 247`ralloc` allows that: 248 249```rust 250extern crate ralloc; 251 252fn main() { 253 let buf = ralloc::try_alloc(8, 4); 254 // `buf` is a Result: It is Err(()) if the allocation failed. 255} 256``` 257