[Tcl-bugs] [ tcl-Bugs-2017946 ] Mem leak in NRE/lack of trampoline

[SourceForge.net <no...@so...>]

Bugs item #2017946, was opened at 2008-07-14 13:53
Message generated for change (Comment added) made by tallniel
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=110894&aid=2017946&group_id=10894

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: 45. Parsing and Eval
Group: current: 8.6a1
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Neil Madden (tallniel)
Assigned to: miguel sofer (msofer)
Summary: Mem leak in NRE/lack of trampoline

Initial Comment:
A simple tail-recursive factorial function using NRE bombs out at around N=10,000 due to out of memory panic in Tcl bignum code. Equivalent iterative version completes fine on same input. It seems like the C stack is growing despite NRE, and locals aren't being reclaimed? Is this [if] causing the tailcall to not work? Test proc:

proc fac-tr {n {k 1}} {
    if {$n <= 1} {
        return $k
    } else {
        tailcall fac-tr [- $n 1] [* $n $k]
    }
}
fac-tr 10000

(abort reproducible on Windows XP, with 4GB RAM). Stack dump at abort:

 	tclsh86sg.exe!_chkstk()  Line 91	Asm
 	tclsh86sg.exe!_NMSG_WRITE(int rterrnum=10)  Line 194 + 0x18	C
 	tclsh86sg.exe!abort()  Line 44 + 0x7	C
 	tclsh86sg.exe!Tcl_PanicVA(const char * format=0x005603e8, char * argList=0x00033538)  Line 104	C
 	tclsh86sg.exe!Tcl_Panic(const char * format=0x005603e8, ...)  Line 131 + 0xd	C
 	tclsh86sg.exe!Tcl_Realloc(char * ptr=0x148e7fe8, unsigned int size=12944)  Line 1108 + 0xe	C
 	tclsh86sg.exe!TclBN_mp_grow(mp_int * a=0x000340b4, int size=3236)  Line 35 + 0x13	C
 	tclsh86sg.exe!TclBN_mp_copy(mp_int * a=0x00033584, mp_int * b=0x000340b4)  Line 31 + 0xf	C
 	tclsh86sg.exe!TclBN_mp_init_copy(mp_int * a=0x000340b4, mp_int * b=0x00033584)  Line 26 + 0xd	C
 	tclsh86sg.exe!GetBignumFromObj(Tcl_Interp * interp=0x00000000, Tcl_Obj * objPtr=0x14f92310, int copy=0, mp_int * bignumValue=0x000340b4)  Line 2797 + 0xd	C
 	tclsh86sg.exe!Tcl_TakeBignumFromObj(Tcl_Interp * interp=0x00000000, Tcl_Obj * objPtr=0x14f92310, mp_int * bignumValue=0x000340b4)  Line 2902 + 0x13	C
 	tclsh86sg.exe!TclExecuteByteCode(Tcl_Interp * interp=0x00afa8a8, ByteCode * codePtr=0x00bb7fb8)  Line 6428 + 0x15	C
 	tclsh86sg.exe!Tcl_EvalObjv(Tcl_Interp * interp=0x00afa8a8, int objc=3, Tcl_Obj * const * objv=0x14cb1fe0, int flags=524288)  Line 4116 + 0x10	C
 	tclsh86sg.exe!TailcallFromTebc(void * * data=0x14f922cc, Tcl_Interp * interp=0x00afa8a8, int result=0)  Line 7838 + 0x16	C
>	tclsh86sg.exe!TclEvalObjv_NR2(Tcl_Interp * interp=0x00afa8a8, int result=0, TEOV_record * rootPtr=0x06a2ea10)  Line 4238 + 0x16	C
 	tclsh86sg.exe!Tcl_EvalObjv(Tcl_Interp * interp=0x00afa8a8, int objc=3, Tcl_Obj * const * objv=0x14cb1f98, int flags=524288)  Line 4207 + 0x11	C
 	tclsh86sg.exe!TailcallFromTebc(void * * data=0x14f92344, Tcl_Interp * interp=0x00afa8a8, int result=0)  Line 7838 + 0x16	C
 	tclsh86sg.exe!TclEvalObjv_NR2(Tcl_Interp * interp=0x00afa8a8, int result=0, TEOV_record * rootPtr=0x06a2ea10)  Line 4238 + 0x16	C
 	tclsh86sg.exe!Tcl_EvalObjv(Tcl_Interp * interp=0x00afa8a8, int objc=3, Tcl_Obj * const * objv=0x14cb1f50, int flags=524288)  Line 4207 + 0x11	C
 	tclsh86sg.exe!TailcallFromTebc(void * * data=0x14f923bc, Tcl_Interp * interp=0x00afa8a8, int result=0)  Line 7838 + 0x16	C
... stack then has several hundred repeats of these TailcallFromTebc/Tcl_EvalObjv combinations....

I thought this might be the [if] preventing the tailcall reclaiming the stack, but I get the same abort with the simpler:

 proc fac-tr {n {k 1}} {
     if {$n <= 1} { return $k }
     tailcall fac-tr [- $n 1] [* $n $k]
 }



----------------------------------------------------------------------

>Comment By: Neil Madden (tallniel)
Date: 2008-07-14 15:40

Message:
Logged In: YES 
user_id=102050
Originator: YES

The bug seems to disappear when fac-tr is itself called from a
byte-compiled
context (e.g. a proc or loop body), e.g.:

 proc foo {} { fac-tr 10000 }
 # or
 foreach _ _ { fac-tr 10000 }

This completes fine, apparently consuming constant stack. It is only when
fac-tr is called from a non-byte-compiled context that [tailcall] seems
to
not work as expected (C stack grows as pre-NRE).

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=110894&aid=2017946&group_id=10894