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