L1nxy's Blog

This is a simple blog about tech and life

0%

MIT 6.828 Lab1

MIT 6.828 Lab1

Environment Configuration

Arch

1
sudo pacman -S riscv64-linux-gnu-binutils riscv64-linux-gnu-gcc riscv64-linux-gnu-gdb qemu-arch-extra

Mac

1
2
$ brew tap riscv/riscv
$ brew install riscv-tools

WSL

I DO NOT recommend you use WSL to write lab,because wsl have many bugs,and hard to use. when bug come, i must reboot my win10 and reset network.

If you still want to use wsl, try to Arch WSL.

Get the code and Test

1
git clone git://github.com/mit-pdos/xv6-riscv-fall19.git

Enter the xv6-riscv-fall19, if you have full toolchain, run make and make qemu and run qemu with xv6 image.

Grade

There have a grade program that can test you code and make grade, the name of grade program is grade-lab-$(LAB) , for example , we should use ./grade-lab-util in this lab1.

Write Lab1

sleep

Implement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. (A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip.) Your solution should be in the file user/sleep.c.

Solution:

just write it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[])
{
if(argc < 1)
{
fprintf(2,"Usage: sleep x second\n");
exit(1);
}
int sec = atoi(argv[1]);
sleep(sec);
exit(0);
}

uptime(optional)

1
2
3
4
5
6
7
8
9
10
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[])
{
int t = uptime();
printf("%d\n",t);
exit(0);
}

pingpong

Write a program that uses UNIX system calls to ping-pong a byte between two processes over a pair of pipes, one for each direction. The parent sends by writing a byte to parent_fd[1] and the child receives it by reading from parent_fd[0]. After receiving a byte from parent, the child responds with its own byte by writing to child_fd[1], which the parent then reads. Your solution should be in the file user/pingpong.c.

Solution:

learn to use pipe and 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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int parent_fd[2];
int child_fd[2];
char buf[256];
int main()
{
pipe(parent_fd);
pipe(child_fd);
if(fork() == 0)
{
close(0);
close(parent_fd[1]);
int n = read(parent_fd[0],buf,sizeof buf);
buf[n]='\0';
int pid = getpid();
printf("%d: received %s\n",pid,buf);
close(child_fd[0]);
write(child_fd[1],"pong",5);
exit(0);
}
else
{
close(parent_fd[0]);
write(parent_fd[1],"ping",5);

int n = read(child_fd[0],buf,sizeof buf);
buf[n] = '\0';
int pid = getpid();
printf("%d: received %s\n",pid,buf);
exit(0);
}
}

primes

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

Solution:

this problem is hard for me, i can not use gdb in OSX, because gdb installation is too complicate in OSX, and i am too lazy.

My code work with a bug, but it stop at number 17,and cannot fork more process.

I find a paper about use pipe and fork to generate primes, and it’s also just generate number 17 and stop work.

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

void prime_aux(int fd)
{
int pfd[2], num;
int i;
top:
while (read(fd, &num, sizeof num) != 4)
;
printf("prime %d\n", num);

pipe(pfd);
int id;
id = fork();
if (id < 0)
{
exit(0);
}
if (id == 0)
{
close(fd);
close(pfd[1]);
fd = pfd[0];
goto top;
}
close(pfd[0]);
while (1)
{
if(read(fd, &i, sizeof i) != sizeof i)
exit(0);
if (i % num)
{
if(write(pfd[1], &i, sizeof i) !=sizeof i)
exit(0);
}
}
}
int main(void)
{
int p[2];
pipe(p);
if (fork() == 0)
{
close(p[0]);
for (int i = 2; i < 35; i++)
{
if (write(p[1], &i, sizeof i) != 4)
{
printf("write error\n");
exit(0);
}
}
}
close(p[1]);
prime_aux(p[0]);

exit(0);
}

find

Write a simple version of the UNIX find program: find all the files in a directory tree whose name matches a string. Your solution should be in the file user/find.c.

Solution:

