详解 KCP 协议的原理和实现 - Luyu Huang's Tech Blog

[luyuhuang]

https://luyuhuang.tech/2020/12/09/kcp.html

1. 引言KCP 是一个快速可靠的 ARQ (Automatic Repeat-reQuest, 自动重传请求) 协议, 采用了不同于 TCP 的自动重传策略, 有着比 TCP 更低的网络延迟. 实际通常使用 KCP over UDP 代替 TCP, 应用在网络游戏和音视频传输中. KCP 的实现短小精悍, 非常...

[forevering]

分析透彻详细，好文！

[luyuhuang]

@forevering 分析透彻详细，好文！

谢谢! 很高兴能对你有所帮助.

[magicsn0w]

深度好文,对了解kcp有很大帮助,感谢!

[luyuhuang]

@magicsn0w 深度好文,对了解kcp有很大帮助,感谢!

很高兴能帮到你!

[iamazy]

感谢博主写的这篇文档，想要转载可以吗

[luyuhuang]

@iamazy 感谢博主写的这篇文档，想要转载可以吗

可以哦, 附上原文链接即可

[Navimark]

1. 首先, 每个数据报文和 ACK 都会带上 sn, 唯一标识一个报文; 发送方发送一个数据报文, 接收方收到后回一个 ACK, 接收方（应该是发送方?）收到 ACK 后根据 sn 将对应的报文标记为已送达; 同时, 每个报文都会带上 una, 发送方也会根据 una 将相应的报文标记已送达
2. 对于&((TYPE *)0)->MEMBER，我自己浅薄的理解：这个表达式的目的是“比划”出一个合适大小的偏移。对于IQUEUE_ENTRY(p, IKCPSEG, node)来说，展开就是 ( IKCPSEG *)( ((char*)((type*)p)) - ((size_t) &(( IKCPSEG *)0)->node))，跳过 node 的 offset，整个表达式的返回值被当做 IKCPSEG * 类型的指针，指向 IKCPSEG 真正 payload 开始的部分(开始于conv)。这种对结构体的巧妙利用，和下面这段来自《征服C语言》的变体代码有异曲同工之妙，忍不住拿出来分享一番：

   void testStruct(void)
   {
       struct Point {
           float x;
           float y;
       };
   
       struct Points {
           int count;
           struct Point *point;
       };
   
   
       int pcnt = 5;
       struct Points *point_5 = malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1));
       point_5->count = pcnt;
   
       point_5->point = (struct Point *)(((char *)point_5) - offsetof(struct Points, point));
   
       for (NSInteger i= 0; i != pcnt; ++i) {
           struct Point *tmpP = point_5->point -  i;
           tmpP->x = 1 * i + 2;
           tmpP->y = 3 * i + 3;
           printf("写入---%ld:(%lf, %lf)\n", i, tmpP->x, tmpP->y);
       }
   
   
       for (NSInteger i= 0; i != pcnt; ++i) {
           struct Point *tmpP = point_5->point -  i;
           printf("读取---%ld:(%lf, %lf)\n", i, tmpP->x, tmpP->y);
       }
   
       free(point_5);
   }
   
   

[luyuhuang]

@Navimark 发送方发送一个数据报文, 接收方收到后回一个 ACK, 接收方（应该是发送方?）

这里写错了, 感谢指正

这种对结构体的巧妙利用

嘛, 我倒是觉得这样写挺丑的... 不过 C 语言毕竟不是那么高级的语言. 高级的语言往往会提供一些语法, 然后编译器生成这种计算 offset 的代码 (没错说的就是 C++, 虽然 C++ 也很丑, 哈哈哈.

[luyuhuang]

@Navimark

    int pcnt = 5;
    struct Points *point_5 = malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1));
    point_5->count = pcnt;

    point_5->point = (struct Point *)(((char *)point_5) - offsetof(struct Points, point));

    for (NSInteger i= 0; i != pcnt; ++i) {
        struct Point *tmpP = point_5->point -  i;
    }

