RFC: fast string matching infrastrure for netfilter

Hi,

I've finished a first usable version of a infrastructure to look for matchings in a packet. Features:

* A library consisting in three public functions: constructor, destructor and searching.
* Boyer-moore algorithm to perform fast matchings.
* Brute force search on the edges of two fragments to look for fragmented matches, that is O(m) searchs where m is the size of the pattern, it's not that bad for small pattern I think. It's fragment aware by means of rusty's skb_iter functions.

Comments welcome.

Signature · 4 lines

-- 
Pablo

------------------------------------------------------------------------

net/ipv4/netfilter/nf_string_match.c new file +77 -0

@@ -0,0 +1,264 @@
+/* Efficient string matching fragment aware infrastrure for netfilter
+ * Copyright (C) 2004 Pablo Neira Ayuso <[email protected]>
+ *
+ *      This program is free software; you can redistribute it and/or
+ *      modify it under the terms of the GNU General Public License
+ *      as published by the Free Software Foundation; either version
+ *      2 of the License, or (at your option) any later version.
+ *
+ * Idea:
+ * 	
+ * 	This algorithm used Boyer-Moore fast matching algorithm to look
+ * 	for a pattern in the payload of a packet. Since it is fragment
+ * 	aware, it looks for partial matches on the edges of two fragments.
+ *
+ * Literature:
+ * 
+ *      A Fast String Searching Algorithm, R.S. Boyer and Moore.
+ *      Communications of the Association for Computing Machinery, 
+ *      20(10), 1977, pp. 762-772.
+ *	http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
+ *
+ * 	Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004
+ * 	http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
+ * 
+ * Implementation:
+ * 
+ * 	Boyer Moore implementation heavily based on Gianni Tedesco's.
+ */
+
+#include <linux/module.h>
+#include <linux/netfilter_ipv4/nf_string_match.h>
+#include <linux/skbuff.h>
+
+#if 0
+#define DEBUGP printk
+#else
+#define DEBUGP(format, args...)
+#endif
+
+/* Compute constant structures needed by the boyer-moore algorithm,
+ * this is done just ONCE. */
+static void
+sm_preprocess(struct nf_string_match *sm)
+{
+	int i, j, len[ASIZE], ended;
+
+	/* Compute the bad caracter shift array */
+	for (i = 0; i < ASIZE; i++)
+		sm->badshift[i] = sm->patlen;
+	for (i = 0; i < sm->patlen - 1; i++)
+		sm->badshift[(int) sm->pat[i]] = sm->patlen - 1 - i;
+
+	/* Compute the good shift array, used to match reocurrences 
+	 * of a subpattern */
+	for (i = 1; i < sm->patlen; i++) {
+		for (j = 0; j < sm->patlen && sm->pat[sm->patlen -1 - j] 
+				== sm->pat[sm->patlen - 1 - i - j]; j++);
+		len[i] = j;
+	}  
+
+	sm->goodshift[0] = 1;
+	for (i = 1; i < sm->patlen; i++)
+		sm->goodshift[i] = sm->patlen;
+	for (i = sm->patlen - 1; i > 0; i--)
+		sm->goodshift[len[i]] = i;
+
+	ended = 0;
+	for (i = 0; i < sm->patlen; i++) {
+		if (len[i] == sm->patlen - 1 - i)
+			ended = i;
+		if (ended)
+			sm->goodshift[i] = ended;
+	}
+}
+
+struct nf_string_match *
+nf_string_match_create(const char *pat, int patlen)

net/ipv4/netfilter/nf_string_match.c new file +156 -0

