问题
给定一棵二叉树的头节点head和一个32位整数sum,二叉树节点值类型为整型,求累加和为sum的最长路径长度.
路径是指从某个节点往下,每次最多选择一个孩子节点或者不选所形成的节点链
bootloader实际做了两件事:进入保护模式和加载内核程序
。这篇文章将介绍bootloader加载内核程序的过程
对 ELF 文件有了基础地认识后,我们再来研究一下 Boot Loadr 具体是如何将 kernel 的可执行 ELF 文件加载到内存中的。boot/main.c 就是从硬盘读取 kernel
,下面我们就分块来分析一下这个C程序
void bootmain(void)
{
struct Proghdr *ph, *eph;
// read 1st page off disk
// 把操作系统映像文件的elf头部读取出来放入内存中,把内核的第一个页
//的内容读取到内存地址ELFHDR(0x10000)处
// 程序就将文件的前 4KB 读入内 存,这其中包括 ELF 文件头以及程序头表
// 这样就可以找到文件的每一段
readseg((uint32_t) ELFHDR, SECTSIZE*8, 0);
// is this a valid ELF?
// elf文件的头部就是用来描述这个elf文件如何在存储器中存储,文件是可链
// 接文件还是可执行文件,会有不同的elf头部格式.对于一个可执行程序,通
// 常包含存放代码的文本段(text section),存放全局变量的data段,存放
// 字符串常量的rodata段
if (ELFHDR->e_magic != ELF_MAGIC)
goto bad;
// load each program segment (ignores ph flags)
// 部中一定包含Program Header Table。这个表格存放着程序中所有段的信息。
// 通过这个表我们才能找到要执行的代码段,数据段等等。所以我们先获得这个表
ph = (struct Proghdr *) ((uint8_t *) ELFHDR + ELFHDR->e_phoff);
eph = ph + ELFHDR->e_phnum; //表尾
//把操作系统内核的各个段从外存读入内存中
for (; ph < eph; ph++)
// p_pa is the load address of this segment (as well
// as the physical address)
readseg(ph->p_pa, ph->p_memsz, ph->p_offset);
// call the entry point from the ELF header
// note: does not return!
// 跳转到操作系统内核程序的起始指令处.把控制权从boot loader转交给了操作
// 系统的内核
((void (*)(void)) (ELFHDR->e_entry))();
bad:
outw(0x8A00, 0x8A00);
outw(0x8A00, 0x8E00);
while (1)
/* do nothing */;
}
可以看到 SECTSIZE*8 代表 4KB,这就是说在一开始 ,程序就将文件的前4KB 读入内存,这其中包括 ELF文件头以及程序头表
, 根据这些信息,我们可以找到文件的每一段 。于是紧接着程序利用 readseg函数将内核文件的每一段依次读入内存
然后转到内核入口地址执行。实际上我们可以通过“objdump –f 可执行文件”命令来查看 ELF 文件的入口地址。
通过实验可以看到 kernel 的入口地址是 0xf010000c,然而在程序跳转的时候,却
将 0xf010000c 与 0xFFFFFF 相与以后的值作为入口地址,这是因为 kernel 程序的链接地址 是 0xf0100000,而由于实际的物理内存没有那么大,在 0xf0100000 地址处并没有物理内存
, 所以真正的加载地址实际上是 0x100000,相应的入口地址也就是 0x10000c,即是 0xf010000c 与 0xFFFFFF 相与以后的值。
当我们查看内存的中的 ELF 文件头的相应信息后,我们发现 kernel 可执行文件实际上是分为 两段
第一段在文件中的偏移是 0x1000,而在内存中占据的字节数是 0x6daa,链接地址 0xf0100000;
第二段在文件中的偏移是 0x8000,而在内存中占据的字节数是 0x8bc0,链接地址 0xf0107000
在上图中可以看到kernel可执行文件的第一段包含了 ELF 文件的.test 节、.rodata 节、.stab节以及.stabstr 节
,而文件的第二段包含了.data 节以及在硬盘上不占用空间但在内存中占据 660 字节的.bss 节
,在这里程序头表的第二项会用 p_filesz 成员变量标注该段在文件占用的字节数(磁盘)并且同时用 p_memsz 标注在内存中占用的字节数,这样 Boot Loader 便会在从硬盘读 入第二段的同时为.bss节在内存中分配空间
。.comment 节没有被包含在 任意一段中,这表明它没有被装入内存
操作系统,江湖流传着
计算机三大浪漫之一
。在学习这门课时,如果仅仅把目光停留在课本上一些关于操作系统概念上的叙述,并不能对操作系统有着深层次的理解。 当然也体会不到其中的浪漫
。
MIT的操作系统课程6.828是大家口中的OS神课。麻雀虽小,五脏俱全。它能够帮助我们真正的了解操作系统在做什么以及一个小型OS具体到代码是如何实现的
。开始折腾吧,它值得你付出时间和精力。
我将该项目的目前完成Lab的代码实现托管在github上,传送们.欢迎star
虽然之前读过《深入理解计算机系统》,读完之后对很多OS的概念和实现细节都是只见树木不见森林。然后从寒假回家就窝家里开始刷Lab。目前对OS的理解清楚了很多,从书本概念到0距离接触代码这一过程,将很多之前学习过的知识点都串了起来
。比如elf文件的理解,函数调用的底层机制实现。当然汇编代码的阅读能力,没有了之前对它的恐惧感,算是得到质的提升吧。
不可否认的是有些Exercise真的非常让人头痛、一个bug可能会调很久甚至几天没有进展。一个概念查阅大量的资料,反复的理解,一遍又一遍地认识
。
具体每个Lab所完成的工作(目前只刷到lab4)
Lab1是熟悉的过程,需要学习QEMU模拟器的使用、开机启动流程、调试工具、bootloader、以及整个加载kernel的流程。做完这个lab会具备基本的内核调试能力,以及掌握开机到通电,
bootloader是如何加载kernel
的。Lab2要完成
JOS的的内存管理模块
,需要学习一些计算机基础知识,如虚拟地址系统是如何工作的,地址空间是如何切分的,物理页面是如何管理的。做完这个lab将会给JOS添加最基本的内存管理功能,即Kernel其余模块需要物理页,这个模块可以分配出来
。Lab3为
JOS添加进程的支持、异常/中断的支持、系统调用和页中断的支持
。这个lab内容比较多,但收获也比较大,做完后会对从用户态陷入内核态,执行系统调用,然后返回这整个流程都非常清楚(不是泛泛的清楚,而是代码级别的清楚,这是和学概念不同的地方)。
由于考研,准备实习,该项目也就暂时搁浅了。Lab4为JOS添加多核支持、RR调度、COW的fork、抢占式内核、时钟中断和最基本的IPC机制
。Lab6为JOS添加网络的支持
。这两个Lab对我来说,还是有很大的吸引力。日后一定会抠出时间,将它们完成。至于Lab5的文件系统,本人不太感冒。
PS:想想之后将Dartnet协议栈移植到JOS就激动,先在这挖个大坑吧
。
归根结底这只一个课程OS,JOS还有很大的提升空间,离工业级使用还差很多,以下是一些改进点:
JOS和xv6的内存管理方式都是空闲链表,这导致
如果内核想要连续的物理内存,将十分困难
,所以linux采用了buddy system来解决碎片问题。JOS和xv6的进程调度是最简单的RR方式,这使得它们
无法应用在某些特殊的场景下,而且父进程很容易fork子进程把CPU时间全抢了
。
打算之后再读读《Linux内核设计与实现》,发现JOS到底哪里做得不好以及Linux是如何解决的
。
最后感谢开源
,在刷Lab的过程中遇到不少的坑,总能从前辈的经验中学习,帮助自己更有方向性的解决问题
参考链接
推荐一门课:6.828
本篇文章主要介绍简单可靠传输的原理实现,我们只考虑由连接管理使用的控制,其它部分将在另外几篇博文中介绍。为了完成SRT的测试,我们需要编写一个客户端和一个服务器。
就像TCP一样,SRT提供按顺序字节流的可靠传递。这里SRT做出了一些假设,以简化协议的设计和实现。
- 单向传输,即DATA段从客户端流向接受端
- 连接管理:客户端发起和断开连接
- 不支持流量控制或拥塞控制
SRT拥有以下机制
- 连接管理:连接和断开
- 校验和用于检测接受的数据是否被破坏
- 回退N步用于在接收端可靠地传送数据,序列号用于检测丢失的数据和将数据重新排序
- 重传:客户端使用超时和ACK来重传丢失的数据和控制分组(例如SYN)
上一篇博文中,我们看到在DartNet协议栈的不同层之间有许多API。在实现SRT过程中,我们不使用SNP层转发,专注于客户端和服务器的实现与SRT API相关联的一组有限功能 。只考虑客户端和服 务器之间的连接相关的函数调用。SRT像TCP一样能够支持多个同时连接。我们将讨论数据结构和有限状态机(FSM)需要在本文后面支持这一点。
没有SNP时,SRT直接位于覆盖层上。在这种情况下,覆盖层简单地实现客户端和服务器SRT传输协议之间的TCP连接。我们的覆盖层也只包含客户端和服务器之间的直接TCP连接。
overlay_start()和 overlay_stop()
函数创建客户端和服务器之间的TCP直接连接。overlay_start()返回TCP套接字描述符。overlay_stop()关闭TCP连接。
首先需要实现的是snp _sendseg()和 snp_recvseg()函数,以使用覆盖层的TCP连接发送和接段
。在TCP数据作为字节流发送的情况下。为了通过覆盖层TCP连接发送数据段,我们需要在字节流中添加分隔符。
在SRT中,使用特殊字符“!&”表示段的开始,特殊字符“!#”表示段的结束。这些分隔符不应该出现在客户端和服务之间发送的数据中。这是一个限制(并且如果“!&”或“!#”发生在客户端的字节流中,协议将不正确地操作,因此应该确保数据不包括这些特殊控制字符对)。分隔符是必要的,因为STR分组的接收侧(即STR标头+ STR段)需要知道它何时成功接收到SRT分组,这是一种方法。
可能是最简单的方法。
因为覆盖层是从TCP构建的,而不是说UDP,我们没有任何损失
。为了允许覆盖看起来像在有损链路上运行,并且分组可以在因特网中丢失,我们在接收到SRT分组时在snp _recvseg()中调用丢失 loss()函数,以丢弃具有概率PROBABILITY_LOSS的分段来模拟分组丢失以迫使SRT恢复丢失的分段
,其可以是SRT DATA分组 ,SYN, SYNACK,FIN和FINACK。 SRT协议必须能够正确地从任何这些数 据包的丢失中恢复。
图3:这些是DartNet API函数调用的子集
功能的流程如下
app_client.c和app_server.c,应用程序层代码首先通过在overlay_start()中的客户端和服务器之间创建一个直接TCP链接来启动覆盖层。在app _client和 app _server中实 现overlay_start()。 服务器通过调用srt _svr _init()初始化SRT服务器,客户机通过调用srt _client _init()初始化 SRT客户机。
然后服务器调用srt _svr _sock()创建服务器端套接字,srt _svr _accept()接受来自客户端的连 接请求(SRT层的控制消息SYN)客户端创建一个套接字,并分别通过调用srt _client _sock() 和 srt _client _connect()连接到服务器套接字。
客户端和服务器在不同端口上建立两个连接,所以SRT可以处理多个连接:服务器创建另一个套接字并等待传入连接,客户端创建另一个套接字并连接到新的服务器套接字。通过这样做,SRT可以同时有多个连接。
客户端在等待时间之后通过为每个连接调用srt _client _disconnect()断开与服务器的连接。最 后,服务器通过调用srt _svr _close()关闭套接字,客户端通过调用srt _client _close()关闭 套接字。
该app_client和app_server通过调用终止其进程之前停止叠加层over_end()在客户端和服务器。实现了overlay_stop(),而且还实现了srt˙client.c和 srt_server.c中使用的所有SRT 函数。
SRT定义了实现将数据控制和分组成段的多个重要数据结构。
SRT分组包括SRT头(参见下面的srt_hdr_t)和SRT段(参见seg_t-数据字节流在这里)。SRT分组被封装到SNP分组中,当我们进入SNP时我们将讨论该SNP分组。注意,SRT报头包括与分组相关联的重要信息,包括例如无符号短整型类型; 。
报头中的type字段定义数据包的类型:
#define SYN 0
#define SYNACK 1
#define FIN 2
#define FINACK 3
#define DATA 4
#define DATAACK 5
SRT协议以段为单位发送和接收数据。
图4:段头格式
它在seg.h中定义:
typedef struct srt_hdr {
unsigned int src_port; //source port number
unsigned int dest_port; //destination port number
unsigned int seq_num; //sequence number
unsigned short int length; //segment data length
unsigned short int type; //segment type
unsigned short int rcv_win; //currently not used
unsigned short int checksum; //currently not used
} srt_hdr_t;
typedef struct segment {
srt_hdr_t header;
char data[MAX_SEG_LEN];
} seg_t;
SRT使用传输控制块(TCB)维护与连接相关联的所有状态。对于每个连接,客户端和服务器端初始化并维护TCB。当连接关闭时,TCB返回到未使用的TCB池。下图显示了为每个连接维护的服务器端TCB。当srt _svr _init()和 srt _client _init()分别由server_App 和client_App 调用时,TCB表 在启动时在客户端和服务器上初始化。在编码SRT时,始终对数据结构和数据结构表使用malloc()/ free()。
typedef struct svr_tcb {
unsigned int svr_nodeID; //node ID of server, similar as IP address
unsigned int svr_portNum; //port number of server
unsigned int client_nodeID; //node ID of client, similar as IP address
unsigned int client_portNum; //port number of client
unsigned int state; //state of server
unsigned int expect_seqNum; //sequence number of the data seg server is expecting
char* recvBuf; //a pointer pointing to a receive Buffer
unsigned int usedBufLen; //size of received data in receiver buffer
pthread_mutex_t* bufMutex; //a pointer pointing to a mutex for receive buffer access
}
svr_tcb_t;
对于每个连接,SRT客户端维护客户端和服务器TCB
typedef struct client_tcb {
unsigned int svr_nodeID; //node ID of server, similar as IP address
unsigned int svr_portNum; //port number of server
unsigned int client_nodeID; //node ID of client, similar as IP address
unsigned int client_portNum; //port number of client
unsigned int state; //state of client
unsigned int next_seqNum; //next sequence number
pthread_mutex_t* bufMutex; //a pointer pointing to a mutex for send buffer access
segBuf_t* sendBufHead; //used by send buffer
segBuf_t* sendBufunSent; //used by send buffer
segBuf_t* sendBufTail; //used by send buffer
unsigned int unAck_segNum; //number of unAcked segments
} client_tcb_t;
SRT具有与TCP类似的连接设置和断开。SRT只是使用两次握手。
连接设置
当客户端发送SYN并且服务器用SYNACK响应时建立连接
图5:SRT连接设置
But life is not that simple: corruption and loss of control messages get in the way
设置和断开时可能发生的以下问题:在SYN中发生丢失或损坏;客户端已经发送,服务器却不知道。这个问题如何解决?如果服务器接收到SYN,在发送SYNACK过程中丢失,会发生什么?
这些异常的解决方案如下:在丢失SYN的情况下,str_client需要设置SYN_TIMEOUT,如果在该周期内没有收到SYN ACK,则它会发送另一个SYN并再次设置定时器。它重复此操作,直到它获得SYNACK或超过SYN_MAX_RETRY。在该状态下,它很可能接收SYN。
SRT连接断开
当客户端发送FIN并且服务器相应地使用FINACK进行响应时,采取(断开)连接
图6:SRT连接断开
但是我们可以在这里丢包。在FIN中发生了什么?客户端需要在FIN_TIMEOUT之后发送另一个FIN,直到FIN_MAX_RETRY。如果FINACK丢失会发生什么?客户端必须等待重传FIN_MAX_RETRY以尝试获得FINACK。如果它没有得到FINACK,它在等待期后转换到CLOSE状态,并假定连接有时间以有序的方式关闭。
客户端和服务器端实现FSM。
FSM由有限数量的状态组成。状态转换由状态机和EVENT / ACTION控制。基本上,在例如在客户端 FSM上的状态下,例如,假设其处于状态 = SYNSENT并且发生事件 SYN_TIMEOUT,则适当的ACTION 发送SYN。检查客户端FSM,看看是否是这种情况。
客户端FSM
在客户端TCB中在结构的“状态”元素中维护的状态如下:
//states of client
#define CLOSED 1
#define SYNSENT 2
#define CONNECTED 3
#define FINWAIT 4
当实现协议时,您将需要咨询这里所示的状态机,以确定客户端和服务器的状态转换,因为在连接建立和拆除期间交换段。这里SRT服务器状态机如图2所示。8。SRT客户端状态机如图1所示。
SRT客户端FSM
在服务器TCB中在结构的“状态”元素中维护的状态如下:
//states of server
#define CLOSED 1
#define LISTENING 2
#define CONNECTED 3
#define CLOSEWAIT 4
服务器端FSM
要想弄懂一个技术,我一贯的学习路线,就去读它的源码,再动手实现它
。自己动手主动学习,一点一点地将它搭建起来。一来满足自己的好奇欲,二来本质的深刻理解使我能够更放心地使用它
。于是上知乎搜索如何更好的学习TCP/IP协议,就淘到了达特茅斯的lab DartNet,该实验有框架代 码。省去很多琐碎的工作。正合我意,撸起袖子开启了网络协议栈的不归路。
我将该项目的所有代码实现托管在github上, 传送门 .欢迎start
DartNet是一个类TCP/IP协议栈
。它的核心是简单可靠传输(SRT)层和简单网络协议 (SNP)层
。
Simple Reliable Transport(SRT)实现了运输层TCP的功能 ,保证数据流的可靠传输。Simple Network Protocol (SNP)实现了网络层IP的功能,完成网络层的两个重要功能:转发和选路。
DartNet整个实验运行起来的框架
由于DartNet不能在互联网的路由器上运行我们的代码,为了绕过不能更改路由器代码的限制,于是设计了覆盖网络层(overlap),在终端系统中构建网络节点作为路由
。最终DartNet的简单可靠传输(SRT)层和简单网络协议(SNP)层在构建的覆盖网络层(overlap)上运行,完成DartNet协议栈的测试与实验。
下图所示的DartNet协议栈,客户端和服务器创建套接字来完成两个主机间的数据传输
。DartNet是一个自顶向下的分层架构。第n-1层为第n层提供服务和API。SRT为应用程序提供字节流的可靠传送,SNP提供类似于IP的端系统之间的转发和选路。覆盖层运行DartNet堆栈的端主机网络。
DartNet的通信协议栈
在DartNet中,每对相邻节点之间存在TCP连接。在每个节点上,存在覆盖网络(overlap)层,简单网络协议(SNP)层,简单可靠传输(SRT)层和应用层
DartNet API函数调用
接下来的几篇文章,会对每一层的功能原理,以及数据结构
进行相关的介绍。上图中的API函数将在对应层一一实现
。
要想弄懂一个技术,我一贯的学习路线,就去读它的源码,再动手实现它
。自己动手主动学习,一点一点地将它搭建起来。一来满足自己的好奇欲,二来本质的深刻理解使我能够更放心地使用它
。于是上知乎搜索如何更好的学习TCP/IP协议,就淘到了达特茅斯的lab DartNet,该实验有框架代 码。省去很多琐碎的工作。正合我意,撸起袖子开启了网络协议栈的不归路。
我将该项目的所有代码实现托管在github上, 传送门 .欢迎start
DartNet是一个类TCP/IP协议栈
。它的核心是简单可靠传输(SRT)层和简单网络协议 (SNP)层
。
Simple Reliable Transport(SRT)实现了运输层TCP的功能 ,保证数据流的可靠传输。Simple Network Protocol (SNP)实现了网络层IP的功能,完成网络层的两个重要功能:转发和选路。
DartNet整个实验运行起来的框架
由于DartNet不能在互联网的路由器上运行我们的代码,为了绕过不能更改路由器代码的限制,于是设计了覆盖网络层(overlap),在终端系统中构建网络节点作为路由
。最终DartNet的简单可靠传输(SRT)层和简单网络协议(SNP)层在构建的覆盖网络层(overlap)上运行,完成DartNet协议栈的测试与实验。
下图所示的DartNet协议栈,客户端和服务器创建套接字来完成两个主机间的数据传输
。DartNet是一个自顶向下的分层架构。第n-1层为第n层提供服务和API。SRT为应用程序提供字节流的可靠传送,SNP提供类似于IP的端系统之间的转发和选路。覆盖层运行DartNet堆栈的端主机网络。
DartNet的通信协议栈
在DartNet中,每对相邻节点之间存在TCP连接。在每个节点上,存在覆盖网络(overlap)层,简单网络协议(SNP)层,简单可靠传输(SRT)层和应用层
DartNet API函数调用
接下来的几篇文章,会对每一层的功能原理,以及数据结构
进行相关的介绍。上图中的API函数将在对应层一一实现
。