No, no, no. Now you can’t rely on those ‘malloc()’ stuff anymore.

Always tresures things that already lost. All of us.

0x00 Partial Translations of Intel 80386 Manual (I)

Chapter 5 Memory Management

80386 通过两步将逻辑地址(i.e. 程序看到的地址)转换为物理地址(i.e. 实际上的内存中的地址):

  1. 段转换,这一步将逻辑地址(包含一个段选择子和段偏移量的地址)转换为线性地址。
  2. 页转换,这一步将线性地址转换为物理地址。这一步不是必要的,看你分页开没开。

对于应用程序来说,这两步是不可见的。下图描述了在一种抽象的转换流程。

接下来的内容将描述这两步转换过程,但是关于内存保护的内容不会提及。它们将在第六章被阐述。

Chapter 5.1 Segment Translation

下图给出了一个更加详细的段转换的过程。

Segment Translation

5.1.1 Segment Descriptors

段描述符提供了处理器需要的将逻辑地址转换为线性地址需要的信息。下图展示了两种一般段描述符的格式。

Two General SegmentDescriptor Format

其中:

BASE 定义了段在线性地址空间中的位置。它在一个描述符中被拆成了三段,处理器在解析时会将其合并为一个32位的地址进行使用。

LIMIT 定义了段的大小。注意LIMIT有两种单位,一种是以byte为单位,此时这个段的大小最大为1MB。另外一种是以4KB为单位,这时候这个段的最大大小为4GB。如果选择了这种单位,那么在载入时这个LIMIT段的内容实际上会被右移12位之后再处理。

选择LIMIT单位的方法是G(ranularity) Bit ,即上图的G。0 => 1byte 1=>4KB

TYPE 即描述符的类型。

D(escriptor)P(rivilege)L(evel) 即描述符的权限,用于保护机制。

P(resent) bit 描述符是否存在。若该位为0,则当试图使用这个描述符时,CPU会产生一个异常。这是一个很有用的特性,常被用在虚拟内存的实现当中。

既然描述符Present为0,那么自然有一些魔幻的用法。最常见的是可以用来存储一些额外数据,比如:

Magic Use of Non-Present Desc

标记了 AVAILABLE 的位置都可以用来存储数据。

A(ccessed) bit 当这个描述符被访问的时候,CPU将设置这个位。通过周期性地清除和检测这个位,可以达到统计使用频率的作用。

5.1.2 Descriptor Tables

处理器中一共有两种描述符表,分别是

  • 全局描述符表(GDT),其地址和界限存储在GDTR寄存器中。
  • 局部描述符表(LDT),其地址和界限存储在LDTR寄存器中。

一个描述符表其实就是简单的描述符的内存数组。每个描述符长度为8个字节,一个描述符表的长度不定,但是最大存储8192(2^13)个描述符。

需要注意的是,GDT的第一个描述符(index=0)处不会被处理器使用。

使用LGDT/SGDT/LLDT/SLDT指令可以访问描述符表寄存器。

Descriptor Tables

5.1.3 Segment Selectors

段选择子,是用来选择对应的段描述符的数据结构。

Segment Selectors

其中:

INDEX - 描述符在描述符表中的index。

T(able)I(ndicator) - 0: 全局描述符表(GDT); 1:局部描述符表(LDT)

RPL 请求者的权限等级,用于保护机制。

由于 GDT 中 INDEX=0的描述符不被使用,所以INDEX=TI=0的描述符在被用来进行内存访问的时候会触发一次异常。这个特性可以用于初始化未使用的段寄存器或捕获异常的内存访问。

5.1.4 Segment Registers

Segment Registers

为了加快访存的速度,每个段寄存器都由两部分组成:显式部分(16位的段选择子)和隐式部分(对应的段描述符)。在显式部分被修改后,处理器会自动将对应的描述符载入隐式部分,这样在访存的时候,就不需要重复地去访问段描述符表。

