[PATCH 1/2] string match for iptables

[PATCH 1/2] string match for iptables

[Pablo Neira]

[-- Attachment #1: Type: text/plain, Size: 297 bytes --]

Hi,

Here comes the iptables string match since the textsearch infrastructure 
went into 2.6.13. This adds to iptables the ability of looking for given 
patterns in packets. I'll be happy to see this stuff in Davem's 2.6.14 
tree ;)

Signed-off-by: Pablo Neira Ayuso <pablo@eurodev.net>

--
Pablo

[-- Attachment #2: 10ipt_string.patch --]
[-- Type: text/x-patch, Size: 4743 bytes --]

Index: netfilter-2.6.14/net/ipv4/netfilter/ipt_string.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ netfilter-2.6.14/net/ipv4/netfilter/ipt_string.c	2005-08-20 17:10:03.000000000 +0200
@@ -0,0 +1,91 @@
+/* String matching match for iptables
+ * 
+ * (C) 2005 Pablo Neira Ayuso <pablo@eurodev.net>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/skbuff.h>
+#include <linux/netfilter_ipv4/ip_tables.h>
+#include <linux/netfilter_ipv4/ipt_string.h>
+#include <linux/textsearch.h>
+
+MODULE_AUTHOR("Pablo Neira Ayuso <pablo@eurodev.net>");
+MODULE_DESCRIPTION("IP tables string match module");
+MODULE_LICENSE("GPL");
+
+static int match(const struct sk_buff *skb,
+		 const struct net_device *in,
+		 const struct net_device *out,
+		 const void *matchinfo,
+		 int offset,
+		 int *hotdrop)
+{
+	struct ts_state state;
+	struct ipt_string_info *conf = (struct ipt_string_info *) matchinfo;
+
+	memset(&state, 0, sizeof(struct ts_state));
+
+	return (skb_find_text((struct sk_buff *)skb, conf->from_offset, 
+			     conf->to_offset, conf->config, &state) 
+			     != UINT_MAX) && !conf->invert;
+}
+
+#define STRING_TEXT_PRIV(m) ((struct ipt_string_info *) m)
+
+static int checkentry(const char *tablename,
+		      const struct ipt_ip *ip,
+		      void *matchinfo,
+		      unsigned int matchsize,
+		      unsigned int hook_mask)
+{
+	struct ipt_string_info *conf = matchinfo;
+	struct ts_config *ts_conf;
+
+	if (matchsize != IPT_ALIGN(sizeof(struct ipt_string_info)))
+		return 0;
+
+	/* Damn, can't handle this case properly with iptables... */
+	if (conf->from_offset > conf->to_offset)
+		return 0;
+
+	ts_conf = textsearch_prepare(conf->algo, conf->pattern, conf->patlen,
+				     GFP_KERNEL, TS_AUTOLOAD);
+	if (IS_ERR(ts_conf))
+		return 0;
+
+	conf->config = ts_conf;
+
+	return 1;
+}
+
+static void destroy(void *matchinfo, unsigned int matchsize)
+{
+	textsearch_destroy(STRING_TEXT_PRIV(matchinfo)->config);
+}
+
+static struct ipt_match string_match = {
+	.name 		= "string",
+	.match 		= match,
+	.checkentry	= checkentry,
+	.destroy 	= destroy,
+	.me 		= THIS_MODULE
+};
+
+static int __init init(void)
+{
+	return ipt_register_match(&string_match);
+}
+
+static void __exit fini(void)
+{
+	ipt_unregister_match(&string_match);
+}
+
+module_init(init);
+module_exit(fini);
Index: netfilter-2.6.14/net/ipv4/netfilter/Makefile
===================================================================
--- netfilter-2.6.14.orig/net/ipv4/netfilter/Makefile	2005-08-20 15:49:31.000000000 +0200
+++ netfilter-2.6.14/net/ipv4/netfilter/Makefile	2005-08-20 17:10:03.000000000 +0200
@@ -65,6 +65,7 @@
 obj-$(CONFIG_IP_NF_MATCH_ADDRTYPE) += ipt_addrtype.o
 obj-$(CONFIG_IP_NF_MATCH_PHYSDEV) += ipt_physdev.o
 obj-$(CONFIG_IP_NF_MATCH_COMMENT) += ipt_comment.o
