Can anyone explain me what a "stack overflow" error is (at least what it means in Pd) and what I can do about it?! Thank you
D.S
http://www.flickr.com/photos/schafferdavid/ http://audioblog.arteradio.com/David_Schaffer/
Hi David,
Funny, I just posted a good example of stack overflow, the typical counter:
[f]X[+ 1]
where [+ 1] gets sent to the hot rather than the cold inlet of [f].
Because computers are dumb animals, they will try to do exactly what you tell them to without any regards to whether it's sane/possible or not. In this case, the classic stack overflow, you've asked the computer to put itself in an infinite loop ("infinite recursion"), counting and retriggering itself as fast as the CPU will let it do. When PD detects this, it disables that part of the patch and gives a "stack overflow" error.
Sending a "bang" message to the [until] object, created without an argument saying how many times the bang should be done, will give roughly the same effect--effectively you have said to do something forever without limit and with no time constraint (although this particular example does something worse than just throw a "stack overflow" message, it completely freezes PD!).
For a proper explanation, Wikipedia offers the following:
http://en.wikipedia.org/wiki/Stack_overflow
The gist of it is, you have used up all the available memory in the call stack, and the program has no more memory to store variables and do operations.
Avoiding stack overflow is possible by practicing good patching strategies and paying close attention to order of operations. Use [trigger] to properly sequence messages. Don't "fan" patch cables, which can create indeterminate order of operations. Pay attention to "hot" and "cold" inlets, so that a section of the patch can't run away with itself (as in the improper counter example above). Use the "Find last error" command to try to sniff out where the overflow might be happening, then look for fanned cables, wrong connections or other indeterminate/not sane orders of operations there.
Hope that helps, d.
David Schaffer wrote:
Can anyone explain me what a "stack overflow" error is (at least what it means in Pd) and what I can do about it?! Thank you
On Mon, 17 Dec 2007 20:08:20 +0100 Derek Holzer derek@umatic.nl wrote:
Sending a "bang" message to the [until] object, created without an argument saying how many times the bang should be done, will give roughly the same effect--
If only!
Objects that overflow the stack cause an exception, most of which trap nicely and you get a gentle report not to do that again.
Sending an unqualified bang to [until] will have you reaching for power switch because it enters a very tight loop with no exit condition and no hope of even seeing a SIGINT.
I know we like to pretend this is "feature", but isn't it time to treat it as a bug?
On Mon, Dec 17, 2007 at 07:42:44PM +0000, Andy Farnell wrote:
I know we like to pretend this is "feature", but isn't it time to treat it as a bug?
on one hand it is not a bug, as pd is a progarmming languge, like for(;;); is not a bug, it's a feature as well as while(); so ..
but havind a simple C progarmm in for(;;) doesn't cause much trouble, SIGINT usualy kills it .. may be some protection should be considered for [bang(--[until], so it doesn't cause the system such a DoS in this way.. i haven't actually tested this thing yet .. is it really true , or somehow you can kill pd when it get in such a loop ?
ilya .d wrote:
On Mon, Dec 17, 2007 at 07:42:44PM +0000, Andy Farnell wrote:
I know we like to pretend this is "feature", but isn't it time to treat it as a bug?
but havind a simple C progarmm in for(;;) doesn't cause much trouble, SIGINT usualy kills it ..
Pd is _is_ a simple C programm, and [bang(->[until] does something very similar to for(;;);
may be some protection should be considered for [bang(--[until], so it doesn't cause the system such a DoS in this way.. i haven't actually tested this thing yet .. is it really true , or somehow you can kill pd when it get in such a loop ?
that is what i was trying to say (too): it doesn't hang here. it might hang the system, if Pd is running with realtime-priorities. (hey this is what you asked for when turning on rt-priorities)
fgmasdr IOhannes
On Mon, 2007-12-17 at 21:45 +0100, IOhannes m zmoelnig wrote:
ilya .d wrote:
On Mon, Dec 17, 2007 at 07:42:44PM +0000, Andy Farnell wrote:
I know we like to pretend this is "feature", but isn't it time to treat it as a bug?
but havind a simple C progarmm in for(;;) doesn't cause much trouble, SIGINT usualy kills it ..
Pd is _is_ a simple C programm, and [bang(->[until] does something very similar to for(;;);
may be some protection should be considered for [bang(--[until], so it doesn't cause the system such a DoS in this way.. i haven't actually tested this thing yet .. is it really true , or somehow you can kill pd when it get in such a loop ?
that is what i was trying to say (too): it doesn't hang here. it might hang the system, if Pd is running with realtime-priorities. (hey this is what you asked for when turning on rt-priorities)
hm... i still can kill pd, although i am running it with -rt. it just might take me two minutes to kill it. i am not sure, if this actually the main purpose of pd-watchdog, but whenever i see the message 'pd-watchdog: signaling pd', i have a few ms of free cpu time to move the mouse pointer and/or hit some keys. after a few watchdog interrupts i am usuably able to get the xterm, where pd is running in, into focus, so that i can press ctl-c and kill pd.
roman
___________________________________________________________ Der frühe Vogel fängt den Wurm. Hier gelangen Sie zum neuen Yahoo! Mail: http://mail.yahoo.de
Andy Farnell wrote:
On Mon, 17 Dec 2007 20:08:20 +0100 Derek Holzer derek@umatic.nl wrote:
Sending a "bang" message to the [until] object, created without an argument saying how many times the bang should be done, will give roughly the same effect--
If only!
Objects that overflow the stack cause an exception, most of which trap nicely and you get a gentle report not to do that again.
Sending an unqualified bang to [until] will have you reaching for power switch because it enters a very tight loop with no exit condition and no hope of even seeing a SIGINT.
I know we like to pretend this is "feature", but isn't it time to treat it as a bug?
so what is the behaviour you would like to see? only allow fixed sized loops? stop iterating after a maximum 10 bangs? use [del 0] inbetween to make the loop interruptible?
all of the above would break a lot of my patches.
btw, Pd does not freeze for me. while i am typing this email, an infinite [until] is eating most of my CPU power (but not all).
now i did send it a SIGINT and this freed my CPU.
mfa.sdr IOhannes
On Dec 17, 2007 1:42 PM, Andy Farnell padawan12@obiwannabe.co.uk wrote:
I know we like to pretend this is "feature", but isn't it time to treat it as a bug?
It is only a bug if you mispatch things... otherwise, it works...
-- Use the source
PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Usually it means you are recursively calling a function (although not always), and it has pushed so many return addresses on the stack, that the stack buffer overflows. The stack is used by the processor to store addresses when it makes function calls, so that it can mark where to return to when the function call has completed. Can you give an example of the patch that is causing this error?
Mike
On Dec 17, 2007 12:47 PM, David Schaffer schafferdavid@hotmail.com wrote:
Can anyone explain me what a "stack overflow" error is (at least what it means in Pd) and what I can do about it?! Thank you
D.S
http://www.flickr.com/photos/schafferdavid/ http://audioblog.arteradio.com/David_Schaffer/
PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
The stack is a block of memory that is reserved by the cpu for saving the location of the next instruction to execute and register contents before jumping to a subroutine or interrupt handler. It is also used to save the parameters of a function call. When the subroutine is completed the program continues where it left off, by retrieving the most recently added address and register contents from the stack. The cpu signals an overflow whenever the stack space runs out (the program tries to access the stack beyond its boundaries) This usually occurs when the program repeatedly calls the same subroutine from within (recursion) and doesn't return. In pd it usually means you have a loop somewhere, so that the output of an object is feeding its own input: each time a new output is calculated a new input is generated, so the process never ends and eventually the stack overflows.
Martin
David Schaffer wrote:
To: "pd list" pd-list@iem.at Subject: [PD] What exactly is a "stack overflow" ? Date: Mon, 17 Dec 2007 19:47:22 +0100
Can anyone explain me what a "stack overflow" error is (at least what it means in Pd) and what I can do about it?! Thank you
D.S
http://www.flickr.com/photos/schafferdavid/ http://audioblog.arteradio.com/David_Schaffer/
PD-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
On Mon, 2007-12-17 at 19:44 +0000, Martin Peach wrote:
In pd it usually means you have a loop somewhere, so that the output of an object is feeding its own input: each time a new output is calculated a new input is generated, so the process never ends and eventually the stack overflows.
AFAICT in most cases the stack doesn't actually overflow. If the message "stack overflow" gets posted to the Pd console it means that pd has prevented a stack overflow by monitoring the recursion depth, and stopping the message graph at a given outlet.
Jamie
On Mon, 17 Dec 2007, Martin Peach wrote:
The cpu signals an overflow whenever the stack space runs out (the program tries to access the stack beyond its boundaries)
With Pd, this is never what happens on its own. Instead, just before processing each message, a check of the count of nested message processings in made (messages sent that are still being processed, not counting those scheduled by [delay] and stuff).
Win16 would typically have a 512 byte limit for the stack. This is too little for today's needs, but it could be increased up to 64k if you really wanted. In contrast, Linux can typically grow the stack to 512 megs or more, and I don't see why Win32 wouldn't be able to (though I have idea what Win32 does about it -- it probably has a reasonable stack size). 512 megs is too much for the protection that Pd needs.
Older versions of Pd checked stack size instead, but it was a problem with large on-stack allocations. What Linux (or OSX) does when reaching maximum stack size (which you can intentionally lower) is raise a signal, using kill(). It normally doesn't give you any sane way of handling this, so this is why applications that want to stay alive after a so-called stack overflow have to do it themselves and never involve the OS in it.
(If you want to escape an OS-based stack overflow, you can, you need to do things dependent on both which OS and which CPU type, and I wouldn't be surprised if it also depended on which kernel version. I never actually did it, but I'm pretty sure that it's doable, just that it's too scary).
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada
On Dec 17, 2007 11:15 PM, Mathieu Bouchard matju@artengine.ca wrote:
On Mon, 17 Dec 2007, Martin Peach wrote:
The cpu signals an overflow whenever the stack space runs out (the program tries to access the stack beyond its boundaries)
With Pd, this is never what happens on its own. Instead, just before processing each message, a check of the count of nested message processings in made (messages sent that are still being processed, not counting those scheduled by [delay] and stuff).
I have understood the "overflow" part to mean that "stack overflow" refers to a situation where the process of writing info to the stack continues past the memory reserved for the stack, writing to unspecified places in memory; if a safeguard stops it before then, it doesn't really overflow, does it? Seems to me it's an error message about a stack overflow- perfectly appropriate of course- but that it doesn't actually happen.
-Chuckk
Mathieu Bouchard wrote:
On Mon, 17 Dec 2007, Martin Peach wrote:
The cpu signals an overflow whenever the stack space runs out (the program tries to access the stack beyond its boundaries)
With Pd, this is never what happens on its own. Instead, just before processing each message, a check of the count of nested message processings in made (messages sent that are still being processed, not counting those scheduled by [delay] and stuff).
So it's not really a stack overflow, more like a buffer overrun.
Win16 would typically have a 512 byte limit for the stack. This is too little for today's needs, but it could be increased up to 64k if you really wanted. In contrast, Linux can typically grow the stack to 512 megs or more, and I don't see why Win32 wouldn't be able to (though I have idea what Win32 does about it -- it probably has a reasonable stack size). 512 megs is too much for the protection that Pd needs.
But if you don't have 512Meg of RAM then what? The OS must only allocate a
fraction of available memory for stack, preserving enough memory for program
and variables.
The 6502 in the Apple][ had exactly 256 bytes of stack and would just crash
on overflow.
With pentiums and the like the OS has to tell the CPU what the stack limits
are and then the cpu throws an exception if the stack is accessed outside
the limit. That interrupts the OS, which kills the offending process and
prints "stack overflow" or whatever.
Older versions of Pd checked stack size instead, but it was a problem with large on-stack allocations. What Linux (or OSX) does when reaching maximum stack size (which you can intentionally lower) is raise a signal, using kill(). It normally doesn't give you any sane way of handling this, so this is why applications that want to stay alive after a so-called stack overflow have to do it themselves and never involve the OS in it.
(If you want to escape an OS-based stack overflow, you can, you need to do things dependent on both which OS and which CPU type, and I wouldn't be surprised if it also depended on which kernel version. I never actually did it, but I'm pretty sure that it's doable, just that it's too scary).
You would need to modify the processor's interrupt table by replacing the stack overflow exception handler, which is likely to cause trouble elsewhere. The OS wouldn't let you do that anyway, because you'd be accessing memory outside of user space, which triggers another kind of exception, "segmentation fault", the same one triggered by accessing a null pointer.
Martin
On Mon, 17 Dec 2007, Martin Peach wrote:
With Pd, this is never what happens on its own. Instead, just before processing each message, a check of the count of nested message processings in made (messages sent that are still being processed, not counting those scheduled by [delay] and stuff).
So it's not really a stack overflow, more like a buffer overrun.
A stack is a buffer, and an overflow of addresses is an overrun... what are you trying to say?
But if you don't have 512Meg of RAM then what?
Then you have swap, and if you don't have swap, you necessarily get a stack overflow, but it's assumed that if you didn't allocate on the stack, you would allocate the same amount of memory on the heap, so it shouldn't be much different.
The OS must only allocate a fraction of available memory for stack, preserving enough memory for program and variables.
It allocates nothing beforehand, and then at each segmentation fault that occurs at the CPU level, the OS traps a stack-related segmentation fault and adds 4k of RAM to the stack and retries the same code. It's either an auto-expand mmap or the equivalent of it.
The 6502 in the Apple][ had exactly 256 bytes of stack and would just crash on overflow.
I never knew how big the stack was on the CoCo, but given what I know, it must necessarily have been much less than 256 bytes, e.g. 32 or 64 bytes, because BASIC reserved everything after the first 256 bytes, and most of the first 256 bytes were reserved for something else...
With pentiums and the like the OS has to tell the CPU what the stack limits are and then the cpu throws an exception if the stack is accessed outside the limit. That interrupts the OS, which kills the offending process and prints "stack overflow" or whatever.
The OS usually grows the stack. Such a process allows to not have to reserve any memory in advance, so that the stack can be pretty much any size without wasting more than 4k at a time (except that the stack never is ungrown, afaik).
You would need to modify the processor's interrupt table by replacing the stack overflow exception handler, which is likely to cause trouble elsewhere. The OS wouldn't let you do that anyway, because you'd be accessing memory outside of user space, which triggers another kind of exception, "segmentation fault", the same one triggered by accessing a null pointer.
In theory, wouldn't you just register a signal-handler for SIGSTKFLT instead?
But either way (even if the other way was possible), I think that you'd get in trouble because the interrupt/signal-handler would need to push at least 3 words on a stack that is already full.
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada
Mathieu Bouchard wrote:
On Mon, 17 Dec 2007, Martin Peach wrote:
With Pd, this is never what happens on its own. Instead, just before processing each message, a check of the count of nested message processings in made (messages sent that are still being processed, not counting those scheduled by [delay] and stuff).
So it's not really a stack overflow, more like a buffer overrun.
A stack is a buffer, and an overflow of addresses is an overrun... what are you trying to say?
A stack is Last In First Out, like a stack of trays in a cafeteria, and a buffer is First In First Out, like a train in a tunnel. Pd processes messages in the order they are sent, it uses a buffer.
But if you don't have 512Meg of RAM then what?
Then you have swap, and if you don't have swap, you necessarily get a stack overflow, but it's assumed that if you didn't allocate on the stack, you would allocate the same amount of memory on the heap, so it shouldn't be much different.
I think the machine would not be useful with the stack on the hard drive, it would be much too slow.
You would need to modify the processor's interrupt table by replacing the stack overflow exception handler, which is likely to cause trouble elsewhere. The OS wouldn't let you do that anyway, because you'd be accessing memory outside of user space, which triggers another kind of exception, "segmentation fault", the same one triggered by accessing a null pointer.
In theory, wouldn't you just register a signal-handler for SIGSTKFLT instead?
SIGSTKFLT is thrown by the cpu when the stack overflows, and registering a handler amounts to modifying the interrupt table, so its the same thing.
But either way (even if the other way was possible), I think that you'd get in trouble because the interrupt/signal-handler would need to push at least 3 words on a stack that is already full.
Well obviously you're supposed to do it before the stack is too big. If as you say the OS starts out with no stack and waits for trouble, it would have the same problem. I would have thought that a stack overflow requires a restart, unless the exception kicks in before the absolute end of the stack.
Martin
On Thu, 20 Dec 2007, Martin Peach wrote:
a buffer is First In First Out, like a train in a tunnel.
Well, no. Perhaps some uses of the word "buffer" assume that, but most don't. "buffer" is a very vague word. If you want to say FIFO, you just say FIFO or you say queue.
Pd processes messages in the order they are sent, it uses a buffer.
Oh no it doesn't. Pd's immediate message processing is LIFO ("depth first"); Pd's delayed message processing is FIFO ("breadth first"). Look at the execution order for a normal patch, then replace each connection by a delay with a pair of connections. You will observe a change from depth first to breadth first.
I think the machine would not be useful with the stack on the hard drive, it would be much too slow.
So what. It can do it anyway, and if it happens, it won't be any slower than if you had allocated the same arrays in heap instead, as the OS would also have to swap parts of the stack out, to make enough heap fit in.
SIGSTKFLT is thrown by the cpu when the stack overflows, and registering a handler amounts to modifying the interrupt table, so its the same thing.
So why didn't you just talk about SIGSTKFLT instead of going on about how ring 0 can do stuff a user mode process can't?
Well obviously you're supposed to do it before the stack is too big.
If the stack is not too big, then you don't get a STKFLT.
If as you say the OS starts out with no stack and waits for trouble, it would have the same problem. I would have thought that a stack overflow requires a restart, unless the exception kicks in before the absolute end of the stack.
I hope so. If it does, then surely it gives at least a full 4k extra (you can't wait for non-4k boundaries unless you're in very slow debug mode like what valgrind does).
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada
David Schaffer skrev:
Can anyone explain me what a "stack overflow" error is (at least what it means in Pd) and what I can do about it?! Thank you
hi guys
stand still until
attached "until-haiku.pd"
mvh/Stef
#N canvas 675 -4 417 447 10; #X obj 173 177 f; #X obj 202 177 + 1; #X floatatom 242 196 5 0 0 0 - - -; #N canvas 0 0 450 300 (subpatch) 0; #X array vu 64 float 1; #A 0 0.046875 0.03125 0.015625 0 0.984375 0.96875 0.953125 0.9375 0.921875 0.90625 0.890625 0.875 0.859375 0.84375 0.828125 0.8125 0.796875 0.78125 0.765625 0.75 0.734375 0.71875 0.703125 0.6875 0.671875 0.65625 0.640625 0.625 0.609375 0.59375 0.578125 0.5625 0.546875 0.53125 0.515625 0.5 0.484375 0.46875 0.453125 0.4375 0.421875 0.40625 0.390625 0.375 0.359375 0.34375 0.328125 0.3125 0.296875 0.28125 0.265625 0.25 0.234375 0.21875 0.203125 0.1875 0.171875 0.15625 0.140625 0.125 0.109375 0.09375 0.078125 0.0625; #X coords 0 1 63 0 64 64 1; #X restore 50 106 graph; #X obj 173 142 until; #X floatatom 203 114 5 0 0 0 - - -; #X obj 173 116 1; #N canvas 460 279 458 308 scroll 0; #X obj 208 201 list prepend 0; #X obj 208 231 list trim; #X obj 208 108 inlet; #X obj 256 173 list split 64; #X obj 208 260 s vu; #X obj 208 146 list; #X connect 0 0 1 0; #X connect 1 0 4 0; #X connect 2 0 5 0; #X connect 3 0 5 1; #X connect 3 2 5 1; #X connect 5 0 3 0; #X connect 5 0 0 0; #X restore 172 258 pd scroll vu 64; #N canvas 0 0 638 540 frame-count 0; #X obj 266 256 bang~; #X obj 120 73 inlet; #X obj 266 425 outlet; #X obj 266 286 f; #X obj 294 288 + 1; #X obj 120 412 switch~; #X obj 120 253 1; #X obj 266 314 mod; #X obj 266 368 select 0; #X obj 120 128 t b f; #X obj 155 158 select 0; #X obj 155 189 0; #X obj 215 216 1; #X obj 214 189 t b f b; #X obj 265 219 0; #X obj 40 40 loadbang; #X obj 40 40; #X msg 40 62 ; pd dsp 1 ;; #X connect 0 0 3 0; #X connect 1 0 9 0; #X connect 3 0 7 0; #X connect 4 0 3 1; #X connect 6 0 5 0; #X connect 7 0 4 0; #X connect 7 0 8 0; #X connect 8 0 2 0; #X connect 9 0 6 0; #X connect 9 1 10 0; #X connect 10 0 11 0; #X connect 10 1 13 0; #X connect 11 0 6 1; #X connect 12 0 6 1; #X connect 13 0 12 0; #X connect 13 1 7 1; #X connect 13 2 14 0; #X connect 14 0 3 1; #X connect 15 0 17 0; #X restore 173 82 pd frame-count; #X floatatom 173 61 5 0 0 0 - - -; #X obj 173 39 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1 -1; #X obj 172 200 mod 64; #X obj 172 226 / 64; #X obj 200 36 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 0 1; #X connect 0 0 11 0; #X connect 1 0 0 1; #X connect 2 0 11 1; #X connect 2 0 12 1; #X connect 4 0 0 0; #X connect 5 0 6 1; #X connect 6 0 4 0; #X connect 8 0 6 0; #X connect 9 0 8 0; #X connect 10 0 9 0; #X connect 11 0 1 0; #X connect 11 0 12 0; #X connect 12 0 7 0; #X connect 13 0 9 0;