/*	
 *	clipgc.c
 *
 *	P/ECE用ガーベージコレクター
 *
 *	「K.Sasada's Home Page」(http://www.namikilab.tuat.ac.jp/~sasada/)さんの
 *	『PiGC : P/ECE 用ガベージコレクター』(http://www.namikilab.tuat.ac.jp/~sasada/prog/pigc.html)
 *	の実装を参考にさせて頂きました。ありがとうございます。
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2004 Naoyuki Sawa
 *
 *	* Tue Jul 22 07:00:00 JST 2004 Naoyuki Sawa
 *	- 作成開始。
 *	* Tue Jul 22 20:04:00 JST 2004 Naoyuki Sawa
 *	- レジスタから参照されているメモリブロックを誤って開放してしまうのを防ぐため、
 *	  ガーベージコレクター本体を呼び出す前に%r0-3をスタックに積むように変更しました。
 */
#include "clip.h"

/****************************************************************************
 *	
 ****************************************************************************/

typedef struct _GC {
	void* (*old_pceHeapAlloc)(unsigned long size);	/* 本物のpceHeapAlloc()を保存。(NULL:未初期化) */
	unsigned int sram_top;				/* SRAM先頭アドレス     */
	unsigned int sram_end;				/* SRAM終端アドレス(+1) */
	unsigned int stack_top;				/* スタック領域先頭アドレス     */
	unsigned int stack_end;				/* スタック領域終端アドレス(+1) */
	HEAPMEM* heaptop;				/* 最初のメモリブロック管理構造体アドレス */
} GC;
static GC _gc;

/* HEAPMEM.owner拡張。PieceSystem規定の値と重複してはダメ!! */
#define HMO_NOREF_USER	0x1111	/* 未参照のHMO_DEFAULT_USER */

static void _gc_run() __attribute__((unused));
static int gc_mark(void* top, void* end);
static void* new_pceHeapAlloc(unsigned long size);

extern unsigned int __START_FRAM_ADDR[];
extern unsigned int __END_FRAM_ADDR[];
extern unsigned int __START_DEFAULT_CODE[];
extern unsigned int __END_DEFAULT_CODE[];
extern unsigned int __START_DEFAULT_DATA[];
extern unsigned int __END_DEFAULT_DATA[];
extern unsigned int __START_DEFAULT_BSS[];
extern unsigned int __END_DEFAULT_BSS[];

/****************************************************************************
 *	
 ****************************************************************************/

void
gc_init()
{
	GC* gc = &_gc;
	//
	const SYSTEMINFO* sysinfo;
	const pceAPPHEAD* apphead;

	/* まず確実に未初期化状態に戻します。 */
	gc_free();

	/* SRAMの先頭・終端アドレスを取得します。 */
	sysinfo = pceSystemGetInfo();
	gc->sram_top = (unsigned int)sysinfo->sram_top;
	gc->sram_end = (unsigned int)sysinfo->sram_end;

	/* スタック領域と、最初のメモリブロック管理構造体アドレスを取得します。 */
	apphead = (const pceAPPHEAD*)__START_DEFAULT_CODE;
	if(apphead->stack_size) {
		/* * スタックをSRAMに配置した場合のメモリレイアウトは、以下の通りです。
		 *
		 *	0000000	+-------------+
		 *		|ｼｽﾃﾑWORK     |
		 *	0001000	+-------------+	__START_FRAM_ADDR
		 *		|高速RAM転送  |
		 *	0001???	+-------------+	__END_FRAM_ADDR
		 *		|空き         |
		 *	0002000	+-------------+
		 *
		 *	0100000	+-------------+	__START_DEFAULT_CODE
		 *		|ﾌﾟﾛｸﾞﾗﾑ･定数 |
		 *	01?????	+-------------+	__END_DEFAULT_CODE == __START_DEFAULT_DATA
		 *		|初期化済変数 |
		 *	01?????	+-------------+	__END_DEFAULT_DATA == __START_DEFAULT_BSS
		 *		|ｾﾞﾛ初期化変数|
		 *	01?????	+-------------+	__END_DEFAULT_BSS == apphead->bss_end
		 *		|ｽﾀｯｸ領域     |
		 *	01?????	+-------------+	(apphead->bss_end + apphead->stack_size) == heaptop
		 *		|ﾋｰﾌﾟ領域     |
		 *	0140000	+-------------+
		 */
		gc->stack_top = (unsigned int)apphead->bss_end;
		gc->stack_end = gc->stack_top + apphead->stack_size;
		gc->heaptop = (HEAPMEM*)gc->stack_end;
	} else {
		/* * スタックを高速RAMに配置した場合のメモリレイアウトは、以下の通りです。
		 *
		 *	0000000	+-------------+
		 *		|ｼｽﾃﾑWORK     |
		 *	0001000	+-------------+	__START_FRAM_ADDR
		 *		|(高速RAM転送)|	... 通常は使いません。__START_FRAM_ADDR == __END_FRAM_ADDR == 0x1000 です。
		 *	0001???	+-------------+	__END_FRAM_ADDR
		 *		|ｽﾀｯｸ領域     |
		 *	0002000	+-------------+
		 *
		 *	0100000	+-------------+	__START_DEFAULT_CODE
		 *		|ﾌﾟﾛｸﾞﾗﾑ･定数 |
		 *	01?????	+-------------+	__END_DEFAULT_CODE == __START_DEFAULT_DATA
		 *		|初期化済変数 |
		 *	01?????	+-------------+	__END_DEFAULT_DATA == __START_DEFAULT_BSS
		 *		|ｾﾞﾛ初期化変数|
		 *	01?????	+-------------+	__END_DEFAULT_BSS == apphead->bss_end == heaptop
		 *		|ﾋｰﾌﾟ領域     |
		 *	0140000	+-------------+
		 */
		gc->stack_top = (unsigned int)__END_FRAM_ADDR;
		gc->stack_end = 0x2000;
		gc->heaptop = (HEAPMEM*)apphead->bss_end;
	}
	if(gc->heaptop->mark != HEAPMEMMK) DIE();

	/* pceHeapAlloc()をフックします。(old_pceHeapAlloc!=NULL:初期化済) */
	gc->old_pceHeapAlloc = pceVectorSetKs(KSNO_HeapAlloc, new_pceHeapAlloc);
}

