Linux协议栈查找算法优化随想 电脑资料

Linux协议栈查找算法优化随想 电脑资料 Linux的网络协议栈实现可谓精确却不失精巧，不必说Netfilter，单单说TC就够了，但是有几处硬伤，本文做一个不完备的记录，就当是随笔，不必当真， 0

Linux协议栈查找算法优化随想电脑资料 Linux的网络协议栈实现可谓精确却不失精巧，不必说Netfilter， 单单说TC就够了，但是有几处硬伤，本文做一个不完备的记录，就 当是随笔，不必当真， 0.查找的种类Linux协议栈作为一个纯软件实现，保存了硬件接 口，但是本文不涉及硬件。 0.1.查不到不创立像路由查找这类，如果查找不到路由项，那么就 直接返回失败，数据包就此丢弃。对于这类查找，表项的创立和删 除是特定事件(比方人为配置，网卡up/down等)触发的，不是自动 的。查找结果的成功与失败所消耗的性能是一致的，所不同的协议 栈对待成功与失败的方式不同，因此本文不关注这类查找。 0.2.查不到即创立像conntrack查找，邻居查找这类，如果查找失 败，将会建立一个新的表项，因此查找结果的成功与失败对性能的 影响是完全不对称的。如果查找失败，性能损耗是巨大的，即使对 于高效的hash算法，起码你要遍历完特定hash值指定的冲突链表 才能发现失败，这在平均看来已经是一笔很大的开销了，然后发现 失败，这才是一个开始，接下来要分配内存，创立表项，这又是一 笔很大的花费，既消耗了时间又消耗了空间。虽然空间损耗不可防 止，但是我希望在必须分配内存创立表项之前，用最快的速度发现 查找失败。 0.3.介于0.1与0.2的查找TCPsocket查找介于0.1和0.2之间， 对于Listen状态socket的查找，它的目标是创立一个客户 socket，但是首先它要确保特定的TCP四元组不在ESTABLISHED状 态或者TW状态的socket中被找到，如果存在大量的TW套接字，将