• 后端
• 网络
• 通信

导读

lws_dsh（Disordered Shared Heap，无序共享堆）是 libwebsockets 内部一个轻量的内存管理抽象：它在单个线性缓冲区内按“种类（kind）”维护多个 FIFO，允许不同种类的报文乱序退役（retired out of order），同时通过lws_dll2双向链表把碎片化管理成可合并的 free list。本文以仓库自带的 API 自测程序 api-test-lws_dsh 为入口，逐项讲解它的构建方式、命令行用法、全部测试用例的意图，并结合 lws-dsh.h 与 lws-dsh.c 的源码级实现，说明其在 Secure Streams 序列化代理、传输排序器等真实模块中的落地场景。读完你将掌握lws_dsh的完整 API 用法、碎片合并（coalescing）、拆分（split）等核心机制，以及如何用ctest跑通该自测。

一、关联文档概览：一个“能跑的说明书”

minimal-examples-lowlevel/api-tests/api-test-lws_dsh/README.md 本身非常精炼，只有三个部分：一句话定位（Demonstrates how to use and performs selftests for lws_dsh）、构建命令、命令行参数与一次运行示例。它属于典型的“最小示例 + 自测”型文档——真正的技术细节全部沉淀在同目录的 main.c 与库源码中。因此本文将以文档骨架为主线，把源码里的实现细节和测试意图逐层展开，让读者看到文档背后完整的机制。

1. 构建

文档给出的构建方式是在示例目录内直接执行：

$ cmake . && make

该示例通过 CMakeLists.txt 以find_package(libwebsockets CONFIG REQUIRED)的方式链接已安装的 libwebsockets，并调用require_lws_config()检查两个编译期开关：

• LWS_WITH_NETWORK 1：网络相关代码必须开启；
• LWS_WITH_LWS_DSH 1：lws_dsh 支持必须开启。

只有两个开关同时满足时才构建可执行文件lws-api-test-lws_dsh，并额外注册一条 ctest 测试：

add_test(NAME api-test-lws_dsh COMMAND lws-api-test-lws_dsh)

在仓库根 CMakeLists.txt 中，LWS_WITH_LWS_DSH的默认值是OFF（option(LWS_WITH_LWS_DSH "Support lws_dsh_t Disordered Shared Heap" OFF)），因此要在构建 libwebsockets 时显式开启：-DLWS_WITH_LWS_DSH=ON。完整构建参考可见 README.cmake.md。

2. 命令行用法

文档给出的命令行参数如下表：

对应地，main.c 中通过lws_switches表注册了两个开关：-d（Debug logs，如-d 15）与--help（打印帮助信息）。-d的取值在 libwebsockets 的日志系统中按位组合（LLL_ERR=1、LLL_WARN=2、LLL_NOTICE=4、LLL_INFO=8、LLL_DEBUG=16等），-d15表示同时输出 ERR/WARN/NOTICE/INFO 四类日志。详细机制参见 README.logging.md。

文档给出的典型运行输出：

$ ./lws-api-test-lws_dsh [2018/10/09 09:14:17:4834] USER: LWS API selftest: lws_dsh [2018/10/09 09:14:17:4835] USER: Completed: PASS

（时间戳为文档撰写年代的历史输出；当前版本会打印每个子测试的结果，见下文第三节。）主函数逻辑与输出完全一致：先打印LWS API selftest: lws_dsh，依次执行test1、test3～test8，任一失败即提前退出，最终打印Completed: PASS或Completed: FAIL并以返回值作为进程退出码，便于脚本与 ctest 判定。

二、lws_dsh 是什么：设计目标与适用场景

在进入测试用例前，先建立对lws_dsh的整体认识。头文件 lws-dsh.h 的注释给出了准确定义：

lws_dsh (Disordered Shared Heap) is an opaque abstraction supporting a single linear buffer (overallocated at end of the lws_dsh_t) which may contain multiple kinds of packets that are retired out of order, and tracked by kind.

几个关键设计点：

