About matching

About matching

[Wang Jian]

Hi,

I haven't looked into code on how these two rules are evaluated


iptables <match rule 1> -j CONNMARK --set-mark value/mask
iptables <match rule 1> -j RETURN


How many times the match rule 1 is evaluated when matched? If two, then
the second time is waste of CPU cycle.

Then think these three

iptables <match rule 1> -j CONNMARK --set-mark value/mask
iptables <match rule 1> -j CONNMARK --restore --mask mask
iptables <match rule 1> -j RETURN

Are there any optimization for such case?


-- 
  lark

Re: About matching

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Wang Jian wrote:

| iptables <match rule 1> -j CONNMARK --set-mark value/mask
| iptables <match rule 1> -j RETURN
|
| How many times the match rule 1 is evaluated when matched? If two, then
| the second time is waste of CPU cycle.

It evaluates twice. I have made a "previous" match which I haven't finished
into a patch yet (some cleanup, documentation and iptables-save & -restore
support). It lets you do the above like this:

iptables <match rule 1> -j CONNMARK --set-mark value/mask
iptables --previous -j RETURN

| Then think these three
|
| iptables <match rule 1> -j CONNMARK --set-mark value/mask
| iptables <match rule 1> -j CONNMARK --restore --mask mask
| iptables <match rule 1> -j RETURN
|
| Are there any optimization for such case?

I would guess mask restoring is usually done globally without matching some
specific criteria.. but nevertheless, the --previous could be used here if
wanted, it can be used many times in a row.

I'll try to finish off the patch tomorrow.

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCVC64xyF48ZTvn+4RAi8pAJ4sjXT1KZf5Ora6S0Rr5dCXmcGj9gCgzKQi
OUx6jdlw3FvPEtVuWgZ2/j8=
=bp5F
-----END PGP SIGNATURE-----

Re: About matching

[Wang Jian]

Hi Jonas Berlin,

I have an idea before, that looks like the following

1. A match is marked as dup when insert into chain if it has the same
match rule with previous;
2. When a match gets deleted followed by match marked as dup , do
housekeeping to make sure the dup relation is correct;
3. When a match is hit, if non-return, the following match marked as dup
is evaluated immediately as hit.

This can be achieved with a little code. But the problem here is when
used in mangle table, the target action may make the matching rule false.

--previous is an indication that the previous matching is used anyway
even if the target action changes the evaluation result. You may use the
same algorithm above and save a lot trouble :)


On Wed, 06 Apr 2005 21:47:22 +0300, Jonas Berlin <xkr47@outerspace.dyndns.org> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Wang Jian wrote:
> 
> | iptables <match rule 1> -j CONNMARK --set-mark value/mask
> | iptables <match rule 1> -j RETURN
> |
> | How many times the match rule 1 is evaluated when matched? If two, then
> | the second time is waste of CPU cycle.
> 
> It evaluates twice. I have made a "previous" match which I haven't finished
> into a patch yet (some cleanup, documentation and iptables-save & -restore
> support). It lets you do the above like this:
> 
> iptables <match rule 1> -j CONNMARK --set-mark value/mask
> iptables --previous -j RETURN
> 
> | Then think these three
> |
> | iptables <match rule 1> -j CONNMARK --set-mark value/mask
> | iptables <match rule 1> -j CONNMARK --restore --mask mask
> | iptables <match rule 1> -j RETURN
> |
> | Are there any optimization for such case?
> 
> I would guess mask restoring is usually done globally without matching some
> specific criteria.. but nevertheless, the --previous could be used here if
> wanted, it can be used many times in a row.
> 
> I'll try to finish off the patch tomorrow.
> 
> - --
> - - xkr47
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (GNU/Linux)
> 
> iD8DBQFCVC64xyF48ZTvn+4RAi8pAJ4sjXT1KZf5Ora6S0Rr5dCXmcGj9gCgzKQi
> OUx6jdlw3FvPEtVuWgZ2/j8=
> =bp5F
> -----END PGP SIGNATURE-----



-- 
  lark

Re: About matching

[Patrick Schaaf]

Hello Wang Jian,

> I have an idea before, that looks like the following
> 
> 1. A match is marked as dup when insert into chain if it has the same
> match rule with previous;
> 2. When a match gets deleted followed by match marked as dup , do
> housekeeping to make sure the dup relation is correct;
> 3. When a match is hit, if non-return, the following match marked as dup
> is evaluated immediately as hit.
> 
> This can be achieved with a little code. But the problem here is when
> used in mangle table, the target action may make the matching rule false.

The other problem is that there are several kinds of matches that
have direct or indirect side effects when run. Consider -m limit:
if you have two lines directly following each other, both using
only '-m limit --limit 1/s', your dup solution would decide the
limit only once, where the current solution presents two independant
limits of 1/s each. There are several more matches that are like that.

These cases MUST be handled, i.e. dup logic deactivated, because it is
not acceptable to change semantics of established rulesets just for the
sake of efficiency (just my strong opinion).

best regards
  Patrick

Re: About matching

[Wang Jian]

Hi Patrick Schaaf,


On Thu, 7 Apr 2005 07:43:02 +0200, Patrick Schaaf <bof@bof.de> wrote:

> Hello Wang Jian,
> 
> > I have an idea before, that looks like the following
> > 
> > 1. A match is marked as dup when insert into chain if it has the same
> > match rule with previous;
> > 2. When a match gets deleted followed by match marked as dup , do
> > housekeeping to make sure the dup relation is correct;
> > 3. When a match is hit, if non-return, the following match marked as dup
> > is evaluated immediately as hit.
> > 
> > This can be achieved with a little code. But the problem here is when
> > used in mangle table, the target action may make the matching rule false.
> 
> The other problem is that there are several kinds of matches that
> have direct or indirect side effects when run. Consider -m limit:
> if you have two lines directly following each other, both using
> only '-m limit --limit 1/s', your dup solution would decide the
> limit only once, where the current solution presents two independant
> limits of 1/s each. There are several more matches that are like that.
> 
> These cases MUST be handled, i.e. dup logic deactivated, because it is
> not acceptable to change semantics of established rulesets just for the
> sake of efficiency (just my strong opinion).
> 

Yes. So I think --previous is a strong indication that
you-know-what-you-are-doing. With this option, kernel is instructed that
this optimization is needed, and is ok even if there are conflicts.

Because this is will not lead to crashes, I think let the user space (I
mean, users) do the work is best, actually, the user who use the rule
knows the best here.

-- 
  lark

Re: About matching

[Patrick Schaaf]

> Yes. So I think --previous is a strong indication that
> you-know-what-you-are-doing. With this option, kernel is instructed that
> this optimization is needed, and is ok even if there are conflicts.

I agree. Following implementation thougts and questions arise:

It would be a bit more typing work, but '-m previous' would be
more easy to implement, I think: just write it as a new match.
The match function will need access to a 'didmatch' boolean variable.
The variable value would be determined by the result of the immediately
previous match, surely available to the main table walking code.

Should this variable be set to 0 when entering each new chain? I think yes.

Then there is the question of how the previous match code would access
the variable. Without changing the call signature of match functions,
it needs to be somewhat global. Hmm: can there be several ruleset
walks active at the same time and on the same processor? If not,
this could be a CPU-private variable.

Last question: in the main match loop, some matching is handled by
the loop itself (input/output device, source/destination IP address).
Now, when a rule uses -m previous, should this rule's device and
IP address fields be checked, anyway, or should this check also
be ommitted? I think it could also be ommitted.

Finally, a full common-subexpression-elimination, in user level,
before pushing the ruleset into the kernel, would be very nice.
Unfortunately this will be harder to do when single-rule-updates,
instead of full-table-loading, becomes state of the art. :)

all the best
  Patrick

Re: About matching

[Patrick Schaaf]

Hmm, regarding --previous... Do we have two bits spare in the
general rule structure, which could indicate 'match just like
the previous match did', and 'match exactly if the previous
match did NOT match'?

It we do have such bits spare, a general --previous-matched
and --previous-failed syntax might be easier than a new match
with signature change or percpu variables: all decision logic
stays properly localized in the table scanning main loop.

BTW, it just occurred to be that --previous-failed, a logical
consequence of the --previous idea :), is a nice thing to
have by itself: it permits proper if/then/else semantics
for nonterminating targets!

iptables -A xxx -m this -m that -j LOG --log-prefix "thisandthat: "
iptables -A xxx --previous-failed -j LOG --log-prefix "NOT-thisandthat: "

best regards
  Patrick

Re: About matching

[Wang Jian]

Hi Patrick Schaaf,


On Thu, 7 Apr 2005 08:43:23 +0200, Patrick Schaaf <bof@bof.de> wrote:

> Hmm, regarding --previous... Do we have two bits spare in the
> general rule structure, which could indicate 'match just like
> the previous match did', and 'match exactly if the previous
> match did NOT match'?
> 
> It we do have such bits spare, a general --previous-matched
> and --previous-failed syntax might be easier than a new match
> with signature change or percpu variables: all decision logic
> stays properly localized in the table scanning main loop.
> 
> BTW, it just occurred to be that --previous-failed, a logical
> consequence of the --previous idea :), is a nice thing to
> have by itself: it permits proper if/then/else semantics
> for nonterminating targets!
> 
> iptables -A xxx -m this -m that -j LOG --log-prefix "thisandthat: "
> iptables -A xxx --previous-failed -j LOG --log-prefix "NOT-thisandthat: "
> 

Yes, this will be a very nice feature. But we should notice the
potential race when delete the immediate previous rule before the
--previous-failed rule. I think it is hard to handle the race.


-- 
  lark

Re: About matching

[Wang Jian]

Hi Patrick Schaaf,


On Thu, 7 Apr 2005 08:35:48 +0200, Patrick Schaaf <bof@bof.de> wrote:

> > Yes. So I think --previous is a strong indication that
> > you-know-what-you-are-doing. With this option, kernel is instructed that
> > this optimization is needed, and is ok even if there are conflicts.
> 
> I agree. Following implementation thougts and questions arise:
> 
> It would be a bit more typing work, but '-m previous' would be
> more easy to implement, I think: just write it as a new match.
> The match function will need access to a 'didmatch' boolean variable.
> The variable value would be determined by the result of the immediately
> previous match, surely available to the main table walking code.
> 
> Should this variable be set to 0 when entering each new chain? I think yes.
> 

Here, first we should decide how -m previous is implemented.

1. A real match;
2. A pseudo match, which copy previous rule's match and mark itself a
dup of previous match;

I prefer the later. The insertion and deletion logic will be very small
and clean. When you delete the previous, this match still makes sense,
and you just clear the 'dup' mark.

> Then there is the question of how the previous match code would access
> the variable. Without changing the call signature of match functions,
> it needs to be somewhat global. Hmm: can there be several ruleset
> walks active at the same time and on the same processor? If not,
> this could be a CPU-private variable.
> 
> Last question: in the main match loop, some matching is handled by
> the loop itself (input/output device, source/destination IP address).
> Now, when a rule uses -m previous, should this rule's device and
> IP address fields be checked, anyway, or should this check also
> be ommitted? I think it could also be ommitted.
> 

These two questions depends on the decision made above.

> Finally, a full common-subexpression-elimination, in user level,
> before pushing the ruleset into the kernel, would be very nice.
> Unfortunately this will be harder to do when single-rule-updates,
> instead of full-table-loading, becomes state of the art. :)
> 

tc filter seems to be doing this in kernel space.


-- 
  lark

Re: About matching

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Wang Jian wrote:

