背景

在boot/boot.S文件中，引入了一个全局描述符表，这个表把所有的段的基址设置为0，界限设置为0xffffffff=4GB的方式，关闭了分段管理的功能。因此虚拟地址中的段选择子字段的内容没有意义，线性地址的值总是等于虚拟地址中段内偏移的值

gdt:
  SEG_NULL                # null seg
  SEG(STA_X|STA_R, 0x0, 0xffffffff)        # code seg
  SEG(STA_W, 0x0, 0xffffffff)            # data seg

虚拟地址，线性地址与物理地址

虚拟地址(Virtual Address)是由两部分组成：段选择子(segment selector)和段内偏移(segment offset)
线性地址(Linear Address)指的是通过段地址转换机制把虚拟地址进行转换之后得到的地址
物理地址(Physical Addresses)是分页地址转换机制把线性地址进行转换之后得到的真实的内存地址
逻辑地址：虚拟地址中的段内偏移

整个流程是虚拟地址先经过分段机制转化成线性地址，之后再通过分页机制转化为物理地址。

一旦进入保护模式，我们就不能直接使用线性地址或者物理地址了。所有代码中的地址引用都是虚拟地址的形式，然后被MMU系统所转换，所以C语言中的指针其实都是虚拟地址

页表管理机制

管理页表相关的函数：

• pgdir_walk()
• boot_map_region()
• page_lookup()
• page_remove()
• page_insert()

JOS中采用的是二级页表结构，根据va高10位得到页目录表项，从一级页表里得到页表物理地址，再根据va接下去的10位得到页表表项，得到页物理地址，最后根据最后12位页内偏移，得到最终的物理地址

为了方便我们实现页表管理，inc/mmu.h提供了几个有用的宏来帮助我们操作地址：

PGNUM(la)：物理地址的页号
PDX(la)：线性地址的页目录表项
PTX(la)：线性地址的页表表项
PGOFF(la)：线性地址的页内偏移
PTE_ADDR(pte)：页表表项/页目录表项的物理地址

由于现在还没通过%cr3激活页表，因此现在的地址映射依然是之前的[KERNBASE, KERNBASE + 4MB)到[0, 4MB)。为了方便实现当前物理地址、页信息结构 、虚拟地址之间的转换，kern/pmap.h中也提供了一些有用的宏和函数：

PADDR(kva)：虚拟地址对应的物理地址
KADDR(pa)：物理地址对应的虚拟地址
page2pa(pp)：页结构pp所对应的物理页地址
page2kva(pp)：获取页结构pp对应的虚拟地址
pa2page(pa)：物理地址所在的物理页的页结构pp

页面管理函数的实现

其实我们只需页面插入与页面删除两个函数即可实现页面管理的工作，下面通过函数原型，函数功能，以及函数实现三个方面来一一分析页面管理函数。

pgdir_walk()函数
函数原型：pgdir_walk(pde_t pgdir, const void va, int create)
函数功能：返回线性地址对应的页表项(PTE)的虚拟地址

create 标志是1，如果当前va地址所属的页不存在，那么申请开辟这页
create 标志是0，仅仅是查询va地址所属的页是否存在。存在就返回对应的page table的入口地址，不存在就返回NULL

pte_t * pgdir_walk(pde_t *pgdir, const void * va, int create)
{
      unsigned int page_off;
      pte_t * page_base = NULL;
      struct PageInfo* new_page = NULL;

      unsigned int dic_off = PDX(va);
      pde_t * dic_entry_ptr = pgdir + dic_off;

      if(!(*dic_entry_ptr & PTE_P))
      {
            if(create)
            {
                   new_page = page_alloc(1);
                   if(new_page == NULL) return NULL;
                   new_page->pp_ref++;
                   *dic_entry_ptr = (page2pa(new_page) | PTE_P | PTE_W | PTE_U);
            }
           else
               return NULL;      
      }  

      page_off = PTX(va);
      page_base = KADDR(PTE_ADDR(*dic_entry_ptr));
      return &page_base[page_off];
}

boot_map_region()函数
函数原型：static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
函数功能：完成虚拟地址到物理地址的映射过程，将虚拟地址空间范围[va, va+size)映射到物理空间[pa,pa+size)的映射关系加入到页表中

这个函数主要的目的是为了设置虚拟地址UTOP之上的地址范围，这一部分的地址映射是静态的，在操作系统的运行过程中不会改变，这些页PageInfo的pp_ref域的值不会改变

在每一轮中，把一个虚拟页和物理页的映射关系存放到响应的页表项中。直到把size个字节的内存都分配完。

static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
    int nadd;
    pte_t *entry = NULL;
    for(nadd = 0; nadd < size; nadd += PGSIZE)
    {
        entry = pgdir_walk(pgdir,(void *)va, 1);    //Get the table entry of this page.
        *entry = (pa | perm | PTE_P);
        pa += PGSIZE;
        va += PGSIZE;
    }
}

page_insert()函数
函数原型：page_insert(pde_t pgdir, struct PageInfo pp, void *va, int perm)
函数功能：物理内存中页pp与虚拟地址va建立映射关系

如果va所在的虚拟内存页不存在，那么pgdir_walk的create为1，创建这个虚拟页。如果va所在的虚拟内存页存在，那么取消当前va的虚拟内存页也和之前物理页的关联，并且为va建立新的物理页联系

pp->pp_ref++语句需要放在page_remove之前，在虚拟内存页已经存在的情况，pp被释放，从而导致无法访问。

int page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
    pte_t *entry = NULL;
    entry =  pgdir_walk(pgdir, va, 1);    //Get the mapping page of this address va.
    if(entry == NULL) return -E_NO_MEM;

    pp->pp_ref++;
    if((*entry) & PTE_P)             //If this virtual address is already mapped.
    {
        tlb_invalidate(pgdir, va);
        page_remove(pgdir, va);
    }
    *entry = (page2pa(pp) | perm | PTE_P);
    pgdir[PDX(va)] |= perm;                  //Remember this step!

    return 0;
}

page_lookup()函数
函数原型：struct PageInfo page_lookup(pde_t pgdir, void va, pte_t *pte_store)
函数功能：根据虚拟地址va返回它映射的物理页信息

调用pgdir_walk函数获取这个va对应的页表项，然后判断这个页是否已经在内存中，如果在则返回这个页的PageInfo结构体指针。并且把这个页表项的内容存放到pte_store中。

疑问：pte_store设置成二级指针的意义何在？

struct PageInfo * page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
    pte_t *entry = NULL;
    struct PageInfo *ret = NULL;

    entry = pgdir_walk(pgdir, va, 0);
    if(entry == NULL)
        return NULL;
    if(!(*entry & PTE_P))
        return NULL;

    ret = pa2page(PTE_ADDR(*entry));
    if(pte_store != NULL)
    {
        *pte_store = entry;
    }
    return ret;
}

page_remove()函数
函数原型：void page_remove(pde_t pgdir, void va)
函数功能：取消虚拟地址va对应的物理页的映射关系

利用page_lookup()找到这个物理页使它无效，同时要将tlb中的对应条目无效。pp_ref减一，*pte = 0；将此页对应的页表项置0，页面回收

void page_remove(pde_t *pgdir, void *va)
{
    pte_t *pte = NULL;
    struct PageInfo *page = page_lookup(pgdir, va, &pte);
    if(page == NULL) return ;    

    page_decref(page);
    tlb_invalidate(pgdir, va);
    *pte = 0;
}