• 单次大分配：整个 dsh 只做一次堆分配，lws_dsh_t结构体、每 kind 的对象头数组（lws_dsh_obj_head_t *oha）与数据缓冲区全部位于同一块内存（dsh = lws_malloc(sizeof(lws_dsh_t) + buf_len + oha_len, ...)），并在创建时额外多分配 64 字节余量（buf_len += 64）。
• 按 kind 分 FIFO：每种报文类型拥有自己的lws_dll2队列，lws_dsh_alloc_tail()从队尾入队、lws_dsh_get_head()从队头取出。同 kind 严格 FIFO，不同 kind 之间可以乱序取用。
• 空洞即“第 0 种对象”：被释放的空闲区域作为特殊对象挂在 kind 0 的 free list 上，free list 按缓冲区地址排序，从而能以 O(邻接) 成本做合并（coalescing）。
• 多缓冲区可组队：多个 dsh 可以挂在同一个lws_dll2_owner链表上，本地装不下时可以“借用”同组其他 dsh 的空间，被借出的对象在本地记账（见第四节“foreign allocation”）。

1. 内存记账的三组指标

从 private-lib-core.h 中的lws_dsh_t结构体可以看到运行时记账字段：

• buffer_size：缓冲区总大小（含 64 字节余量）；
• locally_free/locally_in_use：本地空闲 / 在用字节数，二者之和恒等于buffer_size；
• oha[kind].total_size：每种 kind 目前在用字节数；
• splitat、flags、being_destroyed：分别控制拆分阈值、行为标志位与销毁状态。

对象本身lws_dsh_obj_t在 payload 前前置一个管理头，包含list（lws_dll2_t，必须放在首位）、归属dsh、逻辑长度size、对齐后占用的实际长度asize、以及kind（用于归还时正确记账）。所有对象都按sizeof(int *)对齐（lws_dsh_align()）。

三、测试用例逐项剖析

main.c 没有test2，测试编号为 1、3、4、5、6、7、8，覆盖了 API 的核心行为面。以下结合源码逐项说明其验证意图。

1. test1：单 dsh 多 kind 的基础 FIFO 与乱序取用

test1创建lws_dsh_create(NULL, 16384, 2)（独立 dsh，16 KB 缓冲，2 种 kind），随后：

1. kind 0 入队"hello"（5 字节）；
2. kind 1 入队"some other string"（17 字节）；
3. kind 0 再入队"hello again"（11 字节）；
4. 先取 kind 1 队头，校验为 17 字节的"some other string"；
5. 再取 kind 0 队头，依次校验 5 字节"hello"、11 字节"hello again"。

这个用例验证两件事：每种 kind 内部严格 FIFO（kind 0 先入先出，"hello"先于"hello again"被取走），以及不同 kind 之间可以乱序取用（先取 kind 1 再取 kind 0 完全合法）——这正是 “Disordered” 一词的含义。

2. test3：不可满足的大分配与多 dsh 组队

test3先lws_dll2_owner_clear(&owner)建立 owner 链表，再创建两个 4096 字节的 dsh 挂到同一 owner 上，并准备一个 8192 字节的 blob（注释特别说明：blob 足够大，确保 5000 字节请求是真实“装不下”而不是调用方虚报长度）。随后：

1. dsh1 入队 4000 字节（kind 0）；
2. dsh2 入队"hello"（5 字节）；
3. 预期失败：向 dsh1 再入队 5000 字节——此时两个 dsh 加起来也装不下，lws_dsh_alloc_tail()必须返回非 0；
4. dsh2 再入队"hello again"（11 字节）确认恢复可用。

该用例验证了分配失败路径的确定性：当本地与可借用的缓冲区都放不下时，分配被干净拒绝，且不破坏已有对象。

3. test4：耗尽 free list 后回收再分配

test4创建 4096 字节、2 kind 的 dsh，先用 4000 字节几乎占满整个缓冲，取出并释放，确认整块空间回到 free list；随后连续分配 17 字节与 11 字节两个对象，再次取出时接受两种合法结果：

• 若未合并：17 字节的"some other string"；
• 若已合并（注释明确表示“it may (should...) coalesce”）：28 字节的"some other stringhello again"。

这正是 free list 按地址排序后相邻空闲块自动合并（coalescing）的直接证据。

