Linux內存管理的源碼實現

author:kf701  mail:kf_701@21cn.com   hefei of china  5/2005     寫作中...

　　最近一段時間在閱讀Linux的源代碼，想把看到的東西寫出來，覺得內存這一部分最簡單，就先寫了出來。請指正！

***于17/5/2005***

　　內存最低4K的地址是一張頁目錄(page_dir)，頁目錄共1024項，每項4字節。目錄項的結構如下：
 ____________________________________
｜32-12位為頁框地址   ｜　　　   ｜U｜R｜p｜
｜                                     ｜               ｜S｜W｜ ｜
｜_________________｜______ ｜_｜_ ｜_｜

隨后的16K，用來做了4張頁表，頁表項結構和頁目錄項結構一樣。頁表的每一項指向一個物理頁面，
也就是指向內存中的一個4K大小的空間。有了這4張頁表，已經能尋址16M的內存了。
　　下面就是在系統初始化的時候在head.s程序中設置一張頁目錄和四張頁表的代碼。此時頁目錄中
僅前4項有效，正是指向位于其下面的4張頁表，而這4張頁表尋址了內存的最低16M。

198 setup_paging:
199         movl 24*5,%ecx               /* 5 pages - pg_dir+4 page tables */
200         xorl %eax,%eax
201         xorl %edi,%edi                  /* pg_dir is at 0x000 */
202         cld;rep;stosl
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          /*  --------- " " --------- */
207         movl $pg3+4092,%edi
208         movl xfff007,%eax             /*  16Mb - 4096 + 7 (r/w user,p) */
209         std
210 1:      stosl                   /* fill pages backwards - more efficient :-) */
211         subl x1000,%eax
212         jge 1b

　　以后每次有fork新進程，都要為新進程分配內存。但具體是怎么做的呢，我也想知道，一起看吧。
當執行fork時，它使用int0x80調用sys_fork函數，sys_fork的代碼位于system_call.s中，很短如下：

208 _sys_fork:
209         call _find_empty_process
210         testl %eax,%eax
211         js 1f
212         push %gs
213         pushl %esi
214         pushl %edi
215         pushl %ebp
216         pushl %eax
217         call _copy_process
218         addl ,%esp
219 1:      ret

看到其中調用了兩個函數，find_empty_process and copy_process，這兩個函數在fork.c文件里實現的。
find_empty_process是為將要創建的新進程找一個pid，保存在last_pid里，然后調用copy_process，這
是sys_fork真正的主程序，其中有如此句：

 77         p = (struct task_struct *) get_free_page();

　　先為新進程分配一張物理頁面，用來存放進程的PCB結構，即task_struct結構。光給新進程一張物
理頁面來存放它的task_struct，顯然是不能滿足它的。
　　我們知道，在創建之初，新進程是和其父進程共享代碼和數據的。這是人為定的，不過這樣的好處
不言而喻。因此在創建的時候就沒有必要將其代碼和數據全部copy到新內存地址里，而只為新進程創建
頁目錄項和頁表就可以了。代碼如下：

115         if (copy_mem(nr,p)) { /*copy_mem調用memory.c里的copy_page_tables*/
116                 task[nr] = NULL;
117                 free_page((long) p);
118                 return -EAGAIN;
119         }

　　copy_mem為新進程分配頁表空間，并把父進程的頁表內容copy到新進程的頁表空間里，這樣新進
程的頁表的每一項指向的物理頁面和其父進程頁表的相應每一項指向的物理頁面是一樣的。少說了一些，
不能只copy頁表就完事了。
　　32位線性地址轉換為物理地址的時候，最先要找到32位線性地址對應的頁目錄項，再用頁目錄項找
到頁表地址。新進程有了自己的頁表，并且頁表也都指向了物理地址，現在少的就是頁目錄項了。
　　新進程在創建的時候，在4G線性空間里給其分配了64M的線性空間，是通過設置LDT來完成的：

130　　　　set_ldt_desc(gdt+(nr<<1)+FIRST_LDT_ENTRY,&(p->ldt));

這64M的線性地址是從nr*64M的地址處開始的，這個地址正好可以被映射到頁目錄里的一項，這項的地
址是：((nr*64M)>>20)&0xffc。只要從這里開始，在頁目錄里建一些頁目錄項，指向新創建的進程的頁
表地址(copy_mem調用copy_page_tables()來做的)。
　　到這里，copy_mem的工作可以說是完成了，不過一定不能少了這一句：

177                      this_page &= ~2; (memory.c)

由于新進程和其父進程共享物理內存頁面，因此把這些物理頁面重新都設成只讀是必要的。上面這句是
放在copy_page_tables函數里面的循環中的。copy_mem主要是靠調用這個程序來完成工作的。

