/*	
 *	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-2012 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にしないという手があります。
 *	    なぜなら、現在走査中のブロックよりも後方のブロックは、現在のヒープ走査ループ中に走査されるので、ループ再開不要だからです。
 *	    この手段により、最終のループ再開が一回省略できる可能性があり、高速化できる可能性があります。
 *	    しかし、あまりにもメモリレイアウトに依存しすぎているし、コードがわかりづらくなる恐れがあります。
 *	    それに、ヒープ全体に対する一回の走査ループが無駄に発生したとしても、さほど大きな負荷ではありません。
 *	    コードをわかり易く保つために、この手段は採用しないことにしました。
 *	* Sat Jun 20 01:31:13 JST 2009 Naoyuki Sawa
 *	- 割り込みルーチン内でpceHeap*()を使ったときにGCが発生したり、明示的にgc_run()を呼び出しても安全なよう、
 *	  _gc_run()関数内にENTER_CS～LEAVE_CSを追加し、割り込み禁止としました。
 *	- gc_run()は時間のかかる処理なので、割り込み禁止にするのは気が引けたのですが、やはり割り込み禁止にすることにしました。
 *	  clippce.cモジュール内でpceHeap*()を割り込み禁止に変更し、割り込みルーチン内で使用可能としている以上、
 *	  ガーベージコレクターも割り込み内で安全に利用可能でなければ、片手落ちであると考えたからです。
 *	  確かにgc_run()は時間がかかるのですが、頻繁に発生する処理ではないので、大きな影響は無いと思います。
 *	  gc_run()が発生したときに、長時間割り込みが禁止されて、サウンドにノイズが乗ったり、16階調表示がちらついたとしても、
 *	  たまに一瞬発生するだけであって、さほど気にならないと思います。(※TODO:2009/06/20現在、まだ実際に試していません)
 *	* Sat Nov 24 17:12:52 JST 2012 Naoyuki Sawa
 *	- メモリブロックの内部を指すポインタも、有効な参照と見なすように、変更しました。
 *	  他の一般的なGCも同様な設計であるため、それらに倣うことにしました。(Boehm GC、D言語のGC、など)
 *	* Tue Nov 27 22:17:14 JST 2012 Naoyuki Sawa
 *	- GCの動作レベルを変更する仕組みを追加しました。(gc_init()の引数追加)
 *	- 今後作成するアプリケーションでは、極力「保守的」GC動作レベルを使用して、動作検証してください。
 *	  動作検証の結果、もし「保守的」動作レベルにおける上述の欠点が、実用上問題にならないようならば、
 *	  敢えて「中間的」「積極的」動作レベルを使用する必要は無く、「保守的」に統一するかも知れません。
 *	* Thu Nov 29 23:35:33 JST 2012 Naoyuki Sawa
 *	- gc_scan()をアセンブラ化しました。
 *	  効果は、約30%高速化と、28バイト省メモリ化です。(GC動作レベル=保守的,ターボ=無し,ユーザースタック=SRAM配置にて計測)
 *	* Fri Nov 30 13:39:02 JST 2012 Naoyuki Sawa
 *	- スタックレイアウトの前提が、現在のCLiPアプリケーションと一致していなかった、重大な問題を修正しました。
 *	  詳細は、gc_init()内コメントを参照してください。
 */
#include "clip.h"

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

