「MIT 6.828」MIT 6.828 Fall 2018 lab6

Lab6 终于到最后一个part了

Posted by 许大仙 on May 17, 2022

最近的科研告一段落了,实话实话,不太有多少成绩,完全算不是满意,不过过程还是比较快乐的。

马上要去实习了,所以把脱了这么久的OS lab做完吧。

然后再啃啃ULK和《Linux内核设计与实现》吧。

Lab 6: Network Driver (default final project)

这是最后一个独立完成的lab了。

OS不能没有network stack【no self respecting OS should go without a network stack】,在这个实验中,我们要写一个E1000网卡的驱动。

The card will be based on the Intel 82540EM chip, also known as the E1000.

Commit lab5中实现的内容,merge lab5到lab6 分支,并开始实验吧。

网卡驱动程序不足以让您的操作系统连接到 Internet。因此,在lab6 ,我们于新的 net/目录以及kern/中的新文件中为您提供了网络栈和网络服务器(a network stack and a network server)的code。

除了编写驱动程序之外,您还需要创建一个系统调用接口来访问您的驱动程序。您将实现missing的部分网络服务器代码以在network stack和driver之间传输数据包。您还将通过完成一个web服务器将所有内容联系在一起。使用自实现的Web服务器,您将能够从lab5中的文件系统内通过网络提取文件。

许多内核设备驱动程序代码几乎需要自己从头开始编写,并且这个实验提供的指导比以前的实验少得多:没有框架文件,没有一成不变的系统调用接口,许多设计决策都由您决定。出于这个原因,建议您在开始任何单独的练习之前阅读整个lab的描述。

QEMU’s virtual network

我们将使用 QEMU 的user mode下的network stack,因为它不需要管理权限即可运行。关于QEMU user-net的信息文档在这里。我们更新了 makefile 以启用 QEMU user-mode network stack和E1000 虚拟网卡。

默认情况下,QEMU 提供了一个运行在 IP 10.0.2.2 上的虚拟路由器,并将分配给 JOS 的 IP 地址为 10.0.2.15。为了简单起见,我们将这些默认值硬编码到net/ns.h中的network server内。

通过使用-net user 选项(即默认配置 ),QEMU将完全使用user-mode network stack。具体的虚拟网络配置如下:

guest (10.0.2.15)  <------>  Firewall/DHCP server <-----> Internet
                      |          (10.0.2.2)
                      |
                      ---->  DNS server (10.0.2.3)
                      |
                      ---->  SMB server (10.0.2.4)

The QEMU VM behaves as if it was behind a firewall which blocks all incoming connections.

虽然 QEMU’s virtual network 允许 JOS 与 Internet 建立任意连接,但 JOS 的 10.0.2.15 地址在 QEMU 内部运行的虚拟网络之外没有任何意义(即 QEMU 充当 NAT),因此我们不能直接从外部甚至是host,连接到在JOS中运行的network server。为了解决这个问题,我们将 QEMU 配置为在主机的某个端口上运行一个服务器,该服务器简单地连接到 JOS 中的某个端口,并在您的真实主机和虚拟网络之间来回传输数据。【根据上述提到的QEMU文档,我们得知这种从host某个端口到QEMU guest的重定向可以通过-netdev user,hostfwd=...来实现】

我们将在端口 7 (echo) 和 80 (http) 上运行 JOS servers。为避免共享 Athena 机器【和课程相关】上的冲突,makefile 会根据您的用户 ID 生成转发端口。要找出 QEMU 在您的开发主机上转发到哪些端口,请运行make which-ports。为方便起见,makefile 还提供了make nc-7make nc-80,它允许您直接与在终端的这些端口上运行的服务器进行交互。(这仅用于通过nc连接到正在运行的 QEMU 实例,您必须提前单独启动 QEMU。)

Packet Inspection

makefile 还配置QEMU的network stack以将所有传入和传出的数据包记录到/lab目录中的qemu.pcap

要获取捕获数据包的十六进制/ASCII 转储,请使用tcpdump,如下所示:

tcpdump -XXnr qemu.pcap

同时您可以使用Wireshark以图形方式检查 pcap 文,Wireshark可支持解码和检查数百种网络协议。

Debugging the E1000

