第一讲: 程序的运行过程

程序的编译过程

compile_process

  1. 预处理:加入头文件,替换宏 gcc HelloWorld.c -o HelloWorld.i
  2. 编译:包含预处理,将C程序转成成汇编程序 gcc HelloWorld.c -S -c Helloworld.s
  3. 汇编:包含预处理和汇编,将汇编程序转换成可链接的二进制程序 gcc HelloWorld.c -c HelloWorld.o
  4. 链接:将可链接的二进制程序和其他的库链接在一起,形成可执行的程序文件 gcc HelloWorld.c -o HelloWorld

程序装载执行

冯诺依曼体系结构五大组件

  • 装载数据和程序的输入设备
  • 记住程序和数据的存储器
  • 完成数据加工的运算器
  • 控制程序执行的控制器
  • 显示处理结果的输出设备

HelloWorld汇编代码解释

objdump -d hello_world.o compile_code

上图分为四列:

  • 第一列为地址
  • 第二列为数据
  • 第三列为汇编命令
  • 第四列为注释

将上图中代码装入计算机中,状态如下图:

compile_code_status

第二讲:实现一个最小内核

OS引导流程

os_load

BIOS固件负责检测和初始化CPU、内存及主办平台,然后加载引导设备(如磁盘)的第一个扇区地址的数据 到0x7c00地址开始的内存空间,街道跳转到0x7c00处执行指令,即GRUB指导程序

引导汇编代码

C作为通用的高级语言不能直接操作特定的硬件,而且C语言的函数调用、传参都 需要栈 所以需要汇编代码来出席这些C语言的工作环境

 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
;彭东 @ 2021.01.09
MBT_HDR_FLAGS EQU 0x00010003
MBT_HDR_MAGIC EQU 0x1BADB002 ;多引导协议头魔数
MBT_HDR2_MAGIC EQU 0xe85250d6 ;第二版多引导协议头魔数
global _start ;导出_start符号
extern main ;导入外部的main函数符号
[section .start.text] ;定义.start.text代码节
[bits 32] ;汇编成32位代码
_start:
jmp _entry
ALIGN 8
mbt_hdr:
dd MBT_HDR_MAGIC
dd MBT_HDR_FLAGS
dd -(MBT_HDR_MAGIC+MBT_HDR_FLAGS)
dd mbt_hdr
dd _start
dd 0
dd 0
dd _entry
;以上是GRUB所需要的头
ALIGN 8
mbt2_hdr:
DD MBT_HDR2_MAGIC
DD 0
DD mbt2_hdr_end - mbt2_hdr
DD -(MBT_HDR2_MAGIC + 0 + (mbt2_hdr_end - mbt2_hdr))
DW 2, 0
DD 24
DD mbt2_hdr
DD _start
DD 0
DD 0
DW 3, 0
DD 12
DD _entry
DD 0
DW 0, 0
DD 8
mbt2_hdr_end:
;以上是GRUB2所需要的头
;包含两个头是为了同时兼容GRUB、GRUB2
ALIGN 8
_entry:
;关中断
cli
;关不可屏蔽中断
in al, 0x70
or al, 0x80
out 0x70,al
;重新加载GDT
lgdt [GDT_PTR]
jmp dword 0x8 :_32bits_mode
_32bits_mode:
;下面初始化C语言可能会用到的寄存器
mov ax, 0x10
mov ds, ax
mov ss, ax
mov es, ax
mov fs, ax
mov gs, ax
xor eax,eax
xor ebx,ebx
xor ecx,ecx
xor edx,edx
xor edi,edi
xor esi,esi
xor ebp,ebp
xor esp,esp
;初始化栈,C语言需要栈才能工作
mov esp,0x9000
;调用C语言函数main
call main
;让CPU停止执行指令
halt_step:
halt
jmp halt_step
GDT_START:
knull_dsc: dq 0
kcode_dsc: dq 0x00cf9e000000ffff
kdata_dsc: dq 0x00cf92000000ffff
k16cd_dsc: dq 0x00009e000000ffff
k16da_dsc: dq 0x000092000000ffff
GDT_END:
GDT_PTR:
GDTLEN dw GDT_END-GDT_START-1
GDTBASE dd GDT_START
  • 1~40行:GRUB多引导协议头
  • 44~52行:关掉中断,设定CPU的工作模式
  • 54~73行:初始化CPU的寄存器和C语言的运行环境
  • 78~87行:设置CPU工作模式所需要的数据

主函数

1
2
3
4
5
6
7
//main.c
#include "vgastr.h"
void main()
{
  printf("Hello OS!");
  return;
} 

控制计算机屏幕

显卡有多种形式

  • 集显:集成在主办
  • 核显:CPU芯片内
  • 独显:独立存在,同时PCIE接口连接

显卡的字符模式将屏幕分成24行,每行80个字符,把字符映射到以0xb8000开始的内存中 一个字符对应两个字节,一个字节是字符的ASCII码,另外一个字节为字符的颜色值

byte_mode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// vgsstr.c
void _strwrite(char* string) 
{
    char* p_string = (char*)(oxb8000); //显存开始的地址
    while (*string) 
    {
        *p_string = *string++;
        p_string += 2;
    }
    return;
}

void printf(char* fmt, ...) 
{
    _strwrite(fmt);
    return;
}

编译和安装

编译

compile_process

安装

上述编译流程会得到HelloOS.bin文件,但序言GRUB能够找到它 具体配置在grub.cfg的文件中

1
2
3
4
5
6
7
menuentry 'HelloOS' {
     insmod part_msdos #GRUB加载分区模块识别分区
     insmod ext2 #GRUB加载ext文件系统模块识别ext文件系统
     set root='hd0,msdos4' #注意boot目录挂载的分区(df /boot 查看)
     multiboot2 /boot/HelloOS.bin #GRUB以multiboot2协议加载HelloOS.bin
     boot #GRUB启动HelloOS.bin
}

重启系统长按shit键然后选择HelloOS即可

第三讲:内核结构设计

内核功能

  • 管理CPU:CPU是执行程序的,而内核吧运行时的程序抽象成 进程,所以称之为进程管理
  • 管理内存
  • 管理硬盘
  • 管理显卡
  • 管理各种I/O设备

宏内核结构

宏内核就是所有诸如管理进程等功能的代码进过编译链接形成一个大的可执行程序

这个大程序里有实现这个功能的所有代码,向应用软件提供一些接口(即系统API) macro-core

宏内核的优点是组件都在内核中合一相互调用性能极高;但缺点也很明显,高度耦合,没有模块化

微内核结构

微内核仅仅只有进程调度、处理中断、内存空间映射和进程间通信等功能

实际功能如进程管理、内存管理、文件管理等做成一个个服务进程

微内核与应用进程和服务进程通过消息通信

应用程序要请求相关服务,就向微内核发送一条与此服务对应的消息,微内核再把这条消息转发给相关的服务进程,接着服务进程会完成相关的服务。

我们的选择

大致将内核分为三个大层

  • 内核接口层
  • 内核功能层
  • 内核硬件层

core-structure

内核接口层

  1. 定义了一套UNIX接口的子集
  2. 检查参数的合法性

内核功能层

主要完成各种事件功能

  1. 进程管理:实现进程的创建、销毁、调度
  2. 内存管理:内存池分为页面内存池和任意大小的内存池
  3. 中断管理:把中断回调函数安插在相关的数据结构中,发生相关的中断就会调用回调函数
  4. 设备管理:把驱动程序模块、驱动程序本身和驱动程序创建的设备组织在一起

内核硬件层

  1. 初始化:初始化少量的设备、CPU、内存、中断的控制,内核用户管理的数据结构
  2. CPU控制:提供CPU模式设定、开关中断、读写CPU特定寄存器等功能
  3. 中断处理:保存上下文、调用中断回调函数、操作中断控制器
  4. 物理内存管理:分配和释放大块内存、内存空间映射、操作MMU和Cache
  5. 平台其他相关功能

第四讲:业界成熟内核架构

Linux

linux-core

Linux使用的宏内核架构,模块之间的通信主要是函数调用

Darwin

macos-core

Darwin有两个内核层

  • Mach层:微内核,然提供十分简单的进程、线程、IPC 通信、虚拟内存设备驱动相关的功能服务
  • BSD层:提供强大的安全特性,完善的网络服务,各种文件系统的支持,同时对 Mach 的进程、线程、IPC、虚拟内核组件进行细化、扩展延伸

Windows NT

windows-core

每个执行体互相独立,只对外提供相应的接口,其它执行体要通过内核模式可调用接口和其它执行体通信或者请求其完成相应的功能服务

评论区拾遗

内核相当于所有的功能都耦合在一起,放在内核内 微内核是把大多数功能解耦出来,放在用户态,使用IPC在用户态调用服务进程 混合结构其实与微内核相似,只不过解耦出来的这些功能依然放在内核里,动态加载和卸载

第五讲:执行程序的三种模式

CPU的工作模式有三种

  • 实模式
  • 保护模式
  • 长模式

实模式

实模式又称实地址模式,一方面是运行真实的指令,另一方面内存地址是真实的

寄存器

通常情况下指令的操作数就是寄存器,下图为x86 实模式下的寄存器

physical_register

内存

指令和数据都放在内存中,内存的地址值计算过程如下图

physical_memory

内存地址是由段寄存器左移4位,再加上一个统统寄存器的值形成地址,然后由这个地址去访问内存 (这个即是分段内存管理模式)

代码段是CS和IP确定的,栈段是由SS和SP确定的

DOS实模式汇编代码程序实例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
data SEGMENT ;定义一个数据段存放Hello World!
    hello  DB 'Hello World!$' ;注意要以$结束
data ENDS
code SEGMENT ;定义一个代码段存放程序指令
    ASSUME CS:CODE,DS:DATA ;告诉汇编程序,DS指向数据段CS指向代码段
start:
    MOV AX,data  ;data段首地址赋值给AX                
    MOV DS,AX    ;AX赋值给DS,使DS指向data段
    LEA DX,hello ;使DX指向hello首地址
    MOV AH,09h   ;AH设置参数09HAH是AX高8位AL是AX低8位,其它类似
    INT 21h      ;执行DOS中断输出DS指向的DX指向的字符串hello
    MOV AX,4C00h ;AH设置参数4C00h
    INT 21h      ;调用4C00h号功能,结束程序
code ENDS
END start

中断

中断即终止当前程序,转而跳转到另一个特定的地址上,去运行特定的代码。

在实模式中即:先保存CS和IP寄存器,然后装载新的CS和IP寄存器

interrupt-vector-table 为了实现中断,就需要在内存中放一个中断向量表(中断信号和对应响应程序的首地址)

这个表的地址和长度由IDTR寄存器指向,在实模式中,一个条目由代码段地址和端内偏移组成

根据中断信合和IDTR寄存器的信息,CPU能够计算出中断向量的条目,进而装载CS(段基地址)、IP寄存器(段内偏移),最终响应中断

保护模式

protected-register

相比实模式,保护模式增加了一些控制寄存器和段寄存器,扩展通用寄存器的位宽

特权级

protected-privilege-level

从内到外,权力逐步提升

段描述符

protected-segment-descriptor

内存是分段模型,对内存的保护可以转化成对段的保护

段描述符是一个64位的数据,包含了段基地址、段长度、段权限、段类型和读写状态等

由于信息的扩展,16位的寄存器放不下,段描述符放在内存中

多个段描述符在内存中形成全局段描述符表,该表的基地址和长度由GDTR寄存器指示

protected-segment-descriptor-table

段寄存器不再放段基地址,而是段在段描述符表的索引

平坦模型

x86 CPU不能直接使用分页模型,通过简化设计,来时分段称为一个"虚设",这个称之为保护模式的平坦模型

将段的基地址设为0,段长度设为0xFFFFF(2 ** 20 = 1M),段的粒度为4KB 在此模式下不同的段可以重叠、交叉和包含

中断

保护模式需要检查权限,所以需要扩展中断向量表的信息 每个中断用一个中断门描述符来表示,格式如下

protected-interrupt

中断向量表的条目也变成了中断门描述符 protected-interrupt-table

产生中断后

  1. 检查中断号是否在有效区间(0~255)
  2. 检查描述符类型
  3. 权限检查(如果权限等级不同会进行栈切换)
  4. 加载目标代码偏移段到EIP寄存器

切换

由实模式切换到保护模式步骤如下:

  1. 准备全局段描述符表
1
2
3
4
5
6
7
8
GDT_START:
knull_dsc: dq 0
kcode_dsc: dq 0x00cf9e000000ffff
kdata_dsc: dq 0x00cf92000000ffff
GDT_END:
GDT_PTR:
GDTLEN  dw GDT_END-GDT_START-1
GDTBASE  dd GDT_START
  1. 设置GDTR寄存器,使之指向全局段描述符表
1
lgdt [GDT_PTR]
  1. 设置CR0寄存器,开启保护模式
1
2
3
4
;开启 PE
mov eax, cr0
bts eax, 0                      ; CR0.PE =1
mov cr0, eax         
  1. 进行长跳转,加载CS段寄存器
1
jmp dword 0x8 :_32bits_mode ;_32bits_mode为32位代码标号即段偏移

长模式

长模式又称AMD64,它是CPU在现有基础上有了64位的处理能力

寄存器

所有通用寄存器都是64位,可以单独使用低32位,低32位可以查封成一个低16位,低16位可以拆分成两个8位寄存器

amd64-register

段描述符

amd64-segment-descriptor

中断

amd64-interrupt

切换

  1. 准备长模式全局段描述符表
1
2
3
4
5
6
7
8
ex64_GDT:
null_dsc:  dq 0
;第一个段描述符CPU硬件规定必须为0
c64_dsc:dq 0x0020980000000000  ;64位代码段
d64_dsc:dq 0x0000920000000000  ;64位数据段
eGdtLen   equ $ - null_dsc  ;GDT长度
eGdtPtr:dw eGdtLen - 1  ;GDT界限
     dq ex64_GDT
  1. 准备长模式下的MMU页表

长模式下内存地址空间的保护交给了 MMU,MMU 依赖页表对地址进行转换,页表有特定的格式存放在内存中,其地址由 CPU 的 CR3 寄存器指向

1
2
3
4
5
mov eax, cr4
bts eax, 5   ;CR4.PAE = 1
mov cr4, eax ;开启 PAE
mov eax, PAGE_TLB_BADR ;页表物理地址
mov cr3, eax
  1. 加载GDTR寄存器,是指指向全局段描述符