粘包

所谓的粘包问题主要是因为接收方不知道消息之间的界限，不知道一次性提取多少字节的数据所造成的。发送方引起的粘包跟TCP协议本身有关，TCP为提高传输效率，发送方往往要收集到足够多的数据后才发送一个TCP段，这样接收方就收到了粘包数据。而UDP是面向消息的协议，每个UDP段都是一条消息，应用程序必须以消息为单位提取数据，不能一次提取任意字节的数据。

粘包问题的解决方案

从本质上解决，在应用层维护消息与消息的边界

• 更复杂的应用层协议
• 用一个包体中绝不会出现的结束标志标识包结束
• 告知包的长度协议头开始固定长度的字节告知后续包长。收方先收包长字节，知道了后续包长后再收

方法三实现
我们自定义一个包体结构。先接收固定的4个字节，从中得知实际数据的长度n，再调用readn读取n个字符，这样数据包之间有了界定。

struct packet {
    int len;
    char buf[1024];
};

void do_service(int conn)
{
    struct packet recvbuf;
    int n;
    while (1)
    {
        memset(&recvbuf, 0, sizeof(recvbuf));
        int ret = readn(conn, &recvbuf.len, 4);
        if (ret == -1)
            ERR_EXIT("read error");
        else if (ret < 4)   //客户端关闭
        {
            printf("client close\n");
            break;
        }

        n = ntohl(recvbuf.len);
        ret = readn(conn, recvbuf.buf, n);
        if (ret == -1)
            ERR_EXIT("read error");
        if (ret < n)   //客户端关闭
        {
            printf("client close\n");
            break;
        }

        fputs(recvbuf.buf, stdout);
        writen(conn, &recvbuf, 4 + n);
    }
}

拆包

既然TCP传输容易出现粘包，并且在很多应用中，消息必须使用固定的格式发送。在这种情况下，我们需要拆包，按发送格式解析数据流。大二参加华为精英挑战赛，德州扑克AI。服务器发送过来的数据流就出现了粘包问题。下面简单地介绍拆包的两种方法。

动态缓冲区暂存

每一个连接动态分配一个缓冲区，同时把此缓冲区和SOCKET关联。当接收到数据时首先把此段数据存放在缓冲区中。判断缓冲区中数据长度是否够一个包头的长度，如不够，不进行拆包操作。根据包头解析出包体长度。判断缓存区中除包头外的数据长度是否够一个包体的长度，如不够，不进行拆包操作。取出整个数据包。不仅从缓冲区中拷贝出数据包，而且要把此数据包从缓存区中删除掉。把此包后面的数据移动到缓冲区的起始地址。

空间上的消耗：为每个连接动态分配一个缓冲区需要使用大量的内存
时间上的消耗：三个地方需要拷贝数据，把数据存放在缓冲区，把完整的数据包从缓冲区取出来，把数据包从缓冲区中删除。

动态缓冲区暂存的优化

TCP协议本身维护了一个缓冲区，所以我们可以直接利用TCP的缓冲区来缓存我们的数据，不需要为每一个连接分配一个缓冲区了。recv或者wsarecv都有一个参数，用来表示我们要接收多长的数据。每次根据得到的长度从缓冲区读取相应的数据字节即可。

参考链接
粘包与拆包

前言

TCP和UDP的区别

• TCP提供面向连接的、可靠的数据流传输
• UDP提供非面向连接的、不可靠的数据报传输
• TCP数据安全可靠，UDP数据传输快

TCP的三次握手

主机A向B发送连接请求
主机B对收到的主机A的报文段进行确认
主机A再次对主机B的确认进行确认

三次握手状态图(第二次ack应为x+1)

TCP的三次握手过程？为什么会采用三次握手，若采用二次握手可以吗?
采用三次握手是为了防止失效的连接请求报文段突然又传送到主机，因而产生错误

考虑这样一种特殊情况，主机A第一次发送的连接请求并没有丢失，而是因为网络节点导致延迟达到主机B。主机B以为是主机A又发起的新连接，于是主机B同意连接，并向主机A发回确认，此时主机A根本不会理会，主机B就一直在等待主机A发送数据，导致主机B的资源浪费

如果采用三次握手，由于客户端不会向服务端发出确认，服务端由于没有收到确认信息，就知道客户端没有要求建立连接，不建立该连接

SYN flood攻击

假设一个用户向服务器发送了SYN报文后突然死机或掉线，那么第三次握手无法完成，这种情况下服务器端一般会重试（再次发送SYN+ACK给客户端）并等待一段时间后丢弃这个未完成的连接，这段时间的长度称为SYN Timeout。如 果大量模拟这种情况，服务器端为了维护一个非常大的半连接列表而消耗非常多的资源

SYN flood只能攻击TCP服务，由于UDP不需要连接，故不受影响。

TCP的四次挥手

由于接收到FIN时意味将没有数据再发来，但是还是可以继续发送数据，所以断开连接时必须是四次握手

四次挥手状态图

为什么A在TIME—WAIT状态必须等待2MSL时间呢？

• 为了保证A发送的最后一个ACK报文段能够到达B
  若该ACK报文段很有可能丢失，如果A在TIME—WAIT状态不等待一段时间就直接释放连接到CLOSED状态，那么就无法收到B重传的FIN+ACK报文段，也不会再发送一次确认ACK报文段，那么B就无法正常进入CLOSED状态

• 防止已失效的请求连接出现在本连接中
  在连接处于2MSL等待时，任何迟到的报文段将被丢弃，这样可以使下一个新的连接中不会出现这种旧的连接之前延迟的报文段。

前言

static extern const三个笔试面试出场率极高的关键字，之前只是拿起来就用，出了问题就Google。为了备战春招，就特意花了些时间整理了下。思路理顺了，不管怎么考查也不怕了。

static静态成员变量

总的来说，有一下三点：

• 改变变量的作用域
• 延长变量的生命周期,程序结束才会销毁
• 在同一作用域或文件中,只被初始化一次

C static静态成员变量

在C语言中，static可以用来修饰局部变量，全局变量以及函数。在不同的情况下static的作用不尽相同

修饰局部变量

局部变量是存放在栈区，并且局部变量的生命周期在该语句块执行结束时便结束了。但是如果用static进行修饰的话，变量便存放在静态数据区，其生命周期一直持续到整个程序执行结束

虽然用static对局部变量进行修饰过后，其生命周期以及存储空间发生了变化，但是其作用域并没有改变，其仍然是一个局部变量，作用域仅限于该语句块。在用static修饰局部变量后，该变量只在初次运行时进行初始化工作，且只进行一次

void fun()
{
    static int a=1; a++;
    printf("%d\n",a);
}

int main(void)
{
    fun();
    fun();
    return 0;  
}

程序执行结果为: 2 3
说明在第二次调用fun()函数时，a的值为2，并且没有进行初始化赋值，直接进行自增运算。

修饰全局变量

