Why stack overflow occurs

Connect and share knowledge within a single location that is structured and easy to search. How does a stack overflow occur and what are the best ways to make sure it doesn't happen, or ways to prevent one, particularly on web servers, but other examples would be interesting as well?

A stack, in this context, is the last in, first out buffer you place data while your program runs. Last in, first out LIFO means that the last thing you put in is always the first thing you get back out - if you push 2 items on the stack, 'A' and then 'B', then the first thing you pop off the stack will be 'B', and the next thing is 'A'.

When you call a function in your code, the next instruction after the function call is stored on the stack, and any storage space that might be overwritten by the function call. The function you call might use up more stack for its own local variables.

When it's done, it frees up the local variable stack space it used, then returns to the previous function. A stack overflow is when you've used up more memory for the stack than your program was supposed to use.

In embedded systems you might only have bytes for the stack, and if each function takes up 32 bytes then you can only have function calls 8 deep - function 1 calls function 2 who calls function 3 who calls function This might overwrite memory, code, etc.

Many programmers make this mistake by calling function A that then calls function B, that then calls function C, that then calls function A. It might work most of the time, but just once the wrong input will cause it to go in that circle forever until the computer recognizes that the stack is overblown.

Generally, the OS and the programming language you're using manage the stack, and it's out of your hands. You should look at your call graph a tree structure that shows from your main what each function calls to see how deep your function calls go, and to detect cycles and recursion that are not intended.

Intentional cycles and recursion need to be artificially checked to error out if they call each other too many times. Beyond good programming practices, static and dynamic testing, there's not much you can do on these high level systems. In the embedded world, especially in high reliability code automotive, aircraft, space you do extensive code reviews and checking, but you also do the following:.

It depends on the 'sandbox' you have whether you can control or even see the stack. Chances are good you can treat web servers as you would any other high level language and operating system - it's largely out of your hands, but check the language and server stack you're using.

It is possible to blow the stack on your SQL server, for instance. A stack overflow in real code occurs very rarely. Most situations in which it occurs are recursions where the termination has been forgotten.

It might however rarely occur in highly nested structures, e. The only real help here is to refactor the code to use an explicit stack object instead of the call stack. A stack overflow occurs when Jeff and Joel want to give the world a better place to get answers to technical questions. It's too late to prevent this stack overflow. That "other site" could have prevented it by not being scuzzy. Most people will tell you that a stack overflow occurs with recursion without an exit path - while mostly true, if you work with big enough data structures, even a proper recursion exit path won't help you.

Infinite recursion is a common way to get a stack overflow error. To prevent - always make sure there's an exit path that will be hit. Usually a stack overflow is the result of an infinite recursive call given the usual amount of memory in standard computers nowadays.

When you make a call to a method, function or procedure the "standard" way or making the call consists on:. So, usually this takes a few bytes depeding on the number and type of the parameters as well as the machine architecture. You'll see then that if you start making recursive calls the stack will begin to grow. Now, stack is usually reserved in memory in such a way that it grows in opposite direction to the heap so, given a big number of calls without "coming back" the stack begins to get full.

Now, on older times stack overflow could occur simply because you exausted all available memory, just like that. The call stack has a limited amount of memory available to it. Its size is determined by the programming language , the architecture , whether multi-threading is available on the CPU , and how much memory is available.

Usually, when a stack overflow error occurs, the program crashes and can either freeze or close the program. Any unsaved data or work is lost.

The stack overflow error is often caused by an infinite loop or the creation of variables larger than the size of the call stack. A run-time stack is a special area of computer memory that works on the LIFO principle Last in, first out : the last element added to a structure must be the first one to be removed.

The word "stack" refers to the manner in which several plates are stacked: you form a stack by putting the plates on top of each other this way of adding an object into the stack is called "push" and then remove them starting with the top plate this way of removing an object from the stack is known as "pop".

Run-time stack is also known as call stack , execution stack and machine stack these terms are used in order not to mix it up with the "stack" as an abstract data structure. The purpose of a stack is to allow the programmer to conveniently arrange calls of subroutines. A stack can be used to store arguments to be passed to a function being called and its local variables. If another function is called by the first one, it can pop the arguments from the stack and use them, as well as store its own variables in a memory area allocated for this function.

As it returns control, it also clears and frees the stack memory. High-level language programmers usually don't bother about such things, for the task of generating the necessary routine code is performed solely by the compiler. We have finally got close to the subject of our discussion.

As an abstraction, a stack is an infinite storage you can endlessly add new items into. Unfortunately, everything is finite in the real world - stack memory is no exception.

What will happen when it runs out as new arguments are being pushed into it or when a function allocates memory to store its variables? An error known as a stack overflow will occur. Since a stack is used to arrange calls of user subroutines and most programs written in contemporary programming languages - including object-oriented ones - actively employ functions one way or another , the program won't be able to call any function after the error occurs.

When that happens, the operating system takes control back, clears the stack and terminates the program. Here lies the difference between the buffer overflow and the stack overflow.

The former occurs when the program attempts to access a memory area outside the buffer's boundary and remains unnoticed if there is no protection against that; the program goes on to run correctly if lucky enough.

It's only when there is memory protection that a segmentation fault occurs. But when a stack overflow occurs, the program inevitably crashes. To be most precise, this scenario is only true for native languages. The virtual machine in managed languages has its own stack for managed programs, which is easier to monitor, so that you can even afford throwing an exception when a stack overflow occurs.

What are the reasons for this unpleasant error? Keeping in mind the above described mechanism, we can name one: too many embedded function calls. This scenario is especially probable when using recursion: it is actually this error that infinite recursion terminates with when there is no lazy evaluation mechanism , unlike an infinite loop which may be useful at times.

However, when there is a very small area of memory allocated on the stack which is, for instance, typical of microcontrollers , just a short sequence of calls will do the job. Another reason is local variables requiring too much stack memory. It's a bad idea to create a local array of a million of items or a million local variables just in case.

Just one call of such a "greedy" function may easily trigger a stack overflow. If you want to get large data amounts, you'd better use dynamic memory to be able to process an error in case it runs out. Dynamic memory, however, is quite slow to allocate and free because it is managed by the operating system.

Besides, you have to manually allocate and release it when provided with a direct access. Conversely, stack memory is allocated very quickly in fact you just need to change the value of one register ; moreover, objects allocated on the stack are automatically destroyed when the function returns control and clears the stack.

You naturally can't help the urge to exploit it. Therefore, the third reason for the bug is manual allocation of stack memory by the programmer. The C library provides the special function alloca for this purpose. An interesting thing is that while the malloc function intended to allocate dynamic memory has a "sibling" that frees it the free function , the alloca function has none: memory is freed automatically once the function returns control.

This thing is likely to complicate the issue, for you can't free memory before leaving the function. Though the man page for the alloca function clearly reads that it "is machine- and compiler-dependent; on many systems it cannot be used properly and may cause errors; its use is discouraged", programmers still use it.