2011年10月30日 星期日

小心 C++ 的 non-local static 物件的初始順序

Java 有保證在第一次使用 class 內任何東西時, 會執行 class initialization 的程式。而 C++ 沒有保證不同編譯單元的 non-local static 物件的初始順序。

  • 編譯單元是指同一 object file 的原始碼和其引入的檔案
  • static 物件指不在 heap 也不在 stack 上的東西, 包含全域變數、namespace 上的變數、class 內 static member 等

這會導致一個可怕的事實: 使用另一個 object file 的 namespace 下的物件時 (這是滿常見的需求), 會導致未定義的行為。《Effective C++ 3/e》item 4 的建議解法是用函式存 local static 物件, 然後用函式取得該物件 (類似 singleton 的概念)。

用程式來說, 就是:

// Bad! Lead to an undefined behavior if clients access tfs.
FileSystem tfs;

// Good!
FileSystem& tfs() {
    static FileSystem fs;
    return fs;
}

附帶一提, 不同語言的規範差真多, 之前看 ARM 的組語, 才發覺之前只知道 x86 的東西, 而對 CPU 有些誤解。現在確信只學單一工具會有風險, 思維會受限於該工具, 誤以為那就是世界。人生有許多事也是如此, 想到莊子所說的話:

井蛙不可以語於海者,拘於虛也;﹔夏蟲不可以語於冰者,篤於時也;曲士不可以語於道者,束於教也。

體悟漸多後, 漸漸也不知要寫什麼心得才好。總之就是多看看, 時時提醒自己所知很窄, 別錯將一種方法當作只有這種方法。

x86 呼叫函式的設計慣例 (call convention)

在看了《BUFFER OVERFLOW 5 - C/C++ Function Operation》後, 才明白 stack frame 的細節, 果然教人攻擊的文件講得最清楚啊。後來又看了《x86 calling conventions》, 才明白 compiler 編譯高階語言為組語時, 只是定好一套規範, 確保能和 OS 的 linker、loader 搭起來, 到沒有規定一定得怎麼做。編譯的其中一項設計, 是規範 caller 和 callee (被呼叫的函式) 之間怎麼互動, 也就是怎麼傳參數過去, 怎麼取回運算結果。《x86 calling conventions》有列多種做法。

換句話說, 這和設計及使用框架一樣, 為了方便上層開發者, 針對某項工作制定了一整個框架, 只要照著框架的規範使用框架提供的工具, 寫起來就會很快。不過也因此犠牲掉一些彈性和效率, 是不可免的 trade-off。巨觀來看, 設計工具將高階語言編成可執行檔, 也是設計一套框架。如同使用其它框架一樣, 框架幫開發者省去細節, 專心於開發應用程式上; 而了解框架能進一步讓使用者用得更順手, 還有從框架的設計中學到深入的技巧。

呼叫函式時, caller 大致上需要做以下的事, 順序是我大概列的, 只是一種 call convention, 沒有寫得很精確:

  1. 準備參數給 callee
  2. 備份 caller 用到的一些暫存器
  3. 備份 caller 下一個要執行的指令位置
  4. 跳到 callee 要執行的指令位置
  5. ( callee 備份 caller 的 frame's base pointer, 改變 frame's base pointer (ebp)、 stack pointer (esp) )
  6. ( callee 自己準備空間做為區域變數 )
  7. ( callee 結束後, callee 要清掉自己的區域變數 )
  8. 待 callee 結束後, 取得 callee 運算結果
  9. 待 callee 結束後, 清掉傳給 callee 的參數