我们很幸运能够使用硬件仿真。Since the E1000 is running in software, 因此仿真的E1000可以以用户能够读懂的方式将内部状态和遇到的任何bug报告给我们。通常,对于使用裸机编写的驱动程序开发人员来说,这是几乎不可得的。

E1000 可以产生大量调试输出,为此您必须启用特定的日志记录通道(logging channels)。Some channels you might find useful are:

image-20220517220028916

例如,要启用“tx”和“txerr”日志记录,请使用make E1000_DEBUG=tx,txerr ....

注意: E1000_DEBUG标志仅适用于 6.828 版本的 QEMU。

You can take debugging using software emulated hardware one step further。也就是说,如果您遇到困难并且不明白为什么 E1000 没有按照您期望的方式运作,您可以在hw/net/e1000.c中查看 QEMU 的 E1000 实现。

The Network Server

Writing a network stack from scratch is hard work. Instead, we will be using IwIP, 一个轻量级的开源TCP/IP协议套件(其中包含了一个协议栈)。在本实验中,lwIP可以看做是一个实现了 BSD 套接字接口并具有数据包输入端口和数据包输出端口的黑盒【具体的实现代码可以参考JOS内核代码中的net/lwip/目录】。

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

  • core network server environment (includes socket call dispatcher and lwIP)
  • input environment
  • output environment
  • timer environment

下图显示了不同的环境及其关系。该图显示了整个系统,包括设备驱动程序,稍后将介绍。在本实验中,您将实现绿色高亮的部分。

Network server architecture

The Core Network Server Environment

核心网络服务组件(Core Network Server Environment)是由socket call dispatcher和network stack(即这里IwIP)组成的。套接字调用调度程序(socket call dispatcher)的工作方式与文件服务器完全相同。用户环境使用存根stubs (定义在lib/nsipc.c中)将 IPC messages发送到核心网络服务组件。

如果您查看 lib/nsipc.c,您会看到我们找到核心网络服务组件的方式与我们找到文件服务器的方式相同:在系统初始化的时候,调用了i386_init——使用 NS_TYPE_NS 创建了 NS 环境,此后通过扫描envs,寻找这种特殊的环境类型(nsenv)。对于每个用户环境的 IPC请求,网络服务组件中的调度程序(socket call dispatcher)会代表用户调用 lwIP协议栈提供的相应 BSD 套接字接口函数。

//我们经过了一个又一个实验
void
i386_init(void)
{
	// Initialize the console.
	// Can't call cprintf until after we do this!
	cons_init();
	cprintf("6828 decimal is %o octal!\n", 6828);

	// Lab 2 memory management initialization functions
	mem_init();
	// Lab 3 user environment initialization functions
	env_init();
	trap_init();
	// Lab 4 multiprocessor initialization functions
	mp_init();
	lapic_init();
	// Lab 4 multitasking initialization functions
	pic_init();

	// Lab 6 hardware initialization functions
	time_init();	//这里已经完成过时间中断的初始化,即ticks = 0
	pci_init();		//这个是PCI初始化,也就是搜索所有用PCI连接的硬件[记录到root_bus中]
	
	// Acquire the big kernel lock before waking up APs
	// Your code here:
	lock_kernel();

	// Starting non-boot CPUs
	boot_aps();

	// Start fs. 【可以看到这里在初始化文件系统环境】
	ENV_CREATE(fs_fs, ENV_TYPE_FS);

#if !defined(TEST_NO_NS)
	// Start ns.【类似地初始化了网络服务组件的环境,记录core network environment到net_ns中】
	ENV_CREATE(net_ns, ENV_TYPE_NS);
#endif

	// Schedule and run the first user environment!
	sched_yield();
}

//最后ENV_CREATE会调用env.c中的env_create(uint8_t *binary, enum EnvType type),为特定的binary分配env结构,然后加载这个binary到特定的虚拟进程空间中。

//我们可以在 `lib/nsipc.c`中看到寻找核心网络服务组件相关的代码如下:
static int
nsipc(unsigned type)
{
    static envid_t nsenv;
	if (nsenv == 0)
		nsenv = ipc_find_env(ENV_TYPE_NS);
    /* …… */
}

