Linux下的內(nèi)存管理方式

1 如何在保護(hù)模式下實(shí)現(xiàn)對(duì)物理內(nèi)存的管理
保護(hù)模式在硬件上為實(shí)現(xiàn)虛擬存儲(chǔ)創(chuàng)造了條件，但是內(nèi)存的管理還是要由軟件來(lái)做。操作系統(tǒng)作為
資源的管理者，當(dāng)然要對(duì)內(nèi)存的管理就要由他來(lái)做了。
在386 保護(hù)模式下，對(duì)任何一個(gè)物理地址的訪問(wèn)都要通過(guò)頁(yè)目錄表和頁(yè)表的映射機(jī)制來(lái)間接訪問(wèn)，
而程序提供的任何地址信息都會(huì)被當(dāng)成線性地址進(jìn)行映射，這就使得地址提供者不知道他所提供的線性
地址最后被映射到了哪個(gè)具體的物理地址單元。這樣的措施使得用戶程序不能隨意地操作物理內(nèi)存，提
高了系統(tǒng)的安全性，但是也給操作系統(tǒng)管理物理內(nèi)存造成了障礙。而操作系統(tǒng)必須要了解物理內(nèi)存的使
用情況才談得上管理。
要能夠在保護(hù)模式下感知物理內(nèi)存，也就是說(shuō)要能夠避開保護(hù)模式下線性地址的影響，直接對(duì)物理
內(nèi)存進(jìn)行操作。如何避開呢？正如前面所說(shuō)：在保護(hù)模式下對(duì)任何一個(gè)物理地址的訪問(wèn)都要通過(guò)對(duì)線性
地址的映射來(lái)實(shí)現(xiàn)。
不可能繞過(guò)這個(gè)映射機(jī)制，那只有讓他對(duì)內(nèi)核失效。如果讓內(nèi)核使用的線性地址和物理地址重合，比如：
當(dāng)內(nèi)核使用0x0000 1000 這個(gè)線性地址時(shí)訪問(wèn)到的就是物理內(nèi)存中的0x00001000 單元。問(wèn)題不就解決
了嗎！linux0.11 中采用的正是這種方法。
在進(jìn)入保護(hù)模式之前，要初始化頁(yè)目錄表和頁(yè)表，以供在切換到保護(hù)模式之后使用，要實(shí)現(xiàn)內(nèi)核線
性地址和物理地址的重合，必須要在這個(gè)時(shí)候在頁(yè)目錄表和頁(yè)表上做文章。
在看代碼之前首先說(shuō)明幾點(diǎn)：
由于linus 當(dāng)時(shí)編寫程序時(shí)使用的機(jī)器只有16M 的內(nèi)存，所以程序中也只處理了16M 物理內(nèi)存的
情況，而且只考慮了4G 線性空間的情況。一個(gè)頁(yè)表可以尋址4M 的物理空間，所以只需要4 個(gè)頁(yè)表，
一個(gè)頁(yè)目錄表可以尋址4G 的線性空間，所以只需要1 個(gè)頁(yè)目錄表。
程序?qū)㈨?yè)目錄表放在物理地址_pg_dir＝0x0000 處，4 個(gè)頁(yè)表分別放在pg0＝0x1000, pg1＝0x2000,
pg2＝0x3000, pg3＝0x4000 處
下面是最核心的幾行代碼：在linux/boot/head.s 中
首先對(duì)5 頁(yè)內(nèi)存清零
198 setup_paging:
199 movl $1024*5,%ecx /* 5 pages - pg_dir+4 page tables */
#設(shè)置填充次數(shù)ecx=1024*5
200 xorl %eax,%eax #設(shè)置填充到內(nèi)存單元中的數(shù)eax=0
201 xorl %edi,%edi /* pg_dir is at 0x000 */
#設(shè)置填充的起始地址0，也是頁(yè)目錄表的起始位置
202 cld;rep;stosl
下面填寫頁(yè)目錄表的頁(yè)目錄項(xiàng)
對(duì)于4 個(gè)頁(yè)目錄項(xiàng)，將屬性設(shè)置為用戶可讀寫，存在于物理內(nèi)存，所以頁(yè)目錄項(xiàng)的低12 位是0000 0000
0111B
以第一個(gè)頁(yè)目錄項(xiàng)為例，$ pg0+7=0x0000 1007
表示第一個(gè)頁(yè)表的物理地址是0x0000 1007&0xffff f000=0x0000 1000;
權(quán)限是0x0000 1007&0x0000 0fff=0x0000 0007
203 movl $pg0+7,_pg_dir /* set present bit/user r/w */
204 movl $pg1+7,_pg_dir+4 /* --------- " " --------- */
205 movl $pg2+7,_pg_dir+8 /* --------- " " --------- */
206 movl $pg3+7,_pg_dir+12 /* --------- " " --------- */
接著便是對(duì)頁(yè)表的設(shè)置:
4 個(gè)頁(yè)表×1024 個(gè)頁(yè)表項(xiàng)×每個(gè)頁(yè)表項(xiàng)尋址4K 物理空間：4*1024*4*1024=16M
每個(gè)頁(yè)表項(xiàng)的內(nèi)容是：當(dāng)前項(xiàng)所映射的物理內(nèi)存地址 + 該頁(yè)的權(quán)限
其中該頁(yè)的屬性仍然是用戶可讀寫，存在于物理內(nèi)存，即0x0000 0007
具體的操作是從16M 物理空間的最后一個(gè)頁(yè)面開始逆序填寫頁(yè)表項(xiàng)：
最后一個(gè)頁(yè)面的起始物理地址是0x0xfff000，加上權(quán)限位便是0x fff007,以后每減0x1000（一個(gè)頁(yè)面
的大?。┍闶窍乱粋€(gè)要填寫的頁(yè)表項(xiàng)的內(nèi)容。
207 movl $pg3+4092,%edi # edi 指向第四個(gè)頁(yè)表的最后一項(xiàng)4096-4。
208 movl $0xfff007,%eax /* 16Mb - 4096 + 7 (r/w user,p) */
#把第四個(gè)頁(yè)表的最后一項(xiàng)的內(nèi)容放進(jìn)eax
209 std # 置方向位，edi 值以4 字節(jié)的速度遞減。
210 1: stosl /* fill pages backwards - more efficient :-) */
211 subl $0x1000,%eax # 每填寫好一項(xiàng)，物理地址值減0x1000。
212 jge 1b # 如果eax 小于0 則說(shuō)明全填寫好了。
# 使頁(yè)目錄表基址寄存器cr3 指向頁(yè)目錄表。
213 xorl %eax,%eax /* pg_dir is at 0x0000 */
令eax=0x0000 0000(頁(yè)目錄表基址)
214 movl %eax,%cr3 /* cr3 - page directory start */
# 設(shè)置cr0 的PG 標(biāo)志（位31），啟動(dòng)保護(hù)模式
215 movl %cr0,%eax
216 orl $0x80000000,%eax # 添上PG 標(biāo)志位。
217 movl %eax,%cr0 /* set paging (PG) bit */
在分析完這段代碼之后，應(yīng)該對(duì)初始化后的頁(yè)目錄表和頁(yè)表有了一個(gè)大概的了解了，當(dāng)這段代
碼運(yùn)行完后內(nèi)存中的映射關(guān)系應(yīng)該如圖所示：
接下來(lái)將內(nèi)核代碼段描述符gdt 設(shè)置為
0x00c09a0000000fff /* 16Mb */ # 代碼段最大長(zhǎng)度16M。
這樣線性地址就和物理地址重合了。
下面用兩個(gè)例子驗(yàn)證一下：
（1） 要尋找pg_dir 的第15 項(xiàng)的內(nèi)容
這個(gè)地址應(yīng)該是在頁(yè)目錄表的(15-1)*4=0x38 位置，把它寫成32 為地址使0x0000 0038，當(dāng)內(nèi)
核使用這個(gè)地址時(shí)，仍然要通過(guò)映射：首先取高10 位，0000 0000 00B，根據(jù)203 行的代碼，
頁(yè)目錄表第0 項(xiàng)的內(nèi)容是$pg0+7，得到頁(yè)表地址是pg0=0x0000 1000,CPU 將用這個(gè)地址加上偏
移量找到對(duì)應(yīng)的頁(yè)表項(xiàng)，偏移量＝線性地址中間10 位*4＝0，根據(jù)203～221 行執(zhí)行的結(jié)果，
在pg0 中偏移量為0 的頁(yè)表項(xiàng)為0x0000 0007, CPU 得到頁(yè)表地址是0x0000 0000 加上線性地址
的最后12 位，將找到0x0000 0038 單元的內(nèi)容。
（2）尋找任意物理單元0x00f5 9f50
與第一個(gè)例子一樣，用這個(gè)地址作為線性地址尋址，先用高10 位尋找頁(yè)表，頁(yè)目錄表第0000
0000 11B 項(xiàng)指向pg3，根據(jù)線性地址中間10 位11 0101 1001B 尋找頁(yè)表項(xiàng)，pg3 的第11 0101
1001B 應(yīng)該是0x00f5 9007，
取得頁(yè)表基址0x00f5 9000，加上頁(yè)內(nèi)偏移量0x f50，最后得到的就是物理地址0x00f5 9f50 的
內(nèi)容。
從上面兩個(gè)例子可以看出：內(nèi)核中使用的線性地址實(shí)際上已經(jīng)是物理地址，這樣從現(xiàn)象上
看386 的地址映射機(jī)制對(duì)內(nèi)核失效了:-)
明白了這一點(diǎn)之后，對(duì)后面內(nèi)存管理方面的的分析就容易得多了
2 內(nèi)存初始化
當(dāng)操作系統(tǒng)啟動(dòng)前期實(shí)現(xiàn)對(duì)于物理內(nèi)存感知之后，接下來(lái)要做的就是對(duì)物理內(nèi)存的管理，要合理的
使用。對(duì)于Linux 這樣一個(gè)操作系統(tǒng)而言，內(nèi)存有以下一些使用：面向進(jìn)程，要分配給進(jìn)程用于執(zhí)行所必
要的內(nèi)存空間；面向文件系統(tǒng)，要為文件緩沖機(jī)制提供緩沖區(qū)，同時(shí)也要為虛擬盤機(jī)制提供必要的空
間。這三種對(duì)于內(nèi)存的使用相對(duì)獨(dú)立，要實(shí)現(xiàn)這一些，就決定了物理內(nèi)存在使用時(shí)需要進(jìn)行劃分，而最
簡(jiǎn)單的方式就是分塊，將內(nèi)存劃分為不同的塊，各個(gè)塊之間各司其職，互不干擾。linux0.11 中就是這樣
作的。
Linux0.11 將內(nèi)存分為內(nèi)核程序、高速緩沖、虛擬盤、主內(nèi)存四個(gè)部分（黑色部分是頁(yè)目錄表、幾個(gè)
頁(yè)表，全局描述符表，局部描述符表。一般將他們看作內(nèi)核的一部分）。為什么要為內(nèi)核程序單獨(dú)劃出一
個(gè)塊來(lái)呢？主要是為了實(shí)現(xiàn)上簡(jiǎn)單。操作系統(tǒng)作為整個(gè)計(jì)算機(jī)資源的管理者，內(nèi)核程序起著主要的作
用，它的代碼在操作系統(tǒng)運(yùn)行時(shí)會(huì)經(jīng)常被調(diào)用，需要常駐內(nèi)存。所以將這部分代碼與一般進(jìn)程所使用的
空間區(qū)分開，為他們專門化出一塊內(nèi)存區(qū)域。專門劃出一塊區(qū)域還有一個(gè)好處，對(duì)于內(nèi)核程序來(lái)說(shuō)， 對(duì)
于自己的的管理就簡(jiǎn)單了，內(nèi)核不用對(duì)自己代碼進(jìn)行管理。比如：當(dāng)內(nèi)核要執(zhí)行一個(gè)系統(tǒng)調(diào)用時(shí)，發(fā)現(xiàn)
相應(yīng)的代碼沒(méi)有在內(nèi)存，就必須調(diào)用相關(guān)的內(nèi)核代碼去將這個(gè)系統(tǒng)調(diào)用的代碼加載到內(nèi)存，在這個(gè)過(guò)程
中，有可能出現(xiàn)再次被調(diào)用的相關(guān)內(nèi)核代碼不在內(nèi)存中的情況，最后就可能會(huì)導(dǎo)致系統(tǒng)崩潰。操作系統(tǒng)
為了避免這種情況，在內(nèi)核的設(shè)計(jì)上就變得復(fù)雜了。如果將內(nèi)核代碼專門劃一個(gè)塊出來(lái)，將內(nèi)核代碼全
部載入這個(gè)塊保護(hù)起來(lái)，就不會(huì)出現(xiàn)上面講的情況了。
在linux0.11 中內(nèi)存管理主要是對(duì)主內(nèi)存塊的管理。
要實(shí)現(xiàn)對(duì)于這一塊的管理，內(nèi)核就必須對(duì)這一塊中的每一個(gè)物理頁(yè)面的狀態(tài)很清楚。一個(gè)物理頁(yè)面
應(yīng)該有以下基本情況：是否被分配，對(duì)于它的存取權(quán)限（可讀、可寫），是否被訪問(wèn)過(guò), 是否被寫過(guò)，被
多少個(gè)不同對(duì)象使用。對(duì)于linux0.11 來(lái)說(shuō)，后面幾個(gè)情況可以通過(guò)物理頁(yè)面的頁(yè)表項(xiàng)的D、A、XW 三項(xiàng)
得到，所以對(duì)于是否被分配，被多少個(gè)對(duì)象使用就必須要由內(nèi)核建立相關(guān)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄。在linux0.11
定義了一個(gè)字符數(shù)組mem_map [ PAGING_PAGES ] 用于對(duì)主內(nèi)存區(qū)的頁(yè)面分配和共享信息進(jìn)行記錄。
以下代碼均在/mm/memory.c 中
43 #define LOW_MEM 0x100000 // 主內(nèi)存塊可能的最低端（1MB）。
44 #define PAGING_MEMORY (15*1024*1024) // 主內(nèi)存區(qū)最多可以占用15M。
45 #define PAGING_PAGES (PAGING_MEMORY>>12) // 主內(nèi)存塊最多可以占用的物理頁(yè)面數(shù)
46 #define MAP_NR(addr) (((addr)-LOW_MEM)>>12) // 將指定物理內(nèi)存地址映射為映射數(shù)組標(biāo)號(hào)。
47 #define USED 100 // 頁(yè)面被占用標(biāo)志
57 static unsigned char mem_map [ PAGING_PAGES ] = {0,}; // 主內(nèi)存塊映射數(shù)組
mem_map 中每一項(xiàng)的內(nèi)容表示物理內(nèi)存被多少個(gè)的對(duì)象使用，所以對(duì)應(yīng)項(xiàng)為0 就表示對(duì)應(yīng)物理內(nèi)存
頁(yè)面空閑。
可以看出當(dāng)內(nèi)核在定義映射數(shù)組時(shí)是以主內(nèi)存塊最大可能大小mem_map 15M 來(lái)定義的，最低起始地
址為L(zhǎng)OW_MEM，mem_map 的第一項(xiàng)對(duì)應(yīng)于物理內(nèi)存的地址為L(zhǎng)OW_MEM，所以就有了第46 行的映射
關(guān)系MAP_NR。而當(dāng)實(shí)際運(yùn)行時(shí)主內(nèi)存塊卻不一定是這么大，這就需要根據(jù)實(shí)際主內(nèi)存塊的大小對(duì)mem
_map 的內(nèi)容進(jìn)行調(diào)整。對(duì)于不是屬于實(shí)際主內(nèi)存塊的物理內(nèi)存的對(duì)應(yīng)項(xiàng)清除掉，linux0.11 采用的做法是
在初始化時(shí)將屬于實(shí)際屬于主內(nèi)存塊的物理內(nèi)存的對(duì)應(yīng)項(xiàng)的值清零，將不屬于的置為一個(gè)相對(duì)較大的值
USED。這樣在作管理時(shí)這些不屬于主內(nèi)存塊的頁(yè)面就不會(huì)通過(guò)主內(nèi)存塊的管理程序被分配出去使用了。
下面就是主內(nèi)存塊初始化的代碼：
/init/main.c
當(dāng)系統(tǒng)初啟時(shí)，啟動(dòng)程序通過(guò)BIOS 調(diào)用將1M 以后的擴(kuò)展內(nèi)存大?。↘B）讀入到內(nèi)存0x90002 號(hào)單元
58 #define EXT_MEM_K (*(unsigned short *)0x90002)
下面是系統(tǒng)初始化函數(shù)main() 中的內(nèi)容
112 memory_end = (1<<20) + (EXT_MEM_K<<10); // 內(nèi)存大小=1Mb 字節(jié)+ 擴(kuò)展內(nèi)存(k)*1024 字節(jié)。
113 memory_end &= 0xfffff000; // 以頁(yè)面為單位取整。
114 if (memory_end > 16*1024*1024) // linux0.11 最大支持16M 物理內(nèi)存
115 memory_end = 16*1024*1024;
116 if (memory_end > 12*1024*1024) // 根據(jù)內(nèi)存大小設(shè)置緩沖區(qū)末端的位置
117 buffer_memory_end = 4*1024*1024;
118 else if (memory_end > 6*1024*1024)
119 buffer_memory_end = 2*1024*1024;
120 else
121 buffer_memory_end = 1*1024*1024;
122 main_memory_start = buffer_memory_end; // 主內(nèi)存起始位置= 緩沖區(qū)末端；
123 #ifdef RAMDISK // 如果定義了虛擬盤，重新設(shè)置主內(nèi)存塊起始位置
//rs_init() 返回虛擬盤的大小
124 main_memory_start += rd_init(main_memory_start, RAMDISK*1024);
125 #endif
126 mem_init(main_memory_start,memory_end); // 初始化主內(nèi)存塊
下面就是mem_init 的代碼。
399 void mem_init(long start_mem, long end_mem)
400 {
401 int i;
402
403 HIGH_MEMORY = end_mem; // 設(shè)置物理內(nèi)存最高端。
404 for (i=0 ; i<PAGING_PAGES ; i++) // 將主內(nèi)存塊映射數(shù)組所有項(xiàng)置為USED
405 mem_map[i] = USED;
406 i = MAP_NR(start_mem); // 計(jì)算實(shí)際主內(nèi)存塊物理地址起始位置對(duì)應(yīng)的映射項(xiàng)
407 end_mem - = start_mem; // 計(jì)算實(shí)際主內(nèi)存塊大小
408 end_mem >>= 12; // 計(jì)算需要初始化的映射項(xiàng)數(shù)目
409 while (end_mem-->0) 將實(shí)際主內(nèi)存塊對(duì)// 應(yīng)的映射項(xiàng)置為0（空閑）
410 mem_map[i++]=0;
411 }
通過(guò)以上的操作之后，操作系統(tǒng)便可以了解主內(nèi)存塊中物理內(nèi)存頁(yè)面的使用情況了。
3 內(nèi)存的分配與回收
分配
當(dāng)內(nèi)核本身或者進(jìn)程需要一頁(yè)新的物理頁(yè)面時(shí)，內(nèi)核就要給他分配一個(gè)空閑的物理頁(yè)面。內(nèi)核需要
查詢相關(guān)信息，以盡量最優(yōu)的方案分配一個(gè)空閑頁(yè)面，尤其是在有虛存管理機(jī)制的操作系統(tǒng)中對(duì)于空閑
頁(yè)面的選取方案非常重要，如果選取不當(dāng)將導(dǎo)致系統(tǒng)抖動(dòng)。linux0.11 沒(méi)有實(shí)現(xiàn)虛存管理，也就不用考慮
這些，只需要考慮如何找出一個(gè)空閑頁(yè)面。
知道了內(nèi)核對(duì)主內(nèi)存塊中空閑物理內(nèi)存頁(yè)面的映射結(jié)構(gòu)mem_map，查找空閑頁(yè)面的工作就簡(jiǎn)單了。
只需要在mem_map 找出一個(gè)空閑項(xiàng)，并將該項(xiàng)映射為對(duì)應(yīng)的物理頁(yè)面地址。算法如下：
算法：get_free_page
輸入：無(wú)
輸出：空閑頁(yè)面物理地址
{
從最后一項(xiàng)開始查找mem_map 空閑項(xiàng)；
if( 沒(méi)有空閑項(xiàng))
renturn 0；
將空閑項(xiàng)內(nèi)容置1，表示已經(jīng)被占用；
將空閑項(xiàng)對(duì)應(yīng)的下標(biāo)轉(zhuǎn)換為對(duì)應(yīng)的物理頁(yè)面的物理地址＝
( 數(shù)組下標(biāo)<<12 ＋ LOW_MEM)
將該物理頁(yè)內(nèi)容清零
return 對(duì)應(yīng)的物理地址；
}
get_free_page 的源碼如下：
/mm/memory.c
59 /*
60 * Get physical address of first (actually last :-) free page, and mark it
61 * used. If no free pages left, return 0.
62 */
/*
* 獲取首個(gè)(實(shí)際上是最后1 個(gè):-) 空閑頁(yè)面，并標(biāo)記為已使用。如果沒(méi)有空閑頁(yè)面，
* 就返回0。
*/
// 輸入：%1與%0 相同表示eax，初值為0；%2 表示直接操作數(shù)(LOW_MEM)；
%3 表示ecx，初值為PAGING PAGES；搜索次數(shù)
%4 表示edi 初值為映射數(shù)組最后一項(xiàng)地址mem_map+PAGING_PAGES-1。
// 輸出：返回%0, 表示eax 頁(yè)面起始地址。eax 即__res
63 unsigned long get_free_page(void)
64 {
65 register unsigned long __res asm( "ax");
66
67 __asm__( "std ; repne ; scasb/n/t" // 置方向位，將al(0) 與(edi) 開始的反相ecx 個(gè)字節(jié)的內(nèi)容比較
68 "jne 1f/n/t" // 如果沒(méi)有等于0 的字節(jié)，則跳轉(zhuǎn)結(jié)束（返回0）。
69 "movb $1,1(%%edi)/n/t // 將該內(nèi)存映射項(xiàng)置1。
70 "sall $12,%%ecx/n/t" 相對(duì)于// LOW_MEM 的頁(yè)面起始地址。
71 "addl %2,%%ecx/n/t" // 加上LOW_MEM ＝ > 頁(yè)面實(shí)際物理起始地址。
72 "movl %%ecx,%%edx/n/t" // 保存頁(yè)面實(shí)際物理起始地址。
73 "movl $1024,%%ecx/n/t" // 置計(jì)數(shù)值1024
74 "leal 4092(%%edx),%%edi/n/t" // 使edi 指向該物理頁(yè)末端
75 "rep ; stosl/n/t" // 沿反方向?qū)⒃擁?yè)清零。
76 "movl %%edx,%%eax/n" // 將頁(yè)面實(shí)際物理起始地址放入eax（返回值）。
77 "1:"
78 : "=a" (__res)
79 : "" (0), "i" (LOW_MEM), "c" (PAGING_PAGES),
80 "D" (mem_map+PAGING_PAGES-1)
81 : "di", "cx", "dx");
82 return __res; // 返回空閑頁(yè)面實(shí)際物理起始地址（如果無(wú)空閑也則返回0）。
83 }
84
這個(gè)函數(shù)返回的只是物理頁(yè)面的物理地址，下一節(jié)將具體講如何將物理地址映射為線性地址。
回收：
當(dāng)內(nèi)核使用完一個(gè)物理頁(yè)面或者進(jìn)程退出時(shí)內(nèi)核歸還申請(qǐng)了的物理頁(yè)面。這時(shí)就需要更改相應(yīng)的信
息，以便下一次使用。在歸還頁(yè)面時(shí)可能會(huì)出現(xiàn)下面幾種情況：
1）頁(yè)面物理地址低于主內(nèi)存塊可能的最低端，這種情況不需要處理直接退出，因?yàn)檫@部分內(nèi)存空
間被用于內(nèi)核程序和緩沖，沒(méi)有作為分配頁(yè)面的內(nèi)存空間。還有一種情況會(huì)出現(xiàn)這種情況，當(dāng)內(nèi)存操作
失敗時(shí)，會(huì)調(diào)用回收頁(yè)面過(guò)程回收已經(jīng)分配了的物理頁(yè)，如果因?yàn)閮?nèi)存分配失敗造成的，就不需要真正
的回收操作，調(diào)用回收過(guò)程時(shí)會(huì)以0 為輸入?yún)?shù)。
2）頁(yè)面物理地址高于實(shí)際物理內(nèi)存最高地址。這種情況是不允許的，內(nèi)核將使調(diào)用對(duì)象進(jìn)入死循
環(huán)，這是一種簡(jiǎn)單而有效的方法，因?yàn)檫@種情況要判斷出錯(cuò)原因是很困難的。
3）調(diào)用對(duì)象試圖釋放一塊空閑物理內(nèi)存。出現(xiàn)這種情況可能是因?yàn)槎鄠€(gè)對(duì)象共享該物理頁(yè)，在釋
放時(shí)出現(xiàn)了重復(fù)釋放。比如：進(jìn)程A、B共享物理頁(yè)170，由于系統(tǒng)的原因A將該頁(yè)釋放了兩次，當(dāng)B
釋放該頁(yè)時(shí)就會(huì)出現(xiàn)這種情況。這種情況也是不允許的，一般意味著內(nèi)核出錯(cuò)，內(nèi)核將使調(diào)用對(duì)象進(jìn)入
死循環(huán)以避免錯(cuò)誤擴(kuò)散。
4）要釋放的頁(yè)面正確。因?yàn)榭赡苁枪蚕韮?nèi)存，所以要將該頁(yè)對(duì)應(yīng)的映射項(xiàng)的值減1，表示減少了
一個(gè)引用對(duì)象。如果引用數(shù)減到0了，并不對(duì)物理頁(yè)面的內(nèi)容清0，等到被分配時(shí)再做，因?yàn)榭赡苓@個(gè)頁(yè)
面不會(huì)在被使用，同時(shí)在分配時(shí)用匯編代碼來(lái)做效率會(huì)很高。
這樣下面的代碼就很好理解了：
85 /*
86 * Free a page of memory at physical address 'addr'. Used by
87 * 'free_page_tables()'
88 */
/*
* 釋放物理地址'addr' 開始的一頁(yè)內(nèi)存。用于函數(shù)'free_page_tables()'。
*/
89 void free_page(unsigned long addr)
90 {
91 if (addr < LOW_MEM) return; 如果物理地址小于// addr 主內(nèi)存塊可能的最低端，則返回。
92 if (addr >= HIGH_MEMORY)
// 如果物理地址addr>= 實(shí)際內(nèi)存大小，則顯示出錯(cuò)信息，調(diào)用對(duì)象死機(jī)。
93 panic( "trying to free nonexistent page");
94 addr - = LOW_MEM; // 將物理地址換算為對(duì)應(yīng)的內(nèi)存映射數(shù)組下標(biāo)。
95 addr >>= 12;
96 if (mem_map[addr]--) return; // 如果對(duì)應(yīng)內(nèi)存映射數(shù)組項(xiàng)不等于0，則減1，返回
97 mem_map[addr]=0; // 否則置對(duì)應(yīng)映射項(xiàng)為0，并顯示出錯(cuò)信息，調(diào)用對(duì)象死機(jī)。
98 panic( "trying to free free page");
99 }
100

