MARK target extension

MARK target extension

[Grzegorz Nosek]

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

Hello all!

I've extended the MARK target (ipv4 only currently) to allow partial
modification of nfmark values instead of replacing. As in:

... -j MARK --set-mark 0x80
... -j MARK --set-mark 0x8000 --mask 0xff00

sets the resulting mark value to 0x8080. Note that it isn't a logical OR:

... -j MARK --set-mark 0xffff
... -j MARK --set-mark 0 --mask 0xff

would change the mark to 0xff00.

This way you can use the nfmark as a bit field (testing individual
bits can be done already). Patches included are based on
iptables-1.2.9 (from debian sarge source) and kernel 2.4.26, somewhat
patched (nothing related to nfmark, though, so it should apply cleanly
to a vanilla kernel too). What do you think? IMNSHO it would be useful
to include in standard kernel/iptables especially as it breaks no
existing applications (default mask is 0xffffffff), is no code bloat
and might actually be useful to somebody besides me. Note that it's my
first public kernel patch so be gentle.

Regards,
 Greg


[-- Attachment #2: iptables-mark-1.2.9.diff --]
[-- Type: text/plain, Size: 2503 bytes --]

diff -Naur iptables-1.2.9/extensions/libipt_MARK.c iptables-1.2.9-mark/extensions/libipt_MARK.c
--- iptables-1.2.9/extensions/libipt_MARK.c	2003-03-02 17:16:45.000000000 +0100
+++ iptables-1.2.9-mark/extensions/libipt_MARK.c	2004-05-26 17:37:17.000000000 +0200
@@ -20,12 +20,14 @@
 	printf(
 "MARK target v%s options:\n"
 "  --set-mark value                   Set nfmark value\n"
+"  --mask value                       Set modification mask\n"
 "\n",
 IPTABLES_VERSION);
 }
 
 static struct option opts[] = {
 	{ "set-mark", 1, 0, '1' },
+	{ "mask", 1, 0, '2' },
 	{ 0 }
 };
 
@@ -33,6 +35,9 @@
 static void
 init(struct ipt_entry_target *t, unsigned int *nfcache)
 {
+	struct ipt_mark_target_info *markinfo =
+		(struct ipt_mark_target_info *)t->data;
+	markinfo->mask = 0xffffffff;
 }
 
 /* Function which parses command options; returns true if it
@@ -50,10 +55,20 @@
 		if (string_to_number(optarg, 0, 0xffffffff, 
 				     (unsigned int *)&markinfo->mark))
 			exit_error(PARAMETER_PROBLEM, "Bad MARK value `%s'", optarg);
-		if (*flags)
+		if (*flags & 1)
 			exit_error(PARAMETER_PROBLEM,
 			           "MARK target: Can't specify --set-mark twice");
-		*flags = 1;
+		*flags |= 1;
+		break;
+
+	case '2':
+		if (string_to_number(optarg, 0, 0xffffffff, 
+				     (unsigned int *)&markinfo->mask))
+			exit_error(PARAMETER_PROBLEM, "Bad mask value `%s'", optarg);
+		if (*flags & 2)
+			exit_error(PARAMETER_PROBLEM,
+			           "MARK target: Can't specify --mask twice");
+		*flags |= 2;
 		break;
 
 	default:
@@ -66,15 +81,17 @@
 static void
 final_check(unsigned int flags)
 {
-	if (!flags)
+	if ((flags & 1) == 0)
 		exit_error(PARAMETER_PROBLEM,
 		           "MARK target: Parameter --set-mark is required");
 }
 
 static void
-print_mark(unsigned long mark, int numeric)
+print_mark(unsigned long mark, unsigned long mask, int numeric)
 {
 	printf("0x%lx ", mark);
+	if (mask != 0xffffffff)
+		printf(" mask 0x%lx ", mask);
 }
 
 /* Prints out the targinfo. */
@@ -86,7 +103,7 @@
 	const struct ipt_mark_target_info *markinfo =
 		(const struct ipt_mark_target_info *)target->data;
 	printf("MARK set ");
-	print_mark(markinfo->mark, numeric);
+	print_mark(markinfo->mark, markinfo->mask, numeric);
 }
 
 /* Saves the union ipt_targinfo in parsable form to stdout. */
@@ -97,6 +114,8 @@
 		(const struct ipt_mark_target_info *)target->data;
 
 	printf("--set-mark 0x%lx ", markinfo->mark);
+	if (markinfo->mask != 0xffffffff)
+		printf("--mask 0x%lx ", markinfo->mask);
 }
 
 static