Just read ls.c and read directions. and you can copy some code about regex matching to complete the optional question, like my code.

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
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/fs.h"
#include "user/user.h"
// Regexp matcher from Kernighan & Pike,
// The Practice of Programming, Chapter 9.

int matchhere(char*, char*);
int matchstar(int, char*, char*);

int
match(char *re, char *text)
{
if(re[0] == '^')
return matchhere(re+1, text);
do{ // must look at empty string
if(matchhere(re, text))
return 1;
}while(*text++ != '\0');
return 0;
}

// matchhere: search for re at beginning of text
int matchhere(char *re, char *text)
{
if(re[0] == '\0')
return 1;
if(re[1] == '*')
return matchstar(re[0], re+2, text);
if(re[0] == '$' && re[1] == '\0')
return *text == '\0';
if(*text!='\0' && (re[0]=='.' || re[0]==*text))
return matchhere(re+1, text+1);
return 0;
}

// matchstar: search for c*re at beginning of text
int matchstar(int c, char *re, char *text)
{
do{ // a * matches zero or more instances
if(matchhere(re, text))
return 1;
}while(*text!='\0' && (*text++==c || c=='.'));
return 0;
}

char *fmtname(char *path)
{
static char buf[DIRSIZ + 1];
char *p;

// Find first character after last slash.
for (p = path + strlen(path); p >= path && *p != '/'; p--)
;
p++;

// Return blank-padded name.
if (strlen(p) >= DIRSIZ)
return p;
memmove(buf, p, strlen(p));
buf[strlen(p)] = '\0';
return buf;
}

void find(char *path, const char *file_name)
{
char buf[512], *p;
int fd;
struct dirent de;
struct stat st;
if ((fd = open(path, 0)) < 0)
{
fprintf(2, "find: cannot open %s\n", path);
close(fd);
return;
}

if (fstat(fd, &st) < 0)
{
fprintf(2, "find : cannot stat %s\n", path);
close(fd);
return;
}

switch (st.type)
{
case T_FILE:
if (strcmp(fmtname(path), file_name) == 0)
{
printf("%s\n", path);
}
break;
case T_DIR:
if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf)
{
printf("find : path too long\n");
break;
}

strcpy(buf, path);
p = buf + strlen(buf);
*p++ = '/';
while (read(fd, &de, sizeof de) == sizeof de)
{
if (de.inum == 0)
{
continue;
}
memmove(p, de.name, DIRSIZ);
p[DIRSIZ] = 0;
if (stat(buf, &st) < 0)
{
printf("find: cannot stat : %s\n", buf);
continue;
}
if (strcmp(fmtname(buf), file_name) == 0)
{
printf("%s\n", buf);
continue;
}
else if (st.type == T_DIR
&& strcmp(de.name, ".") != 0 && strcmp(de.name, "..") != 0)
{
find(buf, file_name);
}
//printf("%s and %s cmp result %d\n",fmtname(buf),file_name,strcmp(fmtname(buf),file_name));
}
break;
}
}
int main(int argc, char *argv[])
{
if (argc < 2)
{
printf("need two avgvs\n");
exit(0);
}
find(argv[1], argv[2]);
exit(0);
}

xargs

Write a simple version of the UNIX xargs program: read lines from standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

Solution:

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
#include "kernel/param.h"
#include "kernel/fcntl.h"
#include "kernel/types.h"
#include "user/user.h"

char c;
int i = 0;
char buf[256];
int main(int argc, char *argv[])
{
if (argc < 2)
{
fprintf(2, "xargs command need more args\n");
exit(1);
}
int n;
while ((n = read(0, &c, 1)) > 0)
{
if (n == 1 && c != '\n')
{
buf[i++] = c;
continue;
}
if (c == '\n')
{
buf[i] = '\0';
i = 0;
argv[argc] = buf;
argv[argc+1] = 0;
if (fork() == 0)
{
exec(argv[1], argv + 1);
exit(1);
}
else
{
wait(0);
}
buf[i] = '\0';
}
}
exit(1);
}