Linux高端內存映射(下)

非連續內存分配

非連續內存分配是指將物理地址不連續的頁框映射到線性地址連續的線性地址空間，主要應用於大容量的內存分配。采用這種方式分配內存的主要優點是避免了外部碎片，而缺點是必須打亂內核頁表，而且訪問速度較連續分配的物理頁框慢。

相關閱讀：

Linux高端內存映射(上)  http://www.linuxidc.com/Linux/2012-05/60627.htm
Linux高端內存映射(中)  http://www.linuxidc.com/Linux/2012-05/60628.htm
Linux高端內存映射(中)  http://www.linuxidc.com/Linux/2012-05/60902.htm

非連續內存分配的線性地址空間是從VMALLOC_START到VMALLOC_END(具體可以參見<<Linux高端內存映射(上)>>)，共128M，每當內核要用vmalloc類的函數進行非連續內存分配，就會申請一個vm_struct結構來描述對應的vmalloc區，兩個vmalloc區之間的間隔至少為一個頁框的大小，即PAGE_SIZE。下圖是非連續內存分配區的示意圖

所有的vm_struct都會鏈入vmlist鏈表來管理，從2.6的某個內核版本開始，為了提高效率，內核又為vmalloc區添加了vmap_area結構和vm_struct共同描述，並且引入了紅黑樹來組織這些結構，鑒於紅黑樹的復雜，為了簡化討論，把重心放在非連續內存分配的機制上，涉及到vmap_area的具體代碼不做詳細的分析。

數據結構描述

在分析具體的代碼之前，我們先了解描述vmalloc區的這兩個數據結構

1. struct vm_struct {  
2.     struct vm_struct    *next;       /*指向下一個vm區域*/  
3.     void                *addr;       /*指向第一個內存單元(線性地址)*/  
4.     unsigned long       size;        /*該塊內存區的大小*/  
5.     unsigned long       flags;       /*內存類型的標識字段*/  
6.     struct page        **pages;        /*指向頁描述符指針數組*/  
7.     unsigned int        nr_pages;    /*內存區大小對應的頁框數*/  
8.     unsigned long       phys_addr;   /*用來映射硬件設備的IO共享內存，其他情況下為0*/  
9.     void                *caller;     /*調用vmalloc類的函數的返回地址*/  
10. };  

1. struct vmap_area {  
2.     unsigned long va_start;       /*malloc區的起始地址*/  
3.     unsigned long va_end;         /*malloc區的結束地址*/  
4.     unsigned long flags;          /*類型標識*/  
5.     struct rb_node rb_node;    /* address sorted rbtree */  
6.     struct list_head list;         /* address sorted list */  
7.     struct list_head purge_list; /* "lazy purge" list */  
8.     void *private;                /*指向配對的vm_struct*/  
9.     struct rcu_head rcu_head;  
10. };