+obj-$(CONFIG_IP_NF_MATCH_STRING) += ipt_string.o
 
 # targets
 obj-$(CONFIG_IP_NF_TARGET_REJECT) += ipt_REJECT.o
Index: netfilter-2.6.14/net/ipv4/netfilter/Kconfig
===================================================================
--- netfilter-2.6.14.orig/net/ipv4/netfilter/Kconfig	2005-08-20 15:49:31.000000000 +0200
+++ netfilter-2.6.14/net/ipv4/netfilter/Kconfig	2005-08-20 17:50:59.000000000 +0200
@@ -410,6 +410,18 @@
 	  destination IP' or `500pps from any given source IP'  with a single
 	  IPtables rule.
 
+config IP_NF_MATCH_STRING
+	tristate  'string match support'
+	depends on IP_NF_IPTABLES 
+	select TEXTSEARCH
+	select TEXTSEARCH_KMP
+	select TEXTSEARCH_FSM
+	help
+	  This option adds a `string' match, which allows you to look for
+	  pattern matchings in packets.
+
+	  To compile it as a module, choose M here.  If unsure, say N.
+
 # `filter', generic and specific targets
 config IP_NF_FILTER
 	tristate "Packet filtering"
Index: netfilter-2.6.14/include/linux/netfilter_ipv4/ipt_string.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ netfilter-2.6.14/include/linux/netfilter_ipv4/ipt_string.h	2005-08-20 17:10:03.000000000 +0200
@@ -0,0 +1,18 @@
+#ifndef _IPT_STRING_H
+#define _IPT_STRING_H
+
+#define IPT_STRING_MAX_PATTERN_SIZE 128
+#define IPT_STRING_MAX_ALGO_NAME_SIZE 16
+
+struct ipt_string_info
+{
+	u_int16_t		from_offset;
+	u_int16_t		to_offset;
+	char			algo[IPT_STRING_MAX_ALGO_NAME_SIZE];
+	char			pattern[IPT_STRING_MAX_PATTERN_SIZE];
+	u_int8_t		patlen;
+	u_int8_t		invert;
+	struct ts_config	*config;
+};
+
+#endif /*_IPT_STRING_H*/

Re: [PATCH 1/2] string match for iptables

[Patrick McHardy]

Pablo Neira wrote:
> Here comes the iptables string match since the textsearch infrastructure
> went into 2.6.13. This adds to iptables the ability of looking for given
> patterns in packets. I'll be happy to see this stuff in Davem's 2.6.14
> tree ;)

> +struct ipt_string_info
> +{
> +	u_int16_t		from_offset;
> +	u_int16_t		to_offset;
> +	char			algo[IPT_STRING_MAX_ALGO_NAME_SIZE];
> +	char			pattern[IPT_STRING_MAX_PATTERN_SIZE];
> +	u_int8_t		patlen;
> +	u_int8_t		invert;
> +	struct ts_config	*config;
> +};

Embedding a pointer in the struct causes different alignment depending
on the wordsize and doesn't work in mixed 64/32 bit environments.
Please use __attribute__((aligned(8))) to prevent this.

Otherwise, it looks good.

Re: [PATCH 1/2] string match for iptables

[David S. Miller]

From: Patrick McHardy <kaber@trash.net>
Subject: Re: [PATCH 1/2] string match for iptables
Date: Sat, 20 Aug 2005 18:35:54 +0200

