target/linux/generic-2.4/patches/609-netfilter_string.patch

   1 diff -urN linux.old/include/linux/netfilter_ipv4/ipt_string.h linux.dev/include/linux/netfilter_ipv4/ipt_string.h
   2 --- linux.old/include/linux/netfilter_ipv4/ipt_string.h 1970-01-01 01:00:00.000000000 +0100
   3 +++ linux.dev/include/linux/netfilter_ipv4/ipt_string.h 2006-11-13 23:33:31.000000000 +0100
   4 @@ -0,0 +1,18 @@
   5 +#ifndef _IPT_STRING_H
   6 +#define _IPT_STRING_H
   7 +
   8 +#define IPT_STRING_MAX_PATTERN_SIZE 128
   9 +#define IPT_STRING_MAX_ALGO_NAME_SIZE 16
  10 +
  11 +struct ipt_string_info
  12 +{
  13 +       u_int16_t from_offset;
  14 +       u_int16_t to_offset;
  15 +       char      algo[IPT_STRING_MAX_ALGO_NAME_SIZE];
  16 +       char      pattern[IPT_STRING_MAX_PATTERN_SIZE];
  17 +       u_int8_t  patlen;
  18 +       u_int8_t  invert;
  19 +       struct ts_config __attribute__((aligned(8))) *config;
  20 +};
  21 +
  22 +#endif /*_IPT_STRING_H*/
  23 diff -urN linux.old/net/ipv4/netfilter/Config.in linux.dev/net/ipv4/netfilter/Config.in
  24 --- linux.old/net/ipv4/netfilter/Config.in      2006-11-13 23:43:38.000000000 +0100
  25 +++ linux.dev/net/ipv4/netfilter/Config.in      2006-11-13 23:33:31.000000000 +0100
  26 @@ -52,6 +52,7 @@
  27    fi
  28    if [ "$CONFIG_EXPERIMENTAL" = "y" ]; then
  29      dep_tristate '  Unclean match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_UNCLEAN $CONFIG_IP_NF_IPTABLES
  30 +    dep_tristate '  String match support (EXPERIMENTAL) ' CONFIG_IP_NF_MATCH_STRING $CONFIG_IP_NF_IPTABLES
  31      dep_tristate '  Owner match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_OWNER $CONFIG_IP_NF_IPTABLES
  32      dep_tristate '  Layer 7 match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_LAYER7 $CONFIG_IP_NF_CONNTRACK
  33      dep_mbool '  Layer 7 debugging output (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_LAYER7_DEBUG $CONFIG_IP_NF_MATCH_LAYER7
  34 diff -urN linux.old/net/ipv4/netfilter/ipt_string.c linux.dev/net/ipv4/netfilter/ipt_string.c
  35 --- linux.old/net/ipv4/netfilter/ipt_string.c   1970-01-01 01:00:00.000000000 +0100
  36 +++ linux.dev/net/ipv4/netfilter/ipt_string.c   2006-11-14 02:26:03.000000000 +0100
  37 @@ -0,0 +1,99 @@
  38 +/* String matching match for iptables
  39 + *
  40 + * (C) 2005 Pablo Neira Ayuso <pablo@eurodev.net>
  41 + *
  42 + * This program is free software; you can redistribute it and/or modify
  43 + * it under the terms of the GNU General Public License version 2 as
  44 + * published by the Free Software Foundation.
  45 + */
  46 +
  47 +#include <linux/init.h>
  48 +#include <linux/module.h>
  49 +#include <linux/kernel.h>
  50 +#include <linux/skbuff.h>
  51 +#include <linux/netfilter_ipv4/ip_tables.h>
  52 +#include <linux/netfilter_ipv4/ipt_string.h>
  53 +#include "textsearch/textsearch.h"
  54 +#include "textsearch/textsearch.c"
  55 +#include "textsearch/ts_bm.c"
  56 +#include "textsearch/ts_kmp.c"
  57 +
  58 +MODULE_AUTHOR("Pablo Neira Ayuso <pablo@eurodev.net>");
  59 +MODULE_DESCRIPTION("IP tables string match module");
  60 +MODULE_LICENSE("GPL");
  61 +
  62 +static int match(const struct sk_buff *skb,
  63 +                const struct net_device *in,
  64 +                const struct net_device *out,
  65 +                const void *matchinfo,
  66 +                int offset,
  67 +                int *hotdrop)
  68 +{
  69 +       struct iphdr *ip = skb->nh.iph;
  70 +       struct ts_state state;
  71 +       struct ipt_string_info *conf = (struct ipt_string_info *) matchinfo;
  72 +       char *buf = (char *)ip+(ip->ihl*4);
  73 +       int len = ntohs(ip->tot_len)-(ip->ihl*4);
  74 +
  75 +       memset(&state, 0, sizeof(struct ts_state));
  76 +
  77 +       return (textsearch_find_continuous(conf->config, &state, buf, len) != UINT_MAX) && !conf->invert;
  78 +}
  79 +
  80 +#define STRING_TEXT_PRIV(m) ((struct ipt_string_info *) m)
  81 +
  82 +static int checkentry(const char *tablename,
  83 +                     const struct ipt_ip *ip,
  84 +                     void *matchinfo,
  85 +                     unsigned int matchsize,
  86 +                     unsigned int hook_mask)
  87 +{
  88 +       struct ipt_string_info *conf = matchinfo;
  89 +       struct ts_config *ts_conf;
  90 +
  91 +       if (matchsize != IPT_ALIGN(sizeof(struct ipt_string_info)))
  92 +               return 0;
  93 +
  94 +       /* Damn, can't handle this case properly with iptables... */
  95 +       if (conf->from_offset > conf->to_offset)
  96 +               return 0;
  97 +
  98 +       ts_conf = textsearch_prepare(conf->algo, conf->pattern, conf->patlen,
  99 +                                    GFP_KERNEL, TS_AUTOLOAD);
 100 +       if (IS_ERR(ts_conf))
 101 +               return 0;
 102 +
 103 +       conf->config = ts_conf;
 104 +
 105 +       return 1;
 106 +}
 107 +
 108 +static void destroy(void *matchinfo, unsigned int matchsize)
 109 +{
 110 +       textsearch_destroy(STRING_TEXT_PRIV(matchinfo)->config);
 111 +}
 112 +
 113 +static struct ipt_match string_match = {
 114 +       .name           = "string",
 115 +       .match          = match,
 116 +       .checkentry     = checkentry,
 117 +       .destroy        = destroy,
 118 +       .me             = THIS_MODULE
 119 +};
 120 +
 121 +static int __init init(void)
 122 +{
 123 +       init_bm();
 124 +       init_kmp();
 125 +       return ipt_register_match(&string_match);
 126 +}
 127 +
 128 +static void __exit fini(void)
 129 +{
 130 +       exit_kmp();
 131 +       exit_bm();
 132 +       ipt_unregister_match(&string_match);
 133 +}
 134 +
 135 +module_init(init);
 136 +module_exit(fini);
 137 diff -urN linux.old/net/ipv4/netfilter/Makefile linux.dev/net/ipv4/netfilter/Makefile
 138 --- linux.old/net/ipv4/netfilter/Makefile       2006-11-13 23:43:38.000000000 +0100
 139 +++ linux.dev/net/ipv4/netfilter/Makefile       2006-11-13 23:33:31.000000000 +0100
 140 @@ -107,6 +107,7 @@
 141  obj-$(CONFIG_IP_NF_MATCH_CONNMARK) += ipt_connmark.o
 142  obj-$(CONFIG_IP_NF_MATCH_CONNTRACK) += ipt_conntrack.o
 143  obj-$(CONFIG_IP_NF_MATCH_UNCLEAN) += ipt_unclean.o
 144 +obj-$(CONFIG_IP_NF_MATCH_STRING) += ipt_string.o
 145  obj-$(CONFIG_IP_NF_MATCH_TCPMSS) += ipt_tcpmss.o
 146  obj-$(CONFIG_IP_NF_MATCH_LAYER7) += ipt_layer7.o
 147  obj-$(CONFIG_IP_NF_MATCH_CONNBYTES) += ipt_connbytes.o
 148 diff -urN linux.old/net/ipv4/netfilter/textsearch/textsearch.c linux.dev/net/ipv4/netfilter/textsearch/textsearch.c
 149 --- linux.old/net/ipv4/netfilter/textsearch/textsearch.c        1970-01-01 01:00:00.000000000 +0100
 150 +++ linux.dev/net/ipv4/netfilter/textsearch/textsearch.c        2006-11-14 02:31:47.000000000 +0100
 151 @@ -0,0 +1,305 @@
 152 +/*
 153 + * lib/textsearch.c    Generic text search interface
 154 + *
 155 + *             This program is free software; you can redistribute it and/or
 156 + *             modify it under the terms of the GNU General Public License
 157 + *             as published by the Free Software Foundation; either version
 158 + *             2 of the License, or (at your option) any later version.
 159 + *
 160 + * Authors:    Thomas Graf <tgraf@suug.ch>
 161 + *             Pablo Neira Ayuso <pablo@eurodev.net>
 162 + *
 163 + * ==========================================================================
 164 + *
 165 + * INTRODUCTION
 166 + *
 167 + *   The textsearch infrastructure provides text searching facitilies for
 168 + *   both linear and non-linear data. Individual search algorithms are
 169 + *   implemented in modules and chosen by the user.
 170 + *
 171 + * ARCHITECTURE
 172 + *
 173 + *      User
 174 + *     +----------------+
 175 + *     |        finish()|<--------------(6)-----------------+
 176 + *     |get_next_block()|<--------------(5)---------------+ |
 177 + *     |                |                     Algorithm   | |
 178 + *     |                |                    +------------------------------+
 179 + *     |                |                    |  init()   find()   destroy() |
 180 + *     |                |                    +------------------------------+
 181 + *     |                |       Core API           ^       ^          ^
 182 + *     |                |      +---------------+  (2)     (4)        (8)
 183 + *     |             (1)|----->| prepare()     |---+       |          |
 184 + *     |             (3)|----->| find()/next() |-----------+          |
 185 + *     |             (7)|----->| destroy()     |----------------------+
 186 + *     +----------------+      +---------------+
 187 + *
 188 + *   (1) User configures a search by calling _prepare() specifying the
 189 + *       search parameters such as the pattern and algorithm name.
 190 + *   (2) Core requests the algorithm to allocate and initialize a search
 191 + *       configuration according to the specified parameters.
 192 + *   (3) User starts the search(es) by calling _find() or _next() to
 193 + *       fetch subsequent occurrences. A state variable is provided
 194 + *       to the algorihtm to store persistant variables.
 195 + *   (4) Core eventually resets the search offset and forwards the find()
 196 + *       request to the algorithm.
 197 + *   (5) Algorithm calls get_next_block() provided by the user continously
 198 + *       to fetch the data to be searched in block by block.
 199 + *   (6) Algorithm invokes finish() after the last call to get_next_block
 200 + *       to clean up any leftovers from get_next_block. (Optional)
 201 + *   (7) User destroys the configuration by calling _destroy().
 202 + *   (8) Core notifies the algorithm to destroy algorithm specific
 203 + *       allocations. (Optional)
 204 + *
 205 + * USAGE
 206 + *
 207 + *   Before a search can be performed, a configuration must be created
 208 + *   by calling textsearch_prepare() specyfing the searching algorithm and
 209 + *   the pattern to look for. The returned configuration may then be used
 210 + *   for an arbitary amount of times and even in parallel as long as a
 211 + *   separate struct ts_state variable is provided to every instance.
 212 + *
 213 + *   The actual search is performed by either calling textsearch_find_-
 214 + *   continuous() for linear data or by providing an own get_next_block()
 215 + *   implementation and calling textsearch_find(). Both functions return
 216 + *   the position of the first occurrence of the patern or UINT_MAX if
 217 + *   no match was found. Subsequent occurences can be found by calling
 218 + *   textsearch_next() regardless of the linearity of the data.
 219 + *
 220 + *   Once you're done using a configuration it must be given back via
 221 + *   textsearch_destroy.
 222 + *
 223 + * EXAMPLE
 224 + *
 225 + *   int pos;
 226 + *   struct ts_config *conf;
 227 + *   struct ts_state state;
 228 + *   const char *pattern = "chicken";
 229 + *   const char *example = "We dance the funky chicken";
 230 + *
 231 + *   conf = textsearch_prepare("kmp", pattern, strlen(pattern),
 232 + *                             GFP_KERNEL, TS_AUTOLOAD);
 233 + *   if (IS_ERR(conf)) {
 234 + *       err = PTR_ERR(conf);
 235 + *       goto errout;
 236 + *   }
 237 + *
 238 + *   pos = textsearch_find_continuous(conf, &state, example, strlen(example));
 239 + *   if (pos != UINT_MAX)
 240 + *       panic("Oh my god, dancing chickens at %d\n", pos);
 241 + *
 242 + *   textsearch_destroy(conf);
 243 + *
 244 + * ==========================================================================
 245 + */
 246 +
 247 +#include <linux/config.h>
 248 +#include <linux/module.h>
 249 +#include <linux/types.h>
 250 +#include <linux/string.h>
 251 +#include <linux/init.h>
 252 +#include <linux/netfilter_ipv4/lockhelp.h>
 253 +#include "textsearch.h"
 254 +
 255 +static LIST_HEAD(ts_ops);
 256 +static spinlock_t ts_mod_lock = SPIN_LOCK_UNLOCKED;
 257 +static DECLARE_RWLOCK(ts_ops_lock);
 258 +
 259 +static inline struct ts_ops *lookup_ts_algo(const char *name)
 260 +{
 261 +       struct ts_ops *o;
 262 +
 263 +       read_lock(&ts_ops_lock);
 264 +       list_for_each_entry(o, &ts_ops, list) {
 265 +               if (!strcmp(name, o->name)) {
 266 +                       MOD_INC_USE_COUNT;
 267 +                       read_unlock(&ts_ops_lock);
 268 +                       return o;
 269 +               }
 270 +       }
 271 +       read_unlock(&ts_ops_lock);
 272 +
 273 +       return NULL;
 274 +}
 275 +
 276 +/**
 277 + * textsearch_register - register a textsearch module
 278 + * @ops: operations lookup table
 279 + *
 280 + * This function must be called by textsearch modules to announce
 281 + * their presence. The specified &@ops must have %name set to a
 282 + * unique identifier and the callbacks find(), init(), get_pattern(),
 283 + * and get_pattern_len() must be implemented.
 284 + *
 285 + * Returns 0 or -EEXISTS if another module has already registered
 286 + * with same name.
 287 + */
 288 +int textsearch_register(struct ts_ops *ops)
 289 +{
 290 +       int err = -EEXIST;
 291 +       struct ts_ops *o;
 292 +
 293 +       if (ops->name == NULL || ops->find == NULL || ops->init == NULL ||
 294 +           ops->get_pattern == NULL || ops->get_pattern_len == NULL)
 295 +               return -EINVAL;
 296 +
 297 +       spin_lock(&ts_mod_lock);
 298 +       list_for_each_entry(o, &ts_ops, list) {
 299 +               if (!strcmp(ops->name, o->name))
 300 +                       goto errout;
 301 +       }
 302 +
 303 +       write_lock(&ts_ops_lock);
 304 +       list_add_tail(&ops->list, &ts_ops);
 305 +       write_unlock(&ts_ops_lock);
 306 +
 307 +       err = 0;
 308 +errout:
 309 +       spin_unlock(&ts_mod_lock);
 310 +       return err;
 311 +}
 312 +
 313 +/**
 314 + * textsearch_unregister - unregister a textsearch module
 315 + * @ops: operations lookup table
 316 + *
 317 + * This function must be called by textsearch modules to announce
 318 + * their disappearance for examples when the module gets unloaded.
 319 + * The &ops parameter must be the same as the one during the
 320 + * registration.
 321 + *
 322 + * Returns 0 on success or -ENOENT if no matching textsearch
 323 + * registration was found.
 324 + */
 325 +int textsearch_unregister(struct ts_ops *ops)
 326 +{
 327 +       int err = 0;
 328 +       struct ts_ops *o;
 329 +
 330 +       spin_lock(&ts_mod_lock);
 331 +       list_for_each_entry(o, &ts_ops, list) {
 332 +               if (o == ops) {
 333 +                       write_lock(&ts_ops_lock);
 334 +                       list_del(&o->list);
 335 +                       write_unlock(&ts_ops_lock);
 336 +                       goto out;
 337 +               }
 338 +       }
 339 +
 340 +       err = -ENOENT;
 341 +out:
 342 +       spin_unlock(&ts_mod_lock);
 343 +       return err;
 344 +}
 345 +
 346 +struct ts_linear_state
 347 +{
 348 +       unsigned int    len;
 349 +       const void      *data;
 350 +};
 351 +
 352 +static unsigned int get_linear_data(unsigned int consumed, const u8 **dst,
 353 +                                   struct ts_config *conf,
 354 +                                   struct ts_state *state)
 355 +{
 356 +       struct ts_linear_state *st = (struct ts_linear_state *) state->cb;
 357 +
 358 +       if (likely(consumed < st->len)) {
 359 +               *dst = st->data + consumed;
 360 +               return st->len - consumed;
 361 +       }
 362 +
 363 +       return 0;
 364 +}
 365 +
 366 +/**
 367 + * textsearch_find_continuous - search a pattern in continuous/linear data
 368 + * @conf: search configuration
 369 + * @state: search state
 370 + * @data: data to search in
 371 + * @len: length of data
 372 + *
 373 + * A simplified version of textsearch_find() for continuous/linear data.
 374 + * Call textsearch_next() to retrieve subsequent matches.
 375 + *
 376 + * Returns the position of first occurrence of the pattern or
 377 + * UINT_MAX if no occurrence was found.
 378 + */
 379 +unsigned int textsearch_find_continuous(struct ts_config *conf,
 380 +                                       struct ts_state *state,
 381 +                                       const void *data, unsigned int len)
 382 +{
 383 +       struct ts_linear_state *st = (struct ts_linear_state *) state->cb;
 384 +
 385 +       conf->get_next_block = get_linear_data;
 386 +       st->data = data;
 387 +       st->len = len;
 388 +
 389 +       return textsearch_find(conf, state);
 390 +}
 391 +
 392 +/**
 393 + * textsearch_prepare - Prepare a search
 394 + * @algo: name of search algorithm
 395 + * @pattern: pattern data
 396 + * @len: length of pattern
 397 + * @gfp_mask: allocation mask
 398 + * @flags: search flags
 399 + *
 400 + * Looks up the search algorithm module and creates a new textsearch
 401 + * configuration for the specified pattern. Upon completion all
 402 + * necessary refcnts are held and the configuration must be put back
 403 + * using textsearch_put() after usage.
 404 + *
 405 + * Note: The format of the pattern may not be compatible between
 406 + *       the various search algorithms.
 407 + *
 408 + * Returns a new textsearch configuration according to the specified
 409 + *         parameters or a ERR_PTR().
 410 + */
 411 +struct ts_config *textsearch_prepare(const char *algo, const void *pattern,
 412 +                                    unsigned int len, gfp_t gfp_mask, int flags)
 413 +{
 414 +       int err = -ENOENT;
 415 +       struct ts_config *conf;
 416 +       struct ts_ops *ops;
 417 +
 418 +       ops = lookup_ts_algo(algo);
 419 +
 420 +       if (ops == NULL)
 421 +               goto errout;
 422 +
 423 +       conf = ops->init(pattern, len, gfp_mask);
 424 +       if (IS_ERR(conf)) {
 425 +               err = PTR_ERR(conf);
 426 +               goto errout;
 427 +       }
 428 +
 429 +       conf->ops = ops;
 430 +       return conf;
 431 +
 432 +errout:
 433 +       if (ops)
 434 +               MOD_DEC_USE_COUNT;
 435 +
 436 +       return ERR_PTR(err);
 437 +}
 438 +
 439 +/**
 440 + * textsearch_destroy - destroy a search configuration
 441 + * @conf: search configuration
 442 + *
 443 + * Releases all references of the configuration and frees
 444 + * up the memory.
 445 + */
 446 +void textsearch_destroy(struct ts_config *conf)
 447 +{
 448 +       if (conf->ops) {
 449 +               if (conf->ops->destroy)
 450 +                       conf->ops->destroy(conf);
 451 +               MOD_DEC_USE_COUNT;
 452 +       }
 453 +
 454 +       kfree(conf);
 455 +}
 456 +
 457 diff -urN linux.old/net/ipv4/netfilter/textsearch/textsearch.h linux.dev/net/ipv4/netfilter/textsearch/textsearch.h
 458 --- linux.old/net/ipv4/netfilter/textsearch/textsearch.h        1970-01-01 01:00:00.000000000 +0100
 459 +++ linux.dev/net/ipv4/netfilter/textsearch/textsearch.h        2006-11-14 02:11:59.000000000 +0100
 460 @@ -0,0 +1,182 @@
 461 +#ifndef __LINUX_TEXTSEARCH_H
 462 +#define __LINUX_TEXTSEARCH_H
 463 +
 464 +#ifdef __KERNEL__
 465 +
 466 +#include <linux/types.h>
 467 +#include <linux/list.h>
 468 +#include <linux/kernel.h>
 469 +#include <linux/module.h>
 470 +#include <linux/slab.h>
 471 +
 472 +typedef int gfp_t;
 473 +struct ts_config;
 474 +
 475 +/**
 476 + * TS_AUTOLOAD - Automatically load textsearch modules when needed
 477 + */
 478 +#define TS_AUTOLOAD    1
 479 +
 480 +/**
 481 + * struct ts_state - search state
 482 + * @offset: offset for next match
 483 + * @cb: control buffer, for persistant variables of get_next_block()
 484 + */
 485 +struct ts_state
 486 +{
 487 +       unsigned int            offset;
 488 +       char                    cb[40];
 489 +};
 490 +
 491 +/**
 492 + * struct ts_ops - search module operations
 493 + * @name: name of search algorithm
 494 + * @init: initialization function to prepare a search
 495 + * @find: find the next occurrence of the pattern
 496 + * @destroy: destroy algorithm specific parts of a search configuration
 497 + * @get_pattern: return head of pattern
 498 + * @get_pattern_len: return length of pattern
 499 + * @owner: module reference to algorithm
 500 + */
 501 +struct ts_ops
 502 +{
 503 +       const char              *name;
 504 +       struct ts_config *      (*init)(const void *, unsigned int, gfp_t);
 505 +       unsigned int            (*find)(struct ts_config *,
 506 +                                       struct ts_state *);
 507 +       void                    (*destroy)(struct ts_config *);
 508 +       void *                  (*get_pattern)(struct ts_config *);
 509 +       unsigned int            (*get_pattern_len)(struct ts_config *);
 510 +       struct module           *owner;
 511 +       struct list_head        list;
 512 +};
 513 +
 514 +/**
 515 + * struct ts_config - search configuration
 516 + * @ops: operations of chosen algorithm
 517 + * @get_next_block: callback to fetch the next block to search in
 518 + * @finish: callback to finalize a search
 519 + */
 520 +struct ts_config
 521 +{
 522 +       struct ts_ops           *ops;
 523 +
 524 +       /**
 525 +        * get_next_block - fetch next block of data
 526 +        * @consumed: number of bytes consumed by the caller
 527 +        * @dst: destination buffer
 528 +        * @conf: search configuration
 529 +        * @state: search state
 530 +        *
 531 +        * Called repeatedly until 0 is returned. Must assign the
 532 +        * head of the next block of data to &*dst and return the length
 533 +        * of the block or 0 if at the end. consumed == 0 indicates
 534 +        * a new search. May store/read persistant values in state->cb.
 535 +        */
 536 +       unsigned int            (*get_next_block)(unsigned int consumed,
 537 +                                                 const u8 **dst,
 538 +                                                 struct ts_config *conf,
 539 +                                                 struct ts_state *state);
 540 +
 541 +       /**
 542 +        * finish - finalize/clean a series of get_next_block() calls
 543 +        * @conf: search configuration
 544 +        * @state: search state
 545 +        *
 546 +        * Called after the last use of get_next_block(), may be used
 547 +        * to cleanup any leftovers.
 548 +        */
 549 +       void                    (*finish)(struct ts_config *conf,
 550 +                                         struct ts_state *state);
 551 +};
 552 +
 553 +/**
 554 + * textsearch_next - continue searching for a pattern
 555 + * @conf: search configuration
 556 + * @state: search state
 557 + *
 558 + * Continues a search looking for more occurrences of the pattern.
 559 + * textsearch_find() must be called to find the first occurrence
 560 + * in order to reset the state.
 561 + *
 562 + * Returns the position of the next occurrence of the pattern or
 563 + * UINT_MAX if not match was found.
 564 + */
 565 +static inline unsigned int textsearch_next(struct ts_config *conf,
 566 +                                          struct ts_state *state)
 567 +{
 568 +       unsigned int ret = conf->ops->find(conf, state);
 569 +
 570 +       if (conf->finish)
 571 +               conf->finish(conf, state);
 572 +
 573 +       return ret;
 574 +}
 575 +
 576 +/**
 577 + * textsearch_find - start searching for a pattern
 578 + * @conf: search configuration
 579 + * @state: search state
 580 + *
 581 + * Returns the position of first occurrence of the pattern or
 582 + * UINT_MAX if no match was found.
 583 + */
 584 +static inline unsigned int textsearch_find(struct ts_config *conf,
 585 +                                          struct ts_state *state)
 586 +{
 587 +       state->offset = 0;
 588 +       return textsearch_next(conf, state);
 589 +}
 590 +
 591 +/**
 592 + * textsearch_get_pattern - return head of the pattern
 593 + * @conf: search configuration
 594 + */
 595 +static inline void *textsearch_get_pattern(struct ts_config *conf)
 596 +{
 597 +       return conf->ops->get_pattern(conf);
 598 +}
 599 +
 600 +/**
 601 + * textsearch_get_pattern_len - return length of the pattern
 602 + * @conf: search configuration
 603 + */
 604 +static inline unsigned int textsearch_get_pattern_len(struct ts_config *conf)
 605 +{
 606 +       return conf->ops->get_pattern_len(conf);
 607 +}
 608 +
 609 +extern int textsearch_register(struct ts_ops *);
 610 +extern int textsearch_unregister(struct ts_ops *);
 611 +extern struct ts_config *textsearch_prepare(const char *, const void *,
 612 +                                           unsigned int, gfp_t, int);
 613 +extern void textsearch_destroy(struct ts_config *conf);
 614 +extern unsigned int textsearch_find_continuous(struct ts_config *,
 615 +                                              struct ts_state *,
 616 +                                              const void *, unsigned int);
 617 +
 618 +
 619 +#define TS_PRIV_ALIGNTO        8
 620 +#define TS_PRIV_ALIGN(len) (((len) + TS_PRIV_ALIGNTO-1) & ~(TS_PRIV_ALIGNTO-1))
 621 +
 622 +static inline struct ts_config *alloc_ts_config(size_t payload,
 623 +                                               gfp_t gfp_mask)
 624 +{
 625 +       struct ts_config *conf;
 626 +
 627 +       conf = kmalloc(TS_PRIV_ALIGN(sizeof(*conf)) + payload, gfp_mask);
 628 +       if (conf == NULL)
 629 +               return ERR_PTR(-ENOMEM);
 630 +
 631 +       memset(conf, 0, TS_PRIV_ALIGN(sizeof(*conf)) + payload);
 632 +       return conf;
 633 +}
 634 +
 635 +static inline void *ts_config_priv(struct ts_config *conf)
 636 +{
 637 +       return ((u8 *) conf + TS_PRIV_ALIGN(sizeof(struct ts_config)));
 638 +}
 639 +
 640 +#endif /* __KERNEL__ */
 641 +
 642 +#endif
 643 diff -urN linux.old/net/ipv4/netfilter/textsearch/ts_bm.c linux.dev/net/ipv4/netfilter/textsearch/ts_bm.c
 644 --- linux.old/net/ipv4/netfilter/textsearch/ts_bm.c     1970-01-01 01:00:00.000000000 +0100
 645 +++ linux.dev/net/ipv4/netfilter/textsearch/ts_bm.c     2006-11-14 02:22:20.000000000 +0100
 646 @@ -0,0 +1,190 @@
 647 +/*
 648 + * lib/ts_bm.c         Boyer-Moore text search implementation
 649 + *
 650 + *             This program is free software; you can redistribute it and/or
 651 + *             modify it under the terms of the GNU General Public License
 652 + *             as published by the Free Software Foundation; either version
 653 + *             2 of the License, or (at your option) any later version.
 654 + *
 655 + * Authors:    Pablo Neira Ayuso <pablo@eurodev.net>
 656 + *
 657 + * ==========================================================================
 658 + *
 659 + *   Implements Boyer-Moore string matching algorithm:
 660 + *
 661 + *   [1] A Fast String Searching Algorithm, R.S. Boyer and Moore.
 662 + *       Communications of the Association for Computing Machinery,
 663 + *       20(10), 1977, pp. 762-772.
 664 + *       http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
 665 + *
 666 + *   [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004
 667 + *       http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
 668 + *
 669 + *   Note: Since Boyer-Moore (BM) performs searches for matchings from right
 670 + *   to left, it's still possible that a matching could be spread over
 671 + *   multiple blocks, in that case this algorithm won't find any coincidence.
 672 + *
 673 + *   If you're willing to ensure that such thing won't ever happen, use the
 674 + *   Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose
 675 + *   the proper string search algorithm depending on your setting.
 676 + *
 677 + *   Say you're using the textsearch infrastructure for filtering, NIDS or
 678 + *   any similar security focused purpose, then go KMP. Otherwise, if you
 679 + *   really care about performance, say you're classifying packets to apply
 680 + *   Quality of Service (QoS) policies, and you don't mind about possible
 681 + *   matchings spread over multiple fragments, then go BM.
 682 + */
 683 +
 684 +#include <linux/config.h>
 685 +#include <linux/kernel.h>
 686 +#include <linux/module.h>
 687 +#include <linux/types.h>
 688 +#include <linux/string.h>
 689 +#include "textsearch.h"
 690 +
 691 +/* Alphabet size, use ASCII */
 692 +#define ASIZE 256
 693 +
 694 +#if 0
 695 +#define DEBUGP printk
 696 +#else
 697 +#define DEBUGP(args, format...)
 698 +#endif
 699 +
 700 +struct ts_bm
 701 +{
 702 +       u8 *            pattern;
 703 +       unsigned int    patlen;
 704 +       unsigned int    bad_shift[ASIZE];
 705 +       unsigned int    good_shift[0];
 706 +};
 707 +
 708 +static unsigned int bm_find(struct ts_config *conf, struct ts_state *state)
 709 +{
 710 +       struct ts_bm *bm = ts_config_priv(conf);
 711 +       unsigned int i, text_len, consumed = state->offset;
 712 +       const u8 *text;
 713 +       int shift = bm->patlen, bs;
 714 +
 715 +       for (;;) {
 716 +               text_len = conf->get_next_block(consumed, &text, conf, state);
 717 +
 718 +               if (unlikely(text_len == 0))
 719 +                       break;
 720 +
 721 +               while (shift < text_len) {
 722 +                       DEBUGP("Searching in position %d (%c)\n",
 723 +                               shift, text[shift]);
 724 +                       for (i = 0; i < bm->patlen; i++)
 725 +                            if (text[shift-i] != bm->pattern[bm->patlen-1-i])
 726 +                                    goto next;
 727 +
 728 +                       /* London calling... */
 729 +                       DEBUGP("found!\n");
 730 +                       return consumed += (shift-(bm->patlen-1));
 731 +
 732 +next:                  bs = bm->bad_shift[text[shift-i]];
 733 +
 734 +                       /* Now jumping to... */
 735 +                       shift = max_t(int, shift-i+bs, shift+bm->good_shift[i]);
 736 +               }
 737 +               consumed += text_len;
 738 +       }
 739 +
 740 +       return UINT_MAX;
 741 +}
 742 +
 743 +static int subpattern(u8 *pattern, int i, int j, int g)
 744 +{
 745 +       int x = i+g-1, y = j+g-1, ret = 0;
 746 +
 747 +       while(pattern[x--] == pattern[y--]) {
 748 +               if (y < 0) {
 749 +                       ret = 1;
 750 +                       break;
 751 +               }
 752 +               if (--g == 0) {
 753 +                       ret = pattern[i-1] != pattern[j-1];
 754 +                       break;
 755 +               }
 756 +       }
 757 +
 758 +       return ret;
 759 +}
 760 +
 761 +static void bm_compute_prefix_tbl(struct ts_bm *bm, const u8 *pattern,
 762 +                              unsigned int len)
 763 +{
 764 +       int i, j, g;
 765 +
 766 +       for (i = 0; i < ASIZE; i++)
 767 +               bm->bad_shift[i] = len;
 768 +       for (i = 0; i < len - 1; i++)
 769 +               bm->bad_shift[pattern[i]] = len - 1 - i;
 770 +
 771 +       /* Compute the good shift array, used to match reocurrences
 772 +        * of a subpattern */
 773 +       bm->good_shift[0] = 1;
 774 +       for (i = 1; i < bm->patlen; i++)
 775 +               bm->good_shift[i] = bm->patlen;
 776 +        for (i = bm->patlen-1, g = 1; i > 0; g++, i--) {
 777 +               for (j = i-1; j >= 1-g ; j--)
 778 +                       if (subpattern(bm->pattern, i, j, g)) {
 779 +                               bm->good_shift[g] = bm->patlen-j-g;
 780 +                               break;
 781 +                       }
 782 +       }
 783 +}
 784 +
 785 +static struct ts_config *bm_init(const void *pattern, unsigned int len,
 786 +                                gfp_t gfp_mask)
 787 +{
 788 +       struct ts_config *conf;
 789 +       struct ts_bm *bm;
 790 +       unsigned int prefix_tbl_len = len * sizeof(unsigned int);
 791 +       size_t priv_size = sizeof(*bm) + len + prefix_tbl_len;
 792 +
 793 +       conf = alloc_ts_config(priv_size, gfp_mask);
 794 +       if (IS_ERR(conf))
 795 +               return conf;
 796 +
 797 +       bm = ts_config_priv(conf);
 798 +       bm->patlen = len;
 799 +       bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;
 800 +       bm_compute_prefix_tbl(bm, pattern, len);
 801 +       memcpy(bm->pattern, pattern, len);
 802 +
 803 +       return conf;
 804 +}
 805 +
 806 +static void *bm_get_pattern(struct ts_config *conf)
 807 +{
 808 +       struct ts_bm *bm = ts_config_priv(conf);
 809 +       return bm->pattern;
 810 +}
 811 +
 812 +static unsigned int bm_get_pattern_len(struct ts_config *conf)
 813 +{
 814 +       struct ts_bm *bm = ts_config_priv(conf);
 815 +       return bm->patlen;
 816 +}
 817 +
 818 +static struct ts_ops bm_ops = {
 819 +       .name             = "bm",
 820 +       .find             = bm_find,
 821 +       .init             = bm_init,
 822 +       .get_pattern      = bm_get_pattern,
 823 +       .get_pattern_len  = bm_get_pattern_len,
 824 +       .owner            = THIS_MODULE,
 825 +       .list             = LIST_HEAD_INIT(bm_ops.list)
 826 +};
 827 +
 828 +static int __init init_bm(void)
 829 +{
 830 +       return textsearch_register(&bm_ops);
 831 +}
 832 +
 833 +static void __exit exit_bm(void)
 834 +{
 835 +       textsearch_unregister(&bm_ops);
 836 +}
 837 diff -urN linux.old/net/ipv4/netfilter/textsearch/ts_kmp.c linux.dev/net/ipv4/netfilter/textsearch/ts_kmp.c
 838 --- linux.old/net/ipv4/netfilter/textsearch/ts_kmp.c    1970-01-01 01:00:00.000000000 +0100
 839 +++ linux.dev/net/ipv4/netfilter/textsearch/ts_kmp.c    2006-11-14 02:22:04.000000000 +0100
 840 @@ -0,0 +1,141 @@
 841 +/*
 842 + * lib/ts_kmp.c                Knuth-Morris-Pratt text search implementation
 843 + *
 844 + *             This program is free software; you can redistribute it and/or
 845 + *             modify it under the terms of the GNU General Public License
 846 + *             as published by the Free Software Foundation; either version
 847 + *             2 of the License, or (at your option) any later version.
 848 + *
 849 + * Authors:    Thomas Graf <tgraf@suug.ch>
 850 + *
 851 + * ==========================================================================
 852 + *
 853 + *   Implements a linear-time string-matching algorithm due to Knuth,
 854 + *   Morris, and Pratt [1]. Their algorithm avoids the explicit
 855 + *   computation of the transition function DELTA altogether. Its
 856 + *   matching time is O(n), for n being length(text), using just an
 857 + *   auxiliary function PI[1..m], for m being length(pattern),
 858 + *   precomputed from the pattern in time O(m). The array PI allows
 859 + *   the transition function DELTA to be computed efficiently
 860 + *   "on the fly" as needed. Roughly speaking, for any state
 861 + *   "q" = 0,1,...,m and any character "a" in SIGMA, the value
 862 + *   PI["q"] contains the information that is independent of "a" and
 863 + *   is needed to compute DELTA("q", "a") [2]. Since the array PI
 864 + *   has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
 865 + *   save a factor of |SIGMA| in the preprocessing time by computing
 866 + *   PI rather than DELTA.
 867 + *
 868 + *   [1] Cormen, Leiserson, Rivest, Stein
 869 + *       Introdcution to Algorithms, 2nd Edition, MIT Press
 870 + *   [2] See finite automation theory
 871 + */
 872 +
 873 +#include <linux/config.h>
 874 +#include <linux/module.h>
 875 +#include <linux/types.h>
 876 +#include <linux/string.h>
 877 +#include "textsearch.h"
 878 +
 879 +struct ts_kmp
 880 +{
 881 +       u8 *            pattern;
 882 +       unsigned int    pattern_len;
 883 +       unsigned int    prefix_tbl[0];
 884 +};
 885 +
 886 +static unsigned int kmp_find(struct ts_config *conf, struct ts_state *state)
 887 +{
 888 +       struct ts_kmp *kmp = ts_config_priv(conf);
 889 +       unsigned int i, q = 0, text_len, consumed = state->offset;
 890 +       const u8 *text;
 891 +
 892 +       for (;;) {
 893 +               text_len = conf->get_next_block(consumed, &text, conf, state);
 894 +
 895 +               if (unlikely(text_len == 0))
 896 +                       break;
 897 +
 898 +               for (i = 0; i < text_len; i++) {
 899 +                       while (q > 0 && kmp->pattern[q] != text[i])
 900 +                               q = kmp->prefix_tbl[q - 1];
 901 +                       if (kmp->pattern[q] == text[i])
 902 +                               q++;
 903 +                       if (unlikely(q == kmp->pattern_len)) {
 904 +                               state->offset = consumed + i + 1;
 905 +                               return state->offset - kmp->pattern_len;
 906 +                       }
 907 +               }
 908 +
 909 +               consumed += text_len;
 910 +       }
 911 +
 912 +       return UINT_MAX;
 913 +}
 914 +
 915 +static inline void kmp_compute_prefix_tbl(const u8 *pattern, unsigned int len,
 916 +                                     unsigned int *prefix_tbl)
 917 +{
 918 +       unsigned int k, q;
 919 +
 920 +       for (k = 0, q = 1; q < len; q++) {
 921 +               while (k > 0 && pattern[k] != pattern[q])
 922 +                       k = prefix_tbl[k-1];
 923 +               if (pattern[k] == pattern[q])
 924 +                       k++;
 925 +               prefix_tbl[q] = k;
 926 +       }
 927 +}
 928 +
 929 +static struct ts_config *kmp_init(const void *pattern, unsigned int len,
 930 +                                 gfp_t gfp_mask)
 931 +{
 932 +       struct ts_config *conf;
 933 +       struct ts_kmp *kmp;
 934 +       unsigned int prefix_tbl_len = len * sizeof(unsigned int);
 935 +       size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len;
 936 +
 937 +       conf = alloc_ts_config(priv_size, gfp_mask);
 938 +       if (IS_ERR(conf))
 939 +               return conf;
 940 +
 941 +       kmp = ts_config_priv(conf);
 942 +       kmp->pattern_len = len;
 943 +       kmp_compute_prefix_tbl(pattern, len, kmp->prefix_tbl);
 944 +       kmp->pattern = (u8 *) kmp->prefix_tbl + prefix_tbl_len;
 945 +       memcpy(kmp->pattern, pattern, len);
 946 +
 947 +       return conf;
 948 +}
 949 +
 950 +static void *kmp_get_pattern(struct ts_config *conf)
 951 +{
 952 +       struct ts_kmp *kmp = ts_config_priv(conf);
 953 +       return kmp->pattern;
 954 +}
 955 +
 956 +static unsigned int kmp_get_pattern_len(struct ts_config *conf)
 957 +{
 958 +       struct ts_kmp *kmp = ts_config_priv(conf);
 959 +       return kmp->pattern_len;
 960 +}
 961 +
 962 +static struct ts_ops kmp_ops = {
 963 +       .name             = "kmp",
 964 +       .find             = kmp_find,
 965 +       .init             = kmp_init,
 966 +       .get_pattern      = kmp_get_pattern,
 967 +       .get_pattern_len  = kmp_get_pattern_len,
 968 +       .owner            = THIS_MODULE,
 969 +       .list             = LIST_HEAD_INIT(kmp_ops.list)
 970 +};
 971 +
 972 +static int __init init_kmp(void)
 973 +{
 974 +       return textsearch_register(&kmp_ops);
 975 +}
 976 +
 977 +static void __exit exit_kmp(void)
 978 +{
 979 +       textsearch_unregister(&kmp_ops);
 980 +}
 981 +