Tcl Source Code

In GrowEvaluationStack(ExecEnv *eePtr, int growth,int move), the "growth" argument is of the signed int type which means that this API cannot be used to allocate more than 2GB of memory. There is no range check either, so if a Tcl command tries to allocate more than 2GB, the API just silently corrupts memory.

Specifically, the bug was found by trying to do lsort on a very large list.

a) create a very large list (e.g. 108707840 entries) of string, called, for example, $names.

b) sort and uniquify the list:
set sorted_unique_names [lsort -unique $names] # This will cause a memory error

The top of the stacktrace is:
#0  0x0000000014700aa1 in GrowEvaluationStack (eePtr=0x1e2c9a80, 
    growth=-210747392, move=0)
    at /global/sde_apps/tcl/m/prod/tcl/tcl8.6/generic/tclExecute.c:1124
#1  0x000000001470172f in StackAllocWords ()
    at /global/sde_apps/tcl/m/prod/tcl/tcl8.6/generic/tclExecute.c:1252
#2  0x0000000014702302 in TclStackAlloc (interp=0x1e2c6c00, 
    numBytes=-1685979136)
    at /global/sde_apps/tcl/m/prod/tcl/tcl8.6/generic/tclExecute.c:1349
#3  Tcl_LsortObjCmd (clientData=0x0, interp=0x1e2c6c00, objc=3, 
    objv=0x1e2d4e70)
    at /global/sde_apps/tcl/m/prod/tcl/tcl8.6/generic/tclCmdIL.c:3960

fixed now in 8.6 and trunk.

Just as small test-case to reproduce:

% set l {1}; time {lappend l {*}$l} 27; puts "[llength $l] elements"
134217728 elements
% lsort -unique $l; # should return "1"
Segmentation fault (core dumped)

This going to the array of indices that will be used for sorting, allocated via "TclStackAlloc(interp, sizeof(int) * sortInfo.indexc)" which indeed very doubtful by lsort, that can sort really large lists.

Instead of the rewriting of GrowEvaluationStack/TclStackAlloc rather the ckalloc should be used here instead (at least by large size of the sorting list).

I want fix it right away...

BTW If someone nevertheless want to rewrite "int" as "ptrdiff_t", then the "int numBytes" for pair TclStackAlloc/TclStackRealloc should be then also rewritten as "size_t numBytes".

Thx for reporting!

It should be indeed rewritten using ptrdiff_t resp. offset_t (no idea which of both will be supported by all platforms/compilers). size_t would be also a variant if "growth" used only to enlarge the stack (to be verified).

But I did not yet understand what some large list has concertedly with the evaluation stack... Should the "names" be just not a variable name in such case? According to:

% tcl::unsupported::disassemble script {lsort -unique $names}
ByteCode 0x004E7F90, refCt 1, epoch 16, interp 0x004CAF58 (epoch 16)
  Source "lsort -unique $names"
  Cmds 1, src 20, inst 10, litObjs 3, aux 0, stkDepth 3, code/src 0.00
  Commands 1:
      1: pc 0-8, src 0-19
  Command 1: "lsort -unique $names"
    (0) push1 0         # "lsort"
    (2) push1 1         # "-unique"
    (4) push1 2         # "names"
    (6) loadStk
    (7) invokeStk1 3
    (9) done