# Lab 1 Xv6 and Unix utilities

## Introduction 

This lab makes you familiar with xv6 and its system calls.

## 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

```
if(argc < 2){
  fprintf(2, “Usage: sleep for a new sec…\n”);
  exit(-1);
}
sleep(atoi(argv[1]));
exit(1);
```

## 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

```
int p[2];
  char buf[100];
  pipe(p);

  int pid = fork();
  if (pid == 0) {
    write(p[1], “ping”, 4);
    printf(“Thread id %d: received ping\n”, getpid());
  } 
  else {
    wait(0);
    read(p[0], buf, 4);
    printf(“Thread id %d: received pong\n”, getpid());
  }
```

## 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](http://swtch.com/~rsc/thread/) and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

### Hints

```
$ primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
```

### Solution

Use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbour over a pipe and writes to its right neighbour over another pipe.

![](https://1274781047-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M13JlZNu0b_edmxHTQk%2F-M1PLpQ2KkOlY7G30_CI%2F-M1PM4eg-SnFssl_F0q-%2Fimage.png?alt=media\&token=e4f1959f-d0cf-4e93-8d28-7988a3001efb)

Loop from 2 to 35. Write them to pipe one by one. Read the first one from pipe buffer. Record as `Num`. Create a new pipe, write everything not dividable by `Num` (Use mod).

```c
void exec_pipe(int *fd*)
{
    int num;
    read(fd, &num, 4);
    printf(“Thead(%d) prime %d\n”, getpid(), num);

    int p[2];
    pipe(p);
    int tmp = -1;
    while (1) {
        int n = read(fd, &tmp, 4);
        if (n<= 0) {
            break;
        }
        if (tmp % num != 0) {
            *//printf(“%d writing %d and n is: %d\n”, getpid(), tmp, n);*
            write(p[1], &tmp, 4);
        }
    }
    if (tmp == -1) {
        close(p[1]);
        close(p[0]);
        close(fd);
        return;
    }
    int pid = fork();
    if (pid == 0) {
        close(p[1]);
        close(fd);
        exec_pipe(p[0]);
        close(p[0]);
    }
    else {
        close(p[1]);
        close(p[0]);
        close(fd);
        wait(0);
    }
}
```

```c
int
main(int *argc*, char **argv*[])
{
  int p[2];
  pipe(p);
  for (int i = 2; i<35; i++) {
      int n = i;
      write(p[1], &n, 4);
  }
  close(p[1]);
  exec_pipe(p[0]);
  close(p[0]);

  exit(1);
}
```

## 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

Code is modified based on `ls`. Below is the `ls` code:

```c
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));
  memset(buf+strlen(p), ‘ ‘, DIRSIZ-strlen(p));
  return buf;
}

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

  if((fd = open(path, 0)) < 0){
    fprintf(2, “ls: cannot open %s\n", path);
    return;
  }

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

  switch(st.type){
  case T_FILE:
    printf(“%s %d %d %l\n”, fmtname(path), st.type, st.ino, st.size);
    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(“ls: cannot stat %s\n”, buf);
        continue;
      }
      printf(“%s %d %d %d\n”, fmtname(buf), st.type, st.ino, st.size);
    }
    break;
  }
  close(fd);
}
```

Modify the case `T_DIR` to do the filename comparision.

```c
if (st.type == T_DIR && *p != '.') {
          ls(p, filename);
      } else if (strcmp(p, filename) == 0) {
        printf(“./%s\n”, buf);
      }
```

## 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.

### Hints

* Use fork and exec system call to invoke the command on each line of input. Use wait in the parent to wait for the child to complete running the command.
* Read from stdin a character at the time until the newline character (‘\n’).
* kernel/param.h declares `MAXARG`, which may be useful if you need to declare an argv.
* Changes to the file system persist across runs of qemu; to get a clean file system run make clean and then make qemu.

### Solution

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

int
getcmd(char **buf*, int *nbuf*)
{
  memset(buf, 0, nbuf);
  gets(buf, nbuf);
  if(buf[0] == 0) *// EOF*
  {
    *//printf("WOW!\n");*
    return -1;
  }

  return 0;
}

char whitespace[] = " \t\r\n\v";

int
gettoken(char ***ps*, char **es*, char ***q*, char ***eq*)
{
  char *s;
  int ret;

  s = *ps;
  while(s < es && strchr(whitespace, *s))
    s++;
  if(q)
    *q = s;
  ret = *s;
  switch(*s){
  case 0:
    break;
  default:
    ret = 'a';
    while(s < es && !strchr(whitespace, **s*))
      s++;
    break;
  }
  if(eq)
    *eq = s;

  while(s < es && strchr(whitespace, *s))
    s++;
  *ps = s;
  return ret;
}

int
main(int *argc*, char **argv*[])
{
  char *xargs[MAXARG];
  for (int i=1; i<argc;i++) {
    *// Skip `xargs` cmd name.*
    xargs[i-1] = argv[i];
  }

  static char buf[MAXARG][100];
  char *q, *eq;
  int j = argc-1;
  int i = 0;
  *// Split each line into array of args.*
  while(getcmd(buf[i], sizeof(buf[i])) >= 0){
    char *s = buf[i];
    char *es = s + strlen(s);
    while (gettoken(&s, es, &q, &eq) != 0) {
      *// Set end to 0.*
      xargs[j] = q;
      *eq = 0;
      j++;
      i++;
    }
  }

  int pid = fork();
  if (pid == 0) {
    exec(xargs[0], xargs);
  }
  wait();

  exit();
}
```

### Things learnt

1. `ls` looks up current process directory if no args is passed in. Similar to `ls .` `namex` is used to look up directory `inode`, and find all filenames in the directory `inode`.
2. `pipe` does not close if write part fd is closed. So we can do: write everything to `p[1]`, close `p[1]’s fd`, then read from `p[0]`.
3. Think more why we designed this way, not just make it working and leave.

## 心得

C程序短小精悍。在unix的世界里数个小部件拼接成大项目。每一个bit都来的有缘由, 没有多余的内存用来浪费。这才是编程的精髓吧。


---

# 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://xiayingp.gitbook.io/build_a_os/labs/lab-1-xv6-and-unix-utilities.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.