[コンパイラ]初めてのコンパイラ作成

GCCの構文解析は、再帰下降構文解析法(recursive descent parsing)を使っている

下記のシンプルなアセンブリもコンパイラと言える。

.intel_syntax noprefix
.globl main

main:
        mov rax, 42
        ret

### Intel記法とAT&T記法

mov rbp, rsp // intel
mov %rsp, %rbp // AT&T ...結果レジスタが第二引数にくる

mov rax, 8 // intel
mov $8, %rax // AT&T ...数字には$をつける

mov [rbp + rcx * 4 - 8], rax // intel
mov %rax, -8(rbp, rcx, 4) // AT&T 

### コンパイラの作成

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv){
	if(argc != 2){
		fprintf(stderr, "引数の個数が正しくありません\n");
		return 1;
	}

	printf(".intel_syntax noprefix\n");
	printf(".global main\n");
	printf("main:\n");
	printf("	mov rax, %d\n", atoi(argv[1]));
	printf("	ret\n");
	return 0;
}
$ gcc -o 9cc 9cc.c
$ ./9cc 345 > tmp.s
$  cat tmp.s
.intel_syntax noprefix
.global main
main:
	mov rax, 345
	ret

$ gcc -o tmp tmp.s
$ ./tmp
$ echo $?
89

あれ? 345が89になるな。何故だ? あ、0〜255の範囲でないと行けないからですな。

[コンパイラ]アセンブリ

### 関数のアセンブリ変換
呼び出した関数が終了した後に、元々実行していたアドレス(リターンアドレス)に戻ってくる必要がある
リターンアドレスはメモリ上のスタックに保存される
スタックは、スタックの一番上のアドレスを保持する1つの変数のみを使って実装できる
スタックトップを保持している記憶領域をスタックポインタという

c

#include <stdio.h>

int plus(int x, int y){
	return x + y;
}

int main(){
	return plus(3, 4);
}

アセンブリ

.intel_syntax noprefix
.globl plus, main

plus:
		add rsi, rdi
		mov rax, rsi
		ret

main:
        mov rdi, 3
        mov rsi, 4
        call plus
        ret

第一引数はRDIレジスタ、第二引数はRSIレジスタに入れる約束になっている
callは関数を呼び出す。具体的にはアドレスをスタックにプッシュし、ジャンプ
addはrsiレジスタに上書きされて保存される
返り値はRAXに入れることになっている
retでスタックからアドレスを1つポップ

CPUはメモリを読み書きすることでプログラムの実行を進めていく

[コンパイラ]CPUの命令とアセンブリ

コンパイラは、構文解析、中間パス、コード生成というステージがある
コンパイラが動作するマシンのことを「ホスト」、コンパイラが出力したコードが動作するマシンのことを「ターゲット」という
ホストとターゲットが異なるコンパイラをクロスコンパイラという

### CPU
現在実行中の命令アドレスをCPU内部に保持していて、そのアドレスから命令を読み出して、そこに書かれていることを行い、そして次の命令を読み出して実行する
現在実行中のアドレスのことをプログラムカウンタ(PC)やインストラクションポインタ(IP)という
cpuが実行するプログラム形式そのもののことを機械語(machine code)という
CPUの分岐命令(branch instruction)を使うと、次の命令以外の任意のアドレスに設定することができる(ジャンプ、分岐) eg.if文やループ文など
プログラムカウンタ以外にも少数のデータ保存領域を持っており、レジスタと呼ぶ
2つのレジスタの値を使って何らかの演算を行い、結果をレジスタに書き戻すというフォーマットになっている
命令を命令セットアーキテクチャ(instruction set architecture)という
x86-64命令セットはAMD64、Intel64, x64などと呼ばれることがある
-> awsでインスタンスを作ろうとするとき “64-bit x86″と表示されるが、このx86は命令セットのこと

### アセンブラ
アセンブリは機械語にほぼそのまま1対1で対応する言語
$ objdump -d -M intel /bin/ls

/bin/ls: file format elf64-x86-64

Disassembly of section .init:

0000000000003758 <_init@@Base>:
3758: 48 83 ec 08 sub rsp,0x8
375c: 48 8b 05 7d c8 21 00 mov rax,QWORD PTR [rip+0x21c87d] # 21ffe0 <__gmon_start__>
3763: 48 85 c0 test rax,rax
3766: 74 02 je 376a <_init@@Base+0x12>
3768: ff d0 call rax
376a: 48 83 c4 08 add rsp,0x8
376e: c3 ret

