[PATCH] fork_init: fix division by zero

[PATCH] fork_init: fix division by zero

[Yuri Tikhonov]

The following patch fixes divide-by-zero error for the
cases of really big PAGE_SIZEs (e.g. 256KB on ppc44x).
Support for such big page sizes on 44x is not present in the
current kernel yet, but coming soon.

Also this patch fixes the comment for the max_threads
settings, as this didn't match the things actually done
in the code.

Signed-off-by: Yuri Tikhonov <yur@emcraft.com>
Signed-off-by: Ilya Yanok <yanok@emcraft.com>
---
 kernel/fork.c |    8 ++++++--
 1 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/kernel/fork.c b/kernel/fork.c
index 2a372a0..b0ac2fb 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -181,10 +181,14 @@ void __init fork_init(unsigned long mempages)
 
 	/*
 	 * The default maximum number of threads is set to a safe
-	 * value: the thread structures can take up at most half
-	 * of memory.
+	 * value: the thread structures can take up at most
+	 * (1/8) part of memory.
 	 */
+#if (8 * THREAD_SIZE) > PAGE_SIZE
 	max_threads = mempages / (8 * THREAD_SIZE / PAGE_SIZE);
+#else
+	max_threads = mempages * PAGE_SIZE / (8 * THREAD_SIZE);
+#endif
 
 	/*
 	 * we need to allow at least 20 threads to boot a system
-- 
1.5.6.1

Re: [PATCH] fork_init: fix division by zero

[Geert Uytterhoeven]

On Tue, 9 Dec 2008, Yuri Tikhonov wrote:
> The following patch fixes divide-by-zero error for the
> cases of really big PAGE_SIZEs (e.g. 256KB on ppc44x).
> Support for such big page sizes on 44x is not present in the
> current kernel yet, but coming soon.
> 
> Also this patch fixes the comment for the max_threads
> settings, as this didn't match the things actually done
> in the code.
> 
> Signed-off-by: Yuri Tikhonov <yur@emcraft.com>
> Signed-off-by: Ilya Yanok <yanok@emcraft.com>
> ---
>  kernel/fork.c |    8 ++++++--
>  1 files changed, 6 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/fork.c b/kernel/fork.c
> index 2a372a0..b0ac2fb 100644
> --- a/kernel/fork.c
> +++ b/kernel/fork.c
> @@ -181,10 +181,14 @@ void __init fork_init(unsigned long mempages)
>  
>  	/*
>  	 * The default maximum number of threads is set to a safe
> -	 * value: the thread structures can take up at most half
> -	 * of memory.
> +	 * value: the thread structures can take up at most
> +	 * (1/8) part of memory.
>  	 */
> +#if (8 * THREAD_SIZE) > PAGE_SIZE
>  	max_threads = mempages / (8 * THREAD_SIZE / PAGE_SIZE);
> +#else
> +	max_threads = mempages * PAGE_SIZE / (8 * THREAD_SIZE);
                      ^^^^^^^^^^^^^^^^^^^^
> +#endif

Can't this overflow, e.g. on 32-bit machines with HIGHMEM?

With kind regards,

Geert Uytterhoeven
Software Architect

Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

Phone:    +32 (0)2 700 8453
Fax:      +32 (0)2 700 8622
E-mail:   Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/

A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010

Re[2]: [PATCH] fork_init: fix division by zero

[Yuri Tikhonov]

=0D=0A Hello Geert,

