Xv6 Lab10: file system

Large files 链接到标题

这个作业需要我们将 xv6 的最大文件大小从 12 + 256 Bytes 修改为 11 + 256 + 256 * 256 Bytes。

为了达成这个目标，我们需要使用二级索引块，对 inode 的 addrs 字段，首先将 NDIRECT 从 $12$ 修改为 $11$，即前 $11$ 个 block 是 direct block，addrs[NDIRECT] 对应的块是一个一级索引块，这个块中的每个元素（共 BSIZE / sizeof(uint) 个元素）都是一个数据块的编号；而 addrs[NDIRECT + 1] 是一个二级索引块，这个块中的每个元素都是一级索引块的编号，由编号找到一级索引块，然后再由以及索引块找到数据块。

这个作业的主要任务就是修改 bmap 和 itrunc 两个函数。

先修改 fs.h 中的 NDIRECT 的相关定义：

#define FSMAGIC 0x10203040

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDINDIRECT (NINDIRECT * NINDIRECT)
#define MAXFILE (NDIRECT + NINDIRECT + NDINDIRECT)

struct dinode {
    short type;              // File type
    short major;             // Major device number (T_DEVICE only)
    short minor;             // Minor device number (T_DEVICE only)
    short nlink;             // Number of links to inode in file system
    uint size;               // Size of file (bytes)
    uint addrs[NDIRECT + 2]; // Data block addresses
};

注意 file.h 中的 inode 结构体也要做相应的修改。

修改 bmap 函数，用商来表示一级块的编号，模来表示数据块的编号。

static uint bmap(struct inode *ip, uint bn) {
    uint addr, *a;
    struct buf *bp;

    if (bn < NDIRECT) {
        if ((addr = ip->addrs[bn]) == 0)
            ip->addrs[bn] = addr = balloc(ip->dev);
        return addr;
    }
    bn -= NDIRECT;

    if (bn < NINDIRECT) {
        // Load indirect block, allocating if necessary.
        if ((addr = ip->addrs[NDIRECT]) == 0)
            ip->addrs[NDIRECT] = addr = balloc(ip->dev);
        bp = bread(ip->dev, addr);
        a = (uint *)bp->data;
        if ((addr = a[bn]) == 0) {
            a[bn] = addr = balloc(ip->dev);
            log_write(bp);
        }
        brelse(bp);
        return addr;
    }

    bn -= NINDIRECT;
    if (bn < NDINDIRECT) {
        if ((addr = ip->addrs[NDIRECT + 1]) == 0) {
            addr = balloc(ip->dev);
            ip->addrs[NDIRECT + 1] = addr;
        }
        struct buf *tmp_buf = bread(ip->dev, addr);
        uint *arr_tmp = (uint *)tmp_buf->data;
        uint lv1_addr;
        if ((lv1_addr = arr_tmp[bn / NINDIRECT]) == 0) {
            lv1_addr = balloc(ip->dev);
            arr_tmp[bn / NINDIRECT] = lv1_addr;
            log_write(tmp_buf);
        }
        brelse(tmp_buf);
        bp = bread(ip->dev, lv1_addr);
        a = (uint *)bp->data;
        if ((addr = a[bn % NINDIRECT]) == 0) {
            a[bn % NINDIRECT] = addr = balloc(ip->dev);
            log_write(bp);
        }
        brelse(bp);
        return addr;
    }

    panic("bmap: out of range");
}

修改 itrunc，如果了解 inode 的数据在磁盘中分布方式的话，free 起来也很简单，照着原先的 itrunc 写就好了。先释放数据块，然后释放这些数据块对应的一级索引块，最后释放这些数据块对应的二级索引块。

void itrunc(struct inode *ip) {
    int i, j;
    struct buf *bp;
    uint *a;

    for (i = 0; i < NDIRECT; i++) {
        if (ip->addrs[i]) {
            bfree(ip->dev, ip->addrs[i]);
            ip->addrs[i] = 0;
        }
    }

    if (ip->addrs[NDIRECT]) {
        bp = bread(ip->dev, ip->addrs[NDIRECT]);
        a = (uint *)bp->data;
        for (j = 0; j < NINDIRECT; j++) {
            if (a[j])
                bfree(ip->dev, a[j]);
        }
        brelse(bp);
        bfree(ip->dev, ip->addrs[NDIRECT]);
        ip->addrs[NDIRECT] = 0;
    }

    if (ip->addrs[NDIRECT + 1]) {
        bp = bread(ip->dev, ip->addrs[NDIRECT + 1]);
        a = (uint *)bp->data;
        for (int j = 0; j < NINDIRECT; ++j) {
            if (a[j]) {
                struct buf *sub_bp = bread(ip->dev, a[j]);
                uint *addr = (uint *)sub_bp->data;
                for (int k = 0; k < NINDIRECT; ++k) {
                    if (addr[k]) {
                        bfree(ip->dev, addr[k]);
                    }
                }
                brelse(sub_bp);
                bfree(ip->dev, a[j]);
            }
        }
        brelse(bp);
        bfree(ip->dev, ip->addrs[NDIRECT + 1]);
        ip->addrs[NDIRECT + 1] = 0;
    }

    ip->size = 0;
    iupdate(ip);
}