| 1. A match is marked as dup when insert into chain if it has the same
| match rule with previous;

I completely agree with Patrick Schaaf on the side effects.

| --previous is an indication that the previous matching is used anyway
| even if the target action changes the evaluation result. You may use the

I think this feature is one of the strong points of --previous. You can
perform multiple actions without the possible side-effects from the
redundant matching, maybe especially when you do a -j RETURN or -j DROP as
the second (or even third) action.

I understand how the automatic optimization would be convenient in that it
would work with existing solutions, but currently we can't do that reliably,
and it would require changes to all matchers & targets for them to report
whether they have side-effects or not. And even then, the --previous match
would have to be used to explicitly optimize the cases where the implicit
optimization is disabled because of the side-effects.

I don't know if it really is worth making all those changes. The --previous
already gives the same power (although not automatically), is very well
defined and the side-effects are obvious. Also, the implicity could be
emulated in userspace to some degree if one would want to.

//

In the shell script I use to set up my firewall, I have a helper function
like this:

iptv () {
~  table="$1" ; shift
~  chain="$1" ; shift
~  verdict="$1" ; shift
~  iptables -t $table -A $chain "$@"
~  iptables -t $table -A $chain --previous -j $verdict
}

So I can do stuff like

iptv filter INPUT DROP -m random --average 50 -j LOG

which gives

iptables -t filter -A INPUT -m random --average 50 -j LOG
iptables -t filter -A INPUT --previous -j DROP

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCVOM2xyF48ZTvn+4RAlrRAKDn0GG165JQIwUmDGe4yKk9qVhnjQCgnw/B
ySA4iwsfG6h8MpidBc+U5MM=
=Unac
-----END PGP SIGNATURE-----

Re: About matching

[Wang Jian]

Hi Jonas Berlin,


On Thu, 07 Apr 2005 10:37:28 +0300, Jonas Berlin <xkr47@outerspace.dyndns.org> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Wang Jian wrote:
> 
> | 1. A match is marked as dup when insert into chain if it has the same
> | match rule with previous;
> 
> I completely agree with Patrick Schaaf on the side effects.
> 
> | --previous is an indication that the previous matching is used anyway
> | even if the target action changes the evaluation result. You may use the
> 
> I think this feature is one of the strong points of --previous. You can
> perform multiple actions without the possible side-effects from the
> redundant matching, maybe especially when you do a -j RETURN or -j DROP as
> the second (or even third) action.

Yes. In the discussion with Patrick Schaaf, we all agree on this.

> I understand how the automatic optimization would be convenient in that it
> would work with existing solutions, but currently we can't do that reliably,
> and it would require changes to all matchers & targets for them to report
> whether they have side-effects or not. And even then, the --previous match
> would have to be used to explicitly optimize the cases where the implicit
> optimization is disabled because of the side-effects.

I should make it clear, that the algorithm is not only for automatic
optimization. I suggest it because it is very simple and clean and can
be also used by your --previous match.

Actually, because I take side effects of matches and targets into
account, I am against automatic optimization. One should use -m previous
to explicitly trigger optimization. But that doesn't mean the algorithm
itself is bad. In other mails I have said that using this algorithm, the
insertion and deletion is very simple and clean and fast.

> I don't know if it really is worth making all those changes. The --previous
> already gives the same power (although not automatically), is very well
> defined and the side-effects are obvious. Also, the implicity could be
> emulated in userspace to some degree if one would want to.
> 

Post your code finished or not, and we can discuss it :) I wish we can
find the simpler if not simplest solution to current core.

> //
> 
> In the shell script I use to set up my firewall, I have a helper function
> like this:
> 
> iptv () {
> ~  table="$1" ; shift
> ~  chain="$1" ; shift
> ~  verdict="$1" ; shift
> ~  iptables -t $table -A $chain "$@"
> ~  iptables -t $table -A $chain --previous -j $verdict
> }
> 
> So I can do stuff like
> 
> iptv filter INPUT DROP -m random --average 50 -j LOG
> 
> which gives
> 
> iptables -t filter -A INPUT -m random --average 50 -j LOG
> iptables -t filter -A INPUT --previous -j DROP
> 
> - --
> - - xkr47
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (GNU/Linux)
> 
> iD8DBQFCVOM2xyF48ZTvn+4RAlrRAKDn0GG165JQIwUmDGe4yKk9qVhnjQCgnw/B
> ySA4iwsfG6h8MpidBc+U5MM=
> =Unac
> -----END PGP SIGNATURE-----



-- 
  lark

Re: About matching

[Jozsef Kadlecsik]

Hello,

On Thu, 7 Apr 2005, Wang Jian wrote:

> iptables <match rule 1> -j CONNMARK --set-mark value/mask
> iptables <match rule 1> -j RETURN
>
> How many times the match rule 1 is evaluated when matched? If two, then
> the second time is waste of CPU cycle.
>
> Then think these three
>
> iptables <match rule 1> -j CONNMARK --set-mark value/mask
> iptables <match rule 1> -j CONNMARK --restore --mask mask
> iptables <match rule 1> -j RETURN
>
> Are there any optimization for such case?

No, but what's wrong with a natural subchain called with the condition
<match rule 1>? If the return position should be the chain according to
the original rules above, one could dust off Henrik's goto patch from
pom-ng.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

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

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Patrick Schaaf on 2005-04-07 06:43 UTC:

| Hmm, regarding --previous... Do we have two bits spare in the
| general rule structure, which could indicate 'match just like
| the previous match did', and 'match exactly if the previous
| match did NOT match'?

Yes. IPT_F_MASK has many spare bits, and IPT_INV_MASK has exactly one
bit left (same for ipv6).

| It we do have such bits spare, a general --previous-matched
| and --previous-failed syntax might be easier than a new match
| with signature change or percpu variables: all decision logic
| stays properly localized in the table scanning main loop.

This is my implementation exactly. I also believe this does not break
binary compatibility; it just extends the use of the bitmasks, and
"older" iptables clients will just never set the bits in question - and
in the other way around when the iptables binary supports --previous but
the kernel doesnt no problems occur unless the user tries to use --previous.

| BTW, it just occurred to be that --previous-failed, a logical
| consequence of the --previous idea :), is a nice thing to
| have by itself: it permits proper if/then/else semantics
| for nonterminating targets!

Naturally, I thought of this too.. :)

| iptables -A xxx --previous-failed -j LOG --log-prefix "NOT-thisandthat: "

actually..

iptables -A xxx ! --previous -j LOG ...

There's one slight peculiarity with the current implementation.. if one
wants to use a target that works only for some specific protocol, say
TARPIT, one needs to:

iptables -A INPUT --previous -p tcp -j TARPIT

.. I haven't yet investigated if it would be possible to inherit the
protocol nicely..

I include only the kernel part of the patch for now so you can study and
complain about it :) I have some pending fixes for ip6tables that I want
to go in first before posting the iptables patch, which is trivial anyway..

I'm sorry for the long delay.. as you see from the patch it was done
more than three weeks ago.. :/ Otoh I tested it properly only last week.

- ----

I have also been thinking a bit about the original suggestion by Ben La
Monica in the thread "Multiple Targets" to allow multiple targets:

Quoting Patrick Schaaf on 2005-02-19 08:28 UTC:

|> iptables -A auth -i int+ -m mac --mac-source 00:00:00:00:00:00 -j
|> MARK,RETURN --set-mark 1
|> iptables -A auth -i int+ -m mac --mac-source 00:00:00:00:00:01 -j
|> MARK,RETURN --set-mark 2
|
| Problem: target options. How would the commandline parser see that
| --set-mark belongs to MARK, and --log-prefix belongs to LOG? What
| about the hypothetical case of several targets having target options
| with identical names?

How about:

iptables -A auth -i int+ -m mac --mac-source 00:00:00:00:00:00 \
~  -j MARK --set-mark 1 -j RETURN

and further:

iptables -A auth -i int+ -m mac --mac-source 00:00:00:00:00:00 \
~  -j MARK --set-mark 1 -j LOG --log-prefix "mark!" -j RETURN

This way the options would be clearly grouped and easily parsable. The
amount of targets (in the structs passed from/to userspace and used in
the kernel) could probably be made flexible, just like the matches are.
Even with the current iptables the target can be omitted, so it actually
already has some flexibility :)

This all would possibly, although not necessarily break binary
compatibility with the kernel. I am not familiar with the extendability
of the userspace "api"..

Even if it would break binary compatibility, I see how it could be
useful for users with large rulesets, since this could possibly halve
the amount of rules needed, and I think at that point these users might
be willing to recompile iptables to get that benefit, and of course
others who just like the comfort :)

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCWke2xyF48ZTvn+4RArC0AJ9pFgdW+kfBSstLRjumo2fTGvuTkwCeLf3M
YCvA+Z/rjQkWAJdlf2HgFRk=
=3twV
-----END PGP SIGNATURE-----

[-- Attachment #2: linux-2.6.10.patch --]
[-- Type: text/x-patch, Size: 7898 bytes --]

/home/xkr47/bin/Linux_AuthenticAMD/xkrdiff
diff --exclude-from=/tmp/srcdiff.excludes.tcxXkn -Np -x autoconf.h -ur history/140/linux/include/linux/netfilter_ipv4/ip_tables.h linux/include/linux/netfilter_ipv4/ip_tables.h
--- 140/include/linux/netfilter_ipv4/ip_tables.h	2005-03-16 17:09:11.000000000 +0200
+++ linux/include/linux/netfilter_ipv4/ip_tables.h	2005-03-17 02:17:33.000000000 +0200
@@ -110,6 +110,7 @@ struct ipt_counters
 /* Values for "flag" field in struct ipt_ip (general ip structure). */
 #define IPT_F_FRAG		0x01	/* Set if rule is a fragment rule */
-#define IPT_F_MASK		0x01	/* All possible flag bits mask. */
+#define IPT_F_PREVIOUS		0x02	/* Set if dependent on previous rule */
+#define IPT_F_MASK		0x03	/* All possible flag bits mask. */
 
 /* Values for "inv" field in struct ipt_ip. */
 #define IPT_INV_VIA_IN		0x01	/* Invert the sense of IN IFACE. */
@@ -120,7 +121,8 @@ struct ipt_counters
 #define IPT_INV_DSTIP		0x10	/* Invert the sense of DST OP. */
 #define IPT_INV_FRAG		0x20	/* Invert the sense of FRAG. */
 #define IPT_INV_PROTO		0x40	/* Invert the sense of PROTO. */
-#define IPT_INV_MASK		0x7F	/* All possible flag bits mask. */
+#define IPT_INV_PREVIOUS	0x80	/* Invert the sense of PREVIOUS. */
+#define IPT_INV_MASK		0xFF	/* All possible flag bits mask. */
 
 /* This structure defines each of the firewall rules.  Consists of 3
    parts which are 1) general IP header stuff 2) match specific
diff --exclude-from=/tmp/srcdiff.excludes.tcxXkn -Np -x autoconf.h -ur history/140/linux/include/linux/netfilter_ipv6/ip6_tables.h linux/include/linux/netfilter_ipv6/ip6_tables.h
--- 140/include/linux/netfilter_ipv6/ip6_tables.h	2005-03-16 17:09:16.000000000 +0200
+++ linux/include/linux/netfilter_ipv6/ip6_tables.h	2005-03-17 05:13:02.000000000 +0200
@@ -112,6 +112,7 @@ struct ip6t_counters
 					   protocols */
 #define IP6T_F_TOS		0x02	/* Match the TOS. */
-#define IP6T_F_MASK		0x03	/* All possible flag bits mask. */
+#define IP6T_F_PREVIOUS	0x04    /* Set if dependent on previous rule */
+#define IP6T_F_MASK		0x07    /* All possible flag bits mask. */
 
 /* Values for "inv" field in struct ip6t_ip6. */
 #define IP6T_INV_VIA_IN		0x01	/* Invert the sense of IN IFACE. */
@@ -122,7 +123,8 @@ struct ip6t_counters
 #define IP6T_INV_DSTIP		0x10	/* Invert the sense of DST OP. */
 #define IP6T_INV_FRAG		0x20	/* Invert the sense of FRAG. */
 #define IP6T_INV_PROTO		0x40	/* Invert the sense of PROTO. */
-#define IP6T_INV_MASK		0x7F	/* All possible flag bits mask. */
+#define IP6T_INV_PREVIOUS	0x80    /* Invert the sense of PREVIOUS. */
+#define IP6T_INV_MASK		0xFF    /* All possible flag bits mask. */
 
 /* This structure defines each of the firewall rules.  Consists of 3
    parts which are 1) general IP header stuff 2) match specific
diff --exclude-from=/tmp/srcdiff.excludes.tcxXkn -Np -x autoconf.h -ur history/140/linux/net/ipv4/netfilter/ip_tables.c linux/net/ipv4/netfilter/ip_tables.c
--- 140/net/ipv4/netfilter/ip_tables.c	2005-03-16 17:09:11.000000000 +0200
+++ linux/net/ipv4/netfilter/ip_tables.c	2005-03-17 05:07:34.000000000 +0200
@@ -131,7 +131,8 @@ ip_packet_match(const struct iphdr *ip,
 		const char *indev,
 		const char *outdev,
 		const struct ipt_ip *ipinfo,
-		int isfrag)
+		int isfrag,
+		int previous_matched)
 {
 	size_t i;
 	unsigned long ret;
@@ -201,6 +202,14 @@ ip_packet_match(const struct iphdr *ip,
 		return 0;
 	}
 
+	/* If we have a "previous" rule but the previous rule didn't match
+	 * then we return zero */
+	if (FWINV((ipinfo->flags&IPT_F_PREVIOUS) && !previous_matched, IPT_INV_PREVIOUS)) {
+		dprintf("Previous rule but previous didn't match.%s\n",
+			ipinfo->invflags & IPT_INV_PREVIOUS ? " (INV)" : "");
+		return 0;
+	}
+
 	return 1;
 }
 