[-- Attachment #3: kernel-mark-2.4.26.diff --]
[-- Type: text/plain, Size: 1202 bytes --]

diff -Naur linux-2.4.26-ow1+route/include/linux/netfilter_ipv4/ipt_MARK.h linux-2.4.26-ow1+route+mark/include/linux/netfilter_ipv4/ipt_MARK.h
--- linux-2.4.26-ow1+route/include/linux/netfilter_ipv4/ipt_MARK.h	2000-03-17 19:56:20.000000000 +0100
+++ linux-2.4.26-ow1+route+mark/include/linux/netfilter_ipv4/ipt_MARK.h	2004-05-26 17:10:26.000000000 +0200
@@ -3,6 +3,7 @@
 
 struct ipt_mark_target_info {
 	unsigned long mark;
+	unsigned long mask;
 };
 
 #endif /*_IPT_MARK_H_target*/
diff -Naur linux-2.4.26-ow1+route/net/ipv4/netfilter/ipt_MARK.c linux-2.4.26-ow1+route+mark/net/ipv4/netfilter/ipt_MARK.c
--- linux-2.4.26-ow1+route/net/ipv4/netfilter/ipt_MARK.c	2001-09-30 21:26:08.000000000 +0200
+++ linux-2.4.26-ow1+route+mark/net/ipv4/netfilter/ipt_MARK.c	2004-05-26 17:18:49.000000000 +0200
@@ -16,9 +16,10 @@
        void *userinfo)
 {
 	const struct ipt_mark_target_info *markinfo = targinfo;
+	long new_mark = ((*pskb)->nfmark & ~markinfo->mask) | (markinfo->mark & markinfo->mask);
 
-	if((*pskb)->nfmark != markinfo->mark) {
-		(*pskb)->nfmark = markinfo->mark;
+	if((*pskb)->nfmark != new_mark) {
+		(*pskb)->nfmark = new_mark;
 		(*pskb)->nfcache |= NFC_ALTERED;
 	}
 	return IPT_CONTINUE;

Re: MARK target extension

[Patrick McHardy]

Grzegorz Nosek wrote:
> Hello all!
> 
> I've extended the MARK target (ipv4 only currently) to allow partial
> modification of nfmark values instead of replacing. As in:
> 
> ... -j MARK --set-mark 0x80
> ... -j MARK --set-mark 0x8000 --mask 0xff00
> 
> sets the resulting mark value to 0x8080. Note that it isn't a logical OR:
> 
> ... -j MARK --set-mark 0xffff
> ... -j MARK --set-mark 0 --mask 0xff
> 
> would change the mark to 0xff00.
> 
> This way you can use the nfmark as a bit field (testing individual
> bits can be done already). Patches included are based on
> iptables-1.2.9 (from debian sarge source) and kernel 2.4.26, somewhat
> patched (nothing related to nfmark, though, so it should apply cleanly
> to a vanilla kernel too). What do you think? IMNSHO it would be useful
> to include in standard kernel/iptables especially as it breaks no
> existing applications (default mask is 0xffffffff), is no code bloat
> and might actually be useful to somebody besides me. Note that it's my
> first public kernel patch so be gentle.

We already have a similar patch, MARK-operations, in pom-ng.
Unfortunately it can't be included in the stable series because
it breaks userspace compatibility.

Regards
Patrick

> 
> Regards,
>  Greg

Re: MARK target extension

[Grzegorz Nosek]

On Thu, 27 May 2004 11:53:08 +0200, Patrick McHardy wrote
> We already have a similar patch, MARK-operations, in pom-ng.
> Unfortunately it can't be included in the stable series because
> it breaks userspace compatibility.
> 
> Regards
> Patrick
> 

I had a look at the patch and it's indeed similar but supports only
single AND and OR operations and I think that it should allow more
flexibility. If you don't like the idea of adding another parameter,
maybe something like this would do:
--set-mark overrides all, without further questions
--and-mark and --or-mark are performed in sequence (thus more than one
allowed), so that (in my proposed syntax)
    --set-mark 0x1234 --mask 0xffff
(leaving top 16 bits untouched) could be expressed as
    --and-mark 0xffff0000 --or-mark 0x1234
It shouldn't break any existing applications either (they're using
only one of the parameters now).

It certainly is possible to get the same result using two consecutive
rules but it seems inefficient.

Regards,
 Greg

Re: MARK target extension

[Patrick McHardy]

Grzegorz Nosek wrote:

> I had a look at the patch and it's indeed similar but supports only
> single AND and OR operations and I think that it should allow more
> flexibility. If you don't like the idea of adding another parameter,
> maybe something like this would do:
> --set-mark overrides all, without further questions
> --and-mark and --or-mark are performed in sequence (thus more than one
> allowed), so that (in my proposed syntax)
>     --set-mark 0x1234 --mask 0xffff
> (leaving top 16 bits untouched) could be expressed as
>     --and-mark 0xffff0000 --or-mark 0x1234
> It shouldn't break any existing applications either (they're using
> only one of the parameters now).
> 
> It certainly is possible to get the same result using two consecutive
> rules but it seems inefficient.

