Lab8 report

练习0：填写已有实验

用meld对比修改了以下文件：

kdebug.c
trap.c
default_pmm.c
pmm.c
swap_fifo.c
vmm.c
proc.c
default_sched.c
monitor.c
check_sync.c

在练习0中暂时无需对以上文件做修改。

练习1: 完成读文件操作的实现（需要编码）

实验思路

打开文件时，调用 safe_open()函数，然后依次调用open->sys_open->syscall，从而引发系统调用然后进入内核态，然后会由sys_open内核函数处理系统调用，进一步调用到内核函数sysfile_open，然后将存有文件路径的字符串拷贝到内核空间中的字符串path中，并进入到vfs的处理流程完成进一步的打开文件操作中。
系统会分配一个file变量，这个变量其实是current->fs_struct->filemap[]中的一个元素，内容为空，但是分配完了之后还不能找到对应对应的文件结点。所以系统在该层调用了vfs_open函数通过调用vfs_lookup找到path对应文件的inode，然后调用vfs_open函数打开文件。然后层层返回，通过执行语句file->node=node;，就把当前进程的current->fs_struct->filemap[fd]（即file所指变量）的成员变量node指针指向了代表文件的索引节点node。这时返回fd。最后完成打开文件的操作。

实现过程

sfs_inode.c

sfs_io_nolock()函数

static int
sfs_io_nolock(struct sfs_fs *sfs, struct sfs_inode *sin, void *buf, off_t offset, size_t *alenp, bool write) {
    ······
    //读取第一部分的数据
    if ((blkoff = offset % SFS_BLKSIZE) != 0) {
        size = (nblks != 0) ? (SFS_BLKSIZE - blkoff) : (endpos - offset);
        if ((ret = sfs_bmap_load_nolock(sfs, sin, blkno, &ino)) != 0) {
            goto out;
        }
        if ((ret = sfs_buf_op(sfs, buf, size, ino, blkoff)) != 0) {
            goto out;
        }
        alen += size;
        if (nblks == 0) {
            goto out;
        }
        buf += size, blkno ++, nblks --;
    }
    //读取中间部分的数据，将其分为size大学的块，然后一次读一块直至读完
    size = SFS_BLKSIZE;
    while (nblks != 0) {
        if ((ret = sfs_bmap_load_nolock(sfs, sin, blkno, &ino)) != 0) {
            goto out;
        }
        if ((ret = sfs_block_op(sfs, buf, ino, 1)) != 0) {
            goto out;
        }
        alen += size, buf += size, blkno ++, nblks --;
    }
    //读取第三部分的数据
    if ((size = endpos % SFS_BLKSIZE) != 0) {
        if ((ret = sfs_bmap_load_nolock(sfs, sin, blkno, &ino)) != 0) {
            goto out;
        }
        if ((ret = sfs_buf_op(sfs, buf, size, ino, 0)) != 0) {
            goto out;
        }
        alen += size;
    }
    ······
}

思考题

在实验报告中给出设计实现”UNIX的PIPE机制“的概要设方案，鼓励给出详细设计方案

管道可以看作是由内核管理的一个缓冲区，一端连接进程A的输出，另一端连接进程B的输入。进程A会向管道中放入信息，而进程B会取出被放入管道的信息。当管道中没有信息，进程B会等待，直到进程A放入信息。当管道被放满信息的时候，进程A会等待，直到进程B取出信息。当两个进程都结束的时候，管道也自动消失。
管道基于fork机制建立，从而让两个进程可以连接到同一个PIPE上。
最开始的时候，管道两端都连接在同一个进程A上，当fork复制进程A得到进程B的时候，会将这两个连接也复制到新的进程B上。随后，每个进程关闭自己不需要的一个连接。例如进程A关闭向PIPE输入的链接，进程B关闭接收PIPE输出的连接。 从而二者即可通过该PIPE进行通信。
在UNIX中，管道的实现并没有使用专门的数据结构，而是借助了文件系统的file结构和VFS的索引节点inode。通过将两个 file 结构指向同一个临时的 VFS 索引节点，而这个 VFS 索引节点又指向一个物理页面而实现的。具体来说，即有两个 file 数据结构，但它们定义文件操作例程地址是不同的，其中一个是向管道中写入数据的例程地址，而另一个是从管道中读出数据的例程地址。这样，用户程序的系统调用仍然是通常的文件操作，而内核却利用这种抽象机制实现了管道这一特殊操作。
当写进程向管道中写入时，它利用标准的库函数write()，系统根据库函数传递的文件描述符，可找到该文件的 file 结构。file 结构中指定了用来进行写操作的函数（即写入函数）地址，于是，内核调用该函数完成写操作。
写入函数在向内存中写入数据之前，必须首先检查 VFS 索引节点中的信息，同时满足如下条件时，才能进行实际的内存复制工作：

