skaiuijing

引言

前置篇讲完了，现在让我们进入到正式的动手操作篇。一篇理论，一篇代码实现。

本篇主要讲内存与buf。

buf

在数据进入到一台主机的时候，这台主机必须要分配内存来承载这些数据。

我们可以直接分配一个数组，或者使用malloc或者其他的动态内存管理函数来获得内存，然后可以把数据复制到这个数组或者动态内存中。

或者，我们可以事先预存一大批内存，网卡直接DMA写入这些内存，这样就不用复制了。

但是，我们会遇到一些问题：

  • 网络是分层的，上层怎么知道这些数据多长呢？
  • 不同数据需要的内存不一样，每次都要按需分配吗？
  • 不同数据对应的操作不一样，不同数据包需要被划分给不同模块处理

这些操作太繁杂了。

我们需要明白，程序 = 数据结构 + 算法。

数据结构，就是结构体、模块等等。

在计算机中，我们习惯叫这种模块或者此在叫对象，设计一个模块其实是一种哲学。

对于这种情况，当我们认识到主体本身是一个趋于变化、自在自为的存在时，我们需要一个能够收束其存在的此在。

对于程序来说，此在就是本身的数据结构结构，此在的意义是去存在，而存在则是交互的一种动态过程。

结构体与交互

我们需要定义一个结构体，把各种程序模块对内存的操作收束到这个结构体中，这个结构体我们称之为buf。

一部分程序想知道这些数据多大，我们就在buf结构体中加一个字段len。

一部分程序想把不同的内存挂到不同的位置，我们就在buf结构体中加一个链表。

一部分程序想对不同的buf进行排序，我们就在buf中添加序号，然后添加链表或者红黑树赋值排序。

一部分程序想区分不同的数据类型，我们就在buf中添加一个flag。

这些程序是客体，当然，这是相对于buf来说的，buf一直是一个主体。

buf这个主体是由客体定义的，但客体却承担了主体的主体。

因此，客体是主体的主体，主体是客体的客体。

什么意思呢？

程序是变化的，这是一种架构设计哲学，一个模块做得越多，意味着其他模块做得越少，当一个模块都把自己的行为交给另一个模块，这会是一种灾难。

这意味着这个模块什么事情都要由它指派的模块来做，这个模块本身反而受制于指派的模块。

因此，其实我是不建议把任何事情都交给一个主体来完成的，不管这个主体是AI也好，是其他人也好，当你给得越多，自身也越趋近于一种虚无的状态。

刚才一个朋友跟我说，最近用AI写的代码出问题了，领导和他调试了一整天，感觉AI用多了自己变得越来越傻了，脱了AI代码都不知道怎么写了，但一边说不能用AI，一边又不得不在工作上大量使用。

我想了想，这可能就是一种主奴辩证法的体现吧。

算了，不讲这些了。

内存

我们现在已经知道buf承担的责任了，那就是携带数据，并且适当为程序中的不同模块添加一些辅助功能。

那么，携带数据需要内存，内存从何而来？

有什么好策略？

4.4BSD-lite

让我们打开《TCP/IP详解》卷二，看看4.4BSD-lite，这个三十年前的操作系统是怎么做的。

LWIP

lwip是一个常用的轻量级TCP/IP网络协议栈。

内存管理算法

有读者可能觉得，直接使用库函数分配堆内存不就行了吗？

通用的库函数的时间复杂度是O(N)，效率低得要命，而且，非常容易产生碎片。

我们需要考虑使用内存池策略，而且，管理内存是一个非常烦的事情，所以，我们可能还需要记录每个内存的分配地址，当内存不够时，看看是哪些内存块没释放导致了内存泄漏。

我们还可以批量释放内存，用一个线程自动帮我们释放。

类SLOB内存管理算法

这种小内存管理算法用于在内存资源有限的嵌入式系统中高效地管理内存。这些算法的目标是减少内存碎片，提高内存利用率，并确保分配和释放内存的操作尽可能快速、稳定。

