chapter6 练习
====================

- 本节难度： **大魔王！！** 

本章任务
--------------------

.. tabs::

    .. group-tab:: Rust

        - 在 os 目录下 ``make run TEST=1`` 加载所有测例，``test_usertest`` 打包了所有你需要通过的测例，你也可以通过修改这个文件调整本地测试的内容。
        - 你的内核必须前向兼容，能通过前一章的所有测例。
        - 结合代码、指导书已经课堂所学，理解文件系统的几个概念：全局文件表 / 进程文件描述符等
        - 完成本章编程作业。
        - 最终，完成实验报告并 push 你的 ch6 分支到远程仓库。

    .. group-tab:: C

        - ``ch6b_usertest`` ``ch6_mergetest``
        - 结合代码、指导书已经课堂所学，理解文件系统的几个概念：全局文件表 / 进程文件描述符等
        - 完成本章编程作业。
        - 最终，完成实验报告并 push 你的 ch6 分支到远程仓库。

编程作业
--------------------

进程通信：邮箱
++++++++++++++++++++

这一章我们实现了基于 pipe 的进程间通信，但是看测例就知道了，管道不太自由，我们来实现一套乍一看更靠谱的通信 syscall吧！本节要求实现邮箱机制，以及对应的 syscall。

- 邮箱说明：每个进程拥有唯一一个邮箱，基于“数据报”收发字节信息，利用环形 buffer 存储，读写顺序为 FIFO，不记录来源进程。每次读写单位必须为一个报文，如果用于接收的缓冲区长度不够，舍弃超出的部分 (截断报文) 。为了简单，邮箱中最多拥有 16 条报文，每条报文最大长度 256 字节。当邮箱满时，发送邮件 (也就是写邮箱会失败) 。不考虑读写邮箱的权限，也就是所有进程都能够随意给其他进程的邮箱发报。

**mailread**:

    * syscall ID：401
    * C接口： ``int mailread(void* buf, int len)``
    * Rust接口：``fn mailread(buf: *mut u8, len: usize)``
    * 功能：读取一个报文，如果成功返回报文长度.
    * 参数：
        * buf：缓冲区头。
        * len：缓冲区长度。
    * 说明：
        * len > 256 按 256 处理，len < 队首报文长度且不为 0，则截断报文。
        * len = 0，则不进行读取，如果没有报文读取，返回 -1，否则返回 0，这是用来测试是否有报文可读。
    * 可能的错误：
        * 邮箱空。
        * buf 无效。

**mailwrite**:

    * syscall ID：402
    * C接口：``int mailwrite(int pid, void* buf, int len)``
    * Rust接口：``fn mailwrite(pid: usize, buf: *mut u8, len: usize)``
    * 功能：向对应进程邮箱插入一条报文.
    * 参数：
        * pid: 目标进程id。
        * buf: 缓冲区头。
        * len：缓冲区长度。
    * 说明：
        * len > 256 按 256 处理，
        * len = 0，则不进行写入，如果邮箱满，返回 -1，否则返回 0，这是用来测试是否可以发报。
        * 可以向自己的邮箱写入报文。
    * 可能的错误：
        * 邮箱满。
        * buf 无效。
  
实现完成之后，你应该能通过 mail* 对应的所有测例，在 shell 中执行 usertest 来执行所有测试。

.. hint::

    - 给每个进程默认分配一个邮箱即可。
    - 邮箱的具体实现就是一个 ring buffer。


[挑战，不占分] 进程通信：共享内存
++++++++++++++++++++++++++++++++++++++++

.. note::

    本来这才是本次实验的内容，大家觉得太难了，把它毙掉了。
    
    如果你认为邮箱不够炫酷，可以试试这个。挑战内容，不占分，但你还是必须先实现 mail。

进程间通信 (IPC) 对于某些系统和应用其实十分重要，它被称为微内核的 Achilles tendon，同时在 android 应用中也十分常见，为此 android 系统专门设计了一套 binder 机制来加速 IPC 的效率。

最基础的 IPC 方式大致分两类：

- 内核拷贝：指通过内核完成数据的拷贝，比如 pipe，邮箱。
- 共享内存：直接将同一段物理内存映射到不同进程的虚存空间。

其中内核拷贝的方式一般效率较低，但安全可靠，容易同步。而共享内存的方式不需要内核参与，速度较快，但需要用户态自己想办法同步，同时可能会导致某些攻击，感兴趣的同学可以参考 `TOCTTOU <https://en.wikipedia.org/wiki/TOCTTOU>`_ 。

框架实现的 pipe 属于第一类，那么现在我们来实现第二类。实现 share memory 的方法不止一种，这里我们拓展 ch4 实现的 mmap 的功能，请你在 ch4 的基础上，利用 ch6 新增加或修改的接口，修改 mmap 实现共享内存的申请。

mmap 系统调用新定义：

