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

   1 --- linux/net/ipv4/netfilter/Config.in.org      2005-11-08 23:11:47.011929664 +0100
   2 +++ linux/net/ipv4/netfilter/Config.in  2005-11-08 23:10:33.329131152 +0100
   3 @@ -50,6 +50,7 @@
   4    fi
   5    if [ "$CONFIG_EXPERIMENTAL" = "y" ]; then
   6      dep_tristate '  Unclean match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_UNCLEAN $CONFIG_IP_NF_IPTABLES
   7 +    dep_tristate '  String match support (EXPERIMENTAL) ' CONFIG_IP_NF_MATCH_STRING $CONFIG_IP_NF_IPTABLES
   8      dep_tristate '  Owner match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_OWNER $CONFIG_IP_NF_IPTABLES
   9      dep_tristate '  Layer 7 match support (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_LAYER7 $CONFIG_IP_NF_CONNTRACK
  10      dep_mbool '  Layer 7 debugging output (EXPERIMENTAL)' CONFIG_IP_NF_MATCH_LAYER7_DEBUG $CONFIG_IP_NF_MATCH_LAYER7
  11 --- linux/net/ipv4/netfilter/Makefile.org       2005-11-08 23:11:57.214378656 +0100
  12 +++ linux/net/ipv4/netfilter/Makefile   2005-11-08 23:11:20.980886984 +0100
  13 @@ -97,6 +97,7 @@
  14  obj-$(CONFIG_IP_NF_MATCH_CONNBYTES) += ipt_connbytes.o
  15  obj-$(CONFIG_IP_NF_MATCH_CONNTRACK) += ipt_conntrack.o
  16  obj-$(CONFIG_IP_NF_MATCH_UNCLEAN) += ipt_unclean.o
  17 +obj-$(CONFIG_IP_NF_MATCH_STRING) += ipt_string.o
  18  obj-$(CONFIG_IP_NF_MATCH_TCPMSS) += ipt_tcpmss.o
  19
  20  obj-$(CONFIG_IP_NF_MATCH_LAYER7) += ipt_layer7.o
  21 --- linux/net/ipv4/netfilter/ipt_string.c       1970-01-01 01:00:00.000000000 +0100
  22 +++ linux/net/ipv4/netfilter/ipt_string.c       2005-11-08 23:08:51.531606728 +0100
  23 @@ -0,0 +1,218 @@
  24 +/* Kernel module to match a string into a packet.
  25 + *
  26 + * Copyright (C) 2000 Emmanuel Roger  <winfield@freegates.be>
  27 + *
  28 + * ChangeLog
  29 + *     19.02.2002: Gianni Tedesco <gianni@ecsc.co.uk>
  30 + *             Fixed SMP re-entrancy problem using per-cpu data areas
  31 + *             for the skip/shift tables.
  32 + *     02.05.2001: Gianni Tedesco <gianni@ecsc.co.uk>
  33 + *             Fixed kernel panic, due to overrunning boyer moore string
  34 + *             tables. Also slightly tweaked heuristic for deciding what
  35 + *             search algo to use.
  36 + *     27.01.2001: Gianni Tedesco <gianni@ecsc.co.uk>
  37 + *             Implemented Boyer Moore Sublinear search algorithm
  38 + *             alongside the existing linear search based on memcmp().
  39 + *             Also a quick check to decide which method to use on a per
  40 + *             packet basis.
  41 + */
  42 +
  43 +#include <linux/smp.h>
  44 +#include <linux/module.h>
  45 +#include <linux/skbuff.h>
  46 +#include <linux/file.h>
  47 +#include <net/sock.h>
  48 +
  49 +#include <linux/netfilter_ipv4/ip_tables.h>
  50 +#include <linux/netfilter_ipv4/ipt_string.h>
  51 +
  52 +MODULE_LICENSE("GPL");
  53 +
  54 +struct string_per_cpu {
  55 +       int *skip;
  56 +       int *shift;
  57 +       int *len;
  58 +};
  59 +
  60 +struct string_per_cpu *bm_string_data=NULL;
  61 +
  62 +/* Boyer Moore Sublinear string search - VERY FAST */
  63 +char *search_sublinear (char *needle, char *haystack, int needle_len, int haystack_len)
  64 +{
  65 +       int M1, right_end, sk, sh;
  66 +       int ended, j, i;
  67 +
  68 +       int *skip, *shift, *len;
  69 +
  70 +       /* use data suitable for this CPU */
  71 +       shift=bm_string_data[smp_processor_id()].shift;
  72 +       skip=bm_string_data[smp_processor_id()].skip;
  73 +       len=bm_string_data[smp_processor_id()].len;
  74 +
  75 +       /* Setup skip/shift tables */
  76 +       M1 = right_end = needle_len-1;
  77 +       for (i = 0; i < BM_MAX_HLEN; i++) skip[i] = needle_len;
  78 +       for (i = 0; needle[i]; i++) skip[needle[i]] = M1 - i;
  79 +
  80 +       for (i = 1; i < needle_len; i++) {
  81 +               for (j = 0; j < needle_len && needle[M1 - j] == needle[M1 - i - j]; j++);
  82 +               len[i] = j;
  83 +       }
  84 +
  85 +       shift[0] = 1;
  86 +       for (i = 1; i < needle_len; i++) shift[i] = needle_len;
  87 +       for (i = M1; i > 0; i--) shift[len[i]] = i;
  88 +       ended = 0;
  89 +
  90 +       for (i = 0; i < needle_len; i++) {
  91 +               if (len[i] == M1 - i) ended = i;
  92 +               if (ended) shift[i] = ended;
  93 +       }
  94 +
  95 +       /* Do the search*/
  96 +       while (right_end < haystack_len)
  97 +       {
  98 +               for (i = 0; i < needle_len && haystack[right_end - i] == needle[M1 - i]; i++);
  99 +               if (i == needle_len) {
 100 +                       return haystack+(right_end - M1);
 101 +               }
 102 +
 103 +               sk = skip[haystack[right_end - i]];
 104 +               sh = shift[i];
 105 +               right_end = max(right_end - i + sk, right_end + sh);
 106 +       }
 107 +
 108 +       return NULL;
 109 +}
 110 +
 111 +/* Linear string search based on memcmp() */
 112 +char *search_linear (char *needle, char *haystack, int needle_len, int haystack_len)
 113 +{
 114 +       char *k = haystack + (haystack_len-needle_len);
 115 +       char *t = haystack;
 116 +
 117 +       while ( t <= k ) {
 118 +               if (memcmp(t, needle, needle_len) == 0)
 119 +                       return t;
 120 +               t++;
 121 +       }
 122 +
 123 +       return NULL;
 124 +}
 125 +
 126 +
 127 +static int
 128 +match(const struct sk_buff *skb,
 129 +      const struct net_device *in,
 130 +      const struct net_device *out,
 131 +      const void *matchinfo,
 132 +      int offset,
 133 +      const void *hdr,
 134 +      u_int16_t datalen,
 135 +      int *hotdrop)
 136 +{
 137 +       const struct ipt_string_info *info = matchinfo;
 138 +       struct iphdr *ip = skb->nh.iph;
 139 +       int hlen, nlen;
 140 +       char *needle, *haystack;
 141 +       proc_ipt_search search=search_linear;
 142 +
 143 +       if ( !ip ) return 0;
 144 +
 145 +       /* get lenghts, and validate them */
 146 +       nlen=info->len;
 147 +       hlen=ntohs(ip->tot_len)-(ip->ihl*4);
 148 +       if ( nlen > hlen ) return 0;
 149 +
 150 +       needle=(char *)&info->string;
 151 +       haystack=(char *)ip+(ip->ihl*4);
 152 +
 153 +       /* The sublinear search comes in to its own
 154 +        * on the larger packets */
 155 +       if ( (hlen>IPT_STRING_HAYSTACK_THRESH) &&
 156 +               (nlen>IPT_STRING_NEEDLE_THRESH) ) {
 157 +               if ( hlen < BM_MAX_HLEN ) {
 158 +                       search=search_sublinear;
 159 +               }else{
 160 +                       if (net_ratelimit())
 161 +                               printk(KERN_INFO "ipt_string: Packet too big "
 162 +                                       "to attempt sublinear string search "
 163 +                                       "(%d bytes)\n", hlen );
 164 +               }
 165 +       }
 166 +
 167 +    return ((search(needle, haystack, nlen, hlen)!=NULL) ^ info->invert);
 168 +}
 169 +
 170 +static int
 171 +checkentry(const char *tablename,
 172 +           const struct ipt_ip *ip,
 173 +           void *matchinfo,
 174 +           unsigned int matchsize,
 175 +           unsigned int hook_mask)
 176 +{
 177 +
 178 +       if (matchsize != IPT_ALIGN(sizeof(struct ipt_string_info)))
 179 +               return 0;
 180 +
 181 +       return 1;
 182 +}
 183 +
 184 +void string_freeup_data(void)
 185 +{
 186 +       int c;
 187 +
 188 +       if ( bm_string_data ) {
 189 +               for(c=0; c<smp_num_cpus; c++) {
 190 +                       if ( bm_string_data[c].shift ) kfree(bm_string_data[c].shift);
 191 +                       if ( bm_string_data[c].skip ) kfree(bm_string_data[c].skip);
 192 +                       if ( bm_string_data[c].len ) kfree(bm_string_data[c].len);
 193 +               }
 194 +               kfree(bm_string_data);
 195 +       }
 196 +}
 197 +
 198 +static struct ipt_match string_match
 199 += { { NULL, NULL }, "string", &match, &checkentry, NULL, THIS_MODULE };
 200 +
 201 +static int __init init(void)
 202 +{
 203 +       int c;
 204 +       size_t tlen;
 205 +       size_t alen;
 206 +
 207 +       tlen=sizeof(struct string_per_cpu)*smp_num_cpus;
 208 +       alen=sizeof(int)*BM_MAX_HLEN;
 209 +
 210 +       /* allocate array of structures */
 211 +       if ( !(bm_string_data=kmalloc(tlen,GFP_KERNEL)) ) {
 212 +               return 0;
 213 +       }
 214 +
 215 +       memset(bm_string_data, 0, tlen);
 216 +
 217 +       /* allocate our skip/shift tables */
 218 +       for(c=0; c<smp_num_cpus; c++) {
 219 +               if ( !(bm_string_data[c].shift=kmalloc(alen, GFP_KERNEL)) )
 220 +                       goto alloc_fail;
 221 +               if ( !(bm_string_data[c].skip=kmalloc(alen, GFP_KERNEL)) )
 222 +                       goto alloc_fail;
 223 +               if ( !(bm_string_data[c].len=kmalloc(alen, GFP_KERNEL)) )
 224 +                       goto alloc_fail;
 225 +       }
 226 +
 227 +       return ipt_register_match(&string_match);
 228 +
 229 +alloc_fail:
 230 +       string_freeup_data();
 231 +       return 0;
 232 +}
 233 +
 234 +static void __exit fini(void)
 235 +{
 236 +       ipt_unregister_match(&string_match);
 237 +       string_freeup_data();
 238 +}
 239 +
 240 +module_init(init);
 241 +module_exit(fini);
 242 --- linux/include/linux/netfilter_ipv4/ipt_string.h     1970-01-01 01:00:00.000000000 +0100
 243 +++ linux/include/linux/netfilter_ipv4/ipt_string.h     2005-11-08 23:09:45.219444936 +0100
 244 @@ -0,0 +1,21 @@
 245 +#ifndef _IPT_STRING_H
 246 +#define _IPT_STRING_H
 247 +
 248 +/* *** PERFORMANCE TWEAK ***
 249 + * Packet size and search string threshold,
 250 + * above which sublinear searches is used. */
 251 +#define IPT_STRING_HAYSTACK_THRESH     100
 252 +#define IPT_STRING_NEEDLE_THRESH       20
 253 +
 254 +#define BM_MAX_NLEN 256
 255 +#define BM_MAX_HLEN 1024
 256 +
 257 +typedef char *(*proc_ipt_search) (char *, char *, int, int);
 258 +
 259 +struct ipt_string_info {
 260 +    char string[BM_MAX_NLEN];
 261 +    u_int16_t invert;
 262 +    u_int16_t len;
 263 +};
 264 +
 265 +#endif /* _IPT_STRING_H */