1
lgdt [eGdtPtr]
  1. 开启长模式
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
;开启 64位长模式
mov ecx, IA32_EFER
rdmsr
bts eax, 8  ;IA32_EFER.LME =1
wrmsr
;开启 保护模式和分页模式
mov eax, cr0
bts eax, 0    ;CR0.PE =1
bts eax, 31
mov cr0, eax 
  1. 进行跳转,加载CS段寄存器
1
jmp 08:entry64 ;entry64为程序标号即64位偏移地址

第六讲:地址转换

虚拟地址

虚拟地址由链接器产生,链接器的主要工作是吧多个代码模块组装在一起,并解决模块之间的引用 ,即处理程序代码间的地址引用,形成程序运行的静态内存空间视图

物理地址

物理地址会被地址译码器变成电信号,放在地址总线上,地址总线电子信号的各种组合就可以选择到内存的存储单元

虚实转换

虚实地址转换是通过MMU(内存管理单元)实现的

convert-virtual-address

地址转换关系表本身存放在内存中,如果一个虚拟对称对应一个物理地址,转换表就会把内存耗尽

于是引出了分页模型,虚拟地址空间和物理地址空间都分成了同等大小的页

page-mode

MMU

MMU负责接受虚拟地址值和地址关系转换表,然后输出物理地址

页表

页表即虚拟页到物理页的映射关系

为了洁身空间,页表值存放物理页面的地址,MMU以虚拟地址为索引去查表返回物理页地址

页表是分级的,分为三部分

  • 一个顶级页目录
  • 多个中继页目录
  • 页表

page-mode2

一个虚拟地址从左到右分为四个位段

  • 第一个位段索引顶级页目录,得到中继页目录
  • 第二个位段索引中级页目录,得到页目录
  • 第三个位段索引也目录,得到物理页地址
  • 第四个位段用作该物理页的偏移去访问物理内存

保护模式下的分页

保护模式下只有32位地址空间,32位虚拟地址经过分段机制后得到线性地址, 通常使用平坦模式,所以线性地址和虚拟地址是相同的

4KB页

该分页方式下32位虚拟地址被分为三个位段: 页目录索引、页表索引、页内偏移

page-mode3

CR3寄存器、页目录项和页表项都是32位,所以低12位可以另做它用,形成了页面相关属性,如 是否存在,是否可读写、是否已访问等待

page-mode4 page-mode5 page-mode6

4MB页

该分页方式下,32位虚拟地址被分为2段:页表索引、页内偏移

共1024个条目,每个条目指向一个物理页4MB,正好为4GB地址空间

page-mode7

CR3还是32位寄存器,指向一个4KB大小的页表,仍然要4KB地址对齐,其中包含1024个页表项

长模式下的分页

长模式下扩展为64位

4KB页

long-mode1

64位虚拟地址被分为6段

  • 保留位段: 24位
  • 顶级页目录索引段:9位
  • 页目录指针段: 9位
  • 页目录段:9位
  • 页表段: 9位
  • 页内偏移:12位

顶级页目录、页目录指针、页目录、页表都各占4KB, 各512个条目,每个条目8B即64位

因为x86 CPU并没有实现全64位的地址总线,而是只实现了48位,但寄存器却是64位的, 当第47位是1的时候48~63为1,反之为0

2MB页

该方式下分为5个分段

  • 保留位段: 16位
  • 顶级页目录索引:9位
  • 页目录指针索引:9位
  • 页目录索引:9位
  • 页内偏移:21位

顶级页目录、页目录指针、页目录都各占4KB, 各512个条目,每个条目8B即64位 页表项被放弃,页目录项直接指定了2MB大小的物理页面

开启MMU

  1. 使CPU进入保护模式或长模式
  2. 准备页表数据
  3. 将顶级页目录的物理地址赋值给CR3寄存器
1
2
mov eax, PGAE_TLB_BADR ;页表物理地址
mov cr3, eax
  1. 将CPU的CR0的PE为设置为0,这样就开启了 MMU
1
2
3
4
5
;开启保护模式和分页模式
mov eax, cr0
bts eax, 0    ;CR0.PE = 1
bts eax, 31   ;CR0.P = 1
mov cr0, eax

第七讲:Cache与内存

内存

控制内存读写和刷新的是内存控制器,内存控制器集成在北桥芯片中

由于制造工艺升级,现在北桥芯片被集成到了CPU芯片,这样大大提升了CPU访问内存的性能

Cache

通过程序的局部性原理可以知道CPU大多数时间在访问相同或者相近的地址

那么可以用一块小而快的存储器放在CPU和内存之间,来缓解CPU和内存的之间的性能差距

这个就称之为Cache

Cache中存放了部分内存数据,CPU在访问内存时要先访问Cache

现在的x86 CPU是将Cache集成在CPU内

cache

Cache主要由高速的静态存储器、地址转换模块和行替换模块组成

Cache会把存储器分成若干行,每行32字节或64字节,和内存交换数据最小单位为一行

为了方便管理,多个行又会组成一组

除了正常数据外,行中还有一些标志位,如脏位、回写位等

Cache的大致工作流程如下:

  1. CPU发出的地址由Cache的地址转换模块分成3段:组号、行号和行内偏移
  2. Cache会根据组号、行号查找高速静态存储器中对应的行。如果找到即命中,用行内偏移读取并返回数据给CPU; 否则就分配一个新行并访问内存,把内存中对应的数据加载到Cache行并返回给CPU。 写入操作分为回写和直写,回写就是写入对应的Cache行即可,直写写入Cache行的同时会写入内存
  3. 如果容量不足,就要进入行替换逻辑,即找出一个Cache行写回内存,腾出空间。

Cache引入的问题

x86_cache

上图是简单的双核心CPU,有三级Cache,第一级Cache是指令和数据分开的, 第二级是独立于CPU核心的,第三级是所有CPU核心共享的。

Cache一致性问题主要包括以下三个:

  1. 一个CPU中指令Cache和数据Cache一致性的问题
  2. 多个CPU各自的2级Cache一致性问题
  3. 3级Cache与网卡、显存等设备存储之间的一致性问题

Cache的MESI协议

MESI协议定义了四种基本状态

  1. Modified 当前Cache内容有效,但已和内存不一致,且不存在其他核心的Cache中

  2. Exclusive 当前Cache内容有效,和内存一致,但不存在其他核心的Cache中

  3. Shared

当前Cache内容有效,和内存一致,且在其他核心的Cache中也一至

  1. Invalid 其他情况,当前Cache无效

第八讲:锁-并发操作中如何让数据同步

方法一: 原子操作, 拿下单体变量

C语言可以嵌入汇编代码实现原子操作

 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

//定义一个原子类型
typedef struct s_ATOMIC{
    volatile s32_t a_count; //在变量前加上volatile,是为了禁止编译器优化,使其每次都从内存中加载变量
}atomic_t;
//原子读
static inline s32_t atomic_read(const atomic_t *v)
{        
        //x86平台取地址处是原子
        return (*(volatile u32_t*)&(v)->a_count);
}
//原子写
static inline void atomic_write(atomic_t *v, int i)
{
        //x86平台把一个值写入一个地址处也是原子的 
        v->a_count = i;
}
//原子加上一个整数
static inline void atomic_add(int i, atomic_t *v)
{
        __asm__ __volatile__("lock;" "addl %1,%0"
                     : "+m" (v->a_count)
                     : "ir" (i));
}
//原子减去一个整数
static inline void atomic_sub(int i, atomic_t *v)
{
        __asm__ __volatile__("lock;" "subl %1,%0"
                     : "+m" (v->a_count)
                     : "ir" (i));
}
//原子加1
static inline void atomic_inc(atomic_t *v)
{
        __asm__ __volatile__("lock;" "incl %0"
                       : "+m" (v->a_count));
}
//原子减1
static inline void atomic_dec(atomic_t *v)
{
       __asm__ __volatile__("lock;" "decl %0"
                     : "+m" (v->a_count));
}

加上lock前缀的addl、subl、incl、decl指令都是原子操作,lock前缀表示锁定总线,CPU能互斥使用特定的内存地址

代码模板以__asm__ __volatile开始,后面括号内容分为四个部分,以:分割 以atomic_add举例:

  1. 汇编代码, "lock"; "add %1, %0"
  2. 输出列表,"+m" (v->a_count),"+m"表示输出和内存地址关联
  3. 输入列表, "ir", “r"表示输入i和寄存器关联
  4. 损坏部分,告诉编译器使用了哪些寄存器,以便保存和恢复寄存器的值

方法二: 中断控制,搞定复杂变量

x86 使用cli、sti 指令关闭和开启中断,它们主要是对CPU的eflags寄存器的IF位(第9位)进行 清除和设置,CPU通过此位来决定是否响应中断信号

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// 关闭中断
void hal_cli()
{
    __asm__ __volatile__("cli": : :"memory");
}

// 开启中断
void hal_sti()
{
    __asm__ __volatile__("sti": : :"memory");
}

上面这种方式不支持嵌套调用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void foo() 
{
    hal_cli();
    ...
    hal_sti();
}

void bar() 
{
    hal_cli();
    foo();
    ...
    hal_sti();
}

解决方案为:

  • 关闭中断函数先保存eflags寄存器,然后执行cli指令
  • 开启中断函数恢复保存的eflags寄存器的值
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

typedef u32_t cpuflg_t;
static inline void hal_save_flags_cli(cpuflg_t* flags)
{
     __asm__ __volatile__(
            "pushfl \t\n" //把eflags寄存器压入当前栈顶
            "cli    \t\n" //关闭中断
            "popl %0 \t\n"//把当前栈顶弹出到eflags为地址的内存中        
            : "=m"(*flags)
            :
            : "memory"
          );
}
static inline void hal_restore_flags_sti(cpuflg_t* flags)
{
    __asm__ __volatile__(
              "pushl %0 \t\n"//把flags为地址处的值寄存器压入当前栈顶
              "popfl \t\n"   //把当前栈顶弹出到eflags寄存器中
              :
              : "m"(*flags)
              : "memory"
              );
}

方法三: 自旋锁,协调多核心CPU

控制中断只能控制当前CPU的中断,不能控制其他CPU的中断

自旋锁原理如下图所示:

spin_lock

如果需要正确执行,需要保证读取锁变量和判断并加锁的操作是原子的

x86 提供了一个原子交换指令xchg,它可以让寄存器的值和内存空间的值进行交换

 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
//自旋锁结构
typedef struct
{
     volatile u32_t lock;//volatile可以防止编译器优化,保证其它代码始终从内存加载lock变量的值 
} spinlock_t;
//锁初始化函数
static inline void x86_spin_lock_init(spinlock_t * lock)
{
     lock->lock = 0;//锁值初始化为0是未加锁状态
}
//加锁函数
static inline void x86_spin_lock(spinlock_t * lock)
{
    __asm__ __volatile__ (
    "1: \n"
    "lock; xchg  %0, %1 \n"//把值为1的寄存器和lock内存中的值进行交换
    "cmpl   $0, %0 \n" //用0和交换回来的值进行比较
    "jnz    2f \n"  //不等于0则跳转后面2标号处运行
    "jmp 3f \n"     //若等于0则跳转后面3标号处返回
    "2:         \n" 
    "cmpl   $0, %1  \n"//用0和lock内存中的值进行比较
    "jne    2b      \n"//若不等于0则跳转到前面2标号处运行继续比较  
    "jmp    1b      \n"//若等于0则跳转到前面1标号处运行,交换并加锁
    "3:  \n"     
    :
    : "r"(1), 
    "m"(*lock));
}
//解锁函数
static inline void x86_spin_unlock(spinlock_t * lock)
{
    __asm__ __volatile__(
    "movl   $0, %0\n"//解锁把lock内存中的值设为0就行
    :
    : "m"(*lock));
}

xchg %0, %1其中 %0 对应"r"(1),表示编译器自动分配一个通用寄存器,并填入值1; 而 %1对应"m"(*lock),表示lock是内存地址。 把1和内存的值交换,如果内存值是1,则不影响,否则已交换内存就变成了1,即加锁成功。

自旋锁需要在处理中断的过程中也能使用,所以需要改进

  • 获取自旋锁时先关闭中断
  • 释放自旋锁后恢复
 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

static inline void x86_spin_lock_disable_irq(spinlock_t * lock,cpuflg_t* flags)
{
    __asm__ __volatile__(
    "pushfq                 \n\t"
    "cli                    \n\t"
    "popq %0                \n\t"
    "1:         \n\t"
    "lock; xchg  %1, %2 \n\t"
    "cmpl   $0,%1       \n\t"
    "jnz    2f      \n\t"
    "jmp    3f      \n"  
    "2:         \n\t"
    "cmpl   $0,%2       \n\t" 
    "jne    2b      \n\t"
    "jmp    1b      \n\t"
    "3:     \n"     
    :"=m"(*flags)
    : "r"(1), "m"(*lock));
}
static inline void x86_spin_unlock_enabled_irq(spinlock_t* lock,cpuflg_t* flags)
{
    __asm__ __volatile__(
    "movl   $0, %0\n\t"
    "pushq %1 \n\t"
    "popfq \n\t"
    :
    : "m"(*lock), "m"(*flags));
}

方法四: 信号量,时间管理大师

信号量可以对资源进行保护,同一时刻只有一个代码执行流,又能在资源无法满足的情况下,让CPU执行其他任务

信号量数据结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#define SEM_FLG_MUTEX 0
#define SEM_FLG_MULTI 1
#define SEM_MUTEX_ONE_LOCK 1
#define SEM_MULTI_LOCK 0
//等待链数据结构,用于挂载等待代码执行流(线程)的结构,里面有用于挂载代码执行流的链表和计数器变量,这里我们先不深入研究这个数据结构。
typedef struct s_KWLST
{   
    spinlock_t wl_lock;
    uint_t   wl_tdnr;
    list_h_t wl_list;
}kwlst_t;
//信号量数据结构
typedef struct s_SEM
{
    spinlock_t sem_lock;//维护sem_t自身数据的自旋锁
    uint_t sem_flg;//信号量相关的标志
    sint_t sem_count;//信号量计数值
    kwlst_t sem_waitlst;//用于挂载等待代码执行流(线程)结构
}sem_t;