5.2 Page Translation

接下来描述页转换过程。

在80386中,页转换不是必须的。它仅当CR0寄存器的PG bit 被设置的时候才生效。

当它生效时,它将作为内存地址转换的第二步,将线性地址转换为物理地址,并且提供基于分页的保护机制以及虚拟内存等特性。

5.2.1 Page Frame

一个页面是一个由连续的4KB大小的物理内存组成的结构。页面大小是固定的,并且按4KB对齐。

5.2.2 Linear Address

线性地址的结构如图所示:

Linear Address

其中:

DIR 是次级页表在初级页表中的index

PAGE 是页面在次级页表中的index

OFFSET 是所访问的地址在页面中的偏移。

基于以上的说明,现在给出更加详细的页转换过程图表:

Page Translation Process

5.2.3 Page Tables

一个次级页表就是一个简单的32位的页说明符的数组。由于一个次级页表本身必须包含在一个页面内,所以它最多能够含有1024个页说明符。

显然的,一个初级页表与次级页表的结构并没有什么不同,只不过里面包含的说明符指向的页面全都是次级页表所在的页面。

当前使用的初级页表的物理地址将会被保存在CR3寄存器中,这个寄存器也叫做P(age)D(irectory)B(ase)R(egister)

5.2.4 Page Table Entries

Page Table Entries

其中:

Page Frame Address 即页面的起始地址。 由于页面按4KB对齐,所以起始地址的最后12位总是0。

AVAIL 即这一部分是没有被使用的,可以被用于其他用途。

P(resent) 指的是这个页面是否能被用于地址转换。如果它被使用了,则处理器会抛出一个异常。当Present=0时,这个说明符的其余部分可以被用于其他用途。

D(irty) & A(ccessed) 将在对应的页面被修改/访问的时候被设置,但是不会被硬件清除。这个特性可以用于虚拟内存等。注意当访问时,初级页表和次级页表的Accessed都会被正确设置,但是当修改时,仅次级页表的Dirty会被正确设置。

R(ead)/W(rite) & U(ser)/S(upervisor) 用于页级保护机制。

5.2.5 Page Translation Cache

为了加快内存地址转换的速度,处理器将会存储一部分页表数据在一个缓存中。只有当缓存中没有对应的页面数据时,才会访问页表。

当页表变化时,必须手动刷新缓存。有两种方式进行缓存刷新:

  • 使用MOVCR3寄存器赋值。
  • 切换到一个有着不同CR3的任务。

5.3 Combining Segment and Page Translation

总结一下,80386的两步地址转换的所有步骤:

80386 addressing mech

通过不同的段机制和页机制组合,可以派生出多种内存管理方式。

在这里不再详述。

Chapter 6 Protection

6.1 Why Protection?

In the early ages of computer sciences, there are still people held questions on this.

Now, I believe that there’s nobody out there still thinking we don’t need this.

If ANY, recall the days when we wrote buggy programs.

6.2 Overview

80386的保护机制包括以下5个方面:

  1. 类型检查
  2. 限定检查
  3. 地址区域限制
  4. 入口点限制
  5. 指令集限制

每个访存指令都会被硬件检查,以确保满足以上全部要求。检查过程会与地址转换同时并行地执行,所以没有性能损失。

不满足条件的访存会触发一个异常。

6.3 Segment-Level Protection

所有的5个方面都会应用于段级保护。

这一级保护以段为基本单位,即段描述符保存所需的所有信息。

处理器会在载入段选择子到段寄存器和每次内存访问时进行检查。

6.3.1 Descriptors Store Protection Parameters

回忆段描述符的结构……

Segment Desciptor Protection Info

  • 类型检查

对数据段/代码段来说,有如下的限制:

  1. W限制了一个数据段能否被修改(Write)
  2. R限制了一个代码段能否被执行