I agree with you. CONNMARK seems to have the most flexible solution:
newmark = (ct->mark & ~markinfo->mask) | markinfo->mark;

Note that unlike with your patch, mark isn't ANDed with mask, so you can
also do a simple OR by setting mask to zero.

If you change your patch this way, and also make the userspace-part look
like CONNMARK (mark/mask instead of --mask), I'll happily replace the
MARK-operations patch.

Regards
Patrick

Re: MARK target extension

[Patrick McHardy]

Grzegorz Nosek wrote:
> On Sun, 06 Jun 2004 16:25:12 +0200, Patrick McHardy wrote
> 
>>I agree with you. CONNMARK seems to have the most flexible solution:
>>newmark = (ct->mark & ~markinfo->mask) | markinfo->mark;
> 
> Hmm I think I made it even more flexible by replacing the OR with XOR. 
> 
> --set-mark 0x80 - nfmark = 0x80
> --set-mark 0x80/0x80 - nfmark |= 0x80
> --set-mark 0x80/0 - nfmark ^= 0x80
> --set-mark 0x80/0xff - replace lowest 8 bits with 0x80
> --set-mark 0/0xff - clear lowest 8 bits
> --set-mark 0/0 - silly NOP
> etc.
> 
> With R and S being corresponding bits in mark and mask, you can set
> (RS=11), clear (RS=01), invert (RS=10) and leave intact (RS=00) any
> set of bits in the nfmark. What do you think?

Nice, although the xor operation (0x80/0) is a bit non-intuitive.

> 
>>Note that unlike with your patch, mark isn't ANDed with mask,
>> so you can also do a simple OR by setting mask to zero.
>>
>>If you change your patch this way, and also make the 
>>userspace-part look like CONNMARK (mark/mask instead of -
>>-mask), I'll happily replace the MARK-operations patch.
> 
> 
> Done and attached.

One of my concerns was that MARK and CONNMARK should look and behave
the same way. We should either change CONNMARK to also use xor, or
change your patch to using or. Henrik, what do you think ?

Regards
Patrick

