/* java_object.cpp
   Copyright (C) 2005 Free Software Foundation, Inc.

This file is part of Mysaifu JVM

Mysaifu JVM is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; version 2 of the License.

Mysaifu JVM is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.
*/

#include "StdAfx.h"
#include <tchar.h>
#include "java_object.h"
#include "class_loader.h"
#include "ClassFile.h"
#include "java_utf8.h"
#include "instruction.h"
#include "java_thread.h"
#include "common_funcs.h"
#include "console.h"

#ifdef DEBUG

/**
 * ヒープの統計情報を出力するファイル
 */
//	#define	HEAP_STATISTICS_FILE	_T("\\heap_statistics.txt")

	#ifdef HEAP_STATISTICS_FILE
		#include <stdio.h>
		FILE* g_heap_statistics_file;
	#endif

#endif

/**
 * スモールヒープを使用する場合にはこのマクロに０以外の値を定義する
 */
#define SMALL_HEAP_ENABLED	1

/**
 * スモールヒープブロックサイズ
 */
#define	SMALL_BLOCK_SIZE	64

/**
 * スモールヒープブロックカウント
 */
#define	SMALL_BLOCK_COUNT	256

/**
 * スモールヒープエレメント
 */
struct small_heap_element {
	/**
	 * 空き領域フラグ
	 */
	__int32 flags[SMALL_BLOCK_COUNT];

	/**
	 * データ
	 */
	char data[SMALL_BLOCK_SIZE * SMALL_BLOCK_COUNT * 32];
};

/**
 * スモールヒープ領域
 */
static small_heap_element* g_heap_elements[4096];
static char	g_heap_flags[4096];

/**
 * ファイナライザ構造体
 */
struct finalizer {
	/**
	 * 実行状態を制御するためのハンドル
	 */
	HANDLE hWaiting;

	/**
	 * ターゲットオブジェクトの数
	 */
	unsigned int count;
	
	/**
	 * 配列の大きさ
	 */
	unsigned int array_size;

	/**
	 * finalize()呼び出し対象となるオブジェクトの配列
	 */
	jobject* target_objects;

	/**
	 * ファイナライザがアイドル状態かどうかのフラグ
	 */
	bool idling;

	/**
	 * この構造体のメンバを読み書きする際に使用する
	 * CRITICAL_SECTION
	 */
	LPCRITICAL_SECTION	lock;
};

/**
 * ファイナライザ
 */
static finalizer* g_finalizer;

/**
 * finalize()を持つオブジェクトを生成した数。
 * GCが呼び出されるたびにクリアされる
 */
static int g_finalize_objects_count;

/**
 * g_finalize_objects_count がこの定数を超えると、強制的にGCされる
 */
#define FINALIZE_OBJECTS_COUNT_THRESHOLD	512

/**
 * ガベージコレクタが使用するフラグのフォーマットは以下のとおり
 *
 * ビット0-7 : 現在未使用。将来は以下の用途で使用する予定。
 *			   アドレスロックカウント。カウントが1以上の場合、ガベージコレクタはオブジェクトの
 *            アドレスを移動できない
 * ビット8   : GCマーク。markフェーズでセットされ、sweepフェーズでクリアされる。
 * ビット9   : ファイナライズ到達可能マーク。オブジェクト生成時にセットされ、finalize()実行後にクリアされる
 * ビット10  : このオブジェクトがクラスオブジェクト（staticフィールドの値を保持しているオブジェクト）
 *             の場合にセットされる
 * ビット11  : 未使用。Version 0.2.3までは以下の意味で使用していた。
 *			   オブジェクトの種別を示す。意味は以下のとおり
 *               0 非配列または1次元プリミティブ配列。
 *               1 オブジェクト配列または多次元配列。（各要素にはオブジェクトの参照が入る）
 * ビット12-13 : 未使用。Version 0.2.3までは以下の意味で使用していた。
 *				配列要素のサイズ。配列でない場合は意味を持たない
 *               00 - 1バイト
 *               01 - 2バイト
 *               10 - 4バイト
 *               11 - 8バイト
 * ビット14:   「リファレント」マーク。強到達ではないが、不可到達ではないオブジェクトを
 *　　　　　　示すマーク。markフェーズでセットされ、sweepフェーズでクリアされる。
 * ビット15-16 : 参照オブジェクトの種別を表す
 *               00 - 参照オブジェクトではない
 *               01 - SoftReference
 *               10 - WeakReference
 *               11 - PhantomReference
 * ビット17-31 : 予約ビット
 */

/**
 * ガベージコレクタマーク
 */
#define	GC_MARKED		(1L << 8)

/**
 * ファイナライザが到達可能なオブジェクト
 */
#define	FINALIZE_MARK	(1L << 9)

/**
 * staticデータ
 */
#define STATIC_DATA	(1L << 10)

/**
 * 「リファレント」マーク
 */
#define REFERENT_MARK	(1 << 14)

/**
 * SoftReference/WeakReference/PhantomReferenceフラグ
 */
#define SOFT_REFERENCE_FLAG		(1 << 15)
#define WEAK_REFERENCE_FLAG		(2 << 15)
#define PHANTOM_REFERENCE_FLAG	(3 << 15)

#define GET_FIELD(current_frame, address, descriptor, pop_stack) \
{\
	switch (descriptor[0]) { \
	case 'Z': \
	case 'B': \
		{\
			__int8 value = *(__int8*) address; \
			if (pop_stack) { \
				POP_DISCARD(current_frame);\
			}\
			PUSH_INT(current_frame, value); \
		} \
		break; \
	\
	case 'C': \
		{ \
			unsigned __int16 value = *(unsigned __int16*) address; \
			if (pop_stack) { \
				POP_DISCARD(current_frame);\
			}\
			PUSH_INT(current_frame, value); \
		} \
		break; \
	\
	case 'S': \
		{ \
			__int16 value = *(__int16*) address; \
			if (pop_stack) { \
				POP_DISCARD(current_frame);\
			}\
			PUSH_INT(current_frame, value); \
		} \
		break; \
	\
	case 'I': \
		{ \
			__int32 value = *(__int32*) address; \
			if (pop_stack) { \
				POP_DISCARD(current_frame);\
			}\
			PUSH_INT(current_frame, value); \
		} \
		break; \
	\
	case 'J': \
		{ \
			__int64 value = *(__int64*) address; \
			if (pop_stack) { \
				POP_DISCARD(current_frame);\
			}\
			PUSH_LONG(current_frame, value); \
		} \
		break; \
	\
	case 'F': \
		{ \
			float value = *(float*) address; \
			if (pop_stack) { \
				POP_DISCARD(current_frame);\
			}\
			PUSH_FLOAT(current_frame, value); \
		} \
		break; \
	\
	case 'D': \
		{ \
			double value = *(double*) address; \
			if (pop_stack) { \
				POP_DISCARD(current_frame);\
			}\
			PUSH_DOUBLE(current_frame, value); \
		} \
		break; \
	\
	case 'L': \
	case '[': \
		{ \
			jobject value = *(jobject*) address; \
			if (pop_stack) { \
				POP_DISCARD(current_frame);\
			}\
			PUSH_OBJECT(current_frame, value); \
		} \
		break; \
	\
	default: \
		assert(false); \
	} \
}

#define PUT_FIELD(current_frame, address, descriptor) \
{\
	switch (descriptor[0]) { \
	case 'Z': \
	case 'B': \
		{\
			__int32 value; \
			POP_INT(current_frame, value); \
			*(__int8*) address = (__int8) value; \
		} \
		break; \
	\
	case 'C': \
		{ \
			__int32 value; \
			POP_INT(current_frame, value); \
			*(unsigned __int16*) address = (unsigned __int16) value; \
		} \
		break; \
	\
	case 'S': \
		{ \
			__int32 value; \
			POP_INT(current_frame, value); \
			*(__int16*) address = (__int16) value; \
		} \
		break; \
	\
	case 'I': \
		{ \
			__int32 value; \
			POP_INT(current_frame, value); \
			*(__int32*) address = value; \
		} \
		break; \
	\
	case 'J': \
		{ \
			__int64 value; \
			POP_LONG(current_frame, value); \
			*(__int64*) address = value; \
		} \
		break; \
	\
	case 'F': \
		{ \
			float value; \
			POP_FLOAT(current_frame, value); \
			*(float*) address = value; \
		} \
		break; \
	\
	case 'D': \
		{ \
			double value; \
			POP_DOUBLE(current_frame, value); \
			*(double*) address = value; \
		} \
		break; \
	\
	case 'L': \
	case '[': \
		{ \
			jobject value; \
			POP_OBJECT(current_frame, value); \
			*(jobject*) address = value; \
		} \
		break; \
	\
	default: \
		assert(false); \
	} \
}

/**
 * -Xloggc:filenameオプションで指定されたファイル名
 */
static _TCHAR* g_loggc_filename;

/**
 * -verbose:gc が指定されているか
 */
static boolean g_verbose_gc;

/**
 * ClassFileの配列
 */
static ClassFile** g_class_files;

/**
 * クラスオブジェクトのスタック
 */