void
gc_free()
{
	GC* gc = &_gc;

	/* 初期化されていなければ何もしません。 */
	if(!gc->old_pceHeapAlloc) return;

	/* pceHeapAlloc()のフックを解除します。 */
	pceVectorSetKs(KSNO_HeapAlloc, gc->old_pceHeapAlloc);

	/* クリアします。(old_pceHeapAlloc==NULL:未初期化) */
	memset(gc, 0, sizeof(GC));
}

/* void gc_run() */
asm("
	.code
	.global gc_run
gc_run:
	; 呼び出し側関数が、有効なメモリブロックへのポインタを%r0-3に保持している可能性があります。
	; ガーベージコレクターはレジスタからのメモリブロック参照を検査しないので、
	; そのままでは、レジスタから参照されているメモリブロックを誤って開放してしまう可能性があります。
	; この問題を回避するため、%r0-3をスタックに積んでから、ガーベージコレクター本体を呼び出すことにしました。
	pushn %r3
	call _gc_run
	popn %r3
	ret
");

static void
_gc_run()
{
	GC* gc = &_gc;
	//
	int retval;
	HEAPMEM* phm;

	/* 未初期化時に呼んではいけません。 */
	if(!gc->old_pceHeapAlloc) DIE();

	/* 割り当て済みUSERメモリブロックを、仮に未参照としておきます。 */
	for(phm = gc->heaptop; phm; phm = phm->chain) {
		if(phm->mark != HEAPMEMMK) DIE();
		if(phm->owner == HMO_NOREF_USER) DIE(); /* PieceSystem規定の値と重複!? */
		if(phm->owner == HMO_DEFAULT_USER) phm->owner = HMO_NOREF_USER;
	}

	/* 未参照ブロックのうち、スタック領域orデータ領域から参照されているものを、HMO_DEFAULT_USERに戻します。 */
	gc_mark((void*)gc->stack_top, (void*)gc->stack_end);
	gc_mark(__START_DEFAULT_DATA, __END_DEFAULT_DATA);
	gc_mark(__START_DEFAULT_BSS, __END_DEFAULT_BSS);

	/* 未参照ブロックのうち、空きor未参照ブロック以外から参照されているものを、HMO_DEFAULT_USERに戻します。 */
	do {
		for(phm = gc->heaptop; phm; phm = phm->chain) {
			if(phm->mark != HEAPMEMMK) DIE();
			if(phm->owner && phm->owner != HMO_NOREF_USER) {
				retval = gc_mark(phm + 1/*必要!!*/, phm->chain);
				if(retval) break; /* 新しい参照が追加されたら、もう一度最初から */
			}
		}
	} while(phm); /* breakで抜けた場合、もう一度最初から */

	/* 未参照のまま残ったブロックを開放します。 */
	do {
		for(phm = gc->heaptop; phm; phm = phm->chain) {
			if(phm->mark != HEAPMEMMK) DIE();
			if(phm->owner == HMO_NOREF_USER) {
				retval = pceHeapFree(phm + 1/*必要!!*/);
				if(retval != 0) DIE();
				break; /* チェインが変化したので、もう一度最初から */
			}
		}
	} while(phm); /* breakで抜けた場合、もう一度最初から */
}

/* 指定範囲の全ワードを走査して、未参照メモリブロックへの新しい参照を検出します。
 * 新しい参照を検出したら、マーク(HMO_DEFAULT_USER)して、カウントアップします。
 * 既に参照マークされているメモリブロックへの参照は、カウントアップしません。
 */
static int
gc_mark(void* top, void* end)
{
	int count = 0;
	GC* gc = &_gc;
	//
	unsigned int* pos;
	unsigned int addr;
	HEAPMEM* phm;

	for(pos = (unsigned int*)top; pos < (unsigned int*)end; pos++) {
		addr = *pos - sizeof(HEAPMEM)/*必要!!*/;
		if(!(addr & 3) && (addr >= gc->sram_top) && (addr < gc->sram_end)) {
			for(phm = gc->heaptop; phm; phm = phm->chain) {
				if(phm->mark != HEAPMEMMK) DIE();
				if(phm == (HEAPMEM*)addr) {
					if(phm->owner == HMO_NOREF_USER) {
						phm->owner = HMO_DEFAULT_USER;
						count++;
					}
					break;
				}
			}
		}
	}

	return count;
}

static void*
new_pceHeapAlloc(unsigned long size)
{
	GC* gc = &_gc;
	//
	void* ptr;

	ptr = gc->old_pceHeapAlloc(size); /* 1st try */
	if(!ptr) {
		gc_run();
		ptr = gc->old_pceHeapAlloc(size); /* 2nd try */
		if(!ptr) DIE();
	}

	return ptr;
}

