这里回顾CS 144 Lab 2: the TCP receiver。

实验资料：

Lab 2: the TCP receiver

准备工作

下载代码以及跑通流程

git checkout -b lab2-startercode
git fetch
git merge origin/lab2-startercode
cd build
make -j4 && make check_lab2

接口

// Construct a `TCPReceiver` that will store up to `capacity` bytes
TCPReceiver(const size_t capacity); // implemented for you in .hh file

// Handle an inbound TCP segment
//
// returns `true` if any part of the segment was inside the window
bool segment_received(const TCPSegment &seg);

// 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;

// The window size that should be sent to the peer
//
// Formally: this is the size of the window of acceptable indices
// that the receiver is willing to accept. It's the difference between
// (a) the sequence number of the end of the window (the first index that
//     won't be accepted by the receiver) minus
// (b) the sequence number of the beginning of the window (the ackno).
//
// Operationally: it's the capacity minus the number of bytes that the
// TCPReceiver is holding in the byte stream.
size_t window_size() const;

// number of bytes stored but not yet reassembled
size_t unassembled_bytes() const; // implemented for you in .hh file

// Access the reassembled byte stream
ByteStream &stream_out(); // implemented for you in .hh file

说明

测试的log位于：

/cs144/sponge/build/Testing/

代码

序列号

分析和重点

记号：

stream index($a$): $0\sim 2^{64}-1$
absolute seqno($b$): $1\sim 2^{64}$
seqno无偏移情形($c$): $0\sim 2^{32} -1$
seqno有偏移情形，假设偏移为$e$，($d$): $0\sim 2^{32} -1$

对应关系：

$\begin{aligned} b &= a + 1 \\ c &\equiv b \bmod 2^{32}\\ d&\equiv e +c \bmod 2^{32} \\ & \equiv e +b \bmod 2^{32} \end{aligned}$

wrap

这里已知$ b, e$，计算$d$，利用公式即可：

$d\equiv e +b \bmod 2^{32}$

代码：

//! 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 m = (1ll << 32);
    uint32_t num = (n + isn.raw_value()) % m;

    return WrappingInt32{num};
}

unwrap

这里已知：

$\begin{aligned} d_1 &\equiv e +b_1 \bmod 2^{32} \\ d_2 &\equiv e +b_2 \bmod 2^{32} \\ \end{aligned}$

现在的问题是，给定$b_1, e, d_2$，求出$b_2$，其中$d_1, d_2$是相邻的序号。

分析：

利用同余的性质可得

$\begin{aligned} d_2 - d_1 \equiv b_2 - b_1 \bmod 2^{32} \end{aligned}$

那么

$\begin{aligned} d_2 -d_1&=b_2 - b_1 + 2^{32} k\\ b_2&= b_1 + 2^{32}k +(d_2 - d_1) \end{aligned}$

这里的目标是：找到$b_2$，使得$b_2$和$b_1$的距离最近接，这里是基于：

The checkpoint helps to resolve the ambiguity: it’s a recently unwrapped absolute seqno that the user of this class knows is close to the desired unwrapped absolute seqno for this seqno.

checkpoint有助于解决这种歧义性：它是一个最近解封装的absolute seqno，这个类的用户知道它接近于这个seqno的所需解封装的absolute seqno。

注意：

$|b_2 - b_1| = |2^{32} k + (d_2 - d_1)|$

因为

$1- 2^{32} \le d_2 - d_1 \le 2^{32} -1$

所以根据绝对值函数的性质可得只需要比较$k=-1, 0, 1$的结果即可。

代码：

uint64_t get_abs(uint64_t d1, uint64_t d2) {
  if (d1 > d2) {
    return d1 - d2;
  } else {
    return d2 - d1;
  }
}

//! 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) {
    WrappingInt32 checkpoint_ = wrap(checkpoint, isn);
    // d2 - d1
    int32_t delta = n - checkpoint_;
    // k = 0
    uint64_t r1 = checkpoint + delta;
    // k = 1
    uint64_t r2 = checkpoint + ((1ll << 32) + delta);
    // k = -1
    uint64_t r3 = checkpoint - ((1ll << 32) + delta);
    // 计算距离
    uint64_t d1 = get_abs(r1, checkpoint);
    uint64_t d2 = get_abs(r2, checkpoint);
    uint64_t d3 = get_abs(r3, checkpoint);
    // 分情况讨论
    if (d1 < d2) {
        if (d1 < d3) {
            return r1;
        } else {
            return r3;
        }
    } else {
        if (d2 < d3) {
            return r2;
        } else {
            return r3;
        }
    }
}