4 頁(yè)面映射
如果進(jìn)程請(qǐng)求一頁(yè)空閑內(nèi)存，或者頁(yè)失效錯(cuò)誤時(shí)，會(huì)出現(xiàn)頁(yè)面請(qǐng)求。在這個(gè)時(shí)候請(qǐng)求是以線性地址
的形式提出來(lái)的。因?yàn)閷?duì)于一個(gè)進(jìn)程來(lái)說(shuō)，它感知不到其他進(jìn)程的存在，對(duì)它自己，覺(jué)得獨(dú)占了所有資
源。操作系統(tǒng)在控制物理內(nèi)存的同時(shí)又要控制進(jìn)程的虛擬空間，這就需要在內(nèi)存線性地址與物理地址之
間作轉(zhuǎn)換工作。比如：進(jìn)程在線性地址0x0104 F380 處 產(chǎn)生了缺頁(yè)中斷，內(nèi)核將進(jìn)行一系列的處理，最
后分配一個(gè)物理頁(yè)面，但是并不能這樣返回進(jìn)程執(zhí)行，因?yàn)檫M(jìn)程仍然需要從線性地址0x0104 F380 處讀取
數(shù)據(jù)，就像沒(méi)有發(fā)生過(guò)缺頁(yè)中斷一樣。操作系統(tǒng)就必須要做這個(gè)工作，將物理頁(yè)面映射到線性地址上。
要將物理頁(yè)面映射到線性地址上，就應(yīng)該修改頁(yè)目錄表和頁(yè)表的相關(guān)內(nèi)容，這樣進(jìn)程才能通過(guò)線性
地址找到相應(yīng)的物理頁(yè)面?；仡櫼幌?86 頁(yè)面映射機(jī)制，cpu 通過(guò)線性地址的高10 位尋找到相應(yīng)的頁(yè)
表，再通過(guò)中間10 位尋找到物理頁(yè)面，最后通過(guò)低12 位在物理頁(yè)面中尋找到相應(yīng)的內(nèi)存單元。所以要
讓進(jìn)程找到物理頁(yè)面，就必須根據(jù)線性地址設(shè)置頁(yè)目錄項(xiàng)和頁(yè)表項(xiàng)。linux0.11 使用put_page 來(lái)作這個(gè)處
理，其算法如下：
算法：put_page
輸入：物理頁(yè)面地址page
線性地址address
輸出：如果成功，返回page；如果失敗，返回0
{
if ( 物理頁(yè)面地址低于LOW_MEM 或者不小于HIGH_MEMORY)
顯示出錯(cuò)信息，返回0；
if ( 物理頁(yè)面地址對(duì)應(yīng)的內(nèi)存映射數(shù)組映射項(xiàng)的值?。?1)
顯示出錯(cuò)信息，返回0；
根據(jù)線性地址高10 位找到對(duì)應(yīng)的頁(yè)目錄表項(xiàng)；
if ( 頁(yè)目錄表項(xiàng)對(duì)應(yīng)的頁(yè)表在內(nèi)存中)
根據(jù)頁(yè)目錄表項(xiàng)的到頁(yè)表的物理地址；
else{
分配新的物理頁(yè)面作為新的頁(yè)表；
初始化頁(yè)目錄表項(xiàng)，使它指向新的頁(yè)表；
根據(jù)頁(yè)目錄表項(xiàng)的到頁(yè)表的物理地址；
}
根據(jù)線性地址中間10 位找到對(duì)應(yīng)的頁(yè)表項(xiàng)；
if( 對(duì)應(yīng)的頁(yè)表項(xiàng)已經(jīng)被使用)
顯示出錯(cuò)信息，返回0；
設(shè)置對(duì)應(yīng)的頁(yè)表項(xiàng)，使它指向物理頁(yè)面；
return 物理頁(yè)面地址；
}
put_page 操縱的是由get_free_page（）分配得到的物理頁(yè)面，所以物理頁(yè)面地址應(yīng)該是在主內(nèi)存塊
中，如果不在，就應(yīng)該終止映射，返回失敗。然后調(diào)用put_page 函數(shù)的對(duì)象根據(jù)自身的特性作相關(guān)處
理。同樣是因?yàn)閜ut_page 操縱的是新分配的物理頁(yè)面，所以物理頁(yè)面地址對(duì)應(yīng)的內(nèi)存映射數(shù)組映射項(xiàng)的
值應(yīng)該是1。如果不是1，也應(yīng)該終止映射，返回失敗。如果前面的檢查通過(guò)了，就應(yīng)改進(jìn)行映射了。首
先在頁(yè)目錄表中找到對(duì)應(yīng)頁(yè)目錄項(xiàng)，如果頁(yè)目錄項(xiàng)有效，即對(duì)應(yīng)頁(yè)表在內(nèi)存中，就直接尋找頁(yè)表項(xiàng)。否
則就必須先分配一個(gè)物理頁(yè)作為頁(yè)表。從理論上講，在設(shè)置對(duì)應(yīng)的頁(yè)表項(xiàng)之前應(yīng)該檢查一下該頁(yè)表項(xiàng)是
否已經(jīng)被使用。從而確保映射的一致性，因?yàn)槿绻?yè)表項(xiàng)已經(jīng)被使用，對(duì)其的第二次賦值會(huì)使原來(lái)的映
射關(guān)系失效。但是由于linux 在總體設(shè)計(jì)上的特點(diǎn)，而且新分配的頁(yè)表被全部清零，所以不會(huì)出現(xiàn)這個(gè)問(wèn)
題。隨著對(duì)代碼分析的深入，將體會(huì)到這一點(diǎn)。
下面就是的put_page 代碼：
/mm/memory.c
190
191 /*
192 * This function puts a page in memory at the wanted address.
193 * It returns the physical address of the page gotten, 0 if
194 * out of memory (either when trying to access page-table or
195 * page.)
196 */
/*
* 下面函數(shù)將一內(nèi)存頁(yè)面放置在指定地址處。它返回頁(yè)面的物理地址，如果
* 內(nèi)存不夠(在訪問(wèn)頁(yè)表或頁(yè)面時(shí))，則返回0。
*/
197 unsigned long put_page(unsigned long page,unsigned long address)
198 {
199 unsigned long tmp, *page_table;
200
201 /* NOTE !!! This uses the fact that _pg_dir=0 */
/* 注意!!! 這里使用了頁(yè)目錄基址_pg_dir=0 的條件 */
202
203 if (page < LOW_MEM || page >= HIGH_MEMORY) // 判斷是否在主內(nèi)存塊中
204 printk( "Trying to put page %p at %p/n",page,address);
205 if (mem_map[(page-LOW_MEM)>>12] != 1) // 判斷對(duì)應(yīng)映射項(xiàng)的值是否為1
206 printk( "mem_map disagrees with %p at %p/n",page,address);
207 page_table = (unsigned long *) ((address>>20) & 0xffc); // 根據(jù)線性地址找到對(duì)應(yīng)的頁(yè)目錄表項(xiàng)；
208 if ((*page_table)&1) // 判斷頁(yè)表是否存在
209 page_table = (unsigned long *) (0xfffff000 & *page_table); // 取對(duì)應(yīng)頁(yè)表物理地址
210 else {
211 if (!(tmp=get_free_page())) // 申請(qǐng)新物理頁(yè)作為頁(yè)表
212 return 0;
213 *page_table = tmp|7; // 設(shè)置頁(yè)目錄項(xiàng)
214 page_table = (unsigned long *) tmp;
215 }
216 page_table[(address>>12) & 0x3ff] = page | 7; // 頁(yè)面設(shè)置為用戶權(quán)限、可寫、有效
217 /* no need for invalidate */
/* 不需要刷新頁(yè)變換高速緩沖 */
218 return page; // 返回物理頁(yè)面地址。
219 }
220
在這個(gè)代碼中，如果第一個(gè)判斷為真時(shí)，只是打印出錯(cuò)信息，并沒(méi)有返回。這將導(dǎo)致第二個(gè)判斷時(shí)
數(shù)組溢出，由于語(yǔ)言并不對(duì)數(shù)組溢出進(jìn)行出錯(cuò)處理。這里將可能出現(xiàn)錯(cuò)誤。而且mem_map c 第二個(gè)判斷
也沒(méi)有在打印錯(cuò)誤信息之后返回，這將導(dǎo)致錯(cuò)誤蔓延。不過(guò)幸運(yùn)的是，linux0.11 中不會(huì)以這種參數(shù)調(diào)用
put_page，所以這里只是作一個(gè)算法上的說(shuō)明。
看了put_page 之后，那么get_empty_page 的代碼就很好理解了。get_empty_page 以線性地址為參數(shù)，
申請(qǐng)新的物理頁(yè)面并完成映射過(guò)程。
/mm/memory.c
274 void get_empty_page(unsigned long address)
275 {
276 unsigned long tmp;
277
278 if (!(tmp=get_free_page()) || !put_page(tmp,address)) {
279 free_page(tmp); /* 0 is ok - ignored */
280 oom();
281 }
282 }
283
其中oom() 是用于內(nèi)存使用完后的處理，顯示完信息之后使調(diào)用進(jìn)程退出。
/mm/memory.c
33 static inline volatile void oom(void)
34 {
35 printk( "out of memory/n/r");
36 do_exit(SIGSEGV); // 進(jìn)程退出，出錯(cuò)碼：SIGSEGV（資源暫時(shí)不可用）
37 }
38

