新竹碼農 (2012/9/13): From source to binary 投影片上線

很高興小的有機會再 2012/9/13 的時候在新竹碼農跟大家再度分享 Toolchain 相關的議題

這場演講 From source to binary 原本跟前輩 Jserv 於 2011/3/31 在北科大有跟大家分享過  (http://blog.linux.org.tw/~jserv/archives/2011/04/from_source_to_1.html), 不過有感於 LLVM的發展, 加上想跟在新竹的朋友們分享一下跟Toolchain 相關的議題, 所以便在議程規劃上做了一些新的調整, 把重點 focus 在 compiler 身上, 並加入最近非常流行的  LLVM 而趁著 新竹碼農 的機會跟大家分享的一場"微演講", 歡迎大家討論與指教

Hcsm lect-20120913 from lusecheng

COSCUP 2011: Porting Android to Brand-new CPU Architecture 投影片上線

很高興小的這次有機會能在 COSCUP 2011 跟大家分享 Android porting 相關的議題。

雖然對 Google 來說，能跑 Android Device 當然是越多越好，但因為話題性跟廣告性的原因，Android 的 Release cycle 其實相當短。這也造成其實 Android 每個版本只能在某個平台上跑得很好。這對同樣是以ARM為核心的SOC也是個重大的問題。不過我們把焦點放在一些"次等國民"非主流CPU上，那面對的問題就完全不一樣了。

本次演講使用一個台灣製造的非主流CPU Andes(台灣心) 來當成是參考平來，說明怎樣 Porting Android 到一些非主流的CPU上，面對效能的瓶頸，該怎麼最佳化，歡迎大家討論與指教。

Coscup2011: porting android to brand-new cpu architecture

View more presentations from lusecheng

淺談 GCC 中的 trampoline (1)

最近正好看到前輩 Jserv 的文章 GCC 的 nested function 與 trampoline 以及學長Thinker的 補充說明 後，由於這個領域也算是小弟的守備範圍，又巧逢本格乾旱已久，也好久沒有文章了，就當成是久旱逢甘霖，搭一下順風車淺談一下這個議題。這篇文章會以 GCC 的觀點來切入 trampoline ，並且提及在不同平台中支援 trampoline 的注意事項。不巧的是GCC 4.5 系列 trampoline 的 API 正好有作一些更改，把一些原本是 Macro 的 API 改成使用 Target Hook 的方式，雖然跟功能性沒有什麼太大的關係，由於小弟還沒跟上 GCC 4.5 系列，為了重現臨場感，所以本篇文章如果有使用到 GCC 的原始碼的話，是使用GCC-4.4 系列的原始碼為範例的，請讀者見諒。

Trampoline 字面的意思是體操用的彈翻床，所以就有跳(Jump)的意思存在，其實trampoline這個字在計算機科學領域是有多重意義存在的，不過大多跟跳有關就是了，trampoline詳細的定義和意義可以參考英文維基 Trampoline (computers) 條目中的內容，這邊不再贅述。而 GCC中 Trampoline 主要是用來支援一個以前在程式語言界蠻流行的功能 Nested function，而 Nested function 最主要的目的是被設計來實現 information hiding 的，information hiding 在那個年代被認為是提高軟體工程師生產力的秘密武器，而且也是廣為流行的，就把它想成現在的嵌入式程式阿宅都把灌"吸"當王道這樣就好了。或許讀者就會問說：「好好的 C 語言標準不支援，支援這種奇怪的東西幹麻？」當然除了它可以實現一些很奇特的功能像 Functional  Language 的closure 之類的東西，最重要的原因就是歷史因素，這個歷史因素也很簡單，那就是 Glibc 有用到這個功能，所以 GCC 就支援這個功能了。

如同上一段所說的，傳統上來說 Nested Function 是被設計來實現 information hiding 的，所以變數的Scope (變數的有效範圍) 是 Nested Function 中很重要的議題，就語言學來說，其實變數的Scoping 有分成 Dynamic Scoping 和 Static Scoping，用白話來說，假設每個函式有分成外圈和內圈好了，所謂的 A 比 B 還外圈就是代表 B 被允許存取 A 的資料，而 Static Scoping 的語言代表 A 跟 B 的關係在 Static Time (也就是所謂的 Compiling Time) 決定的，而 Dynamic Scoping 的語言代表 A 跟 B 的關係是在 Dynamic Time (也就是所謂的 Runtime) 決定的。舉個簡單的例子來說明，

procudure A
       procudure B
            XXXX

end

procudure C

    A()
end
   

就 Static Scoping 的語言來說 B 是 A 的內圈，可是就 Dynamic Scoping 的語言來說 A 是 C 的內圈。以實作上來說，內圈函式為了存取外圈函式的變數，內圈函式的 Stack Frame 中就必須要建一條 Link 到外圈函式的 Stack Frame 去，而連結到 Static Scope 外圈函式的 Link 稱為 Static Chain 而連結到 Dynamic  Scope 外圈函式的 Link 稱為 Dynamic  Chain 。

就學理來說，Static Typing 的語言通常會使用 Static Scope ，所以我們偉大的灌"C"哥非常靜態，所以可以想見在C語言上實作 Nested Function 也應該是屬於 Static Scoping 的 ，既然是這樣，所以我們也可以很快的想到 "這樣的系統" 是必須要有 Static Chain 的。所以 GCC 中的 trampoline 需要負責做兩件事情，就是 1.幫將被呼叫的函式產生  Static Chain，然後 2.跳轉到 被呼叫的函式去。GCC 為了減少執行時期的開銷，Static Chain 是存放在一個稱為 Static Chain Register 的暫存器內，想當然爾這個暫存器最好是 Caller-Save Register，而且每個平台會使用不同的Register。以x86 32位元的平台來說，Static Chain Register 是 ECX ，然而 x86-64 ECX已經被當成參數來使用，所以使用R10。最後附帶一提的是，由於 trampoline 的機制必須要在執行在 Stack 上的程式碼，大部分的 RISC Machine ( 因為 instruction 跟 data caches分離) 在trampoline 複製到 Stack 中的時候因為不知道他是指令，所以會產生 Memory 的值跟 Instruction Cache 中的值不一致的狀況，所以在使用這種機制時就必須要 clear instruction cache ，以避免執行到 instruction cache 中的舊指令。

使用 Chroot 來混用 Ubuntu 10.04 TLS 和 Ubuntu 8.04 LTS

Ubuntu 是個非常流行而且算是主流中的主流(?)的一種Linux發行版，也就因為是主流中的主流，所以其實 Ubuntu 中的套件裡面軟體都非常新(不過Ubuntu當一個版本Release後，通常就不會升級裡面軟體的版本主要版本了，通常只進行bugfix 和 patch number的更新)，這對很喜歡用新版的Linux使用者來說，算是一種福音。(當然，如果很喜歡用最新版而且非常想更新主要版本的使用者，通常會選擇Gentoo+使用~符號來嘗鮮)。版本新是很好，可是對軟體開發者來說，卻有個非常重大的缺點，那就是開發出來的二進制的散佈問題。

或許有的人會問：「那就用 static link 就好了阿，這樣不是一切都解決了？」姑且不提有些函式庫就是沒辦法 static link，還是某些發行版為了 license issue ，所以只提供了share 版本的函式庫 ，其實static link 並不能完全解決二進制散佈問題。聽到筆者這樣說，或許這樣大家就會問了：「static link 不是把所有的東西拉進來了嗎？而且理論上是 Self-contain 的，為什麼還是會遇到問題？」簡單的說，在編譯的時候即使使用了 static link，很清楚的地方是，其實 kernel 並沒有被拉到執行檔內，這樣的話static link的二進制檔嚴格來說是跟 kernel 有些相依性的。

什麼是跟 kernel 有些相依性，程式開發人員都知道，跟 Linux 打交道的方法就是透過 system call，linux 中的 libc (glibc, eglibc, uclibc and bionic) 就是提供了 C 語言跟 linux kernel 系統呼叫的一個橋樑，為了效能上的考量，新版的 libc 通常會使用某個版本以上的 linux kernel 才提供的 syscall，這樣會造成即使是static link的二進制，也需要在某個版本以上的Linux Kernel才能執行。以Ubuntu來說，8.04 編譯出來的檔案至少要使用2.6.8以上的Linux Kernel才能執行，而10.04卻需要2.6.18以上的Linux Kernel才能執行，這個差距足以讓那些 Red Hat Enterprise Linux AS release 4 或是 Cent OS 4.6 的工作站無法執行在Ubuntu 10.04 開發出來的二進制。

如果想要升級到 Ubuntu 10.04 LTS 卻害怕相容性問題，想要使用新版本的軟體來開發程式卻想使用 Ubuntu 8.04 LTS 來編譯程式的話，或許有人會想用使用Dual Boot，可是其實不需要那麼麻煩， chroot 就是你的救星！ 參考 Gentoo的作法 ，先將Ubuntu 8.04 安裝在某個分割區，然後使用Ubuntu 10.04 開機後，掛載 8.04 的分割區後，執行以下的程式碼 (假設 8.04 的分割區在被掛載在 /mnt )，然後再執行 chroot /mnt /bin/bash ，就能輕鬆享用 8.04 的環境。

# mount -o bind /dev /mnt/dev
# mount -o bind /dev/pts /mnt/dev/pts
# mount -o bind /dev/shm /mnt/dev/shm
# mount -o bind /proc /mnt/proc
# mount -o bind /proc/bus/usb /mnt/proc/bus/usb
# mount -o bind /sys /mnt/sys

淺談C++例外處理 (後篇)

這一篇是這個系列的完結篇了，重點放在 GCC C++ Compiler 的例外處理機制 - Dwarf2 Exception Handling。看到 "Dwarf" 這個英文單字，如果是執行檔格式有研究的人，大概會想到的東西除了龍與地下城和魔獸爭霸的矮人以外就是debug相關的東西了。沒錯，這邊Dwarf2的意思就跟大家想的那件是一樣，他是一種 "ELF" 格式中的 debugging data format，全名是 "Debug With Attributed Record Format"。會取這個名字的梗是由於"ELF"是精靈，而"Dwarf"雖然我們叫他為矮人，而他們在北歐神話中其實是一種精靈(黑暗精靈)。

例外處理的概念並不困難，只是實作卻是比想像中複雜很多，撇開C++標準規定的"拋出異常時必需要解構所有的自動變數"這個複雜的描述不談，其實對程式語言來說，想要正確的回復到那個時候的狀態，只要能取回例外處理區塊 (在 C++中為catch block) 範圍看的到的區域變數值就差不多了。然而，取回區域變數值說起來很容易，事實上卻不容易，以 C++ 這種語言來說，函式的呼叫或是程式區塊是用堆疊的觀念去處理的，更何況編譯器為了最佳化，是有可能把變數放到暫存器內的。所以可想而知編譯器會在函式的開頭和結尾都插入一些代碼來負責這些平衡堆疊這件事。用簡單的話來說，就是編譯器函式的開頭插入把堆疊指標($esp)調整好，並把有用到且該保存的暫存器壓入堆疊內，並且在離開的時候插入了恢復堆疊指標和暫存器的代碼。

我們看以下的程式碼，如果執行時期 a 呼叫了 b ，且 b 呼叫了 c 的話。

   a() call b() call c()

如果 c 函式是經由例外處理這條路徑回到了 a ( 也就是 c 拋出例外，而且 b 沒有例外處理區域，而 a 是有例外處理區域的話 )，可以而知的是 c  跟 b 結尾的程式(用編譯器的行話來說叫epilogue) 並沒有機會被呼叫到，也就是說，如果發生這樣的狀況，我們如果想要進行堆疊的回復動作 (Stack Unwinding) 就必須要經過特殊處理了。在上一篇中，我們已經談過了 GCC 的 C++ 編譯器如何使用 C 函式庫中，專門用來處理非本地跳躍的函式 Setjmp/Longjmp 來處理這個問題，而這一篇，我們將會討論GCC 的 C++ 編譯器使用的第二種處理機制，也就是利用 Dawrf2 中的 debug informantion 來處理這個問題。

那如何利用 debug informantion 來進行 Stack Unwinding 呢？簡單來說，Dawrf2 的除錯資訊當中裡面有一個欄位是專門用來提供frame相關的資訊稱為CFI (Call Frame Infomation)，編譯器當然也準備好每個函式Frame相關的操作如 push register 和 stack / frame pointer 的調整並編碼成debug informantion 存到執行檔當中。 所以當例外發生的時候，C++ Runtime Library 就能解析這個除錯資訊來了解究竟在函式開頭的時候編譯器做了些什麼事，並且把必要回復的資訊恢復回來。由於GCC 的 C++ 編譯器是使用 langauge-specific data area (LSDA) 這個欄位來儲存這部份的資料並且使用了LEB128編碼來進行壓縮。附帶一提的是，由於這種編碼方式的資料存取的時候是 Unaligned，縱使是硬體有支援 Unaligned access 還是會降低存取的效率。而且由於大部分的函式都是aligned，可是這種狀況會讓函式變成Unaligned ，如果dynmaic loader在設計的時候沒有考慮到這一點，在沒有硬體沒有支援Unaligned access 的處理器上，可能就會引發異常了。 

接下來切入實作部份，上一篇中已經將 GCC C++ Compiler 例外處理的應用程式介面(API) 和 C++程式碼中的 try, throw, catch 區塊和表示式對應的程式碼說明了一次。由於對 GCC C++ Compiler 例外處理的機制來說，使用Dwarf2 Exception Handling 來進行例外處理是不會影響大流程的，只有 Unwinding 的部分是會受到使用Setjmp/Longjmp 或Dwarf2 Exception Handling 影響。基本上來說，兩種例外處理機制並不是相容的，為了區別使用兩種例外處理機制的二進位並且讓他們可以在共用函式庫內共存，兩種機制使用的例外處理API是稍有不同的 ─ 在_Unwind開頭的API中，他們使用了名字相似但不同的函式，這個處理方式也能讓autotool之流的工具可以方便的辨認他們的編譯器是使用哪種例外處理的機制。以下為兩種機制使用的例外處理API的名稱。

Dwarf2 (Call Frame)	Setjmp/Longjmp
_Unwind_RaiseException	_Unwind_SjLj_RaiseException
_Unwind_ForcedUnwind	_Unwind_SjLj_ForcedUnwind
_Unwind_Resume	_Unwind_SjLj_Resume
_Unwind_Resume_or_Rethrow	_Unwind_SjLj_Resume_or_Rethrow

例外處理的三個關鍵字中，以 throw 的處理最複雜，也就是在throw 轉換控制權到catch區塊的時候需要進行Stack Unwind並且進行非本地的跳轉，上一篇中也提到了主要處理throw這個關鍵字語意的例外處理函式就是 _Unwind_RaiseException。其實_Unwind_RaiseException的處理方式也跟SjLj的版本差不多，有比較大差異的地方大概就是尋找handler 的方式 和 跳轉至例外處理函式的方式。基本上尋找handler是利用PC值去Unwind Table查表來尋找例外處理函式，而比較複雜的是跳轉的部分，他用了一個GCC builtin函式 __builtin_eh_return

do                                                                     
  {                                                                    
    long offset = uw_install_context_1 ((CURRENT), (TARGET));          
    void *handler = __builtin_frob_return_addr ((TARGET)->ra); 
    __builtin_eh_return (offset, handler); 
  }                                                                   
while (0)

以上的程式是_Unwind_RaiseException用來返回例外處理函式的程式碼，uw_install_context_1 是用來恢復handler的暫存器資訊並且計算 Stack Pointer 需要調整的值，第二個函式是用來取得 handler 的位址。第三部份是 __builtin_eh_return ，由於它是一個GCC平台相關的內建函式，所以每個平台的實作稍有不同。大部分平台採取的實作方式是利用一個被大部分的RTOS用來進行 Context Switch 時候技法 ─ 在Stack中更新 pushed return address ，也就是說函式返回的時候就可以自動進行跳轉，然後返回前必須修正Stack Pointer的值，這樣控制權轉移到正確的地方的時候 (某個catch block)，這時堆疊中的值也是會正確的了。

Undefine Behavior 和 GCC

有個編譯器的測試程式是這樣寫的，基本上這些測試程式會利用執行程式的回傳值來判斷編譯器是否能通過測試。換句話說，只要編譯並執行了這個測試程式而且執行程式的回傳值是0，就代表編譯器通過這個測驗，反之，就代表編譯器無法通過這個測驗。( 註: 呼叫abort將回傳1，也就是代表測試失敗。)

void f(int i)
{
  i = i > 0 ? i : -i;   if (i<0)
    return;
  abort ();
}
int main(int argc, char *argv[])
{
  f(INT_MIN);
  exit (0);
}

上述程式在進行的其實就是 abs (absolute value) 的測試，看起來如此簡單的一個程式，長的雖然如此甜美，可是卻是包藏禍心的。跟電腦上的數值表示法熟的人就會發現其實有某個數字是沒有辦法正確的做"數學上的" absolute value，也不難猜的，他就是那個整數的最小值。對整數的最小值來說，他並沒有對應的正數值，所以整數的最小值進行絕對值運算後會溢位。以在ISO C99 spec 當中，對整數的絕對值相關函式的解釋來說，這樣的行為將會是未定義的。既然是未定義的，就會取決於硬體的實作。一般而言，硬體實作絕對值時，通常會有兩種實作方式，第一種就是直接運算，也就是整數的最小時做絕對值後的結果還會是他原本的值(以32位元來說0xf0000000取補數+1還是0xf0000000)，第二種狀況在DSP比較常出現，就是硬體會幫忙做飽和運算，也就是結果會是正的最大值(0x7fffffff)。
編譯器的核心是IR(intermediate representation)，IR對一個編譯器進行最佳化時的重要程度，是可以用"IR是編譯器的生命"來形容的。 上述程式粗體表示的部分，其實出乎大部分人(?)意料之外的，如果硬體有支援ABS指令的話，大部分的主流編譯器是能產生ABS指令來最佳化這個運算式的。簡單來說，GCC 為了進行最佳化，定義了許多低階的指令範本(Instruction Pattern)，用來match C 語言所代表的運算式，當然中間還兼過了許多跟平台無關的最佳化過程(像Loop Optimization)，如果目標平台的硬體有定義abs的Instruction Pattern，GCC就會拿它來match上面那個運算式，也就是為什麼GCC能選擇性的用上abs指令來最佳化那條運算式。不過就一個未定義的行為而言，有必要去測試它的正確性嗎？
很可惜的是GCC是支援多個程式語言的前端，這個未定義的表示式在某些語言中是有定義(對，我就是在說你，Java)。JLS (Java Langauge Sepc) 中定義了有號算數運算如果有溢位的話，必須要使用2的補數表示法來 wraps around 。也就是說，在Java中，剛剛那個絕對值運算"必須"也應該要維持原本的值。GCC為了同時支援兩種不相容的Spec，所以就定義了一個編譯器選項-fwrapv來指定編譯器要不要wraps around有號運算的結果。所以上面那支測式程式還是有它存在的意義，其實編譯器在編譯這個程式時，就是要測試-fwrapv這個編譯器選項有沒有實作正確，這對一些只有 saturates 版本ABS指令的CPU/DSP/GPU造成一些困擾，也就是說當-fwrapv這個選項打開的時候，編譯器要清楚的知道不能使用abs的Instruction Pattern去match那個運算式了。

Signed不Signed還是問題所在 之 C# Remix 版

每個男人都想當慣C，可是在2009年的今天也有不少男人不想當慣C，想當慣西夏(C#)也說不定，跟C和C++比起來，C#是個純物件導向的程式語言，在Everything is object的設計前提上，這些Signed 不Signed 的問題當然使用者不是很想去沾惹，總是希望Framework能把事情處理的很好，這樣王子和公主就能過這幸福快樂的日子了。在這個那麼美好的世界當中，會不會有那些令人惱怒的轉換規則呢？在前篇中提到的C 語言中Signed Type 跟 Unsigned Type 容易造成的誤會和運算轉換的規則，在現行的純物件導向語言當中，轉換的規則、Signed Type 跟 Unsigned Type 之間的交互作用，又全然是另外一個故事了，本篇以C#為例來探討一下所謂的新世紀Signed 問題。

當然這整件事情的緣起，是在某朋友的部落閣當中，看到了一個程式。這個程式這這樣寫的。

unsigned int i=1;
int j=-1;
if(i>j) printf("i>j");
else printf(“j>i");

慣C的人看到一定馬上就看出問題所在，大聲說出：「閃開，讓專業的來」，或是「放開那女孩」，然後新警察就會出來說，依造前篇的規則，這個轉換會根據C99 Spec中的6.3.1.8的Rule 3(a)，得到 "j>i"這個慣C的人看起來很自我感覺良好，可是大家感覺卻不太好的結果。有沒有念過國小的人都知道1是比-1來得大，不過"數學是數學"，"數字要在程式中表現出來"就是會有這樣的結果，數值的表示本來就是有極限，所以才需要訂規則消除這種模糊的狀況，這個應該是程式工程師應該小心的，這是他們的責任。不過把這個看起來詭異的程式拿去C語言的後繼者，也是2000之後才出現的新世紀語言C#去做驗證，卻得到了看起來正常，卻沒有那麼正常的答案"i>j" 。

看起來正常是法理上是"i>j" 應該，"j>i"會是悲哀，可是如果仔細去想的話，這樣的結果又會令人覺得奇怪，畢竟在C#中什麼都是物件，那個運算子'=='其實會對應到某物件的成員函式，那現在 i 跟 j 的型態並不一樣，那到底是哪個比較函式會被叫起來呢？不過對程式語言稍有理解的人其實會了解，這樣的情境下你的編譯器勢必會幫你動一些手腳，如果你不懂你的編譯器幫你做了些什麼，那可能會是個災難。一個看起來合理的想法可是卻是錯誤的想法就是編譯器會幫你把unsigned int i (C# 中 uint i) 會被轉成 Signed Type，讓這個轉換看起來會得到這樣的結果，可是C#是個號稱自己是個強型態的語言，除了隱性轉換之外(所謂的隱性轉換就是設計者覺得合理的轉換(笑))，使用者是必須在程式碼顯性的說出：「我就是要這個轉換。」然而unsigned int i 轉 int 是會丟失資料的，這樣一個轉換的確不該是一個隱性轉換。會設計成這樣就是不希望使用者管這問題，如果是顯性轉換的話，其實使用者是在意了。

另外一個合理的實作是把每個基本形態的比較運算子成員函式做不同型態的比較，這樣的話unsigned int 就能正確的跟int 做相比了，不過這樣的排列組合會挺多的，所以並不是一個很好的解法。另外一個合理的轉換方式就是把unsigned int i 跟 int j 都轉成64bit int 再來進行比較，這樣就可以得到合理的結果了，事實上C#的Language Specification中是使用這種解法的，所以C#會得到"i>j"也非常正常。其實就如同其他的語言，不同型態的運算難免不了要做 promotion，只是這樣的作法就見仁見智了。最後，這部份的轉換是定義在C# Spec中的 7.2.6 中，其中的第二節Binary numeric promotions就是在這個範例程式碼當中，C#編譯器所套用的轉換規則。