OS-lab5

OS-lab5

写在前面，往年的上机实验都是60分就给满，去年因为疫情转为线上，实验总分还送了10分。就是说大佬甚至不用申优就能拿99分。今年exam和extra都是按百分比算分，1分的extra得了80相当于0.8。所以不能完全实现，实现一部分骗个样例分也不错。OS上机终于结束，在之后打算再好好理解一下MOS，内存管理，进程管理，文件系统，Shell和管道都有不太清楚的地，感觉OS一路下来每次都跟CO P7一样抽象。

上机

lab5-1

exam

lab5-1这部分涉及到读取外设，不用管文件系统。在完成此部分之前建议学习如何从控制台轮询读取输入，如何关闭控制台。

这次exam还是比较简单，就是读取时钟外设，实现两个函数

  • u_int get_time(u_int *us), 返回秒数，微秒通过指针返回
  • void usleep(u_int us)，调用此函数实现：读取当前时间，然后休眠至少us微秒。

需要注意返回的都是无符号数，计算休眠时间时先转换成有符号数（因为涉及到减法）：

​ int s = (ys2 - ys1) * 1000000;
​ int uus = yus2 - yus1
​ s + uus 即为休眠时间

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
u_int get_time(u_int *us)
{
  int temp = 0;
  u_int rtc = 0x15000000;
  u_int time;
  syscall_write_dev(&temp, rtc, 4);
  syscall_read_dev(&time, rtc + 0x0010, 4);         //读取秒
  syscall_read_dev(us, rtc + 0x0020, 4);            //读取微秒
  return time;
}

void usleep(u_int us)
{
  int temp = 0;
  u_int us1;
  u_int us2;
  u_int s1;
  s1 = get_time(&us1);
  int ys1 = (int)(s1);
  int yus1 = (int)(us1);
  while (1)
  {
    u_int s2 = get_time(&us2);
    int ys2 = (int)(s2);
    int yus2 = (int)(us2);
    int yus = (int)(us);
    int s = (ys2 - ys1) * 1000000;
    int uus = yus2 - yus1 - yus;
    if ((s + uus) >= 0)
    {
      return;
    }
    else
    {

      syscall_yield();
    }
  }
}

extra

实现一个固态硬盘，普通磁盘如果要覆盖写直接写就可以，但固态硬盘需要先擦除再写，频繁擦除会降低硬盘寿命，这也是为什么固态硬盘寿命较短的原因。为保证各个硬盘块擦除均匀，我们要实现分配系统。（具体题面忘了）,extra只得了80分，没找见bug。

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
int yinshe[32];
int phmap[32];
int phca[32];
char s[520];
int getlogno(int phno)
{
	for (int i = 0; i < 32; i++)
	{
		if (yinshe[i] == phno)
		{

			return i;
		}
	}
}
int fen()
{
	int min = 114514;
	int flag = -1;
	for (int i = 0; i < 32; i++)
	{
		if (phmap[i] == 0 && phca[i] < min)
		{
			min = phca[i];
			flag = i;
		}
	}
	if (min < 5)
	{
		return flag;
	}

	int a = flag;
	flag = -1;
	min = 114514;
	for (int i = 0; i < 32; i++)
	{
		if (phmap[i] == 1 && phca[i] < min)
		{
			min = phca[i];
			flag = i;
		}
	}
	int b = flag;
	void *temp;
	ide_read(0, b, temp, 1);
	ide_write(0, a, temp, 1);
	phmap[a] = 1;
	yinshe[getlogno(b)] = a;
	ide_write(0, b, s, 1);
	phca[b]++;
	phmap[b] = 0;
	return b;
}
void ssd_init()
{
	for (int i = 0; i < 32; i++)
	{
		yinshe[i] = -1;
		phmap[i] = 0;
		phca[i] = 0;
	}
}
int ssd_read(u_int logic_no, void *dst)
{
	if (yinshe[logic_no] == -1)
	{
		return -1;
	}
	else
	{
		ide_read(0, yinshe[logic_no], dst, 1);
		return 0;
	}
}
void ssd_write(u_int logic_no, void *src)
{
	int phno;
	if (yinshe[logic_no] == -1)
	{
		phno = fen();
		yinshe[logic_no] = phno;
		phmap[phno] = 1;
		ide_write(0, phno, src, 1);
	}
	else
	{

		phno = yinshe[logic_no];
		ide_write(0, phno, s, 1);
		phca[phno]++;
		yinshe[logic_no] = -1;
		phmap[phno] = 0;
		phno = fen();
		yinshe[logic_no] = phno;
		phmap[phno] = 1;
		ide_write(0, phno, src, 1);
	}
}
void ssd_erase(u_int logic_no)
{
	if (yinshe[logic_no] == -1)
	{
		return;
	}
	int phno = yinshe[logic_no];
	ide_write(0, phno, s, 1);
	phca[phno]++;
	phmap[phno] = 0;
	yinshe[logic_no] = -1;
}

