[PATCH] kallsyms: fix potential overflow in binary search

[PATCH] kallsyms: fix potential overflow in binary search

[Vegard Nossum]

>From 61b840f071e496f632fcc293f5435428cfc98844 Mon Sep 17 00:00:00 2001
From: Vegard Nossum <vegard.nossum@gmail.com>
Date: Tue, 13 May 2008 10:20:27 +0200
Subject: [PATCH] kallsyms: fix potential overflow in binary search

This will probably never trigger... but it won't hurt to be careful.

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Signed-off-by: Vegard Nossum <vegard.nossum@gmail.com>
---
 kernel/kallsyms.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 6fc0040..38fc10a 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -176,7 +176,7 @@ static unsigned long get_symbol_pos(unsigned long addr,
 	high = kallsyms_num_syms;
 
 	while (high - low > 1) {
-		mid = (low + high) / 2;
+		mid = low + (high - low) / 2;
 		if (kallsyms_addresses[mid] <= addr)
 			low = mid;
 		else
-- 
1.5.4.1

Re: [PATCH] kallsyms: fix potential overflow in binary search

[Paulo Marques]

Vegard Nossum wrote:
>>From 61b840f071e496f632fcc293f5435428cfc98844 Mon Sep 17 00:00:00 2001
> From: Vegard Nossum <vegard.nossum@gmail.com>
> Date: Tue, 13 May 2008 10:20:27 +0200
> Subject: [PATCH] kallsyms: fix potential overflow in binary search
> 
> This will probably never trigger... but it won't hurt to be careful.

Not "probably", this will never trigger _period_. If you ever have more 
than 2^31 symbols in the kernel's kallsyms table you'll have worse 
problems to worry about than the binary search overflowing.

So, I don't think it is worth this des-optimization at all...

> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
> 
> Signed-off-by: Vegard Nossum <vegard.nossum@gmail.com>
> ---
>  kernel/kallsyms.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
> index 6fc0040..38fc10a 100644
> --- a/kernel/kallsyms.c
> +++ b/kernel/kallsyms.c
> @@ -176,7 +176,7 @@ static unsigned long get_symbol_pos(unsigned long addr,
>  	high = kallsyms_num_syms;
>  
>  	while (high - low > 1) {
> -		mid = (low + high) / 2;
> +		mid = low + (high - low) / 2;
>  		if (kallsyms_addresses[mid] <= addr)
>  			low = mid;
>  		else


-- 
Paulo Marques - www.grupopie.com

Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration

Re: [PATCH] kallsyms: fix potential overflow in binary search

[Pekka Enberg]

On Wed, May 14, 2008 at 2:44 PM, Paulo Marques <pmarques@grupopie.com> wrote:
> > This will probably never trigger... but it won't hurt to be careful.
>
>  Not "probably", this will never trigger _period_. If you ever have more
> than 2^31 symbols in the kernel's kallsyms table you'll have worse problems
> to worry about than the binary search overflowing.
>
>  So, I don't think it is worth this des-optimization at all...

Yes it is. It serves as correct reference code and the
"deoptimization" is not measurable.

Re: [PATCH] kallsyms: fix potential overflow in binary search

[Paulo Marques]

Pekka Enberg wrote:
> On Wed, May 14, 2008 at 2:44 PM, Paulo Marques <pmarques@grupopie.com> wrote:
>>> This will probably never trigger... but it won't hurt to be careful.
>>  Not "probably", this will never trigger _period_. If you ever have more
>> than 2^31 symbols in the kernel's kallsyms table you'll have worse problems
>> to worry about than the binary search overflowing.
>>
>>  So, I don't think it is worth this des-optimization at all...
> 
> Yes it is. It serves as correct reference code and the
> "deoptimization" is not measurable.

Hum? "reference code"? in the middle of a kallsyms function?

And are you really worried about contiguous arrays that are bigger than 
2^31 elements? What kind of kernel structure would that be?

The fact that the "deoptimization" isn't measurable isn't an excuse for 
unnecessary bloat.

This all seems like a wild goose chase to me...

-- 
Paulo Marques - www.grupopie.com

"To be, or not to be? That is ..... liable to be removed at -O2 and above."

Re: [PATCH] kallsyms: fix potential overflow in binary search

[Vegard Nossum]

Hi,

On Wed, May 14, 2008 at 1:44 PM, Paulo Marques <pmarques@grupopie.com> wrote:
> Vegard Nossum wrote:
>>>
>>> From 61b840f071e496f632fcc293f5435428cfc98844 Mon Sep 17 00:00:00 2001
>>
>> From: Vegard Nossum <vegard.nossum@gmail.com>
>> Date: Tue, 13 May 2008 10:20:27 +0200
>> Subject: [PATCH] kallsyms: fix potential overflow in binary search
>>
>> This will probably never trigger... but it won't hurt to be careful.
>
> Not "probably", this will never trigger _period_. If you ever have more than
> 2^31 symbols in the kernel's kallsyms table you'll have worse problems to
> worry about than the binary search overflowing.
>
> So, I don't think it is worth this des-optimization at all...

You are right, and I will not push this patch through if you think it's stupid.

The change is only a matter of principle; at the very least, document
your assumptions! So my patch changed something that was not obviously
right to something that is explicitly right. Is it even remotely
possible that somebody could notice that we never have 2^32 kallsym
entries and change these array indices to a smaller type, without
taking the possibility of overflow into account? It sounds unlikely, I
agree; on the other hand, what makes this different from all the
_other_ times you thought something was impossible and it wasn't?
(Surely you've had those experiences too?)

My mentality is to make things work under as many circumstances as
possible, provided the effort is worth it, so that I won't be
surprised in the future. Documentation is another way to do that.
Would you rather see a patch that introduces a comment which explains
why the overflow isn't possible (in the current situation)?

If you still believe this is wrong, then I will ask Andrew to withdraw
the patch. Thank you for your comments.


Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036