Concurrent Optimizing Brainfuck JIT compiler

contributed by <kobe0308>, <youchihwang>, <vjux>, <mingnus>

tags: `kobeyu`

github

作業目標

[ ]研究concurrent Brainfuck JIT Compiler

工作項目

[ ]分析各種不同的實現方式
- Bukkake: A parallel brainfuck JIT in C
- Brainfuck Process Extensions
- Parallel Brainfuck
- Concurrent Brainfuck
[ ]擴充concurrent語法
[ ]語言規格書
[ ]功能驗證
[ ]效能分析
- 參考 rdebath/Brainfuck 的成果

中英關鍵字間請以空白隔開

請補上 github 連結
課程助教

已修正 Kobe Yu

Bukkake實作分析

此實作是參考 cmdli 的版本,在 Repository 中有一份投影片簡報,摘要如下:

1. 觀察 helloworld.b 的程式發現

迴圈內都是加法運算
都是依序執行
Withholds treats from puppies ??
可以被平行化!

以 HelloWorld.b 為例,在迴圈內是針對不同的 cell 做運算,對於資料的存取是互相獨立的,所以迴圈內的操作可以完全的平行化.

"withholds treats from puppies" 意思是不給小狗獎勵(食物之類), 引申意思可能是沒有給電腦足以發揮其性能的程式?? mingnus

2. concurrent 的設計
每一行都是一個 program,就像 thread_create 所要帶入的 function.

