# Lab1

## 启动xv6(难度：Easy)

<https://lmx.gitbook.io/mit-6.s081/>

## sleep(难度：Easy)

> YOUR JOB
>
> **实现xv6的UNIX程序**`sleep`**：您的**`sleep`**应该暂停到用户指定的计时数。一个滴答(tick)是由xv6内核定义的时间概念，即来自定时器芯片的两个中断之间的时间。您的解决方案应该在文件\*user/sleep.c\*中**

```c
// user/ulib.c
int
atoi(const char *s)
{
  int n;

  n = 0;
  while('0' <= *s && *s <= '9')
    n = n*10 + *s++ - '0';
  return n;
}

// kernel/sysproc.c
uint64
sys_sleep(void)
{
  int n;
  uint ticks0;

  if(argint(0, &n) < 0)
    return -1;
  acquire(&tickslock);
  ticks0 = ticks;
  while(ticks - ticks0 < n){
    if(myproc()->killed){
      release(&tickslock);
      return -1;
    }
    sleep(&ticks, &tickslock);
  }
  release(&tickslock);
  return 0;
}
// kernel/sysproc.h
#define SYS_sleep  13

// user/user.h提供了sleep的声明以便其他程序调用,用汇编程序编写的user/usys.S可以帮助sleep从用户区跳转到内核区。
```

实现代码：

```c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int 
main(int args,char *argv[]) 
{
    if (args < 2) {
        fprintf(2,"Usage: sleep time\n");
        exit(1);
    }

    int t;
    t = atoi(argv[1]);
    sleep(t);

    exit(0);
}
```

测试：

```shell
./grade-lab-util sleep

# output:
== Test sleep, no arguments == sleep, no arguments: OK (3.4s) 
== Test sleep, returns == sleep, returns: OK (1.0s) 
== Test sleep, makes syscall == sleep, makes syscall: OK (1.1s) 
```

## pingpong（难度：Easy）

> YOUR JOB
>
> **编写一个使用UNIX系统调用的程序来在两个进程之间“ping-pong”一个字节，请使用两个管道，每个方向一个。父进程应该向子进程发送一个字节;子进程应该打印“`<pid>: received ping`”，其中`<pid>`是进程ID，并在管道中写入字节发送给父进程，然后退出;父级应该从读取从子进程而来的字节，打印“`<pid>: received pong`”，然后退出。您的解决方案应该在文件\*user/pingpong.c\*中。**

**请使用两个管道**

不用两个管道会报莫名其妙的错误(我还是看不透pipe)

p\[0] 是管道的读端，p\[1]是管道的写端

```c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

char buf[1024];
int
main(int argc, char const *argv[])
{
    if (argc > 1) {
        fprintf(2,"Usage: pingpong\n");
        exit(1);
    }
    // cp child pipe，pp parent pipe
    int cp[2],pp[2];
    // cbuf：child buf
    char cbuf[10],pbuf[10];
    
    // Initialize the read(p[0]) and write(p[1]) side of the pipeline
    pipe(cp);
    pipe(pp);

    int rc = fork();
    // fork 会让父子复制文件描述符，管道fork之后可以看成连接父子，四个端口，所以你会看到下面重复close
    if (rc==0) {
        //entry child
        // close the write side when reading
        close(cp[1]);
        // receive parent ping
        int r = read(cp[0],cbuf,1);
        if (r > 0) {
            printf("%d: received ping\n",getpid());
        }
        close(cp[0]);
        // send pong
        // Close the read side of parent when writing
        close(pp[0]);
        write(pp[1],"c",1);
        close(pp[1]);
        exit(0);
    } else if (rc > 0) {
        // entry parent
        // Close the read side of child pipe when writing
        close(cp[0]);
        write(cp[1],"p",1);
        // close the write side after writing
        close(cp[1]);
        // receive pong
        wait(0);
        // close the write side when reading
        close(pp[1]);
        int r = read(pp[0],pbuf,1);
        if (r > 0) {
            printf("%d: received pong\n",getpid());
        }
        // close the read side after reading
        close(pp[0]);
    } else {
        fprintf(2,"fork error\n");
        exit(1);
    }

    exit(0);
}
```

测试：

```shell
root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util pingpong

make: 'kernel/kernel' is up to date.
== Test pingpong == pingpong: OK (0.9s) 
```

## Primes(素数，难度：Moderate/Hard)