static frame* g_static_data_stack;

#define STATIC_DATA_STACK_SIZE	4096

/**
 * 「ルート」ヒープ領域へのポインタ
 */
static java_object* g_heap_root = NULL;

/**
 * 最大ヒープサイズ(バイト）
 */
static unsigned int g_max_heap_size = 2 * 1024 * 1024;

/**
 * 現在確保済みヒープサイズ
 */
static unsigned int g_allocated_size;

/**
 * ガベージコレクタ走行中フラグ
 */
static bool g_gc_running = false;

/**
 * GC中にjava.lang.ref.Reference オブジェクトを格納する配列の要素数
 */
static int g_references_count;

/**
 * GC中にjava.lang.ref.Referenceオブジェクトを格納する配列
 */
static jobject* g_references;

/**
 * java.lang.ref.Reference.lock オブジェクト
 * GC中はこのオブジェクトのモニタを取得しておく。
 */
static jobject g_Reference_lock;

// --- static変数の定義 ここまで ---


// --- static関数の宣言 ここから ---
static inline bool is_non_primitive_array(java_object* obj);

static void gc_mark();
static void gc_mark(frame* sframe);
static void gc_mark(jobject obj, int marktype);
static void gc_start_finalizer();
static void gc_enqueue();
static void gc_prepare_finalize();

#ifndef USE_JAVA_HEAP
static void gc_sweep();
#endif

static void gc_wakeup_finalizer(finalizer* f);
static bool is_idling(finalizer* f);

static int get_reference_type_flag(java_object* obj);

//--- static関数の宣言　ここまで

#ifdef USE_JAVA_HEAP

/**
 * チェック用データ
 */
#define CHECK_DATA     ((unsigned char) 0xEF)

class JavaHeap {
private:
	/**
	 * ビットマスク
	 */
	static const __int32 BIT_MASK[32];

	/**
	 * オブジェクトのアライメント
	 */
	static const int OBJECT_ALIGN = 8;

	/**
	 * ビットフラグ配列1要素あたりのビット数
	 */
	static const int NUM_BITS = 32;

	/**
	 * 割り当て中アドレスを示すビット列
	 */
	__int32* allocatedBits;

	/**
	 * ヒープの開始位置
	 */
	char* heapBase;

	/**
	 * 未Commitアドレスの開始位置
	 */
	char* startOfUncommitted;

	/**
	 * ヒープリミット
	 */
	char* heapLimit;

	/**
	 * 空き領域のリンクリスト
	 */
	java_object* freeObjects;

	/**
	 * メモリをコミットする
	 */
	char* commitNextBlock();

	/**
	 * 指定されたアドレスに対応するビットフラグ配列のインデックスを得る
	 */
	inline int getFlagIndex(java_object* addr) {
		assert(((unsigned int)addr%OBJECT_ALIGN) == 0);
		assert((char*) addr >= this->heapBase && (char*) addr < this->heapLimit);
		return ((unsigned int)addr - (unsigned int) this->heapBase) / (OBJECT_ALIGN * NUM_BITS);
	}

	/**
	 * 指定されたアドレスに対応するビットフラグ配列のビットマスクを得る
	 */
	inline __int32 getFlagMask(java_object* addr) {
		assert(((unsigned int)addr%OBJECT_ALIGN) == 0);
		assert((char*) addr >= this->heapBase && (char*) addr < this->heapLimit);

		return BIT_MASK[(((unsigned int)addr - (unsigned int)this->heapBase) / 8 ) % NUM_BITS];
	}

	/**
	 * 指定されたアドレス位置にオブジェクトが存在するかを判定する
	 * mark()フェーズで使用する
	 */
	inline bool isObject(java_object* addr) {
		assert(((unsigned int)addr%OBJECT_ALIGN) == 0);
		assert((char*) addr >= this->heapBase && (char*) addr < this->heapLimit);

		return (((unsigned int) addr % OBJECT_ALIGN) == 0)
					&& this->allocatedBits[getFlagIndex(addr)]&getFlagMask(addr);
	}

	/**
	 * 指定されたアドレス位置を allocatedBits に記録する
	 * allocate()が使用する
	 */
	inline void setAllocatedBit(java_object* addr) {
		assert(((unsigned int)addr%OBJECT_ALIGN) == 0);
		assert((char*) addr >= this->heapBase && (char*) addr < this->heapLimit);

		this->allocatedBits[getFlagIndex(addr)] |= getFlagMask(addr);
	}

	/**
	 * 指定されたアドレス位置に対応する allocatedBits をクリアする
	 * sweep()時に使用する
	 */
	inline void clearAllocatedBit(java_object* addr) {
		assert(((unsigned int)addr%OBJECT_ALIGN) == 0);
		assert((char*) addr >= this->heapBase && (char*) addr < this->heapLimit);

		this->allocatedBits[getFlagIndex(addr)] &= ~getFlagMask(addr);
	}

	/**
	 * チェックデータを書き込む
	 */
	inline void writeCheckData(java_object* addr) {
		*(char*)((char*) addr + addr->size - 1) = (char) CHECK_DATA;
	}

public:
	/**
	 * JavaHeapを作成する
	 *
	 * @param	最大ヒープサイズ
	 */
	JavaHeap(size_t maxSize);
	
	~JavaHeap();

	/**
	 * 指定されたサイズのメモリをJavaヒープから割り当てる
	 */
	java_object* allocate(size_t size);

	/**
	 * sweepを行う。
	 */
	void sweep();
};

static JavaHeap* g_JavaHeap;

#endif

/**
 * ヒープ領域を初期化する
 *
 * @param	max_size	ヒープの最大サイズ
 */
void initialize_heap(unsigned int max_size) {
	g_max_heap_size = max_size;
	g_allocated_size = 0;
	g_static_data_stack = alloc_root_frame(NULL, STATIC_DATA_STACK_SIZE);

	// スモールヒープのフラグを初期化する
	memset(g_heap_flags, 1, sizeof(g_heap_flags));

#ifdef HEAP_STATISTICS_FILE
	// ヒープ統計情報を出力する
	g_heap_statistics_file = _tfopen(HEAP_STATISTICS_FILE, _T("w"));
#endif

#ifdef USE_JAVA_HEAP
	g_JavaHeap = new JavaHeap(max_size);
#endif
}

/**
 * ガベージコレクタを初期化する
 */
bool init_gc() {
	jobject lock_object = NULL;
	frame* root_frame = alloc_root_frame(NULL);
	ClassFile* reference_class = find_ClassFile(root_frame,
												intern_utf8("java/lang/ref/Reference"));
	if (reference_class != NULL) {
		jfieldID lock = get_static_field_id(reference_class, intern_utf8("lock"), intern_utf8("Ljava/lang/Object;"));
		get_static_field(root_frame, get_static_data(reference_class), lock);
		POP_OBJECT(root_frame, lock_object);
	}
	free_root_frame(root_frame);
	if (lock_object != NULL) {
		g_Reference_lock = lock_object;
		return true;
	} else {
		return false;
	}
}

/**
 * 64バイト分のメモリを確保する
 */
static void* alloc_64bytes(small_heap_element* elem) {
	for (int i = 0; i < SMALL_BLOCK_COUNT; ++i) {
		__int32 flag = elem->flags[i];
		if (flag) {
			// 一番右端で"1"となっているビットの位置を求めた後、一番右端で"1"となっているビットを0にする
			int pos = count_bits((flag & (-flag)) - 1);										
			elem->flags[i] = flag & ((unsigned __int32) flag - 1);
			
			// オフセットを計算する
			unsigned int offset = (i * SMALL_BLOCK_SIZE * 32) + (pos * SMALL_BLOCK_SIZE);
			return elem->data + offset;
		}
	}
	return NULL;
}

/**
 * スモールヒープエレメントを確保する
 */
static small_heap_element* alloc_small_heap_element() {
//	small_heap_element* elem = (small_heap_element*) malloc(sizeof(small_heap_element));
	small_heap_element* elem = (small_heap_element*) calloc(sizeof(small_heap_element), 1);
	if (elem != NULL) {
		memset(elem->flags, 0xff, sizeof(elem->flags));
	}
	return elem;
}

/**
 * 64バイト分のメモリを確保する
 */
static void* alloc_64bytes() {
	void* result = NULL;
	for (int i = 0; i < sizeof(g_heap_elements) / sizeof(*g_heap_elements); ++i) {
		if (g_heap_flags[i]) {
			small_heap_element* elem = g_heap_elements[i];
			if (elem == NULL) {
				elem = alloc_small_heap_element();
				if (elem == NULL) {
					break;
				}
				g_heap_elements[i] = elem;
			}
			result = alloc_64bytes(elem);
			if (result != NULL) {
				break;
			} else {
				g_heap_flags[i] = 0;
			}
		}
	}
	// ゼロクリアは領域が開放された時点で行われているため、
	// ここで行う必要はない
//	if (result != NULL) {
//		memset(result, 0, SMALL_BLOCK_SIZE);
//	}
	return result;
}

/**
 * 64バイト分のメモリを開放する
 */