對照用 gcc -S 編譯 C 程式成組語來看原組語碼, 有一些小心得:

  • 了解呼叫函式要做這麼多事, 也難怪小動作要盡量 inline, 不要真的呼叫函式; 還有避免使用遞迴, 改用 loop + stack。
  • 明白函式內用 static 宣告的變數, 會放到 .data 或 .bss (視有無初始值), 而不在 stack 上。所以函式結束後, 能夠保留原本狀態。
  • 因為呼叫函式是一層層地將函式參數、caller return address、區域變數等資料丟到 stack 上, 當函式結束時, 不用清掉剛才用的區域變數, 只要將 frame pointer 和 stack pointer 指回 caller 用的位置, 就能跳回 caller 之前執行的指令接著跑 (有時仍需還原一些用到的 register)。雖然因此不能取得區域變數, 但省下清記憶體的時間, 算不錯的 trade-off。反過來說, 也沒人規定「一定不能取回結束函式內的區域變數」, 這是 C/C++ 的語法規範, 而相關工具也只是照語法實作而已。
  • 由於 stack pointer (esp) 會變動, 使用 frame pointer (ebp) 比較方便取得參數和區域變數, 分別在 ebp 的上下方。ebp 附近也存了準備還原回 caller 狀態的暫存器, 如 caller 的 ebp。
  • gcc 在進入函式時, 會先計算之後呼叫函式時, 需要多大的空間傳參數, 多讓 stack 往下長一些空間, 這樣之後要呼叫函式時, 可以直接將參數放到預留空間上, 這樣函式結束時, 不需要清掉參數。下面舉例說明。
$ cat f.c
#include <stdio.h>

int add2(int a, int b) {
    return a + b;
}

int add3(int a, int b, int c) {
    return a + b + c;
}

int main(void) {
    add2(3, 5);
    add3(3, 5, 8);
    return 0;
}
$ gcc -S f.c
$ cat f.s
        .file   "f.c"
        .text
.globl add2
        .type   add2, @function
add2:
        pushl   %ebp
        movl    %esp, %ebp
        movl    12(%ebp), %eax
        movl    8(%ebp), %edx
        leal    (%edx,%eax), %eax
        popl    %ebp
        ret
        .size   add2, .-add2
.globl add3
        .type   add3, @function
add3:
        pushl   %ebp
        movl    %esp, %ebp
        movl    12(%ebp), %eax
        movl    8(%ebp), %edx
        leal    (%edx,%eax), %eax
        addl    16(%ebp), %eax
        popl    %ebp
        ret
        .size   add3, .-add3
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $12, %esp  # 在 stack 上預留 4 * 3 = 12 bytes 放參數
        movl    $5, 4(%esp)
        movl    $3, (%esp)
        call    add2
        movl    $8, 8(%esp)  # 呼叫完 add2 後不需清 stack 上的參數
        movl    $5, 4(%esp)
        movl    $3, (%esp)
        call    add3
        movl    $0, %eax
        leave
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
        .section        .note.GNU-stack,"",@progbits

原本的作法是在呼叫函式前用 push 放參數, 呼叫完函式後, caller 用 pop 清掉參數。上面的例子, 則省掉清參數的動作, 也是空間換時間的好例子。

之所以如此強調「清函式參數」和「清區域變數」的行為, 是因為記憶體相關操作相對於 CPU 運算很慢, 要記憶體也慢、清記憶體也慢 (可以實驗看看跑 tree-based 的演算法, 然後比較有無 free tree 的情況, 效能差多少), 了解這些小動作省去清記憶體的動作, 覺得很讚。仔細一想, 這和預先要一塊 buffer, 然後自己管記憶體以減少頻繁地要小塊記憶體的概念相似, 只是在呼叫函式的時候, stack 就是那塊 buffer。

最後附上兩個自己試的小例子, 說明 stack frame 結束後, 原記憶體上的資料仍會留著, 可以將它讀出來, 不過不是什麼正確的行為就是了。

例一:

#include <stdio.h>

void a(void) {
    int i;
    printf("%d ", i);
    i = 10;
    printf("%d\n", i);
}

void b(void) {
    int i;
    printf("%d ", i);
    i = 20;
    printf("%d\n", i);
}

int main(void) {
    a();
    b();
    a();
    return 0;
}

執行結果:

-1080771896 10
10 20
20 10

例二:

#include <stdio.h>

struct Point {
    long x, y;
};

struct Point get_p(void) {
    struct Point a;
    return a;
}

void set_x(void) {
    struct Point a;
    a.x = 1;
}

void set_y(void) {
    struct Point a;
    a.y = 2;
}

int main(void) {
    struct Point t;
    t.x = t.y = 100;
    set_x();
    set_y();
    t = get_p();
    printf("%ld %ld\n", t.x, t.y);
    return 0;
}

執行結果:

1 2

2011年10月28日 星期五

交接心得

將之前隨手的筆記稍微整理一下備忘。

