跨 skb 数据块匹配过滤规则中的字符串
Netfilter 的 xt_string 在选择 kmp 后，以前缀表避免重复回溯，并保留匹配进度跨越同一 skb 的多个数据块。
工程问题#
字符串过滤规则需要在指定偏移范围内寻找字节模式，而 skb 的数据可能分散在多个内存块中。既要避免重复比较已经匹配的前缀，也不能因为模式跨过块边界就漏掉匹配。
实际实现#
规则安装时，string_mt_check 根据 conf->algo 调用 textsearch_prepare，并缓存模式的预处理结果。配置 kmp 时使用 kmp_ops 注册的实现；数据包匹配由 string_mt 调用 skb_find_text。kmp_find 逐块取得数据，以 q 记录已匹配的模式前缀；失配时依据 prefix_tbl 回退 q，q 在获取下一块时保持不变。
处理流程#
- 安装规则时选择 kmp，并按模式构建可复用的前缀表
- 对当前 skb 的指定偏移范围逐块取得待匹配字节
- 失配时回退到已有前缀的最长可用后缀，继续读取当前字节
- 保留 q 跨越数据块边界，找到完整模式后将位置交还过滤规则
源码片段#
固定版本 · 原文摘录54 if (conf->u.v1.flags & XT_STRING_FLAG_IGNORECASE)55 flags |= TS_IGNORECASE;56 ts_conf = textsearch_prepare(conf->algo, conf->pattern, conf->patlen,57 GFP_KERNEL, flags);58 if (IS_ERR(ts_conf))59 return PTR_ERR(ts_conf);6061 conf->config = ts_conf;62 return 0;规则检查时把算法名、模式和 flags 交给 textsearch_prepare，并将返回配置保留给后续数据包使用。
23static bool24string_mt(const struct sk_buff *skb, struct xt_action_param *par)25{26 const struct xt_string_info *conf = par->matchinfo;27 bool invert;2829 invert = conf->u.v1.flags & XT_STRING_FLAG_INVERT;3031 return (skb_find_text((struct sk_buff *)skb, conf->from_offset,32 conf->to_offset, conf->config)33 != UINT_MAX) ^ invert;34}实际过滤路径对当前 skb 的配置范围调用 skb_find_text，并按规则处理反向匹配。
49 for (;;) {50 text_len = conf->get_next_block(consumed, &text, conf, state);5152 if (unlikely(text_len == 0))53 break;5455 for (i = 0; i < text_len; i++) {56 while (q > 0 && kmp->pattern[q]57 != (icase ? toupper(text[i]) : text[i]))58 q = kmp->prefix_tbl[q - 1];59 if (kmp->pattern[q]60 == (icase ? toupper(text[i]) : text[i]))61 q++;62 if (unlikely(q == kmp->pattern_len)) {63 state->offset = consumed + i + 1;64 return state->offset - kmp->pattern_len;65 }66 }6768 consumed += text_len;69 }q 在块循环外初始化，在不同 get_next_block 返回的数据块之间保持。失配时按前缀表回退，找到完整模式就返回其起始位置。
74static inline void compute_prefix_tbl(const u8 *pattern, unsigned int len,75 unsigned int *prefix_tbl, int flags)76{77 unsigned int k, q;78 const u8 icase = flags & TS_IGNORECASE;7980 for (k = 0, q = 1; q < len; q++) {81 while (k > 0 && (icase ? toupper(pattern[k]) : pattern[k])82 != (icase ? toupper(pattern[q]) : pattern[q]))83 k = prefix_tbl[k-1];84 if ((icase ? toupper(pattern[k]) : pattern[k])85 == (icase ? toupper(pattern[q]) : pattern[q]))86 k++;87 prefix_tbl[q] = k;88 }89}按模式本身构建前缀表；失配时复用已有前缀信息，与搜索阶段的回退规则对应。
130static struct ts_ops kmp_ops = {131 .name = "kmp",132 .find = kmp_find,133 .init = kmp_init,134 .get_pattern = kmp_get_pattern,135 .get_pattern_len = kmp_get_pattern_len,136 .owner = THIS_MODULE,137 .list = LIST_HEAD_INIT(kmp_ops.list)138};139140static int __init init_kmp(void)141{142 return textsearch_register(&kmp_ops);143}将名字 kmp、初始化函数和查找函数注册到 textsearch，连接配置选择和具体实现。
五段原文展示规则安装、包匹配、块间状态、前缀表和注册机制；也保留同版 ts_bm.c 的上下文，支持对分块行为的比较。
收益与取舍#
工程分析带来的收益
- 长度 m 的模式预处理为 O(m)，单次搜索长度 n 的输入为 O(n)，每条规则保留 O(m) 的模式和前缀信息
- 在同一 skb 的非连续数据块之间保持匹配进度，无须为 KMP 先拼出一个连续大缓冲区
付出的代价
- 每条规则都要保存模式与前缀表；匹配多条规则时并不是一次共享的多模式扫描
- 逐字节扫描不保证在所有流量与模式分布上快于跳跃式匹配算法
- 字节级大小写处理不等同 Unicode 文本匹配，范围外数据也不会参与本次搜索
可比较的选择
Linux textsearch 的 Boyer–Moore 实现可以利用跳跃减少比较，但该版本文件明确提醒：跨多个输入块的模式可能匹配不到；不能只比较算法名字而忽略分块行为。
先合并缓冲区再搜索便于使用要求连续内存的算法，但可能增加复制、分配和缓冲区生命周期成本。
版本与适用范围#
对应 Linux v6.12 的 xt_string，明确限定规则算法为 kmp。这里的“跨块”是同一次 skb 文本搜索中的内存数据块，不能解释为重组任意多个 TCP 包、解密 TLS 或按应用协议解析数据；这些不由本例 KMP 完成。规则支持偏移范围、忽略大小写和反向匹配，完整检查逻辑在 xt_string.c。
参考来源#
源码、官方文档与原始论文lib/ts_kmp.c · kmp_find / compute_prefix_tbl / kmp_ops