c++ 的高性能内存池

一般，使用malloc free和 new delete来动态管理内存，因为牵扯到系统调用，因此效率很低。内存池的思想就是使用很少的系统调用，申请一大块内存自己管理。内存池向系统申请大块内存，然后再分为小片给程序使用，每次请求内存，起始都是在内存池里拿内存而非通过系统调用。（线程池和对象池有着类似的思想）。内存池的优点：

• 原理上比malloc和new快
• 分配内存时不存在开销（overhead）
• 几乎不存在内存碎片（为什么？？？）
• 无需一个个释放对象，只需要释放内存池即可

缺点：

• 需要知道分配对象的大小
• 需要根据应用的情况来调节

1
2
3
4
5
6

/*******
* 赋值 *
*******/
//  使用 = delete 禁用拷贝赋值，只保留移动赋值
MemoryPool& operator=(const MemoryPool& mp) = delete;
MemoryPool& operator=(const MemoryPool&& mp) noexcept;

1
2

// static_assert: 编译期断言检查
static_assert(BlockSize >= 2 * sizeof(Slot_), "BlockSize too small.")

每个slot作为一个块

1
2
3
4

union Slot_ {
      value_type element;
      Slot_* next;
    };

一个奇怪的构造函数

1
2
3
4
5
6
7
8
9

// MemoryPool.h
MemoryPool(const MemoryPool& mp) noexcept; // 拷贝构造函数

// MemoryPool.cpp
template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool(const MemoryPool& mp) noexcept: MemoryPool() {}

// 推测其意思就是调用无参数构造函数。
// 可是明明走的是拷贝构造函数

析构函数中的强制类型转换

1
2
3
4
5
6
7
8
9
10
11

template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::~MemoryPool()
noexcept
{
  slot_pointer_ curr = currentBlock_;
  while (curr != nullptr) {
    slot_pointer_ prev = curr->next;
    operator delete(reinterpret_cast<void*>(curr));
    curr = prev;
  }
}

1
2
3
4

Slot_ *currentBlock_;
Slot_ *currentSlot_;
Slot_ *lastSlot_;
Slot_ *freeSlots_;

内存池拥有四个指针，freeSlots应该就是空闲slot

一个内存池MemoryAlloc包含若干个block块，空闲内存块通过链表的形式记录，block内以slot呈现。

首先我们使用 typedef 定义了某个东西成为了 allocator，这是毫无疑问的，而这个东西却是：

1

typename Alloc::template rebind<Node>::other

它长得很奇怪，这其实是为了解决让编译器不认识代码的问题而出现的写法（语法）。

首先我们定义了 Alloc = std::allocator<T>，而 rebind 其实是 std::allocator 的一个成员。巧就巧在，rebind 本身又是另一个模板， C++ 称其为 dependent name。完整的形式本来应该是：

1

std::allocator<T>::rebind<Node>::other

但是模板的相关解析已经在 <T> 出现过了，后面的 <Node> 中的 < 只能被解释为小于符号，这会导致编译出错。为了表示 dependent name 是一个模板，就必须使用 template 前缀。如果没有 template 前缀，< 会被编译器解释为小于符号。所以，我们必须写成下面的形式：

1

std::allocator<T>::template rebind<Node>::other

最后，编译器在其实根本没有任何办法来区分 other 究竟是一个类型，还是一个成员。但我们其实知道 other 是一个类型，所以使用 typename 来明确指出这是一个类型，最终才有了：

1

typename std::allocator<T>::template rebind<Node>::other

四个文件

memory_pool

​ |– MemoryPool.h

​ |– MemoryPool.cpp

​ |– StackAlloc.h

​ |– Test.cpp

MemoryPool.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

//
// Created by 张庆 on 2022/7/22.
//

#ifndef TINY_RECORD_MEMORYPOOL_H
#define TINY_RECORD_MEMORYPOOL_H

#pragma once
#include <cstddef>  // for size_t
#include <cstdint>  // for uintptr_t
#include <utility>  // for std::swap, std::forward

template <typename T, size_t BlockSize = 4096> class MemoryPool {
public:
    template<typename U>
    struct rebind{  // 结构体 rebind
        typedef MemoryPool<U> other;
    };

    /***********************
     * T 类型的构造和析构
     * ********************/
    // 内存池的构造和析构
    MemoryPool() noexcept;  // 构造函数
    MemoryPool(const MemoryPool &mem) noexcept;  // 拷贝构造
    MemoryPool(MemoryPool &&mem) noexcept;  // 移动构造

    // 拷贝构造函数,以另一个类型为模板 MemoryPool<U>
    template <typename U>
    MemoryPool(const MemoryPool<U> &mem) noexcept;

    // 析构函数
    ~MemoryPool() noexcept;


    // 赋值，禁用拷贝赋值，只保留移动赋值
    // 我猜测拷贝复制对于内存池而言会出现和c++ string使用cow一样的问题
    MemoryPool &operator = (const MemoryPool &mem) = delete;
    MemoryPool &operator = (MemoryPool &&mem) noexcept;

    // 获取元素的地址
    // 返回引用类型变量地址
    inline T *address(T &element) const noexcept{return  &element;} // 括号后的const不可修改函数内的内容
    // 返回常量引用类型变量地址
    inline const T *address(const T &element) const noexcept{return &element;}


    /***********************
     * Allocator
     * ********************/
    /** 拥有四个接口
       1. 从内存池为对象分配内存
       2. 从内存池为对象释放内存a
       3. 构造和析构对象
       4. new与delete
     **/

    /***********************
     * 从内存池为对象分配内存
     * ********************/
    // 分配足够的存储空间来存储T的n个对象实例
    // hint 是建议地址，没有特别需求设为0。
    // 函数会返回一个实际map的地址
    inline T *allocate(size_t n = 1, const T *hint = nullptr){
        // 有freeSLot_，那么可以直接往后使用
        if(freeSlot_ !=nullptr){
            T *result = reinterpret_cast<T *>(freeSlot_); // 指针的一个强制转换
            freeSlot_ = freeSlot_->next;
            return result;
        }else{  // do not have freeSlot_
            // freeSlot_还未初始化或者已经用完
            if(currentSlot_ >= lastSlot_){  // 耗尽
                allocateBlock();
            }
            return reinterpret_cast<T *>(currentSlot_++);
        }
    }


    /***********************
     * 从内存池为对象释放内存
     * ********************/
    inline void deallocate(T *p, size_t n = 1){  // n是对象个数
        // TODO：解决？？？ 只释放了一个SLot. Block貌似就是一个对象
        if(p != nullptr){
            // freeSlot 头插法建立
            // 释放的链表头插法进去，如果freeSlot_目前是A->B->C, 释放了个X，那么变为X->A->B->C
            reinterpret_cast<Slot_ *>(p)->next = freeSlot_;
            freeSlot_ = reinterpret_cast<Slot_ *>(p);
        }
    }


    /***********************
     * 构造与析构对象
     * ********************/
     // 使用p指向的args参数构造一个对象
    template<typename U, typename... Args>
    inline void construct(U* p, Args &&... args){
        new (p) U(std::forward<Args>(args)...);
        // 在p指向的内存，用给定模板参数列表（转发、解包）新建一个U类型的对象
    }

    // 调用p指向的对象的析构函数
    template<typename U>
    inline void destroy(U *p){
        p->~U();
    }


    /***********************
     * new 与 delete
     * ********************/
    template<typename... Args>  // 变参模板
    inline T *newElement(Args &&... args){
        T *result = allocate();
        construct(result, std::forward<Args>(args)...);
        // std::forward的模板参数必须是<Args>,而不能是<Args...>
        // 这是由于我们不能对Args进行解包之后传递给std::forward
        return result;
    }

    inline void deleteElement(T *p){
        if(p != nullptr){  // p指向的对象不为空
            p->~T();  // 对象析构
            deallocate(p);  // 释放指针
        }
    }

    /***********************
     * 最多能容纳多少个对象
     * ********************/
    inline size_t max_size() const noexcept{
        // -1 表示当前能寻址的最大内存地址
        size_t max_Block = -1/BlockSize;
        // 每个Block能容纳T的个数
        size_t max_T = (BlockSize - sizeof(char *))/sizeof(Slot_);
        return max_Block*max_T;
    }

private:
    union Slot_{
        T element;
        Slot_ *next;
    };

    Slot_ *currentBlock_;
    Slot_ *currentSlot_;
    Slot_ *lastSlot_;
    Slot_ *freeSlot_;

    void allocateBlock();

    /***********************
     * 对齐align
     * ********************/
     // uintptr_t是可以容纳指针大小的integer type，
     // 但是size_t不一定是，在一些具有分段寻址机制的平台，size_t可能比一个指针的大小还小。
     // padding代表需要往后移多少个位置，才能按照align的大小进行对齐
     // 比如  2  4， 那么还需要后移2个位置
     inline size_t padPointer(char* p, size_t align) const noexcept{
         uintptr_t addr = reinterpret_cast<uintptr_t>(p);
         size_t padding = (align - addr) % align;
         // 测试一下，开源代码给的测试用例
         // printf("addr = %08lx\n, align = %02lx, and padding = %02lx\n", addr, align, padding);
         return padding;
     }

     // 编译期断言检查
    static_assert(BlockSize >= 2*sizeof(Slot_),"static_assert: Block is too small!");
};








#endif //TINY_RECORD_MEMORYPOOL_H

MemoryPool.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

//
// Created by 张庆 on 2022/7/22.
//
#include "MemoryPool.h"
using namespace std;

// 默认构造函数
template<typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool() noexcept{
    currentBlock_ = nullptr;
    currentSlot_ = nullptr;
    lastSlot_ = nullptr;
    freeSlot_ = nullptr;
}

// 拷贝构造函数
template<typename T, size_t BlockSize>
MemoryPool< T, BlockSize>::MemoryPool(const MemoryPool &mem) noexcept
        :MemoryPool() {}
        // TODO: // 为什么调用无参数构造函数???

// 拷贝构造
template<typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool(MemoryPool &&mem) noexcept{
currentBlock_ = mem.currentBlock_;
mem.currentBlock_ = nullptr;  //  释放之前的block指针
currentSlot_ = mem.currentSlot_;
lastSlot_ = mem.lastSlot_;
freeSlot_ = mem.freeSlot_;
}

// 另一个类型U
template<typename T, size_t BlockSize>
template<typename U>
MemoryPool< T, BlockSize>::MemoryPool(const MemoryPool<U> &mem) noexcept
        :MemoryPool() {}

// 析构一个Block
template<typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::~MemoryPool() noexcept {
    Slot_ * cur = currentBlock_;
    while(cur !=nullptr){
        Slot_ *nxt = cur->next;
        ::operator delete(reinterpret_cast<void *>(cur));
        cur = nxt;
    }
}

// 移动赋值
// 拷贝赋值已经被delete， 即禁用
// 重载operator=
template<typename T, size_t BlockSize>
MemoryPool<T, BlockSize> &MemoryPool<T, BlockSize>::
operator=(MemoryPool &&mem) noexcept {
    if(this != &mem){  // 若不是给自己赋值
        // 交换第一块Block的位置
        // swap内部也是移动赋值机制，确保了不会有多个指针指向一块空间
        // 这样不会出现一块空间被重复释放的问题
       std::swap(currentBlock_, mem.currentBlock_);
       currentSlot_ = mem.currentSlot_;
       lastSlot_ = mem.lastSlot_;
       freeSlot_ = mem.freeSlot_;
    }
    return *this; // 对象
}

// 为内存池分配内存
// allocateBlock()
template<typename T, size_t BlockSize>
void MemoryPool<T, BlockSize>::allocateBlock() {
    // Block 也按照头插法建立
    char *newBlock = reinterpret_cast<char *>(::operator new(BlockSize));
    reinterpret_cast<Slot_ *>(newBlock)->next = currentBlock_; // 头插
    currentBlock_ = reinterpret_cast<Slot_ *>(newBlock);
    // 需要做一个内存对齐，因为第一个指针指向Block，而不是Slot_
    // 第一个指针之后的都是Slot_
    char *curPoint = newBlock + sizeof(Slot_ *);
    // alignof(type)将指定类型的对齐方式返回为类型的值 size_t
    size_t padding = padPointer(curPoint, alignof(Slot_));
    currentSlot_ = reinterpret_cast<Slot_ *>(curPoint + padding);
    lastSlot_ = reinterpret_cast<Slot_ *>(newBlock + BlockSize - sizeof(Slot_) + 1);
}