一个全局变量，它既可以在本源文件中被访问到，也可以在同一个工程的 其它源文件中被访问(需用extern进行声明）

//file1.c
int a=1;

//file2.c
#include<stdio.h>
extern int a;
int main(void)
{
    printf("%d\",a);
    return 0;
}

执行结果为 1
但是如果在file1.c中把int a = 1改为static int a=1;在file2.c是无法访问到变量a。因为static对全局变量进行修饰改变了其作用域的范围，由原来的整个工程可见变为本源文件可见

修饰函数

用static修饰函数的话，情况与修饰全局变量大同小异，改变了函数的作用域

C++ static静态成员变量

有时候我们希望在多个对象之间共享数据，对象a改变了某份数据后对象 b可以检测到。共享数据的典型使用场景是计数，以前面的Student类为例，如果我们想知道班级中共有多少名学生，就可以设置一份共享的变量，每次创建对象时让该变量加1。

类静态成员变量等同于全局变量。声明一个类静态成员变量做到多个实例共享一个全局变量。在C++中，我们可以使用静态成员变量来实现多个对象共享数据的目标

static成员变量属于类，不属于某个具体的对象，即使创建多个对象，也只为 m_total分配一份内存，所有对象使用的都是这份内存中的数据。当某个对象修改了m_total，也会影响到其他对象。

static成员变量必须在类声明的外部初始化 type class::name = value;
静态成员变量既可以通过对象名访问，也可以通过类名访问，但要遵循 private、protected 和 public关键字的访问权限限制。

//通过类类访问 static 成员变量
Student::m_total = 10;
//通过对象来访问 static 成员变量
Student stu("小明", 15, 92.5f);
stu.m_total = 20;
//通过对象指针来访问 static 成员变量
Student *pstu = new Student("李华", 16, 96);
pstu -> m_total = 20;

static成员变量的内存既不是在声明类时分配，也不是在创建对象时分配，而是在（类外）初始化时分配。反过来说，没有在类外初始化的static成员变量不能使用

static成员变量不占用对象的内存，即使不创建对象也可以访问。static成员变量和普通的static变量类似，都在内存分区中的全局数据区分配内存到程序结束时才释放。这就意味着，static成员变量不随对象的创建而分配内存，也不随对象的销毁而释放内存。而普通成员变量在对象创建时分配内存，在对象销毁时释放内存

初始化时可以赋初值，也可以不赋值。如果不赋值，那么会被默认初始化为 0。而动态数据区（堆区、栈区）变量的默认值是不确定的，一般认为是垃圾值。

C++ static静态成员函数

静态成员函数与普通成员函数的根本区别在于：普通成员函数有this指针，可以访问类中的任意成员；而静态成员函数没有this指针，只能访问静态成员（包括静态成员变量和静态成员函数）

//程序报错,{}则表明定义实现
static int fun4() {};

和静态成员变量类似，静态成员函数在声明时要加 static，在定义时不能加 static。静态成员函数可以通过类来调用（一般都这样做），也可以通过对象来调用

extern关键字

在C语言中，修饰符extern用在变量或者函数的声明前，用来说明此变量/函数是在别处已定义，要在此处引用

调用其它文件中的函数和变量，只需把该文件用#include包含进来即可，为啥要用extern？
extern会加速程序的编译过程，能节省时间

在C++中extern还有另外一种作用，指示C或者C＋＋函数的调用规范。在C++中调用C库函数，就需要在C++程序中用extern “C”声明要引用的 函数。

参考链接
C++ static静态成员变量

前言

static extern const三个笔试面试出场率极高的关键字，之前只是拿起来就用，出了问题就Google。为了备战春招，就特意花了些时间整理了下。思路理顺了，不管怎么考查也不怕了。

static静态成员变量

总的来说，有一下三点：

• 改变变量的作用域
• 延长变量的生命周期,程序结束才会销毁
• 在同一作用域或文件中,只被初始化一次

C static静态成员变量

在C语言中，static可以用来修饰局部变量，全局变量以及函数。在不同的情况下static的作用不尽相同

修饰局部变量

局部变量是存放在栈区，并且局部变量的生命周期在该语句块执行结束时便结束了。但是如果用static进行修饰的话，变量便存放在静态数据区，其生命周期一直持续到整个程序执行结束

虽然用static对局部变量进行修饰过后，其生命周期以及存储空间发生了变化，但是其作用域并没有改变，其仍然是一个局部变量，作用域仅限于该语句块。在用static修饰局部变量后，该变量只在初次运行时进行初始化工作，且只进行一次

void fun()
{
    static int a=1; a++;
    printf("%d\n",a);
}

int main(void)
{
    fun();
    fun();
    return 0;  
}

程序执行结果为: 2 3
说明在第二次调用fun()函数时，a的值为2，并且没有进行初始化赋值，直接进行自增运算。

修饰全局变量

一个全局变量，它既可以在本源文件中被访问到，也可以在同一个工程的 其它源文件中被访问(需用extern进行声明）

//file1.c
int a=1;

//file2.c
#include<stdio.h>
extern int a;
int main(void)
{
    printf("%d\",a);
    return 0;
}

执行结果为 1
但是如果在file1.c中把int a = 1改为static int a=1;在file2.c是无法访问到变量a。因为static对全局变量进行修饰改变了其作用域的范围，由原来的整个工程可见变为本源文件可见

修饰函数

用static修饰函数的话，情况与修饰全局变量大同小异，改变了函数的作用域

C++ static静态成员变量

有时候我们希望在多个对象之间共享数据，对象a改变了某份数据后对象 b可以检测到。共享数据的典型使用场景是计数，以前面的Student类为例，如果我们想知道班级中共有多少名学生，就可以设置一份共享的变量，每次创建对象时让该变量加1。

类静态成员变量等同于全局变量。声明一个类静态成员变量做到多个实例共享一个全局变量。在C++中，我们可以使用静态成员变量来实现多个对象共享数据的目标

static成员变量属于类，不属于某个具体的对象，即使创建多个对象，也只为 m_total分配一份内存，所有对象使用的都是这份内存中的数据。当某个对象修改了m_total，也会影响到其他对象。

static成员变量必须在类声明的外部初始化 type class::name = value;
静态成员变量既可以通过对象名访问，也可以通过类名访问，但要遵循 private、protected 和 public关键字的访问权限限制。

//通过类类访问 static 成员变量
Student::m_total = 10;
//通过对象来访问 static 成员变量
Student stu("小明", 15, 92.5f);
stu.m_total = 20;
//通过对象指针来访问 static 成员变量
Student *pstu = new Student("李华", 16, 96);
pstu -> m_total = 20;

static成员变量的内存既不是在声明类时分配，也不是在创建对象时分配，而是在（类外）初始化时分配。反过来说，没有在类外初始化的static成员变量不能使用

static成员变量不占用对象的内存，即使不创建对象也可以访问。static成员变量和普通的static变量类似，都在内存分区中的全局数据区分配内存到程序结束时才释放。这就意味着，static成员变量不随对象的创建而分配内存，也不随对象的销毁而释放内存。而普通成员变量在对象创建时分配内存，在对象销毁时释放内存

初始化时可以赋初值，也可以不赋值。如果不赋值，那么会被默认初始化为 0。而动态数据区（堆区、栈区）变量的默认值是不确定的，一般认为是垃圾值。

C++ static静态成员函数

静态成员函数与普通成员函数的根本区别在于：普通成员函数有this指针，可以访问类中的任意成员；而静态成员函数没有this指针，只能访问静态成员（包括静态成员变量和静态成员函数）

//程序报错,{}则表明定义实现
static int fun4() {};

和静态成员变量类似，静态成员函数在声明时要加 static，在定义时不能加 static。静态成员函数可以通过类来调用（一般都这样做），也可以通过对象来调用

extern关键字

在C语言中，修饰符extern用在变量或者函数的声明前，用来说明此变量/函数是在别处已定义，要在此处引用

调用其它文件中的函数和变量，只需把该文件用#include包含进来即可，为啥要用extern？
extern会加速程序的编译过程，能节省时间

在C++中extern还有另外一种作用，指示C或者C＋＋函数的调用规范。在C++中调用C库函数，就需要在C++程序中用extern “C”声明要引用的 函数。

参考链接
C++ static静态成员变量

在前面的文章中，我们在DartNet覆盖网络（ON）层上直接实现了SRT。现在我们需要添加路由和分组转发到DartNet。本篇文章将介绍DartNet网络层的设计，并实现简单网络协议（SNP），以提供类似于在互联网路由器上运行的IP协议和路由的转发。

本篇文章的具体内容：

• SNP API
• SNP路由协议
• SNP数据包转发
• SNP过程实现

DartNet

在DartNet中，在每对相邻节点之间存在TCP连接。在每个节点上，存在覆盖网络（ON）层，简单网络协议（SNP）层，简单可靠传输（SRT）层和应用层

ON进程包含n + 1个线程，其中n是相邻节点的数目。对于这些ON线程，一个是主线程，另外n个线程是listen_to_neighbor线程。实现覆盖网络（ON）层

SNP进程包含3个线程：主线程，pkthandler线程和routeupdate_daemon线程。实现简单网络协议（SNP）层

SRT进程包含两个线程：主线程和seghandler线程。实现SRT层和应用层。

DartNet实现图

SNP API

DartNet API调用图

SNP进程向SRT进程提供两个函数：snp_sendseg（）和snp_recvseg（）。我们之前实现了这两个SNP API。然而在那时，这些SNP API是使用两个节点之间的直接TCP连接来实现的。在这里我们将使用ON层重新实现这些API

SRT进程调用snp_sendseg（）将段发送到目标节点。当SRT进程调用snp_sendseg（）时，sendseg_arg_t结构被发送到本地SNP进程。本地SNP进程使用getsegToSend（）接收此sendseg_arg_t结构。然后，本地SNP进程将每个分段封装到一个分组中，并使用overlay_sendpkt（）将分组发送到下一跳。

SNP进程通过调用overlay_recvpkt（）函数从本地ON进程接收数据包。在SNP过程接收到分组之后，SNP过程从分组的数据字段中提取分段，并且向本地SRT过程转发sendseg_arg_t结构。本地SRT进程调用snp_recvseg（）接收此sendseg_arg_t结构。

sendseg_arg_t在seg.h中定义

//This is the data structure exchanged between the SNP process and the SRT process.
//It contains a node ID and a segment.
//For snp_sendseg(), the node ID is the destination node ID of the segment.
//For snp_recvseg(), the node ID is the source node ID of the segment.

typedef struct sendsegargument {
  int nodeID;   //node ID
  seg_t seg;    //a segment
} sendseg_arg_t;

SNP路由协议

SNP路由协议是距离矢量路由协议。SNP路由协议使用链路成本作为路由度量。当两个节点之间存在多条路径时，应选择总链路成本较小的路径。我们先看看SNP路由协议使用的数据结构。然后讨论SNP路由算法。

SNP路由协议使用3个表：邻居成本表，距离向量表和路由表。我们将一一讨论它们。覆盖中的每个节点都有一个SNP进程在其上运行，每个SNP进程维护一个邻居成本表，一个距离向量表和一个路由表，用于运行它的节点。

邻居链路成本表

节点的邻居成本表包含到其所有邻居的直接链路成本。邻居成本表具有n个条目，其中n是节点的邻居的数量。邻居成本表项在network / nbrcosttable.h中定义。

//neighbor cost table entry definition

typedef struct neighborcostentry {
  unsigned int nodeID;  //neighbor’s node ID
  unsigned int cost;    //direct link cost to the neighbor
} nbr_cost_entry_t;

当SNP过程开始时，动态创建邻居表。邻居成本表通过解析topology.dat中包含的拓扑信息来初始化。

距离向量表

距离向量表包含从源节点到网络中所有节点的估计的链路成本。距离向量结构在network / dvtable.h中定义

//distance vector entry definition

typedef struct distancevectorentry {
  int nodeID;         //destination nodeID
  unsigned int cost;  //estimated link cost to the destination
} dv_entry_t;

//distance vector definition

typedef struct distancevector {
  int         nodeID;   //source nodeID
  dv_entry_t  *dvEntry; //an array of N dv_entry_ts, each of which contains the
                //destination node ID and the estimated link cost to the destination
                //from the source node. N is the total number of nodes in the overlay.
} dv_t;

dv_t是一个距离向量，其包含源nodeID和N个dv_entry_t结构的数组，其中N是覆盖中的节点总数(表中的横坐标)。dv_entry_t包含目的节点ID和到目的地节点的链路成本。距离向量表包含n + 1个距离向量 (表中的纵坐标)，其中n是节点的邻居的数目，另一个为节点本身。

当SNP过程开始时，动态创建距离向量表。使用来自topology.dat文件的链路成本信息来初始化节点自身的距离向量。目的地节点为节点本身，则链路成本为0。目的地节点是相邻节点，链路成本是直接链路成本。否则，估计的链接成本为INFINITE_COST。距离向量表中的相邻节点的其他距离向量用INFINITE_COST初始化。

路由表

路由表是具有MAX_ROUTINGTABLE_SLOTS个元素的散列表。每个元素指向一个routingtable_entry_t链表。使用链表解决冲突。routingtable_entry_t结构和路由表本身在network/routingtable.h中定义。

路由表

//routingtable_entry_t is the routing entry contained in the routing table.

typedef struct routingtable_entry {
  int destNodeID;                   //destination node ID
  int nextNodeID;                   //next node ID to which the packet should be forwarded
  struct routingtable_entry* next;  //pointer to the next routingtable_entry_t in the same routing table slot
} routingtable_entry_t;

//A routing table is a hash table containing MAX_ROUTINGTABLE_SLOTS slots.
//Each slot is a linked list of routing entries.

typedef struct routingtable {
  routingtable_entry_t* hash[MAX_ROUTINGTABLE_SLOTS];
} routingtable_t;

routing_entry_t结构包含此目标节点的ID和下一跳的nodeID。路由表是一个哈希表。makehash（）是哈希表的散列函数，键值为目标节点ID，散列值为目标节点在哈希表的槽号

要将路由entry添加到路由表，首先使用散列函数makehash（）来获取应存储此路由entry槽号。然后将路由entry插入该槽中的链表中。要查找一个目标路由entry，过程与添加类似

通过为所有相邻节点添加路由entry来初始化路由表，对于作为目的地节点的每个相邻节点，将下一跳节点设置为相邻节点本身。

SNP路由算法

SNP路由协议使用距离向量路由算法。具体原理与实现，可以自行阅读《计算机网咯：自顶向下方法》中的距离矢量（DV）路由算法。

当SNP进程启动时，它启动一个routeupdate_daemon线程。routeupdate_daemon线程每ROUTEUPDATE_INTERVAL时间间隔广播一个路由更新包。该路由更新包的内容是源节点的距离向量。接收方的距离向量表和路由表根据此距离向量信息 更新相应的表项。接收方不会转发接收到的路由更新包，路由更新只会被源节点的直接邻居接收。

SNP路由算法实现过程中，用图片的形式，表示各表内容的变化。

DartNet拓扑

邻居链路成本表

初始化后，节点的距离向量表和路由表显示在图的左侧。
在所有节点接收到来自它们的邻居的所有第一路由更新分组之后，距离向量表更新并且在图的右侧示出

在所有节点从其邻居接收到第二路由更新分组之后的距离向量表和路由表

数据包转发

在SNP过程中，分组转发在pkthandler线程中完成。pkthandler线程通过调用overlay_recvpkt（）从ON进程接收数据包。

如果接收的分组是SNP分组，并且目的地节点是该节点，则pkthandler线程将分组转发到SRT进程。
如果分组是SNP分组，并且目的地节点不是该节点，则pkthandler线程根据路由表将分组转发到下一跳。
如果该分组是路由更新分组，则pkthandler线程使用我们上面描述的SNP路由算法来更新距离向量表和路由表。

SNP过程实现

SNP作为进程运行。覆盖层中的每个节点都有一个SNP进程在其上运行。SNP进程的代码如下所示：

printf("network layer is starting, pls wait...\n");

  //initialize global variables
  nct = nbrcosttable_create();
  dv = dvtable_create();
  dv_mutex = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t));
  pthread_mutex_init(dv_mutex,NULL);
  routingtable = routingtable_create();
  routingtable_mutex = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t));
  pthread_mutex_init(routingtable_mutex,NULL);
  overlay_conn = -1;
  transport_conn = -1;

  nbrcosttable_print(nct);
  dvtable_print(dv);
  routingtable_print(routingtable);

  //register a signal handler which is used to terminate the process
  signal(SIGINT, network_stop);

  //connect to local ON process
  overlay_conn = connectToOverlay();
  if (overlay_conn<0) {
    printf("can’t connect to overlay process\n");
    exit(1);
  }

  //start a thread that handles incoming packets from ON process
  pthread_t pkt_handler_thread;
  pthread_create(&pkt_handler_thread,NULL,pkthandler,(void*)0);

  //start a route update thread
  pthread_t routeupdate_thread;
  pthread_create(&routeupdate_thread,NULL,routeupdate_daemon,(void*)0);

  printf("network layer is started...\n");
  printf("waiting for routes to be established\n");
  sleep(NETWORK_WAITTIME);
  routingtable_print(routingtable);

  //wait connection from SRT process
  printf("waiting for connection from SRT process\n");
  waitTransport();