static void free_64bytes(small_heap_element* elem, void* p) {
	unsigned int offset = (char*) p - elem->data;
	int index = offset / (SMALL_BLOCK_SIZE * 32);
	int pos = (offset - (index * SMALL_BLOCK_SIZE * 32)) / SMALL_BLOCK_SIZE;
	elem->flags[index] |= (1 << pos);
}

static void free_64bytes(void* p) {
	for (int i = 0; i < sizeof(g_heap_elements) / sizeof(*g_heap_elements); ++i) {
		small_heap_element* elem = g_heap_elements[i];
		if (elem != NULL) {
			if (p >= elem->data && p < elem->data + sizeof(elem->data)) {
				// 次回使用に備えてゼロクリアしておく
				memset(p, 0, SMALL_BLOCK_SIZE);
				free_64bytes(elem, p);
				g_heap_flags[i] = 1;	// 少なくとも１つの空きがある
				return;
			}
		}
	}
	// おかしなポインタが渡された
	assert(false);
	fatal_error(_T("free_64bytes() failed."));
}

/**
 * ヒープからメモリを確保する
 */
static void* heap_alloc(size_t size) {
#ifdef USE_JAVA_HEAP

	return g_JavaHeap->allocate(size);

#else

#if SMALL_HEAP_ENABLED
	// スモールヒープサイズ処理
	if (size <= SMALL_BLOCK_SIZE) {
		size = SMALL_BLOCK_SIZE;
	}
#endif
	assert(! g_gc_running);	// GC実行中は新規ヒープを確保できない

	if (g_allocated_size + size >= g_max_heap_size) {
		gc();
		if (g_allocated_size + size >= g_max_heap_size) {
			return NULL;
		}
	}

	// メモリを確保し、0で初期化する
	java_object* elem;

#if SMALL_HEAP_ENABLED
	// スモールヒープ確保処理を行う
	if (size == SMALL_BLOCK_SIZE) {
		elem = (java_object*) alloc_64bytes();
	} else {
		elem = (java_object*) calloc(size, 1);
	}
#else
	elem = (java_object*) calloc(size, 1);
#endif

	if (! elem) {
		// GCを実行してみる
		gc();
#if SMALL_HEAP_ENABLED
		// スモールヒープ確保処理を行う
		if (size == SMALL_BLOCK_SIZE) {
			elem = (java_object*) alloc_64bytes();
		} else {
			elem = (java_object*) calloc(size, 1);
		}
#else
		elem = (java_object*) calloc(size, 1);
#endif
		if (!elem) {
			// ギブアップ
			return elem;
		}
	}

	// 確保したサイズを加算する
	g_allocated_size += size;
	elem->size = size;

	if (g_heap_root == NULL) {
		// リスト先頭要素を作成する
		elem->next = NULL;
		g_heap_root = elem;
	} else {
		// リストの先頭に確保したヒープを挿入する
		elem->next = g_heap_root;
		g_heap_root = elem;
	}

#ifdef	HEAP_STATISTICS_FILE
	_TCHAR buff[128];
	_stprintf(buff, _T("%d bytes allocated.\n"), size);
	_fputts(buff, g_heap_statistics_file);
#endif

	return elem;

#endif /* ! USE_JAVA_HEAP */
}

/**
 * ヒープからメモリを開放する
 */
#ifndef USE_JAVA_HEAP
static void heap_free(java_object* elem) {
	// 開放したサイズ分減算する
	int size = elem->size;
	g_allocated_size -= size;

#ifdef DEBUG
	// 開放した領域にアクセスしてしまったことを検知できるように印をつけておく
	ClassFile* cfile = elem->class_file;
	memset(elem, 0xff, size);
	elem->class_file = cfile;
#endif
	
#if SMALL_HEAP_ENABLED
	if (size <= SMALL_BLOCK_SIZE) {
		free_64bytes(elem);
	} else {
		// ランタイムライブラリにメモリを返却する
		free(elem);
	}
#else
	free(elem);
#endif

}
#endif

/**
 * 指定されたオブジェクトが、非プリミティブ配列かを返す
 */
static inline bool is_non_primitive_array(java_object* obj) {
	java_utf8* name = obj->class_file->this_class_name;
	return name[0] == '[' && (name[1] == 'L' || name[1] == '[');
}

/**
 * 指定されたクラスのstaticデータオブジェクトを作成する。
 * このオブジェクトはガベージコレクトされないように保護される。
 *
 * @param	cfile	ClassFile構造体のポインタ。
 * @return	クラスオブジェクト。作成できなかった場合はNULL。
 */
jobject alloc_static_data(ClassFile* cfile) {
	// クリティカルセクションに入る
	EnterCriticalSection(&g_global_critical_section);

	// 確保するメモリサイズを計算する
	unsigned int static_fields_size = get_static_fields_size(cfile);
	size_t size = sizeof(java_object) + static_fields_size;

	java_object* data = (java_object*) heap_alloc(size);
	if (data != NULL) {
		data->class_file = cfile;
		data->count = static_fields_size;
		data->flags |= STATIC_DATA;
		if (! ensure_stack_capacity(g_static_data_stack)) {
			fatal_error(_T("g_static_data_stack overflow"));
		}
		PUSH_OBJECT(g_static_data_stack, (jobject) data);
	}

	// クリティカルセクションから抜ける
	LeaveCriticalSection(&g_global_critical_section);

	return (jobject) data;
}

/**
 * 指定されたクラスのインスタンスデータ領域を作成する
 * この関数の呼び出しに先立って、指定されたクラスおよびスーパークラス、スーパーインスタンスの
 * 初期化が完了していなければならない
 *
 * @param	cfile	ClassFile構造体のポインタ。
 * @param	参照をpushするスタック
 * @return	オブジェクトへの参照。確保できなかった場合はNULL。
 */
jobject alloc_object(ClassFile* cfile, frame* stack) {
	// クリティカルセクションで保護する
	EnterCriticalSection(&g_global_critical_section);

	assert(cfile->this_class_name[0] != '[');

	bool finalize_object = has_finalizer(cfile);
	if (finalize_object) {
		g_finalize_objects_count++;
		if (g_finalize_objects_count > FINALIZE_OBJECTS_COUNT_THRESHOLD) {
			// finalize()オブジェクトの数が閾値を超えたので強制的にGCする
			gc();
		}
	}

	// このクラスのフィールドサイズを取得する
	int fields_size = get_fields_size(cfile);
	assert(fields_size >= 0);

	// ヒープ領域からメモリを確保する
	size_t size = sizeof(java_object) + fields_size;
	java_object* data = (java_object*) heap_alloc(size);
	if (data == NULL) {
		// メモリを確保できない場合は、OutOfMemoryErrorをthrowする
		throw_OutOfMemoryError(stack);
	} else {

		// ファイナライザを保持しているかを調べ、オブジェクトに印をつけておく
		if (finalize_object) {
			data->flags |= FINALIZE_MARK;
		}

		// 必要となるデータを初期化する
		data->class_file = cfile;
		data->count = fields_size;
		
		// スタックにpushする
		PUSH_OBJECT(stack, (jobject) data);
	}		
	// クリティカルセクションを終了する
	LeaveCriticalSection(&g_global_critical_section);

	return (jobject) data;
}

/**
 * 指定された配列の領域を作成する
 * この関数の呼び出しに先立って、指定されたクラスおよびスーパークラス、スーパーインスタンスの
 * 初期化が完了していなければならない
 *
 * @param	cfile	ClassFile構造体のポインタ。配列クラスを表していなければならない。
 * @param	count	配列の要素数。正数でなければならない。
 * @return	配列の内容を保持する領域。確保できなかった場合はNULL。
 */
jarray alloc_array(ClassFile* cfile, __int32 count, frame* stack) {
	// クリティカルセクションに入る
	EnterCriticalSection(&g_global_critical_section);
	
	assert(count >= 0);
	assert(cfile->this_class_name[0] == '[');

	// ヒープ領域からメモリを確保する
	unsigned int component_size = get_array_component_size(cfile->this_class_name);
	size_t size = sizeof(java_object)
				+ component_size * count;
	java_object* data = (java_object*) heap_alloc(size);
	if (data == NULL) {
		// メモリ不足の場合はOutOfMemoryErrorをthrowする
		throw_OutOfMemoryError(stack);
	} else {
		// データを初期化する
		data->class_file = cfile;

		// array.length を count に入れる
		data->count = count;

		// スタックにpushする
		PUSH_OBJECT(stack, (jobject) data);
	}

	// クリティカルセクションを終了する
	LeaveCriticalSection(&g_global_critical_section);

	return (jarray) data;
}

/**
 * 指定されたUTF-8文字列をJavaのchar[]に変換する
 * 指定されたUTF-8文字列がUnicodeに変換された後、そのUnicode文字列を保持する
 * char配列が作成される
 *
 * @param	cfile	char[]を表すClassFile構造体。(クラス名は"[C")
 * @param	utf8	UTF-8文字列
 * @param	stack	作成した配列の参照をpushするスタック・フレーム。
 * @return	作成した配列の参照。作成できなかった場合NULL
 */
