This has been a HUGE learning curve for me as I have never implemented automatic garbage collection in C++ before. Here is another installment and a collector that no longer leaks memory (blush).
Also check out the VSPL/Language development index page.
FYI - the picture has absolutely nothing to do with this post other than it is about a pointer!
As I mentioned before, the garbage collector for my referrence VSPL/C++ implementation is just a reference counter. Actually, I say 'just' but reference counters are becoming a hot topic again. There are places where 'stop the world' garbage collection is not really the best approach. First of all, mark/scan garbage collection has to traverse the whole heap which can be expensive which very large programs and massive object counts. Also, games and real time applications cannot have 'stop the world' methodologies. So, despite the drawbacks, reference counting might prove to be the garbage collector of choice for many applications moving forward.
VSPL has been designed to be threaded from day one, this means its garbage collection needs to be thread safe. To achive this I implemented atomic operations for the reference increment and decrement. However, some operands in VSPL need to actually be reference counted even though they are still passed as VSPL_OPERAND counted pointer objects. These operand closely relate to constants in other languages; also there is no point counting null pointers. So, I implmeneted the ability for the counted pointer not to bother counting is it was in 'permanent' mode. Unfortunately, I made a simple mistake of still calling new for the counter memory its self, even though the counter pointer was not counting. This new memory was never reclaimed. A little bit of code fixed this and the approach works very cleanly now:
This leaks like a sive:
:ptr(p), count(new VSPL_INT(1)),useCount(p!=0)
This does not:
:ptr(p), count(p!=0?new VSPL_INT(1):0),useCount(p!=0)
Again...
Leaky:
:ptr(p), count(new VSPL_INT(1)),useCount(!permanent)
Clean:
:ptr(p), count(permanent?0:new VSPL_INT(1)),useCount(!permanent)
The next advance I've made is to have a tracing and non tracing version. The tracing version uses RTTI (run time type identification) to keep track of what counted pointers are in existance and to what objects they pointer. It keeps a separate track of the permanent and referece counted versions. This means that if memory appears to be leaking in the program you can define VSPL_MEMTRACE and recompile and then call DumpCReferences for counted references or DumpPReferences for permanent references to see what references are actually active. Here is an example of the output, first the counted reference system showing creating and deleting of objects.
Deleting->00339170 class VSPL::cVSPL_List
Creating->00339170 class VSPL::cVSPL_Number
Creating->0033A958 class VSPL::cVSPL_List
Deleting->0033B308 class VSPL::cVSPL_List
Deleting->0033B150 class VSPL::cVSPL_Number
Creating->0033A858 class VSPL::cVSPL_List
Deleting->0033A958 class VSPL::cVSPL_List
Creating->0033A958 class VSPL::cVSPL_List
Deleting->0033A858 class VSPL::cVSPL_List
Creating->0033B330 class VSPL::cVSPL_Number
Creating->0033B358 class VSPL::cVSPL_List
Deleting->0033A958 class VSPL::cVSPL_List
Deleting->00339170 class VSPL::cVSPL_Number
Deleting->0033A9E8 class VSPL::cVSPL_RunnerOperand
Creating->00339198 class VSPL::cVSPL_Number
Creating->0033B078 class VSPL::cVSPL_List
Deleting->0033B358 class VSPL::cVSPL_List
Creating->0033A858 class VSPL::cVSPL_Number
Next the dump of permanent and counted objects near the end of the execution of the program:
All known counted references
00335360->class VSPL::cVSPL_Parser::cNothing
003353E8->class VSPL::cVSPL_Parser::cTrue
00335468->class VSPL::cVSPL_Parser::cFalse
003356E8->class VSPL::cVSPL_StdLib::cGt
00335788->class VSPL::cVSPL_StdLib::cSum
00335A08->class VSPL::cVSPL_StdLib::cDiff
00335BA0->class VSPL::cVSPL_StdLib::cQuot
00335D38->class VSPL::cVSPL_StdLib::cProd
00335ED0->class VSPL::cVSPL_StdLib::cTimer
00336068->class VSPL::cVSPL_ExtLib::cPrint
00336750->class VSPL::cVSPL_Parser::cPushAccumulator
003380F8->class VSPL::cVSPL_Parser::cPopAccumulator
00338418->class VSPL::cVSPL_Parser::cAppend
00338458->class VSPL::cVSPL_Parser::cGet
003384F8->class VSPL::cVSPL_Parser::cIf
00338778->class VSPL::cVSPL_Parser::cElse
00338910->class VSPL::cVSPL_Parser::cInvoke
00338AA8->class VSPL::cVSPL_Parser::cLoop
00338B48->class VSPL::cVSPL_Parser::cCall
00338DC8->class VSPL::cVSPL_Parser::cInterpret
00339230->class VSPL::cVSPL_Parser::cStore
00339528->class VSPL::cVSPL_Parser::cNumber
00339658->class VSPL::cVSPL_Parser::cRetrieve
003396B0->class VSPL::cVSPL_Parser::cStore
00339B48->class VSPL::cVSPL_Parser::cRetrieve
00339C58->class VSPL::cVSPL_Parser::cStore
00339E08->class VSPL::cVSPL_Parser::cNumber
0033A0B8->class VSPL::cVSPL_Runner
0033A5D8->class VSPL::cVSPL_Runner
0033ADD8->class VSPL::cVSPL_Parser::cNumber
All known permanent references
00336310->class VSPL::cVSPL_Bool
003380A8->class VSPL::cVSPL_Bool
003395C0->class VSPL::cVSPL_Number
00339BE8->class VSPL::cVSPL_Number
0033AE20->class VSPL::cVSPL_Number
The above was generated whilst running the following VSPL:
Timer !time 100 !count [ ?count,1>Diff !count,0>Gt ] Loop Timer,?time>Diff Print
Finally, here is the counted reference code. Notes:
- VSPL_INT is just int on Win32
- The tracing class has to cope with counted pointers being created static and
so it must create its MAP containers when they are needed rather than in the class
initializer. I was in a bit of a hurry (and it if only debug code) as I just assumed a boolean will start of false and used that to control creating the maps. C++ says uninitialized memory can have any value, but Windows (and Linux I think) zeros it (which is false in bool). Anyhow, oneday I will go look up a better method of handling this.
- The RTTI spec only seems to say that the name() returns a null turminated byte string. So
std::string(typeid(*(this->ptr)).name()) may or may not produce a string usable for tracing. I have just made the assumption that it will and so far it works on Windows. I am starting to think of making a Linux version if time permits.
/* The below is the start of a linux version which uses atomicity.h
to provide the atomic increment and decrement of the reference count.*/
//#define GPP_MEMORY_MODEL
#ifdef GPP_MEMORY_MODEL
inline VSPL_INT InterlockedIncrement(VSPL_INT* count)
{
__atomic_add((_Atomic_word*)cout,1);
return *count;
}
inline VSPL_INT InterlockedDecrement(VSPL_INT* count)
{
__atomic_add((_Atomic_word*)cout,-1);
return *count;
}
#endif
#ifdef VSPL_MEMTRACE
/* This class stores the information required for memory tracing
* and does the pretty print of the memory trace
*/
class MemTracer
{
private:
static bool isInit;
static void Init()
{
// This works on Windows - no reason to suspect
// it will work anywhere else!
if(!isInit)
{
cReferences=new std::map<std::string,std::string>();
pReferences=new std::map<std::string,std::string>();
isInit=true;
}
}
static std::map<std::string,std::string>* cReferences;
static std::map<std::string,std::string>* pReferences;
public:
static void DumpCReferences()
{
Init();
for
(
std::map<std::string,std::string>::iterator it=cReferences->begin();
it!=cReferences->end();
++it
)
{
std::cout << it->first << "->" << it->second << std::endl;
}
}
static void DumpPReferences()
{
Init();
for
(
std::map<std::string,std::string>::iterator it=pReferences->begin();
it!=pReferences->end();
++it
)
{
std::cout << it->first << "->" << it->second << std::endl;
}
}
static void SetCReference(std::string& k,std::string& v)
{
Init();
(*MemTracer::cReferences)[k]=v;
}
static void SetPReference(std::string& k,std::string& v)
{
Init();
(*MemTracer::pReferences)[k]=v;
}
static void RemoveCReference(std::string& k)
{
std::map<std::string,std::string>::iterator it=MemTracer::cReferences->find(k);
MemTracer::cReferences->erase(it);
}
};
/* This is the tracing verion of the counted pointer */
template <class T>
class CountedPtr
{
private:
// I have put this first to double ensure it is 32(or 64) bit
// aligned for the memory barrier - this is the ref count for
// this counted pointer
VSPL_INT* count;
// This points to what ever this pointer points to
T* ptr;
// This sets if the counting part of this pointer is disabled.
// Having this set to false means that the ref count is not used
// which is what we want if we _know_ an object never needs to
// be garbage collected so the cost of thread safe ref counting
// need not be incured.
VSPL_BOOL useCount;
public:
// Note that quite often a counted reference is created and
// then a value set to it with the = operator. This means that
// this constructor will be called with p=0 (NULL) as default.
// When this happens - there is no point reference counting a
// pointer to null - so the useCount is then to FALSE when p=0
// and true otherwise.
explicit CountedPtr(T* p=0)
:ptr(p), count(p!=0?new VSPL_INT(1):0),useCount(p!=0)
{
if(useCount)
{
std::cout << "Creating->" << this->ptr << " " << typeid(*(this->ptr)).name() << std::endl;
MemTracer::SetCReference(ToString(this->ptr),std::string(typeid(*(this->ptr)).name()));
}
else
{
if(p!=0)
MemTracer::SetPReference(ToString(this->ptr),std::string(typeid(*(this->ptr)).name()));
}
}
CountedPtr(T* p,VSPL_BOOL permanent)
:ptr(p), count(permanent?0:new VSPL_INT(1)),useCount(!permanent)
{
if(useCount)
{
std::cout << "Creating->" << this->ptr << " " << typeid(this->ptr).name() << std::endl;
MemTracer::SetCReference(ToString(this->ptr),std::string(typeid(*(this->ptr)).name()));
}
else
{
if(p!=0)
MemTracer::SetPReference(ToString(this->ptr),std::string(typeid(*(this->ptr)).name()));
}
}
CountedPtr(const CountedPtr<T>& p) throw()
: ptr(p.ptr),count(p.count),useCount(p.useCount)
{
if(useCount)
{
InterlockedIncrement(count);
}
}
~CountedPtr() throw()
{
dispose();
}
CountedPtr<T>& operator=(const CountedPtr<T>& p) throw()
{
if(this != &p){
dispose();
ptr=p.ptr;
count=p.count;
useCount=p.useCount;
if(useCount)
{
InterlockedIncrement(count);
}
}
return *this;
}
T& operator*() const throw()
{
return *ptr;
}
T* operator->() const throw()
{
return ptr;
}
VSPL_BOOL IsNull()
{ return ptr==0; }
private:
void dispose()
{
if(useCount)
{
if(InterlockedDecrement(count) == 0)
{
std::cout << "Deleting->" << this->ptr << " " << typeid(*(this->ptr)).name() << std::endl;
MemTracer::RemoveCReference(ToString(this->ptr));
delete count;
delete ptr;
}
}
}
};
#else
/* The non tracing version for normal operations.
* This is infinitely faster, never use the tracing
* version unless you are debuging for leaks!
*/
template <class T>
class CountedPtr
{
private:
VSPL_INT* count;
T* ptr;
VSPL_BOOL useCount;
public:
explicit CountedPtr(T* p=0)
:ptr(p), count(p!=0?new VSPL_INT(1):0),useCount(p!=0){}
CountedPtr(T* p,VSPL_BOOL permanent)
:ptr(p), count(permanent?0:new VSPL_INT(1)),useCount(!permanent){}
CountedPtr(const CountedPtr<T>& p) throw()
: ptr(p.ptr),count(p.count),useCount(p.useCount)
{if(useCount)InterlockedIncrement(count);}
~CountedPtr() throw()
{dispose();}
CountedPtr<T>& operator=(const CountedPtr<T>& p) throw()
{
if(this != &p){
dispose();
ptr=p.ptr;
count=p.count;
useCount=p.useCount;
if(useCount) InterlockedIncrement(count);
}
return *this;
}
T& operator*() const throw()
{return *ptr;}
T* operator->() const throw()
{return ptr;}
VSPL_BOOL IsNull()
{ return ptr==0; }
private:
void dispose()
{
if(useCount)
{
if(InterlockedDecrement(count) == 0)
{
delete count;
delete ptr;
}
}
}
};
#endif