测试

make -j4 && ctest -R wrap

Test project /cs144/sponge/build
    Start 1: t_wrapping_ints_cmp
1/3 Test #1: t_wrapping_ints_cmp ..............   Passed    0.00 sec
    Start 2: t_wrapping_ints_unwrap
2/3 Test #2: t_wrapping_ints_unwrap ...........   Passed    0.00 sec
    Start 3: t_wrapping_ints_wrap
3/3 Test #3: t_wrapping_ints_wrap .............   Passed    0.00 sec

100% tests passed, 0 tests failed out of 3

Total Test time (real) =   0.01 sec

TCP receiver

分析和重点

SYN和FIN时absolute seqno需要加1，序列长度需要减1；
注意只要窗口和序列有交集时就可接收；
窗口，序列长度为0时需要记为1；
注意absolute seqno和stream index之间的转换；

代码：

bool TCPReceiver::segment_received(const TCPSegment &seg) {
    TCPHeader header = seg.header();
    // absolute seqno
    uint64_t index;
    // absolute seqno
    uint32_t abs_seq;
    // window size
    size_t win_size = window_size();
    // 窗口为0则转换为1
    win_size = win_size ? win_size : 1;
    // seq_len
    size_t seq_len = seg.length_in_sequence_space();
    // seq_no
    WrappingInt32 seq_no = header.seqno;
    // SYN
    if (header.syn) {
        // 如果碰到多次syn则返回false
        if (_is_set_syn) {
            return false;
        }
        // 设置syn, isn
        _is_set_syn = true;
        _is_set_isn = true;
        _isn = header.seqno;
        // SYN长度为1
        // 第一个位置为1, 因为不包括SYN
        _checkpoint = 1;
        // 更新abs_seq
        _abs_seq = 1;
        // syn时长度减1
        seq_len -= 1;
        // 初始化
        index = 1;
        // 特殊则返回true
        if (seq_len == 0) {
            return true;
        }
    } else if (!_is_set_syn) {
        // 没有syn
        return false;
    } else {
        // relative seqno -> absolute seqno
        index = unwrap(seq_no, _isn, _checkpoint);
        _checkpoint = index;
    }
    
    // FIN
    if (header.fin) {
        if (!_is_set_syn) {
            return false;
        }
        // 更新syn
        _is_set_syn = false;
        // fin时长度减1
        seq_len -= 1;
    }

    // seq_len为0时则转换为1
    seq_len = seq_len ? seq_len : 1;

    // 序列区间[index, index + seq_len)
    // 窗口区间[_abs_seq, _abs_seq + window_size)
    // 不重合时报错
    if (((_abs_seq >= index + seq_len) || (index >= _abs_seq + win_size))) {
        return false;
    }

    // absolute seqno -> stream index
    _reassembler.push_substring(seg.payload().copy(), index - 1, header.fin);
    // stream index -> absolute seqno
    abs_seq = _reassembler.get_index() + 1;
    // 更新对应关系
    _abs_seq = abs_seq;
    // 为FIN时更新absolute seqno
    if (header.fin) {
        _abs_seq += 1;
    }

    return true;
}

optional<WrappingInt32> TCPReceiver::ackno() const { 
    if (_is_set_isn) {
        return wrap(_abs_seq, _isn);
    } else {
        return {};
    }
}

size_t TCPReceiver::window_size() const { return _capacity - _reassembler.stream_out().buffer_size(); }

测试

make -j4 && make check_lab2

Test project /cs144/sponge/build
      Start  1: t_wrapping_ints_cmp
 1/25 Test  #1: t_wrapping_ints_cmp ..............   Passed    0.00 sec
      Start  2: t_wrapping_ints_unwrap
 2/25 Test  #2: t_wrapping_ints_unwrap ...........   Passed    0.00 sec
      Start  3: t_wrapping_ints_wrap
 3/25 Test  #3: t_wrapping_ints_wrap .............   Passed    0.00 sec
      Start  4: t_recv_connect
 4/25 Test  #4: t_recv_connect ...................   Passed    0.00 sec
      Start  5: t_recv_transmit
 5/25 Test  #5: t_recv_transmit ..................   Passed    0.04 sec
      Start  6: t_recv_window
 6/25 Test  #6: t_recv_window ....................   Passed    0.00 sec
      Start  7: t_recv_reorder
 7/25 Test  #7: t_recv_reorder ...................   Passed    0.00 sec
      Start  8: t_recv_close
 8/25 Test  #8: t_recv_close .....................   Passed    0.00 sec
      Start 15: t_strm_reassem_single
 9/25 Test #15: t_strm_reassem_single ............   Passed    0.00 sec
      Start 16: t_strm_reassem_seq
