軟體學徒forever

原文作者： Rob Landley 原文連結： http://lxr.linux.no/linux+v3.2.1/Documentation/rbtree.txt red-black tree是什麼？它們有什麼用？ red-black tree是一種self-balancing binary search tree，用來儲存可被排序的key/value資料組合。與radix trees不同（用來有效地儲存sparse arrays，所以會用長整數的索引來安插/存取/刪除節點），也與hash tables不同（沒有保持在有序的狀態，所以無法輕易地以有序的方式巡訪，並且必須以特定的大小與hash function來微調效能，而rbtresss則可以優雅地擴展並儲存任意的key值）。 （譯註：雖然是很基本的觀念，但小弟還是要囉唆一下。資料結構的選用是因時制宜的。千萬不要以為rbtrees比上述兩種結構好，rbtrees基本上算是對各種操作最四平八穩的結構，但應用時，往往可以挑選更佳的資料結構。舉例來說，如果我們只需要安插/搜尋節點，那麼幾乎沒有什麼資料結構比hash table更合適了，複雜度只要O(1)。） red-black tree跟AVL trees很像，不過為最糟狀況下的安插與刪除提供了較佳的時間表現（個別最多兩次旋轉與三次旋轉便可讓tree恢復平衡），不過對於搜尋會有一點點的損失（不過還是保持在O(logn）)。 引用自Linux Weekly News： 在kernel中有許多red-black trees的應用。deadline與CFQ I/O排程器用rbtrees追蹤請求；ext3檔案系統使用rbtrees紀錄directory entries。Virtual memory areas (VMAs) 也是以rbtrees追蹤、epoll的檔案描述器、密碼學用的key值、以及在"階層式token bucket"的網路封包。 這份文件涵蓋Linux rbtress的使用方式。更多有關red-black tree的原理與實作資訊可參考：     Linux Weekly News上的文章     http://lwn.net/Articles/184495/     維基百科上關於red-

今天想跟大家分享一下我這陣子讀的兩本書，算是非技術類的計算機書籍。一本從歷史的角度出發，介紹黑客文化；另一本則是數位頂尖coders的訪談記錄。雖然風格與取向不同，但共通點就是 - 非常有趣。我想，應該適合所有喜歡計算機的朋友參考看看。 1. Hackers: Heroes of Computer Revolution 這本書從黑客的起源開始講起，描述了計算機領域的第一批黑客如何誕生，他們如何看待這個世界，如何進行思考，甚至往往在不經意的情況下改變了這個世界。閱讀這本書，你會看到不同類型的黑客，差距之大令人難以想像，但他們也有不少共同點，包括喜歡進入極度專心的思考狀態、喜歡了解事物最根本的運作機制、熱愛開放與自由。如果你也是覺得計算機這個東西很神奇，想要探究這個人類智慧的結晶，進而愛上程式設計，那麼這本書真的值得好好看一下。  2. Coders at Work 如果第一本書引起你的興趣，那這本Coders at Work就更不能錯過了。此書作者專訪了十幾位黑客中的黑客，每位都是公認的master，更有趣的是，作者提出了許多有趣的問題，這些問題在目前的情況來說，似乎都有不同學派提出解決方法，但我覺得要實際解決問題，往往還是要我們動手之後才真的明瞭，無論在哪個知識領域其實都是如此，但在軟體領域這點更是少數的不變定律。也因為如此，當我們有機會看到在計算機領域真的有所成就的大師們提出建言時，我認為這些智慧話語比什麼都還珍貴(當然，要經過思考後再決定是否接受其觀點)。另外，你也可以看到，即使是這些大師，他們也幾乎都還是每天不斷地寫程式呢！！相比之下，台灣不少程式設計師一天到晚想著哪天可以不用再coding，實在是...唉... :-(

作者： M. Tim Jones 原文連結： http://www.ibm.com/developerworks/linux/library/l-graphvis/ 摘要 ：你可以花時間在大量的程式碼之間穿梭進而了解function的流程，但當function pointer牽涉其中，並且程式碼非常冗長與糾纏時，這個過程會變得相當困難。本篇文章使用開放原始碼軟體以及一點膠合用的代碼，為你展示如何建立一個動態的function call圖表產生器。 透過圖形化的方式去觀察一個應用程式的呼叫流程是非常具有教育性的經驗。這麼做可以幫助你了解應用程式的內部行為以及獲取對程式進行最佳化的資訊。舉例來說，透過最佳化那些被呼叫最多次的function，你就可以用最少的力氣去得到最大的改進。除此以外，呼叫流程可以識別出使用者的function中最深度的call depth，然後你就可以為stack記憶體作適當的安排使用(在嵌入式系統中，這是一個很重要的考量)。 要獲取並顯示一幅call graph，你需要4個元素：一個GNU toolchain、addr2line程式、一些自定義的膠合代碼、以及一個叫作Graphviz的工具程式。addr2line程式讓你能夠在知道一個執行檔的某個位址後，識別出function名稱以及在源代碼中的行號。自定義的膠合代碼則是一個簡單的工具，可以將位址的追蹤流程轉變成一個圖形的規格。Graphviz則是讓你能夠產生出那些圖形。整個流程如Figure 1所示： Figure 1. 收集追蹤資訊、轉化、並產生圖形的流程 資料收集：追蹤function呼叫 要產生function呼叫的追蹤資訊，你必須知道在程式中的每個function何時被呼叫。在美好的舊時光中，你在每個function的進入點與離開點手動插入可產出獨一無二的符號。這個過程很冗長，令人生厭並且容易出錯，而且還會讓代碼變得混亂。 幸運的是，GNU toolchain(也就是gcc)提供一個為程式自動嵌入自訂function的方式。當被嵌入的程式執行時，profiling程式行為的資料就可以進行收集。你只需提供兩個特殊的此類functions。一個會在被嵌入的function被呼叫時執行；另一個則是當被嵌入的function離開時被呼叫(看Listing 1.)。

最近看了幾篇關於如何產生C function的call graph的文章，相關手法不少，我將可能有用的resource稍微作點分類整理，這幾天會進行試作： Static： 透過對source code做分析，列出function間的關係。優點：不需更改代碼、簡便、對inline function也有效。缺點：無法顯示執行期資訊，像是執行時間與次數，或recursive function或 function pointer的判斷似乎都不是很準確。 透過cscope產生出來的索引進行分析，然後繪圖，像 這篇 。 利用cflow ，列出程式碼呼叫function的樹狀圖。 Dynamic ：優點：沒有static的缺點。缺點：對inline function無效、一般不如static簡便，但都算簡易。 kcachegrind 。利用 valgrind 的基礎設施收集執行期資訊。 gprof2dot 。利用gprof的基礎設施收集執行期資訊。 利用gcc的instrumentation functions。基本運作機制可參考 jserv大俠的介紹 ，實作部份可以參考Aurelian的 proof of concept ，或參考M. Tim Jones這篇整合度更高的 文章 。 利用 gdb script 。可以避免inline function沒有被計算在內，有趣 :-) 。