@@ -274,6 +283,7 @@ ipt_do_table(struct sk_buff **pskb,
 	const char *indev, *outdev;
 	void *table_base;
 	struct ipt_entry *e, *back;
+	int previous_matched = 0; // update when and only when variable "e" changes
 
 	/* Initialization */
 	ip = (*pskb)->nh.iph;
@@ -314,14 +324,14 @@ ipt_do_table(struct sk_buff **pskb,
 		IP_NF_ASSERT(e);
 		IP_NF_ASSERT(back);
 		(*pskb)->nfcache |= e->nfcache;
-		if (ip_packet_match(ip, indev, outdev, &e->ip, offset)) {
+		if (ip_packet_match(ip, indev, outdev, &e->ip, offset, previous_matched)) {
 			struct ipt_entry_target *t;
 
 			if (IPT_MATCH_ITERATE(e, do_match,
 					      *pskb, in, out,
 					      offset, &hotdrop) != 0)
 				goto no_match;
-
+			
 			ADD_COUNTER(e->counters, ntohs(ip->tot_len), 1);
 
 			t = ipt_get_target(e);
@@ -340,6 +350,11 @@ ipt_do_table(struct sk_buff **pskb,
 					e = back;
 					back = get_entry(table_base,
 							 back->comefrom);
+
+					 /* return from chain, verdict must
+					    be 1 since we went there in the
+					    first place */
+					previous_matched = 1;
 					continue;
 				}
 				if (table_base + v
@@ -354,6 +369,10 @@ ipt_do_table(struct sk_buff **pskb,
 				}
 
 				e = get_entry(table_base, v);
+
+				/* gosub chain -> previous "undefined" when
+				   entering */
+				previous_matched = 0;
 			} else {
 				/* Targets which reenter must return
                                    abs. verdicts */
@@ -387,11 +406,14 @@ ipt_do_table(struct sk_buff **pskb,
 				else
 					/* Verdict */
 					break;
+
+				previous_matched = 1;
 			}
 		} else {
 
 		no_match:
 			e = (void *)e + e->next_offset;
+			previous_matched = 0;
 		}
 	} while (!hotdrop);
 
diff --exclude-from=/tmp/srcdiff.excludes.tcxXkn -Np -x autoconf.h -ur history/140/linux/net/ipv6/netfilter/ip6_tables.c linux/net/ipv6/netfilter/ip6_tables.c
--- 140/net/ipv6/netfilter/ip6_tables.c	2005-03-16 17:09:16.000000000 +0200
+++ linux/net/ipv6/netfilter/ip6_tables.c	2005-03-17 05:12:05.000000000 +0200
@@ -162,7 +162,8 @@ ip6_packet_match(const struct sk_buff *s
 		 const char *outdev,
 		 const struct ip6t_ip6 *ip6info,
 		 unsigned int *protoff,
-		 int *fragoff)
+		 int *fragoff,
+		 int previous_matched)
 {
 	size_t i;
 	unsigned long ret;
@@ -290,6 +291,15 @@ ip6_packet_match(const struct sk_buff *s
 			!(ip6info->invflags & IP6T_INV_PROTO))
 			return 0;
 	}
+
+	/* If we have a "previous" rule but the previous rule didn't match
+	 * then we return zero */
+	if (FWINV((ip6info->flags&IP6T_F_PREVIOUS) && !previous_matched, IP6T_INV_PREVIOUS)) {
+		dprintf("Previous rule but previous didn't match.%s\n",
+			ip6info->invflags & IP6T_INV_PREVIOUS ? " (INV)" : "");
+		return 0;
+	}
+
 	return 1;
 }
 
@@ -365,6 +375,7 @@ ip6t_do_table(struct sk_buff **pskb,
 	const char *indev, *outdev;
 	void *table_base;
 	struct ip6t_entry *e, *back;
+	int previous_matched = 0; // update when and only when variable "e" changes
 
 	/* Initialization */
 	indev = in ? in->name : nulldevname;
@@ -404,7 +415,7 @@ ip6t_do_table(struct sk_buff **pskb,
 		IP_NF_ASSERT(back);
 		(*pskb)->nfcache |= e->nfcache;
 		if (ip6_packet_match(*pskb, indev, outdev, &e->ipv6,
-			&protoff, &offset)) {
+			&protoff, &offset, previous_matched)) {
 			struct ip6t_entry_target *t;
 
 			if (IP6T_MATCH_ITERATE(e, do_match,
@@ -433,6 +444,11 @@ ip6t_do_table(struct sk_buff **pskb,
 					e = back;
 					back = get_entry(table_base,
 							 back->comefrom);
+
+					/* return from chain, verdict must
+					   be 1 since we went there in the
+					   first place */
+					previous_matched = 1;
 					continue;
 				}
 				if (table_base + v
@@ -447,6 +463,9 @@ ip6t_do_table(struct sk_buff **pskb,
 				}
 
 				e = get_entry(table_base, v);
+				/* gosub chain -> previous "undefined" when
+				   entering */
+				previous_matched = 0;
 			} else {
 				/* Targets which reenter must return
                                    abs. verdicts */
@@ -476,11 +495,14 @@ ip6t_do_table(struct sk_buff **pskb,
 				else
 					/* Verdict */
 					break;
+
+				previous_matched = 1;
 			}
 		} else {
 
 		no_match:
 			e = (void *)e + e->next_offset;
+			previous_matched = 0;
 		}
 	} while (!hotdrop);
 

[-- Attachment #3: help --]
[-- Type: text/plain, Size: 690 bytes --]

Add a flag that lets you use the result of the previous rule.

Can be used to optimize away unnecessary duplicate rule matching like:

  iptables -A INPUT -p tcp --dport 137 -j LOG --log-prefix windows
  iptables -A INPUT -p tcp --dport 137 -j DROP

with:

  iptables -A INPUT -p tcp --dport 137 -j LOG --log-prefix windows
  iptables -A INPUT --previous -j DROP

Also, when the matching has side-effects (like counters or rate limiters),
these can be avoided with --previous. Also, the inverse can be used, and
--previous can be used multiple times in a row.

It can also be used to simulate "goto" like this:

  iptables -A INPUT ... -j SOMEWHERE
  iptables -A INPUT --previous -j RETURN

Re: About matching (also was: Multiple Targets)

[Wang Jian]

Hi Jonas Berlin,

The problem is how to handle rule deletion, for example,

  iptables -A INPUT -p tcp --dport 137 -j LOG --log-prefix windows
  iptables --previous -j DROP

When the first rule is deleted, then the second --previous is gone?


On Mon, 11 Apr 2005 09:47:41 +0000, Jonas Berlin <xkr47@outerspace.dyndns.org> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Quoting Patrick Schaaf on 2005-04-07 06:43 UTC:
> 
> | Hmm, regarding --previous... Do we have two bits spare in the
> | general rule structure, which could indicate 'match just like
> | the previous match did', and 'match exactly if the previous
> | match did NOT match'?
> 
> Yes. IPT_F_MASK has many spare bits, and IPT_INV_MASK has exactly one
> bit left (same for ipv6).
> 
> | It we do have such bits spare, a general --previous-matched
> | and --previous-failed syntax might be easier than a new match
> | with signature change or percpu variables: all decision logic
> | stays properly localized in the table scanning main loop.
> 
> This is my implementation exactly. I also believe this does not break
> binary compatibility; it just extends the use of the bitmasks, and
> "older" iptables clients will just never set the bits in question - and
> in the other way around when the iptables binary supports --previous but
> the kernel doesnt no problems occur unless the user tries to use --previous.
> 
> | BTW, it just occurred to be that --previous-failed, a logical
> | consequence of the --previous idea :), is a nice thing to
> | have by itself: it permits proper if/then/else semantics
> | for nonterminating targets!
> 
> Naturally, I thought of this too.. :)
> 
> | iptables -A xxx --previous-failed -j LOG --log-prefix "NOT-thisandthat: "
> 
> actually..
> 
> iptables -A xxx ! --previous -j LOG ...
> 
> There's one slight peculiarity with the current implementation.. if one
> wants to use a target that works only for some specific protocol, say
> TARPIT, one needs to:
> 
> iptables -A INPUT --previous -p tcp -j TARPIT
> 
> .. I haven't yet investigated if it would be possible to inherit the
> protocol nicely..
> 
> I include only the kernel part of the patch for now so you can study and
> complain about it :) I have some pending fixes for ip6tables that I want
> to go in first before posting the iptables patch, which is trivial anyway..
> 
> I'm sorry for the long delay.. as you see from the patch it was done
> more than three weeks ago.. :/ Otoh I tested it properly only last week.
> 
> - ----
> 
> I have also been thinking a bit about the original suggestion by Ben La
> Monica in the thread "Multiple Targets" to allow multiple targets:
> 
> Quoting Patrick Schaaf on 2005-02-19 08:28 UTC:
> 
> |> iptables -A auth -i int+ -m mac --mac-source 00:00:00:00:00:00 -j
> |> MARK,RETURN --set-mark 1
> |> iptables -A auth -i int+ -m mac --mac-source 00:00:00:00:00:01 -j
> |> MARK,RETURN --set-mark 2
> |
> | Problem: target options. How would the commandline parser see that
> | --set-mark belongs to MARK, and --log-prefix belongs to LOG? What
> | about the hypothetical case of several targets having target options
> | with identical names?
> 
> How about:
> 
> iptables -A auth -i int+ -m mac --mac-source 00:00:00:00:00:00 \
> ~  -j MARK --set-mark 1 -j RETURN
> 
> and further:
> 
> iptables -A auth -i int+ -m mac --mac-source 00:00:00:00:00:00 \
> ~  -j MARK --set-mark 1 -j LOG --log-prefix "mark!" -j RETURN
> 
> This way the options would be clearly grouped and easily parsable. The
> amount of targets (in the structs passed from/to userspace and used in
> the kernel) could probably be made flexible, just like the matches are.
> Even with the current iptables the target can be omitted, so it actually
> already has some flexibility :)
> 
> This all would possibly, although not necessarily break binary
> compatibility with the kernel. I am not familiar with the extendability
> of the userspace "api"..
> 
> Even if it would break binary compatibility, I see how it could be
> useful for users with large rulesets, since this could possibly halve
> the amount of rules needed, and I think at that point these users might
> be willing to recompile iptables to get that benefit, and of course
> others who just like the comfort :)
> 
> - --
> - - xkr47
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (GNU/Linux)
> 
> iD8DBQFCWke2xyF48ZTvn+4RArC0AJ9pFgdW+kfBSstLRjumo2fTGvuTkwCeLf3M
> YCvA+Z/rjQkWAJdlf2HgFRk=
> =3twV
> -----END PGP SIGNATURE-----