+++++ +++++             initialize counter (cell #0) to 10
[                       
   > +++++ ++              add  7 to cell #1
   > +++++ +++++           add 10 to cell #2 
   > +++                   add  3 to cell #3
   > +                     add  1 to cell #4
   <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'

平行化後的 helloworld.b

thread#1 ~ thread#4 初始化 cell[1] ~ cell[4] ({70, 100, 30, 10})
thread#0 印出 "Hello "
thread#5 印出 "W"
thread#0 印出 "orld!\n"

+++++*-[**********-] |>++H.|>+e.+++++ ++l.l.+++o.>++_.<|W|o.+++r.----- -l. ----- ---d.>+!.>\n.
> +++++ ++         70|
>> +++++ +++++     100|
>>> +++            30|
>>>> +             10|
                           |>+++++ +++++ +++++         |.|

回到 bukkake 的版本
- 在程式中每一行代表一個 thread ,要注意的是這邊所有的記憶體都是共享的(shared memory),所以無論哪個 thread 在執行時都可以存取 tape 的內容.
- 呼叫 thread 的方式是透過 * 這個操作字元,當執行到 * 時,啟動一個 thread 執行第(*ptr)行的指令.
舉例:
印出四個字元 !"#!,其中兩個!是在第一個 thread (第一行)印出,第二個 thread (第二行)印出 ",而第三個 thread (第三行)印出 #,程式碼如下:

+++++ [>++++++<-]> +++.<+* +*         |>--.  \n
>+.                                   |
>+.                                   |

Concurrent 擴充語法

\n : return; exit thread and denote beginning of another function
* : relative spawn; spawn a thread running the line number that is
the sum of your line number and the current byte
| : barrier; block until all threads with a barrier in this column are at said

column
舉例:

	正確的同步(barrier)
	+++.<+* +* | \n
	+++.       |
	
	可能產生非預期結果的語法
	+++.<+* +* | \n
	+++.|

解析程式碼

Bukkake JIT 是跟 OS 申請一塊可執行的記憶體,然後根據每一個 bf 的指令轉為 x86 組合語言,並寫入記憶體中,等到所有的 bf 程式碼都轉換完成後就從記憶體的第一個位址開始執行,所以沒有 IR 的設計.
關於 concurrent 的原理目前看到有一個 thread pool ,至於怎麼派發工作與其他細節尚待解析.

bukkake.c

應用程式的入口 (main) 的所在,一開始會透過 mmap 將檔案到映射虛擬記憶體空間,使用回傳的位址對檔案進行讀寫操作.
在開始解析程式之前會先計算以下參數:程式的總行數,最長的列寬度以及在第一行 (main thread) 是否有 concurrent ('*')的指令,接著會宣告四塊記憶體空間：

barriers = calloc(longest_row, sizeof(struct barrier*));
line_barriers = (unsigned long**) calloc(num_rows, sizeof(unsigned long*));
line_barrier_indices = (unsigned long*) calloc(num_rows, sizeof(unsigned long));
lines = calloc(num_rows + 1, sizeof(func));

src/barrier.c 的 Line #53 是 sched_yield();，要注意到後者在 Linux 2.6.23 所引入的 CFS 已經棄置，請改用其他方式 jserv

todo
1.理解 sched_yield（）
2.CFS 原理
3.引進 CFS 對於 sched_yield() 的影響
4.更好的實作方式與評估效益.
ref
kobeyu

runtime.c

會使用到 jit.c 跟 static.c ,往下trace code.

Machine code

根據 Intel 64 and IA-32 Architectures Software Developer’s Manual

// push rcx
jit(0x51);

source code 中有一段程式碼 push rcx 需要將其編為機械碼，從 intel spec 中得知 rcx 為 64 位元的 register，而push 的 Opcode 是 50+rd， +rd 是用來編碼 register operand，那 +rd 要填什麼值呢？第二個 table 查知RCX 的 Reg Field 要填為 1，機械碼編為 51。
而 Op/En 的 M、 O、 I, 64-Bit Mode 的 Valid、N.E、 Compat/Leg Mode， REX.B 這些欄位還不知道其作用。YouChih Wang

// push r8
jit2(0x41, 0x50);

source code 中有一段程式碼 push r8 需要將其編為機械碼，從 intel spec 中得知 r8 為 64 位元的 register，而push 的 Opcode 是 50+rd， +rd 是用來編碼 register operand，那 +rd 要填什麼值呢？第二個 table 查知RCX 的 Reg Field 要填為 0，機械碼編為 50。但是為什麼要多編 0x41 呢？從 table3-1 得知 R8 的 REX.B 是 yes，所以需要加入 RegPrefix 的指令，再看 table 2-4，REX.B 填 1，所以 REG Prefix 編碼為 0x41，最後整個 push r8 編碼為 0x41 0x50。YouChih Wang

// mov bu_putchar, %rax
jit2(0x48, 0xb8);
uint64_t loc = (uint64_t) bu_putchar;
jit64(loc);

看到 maker 在 .c 加了組合語言的註解 mov bu_putchar, %rax，看不懂 % 這個符號是代表什麼，查了才知道，assembly language syntax 主要有分二個 branches，一個是 AT&T syntax，另一個是 intel syntax，可以從存取 register 的符號區分兩者。

AT&T syntax 存取 register 需加 %，mov 指令的 destination 在後方，使用常數需加$；

而 intel syntax 存取 register 不需加 %，mov 指令的 destination 在前方，使用常數不需加 $。

而 GNU as 可使用.intel_syntax selects Intel mode, .att_syntax兩種設定來選擇 AT&T syntax 或 intel syntax
YouChih Wang

rd io 的 io 是什麼？目前尚未找到定義。YouChih Wang

找到 io 的定義了，原來是在 opcode 後接 8 byte immediate，也就是 64 bits 立即值，在這裡指的是 funtion address。YouChih Wang

藉由 table 3-1 可得知 rd 需填 0，所以 Opcode 部分就是 0xB8。（在未查到 rd io 定義前。）

REX.W 需設為 1。所以需加 prefix instruction 0x48。

整個編碼就是 0x48 0xb8。YouChih Wang

uint64_t loc = (uint64_t) bu_putchar;
jit64(loc);

這段是將 bu_putchar 的 address 取出來。

使用 objdump -d bukkake命令，可以 disassemble objfile，查看 bu_putchar 的 address 為 0…04017c0，

// mov bu_putchar, %rax
jit2(0x48, 0xb8);
uint64_t loc = (uint64_t) bu_putchar;
jit64(loc);

以上這段程式碼是在 bu_put() 裡，使用 objdump -d bukkake命令 disassemble objfile，找尋 bu_put（），看到對應的位置顯示$0x4017c0，這就是 bu_putchar 的 address，並且使用 jit64() 將這 64 bit 的 address 放入執行檔。

System V Application Binary Interface x86-64TM Architecture Processor Supplement Draft Version 0.21

3.2.2 The Stack Frame

In addition to registers, each function has a frame on the run-time stack.

每個 function 除了可以使用 register 外，在 run-time 時還可以使用 stack。YouChih Wang

This stack grows downwards from high addresses.

從以下的 test.c line 2 , pr_2 傳遞參數到 pr_3，line 35，line 36，pr_3() 接收來自 pr_2 ()的參數，再對應到 test.s pr_3() line 13，14 即可驗證 stack 是從高位址往低位址成長。

  test.c
  
  1 #include <stdio.h>         
  2 void pr_3(int a_3, int b_3)
  3 {
  4 }
  5 
  6 void pr_2(int a_2, int b_2)
  7 {
  8         pr_3(a_2, b_2);
  9 }
 10 
 11 void pr_1(int a_1, int b_1)
 12 {
 13         pr_2(a_1, b_1);
 14 }
 15 
 16 int main ()
 17 {
 18         int a=0;
 19         int b=1;
 20 
 21         pr_1(a, b);
 22 
 23         return 0;
 24 }

執行 gcc -O0 -S test.c，
生成 test.s

  test.s
  
  1         .file   "test.c"                                                                                                                
  2         .text
  3         .globl  pr_3
  4         .type   pr_3, @function
  5 pr_3:
  6 .LFB0:
  7         .cfi_startproc
  8         pushq   %rbp
  9         .cfi_def_cfa_offset 16
 10         .cfi_offset 6, -16
 11         movq    %rsp, %rbp
 12         .cfi_def_cfa_register 6
 13         movl    %edi, -4(%rbp)
 14         movl    %esi, -8(%rbp)
 15         nop
 16         popq    %rbp
 17         .cfi_def_cfa 7, 8
 18         ret
 19         .cfi_endproc
 20 .LFE0:
 21         .size   pr_3, .-pr_3
 22         .globl  pr_2
 23         .type   pr_2, @function
 24 pr_2:
 25 .LFB1:
 26         .cfi_startproc
 27         pushq   %rbp
 28         .cfi_def_cfa_offset 16
 29         .cfi_offset 6, -16
 30         movq    %rsp, %rbp
 31         .cfi_def_cfa_register 6
 32         subq    $8, %rsp
 33         movl    %edi, -4(%rbp)
 34         movl    %esi, -8(%rbp)
 35         movl    -8(%rbp), %edx
 36         movl    -4(%rbp), %eax
 37         movl    %edx, %esi
 38         movl    %eax, %edi
 39         call    pr_3
 40         nop
 41         leave
 42         .cfi_def_cfa 7, 8
 43         ret
 44         .cfi_endproc
 45 .LFE1:
 46         .size   pr_2, .-pr_2
 47         .globl  pr_1
 48         .type   pr_1, @function
 49 pr_1:
 50 .LFB2:
 51         .cfi_startproc
 52         pushq   %rbp
 53         .cfi_def_cfa_offset 16
 54         .cfi_offset 6, -16
 55         movq    %rsp, %rbp
 56         .cfi_def_cfa_register 6
 57         subq    $8, %rsp
 58         movl    %edi, -4(%rbp)
 59         movl    %esi, -8(%rbp)
 60         movl    -8(%rbp), %edx
 61         movl    -4(%rbp), %eax
 62         movl    %edx, %esi
 63         movl    %eax, %edi
 64         call    pr_2
 65         nop
 66         leave
 67         .cfi_def_cfa 7, 8
 68         ret
 69         .cfi_endproc
 70 .LFE2:
 71         .size   pr_1, .-pr_1
 72         .globl  main
 73         .type   main, @function
 74 main:
 75 .LFB3:
 76         .cfi_startproc
 77         pushq   %rbp
 78         .cfi_def_cfa_offset 16
 79         .cfi_offset 6, -16
 80         movq    %rsp, %rbp
 81         .cfi_def_cfa_register 6
 82         subq    $16, %rsp
 83         movl    $0, -8(%rbp)
 84         movl    $1, -4(%rbp)
 85         movl    -4(%rbp), %edx
 86         movl    -8(%rbp), %eax
 87         movl    %edx, %esi
 88         movl    %eax, %edi
 89         call    pr_1
 90         movl    $0, %eax
 91         leave
 92         .cfi_def_cfa 7, 8
 93         ret
 94         .cfi_endproc
 95 .LFE3:
 96         .size   main, .-main
 97         .ident  "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609"
 98         .section        .note.GNU-stack,"",@progbits

Figure 3.3 shows the stack organization.
The end of the input argument area shall be aligned on a 16 byte boundary.

解釋 parameter 和 argument 差別
1：parameter 可以想成是投手準備要投球過來，投 1、2、3、…顆，但還沒投的那些球，argument 可以想成是投手真正投出去的球。

2：也可參考 stackoverflow What's the difference between an argument and a parameter

3：也可參考 c11 spec 關於 argument 的部分，3.3 有一段描述 expression in the comma-separated list bounded by the parentheses in a function call，argument 是在 function call 中由（）所包括起來的 expression，有一點感覺了嗎？若沒有，6.5.17 還有一段，In the function call
f(a, (t=3, t+2), c)
the function has three arguments, the second of which has the value 5.，這個 function 有 3 個 arguments，第 2 個 argument 是 5，
這就是真正投出去的球。

3.3
1 argument
actual argument
actual parameter (deprecated)
expression in the comma-separated list bounded by the parentheses in a function call
expression, or a sequence of preprocessing tokens in the comma-separated list bounded
by the parentheses in a function-like macro invocation
6.5.17 Comma operator
3 EXAMPLE As indicated by the syntax, the comma operator (as described in this subclause) cannot
appear in contexts where a comma is used to separate items in a list (such as arguments to functions or lists
of initializers). On the other hand, it can be used within a parenthesized expression or within the second
expression of a conditional operator in such contexts. In the function call
f(a, (t=3, t+2), c)
the function has three arguments, the second of which has the value 5.

4：也可參考 c11 spec 關於 parameter 的部分，3.16 有一段描述，object declared as part of a function declaration，parameter是屬於 function 宣告的一部分，這就是投手準備要投球過來，投 1、2、3、…顆，但還沒投的那些球。

3.16
parameter
formal parameter
formal argument (deprecated)
object declared as part of a function declaration or definition that acquires a value on
entry to the function, or an identifier from the comma-separated list bounded by the
parentheses immediately following the macro name in a function-like macro definition

YouChih Wang

In other words, the value (%rsp − 8) is always a multiple of 16 when control is
transferred to the function entry point. The stack pointer, %rsp, always points to
the end of the latest allocated stack frame. 7
The 128-byte area beyond the location pointed to by %rsp is considered to
be reserved and shall not be modified by signal or interrupt handlers.8 Therefore,
functions may use this area for temporary data that is not needed across function
calls. In particular, leaf functions may use this area for their entire stack frame,
rather than adjusting the stack pointer in the prologue and epilogue.

以上部分，還不懂，需再回來看。YouChih Wang

System V Application Binary Interface x86-64TM Architecture Processor Supplement Draft Version 0.21

3.2.3 Parameter Passing
The conventional use of %rbp as a frame pointer for the stack frame may be avoided by using
%rsp (the stack pointer) to index into the stack frame. This technique saves two instructions in
the prologue and epilogue and makes one additional general-purpose register (%rbp) available.

%rbp：frame (base) pointer (%rbp)
%rsp：stack pointer that point top of stack
caller function 會有 local stack frame，由 %rbp 指向 stack frame 起點，由 %rsp 指向最 top 的 stack，當 caller 呼叫 callee 時，caller 的 %rsp 需將值指定給 callee 的 %rbp，當成是 callee 的 stack frame，從上方的 test.s 的 pr_3() line 8 line 11 可得知，以上是描述 call flow，
那 return flow 呢？可藉由 pop %rbp 將 caller 的 return address pop 出，下方使用 gdb 利用 %rbp 來印出 caller

(gdb) b pr_3
Breakpoint 1 at 0x4004e0: file test.c, line 4.
(gdb) r
Starting program: /home/xxx/Jserv/test/test 

Breakpoint 1, pr_3 (a_3=0, b_3=1) at test.c:4
4	}
(gdb) backtrace
#0  pr_3 (a_3=0, b_3=1) at test.c:4
#1  0x0000000000400500 in pr_2 (a_2=0, b_2=1) at test.c:8
#2  0x0000000000400520 in pr_1 (a_1=0, b_1=1) at test.c:13
#3  0x0000000000400548 in main () at test.c:21

futex：類似 mutex，但不同的是 futex 是在 userspace 執行，少了進出 kernel space，所以 overhead 會比較小。

jit.c

卡關中…
卡在組合語言的部分:

    // get rcx from param
    // mov %rdi, %rcx
    jit3(0x48, 0x89, 0xf9);

問題定義:
根據AMD64 ABI規格書P24的描述,在函式呼叫時參數傳遞是透過暫存器來完成的,第一個 argument 使用 %rdi ,第二個是 %rsi ,第三個是 %rdx ,第四個是 %rcx …

為什麼需要 calling conventions 機制呢？
舉例：Android 手機中有一個 java virtual machine 名為 Dalvik，上面跑的都是 java code，若需要執行 C++ 程式那怎麼辦呢？ Java 會透過名為 java native method 的 interface 去呼叫 C++ 程式，而參數要如何傳遞呢？這就要兩方都遵守 ABI interface 傳參數的規範，才能正確取得參數，請看下面的 caller 和 callee 參數放置的順序。youchihwang

下方的 Java 程式碼沒有列出的必要，說明用的程式碼應該儘量精簡且具體。Dalvik 的例子真要探討的話，已經超出 calling convention，請見: JNI Tips jserv

下方的檔案 [Android 7.0.0_r1 - Nougat/frameworks/base/services/core/java/com/android/server/lights/LightsService.javaLightsService.java](http://androidxref.com/7.0.0_r1/xref/frameworks/base/services/core/java/com/android/server/lights/LightsService.java) line 136 使用 JNI setLight_native（）interface。 [Android 7.0.0_r1 - Nougat /frameworks/base/services/core/jni/com_android_server_lights_LightsService.cpp](http://androidxref.com/7.0.0_r1/xref/frameworks/base/services/core/jni/com_android_server_lights_LightsService.cpp) Line 106 就是 JNI setLight_native 的實作 [Android 7.0.0_r1 - Nougat/hardware/qcom/display/msm8084/liblight/lights.c](http://androidxref.com/7.0.0_r1/xref/hardware/qcom/display/msm8084/liblight/lights.c) Line 260 ~ 269 是指定一個低層的function 給上層使用。

仍有疑惑的地方是：
1.呼叫這個 asm 函式(caller)的地方在哪裡
2.傳入幾個參數以及這些參數的用途.

根據 Wikipedia 的資料,Windows 的參數傳遞依序是透過 RCX/RDX/R8/R9…但這不會是在 Windows 上開發的(non-POSIX).

把第一參數 rdi 存到 rcx , 不過光看這行還是不知道上下文做了什麼XD mingnus
你應該寫個小程式，然後用 gcc -S 和對照 objdump -d 的輸出，確認 function call 由哪些機械碼指令完成 jserv
這時候非常需要 GDB，請趕快學習，包含 GDB Python integration jserv

todo:
寫一個小程式,除了 main 之外還有一個四個參數 (int) 的 function ,比對 asm/objdump/gdb 參數傳遞的過程,並驗證是否符合abi規格書中所描述方式進行. kobeyu

驗證參數傳遞是依序透過 di/si/dx/cx 四個暫存器傳遞,











void func(int a, int b, int c, int d)
{
    a++; b++; c++; d++;
    printf("abcdK:%d,%d,%d,%d\n",a,b,c,d);
}

int main(void)
{
    func(1,2,3,4);
        return 0;
}

$ gcc -S callee.c
以下是 .s 的內容
可以看到第 17~20 行是暫存器 di/si/dx/cx 依序把傳進來的參數搬到 %rbp 對應的記憶體位置








































.file   "callee.c"
        .section        .rodata
.LC0:
        .string "abcdK:%d,%d,%d,%d\n"
        .text
        .globl  func
        .type   func, @function
func:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $16, %rsp
        movl    %edi, -4(%rbp)
        movl    %esi, -8(%rbp)
        movl    %edx, -12(%rbp)
        movl    %ecx, -16(%rbp)
        movl    -16(%rbp), %esi
        movl    -12(%rbp), %ecx
        movl    -8(%rbp), %edx
        movl    -4(%rbp), %eax
        movl    %esi, %r8d
        movl    %eax, %esi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   func, .-func
        .globl  main
        .type   main, @function
main:
.LFB1:
#include <stdio.h>

$objdump -d a.out
以下是 objdump 的內容,可以看到第 6~9 行依序是暫存器 di/si/dx/cx 把傳進來的參數搬到 %rbp 對應的記憶體位置







































...
000000000040052d <func>:
  40052d:       55                      push   %rbp
  40052e:       48 89 e5                mov    %rsp,%rbp
  400531:       48 83 ec 10             sub    $0x10,%rsp
  400535:       89 7d fc                mov    %edi,-0x4(%rbp)
  400538:       89 75 f8                mov    %esi,-0x8(%rbp)
  40053b:       89 55 f4                mov    %edx,-0xc(%rbp)
  40053e:       89 4d f0                mov    %ecx,-0x10(%rbp)
  400541:       83 45 fc 01             addl   $0x1,-0x4(%rbp)
  400545:       83 45 f8 01             addl   $0x1,-0x8(%rbp)
  400549:       83 45 f4 01             addl   $0x1,-0xc(%rbp)
  40054d:       83 45 f0 01             addl   $0x1,-0x10(%rbp)
  400551:       8b 75 f0                mov    -0x10(%rbp),%esi
  400554:       8b 4d f4                mov    -0xc(%rbp),%ecx
  400557:       8b 55 f8                mov    -0x8(%rbp),%edx
  40055a:       8b 45 fc                mov    -0x4(%rbp),%eax
  40055d:       41 89 f0                mov    %esi,%r8d
  400560:       89 c6                   mov    %eax,%esi
  400562:       bf 24 06 40 00          mov    $0x400624,%edi
  400567:       b8 00 00 00 00          mov    $0x0,%eax
  40056c:       e8 9f fe ff ff          callq  400410 <printf@plt>
  400571:       c9                      leaveq 
  400572:       c3                      retq   

0000000000400573 <main>:
  400573:       55                      push   %rbp
  400574:       48 89 e5                mov    %rsp,%rbp
  400577:       b9 04 00 00 00          mov    $0x4,%ecx
  40057c:       ba 03 00 00 00          mov    $0x3,%edx
  400581:       be 02 00 00 00          mov    $0x2,%esi
  400586:       bf 01 00 00 00          mov    $0x1,%edi
  40058b:       e8 9d ff ff ff          callq  40052d <func>
  400590:       b8 00 00 00 00          mov    $0x0,%eax
  400595:       5d                      pop    %rbp
  400596:       c3                      retq   
  400597:       66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
  40059e:       00 00 
...

GDB 驗證
也是一樣依序透過 di/si/dx/cx 傳遞參數.

Breakpoint 1, func (a=1, b=2, c=3, d=4) at callee.c:6
6               a++; b++; c++; d++;
(gdb) info register
rax            0x400573 4195699
rbx            0x0      0
rcx            0x4      4
rdx            0x3      3
rsi            0x2      2
rdi            0x1      1
rbp            0x7fffffffe150   0x7fffffffe150
rsp            0x7fffffffe140   0x7fffffffe140
r8             0x7ffff7dd4e80   140737351863936
r9             0x7ffff7dea530   140737351951664
r10            0x7fffffffdff0   140737488347120
r11            0x7ffff7a36e50   140737348070992
r12            0x400440 4195392
r13            0x7fffffffe240   140737488347712
r14            0x0      0
r15            0x0      0
rip            0x400541 0x400541 <func+20>
eflags         0x202    [ IF ]
cs             0x33     51
ss             0x2b     43
ds             0x0      0
es             0x0      0
fs             0x0      0
gs             0x0      0
(gdb)

X86 MMU fault handling is turing complete

論文
 簡報錄影

摘要:
目前就我的理解是: 刻意地對記憶體操作,故意產生 page fault 的情況,然後讓某些 flag 發生規性性的變化,讓這些連續的間接操作與變化滿足圖靈完備,由於不是由指令直接控制這些 cpu 上的 flag ,所以可以聲稱不用透過任何的 cpu 指令就可以達到滿足圖靈完備.

這樣透過指令間接地操作機器在術語上稱為 "Weird Machine"

參考資料
- WiKi - weired machine
- The Weird Machine
- asm: movdbz
- Exploit Programming
- Instruction-less computation

文件 Brainfuck Process Extensions

Brainfuck Process Extensions 心得

Tritium Optimization Techniques

根據 esolangs.org 指出, Tritium 是目前最快的 bf interpreter, 特色包括各式深度最佳化手法 (-O0 ~ -Orun) 及多樣化的 backends (包括 profiler, 會追蹤每條 IR 的執行次數)。其最佳化方式大致如下: 輸入的 bf code 會被轉成 IR code, 稱之為 tree (實際上是 list of tree cells), interpreter 再對 IR 進行多次最佳化, 最後交由 backend 輸出。

Tritium IR code

一道 IR code 由struct bfi表示。我們可用 option -vvv 印出 IR code

Sample:

  T_ADD[0]:10, $0, prev 0, prof 1, @(1,1)
  T_WHL[0],id=1, $1, jmp $12, prof 1, @(1,11)

以第一行為例, 其對應的 C-code 為p[0] += 10
T_ADD: IR code
[0]: IR 操作相對位址 (相對於目前 cell)。對應bfi::offset
:10: IR operand, 相當於 RLE 處理後的累計次數。對應bfi::count
$0: IR index label (用於jmp指令)
prof 1: IR 執行次數 (profiler 開啟時才會輸出, option -T)
@(1,1): line 1, column 1

Tritium Optimisation Levels

-m: No optimisation
-O0: RLE, 並移除程式開頭不可能執行的 loop
- function: load_file()
-O1: Only enable pointer motion optimisation.
- Clear loop: 將[-]或[+]轉換為 value set, 對應的 IR code 為T_SET
  - function: quick_scan()
- Merging pointer movements: 消除不必要的 pointer movement, 改用常數 offset 存取 cells。概念類似於 operation offset, 但是功能更強, 可以跨 loop 整併 pointer movement。整併後除了可減少指標運算, 也有助於 backend register allocation。
  - example1: >>>++<<<- 轉換為 p[3] += 2; p[0]--;
  - example2: >>>>[>>>++<<<-] 轉換為 while (p[4]) {p[7] += 2; p[4]--;}
  - example3: >>>>[>>>++<<<-]<<[>++<-] 轉換為
    while (p[4]) {p[7] += 2; p[4]--;} while (p[2]) {p[3] += 2; p[2]--;}
  - function: pointer_scan()。實作上是透過合併與 propagate T_MOV IR code 達成, 例如>>>++<<<-當中的p+=3及p-=3就會併入T_ADD, 如下所示
- pointer_regen

Pointer movement optimization example1

    # example1: >>>++<<<-
    # initial IR code (RLE only)
    T_MOV 3 $0, prev 0, @(1,1)
    T_ADD[0]:2, $1, @(1,4)
    T_MOV -3 $2, @(1,6)
    T_ADD[0]:-1, $3, next 0, @(1,9)

    # temporary IR code
    T_ADD[3]:2, $1, prev 0, @(1,4)
    T_MOV 3 $0, @(1,1)
    T_MOV -3 $2, @(1,6)
    T_ADD[0]:-1, $3, next 0, @(1,9)

    # final IR code
    T_ADD[3]:2, $1, prev 0, @(1,4)
    T_ADD[0]:-1, $3, next 0, @(1,9)

Pointer movement optimization example2

    # example2: >>>>[>>>++<<<-]
    # initial IR code (RLE only)
    T_MOV 4 $0, prev 0, @(1,1)
    T_WHL[0],id=1, $1, jmp $6, @(1,5)
     T_MOV 3 $2, @(1,6)
     T_ADD[0]:2, $3, @(1,9)
     T_MOV -3 $4, @(1,11)
     T_ADD[0]:-1, $5, @(1,14)
    T_END[0] id=1, $6, next 0, jmp $1, @(1,15)

    # temporary IR code1
    # 將 loop 之前的 pointer movement 移到 loop 尾端
    T_WHL[4],id=1, $1, prev 0, jmp $6, @(1,5)
     T_MOV 4 $7, @(1,5)
     T_MOV 3 $2, @(1,6)
     T_ADD[0]:2, $3, @(1,9)
     T_MOV -3 $4, @(1,11)
     T_ADD[0]:-1, $5, @(1,14)
     T_MOV -4 $8, @(1,14)
    T_END[4] id=1, $6, jmp $1, @(1,15)
    T_MOV 4 $0, next 0, @(1,1)

    # temporary IR code2
    # 中間最佳化步驟類似於 example1, 在此省略
    T_WHL[4],id=1, $1, prev 0, jmp $6, @(1,5)
     T_ADD[7]:2, $3, @(1,9)
     T_ADD[4]:-1, $5, @(1,14)
    T_END[4] id=1, $6, jmp $1, @(1,15)
    T_MOV 4 $0, next 0, @(1,1)

    # final IR code
    # 最後一行`T_MOV`位於程式尾端, 故被移除
    T_WHL[4],id=1, $1, prev 0, jmp $6, @(1,5)
     T_ADD[7]:2, $3, @(1,9)
     T_ADD[4]:-1, $5, @(1,14)
    T_END[4] id=1, $6, jmp $1, @(1,15)

-O2: Allow a few simple optimisations.
- invariants_scan(): 迴圈相關的最佳化。根據迴圈特性, 將其轉成更有效率的 IR
  - classify_loop(): 標記 loop 類型。只執行一次的迴圈標記為 T_IF, 執行次數未知的迴圈則標記為T_CALC, T_MULT, 或T_CMULT
  - flatten_multiplier(): 概念類似於 multiplication loop, 將T_MULT或T_CMULT迴圈內容轉為乘法
  - build_string_in_tree(): 為了克服 brainfuck 沒有常數字串/字元的最佳化手法。做法是根據 cell[i] 當前數值, 將brainfuck output op . (T_PRT) 轉換為直接列印常數字元 (T_CHR)。例如hello.b可以被轉換為一連串T_CHR指令, 使其不再依賴 cell 內容列印字元
  - find_known_calc_state(): 簡化T_CALC不變量相關操作, 例如 C-code a = b; b = 0; b = a; a = 1; 可簡化為a = 1;, 因為變數b的數值最後還是沒有改變。這類操作常見於 brainfuck, 因為 brainfuck 做 copy assignment 必然會使 rvalue (即 copy source) 歸零, 如果想保持該數值只能把它暫存到其他位址，因此造成了上述程式碼。(參見上次作業)
  - scan_one_node(): 掃瞄 cell[i] 的所有操作並進行最佳化, 其中一個功能是簡化執行次數已知的迴圈 (flatten_loop()), 例如 C-code for (i = 0; i < 10; i++) x++;可簡化為x += 10;
- 刪除程式尾端的T_SET, T_ADD, T_CALC指令
  - 這些指令不影響程式輸出入, 形同 dead code, 故可刪除
  - function: trim_trailing_sets()
- 再次合併 pointer movement (if -fpointer-rescan is provided)

某些手法應該是既有的編譯器最佳化手法, 應該有對應的專有名詞 (回顧 compiler 課本後半段) mingnus

Example of trim_trailing_sets()

  # hello.b
  ++++++++++[>+++++++>++++++++++>+++>+<<<<-]
  >++.>+.+++++++..+++.>++.<<+++++++++++++++.
  >.+++.------.--------.>+.>.

  # hello.b after invariants_scan()
  # trim_trailing_sets() 將刪除末端四個 T_SET 指令
  T_CHR 'H', $15, prev 0, @(1,46)
  T_CHR 'e', $18, skip $15, @(1,49)
  T_CHR 'l', $20, skip $15, @(1,57)
  T_CHR 'l', $21, skip $15, @(1,58)
  T_CHR 'o', $23, skip $15, @(1,62)
  T_CHR ' ', $26, skip $15, @(1,66)
  T_CHR 'W', $29, skip $15, @(1,84)
  T_CHR 'o', $31, skip $15, @(1,86)
  T_CHR 'r', $33, skip $15, @(1,90)
  T_CHR 'l', $35, skip $15, @(1,97)
  T_CHR 'd', $37, skip $15, @(1,106)
  T_CHR '!', $40, skip $15, @(1,109)
  T_CHR 0x0a, $42, skip $15, @(1,111)
  T_SET[4]:10, $9, @(1,36)
  T_SET[1]:87, $28, @(1,69)
  T_SET[2]:100, $36, @(1,98)
  T_SET[3]:33, $39, next 0, @(1,108)

Example of find_known_calc_state()

  # awib 開頭程式碼, 重點是中間這段 "[->+>+<<]>>[-<<+>>]+"
  >>>>>>>>>>>>>>>>>>>>++>>>>+[>[-],+[->+>+<<]>>[-<<+>>]+<[-[>+++++[-<----
  --->]+<-[-[-[-[--------------[--[-->>+<<[>>-<++[-<--------->]+<[--[>+++
  ++++++[-<++++++++++>]<[-]]]]]]]]]]]<->]>[-<<<->>>]<<<]

  # invariants_scan() loop #44, processing $12 (T_SET[25]:0, $12, @(1,36))
  T_SET[20]:2, $1, prev 0, @(1,21)
  T_SET[24]:1, $3, @(1,27)
  T_WHL[24],id=1, $4, jmp $107, @(1,28)
   T_SET[25]:0, $7, @(1,31)
   T_INP[25], $9, @(1,33)
   T_ADD[25]:1, $10, @(1,34)
   T_CALC[26] = 0 + [25]*1, $14, @(1,38)
   T_CALC[27] = 0 + [25]*1, $16, @(1,40)
   T_SET[25]:0, $12, @(1,36)
   T_CALC[25] = 0 + [27]*1, $23, @(1,50)
   T_CALC[27] += [27]*-1 + 0, $21, @(1,47)
   T_NOP[27]:0, $25, jmp $20, @(1,53)
   T_ADD[27]:1, $26, @(1,54)
   ...

  # invariants_scan() loop #49, processing $14  (T_CALC[26] = 0 + [25]*1, $14, @(1,38))
  # cell[25] 數值不變, 故簡化為 T_NOP
  T_SET[20]:2, $1, prev 0, @(1,21)
  T_SET[24]:1, $3, @(1,27)
  T_WHL[24],id=1, $4, jmp $107, @(1,28)
   T_SET[25]:0, $7, @(1,31)
   T_INP[25], $9, @(1,33)
   T_ADD[25]:1, $10, @(1,34)
   T_CALC[26] = 0 + [25]*1, $14, @(1,38)
   T_CALC[27] = 0 + [25]*1, $16, @(1,40)
   T_NOP[25]:0, x2[25]:1, x3[25]:0, $23, @(1,50)
   T_CALC[27] += [27]*-1 + 0, $21, @(1,47)
   T_NOP[27]:0, $25, jmp $20, @(1,53)
   T_ADD[27]:1, $26, @(1,54)
   ...

  # invariants_scan() loop #62, processing $14  (T_CALC[26] = 0 + [25]*1, $14, @(1,38))
  # 簡化 cell[27] 相關操作後的結果
  T_SET[20]:2, $1, prev 0, @(1,21)
  T_SET[24]:1, $3, @(1,27)
  T_WHL[24],id=1, $4, jmp $107, @(1,28)
   T_SET[25]:0, $7, @(1,31)
   T_INP[25], $9, @(1,33)
   T_ADD[25]:1, $10, @(1,34)
   T_CALC[26] = 0 + [25]*1, $14, @(1,38)
   T_ADD[27]:1, $26, @(1,54)
   ...

-O3 Maximum normal level, default.
- 從 code 來看, -O2 和 -O3 的效果應該是一樣的
-Orun When generating code run the interpreter over it first.
- function: try_opt_runner() (opt_runner = 1)

其他實驗

巢狀迴圈

brainfuck 必須以巢狀迴圈做兩個變數的乘法運算, 例如以下 C-code

p[0] = getchar();
p[1] = getchar();
p[2] = p[1] * p[0];
p[1] = 0;
p[0] = 0;
putchar(p[2]);

對應的 brainfuck 為

,>,<[->[->+<]<]>>.

但 Tritium 無法簡化巢狀迴圈

  T_INP[0], $0, prev 0, @(1,1)
  T_INP[1], $2, @(1,3)
  T_WHL[0],id=1, $4, jmp $14, @(1,5)
   T_ADD[0]:-1, $5, @(1,6)
   T_CALC[2] += [1]*2 + 0, $10, @(1,11)
   T_SET[1]:0, $8, @(1,9)
  T_END[0] id=1, $14, jmp $4, @(1,16)
  T_PRT[2], $16, next 0, @(1,19)

Register allocation

測試 ASM backend 如何實現 IR, 並比較不同 optimization level 的 register allocation

測試1: 乘法 p[2] = (p[1] * 2) * p[0];

,>,<[->[->++<]<]>>.

-O1 產生的 IR code

  T_INP[0], $0, prev 0, @(1,1)
  T_INP[1], $2, @(1,3)
  T_WHL[0],id=1, $4, jmp $14, @(1,5)
   T_ADD[0]:-1, $5, @(1,6)
   T_WHL[1],id=2, $7, jmp $12, @(1,8)
    T_ADD[1]:-1, $8, @(1,9)
    T_ADD[2]:2, $10, @(1,11)
   T_END[1] id=2, $12, jmp $7, @(1,14)
  T_END[0] id=1, $14, jmp $4, @(1,16)
  T_PRT[2], $16, next 0, @(1,19)

-O1 -s 輸出的 nasm 片段, 對應中間那段 loop
IR 都是 unary operation, 因此未使用額外 register

loop_1:
	dec byte ptr [ecx]
	cmp dh,byte ptr [ecx+1]
	jz end_2
loop_2:
	dec byte ptr [ecx+1]
	add byte ptr [ecx+2],2
	cmp dh,byte ptr [ecx+1]
	jnz loop_2
end_2:
	cmp dh,byte ptr [ecx]
	jnz loop_1
end_1:

-O2 產生的 IR code

  T_INP[0], $0, prev 0, @(1,1)
  T_INP[1], $2, @(1,3)
  T_WHL[0],id=1, $4, jmp $14, @(1,5)
   T_ADD[0]:-1, $5, @(1,6)
   T_CALC[2] += [1]*2 + 0, $10, @(1,11)
   T_SET[1]:0, $8, @(1,9)
  T_END[0] id=1, $14, jmp $4, @(1,16)
  T_PRT[2], $16, next 0, @(1,19)

-O2 -s 輸出的 nasm 片段, 對應中間那段 loop
乘法運算暫存於 eax

loop_1:
	dec byte ptr [ecx]
	movzx eax,byte ptr [ecx+1]
	add eax,eax
	add byte ptr [ecx+2],al
	mov byte ptr [ecx+1],0
	cmp dh,byte ptr [ecx]
	jnz loop_1
end_1:

測試2: 連加 p[2] = p[0] + p[1]

,>,<[->>+<<]>[->+<]>.

-O2 產生的 IR

  T_INP[0], $0, prev 0, @(1,1)
  T_INP[1], $2, @(1,3)
  T_CALC[2] = 0 + [0]*1, $7, @(1,9)
  T_CALC[2] += [1]*1 + 0, $14, @(1,17)
  T_PRT[2], $18, next 0, @(1,21)

-O2 -s 輸出的 nasm 片段

	movzx eax,byte ptr [ecx]
	mov byte ptr [ecx+2],al
	movzx eax,byte ptr [ecx+1]
	add byte ptr [ecx+2],al

需存取四次記憶體, 但如果是一般 compiled C-code, 只需存取三次 (p[0] 及 p[1] 分別載入不同暫存器, 相加後存入 p[2])

Debugging Tritium

善用 option -v (有些 debug message 需要超過五個-v)
printtree() 印出全部 IR
注意 profiler 無法處理含有 input 指令的程式

附錄

GDB Python Integration

本文介紹 gdb Python API 使用案例, 並改善 supertrace.py, 使其更容易使用

Concurrent Optimizing Brainfuck JIT compiler

tags: kobeyu

作業目標

工作項目

Bukkake實作分析

Concurrent 擴充語法

解析程式碼

bukkake.c

runtime.c

Machine code

System V Application Binary Interface x86-64TM Architecture Processor Supplement Draft Version 0.21

jit.c

X86 MMU fault handling is turing complete

Brainfuck Process Extensions 心得

Tritium Optimization Techniques

Tritium IR code

Tritium Optimisation Levels

其他實驗

Debugging Tritium

附錄

GDB Python Integration

參考資料

tags: `kobeyu`