Concurrent Rubi

# 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 種特權等級構成。以下圖為例，越內環能夠存取越多功能，外環則越少。![](https://i.imgur.com/XYfauW2.png) * 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/) * ![](https://i.imgur.com/MMxoYTo.png) --- ## 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 依照著下圖所示的順序，來進行編譯 ![](https://i.imgur.com/sq8H6Wk.png) * 不支援： * 函式宣告 * main 與 function 交錯 * 在空白處的程式碼隨意打'值'(123、"abc")，而提出 warning ## 執行流程 ### 執行指令 `./rubi progs/fib.rb` ![](https://i.imgur.com/k785Xc7.png) ## 語言處理器 ![](https://i.imgur.com/pDnps9s.png) ---- ![](https://i.imgur.com/aeMm08P.jpg) ---- ![](https://i.imgur.com/ZfAjwx5.png) --- ### lex ![](https://i.imgur.com/JT8TgOO.png) ---- ### parser ![](https://i.imgur.com/j4fUURc.png) ![](https://i.imgur.com/UuD0AUf.png) ---- ### 執行程式 ![](https://i.imgur.com/hwnFSnE.png) --- ### 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 ![](http://rubylearning.com/images/operators.jpg) ### rubi's "expr.dasc" * 最高優先權：`{` `}` `[` `]` * 第2優先權：`*` `/` `%` * 第3優先權：`+` `-` * 第4優先權：`<` `>` `!=` `==` `<=` `=>` * 最低優先權：`and` `&` `or` `|` `xor` ![](https://i.imgur.com/8dMVgRU.png) ### rubi's "stdlib.dasc" ![](https://i.imgur.com/yFMF3ti.png) 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 ![](https://i.imgur.com/ztKMfAx.png) ## 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 ![](https://i.imgur.com/it6XbY6.png) >> 這案例不好，我們看不出實際機械碼長什麼樣 [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部分分開。 ## 原本 ![](https://i.imgur.com/yELejzX.png) ## 後來 ![](https://i.imgur.com/nCROzM4.png) --- ## 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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.