当SNP过程开始时，首先建表并初始化这些表。SNP过程还创建和初始化两个互斥：一个用于向量表，另一个用于路由表。

overlay_conn为SNP进程与本地ON进程的连接的TCP描述符和transport_conn为SNP进程与本地SRT进程的连接的TCP描述符。当SNP过程开始时，SNP过程将overlay_conn和transport_conn初始化为-1作为无效。

然后，SNP进程将信号处理程序network_stop（）注册到信号SIGINT，使得当接收到SIGINT信号时，调用network_stop（）以终止SNP进程。SNP进程调用函数connectToOverlay（）连接到端口OVERLAY_PORT上的本地ON进程

在建立与ON进程的TCP连接之后，SNP进程启动pkthandler线程。接着启动routeupdate_daemon线程。然后，SNP过程等待一段时间，以便路由表更新完成

SNP进程然后调用waitTransport（）函数在NETWORK_PORT上打开一个端口来等待来自本地SRT进程的TCP连接。连接本地SRT进程后，waitTransport（）函数接收sendseg_arg_t结构，其中包含来自SRT进程的段及其目标nodeID。将接收的段封装重新封装，并使用overlay_sendpkt发送到下一跳。从路由表中检索下一跳的节点ID。

SNP过程在接收到SIGINT信号时终止。当接收到SIGINT信号时，信号处理器函数network_stop（）通过关闭所有TCP连接，释放所有动态分配的内存并终止SNP进程来停止覆盖

