# Concurrent Rubi
contributed by <`green0413`>, <`shouchengH`>, <`SarahYuHanCheng`>, <`eesuserp`>
#### 預期進度表:
11/25 完成expr,function,(while,for)剛剛說的事
11/26、27 定義完rubi的BNF ( prefix )
## 預期目標
* 探討編譯器設計，以 DynASM 為例，解說 Rubi 運作原理，並提出 code refactoring 與效能改善機制
* 實做 concurrency 語法支援，不必跟 Ruby 相容
* 依據 prog 的程式，熟悉 Rubi 語法，著手設計類似 A09: jit-compiler 裡頭整合性的 benchmark suite，提出改善內建 benchmark suite 效能的機制，並且要能夠充分解釋行為，需要一併透過 gnuplot 自動產生效能分析圖表
* 對 Rubi 程式語言進行擴充，使其能夠支援 concurrency / parallelism。需要有程式語言的規格描述並且驗證。
* 學習 [Ruby Concurrency and Parallelism: A Practical Tutorial](https://www.toptal.com/ruby/ruby-concurrency-and-parallelism-a-practical-primer) /[github](https://github.com/eqbal/threads_and_forks.git)的語法和觀念
>> 中英文字間請以空白隔開
>> [name=課程助教][color=red]
## 產出
* [程式碼](https://github.com/SarahTree/rubi.git)
* [影片](https://www.youtube.com/watch?v=ON8kbB0FbRU)
## 資料閱讀
### 深入探索 Linux 核心架構
* 特權等級
* intel IA-32 系架構使用 4 種特權等級構成。以下圖為例，越內環能夠存取越多功能，外環則越少。
* Linux 只使用兩種模式: Kernel mode 和 User mode。兩種模式的關鍵差別在對於高於`TASK_SIZE` 的記憶體區域的存取。在 User mode 中無法存取核心空間。從 User mode 切換至 Kernel mode 必須透過 System call。
* IA-32系統上的定址空間可達 4GB( $2^{32}$ )。Kernel 分配到 1 GB ， User space process 可用空間為 3 GB。
### [POSIX Threads](https://computing.llnl.gov/tutorials/pthreads/)
* 
---
## TODO:
#### 程式碼解讀分工
- [ ] division(整數除法是錯？)
- [ ] break(done by greenyo)
- [ ] operator priority
- [ ] fork_join--pthread(create,lock)(wait)
- [ ] code refactoring(rename,struct)(wait)
- [ ] seperate .c from .dasc with IR
- [ ] different between recursion and function(shoucheng)
- [ ] how to control the depth of stack(detect and alert)(wait)
- [ ] find i32 in progs
- [ ] miller.rb line:25 why "q<30"
- [ ] 設計IR -> assignment
-> 流程控制
-> ...
- [ ] stack管理
#### Youtube
-
---
## 原 Rb 程式碼支援語法
* Rubi 依照著下圖所示的順序，來進行編譯
* 不支援：
* 函式宣告
* main 與 function 交錯
* 在空白處的程式碼隨意打'值'(123、"abc")，而提出 warning
## 執行流程
### 執行指令
`./rubi progs/fib.rb`
## 語言處理器
----
----
---
### lex
----
### parser
----
### 執行程式
---
### Division
`static void mulDivExpr()`為普通的除法，結果會是整數，可透過 `.0` or `.to_f` 將之改為浮點數的結果，但在 rubi 行不通
```
irb(main):001:0> 2/3
=> 0
irb(main):002:0> 2.0/3
=> 0.6666666666666666
irb(main):003:0> 2.to_f / 3
=> 0.6666666666666666
```
>> TODO: 實做正確的整數除法 [name=jserv]
### fork
* engine.c
```clike=
static void ffork() {
fork();
}
```
```clike=
static void *funcTable[] = {
put_i32, /* 0 */ put_str, /* 4 */ put_ln, /* 8 */ malloc, /* 12 */
xor128, /* 16 */ printf, /* 20 */ add_mem, /* 24 */ ssleep, /* 28 */
fopen, /* 32 */ fprintf, /* 36 */ fclose, /* 40 */ fgets, /* 44 */
free, /* 48 */ freeAddr, /* 52 */ ffork /* 56 */
};
```
* stdlib.h
```clike=
static std_function stdfunc[] = {
{"put_i32",1,0},
{"Array", 1, 12},
{"rand", 0, 16}, {"printf", -1, 20}, {"sleep", 1, 28},
{"fopen", 2, 32}, {"fprintf", -1, 36}, {"fclose", 1, 40}, {"fgets", 3, 44},
{"free", 1, 48}, {"freeLocal", 0, 52}, {"ffork", 0, 56}
};
```
參照`stdlib.h`裡的structure `std_function`
### operator priority
### rubi's "expr.dasc"
* 最高優先權：`{` `}` `[` `]`
* 第2優先權：`*` `/` `%`
* 第3優先權：`+` `-`
* 第4優先權：`<` `>` `!=` `==` `<=` `=>`
* 最低優先權：`and` `&` `or` `|` `xor`
### rubi's "stdlib.dasc"
or的規則
```
puts nil || 2008 //2008
puts false || 2008 //2008
puts "ruby" || 2008 //ruby
```
>>上面三行要說明什麼？
>>[color=red][name=課程助教]
### Concurrent
* ~~FORK~~ :`fork do` `Process.waitall` faster, but expensive, especially if a Copy-on-Write (CoW) is not utilized by the Ruby interpreter
* ~~Multiple threads within a single process~~ :
* shared file descriptors
* semaphores (between parent and child forked processes)
* communicate via pipes
* Thanks to the GIL, only one thread can execute at a time.
* Multithreading on RUBY(share address space and memory)
* ~~Thread pool~~ with queue(maintain consistency, avoid use of mutex) : Celluloid and its Actor model.deadlock-free
* Background Jobs : without blocking the current thread,examples include Sidekiq, Resque, Delayed Job, and Beanstalkd
@`ifStmt()`
// didn't simply 'jz =>end' to prevent address diff too large
>>上面兩行是什麼資訊?
>>[color=red][name=課程助教]
### Execute
* <parser.dasc>
* `dasm_init(&d, 1);`只設一個 maxsection，可在這裡修改為多個，以利 concurrency？
* `eval(int pos, int status)` 對每一個陳述式 expression 作運算，函數 expression() 對這些第一層結構進行剖析並產生 JIT 機器碼，eval(0, 0) 這個函數幾乎完成了 Rubi JIT compiler 的主要動作。
* 產生的機器碼形式的目的碼，放入 jit_main 這個函數指標中
* 還是不知道 funcTable[] 作用
* `compExpr()`: get argument
## Thread
## Stack Overflow protection
* Stack canaries
* between buffer & control data
* three types:
* terminator
* random
* random XOR.
* < minilua.c > `checkstack`
### Function 與 END
`parser.h`
* function 資料結構
```C
typedef struct {
int address, args, espBgn; //address-> 函式位址(EIP), args->參數個數 , espBg-> 函式內變數起始的位址(EBP)
char name[0xFF]; //函式名稱
} func_t;
struct {
func_t func[0xff]; //
int count, inside, now; // count->function總數 , inside->IN_FUNC(def的function下)、IN_GLOBAL(全域下) , now->function id
} functions;
```
>> 思考這裡該如何進行 code refactoring，比方說更好的命名，以及 struct 內部成員的調整 [name=jserv]
### DynASM
* DynASM 是一個將給定組合語言在執行時期輸出的預先處理器，再編譯(詞法分析，語法分析，語義分析及優化)前就處理，將 C/Assembler 的程式碼轉成 C 語言
* example1
>> 這案例不好，我們看不出實際機械碼長什麼樣 [name=jserv]
### if 實做
#### 指令說明
``` test ``` 比較兩個數是否相等，實做是將後面接的兩個 operands 做 AND 運算，其運算會更改到 SF, ZF, PF flag。
```jnz``` 全名叫 **Jump if not zero**，會觀察 ZF，如果 ZF 是0則跳，如果是```set```則不跳。
---
### 我們做的
由於原本程式在解析的部分參雜了C語言與dasc的code，經由minilua之後產生codegen.c，最後才經過gcc compiler，導致gcc compiler無法偵測parser、expr與stdlib是否有程式碼的語法錯誤或是其他錯誤。
所以我們要做的事情就是把dasc的code部分分開。
## 原本
## 後來
---
## Context free Grammar([BNF C版](http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf))
#### Statement
```
stat : labeled_stat
| exp_stat
| compound_stat
| selection_stat
| iteration_stat
| jump_stat
```
#### while & for
```
iteration_stat : 'while' '(' exp ')' stat
| 'do' stat 'while' '(' exp ')' ';'
| 'for' '(' exp ';' exp ';' exp ')' stat
| 'for' '(' exp ';' exp ';' ')' stat
| 'for' '(' exp ';' ';' exp ')' stat
| 'for' '(' exp ';' ';' ')' stat
| 'for' '(' ';' exp ';' exp ')' stat
| 'for' '(' ';' exp ';' ')' stat
| 'for' '(' ';' ';' exp ')' stat
| 'for' '(' ';' ';' ')' stat
```
#### if & switch
```
selection_stat : 'if' '(' exp ')' stat
| 'if' '(' exp ')' stat 'else' stat
| 'switch' '(' exp ')' stat
```
#### return
```
jump_stat : 'goto' id ';'
| 'continue' ';'
| 'break' ';'
| 'return' exp ';'
| 'return' ';'
```
#### end
```
'end'
```
#### expression
```
type_spec : 'void' | 'int' | 'string' | 'double'
direct_declarator : id
| '(' declarator ')'
| direct_declarator '[' const_exp ']'
| direct_declarator '[' ']'
| direct_declarator '(' param_type_list ')'
| direct_declarator '(' id_list ')'
| direct_declarator '(' ')'
exp : assignment_exp
| exp ',' assignment_exp
const_exp : conditional_exp
assignment_exp : conditional_exp
| assignment_operator assignment_exp
assignment_operator : '='
```
logical expression
```
logical_or_exp : logical_and_exp
| logical_or_exp 'or' logical_and_exp
logical_and_exp : inclusive_xor_exp
| logical_and_exp 'and' logical_xor_exp
logical_xor_exp : logical_or_exp
| logical_xor_exp 'xor' inclusive_or_exp
inclusive_or_exp : exclusive_or_exp
| inclusive_or_exp '|' exclusive_or_exp
exclusive_or_exp : and_exp
| exclusive_or_exp '^' and_exp
and_exp : equality_exp
| and_exp '&' equality_exp
```
condition expression
```
equality_exp : relational_exp
| equality_exp '==' relational_exp
| equality_exp '!=' relational_exp
relational_exp : shift_expression
| relational_exp '<' shift_expression
| relational_exp '>' shift_expression
| relational_exp '<=' shift_expression
| relational_exp '>=' shift_expression
```
add、sub expression
```
additive_exp : mult_exp
| additive_exp '+' mult_exp
| additive_exp '-' mult_exp
```
mul、div expression
```
mult_exp : cast_exp
| mult_exp '*' postfix_exp
| mult_exp '/' postfix_exp
| mult_exp '%' postfix_exp
```
```
argument_exp_list : assignment_exp
| argument_exp_list ',' assignment_exp
postfix_exp : primary_exp
| postfix_exp '[' exp ']'
| postfix_exp '(' argument_exp_list ')'
```
function
```
function_definition : decl_specs declarator decl_list compound_stat
| declarator decl_list compound_stat
| decl_specs declarator compound_stat
| declarator compound_stat
;
```
---
## Context free Grammar([BNF Ruby版](https://www.cse.buffalo.edu/~regan/cse305/RubyBNF.pdf))
#### Statement
```
STMT : CALL do ["|" [BLOCK_VAR] "|"] COMPSTMT end
| undef FNAME
| alias FNAME FNAME
| STMT if EXPR
| STMT while EXPR
| STMT unless EXPR
| STMT until EXPR
| "BEGIN" "{" COMPSTMT "}" //object initializer
| "END" "{" COMPSTMT "}" //object finalizer
| LHS = COMMAND [do ["|" [BLOCK_VAR] "|"] COMPSTMT end]
| EXPR
```
#### Primary
```
PRIMARY: "(" COMPSTMT ")"
| LITERAL
| VARIABLE
| PRIMARY :: IDENTIFIER
| :: IDENTIFIER
| PRIMARY "[" [ARGS] "]"
| "[" [ARGS [,]] "]"
| "{" [ARGS | ASSOCS [,]] "}"
| return ["(" [CALL_ARGS] ")"]
| yield ["(" [CALL_ARGS] ")"]
| defined? "(" ARG ")"
| FUNCTION
| FUNCTION "{" ["|" [BLOCK_VAR] "|"] COMPSTMT "}"
| if EXPR THEN COMPSTMT
{elsif EXPR THEN COMPSTMT} [else COMPSTMT] end
| unless EXPR THEN COMPSTMT [else COMPSTMT] end
| while EXPR DO COMPSTMT end
| until EXPR DO COMPSTMT end
| case COMPSTMT when WHEN_ARGS THEN COMPSTMT
{when WHEN_ARGS THEN COMPSTMT} [else COMPSTMT] end
for BLOCK_VAR in EXPR DO COMPSTMT end
| begin COMPSTMT {rescue [ARGS] DO
COMPSTMT} [else COMPSTMT] [ensure COMPSTMT] end
| class IDENTIFIER [< IDENTIFIER] COMPSTMT end
| module IDENTIFIER COMPSTMT end
| def FNAME ARGDECL COMPSTMT end
| def SINGLETON (. | ::) FNAME ARGDECL COMPSTMT end
```
#### THEN & DO
```
THEN : T | then | T then //"then" and "do" can go on next line
DO : T | do | T do
```
#### FUNCTION
```
FUNCTION : OPERATION ["(" [CALL_ARGS] ")"]
| PRIMARY.OPERATION "(" [CALL_ARGS] ")"
| PRIMARY :: OPERATION "(" [CALL_ARGS] ")"
| PRIMARY.OPERATION
| PRIMARY :: OPERATION
| super "(" [CALL_ARGS] ")"
| super
```
#### CALL_ARGS
```
CALL_ARGS : ARGS
| ARGS [, ASSOCS] [, * ARG] [, & ARG]
| ASSOCS [, * ARG] [, & ARG]
| * ARG [, & ARG] | & ARG
| COMMAND
```
#### PRIMARY
```
PRIMARY: "(" COMPSTMT ")"
| LITERAL
| VARIABLE
| PRIMARY :: IDENTIFIER
| :: IDENTIFIER
| PRIMARY "[" [ARGS] "]"
| "[" [ARGS [,]] "]"
| "{" [ARGS | ASSOCS [,]] "}"
| return ["(" [CALL_ARGS] ")"]
| yield ["(" [CALL_ARGS] ")"]
| defined? "(" ARG ")"
| FUNCTION
| FUNCTION "{" ["|" [BLOCK_VAR] "|"] COMPSTMT "}"
| if EXPR THEN
COMPSTMT
{elsif EXPR THEN
COMPSTMT}
[else
COMPSTMT]
end
| unless EXPR THEN
COMPSTMT
[else
COMPSTMT]
end
| while EXPR DO COMPSTMT end
| until EXPR DO COMPSTMT end
| case COMPSTMT
when WHEN_ARGS THEN COMPSTMT
{when WHEN_ARGS THEN COMPSTMT}
[else
COMPSTMT]
end
| for BLOCK_VAR in EXPR DO
COMPSTMT
end
| begin
COMPSTMT
{rescue [ARGS] DO
COMPSTMT}
[else
COMPSTMT]
[ensure
COMPSTMT]
end
| class IDENTIFIER [< IDENTIFIER]
COMPSTMT
end
| module IDENTIFIER
COMPSTMT
end
| def FNAME ARGDECL
COMPSTMT
end
| def SINGLETON (. | ::) FNAME ARGDECL
COMPSTMT
end
```
---
## 問題
---
* compile 32bit and fails : `features.h:374:25: fatal error: sys/cdefs.h: No such file o+r directory`
* <lex.o>was built for i386
- [ ] install 32 bit c library: `sudo apt-get install gcc-multilib` `sudo apt-get install g++-multilib`
---
## 參考資料
* [x86 instruction listings](https://en.wikipedia.org/wiki/X86_instruction_listings)
* [stack 說明](http://godleon.blogspot.tw/2008/02/indirect-addressing-indirect-address.html)
* [陳鍾誠介紹rubi](http://ccc.nqu.edu.tw/wd.html#pmag201511/home.wd)
* [Dynasm函式介紹](http://corsix.github.io/dynasm-doc/reference.html#dasm_init)
* [Hello, jit world!](http://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html)
* [Calling convention for system calls](http://www.cs.virginia.edu/~evans/cs216/guides/x86.html#calling)
* [ruby](http://rubylearning.com/satishtalim/numbers_in_ruby.html)
* [Intermediate Representations (IR)](http://cs.lmu.edu/~ray/notes/ir/)
* [組合語言介紹](http://120.101.8.4/lyhsu/database/grade/%E7%8E%8B%E4%BF%A1%E4%BB%81/%E7%B5%84%E5%90%88%E8%AA%9E%E8%A8%80%E8%AA%B2%E6%9C%ACCHAP05.pdf)
* [IR](http://www.programcreek.com/2011/02/how-compiler-works/)
* http://docs.huihoo.com/ruby/ruby-man-1.4/yacc.html
Sign in with Wallet
Connect another wallet