軟體學徒forever

原文作者： Eli Bendersky 原文連結： http://eli.thegreenplace.net/2011/11/11/position-independent-code-pic-in-shared-libraries-on-x64/ 前一篇文章 解釋過與位址無關程式碼（position independent code, PIC）如何運作，並使用在 x86 上編譯過的程式作為範例。我承諾過在另一篇文章中涵蓋 x64 上的 PIC ，也就是現在這篇。既然大家都已經了解 PIC 的基本原理，這篇文章將不會牽扯太多細節。一般情況下，概念在不同平台下都是相似的，但細節會因為機器架構而有所不同。 RIP-relative 定址 在 x86 上，函式的呼叫（使用 call 指令）使用與目前指令相對位移的方式定址，資料的取用（使用 mov 指令）只支援絕對定址。既然 PIC 無可避免地需要利用 IP-relative 的定址方式，絕對位址就不容易與 PIC 同時存在，而 這也造成我們在前一篇文章看到 PIC 會比較沒有效率的原因。 x64 透過一個新的"RIP-relative 定址模式"修正了這點，這是 64 位元的 mov 指令去存去記憶體的預設模式（此模式也在其他指令中使用，像 lea ）。根據"英特爾架構手冊第二冊"中的說明：   一個新的定址模式，RIP-relative（相對於 instruction-pointer），在64 位元模式中被實作。一種有效率的方式去增加相對於指向下一個指令的 64 位元 RIP 的位移   在 RIP-relative 模式中的位移長度為 32 位元。由於正負值的位移都有需要，所以在 RIP 中的此種模式，支援的最大位移大概有最多 +/- 2GB 的位移。 在 x64 PIC 中取用資料 – 一個例子 作為一個簡單的對照，我會使用跟前篇文章同樣的 C 代碼作為取用資料的例子： int myglob = 42 ; int ml_func ( int a, int b) { return myglob + a + b; } 讓我們看看 ml_func 的反組譯：  00000000000005ec ...

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

原文日期：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的核心有更大的記憶體支援。然而，這項支援有著先天上的代價與限...

原文作者： 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/  ...

作者： 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.)。...

原文作者： 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 ）。 不過在研究一個軟體之前，你大概就已經有這類基礎了。所以我們就從閱讀原始碼的建議與模式開始吧。 你將會注意到，對於所有的軟體系統或至少所有的大型軟體子系統都有一些基本的建構元...