軟體學徒forever

原文日期：2011/07/11 原文作者： Martin Fowler 原文連結： http://martinfowler.com/bliki/FrequencyReducesDifficulty.html 我最喜愛的一段話是： 如果它會造成傷害，那就多作幾次 。這句話有奇妙的美感，表面上看起來沒道理，不過當我們深入探索後，會發現一些深具價值的意義。 整合是一個很好的例子。多數程式設計師在很早就了解到，與他人整合這件工作是相當令人沮喪與痛苦的經驗。人們的反應自然是盡可能地避免它。 嘲諷的是，如果我們能夠將痛苦與整合的時間畫出關係圖的話，我們應可發現該圖會像這樣： 如果你有這樣的指數關係，然後用更高的頻率經常地去作事情，你就能夠戲劇性地減輕痛苦。(譯註：當然，每作一次事情是有代價的，需要時間、精力，所以降低每次作事情的代價，也可以讓我們更有勇氣多作幾次。)這也就是 持續整合 所關注的 - 透過每日整合，整合時的痛苦幾乎消失了。整合的確有代價，所以我們經常地執行它，於是它變得不再痛苦了。 讓痛苦的事情執行地更頻繁在敏捷開發的思想中開花結果。測試、重構、資料庫遷移、與客戶對話、規劃、發佈 - 所有這些活動都以更高的頻率在進行。 是什麼造成這樣的效應？我認為有3個明顯的理由。首先，大多數的工作會在總量變得更多時，有更高的困難度，但是當被分解成較小的工作時就會容易得多。資料庫遷移就是一個很好的例子。明確指出一個大型資料庫的相關表格是非常容易出錯的。不過如果你能夠每次改變一點點，就會更容易讓每一次更改都是正確的。另外，你也可以輕易將這些小遷移串在一起形成一個連續的過程。因此，當你將一個大型的遷移分成多次小型的動作，整件事就會變得容易許多。這也是 重構資料庫 的基本要素。 回饋是第二個理由。大部份的敏捷想法就是如何去建立回饋迴路以讓我們可以更快地學習。在極限編程中，回饋是一個明確的價值觀。在 Ken Schwaber的討論 中，這是明確的開發流程與經驗式的開發流程的最大差異之處。在一個像軟體開發這樣複雜的過程裡，你必須非常頻繁地檢視你目前位於何處並作出一連串的修正。要作到這點，你必須找尋任何可以增加回饋迴路的機會並提升頻率，這樣就能夠更快地獲取更多進行修正的回饋。 第3個理由是為了練習。對於任何活動，當我們作的更多，我們就會更進步。大...

這半年來在工作上負責開發一個在Linux核心中的記憶體管理模組，主要用來處理視訊記憶體的需求。在開發的過程閱讀了不少資料，我將其中不錯的文章整理一下，或許對剛接觸的朋友會有點幫助： Memory management reference (MMR)：這個網站非常適合新手入門記憶體管理。其中的幾篇入門文章寫得尤其好。從 overview 可以知道記憶體管理的技術範圍，從 allocation 可以知道malloc()/free()的基本實作手法與優缺點，從 recycling 則可以知道常見的garbage collection機制。 Inside memory management (IMM)：閱讀過MMR的基礎文章後，就可以從不同的角度去獨立學習。這篇文章講的是如何在Linux上實現一組最簡單的malloc()/free()。 Buddy memory allocation (BMA)：IMM這篇文章實現了簡單的記憶體配置，但馬上也面臨到嚴重的external fragmentation的問題，減緩的手法之一是透過buddy memory allocation，wikipedia上的說明非常清楚，實作的話可以參考對岸好手雲風的 設計 。 Slab allocator ：BMA的方式一定程度的減緩了external fragmentation，但卻也令小塊記憶體配置頻繁時的internal fragmentation的情況變得嚴重，解決手法很多，slab allocator試著解決這個問題，並提升了效能。實作方式可以參考 libumem 。 What every programmer should know about memory ：如果你想要深入學習記憶體管理技術，那麼從記憶體的硬體模組、計算機架構、作業系統的角度切入是不可或缺的，但是從頭閱讀數本教科書然後截取出跟記憶體相關章節有點累人，好在glibc的 維護者 寫了一篇好文章，介紹程式設計師所應該知道的基礎。 閱讀Linux source code：我是在有了前面這些基礎後，重新看Linux相關書籍與記憶體管理技術才有較深入的理解，包括MMU、page cache、hot-n-cold page、slab framework、swap...，畢竟Linux kernel hacker對很多名...

在Linux核心中，存在數種記憶體配置介面，不同的配置方式有其適用之處，有時我們甚至必須在這幾種介面都不敷所需時，針對我們的應用設計專屬的配置方式，才有可能達到所需的目標。我整理了一張圖，是目前自己在考慮時的步驟：