> ------------------------------------------------------------------------
> 
> diff -Naur linux-2.4.26-ow1+route/include/linux/netfilter_ipv4/ipt_MARK.h linux-2.4.26-ow1+route+mark/include/linux/netfilter_ipv4/ipt_MARK.h
> --- linux-2.4.26-ow1+route/include/linux/netfilter_ipv4/ipt_MARK.h	2000-03-17 19:56:20.000000000 +0100
> +++ linux-2.4.26-ow1+route+mark/include/linux/netfilter_ipv4/ipt_MARK.h	2004-05-26 17:10:26.000000000 +0200
> @@ -3,6 +3,7 @@
>  
>  struct ipt_mark_target_info {
>  	unsigned long mark;
> +	unsigned long mask;
>  };
>  
>  #endif /*_IPT_MARK_H_target*/
> diff -Naur linux-2.4.26-ow1+route/net/ipv4/netfilter/ipt_MARK.c linux-2.4.26-ow1+route+mark/net/ipv4/netfilter/ipt_MARK.c
> --- linux-2.4.26-ow1+route/net/ipv4/netfilter/ipt_MARK.c	2001-09-30 21:26:08.000000000 +0200
> +++ linux-2.4.26-ow1+route+mark/net/ipv4/netfilter/ipt_MARK.c	2004-05-26 17:18:49.000000000 +0200
> @@ -16,9 +16,10 @@
>         void *userinfo)
>  {
>  	const struct ipt_mark_target_info *markinfo = targinfo;
> +	long new_mark = ((*pskb)->nfmark & ~markinfo->mask) ^ markinfo->mark;
>  
> -	if((*pskb)->nfmark != markinfo->mark) {
> -		(*pskb)->nfmark = markinfo->mark;
> +	if((*pskb)->nfmark != new_mark) {
> +		(*pskb)->nfmark = new_mark;
>  		(*pskb)->nfcache |= NFC_ALTERED;
>  	}
>  	return IPT_CONTINUE;
> 
> 

Re: MARK target extension

[Henrik Nordstrom]

On Wed, 9 Jun 2004, Patrick McHardy wrote:

> Nice, although the xor operation (0x80/0) is a bit non-intuitive.

And therefore also quite easy to get wrong.. for me the intuitive meaning
of 0x80/0 is to set bit 0x80 or nothing, not xor.

I do agree that it is nice to have the functionality of xor. 

May I propose that to solve this a userspace option is added "--xor-mark
value", and that mask 0 is probited in --set-mark if this representation
is used.

> One of my concerns was that MARK and CONNMARK should look and behave
> the same way. We should either change CONNMARK to also use xor, or
> change your patch to using or. Henrik, what do you think ?

I have no problem adjusting CONNMARK if a acceptable notation is found. It
has not yet been submitted to the kernel even if this has been favorly
discussed many times already.

Regards
Henrik

Re: MARK target extension

[Henrik Nordstrom]

On Thu, 10 Jun 2004, Grzegorz Nosek wrote:

> Taking this a little bit further, why not get rid of the /mask
> entirely as it's not exactly obvious what it means and replace them
> with more verbose --set-mark, --or-mark, --and-mark, --xor-mark?

Because the mask is far more powerful in the --set-mark.

--or-mark makes sense to add as an alternative human representation as
0x80/0x80 is not very intuitive unless one is used to work with masked
values, and even more so if value/0 is reserved for xor (mask 0 in
CONNMARK is today or, regardless of the value)

--and-mark also makes sense to add as an alternative representation of 
0/value

but both --or-mark and --and-mark can be represented in --set-mark by the
logics of --set-mark. It is only --xor-mark which can not.


> It would look like the mark-operations patch but should allow for
> multiple operations per line. --set-mark would prohibit any other
> options, --and-mark would be performed before --xor-mark. --or-mark
> would end up as a xor and a change to the and mask, as in: xor_mark =
> or_mark; and_mark = and_mark & ~or_mark; /* or something, I'm asleep
> right now */

If you like the userspace can allow for multiple and/or/set operations (in
any order). xor is exclusive with the other operations however unless the 
representation is extended with one more bitfield for xor.

> One side effect would be that upon iptables-save, all ORs would change
> to XORs "mysteriously" but there might be a way to detect ORs and
> treat them as such (xor_mask & and_mask == 0 or thereabouts).

Eh?

xor is a special case and will always be xor. xor can not be combined with 
anything else without extending the representation, and if the 
representation is extended xor is still cleraly separate from the other 
operation.

With the following binary representation and kernel function any
combination of set/and/or/xor can be represented:

  unsigned long value, mask, xor;


  newvalue = ((oldvalue & mask) | value) ^ xor;

or alternatively

  newvalue = ((oldvalue ^ xor ) & mask ) | value)


Userspace operations:


  --set-mark

      value |= specified_value;
      if (mask specified)
          mask |= specified_mask;
      else
          mask = ~0;

  --or-mark

      value |= specified_value;
      mask |= specified_value;

  --and-mark becomes

      if (mask = 0)
          mask = ~0;
      mask &= specified_value;

  --xor-mark becomes

      if (mask = 0)
          mask = ~0;
      xor |= specified_value;



If you like there can be appropriate asserts to alert the user if he is 
specifying conflicting operations on the same bit, but I am not sure if 
this is needed other than for xor.

Regards
Henrik

Re: MARK target extension

[Patrick McHardy]

On Wed, 2004-06-09 at 15:43, Henrik Nordstrom wrote:
> On Wed, 9 Jun 2004, Patrick McHardy wrote:
>
> I do agree that it is nice to have the functionality of xor. 
> 
> May I propose that to solve this a userspace option is added "--xor-mark
> value", and that mask 0 is probited in --set-mark if this representation
> is used.

Seems like a good way. I'm also going to add --and-mark and --or-mark as
alternative representations. I'll post the patch before applying it to
see if everyone is happy.

> > One of my concerns was that MARK and CONNMARK should look and behave
> > the same way. We should either change CONNMARK to also use xor, or
> > change your patch to using or. Henrik, what do you think ?
> 
> I have no problem adjusting CONNMARK if a acceptable notation is found. It
> has not yet been submitted to the kernel even if this has been favorly
> discussed many times already.

Yes, I know. I hope it will go in soon ..

Regards
Patrick

Re: MARK target extension

[Grzegorz Nosek]

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

On Sun, 13 Jun 2004 22:23:08 +0200, Patrick McHardy wrote
> On Wed, 2004-06-09 at 15:43, Henrik Nordstrom wrote:
> > On Wed, 9 Jun 2004, Patrick McHardy wrote:
> >
> > I do agree that it is nice to have the functionality of xor. 
> > 
> > May I propose that to solve this a userspace option is added
"--xor-mark
> > value", and that mask 0 is probited in --set-mark if this
representation
> > is used.
> 
> Seems like a good way. I'm also going to add --and-mark and -
> -or-mark as alternative representations. I'll post the patch 
> before applying it to see if everyone is happy.
> 
> > > One of my concerns was that MARK and CONNMARK should look and behave
> > > the same way. We should either change CONNMARK to also use xor, or
> > > change your patch to using or. Henrik, what do you think ?
> > 
> > I have no problem adjusting CONNMARK if a acceptable notation is
found. It
> > has not yet been submitted to the kernel even if this has been favorly
> > discussed many times already.
> 
> Yes, I know. I hope it will go in soon ..
> 
> Regards
> Patrick


Hello

I'm sorry I haven't replied earlier, I had connectivity problems (my
ISP sucks really bad...). Here's the reply I prepared earlier, I've
rewritten the code from scratch and I like it. I'd love to know your
input.

Regards,
 Greg

Several-days-old reply follows:
----------------------------------------------------------------
On Thu, 10 Jun 2004 11:59:35 +0200 (CEST), Henrik Nordstrom wrote
> On Thu, 10 Jun 2004, Grzegorz Nosek wrote:
> 
> > Taking this a little bit further, why not get rid of the /mask
> > entirely as it's not exactly obvious what it means and replace them
> > with more verbose --set-mark, --or-mark, --and-mark, --xor-mark?
> 
> Because the mask is far more powerful in the --set-mark.

Please check your opinion against my new code. :)