Symbolic links 链接到标题

首先要搞清楚硬连接（hard link）与符号连接（soft link or symbolic link）之间的区别。

int link(const char *target, const char *path)，我们要为 target 创建一个路径为 path 的硬链接。在硬链接的情况下，两个路径对应着同一个 inode，我们可以先看一下 xv6 中 sys_link 的实现，它的核心在于调用 dirlink 在 path 的父目录下，创建对应的 directory entry，而这个 entry（即 dirent）的 inum 和目标文件的 inum 是相同的，即当我们通过 dirlookup 调用 iget 来获取 inode 的指针时，两个指针指向的是同一个 inode。

而符号链接 int symlink(const char *target, const char *path) 则不一样，path 对应的 inode（记为 ip）和 target 对应的 inode（记为 tp）并不是同一个，只不过在 ip 的数据块中，存储的是 tp 的路径，即字符串 target。同时 ip->type 是 T_SYMLINK。

明确了符号链接与硬链接的区别，这个作业就不难写了（我当时把符号链接跟硬链接搞混了，折腾了很久）。

添加系统调用的步骤不再赘述。直接思考如何实现 sys_symlink。思路很简单，利用 create 创建一个 inode，注意这里创建的 inode（即返回的 inode 的指针）是带锁的！然后利用 writei 将数据（即字符串 target）写入到 inode，注意这里应该是 kernel page table 下，writei 自身会调用 iupdate，因此不需要我们手动调用 iupdate。

inode 是直写的，修改了 inode 的数据必须调用 iupdate 更新到磁盘。

注意整个流程需要用 begin_op 和 end_op 包裹起来，iput 也会调用 iupdate，而 iupdate 会调用 log_write。

uint64 sys_symlink(void) {
    char path[MAXPATH];
    char target[MAXPATH];
    struct inode *ip;
    // printf("symlink\n");
    if (argstr(0, target, MAXPATH) < 0 || argstr(1, path, MAXPATH) < 0) {
        return -1;
    }
    begin_op();
    // maxpath 为 128，即需要 128 个字节，一个 block 是 1024 个字节
    if ((ip = create(path, T_SYMLINK, 0, 0)) == 0) { // create 返回的是锁定的 ip
        end_op();
        return -1;
    }
    // printf("start_symlink_loop\n");
    if ((writei(ip, 0, (uint64)target, 0, MAXPATH)) < MAXPATH) {
        iunlockput(ip);
        end_op();
        return -1;
    }
    // iupdate(ip);
    iunlockput(ip);
    end_op();
    return 0;
}

同时，我们还需要修改 sys_open，添加判断 ip->type 是否为 T_SYMLINK 的处理逻辑，并且需要防止符号链接形成环路，即需要限制循环次数，我这里定为 #define R_MAX_DEPTH 12（这里之前没注意提示的内容，被死循环卡了挺久的）。

uint64 sys_open(void) {
    char path[MAXPATH];
    int fd, omode;
    struct file *f;
    struct inode *ip;
    int n;

    if ((n = argstr(0, path, MAXPATH)) < 0 || argint(1, &omode) < 0)
        return -1;

    begin_op();

    if (omode & O_CREATE) {
        ip = create(path, T_FILE, 0, 0);
        if (ip == 0) {
            end_op();
            return -1;
        }
    } else {
        if ((ip = namei(path)) == 0) {
            end_op();
            return -1;
        }
        ilock(ip);
        if (ip->type == T_DIR && omode != O_RDONLY) {
            iunlockput(ip);
            end_op();
            return -1;
        }
    }

    if (ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)) {
        iunlockput(ip);
        end_op();
        return -1;
    }

    if (ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
        int read_num;
        int recur_times = 0;
        while (ip->type == T_SYMLINK) {
            if ((read_num = readi(ip, 0, (uint64)path, 0, MAXPATH)) < MAXPATH) {
                iunlockput(ip);
                end_op();
                return -1;
            }
            iunlockput(ip);
            ip = namei(path);
            // printf("symlink, path: %s %d\n", path, 2);
            if (ip == 0 || recur_times++ >= R_MAX_DEPTH) {
                end_op();
                return -1;
            }
            ilock(ip);
        }
    }

    if ((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0) {
        if (f)
            fileclose(f);
        iunlockput(ip);
        end_op();
        return -1;
    }

    if (ip->type == T_DEVICE) {
        f->type = FD_DEVICE;
        f->major = ip->major;
    } else {
        f->type = FD_INODE;
        f->off = 0;
    }
    f->ip = ip;
    f->readable = !(omode & O_WRONLY);
    f->writable = (omode & O_WRONLY) || (omode & O_RDWR);

    if ((omode & O_TRUNC) && ip->type == T_FILE) {
        itrunc(ip);
    }

    iunlock(ip);
    end_op();

    return fd;
}