-- 
  lark

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Wang Jian on 2005-04-13 00:48 UTC:
> The problem is how to handle rule deletion, for example,
> 
>   iptables -A INPUT -p tcp --dport 137 -j LOG --log-prefix windows
>   iptables --previous -j DROP
> 
> When the first rule is deleted, then the second --previous is gone?

Unfortunately not. It gets combined with the rule before that. Or if
there was no rule before that, it never matches.

If the official netfilter guys think that --previous rules should be
deleted also when parent is gone, I can look at how to implemenent that
at some point.

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCXG1WxyF48ZTvn+4RArUaAKCZ1fg4r0MUbaPA9xvC1EeTESjiLwCfTYFY
6e0f30D6sPZ/tEz8zMUzbo8=
=fU2n
-----END PGP SIGNATURE-----

Re: About matching (also was: Multiple Targets)

[Wang Jian]

Hi Jonas Berlin,

My idea is --previous is pseudo match and will duplicate the previous
match rule and mark itself a dup. When the previous rule is deleted,
this one will de-mark the dup, but the matching rule itself still makes
sense.


On Wed, 13 Apr 2005 00:52:40 +0000, Jonas Berlin <xkr47@outerspace.dyndns.org> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Quoting Wang Jian on 2005-04-13 00:48 UTC:
> > The problem is how to handle rule deletion, for example,
> > 
> >   iptables -A INPUT -p tcp --dport 137 -j LOG --log-prefix windows
> >   iptables --previous -j DROP
> > 
> > When the first rule is deleted, then the second --previous is gone?
> 
> Unfortunately not. It gets combined with the rule before that. Or if
> there was no rule before that, it never matches.
> 
> If the official netfilter guys think that --previous rules should be
> deleted also when parent is gone, I can look at how to implemenent that
> at some point.
> 
> - --
> - - xkr47
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (GNU/Linux)
> 
> iD8DBQFCXG1WxyF48ZTvn+4RArUaAKCZ1fg4r0MUbaPA9xvC1EeTESjiLwCfTYFY
> 6e0f30D6sPZ/tEz8zMUzbo8=
> =fU2n
> -----END PGP SIGNATURE-----



-- 
  lark

Re: About matching (also was: Multiple Targets)

[Patrick Schaaf]

> Quoting Wang Jian on 2005-04-13 00:48 UTC:
> > The problem is how to handle rule deletion, for example,
> > 
> >   iptables -A INPUT -p tcp --dport 137 -j LOG --log-prefix windows
> >   iptables --previous -j DROP
> > 
> > When the first rule is deleted, then the second --previous is gone?
> 
> Unfortunately not. It gets combined with the rule before that. Or if
> there was no rule before that, it never matches.
> 
> If the official netfilter guys think that --previous rules should be
> deleted also when parent is gone, I can look at how to implemenent that
> at some point.

Not that I'm an official netfilter guy, but I think that there should
not be any such automation. It will be up to the admin, and a delicate
task, to _write_ rules using --previous - why wouldn't one also trust the
admin to get deletion right, then?

In a programming language, even an IDE (although I don't use them),
I wouldn't expect the body of an if(){} statement to go away
automatically when I delete the if condition itself. Why should
it be different, here?

Finally, it could even be the desire of the admin to keep the --previous
rule, and have it match the rule before the deleted rule. The hypothetic
double-rule-deletion would make that impossible.

best regards
  Patrick

Re: About matching (also was: Multiple Targets)

[Patrick Schaaf]

Hello Wang Jian,

> My idea is --previous is pseudo match and will duplicate the previous
> match rule and mark itself a dup. When the previous rule is deleted,
> this one will de-mark the dup, but the matching rule itself still makes
> sense.

Upon deletion, the rule-to-be-deleted is still known in whatever
program is doing the deletion. So the duplication you describe
here does not make sense, even when we would _want_ the --previous
rule to automatically morph into the original rule. No dup marking
needed. Also no copying over matches, or something. Just this logic:
	is the rule following the to-be-deleted rule --previous?
	NO: proceed as always
	YES: delete the --previous rule, and leave the to-be-deleted
	rule undisturbed.

A more interesting problem is, what to do with
	iptables -A xxx -m this -m that -j DODAD
	iptables -A xxx ! --previous
i.e. a not-previous match. Upon deletion of the first of these rules,
how would you go about negating ALL those combined matches to form
a revived, ! --previous replacing rule line? Note: not all matches
even implement negation of all their parameters...

Also see my other mail: I think that all this is too complicated and
too restrictive on the admin of the machine, and should simply NOT
be done. The "more interesting" problem above, seems to confirm
this feeling :)

best regards
  Patrick

Re: About matching (also was: Multiple Targets)

[Jozsef Kadlecsik]

On Wed, 13 Apr 2005, Patrick Schaaf wrote:

> Also see my other mail: I think that all this is too complicated and
> too restrictive on the admin of the machine, and should simply NOT
> be done. The "more interesting" problem above, seems to confirm
> this feeling :)

I absolutely agree.

Rule evaluation should be improved by replacing the current linear
algorithm with some tree-based solution like nf-hipac. Or even with a tree
of internal IP sets ;-)

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: About matching (also was: Multiple Targets)

[Patrick Schaaf]

Hi Jozsef,

On Wed, Apr 13, 2005 at 09:03:14AM +0200, Jozsef Kadlecsik wrote:
> On Wed, 13 Apr 2005, Patrick Schaaf wrote:
> 
> > Also see my other mail: I think that all this is too complicated and
> > too restrictive on the admin of the machine, and should simply NOT
> > be done. The "more interesting" problem above, seems to confirm
> > this feeling :)
> 
> I absolutely agree.
> 
> Rule evaluation should be improved by replacing the current linear
> algorithm with some tree-based solution like nf-hipac. Or even with a tree
> of internal IP sets ;-)

Or with a code generator with proper common subexpression elimination.
Wasn't there a tcng project going that way? I sometimes think that
this must be the right approach, just because so much optimization
work went into gcc - and it can't be too hard, at least on current
server/desktop processors, when even a full kernel compile is only
one or two minutes...

BTW, I do find the general idea of '--previous' / '! --previous'
sensible and appealing, because it wouldn't cost much to implement,
and would give a tool to the ruleset writer to at least express
_some_ commonality.

It's just the "upon deletion, do magic when the next rule is --previous",
that I objected to.

best regards
  Patrick

Re: About matching (also was: Multiple Targets)

[Jozsef Kadlecsik]

Hi Patrick,

On Wed, 13 Apr 2005, Patrick Schaaf wrote:

> > Rule evaluation should be improved by replacing the current linear
> > algorithm with some tree-based solution like nf-hipac. Or even with a tree
> > of internal IP sets ;-)
>
> Or with a code generator with proper common subexpression elimination.
> Wasn't there a tcng project going that way? I sometimes think that
> this must be the right approach, just because so much optimization
> work went into gcc - and it can't be too hard, at least on current
> server/desktop processors, when even a full kernel compile is only
> one or two minutes...

Have you seen Compact Filter (http://www.cs.aau.dk/~mixxel/cf/)?
Even ported to 2.6.7, but with large rulesets the compiling of the filter
is as crawling as iptables itself.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: About matching (also was: Multiple Targets)

[Wang Jian]

Hi Patrick Schaaf,

Common subexpression aggregation should be the best way to go. But
before that is done, we should consider how to improve current scheme,
right? It is a short term vs. long term problem.

Although ! --previous can be done, I am against it with current scheme.
The current scheme is for line by line match, not for structured
semantic such as if-else. Structured rule matching semantic needs much
work for correctness of insertion or deletion.

The --previous is a speedup, it is by no means a structured change.

I will defend my idea of duplication mark. It does make sense. It keeps
user space compatibility very well.

Consider this

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN --previous -j ACTION2
iptables -A SOMECHAIN --previous -j RETURN

The user space doesn't do the real work. The kernel space code store the
rules like this:

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN -m this -m that -j ACTION2 (dup match)
iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)

When user space do delete, it do deletion as old days. But kernel, do
the trivial magic.

If delete the first

iptables -A SOMECHAIN -m this -m that -j ACTION2 <-- de-mark
iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)

If delete the second

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)

Do --previous insertion 

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN -m this -m that -j NEWACTION1 (dup match)
iptables -A SOMECHAIN -m this -m that -j ACTION2 (dup match)
iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)

Do non --previous insertion

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN -m newmatch -j NEWACTION1
iptables -A SOMECHAIN -m this -m that -j ACTION2 <-- de-mark
iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)


On Wed, 13 Apr 2005 09:14:27 +0200, Patrick Schaaf <bof@bof.de> wrote:

> Hi Jozsef,
> 
> On Wed, Apr 13, 2005 at 09:03:14AM +0200, Jozsef Kadlecsik wrote:
> > On Wed, 13 Apr 2005, Patrick Schaaf wrote:
> > 
> > > Also see my other mail: I think that all this is too complicated and
> > > too restrictive on the admin of the machine, and should simply NOT
> > > be done. The "more interesting" problem above, seems to confirm
> > > this feeling :)
> > 
> > I absolutely agree.
> > 
> > Rule evaluation should be improved by replacing the current linear
> > algorithm with some tree-based solution like nf-hipac. Or even with a tree
> > of internal IP sets ;-)
> 
> Or with a code generator with proper common subexpression elimination.
> Wasn't there a tcng project going that way? I sometimes think that
> this must be the right approach, just because so much optimization
> work went into gcc - and it can't be too hard, at least on current
> server/desktop processors, when even a full kernel compile is only
> one or two minutes...
> 
> BTW, I do find the general idea of '--previous' / '! --previous'
> sensible and appealing, because it wouldn't cost much to implement,
> and would give a tool to the ruleset writer to at least express
> _some_ commonality.
> 
> It's just the "upon deletion, do magic when the next rule is --previous",
> that I objected to.
> 
> best regards
>   Patrick