- syscall ID: 222
- C接口：``int mmap(void* start, unsigned long long len, int port, int flag, int shmem_id)``
- Rust 接口：``fn mmap(start: usize, len: usize, prot: usize, flag: usize, shmem_id: isize) -> i32``
- 功能：当 flag 等于 0 时，功能与 ch4 时一致；当 flag = 1 时，视为申请共享内存 (可类比 posix 接口的 MAP_SHARED 标志) ，这时需要根据 shmem_id 将对应的物理内存映射到 start 开始的虚存，内存页的属性为 prot。若此时 shmem_id 为 -1 时，视为需要申请一段新的物理内存作为共享内存使用; 若 shmem_id != -1，视作申请对应 id 的共享内存。
- 参数：
    - start：需要映射的虚存起始地址。
    - len：映射字节长度，可以为 0 (如果是则直接返回) ，不可过大 (上限 1GiB)。
    - port：第 0 位表示是否可读，第 1 位表示是否可写，第 2 位表示是否可执行。其他位无效 (必须为 0)。
    - flag：申请内存的模式，为 0 时为申请物理内存，为 1 时为申请共享内存，其他值视作错误。
    - shmem_id：申请共享内存时使用，表示内核记录的一段共享内存的 id，该 id 全内核唯一 (注意和 fd 的区别，fd 是 process 的属性, shmem_id 是全内核的属性)。
- 返回值: 
    - 若发生错误，返回 -1。
    - 若 flag == 0，返回值同 ch4。
    - 若 flag == 1，总返回映射的 shmem_id。
- 说明：
    - 我们尚未有完整文件系统，所以这只是一个看上去像 posix 的 mmap 但实际不是的系统调用。
    - 我们不定义共享内存与 fork 的相互作用，不会加以测试，任何实现都可以。
    - 允许同一个进程将同一块共享内存映射到自己的不同虚存。
    - 为了简单，addr 要求按页对齐 (否则报错)，len 可直接按页上取整。
    - 为了简单，不考虑发生错误时的页回收 (也就是内存泄漏) 。
- 错误：
    - [addr, addr + len) 存在已经被映射的页。
    - 物理内存不足。
    - port & !0x7 != 0 (port 其余位必须为0)。
    - port & 0x7 = 0 (这样的内存无意义)。
    - flag & ~0x1 != 0 (flag 应为 0 或 1)
    - shmem_id 无效。

munmap 系统调用定义：

- syscall ID：215
- C接口： ``int munmap(void* start, unsigned long long len)``
- Rust接口： ``fn munmap(start: usize, len: usize) -> i32``
- 功能：取消一块虚存的映射。
- 参数：同 mmap
- 说明：
    - 为了简单，参数错误时不考虑内存的恢复和回收。
- 错误：
    - [start, start + len) 中存在未被映射的虚存。

正确实现后，你的 os 应该能够正确运行 shmem* 对应的一些测试用例，在 shell 中执行 usertest1 来执行测试。

.. note::

    - QAQ，shmem 的企划被老师以太难为由毙掉了，所以就成了 challange...
    - 难受啊，这个唯一一个测例和参考实现都写好了的 challange ...


问答作业
--------------------

1. 举出使用 pipe 的一个实际应用的例子。

.. hint::

    - 想想你平时咋使用 linux terminal 的？
    - 如何使用 `cat <https://man7.org/linux/man-pages/man1/cat.1.html>`_ 和 `wc <https://man7.org/linux/man-pages/man1/wc.1.html>`_ 完成一个文件的行数统计？

2. 共享内存的测例中有如下C语言片段(伪代码)：

    .. code-block:: c 

        int main()
        {
            uint64 *A = (void *)0x10000000;
            uint64 *B = (void *)(0x10000000 + 0x1000);
            uint64 len = 0x1000;
            make_shmem(A, B, len); // 会将 [A, A + len) [B, B + len) 这两段虚存映射到同一段物理内存
            *A = 0xabab;
            __sync_synchronize();  // 这是什么？
            if(*B != 0xabab) {
                return ERROR;
            }
            printf("OK!");
            return 0;
        }

    请自己查阅注释 ``__sync_synchronize`` 对应的这一行代码有什么作用？如果去掉有可能会导致什么错误？为什么？

报告要求
--------------------

注意目录要求，报告命名 ``lab4.pdf``，位于 ``reports`` 目录下。 后续实验同理。

报告内容：

- [暂未支持] ``lab4.pdf`` CI 网站提交，注明姓名学号。 
- 注意目录要求，报告命名 ``lab4.md`` 或 ``lab4.pdf``，位于 ``reports`` 目录下。命名错误视作没有提交。不需要删除 ``lab1.md/pdf`` ``lab2.md/pdf`` ``lab3.md/pdf``。后续实验同理。
- 简单总结你实现的功能（200字以内，不要贴代码）。
- 完成 ch6 问答作业。
- [可选，不占分] 你对本次实验设计及难度的看法。