5 釋放頁(yè)表：
內(nèi)核使用了內(nèi)存，自然就會(huì)有釋放的時(shí)候。當(dāng)進(jìn)程創(chuàng)建時(shí)，需要獲得大量的內(nèi)存，也會(huì)釋放大量的
內(nèi)存空間；當(dāng)進(jìn)程退出時(shí)，肯定有大量的內(nèi)存需要釋放。而伴隨這種大量的內(nèi)存釋放工作，這些空間對(duì)
應(yīng)的頁(yè)表也會(huì)變成無(wú)用的。如果不進(jìn)行回收，將是巨大的浪費(fèi)。
內(nèi)核如果要做這種釋放（見算法free_page_tables），至少需要釋放一個(gè)頁(yè)表所映射的4M 的線性空
間，所以釋放空間起始地址應(yīng)該是以4M 為邊界的。要釋放的空間不可以是低16M 的空間。
算法：free_page_tables
輸入：要釋放空間起始線性地址from
要釋放空間大小size
輸出：如果成功，返回0；如果失敗，使調(diào)用對(duì)象進(jìn)入死循環(huán)
{
if( 要釋放的空間不是以4M 為邊界)
顯示出錯(cuò)信息，調(diào)用對(duì)象死循環(huán)；
if( 要釋放的空間是用于內(nèi)核控制物理內(nèi)存的低16M 空間)
顯示出錯(cuò)信息，調(diào)用對(duì)象死循環(huán)；
計(jì)算要釋放的空間所占的頁(yè)表數(shù)；
for( 每個(gè)要釋放的頁(yè)表){
for( 每個(gè)頁(yè)表項(xiàng))
if( 頁(yè)表項(xiàng)映射有物理頁(yè)面)
釋放物理頁(yè)面free_page()；
將該頁(yè)表項(xiàng)設(shè)為空閑；
}
釋放頁(yè)表使用的物理頁(yè)；
將該頁(yè)表對(duì)應(yīng)的頁(yè)目錄項(xiàng)設(shè)為空閑；
}
刷新頁(yè)變換高速緩沖；
return 0；
}
因?yàn)檫@個(gè)線性空間是用于內(nèi)核對(duì)物理內(nèi)存的控制，不可以被釋放。接下來(lái)要做的就很明顯了。整個(gè)操作
將導(dǎo)致頁(yè)目錄表的變化。由于cpu 為了提高內(nèi)存訪問(wèn)速度，會(huì)將頁(yè)目錄表和部分頁(yè)表加載到cpu 頁(yè)變換高
速緩存中，我們修改了頁(yè)目錄表就必須使cpu 頁(yè)變換高速緩存中的內(nèi)容同我們修改后的相同，所以必須刷
新頁(yè)變換高速緩沖。通過(guò)重新對(duì)頁(yè)目錄表寄存器cr3 賦值就可以使cpu 刷新頁(yè)變換高速緩沖。具體代碼見
下：
/mm/memory.c
39 #define invalidate() /
40 __asm__( "movl %%eax,%%cr3":: "a" (0)) // 寄存器eax 中存放0，即頁(yè)目錄表起始地址
41
101 /*
102 * This function frees a continuos block of page tables, as needed
103 * by 'exit()'. As does copy_page_tables(), this handles only 4Mb blocks.
104 */
/*
* 下面函數(shù)釋放頁(yè)表連續(xù)的內(nèi)存塊，'exit()' 需要該函數(shù)。與copy_page_tables()
* 類似，該函數(shù)僅處理4Mb 的內(nèi)存塊。
*/
105 int free_page_tables(unsigned long from,unsigned long size)
106 {
107 unsigned long *pg_table;
108 unsigned long * dir, nr;
109
110 if (from & 0x3fffff) 要釋放// 空間線性地址應(yīng)該以4M 為邊界。
111 panic( "free_page_tables called with wrong alignment");
112 if (!from) // 這里只對(duì)低4M 空間的釋放進(jìn)行限制，BUG
113 panic( "Trying to free up swapper memory space");
114 size = (size + 0x3fffff) >> 22; // 計(jì)算要釋放的頁(yè)表數(shù)
115 dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */ // 第一個(gè)要釋放頁(yè)表對(duì)應(yīng)的頁(yè)目錄項(xiàng)
116 for ( ; size-->0 ; dir++) {
117 if (!(1 & *dir)) // 該目錄項(xiàng)是否有效
118 continue;
119 pg_table = (unsigned long *) (0xfffff000 & *dir); // 計(jì)算頁(yè)表起始地址。
120 for (nr=0 ; nr<1024 ; nr++) {
121 if (1 & *pg_table) // 頁(yè)表項(xiàng)有效，則釋放對(duì)應(yīng)頁(yè)。
122 free_page(0xfffff000 & *pg_table);
123 *pg_table = 0; // 將對(duì)應(yīng)頁(yè)表項(xiàng)置為空閑
124 pg_table++;
125 }
126 free_page(0xfffff000 & *dir); // 釋放頁(yè)表使用的物理頁(yè)；
127 *dir = 0; // 將對(duì)應(yīng)頁(yè)目錄表項(xiàng)置為空閑
128 }
129 invalidate(); // 刷新頁(yè)變換高速緩沖。
130 return 0;
131 }
132
6 內(nèi)存共享
在一個(gè)系統(tǒng)中，內(nèi)存往往是最緊張的資源，為了將這種資源合理的利用，就必須搞清楚內(nèi)存是如何
被使用的，只有這樣才能進(jìn)行合理而且高效的分配。
進(jìn)程有時(shí)需要讀內(nèi)存，有時(shí)需要寫內(nèi)存，這個(gè)過(guò)程似乎是隨機(jī)的。但是對(duì)于每一個(gè)進(jìn)程來(lái)說(shuō)，有一
個(gè)段是不會(huì)被寫的，那就是代碼段。這個(gè)段的內(nèi)容由進(jìn)程的可執(zhí)行文件決定，不會(huì)改變，進(jìn)程運(yùn)行時(shí)，
也不能修改這個(gè)段的內(nèi)容。如果兩個(gè)進(jìn)程使用的是同一個(gè)可執(zhí)行文件，比如：打開兩個(gè)try.exe 文件（假
定該可執(zhí)行文件不支持多線程），這時(shí)如果讓兩個(gè)進(jìn)程在內(nèi)存中分別使用兩份代碼，將造成不必要的內(nèi)存
浪費(fèi)，所以這種情況下，內(nèi)核會(huì)讓這兩個(gè)進(jìn)程使用同一個(gè)代碼段的內(nèi)存空間。
其實(shí)數(shù)據(jù)段也是可以共享的，同樣是使用同一可執(zhí)行文件的多個(gè)進(jìn)程，他們?cè)谶M(jìn)程還沒(méi)有開始執(zhí)行
時(shí)，數(shù)據(jù)段是相同的，隨著進(jìn)程的運(yùn)行，數(shù)據(jù)段的內(nèi)容可能會(huì)被改變。內(nèi)存的訪問(wèn)具有局部性，在一段
時(shí)間內(nèi)可能不會(huì)有對(duì)數(shù)據(jù)段的某些區(qū)間修改，這個(gè)時(shí)間段可能很短，如果進(jìn)程的數(shù)據(jù)操作完全靠堆棧來(lái)
實(shí)現(xiàn)，這個(gè)時(shí)間段就可能是進(jìn)程的整個(gè)生命周期。但是如何預(yù)測(cè)進(jìn)程的數(shù)據(jù)操作是在哪里，如何預(yù)測(cè)數(shù)
據(jù)段哪些區(qū)間可以共享，哪些不行，從而安排內(nèi)存的使用？答案是否定的，對(duì)于現(xiàn)代操作系統(tǒng)而言， 這
種預(yù)測(cè)是不現(xiàn)實(shí)的，或者代價(jià)相當(dāng)大。與其花費(fèi)大量精力去做預(yù)測(cè)，為什么不采用以逸待勞的辦法呢？
先將空間共享，等到進(jìn)程對(duì)共享空間進(jìn)行寫操作時(shí)再取消對(duì)該頁(yè)的共享。liunx 采用了一種稱為寫時(shí)復(fù)制
(copy on write) 的機(jī)制。這種機(jī)制必須要有硬件的支持，在386 頁(yè)面映射機(jī)制中，有一個(gè)讀寫權(quán)限標(biāo)志位
XW，將這一位設(shè)為只讀（0）方式
之后，如果進(jìn)程試圖對(duì)該頁(yè)進(jìn)行寫操
作，cpu 將出現(xiàn)頁(yè)面異常中斷，調(diào)用
內(nèi)核設(shè)定的頁(yè)面異常中斷處理程序，在這里內(nèi)核將原來(lái)的頁(yè)面復(fù)制一份，再取消對(duì)該頁(yè)面的共享，這樣
就互不干擾了。有了這個(gè)保障，內(nèi)核在進(jìn)行內(nèi)存共享操作時(shí)就可以放心了。
當(dāng)內(nèi)核使用fork 創(chuàng)建一個(gè)進(jìn)程時(shí)，子進(jìn)程將使用和父進(jìn)程的同樣代碼段和數(shù)據(jù)段，然后根據(jù)fork 返
回的不同的值作為判斷，運(yùn)行不同的代碼。見示例程序：
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
void main(){
int childpid.data=100;
childpid=fork();
if(childpid==0){
printf("I'm child!/n");
printf("My father have a data ,it's %d!/n",data);
exit(0);
}
printf("I'm father!I have a child %d/n",childpid);
exit(0);
}
創(chuàng)建一個(gè)進(jìn)程后，父進(jìn)程和子進(jìn)程使用同樣的代碼。但是他們中childpid 的值不同，如果是子進(jìn)
程，childpid 的值是0；如果是父進(jìn)程，childpid 的值是子進(jìn)程的進(jìn)程號(hào)。在這以后，子進(jìn)程可能會(huì)使用父
進(jìn)程中的一些數(shù)據(jù)。如果子進(jìn)程不調(diào)用另一個(gè)可執(zhí)行文件作為其執(zhí)行代碼，子進(jìn)程將一直使用父進(jìn)程的
代碼。