对系统段来说,它的TYPE信息如下表。

  Table 6-1. System and Gate Descriptor Types

  Code      Type of Segment or Gate

  0       -reserved
  1       Available 286 TSS
  2       LDT
  3       Busy 286 TSS
  4       Call Gate
  5       Task Gate
  6       286 Interrupt Gate
  7       286 Trap Gate
  8       -reserved
  9       Available 386 TSS
  A       -reserved
  B       Busy 386 TSS
  C       386 Call Gate
  D       -reserved
  E       386 Interrupt Gate
  F       386 Trap Gate

在以下的情况会发生类型检查:

  1. 当一个段选择子被载入段寄存器时,会阻止类型不匹配的段被载入到特定的段寄存器。
  2. 当一个指令需要访问某个段寄存器所指向的段时,会阻止不允许的指令。
  • 界限检查

段的LIMIT有两种方式被解释:

E(xpand down)被清除时,可以访问的区域是BASE~BASE+LIMIT-1

E被设置时,可以访问和不可以访问的区域将被反转。但是此时G不再起作用,而是B来决定最大范围是64KB或4GB。

  • 权限等级检查

名词解释:

  • DPL: 描述符权限等级,即描述符结构上的那个。
  • RPL: 请求源权限等级,在选择子上,代表使用选择子的过程的权限等级。
  • CPL: 执行中权限等级,处理器内部维护。一般来说,等于正在执行的段的DPL。

在访问另外一个段的时候,处理器会自动对比CPL以及其他一些权限等级以决定是否能够访问。接下来的内容将详细说明这部分的内容。

6.3.2 Restricting Access to Data

在一个选择子被载入数据段寄存器(DS, ES, FS, GS, SS)时,处理器会自动检查权限等级。

条件为:只能装载DPL>=max{CPL,RPL}的段的段选择子进入数据段寄存器。换句话说,代码只能访问来自相等或更低优先权的数据。

我们也可以从代码段读取数据。但是,没有任何一种手段能向一个代码段里写入数据。以下是读取的方法:

  • 将一个可读(R)且可执行(TYPE=EXECUTABLE)的段载入数据段寄存器。
  • 使用CS Override Prefix来直接访问一个已经载入CS的代码段。
6.3.3 Restrcting Control Transfers

在80386中,控制流转移可以通过 JMP/CALL/RET/INT/IRET 和异常/中断机制完成。这里主要讨论JMP/CALL/RET导致的控制流转移。

近跳转指令仅在当前代码段中进行移动,所以只会进行界限检查。

远跳转指令需要访问其他的代码段,所以处理器将会进行权限检查。以下可行的远跳转指令目标:

  • 另一个可执行段
  • 一个调用门描述符

当目标为另一个可执行段时,进行的权限检查如下:

  • DPL == CPL
  • C(onforming) set + DPL<=CPL

当一个可执行段的C(onforming)被设置时,这个段会被按照调用时的CPL继续执行,而不是变更为该段的DPL

6.3.4 Gate Descriptors Guard Procedure Entry Points

为了提供控制流在不同权限级之间的转移的保护机制,80386使用了门描述符。一共有4种门描述符,分别是:

  • 调用门描述符
  • 陷阱门描述符
  • 中断门描述符
  • 任务门描述符

现在我们主要讨论调用门描述符。

Call Gate Descriptors

其中:

SELECTOR+OFFSET 指定了对应过程的入口点。在这种情况下,远跳转指令的操作数不再是段选择子+offset,而改为选择一个门描述符,并且offset被忽略。

门描述符可以被用于以更小或相等的优先级来执行一个过程。不过仅有CALL指令能用于跳转到更小优先级。

权限检查条件为:

MAX{CPL,RPL} <= gate DPL 且

target DPL (< for CALL)= CPL

当使用call跳转到一个新的权限等级时,一个权限间转换会被产生。

