[PATCH pom-ng] string match on 2.6 kernel

[PATCH pom-ng] string match on 2.6 kernel

[Anatoly Pugachev]

[-- Attachment #1.1: Type: text/plain, Size: 467 bytes --]

This kernel-2.6 patch is over cvs version of patch-o-matic, i'm used patch-o-
matic-ng-20050316. Since i'm not a kernel programmer, this patch isn't SMP
clean - noticed this in string/linux-2.6/info. 
'diff -ru string/linux string/linux-2.6' for my changes over original sources. 
Someone please fix my lameness.

I've tested it over my linux 2.6.10 kernel and it "works for me".

PS: maybe smp_num_cpus = num_booting_cpus() can help?
-- 
Anatoly Pugachev

[-- Attachment #1.2: pom-string-kernel26-no-SMP-clean.patch --]
[-- Type: text/plain, Size: 9075 bytes --]

diff -ruN patch-o-matic-ng-20050316/string/help pom/string/help
--- patch-o-matic-ng-20050316/string/help	2003-12-18 21:47:52.000000000 +0300
+++ pom/string/help	2005-03-18 19:58:44.000000000 +0300
@@ -4,3 +4,6 @@
 
 THIS PATCH DOES NOT WORK WITH KERNEL 2.4.9 !!!
 
+ Doesn't work with SMP kernel 2.6.x
+
+Usage example:
+# iptables -A INPUT -m string --string 'cmd.exe' -j QUEUE
+
diff -ruN patch-o-matic-ng-20050316/string/info pom/string/info
--- patch-o-matic-ng-20050316/string/info	2005-02-21 23:05:18.000000000 +0300
+++ pom/string/info	2005-03-17 10:20:56.000000000 +0300
@@ -2,4 +2,3 @@
 Author: Emmanuel Roger <winfield@freegates.be>
 Status: Working, not with kernel 2.4.9
 Repository: extra
-Requires: linux < 2.6.0
diff -ruN patch-o-matic-ng-20050316/string/linux-2.6/include/linux/netfilter_ipv4/ipt_string.h pom/string/linux-2.6/include/linux/netfilter_ipv4/ipt_string.h
--- patch-o-matic-ng-20050316/string/linux-2.6/include/linux/netfilter_ipv4/ipt_string.h	1970-01-01 03:00:00.000000000 +0300
+++ pom/string/linux-2.6/include/linux/netfilter_ipv4/ipt_string.h	2003-12-18 21:47:52.000000000 +0300
@@ -0,0 +1,21 @@
+#ifndef _IPT_STRING_H
+#define _IPT_STRING_H
+
+/* *** PERFORMANCE TWEAK ***
+ * Packet size and search string threshold,
+ * above which sublinear searches is used. */
+#define IPT_STRING_HAYSTACK_THRESH	100
+#define IPT_STRING_NEEDLE_THRESH	20
+
+#define BM_MAX_NLEN 256
+#define BM_MAX_HLEN 1024
+
+typedef char *(*proc_ipt_search) (char *, char *, int, int);
+
+struct ipt_string_info {
+    char string[BM_MAX_NLEN];
+    u_int16_t invert;
+    u_int16_t len;
+};
+
+#endif /* _IPT_STRING_H */
diff -ruN patch-o-matic-ng-20050316/string/linux-2.6/net/ipv4/netfilter/ipt_string.c pom/string/linux-2.6/net/ipv4/netfilter/ipt_string.c
--- patch-o-matic-ng-20050316/string/linux-2.6/net/ipv4/netfilter/ipt_string.c	1970-01-01 03:00:00.000000000 +0300
+++ pom/string/linux-2.6/net/ipv4/netfilter/ipt_string.c	2005-03-17 11:24:43.000000000 +0300
@@ -0,0 +1,223 @@
+/* Kernel module to match a string into a packet.
+ *
+ * Copyright (C) 2000 Emmanuel Roger  <winfield@freegates.be>
+ * 
+ * ChangeLog
+ *	19.02.2002: Gianni Tedesco <gianni@ecsc.co.uk>
+ *		Fixed SMP re-entrancy problem using per-cpu data areas
+ *		for the skip/shift tables.
+ *	02.05.2001: Gianni Tedesco <gianni@ecsc.co.uk>
+ *		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 <gianni@ecsc.co.uk>
+ * 		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 <linux/smp.h>
+#include <linux/module.h>
+#include <linux/skbuff.h>
+#include <linux/file.h>
+#include <net/sock.h>
+
+#include <linux/netfilter_ipv4/ip_tables.h>
+#include <linux/netfilter_ipv4/ipt_string.h>
+
+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 ) {
+#if defined(CONFIG_SMP)
+		for(c=0; c<smp_num_cpus; c++) {
+			if ( bm_string_data[c].shift ) kfree(bm_string_data[c].shift);
+			if ( bm_string_data[c].skip ) kfree(bm_string_data[c].skip);
+			if ( bm_string_data[c].len ) kfree(bm_string_data[c].len);
+		}
+#endif
+		kfree(bm_string_data);
+	}
+}
+
+static struct ipt_match string_match
+= { { NULL, NULL }, "string", &match, &checkentry, NULL, THIS_MODULE };
+
+static int __init init(void)
+{
+	int c;
+	size_t tlen;
+	size_t alen;
+
+#ifndef CONFIG_SMP
+  #define smp_num_cpus 1
+#endif
+	tlen=sizeof(struct string_per_cpu)*smp_num_cpus;
+	alen=sizeof(int)*BM_MAX_HLEN;
+	
+	/* allocate array of structures */
+	if ( !(bm_string_data=kmalloc(tlen,GFP_KERNEL)) ) {
+		return 0;
+	}
+	
+	memset(bm_string_data, 0, tlen);
+	
+	/* allocate our skip/shift tables */
+	for(c=0; c<smp_num_cpus; c++) {
+		if ( !(bm_string_data[c].shift=kmalloc(alen, GFP_KERNEL)) )
+			goto alloc_fail;
+		if ( !(bm_string_data[c].skip=kmalloc(alen, GFP_KERNEL)) )
+			goto alloc_fail;
+		if ( !(bm_string_data[c].len=kmalloc(alen, GFP_KERNEL)) )
+			goto alloc_fail;
+	}
+	
+	return ipt_register_match(&string_match);
+
+alloc_fail:
+	string_freeup_data();
+	return 0;
+}
+
+static void __exit fini(void)
+{
+	ipt_unregister_match(&string_match);
+	string_freeup_data();
+}
+
+module_init(init);
+module_exit(fini);
diff -ruN patch-o-matic-ng-20050316/string/linux-2.6/net/ipv4/netfilter/Kconfig.ladd pom/string/linux-2.6/net/ipv4/netfilter/Kconfig.ladd
--- patch-o-matic-ng-20050316/string/linux-2.6/net/ipv4/netfilter/Kconfig.ladd	1970-01-01 03:00:00.000000000 +0300
+++ pom/string/linux-2.6/net/ipv4/netfilter/Kconfig.ladd	2004-05-06 17:45:43.000000000 +0400
@@ -0,0 +1,9 @@
+config IP_NF_MATCH_STRING
+	tristate  'String match support'
+	depends on IP_NF_IPTABLES
+	help
+	  String matching alows you to match packets which contain a
+	  specified string of characters.
+	
+	  If you want to compile it as a module, say M here and read
+	  Documentation/modules.txt.  If unsure, say `N'.
diff -ruN patch-o-matic-ng-20050316/string/linux-2.6/net/ipv4/netfilter/Makefile.ladd pom/string/linux-2.6/net/ipv4/netfilter/Makefile.ladd
--- patch-o-matic-ng-20050316/string/linux-2.6/net/ipv4/netfilter/Makefile.ladd	1970-01-01 03:00:00.000000000 +0300
+++ pom/string/linux-2.6/net/ipv4/netfilter/Makefile.ladd	2005-03-17 12:35:01.000000000 +0300
@@ -0,0 +1,2 @@
+obj-$(CONFIG_IP_NF_MATCH_HELPER) += ipt_helper.o
+obj-$(CONFIG_IP_NF_MATCH_STRING) += ipt_string.o

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH pom-ng] string match on 2.6 kernel

[Pablo Neira]

Hi,

Anatoly Pugachev wrote:
> This kernel-2.6 patch is over cvs version of patch-o-matic, i'm used patch-o-
> matic-ng-20050316. Since i'm not a kernel programmer, this patch isn't SMP
> clean - noticed this in string/linux-2.6/info. 

Current string matching support in pom-ng has several problems:

o Boyer-Moore shifts are calculated every time a packets hits the match, 
this is not necessary. This increases the constants hidden in the O-big 
notation.
o As you pointed out, it's neither SMP nor preemptible safe. Per-cpu 
stuff is not the way to do this.

I've got a brand new infrastructure for string matching that I posted 
during xmas. As soon as I get some spare time I'll be back on it.

--
Pablo