kallsyms: fix potential overflow in binary search
PATCH 1/1 kallsyms: fix potential overflow in binary search
Quoted 1 line
From
61b840f071e496f632fcc293f5435428cfc98844Mon Sep 17 00:00:00 2001
From: Vegard Nossum <[email protected]>
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
--- kernel/kallsyms.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/kallsyms.c +1 -1
@@ -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
Signature · 1 line
1.5.4.1
Quoted 6 lines · Vegard Nossum
Quoted 1 line
From
61b840f071e496f632fcc293f5435428cfc98844Mon Sep 17 00:00:00 2001From: Vegard Nossum <[email protected]>
Date: Tue, 13 May 2008 10:20:27 +0200
Subject: [PATCH] kallsyms: fix potential overflow in binary searchThis 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...
Quoted 20 lines
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Signed-off-by Vegard Nossum <[email protected]>--- kernel/kallsyms.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)kernel/kallsyms.c +1
-1@@ -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
Signature · 4 lines
Paulo Marques - www.grupopie.com Dear aunt, let's set so double the killer delete select all. -- Microsoft voice recognition live demonstration
Quoted 7 lines · Paulo Marques
Quoted 1 line
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.
Quoted 10 lines · Pekka Enberg
Quoted 6 lines · Paulo Marques
Quoted 1 line
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...
Signature · 3 lines
Paulo Marques - www.grupopie.com "To be, or not to be? That is ..... liable to be removed at -O2 and above."
Hi,
Quoted 8 lines · Paulo Marques
Quoted 7 lines · Vegard Nossum
Quoted 2 lines
From
61b840f071e496f632fcc293f5435428cfc98844Mon Sep 17 00:00:00 2001From: Vegard Nossum <[email protected]>
Date: Tue, 13 May 2008 10:20:27 +0200
Subject: [PATCH] kallsyms: fix potential overflow in binary search
Quoted 7 lines
Quoted 1 line
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
Signature · 4 lines
"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