为了保证系统正确性,每个权限等级有它们自己的栈空间。同一权限等级的不同人物之间可以指定不同的TSS,这使得它们之间也有自己的栈空间。而操作系统负责分配地址给这些栈空间。

当发生权限间转换时,处理器将从当前任务的TSS载入目标权限等级的SS,此时要求:目标栈段必须有足够的空间去包含以下的内容:原先的SS:ESP,返回地址,以及所有的参数和局部变量,并且这个段的DPL必须等于目标权限等级。

在这种情况下,复制的参数数量来自门描述符的COUNT字段,单位为双字,最大为31个。

具体的步骤如下:

  • 检查大小,不足则抛出stack fault, error code=0
  • 将原先的SS:ESP值以双字压入新栈
  • 复制参数
  • 将原先的CS:EIP压入新栈

New Stack Content After Interlevel Calls

(如果31个双字参数不够用,可以使用保存的SS:ESP来访问剩下的参数。不过……你一定在开玩笑吧?)

当从一个远CALL指令返回时,处理器会将原先保存的返回地址从栈中弹出,并且在实际跳转之前执行权限检查。

具体的步骤如下:

  • 做以下检查,并将CS:EIP和SS:ESP弹栈并设置。
  Table 6-3. Interlevel Return Checks

  SF = Stack Fault
  GP = General Protection Exception
  NP = Segment-Not-Present Exception

  Type of Check                                  Exception   Error Code

  ESP is within current SS segment               SF          0
  ESP + 7 is within current SS segment           SF          0
  RPL of return CS is greater than CPL           GP          Return CS
  Return CS selector is not null                 GP          Return CS
  Return CS segment is within descriptor
    table limit                                  GP          Return CS
  Return CS descriptor is a code segment         GP          Return CS
  Return CS segment is present                   NP          Return CS
  DPL of return nonconforming code
    segment = RPL of return CS, or DPL of
    return conforming code segment <= RPL
    of return CS                                 GP          Return CS
  ESP + N + 15 is within SS segment
  N   Immediate Operand of RET N Instruction     SF          Return SS
  SS selector at ESP + N + 12 is not null        GP          Return SS
  SS selector at ESP + N + 12 is within
    descriptor table limit                       GP          Return SS
  SS descriptor is writable data segment         GP          Return SS
  SS segment is present                          SF          Return SS
  Saved SS segment DPL = RPL of saved
    CS                                           GP          Return SS
  Saved SS selector RPL = Saved SS
    segment DPL                                  GP          Return SS
  • 根据RET指令的操作数调整原先的SS:ESP,但是不立即进行界限检测。

  • 检查DS,ES,FS,GS段寄存器的内容,并将所有不符合权限要求的段寄存器设置为空选择子。

6.4 Page-Level Protection

以下两种权限控制被应用在页级保护上:

  • 地址空间限制
  • 类型检查
6.4.1 Page-Table Entries Hold Protection Parameters

页说明符中,仅有R/WU/S两个位用于保护机制。

U/S=0 => Supervisor,即系统级软件

U/S=1 => User,即用户级软件

当前的U/S状态与当前的CPL有关。当为0,1或2时,代表Supervisor,当为3时,代表User。

User无法访问Supervisor权限的页面。

R/W=0 => 只读

R/W=1 => 读写

这个就比较清晰了,不再赘述。

当访问一个页面时,初级页表和次级页表的对应项的权限信息都会被正确检查。

以下的操作会无视CPL而被视作最高权限来进行权限检查:

  • 读取 LDT, GDT, TSS, IDT
  • 在跨权限级的CALL/INT中读取内部栈

6.5 Combining Page and Segment Protection

在权限检查过程中,会首先检查段权限,再检查页权限。

0x01 Setup Environment

在开始写代码之前,先略微调整一下工作环境w

之前说的,通过降级gcc和单独编译qemu的方法已经弃用!

现在使用的是,environment modules + zhwkpkg 安装特殊版本的gccqemu !