——–
3758: 48 83 ec 08 sub rsp,0x8
3758はメモリのアドレス
48 83 ec 08は命令の機械語
sub rsp,0x8はアッセンブリ rspから8を引く

### Cとアセンブラ

#include <stdio.h>

int main(int argc, char** argv[]){

	return 42; // 終了コード

}

$ gcc -o test test.c
$ ./test
$ echo $?  // 終了コードは$?にセットされる
42

### アセンブリファイルの作成
アセンブリファイルの拡張子は.s

.intel_syntax noprefix
.globl main
main:
	mov rax, 42
	ret

プログラミング勉強の良いところは、後からどんどん繋がってくることだな

FPGA

FPGAとは?
-> Field Programmable Gate Arrayの略
-> 現場で書き換え可能な論理回路の多数配列:ハードウェア言語で修正が出来るデバイス

ハードウェア言語とは一般的に半導体の回路記述をする際に用いる言語
論理回路とはデジタル信号を扱う回路のこと
論理合成と配置配線はハードウェア言語で記述された回路をFPGAに書き込む為のデータに変換すること

CPLDは汎用ロジックIC数百個~数千個分の回路を内部で構成できる
LSIを超える規模の回路を簡単に構成できる
PLGの一種

【組み込み系の開発工程】
要求分析→要件定義→基本設計・詳細設計→RTL設計(Verilog、VHDLなどを用いてコーディング) →論理合成→動作シミュレーション→配置配線

ビッグデータのデータ処理やディープラーニング向けの並列計算等にFPGAやASICが使われることもある

[CPU]命令セット

– 命令の集まり
– コンピュータで使われる命令の表現形式と各命令の動作を定めたもの
命令 = 操作オペランド + 対象
L ソースオペランド
L デスティネーションオペランド
オペランドとなるものはデータレジスタ、メモリ語、プログラムカウンタ、その他レジスタ

### 命令の表現形式
(1)R型: op(5:操作コード) rs(5:オペランドレジスタ) rt(5) rd(5) aux(11:実行細則)
(2)I型: op(6) rs(5) rt(5) imm/dpl(16:immediate displacement)
(3)A型: op(6) addr(26:メモリアドレス)
命令語が32ビット、命令セットの大きさが64、レジスタ数が32

アセンブリ言語表現
R型:add r2 r3 r1 0
I型:subi r2 r1 14
A型:j 1048581

算術論理演算命令(R型(整数)、I型、 R型(浮動小数点))
加算:add, addi, fadd
減算:sub, subi, fsub
乗算:mul, muli, fmul
除算:div, divi, fdiv
除余:rem, remi
絶対値:abs, , fabs
算術左シフト: sla, ,
算術右シフト: sra, ,
論理積:and, andi
論理和:or, ori
否定:not,
NOR:nor, nori
NAND:nand, nandi
排他的論理和:xor, xori
EQUIV:eq, eqi
論理左シフト:sll
論理右シフト:srl

命令の動作はオペランドがデコーダでALUに行き、レジスタのアドレスを取得して計算する

シリコンチップで集積回路を作るには、シリコン上の構造物の配置を図面に落とす必要がある
基本素子を作り、それを配置していく

ICチップを作るには、まず原材料としてシリコンウェハー(Si)が必要
ピラニア溶液(H2SO4:H2O2)、RCA1(H2O:NH3:H2O2)、RCA2(H2O:HCL:H2O2)で洗浄してHF液につけて自然酸化膜を作る

なるほど、CPUの設計って回路設計だけでなく、物理、化学、光学、電気学などかなり幅広い知識を応用してんだな。

[C言語]カーネル

Unix系では新しいプロセスはfork()により生成されexec()系の関数により新たなプログラムに書き換わる
プログラムを実行する為のライブラリ関数としてexeclp()やexecvp()などがある
execveシステムコールが発行されるとカーネルの仕事となる
– 実行ファイルを読み込み、仮想メモリ上にマッピングする
– argc/argv[]、BSSの初期化、環境変数の引き渡しなどを行う
– 実行ファイル上のエントリポイントから実行を開始する

※カーネルを読み込むには5年程度の技術と時間がかかる
カーネルの大部分はC言語で書かれているが、CPU固有の処理部分はアセンブラ言語で書かれている