主要參考文章: 《How to hand over a project systematically? - Stack Overflow》。Stack Overflow 真是居家必備的好參考資料。其它參考文章滿發散的, 沒有詳記出處, 看些設置專案的 best practice 也有用, 預防勝於治療。

消化後, 我自己覺得重要的事, 依順序如下:

  1. 每個專案要有個 readme 說明如何開始。確保對方知道如何跑 tests 還有跑範例指令得出範例結果, 確認專案沒有問題。建立專案環境包含知道專案相依性, 若有用適當的軟體, 會少很多痛苦, 像 python 的 virtualenv + pip 是不錯的選擇, 可以盡可能地找出最乾淨的相依組合。
  2. 為什麼我們需要這東西, 它的目的為何
  3. System Context 和 Architecture Overview: 方便對整體有個概念, 兩張圖的用途不同, 參考《Architecture Overview》。不過我的交接對像本來就知道部份內容, 雖然有畫這些圖, 卻不知效果如何。
  4. data flow diagram: 個人偏好有個實例表示資料如何在各元件之間轉換, 能自己想通整個資料走向, 對理解整個架構和除錯很有幫助。我自己在理解專案時, 常會自己畫資料流, 藉此弄清楚架構, 找出我不明白的環節。

從上面列的東西, 可看出來重心放在小巧實例, 方便快速上手, 有東西跑, 比較會有感覺。再來是架構 (概念)和設計背後的原因, 這些很難從程式碼看出來的東西。程式註解也該寫這麼做的原因, 而不是它在做什麼。後者看程式就可以懂了, 寫文件的時間也要花在刀口上。此外, 文件本身也會有維護成本, 盡量寫真的必要的部份。

產生 core dump 檔案

重新寫過記錄在《產生 core dump 的方法》

C/C++ const

個人認為 coding 的核心就是管理「物件/函式」之間的 state, 像 namespace (或 Java 的 package)、class、少用全域變數、static 與否等, 都是協助管理 state 的語法。另外, const 也是很有用的語法, 在 C/C++ 這裡用法更靈活。

參考《Const-Correctness in C++》, 筆記如下:

  • const 和 pointer 的關係: 有分目標變數是否為常數, 和指標本身是否為常數兩種, 共有四種組合。詳見之前寫的: 《C 的型別宣告》
  • const_cast: 將常數轉回非常數, 但為造成未定義的行為, 使用情境很窄, 見文末的例子。
  • 基於 "..." 的實際運作情況, 寫成 char const *s = "..." 較好。若使用 char *s = "...", 之後改變 s[3] 會造成未定義結果。該篇說明的例子是, 改變 s[3] 後會改到別的常數字串, 因為是用同一個 string pool (見該篇例子); 而我用 gcc 在 linux 下試的結果是 segmentation fault。
  • const member function 很有意思 (即宣告成 void foo() const), 用它可做到類似 Haskell 的 stateless 的效果, 語意上是不會改變 member fields, 所以 const member function 只能呼叫其它 const member function, 和 Haskell 預設 function 的行為很像, 有助於維護程式。個人相當喜歡這個效果, 可惜 Java 沒有, 得自己用 interface 做到類似效果, 不怎麼直覺。
  • 承上, const member function 的表現行為, 相當於讓 this 的型別變成 Klass const * const this, 其中 Klass 是某個類別名稱。所以在取用 this->xxx = ... 時自然會造成編譯錯誤。附帶一提, 一般 member function 的 this 的型別則是 Klass * const this, 也就是 this 都是常數指標, 不能讓 this 指到別的物件, 即 this = ... 會造成編譯錯誤; const member function 則多了「指到的對像為常數」的限制, 即 this->xxx = ... 會造成編譯錯誤。
  • const member function 有個顯著的缺點, 它無法做 cache。既然知道它不會改 member field, 那應該有很大的機會針對傳入參數做 cache, 省下運算時間。但衝突的是, const member function 就是不能改 member field, 自然也不方便做 cache (用全域變數太髒了)。這時得引入關鍵字 mutable。const member function 可以改變宣告為 mutable 的 member field。

2011-10-30 Update

