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);

建议继续学习：

1. linux内核研究笔记(一）内存管理 – page介绍    (阅读：8564)
2. 字符串匹配那些事（一）    (阅读：5765)
3. PHP内核介绍及扩展开发指南―Extensions 的编写    (阅读：4645)
4. 我的内核配置文件    (阅读：3693)
5. Linux内核协议栈对于timewait状态的处理    (阅读：3691)
6. PHP内核介绍及扩展开发指南―高级主题    (阅读：3592)
7. PHP内核介绍及扩展开发指南―基础知识    (阅读：3385)
8. Linux内核模块开发(笔记)    (阅读：3060)
9. 在 Dell PowerEdge 1950 上安装 Linux 2.6.32-rc8 内核的问题与解决    (阅读：3033)
10. 在Ubuntu上使用SystemTap    (阅读：3023)