> tasks:
>
> YOUR JOB
>
> **使用管道编写**`prime sieve`**(筛选素数)的并发版本。这个想法是由Unix管道的发明者Doug McIlroy提出的。请查看**[**这个网站**](http://swtch.com/~rsc/thread/)**，该网页中间的图片和周围的文字解释了如何做到这一点。您的解决方案应该在\*user/primes.c\*文件中。**

感觉上面那题会了的话，这题比上一题简单

```c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int 
main(int argc, char const *argv[])
{
    int p[2],nums[36];
    int index = 0;
    for (int i=2;i<36;i++) {
        nums[index++] = i;
    }

    while (index > 0)
    {
        // p[0] read , p[1] write
        pipe(p);
        int rc = fork();
        if (rc > 0) {
            // entry parent
            close(p[0]);
            for(int i=0;i<index;i++) {
                write(p[1],&nums[i],sizeof(int));
            }
            close(p[1]);
            // 主进程一直在这里等着子进程完成，子进程一完成就会进入
            wait(0);
            // 如果这里不exit的话，当打完所有的素数后就会陷入死循环
            exit(0);
        } else if (rc == 0) {
            close(p[1]);
            index = -1;
            int val,prime;
            prime = -1;
            while (read(p[0],&val,sizeof(int)) > 0)
            {
                if (index < 0) {
                    prime = val;
                    index++;
                }else if (val%prime!=0) {
                    nums[index++] = val;
                }
            }
            close(p[0]);
            printf("prime %d\n",prime);
        }
    }
    
    exit(0);
}
```

测试：

```shell
root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util primes
make: 'kernel/kernel' is up to date.
== Test primes == primes: OK (1.5s) 
```

关于上面的主线程为什么要exit，有一个比较坑的地方：

看下面程序:

```c
#include<stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc, char const *argv[])
{
    int index = 0;
    while (index <= 3)
    {
        printf("entry while\n");
        int rc = fork();
        if (rc == 0) {
            printf("child pid:%d\n",getpid());
            index++;
            printf("%d \n",index);
            sleep(1);
        }else {
            printf("parent pid:%d\n",getpid());
            wait(0);
            exit(0);
        }
    }
    printf("break while\n");
    exit(0);
}
// 它会进入死循环，然后一直 输出
/*
entry while
parent pid:24154
child pid:24167
3 
*/
```

* 首先fork出来的是进程，父和子的index是不相通的
* 当子进程的index超过3，子进程就会结束
* 这里意思就是在3之前主进程都在wait(),3的时候子进程会exit，这时候index为2的是它的父进程，而这个2的进程同时也是1的子进程，所以那个最初的进程一直都不会退出，然后一直卡在index为2的那个线程那里，一直fork。
* 当到子进程的index为2时，他成为父进程，fork一个子进程，子进程复制变量，index=2，index++ 变成3，然后该子进程退出。但是此时父进程的index是2，它还会继续进入循环，又fork一个子进程，子进程再复制变量，然后自增，周而复始...这样就一直卡在3这里了
* 所以必须有个 exit(0),在他完成所有的子任务第一遍时，也就是打印第一遍3的时候就退出程序，这样就完成了任务了
* 再看上面的通关代码，也是如此，如果没有exit(0),就会一直卡在输出31的地方，因为它也会在那时候一直fork一个子进程，然后退出然后再fork再退出再fork。
* 反正就是要记得，fork会复制变量，但是父子的变量是不同的，子进程的这个变量改变不会影响父进程的值。也就是fork是变量复制但不共享

## find（难度：Moderate）

> YOUR JOB
>
> **写一个简化版本的UNIX的`find`程序：查找目录树中具有特定名称的所有文件，你的解决方案应该放在\*user/find.c\***

刚开始不知道他要实现啥，写完只通过了第一个test，但是输出显示第二个test我失败是miss了一些输出，那我按它的输入去debug，发现我没有递归进子目录....蠢得可以，又改了一下才ok，所以还是要好好思考...

```
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
void find(char* path) {
    // 这里得代码主要是参照 ls.c 的，lab里面提示的，应该不算作弊(bushi
    int fd;
    char buf[512];
    char *p;
    struct dirent de;
    struct stat st;

    if ((fd=open(path,0))<0)
    {
        fprintf(2, "find: %s: No such file or directory\n", path);
        return;
    }
    if(fstat(fd, &st) < 0){
        fprintf(2, "find: %s:cannot stat\n", path);
        close(fd);
        return;
    }

    switch (st.type)
    {
    case T_FILE:
        // 如果是文件直接输出就可了
        printf("%s\n",path);
        break;
    case T_DIR:
        // 如果是dir处理起来麻烦点，但是不难，就是要记得如果子目录也是dir的话也要进行递归
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
            printf("find: path too long\n");
            return;
        }
        strcpy(buf, path);
        p = buf+strlen(buf);
        *p++ = '/';
        while (read(fd, &de, sizeof(de)) == sizeof(de))
        {
            if(de.inum == 0) {
                continue;
            }
            // 因为de.name的定义是 char name[DIRSIZ]; 
            // 这里会直接把p的值设为de.name
            // 但是前面已经*p++='/'了，所以de.name会添加在buf的'/'后面
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;
            if(stat(buf, &st) < 0){
                printf("find: cannot stat %s\n", buf);
                continue;
            }
            if(st.type==T_FILE){
                printf("%s\n",buf);
            }else if (st.type==T_DIR&&strcmp(de.name,".")!=0&&strcmp(de.name,"..")!=0){
                printf("%s\n",buf);
                find(buf);
            }else {
                printf("%s\n",buf);
            }
        }
        break;
    }
    close(fd);
}

int main(int argc, char *argv[])
{
    // the solution of find
    if(argc == 1) {
        find(".");
        exit(0);
    }
    
    // 有几个要查找得参数就查几次
    for(int i = 1;i < argc;i++) {
        find(argv[i]);
    }
    exit(0);
}

```

test:

```
./grade-lab-util find 

make: 'kernel/kernel' is up to date.
== Test find, in current directory == find, in current directory: OK (2.1s) 
== Test find, recursive == find, recursive: OK (1.8s) 
```

不知道有没有更快得实现，期待一手

## xargs (难度： Moderate)

前面的find实现有坑，我的find理解和出题人的find理解不同

在ubuntu下的 find . b 不是先 find . 再 find b吗，我试了一下就是这样啊，但是这道题目要求find . b 是在 . 路径下寻找 b 的目录，这让我不得不回去改了一下find的代码，先贴上改完的find，被迫无奈：

```
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

char* filename;

void find(char* path,int bool) {
    int fd;
    char buf[512];
    char *p;
    struct dirent de;
    struct stat st;

    if ((fd=open(path,0))<0)
    {
        fprintf(2, "find: %s: No such file or directory\n", path);
        return;
    }
    if(fstat(fd, &st) < 0){
        fprintf(2, "find: %s:cannot stat\n", path);
        close(fd);
        return;
    }

    switch (st.type)
    {
    case T_FILE:
        if(bool == 0) {
            printf("%s\n",buf);
        }else if (bool == 1 && strcmp(filename,de.name)==0){
            printf("%s\n",buf);
        }
        break;
    case T_DIR:
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
            printf("find: path too long\n");
            return;
        }
        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(st.type==T_FILE){
                if(bool == 0) {
                    printf("%s\n",buf);
                }else if (bool == 1 && strcmp(filename,de.name)==0){
                    printf("%s\n",buf);
                }
            }else if (st.type==T_DIR&&strcmp(de.name,".")!=0&&strcmp(de.name,"..")!=0){
                if (bool == 0) {
                    printf("%s\n",buf);
                    find(buf,0);
                }else if(bool == 1) {
                    if (strcmp(filename,de.name)==0) {
                        printf("%s\n",buf);
                    }
                    find(buf,1);
                }
            }
        }
        break;
    }
    close(fd);
}

int main(int argc, char *argv[])
{
    // the solution of find
    if(argc == 1) {
        find(".",0);
        exit(0);
    }

    if(argc == 3 && strcmp(argv[1],".")==0) {
        filename = (char *)malloc(sizeof(argv[2]));
        filename = argv[2];
        find(".",1);
        exit(0);
    }
    
    for(int i = 1;i < argc;i++) {
        find(argv[i],0);
    }
    exit(0);
}
```

通过实现：

```
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/param.h"
#include "user/user.h"

const int MAXREAD = 1024;

int main(int argc, char *argv[])
{
    // stdout 0
    char* params[MAXARG];
    int index = 0;
    for(int i=1;i<argc;i++){
        params[index++] = argv[i];
    }

    char buf[MAXREAD];
    int bytes = 0;
    while ((bytes=read(0,&buf,MAXREAD))>0)
    {
        char *arg = (char *)malloc(sizeof(buf));
        int argi = 0;
        // 因为下面要执行 exec，所以需要fork
        int rc = fork();
        if(rc==0) {
            for(int i=0;i<bytes;i++) {
                // 如果碰到 \n or space 说明一个单词结束了，这时候添加进params然后重置初始化工作
                if(buf[i]=='\n'||buf[i]==' ') {
                    // 结束标志,不加也行
                    arg[argi] = '\0;
                    argi = 0;
                    params[index++] = arg;
                    arg = (char *)malloc(sizeof(arg));
                }else {
                    arg[argi++]=buf[i];
                }
            }
            exec(argv[1],params);
        }else {
            wait(0);
        }
    }
    
    exit(0);
}
```

test:

```
root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util xargs
make: 'kernel/kernel' is up to date.
== Test xargs == xargs: OK (2.0s) 
    (Old xv6.out.xargs failure log removed)

root@ubuntu:/home/lmx/Desktop/xv6-labs-2020# ./grade-lab-util find
make: 'kernel/kernel' is up to date.
== Test find, in current directory == find, in current directory: OK (1.2s) 
== Test find, recursive == find, recursive: OK (1.1s)
```

<br>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lmx.gitbook.io/mit-6.s081/lab/lab1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.