lab5-2

主要考文件系统，说实话课下需要自己完成的只是冰山一角，一定要在完成后好好理解一下。fs是文件服务进程处理文件操作请求的函数都放在这个目录下，user/lib里的file.c和fd.c是其他进程的用户接口。这次extra甚至考了tools里的format.c（课下一眼没看，课上看源码看了将近一个小时）

exam

file.c中实现的open函数实现打开绝对路径，我们修改实现openat打开某个目录下的相对路径，具体如下，全部对标open，两者几乎一样

就是在walk_path传入当前目录，从这开始找而不是从根目录。

  • file.c 中实现int openat(int dirfd, const char *path, int mode)实现在当前目录（文件操作符为dirfd）下寻找路径为path的文件
  • fsipc.c中实现int fsipc_openat(u_int dir_fileid, const char *path, u_int omode, struct Fd *fd)构建你的struct Fsreq_openat *req
  • fs/serv.c实现void serve_openat(u_int envid, struct Fsreq_openat *rq)并修改serve函数
  • fs/fs.c中实现int file_openat(struct File *dir, char *path, struct File **pfile)和int walk_path_at(struct File *par_dir, char *path, struct File **pdir, struct File **pfile, char *lastelem)

看似很麻烦，但其实大部分就是复制粘贴

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
// file.c
int openat(int dirfd, const char *path, int mode)
{
	struct Fd *dir;
	struct Fd *fd;
	int r;
	if ((r = fd_lookup(dirfd, &dir)) < 0)
	{
		return r;
	}
	struct Filefd *dirfile = (struct Filefd *)dir;
	int fileid = dirfile->f_fileid;                  //找到当前目录的fileid
	try(fd_alloc(&fd));
	try(fsipc_openat(fileid, path, mode, fd));
	char *va;
	struct Filefd *ffd;
	u_int size, fileid1;
	va = fd2data(fd);
	ffd = (struct Filefd *)fd;
	size = ffd->f_file.f_size;
	fileid1 = ffd->f_fileid;
	for (int i = 0; i < size; i += BY2PG)
	{
		try(fsipc_map(fileid1, i, va + i));
	}
	return fd2num(fd);
}

//fsipc.c
int fsipc_openat(u_int dir_fileid, const char *path, u_int omode, struct Fd *fd)
{
	u_int perm;
	struct Fsreq_openat *req;

	req = (struct Fsreq_openat *)fsipcbuf;

	// The path is too long.
	if (strlen(path) >= MAXPATHLEN)
	{
		return -E_BAD_PATH;
	}
	req->dir_fileid = dir_fileid;
	strcpy((char *)req->req_path, path);
	req->req_omode = omode;
	return fsipc(FSREQ_OPENAT, req, fd, &perm);
}

//serv.c
void serve_openat(u_int envid, struct Fsreq_openat *rq)
{

	struct Open *pOpen;
	int r;
	if ((r = open_lookup(envid, rq->dir_fileid, &pOpen)) < 0)      //找到当前目录
	{
		ipc_send(envid, r, 0, 0);
		return;
	}
	struct File *dir = pOpen->o_file;

	struct File *f;
	struct Filefd *ff;
	struct Open *o;

	// Find a file id.
	if ((r = open_alloc(&o)) < 0)
	{
		ipc_send(envid, r, 0, 0);
	}

	// Open the file.
	if ((r = file_openat(dir, rq->req_path, &f)) < 0)
	{
		ipc_send(envid, r, 0, 0);
		return;
	}

	// Save the file pointer.
	o->o_file = f;

	// Fill out the Filefd structure
	ff = (struct Filefd *)o->o_ff;
	ff->f_file = *f;
	ff->f_fileid = o->o_fileid;
	o->o_mode = rq->req_omode;
	ff->f_fd.fd_omode = o->o_mode;
	ff->f_fd.fd_dev_id = devfile.dev_id;

	ipc_send(envid, 0, o->o_ff, PTE_D | PTE_LIBRARY);
}

