GarbageCollector.cpp

#include <jetscript/GarbageCollector.h>
#include <jetscript/JetContext.h>

using namespace Jet;

//#define JETGCDEBUG

GarbageCollector::GarbageCollector(JetContext* context) : context(context)
{
	this->allocationCounter = 1;//messes up if these start at 0
	this->collectionCounter = 1;
}

void GarbageCollector::Cleanup()
{
	//need to do a two pass system to properly destroy userdata
	//first pass of destructing
	for (auto ii: this->gen1)
	{
		switch (ii->type)
		{
		case ValueType::Function:
		case ValueType::Object:
		case ValueType::Array:
		case ValueType::String:
			break;
		case ValueType::Userdata:
			{
				Value ud = Value(((JetUserdata*)ii), ((JetUserdata*)ii)->prototype);
				Value _gc = (*((JetUserdata*)ii)->prototype).get("_gc");
				if (_gc.type == ValueType::NativeFunction)
					_gc.func(this->context, &ud, 1);
				else if (_gc.type == ValueType::Function)
					throw RuntimeException("Non Native _gc Hooks Not Implemented!");//todo
				else if (_gc.type != ValueType::Null)
					throw RuntimeException("Invalid _gc Hook!");
				break;
			}
		}
	}

	for (auto ii: this->gen2)
	{
		switch (ii->type)
		{
		case ValueType::Function:
		case ValueType::Object:
		case ValueType::Array:
		case ValueType::String:
			break;
		case ValueType::Userdata:
			{
				Value ud = Value(((JetUserdata*)ii), ((JetUserdata*)ii)->prototype);
				Value _gc = (*((JetUserdata*)ii)->prototype).get("_gc");
				if (_gc.type == ValueType::NativeFunction)
					_gc.func(this->context, &ud, 1);
				else if (_gc.type == ValueType::Function)
					throw RuntimeException("Non Native _gc Hooks Not Implemented!");//todo
				else if (_gc.type != ValueType::Null)
					throw RuntimeException("Invalid _gc Hook!");
				break;
			}
		}
	}

	//delete everything else
	for (auto ii: this->gen1)
	{
		switch (ii->type)
		{
		case ValueType::Function:
			{
				Closure* fun = (Closure*)ii;
				if (fun->numupvals)
					delete[] fun->upvals;
				delete fun->generator;
				delete fun;
				break;
			}
		case ValueType::Object:
			delete (JetObject*)ii;
			break;
		case ValueType::Array:
			((JetArray*)ii)->data.~vector();
			delete[] (char*)ii;
			break;
		case ValueType::Userdata:
			//did in first pass
			delete (JetUserdata*)ii;
			break;
		case ValueType::String:
			{
				JetString* str = (JetString*)ii;
				delete[] str->data;
				delete str;
				break;
			}
		case ValueType::Capture:
			{
				Capture* c = (Capture*)ii;
				delete c;
				break;
			}
		}
	}

	for (auto ii: this->gen2)
	{
		switch (ii->type)
		{
		case ValueType::Function:
			{
				Closure* fun = (Closure*)ii;
				if (fun->numupvals)
					delete[] fun->upvals;
				delete fun->generator;
				delete fun;
				break;
			}
		case ValueType::Object:
			delete (JetObject*)ii;
			break;
		case ValueType::Array:
			delete ((JetArray*)ii);
			break;
		case ValueType::Userdata:
			//did in first pass
			delete (JetUserdata*)ii;
			break;
		case ValueType::String:
			{
				JetString* str = (JetString*)ii;
				delete[] str->data;
				delete str;
				break;
			}
		case ValueType::Capture:
			{
				Capture* c = (Capture*)ii;
				delete c;
				break;
			}
		}
	}
}

