A fast & memory efficient userspace allocator.
This allocator is used as the default Redox.
It fully works, although it is somewhat slower than jemalloc, since it hasn't been optimized yet.
I consider the state of the code quality very good.
- BSD
- Linux
- Mac OS X
- Redox
- Windows
Make sure you have Rust nightly.
Add ralloc
to Cargo.toml
:
[dependencies.ralloc]
git = "https://github.com/redox-os/ralloc.git"
then import it in your main file:
extern crate ralloc;
ralloc
is now ready to roll!
Note that ralloc
cannot coexist with another allocator, unless they're deliberately compatible.
Ralloc makes use of a global-local model allowing one to allocate or deallocate without locks, synchronization, or atomic writes. This provides reasonable performance, while preserving flexibility and ability to multithread.
ralloc
gives data to two debugger symbols specified in ralloc_shim
, when
the debugger
feature is enabled. The default shim
implementation is wired
to valgrind
, which can thus be used with ralloc
to detect memory leaks and
uninitialized use out-of-the-box.
You can configure, tweak, and customize almost everything in ralloc
. By
changing the shim
module, this is easily achieved.
For example, you can change the reallocation strategy, the memtrim limits, the log target, and so on.
If you enable the log
feature, you get detailed logging of the allocator, e.g.
| : BRK'ing a block of size, 80, and alignment 8. (at bookkeeper.rs:458)
| : Pushing 0x5578dacb2000[0x0] and 0x5578dacb2050[0xffb8]. (at bookkeeper.rs:490)
|x : Freeing 0x1[0x0]. (at bookkeeper.rs:409)
x| : BRK'ing a block of size, 4, and alignment 1. (at bookkeeper.rs:458)
x| : Pushing 0x5578dacc2008[0x0] and 0x5578dacc200c[0xfffd]. (at bookkeeper.rs:490)
x|x : Reallocating 0x5578dacc2008[0x4] to size 8 with align 1. (at bookkeeper.rs:272)
x|x : Inplace reallocating 0x5578dacc2008[0x4] to size 8. (at bookkeeper.rs:354)
_|x : Freeing 0x5578dacb2058[0xffb0]. (at bookkeeper.rs:409)
_|x : Inserting block 0x5578dacb2058[0xffb0]. (at bookkeeper.rs:635)
To the left, you can see the state of the block pool. x
denotes a non-empty
block, _
denotes an empty block, and |
denotes the cursor.
The a[b]
is a syntax for block on address a
with size b
.
You can set the log level (e.g. to avoid too much information) in shim
.
You can set custom OOM handlers, by:
extern crate ralloc;
fn my_handler() -> ! {
println!("Oh no! You ran out of memory.");
}
fn main() {
ralloc::set_oom_handler(my_handler);
// Do some stuff...
}
You can override the global OOM handler for your current thread. Enable the thread_oom
feature, and then do:
extern crate ralloc;
fn my_handler() -> ! {
println!("Oh no! You ran out of memory.");
}
fn main() {
ralloc::set_thread_oom_handler(my_handler);
// Do some stuff...
}
Many allocators limits deallocations to be allocated block, that is, you cannot
perform arithmetics or split it. ralloc
does not have such a limitation:
extern crate ralloc;
use std::mem;
fn main() {
// We allocate 200 bytes.
let vec = vec![0u8; 200];
// Cast it to a pointer.
let ptr = vec.as_mut_ptr();
// To avoid UB, we leak the vector.
mem::forget(vec);
// Now, we create two vectors, each being 100 bytes long, effectively
// splitting the original vector in half.
let a = Vec::from_raw_parts(ptr, 100, 100);
let b = Vec::from_raw_parts(ptr.offset(100), 100, 100);
// Now, the destructor of a and b is called... Without a segfault!
}
If you are willing to trade a little performance, for extra security you can
compile ralloc
with the security
flag. This will, along with other things,
make frees zeroing.
In other words, an attacker cannot for example inject malicious code or data, which can be exploited when forgetting to initialize the data you allocate.
Allocators are extremely security critical. If the same address is allocated to two different callers, you risk all sorts of vulnerabilities. For this reason, it is important that the code is reviewed and verified.
ralloc
uses a multi-stage verification model:
- The type checker. A significant part of the verification is done entirely statically, and enforced through the type checker. We make excessive use of Rust's safety features and especially affine types.
- Unit testing.
ralloc
has full-coverage unit tests, even for private interfaces. - Integration testing suit.
ralloc
uses a form of generative testing, where tests are "expanded" through a fixed set of functions. This allows relatively few tests (e.g., a few hundreds of lines) to multiply and become even more effective. - Runtime checks.
ralloc
tries to avoid runtime tests, whenever it can, but that is not always possible. When the security gain is determined to be significant, and the performance loss is small, we use runtime checks (like checks for buffer overflows). - Debug assertions.
ralloc
contains numerous debug assertions, enabled in debug mode. These allows for very careful testing for things like double free, memory corruption, as well as leaks and alignment checks. - Manual reviewing. One or more persons reviews patches to ensure high security.
ralloc
makes heavy use of Rust's type system, to make safety guarantees.
Internally, ralloc
has a primitive named Block
. This is fairly simple,
denoting a contiguous segment of memory, but what is interesting is how it is
checked at compile time to be unique. This is done through the affine type
system.
This is just one of many examples.
ralloc
is platform independent. It depends on ralloc_shim
, a minimal
interface for platform dependent functions. An default implementation of
ralloc_shim
is provided (supporting Mac OS, Linux, and BSD).
Inplace reallocation can be significantly faster than memcpy'ing reallocation. A limitation of libc is that you cannot do reallocation inplace-only (a failable method that guarantees the absence of memcpy of the buffer).
Having a failable way to do inplace reallocation provides some interesting possibilities.
extern crate ralloc;
fn main() {
let buf = ralloc::alloc(40, 1);
// BRK'ing 20 bytes...
let ptr = unsafe { ralloc::inplace_realloc(buf, 40, 45).unwrap() };
// The buffer is now 45 bytes long!
}
ralloc
provides a sbrk
, which can be used safely without breaking the allocator:
extern crate ralloc;
fn main() {
// BRK'ing 20 bytes...
let ptr = unsafe { ralloc::sbrk(20) };
}
Alignments doesn't have to be a power of two.
Often you are interested in handling OOM on a case-by-case basis. This is especially true when dealing with very big allocation.
ralloc
allows that:
extern crate ralloc;
fn main() {
let buf = ralloc::try_alloc(8, 4);
// `buf` is a Result: It is Err(()) if the allocation failed.
}