OSTEP NOTES & HW：虚拟内存

基址加界限机制（base and bound）

一个实现虚拟内存的初步机制：基址加界限机制，只需要很少的硬件逻辑，就可以将虚拟地址和基址寄存器加起来，并检查进程产生的地址没有越界

• 有时又称为动态重定位（dynamic relocation）
• 要求每个 CPU 需要两个硬件寄存器：基址（base）寄存器和界限（bound）寄存
  器，有时称为限制（limit）寄存器，它们被包含在内存管理单元（Memory Management Unit，MMU）
• 这组基址和界限寄存器，让我们能够将地址空间放在物理内存的任何位置，同时又能确保进程只能访问自己的地址空间
• 进程产生的所有内存引用，都会被处理
  器通过以下方式转换为物理地址：physical address = virtual address + base
• 基址寄存器将虚拟地址转换为物理地址
• 界限寄存器提供访问保护。进程需要访问超过这个界限或者为负数的虚拟地址，CPU 将触发异常，进程最终可能被终止

基址加界限机制的弊端是，容易造成内部碎片（internal fragmentation），指的是已经分配的内存单元内部有未使用的空间（即碎片）

如果我们将整个地址空间放入物理内存，那么栈和堆之间的空间并没有被进程使用，却依然占用了实际的物理内存

受限直接访问（Limited Direct Execution，LDE）

• 程序指令直接访问硬件，只在一些关键点，如系统调用或时钟中断由操作系统介入保持对硬件的控制

基于硬件的地址转换（hardware-based address translation）

• 硬件对内存访问进行处理（即指令获取、数据读取或写入），将指令中的虚拟（virtual）地址转换为数据实际存储的物理（physical）地址，每次内存引用都会将应用程序的内存引用重定位到内存中实际的位置
• 每个进程都具有一个假象：具有机器的、连续的所有的内存，但是本质上进程所拥有的只是虚拟地址，真实的物理地址由操作系统进行分配，从虚拟地址到真实物理地址的过程被称为重定位

分段（segmentation）

如上所说，如果我们将整个地址空间放入物理内存，那么栈和堆之间的空间并没有被进程使用，却依然占用了实际的物理内存（可以参照上图）

怎样支持大地址空间，同时栈和堆之间（可能）有大量空闲空间？为了解决这个问题，分段（segmentation）的概念应运而生

分段机制需要地址空间内的每个逻辑段都有一对基址和界限寄存器，一个段只是地址空间里的一个连续定长的区域（代码、栈和堆），分段能够将不同的段放到不同的物理内存区域，避免了虚拟地址空间中的未使用部分占用物理内存，栈和堆之间没有使用的区域就不需要再分配物理内存

那么问题又来了，如何知道段内的偏移量？以及地址引用了哪个段？栈和堆的增长方向相反，又该如何偏移？如何表示地址共享从而提升效率？

• 可以将虚拟地址表示为[段标志][段内偏移]，用虚拟地址的开头几位段标志来标识
  不同的段，比如：如果前两位是 00，硬件就知道这是属于代码段的地址，用代码段的基址和界限来重定位到正确的物理地址；如果前两位是 01，则是堆地址，使用堆的基址和界限
• 段寄存器可以增加硬件标记位实现保护，比如某一位对应是正/反向增长。某一位表示保护位（rwx），检查特定访问是否允许。如果用户进程试图写入只读段，或从非执行段执行指令，硬件会触发异常，让操作系统来处理出错进程

段寄存器的值（有保护）

段	基址	大小	是否反向增长	保护
代码	32KB	2KB	1	读—执行

操作系统的工作

• 有了分段之后，操作系统在上下文切换时应该做到，将各个段寄存器中的内容保存和恢复
• 每个进程都有自己独立的虚拟地址空间，操作系统必须在进程运行前，确保这些寄存器被正确地赋值

分段的利与弊

• 快速，简单。分段要求的算法很容易，很适合硬件完成，地址转换的开销极小
• 代码放在独立的段中，这样的段就可能被多个运行的程序共享
• 增加了外部碎片

保护模式下的分段

保护模式下的段值只是一个索引，这个索引称为段选择符，即段寄存器的作用是用来选择段描述符，而段描述符包含了段的特征

段选择符

┌──────────────────────────┬────────┬────────┐
│                          │        │        │
│                          │        │        │
│                          │        │        │
│  描述符索引（索引域）      │ TL     │   RPL  │
│                          │        │        │
│                          │        │        │
└──────────────────────────┴────────┴────────┘

• 索引域：指向描述符表中相应的描述符
• 选择域：如果 TI=1，就从局部描述符表中选择相应的描述符，如果TI=0，就从全局描述符表中选择描述符
• RPL(Requestor Privilege Level)：只有请求者特权级RPL高于(数字低于)或等于相应的描述符特权级DPL，描述符才能被存取，这就可以实现一定程度的保护

段描述符

