OSTEP：分页的计算

第二十章：分页：较小的表

1. 对于线性页表，只要知道第一个Page的地址，存于寄存器当中，就可以通过这个地址依次陆续推算下一个或后面任意一个有效的地址范围。对于多级页表，通过多次搜索，依旧可以在只有最初的页表的地址的情况下，通过多次的偏移查询来定位到最后需要的特定地址。

2. 这里取例子说明算法，具体答案通过-c参数可直接输出

   这里以seed为0的时候为例

   首先，在README.md中可以得到以下信息

   • Page Size: 32 bytes
   • Virtual Address Space：32 KB(1024个分页 2^15)
     • 虚拟地址需要 15 bits (VPN 占 10 bit，offset 占 5 bit)
   • Physical Memory: 128个分页(2^12)
     • 物理地址需要 12 bits (PFN 占 7bit, offset 占 5 bit )
   • Virtual Address Space 的前五位对应了Page Directory的索引

   通过seed生成0对应的地址数据，用于PDE查表，内容如下

   Page Content

   page   0:1b1d05051d0b19001e00121c1909190c0f0b0a1218151700100a061c06050514
   page   1:0000000000000000000000000000000000000000000000000000000000000000
   page   2:121b0c06001e04130f0b10021e0f000c17091717071e001a0f0408120819060b
   page   3:7f7f7f7fcd7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f887f7f7f7f7f7f7f7fb9
   page   4:0b041004051c13071b131d0e1b150107080507071b0e1b0411001c000c181e00
   page   5:17131d0a1202111906081507081d1e041b1101121301171902140e070e040a14
   page   6:0000000000000000000000000000000000000000000000000000000000000000
   page   7:0000000000000000000000000000000000000000000000000000000000000000
   page   8:11101a120f10180a11151e151d0c12170a081e0a1e1a06191e08141702190915
   page   9:0000000000000000000000000000000000000000000000000000000000000000
   page  10:0000000000000000000000000000000000000000000000000000000000000000
   page  11:0910141d04011a18170e150c050c18181d1b151016051c16120d13131b11060d
   page  12:060b16191c05141d01141a0a07120d050e0c110f090b19071100160a0108071d
   page  13:19100b0e000614140f1d0e091a08121519180b0101161d0a0d16140814090b10
   page  14:1218140b000d1c0a07040f10020c141d0d0d0e060c140c12191e1b0b00120e07
   page  15:0000000000000000000000000000000000000000000000000000000000000000
   page  16:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fea7f7f7f
   page  17:0000000000000000000000000000000000000000000000000000000000000000
   page  18:7f7f7f7f7f7fab7f7f7f8e7f7f7fdd7f7f7f7f7f7f7f8b7f7f7f7f7f7f7f7f7f
   page  19:00130001061402011e0d1b060d0b050a1e170b0c081016150e011c0c0c00041a
   page  20:1a190402020c1d110807030419041a190411001a11170f151c111b0a03000719
   page  21:0b081b0e1c151e121e050d111e111a130f0c0b09061d101a1b1d070a13090417
   page  22:1212150f081b0a0e130f1d1d1c1c120f150608010500140418151e0c1c0e0a03
   page  23:1d0f030b0c0f1e1e1113140f0f091502091b071d1e110102060a03180b07010b
   page  24:0000000000000000000000000000000000000000000000000000000000000000
   page  25:03031c031b0e0e0a0c0b110a1907070e1c0016000c170d0d070e070814121c1e
   page  26:090e1d18081115180d0c170d070e1d040e130e06001513000917131004150e15
   page  27:0000000000000000000000000000000000000000000000000000000000000000
   page  28:0f1d0f0a0211070b0b17071d170e1b0b0b04180c0f0e140b1c0d0b0c171e1a0e
   page  29:17081e031b010710120c030708171c120118090a10071c050c08101113100c13
   page  30:7f7f7f7f7f847f7f7f7f977fbd7f7ff47f7f7f7f7f7f7f7f7f7f7f7f7f7f9c7f
   page  31:7f7f7f7f7f7fd07f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page  32:0000000000000000000000000000000000000000000000000000000000000000
   page  33:7f7f7f7f7f7f7f7fb57f9d7f7f7f7f7f7f7f7f7f7f7f7f7f7f7ff6b17f7f7f7f
   page  34:0413050d0c02161518101105060710190b1b16160a031d1a0c1a1b0a0f0a151c
   page  35:0000000000000000000000000000000000000000000000000000000000000000
   page  36:1d1313160c0c1400050a07130b1b110c0c150c14010d0804100f11171b0f090e
   page  37:1e0f0a0d0c100c021e1e05070d15001913081a1409101e01151a150412180c12
   page  38:0000000000000000000000000000000000000000000000000000000000000000
   page  39:1b111e171108150e160c0f001601151218081506100a1e1e06110a1e1c121615
   page  40:0d030b1007190b0709191c1d0017100307080c0e1d01151a0b07060904110700
   page  41:7f7f7f7f7f7f7f7fe57f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f8d7f7f7f7f7f
   page  42:03041501111c1015001312110c0b1e01001d050306181d000d030806140a050f
   page  43:190802041311011e0e0916000d141d171b030d00080b0a0b180519100a11050f
   page  44:7f7f7f7f7f7fcc7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fa27f7f7f7f7f7f
   page  45:7fb27fef7f7f7f7fa4f57f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page  46:0000000000000000000000000000000000000000000000000000000000000000
   page  47:070a0f1002090b0c0e0d020613190f0402040b111410110a14160c19171c0e0a
   page  48:0000000000000000000000000000000000000000000000000000000000000000
   page  49:1e0a0f0702030d13101003010b1d05080e1c1d00140714171b151a1804011610
   page  50:161b040706011a0f020d0d181704130f0004140b1d0f15040e1619060c0e0d0e
   page  51:14000f1a070a1a0511071d180d02090f1c0311151019101d12120d120b110905
   page  52:0000000000000000000000000000000000000000000000000000000000000000
   page  53:0f0c18090e121c0f081713071c1e191b09161b150e030d121c1d0e1a08181100
   page  54:1901050f031b1c090d11081006090d121008070318031607081614160f1a0314
   page  55:0000000000000000000000000000000000000000000000000000000000000000
   page  56:0000000000000000000000000000000000000000000000000000000000000000
   page  57:1c1d1602020b000a001e19021b0606141d03000b00121a05030a1d041d0b0e09
   page  58:0000000000000000000000000000000000000000000000000000000000000000
   page  59:0000000000000000000000000000000000000000000000000000000000000000
   page  60:0000000000000000000000000000000000000000000000000000000000000000
   page  61:010510020c0a0c031c0e1a1e0a0e150d09161b1c130b1e1302021701000c100d
   page  62:7f7f7fa87f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page  63:0612060a1d1b19010407181a12161902021a010601001a0a0404141e0f1b0f11
   page  64:18121708080d1e161d10111e0518181a1704141c110b1d110c13180700101d15
   page  65:7f7f7f7f7f7f7f7f7f7f997f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page  66:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fd77f7f
   page  67:0000000000000000000000000000000000000000000000000000000000000000
   page  68:121216020f060c0f0a0c16011d120511020f150d09141c1b0b1a03011e171311
   page  69:190a19020d0a0d190f1e1a03090016001b050c01090c0117160b1902010b1b17
   page  70:0000000000000000000000000000000000000000000000000000000000000000
   page  71:7f7f7f7f7f7f7f7f7f7f7f857f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page  72:180c0018050c0b030a051314000e111b0f02011a181a081402190a1d0e011c13
   page  73:0000000000000000000000000000000000000000000000000000000000000000
   page  74:0d0b1e08180d0b011a151b0d14030c06011d0604060b10041e1e040c151b0f1c
   page  75:1a1c011b00141c0f0c0a1c1c13160a041e14081e120a1b021804030816120d04
   page  76:0c11150c1b1d1e01191b041d03061d191108070c0013011702000817190f1d03
   page  77:1c061606001b1a0205071c0b190d0b171308121519141312021d16081513140b
   page  78:0e02171b1c1a1b1c100c1508191a1b121d110d141e1c1802120f131a07160306
   page  79:1e1b1516071708030e0a050d1b0d0d1510041c0d180c190c06061d12010c0702
   page  80:1b081d1c020d170d0f19151d051c1c131d071b171202000007170b18130c1b01
   page  81:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fe27f7f7f7f7f7f7f7f7f7f7f7f7ffa
   page  82:0000000000000000000000000000000000000000000000000000000000000000
   page  83:0000000000000000000000000000000000000000000000000000000000000000
   page  84:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f947f7f7f7f7fce
   page  85:7f7f7f7f7f7f7f7f9a7fbf7f7f7f7f7f7f7f7f7faf7f7f7f7f7f7f7f7f7f7f7f
   page  86:7f7f7f7f7f7f7fc57f7f7f7f7f7f7f7f7f7f7f7fca7f7fee7f7f7f7f7f7f7f7f
   page  87:1805180d170e1802011c0f1b1d14110602191b18150d09030d111c1d0c031716
   page  88:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fc47f7f7f7f7f7f7f7f7f7f7f7f
   page  89:0000000000000000000000000000000000000000000000000000000000000000
   page  90:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fc07f7f7f7f7f7f7f7fde7f7f7f7f7f7f
   page  91:7f7f7f7f7f7f7f7f7f7f7f7fa57f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page  92:0000000000000000000000000000000000000000000000000000000000000000
   page  93:0a1a1907001905181505021c12130e0412071816001c01020904070b160c080f
   page  94:1406190710140713080519110a1200040c1e0f021718181115061619170a1213
   page  95:0a1d0f1d1e1915040012151d10151406131e0315130b18001b190e030e12070f
   page  96:7f7f7f7f7f7f7f7f7f7f7f7f7f7fb67f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page  97:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fc87f7f7f7f7fe77f7f7f7f7f7f7f7f7f
   page  98:15191803171a170e1503170818130f100201001804030b1e1b0919020c111e01
   page  99:090b1304150b1204140a0e0c0e1509140109170113000e1b0010021a15171400
   page 100:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fa77f7f7f7f7f7f7f7f7f7fe37f7f
   page 101:0e0a00010b061005061416091a070a16011c020e1601191e0e030203170c1c0d
   page 102:1d031b0116000d1a0c1c1612050a0c121e080f1c0a13171317061d0512091309
   page 103:1e171c061012190e180c121a181400050f07021a1d090c19011303081901010c
   page 104:7f7f7f7f7f7f7f7f7f7f7f7f80aa7f7f7f7f7f7f7f7f7f7f7f7f7f7ff07f7f7f
   page 105:b37f7f7f7f7f7f7f7f7f7f7f7f937f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page 106:160a000e1001110a00050310011c1a1d091c1e170814120c090103040e131701
   page 107:7f7f7f7f7f7f7f7f7f7f7f7f7f7ff17f7f7f7f7f7f7f7f7ff37f7f7f7f7f7f7f
   page 108:83fee0da7fd47febbe9ed5ade4ac90d692d8c1f89fe1ede9a1e8c7c2a9d1dbff
   page 109:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f827f7f7f7f7f7f7f7f7f7f7f7f7f7f
   page 110:1614041e0c120b010e0401131303110a0b180f1b120e130a03151318031c181c
   page 111:08000115111d1d1c01171514161b130b10061200040a18160a1301051e080c11
   page 112:19051e1302161e0c150906160019100303141b081e031a0c02080e181a041014
   page 113:1d07111b1205071e091a181716181a01050f06100f03020019021d1e170d080c
   page 114:0000000000000000000000000000000000000000000000000000000000000000
   page 115:110601040d1406151a170d141e1b0a1505110b0d0d141a0e0417171d0c0e101b
   page 116:0a130b11150f14171a05060f0f19101b180f190e0a0d0e1401161e0e02060307
   page 117:1b0a170019111d0b130a18121e000401031c1d0e1d19181705110d1d05051404
   page 118:1119021a1c05191a1b101206150c00040c1b111c1c02120a0f0e0e03190f130e
   page 119:0000000000000000000000000000000000000000000000000000000000000000
   page 120:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fcb7f7f7f7f7f7f7f7f7f7f7f7f7f
   page 121:0000000000000000000000000000000000000000000000000000000000000000
   page 122:051e0312041b1d18090717090d01040002020d1116040d13020d0b1d010c0c16
   page 123:0000000000000000000000000000000000000000000000000000000000000000
   page 124:0000000000000000000000000000000000000000000000000000000000000000
   page 125:0000000000000000000000000000000000000000000000000000000000000000
   page 126:7f7f7f7f7f7f7f7f8ce6cf7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f967f7f7f7f7f
   page 127:7f7f7f7f7f7f7f7f7f7f7f7f7f7f7f7fdf7f7f7f7f7f7f7f7f7f7f7f7f957f7f

   并且根据模拟生成的PDBR: 108可以知道Page 108对应的内容即是第一级PDE的映射

   接下来就可以进行计算了，这里取一个vaild和invaild的答案分析计算过程

   Virtual Address 611c:
     --> pde index:0x18 [decimal 24] pde contents:0xa1 (valid 1, pfn 0x21 [decimal 33])
       --> pte index:0x8 [decimal 8] pte contents:0xb5 (valid 1, pfn 0x35 [decimal 53])
         --> Translates to Physical Address 0x6bc --> Value: 08
   Virtual Address 3da8:
     --> pde index:0xf [decimal 15] pde contents:0xd6 (valid 1, pfn 0x56 [decimal 86])
       --> pte index:0xd [decimal 13] pte contents:0x7f (valid 0, pfn 0x7f [decimal 127])
         --> Fault (page table entry not valid)

   Virtual Address 611c

   1. 将611c按二进制转换为Virtual Address Space对应的 15 bits 为 11000 01000 11100。对PDE分割前五位有11000(decimal 24)

   2. 这个时候对最顶层的PDTR对应的Page 108进行查表操作

   首先可以通过Page Content得到Page 108内容如下

   Page 108: 83 fe e0 da 7f d4 7f eb be 9e d5 ad e4 ac 90 d6 92 d8 c1 f8 9f e1 ed e9 a1 e8 c7 c2 a9 d1 db ff
   Index:    0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

   通过查表找到对应Index的内容可以知道24(11000)对应位置的内容是a1，转换为二进制为1010 0001，读取最高位为1可以知道是vaild。再通过后面的0010 0001转换为十进制为33，因此再继续查询Page 33的内容

   Page 33:7f 7f 7f 7f 7f 7f 7f 7f b5 7f 9d 7f 7f 7f 7f 7f 7f 7f 7f 7f 7f 7f 7f 7f 7f 7f f6 b1 7f 7f 7f 7f
   Index:  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

   611c的[1-5]位为PDE，这时我们则需要通过[6-10]位来通过PTE寻找VPN对应的PFN地址。由611c为11000 01000 11100可以知道这次为01000即(decmial 8)，对照上面page 33可以发现第八个对应的内容为53，因此可以知道最终VPN对应上了PFN的Page 53。最后再通过offset的11100，配合Page 53对应的二进制PFN地址11 0101结合offset的11100有110101 11100，也就是最后答案的0x6bc，其中通过offset在Page 53中查表可以找到对应的 Value 为 08

   Virtual Address 3da8

   1. 和611c同理，将3da8转为二进制01111 01101 01000，得到pde index为01111(15)，对应的Value为0xd6(1101 0110)，通过1101 0110最高位可以知道目标分页为vaild，去掉vaild bit可以得到索引的pte为0x56(0101 0110 | 86)

   2. 检索Page 86，由PTE index为01101可以找到对应的Value为0x7f(0111 1111)由于最高位为0，因此是invaild，也就是说pte无效，无法访问

   其他的情况也是依次类推，即可算出结果是否有效

3. 根据个人理解，具体缓存hit或miss的概率主要由对应内存上的数据决定。对于访问次数较多的内容hit缓存加快速度的概率自然更高；而对于不重复的多次查询（比如上面的练习），自然miss的概率会更高。因此对于进程来说，如果能将数据尽量集中在某一块分页上则能有效提高内存访问和处理的速度。