StackAlloc.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

//
// Created by 张庆 on 2022/7/22.
//

#ifndef TINY_RECORD_STACKALLOC_H
#define TINY_RECORD_STACKALLOC_H

#include <memory>

/**
 * 实现堆栈结构的模板类
 * 使用allocator_traits(specifically with MemoryPool)
 * **/

template<typename T>
struct StackNode_{
    T data;
    StackNode_* prev;
};

/**
 * T 是存储在stack中的对象，alloc 是所使用的allocator
 * **/
template<typename T, typename alloc = std::allocator<T>>
class StackAlloc {
public:
    typedef StackNode_<T> node;
    // rebind 是 std::allocator的一个成员
    // rebind本身就是另一个模板， 形式类似于 std::allocator<T>::rebind<Node>::other
    // template 是为了说明other是个类型，而不是一个成员
    typedef typename alloc::template rebind<node>::other allocator;

    /** 构造函数 **/
    StackAlloc(){head_ = 0;}

    /** 析构函数 **/
    ~StackAlloc(){clear();}

    /** 当前栈是否为空 */
    bool isEmpty(){
        return (head_ == 0);
    }

    /** 清除所有元素，stack清空 **/
    void clear(){  // T is an object
        node* cur = head_;
        while(cur!=0){
            node* temp = cur->prev;
            allocator_.destroy(cur);
            allocator_.deallocate(cur,1);
            cur = temp;
        }
        head_ = 0;
    }


    /** put an element on the top of the stack*/
    // element is an object
    void push(T element){
        node* newEle = allocator_.allocate(1); // 分配一个新的Slot_
        allocator_.construct(newEle, node()); // inline void construct(U* p, Args&&... args){
        newEle->data = element;
        newEle->prev = head_;
        head_ = newEle;
    }

    T top(){
        return head_->data;
    }
    /** 移除顶端元素,返回对象 */
    T pop(){
        node* cur = head_->prev;
        T cur_ele = head_->data;
        allocator_.destroy(head_);
        allocator_.deallocate(head_,1);
        head_ = cur;
        return cur_ele;
    }

private:
    allocator allocator_;
    node* head_;
};


#endif //TINY_RECORD_STACKALLOC_H

Test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

//
// Created by 张庆 on 2022/7/22.
//

#include <iostream>
#include <cassert>
#include <time.h>
#include <vector>

#include "MemoryPool.cpp"
#include "StackAlloc.h"


#define MAXELES 100000
#define REPS 50

using namespace std;


int main(){
    /*****************
     *
     * use default allocator
     *
     * ***************/
    cout<< "======Use default allocator======"<<endl;
    clock_t start;

    // 使用 StackAlloc, 此时allocator为默认allocator<int>
    StackAlloc<int, std::allocator<int>> stackDefault;

    start = clock();
    for(int i = 0;i<REPS;++i){
        assert(stackDefault.isEmpty());   // 为0则中断
        for(int j = 0;j<MAXELES/4;++j){
            stackDefault.push(j);
            stackDefault.push(j);
            stackDefault.push(j);
            stackDefault.push(j);
        }

        for(int j = 0;j<MAXELES/4;++j){
            stackDefault.pop();
            stackDefault.pop();
            stackDefault.pop();
            stackDefault.pop();
        }
    }

    cout<<"default allocator time: ";
    cout<< ((double)(clock() - start)/CLOCKS_PER_SEC) <<endl;


    /*****************
     *
     * use MemoryPool
     *
     * ***************/
    cout<< "======Use MemoryPool======"<<endl;
    StackAlloc<int, MemoryPool<int>> stackWithMem;

    start = clock();
    for(int i = 0;i<REPS;++i){
        assert(stackWithMem.isEmpty());   // 为0则中断
        for(int j = 0;j<MAXELES/4;++j){
            stackWithMem.push(j);
            stackWithMem.push(j);
            stackWithMem.push(j);
            stackWithMem.push(j);
        }

        for(int j = 0;j<MAXELES/4;++j){
            stackWithMem.pop();
            stackWithMem.pop();
            stackWithMem.pop();
            stackWithMem.pop();
        }
    }

    cout<<"default allocator time: ";
    cout<< ((double)(clock() - start)/CLOCKS_PER_SEC) <<endl;


    /**
     * 用动态数组vector代替stack
     * */
    cout<< "======Use vector======"<<endl;
    std::vector<int> vec;
    start = clock();

    for(int i = 0;i<REPS;++i){
        assert(vec.empty());   // 为0则中断
        for(int j = 0;j<MAXELES/4;++j){
            vec.push_back(j);
            vec.push_back(j);
            vec.push_back(j);
            vec.push_back(j);
        }

        for(int j = 0;j<MAXELES/4;++j){
            vec.pop_back();
            vec.pop_back();
            vec.pop_back();
            vec.pop_back();
        }
    }

    cout<<"vector time: ";
    cout<< ((double)(clock() - start)/CLOCKS_PER_SEC) <<endl;
    return 0;
}

Network Driver (default final project)

Lab 6 Network Driver

网卡基于E1000芯片

除了编写驱动之外，还需要创建一个 system call 来访问我们的驱动程序。我们将实现缺失的网络服务器代码，以在网络堆栈和驱动程序之间传输数据包。我们还可以通过完成web服务器将所有内容绑定在一起。使用新的web服务器，我们能够从文件系统中提供文件。

没有框架文件，没有固定的系统调用接口，许多设计决策都留给您。

QEMU’s virtual network

QEMU是一个模拟处理器软件，默认提供一个运行在IP 10.0.2.2 上的虚拟路由，并为JOS分配IP 10.0.2.15 ，为了解决内网连接问题，host无法运行在QEMU上的web server，我们配置QEMU在主机某个端口上运行服务。该端口只需连接到JOS中的某个端口，并在真实主机和虚拟网络之间来回传送数据。

echo server是回显服务,用户输入什么,服务器将输入信息返回给客户端。

webserver 是指驻留于因特网上某种类型计算机的程序。当Web浏览器（客户端）连到服务器上并请求文件时，服务器将处理该请求并将文件反馈到该浏览器上，附带的信息会告诉浏览器如何查看该文件（即文件类型）。服务器使用HTTP（超文本传输协议）与客户机浏览器进行信息交流，这就是人们常把它们称为HTTP服务器的原因。目前最主流的三个Web服务器是Apache Nginx IIS。

Packet Inspection

Makefile 配置了QEMU的网络栈，将进出的网络包记录到 qemu.pcap中。我们可以使用图形化的 wireshark，或是使用命令行获得网络包的hex/ASCII信息。

1

tcpdump -XXnr qemu.pcap

Debugging the E1000

The E1000 can produce a lot of debug output, so you have to enable specific logging channels. Some channels you might find useful are:

To enable “tx” and “txerr” logging, for example, use make E1000_DEBUG=tx,txerr ….

The Network Server

从零开始写一个网络栈是十分困难的，因此我们使用lwIP， 其是一个开源的轻量级TCP/IP协议套件，其中包含网络栈。

网络服务器实际上是四个环境的组合:

• 核心网络服务器环境(包括套接字调用调度程序和lwIP)

• 输入环境

• 输出环境

• 计时器的环境

我们将实现图中标记为绿色的部分。

The Core Network Server Environment

Socket是应用层与TCP/IP协议族通信的中间软件抽象层，它是一组接口。在设计模式中，Socket其实就是一个门面模式，它把复杂的TCP/IP协议族隐藏在Socket接口后面，对用户来说，一组简单的接口就是全部，让Socket去组织数据，以符合指定的协议。

For each user environment IPC, the dispatcher in the network server calls the appropriate BSD socket interface function provided by lwIP on behalf of the user.

Regular user environments do not use the nsipc_* calls directly. Instead, they use the functions in lib/sockets.c, which provides a file descriptor-based sockets API.

文件服务器和网络服务器之间有一个关键的区别。像accept和recv这样的BSD套接字调用可以无限阻塞。由于这是不可接受的，网络服务器使用用户级线程来避免阻塞整个服务器环境。

除了核心网络环境之外，还有三个辅助环境。除了接收来自用户应用程序的消息外，核心网络环境的调度程序还接收来自输入环境和计时器环境的消息。

核心网络服务器环境是由所有套接字调用分发者和lwIP组成。套接字调度器和文件服务器工作类似。用户环境使用根(lib/nsipc.c
)发送IPC消息给核心网络环境。如果你查看lib/nsipc.c
，你可以看到核心网络服务器和文件服务器一样:i386_init
创建带有NS_TYPE_NS
的环境，所以我们扫描envs
，找到特殊的环境类型。对于每个用户环境IPC，网络服务器的调度器调用合适BSD套接字接口函数

常用的用户环境不使用nsipc_*
直接调用。相反，他们使用lib/sockets.c
中的函数，它提供了一个基于文件描述符的套接字API。因此，用户环境通过文件描述符指向套接字，就像指向磁盘上的文件一样。大量的操作(connect
, accept
等)是指定套接字的，但是read
, write
和close
是通过普通的文件描述符lib/fd.c
完成的。和文件服务器为所有打开的文件保留唯一ID一样，lwIP也生成唯一ID为所有打开的套接字。在文件服务器和网络服务器中，我们使用保存在struct Fd
中的信息来映射每个环境文件描述符到这些唯一ID空间

尽管文件服务器和网络服务器的IPC调度器行为一样，但是还有一个关键的区别。BSD套接字调用像accept
和recv
能无限阻塞。如果调度器允许lwIP执行阻塞调用中的一个，调度器也会阻塞，整个系统，同一个时间只有一个网络调用。因为这是不能接受的，所以网络服务器使用用户级别的线程来避免阻塞整个服务环境。对于每个到达的IPC消息，调度器创建一个线程，在线程中处理请求。如果线程阻塞，只有那个线程进入休眠，其他线程会继续执行

除了核心网络环境之外，也有三个辅助环境，除了从用户程序接收消息，核心网络环境调度器也从输入和时间环境接收消息

输出环境

当正在服务用户环境的套接字调用时，lwIP会为网卡生成包数据.lwIP发送每个包给输出辅助环境，使用NSREQ_OUTPUT
的IPC消息，包数据会在IPC的页参数带上。输出环境负责接收这些消息，通过你创建的系统调用接口分发给设备驱动

输入环境

通过网卡接收到的包，需要注入到lwIP中，对于每一个设备驱动接收到的包，输入环境从内核空间拉出包(使用你需要实现的内核系统调用)，然后发送包数据到核心服务环境，使用NSREQ_INPUT
的IPC消息

包输入功能与核心网络环境分离，因为JOS很难同时接收IPC消息，同时轮询或等待设备驱动数据包也很困难。在JOS中，我们没有select
系统调用，这个系统调用可以监听多个输入源来区分哪个输入准备进行了

如果你阅读过net/input.c
和net/output.c
，你会发现这两个都需要你实现。这是主要的，因为实现决定了系统调用接口。在你实现了驱动和系统调用接口之后，你需要为两个辅助环境编写代码

定时器环境

定时器环境周期性发送NSREQ_TIMER
类型消息给核心网络服务器，通知一个定时器已经过期了。来自线程的定时器消息被lwIP用来实现各种各样的网络超时

Part A: Initialization and transmitting packets 实现和转发包(报文)

你的内核代码没有时间概念，所以你需要添加。现在有时钟中断，这是由硬件每10ms生成的。每个时钟中断，我们可以递增变量来表明时间已经提前了10ms。这个实现在kern/time.c
，但是没有植入到你的内核中

我们需要为我们的内核添加时间概念。使用时钟中断，并用一个变量进行计数。

