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 relatively slow, since it haven't been optimized 10yet. 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- [x] Mac OS X 19- [x] Redox 20- [ ] Windows 21 22## Using ralloc 23 24Be sure to use 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, syncronization, 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### Custom out-of-memory handlers 59 60You can set custom OOM handlers, by: 61 62```rust 63extern crate ralloc; 64 65fn my_handler() -> ! { 66 println!("Oh no. Blame the Mexicans."); 67} 68 69fn main() { 70 ralloc::set_oom_handler(my_handler); 71 // Do some stuff... 72} 73``` 74 75### Thread-specific OOM handlers. 76 77You can override the global OOM handler for your current thread. Enable the `thread_oom` feature, and then do: 78 79```rust 80extern crate ralloc; 81 82fn my_handler() -> ! { 83 println!("Oh no. Blame the Mexicans."); 84} 85 86fn main() { 87 ralloc::set_thread_oom_handler(my_handler); 88 // Do some stuff... 89} 90``` 91 92### Partial deallocation 93 94Many allocators limits deallocations to be allocated block, that is, you cannot 95perform arithmetics or split it. `ralloc` does not have such a limitation: 96 97```rust 98extern crate ralloc; 99 100use std::mem; 101 102fn main() { 103 // We allocate 200 bytes. 104 let vec = vec![0u8; 200]; 105 // Cast it to a pointer. 106 let ptr = vec.as_mut_ptr(); 107 108 // To avoid UB, we leak the vector. 109 mem::forget(vec); 110 111 // Now, we create two vectors, each being 100 bytes long, effectively 112 // splitting the original vector in half. 113 let a = Vec::from_raw_parts(ptr, 100, 100); 114 let b = Vec::from_raw_parts(ptr.offset(100), 100, 100); 115 116 // Now, the destructor of a and b is called... Without a segfault! 117} 118``` 119 120### Top notch security 121 122If you are willing to trade a little performance, for extra security you can 123compile `ralloc` with the `security` flag. This will, along with other things, 124make frees zeroing. 125 126In other words, an attacker cannot for example inject malicious code or data, 127which can be exploited when forgetting to initialize the data you allocate. 128 129### Code verification 130 131Allocators are extremely security critical.If the same addressis allocated to 132two different callers, you risk all sorts of vulnerabilities. For this reason, 133it is important that the code is reviewed and verified. 134 135`ralloc` uses a multi-stage verification model: 136 1371. The type checker. A significant part of the verification is done entirely 138 statically, and enforced through the type checker. We make excessive use of 139 Rust's safety features and especially affine types. 1402. Unit testing. `ralloc` has full-coverage unit tests, even for private 141 interfaces. 1423. Integration testing suit. `ralloc` uses a form of generative testing, where 143 tests are "expanded" through a fixed set of functions. This allows 144 relatively few tests (e.g., a few hundreds of lines) to multiply and become 145 even more effective. 1464. Runtime checks. `ralloc` tries to avoid runtime tests, whenever it can, but 147 that is not always possible. When the security gain is determined to be 148 significant, and the performance loss is small, we use runtime checks (like 149 checks for buffer overflows). 1505. Debug assertions. `ralloc` contains numerous debug assertions, enabled in 151 debug mode. These allows for very careful testing for things like double 152 free, memory corruption, as well as leaks and alignment checks. 1536. Manual reviewing. One or more persons reviews patches to ensure high 154 security. 155 156### Security through the type system 157 158`ralloc` makes heavy use of Rust's type system, to make safety guarantees. 159Internally, `ralloc` has a primitive named `Block`. This is fairly simple, 160denoting a contagious segment of memory, but what is interesting is how it is 161checked at compile time to be unique. This is done through the affine type 162system. 163 164This is just one of many examples. 165 166### Platform agnostic 167 168`ralloc` is platform independent. It depends on `ralloc_shim`, a minimal 169interface for platform dependent functions. An default implementation of 170`ralloc_shim` is provided (supporting Mac OS, Linux, and BSD). 171 172### Forcing inplace reallocation 173 174Inplace reallocation can be significantly faster than memcpy'ing reallocation. 175A limitation of libc is that you cannot do reallocation inplace-only (a 176failable method that guarantees the absence of memcpy of the buffer). 177 178Having a failable way to do inplace reallocation provides some interesting possibilities. 179 180```rust 181extern crate ralloc; 182 183fn main() { 184 let buf = ralloc::alloc(40, 1); 185 // BRK'ing 20 bytes... 186 let ptr = unsafe { ralloc::inplace_realloc(buf, 40, 45).unwrap() }; 187 188 // The buffer is now 45 bytes long! 189} 190``` 191 192### Safe SBRK 193 194`ralloc` provides a `sbrk`, which can be used safely without breaking the allocator: 195 196```rust 197extern crate ralloc; 198 199fn main() { 200 // BRK'ing 20 bytes... 201 let ptr = unsafe { ralloc::sbrk(20) }; 202} 203``` 204 205### Logging 206 207If you enable the `log` feature, you get detailed logging of the allocator, e.g. 208 209``` 210| : BRK'ing a block of size, 80, and alignment 8. (at bookkeeper.rs:458) 211| : Pushing 0x5578dacb2000[0x0] and 0x5578dacb2050[0xffb8]. (at bookkeeper.rs:490) 212|x : Freeing 0x1[0x0]. (at bookkeeper.rs:409) 213x| : BRK'ing a block of size, 4, and alignment 1. (at bookkeeper.rs:458) 214x| : Pushing 0x5578dacc2008[0x0] and 0x5578dacc200c[0xfffd]. (at bookkeeper.rs:490) 215x|x : Reallocating 0x5578dacc2008[0x4] to size 8 with align 1. (at bookkeeper.rs:272) 216x|x : Inplace reallocating 0x5578dacc2008[0x4] to size 8. (at bookkeeper.rs:354) 217_|x : Freeing 0x5578dacb2058[0xffb0]. (at bookkeeper.rs:409) 218_|x : Inserting block 0x5578dacb2058[0xffb0]. (at bookkeeper.rs:635) 219``` 220 221To the left, you can see the state of the block pool. `x` denotes a non-empty 222block, `_` denotes an empty block, and `|` denotes the cursor. 223 224The `a[b]` is a syntax for block on address `a` with size `b`. 225 226### Useless alignments 227 228Alignments doesn't have to be a power of two. 229 230## Planned features 231 232### Failable allocations 233 234Often you are interested in handling OOM on a case-by-case basis. This is 235especially true when dealing with very big allocation. 236 237`ralloc` allows that: 238 239```rust 240extern crate ralloc; 241 242fn main() { 243 let buf = ralloc::try_alloc(8, 4); 244 // `buf` is a Result: It is Err(()) if the allocation failed. 245} 246``` 247