## カーネルのディレクトリ
Documentation ドキュメント
arch アーキテクチャ依存
block ブロック入出力層
crypto 暗号化
drivers デバイス・ドライバ
firmware ファームウェア
fs VFS(Virtual File System)とファイル・システム
include カーネル用のヘッダ・ファイル
init 起動と初期化(initialization)
ipc プロセス間通信(interprocess communication)
kernel カーネルの中心部分
lib ヘルパ
mm メモリ管理(memory management)
net ネットワーク
samples サンプルコード
scripts カーネルのコンパイルに必要なスクリプト
security Lnux Security Module
sound サウンド・サブシステム
tools カーネル開発用のツール
usr 起動直後にユーザ空間で実行されるプログラム(initramfs)
virt 仮想化インフラ

C言語ではcrt(C RunTime startup)というアセンブリで記述されたプログラムが一番最初に実行される
OSの開発ではこのcrtを環境に合わせて用意する

[C言語]メモリリーク

メモリリークとは、動的に割当てたメモリ領域を解放し忘れることで次第にメモリ資源を食い潰していき、いずれプログラムやシステムに異常をきたすという問題。
c言語のメモリ解放はmalloc()やfree()が使われてきた。
malloc()で割当てて、free()で解放する。
メモリの解放を忘れていると、プログラムが終了するまでメモリ資源を無駄に占有し続ける。

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

int maikFile(char *fileName, int size){
	FILE *fp;
	char *pData;

	// メモリ解放
	pData = malloc(size);
	if(pData == NULL){
		return 1;
	}

	fp = fopen(fileName, "wb");
	if(fp == NULL){
		return 1;
	}

	memset(pData, 0x20, size);
	fwrite(pData, size, 1, fp);
	fclose(fp);

	free(pData);
	return 0;
}


int main(int argc, char** argv[]){

	return 0;

}

ファイルシステムオープンの失敗を繰り返すと、メモリは解放されずにreturn1となるのでメモリリークになる。

[C言語]ファイヤーウォール

ファイヤーウォールとはパケットの制御または破棄を行うソフトウェアである

特定のパケットとは、
– 特定のポートにアクセスするパケット
– 特定のIPアドレスからのパケット
– 特定の内容をもつパケット
などがある。

ファイヤーウォールを作成するには
– パケットの中身を見る
– パケットの転送可否を行う

### パケットキャプチャ
パケットの中身を見る
TCPやUDPはもとより、IPやEthernetレベルのデータリンク情報も解析する
一般的に tcpdump や wireshark などがある

#include <stdio.h>
#include <net/if.h> // ネットワークインターフェイス構造体 PF_PACKET
#include <net/ethernet.h> // ETH_P_ALL

void analyzePacket(u_char *buf){
	printEtherHeader(buf);
}

void printEtherHeader(u_char *buf){
	struct ether_header *eth;
	eth = (struct ether_header *)buf;
	printf("Dst MAC addr :%17s\n", mac_ntoa(eth->ether_dhost));
	printf("Src MAC addr :%17s\n", mac_ntoa(eth->ether_shost));
	printf("Ethernet Type :0x%04x\n", ntohs(ether_type));
}

char *mac_ntoa(u_char *d){
	static char str[18];
	sprintf(str,"%02x:%02x:%02x:%02x:%02x:%02x",d[0],d[1],d[2],d[3],d[4],d[5]);
	return str;
}

int main(int argc, char** argv[]){

	int soc;
	u_char buf[65535]; // u_charはunsigned char
	soc = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
	while(1){
		read(soc,buf,sizeof(buf));
		analyzePacket(buf);
	}
	return 0;

}

int socket(int domain, int type, int protocol);
PF_PACKETを指定すると,データリンク層やネットワーク層の生データを扱える
通常はSOCK_STREAM(TCPの場合)やSOCK_DGRAM(UDPの場合)
ETHERNETとは、TCP/IPプロトコルのネットワークインターフェース層に対応する有線の規格

宛先MAC address(固有識別番号)、送信元MAC address, type, ip以降
ビッグエンディアン

[C言語]ICMP

ICMPとはInternet Control Message Protocol
Internet Protocolのデータグラム処理における誤りの通知や通信に関する情報の通知などのために使用される

#include <stdio.h>

#include <sys/socket.h> // Internet Protocol family
#include <netinet/in.h> // Internet Protocol family