//{{2012/11/30変更
//typedef struct _GC {
//	void* (*old_pceHeapAlloc)(unsigned long size);	/* + 0,4 本物のpceHeapAlloc()を保存。(NULL:未初期化) */
//	unsigned int sram_top;				/* + 4,4 SRAM先頭アドレス     */
//	unsigned int sram_end;				/* + 8,4 SRAM終端アドレス(+1) */
//	unsigned int stack_top;				/* +12,4 スタック領域先頭アドレス     */
//	unsigned int stack_end;				/* +16,4 スタック領域終端アドレス(+1) */
//	HEAPMEM* heaptop;				/* +20,4 最初のメモリブロック管理構造体アドレス */
////{{2012/11/27追加
//	unsigned char level;				/* +24,1 GCの動作レベル */
////}}2012/11/27追加
//} GC;
//↓2012/11/30変更
typedef struct _GC {
	void* (*old_pceHeapAlloc)(unsigned long size);	/* + 0,4 本物のpceHeapAlloc()を保存。(NULL:未初期化) */
	unsigned int sram_top;				/* + 4,4 SRAM先頭アドレス     */
	unsigned int sram_end;				/* + 8,4 SRAM終端アドレス(+1) */
	HEAPMEM* heaptop;				/* +12,4 最初のメモリブロック管理構造体アドレス */
	unsigned char level;				/* +16,1 GCの動作レベル */
} GC;
//}}2012/11/30変更
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));
//{{2012/11/29変更
//static int gc_scan(void* top, void* end);
//↓2012/11/29変更
#ifndef PIECE
static int gc_scan(void* top, void* end);
#else /*PIECE*/
/*static*/ int gc_scan(void* top, void* end); /* asmブロックで定義 */
#endif/*PIECE*/
//}}2012/11/29変更
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[];

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

//{{2012/11/27変更
//void
//gc_init()
//↓2012/11/27変更
void
gc_init(int level)
//}}2012/11/27変更
{
	GC* gc = &_gc;
	//
	const SYSTEMINFO* sysinfo;
	const pceAPPHEAD* apphead;

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

//{{2012/11/27追加
	/* GCの動作レベルを格納します。 */
	if((level < GC_LEVEL_CONSERVATIVE) || (level > GC_LEVEL_AGGRESSIVE)) DIE(); /* GCの動作レベル指定が不正 */
	gc->level = level;
//}}2012/11/27追加

	/* 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;
//{{2012/11/30変更
//	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;
//	}
//↓2012/11/30変更
//↓* Fri Nov 30 13:39:02 JST 2012 Naoyuki Sawa
//↓- 上記の処理は、現在のCLiPアプリケーションのスタックレイアウトと、一致していないことに気付きました。
//↓  2004/7にclipgc.cの初版を作成した時点では正しかったのですが、2004/12にスタックレイアウトの大幅な変更を行ったからです。(clip.mk内2004/12/27コメント参照)
//↓  2004/12～2012/11までの約8年間、間違いに気付かないまま使い続けていました。←←←■■■重大な問題■■■
//↓- 【経緯】
//↓  2004/7にclipgc.cの初版を作成した時点では、システムスタックとユーザースタックを、両方SRAMに置くか、両方FRAMに置くかであり、上記の処理はその前提で作成していました。
//↓  2004/12以降は、システムスタックは常にSRAMに置き、ユーザースタックをSRAMに置くかFRAMに置くかを選択できるようになっています。(clippce.c内stack_layout()コメント参照)
//↓- 【発生していた問題】
//↓  ユーザースタックをFRAMに置いた場合、ユーザースタックに対するgc_scan()が実行されず、ユーザースタックが参照しているメモリブロックを誤って開放してしまいます。
//↓- 【対策】
//↓  clipgc.cモジュール内で独自にスタックレイアウトを判断するのでなく、clippce.c内のstack_layout()で起動時に格納したスタックレイアウトを参照するようにしました。
//↓  今回の修正により、上記のケースも正しく処理できるようになりました。
//↓- 【未解決の問題】⇒重要度低と判断し、対策しない
//↓  今回の修正後も、一時的なスタックに対するgc_scan()が実行されない可能性は残っています。
//↓  たとえば、ユーザースタックをSRAMに置いた後、一時的にstack_switch()を用いて、FRAM2やFRAM4の余りエリアにスタックを切り替えた場合です。
//↓  しかし、実際には、FRAM2やFRAM4の余りエリアにスタックを切り替えた状態で、GCが走る(=メモリ確保関数を利用する)ことはまず無いと思います。
//↓  FRAM2やFRAM4にスタックを切り替えるということは、速度が非常に重要なケースであり、それらの処理の中でメモリ確保関数を利用することは無いと思うからです。
//↓  従って、FRAM2やFRAM4の余りエリアにスタックを切り替えた状態を把握して、gc_scan()を実行することは *実用上、必要では無い* と判断しました。
	//if(!apphead->stack_size) DIE(); /* 起動時に、clippce.c内のstack_layout()で既に同等の検査を行っているので、ここでは検査不要です。 */
	gc->heaptop = (HEAPMEM*)(apphead->bss_end + apphead->stack_size);
//}}2012/11/30変更
	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();

ENTER_CS; /*{{2009/06/20:追加}}*/

	/* 割り当て済みユーザーブロックを、仮に未参照ブロックとしておきます。 */
	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データ領域から参照されているものを、要走査ブロックとします。 */
//{{2012/11/30変更
//	gc_scan((void*)gc->stack_top, (void*)gc->stack_end);
//↓2012/11/30変更
	gc_scan(stack_info.sysstack_top, stack_info.sysstack_end);	/* システムスタック … SRAM */
	gc_scan(stack_info.usrstack_top, stack_info.usrstack_end);	/* ユーザースタック … SRAM or FRAM */
//}}2012/11/30変更
	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で抜けた場合、もう一度最初から */

LEAVE_CS; /*{{2009/06/20:追加}}*/
}