Add a call to time_tick for every clock interrupt in kern/trap.c(in kern/time.c). Implement sys_time_msec and add it to syscall in kern/syscall.c so that user space has access to the time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 1
// LAB 4: Your code here.
    case (IRQ_OFFSET + IRQ_TIMER):
        // 回应8259A 接收中断。
        lapic_eoi();
        time_tick();
        sched_yield();
        break;
// 2
static int
sys_time_msec(void)
{
    // LAB 6: Your code here.
    return time_msec();
    // panic("sys_time_msec not implemented");
}
// 3
case SYS_time_msec:
        return sys_time_msec();

The Network Interface Card

Browse Intel’s Software Developer’s Manual for the E1000. 本手册涵盖了几个密切相关的以太网控制器。QEMU模拟82540EM。

接收和发送描述:

数据包接收

​ 识别到网络上存在一个数据包，

​ 执行地址过滤,

​ 将数据包存储在接收数据FIFO中，

​ 将数据传输到主机内存中的接收缓冲区，

​ buffer size RCTL.BSIZE & RCTL.BSEX

​ updating the state of a receive descriptor.

​ Status

​ Errors

​ Specia

PCI Interface

PCI是外围设备互连(Peripheral Component Interconnect)的简称，是在目前计算机系统中得到广泛应用的通用总线接口标准：

在一个PCI系统中，最多可以有256根PCI总线，一般主机上只会用到其中很少的几条。
在一根PCI总线上可以连接多个物理设备，可以是一个网卡、显卡或者声卡等，最多不超过32个。
一个PCI物理设备可以有多个功能，比如同时提供视频解析和声音解析，最多可提供8个功能。
每个功能对应1个256字节的PCI配置空间

为了在引导期间执行PCI初始化，PCI代码遍历PCI总线以寻找设备。 当它找到设备时，它会读取其供应商ID和设备ID，并使用这两个值作为搜索pci_attach_vendor数组的键。 该数组由struct pci_driver条目组成，如下所示：

1
2
3
4

struct pci_driver {
    uint32_t key1, key2;
    int (*attachfn) (struct pci_func *pcif);
};

如果发现的设备的供应商ID和设备ID与数组中的条目匹配，则PCI代码会调用该条目的attachfn来执行设备初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13

struct pci_func {
    struct pci_bus *bus;

    uint32_t dev;
    uint32_t func;

    uint32_t dev_id;
    uint32_t dev_class;

    uint32_t reg_base[6];
    uint32_t reg_size[6];
    uint8_t irq_line;
};

我们重点关注struct pci_func的最后三个成员，因为它们记录了设备的negotiated memory，I/O 和中断资源。 reg_base和reg_size数组包含最多六个基址寄存器或BAR的信息。reg_base存储内存映射 I/O 区域的基地址（或 I/O 端口资源的基本 I/O 端口），reg_size包含reg_base中相应基值的大小（以字节为单位）或 I/O 端口数， 和irq_line包含分配给设备的 IRQ line 以进行中断。

pci_func_enable将会使能设备，协调资源，并将其填入struct pci_func。

Exercise 3

Implement an attach function to initialize the E1000.

查看手册以及根据内核启动时的打印信息，我们可以知道 E1000 的 Vender ID = 0x8086， Device ID = 0x100E。

Add an entry to the pci_attach_vendor array in kern/pci.c to trigger your function if a matching PCI device is found，将E1000加入数组中

1
2
3
4

struct pci_driver pci_attach_vendor[] = {
    { PCI_E1000_VENDOR_ID, PCI_E1000_DEVICE_ID, &pci_e1000_attach},
    { 0, 0, 0 },
};

编写 e1000.c and e1000.h文件。.c文件写 attach函数， 在.h 文件中定义其 PCI ID等信息。

just enable the E1000 device via pci_func_enable.

Memory-mapped I/O

软件通过 Memory-mapped I/O 与 E1000 进行通信。之前我们已经两次接触过 MMIO这个概念了，分别在 CGA控制台和 lapic。 我们通过内存地址对设备进行读写。这些以内存地址为基础的读写目标并不是 DRAM，而是设备。

pci_func_enable 为 E1000分配了一个 MMIO 区域并且在 BAR0 中存储了它的 base and size。这是分配给设备的一系列物理内存地址，这意味着我们必须通过虚拟地址访问它。 由于MMIO区域被分配了非常高的物理地址（通常高于3GB），因为JOS的256MB限制，我们无法使用KADDR（内核地址）访问它。所以我们将创建一个新的映射。我们还是使用mmio_map_region分配MMIOBASE以上的区域，其保证了我们不会修改到之前创建的 LAPIC 映射。由于PCI设备初始化发生在JOS创建用户环境之前，因此您可以在kern_pgdir中创建映射，并且它总是可用的。

Exercise 4

In your attach function, create a virtual memory mapping for the E1000’s BAR 0 by calling mmio_map_region (which you wrote in lab 4 to support memory-mapping the LAPIC).

将E1000的物理地址映射到虚拟地址，同时记录映射的虚拟地址，方便之后对 E1000 设备的访问。

1
2

// 映射，并保存其虚拟地址，方便访问。
e1000 = mmio_map_region(pcif->reg_base[0], pcif->reg_size[0]);

1
2
3
4
5
6
7
8

cprintf("device status:[%08x]\n", *(uint32_t *)((uint8_t *)e1000 + E1000_DEVICE_STATUS));
// 或者写为 e1000[E1000_DEVICE_STATUS >> 2];
#define E1000_LOCATE(offset)  (offset >> 2)
cprintf("device status:[%08x]\n", e1000[E1000_LOCATE(E1000_DEVICE_STATUS)]);

// 结果
PCI function 00:03.0 (8086:100e) enabled
device status:[80080783]

DMA

通过读写 E1000 寄存器来传输接收数据包是十分低效的做法，并且还需要E1000 缓存数据包。因此考虑到各个方面的因素，我们采用 DMA 的方式直接访问内存。驱动程序负责为发送和接收队列分配内存，设置DMA描述符，并使E1000定位到这些队列，但之后的所有内容都会变成异步的。

从抽象层来看，接收和发送队列非常相似。 两者都由一系列描述符组成。 虽然这些描述符的确切结构各不相同，但每个描述符包含一些标志和数据包数据缓冲区的物理地址（要发送的网卡的数据包数据，或者操作系统为网卡写入接收数据包而分配的缓冲区）。

Transmitting Packets

初始化要发送的网卡。传输初始化的第一步是设置传输队列。

1
2
3
4
5
6
7
8
9
10
11
12
13

/* Transmit Descriptor */
struct E1000TxDesc {
    uint64_t buffer_addr;       /* Address of the descriptor's data buffer */

    uint16_t length;    /* Data buffer length */
    uint8_t cso;        /* Checksum offset */
    uint8_t cmd;        /* Descriptor control */

    uint8_t status;     /* Descriptor status */
    uint8_t css;        /* Checksum start */
    uint16_t special;

}__attribute__((packed));

在驱动程序初始化期间为每个描述符保留数据包缓冲区的空间，并简单地将数据包数据复制到这些预分配的缓冲区中。

Exercise 5

执行第14.5节(但不是它的子节)中描述的初始化步骤。使用第13节作为初始化过程中引用的寄存器的参考，使用第3.3.3节和第3.4节作为传输描述符和传输描述符数组的参考。

在对各寄存器进行初始化时，要不断得在第13章找到其偏移地址和详细定义。最后按照要求写入地址。

我们必须将要传输的数据包添加到传输队列的尾部，这意味着需要将数据包数据复制到下一个数据包缓冲区，然后更新TDT（传输描述符尾部）寄存器以通知网卡在传输队列中有另一个数据包。[Note] TDT 是传输描述符数组的索引而不是偏移地址。

如果在发送描述符的命令字段中设置RS（Report Status）位，则当网卡在该描述符中发送了数据包时，网卡将在描述符的状态字段中设置DD（Descriptor Done）位。 如果设置了描述符的DD位，我们就能回收该描述符并使用它来传输另一个数据包。

如果用户调用传输系统调用，但下一个描述符的DD位未置位，表明传输队列已满，该怎么办？ 你必须决定在这种情况下该做什么。你可以简单地丢弃数据包。网络协议对此具有弹性，但如果丢弃大量数据包，协议可能无法恢复。我们可以告诉用户环境它必须重试，就像我们对sys_ipc_try_send所做的那样。This has the advantage of pushing back on the environment generating the data.。

Exercise 6

编写一个函数，通过检查下一个描述符是否空闲来传输一个包，将包数据复制到下一个描述符，并更新TDT。确保您处理的传输队列已满。

Exercise 7

添加一个系统调用，允许您从用户空间传输数据包。具体的界面取决于您。不要忘记检查从用户空间传递给内核的指针

Transmitting Packets: Network Server传输报文:网络服务器

既然我们已经有了 packet send 的系统调用，也是时候发送数据包了。output helper environment 运行在一个循环中：从 core network server 接收 NSREQ_OUTPUT IPC 信息，使用 system call 将伴随 IPC 发送过来的 Packet 发送到设备驱动中。 NSREQ_OUTPUT由在net/lwip/jos/jif/jif.c文件中的low_level_output 函数发送 , which glues the lwIP stack to JOS’s network system. 每个IPC 都包含一个由 union Nsipc构成的页，packet 存在于 struct kif_pkt字段。struct jif_pkt looks like：

1
2
3
4

struct jif_pkt {
    int jp_len;
    char jp_data[0];
};

在结构的末尾使用像jp_data这样的零长度数组是用于表示没有预定长度的缓冲区的常见C技巧（有些人会说是恶心）。 由于C不进行数组边界检查，只要确保结构后面有足够的未使用内存，就可以使用jp_data，就好像它是一个任意大小的数组一样。

Exercise 8

Implement net/output.c.

在/net/serv.c中创建了一个相当于守护进程output，在output 中我们需要接收 ipc， 解析信息然后调用 system call 发送数据包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void
output(envid_t ns_envid)
{
    binaryname = "ns_output";

    // LAB 6: Your code here:
    //     - read a packet from the network server
    //    - send the packet to the device driver
    uint32_t whom;
    int perm;
    int32_t req;

    while (1) {
        req = ipc_recv((envid_t *)&whom, &nsipcbuf, &perm);
        if (req != NSREQ_OUTPUT) {
            continue;
        }
        while (sys_pkt_try_send(nsipcbuf.pkt.jp_data, nsipcbuf.pkt.jp_len) < 0) {
            sys_yield();
        }
    }
}

Linux Daemon（守护进程）是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务，不是对整个系统就是对某个用户程序提供服务。Linux系统的大多数服务器就是通过守护进程实现的。常见的守护进程包括系统日志进程syslogd、 web服务器httpd、邮件服务器sendmail和数据库服务器mysqld等。

Lab 5: File system, Spawn and Shell

Introduction

In this lab, you will implement spawn, a library call that loads and runs on-disk executables. 然后，您将充实内核和库操作系统，使其足以在控制台上运行shell。这些特性需要一个文件系统，本实验室介绍了一个简单的读写文件系统。

File system preliminaries（文件系统初步）

我们要完成一个相对简单的文件系统，其可以实现创建、读、写以及删除在分层目录结构中组织的文件。目前我们的OS只支持单用户，因此我们的文件系统也不支持UNIX文件拥有或权限的概念。同时也不支持硬链接、符号链接、时间戳或是特别的设备文件。

On-Disk File System Structure

大多数UNIX文件系统将可用磁盘空间划分为两种主要类型的区域:inode区域和数据区域。UNIX文件系统为文件系统中的每个文件分配一个inode;一个文件的inode保存着关于该文件的关键元数据，比如它的属性和指向其数据块的指针。数据区域被划分为更大的数据块(通常为8KB或更多)，文件系统在其中存储文件数据和目录元数据。目录项包含文件名和指向索引节点的指针;如果文件系统中的多个目录条目引用了该文件的inode，则该文件被称为硬链接文件。由于我们的文件系统不支持硬链接，我们不需要这种间接级别，因此可以进行方便的简化:我们的文件系统根本不使用inode，而只是将一个文件(或子目录)的所有元数据存储在描述该文件的(唯一的)目录条目中。

