軟體學徒forever

這半年來在工作上負責開發一個在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核心中，存在數種記憶體配置介面，不同的配置方式有其適用之處，有時我們甚至必須在這幾種介面都不敷所需時，針對我們的應用設計專屬的配置方式，才有可能達到所需的目標。我整理了一張圖，是目前自己在考慮時的步驟：

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

glibc裡其實有實作了不少有趣的機制，我今天試著玩其中的一個小東西 - memory allocation hooks 。 我們都知道，在C語言中若需要在執行期要到一塊大小為size的記憶體需要透過malloc(size)去獲得，但是malloc之後必須在不用了以後正確釋放，否則就會有memory leak產生。用肉眼去觀察malloc/free的流程是非常辛苦的一件事，尤其當我們接手別人的程式時，要確認這件事更是困難重重。當然，有不少現成的分析工具可以使用，不過我愈來愈想知道那些工具的可能實作手法，或許必要時就可以自己做一個客制化的小工具。 在這種想法下，我在 這篇文章 發現了 memory allocation hooks(嗯...以前從來沒有仔細看過 glibc manual ，沒想到glibc的特異功能還真不少 :P)， 稍微想了一下，利用這個機制應該就可以完成一個簡易的memory leak detector，glibc對其相關介面的描述是： __malloc_hook The value of this variable is a pointer to the function that  malloc  uses whenever it is called. You should define this function to look like  malloc ; that is, like: void * function (size_t size , const void * caller ) The value of  caller  is the return address found on the stack when the  malloc  function was called. This value allows you to trace the memory consumption of the program. __free_hook The value of this variable is a pointer to function that  free  uses wh...

整理了一下Linux/glibc在user space的一些記憶體管理行為後，發現幾個有趣的現象，感覺值得紀錄一下： 1. glibc會依據malloc的block大小決定使用brk()/sbrk()或mmap()。 malloc呼叫後，glibc會根據block的大小決定是透過brk()/sbrk()或mmap()去跟kernel要記憶體，這個值可以透過mallopt(MMAP_THRESHOLD, size)去變更。我猜想這應該是為了效率問題。因為在heap中要找尋一塊足夠大的block，必須有某種查詢的方式去看目前free block是否足夠大塊，而一般程式的行為應該是以小塊block居多，所以往往會造成需要再呼叫brk()/sbrk()去要記憶體，而釋放大塊的block時，又需要再 次呼叫brk()/sbrk()(小塊block一般不需要，看2.的說明)，這樣會造成很多不必要的system call呼叫。 2. glibc透過brk()/sbrk()去擴展/縮減heap的策略類似Schmitt trigger 因為brk()/sbrk()是system call，所以一般這個開銷會比library call大一些，為了減少小尺寸的block頻繁地觸發system call，brk()/sbrk()的呼叫時機會類似Schmitt trigger的特性，也就是說，當第一次要求小block時，就會透過brk()去擴展一個較大的尺寸，以減少後續呼叫次數，然後釋放block後，會等到heap的頂端退到了一個門檻值後才再呼叫sbrk去縮減。觀察方式很容易，如下： [mars@dream tmp]$ ./a.out & [2] 2447 [mars@dream tmp]$ 0x8b8f008  [mars@dream tmp]$ cat /proc/2447/maps  08048000-08049000 r-xp 00000000 08:03 2891777    /home/mars/hobbies/tmp/a.out 08049000-0804a000 r--p 00000000 08:03 2891777    /home/mars/hobbies/...

memory poo l是實現客制化的allocator的常見手法，尤其是對快速的alloc/free有很高要求的環境。之所以可以有較快速的alloc/free，是因為memory pool的特性 - 每個pool中的基本block的大小是一樣的，而alloc時，所要求的memory也都是一個block。 怎麼利用這個特性來實作快速的alloc/free呢？以 Linux kernel為例 ，我們可以看到： 18 static void add_element ( mempool_t * pool , void * element ) 19 { 20 BUG_ON ( pool -> curr_nr >= pool -> min_nr ); 21 pool -> elements [ pool -> curr_nr ++] = element ; 22 } 23 24 static void * remove_element ( mempool_t * pool ) 25 { 26 BUG_ON ( pool -> curr_nr <= 0); 27 return pool -> elements [-- pool -> curr_nr ]; 28 } pool->elments[]是在使用者呼叫 mempool_create(...) 時所動態建立，存放的是一組void *，指向實際可被使用的memory block。當呼叫 mempool_alloc(...) 時，經過一些檢查與處理，就會呼叫到remove_element(...)，回傳指到的memory block的位址，然後將下一次要給出的block位址由pool->curr_nr去索引。很簡單又快速的便完成alloc，free則是類似的反向動作而已。 太簡單了吧？你這麼想著。沒錯，但有人寫出類似如下的實作（當然，是簡化的版本，不過意思到了 :P）： static struct block *remove_element(mempool *pool) { struct block *blk= NULL; ...

在網路上看到了有人寫了一系列講解電腦內部運作的好文章，作者為  Gustavo Duarte  ，作為一個軟體學徒，看到這麼牛的前輩花了如此多的精神整理出來的心得，實在很想推荐給大家，所以斗膽試譯一下，順便督促自己仔細地閱讀過一遍。這將會是一系列的譯文。從主機板常識、CPU cache，x86的開機過程、Linux開機過程、kernel記憶體管理、行程的address space、虛擬記憶體的管理等等，個人覺得真是一氣呵成，很是精彩啊~  OK，第1篇，講的是主機板晶片組與其memory map。 作者：  Gustavo Duarte 原文連結： http://duartes.org/gustavo/blog/post/motherboard-chipsets-memory-map 主機板晶片組與其memory map Motherboard Chipsets and the Memory Map 為了解釋現代的核心是如何工作的，我將會陸續寫幾篇文章來解釋電腦的內部運作。我希望這些文章可以讓一些 沒有太多經驗的 愛好者以及程式設計師覺得有所幫助。我們會聚焦在Linux, Windows以及Intel處理器。內部機制是我的興趣，我已經寫過一些kernel-mode的程式碼但沒有持續一直玩它。第1篇文章描述現代以Intel為基礎的主機板是如何存取記憶體以及系統記憶體的對應。 我們先來看看一個Intel電腦是怎麼接在一起的。下圖表示了主機板上的主要的元件： 現代主機板方塊圖。southbridge與northbridge構成了chipset。 如同你看到的，最要緊的是要記住CPU並不會真的知道什麼東西跟它接在一起。它透過 pin 腳跟外界相連，但它不在乎外在世界為何。外在世界可能是電腦裡的一塊主機板，但也可能是個烤麵包機、路由器、大腦植入器或者是CPU測試機台。外界與CPU溝通主要有三種方式：memory address space, I/O address space以及interrupt。我們目前只先關心主機板與memory。[譯註：環境(主機板)與溝通方式(memory)] 在主機板上，CPU的對外通道就是替它連接到northbridg...