4. test5：PRNG 驱动的压力与双向排空

test5是唯一的随机化用例，用lws_xos（xorshift 随机数发生器，种子0x123456789abcdef0ull）模拟两类生产者/消费者的激烈竞争：

• 60% 概率：kind 0 写入 1～128 字节随机数据；
• 80% 概率：kind 1 写入 1～128 字节随机数据；
• 40% 概率：kind 0 排空当前队头（while循环取干净）；
• 30% 概率：kind 1 排空当前队头。

预算值budget = (lws_xos(&xos) % 4000) + 4000，即随机迭代 4000～7999 轮，缓冲 409600 字节。结束后把两种 kind 全部排空，并在_DEBUG构建下调用lws_dsh_describe(dsh, "test dsh end state")打印最终状态。这个用例相当于对整条“分配—乱序取用—释放—合并”链路的随机压力测试。

5. test6：顺序合并且每 kind 独立 FIFO

test6与test1结构几乎相同，但特意在 kind 0、kind 1、kind 0 交错入队后先取 kind 1、再依次取 kind 0，再次确认跨 kind 交错入队不影响各自 FIFO 的顺序性。失败路径在_DEBUG下同样会lws_dsh_describe()转储现场。

6. test7：装得下才分配，装不下就拒绝

test7在 4096 字节 dsh 中先入队 3000 字节（kind 0），再尝试入队同样 3000 字节（kind 1）。第一个 3000 字节占掉缓冲大半后，剩余空间不足以再容纳 3000 字节对象（含管理头与对齐），因此第二次分配必须失败；随后取出第一次分配的对象并逐字节比对内容（memcmp(a1, big, sizeof(big))），确认第一次分配内容完好。注释点明了边界语义：“一个分配可以留下比自身还小的剩余空间，只要它本身装得下即可；装不下的必须被拒绝”。

7. test8：部分消费与整块回收

test8展示了流式消费场景：

1. kind 0 入队 10 字节"0123456789"；
2. lws_dsh_consume(dsh, 0, 4)消费前 4 字节，再lws_dsh_get_head()应得到 6 字节的"456789"；
3. 继续lws_dsh_consume(dsh, 0, 6)消费剩余 6 字节；
4. 此时lws_dsh_get_head()必须失败（对象已不存在），且lws_dsh_get_size(dsh, 0)为 0；
5. 最后再入队 3000 字节（kind 1）必须成功——证明整块空间确实全部回收。

实现上，lws_dsh_consume()在部分消费时用memmove把剩余数据“前移”到对象头部，保持get_head()返回的指针不变（这样调用方后续仍可安全地把该指针交给lws_dsh_free()），且asize不变、记账不动；当消费长度 ≥ 对象长度时直接整对象释放。

四、核心 API 速查

以下 API 均声明于 lws-dsh.h，实现在 lws-dsh.c。

其中count_kinds可或上两个行为标志：LWS_DSHFLAG_ENABLE_COALESCE（允许与队尾对象合并，见search_best_free()中对 “natural hole” 的处理）与LWS_DSHFLAG_ENABLE_SPLIT（配合splitat把超长写入切成多段；lws_dsh_alloc_tail()中若后续分片失败，会按快照回滚已提交的分片并收缩被合并的队尾对象，避免出现“长度前缀与负载不匹配”的脏帧）。

五、实现机制纵深：free list、合并与借用

1. free list 的排序与双向合并

lws-dsh.c 中所有空闲对象挂在dsh->oha[0].owner（kind 0 即 free kind），并以buf_compare（按指针地址差）做有序插入（lws_dll2_add_sorted）。lws_dsh_free()释放对象时按地址关系执行两步合并：

1. 检查紧邻后方（list.next）是否也是空闲块，是则并入自身（[被释放][空闲] → [更大空闲]）；
2. 检查紧邻前方（list.prev）是否也是空闲块，是则被其吸收（[空闲][被释放] → [更大空闲]）。

由于 free list 持续趋向合并，地址有序性得以廉价维护。相关链表操作 API 详见 README.lws_dll.md。

2. 分配：best-fit 与 split