1. 内存中有足够的空间可容纳所有要写入的数据；
2. 内存没有被读程序锁定。

如果同时满足上述条件，写入函数首先锁定内存，然后从写进程的地址空间中复制数据到内存。否则，写入进程就休眠在 VFS 索引节点的等待队列中，接下来，内核将调用调度程序，而调度程序会选择其他进程运行。写入进程实际处于可中断的等待状态，当内存中有足够的空间可以容纳写入数据，或内存被解锁时，读取进程会唤醒写入进程，这时，写入进程将接收到信号。当数据写入内存之后，内存被解锁，而所有休眠在索引节点的读取进程会被唤醒。
管道的读取过程和写入过程类似。但是，进程可以在没有数据或内存被锁定时立即返回错误信息，而不是阻塞该进程，这依赖于文件或管道的打开模式。反之，进程可以休眠在索引节点的等待队列中等待写入进程写入数据。当所有的进程完成了管道操作之后，管道的索引节点被丢弃，而共享数据页也被释放。

练习2: 完成基于文件系统的执行程序机制的实现（需要编码）

实验思路

load_icode主要是将文件加载到内存中执行，根据注释的提示分为了七个步骤：

1. 建立内存管理器
2. 建立页目录
3. 将文件逐个段加载到内存中，这里要注意设置虚拟地址与物理地址之间的映射
4. 建立相应的虚拟内存映射表
5. 建立并初始化用户堆栈
6. 处理用户栈中传入的参数
7. 最后很关键的一步是设置用户进程的中断帧

此外，一旦发生错误还需要进行错误处理。

实现过程

proc.c

alloc_proc()函数

static struct proc_struct *
alloc_proc(void) {
    ······
        proc->filesp = NULL;//初始化fs中的进程控制结构
    }
    return proc;
}

do_fork()函数

int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    ······    
    if (setup_kstack(proc) != 0) {
        goto bad_fork_cleanup_proc;
    }
    /*if (copy_mm(clone_flags, proc) != 0) {
        goto bad_fork_cleanup_kstack;
    }*/
    if (copy_files(clone_flags, proc) != 0) {
        goto bad_fork_cleanup_kstack;
    }
    if (copy_mm(clone_flags, proc) != 0) {
        goto bad_fork_cleanup_fs;
    }
    copy_thread(proc, stack, tf);
}

load_icode()函数

