diff options
author | Felix Fietkau <nbd@openwrt.org> | 2006-11-14 01:45:10 +0000 |
---|---|---|
committer | Felix Fietkau <nbd@openwrt.org> | 2006-11-14 01:45:10 +0000 |
commit | 1f678a186c9bded3185e31652dc4c45109b0fbd8 (patch) | |
tree | 776f309fa4f1a4c499bf102edef1f7c7ea6e71ee /target/linux/generic-2.4 | |
parent | ace9292e6625d018dd3f1176c00839e1a3231c2b (diff) | |
download | upstream-1f678a186c9bded3185e31652dc4c45109b0fbd8.tar.gz upstream-1f678a186c9bded3185e31652dc4c45109b0fbd8.tar.bz2 upstream-1f678a186c9bded3185e31652dc4c45109b0fbd8.zip |
fix the backport of ipt_string by adding the linux 2.6 textsearch code in a way that does not require adding stuff to our kernel image - linux 2.6 compatible
git-svn-id: svn://svn.openwrt.org/openwrt/trunk@5527 3c298f89-4303-0410-b956-a3cf2f4a3e73
Diffstat (limited to 'target/linux/generic-2.4')
-rw-r--r-- | target/linux/generic-2.4/patches/609-netfilter_string.patch | 867 |
1 files changed, 750 insertions, 117 deletions
diff --git a/target/linux/generic-2.4/patches/609-netfilter_string.patch b/target/linux/generic-2.4/patches/609-netfilter_string.patch index c8e1a2d2de..ed5353f7a9 100644 --- a/target/linux/generic-2.4/patches/609-netfilter_string.patch +++ b/target/linux/generic-2.4/patches/609-netfilter_string.patch @@ -1,6 +1,6 @@ -diff -Nur linux-2.4.32/include/linux/netfilter_ipv4/ipt_string.h linux-2.4.32.patch/include/linux/netfilter_ipv4/ipt_string.h ---- linux-2.4.32/include/linux/netfilter_ipv4/ipt_string.h 1970-01-01 01:00:00.000000000 +0100 -+++ linux-2.4.32.patch/include/linux/netfilter_ipv4/ipt_string.h 2005-12-16 00:40:19.082509250 +0100 +diff -urN linux.old/include/linux/netfilter_ipv4/ipt_string.h linux.dev/include/linux/netfilter_ipv4/ipt_string.h +--- linux.old/include/linux/netfilter_ipv4/ipt_string.h 1970-01-01 01:00:00.000000000 +0100 ++++ linux.dev/include/linux/netfilter_ipv4/ipt_string.h 2006-11-13 23:33:31.000000000 +0100 @@ -0,0 +1,18 @@ +#ifndef _IPT_STRING_H +#define _IPT_STRING_H @@ -20,10 +20,444 @@ diff -Nur linux-2.4.32/include/linux/netfilter_ipv4/ipt_string.h linux-2.4.32.pa +}; + +#endif /*_IPT_STRING_H*/ -diff -Nur linux-2.4.32/include/linux/textsearch.h linux-2.4.32.patch/include/linux/textsearch.h ---- linux-2.4.32/include/linux/textsearch.h 1970-01-01 01:00:00.000000000 +0100 -+++ linux-2.4.32.patch/include/linux/textsearch.h 2005-12-16 11:15:34.838073000 +0100 -@@ -0,0 +1,205 @@ +diff -urN linux.old/net/ipv4/netfilter/Config.in linux.dev/net/ipv4/netfilter/Config.in +--- linux.old/net/ipv4/netfilter/Config.in 2006-11-13 23:43:38.000000000 +0100 ++++ linux.dev/net/ipv4/netfilter/Config.in 2006-11-13 23:33:31.000000000 +0100 +@@ -52,6 +52,7 @@ + fi + if [ "$CONFIG_EXPERIMENTAL" = "y" ]; then + dep_tristate ' Unclean match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_UNCLEAN $CONFIG_IP_NF_IPTABLES ++ dep_tristate ' String match support (EXPERIMENTAL) ' CONFIG_IP_NF_MATCH_STRING $CONFIG_IP_NF_IPTABLES + dep_tristate ' Owner match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_OWNER $CONFIG_IP_NF_IPTABLES + dep_tristate ' Layer 7 match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_LAYER7 $CONFIG_IP_NF_CONNTRACK + dep_mbool ' Layer 7 debugging output (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_LAYER7_DEBUG $CONFIG_IP_NF_MATCH_LAYER7 +diff -urN linux.old/net/ipv4/netfilter/ipt_string.c linux.dev/net/ipv4/netfilter/ipt_string.c +--- linux.old/net/ipv4/netfilter/ipt_string.c 1970-01-01 01:00:00.000000000 +0100 ++++ linux.dev/net/ipv4/netfilter/ipt_string.c 2006-11-14 02:26:03.000000000 +0100 +@@ -0,0 +1,99 @@ ++/* String matching match for iptables ++ * ++ * (C) 2005 Pablo Neira Ayuso <pablo@eurodev.net> ++ * ++ * This program is free software; you can redistribute it and/or modify ++ * it under the terms of the GNU General Public License version 2 as ++ * published by the Free Software Foundation. ++ */ ++ ++#include <linux/init.h> ++#include <linux/module.h> ++#include <linux/kernel.h> ++#include <linux/skbuff.h> ++#include <linux/netfilter_ipv4/ip_tables.h> ++#include <linux/netfilter_ipv4/ipt_string.h> ++#include "textsearch/textsearch.h" ++#include "textsearch/textsearch.c" ++#include "textsearch/ts_bm.c" ++#include "textsearch/ts_kmp.c" ++ ++MODULE_AUTHOR("Pablo Neira Ayuso <pablo@eurodev.net>"); ++MODULE_DESCRIPTION("IP tables string match module"); ++MODULE_LICENSE("GPL"); ++ ++static int match(const struct sk_buff *skb, ++ const struct net_device *in, ++ const struct net_device *out, ++ const void *matchinfo, ++ int offset, ++ int *hotdrop) ++{ ++ struct iphdr *ip = skb->nh.iph; ++ struct ts_state state; ++ struct ipt_string_info *conf = (struct ipt_string_info *) matchinfo; ++ char *buf = (char *)ip+(ip->ihl*4); ++ int len = ntohs(ip->tot_len)-(ip->ihl*4); ++ ++ memset(&state, 0, sizeof(struct ts_state)); ++ ++ return (textsearch_find_continuous(conf->config, &state, buf, len) != UINT_MAX) && !conf->invert; ++} ++ ++#define STRING_TEXT_PRIV(m) ((struct ipt_string_info *) m) ++ ++static int checkentry(const char *tablename, ++ const struct ipt_ip *ip, ++ void *matchinfo, ++ unsigned int matchsize, ++ unsigned int hook_mask) ++{ ++ struct ipt_string_info *conf = matchinfo; ++ struct ts_config *ts_conf; ++ ++ if (matchsize != IPT_ALIGN(sizeof(struct ipt_string_info))) ++ return 0; ++ ++ /* Damn, can't handle this case properly with iptables... */ ++ if (conf->from_offset > conf->to_offset) ++ return 0; ++ ++ ts_conf = textsearch_prepare(conf->algo, conf->pattern, conf->patlen, ++ GFP_KERNEL, TS_AUTOLOAD); ++ if (IS_ERR(ts_conf)) ++ return 0; ++ ++ conf->config = ts_conf; ++ ++ return 1; ++} ++ ++static void destroy(void *matchinfo, unsigned int matchsize) ++{ ++ textsearch_destroy(STRING_TEXT_PRIV(matchinfo)->config); ++} ++ ++static struct ipt_match string_match = { ++ .name = "string", ++ .match = match, ++ .checkentry = checkentry, ++ .destroy = destroy, ++ .me = THIS_MODULE ++}; ++ ++static int __init init(void) ++{ ++ init_bm(); ++ init_kmp(); ++ return ipt_register_match(&string_match); ++} ++ ++static void __exit fini(void) ++{ ++ exit_kmp(); ++ exit_bm(); ++ ipt_unregister_match(&string_match); ++} ++ ++module_init(init); ++module_exit(fini); +diff -urN linux.old/net/ipv4/netfilter/Makefile linux.dev/net/ipv4/netfilter/Makefile +--- linux.old/net/ipv4/netfilter/Makefile 2006-11-13 23:43:38.000000000 +0100 ++++ linux.dev/net/ipv4/netfilter/Makefile 2006-11-13 23:33:31.000000000 +0100 +@@ -107,6 +107,7 @@ + obj-$(CONFIG_IP_NF_MATCH_CONNMARK) += ipt_connmark.o + obj-$(CONFIG_IP_NF_MATCH_CONNTRACK) += ipt_conntrack.o + obj-$(CONFIG_IP_NF_MATCH_UNCLEAN) += ipt_unclean.o ++obj-$(CONFIG_IP_NF_MATCH_STRING) += ipt_string.o + obj-$(CONFIG_IP_NF_MATCH_TCPMSS) += ipt_tcpmss.o + obj-$(CONFIG_IP_NF_MATCH_LAYER7) += ipt_layer7.o + obj-$(CONFIG_IP_NF_MATCH_CONNBYTES) += ipt_connbytes.o +diff -urN linux.old/net/ipv4/netfilter/textsearch/textsearch.c linux.dev/net/ipv4/netfilter/textsearch/textsearch.c +--- linux.old/net/ipv4/netfilter/textsearch/textsearch.c 1970-01-01 01:00:00.000000000 +0100 ++++ linux.dev/net/ipv4/netfilter/textsearch/textsearch.c 2006-11-14 02:31:47.000000000 +0100 +@@ -0,0 +1,305 @@ ++/* ++ * lib/textsearch.c Generic text search interface ++ * ++ * This program is free software; you can redistribute it and/or ++ * modify it under the terms of the GNU General Public License ++ * as published by the Free Software Foundation; either version ++ * 2 of the License, or (at your option) any later version. ++ * ++ * Authors: Thomas Graf <tgraf@suug.ch> ++ * Pablo Neira Ayuso <pablo@eurodev.net> ++ * ++ * ========================================================================== ++ * ++ * INTRODUCTION ++ * ++ * The textsearch infrastructure provides text searching facitilies for ++ * both linear and non-linear data. Individual search algorithms are ++ * implemented in modules and chosen by the user. ++ * ++ * ARCHITECTURE ++ * ++ * User ++ * +----------------+ ++ * | finish()|<--------------(6)-----------------+ ++ * |get_next_block()|<--------------(5)---------------+ | ++ * | | Algorithm | | ++ * | | +------------------------------+ ++ * | | | init() find() destroy() | ++ * | | +------------------------------+ ++ * | | Core API ^ ^ ^ ++ * | | +---------------+ (2) (4) (8) ++ * | (1)|----->| prepare() |---+ | | ++ * | (3)|----->| find()/next() |-----------+ | ++ * | (7)|----->| destroy() |----------------------+ ++ * +----------------+ +---------------+ ++ * ++ * (1) User configures a search by calling _prepare() specifying the ++ * search parameters such as the pattern and algorithm name. ++ * (2) Core requests the algorithm to allocate and initialize a search ++ * configuration according to the specified parameters. ++ * (3) User starts the search(es) by calling _find() or _next() to ++ * fetch subsequent occurrences. A state variable is provided ++ * to the algorihtm to store persistant variables. ++ * (4) Core eventually resets the search offset and forwards the find() ++ * request to the algorithm. ++ * (5) Algorithm calls get_next_block() provided by the user continously ++ * to fetch the data to be searched in block by block. ++ * (6) Algorithm invokes finish() after the last call to get_next_block ++ * to clean up any leftovers from get_next_block. (Optional) ++ * (7) User destroys the configuration by calling _destroy(). ++ * (8) Core notifies the algorithm to destroy algorithm specific ++ * allocations. (Optional) ++ * ++ * USAGE ++ * ++ * Before a search can be performed, a configuration must be created ++ * by calling textsearch_prepare() specyfing the searching algorithm and ++ * the pattern to look for. The returned configuration may then be used ++ * for an arbitary amount of times and even in parallel as long as a ++ * separate struct ts_state variable is provided to every instance. ++ * ++ * The actual search is performed by either calling textsearch_find_- ++ * continuous() for linear data or by providing an own get_next_block() ++ * implementation and calling textsearch_find(). Both functions return ++ * the position of the first occurrence of the patern or UINT_MAX if ++ * no match was found. Subsequent occurences can be found by calling ++ * textsearch_next() regardless of the linearity of the data. ++ * ++ * Once you're done using a configuration it must be given back via ++ * textsearch_destroy. ++ * ++ * EXAMPLE ++ * ++ * 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); ++ * ++ * ========================================================================== ++ */ ++ ++#include <linux/config.h> ++#include <linux/module.h> ++#include <linux/types.h> ++#include <linux/string.h> ++#include <linux/init.h> ++#include <linux/netfilter_ipv4/lockhelp.h> ++#include "textsearch.h" ++ ++static LIST_HEAD(ts_ops); ++static spinlock_t ts_mod_lock = SPIN_LOCK_UNLOCKED; ++static DECLARE_RWLOCK(ts_ops_lock); ++ ++static inline struct ts_ops *lookup_ts_algo(const char *name) ++{ ++ struct ts_ops *o; ++ ++ read_lock(&ts_ops_lock); ++ list_for_each_entry(o, &ts_ops, list) { ++ if (!strcmp(name, o->name)) { ++ MOD_INC_USE_COUNT; ++ read_unlock(&ts_ops_lock); ++ return o; ++ } ++ } ++ read_unlock(&ts_ops_lock); ++ ++ return NULL; ++} ++ ++/** ++ * textsearch_register - register a textsearch module ++ * @ops: operations lookup table ++ * ++ * This function must be called by textsearch modules to announce ++ * their presence. The specified &@ops must have %name set to a ++ * unique identifier and the callbacks find(), init(), get_pattern(), ++ * and get_pattern_len() must be implemented. ++ * ++ * Returns 0 or -EEXISTS if another module has already registered ++ * with same name. ++ */ ++int textsearch_register(struct ts_ops *ops) ++{ ++ int err = -EEXIST; ++ struct ts_ops *o; ++ ++ if (ops->name == NULL || ops->find == NULL || ops->init == NULL || ++ ops->get_pattern == NULL || ops->get_pattern_len == NULL) ++ return -EINVAL; ++ ++ spin_lock(&ts_mod_lock); ++ list_for_each_entry(o, &ts_ops, list) { ++ if (!strcmp(ops->name, o->name)) ++ goto errout; ++ } ++ ++ write_lock(&ts_ops_lock); ++ list_add_tail(&ops->list, &ts_ops); ++ write_unlock(&ts_ops_lock); ++ ++ err = 0; ++errout: ++ spin_unlock(&ts_mod_lock); ++ return err; ++} ++ ++/** ++ * textsearch_unregister - unregister a textsearch module ++ * @ops: operations lookup table ++ * ++ * This function must be called by textsearch modules to announce ++ * their disappearance for examples when the module gets unloaded. ++ * The &ops parameter must be the same as the one during the ++ * registration. ++ * ++ * Returns 0 on success or -ENOENT if no matching textsearch ++ * registration was found. ++ */ ++int textsearch_unregister(struct ts_ops *ops) ++{ ++ int err = 0; ++ struct ts_ops *o; ++ ++ spin_lock(&ts_mod_lock); ++ list_for_each_entry(o, &ts_ops, list) { ++ if (o == ops) { ++ write_lock(&ts_ops_lock); ++ list_del(&o->list); ++ write_unlock(&ts_ops_lock); ++ goto out; ++ } ++ } ++ ++ err = -ENOENT; ++out: ++ spin_unlock(&ts_mod_lock); ++ return err; ++} ++ ++struct ts_linear_state ++{ ++ unsigned int len; ++ const void *data; ++}; ++ ++static unsigned int get_linear_data(unsigned int consumed, const u8 **dst, ++ struct ts_config *conf, ++ struct ts_state *state) ++{ ++ struct ts_linear_state *st = (struct ts_linear_state *) state->cb; ++ ++ if (likely(consumed < st->len)) { ++ *dst = st->data + consumed; ++ return st->len - consumed; ++ } ++ ++ return 0; ++} ++ ++/** ++ * textsearch_find_continuous - search a pattern in continuous/linear data ++ * @conf: search configuration ++ * @state: search state ++ * @data: data to search in ++ * @len: length of data ++ * ++ * A simplified version of textsearch_find() for continuous/linear data. ++ * Call textsearch_next() to retrieve subsequent matches. ++ * ++ * Returns the position of first occurrence of the pattern or ++ * UINT_MAX if no occurrence was found. ++ */ ++unsigned int textsearch_find_continuous(struct ts_config *conf, ++ struct ts_state *state, ++ const void *data, unsigned int len) ++{ ++ struct ts_linear_state *st = (struct ts_linear_state *) state->cb; ++ ++ conf->get_next_block = get_linear_data; ++ st->data = data; ++ st->len = len; ++ ++ return textsearch_find(conf, state); ++} ++ ++/** ++ * textsearch_prepare - Prepare a search ++ * @algo: name of search algorithm ++ * @pattern: pattern data ++ * @len: length of pattern ++ * @gfp_mask: allocation mask ++ * @flags: search flags ++ * ++ * Looks up the search algorithm module and creates a new textsearch ++ * configuration for the specified pattern. Upon completion all ++ * necessary refcnts are held and the configuration must be put back ++ * using textsearch_put() after usage. ++ * ++ * Note: The format of the pattern may not be compatible between ++ * the various search algorithms. ++ * ++ * Returns a new textsearch configuration according to the specified ++ * parameters or a ERR_PTR(). ++ */ ++struct ts_config *textsearch_prepare(const char *algo, const void *pattern, ++ unsigned int len, gfp_t gfp_mask, int flags) ++{ ++ int err = -ENOENT; ++ struct ts_config *conf; ++ struct ts_ops *ops; ++ ++ ops = lookup_ts_algo(algo); ++ ++ if (ops == NULL) ++ goto errout; ++ ++ conf = ops->init(pattern, len, gfp_mask); ++ if (IS_ERR(conf)) { ++ err = PTR_ERR(conf); ++ goto errout; ++ } ++ ++ conf->ops = ops; ++ return conf; ++ ++errout: ++ if (ops) ++ MOD_DEC_USE_COUNT; ++ ++ return ERR_PTR(err); ++} ++ ++/** ++ * textsearch_destroy - destroy a search configuration ++ * @conf: search configuration ++ * ++ * Releases all references of the configuration and frees ++ * up the memory. ++ */ ++void textsearch_destroy(struct ts_config *conf) ++{ ++ if (conf->ops) { ++ if (conf->ops->destroy) ++ conf->ops->destroy(conf); ++ MOD_DEC_USE_COUNT; ++ } ++ ++ kfree(conf); ++} ++ +diff -urN linux.old/net/ipv4/netfilter/textsearch/textsearch.h linux.dev/net/ipv4/netfilter/textsearch/textsearch.h +--- linux.old/net/ipv4/netfilter/textsearch/textsearch.h 1970-01-01 01:00:00.000000000 +0100 ++++ linux.dev/net/ipv4/netfilter/textsearch/textsearch.h 2006-11-14 02:11:59.000000000 +0100 +@@ -0,0 +1,182 @@ +#ifndef __LINUX_TEXTSEARCH_H +#define __LINUX_TEXTSEARCH_H + @@ -35,30 +469,7 @@ diff -Nur linux-2.4.32/include/linux/textsearch.h linux-2.4.32.patch/include/lin +#include <linux/module.h> +#include <linux/slab.h> + -+#ifdef __CHECKER__ -+#define __bitwise__ __attribute__((bitwise)) -+#else -+#define __bitwise__ -+#endif -+#ifdef __CHECK_ENDIAN__ -+#define __bitwise __bitwise__ -+#else -+#define __bitwise -+#endif -+ -+typedef __u16 __bitwise __le16; -+typedef __u16 __bitwise __be16; -+typedef __u32 __bitwise __le32; -+typedef __u32 __bitwise __be32; -+#if defined(__GNUC__) && !defined(__STRICT_ANSI__) -+typedef __u64 __bitwise __le64; -+typedef __u64 __bitwise __be64; -+#endif -+ -+#ifdef __KERNEL__ -+typedef unsigned __bitwise__ gfp_t; -+#endif -+ ++typedef int gfp_t; +struct ts_config; + +/** @@ -215,7 +626,7 @@ diff -Nur linux-2.4.32/include/linux/textsearch.h linux-2.4.32.patch/include/lin + + conf = kmalloc(TS_PRIV_ALIGN(sizeof(*conf)) + payload, gfp_mask); + if (conf == NULL) -+ return -ENOMEM; ++ return ERR_PTR(-ENOMEM); + + memset(conf, 0, TS_PRIV_ALIGN(sizeof(*conf)) + payload); + return conf; @@ -229,120 +640,342 @@ diff -Nur linux-2.4.32/include/linux/textsearch.h linux-2.4.32.patch/include/lin +#endif /* __KERNEL__ */ + +#endif -diff -Nur linux-2.4.32/net/ipv4/netfilter/Config.in linux-2.4.32.patch/net/ipv4/netfilter/Config.in ---- linux-2.4.32/net/ipv4/netfilter/Config.in 2005-01-19 15:10:13.000000000 +0100 -+++ linux-2.4.32.patch/net/ipv4/netfilter/Config.in 2005-12-16 00:41:43.023755250 +0100 -@@ -42,6 +42,7 @@ - fi - if [ "$CONFIG_EXPERIMENTAL" = "y" ]; then - dep_tristate ' Unclean match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_UNCLEAN $CONFIG_IP_NF_IPTABLES -+ dep_tristate ' String match support (EXPERIMENTAL) ' CONFIG_IP_NF_MATCH_STRING $CONFIG_IP_NF_IPTABLES - dep_tristate ' Owner match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_OWNER $CONFIG_IP_NF_IPTABLES - fi - # The targets -diff -Nur linux-2.4.32/net/ipv4/netfilter/ipt_string.c linux-2.4.32.patch/net/ipv4/netfilter/ipt_string.c ---- linux-2.4.32/net/ipv4/netfilter/ipt_string.c 1970-01-01 01:00:00.000000000 +0100 -+++ linux-2.4.32.patch/net/ipv4/netfilter/ipt_string.c 2005-12-16 00:40:48.436343750 +0100 -@@ -0,0 +1,91 @@ -+/* String matching match for iptables +diff -urN linux.old/net/ipv4/netfilter/textsearch/ts_bm.c linux.dev/net/ipv4/netfilter/textsearch/ts_bm.c +--- linux.old/net/ipv4/netfilter/textsearch/ts_bm.c 1970-01-01 01:00:00.000000000 +0100 ++++ linux.dev/net/ipv4/netfilter/textsearch/ts_bm.c 2006-11-14 02:22:20.000000000 +0100 +@@ -0,0 +1,190 @@ ++/* ++ * lib/ts_bm.c Boyer-Moore text search implementation ++ * ++ * This program is free software; you can redistribute it and/or ++ * modify it under the terms of the GNU General Public License ++ * as published by the Free Software Foundation; either version ++ * 2 of the License, or (at your option) any later version. ++ * ++ * Authors: Pablo Neira Ayuso <pablo@eurodev.net> ++ * ++ * ========================================================================== + * -+ * (C) 2005 Pablo Neira Ayuso <pablo@eurodev.net> ++ * Implements Boyer-Moore string matching algorithm: + * -+ * This program is free software; you can redistribute it and/or modify -+ * it under the terms of the GNU General Public License version 2 as -+ * published by the Free Software Foundation. ++ * [1] A Fast String Searching Algorithm, R.S. Boyer and Moore. ++ * Communications of the Association for Computing Machinery, ++ * 20(10), 1977, pp. 762-772. ++ * http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf ++ * ++ * [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 ++ * http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf ++ * ++ * Note: Since Boyer-Moore (BM) performs searches for matchings from right ++ * to left, it's still possible that a matching could be spread over ++ * multiple blocks, in that case this algorithm won't find any coincidence. ++ * ++ * If you're willing to ensure that such thing won't ever happen, use the ++ * Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose ++ * the proper string search algorithm depending on your setting. ++ * ++ * Say you're using the textsearch infrastructure for filtering, NIDS or ++ * any similar security focused purpose, then go KMP. Otherwise, if you ++ * really care about performance, say you're classifying packets to apply ++ * Quality of Service (QoS) policies, and you don't mind about possible ++ * matchings spread over multiple fragments, then go BM. + */ + -+#include <linux/init.h> -+#include <linux/module.h> ++#include <linux/config.h> +#include <linux/kernel.h> -+#include <linux/skbuff.h> -+#include <linux/netfilter_ipv4/ip_tables.h> -+#include <linux/netfilter_ipv4/ipt_string.h> -+#include <linux/textsearch.h> ++#include <linux/module.h> ++#include <linux/types.h> ++#include <linux/string.h> ++#include "textsearch.h" + -+MODULE_AUTHOR("Pablo Neira Ayuso <pablo@eurodev.net>"); -+MODULE_DESCRIPTION("IP tables string match module"); -+MODULE_LICENSE("GPL"); ++/* Alphabet size, use ASCII */ ++#define ASIZE 256 + -+static int match(const struct sk_buff *skb, -+ const struct net_device *in, -+ const struct net_device *out, -+ const void *matchinfo, -+ int offset, -+ int *hotdrop) ++#if 0 ++#define DEBUGP printk ++#else ++#define DEBUGP(args, format...) ++#endif ++ ++struct ts_bm +{ -+ struct ts_state state; -+ struct ipt_string_info *conf = (struct ipt_string_info *) matchinfo; ++ u8 * pattern; ++ unsigned int patlen; ++ unsigned int bad_shift[ASIZE]; ++ unsigned int good_shift[0]; ++}; + -+ memset(&state, 0, sizeof(struct ts_state)); ++static unsigned int bm_find(struct ts_config *conf, struct ts_state *state) ++{ ++ struct ts_bm *bm = ts_config_priv(conf); ++ unsigned int i, text_len, consumed = state->offset; ++ const u8 *text; ++ int shift = bm->patlen, bs; ++ ++ for (;;) { ++ text_len = conf->get_next_block(consumed, &text, conf, state); ++ ++ if (unlikely(text_len == 0)) ++ break; ++ ++ while (shift < text_len) { ++ DEBUGP("Searching in position %d (%c)\n", ++ shift, text[shift]); ++ for (i = 0; i < bm->patlen; i++) ++ if (text[shift-i] != bm->pattern[bm->patlen-1-i]) ++ goto next; + -+ return (skb_find_text((struct sk_buff *)skb, conf->from_offset, -+ conf->to_offset, conf->config, &state) -+ != UINT_MAX) && !conf->invert; ++ /* London calling... */ ++ DEBUGP("found!\n"); ++ return consumed += (shift-(bm->patlen-1)); ++ ++next: bs = bm->bad_shift[text[shift-i]]; ++ ++ /* Now jumping to... */ ++ shift = max_t(int, shift-i+bs, shift+bm->good_shift[i]); ++ } ++ consumed += text_len; ++ } ++ ++ return UINT_MAX; +} + -+#define STRING_TEXT_PRIV(m) ((struct ipt_string_info *) m) ++static int subpattern(u8 *pattern, int i, int j, int g) ++{ ++ int x = i+g-1, y = j+g-1, ret = 0; ++ ++ while(pattern[x--] == pattern[y--]) { ++ if (y < 0) { ++ ret = 1; ++ break; ++ } ++ if (--g == 0) { ++ ret = pattern[i-1] != pattern[j-1]; ++ break; ++ } ++ } + -+static int checkentry(const char *tablename, -+ const struct ipt_ip *ip, -+ void *matchinfo, -+ unsigned int matchsize, -+ unsigned int hook_mask) ++ return ret; ++} ++ ++static void bm_compute_prefix_tbl(struct ts_bm *bm, const u8 *pattern, ++ unsigned int len) +{ -+ struct ipt_string_info *conf = matchinfo; -+ struct ts_config *ts_conf; ++ int i, j, g; ++ ++ for (i = 0; i < ASIZE; i++) ++ bm->bad_shift[i] = len; ++ for (i = 0; i < len - 1; i++) ++ bm->bad_shift[pattern[i]] = len - 1 - i; ++ ++ /* Compute the good shift array, used to match reocurrences ++ * of a subpattern */ ++ bm->good_shift[0] = 1; ++ for (i = 1; i < bm->patlen; i++) ++ bm->good_shift[i] = bm->patlen; ++ for (i = bm->patlen-1, g = 1; i > 0; g++, i--) { ++ for (j = i-1; j >= 1-g ; j--) ++ if (subpattern(bm->pattern, i, j, g)) { ++ bm->good_shift[g] = bm->patlen-j-g; ++ break; ++ } ++ } ++} + -+ if (matchsize != IPT_ALIGN(sizeof(struct ipt_string_info))) -+ return 0; ++static struct ts_config *bm_init(const void *pattern, unsigned int len, ++ gfp_t gfp_mask) ++{ ++ struct ts_config *conf; ++ struct ts_bm *bm; ++ unsigned int prefix_tbl_len = len * sizeof(unsigned int); ++ size_t priv_size = sizeof(*bm) + len + prefix_tbl_len; + -+ /* Damn, can't handle this case properly with iptables... */ -+ if (conf->from_offset > conf->to_offset) -+ return 0; ++ conf = alloc_ts_config(priv_size, gfp_mask); ++ if (IS_ERR(conf)) ++ return conf; + -+ ts_conf = textsearch_prepare(conf->algo, conf->pattern, conf->patlen, -+ GFP_KERNEL, TS_AUTOLOAD); -+ if (IS_ERR(ts_conf)) -+ return 0; ++ bm = ts_config_priv(conf); ++ bm->patlen = len; ++ bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len; ++ bm_compute_prefix_tbl(bm, pattern, len); ++ memcpy(bm->pattern, pattern, len); + -+ conf->config = ts_conf; ++ return conf; ++} + -+ return 1; ++static void *bm_get_pattern(struct ts_config *conf) ++{ ++ struct ts_bm *bm = ts_config_priv(conf); ++ return bm->pattern; +} + -+static void destroy(void *matchinfo, unsigned int matchsize) ++static unsigned int bm_get_pattern_len(struct ts_config *conf) +{ -+ textsearch_destroy(STRING_TEXT_PRIV(matchinfo)->config); ++ struct ts_bm *bm = ts_config_priv(conf); ++ return bm->patlen; +} + -+static struct ipt_match string_match = { -+ .name = "string", -+ .match = match, -+ .checkentry = checkentry, -+ .destroy = destroy, -+ .me = THIS_MODULE ++static struct ts_ops bm_ops = { ++ .name = "bm", ++ .find = bm_find, ++ .init = bm_init, ++ .get_pattern = bm_get_pattern, ++ .get_pattern_len = bm_get_pattern_len, ++ .owner = THIS_MODULE, ++ .list = LIST_HEAD_INIT(bm_ops.list) +}; + -+static int __init init(void) ++static int __init init_bm(void) +{ -+ return ipt_register_match(&string_match); ++ return textsearch_register(&bm_ops); +} + -+static void __exit fini(void) ++static void __exit exit_bm(void) +{ -+ ipt_unregister_match(&string_match); ++ textsearch_unregister(&bm_ops); ++} +diff -urN linux.old/net/ipv4/netfilter/textsearch/ts_kmp.c linux.dev/net/ipv4/netfilter/textsearch/ts_kmp.c +--- linux.old/net/ipv4/netfilter/textsearch/ts_kmp.c 1970-01-01 01:00:00.000000000 +0100 ++++ linux.dev/net/ipv4/netfilter/textsearch/ts_kmp.c 2006-11-14 02:22:04.000000000 +0100 +@@ -0,0 +1,141 @@ ++/* ++ * lib/ts_kmp.c Knuth-Morris-Pratt text search implementation ++ * ++ * This program is free software; you can redistribute it and/or ++ * modify it under the terms of the GNU General Public License ++ * as published by the Free Software Foundation; either version ++ * 2 of the License, or (at your option) any later version. ++ * ++ * Authors: Thomas Graf <tgraf@suug.ch> ++ * ++ * ========================================================================== ++ * ++ * Implements a linear-time string-matching algorithm due to Knuth, ++ * Morris, and Pratt [1]. Their algorithm avoids the explicit ++ * computation of the transition function DELTA altogether. Its ++ * matching time is O(n), for n being length(text), using just an ++ * auxiliary function PI[1..m], for m being length(pattern), ++ * precomputed from the pattern in time O(m). The array PI allows ++ * the transition function DELTA to be computed efficiently ++ * "on the fly" as needed. Roughly speaking, for any state ++ * "q" = 0,1,...,m and any character "a" in SIGMA, the value ++ * PI["q"] contains the information that is independent of "a" and ++ * is needed to compute DELTA("q", "a") [2]. Since the array PI ++ * has only m entries, whereas DELTA has O(m|SIGMA|) entries, we ++ * save a factor of |SIGMA| in the preprocessing time by computing ++ * PI rather than DELTA. ++ * ++ * [1] Cormen, Leiserson, Rivest, Stein ++ * Introdcution to Algorithms, 2nd Edition, MIT Press ++ * [2] See finite automation theory ++ */ ++ ++#include <linux/config.h> ++#include <linux/module.h> ++#include <linux/types.h> ++#include <linux/string.h> ++#include "textsearch.h" ++ ++struct ts_kmp ++{ ++ u8 * pattern; ++ unsigned int pattern_len; ++ unsigned int prefix_tbl[0]; ++}; ++ ++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; ++ ++ 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] != text[i]) ++ q = kmp->prefix_tbl[q - 1]; ++ if (kmp->pattern[q] == 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; ++} ++ ++static inline void kmp_compute_prefix_tbl(const u8 *pattern, unsigned int len, ++ unsigned int *prefix_tbl) ++{ ++ unsigned int k, q; ++ ++ for (k = 0, q = 1; q < len; q++) { ++ while (k > 0 && pattern[k] != pattern[q]) ++ k = prefix_tbl[k-1]; ++ if (pattern[k] == pattern[q]) ++ k++; ++ prefix_tbl[q] = k; ++ } ++} ++ ++static struct ts_config *kmp_init(const void *pattern, unsigned int len, ++ gfp_t gfp_mask) ++{ ++ struct ts_config *conf; ++ struct ts_kmp *kmp; ++ unsigned int prefix_tbl_len = len * sizeof(unsigned int); ++ size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len; ++ ++ conf = alloc_ts_config(priv_size, gfp_mask); ++ if (IS_ERR(conf)) ++ return conf; ++ ++ kmp = ts_config_priv(conf); ++ kmp->pattern_len = len; ++ kmp_compute_prefix_tbl(pattern, len, kmp->prefix_tbl); ++ kmp->pattern = (u8 *) kmp->prefix_tbl + prefix_tbl_len; ++ memcpy(kmp->pattern, pattern, len); ++ ++ return conf; ++} ++ ++static void *kmp_get_pattern(struct ts_config *conf) ++{ ++ struct ts_kmp *kmp = ts_config_priv(conf); ++ return kmp->pattern; ++} ++ ++static unsigned int kmp_get_pattern_len(struct ts_config *conf) ++{ ++ struct ts_kmp *kmp = ts_config_priv(conf); ++ return kmp->pattern_len; ++} ++ ++static struct ts_ops kmp_ops = { ++ .name = "kmp", ++ .find = kmp_find, ++ .init = kmp_init, ++ .get_pattern = kmp_get_pattern, ++ .get_pattern_len = kmp_get_pattern_len, ++ .owner = THIS_MODULE, ++ .list = LIST_HEAD_INIT(kmp_ops.list) ++}; ++ ++static int __init init_kmp(void) ++{ ++ return textsearch_register(&kmp_ops); ++} ++ ++static void __exit exit_kmp(void) ++{ ++ textsearch_unregister(&kmp_ops); +} + -+module_init(init); -+module_exit(fini); -diff -Nur linux-2.4.32/net/ipv4/netfilter/Makefile linux-2.4.32.patch/net/ipv4/netfilter/Makefile ---- linux-2.4.32/net/ipv4/netfilter/Makefile 2003-08-25 13:44:44.000000000 +0200 -+++ linux-2.4.32.patch/net/ipv4/netfilter/Makefile 2005-12-16 00:42:10.929499250 +0100 -@@ -85,6 +85,7 @@ - obj-$(CONFIG_IP_NF_MATCH_STATE) += ipt_state.o - obj-$(CONFIG_IP_NF_MATCH_CONNTRACK) += ipt_conntrack.o - obj-$(CONFIG_IP_NF_MATCH_UNCLEAN) += ipt_unclean.o -+obj-$(CONFIG_IP_NF_MATCH_STRING) += ipt_string.o - obj-$(CONFIG_IP_NF_MATCH_TCPMSS) += ipt_tcpmss.o - - # targets |