/* 指定範囲の全ワードを走査して、未参照ブロックへの新しい参照を検出します。
 * 未参照ブロックへの新しい参照を検出したら、要走査ブロックとマークします。
 */
//{{2012/11/27変更,2012/11/29変更
//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++) {
//#if 0 //{{2012/11/24変更
//		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;
//				}
//			}
//		}
//#else //↓2012/11/24変更
//// * Sat Nov 24 17:12:52 JST 2012 Naoyuki Sawa
//// - メモリブロックの内部を指すポインタも、有効な参照と見なすように、変更しました。
////   他の一般的なGCも同様な設計であるため、それらに倣うことにしました。(Boehm GC、D言語のGC、など)
////
////	【変更前】
////	　　　　　　　　　　　　　│　　　　　　　│
////	　　　　　　　　　　　　　┣━━━━━━━┫
////	┌────┐　有効な参照　┃ＨＥＡＰＭＥＭ┃
////	│ポインタ├──────→┣━━━━━━━┫
////	└────┘　　　　　　　┃／／／／／／／┃
////	　　　　　　　　　　　　　┃／／／／／／／┃
////	┌────┐　無効な参照　┃／／／／／／／┃
////	│ポインタ├──────→┃／／／／／／／┃
////	└────┘　　　　　　　┃／／／／／／／┃
////	　　　　　　　　　　　　　┣━━━━━━━┫
////	　　　　　　　　　　　　　│ＨＥＡＰＭＥＭ│
////	　　　　　　　　　　　　　├───────┤
////	　　　　　　　　　　　　　│　　　　　　　│
////
////	【変更後】
////	　　　　　　　　　　　　　│　　　　　　　│
////	　　　　　　　　　　　　　┣━━━━━━━┫
////	┌────┐　有効な参照　┃ＨＥＡＰＭＥＭ┃
////	│ポインタ├──────→┣━━━━━━━┫
////	└────┘　　　　　　　┃／／／／／／／┃
////	　　　　　　　　　　　　　┃／／／／／／／┃
////	┌────┐　有効な参照　┃／／／／／／／┃
////	│ポインタ├──────→┃／／／／／／／┃
////	└────┘　　　　　　　┃／／／／／／／┃
////	　　　　　　　　　　　　　┣━━━━━━━┫
////	　　　　　　　　　　　　　│ＨＥＡＰＭＥＭ│
////	　　　　　　　　　　　　　├───────┤
////	　　　　　　　　　　　　　│　　　　　　　│
////
//// - 今回の変更による利点:
////   GCを利用するアプリケーションが、注意して、メモリブロックの先頭アドレスを保持する必要が無くなります。
////   特に有用な例として、構造体の途中に LIST_ENTRY を置いて、リストを保持することができるようになります。
////   これまでに作成したコードは、LIST_ENTRY を構造体の先頭に置くよう注意していましたが、今後は構造体の途中に置いても構いません。
////
////	【変更前】
////	typedef struct _NODE {
////		LIST_ENTRY list_entry;	←他のノードからのポインタが、メモリブロックの先頭アドレスを指すよう、LIST_ENTRY を構造体の先頭に置く必要がありました 。
////		int key;
////		int value;
////	} NODE;
////
////	【変更後】
////	typedef struct _NODE {
////		int key;
////		int value;
////		LIST_ENTRY list_entry;	←LIST_ENTRY を構造体のどこに置いても構いません。左の例では末尾に置きましたが、先頭のままや、途中に置いても構いません。
////	} NODE;
////
//// - 今回の変更による欠点:
////   保守的GCの特性により、ポインタでない値をポインタと見なし、実際には参照されていないメモリブロックを開放しない可能性が高まります。
////   変更前は、偶然、メモリブロックの先頭アドレスに一致した場合のみでしたが、変更後は、偶然、メモリブロックの範囲に一致した場合も開放しないようになるからです。
////
//// - 今後の検討:
////   もし、実用上、「実際には参照されていないメモリブロックを開放しないケース」が増えすぎて使用に耐えない場合は、元に戻してください。
////   ここ以外に変更箇所はありませんので、上の「#if 0」を「#if 1」に変更するだけで、元に戻ります。
//		addr = *pos;
//		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->owner == HMO_NOREF_USER) {
//					if((addr >= (unsigned int)(phm + 1/*必要!!*/)) &&
//					   (addr <  (unsigned int)(phm->chain))) {	/* 未参照ブロックへの新しい参照を検出したら… */
//						phm->owner = HMO_NOSCAN_USER;		/* 要走査ブロックとしてマークします。(未走査) */
//						result = 1;
//						break;
//					}
//				}
//			}
//		}
//#endif//}}2012/11/24変更
//	}
//
//	return result;
//}
//↓2012/11/27変更,2012/11/29変更
#ifndef PIECE
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;
		/* GCの動作レベルが、「中間的」又は「積極的」ならば… */
		if(gc->level >= GC_LEVEL_INTERMEDIATE) {
			/* アドレスが、ワード境界を指していなければ、有効な参照と見なさない。 */
			if(addr & 3) {
				continue;
			}
		}
		if((addr >= gc->sram_top) && (addr < gc->sram_end)) {
			for(phm = gc->heaptop; phm; phm = phm->chain) {
				if(phm->mark != HEAPMEMMK) DIE();
				if(phm->owner == HMO_NOREF_USER) {
					/* GCの動作レベルが、「保守的」又は「中間的」ならば… */
					if(gc->level <= GC_LEVEL_INTERMEDIATE) {
						/* アドレスが、メモリブロックの範囲内ならば、有効な参照と見なす。 */
						if((addr >= (unsigned int)(phm + 1/*必要!!*/)) &&
						   (addr <  (unsigned int)(phm->chain))) {	/* 未参照ブロックへの新しい参照を検出したら… */
							phm->owner = HMO_NOSCAN_USER;		/* 要走査ブロックとしてマークします。(未走査) */
							result = 1;
							break;
						}
					/* GCの動作レベルが、「積極的」ならば… */
					} else {
						/* アドレスが、メモリブロックの先頭に一致する場合のみ、有効な参照と見なす。 */
						if(addr == (unsigned int)(phm + 1/*必要!!*/)) {	/* 未参照ブロックへの新しい参照を検出したら… */
							phm->owner = HMO_NOSCAN_USER;		/* 要走査ブロックとしてマークします。(未走査) */
							result = 1;
							break;
						}
					}
				}
			}
		}
	}

	return result;
}
#else /*PIECE*/
#if 0
asm("
		.code
		.align		1
;//{{==================== ブロックA ====================;//
gc_scan:
		;// %r12 := pos = top
		;// %r13 := end
		xld.w		%r9, _gc+4		;// %r9  :=           &_gc.sram_top
		ld.w		%r4, [%r9]+		;// %r4  := sram_top = _gc.sram_top
;//{{2012/11/30変更
;//		ld.w		%r5, [%r9]		;// %r5  := sram_end = _gc.sram_end
;//		add		%r9, 12			;// %r9  :=           &_gc.heaptop
;//↓2012/11/30変更
		ld.w		%r5, [%r9]+		;// %r5  := sram_end = _gc.sram_end
;//}}2012/11/30変更
		ld.w		%r6, [%r9]+		;// %r6  := heaptop  = _gc.heaptop
		ld.ub		%r7, [%r9]		;// %r7  := level    = _gc.level
		jp.d		gc_scan_NEXT_POS	;// goto gc_scan_NEXT_POS
		ld.w		%r10, 0			;// %r10 := result   = 0					*delay*
gc_scan_LOOP_POS:					;// do {
		;//-------------------------------------;//
		;// %r4  := sram_top
		;// %r5  := sram_end
		;// %r6  := heaptop
		;// %r7  := level
		;// %r10 := result
		;// %r12 := pos
		;// %r13 := end
		ld.w		%r11, [%r12]+		;//   %r11 := addr = *pos++
		;//
;//		cmp		%r7, 1			;//   if(level >= GC_LEVEL_INTERMEDIATE) {	【→①】
		jrlt		4
		 ld.w		%r9, %r11		;//     if(addr & 3) {
		 and		%r9, 3			;//       goto gc_scan_NEXT_POS
		 jrne		gc_scan_NEXT_POS	;//     }
		;//					;//   }
		cmp		%r11, %r4		;//   if(addr <  sram_top)
		jrult		gc_scan_NEXT_POS	;//     goto gc_scan_NEXT_POS
		cmp		%r11, %r5		;//   if(addr >= sram_end)
		jruge		gc_scan_NEXT_POS	;//     goto gc_scan_NEXT_POS
		;//					;//   }
		jp.d		gc_scan_NEXT_PHM	;//   goto gc_scan_NEXT_PHM
		ld.w		%r15, %r6		;//   %r15 := chain = heaptop					*delay*
;//{{==================== ブロックB ====================;//
gc_scan_LOOP_PHM:					;//   do {
		;//-------------------------------------;//
		;// %r4  := sram_top
		;// %r5  := sram_end
		;// %r6  := heaptop
		;// %r7  := level
		;// %r10 := result
		;// %r11 := addr
		;// %r12 := pos
		;// %r13 := end
		;// %r14 := phm
		ld.uh		%r9, [%r14]+		;//     %r9  := mark  = phm->mark
		;//
		xcmp		%r9, 0xA431		;//     if(mark != HEAPMEMMK)
		jrne		gc_scan_DIE		;//       goto gc_scan_DIE
		;//
		ld.uh		%r9, [%r14]+		;//     %r9  := owner = phm->owner
		ld.w		%r15, [%r14]+		;//     %r15 := chain = phm->owner, %r14 := (unsigned)(phm+1)
		xcmp		%r9, 0x1111		;//     if(owner != HMO_NOREF_USER)
		jrne		gc_scan_NEXT_PHM	;//       goto gc_scan_NEXT_PHM
		;//
		cmp		%r11, %r14		;//     if(addr < (unsigned)(phm+1))
		jrult		gc_scan_NEXT_PHM	;//       goto gc_scan_NEXT_PHM
		;//
		cmp		%r7, 1			;//     if(level <= GC_LEVEL_INTERMEDIATE) {
		jrle.d		4			;//       %r9  := limit = chain
		 ld.w		%r9, %r15		;//     } else {						*delay*
		 ld.w		%r9, %r14		;//       %r9  := limit = (unsigned)(phm+1)+1
		 add		%r9, 1			;//     }
		cmp		%r11, %r9		;//     if(addr >= limit)
		jruge		gc_scan_NEXT_PHM	;//       goto gc_scan_NEXT_PHM
		;//
		sub		%r14, 6			;//     %r14 := &phm->owner
		xld.w		%r9, 0x2222		;//              phm->owner = HMO_NOSCAN_USER
		ld.h		[%r14], %r9
		jp.d		gc_scan_NEXT_POS	;//     goto gc_scan_NEXT_POS
		ld.w		%r10, 1			;//     result = 1						*delay*
		;//-------------------------------------;//
;//{{==================== ブロックC ====================;//
gc_scan_NEXT_PHM:
		;// %r4  := sram_top
		;// %r5  := sram_end
		;// %r6  := heaptop
		;// %r7  := level
		;// %r10 := result
		;// %r12 := pos
		;// %r13 := end
		;// %r15 := chain
		cmp		%r15, 0			;//   } while(chain)
		jrne.d		gc_scan_LOOP_PHM
		ld.w		%r14, %r15		;//   %r14 := phm = chain					*delay*
		;//-------------------------------------;//
gc_scan_NEXT_POS:
		;// %r4  := sram_top
		;// %r5  := sram_end
		;// %r6  := heaptop
		;// %r7  := level
		;// %r10 := result
		;// %r12 := pos
		;// %r13 := end
		cmp		%r12, %r13		;// } while(pos < end)
		jrult.d		gc_scan_LOOP_POS
		cmp		%r7, 1			;//						【←①】	*delay*
		;//
		ret					;// return result
");
#else//↓僅かでも高速化,省メモリ化するために、ブロックBとCの位置を入れ替えました。ブロックA末尾のjp命令を、【節約】できました。
asm("
		.code
		.align		1
;//{{==================== ブロックA ====================;//
gc_scan:
		;// %r12 := pos = top
		;// %r13 := end
		xld.w		%r9, _gc+4		;// %r9  :=           &_gc.sram_top
		ld.w		%r4, [%r9]+		;// %r4  := sram_top = _gc.sram_top
;//{{2012/11/30変更
;//		ld.w		%r5, [%r9]		;// %r5  := sram_end = _gc.sram_end
;//		add		%r9, 12			;// %r9  :=           &_gc.heaptop
;//↓2012/11/30変更
		ld.w		%r5, [%r9]+		;// %r5  := sram_end = _gc.sram_end
;//}}2012/11/30変更
		ld.w		%r6, [%r9]+		;// %r6  := heaptop  = _gc.heaptop
		ld.ub		%r7, [%r9]		;// %r7  := level    = _gc.level
		jp.d		gc_scan_NEXT_POS	;// goto gc_scan_NEXT_POS
		ld.w		%r10, 0			;// %r10 := result   = 0					*delay*
gc_scan_LOOP_POS:					;// do {
		;//-------------------------------------;//
		;// %r4  := sram_top
		;// %r5  := sram_end
		;// %r6  := heaptop
		;// %r7  := level
		;// %r10 := result
		;// %r12 := pos
		;// %r13 := end
		ld.w		%r11, [%r12]+		;//   %r11 := addr = *pos++
		;//
;//		cmp		%r7, 1			;//   if(level >= GC_LEVEL_INTERMEDIATE) {	【→①】
		jrlt.d		5
		 ld.w		%r15, %r6		;//   %r15 := chain = heaptop	←───┐			*delay*
		 ld.w		%r9, %r11		;//     if(addr & 3) {			│
		 and		%r9, 3			;//       goto gc_scan_NEXT_POS		│
		 jrne		gc_scan_NEXT_POS	;//     }				│
		;//					;//   }					│
		cmp		%r11, %r4		;//   if(addr <  sram_top)		│
		jrult		gc_scan_NEXT_POS	;//     goto gc_scan_NEXT_POS		│
		cmp		%r11, %r5		;//   if(addr >= sram_end)		│
		jruge		gc_scan_NEXT_POS	;//     goto gc_scan_NEXT_POS		│
		;//					;//   }					│
;//【節約】	jp.d		gc_scan_NEXT_PHM	;//   goto gc_scan_NEXT_PHM		│
;//		ld.w		%r15, %r6		;//   %r15 := chain = heaptop	────┘			*delay*
;//{{==================== ブロックC ====================;//
gc_scan_NEXT_PHM:
		;// %r4  := sram_top
		;// %r5  := sram_end
		;// %r6  := heaptop
		;// %r7  := level
		;// %r10 := result
		;// %r12 := pos
		;// %r13 := end
		;// %r15 := chain
		cmp		%r15, 0			;//   } while(chain)
		jrne.d		gc_scan_LOOP_PHM
		ld.w		%r14, %r15		;//   %r14 := phm = chain					*delay*
		;//-------------------------------------;//
gc_scan_NEXT_POS:
		;// %r4  := sram_top
		;// %r5  := sram_end
		;// %r6  := heaptop
		;// %r7  := level
		;// %r10 := result
		;// %r12 := pos
		;// %r13 := end
		cmp		%r12, %r13		;// } while(pos < end)
		jrult.d		gc_scan_LOOP_POS
		cmp		%r7, 1			;//						【←①】	*delay*
		;//
		ret					;// return result
;//{{==================== ブロックB ====================;//
gc_scan_LOOP_PHM:					;//   do {
		;//-------------------------------------;//
		;// %r4  := sram_top
		;// %r5  := sram_end
		;// %r6  := heaptop
		;// %r7  := level
		;// %r10 := result
		;// %r11 := addr
		;// %r12 := pos
		;// %r13 := end
		;// %r14 := phm
		ld.uh		%r9, [%r14]+		;//     %r9  := mark  = phm->mark
		;//
		xcmp		%r9, 0xA431		;//     if(mark != HEAPMEMMK)
		jrne		gc_scan_DIE		;//       goto gc_scan_DIE
		;//
		ld.uh		%r9, [%r14]+		;//     %r9  := owner = phm->owner
		ld.w		%r15, [%r14]+		;//     %r15 := chain = phm->owner, %r14 := (unsigned)(phm+1)
		xcmp		%r9, 0x1111		;//     if(owner != HMO_NOREF_USER)
		jrne		gc_scan_NEXT_PHM	;//       goto gc_scan_NEXT_PHM
		;//
		cmp		%r11, %r14		;//     if(addr < (unsigned)(phm+1))
		jrult		gc_scan_NEXT_PHM	;//       goto gc_scan_NEXT_PHM
		;//
		cmp		%r7, 1			;//     if(level <= GC_LEVEL_INTERMEDIATE) {
		jrle.d		4			;//       %r9  := limit = chain
		 ld.w		%r9, %r15		;//     } else {						*delay*
		 ld.w		%r9, %r14		;//       %r9  := limit = (unsigned)(phm+1)+1
		 add		%r9, 1			;//     }
		cmp		%r11, %r9		;//     if(addr >= limit)
		jruge		gc_scan_NEXT_PHM	;//       goto gc_scan_NEXT_PHM
		;//
		sub		%r14, 6			;//     %r14 := &phm->owner
		xld.w		%r9, 0x2222		;//              phm->owner = HMO_NOSCAN_USER
		ld.h		[%r14], %r9
		jp.d		gc_scan_NEXT_POS	;//     goto gc_scan_NEXT_POS
		ld.w		%r10, 1			;//     result = 1						*delay*
		;//-------------------------------------;//
");
#endif
static void __attribute__((unused)) gc_scan_DIE() { DIE(); } /* asmブロックから参照 */
#endif/*PIECE*/
//}}2012/11/27変更,2012/11/29変更

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();
	}
//{{2012/11/27追加
	/* 確保したメモリブロックを、(-1)でクリアします。
	 * - 理由1:
	 *   メモリブロックの中に、以前に確保した際に書き込んだポインタ値が残っていて、有効な参照と見なしてしまうことを避けるためです。
	 *   GC_LEVEL_AGGRESSIVEではさほど問題になりませんが、GC_LEVEL_CONSERVATIVEとGC_LEVEL_INTERMEDIATEでは、実用上、この処理が必須です。
	 *   この処理を行わないと、実際には使用していないメモリブロックを開放しないケースが多く、すぐにメモリ不足エラーが発生しました。
	 *   特に、古いHEAPMEM構造体の値が、メモリブロックの中に残っていると、誤って有効な参照と見なしやすいため、クリアすることが必須です。
	 * - 理由2:
	 *   0でなく(-1)でクリアすることにした理由は、GC_LEVEL_AGGRESSIVE又はGC_LEVEL_INTERMEDIATEの場合に、早く無効な参照と判断できるからです。
	 *   GC_LEVEL_AGGRESSIVEとGC_LEVEL_INTERMEDIATEは、ワード境界を指していない数値を、無効な参照と判断して、最初に除外しています。
	 *   具体的には、gc_scan()の実装を参照してください。
	 *   理由2は重要な点ではなく、実際には、0でクリアしてもほとんど違いはありません。
	 * - 考察
	 *   今回の変更により、確保したメモリブロック全体を毎回クリアする処理が増えたため、かなり性能低下したと思います。
	 *   ただし、GCを使用するアプリケーションは、元々速度にシビアではないと思うため、この点は許容することにしました。
	 */
	memset(ptr, -1, size);
//}}2012/11/27追加

	return ptr;
}