常规用户环境下,是不会直接使用调用nsipc_*的【即lwIP协议栈提供的BSD套接字接口函数,可见于lib/nsipc.c,如nsipc_accept, nsipc_bind之类的】。相反,正常用户程序会使用lib/sockets.c中的函数,它提供了一个基于文件描述符的套接字 API。因此,用户环境可以通过文件描述符引用套接字,就像它们引用磁盘文件一样。有许多操作(connect,accept等)是特定于套接字的,但是对于另外一些操作如read, write等则通过lib/fd.c中正常的文件描述符设备调度代码进行。此外,就像文件服务器如何为所有打开的文件维护内部唯一ID一样,lwIP 也为所有打开的套接字生成唯一 ID。在文件服务器和网络服务器中,我们使用存储在struct Fd中信息将每个环境/进程的文件描述符映射到这些唯一的 ID 空间。

尽管看起来文件服务器和网络服务器的 IPC 调度程序的行为相同,但还是有一个关键的区别。BSD socket calls like `accept` and `recv` 可以无限制的阻塞。如果调度器让 lwIP 执行这些阻塞调用之一,调度器也会阻塞,整个系统一次只能有一个未完成的网络调用。由于这是不可接受的,网络服务组件会使用用户级线程( user-level threading)来避免阻塞整个服务器环境(server environment)。对于每个传入的 IPC 消息,调度程序创建一个网络线程并在新创建的线程中处理请求。如果线程阻塞,则只有该网络线程进入睡眠状态,而其他线程继续运行。【因此IPC dispatcher基本上都是多线程程序】

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

The Output Environment

在服务用户环境套接字调用时,lwIP 将生成数据包交由网卡传输。具体来说,LwIP会将每个包传递给output helper environment ,即通过将数据包附加在 NSREQ_OUTPUT IPC 消息的page参数中,完成传递。The output environment会负责接受这些消息并通过我们即将创建的系统调用接口将数据包转发到设备驱动程序。

The Input Environment

网卡从网络中收到的数据包需要注入lwIP协议栈中,这就需要the input helper environment的帮助。

对于设备驱动程序接收到的每个数据包, the input environment将数据包pull出内核空间(使用您将实现的内核系统调用)并用过NSREQ_INPUTIPC 消息将数据包发送到核心网络服务环境(core network server environment)。

数据包输入功能与核心网络服务环境分离,因为 JOS 很难同时accept IPC 消息,并轮询或等待来自设备驱动程序的数据包。我们在 JOS 中没有实现select系统调用,以允许environments监视多个输入源,以识别哪些输入已准备好被处理。

如果您查看net/input.cnet/output.c,您会发现两者都需要实现。这主要是因为实现取决于你的系统调用接口。在实现驱动程序和系统调用接口后,您将为这两个辅助环境(即input/output environments)编写代码。

The Timer Environment

定时器环境定期向核心网络服务组件发送NSREQ_TIMER类型的消息,通知它定时器的时间已到(expired)。lwIP使用来自该线程/环境的计时器消息来实现各种网络超时。

Environment Creation Analysis

我们可以在整个网络服务的目录(即net)下看到net/serv.c中构建了多个环境,并且创建线程调度。

void
umain(int argc, char **argv)
{
	envid_t ns_envid = sys_getenvid();

	binaryname = "ns";

	// fork off the timer thread which will send us periodic messages
	timer_envid = fork(); //创建定时器环境
	if (timer_envid < 0)
		panic("error forking");
	else if (timer_envid == 0) {	//在定时器进程中
		timer(ns_envid, TIMER_INTERVAL); //定时启动ns环境
		return;	//然后返回
	}

	// fork off the input thread which will poll the NIC driver for input
	// packets
	input_envid = fork();	//输入环境创建
	if (input_envid < 0)
		panic("error forking");
	else if (input_envid == 0) {
		input(ns_envid);	//之后要完善这个函数
		return;
	}

	// fork off the output thread that will send the packets to the NIC
	// driver
	output_envid = fork();//输出环境
	if (output_envid < 0)
		panic("error forking");
	else if (output_envid == 0) {
		output(ns_envid);	//之后要完善这个函数
		return;
	}

	// lwIP requires a user threading library; start the library and jump
	// into a thread to continue initialization.
	thread_init();//线程初始化
	thread_create(0, "main", tmain, 0);	//线程创建,调用tmain,初始化整个协议栈等,并且调用serve()启动网络服务,接受各种系统调用。
	thread_yield();//线程调度【这里的调度策略很简单,就是保存当前线程到thread_queue,然后出队下一个线程,将这个线程的tc_jb字段的各种线程寄存器暂存值恢复到现有寄存器中,继续执行。
	// never coming here!
}