On Wednesday, December 10, 2008 you wrote:
> On Tue, 9 Dec 2008, Yuri Tikhonov wrote:
>> The following patch fixes divide-by-zero error for the
>> cases of really big PAGE_SIZEs (e.g. 256KB on ppc44x).
>> Support for such big page sizes on 44x is not present in the
>> current kernel yet, but coming soon.
>>=20
>> Also this patch fixes the comment for the max_threads
>> settings, as this didn't match the things actually done
>> in the code.
>>=20
>> Signed-off-by: Yuri Tikhonov <yur@emcraft.com>
>> Signed-off-by: Ilya Yanok <yanok@emcraft.com>
>> ---
>>  kernel/fork.c |    8 ++++++--
>>  1 files changed, 6 insertions(+), 2 deletions(-)
>>=20
>> diff --git a/kernel/fork.c b/kernel/fork.c
>> index 2a372a0..b0ac2fb 100644
>> --- a/kernel/fork.c
>> +++ b/kernel/fork.c
>> @@ -181,10 +181,14 @@ void __init fork_init(unsigned long mempages)
>> =20
>>       /*
>>        * The default maximum number of threads is set to a safe
>> -      * value: the thread structures can take up at most half
>> -      * of memory.
>> +      * value: the thread structures can take up at most
>> +      * (1/8) part of memory.
>>        */
>> +#if (8 * THREAD_SIZE) > PAGE_SIZE
>>       max_threads =3D mempages / (8 * THREAD_SIZE / PAGE_SIZE);
>> +#else
>> +     max_threads =3D mempages * PAGE_SIZE / (8 * THREAD_SIZE);
>                       ^^^^^^^^^^^^^^^^^^^^
>> +#endif

> Can't this overflow, e.g. on 32-bit machines with HIGHMEM?

 The multiplier here is not PAGE_SIZE, but [PAGE_SIZE / (8 *=20
THREAD_SIZE)], and this value is expected to be rather small (2, 4, or=20
so).

 Furthermore, due to the #if/#endif construction multiplication is=20
used only with rather big PAGE_SIZE values, and the bigger page size=20
is then the smaller 'mempages' is.

 So, for example, when running with PAGE_SIZE=3D256KB, THREAD_SIZE=3D8KB,=
=20
on 32-bit 440spe-based machine with 4GB RAM installed, here we have:

 max_threads =3D (4G/256K) * (256K / 8 * 8K) =3D 16384 * 4 =3D 65536.

 And the overflow will have a place only in case of very very big=20
sizes of RAM: >=3D 256TB:

 max_threads =3D (256T / 256K) * (256K / 8 * 8K) =3D 0x4000.0000 * 4.

 But I don't think that with 256TB RAM installed this code will be=20
the only place of problems :)

 Regards, Yuri

 --
 Yuri Tikhonov, Senior Software Engineer
 Emcraft Systems, www.emcraft.com

Re: [PATCH] fork_init: fix division by zero

[Al Viro]

On Wed, Dec 10, 2008 at 01:01:13PM +0300, Yuri Tikhonov wrote:

> >> +     max_threads = mempages * PAGE_SIZE / (8 * THREAD_SIZE);
> >                       ^^^^^^^^^^^^^^^^^^^^
> >> +#endif
> 
> > Can't this overflow, e.g. on 32-bit machines with HIGHMEM?
> 
>  The multiplier here is not PAGE_SIZE, but [PAGE_SIZE / (8 * 
> THREAD_SIZE)], and this value is expected to be rather small (2, 4, or 
> so).

x * y / z is parsed as (x * y) / z, not x * (y / z).

Only assignment operators (and ?:, in a sense that a ? b : c ? d : e is
parsed as a ? b : (c ? d : e)) are right-to-left.  The rest is left-to-right.

Re[2]: [PATCH] fork_init: fix division by zero

[Yuri Tikhonov]

=0D=0A Hello Al,

On Wednesday, December 10, 2008 you wrote:

> On Wed, Dec 10, 2008 at 01:01:13PM +0300, Yuri Tikhonov wrote:

>> >> +     max_threads =3D mempages * PAGE_SIZE / (8 * THREAD_SIZE);
>> >                       ^^^^^^^^^^^^^^^^^^^^
>> >> +#endif
>>=20
>> > Can't this overflow, e.g. on 32-bit machines with HIGHMEM?
>>=20
>>  The multiplier here is not PAGE_SIZE, but [PAGE_SIZE / (8 *=20
>> THREAD_SIZE)], and this value is expected to be rather small (2, 4, or=
=20
>> so).

> x * y / z is parsed as (x * y) / z, not x * (y / z).

 Here we believe in preprocessor: since all PAGE_SIZE, 8, and=20
