Pwn进你的心
0%

HIT-OSLab6

Posted on In 12k 11 mins.

HIT-OSLab6

实验目的：

  • 深入理解操作系统的段、页式内存管理，深入理解段表、页表、逻辑地址、线性地址、物理地址等概念
  • 实现段、页式内存管理的地址映射过程
  • 编程实现段、页式内存管理上的内存共享，从而深入理解操作系统的内存管理

实验内容：

  • 用 Bochs 调试工具跟踪 Linux-0.11 的地址翻译(地址映射)过程，了解 IA-32(Intel Architecture 32-bit) 的CPU架构下的地址翻译
  • 在 Linux-0.11 中实现 Linux-0.11 的内存管理机制，具体来说就是实现如下3个系统调用：
    • sys_shmget：获取一个共享内存块
    • sys_shmat：映射一个共享内存块
  • 在 Ubuntu 上编写多进程的生产者-消费者程序，用共享内存做缓冲区（上一个实验是用文件做缓冲区）
  • 在上一个实验（信号量的实现和在 pc.c 程序上的应用）的基础上，为 Linux-0.11 增加共享内存功能，并将生产者-消费者程序移植到 Linux-0.11

实验过程

本实验基于上个实验，因此需要保存上个实验的代码

逻辑地址，虚拟地址，线性地址，物理地址是计算机内存管理中的重要概念：

  • 逻辑地址：
    • 逻辑地址是程序使用的地址
    • 编译器编译程序时，会为程序生成代码段和数据段，然后将所有代码放到代码段中，将所有数据放到数据段中，最后程序中的每句代码和每条数据都会有自己的逻辑地址
  • 虚拟地址：
    • 虚拟地址是操作系统为每个进程分配的地址空间，保证了进程之间的隔离和安全性
  • 线性地址：
    • 由虚拟地址通过 “分段” / “分页” 机制转换而来的地址
  • 物理地址：
    • 物理地址是指内存中的实际地址，它是硬件访问的地址
    • 如果 CPU 没有分页机制，那么线性地址等于物理地址
    • 如果 CPU 有分页机制，那么线性地址必须通过转换才能变成物理地址

逻辑地址，虚拟地址，线性地址，物理地址之间的关系是：

  • 在程序编写时，汇编指令使用的地址为逻辑地址（编译器为各个符号分配的地址）
  • 当程序被加载到内存中时，操作系统会将逻辑地址转化为虚拟地址
  • 在 x86 架构中：
    • 虚拟地址通过段选择器和段描述符转化为线性地址
    • 线性地址通过页表转化为物理地址

实验要求跟踪调试 Linux-0.11 的地址映射过程，测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int i = 0x12345678;

int main(void)
{
    printf("LQD The logical/virtual address of i is 0x%08x", &i);
    fflush(stdout);

    while (i);

    return 0;
}
  • 运行后程序死循环

我们的目标就是调试分析变量 i 的物理地址，修改该地址使程序停止死循环：

  • 程序运行之后输出的 0x3004 就是变量 i 的虚拟地址

线性地址由段选择器和段描述符计算而来，因此我们需要先查找到段描述符

进程的段描述符记录在该进程的 LDT 表中，而 LDT 表则记录在 GDT 表中（LDTR 寄存器记录 LDT 表存放在 GDT 表的位置，GDTR 寄存器则记录有 GDT 表的物理地址）

用 sreg 命令可以显示所有寄存器的信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<bochs:3> sreg
es:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=1
	Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
cs:0x000f, dh=0x10c0fb00, dl=0x00000002, valid=1
	Code segment, base=0x10000000, limit=0x00002fff, Execute/Read, Non-Conforming, Accessed, 32-bit
ss:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=1
	Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
ds:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=3
	Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
fs:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=1
	Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
gs:0x0017, dh=0x10c0f300, dl=0x00003fff, valid=1
	Data segment, base=0x10000000, limit=0x03ffffff, Read/Write, Accessed