前面知道为了避免整个网络服务的阻塞,dispatcher会通过线程池来处理IPC请求。具体的线程实现定义在:net/lwip/jos/arch/thread.c中。

void
thread_init(void) {
    threadq_init(&thread_queue);//进去看这个函数
    max_tid = 0;
}
//lwpic/jos/threadq.h【线程池的管理操作就在threadq.c中】
static inline void 
threadq_init(struct thread_queue *tq)
{
    tq->tq_first = 0;
    tq->tq_last = 0;
}

struct thread_context;

struct thread_queue //一个线程池,或许应该叫线程队列
{
    struct thread_context *tq_first;
    struct thread_context *tq_last;
};

struct thread_context { //线程结构体,即TCB
    thread_id_t		tc_tid;  //线程ID
    void		*tc_stack_bottom;//线程栈
    char 		tc_name[name_size];//线程名
    void		(*tc_entry)(uint32_t);//线程指令地址 ,实现过线程这个很好理解
    uint32_t		tc_arg;//参数
    struct jos_jmp_buf	tc_jb;//这个可以简单理解为,保存了各个寄存器的内容
    volatile uint32_t	*tc_wait_addr;
    volatile char	tc_wakeup;
    void		(*tc_onhalt[THREAD_NUM_ONHALT])(thread_id_t);
    int			tc_nonhalt;
    struct thread_context *tc_queue_link;
};

线程创建的代码如下:

int
thread_create(thread_id_t *tid, const char *name, 
		void (*entry)(uint32_t), uint32_t arg) {
    struct thread_context *tc = malloc(sizeof(struct thread_context));//分配一个空间
    if (!tc)
	return -E_NO_MEM;

    memset(tc, 0, sizeof(struct thread_context));
    
    thread_set_name(tc, name);//设置线程名
    tc->tc_tid = alloc_tid();//自己看

    tc->tc_stack_bottom = malloc(stack_size);//每个线程应该有独立的栈,但是一个进程的线程内存是共享的,因为共用一个页表。很明显的能够看出来,TCB没有页表,所以内存都是共享的,所以理论上来说,是可以跨线程访问栈的。 
    if (!tc->tc_stack_bottom) {
	free(tc);
	return -E_NO_MEM;
    }

    void *stacktop = tc->tc_stack_bottom + stack_size;
    // Terminate stack unwinding
    stacktop = stacktop - 4;
    memset(stacktop, 0, 4);
    
    memset(&tc->tc_jb, 0, sizeof(tc->tc_jb));
    tc->tc_jb.jb_esp = (uint32_t)stacktop;//初始化栈顶
    tc->tc_jb.jb_eip = (uint32_t)&thread_entry;	//通过thread_entry函数指针初始化线程入口。这个函数指针实际就是cur_tc->tc_entry(cur_tc->tc_arg);即调用线程开始执行的enrty即main,然后传入参数。
    tc->tc_entry = entry;
    tc->tc_arg = arg;//参数

    threadq_push(&thread_queue, tc);//加入线程队列

    if (tid)
	*tid = tc->tc_tid;
    return 0;
}

对于网络服务来说,第一个启动的线程就是“main”,指向tmain函数,然后调用serve(),处理三个环境和核心网络服务环境之间的通信【各种来自用户的ipc请求(底层的socket相关函数调用)和网卡数据】。

static void
tmain(uint32_t arg) {
	serve_init(inet_addr(IP),
		   inet_addr(MASK),
		   inet_addr(DEFAULT));//初始化了一点东西
	serve();//然后就是这个服务了
}

注意:详细看看serve()函数以及内部的调用时间处理函数serve_thread()

Part A: Initialization and transmitting packets