6.1 共享空間
有了386 對(duì)頁(yè)面共享的支持，共享空間的方法就很容易想到了。將被共享的空間的頁(yè)目錄表和頁(yè)表復(fù)
制一份，并且將所有頁(yè)表項(xiàng)的訪問(wèn)屬性設(shè)為只讀，并修改頁(yè)面映射表中的頁(yè)面引用信息即可。具體算法
如下：
算法：copy_page_tables
輸入：共享源頁(yè)面起始地址from
共享目的空間頁(yè)面起始地址to
被共享空間的大小size
輸出：如果成功，返回0
{
if(from 或者to 不是以4M 為邊界)
顯示出錯(cuò)信息，使調(diào)用對(duì)象進(jìn)入死循環(huán)；
for( 共享源空間的每一個(gè)頁(yè)目錄項(xiàng)){
if( 對(duì)應(yīng)共享目的空間的頁(yè)表已經(jīng)存在)
顯示出錯(cuò)信息，死循環(huán)；
if( 共享源空間的頁(yè)目錄項(xiàng)不存在)
continue；
為對(duì)應(yīng)共享目的空間分配空閑頁(yè)作為頁(yè)表；
設(shè)置該空閑頁(yè)屬性（可寫、用戶、有效）
if( 共享源空間本次復(fù)制的是前4M 的內(nèi)核空間)
本次共享空間只是前640K；
for( 每個(gè)要共享空間的頁(yè)表項(xiàng)){
復(fù)制頁(yè)表項(xiàng)；
if( 對(duì)應(yīng)頁(yè)不存在)
continue；
if( 被共享頁(yè)在主內(nèi)存塊映射表映射范圍內(nèi) ){
將兩個(gè)頁(yè)表項(xiàng)都置為只讀；
對(duì)應(yīng)頁(yè)面映射項(xiàng)內(nèi)容加1；
}
else
只將復(fù)制的頁(yè)表項(xiàng)置為只讀；
}
}
刷新頁(yè)變換高速緩沖；
}
對(duì)于帶有頁(yè)表復(fù)制，和帶有頁(yè)表的釋放一樣，必須保證被共享的空間和被共享到的空間起始地址是
以4M 為邊界的；每次共享4M 的空間，像以前一樣，對(duì)于內(nèi)核空間必須作特殊處理。640K 到1M 的空
間本來(lái)是高速緩沖塊的空間，但是被顯存和BIOS 占用了，所以這部分空間是不共享的；因?yàn)閘inus 當(dāng)初
使用的計(jì)算機(jī)有16M 的內(nèi)存，高速緩沖空間結(jié)束位置是4M（見啟動(dòng)后內(nèi)存分配），所以可能是由于這個(gè)
原因，1M 到3,071K 這個(gè)空間也是不共享的，對(duì)高速緩沖共享是沒(méi)有意義的，這樣內(nèi)核的前4M 空間就
只共享640K。如果被共享頁(yè)不在主內(nèi)存塊映射表范圍內(nèi)，共享的就是這640K 的空間，是內(nèi)核使用的，
在共享時(shí)，源頁(yè)表項(xiàng)不被置為只讀。
/mm/memory.c
132
133 /*
134 * Well, here is one of the most complicated functions in mm. It
135 * copies a range of linerar addresses by copying only the pages.
136 * Let's hope this is bug-free, 'cause this one I don't want to debug :-)
137 *
138 * Note! We don't copy just any chunks of memory - addresses have to
139 * be divisible by 4Mb (one page-directory entry), as this makes the
140 * function easier. It's used only by fork anyway.
141 *
142 * NOTE 2!! When from==0 we are copying kernel space for the first
143 * fork(). Then we DONT want to copy a full page-directory entry, as
144 * that would lead to some serious memory waste - we just copy the
145 * first 160 pages - 640kB. Even that is more than we need, but it
146 * doesn't take any more memory - we don't copy-on-write in the low
147 * 1 Mb-range, so the pages can be shared with the kernel. Thus the
148 * special case for nr=xxxx.
149 */
/*
好了，下面是內(nèi)存管理中最為復(fù)雜的程序之* mm 一。它通過(guò)只復(fù)制內(nèi)存頁(yè)面
* 來(lái)拷貝一定范圍內(nèi)線性地址中的內(nèi)容。希望代碼中沒(méi)有錯(cuò)誤，因?yàn)槲也幌?br />* 再調(diào)試這塊代碼了.。
*
* 注意！我們并不是僅復(fù)制任何內(nèi)存塊 - 內(nèi)存塊的地址需要是4Mb 的倍數(shù)（正好
* 一個(gè)頁(yè)目錄項(xiàng)對(duì)應(yīng)的內(nèi)存大?。?yàn)檫@樣處理可使函數(shù)很簡(jiǎn)單。不管怎樣，
* 它僅被fork() 使用（fork.c 第56 行）。
*
* 注意2?。‘?dāng)from==0 時(shí)，是在為第一次fork() 調(diào)用復(fù)制內(nèi)核空間。此時(shí)我們
* 不想復(fù)制整個(gè)頁(yè)目錄項(xiàng)對(duì)應(yīng)的內(nèi)存，因?yàn)檫@樣做會(huì)導(dǎo)致內(nèi)存嚴(yán)重的浪費(fèi) - 我們
* 只復(fù)制頭160 個(gè)頁(yè)面 - 對(duì)應(yīng)640kB。即使是復(fù)制這些頁(yè)面也已經(jīng)超出我們的需求，
* 但這不會(huì)占用更多的內(nèi)存 - 在低1Mb 內(nèi)存范圍內(nèi)我們不執(zhí)行寫時(shí)復(fù)制操作，所以
* 這些頁(yè)面可以與內(nèi)核共享。因此這是nr=xxxx 的特殊情況（nr 在程序中指頁(yè)面數(shù)）。
*/
150 int copy_page_tables(unsigned long from,unsigned long to,long size)
151 {
152 unsigned long * from_page_table;
153 unsigned long * to_page_table;
154 unsigned long this_page;
155 unsigned long * from_dir, * to_dir;
156 unsigned long nr;
157
158 if ((from&0x3fffff) || (to&0x3fffff)) // 判斷是否以4M 為邊界
159 panic( "copy_page_tables called with wrong alignment");
160 from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */ 計(jì)// 算起始頁(yè)目錄項(xiàng)
161 to_dir = (unsigned long *) ((to>>20) & 0xffc);
162 size = ((unsigned) (size+0x3fffff)) >> 22; // 計(jì)算要共享的頁(yè)表數(shù)
163 for( ; size-->0 ; from_dir++,to_dir++) {
164 if (1 & *to_dir) // 被共享到的頁(yè)表已經(jīng)存在
165 panic( "copy_page_tables: already exist");
166 if (!(1 & *from_dir)) // 被共享的頁(yè)表不存在
167 continue;
168 from_page_table = (unsigned long *) (0xfffff000 & *from_dir); // 取源頁(yè)表地址
169 if (!(to_page_table = (unsigned long *) get_free_page()))
170 return -1; /* Out of memory, see freeing */
171 *to_dir = ((unsigned long) to_page_table) | 7; // 設(shè)置該頁(yè)屬性（可寫、用戶、有效）
172 nr = (from==0)?0xA0:1024; // 如果是前4M 空間，只共享640K(160 頁(yè))
173 for ( ; nr-- > 0 ; from_page_table++,to_page_table++) {
174 this_page = *from_page_table;
175 if (!(1 & this_page)) // 如果當(dāng)前源頁(yè)表項(xiàng)沒(méi)有使用，則不用復(fù)制
176 continue;
177 this_page &= ~2; // 將目的頁(yè)表項(xiàng)設(shè)為只讀
178 *to_page_table = this_page;
179 if (this_page > LOW_MEM) { // 如果被共享頁(yè)在主內(nèi)存塊映射表映射范圍內(nèi)
180 *from_page_table = this_page; // 源頁(yè)表項(xiàng)設(shè)為只讀
181 this_page -= LOW_MEM;
182 this_page >>= 12;
183 mem_map[this_page]++; // 共享數(shù)加一
184 }
185 }
186 }
187 invalidate(); // 刷新頁(yè)變換高速緩沖。
188 return 0;
189 }
190
6.2 共享進(jìn)程空間
6.2.1 早期共享
當(dāng)內(nèi)核使用fork 創(chuàng)建一個(gè)進(jìn)程時(shí)，子進(jìn)程將使用和父進(jìn)程的進(jìn)程空間進(jìn)行完全的拷貝。子進(jìn)程除了
要與父進(jìn)程共享內(nèi)存空間外，如果要在這個(gè)內(nèi)存空間上運(yùn)行還需要根據(jù)父進(jìn)程的數(shù)據(jù)段描述符和代碼段
描述符設(shè)置子進(jìn)程的自己的數(shù)據(jù)段描述符和代碼段描述符。算法如下：
算法：copy_mem
輸入：子進(jìn)程進(jìn)程號(hào)nr
子進(jìn)程進(jìn)程控制塊p
輸出：如果成功，返回0
{
取得父進(jìn)程的數(shù)據(jù)段、代碼段的段限長(zhǎng)和基地址；
if（數(shù)據(jù)段和代碼段段限長(zhǎng)和基地址不合法）
顯示出錯(cuò)信息，死循環(huán)；
設(shè)置子進(jìn)程的數(shù)據(jù)段、代碼段的段限長(zhǎng)和基地址；
共享代碼段和數(shù)據(jù)段內(nèi)存空間（copy_page_tables）
if（共享失?。﹞
釋放子進(jìn)程共享內(nèi)存空間時(shí)申請(qǐng)的頁(yè)面；
return 共享失敗；
}
return 0；
}
由于linux0.11 只支持?jǐn)?shù)據(jù)段和代碼段基址相同的進(jìn)程，所以判斷數(shù)據(jù)段和代碼段的合法性首先應(yīng)
該檢測(cè)兩者是否相同；又由于代碼段在數(shù)據(jù)段之前，所以代碼段限長(zhǎng)一定要小于數(shù)據(jù)段限長(zhǎng)；
/kernel/fork.c
// 當(dāng)前進(jìn)程即父進(jìn)程
39 int copy_mem(int nr,struct task_struct * p)
40 {
41 unsigned long old_data_base,new_data_base,data_limit;
42 unsigned long old_code_base,new_code_base,code_limit;
43
44 code_limit=get_limit(0x0f); // 取當(dāng)前進(jìn)程代碼段和數(shù)據(jù)段段限長(zhǎng)
45 data_limit=get_limit(0x17);
46 old_code_base = get_base(current->ldt[1]); // 取原代碼段和數(shù)據(jù)段段基址
47 old_data_base = get_base(current->ldt[2]);
48 if (old_data_base != old_code_base)
49 panic( "We don't support separate I&D");
50 if (data_limit < code_limit)
51 panic( "Bad data_limit");
52 new_data_base = new_code_base = nr * 0x4000000; // 子進(jìn)程基址= 進(jìn)程號(hào)*64Mb( 進(jìn)程線性空間)
53 p->start_code = new_code_base;
54 set_base(p->ldt[1],new_code_base); // 設(shè)置代碼段、數(shù)據(jù)段基址
55 set_base(p->ldt[2],new_data_base);
56 if (copy_page_tables(old_data_base,new_data_base,data_limit)) { // 共享代碼段和數(shù)據(jù)段內(nèi)存空間
57 free_page_tables(new_data_base,data_limit); 釋// 放共享內(nèi)存空間時(shí)申請(qǐng)的頁(yè)面
58 return -ENOMEM;
59 }
60 return 0;
61 }
62