假定信号量sem_count初始化为1,等待链sem_waitlst初始化为空

信号量的获取down和释放up的代码如下

 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

//获取信号量
void krlsem_down(sem_t* sem)
{
    cpuflg_t cpufg;
start_step:    
    krlspinlock_cli(&sem->sem_lock,&cpufg);//获取自旋锁
    if(sem->sem_count<1)
    {//如果信号量值小于1,则让代码执行流(线程)睡眠
        krlwlst_wait(&sem->sem_waitlst);
        krlspinunlock_sti(&sem->sem_lock,&cpufg);
        krlschedul();//切换代码执行流,下次恢复执行时依然从下一行开始执行,所以要goto开始处重新获取信号量
        goto start_step; 
    }
    sem->sem_count--;//信号量值减1,表示成功获取信号量
    krlspinunlock_sti(&sem->sem_lock,&cpufg);//释放自旋锁
    return;
}
//释放信号量
void krlsem_up(sem_t* sem)
{
    cpuflg_t cpufg;
    krlspinlock_cli(&sem->sem_lock,&cpufg); //获取自旋锁
    sem->sem_count++;//释放信号量
    if(sem->sem_count<1)
    {//如果小于1,则说数据结构出错了,挂起系统
        krlspinunlock_sti(&sem->sem_lock,&cpufg);
        hal_sysdie("sem up err");
    }
    //唤醒该信号量上所有等待的代码执行流(线程)
    krlwlst_allup(&sem->sem_waitlst);
    krlspinunlock_sti(&sem->sem_lock,&cpufg);
    krlsched_set_schedflgs();
    return;
}

获取信号量

  1. 对用于保护信号量本身的自旋锁sem_lock加锁
  2. 判断sem_count的值: 如果小于1则让进程进入等待状态并将其挂入sem_waitlst; 否则表示信号量获取成功,将sem_count-1,并释放自旋锁

释放信号量

  1. 对用于保护信号量本身的自旋锁sem_lock加锁
  2. 对sem_count+1
  3. 唤醒sem_waitlst的进程,释放自旋锁

第九讲 Linux的并发实现

原子变量

Linux提供了一个原子类型变量atomic_t

1
2
3
4
5
6
7
8
9
tyepedef struct 
{
    int counter;
} atomic_t;

typedef struct
{
    s64 counter;    
} atomic64_t;

操作函数

 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

//原子读取变量中的值
static __always_inline int arch_atomic_read(const atomic_t *v)
{
    return __READ_ONCE((v)->counter);
}
//原子写入一个具体的值
static __always_inline void arch_atomic_set(atomic_t *v, int i)
{
    __WRITE_ONCE(v->counter, i);
}
//原子加上一个具体的值
static __always_inline void arch_atomic_add(int i, atomic_t *v)
{
    asm volatile(LOCK_PREFIX "addl %1,%0"
             : "+m" (v->counter)
             : "ir" (i) : "memory");
}
//原子减去一个具体的值
static __always_inline void arch_atomic_sub(int i, atomic_t *v)
{
    asm volatile(LOCK_PREFIX "subl %1,%0"
             : "+m" (v->counter)
             : "ir" (i) : "memory");
}
//原子加1
static __always_inline void arch_atomic_inc(atomic_t *v)
{
    asm volatile(LOCK_PREFIX "incl %0"
             : "+m" (v->counter) :: "memory");
}
//原子减1
static __always_inline void arch_atomic_dec(atomic_t *v)
{
    asm volatile(LOCK_PREFIX "decl %0"
             : "+m" (v->counter) :: "memory");
}



#define __READ_ONCE(x)  \
(*(const volatile __unqual_scalar_typeof(x) *)&(x))
#define __WRITE_ONCE(x, val) \
do {*(volatile typeof(x) *)&(x) = (val);} while (0)
//__unqual_scalar_typeof表示声明一个非限定的标量类型,非标量类型保持不变。说人话就是返回x变量的类型,这是GCC的功能,typeof只是纯粹返回x的类型。

