View Ticket
Not logged in
2021-12-16
08:37 Closed ticket [31e302fcf7]: signed integer overflow in generic/tclHash.c plus 7 other changes artifact: 70e0018f09 user: jan.nijtmans
08:35
Fix [31e302fcf7]: signed integer overflow in generic/tclHash.c check-in: 96d30a7f6b user: jan.nijtmans tags: core-8-6-branch
00:45 New ticket [31e302fcf7] signed integer overflow in generic/tclHash.c. artifact: eedfdc67cb user: chrstphrchvz

Ticket UUID: 31e302fcf74ff38e31a1ddb5b0a0e2c1506766b3
Title: signed integer overflow in generic/tclHash.c
Type: Patch Version: 8.6.12
Submitter: chrstphrchvz Created on: 2021-12-16 00:45:59
Subsystem: 69. Other Assigned To: jan.nijtmans
Priority: 5 Medium Severity: Minor
Status: Closed Last Modified: 2021-12-16 08:37:48
Resolution: Fixed Closed By: jan.nijtmans
    Closed on: 2021-12-16 08:37:48
Description:

(Not sure which category to pick for hash tables.)

The RANDOM_INDEX() macro in generic/tclHash.c multiplies an input, which is not necessarily unsigned, by 1103515245L. On platforms where sizeof(long) == 4, this often leads to signed integer overflow for signed inputs. UBSan (-fsanitize=signed-integer-overflow) complains on tclsh startup (somewhere during TclOO initialization):

tcl/generic/tclHash.c:442:10: runtime error: signed integer overflow: -1322139600 * 1103515245 cannot be represented in type 'long int'
tcl/generic/tclHash.c:1075:11: runtime error: signed integer overflow: -1341125938 * 1103515245 cannot be represented in type 'long int'
%

For systems with sizeof(long) == 8 but sizeof(int) == 4, a similar error can be reproduced by changing 1103515245L to 1103515245:

tcl/generic/tclHash.c:442:10: runtime error: signed integer overflow: 113680 * 1103515245 cannot be represented in type 'int'
tcl/generic/tclHash.c:1075:11: runtime error: signed integer overflow: 14286 * 1103515245 cannot be represented in type 'int'
%

Signed integer overflow can be avoided by instead using 1103515245UL (causing signed inputs to be sign-extended and then cast to unsigned long):

diff --git generic/tclHash.c generic/tclHash.c
index bcf6eee00..5de816829 100644
--- generic/tclHash.c
+++ generic/tclHash.c
@@ -35,7 +35,7 @@
  */
 
#define RANDOM_INDEX(tablePtr, i) \
-    ((((i)*1103515245L) >> (tablePtr)->downShift) & (tablePtr)->mask)
+    ((((i)*1103515245UL) >> (tablePtr)->downShift) & (tablePtr)->mask)
 
 /*
  * Prototypes for the array hash key methods.

User Comments: jan.nijtmans added on 2021-12-16 08:37:48:

Fixed [96d30a7f6b67115d|here]. Thanks for the report and patch!