毕设回顾——轻量可靠传输协议的设计与实现

许久未写博客，一方面是因为三四月份都在忙于毕设，每天都在查资料和debug，几乎挤不出时间来写blog，另一方面主要还是因为犯懒了。这次就一次性写一篇技术+心得向的文章，来总结一下这两个月毕设的工作。

仓库地址：https://github.com/zhf999/ReliableUDP

选题与准备

因为研究生导师让我跟着本校导师做毕设，所以我也就只能自己选题。最开始选了很多和密码学、信息安全有关的题目，但是最后是《轻量可靠传输协议的设计与实现》这个题目中签了，其实在很久以前学socket编程的时候就对网络协议比较感兴趣，今天也终于有机会深入研究一下了。

前期资料的准备方面，我最开始进行了一系列网络协议相关书籍的阅读，包括《TCP/IP协议详解卷一：协议》以及《计算机网络：自顶向下方法》，这些书籍都是业界非常优秀的数据，但是讲的主要是协议在逻辑上的设计，并没有设计具体的代码实现。深入了解了TCP协议的设计原理后，我就在应用层利用socket开始实现代码了。

实现方法

用户态RUDP

最开始，我非常想当然地使用C语言的socket来进行开发，具体地说是在Linux平台上，通过socket发送UDP数据包，UDP数据中带着RUDP的数据包。这样，双方实质上还是通过UDP包进行通信，只不过在接收UDP包后，还需要根据其中的RUDP头部相关的控制字段来提供更多的服务。

使用这样的用户态实现RUDP有一个很关键的问题需要解决，就是RUDP若想要实现可靠传输，就必须加入重传机制，而重传等机制的实现又离不开定时器。如果RUDP程序和应用程序是运行在同一个线程中的话，那就无法使用定时器，除非应用程序主动地每隔一段时间检查是否超时，而“主动检查”在某些场景下是很难实现的，比如等待用户输入数据，只要用户不输入数据，程序接下来代码就无法运行。

所以，用户态的RUDP，我采用了多线程的设计。在操作系统层面，RUDP是以库形式被封装的，当应用程序调用RUDP的相关函数时，会新建线程，新的RUDP线程会在后端检查定时器是否超时，从而进行重传等一系列操作。

顺着这样的思路，我一直把连接建立的过程写完了。本以为按照这样的进度下去，不出一个月就能把协议代码写完，但是由于在中期答辩之前一直没有和导师沟通过实现的细节，所以实际上我的工作方向一直是错误的。导师希望我在Linux的内核态下进行编程，从而在内核中实现一个通用的内核协议。这导致我在前8周的工作几乎全部作废（起码在代码上是这样的），虽然很不爽，但是我并没有对师兄或者导师有不好的情绪，毕竟没有及时沟通是我的问题，只能认倒霉，重新在内核实现一遍吧，就当锻炼了。

内核态RUDP

在内核中实现RUDP，难度和在用户态下实现不是一个量级了。在编写代码之前要做的一件事就是深入阅读Linux内核源码，参考一下Linux内核协议栈的实现原理。不得不说，Linux内核的源代码简直就是一坨屎山，首先是里面用到了一堆goto语句，然后是一系列不明意义的函数调用，很多被弃用的函数也没有及时标注，读起来那叫一个折磨。

阅读Linux源码利用到的主要工具也可以稍微总结一下，首先是在线的网站：https://elixir.bootlin.com/linux/latest/source，这个网站可以跳转到变量的定义、声明还有引用处，还是挺方便的，唯一缺点就是访问速度比较慢；然后是source insight和source tail这两个线下工具，我更偏向于后者，因为后者的UI更友好，使用也没什么门槛，但是业内对前者评价更高；最后是几本书，《Linux内核源码剖析——TCP/IP实现》，《Linux内核设计与实现》，《Linux网络内核分析与开发》虽然这些书使用的Linux版本都比较老旧，但是其中对Linux内核设计思路的解读还是非常有借鉴意义的。

向Linux内核添加协议需要使用内核模块，内核模块可以被快速地安装和卸载，避免了直接对内核源码进行修改，可以节约大量的时间和精力。

Linux内核的实现

先研究一下Linux内核中网络协议是怎么实现的，

就以sendto这个系统调用为例，当应用层调用sendto这个C语言库函数时，Linux内核会通过系统调用sys_sendto，在这个函数中，会t通过套接口层操作集结构体inet_dgram_ops调用sendmsg，这个函数指针指向inet_sendmsg函数，套接口层的相关处理完毕后，紧接着会引用到传输层操作集结构体udp_prot中的sendmsg指针，这个函数指针指向udp_sendmsg函数，在这个函数中会完成和传输层有关的操作，完毕后进入网络层。

