[PKT_SCHED] cls_basic: Use unsigned int when generating handle

[PKT_SCHED] cls_basic: Use unsigned int when generating handle

[Thomas Graf]

Prevents filters from being added if the first generated
handle already exists.

Signed-off-by: Kim Nordlund <kim.nordlund@nokia.com>
Signed-off-by: Thomas Graf <tgraf@suug.ch>

Index: net-2.6/net/sched/cls_basic.c
===================================================================
--- net-2.6.orig/net/sched/cls_basic.c	2006-09-26 13:35:29.000000000 +0200
+++ net-2.6/net/sched/cls_basic.c	2006-09-26 13:35:39.000000000 +0200
@@ -194,7 +194,7 @@
 	if (handle)
 		f->handle = handle;
 	else {
-		int i = 0x80000000;
+		unsigned int i = 0x80000000;
 		do {
 			if (++head->hgenerator == 0x7FFFFFFF)
 				head->hgenerator = 1;

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[Patrick McHardy]

Thomas Graf wrote:
> Prevents filters from being added if the first generated
> handle already exists.
> 
> Signed-off-by: Kim Nordlund <kim.nordlund@nokia.com>
> Signed-off-by: Thomas Graf <tgraf@suug.ch>
> 
> Index: net-2.6/net/sched/cls_basic.c
> ===================================================================
> --- net-2.6.orig/net/sched/cls_basic.c	2006-09-26 13:35:29.000000000 +0200
> +++ net-2.6/net/sched/cls_basic.c	2006-09-26 13:35:39.000000000 +0200
> @@ -194,7 +194,7 @@
>  	if (handle)
>  		f->handle = handle;
>  	else {
> -		int i = 0x80000000;
> +		unsigned int i = 0x80000000;

I don't see how this patch changes anything, the loop already
ends when i == 0 (and it can't go negative):

        do {
                if (++head->hgenerator == 0x7FFFFFFF)
                        head->hgenerator = 1;
        } while (--i > 0 && basic_get(tp, head->hgenerator));

which should also make sure that no handle gets used twice:

        if (i <= 0) {
                printk(KERN_ERR "Insufficient number of handles\n");
                goto errout;
        }

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[Thomas Graf]

* Patrick McHardy <kaber@trash.net> 2006-09-26 15:32
> Thomas Graf wrote:
> > Prevents filters from being added if the first generated
> > handle already exists.
> > 
> > Signed-off-by: Kim Nordlund <kim.nordlund@nokia.com>
> > Signed-off-by: Thomas Graf <tgraf@suug.ch>
> > 
> > Index: net-2.6/net/sched/cls_basic.c
> > ===================================================================
> > --- net-2.6.orig/net/sched/cls_basic.c	2006-09-26 13:35:29.000000000 +0200
> > +++ net-2.6/net/sched/cls_basic.c	2006-09-26 13:35:39.000000000 +0200
> > @@ -194,7 +194,7 @@
> >  	if (handle)
> >  		f->handle = handle;
> >  	else {
> > -		int i = 0x80000000;
> > +		unsigned int i = 0x80000000;
> 
> I don't see how this patch changes anything, the loop already
> ends when i == 0 (and it can't go negative):
> 
>         do {
>                 if (++head->hgenerator == 0x7FFFFFFF)
>                         head->hgenerator = 1;
>         } while (--i > 0 && basic_get(tp, head->hgenerator));
> 
> which should also make sure that no handle gets used twice:
> 
>         if (i <= 0) {
>                 printk(KERN_ERR "Insufficient number of handles\n");
>                 goto errout;
>         }

You're right, 0x80000000 - 1 is already positive. Ignore the patch.

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[Nordlund Kim (Nokia-NET/Helsinki)]

On Tue, 26 Sep 2006, ext Thomas Graf wrote:
> You're right, 0x80000000 - 1 is already positive. Ignore the patch.

basic_change() won't work without this patch if we compile the
kernel with the GCC version in RHEL5...

gcc version 4.1.1 20060817 (Red Hat 4.1.1-18)

which optimizes the code like this (objdump -S inttest.c) ...

int main()
{
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
  int i = 0x80000000;
  do {
    printf(KERN_ERR "in do %d\n", i);
   3:   68 00 00 00 80          push   $0x80000000
   8:   68 00 00 00 00          push   $0x0
   d:   e8 fc ff ff ff          call   e <main+0xe>
  } while (--i > 0);
  printf(KERN_ERR "out of do %d\n", i);
  12:   68 00 00 00 80          push   $0x80000000
  17:   68 0a 00 00 00          push   $0xa
  1c:   e8 fc ff ff ff          call   1d <main+0x1d>
  return 0;
}
  21:   31 c0                   xor    %eax,%eax
  23:   c9                      leave
  24:   c3                      ret

# ./inttest
in do -2147483648
out of do -2147483648

gcc -m32 -Wall -Wundef -Wstrict-prototypes -Wno-trigraphs 
-fno-strict-aliasing -fno-common -Wstrict-prototypes -Wundef 
-Werror-implicit-function-declaration  -fno-stack-protector -Os 
-fno-omit-frame-pointer -fno-optimize-sibling-calls 
-fasynchronous-unwind-tables -g -pipe -msoft-float 
-fno-builtin-sprintf -fno-builtin-log2 -fno-builtin-puts  
-mpreferred-stack-boundary=2  -march=i686 -mtune=generic 
-mtune=generic -mregparm=3 -ffreestanding 
-Wdeclaration-after-statement -Wno-pointer-sign   -c -o 
inttest.o inttest.c

So I would suggest to apply this patch to be compatible with the
GCC version in RHEL5, and simply to make code clearer (to the
intended idea).

--KimN

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[Thomas Graf]

* Nordlund Kim (Nokia-NET/Helsinki) <Kim.Nordlund@nokia.com> 2006-09-27 11:50
> basic_change() won't work without this patch if we compile the
> kernel with the GCC version in RHEL5...
> 
> gcc version 4.1.1 20060817 (Red Hat 4.1.1-18)
> 
> which optimizes the code like this (objdump -S inttest.c) ...
> 
> int main()
> {
>    0:   55                      push   %ebp
>    1:   89 e5                   mov    %esp,%ebp
>   int i = 0x80000000;
>   do {
>     printf(KERN_ERR "in do %d\n", i);
>    3:   68 00 00 00 80          push   $0x80000000
>    8:   68 00 00 00 00          push   $0x0
>    d:   e8 fc ff ff ff          call   e <main+0xe>
>   } while (--i > 0);
>   printf(KERN_ERR "out of do %d\n", i);
>   12:   68 00 00 00 80          push   $0x80000000
>   17:   68 0a 00 00 00          push   $0xa
>   1c:   e8 fc ff ff ff          call   1d <main+0x1d>
>   return 0;
> }
>   21:   31 c0                   xor    %eax,%eax
>   23:   c9                      leave
>   24:   c3                      ret
> 
> # ./inttest
> in do -2147483648
> out of do -2147483648

Very interesting, naturally I tried the same after Patrick's
comment but gcc 20060901 produced code as expected, thus
staying in the loop. But now after specifying -Os gcc seems
to turn on some optimziation which produces the same code as
above.

I'm not sure I understand this optimization :-)

> So I would suggest to apply this patch to be compatible with the
> GCC version in RHEL5, and simply to make code clearer (to the
> intended idea).

Yes.

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[Patrick McHardy]

Thomas Graf wrote:
> * Nordlund Kim (Nokia-NET/Helsinki) <Kim.Nordlund@nokia.com> 2006-09-27 11:50
> 
>>So I would suggest to apply this patch to be compatible with the
>>GCC version in RHEL5, and simply to make code clearer (to the
>>intended idea).
> 
> 
> Yes.

I don't care much about this small change, but I think bugs
should be fixed where they originate. If RH's gcc miscompiles
this with -Os I wouldn't trust it anyway, and the easy way to
fix it seems to be to deactivate CONFIG_CC_OPTIMIZE_FOR_SIZE,
which even includes a big warning of broken compilers.
What about the similar code in u32 and cbq?

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[Thomas Graf]

* Patrick McHardy <kaber@trash.net> 2006-09-27 11:44
> Thomas Graf wrote:
> > * Nordlund Kim (Nokia-NET/Helsinki) <Kim.Nordlund@nokia.com> 2006-09-27 11:50
> > 
> >>So I would suggest to apply this patch to be compatible with the
> >>GCC version in RHEL5, and simply to make code clearer (to the
> >>intended idea).
> > 
> > 
> > Yes.
> 
> I don't care much about this small change, but I think bugs
> should be fixed where they originate.

Absolutely, I'm not even sure who's fault it really is. When
writing that code I must have expected gcc to correctly
underflow which might have been a wrong assumption.

I think it doesn't matter whether this is a gcc bug or not,
having this code part wort with gcc 4.1 is a good thing anyway.

> If RH's gcc miscompiles
> this with -Os I wouldn't trust it anyway, and the easy way to
> fix it seems to be to deactivate CONFIG_CC_OPTIMIZE_FOR_SIZE,
> which even includes a big warning of broken compilers.

gcc >= 4.1 seems to produce this code with either -Os or -O2
so the range of affected useres might in fact be bigger.

> What about the similar code in u32 and cbq?

Not affected by this.

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[Nordlund Kim (Nokia-NET/Helsinki)]

On Wed, 27 Sep 2006, ext Thomas Graf wrote:

> gcc >= 4.1 seems to produce this code with either -Os or -O2
> so the range of affected useres might in fact be bigger.

I believe gcc >= 4.1 is just updating to match ISO/IEC 9899:1999: 
This piece of code crosses undefined behaviour as defined in

    3.4.3
    1 undefined behavior
    behavior, upon use of a nonportable or erroneous program construct or
    of erroneous data,
    for which this International Standard imposes no requirements
    2 NOTE Possible undefined behavior ranges from ignoring the situation
    completely with unpredictable
    results, to behaving during translation or program execution in a
    documented manner characteristic of the
    environment (with or without the issuance of a diagnostic message),
    to terminating a translation or
    execution (with the issuance of a diagnostic message).
    3 EXAMPLE An example of undefined behavior is the behavior on integer
    overflow.

For undefined types there is no overflow:

    6.2.5 Types

    9 The range of nonnegative values of a signed integer type is a
    subrange of the
    corresponding unsigned integer type, and the representation of the
    same value in each
    type is the same.31) A computation involving unsigned operands can
    never overflow,
    because a result that cannot be represented by the resulting unsigned
    integer type is
    reduced modulo the number that is one greater than the largest value
    that can be
    represented by the resulting type.

But for signed types it falls under this:

    6.5 Expressions
    5 If an exceptional condition occurs during the evaluation of an
    expression (that is, if the
    result is not mathematically defined or not in the range of
    representable values for its
    type), the behavior is undefined.

Already the initial assignment of 0x80000000 to int falls under this:

    6.3.1.3 Signed and unsigned integers
    1 When a value with integer type is converted to another integer type
    other than _Bool, if
    the value can be represented by the new type, it is unchanged.
    2 Otherwise, if the new type is unsigned, the value is converted by
    repeatedly adding or
    subtracting one more than the maximum value that can be represented
    in the new type
    until the value is in the range of the new type.49)
    3 Otherwise, the new type is signed and the value cannot be
    represented in it; either the
    result is implementation-defined or an implementation-defined signal
    is raised.

Of course it can be argued whether the gcc optimization is sane. But it
seems not to be wrong, and there is no justification for writing the code
to be unspecified.

--KimN

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[David Miller]

From: "Nordlund Kim (Nokia-NET/Helsinki)" <Kim.Nordlund@nokia.com>
Date: Wed, 27 Sep 2006 14:45:21 +0300 (EEST)

> But for signed types it falls under this:
> 
>     6.5 Expressions
>     5 If an exceptional condition occurs during the evaluation of an
>     expression (that is, if the
>     result is not mathematically defined or not in the range of
>     representable values for its
>     type), the behavior is undefined.
> 
> Already the initial assignment of 0x80000000 to int falls under this:
> 
>     6.3.1.3 Signed and unsigned integers
>     1 When a value with integer type is converted to another integer type
>     other than _Bool, if
>     the value can be represented by the new type, it is unchanged.
>     2 Otherwise, if the new type is unsigned, the value is converted by
>     repeatedly adding or
>     subtracting one more than the maximum value that can be represented
>     in the new type
>     until the value is in the range of the new type.49)
>     3 Otherwise, the new type is signed and the value cannot be
>     represented in it; either the
>     result is implementation-defined or an implementation-defined signal
>     is raised.
> 
> Of course it can be argued whether the gcc optimization is sane. But it
> seems not to be wrong, and there is no justification for writing the code
> to be unspecified.

Correct, and actually this undefined behavior turns out to be
critical for several types of loop optimizations which I feel
totally justifies the interpretation gcc is using now.

I'll apply Thomas's original patch, thanks.

Re: [PKT_SCHED] cls_basic: Use unsigned int when generating handle

[David Miller]

From: Thomas Graf <tgraf@suug.ch>
Date: Tue, 26 Sep 2006 13:59:10 +0200

> Prevents filters from being added if the first generated
> handle already exists.
> 
> Signed-off-by: Kim Nordlund <kim.nordlund@nokia.com>
> Signed-off-by: Thomas Graf <tgraf@suug.ch>

Applied, I'll push this to -stable too.