看完《Effective C++ 3/e》 item 3 談論如何使用 const, 多學到了:

  • const std::vector<int>::iterator iter = vec.begin(); 相當於 int * const
  • std::vector<int>::const_iterator iter = vec.begin(); 才是 int const *
  • 即使用了 const member function, 仍要避免傳出指標, 以免指標指向的內容被改變, 造成 const member function 看似沒有改變內容的假像
  • 若需要同時提供同樣操作, 但有傳回 const 和非 const 的兩種版本, 為了避免重覆程式碼, 可實作傳回 const 的版本, 然後在非 const 的版本用轉型的方式呼叫 const 的版本:
const char& operator[](std::size_t position) const {
    ...
}
char& operator[](std:size_t position) {
    return const_cast<char&>(
        static_cast<const T&>(*this)[position]
    );
}

2011年10月14日 星期五

關於 C/C++ 負整數的 shift 以及 arithmetic right shift 的小技巧

在看 《Tonc: Whirlwind Tour of ARM Assembly》 的時候學到一個小技巧: 若 n 是有號 32bit 整數, 則 n>>31 相當於 n >= 0 ? 0 : -1。

看完 arithmetic shift 的定義後, 才發現我沒弄懂 arithmetic right shift, 原來是一直補進 signed bit (most significant bit), 當它是負數時, 等於一直補 1 進來。所以, -1 不管右移幾次, 結果仍是 -1, 不是 0。

將這訊息發到 G+plurk 後, 看到許多人提到 C、C++ 沒定義 signed shift 的行為, 所以用的時候要小心。jserv 提到 compiler 可以加參數改變位元運算的結果。

查看 gcc 的說明, 得知 gcc 有實作 arithmetic right shift, 但看不懂 left shift 的部份。Scott 提到這篇有解釋, 然後我明白了一件事: 關於 C99、C++0x draft 的定義, 我都看不太懂啊 ...。孩子的教育不能等, 要好好學英文。

btw, Louis 提到一個有趣的應用, ((n>>31)^n) - (n>>31) 等同於 abs(n)。拆解這個式子可得知, n 是正數時:

  • n>>31 是 0
  • n^0 仍是 n
  • n - 0 仍是 n

n 是負數時:

  • n>>31 是 -1
  • -1 以 2 補數表示為 0xFFFFFFFF
  • n^(-1) 等同於 1 補數運算
  • 最後再減 -1, 得到 2 補數運算的值

順便試著寫了以下的 C code, 再編成 assembly code, 想說看看會差多少:

int abs1(int n) {
    return n >= 0 ? n : -n;
}

int abs2(int n) {
    if (n >= 0)
        return n;
    return -n;
}

int abs3(int n) {
    return ((n>>31)^n) - (n>>31);
}

結果 abs1 和 abs3 差不多, 以下是 abs1 用 gcc 4.4.3 -O3 編後的結果:

abs1:
 pushl %ebp
 movl %esp, %ebp
 movl 8(%ebp), %eax
 popl %ebp
 movl %eax, %edx
 sarl $31, %edx
 xorl %edx, %eax
 subl %edx, %eax
 ret

gcc 偷吃步用 arithmetic right shift 避免使用 branch。不知這是針對特例的最佳化, 還是用某種神祕的機制算出來的。附帶一提, 我用不同版本的 gcc 編出來的結果不同, 用 4.5.2 最佳化編譯後, abs1 和 abs3 的結果完全一樣, 只差在用的 register 不同。

另外, 若用 ARM assembly 的話, abs() 可以寫成:

@@ 參數由 r0 傳入, 結果寫到 r0
cmp     r0, #0
sublt     r0, 0, r0

而用 arithmetic right shift 的版本則是:

eor     r1, r0, r0, asr #31
sub     r0, r1, r0, asr #31

都是兩個算數指令, 速度應該一樣吧。我沒裝 ARM 開發環境, 應該沒寫錯吧。藉機練習寫看看, 體會指令附加 branch 以及 barrel shifter 的便利之處。指令詳細說明, 見這篇的 "23.3.2. Data instructions"。"r0, asr #31" 那部份是 Op2, 可在同一 cycle 內取得 shift 後的值。

2011年10月4日 星期二

Django 的 runserver 如何實作 autoreload

做完上篇的勘查後, 好奇之下順便看一下 runserver 怎麼實作 autoreload。

看 core/management/commands/runserver.py 會看到 autoreload.main(inner_run)。然後看 utils/autoreload.py, 稍微看原始碼, 配合 pdb觀察行為, 還滿簡單的。