_lws_dsh_alloc_tail()遍历 free list 找能装下且最小的空闲块（best-fit）；若空闲块足够大（剩余部分还能容纳另一个对象头asize < asize_need + 2*sizeof(lws_dsh_obj_t)判断是否值得拆分），则把对象头前移、把“尾段”作为新空闲对象重新有序挂回 free list，从而保证后续顺序对象可以继续合并。

3. 组队与 foreign allocation

lws_dsh_create()接受owner参数把多个 dsh 挂到同一个lws_dll2_owner。当本地 free list 无法满足时，分配器会遍历同组其他 dsh 借用空间；借用来的对象在本地 kind FIFO 中照常排队记账（lws_dsh_obj_t中记录真实归属dsh），释放时归还给真实归属者。lws_dsh_destroy()销毁前会检查同组 dsh 是否有借用自己的缓冲，并尽量迁移这些对象到幸存的 dsh，实在迁移不了的才“干净销毁”。

六、lws_dsh 在仓库中的真实使用者

作为内部基础设施，lws_dsh在仓库中有多处真实落地，可以作为理解其价值的对照：

• Secure Streams 序列化代理（lib/secure-streams/serialized/proxy/proxy.c）：代理连接创建conn->dsh = lws_dsh_create(&pt->ss_dsh_owner, dsh_size, ...)，并用KIND_C_TO_P、KIND_SS_TO_P两个 kind 分别缓存 client→proxy 与 proxy→client 两个方向的序列化消息；lws_dsh_get_size()被用来做流量控制和反压判断。同组的 dsh 还可以在内存压力下互相借用，这正是“shared heap”的实际价值。
• Secure Streams 序列化客户端（sspc-deserialize.c）：按代理通告的dsh_size创建 dsh，把反序列化后的帧暂存其中。
• 传输排序器 lws_transport_sequencer（lib/core-net/lws-transport-sequencer.c）：ts->dsh = lws_dsh_create(NULL, i->window_size * 2 + 32768, 2)，用 dsh 暂存需要重排/重传的载荷，lws_dsh_get_head()与lws_dsh_free()负责按序投递与回收。

此外，README.fault-injection.md 还列出了针对 dsh 的故障注入点（如ssproxy_dsh_create_oom、ssproxy_dsh_rx_queue_oom、sspc_dsh_ss2p_oom），说明该模块被纳入 libwebsockets 的 OOM 故障注入测试体系。

七、如何验证：ctest 与故障注入

1. ctest 集成

该自测已注册进 ctest 套件。在 README.ctest.md 的完整运行记录中可以看到：

Start 4: api-test-lws_dsh 67/73 Test #4: api-test-lws_dsh ............................ Passed 0.01 sec

在仓库根目录配置构建（-DLWS_WITH_LWS_DSH=ON）后，运行ctest -R api-test-lws_dsh即可单独执行该项；也可以直接运行二进制./lws-api-test-lws_dsh，其返回值 0 表示 PASS、非 0 表示 FAIL，方便接入 CI。

2. 故障注入验证

lws_dsh 相关的故障注入点位于READMEs/README.fault-injection.md的 ssproxy 分组，可分别模拟“代理创建 dsh 时 OOM”“dsh 接收队列分配 OOM（导致下游连接断开）”“ss→proxy 方向 dsh 分配 OOM”“C→P payload 分配 OOM”等场景，用于验证库在内存耗尽路径上的健壮性。启用方法参见 README.fault-injection.md。

八、小结

从 api-test-lws_dsh/README.md 出发，我们完整覆盖了lws_dsh的构建、命令行、8 个测试用例（1、3～8）的意图与验证点，并通过源码确认了其三大核心机制：按 kind 的乱序 FIFO、地址有序 free list 的双向合并、多 dsh 组队借用。该组件在 Secure Streams 代理、序列化客户端与传输排序器中承担消息缓存职责，且有对应的 ctest 用例与故障注入点保障质量。对于希望在 libwebsockets 内部实现“单缓冲多队列、允许乱序消费”的应用，lws_dsh是一个开箱即用的选择。

• 后端
• 网络
• 通信