目前的JOS内核是没有时间概念的,所以我们需要为其添加。当前有一个由硬件每 10ms 产生一次的时钟中断。在每次时钟中断时,我们可以增加一个变量(ticks)来指示时间走了多少个10ms。这是在kern/time.c中实现的,但尚未完全集成到当前的内核中。

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

//首先我们需要看看kern/time.c中实现了哪些东西
#include <kern/time.h>
#include <inc/assert.h>
static unsigned int ticks;
void
time_init(void) //在i386_init中已经调用过初始化函数了
{
	ticks = 0;
}

// This should be called once per timer interrupt.  A timer interrupt
// fires every 10 ms.
void
time_tick(void)	//我们需要在中断处理调度器中调用的目标函数
{
	ticks++;
	if (ticks * 10 < ticks)
		panic("time_tick: time overflowed");
}

unsigned int
time_msec(void) //返回现在具体的毫秒时间,
{
	return ticks * 10;
}

因此我们修改如下内容:

//Exercise 1
// `kern/trap.c`
static void
trap_dispatch(struct Trapframe *tf)
{
    /* …… */
    // Add time tick increment to clock interrupts.
    // Be careful! In multiprocessors, clock interrupts are
    // triggered on every CPU.
    // LAB 6: Your code here.
    if(tf->tf_trapno == IRQ_OFFSET+IRQ_TIMER){
        lapic_eoi();
        if(thiscpu == bootcpu){
            time_tick();
        }
        sched_yield();	//never return
        //return;
    }
    /* …… */
}

//`kern/syscall.c`
// Return the current time.
static int
sys_time_msec(void)
{
	// LAB 6: Your code here.
	return time_msec();
}
//并在syscall中添加
int32_t
syscall(uint32_t syscallno, uint32_t a1, uint32_t a2, uint32_t a3, uint32_t a4, uint32_t a5)
{
    /* …… */
    case SYS_time_msec:
		return sys_time_msec();
   	/* …… */
}

Use make INIT_CFLAGS=-DTEST_NO_NS run-testtime to test your time code。You should see the environment count down from 5 in 1 second intervals. The “-DTEST_NO_NS” disables starting the network server environment because it will panic at this point in the lab.

可以看到starting count down: 5 4 3 2 1 0,则测试成功。

The Network Interface Card

编写驱动程序需要深入了解硬件,以及其呈现给软件的接口。实验文本将提供有关如何与 E1000 交互的高级概述,但您需要在编写驱动程序时大量使用英特尔的手册。

Exercise 2. Browse Intel’s Software Developer’s Manual for the E1000. This manual covers several closely related Ethernet controllers. QEMU emulates the 82540EM.

You should skim over chapter 2 now to get a feel for the device.

To write your driver, you’ll need to be familiar with chapters 3 and 14, as well as 4.1 (though not 4.1’s subsections).

You’ll also need to use chapter 13 as reference.

The other chapters mostly cover components of the E1000 that your driver won’t have to interact with. Don’t worry about the details right now; just get a feel for how the document is structured so you can find things later.

While reading the manual, keep in mind that the E1000 is a sophisticated device with many advanced features. A working E1000 driver only needs a fraction of the features and interfaces that the NIC provides.

Think carefully about the easiest way to interface with the card. We strongly recommend that you get a basic driver working before taking advantage of the advanced features.

这里主要给出手册中一些比较重要的部分和概念:

image-20220603203145352

Section 2

DMA Engine and Data FIFO

DMA引擎处理主机存储器和片上存储器之间的接收和发送数据及描述符的传输。【说白了,DMA就是释放了CPU,代替其完成网卡和主存之间的网络数据传输】

在接收路径中,DMA引擎将存储在接收数据FIFO缓冲器(receive data FIFO buffer)中的数据传输到主机内存中的接收缓冲器,该缓冲器由描述符中的地址指定。它还获取并写回更新的接收描述符(receive descriptors )到主机内存。

在发送路径中,DMA引擎将存储在主机内存缓冲区的数据传输到发送数据FIFO缓冲区(transmit data FIFO buffer)。它还获取并写回更新的发送描述符(transmit descriptors)。