static int
load_icode(int fd, int argc, char **kargv) {
    assert(argc >= 0 && argc <= EXEC_MAX_ARG_NUM);
    //(1)建立内存管理器
    if (current->mm != NULL) {
        panic("load_icode: current->mm must be empty.\n");
    }
    //(2)建立页目录
    int ret = -E_NO_MEM;// E_NO_MEM代表因为存储设备产生的请求错误
    struct mm_struct *mm;// 建立内存管理器
    if ((mm = mm_create()) == NULL) {
        goto bad_mm;
    }
    if (setup_pgdir(mm) != 0) {
        goto bad_pgdir_cleanup_mm;
    }
    struct Page *page;
    //(3)从文件加载程序到内存
    struct elfhdr __elf, *elf = &__elf;
    if ((ret = load_icode_read(fd, elf, sizeof(struct elfhdr), 0)) != 0) {
        goto bad_elf_cleanup_pgdir;
    }
    if (elf->e_magic != ELF_MAGIC) {
        ret = -E_INVAL_ELF;
        goto bad_elf_cleanup_pgdir;
    }
    struct proghdr __ph, *ph = &__ph;
    uint32_t vm_flags, perm, phnum;
    for (phnum = 0; phnum < elf->e_phnum; phnum ++) {
        off_t phoff = elf->e_phoff + sizeof(struct proghdr) * phnum;//循环读取程序的每个段的头部
        if ((ret = load_icode_read(fd, ph, sizeof(struct proghdr), phoff)) != 0) {
            goto bad_cleanup_mmap;
        }
        if (ph->p_type != ELF_PT_LOAD) {
            continue ;
        }
        if (ph->p_filesz > ph->p_memsz) {
            ret = -E_INVAL_ELF;
            goto bad_cleanup_mmap;
        }
        if (ph->p_filesz == 0) {
            continue ;
        }
        vm_flags = 0, perm = PTE_U;
        if (ph->p_flags & ELF_PF_X) vm_flags |= VM_EXEC;
        if (ph->p_flags & ELF_PF_W) vm_flags |= VM_WRITE;
        if (ph->p_flags & ELF_PF_R) vm_flags |= VM_READ;
        if (vm_flags & VM_WRITE) perm |= PTE_W;
        if ((ret = mm_map(mm, ph->p_va, ph->p_memsz, vm_flags, NULL)) != 0) {
            goto bad_cleanup_mmap;
        }
        off_t offset = ph->p_offset;
        size_t off, size;
        uintptr_t start = ph->p_va, end, la = ROUNDDOWN(start, PGSIZE);
        ret = -E_NO_MEM;
        //复制数据段和代码段
        end = ph->p_va + ph->p_filesz;
        while (start < end) {
            if ((page = pgdir_alloc_page(mm->pgdir, la, perm)) == NULL) {
                ret = -E_NO_MEM;
                goto bad_cleanup_mmap;
            }
            off = start - la, size = PGSIZE - off, la += PGSIZE;
            if (end < la) {
                size -= la - end;
            }
            if ((ret = load_icode_read(fd, page2kva(page) + off, size, offset)) != 0) {
                goto bad_cleanup_mmap;
            }
            start += size, offset += size;
        }
        //建立BSS段
        end = ph->p_va + ph->p_memsz;
        if (start < la) {
            /* ph->p_memsz == ph->p_filesz */
            if (start == end) {
                continue ;
            }
            off = start + PGSIZE - la, size = PGSIZE - off;
            if (end < la) {
                size -= la - end;
            }
            memset(page2kva(page) + off, 0, size);
            start += size;
            assert((end < la && start == end) || (end >= la && start == la));
        }
        while (start < end) {
            if ((page = pgdir_alloc_page(mm->pgdir, la, perm)) == NULL) {
                ret = -E_NO_MEM;
                goto bad_cleanup_mmap;
            }
            off = start - la, size = PGSIZE - off, la += PGSIZE;
            if (end < la) {
                size -= la - end;
            }
            memset(page2kva(page) + off, 0, size);
            start += size;
        }
    }
    sysfile_close(fd);
    //(4)建立相应的虚拟内存映射表
    vm_flags = VM_READ | VM_WRITE | VM_STACK;//建立虚拟地址与物理地址之间的映射
    if ((ret = mm_map(mm, USTACKTOP - USTACKSIZE, USTACKSIZE, vm_flags, NULL)) != 0) {
        goto bad_cleanup_mmap;
    }
    assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-PGSIZE , PTE_USER) != NULL);
    assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-2*PGSIZE , PTE_USER) != NULL);
    assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-3*PGSIZE , PTE_USER) != NULL);
    assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-4*PGSIZE , PTE_USER) != NULL);
    //(5)设置用户栈
    mm_count_inc(mm);
    current->mm = mm;
    current->cr3 = PADDR(mm->pgdir);
    lcr3(PADDR(mm->pgdir));
    //(6)处理用户栈中传入的参数，其中argc对应参数个数，uargv[]对应参数的具体内容的地址
    uint32_t argv_size=0, i;
    for (i = 0; i < argc; i ++) {
        argv_size += strnlen(kargv[i],EXEC_MAX_ARG_LEN + 1)+1;
    }
    uintptr_t stacktop = USTACKTOP - (argv_size/sizeof(long)+1)*sizeof(long);
    char** uargv=(char **)(stacktop  - argc * sizeof(char *));
    argv_size = 0;
    for (i = 0; i < argc; i ++) {
        uargv[i] = strcpy((char *)(stacktop + argv_size ), kargv[i]);
        argv_size +=  strnlen(kargv[i],EXEC_MAX_ARG_LEN + 1)+1;
    }
    
    stacktop = (uintptr_t)uargv - sizeof(int);
    *(int *)stacktop = argc;
    //(7)设置进程的中断帧 
    struct trapframe *tf = current->tf;
    memset(tf, 0, sizeof(struct trapframe));
    tf->tf_cs = USER_CS;
    tf->tf_ds = tf->tf_es = tf->tf_ss = USER_DS;
    tf->tf_esp = stacktop;
    tf->tf_eip = elf->e_entry;
    tf->tf_eflags = FL_IF;
    ret = 0;
    //(8)错误处理部分