ldtr:0x0068, dh=0x000082fe, dl=0x92d00068, valid=1
tr:0x0060, dh=0x00008bfe, dl=0x92e80068, valid=1
gdtr:base=0x0000000000005cb8, limit=0x7ff
idtr:base=0x00000000000054b8, limit=0x7ff
  • GDTR 寄存器中的值为 0x5cb8
  • LDTR 寄存器中的值为 0x0068
  • DS 寄存器中的值为 0x0017（0b000000000010111，索引值为 0b10）

用 xp 命令可以打印指定内存的数据：

  • 查看 GDT 表信息，LDT 表的物理地址为 0xfe92d0
1
2
3
4
<bochs:5> xp /8w 0x00005cb8+0x68
[bochs]:
0x0000000000005d20 <bogus+       0>:	0x92d00068	0x000082fe	0xb2e80068	0x000089f8
0x0000000000005d30 <bogus+      16>:	0xb2d00068	0x000082f8	0x00000000	0x00000000
  • 查看对应 LDT 表信息，DS 段的索引为 0x2，对应 0x00003fff 0x10c0f300
1
2
3
4
<bochs:6> xp /8w 0xfe92d0
[bochs]:
0x0000000000fe92d0 <bogus+       0>:	0x00000000	0x00000000	0x00000002	0x10c0fb00
0x0000000000fe92e0 <bogus+      16>:	0x00003fff	0x10c0f300	0x00000000	0x00fea000

段描述符的结构如下：

  • 段基址由3部分组合而成：[0,8)，[24,32)，[48,64)
1
2
bin(0x00003fff10c0f300) =>
0b[0000000000000000]0011111111111111[00010000]1100000011110011[00000000]
  • 计算得基地址为 0x10000000
  • 因此线性地址为 0x10003004
1
2
In [1]: hex(0b00010000000000000000000000000000)
Out[1]: '0x10000000'

用 calc 命令验证线性地址是否正确：

1
2
<bochs:7> calc ds:0x3004
0x10003004 268447748

线性地址的结构如下：

1
2
bin(0x10003004) =>
0b[1000000][0000000011][000000000100]
  • 0-11：页内偏移 - 4
  • 12-21：页表索引 - 3
  • 22-31：页目录索引 - 64（二级页表索引）

在 IA-32(英特尔的32位CPU架构) 下，页目录表的位置由 CR3 寄存器指引，用 creg 命令可以看到：

1
2
3
4
5
6
7
8
9
<bochs:2> creg
CR0=0x8000001b: PG cd nw ac wp ne ET TS em MP PE
CR2=page fault laddr=0x0000000010002fb0
CR3=0x000000000000
    PCD=page-level cache disable=0
    PWT=page-level write-through=0
CR4=0x00000000: cet pke smap smep osxsave pcid fsgsbase smx vmx osxmmexcpt umip osfxsr pce pge mce pae pse de tsd pvi vme
CR8: 0x0
EFER=0x00000000: ffxsr nxe lma lme sce
  • 页目录表所在物理地址为 0x0
  • 页目录表和页表中的内容很简单，是1024个32位数，这32位中前20位是物理页框号，后面是一些属性信息（最重要的是最后一位P）
1
2
3
4
5
<bochs:4> xp /8w 0+64*4
[bochs]:
0x0000000000000100 <bogus+       0>:	0x00fa6027	0x00000000	0x00000000	0x00000000
0x0000000000000110 <bogus+      16>:	0x00000000	0x00000000	0x00000000	0x00000000
0x0000000000000120 <bogus+      32>:	0x00000000	0x00000000	0x00000000	0x00000000
  • 页表所在的物理页框号为 0x00fa6，即页表在物理内存为 0x00fa6000 处
1
2
3
4
<bochs:5> xp /8w 0x00fa6000 + 3*4
[bochs]:
0x0000000000fa600c <bogus+       0>:	0x00f99067	0x00000000	0x00000000	0x00000000
0x0000000000fa601c <bogus+      16>:	0x00000000	0x00000000	0x00000000	0x00000000
  • 物理页所在的物理页框号为 0x00f99，即物理页在物理内存为 0x00f99000 处
  • 因此变量 i 的物理地址为 0x00f99004

