这篇文章单独记录 CS144 TCP labs 的实现过程。

0. Checkpoint 0：ByteStream

Checkpoint 0 实现的是一个有限容量的 FIFO 字节流。

1
Writer -> buffer -> Reader

核心状态：

1
2
3
4
5
capacity_  : buffer 最大容量
buffer_    : 当前还没被读取的数据
pushed_    : 历史累计写入字节数
popped_    : 历史累计读取字节数
closed_    : writer 是否关闭

0.1 push

写入时不能超过剩余容量。

1
2
3
4
5
6
7
8
9
10
void Writer::push( string data )
{
  if ( closed_ ) {
    return;
  }

  uint64_t writable = min( static_cast<uint64_t>( data.size() ), available_capacity() );
  buffer_.append( data.substr( 0, writable ) );
  pushed_ += writable;
}

0.2 pop

读取时不能超过当前 buffer 中已有的数据。

1
2
3
4
5
6
void Reader::pop( uint64_t len )
{
  uint64_t popable = min( len, static_cast<uint64_t>( buffer_.size() ) );
  buffer_.erase( 0, popable );
  popped_ += popable;
}

0.3 close 与 is_finished

close() 只表示 writer 不再写入；只有 buffer 也被读空，整个 stream 才算 finished。

1
2
3
4
bool Reader::is_finished() const
{
  return closed_ && buffer_.empty();
}

这和 TCP 的 FIN 很像：收到 FIN 后，之前已经收到的数据仍然要继续交给应用层读取。

1. Checkpoint 1：Reassembler

Checkpoint 1 实现的是 Reassembler，用于把乱序、重复、重叠的 substring 重新拼成连续 ByteStream。

接口：

1
void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring )

核心状态：

1
2
3
next_index : 下一个可以写入 ByteStream 的 index
pending_   : 已经收到但暂时不能输出的乱序片段
eof_index_ : 字节流结束位置

1.1 已输出数据裁剪

如果收到的数据前缀已经输出过，需要裁掉旧前缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
const uint64_t current_index = output_.writer().bytes_pushed();
const uint64_t end_index = first_index + data.size();

if ( end_index <= current_index ) {
  try_close();
  return;
}

if ( first_index < current_index ) {
  const uint64_t trim_len = current_index - first_index;
  data = data.substr( trim_len );
  first_index = current_index;
}

1.2 正好接上 next_index

如果新片段正好接上当前 ByteStream 的末尾，就直接写入，并尝试 flush pending。

1
2
3
4
5
6
if ( first_index == next_index() ) {
  output_.writer().push( data );
  flush_pending();
  try_close();
  return;
}

2.3 重叠区间合并

重叠数据不能重复保存，需要合并成更大的区间。

1
2
3
4
new: [3,8)  = lowor
old: [5,10) = world
----------------
[3,10) = loworld

核心代码：

1
2
3
4
5
6
const uint64_t merged_start = min( new_start, old_start );
const uint64_t merged_end = max( new_end, old_end );
string merged( merged_end - merged_start, '\0' );

merged.replace( new_start - merged_start, new_data.size(), new_data );
merged.replace( old_start - merged_start, old_data.size(), old_data );

这里的 offset 用来把 stream index 转换成 merged 字符串内部下标。

1.4 遍历时删除 map 元素

如果遍历过程中要删除 map 元素，应使用 iterator，而不是 range-for。

1
it = pending_.erase( it );

erase(it) 会删除当前元素，并返回下一个有效 iterator。

2. Checkpoint 2：TCPReceiver

Checkpoint 2 把 TCP segment 接到 Reassembler 上。

1
2
3
4
5
6
7
8
9
TCPSenderMessage
  ├── seqno
  ├── SYN
  ├── payload
  └── FIN
        ↓
TCPReceiver::receive()
        ↓
Reassembler::insert(first_index, data, is_last_substring)

2.1 Wrap32 & Unwrap

  1. Wrap()
    Wrap将64位的绝对序列号转换成32位的TCP序列号。
1
return zero_point + static_cast<uint32_t>(n);

保留n的低32位，同时加上此时的ISN。
例如：

1
2
ISN = 1000
absolute seqno = 5    =>TCP seqnp = 1005

如果此时absolute seqno = 2^32 + 5 ， TCP seqno仍然是1005.

  1. Unwrap()
  • 计算offset：offset在做什么？
    当前TCP序列号相对ISN向前移动了多少。是当前TCP seqno相对于ISN 32位的环形距离，也是绝对序列号的低32位
1
2
3
const uint32_t offset = raw_value_ - zero_point.raw_value_;
//raw_value_ 当前收到的32位TCP seqno
//zero_point.raw_value_ 连接开始时候的ISN

因此只知道offset，无法知道它属于哪一轮。

  • checkpoint的作用
    如果 checkpoint <= offset，offset 是距离 checkpoint 最近的非负候选值，可以直接返回。这里不能据此断言实际是否发生过回绕；checkpoint 只是帮助选择候选值的参考位置。

否则需要根据 checkpoint 估算目标绝对序号位于第几个回绕周期。所有候选值都满足 offset + k × 2^32，相邻候选值之间相差 2^32。k 先找到 checkpoint 左边的候选值；余数再判断左边和右边哪一个离 checkpoint 更近。

1
2
3
4
5
6
L = offset + k × 2^32                         R = offset + (k + 1) × 2^32
●──────────────────────────│────────▲──────────────────●
                           │        checkpoint
                       中点 L + 2^31
|<─────────── remainder ───────────>|
                                    |<─2^32-remainder──>|

图中 remainder 是 checkpoint 到左侧候选值 L 的距离。当它达到半个周期 2^31 时，右侧候选值 R 不再比 L 更远，因此代码选择下一轮。

1
2
3
4
5
6
7
8
9
10
11
12
//offset只是绝对序列号的低32位
uint64_t diff = checkpoint - offset; //diff表示checkpoint与最小候选值offset的距离
uint64_t k = diff >> 32;  //diff / 2^32 :checkpoint左侧候选值所在的回绕周期

//如果 checkpoint 已经越过左右两个候选值的中点，就选择下一轮的候选值。 1ULL << 31 => 2^31
//超过左右中点则进入下一轮，未超过则在当前轮次
if((diff & 0xFFFFFFFF) >= 1ULL << 31){ 
  k += 1;
  return offset + (k << 32);
}else{
  return offset + (k << 32);
}

2.2 TCPReceiver::receive

2.3 TCPReceiver::send

3. Checkpoint 3：TCPSender

4. Network Interface（Checkpoint 5）

保留 Ethernet frame、ARP、IP 与网卡接口，这是嵌入式网络开发的核心内容。

5. IP 路由基础（Checkpoint 6 选学）

只学习路由表、默认网关、TTL 与最长前缀匹配，不要求完整实现路由器项目。

6. End-to-End TCP/IP Integration（Checkpoint 7 精选）

只完成单机端到端联调和数据传输，跳过多人组网与创意项目。