6.2.2 后期共享
當(dāng)子進(jìn)程被fork 出來(lái)后，就會(huì)和父進(jìn)程分道揚(yáng)鑣，獨(dú)立地被內(nèi)核調(diào)度執(zhí)行，在這個(gè)過(guò)程中父進(jìn)程和子
進(jìn)程的執(zhí)行是獨(dú)立的，互不影響。如果父進(jìn)程因?yàn)槿表?yè)新申請(qǐng)了物理頁(yè)面，子進(jìn)程是不知道的。示例如
下：
當(dāng)子進(jìn)程產(chǎn)生缺頁(yè)時(shí)，子進(jìn)程還是要盡量地“偷懶”，除了在被fork 出來(lái)時(shí)可以與父進(jìn)程共享內(nèi)存
外，父進(jìn)程新申請(qǐng)的物理頁(yè)也是可以被共享的。只要申請(qǐng)頁(yè)被讀入之后還沒(méi)有被改變過(guò)就可以共享。
其實(shí)上面說(shuō)的例子中，如果是子進(jìn)程申請(qǐng)了新的物理頁(yè)，父進(jìn)程同樣可以拿來(lái)用，如果子進(jìn)程還fork
了孫進(jìn)程，孫進(jìn)程申請(qǐng)的頁(yè)面子進(jìn)程和父進(jìn)程都可以使用。因?yàn)榉值罁P(yáng)鑣之后各個(gè)進(jìn)程是平等的，只要
大家都使用同一個(gè)可執(zhí)行程序，誰(shuí)先申請(qǐng)新物理頁(yè)都是一樣的。
試圖共享內(nèi)存的算法如下：
算法：share_page
輸入：共享地址address
輸出：如果成功，返回1
{
if ( 要求共享的進(jìn)程A 沒(méi)有對(duì)應(yīng)的可執(zhí)行文件)
return 0；
if (A 對(duì)應(yīng)的可執(zhí)行文件沒(méi)有被多個(gè)進(jìn)程使用)
return 0；
for( 每個(gè)存在的進(jìn)程P)
{
if (P 就是要求共享的進(jìn)程本身)
continue；
if (P 對(duì)應(yīng)可執(zhí)行文件與要求共享的進(jìn)程的不同)
continue；
if (P 進(jìn)程共享地址對(duì)應(yīng)的物理頁(yè)不存在或不干凈)
continue；
if ( 對(duì)應(yīng)物理頁(yè)不屬于主內(nèi)存塊 )
continue；
if ( 進(jìn)程A 共享地址對(duì)應(yīng)的頁(yè)表不存在 )
{
為頁(yè)表分配新的物理頁(yè)；
設(shè)置頁(yè)目錄項(xiàng)；
}
if ( 進(jìn)程A 對(duì)應(yīng)的頁(yè)表項(xiàng)已經(jīng)存在 )
顯示錯(cuò)誤信息，死循環(huán)；
將進(jìn)程P 對(duì)應(yīng)的頁(yè)表項(xiàng)屬性設(shè)為只讀；
設(shè)置進(jìn)程A 對(duì)應(yīng)地址的頁(yè)表項(xiàng)；
物理頁(yè)引用數(shù)加1；
刷新頁(yè)變換高速緩沖。
return 1；
}
return 0；
}
對(duì)于每一個(gè)進(jìn)程都應(yīng)該對(duì)應(yīng)一個(gè)可執(zhí)行文件，當(dāng)進(jìn)程處于某些特定時(shí)刻（如：正在作進(jìn)行初始化設(shè)
置）時(shí)沒(méi)有對(duì)應(yīng)的可執(zhí)行文件，當(dāng)然也就不應(yīng)該作共享處理。如果對(duì)應(yīng)的可執(zhí)行文件應(yīng)用數(shù)不大于1，則
表示沒(méi)有進(jìn)程與要求共享的進(jìn)程共享對(duì)應(yīng)的可執(zhí)行文件，也不會(huì)有共享對(duì)象。
接下來(lái)的任務(wù)就是找到一個(gè)符合要求的共享物理頁(yè)，條件有：1，進(jìn)程對(duì)應(yīng)可執(zhí)行文件相同；2，對(duì)
應(yīng)物理頁(yè)在被讀入之后沒(méi)有被修改過(guò)。如果要求共享進(jìn)程對(duì)應(yīng)地址的頁(yè)表項(xiàng)存在，但是原來(lái)是因?yàn)槿表?yè)
才進(jìn)入共享操作的，肯定系統(tǒng)出現(xiàn)了嚴(yán)重錯(cuò)誤。
最后進(jìn)程P 對(duì)應(yīng)的頁(yè)表項(xiàng)屬性修改為只讀，設(shè)置進(jìn)程A 對(duì)應(yīng)地址的頁(yè)表項(xiàng)，使它指向共享物理頁(yè)，
屬性為只讀，物理頁(yè)對(duì)應(yīng)主內(nèi)存塊映射數(shù)組項(xiàng)加1；因?yàn)轫?yè)表發(fā)生了變化，所以要刷新頁(yè)變換高速緩沖。
下面是具體代碼：
/mm/memory.c
335
336 /*
337 * share_page() tries to find a process that could share a page with
338 * the current one. Address is the address of the wanted page relative
339 * to the current data space.
340 *
341 * We first check if it is at all feasible by checking executable->i_count.
342 * It should be >1 if there are other tasks sharing this inode.
343 */
/*
* share_page() 試圖找到一個(gè)進(jìn)程，它可以與當(dāng)前進(jìn)程共享頁(yè)面。參數(shù)address 是
* 當(dāng)前數(shù)據(jù)空間中期望共享的某頁(yè)面地址。
*
* 首先我們通過(guò)檢測(cè)executable->i_count 來(lái)查證是否可行。如果有其它任務(wù)已共享
* 該inode，則它應(yīng)該大于1。
*/
344 static int share_page(unsigned long address)
345 {
346 struct task_struct ** p;
347
348 if (!current->executable) 沒(méi)// 有對(duì)應(yīng)的可執(zhí)行文件
349 return 0;
350 if (current->executable->i_count < 2) // 不是多進(jìn)程共享可執(zhí)行文件
351 return 0;
352 for (p = &LAST_TASK ; p > &FIRST_TASK ; --p) { // 搜索每個(gè)進(jìn)程控制塊指針
353 if (!*p) // 沒(méi)有對(duì)應(yīng)進(jìn)程
354 continue;
355 if (current == *p) // 就是指向當(dāng)前任務(wù)
356 continue;
357 if ((*p)->executable != current->executable) // 不是與當(dāng)前任務(wù)使用同一個(gè)可執(zhí)行文件
358 continue;
359 if (try_to_share(address,*p)) // 試圖共享頁(yè)面
360 return 1;
361 }
362 return 0;
363 }
364
下面是try_to_share(address,*p) 的代碼：
/mm/memory.c
283
284 /*
285 * try_to_share() checks the page at address "address" in the task "p",
286 * to see if it exists, and if it is clean. If so, share it with the current
287 * task.
288 *
289 * NOTE! This assumes we have checked that p != current, and that they
290 * share the same executable.
291 */
/*
* try_to_share() 在任務(wù)"p" 中檢查位于地址"address" 處的頁(yè)面，看頁(yè)面是否存在，是否干凈。
* 如果是干凈的話，就與當(dāng)前任務(wù)共享。
*current 共享p 已有的物理頁(yè)面
* 注意！這里我們已假定p != 當(dāng)前任務(wù)，并且它們共享同一個(gè)執(zhí)行程序。
*/
// address 是線性地址，是一個(gè)相對(duì)于code_start 的偏移量，在執(zhí)行完這個(gè)函數(shù)后，p 和current 偏移是
// address 的位置共享物理內(nèi)存!!!
292 static int try_to_share(unsigned long address, struct task_struct * p)
293 {
294 unsigned long from;
295 unsigned long to;
296 unsigned long from_page;
297 unsigned long to_page;
298 unsigned long phys_addr;
299
300 from_page = to_page = ((address>>20) & 0xffc); 計(jì)算相// 對(duì)于起始代碼偏移的頁(yè)目錄項(xiàng)數(shù)
// 加上自身的start_code 的頁(yè)目錄項(xiàng)，得到address 分別在p 和current 中對(duì)應(yīng)的頁(yè)目錄項(xiàng)
301 from_page += ((p->start_code>>20) & 0xffc);
302 to_page += ((current->start_code>>20) & 0xffc);
303 /* is there a page-directory at from? */
/* 在from 處是否存在頁(yè)目錄？*/
304 from = *(unsigned long *) from_page; // 取頁(yè)目錄項(xiàng)的內(nèi)容
305 if (!(from & 1)) // 對(duì)應(yīng)頁(yè)表是否存在
306 return 0;
// 取對(duì)應(yīng)的頁(yè)表項(xiàng)
307 from &= 0xfffff000;
308 from_page = from + ((address>>10) & 0xffc);
309 phys_addr = *(unsigned long *) from_page;
310 /* is the page clean and present? */
/* 頁(yè)面干凈并且存在嗎？*/
311 if ((phys_addr & 0x41) != 0x01)
312 return 0;　　　
313 phys_addr &= 0xfffff000;
314 if (phys_addr >= HIGH_MEMORY || phys_addr < LOW_MEM) // 是否在主內(nèi)存塊中
315 return 0;
// 取頁(yè)目錄項(xiàng)內(nèi)容..to。如果該目錄項(xiàng)無(wú)效(P=0)，則取空閑頁(yè)面，并更新to_page 所指的目錄項(xiàng)。　
316 to = *(unsigned long *) to_page; // 取目標(biāo)地址的頁(yè)目錄項(xiàng)
317 if (!(to & 1)) // 如果對(duì)應(yīng)頁(yè)表不存在
318 if (to = get_free_page()) // 分配新的物理頁(yè)
319 *(unsigned long *) to_page = to | 7;
320 else
321 oom();
322 to &= 0xfffff000; // 取目標(biāo)地址的頁(yè)表項(xiàng)
323 to_page = to + ((address>>10) & 0xffc);
324 if (1 & *(unsigned long *) to_page) // 如果對(duì)應(yīng)頁(yè)表項(xiàng)已經(jīng)存在，則出錯(cuò)，死循環(huán)
325 panic( "try_to_share: to_page already exists");
326 /* share them: write-protect */
/* 對(duì)它們進(jìn)行共享處理：寫保護(hù). */
327 *(unsigned long *) from_page &= ~2;
328 *(unsigned long *) to_page = *(unsigned long *) from_page; 共享物理內(nèi)存
// 　刷新頁(yè)變換高速緩沖。　
329 invalidate();
// 共享物理頁(yè)引用數(shù)加1
330 phys_addr -= LOW_MEM;
331 phys_addr >>= 12;
332 mem_map[phys_addr]++;
333 return 1;
334 }
335

