1.内存初始化
在linux0.12中，默认最大可以支持16M物理内存，如果需要支持更大的物理内存需要自己修改代码。整个16M内存被线性划分为如下区域:1M以下为内核使用的区域，1M-4M为高速缓冲区，用来将磁盘数据缓冲至此，从而提高读写效率;4M-4.5M为虚拟磁盘，4.5M以上为主存区。最大可达到4.5M-16M。
内核将主存区域划分为页进行管理，每个页都有mem_map数组元素与之对应，用来记录该页数据是否已被使用。在初始化内存时，对mem_map的每个元素设置为100(Used)，而将主存区域start_mem和end_mem之间的mem_map设置为0(Available)。这样在遍历整个内存空间时，仅仅主存区域可被选择。
#define PAGING_MEMORY (15*1024*1024) //总共可用物理内存
#define PAGING_PAGES (PAGING_MEMORY>>12) //总共管理的物理内存页数
//标识位数组，每个page一个，数组大小为3840，需要占内存3840 Byte (一个page4K以内)
unsigned char mem_map [ PAGING_PAGES ] = {0,};
mem_map的索引为物理地址页(4K)，所以物理内存的管理是以牺牲一页物理内存4K字节为代价的。 而从物理地址映射到mem_map的关系为：
mem_map[(physicalAddrss-1M)>>12]。mem_map的值为该物理内存共享的数量。
内存是同时开启分段和分页机制管理的, 分段是通过GTD, LTD等来完成的，而分页是通过页目录表(page dir table)和页表(page table)来达到的：其中线性地址的31-22为页目录项，21-12位为页表项，最后12为页内偏移地址。
- 页目录表(page dir table): linux0.12使用一页内存保存了真个系统的页目录表，一共可以支持210=1024个页目录表项，每个页目录表项可以管理4M内存，所以理论上linux0.12可以支持4G内存。其中前4个页目录表项对应的16M物理内存为内核初始化并使用。对于内核代码而言，线性地址即为物理地址。
- 页表(page table): 一个页目录表项对应1024个页表项，最后映射到的内存为4096*1024 = 4M, 即1024个内存页。
页表项数据，P=1时表示该页数据在内存中。P=0表示该页数据在swap中，并且前31bit代表的swap_nr，即映射都硬盘位置的标号。
2.缺页处理 do_no_page
当访问一页线性地址，该线性地址出现下列情形导致不能被直接访问时
- 并不在页目录表中
- 在页目录表但是页表项不存在
- 页表项存在页frame没有加载到内存时，
80X86体结构的CPU会发起中断。将该线性地址压入CR2寄存器，通过中断门可以处理该中断。do_no_page即为该中断处理程序，其主要作用是在页目录表和页表中加入该线性address,并将对应数据加载到主存中。这里线性地址和应用程序相关，比如/usr/bin/java这个程序代码需要加载到主存中。 值得注意的是，文件数据的加载必须通过高速缓存区，也就是说,/usr/bin/java这个程序对应的二进制代码被首先加载到高速缓存区，然后再被进程A,B,C分别拷贝一份到主存区，由各自的线性地址空间与之关联。 整个do_no_page处理如下：
- 首先进行数据校验，即输入的线性地址必须在64M*nr之内。否则报错退出。
- 然后如果发现线性地址已经在页目录表中存在，并且对应的页表项也存在页frame没有加载到内存中，说明该页frame曾经被刷到内存中后被交换到硬盘上，那么直接从swap分区将该页frame加载到内存中。
- 之后根据线性地址，判断需要加载的数据是否在代码/数据区，是否在lib区。linux0.12对一个任务分配了64M*nr~64M*(nr+1)的线性地址空间，这64M地址的分布布局是一定的，最顶端为lib区，然后是环境变量和参数，接下来是用户进程堆栈；实际的代码/数据区从64M地址的底端往上长。如果需要加载的线性地址不在代码/数据区或者lib区，那么应该是给该进程分配堆栈数据，则直接分配一页空间，并将这一页物理地址和address做关联。
- 如果在代码/数据区或者lib区，那么根据inode值，在其他运行的任务中尝试寻找已经打开该inode，并且对应的物理页已经加载过的任务。因为两个任务若加载同样的exe/lib，并且同样的物理地址被加载，根据每个任务在线性空间的分配，address-start_code的偏移量应该是一样的，对应的目标线性地址应该在page dir/page table中可以找到，并且根据页表项P标志位知道是否位于内存中。如果位于内存中，那么直接返回。
- 如果共享不成功(没有任务打开inode，或者对应inode的这块线性地址并没有在物理内存中)，则根据线性地址和inode可以计算出需要读的磁盘block号，读出4个block(1 block = 1K)到物理页page中，并把超过end_data的置0，最后将address的线性地址和读出的物理页page关联(put_page)。由于当前进程在64M线性地址空间的分布是按照: text-data-bss这样划分的，所以address - start_code就是相当于可执行程序文件的偏移量。据此，可以算出在inode中的块号，然后再通过文件系统算出最终对应于磁盘上的块号。
//缺页处理, address为输入的线性地址
void do_no_page(unsigned long error_code,unsigned long address)
{
int nr[4];
unsigned long tmp;
unsigned long page;
int block,i;
struct m_inode * inode;
if (address < TASK_SIZE)
printk("\n\rBAD!! KERNEL PAGE MISSING\n\r");
if (address - current->start_code > TASK_SIZE) {
printk("Bad things happen: nonexistent page error in do_no_page\n\r");
do_exit(SIGSEGV);
}
//dir=0，得到页目录项值
page = *(unsigned long *) ((address >> 20) & 0xffc);
if (page & 1) {
page &= 0xfffff000;//页表地址
//页表项物理地址 = 页表基地址 + 页表项偏移量
page += (address >> 10) & 0xffc;
tmp = *(unsigned long *) page;//页表项值
if (tmp && !(1 & tmp)) {//页表项对应的页面不在内存中，从swap分区加载
swap_in((unsigned long *) page);
return;
}
}
//这里根据需要的线性地址和当前任务的线性地址开始处的差
//可以计算出在该inode中需要读的block号，
address &= 0xfffff000;
tmp = address - current->start_code;
if (tmp >= LIBRARY_OFFSET ) {
inode = current->library;
block = 1 + (tmp-LIBRARY_OFFSET) / BLOCK_SIZE;
} else if (tmp < current->end_data) {
inode = current->executable;
block = 1 + tmp / BLOCK_SIZE;
} else {
inode = NULL;
block = 0;
}
//不在当前进程的CS/DS线性地址范围内，直接分配一页
if (!inode) {
get_empty_page(address);
return;
}
//如果当前进程的inode被别的进程加载，则尝试共享，共享计数加1并返回
if (share_page(inode,tmp))
return;
//前两种情形都不存在，只好新建一页，然后读取address处指定的4K数据(1 page)
if (!(page = get_free_page()))
oom();
/* remember that 1 block is used for header */
//第一个block空出来不用，所以block要从1开始算起
for (i=0 ; i<4 ; block++,i++)
nr[i] = bmap(inode,block);
bread_page(page,inode->i_dev,nr);
//下面对超过end_data区域的数据清0
i = tmp + 4096 - current->end_data;
if (i>4095)
i = 0;
tmp = page + 4096;
while (i-- > 0) {
tmp--;
*(char *)tmp = 0;
}
if (put_page(page,address))
return;
//出错处理
free_page(page);
oom();
}
3.页写保护处理 do_wp_page
linux0.12采取了load-on-demand和copy-on-write的策略，当调用系统调用fork出一个子进程时，子进程和父亲进程会共享物理内存，并且子进程和父进程的页表项会被置为只读，当子进程或者父进程的任何一方企图对自己的进程空间线性地址进行写操作时，CPU会触发写保护中断操作，do_wp_page这时候会被调用。其主要作用就是新开辟一页内存，以便进程空间线性地址进行写操作可以继续执行。如果一个子进程在fork处理之后直接去执行execve。则会节省下这段内存。
//table_entry:页表项
//该函数执行copy-on-write
//即在table_entry指向的物理内存(old_page)并没有分配的情行下，
//从物理内存中分配一页，从old_page拷贝
//fork系统调用的底层实现
void un_wp_page(unsigned long * table_entry)
{
unsigned long old_page,new_page;
old_page = 0xfffff000 & *table_entry;
//如果shared-counter为1直接返回
if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {
*table_entry |= 2;
invalidate();
return;
}
if (!(new_page=get_free_page()))
oom();
if (old_page >= LOW_MEM)
mem_map[MAP_NR(old_page)]--;
copy_page(old_page,new_page);
*table_entry = new_page | 7;
invalidate();
}
/*
* This routine handles present pages, when users try to write
* to a shared page. It is done by copying the page to a new address
* and decrementing the shared-page counter for the old page.
*
* If it's in code space we exit with a segment error.
*/
void do_wp_page(unsigned long error_code,unsigned long address)
{
if (address < TASK_SIZE)
printk("\n\rBAD! KERNEL MEMORY WP-ERR!\n\r");
if (address - current->start_code > TASK_SIZE) {
printk("Bad things happen: page error in do_wp_page\n\r");
do_exit(SIGSEGV);
}
#if 0
/* we cannot do this yet: the estdio library writes to code space */
/* stupid, stupid. I really want the libc.a from GNU */
if (CODE_SPACE(address))
do_exit(SIGSEGV);
#endif
//考虑到4字节一个entitry
//(address>>20) &0xffc 就是 (address>>22) &0x3ff >>2 页目录项值
//(address>>10) & 0xffc 就是 (address>>12) &0x3ff >>2 页表项值
un_wp_page((unsigned long *)
(((address>>10) & 0xffc) + (0xfffff000 &
*((unsigned long *) ((address>>20) &0xffc)))));
}
4.物理内存的分配和释放
下面两个函数仅仅针对物理内存操作，不涉及到线性地址。
get_free_page返回可以用的一页物理地址。该方法从mem_map中查找值为0的项，得到可以用的页index后，将其换算成物理页的基地址 physicalAddress = index<<12 + 1M， 并对该地址所在的4K字节置0.
get_free_page的调用分析：该函数试图从mem_map数组中找到一个可以用的内存页，具体满足的是条件mem_map[inxex]=0，找到以后将mem_map[index]=1，然后将index 换算成主存物理地址，并对该页地址初始化0操作。如果在此过程中没有可以使用的内存页，则调用swap_out函数，swap_out从线性地址空间64M-4G按顺序寻找一个page frame在物理内存中的，如果找到这么一个page frame(肯定可以找到，否则页不会有swap_out发生)，则将该页表重置(*table_ptr = swap_nr<<1;)并将该page frame的数据写到硬盘上。
/*
* Get physical address of first (actually last :-) free page, and mark it
* used. If no free pages left, return 0.
*/
unsigned long get_free_page(void)
{
register unsigned long __res asm("ax");
repeat:
__asm__("std ; repne ; scasb\n\t" //找到DI中最后的一个标志位为0的page ECX-- AX=0 DI=mem_map+PAGING_PAGES-1
"jne 1f\n\t"
//OK，找到可以用的页，标志位置为1，注意scasb的伪代码为:
//%%AL-%%DI （compare byte in AL and des)
//%%DI=%%DI-1 (std and byte operation)
//所以等到repne判断%%DI=0的时候，%%DI对应的值已经减1了，故这里需要用1(%%edi)补偿回来
"movb $1,1(%%edi)\n\t"
//ECX执向 mem_map里面可以用的索引值，注意repne循环的时候使用ECX作为计数器自减
//ECX=(valid_page)>>12+LOW_MEM，注意在repne和scasb过程中，ECX作为计数器一直递减(std)
"sall $12,%%ecx\n\t"
"addl %2,%%ecx\n\t"
"movl %%ecx,%%edx\n\t"
"movl $1024,%%ecx\n\t"
"leal 4092(%%edx),%%edi\n\t" //注意不是4096，因为是从低字节到高字节的 4 byte拷贝，第一个是4092-4096,最后一个是0-4
"rep ; stosl\n\t"//copy 1024(ECX--) from EAX to EDI(--) (从高到低)
"movl %%edx,%%eax\n"
"1:"
:"=a" (__res)
:"0" (0),"i" (LOW_MEM),"c" (PAGING_PAGES),
"D" (mem_map+PAGING_PAGES-1)
:"di","cx","dx");
if (__res >= HIGH_MEMORY)
goto repeat;
if (!__res && swap_out())
goto repeat;
return __res;
}
free_page释放一页物理地址，所谓的“释放”是指将mem_map对应的共享值减1. 并不真正的将物理内存清除。在 copy-on-write中，新写入的进程会对原来共享内存进行free操作，本质上就是将共享计数从2减到1.
free_page_tables释放指定线性地址空间内的4M*X的内存，包括管理这4M线性地址空间的一页页表内存也会释放，同时对应于该4M线性地址空间的page dir元素也会置为0.表示没有使用。
5.虚拟内存 swap
swap分区对上层mm是透明的，比如说我想访问一个线性地址，该线性地址的前20个bit决定了一个页表项在内存中的位置(10bit 页目录项 + 10bit 页表项)，当我们安装该物理内存地址访问到该页表项的值时，如果P=0，表示该页存储在swap分区中，其页表项的其余31bit则用来表示swap分区序号swan_nr(其实是15 bit，因为最大swap_nr=32K)，从swap分区序号swap_nr可以知道应该读硬盘的位置 (block sec = swap_nr >>3, 需要读8 sectors)。只有当P=1时，表实该页在物理内存中，页表项的值代表了实际的物理地址。
可以这么理解，页表项描述了数据页的位置
- 指向的页在内存中的物理地址(P==1): 20bit physical address (4K对齐 10 bit 页目录项 + 10 bit 页表项 )
- 指向的页在硬盘中的物理地址(P==0): 15bit swap number (可以转化为block和sectors)
swap主要提供两个函数:
- swap_out：当有内存分配请求，并且当前的物理内存已经使用完毕，此时需要将一些数据从内存写到硬盘上，以便空出物理内存页。 (被get_free_page调用)
- swap_in: 当有数据访问请求，并且访问的线性地址对应的页表项(前20bit)所指的内存页不存在，但是可以确定该页数据已经从磁盘上加载过，此时需要将对应内存页的数据从硬盘读入到内存中来。 (被do_no_page调用)
一个程序首先是被fork处理，设置好pg_dir, page table以后，实际上page table entry还是指向原父进程的物理地址。下面会调用execve，完成子进程copy on write的内存操作。
swap并不能提供给程序无限的内存使用空间。有一种错觉是swap类似北京到上海的铁轨，并不需要有北京-上海这么长的铁轨容量，只要够快不够用的时候可以临时搭建。对应到内存是说只要频繁的swap就可以支持无限的内存， 追究到实现细节是说swap在占用的情况下可以重新复用，好比北京到上海的铁轨，过了天津以后，北京-天津段的铁轨可以拆了再铺前面需要的一段。实际上并不是这样，swap在使用以后不可以自行拆除，除非是进程退出。 所以，系统里的最大内存容量是被主存+swap限制的。在分不出新的内存page的情况下，系统会抛出OOM的错。swap只是主存的一个"数据"备份而已。而且还没办法区分数据的冷热。
lib库中的malloc和free
这里的lib库指的是kernel的调用库，并不是面向最终应用程序的glibc这种库。lib库的malloc和free等调用对kernel其他可能使用内存的组件(例如net)封装了内存管理的细节，使得组件可以方便的获取内存资源。由于malloc和free容易和面向应用程序的程序库重名，从linux0.98开始这两个函数被重命名为kmalloc, kfree。
具体的实现层面引入bucket的概念，每个物理页可以分成若干个bucket，一个物理页上的bucket都是相同大小的，例如物理页1分成256个16byte，物理页2分成128个32byte等等。每个物理页有元数据bucket_desc进行管理，bucket_desc存储了bucket的大小，指向的物理页可用地址，物理页基地址等等。
bucket_desc数据也会占用相应的内存，数据bucket_desc相当于metadata，不会释放，只会复用。而bucket_desc所管理的bucket对应的物理页，在refcnt降为0时会释放掉(调用逻辑释放free_page)，这样该页内存可以继续使用。 全局指针free_bucket_desc保存可以使用的bucket_desc的列表，在全部的bucket_desc用完时会继续申请物理内存。
// 管理一个page的数据结构 16bytes管理4K，一页为4K/16=256个，可以管理256*4K=1M内存
struct bucket_desc { /* 16 bytes */
void *page; //页基线性地址
struct bucket_desc *next; //用来将一页数据链接起来
void *freeptr; //当前可用页的线性地址(0表示无可用)
unsigned short refcnt; //当前页的bucket个数
unsigned short bucket_size; //bucket的大小
};
相同大小的bucket页由一个链表chain管理，这样可以根据用户申请内存的大小，在链表chain中找寻最小那个可以满足用户请求的chain，然后跟据bucket_desc找到freeptr不为0的可以用的地址。
6.总结
内存模块抽象了主存和硬盘swap分区，对上提供了内存使用的管理功能，包括内存的申请和释放等。
从内存模块的分层概念上来说，内存模块首先对系统调用fork/execve/exit等进程的创建/执行/退出等，提供了以页目录表和页表为核心的线性地址空间的管理，使得每个进程都可以独享64M的虚拟地址空间；而对kernel中其他直接需要分配内存资源的模块，直接提供了物理内存的申请和释放的功能。当然，内存大小是受物理内存+swap分区的严格限制。
