Joel C. Salomon wrote:
> Detecting stack overflow at runtime might also not be trivial.

In a way it is trivial... if you accept a 7% added overhead per function call :o). (The number is what I remember costed Borland Pascal.)

Andrei

Andrei Alexandrescu:
> [Detecting stack overflow at runtime] In a way it is trivial... if you accept a 7% added overhead per function call :o). (The number is what I remember costed Borland Pascal.)<

Now Delphi and FreePascal allow to switch that on and off. From the page: http://www.freepascal.org/docs-html/prog/progsu100.html

1.2.24  $S : Stack checking
The {$S+} directive tells the compiler to generate stack checking code. This generates code to check if a stack overflow occurred, i.e. to see whether the stack has grown beyond its maximally allowed size. If the stack grows beyond the maximum size, then a run-time error is generated, and the program will exit with exit code 202.
Specifying {$S-} will turn generation of stack-checking code off.
The command line compiler switch -Ct has the same effect as the {$S+} directive.
By default, no stack checking is performed.

I have never timed programs to test how much you have to pay if you want stack checking code. The compiler is free, and suitable testing programs can be found in the Shootout site, so if you want you don't need much time to test this.

Bye,
bearophile

bearophile wrote:
> Andrei Alexandrescu:
>> [Detecting stack overflow at runtime] In a way it is trivial... if you accept a 7% added overhead per function call :o). (The number is what I remember costed Borland Pascal.)<
> 
> Now Delphi and FreePascal allow to switch that on and off. From the page: http://www.freepascal.org/docs-html/prog/progsu100.html
> 
> 1.2.24  $S : Stack checking
> The {$S+} directive tells the compiler to generate stack checking code. This generates code to check if a stack overflow occurred, i.e. to see whether the stack has grown beyond its maximally allowed size. If the stack grows beyond the maximum size, then a run-time error is generated, and the program will exit with exit code 202.
> Specifying {$S-} will turn generation of stack-checking code off.
> The command line compiler switch -Ct has the same effect as the {$S+} directive.
> By default, no stack checking is performed.
> 
> I have never timed programs to test how much you have to pay if you want stack checking code. The compiler is free, and suitable testing programs can be found in the Shootout site, so if you want you don't need much time to test this.
> 
> Bye,
> bearophile

Doesn't the OS protect you from stack overflows?

  -- Daniel

Andrei Alexandrescu wrote:
> Georg Wrede wrote:
>> Andrei Alexandrescu wrote:
>>> Computing the stack depth even for non-recursive functions is an interprocedural analysis so it's difficult to do modularly. The stack is also unchecked so going with a "good enough" approximation is bound to be risky.
>>
>> The old size estimation problem. No matter how big you decide on, somewhere is an idiot who will blow that size too.
>>
>>
>> A runtime solution just occurred to me. The newly allocated stack for a thread is zeroed first, right? Well then, just before the thread finishes, one could scan the stack area, and find the first address that contains a non-zero value.
>>
>> This isn't bullet proof in theory, but hey, the aim is to help in /estimating/ the needed stack size.

You could have the GC report stack sizes when it performs a collection.  No guarantee it would be a high-water mark, but it's something.

>> Incidentally, this raises another thought: what if the stack was extendable? Like D arrays? A stack overflow would trigger a relocation of the stack, and then continue. Being able to have hundreds of small stacks would be useful in other things than threads, too.
> 
> That would be great. I don't know whether it can be done.

Windows works this way, and it's possible to do in user code (the Fiber implementation has some of the groundwork for this).  Beyond "usable" stack is a guard page that triggers a stack extension when hit.  But I think if you grow the stack past the guard page without ever touching it you can still blow the stack.

> By the way, I think you're underestimating how much stack the OS gives to the stack. On my system:
> 
> $ grep PTHREAD_STACK /usr/include/**/*.h
> /usr/include/bits/local_lim.h:#define PTHREAD_STACK_MIN 16384
> /usr/include/pthread.h:   minimal size of the block must be PTHREAD_STACK_MIN.*/
> /usr/include/pthread.h:   to be started.  This size must never be less than PTHREAD_STACK_MIN
> $ _
> 
> You can't have a stack smaller than 16KB as far as I understand. I seem to recall the default stack size is much bigger.

On Windows I think the default size is 1MB.