jcharArray alloc_char_array(ClassFile* cfile, const java_utf8* utf8, frame* stack) {
	// クリティカルセクションに入る
//	EnterCriticalSection(&g_global_critical_section);
	
	// Unicodeバッファを作成する
	int unicode_length = strlen(utf8) * 2 + 1;
	TCHAR* unicode = (TCHAR*) malloc(sizeof(TCHAR) * unicode_length);
	if (unicode == NULL) {
		fatal_error(FATAL_ERROR_NO_MEMORY);
	}
	jcharArray array_reference = NULL;
	// UTF-8をUnicodeにコンバートする
	int len = convert_to_TCHAR(utf8, unicode, unicode_length);
	array_reference = alloc_char_array(cfile, unicode, len, stack);
	
	// 作成したUnicodeバッファを開放する
	free(unicode);

	// クリティカルセクションから抜ける
//	LeaveCriticalSection(&g_global_critical_section);

	return array_reference;
}

/**
 * 指定された参照の内容を複製する
 */
jobject clone(frame* frm, jobject ref) {
	ClassFile* cfile = get_ClassFile(ref);
	jobject result = NULL;
	if (is_array_class(cfile)) {
		result = alloc_array(cfile, get_array_length((jarray) ref), frm);
	} else {
		result = alloc_object(cfile, frm);
	}

	if (result != NULL) {
		java_object* dst = lock_address(result);
		void* dstptr = get_body_ptr(dst);

		java_object* src = lock_address(ref);
		void* srcptr = get_body_ptr(src);

		unsigned int bodysize = dst->size - sizeof(java_object);
		memcpy(dstptr, srcptr, bodysize);

		unlock_address(result);
		unlock_address(ref);
	}
	return result;
}

/**
 * 指定されたUnicode文字列をJavaのchar[]に変換する
 *
 * @param	cfile	char[]を表すClassFile構造体。(クラス名は"[C")
 * @param	unicode	Unicode文字列
 * @param	length	Unicode文字列の長さ。
 * @param	stack	作成した配列の参照をpushするスタック・フレーム。
 * @return	作成した配列の参照。作成できなかった場合NULL
 */
jcharArray alloc_char_array(ClassFile* cfile, _TCHAR* unicode, int length, frame* stack) {
	// クリティカルセクションに入る
//	EnterCriticalSection(&g_global_critical_section);
	
	// 配列オブジェクトを確保する
	jobject array_reference = alloc_array(cfile, length, stack);
	if (array_reference == NULL) {
		throw_OutOfMemoryError(stack);
	} else {
		// 配列要素にUnicode文字列を直接コピーする
		java_object* obj = lock_address(array_reference);
		TCHAR* buff = (TCHAR*) get_body_ptr(obj);
		memcpy(buff, unicode, sizeof(TCHAR) * length);
		unlock_address(array_reference);
	}
	
	// クリティカルセクションから抜ける
//	LeaveCriticalSection(&g_global_critical_section);

	return (jcharArray) array_reference;
}

/**
 * 指定された非staticフィールドに値を設定する
 *
 * @param	cfile	設定対象となるクラス
 * @param	index	カレントクラス内でのインデックス
 * @param	frame	設定値が格納されたスタックフレーム
 */
void put_field(frame* frame, ClassFile* cfile, jfieldID fid) {
	// フィールドサイズから、スタック上にある参照の位置を求める
	unsigned int size = get_field_info(cfile, fid)->size;
	int offset;
	switch (size) {
	case 1:
	case 2:
	case 4:
		offset = 1;
		break;
	case 8:
		offset = 2;
		break;
	default:
		// ここにはこないはず
		assert(false);
		return;
	}

	// 参照を取得する
	// ガベージコレクタに回収されてしまわないように、popはしない
	__int32 data;
	get_stack_data(frame, offset, &data);
	jobject ref = (jobject) data;
	if (ref == NULL) {
		throw_exception(frame, "java/lang/NullPointerException");
		return;
	}

	// オブジェクトのアドレスをロックする
	java_object* obj = lock_address(ref);

	// フィールドに値を設定する
	field_info* finfo = get_field_info(obj->class_file, fid);
	unsigned char* address = (unsigned char*) get_body_ptr(obj);
	address += finfo->position;
	PUT_FIELD(frame, address, finfo->descriptor);

	// 参照をpopする
	POP_OBJECT(frame, ref);
	
	// オブジェクトのアドレスをアンロックする
	unlock_address(ref);
}

/**
 * 指定された非staticフィールドに値を設定する
 *
 * @param	cfile	設定対象となるクラス
 * @param	index	カレントクラス内でのインデックス
 * @param	frame	設定値が格納されたスタックフレーム
 */
void put_field_by_position(frame* frame, const java_utf8* descriptor, unsigned int position) {
	// フィールドサイズから、スタック上にある参照の位置を求める
	u1 type = descriptor[0];
	
	int offset;
	switch (type) {
	case 'J':
	case 'D':
		offset = 2;
		break;

	default:
		offset = 1;
		break;
	}

	// 参照を取得する
	// ガベージコレクタに回収されてしまわないように、popはしない
	__int32 data;
	get_stack_data(frame, offset, &data);
	jobject ref = (jobject) data;
	if (ref == NULL) {
		throw_exception(frame, "java/lang/NullPointerException");
		return;
	}

	// オブジェクトのアドレスをロックする
	java_object* obj = lock_address(ref);

	// フィールドに値を設定する
	unsigned char* address = (unsigned char*) get_body_ptr(obj);
	address += position;
	PUT_FIELD(frame, address, descriptor);

	// 参照をpopする
	POP_OBJECT(frame, ref);
	
	// オブジェクトのアドレスをアンロックする
	unlock_address(ref);
}

/**
 * 指定されたstaticフィールドに値を設定する
 *
 * @param	ref		オブジェクトの参照
 * @param	fid		フィールドID
 * @param	frame	設定値が格納されたスタックフレームへのポインタ
 */
void put_static_field(frame* frame, jobject ref, jfieldID fid) {
	ClassFile* target_class_file = get_ClassFile(ref);
	field_info* finfo = get_static_field_info(target_class_file, fid);
	ClassFile* declaring_class_file = finfo->declaring_ClassFile;
	if (target_class_file != declaring_class_file) {
		ref = get_static_data(declaring_class_file);
	}

	// オブジェクトのアドレスをロックする
	java_object* obj = lock_address(ref);

	// フィールドに値を設定する
	unsigned char* address = (unsigned char*) get_body_ptr(obj);
	address += finfo->position;
	PUT_FIELD(frame, address, finfo->descriptor);

	// オブジェクトのアドレスをアンロックする
	unlock_address(ref);
}

/**
 * 指定されたstaticフィールドの値を返す
 *
 * @param	ref		オブジェクトへの参照。クラスオブジェクトでなければならない
 * @param	fid		フィールドID
 * @param	stack	フィールドの値を格納するスタック・フレーム
 */
bool get_static_field(frame* frame, jobject ref, jfieldID fid) {
	ClassFile* target_class_file = get_ClassFile(ref);
	field_info* finfo = get_static_field_info(target_class_file, fid);
	ClassFile* declaring_class_file = finfo->declaring_ClassFile;
	if (target_class_file != declaring_class_file) {
		ref = get_static_data(declaring_class_file);
	}
	// オブジェクトのアドレスをロックする
	java_object* obj = lock_address(ref);
	unsigned char* address = (unsigned char*) get_body_ptr(obj);
	address += finfo->position;
	GET_FIELD(frame, address, finfo->descriptor, false);
	
	// オブジェクトのアドレスをアンロックする
	unlock_address(ref);
	return true;
}

/**
 * 指定されたフィールドの値を返す
 *
 * @param	cfile	クラスファイル
 * @param	fid		フィールドID
 * @param	stack	フィールドの値を格納するスタック・フレーム
 */
bool get_field(frame* frame, ClassFile* cfile, jfieldID fid) {
	jobject ref;
	get_stack_data(frame, 0, (__int32*) &ref);

	// 参照がnullかを調べ、nullの場合はNullPointerExceptionをthrowする
	if (ref == NULL) {
		throw_exception(frame, "java/lang/NullPointerException");
		return false;
	}


	// オブジェクトのアドレスをロックする
	java_object* obj = lock_address(ref);
	
	field_info* finfo = get_field_info(obj->class_file, fid);
	// フィールドのアドレスを計算
	unsigned int position = finfo->position;
	unsigned char* ptr = (unsigned char*) get_body_ptr(obj);
	ptr += position;

	// ガベージコレクトを避ける
//	jobject global_ref = new_global_reference(ref);	
//	POP_DISCARD(frame);
//	ref = global_ref;

	GET_FIELD(frame, ptr, finfo->descriptor, true);
	
	// アドレスをアンロックする
	unlock_address(ref);

	// ガベージコレクト可能にする
//	delete_global_reference(global_ref);	

	return true;
}

/**
 * 指定されたフィールドの値を返す
 *
 * @param	frame	フィールドの値を格納するフレーム
 * @param	finfo	field_info構造体へのポインタ
 * @param	offset	オブジェクト内のフィールドのオフセット値
 */
