6.S081：4.find功能实现

find (moderate)

Write a simple version of the UNIX find program: find all the files in a directory tree with a specific name. Your solution should be in the file user/find.c.

Some hints:

Look at user/ls.c to see how to read directories.

Use recursion to allow find to descend into sub-directories.

Don't recurse into "." and "..".

Changes to the file system persist across runs of qemu; to get a clean file system run make clean and then make qemu.

You'll need to use C strings. Have a look at K&R (the C book), for example Section 5.5.

Note that == does not compare strings like in Python. Use strcmp() instead.

Add the program to UPROGS in Makefile.

Your solution is correct if produces the following output (when the file system contains the files b and a/b):

$ make qemu
...
init: starting sh
$ echo > b
$ mkdir a
$ echo > a/b
$ find . b
./b
./a/b
    $

思考

在一个特定目录下根据文件名查找，查看user/ls.c源码可知，需要先打开文件/目录，显然目录里面又包含文件，这样一来，这个查找显然是需要递归的，当查找到目录时，递归查找该目录下的文件，当遇到文件时返回即可。

特别注意的是，不能查找.和..这两个目录，不然废了。

在xv6中定义了三种类型：

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

分别是目录、文件、设备，当xv6打开一个文件时，就要去申请一个stat数据结构，它包含了文件的信息

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;
}

要读取当前目录的每个条目，需要

read(fd, &de, sizeof(de)) == sizeof(de)

de保存了文件名，可以通过de.name访问，之后与目标文件名称对比即可，可以用strcmp

strcmp(de.name, target);

做出本实验的关键是看懂xv6如何读取文件目录

Code

#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;
    }
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
        printf("ls: path too long\n");
        close(fd);
        return ;
    }
    if(st.type != T_DIR) {
        close(fd);
        return ;
    }
    strcpy(buf, path);
    p = buf + strlen(buf);
    *p++ = '/';
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
        if(de.inum == 0 || strcmp(".", de.name) == 0 || strcmp("..", de.name) == 0) 
            continue;
        int flag = strcmp(de.name, target);
        memmove(p, de.name, DIRSIZ);
        p[DIRSIZ] = 0;
        //printf("%d %d\n", strlen(p), sizeof(p));
        if(flag == 0) fprintf(1, "%s\n", buf);
        find(buf, target);
    }
    close(fd);
}

int main(int argc, char *argv[]){
    if(argc < 3){
        fprintf(2, "argument counts error\n");
        exit(0);
    }
    find(argv[1], argv[2]);
    exit(0);
}