+		kfree(sm->goodshift);
+		return NULL;
+	}
+	memset(sm->pat, patlen, sizeof(char) * patlen);
+	
+	strcpy(sm->pat, pat);
+	sm->patlen = patlen;
+
+	/* Preprocess the pattern */
+	sm_preprocess(sm);
+
+	return sm;
+}
+
+/* release the structure */
+void nf_string_match_destroy(struct nf_string_match *sm)
+{
+	kfree(sm->goodshift);
+	kfree(sm->pat);
+	kfree(sm);
+}
+
+#define MAX(a,b) a>b?a:b
+
+/* this functions returns the offset where a matching was found */
+static unsigned int
+sm_search(struct nf_string_match *sm, unsigned char *data, int size, 
+	  unsigned int *offset)
+{
+	int right_end = sm->patlen, sk, sh, i;
+
+	while (right_end < size) {
+		DEBUGP("Searching in position %d (%c)\n", 
+		       right_end, data[right_end]);
+		for (i = 0; i < sm->patlen && data[right_end - i] 
+				== sm->pat[sm->patlen - 1 - i]; i++);
+		if (i == sm->patlen) {
+			/* London calling... */
+			DEBUGP("found!\n");
+			*offset += (right_end - (sm->patlen - 1));
+			return 1;
+		}
+		
+		sk = sm->badshift[data[right_end - i]];  
+		sh = sm->goodshift[i];
+		DEBUGP("bad shift: %d good shift: %d\n", sk, sh);
+
+		/* Now jumping to... */
+		right_end = MAX(right_end - i + sk, right_end + sh);
+	}
+	*offset += size;
+	return 0;
+}
+
+/* Brute force: look for a partial matching at the end of the packet.
+ * A match never hits here, it's impossible. */
+static void
+sm_frag_search_end(struct nf_string_match *sm, void *ptr, int size, 
+		   int *partial)
+{
+	int i;
+	unsigned char *data = ptr + size - sm->patlen;
+
+	for (i=0; i < sm->patlen; i++) {
+		DEBUGP("end: %c == %c (%d)\n", data[i], 
+			sm->pat[*partial], *partial);
+		
+		if (data[i] == sm->pat[*partial])
+			(*partial)++;
+		else {
+			if (data[i] == sm->pat[0])
+				*partial = 1;
+			else 
+				*partial = 0;
+		}
+	}
+	DEBUGP("sm->partial:%d\n", *partial);
+}
+
+/* Brute force: Look for a matching at the beginning. Yes, here
+ * we can hit a full match */
+static int
+sm_frag_search_begin(struct nf_string_match *sm, void *ptr, int size, 
+		     unsigned int *offset, int *partial)
+{
+	int i, j = sm->patlen - *partial;
+	unsigned char *data = (unsigned char *) ptr;
+
+	for (i=0; i<j; i++) {
+		DEBUGP("begin: %c == %c (%d)\n", data[i],
+			sm->pat[*partial], *partial);
+
+		if (data[i] == sm->pat[*partial])
+			(*partial)++;
+		else
+			*partial = 0;
+	}
+
+	if (*partial == sm->patlen) {
+		DEBUGP("Fragmented match!\n");
+		*offset += i;
+		return 1;
+	}
+
+	/* No matching founds, so reset counter */
+	*partial = 0;
+
+	return 0;
+}
+
+static inline int
+frag_search(void *data, int size, struct nf_string_match *sm, 
+	    unsigned int *offset, int *partial)
+{
+	/* There was a partial match before */
+	if (sm_frag_search_begin(sm, data, size, offset, partial))
+		return 1;
+
+	if (sm_search(sm, data, size, offset))
+		return 1;
+
+	sm_frag_search_end(sm, data, size, partial);
+
+	return 0;
+}
+
+int
+nf_string_match_search(const struct sk_buff *skb, struct nf_string_match *sm,
+		       unsigned int *offset)
+{
+	/* make sure offset is always set to zero */
+	*offset = 0;
+
+	if (!skb_is_nonlinear(skb)) {
+		DEBUGP("linear searching\n");
+		/* General case: look for pattern in linear packet */
+		if (sm_search(sm, skb->data, skb->len, offset))
+			return 1;
+	} else {
+		/* The packet is fragmented */
+		struct skb_iter i;
+		int partial = 0;
+
+		DEBUGP("non linear searching\n");
+
+		/* Look for the pattern in first fragment */
+		skb_iter_first(skb, &i);
+		if (frag_search(i.data, i.len, sm, offset, &partial))
+			return 1;
+
+		/* Now, the rest of fragments ... */
+		while (skb_iter_next(skb, &i)) {
+			DEBUGP("%p (size:%d)\n", i.data, i.len);
+			if (frag_search(i.data, i.len, sm, offset, &partial))
+				return 1;
+		}

net/ipv4/netfilter/nf_string_match.c new file +6 -0

+
+MODULE_LICENSE("GPL");
+
+EXPORT_SYMBOL_GPL(nf_string_match_create);
+EXPORT_SYMBOL_GPL(nf_string_match_search);
+EXPORT_SYMBOL_GPL(nf_string_match_destroy);

include/linux/netfilter_ipv4/nf_string_match.h new file +24 -0

@@ -0,0 +1,24 @@
+#ifndef _STRING_MATCHING_H
+#define _STRING_MATCHING_H
+
+#include <linux/skbuff.h>
+
+/* Alphabet size */
+#define ASIZE 256
+
+struct nf_string_match {
+	char 		*pat;
+	int 		patlen;
+
+	int 		badshift[ASIZE];
+	int 		*goodshift;
+};
+
+extern struct nf_string_match *
+nf_string_match_create(const char *pat, int patlen);
+extern int nf_string_match_search(const struct sk_buff *skb, 
+				  struct nf_string_match *sm,
+				  unsigned int *offset);
+extern void nf_string_match_destroy(struct nf_string_match *sm);
+
+#endif

Quoted 5 lines

I've finished a first usable version of a infrastructure to look for matchings in a packet. Features:

* A library consisting in three public functions: constructor, destructor and searching.
* Boyer-moore algorithm to perform fast matchings.
* Brute force search on the edges of two fragments to look for fragmented matches, that is O(m) searchs where m is the size of the pattern, it's not that bad for small pattern I think. It's fragment aware by means of rusty's skb_iter functions.

Looks good. A problem is that it's only in-tree user is part of ip_conntrack. I have actually given up keeping nf_conntrack up to date currently, but I hope we can now really put ip_conntrack in maintenance mode and concentrate on nf_conntrack. Any chance you want to base this on the nf_conntrack patch ?

Quoted 1 line

Comments welcome.

See below.

net/ipv4/netfilter/nf_string_match.c new file +0 -0

net/ipv4/netfilter/nf_string_match.c new file +11 -0

+struct nf_string_match *
+nf_string_match_create(const char *pat, int patlen)
+{
+	struct nf_string_match *sm;
+
+	sm = kmalloc(sizeof(struct nf_string_match), GFP_KERNEL);
+	if (!sm)
+		return NULL;
+	memset(sm, 0, sizeof(struct nf_string_match));
+
+	sm->goodshift = (int *) kmalloc(patlen * sizeof(int), GFP_KERNEL);

net/ipv4/netfilter/nf_string_match.c new file +10 -0

+	
+	strcpy(sm->pat, pat);
+	sm->patlen = patlen;
+
+	/* Preprocess the pattern */
+	sm_preprocess(sm);
+
+	return sm;
+}
+

Hi,

I've finished a first usable version of a infrastructure to look for matchings in a packet. Features:

* A library consisting in three public functions: constructor, destructor and searching.

Pablo

I have actually given up keeping nf_conntrack up to date currently, but I hope we can now really put ip_conntrack in maintenance mode and concentrate
on nf_conntrack. Any chance you want to base this on the nf_conntrack patch ?

Quoted 6 lines · Patrick McHardy

I have actually given up keeping nf_conntrack up to date currently, but I hope we can now really put ip_conntrack in maintenance mode and concentrate
on nf_conntrack. Any chance you want to base this on the nf_conntrack patch ?

Actually, what is the opinion that nf_conntrack uses the union of IPv4 and IPv6 addresses in the tuples?

The infrastructure is there in the patch to support IPv4/IPv6 conntrack separatedly in spite of the common code and not to waste so many bytes at every IPv4 connections for the sake of supporting IPv6.

Shouldn't there be
put more effort into this long standing issue, before swithcing over it?

Quoted 6 lines

I have actually given up keeping nf_conntrack up to date currently, but I hope we can now really put ip_conntrack in maintenance mode and concentrate
on nf_conntrack. Any chance you want to base this on the nf_conntrack patch ?

Actually, what is the opinion that nf_conntrack uses the union of IPv4 and IPv6 addresses in the tuples?

Jozsef

Quoted 3 lines

Actually, what is the opinion that nf_conntrack uses the union of IPv4 and IPv6 addresses in the tuples?

In my opinion that's something that could also be improved later.

Quoted 3 lines

The infrastructure is there in the patch to support IPv4/IPv6 conntrack separatedly in spite of the common code and not to waste so many bytes at every IPv4 connections for the sake of supporting IPv6.

You mean the get_features stuff and seperate caches ? I'm don't like this part very much, I thing Rusty's "structure extension stuff" (ct_extend) is a nicer way to do this, although its probably not useable for the tuples.

I think we should put ip_conntrack in maintenance mode, than we can resync nf_conntrack and make changes like this before we submit it.

Quoted 18 lines

net/ipv4/netfilter/nf_string_match.c new file +18 -0

+struct nf_string_match *
+nf_string_match_create(const char *pat, int patlen)
+{
+	struct nf_string_match *sm;
+
+	sm = kmalloc(sizeof(struct nf_string_match), GFP_KERNEL);
+	if (!sm)
+		return NULL;
+	memset(sm, 0, sizeof(struct nf_string_match));
+
+	sm->goodshift = (int *) kmalloc(patlen * sizeof(int), GFP_KERNEL);
+	if (!sm->goodshift)
+		return NULL;
+	memset(sm->goodshift, 0, sizeof(int) * patlen);
+	
+	sm->pat = (char *) kmalloc(patlen * sizeof(int), GFP_KERNEL);
+	if (!sm->pat) {
+		kfree(sm->goodshift);

net/ipv4/netfilter/nf_string_match.c line 96

Quoted 5 lines

net/ipv4/netfilter/nf_string_match.c new file +3 -0

+		return NULL;
+	}
+	memset(sm->pat, patlen, sizeof(char) * patlen);

is there any intention behind kmalloc()ing the pattern using sizeof(int) and then memset()ting it using sizeof(char)?

Quoted 10 lines · Patrick McHardy

Quoted 5 lines

The infrastructure is there in the patch to support IPv4/IPv6 conntrack separatedly in spite of the common code and not to waste so many bytes at every IPv4 connections for the sake of supporting IPv6.

You mean the get_features stuff and seperate caches ? I'm don't like this part very much, I thing Rusty's "structure extension stuff" (ct_extend) is a nicer way to do this, although its probably not useable for the tuples.

Unfortunately I have to disagree. I think I pointed it out in an earlier email, but I'm not sure whether it was on IRC or whether you've been on the list of recipients.

the nf_conntrack approach of having multiple slab caches of differently sized conntrack structures is better from a performance point of view.

If you look at the typical applications, people will usually

a) either use NAT on most/all of their connections
b) or not use NAT on any of their connections

Now why don't they (the 'b' users) recompile their kernel? Because they use vendor-kernels, and they compile with everything enabled.

So what we end up if we use rusty's scheme for nat private data, is that we have at least one additional allocation, and two disjunct seperate pieces of memory (which will probably also introduce yet another cache
miss). This is acceptable for rare exceptional cases, not for 99.9% of
your connections.