// fs.c
int walk_path_at(struct File *par_dir, char *path, struct File **pdir, struct File **pfile, char *lastelem){
     char *p;
	char name[MAXNAMELEN];
	struct File *dir, *file;
	int r;

	// start at the root.
	path = skip_slash(path);
	file = par_dir;                                         //最关键一步
	dir = 0;
	name[0] = 0;

	if (pdir) {
		*pdir = 0;
	}

	*pfile = 0;

	// find the target file by name recursively.
	while (*path != '\0') {
		dir = file;
		p = path;

		while (*path != '/' && *path != '\0') {
			path++;
		}

		if (path - p >= MAXNAMELEN) {
			return -E_BAD_PATH;
		}

		memcpy(name, p, path - p);
		name[path - p] = '\0';
		path = skip_slash(path);
		if (dir->f_type != FTYPE_DIR) {
			return -E_NOT_FOUND;
		}

		if ((r = dir_lookup(dir, name, &file)) < 0) {
			if (r == -E_NOT_FOUND && *path == '\0') {
				if (pdir) {
					*pdir = dir;
				}

				if (lastelem) {
					strcpy(lastelem, name);
				}

				*pfile = 0;
			}

			return r;
		}
	}

	if (pdir) {
		*pdir = dir;
	}

	*pfile = file;
	return 0;

}

extra

实现新的一种文件类型，即链接文件，可以看做是Windows的快捷方式，只不过这种文件内容存的是其指向文件的绝对路径，其指向文件可能还是一个链接文件，但保证最终指向一个普通文件

  • 修改format.c
    • 增加void write_symlink(struct File *dirf, const char *path)
    • 修改主函数，增加分支
    • 修改write_directory，增加分支
  • 修改open，实现如果当前文件是链接文件，最终要返回最终指向的普通文件

使用memcpy时一定要注意，目标缓冲区一定要初始化

即char nextpath[1024] = "\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
int open(const char *path, int mode) {
	int r;

	// Step 1: Alloc a new 'Fd' using 'fd_alloc' in fd.c.
	// Hint: return the error code if failed.
	struct Fd *fd;
	/* Exercise 5.9: Your code here. (1/5) */
    try(fd_alloc(&fd));
	// Step 2: Prepare the 'fd' using 'fsipc_open' in fsipc.c.
	/* Exercise 5.9: Your code here. (2/5) */
    try(fsipc_open(path, mode, fd));
	// Step 3: Set 'va' to the address of the page where the 'fd''s data is cached, using
	// 'fd2data'. Set 'size' and 'fileid' correctly with the value in 'fd' as a 'Filefd'.
	char *va;
	struct Filefd *ffd;
	u_int size, fileid;
	/* Exercise 5.9: Your code here. (3/5) */
    va = fd2data(fd);
    ffd = (struct Filefd *)fd;
	size = ffd->f_file.f_size;
	fileid = ffd->f_fileid;
	// Step 4: Alloc pages and map the file content using 'fsipc_map'.
	for (int i = 0; i < size; i += BY2PG) {
		/* Exercise 5.9: Your code here. (4/5) */
        try(fsipc_map(fileid,i,va + i));
	}

	// Step 5: Return the number of file descriptor using 'fd2num'.
	/* Exercise 5.9: Your code here. (5/5) */
	while(ffd->f_file.f_type == 2){
           char next[1024] = "\0";
	   file_read(fd, next, ffd->f_file.f_size, 0);
	   return open(next, mode);
		}
    return fd2num(fd);
}


void write_symlink(struct File *dirf, const char *path)
{
	struct File *target = create_file(dirf);
	// Your code here: 使用 readlink() 函数读取链接文件指向的路径，将其写入到下一个可用的磁盘块
	char nextlink[1024] = "\0";
	readlink(path, nextlink, 1024);
	memcpy((void *)disk[nextbno].data, nextlink, strlen(nextlink));
	const char *fname = strrchr(path, '/');
	if (fname)
	{
		fname++;
	}
	else
	{
		fname = path;
	}
	// Your code here: 设置链接文件的文件名、大小（指向路径的字符串的长度）、类型属性
	target->f_size = strlen(nextlink);
	strcpy(target->f_name, fname);
	target->f_type = FTYPE_LNK;
	save_block_link(target, 0, next_block(BLOCK_DATA));
}


