Lab: Xv6 and Unix utilities
===
###### tags: `6.1810`
# Setup env
以 mac m1 為例，首先安裝開發者工具
`$ xcode-select --install`
接著安裝 homebrew，package manager
`$ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"`
接著安裝 riscv tool chain
```
$ brew tap riscv/riscv
$ brew install riscv-gnu-toolchain
```
安裝完成後，測試
```shell=
$ riscv64-unknown-elf-gcc --version
riscv64-unknown-elf-gcc (g1ea978e3066-dirty) 12.1.0
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
# Boot xv6
目標是在 qemu 執行 xv6 kernel
首先下載程式碼
```shell
$ git clone git://g.csail.mit.edu/xv6-labs-2022
Cloning into 'xv6-labs-2022'...
...
```
下載後進入 xv6 資料夾
`$ cd xv6-labs-2022`
確認 branch 是否為 util
```
$ git status
On branch util
Your branch is up to date with 'origin/util'.
nothing to commit, working tree clean
```
如果不是的話執行`git branch util`切換到 `util`
執行 qemu 模擬器
```
$ make qemu
riscv64-unknown-elf-gcc -c -o kernel/entry.o kernel/entry.S
riscv64-unknown-elf-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -DSOL_UTIL -MD -mcmodel=medany -ffreestanding -fno-common -nostdlib -mno-relax -I. -fno-stack-protector -fno-pie -no-pie -c -o kernel/start.o kernel/start.c
...
riscv64-unknown-elf-ld -z max-page-size=4096 -N -e main -Ttext 0 -o user/_zombie user/zombie.o user/ulib.o user/usys.o user/printf.o user/umalloc.o
riscv64-unknown-elf-objdump -S user/_zombie > user/zombie.asm
riscv64-unknown-elf-objdump -t user/_zombie | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$/d' > user/zombie.sym
mkfs/mkfs fs.img README user/xargstest.sh user/_cat user/_echo user/_forktest user/_grep user/_init user/_kill user/_ln user/_ls user/_mkdir user/_rm user/_sh user/_stressfs user/_usertests user/_grind user/_wc user/_zombie
nmeta 46 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 1) blocks 954 total 1000
balloc: first 591 blocks have been allocated
balloc: write bitmap block at sector 45
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0
xv6 kernel is booting
hart 2 starting
hart 1 starting
init: starting sh
$
```
進到 xv6 後，執行 ls ，就算完成了。
```
$ ls
. 1 1 1024
.. 1 1 1024
README 2 2 2227
xargstest.sh 2 3 93
cat 2 4 32864
echo 2 5 31720
forktest 2 6 15856
grep 2 7 36240
init 2 8 32216
kill 2 9 31680
ln 2 10 31504
ls 2 11 34808
mkdir 2 12 31736
rm 2 13 31720
sh 2 14 54168
stressfs 2 15 32608
usertests 2 16 178800
grind 2 17 47528
wc 2 18 33816
zombie 2 19 31080
console 3 20 0
```
要離開 qemu 的話，先按 `ctrl+a`，再按 x，就可以離開。
# sleep
撰寫一個呼叫 sys_sleep 的程式
根據提示，先參考 `user/echo.c` 瞭解如何取得 command-line 參數，
```clike=
# user/echo.c
int
main(int argc, char *argv[])
{
int i;
for(i = 1; i < argc; i++){
write(1, argv[i], strlen(argv[i]));
if(i + 1 < argc){
write(1, " ", 1);
} else {
write(1, "\n", 1);
}
}
exit(0);
}
```
`argc` 是參數數量。如果沒有帶入參數的話是1。
`argv` 是一個 array of pointer，指向字串，c 語言的字串為一段連續的記憶體，型態為 `char`，結尾是 `\0`。當把 `char[]` 當作參數傳遞時，`char[]` 與 `char *`是等價的。
於是 sleep.c 可以寫為
```clike=
# sleep.c
int
main(int argc, char *argv[])
{
if (argc != 2) {
printf("Use ./sleep second.\n");
exit(1);
}
}
```
接著透過 [atoi](https://github.com/mit-pdos/xv6-riscv/blob/f5b93ef12f7159f74f80f94729ee4faabe42c360/user/ulib.c#L99) 將參數轉換成 integer.
```clike=
# sleep.c
int
main(int argc, char *argv[])
{
if (argc != 2) {
printf("Use ./sleep second.\n");
exit(1);
}
int n = atoi(argv[1]);
}
```
下一步是呼叫 `sys_sleep`，
參考 [user.h](https://github.com/mit-pdos/xv6-riscv/blob/f5b93ef12f7159f74f80f94729ee4faabe42c360/user/user.h#L23) 可以知道 `sys_sleep` 的 `prototype` 為`int sleep(int);`
```clike=
# sleep.c
int
main(int argc, char *argv[])
{
if (argc != 2) {
printf("Use ./sleep second.\n");
exit(1);
}
int n = atoi(argv[1]);
sleep(n);
exit(0);
}
```
最後增加 `sleep` 到 makefile 就大功告成拉！
執行 qemu 測試
```shell=
$ make qemu
...
init: starting sh
$ sleep 10
(nothing happens for a little while)
$
```
使用自動打分數系統
`make GRADEFLAGS=sleep grade`
# pingpong
學習使用 `pipe`, `fork`
首先建立一個 pipe
```clike=
# pingpong.c
int
main(int argc, char *argv[])
{
int fds[2];
if (pipe(fds) == -1)
exit(1);
}
```
接著呼叫 `fork()`
```clike=
# pingpong.c
int
main(int argc, char *argv[])
{
...
int pid = fork();
if (pid < 0) {
printf("fork() failed\n");
exit(1)
} else if (pid == 0) {
// child
} else {
// parent
}
}
```
parent 先發送一個 byte 給 child， child 接收後回傳一個 byte 給 parent
```clike=
# pingpong.c
int
main(int argc, char *argv[])
{
...
int pid = fork();
char c;
if (pid < 0) {
printf("fork() failed\n");
exit(1)
} else if (pid == 0) {
// child
read(fd[0], &c, sizeof(c));
printf("%d: received ping", getpid());
write(fd[1], &c, sizeof(c));
} else {
// parent
write(fd[1], &c, sizeof(c));
read(fd[0], &c, sizeof(c));
printf("%d: received pong", getpid());
}
exit(0);
}
```
最後增加 pingpong 到 makefile，執行 qemu
```shell=
$ make qemu
...
init: starting sh
$ pingpong
4: received ping
3: received pong
$
```
# primes
閱讀 [Bell Labs and CSP Threads](https://swtch.com/~rsc/thread/)
每一個格子代表一個 process，會過濾 input，將合適的 output 傳遞下去，最左邊需要一個 process 傳遞所有的資料
先建立 parent 及 child ，並做 redirect，沒有用到的 io 先關掉
```clike=
# primes
int main(int argc, char const *argv[])
{
int fds[2];
if (pipe(fds) < 0) {
printf("pipe() failed\n");
exit(1);
}
int pid = fork();
if (pid < 0) {
printf("pid() failed\n");
exit(1);
} else if (pid == 0) {
close(0);
dup(fds[0]);
close(fds[0]);
close(fds[1]);
exit(0);
} else {
close(1);
dup(fds[1]);
close(fds[0]);
close(fds[1]);
for (int i = 2; i <= 35; i++) {
write(1, &i, sizeof(i));
}
close(1);
if (wait(0) < 0) {
fprintf(2, "wait() failed\n");
exit(1);
}
}
exit(0);
}
```
child 第一個接收到的數字 `n` 會當作基準，之後的數字可以被 `n` 整除的話就過濾掉，
以下程式碼 `csp()` 透過 `read()` 判斷是否需要建立新的 `child`，若 `read()`有回傳表示需要，沒有用到的 `pipe` 要先關閉，否則 `read()` 不會回傳，程式不會結束。
```clike=
void csp()
{
int p;
// get number from right side
if (read(0, &p, sizeof(p))) {
printf("prime %d\n", p);
int fds[2];
if (pipe(fds) < 0) {
printf("pipe() failed in csp()\n");
exit(1);
}
int pid;
if ((pid = fork()) < 0) {
printf("fork() failed\n");
exit(1);
} else if (pid == 0) {
close(0);
dup(fds[0]);
close(fds[0]);
close(fds[1]);
csp();
} else {
close(1);
dup(fds[1]);
close(fds[0]);
close(fds[1]);
int n;
while (read(0, &n, sizeof(n))) {
if (n % p)
write(1, &n, sizeof(n));
}
}
}
close(0);
close(1);
wait(0);
}
int main(int argc, char const *argv[])
{
...
} else if (pid == 0) {
close(0);
dup(fds[0]);
close(fds[0]);
close(fds[1]);
csp();
} else {
...
}
```
```clike=
# primes
int fds[2];
if (pipe(fds) < 0) {
printf("pipe() failed\n");
exit(1);
}
int pid = fork();
if (pid < 0) {
printf("pid() failed\n");
exit(1);
} else if (pid == 0) {
// use pseudo code https://swtch.com/~rsc/thread/
close(0);
dup(fds[0]);
close(fds[0]);
close(fds[1]);
csp();
} else {
close(1);
dup(fds[1]);
close(fds[0]);
close(fds[1]);
for (int i = 2; i <= 35; i++) {
write(1, &i, sizeof(i));
}
// close pipe so child process will return from read().
close(1);
if (wait(0) < 0) {
fprintf(2, "wait() failed\n");
exit(1);
}
}
exit(0);
}
```
# find
參考 `user/ls.c` 的架構，
```clike=
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
void
find(char *path)
{
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);
return;
}
if(fstat(fd, &st) < 0){
fprintf(2, "find: cannot stat %s\n", path);
close(fd);
return;
}
switch(st.type){
case T_DEVICE:
case T_FILE:
break;
case T_DIR:
if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
printf("ls: 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;
}
}
break;
}
close(fd);
}
int
main(int argc, char *argv[])
{
if(argc != 3){
printf("Use ./find path file\n");
exit(1);
}
find(argv[1]);
exit(0);
}
```
`find` 需要比對每個檔案名稱，若是名稱相同，印出路徑。
參考 `fmtname()`，`cmpname()` 比對檔案名稱是否相同。
```clike=
void
cmpname(char *path, char *fileName)
{
char *p;
// Find first character after last slash.
for(p=path+strlen(path); p >= path && *p != '/'; p--)
;
p++;
if (strcmp(p, fileName) == 0)
printf("%s\n", path);
}
```
在一開始呼叫 `cmpname`
```diff=
void
find(char *path, char *fileName)
{
char buf[512], *p;
int fd;
struct dirent de;
struct stat st;
+ cmpname(path, fileName);
...
}
```
接著考慮 `.` 及 `..`，若是這兩個資料夾名稱，則不遞迴執行 `find()`
```diff=
case T_DIR:
...
while(read(fd, &de, sizeof(de)) == sizeof(de)) {
...
+ if (strcmp(".", de.name) == 0 || strcmp("..", de.name) == 0)
+ continue;
+ find(buf, fileName);
}
```
# xargs
- `argvs` 為執行 `exec` 時帶入的參數
- 透過 `read` 切割 input，將 input 放到 `buf`
- buf 放到 `argvs` 的最後一項
```clike=
int main(int argc, char *argv[])
{
char buf[128];
char *argvs[MAXARG];
char c;
char *p = buf;
memset(argvs, 0, sizeof(argvs));
int i;
for (i = 1; i < argc; i++) {
argvs[i - 1] = argv[i];
}
argvs[i-1] = buf;
while (read(0, &c, sizeof(c))) {
if (c != '\n' && p < (buf + sizeof(buf))) {
*p++ = c;
} else {
*p = '\0';
xargs(argvs);
p = buf;
}
}
return 0;
}
```
`xargs` 執行程式並帶入對應的參數
```clike=
void
xargs(char *argv[])
{
int pid;
if ((pid = fork()) < 0) {
printf("xargs: fork() failed\n");
exit(1);
} else if (pid == 0) {
close(0);
exec(argv[0], argv);
}
wait(0);
}
```
# references
https://pdos.csail.mit.edu/6.S081/2022/tools.html
https://github.com/mit-pdos/xv6-riscv
Sign in with Wallet
Connect another wallet