套接口层主要是进行协议族的区分，在本例中调用的是INET协议族，其他协议族包括Unix域协议族等，和协议族有关的操作主要包括地址等；传输层则是进行传输层协议的区分，例如区分UDP和TCP协议。本课题的实现原理就是通过修改并向内核注册我们自己的rudp_prot结构体，这是一个操作集，从而定义RUDP协议各个系统调用的行为。

RUDP的算法与数据结构

RUDP的算法大部分是凭空想出来的，但是也有一部分是借鉴自Linux内核TCP的实现原理。

头部

头格式其实没有什么好解说的，所见即所得，除了需要解释一下报文类型外其他都是望文生义就可以知道其意义。报文类似实际上也只有两种，一种是携带数据的包DATA，另一种是接收方发送的确认包ACK。

实际上最开始还有SYN、SYNACK等类型，它们和TCP中的报文类型类似都是用来建立连接的，但是导师建议RUDP没有必要加入三次握手的连接机制，遂被弃用。

双队列

为了实现可靠传输，发送方在发送报文后，不应该将报文直接释放，而应该将其储存起来等待重传，待接收方接收并确认后再释放。

TCP中使用了“滑动窗口”这个概念来实现可靠传输（其实更多是为了流量控制），但是由于TCP进行流量控制的单位是字节，所以窗口大小的单位也为字节，这给实现带来了较大的困难。为了实现上的方便，RUDP使用两个队列来对滑动窗口进行模拟，与TCP不同的是，RUDP的窗口大小的单位为数据包。

RUDP的两个队列分别为待发送队列和已发送队列，应用程序传递的数据会被打包加入待发送队列中，待时机合适时发送，并转移到已发送队列中去；已发送队列中的数据包会被保留，直至接收方发来了对应的确认包，当数据包超过一段时间没有被对方确认时，RUDP就会重传队列中的所有数据包。双队列机制也可以用来实现流量控制，实际上待发送队列是用来上图模拟滑动窗口的粉红色部分，已发送队列则是模拟蓝色部分。所以想控制一次性发送的数据包数量，只要控制已发送的队列的大小即可。当已发送队列的长度到达一个最大值，就不将更多的数据包加入其中，就实现了粗略的流量控制（单位为数据包而非字节）。

窗口的变化

窗口大小需要随着网络情况的波动而变化，以防止在网络拥塞时继续向其中传输过多的数据包。其具体规则如下：

• 初始值、最大值和阈值：初始值及最小值均为 1，最大值为 64，阈值为 32。在窗口大小大于或小于阈值时，变化的数额也会有所不同。

• 完成一个数据包的传输：当窗口大小小于阈值时，窗口大小翻倍；当窗口大小大于阈值时，窗口大小增加 2。窗口大小始终不会超过最大值 64。

• 当发生丢包时：发生丢包时，即发送方的重传定时器每到达一次激活时间，窗口大小就会减小为原来的 4/5。窗口的大小始终不会小于最小值 1。

需要注意的时，RUDP窗口大小初始值必须为1，否则若传输的第一个数据包发生了丢包，则接收方会直接将第二个数据包（接收方并没有察觉丢包，所以会将第二个数据包当做第一个）的序号作为初始序号。这样以来第一个数据包就在双方毫无察觉的情况下发生了丢包。

定时器

设想的定时器主要有三个，但由于种种原因，重置定时器并没有实现。

重传定时器

重传定时器主要用于未确认数据包的重传，当其到期时，会将滑动窗口中的所有未被确认数据包重新发送。需要注意的是，重新发送并不会修改数据包的序号。在重传定时器的处理函数执行完毕后，若窗口中还有未被确认的数据包，则重传定时器会再次被激活，从而继续发送未被确认的数据包。
重传定时器触发时，所有未被确认的数据包都会被重传，这意味着所有待重传的数据包共享一个重传定时器。如此设计是为了使用尽可能少的定时器来完成重传任务，若为每一个数据包设立一个重传定时器，则会消耗较多系统资源，且管理上较为复杂。

延迟确认定时器

在停止-等待协议中，每一个数据包发送后都需要等待对方的确认后才能继续发送，因此不容易引发网络的拥堵。而在 RUDP 协议所实现的回退 N 帧协议中，由于接收方一次性可能接收大量数据包，因此接收方也需要一次性回复多个 ACK类型的包，这种情况下容易造成网络的拥堵。故加入延迟确认定时器来避免一次性大量的 ACK 回复。

在 RUDP 协议中，数据包确认方式为捎带确认，即确认号为 x 的确认包可以将序号小于或等于 x 的数据包全部确认。这就意味着 RUDP 可以使用一个确认包来完成先前所有数据包的确认。为此， RUDP 中加入了延迟确认定时器。当数据包到来时，若定时器未被启动，则启动定时器；若定时器已经被启动，则将定时器的触发时间推迟一半。这样，当定时器被触发时，接收方就会发送最大的确认序号，这样以来，以往的数据包就全部被捎带确认了。

