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 的函数是：

[c]
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  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;
    }

}
[/c]

结合 KMP 实现的主函数来理解更一目了然：

[c]
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  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;

}
[/c]

内核中的 KMP 函数接口是封装过的，你不能直接调用它。如果你的内核模块中要使用它，可以参考 lib/textsearch.c 中给的例子：

[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 %dn”, pos);

textsearch_destroy(conf);
[/c]