文件和目录在逻辑上都由一系列数据块组成，这些数据块可以分散在磁盘中，就像环境的虚拟地址空间的页面可以分散在物理内存中一样。文件系统环境隐藏了块布局的细节，提供了在文件中任意偏移位置读取和写入字节序列的接口。文件系统环境在内部处理对目录的所有修改，作为执行文件创建和删除等操作的一部分。我们的文件系统允许用户环境直接读取目录元数据(例如，使用read)，这意味着用户环境可以自己执行目录扫描操作(例如，实现ls程序)，而不必依赖于对文件系统的额外特殊调用。这种目录扫描方法的缺点是，它使应用程序依赖于目录元数据的格式，在不更改或至少重新编译应用程序的情况下，很难更改文件系统的内部布局，这也是大多数现代UNIX变体不鼓励使用这种方法的原因。

Sectors and Blocks

扇区是对磁盘的概念，块是对OS的概念。 块的 size 必须是扇区size 的整数倍。

Superblocks

文件系统通常在磁盘上的“易于查找”位置保留某些磁盘块（例如从最开始或最后）以保存描述文件系统属性的元数据，例如块大小 ，磁盘大小，查找根目录所需的任何元数据，上次挂载文件系统的时间，文件系统上次检查错误的时间等等。 这些特殊块称为超级块。

我们的文件系统将只有一个超级块，它始终位于磁盘上的第1块。它的布局由struct Super在inc/fs.h中定义。块0通常保留来保存引导加载程序和分区表，因此文件系统通常不使用第一个磁盘块。许多“真正的”文件系统维护多个超级块，复制到磁盘上几个间隔很宽的区域，因此，如果其中一个超级块损坏或磁盘在该区域出现了媒体错误，仍然可以找到其他超级块，并使用它们访问文件系统。

1
2
3
4
5

struct Super {
    uint32_t s_magic;        // Magic number: FS_MAGIC
    uint32_t s_nblocks;        // Total number of blocks on disk
    struct File s_root;        // Root directory node
};

Superblock, Inode, Dentry 和 File 都属于元数据(Metadata)，根据维基百科中的解释，所谓元数据，就是描述数据的数据（data about data），主要是描述数据属性（property）的信息，用来支持如指示存储位置、历史数据、资源查找、文件记录等功能。Linux/Unix 文件系统的元数据以多级结构保存。

superblock：记录此filesystem 的整体信息，包括inode[表情]ock的总量、使用量、剩余量， 以及档案系统的格式与相关信息等；
inode：记录档案的属性，一个档案占用一个inode，同时记录此档案的资料所在的block 号码；
block：实际记录档案的内容，若档案太大时，会占用多个block 。

Superblock 是文件系统最基本的元数据，它定义了文件系统的类似、大小、状态，和其他元数据结构的信息（元数据的元数据）。

File Meta-data

The layout of the meta-data describing a file in our file system is described by struct File in inc/fs.h. Unlike in most “real” file systems, for simplicity we will use this one File structure to represent file meta-data

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct File {
    char f_name[MAXNAMELEN];    // filename
    off_t f_size;            // file size in bytes
    uint32_t f_type;        // file type

    // Block pointers.
    // A block is allocated iff its value is != 0.
    uint32_t f_direct[NDIRECT];    // direct blocks
    uint32_t f_indirect;        // indirect block

    // Pad out to 256 bytes; must do arithmetic in case we're compiling
    // fsformat on a 64-bit machine.
    uint8_t f_pad[256 - MAXNAMELEN - 8 - 4*NDIRECT - 4];
} __attribute__((packed));    // required only on some 64-bit machines

Directories versus Regular Files(目录与普通文件)

我们的文件系统中的超级块包含一个 File结构，其保存了文件系统根目录的元数据。这个目录文件的内容是一系列文件结构体，其描述了文件系统根目录下的文件和目录。任何根目录下的子目录可能包含更多表示子子目录的文件结构体，以此类推。

The File System

我们实现的文件系统的关键部分是:

• 读数据到缓存中并能写回到磁盘；

• 分配磁盘块;

• 将文件偏移映射到磁盘块;

• 并在IPC接口中实现读，写和打开。

Disk Access

操作系统中的文件系统环境需要能够访问磁盘，但是我们还没有在内核中实现任何磁盘访问功能。我们没有采用传统的“单片”操作系统策略，即在内核中添加IDE磁盘驱动程序以及允许文件系统访问它的必要系统调用，而是将IDE磁盘驱动程序作为用户级文件系统环境的一部分来实现。我们仍然需要稍微修改内核，以便让文件系统环境拥有实现磁盘访问所需的权限。

只要我们依赖于轮询、基于“编程I/O”(PIO)的磁盘访问，并且不使用磁盘中断，就很容易通过这种方式在用户空间中实现磁盘访问。也可以在用户模式下实现中断驱动的设备驱动程序(例如，L3和L4内核就可以做到这一点)，但难度更大，因为内核必须字段设备中断并将它们分派到正确的用户模式环境中。

x86处理器使用EFLAGS寄存器中的IOPL位来确定是否允许保护模式代码执行特殊的设备I/O指令，如in和OUT指令。因为我们需要访问的所有IDE磁盘寄存器都位于x86的I/O空间中，而不是内存映射的，所以给文件系统环境“I/O特权”是我们唯一需要做的事情，以便允许文件系统访问这些寄存器。实际上，EFLAGS寄存器中的IOPL位为内核提供了一种简单的“全或无”方法来控制用户模式代码是否可以访问I/O空间。在我们的示例中，我们希望文件系统环境能够访问I/O空间，但是我们根本不希望任何其他环境能够访问I/O空间。

Exercise 1:

i386_init通过将类型ENV_TYPE_FS传递给环境创建函数env_create来标识文件系统环境。在env.c中修改env_create，使它赋予文件系统环境I/O权限，但不赋予任何其他环境该权限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void
env_create(uint8_t *binary, enum EnvType type)
{
   // LAB 3: Your code here.
    struct Env* e;   // 新建一个进程
    int r = env_alloc(&e, 0);
    if(r<0){
        panic("env_create: env alloc error: %e", r);
    }
    // 分配成功
    e->env_type = type;
    // 添加文件权限
    if(type == ENV_TYPE_FS){
        e->env_tf.tf_eflages |= FL_IOPL_MASK
    }
    load_icode(e, binary);
}

Question

1. Do you have to do anything else to ensure that this I/O privilege setting is saved and restored properly when you subsequently switch from one environment to another? Why?

   不需要，因为在环境切换时，会保存eflags的值，后续也会使用env_pop_tf来恢复eflags的值。

The Block Cache

在我们的文件系统中，我们将在处理器的虚拟内存系统的帮助下实现一个简单的“缓冲区缓存”(实际上只是块缓存)。块缓存的代码在fs/bc.c中。

我们的文件系统只能处理3GB或更小的磁盘。我们在文件系统环境的地址空间中保留了一个很大的、固定的3GB区域，从0x10000000 (DISKMAP)到0xD0000000 (DISKMAP+DISKMAX)，作为磁盘的“内存映射”版本。例如，磁盘块0映射到虚拟地址0x10000000，磁盘块1映射到虚拟地址0x10001000，依此类推。fs/bc.c中的diskaddr函数实现了从磁盘块号到虚拟地址的转换(以及一些完整性检查)。

将整个磁盘读入内存需要很长时间，因此我们将实现一种请求页面调度，当进程在运行时需要访问某部分程序和数据时，若发现请求页面不在内存，便提出请求，由OS将其所需页面调入内存。这样，我们就可以假装整个磁盘都在内存中。

Exercise 2：

implement the bc_pgfault and flush_block functions in fs/bc.c.

bc_pgfault is a page fault handler, just like the one your wrote in the previous lab for copy-on-write fork, 只不过它的工作是从磁盘加载页面以响应页面错误.

When writing this, keep in mind that

​ (1) addr may not be aligned to a block boundary and

​ (2) ide_read operates in sectors, not blocks.

如果需要，flush_block函数应该将一个块写入磁盘。如果块甚至不在块缓存中(也就是说，页面没有映射)，或者它不是脏的，则Flush_block不应该做任何事情。我们将使用VM硬件来跟踪磁盘块自上次从磁盘读取或写入磁盘以来是否被修改过。要查看一个块是否需要写入，我们只需查看uvpt条目中是否设置了PTE_D“脏”位。PTE_D位由处理器设置，以响应对该页的写操作;参见386参考手册第五章5.2.4.3。)将块写入磁盘后，flush_block应该使用sys_page_map清除PTE_D位。

采用了wb

块号与扇区号有一定的区别，在完成这两个函数时，要注意区分这两个概念。 JOS 块大小位4kB，扇区大小为512B，每次读写一个块，就需要读写4个扇区。因此，JOS使用了一个宏定义#define BLKSECTS (BLKSIZE / SECTSIZE)来描述两者的关系。

bc_pgfault()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

static void
bc_pgfault(struct UTrapframe *utf)
{
   void *addr = (void *) utf->utf_fault_va;
   uint32_t blockno = ((uint32_t)addr - DISKMAP) / BLKSIZE;
   int r;

   // Check that the fault was within the block cache region
   if (addr < (void*)DISKMAP || addr >= (void*)(DISKMAP + DISKSIZE))
      panic("page fault in FS: eip %08x, va %08x, err %04x",
            utf->utf_eip, addr, utf->utf_err);

   // Sanity check the block number.
   if (super && blockno >= super->s_nblocks)
      panic("reading non-existent block %08x\n", blockno);

   // Allocate a page in the disk map region, read the contents
   // of the block from the disk into that page.
   // Hint: first round addr to page boundary. fs/ide.c has code to read
   // the disk.
   //
   // LAB 5: you code here:
    addr = (void*) ROUNDUP(addr, PGSIZE);
    // Allocate a page of memory and map it at 'addr' with permission 'PTE_P|PTE_W|PTE_U' in the address space of 'envid'.
    if((r = sys_page_alloc(0,addr,PTE_P|PTE_W|PTE_U))<0){
        panic("in bc_pgfault, sys_page_alloc: %e", r);
    }

    if ( (r = ide_read(blockno*BLKSECTS, addr, BLKSECTS)) < 0) {
        panic("in bc_pgfault, ide_read: %e",r);
    }

   // Clear the dirty bit for the disk block page since we just read the
   // block from disk
   if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)
      panic("in bc_pgfault, sys_page_map: %e", r);

   // Check that the block we read was allocated. (exercise for
   // the reader: why do we do this *after* reading the block
   // in?)
   if (bitmap && block_is_free(blockno))
      panic("reading free block %08x\n", blockno);
}

flush_block()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 如果需要，将包含VA的块的内容清除到磁盘，然后使用sys_page_map清除PTE_D位。
// 如果该块不在块缓存中或不是脏的，则不做任何操作。
// Hint: Use va_is_mapped, va_is_dirty, and ide_write.
// Hint: Use the PTE_SYSCALL constant when calling sys_page_map.
// Hint: Don't forget to round addr down.
void
flush_block(void *addr)
{
   uint32_t blockno = ((uint32_t)addr - DISKMAP) / BLKSIZE;

   if (addr < (void*)DISKMAP || addr >= (void*)(DISKMAP + DISKSIZE))    // 越界
      panic("flush_block of bad va %08x", addr);

   // LAB 5: Your code here.
   //panic("flush_block not implemented");
    addr = (void *)ROUNDDOWN(addr, PGSIZE);
    if (va_is_mapped(addr) && va_is_dirty(addr)) {  // 映射过并且为脏
        ide_write(blockno*BLKSECTS, addr , BLKSECTS);  // 写回到磁盘
        if ((r = sys_page_map(0, addr, 0, addr, uvpt[PGNUM(addr)] & PTE_SYSCALL)) < 0)   // 清空PTE_D (脏)位
            panic("in flush_block, sys_page_map: %e", r);
    }
}

fs/fs.c中的fs_init()将会初始化super和bitmap全局指针变量。

至此对于文件系统进程只要访问虚拟内存[DISKMAP, DISKMAP+DISKMAX]范围中的地址addr，就会访问到磁盘((uint32_t)addr - DISKMAP) / BLKSIZE block中的数据。