void GarbageCollector::Mark()
{
	//mark basic types
	this->greys.Push(context->Array);
	this->greys.Push(context->arrayiter);
	this->greys.Push(context->object);
	this->greys.Push(context->objectiter);
	this->greys.Push(context->string);
	this->greys.Push(context->function);

	for (unsigned int i = 0; i < this->context->prototypes.size(); i++)
		this->greys.Push(this->context->prototypes[i]);

	//mark all objects being held by native code
	for (unsigned int i = 0; i < this->nativeRefs.size(); i++)
	{
		if (this->nativeRefs[i]._object->grey == false)
		{
			this->nativeRefs[i]._object->grey = true;
			this->greys.Push(this->nativeRefs[i]);
		}
	}

	//add more write barriers to detect when objects are removed and what not
	//if flag is marked, then black
	//if no flag and grey bit, then grey
	//if no flag or grey bit, then white

	//push all reachable items onto grey stack
	//this means globals
	{
		//StackProfile profile("Mark Globals as Grey");
		for (unsigned int i = 0; i < context->vars.size(); i++)
		{
			if (context->vars[i].type > ValueType::NativeFunction)
			{
				if (context->vars[i]._object->grey == false)
				{
					context->vars[i]._object->grey = true;
					this->greys.Push(context->vars[i]);
				}
			}
		}
	}


	if (context->stack.size() > 0)
	{
		//StackProfile prof("Make Stack Grey");
		for (unsigned int i = 0; i < context->stack.size(); i++)
		{
			if (context->stack.mem[i].type > ValueType::NativeFunction)
			{
				if (context->stack.mem[i]._object->grey == false)
				{
					context->stack.mem[i]._object->grey = true;
					this->greys.Push(context->stack.mem[i]);
				}
			}
		}
	}


	//this is really part of the sweep section
	if (context->callstack.size() > 0)
	{
		//StackProfile prof("Traverse/Mark Stack");
		//printf("GC run at runtime!\n");
		//traverse all local vars
		if (context->curframe && context->curframe->grey == false)
		{
			context->curframe->grey = true;
			this->greys.Push(Value(context->curframe));
		}

		int sp = 0;
		for (unsigned int i = 0; i < context->callstack.size(); i++)
		{
			auto closure = context->callstack[i].second;
			if (closure == 0)
				continue;

			if (closure->grey == false)
			{
				closure->grey = true;
				this->greys.Push(Value(closure));
			}
			int max = sp+closure->prototype->locals;
			for (; sp < max; sp++)
			{
				if (context->localstack[sp].type > ValueType::NativeFunction)
				{
					if (context->localstack[sp]._object->grey == false)
					{
						context->localstack[sp]._object->grey = true;
						this->greys.Push(context->localstack[sp]);
					}
				}
			}
		}

		//mark curframe locals
		if (context->curframe)
		{
			int max = sp+context->curframe->prototype->locals;
			for (; sp < max; sp++)
			{
				if (context->localstack[sp].type > ValueType::NativeFunction)
				{
					if (context->localstack[sp]._object->grey == false)
					{
						context->localstack[sp]._object->grey = true;
						this->greys.Push(context->localstack[sp]);
					}
				}
			}
		}
	}


	{
		//StackProfile prof("Traverse Greys");
		while(this->greys.size() > 0)
		{
			//traverse the object
			auto obj = this->greys.Pop();
			switch (obj.type)
			{
			case ValueType::Object:
				{
					//obj._object->DebugPrint();
					if (obj._object->prototype && obj._object->prototype->grey == false)
					{
						obj._object->prototype->grey = true;

						this->greys.Push(obj._object->prototype);
					}

					obj._object->mark = true;
					for (auto ii: *obj._object)
					{
						if (ii.first.type > ValueType::NativeFunction && ii.first._object->grey == false)
						{
							ii.first._object->grey = true;
							greys.Push(ii.first);
						}
						if (ii.second.type > ValueType::NativeFunction && ii.second._object->grey == false)
						{
							ii.second._object->grey = true;
							greys.Push(ii.second);
						}
					}
					break;
				}
			case ValueType::Array:
				{
					obj._array->mark = true;

					for (auto ii: obj._array->data)
					{
						if (ii.type > ValueType::NativeFunction && ii._object->grey == false)
						{
							ii._object->grey = true;
							greys.Push(ii);
						}
					}

					break;
				}
			case ValueType::String:
				{
					obj._string->mark = true;

					break;
				}
#ifdef _DEBUG
			case ValueType::Capture:
				{
					throw RuntimeException("There should not be an upvalue in the grey loop");
					break;
				}
#endif
			case ValueType::Function:
				{
					obj._function->mark = true;
					//printf("Function Marked\n");
					if (obj._function->prev && obj._function->prev->grey == false)
					{
						obj._function->prev->grey = true;
						greys.Push(Value(obj._function->prev));
					}

					if (obj._function->numupvals)
					{
						for (unsigned int i = 0; i < obj._function->numupvals; i++)
						{
							auto uv = obj._function->upvals[i];
							if (uv && uv->grey == false)
							{
								if (uv->closed)
								{
									//mark the value stored in it
									if (uv->value.type > ValueType::NativeFunction)
									{
										if (uv->value._object->grey == false)
										{
											uv->value._object->grey = true;
											greys.Push(uv->value);
										}
									}
								}
								//mark it
								uv->grey = true;
								uv->mark = true;
							}
						}
					}

					if (obj._function->generator)
					{
						//mark generator stack
						for (unsigned int i = 0; i < obj._function->prototype->locals; i++)
						{
							if (obj._function->generator->stack[i].type > ValueType::NativeFunction)
							{
								if (obj._function->generator->stack[i]._object->grey == false)
								{
									obj._function->generator->stack[i]._object->grey = true;
									greys.Push(obj._function->generator->stack[i]);
								}
							}
						}
					}
					break;
				}
			case ValueType::Userdata:
				{
					obj._userdata->mark = true;

					if (obj._userdata->prototype && obj._userdata->prototype->grey == false)
					{
						obj._userdata->prototype->grey = true;

						greys.Push(obj._userdata->prototype);
					}
					break;
				}
			}
		}
	}
}