-- 
  lark

Re: About matching (also was: Multiple Targets)

[Patrick Schaaf]

> > Or with a code generator with proper common subexpression elimination.
> > Wasn't there a tcng project going that way? I sometimes think that
> > this must be the right approach, just because so much optimization
> > work went into gcc - and it can't be too hard, at least on current
> > server/desktop processors, when even a full kernel compile is only
> > one or two minutes...
> 
> Have you seen Compact Filter (http://www.cs.aau.dk/~mixxel/cf/)?
> Even ported to 2.6.7, but with large rulesets the compiling of the filter
> is as crawling as iptables itself.

Didn't notice before - thanks for the link, I'll look into it.
>From a first glance this does not seem to use gcc, right?

Maybe using a generate-C/compile-C approach would become more feasible
when both tcc (www.tinycc.org) and gcc are used. tcc is incredibly fast,
but probably a lot worse than gcc at optimizing - one could imagine ordinary
rule updates to usually be optimized using tcc, and only when the admin feels
they have a stable ruleset, they could press some button which then takes
the ruleset through gcc's optimizer.

(see my hands waving? :)

best regards
  Patrick

Re: About matching (also was: Multiple Targets)

[Jozsef Kadlecsik]

On Wed, 13 Apr 2005, Patrick Schaaf wrote:

> > Have you seen Compact Filter (http://www.cs.aau.dk/~mixxel/cf/)?
>
> From a first glance this does not seem to use gcc, right?

No, it's a rule-compiler and optimizer in userspace and the
compiled-optimized rules are pushed simply to the kernel using netlink.

> Maybe using a generate-C/compile-C approach would become more feasible
> when both tcc (www.tinycc.org) and gcc are used.

It seems I'm not on the track: what code would be generated in C?

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: About matching (also was: Multiple Targets)

[Patrick Schaaf]

> > Maybe using a generate-C/compile-C approach would become more feasible
> > when both tcc (www.tinycc.org) and gcc are used.
> 
> It seems I'm not on the track: what code would be generated in C?

Roughly, translate each chain into a C function, each table into a C
source file. Load the resulting object like you would load kernel
modules.

Some "standard" matches could be generated inline. Other, more complex
match functions, could be called like before. Maybe some of them would
be marked "const", to tell the compiler that calling them with exactly
the same arguments, will produce exactly the same results.

The compiler could then optimize all redundant checks within a chain
(C function), and an advanced compiler could even do whole-table
optimizations on the table's C source module.

(See, I can wave my hands some more :)

best regards
  Patrick

Re: About matching (also was: Multiple Targets)

[Martijn Lievaart]

Wang Jian wrote:

>Hi Patrick Schaaf,
>
>Common subexpression aggregation should be the best way to go. But
>before that is done, we should consider how to improve current scheme,
>right? It is a short term vs. long term problem.
>
>Although ! --previous can be done, I am against it with current scheme.
>The current scheme is for line by line match, not for structured
>semantic such as if-else. Structured rule matching semantic needs much
>work for correctness of insertion or deletion.
>
>The --previous is a speedup, it is by no means a structured change.
>
>I will defend my idea of duplication mark. It does make sense. It keeps
>user space compatibility very well.
>
>Consider this
>
>iptables -A SOMECHAIN -m this -m that -j ACTION1
>iptables -A SOMECHAIN --previous -j ACTION2
>iptables -A SOMECHAIN --previous -j RETURN
>
>The user space doesn't do the real work. The kernel space code store the
>rules like this:
>
>iptables -A SOMECHAIN -m this -m that -j ACTION1
>iptables -A SOMECHAIN -m this -m that -j ACTION2 (dup match)
>iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)
>
>When user space do delete, it do deletion as old days. But kernel, do
>the trivial magic.
>
>If delete the first
>
>iptables -A SOMECHAIN -m this -m that -j ACTION2 <-- de-mark
>iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)
>
>If delete the second
>
>iptables -A SOMECHAIN -m this -m that -j ACTION1
>iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)
>
>Do --previous insertion 
>
>iptables -A SOMECHAIN -m this -m that -j ACTION1
>iptables -A SOMECHAIN -m this -m that -j NEWACTION1 (dup match)
>iptables -A SOMECHAIN -m this -m that -j ACTION2 (dup match)
>iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)
>
>Do non --previous insertion
>
>iptables -A SOMECHAIN -m this -m that -j ACTION1
>iptables -A SOMECHAIN -m newmatch -j NEWACTION1
>iptables -A SOMECHAIN -m this -m that -j ACTION2 <-- de-mark
>iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)
>
>  
>

This is so non-intuitive it makes my head hurt. Also:

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN -m this -m that -j ACTION2 (dup match)
iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)

If delete the first

iptables -A SOMECHAIN -m this -m that -j ACTION2 <-- de-mark
iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)

Now reinsert the first:

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN -m this -m that -j ACTION2 <-- NO DUP MATCH ANYMORE
iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)


which is bad when any of the matches have side effects.

IMO a better course of action is to only allow deletion of the last match(es) in a "previous-chain", which could be the complete chain. So given the example above:


iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN --previous -j ACTION2
iptables -A SOMECHAIN --previous -j RETURN

This would only allow to delete the third, the third and the second or all three rules before a commit occurs. These semantics would also allow nicely for ! --previous.

The more I think about it, the more I like it. This in effect gives multiple targets. Now someone is bound to come up with the idea that it should also be possible to write

iptables -A SOMECHAIN -m this -m that -j ACTION1 -j ACTION2 -j RETURN

as syntactic sugar. This makes a lot of sense, but is not needed. Let some front-end tool compile the rules to the --previous form, don't burden netfilter with this, unless it can be implemented very easily, which I don't think it can. The semantics are to murky.

M4

Re: About matching (also was: Multiple Targets)

[Wang Jian]

Hi Martijn Lievaart,


On Wed, 13 Apr 2005 12:09:39 +0200, Martijn Lievaart <m@rtij.nl> wrote:

> 
> This is so non-intuitive it makes my head hurt. Also:
> 
> iptables -A SOMECHAIN -m this -m that -j ACTION1
> iptables -A SOMECHAIN -m this -m that -j ACTION2 (dup match)
> iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)
> 
> If delete the first
> 
> iptables -A SOMECHAIN -m this -m that -j ACTION2 <-- de-mark
> iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)
> 
> Now reinsert the first:
> 
> iptables -A SOMECHAIN -m this -m that -j ACTION1
> iptables -A SOMECHAIN -m this -m that -j ACTION2 <-- NO DUP MATCH ANYMORE
> iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)
> 
> 

Good catch. I am convinced.

> which is bad when any of the matches have side effects.
> 
> IMO a better course of action is to only allow deletion of the last match(es) in a "previous-chain", which could be the complete chain. So given the example above:
> 
> 
> iptables -A SOMECHAIN -m this -m that -j ACTION1
> iptables -A SOMECHAIN --previous -j ACTION2
> iptables -A SOMECHAIN --previous -j RETURN
> 
> This would only allow to delete the third, the third and the second or all three rules before a commit occurs. These semantics would also allow nicely for ! --previous.
> 

Good point. But insertion before the first?

And how about

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN --previous -j ACTION2
iptables -A SOMECHAIN !--previous -j ACTION3
iptables -A SOMECHAIN --previous -j RETURN

The ! --previous semantics is confusing in this case.


> The more I think about it, the more I like it. This in effect gives multiple targets. Now someone is bound to come up with the idea that it should also be possible to write
> 
> iptables -A SOMECHAIN -m this -m that -j ACTION1 -j ACTION2 -j RETURN
> 
> as syntactic sugar. This makes a lot of sense, but is not needed. Let some front-end tool compile the rules to the --previous form, don't burden netfilter with this, unless it can be implemented very easily, which I don't think it can. The semantics are to murky.
> 

Yes, this sound good.


-- 
  lark

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Martijn Lievaart on 2005-04-13 10:09 UTC:
> The more I think about it, the more I like it. This in effect gives
> multiple targets. Now someone is bound to come up with the idea that it
> should also be possible to write
> 
> iptables -A SOMECHAIN -m this -m that -j ACTION1 -j ACTION2 -j RETURN
> 
> as syntactic sugar. This makes a lot of sense, but is not needed. Let
> some front-end tool compile the rules to the --previous form, don't
> burden netfilter with this, unless it can be implemented very easily,
> which I don't think it can. The semantics are to murky.

Did you see the mail from me on Mon, 11 Apr 2005 09:47:41 +0000 ? It's
the first email with the subject
   "Re: About matching (also was: Multiple Targets)

I wrote some thoughts on how multiple targets could be implemented.

Regarding the rule byte & packet counters, I guess they would be updated
regardless of how the actions turn out.. (I guess that's how it works
now too)

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCXPwNxyF48ZTvn+4RAgXnAKCl+Th3X9iGTb0CMrkmKTBJ7sjFvgCg4PSv
p4DpDwdev7ZbrBAfmbkeJWE=
=Rp43
-----END PGP SIGNATURE-----

Re: About matching (also was: Multiple Targets)

[Martijn Lievaart]

Hi Jian (or is Wang your first name?)

Wang Jian wrote:

>>IMO a better course of action is to only allow deletion of the last match(es) in a "previous-chain", which could be the complete chain. So given the example above:
>>
>>
>>iptables -A SOMECHAIN -m this -m that -j ACTION1
>>iptables -A SOMECHAIN --previous -j ACTION2
>>iptables -A SOMECHAIN --previous -j RETURN
>>
>>This would only allow to delete the third, the third and the second or all three rules before a commit occurs. These semantics would also allow nicely for ! --previous.
>>
>>    
>>
>
>Good point. But insertion before the first?
>  
>

Yes, that cannot be (easily) automated. And that's a good point, it 
really screws up the whole idea of looking at this as if there are 
multiple actions on a single rule that can easily be manipulated. But if 
we lose that last requirement. Netfilter is not easy, we should not make 
it seemingly easy while actually making it more difficult. Rules using 
--previous cannot be seen apart form the rule they reference. In 
principle, they should be manipulated together. Being able to manipulate 
(delete, insert) rules inside such a "previous-chain" should be looked 
upon as a bonus.

I realise this makes the first rule special. It defines the match for 
the whole "previous-chain", but also gives the first action. If this 
really bothers you, you can always do:

iptables -A SOMECHAIN -m this -m that
iptables -A SOMECHAIN --previous -j ACTION1
iptables -A SOMECHAIN --previous -j ACTION2
iptables -A SOMECHAIN --previous -j RETURN

But how is that different from:

iptables -A SOMECHAIN -m this -m that -j TMPCHAIN
iptables -N TMPCHAIN
iptables -A TMPCHAIN -j ACTION1
iptables -A TMPCHAIN -j ACTION2

The only real advantage I can think of is that using --previous makes it easier to generate rules automatically. I know I could use it in my rule generator (not yet ready for distribution, but in production here). It also has the slight advantage of being slightly easier to read. However, I guess it is slightly less efficient than using temporary chains, especially if the condition does not match in general.

Also, rethinking deletion, the only requirement is that  one cannot 
commit deletion of a rule if  another rule points to it using 
--previous. What this implies depends on what you mean by points to, see 
below.

>And how about
>
>iptables -A SOMECHAIN -m this -m that -j ACTION1
>iptables -A SOMECHAIN --previous -j ACTION2
>iptables -A SOMECHAIN !--previous -j ACTION3
>iptables -A SOMECHAIN --previous -j RETURN
>
>The ! --previous semantics is confusing in this case.
>
>  
>