So even if Rusty's architecture and API is cleaner, I'm very much in favour of the nf_conntrack design and Yasuyuki's current implementation.

Now you can argue about conntrack/nat helper private data. Here my argument is weaker, since normally you have something like < 1% of your connections with a helper. For this I would be willing to accept the additional allocation and whatever.

But, then think of a firewall in front of an FTP (IRC/...) Server, and your traffic pattern immediately looks like 50% of your connections (not talking about traffic) have helper private data... and my argument becomes stronger again.

Quoted 4 lines

I think we should put ip_conntrack in maintenance mode, than we can resync nf_conntrack and make changes like this before we submit it.

At last, we again agree :)

Quoted 3 lines

I think we should put ip_conntrack in maintenance mode, than we can resync nf_conntrack and make changes like this before we submit it.

At last, we again agree :)

Quoted 17 lines · Harald Welte

the nf_conntrack approach of having multiple slab caches of differently sized conntrack structures is better from a performance point of view.

If you look at the typical applications, people will usually

a) either use NAT on most/all of their connections
b) or not use NAT on any of their connections

Now why don't they (the 'b' users) recompile their kernel? Because they use vendor-kernels, and they compile with everything enabled.

So what we end up if we use rusty's scheme for nat private data, is that we have at least one additional allocation, and two disjunct seperate pieces of memory (which will probably also introduce yet another cache
miss). This is acceptable for rare exceptional cases, not for 99.9% of
your connections.