//如果 x 是int类型则返回“int” 
#define __READ_ONCE(x)  \
(*(const volatile int *)&(x))
#define __WRITE_ONCE(x, val) \
do {*(volatile int *)&(x) = (val);} while (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
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

//实际保存eflags寄存器
extern __always_inline unsigned long native_save_fl(void){
    unsigned long flags;
    asm volatile("# __raw_save_flags\n\t"
                 "pushf ; pop %0":"=rm"(flags)::"memory");
    return flags;
}
//实际恢复eflags寄存器
extern inline void native_restore_fl(unsigned long flags){
    asm volatile("push %0 ; popf"::"g"(flags):"memory","cc");
}
//实际关中断
static __always_inline void native_irq_disable(void){
    asm volatile("cli":::"memory");
}
//实际开启中断
static __always_inline void native_irq_enable(void){
    asm volatile("sti":::"memory");
}
//arch层关中断
static __always_inline void arch_local_irq_disable(void){
    native_irq_disable();
}
//arch层开启中断
static __always_inline void arch_local_irq_enable(void){ 
    native_irq_enable();
}
//arch层保存eflags寄存器
static __always_inline unsigned long           arch_local_save_flags(void){
    return native_save_fl();
}
//arch层恢复eflags寄存器
static  __always_inline void arch_local_irq_restore(unsigned long flags){
    native_restore_fl(flags);
}
//实际保存eflags寄存器并关中断
static __always_inline unsigned long arch_local_irq_save(void){
    unsigned long flags = arch_local_save_flags();
    arch_local_irq_disable();
    return flags;
}
//raw层关闭开启中断宏
#define raw_local_irq_disable()     arch_local_irq_disable()
#define raw_local_irq_enable()      arch_local_irq_enable()
//raw层保存恢复eflags寄存器宏
#define raw_local_irq_save(flags)           \
    do {                        \
        typecheck(unsigned long, flags);    \
        flags = arch_local_irq_save();      \
    } while (0)
    
#define raw_local_irq_restore(flags)            \
    do {                        \
        typecheck(unsigned long, flags);    \
        arch_local_irq_restore(flags);      \
    } while (0)
    
#define raw_local_save_flags(flags)         \
    do {                        \
        typecheck(unsigned long, flags);    \
        flags = arch_local_save_flags();    \
    } while (0)
//通用层接口宏 
#define local_irq_enable()              \
    do { \
        raw_local_irq_enable();         \
    } while (0)

#define local_irq_disable()             \
    do {                        \
        raw_local_irq_disable();        \
    } while (0)

#define local_irq_save(flags)               \
    do {                        \
        raw_local_irq_save(flags);      \
    } while (0)

#define local_irq_restore(flags)            \
    do {                        \
        raw_local_irq_restore(flags);       \
    } while (0)

do{}while(0)表达式会保证{}中的代码片段执行一次,保证宏展开时这个代码片段是一个整体

自旋锁

Linux自旋锁有多种实现,下面介绍两种

原始自旋锁

数据结构

1
2
3
typedef struct {
    volatile unsigned long lock; 
} spinlock_t;

函数

 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

#define spin_unlock_string \  
    "movb $1,%0" \ //写入1表示解锁
    :"=m" (lock->lock) : : "memory"

#define spin_lock_string \
  "\n1:\t" \  
    "lock ; decb %0\n\t" \ //原子减1
  "js 2f\n" \    //当结果小于0则跳转到标号2处,表示加锁失败
    ".section .text.lock,\"ax\"\n" \ //重新定义一个代码段,这是优化技术,避免后面的代码填充cache,因为大部分情况会加锁成功,链接器会处理好这个代码段的
  "2:\t" \  
    "cmpb $0,%0\n\t" \  //和0比较
    "rep;nop\n\t" \  //空指令
    "jle 2b\n\t" \   //小于或等于0跳转到标号2
    "jmp 1b\n" \   //跳转到标号1  
    ".previous"
//获取自旋锁
static inline void spin_lock(spinlock_t*lock){
    __asm__ __volatile__(
    spin_lock_string
    :"=m"(lock->lock)::"memory"
    );
}
//释放自旋锁
static inline void spin_unlock(spinlock_t*lock){
__asm__ __volatile__(
    spin_unlock_string
    );
}

spin_unlock_string只是简单将锁值设置为1,表示释放自旋锁

spin_lock_string使用了decb原子减一指令,如果结果为0表示加锁成功;否则 进入循环比较

当有多个进程同时等在自旋锁时,后续获取锁的进程是不确定的, 取决于内存总线协议决定哪个CPU核心可以访问内存

排队自旋锁

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

//RAW层的自旋锁数据结构
typedef struct raw_spinlock{
    unsigned int slock;//真正的锁值变量
}raw_spinlock_t;
//最上层的自旋锁数据结构
typedef struct spinlock{
    struct raw_spinlock rlock;
}spinlock_t;
//Linux没有这样的结构,这只是为了描述方便
typedef struct raw_spinlock{
    union {
        unsigned int slock;//真正的锁值变量
    }
}raw_spinlock_t;

slock域被分为两部分,分别保存锁持有者owner(低16位)和未来锁申请者next(高16位)的序号

只有next域和owner域相等时,才表示处于未使用的状态

slock初始值为0,即next和owner被置为0

进程申请自旋锁时,将next域加1,并将原值作为自己的序号

如果序号等于申请时的owner的值,说明自旋锁处于未使用的状态,则进程直接获得锁;

否则,该进程循环检查owner域是否等于自己持有的序号,一旦相等则表名锁轮到自己获取

进程释放锁时,原子的将owner域加 1 即可,下一个进程会发现这个变化

 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
static inline void __raw_spin_lock(raw_spinlock_t*lock){
int inc = 0x00010000;
int tmp;
__asm__ __volatile__(
"lock ; xaddl %0, %1\n" //将inc和slock交换,然后 inc=inc+slock
                        //相当于原子读取next和owner并对next+1
"movzwl %w0, %2\n\t"//将inc的低16位做0扩展后送tmp tmp=(u16)inc
"shrl $16, %0\n\t" //将inc右移16位 inc=inc>>16
"1:\t"
"cmpl %0, %2\n\t" //比较inc和tmp,即比较next和owner 
"je 2f\n\t" //相等则跳转到标号2处返回
"rep ; nop\n\t" //空指令
"movzwl %1, %2\n\t" //将slock的低16位做0扩展后送tmp 即tmp=owner
"jmp 1b\n" //跳转到标号1处继续比较
"2:"
:"+Q"(inc),"+m"(lock->slock),"=r"(tmp)
::"memory","cc"
);
}
#define UNLOCK_LOCK_PREFIX LOCK_PREFIX
static inline void __raw_spin_unlock(raw_spinlock_t*lock){
__asm__ __volatile__(
UNLOCK_LOCK_PREFIX"incw %0"//将slock的低16位加1 即owner+1
:"+m"(lock->slock)
::"memory","cc");
}

try_lock实现当无法立即获取自旋锁时,资源放弃

 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

static inline int __raw_spin_trylock(raw_spinlock_t*lock){
    int tmp;
    int new;
    asm volatile(
    "movl %2,%0\n\t"//tmp=slock
    "movl %0,%1\n\t"//new=tmp
    "roll $16, %0\n\t"//tmp循环左移16位,即next和owner交换了
    "cmpl %0,%1\n\t"//比较tmp和new即(owner、next)?=(next、owner)
    "jne 1f\n\t" //不等则跳转到标号1处 
    "addl $0x00010000, %1\n\t"//相当于next+1
    "lock ; cmpxchgl %1,%2\n\t"//new和slock交换比较    
    "1:"
    "sete %b1\n\t" //new = eflags.ZF位,ZF取决于前面的判断是否相等
    "movzbl %b1,%0\n\t" //tmp = new
    :"=&a"(tmp),"=Q"(new),"+m"(lock->slock)
    ::"memory","cc");
    return tmp;
}
int __lockfunc _spin_trylock(spinlock_t*lock){ 
    preempt_disable();
    if(_raw_spin_trylock(lock)){
        spin_acquire(&lock->dep_map,0,1,_RET_IP_);
        return 1;
    }
    preempt_enable();
    return 0;
}
#define spin_trylock(lock) __cond_lock(lock, _spin_trylock(lock))

_spin_trylock返回1表示尝试加锁成功

信号量

信号量可以分为单值信号量和多值信号量

信号量最大的优势是即可以是申请失败的进程睡眠,又可以作为资源计数器使用

1
2
3
4
5
6
7
struct semaphore
{
    raw_spinlock_t lock; // 保护信号量自身的自旋锁
    unsigned int count; // 信号量值
    struct list_head wait_list; //挂载睡眠等待进程的链表
}

接口函数

 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
static inline int __sched __down_common(struct semaphore *sem, long state,long timeout)
{
    struct semaphore_waiter waiter;
    //把waiter加入sem->wait_list的头部
    list_add_tail(&waiter.list, &sem->wait_list);
    waiter.task = current;//current表示当前进程,即调用该函数的进程
    waiter.up = false;
    for (;;) {
        if (signal_pending_state(state, current))
            goto interrupted;
        if (unlikely(timeout <= 0))
            goto timed_out;
        __set_current_state(state);//设置当前进程的状态,进程睡眠,即先前__down函数中传入的TASK_UNINTERRUPTIBLE:该状态是等待资源有效时唤醒(比如等待键盘输入、socket连接、信号(signal)等等),但不可以被中断唤醒
        raw_spin_unlock_irq(&sem->lock);//释放在down函数中加的锁
        timeout = schedule_timeout(timeout);//真正进入睡眠
        raw_spin_lock_irq(&sem->lock);//进程下次运行会回到这里,所以要加锁
        if (waiter.up)
            return 0;
    }
 timed_out:
    list_del(&waiter.list);
    return -ETIME;
 interrupted:
    list_del(&waiter.list);
    return -EINTR;

    //为了简单起见处理进程信号(signal)和超时的逻辑代码我已经删除
}
//进入睡眠等待
static noinline void __sched __down(struct semaphore *sem)
{
    __down_common(sem, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
}
//获取信号量
void down(struct semaphore *sem)
{
    unsigned long flags;
    //对信号量本身加锁并关中断,也许另一段代码也在操作该信号量
    raw_spin_lock_irqsave(&sem->lock, flags);
    if (likely(sem->count > 0))
        sem->count--;//如果信号量值大于0,则对其减1
    else
        __down(sem);//否则让当前进程进入睡眠
    raw_spin_unlock_irqrestore(&sem->lock, flags);
}
//实际唤醒进程 
static noinline void __sched __up(struct semaphore *sem)
{
    struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list, struct semaphore_waiter, list);
    //获取信号量等待链表中的第一个数据结构semaphore_waiter,它里面保存着睡眠进程的指针
    list_del(&waiter->list);
    waiter->up = true;
    wake_up_process(waiter->task);//唤醒进程重新加入调度队列
}
//释放信号量
void up(struct semaphore *sem)
{
    unsigned long flags;
    //对信号量本身加锁并关中断,必须另一段代码也在操作该信号量
    raw_spin_lock_irqsave(&sem->lock, flags);
    if (likely(list_empty(&sem->wait_list)))
        sem->count++;//如果信号量等待链表中为空,则对信号量值加1
    else
        __up(sem);//否则执行唤醒进程相关的操作
    raw_spin_unlock_irqrestore(&sem->lock, flags);
}

读写锁

读写之间是互斥的,读写竞争锁时,写会优先得到锁

读写锁本质上是自旋锁的变种,是带计数的自旋锁

 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

//读写锁初始化锁值
#define RW_LOCK_BIAS     0x01000000
//读写锁的底层数据结构
typedef struct{
    unsigned int lock;
}arch_rwlock_t;
//释放读锁 
static inline void arch_read_unlock(arch_rwlock_t*rw){ 
    asm volatile(
        LOCK_PREFIX"incl %0" //原子对lock加1
        :"+m"(rw->lock)::"memory");
}
//释放写锁
static inline void arch_write_unlock(arch_rwlock_t*rw){
    asm volatile(
        LOCK_PREFIX"addl %1, %0"//原子对lock加上RW_LOCK_BIAS
        :"+m"(rw->lock):"i"(RW_LOCK_BIAS):"memory");
}
//获取写锁失败时调用
ENTRY(__write_lock_failed)
    //(%eax)表示由eax指向的内存空间是调用者传进来的 
    2:LOCK_PREFIX addl  $ RW_LOCK_BIAS,(%eax)
    1:rep;nop//空指令
    cmpl $RW_LOCK_BIAS,(%eax)
    //不等于初始值则循环比较,相等则表示有进程释放了写锁
    jne   1b
    //执行加写锁
    LOCK_PREFIX subl  $ RW_LOCK_BIAS,(%eax)
    jnz 2b //不为0则继续测试,为0则表示加写锁成功
    ret //返回
ENDPROC(__write_lock_failed)
//获取读锁失败时调用
ENTRY(__read_lock_failed)
    //(%eax)表示由eax指向的内存空间是调用者传进来的 
    2:LOCK_PREFIX incl(%eax)//原子加1
    1:  rep; nop//空指令
    cmpl  $1,(%eax) //和1比较 小于0则
    js 1b //为负则继续循环比较
    LOCK_PREFIX decl(%eax) //加读锁
    js  2b  //为负则继续加1并比较,否则返回
    ret //返回
ENDPROC(__read_lock_failed)
//获取读锁
static inline void arch_read_lock(arch_rwlock_t*rw){
    asm volatile(
        LOCK_PREFIX" subl $1,(%0)\n\t"//原子对lock减1
        "jns 1f\n"//不为小于0则跳转标号1处,表示获取读锁成功
        "call __read_lock_failed\n\t"//调用__read_lock_failed
        "1:\n"
        ::LOCK_PTR_REG(rw):"memory");
}
//获取写锁
static inline void arch_write_lock(arch_rwlock_t*rw){
    asm volatile(
        LOCK_PREFIX"subl %1,(%0)\n\t"//原子对lock减去RW_LOCK_BIAS
        "jz 1f\n"//为0则跳转标号1处
        "call __write_lock_failed\n\t"//调用__write_lock_failed
        "1:\n"
        ::LOCK_PTR_REG(rw),"i"(RW_LOCK_BIAS):"memory");
}

计数器lock的初始值为0x01000000

  1. 获取读锁时,lock加1,判断lock的符号位是否为0(即lock是否大于0)为0则表示加锁成功; 否则表示获取读锁失败,此时调用__read_lock_failed,循环测试lock+1>=1

  2. 获取写时,lock减去初始值,判断lock是否为0,如果不为0则调用__write_lock_failed循环测试lock+0x01000000 == 0x01000000

第十讲:设置工作模式和环境

内核映像文件

iso_file_format

内核映像文件是由多个文件封装的一个文件,其中包含二级引导器的模块,内核模块,图片和文字库文件等。

GRUB通过上图中的4KB的GRUB头来识别映像文件,然后根据映像文件头描述符和文件头描述符的信息解析其他文件

 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
//映像文件头描述符
typedef struct s_mlosrddsc
{
    u64_t mdc_mgic; //映像文件标识
    u64_t mdc_sfsum;//未使用
    u64_t mdc_sfsoff;//未使用
    u64_t mdc_sfeoff;//未使用
    u64_t mdc_sfrlsz;//未使用
    u64_t mdc_ldrbk_s;//映像文件中二级引导器的开始偏移
    u64_t mdc_ldrbk_e;//映像文件中二级引导器的结束偏移
    u64_t mdc_ldrbk_rsz;//映像文件中二级引导器的实际大小
    u64_t mdc_ldrbk_sum;//映像文件中二级引导器的校验和
    u64_t mdc_fhdbk_s;//映像文件中文件头描述的开始偏移
    u64_t mdc_fhdbk_e;//映像文件中文件头描述的结束偏移
    u64_t mdc_fhdbk_rsz;//映像文件中文件头描述的实际大小
    u64_t mdc_fhdbk_sum;//映像文件中文件头描述的校验和
    u64_t mdc_filbk_s;//映像文件中文件数据的开始偏移
    u64_t mdc_filbk_e;//映像文件中文件数据的结束偏移
    u64_t mdc_filbk_rsz;//映像文件中文件数据的实际大小
    u64_t mdc_filbk_sum;//映像文件中文件数据的校验和
    u64_t mdc_ldrcodenr;//映像文件中二级引导器的文件头描述符的索引号
    u64_t mdc_fhdnr;//映像文件中文件头描述符有多少个
    u64_t mdc_filnr;//映像文件中文件头有多少个
    u64_t mdc_endgic;//映像文件结束标识
    u64_t mdc_rv;//映像文件版本
}mlosrddsc_t;

#define FHDSC_NMAX 192 //文件名长度
//文件头描述符
typedef struct s_fhdsc
{
    u64_t fhd_type;//文件类型
    u64_t fhd_subtype;//文件子类型
    u64_t fhd_stuts;//文件状态
    u64_t fhd_id;//文件id
    u64_t fhd_intsfsoff;//文件在映像文件位置开始偏移
    u64_t fhd_intsfend;//文件在映像文件的结束偏移
    u64_t fhd_frealsz;//文件实际大小
    u64_t fhd_fsum;//文件校验和
    char   fhd_name[FHDSC_NMAX];//文件名
}fhdsc_t;

内核映像文件使用lmoskrlimg打包

1
2
3
4
5
6
lmoskrlimg -m k -lhf GRUB头文件 -o 映像文件 -f 输入的文件列表
-m 表示模式 只能是k内核模式
-lhf 表示后面跟上GRUB头文件
-o 表示输出的映像文件名 
-f 表示输入文件列表
#例如:lmoskrlimg -m k -lhf grubhead.bin -o kernel.img -f file1.bin file2.bin file3.bin file4.bin 

准备环境

安装虚拟机

使用virtual box虚拟机

准备硬盘

生成纯二进制文件

1
2
3
4
5
6
7

dd bs=512 if=/dev/zero of=hd.img count=204800

#bs:表示块大小,这里是512字节
#if:表示输入文件,/dev/zero就是Linux下专门返回0数据的设备文件,读取它就返回0
#of:表示输出文件,即我们的硬盘文件。
#count:表示输出多少块

格式化(建立文件系统)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# 1. 将文件变成回环设备
# loop0可能被占用,换成其他名字即可 
sudo losetup /dev/loop0 hd.img

# 2. 建立文件系统
sudo mkfs.ext4 -q /dev/loop0

# 3. 挂载
# 挂载硬盘文件, 可通过 lsblk 命令验证结果
sudo mount -o loop ./hd.img  ./hdisk 
 # 建立boot目录
sudo mkdir ./hdist/boot 

安装GRUB

  1. 安装GRUB
1
2
3
4
5

# 安装GRUB
sudo grub-install --boot-directory=./hdisk/boot/ --force --allow-floppy /dev/loop0
# --boot-directory 指向先前我们在虚拟硬盘中建立的boot目录。
# --force --allow-floppy :指向我们的虚拟硬盘设备文件/dev/loop0
  1. 编写配置文件

在 /hdisk/boot/grub/ 目录建立 grub.config 文件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
menuentry 'HelloOS' {
insmod part_msdos
insmod ext2
set root='hd0,msdos1' #我们的硬盘只有一个分区所以是'hd0,msdos1'
multiboot2 /boot/HelloOS.eki #加载boot目录下的HelloOS.eki文件
boot #引导启动
}
set timeout_style=menu
if [ "${timeout}" = 0 ]; then
  set timeout=10 #等待10秒钟自动启动
fi

转成硬盘格式

将Linux识别的硬盘 转换成虚拟机识别的硬盘

VBoxManage是在宿主机执行,文件可通过共享文件夹传输

1
2
3
VBoxManage convertfromraw ./hd.img --format VDI ./hd.vdi
#convertfromraw 指向原始格式文件
#--format VDI  表示转换成虚拟需要的VDI格式

安装虚拟硬盘

1
2
3
4
5
6
7
8

# 第一步:配置硬盘控制器 
# SATA的硬盘其控制器是intelAHCI
VBoxManage storagectl HelloOS --name "SATA" --add sata --controller IntelAhci --portcount 1
# 第二步:挂载虚拟硬盘
VBoxManage closemedium disk ./hd.vdi #删除虚拟硬盘UUID并重新分配
#将虚拟硬盘挂到虚拟机的硬盘控制器
VBoxManage storageattach HelloOS --storagectl "SATA" --port 1 --device 0 --type hdd --medium ./hd.vdi

启动

1
VBoxManage startvm HelloOS #启动虚拟机

第十一讲:建造二级引导器

二级引导器作用

收集机器信息,对CPU、内存、显卡等进行初级配置

存储结构

收集的信息会存在如下的数据结构中

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct s_MACHBSTART
{
    u64_t   mb_krlinitstack;//内核栈地址
    u64_t   mb_krlitstacksz;//内核栈大小
    u64_t   mb_imgpadr;//操作系统映像
    u64_t   mb_imgsz;//操作系统映像大小
    u64_t   mb_bfontpadr;//操作系统字体地址
    u64_t   mb_bfontsz;//操作系统字体大小
    u64_t   mb_fvrmphyadr;//机器显存地址
    u64_t   mb_fvrmsz;//机器显存大小
    u64_t   mb_cpumode;//机器CPU工作模式
    u64_t   mb_memsz;//机器内存大小
    u64_t   mb_e820padr;//机器e820数组地址
    u64_t   mb_e820nr;//机器e820数组元素个数
    u64_t   mb_e820sz;//机器e820数组大小
    //……
    u64_t   mb_pml4padr;//机器页表数据地址
    u64_t   mb_subpageslen;//机器页表个数
    u64_t   mb_kpmapphymemsz;//操作系统映射空间大小
    //……
    graph_t mb_ghparm;//图形信息
}__attribute__((packed)) machbstart_t;

模块规划

modules

上图的文件经过编译会生成三个文件,具体流程如下

compile

然后用映像打包工具打包成映像文件

1
2

lmoskrlimg -m k -lhf initldrimh.bin -o Cosmos.eki -f initldrkrl.bin initldrsve.bin

实现GRUB头

GRUB头有两个文件

  • imginithead.asm汇编文件: 让GUR识别、设置C语言环境
  • inithead.c文件:查找引导器核心文件initldrkrl,bin文件并将其放到特定的内存地址上

imginithead.asm

主要工作是初始化CPU的 寄存器,加载GDT,切换到CPU的保护模式

首先是 GRUB1 和 GRUB2需要的带个头结构

 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
MBT_HDR_FLAGS  EQU 0x00010003
MBT_HDR_MAGIC  EQU 0x1BADB002
MBT2_MAGIC  EQU 0xe85250d6
global _start
extern inithead_entry
[section .text]
[bits 32]
_start:
  jmp _entry
align 4
mbt_hdr:
  dd MBT_HDR_MAGIC
  dd MBT_HDR_FLAGS
  dd -(MBT_HDR_MAGIC+MBT_HDR_FLAGS)
  dd mbt_hdr
  dd _start
  dd 0
  dd 0
  dd _entry
ALIGN 8
mbhdr:
  DD  0xE85250D6
  DD  0
  DD  mhdrend - mbhdr
  DD  -(0xE85250D6 + 0 + (mhdrend - mbhdr))
  DW  2, 0
  DD  24
  DD  mbhdr
  DD  _start
  DD  0
  DD  0
  DW  3, 0
  DD  12
  DD  _entry 
  DD  0  
  DW  0, 0
  DD  8
mhdrend:

关闭中断并加载GDT

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
_entry:
  cli           ;关中断
  in al, 0x70 
  or al, 0x80  
  out 0x70,al  ;关掉不可屏蔽中断   
  lgdt [GDT_PTR] ;加载GDT地址到GDTR寄存器
  jmp dword 0x8 :_32bits_mode ;长跳转刷新CS影子寄存器
  ;………………
;GDT全局段描述符表
GDT_START:
knull_dsc: dq 0
kcode_dsc: dq 0x00cf9e000000ffff
kdata_dsc: dq 0x00cf92000000ffff
k16cd_dsc: dq 0x00009e000000ffff 16位代码段描述符
k16da_dsc: dq 0x000092000000ffff 16位数据段描述符
GDT_END:
GDT_PTR:
GDTLEN  dw GDT_END-GDT_START-1  ;GDT界限
GDTBASE  dd GDT_ST  

初始化段寄存器、通用寄存器和栈寄存器

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

_32bits_mode
  mov ax, 0x10
  mov ds, ax
  mov ss, ax
  mov es, ax
  mov fs, ax
  mov gs, ax
  xor eax,eax
  xor ebx,ebx
  xor ecx,ecx
  xor edx,edx
  xor edi,edi
  xor esi,esi
  xor ebp,ebp
  xor esp,esp
  mov esp,0x7c00 ;设置栈顶为0x7c00
  call inithead_entry ;调用inithead_entry函数在inithead.c中实现
  jmp 0x200000  ;跳转到0x200000地址

上述代码最后调用了 inithead_entry 函数

inithead_entry分别调用了write_realintsvefilewrite_ldrkrlfile, 将映像文件中的initldrsve.bin文件和initldrkrl.bin文件写入到特定的内存中 其中有两个依赖函数find_filem2mcopy find_file函数负责扫描映像文件中的文件头描述符,对比其中的文件名, 然后返回对应的文件的文件头描述符地址,这样就可以得到其位置和大小

m2mcopy函数 负责将 映像文件复制到具体的内存空间中

 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

#define MDC_ENDGIC 0xaaffaaffaaffaaff
#define MDC_RVGIC 0xffaaffaaffaaffaa
#define REALDRV_PHYADR 0x1000
#define IMGFILE_PHYADR 0x4000000
#define IMGKRNL_PHYADR 0x2000000
#define LDRFILEADR IMGFILE_PHYADR
#define MLOSDSC_OFF (0x1000)
#define MRDDSC_ADR (mlosrddsc_t*)(LDRFILEADR+0x1000)

void inithead_entry()
{
    write_realintsvefile();
    write_ldrkrlfile();
    return;
}
//写initldrsve.bin文件到特定的内存中
void write_realintsvefile()
{
    fhdsc_t *fhdscstart = find_file("initldrsve.bin");
    if (fhdscstart == NULL)
    {
        error("not file initldrsve.bin");
    }
    m2mcopy((void *)((u32_t)(fhdscstart->fhd_intsfsoff) + LDRFILEADR),
            (void *)REALDRV_PHYADR, (sint_t)fhdscstart->fhd_frealsz);
    return;
}
//写initldrkrl.bin文件到特定的内存中
void write_ldrkrlfile()
{
    fhdsc_t *fhdscstart = find_file("initldrkrl.bin");
    if (fhdscstart == NULL)
    {
        error("not file initldrkrl.bin");
    }
    m2mcopy((void *)((u32_t)(fhdscstart->fhd_intsfsoff) + LDRFILEADR),
            (void *)ILDRKRL_PHYADR, (sint_t)fhdscstart->fhd_frealsz);
    return;
}
//在映像文件中查找对应的文件
fhdsc_t *find_file(char_t *fname)
{
    mlosrddsc_t *mrddadrs = MRDDSC_ADR;
    if (mrddadrs->mdc_endgic != MDC_ENDGIC ||
        mrddadrs->mdc_rv != MDC_RVGIC ||
        mrddadrs->mdc_fhdnr < 2 ||
        mrddadrs->mdc_filnr < 2)
    {
        error("no mrddsc");
    }
    s64_t rethn = -1;
    fhdsc_t *fhdscstart = (fhdsc_t *)((u32_t)(mrddadrs->mdc_fhdbk_s) + LDRFILEADR);
    for (u64_t i = 0; i < mrddadrs->mdc_fhdnr; i++)
    {
        if (strcmpl(fname, fhdscstart[i].fhd_name) == 0)
        {
            rethn = (s64_t)i;
            goto ok_l;
        }
    }
    rethn = -1;
ok_l:
    if (rethn < 0)
    {
        error("not find file");
    }
    return &fhdscstart[rethn];
}

进入二级引导器

imginithead.asm最后的指令jump 0x200000跳转到了物理内存地址0x200000地址处 这个地址放置的正是initldrkrk.bin文件 这一跳进入了二级引导器的主模块

由于模块的 改变,需要写一小段汇编代码,建立下面这个initldr32.asm文件

重新把GDT(段描述符表)、IDT(中断选择子表)和寄存器重新初始化,然后调用二级引导器的主函数ldrkrl_entry

 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

_entry:
  cli
  lgdt [GDT_PTR];加载GDT地址到GDTR寄存器
  lidt [IDT_PTR];加载IDT地址到IDTR寄存器
  jmp dword 0x8 :_32bits_mode;长跳转刷新CS影子寄存器
_32bits_mode:
  mov ax, 0x10  ; 数据段选择子(目的)
  mov ds, ax
  mov ss, ax
  mov es, ax
  mov fs, ax
  mov gs, ax
  xor eax,eax
  xor ebx,ebx
  xor ecx,ecx
  xor edx,edx
  xor edi,edi
  xor esi,esi
  xor ebp,ebp
  xor esp,esp
  mov esp,0x90000 ;使得栈底指向了0x90000
  call ldrkrl_entry ;调用ldrkrl_entry函数
  xor ebx,ebx
  jmp 0x2000000 ;跳转到0x2000000的内存地址
  jmp $
GDT_START:
knull_dsc: dq 0
kcode_dsc: dq 0x00cf9a000000ffff ;a-e
kdata_dsc: dq 0x00cf92000000ffff
k16cd_dsc: dq 0x00009a000000ffff 16位代码段描述符
k16da_dsc: dq 0x000092000000ffff 16位数据段描述符
GDT_END:
GDT_PTR:
GDTLEN  dw GDT_END-GDT_START-1  ;GDT界限
GDTBASE  dd GDT_START

IDT_PTR:
IDTLEN  dw 0x3ff
IDTBAS  dd 0  ;这是BIOS中断表的地址和长度

调用BIOS中断

因为获取内存布局信息、设置显卡图像 模式等功能需要依赖BIOS的中断服务

可是BIOS中断工作在16位实模式,所以需要上下文切换,大体流程如下:

  1. 保存C语言环境下的 CPU上线文,即保护模式下的所有通用寄存器、段寄存器、程序指针寄存器和栈寄存器
  2. 切换到实模式,调用BIOS中断,把中断结果保存在内存中
  3. 切换回保护模式,加载之前保存的寄存器
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

realadr_call_entry:
  pushad     ;保存通用寄存器
  push    ds
  push    es
  push    fs ;保存4个段寄存器
  push    gs
  call save_eip_jmp ;调用save_eip_jmp 
  pop  gs
  pop  fs
  pop  es      ;恢复4个段寄存器
  pop  ds
  popad       ;恢复通用寄存器
  ret
save_eip_jmp:
  pop esi  ;弹出call save_eip_jmp时保存的eip到esi寄存器中 
  mov [PM32_EIP_OFF],esi ;把eip保存到特定的内存空间中
  mov [PM32_ESP_OFF],esp ;把esp保存到特定的内存空间中
  jmp dword far [cpmty_mode];长跳转这里表示把cpmty_mode处的第一个4字节装入eip,把其后的2字节装入cs
cpmty_mode:
  dd 0x1000
  dw 0x18
  jmp $

jmp dword far [cpmty_mode]指令表示把 [cpmty_mode] 处的数据装入 CS: EIP, 即把 0x18: 0x1000 装入 CS: EIP 中, 0x18 是段描述索引,指向GDT中的 16 位代码段描述符, 0x10000 表示段内地址偏移

这个地址起始的代码如下

 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

[bits 16]
_start:
_16_mode:
  mov  bp,0x20 ;0x20是指向GDT中的16位数据段描述符 
  mov  ds, bp
  mov  es, bp
  mov  ss, bp
  mov  ebp, cr0
  and  ebp, 0xfffffffe
  mov  cr0, ebp CR0.P=0 关闭保护模式
  jmp  0:real_entry ;刷新CS影子寄存器,真正进入实模式
real_entry:
  mov bp, cs
  mov ds, bp
  mov es, bp
  mov ss, bp ;重新设置实模式下的段寄存器 都是CS中值,即为0 
  mov sp, 08000h ;设置栈
  mov bp,func_table
  add bp,ax
  call [bp] ;调用函数表中的汇编函数,ax是C函数中传递进来的
  cli
  call disable_nmi
  mov  ebp, cr0
  or  ebp, 1
  mov  cr0, ebp CR0.P=1 开启保护模式
  jmp dword 0x8 :_32bits_mode
[BITS 32]
_32bits_mode:
  mov bp, 0x10
  mov ds, bp
  mov ss, bp;重新设置保护模式下的段寄存器0x1032位数据段描述符的索引
  mov esi,[PM32_EIP_OFF];加载先前保存的EIP
  mov esp,[PM32_ESP_OFF];加载先前保存的ESP
  jmp esi eip=esi 回到了realadr_call_entry函数中

func_table:  ;函数表
  dw _getmmap ;获取内存布局视图的函数
  dw _read ;读取硬盘的函数
    dw _getvbemode ;获取显卡VBE模式 
    dw _getvbeonemodeinfo ;获取显卡VBE模式的数据
    dw _setvbemode ;设置显卡VBE模式

上面的代码将其编译成16位的二进制文件,然后放在0x10000开始的内存空间 代码流程如下:

  1. _16_mode进入实模式
  2. real_entry根据ax寄存器的值找到函数表对应的函数,执行完后再次进入保护模式
  3. 加载EIP和ESP寄存器,从而回到realadr_call_entry函数

引导器主函数

1
2
3
4
5
void ldrkrl_entry()
{
    init_bstartparm();
    return;
}

ldrkrl_entry函数在initldr32.asm文件中被调用

第十二讲:探查和收集信息

入口函数ldrkrl_entry实际调用了init_bstartparm

初始化

首先在1MB的内存地址处初始化了一个机器信息结构machbstart_t

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
//初始化machbstart_t结构体,清0,并设置一个标志
void machbstart_t_init(machbstart_t* initp)
{
    memset(initp,0,sizeof(machbstart_t));
    initp->mb_migc=MBS_MIGC;
    return;
}
void init_bstartparm()
{
    machbstart_t* mbsp = MBSPADR;//1MB的内存地址
    machbstart_t_init(mbsp);
    return;
}

检查CPU

我们需要检查CPU,主要通过两个函数实现:

  • chk_cpuid: 检查CPU是否支持CPUID指令
  • chk_cpuid: 用CPUID指令检查CPU是否支持64位长模式
 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
//通过改写Eflags寄存器的第21位,观察其位的变化判断是否支持CPUID
int chk_cpuid()
{
    int rets = 0;
    __asm__ __volatile__(
        "pushfl \n\t"
        "popl %%eax \n\t"
        "movl %%eax,%%ebx \n\t"
        "xorl $0x0200000,%%eax \n\t"
        "pushl %%eax \n\t"
        "popfl \n\t"
        "pushfl \n\t"
        "popl %%eax \n\t"
        "xorl %%ebx,%%eax \n\t"
        "jz 1f \n\t"
        "movl $1,%0 \n\t"
        "jmp 2f \n\t"
        "1: movl $0,%0 \n\t"
        "2: \n\t"
        : "=c"(rets)
        :
        :);
    return rets;
}
//检查CPU是否支持长模式
int chk_cpu_longmode()
{
    int rets = 0;
    __asm__ __volatile__(
        "movl $0x80000000,%%eax \n\t"
        "cpuid \n\t" //把eax中放入0x80000000调用CPUID指令
        "cmpl $0x80000001,%%eax \n\t"//看eax中返回结果
        "setnb %%al \n\t" //不为0x80000001,则不支持0x80000001号功能
        "jb 1f \n\t"
        "movl $0x80000001,%%eax \n\t"
        "cpuid \n\t"//把eax中放入0x800000001调用CPUID指令,检查edx中的返回数据
        "bt $29,%%edx  \n\t" //长模式 支持位  是否为1
        "setcb %%al \n\t"
        "1: \n\t"
        "movzx %%al,%%eax \n\t"
        : "=a"(rets)
        :
        :);
    return rets;
}
//检查CPU主函数
void init_chkcpu(machbstart_t *mbsp)
{
    if (!chk_cpuid())
    {
        kerror("Your CPU is not support CPUID sys is die!");
        CLI_HALT();
    }
    if (!chk_cpu_longmode())
    {
        kerror("Your CPU is not support 64bits mode sys is die!");
        CLI_HALT();
    }
    mbsp->mb_cpumode = 0x40;//如果成功则设置机器信息结构的cpu模式为64位
    return;
}

获取内存布局

描述内存的数据结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#define RAM_USABLE 1 //可用内存
#define RAM_RESERV 2 //保留内存不可使用
#define RAM_ACPIREC 3 //ACPI表相关的
#define RAM_ACPINVS 4 //ACPI NVS空间
#define RAM_AREACON 5 //包含坏内存
typedef struct s_e820{
    u64_t saddr;    /* 内存开始地址 */
    u64_t lsize;    /* 内存大小 */
    u32_t type;    /* 内存类型 */
}e820map_t;

获取内存布局信息就是获取这个结构体的数组,具体实现代码如下:

 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

void mmap(e820map_t **retemp, u32_t *retemnr)
{
    realadr_call_entry(RLINTNR(0), 0, 0);
    *retemnr = *((u32_t *)(E80MAP_NR));
    *retemp = (e820map_t *)(*((u32_t *)(E80MAP_ADRADR)));
    return;
}


#define ETYBAK_ADR 0x2000
#define PM32_EIP_OFF (ETYBAK_ADR)
#define PM32_ESP_OFF (ETYBAK_ADR+4)
#define E80MAP_NR (ETYBAK_ADR+64)//保存e820map_t结构数组元素个数的地址
#define E80MAP_ADRADR (ETYBAK_ADR+68) //保存e820map_t结构数组的开始地址
void init_mem(machbstart_t *mbsp)
{
    e820map_t *retemp;
    u32_t retemnr = 0;
    mmap(&retemp, &retemnr);
    if (retemnr == 0)
    {
        kerror("no e820map\n");
    }
    //根据e820map_t结构数据检查内存大小
    if (chk_memsize(retemp, retemnr, 0x100000, 0x8000000) == NULL)
    {
        kerror("Your computer is low on memory, the memory cannot be less than 128MB!");
    }
    mbsp->mb_e820padr = (u64_t)((u32_t)(retemp));//把e820map_t结构数组的首地址传给mbsp->mb_e820padr 
    mbsp->mb_e820nr = (u64_t)retemnr;//把e820map_t结构数组元素个数传给mbsp->mb_e820nr 
    mbsp->mb_e820sz = retemnr * (sizeof(e820map_t));//把e820map_t结构数组大小传给mbsp->mb_e820sz 
    mbsp->mb_memsz = get_memsize(retemp, retemnr);//根据e820map_t结构数据计算内存大小。
    return;
}

其中mmap通过realadr_call_entry调用实模式下的_getmmap

 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

_getmmap:
  push ds
  push es
  push ss
  mov esi,0
  mov dword[E80MAP_NR],esi
  mov dword[E80MAP_ADRADR],E80MAP_ADR ;e820map结构体开始地址
  xor ebx,ebx
  mov edi,E80MAP_ADR
loop:
  mov eax,0e820h ;获取e820map结构参数
  mov ecx,20    ;e820map结构大小
  mov edx,0534d4150h ;获取e820map结构参数必须是这个数据
  int 15h  ;BIOS的15h中断
  jc .1
  add edi,20
  cmp edi,E80MAP_ADR+0x1000
  jg .1
  inc esi
  cmp ebx,0
  jne loop ;循环获取e820map结构
  jmp .2
.1:
  mov esi,0    ;出错处理,e820map结构数组元素个数为0
.2:
  mov dword[E80MAP_NR],esi ;e820map结构数组元素个数
  pop ss
  pop es
  pop ds
  ret

初始化内核栈

因为操作系统使用C语言写的,所以需要有栈

初始化其实就是在机器信息结构machbstart_t中记录一下栈顶地址和栈大小

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#define IKSTACK_PHYADR (0x90000-0x10)
#define IKSTACK_SIZE 0x1000
//初始化内核栈
void init_krlinitstack(machbstart_t *mbsp)
{   
    // 检查是否 和已经用到的内存空间(0x8f000 ~ 0x8f000_0x1001)冲突
    if (1 > move_krlimg(mbsp, (u64_t)(0x8f000), 0x1001))
    {
        kerror("iks_moveimg err");
    }
    mbsp->mb_krlinitstack = IKSTACK_PHYADR;//栈顶地址
    mbsp->mb_krlitstacksz = IKSTACK_SIZE; //栈大小是4KB
    return;
}

放置内核文件和字库文件

从映像文件中解析出来放在特定内存空间中

 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
//放置内核文件
void init_krlfile(machbstart_t *mbsp)
{
//在映像中查找相应的文件,并复制到对应的地址,并返回文件的大小,这里是查找kernel.bin文件
    u64_t sz = r_file_to_padr(mbsp, IMGKRNL_PHYADR, "kernel.bin");
    if (0 == sz)
    {
        kerror("r_file_to_padr err");
    }
    //放置完成后更新机器信息结构中的数据
    mbsp->mb_krlimgpadr = IMGKRNL_PHYADR;
    mbsp->mb_krlsz = sz;
    //mbsp->mb_nextwtpadr始终要保持指向下一段空闲内存的首地址 
    mbsp->mb_nextwtpadr = P4K_ALIGN(mbsp->mb_krlimgpadr + mbsp->mb_krlsz);
    mbsp->mb_kalldendpadr = mbsp->mb_krlimgpadr + mbsp->mb_krlsz;
    return;
}
//放置字库文件
void init_defutfont(machbstart_t *mbsp)
{
    u64_t sz = 0;
    //获取下一段空闲内存空间的首地址 
    u32_t dfadr = (u32_t)mbsp->mb_nextwtpadr;
//在映像中查找相应的文件,并复制到对应的地址,并返回文件的大小,这里是查找font.fnt文件
    sz = r_file_to_padr(mbsp, dfadr, "font.fnt");
    if (0 == sz)
    {
        kerror("r_file_to_padr err");
    }
    //放置完成后更新机器信息结构中的数据
    mbsp->mb_bfontpadr = (u64_t)(dfadr);
    mbsp->mb_bfontsz = sz;
    //更新机器信息结构中下一段空闲内存的首地址  
    mbsp->mb_nextwtpadr = P4K_ALIGN((u32_t)(dfadr) + sz);
    mbsp->mb_kalldendpadr = mbsp->mb_bfontpadr + mbsp->mb_bfontsz;
    return;
}

建立MMU页表数据

Memory Management Unit

内核虚拟地址空间从 0xffff800000000000 开始,大小为 16GB, 所以映射关系为:0xffff800000000000~0xffff800400000000 映射到物理地址空间 0~0x400000000

 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
#define KINITPAGE_PHYADR 0x1000000
void init_bstartpages(machbstart_t *mbsp)
{
    //顶级页目录
    u64_t *p = (u64_t *)(KINITPAGE_PHYADR);//16MB地址处
    //页目录指针
    u64_t *pdpte = (u64_t *)(KINITPAGE_PHYADR + 0x1000);
    //页目录
    u64_t *pde = (u64_t *)(KINITPAGE_PHYADR + 0x2000);
    //物理地址从0开始
    u64_t adr = 0;
    if (1 > move_krlimg(mbsp, (u64_t)(KINITPAGE_PHYADR), (0x1000 * 16 + 0x2000)))
    {
        kerror("move_krlimg err");
    }
    //将顶级页目录、页目录指针的空间清0
    for (uint_t mi = 0; mi < PGENTY_SIZE; mi++)
    {
        p[mi] = 0;
        pdpte[mi] = 0;
    }
    //映射
    for (uint_t pdei = 0; pdei < 16; pdei++)
    {
        pdpte[pdei] = (u64_t)((u32_t)pde | KPDPTE_RW | KPDPTE_P);
        for (uint_t pdeii = 0; pdeii < PGENTY_SIZE; pdeii++)
        {//大页KPDE_PS 2MB,可读写KPDE_RW,存在KPDE_P
            pde[pdeii] = 0 | adr | KPDE_PS | KPDE_RW | KPDE_P;
            adr += 0x200000;
        }
        pde = (u64_t *)((u32_t)pde + 0x1000);
    }
    //让顶级页目录中第0项和第((KRNL_VIRTUAL_ADDRESS_START) >> KPML4_SHIFT) & 0x1ff项,指向同一个页目录指针页  
    p[((KRNL_VIRTUAL_ADDRESS_START) >> KPML4_SHIFT) & 0x1ff] = (u64_t)((u32_t)pdpte | KPML4_RW | KPML4_P);
    p[0] = (u64_t)((u32_t)pdpte | KPML4_RW | KPML4_P);
    //把页表首地址保存在机器信息结构中
    mbsp->mb_pml4padr = (u64_t)(KINITPAGE_PHYADR);
    mbsp->mb_subpageslen = (u64_t)(0x1000 * 16 + 0x2000);
    mbsp->mb_kpmapphymemsz = (u64_t)(0x400000000);
    return;
}

为了简化编程,使用了长模式下的 2MB 分页方式

映射的核心逻辑由两重循环控制,外层循环控制页目录指针顶,只有 16 项,其中每一项都指向一个页目录,每个页目录中有 512 个物理页地址

物理地址每次增加 2MB,这是由 26~30 行的内层循环控制,每执行一次外层循环就要执行 512 次内层循环。

最后,顶级页目录中第 0 项和第 ((KRNL_VIRTUAL_ADDRESS_START) » KPML4_SHIFT) & 0x1ff 项,指向同一个页目录指针页,这样的话就能让虚拟地址:0xffff800000000000~0xffff800400000000 和虚拟地址:0~0x400000000,访问到同一个物理地址空间 0~0x400000000,这样做是有目的,内核在启动初期,虚拟地址和物理地址要保持相同。

设置显卡图形模式

显卡默认是文本模式,只能显示ASCII字符,需要切换到图形模式

切换显卡模式需要使用BIOS中断

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void init_graph(machbstart_t* mbsp)
{
    //初始化图形数据结构
    graph_t_init(&mbsp->mb_ghparm);
    //获取VBE模式,通过BIOS中断
    get_vbemode(mbsp);
    //获取一个具体VBE模式的信息,通过BIOS中断
    get_vbemodeinfo(mbsp);
    //设置VBE模式,通过BIOS中断
    set_vbemodeinfo();
    return;
}

这里使用了 VBE 的 118h 模式,该模式屏幕f分辨率为 1024*768,显存大小是 16.8MB

屏幕分辨率为 1024 * 768,即共768行,为行1024个像素点, 每个像素点占32位空间(红、绿、蓝、透明各8位)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

typedef struct s_PIXCL
{
    u8_t cl_b; //蓝
    u8_t cl_g; //绿
    u8_t cl_r; //红
    u8_t cl_a; //透明
}__attribute__((packed)) pixcl_t;

#define BGRA(r,g,b) ((0|(r<<16)|(g<<8)|b))
//通常情况下用pixl_t 和 BGRA宏
typedef u32_t pixl_t;


u32_t* dispmem = (u32_t*)mbsp->mb_ghparm.gh_framphyadr;
dispmem[x + (y * 1024)] = pix;
//x,y是像素的位置

集成

init_bstartparm将上述功能串联起来,设置工作环境

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void init_bstartparm()
{
    machbstart_t *mbsp = MBSPADR;
    machbstart_t_init(mbsp);
    //检查CPU
    init_chkcpu(mbsp);
    //获取内存布局
    init_mem(mbsp);
    //初始化内核栈
    init_krlinitstack(mbsp);
    //放置内核文件
    init_krlfile(mbsp);
    //放置字库文件
    init_defutfont(mbsp);
    //将e820map结构数组从低地址(0x2068)搬到高地址(0x2000000)
    init_meme820(mbsp);
    //建立MMU页表
    init_bstartpages(mbsp);
    //设置图形模式
    init_graph(mbsp);
    return;
}

前面已经设置了图形模式,可以展示图片了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void logo(machbstart_t* mbsp)
{
    u32_t retadr=0,sz=0;
    //在映像文件中获取logo.bmp文件
    get_file_rpadrandsz("logo.bmp",mbsp,&retadr,&sz);
    if(0==retadr)
    {
        kerror("logo getfilerpadrsz err");
    }
    //显示logo文件中的图像数据
    bmp_print((void*)retadr,mbsp);
    return;
}
void init_graph(machbstart_t* mbsp)
{    
    //……前面代码省略
    //显示
    logo(mbsp);
    return;
}

切换CPU到长模式

切换到长模式(64位)后,寄存器位宽变了,需要重新初始化

 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
[section .start.text]
[BITS 32]
_start:
    cli
    mov ax,0x10
    mov ds,ax
    mov es,ax
    mov ss,ax
    mov fs,ax
    mov gs,ax
    lgdt [eGdtPtr]        
    ;开启 PAE
    mov eax, cr4
    bts eax, 5                      ; CR4.PAE = 1
    mov cr4, eax
    mov eax, PML4T_BADR             ;加载MMU顶级页目录
    mov cr3, eax  
    ;开启 64bits long-mode
    mov ecx, IA32_EFER
    rdmsr
    bts eax, 8                      ; IA32_EFER.LME =1
    wrmsr
    ;开启 PE 和 paging
    mov eax, cr0
    bts eax, 0                      ; CR0.PE =1
    bts eax, 31
    ;开启 CACHE       
    btr eax,29                    ; CR0.NW=0
    btr eax,30                    ; CR0.CD=0  CACHE
    mov cr0, eax                    ; IA32_EFER.LMA = 1
    jmp 08:entry64
[BITS 64]
entry64:
    mov ax,0x10
    mov ds,ax
    mov es,ax
    mov ss,ax
    mov fs,ax
    mov gs,ax
    xor rax,rax
    xor rbx,rbx
    xor rbp,rbp
    xor rcx,rcx
    xor rdx,rdx
    xor rdi,rdi
    xor rsi,rsi
    xor r8,r8
    xor r9,r9
    xor r10,r10
    xor r11,r11
    xor r12,r12
    xor r13,r13
    xor r14,r14
    xor r15,r15
    mov rbx,MBSP_ADR
    mov rax,KRLVIRADR
    mov rcx,[rbx+KINITSTACK_OFF]
    add rax,rcx
    xor rcx,rcx
    xor rbx,rbx
    mov rsp,rax
    push 0
    push 0x8
    mov rax,hal_start                 ;调用内核主函数
    push rax
    dw 0xcb48
    jmp $
[section .start.data]
[BITS 32]
x64_GDT:
enull_x64_dsc:  dq 0  
ekrnl_c64_dsc:  dq 0x0020980000000000   ; 64-bit 内核代码段
ekrnl_d64_dsc:  dq 0x0000920000000000   ; 64-bit 内核数据段
euser_c64_dsc:  dq 0x0020f80000000000   ; 64-bit 用户代码段
euser_d64_dsc:  dq 0x0000f20000000000   ; 64-bit 用户数据段
eGdtLen      equ  $ - enull_x64_dsc   ; GDT长度
eGdtPtr:    dw eGdtLen - 1      ; GDT界限
        dq ex64_GDT

上述代码具体详情是:

  • 1~11行加载70~75行的 GDT
  • 13~17行设置MMU、加载二级引导器中准备好的MMU页表
  • 19~30行开启长模式、打开Cache
  • 34~54行初始化寄存器
  • 55~61行读取二级引导器中准备好的机器信息结构的栈地址存到RSP寄存器
  • 63~66行把8和hal_start函数地址压入栈,利用dw 0xcb48指令将数据弹出到 RIP和CS寄存器

第十三讲 实现板级初始化

hal层初始化

hal层对硬件相关的操作进行了抽象,对内核提供接口

初始化平台

init_halplaltform主要完成两个任务:

  • 复制二级引导器建立的机器信息结构到hal层中的全局变量中,并释放二级引导器对应数据的内存
  • 初始化图形显卡的驱动
 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
void machbstart_t_init(machbstart_t *initp)
{
    //清零
    memset(initp, 0, sizeof(machbstart_t));
    return;
}

void init_machbstart()
{
    machbstart_t *kmbsp = &kmachbsp;
    machbstart_t *smbsp = MBSPADR;//物理地址1MB处
    machbstart_t_init(kmbsp);
    //复制,要把地址转换成虚拟地址
    memcopy((void *)phyadr_to_viradr((adr_t)smbsp), (void *)kmbsp, sizeof(machbstart_t));
    return;
}
//平台初始化函数
void init_halplaltform()
{
    //复制机器信息结构
    init_machbstart();
    //初始化图形显示驱动
    init_bdvideo();
    return;
}

kmachbsp是个hal层的全局变量,通过宏声明

1
2
3
4
5
6
//file: Comos/hal/x86
//全局变量定义变量放在data段
#define  HAL_DEFGLOB_VARIABLE(vartype, varnam) \
EXTERN __attribute__((section(".data"))) vartype varname

HAL_DEFGLOB_VARIABLE(machbstart_t, kmachbsp); 

图形显卡初始化

 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

void init_bdvideo()
{
    dftgraph_t *kghp = &kdftgh;
    //初始化图形数据结构,里面放有图形模式,分辨率,图形驱动函数指针
    init_dftgraph();
    //初始bga图形显卡的函数指针
    init_bga();
    //初始vbe图形显卡的函数指针
    init_vbe();
    //清空屏幕 为黑色
    fill_graph(kghp, BGRA(0, 0, 0));
    //显示背景图片 
    set_charsdxwflush(0, 0);
    hal_background();
    return;
}


typedef struct s_DFTGRAPH
{
    u64_t gh_mode;         //图形模式
    u64_t gh_x;            //水平像素点
    u64_t gh_y;            //垂直像素点
    u64_t gh_framphyadr;   //显存物理地址 
    u64_t gh_fvrmphyadr;   //显存虚拟地址
    u64_t gh_fvrmsz;       //显存大小
    u64_t gh_onepixbits;   //一个像素字占用的数据位数
    u64_t gh_onepixbyte;
    u64_t gh_vbemodenr;    //vbe模式号
    u64_t gh_bank;         //显存的bank数
    u64_t gh_curdipbnk;    //当前bank
    u64_t gh_nextbnk;      //下一个bank
    u64_t gh_banksz;       //bank大小
    u64_t gh_fontadr;      //字库地址
    u64_t gh_fontsz;       //字库大小
    u64_t gh_fnthight;     //字体高度
    u64_t gh_nxtcharsx;    //下一字符显示的x坐标
    u64_t gh_nxtcharsy;    //下一字符显示的y坐标
    u64_t gh_linesz;       //字符行高
    pixl_t gh_deffontpx;   //默认字体大小
    u64_t gh_chardxw;
    u64_t gh_flush;
    u64_t gh_framnr;
    u64_t gh_fshdata;      //刷新相关的
    dftghops_t gh_opfun;   //图形驱动操作函数指针结构体
}dftgraph_t;
typedef struct s_DFTGHOPS
{
    //读写显存数据
    size_t (*dgo_read)(void* ghpdev,void* outp,size_t rdsz);
    size_t (*dgo_write)(void* ghpdev,void* inp,size_t wesz);
    sint_t (*dgo_ioctrl)(void* ghpdev,void* outp,uint_t iocode);
    //刷新
    void   (*dgo_flush)(void* ghpdev);
    sint_t (*dgo_set_bank)(void* ghpdev, sint_t bnr);
    //读写像素
    pixl_t (*dgo_readpix)(void* ghpdev,uint_t x,uint_t y);
    void   (*dgo_writepix)(void* ghpdev,pixl_t pix,uint_t x,uint_t y);
    //直接读写像素 
    pixl_t (*dgo_dxreadpix)(void* ghpdev,uint_t x,uint_t y);
    void   (*dgo_dxwritepix)(void* ghpdev,pixl_t pix,uint_t x,uint_t y);
    //设置x,y坐标和偏移
    sint_t (*dgo_set_xy)(void* ghpdev,uint_t x,uint_t y);
    sint_t (*dgo_set_vwh)(void* ghpdev,uint_t vwt,uint_t vhi);
    sint_t (*dgo_set_xyoffset)(void* ghpdev,uint_t xoff,uint_t yoff);
    //获取x,y坐标和偏移
    sint_t (*dgo_get_xy)(void* ghpdev,uint_t* rx,uint_t* ry);
    sint_t (*dgo_get_vwh)(void* ghpdev,uint_t* rvwt,uint_t* rvhi);
    sint_t (*dgo_get_xyoffset)(void* ghpdev,uint_t* rxoff,uint_t* ryoff);
}dftghops_t;
//刷新显存
void flush_videoram(dftgraph_t *kghp)
{
    kghp->gh_opfun.dgo_flush(kghp);
    return;
}

我们将实际的图形驱动函数填入了dftghops_t结构体,通过结构体就可以调用相应的函数了

初始化内存

对二级引导器的内存布局信息进行扩展:

  • 增加内存保留空间
  • 对布局信息进行排序
 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

#define PMR_T_OSAPUSERRAM 1
#define PMR_T_RESERVRAM 2
#define PMR_T_HWUSERRAM 8
#define PMR_T_ARACONRAM 0xf
#define PMR_T_BUGRAM 0xff
#define PMR_F_X86_32 (1<<0)
#define PMR_F_X86_64 (1<<1)
#define PMR_F_ARM_32 (1<<2)
#define PMR_F_ARM_64 (1<<3)
#define PMR_F_HAL_MASK 0xff

typedef struct s_PHYMMARGE
{
    spinlock_t pmr_lock;//保护这个结构是自旋锁
    u32_t pmr_type;     //内存地址空间类型
    u32_t pmr_stype;
    u32_t pmr_dtype;    //内存地址空间的子类型,见上面的宏
    u32_t pmr_flgs;     //结构的标志与状态
    u32_t pmr_stus;
    u64_t pmr_saddr;    //内存空间的开始地址
    u64_t pmr_lsize;    //内存空间的大小
    u64_t pmr_end;      //内存空间的结束地址
    u64_t pmr_rrvmsaddr;//内存保留空间的开始地址
    u64_t pmr_rrvmend;  //内存保留空间的结束地址
    void* pmr_prip;     //结构的私有数据指针,以后扩展所用
    void* pmr_extp;     //结构的扩展数据指针,以后扩展所用
}phymmarge_t;


u64_t initpmrge_core(e820map_t *e8sp, u64_t e8nr, phymmarge_t *pmargesp)
{
    u64_t retnr = 0;
    for (u64_t i = 0; i < e8nr; i++)
    {
        //根据一个e820map_t结构建立一个phymmarge_t结构
        if (init_one_pmrge(&e8sp[i], &pmargesp[i]) == FALSE)
        {
            return retnr;
        }
        retnr++;
    }
    return retnr;
}
void init_phymmarge()
{
    machbstart_t *mbsp = &kmachbsp;
    phymmarge_t *pmarge_adr = NULL;
    u64_t pmrgesz = 0;
    //根据machbstart_t机器信息结构计算获得phymmarge_t结构的开始地址和大小
    ret_phymmarge_adrandsz(mbsp, &pmarge_adr, &pmrgesz);
    u64_t tmppmrphyadr = mbsp->mb_nextwtpadr;
    e820map_t *e8p = (e820map_t *)((adr_t)(mbsp->mb_e820padr));
    //建立phymmarge_t结构
    u64_t ipmgnr = initpmrge_core(e8p, mbsp->mb_e820nr, pmarge_adr);
    //把phymmarge_t结构的地址大小个数保存machbstart_t机器信息结构中
    mbsp->mb_e820expadr = tmppmrphyadr;
    mbsp->mb_e820exnr = ipmgnr;
    mbsp->mb_e820exsz = ipmgnr * sizeof(phymmarge_t);
    mbsp->mb_nextwtpadr = PAGE_ALIGN(mbsp->mb_e820expadr + mbsp->mb_e820exsz);
    //phymmarge_t结构中地址空间从低到高进行排序,我已经帮你写好了
    phymmarge_sort(pmarge_adr, ipmgnr);
    return;
}

初始化中断

数据结构为gate_t,最大为256,由IDTR寄存器指向

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
typedef struct s_GATE
{
        u16_t   offset_low;     /* 偏移 */
        u16_t   selector;       /* 段选择子 */
        u8_t    dcount;         /* 该字段只在调用门描述符中有效。如果在利用调用门调用子程序时引起特权级的转换和堆栈的改变,需要将外层堆栈中的参数复制到内层堆栈。该双字计数字段就是用于说明这种情况发生时,要复制的双字参数的数量。*/
        u8_t    attr;           /* P(1) DPL(2) DT(1) TYPE(4) */
        u16_t   offset_high;    /* 偏移的高位段 */
        u32_t   offset_high_h;
        u32_t   offset_resv;
}__attribute__((packed)) gate_t;
//定义中断表
HAL_DEFGLOB_VARIABLE(gate_t,x64_idt)[IDTMAX];

设置函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
//vector 向量也是中断号
//desc_type 中断门类型,中断门,陷阱门
//handler 中断处理程序的入口地址
//privilege 中断门的权限级别
void set_idt_desc(u8_t vector, u8_t desc_type, inthandler_t handler, u8_t privilege)
{
    gate_t *p_gate = &x64_idt[vector];
    u64_t base = (u64_t)handler;
    p_gate->offset_low = base & 0xFFFF;
    p_gate->selector = SELECTOR_KERNEL_CS;
    p_gate->dcount = 0;
    p_gate->attr = (u8_t)(desc_type | (privilege << 5));
    p_gate->offset_high = (u16_t)((base >> 16) & 0xFFFF);
    p_gate->offset_high_h = (u32_t)((base >> 32) & 0xffffffff);
    p_gate->offset_resv = 0;
    return;
}

中断处理程序负责保存CPU寄存器、调用中断程序、恢复CPU寄存器

保存和恢复寄存区汇编代码

  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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
//保存中断后的寄存器
%macro  SAVEALL  0
  push rax
  push rbx
  push rcx
  push rdx
  push rbp
  push rsi
  push rdi
  push r8
  push r9
  push r10
  push r11
  push r12
  push r13
  push r14
  push r15
  xor r14,r14
  mov r14w,ds
  push r14
  mov r14w,es
  push r14
  mov r14w,fs
  push r14
  mov r14w,gs
  push r14
%endmacro
//恢复中断后寄存器
%macro  RESTOREALL  0
  pop r14
  mov gs,r14w
  pop r14 
  mov fs,r14w
  pop r14
  mov es,r14w
  pop r14
  mov ds,r14w
  pop r15
  pop r14
  pop r13
  pop r12
  pop r11
  pop r10
  pop r9
  pop r8
  pop rdi
  pop rsi
  pop rbp
  pop rdx
  pop rcx
  pop rbx
  pop rax
  iretq
%endmacro
//保存异常下的寄存器
%macro  SAVEALLFAULT 0
  push rax
  push rbx
  push rcx
  push rdx
  push rbp
  push rsi
  push rdi
  push r8
  push r9
  push r10
  push r11
  push r12
  push r13
  push r14
  push r15
  xor r14,r14
  mov r14w,ds
  push r14
  mov r14w,es
  push r14
  mov r14w,fs
  push r14
  mov r14w,gs
  push r14
%endmacro
//恢复异常下寄存器
%macro  RESTOREALLFAULT  0
  pop r14
  mov gs,r14w
  pop r14 
  mov fs,r14w
  pop r14
  mov es,r14w
  pop r14
  mov ds,r14w
  pop r15
  pop r14
  pop r13
  pop r12
  pop r11
  pop r10
  pop r9
  pop r8
  pop rdi
  pop rsi
  pop rbp
  pop rdx
  pop rcx
  pop rbx
  pop rax
  add rsp,8
  iretq
%endmacro
//没有错误码CPU异常
%macro  SRFTFAULT 1
  push    _NOERRO_CODE
  SAVEALLFAULT
  mov r14w,0x10
  mov ds,r14w
  mov es,r14w
  mov fs,r14w
  mov gs,r14w
  mov   rdi,%1 ;rdi, rsi
  mov   rsi,rsp
  call   hal_fault_allocator
  RESTOREALLFAULT
%endmacro
//CPU异常
%macro  SRFTFAULT_ECODE 1
  SAVEALLFAULT
  mov r14w,0x10
  mov ds,r14w
  mov es,r14w
  mov fs,r14w
  mov gs,r14w
  mov   rdi,%1
  mov   rsi,rsp
  call   hal_fault_allocator
  RESTOREALLFAULT
%endmacro
//硬件中断
%macro  HARWINT  1
  SAVEALL
  mov r14w,0x10
  mov ds,r14w
  mov es,r14w
  mov fs,r14w
  mov gs,r14w
  mov  rdi, %1
  mov   rsi,rsp
  call    hal_intpt_allocator
  RESTOREALL
%endmacro


//除法错误异常 比如除0
exc_divide_error:
  SRFTFAULT 0
//单步执行异常
exc_single_step_exception:
  SRFTFAULT 1
exc_nmi:
  SRFTFAULT 2
//调试断点异常
exc_breakpoint_exception:
  SRFTFAULT 3
//溢出异常
exc_overflow:
  SRFTFAULT 4
//段不存在异常
exc_segment_not_present:
  SRFTFAULT_ECODE 11
//栈异常
exc_stack_exception:
  SRFTFAULT_ECODE 12
//通用异常
exc_general_protection:
  SRFTFAULT_ECODE 13
//缺页异常
exc_page_fault:
  SRFTFAULT_ECODE 14
hxi_exc_general_intpfault:
  SRFTFAULT 256
//硬件1~7号中断
hxi_hwint00:
  HARWINT  (INT_VECTOR_IRQ0+0)
hxi_hwint01:
  HARWINT  (INT_VECTOR_IRQ0+1)
hxi_hwint02:
  HARWINT  (INT_VECTOR_IRQ0+2)
hxi_hwint03:
  HARWINT  (INT_VECTOR_IRQ0+3)
hxi_hwint04:
  HARWINT  (INT_VECTOR_IRQ0+4)
hxi_hwint05:
  HARWINT  (INT_VECTOR_IRQ0+5)
hxi_hwint06:
  HARWINT  (INT_VECTOR_IRQ0+6)
hxi_hwint07:
  HARWINT  (INT_VECTOR_IRQ0+7)

初始化函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void init_idt_descriptor()
{
//一开始把所有中断的处理程序设置为保留的通用处理程序
    for (u16_t intindx = 0; intindx <= 255; intindx++)
    {
        set_idt_desc((u8_t)intindx, DA_386IGate, hxi_exc_general_intpfault, PRIVILEGE_KRNL);
    }
    set_idt_desc(INT_VECTOR_DIVIDE, DA_386IGate, exc_divide_error, PRIVILEGE_KRNL);
    set_idt_desc(INT_VECTOR_DEBUG, DA_386IGate, exc_single_step_exception, PRIVILEGE_KRNL);
    set_idt_desc(INT_VECTOR_NMI, DA_386IGate, exc_nmi, PRIVILEGE_KRNL);
    set_idt_desc(INT_VECTOR_BREAKPOINT, DA_386IGate, exc_breakpoint_exception, PRIVILEGE_USER);
    set_idt_desc(INT_VECTOR_OVERFLOW, DA_386IGate, exc_overflow, PRIVILEGE_USER);
//篇幅所限,未全部展示
    set_idt_desc(INT_VECTOR_PAGE_FAULT, DA_386IGate, exc_page_fault, PRIVILEGE_KRNL);
    set_idt_desc(INT_VECTOR_IRQ0 + 0, DA_386IGate, hxi_hwint00, PRIVILEGE_KRNL);
    set_idt_desc(INT_VECTOR_IRQ0 + 1, DA_386IGate, hxi_hwint01, PRIVILEGE_KRNL);
    set_idt_desc(INT_VECTOR_IRQ0 + 2, DA_386IGate, hxi_hwint02, PRIVILEGE_KRNL);
    set_idt_desc(INT_VECTOR_IRQ0 + 3, DA_386IGate, hxi_hwint03, PRIVILEGE_KRNL);
    //篇幅所限,未全部展示
     return;
}

CPU响应中断后,需要相应的分发器处理,具体的中断处理框架如下图

interrupt-process

中断异常描述数据结构intfltdsc_t

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

typedef struct s_INTFLTDSC{    
    spinlock_t  i_lock;    
    u32_t       i_flg;    
    u32_t       i_stus;    
    uint_t      i_prity;        //中断优先级    
    uint_t      i_irqnr;        //中断号    
    uint_t      i_deep;         //中断嵌套深度    
    u64_t       i_indx;         //中断计数    
    list_h_t    i_serlist;      //也可以使用中断回调函数的方式
    uint_t      i_sernr;        //中断回调函数个数   
    list_h_t    i_serthrdlst;   //中断线程链表头    
    uint_t      i_serthrdnr;    //中断线程个数    
    void*       i_onethread;    //只有一个中断线程时直接用指针    
    void*       i_rbtreeroot;   //如果中断线程太多则按优先级组成红黑树
    list_h_t    i_serfisrlst;      
    uint_t      i_serfisrnr;       
    void*       i_msgmpool;     //可能的中断消息池    
    void*       i_privp;    
    void*       i_extp;
}intfltdsc_t;

中断可以由另一个线程执行 ,也可以是一个回调函数,回调函数存放的结构体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
typedef drvstus_t (*intflthandle_t)(uint_t ift_nr,void* device,void* sframe); //中断处理函数的指针类型
typedef struct s_INTSERDSC{    
    list_h_t    s_list;        //在中断异常描述符中的链表
    list_h_t    s_indevlst;    //在设备描述描述符中的链表
    u32_t       s_flg;        
    intfltdsc_t* s_intfltp;    //指向中断异常描述符 
    void*       s_device;      //指向设备描述符
    uint_t      s_indx;    
    intflthandle_t s_handle;   //中断处理的回调函数指针
}intserdsc_t;

当内核或者设备 驱动要安装一个中断处理函数时,先申请一个intserdsc_t结构体,然后 把中断函数的地址写入其中,最后把结构体挂载到对应的intfltdsc_t中的i_serfisrlst链表中 由于中断信号有限,而驱动设备可以有更多,所以发生中断时,对应信号所有的处理函数会依次执行, 如果不是自己设备产生的中断,就会跳过。

分发器函数

 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
//中断处理函数
void hal_do_hwint(uint_t intnumb, void *krnlsframp)
{    
    intfltdsc_t *ifdscp = NULL;    
    cpuflg_t cpuflg;
    //根据中断号获取中断异常描述符地址    
    ifdscp = hal_retn_intfltdsc(intnumb);
    //对断异常描述符加锁并中断    
    hal_spinlock_saveflg_cli(&ifdscp->i_lock, &cpuflg);    
    ifdscp->i_indx++;    
    ifdscp->i_deep++;
    //运行中断处理的回调函数
    hal_run_intflthandle(intnumb, krnlsframp);    
    ifdscp->i_deep--;
    //解锁并恢复中断状态    
    hal_spinunlock_restflg_sti(&ifdscp->i_lock, &cpuflg);    
    return;
}
//异常分发器
void hal_fault_allocator(uint_t faultnumb, void *krnlsframp)
{
    //我们的异常处理回调函数也是放在中断异常描述符中的
    hal_do_hwint(faultnumb, krnlsframp);
    return;
}
//中断分发器
void hal_hwint_allocator(uint_t intnumb, void *krnlsframp)
{
    hal_do_hwint(intnumb, krnlsframp);
    return;
}

调用回调函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void hal_run_intflthandle(uint_t ifdnr, void *sframe)
{    
    intserdsc_t *isdscp;    
    list_h_t *lst;
    //根据中断号获取中断异常描述符地址    
    intfltdsc_t *ifdscp = hal_retn_intfltdsc(ifdnr);
    //遍历i_serlist链表    
    list_for_each(lst, &ifdscp->i_serlist)    
    {   
        //获取i_serlist链表上对象即intserdsc_t结构
        isdscp = list_entry(lst, intserdsc_t, s_list);  
        //调用中断处理回调函数      
        isdscp->s_handle(ifdnr, isdscp->s_device, sframe);    
    }
    return;
}

初始化中断控制器

中断控制器可以屏蔽或启动哪些设备,也可以设定设备之间的优先级 x86平台最开始使用的是8259A控制器,以级联的方式存在,有15个信号源

8259A

第十四讲 Linux初始化(上)

全局流程

机器加电后,BIOS会进行自检,然后加载引导设备中的引导扇区,在安装有Linux 操作系统的环境的引导扇区有GRUB程序,GRUB会加载Linux内核映像vmlinuz linux_boot1

从BIOS到GRUB

加电时,会将CS和IP寄存器设置为0XF000和0XFFF0,这个对应物理地址0XFFF0(CS左移4位+IP), 这个 地址连接了主板上的一个小 ROM芯片,这个芯片和内存有相同的访问机制和寻址方式, 只是在断电时也不会丢失数据,BIOS程序就存储在这个芯片上。

BIOS一开始会初始化CPU;然后检查内存,将自己的一部分复制到内存,跳转到内存中运行; 接下来枚举本地设备进行初始化,检查硬件是否损坏; 之后在内存中建立中断表和中断服程序,从0x00000~0x003ff的1KB空间构建中断表,中断表有256个条目,每个条目4字节(CS+IP寄存器), 0x00400~0x004FF的256KBk空间构建BIOSu数据区,其中在0x0e05b的地址加载了8KB大小的和中断表对应的中断服务程序。

当BIOS找到启动区后(设备的0盘0道1扇区,共 512字节,最后两字节为0x55和0xaa,即代表包含GRUB启动程序),将数据复制到 0x7c00起始的内存地址,然后加控制权交给了GRUB

GRUB启动

由于GRUB程序不止512字节,所以会分多次加载。 其中有两个重要的文件,第一个是boot.imgboot.img会被GRUB程序写到硬盘的启动区,同时在文件中的第一个位置 写入core.img占用的第一个扇区的区号; 第二个文件是core.imgcore.img中嵌入了足够多的功能, 可以识别硬盘文件系统 、访问/boot/grub目录、加载启动菜单等

详解vmlinuz文件结构

linux_vmlinuz

第十五讲 Linux初始化(下)

linux_start_kernel

  1. GRUB 加载 vmlinuz 文件之后,会把控制权交给 vmlinuz 文件的 setup.bin 的部分中 _start,它会设置好栈,清空 bss,设置好 setup_header 结构,调用 16 位 main 切换到保护模式,最后跳转到 1MB 处的 vmlinux.bin 文件中。

  2. 从 vmlinux.bin 文件中 startup32、startup64 函数开始建立新的全局段描述符表和 MMU 页表,切换到长模式下解压 vmlinux.bin.gz。释放出 vmlinux 文件之后,由解析 elf 格式的函数进行解析,释放 vmlinux 中的代码段和数据段到指定的内存。然后调用其中的 startup_64 函数,在这个函数的最后调用 Linux 内核的第一个 C 函数。

  3. Linux 内核第一个 C 函数重新设置 MMU 页表,随后便调用了最有名的 start_kernel 函数, start_kernel 函数中调用了大多数 Linux 内核功能性初始化函数,在最后调用 rest_init 函数建立了两个内核线程,在其中的 kernel_init 线程建立了第一个用户态进程。

第十六讲 划分土地(上):如何划分和组织内存

由于分段模式难以映射虚拟地址空间,我们使用分页模式管理内存,每页大小为4KB

如何表示一个页

memory_page_view

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
//物理地址和标志  
typedef struct s_PHYADRFLGS
{
    u64_t paf_alloc:1;     //分配位
    u64_t paf_shared:1;    //共享位
    u64_t paf_swap:1;      //交换位
    u64_t paf_cache:1;     //缓存位
    u64_t paf_kmap:1;      //映射位
    u64_t paf_lock:1;      //锁定位
    u64_t paf_dirty:1;     //脏位
    u64_t paf_busy:1;      //忙位
    u64_t paf_rv2:4;       //保留位
    u64_t paf_padrs:52;    //页物理地址位
}__attribute__((packed)) phyadrflgs_t;

页的物理地址是4KB(0x1000=2**12)对齐的,所以低12位可用作其他标志位

内存区

memory_partition

将物理内存分为三个区: 硬件区、内核区和应用区

硬件区

硬件区占用地址区间为 0~32MB,用于一些不依赖 CPU 直接和内存交换数据的硬件,如 DMA

内核区

用于内核

应用区

用于用户态程序

按需分配,应用用到一个页,就分配一个页,如果访问到没有和物理内存页建立映射关系的虚拟内存页, CPU 会产生缺页中断,操作系统会非配一个物理页,并和虚拟也建好映射关系

组织内存页

 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

typedef struct s_BAFHLST
{
    spinlock_t af_lock;    //保护自身结构的自旋锁
    u32_t af_stus;         //状态 
    uint_t af_oder;        //页面数的位移量
    uint_t af_oderpnr;     //oder对应的页面数比如 oder为2那就是1<<2=4
    uint_t af_fobjnr;      //多少个空闲msadsc_t结构,即空闲页面
    uint_t af_mobjnr;      //此结构的msadsc_t结构总数,即此结构总页面
    uint_t af_alcindx;     //此结构的分配计数
    uint_t af_freindx;     //此结构的释放计数
    list_h_t af_frelst;    //挂载此结构的空闲msadsc_t结构
    list_h_t af_alclst;    //挂载此结构已经分配的msadsc_t结构
}bafhlst_t;


#define MDIVMER_ARR_LMAX 52
typedef struct s_MEMDIVMER
{
    spinlock_t dm_lock;      //保护自身结构的自旋锁
    u32_t dm_stus;           //状态
    uint_t dm_divnr;         //内存分配次数
    uint_t dm_mernr;         //内存合并次数
    bafhlst_t dm_mdmlielst[MDIVMER_ARR_LMAX];//bafhlst_t结构数组
    bafhlst_t dm_onemsalst;  //单个的bafhlst_t结构
}memdivmer_t;

dm_mdmlielst第 n个元素挂载 2 ** n 个 物理地址连续的msadsc_t 结构,

memory_part

第十七讲 划分土地(中):如何实现内存页面初始化

内存页结构初始化

内存区结构构初始化

处理内存占用

合并内存页到内存区

虚实地址映射

第十八讲 划分土地(下):如何实现内存页的分配和释放

内存页的分配

比如现在我们要分配一个页面,这个算法将执行如下步骤:

  1. 根据一个页面的请求,会返回 m_mdmlielst 数组中的第 0 个 bafhlst_t 结构。
  2. 如果第 0 个 bafhlst_t 结构中有 msadsc_t 结构就直接返回,若没有 msadsc_t 结构,就会继续查找 m_mdmlielst 数组中的第 1 个 bafhlst_t 结构。
  3. 如果第 1 个 bafhlst_t 结构中也没有 msadsc_t 结构,就会继续查找 m_mdmlielst 数组中的第 2 个 bafhlst_t 结构。
  4. 如果第 2 个 bafhlst_t 结构中有 msadsc_t 结构,记住第 2 个 bafhlst_t 结构中对应是 4 个连续的 msadsc_t 结构。这时让这 4 个连续的 msadsc_t 结构从第 2 个 bafhlst_t 结构中脱离。
  5. 把这 4 个连续的 msadsc_t 结构,对半分割成 2 个双 msadsc_t 结构,把其中一个双 msadsc_t 结构挂载到第 1 个 bafhlst_t 结构中。
  6. 把剩下一个双 msadsc_t 结构,继续对半分割成两个单 msadsc_t 结构,把其中一个单 msadsc_t 结构挂载到第 0 个 bafhlst_t 结构中,剩下一个单 msadsc_t 结构返回给请求者,完成内存分配。

memory_divide

内存页的释放

比如现在我们要释放一个页面,这个算法将执行如下步骤。

  1. 释放一个页面,会返回 m_mdmlielst 数组中的第 0 个 bafhlst_t 结构。
  2. 设置这个页面对应的 msadsc_t 结构的相关信息,表示已经执行了释放操作。
  3. 开始查看第 0 个 bafhlst_t 结构中有没有空闲的 msadsc_t,并且它和要释放的 msadsc_t 对应的物理地址是连续的。没有则把这个释放的 msadsc_t 挂载第 0 个 bafhlst_t 结构中,算法结束,否则进入下一步。
  4. 把第 0 个 bafhlst_t 结构中的 msadsc_t 结构拿出来与释放的 msadsc_t 结构,合并成 2 个连续且更大的 msadsc_t。
  5. 继续查看第 1 个 bafhlst_t 结构中有没有空闲的 msadsc_t,而且这个空闲 msadsc_t 要和上一步合并的 2 个 msadsc_t 对应的物理地址是连续的。没有则把这个合并的 2 个 msadsc_t 挂载第 1 个 bafhlst_t 结构中,算法结束,否则进入下一步。
  6. 把第 1 个 bafhlst_t 结构中的 2 个连续的 msadsc_t 结构,还有合并的 2 个地址连续的 msadsc_t 结构拿出来,合并成 4 个连续且更大的 msadsc_t 结构。
  7. 继续查看第 2 个 bafhlst_t 结构,有没有空闲的 msadsc_t 结构,并且它要和上一步合并的 4 个 msadsc_t 结构对应的物理地址是连续的。没有则把这个合并的 4 个 msadsc_t 挂载第 2 个 bafhlst_t 结构中,算法结束。

memory_recollect

参考