> Pablo Neira wrote:
> > Here comes the iptables string match since the textsearch infrastructure
> > went into 2.6.13. This adds to iptables the ability of looking for given
> > patterns in packets. I'll be happy to see this stuff in Davem's 2.6.14
> > tree ;)
> 
> > +struct ipt_string_info
> > +{
> > +	u_int16_t		from_offset;
> > +	u_int16_t		to_offset;
> > +	char			algo[IPT_STRING_MAX_ALGO_NAME_SIZE];
> > +	char			pattern[IPT_STRING_MAX_PATTERN_SIZE];
> > +	u_int8_t		patlen;
> > +	u_int8_t		invert;
> > +	struct ts_config	*config;
> > +};
> 
> Embedding a pointer in the struct causes different alignment depending
> on the wordsize and doesn't work in mixed 64/32 bit environments.
> Please use __attribute__((aligned(8))) to prevent this.

Our ability to translate netfilter structures in compat mode
is primitive, at best, and I think we really should try to
do something about this soon.

This IP tables modules can provide a bit of help, with some kind
of descriptor, or set of methods the compat layer can call into
for help (or a flag saying, "no translation necessary").

One thing about the implementation is that it is apparent that
people often load an _enormous_ amount of rules.  A large enough
set that kmalloc() can't get enough space for the entire rule set.
I've seen a report about this recently on sparc64, where someone
tries to load enough ipt_replace rules that the kmalloc() done
by the compat mode translation stuff was too large.

One thing that can help is to not put pointers into these rules,
that is actually the most difficult case to handle.  Without
pointers, the entire struct can be defined using portable types
that require no translation.  Once you introduce a pointer, using
the user's struct as-is becomes impossible.  (as an added bonus
such rules could thus be sent over the wire as well, if we ever
wanted to do that)

In this case, we could put a zero length array at the end.  But
I realize that with iptables rules this may be difficult due to
some restriction I am not aware of.

Re: [PATCH 1/2] string match for iptables

[Patrick McHardy]

David S. Miller wrote:
> Our ability to translate netfilter structures in compat mode
> is primitive, at best, and I think we really should try to
> do something about this soon.

The compat code looks broken, it assumes struct ipt_entry is equal
in both environments, which is not true, at least not on my AMD64.
But we have a couple of spots in userspace were 32bit iptables on
64bit kernel is explicitly handled (libipt_MARK, libipt_CONNMARK,
...), so it does seem to work on some machines.

Anyway, I already started working on this after Andi claimed it was
unfixable, but so far I can only dump the ruleset, insertion doesn't
work yet.

> This IP tables modules can provide a bit of help, with some kind
> of descriptor, or set of methods the compat layer can call into
> for help (or a flag saying, "no translation necessary").

At the moment we have two modules that need translation, CLUSTERIP
and hashlimit. Thanks to versioning we can just fix them in a new
structure.

> One thing about the implementation is that it is apparent that
> people often load an _enormous_ amount of rules.  A large enough
> set that kmalloc() can't get enough space for the entire rule set.
> I've seen a report about this recently on sparc64, where someone
> tries to load enough ipt_replace rules that the kmalloc() done
> by the compat mode translation stuff was too large.

Where does it call kmalloc? net/compat.c uses compat_alloc_user_space
for the translated ruleset.

> One thing that can help is to not put pointers into these rules,
> that is actually the most difficult case to handle.  Without
> pointers, the entire struct can be defined using portable types
> that require no translation.  Once you introduce a pointer, using
> the user's struct as-is becomes impossible.  (as an added bonus
> such rules could thus be sent over the wire as well, if we ever
> wanted to do that)
> 
> In this case, we could put a zero length array at the end.  But
> I realize that with iptables rules this may be difficult due to
> some restriction I am not aware of.

The entire ruleset is one big blob so dynamically sizing structures
doesn't work. There's also no room to put a pointer somewhere outside
of the match/target structures where they could keep instantiated
private data. I think there is no way to avoid this until we get
rid of the one-big-blob thing.

Re: [PATCH 1/2] string match for iptables