This is something that has to be decided upon. Does --previous match the 
previous rule, or the previous non-previous rule (iow the start of the 
--previous chain). Intuitively I would say the latter.

In that case your rules would be equivalent to:

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN --previous -j ACTION2
iptables -A SOMECHAIN --previous -j RETURN
iptables -A SOMECHAIN -j ACTION3

If --previous matches the previous rule, not the start of that "previous chain) the RETURN is executed if ACTION3 is executed (iow if the first rule did not match). This can be translated to the latter semantics as:

iptables -A SOMECHAIN -m this -m that -j ACTION1
iptables -A SOMECHAIN --previous -j ACTION2
iptables -A SOMECHAIN !--previous -j ACTION3
iptables -A SOMECHAIN !--previous -j RETURN


Which I find clearer.

Also, if --previous "points to" the first rule of the "previous-chain" we can allow deletion of any but that first rule (or the complete chain). Otherwise you're stuck with "only delete at the end" semantics (such as I described previously).



>>The more I think about it, the more I like it. This in effect gives
>>multiple targets. Now someone is bound to come up with the idea that it
>>should also be possible to write
>>
>>    
>>
>>iptables -A SOMECHAIN -m this -m that -j ACTION1 -j ACTION2 -j RETURN
>>
>>
>>as syntactic sugar. This makes a lot of sense, but is not needed. Let some front-end tool compile the rules to the --previous form, don't burden netfilter with this, unless it can be implemented very easily, which I don't think it can. The semantics are to murky.
>>
>>    
>>
>
>Yes, this sound good.
>
>  
>

Especially thinking about !--previous makes this burdensome, but guess 
what, it can be done!

iptables -A SOMECHAIN -m this -m that -j ACTION1 -j ACTION2 ! -j ACTION3 

Hmmmmm, I'm not convinced we should take this route. It looks nice at first, but how should this be printed? Manipulated?

M4

Re: About matching (also was: Multiple Targets)

[Patrick Schaaf]

> iptables -A SOMECHAIN -m this -m that
> iptables -A SOMECHAIN --previous -j ACTION1
> iptables -A SOMECHAIN --previous -j ACTION2
> iptables -A SOMECHAIN --previous -j RETURN
> 
> But how is that different from:
> 
> iptables -A SOMECHAIN -m this -m that -j TMPCHAIN
> iptables -N TMPCHAIN
> iptables -A TMPCHAIN -j ACTION1
> iptables -A TMPCHAIN -j ACTION2

It RETURNs to different places, i.e. to the caller of SOMECHAIN in the
first case, and to the next rule in SOMECHAIN for the second case.

BTW, anybody ever thought about giving -j RETURN an --up N option?

iptables -A SOMECHAIN -m this -m that -j TMPCHAIN
iptables -N TMPCHAIN
iptables -A TMPCHAIN -j ACTION1
iptables -A TMPCHAIN -j ACTION2
iptables -A TMPCHAIN -j RETURN --up 2

best regards
  Patrick

Re: About matching (also was: Multiple Targets)

[Martijn Lievaart]

Patrick Schaaf wrote:

>>iptables -A SOMECHAIN -m this -m that
>>iptables -A SOMECHAIN --previous -j ACTION1
>>iptables -A SOMECHAIN --previous -j ACTION2
>>iptables -A SOMECHAIN --previous -j RETURN
>>
>>But how is that different from:
>>
>>iptables -A SOMECHAIN -m this -m that -j TMPCHAIN
>>iptables -N TMPCHAIN
>>iptables -A TMPCHAIN -j ACTION1
>>iptables -A TMPCHAIN -j ACTION2
>>    
>>
>
>It RETURNs to different places, i.e. to the caller of SOMECHAIN in the
>first case, and to the next rule in SOMECHAIN for the second case.
>
>BTW, anybody ever thought about giving -j RETURN an --up N option?
>
>iptables -A SOMECHAIN -m this -m that -j TMPCHAIN
>iptables -N TMPCHAIN
>iptables -A TMPCHAIN -j ACTION1
>iptables -A TMPCHAIN -j ACTION2
>iptables -A TMPCHAIN -j RETURN --up 2
>
>  
>

Good catch! So even two liters coffee and a packet of sigarets is not 
enough to make me think clearly.

It /could/ be done with the GOTO action:

iptables -A SOMECHAIN -m this -m that -j GOTO --goto TMPCHAIN
iptables -N TMPCHAIN
iptables -A TMPCHAIN -j ACTION1
iptables -A TMPCHAIN -j ACTION2
iptables -A TMPCHAIN -j RETURN


IMO --previous has the advantage of readability here.

So there actually are three options to implement this. Either 
--previous, GOTO or RETURN --up. Advantages:

--previous: Readability
GOTO: Already in POM?
RETURN --up: Also useful in different scenarios?

M4

Re: About matching (also was: Multiple Targets)

[Martijn Lievaart]

Jonas Berlin wrote:

>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>Quoting Martijn Lievaart on 2005-04-13 10:09 UTC:
>  
>
>>The more I think about it, the more I like it. This in effect gives
>>multiple targets. Now someone is bound to come up with the idea that it
>>should also be possible to write
>>
>>iptables -A SOMECHAIN -m this -m that -j ACTION1 -j ACTION2 -j RETURN
>>
>>as syntactic sugar. This makes a lot of sense, but is not needed. Let
>>some front-end tool compile the rules to the --previous form, don't
>>burden netfilter with this, unless it can be implemented very easily,
>>which I don't think it can. The semantics are to murky.
>>    
>>
>
>Did you see the mail from me on Mon, 11 Apr 2005 09:47:41 +0000 ? It's
>the first email with the subject
>   "Re: About matching (also was: Multiple Targets)
>
>I wrote some thoughts on how multiple targets could be implemented.
>
>Regarding the rule byte & packet counters, I guess they would be updated
>regardless of how the actions turn out.. (I guess that's how it works
>now too)
>  
>

:-) So back full circle :-) I read it, but lost track of it in the chain.

I'm still not convinced we need this, but it /could/ be implemented 
using an (then internal) --previous match.

IF (and I'm still not convinced it's a good idea) this is implemented, 
there are three ways to do it as I see it now:
1) Either implement --previous wholy in the kernel and make the multiple 
targets part of the kernel interface.
2) Or make this syntactic sugar in the iptables binary.
3) Or don't use any form of --previous and implement it differently in 
the kernel.

1) and 3) are really equivalent from a users point of view, also from 
the viewpoint of binary compatibility. It's just an implementation 
detail. OTOH 2) can be implemented sanely in all the binaries (iptables, 
-save and -restore) but will make the kernel API divert semantically 
from the commandline API. I'm not sure we want that. I still would 
advocate to make an explicit --previous match with semantics as outlined 
in my previous mail. It implements the functionality we want (as Patrick 
points out in another mail you would need an -j RETURN --up 2 to 
implement the same, it can also be done with a GOTO).

M4

Re: About matching (also was: Multiple Targets)

[Henrik Nordstrom]

On Wed, 13 Apr 2005, Patrick Schaaf wrote:

> BTW, I do find the general idea of '--previous' / '! --previous'
> sensible and appealing, because it wouldn't cost much to implement,
> and would give a tool to the ruleset writer to at least express
> _some_ commonality.

imho you have this with jumps to a sub-chain today.. The jump rule is the 
condition, and the sub-chain has the list of actions to execute when this 
condition is true (and maybe more detailed conditions).

Regards
Henrik

Re: About matching (also was: Multiple Targets)

[Henrik Nordstrom]

On Wed, 13 Apr 2005, Wang Jian wrote:

> iptables -A SOMECHAIN -m this -m that -j ACTION1
> iptables -A SOMECHAIN -m this -m that -j ACTION2 (dup match)
> iptables -A SOMECHAIN -m this -m that -j RETURN (dup match)

If we would have matches indicate if they are const for the packet or 
volatile (i.e. random) then this could all be automatic in the kernel, and 
any later tree based approaches would benefit greatly from this info. No 
need for any user action at all, just updated kernel and userspace.

on a related note hipac has a hardcoded list of "const" iptables matches 
for pretty much this reason.

Regards
Henrik

Re: About matching (also was: Multiple Targets)

[Henrik Nordstrom]

On Wed, 13 Apr 2005, Martijn Lievaart wrote:

> The only real advantage I can think of is that using --previous makes it 
> easier to generate rules automatically.

In automatic rule generation it is just as easy to create a subchain as it 
is to remember to use --previous.

But as seen in another thread iptables (the userspace) do have some 
performance issues with large numbers of chains. But this in itself is not 
an argument for --previous (just a sign that the chain management could do 
with some improvement)

Regards
Henrik

Re: About matching (also was: Multiple Targets)

[Henrik Nordstrom]

On Wed, 13 Apr 2005, Patrick Schaaf wrote:

> BTW, anybody ever thought about giving -j RETURN an --up N option?

IIRC there was some talk about this when the --goto thing was discussed 
some many months (year?) ago, but I do not remember what the final 
conclusions was.

Personally I think it would be good, but I think there was some opposion 
(Harald?) from it being very confusing when the chain is called from more 
than one place..

Regards
Henrik

Re: About matching (also was: Multiple Targets)

[Ben La Monica]

On 4/13/05, Henrik Nordstrom <hno@marasystems.com> wrote:
> On Wed, 13 Apr 2005, Patrick Schaaf wrote:
> 
> > BTW, anybody ever thought about giving -j RETURN an --up N option?

I actually started working on a patch, but then someone mentioned that
it had to be binary compatible with the current iptables. The problem
being that RETURN is a special case. The --up N option is only like 15
lines of code if nobody minds the fact that you'll need to use a newer
version of the iptables binary and newer kernel. Since RETURN is just
an ipt_standard_target like DROP or ACCEPT.

Also, concerning the multiple targets for one match, what about a
module that did something like this:

iptables -I INPUT -p tcp -s 10.0.0.0/24 -j MULTIPLE --mjump ULOG
--ulog-prefix "bad" --mjump REJECT --reject-with tcp-reset

And then the MULTIPLE target would actually create the targets for
ULOG and REJECT, put them in a linked list, execute them in the order
received, and then use the last value to return to iptables with the
verdict.

Anyway, if you have any input regarding this, I can try to write it
this weekend.

-Ben

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Ben La Monica on 2005-04-14 08:01 UTC:

> I actually started working on a patch, but then someone mentioned that
> it had to be binary compatible with the current iptables. The problem
> being that RETURN is a special case. The --up N option is only like 15
> lines of code if nobody minds the fact that you'll need to use a newer
> version of the iptables binary and newer kernel. Since RETURN is just
> an ipt_standard_target like DROP or ACCEPT.

I think I'd rather decide on the calling side how up to go instead of on
the return side.

> Also, concerning the multiple targets for one match, what about a
> module that did something like this:
> 
> iptables -I INPUT -p tcp -s 10.0.0.0/24 -j MULTIPLE --mjump ULOG
> --ulog-prefix "bad" --mjump REJECT --reject-with tcp-reset
> 
> And then the MULTIPLE target would actually create the targets for
> ULOG and REJECT, put them in a linked list, execute them in the order
> received, and then use the last value to return to iptables with the
> verdict.

Interesting idea.. but I think I would still prefer to just write
support for multiple targets, e.g.

iptables ... -j MARK --set-mark 10 -j LOG --log-prefix "foo" -j ACCEPT