我们已经实现了DartNet的SRT协议。之所以设计覆盖层，因为我们不能在互联网的真实路由器上运行我们的简单网络协议（SNP）。这是一个非常酷的方法来绕过不能更改路由器代码的限制。带上你的好奇心，开始了解它吧。在本篇文章，我们将讨论覆盖网络层的设计

本篇文章的具体内容：

• 覆盖层拓扑和节点ID
• 覆盖层的构造
• 邻居表
• SNP数据包格式
• 覆盖过程实现
• 测试叠加

覆盖层拓扑和节点ID

DartNet建立在覆盖层网络上。这个覆盖层网络的拓扑在topology.dat文件中定义。topology.dat中的每一行具有以下格式：
host1 host2 link cost

其中host1是计算机的主机名，host2是另一台计算机的主机名，link cost是这两个主机之间的直接链接开销。

覆盖拓扑

在DartNet中，使用nodeID来标识主机。nodeID与TCP/IP中的IP地址具有类似 的作用。nodeID是由主机IP地址的后8位表示的整数。例如，IP地址为“202.120.95.36”的主机作为节点ID 36。

覆盖层的构造

我们的覆盖层网络中有4个节点。在每个节点上，有一个ON进程和SNP进程在运行。ON进程和SNP进程与本地TCP连接相连。ON过程还保持与所有相邻节点的TCP连接。例如，左上节点在覆盖网络中具有3个相邻节点。存在到每个相邻节点的TCP连接。

覆盖过程图

节点到邻居的每个TCP连接，都有一个listen_to_neighbor线程。listen_to_neighbor线程保持从该邻居接收分组并且将接收的分组转发到SNP进程。对于ON进程和SNP进程之间的TCP连接，主线程继续从SNP进程接收包含分组和下一跳的nodeID的sendpkt_arg_t结构，并将这些分组发送到下一跳节点。

左上节点的ON线程图

邻居表

ON进程维护邻居表。邻居表包含相邻节点的信息。邻居表在overlay / neighbortable.h中定义

//neighbortable entry definition
//a neighbor table contains n entries where n is the number of neighbors

typedef struct neighborentry {
  int nodeID;       //neighbor’s node ID
  in_addr_t nodeIP; //neighbor’s IP address
  int conn;         //TCP connection’s socket descriptor to the neighbor
} nbr_entry_t;

邻居表具有n个entry，其中n是覆盖层中的邻居的数目。邻居表中的每个entry包含邻居的nodeID，邻居的IP地址和TCP连接对邻居的套接字描述符。

SNP数据包格式

ON过程从覆盖层网络接收SNP分组并转发到SNP层。ON过程还从SNP层接收SNP分组，并转发到覆盖层网络。SNP包格式在common / pkt.h中定义

数据包格式图

//packet type definition, used for type field in the SNP header
#define ROUTE_UPDATE 1
#define SNP 2

//SNP packet format definition
typedef struct snpheader {
  int src_nodeID;               //source node ID
  int dest_nodeID;              //destination node ID
  unsigned short int length;    //length of the data in the packet
  unsigned short int type;      //type of the packet
} snp_hdr_t;

typedef struct packet {
  snp_hdr_t header;
  char data[MAX_PKT_LEN];
} snp_pkt_t;

如果分组类型等于SNP，则分组中包含的数据将是一个段（包括段头和数据）。如果分组的类型是ROUTE_UPDATE，则节点的距离向量包含在分组的数据字段中。

//A route update entry

typedef struct routeupdate_entry {
  unsigned int nodeID;  // destination nodeID
  unsigned int cost; // link cost between source (src_nodeID in header) and destination nodes
} routeupdate_entry_t;

