Stanford University CS144 Lab2 The TCP Receiver

Love The Way You Lie 2022-09-12 01:59 125阅读 0赞

### 文章目录 ###

*   *  前引
     *  Lab2 The TCP Receiver
     *   *  获取实验文档+调试方法介绍
         *  1、Overview(总览)
         *  2、Getting started(开始)
         *   *  编译报错 获取LIBPCAP-DEV
         *  3、Translating between 64-bit indexes and 32-bit seqnos(3.1在64位索引和32位序列号之间的转换)
         *   *  1、任务介绍
             *  2、实现思路(wrap unwrap)
             *  3、代码实现(wrapping\_integers.cc)
             *  4、编译运行 测试用例检验程序 (100% tests passed)
         *  4、Implementing the TCP receiver(实现TCP接收器)
         *   *  1、实现前想说点的
             *  2、任务介绍
             *  3、实现思路(segment\_received ackno window\_size）
             *  4、最终代码实现(tcp\_receiver.hh tcp\_receiver.cc)
             *   *  新增函数(byte\_stream.cc stream\_reassembler.cc)
                 *  代码实现(tcp\_receiver.hh)
                 *  代码实现(tcp\_receiver.cc)
             *  5、编译运行 测试用例检验程序 (100% tests passed)

--------------------

## 前引 ##

--------------------

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

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

--------------------

## Lab2 The TCP Receiver ##

--------------------

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

--------------------

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

**下载下面的这个即可**  
![在这里插入图片描述][f6a0e48a253e4d1092df872a4766f9be.png]

--------------------

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

--------------------

### 1、Overview(总览) ###

--------------------

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

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

### 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`的转换**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 1]

--------------------

#### 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`**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 2]

--------------------

### 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`的话 哈哈 那如果以后你写类似的代码就要小心了!**  
**我们实际跑一下看一下结果是什么？**

![在这里插入图片描述][cf5fe74b0e8c45e3bc185f8d23ff0048.png]

--------------------

**啊？ 怎么会是`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 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.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人也是需要休息的 哈哈**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 3]

[CS144 Lab Assignments]: https://cs144.github.io/
[f6a0e48a253e4d1092df872a4766f9be.png]: /images/20220828/3182c4d8d7e34a768c6e13719ddfc4bc.png
[Stanford University CS144]: https://love6.blog.csdn.net/article/details/120408368
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/6f72eb0dc18f46c6b12ec21eb7dc2ebc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/0e26da3b54f74100aaf5e20878f8cc2d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/277ad5deac9d4322a6e7658fff52881e.png
[cf5fe74b0e8c45e3bc185f8d23ff0048.png]: /images/20220828/8411a2b08de24355b6315caf3f672815.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/4a5552db73bd44de9b84ea835d6fe156.png