int main(int argc, char **argv)
{
	static_assert(sizeof(struct File) == BY2FILE);
	init_disk();

	if (argc < 3)
	{
		fprintf(stderr, "Usage: fsformat <img-file> [files or directories]...\n");
		exit(1);
	}

	for (int i = 2; i < argc; i++)
	{
		char *name = argv[i];
		struct stat stat_buf;
		int r = lstat(name, &stat_buf);
		assert(r == 0);
		if (S_ISDIR(stat_buf.st_mode))
		{
			printf("writing directory '%s' recursively into disk\n", name);
			write_directory(&super.s_root, name);
		}
		else if (S_ISREG(stat_buf.st_mode))
		{
			printf("writing regular file '%s' into disk\n", name);
			write_file(&super.s_root, name);
		}
		else if (S_ISLNK(stat_buf.st_mode))                     //增加的分支
		{
			write_symlink(&super.s_root, name);
		}
		else
		{
			fprintf(stderr, "'%s' has illegal file mode %o\n", name, stat_buf.st_mode);
			exit(2);
		}
	}

	flush_bitmap();
	finish_fs(argv[1]);
	return 0;
}



void write_directory(struct File *dirf, char *path)
{
	DIR *dir = opendir(path);
	if (dir == NULL)
	{
		perror("opendir");
		return;
	}
	struct File *pdir = create_file(dirf);
	strncpy(pdir->f_name, basename(path), MAXNAMELEN - 1);
	if (pdir->f_name[MAXNAMELEN - 1] != 0)
	{
		fprintf(stderr, "file name is too long: %s\n", path);
		// File already created, no way back from here.
		exit(1);
	}
	pdir->f_type = FTYPE_DIR;
	for (struct dirent *e; (e = readdir(dir)) != NULL;)
	{
		if (strcmp(e->d_name, ".") != 0 && strcmp(e->d_name, "..") != 0)
		{
			char *buf = malloc(strlen(path) + strlen(e->d_name) + 2);
			sprintf(buf, "%s/%s", path, e->d_name);
			if (e->d_type == DT_DIR)
			{
				write_directory(pdir, buf);
			} 
			else if (e->d_type == DT_LNK)                      //增加的分支
			{
				write_symlink(pdir, buf);
			}
			else
			{
				write_file(pdir, buf);
			}
			free(buf);
		}
	}
	closedir(dir);
}

实验报告

一、Thinking

Thinking 5.1 如果通过 kseg0 读写设备，那么对于设备的写入会缓存到 Cache 中。这是 一种错误的行为，在实际编写代码的时候这么做会引发不可预知的问题。请思考：这么做 这会引发什么问题？对于不同种类的设备（如我们提到的串口设备和 IDE 磁盘）的操作会 有差异吗？可以从缓存的性质和缓存更新的策略来考虑。

举个例子，比如往控制台写入0123，此时0123会缓存到控制台，此时从控制台读入字符串，就会读到0123。不同类型设备的错误可能不一样。这是因为cache中存储的内容只有被替换时，才会写回到设备。

Thinking 5.2 查找代码中的相关定义，试回答一个磁盘块中最多能存储多少个文件控制 块？一个目录下最多能有多少个文件？我们的文件系统支持的单个文件最大为多大？

每个磁盘块大小为4KB，而每个文件控制块被char f_pad对齐为256B，所以可以存储16个文件控制块

可看做一个磁盘块都用来存储文件磁盘块号，最多有1024个磁盘块，大小为1024 * 4KB = 4MB

一个目录最多有1024个磁盘块，+最多有1024 * 16 = 16384个文件

Thinking 5.3 请思考，在满足磁盘块缓存的设计的前提下，我们实验使用的内核支持的最 大磁盘大小是多少？

DISKMAX为0x40000000，所以满足最大的磁盘大小为1GB

Thinking 5.4 在本实验中，fs/serv.h、user/include/fs.h 等文件中出现了许多宏定义， 试列举你认为较为重要的宏定义，同时进行解释，并描述其主要应用之处。

serv.h