Quoted 5 lines

So even if Rusty's architecture and API is cleaner, I'm very much in favour of the nf_conntrack design and Yasuyuki's current implementation.

But unlike ct_extend, the get_features stuff is very unflexible. The way it is currently implemented it only works for a single dynamically allocated part without leaving holes, and it even it if could handle more, they all need to be determined at allocation time, so a worst-case assumption
has to be made for anything depending on the ruleset. This is especially a concern with modules and distribution-kernels, NAT could be loaded at any time, so the memory needs to be allocated in advance.

Quoted 14 lines · Harald Welte

Quoted 10 lines · Patrick McHardy

Quoted 5 lines

The infrastructure is there in the patch to support IPv4/IPv6 conntrack separatedly in spite of the common code and not to waste so many bytes at every IPv4 connections for the sake of supporting IPv6.

You mean the get_features stuff and seperate caches ? I'm don't like this part very much, I thing Rusty's "structure extension stuff" (ct_extend) is a nicer way to do this, although its probably not useable for the tuples.

Quoted 4 lines

Unfortunately I have to disagree. I think I pointed it out in an earlier email, but I'm not sure whether it was on IRC or whether you've been on the list of recipients.

Hmm, I can't recall talking about this earlier.

Quoted 9 lines

Now you can argue about conntrack/nat helper private data. Here my argument is weaker, since normally you have something like < 1% of your connections with a helper. For this I would be willing to accept the additional allocation and whatever.