仔细看了下, 感觉这里有些奇怪呀, 首先 malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1)) 为什么是 pcnt - 1, 那还有一个 point 存哪呢. 然后就是 (struct Point *)(((char *)point_5) - offsetof(struct Points, point)) 为什么是拿结构体的起始地址减去 point 字段的 offset, 这样得到的地址不是指向分配的内存的外面了吗. 最后 point_5->point - i 为什么是减 i, 这是不是越减越远了.

[Navimark]

@luyuhuang

@Navimark 发送方发送一个数据报文, 接收方收到后回一个 ACK, 接收方（应该是发送方?）

这里写错了, 感谢指正

这种对结构体的巧妙利用

嘛, 我倒是觉得这样写挺丑的... 不过 C 语言毕竟不是那么高级的语言. 高级的语言往往会提供一些语法, 然后编译器生成这种计算 offset 的代码 (没错说的就是 C++, 虽然 C++ 也很丑, 哈哈哈.

我写完评论后，同事就来“嘲讽”我说，这种用 Macro Define 实现抽象循环双链表的形式，在 Linux 内核代码中太常见了，好吧，确实是我浅薄了🙄

[Navimark]

@luyuhuang

@Navimark

    int pcnt = 5;
    struct Points *point_5 = malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1));
    point_5->count = pcnt;

    point_5->point = (struct Point *)(((char *)point_5) - offsetof(struct Points, point));

    for (NSInteger i= 0; i != pcnt; ++i) {
        struct Point *tmpP = point_5->point -  i;
    }

仔细看了下, 感觉这里有些奇怪呀, 首先 malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1)) 为什么是 pcnt - 1, 那还有一个 point 存哪呢. 然后就是 (struct Point *)(((char *)point_5) - offsetof(struct Points, point)) 为什么是拿结构体的起始地址减去 point 字段的 offset, 这样得到的地址不是指向分配的内存的外面了吗. 最后 point_5->point - i 为什么是减 i, 这是不是越减越远了.

malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1)) 为什么是 pcnt - 1, 那还有一个 point 存哪呢.

第一个 Point 被放置在 sizeof(struct Points) 对应的内存空间中，剩下的 4 个只需要 sizeof(struct Point) * (pcnt - 1)大小的空间。当然这里利用了一个巧合：sizeof(struct Point *) 和 sizeof(struct Point) 大小相等

[Navimark]

@luyuhuang

@Navimark

    int pcnt = 5;
    struct Points *point_5 = malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1));
    point_5->count = pcnt;

    point_5->point = (struct Point *)(((char *)point_5) - offsetof(struct Points, point));

    for (NSInteger i= 0; i != pcnt; ++i) {
        struct Point *tmpP = point_5->point -  i;
    }

仔细看了下, 感觉这里有些奇怪呀, 首先 malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1)) 为什么是 pcnt - 1, 那还有一个 point 存哪呢. 然后就是 (struct Point *)(((char *)point_5) - offsetof(struct Points, point)) 为什么是拿结构体的起始地址减去 point 字段的 offset, 这样得到的地址不是指向分配的内存的外面了吗. 最后 point_5->point - i 为什么是减 i, 这是不是越减越远了.

为什么是拿结构体的起始地址减去 point 字段的 offset, 这样得到的地址不是指向分配的内存的外面了吗

目的是为了得到Points 的 point成员偏移的地址，访问该地址再后面的空间，理论上是不合法的，但这里是通过point_5 指针偏移访问的，而point_5 是动态分配的连续空间，所以作上述偏移后，实际上还落在刚刚申请的堆空间内。

[Navimark]

@luyuhuang

@Navimark

    int pcnt = 5;
    struct Points *point_5 = malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1));
    point_5->count = pcnt;

    point_5->point = (struct Point *)(((char *)point_5) - offsetof(struct Points, point));

    for (NSInteger i= 0; i != pcnt; ++i) {
        struct Point *tmpP = point_5->point -  i;
    }

仔细看了下, 感觉这里有些奇怪呀, 首先 malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1)) 为什么是 pcnt - 1, 那还有一个 point 存哪呢. 然后就是 (struct Point *)(((char *)point_5) - offsetof(struct Points, point)) 为什么是拿结构体的起始地址减去 point 字段的 offset, 这样得到的地址不是指向分配的内存的外面了吗. 最后 point_5->point - i 为什么是减 i, 这是不是越减越远了.