THREAD_SIZE are the constants we expect it will calculate this.

 E.g. here is the result from this line as produced by cross-gcc=20
4.2.2:

        lis     r9,0
        rlwinm  r29,r29,2,16,29
        stw     r29,0(r9)

 As you see - only rotate-left, i.e. multiplication to the constant.

 In any case, adding braces as follows probably would be better:

+     max_threads =3D mempages * (PAGE_SIZE / (8 * THREAD_SIZE));

 Right ?

> Only assignment operators (and ?:, in a sense that a ? b : c ? d : e is
> parsed as a ? b : (c ? d : e)) are right-to-left.  The rest is left-to-ri=
ght.



 Regards, Yuri

 --
 Yuri Tikhonov, Senior Software Engineer
 Emcraft Systems, www.emcraft.com

Re: [PATCH] fork_init: fix division by zero

[Scott Wood]

On Wed, Dec 10, 2008 at 01:29:12PM +0300, Yuri Tikhonov wrote:
> On Wednesday, December 10, 2008 you wrote:
> > x * y / z is parsed as (x * y) / z, not x * (y / z).
> 
>  Here we believe in preprocessor: since all PAGE_SIZE, 8, and 
> THREAD_SIZE are the constants we expect it will calculate this.
> 
>  E.g. here is the result from this line as produced by cross-gcc 
> 4.2.2:
> 
>         lis     r9,0
>         rlwinm  r29,r29,2,16,29
>         stw     r29,0(r9)
> 
>  As you see - only rotate-left, i.e. multiplication to the constant.

Yes, and also note that it is masking the result by 0xfffc, to preserve
the effect of any overflow in (x * y).

-Scott

Re[2]: [PATCH] fork_init: fix division by zero

[Yuri Tikhonov]

=0D=0AHello Scott,

On Wednesday, December 10, 2008 you wrote:

> On Wed, Dec 10, 2008 at 01:29:12PM +0300, Yuri Tikhonov wrote:
>> On Wednesday, December 10, 2008 you wrote:
>> > x * y / z is parsed as (x * y) / z, not x * (y / z).
>>=20
>>  Here we believe in preprocessor: since all PAGE_SIZE, 8, and=20
>> THREAD_SIZE are the constants we expect it will calculate this.
>>=20
>>  E.g. here is the result from this line as produced by cross-gcc=20
>> 4.2.2:
>>=20
>>         lis     r9,0
>>         rlwinm  r29,r29,2,16,29
>>         stw     r29,0(r9)
>>=20
>>  As you see - only rotate-left, i.e. multiplication to the constant.