以太网控制器数据FIFO块包括一个64 KB(82547GI/EI为40 KB)的片上缓冲器,用于接收和发送操作。接收和发送FIFO的大小可以根据系统要求来分配。FIFO为以太网控制器接收或发送的帧提供一个临时缓冲存储区。【Ethernet controller应该是用于接收/输送数据链路层中的帧(frame)】

DMA引擎和大型数据FIFO( the large data FIFOs)经过优化,以最大限度地提高PCI总线的效率,并通过以下方式降低处理器的利用率。

  • 缓解瞬时接收带宽需求,并通过在传输前缓冲整个出站数据包来消除传输不足
  • 在传输FIFO内排队传输帧,允许以最小的帧间间隔进行 back-to-back传输
  • 允许以太网控制器承受较长的PCI总线延迟而不丢失传入数据或破坏传出数据
  • 允许通过传输FIFO阈值来调整传输开始阈值。这种对系统性能的调整是基于可用的PCI带宽、线速和延迟的考虑
  • 卸载接收和传输IP和TCP/UDP校验
  • 直接从传输FIFO重传任何导致错误的传输(碰撞检测、数据不足),从而消除了从主机内存重新访问该数据的需要

DMA Addressing

此外,一般情况下,以太网控制器的寻址都是64bits,但由于Ethernet controller兼容PCI 2.2 or 2.3 Specification,且对于PCI 2.2 or 2.3而言,任何64位的地址,高于32bits的地址位都默认赋值为0b,appear as a 32-bit address cycle.

PCI是小端序的,但是并不是所有使用PCI的处理器都认为地址是小端序的。由于网络数据是字节流,因此处理器和以太网控制器需要统一内存数据的表示顺序。默认来说,会统一到小端序。

image-20220604150700186

Interrupts

The Ethernet controller provides a complete set of interrupts that allow for efficient software management. The interrupt structure is designed to accomplish the following:

  • Make accesses “thread-safe” by using ‘set’ and ‘clear-on-read’ rather than ‘read-modify-write’ operations.【以四个特殊寄存器实现】
  • Minimize the number of interrupts needed relative to work accomplished.
  • Minimize the processing overhead associated with each interrupt

Hardware Acceleration Capability

  • The Ethernet controller provides the ability to offload IP, TCP, and UDP checksum for transmit. For common frame types, the hardware automatically calculates, inserts, and checks the appropriate checksum values normally handled by software.
  • The Ethernet controller implements a TCP segmentation capability for transmits that allows the software device driver to offload packet segmentation and encapsulation to the hardware.

Buffer and Descriptor Structure

Software allocates the transmit and receive buffers, and also forms the descriptors that contain pointers to, and the status of, those buffers.

the driver software and the hardware of the buffers and descriptors之间存在一个概念上的所有权边界。软件赋予硬件对接收缓冲区队列的所有权。这些接收缓冲区存储数据,一旦有有效的数据包到达,软件就拥有这些数据。

对于传输,软件维护一个缓冲区队列。驱动程序软件拥有一个缓冲区,直到它准备好传输。然后,软件将缓冲区提交给硬件;硬件拥有缓冲区,直到数据被加载或传输到发送FIFO中。

Descriptors存储了有关于buffers的一些信息: 物理地址、长度、buffer状态以及命令信息。描述符包含一个end-of-packet字段,表示the last buffer for a packet. 描述符还包含表明数据包类型的特定信息,以及在传输数据包时要执行的具体操作,如VLAN或校验和卸载的操作。

Section 3

Part B: Receiving packets and the web server

Reference

推荐一个进阶版的part:MIT6.S081 Operating System Engineering

数据链路层(Data Link Layer)是OSI参考模型第二层,位于物理层与网络层之间。在广播式多路访问链路中(局域网),由于可能存在介质争用,它还可以细分成介质访问控制(MAC)子层和逻辑链路控制(LLC)子层,介质访问控制(MAC)子层专职处理介质访问的争用与冲突问题。

PHY: Port Physical Layer,即OSI模型中的物理层。PHY連接一個數據鏈路層的設備(MAC)到一個物理媒介,如光纖或銅纜線。典型的PHY包括PCS(Physical Coding Sublayer,物理編碼子層)和PMD(Physical Media Dependent,物理介質相關子層)。PCS對被傳送和接受的資訊加碼和解碼,目的是使接收器更容易恢復信號。