Stanford University CS144 Lab2 The TCP Receiver

---

前引

---

各位好 我又来做Lab2了 其实做到现在 我并不很想再继续做下去了 但是呢 哈哈 我是一个比较有执念的人 很多事情做到中间就放弃 我会一直纠结 所以 我的执念让我继续坚持做这个Lab

做到现在 我感觉一个很明显的感觉 就是这个Lab所带给我的挫折和挫败感远大于完成Lab的那一刻喜悦与开心 但没有办法 再不想做 还是得继续做下去 那就继续往下走吧 争取一天一个Lab 这段时间做Lab我都把刷题留给做Lab了 希望后面更顺利一点点

---

Lab2 The TCP Receiver

---

获取实验文档+调试方法介绍

---

为了方便大家 还是一样下面贴一下文档获取链接吧
CS144实验文档获取链接
CS144 Lab Assignments

下载下面的这个即可

---

老样子 贴一下调试方法的博客链接
Stanford University CS144 调试方法

---

1、Overview(总览)

---

对于文章原文的话 我还是稍微写一下就好了
我们这个Lab 目标现在就是写出TCP Receiver 我现在很多时候不再看机翻的文档了 都在尽量看英文的原文文档 因为机翻很多地方都没有介绍清楚 - - 导致意思我都不懂

反正这个Lab有两个任务 对于真的实现TCP RECEIVER的时候我再来介绍一下实现思路吧
下面贴个图

---

2、Getting started(开始)

---

做个Lab1的这一步都还是比较熟了
进入路径sponge 输入git merge origin/lab2-startercode 即获得了文档所需要的材料了

然后我们可以尝试一下进入sponge/build 编译一下 然后下面就报了错 详情看下面

---

编译报错 获取LIBPCAP-DEV

---

以下是在我编译的时候报的错

LIBPCAP
linked by target “tcp_parser” in directory /home/cooiboi/CS144/sponge/tests
linked by target “tcp_parser” in directory /home/cooiboi/CS144/sponge/tests

解决办法 sudo apt-get install libpcap-dev
安装了libpcap-dev库后 编译就正常了

---

3、Translating between 64-bit indexes and 32-bit seqnos(3.1在64位索引和32位序列号之间的转换)

---

1、任务介绍

---

这个部分其实不难 但是我写了还是挺久的 - - 呜呜
主要就是理解这个他要我们干什么 因为我写了很久 所以觉得像我一样的hxd应该还是很多的 每一部分的分析还是细致点好一点吧 我写的久 主要是没有理解checkpoint干什么的 还有对于无符号整型数 负数溢出那个地方没有处理 那下面就说一下吧

---

大家先看一下官方文档中说的三条原则吧

1、Your implementation needs to plan for 32-bit integers to wrap around
您的实现需要计划用32位整数来完成

2、TCP sequence numbers start at a random value.
TCP序列号从一个随机值开始

3、The logical beginning and ending each occupy one sequence number
逻辑的开始和结束每个都占据一个序列号：除了确保接收所有字节的数据外，TCP还确保流的开始和结束被可靠地接收

---

好了 作为热身工作 Warm-up 要求我们转换seqno和64位序号
为什么会有这部分呢 大家还记得我们上一个Lab所实现的聚流器吗 那个Lab我忘说了 因为TCP传输我们认为是可以传输没有限制大小的字节数的
但是很明显 如果学习过TCP首部字段行的话 可以很清楚的知道一般TCP首部是20字节 UDP一般是8字节 而对我们的序列号的话 一共是32位 合计4字节

但为什么不用64位呢 哈哈 可能第一个是历史原因没有我们的传输文件不会发展到有那么大吧（我猜的）第二个就是 如果首部字段行多了 那开销就大了 很简单的道理^^ 首部字段行每一个字节都很宝贵 因为每一个TCP连接都要安装上这样的头部

---

好了 大概介绍了一下原因 那就到了介绍我们要做什么了

我们就是目标把32位的seqno 转换为64位的序号 因为我们传输进入流聚合器的时候 序号就是64位index 但是我们的TCP协议传输进去的时候 只传输有效载荷段 即不传输SYN FIN的开始和结束的相对于的序号的载荷 那个我们现在不处理 现在只处理32位seqno与64 absolute seqno的转换
下面的截图是假设 我们要传输一个字符串是cat 对于32位的seqno起始位置假设为pow(2,32) -2 即ISN为pow(2,32) -2 有效载荷和SYN FIN的相对应的值