每个段由一个段描述符表示，它描述了段的特征。段描述符存放在全局描述符表（GDT）或局部描述符（LDT）表中

堆上内存分配

void * malloc(size t size)

• size是请求的字节数。函数返回一个指针（没有具体的类型，在 C 语言的术语中是 void 类型），指向size大小（或较大一点）的一块空间，void* 类型可以强制转换为任何其它类型的指针
• 分配成功则返回指向被分配内存的指针，失败返回空指针NULL（要注意错误处理）
• malloc后的需要配合free使用，否则会导致内存泄露（虽然进程退出的时候os会回收这部分内存，但是不free仍是一种不好的行为，比如web服务器这种长时间运行的进程的内存泄露是很严重的， 并且很难排查）

void free(void *ptr)

• 函数接受一个指针，不需要指定这块空间的大小，即可释放对应的内存块
• 在只传入一个指针的情况下，库必须能够弄清楚这块内存的大小

Linux内存布局

空闲链表

空闲链表记录了堆中的哪些空间还没有分配

假设这是堆中空间布局

+----------------------------+
|        |         |         |
| used   |  free	 | used    |
+----------------------------+
0       10        20         30

那么对应的链表结构为：

                         +------------+                 +-------------+                   
                         |            |                 |             |                   
                         |  addr:0    |                 |   addr:20   |                   
 head     ----------->   |  len:10    |    --------->   |   len:10    | ---------->   NULL
                         |            |                 |             |                   
                         +------------+                 +-------------+                   

typedef struct node_t {
    int size;
    struct node_t *next;
} node_t;

当我们使用malloc(20)在堆中分配出20个字节的空间时，所占用的不仅仅是20字节，因为头块（header）中保存一点额外的信息

typedef struct header_t {
    int size;//所分配空间的大小
    int magic;//幻数，提供完整性检查
} header_t;

void free(void *ptr) {
    header_t *hptr = (void *)ptr - sizeof(header_t);//得到头块的位置
}



       hptr

               ─────────►┌────────────┐
                         │            │
                         │  size:20   │  header_t
                         │            │
       ptr     ────────► ├────────────┤
                         │            │
                         │  magic     │
                         │            │
                         ├────────────┤
                         │            │
                         │            │
                         │            │
                         │            │  allocated bytes
                         │            │
                         │            │
                         └────────────┘

分页

基本概念

分页：将内存分割成固定大小的单元，每个单元称为一页

虚拟地址：[虚拟页号][页内偏移]

• 将虚拟页映射到物理页，偏移得到物理地址
• 虚拟页面号（virtual page number，VPN）
• 物理页号（physical page number，PFN）

页表

• 页表基址寄存器（page-table base register）包含页表的起始位置的物理地址
• 记录地址空间的每个虚拟页放在物理内存中的位置，是一种数据结构，用于将虚拟地址（或者实际上，是虚拟页号）映射到物理地址（物理帧号）
• 每个进程保存一个数据结构，称为页表，页表的主要作用是为地址空间的每个虚拟页面保存地址转换（address translation）

页表大小的考虑

对于32 位地址空间，假设一个页大小为4KB，那么：

• 一个页有2^12个字节，也即是页内偏移为12位
• 2^32 / 2^12 = 2^20 ，也即是需要2^20个页

因此，对于每个进程，操作系统需要为其维护2^20个页表转换，假设一个转换需要4字节，则每个进程需要2^22字节，也即是4MB的内存，对于多进程来说，这个开销是十分巨大的

页表项

最简单的页表实现是线性页表，它的本质是一个数组也即是通过虚拟页号（VPN）检索该数组，并在该索引处查找页表项（PTE），找到期望的物理帧号（PFN）

一个 x86 架构的示例页表项：

• 存在位（P），表示该页是在物理存储器还是在磁盘上（即它已被换出，swapped out）
• 读/写位（R/W）
• 访问位（A），有时用于追踪页是否被访问，也用于确定哪些页很受欢迎，因此应该保留在内存中
• 脏位（D），页面被带入内存后是否被修改过
• 页帧号（PFN）

TLB

地址转换旁路缓冲存储器 （translation-lookaside buffer，TLB）

• 是频繁发生的虚拟到物理地址转换的硬件缓存（cache）
• 工作工程：对于每次内存访问，先从虚拟地址中提取页号（VPN），查看tlb是否命中，如果未命中，则访问页表（这会造成巨大的开销）

页表与TLB的有效位：

• 页表中页表项（PTE）若被标记为无效，就意味着该页并没有被进程申请使用，正常运行的程序不应该访问该地址
• TLB 的有效位不同用来标志 TLB 项是不是有效的地址映射

进程切换时，对于不同的进程，TLB的内容没有意义。倘若上下文切换的时候清空 TLB，那么会导致未命中，造成大量的开销。因此可以给TLB加上地址空间标识符（Address Space Identifier，ASID），从而标志不同的进程

考虑到换入换出开销，可以替换最近最少使用（least-recently-used，LRU）的项