10/25 Test #16: t_strm_reassem_seq ...............   Passed    0.00 sec
      Start 17: t_strm_reassem_dup
11/25 Test #17: t_strm_reassem_dup ...............   Passed    0.00 sec
      Start 18: t_strm_reassem_holes
12/25 Test #18: t_strm_reassem_holes .............   Passed    0.00 sec
      Start 19: t_strm_reassem_many
13/25 Test #19: t_strm_reassem_many ..............   Passed    0.23 sec
      Start 20: t_strm_reassem_overlapping
14/25 Test #20: t_strm_reassem_overlapping .......   Passed    0.00 sec
      Start 21: t_strm_reassem_win
15/25 Test #21: t_strm_reassem_win ...............   Passed    0.29 sec
      Start 22: t_strm_reassem_cap
16/25 Test #22: t_strm_reassem_cap ...............   Passed    0.00 sec
      Start 23: t_byte_stream_construction
17/25 Test #23: t_byte_stream_construction .......   Passed    0.00 sec
      Start 24: t_byte_stream_one_write
18/25 Test #24: t_byte_stream_one_write ..........   Passed    0.00 sec
      Start 25: t_byte_stream_two_writes
19/25 Test #25: t_byte_stream_two_writes .........   Passed    0.00 sec
      Start 26: t_byte_stream_capacity
20/25 Test #26: t_byte_stream_capacity ...........   Passed    0.00 sec
      Start 27: t_byte_stream_many_writes
21/25 Test #27: t_byte_stream_many_writes ........   Passed    0.01 sec
      Start 28: t_webget
22/25 Test #28: t_webget .........................   Passed    0.66 sec
      Start 48: t_address_dt
23/25 Test #48: t_address_dt .....................   Passed    0.03 sec
      Start 49: t_parser_dt
24/25 Test #49: t_parser_dt ......................   Passed    0.00 sec
      Start 50: t_socket_dt
25/25 Test #50: t_socket_dt ......................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 25

Total Test time (real) =   1.32 sec
[100%] Built target check_lab2

一个坑

测试22（t_strm_reassem_cap）会再测试下stream_reassembler部分的功能，由于lab1中实现的有点问题，所以这里又花了很久，修改的是push_substring函数，这里的修改点是，push时可能超过缓存，所以计算最后一个被push的字符last_str时不能简单相加，代码如下：

//! \details This function accepts a substring (aka a segment) of bytes,
//! possibly out-of-order, from the logical stream, and assembles any newly
//! contiguous substrings and writes them into the output stream in order.
// push字符串, 要求为index <= _index < index + data.size(), 此处不考虑缓存的问题
bool StreamReassembler::push_substring(const std::string &data, const uint64_t index) {
    // 有重叠
    int l1 = last_str.size();
    int l2 = data.size();
    // 忽略空字符
    if (l2 == 0) {
        return false;
    }
    // 新数据和旧数据没有重合
    if (index > _index) {
        return false;
    }
    // 新数据包含在之前的数据中
    if (_index >= index + l2) {
        return false;
    }
    // 特殊情况, 第一次insert或者相邻
    if ((l1 == 0) || (_index == index)) {
        // 拼接
        std::string new_data = data;
        size_t l = _output.write(new_data);
        // 重要更新, 注意可能超过缓存!!!
        last_str += data.substr(0, l);
        _index += l;

        return true;
    }

    int l;
    // 一般情形, 此时一定有重叠
    // ____
    //   _____
    // 找到重叠位置
    std::string res_data;
    get_inter(l, l1, l2, last_str, data, res_data);
    // 重叠的后续部分
    std::string new_data = data.substr(l, l2 - l);
    // push
    size_t l3 = _output.write(new_data);
    // 重要更新, 注意可能超过缓存!!!
    last_str += new_data.substr(0, l3);
    _index += l3;

    return true;
}