PTE_DIRTY，内存可以看做CPU和disk之间的cache，所以PTE_DIRTY代表物理页所对应的磁盘块内容是否被更改了

fs.h

NDIRECT 10 ，直接索引的数量

NINDIRECT (BY2BLK / 4) 间接索引的数量

MAXFILESIZE (NINDIRECT * BY2BLK) 文件最大大小

BY2FILE 256 文件控制块大小

Thinking 5.5 在 Lab4“系统调用与 fork”的实验中我们实现了极为重要的 fork 函数。那 么 fork 前后的父子进程是否会共享文件描述符和定位指针呢？请在完成上述练习的基础上 编写一个程序进行验证。

会共享，fork时，会把文件操作符复制过去。但是并不共享，相当于父子进程分别打开同一个文件，可以独立修改文件内容。

Thinking 5.6 请解释 File, Fd, Filefd 结构体及其各个域的作用。比如各个结构体会在哪 些过程中被使用，是否对应磁盘上的物理实体还是单纯的内存数据等。说明形式自定，要 求简洁明了，可大致勾勒出文件系统数据结构与物理实体的对应关系与设计框架。

  • Fd当从文件服务进程传回时，其可被强制转换类型，得到文件控制块
  • f_fileid对应着文件服务进程中一个open结构体，得到对应关系
  • File对应的是磁盘上的物理实体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Fd { u_int fd_dev_id;  //设备id
​           u_int fd_offset;  //fd所指向地址
            u_int fd_omode;   //文件操作类型
            };
struct Filefd {
               struct Fd f_fd;      //文件操作符
               u_int f_fileid;      //文件id
               struct File f_file;  //文件控制块
 };
 struct File {
	char f_name[MAXNAMELEN]; // filename
	uint32_t f_size;	 // file size in bytes
	uint32_t f_type;	 // file type
	uint32_t f_direct[NDIRECT];
	uint32_t f_indirect;

	struct File *f_dir; // the pointer to the dir where this file is in, valid only in memory.
	char f_pad[BY2FILE - MAXNAMELEN - (3 + NDIRECT) * 4 - sizeof(void *)];
}



Thinking 5.7 图5.7中有多种不同形式的箭头，请解释这些不同箭头的差别，并思考我们 的操作系统是如何实现对应类型的进程间通信的。

实线箭头为同步消息

虚线箭头为同步返回消息

首先操作系统创建用户进程和文件服务进程，文件服务进程完成初始化可以工作，开始轮询不断接受用户进程的文件请求。用户进程不同操作，通过发送信息到文件服务进程，请求服务，等待文件服务进程完成相应操作并返回结果。

二、实验难点

虚拟地址

外设对应的地址属于kesg1的地址，当用户进程需要读写外设时，需要通过系统调用来完成。内核态访问用户空间的地址会通过当前进程的标识符访问TLB进而得到物理地址。而在之前的lab3-extra中，之所以需要通过用户虚拟地址转换为内核态虚拟地址是因为指令所在的页面权限没有可写权限。并且用户地址范围可能是跨页的，并且可能是缺页的，所以不能通过内核态地址访问。

文件操作

我们可以把内存看做磁盘和CPU之间的cache，是通过将要访问的文件映射到内存中，修改内存，最终修改结果又会返回到磁盘中。处理文件操作是由文件服务进程和用户进程之间的通信完成的，用户进程将需要进行的操作的信息发送到文件服务进程，并将文件映射到用户进程的地址中。如果修改文件内容，对应内存页面会有PTE_DIRTY标志，会把修改写入磁盘。

Fd， FileFd等对应的结构体

在思考题已给出解释

三、实验体会

lab5在代码提示下补全还是很容易的。但文件操作具体的实现却很复杂，从5.9到5.13用户接口的实现，我们仅仅完成很小的一部分。具体过程需要自己看源码理解。在最初拉取分支的时候看到fs目录甚是困惑，管理文件为什么放到了用户态中，其实这符合微内核的思想。但同时也有疑问，是否应该给用户进程这么大的权限。从打开一个文件到更改并保存关闭，这之间各个函数的调用和进程之间的通信非常复杂，需要理解清楚。

OS
#OS #实验报告
OS-lab5
https://etherialize.github.io/2023/05/22/OS-lab5/
作者
HZY
发布于
2023年5月22日
许可协议