最后说一下 我们传输到最后进入stream的index 即没有SYN和FIN这个转换比较简单 我们任务是处理seqno <-> absolute seqno的转换

---

2、实现思路(wrap unwrap)

---

好了 做这部分我还是好好的讲一下思路吧 - - 我的代码相比其他的博客实现要多那么几行 但是这就是我开始就想到的 就直接写了

WrappingInt32 wrap(uint64_t n, WrappingInt32 isn)

这个函数是 absolute seq -> seqno的转换
给了起始的isn 对于absolute seq 我们直接取(1<<32)的余数即可 因为对于seqno 连续到了(1<<32)就又会回到原点isn 所以我们对absolute seq % (1<<32) 即可得到seqno相对isn的相对增量 我们再对isn + 相对增量 即得到seq 如果此时seq >= (1<<32) 再取一次%(1<<32) 取余即可

---

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint)

这个函数相对 wrap要更难一点了 首先为什么会有checkpoint这个存在 我来详细介绍一下 因为如果 n与isn相对增量假如为17 那么ret_num 则会有无数种情况 17、(1<<32）+ 17、(1<<33) + 17等等
那么对于我们的 checkpoint 则是限制了范围 因为这些答案之间都差距了 (1<<32) 所以我们只要取离 checkpoint 最近的那一个答案即可
即 checkpoint + (1<<31) 或者 checkpoint - (1<<31) 范围之内都是我们的正确答案 我们按照这种思路去实现即可

下面再补两句 对于unwrap 我举个例子 加入n-isn的相对增量为30 而checkpoint在(1<<32) ~ (1<<33)之间 那么我们的答案有三个情况 (1<<32)+30或者(1<<33)+30 无论怎么样最多出现两种情况 我们从中取一种即可

对了 还要一定一定要注意 运算的时候要注意负数溢出的情况 因为我们参与运算如果有-号的话 相减的话 则会溢出 然后wrap 所以要避免这种情况

---

3、代码实现(wrapping_integers.cc)

---

#include "wrapping_integers.hh"// Dummy implementation of a 32-bit wrapping integer// For Lab 2, please replace with a real implementation that passes the
// automated checks run by `make check_lab2`.template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {
    }using namespace std;//! Transform an "absolute" 64-bit sequence number (zero-indexed) into a WrappingInt32
//! \param n The input absolute 64-bit sequence number
//! \param isn The initial sequence number
WrappingInt32 wrap(uint64_t n, WrappingInt32 isn)
{
    uint64_t num = 1;num <<= 32;uint32_t seqno = 0,wrapped_num = n%num;seqno = (isn.raw_value() + wrapped_num) % num;return WrappingInt32{
    seqno};
}//! Transform a WrappingInt32 into an "absolute" 64-bit sequence number (zero-indexed)
//! \param n The relative sequence number
//! \param isn The initial sequence number
//! \param checkpoint A recent absolute 64-bit sequence number
//! \returns the 64-bit sequence number that wraps to `n` and is closest to `checkpoint`
//!
//! \note Each of the two streams of the TCP connection has its own ISN. One stream
//! runs from the local TCPSender to the remote TCPReceiver and has one ISN,
//! and the other stream runs from the remote TCPSender to the local TCPReceiver and
//! has a different ISN.
uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) 
{
    uint64_t num = 1;num <<= 32;uint64_t ret_num = (checkpoint/num)*num;ret_num += (n.raw_value() >= isn.raw_value()) ? n.raw_value() - isn.raw_value() : n.raw_value() + num - isn.raw_value();uint64_t checknum = (ret_num + num >= checkpoint) ? ret_num + num - checkpoint : checkpoint - ret_num - num; if(checknum < (num>>1)) ret_num += num;else if(ret_num >= num){
    checknum = (ret_num - num >= checkpoint) ? ret_num - num - checkpoint : checkpoint + num - ret_num; if(checknum < (num>>1)) ret_num -= num;}return ret_num;
}

---

4、编译运行 测试用例检验程序 (100% tests passed)

---

我们make后 输入ctest -R wrap

---

4、Implementing the TCP receiver(实现TCP接收器)

---

1、实现前想说点的

---

终于终于终于写出来了 无语 - - 因为一个地方我改了三个小时 本来实现起来很简单的 但是就是因为一些地方出错了 但总之现在写出来 所以请大家看一下下面的代码 能不能心里面想一下答案是多少

#include <iostream>
using namespace std;int main()
{
    bool a = true,b = true;uint64_t num = (a) ? 1 : 0 + (b) ? 1 : 0;cout << num << endl;return 0;
}

---