inner_run 是真正處理 web request 的函式, autoreload 的行為如下:

  1. 在執行 inner_run 前, 先 fork 出 child process
  2. 讓 child process 開另一個 thread
  3. parent process 等待 fork 出來的 child process 結束
  4. child process 的一個 thread 每秒掃一次所有載入的 module, 看看原始碼是否有更新。有的話, 結束這個 process, 傳回 exit code 3
  5. child process 的另一個 thread 執行 inner_run
  6. parent process 發覺 child process 的 exit code 為 3 時, 重 fork 一次, 然後回到步驟 2

要注意的是, 要用 parent process 重 fork, 而不是 child process 自己再 fork 新 process。這樣才能確保由原本乾淨的狀態重讀全部 modules (parent process fork 完就沒做事了, 確保狀態沒有一絲改變)。

偵測程式更動的程式是 code_changed(), 關鍵部份是如何找出所有相關程式:

filter(lambda v: v, map(lambda m: getattr(m, "__file__", None), sys.modules.values()))

然後將 .pyc, .pyo 改為 .py, 接著記錄所有 py 檔的上次更新時間, 留待下次呼叫此函式時比對。從這段程式可看出, 包含 site-package 或 virtualenv 裡的程式也在偵測範圍內, 還挺方便的。

小心 Django 的 ADMIN_MEDIA_PREFIX

踏到這個雷兩次了, 記錄一下。

在使用 runserver 開發程式時, runserver 會特別處理 ADMIN_MEDIA_PREFIX, 先處理 prefix 為 ADMIN_MEDIA_PREFIX 的路徑, 再將其它情況交回給原本 urls.py 裡定義的 handler。

這導致當自己的靜態檔案放在 media/ 下, 又忘了改 ADMIN_MEDIA_PREFIX 時 ( settings.py 預設為 media/), 會讀不到自己 media/ 下的檔案, 而出現 "Page not found: ..." 的錯誤訊息。

從以下兩個現象, 推測中間有人先處理掉 request:

  • browser 有送出 request 但得到 404
  • runserver 的 console 沒輸出訊息表示有收到 request 並回覆 404

所以推測有人從中做梗!!

解法很簡單, 就是將 ADMIN_MEDIA_PREFIX 隨便設一個其它名稱, 像是 "admin_media"。之前有人發 issue 請 Django 改掉 django-admin.py 的值, 不過下場是 wontfix。

相關的程式從 core/management/commands/runserver.py 找到 core/servers/basehttp.py, 然後看 AdminMediaHandler.call 的部份。

這段先看是否符合 ADMIN_MEDIA_PREFIX , 不是的話就由原本使用者寫的方式處理:

        # Ignore requests that aren't under ADMIN_MEDIA_PREFIX. Also ignore
        # all requests if ADMIN_MEDIA_PREFIX isn't a relative URL.
        if self.media_url.startswith('http://') or self.media_url.startswith('https://') \
            or not environ['PATH_INFO'].startswith(self.media_url):
            return self.application(environ, start_response)

接下來是針對 ADMIN_MEDIA_PREFIX 的特殊處理, 也只是看檔案、讀檔案而已:

        # Find the admin file and serve it up, if it exists and is readable.
        try:
            file_path = self.file_path(environ['PATH_INFO'])
        except ValueError: # Resulting file path was not valid.
            status = '404 NOT FOUND'
            headers = {'Content-type': 'text/plain'}
            output = ['Page not found: %s' % environ['PATH_INFO']]
            start_response(status, headers.items())
            return output
        if not os.path.exists(file_path):
            status = '404 NOT FOUND'
            headers = {'Content-type': 'text/plain'}
            output = ['Page not found: %s' % environ['PATH_INFO']]
        else:
            try:
                fp = open(file_path, 'rb')
            except IOError:
                status = '401 UNAUTHORIZED'
                headers = {'Content-type': 'text/plain'}
                output = ['Permission denied: %s' % environ['PATH_INFO']]
        ...

在 Fedora 下裝 id-utils

Fedora 似乎因為執行檔撞名,而沒有提供 id-utils 的套件 ,但這是使用 gj 的必要套件,只好自己編。從官網抓好 tarball ,解開來編譯 (./configure && make)就是了。 但編譯後會遇到錯誤: ./stdio.h:10...