軟體學徒forever

這次參加了 PyCon 2012 ，我將個人覺得有趣的 talks 摘要如下： Day 1, 6/9 Clime: Simple CLI-ize Your Program! clime  是個可以將 python module 直接轉換成遵循 Unix 命令列程式般來操作的模組。主要原理是利用 Python 的 introspection 機制來取得模組中的 docstring ，然後再解析命令列上的選項，接著轉換成傳進模組的參數。這個創意頗有趣，可以讓註解與解析命令列的流程一致，畢竟解析命令列選項是蠻固定的步驟，是可以交由電腦執行的。但是像C語言並不支援 introspection，或許可以實作一個source-to-source translator，來為C programm作到一樣的效果。 Even faster Django 原本我對 web 開發技術完全沒有概念，但是聽完這場talk後，居然就大致上了解了整個流程與常見的最佳化技巧。當然，光用聽的沒實作經驗還是有很大的差距，但也不禁思考，網站開發在技術方面其實大多不難，重點是在創意與服務，對於我這種喜歡 system programming 的硬漢，的確需要轉換腦袋才行。:-) NLTK: Natural Language Toolkit Introduxtion and Application 這場 talk 的講者是 聚寶評 的實作者，利用自然語言處理去自動分析網路上部落客的文章，然後擷取出對我們有用的資訊。由於我的新工作要負責垃圾郵件的過濾，所以這個技術看起來很值得一試。 PySX, a playstation emulatiorin Python 這是一個 playstation emulator，總算看到一個比較接近 system programming 的議題，但卻放在閃電秀(only 5 min)...真是太可惜了...或許明年我也來試著投稿？ MMIX emulator in Python? :P

到了新公司以後，第一次參加會議時聽到大家在討論一個問題： 為何有些時候離開shell的時候，background（BG） jobs不會被終結？ 由於同事們都有更重要的事要處理，而我才剛進來幾天，還沒啥工作，就查了一下原因。發現其實理由也蠻單純的（參考 TLPI 一書的section 34.6）。首先，只有兩種情況會讓 kernel 發出 SIGHUP 給 controlling terminal ： 1.      Terminal driver 偵測到 “disconnect” 2.      GUI 的 terminal window 關閉 再依據目前的 controlling process 是否為 shell ，會有兩種可能狀況： 1.      Shell 會註冊此訊號的處理方式，並將 SIGHUP 傳給 shell 所生出的所有 process groups (jobs) 2.      若非 shell( 一般沒有攔截 SIGHUP ，則 kernel 會將 SIGHUP 送給 foreground（FG） job) ， 然後將解除 session 所相關的 terminal 從這邊可以看出來：只要放入BG，然後用不會產生 SIGHUP  的方式離開 shell ，就可保持 job 持續執行。 因為 shell 如果不是收到 SIGHUP ，而只是正常離開的話，就不會主動終結BG jobs （在bash底下，可額外透過設定huponexit選項決定正常離開時是否發送SIGHUP給非FG jobs） ，若沒有主動終結，BG  job 便自然會被 reparent 給 init 。 我作了幾個實驗，確認BG  job 的確都會活著 ( 並且被 reparent 給 init) ： 1.      開啟 GUI terminal ，執行一個 for(;;); 並推到背景 ( 用 & 的方式 ) ，然後鍵入 exit 離開。 2.   ...