attach.imzhwk.com上的包名分别是gcc-6-josqemu-jos,相信大家一看就会怎么用了w

GNUmakefilepacman.conf的改动自然也要还原w

对了,备注一下编译qemu踩的最新坑(

除了上次说的所有坑以外,因为内核升级,所有struct ucontext都需要改为ucontext_t哦(

0x02 Physical Page Management

为了能够以页为单位管理物理内存,我们需要进入真正的分页模式,并且有一个可用的物理页管理器。

这个简单的物理页管理器位于kern/pmap.c,主要提供以下函数:

  • boot_alloc() 当未完成任何初始化工作时,强行进行必须的页面分配工作(如为二级页表、空闲链表等分配页面)。
  • mem_init() 用于初始化二级页表。
  • page_init() 用于初始化空闲页面链表
  • page_alloc() hmmm..你觉得呢
  • page_free() 就不用详细描述了吧

具体的实现不再详述,下面分别说一下我自己对这几个函数的实现思路:

boot_alloc()

由于使用boot_alloc分配的页面不需要free,所以实现很简单:直接强行分配ROUNDUP(last_free+nbytes,PGSIZE)个页面就可以了,之后递增last_free。

mem_init()

这个函数接下来还会用到,这里只是要求实现一个使用boot_alloc分配一块空间来存储所有的页面结构体。直接调用boot_alloc再memset就好,非常简单。

这里比较有意思的是这一句:

kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;

这句话干了什么事情呢?

它把初级页表自己加入了自己当中。也就是说,当访问UPVT+secondary_pgtable+offset的时候,这个secondary_pgtable将在这个kern_pgdir中进行查找。也就是说,这个初级页表同时充当了次级页表。非常魔幻的操作(

page_init()

这个函数要求我们将所有的空闲页面链入空闲页面链表。

但是哪些页面是空闲的呢?

这里着重解释一下第四项:内核到底在哪?

(不过它实际存在的内存位置并不重要,重要的是,它的最顶部在哪?

答案是PADDR(boot_alloc(0))

这里一个很容易令人想不明白的问题是内核栈空间在哪里?

答案是在之前boot_alloc里面那个end tricks的下面。回看entry.S,发现用于初始化栈顶指针ESP的是一个叫bootstacktop的玩意。再看这个玩意,发现有一个.SPACE KSTKSIZE的东西,而它就是用于在可执行内部给内核栈分配空间的。那么,既然可执行内部已经分配完毕了,而那个end tricks的作用是指向可执行文件载入的尾部,那么自然,栈也在它的下面了。

page_alloc() & page_free()

这两个都是简单的链表操作了。不再详述。

0x03 Virtual Memory

ASSUME you have previously read the translated version of Intel 80386 Manual(look up!),

as the terminology will be the same when describing stuffs.

What Does JOS Kernel Memory Mapping Looks Like?

首先,在JOS当中,段转换机制被一个base=0,lim=MAX的段给实际上禁用了。

Note I’m saying “practically”, as there’s no way we can actually “disable segmentation” in 80386. Fack Intel.

也就是说,虚拟地址实际上等于线性地址。我们需要处理的,只有线性地址转换到物理地址的步骤,即页级转换。

当然基于段的保护机制仍然在生效——不过通过正确地设置段权限,可以让它显得“毫无影响”。

在lab1的part3,我们设置了一个“映射”式的页表,让内核能运行在高位虚拟地址,但是只有4MB大小。

接下来要做的是扩充这个映射,让它映射256M大小的内存到高位地址,并且设置其他的一部分映射。

Address Types in Source Code

简单总结一下:

+-- C Type --+-- Addr --+--  Base Type --+
|    TYPE*   |   Virt   |     Pointer    |
|  uintptr_t |   Virt   |     uint32_t   |
| physaddr_t |   Phys   |     uint32_t   |
+------------+----------+----------------+

My Answer to THAT QUESTION (1)

uintptr_t, 显然地。

  • Hint: char* value可以被解引用。

Page Table Management

接下来我们需要实现一些用于管理页表的函数(位于pmap.c),这些函数包括:

  • pgdir_walk(): 给定 pgdir(初级页表) 和 虚拟地址,获得对应的pte(次级页表项)
  • boot_map_region(): 在给定 pgdir 创建从 va~va+size 到 pa~pa+size 范围的映射,权限为perm
  • page_lookup(): 返回映射到给定虚拟地址的物理页面
  • page_remove(): 解除给定物理页面与给定虚拟地址之间的映射
  • page_insert(): 在给定的 pgdir 创建 给定物理页面 与 虚拟地址 之间的映射,权限为perm。 这个与上一个的要求略有不同,请自行阅读代码注释w

接下来在这里简述各个函数的实现思路:

pgdir_walk()

这个其实满简单的,虽然代码写了不少(笑

注意阅读mmu.h,里面有非常多有用的宏。

还需要注意页表项里面的base是物理地址,但是返回的pte_t*应是虚拟地址。

注意处理不存在空闲页的情况。

boot_map_region()

也非常简单。需要注意的是size可能多于1个页面大小,使用循环解决这个问题。

page_lookup()

稍微结合一下pgdir_walk和pa2page就可以完成,不再赘述。

page_remove()

活用page_lookup()即可快乐地写好。需要注意page_decref()当pp_ref==0时会自动帮你释放。

page_insert()

这里说一下那个elegant way(

如果你写的很垃圾,这里是有可能会爆的,问题在于你的page_remove如果太靠前,会导致仅有一个引用的物理页面被page_remove释放,但是这里是没法去申请物理页面的,导致这个物理页面被错误地认为空闲,但是却实际存在于页表中。

那么这是elegant way(我觉得是这样的

	// set up mapping
	pte_t* pagetab_entry = pgdir_walk(pgdir,va,true);
	if(pagetab_entry == NULL) return -E_NO_MEM;
	// increase ref cnts
	pp->pp_ref += 1;
	// remove former mappings when necessary
	page_remove(pgdir,va);
	// set up pte
	*pagetab_entry = page2pa(pp) | perm | PTE_P;
	// invalidate tlb
	tlb_invalidate(pgdir,va);
	return 0;

The fact is, writing code in this way may make people spend much time thinking why this works, but writing code in the most straightforward way may seem easy to understand at first sight, but longer code will cause some other reading troubles.

Personal selections, really.

Kernel Address Space

简单地说一下虚拟地址空间的权限分布吧:

[ULIM,+INF) Kernel Space (W,Supervisor)
[UTOP,ULIM) Kernel Structures (R,User)
[   0,UTOP) User Space (W,User)

Initialize IT!

我们需要在mem_init()中补完设置内核地址空间映射和权限的部分。

简单说一下几个点:

  • 首先设置页表自身的映射。要设置两个地方的映射:映射到UPAGES和自己的虚拟地址;权限不同,使用boot_map_region即可。如果使用page_insert,因为实际上这个页面不是由真正的分配器分配的,会报Double free错误。
  • 然后设置内核栈的映射。注意使用已有的bootstack作为栈空间底部的地址。
  • 最后设置所有物理页映射。

Questions

  1. 略。需要进行一些简单的数学运算,懒得做了。
  2. 因为设置了内核空间(即 0xf0…0~4G)的权限。80386的页级保护机制为此提供了支持。
  3. 0xeec00000大小。这是最高的没有被映射的地址。也就是说,从0xeebfffff到0x0的位置是全部可以被利用的。
  4. 我认为Overhead的主要问题出在……映射了大量的物理空间到0xf0…0以上导致页表膨胀。
  5. 这个问题我好像已经在上一篇博客回答过了……?

0x04 Challenges!

没有challenge的检测程序啊……有点懒,以后再做吧。