它采用不断分割的方法对内存进行动态分配，分为初始化，分割，释放三个步骤，为了简洁起见，笔者直接放图：

初始化与申请

1
2
3
4
graph LR
A(头部)-->B(初始大内存块)-->C(尾部)

 
1
2
graph LR
A(头部)-->B(内存块)-->C(内存块)-->D(内存块)-->E(内存块)-->T(尾部)

这是整体思想，通过对初始内存块的不断切割，最终形成了各个不同的内存块。

初始化

1
2
graph LR
A(头部)-->B(内存块)-->C(尾部)

在初始化后，空闲内存块已经形成了一条链表，这条链表被称为空闲内存块链表，内存块被使用就被踢出这条链表，被释放就加入这条链表，如果内存块大于要申请的大小，就把多余的部分切割，然后加入这条内存链表。

malloc会找到合适的内存块，并且返回它的地址。

申请malloc

1
2
3
4
graph LR
A(头部)--从头开始找_直到找到符合大小的内存块-->B(内存块)-->C(内存块)-->D(内存块)-->E(内存块)-->T(尾部)


1
2
3
graph LR
G(链表起始)--把初始化的内存链表模型作为空闲内存块建立的链表-->F(结束)
A(prev)--在这条链表上找到符合条件的内存块-->B(use)-->C(new)

这条链表上就是空闲内存块链表，内存块被使用就被踢出这条链表，被释放就加入这条链表，如果内存块大于要申请的大小，就把多余的部分切割，然后加入这条内存链表。

最终读者会看到，空闲内存块会越来越小，而且也越来越不连续。

虽然通过指针，通常情况下我们可以把不连续的空间当成连续的空间使用，这些不连续的空间被称为碎片。但是，

当不连续的空间越来越小时，我们很可能找不到一个足够大的空间碎片满足存储请求，尽管总的空闲空间可能仍然满足。

这样下去，系统绝对是会崩溃的。

为了避免碎片问题，也有一些方法被广泛采用。

分配时的策略

为了减少碎片，通常有两种策略：best-fit和first-fit。

best-fit算法：这个策略趋向于将大的碎片保留下来满足后续的请求。我们根据空闲空间块的大小，将它们分在若干个容器中，在容器中，存储块按照他们的大小进行排列，这使得寻找best-fit块变得更加容易。

first-fit算法 ：在这个策略中，对象被放置在地址最低的、能够容纳对象的碎片中。这种策略的优点是速度快，但是内存分配性能比较差。

free释放

释放内存块，就是将内存块加入空闲内存块表。同时会有一些方法减少碎片。

合并内存块

同时，如果我们检测到free释放的内存块的地址与其他空闲内存块是连续的，我们会合并它们：

释放

1
2
3
4
graph LR
A(空闲内存块)-->D(空闲内存块)-->B(空闲内存块);

C(Insert)-->D(空闲内存块);

直接插入即可，但是，插哪里呢？

答案是根据地址找，如果上一个空闲内存块的地址比这个内存块开头的地址要低，而下一个却要高一些，那就插入这中间。

1
2
3
graph LR
A(start)-->B-->C(Insert)-->D-->E-->G(end);

插入后，看看与后面的内存块是不是相邻，相邻就合并：

1
2
3
graph LR
A(start)--后相邻-->B-->C(Insert + D)-->E-->F(end);

内存块前相邻，合并后等价于：

1
2
3
4
graph LR

A(start)--前相邻-->B(B+Insert)-->D-->E-->F(end);

前后都相邻：

1
2
graph LR
A(start)--可以只考虑最终结果-->B--Insert + D-->E-->F(end);

合并后等价于：

1
2
3
4
graph LR

A(start)--可以只考虑最终结果-->B(B + Insert +D)-->E-->F(end);

共有三种情况：前相邻、后相邻、前后都相邻。

如果前后相邻是相互独立的，那么互不影响，如果不独立，通过后，前的顺序可以得到前后都相邻的结果，因此该顺序正确。

所以程序中，我们先进行后相邻合并判断，再进行前相邻合并判断。