> Yes, and also note that it is masking the result by 0xfffc, to preserve
> the effect of any overflow in (x * y).

 Right, such a mask was the result of missed brackets. Now (see=20
"[PATCH][v2] fork_init: fix division by zero" I've just posted) the=20
situation is better:

        lis     r9,0
        rlwinm  r29,r29,2,0,29
        stw     r29,0(r9)

 I.e. the mask is 0xFFFFFFFC.

 Regards, Yuri

 --
 Yuri Tikhonov, Senior Software Engineer
 Emcraft Systems, www.emcraft.com

Re: Re[2]: [PATCH] fork_init: fix division by zero

[David Howells]

Yuri Tikhonov <yur@emcraft.com> wrote:

>  Here we believe in preprocessor: since all PAGE_SIZE, 8, and 
> THREAD_SIZE are the constants we expect it will calculate this.

The preprocessor shouldn't be calculating this.  I believe it will _only_
calculate expressions for #if.  In the situation you're referring to, it
should perform a substitution and nothing more.  The preprocessor doesn't
necessarily know how to handle the types involved.

In any case, there's an easy way to find out: you can ask the compiler to give
you the result of running the source through the preprocessor only.  For
instance, if you run this:

	#define PAGE_SIZE 4096
	#define THREAD_SIZE 8192
	unsigned long mempages;
	unsigned long jump(void)
	{
		unsigned long max_threads;
		max_threads = mempages * PAGE_SIZE / (8 * THREAD_SIZE);
		return max_threads;
	}

through "gcc -E", you get:

	# 1 "calc.c"
	# 1 "<built-in>"
	# 1 "<command line>"
	# 1 "calc.c"
	unsigned long mempages;
	unsigned long jump(void)
	{
	 unsigned long max_threads;
	 max_threads = mempages * 4096 / (8 * 8192);
	 return max_threads;
	}


>  In any case, adding braces as follows probably would be better:
> 
> +     max_threads = mempages * (PAGE_SIZE / (8 * THREAD_SIZE));

I think you mean brackets, not braces '{}'.

>  Right ?

Definitely not.

I added this function to the above:

	unsigned long alt(void)
	{
		unsigned long max_threads;
		max_threads = mempages * (PAGE_SIZE / (8 * THREAD_SIZE));
		return max_threads;
	}

and ran it through "gcc -S -O2" for x86_64:

	jump:
		movq    mempages(%rip), %rax
		salq    $12, %rax
		shrq    $16, %rax
		ret
	alt:
		xorl    %eax, %eax
		ret

Note the difference?  In jump(), x86_64 first multiplies mempages by 4096, and
_then_ divides by 8*8192.

In alt(), it just returns 0 because the compiler realised that you're
multiplying by 0.

If you're going to bracket the expression, it must be:

		max_threads = (mempages * PAGE_SIZE) / (8 * THREAD_SIZE);

which should be superfluous.

>  E.g. here is the result from this line as produced by cross-gcc 
> 4.2.2:
> 
>         lis     r9,0
>         rlwinm  r29,r29,2,16,29
>         stw     r29,0(r9)
> 
>  As you see - only rotate-left, i.e. multiplication to the constant.

Ummm...  On powerpc, I believe rotate-left would be a division as it does the
bit-numbering and the bit direction the opposite way to more familiar CPUs
such as x86.

David

Re: Re[2]: [PATCH] fork_init: fix division by zero

[Geert Uytterhoeven]

On Wed, 10 Dec 2008, David Howells wrote:
> Yuri Tikhonov <yur@emcraft.com> wrote:
> >  In any case, adding braces as follows probably would be better:
> > 
> > +     max_threads = mempages * (PAGE_SIZE / (8 * THREAD_SIZE));
> 
> I think you mean brackets, not braces '{}'.
> 
> >  Right ?
> 
> Definitely not.
> 
> I added this function to the above:
> 
> 	unsigned long alt(void)
> 	{
> 		unsigned long max_threads;
> 		max_threads = mempages * (PAGE_SIZE / (8 * THREAD_SIZE));
> 		return max_threads;
> 	}
> 
> and ran it through "gcc -S -O2" for x86_64:
> 
> 	jump:
> 		movq    mempages(%rip), %rax
> 		salq    $12, %rax
> 		shrq    $16, %rax
> 		ret
> 	alt:
> 		xorl    %eax, %eax
> 		ret
> 
> Note the difference?  In jump(), x86_64 first multiplies mempages by 4096, and
> _then_ divides by 8*8192.
> 
> In alt(), it just returns 0 because the compiler realised that you're
> multiplying by 0.

The case were the multiplier is 0 (actually smaller than 1, but not integer)
is handled by

	#if (8 * THREAD_SIZE) > PAGE_SIZE
	      max_threads = mempages / (8 * THREAD_SIZE / PAGE_SIZE);
	#else
	     ...

> If you're going to bracket the expression, it must be:
> 
> 		max_threads = (mempages * PAGE_SIZE) / (8 * THREAD_SIZE);
> 
> which should be superfluous.

No, `mempages * PAGE_SIZE' may overflow.

With kind regards,

Geert Uytterhoeven
Software Architect

Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

Phone:    +32 (0)2 700 8453
Fax:      +32 (0)2 700 8622
E-mail:   Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/

A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010

Re[4]: [PATCH] fork_init: fix division by zero

[Yuri Tikhonov]

=0D=0A Hello David,

On Wednesday, December 10, 2008 you wrote:

> Yuri Tikhonov <yur@emcraft.com> wrote:

>>  Here we believe in preprocessor: since all PAGE_SIZE, 8, and=20
>> THREAD_SIZE are the constants we expect it will calculate this.

> The preprocessor shouldn't be calculating this.  I believe it will _only_
> calculate expressions for #if.  In the situation you're referring to, it
> should perform a substitution and nothing more.  The preprocessor doesn't
> necessarily know how to handle the types involved.

> In any case, there's an easy way to find out: you can ask the compiler to=
 give
> you the result of running the source through the preprocessor only. For
> instance, if you run this:

>         #define PAGE_SIZE 4096
>         #define THREAD_SIZE 8192
>         unsigned long mempages;
>         unsigned long jump(void)
>         {
>                 unsigned long max_threads;
>                 max_threads =3D mempages * PAGE_SIZE / (8 * THREAD_SIZE);
>                 return max_threads;
>         }

> through "gcc -E", you get:

>         # 1 "calc.c"
>         # 1 "<built-in>"
>         # 1 "<command line>"
>         # 1 "calc.c"
>         unsigned long mempages;
>         unsigned long jump(void)
>         {
>          unsigned long max_threads;
>          max_threads =3D mempages * 4096 / (8 * 8192);
>          return max_threads;
>         }


>>  In any case, adding braces as follows probably would be better:
>>=20
>> +     max_threads =3D mempages * (PAGE_SIZE / (8 * THREAD_SIZE));

> I think you mean brackets, not braces '{}'.

 Yes, it was a typo.


>>  Right ?

> Definitely not.

> I added this function to the above:

>         unsigned long alt(void)
>         {
>                 unsigned long max_threads;
>                 max_threads =3D mempages * (PAGE_SIZE / (8 * THREAD_SIZE)=
);
>                 return max_threads;
>         }

> and ran it through "gcc -S -O2" for x86_64:

>         jump:
>                 movq    mempages(%rip), %rax
>                 salq    $12, %rax
>                 shrq    $16, %rax
>                 ret
>         alt:
>                 xorl    %eax, %eax
>                 ret

> Note the difference?  In jump(), x86_64 first multiplies mempages by 4096=
, and
> _then_ divides by 8*8192.

> In alt(), it just returns 0 because the compiler realised that you're
> multiplying by 0.

 I think Geert has already commented this: you've compiled your alt()=20
functions having 4K PAGE_SIZE and 8K THREAD_SIZE - this case is=20
handled by the old code in fork_init.

> If you're going to bracket the expression, it must be:

>                 max_threads =3D (mempages * PAGE_SIZE) / (8 * THREAD_SIZE=
);

> which should be superfluous.

>>  E.g. here is the result from this line as produced by cross-gcc=20
>> 4.2.2:
>>=20
>>         lis     r9,0
>>         rlwinm  r29,r29,2,16,29
>>         stw     r29,0(r9)
>>=20
>>  As you see - only rotate-left, i.e. multiplication to the constant.

> Ummm...  On powerpc, I believe rotate-left would be a division as it does=
 the
> bit-numbering and the bit direction the opposite way to more familiar CPUs
> such as x86.

 On powerpc shifting left is multiplication by 2, as this has the most=20
significant bit first.

 Regards, Yuri

 --
 Yuri Tikhonov, Senior Software Engineer
 Emcraft Systems, www.emcraft.com

Re: Re[2]: [PATCH] fork_init: fix division by zero

[Paul Mackerras]

David Howells writes:

> Ummm...  On powerpc, I believe rotate-left would be a division as it does the
> bit-numbering and the bit direction the opposite way to more familiar CPUs
> such as x86.

No.  :)

"Left" and "right" are relative to the way those of us humans in the
Western European cultural tradition write numbers, which is
big-endian.  So rotate-left always moves bits towards the more
significant end of the word.

Paul.

Re: Re[2]: [PATCH] fork_init: fix division by zero

[David Howells]

David Howells <dhowells@redhat.com> wrote:

> Ummm...  On powerpc, I believe rotate-left would be a division as it does the
> bit-numbering and the bit direction the opposite way to more familiar CPUs
> such as x86.

Actually, I'm not sure that's true.  Sometimes powerpc makes my head hurt:-)

David