7 頁(yè)面異常
當(dāng)cpu 在進(jìn)行內(nèi)存訪問(wèn)時(shí)，可能因?yàn)槿表?yè)或者試圖對(duì)一個(gè)只讀頁(yè)面進(jìn)行寫操作而產(chǎn)生頁(yè)面異常，cpu
進(jìn)入相應(yīng)的頁(yè)面異常中斷處理程序。
由于異常可能由缺頁(yè)或者寫只讀頁(yè)面產(chǎn)生，兩種情況的處理也是不同的，所以中斷處理程序首先應(yīng)該
區(qū)分產(chǎn)生本次異常的原因，進(jìn)入不同的處理過(guò)程。算法如下：
算法：page_fault
輸入：出錯(cuò)碼error_code
出錯(cuò)線性地址address
輸出：無(wú)
{
保存現(xiàn)場(chǎng)；
根據(jù)出錯(cuò)碼判斷出錯(cuò)原因；
if ( 缺頁(yè))
作缺頁(yè)處理do_no_page(error_code, address);
else
作寫保護(hù)出錯(cuò)處理do_wp_page(error_code, address)；
恢復(fù)現(xiàn)場(chǎng)；
return；
}
在x86 處理器中error_code 由cpu 產(chǎn)生并在保存了中斷點(diǎn)的相關(guān)內(nèi)容之后將其壓入堆棧，出錯(cuò)碼的
最低位指示出錯(cuò)原因（1：寫出錯(cuò)；0：缺頁(yè)）。address 則是由一個(gè)專門的32 位寄存器cr2 保存。具體代
碼如下：
/mm/page.s
11
12 .globl _page_fault
13
14 _page_fault:
15 xchgl %eax,(%esp) // 交換eax 與esp 所指向空間的內(nèi)容=>1. 保存eax; 2. 取出error_code
16 pushl %ecx // 保存現(xiàn)場(chǎng)
17 pushl %edx
18 push %ds
19 push %es
20 push %fs
21 movl $0x10,%edx //(21～24行)使ds、es、fs指向系統(tǒng)數(shù)據(jù)段
22 mov %dx,%ds
23 mov %dx,%es
24 mov %dx,%fs
25 movl %cr2,%edx // 取出錯(cuò)線性地址
26 pushl %edx // 將出錯(cuò)地址和出錯(cuò)碼壓入堆棧，作為處理函數(shù)的輸入?yún)?shù)
27 pushl %eax
28 testl $1,%eax // 判斷出錯(cuò)碼最低位，決定調(diào)用函數(shù)
29 jne 1f 為// 1，調(diào)用寫保護(hù)出錯(cuò)處理函數(shù)
30 call _do_no_page // 為0，調(diào)用缺頁(yè)處理函數(shù)
31 jmp 2f
32 1: call _do_wp_page
33 2: addl $8,%esp // 丟棄輸入?yún)?shù)error_code 和address
34 pop %fs // 恢復(fù)現(xiàn)場(chǎng)
35 pop %es
36 pop %ds
37 popl %edx
38 popl %ecx
39 popl %eax
40 iret
在這段代碼中，我們可以充分領(lǐng)略到系統(tǒng)程序員對(duì)匯編編程知識(shí)的要求。 在第15行xchgl %eax,(%
esp) ，必須非常清楚壓棧過(guò)程。當(dāng)cpu 執(zhí)行壓棧操作時(shí)，是先執(zhí)行esp=esp-4; 再將數(shù)據(jù)送入esp 所指向
的單元。cpu 在進(jìn)入異常中斷處理程序之前，將error_code 壓入了堆棧，當(dāng)前esp 指向的單元存放的就是
error_code，所以第15 行的命令，取出了error_code 又將eax 保存了，如果要用其他方法實(shí)現(xiàn)應(yīng)該是
pushl eax
movl (esp+4),eax
相比之下，15行的程序?qū)ax 放在了error_code 原來(lái)存放的空間，節(jié)約了堆棧空間，同時(shí)也節(jié)約指令
數(shù)，可謂是一箭四雕。在33 行 2: addl $8,%esp 對(duì)于輸入?yún)?shù)的丟棄，不是用兩次popl 操作，而是直接將
esp 加8，又省了一條指令。可見高水平的系統(tǒng)程序員為了提高效率是多么的摳門。這樣的程序雖然效率
高，但是對(duì)于理解會(huì)有一定的障礙，不過(guò)換個(gè)方向來(lái)想，畢竟這種底層代碼不是人人都會(huì)去仔細(xì)讀的。
7.1 缺頁(yè)中斷
在對(duì)進(jìn)行進(jìn)程初始設(shè)置時(shí)，內(nèi)核并不是將進(jìn)程可能用到的所有內(nèi)存一次性分配給進(jìn)程，而是在進(jìn)程
要訪問(wèn)該地址時(shí)分配，將內(nèi)存分配給一定會(huì)被訪問(wèn)的空間，這樣就提高內(nèi)存資源的使用率。這樣作就不
可避免地會(huì)出現(xiàn)缺頁(yè)中斷。當(dāng)cpu 訪問(wèn)一個(gè)內(nèi)存單元時(shí)，如果該單元所在的頁(yè)面不在內(nèi)存中，cpu 將產(chǎn)生
頁(yè)面異常，進(jìn)一步進(jìn)入缺頁(yè)處理程序，算法如下：
算法：do_no_page
輸入：出錯(cuò)碼error_code
出錯(cuò)線性地址address
輸出：無(wú)
{
if ( 出錯(cuò)進(jìn)程沒(méi)有對(duì)應(yīng)的可執(zhí)行文件
|| 出錯(cuò)地址不在代碼和數(shù)據(jù)段)
{
分配物理頁(yè)面并映射到出錯(cuò)線性地址( 使用get_empty_page())；
return；
}
試圖共享頁(yè)面( 使用share_page())；
if ( 共享頁(yè)面成功)
return ；
分配新的物理頁(yè)面(get_free_page())；
從可執(zhí)行文件中將頁(yè)面對(duì)應(yīng)的內(nèi)容讀入內(nèi)存；
將頁(yè)面中不屬于代碼段和數(shù)據(jù)段的內(nèi)容清零；
將新的物理頁(yè)面映射到出錯(cuò)線性地址(put_page())；
if ( 映射失敗)
{
釋放新申請(qǐng)的物理頁(yè)面；
顯示出錯(cuò)，死循環(huán)；
}
return；
}
進(jìn)程在不同的時(shí)刻會(huì)處于不同的狀態(tài)，如果進(jìn)程此時(shí)還處于初始化時(shí)期，就可能還沒(méi)有設(shè)置對(duì)應(yīng)的
可執(zhí)行文件，這個(gè)時(shí)候的內(nèi)存使用請(qǐng)求可能是與其設(shè)置有關(guān)的，所以需要為其分配內(nèi)存。
對(duì)于進(jìn)程的可執(zhí)行文件，在這里只是說(shuō)一下它的基本結(jié)構(gòu)：
進(jìn)程對(duì)應(yīng)的可執(zhí)行文件包含有進(jìn)程的代碼段和數(shù)據(jù)段的內(nèi)容，進(jìn)程的線性地址與可執(zhí)行文件內(nèi)容的
邏輯地址是對(duì)應(yīng)的，如果出錯(cuò)是在代碼段和數(shù)據(jù)段，應(yīng)該先試圖共享內(nèi)存，共享不成功就應(yīng)該分配內(nèi)存
并從可執(zhí)行文件中讀取相應(yīng)內(nèi)容，；如果不是在這兩個(gè)段，就直接分配內(nèi)存。
可執(zhí)行文件存儲(chǔ)在磁盤上，磁盤的存儲(chǔ)基本單位是1KB，所以要讀取一個(gè)頁(yè)面的內(nèi)容就要讀取四個(gè)
磁盤塊。從可執(zhí)行文件中讀取內(nèi)容由bmap 和bread_page 兩個(gè)函數(shù)來(lái)作，首先將出錯(cuò)線性地址所在頁(yè)面換
算成可執(zhí)行文件對(duì)應(yīng)的邏輯盤塊號(hào)，bmap 用于將邏輯盤塊號(hào)換算成物理盤塊號(hào)，最后由bread_page 將四
個(gè)物理盤塊讀入內(nèi)存。
在讀入過(guò)程中，可能出現(xiàn)這種情況，由于線性地址太大，對(duì)應(yīng)頁(yè)面換算得到的邏輯盤塊號(hào)過(guò)大，對(duì)
應(yīng)可執(zhí)行文件卻沒(méi)有這么大（如下所示，這時(shí)后兩塊邏輯盤塊將不會(huì)被讀入），多余的邏輯盤將不會(huì)被讀
入。
另外，讀入一頁(yè)內(nèi)存之后，該頁(yè)的結(jié)束地址可能會(huì)超過(guò)end_data。
由于上述兩種情況，應(yīng)該對(duì)多出來(lái)的內(nèi)存清零。
最后就是映射頁(yè)面，put_page 只有在申請(qǐng)新的頁(yè)表空間失敗的情況會(huì)返回0，這時(shí)就應(yīng)該將已經(jīng)申請(qǐng)
了的物理頁(yè)面釋放，然后調(diào)用oom() 報(bào)錯(cuò)。
具體代碼如下：
/mm/memory.c
365 void do_no_page(unsigned long error_code,unsigned long address)
366 {
367 int nr[4];
368 unsigned long tmp;
369 unsigned long page;
370 int block,i;
371
372 address &= 0xfffff000; 取// 頁(yè)面起始地址
373 tmp = address - current->start_code; // 換算出相對(duì)于進(jìn)程代碼起始地址的相對(duì)地址
374 if (!current->executable || tmp >= current->end_data) { // 沒(méi)有對(duì)應(yīng)可執(zhí)行文件或不在代碼和數(shù)據(jù)段
375 get_empty_page(address);
376 return;
377 }
// 到此處時(shí)一定是代碼和數(shù)據(jù)長(zhǎng)度范圍內(nèi)
378 if (share_page(tmp)) // 嘗試共享內(nèi)存
379 return;
380 if (!(page = get_free_page())) // 分配新的物理內(nèi)存
381 oom();
382 /* remember that 1 block is used for header */
/* 記住，（程序）頭要使用1 個(gè)數(shù)據(jù)塊 */
383 block = 1 + tmp/BLOCK_SIZE; // 換算邏輯塊起始?jí)K號(hào)
384 for (i=0 ; i<4 ; block++,i++) // 將邏輯塊號(hào)換算成物理塊號(hào)
385 nr[i] = bmap(current->executable,block);
386 bread_page(page,current->executable->i_dev,nr); // 讀入一個(gè)頁(yè)的四個(gè)磁盤塊
387 i = tmp + 4096 - current->end_data; // 對(duì)超出數(shù)據(jù)段的內(nèi)容清零
388 tmp = page + 4096;
389 while (i-- > 0) {
390 tmp--;
391 *(char *)tmp = 0;
392 }
393 if (put_page(page,address)) // 頁(yè)面映射
394 return;
395 free_page(page);
396 oom();
397 }
398