Andrei Alexandrescu wrote:
> Georg Wrede wrote:
>> Andrei Alexandrescu wrote:
>>> Computing the stack depth even for non-recursive functions is an interprocedural analysis so it's difficult to do modularly. The stack is also unchecked so going with a "good enough" approximation is bound to be risky.
>>
>> The old size estimation problem. No matter how big you decide on, somewhere is an idiot who will blow that size too.
>>
>>
>> A runtime solution just occurred to me. The newly allocated stack for a thread is zeroed first, right? Well then, just before the thread finishes, one could scan the stack area, and find the first address that contains a non-zero value.
>>
>> This isn't bullet proof in theory, but hey, the aim is to help in /estimating/ the needed stack size.
> 
> You can't be more serious than Mark Twain when giving advice on the stock market: "Buy some stock. If it goes up, sell it. If it doesn't go up, don't buy it."

I'd be amazed if the stack usage of hello.d varied from run to run.

>> Incidentally, this raises another thought: what if the stack was extendable? Like D arrays? A stack overflow would trigger a relocation of the stack, and then continue. Being able to have hundreds of small stacks would be useful in other things than threads, too.
> 
> That would be great. I don't know whether it can be done.

Two methods come to mind.(1)

> By the way, I think you're underestimating how much stack the OS gives to the stack. On my system:
> 
> $ grep PTHREAD_STACK /usr/include/**/*.h
> /usr/include/bits/local_lim.h:#define PTHREAD_STACK_MIN 16384
> /usr/include/pthread.h:   minimal size of the block must be PTHREAD_STACK_MIN.*/
> /usr/include/pthread.h:   to be started.  This size must never be less than PTHREAD_STACK_MIN

Seems like that minimum means the OS won't start a new thread with less [stack] space left on the computer. Gotta be /some/ value, big enough to be fine with virtually any app.

> You can't have a stack smaller than 16KB as far as I understand. I seem to recall the default stack size is much bigger.

Totally not having researched this... The page http://www.unix.com/high-level-programming/34632-how-find-out-stack-size-occupied-process.html
states that "Most Linux systems have no stack limits set" (didn't have time to find a definitive reference, yet).

Also, PTHREAD_STACK_MIN would be the main process stack size. If we're running co-operative multitasking, or continuations or some such, then the other stacks really can be smaller.

The important thing to know is, does "somebody else" than our program use the current stack? If not, then we're free to allocate "just enough" (in practice much more) to the stacks. IIUC, our stack is only used by our app, its library calls, and the OS API calls.


(1) Using several stacks:

What does one need to use several stacks? Let's assume we have the "regular" stack, and then we temporarily want to use another.

First we allocate space for the new stack. Then we disable interrupts, (we could even save processor state), change the stack pointer to point to the new stack. Enable interrupts, and go on with the program (i.e. call the routine we want to have using the new stack). Once it finishes, disable interrupts, reset the stack pointer, enable interrupts.

Knowing in advance the needed stack space helps here. Especially if instances of the same code are to run with each stack, then all we need is an array of stack spaces. :-)

The other thing: suppose we really don't know the stack usage. Then each routine can use the same stack while it runs, and at task switch we copy the actually used portion of the stack to the heap. Next time we want to run that task, we copy the data back from the heap.

I admit this isn't done in an evening, but it's doable.

Georg Wrede wrote:
> Andrei Alexandrescu wrote:
>> Georg Wrede wrote:
>>> Andrei Alexandrescu wrote:
>>>> Computing the stack depth even for non-recursive functions is an interprocedural analysis so it's difficult to do modularly. The stack is also unchecked so going with a "good enough" approximation is bound to be risky.
>>>
>>> The old size estimation problem. No matter how big you decide on, somewhere is an idiot who will blow that size too.
>>>
>>>
>>> A runtime solution just occurred to me. The newly allocated stack for a thread is zeroed first, right? Well then, just before the thread finishes, one could scan the stack area, and find the first address that contains a non-zero value.
>>>
>>> This isn't bullet proof in theory, but hey, the aim is to help in /estimating/ the needed stack size.
>>
>> You can't be more serious than Mark Twain when giving advice on the stock market: "Buy some stock. If it goes up, sell it. If it doesn't go up, don't buy it."
> 
> I'd be amazed if the stack usage of hello.d varied from run to run.

I'd be amazed if hello.d were your prototype of a useful program :o).

Let's face it. Any program that uses mutual recursion of any kind (even when the user did not set out to use recursion) or that uses alloca (fewer), is bound to have the consumed stack dependent on the input. Even without recursion, various traces of a program depend on a data and have different stack depths. That's why your estimate is utterly useless. I can't believe you brought it up as anything else but jesting (maybe you are and I'm not getting it). I can't even believe I'm replying! :o)