用 page 命令验证物理地址是否正确：

1
2
3
4
<bochs:6> page 0x10003004
 PDE: 0x0000000000fa6027    ps         A pcd pwt U W P
 PTE: 0x0000000000f99067       g pat D A pcd pwt U W P
linear page 0x0000000010003000 maps to physical page 0x000000f99000

打印该地址的数据即可发现 0x12345678：

1
2
3
<bochs:8> xp /w 0x00f99004
[bochs]:
0x0000000000f99004 <bogus+       0>:	0x12345678

最后使用 setpmem 命令修改内存即可：

1
2
3
4
<bochs:10> setpmem 0x00f99004 4 0
<bochs:11> xp /w 0x00f99004
[bochs]:
0x0000000000f99004 <bogus+       0>:	0x00000000
  • 程序成功退出

Linux 和 Unix 系统中，共享内存（Shared Memory）是一种在多进程环境下实现进程间通信的技术，它允许多个进程同时访问同一块内存区域，从而实现数据的共享和通信

在为 linux-0.11 编写共享内存代码前，我们需要先分析一下 linux-0.11 对页面的管理机制

1
2
3
#define PAGING_MEMORY (15*1024*1024)
#define PAGING_PAGES (PAGING_MEMORY>>12)
static unsigned char mem_map [ PAGING_PAGES ] = {0,};
  • mem_map 是一个全局数组，在 Linux 0.11 中用于存储物理内存的映射
  • 其索引代表线性地址，每个元素代表一个物理页框

在 Linux-0.11 中，物理内存由一系列页框组成，每个页框的大小为 4KB，mem_map 数组存储了所有已经分配的物理页框的地址，当进程需要分配内存时，会从 mem_map 中查找一个空闲的页框，将其分配给进程，并将该页框的地址返回给进程

初始化 mem_map 数组的函数为 mem_init，在 swapper 进程中会调用一次：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MAP_NR(addr) (((addr)-LOW_MEM)>>12)
#define USED 100

void mem_init(long start_mem, long end_mem)
{
	int i;

	HIGH_MEMORY = end_mem;
	for (i=0 ; i<PAGING_PAGES ; i++)
		mem_map[i] = USED;
	i = MAP_NR(start_mem);
	end_mem -= start_mem;
	end_mem >>= 12;
	while (end_mem-->0)
		mem_map[i++]=0;
}

空闲页面分配的函数 get_free_page 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define LOW_MEM 0x100000
unsigned long get_free_page(void) /* 获取一个空闲页 */
{
register unsigned long __res asm("ax");

__asm__("std ; repne ; scasb\n\t" /* 查找一个末尾为"\0"的page,记录在edi中 */
	"jne 1f\n\t"		   /* 如果scasb指令返回非零值,说明页框已经被占用 */
	"movb $1,1(%%edi)\n\t"	/* [edi+1]=1,对应页面设置为'1' */
	"sall $12,%%ecx\n\t"	
	"addl %2,%%ecx\n\t"
	"movl %%ecx,%%edx\n\t"
	"movl $1024,%%ecx\n\t"
	"leal 4092(%%edx),%%edi\n\t"
	"rep ; stosl\n\t"
	"movl %%edx,%%eax\n"
	"1:"
	:"=a" (__res)
	:"0" (0),"i" (LOW_MEM),"c" (PAGING_PAGES), /* 设置i为LOW_MEM(从LOW_MEM开始计数) */
	"D" (mem_map+PAGING_PAGES-1)
	);
return __res;
}
  • repne scasb 用于将寄存器的内容与内存中的数据进行比较（一直重复直到 edi 末尾为 “\0”）
  • 核心操作就是遍历一遍 mem_map，返回合适的空闲页面

释放已分配页面的函数 get_free_page 代码如下：

1
2
3
4
5
6
7
8
9
10
11
void free_page(unsigned long addr)
{
	if (addr < LOW_MEM) return;
	if (addr >= HIGH_MEMORY)
		panic("trying to free nonexistent page");
	addr -= LOW_MEM;
	addr >>= 12;
	if (mem_map[addr]--) return;
	mem_map[addr]=0;
	panic("trying to free free page");
}
  • 将对应的 mem_map[addr] 末尾置为 “\x00”