void get_field_by_position(frame* frame, const java_utf8* descriptor, unsigned int position) {
	jobject ref;
	get_stack_data(frame, 0, (__int32*) &ref);

	// 参照がnullかを調べ、nullの場合はNullPointerExceptionをthrowする
	if (ref == NULL) {
		throw_exception(frame, "java/lang/NullPointerException");
		return;
	}

	// オブジェクトのアドレスをロックし、フィールドのアドレスを取得する
	java_object* obj = lock_address(ref);
	unsigned char* ptr = (unsigned char*) get_body_ptr(obj) + position;

	// フィールド情報を取得し、frameにpushする
	GET_FIELD(frame,	// 結果をpushするframe
			  ptr,		// フィールドのアドレス
			  descriptor,	// ディスクリプタ
			  true);	// frameから参照値をpopする
	
	// アドレスをアンロックする
	unlock_address(ref);
}

/**
 * オブジェクトの配列要素を取得する
 */
bool load_object_array(jarray arrayref, __int32 index, jobject* pref) {
	java_object* obj = lock_address(arrayref); \
	if (index < 0 || index >= obj->count) { \
		unlock_address(arrayref); \
		return false; \
	} \
	jobject * body = (jobject *) get_body_ptr(obj); \
	*pref = body[index]; \
	unlock_address(arrayref); \
	return true; \
}

/**
 * 指定された配列の要素を設定する
 *
 * @param	arrayref	配列オブジェクト
 * @param	index		設定する構成要素のインデックス
 * @param	value		設定値
 * @return	正常に処理が完了できた場合true。インデックス値が配列の範囲外である場合false。
 */
bool store_object_array(jarray arrayref, __int32 index, jobject value) {
	java_object* obj = lock_address(arrayref);
	if (index < 0 || index >= obj->count) {
		unlock_address(arrayref);
		return false;
	}
	jobject* body = (jobject*) get_body_ptr(obj);
	body[index] = value;
	unlock_address(arrayref);
	return true;
}

/**
 * このオブジェクトのモニタを返す
 *
 */
monitor* get_monitor(jobject ref) {
	java_object* obj = lock_address(ref);
	monitor* monitor = obj->object_monitor;
	unlock_address(ref);
	return monitor;
}

/**
 * このオブジェクトのモニタを設定する
 *
 */
void set_monitor(jobject ref, monitor* m) {
	java_object* obj = lock_address(ref);
	obj->object_monitor = m;
	unlock_address(ref);
}

/**
 * ガベージコレクタを起動する
 */
void gc() {
	DBG(_T("GC invoked. size="));
	DBG_UINT(g_allocated_size);
	DBG(_T("\n"));

	// クリティカルセクションに入る
	EnterCriticalSection(&g_global_critical_section);
	if (g_gc_running) {
		// 再帰的に呼び出すことはできない
		LeaveCriticalSection(&g_global_critical_section);
		DBG(_T("GC recursive call, then return.\n"));
		return;
	}
	g_gc_running = true;

	// ファイナライズオブジェクト数をクリアする
	g_finalize_objects_count = 0;
	
	// 現行のスレッドのプライオリティを保存する
	int org_priority = CeGetThreadPriority(GetCurrentThread());
	
	// ガベージコレクションの処理を可能な限り早く終わらせるため、優先度を上げる
	CeSetThreadPriority(GetCurrentThread(), 248);

	// GC実行前のヒープサイズとパフォーマンスカウンタ値を取得しておく
	unsigned int before_size = g_allocated_size;
	LARGE_INTEGER before_counter;
	QueryPerformanceCounter(&before_counter);

	// java.lang.ref.Referenceのロックを取得する
	if (g_Reference_lock == NULL) {
		fatal_error(_T("Object java.lang.ref.Reference is null"));
	}
	monitor_enter(g_Reference_lock);

	DBG(_T("GC suspends all other threads\n"));
	// 全スレッドをサスペンドさせる
	if (! suspend_all_other_threads()) {
		 // スレッドをサスペンドできなかった。ギブアップ
		DBG(_T("FATAL: GC could not suspend all other threads.\n"));
		monitor_exit(g_Reference_lock);
		CeSetThreadPriority(GetCurrentThread(), org_priority);
		LeaveCriticalSection(&g_global_critical_section);
		return;
	}

	// マークする
	g_references_count = 0;
	g_references = NULL;
	DBG(_T("GC marks objects.\n"));
	gc_mark();

	DBG(_T("GC resumes suspended threads.\n"));
	// スレッドを再開できない。非常にまずい
	if (! resume_all_other_threads()) {
		monitor_exit(g_Reference_lock);
		CeSetThreadPriority(GetCurrentThread(), org_priority);
		LeaveCriticalSection(&g_global_critical_section);

		DBG(_T("FATAL: Cannot resume all other threads.\n"));
		fatal_error(_T("Cannot resume threads"));

		return;
	}
	
	// java.lang.ref.Referenceのキューイング処理を行う
	DBG(_T("GC enqueue References.\n"));
	gc_enqueue();
	
	// ファイナライズの準備をする
	// （この処理中にファイナライズ必要なオブジェクトが収集される）
	gc_prepare_finalize();

	// スイープする。
	DBG(_T("GC sweeps unused objects.\n"));

#ifdef USE_JAVA_HEAP
	g_JavaHeap->sweep();
#else
	gc_sweep();
#endif

	// ファイナライザの目を覚ます。
	// ファイナライザを同一スレッドで実行してしまうとデッドロックが発生するため、
	// 「ファイナライザスレッド」で実行する
	DBG(_T("GC will wakeup finalize thread.\n"));
	finalizer* f = get_finalizer();
	gc_start_finalizer();

	// Reference.lock を解放する
	monitor_exit(g_Reference_lock);
	DBG(_T("GC Unlocked java.lang.ref.Reference.lock\n"));

	// ガベージコレクタ実行後のパフォーマンスカウンタを取得する
	LARGE_INTEGER after_counter;
	QueryPerformanceCounter(&after_counter);
	LARGE_INTEGER freq;
	QueryPerformanceFrequency(&freq);

	if (g_loggc_filename || g_verbose_gc) {
		_TCHAR buff[128];

		LONGLONG diff = after_counter.QuadPart - before_counter.QuadPart;
		double time = (double) diff / (double) freq.QuadPart;
		_stprintf(buff,
				  _T("[FULL GC %uK -> %uK(%uK) %lf secs]\r\n"),
				  before_size / 1024,
				  g_allocated_size / 1024,
				  (g_max_heap_size - g_allocated_size) / 1024,
				  time);
		if (g_loggc_filename) {
			// -Xloggc:filename オプションが指定されている場合
			FILE* f = _tfopen(g_loggc_filename, _T("a"));
			if (f) {
				_fputts(buff, f);
				fclose(f);
			}
		}
		if (g_verbose_gc) {
			console_write(buff);
		}
	}

	// スレッドのプライオリティを元に戻す
	CeSetThreadPriority(GetCurrentThread(), org_priority);

	// GC実行フラグをクリア
	g_gc_running = false;

	// クリティカルセクションを抜ける
	LeaveCriticalSection(&g_global_critical_section);

	DBG(_T("GC finished. size="));
	DBG_UINT(g_allocated_size);
	DBG(_T("\n"));
}

/**
 * マーク処理を行う
 */
static void gc_mark() {
	unsigned int root_count = get_root_frame_count();
	for (unsigned int i = 0; i < root_count; ++i) {
		frame* root_frame = get_root_frame(i);
		if (root_frame) {
			gc_mark(root_frame);
		}
	}
}

/**
 * 指定されたframeから順番にjava_objectをmarkしていく
 */
static void gc_mark(frame* root_frame) {
	__int32* data;
	__int32* references;
	unsigned int count;
	jobject current_exception;
	if (get_root_frame_info(root_frame, &data, &references, &count, &current_exception)) {
		for (unsigned int i = 0; i < count; ++i) {
			__int32 ref = *references++;
			if (*data++ == ref					// ごみと区別するための比較
					&& ref						// nullはマークしない
					&& ! (ref & 0x80000000)) {	// returnAddress型はマークしない
				// 参照値が入っている場合
				gc_mark((jobject) ref, GC_MARKED);
			}
		}
		// 例外をマークする
		if (current_exception != NULL) {
			DBG(_T("GC marks current exception\n"));
			gc_mark(current_exception, GC_MARKED);
		}
	}
}

/**
 * 指定されたオブジェクトに、指定されたマークをつける
 */