原文作者： Daniel Himmelein 原文連結： http://himmele.blogspot.com/2012/01/how-do-you-read-source-code.html 如果這個世界就像Marc Andreessen與我所認為的一樣， 正在被軟體吞噬 ，你要如何[讀|吞]原始碼？ 好吧，讓我們先回答究竟為何你需要很會閱讀原始碼。首先，搞懂事物是如何運作的總是樂趣無窮，透過閱讀程式碼，我們就是對有趣的軟體系統與專案在做這件事。 另一個閱讀原始碼的理由是為了透過別人的經驗以及他們的錯誤，能夠更好地（並更快地）閱讀以及撰寫軟體。 如果你參與一個新的軟體公司或開放原始碼計畫，你很有可能要與一個既存的巨大代碼庫奮戰，所以你需要能夠很快的熟悉它，然後實作測試以及功能，或修正錯誤。 閱讀原始碼的主要目的永遠都是為了理解軟體系統的所有面貌。在這篇文章中，我提供一些閱讀時的建議與模式，這些都讓我的軟體工程師生涯輕鬆許多。 :-) 所以現在的主要問題是： 你要如何閱讀原始碼？ 在你一頭栽進一個軟體專案的原始碼之前，你必須確認你擁有足夠的相關知識以瞭解軟體的特定區塊。因此，你需要從閱讀文件開始以獲取大的概念，以及閱讀與該軟體平台/產品相關的資訊科學，或部份領域（像是Windows apps、Mac OS X、iOS apps、Android apps、作業系統、電腦網路、瀏覽器、搜尋引擎、資料庫...）。 你不需要知道該主題的所有東西，但是你 必須能夠瞭解該軟體平台/產品的核心抽象概念與基本的建構元件 。也就是說，在開始撰寫你自己的Linux排程演算法前，你應該要知道甚麼是processes、threads、semaphores等等（可參考Andrew S. Tanenbaum的 Modern Operating Systems ）。在開始之前，你也應該知道Linux特定的process管理機制（可參閱Rober Love的 Linux Kernel Development 以及Wolfgang Mauerer的 Linux Kernel Architecture ）。 不過在研究一個軟體之前，你大概就已經有這類基礎了。所以我們就從閱讀原始碼的建議與模式開始吧。 你將會注意到，對於所有的軟體系統或至少所有的大型軟體子系統都有一些基本的建構元

今天同事在處理一個陌生的模組時遇到kernel panic，Linux印出了backtrace，同事大致上可以知道是在哪個function中，但該function的長度頗長，短時間無法定位在哪個位置，在這種情況下，要如何收斂除錯範圍呢？更糟的是，由於加入printk會改變模組行為，所以printk基本上無法拿來檢查參數的值是否正常。 一般這樣的問題會backtrace的資訊來著手。從這個資訊我們可以知道在function中的多少offset發生錯誤，以x86為例(從 LDD3 借來的例子)： Unable to handle kernel NULL pointer dereference at virtual address 00000000 printing eip: d083a064 Oops: 0002 [#1] SMP CPU:    0 EIP:    0060:[<d083a064>]    Not tainted EFLAGS: 00010246   (2.6.6) EIP is at faulty_write+0x4/0x10 [faulty] eax: 00000000   ebx: 00000000   ecx: 00000000   edx: 00000000 esi: cf8b2460   edi: cf8b2480   ebp: 00000005   esp: c31c5f74 ds: 007b   es: 007b   ss: 0068 Process bash (pid: 2086, threadinfo=c31c4000 task=cfa0a6c0) Stack: c0150558 cf8b2460 080e9408 00000005 cf8b2480 00000000 cf8b2460 cf8b2460        fffffff7 080e9408 c31c4000 c0150682 cf8b2460 080e9408 00000005 cf8b2480        00000000 00000001 00000005 c0103f8f 00000001 080e9408 00000005 00000005 Call Trace:  [<c0150558>] vfs