/*
 *	clipalca.c
 *
 *	alloca()、GNU Cの組み込み関数互換機能
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2012-2014 Naoyuki Sawa
 *
 *	* Tue Oct 16 11:50:08 JST 2012 Naoyuki Sawa
 *	- 1st リリース。
 *	- 宣言は、include/alloca.h にあります。
 *	* Sat May 31 14:34:06 JST 2014 Naoyuki Sawa
 *	- alloca_hook_procのバグを修正しました。
 *	  allocaを呼び出した関数が戻り値を返すとき、フック関数であるalloca_hook_procが戻り値を破壊していました。
 *	  今回の修正で、allocaを呼び出した関数が返した戻り値をallocaが破壊せず、正しく中継するようになりました。
 */
#include "clip.h"

/****************************************************************************
 *	alloca
 ****************************************************************************/

/* alloca()で確保したメモリを、チェインして保持するための構造体 */
typedef struct _ALLOCA_INFO {
	LIST_ENTRY list_entry;	/* チェイン用 */
	void* return_address;	/* フック戻りアドレス */
	/* この後に、確保したメモリが続きます */
} ALLOCA_INFO;

/* データで初期化しておくことによって、初回にInitializeListHead()で初期化する必要が無くなる。 */
static LIST_ENTRY alloca_info_head = { /*Flink*/&alloca_info_head, /*Blink*/&alloca_info_head };

/*--------------------------------------------------------------------------*/

