跳到主要內容

發表文章

目前顯示的是 2013的文章

淺讀Linux root file system初始化流程

在Unix的世界中,file system佔據一個極重要的抽象化地位。其中,/ 所代表的rootfs更是所有後續新增file system所必須依賴前提條件。以Linux為例,黑客 Jserv 就曾經詳細說明過 initramfs的背後設計考量 。本篇文章不再重複背景知識,主要將追蹤rootfs初始化的流程作點整理,免得自己日後忘記。 :-) file system與特定CPU架構無關,所以我觀察的起點從init/main.c的start_kernel()開始,這是Linux作完基本CPU初始化後首先跳進的C function(我閱讀的版本為 3.12 )。跟root file system有關的流程羅列如下: start_kernel()         -> vfs_caches_init_early()         -> vfs_caches_init()                 -> mnt_init()                         -> init_rootfs()                         -> init_mount_tree()         -> rest_init()                 -> kernel_thread(kernel_init,...) 其中比較重要的是mnt_int()中的init_rootfs()與init_mout_tree()。init_rootfs()實作如下: int __init init_rootfs(void) {         int err = register_filesystem(&rootfs_fs_type);         if (err)                 return err;         if (IS_ENABLED(CONFIG_TMPFS) && !saved_root_name[0] &&                 (!root_fs_names || strstr(root_fs_names, "tmpfs"))) {          

淺讀CuRT:task, context switch與scheduling

上一篇 整理了CuRT從硬體上電後到跳入C function前所作的事情,本篇文章則會紀錄CuRT如何準備multitasking環境,以及CuRT於執行期的行為分析。 在app/shell/main.c中,我們可以看到main()的開頭為: int main() {         SerialInit();         init_interrupt_control();         init_curt(); ... SerialInit()只是把UART port初始化,方便printf()可以正常運作。init_interrupt_control()則設定pxa255的interrupt controller可以接收外部的interrupt sources,稍後啟動的timer就會發出定期的interrupt驅動scheduling。init_curt()作的事情就比較多了點,讓我們進去瞧一瞧: void init_curt() {         int i;         for (i = 0; i < MAX_PRIO; i++) {                 prio_exist_flag[i] = false;                 init_list(&ready_list[i]);         }         init_list(&delayed_list);         init_list(&blocked_list);         init_list(&termination_wait_list);         for (i = 0; i < MAX_THREAD; i++)                 thread_table[i] = NULL;         is_start_os = false;         interrupt_nesting = 0;         os_time_tick = 0;         current_top_prio = MAX_PRIO;         total_csw_cnt = 0

淺讀CuRT:啟動流程

Jserv 所寫的 CuRT 是一個非常輕量級的kernel,運行於ARMv5( PXA255 )。很適合拿來作為熟習ARM基本架構與實驗作業系統的各項技術。今天下載後,發現在我的環境(ubuntu12.04)需要作點修改才能通過編譯並正常執行,改完索性clone了一份上 github ,以利之後實驗修改。這篇文章則是為研讀此kernel所作的一系列紀錄的開頭。 千頭萬緒,從何開始呢?ARM規範其CPU reset後從0x0的位址開始執行,從PXA255的 手冊 上可知,初始的0x0落於boot ROM的範圍: 但是觀察編譯出來的curt_image.elf可以發現,其link address都以0xa0000000為base,這段位址落於SDRAM的範圍: 由於SDRAM必須要有controller控制時序,所以應該會先由boot ROM將其設定好後再搬過去執行。以上幾件事要能夠運行成功,那麼就勢必在初始時要有一段PIC的程式作relocation(或以某種方式remap address range),等等我們便可發現確實存在這樣的一段代碼。 觀察curt_image.elf的disassembly可知道,_start是.text的起頭,此符號定義於arch/arm/mach-pxa/start.S,所以我們就從這個檔案開始看起吧。:-) .text /* exception handler vector table */ _start: b reset_handler b und_handler b swi_handler b abt_pref_handler b abt_data_handler b not_used b irq_handler b fiq_handler 這邊是典型的reset vector的部份,由於除了reset_handler以外的其他mode我目前還不感興趣,所以就直接跳到reset_handler繼續看: reset_handler:  b set_misc set_misc: ... mask_off_int_reg: /* Mask off all IRQs and FIQs */ ... init_clock_reg: /* PXA250 Clo

scheduler實作技巧於FPGA驗證上的應用

在IC設計公司,有一部分的軟體工程師需要與IC設計師緊密合作,負責驗證相關硬體模組功能與驅動程式撰寫。在硬體設計初步完工階段,通常會先在FPGA上進行邏輯方面的軟體驗證,通常軟體在此時會以最簡單的方式,準備好C語言運行環境後,進行bare metal上的控制,確認無誤後,才送交後端進行timing的調整。如果是功能較為豐富的SoC,還會在FPGA上運行完整的作業系統(如Linux),確認在實際應用情況下,所有功能仍然如預期般執行。 bare metal控制的好處是環境單純。容易確認問題是在某個步驟所發生,而且執行效率極高。另一方面,運行作業系統的好處不言而喻,但缺點就是摻雜了太多額外不相干的環節,並且由於FPGA效能問題,一段時間能進行的測試次數相較於bare metal的環境往往少一個數量級以上。所以,我們有時會需要以bare metal為基礎,往上逐漸添加部份系統功能以協助驗證工作。 其中一項常見的需求就是: bare metal環境通常沒有多工能力,但我們需要確認某幾個硬體功能"同時"運作時,是否會有系統執行問題?(bus hanged, interrupt lost, hardware state錯亂...) 為了這項功能,許多人的選擇是想辦法運行完整的作業系統來確認,但在初期的環境準備與後續的除錯,都常常耗費大量不必要的精力與時間。所以有些人則是在bare metel的環境下,以各種怪招來實現不同硬體動作"同時"運行的效果,比如說在某個硬體的ISR中,去驅動另一個硬體的read/write。這種作法往往誨澀難懂,並且掛一漏萬。 其實如果只是要達成上述需求,我們可以有更乾淨的作法:一個簡單的scheduler。只需要準備: context switch task structure與其獨立的stack timer interrupt ramdom timeslot for task 而task間的同步機制通常直接開/關中斷,也就足夠了。不太需要實作完整的task state machine。也就是說,基本上只要將" 一步步寫嵌入式操作系統 "一書的最後一章的範例程式稍作修改,即可備妥以上基礎設施(大概不到200行C與assembly)。有圖有真相,以下是我在實際

Maximum Partition Number for Each MMC Block Device

今天花時間看一個客戶回報的問題,因為解決方法很簡單,但卻浪費了不少時間,所以將解決過程紀錄下來,作為警惕。:P 問題是這樣的:為什麼對 eMMC  裝置作完 partition 後(切出 3 個 primary partitions, 還有 1 個 extended partition 包含 12 個 logical partitions),只有產生 3 個 primary partitions 以及 1個 extended partition 以及 3 個 logical partitions 的 device node? 我先花了些時間研究 MBR 的格式,然後肉眼觀察 partition 後的 eMMC raw data,看起來 fdisk  與我們加進 Linux kernel 的 host controller driver 應該沒有問題 ,那問題應該就是在 Linux parsing  MBR 的過程,再花了一點時間,觀察 linux/block/partitions/check.c  ,發現會以一個 block device 的 minors 作為 partition 數量的上限 。 好了,所以問題就在於 MMC layer 在將控制權交給 block layer 之前,是如何設定這個數值的。簡單搜尋一下,發現 在這 : 70 /* 71 * The defaults come from config options but can be overriden by module 72 * or bootarg options. 73 */ 74 static int perdev_minors = CONFIG_MMC_BLOCK_MINORS ; 75 呼,真相大白,原來需要調整這個 option...,預設值為 8 ,所以最多只產出 7 個 device node給 partitions 使用。我學到的教訓是:99%的情況下,不要浪費時間懷疑已相當成熟的工具,應先花點時間觀察是否有供使用者調整的選項。 不過從另一方面想,也確實地了解一遍每個步驟以及相互之間的關係,不算損失太多。:P

C0 Scanner and Parser in Python

下雨天在家沒事作,整理書架時,翻了一下之前介紹過的 系統程式 一書,突然想到自己好一陣子沒機會寫 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。無論實作與說明都非常精彩。

Memory Barrier in Lock API

由於現今 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 ;

Side Effects of Pipeline

這幾天跟同事在實作 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 :        3a000005        bcc     effecddc <SDRM_BN_Cmp + 0x34>                  return   SDRM_DWD_Cmp ( BN_Src1 - >pData, BN_Src1 - >Length, effecdc4 :        e590000c        ldr     r0,  [ r0,  #12] effecdc8 :        e1a01003        mov     r1, r3 effecdcc :        e59e200c        ldr     r2,  [ lr,  #12] effecdd0 :        e1a0300c        mov     r3, ip effecdd4 :

Link error in MIPS with GNU ld

一個多月沒有寫 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 問題,先用安全點的作法。:-)