But, then think of a firewall in front of an FTP (IRC/...) Server, and your traffic pattern immediately looks like 50% of your connections (not talking about traffic) have helper private data... and my argument becomes stronger again.

Quoted 6 lines

Quoted 4 lines

I think we should put ip_conntrack in maintenance mode, than we can resync nf_conntrack and make changes like this before we submit it.

At last, we again agree :)

timeout: move to a 32-bit seconds counter, and use a sweep-method to
clean up connections rather than a timer per conn. Save 28 bytes.

ip_nat_info: use hash tree. Save 8 bytes.
tuplehash: use hash tree, put proto in status word. Save 24 bytes.

But unlike ct_extend, the get_features stuff is very unflexible. The way it is currently implemented it only works for a single dynamically allocated part without leaving holes, and it even it if could handle more, they all need to be determined at allocation time, so a worst-case assumption
has to be made for anything depending on the ruleset. This is especially a concern with modules and distribution-kernels, NAT could be loaded at any time, so the memory needs to be allocated in advance.

Quoted 5 lines

But, then think of a firewall in front of an FTP (IRC/...) Server, and your traffic pattern immediately looks like 50% of your connections (not talking about traffic) have helper private data... and my argument becomes stronger again.

Sure, but helpers are slow anyway. The additional allocation is a one-time effort, the two disjunct pieces of memory shouldn't hurt too much since nf_conntrack is very large and covers multiple cache-lines already. Rusty mentioned he got struct ip_conntrack down to ~150b, this makes it possible to have a lot more active connections without exceeding the cache.