使用延迟确认的方式可以减少网络中泛滥的 ACK 包数量，但代价是略微增大了 ACK 包发送的延迟。

重置定时器

RUDP 目前仅支持点对点的数据传输，当接收方接收到发送方发送的第一个数据包后，双方的数据传输对象就绑定了。为了使得双方在完成数据传输后还能继续与网络中的其他主机通信， RUDP 引入了重置定时器。在双方互相没有数据包通信一段时间后，双方就会将传输控制块的状态恢复到原始状态，以接受其他主机的数据包。

与 TCP 的连接保活机制不同， RUDP 并不会主动发送心跳包来维持连接。如果应用层是间断性的数据传输，则双方可能因为重置定时器的存在而将窗口大小归为 1，或导致其中一方的因与其他主机通信而无法接收数据。若希望能够在一定时间内维持双方的 RUDP 状态，则应由应用层定时发送数据包。

定时器的超时时间

定时器的超时时间是一个固定值，由于开发周期有限，并没有办法对其进行精确的估算，而是直接使用一个经验值。

总结与回顾

原本以为技术向的总结需要写很多，但是发现大部分内容都可以从论文中直接搬出来，而关于Linux内核的实现部分似乎又没有必要再拾人牙慧地复述一遍，已经有很多的优秀书籍可以参考了。其实写到这我发现，在参与一个项目时学到的技术或者知识也许不是最重要的，大部分都是套用现成的数据结构或算法来完成，更重要的是这个项目中积累的经验和教训。所以，接下来就从稍微宏观的一点的角度来讲一下完成这个毕设时遇到的困难，解决办法以及吸取的经验。

结构体越界

不知道“结构体越界”这个名词到底存不存在，反正是我自己造的。初学C语言时，经常遇到对数组访问越界的情况。类似地，结构体越界就是在进行结构体指针强制转换时，访问到原来结构体外的内存了。实际上在用户态，对数组访问发生越界不会引发致命的错误，因为内核会监督地址的访问，顶多报一个段错误。然而在内核态，地址的错误访问内核是察觉不到的，并且会导致内核的崩溃。

在编写代码时，遇到这样一个bug，表现为：在结束运行测试程序的一段时间内，内核会随机地卡死，没有任何的错误报告和提示。最初以为是定时器使用的问题，因为在删除定时器后程序就能正常运行，但是最后发现不是定时器引发错误，而是结构体越界引起的。Linux传输层使用的控制块是struct sock结构体，该结构体为其他所有协议结构体的“基类”，这是通过指针强制转化实现的。只要在定义新的结构体时，将 struct sock结构体作为第一个成员，就可以在两种指针之间互相强制转化，前提是该指针确指向扩展后的结构体。

举例说明：

struct my_sock
{
    struct sock sk;
    int a,b,c;
};

void func(struct sock *sk)
{
    struct my_sock *p = (struct my_sock*)sk;
    p->a = 1;
    p->b = 2;
    p->c = 3;
}

int main()
{
    struct sock x;
    struct my_sock y;
   	func(&x); // not available
    func((struct sock*)&y); // available
}

在主函数中有两个函数调用，前一个函数调用是不可行的，因为sock结构体经过指针转换后，实际上的内存大小并没有变，所以访问 a b c三个变量时都是越界行为。而第二个函数调用是可行的，因为实际上的内存大小即为struct my_sock的内存大小。

在RUDP内核模块中，错误不是这么显而易见的，因为函数所带的指针参数是由多层函数调用传递下来的，很难得知其原型是什么。但是经过高人指点后还是发现了问题所在：

struct proto rudp_prot
{
    // ...
    int obj_size = sizeof(struct my_sock);
    // ...
}

这个obj_size成员就定义了结构体的大小，内核会根据这个值来为struct sock*这个指针申请空间。在一次重构代码时，我将其遗漏了，导致结构体大小始终为udp_sock结构体的大小，最终导致每一次内存访问都是越界的。

函数导出

Linux内核中引入了“符号导出”这个概念，即内核源码中的符号只有被导出后才可以在内核模块中使用，否则是用不了的。这让人十分头大，网络协议栈中有很多关键函数都没有被导出，向使用它们就得自己实现，而实现的过程中又会遇到新的未导出函数，继续实现下去无疑是把内核完全再实现一遍。

于是为了快捷地在内核模块中使用这些函数，就必须修改内核源码，将其导出。这个做法不算复杂，只需要在内核函数的定义后面加一行代码即可，但是每次修改源码都要进行1-2小时的编译。好在需要修改源码的机会并不多，并且可以一次性修改完再编译，节约一些时间。

另一个坑点就是在给师兄复现的时候，我把内核源码通过GitHub传给他，师兄编译安装后总会出现问题，而我本地复现是没有问题的。最后又尝试将源码打成压缩包通过微信发给他，这才解决问题。为什么通过GitHub传递源码会引起源码不一致，这个至今没有找出原因。