　　分析到這里，我終于可以小舒一口氣了。不如回顧一下：
系統初始化的時候在內存起始處建一張頁目錄(page_dir)，以后所有的進程都使用這張頁目錄。并為系
統建了4張頁表。以后每有新進程產生，便為之分配空間存放PCB（即struct task_struct)，然后為之通
過復制父進程的頁表來創建自己的頁表，并創建相應的頁目錄項。

***于18/5/2005中午***

　　程序運行了，問題又來了。終于讀到了“寫時復制”和請求調頁的部分。當程序訪問的線性地址沒
有被映射到一個物理頁面，或欲寫操作的線性地址映射的物理頁面僅是只讀，都會產生一個頁異常，然
后就會轉去頁異常中斷處理程序(int 14)執行，頁異常中斷處理程序(page.s)如下：

 14 _page_fault:
 15         xchgl %eax,(%esp)
 16         pushl %ecx
 17         pushl %edx
 18         push %ds
 19         push %es
 20         push %fs
 21         movl x10,%edx
 22         mov %dx,%ds
 23         mov %dx,%es
 24         mov %dx,%fs
 25         movl %cr2,%edx
 26         pushl %edx
 27         pushl %eax
 28         testl ,%eax
 29         jne 1f
 30         call _do_no_page
 31         jmp 2f
 32 1:      call _do_wp_page
 33 2:      addl ,%esp
 34         pop %fs
 35         pop %es
 36         pop %ds
 37         popl %edx
 38         popl %ecx
 39         popl %eax
 40         iret