#include <netinet/ip.h>  // IPヘッダ構造体
#include <netinet/ip_icmp.h> // ICMPヘッダ

unsigned short checksum(unsigned short *buf, int bufsz){

	unsigned long sum = 0;

	while(bufsz > 1){
		sum += *buf;
		buf++;
		bufsz -= 2;
	}

	if(bufsz == 1){
		sum += *(unsigned char *)buf;
	}

	sum = (sum & 0xffff) + (sum >> 16);
	sum = (sum & 0xffff) + (sum >> 16);

	return ~sum;
}

int main(int argc, char** argv[]){

	int sock;
	struct icmphdr hdr;
	struct sockaddr_in addr;
	int n;

	char buf[2000];
	struct icmphdr *icmphdrptr;
	struct iphdr *iphdrptr;

	if(argc != 2){
		printf("usage : %s IPADDR\n", argv[0]);
		return 1;
	}

	addr.sin_family = AF_INET;
	addr.sin_addr.s_addr = inet_addr(argv[1]);

	sock = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);
	if(sock < 0){
		perror("socket");
		return 1;
	}

	memset(&hdr, 0, sizeof(hdr));

	hdr.type = ICMP_ECHO;
	hdr.code = 0;
	hdr.checksum = 0;
	hdr.un.echo.id = 0;
	hdr.un.echo.sequence = 0;

	hdr.checksum = chechsum((unsigned short *)&hdr, sizeof(hdr));

	n = sendto(sock, (char *)&hdr, sizeof(hdr), 0, (struct sockaddr *)&addr, sizeof(addr));
	if (n < 1){
		perror("sendto");
	}

	memset(buf, 0, sizeof(buf));

	n = recv(sock, buf, sizeof(buf), 0);
	if(n < 1){
		perror("recv");
	}

	iphdrptr = (struct iphdr *) buf;

	icmphdrptr = (struct icmphdr *)(buf + (iphdrptr->ihl * 4));

	if(icmphdrptr->type == ICMP_ECHOREPLY){
		printf("received ICMP ECHO REPLY\n");
	} else {
		printf("received ICMP %d\n", icmphdrptr->type);
	}

	close(sock);
	

	return 0;

}

[C言語]UDP

UDPはデータが宛先に届いたかどうかを関知しない為、到着を保証しない
複数の相手に同時にデータを送信できる、TCPは1対1のユニキャストのみ
TCPよりリアルタイム性が高い
用途は映像、音楽のストリーミング、Voice Over IPなど

### UDP受信
– ソケットを作る
– bindするIPアドレスとポートを設定
– ソケットに名前をつける
– データを受け取る

#include <stdio.h>
#include <sys/types.h> // typedef シンボルおよび構造体のコレクション
#include <sys/socket.h> // Internet Protocol family
#include <netinet/in.h> // Internet Protocol family

int main(int argc, char** argv){

	int sock;
	struct sockaddr_in addr; // sockaddr_inはIPアドレスやポート番号を保持する為の構造体

	char buf[2048];

	sock = socket(AF_INET, SOCK_DGRAM, 0); // ソケットの作成

	addr.sin_family = AF_INET; // アドレスファミリ
	addr.sin_port = htons(12345); // ポート番号、 htonsはネットワークバイトオーダに変換
	addr.sin_addr.s_addr = INADDR_ANY; // IPアドレス

	bind(sock, (struct sockaddr *)&addr, sizeof(addr)); // sockはソケットとアドレスの結合

	memset(buf, 0, sizeof(buf)); // バイトメモリブロックのセット
	recv(sock, buf, sizeof(buf), 0); // ソケットからメッセージを受け取る

	printf("%s\n", buf);

	close(sock);

	return 0;

}

### UDP送信
– ソケットを作る
– 宛先を指定して送信

#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>

int main(){
	
	int sock;
	struct sockaddr_in addr;

	sock = socket(AF_INET, SOCK_DGRAM, 0);

	addr.sin_family = AF_INET;
	addr.sin_port = htons(12345);
	addr.sin_addr.s_addr = inet_addr("127.0.0.1");

	sendto(sock, "HELLO", 5, 0, (struct sockaddr *)&addr, sizeof(addr));

	close(sock);

	return 0;
}

TCP/IPはデータを切れ目のないストリームとして扱う、ストリームのイメージは固定された通信路
一方、UDPはデータグラム(塊)として扱う

TCPとUDPについてわかってきました。