CS144: LAB0
0.写在前面
- 这更倾向于个人完成 lab 后的思考和总结,而不是 CS144 lab 答案或者 lab document 翻译(指南或者翻译已经有大佬做的很好了,下面已经贴出链接)
- 出于斯坦福“Honor Code”的要求,文内也尽量避免出现关键代码,忘了是做CSAPP还是MIT6.S081 的 lab 时看到的一句话:抄答案会“使你丢失必要的思考和训练”,而我们主动学习国外这些优秀的公开课,不正是为了得到“必要的思考和训练”吗,切勿南辕北辙,写给自己,勿忘初心。
- CS144很多大佬的blog:https://csdiy.wiki/计算机网络/CS144/
1.使用telnet体验流经网络的可靠的双向字节流
telnet是基于TCP的协议,主要作用是远程登录服务器,相比SSH的登录方式,不安全,因为数据是明文传输。(SSH服务使用22端口,telnet服务使用23端口)
登录远程服务器:telnet ip 23
(需要远程服务器开启23端口器安装了telnet服务)
telnet 可以用于和任意端口建立连接,如通过telnet可以向服务器发送http请求。
-
telnet可以与远程服务器建立连接:
telnet cs144.keithw.org http
(http代表80端口) -
发送HTTP请求:
GET /hello HTTP/1.1 Host: cs144.keithw.org Connection: close
-
接下来就可以收到服务器发回的响应
这个telnet的例子是想说明,利用telnet(TCP),客户端与服务器之间建立了可靠的双向字节流:将字节以特定的顺序输入到客户端,这些字节会被以相同的顺序传送到服务器端,然后服务器端的响应也会传送回到客户端。
2.使用telnet体验本机的可靠双向字节流
- 本机使用netcat开启服务端:
//以本机为服务器监听 9090 端口,并输出详细信息
netcat -l -v 9090
- 开启另一个终端窗口,使用telnet开启客户端:
//连接本机的9090端口
telnet localhost 9090
- 这样服务端和客户端之间就建立起了可靠的双向字节流。在任意一端输入任意字符,回车发送,字符就会出现在另一端。
3.Modern C++
这一部分我理解的不是很深,但觉得很重要,目前 lab document中给出了 12 条建议,我也只是在编程中尽量遵循这些建议。
举 2 个简单的例子:
- 其中一条建议是:
Never use new or delete.
因为可能会造成内存泄露,所以下面我们创建套接字对象的时候,就不要使用Socket *socket = new Socket();
而是直接使用声明的方式:Socket socket;
- 另一条建议是:
Avoid C-style strings (char *str) or string functions (strlen(), strcpy()). These are pretty error-prone. Use a std::string instead.
,所以下面我们使用字符串拼接HTTP请求的时候,不要使用char * str = " GET /index HTTP/1.1 ..."
这种形式,而是使用std::string httprequest = "GET \index HTTP/1.1..."
4.webget函数
从这里才算真正开始写lab,这个lab要求的是:使用斯坦福专门为CS144准备的 TCP 库:Sponge,进行Socket编程,实现一个客户端,与服务端建立连接后可以获得服务端的web响应。这个库其实就是对于Linux关于Socket编程的系统调用的再封装,只不过是用Modern C++的方式封装了。
写webget函数必须很熟悉Socket编程,否则无法完成这部分作业的。
关于Socket编程的资料太多了,这里就不提了,说白了就是API调用,从操作系统到各种语言,connect,listen,accept等函数已经为你贴心地封装好了,搞清楚调用顺序就好。
有了Socket编程的知识,再阅读一下TCPSocket的refernce:https://cs144.github.io/doc/lab0/class_t_c_p_socket.html (特别说明,TCPSocket给出了示例代码,很有参考意义),明白了我们只需要写客户端的代码,所以只需要两步:
- 创建客户端Socket套接字
- 与服务端进行connect
- 发送HTTP请求
- 打印服务端返回的响应
其中第 4 点需要注意:客户端如何判断已经接收完毕响应?lab doc中有提示,当客户端从字节流中读到EOF(end of file)时,结束读取。开始我没有仔细看 Sponge 中 FileDescriptor (TCPSocket的父类)的成员函数,所以在判断是否读到 EOF 时使用了很笨的方法:
//一直读取,直到从字节流中读不到任何字节再结束
while (true)
{
auto received = tcpsocket.read();
cout << received ;
if (received.size() == 0) {
break;
}
}
tcpsocket.close();
虽然以上代码也可以通过测试,但明显是不对的,在仔细看了 FileDescriptor 的成员函数后,发现了有eof判断的方法:
bool FileDescriptor::eof() const
所以判断EOF的代码可以优雅一点:
while (!tcpsocket.eof())
{
auto received = tcpsocket.read();
cout << received;
}
tcpsocket.close();
5.基于内存的可靠字节流
我认为上一部分的 webget 中最关键的一行代码就是对于 connet 函数的调用,connect之后(默认服务端已经出于监听状态),可靠的字节流被建立了,通过这个字节流,我们可以发送请求,接受响应,一切就像最开始使用 telnet 建立的可靠字节流一模一样。使用 telnet,或者使用Socket编程建立的可靠字节流其实就是TCP连接。
lab0一直在给我们示范什么是可靠的字节流,从最开始使用现成的telnet服务、到我们自己利用Sponge库进行Socket编程,最后这个部分要求我们在内存中实现可靠字节流。
内存中的可靠字节流这个概念其实很简单,就是需要实现一个传输字节的容器,容器的元素是保存在内存中的,比如C++的vector,Java的Arraylist,每种编程语言都有自带的 n 种数据结构,然后给这个容器提供一些方法,可以往这个容器里写数据,也可以从这个容器中读数据,需要保证读出来的顺序和写入的顺序一致。借助这样一个容器,writer和reader就可以传输数据了。这就是基于内存的可靠字节流。
流量限制的概念:lab doc解释的很好,假设我们这个容器的容量只有1byte,它依旧可以传送一个1TB的字节流,只要 writer 每次写 1 个字节,然后在 writer 写下一个字节之前,reader 把这个字节读走。所以在程序中涉及到三个数据大小的的概念:
- writer 准备写入容器的数据大小:data.size()
- 容器中现有的数据多少:container.size()
- 容器的容量:container.capacity
所以一个简单的逻辑就是 data.size() <= capacity - container.size()
时,data才能被全部写入容器中,否则超出的部分会被丢掉,read函数也有类似的逻辑。
lab doc已经给出了writer和reader需要实现的接口,其中 read 的概念是 peek + pop 两步完成的:
- peek_output:将数据从容器中复制出来,这是read想要读到的数据
- pop_output:将数据从容器中删除,完成read操作
最后一点是选择什么容器暂时存放字节流,考虑到整门课程的lab是累加进行的,后面的 lab 会看到ByteStream是整个TCP协议实现的核心组件。所以前面的工作后影响到后面的lab,建议开始就选择高效的实现。考虑这几个C++中的顺序存储结构的容器:vector、list、deque。由于传输字节流本质是大量的插入和删除操作,deque或许是个不错的选择~
CS144: LAB1
0.概述
这个lab开始给我们展现这门课程的全貌,如果说做完lab0的in memory ByteSteam后还有些云里雾里的,那么看完这幅图一定会豁然开朗,lab0实现的ByteStream是实现TCPConnection的核心模块,因为它提供了最基础的字节流操作:读、写、判断eof等。
基于这个核心模块,本节要求实现图中的StreamReassembler,字节流重组器,测试会为你提供无冲突的、但是可能重复的、有唯一index标识的n个字节流片段,他们都属于一个完整的、更大的字节流,需要我们把这些字节流片段重新缝合为正确的顺序:
- 无冲突的:如果存在字节流片段
data="a" index=0
,那么就不可能存在data="b" index=0
这样的片段 - 可能重复的:如果存在字节流片段
data="a" index=0
,可能存在data="ab" index=0
这样的片段 - 有唯一index标识:字节流中每一个字节都有自己的index标识,用来标识他在整个字节流中的位置
//提供3组字节流片段
data="bc" index=1 eof=0
data="ab" index=0 eof=0
data="de" index=3 eof=1
//经过 StreamReassembler 缝合后的字节流片段
"abcde" eof=1
1.思路
这个lab乍听上去很简单,已经给了字节流的唯一index,看上去就是简单的字符串拼接,但要想写出无bug的程序还是有点难度的。我中间测试通过率一度卡在94%,但是最后的bug一旦改正另一个地方就会出bug,陷入了矛盾的境地,索性换了一种思路,完全推倒重来,终于顺利通过。(考虑到所有lab都是累加进行的,测试通过率不到100%不建议开下一个lab,否则回头补作业很头秃)
难点:
-
字符串情况很复杂,需要判断去重,需要正确返回eof标志,拼接的过程和整个字节流的write、read操作是随机混合的,是否write还要考虑到lab0实现的ByteStream的capacity的限制(注意这个capacity不是下图的capacity,下图的capacity指的是StreamReassembler的capacity,即map的最大容量,在代码中这两个值是一样的)
-
关于capacity的理解:下图给我们一些启示,StreamReassembler是包括ByteStream的,一个字节进入StreamReassembler后,如果不能缝合,就属于下图的红色部分(unassembled byte);如果成功缝合并写入ByteStream,就属于绿色部分(re-assembled byte);如果被ByteStream的read()操作读取,就从ByteStream中pop,属于蓝色部分。StreamReassemble的capacity就是红色部分加绿色部分。同时ByteStream的capacity也是这么大,因为StreamReassemble同时使用这个值初始化了ByteStream。
界定游标定义为红绿交界处的游标,这个游标的含义就是:此游标之前的byte全部属于缝合好的。
思路1:
以界定游标为标志,给出的字节流片段分为三种情况
- 整个片段在界定游标左边的
- 整个片段包住界定游标的
- 整个片段有界定游标右边的
优点:高效
缺点:去重很麻烦(最开始使用这种思路,编码实现后,测试通过率一直卡在94%,最后放弃这种思路)
思路2:
经过强哥启发,换了一种数据结构,如unorderedmap,key是index,value是一个字节,这样就不用思路1中的merge和去重操作了,核心函数push_substring
的代码只有大约30行,而且错误率很低。
优点:思路简单,实现简单
缺点:空字符串也占据一个bucket,后面的lab可能要特殊处理一下。
2.一个经典的错误
我测试出现的一个经典错误例子是,没有考虑ByteStream的空间
ByteStream.capacity = 2
data="ab" index=0 eof=0
data="cd" index=2 eof=0
read(2)
data="cd" index=2 eof=0
在这个例子中,正确的顺序是:
- "ab"缝合成功,写入"ab",调用
_output_write(&data)
操作返回值是2(如果你的lab0正确实现的话) - "cd"缝合不成功,因为ByteStream中已经没有空间,也不进行写入。
- read(2),ByteStream有空间
- "cd"缝合成功,调用
_output_write(&data)
操作返回值是2,总写入字节是4
如果不考虑ByteStream的空间,就会出现以下情况:
- "ab"缝合成功,写入"ab",调用
_output_write(&data)
操作返回值是2 - "cd"缝合成功,调用
_output_write(&data)
操作返回值是0(silently discarded) - read(2),ByteStream有空间
- "cd"缝合不成功,因为在2中cd已经缝合成功,界定游标已经为4,此"cd"被判定为重复。所以总写入字节是2
3. 测试结果:
CS144: LAB2:the TCP receiver
0.概述
seqno和abs_seqno相互转换的代码就略过了~工具性质比较大,且不算难。lab doc中也给出了最关键的提示:如果两个seqno之间相差offset,那么他们对应的两个abs_seqno之间也相差了offset。
- abs_seqno -> seqno是大范围往小范围的转换,所以 isn (32bit)直接加abs_seqno (64bit)的结果转换为32bit数字自然会溢出,不用我们额外处理。
- seqno -> abs_seqno是小范围往大范围转换,所以每一个seqno 一定对应着不止一个abs_seqno,这就需要checkpoint来指示,我们需要选择哪个abs_seqno作为最终的结果。checkpoint表示上一次seqno -> abs_seqno转换出来的的abs_seqno,我们要选择距离上一个abs_seqno(checkpoint)最近的abs_seqno作为本次seqno -> abs_seqno的结果;为什么要这么选择,因为同一个seqno对应的多个abs->aeqno之间依次相差232,而相邻两次到达的segment之间的abs_seqno相差不太可能超过232
再次祭出这张图,这个lab要求实现图中的TCP receiver,这个Receiver的要做三件事:
- 接收:接收TCPsenment
- 重组:提取TCPsenment中的关键信息:序列号seqno,同步标志SYN,结束标志FIN,数据Payload,将这片字节流缝合到正确的位置(重组功能已经实现,只需实现提取功能)
- 返回关键信息:根据接收情况更新ackno和windowsize,在lab3中要把这两个信息返回给sender
TCPsegment结构是这样的:
seqno:序列号,是从ISN开始,字节流中的每个字节都有自己的序列号,TCPSegment 的序列号是指 Payload 首字节的序号,如果这是一个带有SYN标志的 TCPSegment ,那么 seqno 就是 ISN
SYN:同步标志,表示这个segment就是字节流的第一段
FIN:结束标志,表示这个segment最后一个字节就是字节流的最后一个字节
1.思路
这一节相对来说比较简单,因为从图上看,TCP receiver的核心部件:重组器和ByteStream已经实现了。
-
接收,sponge库已经提供了 TCPSegment、TCPHeader这些类,对于 segment_received 函数直接接收 TCPSegment参数,这个功能无需实现
void TCPReceiver::segment_received(const TCPSegment &seg) { //your code here }
-
重组
-
提取 seqno:需要注意到达 segment_received 函数的 TCPSegment 是无序的,所以我们的第一步应该寻找带SYN 的TCPSegment并设置ISN的值,有了ISN才可以进行 seqno->abs_seqno 的转换,进而得到 stream index(重组器的重要参数)。需要注意ISN没有值时seqno无法进行转换,所以接收到的 TCPSegment 会被丢弃。
-
提取 Payload:这是重组器需要 data
-
提取FIN:FIN标志着字节流输入的结束,TCPSegment的FIN标志会被转换为重组器的eof标志
-
-
返回关键信息:
- ackno:ackno是指receiver不知道的下一个字节的seqno,以上面这幅 “SYN c a t FIN”为例,那么返回的ackno就应该是3
- window_size:指的是reciver还有多少空间,仔细读代码,可以知道这里的空间是指重组器的空间,同时也是ByteStream的空间,即同一个capacity初始化了 TCP Receiver、StreamReassembler、Bytestream的capacity。所以windows_size可以直接使用我们在lab0实现了的:remaining_capacity()
2.测试结果
CS144: LAB3:the TCP sender
0.概述与思路
继续回到这张图,这个lab要求实现图中的TCPSender(以下简称sender),和前三个lab实现的receiver一样,其核心也是一个ByteStream,当有数据写到ByteStream中时,sender需要实现三点:
- 发送,疯狂发送,只要stream中有字节、只要receiver有空间,就发送:根据receiver返回的ackno和win_size,将数据包装为TCPSegment(这一步不必担心,sponge已经提供了TCPSegment类,只需要填充对应的成员变量:SYN、FIN、Payload、seqno 即可)发送出去。
- 跟踪发送情况:不能光发出去就不管了,还要跟踪发出去的TCPSegment是否被receiver接收到了,所以每发出去一个TCPSegment,都要把他加入到跟踪列表,只有收到receiver返回的ackno,才能确定这个segment被接收,如果被接收,那就将其从跟踪列表中删除,如果没被接收,就需要进行第三步。
- 重传:需要我们实现一个全局的重传计时器,即
tick函数
,这个函数会定期被调用,以显示我们距离最近一次成功发送(这里"成功发送"的定义是指收到了“全新”的receiver的ackno,所谓全新,即这个ackno显示,跟踪列表中有TCPSegment被接收到了)过去了多久,如果超过了RTO( resend time out),就需要将跟踪列表中最早的一个segment进行重发,重发之后还要将RTO倍增。
1.有点小坑的地方
-
在读完lab doc后,有一个地方没讲清楚,就是在发送数据之前要不要进行我们熟悉的TCP三次握手,我在写的时候也犹豫了,但是考虑到三次握手需要实现ACK 标志位填充,而lab doc中压根没有提到这一点,于是就没有实现这一点,即第一个segment包直接是ISN+Payload,而不是三次握手的单独SYN包,后面发现有同学第一个单独发送Segment也可以通过测试,想必是lab3的测试并不要求三次握手。
-
关于全局计时器:我们不是给每一个segment都计时,如果时间超过了RTO,就重发这个segment,记住,我们只有一个计时器,也只有一个跟踪列表,如果计时器的时间超过了RTO,就从跟踪列表中找最早的segment就重发,这也提示在具体实现时,跟踪列表要使用顺序存储结构的容器,到时候只要将容器中的第一个segment重发就可以了,list,vector甚至lab1中的deque都可以~
-
重发但是 RTO back off 不倍增的情况:测试中有这样一句话:"When filling window, treat a '0' window size as equal to '1' but don't back off RTO",要求在 window_size 为0时,不要把RTO翻倍,我自己理解是一种尽快断开的策略,因为receiver已经为0了,表示不可接收新的数据,所以sender没必要倍增后再重发,应该尽快冲到最大重发次数后,断开连接,所以有这个逻辑。
if (window_size != 0) { retransmission_timeout_ *= 2; }
-
考虑正在飞的子弹:fill_window函数发送的条件之一是receiver有空间,并不是简单判断
window_size>0
,因为有部分segment正在路上,还没有收到receiver的ackno,所以应该假设这部分segment可以顺利到达,给他们提前留出空间,所以判断逻辑应该是:window_size > bytes_in_flight()
,另外,min(TCPConfig::MAX_PAYLOAD_SIZE, window_size - bytes_in_flight())
也是我们下一次应该发送的字节数~
2.测试结果
CS144: LAB4:the summit
0.概述
虽说本节的 lab doc 强调了我们已经完成了大部分工作,但第lab4的工作量真的不小,这个工作量不是指代码量,而是指debug花费的精力。硬着头皮开干吧,毕竟是summit了嘛。(这个lab花了我整整一周的时间,前4个lab花了我两周时间,中间无休,每天5~6小时)
在做这个lab之前,我一直有一个疑问,之前在课本上学过的三次握手和四次挥手好像和前三个lab并不能很紧密地联系到一起,做完lab4后才有了答案,原来需要在TCPConnection中实现状态的流转。
TCP 状态流转图,摘自:https://users.cs.northwestern.edu/~agupta/cs340/project2/TCPIP_State_Transition_Diagram.pdf
简单解释一下这幅图:图中圆角矩形框中的就是TCP的11个状态(结合代码说就是TCPConnection的状态),而这个状态是由TCP的sender、receiver以及另外两个布尔变量决定的。lab4的任务就是实现这幅图。图中实线就是常规client的状态流转,虚线就是常规server状态流转。
1.思路
lab0~3虽然是面向对象的形式,但思路依旧是面向过程编程的,是线性的,但参考下Linux内核,TCP的状态转换通常是通过一些事件(如接收、发送数据、收到ACK确认等)触发的,当事件发生时,TCP协议的状态会相应地转换到另一个状态,以实现连接的建立、数据传输和连接的关闭等功能。内核会根据协议规范对每个状态及其转换条件进行判断和处理,从而控制TCP连接的状态转换。
基于这个思路,我决定还是使用状态机来实现lab4,到时候代码的可读性更好,也更易于debug。而且lab4已经实现了state()
函数,只需要使用state() == TCPState::State::xxx
就可以方便地判断状态。
以最关键的segment_received()
函数为例,伪代码是这个样子的:
void TCPConnection::segment_received(const TCPSegment &seg) {
if (state() == TCPState::State::LISTEN) {
if (seg.header().syn && seg.header().ack) {
//经过以下两步,状态就可以装换到 SYN_RCVD
receive_ack_and_syn_seg();
send_ack_seg();
}
}
else if (state() == TCPState::State::SYN_RCVD) {
if (seg.header().ack) {
// 接收ACK,就可以进入Established状态
sender_.ack_received(seg.header().ackno, seg.header().win);
receiver_.segment_received(seg);
}
}
else if (state() == TCPState::State::SENT) {
}
...
...
}
只要照着状态流转图严格写判断条件,这个lab的框架很快就可以写好,但是很有可能有bug,因为状态流转图太理想了,他无法反映一些例外情况。
2.状态流转图的例外情况
这个lab的测试的输出信息节省了我们大量的DEBUG时间,以我实际的一个bug为例,在四次挥手阶段:
- 如果服务端处于ESTABLISHED状态,那么接收到FIN包后返回ACK包,进入CLOSED_WAIT状态,这个逻辑很明显,很容易在代码中实现。
- 对于CLOSED_WAIT状态,按照这幅图来看,似乎可以不用接收任何segment,只需要让服务端一直发送数据,发送完毕之后会自动发送FIN(lab3实现),就可以进入下一个状态。
- 但事情没这么简单,你需要像ESTABLISHED状态那样,在CLOSED_WAIT状态时也具有:接收FIN时返回ACK的能力。因为服务端对于客户端发来的ACK可能会丢失,如果客户端没有收到ACK,就会重新发送FIN,此时服务端处于CLOSED_WAIT状态,所以就需要在CLOSED_WAIT状态时也具有:接收FIN时返回ACK的能力。
你看,就像上面说的,如果没有测试,只是看着状态流转图写代码,很容易就会出现某个状态丢失了对于某种包的处理能力的bug。
3.DEBUG的方法
-
在代码中打cout日志,可以在每个主要函数开头都加上:
cout<<"in file: "<<__FILE__<<" in function: "<<__FUNCTION__<<"() at line :"<<__LINE__<<"\n";
这样你在使用make check_lab4的时候,如果遇到出错的test,就可以打出测试函数的调用栈,这种方法至少帮助我解决了90%的bug。(这里我有一个问题,按说cout语句会在每一个调用了这个函数的test中打出来,但是结果是只有Failed的test才会打出,我没有仔细看测试文件是怎么做到这一点的,和朋友讨论后猜测是IO屏蔽之类的?有知道的朋友可以赐教一下,但是这对我们来说是个好事情。)
-
使用抓包软件分析,这个方法在 lab4 doc的第6节:Testing 中讲的很详细,如何使用抓包软件得到TCP传输过程。如下图,左边是client,右边是server,中间是抓包软件,可以看到抓包软件的输出很清晰,segment中SYN、ACK、FIN都有标注。你可以通过观察中间的窗口来查看哪个包被漏发了。
4.最“难”的部分:优雅结束
这个本来不难,但是难点在于lab doc讲的太绕了哈哈,lab4 doc中讲到这一点:The hardest part will be deciding when to fully terminate a TCPConnection and declare it no longer "active."
其实就是4次挥手的过程,如何实现?lab4 doc中第5节的内容就是讲这个的。lab doc中第五节上来就给定了一方可以优雅关闭的4个前提条件:
- 前提条件1:本地receiver已经接收了所有的segment,并且排列完毕,收到了eof,结束。
- 前提条件2:本地sender被上层应用关闭,并且发送了一个FIN包
- 前提条件3:本地发送的所有seg都收到了ACK
- 前提条件4:本地TCPConnection确认peer满足了前提条件3:即peer发送的所有seg都收到了ACK包
看这个很容易被绕晕,实质就是:先发出关闭请求(FIN,第一次挥手)的一方是没有办法确认自己的ACK(第四次挥手)是否被peer收到。
所以为了解决这个问题,就需要先发出关闭请求的一方有一个“徘徊机制”去等待一段时间,下图中的TIME_WAIT状态,如果发现peer没有重发FIN(第三次挥手),就认为ACK(第四次挥手)是被接收到了。
那么放在代码中,如何确认哪一方是先发出FIN包的呢?lab4 doc 5.1节已经给了答案:If the inbound stream ends before the TCPConnection has reached EOF on its outbound stream, this variable needs to be set to false.
即receiver已经收到了eof,但是sender还没有收到eof,就像上图中的服务端收到FIN(第一次挥手)的状态,这时的服务端是不需要徘徊的,最关键的代码在这里:
//满足前提条件1
if (_receiver.stream_out().input_ended()) {
if (!_sender.stream_in().eof()) {
//如果receiver已经收到了eof,但是sender还没有收到eof,无需徘徊
_linger_after_streams_finish = false;
}
//满足前提条件2、3
else if (sender_.bytes_in_flight() == 0) {
//如果无需徘徊,立即结束,否则等待超时后结束
if (!_linger_after_streams_finish || time_since_last_segment_received() >= 10 * _cfg.rt_timeout) {
_active = false;
}
}
}
5.测试
终于,完成了summit,只要认真debug了这个lab,看到这个100%,想必此时内心不是狂喜而是十分平静吧哈哈
性能测试: