6.S081/6.828: 1 Lab Xv6 and Unix utilities

原创

冰寒火

修改于 2022-11-26 05:04:10

9970

修改于 2022-11-26 05:04:10

文章被收录于专栏：软件设计软件设计

一、背景

第一个Lab是实现几个shell工具，每个工具都是一个可以独立运行的main函数，会调用系统调用，但其本身并不是系统调用。

实验地址：Lab Xv6 and Unix utilities。

二、sleep

1 问题分析

基于已有的系统调用sleep，实现一个sleep命令，也就是一个main小程序，需要关注以下文件：

命令工具属于用户态，只要在user目录下即可，参考user/其他程序，user/ (e.g., user/echo.c, user/grep.c, and user/rm.c)。
参数不对需要打印错误信息。
sleep系统调用已经实现kernel/sysproc.c下的sys_sleep，user/user.h下也已经声明了sleep系统调用，可以触发中断，中断汇编代码在user/usys.S。
参考工具函数user/ulib.c。
在Makefile文件UPROGS下增加这个程序名，要不然不会编译。

2 代码实现

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

int
main(int argc, char *argv[])
{
  if(argc != 2){
    fprintf(2, "Usage: sleep param too many...\n");
    exit(1);
  }
  int t=atoi(argv[1]);
  sleep(t);
  exit(0);
}

三、pingpong

1 问题分析

实现进程间通信，这涉及到几点：

父进程fork子进程，父进程返回子进程pid，子进程返回0，父子进程共享数据。
pipe，pipe是单向通信，需要两个才能实现双向通信。
涉及read、write、getpid、pipe。

2 代码实现

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

#define ReadFd 0
#define WriteFd 1

/**
 * pipe是一段内核buffer，包含一对fd，一个用来读，一个用来写
 */

int
main(int argc, char *argv[])
{
  if(argc != 1){
    fprintf(2, "Usage: sleep param too many...\n");
    exit(1);
  }
  int f2c[2];
  int c2f[2];
  pipe(f2c);
  pipe(c2f);

  char buf[64];
  //fork对于父进程返回子进程ID，对于子进程返回0
  int pid=fork();
  if(pid>0){
      close(c2f[WriteFd]);
      close(f2c[ReadFd]);
      int n;
      //子进程先发送ping，父进程接收
      while((n=read(c2f[ReadFd],buf,64))<=0);
      fprintf(0,"%d: received %s\n",getpid(),buf);
      strcpy(buf,"pong");
      //收到ping后，父进程发送pong
      n=0;
      while((n=write(f2c[WriteFd],buf,sizeof(buf)))<=0);
      close(f2c[WriteFd]);
      close(c2f[ReadFd]);
      wait(&pid);
      exit(0);
  }else{
      close(c2f[ReadFd]);
      close(f2c[WriteFd]);
      strcpy(buf,"ping");
      int n=0;
      while((n=write(c2f[WriteFd],buf,sizeof(buf)))<=0);
      n=0;
      while ((n=read(f2c[ReadFd],buf,64))<=0);
      fprintf(0,"%d: received %s\n",getpid(),buf);
      close(f2c[WriteFd]);
      close(c2f[ReadFd]);
      exit(0);
  }
}

pipe是一段内核buffer，包含一对fd，一个用来读，一个用来写。pingpong需要f2c和c2f两对管道来实现父进程向子进程写数据，子进程读，子进程向父进程写数据，父进程读。

四、primes

1 问题分析

多进程来筛选素数，埃氏筛法，并实现CSP模型。

fork子进程进行下一步筛选，并且父进程需要等待子进程、子孙进程的结束。
文件句柄上限是35，超过会报错。
递归。
及时释放文件句柄，避免阻塞。
一定要并发，不能够串行，父进程向管道写入数据时要先fork子进程，尽量提高并行程度。

这里涉及到对pipe的理解。pipe是一段内核buffer，包含一对fd，一个用来读，一个用来写。如果读到空时则阻塞进程，如果向写满的pipe继续写入时也会阻塞。那么就会有一个问题：子进程读到空时阻塞，无法结束，而父进程需要wait子进程，也就不能够结束，是不是就死锁了？

pipe读到空时虽然会阻塞，但要是 write fd完全被关闭，则读进程就会被唤醒，返回0，所以我们一定要及时关闭对应的文件描述符，避免死锁。

2 代码实现

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

#define ReadFd 0
#define WriteFd 1

int prime(int fd);
int
main(int argc, char *argv[])
{
  if(argc>2)
    {
        fprintf(2,"usage: primes [number]");
        exit(1);
    }
    int n=35;
    if(argc==2)
    {
        int t=atoi(argv[1]);
        if(t<1)
        {
            fprintf(2,"parameter is invalid!");
            exit(1);
        }
        if(t>35)
            n=t;
    }
    int pp[2];
    pipe(pp);
    int pid=fork();
    if(pid>0){
      close(pp[ReadFd]);
      for (int i = 2; i <= n; i++){
        write(pp[WriteFd],&i,sizeof(int));
      }
      close(pp[WriteFd]);
      wait(&pid);
    }else{
      close(pp[WriteFd]);
      prime(pp[ReadFd]);
      close(pp[ReadFd]);
    }
    exit(0);
}
int prime(int fd){
    
    int first=2;
    int buf;
    if(read(fd,&buf,sizeof(int))<=0){
      exit(0);
    }
    first=buf;
    fprintf(0,"prime %d\n",first);
    int pp[2];
    pipe(pp);
    //传递数据前先fork子进程提高并行程度
    int pid=fork();
    if(pid>0){
      close(pp[ReadFd]);
      while (read(fd,&buf,sizeof(int))>0){
        if(buf%first!=0){
          write(pp[WriteFd],&buf,sizeof(int));
        }
      }
      close(pp[WriteFd]);
    }else{
      close(pp[WriteFd]);
      prime(pp[ReadFd]);
      close(pp[ReadFd]);
    }
    wait(&pid);
    exit(0);
}