[David S. Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Sun, 21 Aug 2005 15:55:22 +0200

> David S. Miller wrote:
> > One thing about the implementation is that it is apparent that
> > people often load an _enormous_ amount of rules.  A large enough
> > set that kmalloc() can't get enough space for the entire rule set.
> > I've seen a report about this recently on sparc64, where someone
> > tries to load enough ipt_replace rules that the kmalloc() done
> > by the compat mode translation stuff was too large.
> 
> Where does it call kmalloc? net/compat.c uses compat_alloc_user_space
> for the translated ruleset.

Sorry, that's the 2.4.x code, perhaps it should be converted
to use either vmalloc() of compat_alloc_user_space().

Re: [PATCH 1/2] string match for iptables

[Patrick McHardy]

David S. Miller wrote:
> From: Patrick McHardy <kaber@trash.net>
> Date: Sun, 21 Aug 2005 15:55:22 +0200
> 
>>Where does it call kmalloc? net/compat.c uses compat_alloc_user_space
>>for the translated ruleset.
> 
> Sorry, that's the 2.4.x code, perhaps it should be converted
> to use either vmalloc() of compat_alloc_user_space().

I'll look into it after fixing the 2.6 compat code.

Re: [PATCH 1/2] string match for iptables

[David S. Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Mon, 22 Aug 2005 02:13:59 +0200

> David S. Miller wrote:
> > Sorry, that's the 2.4.x code, perhaps it should be converted
> > to use either vmalloc() of compat_alloc_user_space().
> 
> I'll look into it after fixing the 2.6 compat code.

Thanks a lot Patrick.

Re: [PATCH 1/2] string match for iptables

[Harald Welte]

[-- Attachment #1: Type: text/plain, Size: 2951 bytes --]

Sorry for the late reply, I just returned from holidays.

On Sat, Aug 20, 2005 at 01:14:03PM -0700, David S. Miller wrote:

> Our ability to translate netfilter structures in compat mode
> is primitive, at best, and I think we really should try to
> do something about this soon.

mh. I always dreamed of pkttables happening earlier so we don't have to
deal with this...

> This IP tables modules can provide a bit of help, with some kind
> of descriptor, or set of methods the compat layer can call into
> for help (or a flag saying, "no translation necessary").
 
> One thing about the implementation is that it is apparent that
> people often load an _enormous_ amount of rules.  A large enough
> set that kmalloc() can't get enough space for the entire rule set.

This tends to happen on smp 2.4.x systems, since they use NR_CPUS times
the ruleset size.  On (at least somewhat recent) 2.6.x, we use
num_possible_cpus() to reduce the bloatage.

> I've seen a report about this recently on sparc64, where someone
> tries to load enough ipt_replace rules that the kmalloc() done
> by the compat mode translation stuff was too large.

was this 2.4.x or 2.6.x ? and was it smp or not?

if it was 2.6.x and smp, we could introduce an option that would use
only one ruleset even on multiple cpus.  it will produce counter
cacheline ping-pong but reduce the memory usage significantly.

> One thing that can help is to not put pointers into these rules,
> that is actually the most difficult case to handle.  Without
> pointers, the entire struct can be defined using portable types
> that require no translation.  Once you introduce a pointer, using
> the user's struct as-is becomes impossible.  (as an added bonus
> such rules could thus be sent over the wire as well, if we ever
> wanted to do that)

The only reason why a pointer is needed at all, is the "dump whole table
to userspace, do some modifications and read it back" approach.  I
seriously doubt that we would be able to change that assumption.  If we
did, it wouldn't be iptables anymore, but half-way into pkttables.

As an intermediate solution we could do some form of indirect
resolval/mapping.  The core could provide an allocation wrapper API
which matches/targets could use for malloc'ing their private data
structures.  In addition to a pointer, it would return an (32bit) ID.
That ID can then be embedded in kernel/userspace data structures.  When
userspace rules come in, the ID gets translated to the real pointer by
some call to that API of the core.

-- 
- Harald Welte <laforge@netfilter.org>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

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

Re: [PATCH 1/2] string match for iptables

[Martin Josefsson]

[-- Attachment #1: Type: text/plain, Size: 2535 bytes --]

On Thu, 2005-08-25 at 12:42 +0200, Harald Welte wrote:

> > One thing that can help is to not put pointers into these rules,
> > that is actually the most difficult case to handle.  Without
> > pointers, the entire struct can be defined using portable types
> > that require no translation.  Once you introduce a pointer, using
> > the user's struct as-is becomes impossible.  (as an added bonus
> > such rules could thus be sent over the wire as well, if we ever
> > wanted to do that)
> 
> The only reason why a pointer is needed at all, is the "dump whole table
> to userspace, do some modifications and read it back" approach.  I
> seriously doubt that we would be able to change that assumption.  If we
> did, it wouldn't be iptables anymore, but half-way into pkttables.
> 
> As an intermediate solution we could do some form of indirect
> resolval/mapping.  The core could provide an allocation wrapper API
> which matches/targets could use for malloc'ing their private data
> structures.  In addition to a pointer, it would return an (32bit) ID.
> That ID can then be embedded in kernel/userspace data structures.  When
> userspace rules come in, the ID gets translated to the real pointer by
> some call to that API of the core.

Now that we have support for diffrent revisions of matches/targets we
can easily add new revisions that uses diffrent structs and later
deprecate the older revisions.

Matches and targets have two sizes defined for their datastructures,
size and userspacesize. size is the total size of the datastructure, the
amount that is allocated for the rule private data. And userspacesize is
the amount transferred to/from userspace when rules are modified.

So we could put all portable members at the top of the structure and all
pointers at the end and set userspacesize to the offset of the first
pointer in the structure. There's no need to transfer that data back and
forth to userspace, it just introduces races in the cases where there's
members used for refcounting in the structure.
So the remaining problem is that the total size of the structure is
diffrent on 32/64 bit.
The userspacesize stays the same on both but not the part of the
structure that holds the "kernelprivate data", iow the last part of the
structure, that changes on 32/64bit and I don't think we can assume that
the size on 64bit is 2 * size on 32bit, that only holds for non portable
types, what if someone wants a portable size in this section...

Any ideas?

-- 
/Martin

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 1/2] string match for iptables

[Martin Josefsson]

[-- Attachment #1: Type: text/plain, Size: 2844 bytes --]

On Thu, 2005-08-25 at 18:54 +0200, Martin Josefsson wrote:

I wonder why davem got lost on the CC, he's there in my Sent folder but
not in the mail I got from netfilter-devel... I hope he makes it this
time.

> On Thu, 2005-08-25 at 12:42 +0200, Harald Welte wrote:
> 
> > > One thing that can help is to not put pointers into these rules,
> > > that is actually the most difficult case to handle.  Without
> > > pointers, the entire struct can be defined using portable types
> > > that require no translation.  Once you introduce a pointer, using
> > > the user's struct as-is becomes impossible.  (as an added bonus
> > > such rules could thus be sent over the wire as well, if we ever
> > > wanted to do that)
> > 
> > The only reason why a pointer is needed at all, is the "dump whole table
> > to userspace, do some modifications and read it back" approach.  I
> > seriously doubt that we would be able to change that assumption.  If we
> > did, it wouldn't be iptables anymore, but half-way into pkttables.
> > 
> > As an intermediate solution we could do some form of indirect
> > resolval/mapping.  The core could provide an allocation wrapper API
> > which matches/targets could use for malloc'ing their private data
> > structures.  In addition to a pointer, it would return an (32bit) ID.
> > That ID can then be embedded in kernel/userspace data structures.  When
> > userspace rules come in, the ID gets translated to the real pointer by
> > some call to that API of the core.
> 
> Now that we have support for diffrent revisions of matches/targets we
> can easily add new revisions that uses diffrent structs and later
> deprecate the older revisions.
> 
> Matches and targets have two sizes defined for their datastructures,
> size and userspacesize. size is the total size of the datastructure, the
> amount that is allocated for the rule private data. And userspacesize is
> the amount transferred to/from userspace when rules are modified.
> 
> So we could put all portable members at the top of the structure and all
> pointers at the end and set userspacesize to the offset of the first
> pointer in the structure. There's no need to transfer that data back and
> forth to userspace, it just introduces races in the cases where there's
> members used for refcounting in the structure.
> So the remaining problem is that the total size of the structure is
> diffrent on 32/64 bit.
> The userspacesize stays the same on both but not the part of the
> structure that holds the "kernelprivate data", iow the last part of the
> structure, that changes on 32/64bit and I don't think we can assume that
> the size on 64bit is 2 * size on 32bit, that only holds for non portable
> types, what if someone wants a portable size in this section...
> 
> Any ideas?
> 
-- 
/Martin

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 1/2] string match for iptables