在Linux核心中存在數種上鎖機制，針對不同情況，我們需要清楚知道使用何種方式才能夠使得核心行為正常並且有效率。許多講解Linux device driver以及核心的書籍或文章都已經寫得很好了，這篇blog主要是為了自己方便所作的整理。 以driver撰寫者的角度，以下三種方式是最常用的： atomic_xxx()：適用於保護簡單的整數型別計數。 spin_lock/spin_unlock：在SMP的環境中，以busy waiting的方式上鎖，在UP下是空運算，CONFIG_PREEMPT開啟時，則還會進行preempt_disable()/preempt_enable()。適合用於保護短時間(少於幾個tick)的臨界區。driver撰寫者常常會使用其變形 - spin_lock_irqsave()/spin_unlock_restore()，來避免被ISR裡的程式碼中斷。在臨界區裡不能進入睡眠。 mutex：binary semaphore。適用於保護在process context下的較長臨界區存取。當無法獲取鎖時，會進入睡眠狀態。當然，一般無法在ISR中使用，如果實在需要在ISR中獲得，必須以mutex_trylock()獲得，但要作好無法獲得lock時的處理。 如果要追蹤核心或撰寫subsystem，還需注意其他可用機制： RCU(Read-Copy-Update)：共用資源大部份唯讀，少數寫入的情況。臨界區內不能睡。受保護的資源必須以pointer存取。RCU的實作者寫了不少文章介紹其原理與設計，可以參考 這邊 。 rwlock：任意數目process的讀，但只能一個寫。有semaphore與spin_lock的版本。必須確認寫只有一個。jiffies就是一例。 rt_mutex：必須開啟CONFIG_RT_MUTEX。 用來減緩priority inversion的延遲程度(採用priority inheritance的策略)。不過目前只有kernel/下有用到。原理與實作可參考LWN上的 好文章 。 使用適當的上鎖機制不只是為了行為正確，也是為了讓lock contention的程度不會嚴重影響效能。然而，要降低lock contention，往往意味著用較細的粒度去上鎖，但較細的粒度表示lock的數量會增加，使...

今天請假在家休息，複習了一下 Foundations of Computer Science 中關於Set的原理與實作。順手整理一下幾種常見的實作方式以及優缺點。 假設兩個Set的大小分別為m個元素與n個元素： unsorted list：求union、intersection、difference的需要O(m*n)，效率不好，但在很多情況下，輸入就僅是unsorted list，沒得選。算法很直覺，可參考 Foundations of Computer Science 第五章。 sorted list：當m與n很接近時，先將list排序可大幅將Set的三種基本運算降至O(n*logn)。 characteristic vector(bitmap)：當元素範圍是在某個固定範圍，並且數量不會多到不易儲存時(bitmap需要初始化，所以數量必須事先確定，不然反覆copy至更大容量的空間會非常沒效率)，用bitmap可以將Set運算降到O(m+n)。 hash table：妥善設計的hash table，可以同時獲得bitmap的效能以及sorted list的彈性，但必須將hash function以及collision的處理設計的有效率，而這需要依據應用進行實驗。 除了用到的資料結構以外，作者還逐步擴展Set的概念，為relational model奠定基礎。

原文日期：2004/03/10 原文作者：Jonathan Corbet 原文連結： http://lwn.net/Articles/75174/ 這篇文章主要是要提供一些背景知識，解釋為何在這次的開發周期中，核心開發者正在考慮從基本架構上修改虛擬記憶體的運作方式。已經了解high與low記憶體是如何在32位元系統上運作的讀者，可以略過這些說明。 一個32位元的處理器最多僅能定址4GB的記憶體。理論上，我們可以擴展指令集來允許更大的定址，但實際上沒有人這麼作，因為對於效能與可計算性的影響都太重了。所以限制依然存在：在32位元的系統上，沒有一個process可以有超過4GB的address space，核心也無法直接定址多過4GB的位址。 事實上，限制條件其實更加嚴重。Linux核心將4GB的address space分割為兩部份，在一般的設定上，32位元的前3GB分配給user space，核心則分配到從0xc0000000開始的1GB空間。共享address space有效能上的好處，硬體的address translation buffer可以被核心與user space共享。 如果核心想要直接存取系統的physical記憶體，必須先建立page table去對應進核心的address space。對於預設的3GB/1GB分割方式，可以直接定址的pyhsical記憶體就只有略小於1GB的數量 - 因為部份的核心空間必須放置核心本身、使用vmalloc()要到的記憶體以及很多其他用途。這也就是為何一直到幾年前(譯註：注意原文發佈時間在2004)，Linux都還不能完整使用32位元系統上超過1GB的記憶體。實際上，在1999年時，Linus甚至 決定 32位元的Linux不會支援超過2GB的記憶體。還嗆聲："這件事沒得談。" Linus的想法沒有改變，但世界持續對於32位元必須支援更大量記憶體有所需求。處理器供應商還增加了新的paging modes，可以讓physical addresses超過32位元的範圍，因此使得4GB的限制消失了。然而，Linux核心對於定址的限制依然沒有改變。令大型系統使用者欣慰的是，Linus承認錯誤，並改變了心意，他最終允許在2.3的核心有更大的記憶體支援。然而，這項支援有著先天上的代價與限...

講述Unix programming的好書不少，不過通常都厚度驚人，雖然閱讀實作這類書籍不會太費力氣，但我通常還是喜歡透過具體而微的小範例快速獲得大觀念(Top down)，然後再依據興趣與精力，決定如何深入細節(bottom up)。 Advanced Linux Programming (ALP)這本書就很對我的胃口。整本書共11章，前10章用很小的範例說明重要的Linux service與GNU開發環境，然後最後一章將大部分的知識以一個小型的http server來整合，跟著快速走過一遍，馬上能夠從門外漢變成看懂門道的巷內人。:-) 這篇blog主要簡單說明最後一章的http server的實作，算是為閱讀此書作個紀錄。 OK，這個http server的功能如下： 1. 可回應簡單的http GET request 2. 根據request，從模組動態產生網頁 3. 模組可以動態外掛進server 4. 同時處理多個http request 5. 此server不需superuser權限，不過有此權限可以看到更多資訊 讓我們從主程式開始看起: 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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121...