7.2 頁(yè)面寫保護(hù)錯(cuò)誤
由于進(jìn)程的fork 和share_page 操作，會(huì)出現(xiàn)多個(gè)進(jìn)程共享一個(gè)物理頁(yè)面的情況，這個(gè)物理頁(yè)面被置
為只讀方式，如果其中一個(gè)進(jìn)程想對(duì)這個(gè)頁(yè)面進(jìn)行寫操作，cpu 就會(huì)產(chǎn)生頁(yè)面異常中斷，并進(jìn)一步進(jìn)入寫
保護(hù)出錯(cuò)處理。
在寫保護(hù)出錯(cuò)處理中，將會(huì)根據(jù)情況復(fù)制被共享的頁(yè)或者取消對(duì)頁(yè)面的寫保護(hù)。
算法：do_wp_page
輸入：出錯(cuò)碼error_code
出錯(cuò)線性地址address
輸出：無(wú)
{
if ( 出錯(cuò)地址屬于進(jìn)程的代碼段)
將進(jìn)程終止；
if ( 出錯(cuò)頁(yè)面屬于主內(nèi)存塊且共享計(jì)數(shù)為1)
{
取消寫保護(hù)；
刷新頁(yè)變換高速緩沖；
return；
}
申請(qǐng)一個(gè)新的物理頁(yè)；
if ( 出錯(cuò)頁(yè)面屬于主內(nèi)存塊)
共享計(jì)數(shù)減1；
使出錯(cuò)時(shí)的頁(yè)表項(xiàng)指向新的物理頁(yè)；
刷新頁(yè)變換高速緩沖；
復(fù)制共享頁(yè)的內(nèi)容到新的物理頁(yè)；
return；
}
對(duì)于一般情況，對(duì)代碼段的寫操作是違法的，肯定是進(jìn)程本身代碼有問(wèn)題，為了不進(jìn)一步引起錯(cuò)
誤，系統(tǒng)將會(huì)把該進(jìn)程終止。但是estdio 庫(kù)（后來(lái)不再為linux 所使用）支持對(duì)代碼段的寫操作，linus 當(dāng)
時(shí)由于沒(méi)有得到這個(gè)庫(kù)的具體資料，所以也只是預(yù)留了操作。
一個(gè)頁(yè)面被多個(gè)進(jìn)程共享，每當(dāng)一個(gè)進(jìn)程產(chǎn)生一次寫保護(hù) 錯(cuò)誤，內(nèi)核將給進(jìn)程分配一個(gè)新的物理頁(yè)
面，將共享頁(yè)面的內(nèi)容復(fù)制過(guò)來(lái)，新的頁(yè)面將設(shè)置為可讀寫，而共享頁(yè)面仍然是只讀的，只是共享計(jì)數(shù)
減小了。當(dāng)其他共享進(jìn)程都產(chǎn)生了一次寫保護(hù)錯(cuò)誤后，共享頁(yè)面的共享計(jì)數(shù)減成了1，其實(shí)就是被一個(gè)進(jìn)
程獨(dú)占了，但此時(shí)該共享頁(yè)面仍然是只讀的，如果獨(dú)占它的進(jìn)程對(duì)它進(jìn)行寫操作仍然會(huì)產(chǎn)生寫保護(hù)出
錯(cuò)。為什么不在共享計(jì)數(shù)減成了1 之后就將共享頁(yè)面置為可寫呢？原因很簡(jiǎn)單，因?yàn)橄到y(tǒng)并不知道最后
是哪個(gè)頁(yè)表項(xiàng)指向這個(gè)共享頁(yè)，如果要把它查找出來(lái)會(huì)有很大的系統(tǒng)開銷，這是中斷處理程序應(yīng)當(dāng)盡量
避免的，所以采用了以逸待勞的辦法。
如果當(dāng)初共享的頁(yè)面不屬于主內(nèi)存塊，在共享時(shí)就沒(méi)有作共享計(jì)數(shù)的處理，就不存在共享計(jì)數(shù)的問(wèn)
題，直接復(fù)制就可以了。
/mm/memory.c
239
240 /*
241 * This routine handles present pages, when users try to write
242 * to a shared page. It is done by copying the page to a new address
243 * and decrementing the shared-page counter for the old page.
244 *
245 * If it's in code space we exit with a segment error.
246 */
/*
* 當(dāng)用戶試圖往一個(gè)共享頁(yè)面上寫時(shí)，該函數(shù)處理已存在的內(nèi)存頁(yè)面，（寫時(shí)復(fù)制）
它是通過(guò)將頁(yè)面復(fù)制到一個(gè)新地址上并遞減* 原頁(yè)面的共享頁(yè)面計(jì)數(shù)值實(shí)現(xiàn)的。
*
* 如果它在代碼空間，我們就以段錯(cuò)誤信息退出。
*/
247 void do_wp_page(unsigned long error_code,unsigned long address)
248 {
249 #if 0
250 /* we cannot do this yet: the estdio library writes to code space */
251 /* stupid, stupid. I really want the libc.a from GNU */
/* 我們現(xiàn)在還不能這樣做：因?yàn)閑stdio 庫(kù)會(huì)在代碼空間執(zhí)行寫操作 */
/* 真是太愚蠢了。我真想從GNU 得到libc.a 庫(kù)。*/
252 if (CODE_SPACE(address)) // 出錯(cuò)地址屬于進(jìn)程的代碼段，則終止當(dāng)前程序
253 do_exit(SIGSEGV);
254 #endif
// 處理取消頁(yè)面保護(hù)。
// 輸入?yún)?shù)指向出錯(cuò)頁(yè)的頁(yè)表項(xiàng)的指針
// 計(jì)算方法：
// 頁(yè)表偏移量+ 頁(yè)表起始地址
255 un_wp_page((unsigned long *)
256 (((address>>10) & 0xffc) + (0xfffff000 &*((unsigned long *) ((address>>20) &0xffc)))));
257
258
259 }
260
un_wp_page 的具體代碼也在/mm/memory.c 中
220
221 void un_wp_page(unsigned long * table_entry)
222 {
223 unsigned long old_page,new_page;
224
225 old_page = 0xfffff000 & *table_entry; // 取出錯(cuò)頁(yè)面對(duì)應(yīng)的物理地址
// 如果屬于主內(nèi)存塊且共享計(jì)數(shù)為1
226 if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {
227 *table_entry |= 2; // 共享頁(yè)置為可寫
228 invalidate();
229 return;
230 }
231 if (!(new_page=get_free_page())) // 申請(qǐng)一個(gè)空閑物理頁(yè)面
232 oom();
233 if (old_page >= LOW_MEM) 如果在// 主內(nèi)存塊中，將共享數(shù)減1
234 mem_map[MAP_NR(old_page)]--;
235 *table_entry = new_page | 7; // 改變table_entry 的指向從而實(shí)現(xiàn)共享的分離
236 invalidate();
237 copy_page(old_page,new_page); // 拷貝共享頁(yè)
238 }
239
8 桶結(jié)構(gòu)
8.1 桶結(jié)構(gòu)定義與初始化
在C 語(yǔ)言中，malloc（int size）用于在用戶空間為某個(gè)大小為size 的結(jié)構(gòu)申請(qǐng)一塊相應(yīng)的內(nèi)存空間，
在內(nèi)核中很多時(shí)候也需要為內(nèi)核的數(shù)據(jù)結(jié)構(gòu)分配內(nèi)存空間。對(duì)于內(nèi)核來(lái)說(shuō)，用戶進(jìn)程分配內(nèi)存空間的操
作與用戶的普通的內(nèi)存訪問(wèn)操作并沒(méi)有區(qū)別，在用戶分配空間時(shí)，內(nèi)核只需要關(guān)心是否超出了用戶的虛
擬地址空間就行了。內(nèi)核給自己分配內(nèi)存空間就不同了，內(nèi)核要對(duì)物理內(nèi)存進(jìn)行管理，對(duì)這種小量的內(nèi)
存分配尤其需要仔細(xì)管理。
要管理，干脆就將將一部分內(nèi)存頁(yè)分成指定大小的塊，大小是1、2、3、4、5 ⋯，當(dāng)內(nèi)核申請(qǐng)時(shí)就
從含有對(duì)應(yīng)大小塊的內(nèi)存中取出一塊分配出去，比如：當(dāng)內(nèi)核申請(qǐng)一個(gè)大小為3 的空間時(shí)，就從被分成
了大小為3 的塊的內(nèi)存頁(yè)中取一個(gè)塊來(lái)分配。這就是桶結(jié)構(gòu)結(jié)構(gòu)的基本思想。將內(nèi)存頁(yè)看成是桶，桶里
面裝的是相同大小的內(nèi)存塊。
如果使用1、2、3、4 ⋯這樣的內(nèi)存塊大小進(jìn)行管理，頁(yè)面的利用率會(huì)很低，可能一個(gè)頁(yè)面只會(huì)被申
請(qǐng)很少幾個(gè)結(jié)構(gòu)，這樣將造成很大的內(nèi)存浪費(fèi)。塊的分配很大程度決定了桶結(jié)構(gòu)的空間使用效率，經(jīng)過(guò)
理論計(jì)算和長(zhǎng)期的實(shí)際運(yùn)行證明，采用2 的冪次作為塊的大小具有理想的效果。linux0.11 采用的就是這
種分塊方式，根據(jù)實(shí)際情況，從16、32、64 ⋯一直到一個(gè)頁(yè)的大小4096 B，在分配時(shí)分配能滿足需求的
最小的塊。
對(duì)于每個(gè)桶，應(yīng)該有一個(gè)結(jié)構(gòu)記錄它的信息，以及與其他桶之間的關(guān)系。linux0.11 中定義了一個(gè)叫
桶描述符的結(jié)構(gòu)，具體結(jié)構(gòu)如下：
/lib/malloc.c
52 struct bucket_desc { /* 16 bytes */ /* 本結(jié)構(gòu)占16 個(gè)字節(jié)*/
53 void *page; // 對(duì)應(yīng)頁(yè)面起始地址
54 struct bucket_desc *next; // 指向下一個(gè)描述符的指針
55 void *freeptr; // 指向本桶中空閑內(nèi)存塊鏈表的指針
56 unsigned short refcnt; // 引用計(jì)數(shù)
57 unsigned short bucket_size; // 本描述符對(duì)應(yīng)內(nèi)存塊的大小
58 };
為了方便查找，內(nèi)核分別將相同塊大小的桶串成一條鏈，鏈表頭結(jié)構(gòu)如下：
60 struct _bucket_dir { /* 8 bytes */ /* 本結(jié)構(gòu)占8 個(gè)字節(jié)*/
61 int size; // 本鏈中桶對(duì)應(yīng)的內(nèi)存塊的大小( 字節(jié)數(shù))
62 struct bucket_desc *chain; // 本鏈中的桶描述符鏈表頭指針
63 };
同時(shí)還有一個(gè)數(shù)組用于保存所有的鏈表頭：
77 struct _bucket_dir bucket_dir[] = {
78 { 16, (struct bucket_desc *) 0}, // 16 字節(jié)長(zhǎng)度的內(nèi)存塊。
79 { 32, (struct bucket_desc *) 0}, // 32 字節(jié)長(zhǎng)度的內(nèi)存塊。
80 { 64, (struct bucket_desc *) 0}, // 64 字節(jié)長(zhǎng)度的內(nèi)存塊。
81 { 128, (struct bucket_desc *) 0}, // 128 字節(jié)長(zhǎng)度的內(nèi)存塊。
82 { 256, (struct bucket_desc *) 0}, // 256 字節(jié)長(zhǎng)度的內(nèi)存塊。
83 { 512, (struct bucket_desc *) 0}, // 512 字節(jié)長(zhǎng)度的內(nèi)存塊。
84 { 1024, (struct bucket_desc *) 0}, // 1024 字節(jié)長(zhǎng)度的內(nèi)存塊。
85 { 2048, (struct bucket_desc *) 0}, // 2048 字節(jié)長(zhǎng)度的內(nèi)存塊。
86 { 4096, (struct bucket_desc *) 0}, // 4096 字節(jié)(1 頁(yè)) 內(nèi)存。
87 { 0, (struct bucket_desc *) 0}
}; /* End of list marker */
88
這幾級(jí)結(jié)構(gòu)關(guān)聯(lián)的結(jié)果如圖：
在初始化時(shí)，系統(tǒng)并不分配任何內(nèi)存作為桶，而是在請(qǐng)求發(fā)生時(shí)才分配內(nèi)存。在分配內(nèi)存作為桶
時(shí)，也要分配一個(gè) bucket_desc 結(jié)構(gòu)，如果這個(gè)結(jié)構(gòu)的分配與一般的內(nèi)核分配請(qǐng)求一樣，就有可能進(jìn)入一
個(gè)死循環(huán)：分配函數(shù)自身也在請(qǐng)求分配。所以 對(duì)于bucket_desc 結(jié)構(gòu)需要獨(dú)立的分配機(jī)制。
專門分配一個(gè)頁(yè)用于存放bucket_desc，當(dāng)需要時(shí)就從這個(gè)頁(yè)面中分配一個(gè)bucket_desc 結(jié)構(gòu)。在初始
化時(shí)，將所有結(jié)構(gòu)利用他們自身的next 指針連成一個(gè)鏈表，用一個(gè)指針指向鏈表頭。這個(gè)指針的定義
為：
92 struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;
這樣就連成了下圖的結(jié)構(gòu)：
bucket_desc 專用頁(yè)的初始化函數(shù)的算法為：
算法： init_bucket_desc
輸入：無(wú)
輸出：無(wú)
{
申請(qǐng)一個(gè)空閑頁(yè)（get_free_page）；
for（每一個(gè)bucket_desc 結(jié)構(gòu)）
{
if（不是最后一個(gè)bucket_desc 結(jié)構(gòu)）
next 指向下一個(gè)bucket_desc 結(jié)構(gòu)；
}
使最后一項(xiàng)的next 指針指向free_bucket_desc 指向的內(nèi)容；
使free_bucket_desc 指向第一個(gè)bucket_desc 結(jié)構(gòu)；
return ；
}
一般情況下，這個(gè)初始化程序是在鏈表為空，即free_bucket_desc 為NULL 時(shí)才會(huì)被調(diào)用。內(nèi)核中的
數(shù)據(jù)結(jié)構(gòu)，尤其是鏈表，需要考慮多任務(wù)調(diào)度可能造成內(nèi)核數(shù)據(jù)結(jié)構(gòu)不一致的情況，對(duì)于get_free_page
這種操作，如果系統(tǒng)引入了虛擬內(nèi)存管理之后，很可能會(huì)導(dǎo)致當(dāng)前執(zhí)行進(jìn)程進(jìn)入睡眠等待內(nèi)存，在這個(gè)
進(jìn)程被激活之前，在其他進(jìn)程執(zhí)行時(shí)，內(nèi)核可能會(huì)因?yàn)榻Y(jié)構(gòu)分配而再次調(diào)用到init_bucket_desc，如果這
時(shí)順利執(zhí)行了，專用頁(yè)被分配了，在睡眠的進(jìn)程重新運(yùn)行時(shí)，仍然會(huì)去改變bucket_desc 鏈表。為了避免
出錯(cuò)，在程序結(jié)構(gòu)上要特別處理。一種方案是：在改變鏈表前檢查free_bucket_desc 是否還是NULL，如
果不是，就成功退出，如果是，就該進(jìn)行對(duì)鏈表的操作；linux0.11 并沒(méi)有采用這種方案，而是繼續(xù)對(duì)鏈
表操作，最后并不是直接的對(duì)free_bucket_desc 賦值，而是向鏈表頭部加入內(nèi)容的操作，這樣就避免內(nèi)核
數(shù)據(jù)結(jié)構(gòu)的不一致。
我們假設(shè)進(jìn)程A 執(zhí)行時(shí)系統(tǒng)進(jìn)入init_bucket_desc，并在申請(qǐng)頁(yè)面（get_free_page）時(shí)被阻塞。之后進(jìn)
程B 運(yùn)行，系統(tǒng)又進(jìn)入 init_bucket_desc，順利執(zhí)行完后退出，這時(shí)內(nèi)核中空閑bucket_desc 鏈表如下：
進(jìn)程A 恢復(fù)執(zhí)行后，從get_free_page 中返回，繼續(xù)執(zhí)行完 init_bucket_desc 函數(shù)，經(jīng)過(guò)最后兩個(gè)操作
（向鏈表頭部加入內(nèi)容的操作）之后將兩個(gè)頁(yè)面連接到了一起：
當(dāng)讀到后面8.2 的代碼后，會(huì)發(fā)現(xiàn)這些考慮在linux0.11 中并不需要，這正是體現(xiàn)了linux 設(shè)計(jì)的嚴(yán)
謹(jǐn)。
/lib/malloc.c
93
94 /*
95 * This routine initializes a bucket description page.
96 */
/*
下面的* 程序用于初始化一頁(yè)桶描述符頁(yè)面。
*/
97 static inline void init_bucket_desc()
98 {
99 struct bucket_desc *bdesc, *first;
100 int i;
101
102 first = bdesc = (struct bucket_desc *) get_free_page(); // 申請(qǐng)一頁(yè)內(nèi)存,first 指向頁(yè)基址
103 if (!bdesc)
104 panic( "Out of memory in init_bucket_desc()");
105 for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) { // 將頁(yè)中的bucket_desc 結(jié)構(gòu)連成鏈表
106 bdesc->next = bdesc+1;
107 bdesc++;
108 }
109 /*
110 * This is done last, to avoid race conditions in case
111 * get_free_page() sleeps and this routine gets called again....
112 */
/*
* 這是在最后處理的，目的是為了避免在get_free_page() 睡眠時(shí)該子程序又被
* 調(diào)用而引起的競(jìng)爭(zhēng)條件。
*/
// 將新頁(yè)的鏈表連入系統(tǒng)的空閑bucket_desc 鏈表
113 bdesc->next = free_bucket_desc;
114 free_bucket_desc = first;
115 }
116
在桶頁(yè)面內(nèi)部，所有的空閑內(nèi)存塊也是串成了
一個(gè)鏈表，桶描述符中的freeptr 指向鏈表頭。使用
下面的代碼初始化桶頁(yè)面就有了右圖所示的結(jié)構(gòu)：
(void *) cp = get_free_page();
160 for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
161 *((char **) cp) = cp + bdir->size;
162 cp += bdir->size;
163 }
164 *((char **) cp) = 0;

