From 4aca87515a5083ae0e31ce3177189fd43b6d05ac Mon Sep 17 00:00:00 2001 From: Andreas Baumann Date: Sat, 3 Jan 2015 13:58:15 +0100 Subject: patch to Vanilla Tomato 1.28 --- .../linux/linux/net/ipv4/netfilter/ipt_string.c | 218 +++++++++++++++++++++ 1 file changed, 218 insertions(+) create mode 100644 release/src/linux/linux/net/ipv4/netfilter/ipt_string.c (limited to 'release/src/linux/linux/net/ipv4/netfilter/ipt_string.c') diff --git a/release/src/linux/linux/net/ipv4/netfilter/ipt_string.c b/release/src/linux/linux/net/ipv4/netfilter/ipt_string.c new file mode 100644 index 00000000..a18b89d0 --- /dev/null +++ b/release/src/linux/linux/net/ipv4/netfilter/ipt_string.c @@ -0,0 +1,218 @@ +/* Kernel module to match a string into a packet. + * + * Copyright (C) 2000 Emmanuel Roger + * + * ChangeLog + * 19.02.2002: Gianni Tedesco + * Fixed SMP re-entrancy problem using per-cpu data areas + * for the skip/shift tables. + * 02.05.2001: Gianni Tedesco + * Fixed kernel panic, due to overrunning boyer moore string + * tables. Also slightly tweaked heuristic for deciding what + * search algo to use. + * 27.01.2001: Gianni Tedesco + * Implemented Boyer Moore Sublinear search algorithm + * alongside the existing linear search based on memcmp(). + * Also a quick check to decide which method to use on a per + * packet basis. + */ + +#include +#include +#include +#include +#include + +#include +#include + +MODULE_LICENSE("GPL"); + +struct string_per_cpu { + int *skip; + int *shift; + int *len; +}; + +struct string_per_cpu *bm_string_data=NULL; + +/* Boyer Moore Sublinear string search - VERY FAST */ +char *search_sublinear (char *needle, char *haystack, int needle_len, int haystack_len) +{ + int M1, right_end, sk, sh; + int ended, j, i; + + int *skip, *shift, *len; + + /* use data suitable for this CPU */ + shift=bm_string_data[smp_processor_id()].shift; + skip=bm_string_data[smp_processor_id()].skip; + len=bm_string_data[smp_processor_id()].len; + + /* Setup skip/shift tables */ + M1 = right_end = needle_len-1; + for (i = 0; i < BM_MAX_HLEN; i++) skip[i] = needle_len; + for (i = 0; needle[i]; i++) skip[needle[i]] = M1 - i; + + for (i = 1; i < needle_len; i++) { + for (j = 0; j < needle_len && needle[M1 - j] == needle[M1 - i - j]; j++); + len[i] = j; + } + + shift[0] = 1; + for (i = 1; i < needle_len; i++) shift[i] = needle_len; + for (i = M1; i > 0; i--) shift[len[i]] = i; + ended = 0; + + for (i = 0; i < needle_len; i++) { + if (len[i] == M1 - i) ended = i; + if (ended) shift[i] = ended; + } + + /* Do the search*/ + while (right_end < haystack_len) + { + for (i = 0; i < needle_len && haystack[right_end - i] == needle[M1 - i]; i++); + if (i == needle_len) { + return haystack+(right_end - M1); + } + + sk = skip[haystack[right_end - i]]; + sh = shift[i]; + right_end = max(right_end - i + sk, right_end + sh); + } + + return NULL; +} + +/* Linear string search based on memcmp() */ +char *search_linear (char *needle, char *haystack, int needle_len, int haystack_len) +{ + char *k = haystack + (haystack_len-needle_len); + char *t = haystack; + + while ( t <= k ) { + if (memcmp(t, needle, needle_len) == 0) + return t; + t++; + } + + return NULL; +} + + +static int +match(const struct sk_buff *skb, + const struct net_device *in, + const struct net_device *out, + const void *matchinfo, + int offset, + const void *hdr, + u_int16_t datalen, + int *hotdrop) +{ + const struct ipt_string_info *info = matchinfo; + struct iphdr *ip = skb->nh.iph; + int hlen, nlen; + char *needle, *haystack; + proc_ipt_search search=search_linear; + + if ( !ip ) return 0; + + /* get lenghts, and validate them */ + nlen=info->len; + hlen=ntohs(ip->tot_len)-(ip->ihl*4); + if ( nlen > hlen ) return 0; + + needle=(char *)&info->string; + haystack=(char *)ip+(ip->ihl*4); + + /* The sublinear search comes in to its own + * on the larger packets */ + if ( (hlen>IPT_STRING_HAYSTACK_THRESH) && + (nlen>IPT_STRING_NEEDLE_THRESH) ) { + if ( hlen < BM_MAX_HLEN ) { + search=search_sublinear; + }else{ + if (net_ratelimit()) + printk(KERN_INFO "ipt_string: Packet too big " + "to attempt sublinear string search " + "(%d bytes)\n", hlen ); + } + } + + return ((search(needle, haystack, nlen, hlen)!=NULL) ^ info->invert); +} + +static int +checkentry(const char *tablename, + const struct ipt_ip *ip, + void *matchinfo, + unsigned int matchsize, + unsigned int hook_mask) +{ + + if (matchsize != IPT_ALIGN(sizeof(struct ipt_string_info))) + return 0; + + return 1; +} + +void string_freeup_data(void) +{ + int c; + + if ( bm_string_data ) { + for(c=0; c