Stanford CS144 Lab 5
Lab Checkpoint 5: down the stack (the network interface)
我们前面算是已经完成了 TCP 的实现，可以与任意系统交换 TCP 报文。从这个 checkpoint 起，我们将实现 network interface，其位于 TCP/IP 协议栈的相对底部，负责处理上层的 IP 包 (Internet datagram) 和下层的以太网帧 (Ethernet frames)。也就是说，我们最终的目的是实现 TCP-in-IP-in-Ethernet。
Checkpoint 4 是一些测量真实世界互联网的实验，无需在实验框架中填充代码，就不在此系列文章中赘述了。
2 Checkpoint 5: The Address Resolution Protocol #
这个 checkpoint 的主要任务是处理 ARP 协议。具体地，我们需要修改给出的 NetworkInterface 类，完成其中的 send_datagram recv_frame tick 三个方法。
send_datagram 是用来将 IP 包包装为以太网帧发送的，同时也要处理 ARP 报文广播的发送。该方法接受 IP 包和下一跳作为参数。一旦下一跳的 MAC 地址 (Ethernet address) 已知，则包装并发送该包；否则，广播一个 ARP request。为了避免造成 flood，发送 ARP request 的频率还受到一些限制。
recv_frame 接受以太网帧，并维护相应状态。传入的以太网帧可能有两种类型：IP 包和 ARP 报文。如果是 IP 包，解析其 payload 并压入 NetworkInterface 的内部队列；如果是 ARP 报文，更新 ARP 表，并查看有没有因为找不到 MAC 地址而没发出去的 IP 包，有则发之。
tick 是测试的时候用来计时的，主要是 ARP 广播超时需要利用其维护状态。
我个人感觉 send_datagram 和 recv_frame 两个方法在功能上会有些耦合，并且后者需要直接调用前者，不是很优雅，各种副作用比较影响思考。假如是一个真实的操作系统内核（我没写过或者读过，基于个人猜测），或许可以采用更加“事件驱动”的方式，把 ARP 表管理的部分拆出来，在每一个 tick 进行处理过期的 ARP entry，遍历 pending 状态的 IP 包等操作，缺点是根据 tick 粒度的不同，会有一定延迟。或许等我学习了 OS，会有更正确的理解吧。
实现上，状态管理还是全靠 std::map。给 NetworkInterface 添加了如下 private 成员：
1// A map of IP address -> {Ethernet address, timestamp} for ARP lookups
2std::map<uint32_t, std::pair<EthernetAddress, size_t>> arp_table_ {};
3
4// A map of IP address in ARP requests -> timestamp for ARP requests that already have been sent
5std::map<uint32_t, size_t> arp_requests_sent_ {};
6
7// A map of IP address -> queue of datagrams that are waiting for an ARP reply
8std::map<uint32_t, std::queue<InternetDatagram>> datagrams_pending_ {};
9
10size_t last_tick_ms_ = {};send_datagram 的实现：
1void NetworkInterface::send_datagram( const InternetDatagram& dgram, const Address& next_hop )
2{
3 uint32_t next_hop_ip = next_hop.ipv4_numeric();
4
5 auto arp_entry = arp_table_.find( next_hop_ip );
6 if ( arp_entry != arp_table_.end() ) {
7 EthernetFrame frame = {
8 .header = {
9 .dst = arp_entry->second.first,
10 .src = ethernet_address_,
11 .type = EthernetHeader::TYPE_IPv4,
12 },
13 .payload = serialize(dgram)
14 };
15 transmit( frame );
16 return;
17 }
18
19 datagrams_pending_[next_hop_ip].push( dgram );
20
21 // Ethernet address unknown, send ARP request
22 // Check timestamp first to avoid flooding
23 auto arp_request_it = arp_requests_sent_.find( next_hop_ip );
24 if ( arp_request_it != arp_requests_sent_.end() && last_tick_ms_ - arp_request_it->second < 5000 ) {
25 return;
26 }
27
28 ARPMessage arp_request = {
29 .opcode = ARPMessage::OPCODE_REQUEST,
30 .sender_ethernet_address = ethernet_address_,
31 .sender_ip_address = ip_address_.ipv4_numeric(),
32 .target_ip_address = next_hop_ip,
33 };
34 EthernetFrame arp_frame = {
35 .header = {
36 .dst = ETHERNET_BROADCAST,
37 .src = ethernet_address_,
38 .type = EthernetHeader::TYPE_ARP,
39 },
40 .payload = serialize(arp_request)
41 };
42 transmit( arp_frame );
43 arp_requests_sent_[next_hop_ip] = last_tick_ms_;
44}recv_frame 的实现。调用了 send_frame 实现 IP 包的重传：
1void NetworkInterface::recv_frame( EthernetFrame frame )
2{
3 if ( frame.header.dst != ethernet_address_ && frame.header.dst != ETHERNET_BROADCAST ) {
4 return;
5 }
6
7 if ( frame.header.type == EthernetHeader::TYPE_IPv4 ) {
8 IPv4Datagram dgram;
9 if ( parse( dgram, move( frame.payload ) ) ) {
10 datagrams_received_.push( move( dgram ) );
11 }
12 }
13
14 if ( frame.header.type == EthernetHeader::TYPE_ARP ) {
15 ARPMessage msg;
16 if ( parse( msg, move( frame.payload ) ) ) {
17 arp_table_[msg.sender_ip_address] = { msg.sender_ethernet_address, last_tick_ms_ };
18 if ( msg.opcode == ARPMessage::OPCODE_REQUEST && msg.target_ip_address == ip_address_.ipv4_numeric() ) {
19 ARPMessage arp_reply = {
20 .opcode = ARPMessage::OPCODE_REPLY,
21 .sender_ethernet_address = ethernet_address_,
22 .sender_ip_address = ip_address_.ipv4_numeric(),
23 .target_ethernet_address = msg.sender_ethernet_address,
24 .target_ip_address = msg.sender_ip_address,
25 };
26 EthernetFrame arp_frame = {
27 .header = {
28 .dst = msg.sender_ethernet_address,
29 .src = ethernet_address_,
30 .type = EthernetHeader::TYPE_ARP,
31 },
32 .payload = serialize(arp_reply)
33 };
34 transmit( arp_frame );
35 }
36
37 auto it = datagrams_pending_.find( msg.sender_ip_address );
38 if ( it != datagrams_pending_.end() ) {
39 while ( !it->second.empty() ) {
40 InternetDatagram dgram = move( it->second.front() );
41 it->second.pop();
42
43 send_datagram( dgram, Address::from_ipv4_numeric( msg.sender_ip_address ) );
44 }
45 datagrams_pending_.erase( it );
46 }
47 }
48 }
49}tick 主要处理 ARP 表和未获响应的 ARP requests 的过期：
1void NetworkInterface::tick( const size_t ms_since_last_tick )
2{
3 last_tick_ms_ += ms_since_last_tick;
4
5 for ( auto it = arp_table_.begin(); it != arp_table_.end(); ) {
6 if ( last_tick_ms_ - it->second.second > 30000 ) { // 30 seconds
7 it = arp_table_.erase( it );
8 } else {
9 ++it;
10 }
11 }
12
13 for ( auto it = arp_requests_sent_.begin(); it != arp_requests_sent_.end(); ) {
14 if ( last_tick_ms_ - it->second > 5000 ) { // 5 seconds
15 datagrams_pending_.erase( it->first );
16 it = arp_requests_sent_.erase( it );
17 } else {
18 ++it;
19 }
20 }
21}这里还有一个小插曲，测试的第一阶段 compile with bug-checkers 在我的机器上需要 18 秒才能跑完，但限时了 15 秒。可以通过修改 etc/tests.cmake 调大时限。