void GarbageCollector::Sweep()
{
	bool nextIncremental = ((this->collectionCounter+1)%GC_STEPS)!=0;
	bool incremental = ((this->collectionCounter)%GC_STEPS)!=0;
	/*if (this->collectionCounter % GC_STEPS == 0)
	printf("Full Collection!\n");
	else
	printf("Incremental Collection!\n");*/

	/* SWEEPING SECTION */


	//this must all be done when sweeping!!!!!!!

	//process stack variables, stack vars are ALWAYS grey

	//finally sweep through
	//sweep and free all whites and make all blacks white
	//iterate through all gc values
#ifdef _DEBUG
	if (this->greys.size() > 0)
		throw RuntimeException("Runtime Error: Garbage collector grey array not empty when collecting!");
#endif

	if (!incremental)//do a gen2 collection
	{
		auto g2list = std::move(this->gen2);
		this->gen2.clear();
		for (auto ii: g2list)
		{
			if (ii->mark || ii->refcount)
			{
				ii->mark = false;
				ii->grey = false;

				this->gen2.push_back(ii);
			}
			else
			{
				//printf("Freeing Gen 2, %d!\n", ii->type);
				this->Free(ii);
			}
		}
	}

	auto g1list = std::move(this->gen1);
	this->gen1.clear();
	for (auto ii: g1list)
	{
		if (ii->mark || ii->refcount)
		{
			//ii->mark = false;//perhaps do this ONLY IF we just did a gen2 collection
			//ii->grey = false;
			this->gen2.push_back(ii);//promote, it SURVIVED

			//printf("Promoting %d!\n", ii->type);
		}
		else
		{
			//printf("Freeing %d!\n", ii->type);
			this->Free(ii);
		}
	}

	//Obviously, this approach doesn't work for a non-copying GC. But the main insights behind a generational GC can be abstracted:

	//Minor collections only take care of newly allocated objects.
	//Major collections deal with all objects, but are run much less often.

	//The basic idea is to modify the sweep phase: 
	//1. free the (unreachable) white objects, but don't flip the color of black objects before a minor collection. 
	//2. The mark phase of the following minor collection then only traverses newly allocated blocks and objects written to (marked gray). 
	//3. All other objects are assumed to be still reachable during a minor GC and are neither traversed, nor swept, nor are their marks changed (kept black). A regular sweep phase is used if a major collection is to follow.
}

