Linux 内核中使用到了字符串搜索，所以它也有 KMP 算法的实现，代码在 lib/ts_kmp.c 中。
Linux 内核中用到 KMP 算法的地方有三处：iptables string match 模块、iptables conntrack amanda 模块（不知道这个是用来干什么的）、以及 ematch qdisc。iptables string match 是通过字符串搜索来匹配一个包，然后进行相应的处理，比如用下面的命令可以阻止对domain.com服务器的HTTP请求：
iptables -I INPUT 1 -p tcp --dport 80 -m string --string "domain.com" --algo kmp -j DROP
至于 ematch qdisc，和它类似，可以通过字符串匹配到对应的包进行 QoS，比如这个例子：
tc filter add dev eth0 parent 10:12 prio 10 protocol ip basic match 'text(kmp foobar from 0 to 200)' flowid 10:1
总之，在内核中实现 KMP 算法是有必要的。下面来看具体实现。
我们知道，KMP 算法中最核心的地方就是 prefix 的计算，也称为 next 数组，它用来表示当字符 pattern[i] 匹配失败后应该从 pattern[next[i]] 字符继续进行匹配，而不总是从头开始，因此它的时间复杂度是O(n)。如果你对 KMP 不熟悉的话，网上有很多介绍，我觉得这篇文章还算不错，在继续看下面的代码之前可以读一下它。
内核中实现比网上的很多代码都更容易理解，因为在匹配开始之前，它就先把 prefix 计算好了。计算 prefix 的函数是：
static inline void compute_prefix_tbl(const u8 *pattern, unsigned int len,
unsigned int *prefix_tbl, int flags)
{
unsigned int k, q;
const u8 icase = flags & TS_IGNORECASE;
for (k = 0, q = 1; q <len; q++) {
while (k> 0 && (icase ? toupper(pattern[k]) : pattern[k])
!= (icase ? toupper(pattern[q]) : pattern[q]))
k = prefix_tbl[k-1];
if ((icase ? toupper(pattern[k]) : pattern[k])
== (icase ? toupper(pattern[q]) : pattern[q]))
k++;
prefix_tbl[q] = k;
}
}
结合 KMP 实现的主函数来理解更一目了然：
static unsigned int kmp_find(struct ts_config *conf, struct ts_state *state)
{
struct ts_kmp *kmp = ts_config_priv(conf);
unsigned int i, q = 0, text_len, consumed = state->offset;
const u8 *text;
const int icase = conf->flags & TS_IGNORECASE;
for (;;) {
text_len = conf->get_next_block(consumed, &text, conf, state);
if (unlikely(text_len == 0))
break;
for (i = 0; i <text_len; i++) {
while (q> 0 && kmp->pattern[q]
!= (icase ? toupper(text[i]) : text[i]))
q = kmp->prefix_tbl[q - 1];
if (kmp->pattern[q]
== (icase ? toupper(text[i]) : text[i]))
q++;
if (unlikely(q == kmp->pattern_len)) {
state->offset = consumed + i + 1;
return state->offset - kmp->pattern_len;
}
}
consumed += text_len;
}
return UINT_MAX;
}
内核中的 KMP 函数接口是封装过的，你不能直接调用它。如果你的内核模块中要使用它，可以参考 lib/textsearch.c 中给的例子：
int pos;
struct ts_config *conf;
struct ts_state state;
const char *pattern = "chicken";
const char *example = "We dance the funky chicken";
conf = textsearch_prepare("kmp", pattern, strlen(pattern),
GFP_KERNEL, TS_AUTOLOAD);
if (IS_ERR(conf)) {
err = PTR_ERR(conf);
goto errout;
}
pos = textsearch_find_continuous(conf, &state, example, strlen(example));
if (pos != UINT_MAX)
panic("Oh my god, dancing chickens at %d\n", pos);
textsearch_destroy(conf);