Ex1:physical page management in JOS. Ans: 這題要求完成在 JOS 中對 physical pages 的管理，第一個要完成的是 bootstrap 時一開始所需要的 boot_alloc()。首先，從 Lab1 我們可以知道進入 kernel 後，physical memory 的使用狀況如下（但在entry.S中只先將[0, 4MB）對映到[KERNBASE, KERBASE+4MB),所以boot_alloc()能直接以指標存取的記憶體會受限在這個範圍）： boot_alloc()的記憶體會在後續持續被使用，但此時尚未完成 virtual memory 的設定，所以我們在 boot_alloc()必須以 page 的大小作為單位來使用，這樣才能在後續管理 page frame 時將 boot_alloc()過的記憶體正確標注狀態。實作如下： 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 43 44 45 46 47 48 49 50 51 static void * boot_alloc ( uint32_t n ) { static char * nextfree = 0 ; // virtual address of next byte of free memory static size_t used_npages = 0 ; static size_t want_npages = 0 ; char * result = NULL ; // this is defined by linker script, kern.ld, // the very beginning virtual address of kernel image extern char btext []; ex...

撰寫過 Linux driver 的程式設計師基本上都知道在實作一個硬體的 interrupt service routine (HW ISR) 時，有數個要遵守的規則，其中最重要的一點就是： 不可在 HW ISR 中呼叫任何可能引起阻擋的function。 但是為什麼有這條規則呢？原因很簡單， 因為 HW interrupt 何時觸發的時間點是未定的 ，當觸發時會在當前的 kernel stack 上執行函式，所以當 context switch 發生時，就有可能造成 回不去了 的悲劇，如下圖所示： 如果要從在 task Y 時發生的 ISR j 回去 ISR i ，勢必得獲得 task X 的 kernel stack ，但除非在 IRQ j 發生時額外紀錄是從哪個 task 過來的才行，也就是說 得在執行 iret 的同時完成一次 context switch ，這件事即使可能在硬體平台上以奇技淫巧作到，也是有問題的。因為 CPU 賦與 HW ISR 隨時可岔斷其他控制路徑的權利，其實也同時希望 HW ISR 盡可能地能夠快速返回以免耽誤原本的執行，所以若允許在 nested IRQ 發生時還進行 context switch ，那麼 HW IRQ 幾乎不可能即時完成任何任務並返回最原先的工作。 但是為何一樣是觸發 ISR，page fault 與 software interrupt 就允許可被 context switch呢？因為觸發這兩件事的時機點非常明確：只會在特定的 task 執行時發生，並且在利用到該 task 的 kernel stack 時，絕不會再次發生(若再次發生，要麼是 kernel 有 bug ，不然就是 user 傳遞了有問題的參數所引起的，後者可以修正，請參考 Understanding the Linux Kernel 的 10.4.3)。所以就可以在回復 task context 後，循著同一個 stack 的路徑返回 user mode。 結論就是，千萬不要在 HW ISR 中呼叫任何可能造成阻擋的function。 :-)

Q：在開機後，在0x10000c設breakpoint，以"x/24x %esp"觀察附近的記憶體，確認何處是stack，以及每一個非零值的意義。 Ans： 觀察到此時的暫存器與記憶體為 (gdb) info reg eax            0x0 0 ecx            0x0 0 edx            0x1f0 496 ebx            0x10074 65652 esp            0x7bbc 0x7bbc ebp            0x7bf8 0x7bf8 esi            0x0 0 edi            0x1126fc 1124092 eip            0x10000c 0x10000c eflags         0x46 [ PF ZF ] cs             0x8 8 ss             0x10 16 ds             0x10 16 es             0x10 16 fs             0x0 0 gs           ...

Ex4：複習C語言中的pointer,並確認了解pointer.c的每一個位址與現象。 Ans： Too easy to describe... :P Ex5：如果bootloader的link address設定錯誤(不是0x7c00)，第1行會出錯的指令為何？ Ans： boot/boot.S的"ljmp    $PROT_MODE_CSEG, $protcseg"，因為ljmp會將絕對位址載入。(先出現的jnz不會出錯是因為jnz是相對跳轉，透過gdb與boot.asm便可發現jnz後的相對位址都是一致的)。 Ex6：分別在BIOS進入到bootloader時與bootloader進入到kernel時觀察0x100000的前8個word，說明為何在這兩個時間點，同樣的記憶體位置的值會不同？ Ans： 因為bootloader會根據kernel image所指定的位置(ELF program header中的LMA)將kernel的每個segment載入記憶體，所以新的值是kernel image的text segment。 Ex7：追蹤JOS kernel，觀察0x100000與0xf0100000兩處的記憶體。如果mapping沒有建立正確，哪條指令會出錯？ Ans： kernel/entry.S中：         mov $relocated, %eax         jmp *%eax relocated: "jmp *%eax"會錯。因為link address定為0xf0100000，所以relocated的值為0xf01xxxxx，當mapping沒有正確設置，就會無法讓EIP正確地從0x1xxxxx跳轉到0xf01xxxxx。 Ex8：將八進制的顯示加進cprintf()中。 Ans： //in lib/printfmt.c void vprintfmt ( void   ( * putch ) ( int ,  void * ) ,  void   * putdat,  const   char   * fmt, va_...

stack 是資訊科學裡的基本概念之一，許多 精妙的演算法 依賴stack的先進後出特性來實現，而其演算法實現因為function call已經依賴於stack的機制，並且由編譯器幫我們產生相關 機器碼 ，所以往往不需在代碼中手動操作stack。 精妙的演算法將function call視為理所當然，以此為基礎往上發展遞迴算法，但除了往上看高階演算法之餘，不妨花點時間往下從機器的角度看看 function call的實現 ，理解了其實現原理後，我們就會發現，許多巧妙的系統程式機制其實都可以此為基礎開展而來： variable numbers of function parameters：透過解析stack上的參數，獲知使用者到底在參數列指定了幾個參數，然後再依序從stack上讀取參數來進行後續動作，可以參考對岸好手 李先靜 的 文章 。 backtrace：由於返回的位址與前一個stack frame的base address都可以從目前的stack frame中獲得，所以要實現backtrace就只需反覆讀取前一個stack frame所存的base address即可，可以參考我之前的 文章 。 OS bootstrap：當CPU一開機時並沒有高階語言可以執行的環境，所以只能使用assembly去實現一開始的部份。有趣的是，要如何從assembly切換到C function？基本上只要先stack frame可以正常使用，就能夠完成這項任務。然後，其他功能就繼續慢慢bootstrap~JOS或許是最容易理解的 實現 ，逐步的設定說明在 這份文檔 的appendice B。 context switch：作業系統中的多個task要進行切換才能方便實現多工與保護。而這個切換的工作概念上需要兩個步驟：scheduling(選出下一個task)以及context-switch(從目前task切換到下一個task)。在context switch中很重要的一步就是回到之前暫停的指令位址以及stack frame，所以必須從某個per-task的記憶體讀取出相關暫存器來恢復context。 ClearRTOS 的實作或許最容易理解，因為有 專書 說明。:-) coroutine：jserv的 好文章 講得非常清楚，也附上了簡易實作。 ... 很...