函数 put_page 用于将线性地址与物理页进行映射，其实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
unsigned long put_page(unsigned long page,unsigned long address)
{
	unsigned long tmp, *page_table;

/* NOTE !!! This uses the fact that _pg_dir=0 */

	if (page < LOW_MEM || page >= HIGH_MEMORY)
		printk("Trying to put page %p at %p\n",page,address);
	if (mem_map[(page-LOW_MEM)>>12] != 1)
		printk("mem_map disagrees with %p at %p\n",page,address);
	page_table = (unsigned long *) ((address>>20) & 0xffc);
	if ((*page_table)&1)
		page_table = (unsigned long *) (0xfffff000 & *page_table);
	else {
		if (!(tmp=get_free_page()))
			return 0;
		*page_table = tmp|7;
		page_table = (unsigned long *) tmp;
	}
	page_table[(address>>12) & 0x3ff] = page | 7;
/* no need for invalidate */
	return page;
}

本实验要求我们实现共享内存，首先我们需要添加共享内存的系统调用号：（在 /include/unistd.h 中）

1
2
#define __NR_shmget		76
#define __NR_shmat 		77
  • 需要注意的是：这里同时需要修改 hdc-0.11.img 中的 hdc/usr/include/unistd.h 文件，如果想在虚拟机中使用 gcc 编译的话，会导入虚拟机 hdc/usr/include/ 中的文件为头文件

接着修改系统调用号的总数：（在 /kernel/system_call.s 中）

1
nr_system_calls = 78

最后添加新的系统调用定义：（在 /include/linux/sys.h 中）

1
2
3
4
extern int sys_shmget();
extern void *sys_shmat();

fn_ptr sys_call_table[] = {......, sys_shmget, sys_shmat};

头文件以及宏定义：（在 /kernel 中新建文件 shm.c）

1
2
3
4
5
6
7
8
#include <asm/segment.h>
#include <linux/kernel.h>
#include <unistd.h>
#include <string.h>
#include <linux/sched.h>

#define SHM_COUNT 20
#define SHM_NAME_SIZE 20

核心结构体 struct_shm_tables：

1
2
3
4
5
struct struct_shm_tables
{
	char name[SHM_NAME_SIZE];
	long addr;
} shm_tables[SHM_COUNT];

基础字符串函数：

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
int strcmp_shm(char* name,char* tmp){
	int i;
	for(i = 0; i<20; i++){
		if(name[i] != tmp[i]) 
            return 0;
        if(tmp[i] =='\0' && name[i] == '\0') break;
	}
	return 1;
}

int strcpy_shm(char* name,char* tmp){
	int i;
	for(i = 0; i<20; i++){
		name[i] = tmp[i];
        if(tmp[i] =='\0') break;
	}
    return i;
}

int find_shm_location(char *name)
{
	int i;
	for (i = 0; i < SHM_COUNT; i++){
		if (!strcmp_shm(name, shm_tables[i].name)){
			return i;
		}
	}
	return -1;
}

系统调用 sys_shmget：获取一片共享内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int sys_shmget(char *name)
{
	int i, shmid;
	char tmp[SHM_NAME_SIZE];
	for (i = 0; i < SHM_NAME_SIZE; i++){
		tmp[i] = get_fs_byte(name + i);
		if (tmp[i] == '\0')
			break;
	}
	shmid = find_shm_location(tmp);
	if (shmid != -1){
		return shmid;
	}
	for (i = 0; i < SHM_COUNT; i++){
		if (shm_tables[i].name[0] == "\0"){
			strcpy_shm(shm_tables[i].name, tmp);
			shm_tables[i].addr = get_free_page(); /* 获取一个空闲的页帧 */
			return i;
		}
	}
	printk("SHM Number limited!\n");
	return -1;
}

系统调用 sys_shmat：映射一片共享内存