The structures currently hold exactly one target, I think it wouldn't be
too hard extending that to have multiple targets instead, just like
there already is support for multiple matches. I think it might even be
easier to implement this than to make targets work properly from a
"MULTIPLE" target.. but that's just my guess :)

Maybe one could use some unused bit in the structures to indicate that
multiple targets are in use in order to remain binary compatible..

> Anyway, if you have any input regarding this, I can try to write it
> this weekend.

Good luck :)

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCXjAwxyF48ZTvn+4RAtekAKChHmHI23Am8BaiAI2zYOQQB/mvogCg17EX
IVypyxHSJvVjbBQJdHzoPk4=
=pGSr
-----END PGP SIGNATURE-----

Re: About matching (also was: Multiple Targets)

[Wang Jian]

Hi Jonas Berlin,


On Thu, 14 Apr 2005 08:56:18 +0000, Jonas Berlin <xkr47@outerspace.dyndns.org> wrote:

> 
> Interesting idea.. but I think I would still prefer to just write
> support for multiple targets, e.g.
> 
> iptables ... -j MARK --set-mark 10 -j LOG --log-prefix "foo" -j ACCEPT
> 
> The structures currently hold exactly one target, I think it wouldn't be
> too hard extending that to have multiple targets instead, just like
> there already is support for multiple matches. I think it might even be
> easier to implement this than to make targets work properly from a
> "MULTIPLE" target.. but that's just my guess :)
> 
> Maybe one could use some unused bit in the structures to indicate that
> multiple targets are in use in order to remain binary compatible..
> 

I am for multiple targets support.

--previous is a hack and it is not very easy to implement in a clean way,
because of the semantics.

Multiple targets' semantics is clean. This is the advantage.


-- 
  lark

Re: About matching (also was: Multiple Targets)

[Henrik Nordstrom]

On Thu, 14 Apr 2005, Jonas Berlin wrote:

> Interesting idea.. but I think I would still prefer to just write
> support for multiple targets, e.g.
>
> iptables ... -j MARK --set-mark 10 -j LOG --log-prefix "foo" -j ACCEPT

All which is technically required for this while keeping full binary 
copatibility is to modify non-terminal targets to register themselves as 
matches in addition to targets.

The only thing holding this back is a conceptual design question if you 
should be allowed to mix non-terminal targets and matches freely, but this 
can be addressed in userspace if desired to force all non-terminal targets 
last in the match list.

Having more than one terminal target is nonsense ihmo.

Regards
Henrik

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Henrik Nordstrom on 2005-04-14 11:43 UTC:

> All which is technically required for this while keeping full binary
> copatibility is to modify non-terminal targets to register themselves as
> matches in addition to targets.

Ingenious! I didn't see this alternative evolution of Ben La Monica's
approach.

Does iptables have any requirement that matches have to be lowercase?

One thing that would not fall into this category is calling a subchain,
because the subchain can either be terminal or non-terminal. Thus, in
the light of not liking the -j RETURN --up N approach, I wonder if it
would be better to have a --return flag or similar to deprecate -j
RETURN so one can write -j SUBCHAIN --return .. I guess that would be
the only need for multi-targets after turning the non-terminal targets
into matches..

> The only thing holding this back is a conceptual design question if you
> should be allowed to mix non-terminal targets and matches freely, but
> this can be addressed in userspace if desired to force all non-terminal
> targets last in the match list.

I think the return values of targets used as matches should verified to
be IPT_CONTINUE (or whatever it was called) and syslog messages written
if that wasn't the case. In either case, the return value would not be
used for anything else..

> Having more than one terminal target is nonsense ihmo.

I agree.

I will be away until next Monday, but if you still haven't started
implementing this by then, I will probably give it a shot :) Otoh I
guess by then this already huge thread will be double the size that it
is now :)

Have a nice weekend,
- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCXm5KxyF48ZTvn+4RAuIjAJkB06iKB94pfgWov9YhlvU6bfAx5wCfVcnZ
b30ovalYYVqbdqfltKB0vP0=
=8NnI
-----END PGP SIGNATURE-----

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

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

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Jonas Berlin on 2005-04-14 13:21 UTC:

>>>All which is technically required for this while keeping full binary
>>>copatibility is to modify non-terminal targets to register themselves as
>>>matches in addition to targets.
> 
> Does iptables have any requirement that matches have to be lowercase?

It seemed not.

>>>The only thing holding this back is a conceptual design question if you
>>>should be allowed to mix non-terminal targets and matches freely, but
>>>this can be addressed in userspace if desired to force all non-terminal
>>>targets last in the match list.
> 
> I think the return values of targets used as matches should verified to
> be IPT_CONTINUE (or whatever it was called) and syslog messages written
> if that wasn't the case. In either case, the return value would not be
> used for anything else..

As a first test, I tested with the LOG target, since that's what people
mostly ask for :)

What I did was I made LOG register itself as both a target and a match.
I kept the name in uppercase which avoided creating new modules.

So this is how it works (I have tested it quickly):

  iptables -A OUTPUT [...] -m LOG --log-prefix "wohoo" -j ACCEPT

instead of:

  iptables -A OUTPUT [...] -j LOG --log-prefix "wohoo"
  iptables -A OUTPUT [...] -j ACCEPT


Alternative implementations:

a) Do you think my idea of updating each potential target with match
code is ok, or

b) should maybe iptables automatically let one use any non-builtin
target as a match directly, or

c) same as b) but instead only let one use targets that have a special
flag set in their ipt_target structure, or

d) same as c) but instead add another struct ipt_match_target interface
(and accompanying register_match_target()) that have modified function
prototypes with only arguments common to both matches and targets..

pros & cons:

a) is trivial to implement and error-prone due to its mechanical nature.
However it doesn't require any changes to the generic netfilter code.

b) unfortunately lets one use targets that are not suitable as matches,
but lets one use any target without updating all targets that could be
used as matches.

c) requires minimal updates to the targets that are suitable (adding one
line), but might be a bit hacky since it would convert match arguments
to target arguments and possibly not all arguments can be given sane
values..

d) requires more modification to the individual targets than c) but less
than a) and does not clutter the source code of the targets like a) does.

To make it clear, the patches attached are implemented according to a).

I would go for a) or d)..

> I will be away until next Monday, but if you still haven't started
> implementing this by then, I will probably give it a shot :) Otoh I

I took my time but here it is :)

Comments, please :)

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCeA3ixyF48ZTvn+4RAndpAJwJ8eQMOWdtwunqTXhOv/eJ8C1GnQCgrKYz
b3gX3rOJEtpkVzMs92zT3RE=
=oiRA
-----END PGP SIGNATURE-----