point_5->point - i

这个还是对指针（point_5->point）作 i 单位的偏移，此处的一个单位的大小即是point_5->point这个指针指向数据的大小，即sizeof(struct Point)，目的是指向下一个 struct Point 的空间。

[Navimark]

@luyuhuang

@Navimark

    int pcnt = 5;
    struct Points *point_5 = malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1));
    point_5->count = pcnt;

    point_5->point = (struct Point *)(((char *)point_5) - offsetof(struct Points, point));

    for (NSInteger i= 0; i != pcnt; ++i) {
        struct Point *tmpP = point_5->point -  i;
    }

仔细看了下, 感觉这里有些奇怪呀, 首先 malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1)) 为什么是 pcnt - 1, 那还有一个 point 存哪呢. 然后就是 (struct Point *)(((char *)point_5) - offsetof(struct Points, point)) 为什么是拿结构体的起始地址减去 point 字段的 offset, 这样得到的地址不是指向分配的内存的外面了吗. 最后 point_5->point - i 为什么是减 i, 这是不是越减越远了.

这段代码没啥目的，仅仅是惊艳于 struct 还有这种用法😲 如有理解不到位的，请大佬指正

[luyuhuang]

@Navimark 还是没太明白, 如果要偏移那肯定是 + offsetof() 和 + i 呀, 怎么会是减. 而且这段代码我实际运行是会 coredump 的.

... 当然这里利用了一个巧合：sizeof(struct Point *) 和 sizeof(struct Point) 大小相等

这个太奇怪了, 如果是我的话变长结构体肯定是这样写

void main(void)
{
    struct Point {
        float x;
        float y;
    };
    
    struct Points {
        int count;
        struct Point point[1];
    };
    
    int pcnt = 5;
    struct Points *point_5 = malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1));
    point_5->count = pcnt;

    for (int i= 0; i != pcnt; ++i) {
        struct Point *tmpP = point_5->point + i;
        tmpP->x = 1 * i + 2;
        tmpP->y = 3 * i + 3;
    }
}

[Navimark]

@Navimark 还是没太明白, 如果要偏移那肯定是 + offsetof() 和 + i 呀, 怎么会是减. 而且这段代码我实际运行是会 coredump 的.

... 当然这里利用了一个巧合：sizeof(struct Point *) 和 sizeof(struct Point) 大小相等

这个太奇怪了, 如果是我的话变长结构体肯定是这样写

void main(void)
{
    struct Point {
        float x;
        float y;
    };
    
    struct Points {
        int count;
        struct Point point[1];
    };
    
    int pcnt = 5;
    struct Points *point_5 = malloc(sizeof(struct Points) + sizeof(struct Point) * (pcnt - 1));
    point_5->count = pcnt;

    for (int i= 0; i != pcnt; ++i) {
        struct Point *tmpP = point_5->point + i;
        tmpP->x = 1 * i + 2;
        tmpP->y = 3 * i + 3;
    }
}

👍🏻这样写确实好一些，struct Points 与 struct Point 的大小包含关系非常清晰，日后struct Point 扩展成(x,y,z)的话，malloc 部分的代码也不用做任何改动

[zhin2929]

una 4 字节: 发送方的接收缓冲区中最小还未收到的报文段的编号. 也就是说, 编号比它小的报文段都已全部接收.

这里的是我理解错了吗？不应该是发送方的发送缓冲区吗

[luyuhuang]

@zhin2929 una 4 字节: 发送方的接收缓冲区中最小还未收到的报文段的编号. 也就是说, 编号比它小的报文段都已全部接收.

这里的是我理解错了吗？不应该是发送方的发送缓冲区吗

如果 A 给 B 发送了一个报文，那么里面的 una 字段就表示 A 的接收缓冲区中最小还未收到的报文段的编号。这个字段就是用于告诉对方“我”收到了哪些报文。可以参考下 4.2.3 的例子。

[jinzhongjia]

好文，解析应该是目前最透彻的了

[luyuhuang]

@jinzhongjia 好文，解析应该是目前最透彻的了

谢谢！