//route update packet format

typedef struct pktrt{
  unsigned int entryNum;  // number of entries contained and in this route update packet
  routeupdate_entry_t entry[MAX_NODE_NUM];
} pkt_routeupdate_t;

路由更新数据包格式

覆盖层网络API

通过TCP连接发送数据时，我们使用分隔符。使用“！＆”表示数据传输的开始，使用“！＃”表示数据传输的结束。因此，当数据通过TCP连接发送时，首先发送“！＆”，然后发送数据，然后发送“！＃”。接收方只需相应地根据分割符进行解析接受即可

API的说明

ON进程为SNP进程提供两个函数调用：overlay_sendpkt（）和overlay_recvpkt（）。

typedef struct sendpktargument {
  int nextNodeID;    //node ID of the next hop
  pkt_t pkt;         //the packet to be sent
} sendpkt_arg_t

int overlay_sendpkt(int nextNodeID, pkt_t* pkt, int overlay_conn)
int overlay_recvpkt(pkt_t* pkt, int overlay_conn)

ON进程使用getpktToSend（）获取一个sendpkt_arg_t数据结构，该结构包含一个数据包和来自SNP进程的下一跳的nodeID。ON进程使用forwardpktToSNP（）将数据包转发到SNP进程。

int getpktToSend(pkt_t* pkt, int* nextNode,int network_conn);
int forwardpktToSNP(pkt_t* pkt, int network_conn);

ON进程使用sendpkt（）向邻居发送数据包，并使用recvpkt（）从邻居接收数据包。

int sendpkt(pkt_t* pkt, int conn);
int recvpkt(pkt_t* pkt, int conn);

覆盖过程实现

ON过程的代码如下

//start overlay initialization
  printf("Overlay: Node %d initializing...\n", topology_getMyNodeID());

  //create a neighbor table
  nt = nt_create();

  //initialize network_conn to -1, means no network layer process is connected yet
  network_conn = -1;

  //register a signal handler which is used to terminate the process
  signal(SIGINT, overlay_stop);

  //print out all the neighbors
  int nbrNum = topology_getNbrNum();
  int i;
  for(i=0;i<nbrNum;i++) {
    printf("Overlay: neighbor %d:%d\n",i+1,nt[i].nodeID);
  }

  //start the waitNbrs thread to wait for incoming connections
  //from neighbors with larger node IDs

  pthread_t waitNbrs_thread;
  pthread_create(&waitNbrs_thread,NULL,waitNbrs,(void*)0);

  //wait for neighboring nodes to start the overlay process

  sleep(OVERLAY_START_DELAY);

  //connect to neighbors with smaller node IDs

  connectNbrs();

  //wait for waitNbrs thread to return

  pthread_join(waitNbrs_thread,NULL);

  //at this point, all connections to the neighbors are created

  //create threads listening to all the neighbors

  for(i=0;i<nbrNum;i++) {
    int* idx = (int*)malloc(sizeof(int));
    *idx = i;
    pthread_t nbr_listen_thread;
    pthread_create(&nbr_listen_thread,NULL,listen_to_neighbor,(void*)idx);
  }

  printf("Overlay: node initialized...\n");
  printf("Overlay: waiting for connection from SNP process...\n");

  //waiting for connection from  SNP process

  waitNetwork();

当ON进程启动时，创建并初始化邻居表。然后注册信号处理器overlay_stop（）用于信号SIGINT，当接收到SIGINT信号时，调用overlay_stop（）以终止ON过程。

建立到覆盖网络中的所有邻居的TCP连接。在我们的设计中，如果两个节点之间存在链接，则具有较小节点ID的节点将在CONNECTION_PORT上打开一个TCP端口，具有较大节点ID的节点将连接到该节点

ON进程启动waitNbrs线程，然后一段时间后调用connectNbrs（）函数。waitNbrs线程在CONNECTION_PORT上打开一个TCP端口，并等待来自节点ID比自身节点ID大的所有邻居的传入连接。待所有传入连接建立后，waitNbrs线程返回。

对于与邻居的每个TCP连接，ON过程启动listen_to_neighbor线程。每个listen_to_neighbor线程使用recvpkt（）保持从邻居接收数据包，并使用forwardpktToSNP（）将数据包转发到SNP进程。

当所有的listen_to_neighbor线程都启动，ON进程调用waitNetwork（）函数。此函数在OVERLAY_PORT上打开一个TCP端口，并等待来自本地SNP进程TCP连接。建立连接后，waitNetwork（）函数继续从SNP进程接收sendpkt_arg_t结构。之后waitNetwork（）使用sendpkt（）将数据包发送到覆盖层网络中的下一跳。当SNP进程断开时，waitNetwork（）关闭连接并等待来自本地SNP进程的下一个连接

ON进程在接收到SIGINT信号时终止。关闭所有TCP连接，释放所有动态分配的内存并终止ON过程来停止覆盖

测试叠加层

SNP进程连接到本地ON进程，并且请求本地过程周期性地广播路由更新分组。SNP过程应该能够从其邻居接收路由更新分组。通过发送和接收路由更新分组，我们可以验证覆盖是否正常工作。

printf("network layer is starting, pls wait...\n");

  //initialize global variables

  overlay_conn = -1;

  //register a signal handler which will kill the process

  signal(SIGINT, network_stop);

  //connect to overlay

  overlay_conn = connectToOverlay();
  if(overlay_conn<0) {
    printf("can’t connect to ON process\n");
    exit(1);
  }

  //start a thread that handles incoming packets from overlay

  pthread_t pkt_handler_thread;
  pthread_create(&pkt_handler_thread,NULL,pkthandler,(void*)0);

  //start a route update thread

  pthread_t routeupdate_thread;
  pthread_create(&routeupdate_thread,NULL,routeupdate_daemon,(void*)0);

  printf("network layer is started...\n");

  //sleep forever
  while(1) {
    sleep(60);
  }

在ON进程中调用waitNetwork（）后，SNP进程启动。当SNP过程开始时，SNP过程首先通过将与本地ON过程的连接设置为-1作为无效。

然后SNP进程调用connecToOverlay（）函数连接到端口OVERLAY_PORT上的ON进程。在建立与ON进程的TCP连接之后，SNP进程启动pkthandler线程处理来自ON进程的传入数据包，启动routeupdate_daemon线程广播路由更新。目前，广播路由更新报文。广播通过将SNP分组报头中的dest_nodeID设置为BROADCAST_NODEID来完成，并使用overlay_sendpkt（）将路由更新分组发送到广播地址BROADCAST_NODEID

最后SNP进程进入while循环，并永久休眠。当接收到SIGINT信号时终止SNP进程。

socket套接字工作于TCP/IP协议中应用层和传输层之间的一个抽象，使得网络上不同的计算机可以进行通信。

在客户端上建立套接字的步骤如下：

• socket()创建套接字
• connect()将套接字连接到服务器
• 使用read()和write()发送和接收数据

在服务器端建立套接字的步骤如下：

• socket()创建套接字
• 使用bind()系统调用将套接字绑定到地址，地址由主机上的端口号组成。
• listen()监听连接
• accept()接受连接。此调用通常阻塞，直到客户端与服务器连接
• 发送和接收数据

CS模式下API图

服务端

sockfd和newsockfd文件描述符，这两个变量存储套接字系统call和accept系统调用返回的

struct sockaddr_in serv_addr，cli_addr;