out:
    return ret;
bad_cleanup_mmap:
    exit_mmap(mm);
bad_elf_cleanup_pgdir:
    put_pgdir(mm);
bad_pgdir_cleanup_mm:
    mm_destroy(mm);
bad_mm:
    goto out;
}

实验结果

ls
 @ is  [directory] 2(hlinks) 23(blocks) 5888(bytes) : @'.'
   [d]   2(h)       23(b)     5888(s)   .
   [d]   2(h)       23(b)     5888(s)   ..
   [-]   1(h)       10(b)    40383(s)   softint
   [-]   1(h)       11(b)    44571(s)   priority
   [-]   1(h)       11(b)    44584(s)   matrix
   [-]   1(h)       10(b)    40391(s)   faultreadkernel
   [-]   1(h)       10(b)    40381(s)   hello
   [-]   1(h)       10(b)    40382(s)   badarg
   [-]   1(h)       10(b)    40404(s)   sleep
   [-]   1(h)       11(b)    44694(s)   sh
   [-]   1(h)       10(b)    40380(s)   spin
   [-]   1(h)       11(b)    44640(s)   ls
   [-]   1(h)       10(b)    40386(s)   badsegment
   [-]   1(h)       10(b)    40435(s)   forktree
   [-]   1(h)       10(b)    40410(s)   forktest
   [-]   1(h)       10(b)    40516(s)   waitkill
   [-]   1(h)       10(b)    40404(s)   divzero
   [-]   1(h)       10(b)    40381(s)   pgdir
   [-]   1(h)       10(b)    40385(s)   sleepkill
   [-]   1(h)       10(b)    40408(s)   testbss
   [-]   1(h)       10(b)    40381(s)   yield
   [-]   1(h)       10(b)    40406(s)   exit
   [-]   1(h)       10(b)    40385(s)   faultread
lsdir: step 4
$ hello
Hello world!!.
I am process 14.
hello pass.

思考题

在实验报告中给出设计实现基于”UNIX的硬链接和软链接机制“的概要设方案，鼓励给出详细设计方案

1. 硬链接机制的设计实现：
   vfs中预留了硬链接的实现接口int vfs_link(char *old_path, char *new_path);。在实现硬链接机制，创建硬链接link时，为new_path创建对应的file，并把其inode指向old_path所对应的inode，inode的引用计数加1。在unlink时将引用计数减去1即可。
2. 软链接机制的设计实现：
   vfs中预留了软链接的实现接口int vfs_symlink(char *old_path, char *new_path);。在实现软链接机制，创建软连接link时，创建一个新的文件（inode不同），并把old_path的内容存放到文件的内容中去，给该文件保存在磁盘上时disk_inode类型为SFS_TYPE_LINK，再完善对于该类型inode的操作即可。unlink时类似于删除一个普通的文件。

和实验参考答案的对比分析。

在lab8_result中make grade之后发现得分是0，sfs_inode.c函数基本相同；而对比proc.c中的函数，发现有以下几处区别

init_main()函数

参考答案中在cprintf("init check memory pass.\n");之前多了如下两行：

    assert(nr_free_pages_store == nr_free_pages());
    assert(kernel_allocated_store == kallocated());

经过验证，这两句会导致一些用户进程无法正常输出"init check memory pass."导致result错误。

函数的命名

我自己的lab7中的copy_files()和put_files()函数在参考答案中分别被命名为copy_fs()和put_fs()函数。
另外，我还猜想参考答案没有满分的原因是，前几次实验的代码在“迁移”的过程中可能产生了错误或者没有完全“迁移”过来。

知识点的分析

考察了基本的文件系统系统调用的实现方法，和基于索引节点组织方式的Simple FS文件系统的设计与实现，以及文件系统抽象层-VFS的设计与实现。前者的考察是基于分析理解，后两者则是需要具体实现。

知识点的补充

对于知识点的考察挺全面的，没有需要补充的地方。