/*	
 *	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をスタックに積むように変更しました。
 *	* Sat Nov 04 12:30:26 JST 2006 Naoyuki Sawa
 *	- 高速化のため、大幅に改造しました。
 *	  改造前の安定動作していたコードは、keep/06_GC高速化前の安定版保存.20061104に保存しました。
 *	- 高速化のための主な変更点は、以下の通りです。(詳しくは、変更前のコードと比較してください。)
 *	  ・改造前の_gc_run()において、新しい参照ブロックを発見するたびにループを中断して最初から走査し直していましたが、
 *	    改造後の_gc_run()では、ループを中断せずに最後まで走査し、一度でも発見があればもう一度走査することにしました。
 *	    変更前は、発見回数と同じ回数のループ再開を行っていましたが、変更後は、複数回の発見を一度の再開にまとめられます。
 *	  ・変更前の_gc_run()では、一度走査したブロックも、ループ再開の度に再走査を行っており、無駄がありました。
 *	    変更後の_gc_run()は、参照されているが未走査であるブロックと、走査済みブロックを区別して扱い、無駄な走査を省きました。
 *	  ・改造前のgc_mark()において、未参照ブロックへの新しい参照を発見した数をカウントしていましたが、
 *	    カウントは無意味なので、改造後のgc_scan()においては、発見の有無を単純な0or1フラグとしました。
 *	- さらに高速化できる可能性があるが、あえて採用しなかった手段があるので、記録しておきます。
 *	  ・gc_scan()において、現在走査中のブロックよりも後方のブロックへの新しい参照の発見では、resultを1にしないという手があります。
 *	    なぜなら、現在走査中のブロックよりも後方のブロックは、現在のヒープ走査ループ中に走査されるので、ループ再開不要だからです。
 *	    この手段により、最終のループ再開が一回省略できる可能性があり、高速化できる可能性があります。
 *	    しかし、あまりにもメモリレイアウトに依存しすぎているし、コードがわかりづらくなる恐れがあります。
 *	    それに、ヒープ全体に対する一回の走査ループが無駄に発生したとしても、さほど大きな負荷ではありません。
 *	    コードをわかり易く保つために、この手段は採用しないことにしました。
 */
#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 */
#define HMO_NOSCAN_USER	0x2222	/* 参照されているが、未走査のHMO_DEFAULT_USER */

static void _gc_run() __attribute__((unused));
static int gc_scan(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();

	/* 割り当て済みユーザーブロックを、仮に未参照ブロックとしておきます。 */
	for(phm = gc->heaptop; phm; phm = phm->chain) {
		if(phm->mark != HEAPMEMMK) DIE();
		switch(phm->owner) {
		/* 空きブロック */
		case 0:
			/** no job **/
			break;
		/* 割り当て済みシステムブロック */
		case HMO_SYSTEM:
			if(phm->chain) DIE();		/* PieceSystem 1.20 においては、HMO_SYSTEMは、ヒープ末端の空ブロックとしてのみ利用されています */
			break;
		/* 割り当て済みユーザーブロック */
		case HMO_DEFAULT_USER:
			phm->owner = HMO_NOREF_USER;	/* 仮に未参照ブロックとしておき、参照を検出したらHMO_NOSCAN_USER→HMO_DEFAULT_USERと遷移します */
			break;
		/* 予期しないメモリブロック種別 */
		default:
			DIE();
		}
	}

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

	/* 要走査ブロックを走査して、参照先ブロックを要走査ブロックとし、自身は走査済みブロックに戻します。 */
	do {
		retval = 0;
		for(phm = gc->heaptop; phm; phm = phm->chain) {
			if(phm->mark != HEAPMEMMK) DIE();
			if(phm->owner == HMO_NOSCAN_USER) {
				retval |= gc_scan(phm + 1/*必要!!*/, phm->chain);
				phm->owner = HMO_DEFAULT_USER; /* 走査済みに戻す */
			}
		}
	} while(retval); /* 新しい要走査ブロックが追加されたら、もう一度最初から */

	/* 未参照ブロックのまま残ったブロックを、すべて開放します。 */
	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; /* phm->chainは無効になったので、forを継続できない。もう一度最初から */
			}
		}
	} while(phm); /* breakで抜けた場合、もう一度最初から */
}

/* 指定範囲の全ワードを走査して、未参照ブロックへの新しい参照を検出します。
 * 未参照ブロックへの新しい参照を検出したら、要走査ブロックとマークします。
 */
static int
gc_scan(void* top, void* end)
{
	int result = 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_NOSCAN_USER;	/* 要走査ブロックとしてマークします。(未走査) */
						result = 1;
					}
					break;
				}
			}
		}
	}

	return result;
}

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;
}

