| Ticket UUID: | 69b4f7eb379e7b806c0c144a36059ca55f569634 | ||
| Title: | FilterInputBytes(): signed integer overflow, poor worst-case performance lengthening objPtr | ||
| Type: | Bug | Created on: | 2022-03-06 20:28:47 |
| Submitter: | chrstphrchvz | Assigned to: | nobody |
| Subsystem: | 24. Channel Commands | Severity: | Minor |
| Priority: | 5 Medium | Last modified: | 2026-10-18 16:44:59 |
| Status: | Open | Closed by: | nobody |
| Resolution: | None | Closed on: | |
| Version: | 8.6.18, 9.1.0 | ||
| Description: | ||||
|
Running this example leads to signed integer overflow in FilterInputBytes() (as reported by UBSan -fsanitize=signed-integer-overflow):
$ dd bs=4096 count=250000 if=/dev/zero | tclsh8.6
tcl/generic/tclIO.c:5330:22: runtime error: signed integer overflow: 1912594432 + 1912594432 cannot be represented in type 'int'
But something else I notice is that once FilterInputBytes() stops growing objPtr exponentially, it falls back to growing linearly by a very small amount (58 bytes in this example), with each growth requiring realloc()—which even if made much faster by using Linux’s mremap() will still cause throughput to drop dramatically. While the overflow can be avoiding by capping length to INT_MAX, low-memory systems—or systems with plenty of memory if FilterInputBytes() is rewritten to use size_t for Tcl 9—still have the slow linear growth performance issue, so it may still be desirable to improve the objPtr growth algorithm to minimize the number of realloc() calls. One approach I think of is something that approximates logistic growth: if length = offset + offset fails, try again with length = offset + (offset >> 1); otherwise try length = offset + (offset >> 2); and so on until whatever reasonable minimum. | ||||
| User Comments: | ||||
chrstphrchvz added on 2022-04-13 18:34:58:
Apparently there are other places in Tcl where objects are first grown exponentially, and then linearly once doubling is not possible. I would think those are affected by performance issues similar to the one seen in FilterInputBytes(), but maybe that is avoided by their use of TCL_MIN_GROWTH. Without a more rigorous analysis, the alternative growth algorithm I suggest (i.e. to approximate logistic growth) may increase the likelihood that a program terminates (due to wasted memory starving other needed allocations) rather than eventually finishes. serhiy.storchaka added on 2026-10-18 16:44:59:
Still present in 9.1 (9.0 has the same code): Tcl_GetsObj(), TclGetsObjBinary() and FilterInputBytes() keep offsets and counts in int, so [gets] of a line over 2 GB panics in Tcl_SetObjLength ("length requested is negative"), returns a negative length with -translation binary, or crashes when a \r ends a buffer. Proposed fix in branch gets-long-lines: Tcl_Size there, and the doubling of the buffer no longer overflows. Tests gets-bigdata-1 to 3 (constraint bigdata, about 6 GB of memory). The growth strategy when doubling fails is unchanged. | ||||