sockaddr_in是互联网地址结构。定义在。变量serv_addr为服务器的地址，cli_addr是客户端的地址。

struct sockaddr_in
{
    short sin_family;
    u_short sin_port;
    struct in_addr sin_addr;
    char sin_zero [8];
};

in_addr结构，在相同的头文件中定义，只包含一个无符号长整型s_addr。

if (argc < 2) 
{
    fprintf(stderr,"ERROR, no port provided\n");
    exit(1);
}

用户需要传入服务器的端口号，若未执行此操作就报错

sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd < 0)
    error("ERROR opening socket");

socket()创建一个套接字，它需要三个参数。
第一个是套接字的地址域。2种：共享文件系统的两个进程的unix域，以及Internet上任意两个主机的Internet域。符号常数AF_UNIX用于前者，而AF_INET后者

第二个参数是套接字的类型。2种：来自文件或管道的流套接字，以及以块读取消息的数据报套接字。符号常量是SOCK_STREAM和SOCK_DGRAM。

第三个参数是协议。如果此参数为零，操作系统将选择最适当的协议。它将选择TCP作为流套接字，UDP选择数据报套接字。

套接字调用返回文件描述符表的一个表项。此值用于对此套接字的所有后续引用。如果套接字调用失败，它返回-1。在这种情况下，程序显示和错误消息并退出。
上面是套接字调用的简化描述；还有许多其他选择域和类型，但这些是最常见的

bzero((char *) &serv_addr, sizeof(serv_addr));

该函数bzero()将缓冲区中的所有值设置为零。它有两个参数，第一个是指向缓冲区的指针，第二个是缓冲区的大小。因此，此行初始化 serv_addr为零。

portno = atoi(argv[1]);

服务器将侦听连接的端口号作为参数传入，并使用该atoi()函数将其从数字字符串转换为整数

serv_addr.sin_family = AF_INET;

short sin_family用于记录地址，它始终设置为符号常量AF_INET。

serv_addr.sin_addr.s_addr = INADDR_ANY;

unsigned long s_addr，记录主机的IP地址。对于服务器，这将始终是运行服务器的计算机的IP地址，INADDR_ANY是获得此地址的符号常量。

serv_addr.sin_port = htons(portno);

unsigned short sin_port，记录端口号。这里需要使用将主机字节顺序中的端口号转换为网络字节顺序中的端口号。

if (bind(sockfd, (struct sockaddr *) &serv_addr,
        sizeof(serv_addr)) < 0)
error("ERROR on binding");

bind()将套接字绑定到一个地址上。它需要三个参数：套接字文件描述符，绑定的地址和绑定的地址的大小。第二个参数是sockaddr类型，但传入的是sockaddr_in，因此必须将它转换为正确的类型。
bind()过程失败的原因有很多，最明显的是该套接字已经在这台机器上使用。

listen(sockfd,5);

listen（sockfd，5）;
listen监听该套接字连接。第一个参数是套接字文件描述符，第二个参数是等待连接的队列大小

clilen = sizeof(cli_addr);
newsockfd = accept(sockfd, (struct sockaddr *) &cli_addr, &clilen);
if (newsockfd < 0)
    error("ERROR on accept");

accept()导致进程阻塞，直到客户端连接到服务器。当连接成功时，它唤醒该进程。返回一个新的文件描述符，并使用这个新的文件描述符完成此连接上的所有通信。第二个参数是指向连接另一端的客户端地址的引用指针，第三个参数是此结构的大小。

bzero(buffer,256);
n = read(newsockfd,buffer,255);
if (n < 0) error("ERROR reading from socket");
printf("Here is the message: %s\n",buffer);

使用bzero()函数初始化缓冲区，然后从套接字读取信息。read()使用新的文件描述符，阻塞直到有一些东西可读，即客户端已经执行write()后。它将读取套接字中的字符，并返回读取的字符数。

n = write(newsockfd,"I got your message",18);
if (n < 0) error("ERROR writing to socket");

一旦建立了连接，两端都可以读写。

内存管理模块分为2部分：物理页面管理和页表管理。前者强调对机器拥有的物理内存的管理，包括建立对应的数据结构、处理分配和回收动作等。而后者主要是强调利用Intel x86系列处理器的页式地址管理功能， 完成(虚拟)线性地址到物理地址的转换，包括建立页目录、页表等。

物理页面管理相关的函数：

• boot_alloc()
• page_init()
• page_alloc()
• page_free()

背景知识

JOS的启动过程是先把bootsector的内容读到0x7c00处，bootsector中的代码开始执行后，会从磁盘上紧接着自己的第2个扇区开始，一直读8个扇区的内容(一共是8×512=4KB，ELF头的大小)到0x10000(64KB)的地方，然后通过对ELF头的解析，得到kernel模块编译出来后所占的大小，并将kernel读到物理内存0x100000(1MB)开始的地方。

然后设置好GDT，并调用i386_init()函数，而i386_init()函数在将自己的BSS区域清零后，调用cons_init()函数设置屏幕显示，为cprintf的运行做 好准备。随后调用i386_detect_memory()函数和i386_vm_init()。后者就是我们内存管理的主要函数了

.bss 节:未初始化的全局变量部分，一部分不会在磁盘有存储空间，因为这些变量并没有被初始化，因此全部默认为0，在将这节装入到内存的时候程序需要为其分配相应大小的初始值为0的内存空间

在调用i386_init()后，系统将重载GDT，新的GDT：

SEG_NULL # null seg
SEG(STA_X|STA_R， -KERNBASE， 0xffffffff) # code seg
SEG(STA_W， -KERNBASE， 0xffffffff) # data seg

新GDT后两项的base，它们是-KERNBASE。如果KERNBASE=0xF0000000，则
GDT的base=0x10000000

页面管理

JOS内核是以页(page)为最小单位，通过链表来管理内存的。它使用MMU来映射，保护每一块被分配出去的内存。操作系统必须要追踪记录哪些内存区域是空闲的，哪些是被占用的。

页面管理相关的数据结构

typedef uint32_t pte_t;
typedef uint32_t pde_t;

struct PageInfo {
    // Next page on the free list.
    // 空闲页面链表next指针
    struct PageInfo *pp_link;

    // pp_ref is the count of pointers (usually in page table entries)
    // to this page, for pages allocated using page_alloc.
    // Pages allocated at boot time using pmap.c's
    // boot_alloc do not have valid reference count fields.

    // 页面状态：空闲/占用
    // 多个不同的虚拟地址被同时映射到相同的物理页上,PageInfo结构体的pp_ref
    // 被位于虚拟地址UTOP之下的虚拟页所映射的次数
    uint16_t pp_ref;
};

下面通过mem_init函数有关页面管理的代码进行简要的分析和流程的梳理。部分代码如下

void mem_init(void)
{
    i386_detect_memory();

    // create initial page directory.
    // kern_pgdir指向操作系统的页目录表，这个页紧跟着操作系统内核之后
    kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
    // 分配一个页的大小，并且将这部分内存清0
    memset(kern_pgdir, 0, PGSIZE);

    // 为页目录表添加第一个页目录表项
    // UVPT：0xef400000，从这个虚拟地址开始，存放的是操作系统的页表kern_pgdir
    // PADDR(kern_pgdir)计算kern_pgdir所对应的真实物理地址
    kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;

    // 分配一块内存，用来存放一个struct PageInfo的数组
    // 数组中的每一个PageInfo代表内存当中的一页,PageInfo为页面链表的节点
    pages = (struct PageInfo *) boot_alloc(sizeof(struct PageInfo) * npages);

    // 内存清0
    memset(pages, 0, npages * sizeof(struct PageInfo));

    page_init();

    check_page_free_list(1);
    check_page_alloc();
}