void GarbageCollector::Run()
{
	//printf("Running GC: %d Greys, %d Globals, %d Stack\n%d Closures, %d Arrays, %d Objects, %d Userdata\n", this->greys.size(), this->vars.size(), 0, this->closures.size(), this->arrays.size(), this->objects.size(), this->userdata.size());
#ifdef JET_TIME_EXECUTION
	INT64 start, end;
	//QueryPerformanceFrequency( (LARGE_INTEGER *)&rate );
	QueryPerformanceCounter( (LARGE_INTEGER *)&start );
#endif
	//mark all references in the grey stack
	this->Mark();

	//clear up dead memory
	this->Sweep();

	this->collectionCounter++;//used to determine collection mode
#ifdef JET_TIME_EXECUTION
	INT64 rate;
	QueryPerformanceCounter( (LARGE_INTEGER *)&end );
	QueryPerformanceCounter((LARGE_INTEGER*)&rate);
	INT64 diff = end - start;
	double dt = ((double)diff)/((double)rate);

	printf("Took %lf seconds to collect garbage\n\n", dt);
#endif
	//printf("collection done\n");
	//printf("GC Complete: %d Greys, %d Globals, %d Stack\n%d Closures, %d Arrays, %d Objects, %d Userdata\n", this->greys.size(), this->vars.size(), 0, this->closures.size(), this->arrays.size(), this->objects.size(), this->userdata.size());
}

void GarbageCollector::Free(gcval* ii)
{
	switch (ii->type)
	{
	case ValueType::Function:
		{
			Closure* fun = (Closure*)ii;
#ifdef JETGCDEBUG
			printf("GC Freeing Function %d\n", ii);

			fun->generator = (Generator*)0xcdcdcdcd;
#else
			if (fun->numupvals)
				delete[] fun->upvals;

			delete fun->generator;
			delete fun;
#endif
			break;
		}
	case ValueType::Object:
		{
#ifdef JETGCDEBUG
			JetObject* obj = (JetObject*)ii;
			obj->nodes = (ObjNode*)0xcdcdcdcd;
#else
			delete (JetObject*)ii;
#endif
			break;
		}
	case ValueType::Array:
		{
#ifdef JETGCDEBUG
			JetArray* arr = (JetArray*)ii;
			arr->data.clear();
#endif
			delete (JetArray*)ii;
			//#endif
			break;
		}
	case ValueType::Userdata:
		{
			Value ud = Value(((JetUserdata*)ii), ((JetUserdata*)ii)->prototype);
			Value _gc = (*((JetUserdata*)ii)->prototype).get("_gc");
			if (_gc.type == ValueType::NativeFunction)
				_gc.func(this->context, &ud, 1);
			else if (_gc.type == ValueType::Function)
				throw RuntimeException("Non Native _gc Hooks Not Implemented!");//todo
			else if (_gc.type != ValueType::Null)
				throw RuntimeException("Invalid _gc Hook!");
			delete (JetUserdata*)ii;
			break;
		}
	case ValueType::String:
		{
			JetString* str = (JetString*)ii;
			delete[] str->data;
			delete str;
			break;
		}
	case ValueType::Capture:
		{
			Capture* uv = (Capture*)ii;
			delete uv;
			//printf("Freeing capture!\n");
			break;
		}
#ifdef _DEBUG
	default:
		throw RuntimeException("Runtime Error: Invalid GC Object Typeid!");
#endif
	}
}