> 
> --or-mark makes sense to add as an alternative human 
> representation as 0x80/0x80 is not very intuitive unless one 
> is used to work with masked values, and even more so if 
> value/0 is reserved for xor (mask 0 in CONNMARK is today or, 
> regardless of the value)

value/0 isn't exactly reserved for XOR, every bit of value and mask is
treated separately, so you can mix all bit operations in a single
statement. As I've written several mails before (the bits have changed
with my latest patch!):

S - a bit of the mask
R - a bit of the mark value

SR |   | operation
---+---+-----------
00 | C | clear
01 | S | set
10 | N | no-op
11 | I | invert

I think that it gives the ultimate flexibility (four operations in two
bits) at the expense of some readability, which could be accomodated in
userspace.

> 
> --and-mark also makes sense to add as an alternative 
> representation of 0/value
> 
> but both --or-mark and --and-mark can be represented in -
> -set-mark by the logics of --set-mark. It is only --xor-mark 
> which can not.
> 

With the OR in kernel code, you're right, with the XOR, anything goes.

> > One side effect would be that upon iptables-save, all ORs would change
> > to XORs "mysteriously" but there might be a way to detect ORs and
> > treat them as such (xor_mask & and_mask == 0 or thereabouts).
> 
> Eh?

That was my sleeping brain trying to say that iptables-save would work
like this:

if (mask==~0)
    print "--set-mark " value
else if (mask == value)
    print "--or-mark " value
else
    print "--and-mark " mask " --xor-mark " value

It's still smarter (and tested at least) in my current patch, though 
(of course, any comments and improvements are welcome). This version
wouldn't probably do anything remotely correct now.

> 
> xor is a special case and will always be xor. xor can not be 
> combined with anything else without extending the 
> representation, and if the representation is extended xor is 
> still cleraly separate from the other operation.

OR can be expressed easily with AND and XOR so I'm not really sure
it's needed
as a separate value.

A | B = (A & (~B)) ^ B

Anything besides AND and XOR, while useful, is only syntactic sugar.

> 
> With the following binary representation and kernel function 
> any combination of set/and/or/xor can be represented:
> 
>   unsigned long value, mask, xor;
> 
>   newvalue = ((oldvalue & mask) | value) ^ xor;
> 
> or alternatively
> 
>   newvalue = ((oldvalue ^ xor ) & mask ) | value)
> 

But still, I don't see how it allows for anything more than a simple

   newvalue = (oldvalue & mask) ^ value;

BTW, I changed the `~mask' into `mask' in my kernel code, I can't seem to
remember the purpose of the negation.

> Userspace operations:
> 
>   --set-mark
> 
>       value |= specified_value;
>       if (mask specified)
>           mask |= specified_mask;
>       else
>           mask = ~0;
> 
>   --or-mark
> 
>       value |= specified_value;
>       mask |= specified_value;
> 
>   --and-mark becomes
> 
>       if (mask = 0)
>           mask = ~0;
>       mask &= specified_value;
> 
>   --xor-mark becomes
> 
>       if (mask = 0)
>           mask = ~0;
>       xor |= specified_value;
> 
> If you like there can be appropriate asserts to alert the 
> user if he is specifying conflicting operations on the same 
> bit, but I am not sure if this is needed other than for xor.
> 