[-- Attachment #2: LOG-match-iptables.diff --]
[-- Type: text/x-patch, Size: 4290 bytes --]

diff -Np -ur orig-iptables-1.3.1/extensions/libipt_LOG.c iptables-1.3.1/extensions/libipt_LOG.c
--- orig-iptables-1.3.1/extensions/libipt_LOG.c	2005-04-02 09:38:39.000000000 +0300
+++ iptables-1.3.1/extensions/libipt_LOG.c	2005-05-04 01:59:01.000000000 +0300
@@ -111,10 +111,8 @@ parse_level(const char *level)
 static int
 parse(int c, char **argv, int invert, unsigned int *flags,
       const struct ipt_entry *entry,
-      struct ipt_entry_target **target)
+      struct ipt_log_info *loginfo)
 {
-	struct ipt_log_info *loginfo = (struct ipt_log_info *)(*target)->data;
-
 	switch (c) {
 	case '!':
 		if (*flags & IPT_LOG_OPT_LEVEL)
@@ -195,6 +193,25 @@ parse(int c, char **argv, int invert, un
 	return 1;
 }
 
+static int
+parse_target(int c, char **argv, int invert, unsigned int *flags,
+	     const struct ipt_entry *entry,
+	     struct ipt_entry_target **target)
+{
+	struct ipt_log_info *loginfo = (struct ipt_log_info *)(*target)->data;
+	return parse(c, argv, invert, flags, entry, loginfo);
+}
+
+static int
+parse_match(int c, char **argv, int invert, unsigned int *flags,
+	    const struct ipt_entry *entry,
+	    unsigned int *nfcache,
+	    struct ipt_entry_match **match)
+{
+	struct ipt_log_info *loginfo = (struct ipt_log_info *)(*match)->data;
+	return parse(c, argv, invert, flags, entry, loginfo);
+}
+
 /* Final check; nothing. */
 static void final_check(unsigned int flags)
 {
@@ -203,11 +220,9 @@ static void final_check(unsigned int fla
 /* Prints out the targinfo. */
 static void
 print(const struct ipt_ip *ip,
-      const struct ipt_entry_target *target,
+      const struct ipt_log_info *loginfo,
       int numeric)
 {
-	const struct ipt_log_info *loginfo
-		= (const struct ipt_log_info *)target->data;
 	unsigned int i = 0;
 
 	printf("LOG ");
@@ -241,13 +256,31 @@ print(const struct ipt_ip *ip,
 		printf("prefix `%s' ", loginfo->prefix);
 }
 
-/* Saves the union ipt_targinfo in parsable form to stdout. */
 static void
-save(const struct ipt_ip *ip, const struct ipt_entry_target *target)
+print_target(const struct ipt_ip *ip,
+	     const struct ipt_entry_target *target,
+	     int numeric)
 {
 	const struct ipt_log_info *loginfo
 		= (const struct ipt_log_info *)target->data;
+	print(ip, loginfo, numeric);
+}
+
+static void
+print_match(const struct ipt_ip *ip,
+	    const struct ipt_entry_match *match,
+	    int numeric)
+{
+	const struct ipt_log_info *loginfo
+		= (const struct ipt_log_info *)match->data;
+	print(ip, loginfo, numeric);
+}
+
 
+/* Saves the union ipt_targinfo in parsable form to stdout. */
+static void
+save(const struct ipt_ip *ip, const struct ipt_log_info *loginfo)
+{
 	if (strcmp(loginfo->prefix, "") != 0)
 		printf("--log-prefix \"%s\" ", loginfo->prefix);
 
@@ -264,8 +297,24 @@ save(const struct ipt_ip *ip, const stru
 		printf("--log-uid ");
 }
 
+static void
+save_target(const struct ipt_ip *ip, const struct ipt_entry_target *target)
+{
+	const struct ipt_log_info *loginfo
+		= (const struct ipt_log_info *)target->data;
+	save(ip, loginfo);
+}
+
+static void
+save_match(const struct ipt_ip *ip, const struct ipt_entry_match *match)
+{
+	const struct ipt_log_info *loginfo
+		= (const struct ipt_log_info *)match->data;
+	save(ip, loginfo);
+}
+
 static
-struct iptables_target log
+struct iptables_target log_target
 = {
     .name          = "LOG",
     .version       = IPTABLES_VERSION,
@@ -273,14 +322,30 @@ struct iptables_target log
     .userspacesize = IPT_ALIGN(sizeof(struct ipt_log_info)),
     .help          = &help,
     .init          = &init,
-    .parse         = &parse,
+    .parse         = &parse_target,
     .final_check   = &final_check,
-    .print         = &print,
-    .save          = &save,
+    .print         = &print_target,
+    .save          = &save_target,
     .extra_opts    = opts
 };
 
+static
+struct iptables_match log_match
+= { 
+	.name		= "LOG",
+	.version	= IPTABLES_VERSION,
+	.size		= IPT_ALIGN(sizeof(struct ipt_log_info)),
+	.userspacesize	= IPT_ALIGN(sizeof(struct ipt_log_info)),
+	.help		= &help,
+	.parse		= &parse_match,
+	.final_check	= &final_check,
+	.print		= &print_match,
+	.save		= &save_match,
+	.extra_opts	= opts
+};
+
 void _init(void)
 {
-	register_target(&log);
+	register_target(&log_target);
+	register_match(&log_match);
 }

[-- Attachment #3: LOG-match-linux-2.6.diff --]
[-- Type: text/x-patch, Size: 3941 bytes --]

diff -Np -ur orig-linux-2.6.11/net/ipv4/netfilter/ipt_LOG.c linux-2.6.11/net/ipv4/netfilter/ipt_LOG.c
--- orig-linux-2.6.11/net/ipv4/netfilter/ipt_LOG.c	2005-04-12 18:41:37.000000000 +0300
+++ linux-2.6.11/net/ipv4/netfilter/ipt_LOG.c	2005-05-04 01:40:14.000000000 +0300
@@ -350,8 +350,7 @@ static void dump_packet(const struct ipt
 }
 
 static void
-ipt_log_packet(unsigned int hooknum,
-	       const struct sk_buff *skb,
+ipt_log_packet(const struct sk_buff *skb,
 	       const struct net_device *in,
 	       const struct net_device *out,
 	       const struct ipt_log_info *loginfo,
@@ -408,11 +407,28 @@ ipt_log_target(struct sk_buff **pskb,
 	char level_string[4] = "< >";
 
 	level_string[1] = '0' + (loginfo->level % 8);
-	ipt_log_packet(hooknum, *pskb, in, out, loginfo, level_string, NULL);
+	ipt_log_packet(*pskb, in, out, loginfo, level_string, NULL);
 
 	return IPT_CONTINUE;
 }
 
+static int
+ipt_log_match(const struct sk_buff *skb,
+	      const struct net_device *in,
+	      const struct net_device *out,
+	      const void *matchinfo,
+	      int offset,
+	      int *hotdrop)
+{
+	const struct ipt_log_info *loginfo = matchinfo;
+	char level_string[4] = "< >";
+
+	level_string[1] = '0' + (loginfo->level % 8);
+	ipt_log_packet(skb, in, out, loginfo, level_string, NULL);
+
+	return 1;
+}
+
 static void
 ipt_logfn(unsigned int hooknum,
 	  const struct sk_buff *skb,
@@ -426,20 +442,19 @@ ipt_logfn(unsigned int hooknum,
 		.prefix = "" 
 	};
 
-	ipt_log_packet(hooknum, skb, in, out, &loginfo, KERN_WARNING, prefix);
+	ipt_log_packet(skb, in, out, &loginfo, KERN_WARNING, prefix);
 }
 
 static int ipt_log_checkentry(const char *tablename,
-			      const struct ipt_entry *e,
-			      void *targinfo,
-			      unsigned int targinfosize,
+			      void *info,
+			      unsigned int infosize,
 			      unsigned int hook_mask)
 {
-	const struct ipt_log_info *loginfo = targinfo;
+	const struct ipt_log_info *loginfo = info;
 
-	if (targinfosize != IPT_ALIGN(sizeof(struct ipt_log_info))) {
-		DEBUGP("LOG: targinfosize %u != %u\n",
-		       targinfosize, IPT_ALIGN(sizeof(struct ipt_log_info)));
+	if (infosize != IPT_ALIGN(sizeof(struct ipt_log_info))) {
+		DEBUGP("LOG: infosize %u != %u\n",
+		       infosize, IPT_ALIGN(sizeof(struct ipt_log_info)));
 		return 0;
 	}
 
@@ -457,20 +472,49 @@ static int ipt_log_checkentry(const char
 	return 1;
 }
 
-static struct ipt_target ipt_log_reg = {
+static int ipt_log_target_checkentry(const char *tablename,
+				     const struct ipt_entry *e,
+				     void *targinfo,
+				     unsigned int targinfosize,
+				     unsigned int hook_mask)
+{
+	return ipt_log_checkentry(tablename, targinfo, targinfosize, hook_mask);
+}
+
+static int ipt_log_match_checkentry(const char *tablename,
+				    const struct ipt_ip *ip,
+				    void *matchinfo,
+				    unsigned int matchinfosize,
+				    unsigned int hook_mask)
+{
+	return ipt_log_checkentry(tablename, matchinfo, matchinfosize, hook_mask);
+}
+
+static struct ipt_target ipt_log_target_reg = {
 	.name		= "LOG",
 	.target		= ipt_log_target,
-	.checkentry	= ipt_log_checkentry,
+	.checkentry	= ipt_log_target_checkentry,
+	.me		= THIS_MODULE,
+};
+
+static struct ipt_match ipt_log_match_reg = {
+	.name		= "LOG",
+	.match		= &ipt_log_match,
+	.checkentry	= &ipt_log_match_checkentry,
 	.me		= THIS_MODULE,
 };
 
 static int __init init(void)
 {
-	if (ipt_register_target(&ipt_log_reg))
+	if (ipt_register_target(&ipt_log_target_reg))
+		return -EINVAL;
+	if (ipt_register_match(&ipt_log_match_reg)) {
+		ipt_unregister_target(&ipt_log_target_reg);
 		return -EINVAL;
+	}
 	if (nflog)
 		nf_log_register(PF_INET, &ipt_logfn);
-	
+
 	return 0;
 }
 
@@ -478,7 +522,8 @@ static void __exit fini(void)
 {
 	if (nflog)
 		nf_log_unregister(PF_INET, &ipt_logfn);
-	ipt_unregister_target(&ipt_log_reg);
+	ipt_unregister_match(&ipt_log_match_reg);
+	ipt_unregister_target(&ipt_log_target_reg);
 }
 
 module_init(init);

Re: About matching (also was: Multiple Targets)

[Jozsef Kadlecsik]

Hi,

On Tue, 3 May 2005, Jonas Berlin wrote:

> >>>All which is technically required for this while keeping full binary
> >>>copatibility is to modify non-terminal targets to register themselves as
> >>>matches in addition to targets.
> >
> > Does iptables have any requirement that matches have to be lowercase?
>
> It seemed not.

Technically there is no such requirement. In practice there is a strict
naming convention: matches are always lovercase while targets are always
uppercase. I object any proposal changing that.

> Alternative implementations:
>
> a) Do you think my idea of updating each potential target with match
> code is ok, or
>
> b) should maybe iptables automatically let one use any non-builtin
> target as a match directly, or
>
> c) same as b) but instead only let one use targets that have a special
> flag set in their ipt_target structure, or
>
> d) same as c) but instead add another struct ipt_match_target interface
> (and accompanying register_match_target()) that have modified function
> prototypes with only arguments common to both matches and targets..

What I can see as viable solution is a flag, which tells which targets may
be used in cascade and let make it possible to type

... -j LOG -j DROP

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Jozsef Kadlecsik on 2005-05-04 07:16 UTC:
> What I can see as viable solution is a flag, which tells which targets may
> be used in cascade and let make it possible to type
> 
> ... -j LOG -j DROP

And if that flag was set, netfilter would also assert that the return
value of the target in question is IPT_CONTINUE ?

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCeHzsxyF48ZTvn+4RAvUTAJ4kmWF98U1lp2qjI9I6b7uRtcJ1LwCcD5MH
QxHQeh3a8c5u+iCOHUVqfP0=
=Faqq
-----END PGP SIGNATURE-----

Re: About matching (also was: Multiple Targets)

[Jozsef Kadlecsik]

On Wed, 4 May 2005, Jonas Berlin wrote:

> Quoting Jozsef Kadlecsik on 2005-05-04 07:16 UTC:
> > What I can see as viable solution is a flag, which tells which targets may
> > be used in cascade and let make it possible to type
> >
> > ... -j LOG -j DROP
>
> And if that flag was set, netfilter would also assert that the return
> value of the target in question is IPT_CONTINUE ?

No, targets may return other values. Something like this

#define IPT_TARGET_ITERATE(e, fn, args...)      \
({                                              \
        unsigned int __i;                       \
        int __ret = 0;                          \
        struct ipt_entry_target *__target;      \
                                                \
        for (__i = sizeof(struct ipt_entry)     \
                   + (e)->target_offset;        \
             __i < (e)->next_offset;            \
             __i += __target->u.target_size) {  \
                __target = (void *)(e) + __i;   \
                                                \
                __ret = fn(__target , ## args); \
                if (__ret != IPT_CONTINUE)      \
                        break;                  \
        }                                       \
        __ret;                                  \
})

would probably work.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Jozsef Kadlecsik on 2005-05-04 08:09 UTC:

>>And if that flag was set, netfilter would also assert that the return
>>value of the target in question is IPT_CONTINUE ?
> 
> No, targets may return other values. Something like this

I know. But my point was, _should_ these targets with the "cascade flag"
set be allowed to return anything else?

For example LOG, MARK, CONNMARK and CLASSIFY targets always return
IPT_CONTINUE. I could agree that NF_DROP could also be allowed if a bad
packet was recognized or some other problem. But should NF_STOLEN or
NF_REPEAT or others really be allowed from these targets with "cascade
flag" set? If there wasn't any restriction on the return value, I don't
know if there's much point of having a cascade flag either?

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFCeNQvxyF48ZTvn+4RAkPIAKCCUEHZkbRCX+1bMLjZOEqGYH9TCgCgjNBC
39EXx3x72L3by9iTJKyB7qo=
=Xmdn
-----END PGP SIGNATURE-----

Re: About matching (also was: Multiple Targets)

[Jozsef Kadlecsik]

On Wed, 4 May 2005, Jonas Berlin wrote:

> >>And if that flag was set, netfilter would also assert that the return
> >>value of the target in question is IPT_CONTINUE ?
> >
> > No, targets may return other values. Something like this
>
> I know. But my point was, _should_ these targets with the "cascade flag"
> set be allowed to return anything else?
>
> For example LOG, MARK, CONNMARK and CLASSIFY targets always return
> IPT_CONTINUE. I could agree that NF_DROP could also be allowed if a bad
> packet was recognized or some other problem. But should NF_STOLEN or
> NF_REPEAT or others really be allowed from these targets with "cascade
> flag" set? If there wasn't any restriction on the return value, I don't
> know if there's much point of having a cascade flag either?

In my opinion cascade targets should return IPT_CONTINUE. They may
return NF_DROP in error conditions, but other return values are not
allowed.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@sunserv.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Jozsef Kadlecsik on 2005-05-05 06:36 UTC:
> In my opinion cascade targets should return IPT_CONTINUE. They may
> return NF_DROP in error conditions, but other return values are not
> allowed.

Right.

How about hotdrop? I guess it should be checked in the
IPT_TARGET_ITERATE macro?

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFChxDXxyF48ZTvn+4RAnEQAKC6vOY1ucjHWxmUI7TJrFems2gtOACdFWsa
ELwbGpmrNwdcBT1WACkVBKQ=
=d18+
-----END PGP SIGNATURE-----

Re: About matching (also was: Multiple Targets)

[Jonas Berlin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quoting Jonas Berlin on 2005-05-15 09:05 UTC:
> How about hotdrop? I guess it should be checked in the
> IPT_TARGET_ITERATE macro?

Sorry, ignore, hotdrop is only for matches.. :)

- --
- - xkr47
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFChxKaxyF48ZTvn+4RAsyqAKCXQTGuDi/haIE/ajzpZtnCXphN5QCeMk6w
pdPt1CPdfnMEsE4dRAokPjc=
=jEwu
-----END PGP SIGNATURE-----