static void gc_mark(jobject ref, int mark) {
	if (ref == NULL) {
		return;
	}
	java_object* obj = lock_address(ref);
	if ((obj->flags & GC_MARKED) != 0) {
		// 強到達である（無限ループを避ける）
		unlock_address(ref);
		return;
	} else if ((obj->flags & mark) != 0) {
		// 強到達ではないが、指定されたマークはすでについている（無限ループを避ける）
		unlock_address(ref);
		return;
	}

	// マークする
	obj->flags |= mark;

	// このオブジェクトが参照しているオブジェクトを、再帰的にマークしていく
	ClassFile* cfile = obj->class_file;
	const java_utf8* cname = cfile->this_class_name;
	jobject* refs = (jobject*) get_body_ptr(obj);
	if (is_non_primitive_array(obj)) {
		// 多次元配列またはオブジェクトの配列の場合、各要素は参照になる
		for (int i = 0; i < obj->count; ++i) {
			gc_mark(refs[i], mark);
		}
	} else if (cname[0] != '[') {
		// 非配列
		// ガベージコレクタは「参照フラグ」を基準にマーク処理を行う。
		// 「参照フラグ」は、各バイトが「参照値かどうか」を表すバイト配列
		// であり、１つの要素はオブジェクトデータの4バイトに対応している。
		// 各参照値は必ず4バイト境界に配置されるため、ガベージコレクタは
		// フィールドの型を１つ１つチェックする必要がなく、4バイト単位に
		// 処理を行うことが可能となっている。
		bool* reference_flags;
		if ((obj->flags & STATIC_DATA) != 0) {
			// staticオブジェクトの場合
			reference_flags = get_static_field_reference_flags(cfile);
		} else {
			// インスタンスオブジェクトの場合
			reference_flags = get_field_reference_flags(cfile);
		}
		int count = obj->count / 4;

		int startpos = 0;
		int type;
		if ((type = get_reference_type_flag(obj)) != 0) {
			if (type != WEAK_REFERENCE_FLAG) {
				// WeakReference以外の参照オブジェクトの場合、先頭のフィールド（referent)に
				// 特別なフラグ REFERENT_MARK をつける
				jobject referent = refs[0];	// フィールド referent
				if (referent != NULL) {
					gc_mark(referent, REFERENT_MARK);
				}
			}
			startpos++;

			// 後でキューイング処理を行うために、配列に参照オブジェクトを入れる。
			g_references_count++;
			g_references = (jobject*) realloc(g_references,
											sizeof(jobject) * g_references_count);
			g_references[g_references_count - 1] = ref;
		}

		for (int i = startpos; i < count; ++i) {
			// オブジェクト内の要素にマークをつけていく
			if (reference_flags[i]) {
				jobject ref = refs[i];
				if (ref != NULL) {
					gc_mark(ref, mark);
				}
			}
		}
	}
	unlock_address(ref);
}

/**
 * ファイナライズの準備処理をする
 */
static void gc_prepare_finalize() {
	// ファイナライザを取得し、ファイナライザをロックする
	finalizer* f = get_finalizer();
	EnterCriticalSection(f->lock);
		
	// ルートエレメントから順番に調べていく
	for (java_object* elem = g_heap_root; elem != NULL; elem = elem->next) {
		if ((elem->flags & (GC_MARKED | REFERENT_MARK | FINALIZE_MARK)) == FINALIZE_MARK) {
			// FINALIZE_MARKのみがついているオブジェクトを、
			// ファイナライザに渡す
			f->count++;
			if (f->count >= f->array_size) {
				f->array_size += 128;	// 128ずつ増やしていく
				f->target_objects = (jobject*) realloc(f->target_objects, sizeof(jobject) * f->array_size);
				if (! f->target_objects) {
					fatal_error(FATAL_ERROR_NO_MEMORY);
				}
			}
			jobject target = make_reference(elem);
			f->target_objects[f->count - 1] = target;

			// ファイナライズ処理が完了する前に回収されるのを防ぐため
			// ファイナライズ対象のオブジェクトおよび参照しているオブジェクトを
			// すべてマークしておく
			// この方法はダメ？
			gc_mark(target, GC_MARKED);
		}
	}

	// ファイナライザのロックを解除する
	LeaveCriticalSection(f->lock);
}


/**
 * スイープ処理を行う。
 */
#ifndef USE_JAVA_HEAP
static void gc_sweep() {
	// ルートエレメントから順番に調べていく
	java_object* elem = g_heap_root;
	java_object* previous = NULL;
	while (elem != NULL) {
 		java_object* next_elem = elem->next;
		bool marked = false;
		if ((elem->flags & REFERENT_MARK) != 0) {
			// 「リファレント」マークをクリアする
			elem->flags &= ~REFERENT_MARK;
			marked = true;
		}
		if ((elem->flags & GC_MARKED) != 0) {
			// GC_MARKEDをクリアする
			elem->flags &= ~GC_MARKED;
			marked = true;
		}
		if ((elem->flags & FINALIZE_MARK) != 0) {
			// この時点では FINALIZE_MARK はクリアしない（ファイナライザがクリアする）
			marked = true;
		}

		if (! marked) {
			// マークされていないオブジェクト
			// オブジェクトを解放する
			jobject ref = make_reference(elem);
			if (get_monitor(ref) != NULL) {
				// モニタを保有している場合には削除する
				delete_monitor(ref);
			}

			// リストから対象エレメントを取り除く
			if (elem == g_heap_root) {
				g_heap_root = next_elem;
			} else {
				previous->next = next_elem;
			}
			heap_free(elem);
		} else {
			// 生き残り
			previous = elem;
		}
		elem = next_elem;
	}
}
#endif

/**
 * java.lang.ref.Referenceのキューイング処理を行う
 */
static void gc_enqueue() {
	frame* frm = alloc_root_frame(NULL);
	for (int i = 0; i < g_references_count; ++i) {
		jobject o = g_references[i];
		int flags = 0;
		int reference_type = 0;

		{
			// アドレスをロックする
			java_object* reference = lock_address(o);
			jobject* body = (jobject*) get_body_ptr(reference);
			
			// 先頭の要素（referent)のマークを調べる
			java_object* referent = lock_address(*body);
			if (referent != NULL) {
				flags = referent->flags;
				reference_type = get_reference_type_flag(reference);
			}

			// アドレスをアンロックする
			unlock_address(*body);
			unlock_address(o);
		}

		if ((flags & GC_MARKED) == 0) {
			// 強到達ではなくなっている場合
			switch (reference_type) {
			case SOFT_REFERENCE_FLAG:
			case WEAK_REFERENCE_FLAG:
				{
					ClassFile* cfile = get_ClassFile(o);
					// clear()メソッドを呼び出す
					jmethodID clear_mid = get_method_id(cfile,
													    intern_utf8("clear"),
														intern_utf8("()V"));
					method_info* clear_minfo = get_method_info(cfile, clear_mid);
					ClassFile* declaring_cfile = clear_minfo->declaring_ClassFile;
					PUSH_OBJECT(frm, o);
					invoke_method(frm, o, declaring_cfile, clear_minfo);
					
					// enqueue()メソッドを呼び出す
					jmethodID enqueue_mid = get_method_id(cfile,
														  intern_utf8("enqueue"),
														  intern_utf8("()Z"));
					method_info* enqueue_minfo = get_method_info(declaring_cfile, enqueue_mid);
					declaring_cfile = enqueue_minfo->declaring_ClassFile;
					PUSH_OBJECT(frm, o);
					invoke_method(frm, o, declaring_cfile, enqueue_minfo);

					break;
				}
			case PHANTOM_REFERENCE_FLAG:
				{
					ClassFile* cfile = get_ClassFile(o);
					// enqueue()メソッドを呼び出す
					// ToDo : finalize()実行後に呼び出すように修正する
					jmethodID enqueue_mid = get_method_id(cfile,
														  intern_utf8("enqueue"),
														  intern_utf8("()Z"));
					method_info* enqueue_minfo = get_method_info(cfile, enqueue_mid);
					ClassFile* declaring_cfile = enqueue_minfo->declaring_ClassFile;
					PUSH_OBJECT(frm, o);
					invoke_method(frm, o, declaring_cfile, enqueue_minfo);

					break;
				}
			}
		}
	}
	free_root_frame(frm);
	free(g_references);
	g_references_count = 0;
}

/**
 * ファイナライズ処理を開始する
 */
static void gc_start_finalizer() {
	finalizer* f = get_finalizer();
	EnterCriticalSection(f->lock);
	if (is_idling(f)) {
		// ファイナライザの目を覚ます
		gc_wakeup_finalizer(f);
	} else {
		// ファイナライザがビジーである
		// ToDo:ファイナライザを複数スレッドで実行可能にする
		DBG(_T("GC finalizer is busy.\n"));
		if (g_verbose_gc) {
			console_write(_T("[Finalize thread is busy.]\r\n"));
		}
	}
	LeaveCriticalSection(f->lock);
}

/**
 * オブジェクトデータ本体が入っている位置のポインタをロックする。
 * この関数を呼び出した時点で、アドレス位置がロックされ、ガベージコレクション
 * 対象ではなくなる。
 * pin_objectを呼び出したのと同一回数 unpin_object 関数を呼び出すまで、
 * ロックされた状態となる。
 */
void* pin_object(jobject ref) {
	java_object* obj = lock_address(ref);
	return get_body_ptr(obj);	// データ本体のポインタを返す。
}

/**
 * 指定されたポインタをアンロックする。
 * この関数に渡すポインタは、pin_object()関数から返されたものを
 * 使用しなければならない。
 */
void unpin_object(void* ptr) {
	java_object* obj = (java_object*) ptr;
	obj--;	// オブジェクトヘッダ位置を計算
	jobject ref = make_reference(obj);
	unlock_address(ref);
}