如果block数据还没复制到内存物理页，bc_pgfault()缺页处理函数会将数据从磁盘拷贝到某个物理页，并且将addr映射到该物理页。这样FS进程只需要访问虚拟地址空间[DISKMAP, DISKMAP+DISKMAX]就能访问磁盘了。

JOS FS进程地址空间和磁盘映射：

The Block Bitmap

在fs_init设置位图(btimap)指针之后，我们可以将位图视为一个位的压缩数组，磁盘上的每个块对应一个位。例如，block_is_free，它只是检查位图中给定的块是否被标记为空闲。

Exercise 3：

使用free_block作为模型来实现fs/fs.c中的alloc_block，它应该在位图中找到一个空闲的磁盘块，标记它已被使用，并返回该块的编号。当您分配一个块时，您应该立即使用flush_block将更改后的位图块刷新到磁盘，以帮助文件系统保持一致性。

我们以一个实例来分析 bitmap的工作原理， 若标记第35个块（块号为34）为使用状态， 则将bitmap[1] 的第 2 （34%32）位标记为 0。 讲道理应该位图位为0是free的呀，JOS这里反过来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Search the bitmap for a free block and allocate it.  When you
// allocate a block, immediately flush the changed bitmap block
// to disk.
//
// Return block number allocated on success,
// -E_NO_DISK if we are out of blocks.
//
// Hint: use free_block as an example for manipulating the bitmap.
int
alloc_block(void)
{
   // The bitmap consists of one or more blocks.  A single bitmap block
   // contains the in-use bits for BLKBITSIZE blocks.  There are
   // super->s_nblocks blocks in the disk altogether.

   // LAB 5: Your code here.
   size_t i;
    for(i = 1; i<super->s_nblocks;++i){
        // block_is_free(): Check to see if the block bitmap indicates that block 'blockno' is free.
        // Return 1 if the block is free, 0 if not.
        if(block_is_free(i)){  // 没有使用，则标记为已使用
            bitmap[i/32] &=  ~(1<<(i%32));
            flush_block(&bitmap[i/32]);  // 写回并重置脏位
            return i;
        }
    }

    //panic("alloc_block not implemented");
   return -E_NO_DISK;
}

File Operations

Exercise 4:

实现file_block_walk和file_get_block。file_block_walk将文件中的块偏移量映射到struct file或间接块中该块的指针，非常像pgdir_walk对页表所做的。File_get_block更进一步，映射到实际的磁盘块，如果需要，分配一个新的磁盘块。

file_block_walk 获得文件第filebno块的地址（其本身是个指针），编写需要注意以下几点。

• ppdiskbno 是块指针（记录块的地址）
• f_indirect 直接记录块号，而不是记地址。
• Don’t forget to clear any block you allocate. 对分配的块进行清零操作后，要写入 disk 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// Find the disk block number slot for the 'filebno'th block in file 'f'.
// Set '*ppdiskbno' to point to that slot.
// The slot will be one of the f->f_direct[] entries,
// or an entry in the indirect block.
// When 'alloc' is set, this function will allocate an indirect block
// if necessary.
//
// Returns:
// 0 on success (but note that *ppdiskbno might equal 0).
// -E_NOT_FOUND if the function needed to allocate an indirect block, but
//    alloc was 0.
// -E_NO_DISK if there's no space on the disk for an indirect block.
// -E_INVAL if filebno is out of range (it's >= NDIRECT + NINDIRECT).
//
// Analogy: This is like pgdir_walk for files.
// Hint: Don't forget to clear any block you allocate.
static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
    // filenno   file block number
    // LAB 5: Your code here.
    // panic("file_block_walk not implemented");
    // ppdiskbno 块指针
    if (filebno < NDIRECT) {   // NDIRECT: Number of block pointers in a File descriptor
        // but note that *ppdiskbno might equal 0
        if(ppdiskbno)
            *ppdiskbno = &(f->f_direct[filebno]);
        else
            return 0;
    }

    if (filebno >= NDIRECT + NINDIRECT)  // NINDIRECT: Number of direct block pointers in an indirect block
        return -E_INVAL;

    // 如果文件还没分配
    filebno -= NDIRECT;
    if (!!f->f_indirect) {  // !!把非0转换为1，而0还是0
        if (alloc == 0)
            return -E_NOT_FOUND;
        // 分配一个 indirect block
        uint32_t blockno;
        if ( (blockno = alloc_block()) < 0)
            return blockno;
        // f_indirect 直接记录块号，而不是记地址
        // f->f_indirect = (uint32_t)diskaddr(blockno);
        f->f_indirect = blockno;
        memset(diskaddr(blockno), 0, BLKSIZE);
        flush_block(diskaddr(blockno));
    }
    if (ppdiskbno)
        *ppdiskbno = (uint32_t *)diskaddr(f->f_indirect) + filebno;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// Set *blk to the address in memory where the filebno'th
// block of file 'f' would be mapped.
// 将*blk设置为文件'f'的第filebno块在内存中的映射地址。
// Returns 0 on success, < 0 on error.  Errors are:
// -E_NO_DISK if a block needed to be allocated but the disk is full.
// -E_INVAL if filebno is out of range.
//
// Hint: Use file_block_walk and alloc_block.
int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{
       // LAB 5: Your code here.
    uint32_t *pdiskbno;  // 块的块号指针
    int r;
    if ( (r = file_block_walk(f, filebno, &pdiskbno, 1))< 0)  //
        return r;  // 找到文件第filebno块的位置pdiskbno

    if(*pdiskbno == 0) {  // 这个位置还没分配
        // 文件块还未分配
        if ( (r = alloc_block()) < 0)   // alloc_block 在位图中搜索一个空闲块并分配它。当您分配一个块时，立即将更改的位图块刷新到磁盘。
            return r;
        *pdiskbno = r;
        memset(diskaddr(r), 0, BLKSIZE);
        flush_block(diskaddr(r));  // wb
    }

    // 最终指向块
    *blk = diskaddr(*pdiskbno);  // // Return the virtual address of this disk block.
    return 0;
    // panic("file_get_block not implemented");
}

The file system interface

由于其他环境无法直接调用文件系统环境中的函数，因此我们将通过 RPC 或在JOS的IPC机制上构建的RPC抽象来公开对文件系统环境的访问。

RPC(Remote Procedure Call)。它是一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术的协议。RPC协议假定某些传输协议的存在，如TCP或UDP，为通信程序之间携带信息数据。在OSI网络通信模型中，RPC跨越了传输层和应用层。RPC使得开发包括网络分布式多程序在内的应用程序更加容易。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

      Regular env           FS env
   +---------------+   +---------------+
   |      read     |   |   file_read   |
   |   (lib/fd.c)  |   |   (fs/fs.c)   |
...|.......|.......|...|.......^.......|...............
   |       v       |   |       |       | RPC mechanism
   |  devfile_read |   |  serve_read   |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |     fsipc     |   |     serve     |
   |  (lib/file.c) |   |  (fs/serv.c)  |
   |       |       |   |       ^       |
   |       v       |   |       |       |
   |   ipc_send    |   |   ipc_recv    |
   |       |       |   |       ^       |
   +-------|-------+   +-------|-------+
           |                   |
           +-------------------+

本质上RPC还是借助IPC机制实现的，普通进程通过IPC向FS进程间发送具体操作和操作数据，然后FS进程执行文件操作，最后又将结果通过IPC返回给普通进程。从上图中可以看到客户端的代码在lib/fd.c和lib/file.c两个文件中。服务端的代码在fs/fs.c和fs/serv.c两个文件中。
相关数据结构之间的关系可用下图来表示：

文件系统服务端代码在fs/serv.c中，serve()中有一个无限循环，接收IPC请求，将对应的请求分配到对应的处理函数，然后将结果通过IPC发送回去。
对于客户端来说：发送一个32位的值作为请求类型，发送一个Fsipc结构作为请求参数，该数据结构通过IPC的页共享发给FS进程，在FS进程可以通过访问fsreq(0x0ffff000)来访问客户进程发来的Fsipc结构。
对于服务端来说：FS进程返回一个32位的值作为返回码，对于FSREQ_READ和FSREQ_STAT这两种请求类型，还额外通过IPC返回一些数据。

Exercise 5

Implement serve_read in fs/serv.c.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int
serve_read(envid_t envid, union Fsipc *ipc)  // 从指定文件中读取出内容，返回给调用者
{
   struct Fsreq_read *req = &ipc->read;  // 指定文件
   struct Fsret_read *ret = &ipc->readRet;  // 调用者

   if (debug)
      cprintf("serve_read %08x %08x %08x\n", envid, req->req_fileid, req->req_n);

   // Lab 5: Your code here:
    int r;
    struct openFile* opf;
    if((r = openfile_lookup(envid, req->req_fileid, &opf))<0){  // Look up an open file for envid.
        return r;
    }
    if((r = file_read(opf->o_file, ret->ret_buf, req->req_n, opf->o_fd->fd_offset))<0){
        return r;
    }
    of->o_fd->fd_offset +=r;

   return r;
}

Exercise 6

Implement serve_write in fs/serv.c and devfile_write in lib/file.c.

serve_write: 在file_write中考虑了块边界的问题bn = MIN(BLKSIZE - pos % BLKSIZE, offset + count - pos);，因此我们同样不需要对 req_n 进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int
serve_write(envid_t envid, struct Fsreq_write *req)
{
    if (debug)
        cprintf("serve_write %08x %08x %08x\n", envid, req->req_fileid, req->req_n);
    int r;
    struct OpenFile *of;
    int reqn;
    if ( (r = openfile_lookup(envid, req->req_fileid, &of)) < 0)
        return r;
    reqn = req->req_n > PGSIZE? PGSIZE:req->req_n;
    
    if ( (r = file_write(of->o_file, req->req_buf, reqn, of->o_fd->fd_offset)) < 0)
        return r;

    of->o_fd->fd_offset += r;
    return r;
}

devfile_write: devfile_write需要调用fsipc，其向文件服务器发送一个进程间请求，并等待回复。请求体保存在fsipcbuf中，回复部分也应该写回到 fsipcbuf中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static ssize_t
devfile_write(struct Fd *fd, const void *buf, size_t n)
{
    // LAB 5: Your code here
    int r;
    if ( n > sizeof (fsipcbuf.write.req_buf)) 
        n = sizeof (fsipcbuf.write.req_buf);
    
    fsipcbuf.write.req_fileid = fd->fd_file.id;
    fsipcbuf.write.req_n = n;
    memmove(fsipcbuf.write.req_buf, buf, n);

    return  fsipc(FSREQ_WRITE, NULL);
}

Spawning Processes