五、find

1 问题分析

从指定目录下寻找目标文件。

参考ls.c，读目录。
迭代+递归，但是避免对"."、".."进行，否则会死循环。
make clean可以清除文件系统。

2 涉及的数据结构

//目录项
#define DIRSIZ 14

struct dirent {
  ushort inum;
  char name[DIRSIZ];
};

# 使用read读取目录即可。

//文件元信息
#define T_DIR     1   // Directory
#define T_FILE    2   // File
#define T_DEVICE  3   // Device

struct stat {
  int dev;     // File system's disk device
  uint ino;    // Inode number
  short type;  // Type of file
  short nlink; // Number of links to file
  uint64 size; // Size of file in bytes
};

int fstat(int fd, struct stat*);

3 代码实现

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

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));
  if (strlen(buf) == 0) return buf;
    for (int i = strlen(buf) - 1; i > 0; i--) {
        if (buf[i - 1] != ' ') {
            buf[i] = '\0';
            return buf;
        }
    }
    return buf;
  return buf;
}

void
find(char *path,char *file){
  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, "ls: cannot stat %s\n", path);
    close(fd);
    return;
  }
  
  switch(st.type){
  case T_FILE:
    //如果path是普通文件且最后一级是file
    if(strcmp(file,fmtname(path))==0){
        fprintf(1,"%s\n",path);
    }
    break;

  case T_DIR:
    //path+"/"+dirent.name
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
      printf("ls: path too long\n");
      break;
    }
    strcpy(buf, path);
    p = buf+strlen(buf);
    *p++ = '/';
    //buf=path+"/"+子目录名
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0)
        continue;
      //不要对当前目录和上级目录递归，会死循环
      if(strcmp(de.name,".")==0 || strcmp(de.name,"..")==0)
        continue;
        
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;
      if(stat(buf, &st) < 0){
        printf("find: cannot stat %s\n", buf);
        continue;
      }
      find(buf,file);
    }
    break;
  }
  close(fd);
}

int
main(int argc, char *argv[])
{

  if(argc != 3){
    fprintf(2, "Usage: find param err...\n");
    exit(1);
  }
  char *dir=argv[1];
  //file必须是文件名，不能是目录
  char *file=argv[2];
  find(dir,file);
  exit(0);
}

六、xargs

1 问题分析

这个shell命令的作用是将管道左边的输出作为xargs命令的输入，能够起到连接多条命令的作用。

从标准输入中读取所有行数据，然后将每一行作为xargs后面跟着的命令的参数去执行，左边有多少行，右边就执行多少次。要注意换行符“\n”

2 代码实现

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

#define BUFSIZE 1024
#define MAXLEN 100
int
main(int argc,char* argv[]){
    if(argc<2){
        fprintf(2,"Usage: xargs command\n");
        exit(1);
    }
    char *param[MAXARG];
    int index=0;
    for(int i=1;i<argc;i++){
        if(strcmp(argv[i],"-n")==0){
            i++;
        }else{
            param[index]=(char*)malloc(strlen(argv[i]));
            strcpy(param[index++],argv[i]);
        }
    }
    char buf[MAXLEN],*p=buf;
    while(read(0,p++,1)==1);
    int l=0,r=0;
    //"\n"输入后是两个字符"\\" +"n"，而不是"\n"
    while(r<strlen(buf)){
        if(buf[r]=='\\'&&r<strlen(buf)-1&&buf[r+1]=='n'){
            buf[l]='\n';
            r+=2;
            l++;
        }else{
            buf[l++]=buf[r++];
        }
    }
    buf[l]=0;
    // fprintf(1,"buf: %s, len: %d\n",buf,strlen(buf));
    l=0;
    while(buf[l]=='"'){
        l++;
    }
    //最后面会有一个换行符
    r=strlen(buf)-1-1;
    while(buf[r]=='"'){
        r--;
    }
    for(int i=l;i<=r ;i++){
        buf[i-l]=buf[i];
    } 
    buf[r+1-l]='\n';
    buf[r+2-l]=0;
    // fprintf(1,"l: %d, r: %d, buf: %s, len: %d\n",l,r,buf,strlen(buf));

    l=0;r=0;
    while(r<strlen(buf)){
        if(buf[r]=='\n'){
            param[index]=(char*)malloc(r-l);
            memmove(param[index],buf+l,r-l);
            // fprintf(1,"index: %d, line: %s\n",index,param[index]);
            int pid=fork();
            if (pid==0){
                exec(param[0], param);
                exit(0);
            }else{
                wait(&pid);
            }
            r++;
            l=r;
        }else{
            r++;
        }
    }
    exit(0);
}

主要逻辑就是将=从标准输入中读取数据，并按照'\n'进行分行，将每行数据作为xargs后面命令的参数，有多少行就执行多少次。要注意终端输入的"\n"并不是'\n'，而是'\' 'n'两个字符。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c 语言