Skip to content

Instantly share code, notes, and snippets.

@wtholliday wtholliday/Collector.cpp
Last active Dec 18, 2015

Embed
What would you like to do?
A simple concurrent mark-sweep garbage collector. Requires manual management of the referential graph. I'm confident it works for a single mutator thread, but not sure about multiple mutator threads. Requires boost::lockfree.
//
// Collector.cpp
// Dev
//
// Created by Taylor Holliday on 6/14/13.
// This file is in the public domain.
//
#include "gc2/Collector.hpp"
Collector Collector::collector;
Collector& Collector::GetInstance() {
return collector;
}
Collector::Collector() : _eventQueue(new boost::lockfree::queue<Event>(128)) { }
void Collector::AddRoot(Collectable* node) {
Event e;
e.type = Event::AddRoot;
e.a = node;
_eventQueue->push(e);
}
void Collector::RemoveRoot(Collectable* node) {
Event e;
e.type = Event::RemoveRoot;
e.a = node;
_eventQueue->push(e);
}
void Collector::AddEdge(Collectable* a, Collectable* b) {
Event e;
e.type = Event::Connect;
e.a = a;
e.b = b;
_eventQueue->push(e);
}
void Collector::RemoveEdge(Collectable* a, Collectable* b) {
Event e;
e.type = Event::Disconnect;
e.a = a;
e.b = b;
_eventQueue->push(e);
}
void Collector::_ProcessEvents() {
Event e;
while(_eventQueue->pop(e)) {
switch (e.type) {
case Event::AddRoot: {
_nodes.insert(e.a);
e.a->gcRootCount++;
}
break;
case Event::RemoveRoot: {
e.a->gcRootCount--;
// Root count must be positive.
assert(e.a->gcRootCount >= 0);
}
break;
case Event::Connect: {
e.a->gcConnections.push_back(e.b);
}
break;
case Event::Disconnect: {
std::vector<Collectable*>& adj = e.a->gcConnections;
auto iter = std::find(adj.begin(), adj.end(), e.b);
// The connection must exist.
assert(iter != e.a->gcConnections.end());
adj.erase(iter);
}
break;
default:
break;
}
}
}
void Collector::Collect() {
_ProcessEvents();
static size_t sequence = 0;
sequence++;
std::vector<Collectable*> nodeStack;
// Traverse starting with roots.
for (auto node : _nodes) {
if(node->gcRootCount) {
nodeStack.push_back(node);
}
}
// Mark.
while(not nodeStack.empty()) {
Collectable* node = nodeStack.back();
nodeStack.pop_back();
if(node->gcSequence != sequence) {
node->gcSequence = sequence;
for(auto adj : node->gcConnections) {
nodeStack.push_back(adj);
}
}
}
// Sweep.
std::set<Collectable*> newNodes;
for(auto node : _nodes) {
// Not visited.
if (node->gcSequence != sequence) {
delete node;
} else {
newNodes.insert(node);
}
}
_nodes = newNodes;
}
//
// Collector.h
// Dev
//
// Created by Taylor Holliday on 6/14/13.
// This file is in the public domain.
//
#ifndef __Dev__Collector__
#define __Dev__Collector__
#include <set>
#include <vector>
#include <boost/lockfree/queue.hpp>
// Derive from Collectable if you'd like an object
// to be garbage collected.
struct Collectable {
Collectable() : gcRootCount(0), gcSequence(0) { }
virtual ~Collectable() { }
// Connections as seen by the garbage collector.
std::vector<Collectable*> gcConnections;
// How many times is this node referenced as
// a root.
int gcRootCount;
// Sequence number used to determine if
// the Collectable has been visited in the
// current round of GC.
size_t gcSequence;
};
// The garbage collector. A singleton.
//
// Collector is a mark-sweep garbage collector
// that can be run concurrently in a background
// thread.
//
class Collector {
public:
// Get the singleton instance.
static Collector& GetInstance();
// Add a reference to a root collectable.
void AddRoot(Collectable*);
// Remove a reference to a root collectable.
void RemoveRoot(Collectable*);
// Notify the collector of a new reference
// between Collectables.
void AddEdge(Collectable*, Collectable*);
// Remove a reference between Collectables.
void RemoveEdge(Collectable*, Collectable*);
// Collect garbage. Make sure you only call
// this from one thread at a time.
void Collect();
private:
Collector();
// An event to update the collectors
// own representation of the graph.
struct Event {
enum Type {
AddRoot,
RemoveRoot,
Connect,
Disconnect
};
Type type;
Collectable* a;
Collectable* b;
};
boost::lockfree::queue<Event>* _eventQueue;
// All the nodes we've seen.
std::set<Collectable*> _nodes;
void _ProcessEvents();
static Collector collector;
};
// When passing references to Collectables
// on the stack, always use RootPtr.
template<typename T>
struct RootPtr {
T* _ptr;
RootPtr() : _ptr(0) { }
explicit RootPtr(T* ptr) : _ptr(ptr) {
_Retain();
}
RootPtr(const RootPtr& other) : _ptr(other._ptr) {
_Retain();
}
template<class T2>
RootPtr(const RootPtr<T2>& other) : _ptr(other._ptr) {
_Retain();
}
~RootPtr() {
_Release();
}
RootPtr& operator=(const RootPtr& other) {
if(this != &other) {
_Release();
_ptr = other._ptr;
_Retain();
}
return *this;
}
template<class T2>
RootPtr& operator=(const RootPtr<T2>& other) {
if(this != &other) {
_Release();
_ptr = other._ptr;
_Retain();
}
return *this;
}
T& operator*() { return *_ptr; }
T* operator->() const { assert(_ptr); return _ptr; }
operator T*() { return _ptr; }
operator bool() const { return _ptr != 0; }
bool operator==(const RootPtr& other) const {
return _ptr == other._ptr;
}
bool operator!=(const RootPtr& other) const {
return _ptr != other._ptr;
}
bool operator<(const RootPtr& other) const {
return _ptr < other._ptr;
}
void _Retain() {
if(_ptr) {
Collector::GetInstance().AddRoot(_ptr);
}
}
void _Release() {
if(_ptr) {
Collector::GetInstance().RemoveRoot(_ptr);
}
}
}; // class RootPtr
#endif /* defined(__Dev__Collector__) */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.