1
2
3
4
5
6
7
8
9
void *sys_shmat(int shmid)
{
	if (shm_tables[shmid].name[0] == "\0"){
		printk("SHM not exists!\n");
		return -1;
	}
	put_page(shm_tables[shmid].addr, current->brk + current->start_code); /* 创建页表,建立起虚拟地址到物理地址的映射关系 */
	return (void *)current->brk;
}

最后修改 makefile：

1
2
3
4
5
6
OBJS  = sched.o system_call.o traps.o asm.o fork.o \
	panic.o printk.o vsprintf.o sys.o exit.o \
	signal.o mktime.o sem.o shm.o
	
sem.s sem.o: sem.c ../include/linux/kernel.h ../include/unistd.h
shm.s shm.o: shm.c ../include/linux/kernel.h ../include/unistd.h

接下来我们需要修改上一个实验的生产者-消费者程序，并用共享内存做缓冲区：

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
#define   __LIBRARY__
#include <unistd.h>
#include <sys/types.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>

_syscall2(int,sem_open,const char *,name,unsigned int,value);
_syscall1(int,sem_wait,int,sem);
_syscall1(int,sem_post,int,sem);
_syscall1(int,sem_unlink,const char *,name);

_syscall1(int,shmget,char*,name);
_syscall1(int,shmat,int,shmid);

const int consumerNum = 3;
const int itemNum = 6;
const int bufSize = 10;
int buf_in = 0,buf_out = 0;

int main()
{
    int sem_empty, sem_full, sem_mutex;
    int *buffer;
    int shmid;
    int stat;
    pid_t p;
    int i,j,k,fd;

    if((sem_empty = sem_open("empty",1)) < 0){
        perror("empty error!\n");
        return -1;
    }

    if((sem_full = sem_open("full",0)) < 0){
        perror("full error!\n");
        return -1;
    }

    if((sem_mutex = sem_open("mutex",10)) < 0){
        perror("mutex error!\n");
        return -1;
    }

    shmid = shmget("buffer");

    if(!(p = fork())){
        printf("A(%d) create\n",0);
        buffer = (int *)shmat(shmid);
        for(i = 0; i < itemNum; i++){
            sem_wait(sem_empty);
            sem_wait(sem_mutex);

            printf("A(%d) >> buf_in:%d\n",0,buf_in);
            buffer[0] = buf_in;
            buf_in = (buf_in+1) % bufSize;

            sem_post(sem_mutex);
            sem_post(sem_full);
        }
        printf("A(%d) done\n",0);
        return 0;
    }
    else if(p < 0){
        perror("fork error!\n");
        return -1;
    }

    for(j = 0; j < consumerNum; j++){
        if(!(p = fork())){
            printf("B(%d) create\n",j);
            buffer = (int *)shmat(shmid);
            for(k = 0; k < itemNum/consumerNum; k++){
                sem_wait(sem_full);
                sem_wait(sem_mutex);

                buf_out = buffer[0];
                printf("B(%d) >> buf_out:%d\n",j,buf_out);

                buf_out = (buf_out + 1) % bufSize;
                buffer[0] = buf_out;

                sem_post(sem_mutex);
                sem_post(sem_empty);

            }
            printf("B(%d) done\n",j);
            return 0;
        }
        else if(p < 0){
            perror("fork error!\n");
            return -1;
        }
    }

    while ((wait(&stat)) > 0); 
    sem_unlink("empty");
    sem_unlink("full");
    sem_unlink("mutex");

    puts("all done");
    return 0;
}

这里有一个点需要注意，由于共享页面同时存在于两个进程中，因此会在 do_exit 中被释放两次

为了不触发内核报错，这里需要修改 free_page 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void free_page(unsigned long addr)
{
	if (addr < LOW_MEM) return;
	if (addr >= HIGH_MEMORY)
		panic("trying to free nonexistent page");
	addr -= LOW_MEM;
	addr >>= 12;

	mem_map[addr] = mem_map[addr] & ~(1) ; 

	/*
	if (mem_map[addr]--) return;
	mem_map[addr]=0;
	panic("trying to free free page");
	*/
}

最终的效果如下：