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

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