好吧 如果你说其实4M不大，那么如果是64位的话呢 2^64/2^12 = 2^52个页表entry 每个entry 4byte，就是2^54byte的页表 好吧 应该还没有计算机可以奢侈到能承受这么大的页表
如果用二级页表 前10个bit作为一个页表 可以表示1024个entry 每个entry存的是二级页表的index 可以认为每个entry代表了4M的地址空间 其实就是用的hash的思想 比如一个program 第0个entry 4M存text段的页表，第1个存data 段的页表 最后一个存stack的页表 PTO是page table offset
还是举个例子吧，比如一个virtual address 0x00403004
bit31-bit22: 0000 0000 01
bit21-bit12: 0000 0000 11
bit11-bit0: 0000 0000 0100
PTO1 就是1 PTO2是3 OFFSET 是4 不错挺简单
好了 下面是计算机干的活： MMU先用PT1=1去找第二级页表，怎么找？PT1的entry里存了L2页表的base address, 得到entry 1(从0开始) 对应的是4M-1 到8M-1的地址。相当于是找个二级页表某一个entry的起始地址，然后用PT2=3找这个entry的第4行 对应的地址是多少呢 在这个4M空间内 10个bit 所以依然是1024个entry 每个entry4K大小 0-4K,4K-8K, 8K-12K, 12K-16K对了 就是12K-16K 真正的页表地址还应该加上PT1里面存的base address,得到了页表地址就可以取值了。好了 这个entry里面就是我们想找的 page frame number了，加上offset就是physical address
扩展一下 Core i7采用了4级页表 i7支持48位和52位的物理地址空间(真是够大的。。。)
以48位为例，i7取前36位作为virtual page number，每级页表分到9位作为offset 当然了 每一级的标志位略有不同 不过idea还是类似上面所说的两级页表，前三级页表中bit51-bit12存放的都是下一级页表的基地址，而第四级页表存放的是40位PPN，加上那12位VPO直接得来的offset，就可以为我们提供4PB(52位)的物理地址空间了。牛吧。记住，每一级页表这里是64位，其中40位(bit51-bit12)是存下一级的基地址或者PPN，bit11-bit0是各种标志位，62-52未使用，63位是XD，这是为64位系统引入的，could be used to disable instruction fetches from individual memory pages.通过restricting execution to the read-only text segment来减少buffer overflow attacks。有个小trick，为什么每个页表分9位？page size是多少，一级页表占的空间是多大？答案是page size是4KB或者4MB，linux是4KB，一级页表就是一页。9位的原因:4KB = 2^9 * 8byte，每个entry 64位也就是8byte.好了.算是说圆了至少.
对于页表在kernel 中的implementation
比如在trap里处理TLB exception 也就是TLB miss了 怎么办 如果做demand paging的话 这是必须会遇到的 因为程序开始运行的时候并不会真正把数据load到disk上，shell通过execve装载loader的时候 会删除子进程的虚拟存储段 然后创建一组新的text,data, heap, stack，这时的创建不是真正的创建而只是定义，比如vnode,offset等等先初始化，等到真正要用的时候通过exception来paging。所以如果来了个faultaddress，exception传进来说kernel你帮帮忙处理一下吧。kernel说，好的，拿地址来，假设我们用二级页表来做，kernel先把前10bit给分离出来,
(faultaddress & 0xffc00000) >>22
这个得到的就是上面例子的PTO1=1
(faultaddress & 0x003ff000) >>12
这个得到的就是上面例子的PTO2=3
从current thread可以得到正在运行进程的地址空间struct，which include the first level pagetable base address and stackbase.
关键的来了，每个进程都有个pagetable的base address，也就是之前说的CR3(这里拿CR3来说不太合适。。因为i7是四级页表，)，初始化的时候分了一页，4096来存,这个base address就是初始化返回的分的那一页的首地址。 比如i7里面的CR3 register, points to the beginning of level 1 page table. The value of CR3 is part of each process context, and is restored during each context switch.
as->as_pagetable = alloc_kpages(1);
比如PT 1base address register指向的地址是0x00080000,
那么virtual address 1,也就是第一级页表我们要找的entry的地址
0x00080000 + PTO1*4= 0x00080004
这个entry里面是什么呢，是第二级页表的base address，为啥不再拿个寄存器？kernel说道：大哥，寄存器这种奢侈的东西给你个CR3用应该知足了，后面自己想办法吧。
virtual address 2，vaddr2也就是第二级页表entry的地址：
*vaddr1 + PTO2*4
好了，*vaddr2也就是页表的内容了，其中就有我们要的20bitPPN，加上12位offset 就是物理地址
为啥我们要去知道这两个地址？*vaddr1是二级页表entry的地址，如果不为0，就代表有二级页表存在。*vaddr2就是二级页表的内容，其中有present/absent bit，R/W bit, U/S bit(determine whether the page can be accessed in user mode, protect code and data in the operating system kernel from user program)，还有最重要的physical page number,
言归正传，我们怎么check present/absent bit?简单的很呐，把*vaddr2拿来查看相应bit就行了，做起来就是个一个 & mask
上面我们知道page table不是单纯只存有physical page number，还有一些其他标志位，比如present/absent bit,这一位track哪些页在内存中存在。也就是这个virtual address是不是被缓存在DRAM里面。永远都要有个信念，kernel想方设法给我们造成假象以至于我们以为每个进程都有4G的空间，其实进程p的很多virtual address压根儿是虚的，根本没在真正物理内存内有映射。只有那些有映射的才是真正干活的。所以如果这个bit是0，那么就是这个虚拟也没有被分配物理地址。
TLB entry中也有valid bit，这一位表示是否有一个valid translation,如果这一位是1，那么很好，这个entry有我们要找的physical frame number，TLB是比较牛逼的，每个entry有virtual page number以及对应的physical frame number，只要找到了连offset什么的都不用算，直接可以得到物理地址。这和page table还是有区别的，page table entry里没有存什么virtual page number，只是用VPN做index去找entry而已。由此可见，TLB是比较奢侈的。奢侈也是有代价的，就是一般size都很小嘛。。 比如8个，16个entry，最多64个。。。确实够小。。TLB还有一位是protection bit，当对应page改变的时候，会去设置这一位，比如code段的page就是read and execute(R X)，heap段的page就是read and write(R W)。有人要问了，这TLB到底是怎么查找的。这是MMU干的活，当来了个virtual address的时候，硬件先比较virtual page number，怎么比较，很牛逼的同时也就是并行比较所有的entries。有趣的地方在于如果找不到，那么就是个miss，然后MMU就去做普通的page table lookup.然后更新TLB.相应的bit也要该表，比如modified bit.
好了，至此，多级页表已经没有秘密可言了。最后再说个address translation的optimizaiton
我们说了半天地址转换，目标就是为了得到个物理地址，得到物理地址干什么？去cache或者内存找数据啊！
所以MMU的任务是
1. 想方设法把CPU给的virtual address变成physical address
2. 把这个physical address 传给L1 cache
我们一直在分析virtual address的前20bit(32位)或者前36bit(48位)，不要忘记后面的12bit offset 我们是不会变的，MMU忙活半天拿来了PPN还是得老老实实加上这12位offset。
对于i7而言，每个cache address有64位，形成了2^64个不同的地址，我们需要用这个地址去找数据。假设L1cache是8-associative,那么就有64 sets，每个sets有8个cache line,每个line 有64byte的block，这个block里面有一个valid bit, some tag bits, and a block of data.每个physical address 有6位cache offset bits and 6 index bits.这里的6不是巧合，log2(64)=6。index bits(CI)用来找组,offset bits(CO)用来找某一行。
好了，说了半天，我们是想说一个neat trick，那就是从virtual address拿来的那12bit offset就是CI+CO,刚好也是12位，This is not accident!!!因为那12bit offset在MMU忙活找PPN的时候闲着也是闲着，CPU发现MMU用不着这12bit啊，那我就给你发个VPN你自己忙去吧。我把VPO 12bit发给L1 cache，你先找着，可以找到appropriate set,然后读出8个tags以及对应的data，等到MMU忙完了拿来physical address的时候，取出前20个tag去match这8个tag就好了,这里假设物理地址空间32位。如果是48位或者52位，减去12就是tag的位数
32bit address
64 bytes/block
8 blocks/set
Number of set: 64
Number of blocks: 64*8=512
bits of index = log2(64)=6 #index sets
bit in offset = log2(64) = 6
bits of tag = 32-6-6=20
cache capacity =512*64=32K
bits31-bit12 | bit11-bit6 | bit5-bit0
tag set index offset
offset=100 indicate that the copy of w starts at byte 4 in the block.(we are assuming the words are 4 bytes long)
---------------------------
Below is some thoughts of C program memory allocation
Why we offer static variable a separate space?
Static is the most original, simplest and most secure pattern allocation for variables. When the program is compiled, this sort of variables are allocated a unique and constant space.(Which is cool..)
So the problems like: how much space variables need? Whether current space is sufficient or not? Where should I put the variables?
The answer of all these problems are explicit at first.
So BSS and DATA segment is like the free apartment/house offered by government for government officials in China.
So, where are the local variables stored?
They are on stack. Stack is like rent house. It allow the best efficiency to use the house. When function is called, some space is allocated to it. When it returns, those space are released. Because of stack, recursion is possible for us.
Where does segmentation fault come from?
It comes from the stack!!! Stack overflow lead to segmentation fault. Continuous pushing result in page fault, then smart linux is going to find some extra space to expand the stack. But when it reach a limit(RLIMIT_STACK, 8MB), it means linux really can not tackle this. Then...stack overflow->segmentation fault.
There is another small problem, whether the expand stack gonna to shrink back or not?
No.. It is like the government budget, which is always increasing...
