軟體學徒forever

下雨天在家沒事作，整理書架時，翻了一下之前介紹過的 系統程式 一書，突然想到自己好一陣子沒機會寫 Python ，就試著用 Python 改寫書中所實作的 C0 語言 scanner  以及 parser。C0 是一個類似 C 的語言，但經過大幅簡化，所以很適合當作一個下午的娛樂。:-) scanner 的部份基本只用了基本的字串處理，輸出 token list 後，餵給 parser 。parser 則用簡單的 recursive descent 完成。可以從 github 上抓下來玩玩，運行結果如下： [mars@dream compiler]$ cat sample0.c0 reto = 9; reto = reto + 1; return reto; [mars@dream compiler]$ python parser.py sample0.c0 :PROG  :BASELIST   :BASE    :STATMENT     :id reto     := =     :EXP      :number 9    :; ;   :BASE    :STATMENT     :id reto     := =     :EXP      :id reto      :+ +      :number 1    :; ;   :BASE    :STATMENT     :return return     :id reto    :; ;

市面上已經出現不少教導如何撰寫小型作業系統的書籍，相關線上課程也不少，藉由研讀與實作這些寶貴知識，可以讓我們面對複雜系統時，更得心應手。在我看過的資料裡， 一步步寫嵌入式操作系統 算是最淺顯易懂，並且說理清晰的一本。 以下是各章節的簡介： 第一章：搭建工作環境 作者針對 S3C2410 晶片進行開發，這是一顆 ARM920T 的 SoC ，線上資源豐富，複雜度也不高。以 Skyeye 作為模擬器，免去實際硬體燒錄的麻煩，不過要注意某些程式碼稍嫌簡化，若在實際硬體上需再加進一些初始化動作，但並不影響整體學習。toolchain 使用目前業界慣用的 GNU toolchain 。 第二章：基礎知識 如果在學習 OS 之前，欠缺基本的 linking, loading 的觀念，並且也對基本程式開發工具不熟悉，那麼這章可以好好看一下，作者提供剛剛好夠用的說明。若需要對 linker 與 loader 的完整觀念，可以閱讀 程式設計師的自我修養 。 第三章：操作系統的啟動 這章講解 ARM 的啟動流程，以及必需的初始化設定，讀者可以從這章了解 ARM 的基本架構，尤其是 MMU 的設定部份。由於是 ARMv4 的架構，所以相比於目前最新的 ARMv7, v8 要來的簡潔很多，但主要的功能卻又相當完備，非常適合學習。 第四章：打印函數 這章教導如何實作 printf ，主要說明了 C 語言中的 variadic funtion 底層原理，如果沒 玩弄過 stack 的朋友，可以好好玩一下。:-) 第五章：中斷處理 即使是撰寫過不少 Linux driver 的朋友，可能都不曾設定過 interrupt controller，透過這章的說明，可以嘗試一下如何將 interrupt 與特定 CPU 掛鉤，並思考不同 interrupt 策略的取捨。我個人認為這章稍嫌不足的部份是說明 interrupt source 的幾種關鍵屬性，尤其是 trigger type 的選擇。有機會整理好後再發一篇 blog 說明我的想法 。 第六章：動態內存管理 對 OS 而言，記憶體管理除了 MMU 以外，另一個重點就是如何 有效動態分配 。作者在這章實作了簡易版本的 buddy system 與 slab layer。無論實作與說明都非常精彩。 ...