[Patrick McHardy]

Martin Josefsson wrote:
> On Thu, 2005-08-25 at 18:54 +0200, Martin Josefsson wrote:
> 
> I wonder why davem got lost on the CC, he's there in my Sent folder but
> not in the mail I got from netfilter-devel... I hope he makes it this
> time.

Yes, I noticed this multiple times, mails to the list seem to remove
Dave automatically. Perhaps this has something to do with the
"may sent to list even if not subscribed" setting that was made
when he wasn't subscribed to the list.

DaveM get's removed from Cc (was Re: [PATCH 1/2] string match for iptables)

[Harald Welte]

[-- Attachment #1: Type: text/plain, Size: 1293 bytes --]

On Fri, Aug 26, 2005 at 02:00:02PM +0200, Patrick McHardy wrote:
> Martin Josefsson wrote:
> > On Thu, 2005-08-25 at 18:54 +0200, Martin Josefsson wrote:
> > 
> > I wonder why davem got lost on the CC, he's there in my Sent folder but
> > not in the mail I got from netfilter-devel... I hope he makes it this
> > time.
> 
> Yes, I noticed this multiple times, mails to the list seem to remove
> Dave automatically. Perhaps this has something to do with the
> "may sent to list even if not subscribed" setting that was made
> when he wasn't subscribed to the list.

it's a per-user configuration setting of mailman called "nodupes".  

If X subscribes to a mailinglist L and sets "nodupes", and Z sends a
message to L with Cc: X, then X will be removed.

DaveM had his netfilter-devel subscription set to "nodupes".  I assume
that was a mistake and have disabled that switch via the admin
interface.

-- 
- Harald Welte <laforge@netfilter.org>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

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

Re: DaveM get's removed from Cc (was Re: [PATCH 1/2] string match for iptables)

[Phil Oester]

On Fri, Aug 26, 2005 at 03:27:43PM +0200, Harald Welte wrote:
> it's a per-user configuration setting of mailman called "nodupes".  
> 
> If X subscribes to a mailinglist L and sets "nodupes", and Z sends a
> message to L with Cc: X, then X will be removed.

FWIW, most other lists seem to default to 'dupes', but netfilter-devel
defaults to nodupes.  Perhaps the default should be flipped?

Phil

Re: DaveM get's removed from Cc (was Re: [PATCH 1/2] string match for iptables)

[Harald Welte]

[-- Attachment #1: Type: text/plain, Size: 910 bytes --]

On Fri, Aug 26, 2005 at 08:21:21AM -0700, Phil Oester wrote:
> On Fri, Aug 26, 2005 at 03:27:43PM +0200, Harald Welte wrote:
> > it's a per-user configuration setting of mailman called "nodupes".  
> > 
> > If X subscribes to a mailinglist L and sets "nodupes", and Z sends a
> > message to L with Cc: X, then X will be removed.
> 
> FWIW, most other lists seem to default to 'dupes', but netfilter-devel
> defaults to nodupes.  Perhaps the default should be flipped?

Thanks, changed the default for new members accordingly.

-- 
- Harald Welte <laforge@netfilter.org>                 http://netfilter.org/
============================================================================
  "Fragmentation is like classful addressing -- an interesting early
   architectural error that shows how much experimentation was going
   on while IP was being designed."                    -- Paul Vixie

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