[系统运维]Stanford University CS144 Lab2 The TCP Receiver

前引

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

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

Lab2 The TCP Receiver

获取实验文档

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

下载下面的这个即可

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）

下面就来到详细的实现思路了
先说一个需要注意的点
我们这里的实现不涉及三次握手 三次握手不是在这里处理 我们仅处理好传输进来的数据就行了 不需要管是否刚开始先建立三次握手连接

比如测试用例里面就有
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 reassembled
    size_t unassembled_bytes() const { return _reassembler.unassembled_bytes(); }

    //! \brief handle an inbound segment
    void 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.seqno == isn) 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人也是需要休息的 哈哈