如果你心里面想的和我想的是一样的 你觉得是多少？
如果是2的话 哈哈 那如果以后你写类似的代码就要小心了!
我们实际跑一下看一下结果是什么？

---

啊？ 怎么会是1？ 哈哈哈 正确的写法应该是这样 你看到你就明白了
？后面的 +语句被连同到之前的语句里面去了
所以实现起来是 (a) ? 1 : 1 所以之前的结果是1 以后写这种句子 尽量外面加个括号 培养良好编程习惯

#include <iostream>
using namespace std;int main()
{
    bool a = true,b = true;uint64_t num = ((a) ? 1 : 0) + ((b) ? 1 : 0);cout << num << endl;return 0;
}

---

2、任务介绍

---

在做完上面的热身Lab后 再来完成这个Lab 我做完这个Lab后才发现 分布来做是真的很有必要的 因为中间会涉及两个数字的转换挺多次的 如果函数不分开来弄的话 很容易弄混 而且也挺难一次就实现出来的

我们先来介绍一下这个实验吧 刚刚把实验完成了 我就出校门吃晚饭去了 吃完了玩了会手机才来编辑博客- -
这个部分就是让我们实现一个TCP Receiver 聚合消息的工作我们之前已经完成了 所以这部分的代码相对来说没有那么多 但是细节还是挺多的

TCPReceiver 我们只负责编写三个函数

void TCPReceiver::segment_received (const TCPSegment &seg)
接受TCPSegment的数据报 我们把数据存入到 _reassembler 中 因为有可能随时来的时候会是乱序 TCPSegment里面有SYN FIN Seqno ACK 其实就是一个完整的TCP数据报 详情请看tcp_segment.hh

optional TCPReceiver::ackno() const
返回我们的ACK序号 如果做过Wireshark的hxd应该明白是指的是什么 就是累计确认 ACK序号前的都已经被确认了 换句话来说 这个返回的数是我们下一个需要的字节序号
注意 如果此时还没有SYN发送建立的话 我们返回空值即可

size_t TCPReceiver::window_size() const
这个滑动窗口 刚开始我还想了半天是指的是什么 这里指的是 我们窗口大小 - byte_stream 在应用层中里面的还没有发送出去的缓冲区大小 下面是英文原文
In other words: it’s the capacity minus the number of bytes that the
TCPReceiver is holding in the byte stream

---