slib/spawn.c中的spawn()创建一个新的进程，从文件系统加载用户程序，然后启动该进程来运行这个程序。spawn()就像UNIX中的fork()后面马上跟着exec()。 spawn(const char *prog, const char **argv)`做如下一系列动作：

1. 从文件系统打开prog程序文件
2. 调用系统调用sys_exofork()创建一个新的Env结构
3. 调用系统调用sys_env_set_trapframe()，设置新的Env结构的Trapframe字段（该字段包含寄存器信息）。
4. 根据ELF文件中program herder，将用户程序以Segment读入内存，并映射到指定的线性地址处。
5. 调用系统调用sys_env_set_status()设置新的Env结构状态为ENV_RUNNABLE。

我们实现了spawn而不是UNIX风格的exec，因为在没有内核特殊帮助的情况下，spawn更容易以“exokernel fashion”从用户空间实现。

Exercise 7

spawn C依赖新的系统调用sys_env_set_trapframe来初始化新创建的环境的状态。 在kern/syscall.c中实现sys_env_set_trapframe(不要忘记在sycall()中调度新的系统调用)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// Set envid's trap frame to 'tf'.
// tf is modified to make sure that user environments always run at code
// protection level 3 (CPL 3), interrupts enabled, and IOPL of 0.
//
// Returns 0 on success, < 0 on error.  Errors are:
// -E_BAD_ENV if environment envid doesn't currently exist,
//    or the caller doesn't have permission to change envid.
static int
sys_env_set_trapframe(envid_t envid, struct Trapframe *tf)
{
   // LAB 5: Your code here.
   // Remember to check whether the user has supplied us with a good
   // address!
   // panic("sys_env_set_trapframe not implemented");
    struct Env *env;
    int r;
    if ( (r = envid2env(envid, &env, 1)) < 0)
        return r;

    // 什么时候会出现没有权限访问的问题？
    user_mem_assert(env, tf, sizeof(struct Trapframe), PTE_U);
    // 直接整个结构体也是可以赋值的
    env->env_tf = *tf;
    env->env_tf.tf_cs |= 0x3;
    env->env_tf.tf_eflags &=  (~FL_IOPL_MASK);
    env->env_tf.tf_eflags |= FL_IF;
    return 0;
}

Sharing library state across fork and spawn

在fork和spawn之间共享library的状态

在JOS中，每个设备类型都具有相应的struct Dev，其中包含指向实现读/写/等的函数指针。对于该设备类型。 lib / fd.c在此基础上实现了类似UNIX的通用文件描述符接口。 每个结构体Fd表示它的设备类型，lib/fd.c中的大多数函数只是将操作分派给适当的struct Dev中的函数。

1
2
3
4
5
6
7
8
9
10

// Per-device-class file descriptor operations
struct Dev {
    int dev_id;
    const char *dev_name;
    ssize_t (*dev_read)(struct Fd *fd, void *buf, size_t len);
    ssize_t (*dev_write)(struct Fd *fd, const void *buf, size_t len);
    int (*dev_close)(struct Fd *fd);
    int (*dev_stat)(struct Fd *fd, struct Stat *stat);
    int (*dev_trunc)(struct Fd *fd, off_t length);
};

UNIX文件描述符是一个大的概念，包含pipe，控制台I/O。在JOS中每种设备对应一个struct Dev结构，该结构包含函数指针，指向真正实现读写操作的函数。
lib/fd.c文件实现了UNIX文件描述符接口，但大部分函数都是简单对struct Dev结构指向的函数的包装。

我们希望共享文件描述符，JOS中定义PTE新的标志位PTE_SHARE，如果有个页表条目的PTE_SHARE标志位为1，那么这个PTE在fork()和spawn()中将被直接拷贝到子进程页表，从而让父进程和子进程共享相同的页映射关系，从而达到父子进程共享文件描述符的目的。

Exercise 8

修改lib/fork.c中的duppage()，使之正确处理有PTE_SHARE标志的页表条目。同时实现lib/spawn.c中的copy_shared_pages()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

static int
duppage(envid_t envid, unsigned pn)
{
    int r;
 
    // LAB 4: Your code here.
    void *addr = (void*) (pn * PGSIZE);
    if (uvpt[pn] & PTE_SHARE) {
        sys_page_map(0, addr, envid, addr, PTE_SYSCALL);        //对于标识为PTE_SHARE的页，拷贝映射关系，并且两个进程都有读写权限
    } else if ((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)) { //对于UTOP以下的可写的或者写时拷贝的页，拷贝映射关系的同时，需要同时标记当前进程和子进程的页表项为PTE_COW
        if ((r = sys_page_map(0, addr, envid, addr, PTE_COW|PTE_U|PTE_P)) < 0)
            panic("sys_page_map：%e", r);
        if ((r = sys_page_map(0, addr, 0, addr, PTE_COW|PTE_U|PTE_P)) < 0)
            panic("sys_page_map：%e", r);
    } else {
        sys_page_map(0, addr, envid, addr, PTE_U|PTE_P);    //对于只读的页，只需要拷贝映射关系即可
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// Copy the mappings for shared pages into the child address space.
static int
copy_shared_pages(envid_t child)
{
    // LAB 5: Your code here.
    uintptr_t addr;
    for (addr = 0; addr < UTOP; addr += PGSIZE) {
        if ((uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P) &&
            (uvpt[PGNUM(addr)] & PTE_U) && (uvpt[PGNUM(addr)] & PTE_SHARE)) {
            sys_page_map(0, (void*)addr, child, (void*)addr, (uvpt[PGNUM(addr)] & PTE_SYSCALL));
        }
    }
    return 0;
}

The keyboard interface

目前我们只能在内核监视器中才能接收输入。kern/console.c already contains the keyboard and serial drivers that have been used by the kernel monitor since lab 1, but now you need to attach these to the rest of the system.

kern/console.c 已经包含了从实验1开始内核监视器就在使用的键盘和串行驱动程序，但是现在您需要将它们附加到系统的其他部分。

在/kern/console.c/cons_getc()中的代码，实现了在 monitor 模式下（禁止中断）可以正常获取用户输入。

1
2
3
4
5

// poll for any pending input characters,
    // so that this function works even when interrupts are disabled
    // (e.g., when called from the kernel monitor).
    serial_intr();
    kbd_intr();

在 trap.c 中加入中断处理函数。

1
2
3
4
5
6
7
8

case (IRQ_OFFSET + IRQ_KBD):
    lapic_eoi();
    kbd_intr();
    break;
case (IRQ_OFFSET + IRQ_SERIAL):
    lapic_eoi();
    serial_intr();
    break;

The Shell

总结

Lab5 主要介绍了文件系统的基本组成，为超级块分配易查找的位置，并在超级块中记录根目录文件，此后递进存储即实现了FS的多级目录。利用虚拟地址和MMIO实现了类似统一编址方式，我们可以很方便实现文件访问，其操作过程与内存访问很类似（在文件结构体中 walk 到块号）。

JOS在用户环境实现FS，FS接口是这个Lab的重点。其通过RPC公开接口，在JOS中利用IPC机制构建RPC抽象。regular env->read->ipc_send -> ipc_recv->serve->file_read。
这实际上以微内核的方式实现的FS，FS的serv相当于一种微服务进程，其接收、解析内核转发的信息再执行相应的操作。消息通过一个页映射的Union Fsipc进行传递。

spawn函数表现得像在Unix下创建子进程带有一个立刻执行exec的fork函数。exec()会把当前执行进程覆盖掉来执行外部程序，spawn()则会创建一个新的进程来执行。对于spawn的设计，还是有一些困惑，因为不明白 Unix-Style的exec是如何实现的，所以不能理解为什么spawn更容易在用户空间实现。

最后的Keyboard 接口和Shell都相对简单，比较容易理解。

1. 其他环境无法直接调用文件系统环境中的函数，要通过IPC，进程间消息传递实现。这里应该就是微内核的概念了。但为什么不能直接调用，是怎么实现不能直接调用的？是特意不让别的环境直接使用其函数吗？有没有方法可以实现不同用户程序可以直接调用其他用户程序的函数？

不能直接调用，应该是因为每个用户态的代码都存在于自身的地址空间中，其他用户程序无法访问到。但是我如果在源代码中的某个环境直接#include并且调用另一个环境文件夹下的代码（例如fs），即在编译前就调用了，这会出现什么情况？这样就相当于是宏内核的概念了吗？ 或者是这样设计会增大代码的耦合性？这让我十分疑惑。毕竟这与越过系统调用不一样，系统调用有权限限制。

LAB4: Preemtive Multitasking 抢占式多任务处理

您将在多个同时活跃的用户模式环境中实现抢占式多任务处理。

在A部分中，您将向JOS添加多处理器支持，实现循环调度，并添加基本的环境管理系统调用(创建和销毁环境的调用，以及分配/映射内存的调用)。

在B部分中，您将实现一个类unix的fork()，它允许用户模式环境创建自身的副本。

最后，在C部分中，您将添加对进程间通信(IPC)的支持，允许不同的用户模式环境显式地相互通信和同步。您还将添加对硬件时钟中断和抢占的支持

Part A: Multiprocessor Support and Cooperative Multitasking多处理器支持和多任务协作

我们首先需要把 JOS 扩展到在多处理器系统中运行。然后实现一些新的 JOS 系统调用来允许用户进程创建新的进程。我们还要实现协同轮询调度，允许内核在当前进程自愿放弃CPU（或退出cpu）时从一个环境切换到另一个环境。

我们即将使 JOS 能够支持“对称多处理” (Symmetric MultiProcessing, SMP)。这种模式使所有 CPU 能对等地访问内存、I/O 总线等系统资源。虽然 CPU 在 SMP 下以同样的方式工作，在启动过程中他们可以被分为两个类型：引导处理器(BootStrap Processor, BSP) 负责初始化系统以及启动操作系统；应用处理器( Application Processors, AP ) 在操作系统拉起并运行后由 BSP 激活。哪个 CPU 作为 BSP 由硬件和 BIOS 决定。也就是说目前我们所有的 JOS 代码都运行在 BSP 上。
在 SMP 系统中，每个 CPU 都有一个附属的 LAPIC 单元。LAPIC 单元用于传递中断，并给它所属的 CPU 一个唯一的 ID。在 lab4 中，我们将会用到 LAPIC 单元的以下基本功能 ( 见kern/lapic.c中 )：

• 读取 APIC ID 来判断我们的代码运行在哪个 CPU 之上。(see cpunum() )
• 从 BSP 发送STARTUP 跨处理器中断 (InterProcessor Interrupt, IPI) 来启动 AP。(see lapic_startap() )
• 在 part C 中，我们为 LAPIC 的内置计时器编程来触发时钟中断以支持抢占式多任务处理。(see apic_init() )

处理器通过映射在内存上的 I/O (Memory-Mapped I/O, MMIO) 来访问它的 LAPIC。在 MMIO 中，物理内存的一部分被硬连接到一些 I/O 设备的寄存器，因此，访问内存的 load/store 指令可以被用于访问设备的寄存器。实际上，我们在 lab1 中已经接触过这样的 IO hole，如0xA0000被用来写 VGA 显示缓冲。LAPIC 开始于物理地址0xFE000000 ( 4GB以下32MB处 )。如果用以前的映射算法（将0xF0000000 映射到 0x00000000，也就是说内核空间最高只能到物理地址0x0FFFFFFF）显然太高了。因此，JOS 在 MMIOBASE (即 虚拟地址0xEF800000) 预留了 4MB 来映射这类设备。我们需要写一个函数来分配这个空间并在其中映射设备内存。

LAPIC 和 IOAPIC

APIC全称是Advanced Programmable Interrupt Controller，高级可编程中断控制器。它是在奔腾P54C之后被引入进来的。

在现在的计算机它通常由两个部分组成，分别为LAPIC（Local APIC，本地高级可编程中断控制器）和IOAPIC(I/O高级可编程中断控制器）。

LAPIC在CPU中，IOAPIC通常位于南桥。

APIC是在PIC (Programmable Interrupt Controller) 的基础上发展而来的

IOAPIC: IOAPIC的主要作用是中断的分发。最初有一条专门的APIC总线用于IOAPIC和LAPIC通信，在Pentium4 和Xeon 系列CPU出现后，他们的通信被合并到系统总线中。

Exercise 1: Multiprocessor Support

Implement mmio_map_region in kern/pmap.c. To see how this is used, look at the beginning of lapic_init in kern/lapic.c. You’ll have to do the next exercise, too, before the tests for mmio_map_region will run.

*void mmio_map_region(physaddr_t pa, size_t size)

1
2
3

Reserve size bytes in the MMIO region and map [pa,pa+size) at this location.  Return the base of the reserved region.
在MMIO区域保留大小为size字节的区域，然后把[pa, pa+size]映射到此区域，返回该区域的base.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void *
mmio_map_region(physaddr_t pa, size_t size)
{
   // Where to start the next region.  Initially, this is the
   // beginning of the MMIO region.  Because this is static, its
   // value will be preserved between calls to mmio_map_region
   // (just like nextfree in boot_alloc).
   static uintptr_t base = MMIOBASE;

   // Hint: The staff solution uses boot_map_region.
   //
   // Your code here:
   // panic("mmio_map_region not implemented");
    
    // 取整页数
    size_t roundup_sz = ROUNDUP(size, PGSIZE);
    if(base+roundup_sz > MMIOLIM){
        panic("mmio_map_region: out of MMIOLIM.");
    }
    boot_map_region(kern_pgdir, base, roundup_sz, pa, PTE_PCD|PTE_PWT|PTE_W);
    uintptr_t res_region_base = base;
    base += roundup_sz;
    return (void*)res_region_base;
}

void lapic_init(void)

该函数一开始就调用了mmin_map_region函数，pa为lapicaddr，size为4096 = 4KB，即将从lapicaddr开始的4KB的物理地址映射到虚拟地址(保留区域)，以便我们能访问，然后返回保留区域的起始地址。

Exercise 2: Application Processor Bootstrap

在启动 APs 之前，BSP 需要先搜集多处理器系统的信息，例如 CPU 的总数，CPU 各自的 APIC ID，LAPIC 单元的 MMIO 地址。kern/mpconfig.c 中的 mp_init() 函数通过阅读 BIOS 区域内存中的 MP 配置表来获取这些信息。
boot_aps() 函数驱动了 AP 的引导。APs 从实模式开始，如同 boot/boot.S 中 bootloader 的启动过程。因此 boot_aps() 将 AP 的入口代码 (kern/mpentry.S) 拷贝到实模式可以寻址的内存区域 (0x7000, MPENTRY_PADDR)。
此后，boot_aps() 通过发送 STARTUP 这个跨处理器中断到各 LAPIC 单元的方式，逐个激活 APs。激活方式为：初始化 AP 的 CS:IP 值使其从入口代码执行。通过一些简单的设置，AP 开启分页进入保护模式，然后调用 C 语言编写的 mp_main()。boot_aps() 等待 AP 发送 CPU_STARTED 信号，然后再唤醒下一个。

Read boot_aps() and mp_main() in kern/init.c, and the assembly code in kern/mpentry.S. Make sure you understand the control flow transfer during the bootstrap of APs. Then modify your implementation of page_init() in kern/pmap.cto avoid adding the page at MPENTRY_PADDR to the free list, so that we can safely copy and run AP bootstrap code at that physical address. Your code should pass the updated check_page_free_list() test (but might fail the updated check_kern_pgdir() test, which we will fix soon).

real mode表示我们看到的都是直接的物理地址

Question

1. Compare kern/mpentry.S side by side with boot/boot.S. Bearing in mind that kern/mpentry.S is compiled and linked to run above KERNBASE just like everything else in the kernel, what is the purpose of macro MPBOOTPHYS? Why is it necessary in kern/mpentry.S but not in boot/boot.S? In other words, what could go wrong if it were omitted in kern/mpentry.S?
   Hint: recall the differences between the link address and the load address that we have discussed in Lab 1.

​ MPBOOTPHYS的作用：

kern/mpentry.S是运行在kernbase之上的，因此在实地址模式下，无法进行寻址（即无法访问）。

kern/mpentry.S

1
2
3
4
5
6
7

# This code is similar to boot/boot.S except that
#    - it does not need to enable A20
#    - it uses MPBOOTPHYS to calculate absolute addresses of its
#      symbols, rather than relying on the linker to fill them

#define RELOC(x) ((x) - KERNBASE)
#define MPBOOTPHYS(s) ((s) - mpentry_start + MPENTRY_PADDR)

((s) - mpentry_start + MPENTRY_PADDR) 表示把mpentry地址转换到MPENTRY_PADDR。

kern/init.c中已经进行了内容的拷贝，因此boot.S不需要再次 进行拷贝。而mpentry.S需要宏进行拷贝。

Per-CPU State and Initialization(CPU私有状态和初始化)

当写一个多处理器操作系统时，分清 CPU 的私有状态 ( per-CPU state) 及全局状态 (global state) 非常关键。 kern/cpu.h 定义了大部分的 per-CPU 状态。
我们需要注意的 per-CPU 状态有：

• Per-CPU 内核栈
  因为多 CPU 可能同时陷入内核态，我们需要给每个处理器一个独立的内核栈。用户态切到内核态，内核将用户态时的堆栈寄存器的值保存在内核栈中，以便于从内核栈切换回进程栈时能找到用户栈的地址。

  percpu_kstacks[NCPU][KSTKSIZE]
  在 Lab2 中，我们将 BSP 的内核栈映射到了 KSTACKTOP 下方。相似地，在 Lab4 中，我们需要把每个 CPU 的内核栈都映射到这个区域，每个栈之间留下一个空页作为缓冲区避免 overflow。CPU 0 ，即 BSP 的栈还是从 KSTACKTOP 开始，间隔 KSTACKGAP 的距离就是 CPU 1 的栈，以此类推。

• Per-CPU TSS 以及 TSS 描述符
  为了指明每个 CPU 的内核栈位置，需要任务状态段 (Task State Segment, TSS)，其功能在 Lab3 中已经详细讲过。

• Per-CPU 当前环境指针
  因为每个 CPU 能够同时运行各自的用户进程，我们重新定义了基于cpus[cpunum()] 的 curenv。

• Per-CPU 系统寄存器
  所有的寄存器，包括系统寄存器，都是 CPU 私有的。因此，初始化这些寄存器的指令，例如 lcr3(), ltr(), lgdt(), lidt() 等，必须在每个 CPU 都执行一次。

Exercise 3.

Modify mem_init_mp() (in kern/pmap.c) to map per-CPU stacks starting at KSTACKTOP, as shown in inc/memlayout.h. The size of each stack is KSTKSIZE bytes plus KSTKGAP bytes of unmapped guard pages. Your code should pass the new check in check_kern_pgdir().

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static void
mem_init_mp(void)
{
   
   // LAB 4: Your code here:
    // LAB 2 中只把BSP的内核栈 map 到了KSTACKTOP下方，这次把所有的cpu都进行map
    // 在 kern/cpu.h 中可以找到对 NCPU 以及全局变量 percpu_kstacks 的声明
    uintptr_t start_addr = KSTACKTOP - KSTKSIZE;   // 倒着来
    for(size_t i = start_addr; i<NCPU;++i){  // i代表cpu编号
        boot_map_region(kern_pgdir, (uintptr_t)start_addr, KSTKSIZE, PADDR(percpu_kstacks[i]), PTE_W|PTE_P);
        start_addr-=(KSTKSIZE+KSTKGAP); //gap是两个cpu之间的缓冲区
    }
    // 即使从KSTACKTOP重新开始分配，之前的BSP会直接被覆盖掉，不会有影响
}

Exercise 4.

在 inc/memlayout.h 中可以看到之前分配BSP时，TSS0的定义

这只是对单CPU而言的定义，那么对于多个cpu，就需要其他的TSS，如何寻找这个TSS？trap_init_percpu()注释中说明了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// Initialize and load the per-CPU TSS and IDT
void
trap_init_percpu(void)
{
   
   // LAB 4: Your code here:
	 struct Taskstate* this_ts = &thiscpu->cpu_ts;   //!!!!!!!!!!!!
   // 一开始写成了struct Taskstate this_ts = thiscpu->cpu_ts;
  // 导致cpu的值并未改变，然后出现triple fault    ！！！！！！！！！！
   // Setup a TSS so that we get the right stack
   // when we trap to the kernel.
   ts.ts_esp0 = KSTACKTOP;
   ts.ts_ss0 = GD_KD;
   ts.ts_iomb = sizeof(struct Taskstate);

   // Initialize the TSS slot of the gdt.
   gdt[GD_TSS0 >> 3] = SEG16(STS_T32A, (uint32_t) (&ts),
               sizeof(struct Taskstate) - 1, 0);
   gdt[GD_TSS0 >> 3].sd_s = 0;

   // Load the TSS selector (like other segment selectors, the
   // bottom three bits are special; we leave them 0)
   ltr(GD_TSS0);

   // Load the IDT
   lidt(&idt_pd);
}

运行 make qemu CPUS=4 (or make qemu-nox CPUS=4)

Exercise5: Locking

我们现在的代码在初始化 AP 后就会开始自旋。在进一步操作 AP 之前，我们要先处理几个 CPU 同时运行内核代码的竞争情况。最简单的方法是用一个大内核锁 (big kernel lock)。它是一个全局锁，在某个进程进入内核态时锁定，返回用户态时释放。这种模式下，用户进程可以并发地在 CPU 上运行，但是同一时间仅有一个进程可以在内核态，其他需要进入内核态的进程只能等待。
kern/spinlock.h 声明了一个大内核锁 kernel_lock。它提供了 lock_kernel() 和 unlock_kernel() 方法用于获得和释放锁。在以下 4 个地方需要使用到大内核锁：

• 在 i386_init()，BSP 唤醒其他 CPU 之前获得内核锁
• 在 mp_main()，初始化 AP 之后获得内核锁，之后调用 sched_yield() 在 AP 上运行进程。
• 在 trap()，当从用户态陷入内核态时获得内核锁，通过检查 tf_Cs 的低 2bit 来确定该 trap 是由用户进程还是内核触发。
• 在 env_run()，在切换回用户模式前释放内核锁。

Apply the big kernel lock as described above, by calling lock_kernel() and unlock_kernel() at the proper locations.

kern/init.c/i386_init()

1
2
3
4
5

// Acquire the big kernel lock before waking up APs
// Your code here:
   lock_kernel();
// Starting non-boot CPUs
boot_aps();

init.c/mp_main()

1
2
3
4
5
6
7

// Now that we have finished some basic setup, call sched_yield()
// to start running processes on this CPU.  But make sure that
// only one CPU can enter the scheduler at a time!
//
// Your code here:
   lock_kernel();
   sched_yield();

trap.c/trap()

1
2
3
4
5
6
7

if ((tf->tf_cs & 3) == 3) {   // 陷入了内核态
   // Trapped from user mode.
   // Acquire the big kernel lock before doing any
   // serious kernel work.
   // LAB 4: Your code here.
       lock_kernel();
   assert(curenv);

env.c/env_run()

1
2
3

lcr3(PADDR(e->env_pgdir));
unlock_kernel();
env_pop_tf(&e->env_tf);

为什么要在这几处加大内核锁
从根本上来讲，其设计的初衷就是保证独立性。由于分页机制的存在，内核以及每个用户进程都有自己的独立空间。而多进程并发的时候，如果两个进程同时陷入内核态，就无法保证独立性了。例如内核中有某个全局变量 A，cpu1 让 A=1， 而后 cpu2 却让 A=2，显然会互相影响。

BPS 启动 AP 前，获取内核锁，所以 AP 会在 mp_main 执行调度之前阻塞，在启动完 AP 后，BPS 执行调度，运行第一个进程，env_run() 函数中会释放内核锁，这样一来，其中一个 AP 就可以开始执行调度，运行其他进程。

Question 2.
It seems that using the big kernel lock guarantees that only one CPU can run the kernel code at a time. Why do we still need separate kernel stacks for each CPU? Describe a scenario in which using a shared kernel stack will go wrong, even with the protection of the big kernel lock

在某进程即将陷入内核态的时候（尚未获得锁），其实在 trap() 函数之前已经在 trapentry.S 中对内核栈进行了操作，压入了寄存器信息。如果共用一个内核栈，那显然会导致信息错误。

Exercise6: Round-Robin Scheduling 轮询调度

下一个任务是让 JOS 内核能够以轮询方式在多个任务之间切换。其原理如下：

• kern/sched.c 中的 sched_yield() 函数用来选择一个新的进程运行。它将从上一个运行的进程开始，按顺序循环搜索 envs[] 数组，选取第一个状态为 ENV_RUNNABLE 的进程执行。
• sched_yield()不能同时在两个CPU上运行同一个进程。如果一个进程已经在某个 CPU 上运行，其状态会变为 ENV_RUNNING。
• 程序中已经实现了一个新的系统调用 sys_yield()，进程可以用它来唤起内核的 sched_yield() 函数，从而将 CPU 资源移交给一个其他的进程

Exercise 6.
Implement round-robin scheduling in sched_yield() as described above. Don’t forget to modify syscall() to dispatch sys_yield().
Make sure to invoke sched_yield() in mp_main.
Modify kern/init.c to create three (or more!) environments that all run the program user/yield.c.

首先要找到正在运行的进程在envs[]中的序号。

sched.c/sched_yield()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// Choose a user environment to run and run it.
void
sched_yield(void)
{
   struct Env *idle;

   // Implement simple round-robin scheduling.
   //
   // Search through 'envs' for an ENV_RUNNABLE environment in
   // circular fashion starting just after the env this CPU was
   // last running.  Switch to the first such environment found.
   //
   // If no envs are runnable, but the environment previously
   // running on this CPU is still ENV_RUNNING, it's okay to
   // choose that environment.
   //
   // Never choose an environment that's currently running on
   // another CPU (env_status == ENV_RUNNING). If there are
   // no runnable environments, simply drop through to the code
   // below to halt the cpu.

   // LAB 4: Your code here.
    idle = curenv;
    size_t running_idx = (idle == NULL)?:-1:ENVX(idle->env_id);
    for(size_t i = 0;i<NENV;++i){
        running_idx = (running_idx+1 == NENV)?0:running_idx+1; // 0代表从头再搜，因为起始点可能在中间
        if(envs[running_idx].env_status == RUNNABLE){  // 选取第一个状态为RUNNABLE的进程执行
            env_run(&envs[running_idx]);
            return;
        }
    }
    // 如果没有可运行的环境，但是之前在此CPU上运行的环境仍然是ENV_RUNNING，则可以选择该环境
    if(idle && envs[idle].env_status == ENV_RUNNING){
        env_run(idle);
        return;
    }
   // sched_halt never returns
   sched_halt();
}

inc/syscall.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* system call numbers */ 在syscall.h中有定义，syscall不是trap！！！

/* system call numbers */
enum {
	SYS_cputs = 0,
	SYS_cgetc,
	SYS_getenvid,
	SYS_env_destroy,
	SYS_page_alloc,
	SYS_page_map,
	SYS_page_unmap,
	SYS_exofork,
	SYS_env_set_status,
	SYS_env_set_pgfault_upcall,
	SYS_yield,
	SYS_ipc_try_send,
	SYS_ipc_recv,
	NSYSCALLS
};

Question 3.
In your implementation of env_run() you should have called lcr3(). Before and after the call to lcr3(), your code makes references (at least it should) to the variable e, the argument to env_run. Upon loading the %cr3 register, the addressing context used by the MMU is instantly changed. But a virtual address (namely e) has meaning relative to a given address context–the address context specifies the physical address to which the virtual address maps. Why can the pointer e be dereferenced both before and after the addressing switch?

大意是问为什么通过 lcr3() 切换了页目录，还能照常对 e 解引用。回想在 lab3 中，曾经写过的函数 env_setup_vm()。它直接以内核的页目录作为模版稍做修改。因此两个页目录的 e 地址映射到同一物理地址。

Question 4.
Whenever the kernel switches from one environment to another, it must ensure the old environment’s registers are saved so they can be restored properly later. Why? Where does this happen?

在进程陷入内核时，会保存当前的运行信息，这些信息都保存在内核栈上。而当从内核态回到用户态时，会恢复之前保存的运行信息。
具体到 JOS 代码中，保存发生在 kern/trapentry.S，恢复发生在 kern/env.c。可以对比两者的代码。
保存：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#define TRAPHANDLER_NOEC(name, num)
    .globl name;                            
    .type name, @function;                      
    .align 2;                           
    name:                               
    pushl $0;                           
    pushl $(num);                           
    jmp _alltraps
...

_alltraps:
pushl %ds    // 保存当前段寄存器
pushl %es
pushal    // 保存其他寄存器

movw $GD_KD, %ax
movw %ax, %ds
movw %ax, %es
pushl %esp    //  保存当前栈顶指针
call trap

恢复：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void
env_pop_tf(struct Trapframe *tf)
{
    // Record the CPU we are running on for user-space debugging
    curenv->env_cpunum = cpunum();

    asm volatile(
        "\tmovl %0,%%esp\n"    // 恢复栈顶指针
        "\tpopal\n"    // 恢复其他寄存器
        "\tpopl %%es\n"    // 恢复段寄存器
        "\tpopl %%ds\n"
        "\taddl $0x8,%%esp\n" /* skip tf_trapno and tf_errcode */
        "\tiret\n"
        : : "g" (tf) : "memory");
    panic("iret failed");  /* mostly to placate the compiler */
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

➜  lab git:(lab4) ✗ make qemu-nox CPUS=2
***
*** Use Ctrl-a x to exit qemu
***
qemu-system-i386 -nographic -drive file=obj/kern/kernel.img,index=0,media=disk,format=raw -serial mon:stdio -gdb tcp::26000 -D qemu.log -smp 2 
6828 decimal is 15254 octal!
Physical memory: 131072K available, base = 640K, extended = 130432K
check_page_free_list() succeeded!
check_page_alloc() succeeded!
check_page() succeeded!
check_kern_pgdir() succeeded!
check_page_free_list() succeeded!
check_page_installed_pgdir() succeeded!
SMP: CPU 0 found 2 CPU(s)
enabled interrupts: 1 2
SMP: CPU 1 starting
[00000000] new env 00001000
[00000000] new env 00001001
[00000000] new env 00001002
Incoming TRAP frame at 0xefffffbc
Incoming TRAP frame at 0xeffeffbc
Incoming TRAP frame at 0xefffffbc
Hello, I am environment 00001000.
Incoming TRAP frame at 0xeffeffbc
Hello, I am environment 00001001.
Incoming TRAP frame at 0xefffffbc
Incoming TRAP fIncoming TRAP frame at 0xefffffbc
rame at 0xeffeffbc
Incoming TRAP frame at 0Incoming TRAP frame at 0xefffffbc
Hello, I am environment 00001002.
xeffeffbc
Back in environment 00001000, iteration 0.
Incoming TRAP frame at 0xefffffbc
Incoming TRAP frame at 0xeffeffbc
Incoming TRAP frame at 0xefffffbc
Back in environment 00001001, iteration 0.
Incoming TRAP frame at 0xeffeffbc
Back in environment 00001002, iteration 0.
Incoming TRAP frame at 0xefffffbc
Incoming TRAP frame at 0xeffeffbc
Incoming TRAP frame at 0xefffffbc
Back in environment 00001000, iteration 1.
Incoming TRAP frame at 0xeffeffbc
Back in environment 00001001, iteration 1.
Incoming TRAP frame at 0xefffffbc
Incoming TRAP frame at 0xeffeffbc
Incoming TRAP frame at 0xefffffbc
Back in environment 00001002, iteration 1.
Incoming TRAP frame at 0xeffeffbc
Back in environment 00001000, iteration 2.
Incoming TRAP frame at 0xefffffbc
Incoming TRAP frame at 0xeffeffbc
Incoming TRAP frame at 0xefffffbc
Back in environment 00001001, iteration 2.
Incoming TRAP frame at 0xeffeffbc
Back in environment 00001002, iteration 2.
Incoming TRAP frame at 0xefffffbc
Incoming TRAP frame at 0xeffeffbc
Incoming TRAP frame at 0xefffffbc
Back in environment 00001000, iteration 3.
Incoming TRAP frame at 0xeffeffbc
Back in environment 00001001, iteration 3.
Incoming TRAP frame at 0xefffffbc
Incoming TRAP frame at 0xeffeffbc
Incoming TRAP frame at 0xefffffbc
Back in environment 00001002, iteration 3.
Incoming TRAP frame at 0xeffeffbc
Back in environment 00001000, iteration 4.
Incoming TRAP frame at 0xefffffbc
Incoming TRAP frame at 0xeffeffbc
All done in environment 00001000.
Incoming TRAP frame at 0xefffffbc
Back in environment 00001001, iteration 4.
Incoming TRAP frame at 0xeffeffbc
[00001000] exiting gracefully
[00001000] free env 00001000
Incoming TRAP frame at 0xefffffbc
All done in environment 00001001.
Incoming TRAP frame at 0xeffeffbc
Back in environment 00001002, iteration 4.
Incoming TRAP frame at 0xefffffbc
[00001001] exiting gracefully
[00001001] free env 00001001
Incoming TRAP frame at 0xeffeffbc
All done in environment 00001002.
Incoming TRAP frame at 0xeffeffbc
[00001002] exiting gracefully
[00001002] free env 00001002
No runnable environments in the system!
Welcome to the JOS kernel monitor!
Type 'help' for a list of commands.

cpu=2时，三个进程通过sys_yield切换了5次。

Exercise 7: System Calls for Environment Creation(系统调用: 创建进程)

现在我们的内核已经可以运行多个进程，并在其中切换了。不过，现在它仍然只能运行内核最初设定好的程序 (kern/init.c) 。现在我们即将实现一个新的系统调用，它允许进程创建并开始新的进程。
Unix 提供了 fork() 这个原始的系统调用来创建进程。fork()将会拷贝父进程的整个地址空间来创建子进程。在用户空间里，父子进程之间的唯一区别就是它们的进程 ID。fork()在父进程中返回其子进程的进程 ID，而在子进程中返回 0。父子进程之间是完全独立的，任意一方修改内存，另一方都不会受到影响。
我们将为 JOS 实现一个更原始的系统调用来创建新的进程。涉及到的系统调用如下：

• sys_exofork:
  这个系统调用将会创建一个空白进程：在其用户空间中没有映射任何物理内存，并且它是不可运行的。刚开始时，它拥有和父进程相同的寄存器状态。sys_exofork 将会在父进程返回其子进程的envid_t，子进程返回 0（当然，由于子进程还无法运行，也无法返回值，直到运行：）
• sys_env_set_status:
  设置指定进程的状态。这个系统调用通常用于在新进程的地址空间和寄存器初始化完成后，将其标记为可运行。
• sys_page_alloc:
  分配一个物理页并将其映射到指定进程的指定虚拟地址上。
• sys_page_map:
  从一个进程中拷贝一个页面映射（而非物理页的内容）到另一个。即共享内存。
• sys_page_unmap:
  删除到指定进程的指定虚拟地址的映射。

Exercise 7.
Implement the system calls described above in kern/syscall.c. You will need to use various functions in kern/pmap.c and kern/env.c, particularly envid2env(). For now, whenever you call envid2env(), pass 1 in the checkperm parameter. Be sure you check for any invalid system call arguments, returning -E_INVAL in that case. Test your JOS kernel with user/dumbfork and make sure it works before proceeding.

一个比较冗长的练习。重点应该放在阅读 user/dumbfork.c 上，以便理解各个系统调用的作用。
在 user/dumbfork.c 中，核心是 duppage() 函数。它利用 sys_page_alloc() 为子进程分配空闲物理页，再使用sys_page_map() 将该新物理页映射到内核 (内核的 env_id = 0) 的交换区 UTEMP，方便在内核态进行 memmove 拷贝操作。在拷贝结束后，利用 sys_page_unmap() 将交换区的映射删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void
duppage(envid_t dstenv, void *addr)
{
    int r;

    // This is NOT what you should do in your fork.
    if ((r = sys_page_alloc(dstenv, addr, PTE_P|PTE_U|PTE_W)) < 0)
        panic("sys_page_alloc: %e", r);
    if ((r = sys_page_map(dstenv, addr, 0, UTEMP, PTE_P|PTE_U|PTE_W)) < 0)
        panic("sys_page_map: %e", r);
    memmove(UTEMP, addr, PGSIZE);
    if ((r = sys_page_unmap(0, UTEMP)) < 0)
        panic("sys_page_unmap: %e", r);
}

sys_exofork() 函数

该函数主要是分配了一个新的进程，但是没有做内存复制等处理。唯一值得注意的就是如何使子进程返回0。
sys_exofork()是一个非常特殊的系统调用，它的定义与实现在 inc/lib.h 中，而不是 lib/syscall.c 中。并且，它必须是 inline 的。

1
2
3
4
5
6
7
8
9
10

// This must be inlined.  Exercise for reader: why?
static inline envid_t __attribute__((always_inline))
sys_exofork(void)
{
    envid_t ret;
    asm volatile("int %2"
             : "=a" (ret)
             : "a" (SYS_exofork), "i" (T_SYSCALL));
    return ret;
}

可以看出，它的返回值是 %eax 寄存器的值。那么，它到底是什么时候返回？这就涉及到对整个 进程->内核->进程 的过程的理解。

1
2
3
4
5
6
7
8
9
10
11
12
13