x86/lib: Fix overflow of variable m when val >= 1410065408
Subsystems (2)
PATCH 1/1 x86/lib: Fix overflow of variable m when val >= 1410065408
There is an overflow in variable m in function num_digits when val is >= 1410065408 which leads to the digit calculation loop to iterate more times than required. This results in either more digits being counted or in some cases (for example where val is 1932683193) the value of m eventually overflows to zero and the while loop spins forever).
Currently the function num_digits is currently only being used for small values of val in the SMP boot stage for digit counting on the number of cpus and NUMA nodes, so the overflow is never encounterd. However it is useful to fix the overflow issue in case the function is used for other purposes in the future. (The issue was discovered while investigating the digit counting performance in various kernel helper functions rather than any real-world use-case).
The simplest fix is to make m a long int, the overhead in multiplication speed for a long is very minor for small values of val less than 10000 on modern processors. The alternative fix is to replace the multiplication with a constant division by 10 loop (this compiles down to an multiplication and shift) without needing to make m a long int, but this is slightly slower than the fix in this commit when measured on a range of x86 processors).
--- arch/x86/lib/misc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
arch/x86/lib/misc.c +1 -1
@@ -8,7 +8,7 @@*/ int num_digits (int val) { -int m =10 ; +long m =10 ;int d =1 ;if (val <0 ) {
Signature · 1 line
2.39.2
Quoted 10 lines · Colin Ian King
There is an overflow in variable m in function
num_digitswhen val is >= 1410065408 which leads to the digit calculation loop to iterate more times than required. This results in either more digits being counted or in some cases (for example where val is 1932683193) the value of m eventually overflows to zero and the while loop spins forever).Currently the function
num_digitsis currently only being used for small values of val in the SMP boot stage for digit counting on the number of cpus and NUMA nodes, so the overflow is never encounterd.
encountered.
Quoted 14 lines
However it is useful to fix the overflow issue in case the function is used for other purposes in the future. (The issue was discovered while investigating the digit counting performance in various kernel helper functions rather than any real-world use-case).
The simplest fix is to make m a long int, the overhead in multiplication speed for a long is very minor for small values of val less than 10000 on modern processors. The alternative fix is to replace the multiplication with a constant division by 10 loop (this compiles down to an multiplication and shift) without needing to make m a long int, but this is slightly slower than the fix in this commit when measured on a range of x86 processors).
Quoted 2 lines
Fixes 646e29a1789a ("x86: Improve the printout of the SMP bootup CPU table")Signed-off-by Colin Ian King <[email protected]>
num_digits() now works for all int values.
Thanks.
Quoted 17 lines
--- arch/x86/lib/misc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)arch/x86/lib/misc.c +1
-1@@ -8,7 +8,7 @@*/ int num_digits (int val) { -int m =10 ; +long m =10 ;int d =1 ;if (val <0 ) {
Signature · 1 line
~Randy
On 11/1/23 08:32, Colin Ian King wrote:
...
arch/x86/lib/misc.c line 14
Quoted 7 lines
int
num_digits(int val)
{arch/x86/lib/misc.c +1
-1-int m =10 ; +long m =10 ;int d =1 ;if (val <0 ) {
Isn't this still broken on 32-bit where sizeof(long) == sizeof(int)? Seems like we need 'm' to be able to hold values that are ~10x larger than 'val' if we need this to work for the entire int range.
Also, performance doesn't matter here at *all* with the current use in a couple of printk()'s. Just making 'm' 'long long' or u64 probably be just fine.
Quoted 8 lines · Dave Hansen
On 11/1/23 08:32, Colin Ian King wrote:
...Quoted 6 lines
int num_digits(int val) {arch/x86/lib/misc.c +1
-1-int m =10 ; +long m =10 ;int d =1 ;
Quoted 5 lines
Quoted 1 line
if (val < 0) {Isn't this still broken on 32-bit where sizeof(long) == sizeof(int)? Seems like we need 'm' to be able to hold values that are ~10x larger than 'val' if we need this to work for the entire int range.
Good point, long long is required for 32 bit,
sizes:
arch int long long long i386 4 4 8 x86_64 4 8 8
I'll send a V2.
Quoted 4 lines
Also, performance doesn't matter here at *all* with the current use in a couple of printk()'s. Just making 'm' 'long long' or u64 probably be just fine.