After I scratched my head for a while on this issue (esp. overlapping
masks), I came up with a solution which:
+ is (IMHO) very user-friendly (I'd say DWIM)
+ is extremely flexible (unlimited number and unrestricted order of 
expressions)
- almost doubled the size of libipt_MARK.c
- may not be developer-friendly (obvious operation traded for a bit of
non-obvious implementation)
- may be overkill but I like it

I'll hopefully explain the basis of this idea below. (this might go 
into some README if the MARK target ever gets one)

Theory of operation
-------------------

The new MARK-ops algorithm is based on the fact that any bit can be
transformed in one of 4 ways: clear (00), set (01), no-op (10), invert
(11). Now, the elementary operations are defined as follows (by
examples, lowest 4 bits only):

--set-mark 1/3
	NNCS (leave top 2 bits alone, clear bit 1 and set bit 0)

It can be expressed as a value + mask pair:
m=1100 (~specified_mask)
v=0001 (specified_value)
Read vertically, the (mv) values are the same as the numbers in
parentheses above.

--and-mark 3
	CCNN (clear top 2 bits)
m=0011 (specified_value)
v=0000 (always zero)

--xor-mark 3
	NNII (invert lowest 2 bits)
m=1111 (always ones)
v=0011 (specified_value)

--or-mark 3
	NNSS (set lowest 2 bits)
m=1100 (~specified_value)
v=0011 (specified_value)

Now, this isn't in any way new or innovative and by itself it only
enables us to specify a single command per rule - definitely not 
enough. However, now we define a state diagram which tells us what the 
result of superimposing two states is:

 |CSIN
-+----
C|CSSC
S|CSCS
I|CSNI
N|CSIN

So, if you want to see what should happen to a bit which is set first
and then inverted, you consult the "S" row and "I" column and you know 
that it should be cleared (no surprise). So now we have a state machine 
whose state is represented by nth bit of mask and value (32 independent 
state machines, actually). For example:

--set-mark 1/3 --xor-mark 6

This statement is parsed starting with the --set-mark. We get NNCS 
encoded in mask and value and now we get to the xor. It gives NIIN and 
now we check the state diagram to check what happens to each of the 
bits:
 (bit 3) NN -> N
 (bit 2) NI -> I
 (bit 1) CI -> S
 (bit 0) SN -> S

So now we have the state NISS, which means "don't touch bit 3, invert 
bit 2 and set the lowest 2 ones". It's stored as:
m=1100
v=0111
which is the form directly used inside the kernel.

(old_mark & 0b1100) ^ 0b0111 (kernel code) is completely equivalent to 
what you might expect: ((old_mark & 0b1100) | 0b0001) ^ 0b0110 but 
does the calculation using only 2 logical operations.

Implementation details
----------------------

Replacing symbols (C,S,I,N) with their numerical values (00,01,11,10) 
we get the following table:

MV|00 01 11 10
--+-----------
00|00 01 01 00
01|00 01 00 01
11|00 01 10 11
10|00 01 11 10

It contains two-bit values which can be written in separate Karnaugh
tables:

M |00 01 11 10    V |00 01 11 10
--+-----------    --+-----------
00| 0  0  0  0    00| 0  1  1  0
01| 0  0  0  0    01| 0  1  0  1
11| 0  0  1  1    11| 0  1  0  1
10| 0  0  1  1    10| 0  1  1  0

Given that the two bits designating row are m0,v0 and m1,v1 designate 
the column, we can express the tables as the following functions:

M = m0 & m1
V = v1 ^ (v0 & m1)

And this is what function transfer_value() does. It probably is possible
to find these equations somehow simpler, without several pages of 
explanations, however this documents how I came up with these. Comments 
welcome, of course.

So in the end it turns out (for me at least) that although you may
specify the operation using the set-mark mask, it is unneccessary as 
now you can give the parameters in a mostly natural language (OR this, 
then XOR that and SET another...). And if you write some complex 
expression, you also get its simple{r,st} version for free. I think 
that given this power in --xxx-mark the internal representation 
(visible in VALUE/MASK) is mostly irrelevant as the user won't see it 
anyway.

> Regards
> Henrik

Regards,
 Greg