3、实现思路(segment_received ackno window_size）

---

下面就来到详细的实现思路了
先说一个需要注意的点
我们这里的实现是涉及了一点点三次握手 只不过三次握手不是仅仅在这里处理 但是对于这个Lab我们仅处理好传输进来的数据就好了 详细的三次握手

比如测试用例里面就有
FLAGS = SYN FIN 即SYN FIN同时存在 - - 但是还是需要处理一些基本的情况 但是对于这种情况也是有的 第一次SYN就直接带着数据来的 这个也是需要算进去的

文档中对于这部分处理是这样说的: 即表示我们需要把所有含有数据的包 或者带有FIN的数据包 都要送入StreamReassembler 那这部分先说到这里 我们下面一个函数一个函数看

Push any data, or end-of-stream marker, to the StreamReassembler. If the FIN flag is set in a TCPSegment’s header, that means that the last byte of the payload is the last byte of the entire stream. Remember that the StreamReassembler expects stream indexes starting at zero; you will have to unwrap the seqnos to produce these

---

void TCPReceiver::segment_received(const TCPSegment &seg)

处理TCPSegment 我们至少需要详细的看一下下面的文件 还有一些需要自己去看看 路径在sponge/libsponge/tcp_helpers sponge/libsponge/util
buffer.hh TCPSegment.cc TCPSegment.hh TCPHeader.hh
看了之后就知道文档中对于一些数据 头文件中怎么命名的了
我们需要记录在第一次出现 SYN 记录好ISN 之后再把DATA提取出来 如果报文中有FIN 的话 就需要把push_substring里面的bool设置为true即可 然后我们需要记录一下 我们目前写入了多少数据 即为ackno准备数据

---

optional<WrappingInt32> TCPReceiver::ackno() const

这个没有那么难 但还是有一些细节需要注意
即对于SYN FIN 是需要单独占两个位置的 如果SYN出现了 我们就需要+1 如果FIN也出现了 我们就需要再+1 提示就提示在这里

---

size_t TCPReceiver::window_size() const

在上面已经讲过这个问题了 就是用size - byte_stream里面还没有发送出去的数据 - - 文档中说是这个 那我们就这样实现吧

---

4、最终代码实现(tcp_receiver.hh tcp_receiver.cc)

---

新增函数(byte_stream.cc stream_reassembler.cc)

---

byte_stream.hh byte_stream.cc新增如下

size_t bytes_has_not_read() const;
size_t ByteStream::bytes_has_not_read() const {
     return bytes_written() - bytes_read(); 

---

stream_reassembler.hh stream_reassembler.cc

uint64_t has_recved_bytes() const;
uint64_t StreamReassembler::has_recved_bytes() const{
     return static_cast<uint64_t>(start_idx);}

---

代码实现(tcp_receiver.hh)

---

#ifndef SPONGE_LIBSPONGE_TCP_RECEIVER_HH
#define SPONGE_LIBSPONGE_TCP_RECEIVER_HH#include "byte_stream.hh"
#include "stream_reassembler.hh"
#include "tcp_segment.hh"
#include "wrapping_integers.hh"#include <optional>//! \brief The "receiver" part of a TCP implementation.//! Receives and reassembles segments into a ByteStream, and computes
//! the acknowledgment number and window size to advertise back to the
//! remote TCPSender.
class TCPReceiver {
    StreamReassembler _reassembler;//! Our data structure for re-assembling bytes.size_t _capacity;//! The maximum number of bytes we'll store.bool recv_syn = false;WrappingInt32 isn{
    0};uint64_t recv_bytes = 0;public://! \brief Construct a TCP receiver//!//! \param capacity the maximum number of bytes that the receiver will//! store in its buffers at any give time.TCPReceiver(const size_t capacity) : _reassembler(capacity), _capacity(capacity) {
    }//! \name Accessors to provide feedback to the remote TCPSender//!@{
    //! \brief The ackno that should be sent to the peer//! \returns empty if no SYN has been received//!//! This is the beginning of the receiver's window, or in other words, the sequence number//! of the first byte in the stream that the receiver hasn't received.std::optional<WrappingInt32> ackno() const;//! \brief The window size that should be sent to the peer//!//! Operationally: the capacity minus the number of bytes that the//! TCPReceiver is holding in its byte stream (those that have been//! reassembled, but not consumed).//!//! Formally: the difference between (a) the sequence number of//! the first byte that falls after the window (and will not be//! accepted by the receiver) and (b) the sequence number of the//! beginning of the window (the ackno).size_t window_size() const;//!@}//! \brief number of bytes stored but not yet reassembledsize_t unassembled_bytes() const {
     return _reassembler.unassembled_bytes(); }//! \brief handle an inbound segmentvoid segment_received(const TCPSegment &seg);//! \name "Output" interface for the reader//!@{
    ByteStream &stream_out() {
     return _reassembler.stream_out(); }const ByteStream &stream_out() const {
     return _reassembler.stream_out(); }//!@}
};#endif // SPONGE_LIBSPONGE_TCP_RECEIVER_HH

---

代码实现(tcp_receiver.cc)

---

#include "tcp_receiver.hh"// Dummy implementation of a TCP receiver// For Lab 2, please replace with a real implementation that passes the
// automated checks run by `make check_lab2`.template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {
    }using namespace std;void TCPReceiver::segment_received(const TCPSegment &seg)
{
    TCPHeader seg_header = seg.header();Buffer seg_payload = seg.payload();if(seg_header.syn && !recv_syn){
    isn = seg_header.seqno;  recv_syn = true;}if(recv_syn && (seg_payload.str().size() > 0 || seg_header.fin)){
    if(seg_header.syn) seg_header.seqno = seg_header.seqno + 1;uint64_t send_idx = unwrap(seg_header.seqno-1,isn,recv_bytes);bool fin = seg_header.fin;_reassembler.push_substring(seg_payload.copy(),send_idx,fin);recv_bytes = _reassembler.has_recved_bytes();}
}optional<WrappingInt32> TCPReceiver::ackno() const
{
    if(!recv_syn) return nullopt;uint64_t plus_num = ((recv_syn) ? 1 : 0) + ((_reassembler.stream_out().input_ended()) ? 1 : 0);return wrap(recv_bytes+plus_num,isn); 
}size_t TCPReceiver::window_size() const 
{
    return _capacity - _reassembler.stream_out().bytes_has_not_read();
}

---

5、编译运行 测试用例检验程序 (100% tests passed)

---

下面我们编译即可 进入sponge/build make check_lab2即可检验
终于写完啦 希望每一步代码都走得很稳 这样之后就不会再回来检查了 那各位看官再见啦 IT人也是需要休息的 哈哈