One more thing I was thinking about. If we put ip_conntrack in maintenance mode and probably deprecate it at some time, I see little reason to remove ipchains compat just now. Why not just let it fade out together with ip_conntrack once nf_conntrack is in ? I haven't checked if it was because of incompatibilities or required changes with Rusty's latest work, if so that would be a good reason.

Regards
Patrick

It was IRC, and for IPv6 I agree with Harald that it's probably not the right mechanism. I prefer a simple discriminated union and two slab caches (IPv4 and IPv6), which is hardcoded, but still fairly easy to read.

Quoted 4 lines

Quoted 4 lines

But, then think of a firewall in front of an FTP (IRC/...) Server, and your traffic pattern immediately looks like 50% of your connections (not talking about traffic) have helper private data... and my argument becomes stronger again.

I don't think so. While you will have to do an additional allocation on connection creation, the only real per-packet cost is the extra cacheline (the memchr to find the data in the extend is deliberately
trivial). They'll gain more by removing the copying into buffer on
those helpers, and the lock that goes with it.

Does that mean I should *not* send the expectation and NAT patches to DaveM now? (Posted before the ct_extend patches):

Thanks,
Rusty.

Quoted 4 lines · Rusty Russell

It was IRC, and for IPv6 I agree with Harald that it's probably not the right mechanism. I prefer a simple discriminated union and two slab caches (IPv4 and IPv6), which is hardcoded, but still fairly easy to read.

so what about the nat_info ? If you load iptable_nat, it will be needed for all connections...

Quoted 2 lines

Does that mean I should *not* send the expectation and NAT patches to DaveM now? (Posted before the ct_extend patches):

I was wondering all the time why we keep talking about maintainance mode for ip_conntrack and the coincidential spike in new development for ip_conntrack.

It was IRC, and for IPv6 I agree with Harald that it's probably not the right mechanism. I prefer a simple discriminated union and two slab caches (IPv4 and IPv6), which is hardcoded, but still fairly easy to read.

Does that mean I should *not* send the expectation and NAT patches to DaveM now? (Posted before the ct_extend patches):

Nobody should ever load iptable_nat if it isn't actually used. That's what module autoloading is about. If a distribution does this, it is straight forward broken.

Also, I haven't seen this in practise so far, so it's not a valid optimization target from my point of view.

Quoted 6 lines

Sure, but helpers are slow anyway. The additional allocation is a one-time effort, the two disjunct pieces of memory shouldn't hurt too much since nf_conntrack is very large and covers multiple cache-lines already. Rusty mentioned he got struct ip_conntrack down to ~150b, this makes it possible to have a lot more active connections without exceeding the cache.

Ok, agreed for the helper case. But my argument for NAT still holds, at least as far as I see. Also, stuff like the accounting counters are a similar case.

So maybe in the end we need 'features' for those, and ct_extend for helper related data?

Quoted 7 lines

One more thing I was thinking about. If we put ip_conntrack in maintenance mode and probably deprecate it at some time, I see little reason to remove ipchains compat just now. Why not just let it fade out together with ip_conntrack once nf_conntrack is in ? I haven't checked if it was because of incompatibilities or required changes with Rusty's latest work, if so that would be a good reason.

I don't have a particular favour for or against any of the proposed solutions.

Quoted 3 lines

Does that mean I should *not* send the expectation and NAT patches to DaveM now? (Posted before the ct_extend patches):

I was wondering all the time why we keep talking about maintainance mode for ip_conntrack and the coincidential spike in new development for ip_conntrack.

I think if we push it into ip_conntrack, we need to make sure nf_conntrack is in sync at the same time - otherwise poor Yasuyuki has to (again) sync all the changes... I think he did that often enough...

I don't like sweep...

This reminds me: what about my "timer management frequency reduction" from longtimeago? Basic points:

Quoted 2 lines

This reminds me: what about my "timer management frequency reduction" from longtimeago? Basic points:

If my memory serves me well, Jozsef made some tests using a similar
patch (or maybe yours?), but the results were quite controversial.