Tcl Source Code

View Ticket
Login
Ticket UUID: c9663296fd31fbb2fa1ff1cf019b59f432983516
Title: GrowStringBuffer and GrowUnicodeBuffer do not check for overflows
Type: Bug Created on: 2023-04-23 02:49:00
Submitter: apnadkarni Assigned to: apnadkarni
Subsystem: 41. Memory Allocation Severity: Severe
Priority: 5 Medium Last modified: 2023-05-20 16:41:52
Status: Closed Closed by: apnadkarni
Resolution: Fixed Closed on: 2023-05-20 16:41:52
Version:
Description:

On reallocations, GrowStringBuffer doubles the requested size without checking for integer overflow. This applies to 8.7 and 9.0 (may be even earlier).

On the second attempt, it limits the size to INT_MAX which is no longer the limit in 64-bit 9.0 (should be TCL_SIZE_MAX).

Just noting for now for future correction. The doubling every time also has to be reconsidered as it wastes a lot of memory once sizes get large (bigdata tests) causing memory exhaustion panics when there should not be.

Same is true of GrowUnicodeBuffer

User Comments:
apnadkarni added on 2023-05-05 06:57:10:

Broadening the scope of this ticket:

As Tcl 9 deals with larger sized data, the aggressive overallocation of memory results in memory allocation panics when in reality there is enough memory to satisfy the actual request sizes. To keep amortized cost of allocation at O(1), it is not actually necessary to double requested size on overflow. Any factor > 1 suffices. Many implementations have changed to 1.5. This change is implemented in branch bug-c9663296fd.

The branch also makes one other change - when the overallocation fails, it falls back to a "binary" scheme of reducing overallocation instead of allocating the exact or a small fixed overallocation.

The results of these changes are shown in the table below. Since the change has the potential to impact performance both memory commit and time/op is shown.

Operation Trunk bug-c9663296f
timerate {lappend l x} 20000 0.147346 µs/# 0.146707 µs/#
1.58GB 1.07GB
time {lappend l x} 1000000000 0.229233 us/# 0.219229 us/#
12.61GB 8.07GB
time {append s x} 1000000000 0.153472 us/# 0.155471 us/#
1.58GB 1.17GB

As seen above, there is very significant savings in memory without sacrificing performance.


apnadkarni added on 2023-05-05 07:00:42:
Python and Go use slightly more sophisticated growth algorithms. These as well as other expansion factors can be experimented with later by modifying the TclUpsize* functions.

apnadkarni added on 2023-05-05 13:06:07:
As a further data point that performance wise reducing growth factor does not make a difference, listPerf shows almost identical run time.

22138.03560|1.04  |22356.05310|1.03  |Total run time

chrstphrchvz added on 2023-05-05 13:07:04:

The changes discussed here can probably be used to address [69b4f7eb37], at least in newer Tcl. I had similar ideas there about adjusting the memory allocation growth algorithm. Other ideas (which I am not knowledgeable enough to know if they are good ones) might be to have some TCL_MAX_GROWTH amount, or to keep track of large buffers so Tcl can go back and free unused memory before trying malloc again (or possibly in response to a memory pressure notification from the OS). And while I am aware Tcl was mostly written when computers had far less RAM, many of its memory allocation panics do not seem strictly necessary, but were likely easier to implement than returning errors, or out of the assumption that the stability of the entire system is compromised once malloc() fails.


chrstphrchvz added on 2023-05-05 13:33:10:

After looking again, any effort for [69b4f7eb37] will probably be separate, since it is growing the string of a Tcl_Obj rather than directly growing a buffer, but maybe it is still of interest.


anonymous added on 2023-05-05 19:41:57:

Hi Ashok,

Around 2012/2013, I did some larger tests and changes for Tcl 8.5.13 experiencing with different mallocs and Tcl-internal malloc-growing strategies (also trying the python growth scheme). I think, we are still using this changes in our (highly busy) live-system (ported to 8.6). With smaller growth factors, one is trading memory waste vs. realloc frequencies, which are more problematic on multi-threaded applications.

My experience was that doubling is quite good up to a certain size, but then, the policy should be altered (if one adds 1 byte to a 1GB string, 2GBs are most likely an overkill). By looking at the malloc implementations, it made also sense to over-alloc in multiple of units, which are used by the malloc implementations anyhow (e.g. page sizes). I also added some monitoring code (via compile-time switches) to monitor large reallocs. I also remember, that there were several places to touch (such as DStrings, Tcl_Objs, Lists, ...)

I have just a write-up of the malloc implementation tested [1]. We are also using since a few years a system-malloc patch, which makes it easier to use different malloc implementations as replacement for Tcl's threaded malloc. We still use Google's tclmalloc, although, since a few years, the standard Linux malloc became quite good.

Let me know if you are interested in that code. -gustaf

[1] https://next-scripting.org/2.4.0/doc/misc/thread-mallocs/index1


apnadkarni added on 2023-05-06 02:23:06:
Christopher, with respect to [69b4f7eb37], yes that is a little different because it expects to read a certain number and sets the Tcl_Obj buffer to that length.

However, one of the comments in that ticket talks about the fallback to actual requested size (TCL_MIN_GROWTH etc.). This patch addresses that to some extent as well. If the initial overallocation fails, the fallback now uses a "binary search" kind of mechanism to over allocate. There is of course a trade off there as multiple attempts will be made instead of a single additional attempt.

/Ashok

apnadkarni added on 2023-05-06 02:36:37:
Gustaf,

I think certainly it would very much be of interest at some point, though probably not right away (question of priorities). There are a variety of expansion proposals in the literature as well as actual implementations and choosing one needs some amount of analysis and actual measurement which is time consuming.

With respect to reducing the factor as allocations grow, the amortization analysis I've seen that prove O(1) complexity depend on a constant growth factor (> 1). I am not good enough in complexity analysis to know if that still holds good if that factor is not constant but dependent on allocation size.

However, the resizing / expansion algorithm is now in just one place for strings and lists (TclUpsize* functions in tclInt.h) so experimenting is a little easier as code does not have to change in multiple places.

I had missed the expansions in DString so thanks. That needs to be updated.

I had also not realized the implications about thread contention.

/Ashok

apnadkarni added on 2023-05-20 16:41:52:
Fixed in [18d4bd49a6]