blob: 9b66653ead6540e7f682b10e68de8aa72dbf1b9a [file] [log] [blame]
// Data structures for storing garbage to be freed later (once the
// epochs have sufficiently advanced).
//
// In general, we try to manage the garbage thread locally whenever
// possible. Each thread keep track of three bags of garbage. But if a
// thread is exiting, these bags must be moved into the global garbage
// bags.
use std::ptr;
use std::mem;
use std::sync::atomic::AtomicPtr;
use std::sync::atomic::Ordering::{Relaxed, Release, Acquire};
use ZerosValid;
/// One item of garbage.
///
/// Stores enough information to do a deallocation.
#[derive(Debug)]
struct Item {
ptr: *mut u8,
free: unsafe fn(*mut u8),
}
/// A single, thread-local bag of garbage.
#[derive(Debug)]
pub struct Bag(Vec<Item>);
impl Bag {
fn new() -> Bag {
Bag(vec![])
}
fn insert<T>(&mut self, elem: *mut T) {
let size = mem::size_of::<T>();
if size > 0 {
self.0.push(Item {
ptr: elem as *mut u8,
free: free::<T>,
})
}
unsafe fn free<T>(t: *mut u8) {
drop(Vec::from_raw_parts(t as *mut T, 0, 1));
}
}
fn len(&self) -> usize {
self.0.len()
}
/// Deallocate all garbage in the bag
pub unsafe fn collect(&mut self) {
let mut data = mem::replace(&mut self.0, Vec::new());
for item in data.iter() {
(item.free)(item.ptr);
}
data.truncate(0);
self.0 = data;
}
}
// needed because the bags store raw pointers.
unsafe impl Send for Bag {}
unsafe impl Sync for Bag {}
/// A thread-local set of garbage bags.
#[derive(Debug)]
pub struct Local {
/// Garbage added at least one epoch behind the current local epoch
pub old: Bag,
/// Garbage added in the current local epoch or earlier
pub cur: Bag,
/// Garbage added in the current *global* epoch
pub new: Bag,
}
impl Local {
pub fn new() -> Local {
Local {
old: Bag::new(),
cur: Bag::new(),
new: Bag::new(),
}
}
pub fn insert<T>(&mut self, elem: *mut T) {
self.new.insert(elem)
}
/// Collect one epoch of garbage, rotating the local garbage bags.
pub unsafe fn collect(&mut self) {
let ret = self.old.collect();
mem::swap(&mut self.old, &mut self.cur);
mem::swap(&mut self.cur, &mut self.new);
ret
}
pub fn size(&self) -> usize {
self.old.len() + self.cur.len() + self.new.len()
}
}
/// A concurrent garbage bag, currently based on Treiber's stack.
///
/// The elements are themselves owned `Bag`s.
#[derive(Debug)]
pub struct ConcBag {
head: AtomicPtr<Node>,
}
unsafe impl ZerosValid for ConcBag {}
#[derive(Debug)]
struct Node {
data: Bag,
next: AtomicPtr<Node>,
}
impl ConcBag {
pub fn insert(&self, t: Bag){
let n = Box::into_raw(Box::new(
Node { data: t, next: AtomicPtr::new(ptr::null_mut()) }));
loop {
let head = self.head.load(Acquire);
unsafe { (*n).next.store(head, Relaxed) };
if self.head.compare_and_swap(head, n, Release) == head { break }
}
}
pub unsafe fn collect(&self) {
// check to avoid xchg instruction
// when no garbage exists
let mut head = self.head.load(Relaxed);
if head != ptr::null_mut() {
head = self.head.swap(ptr::null_mut(), Acquire);
while head != ptr::null_mut() {
let mut n = Box::from_raw(head);
n.data.collect();
head = n.next.load(Relaxed);
}
}
}
}