use std::alloc::{GlobalAlloc, Layout, System};
use std::ptr;
pub struct Allocator;
unsafe impl GlobalAlloc for Allocator {
#[inline]
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
if pool::takes(layout.size(), layout.align()) {
return pool::alloc(layout.size());
}
let block = unsafe { System.alloc(layout) };
huge_pages::suggest(block, layout.size());
block
}
#[inline]
unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
if pool::takes(layout.size(), layout.align()) {
let block = pool::alloc(layout.size());
if !block.is_null() {
unsafe { ptr::write_bytes(block, 0, layout.size()) };
}
return block;
}
let block = unsafe { System.alloc_zeroed(layout) };
huge_pages::suggest(block, layout.size());
block
}
#[inline]
unsafe fn dealloc(&self, block: *mut u8, layout: Layout) {
if pool::takes(layout.size(), layout.align()) {
return unsafe { pool::dealloc(block, layout.size()) };
}
unsafe { System.dealloc(block, layout) }
}
#[inline]
unsafe fn realloc(&self, block: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
let was_pooled = pool::takes(layout.size(), layout.align());
let is_pooled = pool::takes(new_size, layout.align());
if !was_pooled && !is_pooled {
let block = unsafe { System.realloc(block, layout, new_size) };
huge_pages::suggest(block, new_size);
return block;
}
if was_pooled && is_pooled && pool::same_block(layout.size(), new_size) {
return block;
}
let Ok(new_layout) = Layout::from_size_align(new_size, layout.align()) else {
return ptr::null_mut();
};
unsafe {
let new_block = self.alloc(new_layout);
if !new_block.is_null() {
ptr::copy_nonoverlapping(block, new_block, layout.size().min(new_size));
self.dealloc(block, layout);
}
new_block
}
}
}
mod pool {
use super::huge_pages;
use std::alloc::{GlobalAlloc, Layout, System};
use std::cell::Cell;
use std::ptr;
pub const GRANULE: usize = 16;
pub const MAX_SIZE: usize = 512;
const CLASSES: usize = MAX_SIZE / GRANULE;
const FIRST_CHUNK: usize = 64 << 10;
const MAX_CHUNK: usize = 4 << 20;
struct Pools {
free: [Cell<*mut u8>; CLASSES],
fresh: Cell<*mut u8>,
fresh_end: Cell<*mut u8>,
next_chunk: Cell<usize>,
}
thread_local! {
static POOLS: Pools = const {
Pools {
free: [const { Cell::new(ptr::null_mut()) }; CLASSES],
fresh: Cell::new(ptr::null_mut()),
fresh_end: Cell::new(ptr::null_mut()),
next_chunk: Cell::new(FIRST_CHUNK),
}
};
}
#[inline(always)]
fn class(size: usize) -> usize {
size.wrapping_sub(1) / GRANULE
}
#[inline(always)]
pub fn takes(size: usize, align: usize) -> bool {
class(size) < CLASSES && align <= GRANULE
}
#[inline(always)]
pub fn same_block(size: usize, other_size: usize) -> bool {
class(size) == class(other_size)
}
#[inline(always)]
pub fn alloc(size: usize) -> *mut u8 {
POOLS.with(|pools| {
let class = class(size);
let Some(head) = pools.free.get(class) else {
return ptr::null_mut();
};
let block = head.get();
if !block.is_null() {
head.set(unsafe { block.cast::<*mut u8>().read() });
return block;
}
pools.cut((class + 1) * GRANULE)
})
}
#[inline(always)]
pub unsafe fn dealloc(block: *mut u8, size: usize) {
POOLS.with(|pools| {
let Some(head) = pools.free.get(class(size)) else {
return;
};
unsafe { block.cast::<*mut u8>().write(head.get()) };
head.set(block);
})
}
impl Pools {
#[inline(always)]
fn cut(&self, bytes: usize) -> *mut u8 {
let block = self.fresh.get();
if (self.fresh_end.get() as usize) - (block as usize) < bytes {
return self.cut_from_new_chunk(bytes);
}
self.fresh.set(block.wrapping_add(bytes));
block
}
#[cold]
#[inline(never)]
fn cut_from_new_chunk(&self, bytes: usize) -> *mut u8 {
let size = self.next_chunk.get();
if bytes > size {
return ptr::null_mut();
}
let Ok(layout) = Layout::from_size_align(size, GRANULE) else {
return ptr::null_mut();
};
let chunk = unsafe { System.alloc(layout) };
if chunk.is_null() {
return chunk;
}
huge_pages::suggest(chunk, size);
let rest = self.fresh.get();
let rest_size = (self.fresh_end.get() as usize) - (rest as usize);
if let Some(head) = self.free.get(class(rest_size)) {
unsafe { rest.cast::<*mut u8>().write(head.get()) };
head.set(rest);
}
self.next_chunk.set((size * 2).min(MAX_CHUNK));
self.fresh.set(chunk.wrapping_add(bytes));
self.fresh_end.set(chunk.wrapping_add(size));
chunk
}
}
}
#[cfg(target_os = "linux")]
mod huge_pages {
use std::ffi::c_void;
use std::sync::atomic::{AtomicUsize, Ordering};
const HUGE_PAGE: usize = 2 << 20;
static PAGE_SIZE: AtomicUsize = AtomicUsize::new(0);
#[inline]
pub fn suggest(block: *mut u8, size: usize) {
if size >= HUGE_PAGE && !block.is_null() {
suggest_range(block, size);
}
}
#[cold]
fn suggest_range(block: *mut u8, size: usize) {
let page_size = match PAGE_SIZE.load(Ordering::Relaxed) {
0 => {
let page_size =
usize::try_from(unsafe { libc::sysconf(libc::_SC_PAGESIZE) }).unwrap_or(0);
if !page_size.is_power_of_two() {
return;
}
PAGE_SIZE.store(page_size, Ordering::Relaxed);
page_size
}
page_size => page_size,
};
let start = block as usize & !(page_size - 1);
let Some(end) = (block as usize)
.checked_add(size)
.and_then(|end| end.checked_next_multiple_of(page_size))
else {
return;
};
unsafe { libc::madvise(start as *mut c_void, end - start, libc::MADV_HUGEPAGE) };
}
}
#[cfg(not(target_os = "linux"))]
mod huge_pages {
#[inline]
pub fn suggest(_block: *mut u8, _size: usize) {}
}
#[cfg(test)]
mod tests {
use super::*;
struct Random(u64);
impl Random {
fn next(&mut self) -> u64 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
self.0
}
fn below(&mut self, bound: usize) -> usize {
(self.next() % bound as u64) as usize
}
fn size(&mut self) -> usize {
match self.below(8) {
0 => 1 + self.below(4096),
1 => pool::GRANULE * (1 + self.below(40)),
2 => pool::GRANULE * (1 + self.below(40)) + 1,
3 => pool::MAX_SIZE - 1 + self.below(3),
_ => 1 + self.below(600),
}
}
}
struct Block {
start: *mut u8,
layout: Layout,
seed: u8,
}
impl Block {
fn expected(&self, position: usize) -> u8 {
self.seed.wrapping_add(position as u8).wrapping_mul(31)
}
fn fill(&self, from: usize) {
for position in from..self.layout.size() {
unsafe { self.start.add(position).write(self.expected(position)) };
}
}
fn check(&self, len: usize) {
for position in 0..len {
let byte = unsafe { self.start.add(position).read() };
assert_eq!(
byte,
self.expected(position),
"byte {} of a block",
position
);
}
}
}
fn churn(seed: u64, rounds: usize) {
let mut random = Random(seed);
let mut blocks: Vec<Block> = Vec::new();
for round in 0..rounds {
match random.below(if blocks.len() > 400 { 6 } else { 4 }) {
0 | 1 => {
let align = 1 << random.below(7);
let layout = Layout::from_size_align(random.size(), align).unwrap();
let zeroed = random.below(4) == 0;
let start = unsafe {
if zeroed {
Allocator.alloc_zeroed(layout)
} else {
Allocator.alloc(layout)
}
};
assert!(!start.is_null());
assert_eq!(start as usize % align, 0);
if zeroed {
for position in 0..layout.size() {
assert_eq!(unsafe { start.add(position).read() }, 0);
}
}
let block = Block {
start,
layout,
seed: round as u8,
};
block.fill(0);
blocks.push(block);
}
2 if !blocks.is_empty() => {
let index = random.below(blocks.len());
let block = &mut blocks[index];
let old_size = block.layout.size();
let new_size = random.size();
let start = unsafe { Allocator.realloc(block.start, block.layout, new_size) };
assert!(!start.is_null());
assert_eq!(start as usize % block.layout.align(), 0);
block.start = start;
block.layout = Layout::from_size_align(new_size, block.layout.align()).unwrap();
block.check(old_size.min(new_size));
block.fill(old_size.min(new_size));
}
_ if !blocks.is_empty() => {
let block = blocks.swap_remove(random.below(blocks.len()));
block.check(block.layout.size());
unsafe { Allocator.dealloc(block.start, block.layout) };
}
_ => {}
}
}
for block in blocks {
block.check(block.layout.size());
unsafe { Allocator.dealloc(block.start, block.layout) };
}
}
#[test]
fn blocks_keep_their_content() {
churn(0x9E37_79B9_7F4A_7C15, 200_000);
}
#[test]
fn threads_have_pools_of_their_own() {
let threads: Vec<_> = (1..=4u64)
.map(|thread| std::thread::spawn(move || churn(thread * 0x2545_F491_4F6C_DD1D, 50_000)))
.collect();
for thread in threads {
thread.join().unwrap();
}
}
#[test]
fn a_block_may_be_freed_on_another_thread() {
let boxes: Vec<Box<[u64; 5]>> = (0..10_000).map(|value| Box::new([value; 5])).collect();
let sum = std::thread::spawn(move || boxes.iter().map(|values| values[4]).sum::<u64>())
.join()
.unwrap();
assert_eq!(sum, 9_999 * 10_000 / 2);
let again: Vec<Box<[u64; 5]>> = (0..10_000).map(|value| Box::new([value; 5])).collect();
assert!(
again
.iter()
.enumerate()
.all(|(value, values)| values[0] == value as u64)
);
}
#[test]
fn a_freed_block_is_the_next_of_its_size() {
let layout = Layout::from_size_align(40, 8).unwrap();
unsafe {
let first = Allocator.alloc(layout);
let second = Allocator.alloc(layout);
assert_ne!(first, second);
Allocator.dealloc(first, layout);
assert_eq!(
Allocator.alloc(Layout::from_size_align(33, 1).unwrap()),
first
);
Allocator.dealloc(first, layout);
Allocator.dealloc(second, layout);
}
}
#[test]
fn growing_within_a_block_does_not_move_it() {
let layout = Layout::from_size_align(17, 1).unwrap();
unsafe {
let block = Allocator.alloc(layout);
assert_eq!(Allocator.realloc(block, layout, 32), block);
let grown = Layout::from_size_align(32, 1).unwrap();
let moved = Allocator.realloc(block, grown, 33);
assert_ne!(moved, block);
Allocator.dealloc(moved, Layout::from_size_align(33, 1).unwrap());
}
}
}