/**
 * ファイナライザスレッドを初期化する
 */
bool init_finalizer() {
	g_finalizer = (finalizer*) malloc(sizeof(finalizer));
	if (g_finalizer == NULL) {
		fatal_error(FATAL_ERROR_NO_MEMORY);
	}
	g_finalizer->hWaiting = CreateEvent(NULL, FALSE, FALSE, NULL);
	g_finalizer->idling = true;
	g_finalizer->count = 0;
	g_finalizer->array_size = 0;	// 初期サイズは0
	g_finalizer->target_objects = (jobject*) malloc(sizeof(jobject) * g_finalizer->array_size);
	if (g_finalizer->target_objects == NULL) {
		fatal_error(FATAL_ERROR_NO_MEMORY);
	}
	// ロック用のクリティカルセクションを作成しておく
	g_finalizer->lock = (LPCRITICAL_SECTION) malloc(sizeof(CRITICAL_SECTION));
	InitializeCriticalSection(g_finalizer->lock);

	return true;
}

/**
 * ファイナライザを返す
 */
finalizer* get_finalizer() {
	return g_finalizer;
}

/**
 * ファイナライザの目を覚ます
 */
static void gc_wakeup_finalizer(finalizer* f) {
	EnterCriticalSection(f->lock);
	SetEvent(f->hWaiting);
	LeaveCriticalSection(f->lock);
}

/**
 * ファイナライズ処理を実行する
 */
void gc_run_finalizer(frame* frm, finalizer* f) {
	while (true) {
		// 「アイドリング」フラグを設定する
		EnterCriticalSection(f->lock);
		f->idling = true;
		LeaveCriticalSection(f->lock);

		// イベントがガベージコレクタによってシグナル状態にされるのを待つ
		WaitForSingleObject(f->hWaiting, INFINITE);

		// 「アイドリング」フラグをクリアする
		EnterCriticalSection(f->lock);
		f->idling = false;

		// ファイナライズ対象オブジェクトの配列をコピーする
		const unsigned int count = f->count;
		// ガベージコレクトされないようにframeに入れておく
		frame* targets = alloc_root_frame(NULL, count + 1);
		if (! targets) {
			fatal_error(FATAL_ERROR_NO_MEMORY);
		}
		for (unsigned int i = 0; i < count; ++i) {
			PUSH_OBJECT(targets, f->target_objects[i]);
		}
		// バッファの有効数を０にしておく
		f->count = 0;

		// ロックを解除する
		LeaveCriticalSection(f->lock);

		// 順番にファイナライザを実行する
		DBG(_T("GC starting finalize. target objects count="));
		DBG_INT(count);
		DBG(_T("\n"));
		if (g_verbose_gc) {
			_TCHAR msg[256];
			_stprintf(msg,
					  _T("[Starting finalize (%d objects)]\r\n"),
					  count);
			console_write(msg);
		}
		jmethodID mid = NULL;
		for (unsigned int i = 0; i < count; ++i) {
			jobject obj;
			POP_OBJECT(targets, obj);
			java_object* elem = lock_address(obj);
			
			if (! mid) {
				mid = get_method_id(elem->class_file,
			                FINALIZE_METHOD_NAME,
							VOID_NOARG_METHOD_DESCRIPTOR);
			}

			// 同じオブジェクトが２回配列に入れられる可能性もあるため、
			// ここで再度チェックする
			if ((elem->flags & FINALIZE_MARK) != 0) {
				method_info* minfo = get_method_info(elem->class_file, mid);
				ClassFile* declaring_class_file = minfo->declaring_ClassFile;

				// オブジェクトの参照をpushする
				PUSH_OBJECT(frm, obj);

				// メソッドを呼び出す
				invoke_method(frm, obj, declaring_class_file, minfo);
				
				// 例外をクリアする
				exception_clear(frm);

				// finalize()を実行したので、FINALIZE_MARKをクリアする
				elem->flags &= ~FINALIZE_MARK;
			}
			unlock_address(elem);

			// 同一優先順位の他のスレッドにタイムスライスを与える（不要？）
			// Sleep(0);
		}

		// テンポラリバッファを開放する
		free_root_frame(targets);

		DBG(_T("GC end finalize.\n"));
		if (g_verbose_gc) {
			console_write(_T("[End finalize]\r\n"));
		}
	}
}

/**
 * ファイナライザがアイドル状態かを返す
 */
static bool is_idling(finalizer* f) {
	return f->idling;
}

/**
 * 配列のコピーを行う
 */
void array_copy(jobject src, unsigned int src_start, jobject dest, unsigned int dest_start, int length) {
	// オブジェクトのアドレスをロックする
	java_object* srcobj = lock_address(src);
	java_object* destobj = lock_address(dest);

	// それぞれの開始アドレスを計算する
	unsigned int compsize = get_array_component_size(srcobj->class_file->this_class_name);
	assert(compsize == get_array_component_size(destobj->class_file->this_class_name));
	unsigned char* srcaddr = (unsigned char*) get_body_ptr(srcobj);
	srcaddr += src_start * compsize;
	unsigned char* destaddr = (unsigned char*) get_body_ptr(destobj);
	destaddr += dest_start * compsize;
	
	// メモリをコピーする。領域が重なっている場合があるため memcpy() ではなく memmove() を使用する
	memmove(destaddr, srcaddr, length * compsize);

	// オブジェクトのアドレスをアンロックする
	unlock_address(src);
	unlock_address(dest);
}

/**
 * 参照オブジェクトであることをガベージコレクタに通知する。
 * SoftReference/WeakReference/PhantomReferenceのインスタンスは、必ずこの関数を用いて
 * ガベージコレクタに登録しておく必要がある。
 * ガベージコレクタは、この関数で登録されたオブジェクトを特別扱いする。
 * typeに指定する数値は以下のとおり。
 */
void set_reference_type(jobject obj, int reference_type) {
	java_object* o = lock_address(obj);
	int flag = 0;
	switch (reference_type) {
	case SOFT_REFERENCE:
		flag = SOFT_REFERENCE_FLAG;
		break;
	
	case WEAK_REFERENCE:
		flag = WEAK_REFERENCE_FLAG;
		break;

	case PHANTOM_REFERENCE:
		flag = PHANTOM_REFERENCE_FLAG;
		break;
	}

	o->flags |= flag;

	unlock_address(obj);
}

/**
 * 参照タイプフラグ([SOFT|WEAK|PHANTOM]_REFERENCE_TYPE_FLAG)を返す。
 */
static int get_reference_type_flag(java_object* obj) {
	return obj->flags & (3 << 15);
}
/**
 * ガベージコレクタログファイル名を設定する
 */
void set_loggc_filename(const _TCHAR* filename) {
	if (filename) {
		g_loggc_filename = (_TCHAR*) malloc(sizeof(_TCHAR) * (_tcslen(filename) + 1));
		_tcscpy(g_loggc_filename, filename);
	}
}

/**
 * -verbose:gc オプションを設定する
 */
void gc_set_verbose(bool verbose) {
	g_verbose_gc = verbose;
}

/**
 * 空きメモリ量を返す
 */
unsigned int gc_get_free_memory() {
	return g_max_heap_size - g_allocated_size;
}

/**
 * ヒープ全体のサイズを返す
 */
unsigned int gc_get_total_memory() {
	return g_max_heap_size;
}

/**
 * 最大メモリ量を返す
 */
unsigned int gc_get_max_memory() {
	return g_max_heap_size;
}


#ifdef USE_JAVA_HEAP

// 現在のExact GCからConservative GCに変更するための準備


/**
 * 切り上げ
 */
#define ALIGN_UP(p, s) ((((p) % (s)) == 0) ? (p) : ((p) + ((s) - ((p) % (s)))))

/**
 * MEM_COMMITする際のアライメント
 */
#define	COMMIT_ALIGN	(64*1024)

#define BIT_0_ON	1
#define BIT_1_ON	(1<<1)
#define BIT_2_ON	(1<<2)
#define BIT_3_ON	(1<<3)
#define BIT_4_ON	(1<<4)
#define BIT_5_ON	(1<<5)
#define BIT_6_ON	(1<<6)
#define BIT_7_ON	(1<<7)
#define BIT_8_ON	(1<<8)
#define BIT_9_ON	(1<<9)
#define BIT_10_ON	(1<<10)
#define BIT_11_ON	(1<<11)
#define BIT_12_ON	(1<<12)
#define BIT_13_ON	(1<<13)
#define BIT_14_ON	(1<<14)
#define BIT_15_ON	(1<<15)
#define BIT_16_ON	(1<<16)
#define BIT_17_ON	(1<<17)
#define BIT_18_ON	(1<<18)
#define BIT_19_ON	(1<<19)
#define BIT_20_ON	(1<<20)
#define BIT_21_ON	(1<<21)
#define BIT_22_ON	(1<<22)
#define BIT_23_ON	(1<<23)
#define BIT_24_ON	(1<<24)
#define BIT_25_ON	(1<<25)
#define BIT_26_ON	(1<<26)
#define BIT_27_ON	(1<<27)
#define BIT_28_ON	(1<<28)
#define BIT_29_ON	(1<<29)
#define BIT_30_ON	(1<<30)
#define BIT_31_ON	(1<<31)

