OSTEP:分页的计算

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

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

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

    这里以seed0的时候为例

    首先,在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
    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    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的映射

    接下来就可以进行计算了,这里取一个vaildinvaild的答案分析计算过程

    1
    2
    3
    4
    5
    6
    7
    8
    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内容如下

    1
    2
    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的内容

    1
    2
    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地址。由611c11000 01000 11100可以知道这次为01000(decmial 8),对照上面page 33可以发现第八个对应的内容为53,因此可以知道最终VPN对应上了PFNPage 53。最后再通过offset11100,配合Page 53对应的二进制PFN地址11 0101结合offset11100110101 11100,也就是最后答案的0x6bc,其中通过offsetPage 53中查表可以找到对应的 Value08

    Virtual Address 3da8

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

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

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

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


OSTEP:分页的计算
https://halc.top/p/c1ec22c4
作者
HalcyonAzure
发布于
2022年5月12日
许可协议