[-- Attachment #2: linux-2.4.26-mark.diff --]
[-- Type: application/octet-stream, Size: 1182 bytes --]

diff -Naur linux-2.4.26-ow1+route/include/linux/netfilter_ipv4/ipt_MARK.h linux-2.4.26-ow1+route-mark/include/linux/netfilter_ipv4/ipt_MARK.h
--- linux-2.4.26-ow1+route/include/linux/netfilter_ipv4/ipt_MARK.h	2000-03-17 19:56:20.000000000 +0100
+++ linux-2.4.26-ow1+route-mark/include/linux/netfilter_ipv4/ipt_MARK.h	2004-05-26 17:10:26.000000000 +0200
@@ -3,6 +3,7 @@
 
 struct ipt_mark_target_info {
 	unsigned long mark;
+	unsigned long mask;
 };
 
 #endif /*_IPT_MARK_H_target*/
diff -Naur linux-2.4.26-ow1+route/net/ipv4/netfilter/ipt_MARK.c linux-2.4.26-ow1+route-mark/net/ipv4/netfilter/ipt_MARK.c
--- linux-2.4.26-ow1+route/net/ipv4/netfilter/ipt_MARK.c	2001-09-30 21:26:08.000000000 +0200
+++ linux-2.4.26-ow1+route-mark/net/ipv4/netfilter/ipt_MARK.c	2004-06-12 01:06:06.000000000 +0200
@@ -16,9 +16,10 @@
        void *userinfo)
 {
 	const struct ipt_mark_target_info *markinfo = targinfo;
+	long new_mark = ((*pskb)->nfmark & markinfo->mask) | markinfo->mark;
 
-	if((*pskb)->nfmark != markinfo->mark) {
-		(*pskb)->nfmark = markinfo->mark;
+	if((*pskb)->nfmark != new_mark) {
+		(*pskb)->nfmark = new_mark;
 		(*pskb)->nfcache |= NFC_ALTERED;
 	}
 	return IPT_CONTINUE;

[-- Attachment #3: iptables-1.2.9-mark.diff --]
[-- Type: application/octet-stream, Size: 4839 bytes --]

diff -Naur iptables-1.2.9/extensions/libipt_MARK.c iptables-1.2.9-mark/extensions/libipt_MARK.c
--- iptables-1.2.9/extensions/libipt_MARK.c	2003-03-02 17:16:45.000000000 +0100
+++ iptables-1.2.9-mark/extensions/libipt_MARK.c	2004-06-12 03:26:23.000000000 +0200
@@ -3,6 +3,7 @@
 #include <string.h>
 #include <stdlib.h>
 #include <getopt.h>
+#include <errno.h>
 
 #include <iptables.h>
 #include <linux/netfilter_ipv4/ip_tables.h>
@@ -19,13 +20,21 @@
 {
 	printf(
 "MARK target v%s options:\n"
-"  --set-mark value                   Set nfmark value\n"
+"  --set-mark value[/mask]            Set nfmark value\n"
+"  --and-mark value                   Perform logical AND on nfmark and value\n"
+"  --xor-mark value                   Perform logical XOR on nfmark and value\n"
+"  --or-mark value                    Perform logical OR on nfmark and value\n"
+"\n"
+"Options can be specified multiple times, in any order.\n"
 "\n",
 IPTABLES_VERSION);
 }
 
 static struct option opts[] = {
 	{ "set-mark", 1, 0, '1' },
+	{ "and-mark", 1, 0, '2' },
+	{ "xor-mark", 1, 0, '3' },
+	{ "or-mark", 1, 0, '4' },
 	{ 0 }
 };
 
@@ -33,6 +42,38 @@
 static void
 init(struct ipt_entry_target *t, unsigned int *nfcache)
 {
+	struct ipt_mark_target_info *markinfo
+		= (struct ipt_mark_target_info *)t->data;
+
+	markinfo->mask = ~0UL;
+}
+
+/* Extract value/mask from a string */
+static void
+parse_arg(char* optarg, struct ipt_mark_target_info* markinfo, int mask_valid)
+{
+	char *tail, *tail2;
+	errno = 0;
+	markinfo->mark = strtoul(optarg, &tail, 0);
+	if (errno || (optarg == tail))
+		exit_error(PARAMETER_PROBLEM, "Bad MARK value `%s'", optarg);
+	if (*tail) {
+		if (!mask_valid || *tail != '/')
+			exit_error(PARAMETER_PROBLEM, "Bad MARK value `%s'", optarg);
+		errno = 0;
+		markinfo->mask = strtoul(tail+1, &tail2, 0);
+		if (errno || (tail2 == tail+1))
+			exit_error(PARAMETER_PROBLEM, "Bad mask value `%s'", tail+1);
+	}
+}
+
+/* State transfer function for subsequent operations on
+   the same bit in nfmark */
+static void
+transfer_value(struct ipt_mark_target_info *markinfo, struct ipt_mark_target_info op)
+{
+	markinfo->mark = op.mark ^ (markinfo->mark & op.mask);
+	markinfo->mask &= op.mask;
 }
 
 /* Function which parses command options; returns true if it
@@ -44,22 +85,39 @@
 {
 	struct ipt_mark_target_info *markinfo
 		= (struct ipt_mark_target_info *)(*target)->data;
+	struct ipt_mark_target_info op;
 
 	switch (c) {
 	case '1':
-		if (string_to_number(optarg, 0, 0xffffffff, 
-				     (unsigned int *)&markinfo->mark))
-			exit_error(PARAMETER_PROBLEM, "Bad MARK value `%s'", optarg);
-		if (*flags)
-			exit_error(PARAMETER_PROBLEM,
-			           "MARK target: Can't specify --set-mark twice");
-		*flags = 1;
+		parse_arg(optarg, &op, 1);
+		if (!op.mask)
+			op.mask = 0;
+		else
+			op.mask ^= ~0UL;
+		break;
+
+	case '2':
+		parse_arg(optarg, &op, 0);
+		op.mask = op.mark;
+		op.mark = 0;
+		break;
+
+	case '3':
+		parse_arg(optarg, &op, 0);
+		op.mask = ~0UL;
+		break;
+
+	case '4':
+		parse_arg(optarg, &op, 1);
+		op.mask = ~op.mark;
 		break;
 
 	default:
 		return 0;
 	}
 
+	transfer_value(markinfo, op);
+	*flags = 1;
 	return 1;
 }
 
@@ -68,13 +126,24 @@
 {
 	if (!flags)
 		exit_error(PARAMETER_PROBLEM,
-		           "MARK target: Parameter --set-mark is required");
+		           "MARK target: A parameter is required (see -j MARK --help)");
 }
 
 static void
-print_mark(unsigned long mark, int numeric)
+print_mark(unsigned long mark, unsigned long mask, int numeric)
 {
-	printf("0x%lx ", mark);
+	if (mask == 0)
+		printf("set 0x%lx ", mark);
+	else if (mark == ~mask)
+		printf("or 0x%lx ", mark);
+	else if ((mark & mask) == 0)
+		printf("set 0x%lx/0x%lx ", mark, ~mask);
+	else {
+		if (mask != ~0UL)
+			printf("and 0x%lx ", mask);
+		if (mark)
+			printf("xor 0x%lx ", mark);
+	}
 }
 
 /* Prints out the targinfo. */
@@ -85,8 +154,8 @@
 {
 	const struct ipt_mark_target_info *markinfo =
 		(const struct ipt_mark_target_info *)target->data;
-	printf("MARK set ");
-	print_mark(markinfo->mark, numeric);
+	printf("MARK ");
+	print_mark(markinfo->mark, markinfo->mask, numeric);
 }
 
 /* Saves the union ipt_targinfo in parsable form to stdout. */
@@ -96,7 +165,18 @@
 	const struct ipt_mark_target_info *markinfo =
 		(const struct ipt_mark_target_info *)target->data;
 
-	printf("--set-mark 0x%lx ", markinfo->mark);
+	if (markinfo->mask == 0)
+		printf("--set-mark 0x%lx ", markinfo->mark);
+	else if (markinfo->mark == ~markinfo->mask)
+		printf("--or-mark 0x%lx ", markinfo->mark);
+	else if ((markinfo->mark & markinfo->mask) == 0)
+		printf("--set-mark 0x%lx/0x%lx ", markinfo->mark, ~markinfo->mask);
+	else {
+		if (markinfo->mask != ~0UL)
+			printf("--and-mark 0x%lx ", markinfo->mask);
+		if (markinfo->mark)
+			printf("--xor-mark 0x%lx ", markinfo->mark);
+	}
 }
 
 static

Re: MARK target extension

[Henrik Nordstrom]

On Mon, 14 Jun 2004, Grzegorz Nosek wrote:

> S - a bit of the mask
> R - a bit of the mark value
> 
> SR |   | operation
> ---+---+-----------
> 00 | C | clear
> 01 | S | set
> 10 | N | no-op
> 11 | I | invert

Interesting encoding with a very nice kernel side algorithm.

> But still, I don't see how it allows for anything more than a simple
> 
>    newvalue = (oldvalue & mask) ^ value;

It doesn't. AND+XOR is logically complete and can represent all the 
bitwise logic operations in a very efficient manner in both space and 
time.

Note: The ~mask in CONNMARK was from the mask representing the bits to
modify, not the bits to save.

Regards
Henrik