由於現今 CPU 與編譯器俱備各種強大的最佳化機制( speculative execution , ALU/LSU pipelines, cache...)，使得程式在執行時，並不像程式設計師在 source code level 看到那樣地循序執行。一般情況下，這不會有問題，因為 CPU 通常只會對"獨立的"指令進行重排，但是當我們是在 multi-core 的情況下，就不是這麼顯而易見了。 今天想談一個 memory barrier 的典型應用，當作是...嗯，為研讀 CPU spec 作點整理。 考慮一個情況，現在我們要設計一組 lock/unlock 的 sync API，作為 multithread 的資源同步機制。在沒有 pthread 或其他 OS system call 可用的情況下，我們要如何實現呢？ 底下是一個簡單的作法： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 struct L { volatile atomic_t flag ; }; void lock_init ( struct * L ) { L -> flag = 0 ; } void lock ( struct * L ) { while ( 1 ) { // if L->flag == 1, atomic_test_and_set does nothing and return 0 // else set it to 1 and return 1 if ( atomic_test_and_set ( L -> flag , 1 )) { break ; ...

這幾天跟同事在實作 IC 的 ROM code 時遇到一個難纏的問題，後來發現與 ARM 的 pipeline 機制有關係，問題是這樣的，看看以下的程式碼(實際上作了什麼事不重要，主要在流程)： int  SDRM_BN_Cmp ( SDRM_BIG_NUM  * BN_Src1, SDRM_BIG_NUM  * BN_Src2 ) { effecda8 :        e92d4008        push     { r3, lr } effecdac :        e1a02000        mov     r2, r0 effecdb0 :        e1a0e001        mov     lr, r1          if   ( BN_Src1 - >Length > =  BN_Src2 - >Length )   { effecdb4 :        e5903004        ldr     r3,  [ r0,  #4] effecdb8 :        e591c004        ldr     ip,  [ r1,  #4] effecdbc :        e153000c        cmp     r3, ip effecdc0 :      ...

一個多月沒有寫 blog 了...並不是沒有東西想寫，而是剛好換了新工作，並且接了幾個有時程壓力的任務，所以每天都累得跟狗一樣... :P Anyway，趁今天早點下班，將一個工作上遇到的連結問題紀錄一下，或許對某些朋友剛好有幫助。問題是這樣的，在某個使用 MIPS GNU toolchain 的環境中，原本一份可以順利編譯的 code ，今天加了一點  code 後，突然出現了連結錯誤： relocation truncated to fit: R_MIPS_GPREL16 against `no symbol' 大家似乎都第一次遇到這個錯誤，google 一陣子找不太到直接解法，但是隱約看到有人提到跟 small data section、register GP 有關，記得在 See MIPS Run 中有描述過類似的句子，翻開教科書(chapter 2)，果然提到 GP 可能會被利用來作為快速的 addressing 方式，但由於要在一個指令作完 addressing ，所以只能用到一個 32 bits 指令的 16 bits，所以如果是以 GP-relative relative addressing 方式來作 relocation ，就必須注意資料必須在 GP 的前後 32KB 的範圍。也就是說，我們有兩種解法： 檢查 toolchain 將哪些 sections 的存取或指令用了 GP-relative addressing，然後改寫 linker script 將這些 sections 與 script 中的 _gp 排近一點(在 reset.S 之類的地方通常會拿 _gp 當作 GP 的值)。 利用編譯選項 -G0，使其不要產生 small data section，而這看起來似乎就是靜態連結時的唯一一種會用的 GP-relative addressing 的 section 。  我們採用方法1，因為方法2似乎有人有遇過不少問題，為了避免又撞到這類 link error 問題，先用安全點的作法。:-)

原文作者： Eli Bendersky 原文連結： http://eli.thegreenplace.net/2012/08/13/how-statically-linked-programs-run-on-linux/   在這篇文章中，我想要探討當一個靜態連結的程式在 Linux 上執行時會發生什麼事情。靜態連結指的是一個程式執行時不需要額外的共享物件，即使是無所不在的 libc 也不需要。實際上，我們在 Linux 遇到的絕大多數程式並不是靜態連結的，需要一個或多個共享物件才能夠執行。然而，這類程式的執行流程牽涉較多細節，所以我想先說明靜態連結的程式。這可以為理解整體流程打下好的基礎，並允許我用較少的細節去討論主要的機制。我在未來會有另一篇文章來將動態連結的行程講述清楚。 Linux 核心 程式的執行起始於 Linux 核心 中。為了運行一個程式，一個行程會呼叫 exec 系列函式 其中之一。這系列的函式都非常相似，差別只在於傳入的程式的引數與環境變數。這些函數最後都會發出 sys_execve 系統呼叫 至 Linux 核心。 sys_execve 為了新程式的執行作了許多準備。要全部解釋完畢會超出這篇文章的目的 - 一本好的核心內部機制書籍對於理解這類細節會很有幫助[1]。我將會專住在對目前的討論有用的部份。 核心必須從硬碟讀取程式的可執行檔案至記憶體中並準備其執行。核心知道如何處理許多種類的二進位格式並且試著以相應的處理方式開啟檔案（這在 fs/exec.c 的  search_binary_handler 中發生）。不過，我們此處只先對 ELF 感興趣，這個格式的對應動作在函式 load_elf_binary 中（位於 fs/binfmt_elf.c）。 核心讀取程式的 ELF header，然後檢查 PT_INTERP segment 以確認是否有某個解譯器被指定。這邊就是靜態連結與動態連結開始有差異的地方。對於靜態連結的程式來說，沒有 PT_INTERP segment 。也是此篇文章要涵蓋的範圍。 核心接著根據 ELF program header 中的資訊將程式的 segments mapping 進記憶體中。最後，核心會直接修改 IP 暫存器的值為 ELF heade...

Structure and Interpretation of Computer Programs (SICP) 是非常經典的一本程式設計"入門書"。英文的資訊非常多，也有不少針對書中作業的討論（ Eli Bendersky , Scheme Community ）。由於正體中文的資訊不多，所以我想寫一篇 blog 來紀錄目前的閱讀心得，希望對還沒看過這本書的朋友（或翻過但還在觀望）有些幫助。 這本書建構了程式設計中各種設計取捨與手法的一個 mental framework。開發軟體時我們會遇到各式各樣的問題，針對不同實務問題我們有許多的慣用法去解決，但這些慣用法背後的精神卻只存於經驗豐富的老手心中，難以言表，導致一般新手不易感受。這本書講的就是作者在選擇設計手法時的系統化方式與思考轉折。 書中使用的語言是 Scheme ，雖然不是一般主流的語言，但作者刻意這麼選擇是有道理的。Scheme 的基本語法極其簡單，但抽象化的威力強大，可以在短短的幾行程式中轉換其設計典範。不同的設計典範各有其適合範疇，作者藉由實例與練習題讓我們不斷思考為什麼這樣比較好、為什麼那樣比較好、為什麼... OK~如果你好奇書中到底提了哪些資訊，以下是我目前的讀書摘要： 使用 procedure 建構抽象化。第一章講得是基本要素：基本型別與 procedure。千萬不要以為這部份跟其他語言書籍一樣無趣，這章從最基本的四則運算開始，逐漸引進 recursion的概念，而 recursion 的各式手法也逐一討論，並且在讀者熟悉用 recursion 計算簡單的數值問題後，開始將 procedure 當作 first class object ，在 procedure 間傳遞操作，引進更多設計手法。到這章結束後，我發現自己以前根本就沒善用 procedure 的能力（原因之一是常用的 C/C++ 不易用簡單的方式完成 procedure 的任意傳遞與組合）。 使用 data 建構抽象化。第一章將 procedure 與一般 data 的界線弭平了，但很多時候我們需要強化的概念是在操作的對象本身。我們會希望用簡單的方式看待複雜的 data 與其使用方式。第一章的 data 都是基本數值，雖然說電腦看到的都是數值，但對人類來說，想看到的是 picture, p...