8.2 桶內(nèi)存塊的分配
在標(biāo)準(zhǔn)的C 函數(shù)中使用malloc（int len）進(jìn)行內(nèi)存塊分配，在linux0.11 中使用了一個(gè)同名的函數(shù)
malloc（int len）進(jìn)行內(nèi)核的內(nèi)存塊分配。為了避免混淆，在0.98 版內(nèi)核之后采用了kmalloc（int size）。
相對(duì)應(yīng)的linux0.11 中的內(nèi)核內(nèi)存塊釋放函數(shù)free_s 也改名為kfree_s。
了解了桶的組織結(jié)構(gòu)，分配內(nèi)存塊的算法就不難理解了。
算法：malloc
輸入：申請(qǐng)內(nèi)存塊大小len
輸出：如果成功，返回內(nèi)存塊指針；失敗則返回NULL；
{
查找一個(gè)桶鏈表，鏈表中 桶的內(nèi)存塊是能夠滿足要求的最小塊；
if（沒(méi)有搜索到符合要求的鏈）
{
打印出錯(cuò)信息：請(qǐng)求塊過(guò)大；
進(jìn)入死循環(huán)；
}
關(guān)中斷；
在鏈表中查詢還有空閑內(nèi)存塊的桶；
if（鏈表中所有桶都沒(méi)有空閑的內(nèi)存塊）
{
if（沒(méi)有空閑桶描述符）
初始化一個(gè)頁(yè)面用作桶描述符（init_bucket_desc）；
從空閑桶描述符鏈表中分配一個(gè)桶描述符；
分配一個(gè)新物理頁(yè)面作為桶；
初始化桶頁(yè)面；
設(shè)置桶描述符指針；
將新桶連入對(duì)應(yīng)的鏈表；
}
從桶中分配一個(gè)空閑內(nèi)存塊；
開中斷；
return 空閑內(nèi)存塊指針；
}
桶結(jié)構(gòu)最大能夠分配的內(nèi)存塊的大小是4KB，如果這個(gè)大小都還不能滿足要求，那么肯定是出問(wèn)題
了。內(nèi)核中不可能申請(qǐng)這么大的內(nèi)存塊。
之后的操作是在中斷關(guān)閉的狀態(tài)下執(zhí)行的，所以就不會(huì)因?yàn)檫M(jìn)程切換導(dǎo)致數(shù)據(jù)結(jié)構(gòu)不一致的情況。似
乎init_bucket_desc 中關(guān)于避免進(jìn)程切換的安排是多余的，但是使用關(guān)中斷作為避免競(jìng)爭(zhēng)的手段是低效
的，尤其是在中間執(zhí)行過(guò)程復(fù)雜的情況下。如果以后引入虛存管理之后，可能必須有進(jìn)程切換，到時(shí)就
不能使用關(guān)中斷了。所以提前在程序結(jié)構(gòu)上作安排才是正確之道。
/lib/malloc.c
116
117 void *malloc(unsigned int len)
118 {
119 struct _bucket_dir *bdir;
120 struct bucket_desc *bdesc;
121 void *retval;
122
123 /*
124 * First we search the bucket_dir to find the right bucket change
125 * for this request.
126 */
/*
首先我們搜索存儲(chǔ)桶目錄* bucket_dir 來(lái)尋找適合請(qǐng)求的桶大小。
*/
127 for (bdir = bucket_dir; bdir->size; bdir++) // 尋找合適的鏈表：(bdir->size)/2<len<=bdir->size
128 if (bdir->size >= len)
129 break;
130 if (!bdir->size) { // 鏈表頭數(shù)組最后一項(xiàng)是NULL
131 printk( "malloc called with impossibly large argument (%d)/n", len);
132
133 panic( "malloc: bad arg");
134 }
135 /*
136 * Now we search for a bucket descriptor which has free space
137 */
/*
* 現(xiàn)在我們來(lái)搜索具有空閑空間的桶描述符。
*/
138 cli(); /* Avoid race conditions */ /* 為了避免出現(xiàn)競(jìng)爭(zhēng)條件 */ // 關(guān)中斷
139 for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) // 尋找還有空閑內(nèi)存塊的桶
140 if (bdesc->freeptr)
141 break;
142 /*
143 * If we didn't find a bucket with free space, then we'll
144 * allocate a new one.
145 */
/*
* 如果沒(méi)有找到具有空閑空間的桶描述符，那么我們就要新建立一個(gè)該目錄項(xiàng)的描述符。
*/
146 if (!bdesc) {
147 char *cp;
148 int i;
149
150 if (!free_bucket_desc) // 沒(méi)有空閑桶描述符
151 init_bucket_desc();
152 bdesc = free_bucket_desc; // 取一個(gè)空閑桶描述符
153 free_bucket_desc = bdesc->next;
154 bdesc->refcnt = 0; 設(shè)// 置新的桶描述符
155 bdesc->bucket_size = bdir->size;
156 bdesc->page = bdesc->freeptr = (void *) cp = get_free_page();
157 if (!cp) // 頁(yè)面申請(qǐng)失敗
158 panic( "Out of memory in kernel malloc()");
159 /* Set up the chain of free objects */
/* 在該頁(yè)空閑內(nèi)存中建立空閑對(duì)象鏈表 */
160 for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
161 *((char **) cp) = cp + bdir->size;
162 cp += bdir->size;
163 }
164 *((char **) cp) = 0; 最后一項(xiàng)的指針為NULL
165 bdesc->next = bdir->chain; /* OK, link it in! */ /* OK，將其鏈入！*/
166 bdir->chain = bdesc;
167 }
// 分配一個(gè)空閑內(nèi)存塊
168 retval = (void *) bdesc->freeptr;
169 bdesc->freeptr = *((void **) retval);
170 bdesc->refcnt++;
171 sti(); /* OK, we're safe again */ /* OK，現(xiàn)在我們又安全了*/ // 開中斷
172 return(retval);
173 }
174
8.3 桶內(nèi)存塊的回收
當(dāng)使用完內(nèi)存塊之后，內(nèi)核將釋放內(nèi)存塊。申請(qǐng)時(shí)內(nèi)核知道需要的內(nèi)存塊的大小，在釋放時(shí)卻不一
定知道要釋放的這塊內(nèi)存的大小是多少。如果沒(méi)有指定要釋放的內(nèi)存塊的大小，怎么確定要釋放內(nèi)存塊
的大小呢？在釋放時(shí)必然會(huì)指定內(nèi)存塊的地址，這個(gè)地址唯一的對(duì)應(yīng)了一個(gè)物理頁(yè)面，也就是唯一對(duì)應(yīng)
了一個(gè)桶，這個(gè)桶的描述符中就記錄了內(nèi)存塊的大小。在linux0.11 中使用free_s(void *obj, int size) 來(lái)釋
放內(nèi)存塊，如果不指定大小，輸入?yún)?shù)size 是0
算法：free_s
輸入：釋放對(duì)象指針obj
釋放對(duì)象大小size（如果是0，表示沒(méi)有指定大?。?br />輸出：無(wú)
{
for（每一個(gè)桶鏈表）{
if（鏈表中桶的內(nèi)存塊大小< 釋放對(duì)象大?。?br />continue；
for（每一個(gè)桶）
if（是釋放對(duì)象對(duì)應(yīng)的桶）
退出搜索；
}
if（搜索桶失?。?br />顯示出錯(cuò)信息，死循環(huán)；
關(guān)中斷；
將要釋放的內(nèi)存塊鏈入桶的空閑鏈表；
修改桶的相關(guān)信息；
if（桶中所有的內(nèi)存塊都是空閑的）
{
釋放桶對(duì)應(yīng)的內(nèi)存塊；
釋放桶對(duì)應(yīng)的描述符；
}
開中斷；
return；
}
可以看出在搜索時(shí)，如果輸入?yún)?shù)size 為0，將會(huì)一次搜索不同size 的桶鏈表。如果指定了size，搜
索速度就會(huì)大幅度提高。但在內(nèi)核中仍然提供了對(duì)不指定大小的釋放操作：
/include/linux/kernel.h
12 #define free(x) free_s((x), 0)
當(dāng)正是釋放內(nèi)存塊時(shí)，關(guān)閉了中斷，仍然是為了避免進(jìn)程切換造成數(shù)據(jù)結(jié)構(gòu)的不一致。free_s 的代碼
如下：
/lib/malloc.c
174
175 /*
176 * Here is the free routine. If you know the size of the object that you
177 * are freeing, then free_s() will use that information to speed up the
178 * search for the bucket descriptor.
179 *
180 * We will #define a macro so that "free(x)" is becomes "free_s(x, 0)"
181 */
/*
* 下面是釋放子程序。如果你知道釋放對(duì)象的大小，則free_s() 將使用該信息加速
* 搜尋對(duì)應(yīng)桶描述符的速度。
*
* 我們將定義一個(gè)宏，使得"free(x)" 成為"free_s(x, 0)"。
*/
182 void free_s(void *obj, int size)
183 {
184 void *page;
185 struct _bucket_dir *bdir;
186 struct bucket_desc *bdesc, *prev;
187
188 /* Calculate what page this object lives in */
/* 計(jì)算該對(duì)象所在的頁(yè)面 */
189 page = (void *) ((unsigned long) obj & 0xfffff000);
190 /* Now search the buckets looking for that page */
/* 現(xiàn)在搜索存儲(chǔ)桶目錄項(xiàng)所鏈接的桶描述符，尋找該頁(yè)面 */
191 for (bdir = bucket_dir; bdir->size; bdir++) {
192 prev = 0; // 如果是0，則搜索到的桶是鏈表的第一個(gè)桶
193 /* If size is zero then this conditional is always false */
/* 如果參數(shù)size 是0，則下面條件肯定是false */
194 if (bdir->size < size)
195 continue;
196 for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
197 if (bdesc->page == page)
198 goto found; // 退出搜索
199 prev = bdesc;
200 }
201 }
202 panic( "Bad address passed to kernel free_s()"); // 如果搜索失敗
203 found:
204 cli(); /* To avoid race conditions */ /* 為了避免競(jìng)爭(zhēng)條件 */
205 *((void **)obj) = bdesc->freeptr; // 鏈入空閑塊鏈表
206 bdesc->freeptr = obj;
207 bdesc->refcnt--;
208 if (bdesc->refcnt == 0) {
209 /*
210 * We need to make sure that prev is still accurate. It
211 * may not be, if someone rudely interrupted us....
212 */
/*
* 我們需要確信prev 仍然是正確的，若某程序粗魯?shù)刂袛嗔宋覀?br />* 就有可能不是了。
*/
213 if ((prev && (prev->next != bdesc)) || (!prev && (bdir->chain != bdesc)))
214
215 for (prev = bdir->chain; prev; prev = prev->next)
216 if (prev->next == bdesc)
217 break;
218 if (prev)
219 prev->next = bdesc->next;
220 else { // prev 如果是0，則搜索到的桶是鏈表的第一個(gè)桶
221 if (bdir->chain != bdesc)
222 panic( "malloc bucket chains corrupted");
223 bdir->chain = bdesc->next;
224 }
225 free_page((unsigned long) bdesc->page); 釋// 放對(duì)應(yīng)內(nèi)存頁(yè)面
226 bdesc->next = free_bucket_desc; // 將桶描述符鏈入空閑桶描述符鏈表
227 free_bucket_desc = bdesc;
228 } /* 208 if (bdesc->refcnt == 0)*/
229 sti(); // 開中斷
230 return;
231 }
232

內(nèi)存9 使用情況統(tǒng)計(jì)
通過(guò)前面的介紹，對(duì)于linux0.11 內(nèi)存管理機(jī)制有了整體的了解。有時(shí)候需要對(duì)主內(nèi)存塊的使用情況
作統(tǒng)計(jì)。統(tǒng)計(jì)的項(xiàng)目有：當(dāng)前主內(nèi)存塊還有多少空閑頁(yè)面；分配了的物理頁(yè)面在4G 的虛擬內(nèi)存空間中的
分布情況。
對(duì)于第一個(gè)項(xiàng)目，只需要對(duì) 主內(nèi)存塊映射數(shù)組mem_map 的空閑項(xiàng)進(jìn)行統(tǒng)計(jì)。對(duì)于第二個(gè)項(xiàng)目，需要
對(duì)4G 的虛存空間進(jìn)行查詢，必須查頁(yè)目錄表和頁(yè)表。通過(guò)頁(yè)目錄表查每個(gè)頁(yè)表的所有項(xiàng)，通過(guò)判斷每個(gè)
頁(yè)表項(xiàng)的有效位(P) 統(tǒng)計(jì)每個(gè)頁(yè)表中映射有多少個(gè)物理頁(yè)面。第一節(jié)曾經(jīng)談到內(nèi)核將16M 的物理內(nèi)存映
射到第0～3個(gè)頁(yè)表上從而實(shí)現(xiàn)對(duì)物理內(nèi)存的控制，在這里這幾個(gè)頁(yè)表是沒(méi)有必要查詢的，因?yàn)槭冀K是
頁(yè)表的1024 項(xiàng)都映射了物理頁(yè)面。但是linux0.11 也對(duì)2、3 兩個(gè)頁(yè)表進(jìn)行了統(tǒng)計(jì)，只跳過(guò)了0、1 兩個(gè)頁(yè)
表。以下便是統(tǒng)計(jì)函數(shù)calc_mem(void)
/mm/memory.c
// 計(jì)算主內(nèi)存塊中空閑頁(yè)面數(shù)并統(tǒng)計(jì)每個(gè)頁(yè)表中映射了的物理頁(yè)面數(shù)。
413 void calc_mem(void)
414 {
415 int i,j,k,free=0;
416 long * pg_tbl;
417
// 掃描映射數(shù)組mem_map[]，統(tǒng)計(jì)主內(nèi)存塊中的空閑頁(yè)面數(shù)并顯示。
418 for(i=0 ; i<PAGING_PAGES ; i++)
419 if (!mem_map[i]) free++;
420 printk( "%d pages free (of %d)/n/r",free,PAGING_PAGES);
// 掃描所有頁(yè)目錄項(xiàng)（除0，1 項(xiàng)），如果頁(yè)目錄項(xiàng)有效，則統(tǒng)計(jì)對(duì)應(yīng)頁(yè)表中有效頁(yè)面數(shù)，并顯示。
421 for(i=2 ; i<1024 ; i++) {
422 if (1&pg_dir[i]) {
423 pg_tbl=(long *) (0xfffff000 & pg_dir[i]);
424 for(j=k=0 ; j<1024 ; j++)
425 if (pg_tbl[j]&1)
426 k++;
427 printk( "Pg-dir[%d] uses %d pages/n",i,k);
428 }
429 }
430 }