首先调用i386_detect_memory函数检测现在系统中有多少可用的内存空间。kern_pgdir是指向操作系统的页目录表的指针，操作系统之后工作在虚拟内存模式下时，就需要这个页目录表进行地址转换。

boot_alloc()函数暂时当做页分配器，之后我们使用的真实页分配器是page_alloc()函数。而它的核心思想就是维护一个静态变量nextfree，里面存放着下一个可以使用的空闲内存空间的虚拟地址`，所以每次当我们想要分配n个字节的内存时，我们都需要修改这个变量的值

为页目录表添加第一个页目录表项后，分配一块内存，分配npages数目的结构体PageInfo空间，由pages指向该块内存。操作系统内核通过这个数组来追踪所有内存页的使用情况。然后运行函数page_init()，这个函数初始化两个信息：pages数组和pages_free_list链表(存放着所有空闲页的信息)

page_init后的内存分布

初始化所有物理内存页的相关数据结构后，check_page_free_list(1)和check_page_alloc()，这两个检查程序检查页面管理是否正确。前者检查page_free_list链表的空闲页，是否都是合法/空闲，后者检查page_alloc()，page_free()两个函数是否能够正确运行

8086处理器是一个16位的处理器，它的数据总线是16位，而地址总线是20位的，最多可以寻址1MB的地址空间。之后的80286处理器也是16位，但是地址总线有24位，从80286开始CPU演变出两种工作模式:实模式和保护模式

x86寄存器

在x86架构中，16位的处理器与32位处理器所对应的寄存器是有所不同的。8086寄存器组就分为通用寄存器，专用寄存器和段寄存器三类总共15个，其中通用寄存器有AX、BX、CX、DX、SP、BP、DI及 SI，专用寄存器包括IP、SP 和FLAGS三个16位寄存器， 而段寄存器则有CS、DS、SS、ES，这些寄存器都是 16位的

为支持1MB寻址空间，8086在实模式下引入了分段的方法。CPU中设置了四个段寄存器:CS、DS、SS和 ES，分别用于可执行代码段 、数据段以及堆栈段 。 每个段寄存器都是16位的，对应于地址总线中的高16位。

段式内存管理

段式内存管理带来了优势:

• 调试错误更容易定位
• 程序的地址不再需要采用内存物理地址进行编码
• 支持更大的内存地址

但是在该环境下，应用程序可以直接对系统的任意内存地址(包括操作系统所在的区域)进行操作

保护模式，这种模式下内存段的访问受到了限制。访问内存时不能直接从段寄存器中获得段的起始地址，而需要经过额外转换和检查。在保护模式下，段范围不再受限于64K，可以达到16MB(或者80386的4GB)。

实模式下段的管理

实模式采用16位寻址模式，在该模式中，最大寻址空间为1MB，最大分段为64KB。

8086处理器地址总线扩展到20位，但算术逻辑运算单元(ALU)宽度即数据总线却只有16位，也就是说直接参与运算的数值都是16位的。寻址时，采用以下公式计算实际访问的物理内存地址:实际物理地址 = (段寄存器 << 4) + 偏移地址这样，便实现了16位内存地址到20位物理地址的转换

80x86系列是使用CS寄存器配合IP寄存器的组合来通知CPU指令在内存中的位置。程序指令在执行过程中一般还需要有各种数据，80x86系列有DS、ES、FS、GS、SS等用于指示不同用途的数据段在内存中的位置。80x86系列使用中断机制来实现系统服务。总的来说，这些就是实模式一个程序运行所需的主要内容。

保护模式下段的管理

保护模式下的分段机制
利用段选择子到全局描述符表中找到需要的段描述符，段描述符中就存放着真正的段的物理首地址，再加上偏移地址量便得到了最后的物理地址

一般保护模式段式寻址可用 xxxx:yyyyyyyy表示。其中xxxx表示索引，也就是 段选择子，是16位的;yyyyyyyy是偏移量，是32位的。

到哪里去寻找全局描述符表呢?80386以及以后的处理器专门设计了一个寄存器GDTR(Global Descriptor Table Register)，专门用于存储全局描述符表在内。GDTR寄存器有48位，其中有32位记录描述符表的物理地址，16位记录全局描述符表的长度(该表占据的物理内存字节数)

再来看看段描述符，段描述符实际上是一个占据64位内存(8个字节)的结构体

一个64位的段描述符包含了段的物理首地址、段的界限以及段的属性。在描述符中，段基址占32位，段限长占20位，属性占12位

保护模式寻址实例

下面将通过一个例子来加深对保护模式寻址方式的理解。在这个程序开始执行的时候cs寄存器的值为0

.set PROT_MODE_CSEG， 0x8         # kernel code segment selector
.set PROT_MODE_DSEG， 0x10        # kernel data segment selector
.set CR0_PE_ON，      0x1         # protected mode enable flag
lgdt    gdtdesc

  movl    %cr0， %eax
  orl     $CR0_PE_ON， %eax
  movl    %eax， %cr0

  # Jump to next instruction， but in 32-bit code segment.
  # Switches processor into 32-bit mode.
  #  实模式跳转到保护模式
  ljmp    $PROT_MODE_CSEG， $protcseg

protcseg:
  movw    0x10， %ax
  movw    %ax，  %dx
  movl    0xf0000000， %ebx
  movl    0x20(%ebx)， %eax

gdt:                                    #gdt表的内容
  SEG_NULL                                # null seg
  SEG(STA_X|STA_R， 0x0， 0xffffffff)        # code seg
  SEG(STA_W， 0x0， 0xffffffff)            # data seg

gdtdesc:
  .word   0x17                            # sizeof(gdt) - 1
  .long   gdt

以上这一小段程序展示了系统进入保护模式以及在保护模式中利用寄存器寻址的过程。

首先lgdt指令将GDT表的地址和表长装入GDTR寄存器，在gdtdesc标识的地方存有一个字及一个双字，前者为0x17表示表的长度(字节数)，后者是表的物理地址。

接着再将CR0的保护模式开启位打开，系统便进入了保护模式，开始采用保护模式的寻址模式进行地址的转换。这个时候，内存中有GDT的3个表项。

进入保护模式后系统立即执行了一个长跳转指令，由于是在保护模式中，所以 PROT_MODE_CSEG被当作段选择子，而protcseg是偏移地址。段选择子的值是0x8，于是对应的段描述符会是表中的第一项，即是SEG(STA_X|STA_R， 0x0， 0xffffffff)这一项，0x0表示段首地址是0，所以最终得到的物理地址为0 + protcseg，程序便会跳到 protcseg 所标识的位置来执行。

之后执行指令: movl 0x20(%ebx)， %eax， 如图所示可知段基址为0，于是物理地址是0+0x20+0xf000000=0xf000020，内存中这个位置的一个双字会被复制到eax寄存器中

这里能访问的到的0到4G的地址空间实际上是虚拟地址空间，在开启分页机制后，还要经过页表转换才能得到真实地址，而在开启分页之前系统一般会控制只访问低地址，这些问题到内存管理我们会进行更深入的讨论