use std::mem;
use std::sync::Arc;
use std::sync::atomic::{fence, AtomicPtr, AtomicUsize, Ordering};
use super::bagpipe::bag::{Revocable, WeakBag};
use super::bagpipe::BagPipe;
use super::bagpipe::queue::{FAAQueueLowLevel, RevocableFAAQueue};
use super::utils::{mmap, LazyInitializable, OwnedArray};
use std::marker::PhantomData;
use std::ptr;
use std::cmp;
#[cfg(feature = "nightly")]
use std::intrinsics::{likely, unlikely};
#[cfg(not(feature = "nightly"))]
#[cfg_attr(feature = "cargo-clippy", allow(inline_always))]
#[inline(always)]
unsafe fn likely(b: bool) -> bool {
b
}
#[cfg(not(feature = "nightly"))]
#[cfg_attr(feature = "cargo-clippy", allow(inline_always))]
#[inline(always)]
unsafe fn unlikely(b: bool) -> bool {
b
}
type SlagPipe<T> = BagPipe<FAAQueueLowLevel<*mut T>>;
pub type RevocablePipe<T> = BagPipe<RevocableFAAQueue<*mut T>>;
pub trait MemoryBlock
where Self: Clone
{
fn new(page_size: usize) -> Self;
fn page_size(&self) -> usize;
fn contains(&self, it: *mut u8) -> bool;
fn carve(&self, npages: usize) -> *mut u8;
}
pub trait CoarseAllocator
where Self: Clone
{
type Block: MemoryBlock;
unsafe fn alloc(&mut self) -> *mut u8;
unsafe fn free(&mut self, item: *mut u8, uncommit: bool);
fn backing_memory(&self) -> &Self::Block;
}
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub struct Metadata {
pub object_size: usize,
n_objects: usize,
n_bitset_words: usize,
total_bytes: usize,
bitset_offset: isize,
objects_offset: isize,
object_mask: usize,
bit_rep_shift: usize,
local_index: usize,
cutoff_objects: usize,
usable_size: usize,
}
use self::bitset::Word;
mod bitset {
use std::sync::atomic::AtomicUsize;
use std::mem;
use std::ops::Deref;
pub struct Word {
inner: AtomicUsize, }
impl Word {
#[inline]
pub fn bits() -> usize {
mem::size_of::<usize>() * 8
}
}
impl Deref for Word {
type Target = AtomicUsize;
fn deref(&self) -> &AtomicUsize {
&self.inner
}
}
}
use self::ref_count::RefCount;
mod ref_count {
use std::sync::atomic::{AtomicUsize, Ordering};
use std::default::Default;
#[cfg(target_pointer_width = "32")]
const WORD_SHIFT: usize = 31;
#[cfg(target_pointer_width = "64")]
const WORD_SHIFT: usize = 63;
const MASK: usize = 1 << WORD_SHIFT;
pub struct RefCount(AtomicUsize);
impl Default for RefCount {
fn default() -> Self {
RefCount(AtomicUsize::new(0))
}
}
impl RefCount {
pub fn init(&self, start: usize) {
self.0.store(start, Ordering::Relaxed);
}
pub fn claim(&self) -> bool {
let was = self.0.fetch_or(MASK, Ordering::Relaxed);
was & MASK == 0
}
pub fn unclaim(&self) -> (bool, usize) {
let was = self.0.fetch_and(!MASK, Ordering::Relaxed);
let claimed = was & MASK == MASK;
(claimed, was & !MASK)
}
pub fn inc_n(&self, n: usize) -> (bool, usize) {
let was = self.0.fetch_add(n, Ordering::Acquire);
let claimed = was & MASK == MASK;
(claimed, was & !MASK)
}
pub fn dec_n(&self, n: usize) -> (bool, usize) {
let was = self.0.fetch_sub(n, Ordering::Release);
let claimed = was & MASK == MASK;
let result = was & !MASK;
debug_assert!(result >= n,
"(dec {:?}; claimed={}), was {}, n={}",
self as *const Self,
claimed,
result,
n);
(claimed, result)
}
#[allow(dead_code)]
pub fn load(&self) -> (bool, usize) {
let was = self.0.load(Ordering::Acquire);
let claimed = was & MASK == MASK;
(claimed, was & !MASK)
}
}
}
pub struct Slag {
meta: AtomicPtr<Metadata>,
rc: RefCount,
handle: AtomicUsize,
_padding: [usize; 5],
}
impl Revocable for Slag {
fn handle(&self) -> &AtomicUsize {
&self.handle
}
}
pub fn compute_metadata(obj_size: usize,
page_size: usize,
local_index: usize,
cutoff_factor: f64,
usable_size: usize)
-> Metadata {
fn bitset_bytes(n_objects: usize, gran: usize) -> usize {
let word_size = mem::size_of::<Word>();
let word_bits = Word::bits();
let bits = n_objects * gran;
let words = if bits % word_bits == 0 {
bits / word_bits
} else {
bits / word_bits + 1
};
words * word_size
}
fn align_padding(alignment: usize, n_objects: usize, gran: usize) -> usize {
debug_assert!(alignment.is_power_of_two());
let header_size = mem::size_of::<Slag>();
let h_bitset_size = header_size + bitset_bytes(n_objects, gran);
let rounded = (h_bitset_size + (alignment - 1)) & !(alignment - 1);
rounded - h_bitset_size
}
fn total_bytes(size: usize, gran: usize, n_objects: usize) -> usize {
let header_size = mem::size_of::<Slag>();
let padding = if size.is_power_of_two() {
align_padding(size, n_objects, gran)
} else {
0
};
header_size + bitset_bytes(n_objects, gran) + padding + n_objects * size
}
fn meta_inner(size: usize,
page_size: usize,
round_up_to_shift: usize,
local_index: usize,
cutoff_factor: f64,
usable_size: usize)
-> (f64, usize, Metadata) {
use std::cmp;
let usable_size = cmp::min(usable_size, page_size);
let mut mult = 1.0;
let round_up_to_bytes = 1 << round_up_to_shift;
let padding_per_object = {
let rem = size % round_up_to_bytes;
if rem == 0 { 0 } else { round_up_to_bytes - rem }
};
let padded_size = size + padding_per_object;
let gran = padded_size / round_up_to_bytes;
debug_assert!(usable_size > 0);
debug_assert!(round_up_to_bytes > 0);
debug_assert!(round_up_to_bytes.is_power_of_two());
debug_assert!(gran > 0);
#[cfg_attr(feature = "cargo-clippy", allow(panic_params))]
debug_assert!({
if gran == 1 {
padded_size.is_power_of_two()
} else {
true
}
});
let bits_per_object = padded_size >> round_up_to_shift;
let bits_per_word = Word::bits();
let slush_size = bits_per_object - (bits_per_word % bits_per_object);
if bits_per_word < slush_size {
mult = -1.0;
}
let mut n_objects = 1;
loop {
if total_bytes(padded_size, gran, n_objects + 1) > usable_size {
break;
}
n_objects += 1;
}
let align_padding = if padded_size.is_power_of_two() {
align_padding(padded_size, n_objects, gran)
} else {
0
};
let bs = (total_bytes(padded_size, gran, n_objects) - n_objects * padding_per_object -
bitset_bytes(n_objects, gran) - mem::size_of::<Slag>() -
align_padding) as f64;
let score = if bs > usable_size as f64 { -1.0 } else { 1.0 } * bs / (usable_size as f64);
let header_offset = mem::size_of::<Slag>() as isize;
let n_words = bitset_bytes(n_objects, gran) / mem::size_of::<Word>();
(score * mult,
n_words,
Metadata {
n_objects: n_objects,
n_bitset_words: n_words,
total_bytes: page_size,
bitset_offset: header_offset,
objects_offset: header_offset +
(align_padding + bitset_bytes(n_objects, gran)) as isize,
object_size: padded_size,
object_mask: 1,
bit_rep_shift: round_up_to_bytes.trailing_zeros() as usize,
local_index: local_index,
cutoff_objects: cmp::max(1, (n_objects as f64 * cutoff_factor) as usize),
usable_size: usable_size,
})
}
let test_meta = Metadata {
n_objects: 0,
n_bitset_words: 0,
total_bytes: 0,
bitset_offset: 0,
objects_offset: 0,
object_size: 0,
object_mask: 0,
bit_rep_shift: 0,
local_index: 0,
cutoff_objects: 0,
usable_size: 0,
};
#[allow(unused)]
let (frag, _, mut meta) = (1..(obj_size.next_power_of_two().trailing_zeros() as usize + 1))
.map(|shift| {
meta_inner(obj_size,
page_size,
shift,
local_index,
cutoff_factor,
usable_size)
})
.fold((-10.0, 1000, test_meta),
|o1, o2| if o1.0 < o2.0 || (o1.0 - o2.0).abs() < 1e-5 && o1.1 > o2.1 {
o2
} else {
o1
});
let bits = Word::bits();
let bits_per_object = meta.object_size >> meta.bit_rep_shift;
let mut cur_bit = 0;
let mut mask = 0;
while cur_bit < bits {
mask |= 1 << cur_bit;
cur_bit += bits_per_object;
}
meta.object_mask = mask;
trace!("created {:?} fragmentation: {:?}", meta, frag);
meta
}
#[cfg_attr(feature = "cargo-clippy", allow(inline_always))]
#[inline(always)]
fn split_index(item_index: usize) -> (isize, usize) {
#[cfg(target_pointer_width = "32")]
const WORD_SHIFT: usize = 5;
#[cfg(target_pointer_width = "32")]
const WORD_MASK: usize = 31;
#[cfg(target_pointer_width = "64")]
const WORD_SHIFT: usize = 6;
#[cfg(target_pointer_width = "64")]
const WORD_MASK: usize = 63;
((item_index >> WORD_SHIFT) as isize, item_index & WORD_MASK)
}
struct AllocIter {
cur_word: usize,
next_word: *mut Word,
refcnt: *const RefCount,
object_base: *mut u8,
object_size: usize,
remaining_words: usize,
cur_word_index: usize,
}
impl AllocIter {
fn new(first_bitset_word: *mut Word,
bitset_words: usize,
refcnt: *const RefCount,
object_base: *mut u8,
object_size: usize)
-> AllocIter {
unsafe {
let cur_word = first_bitset_word.as_ref()
.expect("bitset must point to valid memory")
.swap(0, Ordering::Acquire);
(*refcnt).dec_n(cur_word.count_ones() as usize);
AllocIter {
cur_word: cur_word,
next_word: first_bitset_word.offset(1),
refcnt: refcnt,
object_base: object_base,
object_size: object_size,
remaining_words: (bitset_words - 1),
cur_word_index: 0,
}
}
}
fn refresh_word(&mut self) {
unsafe {
let next = self.next_word
.as_ref()
.expect("bitset must point to valid memory");
self.next_word = self.next_word.offset(1);
self.cur_word = next.swap(0, Ordering::Acquire);
(*self.refcnt).dec_n(self.cur_word.count_ones() as usize);
self.remaining_words -= 1;
self.cur_word_index += 1;
}
}
}
impl Iterator for AllocIter {
type Item = *mut u8;
fn next(&mut self) -> Option<*mut u8> {
let word_size = Word::bits();
loop {
let next_bit = self.cur_word.trailing_zeros() as usize;
if unsafe { unlikely(next_bit == word_size) } {
if self.remaining_words == 0 {
return None;
}
self.refresh_word();
continue;
}
unsafe {
self.cur_word ^= 1 << next_bit;
let object = self.object_base
.offset((self.object_size * (self.cur_word_index * word_size + next_bit)) as
isize);
return Some(object);
}
}
}
}
enum Transition {
Null,
Available,
Full,
}
macro_rules! or_slag_word {
($slag:expr, $bitset_offset:expr, $word:expr, $mask:expr) => {
{
let word = $word;
(($slag as *mut u8).offset($bitset_offset) as *mut Word)
.offset(word as isize)
.as_ref()
.unwrap()
.store($mask, Ordering::Relaxed);
}
};
}
impl Slag {
fn set_metadata(&self, m: *mut Metadata) {
self.meta.store(m, Ordering::Release);
}
pub fn get_metadata(&self) -> &Metadata {
unsafe {
self.meta
.load(Ordering::Relaxed)
.as_ref()
.expect("metadata should always be non-null")
}
}
fn as_raw(&self) -> *mut Self {
self as *const _ as *mut Self
}
unsafe fn init(slag: *mut Self, meta: &Metadata) {
let slf = slag.as_mut().unwrap();
slf.set_metadata(meta as *const _ as *mut Metadata);
slf.rc.init(meta.n_objects);
slf.handle.store(0, Ordering::Relaxed);
let bits_per_object = meta.object_size >> meta.bit_rep_shift;
let bits_per_word = Word::bits();
let slush_size = bits_per_object - (bits_per_word % bits_per_object);
debug_assert!(bits_per_word >= slush_size,
"bpw={}, slush_size={}",
bits_per_word,
slush_size);
let end_slush_shift = bits_per_word - slush_size;
let mut cur_slush = 0;
let rem = ((meta.n_objects * bits_per_object) % bits_per_word) as u32;
let rem_mask = !(!0 << rem);
let mut mask = meta.object_mask;
if mask == !0 {
for word in 0..(meta.n_bitset_words - 1) {
or_slag_word!(slag, meta.bitset_offset, word, !0);
}
if rem_mask == 0 {
or_slag_word!(slag, meta.bitset_offset, meta.n_bitset_words - 1, !0);
} else {
or_slag_word!(slag,
meta.bitset_offset,
meta.n_bitset_words - 1,
!0 & rem_mask);
}
fence(Ordering::Acquire);
return;
}
if rem == 0 {
for word in 0..(meta.n_bitset_words) {
or_slag_word!(slag, meta.bitset_offset, word, mask);
let new_slush = mask >> end_slush_shift;
mask = mask.wrapping_shl(slush_size as u32);
mask |= cur_slush;
cur_slush = new_slush;
}
} else {
for word in 0..(meta.n_bitset_words - 1) {
or_slag_word!(slag, meta.bitset_offset, word, mask);
let new_slush = mask >> end_slush_shift;
mask <<= slush_size;
mask |= cur_slush;
cur_slush = new_slush;
}
or_slag_word!(slag,
meta.bitset_offset,
meta.n_bitset_words - 1,
mask & rem_mask);
}
fence(Ordering::Acquire);
}
pub fn find(item: *mut u8, alignment: usize) -> *mut Self {
debug_assert!(alignment.is_power_of_two());
debug_assert!(alignment > 0);
((item as usize) & !(alignment - 1)) as *mut Self
}
#[inline]
fn get_word(raw_self: *mut Slag, item: *mut u8, m: &Metadata) -> (isize, usize) {
let it_num = item as usize;
let self_num = raw_self as usize;
let item_ix = (it_num - ((m.objects_offset as usize) + self_num)) >> m.bit_rep_shift;
split_index(item_ix)
}
fn free(&self, item: *mut u8) -> Transition {
let m = self.get_metadata();
debug_assert!((item as usize) < (self.as_raw() as usize + m.total_bytes));
let (word, word_ix) = Self::get_word(self.as_raw(), item, m);
let (claimed, was) = self.rc.inc_n(1);
unsafe {
((self.as_raw() as *mut u8).offset(m.bitset_offset) as *mut Word)
.offset(word)
.as_ref()
.unwrap()
.fetch_or(1 << word_ix, Ordering::Release)
};
if !claimed {
if was == m.cutoff_objects - 1 {
return Transition::Available;
}
if was == m.n_objects - 1 {
return Transition::Full;
}
}
Transition::Null
}
fn refresh(&self, meta: &Metadata) -> AllocIter {
unsafe {
AllocIter::new((self.as_raw() as *mut u8).offset(meta.bitset_offset) as *mut Word,
meta.n_bitset_words,
&self.rc,
(self.as_raw() as *mut u8).offset(meta.objects_offset),
1 << meta.bit_rep_shift)
}
}
}
struct Coalescer(OwnedArray<RemoteFreeCell>, PtrStack);
struct RemoteFreeCell {
rc: *mut RefCount,
word: *mut Word,
mask: usize,
}
impl Default for RemoteFreeCell {
fn default() -> Self {
RemoteFreeCell {
rc: ptr::null_mut(),
word: ptr::null_mut(),
mask: 0,
}
}
}
impl Coalescer {
fn new(size: usize) -> Self {
Coalescer(OwnedArray::new(size.next_power_of_two()),
PtrStack::new(size))
}
fn bucket_num(&self, word: usize) -> usize {
word & (self.0.len() - 1)
}
unsafe fn insert(&mut self, item: *mut u8, meta: &Metadata) -> bool {
fn hash_ptr(p: *mut Word) -> usize {
let p_num = p as usize;
let words = p_num >> 3;
let pages = words >> 18;
pages * words
}
let s = &*Slag::find(item, meta.total_bytes);
let rc_ptr = &s.rc as *const _ as *mut RefCount;
let (word, word_ix) = Slag::get_word(s.as_raw(), item, meta);
let word_ptr = ((s.as_raw() as *mut u8).offset(meta.bitset_offset) as *mut Word)
.offset(word);
let bucket_ind = self.bucket_num(hash_ptr(word_ptr));
let bucket = &mut *self.0.get(bucket_ind);
if bucket.rc.is_null() {
*bucket = RemoteFreeCell {
rc: rc_ptr,
word: word_ptr,
mask: 1 << word_ix,
};
self.1.push(bucket as *const _ as *mut u8);
return true;
}
if bucket.word == word_ptr {
bucket.mask |= 1 << word_ix;
return true;
}
false
}
}
pub struct MagazineCache<CA: CoarseAllocator> {
stack_size: usize,
s: PtrStack,
iter: AllocIter,
alloc: SlagAllocator<CA>,
coalescer: Coalescer,
}
impl<CA: CoarseAllocator> LazyInitializable for MagazineCache<CA> {
type Params = (*mut Metadata, usize, CA, RevocablePipe<Slag>);
fn init(&(meta, decommit, ref page_alloc, ref avail): &Self::Params) -> Self {
let salloc = SlagAllocator::partial_new(meta, decommit, page_alloc.clone(), avail.clone());
Self::new(salloc)
}
}
impl<CA: CoarseAllocator> LazyInitializable for LocalCache<CA> {
type Params = (*mut Metadata, usize, CA, RevocablePipe<Slag>);
fn init(&(meta, decommit, ref page_alloc, ref avail): &Self::Params) -> Self {
let salloc = SlagAllocator::partial_new(meta, decommit, page_alloc.clone(), avail.clone());
Self::new(salloc)
}
}
impl<CA: CoarseAllocator> Drop for MagazineCache<CA> {
fn drop(&mut self) {
unsafe {
let meta = &*self.alloc.m;
let mask = self.iter.cur_word;
let word = self.iter.next_word.offset(-1);
let slag = self.alloc.slag;
self.alloc.bulk_free(mask, word, slag, meta);
for i in 0..self.s.top {
let item = *self.s.data.get(i);
self.alloc.free(item)
}
}
}
}
impl<CA: CoarseAllocator> Clone for MagazineCache<CA> {
fn clone(&self) -> Self {
MagazineCache::new_sized(self.alloc.clone(), self.stack_size)
}
}
impl<CA: CoarseAllocator> MagazineCache<CA> {
pub fn new_sized(mut alloc: SlagAllocator<CA>, magazine_size: usize) -> Self {
assert!(magazine_size > 0);
let s = PtrStack::new(magazine_size);
let iter = unsafe { alloc.refresh() };
let buckets = Coalescer::new(magazine_size * 2);
MagazineCache {
stack_size: magazine_size,
s: s,
iter: iter,
alloc: alloc,
coalescer: buckets,
}
}
pub fn new(alloc: SlagAllocator<CA>) -> Self {
use std::cmp;
unsafe {
const DEFAULT_MAGAZINE_BYTES: usize = 512 << 10;
let sz = DEFAULT_MAGAZINE_BYTES / (*alloc.m).object_size;
Self::new_sized(alloc, cmp::max(1, sz))
}
}
unsafe fn slag_alloc(&mut self) -> *mut u8 {
for _ in 0..2 {
match self.iter.next() {
Some(ptr) => return ptr,
None => self.iter = self.alloc.refresh(),
}
}
panic!("New slag is empty {:?} {:?}",
self.alloc.slag,
(*self.alloc.slag).rc.load())
}
pub unsafe fn alloc(&mut self) -> *mut u8 {
if let Some(ptr) = self.s.pop() {
trace_event!(cache_alloc);
ptr
} else {
trace_event!(slag_alloc);
self.slag_alloc()
}
}
pub unsafe fn free(&mut self, item: *mut u8) {
trace_event!(local_free);
if likely(self.s.top < self.stack_size) {
self.s.push(item);
return;
}
self.return_memory();
self.s.push(item);
}
unsafe fn return_memory(&mut self) {
debug_assert_eq!(self.s.top as usize, self.stack_size);
let new_top = self.stack_size / 2;
let meta = &*self.alloc.m;
for i in new_top..self.stack_size {
let item = *self.s.data.get(i);
if !self.coalescer.insert(item, meta) {
self.alloc.free(item)
}
}
self.s.top = new_top;
for cell_ptr in 0..self.coalescer.1.top {
let cell = &mut **(self.coalescer.1.data.get(cell_ptr) as *mut *mut RemoteFreeCell);
let slag = Slag::find(cell.rc as *mut u8, meta.total_bytes);
self.alloc.bulk_free(cell.mask, cell.word, slag, meta);
ptr::write(cell, RemoteFreeCell::default());
}
self.coalescer.1.top = 0;
}
}
pub struct LocalCache<CA: CoarseAllocator> {
alloc: SlagAllocator<CA>,
vals: PtrStack,
iter: AllocIter,
}
impl<CA: CoarseAllocator> Drop for LocalCache<CA> {
fn drop(&mut self) {
unsafe {
let meta = &*self.alloc.m;
let mask = self.iter.cur_word;
let word = self.iter.next_word.offset(-1);
let slag = self.alloc.slag;
self.alloc.bulk_free(mask, word, slag, meta);
for i in 0..self.vals.top {
let item = *self.vals.data.get(i);
self.alloc.free(item)
}
}
}
}
impl<CA: CoarseAllocator> Clone for LocalCache<CA> {
fn clone(&self) -> LocalCache<CA> {
LocalCache::new(self.alloc.clone())
}
}
impl<CA: CoarseAllocator> LocalCache<CA> {
fn new(mut alloc: SlagAllocator<CA>) -> Self {
unsafe {
let stack = PtrStack::new((*alloc.m).n_objects);
let iter = alloc.refresh();
LocalCache {
alloc: alloc,
vals: stack,
iter: iter,
}
}
}
pub unsafe fn free(&mut self, it: *mut u8) {
if self.alloc.contains(it) {
self.vals.push(it);
} else {
self.alloc.free(it);
}
}
pub unsafe fn alloc(&mut self) -> *mut u8 {
self.vals
.pop()
.or_else(|| self.iter.next())
.unwrap_or_else(|| {
let next_iter = self.alloc.refresh();
self.iter = next_iter;
self.iter.next().expect("New iterator should have values")
})
}
}
#[derive(Debug)]
struct MapAddr(*mut u8, usize);
impl Drop for MapAddr {
fn drop(&mut self) {
use self::mmap::unmap;
unsafe {
unmap(self.0, self.1);
}
}
}
#[derive(Debug)]
pub struct Creek {
page_size: usize,
map_info: Arc<MapAddr>,
base: *mut u8,
bump: AtomicPtr<AtomicUsize>,
}
unsafe impl Send for MapAddr {}
unsafe impl Sync for MapAddr {}
unsafe impl Send for Creek {}
unsafe impl Sync for Creek {}
macro_rules! check_bump {
($slf:expr) => {
#[cfg(debug_assertions)]
{
let bump = $slf.bump.load(Ordering::Relaxed);
debug_assert!(!bump.is_null());
}
};
}
impl MemoryBlock for Creek {
#[inline]
fn page_size(&self) -> usize {
check_bump!(self);
self.page_size
}
fn carve(&self, npages: usize) -> *mut u8 {
check_bump!(self);
unsafe {
let new_bump = self.bump
.load(Ordering::Relaxed)
.as_ref()
.unwrap()
.fetch_add(npages, Ordering::Relaxed);
assert!((new_bump + npages) * self.page_size < self.map_info.1,
"address space allocation exceeded");
self.base.offset((new_bump * self.page_size) as isize)
}
}
fn contains(&self, it: *mut u8) -> bool {
check_bump!(self);
let it_num = it as usize;
let base_num = self.base as usize;
it_num >= base_num && it_num < base_num + self.map_info.1
}
fn new(page_size: usize) -> Self {
use self::mmap::fallible_map;
let get_heap = || {
let mut heap_size: usize = 2 << 40;
while heap_size > (1 << 30) {
if let Some(heap) = fallible_map(heap_size) {
return (heap, heap_size);
}
heap_size /= 2;
}
panic!("unable to map heap")
};
assert!(page_size.is_power_of_two());
assert!(page_size > mem::size_of::<usize>());
let (orig_base, heap_size) = get_heap();
info!("created heap of size {}", heap_size);
let orig_addr = orig_base as usize;
let (slush_addr, real_addr) = {
let base = if orig_addr == 0 {
orig_addr + page_size
} else if orig_addr % page_size != 0 {
let rem = orig_addr % page_size;
orig_addr + (page_size - rem)
} else {
orig_addr
};
(base as *mut u8, (base + page_size) as *mut u8)
};
Creek {
page_size: page_size,
map_info: Arc::new(MapAddr(orig_base, heap_size)),
base: real_addr,
bump: AtomicPtr::new(slush_addr as *mut AtomicUsize),
}
}
}
impl Clone for Creek {
fn clone(&self) -> Self {
let bump = self.bump.load(Ordering::Relaxed);
debug_assert!(!bump.is_null());
Creek {
page_size: self.page_size,
map_info: self.map_info.clone(),
base: self.base,
bump: AtomicPtr::new(bump),
}
}
}
pub trait DirtyFn: Clone {
fn dirty(mem: *mut u8);
}
impl DirtyFn for () {
#[inline(always)]
fn dirty(_mem: *mut u8) {}
}
#[derive(Clone)]
pub struct PageAlloc<C: MemoryBlock, D = ()>
where D: DirtyFn
{
target_overhead: usize,
creek: C,
clean: SlagPipe<u8>,
dirty: SlagPipe<u8>,
_marker: PhantomData<D>,
}
impl<C: MemoryBlock, D: DirtyFn> PageAlloc<C, D> {
pub fn new(page_size: usize, target_overhead: usize) -> Self {
let mut res = PageAlloc {
target_overhead: target_overhead,
creek: C::new(page_size),
clean: SlagPipe::new_size(2),
dirty: SlagPipe::new_size(8),
_marker: PhantomData,
};
res.refresh_pages();
res
}
fn refresh_pages(&mut self) {
let creek = &self.creek;
let iter = (0..4).map(|_| creek.carve(1));
self.clean.bulk_add(iter);
}
}
impl<C: MemoryBlock, D: DirtyFn> CoarseAllocator for PageAlloc<C, D> {
type Block = C;
fn backing_memory(&self) -> &C {
&self.creek
}
unsafe fn alloc(&mut self) -> *mut u8 {
if let Ok(ptr) = self.dirty.try_pop_mut() {
trace_event!(grabbed_dirty);
return ptr;
}
loop {
if let Ok(ptr) = self.clean.try_pop_mut() {
trace_event!(grabbed_clean);
D::dirty(ptr);
return ptr;
}
self.refresh_pages();
}
}
unsafe fn free(&mut self, ptr: *mut u8, decommit: bool) {
const MINOR_PAGE_SIZE: isize = 4096;
use self::mmap::uncommit;
use std::cmp;
if decommit || self.dirty.size_guess() >= self.target_overhead as isize {
let uncommit_len = cmp::max(0,
self.backing_memory().page_size() as isize -
MINOR_PAGE_SIZE) as usize;
if uncommit_len == 0 {
self.dirty.push_mut(ptr);
} else {
uncommit(ptr.offset(MINOR_PAGE_SIZE), uncommit_len);
self.dirty.push_mut(ptr);
}
} else {
self.dirty.push_mut(ptr);
}
}
}
struct PtrStack {
data: OwnedArray<*mut u8>,
top: usize,
}
impl PtrStack {
fn new(max_objects: usize) -> PtrStack {
PtrStack {
data: OwnedArray::new(max_objects),
top: 0,
}
}
unsafe fn push(&mut self, item: *mut u8) {
*self.data.get(self.top) = item;
self.top += 1;
}
unsafe fn pop(&mut self) -> Option<*mut u8> {
if self.empty() {
None
} else {
self.top -= 1;
Some(*self.data.get(self.top))
}
}
#[inline]
fn empty(&self) -> bool {
self.top == 0
}
}
pub struct AllocBuilder<T> {
cutoff_factor: f64,
page_size: usize,
target_overhead: usize,
eager_decommit_threshold: usize,
max_objects: usize,
_marker: PhantomData<T>,
}
impl<T> Default for AllocBuilder<T> {
fn default() -> Self {
AllocBuilder {
cutoff_factor: 0.6,
page_size: cmp::max(32 << 10, mem::size_of::<T>() * 4),
target_overhead: 1 << 20,
eager_decommit_threshold: 128 << 10,
max_objects: 1 << 30,
_marker: PhantomData,
}
}
}
impl<T> AllocBuilder<T> {
pub fn cutoff_factor(&mut self, cutoff_factor: f64) -> &mut Self {
self.cutoff_factor = cutoff_factor;
self
}
pub fn page_size(&mut self, page_size: usize) -> &mut Self {
self.page_size = page_size;
self
}
pub fn target_overhead(&mut self, target_overhead: usize) -> &mut Self {
self.target_overhead = target_overhead;
self
}
pub fn eager_decommit_threshold(&mut self, eager_decommit_threshold: usize) -> &mut Self {
self.eager_decommit_threshold = eager_decommit_threshold;
self
}
pub fn max_objects(&mut self, max_objects: usize) -> &mut Self {
self.max_objects = max_objects;
self
}
pub fn build_local(&self) -> LocalAllocator<T> {
LocalAllocator::new_standalone(self.cutoff_factor,
self.page_size,
self.target_overhead,
self.eager_decommit_threshold,
self.max_objects)
}
pub fn build_magazine(&self) -> MagazineAllocator<T> {
MagazineAllocator::new_standalone(self.cutoff_factor,
self.page_size,
self.target_overhead,
self.eager_decommit_threshold,
self.max_objects)
}
}
macro_rules! typed_wrapper {
($name:ident, $wrapped:tt) => {
pub struct $name<T>($wrapped<PageAlloc<Creek>>, PhantomData<T>);
impl<T> Clone for $name<T> {
fn clone(&self) -> Self {
$name(self.0.clone(), PhantomData)
}
}
impl<T> $name<T> {
pub fn new_standalone(cutoff_factor: f64,
page_size: usize,
target_overhead: usize,
eager_decommit: usize,
max_objects: usize)
-> Self {
let pa = PageAlloc::new(page_size, target_overhead);
let slag = SlagAllocator::new(max_objects, mem::size_of::<T>(), 0,
cutoff_factor, eager_decommit, pa);
$name($wrapped::new(slag), PhantomData)
}
pub unsafe fn alloc(&mut self) -> *mut T {
self.0.alloc() as *mut T
}
pub unsafe fn free(&mut self, item: *mut T) {
self.0.free(item as *mut u8)
}
}
unsafe impl<T> Send for $name<T> {}
};
}
typed_wrapper!(LocalAllocator, LocalCache);
typed_wrapper!(MagazineAllocator, MagazineCache);
pub struct SlagAllocator<CA: CoarseAllocator> {
m: *mut Metadata,
slag: *mut Slag,
pages: CA,
available: RevocablePipe<Slag>,
eager_decommit_threshold: usize,
}
impl<CA: CoarseAllocator> Drop for SlagAllocator<CA> {
fn drop(&mut self) {
unsafe {
let slag = self.slag;
let meta = &*self.m;
let (claimed, was) = (*slag).rc.unclaim();
if claimed {
if was == meta.n_objects {
self.pages.free(slag as *mut u8, false);
trace_event!(transition_full);
} else if was >= meta.cutoff_objects {
self.transition_available(slag)
}
} else {
self.pages.free(slag as *mut u8, false);
}
}
}
}
unsafe impl<C: CoarseAllocator + Send> Send for SlagAllocator<C> {}
impl<CA: CoarseAllocator> SlagAllocator<CA> {
pub fn partial_new(meta: *mut Metadata,
decommit: usize,
mut pa: CA,
avail: RevocablePipe<Slag>)
-> Self {
let first_slag = unsafe { pa.alloc() } as *mut Slag;
unsafe {
Slag::init(first_slag, meta.as_ref().unwrap());
};
SlagAllocator {
m: meta,
slag: first_slag,
pages: pa,
available: avail,
eager_decommit_threshold: decommit,
}
}
pub fn new(max_objects: usize,
object_size: usize,
index: usize,
cutoff_factor: f64,
eager_decommit: usize,
mut pa: CA)
-> Self {
let meta = Box::into_raw(Box::new(compute_metadata(object_size,
pa.backing_memory().page_size(),
index,
cutoff_factor,
max_objects)));
let first_slag = unsafe { pa.alloc() } as *mut Slag;
unsafe {
Slag::init(first_slag, meta.as_ref().unwrap());
};
SlagAllocator {
m: meta,
slag: first_slag,
pages: pa,
available: RevocablePipe::new(),
eager_decommit_threshold: eager_decommit,
}
}
unsafe fn refresh(&mut self) -> AllocIter {
let s_ref = &*self.slag;
let meta = &*self.m;
let (_claimed, was) = s_ref.rc.unclaim();
debug_assert_eq!(*meta, *(*s_ref).meta.load(Ordering::Relaxed));
if was >= meta.cutoff_objects {
let _claimed = s_ref.rc.claim();
debug_assert!(_claimed,
"claiming slag either during initialization or due to being over cutoff");
s_ref.refresh(meta)
} else {
let next_slab = match self.available.try_pop_mut() {
Ok(slab) => {
trace_event!(grabbed_available);
slab
}
Err(_) => {
let new_raw = self.pages.alloc() as *mut Slag;
if (*new_raw).meta.load(Ordering::Relaxed) != self.m {
Slag::init(new_raw, meta);
}
new_raw
}
};
self.slag = next_slab;
let s_ref = self.slag.as_mut().expect("s_ref_2"); let claimed = s_ref.rc.claim();
debug_assert!(claimed, "claiming new slag after refresh");
s_ref.refresh(meta)
}
}
fn transition_available(&mut self, slag: *mut Slag) {
trace_event!(transition_available);
self.available.push_mut(slag)
}
#[cfg_attr(feature = "cargo-clippy", allow(inline_always))]
#[inline(always)]
unsafe fn transition_full(&mut self, slag: *mut Slag, meta: &Metadata) {
let real_size = meta.usable_size;
if RevocablePipe::revoke(&slag) {
trace_event!(transition_full);
self.pages
.free(slag as *mut u8, real_size >= self.eager_decommit_threshold)
}
}
unsafe fn bulk_free(&mut self,
mask: usize,
word: *mut Word,
slag: *mut Slag,
meta: &Metadata) {
let n_ones = mask.count_ones() as usize;
if n_ones == 0 {
return;
}
trace_event!(bulk_remote_free);
let s_ref = &*slag;
let (claimed, was) = s_ref.rc.inc_n(n_ones);
let before = (*word).fetch_or(mask, Ordering::Release);
debug_assert_eq!(before & mask,
0,
"Invalid mask: transitioned\n{:064b} with \n{:064b}",
before,
mask);
let now = was + n_ones;
if !claimed {
if now == meta.n_objects {
self.transition_full(slag, meta);
} else if was < meta.cutoff_objects && now >= meta.cutoff_objects {
self.transition_available(slag);
}
}
}
unsafe fn free(&mut self, item: *mut u8) {
trace_event!(remote_free);
let meta = &*self.m;
let it_slag = Slag::find(item, meta.total_bytes);
match it_slag.as_ref().unwrap().free(item) {
Transition::Null => return,
Transition::Available => self.transition_available(it_slag),
Transition::Full => self.transition_full(it_slag, meta),
}
}
fn contains(&self, it: *mut u8) -> bool {
unsafe {
let meta = self.m.as_ref().unwrap();
let it_slag = Slag::find(it, meta.total_bytes);
it_slag == self.slag
}
}
}
impl<CA: CoarseAllocator> Clone for SlagAllocator<CA> {
fn clone(&self) -> Self {
let mut new_page_handle = self.pages.clone();
let first_slag = unsafe { new_page_handle.alloc() as *mut Slag };
unsafe {
Slag::init(first_slag, self.m.as_ref().unwrap());
};
SlagAllocator {
m: self.m,
slag: first_slag,
pages: new_page_handle,
available: self.available.clone(),
eager_decommit_threshold: self.eager_decommit_threshold,
}
}
}
#[cfg(test)]
mod tests {
extern crate env_logger;
use super::*;
use std::thread;
use std::ptr::write_volatile;
use std::collections::HashSet;
#[test]
fn metadata_basic() {
let _ = env_logger::init();
compute_metadata(8, 4096, 0, 0.8, 4);
compute_metadata(16, 4096, 0, 0.8, 1024);
compute_metadata(24, 4096, 0, 0.8, 1024);
compute_metadata(127, 4096, 0, 0.8, 1024);
compute_metadata(800, 2 << 20, 0, 0.8, 32 << 10);
compute_metadata(514, 4096, 0, 0.8, 1024);
compute_metadata(513, 2 << 20, 0, 0.8, 1024);
compute_metadata(768, 4096, 0, 0.8, 1024);
compute_metadata(800, 4096, 0, 0.8, 32 << 10);
compute_metadata(1025, 4096, 0, 0.8, 32 << 10);
}
#[test]
fn obj_alloc_basic() {
let _ = env_logger::init();
let mut oa = AllocBuilder::<usize>::default()
.page_size(4096)
.build_local();
unsafe {
let item = oa.alloc();
write_volatile(item, 10);
oa.free(item);
}
}
#[test]
fn obj_alloc_many_pages_single_threaded_usize() {
obj_alloc_many_pages_single_threaded::<usize>();
}
#[test]
fn obj_alloc_many_pages_single_threaded_u24() {
obj_alloc_many_pages_single_threaded::<[u8; 24]>();
}
#[test]
fn obj_alloc_many_pages_single_threaded_u32() {
obj_alloc_many_pages_single_threaded::<[u8; 32]>();
}
fn obj_alloc_many_pages_single_threaded<T: 'static>() {
let _ = env_logger::init();
const N_ITEMS: usize = 4096 * 20;
let mut oa = AllocBuilder::<T>::default().page_size(4096).build_local();
assert!(mem::size_of::<T>() >= mem::size_of::<usize>());
for _ in 0..N_ITEMS {
unsafe {
let item = oa.alloc();
write_volatile(item as *mut usize, 10);
oa.free(item);
}
}
let mut v = Vec::with_capacity(N_ITEMS);
let mut h = HashSet::new();
for i in 0..N_ITEMS {
unsafe {
let item = oa.alloc();
write_volatile(item as *mut usize, i + 1);
v.push(item);
let item_num = item as usize;
assert!(!h.contains(&item_num));
h.insert(item_num);
}
}
for i in v {
unsafe {
oa.free(i);
}
}
}
#[test]
fn obj_alloc_many_pages_many_threads_usize() {
obj_alloc_many_pages_many_threads::<usize>()
}
#[test]
fn obj_alloc_many_pages_many_threads_u24() {
obj_alloc_many_pages_many_threads::<[u8; 24]>()
}
#[test]
fn obj_alloc_many_pages_many_threads_u32() {
obj_alloc_many_pages_many_threads::<[u8; 32]>()
}
fn obj_alloc_many_pages_many_threads<T: 'static>() {
let _ = env_logger::init();
use std::mem;
const N_ITEMS: usize = 4096 * 4;
const N_THREADS: usize = 40;
let oa = AllocBuilder::<T>::default()
.page_size(4096)
.build_magazine();
assert!(mem::size_of::<T>() >= mem::size_of::<usize>());
let mut threads = Vec::new();
for _ in 0..N_THREADS {
let mut my_alloc = oa.clone();
threads.push(thread::spawn(move || {
for _ in 0..N_ITEMS {
unsafe {
let item = my_alloc.alloc();
write_volatile(item as *mut usize, 10);
my_alloc.free(item);
}
}
let mut v = Vec::with_capacity(N_ITEMS);
let mut h = HashSet::new();
for i in 0..N_ITEMS {
unsafe {
let item = my_alloc.alloc();
write_volatile(item as *mut usize, i);
v.push(item);
let item_num = item as usize;
assert!(!h.contains(&item_num));
h.insert(item_num);
}
}
for i in v {
unsafe {
my_alloc.free(i);
}
}
}));
}
for t in threads {
t.join().expect("threads should exit successfully");
}
}
}