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 /github的語法和觀念

中英文字間請以空白隔開
課程助教

產出

• 程式碼
• 影片

資料閱讀

深入探索 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

---

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: 實做正確的整數除法 jserv

fork

• engine.c

static void ffork() { 
    fork();
}

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

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

上面三行要說明什麼？
課程助教

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

上面兩行是什麼資訊?
課程助教

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 資料結構

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 內部成員的調整 jserv

DynASM

• DynASM 是一個將給定組合語言在執行時期輸出的預先處理器，再編譯(詞法分析，語法分析，語義分析及優化)前就處理，將 C/Assembler 的程式碼轉成 C 語言

• example1
  

  

這案例不好，我們看不出實際機械碼長什麼樣 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版)

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版)

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
• stack 說明
• 陳鍾誠介紹rubi
• Dynasm函式介紹
• Hello, jit world!
• Calling convention for system calls
• ruby
• Intermediate Representations (IR)
• 組合語言介紹
• IR
• http://docs.huihoo.com/ruby/ruby-man-1.4/yacc.html