/*static*/ void alloca_hook_proc();
asm("
		.code
		.align		1
alloca_hook_proc:
		pushn		%r0
		call.d		alloca_hook_proc_sub	;// 管理構造体チェインの先頭の、メモリを開放します。
		ld.w		%r0, %r10		;// %r0  := allocaを呼び出した関数の戻り値		*delay*
		ld.w		%r9, %r10		;// %r9  := 戻りアドレス
		ld.w		%r10, %r0		;// %r10 := allocaを呼び出した関数の戻り値
		popn		%r0
		jp		%r9			;// 管理構造体チェインの先頭の、戻りアドレスへ戻ります。
");

/*--------------------------------------------------------------------------*/

static void* __attribute__((unused)) alloca_hook_proc_sub() { /* asmブロックから参照 */
	ALLOCA_INFO* p_alloca_info;
	void* return_address;
ENTER_CS;
	/* 管理構造体チェインの取り外しを、アトミックに行うため、割り込み禁止 */
	/* チェインの先頭の管理構造体を取り外します。 */
	p_alloca_info = CONTAINING_RECORD(
		RemoveTailList(&alloca_info_head),
		ALLOCA_INFO, list_entry);
	/* alloca()を呼び出した関数の、戻りアドレスのフックを解除する処理を行ってはいけません。
	 * pseudo_alloca()の中でフックした(=戻りアドレスを書き換えた)のは、スタック上の戻りアドレスだからです。
	 * ここへ来たということは、スタック上の戻りアドレスが読み出されたということであり、
	 * スタック上の戻りアドレスの位置は、もうスタックフレーム外になっているからです。
	 */
LEAVE_CS;
	/* 管理構造体から、戻りアドレスを取得します。 */
	return_address = p_alloca_info->return_address;
	/* 管理構造体とメモリを、まとめて開放します。 */
	free(p_alloca_info);
	/* alloca_hook_procに、戻りアドレスを返します。 */
	return return_address;
}

/*--------------------------------------------------------------------------*/

void* pseudo_alloca(size_t size) {
	ALLOCA_INFO* p_alloca_info;
	void** return_address_p;
	/* 管理構造体とメモリを、まとめて確保します。 */
	p_alloca_info = malloc(sizeof(ALLOCA_INFO) + size);
	if(p_alloca_info == NULL) DIE(); /* メモリ不足 */
	/* alloca()を呼び出した関数の、戻りアドレスが格納されているアドレスを取得します。 */
	return_address_p = get_return_address_p(1);
	/* 管理構造体に、alloca()を呼び出した関数の戻りアドレスを格納します。 */
	p_alloca_info->return_address = *return_address_p;
ENTER_CS;
	/* 管理構造体チェインの追加と、戻りアドレスのフックを、アトミックに行うため、割り込み禁止 */
	/* alloca()を呼び出した関数の、戻りアドレスをフックします。 */
	*return_address_p = alloca_hook_proc;
	/* 管理構造体を、チェインの末尾に追加します。 */
	InsertTailList(&alloca_info_head, &p_alloca_info->list_entry);
LEAVE_CS;
	/* 管理構造体の後ろに確保した、メモリを返します。 */
	return p_alloca_info + 1;
}

/****************************************************************************
 *	GNU Cの組み込み関数互換機能
 ****************************************************************************/

//	* Tue Oct 16 12:42:11 JST 2012 Naoyuki Sawa
//	- gcc33が生成するアセンブラコードの、エピローグコードは、以下のいずれかです。
//	  ① add %sp,imm10; popn %rd; ret[.d]
//	  ② add %sp,imm10;           ret[.d]
//	  ③                popn %rd; ret[.d]
//	  ④                          ret[.d]
//	  実際にはgcc33は、ret.dを生成しませんが、一応ret.dでも動作するように対応しました。
//	- 本関数は、gccの上記の特性を利用して、呼び出し元関数のリターンアドレスを探します。
//	  上記のパターンに一致しない、アセンブラ関数から、呼び出すことはできません。
//	  検索するコールスタックの途中に、アセンブラ関数が含まれていてもいけません。
//
//	＜例:OK＞
//		void c_func_1() { c_func_2(); }
//		void c_func_2() { c_func_3(); }
//		void c_func_3() { __builtin_return_address(1); } // c_func_2()の戻りアドレスを取得する
//	＜例:OK＞
//		asm("asm_func_1: call c_func_2; ret;"); //検索対象にならないので大丈夫
//		void c_func_2() { c_func_3(); }
//		void c_func_3() { __builtin_return_address(1); } // c_func_2()の戻りアドレスを取得する
//	＜例:NG＞
//		void c_func_1() { asm_func_2(); }
//		asm("asm_func_2: call c_func_3; ret;"); //検索対象になる
//		void c_func_3() { __builtin_return_address(1); } // asm_func_2()の戻りアドレスを取得することはできない!!
//	＜例:NG＞
//		void c_func_1() { c_func_2(); }
//		void c_func_2() { asm_func3(); } //検索対象だが、それ以前の問題で、ここまで検索が到達しないだろう
//		asm("asm_func_3: ld.w %r12, 1; call get_return_address; ret;"); // c_func_2()の戻りアドレスを取得することはできない!!
//
//	※上記は説明のために__builtin_return_address(1)を使用しましたが、実際には引数0で呼び出すことがほとんどでしょう。
//	  通常は、アセンブラ関数から直接呼び出すことができないこと意外は、問題が生じるケースを気にする必要はありません。

void*  get_frame_address   (unsigned int level);
void*  get_return_address  (unsigned int level);
void** get_return_address_p(unsigned int level);
asm("
		.code
		.align		1
		.global		get_frame_address
		.global		get_return_address
		.global		get_return_address_p
;//void*  get_frame_address   (unsigned int level)
get_frame_address:
		call	get_return_address_p			;// %r10 := get_return_address_p(level)
		ret.d
		add	%r10, 4					;// %r10 := return_address_p + 4		*delay*
;//void*  get_return_address  (unsigned int level)
get_return_address:
		call.d	get_return_address_p			;// %r10 := get_return_address_p(level + 1)
		 add	%r12, 1					;// %r12 :=                      level + 1	*delay*
		ld.w	%r10, [%r10]				;// %r10 := return_address
		ret
;//void** get_return_address_p(unsigned int level)
get_return_address_p:
		ld.w		%r10, %sp			;// %r10 := get_return_address_p()のスタックフレーム
		;//--- __builtin_return_address()の引数levelで指定された回数、さらに呼び出し元関数をたどるループ ---
get_return_address_p_LOOP_1:
		ld.w		%r13, [%r10]+			;// %r13 := get_return_address_p()の戻りアドレス, %r10 := 呼び出し元関数のスタックフレーム
		;//--- 呼び出し元関数の末尾にある、【ret[.d]】を探すループ ---
get_return_address_p_LOOP_2:
		ld.uh		%r14, [%r13]+			;// %r14 := 呼び出し元関数の命令, %r13 := 呼び出し元関数の%pc
		;// 【ret[.d]】のコード：
		;// ┌─-固定-─┐　┌──固定──┐
		;// ０００００１１ｄ０１００００００
		xand		%r14, %r14, 0xFEFF		;// if(%r14 != 【ret[.d]】) {
		xcmp		%r14,       0x0640		;//   goto get_return_address_p_LOOP_2
		jrne		get_return_address_p_LOOP_2	;// }
		;//--- 【ret[.d]】の直前に、【popn %rd】があれば、スタックフレームを調整する ---
		;// 【popn %rd】のコード：
		;// ┌────固定────┐┌ｒｄ┐
		;// ００００００１００１００・・・・
		sub		%r13, 4				;// %r13 := 【ret[.d]】の直前の命令アドレス
		ld.uh		%r14, [%r13]			;// %r14 := 【ret[.d]】の直前の命令
		xsub		%r15, %r14, 0x0240		;// %r15 := (%r14 == 【popn %rd】) であった場合のrd
		xcmp		%r15,       0x000F
		jrugt		6				;// if(%r14 == 【popn %rd】) {
		 add		%r15, 1				;//   %r15 :=                                     (rd + 1)
		 sll		%r15, 2				;//   %r15 :=                                    ((rd + 1) * 4)
		 add		%r10, %r15			;//   %r10 := 呼び出し元関数のスタックフレーム + ((rd + 1) * 4)
		 sub		%r13, 2				;//   %r13 := 【popn %rd】の直前の命令アドレス
		 ld.uh		%r14, [%r13]			;//   %r14 := 【popn %rd】の直前の命令
		;//						;// }
		;//--- 【ret[.d]】又は【popn %rd】の直前に、【add %sp, imm10】があれば、スタックフレームを調整する ---
		;// 【add %sp, imm10】のコード：
		;// ┌─固定─┐┌─-ｉｍｍ１０-─┐
		;// １０００００・・・・・・・・・・
		xsub		%r15, %r14, 0x8000		;// %r15 := (%r14 == 【add %sp, imm10】) であった場合のimm10
		xcmp		%r15,       0x03FF
		jrugt		3				;// if(%r14 == 【add %sp, imm10】) {
		 sll		%r15, 2				;//   %r15 :=                                    (imm10 * 4)
		 add		%r10, %r15			;//   %r10 := 呼び出し元関数のスタックフレーム + (imm10 * 4)
		;//						;// }
		;//--- __builtin_return_address()の引数levelで指定された回数、さらに呼び出し元関数をたどるループ ---
		sub		%r12, 1				;// if(--level >= 0)
		jruge		get_return_address_p_LOOP_1	;//   goto get_return_address_p_LOOP_1
		ret
");