　　根據error_code判斷是缺頁還是寫保護引起的異常，然后去執行相應的處理程序段，先看寫保護的處
理吧。

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 */
252         if (CODE_SPACE(address))
253                 do_exit(SIGSEGV);
254 #endif
255         un_wp_page((unsigned long *)
256                 (((address>>10) & 0xffc) + (0xfffff000 &
257                 *((unsigned long *) ((address>>20) &0xffc)))));
258
259 }
　　程序就一個函數調用，很少有這么簡單的函數，哈哈！address很顯然是程序想要訪問但引起出錯的
線性地址了。(0xfffff000&*((unsigned long *)((address>>20)&0xffc))計算出32位線性地址對應頁表
的地址，再加上一個((address>>10) & 0xffc),就是加上頁表內的偏移量，即得到頁表內的一個頁表項。
看un_wp_page()就更明白了。

221 void un_wp_page(unsigned long * table_entry)
222 {
223         unsigned long old_page,new_page;
224
225         old_page = 0xfffff000 & *table_entry;
226         if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {
227                 *table_entry |= 2;
228                 invalidate();
229                 return;
230         }
231         if (!(new_page=get_free_page()))
232                 oom();
233         if (old_page >= LOW_MEM)
234                 mem_map[MAP_NR(old_page)]--;
235         *table_entry = new_page | 7;
236         invalidate();
237         copy_page(old_page,new_page);
238 }      

　　225－229做了個判斷，如果此物理頁面沒有被共享，則只要將可寫位置1(227)。不然就進入231行去。
在物理內存中分配一頁空間，把原頁面的內容copy到新頁面里(copy_page)，再把那個引起出錯的address
映射到這個新頁面的物理地址上去(235行)。至此，寫保護出錯的處理完成了，可以返回去執行原進程里
引起出錯的那條指令了。
　　上面所述，就是所謂的“寫時復制(copy on write)”。

　　如果是缺頁異常的話，則執行do_no_page，最簡單的辦法就是直接申請一張物理頁面，對應到這個
引起出錯的address，如下：

372         address &= 0xfffff000;
373         tmp = address - current->start_code;
374         if (!current->executable || tmp >= current->end_data) {
375                 get_empty_page(address);
376                 return;
377         }

如果這樣了之，那也太不負責任了，只是在!current->executable || tmp >= current->end_data的情況
下，才這樣做。這是怎樣的情況呢？!current->executable有待閱讀，tmp >= current->end_data很簡單，
在程序體已全部讀入內存后，這可能是動態內存分配所要求的內存空間。
　　否則就嘗試去和別的進程共享一下，如下：

378         if (share_page(tmp))
379                 return;

如果共享不成，那也只好自己申請一張頁面了，如下：

380         if (!(page = get_free_page()))
381                 oom();

一張頁面4K大小，那就到設備上去讀4K大小的程序內容到內存，根據current->executable，可以在設備上
找到缺頁對應程序的相應位置。

382 /* remember that 1 block is used for header */
383         block = 1 + tmp/BLOCK_SIZE;
384         for (i=0 ; i<4 ; block++,i++)
385                 nr[i] = bmap(current->executable,block);
386         bread_page(page,current->executable->i_dev,nr);

判斷讀入4K是否大于程序長度，是的話，則把多出的部分清零。

387         i = tmp + 4096 - current->end_data;
388         tmp = page + 4096;
389         while (i-- > 0) {
390                 tmp--;
391                 *(char *)tmp = 0;
392         }

最后不能忘了把新頁面的物理地址和出錯的線性地址address相對應，形成映射。

393         if (put_page(page,address))
394                 return;

　　do_no_page，就是操作系統理論中的請求調頁。
　　終于明白，原來那么多的操作系統書籍用那么大堆的紙張所述的東西，真正寫起操作系統來，用幾小函數
就把它們完成了。

***于18/5/2005晚上***

　　內存分配出去，當進程運行結束，回收是必要的。
　　其實這些也是簡單的，因為有一個數組，就是下面的：

 43 #define LOW_MEM 0x100000
 44 #define PAGING_MEMORY (15*1024*1024)
 45 #define PAGING_PAGES (PAGING_MEMORY>>12)

 57 static unsigned char mem_map [ PAGING_PAGES ] = ;

可以看到，數組項數是除去最低1M內存后可以分成的頁面數，也就是可以用的物理內存頁面。系統在初始化的
時候把還沒有被使用的內存物理頁面對應的項置為了0，初始代碼如下：

399 void mem_init(long start_mem, long end_mem)
400 {
401         int i;
402
403         HIGH_MEMORY = end_mem;
404         for (i=0 ; i405                 mem_map[i] = USED;
406         i = MAP_NR(start_mem);
407         end_mem -= start_mem;
408         end_mem >>= 12;
409         while (end_mem-->0)
410                 mem_map[i++]=0;
411 }

　　其實前面所有的申請內存的程序里都最終使用了一個函數get_free_page()，不管申請多少的內存，最終還
是要按頁面來申請：

 63 unsigned long get_free_page(void)
 64 {
 65 register unsigned long __res asm("ax");
 66
 67 __asm__("std ; repne ; scasb\n\t"
 68         "jne 1f\n\t"
 69         "movb ,1(%%edi)\n\t"
 70         "sall ,%%ecx\n\t"
 71         "addl %2,%%ecx\n\t"
 72         "movl %%ecx,%%edx\n\t"
 73         "movl 24,%%ecx\n\t"
 74         "leal 4092(%%edx),%%edi\n\t"
 75         "rep ; stosl\n\t"
 76         "movl %%edx,%%eax\n"
 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;
 83 }

這個函數就是在物理內存中找一張沒有使用的頁面并返回其物理地址。這是一段gclearcase/" target="_blank" >cc內聯匯編，它在mem_map
數組中的最后一項一直向前找，只要找一項的值不為0，則用這個數組下標計算出物理地址返回，并把那一項的
值設為1。用下標計算物理地址的方法我想是這樣的：index*4096+LOW_MEN

　　(std;repne;scasb,這三句是依次檢查mem_map里的每一項的值，如果全部不為0，也即沒有物理內存可以用，
立即返回0。movb ,1(%%edi)這句就是把mem_map數組里找到的可用的一項的標志設為1。此時ecx里的值就
是數組下標，因此sall ,%%ecx就是index*4096，addl %2,%%ecx即把剛才的index*4096+LOW_MEM。73,74
75三句是把相應的物理內存空間內容全部清0。movl %%edx,%%eax顯然是返回值了)

　　有件事一定要做，那就是在返回之前把那個物理頁面的內容全部清0。
　　清0的事情讓get_free_page做了，回收就簡單了，只要把mem_map數組的相應項置為0就可以了,從下面可以看
出來，free_page確實只做了這件事:

 89 void free_page(unsigned long addr)
 90 {
 91         if (addr < LOW_MEM) return;
 92         if (addr >= HIGH_MEMORY)
 93                 panic("trying to free nonexistent page");
 94         addr -= LOW_MEM;
 95         addr >>= 12;
 96         if (mem_map[addr]--) return;
 97         mem_map[addr]=0;
 98         panic("trying to free free page");
 99 }

進程退出時，會調用sys_exit，sys_exit只是調用了一下do_exit，回收內存的工作就在這里完成的。

106         free_page_tables(get_base(current->ldt[1]),get_limit(0x0f));
107         free_page_tables(get_base(current->ldt[2]),get_limit(0x17));

free_page_tables釋放進程的代碼段和數據段占用的內存，它內部使用循環，調用free_page完成最終的工作。

　　休息一下，有空再研究............
http://blog.chinaunix.net/index.php?blogId=3063