6.828 Lab1 Utilities

环境搭建

其实没什么好说的，用 Linux 很熟了，在 Debian 上跟步骤 apt install 就行了 (I’m not using arch btw)
盲猜很多人会卡在 git clone
我用的是 2020 版因为我已经做过了 🤣，再回味了一遍

解题思路

踩的一个坑是头文件有依赖关系，必须安装顺序 include, (linker is awesome btw), 然后 clang-format 自动给我 SortInclude 搞得我莫名其妙会失败，汗
还有就是 VSCode Makefile Extension 会导致 include 有问题，很迷

sleep

属于是练手题，让你知道怎么加 user program
然后知道 argc, argv, 转换 string 到 int 就行了？

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
 
int
main (int argc, char **argv)
{
  if (argc < 2)
    {
      printf ("usage: sleep <ticks>\n");
    }
  sleep (atoi (argv[1]));
  exit (0);
}

pingpong

pipe 练手题，要知道 fork and pipe 的用法，read, write, fd, parent and child
经典 IPC btw

The wait(0) function is a system call that suspends the execution of the calling process until one of its child processes terminates or a signal is received.

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
 
int
main (int argc, char const *argv[])
{
  // index 0 -> in, 1 -> out, like fd 0 1 2
  int p2c[2], c2p[2];
  pipe (p2c); // from parent to child
  pipe (c2p); // from child to parent
 
  if (fork () != 0)
    { // parent
      write (p2c[1], "ping", 4);
      char readin_buf[4];
      read (c2p[0], readin_buf, 4);
      printf ("%d: received pong\n", getpid ());
      wait (0); // wait for child to finish
    }
  else
    {
      char readin_buf[4];
      read (p2c[0], readin_buf, 4);
      printf ("%d: received ping\n", getpid ());
      write (c2p[1], readin_buf, 4);
    }
 
  exit(0);
}

$ pingpong
4: received ping
3: received pong

prime

这个还是非常有意思有难度的，和 MapReduce 有点像，又和 functional programming 中的 filter 有点像
中文文档写的不太好，没有很体现 筛 (sieve)

Sieve of Eratosthenes - Wikipedia

用 -1 作为 sentinel to indicate the end of input

第一次没做出来，再做了一次
要注意关 fd 不然会莫名其妙爆掉，查网上看到的，汗
有时候会纠结要不要 return, exit ，不过感觉重点是 wait

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
 
void
sieve (int p_left[2])
{
  // the 1st input is guaranteed to be prime since non-primes are filterd out
  int init_prime;
  read (p_left[0], &init_prime, sizeof (init_prime));
  if (init_prime == -1)
    {
      exit (0);
    }
 
  printf ("prime %d\n", init_prime);
 
  int p_right[2];
  pipe (p_right);
 
  if (fork () == 0)
    {
      // child
      close (p_left[0]);
      close (p_right[1]);
      sieve (p_right);
    }
  else
    {
      // parent
      close (p_right[0]);
      int i;
      while (read (p_left[0], &i, sizeof (i)) && i != -1)
        {
          if (i % init_prime != 0)
            {
              write (p_right[1], &i, sizeof (i));
            }
        }
      i = -1;
      write (p_right[1], &i, sizeof (i));
 
      wait (0);
    }
}
 
int
main (int argc, char const *argv[])
{
  int p[2];
  pipe (p);
 
  if (fork () == 0)
    { // child
      close (p[1]);
      sieve (p);
    }
  else
    {               // parent
      close (p[0]); // parent no need to read
      int i;
      for (i = 2; i <= 35; i++)
        {
          write (p[1], &i, sizeof (i));
        }
      i = -1;
      write (p[1], &i, sizeof (i));
      wait (0);
    }
 
  exit (0);
}

find

最无聊的一个，照抄就有
second thought：写错了，害得后面 xargs test 也错了,💩

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
 
void
find (char *path, char *target)
{
  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_FILE:
      if (strcmp (path + strlen (path) - strlen (target), target) == 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;
            }
 
          // omit . and ..
          if (strcmp (buf + strlen (buf) - 2, "/.") != 0
              && strcmp (buf + strlen (buf) - 3, "/..") != 0)
            {
              find (buf, target); // recursive find
            }
        }
      break;
    }
  close (fd);
}
 
int
main (int argc, char *argv[])
{
  if (argc < 3)
    {
      exit (0);
    }
  char target[512];
  target[0] = '/';
  strcpy (target + 1, argv[2]);
  find (argv[1], target);
  exit (0);
}

xargs

最烦人的一个，莫名其妙会报错，gdb 也没调出来，看其他人才发现理解错 xargs 了 (好像是写错 find 了？idk)
之前没写出来，尝试又重写了一次
主要难点是字符串处理，和理解 xargs

#include "kernel/param.h"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
 
// definitely not very readline but it suit the case
char *
readline (char *buf)
{
  char *pos = buf;
  while (read (0, pos, 1) != 0)
    {
      if (*pos == '\n' || *pos == '\0')
        {
          *pos = '\0';
          return pos;
        }
      pos++;
    }
  return 0;
}
 
void
run (char *program, char *argv[])
{
  if (fork () == 0)
    { // child
      exec (program, argv);
    }
  else
    {
      wait (0);
    }
}
 
int
main (int argc, char *argv[])
{
  char *program = argv[1];
  char *args[MAXARG];
  char readin_buf[2048];
 
  args[0] = program;
  int i = 1;
  // 0 is xargs, 1 is program, first arg starts at 2
  // this is tricky and ugly but it works so whatever
  while (i < argc - 1)
    {
      args[i] = argv[i + 1];
      i++;
    }
 
  char *str_end = readline (readin_buf);
  while (str_end != 0)
    {
      args[i] = readin_buf;
      i++;
      str_end = readline (str_end + 1);
    }
  args[i] = 0;
 
  run (program, args);
  exit (0);
}

实验心得

水平比第一次做的时候提升了，能写出来了😂
总体写的十分开心
或许可以加个 gdb 实验？虽然 printf 也很够了
sieve 的中文文档不太行
gnu c codestyle 是真的丑
好像比较麻木

make grade 似乎没提到？

== Test sleep, no arguments == 
$ make qemu-gdb
sleep, no arguments: OK (3.3s) 
== Test sleep, returns == 
$ make qemu-gdb
sleep, returns: OK (1.4s) 
== Test sleep, makes syscall == 
$ make qemu-gdb
sleep, makes syscall: OK (1.2s) 
== Test pingpong == 
$ make qemu-gdb
pingpong: OK (1.1s) 
== Test primes == 
$ make qemu-gdb
primes: OK (1.2s) 
== Test find, in current directory == 
$ make qemu-gdb
find, in current directory: OK (1.3s) 
== Test find, recursive == 
$ make qemu-gdb
find, recursive: OK (1.8s) 
== Test xargs == 
$ make qemu-gdb
xargs: OK (1.6s) 
== Test time == 
time: OK 
Score: 100/100

Fish Touching🐟🎣

Explorer