Andrei

Georg Wrede wrote:
> Andrei Alexandrescu wrote:
> 
>> You can't have a stack smaller than 16KB as far as I understand. I seem to recall the default stack size is much bigger.
> 
> Totally not having researched this... The page http://www.unix.com/high-level-programming/34632-how-find-out-stack-size-occupied-process.html 
> 
> states that "Most Linux systems have no stack limits set" (didn't have time to find a definitive reference, yet).

One thing I don't understand is how the OS can manage essentially unbounded stack growth in a multithreaded program with a flat address space.  Is it simply that the physical memory for each stack is mapped into the same virtual address space when a context switch occurs?  And if so, how does this work with multiple cores?  The only alternative I can think of would be to dedicate a virtual address range to each stack, which would set a definite upper bound on the stack size for each thread, and wasted/unused memory between stacks.

Andrei Alexandrescu, el 29 de abril a las 09:58 me escribiste:
> Joel C. Salomon wrote:
> >Detecting stack overflow at runtime might also not be trivial.
> 
> In a way it is trivial... if you accept a 7% added overhead per function call :o). (The number is what I remember costed Borland Pascal.)

Using page protection have no overhead, unless you actually hit a stack overflow.

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------

Sean Kelly wrote:
> Georg Wrede wrote:
>> Andrei Alexandrescu wrote:
>>
>>> You can't have a stack smaller than 16KB as far as I understand. I seem to recall the default stack size is much bigger.
>>
>> Totally not having researched this... The page http://www.unix.com/high-level-programming/34632-how-find-out-stack-size-occupied-process.html 
>>
>> states that "Most Linux systems have no stack limits set" (didn't have time to find a definitive reference, yet).
> 
> One thing I don't understand is how the OS can manage essentially unbounded stack growth in a multithreaded program with a flat address space.  Is it simply that the physical memory for each stack is mapped into the same virtual address space when a context switch occurs?  And if so, how does this work with multiple cores?  The only alternative I can think of would be to dedicate a virtual address range to each stack, which would set a definite upper bound on the stack size for each thread, and wasted/unused memory between stacks.

Well, unbounded and unbounded. It just means there's no set value. The stack can grow as long as there is space. And the virtual address range is more than there's physical memory, so I guess they can say no limit.

Andrei Alexandrescu wrote:
> Georg Wrede wrote:
>> Andrei Alexandrescu wrote:
>>> Georg Wrede wrote:
>>>> Andrei Alexandrescu wrote:
>>>>> Computing the stack depth even for non-recursive functions is an interprocedural analysis so it's difficult to do modularly. The stack is also unchecked so going with a "good enough" approximation is bound to be risky.
>>>>
>>>> The old size estimation problem. No matter how big you decide on, somewhere is an idiot who will blow that size too.
>>>>
>>>>
>>>> A runtime solution just occurred to me. The newly allocated stack for a thread is zeroed first, right? Well then, just before the thread finishes, one could scan the stack area, and find the first address that contains a non-zero value.
>>>>
>>>> This isn't bullet proof in theory, but hey, the aim is to help in /estimating/ the needed stack size.
>>>
>>> You can't be more serious than Mark Twain when giving advice on the stock market: "Buy some stock. If it goes up, sell it. If it doesn't go up, don't buy it."
>>
>> I'd be amazed if the stack usage of hello.d varied from run to run.
> 
> I'd be amazed if hello.d were your prototype of a useful program :o).

Somebody more resourceful than I might /prove/ some maximum for any program that doesn't use recursion (be it implicit or explicit recursion). Hello.d attempted to be an example of such a program.

> Let's face it. Any program that uses mutual recursion of any kind (even when the user did not set out to use recursion) or that uses alloca (fewer), is bound to have the consumed stack dependent on the input. 

Of course. And there's a limit to the stack size, ultimately at the hardware level. For any increase in available stack size, the probability of an out-of-stack exception decreases, never reaching zero. I agree.

> Even without recursion, various traces of a program depend on a data and have different stack depths. That's why your estimate is utterly useless.

It'd be useless if we were attempting to give 100.000% guarantees.

> I can't believe you brought it up as anything else but jesting (maybe you are and I'm not getting it).

Jesting on a level where you might not get it, wouldn't be fun. And definitely boring and confusing to the rest of the crowd. :-)

Maybe I'll have to dig up prior art, or something. Clearly I'm not qualified to properly defend the validity of this idea.