__int32 const JavaHeap::BIT_MASK[32] = {
	BIT_0_ON,
	BIT_1_ON,
	BIT_2_ON,
	BIT_3_ON,
	BIT_4_ON,
	BIT_5_ON,
	BIT_6_ON,
	BIT_7_ON,
	BIT_8_ON,
	BIT_9_ON,
	BIT_10_ON,
	BIT_11_ON,
	BIT_12_ON,
	BIT_13_ON,
	BIT_14_ON,
	BIT_15_ON,
	BIT_16_ON,
	BIT_17_ON,
	BIT_18_ON,
	BIT_19_ON,
	BIT_20_ON,
	BIT_21_ON,
	BIT_22_ON,
	BIT_23_ON,
	BIT_24_ON,
	BIT_25_ON,
	BIT_26_ON,
	BIT_27_ON,
	BIT_28_ON,
	BIT_29_ON,
	BIT_30_ON,
	BIT_31_ON,
};

/**
 * JavaHeapを作成する
 *
 * @param	最大ヒープサイズ
 */
JavaHeap::JavaHeap(size_t maxSize) {
	// ビット配列に必要なメモリ量を計算する

	maxSize = ALIGN_UP(maxSize, COMMIT_ALIGN);

	unsigned int numBits = maxSize / OBJECT_ALIGN;
	assert((numBits % 32) == 0);
	size_t bitsSize = numBits / 8;

	this->allocatedBits = (__int32*) malloc(bitsSize);
	
	// 仮想アドレス空間を予約
	this->heapBase      = (char*) VirtualAlloc(NULL, (DWORD) maxSize, MEM_RESERVE, PAGE_NOACCESS); 
	if (NULL == this->heapBase) {
		fatal_error(FATAL_ERROR_NO_MEMORY);
	}

	// メンバ変数を初期化する
	this->heapLimit		= this->heapBase + maxSize;
	this->startOfUncommitted = this->heapBase;
	this->freeObjects = NULL;
}

/**
 * JavaHeapを開放する
 */
JavaHeap::~JavaHeap() {
	char* address = this->heapBase;
	while (address < this->startOfUncommitted) {
		// コミット解除
		VirtualFree(address, COMMIT_ALIGN, MEM_DECOMMIT);
		address += COMMIT_ALIGN;
	}
	// 仮想アドレス空間を開放
	VirtualFree(this->heapBase, 0, MEM_RELEASE);

	free(this->allocatedBits);
}

/**
 * VirtualAlloc()でメモリをコミットする
 */
char* JavaHeap::commitNextBlock() {
	char* result = (char*) VirtualAlloc(this->startOfUncommitted, COMMIT_ALIGN, MEM_COMMIT, PAGE_READWRITE);
	ZeroMemory(result, COMMIT_ALIGN);
	this->startOfUncommitted += COMMIT_ALIGN;
	return result;
}

/**
 * 指定されたサイズのメモリを確保する
 *
 * @param	size	確保するサイズ。java_objectのサイズも含む
 */
java_object* JavaHeap::allocate(size_t size) {
	assert(size >= sizeof(java_object));

	// 末尾に「チェック用データ」を作成するため、1バイト加算する
	size_t allocation_size = ALIGN_UP(size + 1, OBJECT_ALIGN);
	
	bool retry = false;

RETRY:
	java_object* result = NULL;

	if (NULL == this->freeObjects) {
		java_object* freeObj = (java_object*) commitNextBlock();
		if (NULL == freeObj) {
			// 空き領域なし
			if (retry) {
				goto END;
			}
			gc();
			retry = TRUE;
			goto RETRY;
		}
		freeObj->size = COMMIT_ALIGN;
		freeObj->next = NULL;
		writeCheckData(freeObj);
		this->freeObjects = freeObj;
	}

	// 空き領域の検索を開始
	java_object* obj = this->freeObjects;
	java_object* prev_obj = NULL;

	while (true) {
		if (allocation_size <= obj->size) {
			// 空き領域発見
			if (allocation_size <= (obj->size - sizeof(java_object))) {
				// ヒープを分割する
				java_object* div_obj = (java_object*) (((char*) obj) + allocation_size);
				
				// 分割したオブジェクトのヘッダ部分が、未コミット領域をまたいでしまう場合は
				// その領域もcommitしておく（発生する？）
				if (((char*) div_obj + sizeof(java_object)) >= this->startOfUncommitted) {
					if (! commitNextBlock()) {
						// リトライする
						if (retry) {
							goto END;
						}
						gc();
						retry = true;
						goto RETRY;
					}

					// 次オブジェクトのサイズにはCOMMIT_ALIGNを加算する
					div_obj->size = obj->size - allocation_size + COMMIT_ALIGN;

				} else {
					// 次オブジェクトのサイズを設定する
					div_obj->size = obj->size - allocation_size;
					assert(div_obj->size >= sizeof(java_object));
				}
				div_obj->next = obj->next;
				obj->next = div_obj;

			} else {
				// 分割しなかった場合は allocation_size を調整する
				allocation_size = obj->size;
			}
			// フリーリストを更新する
			if (obj == this->freeObjects) {
				// 先頭を置き換える
				assert(! prev_obj);
				this->freeObjects = obj->next;
			} else {
				// リンクをつなぎかえる
				assert(prev_obj);
				prev_obj->next = obj->next;
			}
			// オブジェクトサイズを調整する
			obj->size = allocation_size;
			obj->next = NULL;
			writeCheckData(obj);

			if (((char*) obj + obj->size) > this->heapLimit) {
				// ヒープリミットを飛び越えてしまう(=maxSizeを超えた）
				break;
			}
			// 無限ループから脱出
			result = obj;
			break;
		}

		if (! obj->next) {
			// 次のブロックをコミットしてみる
			char* nextBlock = commitNextBlock();
			if (! nextBlock) {
				// もうメモリがない
				break;
			}
			if (((char*) obj + obj->size) == nextBlock) {
				// 現在位置と次ブロックが連続している場合、ループの先頭に戻る
				obj->size += COMMIT_ALIGN;
				continue;

			} else {
				// 不連続である場合には、オブジェクトのヘッダを設定した後リンクする
				java_object* newobj = (java_object*) nextBlock;
				newobj->size = COMMIT_ALIGN;
				newobj->next = NULL;
				obj->next = newobj;
				writeCheckData(obj);
			}
		}
		prev_obj = obj;
		obj = obj->next;
	}

	if (! result) {
		// ガベージコレクタ起動後、再チャレンジ
		if (retry) {
			goto END;
		}
		gc();
		retry = true;
		goto RETRY;
	}

	// allocatedBitsフラグを立てる
	setAllocatedBit(result);

	// チェック用データを書き込んでおく
	// （最低1バイトは余分に確保しているため、書き込むスペースがある）
	writeCheckData(result);

END:
	return result;
}

void JavaHeap::sweep() {
	// 先頭から順番に調べていく
	java_object* elem = (java_object*) this->heapBase;
	this->freeObjects = NULL;
	java_object* previous = NULL;
	java_object* limit = (java_object*) min(this->startOfUncommitted, this->heapLimit);
	while (elem < limit) {
 		java_object* next_elem = (java_object*)((char*) elem + elem->size);

		if (*(char*) ((char*) elem + elem->size - 1) != (char) CHECK_DATA) {
			// チェックデータが合わない。エラー
			DBG(_T("Heap check failed. Class name="));
			DBG_UTF8(elem->class_file->this_class_name);
			DBG(_T("\n"));
		}

		bool marked = false;
		if ((elem->flags & REFERENT_MARK) != 0) {
			// 「リファレント」マークをクリアする
			elem->flags &= ~REFERENT_MARK;
			marked = true;
		}
		if ((elem->flags & GC_MARKED) != 0) {
			// GC_MARKEDをクリアする
			elem->flags &= ~GC_MARKED;
			marked = true;
		}
		if ((elem->flags & FINALIZE_MARK) != 0) {
			// この時点では FINALIZE_MARK はクリアしない（ファイナライザがクリアする）
			marked = true;
		}

		if (! marked) {
			// マークされていないオブジェクトを解放する
			jobject ref = make_reference(elem);
			if (get_monitor(ref) != NULL) {
				// モニタを保有している場合には削除する
				delete_monitor(ref);
			}

			if (this->freeObjects == NULL) {
				assert(previous == NULL);
				this->freeObjects = elem;
				previous = elem;
				previous->next = NULL;

			} else if (((char*) previous + previous->size) == (char*) elem) {
				// 前の領域と結合する
				previous->size += elem->size;
				previous->next = NULL;
			} else {
				// フリーリストを連結していく
				previous->next = elem;
				previous = elem;
			}
			// ゼロクリアする
			size_t size = previous->size;
			memset(previous, 0, size);
			previous->size = size;
			writeCheckData(previous);
		}
		elem = next_elem;
	}
}

#endif